Title
Code Generation & Optimization
Effective Term
2016 Fall Quarter
Learning Activities
Lecture - 3.0 hours
Discussion - 1.0 hours
Description
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.
Prerequisites
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
