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
|
// Copyright 2016 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
import "fmt"
// A SparseTreeMap encodes a subset of nodes within a tree
// used for sparse-ancestor queries.
//
// Combined with a SparseTreeHelper, this supports an Insert
// to add a tree node to the set and a Find operation to locate
// the nearest tree ancestor of a given node such that the
// ancestor is also in the set.
//
// Given a set of blocks {B1, B2, B3} within the dominator tree, established
// by stm.Insert()ing B1, B2, B3, etc, a query at block B
// (performed with stm.Find(stm, B, adjust, helper))
// will return the member of the set that is the nearest strict
// ancestor of B within the dominator tree, or nil if none exists.
// The expected complexity of this operation is the log of the size
// the set, given certain assumptions about sparsity (the log complexity
// could be guaranteed with additional data structures whose constant-
// factor overhead has not yet been justified.)
//
// The adjust parameter allows positioning of the insertion
// and lookup points within a block -- one of
// AdjustBefore, AdjustWithin, AdjustAfter,
// where lookups at AdjustWithin can find insertions at
// AdjustBefore in the same block, and lookups at AdjustAfter
// can find insertions at either AdjustBefore or AdjustWithin
// in the same block. (Note that this assumes a gappy numbering
// such that exit number or exit number is separated from its
// nearest neighbor by at least 3).
//
// The Sparse Tree lookup algorithm is described by
// Paul F. Dietz. Maintaining order in a linked list. In
// Proceedings of the Fourteenth Annual ACM Symposium on
// Theory of Computing, pages 122–127, May 1982.
// and by
// Ben Wegbreit. Faster retrieval from context trees.
// Communications of the ACM, 19(9):526–529, September 1976.
type SparseTreeMap RBTint32
// A SparseTreeHelper contains indexing and allocation data
// structures common to a collection of SparseTreeMaps, as well
// as exposing some useful control-flow-related data to other
// packages, such as gc.
type SparseTreeHelper struct {
Sdom []SparseTreeNode // indexed by block.ID
Po []*Block // exported data; the blocks, in a post-order
Dom []*Block // exported data; the dominator of this block.
Ponums []int32 // exported data; Po[Ponums[b.ID]] == b; the index of b in Po
}
// NewSparseTreeHelper returns a SparseTreeHelper for use
// in the gc package, for example in phi-function placement.
func NewSparseTreeHelper(f *Func) *SparseTreeHelper {
dom := f.Idom()
ponums := make([]int32, f.NumBlocks())
po := postorderWithNumbering(f, ponums)
return makeSparseTreeHelper(newSparseTree(f, dom), dom, po, ponums)
}
func (h *SparseTreeHelper) NewTree() *SparseTreeMap {
return &SparseTreeMap{}
}
func makeSparseTreeHelper(sdom SparseTree, dom, po []*Block, ponums []int32) *SparseTreeHelper {
helper := &SparseTreeHelper{Sdom: []SparseTreeNode(sdom),
Dom: dom,
Po: po,
Ponums: ponums,
}
return helper
}
// A sparseTreeMapEntry contains the data stored in a binary search
// data structure indexed by (dominator tree walk) entry and exit numbers.
// Each entry is added twice, once keyed by entry-1/entry/entry+1 and
// once keyed by exit+1/exit/exit-1.
//
// Within a sparse tree, the two entries added bracket all their descendant
// entries within the tree; the first insertion is keyed by entry number,
// which comes before all the entry and exit numbers of descendants, and
// the second insertion is keyed by exit number, which comes after all the
// entry and exit numbers of the descendants.
type sparseTreeMapEntry struct {
index *SparseTreeNode // references the entry and exit numbers for a block in the sparse tree
block *Block // TODO: store this in a separate index.
data interface{}
sparseParent *sparseTreeMapEntry // references the nearest ancestor of this block in the sparse tree.
adjust int32 // at what adjustment was this node entered into the sparse tree? The same block may be entered more than once, but at different adjustments.
}
// Insert creates a definition within b with data x.
// adjust indicates where in the block should be inserted:
// AdjustBefore means defined at a phi function (visible Within or After in the same block)
// AdjustWithin means defined within the block (visible After in the same block)
// AdjustAfter means after the block (visible within child blocks)
func (m *SparseTreeMap) Insert(b *Block, adjust int32, x interface{}, helper *SparseTreeHelper) {
rbtree := (*RBTint32)(m)
blockIndex := &helper.Sdom[b.ID]
if blockIndex.entry == 0 {
// assert unreachable
return
}
// sp will be the sparse parent in this sparse tree (nearest ancestor in the larger tree that is also in this sparse tree)
sp := m.findEntry(b, adjust, helper)
entry := &sparseTreeMapEntry{index: blockIndex, block: b, data: x, sparseParent: sp, adjust: adjust}
right := blockIndex.exit - adjust
_ = rbtree.Insert(right, entry)
left := blockIndex.entry + adjust
_ = rbtree.Insert(left, entry)
// This newly inserted block may now be the sparse parent of some existing nodes (the new sparse children of this block)
// Iterate over nodes bracketed by this new node to correct their parent, but not over the proper sparse descendants of those nodes.
_, d := rbtree.Lub(left) // Lub (not EQ) of left is either right or a sparse child
for tme := d.(*sparseTreeMapEntry); tme != entry; tme = d.(*sparseTreeMapEntry) {
tme.sparseParent = entry
// all descendants of tme are unchanged;
// next sparse sibling (or right-bracketing sparse parent == entry) is first node after tme.index.exit - tme.adjust
_, d = rbtree.Lub(tme.index.exit - tme.adjust)
}
}
// Find returns the definition visible from block b, or nil if none can be found.
// Adjust indicates where the block should be searched.
// AdjustBefore searches before the phi functions of b.
// AdjustWithin searches starting at the phi functions of b.
// AdjustAfter searches starting at the exit from the block, including normal within-block definitions.
//
// Note that Finds are properly nested with Inserts:
// m.Insert(b, a) followed by m.Find(b, a) will not return the result of the insert,
// but m.Insert(b, AdjustBefore) followed by m.Find(b, AdjustWithin) will.
//
// Another way to think of this is that Find searches for inputs, Insert defines outputs.
func (m *SparseTreeMap) Find(b *Block, adjust int32, helper *SparseTreeHelper) interface{} {
v := m.findEntry(b, adjust, helper)
if v == nil {
return nil
}
return v.data
}
func (m *SparseTreeMap) findEntry(b *Block, adjust int32, helper *SparseTreeHelper) *sparseTreeMapEntry {
rbtree := (*RBTint32)(m)
if rbtree == nil {
return nil
}
blockIndex := &helper.Sdom[b.ID]
// The Glb (not EQ) of this probe is either the entry-indexed end of a sparse parent
// or the exit-indexed end of a sparse sibling
_, v := rbtree.Glb(blockIndex.entry + adjust)
if v == nil {
return nil
}
otherEntry := v.(*sparseTreeMapEntry)
if otherEntry.index.exit >= blockIndex.exit { // otherEntry exit after blockIndex exit; therefore, brackets
return otherEntry
}
// otherEntry is a sparse Sibling, and shares the same sparse parent (nearest ancestor within larger tree)
sp := otherEntry.sparseParent
if sp != nil {
if sp.index.exit < blockIndex.exit { // no ancestor found
return nil
}
return sp
}
return nil
}
func (m *SparseTreeMap) String() string {
tree := (*RBTint32)(m)
return tree.String()
}
func (e *sparseTreeMapEntry) String() string {
if e == nil {
return "nil"
}
return fmt.Sprintf("(index=%v, block=%v, data=%v)->%v", e.index, e.block, e.data, e.sparseParent)
}
|
