E0 255 Compiler Design
Prof Priti Shankar
Prof Y N Srikant
Course website
Topics covered
- Overview of compiler
- Intermediate code forms
- Runtime storage administration
- Activation records
- Concurrent programs
- OO programs
- Code generation
- Quadruples and abstract syntax trees
- Simple code generator
- Sethi-Ullman algorithm
- Dynamic programming approach
- Heuristics for DAGs
- Basic blocks
- Register allocation
- Code generation tools
- Data flow analysis
- Basics
- Reaching definitions
- Available expressions
- Live variable analysis
- u-d and d-u chains
- Alias analysis
- Simple interprocedural analysis
- Dataflow framework
- Control flow analysis
- Basics
- Dominators
- Loops
- Interval region
- Flow graph reducibility
- Machine independent optimization
- Common subexpression elimination
- Constant propagation
- Copy propagation
- Loop invariants
- Induction variable elimination
- Partical redudancy elimination
- Static Single Assignment form
- Basics
- Optimization based on SSA
- Code parallelization
- Dependence analysis
- Vectorization
- Program dependence graphs
- Global register allocation
- Chaitin's algorithm
- Chow-Hennessy algorithm
- Poletto algorithm
- Instruction scheduling & software pipelining
- Data dependence graphs
- Basic block
- List scheduling
- Finite automata based scheduling
- Modulo scheduling
- Special topics
- Java Virtual Machine
- Escape analysis
- Alias analysis
- Type analysis
Texts and references
- Aho, A.V., Ravi Sethi and J.D. Ullman, Compilers - Principles, Techniques and Tools, Addison Wesley
- S. Muchnick., Advanced Compiler Design and Implementation, Morgan Kauffman
- V.K. Paleri, Y.N. Srikant, P. Shankar, Partial redundancy elimination : a simple pragmatic and provably correct algorithm
- M. Poletto, Vivek Sarkar, Linear Scan Register allocation
- Christoph M. Hoffmann, Michael J O'Donnell, Pattern Matching in Trees
- Data dependence (some xeroxed material)
- Vasanth Bala, Norman Rusbin, Efficient Instruction Scheduling using Finite State Automata
- Micha Sharir, Amir Pnueli, Two Apporoaches to Interprocedural Dataflow Analysis
- Thomas Rep, Susan Horwitz, Moogly Sagiv, Precise Interprocedural Dataflow analysis via Graph Reachability
- Moogly Sagiv, Thomas Rep, Susan Horwitz, Precise Interprocedural Dataflow analysis with Application to Constant propagation
Assignments
Exams
Links
- aiSee(tool for displaying flow graphs)