Ich schreibe einen Compiler für eine Teilmenge von Pascal. Der Compiler erzeugt Maschinenbefehle für eine erfundene Maschine. Ich möchte einen Guckloch-Optimierer für diese Maschinensprache schreiben, aber ich habe Probleme, einige der komplizierteren Muster zu ersetzen.

Spezifikation des Gucklochoptimierers

Ich habe verschiedene Ansätze zum Schreiben eines Gucklochoptimierers untersucht und mich für einen Back-End-Ansatz entschieden:

Der Encoder ruft eine anemit() Funktion jedes Mal, wenn eine Maschinenanweisung generiert werden soll.emit(Instruction currentInstr) Überprüft eine Tabelle mit Gucklochoptimierungen:Wenn der aktuelle Befehl mit dem Ende eines Musters übereinstimmt:Überprüfen Sie die zuvor ausgegebenen Anweisungen auf ÜbereinstimmungWenn alle Anweisungen mit dem Muster übereinstimmen, wenden Sie die Optimierung an und ändern Sie das Ende des CodespeichersWenn keine Optimierung gefunden wurde, geben Sie die Anweisung wie gewohnt ausAktueller Designansatz

Die Methode ist einfach genug, es ist die Implementierung, mit der ich Probleme habe. In meinem Compiler sind Maschinenanweisungen in einem gespeichertInstruction Klasse. Ich schrieb einInstructionMatch Klasse speichert reguläre Ausdrücke, die für jede Komponente eines Maschinenbefehls bestimmt sind. Es istequals(Instruction instr) Methode gibt zurücktrue wenn die Muster mit einer Maschinenanweisung übereinstimmeninstr.

Ich kann es jedoch nicht ganz schaffensich bewerben Die Regeln, die ich habe. Zunächst einmal habe ich das Gefühl, dass ich bei meinem derzeitigen Ansatz mit einem Durcheinander von unnötigen Objekten enden werde. Angesichts der Tatsache, dass eine vollständige Liste der Gucklochoptimierungsnummern ungefähr 400 Muster enthalten kann, wird dies schnell außer Kontrolle geraten. Außerdem kann ich mit diesem Ansatz keine schwierigeren Substitutionen erreichen (siehe "Meine Frage").

Alternative Ansätze

Ein Blatt, das ich gelesen habe, faltet vorherige Anweisungen zu einer langen Zeichenfolge zusammen, verwendet reguläre Ausdrücke, um sie abzugleichen und zu ersetzen, und konvertiert die Zeichenfolge zurück in Maschinenanweisungen. Das schien mir eine schlechte Annäherung zu sein, bitte korrigiere mich, wenn ich falsch liege.

Beispielmuster, Mustersyntax

<code>x: JUMP x+1; x+1: JUMP y  -->  x: JUMP y
LOADL x; LOADL y; add     -->  LOADL x+y
LOADA d[r]; STOREI (n)    -->  STORE (n) d[r]
</code>

Beachten Sie, dass jedes dieser Beispielmuster nur eine für den Menschen lesbare Darstellung der folgenden Maschinenbefehlsvorlage ist:

<code>op_code register n d
</code>

(n gibt normalerweise die Anzahl der Wörter an und d eine Adressverschiebung). Die Syntaxx: <instr> zeigt an, dass der Befehl unter der Adresse gespeichert istx im Codespeicher.

Also die AnweisungLOADL 17 entspricht der vollständigen Maschinenanweisung5 0 0 17 wenn derLOADL Opcode ist 5 (n undr sind in dieser Anleitung nicht verwendet)

Meine Frage

Vor diesem Hintergrund lautet meine Frage also: Wie kann ich Muster effektiv abgleichen und ersetzen, wenn ich Teile vorheriger Anweisungen als Variablen in meine Ersetzung einbeziehen muss? Zum Beispiel kann ich einfach alle Instanzen von ersetzenLOADL 1; add mit der Inkrementiermaschinen-Anweisung - Ich benötige keinen Teil der vorherigen Anweisungen, um dies zu tun. Ich bin jedoch nicht in der Lage, die Werte 'x' und 'y' meines zweiten Beispiels im Substitutionsmuster effektiv zu verwenden.

bearbeiten: Ich sollte erwähnen, dass jedes Feld einesInstruction class ist nur eine ganze Zahl (wie es bei Maschinenbefehlen üblich ist). Jede Verwendung von 'x' oder 'y' in der Mustertabelle ist eine Variable, die für einen beliebigen ganzzahligen Wert steht.