Compiler Construction

People

General Information

The course treats compiler construction for imperative programming languages. This includes lexical, syntactical, and semantic analysis as well as static program analysis, optimization, and code generation. This course provides all necessary theoretical knowledge required to implement a compiler from scratch, which forms the practical part of the lecture.

All students are asked to register for the exams for the winter semester 2013. Exam registration is possible from now on until November 17th, 2013. A withdrawal is possible two weeks before the first exam at the latest. Most students can use the HISPOS. Students of economy computer science, erasmus students, junior students and to some extent students from other courses of studies must use other systems.

Exams

• Place: E2 2
• Exam: Monday, 2014-02-10, 10–12 (s.t.)
  • Results
  • You can have a look at your exam on Tuesday, 2014-02-18, 14–16 in room 401 in E1 3.
• Re-exam: Tuesday, 2014-02-25, 10–12 (s.t.)
• Results
• You can have a look at your exam on Wednesday, 2014-03-05, 14–16 in room 401 in E1 3.
• You must hand in and present your project before 2014-03-15. The presentation will take about half an hour. Make an appointment for the presentation at least three days in advance with me.
• Final grades

Lecture

Please register for the lecture on this page.

• Type: core lecture (9 credit points)
• Place: lecture hall I (HS 1), building E1 3
• Time: Mondays 14–16 (c.t.) and Wednesdays 12–14 (c.t.)
• First Meeting: Wednesday, 2013-10-16, 12–14 (c.t.)

Tutorial

• Place: lecture hall II (HS 2), building E1 3
• Time: Tuesdays 12–14 (c.t.)
• First Meeting: Tuesday, 2013-10-29, 12–14 (c.t.)

Support

• Use the course's AskBot to communicate with the team and your fellow students.
• We use a GitLab to manage the course project.
• We run nightly tests on your project to provide you with feedback about your progress.

These services are only available from within the university network. You can use a VPN to connect to these services from other locations.

Material

1. The Structure of Compilers
2. Lexical Analysis
3. Grammars
4. Pushdown Automata and Parser
5. Recursive Equations over Grammars
6. LL Parser
7. LR Parser
8. Attribute Grammars
9. Attribute Dependencies
10. Program Analysis
11. Intra-procedural Data Flow Analysis
12. SSA
    • Using SSA in Constant Propagation: Constant Propagation with Conditional Branches
    • Cytron et al.'s dominance frontier technique: Efficiently Computing Static Single Assignment Form and the Control Dependence Graph
    • The libfirm approach to SSA construction: Simple and Efficient Construction of Static Single Assignment Form
    • Slides for the latter: Simple and Efficient Construction of Static Single Assignment Form (Presentation slides)
13. Global Value Numbering (GVN)
    • Killdall's original paper: A Unified Approach to Global Program Optimization
    • The AWZ approach: Detecting Equality of Variables in Programs
14. LLVM-IR
15. Intermediate Representation Construction in a Nutshell
16. Code Generation on Expression Trees
• The paper containing the proof for the NP-hardness of instruction selection: Near-optimal instruction selection on DAGs
17. SSA Register Allocation
18. Instruction Selection on SSA DAGs using PBQP

Note: To download background reading, it may be necessary to be in the university's subnet due to licensing issues of the papers' publishers

Exercises

1. Exercise 1 (corresponding Mini Test 1)
2. Exercise 2 (corresponding Mini Test 2)
3. Exercise 3
4. Exercise 4 (corresponding Mini Test 3)
5. Exercise 5 (reference file for the pretty printer)
6. Exercise 6 (corresponding Mini Test 4)
7. Exercise 7 (corresponding Mini Test 5)
8. Exercise 8
9. Exercise 9 (corresponding Mini Test 6)
10. Exercise 10 (corresponding Mini Test 7)
11. Exercise 11
12. Exercise 12

Project Material

• The final draft of C1X, dated 12 April 2011
• Reference example for the pretty printer
• LLVM-IR construction examples

Modus Operandi

There will be eight voluntary mini tests which will take place in the last 20 minutes within the tutorial. Additionally, there will be voluntary exercises. To get a course certificate, students must pass the final exam and the project. Final grades will be based on the exam and the project.

Literature list

• R. Wilhelm and D. Maurer, "Übersetzerbau"
  Springer; Berlin, 2nd print, 1997. ISBN 3-540-61692-6.
• R. Wilhelm and D. Maurer, "Compiler Design"
  Addison-Wesley; Essex, 2nd print, 1996. ISBN 0-201-42290-5.
• R. Wilhelm and H. Seidl, "Übersetzerbau – Virtuelle Maschinen"
  Springer, Berlin, 1st print, 2007. ISBN 978-3-540-49596-3.
• W. Waite and G. Goos, Compiler Construction