Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 2 » Allgemeine Fragen (Übersicht)

Inhaltsverzeichnis

Allgemeine Fragen
Datenfluss Analyse
Aliase
Fazit

Meine Prüfung ist um 8 Uhr aber ich bin zu früh da. Wir fangen 15 Minuten früher an.

P Professor (Dr. Michael Philippsen)
B Beisitzer (Tobias Heineken)
S Student (Ich)

P Das ist ja unüblich, dass sich jemand um 8 Uhr Einträgt?

Allgemeine Fragen

B Was haben wir so in Übersetzerbau 2 gemacht?
S Wir haben versucht ein Programme unter invarianter Semantik zu optimieren
B Was würde das zum Beispiel heißen?
S /Wenn wir toten Code haben, würden wir dieses entfernen wollen wir dieses entfernen (Binarysize). Ein anderes Beispiel wäre es die doppelte Berechnung von Ausrücken zu vermeiden (Laufzeit)./
B Welche Konstrukte interessieren uns bei der Optimierung sehr?
S Ich zögere weil ich jetzt noch nicht darauf hinaus will, aber sage Schleifen.

Datenfluss Analyse

<HTML><dl></HTML> <HTML><dt></HTML>B<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Schauen wir uns ein Beispiel an. Mir wird e2-Code für die Ackermann-Funktion gegeben. (Hier kopiert aus der Vorlage)<HTML></HTML>

func ackermann(m : int, n : int): int
  var a : int;
 
  if m == 0 then
return n + 1;
  end
  if n == 0 then
return ackermann(m - 1, 1);
  end
  a := ackermann(m, n - 1);
  return ackermann(m - 1, a);
end

<HTML></dd></HTML> <HTML><dt></HTML>B<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Nehmen wir an, die Architektur hat ein Problem damit größere Zahlen von kleineren zu Subtrahieren (d.h. wo negative Werte herauskommen) Was könnten wir hier hinsichtlich dieses Problems machen?<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>S<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Wir könnten eine statische Analyse machen, um zu prüfen ob eine problematische Subtraktion stattfindet.<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>B<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Mir wird der IR Code für die obige Funktion gegeben. /Ich habe den Code hier bereits etwas optimiert, damit es auf die Seite passt. Wie würden Sie hier vorgehen/ Im Nachhinein bemerke ich die Optimierung hat bei den ersten zwei Fällen eine Enterkursivierung durchgeführt.<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>S<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>/Wir könnten eine Datenfluss Analyse durchführen, und statisch die möglichen Werte von allen Variablen mit-merken. Dazu brauchen wir den Kontrollflussgraphen, welcher aufgespannt wird durch die Knoten und den möglichen Sprüngen zwischen den Maximalen Grundblöcken./<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>B<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Mir wird der KFG vorgelegt. Hier ist der KFG für den IR Code von oben. Wie würden sie hier vorgehen? Hier ist eine Skizze, ohne Code:<HTML></HTML>

ENTRY
  |
  v
  B1
 /  \
 v   v
 B2  B3 <---
 |   ^ \    \
 |   |  \   |
 |   |  v   |
 |   |  B5  |
 |   | /  \ | 
 |   |v    vv
 |   B4    B6
 v
 EXIT

<HTML></dd></HTML> <HTML><dt></HTML>S<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>/Für DFA müssen wir ein Halbverbund definieren auf einer Trägermenge. Wir werden in diesem Fall wahrscheinlich über den KFG von vorne nach oben nach unten durchlaufen, und mögliche Werte in einer Art Map-Datenstruktur mitgespeichert, welche wir je nach Anweisungen anpassen./<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>B<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Mir wird eine Teilordnung vorgelegt, ähnlich zu den Richtungsvektoren bei den Schleifen:<HTML></HTML>

    *
   / \
  ≤   ≥
 / \ / \
<   =   >

