1CS380C Lecture 8 Using Static Single Assignment 1Using Static Single Assignment Form Last Time– Constructing SSA form Today– Finish naming algorithm– Transforming from SSA– Using SSA for program optimization– Dead-code elimination– Constant propagation– Register allocation– Copy propagation– Induction variablesCS380C Lecture 8 Using Static Single Assignment 2Variable Renaming (cont) Data Structures– Stacks[v] ∀ vHolds the subscript of most recent definition of variable v, initially empty– Counters[v] ∀ vHolds the current number of assignments to variable v; initially 0 Auxiliary Routineprocedure GenName(variable v) i := Counters[v] push i onto Stacks[v] Counters[v] := i + 112 5 9111078634 1312Use the Dominance Tree to remember the mostrecent definition of each variablepushpopCS380C Lecture 8 Using Static Single Assignment 3Variable Renaming Algorithmprocedure Rename(block b)if b previously visited returnfor each φ-function p in bGenName(LHS(p)) and replace v with vi, where i=Top(Stack[v])for each statement s in b (in order)for each variable v ∈ RHS(s)replace v by vi, where i = Top(Stacks[v])for each variable v ∈ LHS(s)GenName(v) and replace v with vi, where i=Top(Stack[v])for each s ∈ succ(b) (in CFG)j ← position in s’s φ-function corresponding to block bfor each φ-function p in sreplace the jth operand of RHS(p) by vi, where i = Top(Stack[v])for each s ∈ child(b) (in DT)Rename(s)for each φ-function or statement t in bfor each vi ∈ LHS(t)Pop(Stack[v])Call Rename(entry-node)Recurse using Depth First SearchUnwind stack when done with this nodeΦ( , , )CS380C Lecture 8 Using Static Single Assignment 4Transformation from SSA Form Proposal– Restore original variable names (i.e., drop subscripts)– Delete all φ-functions Alternative− Perform dead code elimination (to prune φ-functions)− Replace φ-functions with copies in predecessors− Rely on register allocation coalescing to remove unnecessary copiesx0 =x1 = = x0 = x1 Complications− What if versions get out of order?(simultaneously live ranges)2CS380C Lecture 8 Using Static Single Assignment 5Dead Code Elimination for SSA Dead code elimination while ∃ a variable v with no uses and whose def has no other side effects Delete the statement s that defines v for each of s’s ud-chains Delete the corresponding du-chain that points to sx = a + bIf y becomes dead and there are noother uses of x, then the assignment tox becomes dead, too– Contrast this approach with one that uses liveness analysis– This algorithm updates information incrementally– With liveness, we need to invoke liveness and dead codeelimination iteratively until we reach a fixed pointy = x + 3uddusCS380C Lecture 8 Using Static Single Assignment 6Constant Propagation Goal– Discover constant variables and expressions and propagate them forwardthrough the program Uses– Evaluate expressions at compile time instead of run time– Eliminate dead code (e.g., debugging code)– Improve efficacy of other optimizations (e.g., value numbering andsoftware pipelining)CS380C Lecture 8 Using Static Single Assignment 7 Simple constant propagation– V:– * :– F:– Fx←c(In) = – Fx←y⊕z(In) = – . . . c * ¨ = c c * ⊥ = ⊥ c * d = ⊥ if c ≠ d c * d = c if c = d{All constants} ∪ {⊤,⊥ } Data-Flow Analysis for Simple Constant Propagation c if cy=Iny & cz=Inz, then cy ⊕ cz, else ⊤ or ⊥⊤⊥0 1 2 3-3 -2 -1 . . .. . .Using tuples of latticesCS380C Lecture 8 Using Static Single Assignment 8Implementing Simple Constant Propagation Standard worklist algorithm– Identifies simple constants– For each program point, maintains one constant value for each variable– O(EV) (E is the number of edges in the CFG; V is number of variables) Solution− Exploit a sparse dependence representation (e.g., SSA) Problem− Inefficient, since constants may haveto be propagated through irrelevantnodesx = 1y = x3CS380C Lecture 8 Using Static Single Assignment 9Sparse Simple Constant Propagation Reif and Lewis algorithm– Identifies simple constants– Faster than Simple Constants algorithm SSA edges− Explicitly connect defs with uses− How would you do this? Main Idea− Iterate over SSA edges instead ofover all CFG edgesx = 1y = xCS380C Lecture 8 Using Static Single Assignment 10worklist = all statements in SSAwhile worklist ≠ ∅Remove some statement S from worklistif S is x = phi(c,c,...,c) for some constant creplace S with v = cif S is x=c for some constant cdelete s from programfor each statement T that uses vsubstitute c for x in Tworklist = worklist union {T}Sparse Simple Constants Algorithm (Ch. 19 in Appel)x = 1b = x34567read(y)a=y+zCS380C Lecture 8 Using Static Single Assignment 11Sparse Simple Constants Complexity– O(E’) = O(EV), E’ is number of SSA edges– O(N) in practiceCS380C Lecture 8 Using Static Single Assignment 12Backward Analyses vs. Forward AnalysesFor forward data-flow analysis, at phi node apply meet functionFor backward data-flow analysis?v2 := φ(v0,v1)...v2...4v0 :=...2v1 :=...314CS380C Lecture 8 Using Static Single Assignment 13Static Single Information Form (SSI)Ananian’s Masters Thesis, 1997 MITCS380C Lecture 8 Using Static Single Assignment 14Register Allocation Constructing the interference graph– Algorithm 19.17 in Appel– walk backward from each use until find def for that use– any defs found along the way cause interference– when use is in a phi function, only traverse the edge in the flow graph forthe relevant predecessor Is it faster?– Liveness O(VE), where v is the # of variables and E is # of edges in CFG– Interference graph construction from Liveness is O(VE) + O(E+I), whereI is the size of the interference graph.– Using SSA, interference graph construction is O(E+I) with certainrestrictions.CS380C Lecture 8 Using Static Single Assignment 15Copy Propagation Algorithmworklist = all statements in SSAwhile worklist ≠ ∅Remove some statement S from worklistif S is x = phi(y) or x = yfor each statement T that uses xreplace all use of x with yworklist = worklist union {T}delete SCS380C Lecture 8 Using Static Single Assignment 16Induction Variable Identification Types of Induction Variables– Basic induction variables– Variables that are defined once in a loop by a statement of the form,i=i+c (or i=i*c), where c is a constant integer– Derived