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
|
// 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 gc
import (
"cmd/compile/internal/ssa"
"fmt"
"math"
)
// sparseDefState contains a Go map from ONAMEs (*Node) to sparse definition trees, and
// a search helper for the CFG's dominator tree in which those definitions are embedded.
// Once initialized, given a use of an ONAME within a block, the ssa definition for
// that ONAME can be discovered in time roughly proportional to the log of the number
// of SSA definitions of that ONAME (thus avoiding pathological quadratic behavior for
// very large programs). The helper contains state (a dominator tree numbering) common
// to all the sparse definition trees, as well as some necessary data obtained from
// the ssa package.
//
// This algorithm has improved asymptotic complexity, but the constant factor is
// rather large and thus it is only preferred for very large inputs containing
// 1000s of blocks and variables.
type sparseDefState struct {
helper *ssa.SparseTreeHelper // contains one copy of information needed to do sparse mapping
defmapForOname map[*Node]*onameDefs // for each ONAME, its definition set (normal and phi)
}
// onameDefs contains a record of definitions (ordinary and implied phi function) for a single OName.
// stm is the set of definitions for the OName.
// firstdef and lastuse are postorder block numberings that
// conservatively bracket the entire lifetime of the OName.
type onameDefs struct {
stm *ssa.SparseTreeMap
// firstdef and lastuse define an interval in the postorder numbering
// that is guaranteed to include the entire lifetime of an ONAME.
// In the postorder numbering, math.MaxInt32 is before anything,
// and 0 is after-or-equal all exit nodes and infinite loops.
firstdef int32 // the first definition of this ONAME *in the postorder numbering*
lastuse int32 // the last use of this ONAME *in the postorder numbering*
}
// defsFor finds or creates-and-inserts-in-map the definition information
// (sparse tree and live range) for a given OName.
func (m *sparseDefState) defsFor(n *Node) *onameDefs {
d := m.defmapForOname[n]
if d != nil {
return d
}
// Reminder: firstdef/lastuse are postorder indices, not block indices,
// so these default values define an empty interval, not the entire one.
d = &onameDefs{stm: m.helper.NewTree(), firstdef: 0, lastuse: math.MaxInt32}
m.defmapForOname[n] = d
return d
}
// Insert adds a definition at b (with specified before/within/after adjustment)
// to sparse tree onameDefs. The lifetime is extended as necessary.
func (m *sparseDefState) Insert(tree *onameDefs, b *ssa.Block, adjust int32) {
bponum := m.helper.Ponums[b.ID]
if bponum > tree.firstdef {
tree.firstdef = bponum
}
tree.stm.Insert(b, adjust, b, m.helper)
}
// Use updates tree to record a use within b, extending the lifetime as necessary.
func (m *sparseDefState) Use(tree *onameDefs, b *ssa.Block) {
bponum := m.helper.Ponums[b.ID]
if bponum < tree.lastuse {
tree.lastuse = bponum
}
}
// locatePotentialPhiFunctions finds all the places where phi functions
// will be inserted into a program and records those and ordinary definitions
// in a "map" (not a Go map) that given an OName and use site, returns the
// SSA definition for that OName that will reach the use site (that is,
// the use site's nearest def/phi site in the dominator tree.)
func (s *state) locatePotentialPhiFunctions(fn *Node) *sparseDefState {
// s.config.SparsePhiCutoff() is compared with product of numblocks and numvalues,
// if product is smaller than cutoff, use old non-sparse method.
// cutoff == 0 implies all sparse
// cutoff == uint(-1) implies all non-sparse
if uint64(s.f.NumValues())*uint64(s.f.NumBlocks()) < s.config.SparsePhiCutoff() {
return nil
}
helper := ssa.NewSparseTreeHelper(s.f)
po := helper.Po // index by block.ID to obtain postorder # of block.
trees := make(map[*Node]*onameDefs)
dm := &sparseDefState{defmapForOname: trees, helper: helper}
// Process params, taking note of their special lifetimes
b := s.f.Entry
for _, n := range fn.Func.Dcl {
switch n.Class {
case PPARAM, PPARAMOUT:
t := dm.defsFor(n)
dm.Insert(t, b, ssa.AdjustBefore) // define param at entry block
if n.Class == PPARAMOUT {
dm.Use(t, po[0]) // Explicitly use PPARAMOUT at very last block
}
default:
}
}
// Process memory variable.
t := dm.defsFor(&memVar)
dm.Insert(t, b, ssa.AdjustBefore) // define memory at entry block
dm.Use(t, po[0]) // Explicitly use memory at last block
// Next load the map w/ basic definitions for ONames recorded per-block
// Iterate over po to avoid unreachable blocks.
for i := len(po) - 1; i >= 0; i-- {
b := po[i]
m := s.defvars[b.ID]
for n := range m { // no specified order, but per-node trees are independent.
t := dm.defsFor(n)
dm.Insert(t, b, ssa.AdjustWithin)
}
}
// Find last use of each variable
for _, v := range s.fwdRefs {
b := v.Block
name := v.Aux.(*Node)
t := dm.defsFor(name)
dm.Use(t, b)
}
for _, t := range trees {
// iterating over names in the outer loop
for change := true; change; {
change = false
for i := t.firstdef; i >= t.lastuse; i-- {
// Iterating in reverse of post-order reduces number of 'change' iterations;
// all possible forward flow goes through each time.
b := po[i]
// Within tree t, would a use at b require a phi function to ensure a single definition?
// TODO: perhaps more efficient to record specific use sites instead of range?
if len(b.Preds) < 2 {
continue // no phi possible
}
phi := t.stm.Find(b, ssa.AdjustWithin, helper) // Look for defs in earlier block or AdjustBefore in this one.
if phi != nil && phi.(*ssa.Block) == b {
continue // has a phi already in this block.
}
var defseen interface{}
// Do preds see different definitions? if so, need a phi function.
for _, e := range b.Preds {
p := e.Block()
dm.Use(t, p) // always count phi pred as "use"; no-op except for loop edges, which matter.
x := t.stm.Find(p, ssa.AdjustAfter, helper) // Look for defs reaching or within predecessors.
if x == nil { // nil def from a predecessor means a backedge that will be visited soon.
continue
}
if defseen == nil {
defseen = x
}
if defseen != x {
// Need to insert a phi function here because predecessors's definitions differ.
change = true
// Phi insertion is at AdjustBefore, visible with find in same block at AdjustWithin or AdjustAfter.
dm.Insert(t, b, ssa.AdjustBefore)
break
}
}
}
}
}
return dm
}
// FindBetterDefiningBlock tries to find a better block for a definition of OName name
// reaching (or within) p than p itself. If it cannot, it returns p instead.
// This aids in more efficient location of phi functions, since it can skip over
// branch code that might contain a definition of name if it actually does not.
func (m *sparseDefState) FindBetterDefiningBlock(name *Node, p *ssa.Block) *ssa.Block {
if m == nil {
return p
}
t := m.defmapForOname[name]
// For now this is fail-soft, since the old algorithm still works using the unimproved block.
if t == nil {
return p
}
x := t.stm.Find(p, ssa.AdjustAfter, m.helper)
if x == nil {
return p
}
b := x.(*ssa.Block)
if b == nil {
return p
}
return b
}
func (d *onameDefs) String() string {
return fmt.Sprintf("onameDefs:first=%d,last=%d,tree=%s", d.firstdef, d.lastuse, d.stm.String())
}
|
