1CS553 Lecture Static Single Assignment Form 1SSA Technicalities Last Time– Introduced SSA Today– Aliasing in SSA– Building SSA– Backward data-flow analyses– Transforming SSA back to code Next Time– Using SSACS553 Lecture Static Single Assignment Form 2SSA Merging Definitions– φ-functions merge multiple reaching definitions Examplev2 := φ(v0,v1)...v2...4v0 :=...2 v1 :=...312CS553 Lecture Static Single Assignment Form 3Technicalities How can we handle aliasing in SSA? How do we generate SSA? What about backward data-flow analysis problems? How do we generate code from SSA?CS553 Lecture Static Single Assignment Form 4SSA and Aliasing Simple solution– treat all of memory as one variable– MayDef and MayUse semantics degrade analysis accuracy Add more functions into SSA to represent semantics– MayUse and MayDef can be added before the computation of SSA– Optimizations on SSA must handle the semantics of MayUse and MayDef[Chow et al. 96]3CS553 Lecture Static Single Assignment Form 5Transformation to SSA Form Two steps– Insert φ-functions– Rename variablesCS553 Lecture Static Single Assignment Form 6Where Do We Place φ-Functions? Basic Rule– If two distinct (non-null) paths x→z and y→z converge at node z, andnodes x and y contain definitions of variable v, then aφ-function for v is inserted at zv3 := φ(v1,v2)...v3...zv1 :=...xv2 :=...y4CS553 Lecture Static Single Assignment Form 7Approaches to Placing φ-Functions Minimal– As few as possible subject to the basic rule Briggs-Minimal– Same as minimal, except v must be live across some edge of the CFG Pruned– Same as minimal, except dead φ-functions are not inserted What’s the difference between Briggs Minimal and Pruned SSA?CS553 Lecture Static Single Assignment Form 8Briggs Minimal vs. Pruned Briggs Minimal will add aφ function because v is liveacross the blue edge, but PrunedSSA will not because the φfunction is dead = φ(v0,v1)v = = vv = = v = vv = = vv = = v Neither Briggs Minimal norPruned SSA will place aφ function in this case because vis not live across any CFG edge Why would we ever use Briggs Minimal instead of Pruned SSA?5CS553 Lecture Static Single Assignment Form 9Machinery for Placing φ-Functions Recall Dominators– d dom i if all paths from entry to node i include d– d sdom i if d dom i and d≠i Dominance Frontiers– The dominance frontier of a node d is the set of nodes that are “justbarely” not dominated by d; i.e., the set of nodes n, such that– d dominates a predecessor p of n, and– d does not strictly dominate n– DF(d) = {n | ∃p∈pred(n), d dom p and d !sdom n} Notational Convenience– DF(S) = ∪s∈S DF(s)dientryd dom iCS553 Lecture Static Single Assignment Form 10Nodes in Dom(5) {4, 5, 12, 13}5Dominance Frontier Example23 6 7891110DF(d) = {n | ∃p∈pred(n), d dom p and d !sdom n}Dom(5) = {5, 6, 7, 8}541312What’s significant about the Dominance Frontier?1In SSA form, definitions must dominate usesDF(5) =6CS553 Lecture Static Single Assignment Form 11 {10} {10} {6} {10} {6} {6,10}SSA Exercise65 103 4v := ...8v := ...9v :=...2 71DF(8) =DF(9) =DF(2) =DF({8,9}) =DF(10) =DF({2,8,9,10}) =DF(d) = {n | ∃p∈pred(n), d dom p and d !sdom n}1 23v4:=φ(v1,v2)v5:=φ(v3,v4)CS553 Lecture Static Single Assignment Form 12Variable Renaming Basic idea– When we see a variable on the LHS, create a new name for it– When we see a variable on the RHS, use appropriate subscriptx = = xx = = x x0 = = x0x1 = = x1 Easy for straightline code Use a stack when there’s control flow– For each use of x, find the definition of x that dominates itx0 =x = = x = x0Traverse the dominance tree7CS553 Lecture Static Single Assignment Form 13Backward Analyses vs. Forward AnalysesFor forward data-flow analysis, at phi node apply meet functionFor backward data-flow analysis?v2 := φ(v0,v1)...v2...4v0 :=...2v1 :=...31CS553 Lecture Static Single Assignment Form 14Static Single Information Form (SSI)Ananian’s Masters Thesis, 1997 MIT8CS553 Lecture Static Single Assignment Form 15Transformation 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)CS553 Lecture Static Single Assignment Form 16Concepts SSA and aliasing– Simple involves may uses and defs to a single memory variable– Other methods insert more functions into SSA– For both optimization codes must handle semantics SSA construction– Place phi nodes– Variable renaming Backward data-flow analyses can use SSI modification to SSA Transformation from SSA to executable code depends on theoptimizations dead-code elimination and copy propagation9CS553 Lecture Static Single Assignment Form 17Next Time Assignments– Schedule for project 2 due Wednesday– HW1 is due Friday Lecture– Using