Bug 820

What would you like to see? Something like a ConstMatrix class?

I would like to use Eigen datatypes (or a special datatype at least) within C++14 constexpr functions:

That is define a constexpr function like:

template<class EigenMat>
constexpr auto example(EigenMat m) {
  // C++14 allows here multiple statements, mutation of local variables, 
  // control flow (if, switch), iteration (for, while)... 
  auto new_mat = mat * mat.transpose();
  auto norm = new_mat.l2_norm();
  norm *= 2; 
  return norm.eval();
}

and use it on a constant expression matrix to initialize another constant expression:

constexpr Eigen::Matrix<3,3> m {1, 2, 3, 4, 5, 6, 7, 8, 9};
constexpr double test = example(m);

This should be possible for all stack allocated matrix/vector types.

I've encountered a couple of problems trying to adapt Eigen to do this:
- almost the whole interface and implementation of the type has to be annotated with constexpr since it is transitive (constexpr functions can only call other constexpr functions).
  - there is no current system to detect the language version in Eigen that I'm aware of
  - if one uses an EIGEN_CONSTEXPR macro it is worth noting that constexpr already 
     implies inline although compilers don't complain if you use constexpr inline
  - probably the GPU port of eigen requires annotating exactly the same functions so maybe
     both works could be unified
- the matrix type has to be a literal type. That is, among others:
  - it has to provide constexpr constructors (easy), and 
  - initialize all its variables: not so easy since current matrix types don't initialize its variables.
- there are some functions in which one uses static variables to perform some initialization. These are not allowed within constexpr functions but all cases that I've found could easily be changed to initialize the variables to their correct values at compile-time.

I can provide a patch of the first one (annotating the interface as constexpr for all existing matrix types in Eigen 3.2). However, changing the initialization mechanism is non-trivial although it could be maybe done by providing a constructor taking a std::initializer_list (I need to investigate this further and sadly I'm no expert on Eigen's framework for handling storage).

The problem is that would require to duplicate almost everything to have one version with constexpr and one without.

>The problem is that would require to duplicate almost everything to have one
version with constexpr and one without.

Why?

Is it possible to have something like:

