Skip to content

Commit c140df0

Browse files
randall77randall77
committed
[dev.ssa] cmd/compile: allocate the flag register in a separate pass
Spilling/restoring flag values is a pain to do during regalloc. Instead, allocate the flag register in a separate pass. Regalloc then operates normally on any flag recomputation instructions. Change-Id: Ia1c3d9e6eff678861193093c0b48a00f90e4156b Reviewed-on: https://go-review.googlesource.com/17694 Reviewed-by: David Chase <[email protected]>
1 parent 09ffa0c commit c140df0

6 files changed

Lines changed: 162 additions & 50 deletions

File tree

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

Lines changed: 8 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -97,9 +97,10 @@ var passes = [...]pass{
9797
{"lowered cse", cse},
9898
{"lowered deadcode", deadcode},
9999
{"checkLower", checkLower},
100-
{"critical", critical}, // remove critical edges
101-
{"layout", layout}, // schedule blocks
102-
{"schedule", schedule}, // schedule values
100+
{"critical", critical}, // remove critical edges
101+
{"layout", layout}, // schedule blocks
102+
{"schedule", schedule}, // schedule values
103+
{"flagalloc", flagalloc}, // allocate flags register
103104
{"regalloc", regalloc},
104105
{"stackalloc", stackalloc},
105106
}
@@ -142,6 +143,10 @@ var passOrder = [...]constraint{
142143
// checkLower must run after lowering & subsequent dead code elim
143144
{"lower", "checkLower"},
144145
{"lowered deadcode", "checkLower"},
146+
// flagalloc needs instructions to be scheduled.
147+
{"schedule", "flagalloc"},
148+
// regalloc needs flags to be allocated first.
149+
{"flagalloc", "regalloc"},
145150
}
146151

