EECS 583: Advanced Compilers

Winter 2002

Syllabus

Schedule

MW, 3:30 - 5:30, 1012 FXB

Course Description

An in-depth study of compiler backend design for high-performance architectures.  Topics include control-flow and data-flow analysis, classical optimization, instruction scheduling, and register allocation. Advanced topics include memory hierarchy management, optimization for instruction-level parallelism, modulo scheduling, predicated and speculative execution. The class focus  is processor-specific compilation techniques, thus familiarity with both computer architecture and compilers is recommended.

References

Compilers: Principles, Techniques, and Tools, Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman, Addison-Wesley, 1988.

Advanced Compiler Design & Implementation, Steven S. Muchnick, Morgan Kaufmann, 1997.

Building an Optimizing Compiler, Robert Morgan, Butterworth-Heinemann,1998.

Prerequisites

EECS 370, EECS 281, EECS 483 or a basic familiarity with compilers

Grade

Midterm Exam - 30%
Project - 40%
Homeworks - 15%
Class participation - 15%

Midterm exam - There will be 1 in-class (2 hour) exam after at about the 2/3 point of the class covering all material up through register allocation.  The exam will be open book/notes.

Project - The class will be broken down into 4 special interest groups (see below).  Each group will define a couple of projects related to the topic of their group.  The projects will consist of designing and implementing an advanced compiler technique within the Trimaran compiler infrastructure.  A report describing the project should be submitted along with a brief presentation and/or demonstration of the resulting implementation.

Homeworks - Three programming assignments will done throughout the semester.  Each will focus on one particular aspect of the compiler.  The expected homework topics are control flow analysis, classical optimization, and instruction scheduling.  Each homework will consist of implementing a particular technique within the Trimaran compiler system and showing its operation on several test programs.

Class participation - Students are encouraged to take an active role in this class by asking questions or providing comments.  Each student will have the opportunity to present a research paper of their choosing to the class.

Special interest groups

The SIG meetings are intended to be discussion groups in which we will go into more depth about one particular aspect of compiler backends.  You should come prepared to discuss things and participate in the discussion.  Each group will identify several topics within their specific category to investigate.  We will identify relevant papers to be read and presented to the rest of the class.  The groups will also define the projects they wish to do and partition the work amongst the members.

Schedule

Week 1 - Jan 7, 9
            Mon - Course introduction, overview of EPIC architectures
            Wed - Basic control flow analysis

Week 2 - Jan 14, 16
            Mon - EPIC architectures, explicit parallelism, predicated execution, speculative execution, rotating registers
            Wed - Advanced control flow analysis, control dependences, if-conversion

Week 3 - Jan 21, 23
            Mon - MLK holiday
            Wed - Overview of the Trimaran compilation infrastructure, installation, usage, basic data structures

Week 4 - Jan 28, 30
            Mon - Region creation, trace selection, superblock formation, hyperblock formation
            Wed - Basic dataflow analysis, liveness, reaching definitions

Week 5 - Feb 4, 6
            Mon - Advanced dataflow analysis, backward/forward dataflow, def-use chains, availability
            Wed - Classical optimizations, local, global, loop
            Homework 1 due, Sunday February 10, 11:59PM EST

Week 6 - Feb 11, 13
            Mon - Analysis of predicated code - predicate relation analysis, predicate-sensitive dataflow analysis
            Wed - Optimizations for instruction-level parallelism

Week 7 - Feb 18, 20
            Mon - Machine descriptions and dependence graphs
            Wed - Instruction scheduling for a basic block

Week 8 - Feb 25, 27 - No class, spring break

Week 9 - Mar 4, 6
            Mon - Superblock scheduling, models for control speculation, trace scheduling
            Wed - Basics of software pipelining innermost loops

Week 10 - Mar 11, 13
            Mon - Software pipelining implementation
            Wed - Register allocation
            Homework 2 due, Friday March 15, 11:59 PM EST

Week 11 - Mar 18, 20
            Mon - Group 1 student presentations (control flow analysis and optimization)
            Wed - Group 2 student presentations (dataflow analysis and optimization)

Week 12 - Mar 25, 27
            Mon - Exam in class
            Wed - Group 3 student presentations (scheduling, register allocation, and code generation)

Week 13 - Apr 1, 3
            Mon - Group 4 student presentations (memory optimization)
            Wed - Group 1 student presentations (control flow analysis and optimization)

Week 14 - Apr 8, 10
            Mon - Group 2 student presentations (dataflow analysis and optimization)
            Wed - Group 3 student presentations (scheduling, register allocation, and code generation)
            Homework 3 due, Friday April 12, 11:59 PM EST

Week 15 - Apr 15, 17
            Mon - Group 4 student presentations (memory optimization)
            Wed - Class wrap up, perspectives, research opportunities

Week 16 - Apr 22-26 (schedule appointment)
            Final project presentations and demos