Einführung - WWW-Docs for TU

 Documents

 116 views
of 23
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Description
Vorlesung Compilertechnik Sommersemester 2009 Zielcodeerzeugung M. Schölzel Aufgabe der Zielcodeerzeugung  Erzeugung von Programmcode, der auf der…
Share
Transcript
Vorlesung Compilertechnik Sommersemester 2009 Zielcodeerzeugung M. Schölzel Aufgabe der Zielcodeerzeugung  Erzeugung von Programmcode, der auf der gewünschten Zielarchitektur ausgeführt werden kann (oft Assemblercode). Das schließt ein:  Übersetzung der Zwischencodeanweisungen in Assmeblercode (Code-Selection, Scheduling).  Registerallokation.  Erzeugung einer Laufzeitumgebung für das Programm.  Speicherorganisation. 2 Einbettung der Zielcodeerzeugung in den Compiler  Programmkode enthält den aus den Zwischenkodeanweisungen erzeugten Zielcode und statisch erzeugten Zielcode (z.B. Prolog zur Initialisierung der Laufzeitumgebung, Prozeduren zur dynamischen Speicherverwaltung)  Erzeugung statischer Daten (globale Variablen, Konstanten)  Heap speichert dynamisch erzeugte Objekte, die in einer Prozedur erzeugt werden und auch nach dem Verlassen der Prozedur erhalten bleiben sollen.  Stack speichert Rücksprungadressen und lokale Variablen von Prozeduren. Programmcode Statische Daten 3-Adress-Code Zwischen- t2 := t1 + t0 code- t3 := a Zielcode- Heap erzeugung t4 := t2 * t3 erzeugung … Stack 3 Prinzipielles Vorgehen  Für jede Anweisungsart des 3-Adress-Codes ist eine Schablone für den zu erzeugenden Zielcode bekannt.  In dieser Schablone müssen noch die Speicherorte (i.Allg. Register), die die Werte der Variablen des 3-Adress-Codes enthalten, eingetragen werden.  Die benötigten Werte werden durch die Registerallokation an geeigneten Orten zur Verfügung gestellt.  Während der Zielcodeerzeugung wird in geeigneten Datenstrukturen dieser Speicherort mitprotokolliert.  Registerallokation erzeugt auch den Zielcode zum Laden/Speichern von Registerwerten aus dem/in den Speicher. Registerinhalte ein-/auslagern mov [0x1450],r4 mov r7,[0x1454] add r0,r4,r7 r?,r?,r? r0,r?,r? r0,r4,r? … Anweisung- Wert von Wert von Ziel- t12 := a art identi- t5 in t12 in register t13 := t5 + t12 fizieren und Register Register für t13 b := t13 Schablone bereit- bereit- bereit- if t11 then goto next erzeugen stellen stellen stellen … 4 Registerallokation  Ziel: Abbildung der temporären Variablen eines Zwischencodeprogramms auf eine beschränkte Anzahl von Prozessorregistern.  Klassifizierung der Registerallokation:  Lokal: Auf den Basisblock beschränkt.  Global: Für Funktionen oder das gesamte Programm.  Vorgehensweise bei der Registerallokation hängt stark von der Zielarchitektur ab:  Register-/Register-Architektur oder Register-/Speicher- Architektur,  2-Adress- oder 3-Adress-Architektur,  Universeller Registersatz oder Spezialregistersatz,  Flache oder tiefe Registerhierarchie. 5 Fiktive Zielarchitektur  Bei den weiteren Erläuterungen betrachten wir eine Zielarchitektur mit folgenden Eigenschaften:  32-Bit-Register:  Stackpointer: sp  Basepointer: bp  Weitere allgemeine Register: r0,…,r15  Operationen und Bedeutung:  mov rx,ry: ry := rx  mov #imm, rx: rx := imm  mov [addr],rx: rx := mem[addr]  mov rx,[addr]: mem[addr] := rx  add rx,ry,rz: rz := rx + ry  add rx,#imm,rz: rz := rx + imm  Dabei sind:  rx, ry, rz  {sp, bp, r0, …, r16},  imm ist ein 32-Bit-Wert,  addr ist eine 32-Bit-Speicheradresse oder addr  {sp, bp, r0, …, r16} oder addr = bp + imm 6 Lokale Registerallokation für 3-Adress-Register- /Register-Architektur: Verwaltungsstrukturen  V ist die Menge aller Variablen im 3-Adress-Code.  Registerdeskriptor rd : {0,…,RegNum – 1}  (V  {w,r}) speichert für jedes Register die Menge der Variablen, deren Werte sich im Register befinden sowie deren Lese-/Schreibzustand.  Speicherdeskriptor: sd: V   speichert für jede im Speicher abgelegte Variable die Speicheradresse (absolut für globale und relativ für lokale Variablen).  Belegungssituationen der Verwaltungsstrukturen:  Für jede globale Variable a ist durch sd(a) immer ein Speicherplatz festgelegt.  Bei Übersetzung einer Funktion f ist außerdem für jede lokale Variable a in f durch sd(a) eine relative Adresse festgelegt.  Für eine temporäre Variabel existiert  kein Eintrag in rd oder sd,  nur ein Eintrag in rd oder  nur ein Eintrag in sd oder  ein Eintrag in rd und sd.  Für eine Programmvariable existiert  immer ein Eintrag in sd  möglicherweise auch ein Eintrag in rd; dann befindet sich der aktuelle Wert der Variablen im Register. 7 Hilfsfunktionen und Schnittstelle der Registerallokation  Hilfsfunktionen für eine Variable v:  isLocal(v) = True gdw. der Speicherplatz für v im Stapel ist.  addr(v) ist die Adresse des Speicherplatzes von v oder die relative Adresse, die während des Aufbaus der Symboltabelle festgelegt wurde.  getNextFreeLocalAddress(): Liefert die nächste freie relative Adresse im Stapel  getFreeReg(): liefert den Namen eines Registers, in das ein neuer Wert geschrieben werden kann.  getVarInReg(v): Erzeugt den erforderlichen Zielcode, um den Wert der Variablen v in einem Register bereitzustellen.  lockReg(r): Verhindert, dass der Inhalt des Registers r bei folgenden Registeranforderungen ausgelagert wird.  unlockReg(r): Klar  setRegDeskr(r,x): Danach gilt (x,w) = rd(r) und für alle i: 1  i  RegNum und i  r  (x,w)  rd(i) und (x,r)  rd(i).  delete(x,r): Danach gilt: (x,w)  rd(r) und (x,r)  rd(r).  clear(): Löscht Einträge im Speicher- und Registerdeskriptor.  saveRegs(): Sichert Register im Speicher, die aktualisierte Werte von Programmvariablen enthalten. 8 Implementierung von getFreeReg Eingabe: keine Ausgabe: Name eines Registers, dessen Inhalt überschrieben werden kann Algorithmus getFreeReg: Falls ein i existiert mit 1  i  RegNum und rd(i) =  dann return i Falls ein i existiert mit 1  i  RegNum und für alle (v,x)  rd(i) gilt x = r, dann rd(i) := , return i Wähle ein s mit 1  s  RegNum und s ist nicht gesperrt Spill(s) return s Eingabe: Registernummer s Ausgabe: Zielcode zum Auslagern des Registerwertes Algorithmus Spill: for each (v,w)  rd(s) do if sd(v) undefiniert then addr = getNextFreeLocalAddr() outCode("mov s,[bp-addr]") sd(v) := addr else if v ist global then outCode("mov s,[sd(v)]") else outCode("mov s,[bp-sd(v)]") fi fi od 9 rd(s) :=  Beispiel: getFreeReg  Aufruf: getFreeReg() mit Registerdeskriptor: Registerdeskriptor: Erzeugter Spillcode: Neuer Registerdeskriptor: i rd(i) Keiner i rd(i) 0 (t0,w), (a,r) 0 (t0,w), (a,r) 1  1  2 (t2,w), (c,r) Rückgabewert 2 (t2,w), (c,r) … : … 15 (t15,w), (p,r) r1 15 (t15,w), (p,r)  Aufruf: getFreeReg() mit Registerdeskriptor: Registerdeskriptor: Erzeugter Spillcode: Neuer Registerdeskriptor: mov r1,[bp-sd(t1)] i rd(i) i rd(i) mov r1,[sd(a)] 0 (t0,w), (t16,w) 0 (t0,w), (t16,w) 1 (t1,w), (a,w) 1  2 (t2,w), (t18,w) Rückgabewert 2 (t2,w), (t18,w) … : … 15 (t15,w), (t31,w) r1 15 (t15,w), (t31,w) 10 Implementierung von getVarInReg Eingabe: Variable t Ausgabe: Name des Registers, in dem der Wert der Variable bereitgestellt wurde Algorithmus getVarInReg: if x{r,w}i:1  i  RegNum und (t,x)  rd(i) then retrun i fi if i:1  i  RegNum und rd(i) =  then s := i else if i:1  i  RegNum und (v,x)  rd(i): x=r then s := i else Wähle ein Register i mit geringen Kosten beim Auslagern und i ist nicht gesperrt Spill(i) s := i fi fi rd(s) := {(t,r)} if t ist lokal then outCode("mov [bp-sd(t)],s") else outCode("mov [sd(t)],s") fi return s 11 Beispiel: getVarInReg  Aufruf: getVarInReg(t1) mit Registerdeskriptor: Registerdeskriptor: Erzeugter Spillcode: Neuer Registerdeskriptor: i rd(i) Keiner i rd(i) 0  0  1 (t1,w), (b,r) 1 (t1,w), (b,r) 2 (t2,w), (c,r) Rückgabewert 2 (t2,w), (c,r) … : … 15 (t15,w), (p,r) r1 15 (t15,w), (p,r)  Aufruf: getVarInReg(t16) mit Registerdeskriptor: Registerdeskriptor: Erzeugter Spillcode: Neuer Registerdeskriptor: mov r0,[bp-sd(t0)] i rd(i) i rd(i) mov r0,[sd(a)] 0 (t0,w), (a,w) mov [bp-sd(t16)],r0 0 (t16,r) 1 (t1,w), (b,w) 1 (t1,w), (b,w) 2 (t2,w), (c,w) Rückgabewert 2 (t2,w), (c,w) … : … 15 (t15,w), (p,w) r0 15 (t15,w), (p,w) 12 Übersetzung binärer/unärer Anweisungen Eingabe: 3-Adress-Code-Anweisung x := y  z Ausgabe: Zielcode Algorithmus: l := getVarInReg(y); lockReg(l); r := getVarInReg(z); lockReg(r); if isTemp(y) then Delete(y,l); if isTemp(z) then Delete(z,r); t := getFreeReg(x); unlock(l); unlock(r); asmmnem := Assembleropertion für  outCode("asmmnem l,r,t"); setRegDeskr(t,x) Eingabe: 3-Adress-Code-Anweisung x :=  y Ausgabe: Zielcode Algorithmus: r := getVarInReg(y); lookReg(r); if isTemp(y) then Delete(y,r); t := getFreeReg(); unlook(r); asmmnem := Assembleropertion für  outCode("asmmnem r,t"); setRegDeskr(t,x) 13 Beispiel  Übersetzung von t20 := t1 + t16; Aufruf von getVarInReg(t1) und getVarInReg(t16): Registerdeskriptor: Erzeugter Spillcode: Neuer Registerdeskriptor: mov r0,[bp-sd(t0)] i rd(i) locked i rd(i) locked mov r0,[sd(a)] 0 (t0,w), (a,w) 0 mov [bp-sd(t16)],r0 0 (t16,r) 1 1 (t1,w), (b,w) 0 1 (t1,w), (b,w) 1 2 (t2,w), (c,w) 0 Rückgabewert 2 (t2,w), (c,w) 0 … : … 15 (t15,w), (p,w) 0 r1 für t1 15 (t15,w), (p,w) 0 r0 für t16  Aufruf von getFreeReg() Registerdeskriptor: Erzeugter Spillcode: Neuer Registerdeskriptor: Keiner i rd(i) locked i rd(i) locked 0  1 Rückgabewert 0 (t20,w) 0 : 1 (b,w) 1 1 (b,w) 0 r0 2 (t2,w), (c,w) 0 Zielcode: 2 (t2,w), (c,w) 0 … add r1,r0,r0 … 14 15 (t15,w), (p,w) 0 15 (t15,w), (p,w) 0 Übersetzung von Kopieranweisungen (1) Eingabe: 3-Adress-Code-Anweisung x := y, x := k, @x := y, x := @y oder x := &y Ausgabe: Zielcode Algorithmus: Für x := y: if ein i und ein k  {r,w} ex. mit (y,k)  rd(i) then rd(i) := rd(i)  {(x,w)}; else i := getVarInReg(y) rd(i) := rd(i)  {(x,w)}; fi if isTemp(y) then Delete(y,i) Für x := k: r := getFreeReg() outCode("mov #k,r") setRegDesk(r,x); return; Für x := &y: r := getFreeReg() if isLocal(y) then outCode("mov bp,r"); outCode("add r,#addr(y),y"); else outCode("mov #addr(y),r") setRegDesk(r,x); return; 15 Beispiel  Übersetzung von t20 := z Registerdeskriptor: Erzeugter Spillcode: Neuer Registerdeskriptor: keiner i rd(i) locked i rd(i) locked 0 (t0,w), (a,w) 0 0 (t0,w), (a,w) 0 1 (z,w), (b,w) 0 1 (z,w), (b,w), (t20,w) 0 2 (t2,w), (c,w) 0 2 (t2,w), (c,w) 0 … … 15 (t15,w), (p,w) 0 15 (t15,w), (p,w) 0  Übersetzung von t16 := t1 Registerdeskriptor: Erzeugter Spillcode: Neuer Registerdeskriptor: mov [bp-sd(t1)],r0 i rd(i) locked i rd(i) locked 0  0 Rückgabewert 0 (t16,w) 0 : 1 (b,w) 0 1 (b,w) 0 r0 2 (t2,w), (c,w) 0 Zwischencode 2 (t2,w), (c,w) 0 … : … 15 (t15,w), (p,w) 0 Keiner 15 (t15,w), (p,w) 0 16 Übersetzung von Kopieranweisungen (2) Für @x := y: l := getVarInReg(x); lockReg(l); r := getVarInReg(y); unlock(l); if(isTemp(y) then Delete(y,r); if(isTemp(x) then Delete(x,l); outCode("mov r,[l]"); Für x := @y: r := getVarInReg(y); lockReg(r); l := getFreeReg() unlock(r); if(isTemp(y) then Delete(y,r); rd(l) := rd(l)  {(x,w)} outCode("mov [r],l"); 17 Übersetzung von Labels und Sprunganweisungen Aktualisieren der Werte im Eingabe: 3-Adress-Code-Anweisung label: Speicher. Ausgabe: Zielcode Algorithmus: … a := t7 SaveRegs(); label: Einsprung von verschiedenen outCode("label:"); t8 := a Position möglich; Belegung der Clear(); Register unklar. … Eingabe: 3-Adress-Code-Anweisung goto label Sprung zu einer Position an Ausgabe: Zielcode der der Registerdeskriptor gelöscht wird; Aktualisieren der Algorithmus: … Wert eim Speicher nötig. a := t7 SaveRegs(); goto label10 outCode("jmp label"); Hier wird die Registerallokation label9: fortgesetzt. … Eingabe: 3-Adress-Code-Anweisung if x then goto l Sprung zu einer Position an Ausgabe: Zielcode der der Registerdeskriptor Algorithmus: gelöscht wird; Aktualisieren der … Wert eim Speicher nötig. t := getVarInReg(x); a := t7 Delete(x,t) if t8 then goto label20 SaveRegs(); b := t9 Fortsetzung der outCode("BNZ t,l"); … Registeralloka-tion. Belegung der Register für jede 18 Programmausführung fest. Aktivierungsblock  Die Aktivierung einer Funktion durch einen Aufruf erfordert im Allgemeinen die Erzeugung eines Aktivierungsblocks im Laufzeitstapel.  Möglicher Aufbau eines Aktivierungsblocks: Aktivierungsblock der aufgerufenen Funktion Temporäre Daten Ausgelagerte Registerwerte im aktuellen Block Lokale Daten Lokale Variablen im aktuellen Block … Lokale Daten Lokale Variablen in Blöcken, die den aktuellen Block enthalten Maschinenregister Gesicherter Maschinenstatus der rufenden Funktion (z.B. Registerinhalte, Statusregister) Zugriffsverweis Verweis auf den Aktivierungsblock der rufenden Funktion Rücksprungadresse Adresse des rufenden call-Befehls Rückgabewerte Rückgabewert, falls vorhanden (kann sich aber auch in einem Register befinden) Aktuelle Parameter Aktuelle Parameter der aufgerufenen Funktion Aktivierungsblock der rufenden Funktion 19 Übersetzung eines Funktionsaufrufs Eingabe: 3-Adress-Code-Anweisung x := call f(t1,..,tn) Ausgabe: Zielcode Algorithmus: for i := n downto 1 do p := getVarInReg(ti) outCode("push p") Delete(p,ti) od // SaveRegs() erforderlich, falls call einen Basisblock abschließt outCode("add sp,#4,sp"); outCode("call f"); // Clear() erforderlich, falls call einen Basisblock abschließt r := getFreeReg() outCode("pop r") // Ergebniswert laden rd(r) := rd(r)  {(x,w)} // vorausgesetzt Stack wächst zu kleineren Adressen outCode("add sp,#4*n,sp"); sp Rücksprungadresse int g { t0 := 3 push r3 sp undefiniert … t1 := 4 push r2 x = f(3,4); t2 := call f(t0,t1) add sp,#4,sp 3 … x := t2 call f 4 } … pop r1 sp Aktivierungsblock der add sp,#8,sp Funktion g bp 20 Quelltext Zwischencode Zielcode Laufzeitstapel Übersetzung einer Funktionsdeklaration Eingabe: 3-Adress-Code-Anweisung Function Label: Ausgabe: Zielcode Algorithmus: outCode("push bp") outCode("mov sp,bp"); // aktuelle Parameter sind über positive Offsets // größer gleich 12 erreichbar // lokale Variablen mit negativen Offsets outCode("add sp,#frameSize,sp") int f(int a, int b) … push bp sp { Function f: mov sp,bp Lokale Variablen … … add sp,#16,sp } sp bp bp der rufenden Fkt. sp Rücksprungadresse Quelltext Zwischencode Zielcode undefiniert 4 (Parameter a) 3 (Parameter b) Aktivierungsblock der Funktion g bp 21 Laufzeitstapel Übersetzung einer return-Anweisung Eingabe: 3-Adress-Code-Anweisung return x: Ausgabe: Zielcode Algorithmus: r := getVarInReg(x) outCode("mov r,[bp+8]"); SaveRegs(); outCode("mov bp,sp"); outCode("pop bp"); outCode("return"); int f(int a, int b) mov r5,[bp+8] sp { … mov bp,sp Lokale Variablen … return t20 pop bp return 15; … return sp bp bp der rufenden Fkt. } sp Rücksprungadresse Quelltext Zwischencode Zielcode undefiniert 15 3 (Parameter a) 4 (Parameter b) Aktivierungsblock der Funktion g bp 22 Laufzeitstapel Ende der Zielcodeerzeugung Weiter zur Optimierung
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks