ProjectF (Maschinencode Erzeugung) - PascalCase/swp-uebersetzerbau-ss12 GitHub Wiki

###Die Aufgabe

Unsere Aufgabe besteht darin, einen Code-Generator zu implementieren, welcher vorhandenen LLVM-Code einliesst und daraus entweder equivalenten ausführbaren Byte-Code, GNU-Assembler-Code oder Intel-Assembler-Code erzeugt.

###Allgemeines

Als Implementierungssprache haben wir uns für Java entschieden, da diese Sprache im gesamten Übersetzerbau Projekt genutzt wird und weil jeder der Teammitglieder dieses Projekts Erfahrungen in Java hat. Die Ausgabe unseres Code-Generators soll sich ersteinmal nur auf GNU-Assembler-Code beschränken. Dieser Assembler-Code soll dann mit den dem Assembler-Compiler "as" und dem Linker "ld" in ausführbaren Byte-Code Übersetzt werden. Falls nach Erreichen dieses Ziels noch Zeit übrig ist, werden noch weitere Ausgabeformate hinzugefügt.

###Ziele

Folgende Ziele haben wir uns für das Projekt gesetzt:

Primärziele:

  • Einlesen einer LLVM-Code Datei
  • Erstellen einer effektiven Variablen- und Registerverwaltung
  • Übersetzen des LLVM-Code in GNU-Assembler-Code mittels Assembler Templates
  • Bedienung des Code Generators soll angelehnt sein an die Bedienung des C Compilers gcc. (Bsp.: CodeGenerator -o [Ausgabedatei] [Eingabedatei])

Sekundärziele:

  • Übersetzen in Intel-Assembler
  • Übersetzen in direkt ausführbaren Byte-Code
  • Optimierung des erzeugten Assembler-Codes

###Grober Aufbau des Code Generators Grober Aufbau des Code-Generators

###Der Lexer

Der Lexer ist ein Objekt, welcher den LLVM-Code Zeilenweise aus einer angegebenen Datei liesst. Die Relevanten Informationen aus einer LLVM-Codezeile, die zur Übersetzung benötigt werden, werden dann in ein Tokenkonstrukt gepackt und zur weiteren Verarbeitung bereitgestellt.

Benutzung

Der Lexer stellt 3 öffentliche Methoden zur Verfügung:

open([Dateiname]);
getNextToken();
close();

Mithilfe der Methode open(), öffnet der Lexer die angegebene Datei [Dateiname] mit Leserechten. Nun ist es möglich mit getNextToken() eine Zeile aus der Datei lesen zu lassen und die relevanten Informationen in Form eines Tokenobjekts zu erhalten. Dabei liesst getNextToken() immer nur eine Zeile der Datei. Um die Informationen der nächsten Zeile zu bekommen, ist ein weiterer Aufruf von getNextToken() notwendig. Ist der Lexer am Ende einer Datei angelangt, wird ein Token des Types EOF zurückgegeben. Um den Lexer wieder von der Datei zu trennen, muss die Methode close() aufgerufen werden.

Folgendes Beispiel erläutert dieses Vorgehen:

Lexer lex = new Lexer();
lex.open("llvmcode.llvm");			
Token tok  = new Token();

while((tok = lex.getNextToken()).getType() != TokenType.EOF) {
   System.out.println(tok.getType().toString());
}
lex.close();

###Vorarbeit Übersetzung

Funktionsefinition:

  • label Funktionsname
  • enter $Größe $0 (Stackpointer sichern, Speicher auf dem Stack für neue Variablen reservieren)
  • So oft Werte auf Stack wie Anzahl der Parameter (Wenn die Funktion aufgerufen wird sind die Parameter doch schon auf dem Stack?)
  • mov Wert, index %rbp (wird von enter gemacht)

Beispiel:

  • LLVM:

define i32 @addition(i32 %summand1, i32 %summand2) {

  • AT&T:
.type addition, @function
addition:
    enter $0 $0

Funktionsaufruf:

Beispiel:

  • LLVM

%15 = call i32 @addition(i32 %12, i32 %14)

  • AT&T:
pushl <Adresse von %14>(%ebp)
pushl <Adresse von %12>(%ebp)
call addition
addl <Größe aller Parameter>, %esp

return:

  • Rückgabewert mov index %rbp,%eax

Funktionsende:

  • leave
  • ret

Typdefinition:

  • nur Eintrag in Vartabelle

allocieren:

  • In Vartabelle gucken wegen Anzahl bei Records etc
  • solange Wert auf Heap wie Anz

Zuweisung:

  • Wert aus Vartabelle, wo liegt Zielvar (Registerverwaltung) %rbp zuweisen

laden von Werten aus dem Speicher:

  • movl index(%ebp), register (Vartabelle) oder pushl -8(%ebp)
  • BEI FUNKTIONEN LADEN AUF DEN STACK MIT PUSH. LLVM trotzdem LOAD

speichern von werten im speicher

  • movl %register, index(%ebp) ODER movl $4, %register
  • SIEHE laden ANMERKUNG

addition:

  • addl %register1, %register2 (Ergebnis steht in register2)

subtraktion:

  • subl %register1, %register2 (ergebnis in register2)

multiplikation:

  • imull %register1, %register2 (ergebnis in register2)

division:

  • idivl %register1, %register2 (ergebnis in register2)

and und or analog

Bei Multiplikationen/Divisionen mit/durch 2, 4, 8 etc. sollte aus Gründen der Effizienz statt (i)mul/(i)div shl bzw. shr verwendet werden (s. u.).

  • Optimierung später

TODO

  • inline Strings
  • Scructs/Arrays
  • Konstanten
  • Evaluierung!!!!!!!!!!!!!!!