1CS553 Lecture Value Numbering 2Reuse Optimization Idea− Eliminate redundant operations in the dynamic execution of instructions How do redundancies arise?− Loop invariant code (e.g., index calculation for arrays)− Sequence of similar operations (e.g., method lookup)− Lightning frequently strikes twice Types of reuse optimization− Value numbering− Common subexpression elimination− Partial redundancy eliminationCS553 Lecture Value Numbering 3Local Value Numbering Idea− Each variable, expression, and constant is assigned a unique number− When we encounter a variable, expression or constant, see if it’s alreadybeen assigned a number− If so, use the value for that number− If not, assign a new number− Same number ⇒ same value Example a := b + c d := bb := a e := d + c b → #1 c → #2 b + c is #1 + # 2 → #3 a → #3 d → #1 d + c is #1 + # 2 → #3 e → #3 #3 a2CS553 Lecture Value Numbering 5Global Value Numbering How do we handle control flow?w = 8x = 8w = 5x = 5y = w+1z = x+1w → #2x → #2. . .w → #1x → #1. . .CS553 Lecture Value Numbering 6Global Value Numbering (cont) Idea [Alpern, Wegman, and Zadeck 1988]− Partition program variables into congruence classes− All variables in a particular congruence class have the same value− SSA form is helpful Approaches to computing congruence classes− Pessimistic− Assume no variables are congruent (start with n classes)− Iteratively coalesce classes that are determined to be congruent− Optimistic− Assume all variables are congruent (start with one class)− Iteratively partition variables that contradict assumption− Slower but better results3CS553 Lecture Value Numbering 7Role of SSA Form SSA form is helpful− Allows us to avoid data-flow analysis− Variables correspond to valuesa = b. . .a = c. . .a = da not congruent toanythinga1 = b. . .a2 = c. . .a3 = dCongruence classes:{a1,b}, {a2,c}, {a3,d}CS553 Lecture Value Numbering 8Basis Idea− If x and y are congruent then f(x) and f(y) are congruent− Use this fact to combine (pessimistic) or split (optimistic) classes Problem− This is not true for φ-functions Solution: Label φ-functions with join pointta = atb = bx = f(a,b)y = f(ta,tb)x and y arecongruenta1 = x1a2 = y1a3 = φ (a1,a2)b1 = x1b2 = y1b3 = φ (b1,b2)a1 & b1 congruent?a2 & b2 congruent?a3 & b3 congruent?nmnm4CS553 Lecture Value Numbering 9Pessimistic Global Value Numbering Idea− Initially each variable is in its own congruence class− Consider each assignment statement s (reverse postorder in CFG)− Update LHS value number with hash of RHS− Identical value number ⇒ congruence Why reverse postorder?− Ensures that when we consider an assignment statement, we have alreadyconsidered definitions that reach the RHS operandsabecfdPostorder: d, c, e, b, f, aCS553 Lecture Value Numbering 10Algorithmfor each assignment of the form: “x = f(a,b)”ValNum[x] ← UniqueValue()for each assignment of the form: “x = f(a,b)” (in reverse postorder)ValNum[x] ← Hash(f ⊕ ValNum[a] ⊕ ValNum[b])w2 = a1x2 = a1w1 = b1x1 = b1w3 = φn(w1,w2)x3 = φn(x1,x2)y1 = w3+i1z1 = x3+i1i1 = 1a1#1b1#2i1#3w1#4x1#5w2#6x2#7w3#8x3#9y1#10z1#11#2#2#1#1φn(#2,#1) → #12φn(#2,#1) → #12+(#12,#3) → #13+(#12,#3) → #135CS553 Lecture Value Numbering 11Snag! Problem− Our algorithm assumes that we consider operands before variables thatdepend upon it− Can’t deal with code containing loops! Solution− Ignore back edges− Make conservative (worst case) assumption for previously unseenvariable (i.e., assume its in it’s own congruence class)CS553 Lecture Value Numbering 12Optimistic Global Value Numbering Idea− Initially all variables in one congruence class− Split congruence classes when evidence of non-congruence arises− Variables that are computed using different functions− Variables that are computed using functions with non-congruentoperands6CS553 Lecture Value Numbering 13Splitting Initially− Variables computed using the same function are placed in the same class Iteratively− Split classes when correspondingoperands are in different classes− Example: a1 and c1 are congruent,but e1 is congruent to neitherx1 = f(a1,b1). . .y1 = f(c1,d1). . .z1 = f(e1,f1)x1 y1 z1Pa1 c1QP’CS553 Lecture Value Numbering 14Splitting (cont) Definitions− Suppose P and Q are sets representing congruence classes− Q splits P for each i into two sets− P \i Q contains variables in P whose ith operand is in Q− P /i Q contains variables in P whose ith operand is not in Q− Q properly splits P if neither resulting set is emptyx1 = f(a1,b1). . .y1 = f(c1,d1). . .z1 = f(e1,f1)x1 y1 z1a1 c1QP \1 Q P /1 QP7CS553 Lecture Value Numbering 15Algorithmworklist ← ∅for each function fCf ← ∅for each assignment of the form “x = f(a,b)”Cf ← Cf ∪ { x }worklist ← worklist ∪ {Cf}CC ← CC ∪ {Cf}while worklist ≠ ∅Delete some D from worklistfor each class C properly split by D (at operand i)CC ← CC – Cworklist ← worklist – CCreate new congruence classes Cj ←{C \i D} and Ck ← {C /i D}CC ← CC ∪ Cj ∪ Ckworklist ← worklist ∪ Cj ∪ CkNote: see paper for optimizationCS553 Lecture Value Numbering 16Examplex0 = 1y0 = 2x1 = x0+1y1 = y0+1z1 = x0+1S0{x0}S1{y0}S2{x1,y1,z1}S3{x1,z1}S4{y1}SSA codeCongruence classesWorklist: S0={x0}, S1={y0}, S2={x1,y1,z1}, S3={x1,z1}, S4={y1}S0 psplit S0? S0 psplit S1? S0 psplit S2? yes! S2 \1 S0 = {x1,z1} = S3 S2 /1 S0 = {y1} = S4 no no8CS553 Lecture Value Numbering 17Comparing Optimistic and Pessimistic Differences− Handling of loops− Pessimistic makes worst-case assumptions on back edges− Optimistic requires actual contradiction to split classesw0 = 5x0 = 5w1=φ(w0,w2)x1=φ(x0,x2)w2 = w1+1x2 = x1+1CS553 Lecture Value Numbering 18Role of SSA Single global result− Single def reaches each use− No data (flow value) at each point No data flow analysis− Optimistic: Iterate over congruence classes, not CFG nodes− Pessimistic: Visit each assignment once φ-functions− Make data-flow merging explicit− Treat like normal functions9CS553 Lecture Value Numbering 19Next Time Lecture− Common-Subexpression Elimination Study Suggestion− Read Alpern and Zadeck 1992 Chapter about Value Numbering− Do the examples in Muchnick Section 12.4 and examples in paper usingthe others