Optimierungen in Übersetzern

• Pruefer: Prof. Philippsen
• Beisitzer: Stefan Kempf
• Note 1.7
• ~ 30 min.
• Codebeispiel / Graphen + Bleistift

Waehrend der Pruefung herrscht ansich eine angenehme, lockere Atmosphaere, allerdings wird durchaus solange nachgebohrt, bis die richtige Antwort kommt. Insgesamt sollte man auf jedenfall gut vorbereitet sein.

Man sollte eher Wert darauf legen praezise zu antworten und weniger abzuschweifen, da sonst andere Themen, die der Pruefer wissen will, nicht mehr gefragt werden koennen (Leistung = Arbeit / Zeit).

Insgesamt sollte man sich auch mit ausgefalleneren / anderen Beispielen als aus der Uebung / der Vorlesung beschaeftigen, damit man in der Pruefung dann nicht allzu baff ist, wenn die Situation dann ploetzlich ganz anders ist.

Auf die Pruefung habe ich mich ca. 1 Woche mit durcharbeiten des Skripts vorbereitet. Dabei haette ich mehr Fokus auf verstehen der Beispiele / Schritte in den Folien legen sollen. Die Menge verschiedenen Verfahren ist sonst ohne genaues Verstehen leicht ueberfordernd.

Es wurde ein Programmausschnitt vorgelegt mit zugehoerigem KFG. Der Programmausschnitt war dabei dabei C Code. Ich habe bei der Vorbereitung eig. nur mit Zwischencode gearbeitet, weshalb hier etwas Schwierigkeiten entstanden sind. Fragen / Aufgaben:

• Wie kommt man auf den KFG → Grund Block Analyse
• Was ist jetzt aber, wenn ich in C Code zu jeder Zeile ein neues Label einfuehre? → Gemeint war hier, dass beim uebersetzen unangesprungene Label eliminiert werden
• Welche Verfahren kann man auf dem KFG anwaenden? → Dominanz, ImmDomm, …
• Wozu wird die Dominanz / ImmDoms bestimmt? → Schleifen, Phi-Fkt, …
• Was sind Dominanzgrenzen, was bedeutet das? → Neuer eingehender Kontrollfluss …
• Wie bestimmt man Dominanzgrenzen? → DGup / DGlocal Algorithmus erklaeren
• Wie werden Schleifen gefunden? → Natuerliche Schleife bei Rueckkante, Dominanz, …
• Was sind unnatuerliche Schleifen / Wie erkennt man das ein Programm solche hat? → Reduzierbarkeit …
• Phi-Fkt: Warum… → SSA Code, Vorteile SSA erlaeutert
• Mach mal SSA Code → Gemacht
• Schleifen erkennen → Code hat eine unnatuerliche Schleife enthalten, Algo zum erkennen solcher Schleifen erkannt
• Aus SSA erkennbar, dass unnatuerliche Schleife wegfaellt, KFG anpassen
• Was kann man jetzt mit der Schleife machen? → Induktionsvariablen erkennen
• Such mal die Induktionsvariablen …
• Gibt es abhaengige Induktionsvariablen? → Hier etwas tricky, die abhaengigen Ind. Variablen verstecken sich in multidimensionalem Arrayzugriff
• Was kann man jetzt mit den Induktionsvariablen machen? → Herausziehen, dazu die while-Schleife im KFG in eine do-while Schleife umbauen
• Was kann man noch machen? → Parallelisieren, Richtungsvektoren aufstellen usw.
• Stell mal den Richtungsvektor auf → aufstellen
• Kann man das ganze jetzt parallelsieren? → …

• Pruefer: Prof. Philippsen
• Beisitzer: Stefan Kempf
• Note 1.3
• ~ 30 min.
• Codebeispiel / Graphen + Bleistift

Prof. Philippsen und Stefan Kempf haben ein gutes Pokerface, sollte aber jeder der Compilerbau 2 hoert von der vorherigen Pruefung schon wissen.

Insgesamt ist in der Pruefung eine sehr angenehme Atmosphaere, es wird auch wirklich gut geholfen - der Code ist tricky, und es wird nicht erwartet alles gleich automatisch zu sehen. Aber schnell sollte man durchgehen, sonst koennte es am Ende knapp werden!

Vorbereitend sollte man neben Skript und Uebungsblaetter den Uebungscompiler auch implementiert/optimiert haben, hilft ungemein.

War vermutlich das gleiche Beispiel wie das ueber diesem Protokoll; zumindest der Pruefling nach mir hatte den gleichen Code vor sich ;)

