Übersetzerbau 2 2017-08-09

Fach: Optimierungen in Übersetzern

Prüfer: Prof. Philippsen

Beisitzer: Marius Kamp

• Welche wichtige Datenstruktur haben wir denn fuer Optimierungen verwendet? ~> KFG
• Was ist ein KFG, Basisbloecke, wie erstellt man ihn?
• Was kann man damit machen ~> Dominanz bestimmen
• Was ist Dominanz? Wie kann man sie bestimmen? ~> iterativer Fixpunktalgorithmus, Lengauer-Tarjan
• Wie funktioniert iterativer Fixpunktalgorithmus?
• Wofuer wird Dominanz benoetigt? ~> Kontrollflussabhaengigkeit
• Was ist Dominanzgrenze, wie bestimmt man sie?

class C {
//...
}
 
void foo(C p) {
  C c = new C();
  nullptrcheck(c);
  nullptrcheck(p);
  c.x = p.x
  // ...
}

• Wie kann man unnoetige Nullptrchecks erkennen? ~> Datenflussanalyse
• Bitvektorbelegung, Gen-, Kill-Mengen, Konfluenzoperator angeben.
• Was hatten wir noch an Werkzeug fuer Datenflussanalyse? ~> SSA
• Was ist SSA?
• Wie in SSA transformieren? ~? Wertnummerierung (Click)/Dominanzgrenzen (Cytron)
• Click angewandt.
• Wie aus SSA zurueck? ~> CSSA waere nett, Transformationen machen aber iA

Lebensspannen kaputt, also Temporaervariablen einfuehren, drei Zuweisungen.

• Was ist schleifeninvarianter Code?
• Ist bei diesem Codestueck die Zuweisung invariant? ~> abhaenging von p ~> Aliasanalyse
• Welche benutzen wir? ~> interprozedural, also Steensgard
• Steensgard angewandt.
• Was sind Induktionsvariablen? Welche Arten gibt es?
• Transformationsschablone auf gegebenes Codestueck angewandt.
• Schleifengrenze angepasst; illegal bei Ueberlauf.