LEFT | RIGHT |
(no file at all) | |
| 1 package ssa |
| 2 |
| 3 // This file defines algorithms related to dominance. |
| 4 |
| 5 // Dominator tree construction ---------------------------------------- |
| 6 // |
| 7 // We use the algorithm described in Lengauer & Tarjan. 1979. A fast |
| 8 // algorithm for finding dominators in a flowgraph. |
| 9 // http://doi.acm.org/10.1145/357062.357071 |
| 10 // |
| 11 // We also apply the optimizations to SLT described in Georgiadis et |
| 12 // al, Finding Dominators in Practice, JGAA 2006, |
| 13 // http://jgaa.info/accepted/2006/GeorgiadisTarjanWerneck2006.10.1.pdf |
| 14 // to avoid the need for buckets of size > 1. |
| 15 |
| 16 import ( |
| 17 "fmt" |
| 18 "io" |
| 19 "math/big" |
| 20 "os" |
| 21 ) |
| 22 |
| 23 // domNode represents a node in the dominator tree. |
| 24 // |
| 25 // TODO(adonovan): export this, when ready. |
| 26 type domNode struct { |
| 27 Block *BasicBlock // the basic block; n.Block.dom == n |
| 28 Idom *domNode // immediate dominator (parent in dominator tree) |
| 29 Children []*domNode // nodes dominated by this one |
| 30 Level int // level number of node within tree; zero for root |
| 31 Pre, Post int // pre- and post-order numbering within dominator
tree |
| 32 |
| 33 // Working state for Lengauer-Tarjan algorithm |
| 34 // (during which Pre is repurposed for CFG DFS preorder number). |
| 35 // TODO(adonovan): opt: measure allocating these as temps. |
| 36 semi *domNode // semidominator |
| 37 parent *domNode // parent in DFS traversal of CFG |
| 38 ancestor *domNode // ancestor with least sdom |
| 39 } |
| 40 |
| 41 // ltDfs implements the depth-first search part of the LT algorithm. |
| 42 func ltDfs(v *domNode, i int, preorder []*domNode) int { |
| 43 preorder[i] = v |
| 44 v.Pre = i // For now: DFS preorder of spanning tree of CFG |
| 45 i++ |
| 46 v.semi = v |
| 47 v.ancestor = nil |
| 48 for _, succ := range v.Block.Succs { |
| 49 if w := succ.dom; w.semi == nil { |
| 50 w.parent = v |
| 51 i = ltDfs(w, i, preorder) |
| 52 } |
| 53 } |
| 54 return i |
| 55 } |
| 56 |
| 57 // ltEval implements the EVAL part of the LT algorithm. |
| 58 func ltEval(v *domNode) *domNode { |
| 59 // TODO(adonovan): opt: do path compression per simple LT. |
| 60 u := v |
| 61 for ; v.ancestor != nil; v = v.ancestor { |
| 62 if v.semi.Pre < u.semi.Pre { |
| 63 u = v |
| 64 } |
| 65 } |
| 66 return u |
| 67 } |
| 68 |
| 69 // ltLink implements the LINK part of the LT algorithm. |
| 70 func ltLink(v, w *domNode) { |
| 71 w.ancestor = v |
| 72 } |
| 73 |
| 74 // buildDomTree computes the dominator tree of f using the LT algorithm. |
| 75 // Precondition: all blocks are reachable (e.g. optimizeBlocks has been run). |
| 76 // |
| 77 func buildDomTree(f *Function) { |
| 78 // The step numbers refer to the original LT paper; the |
| 79 // reodering is due to Georgiadis. |
| 80 |
| 81 // Initialize domNode nodes. |
| 82 for _, b := range f.Blocks { |
| 83 dom := b.dom |
| 84 if dom == nil { |
| 85 dom = &domNode{Block: b} |
| 86 b.dom = dom |
| 87 } else { |
| 88 dom.Block = b // reuse |
| 89 } |
| 90 } |
| 91 |
| 92 // Step 1. Number vertices by depth-first preorder. |
| 93 n := len(f.Blocks) |
| 94 preorder := make([]*domNode, n) |
| 95 root := f.Blocks[0].dom |
| 96 ltDfs(root, 0, preorder) |
| 97 |
| 98 buckets := make([]*domNode, n) |
| 99 copy(buckets, preorder) |
| 100 |
| 101 // In reverse preorder... |
| 102 for i := n - 1; i > 0; i-- { |
| 103 w := preorder[i] |
| 104 |
| 105 // Step 3. Implicitly define the immediate dominator of each nod
e. |
| 106 for v := buckets[i]; v != w; v = buckets[v.Pre] { |
| 107 u := ltEval(v) |
| 108 if u.semi.Pre < i { |
| 109 v.Idom = u |
| 110 } else { |
| 111 v.Idom = w |
| 112 } |
| 113 } |
| 114 |
| 115 // Step 2. Compute the semidominators of all nodes. |
| 116 w.semi = w.parent |
| 117 for _, pred := range w.Block.Preds { |
| 118 v := pred.dom |
| 119 u := ltEval(v) |
| 120 if u.semi.Pre < w.semi.Pre { |
| 121 w.semi = u.semi |
| 122 } |
| 123 } |
| 124 |
| 125 ltLink(w.parent, w) |
| 126 |
| 127 if w.parent == w.semi { |
| 128 w.Idom = w.parent |
| 129 } else { |
| 130 buckets[i] = buckets[w.semi.Pre] |
| 131 buckets[w.semi.Pre] = w |
| 132 } |
| 133 } |
| 134 |
| 135 // The final 'Step 3' is now outside the loop. |
| 136 for v := buckets[0]; v != root; v = buckets[v.Pre] { |
| 137 v.Idom = root |
| 138 } |
| 139 |
| 140 // Step 4. Explicitly define the immediate dominator of each |
| 141 // node, in preorder. |
| 142 for _, w := range preorder[1:] { |
| 143 if w == root { |
| 144 w.Idom = nil |
| 145 } else { |
| 146 if w.Idom != w.semi { |
| 147 w.Idom = w.Idom.Idom |
| 148 } |
| 149 // Calculate Children relation as inverse of Idom. |
| 150 w.Idom.Children = append(w.Idom.Children, w) |
| 151 } |
| 152 |
| 153 // Clear working state. |
| 154 w.semi = nil |
| 155 w.parent = nil |
| 156 w.ancestor = nil |
| 157 } |
| 158 |
| 159 numberDomTree(root, 0, 0, 0) |
| 160 |
| 161 // printDomTreeDot(os.Stderr, f) // debugging |
| 162 // printDomTreeText(os.Stderr, root, 0) // debugging |
| 163 |
| 164 if f.Prog.mode&SanityCheckFunctions != 0 { |
| 165 sanityCheckDomTree(f) |
| 166 } |
| 167 } |
| 168 |
| 169 // numberDomTree sets the pre- and post-order numbers of a depth-first |
| 170 // traversal of the dominator tree rooted at v. These are used to |
| 171 // answer dominance queries in constant time. Also, it sets the level |
| 172 // numbers (zero for the root) used for frontier computation. |
| 173 // |
| 174 func numberDomTree(v *domNode, pre, post, level int) (int, int) { |
| 175 v.Level = level |
| 176 level++ |
| 177 v.Pre = pre |
| 178 pre++ |
| 179 for _, child := range v.Children { |
| 180 pre, post = numberDomTree(child, pre, post, level) |
| 181 } |
| 182 v.Post = post |
| 183 post++ |
| 184 return pre, post |
| 185 } |
| 186 |
| 187 // dominates returns true if b dominates c. |
| 188 // Requires that dominance information is up-to-date. |
| 189 // |
| 190 func dominates(b, c *BasicBlock) bool { |
| 191 return b.dom.Pre <= c.dom.Pre && c.dom.Post <= b.dom.Post |
| 192 } |
| 193 |
| 194 // Testing utilities ---------------------------------------- |
| 195 |
| 196 // sanityCheckDomTree checks the correctness of the dominator tree |
| 197 // computed by the LT algorithm by comparing against the dominance |
| 198 // relation computed by a naive Kildall-style forward dataflow |
| 199 // analysis (Algorithm 10.16 from the "Dragon" book). |
| 200 // |
| 201 func sanityCheckDomTree(f *Function) { |
| 202 n := len(f.Blocks) |
| 203 |
| 204 // D[i] is the set of blocks that dominate f.Blocks[i], |
| 205 // represented as a bit-set of block indices. |
| 206 D := make([]big.Int, n) |
| 207 |
| 208 one := big.NewInt(1) |
| 209 |
| 210 // all is the set of all blocks; constant. |
| 211 var all big.Int |
| 212 all.Set(one).Lsh(&all, uint(n)).Sub(&all, one) |
| 213 |
| 214 // Initialization. |
| 215 for i := range f.Blocks { |
| 216 if i == 0 { |
| 217 // The root is dominated only by itself. |
| 218 D[i].SetBit(&D[0], 0, 1) |
| 219 } else { |
| 220 // All other blocks are (initially) dominated |
| 221 // by every block. |
| 222 D[i].Set(&all) |
| 223 } |
| 224 } |
| 225 |
| 226 // Iteration until fixed point. |
| 227 for changed := true; changed; { |
| 228 changed = false |
| 229 for i, b := range f.Blocks { |
| 230 if i == 0 { |
| 231 continue |
| 232 } |
| 233 // Compute intersection across predecessors. |
| 234 var x big.Int |
| 235 x.Set(&all) |
| 236 for _, pred := range b.Preds { |
| 237 x.And(&x, &D[pred.Index]) |
| 238 } |
| 239 x.SetBit(&x, i, 1) // a block always dominates itself. |
| 240 if D[i].Cmp(&x) != 0 { |
| 241 D[i].Set(&x) |
| 242 changed = true |
| 243 } |
| 244 } |
| 245 } |
| 246 |
| 247 // Check the entire relation. O(n^2). |
| 248 ok := true |
| 249 for i := 0; i < n; i++ { |
| 250 for j := 0; j < n; j++ { |
| 251 b, c := f.Blocks[i], f.Blocks[j] |
| 252 actual := dominates(b, c) |
| 253 expected := D[j].Bit(i) == 1 |
| 254 if actual != expected { |
| 255 fmt.Fprintf(os.Stderr, "dominates(%s, %s)==%t, w
ant %t\n", b, c, actual, expected) |
| 256 ok = false |
| 257 } |
| 258 } |
| 259 } |
| 260 if !ok { |
| 261 panic("sanityCheckDomTree failed for " + f.FullName()) |
| 262 } |
| 263 } |
| 264 |
| 265 // Printing functions ---------------------------------------- |
| 266 |
| 267 // printDomTree prints the dominator tree as text, using indentation. |
| 268 func printDomTreeText(w io.Writer, v *domNode, indent int) { |
| 269 fmt.Fprintf(w, "%*s%s\n", 4*indent, "", v.Block) |
| 270 for _, child := range v.Children { |
| 271 printDomTreeText(w, child, indent+1) |
| 272 } |
| 273 } |
| 274 |
| 275 // printDomTreeDot prints the dominator tree of f in AT&T GraphViz |
| 276 // (.dot) format. |
| 277 func printDomTreeDot(w io.Writer, f *Function) { |
| 278 fmt.Fprintln(w, "//", f.FullName()) |
| 279 fmt.Fprintln(w, "digraph domtree {") |
| 280 for i, b := range f.Blocks { |
| 281 v := b.dom |
| 282 fmt.Fprintf(w, "\tn%d [label=\"%s (%d, %d)\",shape=\"rectangle\"
];\n", v.Pre, b, v.Pre, v.Post) |
| 283 // TODO(adonovan): improve appearance of edges |
| 284 // belonging to both dominator tree and CFG. |
| 285 |
| 286 // Dominator tree edge. |
| 287 if i != 0 { |
| 288 fmt.Fprintf(w, "\tn%d -> n%d [style=\"solid\",weight=100
];\n", v.Idom.Pre, v.Pre) |
| 289 } |
| 290 // CFG edges. |
| 291 for _, pred := range b.Preds { |
| 292 fmt.Fprintf(w, "\tn%d -> n%d [style=\"dotted\",weight=0]
;\n", pred.dom.Pre, v.Pre) |
| 293 } |
| 294 } |
| 295 fmt.Fprintln(w, "}") |
| 296 } |
LEFT | RIGHT |