lunduniversity.lu.se

Computer Science

Faculty of Engineering, LTH

Denna sida på svenska This page in English

EDAN75 - Optimizing Compilers

News

  • The lecture on Monday 10/9 is in E:2116 8-10.
  • Due to schedule conflict with EDAN65 the lectures on Mondays have been moved from 13-15 to 8-10. I will announce where later.
  • Link to vcc is here.
  • Enroll to labs here

Lectures

See timeedit for room locations (since they differ sometimes from week to week)

  • F1 Introduction to the course
  • F2 dominance analysis, p 53-96 
  • F3 translation to SSA Form, p99-101, 130-141 (142-151 after Lab 2)
  • F4 register allocation, p245-257
  • F5 copy and constant propagation, p153-160
  • F6 Value numbering, p181-194
  • F7 Partial redundancy elimination, p161-180
  • F8 Operator strength reduction, p194-204
  • F9 Dead code elimination, p102-105, 204-214
  • F10 Data dependence analysis, p107-120
  • F11 Unimodular transformations: inner loop parallelization, p215-226
  • F12 Instruction scheduling, p229-243
  • F13 LLVM
  • F14 The Java virtual machine: Hotspot
  • Part 1 and Part 2 of Hans Wennborg's guest lecture on compiler work at Google and switch-statements in LLVM.

Reading advice for the exam

  • Link for the current edition of the book which covers this course instance
  • Link for the 2016 edition of the book for the 2016 course instance. Note that not all research covered in the current course was published in 2016.
Its goal is to give the students a solid understanding of modern optimizing compilers. The course covers:
  • Dominance analysis
  • SSA Form
  • Scalar optimization algorithms
  • Dependence analysis
  • Loop transformations
  • Instruction scheduling
  • Register allocation
  • Link-time optimization
  • The design of the Clang/LLVM compiler
  • Current research in optimizing compilers and virtual machines (e.g., the JVM)

Optimizing compilers make extensive use of graph algorithms and linear algebra for dependence analysis. An optimizing compiler must be fast, and therefore an important focus is on efficient algorithms. Often, however, NP-complete problems need to be solved and therefore good but suboptimal solutions must be found, e.g. to instruction scheduling register allocation.

New this year is a much greater focus on the Clang/LLVM design and source code, i.e. C++. An extra lecture on relevant parts of C++ will be given.

The following are NOT prerequisites:  C programming, C++ programming, EDAN65 Compilers. EDAN65 and EDAN75 can be taken in any order. With some efforts, you will be able to take this course without prior knowledge of C/C++.

After taking this course in LP1 2018, you may want to take EDAN70 Project in Computer Science in LP2 to focus on a relevant topic of your choice in optimizing compilers, and then do a MSc thesis in LP3-LP4 for one of the compiler companies in Lund or elsewhere.

There is a new edition of the course book with recent research (up to 2018) and LLVM 6.0.1. As usual, it is available at Amazon (most conveniently in Sweden: amazon.de). The ISBN is 978-1725930483.

 

 

Page Manager:

Facts about the course