<HTML></HTML>/Lasst und hier lieber diese Werte anstatt einer Wertemenge. Wie würden sie damit vorgehen? Nehmen Sie an, dass es sicher sei alle Parameter sind größer gleich 0./<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>S<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>In dem Fall können wir den Anfangsknoten auf eine Menge wie {n:≥, m:≥} für die Beiden Parameter Ich vergesse hier zu erwähnen, dass alle Knoten vor-initialisiert sein müssen. Wir laufen dann weiter zu dem zweiten (B3).<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>P<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Der Konten hat ja zwei Eingänge, was macht man damit?<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>S<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Ich vergesse weiterhin, dass alle Konten vorinitialisieren werden müssen, tue so als wäre es kein Problem und mache erst mal weiter (fatal). Wir joinen (⊔) ja alle Vorgänger, und gerade wurde nur einer Definiert Ich gehe die Anweisungen in B1 durch, und komme zu einem Sprung.<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>B<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Hier kann man ja was machen<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>S<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>/Ja, wir können ja hier das bisherige Wissen anpassen, je nachdem welchem Kontrollfluss wir verfolgen. Nach jne n$0, 0, L1 wissen wir, dass wir das Wissen im Block mit L1 auf {n:>, m:≥} Aktualisieren./<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>P<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Arbeiten Sie sich in die Richtung von dem B6 Grundblock.<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>S<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Nach dem gleichen Prinzip kann man aus jne m$0, 0, L3 auch m entsprechend anpassen. In B6 haben wir zwei Subtraktionen um 1. Wir wissen, dass diese Sicher sind, weil der Wert statisch garantiert strikt größer als 0 sind.<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>P<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Und was passiert wenn sie dieses wissen dann weiter propagieren zu dem Grundblock B3?<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>S<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Wir joinen?<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>P<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Er will darauf hinaus, dass ich vergessen habe die Knoten zu initialisieren, und das in der Teilordnung oben noch ein ⊥ Element fehlt (kein Wissen ist Vorhanden).<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>B<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Lasst uns nochmal auf das Thema von vorhin zurückgehen, wie kann man hier schleifen erkennen?<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>S<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Bevor wir Schleifen erkennen können, müssen wir Dominanz bestimmen?<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>B<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Dominanz, was ist das?<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>S<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Wenn ein Konten A ein Konten B dominiert, dann muss jeder Kontrollfluss von dem Entry-Konten zu B durch A durchfließen.<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>B<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Wie berechnen wir das?<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>S<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Wir hatten dazu zwei Algorithmen besprochen, das Erste was eine weitere DFA, der zweite hieß „Lengauer–Tarjan“<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>B<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Lengauer-Tarjan wäre jetzt zu Zeitaufwendig. Mir wird ein Blatt mit dem Dominatorbaum gegeben. Was ist das und wie kommt man darauf?<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>S<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>/Der Dominantorbaum wird durch die „Immediate Dominators“ aufgespamnnt. Ein Immediate Dominator, ist immer der nahe-liegenste Dominator im KFG./<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>B<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Wie können wir damit Schleifen erkennen?<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>S<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>/Aus dem Dominatorbaum können wir die wichtigen Regionen ablesen, und dieses gibt uns ein Hinweis darauf, welche Rück-Kanten natürliche Schleifen bestimmen könnten. So ist B3, B5, B6 ein Kandidat./<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>B<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Und wie können wir uns sicher sein, dass es wirklich eine natürliche Schleife ist?<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>S<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Ich zeichne die T1 und T2 Kriterien hin, aber vergessen bei der o -> o Regel explizit zu erwähnen, dass es nur die eine Kante geben darf.<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>P<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Aber dann kann ja alles reduziert werden?<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>S<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Nein, weil es nur die eine Kante gibt.<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>P<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Aber das haben sie nicht gesagt! Er erwähnt auch, dass es noch eine Schleife gibt, welche aber auch offensichtlich ist und ich sofort erwähne.<HTML></HTML> <HTML></HTML>Gut, es ist schon ⅔ der Zeit vergangen!<HTML></HTML><HTML></dd></HTML><HTML></dl></HTML>

