Skip to content

Commit 56e0ecc

Browse files
randall77randall77
committed
cmd/compile: keep value use counts in SSA
Keep track of how many uses each Value has. Each appearance in Value.Args and in Block.Control counts once. The number of uses of a value is generically useful to constrain rewrite rules. For instance, we might want to prevent merging index operations into loads if the same index expression is used lots of times. But I have one use in particular for which the use count is required. We must make sure we don't combine ops with loads if the load has more than one use. Otherwise, we may split a single load into multiple loads and that breaks perceived behavior in the presence of races. In particular, the load of m.state in sync/mutex.go:Lock can't be done twice. (I have a separate CL which triggers the mutex failure. This CL has a test which demonstrates a similar failure.) Change-Id: Icaafa479239f48632a069d0c3f624e6ebc6b1f0e Reviewed-on: https://go-review.googlesource.com/20790 Run-TryBot: Keith Randall <[email protected]> TryBot-Result: Gobot Gobot <[email protected]> Reviewed-by: Todd Neal <[email protected]>
1 parent cb1f2af commit 56e0ecc

23 files changed

Lines changed: 296 additions & 147 deletions

‎src/cmd/compile/internal/gc/ssa.go‎

Lines changed: 18 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -540,7 +540,7 @@ func (s *state) stmt(n *Node) {
540540
m := s.mem()
541541
b := s.endBlock()
542542
b.Kind = ssa.BlockExit
543-
b.Control = m
543+
b.SetControl(m)
544544
// TODO: never rewrite OPANIC to OCALLFUNC in the
545545
// first place. Need to wait until all backends
546546
// go through SSA.
@@ -920,7 +920,7 @@ func (s *state) exit() *ssa.Block {
920920
m := s.mem()
921921
b := s.endBlock()
922922
b.Kind = ssa.BlockRet
923-
b.Control = m
923+
b.SetControl(m)
924924
return b
925925
}
926926

@@ -1795,7 +1795,7 @@ func (s *state) expr(n *Node) *ssa.Value {
17951795

17961796
b := s.endBlock()
17971797
b.Kind = ssa.BlockIf
1798-
b.Control = el
1798+
b.SetControl(el)
17991799
// In theory, we should set b.Likely here based on context.
18001800
// However, gc only gives us likeliness hints
18011801
// in a single place, for plain OIF statements,
@@ -2039,7 +2039,7 @@ func (s *state) expr(n *Node) *ssa.Value {
20392039
b := s.endBlock()
20402040
b.Kind = ssa.BlockIf
20412041
b.Likely = ssa.BranchUnlikely
2042-
b.Control = cmp
2042+
b.SetControl(cmp)
20432043
b.AddEdgeTo(grow)
20442044
b.AddEdgeTo(assign)
20452045

@@ -2143,7 +2143,7 @@ func (s *state) condBranch(cond *Node, yes, no *ssa.Block, likely int8) {
21432143
c := s.expr(cond)
21442144
b := s.endBlock()
21452145
b.Kind = ssa.BlockIf
2146-
b.Control = c
2146+
b.SetControl(c)
21472147
b.Likely = ssa.BranchPrediction(likely) // gc and ssa both use -1/0/+1 for likeliness
21482148
b.AddEdgeTo(yes)
21492149
b.AddEdgeTo(no)
@@ -2396,7 +2396,7 @@ func (s *state) call(n *Node, k callKind) *ssa.Value {
23962396
s.vars[&memVar] = call
23972397
b := s.endBlock()
23982398
b.Kind = ssa.BlockCall
2399-
b.Control = call
2399+
b.SetControl(call)
24002400
b.AddEdgeTo(bNext)
24012401
if k == callDefer {
24022402
// Add recover edge to exit code.
@@ -2654,7 +2654,7 @@ func (s *state) nilCheck(ptr *ssa.Value) {
26542654
chk := s.newValue2(ssa.OpNilCheck, ssa.TypeVoid, ptr, s.mem())
26552655
b := s.endBlock()
26562656
b.Kind = ssa.BlockCheck
2657-
b.Control = chk
2657+
b.SetControl(chk)
26582658
bNext := s.f.NewBlock(ssa.BlockPlain)
26592659
b.AddEdgeTo(bNext)
26602660
s.startBlock(bNext)
@@ -2692,7 +2692,7 @@ func (s *state) sliceBoundsCheck(idx, len *ssa.Value) {
26922692
func (s *state) check(cmp *ssa.Value, fn *Node) {
26932693
b := s.endBlock()
26942694
b.Kind = ssa.BlockIf
2695-
b.Control = cmp
2695+
b.SetControl(cmp)
26962696
b.Likely = ssa.BranchLikely
26972697
bNext := s.f.NewBlock(ssa.BlockPlain)
26982698
line := s.peekLine()
@@ -2740,15 +2740,15 @@ func (s *state) rtcall(fn *Node, returns bool, results []*Type, args ...*ssa.Val
27402740
b := s.endBlock()
27412741
if !returns {
27422742
b.Kind = ssa.BlockExit
2743-
b.Control = call
2743+
b.SetControl(call)
27442744
call.AuxInt = off
27452745
if len(results) > 0 {
27462746
Fatalf("panic call can't have results")
27472747
}
27482748
return nil
27492749
}
27502750
b.Kind = ssa.BlockCall
2751-
b.Control = call
2751+
b.SetControl(call)
27522752
bNext := s.f.NewBlock(ssa.BlockPlain)
27532753
b.AddEdgeTo(bNext)
27542754
s.startBlock(bNext)
@@ -2793,7 +2793,7 @@ func (s *state) insertWBmove(t *Type, left, right *ssa.Value, line int32) {
27932793
b := s.endBlock()
27942794
b.Kind = ssa.BlockIf
27952795
b.Likely = ssa.BranchUnlikely
2796-
b.Control = flag
2796+
b.SetControl(flag)
27972797
b.AddEdgeTo(bThen)
27982798
b.AddEdgeTo(bElse)
27992799

@@ -2838,7 +2838,7 @@ func (s *state) insertWBstore(t *Type, left, right *ssa.Value, line int32) {
28382838
b := s.endBlock()
28392839
b.Kind = ssa.BlockIf
28402840
b.Likely = ssa.BranchUnlikely
2841-
b.Control = flag
2841+
b.SetControl(flag)
28422842
b.AddEdgeTo(bThen)
28432843
b.AddEdgeTo(bElse)
28442844

@@ -3049,7 +3049,7 @@ func (s *state) slice(t *Type, v, i, j, k *ssa.Value) (p, l, c *ssa.Value) {
30493049
b := s.endBlock()
30503050
b.Kind = ssa.BlockIf
30513051
b.Likely = ssa.BranchLikely
3052-
b.Control = cmp
3052+
b.SetControl(cmp)
30533053

30543054
// Generate code for non-zero length slice case.
30553055
nz := s.f.NewBlock(ssa.BlockPlain)
@@ -3150,7 +3150,7 @@ func (s *state) uintTofloat(cvttab *u2fcvtTab, n *Node, x *ssa.Value, ft, tt *Ty
31503150
cmp := s.newValue2(cvttab.geq, Types[TBOOL], x, s.zeroVal(ft))
31513151
b := s.endBlock()
31523152
b.Kind = ssa.BlockIf
3153-
b.Control = cmp
3153+
b.SetControl(cmp)
31543154
b.Likely = ssa.BranchLikely
31553155

31563156
bThen := s.f.NewBlock(ssa.BlockPlain)
@@ -3198,7 +3198,7 @@ func (s *state) referenceTypeBuiltin(n *Node, x *ssa.Value) *ssa.Value {
31983198
cmp := s.newValue2(ssa.OpEqPtr, Types[TBOOL], x, nilValue)
31993199
b := s.endBlock()
32003200
b.Kind = ssa.BlockIf
3201-
b.Control = cmp
3201+
b.SetControl(cmp)
32023202
b.Likely = ssa.BranchUnlikely
32033203

32043204
bThen := s.f.NewBlock(ssa.BlockPlain)
@@ -3269,7 +3269,7 @@ func (s *state) floatToUint(cvttab *f2uCvtTab, n *Node, x *ssa.Value, ft, tt *Ty
32693269
cmp := s.newValue2(cvttab.ltf, Types[TBOOL], x, twoToThe63)
32703270
b := s.endBlock()
32713271
b.Kind = ssa.BlockIf
3272-
b.Control = cmp
3272+
b.SetControl(cmp)
32733273
b.Likely = ssa.BranchLikely
32743274

32753275
bThen := s.f.NewBlock(ssa.BlockPlain)
@@ -3318,7 +3318,7 @@ func (s *state) ifaceType(n *Node, v *ssa.Value) *ssa.Value {
33183318
isnonnil := s.newValue2(ssa.OpNeqPtr, Types[TBOOL], tab, s.constNil(byteptr))
33193319
b := s.endBlock()
33203320
b.Kind = ssa.BlockIf
3321-
b.Control = isnonnil
3321+
b.SetControl(isnonnil)
33223322
b.Likely = ssa.BranchLikely
33233323

33243324
bLoad := s.f.NewBlock(ssa.BlockPlain)
@@ -3360,7 +3360,7 @@ func (s *state) dottype(n *Node, commaok bool) (res, resok *ssa.Value) {
33603360
cond := s.newValue2(ssa.OpEqPtr, Types[TBOOL], typ, target)
33613361
b := s.endBlock()
33623362
b.Kind = ssa.BlockIf
3363-
b.Control = cond
3363+
b.SetControl(cond)
33643364
b.Likely = ssa.BranchLikely
33653365

33663366
byteptr := Ptrto(Types[TUINT8])

‎src/cmd/compile/internal/ssa/block.go‎

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -97,6 +97,16 @@ func (b *Block) LongString() string {
9797
return s
9898
}
9999

100+
func (b *Block) SetControl(v *Value) {
101+
if w := b.Control; w != nil {
102+
w.Uses--
103+
}
104+
b.Control = v
105+
if v != nil {
106+
v.Uses++
107+
}
108+
}
109+
100110
// AddEdgeTo adds an edge from block b to block c. Used during building of the
101111
// SSA graph; do not use on an already-completed SSA graph.
102112
func (b *Block) AddEdgeTo(c *Block) {

‎src/cmd/compile/internal/ssa/check.go‎

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -294,6 +294,26 @@ func checkFunc(f *Func) {
294294
}
295295
}
296296
}
297+
298+
// Check use counts
299+
uses := make([]int32, f.NumValues())
300+
for _, b := range f.Blocks {
301+
for _, v := range b.Values {
302+
for _, a := range v.Args {
303+
uses[a.ID]++
304+
}
305+
}
306+
if b.Control != nil {
307+
uses[b.Control.ID]++
308+
}
309+
}
310+
for _, b := range f.Blocks {
311+
for _, v := range b.Values {
312+
if v.Uses != uses[v.ID] {
313+
f.Fatalf("%s has %d uses, but has Uses=%d", v, uses[v.ID], v.Uses)
314+
}
315+
}
316+
}
297317
}
298318

299319
// domCheck reports whether x dominates y (including x==y).

‎src/cmd/compile/internal/ssa/copyelim.go‎

Lines changed: 7 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -11,11 +11,11 @@ func copyelim(f *Func) {
1111
copyelimValue(v)
1212
}
1313
v := b.Control
14-
if v != nil {
14+
if v != nil && v.Op == OpCopy {
1515
for v.Op == OpCopy {
1616
v = v.Args[0]
1717
}
18-
b.Control = v
18+
b.SetControl(v)
1919
}
2020
}
2121

@@ -34,8 +34,9 @@ func copyelim(f *Func) {
3434
}
3535
}
3636

37-
func copyelimValue(v *Value) {
37+
func copyelimValue(v *Value) bool {
3838
// elide any copies generated during rewriting
39+
changed := false
3940
for i, a := range v.Args {
4041
if a.Op != OpCopy {
4142
continue
@@ -55,6 +56,8 @@ func copyelimValue(v *Value) {
5556
}
5657
advance = !advance
5758
}
58-
v.Args[i] = a
59+
v.SetArg(i, a)
60+
changed = true
5961
}
62+
return changed
6063
}

‎src/cmd/compile/internal/ssa/cse.go‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -182,7 +182,7 @@ func cse(f *Func) {
182182
// them appropriately, so don't mess with them here.
183183
continue
184184
}
185-
b.Control = x
185+
b.SetControl(x)
186186
}
187187
}
188188
}

‎src/cmd/compile/internal/ssa/deadcode.go‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -164,6 +164,18 @@ func deadcode(f *Func) {
164164
}
165165
f.Names = f.Names[:i]
166166

167+
// Unlink values.
168+
for _, b := range f.Blocks {
169+
if !reachable[b.ID] {
170+
b.SetControl(nil)
171+
}
172+
for _, v := range b.Values {
173+
if !live[v.ID] {
174+
v.resetArgs()
175+
}
176+
}
177+
}
178+
167179
// Remove dead values from blocks' value list. Return dead
168180
// values to the allocator.
169181
for _, b := range f.Blocks {
@@ -231,6 +243,7 @@ func (b *Block) removePred(p *Block) {
231243
if v.Op != OpPhi {
232244
continue
233245
}
246+
v.Args[i].Uses--
234247
v.Args[i] = v.Args[n]
235248
v.Args[n] = nil // aid GC
236249
v.Args = v.Args[:n]

‎src/cmd/compile/internal/ssa/flagalloc.go‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -113,7 +113,7 @@ func flagalloc(f *Func) {
113113
if v := b.Control; v != nil && v != flag && v.Type.IsFlags() {
114114
// Recalculate control value.
115115
c := v.copyInto(b)
116-
b.Control = c
116+
b.SetControl(c)
117117
flag = v
118118
}
119119
if v := end[b.ID]; v != nil && v != flag {

‎src/cmd/compile/internal/ssa/func.go‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -114,6 +114,9 @@ func (f *Func) freeValue(v *Value) {
114114
if v.Block == nil {
115115
f.Fatalf("trying to free an already freed value")
116116
}
117+
if v.Uses != 0 {
118+
f.Fatalf("value %s still has %d uses", v, v.Uses)
119+
}
117120
// Clear everything but ID (which we reuse).
118121
id := v.ID
119122

@@ -217,6 +220,7 @@ func (b *Block) NewValue1(line int32, op Op, t Type, arg *Value) *Value {
217220
v.AuxInt = 0
218221
v.Args = v.argstorage[:1]
219222
v.argstorage[0] = arg
223+
arg.Uses++
220224
return v
221225
}
222226

@@ -226,6 +230,7 @@ func (b *Block) NewValue1I(line int32, op Op, t Type, auxint int64, arg *Value)
226230
v.AuxInt = auxint
227231
v.Args = v.argstorage[:1]
228232
v.argstorage[0] = arg
233+
arg.Uses++
229234
return v
230235
}
231236

@@ -236,6 +241,7 @@ func (b *Block) NewValue1A(line int32, op Op, t Type, aux interface{}, arg *Valu
236241
v.Aux = aux
237242
v.Args = v.argstorage[:1]
238243
v.argstorage[0] = arg
244+
arg.Uses++
239245
return v
240246
}
241247

@@ -246,6 +252,7 @@ func (b *Block) NewValue1IA(line int32, op Op, t Type, auxint int64, aux interfa
246252
v.Aux = aux
247253
v.Args = v.argstorage[:1]
248254
v.argstorage[0] = arg
255+
arg.Uses++
249256
return v
250257
}
251258

@@ -256,6 +263,8 @@ func (b *Block) NewValue2(line int32, op Op, t Type, arg0, arg1 *Value) *Value {
256263
v.Args = v.argstorage[:2]
257264
v.argstorage[0] = arg0
258265
v.argstorage[1] = arg1
266+
arg0.Uses++
267+
arg1.Uses++
259268
return v
260269
}
261270

@@ -266,6 +275,8 @@ func (b *Block) NewValue2I(line int32, op Op, t Type, auxint int64, arg0, arg1 *
266275
v.Args = v.argstorage[:2]
267276
v.argstorage[0] = arg0
268277
v.argstorage[1] = arg1
278+
arg0.Uses++
279+
arg1.Uses++
269280
return v
270281
}
271282

@@ -274,6 +285,9 @@ func (b *Block) NewValue3(line int32, op Op, t Type, arg0, arg1, arg2 *Value) *V
274285
v := b.Func.newValue(op, t, b, line)
275286
v.AuxInt = 0
276287
v.Args = []*Value{arg0, arg1, arg2}
288+
arg0.Uses++
289+
arg1.Uses++
290+
arg2.Uses++
277291
return v
278292
}
279293

@@ -282,6 +296,9 @@ func (b *Block) NewValue3I(line int32, op Op, t Type, auxint int64, arg0, arg1,
282296
v := b.Func.newValue(op, t, b, line)
283297
v.AuxInt = auxint
284298
v.Args = []*Value{arg0, arg1, arg2}
299+
arg0.Uses++
300+
arg1.Uses++
301+
arg2.Uses++
285302
return v
286303
}
287304

‎src/cmd/compile/internal/ssa/func_test.go‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -168,7 +168,7 @@ func Fun(c *Config, entry string, blocs ...bloc) fun {
168168
if !ok {
169169
f.Fatalf("control value for block %s missing", bloc.name)
170170
}
171-
b.Control = cval
171+
b.SetControl(cval)
172172
}
173173
// Fill in args.
174174
for _, valu := range bloc.valus {

‎src/cmd/compile/internal/ssa/fuse.go‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -96,7 +96,7 @@ func fuseBlockIf(b *Block) bool {
9696
ss.removePred(s1)
9797
}
9898
b.Kind = BlockPlain
99-
b.Control = nil
99+
b.SetControl(nil)
100100
b.Succs = append(b.Succs[:0], ss)
101101

102102
// Trash the empty blocks s0 & s1.

0 commit comments

Comments
 (0)