Fortgeschrittener Compilerbau

Bereich: Robotik, Computational and Computer Engineering
Fachrichtung: Technische Informatik, Elektrotechnik/Datentechnik
Art: Vorlesung V3
Dozent/Prüfer: Andreas Koch
Betreuer: Julian Oppermann, Lukas Sommer
Voraussetzungen: Grundkenntnisse Compilerbau (aus Compiler 1/Einführung Compilerbau), Algorithmen und Datenstrukturen, Java, Rechnerarchitektur (erworben z.B. durch Technische Grundlagen der Informatik)
Inhalt: Die komplizierten Architekturen moderner Prozessoren können in der Praxis nur noch durch den Einsatz hochgradig optimierender Compiler ausgenutzt werden. Innerhalb dieser Compiler hat sich daher stetig die Komplexität von der Erkennung der Quelltexte hin zu deren möglichst effizienter Umsetzung in Maschinen-Code verschoben. In der Lehrveranstaltung geht es um eine praktische Einführung in die dafür benötigten Algorithmen und Datenstrukturen. Vorgestellt werden Analysen und Transformationen dieser Darstellungen mit dem Ziel, optimierten Maschinen-Code zur Ausführung auf modernen Prozessoren zu erhalten. Der behandelte Stoff wird in Übungsblättern, deren Bearbeitung freiwillig ist (keine Abgabe), sowohl in theoretischen als auch praktischen Aufgaben vertieft. Zusätzlich kann das in der Vorlesung erlangte Wissen im begleitenden Praktikum Compilerbau bei der Implementierung von Erweiterungen bestehender Compiler angewendet werden.

Literatur: • Engineering a Compiler von Keith D. Cooper, Linda Torczon (2. Auflage!)
• Advanced Compiler Design and Implementation von Steven S. Muchnick
• Compilers: Principles, Techniques, and Tools (2. Auflage!) von Aho, Lam, Sethi und Ullman
• sowie ausgewählte wissenschaftliche Veröffentlichungen (siehe unten)

Credits: 5,0 CP
Zeit: • Dienstags, 16:15-17:55 Uhr
• Donnerstags, 11:40-13:20 Uhr (nur in der ersten Semesterhälfte)
Ort: S2|02 / C110
Beginn: 10.04.2018

Vorlesungsfolien

1. Block: Übersetzung objektorientierter Sprachen am Beispiel von Bantam
Farbig, 1-auf-1 Mit Animationen, Farbig, 1-auf-1 (erweitert 19.04.2018)

2. Block: Datenflussanalyse
Farbig, 1-auf-1 Mit Animationen, Farbig, 1-auf-1

3. Block: SSA-Form und CFG-SSA Wandlung
Farbig, 1-auf-1 Mit Animationen, Farbig, 1-auf-1

4. Block: Rückwandlung aus der SSA-Form
Farbig, 1-auf-1 Mit Animationen, Farbig, 1-auf-1

5. Block: Redundanzeliminierung
Farbig, 1-auf-1 Mit Animationen, Farbig, 1-auf-1

6. Block: Partielle Redundanz und ihre Eliminierung
Farbig, 1-auf-1 Mit Animationen, Farbig, 1-auf-1

7. Block: Skalare Optimierung
Farbig, 1-auf-1 Mit Animationen, Farbig, 1-auf-1

8. Block: Einführung in LLVM
clang und LLVM-IR, Mit Animationen, Farbig, 1-auf-1
Backend, Mit Animationen, Farbig, 1-auf-1 Backend, Farbig, 1-auf-1

Aufzeichnungen

Die Folien und der Vortrag werden bis auf weiteres aufgezeichnet. Dabei kann es gelegentlich durch die Tücke der Technik zu Störungen oder Ausfällen kommen. Wir bitten diese zu entschuldigen und hoffen, sie in erneuten Durchgängen zu vermeiden. Die Aufzeichungen selbst sind platzsparend im H.264-Format komprimiert. Zum Abspielen empfehlen wir VLC.

10.04.2018
12.04.2018
17.04.2018: Diese Aufzeichnung steht aus technischen Gründen nicht zur Verfügung. Die Informationsfolien zum Praktikum finden sich hier
19.04.2018
24.04.2018
26.04.2018
03.05.2018
08.05.2018
15.05.2018
17.05.2018
22.05.2018
24.05.2018
29.05.2018
05.06.2018 Aufgrund von technischen Problemen fehlen leider die ersten und letzten 2-3 Minuten der Aufzeichnung
07.06.2018
12.06.2018
19.06.2018
26.06.2018 Achtung, Dateigröße 641 MB durch andere Aufnahmetechnik
03.07.2018 Mikroausfall nach 50 min 🤬 / Dateigröße 750 MB
10.07.2018

Ausgewählte wissenschaftliche Veröffentlichungen als Hintergrundmaterial

Single-Pass Generation of Static Single Assignment Form for Structured Languages
MARC M. BRANDIS and HANSPETER MÖSSENBÖCK
ACM Transactions on Programming Languages andS ystems 16(6): 1684-1698, Nov.1994 ACM Digital Library

Practical Improvements to the Construction and Destruction of Static Single Assignment Form
BRIGGS, COOPER, HARVEY, SIMPSON
SOFTWARE PRACTICE AND EXPERIENCE, VOL. 28(8), 1-28 (July 1998) Wiley Online Library

Efficiently computing static single assignment form and the control dependence graph
CYTRON, FERRANTE, ROSEN, WEGMAN, ZADECK
ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 13 , Issue 4 (October 1991) ACM Digital Library

Value Numbering
BRIGGS, COOPER, SIMPSON
SOFTWARE—PRACTICE AND EXPERIENCE, VOL. 27(6), 701-724 (JUNE 1997) Wiley Online Library