Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(2390)

Delta Between Two Patch Sets: src/pkg/exp/ssa/dom.go

Issue 7229074: code review 7229074: exp/ssa: build fully pruned SSA form. (Closed)
Left Patch Set: Created 11 years, 1 month ago
Right Patch Set: diff -r 734059df2768 https://code.google.com/p/go/ Created 11 years, 1 month ago
Left:
Right:
Use n/p to move between diff chunks; N/P to move between comments. Please Sign in to add in-line comments.
Jump to:
Right: Side by side diff | Download
« no previous file with change/comment | « src/pkg/exp/ssa/doc.go ('k') | src/pkg/exp/ssa/func.go » ('j') | no next file with change/comment »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
LEFTRIGHT
(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 }
LEFTRIGHT

Powered by Google App Engine
RSS Feeds Recent Issues | This issue
This is Rietveld f62528b