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.

2021W, 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: Distance Learning

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

The course is run in a plain online mode.

  • 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

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 (exclusively online, 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 (exclusively online, Videocall): 0.5h

The course starts with a preliminary course meeting and the first lecture on Monday, 4 October 2021, 3.15pm-5.00pm (inclusive of a 15 minutes break), exclusively online in the form of a video conference. The access information for joining the video conference will be provided on time in the TUWEL course of the course.

Lecturers

Institute

Examination modalities

  • Online/offline, not onsite:Eight rated deliveries of theoretical and practical assignments.
  • Online, videocall: 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. homepage of the course).

Course registration

Begin End Deregistration end
01.09.2021 01:00 08.10.2021 12:00 29.10.2021 12:00

Group Registration

GroupRegistration FromTo
Optimierende Übersetzer 104.10.2021 12:0015.10.2021 12:00
Optimierende Übersetzer 204.10.2021 12:0015.10.2021 12:00
Optimierende Übersetzer 304.10.2021 12:0015.10.2021 12:00
Optimierende Übersetzer 404.10.2021 12:0015.10.2021 12:00
Optimierende Übersetzer 504.10.2021 12:0015.10.2021 12:00
Optimierende Übersetzer 604.10.2021 12:0015.10.2021 12:00
Optimierende Übersetzer 704.10.2021 12:0015.10.2021 12:00
Optimierende Übersetzer 804.10.2021 12:0015.10.2021 12:00
Optimierende Übersetzer 904.10.2021 12:0015.10.2021 12:00
Optimierende Übersetzer 1004.10.2021 12:0015.10.2021 12:00
Optimierende Übersetzer 1104.10.2021 12:0015.10.2021 12:00
Optimierende Übersetzer 1204.10.2021 12:0015.10.2021 12:00
Optimierende Übersetzer 1304.10.2021 12:0015.10.2021 12:00
Optimierende Übersetzer 1404.10.2021 12:0015.10.2021 12:00
Optimierende Übersetzer 1504.10.2021 12:0015.10.2021 12:00
Optimierende Übersetzer 1604.10.2021 12:0015.10.2021 12:00
Optimierende Übersetzer 1704.10.2021 12:0015.10.2021 12:00
Optimierende Übersetzer 1804.10.2021 12:0015.10.2021 12:00
Optimierende Übersetzer 1904.10.2021 12:0015.10.2021 12:00
Optimierende Übersetzer 2004.10.2021 12:0015.10.2021 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

if required in English