CS553 Lecture Using Static Single Assignment 2Using Static Single Assignment Form Announcements– Project 2 schedule due today– HW1 due Friday Last Time– SSA Technicalities Today– Constant propagation– Loop invariant code motion– Induction variablesCS553 Lecture Using Static Single Assignment 3Constant 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)CS553 Lecture Using Static Single Assignment 4RoadmapSimple ConstantsKildall [1973]1Sparse Simple ConstantsReif and Lewis [1977]faster2MoreconstantsSparse ConditionalConstantsWegman & Zadeck [1991]faster4MoreconstantsConditional ConstantsWegbreit [1975]3CS553 Lecture Using Static Single Assignment 5Kinds of Constants Simple constants Kildall [1973]– Constant for all paths through a program Conditional constants Wegbreit [1975]– Constant for actual paths through a program (when only one direction ofa conditional is taken)j?4j := 32j := 53c := 1...if c=11true falseCS553 Lecture Using Static Single Assignment 6 2v×c ∩ {(x,c) ∀c} {(x,c)} if (y,cy)∈In & (z,cz)∈In, {(x,cy ⊕ cz)}Data-Flow Analysis for Simple Constant Propagation Simple constant propagation: analysis is “reaching constants”– D:– ӹ:– F:– Kill(x←. . .) = – Gen(x←c) = – Gen(x←y⊕z) = – . . .CS553 Lecture Using Static Single Assignment 7 Reaching constants for simple constant propagation– D:– ӹ:– 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 (cont) c if cy=Iny & cz=Inz, then cy ⊕ cz, else ⊤or ⊥¨⊥0 1 2 3-3-2-1. . .. . .Using tuples of latticesCS553 Lecture Using Static Single Assignment 8Initialization for Reaching Constants Pessimistic– Each variable is initially set to 󲰥in data-flow analysis– Forces merges at loop headers to go to 󲰥conservatively Optimistic– Each variable is initially set to ⊤in data-flow analysis– What assumption is being made when optimistic reaching constants isperformed?CS553 Lecture Using Static Single Assignment 9Implementing 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 mayhave to be propagated throughirrelevant nodesx = 1y = xCS553 Lecture Using Static Single Assignment 10Sparse Simple Constant Propagation Reif and Lewis algorithm Reif and Lewis [1977]– 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 = xCS553 Lecture Using Static Single Assignment 11worklist = 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+zCS553 Lecture Using Static Single Assignment 12Sparse Simple Constants Complexity– O(E’) = O(EV), E’ is number of SSA edges– O(n) in practiceCS553 Lecture Using Static Single Assignment 13Other Uses of 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 + 3uddusCS553 Lecture Using Static Single Assignment 14Other Uses of SSA (cont) Induction variable identification– Induction variables– Variables whose values form an arithmetic progression– Useful for strength reduction and loop transformations Why bother?– Automatic parallelization, . . . Simple approach– Search for statements of the form, i = i + c– Examine ud-chains to make sure there are no other defs of i in the loop– Does not catch all induction variables. Examples?CS553 Lecture Using Static Single Assignment 15Induction Variable Identification (cont) 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 induction variables– Variables that are defined once in a loop as a linear function ofanother induction variable– j = c1 * i + c2– j = i /c1 + c2, where c1 and c2 are loop invariantCS553 Lecture Using Static Single Assignment 16Induction Variable Identification (cont) Informal SSA-based Algorithm– Build the SSA representation– Iterate from innermost CFG loop to outermost loop– Find SSA cycles– Each cycle may be a basic induction variable if a variable in acycle is a function of loop invariants and its value on the currentiteration– Find derived induction variables as functions of loop invariants, itsvalue on the current iteration, and basic induction variablesCS553 Lecture Using Static Single Assignment 17Induction Variable Identification (cont) Informal SSA-based Algorithm (cont)– Determining whether a variable is a function of loop invariants and itsvalue on the current iteration– The φ -function in the cycle will have as one of its inputs a deffrom inside the loop and a def from outside the loop– The def inside the loop will be part of the cycle and will get oneoperand from the φ -function and all others will be loop invariant– The operation will be plus, minus, or unary minusCS553 Lecture Using Static Single Assignment 18Next Time Reading– Ch 8.10, 12.4 Lecture– Redundancy