Bereich

Computer Microsystems

Fachrichtung

Technische Informatik, Elektrotechnik/Datentechnik

Art

IV4 oder V3 (siehe unten)

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. In einem begleitenden Programmierprojekt wird ein bestehender Compiler in Java schrittweise erweitert.

Literatur

• Programming Language Processors in Java von David Watt und Deryck Brown
• Engineering a Compiler von Keith D. Cooper, Linda Torczon
• 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

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

S2|02 / C110

Beginn

14.04.2009

Anmeldung

Für diese Veranstaltung ist eine Anmeldung bis zum 28.04.2009, über das WebReg System unbedingt erforderlich.

Prüfung

Die Prüfung erfolgt vorlesungsbegleitend in Form von zwei Teilprüfungen (V3) bzw. einer Teilprüfung und dem benoteten Programmierprojekt (IV4). Ob die Teilprüfungen mündlich oder schriftlich durchgeführt werden, hängt von der Anzahl der Interessenten ab. Der genau Prüfungsmodus wird in jedem Fall rechtzeitig innerhalb der Anmeldungsfrist bekanntgegeben. 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!

Folien und Aufzeichnungen der Vorlesungen

In diesem Jahr werden das erste Mal die Folien und der Vortrag aufgezeichnet. Bei dieser Premiere kann es gelegentlich durch die Tücke der Technik noch 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 das Paket FFDShow Tryout genutzt werden. Unter Linux ist der übliche mplayer direkt in der Lage, die Dateien abzuspielen.

1. Block: Einleitung, Beschreibung von Programmiersprachen
Farbig, 1-auf-1 Mit Animationen, Farbig, 1-auf-1
Aufzeichnung 1.Teil (40 MB) Aufzeichnung 2. Teil (41 MB)

2. Block: Kompilierungsablauf und Syntaktische Analyse
Farbig, 1-auf-1 Mit Animationen, Farbig, 1-auf-1
Aufzeichnung 1.Teil (40 MB) Aufzeichnung 2. Teil (34 MB)

3. Block: Kontextanalyse
Farbig, 1-auf-1 Mit Animationen, Farbig, 1-auf-1
Aufzeichnung 1.Teil (40 MB*) Aufzeichnung 2.Teil (24 MB)

4. Block: Kontrollflussgraphen und SSA-Form
Farbig, 1-auf-1 Mit Animationen, Farbig, 1-auf-1
Aufzeichnung (61 MB*)

5. Block: Datenflußanalyse
Farbig, 1-auf-1 Mit Animationen, Farbig, 1-auf-1
Aufzeichnung 1.Teil (40 MB) Aufzeichnung 3.Teil (9 MB)
Der 2. Teil der Aufzeichnung steht leider nicht zur Verfügung.

6. Block: Rückwandlung aus der SSA-Form
Farbig, 1-auf-1 Mit Animationen, Farbig, 1-auf-1
Aufzeichnung (39 MB)

7. Block: Optimierung und Redundanzeliminierung
Farbig, 1-auf-1 Mit Animationen, Farbig, 1-auf-1
Aufzeichnung (59 MB)

8. Block: Skalare Optimierung
Farbig, 1-auf-1 Mit Animationen, Farbig, 1-auf-1
Aufzeichnung (28 MB)

9. Block: Laufzeitumgebung
Farbig, 1-auf-1 Mit Animationen, Farbig, 1-auf-1
Aufzeichnung (70 MB)

10. Block: Code-Generierung
Farbig, 1-auf-1 Mit Animationen, Farbig, 1-auf-1
Aufzeichnung (67 MB)

11. Block: Partielle Redundanzeliminierung (nun vollständig)
Farbig, 1-auf-1 Mit Animationen, Farbig, 1-auf-1
Aufzeichnung (76 MB*)

Die mit * markierten Aufzeichnungen haben leider ganz oder teilweise eine sehr schlechte Tonqualität.

Aufgaben für praktische Programmierarbeiten

1. Aufgabe: Interaktive AST-Analyse und Sprachbeschränkung

2. Aufgabe: Erzeugen von SSA-CFGs aus DAST

3. Aufgabe: Rückwandlung von SSA-CFG nach DAST (verfeinert!)

4. Aufgabe: Optimierung mittels DVNT und DCE

An die vier Pflichtaufgaben schliesst sich eine optionale Verbesserungsphase an, in der die Kommentare aus dem letzten Kolloquium noch berücksichtigt werden können. Hier könnten Sie auch weitergehende Optimierungen für eine potenzielle Notenverbesserung realisieren. Aber Obacht: Es ist besser, einen vollständig funktionierenden Compiler zu entwickeln, der nicht alle Optimierungen beherrscht, als einen, der zwar jede Menge Optimierungen kann, aber die Programme verhackstückt!

Materialsammlung für praktische Arbeiten

Quellen des Triangle-Compilers und Beispielprogramme
Unterstützt den vollen Triangle-Sprachumfang, erweitert um Dateioperationen und höhere Speichergrenzen.

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