Meine Programmiersprache kompiliert nach C, ich möchte Tail Recursion-Optimierung implementieren. Die Frage hier ist, wie die Kontrolle an eine andere Funktion übergeben wird, ohne von der aktuellen Funktion "zurückzukehren".
Es ist ziemlich einfach, wenn das Steuerelement an dieselbe Funktion übergeben wird:
%Vor%Wie Sie sehen können, gibt es keinen Rückgabewert und keine Parameter, diese werden in einem separaten Stack übergeben, der durch eine globale Variable adressiert ist.
Eine weitere Option ist die Inline-Assembly:
%Vor% Dies ist ähnlich zu goto , aber wenn goto die Kontrolle an die erste Anweisung in einer Funktion übergibt, wird der von einem Compiler erzeugte "entry code" übersprungen, jmp ist anders, sein Argument ist eine Funktion Zeiger, und Sie müssen 4 oder 8 Bytes hinzufügen, um den Zugangscode zu überspringen.
Die beiden obigen Funktionen funktionieren nur dann, wenn der Angerufene und der Aufrufer die gleiche Menge an Stack für lokale Variablen verwenden, die durch den Zugangscode des Angerufenen zugewiesen wird.
Ich habe versucht, leave manuell mit Inline Assembly zu machen, dann die Return-Adresse auf dem Stack zu ersetzen und dann einen legal Funktionsaufruf wie f() auszuführen. Aber meine Versuche sind alle abgestürzt. Sie müssen BP und SP irgendwie ändern.
Also noch einmal, wie das für x64 zu implementieren? (Angenommen, Funktionen haben keine Argumente und geben void zurück). Tragbare Art ohne Inline-Montage ist besser, aber die Montage wird akzeptiert. Vielleicht kann longjump verwendet werden?
Vielleicht können Sie die Adresse des Angerufenen sogar auf den Stapel schieben, indem Sie die ursprüngliche Absenderadresse und nur ret ?
Versuche nicht, das selbst zu tun. Ein guter C-Compiler kann in vielen Fällen Tail-Call-Eliminierung durchführen und wird dies tun. Im Gegensatz dazu hat ein Hack mit Inline-Assemblierung eine gute Chance, auf eine schwer zu debuggende Art und Weise einen Fehler zu machen.
Siehe beispielsweise dieses Snippet auf godbolt.org. Um es hier zu duplizieren:
Der von mir verwendete C-Code war:
%Vor%Dies kompiliert zu:
%Vor% Beachten Sie, dass der Endanruf beseitigt wurde. Das einzige call ist puts .
Da Sie keine Argumente und Rückgabewerte benötigen, wie wäre es, wenn Sie alle Funktionen zu einem zusammenfassen und anstelle von Funktionsnamen Bezeichnungen verwenden würden?
%Vor%Der schwierige Teil hier ist RETURN und CALL-Makros. Um zurückzukommen, solltest du noch einen weiteren Stack, einen Stapel von Setjump-Puffern, behalten, wenn du zurückkommst, rufst du longjump (ret_stack.pop ()) auf, und wenn du rufst, tust du ret_stack.push (setjump (f)). Dies ist poetische Wiedergabe von c, Sie müssen die Details ausfüllen.
gcc kann hier eine Optimierung mit berechnetem goto bieten, sie sind leichter als longjump. Auch Leute, die vms schreiben, haben ähnliche Probleme und scheinbar asm-basierte Lösungen für die, selbst auf MSVC, siehe Beispiel hier .
Und schließlich kann ein solcher Ansatz selbst dann, wenn er Speicher spart, für den Compiler verwirrend sein und somit Leistungsanomalien verursachen. Sie wahrscheinlich besser für einige tragbare Assembler-ähnliche Sprache generieren, llvm vielleicht? Nicht sicher, sollte etwas sein, das goto berechnet hat.
Der ehrwürdige Ansatz für dieses Problem besteht darin, Trampoline zu verwenden. Im Wesentlichen gibt jede kompilierte Funktion einen Funktionszeiger (und möglicherweise eine Arg-Zahl) zurück. Die oberste Ebene ist eine enge Schleife, die, beginnend mit Ihrem main , einfach den zurückgegebenen Funktionszeiger ad infinitum aufruft. Sie könnten eine Funktion, die longjmp s verwendet, verwenden, um die Schleife zu verlassen, d. H. Das Programm zu beenden.
Siehe dieses SO Q & amp; A. Oder Google "Rekursion tco Trampolin . "
Für einen anderen Ansatz siehe Cheney auf der MTA , wo der Stapel gerade wächst, bis er voll ist löst einen GC aus. Dies funktioniert, sobald das Programm in Continuation Passing Style (CPS) konvertiert wird, da Funktionen in diesem Stil nie zurückkehren; Nach dem GC ist der Stack also Müll und kann wiederverwendet werden.
Ich werde einen Hack vorschlagen. Die Anweisung x86 call , die vom Compiler zum Übersetzen Ihrer Funktionsaufrufe verwendet wird, drückt die Rücksprungadresse auf dem Stapel und führt dann einen Sprung aus.
Was Sie tun können, ist ein bisschen eine Stapelmanipulation, mit einer Inline-Assembly und möglicherweise ein paar Makros, um sich ein bisschen Kopfschmerzen zu ersparen. Sie müssen im Grunde die Rücksprungadresse auf dem Stack überschreiben, was Sie sofort in der aufgerufenen Funktion tun können. Sie können eine Wrapper-Funktion haben, die die Rückgabeadresse überschreibt und Ihre Funktion aufruft - der Kontrollfluss kehrt dann zu dem Wrapper zurück, der dann dorthin wandert, wo Sie ihn angegeben haben.
Tags und Links c compiler-construction tail-recursion