lect. SSA construction © Seth Copen Goldstein 2001-7 115-745SSADominatorsCopyright © Seth Copen Goldstein 2001-7lect. SSA construction © Seth Copen Goldstein 2001-7 2The Φ function• Φ merges multiple definitions along multiple control paths into a single definition.• At a BB with p predecessors, there are p arguments to the Φ function.xnew← Φ(x1, x1, x1, … , xp)• How do we choose which xito use?– Most compiler writers don’t really care!– If we care, use moves on each incoming edge(Or, as in pegasus use a mux)lect. SSA construction © Seth Copen Goldstein 2001-7 3Trivial SSA• Each assignment generates a fresh variable.• At each join point insert Φ functions for all live variables.y ← xy ← 2z ← y + xx ← 1y1← x1y2← 2x2← Φ(x1,x1)y3← Φ(y1,y2)z1← y3+ x2x1← 1Way too many Φfunctions inserted.lect. SSA construction © Seth Copen Goldstein 2001-7 4Minimal SSA• Each assignment generates a fresh variable.• At each join point insert Φ functions for all variables with multiple outstanding defs.y ← xy ← 2z ← y + xx ← 1y1← x1y2← 2y3← Φ(y1,y2)z1← y3+ x1x1← 1lect. SSA construction © Seth Copen Goldstein 2001-7 5When do we insert Φ?11156 781323491012CFGIf there is a def of a in block 5, which nodes need a Φ()?Note: a is implicitly defined in block 1lect. SSA construction © Seth Copen Goldstein 2001-7 6When do we insert Φ?•Insert a Φ function for variable A in block Z iff:– A was defined more than once before(i.e., A defined in X and Y AND X ≠ Y)– Z is the first block that joins the paths from X to Z and Y to Z• Entry block implicitly defines of all vars•Note: A = Φ(…) is a def of Alect. SSA construction © Seth Copen Goldstein 2001-7 7When do we insert Φ?•Insert a Φ function for variable A in block Z iff:– A was defined more than once before(i.e., A defined in X and Y AND X ≠ Y)– There exists a non-empty path from x to z, Pxz, and a non-empty from y to z, Pyzs.t.•Pxz∩ Pyz= { z }•z ∉ Pxqor z ∉ Pyrwhere Pxz= Pxq→ z and Pyz= Pyr→ z• Entry block implicitly defines all vars•Note: A = Φ(…) is a def of Alect. SSA construction © Seth Copen Goldstein 2001-7 8When do we insert Φ?11156 78132349101211156 781323491012lect. SSA construction © Seth Copen Goldstein 2001-7 9When do we insert Φ?11156 78132349101211156 781323491012lect. SSA construction © Seth Copen Goldstein 2001-7 10When do we insert Φ?11156 78132349101211156 781323491012lect. SSA construction © Seth Copen Goldstein 2001-7 11When do we insert Φ?11156 78132349101211156 781323491012lect. SSA construction © Seth Copen Goldstein 2001-7 12Def-use property of SSA•If xiis used in x ← Φ(…, xi, …), thenNO BBs in any path from BB(xi) to BB(Φ) include def of x except BB(Xi) and BB(Φ)• If x is used in y ← … x …, then no BBs in path from BB(x) to BB(y) define x except BB(x)11156 781323491012Another way to say this:Definitions dominate useslect. SSA construction © Seth Copen Goldstein 2001-7 13Dominance Property of SSA• In SSA definitions dominate uses.–If xiis 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)• Use this for an efficient alg to convert to SSA11156 781323491012lect. SSA construction © Seth Copen Goldstein 2001-7 14A little side trip• Computing dominators• d dom n iff every path from s to n goes through d• n dom n for all n• Some definitions:– immediate dominator: d idom n iff•d ≠ n•d domn• d doesn’t dominate any other dominator of n– strictly dominates: s sdom n iff•s domn•s ≠ nlect. SSA construction © Seth Copen Goldstein 2001-7 15Examples•d domniff every path from Entry to n contains d.1 dom 1 ; 1 dom 2 ; 1 dom 3 ; 1 dom 4 ; 2 dom 2 ; 2 dom 3 ; 2 dom 4 ; 3 dom 3 ; 4 dom 4•s strictly dominates n, (s sdom n), iff s dom n and s ≠ n.1 sdom 2 ; 1 sdom 3 ; 1 sdom 4 ;2 sdom 3 ; 2 sdom 4•d immediately dominates n, d=idom(n), iff d sdom n and there is no node x such that d dom x and x dom n.1 idom 2 ; 2 idom 3; 2 idom 4BB 1BB 2BB 3 BB 4EntryExit(adapted from: http://www.eecg.toronto.edu/~voss/ece540/lect. SSA construction © Seth Copen Goldstein 2001-7 16Properties of dominators• idom(n) is unique• The dominance relation is a partial ordering; that is, it is reflexive, anti-symmetric and transitive:–reflexive: x dom x– anti-symmetric: x dom y and y dom x → x = y–transitive : x dom y and y dom z → x dom z(adapted from: http://www.eecg.toronto.edu/~voss/ece540/lect. SSA construction © Seth Copen Goldstein 2001-7 17The dominator tree• One can represent dominators in a cfg as a tree of immediate dominators.• In dominator tree, edge from parent to child if parent idom child in the cfg• The set of dominators of a node are the nodes from the root to the node.BB 1BB 2BB 3 BB 4EntryBB 1BB 2BB 3 BB 4EntryExitlect. SSA construction © Seth Copen Goldstein 2001-7 18Computing Dominators• d dom n iff every path from s to n goes through d• Note: n dom n for all n• If s dom d & d ≠ n & pi∈ pred(n) & d dom pi,then d dom n•• How can we use this?np1p2 pksdlect. SSA construction © Seth Copen Goldstein 2001-7 19Computing Dominators• d dom n iff every path from s to n goes through d• Note: n dom n for all n• If s dom d & d ≠ n & pi∈ pred(n) & d dom pi,then d dom n•np1p2 pksdUI)()(}{)(npredppdomnndom∈=lect. SSA construction © Seth Copen Goldstein 2001-7 20Simple iterative alg• dom(Entry) = Entryfor all other nodes, n, dom(n) = all nodeschanged = truewhile (changed) {changed = falsefor each n, n≠Entry {old = dom(n)if (dom(n) != old) changed = true}}UI)()(}{)(npredppdomnndom∈=(adapted from: http://www.eecg.toronto.edu/~voss/ece540/lect. SSA construction © Seth Copen Goldstein 2001-7 21ExampleDOM (Entry) = {Entry}DOM (1) = {Entry,1}DOM (2) = {Entry,1,2}DOM (3) = {Entry,1,2,3}DOM (4) = {Entry,1,2,3,4}DOM (5) = {Entry,1,2,3,4,5}DOM (6) = {Entry,1,2,3,4,5,6}DOM (7) = {Entry,1,2,3,4,5,7}DOM (8) = {Entry,1,2,3,4,5,8}DOM (9) = {Entry,1,2,3,4,9}DOM (10) = {Entry,1,2,10)BB 1BB 2BB 3BB 4BB 5BB 6BB 8BB 9BB 10ExitBB 7Entry(Borrowed from: http://www.eecg.toronto.edu/~voss/ece540/lect. SSA construction © Seth Copen Goldstein 2001-7 22Finding immediate dominators• idom(n) dominates n, isn’t n, and, doesn’t strictly dominate any other sdom n• Init idom(n) to nodes
View Full Document