FDA001 Advanced Compiler Construction

Contains the course Code generation and optimization (3p) as a proper subset.

Lectures:

32 h

Recommended for

Ph.D. students or practitioners in computer science or systems engineering.

The course was last given:

Spring 2000, but has been revised for Spring 2002 (about 50% of the contents are new compared to previous instances).

Goals

Give Ph.D. students or practitioners knowledge about advanced compiler optimization techniques, as well as compiler generation tools for semantics and code generators.

Prerequisites

Basic course in compiler construction, corresponding to the undergraduate courses Compilers and Interpreters, or Compiler Construction.
Basic course in data structures and algorithms.
Basic knowledge in processor architecture.

Organization

Lectures and student paper presentations.

The first part of the course (semantics, program analysis, intermediate representations, target-independent optimizations) will be given as ca. 8-10 lectures (20h) within one week in February 2002. This part covers mainly issues that have been part of previous instances of this course. It concludes with an oral examination.

The second part of the course (code generation, optimization, parallelization) will be given as ca. 6-8 lectures in late February and March. This part (which may partially overlap in time with part I) covers mainly new topics and can be taken by students that already took this course before. It concludes with an oral examination.

The third part of the course consists of student presentations of about 45 minutes each on an advanced topic in this area, with a written summary of 2-3 pages to be delivered by the end of the period.

Contents

Part I and II (interleaved, no one-to-one correspondence to lectures):

• Introduction: Processor architectures, code generation, intermediate representations, tools (Christoph)
• Foundations, e.g., control and data dependence, data flow analysis (Christoph)
• Overview of optimizations (Uwe / Christoph)
• SSA and its construction (Uwe)
• SSA based optimizations (Uwe)
• Compiler generators. (Peter F)
• Generating semantics modules from Natural Semantics using RML. (Peter F)
• Automatically generating code generators. Some examples. (Peter F)
• Interprocedural optimization. (Christoph / Uwe)
• Code selection. Instruction scheduling. Register allocation. (Christoph)
• Loop scheduling / Software pipelining. (Christoph)

Literature

Steven Muchnick: Advanced Compiler Design and Implementation. Morgan Kaufmann, 1997.

Peter Fritzson: Generating language implementations from Natural Semantics using RML. (Book draft, 1998) (handed out)

Niclas Andersson, Peter Fritzson: Overview and Industrial Application of Code Generator Generators. Journal of Systems and Software, 1995. (handed out)

Rainer Leupers: Retargetable Code Generation for Digital Signal Processors. Kluwer, 1997. (further reading)

Teachers

Christoph Kessler (course leader)

Uwe Assmann

Peter Fritzson.

Examiner

Christoph Kessler

Uwe Assmann

Peter Fritzson.

Schedule

To be announced.

Examination

EXE1: Written homework exercise (Peter F) 1p

MUN1: Oral examination (Uwe, Christoph) 2p

MUN2: Oral examination (Uwe, Christoph) 2p (may be credited to the course Code generation and Optimization)

PRE1: presentation and written summary (Uwe, Christoph) 1p (may be credited to the course Code Generation and Optimization)

Credit

6 credits for the entire course. Participants who already took Advanced Compiler Construction earlier and got points for the course in a previous instance can get the points for N2 and PRE1 credited under the course Code generation and Optimization, but no points for EXE1 and N1.

Comments

ECSEL Graduate Course.