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.