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