185.A04 Optimizing Compilers
This course is in all assigned curricula part of the STEOP.
This course is in at least 1 assigned curriculum part of the STEOP.

2019W, VU, 2.0h, 3.0EC, to be held in blocked form

Properties

  • Semester hours: 2.0
  • Credits: 3.0
  • Type: VU Lecture and Exercise

Learning outcomes

After successful completion of the course, students are able to (among others)

  • explain, assess, and illustrate by means of typically practically relevant program analyses and transformations of optimizing compilation the basic principles and concepts of optimizing compilation, their theoretical foundations, mathematical basis, and of methods for its empirical and formal proof of correctness, completeness and optimality.
  • transfer and apply these principles and concepts to new tasks of optimizing compilation and to explain the chosen proceeding factually and professionally.
  • evaluate and contrast the chances and limitations of optimizing compilation in the tension triangle of decidability, scalability and efficacy as a whole, on the level of analysis and optimization problems, and of concrete analysis and optimization procedures, and to derive conclusions from that for application programming in general.

Subject of course

The course is concerned with the theory and practice of program
analysis and optimization, which is an essential field of research in
the area of programming languages and compilers. The course stretches
from the theoretical foundations to practical applications and the
automatic generation of program analyses and
optimizations. Theoretical and practical assignments as part of the
tutorial offer the opportunity to independently apply and practice
various analysis and optimization techniques, to prove properties they
meet, and to gain hands-on experience of the SATIrE tool used for
practical assignments. SATIrE integrates various tools for the
analysis and optimization of object-oriented languages, among these
the Program Analyzer Generator (PAG).

Part I: Introduction

  • Motivation
  • Classical Gen/Kill data flow analyses

Part II: Intraprocedural Data Flow Analysis

  • Intraprocedural data flow analysis framework
  • Gen/Kill data flow analyses revisited
  • Constant propagation and folding
  • Partial redundancy elimination (PRE)
  • PRE: Busy code motion
  • PRE: Lazy code motion
  • PRE: Sparse code motion
  • PRE: Summary, looking ahead

Part III: Interprocedural Data Flow Analysis

  • Foundations
  • Interprocedural data flow analysis framework
  • The functional approach
  • The context information approach
  • Applications

Part IV: Extensions, other Settings

  • Alias and heap analyses
  • Optimizations for object-oriented languages

Part V: Conclusions

  • Summary, looking ahead

References

Appendices

  • Mathematical foundations
  • Flow graphs, pragmatics of representation
  • Implementing busy and lazy code motion
  • Lazy strength reduction

Selected Reading Recommendations

  • Flemming Nielson, Hanne Riis Nielson, Chris Hankin. Principles of Program Analysis. Springer-V., 2nd edition, 452 pages, ISBN 3-540-65410-0, 2005.
  • Y. N. Srikant, Priti Shankar. The Compiler Design Handbook: Optimizations & Machine Code Generation. CRC Press, 1st edition, 928 pages ISBN 084931240X, 2002. 
  • Keith D. Cooper, Linda Torczon. Engineering a Compiler. Morgan Kaufmann, 801 pages, ISBN 155860698X, 2003. 
  • Steven S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann, 856 pages, ISBN 1558603204, 1997.

Teaching methods

  • Guided self-dependent learning and practicing: guided by means of lecture and flipped classroom sessions, the self-dependent learning and practicing of the competencies described in the learning outcomes utilizing lecture notes, theoretical and practical exercises, and further self-reliantly chosen material from text books, tutorials, and scientific articles proposed for further reading.
  • Role model and feedback-oriented learning: Presenting, explaining, comparing, contrasting, and rating own and others solutions of assignments in tutor-guided tutorials.
  • Self-assessment tests: Tests supporting the regular self-assessment and self-reflection of one's own previous progress and success of learning.

Mode of examination

Immanent

Additional information

ECTS Break Down:

The course is assigned 3.0 ECTS points. This corresponds to an average
workload of 75 hours. This average workload is divided among the
various learning activities of the course as follows (the description Part I to Part V refers to Part I to Part V of the course notes):

  • Guided learning activities (17.25h)
    • Lecture: 9.0h (12 units * 0.75h)
    • Flipped classroom: 5.25h (7 units * 0.75h)
    • Tutorials: 3.0h (4 units * 0.75h)
  • Independent learning activities (57.25h)
    • Self-dependent acquirement of learning outcomes: 30.0h (Proposal: Part I/4.0h, Part II/12.0h, Part III/9.0h, Part IV/4.0h, Part V/1.0h)
    • In particular: Solving assignments: 24.0h (Proposal: 8 Assignments * 3.0h)
    • Preparation for the oral exam: 3.25h
  • Oral exam: 0.5h

