Compiler 2: Fortgeschrittene Themen

Bereich: Computer Microsystems
Fachrichtung: Technische Informatik, Elektrotechnik/Datentechnik
Art: Vorlesung V3
Dozent/Prüfer: Andreas Koch
Betreuer: Jens Huthmann, Julian Oppermann
Voraussetzungen: Grundkenntnisse Compilerbau (aus Compiler 1), 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. Im begleitenden Praktikum Optimierende Compiler wird ein bestehender Compiler für eine objektorientierte Programmiersprache schrittweise um Optimierungen in Java erweitert.

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
• Ausgewählte wissenschaftliche Veröffentlichungen

Credits: 5,0 CP
Zeit: • Dienstags, 16:15-17:55 Uhr
• Donnerstags, 11:40-13:20 Uhr
Ort: S2|02 / C110
Beginn: 15.04.2014

Praktikum: Parallel zur und eng verzahnt mit der Vorlesung wird ein Praktikum angeboten, dessen Besuch dringend empfohlen wird.

Prüfung: Die Prüfung in diesem Semester erfolgt semesterbegleitend in Form einer schriftlichen Abschlussprüfung. Die Klausur findet am 28.07.2014 von 11:30-14:00 Uhr im Hörsaal C205 statt. Hilfsmittel sind keine zugelassen. Bitte stellen Sie in jedem Fall sicher, dass Sie sich, Ihrer Studienordnung entsprechend, rechtzeitig bei der für Sie zuständigen Stelle zur Prüfung angemeldet haben!
Klausurergebnisse/Einsicht: Die vorläufigen Klausurergebnisse sind im TUCaN sichtbar. Die Klausureinsicht findet am 17.09.2014 um 15-17 Uhr in S2|02, Raum E202 statt. Um den Ablauf etwas zu entzerren, tragen Sie sich bitte in die Doodle-Umfrage ein. Sie können gerne ein beliebiges Pseudonym benutzen.

Vorlesungsfolien

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

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 (vorläufig)
Mit Animationen, Farbig, 1-auf-1

5. Block: Redundanzeliminierung (vorläufig)
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
Farbig, 1-auf-1 Mit Animationen, Farbig, 1-auf-1 Zusatzfolien, Mit Animationen, Farbig, 1-auf-1

9. Block: Registerallokation
Mit Animationen, Farbig, 1-auf-1

Aufzeichnungen

Die Folien und der Vortrag werden 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. Falls das von Ihnen verwendete Betriebssystem keinen dafür passenden Codec mitbringt, kann dieser in der Regel problemlos nachinstalliert werden. Für Windows-Varianten könnte dafür bespielsweise die Pakete FFDShow Tryout oder VLC genutzt werden. Unter Linux ist der übliche mplayer direkt in der Lage, die Dateien abzuspielen.

15.04.2014
17.04.2014
22.04.2014
24.04.2014
29.04.2014
06.05.2014
08.05.2014
13.05.2014
15.05.2014
20.05.2014
22.05.2014
27.05.2014
03.06.2014
10.06.2014
17.06.2014
24.06.2014 1. Teil (SSCP, SCCP)
24.06.2014 2. Teil (LLVM), gegen Ende Bild gestört
01.07.2014
08.07.2014
15.07.2014

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

E-path PRE -- Partial Redundancy Elimination Made Easy
DHANAJAY DHAMDHERE
ACM SIGPLAN Notices, 2002, vol. 37, no 8, pp. 53-65, hier korrigierte Fassung Dhananjay Dhamdhere's publications page - use second item

Constant propagation with conditional branches
WEGMAN, ZADECK
ACM TOPLAS, 13(2), April 1991, pp. 181-210 ACM Digital Library

Combining Analyses, Combining Optimizations
CLICK, COOPER
ACM TOPLAS, 17(2), März 1995, pp. 181-196 ACM Digital Library