Aalborg den 08.04.2003

Kompilerkonstruktion: Kode generation

Litteratur

Appel kapitel 8 samt kapitel 9.

Læsevejledning

Kapitel 8 forsøger at simplificere træ mellemkode sproget kaldet Tree fra figur 7.2 på side 138. Formålet med dette er at bringe mellemkoden i et format som passer bedre på target sproget f.eks. assembler kode til en Intel Pentium processor. Det skal altså være nemmere at oversæt Tree sproget til target sproget.

I sektion 8.0 på side 162 beskrives nogle af de problemer, der er med Tree sproget set fra target sproget. Som et eksempel JUMP operation i Tree sproget  tager både en sand og en falsk label med. En JUMP operation i et assembler sprog tager derimod normalt kun en label. For at rette op på dette misforhold mellem Tree sproget og target sproget indføres der derfor en tre trins transformation af Tree sproget, så det passer bedre til target sproget.

I sektion 8.1 beskrive først generelle transformation som illustreres i figur 8.1 på side 165. (1) og (2) fra figur 8.1 burde være til at forstå umiddelbart. Bemærk den væsentlige term commute midte på side 164. Med dette menes, at to udtryk e1 og e2 begge giver det samme resultat lige meget hvilken rækkefølge de er beregnet i, altså (a) e1 før e2 eller (b) e2 før e1.

I sektion 8.2 indføres to begreber basic block og trace brug tid på at forstå disse og hvordan traces generes vha. Algorithm 8.2 på side 172. I kan springe over afsnittet "Optimal Traces" på side 173.

I kapitel 9 skal det omformede Tree sproget oversættes til et assembler sprog kaldet Jouette, altså et target sproget. Dette er selvfølgeligt hardware afhængigt. I sektion 9.0 gives første et overblik over fliselægning (tiling) altså hvorledes man kommer fra mellemkode udtrykt i Tree sproget til assemler udtryk i Jouette.

Sektion 9.1 omhandler forskellige algoritmer for hvorledes man bedst "lægger fliser" i et helt træ udtrykt i Tree sproget. Der gives to måder (1) Maximal Munch og (2) Dynamic programming. Prøv at forstå begge ideen i begge disse måder.

Sektion 9.2 omhandler CICS og RISC maskiner. Disse er rimeligt forskellige maskiner som har f.eks. stor forskel i antal a registre tilgængelig. Desuden er selve opbygning af instruktioner forskellige. RICS maskiner bruger typisk three-address koder, mens CICS maskiner typisk bruger two-address koder. Sæt jer ind i hvad dette betyder.

Sektion 9.3 beskriver instruktionsselektion for MiniJava. Kig på de dele af denne sektion, der er relevant i forhold til jeres projekt.

Opgaver

A Opgave 8.1

B Opgave 8.6

C Opgave 9.1

D Opgave 9.3

Venlig hilsen

Kristian Torp
torp(at) cs (dot) auc (dot) dk