Warum optimiert g ++ immer noch die Tail-Rekursion, wenn das Ergebnis der Rekursionsfunktion multipliziert wird?

Question

Sie sagen, die Tail-Rekursion-Optimierung funktioniert nur, wenn der Aufruf kurz vor der Rückkehr aus der Funktion ist. So zeigen sie diesen Code als Beispiel dafür, was sollte nicht von C-Compiler optimiert werden:

long long f(long long n) { 
    return n > 0 ? f(n - 1) * n : 1; 
} 

, weil es der rekursive Funktionsaufruf von n multipliziert wird, was bedeutet, dass die letzte Operation Multiplikation, nicht rekursiven Aufruf. Es ist jedoch ist auch auf -O1 Ebene:

recursion`f: 
    0x100000930 <+0>: pushq %rbp 
    0x100000931 <+1>: movq %rsp, %rbp 
    0x100000934 <+4>: movl $0x1, %eax 
    0x100000939 <+9>: testq %rdi, %rdi 
    0x10000093c <+12>: jle 0x10000094e    
    0x10000093e <+14>: nop  
    0x100000940 <+16>: imulq %rdi, %rax 
    0x100000944 <+20>: cmpq $0x1, %rdi 
    0x100000948 <+24>: leaq -0x1(%rdi), %rdi 
    0x10000094c <+28>: jg  0x100000940    
    0x10000094e <+30>: popq %rbp 
    0x10000094f <+31>: retq 

Sie sagen, dass:

Ihre endgültige Regeln sind daher ausreichend zu korrigieren. Rückgabe n * fact(n - 1) hat jedoch eine Operation in der Endposition! Dies ist die Multiplikation *, die das letzte ist, was die Funktion tut, bevor sie zurückkehrt. In einigen Sprachen könnte dies tatsächlich als Funktionsaufruf implementiert sein, der dann als Tail-Call optimiert werden könnte.

Wie wir jedoch aus der ASM-Auflistung sehen, ist die Multiplikation immer noch ein ASM-Befehl, keine separate Funktion. So kämpfe ich wirklich Unterschied mit Akku Ansatz zu sehen:

int fac_times (int n, int acc) { 
    return (n == 0) ? acc : fac_times(n - 1, acc * n); 
} 

int factorial (int n) { 
    return fac_times(n, 1); 
} 

Dies erzeugt

recursion`fac_times: 
    0x1000008e0 <+0>: pushq %rbp 
    0x1000008e1 <+1>: movq %rsp, %rbp 
    0x1000008e4 <+4>: testl %edi, %edi 
    0x1000008e6 <+6>: je  0x1000008f7    
    0x1000008e8 <+8>: nopl (%rax,%rax) 
    0x1000008f0 <+16>: imull %edi, %esi 
    0x1000008f3 <+19>: decl %edi 
    0x1000008f5 <+21>: jne 0x1000008f0    
    0x1000008f7 <+23>: movl %esi, %eax 
    0x1000008f9 <+25>: popq %rbp 
    0x1000008fa <+26>: retq 

ich etwas fehlt? Oder sind Compiler nur schlauer geworden?

Answer 1

Wie Sie in dem Assembler-Code zu sehen, ist der Compiler intelligent genug, um Ihren Code in eine Schleife zu drehen, die im Wesentlichen äquivalent zu (die verschiedenen Datentypen abgesehen):

int fac(int n) 
{ 
    int result = n; 
    while (--n) 
     result *= n; 
    return result; 
} 

GCC intelligent genug, um zu wissen, dass der bei jedem Aufruf zu Ihrem ursprünglichen f benötigte Zustand in zwei Variablen (n und result) durch die gesamte rekursive Aufrufsequenz gehalten werden kann, so dass kein Stack notwendig ist. Es kann f zu fac_times und beide zu fac sozusagen umwandeln. Dies ist höchstwahrscheinlich nicht nur ein Ergebnis der Tail-Call-Optimierung im engeren Sinne, sondern auch eine der vielen anderen Heuristiken, die GCC zur Optimierung verwendet.

(Ich kann nicht mehr ins Detail in Bezug auf die spezifische Heuristik gehen, die hier verwendet werden, da ich weiß nicht genug über sie.)

Answer 2

Der nicht-Akkumulator f ist nicht Schwanz-rekursiv. Zu den Optionen des Compilers gehört das Umwandeln in eine Schleife durch Umwandeln oder call/einige insns/ret, aber jmp f ohne andere Umwandlungen nicht.

Tail-Call-Optimierung gilt in Fällen wie folgt aus:

int ext(int a); 
int foo(int x) { return ext(x); } 

asm Ausgabe von godbolt:

foo:         # @foo 
     jmp  ext      # TAILCALL 

Tail-Call-Optimierung bedeutet, eine Funktion (oder recursing) mit einem jmp verlassen statt a ret. Alles andere ist nicht Heckbereichsoptimierung. Tail-Rekursion, die mit einem jmp optimiert ist, ist wirklich eine Schleife.

Ein guter Compiler wird weitere Transformationen durchführen, um die bedingte Verzweigung möglichst am Ende der Schleife zu platzieren, wobei die unbedingte Verzweigung entfernt wird. (In asm ist der do{}while() Stil der Schleife am natürlichsten).