template<int N> struct Foo {
  /* ... */
  constexpr int bar() {
    if(N>0) return N;
    else return rand();
};

constexpr Foo<1> f1;
Foo<-1> f2;

constexpr double d1 = f1.bar();
double d2 = f2.bar();

that is if an object is not instantiated as a constexpr then the constexpr qualifier of its class member are simply ignored? If so, then that's fine and could consider supporting that features through macro to make it optional. Look rather at the devel branch, not the 3.2.

constexpr means "can be used within a constant expression". All constexpr "things" (classes, functions) can be used at run-time without problems. As long as one doesn't do anything illegal at compile-time everything is fine. However, the compiler will check that one doesn't do anything illegal. For example:

constexpr int foo(int a) { return a < 3 ? a : throw(); }

is fine, but 

constexpr int foo(int a) { 
  static bool first = false;
  if (!first) { 
     first = true;
     return 3;
  } else {
     return a;
}

is illegal since static variables are not allowed. 

The following code works fine under clang 3.5:

#include <cstdlib>

template<int N> struct Foo {
  // You need constexpr constructors that initialize the object!
  constexpr Foo() {} 
  // constexpr doesn't imply const anymore!
  constexpr int bar() const { 
    if(N>0) return N;
    else return rand();
  }
};

int main() {

constexpr Foo<1> f1;
Foo<-1> f2;

// here f1's this pointer is const, so bar needs to be const:
constexpr double d1 = f1.bar();

double d2 = f2.bar();

return d2 + d1;
}

Add: constexpr int foo(int a) { return a < 3 ? a : throw(); } is legal, and you can use it to initialize constant expressions as long as foo doesn't throw (throwing at compile-time makes no sense... yet).

If this mostly requires adding `constexpr` to EIGEN_DEVICE_FUNC if available, I have no objections either. Maybe we should rename the macro then, and probably provide different versions of the macro if the sets of applicable functions are not identical.

(In reply to comment #6)
> The following code works fine under clang 3.5:
> 
> #include <cstdlib>
> 
> template<int N> struct Foo {
>   // You need constexpr constructors that initialize the object!
>   constexpr Foo() {} 
>   // constexpr doesn't imply const anymore!
>   constexpr int bar() const { 
>     if(N>0) return N;
>     else return rand();
>   }
> };

Wouldn't this require rand() to be a constexpr? Or is it?

Also, could you elaborate what happens (or is supposed to happen) if a constexpr method throws or asserts?

> Wouldn't this require rand() to be a constexpr? Or is it?

As long as you don't call rand() within the context of a constant expression, no, it doesn't need to be.

> Also, could you elaborate what happens (or is supposed to happen) if a constexpr method throws or asserts?

You get a compiler error since these things are not allowed within the context of a constant expression.

So what does constexpr do? Constexpr means "this function can be used within the context of a constant expression".  The compiler will check some very illegal things (like using static variables or lambda functions). But by allowing throw and asserts, you can reuse the same code for run-time and compile-time computations since these throws and asserts will only trigger _for some inputs_, and as long as you call the function with inputs that do not trigger them within the context of a constant expression, everything is fine (the result of the function is "computable"). 

The main limitations are on the types that you use as parameters and inside those functions (they must be literal types, i.e., they must have constexpr constructors among other things), uninitialized values are not allowed, static variables are not allowed, ... 

Another example are template constexpr functions. For some types the function might be usable within constant expressions, and for other types it might just be usable at run-time. It is up to the programmer to make sure that in constant expressions the function works well (otherwise the compiler will remind you).

>If this mostly requires adding `constexpr` to EIGEN_DEVICE_FUNC if available, I
have no objections either.

It also requires literal types, that is, constexpr constructors that initialize the stack memory to some value (since uninitialized values are not allowed). This is AFAIK not done in stack types within eigen (e.g. when noCols/maxCols and noRows/maxRows at compile time are both known).

(In reply to comment #9)
> > Also, could you elaborate what happens (or is supposed to happen) if a constexpr method throws or asserts?
> 
> You get a compiler error since these things are not allowed within the context
> of a constant expression.

Ok, that would be exactly what we want: We practically get some static assertions for free.

> So what does constexpr do? Constexpr means "this function can be used within
> the context of a constant expression". [...]

Ok, so basically it's a "Please write this in front of all your functions and I will check where it is legal anyways"-flag.
With the exception that for some functions (e.g. those using static variables) it is illegal in any case (not only when called with bad parameters).
In a way that seems similar to CUDA's __device__ qualifier (here also the compiler checks anyways if it is a legal device function ...)

> It also requires literal types, that is, constexpr constructors that initialize
> the stack memory to some value (since uninitialized values are not allowed).

This would at the moment only allow initializations combined out of Zero(), Ones(), Identity(), etc and Vectors up to size 4. E.g., the following could already be possible (after adding constexpr everywhere):

constexpr Matrix4d foo = Matrix4d::Ones() + Vector4d(1,2,3,4)*Vector4d(5,6,7,8).transpose();

Of course for meaningful applications would require C++11-style initializer lists.
We had a mailing list discussion about that some time ago:
http://listengine.tuxfamily.org/lists.tuxfamily.org/eigen/2014/02/threads.html#00007

>"Please write this in front of all your functions and I
will check where it is legal anyways"

I have already done this (so I can and am willing to submit a patch with this). And yes, the keyword doesn't IMO add anything to the language.. pretty annoying. 

> constexpr Matrix4d foo = Matrix4d::Ones() + Vector4d(1,2,3,4)*Vector4d(5,6,7,8).transpose();

I will try this later, but the thing is memory cannot be uninitialized within constexpr objects. That is, if at some point that expression gets evaluated to something like:

struct Storage {
  constexpr Storage() {}
  double data[4];
};

struct Matrix : Storage {  
  // ...
};

Matrix m;  // data is uninitialized, panic!
for (auto&& i : range(0,4)) { m.data[i] = expr(i); }

it will complain that data is uninitialized (I got stucked with this since I don't know the storage classes of Eigen that well). 

Initializer lists should however work, i.e., something like 

struct Storage {
  constexpr Storage() : data{0} {}
  constexpr Storage(std::initializer_list<double> values) : data{values} {}
  double data[4];
};

I'll take a look at this example later and report which errors I get when the whole interface is annotated with constexpr.

(In reply to comment #11)
> Matrix m;  // data is uninitialized, panic!
> for (auto&& i : range(0,4)) { m.data[i] = expr(i); }

Extremely simplified we do something like this:

  class Matrix{
    Storage data;
  public:
    Matrix() { /* don't initialize by default */ }
    Matrix(const Expression &expr) {
      for(...) data(i,j)=expr(i,j);
    }
  };

Would that allow the following? (assuming expr is a constexpr)
  constexpr Matrix A=expr;


There are compile-time options to initialize matrices with 0 or with NaN:
  EIGEN_INITIALIZE_MATRICES_BY_ZERO, EIGEN_INITIALIZE_MATRICES_BY_NAN
http://eigen.tuxfamily.org/dox-devel/TopicPreprocessorDirectives.html

These are not enabled by default since they can get rather expensive in certain situations.

> Would that allow the following? (assuming expr is a constexpr)
>  constexpr Matrix A=expr;

I don't think so since even if we mark the constructor as constexpr :

   constexpr Matrix(const Expression &expr) { ... }

it doesn't initialize the data in the initialization list (which if IIRC is what the requirement for literal types specifies, I need to re-check the new standard since I've only been playing with this a few weeks...).

> There are compile-time options to initialize matrices with 0 or with NaN:
>  EIGEN_INITIALIZE_MATRICES_BY_ZERO, EIGEN_INITIALIZE_MATRICES_BY_NAN
> http://eigen.tuxfamily.org/dox-devel/TopicPreprocessorDirectives.html

I'll try these and see if I can get it to work. Do they initialize the data in the constructor initialization list for stack allocated matrices?

>These are not enabled by default since they can get rather expensive in certain
>situations.

I don't want to pay the price of initialization at run-time since the data is going to be initialized anyways just afterwards.

An option would be to initialize the data _only_ for stack allocated matrices _if_ the user wants to enable Eigen within constant expressions. Matrices on the stack are typically "small" and the stack is fast. Maybe the difference (if measurable) is worth it for those who want to use Eigen within constant expressions.

btw,  I doubt that SSE intrinsics are constexpr, so I'm afraid you'll also have to disable vectorization to make it work.  A workaround would be to use Matrix<> types with the  DontAlign option which currently also disable vectorization for fixed size matrices. A more future solution would be to add a DontVectorize option.

If this requires initialization via the initialization list, I doubt that we can provide a C++03-compatible solution. If there is a significant benefit, we could still consider this for Eigen 4. Otherwise, (and if no C++03 compatible solution exists) I'd suggest making this a WONTFIX.

@Gael Guennebaud:

There has been progress on Clang on being able to evaluate intrinsics at compile time and most of them should work (although they aren't marked as `constexpr` yet, calling the `__builtin_intrinsics` should still work.

thanks, that's a good news.

@Gael and @Christoph, for this to be possible, clang would need to be able to evaluate all intrinsics (including SIMD intrinsics) at compile-time. 

Since that is a titanic task, some developers are asking which intrinsics are actually used by Eigen, so that they can prioritize those:

Can any of you briefly chim in to the discussion here:

https://llvm.org/bugs/show_bug.cgi?id=31446#c6

and maybe point them to where the intrinsics in Eigen3 are defined? 

I think a good first step goal would be to try to be able to evaluate SSE2 intrinsics at compile-time, but obviously for allowing Eigen to offer a constexpr interface it will need to go all the way up to AVX2. Maybe a list of the intrinsics actually used would help them. 

I am also starting to think, that a more pragmatic way of implementing this would be to just add a __builtin_inside_constexpr() function that returns true when the current function is being evaluated inside a constant expression, and allows branching or overloading based on that.

Created attachment 773 [details]
List of SSE, AVX, AVX512 intrinsics used by Eigen.

Here is the sorted list of SSE, AVX, AVX512 intrinsics used by Eigen. To generate it, simply run:

$ grep -hwo -e '_mm[a-z_0-9]*' Eigen/src/Core/arch/ -R | sort -u

So just to keep you guys in the loop. Clang will include in the near future (hopefully in clang 5.0 that will be released in August) a way to detect when something is being evaluated at compile-time, and branch on it, so that Eigen could use something like:

#ifdef CLANG
if constexpr(__ctfe) {
  // call non-intrinsic version of the algorithm
] else {
#endif
  // use intrinsics as usual
#ifdef CLANG
}
#endif

That would allow making the whole interface of eigen easily usable at compile-time (C++17 constexpr is really powerful), and hopefully, something similar will be picked by GCC, and MSVC in the future.

There seem to be a lot of people interested in writing a paper to standardize this by the C++20 time-frame.

Thank you for the info This is indeed a useful feature.

-- GitLab Migration Automatic Message --

This bug has been migrated to gitlab.com's GitLab instance and has been closed from further activity.

You can subscribe and participate further through the new bug through this link to our GitLab instance: https://gitlab.com/libeigen/eigen/issues/820.