ECS 243: Code Generation & Optimization

ECS 243
Code Generation & Optimization
Effective Term
2016 Fall Quarter
Learning Activities
Lecture - 3.0 hours
Discussion - 1.0 hours
Compiler optimizations for performance, code size and power reduction. Topics include control- and data-flow analysis, redundancy elimination, loop and cache optimizations, register allocation, local and global instruction scheduling, and modulo scheduling.
ECS 201A or EEC 270
Enrollment Restrictions
Pass One and Pass Two open to Graduate Students in Computer Science only.

Summary of Course Content
I. Introduction
A. Overall compiler organization: frontend, backend
B. Intermediate representation: high-level, low level
C. Backend organization

II. Control-Flow Analysis
A. Basic blocks
B. Control-flow graph
C. Dominators
D. Loops
E. Call graph
F. Program profiling

III. Control-Oriented Optimizations
A. Local Instruction Scheduling
B. Global Instruction Scheduling
C. Branch Alignment
D. Procedure ordering
E. Unreachable Code Elimination

IV. Loop-Oriented Optimizations
A. Loop-Invariant Code Motion
B. Induction Variable Elimination
C. Loop Unrolling
D. Modulo Scheduling
E. Loop Reversal, Interchange, Pealing, Fission, Fusion, Unswitching, Collapsing

V. Data-Flow Analysis
A. Data Dependence
B. Aliasing
C. Static Single Assignment
D. Reaching Definitions
E. Def-Use Chains, Use-Def Chains
F. Bit-Vector Iterative Analysis
G. Live-Range Analysis (Web Analysis)
H. Symbolic-Register Renumbering, Interference
I. Available Expressions
J. Value Numbering

VI. Data-Oriented Optimizations
A. Dead-Code Elimination
B. Copy propagation
C. Code Hoisting/Sinking
D. Common Sub-Expression Elimination
E. Partial Redundancy Elimination
F. Strength Reduction
G. Register Allocation

Illustrative Reading
K.Cooper and L. Torczon, Engineering A Compiler (chapters 8-13), Morgan Kaufmann, 2003
Plus papers from the literature.

Potential Course Overlap
There is no significant overlap with another course.

Course Category