147152
func init() {

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

Lines changed: 123 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,123 @@
1+
// Copyright 2015 The Go Authors. All rights reserved.
2+
// Use of this source code is governed by a BSD-style
3+
// license that can be found in the LICENSE file.
4+
5+
package ssa
6+
7+
const flagRegMask = regMask(1) << 33 // TODO: arch-specific
8+
9+
// flagalloc allocates the flag register among all the flag-generating
10+
// instructions. Flag values are recomputed if they need to be
11+
// spilled/restored.
12+
func flagalloc(f *Func) {
13+
// Compute the in-register flag value we want at the end of
14+
// each block. This is basically a best-effort live variable
15+
// analysis, so it can be much simpler than a full analysis.
16+
// TODO: do we really need to keep flag values live across blocks?
17+
// Could we force the flags register to be unused at basic block
18+
// boundaries? Then we wouldn't need this computation.
19+
end := make([]*Value, f.NumBlocks())
20+
for n := 0; n < 2; n++ {
21+
// Walk blocks backwards. Poor-man's postorder traversal.
22+
for i := len(f.Blocks) - 1; i >= 0; i-- {
23+
b := f.Blocks[i]
24+
// Walk values backwards to figure out what flag
25+
// value we want in the flag register at the start
26+
// of the block.
27+
flag := end[b.ID]
28+
if b.Control != nil && b.Control.Type.IsFlags() {
29+
flag = b.Control
30+
}
31+
for j := len(b.Values) - 1; j >= 0; j-- {
32+
v := b.Values[j]
33+
if v == flag {
34+
flag = nil
35+
}
36+
if opcodeTable[v.Op].reg.clobbers&flagRegMask != 0 {
37+
flag = nil
38+
}
39+
for _, a := range v.Args {
40+
if a.Type.IsFlags() {
41+
flag = a
42+
}
43+
}
44+
}
45+
for _, p := range b.Preds {
46+
end[p.ID] = flag
47+
}
48+
}
49+
}
50+
// For blocks which have a flags control value, that's the only value
51+
// we can leave in the flags register at the end of the block. (There
52+
// is no place to put a flag regeneration instruction.)
53+
for _, b := range f.Blocks {
54+
v := b.Control
55+
if v != nil && v.Type.IsFlags() && end[b.ID] != v {
56+
end[b.ID] = nil
57+
}
58+
}
59+
60+
// Add flag recomputations where they are needed.
61+
// TODO: Remove original instructions if they are never used.
62+
var oldSched []*Value
63+
for _, b := range f.Blocks {
64+
oldSched = append(oldSched[:0], b.Values...)
65+
b.Values = b.Values[:0]
66+
// The current live flag value.
67+
var flag *Value
68+
if len(b.Preds) > 0 {
69+
flag = end[b.Preds[0].ID]
70+
// Note: the following condition depends on the lack of critical edges.
71+
for _, p := range b.Preds[1:] {
72+
if end[p.ID] != flag {
73+
f.Fatalf("live flag in %s's predecessors not consistent", b)
74+
}
75+
}
76+
}
77+
for _, v := range oldSched {
78+
if v.Op == OpPhi && v.Type.IsFlags() {
79+
f.Fatalf("phi of flags not supported: %s", v.LongString())
80+
}
81+
// Make sure any flag arg of v is in the flags register.
82+
// If not, recompute it.
83+
for i, a := range v.Args {
84+
if !a.Type.IsFlags() {
85+
continue
86+
}
87+
if a == flag {
88+
continue
89+
}
90+
// Recalculate a
91+
c := a.copyInto(b)
92+
// Update v.
93+
v.SetArg(i, c)
94+
// Remember the most-recently computed flag value.
95+
flag = c
96+
}
97+
// Issue v.
98+
b.Values = append(b.Values, v)
99+
if opcodeTable[v.Op].reg.clobbers&flagRegMask != 0 {
100+
flag = nil
101+
}
102+
if v.Type.IsFlags() {
103+
flag = v
104+
}
105+
}
106+
if v := b.Control; v != nil && v != flag && v.Type.IsFlags() {
107+
// Recalculate control value.
108+
c := v.copyInto(b)
109+
b.Control = c
110+
flag = c
111+
}
112+
if v := end[b.ID]; v != nil && v != flag {
113+
// Need to reissue flag generator for use by
114+
// subsequent blocks.
115+
_ = v.copyInto(b)
116+
// Note: this flag generator is not properly linked up
117+
// with the flag users. This breaks the SSA representation.
118+
// We could fix up the users with another pass, but for now
119+
// we'll just leave it. (Regalloc has the same issue for
120+
// standard regs, and it runs next.)
121+
}
122+
}
123+
}

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

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -232,6 +232,11 @@ func Exit(arg string) ctrl {
232232
return ctrl{BlockExit, arg, []string{}}
233233
}
234234

235+
// Eq specifies a BlockAMD64EQ.
236+
func Eq(cond, sub, alt string) ctrl {
237+
return ctrl{BlockAMD64EQ, cond, []string{sub, alt}}
238+
}
239+
235240
// bloc, ctrl, and valu are internal structures used by Bloc, Valu, Goto,
236241
// If, and Exit to help define blocks.
237242

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

Lines changed: 12 additions & 43 deletions
Original file line numberDiff line numberDiff line change
@@ -38,12 +38,6 @@
3838
// x3 can then be used wherever x is referenced again.
3939
// If the spill (x2) is never used, it will be removed at the end of regalloc.
4040
//
41-
// Flags values are special. Instead of attempting to spill and restore the flags
42-
// register, we recalculate it if needed.
43-
// There are more efficient schemes (see the discussion in CL 13844),
44-
// but flag restoration is empirically rare, and this approach is simple
45-
// and architecture-independent.
46-
//
4741
// Phi values are special, as always. We define two kinds of phis, those
4842
// where the merge happens in a register (a "register" phi) and those where
4943
// the merge happens in a stack location (a "stack" phi).
@@ -173,7 +167,6 @@ var registers = [...]Register{
173167
Register{30, "X14"},
174168
Register{31, "X15"},
175169
Register{32, "SB"}, // pseudo-register for global base pointer (aka %rip)
176-
Register{33, "FLAGS"},
177170

178171
// TODO: make arch-dependent
179172
}
@@ -226,7 +219,7 @@ type regAllocState struct {
226219
f *Func
227220

228221
// For each value, whether it needs a register or not.
229-
// Cached value of !v.Type.IsMemory() && !v.Type.IsVoid().
222+
// Cached value of !v.Type.IsMemory() && !v.Type.IsVoid() && !v.Type.IsFlags().
230223
needReg []bool
231224

232225
// for each block, its primary predecessor.
@@ -435,40 +428,9 @@ func (s *regAllocState) allocValToReg(v *Value, mask regMask, nospill bool) *Val
435428
c = s.curBlock.NewValue1(v.Line, OpCopy, v.Type, s.regs[r2].c)
436429
} else if v.rematerializeable() {
437430
// Rematerialize instead of loading from the spill location.
438-
c = s.curBlock.NewValue0(v.Line, v.Op, v.Type)
439-
c.Aux = v.Aux
440-
c.AuxInt = v.AuxInt
441-
c.AddArgs(v.Args...)
431+
c = v.copyInto(s.curBlock)
442432
} else {
443433
switch {
444-
// It is difficult to spill and reload flags on many architectures.
445-
// Instead, we regenerate the flags register by issuing the same instruction again.
446-
// This requires (possibly) spilling and reloading that instruction's args.
447-
case v.Type.IsFlags():
448-
if logSpills {
449-
fmt.Println("regalloc: regenerating flags")
450-
}
451-
ns := s.nospill
452-
// Place v's arguments in registers, spilling and loading as needed
453-
args := make([]*Value, 0, len(v.Args))
454-
regspec := opcodeTable[v.Op].reg
455-
for _, i := range regspec.inputs {
456-
// Extract the original arguments to v
457-
a := s.orig[v.Args[i.idx].ID]
458-
if a.Type.IsFlags() {
459-
s.f.Fatalf("cannot load flags value with flags arg: %v has unwrapped arg %v", v.LongString(), a.LongString())
460-
}
461-
cc := s.allocValToReg(a, i.regs, true)
462-
args = append(args, cc)
463-
}
464-
s.nospill = ns
465-
// Recalculate v
466-
c = s.curBlock.NewValue0(v.Line, v.Op, v.Type)
467-
c.Aux = v.Aux
468-
c.AuxInt = v.AuxInt
469-
c.resetArgs()
470-
c.AddArgs(args...)
471-
472434
// Load v from its spill location.
473435
case vi.spill2 != nil:
474436
if logSpills {
@@ -506,7 +468,7 @@ func (s *regAllocState) init(f *Func) {
506468
s.orig = make([]*Value, f.NumValues())
507469
for _, b := range f.Blocks {
508470
for _, v := range b.Values {
509-
if v.Type.IsMemory() || v.Type.IsVoid() {
471+
if v.Type.IsMemory() || v.Type.IsVoid() || v.Type.IsFlags() {
510472
continue
511473
}
512474
s.needReg[v.ID] = true
@@ -818,6 +780,10 @@ func (s *regAllocState) regalloc(f *Func) {
818780
// by the register specification (most constrained first).
819781
args = append(args[:0], v.Args...)
820782
for _, i := range regspec.inputs {
783+
if i.regs == flagRegMask {
784+
// TODO: remove flag input from regspec.inputs.
785+
continue
786+
}
821787
args[i.idx] = s.allocValToReg(v.Args[i.idx], i.regs, true)
822788
}
823789

@@ -834,8 +800,11 @@ func (s *regAllocState) regalloc(f *Func) {
834800
// Pick register for output.
835801
var r register
836802
var mask regMask
837-
if len(regspec.outputs) > 0 {
803+
if s.needReg[v.ID] {
838804
mask = regspec.outputs[0] &^ s.reserved()
805+
if mask>>33&1 != 0 {
806+
s.f.Fatalf("bad mask %s\n", v.LongString())
807+
}
839808
}
840809
if mask != 0 {
841810
r = s.allocReg(mask)
@@ -858,7 +827,7 @@ func (s *regAllocState) regalloc(f *Func) {
858827
// f()
859828
// }
860829
// It would be good to have both spill and restore inside the IF.
861-
if !v.Type.IsFlags() {
830+
if s.needReg[v.ID] {
862831
spill := b.NewValue1(v.Line, OpStoreReg, v.Type, v)
863832
s.setOrig(spill, v)
864833
s.values[v.ID].spill = spill

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

Lines changed: 5 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -13,12 +13,12 @@ func TestLiveControlOps(t *testing.T) {
1313
Valu("mem", OpInitMem, TypeMem, 0, ".mem"),
1414
Valu("x", OpAMD64MOVBconst, TypeInt8, 0, 1),
1515
Valu("y", OpAMD64MOVBconst, TypeInt8, 0, 2),
16-
Valu("a", OpAMD64TESTB, TypeBool, 0, nil, "x", "y"),
17-
Valu("b", OpAMD64TESTB, TypeBool, 0, nil, "y", "x"),
18-
If("a", "if", "exit"),
16+
Valu("a", OpAMD64TESTB, TypeFlags, 0, nil, "x", "y"),
17+
Valu("b", OpAMD64TESTB, TypeFlags, 0, nil, "y", "x"),
18+
Eq("a", "if", "exit"),
1919
),
2020
Bloc("if",
21-
If("b", "plain", "exit"),
21+
Eq("b", "plain", "exit"),
2222
),
2323
Bloc("plain",
2424
Goto("exit"),
@@ -27,6 +27,7 @@ func TestLiveControlOps(t *testing.T) {
2727
Exit("mem"),
2828
),
2929
)
30+
flagalloc(f.f)
3031
regalloc(f.f)
3132
checkFunc(f.f)
3233
}

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

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -126,6 +126,15 @@ func (v *Value) resetArgs() {
126126
v.Args = v.argstorage[:0]
127127
}
128128

129+
// copyInto makes a new value identical to v and adds it to the end of b.
130+
func (v *Value) copyInto(b *Block) *Value {
131+
c := b.NewValue0(v.Line, v.Op, v.Type)
132+
c.Aux = v.Aux
133+
c.AuxInt = v.AuxInt
134+
c.AddArgs(v.Args...)
135+
return c
136+
}
137+
129138
func (v *Value) Logf(msg string, args ...interface{}) { v.Block.Logf(msg, args...) }
130139
func (v *Value) Fatalf(msg string, args ...interface{}) { v.Block.Fatalf(msg, args...) }
131140
func (v *Value) Unimplementedf(msg string, args ...interface{}) { v.Block.Unimplementedf(msg, args...) }

0 commit comments

Comments
 (0)