Compiler Design - Codegenerierung

Die Codegenerierung kann als letzte Phase der Kompilierung betrachtet werden. Durch die Postleitzahlgenerierung kann der Optimierungsprozess auf den Code angewendet werden, dies kann jedoch als Teil der Codegenerierungsphase selbst angesehen werden. Der vom Compiler generierte Code ist ein Objektcode einer untergeordneten Programmiersprache, z. B. Assemblersprache. Wir haben gesehen, dass der in einer höheren Sprache geschriebene Quellcode in eine niedrigere Sprache umgewandelt wird, was zu einem niedrigeren Objektcode führt, der die folgenden Mindesteigenschaften haben sollte:

Es sollte die genaue Bedeutung des Quellcodes tragen.
Es sollte in Bezug auf CPU-Auslastung und Speicherverwaltung effizient sein.

Wir werden nun sehen, wie der Zwischencode in Zielobjektcode (in diesem Fall Assemblycode) umgewandelt wird.

Directed Acyclic Graph

Directed Acyclic Graph (DAG) ist ein Tool, das die Struktur von Basisblöcken darstellt, den Wertefluss zwischen den Basisblöcken erkennt und auch Optimierungen bietet. DAG bietet eine einfache Transformation für Basisblöcke. DAG kann hier verstanden werden:

Blattknoten repräsentieren Bezeichner, Namen oder Konstanten.
Innenknoten repräsentieren Operatoren.
Innenknoten repräsentieren auch die Ergebnisse von Ausdrücken oder die Bezeichner / Namen, in denen die Werte gespeichert oder zugewiesen werden sollen.

Example:

t₀ = a + b
t₁ = t₀ + c
d = t₀ + t₁

[t ₀ = a + b]	[t ₁ = t ₀ + c]	[d = t ₀ + t ₁ ]

Gucklochoptimierung

Diese Optimierungstechnik arbeitet lokal mit dem Quellcode, um ihn in einen optimierten Code umzuwandeln. Mit lokal meinen wir einen kleinen Teil des vorliegenden Codeblocks. Diese Methoden können sowohl auf Zwischencodes als auch auf Zielcodes angewendet werden. Eine Reihe von Aussagen wird analysiert und auf folgende mögliche Optimierung überprüft:

Redundante Anweisungseliminierung

Auf Quellcodeebene kann der Benutzer Folgendes tun:

int add_ten(int x)
   {
   int y, z;
   y = 10;
   z = x + y;
   return z;
   }

int add_ten(int x)
   {
   int y;
   y = 10;
   y = x + y;
   return y;
   }

int add_ten(int x)
   {
   int y = 10;
   return x + y;
   }

int add_ten(int x)
   {
   return x + 10;
   }

Auf Kompilierungsebene sucht der Compiler nach redundanten Anweisungen. Das mehrfache Laden und Speichern von Anweisungen kann dieselbe Bedeutung haben, selbst wenn einige von ihnen entfernt werden. Zum Beispiel:

MOV x, R0
MOV R0, R1

Wir können die erste Anweisung löschen und den Satz neu schreiben als:

MOV x, R1

Unerreichbarer Code

Nicht erreichbarer Code ist ein Teil des Programmcodes, auf den aufgrund von Programmierkonstrukten nie zugegriffen wird. Programmierer haben möglicherweise versehentlich einen Code geschrieben, der niemals erreicht werden kann.

Example:

void add_ten(int x)
{
   return x + 10;
   printf(“value of x is %d”, x);
}

In diesem Codesegment wird die printf Die Anweisung wird niemals ausgeführt, da die Programmsteuerung zurückkehrt, bevor sie ausgeführt werden kann printf kann entfernt werden.

Ablauf der Steuerungsoptimierung

Es gibt Fälle in einem Code, in denen die Programmsteuerung hin und her springt, ohne eine wesentliche Aufgabe auszuführen. Diese Sprünge können entfernt werden. Betrachten Sie den folgenden Codeabschnitt:

...		
MOV R1, R2
GOTO L1
...
L1 :   GOTO L2
L2 :   INC R1

In diesem Code kann die Bezeichnung L1 entfernt werden, wenn die Steuerung an L2 übergeben wird. Anstatt also zu L1 und dann zu L2 zu springen, kann die Steuerung L2 direkt erreichen, wie unten gezeigt:

...		
MOV R1, R2
GOTO L2
...
L2 :   INC R1

Vereinfachung des algebraischen Ausdrucks

Es gibt Fälle, in denen algebraische Ausdrücke einfach gemacht werden können. Zum Beispiel der Ausdrucka = a + 0 kann ersetzt werden durch a selbst und der Ausdruck a = a + 1 können einfach durch INC a ersetzt werden.

Kraftreduzierung

Es gibt Vorgänge, die mehr Zeit und Platz beanspruchen. Ihre "Stärke" kann verringert werden, indem sie durch andere Vorgänge ersetzt werden, die weniger Zeit und Platz verbrauchen, aber das gleiche Ergebnis erzielen.

Zum Beispiel, x * 2 kann ersetzt werden durch x << 1, was nur eine Linksverschiebung beinhaltet. Obwohl die Ausgabe von a * a und a ^{2 gleich} ist, ist die Implementierung einer ² viel effizienter.

Zugriff auf Maschinenanweisungen

Der Zielcomputer kann komplexere Anweisungen bereitstellen, mit denen bestimmte Vorgänge sehr effizient ausgeführt werden können. Wenn der Zielcode diese Anweisungen direkt aufnehmen kann, verbessert dies nicht nur die Qualität des Codes, sondern führt auch zu effizienteren Ergebnissen.

Code Generator

