Einen JIT-Compiler in Assembler schreiben

Question

Ich habe eine virtuelle Maschine in C geschrieben, die für eine Nicht-JIT-VM eine ordentliche Leistung hat, aber ich möchte etwas Neues lernen und die Leistung verbessern. Meine derzeitige Implementierung verwendet einfach einen Schalter zur Übersetzung von VM-Bytecode in Anweisungen, die in eine Sprungtabelle kompiliert werden. Wie ich sagte, anständige Leistung für das, was es ist, aber ich habe eine Barriere, die nur mit einem JIT-Compiler überwunden werden kann getroffen.

Ich habe vor nicht allzu langer Zeit schon einmal eine ähnliche Frage zur Selbstmodifizierung von 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 zwar in x86-Assembler. (Ich verwende NASM als mein Assembler) Ich bin nicht ganz sicher, wie ich das anstellen soll. Ich kenne mich mit Assembler aus und habe mir einige Beispiele für selbstmodifizierenden Code angesehen, aber ich habe noch nicht herausgefunden, wie man Code generiert.

Mein Hauptproblem ist bisher das Kopieren von Anweisungen in einen ausführbaren Speicherbereich, avec meine Argumente. Ich weiß, dass ich eine bestimmte Zeile in NASM markieren 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 habe mich ü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 irgendwelche Ressourcen oder Beispiele, die die Community zur Verfügung stellen könnte, um mir den Einstieg in diese Aufgabe zu erleichtern? Ein einfaches Beispiel, das zeigt, wie zwei oder drei Anweisungen wie "add" und "mov" verwendet werden, um ausführbaren Code mit Argumenten dynamisch im Speicher zu erzeugen, würde Wunder bewirken.

Answer 1

Ich würde überhaupt nicht empfehlen, ein JIT in Assembler zu schreiben. Es gibt gute Argumente für das Schreiben der am häufigsten ausgeführten Bits der Dolmetscher in der Baugruppe. Ein Beispiel dafür, wie dies aussehen kann, finden Sie hier Kommentar von Mike Pall der Autor von LuaJIT.

Was die JIT betrifft, so gibt es viele verschiedene Stufen mit unterschiedlicher Komplexität:

1. Kompilieren Sie einen Basisblock (eine Folge von nicht verzweigten Anweisungen) durch einfaches Kopieren des Codes des Interpreters. Die Implementierungen einiger (registerbasierter) Bytecode-Anweisungen könnten zum Beispiel so 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

   Die Befehlsfolge lautet also 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

   Dabei wird einfach der entsprechende Code kopiert, so dass wir die verwendeten Register entsprechend initialisieren müssen. Eine bessere Lösung wäre, dies direkt in Maschinenbefehle zu übersetzen mov eax, [ebp + 4] aber jetzt müssen Sie die angeforderten Anweisungen bereits manuell kodieren.

   Diese Technik beseitigt die Gemeinkosten der Interpretation, verbessert aber ansonsten die Effizienz nicht wesentlich. Wenn der Code nur ein oder zwei Mal ausgeführt wird, lohnt es sich möglicherweise nicht, ihn zunächst in Maschinencode zu übersetzen (was zumindest ein Löschen von Teilen des I-Cache erfordert).

2. Einige JITs verwenden zwar die oben beschriebene Technik anstelle eines Interpreters, setzen dann aber einen komplizierteren Optimierungsmechanismus für häufig ausgeführten Code ein. Dabei wird der ausgeführte Bytecode in eine Zwischendarstellung (IR) übersetzt, an der zusätzliche Optimierungen vorgenommen werden.

   Abhängig von der Ausgangssprache und der Art des JITs kann dies sehr komplex sein (weshalb viele JITs diese Aufgabe an LLVM delegieren). Ein methodenbasiertes JIT muss sich mit dem Verbinden von Kontrollflussgraphen befassen, daher verwenden sie die SSA-Form und führen verschiedene Analysen dazu durch (z. B. Hotspot).

   Ein Tracing-JIT (wie LuaJIT 2) kompiliert nur geradlinigen Code, was die Implementierung vieler Dinge erleichtert, aber man muss sehr vorsichtig sein, wie man Traces auswählt und wie man mehrere Traces effizient miteinander verbindet. Gal und Franz beschreiben eine Methode in dieses Papier (PDF) . Für eine andere Methode siehe den LuaJIT-Quellcode. Beide JITs sind in C (oder vielleicht C++) geschrieben.

Answer 2

Ich schlage vor, Sie schauen sich das Projekt an http://code.google.com/p/asmjit/ . Durch die Verwendung des Rahmens, den es bietet, können Sie eine Menge Energie sparen. Wenn Sie alles von Hand schreiben wollen, lesen Sie einfach den Quelltext und schreiben Sie ihn selbst um, ich denke, das ist nicht sehr schwer.