1School of Computer ScienceSSA: Single StaticAssignment15-745: Optimizing CompilersFebruary 16, 2006School of Computer SciencePreviously… Def-Use Chains…for (i=0; i++; i<10) {… = … i …;…}for (i=j; i++; i<20) {… = … i …}School of Computer ScienceDef-Use chains are expensive…switch (i) {case 0: x=3;case 1: x=1;case 2: x=6;case 3: x=7;default: x = 11;}switch (j) {case 0: y=x+7;case 1: y=x+4;case 2: y=x-2;case 3: y=x+1;default: y=x+9;}…School of Computer Science…switch (i) {case 0: x=3; break;case 1: x=1; break;case 2: x=6; break;case 3: x=7; break;default: x = 11;}switch (j) {case 0: y=x+7;case 1: y=x+4;case 2: y=x-2;case 3: y=x+1;default: y=x+9;}…Def-Use chains are expensiveIn general,N defsM uses⇒ O(NM) space and timeA solution is to limit each varto ONE def site2School of Computer ScienceDef-Use chains are expensive…switch (i) {case 0: x=3; break;case 1: x=1; break;case 2: x=6; break;case 3: x=7; break;default: x = 11;}x1 is one of the above x’sswitch (j) {case 0: y=x1+7;case 1: y=x1+4;case 2: y=x1-2;case 3: y=x1+1;default: y=x1+9;}…A solution is to limit each varto ONE def siteSchool of Computer ScienceSSA• Static single assignment is an IR whereevery variable is assigned a value at mostoncea ← x + y a ← b + 2d ← x + aa ← b + ca ← a + 1Not SSANot SSANot SSANot SSASchool of Computer ScienceAdvantages of SSA• Makes du-chains explicit– every definition knows its uses– every use knows its single definition• Makes dataflow optimizations– easier– faster• For most optimizations reduces space/timerequirementsSchool of Computer ScienceSimple SSA Optimizations• Dead Code Elimination– a definition with no uses (and no ????)• Constant Propagation– a use with a constant definitiona ← 1c ← a + ba ← x / y3School of Computer ScienceSSA History• Developed by Wegman, Zadeck, Alpern,and Rosen in 1988– and improved by Cytron, Ferrante, Wegman,and Zadeck in 1989• New to gcc 4.0, used in ORC, used in bothIBM and Sun Java JIT compilersSchool of Computer ScienceConverting to SSA• Easy for a basic block:– assign to a fresh variable at each stmt.– Each use uses the most recently defined var.a ← x + yb ← a + xa ← b + 2c ← y + 1a ← c + aSchool of Computer ScienceConverting to SSA• Easy for a basic block:– assign to a fresh variable at each stmt.– Each use uses the most recently defined var.a ← x + yb ← a + xa ← b + 2c ← y + 1a ← c + aa1 ← x + yb1 ← a1 + xa2 ← b1 + 2c1 ← y + 1a3 ← c1 + a2What about at joins in the CFG?School of Computer Sciencea1 ← x + yb1 ← a1 + xMerging at Joinsa2 ← b + 2c2 ← y + 1c ← 12if (i) {a ← x + yb ← a + x} else {a ← b + 2c ← y + 1}a ← c + ac1 ← 12if (i)a4 ← c? + a?Use a notional fiction: A Φ function4School of Computer ScienceMerging at Joinsa2 ← b + 2c2 ← y + 1c1 ← 12if (i)a1 ← x + yb1 ← a1 + xa3 ← Φ(a1,a2)c3 ← Φ(c1,c2)b2 ← Φ(b1, ?)a4 ← c3 + a3School of Computer ScienceThe Φ function•Φ merges multiple definitions along multiple controlpaths into a single definition•At a BB with p predecessors, there are p argumentsto the Φ functionxnew ← Φ(x1, x2, x3, … , xp)•How does phi choose which xi to use?– We don’t really care!– If we care, use moves on each incoming edgeSchool of Computer Science“Implementing” Φa2 ← b + 2c2 ← y + 1a3 ← a2c3 ← c2c1 ← 12if (i)a1 ← x + yb1 ← a1 + xa3 ← a1c3 ← c1a3 ← Φ(a1,a2)c3 ← Φ(c1,c2)a4 ← c3 + a3School of Computer ScienceTrivial SSA• Each assignment generates a fresh variable• At each join point insert Φ functions for all livevariablesy ← xy ← 2z ← y + xx ← 1y1 ← x1y2 ← 2x2 ← Φ(x1,x1)y3 ← Φ(y1,y2)z1 ← y3 + x2`x1 ← 1Way too many Φfunctions inserted.x2 ← Φ(x1,x1)5School of Computer ScienceMinimal SSA• Each assignment generates a fresh variable.• At each join point insert Φ functions for allvariables with multiple outstanding defs.y ← x y ← 2z ← y + xx ← 1y1 ← x1y2 ← 2y3 ← Φ(y1,y2)z1 ← y3 + x1x1 ← 1School of Computer ScienceAnother Examplea ← 0b ← a + 1c ← c + ba ← b * 2a < Nreturn cSchool of Computer ScienceAnother Examplea ← 0b ← a + 1c ← c + ba ← b * 2a < Nreturn ca1 ← 0a3 ← Φ(a1,a2)c3 ← Φ(c1,c2)b2 ← a3 + 1c2 ← c3 + b2a2 ← b2 * 2a2 < Nreturn c2Notice use of c1entry block has implicit def of all variablesSchool of Computer ScienceWhen do we insert Φ?11156 781323491012CFGIf there is a def of a inblock 5, which nodes needa Φ()?Alternatively, which nodesdon’t need a Φ()?6School of Computer ScienceWhen do we insert Φ?• We insert a Φ function for variable a in block Z iff:– There exist blocks X and Y, X ≠ Y, such that a is defined in X and Y– a is defined in more than one block– There exists a non-empty path from X to Z, PXZ, and a non-emptyfrom Y to Z, PYZ s.t.• PXZ ∩ PYZ = { Z }– paths PXZ and PYZ have no nodes in common except for Z• Z ∉ PXQor Z ∉ PXR where PXZ = PXQ → Z and PYZ = PXR → Z– if Z is in contained elsewhere in PXZ before the end, it is only foundat the end of PYZ and vice versaThis is the path-convergence criterionSchool of Computer ScienceDominance Property of SSA• In SSA definitions dominate uses.– If xi is used in x ← Φ(…, xi, …), thenBB(xi) dominates ith pred of BB(PHI)– If x is used in y ← … x …,then BB(x) dominates BB(y)• We can use dominance information to getan efficient algorithm for converting to SSASchool of Computer ScienceDominatorsa dom bblock a dominates block b if everypossible execution path from entry tob includes aentry dominates everything0 dominates everything but entry1 dominates 2 and 1045231entryexitDominators are useful inidentifying “natural” loopsSchool of Computer ScienceDefinitionsa sdom bIf a and b are different blocks and a domb, we say that a strictly dominates ba idom bIf a sdom b, and there is no c such that asdom c and c sdom b, we say that a isthe immediate dominator of b045231entryexit7School of Computer ScienceProperties of DomDominance is a partial order on the blocks of the flowgraph, i.e.,1. Reflexivity: a dom a for all a2. Anti-symmetry: a dom b and b dom a implies a = b3. Transitivity: a dom b and b dom c implies a dom cNOTE: there may be blocks a and b such that neithera dom b or b dom a holds.The dominators of each node n are linearly ordered bythe dom relation. The dominators of n appear in thislinear order on any path from the initial
View Full Document
Unlocking...