Почему я не могу разрешить постоянное выражение после увеличения -fconstexpr-шагов?

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

Это работает, г ++, однако я получаю следующее сообщение об ошибке в звоне ++:

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-шагов, но лязг все еще не будет компилировать код:

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

Что я должен сделать для лязга, чтобы скомпилировать этот код, как это?

лязг ++:

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

г ++:

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

Answer 1

лязга не memoize 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 бит размера, а кланг хранит constexpr-steps в 32-битном беззнаковом int, поэтому нет кубиков)

Меморандум - это то, что вы храните отслеживать, какие значения соответствуют каким результатам. Таким образом, g ++ оценивает функцию fib (47), сначала оценивая fib (46), а затем вплоть до fib (1) и fib (0). Затем он вычисляет значение fib (45), но это уже делалось, когда он вычислял fib (46), поэтому он просто ищет результат и использует его.

g ++ выполняет шаги O (N + 1) для вычисления fib (47). Clang не запоминает и не отслеживает результат предыдущих вызовов для fib, поэтому он исследует двоичное дерево рекурсивных вызовов. Это занимает больше, чем любое разумное количество шагов, и оно не достигает предела глубины или предела рекурсии, а является предельным шагом.

Стоимость меморандума заключается в том, что он использует больше памяти.

Чтобы сделать clang компиляцией программы как есть, вам нужно будет изменить исходный код компилятора clang, чтобы добавить memoization в свой механизм оценки constexpr.

Answer 2

Проблема Вы сталкиваетесь, кажется exceeding the implementation-defined limits, что позволило бы сделать вызовы к fib не constant expression:

A conditional-expressione 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 3

Учитывая, что сложность наивного Фибоначчи равна O(2^N), 99999999 намного меньше, чем 2^45. Поэтому вы можете попробовать ввести -fconstexpr-steps=35184372088832, но я подозреваю, что ударит некоторые внутренние ограничения компилятора.

Answer 4

При оценке 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) { ... }