Man bekommt ein Stueck C-Code und den entsprechenden KFG. Meine Vorfreude ueber die fehlende &-Operatoren wurde doch etwas gedaempft, als ich die * gesehen hab ;) Der Code und der KFG sind frei aus dem Gedaechtniss, keine Garantie auf Richtigkeit!

static int ArrayA[65536][65536];
static int ArrayB[65536][65536];
 
int *get_first_array(){ return ArrayA; };
int *get_second_array() { return ArrayB; };
 
int main(){
	int *A = get_first_array();
	int *B = get_second_array();
	int c=0;
	for (int i=0;i<1024;i++){
		int j=0;
		if (A==B){
			c++;
			goto append;
		}
 
	/* Maybe some code? */
 
inside:
		if (j<=1024){
append:		
			A[i][j]=B[c][c]+A[i-1][j-2]*A[i][j+2048];
			c = c * c;
			j++;
			goto inside;
		}
 
out:
	}
	return 0;
}

• P: Da kann man ja viele Labels in C reinschreiben, wie wirkt sich das auf den KFG aus?
• A: Gar nicht so sehr, da unnuetze Labels vom RemoveGarbage (zumindest bei unserem E-Compiler) entfernt werden.

• P: Welche Optimierungen kann man auf dem KFG machen?
• A: Dominatoren, Dominanzgrenzen (usw mit Erklaerung)

• P: Wozu braucht mans?
• A: SSA, fuer „c“ mit einem Algorithmus (egal ob Click oder Standard) durchfuehren, Vorteile von SSA erklaeren

• P: Welche Rueckwaertskanten gibts?
• A: nur die von der For-Schleife (gruen). Die andere (rot) wird nicht dominiert, wegen dem „goto append“

• P: Schauen sie sich mal das „if (A==B)“ genau an!
• A: Ja, wird nie ausgefuehrt, da A und B (immer) unterschiedlich sind. Kann man loeschen (also alles was blau ist).
• (+ Erklaerung, dass die Zuweisung „A[i][j]=“ nichts an der Adresse aendert)

• P: Intraprozeduale Aliasanlayse hilft nicht um das zu erkennen. Wie bekommt mans raus?
• A: Interprozedual, Beispiel Steensgard. A –> ArrayA, B –> Array B , nicht verknuepft, kein gemeinsamer Knoten, somit unabhaengig.

• P: Was kann man noch optimieren? Schauen sie sich mal „c“ an
• A: c wird nun immer 0 bleiben. Bekommt man raus durch bedingte Konstantenfortschreibung (kurz erklaeren).

• P: Welche Schleifen gibts nun?
• A: Zwei (rot und gruen).

• P: Was sind alles Induktionsvariablen, was ist invariant, was kann man rausziehen, was sind die regeln dazu.
• A erklaert; Definitionen dazu sollte man gut koennen.
• Wichtig ist das man durch den C-Code die implizite Arrayberechnung nicht sieht - da ist noch „dim“ in „(i-1)*dim+(j-2)“!

• P: Welche Datenbaehngigkeiten gibts
• A: Fluss+Anti, mit Vektor.

• P: Nun schauen sie sich die Arrayzuweisung an
• A: Da nun B[0][0] ist kann man es nun rausziehen.

• P: Weiter schaun!
• A: Da die schleife nur bis j⇐1024 geht, interessiert der letzte Arrayzugriff nicht (j+2048 - somit keine Abhaengigkeiten)

• P: Wie macht mans paralell?
• A: erste Schleife traegt die Abhaengigkeit, man kann somit die innere paralell ausfuehren

• P: Geht auch die aeussere?
• A [stottert ergebnislos bei Schleifenneigung rum] - Richtig ist: ja, durch Schleifenneigung und vertauschen.

• Datum: 22.08.2013
• Pruefer: Prof. Philippsen
• Beisitzer: Jakob Krainz
• ~ 30 min.

Fragen: (Antworten werden mit → eingeleitet)

• Was haben wir denn in der Vorlesung gelernt?
• Was ist KFG? Wie bestimmt man KFG? Dominatoren Wozu? → SSA-Form bestimmen. Wozu noch? → Regionen, insbesondere Schleifen erkennen.
• Was sind Dominatoren? Wie bestimme ich Dominatoren, ImDom und DominatorGrenze?
• Wie erkennt man Schleifen? Welche Arten gibt es?
• Was sind Induktionsvariablen? Welche Arten gibt es?
• Wie bringe ich in SSA-Form? Wozu? Wie komme ich wieder zurück?
• Wie kann man den Schleifenrumpf verkleinern?
• Wann kann man schleifen parallelisieren? Zeig das mal an dem beispiel.