Übersetzerbau 2 2015-07-27

Fach: Optimierungen in Übersetzern

Prüfer: Prof. Philippsen

Wie in anderen Protokollen schon erwähnt, es gibt wohl eine Agenda, thematisch bis zum letzten Teil durchzukommen. Ungefragte Extrainformation kosten Zeit und bringen keinen Bonus. Fragen werden aber sehr oft offen gestellt (Typisch: Was kann man denn hier noch so tun?) und nachdem man das richtige Schlüsselwort genannt hat gibts dazu eine Frage. Die Themen auf der Prüfungsagenda sind immer recht ähnlich, es lohnt sich also sich die entsprechenden Punkte zu merken und (wenn im Code Beispiel passend) gezielt zu nennen.

  b = foo();
 
  for( int i = 0; i < 1024; i++) {
    t = 23 + A[i]
    if( b %2 == 0)
      for( int j = 0; j < 1024; j++) {
        t += A[i*4+j];
        A[i*4+j] = bar( A[i*4+j-1]);
      }
    }
    A[i] = t;
  }

1. Was macht ein Compiler da so?
2. Was ist invarianter Code und wann kann der vorgezogen werden?
3. Was ist Dominanz?
4. Dominiert die Schleife hier den Schleifenausgang/Wo ist der Schleifenausgang?
5. Wie kann man trotzdem Code aus der Schleife herausziehen?
6. Dominatorberechnung (hier muss man möglw. immer nur das Verfahren erklären das man als erstes nennt)?
7. Dominanzgrenzen?
8. Wie werden gemeinsame Teilausdrücke gefunden?
9. Was ist SSA/Wie wird SSA konstruiert?
10. Welchen Vorteil hat das?
11. Was sind Induktionsvariablen/was kann man damit machen?
12. Wie verändert sich die Schleife wenn man die Induktionsvariable ersetzt (detailliert)?
13. Was können wir noch machen (Parallelisierung)?
14. Was sind die Abhängigkeiten?
15. Wann genau kann eine Schleife parallelisiert werden/Welche Schleife kann hier parallelisiert werden?
16. Was kann getan werden, um die äußere Schleife zu parallelisieren/Wie kann die Abhängigkeit von t aufgelöst werden?
17. Wie funktioniert scalar splitting?