为什么在增加 -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 version 3.9.0-svn267343-1~exp1 (trunk)

g++:

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

Answer 1

您遇到的问题似乎是 exceeding the implementation-defined limits, which would then make invocations to fib not a constant expression:

A conditional-expression e is a core constant expression unless the evaluation of e, following the rules of the abstract machine ([intro.execution]), would evaluate one of the following expressions:

an expression that would exceed the implementation-defined limits (see Annex [implimits]);

特别是：

Recursive constexpr function invocations [512].

并且可能：

Size of an object [262 144].

还有。

指标是 clang 认为 int arr[fib(3)]; 正常但抱怨 int arr[fib(45)];，给出了一个误导性的诊断。

为了解决这个问题，我会使用斐波那契的迭代算法，它会更快并且解决你的递归深度问题。

Answer 2

鉴于朴素斐波那契的复杂度为 O(2^N)，99999999 远小于 2^45。所以你可以尝试输入 -fconstexpr-steps=35184372088832，但我怀疑这会达到一些内部编译器限制。

Answer 3

在评估 constexpr 时，根据 5.20 [expr.const] 第 2.6 段，您不允许有未定义的行为：

an operation that would have undefined behavior as specified in Clauses 1 through 16 of this International Standard [Note: including, for example, signed integer overflow (Clause 5) ... ]

溢出有符号整数对象是未定义的行为，fib(45) 是一个相当大的值（我预计会比这更早发生溢出...）。如果您使用

，我会想象代码编译正常（但当然，最终结果是错误的）

constexpr unsigned int fib(unsigned int i) { ... }

Answer 4

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 位无符号整数中，所以没有骰子）

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

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

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

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

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

Why can't I resolve a constant expression after increasing -fconstexpr-steps?

c++

compile-time-constant

constexpr

clang++

c++17