summaryrefslogtreecommitdiffstats
path: root/src/cmd/compile/internal/ssa/dom.go
blob: 39ba4d1647b222534cfc6266cb1ebced62066b10 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
// Copyright 2015 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package ssa

// This file contains code to compute the dominator tree
// of a control-flow graph.

// postorder computes a postorder traversal ordering for the
// basic blocks in f. Unreachable blocks will not appear.
func postorder(f *Func) []*Block {
	return postorderWithNumbering(f, nil)
}

type blockAndIndex struct {
	b     *Block
	index int // index is the number of successor edges of b that have already been explored.
}

// postorderWithNumbering provides a DFS postordering.
// This seems to make loop-finding more robust.
func postorderWithNumbering(f *Func, ponums []int32) []*Block {
	seen := f.Cache.allocBoolSlice(f.NumBlocks())
	defer f.Cache.freeBoolSlice(seen)

	// result ordering
	order := make([]*Block, 0, len(f.Blocks))

	// stack of blocks and next child to visit
	// A constant bound allows this to be stack-allocated. 32 is
	// enough to cover almost every postorderWithNumbering call.
	s := make([]blockAndIndex, 0, 32)
	s = append(s, blockAndIndex{b: f.Entry})
	seen[f.Entry.ID] = true
	for len(s) > 0 {
		tos := len(s) - 1
		x := s[tos]
		b := x.b
		if i := x.index; i < len(b.Succs) {
			s[tos].index++
			bb := b.Succs[i].Block()
			if !seen[bb.ID] {
				seen[bb.ID] = true
				s = append(s, blockAndIndex{b: bb})
			}
			continue
		}
		s = s[:tos]
		if ponums != nil {
			ponums[b.ID] = int32(len(order))
		}
		order = append(order, b)
	}
	return order
}

type linkedBlocks func(*Block) []Edge

func dominators(f *Func) []*Block {
	preds := func(b *Block) []Edge { return b.Preds }
	succs := func(b *Block) []Edge { return b.Succs }

	//TODO: benchmark and try to find criteria for swapping between
	// dominatorsSimple and dominatorsLT
	return f.dominatorsLTOrig(f.Entry, preds, succs)
}

// dominatorsLTOrig runs Lengauer-Tarjan to compute a dominator tree starting at
// entry and using predFn/succFn to find predecessors/successors to allow
// computing both dominator and post-dominator trees.
func (f *Func) dominatorsLTOrig(entry *Block, predFn linkedBlocks, succFn linkedBlocks) []*Block {
	// Adapted directly from the original TOPLAS article's "simple" algorithm

	maxBlockID := entry.Func.NumBlocks()
	scratch := f.Cache.allocIDSlice(7 * maxBlockID)
	defer f.Cache.freeIDSlice(scratch)
	semi := scratch[0*maxBlockID : 1*maxBlockID]
	vertex := scratch[1*maxBlockID : 2*maxBlockID]
	label := scratch[2*maxBlockID : 3*maxBlockID]
	parent := scratch[3*maxBlockID : 4*maxBlockID]
	ancestor := scratch[4*maxBlockID : 5*maxBlockID]
	bucketHead := scratch[5*maxBlockID : 6*maxBlockID]
	bucketLink := scratch[6*maxBlockID : 7*maxBlockID]

	// This version uses integers for most of the computation,
	// to make the work arrays smaller and pointer-free.
	// fromID translates from ID to *Block where that is needed.
	fromID := f.Cache.allocBlockSlice(maxBlockID)
	defer f.Cache.freeBlockSlice(fromID)
	for _, v := range f.Blocks {
		fromID[v.ID] = v
	}
	idom := make([]*Block, maxBlockID)

	// Step 1. Carry out a depth first search of the problem graph. Number
	// the vertices from 1 to n as they are reached during the search.
	n := f.dfsOrig(entry, succFn, semi, vertex, label, parent)

	for i := n; i >= 2; i-- {
		w := vertex[i]

		// step2 in TOPLAS paper
		for _, e := range predFn(fromID[w]) {
			v := e.b
			if semi[v.ID] == 0 {
				// skip unreachable predecessor
				// not in original, but we're using existing pred instead of building one.
				continue
			}
			u := evalOrig(v.ID, ancestor, semi, label)
			if semi[u] < semi[w] {
				semi[w] = semi[u]
			}
		}

		// add w to bucket[vertex[semi[w]]]
		// implement bucket as a linked list implemented
		// in a pair of arrays.
		vsw := vertex[semi[w]]
		bucketLink[w] = bucketHead[vsw]
		bucketHead[vsw] = w

		linkOrig(parent[w], w, ancestor)

		// step3 in TOPLAS paper
		for v := bucketHead[parent[w]]; v != 0; v = bucketLink[v] {
			u := evalOrig(v, ancestor, semi, label)
			if semi[u] < semi[v] {
				idom[v] = fromID[u]
			} else {
				idom[v] = fromID[parent[w]]
			}
		}
	}
	// step 4 in toplas paper
	for i := ID(2); i <= n; i++ {
		w := vertex[i]
		if idom[w].ID != vertex[semi[w]] {
			idom[w] = idom[idom[w].ID]
		}
	}

	return idom
}