Von einem Codegenerator wird erwartet, dass er die Laufzeitumgebung des Zielcomputers und seinen Befehlssatz versteht. Der Codegenerator sollte die folgenden Aspekte berücksichtigen, um den Code zu generieren:

Target language: Der Codegenerator muss die Art der Zielsprache kennen, für die der Code transformiert werden soll. Diese Sprache kann einige maschinenspezifische Anweisungen erleichtern, damit der Compiler den Code bequemer generieren kann. Der Zielcomputer kann entweder über eine CISC- oder eine RISC-Prozessorarchitektur verfügen.
IR Type: Zwischendarstellung hat verschiedene Formen. Es kann sich um eine AST-Struktur (Abstract Syntax Tree), eine umgekehrte polnische Notation oder einen Code mit drei Adressen handeln.
Selection of instruction: Der Codegenerator nimmt die Zwischendarstellung als Eingabe und konvertiert sie (ordnet sie zu) in den Befehlssatz des Zielcomputers. Eine Darstellung kann viele Möglichkeiten (Anweisungen) haben, um sie zu konvertieren. Daher liegt es in der Verantwortung des Codegenerators, die entsprechenden Anweisungen mit Bedacht auszuwählen.
Register allocation: Ein Programm hat eine Reihe von Werten, die während der Ausführung beibehalten werden müssen. Die Architektur des Zielcomputers ermöglicht möglicherweise nicht, dass alle Werte im CPU-Speicher oder in den Registern gespeichert werden. Der Codegenerator entscheidet, welche Werte in den Registern gespeichert werden sollen. Außerdem entscheidet es, welche Register verwendet werden sollen, um diese Werte beizubehalten.
Ordering of instructions: Zuletzt entscheidet der Codegenerator über die Reihenfolge, in der der Befehl ausgeführt wird. Es werden Zeitpläne für Anweisungen erstellt, um diese auszuführen.

Deskriptoren

Der Codegenerator muss beim Generieren des Codes sowohl die Register (auf Verfügbarkeit) als auch die Adressen (Position der Werte) verfolgen. Für beide werden die folgenden zwei Deskriptoren verwendet:

Register descriptor: Der Registerdeskriptor wird verwendet, um den Codegenerator über die Verfügbarkeit von Registern zu informieren. Der Registerdeskriptor verfolgt die in jedem Register gespeicherten Werte. Wenn während der Codegenerierung ein neues Register benötigt wird, wird dieser Deskriptor zur Verfügbarkeit des Registers herangezogen.
Address descriptor: Die Werte der im Programm verwendeten Namen (Bezeichner) können während der Ausführung an verschiedenen Orten gespeichert werden. Adressdeskriptoren werden verwendet, um Speicherorte zu verfolgen, an denen die Werte von Bezeichnern gespeichert sind. Diese Speicherorte können CPU-Register, Heaps, Stapel, Speicher oder eine Kombination der genannten Speicherorte umfassen.

Der Codegenerator hält beide Deskriptoren in Echtzeit auf dem neuesten Stand. Für eine Ladeanweisung LD R1, x, den Codegenerator:

aktualisiert den Registerdeskriptor R1 mit dem Wert x und
aktualisiert den Adressdeskriptor (x), um anzuzeigen, dass sich eine Instanz von x in R1 befindet.

Codegenerierung

Grundblöcke bestehen aus einer Folge von Anweisungen mit drei Adressen. Der Codegenerator verwendet diese Befehlsfolge als Eingabe.

Note: Wenn der Wert eines Namens an mehr als einer Stelle gefunden wird (Register, Cache oder Speicher), wird der Wert des Registers dem Cache und dem Hauptspeicher vorgezogen. Ebenso wird der Wert des Caches dem Hauptspeicher vorgezogen. Der Hauptspeicher wird kaum bevorzugt.

getReg: Der Codegenerator verwendet die Funktion getReg , um den Status der verfügbaren Register und die Position der Namenswerte zu bestimmen. getReg funktioniert wie folgt:

Befindet sich die Variable Y bereits im Register R, wird dieses Register verwendet.
Andernfalls wird dieses Register verwendet, wenn ein Register R verfügbar ist.
Andernfalls, wenn beide oben genannten Optionen nicht möglich sind, wird ein Register ausgewählt, das eine minimale Anzahl von Lade- und Speicheranweisungen erfordert.

Für eine Anweisung x = y OP z kann der Codegenerator die folgenden Aktionen ausführen. Nehmen wir an, dass L der Ort (vorzugsweise Register) ist, an dem die Ausgabe von y OP z gespeichert werden soll:

Rufen Sie die Funktion getReg auf, um den Standort von L zu bestimmen.
Bestimmen Sie den aktuellen Speicherort (Register oder Speicher) von y durch Rücksprache mit dem Adressdeskriptor von y. Wenny ist derzeit nicht im Register LGenerieren Sie dann die folgende Anweisung, um den Wert von zu kopieren y zu L::

MOV y ', L.

wo y’ repräsentiert den kopierten Wert von y.
Bestimmen Sie den aktuellen Standort von z unter Verwendung der gleichen Methode wie in Schritt 2 für y und generieren Sie die folgende Anweisung:

OP z ', L.

wo z’ repräsentiert den kopierten Wert von z.
Jetzt enthält L den Wert von y OP z, dem zugewiesen werden soll x. Wenn L also ein Register ist, aktualisieren Sie seinen Deskriptor, um anzuzeigen, dass es den Wert von enthältx. Aktualisieren Sie den Deskriptor vonx um anzuzeigen, dass es am Ort gespeichert ist L.
Wenn y und z keine weitere Verwendung haben, können sie an das System zurückgegeben werden.

Andere Codekonstrukte wie Schleifen und bedingte Anweisungen werden auf allgemeine Assemblierungsweise in Assemblersprache umgewandelt.