Chap 10 Optimization CSE 4100 Prof Steven A Demurjian Computer Science Engineering Department The University of Connecticut 371 Fairfield Way Unit 2155 Storrs CT 06269 3155 steve engr uconn edu http www engr uconn edu steve 860 486 4818 Material for course thanks to Laurent Michel Aggelos Kiayias Robert LeBarre CH10 1 Overview CSE 4100 Motivation and Background Code Level Optimization Common Sub expression elimination Copy Propagation Dead code elimination Peephole optimization Load Store elimination Unreachable code Flow of Control Optimization Algebraic simplification Strength Reduction Concluding Remarks Looking Ahead CH10 2 Motivation CSE 4100 What we achieved We have working machine code What is missing Code generation does not see the big picture We can generate poor instruction sequences What we need A simple way to locally improve the code quality Goal Transition from Lousy Intermediate Code to More Effective and Efficient Code Response Time Performance Algorithms Memory Usage Measured in terms of Number of Variables Saved Operands Saved Memory Accesses etc CH10 3 Where can Optimation Occur CSE 4100 Source Program Front End Int Code LA Parse Int Code Software Engineer can Profile Program Change Algorithm Data Transform Improve Loops Code Generator Target Program Compiler Can Improve Loops Proc Calls Calculate Addresses Use Registers Selected Instructions Perform Peephole Opt All are Optimizations 1st is User Controlled and Defined At Intermediate Code Level by Compiler At Assembly Level for Target Architecture to take advantage of different machine features CH10 4 Code Level Optimization CSE 4100 First Look at Optimization Section 9 4 in 1st Edition Introduce and Discuss Basic Blocks Requirements for Optimization Section 10 1 in 1st Edition Basic Blocks Flow Graphs Indepth Examination of Optimization Section 10 2 in 1st Edition Function Preserving Transformations Loop Optimizations CH10 5 First Look at Optimization CSE 4100 Optimization Applied to 3 Address Coding 3AC Version of Source Program Examples A B i ct1 b i t2 t1 a t3 t2 c CH10 6 First Look at Optimization CSE 4100 Once Code has been Generated in 3AC an Algorithm can be Applied to Identify each Basic Block which Represents a set of Three Address Statements where Execution Enters at Top and Leaves at Bottom No Branches within Code Represent the Control Flow Dependencies Among and Between Basic Blocks Defines what is Termed a Flow Graph Let s see an Example CH10 7 First Look at Optimization CSE 4100 Steps 1 to 12 from two Slides Back Represented as Optimization Works with Basic Blocks and Flow Graph to Perform Transformations that Generate Equivalent Flow Graph w Improved Perf CH10 8 First Look at Optimization CSE 4100 Optimization will Perform Transformations on Basic Blocks Flow Graph Resulting Graph s Passed Through to Final Code Generation to Obtain More Optimal Code Two Fold Goal of Optimization Reduce Time Reduce Space Optimization Used to Come at a Cost In Old Days Turning on Optimizer Could Double the Compilation Time From 2 hours to 4 hours Is this an Issue Today CH10 9 First Look at Optimization CSE 4100 Two Types of Transformations Structure Preserving Inherent Structure and Implicit Functionality of Basic Blocks is Unchanged Algebraic Elimination of Useless Expressions x x 0 or y y 1 Replace Expensive Operators Change x y 2 to x y y Why We ll Focus on Both CH10 10 Structure Preserving Transformations CSE 4100 Common Sub Expression Elimination How can Following Code be Improved a b c b a d d b c b c d a d What Must Make Sure Doesn t happen Dead Code Elimination If x is not Used in Block Can it be Removed x y z What are the Possible Ramifications if so CH10 11 Structure Preserving Transformations CSE 4100 Renaming Temporary Variables Consider the code t b c Can be Changed to u b c May Reduce the Number of temporaries Make Change from all t s to all u s Interchange of Statements Consider and Change to t1 b c t2 x y t2 x y t1 b c This can Occur as Long as x and y not t1 b and c not t2 What Do you have to Check CH10 12 Requirements for Optimization CSE 4100 Identify Frequently Executed Portions of Code and Make them Perform Better Rule of Thumb Most Programs spend 80 of their Time in 20 of Code Is this True We Focus on Loops since Every Gain in Space or Time is Multiplied by Loop Iterations Reduce Loop s Code and Improve Performance What Other Programming Technique Should be a Major Concern for Optimization CH10 13 Requirements for Optimization CSE 4100 Criteria for Transformations Preserve Meaning of Code Don t Change Output Introduce Errors etc Speed up Programs by Measurable Amount on Average for Entire Code Must be Work the Effort Stick to Meaningful Useful Transformations Provide Different Versions of Compiler Non Optimizing Optimizing Extra Optimization on Demand CH10 14 Requirements for Optimization CSE 4100 Beware that Some Optimization Directives are Ignored In C Define variable as register int I While a Feature of Language cc States that these Instructions are Ignored and Compiler Controls Use of Registers CH10 15 The Overall Optimization Process CSE 4100 Advantages Intermediate Code has Explicit Operations and Their Identification Promotes Optimization Intermediate Code is Relatively Machine Independent Therefore Optimization Doesn t Impact Final Code Generation CH10 16 Example Source Code CSE 4100 CH10 17 Generated Three Address Coding CSE 4100 CH10 18 Flow Graph of Basic Blocks CSE 4100 CH10 19 Indepth Examination of Optimization CSE 4100 Code Transformation Techniques Local within a Basic Block Global between Basic Blocks Data Flow Dependencies Determined by Inspection what do i a and v refer to Dependent in Another Basic Block Scoping is Very Critical CH10 20 Indepth Examination of Optimization CSE 4100 Function Preserving Transformations Common Subexpressions Copy Propagation Deal Code Elimination Loop Optimizations Code Motion Induction Variables Strength Reduction CH10 21 Common Sub Expressions CSE 4100 E is a Common Sub Expression if E as Previously Computed Value of E Unchanged since Previous Computation What Can be Saved in B5 t6 and t7 same computation t6 4 i t8 and t10 same computation x a t6 t7 t8 4 j i Save t8 t9 a t8 4 j Remove 2 temp variables Remove 2 multiplications Remove 4 variable accesses Remove 2 assignments a t6 t9 t9 a t8 a t7 xt9 a t8 t10 B2 Goto 4 j a t10 x Goto B2 CH10 22 Common Sub Expressions CSE 4100 What about B6 t11 and t12 t13 and t15 Similar Savings as in B5