c++ - constexpr 函数求值可以做尾递归优化吗

Question

我想知道对于长循环我们是否可以利用 C++11 中 constexpr 的尾递归？

Answer 1

根据[implimits] 中的规则，允许实现对constexpr 计算设置递归深度限制。具有完整 constexpr 实现的两个编译器(gcc 和 clang)都应用了这样的限制，使用标准建议的默认 512 递归调用。对于这两种编译器，以及遵循标准建议的任何其他实现，尾递归优化基本上是无法检测到的(除非编译器在达到其递归限制之前崩溃)。

一个实现可以选择只计算它无法在其递归深度限制中应用尾递归优化的调用，或者不提供这样的限制。然而，这样的实现可能会对其用户造成伤害，因为它可能会崩溃(由于堆栈溢出)或无法在深度或无限递归的 constexpr 评估上终止。

关于达到递归深度限制时会发生什么，Pubby 的示例提出了一个有趣的观点。 [expr.const]p2 指定

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

不是常量表达式。因此，如果在需要常量表达式的上下文中达到递归限制，则程序格式错误。如果在不需要常量表达式的上下文中调用 constexpr 函数，则实现通常不需要在翻译时尝试对其求值，但如果它选择这样做，并且递归限制为达到，则需要在运行时执行调用。在一个完整的、可编译的测试程序上:

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 说:

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)

clang 说:

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);
                                 ^

如果我们修改代码以便在翻译时不需要进行评估:

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);
}

然后两个编译器都接受它，并生成在运行时计算结果的代码。使用 -O0 构建时，此代码因堆栈溢出而失败。使用 -O2 构建时，编译器的优化器会转换代码以使用尾递归，并且代码可以正确运行(但请注意，此尾递归与 constexpr 评估无关)。