Compiler Optimizations a Compilers try to generate good code ie Fast Code improvement is challenging Many problems are NP-hard Code improvement may slow down the compilation process a In some domains, such as just-in-time compilation, compilation speed is critical Fa|2011 Advanced Compiler techniques
11 Fall 2011 “Advanced Compiler Techniques” Compiler Optimizations ◼ Compilers try to generate good code ◼ i.e. Fast ◼ Code improvement is challenging ◼ Many problems are NP-hard ◼ Code improvement may slow down the compilation process ◼ In some domains, such as just-in-time compilation, compilation speed is critical
Phases of Compilation Character stream Scanner(lexical analysis The first three phases Token stream Parser(syntax analysis) are language dependent Parse tree Semantic analysis Abstract syntax tree Front end The last two with annotations Back end are machine Intermediate code generation dependent Flow graph with pseudo instructions in basic blocks Machine-independent The middle code improverment fwo Modified flow graph dependent on either the Target code generation language nor (Almost) assembly language 如n+ he machine Machine-specifie code improvement Real assembly language 12
12 Fall 2011 “Advanced Compiler Techniques” Phases of Compilation ◼ The first three phases are languagedependent ◼ The last two are machinedependent ◼ The middle two dependent on neither the language nor the machine
Character stream Scanner (lexical analysis) Phases Token stream Parser(syntax analysis) Parse tree Semantic analysis Abstract syntax tree with Front end annotations(high-level IF) Back end Intermediate Control flow graph with code generation pseudo-instructions in basic blocks(medium-level IF) Local redundancy elimination Machine- Modified control flow graph independent Global redundan elimination Modified control flow graph Loop improvement Modified control flow graph (Almost) assembly language Target code generation (low-level IF Preliminary Modified assembly language instruction scheduling Machine. Register allocation specific Modified assembly language Final instruction scheduling Modified assembly language Peephole optimization Fa|2011 Final assembly language
13 Fall 2011 “Advanced Compiler Techniques” Phases
Outline Optimization Rules Basic blocks Control Flow Graph(CFG) a Loops Local Optimizations Peephole optmization Fa|2011 Advanced Compiler techniques 14
14 Fall 2011 “Advanced Compiler Techniques” Outline ◼ Optimization Rules ◼ Basic Blocks ◼ Control Flow Graph (CFG) ◼ Loops ◼ Local Optimizations ◼ Peephole optmization
Basic blocks a A basic block is a maximal sequence of consecutive three-address instructions with the following properties The flow of control can only enter the basic block thru the 1st instr Control will leave the block without halting or branching except possibly at the last instr Basic blocks become the nodes of a flow graph, with edges indicating the order Fa|2011 Advanced Compiler techniques
15 Fall 2011 “Advanced Compiler Techniques” Basic Blocks ◼ A basic block is a maximal sequence of consecutive three-address instructions with the following properties: ◼ The flow of control can only enter the basic block thru the 1st instr. ◼ Control will leave the block without halting or branching, except possibly at the last instr. ◼ Basic blocks become the nodes of a flow graph, with edges indicating the order