Schreiben eines JIT-Compilers in Assembly

Ich habe eine virtuelle Maschine in C geschrieben, die für eine Nicht-JIT-VM eine anständige Leistung bietet, aber ich möchte etwas Neues lernen und die Leistung verbessern. Meine aktuelle Implementierung verwendet einfach einen Schalter, um den VM-Bytecode in Anweisungen zu übersetzen, die in eine Sprungtabelle kompiliert werden. Wie gesagt, anständige Leistung für das, was es ist, aber ich bin auf eine Barriere gestoßen, die nur mit einem JIT-Compiler überwunden werden kann.

Ich habe vor nicht allzu langer Zeit bereits eine ähnliche Frage zum selbstmodifizierenden Code gestellt, aber mir wurde klar, dass ich nicht die richtige Frage gestellt hatte.

Mein Ziel ist es also, einen JIT-Compiler für diese virtuelle C-Maschine zu schreiben, und ich möchte dies in einer x86-Assembly tun. (Ich verwende NASM als Assembler) Ich bin mir nicht ganz sicher, wie ich das machen soll. Ich bin mit der Assemblierung vertraut und habe mir einige selbstmodifizierende Codebeispiele angesehen, aber ich habe noch nicht herausgefunden, wie die Codegenerierung funktioniert.

Mein Hauptblock bisher ist das Kopieren von Anweisungen in ein ausführbares Stück Speicher, mit meine Argumente. Mir ist bewusst, dass ich eine bestimmte Zeile in NASM kennzeichnen und die gesamte Zeile von dieser Adresse mit den statischen Argumenten kopieren kann, aber das ist nicht sehr dynamisch und funktioniert nicht für einen JIT-Compiler. Ich muss in der Lage sein, die Anweisung aus dem Bytecode zu interpretieren, sie in den ausführbaren Speicher zu kopieren, das erste Argument zu interpretieren, es in den Speicher zu kopieren, dann das zweite Argument zu interpretieren und es in den Speicher zu kopieren.

Ich wurde über mehrere Bibliotheken informiert, die diese Aufgabe erleichtern würden, wie GNU Lightning und sogar LLVM. Ich möchte dies jedoch zuerst von Hand schreiben, um zu verstehen, wie es funktioniert, bevor ich externe Ressourcen verwende.

Gibt es Ressourcen oder Beispiele, die diese Community bereitstellen könnte, um mir beim Einstieg in diese Aufgabe zu helfen? Ein einfaches Beispiel, das zwei oder drei Anweisungen wie „add“ und „mov“ zeigt, die verwendet werden, um ausführbaren Code mit Argumenten dynamisch im Speicher zu generieren, würde Wunder bewirken.

Ich würde überhaupt nicht empfehlen, ein JIT in Assembly zu schreiben. Es gibt gute Argumente dafür, die am häufigsten ausgeführten Bits der zu schreiben Dolmetscher bei der Montage. Ein Beispiel dafür, wie dies aussieht, finden Sie hier Kommentar von Mike Pallder Autor von LuaJIT.

Was das JIT betrifft, gibt es viele verschiedene Ebenen mit unterschiedlicher Komplexität:

1. Kompilieren Sie einen Basisblock (eine Folge von nicht verzweigten Anweisungen), indem Sie einfach den Code des Interpreters kopieren. Beispielsweise könnten die Implementierungen einiger (registerbasierter) Bytecode-Befehle wie folgt aussehen:

   ; ebp points to virtual register 0 on the stack
   instr_ADD:
       <decode instruction>
       mov eax, [ebp + ecx * 4]  ; load first operand from stack
       add eax, [ebp + edx * 4]  ; add second operand from stack
       mov [ebp + ebx * 4], eax  ; write back result
       <dispatch next instruction>
   instr_SUB:
       ... ; similar
   

   Also, gegeben die Anweisungssequenz ADD R3, R1, R2, SUB R3, R3, R4 Ein einfaches JIT könnte die relevanten Teile der Interpreter-Implementierung in einen neuen Maschinencode-Chunk kopieren:

       mov ecx, 1
       mov edx, 2
       mov ebx, 3
       mov eax, [ebp + ecx * 4]  ; load first operand from stack
       add eax, [ebp + edx * 4]  ; add second operand from stack
       mov [ebp + ebx * 4], eax  ; write back result
       mov ecx, 3
       mov edx, 4
       mov ebx, 3
       mov eax, [ebp + ecx * 4]  ; load first operand from stack
       sub eax, [ebp + edx * 4]  ; add second operand from stack
       mov [ebp + ebx * 4], eax  ; write back result
   

   Dies kopiert einfach den entsprechenden Code, also müssen wir die verwendeten Register entsprechend initialisieren. Eine bessere Lösung wäre, dies direkt in Maschinenanweisungen zu übersetzen mov eax, [ebp + 4]aber jetzt müssen Sie die angeforderten Anweisungen bereits manuell codieren.

   Diese Technik beseitigt den Overhead der Interpretation, verbessert aber ansonsten die Effizienz nicht sehr. Wenn der Code nur ein- oder zweimal ausgeführt wird, lohnt es sich möglicherweise nicht, ihn zuerst in Maschinencode zu übersetzen (wozu zumindest Teile des I-Cache geleert werden müssen).

2. Während einige JITs die obige Technik anstelle eines Interpreters verwenden, verwenden sie dann einen komplizierteren Optimierungsmechanismus für häufig ausgeführten Code. Dies umfasst das Übersetzen des ausgeführten Bytecodes in eine Zwischendarstellung (IR), an der zusätzliche Optimierungen durchgeführt werden.

   Je nach Ausgangssprache und JIT-Typ kann dies sehr komplex sein (weshalb viele JITs diese Aufgabe an LLVM delegieren). Ein methodenbasiertes JIT muss sich mit dem Verbinden von Kontrollflussdiagrammen befassen, also verwenden sie das SSA-Formular und führen verschiedene Analysen darauf durch (z. B. Hotspot).

   Ein Ablaufverfolgungs-JIT (wie LuaJIT 2) kompiliert nur geradlinigen Code, was die Implementierung vieler Dinge erleichtert, aber Sie müssen sehr vorsichtig sein, wie Sie Ablaufverfolgungen auswählen und wie Sie mehrere Ablaufverfolgungen effizient miteinander verknüpfen. Gal und Franz beschreiben eine Methode in dieses Papier (PDF). Eine andere Methode finden Sie im LuaJIT-Quellcode. Beide JITs sind in C (oder vielleicht C++) geschrieben.

Ich schlage vor, Sie schauen sich das Projekt an http://code.google.com/p/asmjit/. Durch die Verwendung des bereitgestellten Frameworks können Sie viel Energie sparen. Wenn Sie alles von Hand schreiben möchten, lesen Sie einfach die Quelle und schreiben Sie es selbst um, ich denke, es ist nicht sehr schwer.