TU Wien:Optimierende Übersetzer VU (Knoop)
Daten[Bearbeiten | Quelltext bearbeiten]
| Vortragende | Jens Knoop |
|---|---|
| ECTS | 3,0 |
| Alias | Optimizing Compilers (en) |
| Letzte Abhaltung | 2023W |
| Sprache | „bei bedarf in englisch“ ist kein zulässiger Sprachcode. |
| Mattermost | optimierende-uebersetzer • Register • Mattermost-Infos |
| Links | tiss:185A04 |
Inhalt[Bearbeiten | Quelltext bearbeiten]
Die LVA behandelt den theoretischen Background zu Programmoptimierungen. Dazu werden zuerst theoretische Grundlagen, wie Verbände ("Lattices") und Datenflussgraphen behandelt. Der Schwerpunkt liegt auf Intra- und Interprozeduraler Datenflussanalyse und Constant Propagation.
Ablauf[Bearbeiten | Quelltext bearbeiten]
Es gibt jede Woche eine eineinhalbstündige Vorlesung in der Complang-Institutsbibliothek. Im WS16/17 hat Hr. Prof. Knoop vor fast jeder Einheit den Foliensatz aktualisiert, weshalb es wichtig ist, auf das Datum im Dateinamen zu achten (es gibt einen "Masterfoliensatz").
Der Übungsteil bestand aus vier Stift und Papier Übungszetteln, für die man jeweils zwei Wochen Zeit hatte (außer für das Erste, wo man nur eine Woche hatte). Abgabe erfolgt in der Vorlesung. Die Übung ist in Gruppen zu ungefähr dritt durchzuführen. Im ersten Übungsblatt ging es um die Grundlagen, nämlich um Hasse-Diagramme von partiellen Ordnungen, wobei man zeigen musste, welche davon Verbände bzw. vollständige Verbände darstellen (Gegenbeispiel oder Beweis). Für das Zweite musste man für gegebene Mengen und Operationen zeigen, ob sie Verbände darstellen, dass Sicherheitstheorem der Datenflussanalyse beweisen und eine DFA (Datenflussanalyse) Spezifikation aufstellen. Das dritte Übungsblatt beschäftigte sich mit Constant Propagation: Beweisskizze für ein Theorem, Funktionsdefinitionen für DFA-Konstantenalayse. Das Letzte war am einfachsten, man musste zu zwei gegebenen Datenflussgraphen die SSA- und Wertegraphen aufstellen, sowie feststellen welche Ausdrücke als Konstanten erkannt werden.
Parallel gab es einen praktischen Übungsteil, in dem man in drei Übungsbeispielen Analysen in SATIrE erstellen musste (Dominator-Analyse, Konstantenpropagation einfach und mit Bedingungen). Für diese Übung gibt es einen Account auf der g0 und sie werden per Mail abgegeben.
Die Übungsblätter bekamen wir verbessert zurück. Ein Feedback Gespräch mit Hr. Moritsch bzgl. der praktischen Beispiele sollte ausgemacht werden, sowie eine Mündliche Prüfung ("Gespräch") mit Prof. Knoop.
Vorkenntnisse[Bearbeiten | Quelltext bearbeiten]
Es wird ein wenig Wissen über Zwischendarstellungen (abstrakte Syntaxbäume, Kontrollflußgraphen) vorausgesetzt, dieses wird etwa in Übersetzerbau vermittelt, aber auch am Anfang der LVA wiederholt.
Die Implementierung von Programmanalysen in der SATIrE-Infrastruktur passiert in der recht mächtigen funktionalen Programmiersprache FULA, Grundwissen über funktionale Programmierung ist daher sehr hilfreich, und eigentlich unbedingt notwendig. Dieses Wissen kann man sich durch vorausgehenden/gleichzeitigen Besuch von Funktionaler Programmierung aneignen, aber auch ein einfaches Web-Tutorial zu einer funktionalen Programmiersprache oder einfach etwas mehr Einarbeitungszeit in die Infrastruktur sollten für eine gute Note ausreichen.
Kenntnisse aus Übersetzerbau oder Wissen über formale Sprachen, Parsing etc. werden nicht benötigt.
Literatur[Bearbeiten | Quelltext bearbeiten]
Es gibt einen Foliensatz auf Englisch, der fast jede Woche aktualisiert wurde. Am Ende umfasste er 1.641 Seiten (nicht alle Kapitel wurden durch genommen). Zudem wurden ein, zwei gedruckte Blätter ausgeteilt. Ein Tutorial zur live variable analysis in SATIrE ist als PDF verfügbar. Die Dokumentation zu SATIrE lässt zu wünschen übrig. Es empfiehlt sich, die Beispiele auf Github im Rose compiler anzusehen (im WS16/17 war sogar eines der Beispiele eins zu eins ein Übungsbeispiel).
Prüfung[Bearbeiten | Quelltext bearbeiten]
WS19/20:
We pretty much talked about all of the material, pretty much in the order it was presented in the lectures. Classical analyses, the intraprocedural DFA framework, constant propagation, PRE, the interprocedural framework and the extension of some analyses to the interprocedural setting.
Some examples of the questions he asked: Which properties ensure termination, conservativity and coincidence for the framework? What is an example of a conservative and non-coincident optimization? What kind of analysis does the sparse code motion rely on, and how does it work? What kind of frameworks are there and how do they differ? Can you extend [some classical analysis] to the interprocedural setting?
Whenever I didn't know something he would gladly explain, and he seemed to notice and appreciate whenever I was quick at understanding his explanations and deriving more information from it. His face also lit up whenever I started talking about the intuition behind some of the mathematics, so that is also a good idea to talk about.
WS16/17: Noch offen.
(vmtl. veraltet:)
Die Prüfung behandelt den gesamten Stoff der Vorlesung, das meiste allerdings eher überblicksmäßig und im "Big Picture". Was aber nicht heißen soll, dass man kein gut sitzendes Verständnis der in der Vorlesung vermittelten Konzepte und deren Anwendung haben muss. Vor allem die klassischen Analysen (Reaching Definition, Available Expression, Live Variables, Very Busy Expressions, ...) sollte man sehr gut beherrschen. Es ist aber definitiv nicht notwendig oder zielführend, sämtliche Formalismen, Formeln und Details dazu auswendig zu lernen.
Typische Prüfungsfragen sind etwa: "Nennen Sie mir irgendeine Analyse und die dazugehörige Transformation.", "Was ist Devirtualisierung und was ist die Voraussetzung dafür?", "Welche Frameworks gibt es und worin unterscheiden sie sich?" oder "Wann kann die maximale Länge eines Callpaths auf Null gesetzt werden?"
Der Vorlesungsbesuch ist sehr empfehlenswert und sollte, zusammen mit ein-, zweimaliger Lektüre des Skriptums und der Folien, ausreichen, um die Prüfung zu bestehen.
WS13/14: Er hat mich gefragt worüber ich erzählen möchte und ich hab ihm natürlich das erzählt, was ich gut konnte. Es ist sicher nicht schlecht sich alles anzusehen, aber ich glaube, dass es reicht wenn man viel über DFAs und CMs weiß und ihm das dann auführlichst erklärt :)
Zeitaufwand[Bearbeiten | Quelltext bearbeiten]
Der Vorlesungsteil bestand im WS16/17 aus ca. 12 Terminen je eineinhalb bis zwei Stunden. Der letzte Termin war in der vorletzten Jänner Woche. Für die vier theoretischen Übungen haben wir jeweils ca. vier Stunden gebraucht (tlw. etwas mehr). Die drei praktischen Übungen waren auch ca. soviel Aufwand und zusätzliche Einarbeitungszeit.
Highlights / Lob[Bearbeiten | Quelltext bearbeiten]
noch offen
Verbesserungsvorschläge / Kritik[Bearbeiten | Quelltext bearbeiten]
noch offen