c++ - 为什么在增加 -fconstexpr-steps 后无法解析常量表达式？

Question

以下面的constexpr为例:

#include <iostream>

constexpr int fib(const int i)
{
  if (i == 0) return 0;
  if (i == 1) return 1;
  return fib(i-1) + fib(i-2);
}

int main(){
  std::cout << fib(45) << '\n';
}

尽管是 constexpr，但它不会在编译时求值。
我学到的执行编译时评估的技巧如下:

#include <iostream>
#include <type_traits>

#define COMPILATION_EVAL(e) (std::integral_constant<decltype(e), e>::value)

constexpr int fib(const int i)
{
  if (i == 0) return 0;
  if (i == 1) return 1;
  return fib(i-1) + fib(i-2);
}

int main(){
  std::cout << COMPILATION_EVAL(fib(45)) << '\n';
}

这适用于 g++，但是我在 clang++ 中收到以下错误:

clang++-3.9 --std=c++1z -o main main.cpp 

main.cpp:14:33: error: non-type template argument is not a constant expression
  std::cout << COMPILATION_EVAL(fib(45)) << '\n';
                                ^~~~~~~
main.cpp:4:66: note: expanded from macro 'COMPILATION_EVAL'
#define COMPILATION_EVAL(e) (std::integral_constant<decltype(e), e>::value)
                                                                 ^
main.cpp:9:3: note: constexpr evaluation hit maximum step limit; possible infinite loop?
  if (i == 1) return 1;
  ^
main.cpp:10:21: note: in call to 'fib(7)'
  return fib(i-1) + fib(i-2);
                    ^
main.cpp:10:21: note: in call to 'fib(9)'
main.cpp:10:10: note: in call to 'fib(11)'
  return fib(i-1) + fib(i-2);
         ^
main.cpp:10:10: note: in call to 'fib(12)'
main.cpp:10:10: note: in call to 'fib(13)'
main.cpp:10:21: note: (skipping 23 calls in backtrace; use -fconstexpr-backtrace-limit=0 to see all)
  return fib(i-1) + fib(i-2);
                    ^
main.cpp:10:10: note: in call to 'fib(41)'
  return fib(i-1) + fib(i-2);
         ^
main.cpp:10:10: note: in call to 'fib(42)'
main.cpp:10:10: note: in call to 'fib(43)'
main.cpp:10:10: note: in call to 'fib(44)'
main.cpp:14:33: note: in call to 'fib(45)'
  std::cout << COMPILATION_EVAL(fib(45)) << '\n';
                                ^
1 error generated.  

我尝试增加 constexpr-steps，但 clang 仍然无法编译代码:

clang++-3.9 -fconstexpr-depth=99999999 -fconstexpr-backtrace-limit=9999999 -fconstexpr-steps=99999999 --std=c++1z -o main main.cpp

我必须做什么才能让 clang 按原样编译这段代码？

clang ++:

clang version 3.9.0-svn267343-1~exp1 (trunk)

g++:

g++ (Ubuntu 5.1.0-0ubuntu11~14.04.1) 5.1.0

Answer 1

clang 不会内存 constexpr 函数调用。

Here is someone strugging with a similar problem .

fib(47) 中的步数约为 2^45，或 35184372088832。如果您在 -fconstexpr-steps= 发送这么多步骤，you get: :

error: invalid integral value '35184372088832' in '-fconstexpr-steps 35184372088832'

基本上，值太大了。即使不是，由于缺乏内存，编译器也可能在运行那么多步骤之前就崩溃了。 (好吧，phi^47 更接近递归步数，但这仍然是 36 位大小，clang 将 constexpr-steps 存储在 32 位 unsigned int 中，所以没有骰子)

内存是您跟踪哪些值映射到哪些结果的方法。所以 g++ 通过首先评估 fib(46) 然后一直向下评估 fib(1) 和 fib(0) 来评估 fib(47)。然后它计算 fib(45)，但是它在计算 fib(46) 时已经这样做了，所以它只是查找结果并使用它。

g++ 运行 O(N+1) 步来计算 fib(47)。 Clang 不会内存和跟踪先前调用 fib 的结果，因此它会探索递归调用的二叉树。这需要超过任何合理数量的步骤，并且它没有达到深度限制或递归限制，而是达到了步骤限制。

内存的代价是它使用更多的内存。

为了让 clang 按原样编译程序，您必须修改 clang 编译器源代码本身以将内存添加到其 constexpr 评估引擎。