Aliase

<HTML><dl></HTML> <HTML><dt></HTML>B<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Zu einem anderem Thema. Mir wird ein Code-Stück vorgelegt in C, weil wir dazu C brauchen.<HTML></HTML>

void foo(int **pptr, int *ptr, int val) {
 *pptr = ptr;
 *ptr = val;
}
 
int main() {
 int pi = 3;
 int *piptr = &pi;
 int *other;
 
 foo(&other, piptr, 4);
 if (piptr == other) {
      return 3;
 }
 
 if (pi == 3) {
      return 2;
 }
 
 return 1;
}

<HTML></HTML>Wieso interessiert uns hier Alias-Analyse? Wieso bereiten uns Aliase ein Problem?<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>S<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Weil Aliase das Optimieren von Programmen unter invarianter Semantik erschweren.<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>B<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Was wäre hier ein Beispiel?<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>S<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>/Wir könnten in diesem Beispiel, Toten Code entfernen, wenn wir wissen würden, dass piptr == other gelten muss. Dazu brauchen wir eine MUST-Analyse/<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>P<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Was für Kategorien bei der Analyse gibt es denn alles?<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>S<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Ich Fange an Inter- bzw. Intraprozedural, Flussin- bzw. Sensitiv, etc. aufzuzählen.<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>P<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Was davon würde uns in diesem Fall interessieren?<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>S<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Hier stellt der Aufruf von foo ein Problem dar. Wir brauchen also eine Interprozedurale Analyse?<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>B<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Was ist mit dem zweiten Fall? Kann das optimiert werden?<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>S<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Ja, wenn wir mit einer MAY-Analyse ausschließen können, dass pi nicht via Aliasen verändert wurde.<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>B<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Welche Algorithmen haben wir also kennengelernt, die hier helfen können?<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>S<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>/Da Muchnick Interprozedural ist, ist es hier nicht besonders hilfreich. Wir brauchen also Steensgaard, weil das ist Interprozedural./<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>B<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Können Sie das also machen?<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>S<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Ich mache Steensgard, verschmelze aber die Knoten nicht sofort, sondern auf meiner eigenen Initiative hin, aber eben zu spät (fatal).<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>P<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Wofür steht jeder Konten<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>S<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Speicher?<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>P<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Ist unzufrieden.<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>P<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Wie können sie darauf ablesen, ob es ein MAY-Alias gibt.<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>S<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Ich zögere, aber mit eine kleinen Hinweis komme ich darauf, dass es ein MAY-Alias geben kann, wenn in einem Konten zwei Speicherstellen liegen.<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>P<HTML></dt></HTML> <HTML><dd></HTML><HTML></HTML>Wofür steht also jeder Konten?<HTML></HTML><HTML></dd></HTML> <HTML><dt></HTML>S<HTML></dt></HTML> <HTML><dd></HTML>Für eine Menge von Speicherstellen!<HTML></dd></HTML><HTML></dl></HTML>

Fazit

Die Prüfung ist vorbei, ich warte vor dem Zimmer. Nach einer kurzen Weihe werde ich wieder hinein gebeten, und gefragt was für eine Note ich glaube bekommen zu haben.

S Also ich bin nicht so zufrieden, es musste ja genug eingehakt werden. Was passiert wenn ich nichts sage?
P Dann müssen wir uns mehr Mühe machen ihnen die Note zu Erklären.
S Gut, dann glaube ich eine 2.0 oder Schlechter zu haben.
P Wir haben zwischen einer 1.3 und einer 1.7 diskutiert. Er geht darauf hinaus dass ich alle konkreten Fragen sehr gut beantwortet habe, aber bei den Aufgaben habe ich öfters Fehler gemacht (siehe oben mit „fatal“ markiert). Daher ist es keine 1.0, aber wir beschließen uns eine 1.3 zu vergeben.
S Ich bedanke mich, Vielen Dank, wir reden noch kurz über „Denotational Semantics“ und ich verlasse das Zimmer um 8:17.