Übersetzerbau Entwurf - Codegenerierung

Advertisements

Previous Page
Next Page  

Code-Erzeugung kann berücksichtigt als die letzte Phase der Zusammenstellung . Durch Postcodegenerierung können Optimierungsprozess auf dem Code angewandt werden, aber das kann als ein Teil der Codegenerierung Phase selbst zu sehen. Das vom Compiler erzeugte Code ist ein Objekt-Code von einigen untergeordneten Programmiersprache, zum Beispiel, Assembler. Wir haben gesehen, dass der Quellcode in eine übergeordnete Sprache geschrieben wird in eine untergeordnete Sprache, die in einem untergeordneten Objekt-Code führt, die mindestens folgende Eigenschaften haben sollte umgewandelt:

  • Es sollte die genaue Bedeutung des Quellcodes zu durchführen.
  • Es sollte effizient sein, in Bezug auf die CPU-Auslastung und Speicherverwaltung.

Wir werden nun sehen, wie der Zwischencode in die Zielobjektcode umgewandelt (Assembler-Code, in diesem Fall). .

gerichteter azyklischer Graph

gerichteten azyklischen Graphen (DAG) ist ein Werkzeug, das die Struktur der Basisblöcke zeigt, hilft, den Strom von Werten unter den Grundblöcken fließen zu sehen, und bietet Optimierung zu. DAG bietet einfachen Transformation auf Basisblöcke. DAG kann hier verstanden werden:

  • Blatt-Knoten stellen Kennungen, Namen oder Konstanten.

  • Interior Knoten stellen Betreiber.

  • Innenknoten auch vertreten die Ergebnisse der Ausdrücke oder die Bezeichner / Namen, wo die Werte, die gespeichert oder zugeordnet sind .

Beispiel:

t0 = a + b
t1 = t0 + c
d = t0 + t1
Directed Acyclic Graph

[t0 = a + b]

 Directed Acyclic Graph

[t1 = t0 + c]

 Directed Acyclic Graph

[d = t0 + t1]

Peephole Optimierung

Diese Optimierungstechnik arbeitet lokal auf dem Source-Code, um ihn in einer optimierten Code umzuwandeln. Durch die lokale, dann meinen wir einen kleinen Teil des Codeblocks auf der Hand. Diese Verfahren können auf Zwischencodes sowie von Zielcodes angewendet werden. Ein Bündel von Erklärungen analysiert und für das folgende mögliche Optimierung verifiziert:

Redundante Anweisung Beseitigung

Bei Quellcode-Ebene, die folgenden können vom Benutzer durchgeführt werden:

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;
   }
Bei Zusammenstellung Ebene, der Compiler Suchanfragen nach Anweisungen überflüssig in der Natur. Mehrere Laden und Speichern von Befehlen durchzuführen die gleiche Bedeutung, auch wenn einige von ihnen entfernt werden. Zum Beispiel:
  • MOV x, R0
  • MOV R0, R1

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

MOV x, R1

unerreichbar Code

unerreichbar Code ist ein Teil des Programmcodes, die nie wegen Programmierkonstrukte zugegriffen. Programmierer können versehentlich geschrieben haben, ein Stück Code, die nie erreicht werden kann.

Beispiel

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

In diesem Code-Segment, die printf Aussage wird ausgeführt werden nie wie die Programmsteuerung kehrt zurück, bevor sie ausgeführt werden, damit printf kann entfernt werden.

Fluss von Steuer Optimierung

Es gibt Fälle, in einem Code, wo die Programmsteuerung hin und her springt, Ausführen ohne eine bedeutende Aufgabe. Diese Sprünge können entfernt werden. Betrachten Sie das folgende Stück Code: 

...		
MOV R1, R2
GOTO L1
...
L1 :   GOTO L2
L2 :   INC R1
In diesem Code können Label L1 entfernt werden, da sie die Kontrolle an L2 durchläuft. Anstatt also das Springen zu L1 und dann zu L2, die Steuerung direkterreichen L2, wie unten dargestellt:
...		
MOV R1, R2
GOTO L2
...
L2 :   INC R1

algebraischen Ausdruck Vereinfachung

Es gibt Gelegenheiten, wo algebraischen Ausdrücken kann einfach gemacht werden. Beispielsweise kann der Ausdruck a = a + 0 kann ersetzt werden durch a selbst und der Ausdruck a = a + 1 kann einfach durch eine INC ersetzt werden.

Stärke Reduzierung

Es gibt Operationen, die mehr Zeit und Raum zu konsumieren. Ihre "Stärke" könnenreduziert , indem ersetzen sie mit anderen Operationen, die weniger Zeit und Raum zu konsumieren, aber produzieren das gleiche Ergebnis.

Zum Beispiel: x * 2 kann ersetzt werden durch x << 1 , die nur eine Linksverschiebung beinhaltet. Obwohl der Ausgang eines * a und a 2 für gleiche, a 2 ist viel effizienter zu implementieren.

Zugriff auf Maschinenbefehle

Der Zielcomputer kann komplexere Anweisungen bereitzustellen, die die Fähigkeit, bestimmte Operationen sehr effizient durchführen können müssen. Wenn das Ziel-Code kann diese Anweisungen direkt aufnehmen, die nicht nur verbessern die Qualität des Codes, aber auch ergeben effizientere Ergebnisse.

Code Generator

