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

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: diff -r 9ff35ff05de6 https://go.googlecode.com/hg/ 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:
Left: Side by side diff | Download
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
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
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
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 }
LEFTRIGHT

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