// dfsOrig performs a depth first search over the blocks starting at entry block
// (in arbitrary order).  This is a de-recursed version of dfs from the
// original Tarjan-Lengauer TOPLAS article.  It's important to return the
// same values for parent as the original algorithm.
func (f *Func) dfsOrig(entry *Block, succFn linkedBlocks, semi, vertex, label, parent []ID) ID {
	n := ID(0)
	s := make([]*Block, 0, 256)
	s = append(s, entry)

	for len(s) > 0 {
		v := s[len(s)-1]
		s = s[:len(s)-1]
		// recursing on v

		if semi[v.ID] != 0 {
			continue // already visited
		}
		n++
		semi[v.ID] = n
		vertex[n] = v.ID
		label[v.ID] = v.ID
		// ancestor[v] already zero
		for _, e := range succFn(v) {
			w := e.b
			// if it has a dfnum, we've already visited it
			if semi[w.ID] == 0 {
				// yes, w can be pushed multiple times.
				s = append(s, w)
				parent[w.ID] = v.ID // keep overwriting this till it is visited.
			}
		}
	}
	return n
}

// compressOrig is the "simple" compress function from LT paper.
func compressOrig(v ID, ancestor, semi, label []ID) {
	if ancestor[ancestor[v]] != 0 {
		compressOrig(ancestor[v], ancestor, semi, label)
		if semi[label[ancestor[v]]] < semi[label[v]] {
			label[v] = label[ancestor[v]]
		}
		ancestor[v] = ancestor[ancestor[v]]
	}
}

// evalOrig is the "simple" eval function from LT paper.
func evalOrig(v ID, ancestor, semi, label []ID) ID {
	if ancestor[v] == 0 {
		return v
	}
	compressOrig(v, ancestor, semi, label)
	return label[v]
}

func linkOrig(v, w ID, ancestor []ID) {
	ancestor[w] = v
}

// dominatorsSimple computes the dominator tree for f. It returns a slice
// which maps block ID to the immediate dominator of that block.
// Unreachable blocks map to nil. The entry block maps to nil.
func dominatorsSimple(f *Func) []*Block {
	// A simple algorithm for now
	// Cooper, Harvey, Kennedy
	idom := make([]*Block, f.NumBlocks())

	// Compute postorder walk
	post := f.postorder()

	// Make map from block id to order index (for intersect call)
	postnum := f.Cache.allocIntSlice(f.NumBlocks())
	defer f.Cache.freeIntSlice(postnum)
	for i, b := range post {
		postnum[b.ID] = i
	}

	// Make the entry block a self-loop
	idom[f.Entry.ID] = f.Entry
	if postnum[f.Entry.ID] != len(post)-1 {
		f.Fatalf("entry block %v not last in postorder", f.Entry)
	}

	// Compute relaxation of idom entries
	for {
		changed := false

		for i := len(post) - 2; i >= 0; i-- {
			b := post[i]
			var d *Block
			for _, e := range b.Preds {
				p := e.b
				if idom[p.ID] == nil {
					continue
				}
				if d == nil {
					d = p
					continue
				}
				d = intersect(d, p, postnum, idom)
			}
			if d != idom[b.ID] {
				idom[b.ID] = d
				changed = true
			}
		}
		if !changed {
			break
		}
	}
	// Set idom of entry block to nil instead of itself.
	idom[f.Entry.ID] = nil
	return idom
}

// intersect finds the closest dominator of both b and c.
// It requires a postorder numbering of all the blocks.
func intersect(b, c *Block, postnum []int, idom []*Block) *Block {
	// TODO: This loop is O(n^2). It used to be used in nilcheck,
	// see BenchmarkNilCheckDeep*.
	for b != c {
		if postnum[b.ID] < postnum[c.ID] {
			b = idom[b.ID]
		} else {
			c = idom[c.ID]
		}
	}
	return b
}