A-Code-Generator wird erwartet, um ein Verständnis der Laufzeitumgebung der Zielmaschine und deren Befehlssatz haben. Der Codegenerator sollte folgende Dinge berücksichtigen, um den Code zu generieren:

  • Zielsprache : Der Code-Generator hat, von der Art der Zielsprache, für die der Code ist, die transformiert werden können. Diese Sprache kann einige maschinenspezifische Instruktionen zu erleichtern, damit der Compiler den Code generieren in einer bequemen Weise. Der Zielcomputer kann entweder CISC oder RISC-Prozessor-Architektur haben.

  • IR Typ : Zwischendarstellung hat verschiedene Formen. Es kann in Abstract Syntax-Baum (AST) Struktur, umkehren Polish Notation, oder 3-Adresscode.

  • Auswahl der Anweisung : Der Code-Generator nimmt Zwischendarstellung als Eingabe und konvertiert (Karten) sie in Befehlssatz der Zielmaschine. Eine Darstellung kann vielerlei Hinsicht (Anleitung), um sie zu konvertieren, so wird es in der Verantwortung des Code-Generator, um die entsprechenden Anweisungen mit Bedacht zu wählen.

  • Registerzuordnung : Ein Programm hat eine Reihe von Werten, die bei der Ausführung eingehalten werden. der Ziel maschine Architektur dürfen nicht zulassen,alle Werte gehalten werden in den CPU-Speicher oder Register. Codegenerator entscheidet was Werte zu halten in den Registern. Außerdem entscheidet die Register zu verwenden, um diese Werte zu halten.

  • Bestellung der Anweisungen : Endlich entscheidet der Codegenerator die Reihenfolge, in der die Anweisung ausgeführt wird. Es schafft Pläne für Anweisungen, um sie auszuführen.

Deskriptoren

Der Code-Generator muss sowohl die Register (nach Verfügbarkeit) und Adressen (Ort der Werte) zu verfolgen, während der Codegenerierung. Für beide, werden die folgenden zwei Deskriptoren verwendet:

  • Registrieren Deskriptor: Registrieren Deskriptor wird verwendet, um den Code-Generator über die Verfügbarkeit der Register zu informieren. Register Deskriptor verfolgt in jedem Register gespeichert sind. Immer wenn ein neues Register bei der Codegenerierung erforderlich ist, wird diese Bezeichnung für das Register Verfügbarkeit konsultiert.

  • Address Descriptor : Werte der im Programm verwendeten Namen (Bezeichner) kann an verschiedenen Stellen, während in der Ausführung gespeichert werden. Adresse Deskriptoren werden verwendet, um zu verfolgen Speicherstellen zu halten, wo die Werte der Kennungen gespeichert sind. Diese Standorte können CPU-Register, Haufen, Stapel, Speicher oder eine Kombination der genannten Standorte sind.

Codegenerator hält sowohl den Deskriptor in Echtzeit aktualisiert. Für eine Ladeanweisung, LD R1, x, der Code-Generator:

  • updates the Register Descriptor R1 that has value of x and
  • updates the Address Descriptor (x) to show that one instance of x is in R1.

Codegenerierung

Basis-Blöcke bestehen aus einer Folge von drei-Adresse Anweisungen. Code-Generator nimmt diese Folge von Anweisungen als Eingabe.

Hinweis: : Wenn der Wert eines Namens an mehr als einer Stelle (Register, Cache oder Speicher) gefunden wird, wird der Wert des Registers über den Cache und Hauptspeicher vorzuziehen. Ebenso Wert Cache wird über den Hauptspeicher vorzuziehen. Der Hauptspeicher wird kaum einen Vorzug gegeben.

GetReg : Code-Generator verwendet GetReg Funktion, um den Status der verfügbaren Register und die Lage der Name Werte zu bestimmen. GetReg funktioniert wie folgt:

  • Wenn Größe Y ist bereits in Register R, verwendet es dieses Register.

  • Else, wenn einige Register R verfügbar ist, nutzt es dieses Register

  • Else, wenn die beiden oben genannten Optionen nicht möglich sind, wählt es ein Register mit minimalen Anzahl von Lade- und Speicherbefehle benötigt.

Für eine Anweisung x = y OP z, der Code-Generator kann die folgenden Aktionen ausführen. Angenommen, L ist die Lage (vorzugsweise registrieren), wo der Ausgang y OP z gespeichert werden soll:

  • Anruf funktion GetReg, um die Position der L entscheiden.

  • Bestimmen Sie die aktuelle Position (Register oder Speicher) von y nach Anhörung des Address Descriptor von y . Falls y ist derzeit nicht im Register L , dann erzeugen die folgenden Anweisungen, um den Wert von y L kopieren:

    MOV y’, L

    wo y ' stellt den kopierten Wert von y .

  • Bestimmen Sie die aktuelle Position von z mit der gleichen Methode in Schritt 2 für y verwendet und die folgende Anweisung:

    OP z’, L

    wo z' stellt den kopierten Wert von z .

  • Jetzt L den Wert von y OP z enthält, dass soll sich auf x zugewiesen werden. Also, wenn L ist ein Register, aktualisieren ihre Descriptor um anzuzeigen, dass sie den Wert der x enthält. Aktualisieren Sie die Deskriptor x, um anzuzeigen, dass es an der Stelle gespeichert sind L.

  • Wenn y und z keine weitere Verwendung, können sie zurück zu dem System gegeben werden.

Weitere Code-Konstrukte wie Schleifen und bedingte Anweisungen in Assemblersprache in Versammlung Weise transformiert.

Advertisements