The course starts with a preliminary course meeting and the first lecture
on Tuesday, 1 October 2019, 3.15 - 4.45 pm, in "Hörsaal GM7
Kleiner Schiffbau", Bauteil BD Hoftrakt (1st Floor), Room number BD01B41,
Getreidemarkt 9.

Lecturers

Institute

Course dates

DayTimeDateLocationDescription
Tue15:00 - 17:0001.10.2019 - 21.01.2020Kleiner Schiffbau LVA 185.A04 Optimizing Compilers
Optimizing Compilers - Single appointments
DayDateTimeLocationDescription
Tue01.10.201915:00 - 17:00Kleiner Schiffbau LVA 185.A04 Optimizing Compilers
Tue08.10.201915:00 - 17:00Kleiner Schiffbau LVA 185.A04 Optimizing Compilers
Tue15.10.201915:00 - 17:00Kleiner Schiffbau LVA 185.A04 Optimizing Compilers
Tue22.10.201915:00 - 17:00Kleiner Schiffbau LVA 185.A04 Optimizing Compilers
Tue29.10.201915:00 - 17:00Kleiner Schiffbau LVA 185.A04 Optimizing Compilers
Tue05.11.201915:00 - 17:00Kleiner Schiffbau LVA 185.A04 Optimizing Compilers
Tue12.11.201915:00 - 17:00Kleiner Schiffbau LVA 185.A04 Optimizing Compilers
Tue19.11.201915:00 - 17:00Kleiner Schiffbau LVA 185.A04 Optimizing Compilers
Tue26.11.201915:00 - 17:00Kleiner Schiffbau LVA 185.A04 Optimizing Compilers
Tue03.12.201915:00 - 17:00Kleiner Schiffbau LVA 185.A04 Optimizing Compilers
Tue10.12.201915:00 - 17:00Kleiner Schiffbau LVA 185.A04 Optimizing Compilers
Tue17.12.201915:00 - 17:00Kleiner Schiffbau LVA 185.A04 Optimizing Compilers
Tue07.01.202015:00 - 17:00Kleiner Schiffbau LVA 185.A04 Optimizing Compilers
Tue14.01.202015:00 - 17:00Kleiner Schiffbau LVA 185.A04 Optimizing Compilers
Tue21.01.202015:00 - 17:00Kleiner Schiffbau LVA 185.A04 Optimizing Compilers
Course is held blocked

Examination modalities

  • Eight rated deliveries of theoretical and practical assignments.
  • One rated 30 minute oral examination.

Course registration

Begin End Deregistration end
01.09.2019 01:00 11.10.2019 12:00 31.10.2019 12:00

Group Registration

GroupRegistration FromTo
Optimierende Übersetzer 107.10.2019 12:0018.10.2019 12:00
Optimierende Übersetzer 207.10.2019 12:0018.10.2019 12:00
Optimierende Übersetzer 307.10.2019 12:0018.10.2019 12:00
Optimierende Übersetzer 407.10.2019 12:0018.10.2019 12:00
Optimierende Übersetzer 507.10.2019 12:0018.10.2019 12:00
Optimierende Übersetzer 607.10.2019 12:0018.10.2019 12:00
Optimierende Übersetzer 707.10.2019 12:0018.10.2019 12:00
Optimierende Übersetzer 807.10.2019 12:0018.10.2019 12:00
Optimierende Übersetzer 907.10.2019 12:0018.10.2019 12:00
Optimierende Übersetzer 1007.10.2019 12:0018.10.2019 12:00
Optimierende Übersetzer 1107.10.2019 12:0018.10.2019 12:00
Optimierende Übersetzer 1207.10.2019 12:0018.10.2019 12:00
Optimierende Übersetzer 1307.10.2019 12:0018.10.2019 12:00
Optimierende Übersetzer 1407.10.2019 12:0018.10.2019 12:00
Optimierende Übersetzer 1507.10.2019 12:0018.10.2019 12:00
Optimierende Übersetzer 1607.10.2019 12:0018.10.2019 12:00
Optimierende Übersetzer 1707.10.2019 12:0018.10.2019 12:00
Optimierende Übersetzer 1807.10.2019 12:0018.10.2019 12:00
Optimierende Übersetzer 1907.10.2019 12:0018.10.2019 12:00
Optimierende Übersetzer 2007.10.2019 12:0018.10.2019 12:00

Curricula

Literature

No lecture notes are available.

Previous knowledge

The course extends the course 185.A48 Compiler Construction and
complements the courses 185.274 Advanced Compiler Construction and
185.276 Analysis and Verification. The course is thus especially
recommended for students who would like to focus on the field of
programming languages and compilers, and plan to work on a project or
to write a seminar or master's thesis in this field.

Preceding courses

Accompanying courses

Continuative courses

Miscellaneous

Language

German