Warum kann ich nach dem Erhöhen von -fconstexpr-steps keinen konstanten Ausdruck auflösen?

Question

Nehmen Sie das folgende Beispiel 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'; 
} 

Trotz constexpr zu sein, ist es nicht bei der Kompilierung ausgewertet.
Der Trick, den ich gelernt habe, die Kompilierung Auswertung zu erzwingen ist, wie folgt:

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

Dies funktioniert ist g ++, jedoch bekomme ich den folgenden Fehler in Klirren ++:

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. 

Ich habe versucht, die constexpr-Schritten zu erhöhen, aber Klappern noch den Code nicht kompilieren:

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

Was muss ich für Klirren tun, um diesen Code zu kompilieren wie?

Klirren ++:

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

g ++:

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

Answer 1

Klirren nicht Funktion Anrufungen memoize constexpr.

Here is someone strugging with a similar problem. Die Anzahl der Schritte in fib (47) liegt in der Größenordnung von 2^45 oder 35184372088832. Wenn Sie diese vielen Schritte bei -fconstexpr-steps= senden, you get::

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

grundsätzlich Wert zu groß. Selbst wenn dies nicht der Fall wäre, würde der Compiler vermutlich aufgrund von fehlender Memoisierung in die Luft gehen, bevor er so viele Schritte ausgeführt hat. (Nun, Phi^47 ist näher an der Anzahl der rekursiven Schritte, aber das ist immer noch 36 Bits Größe und Clang speichert constexpr-steps in einem 32 Bit unsigned Int, also keine Würfel)

Memoization ist die Sache, wo Sie behalten verfolgen, welche Werte zu welchen Ergebnissen zugeordnet werden. So wertet g ++ fib (47) aus, indem es zuerst fib (46) und dann bis fib (1) und fib (0) auswertet. Dann wertet es fib (45) aus, aber hat es schon getan, als es fib (46) berechnet hat, also sieht es nur das Ergebnis nach und benutzt es.

g ++ läuft O (N + 1) Schritte zur Berechnung von fib (47). Clang merkt sich nicht und verfolgt das Ergebnis früherer Aufrufe von fib, sodass es den Binärbaum von rekursiven Aufrufen untersucht. Dies erfordert mehr als jede vernünftige Anzahl von Schritten und es trifft keine Tiefenbegrenzung oder Rekursionsgrenze, sondern eine Stufengrenze.

Die Kosten für das Memo sind, dass es mehr Speicher verwendet.

Damit call das Programm so kompiliert, wie es ist, müssen Sie den Quellcode des clang-Compilers selbst ändern, um seiner consExpr-Evaluierungs-Engine eine Memoisierung hinzuzufügen.

Answer 2

Das Problem scheint Sie stoßen exceeding the implementation-defined limits zu sein, die dann Anrufungen fib kein constant expression machen würde:

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

Insbesondere:

• Recursive constexpr function invocations [512].

Und vielleicht:

• Size of an object [262 144].

auch.

Der Indikator wäre, dass clang int arr[fib(3)]; in Ordnung hält, aber über int arr[fib(45)]; klagt, was eine eher irreführende Diagnose gibt.

Um dieses Problem zu umgehen, würde ich einen iterativen Algorithmus für Fibonacci verwenden, der schneller wäre und Ihr rekursives Tiefenproblem umgehen würde.

Answer 3

Da die Komplexität der naiven Fibonacci O(2^N) ist, 99999999 als 2^45 viel geringer ist. So können Sie versuchen, -fconstexpr-steps=35184372088832 zu setzen, aber ich vermute, dass einige interne Compiler-Grenzen treffen werden.

Answer 4

Wenn eine constexpr Auswertung Sie nicht zu haben, nicht definiertes Verhalten nach 5.20 [expr.const] Ziffer 2.6 erlaubt: Objekt

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) ... ]

Overflowing eine signierte ganze Zahl ist nicht definiertes Verhalten und fib(45) ist ein ziemlich großer Wert (Ich hätte früher Überläufe erwartet ...).Ich könnte mir vorstellen, dass der Code kompiliert OK (aber natürlich, schließlich die Ergebnisse falsch sind), wenn Sie

verwendet

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