Computer Science

ECS 243 Code Generation and Optimization

ECS 243 CODE GENERATION AND OPTIMIZATION (4) II

Lecture: 3 hours

Discussion: 1 hour

Prerequisite: Course 201A or Engineering Electrical and Computer 270

Grading: Letter; problem sets (10%), project (30%), midterm (20%), final (40%)

Catalog 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.

Expanded Course Description:

  1. Introduction
    1. Overall compiler organization: frontend, backend
    2. Intermediate representation: high-level, low level
    3. Backend organization
  2. Control-Flow Analysis
    1. Basic blocks
    2. Control-flow graph
    3. Loop invariant computations
    4. Dominators
    5. Loops
    6. Call graph
    7. Program profiling
  3. Control-Oriented Optimizations
    1. Loop-Invariant Code Motion
    2. Induction Variable Elimination
    3. Loop Unrolling
    4. Modulo Scheduling
    5. Loop Reversal, Interchange, Pealing, Fission, Fusion, Unswitching, Collapsing
  4. Data-Flow Analysis
    1. Data Dependence
    2. Aliasing
    3. Static Single Assignment
    4. Reaching Definitions
    5. Def-Use Chains, Use-Def Chains
    6. Bit-Vector Iterative Analysis
    7. Live-Range Analysis (Web Analysis)
    8. Symoblic-Register Renumbering, Interference
    9. Available Expressions
    10. Value Numbering
  5. Data-Oriented Optimizations
    1. Dead-Code Elimination
    2. Copy propagation
    3. Cod Hoisting/Sinking
    4. Common Sub-Expression Elimination
    5. Partial Redendancy Elimination
    6. Strength Reduction
    7. Register Allocation

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

Instructor: K. Wilken

Prepared by: K. Wilken

Overlap Statement: There is no significant overlap with another course.

3/07

border