Optimierung - PascalCase/swp-uebersetzerbau-ss12 GitHub Wiki

Allgemein

Wir sind die Gruppe Optimierung. :)

Welche Datenstrukturen muessen waehrend der Programmausfuehrung aktuell gehalten werden:

  • Hashmaps fuer Register mit Definition und Use Informationen
  • Array der Blocks in LLVM_Function
  • verkettete Struktur zwischen Befehlen eines Blocks

Wie muss die Eingabedatei aussehen:

  • muss eine LLVM-Textdatei sein, die mit llvm-as fehlerfrei in LLVM-Bytecode uebersetzt werden kann
  • zugelassen sind folgende Befehle:
  • Labels: entweder eine Zeile am Anfang jedes Blocks mit Labelinformationen (als Kommentar oder ohne) oder kein Block enthaelt solch eine Zeile und die Label werden im Programm generiert

Programmstruktur

OptimierungUML OptimierungUML

Ablauf der Optimierung

  1. parsen des Codes in die einzelnen Funktionen
  2. Erstellung des Flussgraphen einer Funktion
  3. erstellen der Registermap für die Register in der Funktion
  4. durchführen der Optimierungen in dieser Reihenfolge:
  • Constant Folding
  • Reaching analyse
  • Tote Register und Blöcke entfernen
  • doppelte Befehle entfernen
  • Lebendigkeitanalyse mit store und load
  • Entfernung von Blöcken, welche nur unbedingten Sprüngen enthalten
  1. Ausgabe der Optimierung

Befehle, die implementiert sind

  • arithmetische Befehle: add sub mul div
  • float arithmetische Befehle: fadd fsub fmul fdiv
  • logische Operationen: and or xor
  • shift Operationen: shl (shifted to left) lshr (logical shift right) ashr (arithmetic shift right)
  • Speicher Befehle: alloca load store
  • Vergleich Operationen: eq ne ugt uge ult ule sgt sge slt sle
  • Verzweigung: br
  • Rückgabe Befehl: ret
  • Funktionsaufruf: call
  • Pointer Befehle: getelementptr

Implementierte Optimierungen

Constant Folding

Reaching Analyse

Tote Register und Blöcke entfernen

Am Anfang werden die Definition von toten Register aus dem Programm entfernt. Da es Operanden in den gelöschten Befehlen geben kann, welche nun keine Verwendung mehr haben, können diese ebenfalls gelöscht werden. Deswegen werden alle gelöschten Befehle im Register durchgegangen und die Operanden untersucht ob diese weiterhin verwendet werden. Werden diese nicht weiter benutzt, dann werden diese auch entfernt. Beim entfernen der toten Blöcke, werde die Blöcke entfernt, welche im Flussgraph nicht erreichbar sind. Nach dem entfernen eines Blöckes wird überprüft ob deren Folgeblock noch erreichbar ist.

doppelte Befehle entfernen

Die Common Expression wird für jeden Block durchgeführt, dabei wird überprüft ob diese doppelte Befehle enthalten. Dabei werden nur die Befehle einer vorher festlegten Liste beachtet (Derzeit: ADD, SUB, MUL, DIV und LOAD). Sollten doppelte Befehle gefunden werden, wird das aktuelle mit dem bestehenden Kommando ersetzt. Am Ende wird für den Block noch Constant Propagation durchgeführt.

Lebendigkeitsanalyse mit store und load

Entfernung von Blöcken, welche nur unbedingten Sprüngen enthalten

Zuerst wird geprüft, ob ein Block nur unbedingte Sprünge aufweist. Wenn dies ermittelt ist, wird der Block entfernt und alle Vorgängerblöcke untersucht ob diese auf den gelöschtes Block verweisen. Dafür wird der Verweis auf den aktuellen Block mit dem des Zielblocks getauscht und das Register angepasst. Danach wird noch der Flussgraph angepasst, damit dieser weiterhin verwendet werden kann. Am Ende werden die gelöschten Blöcke entfernt.