| |
| |
Compilerbau
Software
Neu! Verzeichnis Software/ enthält die neuesten Versionen von muHwi, risc386, und runtime.c, sowie Beispielprogramme.
- Zur Einführung: das Tool dataGen erleichtert die schematisch Erzeugung von Klassen, die abstrakte Syntaxbäume u.ä. representieren
- Lexikalische Analyse und Parsing von MiniJava Programmen.
Zur lexikalischen Analyse verwenden wir das Tool jflex. Mit diesem Aufruf wird aus dem Lexer file ein Java file erstellt: jflex MJLex.x (genauer /soft/bin/jflex).
Zum Parsing verwenden wir den Parser Generator java-cup der in /soft/IFI/lang/java-cup/java-cup-v11a.jar installiert ist (oder als java-CUP .jar file heruntergeladen werden kann).
Mehrere MiniJava Beispielsprogramme koennen heruntergeladen werden.
(Siehe auch Buch Homepage.)
Für die Ausführung des lexers, ist der CLASSPATH wie folgt zu ändern: export CLASSPATH=$CLASSPATH:/soft/IFI/lang/java-cup/java-cup-v11a.jar
Material zum Download:
- Zwischensprache:
Der Code für die Kanonisierung des Zwischencodes, wie in PK 7
vorgestellt, ist hier verfügbar, zusammen
mit den Hilfspaketen List.java und Utils.java.
Zum Einbinden in den eigenen Code, sollte für jeden Methodenrumpf
this.body folgendes Codestück ausgeführt werden:
LinkedList blks = IntmTrafo.intmTrafo(this.body);
this.canon_body = blks;
Der muHwI Interpreter:
Um das Testen des MiniJava Compilers zu vereinfachen, ist
hier ein Interpreter
für die Zwischensprache verfügbar.
Die aktuelle Version ist 1.10.
muHwI wird "mux-wi'" ausgesprochen
(Details zur Aussprache von Klingonischen Wörtern).
Struktur des Eingabefiles:
Das Eingabefile besteht aus einem Deklarationsblock und einer
Folge von Funktionsdefinitionen,
die den Rümpfen der Methoden in MiniJava entsprechen.
Im Deklarationsblock werden die Namen von Framepointer usw. sowie
Stack- und Heapgrösse definiert, zB:
SET NAME fp = t33 // Framepointer
SET NAME sp = t30 // Stackpointer
SET NAME rp = t3 // Return-value register
SET VALUE sz = 12000 // 12kB of stack
SET VALUE hz = 800000 // 800kB of heap
Im Kopf der Funktionsdefinition muss der Name (mit beginnendem
"L"!) und die Parameterliste angegeben sein.
Folgende Deklarationen für die Parameter sind möglich:
- REG ein (abstraktes) Register,
- LOC eine (relative) Adresses auf dem Frame, und
- MEM eine (absolute) Adresse im Heap.
Das erste Argument der Parameterliste, muss ein Register mit dem THIS Objekt sein.
Optional kann danach die Frame-grösse mit FS angegeben werden.
Als Beispiel, hier die Struktur der Factorial Funktion im Zwischencode:
FCT LFactorial$main(REG t1, REG t77) FS 4 =
{
...
}
Links zu weiteren Beispielen finden sich am Ende der Web page.
Zum Ausdrucken des Codes kann der pretty-printing Visitor in PPIntm verwendet werden (neue Version im package IntmTrafo.
Diese Funktion muss für jeden Methodenrumpf in der Symboltabelle
aufgerufen werden. Der Kopf der Funktionsdefinition muss separat aus
der weiteren Information in der Symboltabelle erzeugt werden.
Wichtige Konventionen:
- Registernamen müssen mit t beginnen, zB: t33
- Funktionsnamen und labels müssen mit L beginnen, zB: Lfact
- Das Resultatregister muss trp sein (oder mit -r name
setzen), der Framepointer muss
tfp sein (oder mit -f name setzen), der Stackpointer muss
tsp sein (oder mit -s name setzen).
Die Namen können auch im Deklarationsteil des Files bestimmt werden (siehe obiges Besipiel). .
- Als "calling convention" werden vor dem Aufruf einer Funktion sämtliche Register abgespeichert.
D.h. es ist (noch) nicht nötig die Funktion procEntryExit1
aus der Vorlesung zu implementieren. In der Endversion der
Zwischensprachengenerierung müssen sämtliche callee-save
Register durch den erzeugten Code gesichert werden.
Dann ist eine einfachere "calling convention" im Interpreter zu
verwenden.
Weitere nützliche Informationen:
- Laufzeitwerte werden im Interpreter als A int für
Adressen und I int für integers repräsentiert.
- Der Stack startet üblicherweise bei Adresse 8000 und wächst nach unten (zu
kleineren Adressen), der Heap startet bei Adresse 8004 und wächst
nach oben.
- Mit flag -C werden die aktuellen Werte für jeden
Methodenaufruf ausgedruckt.
- Mit flag -? erhält man weitere Hinweise zur Verwendung
des Interpreters.
Der Interpreter (Name: muHwI) wird mit dem Filenamen des Zwischencodes und
den Parametern der L...$main Funktion aufgerufen:
muHwI Fact3.intm 5
Während der Ausführung druckt der Interpreter Meldungen über die Ausführung bestimmter Kommandos aus (z.B. Funktionsaufrufe mit Parameterwerten). Am Ende wird das Resultat ausgegeben.
Name für spezielle externe Funktionen, die der Interpreter kennt:
- L_halloc_obj: Allokierung eines heap objects; Parameter: Grösse in Bytes
- L_init_obj: Initialisierung eines heap objects; Parameter: Pointer zum Objekt, Grösse in Bytes
- L_halloc_arr: Allokierung eines Arrays; Parameter: Länge (Anzahl der Einträge)
- L_init_arr: Initialisierung eines Arrays; Parameter: Pointer zum Objekt, Länge (Anzahl der Einträge) (Indizierung startet mit 0; Grösse ist im Index -1 abgelegt)
- L_print: Ausdrucken eines Wertes; Parameter: Wert (Integer oder Adresse)
- L_raise: Laufzeitfehler; Parameter: Error-Code (Integer)
Hier die wichtigsten Optionen:
-? --help show usage information
-v --verbose be verbose
-a --ast show AST
-T Traces --defTrace=Traces default tracing flags (NOT IMPLEMENTED)
-C --callTrace trace function calls
-J --jumpTrace trace jumps
-M --moveTrace trace moves
-A --allocTrace trace memory allocations
-P --paramTrace trace parameter passing
-R --regMap print register maps
-Q --memMap print memory maps
-L --labMap print label maps
-D --debugging debug interpreter itself
-f fp --framepointer=fp name of frame pointer register
-s sp --stackpointer=sp name of stack pointer register
-h hp --heappointer=hp name of heap pointer register
-r rp --returnvalue=rp name of this pointer register
-S size --stacksize=size stack size
-H size --heapsize=size heap size
-W --warnings print warnings
-z --stdcallconv standard calling convention (default: all regs are callee saved)
-o FILE --output=FILE output file (NOT IMPLEMENTED)
$Revision: 1.7 $)
Weitere Beispiele für Zwischencode (so wie er von muHwI eingelesen wird):
MiniJava Programme: ArrSumBUG.java, ArrSum.java, Newton.java, NewtonOO.java
- Instruktionsauswahl:
Um sich mit der Zielarchitektur vertraut zu machen, empfehlen wir in
folgenden Dokumenten nachzulesen:
Intel x386:
MIPS R2000/R3000:
Experimenteller i386 Simulator
(Haskell sources (ghc-6.4 und höher) und Linux-binary) risc386.
Besonderes Feature: Erlaubt eine unbegrenzte Zahl von Hilfsregistern t0,t1,... Diese werden bei Funktionsaufruf automatisch gesichert und bei Rückkehr rückgesichert. Man kann also seinen Code vor Registerzuweisung testen.
Eingabeformat:
- Liest
.s-Dateien in Intel syntax. Beispiel Factorial.raw.s:
.intel_syntax
.type LFactorial$main, @function
#args
LFactorial$main:
push %ebp
mov %ebp, %esp
L3: push 0
call L_halloc_obj
add %esp, 4
mov t1001, %eax
push 0
push t1001
call L_init_obj
add %esp, 8
push 10
push t1001
call LFac$ComputeFac
add %esp, 8
mov t1002, %eax
push t1002
call L_print
add %esp, 4
L4: leave
ret
.type LFac$ComputeFac, @function
#args LOC 0, LOC 4
LFac$ComputeFac:
push %ebp
mov %ebp, %esp
L5: cmp DWORD PTR [%ebp+12], 1
jl L0
jmp L1
L2: mov %eax, t8
jmp L6
L1: mov t1004, DWORD PTR [%ebp+12]
mov t1005, -1
add t1005, DWORD PTR [%ebp+12]
push t1005
push DWORD PTR [%ebp+8]
call LFac$ComputeFac
add %esp, 8
mov t1003, %eax
mov %eax, t1004
imul t1003
mov t8, %eax
jmp L2
L0: mov t8, 1
jmp L2
L6: leave
ret
as-Direktiven, beginnend mit "." (Punkt), werden ignoriert.
- Zeilen, die mit "# " (Doppelkreuz Leer) beginnen (Kommentare),
werden ebenfalls ignoriert.
- Das erste Label startet die erste Prozedur, die mit
ret endet.
- Will man dem Simulator die Argumente der Prozedur mitteilen
(für schönere Traces), tut man das mit dem Pragma
#args, gefolgt von einer Komma-separierten Liste von
Argumentdeskriptoren im muHwI-Stil.
- Die Prozedur, deren Name auf
main endet, wird ausgeführt.
Befehlssatz (RISC): Sehr reduziert, nur 32bit-Befehle
- Zuweisung:
mov
- Arithmetik:
add sub imul idiv cdq neg inc dec lea sal sar
- Booleans:
and or xor not
- Stack:
push pop leave und enter _,0
- Kontrollfluss:
call ret jmp je jne jl jle jg jge
- Flags:
cmp (Nur dieser Befehl setzt Flags, entgegen der Intel Spec.)
Speichermodell - Heap:
- Mit
h_alloc_obj oder h_alloc_arr kann
man sich eine Heap-Zelle anfordern, diese werden als h0,
h1, ... geschrieben.
- Eine Heapadresse besteht aus einem Zellen-Bezeichner und einem
Offset, also z.B.
h1:-4 für die Länge des bei
h1 liegenden Arrays oder h0:4 für das
erste Feld des Objektes in der Zelle h0.
- Offsets, die nicht durch 4 teilbar sind oder aus der Zelle herauszeigen, sind ungültig.
- Zugriff auf eine ungültige Heap-Adresse wirft eine Ausnahme.
- Ebenso das Laden einer nicht-initialisierten Heap-Adresse.
Speichermodell - Stack:
- Der Stack ist ein linearer Adressraum, getrennt vom Heap.
- Interna: beginnt mit 0, nach unten wachsend (also Stackadressen
sind intern negativ).
- Die Register
esp und ebp dürfen nur mit Stack-Adressen geladen werden.
Kontrollfluss:
- Jumps und calls nur auf feste labels!
call legt eine Rücksprungadresse auf den Stack, die von ret wieder entfernt wird. Intern ist das der Bezeichner der aufgerufenen Funktion. Die Sprungadresse kann nicht verwendet werden.
- Ein call sichert alle temp-Register.
Debuggingoptionen:
- NYI
- risc386 schreibt einen Call- und execution-trace nach stderr, mehr gibts im Moment noch nicht.
Aktivitätsanalyse:
Zur Visualisierung der Graphen, die in der Analyse erzeugt werden,
bietet sich das dotty tool an,
das auf den CIP Rechnern installiert ist (Packet: graphviz).
Aufruf zur Erstellung eines PostScript files (dotty Beispielsfile):
dot -Tps example.cfg.dot -o example.cfg.ps
Dokumentation:
Zusammenfassung:
Zum Aufruf der Systemfunktionen aus dem generierten Assembler code,
kann man folgende Laufzeitbibliothek verwenden.
|
|
