Course Title: Compiler Optimization
Full Marks: 45 + 30
Course No: C.Sc. 558
Pass Marks: 22.5+15
Nature of the Course: Theory + Lab
Credit Hrs: 3
Course Description:
Theoretical and practical aspects of building optimizing compilers that effectively exploit modern architectures. The course will begin with the fundamentals of compiler optimization, and will build upon these fundamentals to address issues in state‐of‐the‐art commercial and research machines.
Topics include:
dependence analysis, control flow analysis, redundancy elimination, loop optimizations, inter procedural analysis. Students will implement significant optimizations within the framework of a modern research compiler.
Course Objectives:
This course has following objectives:
- To provide students with the background knowledge necessary to understand the process of constructing an optimizing compilers.
- To review common analysis and code transformation techniques used in optimizing compilers.
- To help prepare students to do research in compilers.
Unit 1: Review of Compiler Structure and Modern Architecture 5 Hrs
Review of compiler structure, Importance of code optimization, Structure of optimizing compilers, Compiler challenges for modern architectures: Instruction pipeline, compiling multiple issue processors, Processor parallelism.
Unit 2: Dependence Analysis and Testing 8 Hrs
Fundamentals of dependence, Dependence in loops, Types of dependences, Direction vectors and distance vectors, Fundamental theorem of parallelization, Testing for dependence: separable, SIV, MIV and GCD testing, Construction of direction and distance vectors.
Unit 3: Preliminary Transformations 6 Hrs
Loop normalization, Data flow analysis: Dead-code elimination, Constant propagation, SSA form, Induction variable substitution: Forward expression, Induction-variables, substitution process.
Unit 4:Loop Optimization 8 Hrs
Loop interchange and vectorization, Loop skewing, Scalar and array expansion, Array renaming, Node splitting, Index-set splitting, Forward substitution, Alignment, Code replication, Loop fusion, Nested loops, Parallel code generation and its problems.
Unit 5: Control Dependence 8 Hrs
If conversion: Branch classification, Forward, Exit and Backward branches, Iterative dependences, Control dependence: Control dependence in loops, Application of control dependence to parallelization, Program dependence graph.
Unit 6: Interprocedural Analysis and Optimization 10 Hrs
Side effect analysis, Constant propagation and alias analysis, Flow-insensitive and flow-sensitive problems, Side effects to arrays, Inline substitution, Linkage tailoring and procedure cloning, Management of interprocedural analysis and optimization.
Recommended Books:
Textbook:
- Allen and Kennedy, Optimizing Compilers for Modern Architectures, Morgan‐Kaufmann
Reference:
- Advanced Compiler Design Implementation, Steven S. Muchnick, Morgan‐Kaufmann
