Unformatted text preview:

CSE 5317Lecture 20: Optimization6 April 2010Nate NystromUTAThursday, May 6, 2010OptimizationThursday, May 6, 2010Constant folding• Very simple optimization• Replace 1+2 with 3• Often done on the ASTThursday, May 6, 2010Constant folding implementationNode%visit(Add%n)%{%%%%Node%e1%=%n.left.accept(this);%%%%Node%e2%=%n.right.accept(this);%%%%if%(e1%instanceof%IntLit%&&%e1%instanceof%IntLit)%{%%%%%%%%int%v1%=%((IntLit)%e1).value;%%%%%%%%int%v2%=%((IntLit)%e2).value;%%%%%%%%return%new%IntLit(v1%+%v2);%%%%}%%%%return%new%Add(v1,%v2);}Thursday, May 6, 2010Constant propagationReplace temporaries with constantsx = 3y = 4z = x * yx = 3y = 4z = 12Thursday, May 6, 2010Constant propagation dataflow• Similar to copy propagation analysis:• forward, must (all paths)•does variable x contain constant k on all paths to this point?• But different lattice:• map every variable to a constant:• sets of (variable, constant) pairs• What’s the ordering?Thursday, May 6, 2010Constant propagation lattice... -2 -1 0 1 2 ...Not a constantUnknownMap each variable toa member of the lattice:Thursday, May 6, 2010Constant propagation analysis• Initialization:•Every variable maps to unknown• Meet operation:• Do a meet on the lattice for each variable:•unknown ⊓ 0 = 0•1 ⊓ 1 = 1•2 ⊓ 3 = not_a_constant•4 ⊓ not_a_constant = not_a_constantThursday, May 6, 2010Incorporating folding• Transfer function should incorporate constant folding{%x%=%1,%y%=%2%}z%=%x%+%y{%x%=%1,%y%=%2,%z%=%3%}Thursday, May 6, 2010Constant propagation transformation• Do analysis.• Traverse IR:• if variable maps to a constant value, substitute constant in the instruction:{%y%=%NOT_CONSTANT,%z%=%3%}x%=%y%+%zMM>x%=%y%+%3Thursday, May 6, 2010Profitable?• Almost always!• Removes temporaries –!reducing register pressure• Shortens live rangers –!reducing register pressure• Creates dead, unreachable code:• if%(false)%...• while%(false)%...Thursday, May 6, 2010Constant propagation for loopsx%=%0;while%(x%>%10)%S;MM>while%(false)%S;• Dead code elimination can now remove the loop.Thursday, May 6, 2010Dead code elimination• Do liveness analysis• If variable not live, remove its definition• This removes uses of variables on the rhs:•ex: removing x = y + z, removes uses of y and z• Repeat!•ex: this may remove definitions of y and z also• Remove unreachable codeThursday, May 6, 2010Interprocedural copy propagationx%=%fact(3);int%fact(int%n)%{%%if%(n%<=%1)%%%%return%1;%%else%%%%return%n%*%fact(nM1);}x%=%3%*%fact(2);n%=%3;if%(n%<=%1)%x%=%1;else%x%=%n%*%fact(nM1);x%=%6%*%fact(1);if%(3%<=%1)%x%=%1;else%x%=%3%*%fact(2);x%=%6%*%1;x%=%6;x%=%3%*%2%*%fact(1);Copy propagation very valuable when combined with inliningThursday, May 6, 2010Reaching definitions• Every assignment is a definition.•A definition d reaches a point p if there exists a path from the point immediately after d to p where d is not killed.y = 3x = 10y = 11if ez = xx = 4x = 1y = 2Thursday, May 6, 2010Reaching definitions• Dataflow:• lattice: sets of definitions• meet = union• transfer function: out[i] = (in[i] - kill[i]) U gen[i]• gen[i] = {i}• kill[i] = { d | target(d) = target(i) }y = 3x = 10y = 11if ez = xx = 4x = 1y = 2Thursday, May 6, 2010Chains• Many optimizations use the following data structures:• ud chain•maps a use of variable x to a list of all reaching definitions of x• du chain•maps a def of variable x to a list of all uses of that def• Can build directly from reaching definitions•ud chains are the central data structure of many analyses and optimizationsThursday, May 6, 2010Constant propagation with ud chains• For each use u, compute const(u):•const(u) = ⊓ { constDef(d) | d in ud-chain(u) }• constDef(d) = c if d is “x = c”• constDef(d) = c if d is “x = y + z” and c = const(y) + const(z)• where + on lattice elements is defined to propagate not_a_constant and unknown:ex: c + not_a_constant = not_a_constant• other instructions are similar• Replace u with const(u) if const(u) is constantThursday, May 6, 2010Loop optimizations• Most time in programs spent in loops – duh!• Important to make loop bodies as fast as possible• Variety of optimizations to do this:• code hoisting (e.g., partial redundancy elimination–last time)• loop transformations (next time)• strength reduction• induction variable eliminationThursday, May 6, 2010Loop structurea=0a<ba=a+1back edgeheader: target of the back edgepreheader: predecessor of the headerTo identify loops:DFS on the CFG to find strongly connected components.loop exitloopThursday, May 6, 2010Loop optimizations• Today:• strength reduction• induction variable elimination•Both require identifying induction variablesThursday, May 6, 2010Induction variables•Variables whose values form a linear progression:• 0, 4, 8, 12, 16, ...• Useful for:• strength reduction• induction variable elimination• loop transformations• Simple approach:•Look for instructions i%=%i%+%c where there are no other assignments to i in the loop• This doesn’t catch all IVs. Why not?Thursday, May 6, 2010Induction variable identification• Basic induction variables (e.g., loop index)• defined once in a loop by statement of the form:i%=%i%+%c, where c is a constant integer• Derived induction variables•defined once in a loop as a linear function of another induction variable:k%=%j%+%c, ork%=%d%*%j, where c and d are loop invariantThursday, May 6, 2010Induction variablesfor%(i%=%0;%i%<%n;%i++)%%%%a[i]%=%0In IR:i%=%0top:%if%i%>=%n%goto%endt%=%4%*%ip%=%a%+%t[p]%=%0i%=%i%+%1goto%topend:Thursday, May 6, 2010Induction variablesfor%(i%=%0;%i%<%n;%i++)%%%%a[i]%=%0In IR:i%=%0top:%if%i%>=%n%goto%endt%=%4%*%ip%=%a%+%t[p]%=%0i%=%i%+%1goto%topend:i is an induction variableThursday, May 6, 2010Induction variablesfor%(i%=%0;%i%<%n;%i++)%%%%a[i]%=%0In IR:i%=%0top:%if%i%>=%n%goto%endt%=%4%*%ip%=%a%+%t[p]%=%0i%=%i%+%1goto%topend:t is an induction variable, t==4*ii is an induction variableThursday, May 6, 2010Induction variablesfor%(i%=%0;%i%<%n;%i++)%%%%a[i]%=%0In IR:i%=%0top:%if%i%>=%n%goto%endt%=%4%*%ip%=%a%+%t[p]%=%0i%=%i%+%1goto%topend:t is an induction variable, t==4*ii is an induction variablep is an induction variable, p==a+4*iThursday, May 6, 2010Induction variable analysis•Maps each variable k to a term: c1 + c2*i•i is a basic induction variable•c1 and c2 are constants such that k = c1 + c2*i when k


View Full Document

UT Arlington CSE 5317 - Optimization

Download Optimization
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Optimization and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Optimization 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?