Can constexpr function evaluation do tail recursion optimization

Question

I wonder whether for long loops we can take advantage of tail recursion for constexpr in C++11?

Answer 1

By the rules in [implimits], an implementation is permitted to put a recursion depth limit on constexpr calculations. The two compilers which have complete constexpr implementations (gcc and clang) both apply such a limit, using the default of 512 recursive calls as suggested by the standard. For both of these compilers, as well as any other implementation which follows the standard's suggestion, a tail recursion optimization would be essentially undetectable (unless the compiler would otherwise crash before reaching its recursion limit).

An implementation could instead choose to only count calls for which it could not apply a tail-recursion optimization in its recursion depth limit, or to not provide such a limit. However, such an implementation would probably be doing a disservice to its users, since it would be likely to either crash (due to a stack overflow) or fail to terminate on constexpr evaluations which recurse deeply or infinitely.

With regard to what happens when the recursion depth limit is reached, Pubby's example raises an interesting point. [expr.const]p2 specifies that

an invocation of a constexpr function or a constexpr constructor that would exceed the implementation-defined recursion limits (see Annex B);

is not a constant expression. Therefore, if the recursion limit is reached in a context which requires a constant expression, the program is ill-formed. If a constexpr function is called in a context which does not require a constant expression, the implementation is not generally required to attempt to evaluate it at translation time, but if it chooses to, and the recursion limit is reached, it is required to instead perform the call at runtime. On a complete, compilable test program:

constexpr unsigned long long f(unsigned long long n, unsigned long long s=0) {
  return n ? f(n-1,s+n) : s;
}
constexpr unsigned long long k = f(0xffffffff);

GCC says:

depthlimit.cpp:4:46:   in constexpr expansion of ‘f(4294967295ull, 0ull)’
depthlimit.cpp:2:23:   in constexpr expansion of ‘f((n + -1ull), (s + n))’
depthlimit.cpp:2:23:   in constexpr expansion of ‘f((n + -1ull), (s + n))’
[... over 500 more copies of the previous message cut ...]
depthlimit.cpp:2:23:   in constexpr expansion of ‘f((n + -1ull), (s + n))’
depthlimit.cpp:4:46: error: constexpr evaluation depth exceeds maximum of 512 (use -fconstexpr-depth= to increase the maximum)

and clang says:

depthlimit.cpp:4:30: error: constexpr variable 'k' must be initialized by a constant expression
constexpr unsigned long long k = f(0xffffffff);
                             ^   ~~~~~~~~~~~~~
depthlimit.cpp:2:14: note: constexpr evaluation exceeded maximum depth of 512 calls
  return n ? f(n-1,s+n) : s;
             ^
depthlimit.cpp:2:14: note: in call to 'f(4294966784, 2194728157440)'
depthlimit.cpp:2:14: note: in call to 'f(4294966785, 2190433190655)'
depthlimit.cpp:2:14: note: in call to 'f(4294966786, 2186138223869)'
depthlimit.cpp:2:14: note: in call to 'f(4294966787, 2181843257082)'
depthlimit.cpp:2:14: note: in call to 'f(4294966788, 2177548290294)'
depthlimit.cpp:2:14: note: (skipping 502 calls in backtrace; use -fconstexpr-backtrace-limit=0 to see all)
depthlimit.cpp:2:14: note: in call to 'f(4294967291, 17179869174)'
depthlimit.cpp:2:14: note: in call to 'f(4294967292, 12884901882)'
depthlimit.cpp:2:14: note: in call to 'f(4294967293, 8589934589)'
depthlimit.cpp:2:14: note: in call to 'f(4294967294, 4294967295)'
depthlimit.cpp:4:34: note: in call to 'f(4294967295, 0)'
constexpr unsigned long long k = f(0xffffffff);
                                 ^

If we modify the code so that the evaluation is not required to occur at translation time:

constexpr unsigned long long f(unsigned long long n, unsigned long long s=0) {
  return n ? f(n-1,s+n) : s;
}
int main(int, char *[]) {
  return f(0xffffffff);
}

then both compilers accept it, and generate code which computes the result at runtime. When building with -O0, this code fails due to stack overflow. When building with -O2, the compilers' optimizers transform the code to use tail recursion and the code functions correctly (but note that this tail recursion is unrelated to constexpr evaluation).

Answer 2

I don't see why it could not be possible, however it is a quality of implementation detail.

It has been traditional to use memoization for templates for example, so that compilers no longer choke on:

template <size_t N>
struct Fib { static size_t const value = Fib <N-1>::value + Fib<N-2>::value; };

template <>
struct Fib<1> { static size_t const value = 1; }

template <>
struct Fib<0> { static size_t const value = 0; }

but instead memoize the already computed value to reduce the complexity of its evaluation to O(N).

Tail-recursion (and pseudo tail-recursion) are optimizations, and like most optimizations are not subjected to the Standard, so there is no reason it would not be possible. Whether a particular compiler uses it or not, however, is hard to predict.

The Standard says in 5.19 [expr.const]:

2/ A conditional-expression is a core constant expression unless it involves one of the following as a potentially evaluated subexpression (3.2) [...]:

• an invocation of a constexpr function or a constexpr constructor that would exceed the implementationdefined recursion limits (see Annex B);

And reading Annex B:

2/ The limits may constrain quantities that include those described below or others. The bracketed number following each quantity is recommended as the minimum for that quantity. However, these quantities are only guidelines and do not determine compliance.

• Recursive constexpr function invocations [512].

Tail recursion is not brooched.