Code Optimization PDF

Code Optimization  Levels of Optimization Window – peephole optimization Basic block Procedural – global (control flow graph) Program level – intraprocedural (program dependence graph)  Peephole Optimizations Constant Folding x := 32 becomes x...

Code Optimization  Levels of Optimization Window – peephole optimization Basic block Procedural – global (control flow graph) Program level – intraprocedural (program dependence graph)  Peephole Optimizations Constant Folding x := 32 becomes x := 64 x := x + 32 Unreachable Code goto L2 x := x + 1  unneeded Flow of control optimizations goto L1 becomes goto L2 … L1: goto L2  Peephole Optimizations Algebraic Simplification x := x + 0  unneeded Dead code x := 32  where x not used after statement y := x + y  y := y + 32 Reduction in strength x := x * 2  x := x + x  Peephole Optimizations Local in nature Pattern driven Limited by the size of the window  Basic Block Level Common Subexpression elimination Constant Propagation Dead code elimination Plus many others such as copy propagation, value numbering, partial redundancy elimination, …  Simple example: a[i+1] = b[i+1] t1 = i+1 t1 = i + 1 t2 = b[t1] t2 = b[t1] t3 = i + 1 t3 = i + 1  no longer live a[t3] = t2 a[t1] = t2 Common expression can be eliminated Now, suppose i is a constant: i=4 i=4 i=4 t1 = 5 t1 = 5 t1 = i+1 t2 = b[t1] t2 = b t2 = b[t1] a[t1] = t2 a = t2 a[t1] = t2 Final Code: i=4 t2 = b a = t2  Control Flow Graph - CFG CFG = < V, E, Entry >, where V = vertices or nodes, representing an instruction or basic block (group of statements). E = (V x V) edges, potential flow of control Entry is an element of V, the unique program entry Two sets used in algorithms: Succ(v) = {x in V| exists e in E, e = v x} Pred(v) = {x in V| exists e in E, e = x v} 1 2 3 4 5  Definitions point - any location between adjacent statements and before and after a basic block. A path in a CFG from point p1 to pn is a sequence of points such that  j, 1 d g=a*c g=d*d i=i+1 if i > 10  Optimizations on CFG Must take control flow into account – Common Sub-expression Elimination – Constant Propagation – Dead Code Elimination – Partial redundancy Elimination –… Applying one optimization may create opportunities for other optimizations.  Redundant Expressions An expression x op y is redundant at a point p if it has already been computed at some point(s) and no intervening operations redefine x or y. m = 2*y*z t0 = 2*y t0 = 2*y m = t0*z m = t0*z n = 3*y*z t1 = 3*y t1 = 3*y n = t1*z n = t1*z o = 2*y–z t2 = 2*y o = t2-z o = t0-z redundant  Redundant Expressions c=a+b Definition site d=a*c Candidates: i=1 a+b a*c d*d f[i] = a + b c*2 Since a + b is i+1 c=c*2 available here, if c > d  redundant! g=a*c g=d*d i=i+1 if i > 10  Redundant Expressions c=a+b Definition site d=a*c Candidates: i=1 a+b a*c d*d f[i] = a + b c*2 Kill site c=c*2 i+1 if c > d Not available g=a*c g=d*d  Not redundant i=i+1 if i > 10  Redundant Expressions An expression e is defined at some point p in the CFG if its value is computed at p. (definition site) An expression e is killed at point p in the CFG if one or more of its operands is defined at p. (kill site) An expression is available at point p in a CFG if every path leading to p contains a prior definition of e and e is not killed between that definition and p. Removing Redundant Expressions t1 = a + b c = t1 d=a*c Candidates: i=1 a+b a*c d*d c*2 i+1 f[i] = t1 c=c*2 if c > d g=a*c g = d*d i=i+1 if i > 10  Constant Propagation b=5 b=5 b=5 c = 4*b c = 20 c = 20 c>b c>5 20 > 5 f t f t f t d=b+2 d=7 d=7 e=a+b e=a+5 e=a+5  Constant Propagation b=5 b=5 c = 20 c = 20 20 > 5 d=7 f t e=a+5 d=7 e=a+5  Copy Propagation b=a b=a c = 4*b c = 4*a c>b c>a d=b+2 d=a+2 e=a+b e=a+a  Simple Loop Optimizations: Code Motion while (i t1) goto L2 body of loop goto L1 L2: t := limit - 2 t1 = limit – 2 L1: while (i t1) goto L2 body of loop goto L1 L2:  Simple Loop Optimizations: Strength Reduction Induction Variables control loop iterations t4 = 4*j j = j – 1 j = j – 1 t4 = 4 * j t4 = t4 - 4 t5 = a[t4] t5 = a[t4] if t5 > v if t5 > v Frequency Reduction (Code Motion): The amount of code in loop is decreased. A statement or expression, which can be moved outside the loop body without affecting the semantics of the program, is moved outside the loop. Example: Optimized code: Initial code: t = Sin(x)/Cos(x); while(i