1
2
3
4
5 package ssa
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 import (
21 "bytes"
22 "fmt"
23 "math/big"
24 "os"
25 "sort"
26 )
27
28
29
30
31
32 func (b *BasicBlock) Idom() *BasicBlock { return b.dom.idom }
33
34
35
36 func (b *BasicBlock) Dominees() []*BasicBlock { return b.dom.children }
37
38
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
50
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
60 type domInfo struct {
61 idom *BasicBlock
62 children []*BasicBlock
63 pre, post int32
64 }
65
66
67
68 type ltState struct {
69
70 sdom []*BasicBlock
71 parent []*BasicBlock
72 ancestor []*BasicBlock
73 }
74
75
76 func (lt *ltState) dfs(v *BasicBlock, i int32, preorder []*BasicBlock) int32 {
77 preorder[i] = v
78 v.dom.pre = i
79 i++
80 lt.sdom[v.Index] = v
81 lt.link(nil, v)
82 for _, w := range v.Succs {
83 if lt.sdom[w.Index] == nil {
84 lt.parent[w.Index] = v
85 i = lt.dfs(w, i, preorder)
86 }
87 }
88 return i
89 }
90
91
92 func (lt *ltState) eval(v *BasicBlock) *BasicBlock {
93
94 u := v
95 for ; lt.ancestor[v.Index] != nil; v = lt.ancestor[v.Index] {
96 if lt.sdom[v.Index].dom.pre < lt.sdom[u.Index].dom.pre {
97 u = v
98 }
99 }
100 return u
101 }
102
103
104 func (lt *ltState) link(v, w *BasicBlock) {
105 lt.ancestor[w.Index] = v
106 }
107
108
109
110 func buildDomTree(f *Function) {
111
112
113
114
115 for _, b := range f.Blocks {
116 b.dom = domInfo{}
117 }
118
119 n := len(f.Blocks)
120
121
122 space := make([]*BasicBlock, 5*n)
123 lt := ltState{
124 sdom: space[0:n],
125 parent: space[n : 2*n],
126 ancestor: space[2*n : 3*n],
127 }
128
129
130 preorder := space[3*n : 4*n]
131 root := f.Blocks[0]
132 prenum := lt.dfs(root, 0, preorder)
133 recover := f.Recover
134 if recover != nil {
135 lt.dfs(recover, prenum, preorder)
136 }
137
138 buckets := space[4*n : 5*n]
139 copy(buckets, preorder)
140
141
142 for i := int32(n) - 1; i > 0; i-- {
143 w := preorder[i]
144
145
146 for v := buckets[i]; v != w; v = buckets[v.dom.pre] {
147 u := lt.eval(v)
148 if lt.sdom[u.Index].dom.pre < i {
149 v.dom.idom = u
150 } else {
151 v.dom.idom = w
152 }
153 }
154
155
156 lt.sdom[w.Index] = lt.parent[w.Index]
157 for _, v := range w.Preds {
158 u := lt.eval(v)
159 if lt.sdom[u.Index].dom.pre < lt.sdom[w.Index].dom.pre {
160 lt.sdom[w.Index] = lt.sdom[u.Index]
161 }
162 }
163
164 lt.link(lt.parent[w.Index], w)
165
166 if lt.parent[w.Index] == lt.sdom[w.Index] {
167 w.dom.idom = lt.parent[w.Index]
168 } else {
169 buckets[i] = buckets[lt.sdom[w.Index].dom.pre]
170 buckets[lt.sdom[w.Index].dom.pre] = w
171 }
172 }
173
174
175 for v := buckets[0]; v != root; v = buckets[v.dom.pre] {
176 v.dom.idom = root
177 }
178
179
180
181 for _, w := range preorder[1:] {
182 if w == root || w == recover {
183 w.dom.idom = nil
184 } else {
185 if w.dom.idom != lt.sdom[w.Index] {
186 w.dom.idom = w.dom.idom.dom.idom
187 }
188
189 w.dom.idom.dom.children = append(w.dom.idom.dom.children, w)
190 }
191 }
192
193 pre, post := numberDomTree(root, 0, 0)
194 if recover != nil {
195 numberDomTree(recover, pre, post)
196 }
197
198
199
200
201 if f.Prog.mode&SanityCheckFunctions != 0 {
202 sanityCheckDomTree(f)
203 }
204 }
205
206
207
208
209 func numberDomTree(v *BasicBlock, pre, post int32) (int32, int32) {
210 v.dom.pre = pre
211 pre++
212 for _, child := range v.dom.children {
213 pre, post = numberDomTree(child, pre, post)
214 }
215 v.dom.post = post
216 post++
217 return pre, post
218 }
219
220
221
222
223
224
225
226 func sanityCheckDomTree(f *Function) {
227 n := len(f.Blocks)
228
229
230
231 D := make([]big.Int, n)
232
233 one := big.NewInt(1)
234
235
236 var all big.Int
237 all.Set(one).Lsh(&all, uint(n)).Sub(&all, one)
238
239
240 for i, b := range f.Blocks {
241 if i == 0 || b == f.Recover {
242
243 D[i].SetBit(&D[0], 0, 1)
244 } else {
245
246
247 D[i].Set(&all)
248 }
249 }
250
251
252 for changed := true; changed; {
253 changed = false
254 for i, b := range f.Blocks {
255 if i == 0 || b == f.Recover {
256 continue
257 }
258
259 var x big.Int
260 x.Set(&all)
261 for _, pred := range b.Preds {
262 x.And(&x, &D[pred.Index])
263 }
264 x.SetBit(&x, i, 1)
265 if D[i].Cmp(&x) != 0 {
266 D[i].Set(&x)
267 changed = true
268 }
269 }
270 }
271
272
273
274 ok := true
275 for i := 0; i < n; i++ {
276 for j := 0; j < n; j++ {
277 b, c := f.Blocks[i], f.Blocks[j]
278 if c == f.Recover {
279 continue
280 }
281 actual := b.Dominates(c)
282 expected := D[j].Bit(i) == 1
283 if actual != expected {
284 fmt.Fprintf(os.Stderr, "dominates(%s, %s)==%t, want %t\n", b, c, actual, expected)
285 ok = false
286 }
287 }
288 }
289
290 preorder := f.DomPreorder()
291 for _, b := range f.Blocks {
292 if got := preorder[b.dom.pre]; got != b {
293 fmt.Fprintf(os.Stderr, "preorder[%d]==%s, want %s\n", b.dom.pre, got, b)
294 ok = false
295 }
296 }
297
298 if !ok {
299 panic("sanityCheckDomTree failed for " + f.String())
300 }
301
302 }
303
304
305
306
307 func printDomTreeText(buf *bytes.Buffer, v *BasicBlock, indent int) {
308 fmt.Fprintf(buf, "%*s%s\n", 4*indent, "", v)
309 for _, child := range v.dom.children {
310 printDomTreeText(buf, child, indent+1)
311 }
312 }
313
314
315
316 func printDomTreeDot(buf *bytes.Buffer, f *Function) {
317 fmt.Fprintln(buf, "//", f)
318 fmt.Fprintln(buf, "digraph domtree {")
319 for i, b := range f.Blocks {
320 v := b.dom
321 fmt.Fprintf(buf, "\tn%d [label=\"%s (%d, %d)\",shape=\"rectangle\"];\n", v.pre, b, v.pre, v.post)
322
323
324
325
326 if i != 0 {
327 fmt.Fprintf(buf, "\tn%d -> n%d [style=\"solid\",weight=100];\n", v.idom.dom.pre, v.pre)
328 }
329
330 for _, pred := range b.Preds {
331 fmt.Fprintf(buf, "\tn%d -> n%d [style=\"dotted\",weight=0];\n", pred.dom.pre, v.pre)
332 }
333 }
334 fmt.Fprintln(buf, "}")
335 }
336
View as plain text