Compiler Optimization Techniques

CP7252 COMPILER OPTIMIZATION TECHNIQUES  L T P C 3 0 0 3 

OBJECTIVES
 To understand different forms of intermediate languages and analyzing programs
 To understand optimizations techniques for single program blocks
 To apply optimizations on procedures and low level code
 To explore and enhance inter procedural optimizations
 To enhance resource utilization
UNIT I INTERMEDIATE REPRESENTATION OF PROGRAMS AND ANALYSIS 9
Structure of an Optimizing Compiler – Compiler Construction tools – LIR, MIR, HIR – DAG – Syntax Tree – Postfix – Control Flow Analysis – Iterative Data Flow Analysis – Static Single Assignment – Basic Block Dependence DAGs – Alias Analysis.
UNIT II LOCAL AND LOOP OPTIMIZATIONS 9
Early Optimizations: Constant-Expression Evaluation – Scalar Replacement of Aggregates – Algebraic Simplifications and Re-association – Value Numbering – Copy Propagation – Sparse Conditional Constant Propagation. Redundancy Elimination: Common – Subexpression Elimination – Loop-Invariant Code Motion – Partial-Redundancy Elimination – Redundancy Elimination and Reassociation – Code Hoisting. Loop Optimizations: Induction Variable Optimizations – Unnecessary Bounds Checking Elimination.
UNIT III PROCEDURE OPTIMIZATION AND SCHEDULING 9
Procedure Optimizations: Tail-Call Optimization and Tail-Recursion Elimination – Procedure Integration – In-Line Expansion – Leaf-Routine Optimization and Shrink Wrapping. Code Scheduling: Instruction Scheduling – Speculative Loads and Boosting – Speculative Scheduling – Software Pipelining – Trace Scheduling – Percolation Scheduling. Control-Flow and Low-Level Optimizations : Unreachable-Code Elimination – Straightening – If Simplifications – Loop Simplifications -Loop Inversion – Un-switching – Branch Optimizations – Tail Merging or Cross Jumping – Conditional Moves – Dead-Code Elimination – Branch Prediction – Machine Idioms and Instruction Combining.
UNIT IV INTER PROCEDURAL OPTIMIZATION 9
Symbol table – Runtime Support – Interprocedural Analysis and Optimization: Interprocedural Control-Flow Analysis – The Call Graph – Interprocedural Data-Flow Analysis – Interprocedural Constant Propagation – Interprocedural Alias Analysis – Interprocedural Optimizations – Interprocedural Register Allocation – Aggregation of Global References.
UNIT V OPTIMIZING FOR MEMORY 9
Register Allocation: Register Allocation and Assignment – Local Methods – Graph Coloring – Priority Based Graph Coloring – Other Approaches to Register Allocation. Optimization for the Memory Hierarchy: Impact of Data and Instruction Caches – Instruction-Cache Optimization – Scalar Replacement of Array Elements – Data-Cache Optimization – Scalar vs. Memory-Oriented Optimizations.
TOTAL : 45 PERIODS
OUTCOMES:
Upon completion of this course, the student should be able to
 Identify the different optimization techniques that are possible for a sequence of code
 Design performance enhancing optimization techniques
 Manage procedures with optimal overheads
 Ensure better utilization of resources

REFERENCES:
1. Steven Muchnick, “Advanced Compiler Design and Implementation”, Morgan Kaufman Publishers, 1997.
2. Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman, “Compilers: Principles, Techniques, and Tools”, Addison Wesley, Second Edition, 2007.
3. Andrew W. Appel, Jens Palsberg, “Modern Compiler Implementation in Java”, Cambridge University Press, Second Edition, 2002.
4. Keith Cooper, Linda Torczon, “Engineering a Compiler”, Morgan Kaufmann, Second Edition, 2011.
5. Randy Allen and Ken Kennedy, “Optimizing Compilers for Modern Architectures: A Dependence based Approach”, Morgan Kaufman, 2001.