Debian Codegraph @

go/ir/dom.go

raw
1 // Copyright 2013 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
4
5 package ir
6
7 // This file defines algorithms related to dominance.
8
9 // Dominator tree construction ----------------------------------------
10 //
11 // We use the algorithm described in Lengauer & Tarjan. 1979. A fast
12 // algorithm for finding dominators in a flowgraph.
13 // https://doi.acm.org/10.1145/357062.357071
14 //
15 // We also apply the optimizations to SLT described in Georgiadis et
16 // al, Finding Dominators in Practice, JGAA 2006,
17 // https://jgaa.info/accepted/2006/GeorgiadisTarjanWerneck2006.10.1.pdf
18 // to avoid the need for buckets of size > 1.
19
20 import (
21 "bytes"
22 "fmt"
23 "io"
24 "math/big"
25 "os"
26 "sort"
27 )
28
29 // Idom returns the block that immediately dominates b:
30 // its parent in the dominator tree, if any.
31 // The entry node (b.Index==0) does not have a parent.
32 func (b *BasicBlock) Idom() *BasicBlock { return b.dom.idom }
33
34 // Dominees returns the list of blocks that b immediately dominates:
35 // its children in the dominator tree.
36 func (b *BasicBlock) Dominees() []*BasicBlock { return b.dom.children }
37
38 // Dominates reports whether b dominates c.
39 func (b *BasicBlock) Dominates(c *BasicBlock) bool {
40 return b.dom.pre <= c.dom.pre && c.dom.post <= b.dom.post
41 }
42
43 type byDomPreorder []*BasicBlock
44
45 func (a byDomPreorder) Len() int { return len(a) }
46 func (a byDomPreorder) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
47 func (a byDomPreorder) Less(i, j int) bool { return a[i].dom.pre < a[j].dom.pre }
48
49 // DomPreorder returns a new slice containing the blocks of f in
50 // dominator tree preorder.
51 func (f *Function) DomPreorder() []*BasicBlock {
52 n := len(f.Blocks)
53 order := make(byDomPreorder, n)
54 copy(order, f.Blocks)
55 sort.Sort(order)
56 return order
57 }
58
59 // domInfo contains a BasicBlock's dominance information.
60 type domInfo struct {
61 idom *BasicBlock // immediate dominator (parent in domtree)
62 children []*BasicBlock // nodes immediately dominated by this one
63 pre, post int32 // pre- and post-order numbering within domtree
64 }
65
66 // buildDomTree computes the dominator tree of f using the LT algorithm.
67 // Precondition: all blocks are reachable (e.g. optimizeBlocks has been run).
68 func buildDomTree(fn *Function) {
69 // The step numbers refer to the original LT paper; the
70 // reordering is due to Georgiadis.
71
72 // Clear any previous domInfo.
73 for _, b := range fn.Blocks {
74 b.dom = domInfo{}
75 }
76
77 idoms := make([]*BasicBlock, len(fn.Blocks))
78
79 order := make([]*BasicBlock, 0, len(fn.Blocks))
80 seen := fn.blockset(0)
81 var dfs func(b *BasicBlock)
82 dfs = func(b *BasicBlock) {
83 if !seen.Add(b) {
84 return
85 }
86 for _, succ := range b.Succs {
87 dfs(succ)
88 }
89 if fn.fakeExits.Has(b) {
90 dfs(fn.Exit)
91 }
92 order = append(order, b)
93 b.post = len(order) - 1
94 }
95 dfs(fn.Blocks[0])
96
97 for i := 0; i < len(order)/2; i++ {
98 o := len(order) - i - 1
99 order[i], order[o] = order[o], order[i]
100 }
101
102 idoms[fn.Blocks[0].Index] = fn.Blocks[0]
103 changed := true
104 for changed {
105 changed = false
106 // iterate over all nodes in reverse postorder, except for the
107 // entry node
108 for _, b := range order[1:] {
109 var newIdom *BasicBlock
110 do := func(p *BasicBlock) {
111 if idoms[p.Index] == nil {
112 return
113 }
114 if newIdom == nil {
115 newIdom = p
116 } else {
117 finger1 := p
118 finger2 := newIdom
119 for finger1 != finger2 {
120 for finger1.post < finger2.post {
121 finger1 = idoms[finger1.Index]
122 }
123 for finger2.post < finger1.post {
124 finger2 = idoms[finger2.Index]
125 }
126 }
127 newIdom = finger1
128 }
129 }
130 for _, p := range b.Preds {
131 do(p)
132 }
133 if b == fn.Exit {
134 for _, p := range fn.Blocks {
135 if fn.fakeExits.Has(p) {
136 do(p)
137 }
138 }
139 }
140
141 if idoms[b.Index] != newIdom {
142 idoms[b.Index] = newIdom
143 changed = true
144 }
145 }
146 }
147
148 for i, b := range idoms {
149 fn.Blocks[i].dom.idom = b
150 if b == nil {
151 // malformed CFG
152 continue
153 }
154 if i == b.Index {
155 continue
156 }
157 b.dom.children = append(b.dom.children, fn.Blocks[i])
158 }
159
160 numberDomTree(fn.Blocks[0], 0, 0)
161
162 // printDomTreeDot(os.Stderr, fn) // debugging
163 // printDomTreeText(os.Stderr, root, 0) // debugging
164
165 if fn.Prog.mode&SanityCheckFunctions != 0 {
166 sanityCheckDomTree(fn)
167 }
168 }
169
170 // buildPostDomTree is like buildDomTree, but builds the post-dominator tree instead.
171 func buildPostDomTree(fn *Function) {
172 // The step numbers refer to the original LT paper; the
173 // reordering is due to Georgiadis.
174
175 // Clear any previous domInfo.
176 for _, b := range fn.Blocks {
177 b.pdom = domInfo{}
178 }
179
180 idoms := make([]*BasicBlock, len(fn.Blocks))
181
182 order := make([]*BasicBlock, 0, len(fn.Blocks))
183 seen := fn.blockset(0)
184 var dfs func(b *BasicBlock)
185 dfs = func(b *BasicBlock) {
186 if !seen.Add(b) {
187 return
188 }
189 for _, pred := range b.Preds {
190 dfs(pred)
191 }
192 if b == fn.Exit {
193 for _, p := range fn.Blocks {
194 if fn.fakeExits.Has(p) {
195 dfs(p)
196 }
197 }
198 }
199 order = append(order, b)
200 b.post = len(order) - 1
201 }
202 dfs(fn.Exit)
203
204 for i := 0; i < len(order)/2; i++ {
205 o := len(order) - i - 1
206 order[i], order[o] = order[o], order[i]
207 }
208
209 idoms[fn.Exit.Index] = fn.Exit
210 changed := true
211 for changed {
212 changed = false
213 // iterate over all nodes in reverse postorder, except for the
214 // exit node
215 for _, b := range order[1:] {
216 var newIdom *BasicBlock
217 do := func(p *BasicBlock) {
218 if idoms[p.Index] == nil {
219 return
220 }
221 if newIdom == nil {
222 newIdom = p
223 } else {
224 finger1 := p
225 finger2 := newIdom
226 for finger1 != finger2 {
227 for finger1.post < finger2.post {
228 finger1 = idoms[finger1.Index]
229 }
230 for finger2.post < finger1.post {
231 finger2 = idoms[finger2.Index]
232 }
233 }
234 newIdom = finger1
235 }
236 }
237 for _, p := range b.Succs {
238 do(p)
239 }
240 if fn.fakeExits.Has(b) {
241 do(fn.Exit)
242 }
243
244 if idoms[b.Index] != newIdom {
245 idoms[b.Index] = newIdom
246 changed = true
247 }
248 }
249 }
250
251 for i, b := range idoms {
252 fn.Blocks[i].pdom.idom = b
253 if b == nil {
254 // malformed CFG
255 continue
256 }
257 if i == b.Index {
258 continue
259 }
260 b.pdom.children = append(b.pdom.children, fn.Blocks[i])
261 }
262
263 numberPostDomTree(fn.Exit, 0, 0)
264
265 // printPostDomTreeDot(os.Stderr, fn) // debugging
266 // printPostDomTreeText(os.Stderr, fn.Exit, 0) // debugging
267
268 if fn.Prog.mode&SanityCheckFunctions != 0 { // XXX
269 sanityCheckDomTree(fn) // XXX
270 }
271 }
272
273 // numberDomTree sets the pre- and post-order numbers of a depth-first
274 // traversal of the dominator tree rooted at v. These are used to
275 // answer dominance queries in constant time.
276 func numberDomTree(v *BasicBlock, pre, post int32) (int32, int32) {
277 v.dom.pre = pre
278 pre++
279 for _, child := range v.dom.children {
280 pre, post = numberDomTree(child, pre, post)
281 }
282 v.dom.post = post
283 post++
284 return pre, post
285 }
286
287 // numberPostDomTree sets the pre- and post-order numbers of a depth-first
288 // traversal of the post-dominator tree rooted at v. These are used to
289 // answer post-dominance queries in constant time.
290 func numberPostDomTree(v *BasicBlock, pre, post int32) (int32, int32) {
291 v.pdom.pre = pre
292 pre++
293 for _, child := range v.pdom.children {
294 pre, post = numberPostDomTree(child, pre, post)
295 }
296 v.pdom.post = post
297 post++
298 return pre, post
299 }
300
301 // Testing utilities ----------------------------------------
302
303 // sanityCheckDomTree checks the correctness of the dominator tree
304 // computed by the LT algorithm by comparing against the dominance
305 // relation computed by a naive Kildall-style forward dataflow
306 // analysis (Algorithm 10.16 from the "Dragon" book).
307 func sanityCheckDomTree(f *Function) {
308 n := len(f.Blocks)
309
310 // D[i] is the set of blocks that dominate f.Blocks[i],
311 // represented as a bit-set of block indices.
312 D := make([]big.Int, n)
313
314 one := big.NewInt(1)
315
316 // all is the set of all blocks; constant.
317 var all big.Int
318 all.Set(one).Lsh(&all, uint(n)).Sub(&all, one)
319
320 // Initialization.
321 for i := range f.Blocks {
322 if i == 0 {
323 // A root is dominated only by itself.
324 D[i].SetBit(&D[0], 0, 1)
325 } else {
326 // All other blocks are (initially) dominated
327 // by every block.
328 D[i].Set(&all)
329 }
330 }
331
332 // Iteration until fixed point.
333 for changed := true; changed; {
334 changed = false
335 for i, b := range f.Blocks {
336 if i == 0 {
337 continue
338 }
339 // Compute intersection across predecessors.
340 var x big.Int
341 x.Set(&all)
342 for _, pred := range b.Preds {
343 x.And(&x, &D[pred.Index])
344 }
345 if b == f.Exit {
346 for _, p := range f.Blocks {
347 if f.fakeExits.Has(p) {
348 x.And(&x, &D[p.Index])
349 }
350 }
351 }
352 x.SetBit(&x, i, 1) // a block always dominates itself.
353 if D[i].Cmp(&x) != 0 {
354 D[i].Set(&x)
355 changed = true
356 }
357 }
358 }
359
360 // Check the entire relation. O(n^2).
361 ok := true
362 for i := range n {
363 for j := range n {
364 b, c := f.Blocks[i], f.Blocks[j]
365 actual := b.Dominates(c)
366 expected := D[j].Bit(i) == 1
367 if actual != expected {
368 fmt.Fprintf(os.Stderr, "dominates(%s, %s)==%t, want %t\n", b, c, actual, expected)
369 ok = false
370 }
371 }
372 }
373
374 preorder := f.DomPreorder()
375 for _, b := range f.Blocks {
376 if got := preorder[b.dom.pre]; got != b {
377 fmt.Fprintf(os.Stderr, "preorder[%d]==%s, want %s\n", b.dom.pre, got, b)
378 ok = false
379 }
380 }
381
382 if !ok {
383 panic("sanityCheckDomTree failed for " + f.String())
384 }
385
386 }
387
388 // Printing functions ----------------------------------------
389
390 // printDomTree prints the dominator tree as text, using indentation.
391 //
392 //lint:ignore U1000 used during debugging
393 func printDomTreeText(buf *bytes.Buffer, v *BasicBlock, indent int) {
394 fmt.Fprintf(buf, "%*s%s\n", 4*indent, "", v)
395 for _, child := range v.dom.children {
396 printDomTreeText(buf, child, indent+1)
397 }
398 }
399
400 // printDomTreeDot prints the dominator tree of f in AT&T GraphViz
401 // (.dot) format.
402 //
403 //lint:ignore U1000 used during debugging
404 func printDomTreeDot(buf io.Writer, f *Function) {
405 fmt.Fprintln(buf, "//", f)
406 fmt.Fprintln(buf, "digraph domtree {")
407 for i, b := range f.Blocks {
408 v := b.dom
409 fmt.Fprintf(buf, "\tn%d [label=\"%s (%d, %d)\",shape=\"rectangle\"];\n", v.pre, b, v.pre, v.post)
410 // TODO(adonovan): improve appearance of edges
411 // belonging to both dominator tree and CFG.
412
413 // Dominator tree edge.
414 if i != 0 {
415 fmt.Fprintf(buf, "\tn%d -> n%d [style=\"solid\",weight=100];\n", v.idom.dom.pre, v.pre)
416 }
417 // CFG edges.
418 for _, pred := range b.Preds {
419 fmt.Fprintf(buf, "\tn%d -> n%d [style=\"dotted\",weight=0];\n", pred.dom.pre, v.pre)
420 }
421
422 if f.fakeExits.Has(b) {
423 fmt.Fprintf(buf, "\tn%d -> n%d [style=\"dotted\",weight=0,color=red];\n", b.dom.pre, f.Exit.dom.pre)
424 }
425 }
426 fmt.Fprintln(buf, "}")
427 }
428
429 // printDomTree prints the dominator tree as text, using indentation.
430 //
431 //lint:ignore U1000 used during debugging
432 func printPostDomTreeText(buf io.Writer, v *BasicBlock, indent int) {
433 fmt.Fprintf(buf, "%*s%s\n", 4*indent, "", v)
434 for _, child := range v.pdom.children {
435 printPostDomTreeText(buf, child, indent+1)
436 }
437 }
438
439 // printDomTreeDot prints the dominator tree of f in AT&T GraphViz
440 // (.dot) format.
441 //
442 //lint:ignore U1000 used during debugging
443 func printPostDomTreeDot(buf io.Writer, f *Function) {
444 fmt.Fprintln(buf, "//", f)
445 fmt.Fprintln(buf, "digraph pdomtree {")
446 for _, b := range f.Blocks {
447 v := b.pdom
448 fmt.Fprintf(buf, "\tn%d [label=\"%s (%d, %d)\",shape=\"rectangle\"];\n", v.pre, b, v.pre, v.post)
449 // TODO(adonovan): improve appearance of edges
450 // belonging to both dominator tree and CFG.
451
452 // Dominator tree edge.
453 if b != f.Exit {
454 fmt.Fprintf(buf, "\tn%d -> n%d [style=\"solid\",weight=100];\n", v.idom.pdom.pre, v.pre)
455 }
456 // CFG edges.
457 for _, pred := range b.Preds {
458 fmt.Fprintf(buf, "\tn%d -> n%d [style=\"dotted\",weight=0];\n", pred.pdom.pre, v.pre)
459 }
460
461 if f.fakeExits.Has(b) {
462 fmt.Fprintf(buf, "\tn%d -> n%d [style=\"dotted\",weight=0,color=red];\n", b.dom.pre, f.Exit.dom.pre)
463 }
464 }
465 fmt.Fprintln(buf, "}")
466 }