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.

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

Properties

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

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
    • Busy code motion
    • Lazy code motion
    • Sparse code motion
    • 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

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, central and control questions supporting the regular self-assessment and self-reflection of one's own previous progress and success of learning.

Mode of examination

Immanent

Additional information

The course is planned as in-person activity. In case of anew restrictions due to the pandemic or energy shortage, the course will be changed to an online mode. 

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.5h)
    • Lecture: 12.0h (12 units * 1.0h)
    • Flipped classroom: 3.0h (6 units * 0.5h)
    • Tutorials: 2.5h (5 units * 0.5h)
  • Independent learning activities (Home universitying, 57.0h)
    • Self-dependent acquirement of learning outcomes: 35.0h (Proposal: Part I/4.0h, Part II/12.0h, Part III/12.0h, Part IV/6.0h, Part V/1.0h)
    • In particular: Solving assignments: 20.0h (Proposal: 4 Assignments * 2.0h + 4 Assignments * 3.0h)
    • Preparation for the oral exam: 2.0h
  • Oral exam: 0.5h

The course starts with a preliminary course meeting and the first lecture on Tuesday, 4 October 2022, 4.15pm-5.45pm, EI 6 Eckert HS.

Lecturers

Institute

Course dates

DayTimeDateLocationDescription
Tue16:00 - 18:0004.10.2022 - 24.01.2023EI 6 Eckert HS 185.A04 Optimizing Compilers
Optimizing Compilers - Single appointments
DayDateTimeLocationDescription
Tue04.10.202216:00 - 18:00EI 6 Eckert HS 185.A04 Optimizing Compilers
Tue11.10.202216:00 - 18:00EI 6 Eckert HS 185.A04 Optimizing Compilers
Tue18.10.202216:00 - 18:00EI 6 Eckert HS 185.A04 Optimizing Compilers
Tue25.10.202216:00 - 18:00EI 6 Eckert HS 185.A04 Optimizing Compilers
Tue08.11.202216:00 - 18:00EI 6 Eckert HS 185.A04 Optimizing Compilers
Tue22.11.202216:00 - 18:00EI 6 Eckert HS 185.A04 Optimizing Compilers
Tue29.11.202216:00 - 18:00EI 6 Eckert HS 185.A04 Optimizing Compilers
Tue06.12.202216:00 - 18:00EI 6 Eckert HS 185.A04 Optimizing Compilers
Tue13.12.202216:00 - 18:00EI 6 Eckert HS 185.A04 Optimizing Compilers
Tue20.12.202216:00 - 18:00EI 6 Eckert HS 185.A04 Optimizing Compilers
Tue10.01.202316:00 - 18:00EI 6 Eckert HS 185.A04 Optimizing Compilers
Tue17.01.202316:00 - 18:00EI 6 Eckert HS 185.A04 Optimizing Compilers
Tue24.01.202316:00 - 18:00EI 6 Eckert HS 185.A04 Optimizing Compilers
Course is held blocked

Examination modalities

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

There are no further rated assessments.

Detailed information on the assessment procedures and modalities are given
in the notes of the preliminary course meeting (cf. TUWEL).

Course registration

Begin End Deregistration end
26.08.2022 01:00 07.10.2022 12:00 28.10.2022 12:00

Group Registration

GroupRegistration FromTo
Optimierende Übersetzer 103.10.2022 12:0014.10.2022 12:00
Optimierende Übersetzer 203.10.2022 12:0014.10.2022 12:00
Optimierende Übersetzer 303.10.2022 12:0014.10.2022 12:00
Optimierende Übersetzer 403.10.2022 12:0014.10.2022 12:00
Optimierende Übersetzer 503.10.2022 12:0014.10.2022 12:00
Optimierende Übersetzer 603.10.2022 12:0014.10.2022 12:00
Optimierende Übersetzer 703.10.2022 12:0014.10.2022 12:00
Optimierende Übersetzer 803.10.2022 12:0014.10.2022 12:00
Optimierende Übersetzer 903.10.2022 12:0014.10.2022 12:00
Optimierende Übersetzer 1003.10.2022 12:0014.10.2022 12:00
Optimierende Übersetzer 1103.10.2022 12:0014.10.2022 12:00
Optimierende Übersetzer 1203.10.2022 12:0014.10.2022 12:00
Optimierende Übersetzer 1303.10.2022 12:0014.10.2022 12:00
Optimierende Übersetzer 1403.10.2022 12:0014.10.2022 12:00
Optimierende Übersetzer 1503.10.2022 12:0014.10.2022 12:00
Optimierende Übersetzer 1603.10.2022 12:0014.10.2022 12:00
Optimierende Übersetzer 1703.10.2022 12:0014.10.2022 12:00
Optimierende Übersetzer 1803.10.2022 12:0014.10.2022 12:00
Optimierende Übersetzer 1903.10.2022 12:0014.10.2022 12:00
Optimierende Übersetzer 2003.10.2022 12:0014.10.2022 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

Language

if required in English