TU Wien:Codegeneratoren VO (Krall)/Prüfung WS2012

Registerallokation

Gegeben Konfliktgraph (ca 8 Knoten). Berechne mit

(a) dem Algorithmus von Chatin, und
(b) dem Algorithmus von Briggs

wieviele Register benötigt man um den Graphen ohne spills einzufärben und außerdem eine Registerbelegung.

Web Algorithmus

Gegeben call graph (Knoten A-I), 3 globale Variablen, L_REF.

Berechne P_REF, C_REF die Webs und eine Registerbelegung für die globalen Variablen.

List scheduling

Ein Program in Pseudo-Assembler (8 Instruktionen) die Latenzen der Befehle.

Berechne den Interferenzgraphen und einen Schedule mittels list scheduling.

Software pipelining

Gegeben eine Schleife. Berechne eine gepiplinete Version der Schleife.

Schleife:

 load R0, (R1)     // deref R1 and load into R0
 add  R1, R1 + 1   // increment R1
 beqz R0           // branch to load if R0 == 0

Anmerkung (WS20): Bei uns war dasselbe Beispiel. Wichtig beim Verstehen der letzten Aufgabe:

• Load hatte ein Latenz von 2 Zyklen (branch und add 1 Zyklus).
• Prozessor konnte 1 Load, 1 Add und 1 Branch pro Zyklus ausführen
• Es gabe den Hinweis, dass es auch einen "negierten" Sprungbefehl gab (bnqz oder ähnlich), welche springt wenn RX != 0 ist.