Uebersetzerbau 2 (SS 2012)

Pruefer: Prof. Dr. M. Philippsen (P)
Beisitzer: Dipl.-Inf. T. Blaß (B)

Meiner Meinung nach muss man die Sachen wirklich Verstanden haben sonst geht man in der Pruefung hoffnungslos unter. Es kommen sehr viele Wissensfragen und Zusammenhangsfragen also nicht einfach den Autopilot einschalten (um moeglichst schnell zu sein) und einfach los legen sonder spezifisch auf die Frage eingehen und auf zwischen Fragen ala „Warum ist/muss X jetzt so/so sein?“ gefasst sein.

Seid schnell (aber verfallt nicht in eine Art Autopilot (siehe unten)) und versucht alles moeglichst fluessig ohne viel zu stocken rueber zubringen. Wenn man was nicht weiss wird einem zwar geholfen: Frage neu formuliert und ggf. erklaert bis man die Antwort weiss. Das wird einem anscheinend auch nicht negativ angerechnet (wenn man die Frage richtig beantwortet) aber die dabei verlorene Zeit schon. Anscheinend hat Prof. Philippsen eine Art Agenda die er durchbekommen will und wenn man nicht alles oder zu wenig schafft macht sich das an der Note bemerkbar.

Schreibt und malt ordentlich sonst kann es zu Missverstaendnissen zwischen euch und dem Pruefer kommen … was wiederum Zeit kostet und sich auch wiederum negativ auf die Note auswirkt.

B: Hier 3 Address Code von:

int foo(int f)
{
	int a = ...;
	int b = ...;
	int c = ...;
	int d[16];
	int e = ...;
	while(i > 7)
	{
		e = 3;
		if( e != f )
		{
			e = 5;
			d[i-3] = a/b;
		}
		else
		{
			d[i-2] = a*b;
		}
		d[i] = a*b/e;
	}
	return 0;
}

P: Sie sind Compiler optimieren Sie die Schleife.
A: Schleife finden. Dazu erst mal KFG.
<KFG>
A: Rueckwaertskante finden dazu Ds, iDs und DTree [war im Autopilotenmodus um moeglichst schnell zu sein, also einfach mal /alles/ erklaert und gemacht]
A: Ds mit Fixpunkt Algorithmus
B: Warum rechnen Sie jetzt die Dominatoren aus reicht es nicht einfach Rueckwaertskanten im KFG zu frueherem Code?
A: Nein weil:

L1:
	bra L3:
L2:
	X
L3:
	bra L2;

dann ist L3 - L2 ja auch keine Schleife.
A: … dann Dominatorbaum und wenn man dann eine Rueckwaertskante im DTree hat da ist die Schleife.
P: Dazu braucht man nicht den DTree.
A: E(n,d) mit d » n ist Rueckwaertskante. Also ja geht ohne DTree.
P: Aber warum dann den DTree.
A: Effizienter (weil man nicht ueber alle Kanten sondern nur ueber die wirklichen Rueckwaertskanten gehen muss)
P: Hmmm… nnnn…. ja, aber das meinte ich nicht. In O ist ja beides O(E)
A: …
P: Was kann man denn mit dem DTree anfangen.
A: Regionen finden, …
P: Genau, was ist dass … ?
A: Ahh.. Stichwort: unnatuerliche Schleifen, da hat man dann keine Rueckwaertskante.
P: Wie stellt man so was fest?
A: Reduzierbar. T1 und T2 Transformationen und wenn am Ende nur noch ein Knoten uebrig bleibt gibt es keine unnatuerlichen Schleifen.
B: Hier der KFG zu dem Code.
P: Machen Sie das mal!
A: <mach> [Hier habe ich unsauber gezeichnet beim zusammen Fassen der Knoten dadurch Entstanden wohl ein, zwei Missverstaendnisse. Also ordentlich Zeichnen vielleicht auch mal ueben wie man einen KFG „in-place“ auf einem Blatt reduziert ohne das es unleserlich wird.]
P: Ja jetzt haben wir also die Schleife gefunden. Was koennen sie hier optimieren?
A: Invarianten Code herausziehen.
P: „Erklaeren Sie mal ziehmlich genau was invarianter Code ist“
A: Erreichende Definition ausserhalb der Scheife, Konstant, muss Schleifenausgang dominieren etc ..
P: Gut dann zeigen Sie mal.
A: a ist invariant und b als ist a*b invarianter Ausdruck kann man vor die Schleife schreiben tmp = a*b, dann vielleicht noch Schleife umschreiben so das if© PREHEADER while© BODY … achso man sollte sowieso aus der while© BODY eine if© do BODY while© machen sonst dominiert nichts in der Schleife den Ausgang.
P: Machen Sie mal bitte.
A: <schmiert im KFG rum>
P: Gut und das e kann man da was machen?
A: Nein dominiert nicht den LoopExit
P: Was koennen sie noch machen?
A: Induktionsvariablen
P: Gut … aber warten Sie ich sehe noch etwas if( e != f )
A: davor steht e = 3; Konstantenpropagation und dann ist e != f invariant und man kann loop-unswitching machen dann dominiert jeweils das e = 5 LoopExit und es ist invariant.
P: Warum will man hier Loop Unswitching.
A: Wegen dem Branch der ist nicht gut wegen Sprungvorhersage.
P: Und warum will man das jetzt noch?
A: Pre-Fetching, Pre-Loading, <Buzzword #42>
P: … [hier wusste ich nicht wirklich worauf er hinaus wollte]
P: Was macht eine CPU damit.
A: Kommt drauf an was fuer eine.
B: Denk einmal an eine moderne CPU.
A: Moderne CPUs haben einen Branch Predictor der ist nach 1,2 mal Schleifendurchlaufen trainiert immer den richtigen (wenn konstanten) Branch zu nehmen und den dann zu Pre Loaden.
P: Ja genau wegen der Instruktions Pipeline. [Hier ist mir immer noch nicht klar was gemeint ist denn wegen Bra-Pres modernen CPUs ist des (bei dieser kleinen Schleife) eigentlich voellig egal ob man unswitched oder nicht … oder vielleicht wollte er darauf hinaus, dann sollte er aber nicht Fragen warum ist es /gut/ hier zu unswitchen]
P: Gut das war es schon. Das mit den Induktionsvariablen haette ich Sie gerne noch gefragt da habe wir aber leider keine Zeit mehr.

