School of EECS, Peking University Advanced Compiler Techniques"(Fall 2011) Introduction to Optimizations Guo yao
School of EECS, Peking University “Advanced Compiler Techniques” (Fall 2011) Introduction to Optimizations Guo, Yao
Outline Optimization rules Basic blocks Control Flow Graph(CFG) a Loops a Local Optimizations Peephole optimization Fa|2011 Advanced Compiler techniques
2 Fall 2011 “Advanced Compiler Techniques” Outline ◼ Optimization Rules ◼ Basic Blocks ◼ Control Flow Graph (CFG) ◼ Loops ◼ Local Optimizations ◼ Peephole optimization
Levels of Optimizations ■Loca a inside a basic block Global (intraprocedural) Across basic blocks Whole procedure analysis Interprocedural Across procedures Whole program analysis Fa|2011 Advanced Compiler techniques
3 Fall 2011 “Advanced Compiler Techniques” Levels of Optimizations ◼ Local ◼ inside a basic block ◼ Global (intraprocedural) ◼ Across basic blocks ◼ Whole procedure analysis ◼ Interprocedural ◼ Across procedures ◼ Whole program analysis
The Golden Rules of optimization Premature Optimization is Evil a Donald Knuth, premature optimization is the root of al∥evi Optimization can introduce new, subtle bugs Optimization usually makes code harder to understand and maintain Get your code right first, then, if really needed, optimize计t Document optimizations carefully a Keep the non-optimized version handy, or even as a comment in your code Fa|2011 Advanced Compiler techniques
4 Fall 2011 “Advanced Compiler Techniques” The Golden Rules of Optimization Premature Optimization is Evil ◼ Donald Knuth, premature optimization is the root of all evil ◼ Optimization can introduce new, subtle bugs ◼ Optimization usually makes code harder to understand and maintain ◼ Get your code right first, then, if really needed, optimize it ◼ Document optimizations carefully ◼ Keep the non-optimized version handy, or even as a comment in your code
The Golden Rules of optimization The 80/20 Rule In general, 80% percent of a program's execution time is spent executing 20% of the code 90°%/10°% for performance- hungry programs Spend your time optimizing the important 10/20% of your program Optimize the common case even at the cost of making the uncommon case slower Fa|2011 Advanced Compiler techniques
5 Fall 2011 “Advanced Compiler Techniques” The Golden Rules of Optimization The 80/20 Rule ◼ In general, 80% percent of a program’s execution time is spent executing 20% of the code ◼ 90%/10% for performance-hungry programs ◼ Spend your time optimizing the important 10/20% of your program ◼ Optimize the common case even at the cost of making the uncommon case slower
The Golden Rules of optimization Good Algorithms Rule a The best and most important way of optimizing a program is using good algorithms E.g. O(n*log)rather than O(n2) However we still need lower level optimization to get more of our programs a In addition, asymptotic complexity is not always an appropriate metric of efficiency a Hidden constant may be misleading E.g. a linear time algorithm than runs in 100*n+100 time is slower than a cubic time algorithm than runs in n3+10 time if the problem size is small Fa|2011 Advanced Compiler Techniques
6 Fall 2011 “Advanced Compiler Techniques” The Golden Rules of Optimization Good Algorithms Rule ◼ The best and most important way of optimizing a program is using good algorithms ◼ E.g. O(n*log) rather than O(n2 ) ◼ However, we still need lower level optimization to get more of our programs ◼ In addition, asymptotic complexity is not always an appropriate metric of efficiency ◼ Hidden constant may be misleading ◼ E.g. a linear time algorithm than runs in 100*n+100 time is slower than a cubic time algorithm than runs in n 3+10 time if the problem size is small
Asymptotic Complexity Hidden Constants Hidden Contants 3000 2500 2000 100n+100 1500 n’nn+10 1000 500 0 0 5 10 15 Problem size Fa|2011 Advanced Compiler Techniques 7
7 Fall 2011 “Advanced Compiler Techniques” Asymptotic Complexity Hidden Constants Hidden Contants 0 500 1000 1500 2000 2500 3000 0 5 10 15 Problem Size Execution Time 100*n+100 n*n*n+10
General Optimization Techniques Strength reduction Use the fastest version of an operation ■Eg instead of instead of Common sub expression elimination Eliminate redundant calculations ■Eg double x=d大(1im/max)大sx; double y=d *(lim max)*sy double depth =d (lim/ max double x= depth大sx; double depth Fa|2011 Advanced Compiler Techniques 8
8 Fall 2011 “Advanced Compiler Techniques” General Optimization Techniques ◼ Strength reduction ◼ Use the fastest version of an operation ◼ E.g. x >> 2 instead of x / 4 x << 1 instead of x * 2 ◼ Common sub expression elimination ◼ Eliminate redundant calculations ◼ E.g. double x = d * (lim / max) * sx; double y = d * (lim / max) * sy; double depth = d * (lim / max); double x = depth * sx; double y = depth * sy;
General Optimization Techniques Code motion Invariant expressions should be executed only once E.g for (int 0; 1< xlength; 1++) x[i] * Math PI Math Cos( double picosy= Math. PI Math cos(y) for (int i=0; i<x length; i++) 区[i]*= piCOs Fa|2011 Advanced Compiler techniques
9 Fall 2011 “Advanced Compiler Techniques” General Optimization Techniques ◼ Code motion ◼ Invariant expressions should be executed only once ◼ E.g. for (int i = 0; i < x.length; i++) x[i] *= Math.PI * Math.cos(y); double picosy = Math.PI * Math.cos(y); for (int i = 0; i < x.length; i++) x[i] *= picosy;
General Optimization Techniques Loop unrolling The overhead of the loop control code can be reduced by executing more than one iteration in the body of the loop. E. g double picosy Math. PI Math cos (y)i for(int 0; i< x length i++) 1 piCOs double picosy Math PI Math cos(y) for (int i =0;i length; i + 2)t x[i]大= piCOS A efficient“+1” In array x[i+1]大= piCOs; indexing is required Fa|2011 Advanced Compiler techniques
10 Fall 2011 “Advanced Compiler Techniques” General Optimization Techniques ◼ Loop unrolling ◼ The overhead of the loop control code can be reduced by executing more than one iteration in the body of the loop. E.g. double picosy = Math.PI * Math.cos(y); for (int i = 0; i < x.length; i++) x[i] *= picosy; double picosy = Math.PI * Math.cos(y); for (int i = 0; i < x.length; i += 2) { x[i] *= picosy; x[i+1] *= picosy; } A efficient “+1” in array indexing is required