Ü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.