<vor die Tuer und zurueck komm>

P: Welche Note wuerden Sie sich geben.
A: Keine 1.0 weil es viel zu langsam war.
P: Ja genau.
…

Irgendwo kam noch:

P: Erreichende Definitionen wie findet man die.
A: DFA: Vorwaertsanalyse …

und

A: Worklist Algorithmus um alle BBs der Schleife zu finden.
P: Warum funktioniert das?
P: Wiese kriegt man hier jetzt keinen Knoten der ausserhalb, bzw. vor der Schleife liegt.
A: Weil LoopHeader alle BBs in der Schleife (alle Vor-,Vorvor- und Vorvorvor…gaenger von LoopExit) dominiert waere dies nicht so so wuerde auch LoopHeader » LoopExit nicht gelten)

Von einem anderen Kommilitonen weiss ich dass die restlichen Fragen gewesen waeren (an neuem Code):

int A[6];
int B[6];
 
int main() {
	int *c = &A;
	int d = 0;
	if(d > 3) {
		foo(c,A);
	} else {
		foo(c,B);
	}
	return 0;
}
 
void foo(int *a, int *b) {
	for(int i = 1; i < 5; ++i) {
		for(int j = 1; j < 5; ++j) {
			a[i,j] = a... b...
			a[i+1,j] = ...b // keine ahnung ^^
		}
	}
}

P: Sind die Schleifen parallelisierbar?
A: Abhaengigkeiten bestimmen. Parallelisierbar machen durch Neigen und Tauschen.

P: Wie macht man Interprozedurale Alias Analyse
A: Steensgard

In dem Sinne nehmt zum lernen kleine Code Fetzen und versucht so schnell und praezise alles zu erklaeren und zu machen. Ds ⇒ Schleifen, Invarianten Code, Schleifenrestrukturierung, Alias Analyse.
Wichtig ist neben Schnelligkeit aber immer die Exaktheit mit der ihr das Wissen praesentiert, sonst gibt es Nach- und Gegenfragen und man verliert Zeit also ein gutes Mittelmasz finden.

Keine geschenkte Pruefung (wie in anderen Faechern) aber machbar. Hohes Niveau aber dafuer sehr wenig (bis kein) (auswendig-)lernen noetig. Das mit dem P=W/t-Prinzip scheint eine Prof. Philippsen Eigenheit zu sein auf die man sich einfach Einstellen muss. Ansonsten nette, entspannte Pruefungsatmosphaere … trotzdem anspruchsvoll und das ist meiner Meinung nach auch gut so.

Wer den Compiler implementiert hat ist selbstverstaendlich klar im Vorteil!