Optimierende Compiler
- Bereich
- Computer Microsystems
- Fachrichtung
- Technische Informatik, Elektrotechnik/Datentechnik
- Art
- IV4
- Dozent
- Andreas Koch
- Voraussetzungen
- Grundkenntnisse Algorithmen und Datenstrukturen, Java, Rechnerarchitektur (erworben z.B. durch Technische Grundlagen der Informatik II)
- 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. Nach einem Überblick über fundamentale Techniken wie Lexing und Parsing werden abstrakte Syntaxbäume und andere Zwischendarstellungen vorgestellt. Im Anschluss geht es dann um Analyse und Transformation dieser Darstellungen mit dem Ziel, optimierten Maschinen-Code zur Ausführung auf modernen Prozessoren zu erhalten.
- Literatur
- • Programming Language Processors in Java von David Watt und Deryck Brown
• Engineering a Compiler von Keith D. Cooper, Linda Torcson
• Advanced Compiler Design and Implementation von Steven S. Muchnick
• Modern Compiler Implementation in Java von Andrew W. Appel, Jens Palsberg
• Ausgewählte wissenschaftliche Veröffentlichungen
- Credits
- 6.0 CP bei Teilnahme auch am praktischen Teil (Aufgaben, Kolloquien, Vorträge), 4.5 CP bei Beschränkung auf die Vorlesung
- Zeit
- • Dienstags, 16:15-17:55 Uhr
• Donnerstags, 11:40-13:20 Uhr - Ort
- • Dienstags S2|02/C110
• Donnerstags S2|02/C120 - Beginn
- 20.04.2006
- Anmeldung
- Anmeldung: Für diese Veranstaltung ist eine Anmeldung bis zum 17.4.2006, 18:00 Uhr, über das WebReg System unbedingt erforderlich.
- Klausuren
- Beide der vorlesungsbegleitenden Klausuren werden in S2|02/C205 geschrieben. Die erste am Montag, dem 19.6.2006, von 18:15 - 19:30 Uhr, die zweite am Mittwoch, dem 26.7.2006 von 14:00-15:15 Uhr. Bitte stellen Sie sicher, dass Sie sich, ihrer Studienordnung entsprechend, rechtzeitig bei der für Sie zuständigen Stelle zur Prüfung angemeldet haben!
Vorlesungsfolien
1. Block: Einleitung, Beschreibung von ProgrammiersprachenFarbig, 1-auf-1 Mit Animationen, Farbig, 1-auf-1
2. Block: Kompilierungsablauf und Syntaktische Analyse
Farbig, 1-auf-1 Mit Animationen, Farbig, 1-auf-1
3. Block: Kontextanalyse
Farbig, 1-auf-1 Mit Animationen, Farbig, 1-auf-1
4. Block: Laufzeitumgebung
Farbig, 1-auf-1 Mit Animationen, Farbig, 1-auf-1
5. Block: Code-Generierung
Farbig, 1-auf-1 Mit Animationen, Farbig, 1-auf-1
6. Block: Optimierung durch Redundanzeliminierung (aktualisiert)
Farbig, 1-auf-1 Mit Animationen, Farbig, 1-auf-1
7. Block: SSA-Form (ergänzt um Rücktransformation)
Farbig, 1-auf-1 Mit Animationen, Farbig, 1-auf-1
8. Block: Datenflußanalyse (korrigiert)
Farbig, 1-auf-1 Mit Animationen, Farbig, 1-auf-1
9. Block: Skalare Optimierung
Farbig, 1-auf-1 Mit Animationen, Farbig, 1-auf-1
Aufgaben für praktische Programmierarbeiten
1. Aufgabe: Programmierung in Triangle2. Aufgabe: Interaktive AST-Analyse und -Transformation
3. Aufgabe: Erzeugen eines CFGs in SSA-Form
4. Aufgabe: DVNT-Optimierung auf SSA-CFG und Rückwandlung in AST
5. Aufgabe: (Optional) Aufräumungsarbeiten
Materialsammlung für praktische Arbeiten
Quellen des Triangle-Compilers und Beispielprogramme (Urversion)Quellen des Triangle-Compilers und Beispielprogramme (mit Dateioperationen und höheren Speichergrenzen)
Eingabedateien für Tests
Beispielprogramme aus der 1. AbgabeAusgewählte wissenschaftliche Veröffentlichungen als Hintergrundmaterial
Single-Pass Generation of Static Single Assignment Form for Structured LanguagesMARC 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