// 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.
// Register allocation.
//
// We use a version of a linear scan register allocator. We treat the
// whole function as a single long basic block and run through
// it using a greedy register allocator. Then all merge edges
// (those targeting a block with len(Preds)>1) are processed to
// shuffle data into the place that the target of the edge expects.
//
// The greedy allocator moves values into registers just before they
// are used, spills registers only when necessary, and spills the
// value whose next use is farthest in the future.
//
// The register allocator requires that a block is not scheduled until
// at least one of its predecessors have been scheduled. The most recent
// such predecessor provides the starting register state for a block.
//
// It also requires that there are no critical edges (critical =
// comes from a block with >1 successor and goes to a block with >1
// predecessor). This makes it easy to add fixup code on merge edges -
// the source of a merge edge has only one successor, so we can add
// fixup code to the end of that block.
// Spilling
//
// During the normal course of the allocator, we might throw a still-live
// value out of all registers. When that value is subsequently used, we must
// load it from a slot on the stack. We must also issue an instruction to
// initialize that stack location with a copy of v.
//
// pre-regalloc:
// (1) v = Op ...
// (2) x = Op ...
// (3) ... = Op v ...
//
// post-regalloc:
// (1) v = Op ... : AX // computes v, store result in AX
// s = StoreReg v // spill v to a stack slot
// (2) x = Op ... : AX // some other op uses AX
// c = LoadReg s : CX // restore v from stack slot
// (3) ... = Op c ... // use the restored value
//
// Allocation occurs normally until we reach (3) and we realize we have
// a use of v and it isn't in any register. At that point, we allocate
// a spill (a StoreReg) for v. We can't determine the correct place for
// the spill at this point, so we allocate the spill as blockless initially.
// The restore is then generated to load v back into a register so it can
// be used. Subsequent uses of v will use the restored value c instead.
//
// What remains is the question of where to schedule the spill.
// During allocation, we keep track of the dominator of all restores of v.
// The spill of v must dominate that block. The spill must also be issued at
// a point where v is still in a register.
//
// To find the right place, start at b, the block which dominates all restores.
// - If b is v.Block, then issue the spill right after v.
// It is known to be in a register at that point, and dominates any restores.
// - Otherwise, if v is in a register at the start of b,
// put the spill of v at the start of b.
// - Otherwise, set b = immediate dominator of b, and repeat.
//
// Phi values are special, as always. We define two kinds of phis, those
// where the merge happens in a register (a "register" phi) and those where
// the merge happens in a stack location (a "stack" phi).
//
// A register phi must have the phi and all of its inputs allocated to the
// same register. Register phis are spilled similarly to regular ops.
//
// A stack phi must have the phi and all of its inputs allocated to the same
// stack location. Stack phis start out life already spilled - each phi
// input must be a store (using StoreReg) at the end of the corresponding
// predecessor block.
// b1: y = ... : AX b2: z = ... : BX
// y2 = StoreReg y z2 = StoreReg z
// goto b3 goto b3
// b3: x = phi(y2, z2)
// The stack allocator knows that StoreReg args of stack-allocated phis
// must be allocated to the same stack slot as the phi that uses them.
// x is now a spilled value and a restore must appear before its first use.
// TODO
// Use an affinity graph to mark two values which should use the
// same register. This affinity graph will be used to prefer certain
// registers for allocation. This affinity helps eliminate moves that
// are required for phi implementations and helps generate allocations
// for 2-register architectures.
// Note: regalloc generates a not-quite-SSA output. If we have:
//
// b1: x = ... : AX
// x2 = StoreReg x
// ... AX gets reused for something else ...
// if ... goto b3 else b4
//
// b3: x3 = LoadReg x2 : BX b4: x4 = LoadReg x2 : CX
// ... use x3 ... ... use x4 ...
//
// b2: ... use x3 ...
//
// If b3 is the primary predecessor of b2, then we use x3 in b2 and
// add a x4:CX->BX copy at the end of b4.
// But the definition of x3 doesn't dominate b2. We should really
// insert a dummy phi at the start of b2 (x5=phi(x3,x4):BX) to keep
// SSA form. For now, we ignore this problem as remaining in strict
// SSA form isn't needed after regalloc. We'll just leave the use
// of x3 not dominated by the definition of x3, and the CX->BX copy
// will have no use (so don't run deadcode after regalloc!).
// TODO: maybe we should introduce these extra phis?
package ssa
import (
"cmd/compile/internal/types"
"cmd/internal/objabi"
"cmd/internal/src"
"fmt"
"unsafe"
)
const (
moveSpills = iota
logSpills
regDebug
stackDebug
)
// distance is a measure of how far into the future values are used.
// distance is measured in units of instructions.
const (
likelyDistance = 1
normalDistance = 10
unlikelyDistance = 100
)
// regalloc performs register allocation on f. It sets f.RegAlloc
// to the resulting allocation.
func regalloc(f *Func) {
var s regAllocState
s.init(f)
s.regalloc(f)
}
type register uint8
const noRegister register = 255
type regMask uint64
func (m regMask) String() string {
s := ""
for r := register(0); m != 0; r++ {
if m>>r&1 == 0 {
continue
}
m &^= regMask(1) << r
if s != "" {
s += " "
}
s += fmt.Sprintf("r%d", r)
}
return s
}
// countRegs returns the number of set bits in the register mask.
func countRegs(r regMask) int {
n := 0
for r != 0 {
n += int(r & 1)
r >>= 1
}
return n
}
// pickReg picks an arbitrary register from the register mask.
func pickReg(r regMask) register {
// pick the lowest one
if r == 0 {
panic("can't pick a register from an empty set")
}
for i := register(0); ; i++ {
if r&1 != 0 {
return i
}
r >>= 1
}
}
type use struct {
dist int32 // distance from start of the block to a use of a value
pos src.XPos // source position of the use
next *use // linked list of uses of a value in nondecreasing dist order
}
// A valState records the register allocation state for a (pre-regalloc) value.
type valState struct {
regs regMask // the set of registers holding a Value (usually just one)
uses *use // list of uses in this block
spill *Value // spilled copy of the Value (if any)
restoreMin int32 // minimum of all restores' blocks' sdom.entry
restoreMax int32 // maximum of all restores' blocks' sdom.exit
needReg bool // cached value of !v.Type.IsMemory() && !v.Type.IsVoid() && !.v.Type.IsFlags()
rematerializeable bool // cached value of v.rematerializeable()
}
type regState struct {
v *Value // Original (preregalloc) Value stored in this register.
c *Value // A Value equal to v which is currently in a register. Might be v or a copy of it.
// If a register is unused, v==c==nil
}
type regAllocState struct {
f *Func
sdom SparseTree
registers []Register
numRegs register
SPReg register
SBReg register
GReg register
allocatable regMask
// for each block, its primary predecessor.
// A predecessor of b is primary if it is the closest
// predecessor that appears before b in the layout order.
// We record the index in the Preds list where the primary predecessor sits.
primary []int32
// live values at the end of each block. live[b.ID] is a list of value IDs
// which are live at the end of b, together with a count of how many instructions
// forward to the next use.
live [][]liveInfo
// desired register assignments at the end of each block.
// Note that this is a static map computed before allocation occurs. Dynamic
// register desires (from partially completed allocations) will trump
// this information.
desired []desiredState
// current state of each (preregalloc) Value
values []valState
// names associated with each Value
valueNames [][]LocalSlot
// ID of SP, SB values
sp, sb ID
// For each Value, map from its value ID back to the
// preregalloc Value it was derived from.
orig []*Value
// current state of each register
regs []regState
// registers that contain values which can't be kicked out
nospill regMask
// mask of registers currently in use
used regMask
// mask of registers used in the current instruction
tmpused regMask
// current block we're working on
curBlock *Block
// cache of use records
freeUseRecords *use
// endRegs[blockid] is the register state at the end of each block.
// encoded as a set of endReg records.
endRegs [][]endReg
// startRegs[blockid] is the register state at the start of merge blocks.
// saved state does not include the state of phi ops in the block.
startRegs [][]startReg
// spillLive[blockid] is the set of live spills at the end of each block
spillLive [][]ID
// a set of copies we generated to move things around, and
// whether it is used in shuffle. Unused copies will be deleted.
copies map[*Value]bool
loopnest *loopnest
}
type endReg struct {
r register
v *Value // pre-regalloc value held in this register (TODO: can we use ID here?)
c *Value // cached version of the value
}
type startReg struct {
r register
v *Value // pre-regalloc value needed in this register
c *Value // cached version of the value
pos src.XPos // source position of use of this register
}
// freeReg frees up register r. Any current user of r is kicked out.
func (s *regAllocState) freeReg(r register) {
s.freeOrResetReg(r, false)
}
// freeOrResetReg frees up register r. Any current user of r is kicked out.
// resetting indicates that the operation is only for bookkeeping,
// e.g. when clearing out state upon entry to a new block.
func (s *regAllocState) freeOrResetReg(r register, resetting bool) {
v := s.regs[r].v
if v == nil {
s.f.Fatalf("tried to free an already free register %d\n", r)
}
// Mark r as unused.
if s.f.pass.debug > regDebug {
fmt.Printf("freeReg %s (dump %s/%s)\n", &s.registers[r], v, s.regs[r].c)
}
if !resetting && s.f.Config.ctxt.Flag_locationlists && len(s.valueNames[v.ID]) != 0 {
kill := s.curBlock.NewValue0(src.NoXPos, OpRegKill, types.TypeVoid)
for int(kill.ID) >= len(s.orig) {
s.orig = append(s.orig, nil)
}
for _, name := range s.valueNames[v.ID] {
s.f.NamedValues[name] = append(s.f.NamedValues[name], kill)
}
s.f.setHome(kill, &s.registers[r])
}
s.regs[r] = regState{}
s.values[v.ID].regs &^= regMask(1) << r
s.used &^= regMask(1) << r
}
// freeRegs frees up all registers listed in m.
func (s *regAllocState) freeRegs(m regMask) {
for m&s.used != 0 {
s.freeReg(pickReg(m & s.used))
}
}
// setOrig records that c's original value is the same as
// v's original value.
func (s *regAllocState) setOrig(c *Value, v *Value) {
for int(c.ID) >= len(s.orig) {
s.orig = append(s.orig, nil)
}
if s.orig[c.ID] != nil {
s.f.Fatalf("orig value set twice %s %s", c, v)
}
s.orig[c.ID] = s.orig[v.ID]
}
// assignReg assigns register r to hold c, a copy of v.
// r must be unused.
func (s *regAllocState) assignReg(r register, v *Value, c *Value) {
if s.f.pass.debug > regDebug {
fmt.Printf("assignReg %s %s/%s\n", &s.registers[r], v, c)
}
if s.regs[r].v != nil {
s.f.Fatalf("tried to assign register %d to %s/%s but it is already used by %s", r, v, c, s.regs[r].v)
}
// Update state.
s.regs[r] = regState{v, c}
s.values[v.ID].regs |= regMask(1) << r
s.used |= regMask(1) << r
s.f.setHome(c, &s.registers[r])
}
// allocReg chooses a register from the set of registers in mask.
// If there is no unused register, a Value will be kicked out of
// a register to make room.
func (s *regAllocState) allocReg(mask regMask, v *Value) register {
mask &= s.allocatable
mask &^= s.nospill
if mask == 0 {
s.f.Fatalf("no register available for %s", v)
}
// Pick an unused register if one is available.
if mask&^s.used != 0 {
return pickReg(mask &^ s.used)
}
// Pick a value to spill. Spill the value with the
// farthest-in-the-future use.
// TODO: Prefer registers with already spilled Values?
// TODO: Modify preference using affinity graph.
// TODO: if a single value is in multiple registers, spill one of them
// before spilling a value in just a single register.
// Find a register to spill. We spill the register containing the value
// whose next use is as far in the future as possible.
// https://en.wikipedia.org/wiki/Page_replacement_algorithm#The_theoretically_optimal_page_replacement_algorithm
var r register
maxuse := int32(-1)
for t := register(0); t < s.numRegs; t++ {
if mask>>t&1 == 0 {
continue
}
v := s.regs[t].v
if n := s.values[v.ID].uses.dist; n > maxuse {
// v's next use is farther in the future than any value
// we've seen so far. A new best spill candidate.
r = t
maxuse = n
}
}
if maxuse == -1 {
s.f.Fatalf("couldn't find register to spill")
}
// Try to move it around before kicking out, if there is a free register.
// We generate a Copy and record it. It will be deleted if never used.
v2 := s.regs[r].v
m := s.compatRegs(v2.Type) &^ s.used &^ s.tmpused &^ (regMask(1) << r)
if m != 0 && !s.values[v2.ID].rematerializeable && countRegs(s.values[v2.ID].regs) == 1 {
r2 := pickReg(m)
c := s.curBlock.NewValue1(v2.Pos, OpCopy, v2.Type, s.regs[r].c)
s.copies[c] = false
if s.f.pass.debug > regDebug {
fmt.Printf("copy %s to %s : %s\n", v2, c, &s.registers[r2])
}
s.setOrig(c, v2)
s.assignReg(r2, v2, c)
}
s.freeReg(r)
return r
}
// makeSpill returns a Value which represents the spilled value of v.
// b is the block in which the spill is used.
func (s *regAllocState) makeSpill(v *Value, b *Block) *Value {
vi := &s.values[v.ID]
if vi.spill != nil {
// Final block not known - keep track of subtree where restores reside.
vi.restoreMin = min32(vi.restoreMin, s.sdom[b.ID].entry)
vi.restoreMax = max32(vi.restoreMax, s.sdom[b.ID].exit)
return vi.spill
}
// Make a spill for v. We don't know where we want
// to put it yet, so we leave it blockless for now.
spill := s.f.newValueNoBlock(OpStoreReg, v.Type, v.Pos)
// We also don't know what the spill's arg will be.
// Leave it argless for now.
s.setOrig(spill, v)
vi.spill = spill
vi.restoreMin = s.sdom[b.ID].entry
vi.restoreMax = s.sdom[b.ID].exit
return spill
}
// allocValToReg allocates v to a register selected from regMask and
// returns the register copy of v. Any previous user is kicked out and spilled
// (if necessary). Load code is added at the current pc. If nospill is set the
// allocated register is marked nospill so the assignment cannot be
// undone until the caller allows it by clearing nospill. Returns a
// *Value which is either v or a copy of v allocated to the chosen register.
func (s *regAllocState) allocValToReg(v *Value, mask regMask, nospill bool, pos src.XPos) *Value {
vi := &s.values[v.ID]
// Check if v is already in a requested register.
if mask&vi.regs != 0 {
r := pickReg(mask & vi.regs)
if s.regs[r].v != v || s.regs[r].c == nil {
panic("bad register state")
}
if nospill {
s.nospill |= regMask(1) << r
}
return s.regs[r].c
}
// Allocate a register.
r := s.allocReg(mask, v)
// Allocate v to the new register.
var c *Value
if vi.regs != 0 {
// Copy from a register that v is already in.
r2 := pickReg(vi.regs)
if s.regs[r2].v != v {
panic("bad register state")
}
c = s.curBlock.NewValue1(pos, OpCopy, v.Type, s.regs[r2].c)
} else if v.rematerializeable() {
// Rematerialize instead of loading from the spill location.
c = v.copyIntoWithXPos(s.curBlock, pos)
} else {
// Load v from its spill location.
spill := s.makeSpill(v, s.curBlock)
if s.f.pass.debug > logSpills {
s.f.Warnl(vi.spill.Pos, "load spill for %v from %v", v, spill)
}
c = s.curBlock.NewValue1(pos, OpLoadReg, v.Type, spill)
}
s.setOrig(c, v)
s.assignReg(r, v, c)
if nospill {
s.nospill |= regMask(1) << r
}
return c
}
// isLeaf reports whether f performs any calls.
func isLeaf(f *Func) bool {
for _, b := range f.Blocks {
for _, v := range b.Values {
if opcodeTable[v.Op].call {
return false
}
}
}
return true
}
func (s *regAllocState) init(f *Func) {
s.f = f
s.f.RegAlloc = s.f.Cache.locs[:0]
s.registers = f.Config.registers
if nr := len(s.registers); nr == 0 || nr > int(noRegister) || nr > int(unsafe.Sizeof(regMask(0))*8) {
s.f.Fatalf("bad number of registers: %d", nr)
} else {
s.numRegs = register(nr)
}
// Locate SP, SB, and g registers.
s.SPReg = noRegister
s.SBReg = noRegister
s.GReg = noRegister
for r := register(0); r < s.numRegs; r++ {
switch s.registers[r].String() {
case "SP":
s.SPReg = r
case "SB":
s.SBReg = r
case "g":
s.GReg = r
}
}
// Make sure we found all required registers.
switch noRegister {
case s.SPReg:
s.f.Fatalf("no SP register found")
case s.SBReg:
s.f.Fatalf("no SB register found")
case s.GReg:
if f.Config.hasGReg {
s.f.Fatalf("no g register found")
}
}
// Figure out which registers we're allowed to use.
s.allocatable = s.f.Config.gpRegMask | s.f.Config.fpRegMask | s.f.Config.specialRegMask
s.allocatable &^= 1 << s.SPReg
s.allocatable &^= 1 << s.SBReg
if s.f.Config.hasGReg {
s.allocatable &^= 1 << s.GReg
}
if s.f.Config.ctxt.Framepointer_enabled && s.f.Config.FPReg >= 0 {
s.allocatable &^= 1 << uint(s.f.Config.FPReg)
}
if s.f.Config.LinkReg != -1 {
if isLeaf(f) {
// Leaf functions don't save/restore the link register.
s.allocatable &^= 1 << uint(s.f.Config.LinkReg)
}
if s.f.Config.arch == "arm" && objabi.GOARM == 5 {
// On ARMv5 we insert softfloat calls at each FP instruction.
// This clobbers LR almost everywhere. Disable allocating LR
// on ARMv5.
s.allocatable &^= 1 << uint(s.f.Config.LinkReg)
}
}
if s.f.Config.ctxt.Flag_dynlink {
switch s.f.Config.arch {
case "amd64":
s.allocatable &^= 1 << 15 // R15
case "arm":
s.allocatable &^= 1 << 9 // R9
case "ppc64le": // R2 already reserved.
// nothing to do
case "arm64":
// nothing to do?
case "386":
// nothing to do.
// Note that for Flag_shared (position independent code)
// we do need to be careful, but that carefulness is hidden
// in the rewrite rules so we always have a free register
// available for global load/stores. See gen/386.rules (search for Flag_shared).
case "s390x":
// nothing to do, R10 & R11 already reserved
default:
s.f.fe.Fatalf(src.NoXPos, "arch %s not implemented", s.f.Config.arch)
}
}
if s.f.Config.nacl {
switch s.f.Config.arch {
case "arm":
s.allocatable &^= 1 << 9 // R9 is "thread pointer" on nacl/arm
case "amd64p32":
s.allocatable &^= 1 << 5 // BP - reserved for nacl
s.allocatable &^= 1 << 15 // R15 - reserved for nacl
}
}
if s.f.Config.use387 {
s.allocatable &^= 1 << 15 // X7 disallowed (one 387 register is used as scratch space during SSE->387 generation in ../x86/387.go)
}
s.regs = make([]regState, s.numRegs)
s.values = make([]valState, f.NumValues())
s.orig = make([]*Value, f.NumValues())
s.copies = make(map[*Value]bool)
if s.f.Config.ctxt.Flag_locationlists {
s.valueNames = make([][]LocalSlot, f.NumValues())
for slot, values := range f.NamedValues {
if isSynthetic(&slot) {
continue
}
for _, value := range values {
s.valueNames[value.ID] = append(s.valueNames[value.ID], slot)
}
}
}
for _, b := range f.Blocks {
for _, v := range b.Values {
if !v.Type.IsMemory() && !v.Type.IsVoid() && !v.Type.IsFlags() && !v.Type.IsTuple() {
s.values[v.ID].needReg = true
s.values[v.ID].rematerializeable = v.rematerializeable()
s.orig[v.ID] = v
}
// Note: needReg is false for values returning Tuple types.
// Instead, we mark the corresponding Selects as needReg.
}
}
s.computeLive()
// Compute block order. This array allows us to distinguish forward edges
// from backward edges and compute how far they go.
blockOrder := make([]int32, f.NumBlocks())
for i, b := range f.Blocks {
blockOrder[b.ID] = int32(i)
}
// Compute primary predecessors.
s.primary = make([]int32, f.NumBlocks())
for _, b := range f.Blocks {
best := -1
for i, e := range b.Preds {
p := e.b
if blockOrder[p.ID] >= blockOrder[b.ID] {
continue // backward edge
}
if best == -1 || blockOrder[p.ID] > blockOrder[b.Preds[best].b.ID] {
best = i
}
}
s.primary[b.ID] = int32(best)
}
s.endRegs = make([][]endReg, f.NumBlocks())
s.startRegs = make([][]startReg, f.NumBlocks())
s.spillLive = make([][]ID, f.NumBlocks())
s.sdom = f.sdom()
}
// Adds a use record for id at distance dist from the start of the block.
// All calls to addUse must happen with nonincreasing dist.
func (s *regAllocState) addUse(id ID, dist int32, pos src.XPos) {
r := s.freeUseRecords
if r != nil {
s.freeUseRecords = r.next
} else {
r = &use{}
}
r.dist = dist
r.pos = pos
r.next = s.values[id].uses
s.values[id].uses = r
if r.next != nil && dist > r.next.dist {
s.f.Fatalf("uses added in wrong order")
}
}
// advanceUses advances the uses of v's args from the state before v to the state after v.
// Any values which have no more uses are deallocated from registers.
func (s *regAllocState) advanceUses(v *Value) {
for _, a := range v.Args {
if !s.values[a.ID].needReg {
continue
}
ai := &s.values[a.ID]
r := ai.uses
ai.uses = r.next
if r.next == nil {
// Value is dead, free all registers that hold it.
s.freeRegs(ai.regs)
}
r.next = s.freeUseRecords
s.freeUseRecords = r
}
}
// liveAfterCurrentInstruction reports whether v is live after
// the current instruction is completed. v must be used by the
// current instruction.
func (s *regAllocState) liveAfterCurrentInstruction(v *Value) bool {
u := s.values[v.ID].uses
d := u.dist
for u != nil && u.dist == d {
u = u.next
}
return u != nil && u.dist > d
}
// Sets the state of the registers to that encoded in regs.
func (s *regAllocState) setState(regs []endReg) {
for s.used != 0 {
s.freeOrResetReg(pickReg(s.used), true)
}
for _, x := range regs {
s.assignReg(x.r, x.v, x.c)
}
}
// compatRegs returns the set of registers which can store a type t.
func (s *regAllocState) compatRegs(t *types.Type) regMask {
var m regMask
if t.IsTuple() || t.IsFlags() {
return 0
}
if t.IsFloat() || t == types.TypeInt128 {
m = s.f.Config.fpRegMask
} else {
m = s.f.Config.gpRegMask
}
return m & s.allocatable
}
func (s *regAllocState) regalloc(f *Func) {
regValLiveSet := f.newSparseSet(f.NumValues()) // set of values that may be live in register
defer f.retSparseSet(regValLiveSet)
var oldSched []*Value
var phis []*Value
var phiRegs []register
var args []*Value
// Data structure used for computing desired registers.
var desired desiredState
// Desired registers for inputs & outputs for each instruction in the block.
type dentry struct {
out [4]register // desired output registers
in [3][4]register // desired input registers (for inputs 0,1, and 2)
}
var dinfo []dentry
if f.Entry != f.Blocks[0] {
f.Fatalf("entry block must be first")
}
for _, b := range f.Blocks {
if s.f.pass.debug > regDebug {
fmt.Printf("Begin processing block %v\n", b)
}
s.curBlock = b
// Initialize regValLiveSet and uses fields for this block.
// Walk backwards through the block doing liveness analysis.
regValLiveSet.clear()
for _, e := range s.live[b.ID] {
s.addUse(e.ID, int32(len(b.Values))+e.dist, e.pos) // pseudo-uses from beyond end of block
regValLiveSet.add(e.ID)
}
if v := b.Control; v != nil && s.values[v.ID].needReg {
s.addUse(v.ID, int32(len(b.Values)), b.Pos) // pseudo-use by control value
regValLiveSet.add(v.ID)
}
for i := len(b.Values) - 1; i >= 0; i-- {
v := b.Values[i]
regValLiveSet.remove(v.ID)
if v.Op == OpPhi {
// Remove v from the live set, but don't add
// any inputs. This is the state the len(b.Preds)>1
// case below desires; it wants to process phis specially.
continue
}
if opcodeTable[v.Op].call {
// Function call clobbers all the registers but SP and SB.
regValLiveSet.clear()
if s.sp != 0 && s.values[s.sp].uses != nil {
regValLiveSet.add(s.sp)
}
if s.sb != 0 && s.values[s.sb].uses != nil {
regValLiveSet.add(s.sb)
}
}
for _, a := range v.Args {
if !s.values[a.ID].needReg {
continue
}
s.addUse(a.ID, int32(i), v.Pos)
regValLiveSet.add(a.ID)
}
}
if s.f.pass.debug > regDebug {
fmt.Printf("uses for %s:%s\n", s.f.Name, b)
for i := range s.values {
vi := &s.values[i]
u := vi.uses
if u == nil {
continue
}
fmt.Printf(" v%d:", i)
for u != nil {
fmt.Printf(" %d", u.dist)
u = u.next
}
fmt.Println()
}
}
// Make a copy of the block schedule so we can generate a new one in place.
// We make a separate copy for phis and regular values.
nphi := 0
for _, v := range b.Values {
if v.Op != OpPhi {
break
}
nphi++
}
phis = append(phis[:0], b.Values[:nphi]...)
oldSched = append(oldSched[:0], b.Values[nphi:]...)
b.Values = b.Values[:0]
// Initialize start state of block.
if b == f.Entry {
// Regalloc state is empty to start.
if nphi > 0 {
f.Fatalf("phis in entry block")
}
} else if len(b.Preds) == 1 {
// Start regalloc state with the end state of the previous block.
s.setState(s.endRegs[b.Preds[0].b.ID])
if nphi > 0 {
f.Fatalf("phis in single-predecessor block")
}
// Drop any values which are no longer live.
// This may happen because at the end of p, a value may be
// live but only used by some other successor of p.
for r := register(0); r < s.numRegs; r++ {
v := s.regs[r].v
if v != nil && !regValLiveSet.contains(v.ID) {
s.freeReg(r)
}
}
} else {
// This is the complicated case. We have more than one predecessor,
// which means we may have Phi ops.
// Start with the final register state of the primary predecessor
idx := s.primary[b.ID]
if idx < 0 {
f.Fatalf("block with no primary predecessor %s", b)
}
p := b.Preds[idx].b
s.setState(s.endRegs[p.ID])
if s.f.pass.debug > regDebug {
fmt.Printf("starting merge block %s with end state of %s:\n", b, p)
for _, x := range s.endRegs[p.ID] {
fmt.Printf(" %s: orig:%s cache:%s\n", &s.registers[x.r], x.v, x.c)
}
}
// Decide on registers for phi ops. Use the registers determined
// by the primary predecessor if we can.
// TODO: pick best of (already processed) predecessors?
// Majority vote? Deepest nesting level?
phiRegs = phiRegs[:0]
var phiUsed regMask
for _, v := range phis {
if !s.values[v.ID].needReg {
phiRegs = append(phiRegs, noRegister)
continue
}
a := v.Args[idx]
// Some instructions target not-allocatable registers.
// They're not suitable for further (phi-function) allocation.
m := s.values[a.ID].regs &^ phiUsed & s.allocatable
if m != 0 {
r := pickReg(m)
phiUsed |= regMask(1) << r
phiRegs = append(phiRegs, r)
} else {
phiRegs = append(phiRegs, noRegister)
}
}
// Second pass - deallocate any phi inputs which are now dead.
for i, v := range phis {
if !s.values[v.ID].needReg {
continue
}
a := v.Args[idx]
if !regValLiveSet.contains(a.ID) {
// Input is dead beyond the phi, deallocate
// anywhere else it might live.
s.freeRegs(s.values[a.ID].regs)
} else {
// Input is still live.
// Try to move it around before kicking out, if there is a free register.
// We generate a Copy in the predecessor block and record it. It will be
// deleted if never used.
r := phiRegs[i]
if r == noRegister {
continue
}
// Pick a free register. At this point some registers used in the predecessor
// block may have been deallocated. Those are the ones used for Phis. Exclude
// them (and they are not going to be helpful anyway).
m := s.compatRegs(a.Type) &^ s.used &^ phiUsed
if m != 0 && !s.values[a.ID].rematerializeable && countRegs(s.values[a.ID].regs) == 1 {
r2 := pickReg(m)
c := p.NewValue1(a.Pos, OpCopy, a.Type, s.regs[r].c)
s.copies[c] = false
if s.f.pass.debug > regDebug {
fmt.Printf("copy %s to %s : %s\n", a, c, &s.registers[r2])
}
s.setOrig(c, a)
s.assignReg(r2, a, c)
s.endRegs[p.ID] = append(s.endRegs[p.ID], endReg{r2, a, c})
}
s.freeReg(r)
}
}
// Copy phi ops into new schedule.
b.Values = append(b.Values, phis...)
// Third pass - pick registers for phis whose inputs
// were not in a register.
for i, v := range phis {
if !s.values[v.ID].needReg {
continue
}
if phiRegs[i] != noRegister {
continue
}
if s.f.Config.use387 && v.Type.IsFloat() {
continue // 387 can't handle floats in registers between blocks
}
m := s.compatRegs(v.Type) &^ phiUsed &^ s.used
if m != 0 {
r := pickReg(m)
phiRegs[i] = r
phiUsed |= regMask(1) << r
}
}
// Set registers for phis. Add phi spill code.
for i, v := range phis {
if !s.values[v.ID].needReg {
continue
}
r := phiRegs[i]
if r == noRegister {
// stack-based phi
// Spills will be inserted in all the predecessors below.
s.values[v.ID].spill = v // v starts life spilled
continue
}
// register-based phi
s.assignReg(r, v, v)
}
// Deallocate any values which are no longer live. Phis are excluded.
for r := register(0); r < s.numRegs; r++ {
if phiUsed>>r&1 != 0 {
continue
}
v := s.regs[r].v
if v != nil && !regValLiveSet.contains(v.ID) {
s.freeReg(r)
}
}
// Save the starting state for use by merge edges.
var regList []startReg
for r := register(0); r < s.numRegs; r++ {
v := s.regs[r].v
if v == nil {
continue
}
if phiUsed>>r&1 != 0 {
// Skip registers that phis used, we'll handle those
// specially during merge edge processing.
continue
}
regList = append(regList, startReg{r, v, s.regs[r].c, s.values[v.ID].uses.pos})
}
s.startRegs[b.ID] = regList
if s.f.pass.debug > regDebug {
fmt.Printf("after phis\n")
for _, x := range s.startRegs[b.ID] {
fmt.Printf(" %s: v%d\n", &s.registers[x.r], x.v.ID)
}
}
}
// Allocate space to record the desired registers for each value.
dinfo = dinfo[:0]
for i := 0; i < len(oldSched); i++ {
dinfo = append(dinfo, dentry{})
}
// Load static desired register info at the end of the block.
desired.copy(&s.desired[b.ID])
// Check actual assigned registers at the start of the next block(s).
// Dynamically assigned registers will trump the static
// desired registers computed during liveness analysis.
// Note that we do this phase after startRegs is set above, so that
// we get the right behavior for a block which branches to itself.
for _, e := range b.Succs {
succ := e.b
// TODO: prioritize likely successor?
for _, x := range s.startRegs[succ.ID] {
desired.add(x.v.ID, x.r)
}
// Process phi ops in succ.
pidx := e.i
for _, v := range succ.Values {
if v.Op != OpPhi {
continue
}
if !s.values[v.ID].needReg {
continue
}
rp, ok := s.f.getHome(v.ID).(*Register)
if !ok {
continue
}
desired.add(v.Args[pidx].ID, register(rp.num))
}
}
// Walk values backwards computing desired register info.
// See computeLive for more comments.
for i := len(oldSched) - 1; i >= 0; i-- {
v := oldSched[i]
prefs := desired.remove(v.ID)
desired.clobber(opcodeTable[v.Op].reg.clobbers)
for _, j := range opcodeTable[v.Op].reg.inputs {
if countRegs(j.regs) != 1 {
continue
}
desired.clobber(j.regs)
desired.add(v.Args[j.idx].ID, pickReg(j.regs))
}
if opcodeTable[v.Op].resultInArg0 {
if opcodeTable[v.Op].commutative {
desired.addList(v.Args[1].ID, prefs)
}
desired.addList(v.Args[0].ID, prefs)
}
// Save desired registers for this value.
dinfo[i].out = prefs
for j, a := range v.Args {
if j >= len(dinfo[i].in) {
break
}
dinfo[i].in[j] = desired.get(a.ID)
}
}
// Process all the non-phi values.
for idx, v := range oldSched {
if s.f.pass.debug > regDebug {
fmt.Printf(" processing %s\n", v.LongString())
}
regspec := opcodeTable[v.Op].reg
if v.Op == OpPhi {
f.Fatalf("phi %s not at start of block", v)
}
if v.Op == OpSP {
s.assignReg(s.SPReg, v, v)
b.Values = append(b.Values, v)
s.advanceUses(v)
s.sp = v.ID
continue
}
if v.Op == OpSB {
s.assignReg(s.SBReg, v, v)
b.Values = append(b.Values, v)
s.advanceUses(v)
s.sb = v.ID
continue
}
if v.Op == OpSelect0 || v.Op == OpSelect1 {
if s.values[v.ID].needReg {
var i = 0
if v.Op == OpSelect1 {
i = 1
}
s.assignReg(register(s.f.getHome(v.Args[0].ID).(LocPair)[i].(*Register).num), v, v)
}
b.Values = append(b.Values, v)
s.advanceUses(v)
goto issueSpill
}
if v.Op == OpGetG && s.f.Config.hasGReg {
// use hardware g register
if s.regs[s.GReg].v != nil {
s.freeReg(s.GReg) // kick out the old value
}
s.assignReg(s.GReg, v, v)
b.Values = append(b.Values, v)
s.advanceUses(v)
goto issueSpill
}
if v.Op == OpArg {
// Args are "pre-spilled" values. We don't allocate
// any register here. We just set up the spill pointer to
// point at itself and any later user will restore it to use it.
s.values[v.ID].spill = v
b.Values = append(b.Values, v)
s.advanceUses(v)
continue
}
if v.Op == OpKeepAlive {
// Make sure the argument to v is still live here.
s.advanceUses(v)
a := v.Args[0]
vi := &s.values[a.ID]
if vi.regs == 0 && !vi.rematerializeable {
// Use the spill location.
// This forces later liveness analysis to make the
// value live at this point.
v.SetArg(0, s.makeSpill(a, b))
} else {
// In-register and rematerializeable values are already live.
// These are typically rematerializeable constants like nil,
// or values of a variable that were modified since the last call.
v.Op = OpCopy
v.SetArgs1(v.Args[1])
}
b.Values = append(b.Values, v)
continue
}
if len(regspec.inputs) == 0 && len(regspec.outputs) == 0 {
// No register allocation required (or none specified yet)
s.freeRegs(regspec.clobbers)
b.Values = append(b.Values, v)
s.advanceUses(v)
continue
}
if s.values[v.ID].rematerializeable {
// Value is rematerializeable, don't issue it here.
// It will get issued just before each use (see
// allocValueToReg).
for _, a := range v.Args {
a.Uses--
}
s.advanceUses(v)
continue
}
if s.f.pass.debug > regDebug {
fmt.Printf("value %s\n", v.LongString())
fmt.Printf(" out:")
for _, r := range dinfo[idx].out {
if r != noRegister {
fmt.Printf(" %s", &s.registers[r])
}
}
fmt.Println()
for i := 0; i < len(v.Args) && i < 3; i++ {
fmt.Printf(" in%d:", i)
for _, r := range dinfo[idx].in[i] {
if r != noRegister {
fmt.Printf(" %s", &s.registers[r])
}
}
fmt.Println()
}
}
// Move arguments to registers. Process in an ordering defined
// by the register specification (most constrained first).
args = append(args[:0], v.Args...)
for _, i := range regspec.inputs {
mask := i.regs
if mask&s.values[args[i.idx].ID].regs == 0 {
// Need a new register for the input.
mask &= s.allocatable
mask &^= s.nospill
// Used desired register if available.
if i.idx < 3 {
for _, r := range dinfo[idx].in[i.idx] {
if r != noRegister && (mask&^s.used)>>r&1 != 0 {
// Desired register is allowed and unused.
mask = regMask(1) << r
break
}
}
}
// Avoid registers we're saving for other values.
if mask&^desired.avoid != 0 {
mask &^= desired.avoid
}
}
args[i.idx] = s.allocValToReg(args[i.idx], mask, true, v.Pos)
}
// If the output clobbers the input register, make sure we have
// at least two copies of the input register so we don't
// have to reload the value from the spill location.
if opcodeTable[v.Op].resultInArg0 {
var m regMask
if !s.liveAfterCurrentInstruction(v.Args[0]) {
// arg0 is dead. We can clobber its register.
goto ok
}
if s.values[v.Args[0].ID].rematerializeable {
// We can rematerialize the input, don't worry about clobbering it.
goto ok
}
if countRegs(s.values[v.Args[0].ID].regs) >= 2 {
// we have at least 2 copies of arg0. We can afford to clobber one.
goto ok
}
if opcodeTable[v.Op].commutative {
if !s.liveAfterCurrentInstruction(v.Args[1]) {
args[0], args[1] = args[1], args[0]
goto ok
}
if s.values[v.Args[1].ID].rematerializeable {
args[0], args[1] = args[1], args[0]
goto ok
}
if countRegs(s.values[v.Args[1].ID].regs) >= 2 {
args[0], args[1] = args[1], args[0]
goto ok
}
}
// We can't overwrite arg0 (or arg1, if commutative). So we
// need to make a copy of an input so we have a register we can modify.
// Possible new registers to copy into.
m = s.compatRegs(v.Args[0].Type) &^ s.used
if m == 0 {
// No free registers. In this case we'll just clobber
// an input and future uses of that input must use a restore.
// TODO(khr): We should really do this like allocReg does it,
// spilling the value with the most distant next use.
goto ok
}
// Try to move an input to the desired output.
for _, r := range dinfo[idx].out {
if r != noRegister && m>>r&1 != 0 {
m = regMask(1) << r
args[0] = s.allocValToReg(v.Args[0], m, true, v.Pos)
// Note: we update args[0] so the instruction will
// use the register copy we just made.
goto ok
}
}
// Try to copy input to its desired location & use its old
// location as the result register.
for _, r := range dinfo[idx].in[0] {
if r != noRegister && m>>r&1 != 0 {
m = regMask(1) << r
c := s.allocValToReg(v.Args[0], m, true, v.Pos)
s.copies[c] = false
// Note: no update to args[0] so the instruction will
// use the original copy.
goto ok
}
}
if opcodeTable[v.Op].commutative {
for _, r := range dinfo[idx].in[1] {
if r != noRegister && m>>r&1 != 0 {
m = regMask(1) << r
c := s.allocValToReg(v.Args[1], m, true, v.Pos)
s.copies[c] = false
args[0], args[1] = args[1], args[0]
goto ok
}
}
}
// Avoid future fixed uses if we can.
if m&^desired.avoid != 0 {
m &^= desired.avoid
}
// Save input 0 to a new register so we can clobber it.
c := s.allocValToReg(v.Args[0], m, true, v.Pos)
s.copies[c] = false
}
ok:
// Now that all args are in regs, we're ready to issue the value itself.
// Before we pick a register for the output value, allow input registers
// to be deallocated. We do this here so that the output can use the
// same register as a dying input.
if !opcodeTable[v.Op].resultNotInArgs {
s.tmpused = s.nospill
s.nospill = 0
s.advanceUses(v) // frees any registers holding args that are no longer live
}
// Dump any registers which will be clobbered
s.freeRegs(regspec.clobbers)
s.tmpused |= regspec.clobbers
// Pick registers for outputs.
{
outRegs := [2]register{noRegister, noRegister}
var used regMask
for _, out := range regspec.outputs {
mask := out.regs & s.allocatable &^ used
if mask == 0 {
continue
}
if opcodeTable[v.Op].resultInArg0 && out.idx == 0 {
if !opcodeTable[v.Op].commutative {
// Output must use the same register as input 0.
r := register(s.f.getHome(args[0].ID).(*Register).num)
mask = regMask(1) << r
} else {
// Output must use the same register as input 0 or 1.
r0 := register(s.f.getHome(args[0].ID).(*Register).num)
r1 := register(s.f.getHome(args[1].ID).(*Register).num)
// Check r0 and r1 for desired output register.
found := false
for _, r := range dinfo[idx].out {
if (r == r0 || r == r1) && (mask&^s.used)>>r&1 != 0 {
mask = regMask(1) << r
found = true
if r == r1 {
args[0], args[1] = args[1], args[0]
}
break
}
}
if !found {
// Neither are desired, pick r0.
mask = regMask(1) << r0
}
}
}
for _, r := range dinfo[idx].out {
if r != noRegister && (mask&^s.used)>>r&1 != 0 {
// Desired register is allowed and unused.
mask = regMask(1) << r
break
}
}
// Avoid registers we're saving for other values.
if mask&^desired.avoid != 0 {
mask &^= desired.avoid
}
r := s.allocReg(mask, v)
outRegs[out.idx] = r
used |= regMask(1) << r
s.tmpused |= regMask(1) << r
}
// Record register choices
if v.Type.IsTuple() {
var outLocs LocPair
if r := outRegs[0]; r != noRegister {
outLocs[0] = &s.registers[r]
}
if r := outRegs[1]; r != noRegister {
outLocs[1] = &s.registers[r]
}
s.f.setHome(v, outLocs)
// Note that subsequent SelectX instructions will do the assignReg calls.
} else {
if r := outRegs[0]; r != noRegister {
s.assignReg(r, v, v)
}
}
}
// deallocate dead args, if we have not done so
if opcodeTable[v.Op].resultNotInArgs {
s.nospill = 0
s.advanceUses(v) // frees any registers holding args that are no longer live
}
s.tmpused = 0
// Issue the Value itself.
for i, a := range args {
v.SetArg(i, a) // use register version of arguments
}
b.Values = append(b.Values, v)
issueSpill:
}
// Load control value into reg.
if v := b.Control; v != nil && s.values[v.ID].needReg {
if s.f.pass.debug > regDebug {
fmt.Printf(" processing control %s\n", v.LongString())
}
// We assume that a control input can be passed in any
// type-compatible register. If this turns out not to be true,
// we'll need to introduce a regspec for a block's control value.
b.Control = s.allocValToReg(v, s.compatRegs(v.Type), false, b.Pos)
if b.Control != v {
v.Uses--
b.Control.Uses++
}
// Remove this use from the uses list.
vi := &s.values[v.ID]
u := vi.uses
vi.uses = u.next
if u.next == nil {
s.freeRegs(vi.regs) // value is dead
}
u.next = s.freeUseRecords
s.freeUseRecords = u
}
// Spill any values that can't live across basic block boundaries.
if s.f.Config.use387 {
s.freeRegs(s.f.Config.fpRegMask)
}
// If we are approaching a merge point and we are the primary
// predecessor of it, find live values that we use soon after
// the merge point and promote them to registers now.
if len(b.Succs) == 1 {
// For this to be worthwhile, the loop must have no calls in it.
top := b.Succs[0].b
loop := s.loopnest.b2l[top.ID]
if loop == nil || loop.header != top || loop.containsCall {
goto badloop
}
// TODO: sort by distance, pick the closest ones?
for _, live := range s.live[b.ID] {
if live.dist >= unlikelyDistance {
// Don't preload anything live after the loop.
continue
}
vid := live.ID
vi := &s.values[vid]
if vi.regs != 0 {
continue
}
if vi.rematerializeable {
continue
}
v := s.orig[vid]
if s.f.Config.use387 && v.Type.IsFloat() {
continue // 387 can't handle floats in registers between blocks
}
m := s.compatRegs(v.Type) &^ s.used
if m&^desired.avoid != 0 {
m &^= desired.avoid
}
if m != 0 {
s.allocValToReg(v, m, false, b.Pos)
}
}
}
badloop:
;
// Save end-of-block register state.
// First count how many, this cuts allocations in half.
k := 0
for r := register(0); r < s.numRegs; r++ {
v := s.regs[r].v
if v == nil {
continue
}
k++
}
regList := make([]endReg, 0, k)
for r := register(0); r < s.numRegs; r++ {
v := s.regs[r].v
if v == nil {
continue
}
regList = append(regList, endReg{r, v, s.regs[r].c})
}
s.endRegs[b.ID] = regList
if checkEnabled {
regValLiveSet.clear()
for _, x := range s.live[b.ID] {
regValLiveSet.add(x.ID)
}
for r := register(0); r < s.numRegs; r++ {
v := s.regs[r].v
if v == nil {
continue
}
if !regValLiveSet.contains(v.ID) {
s.f.Fatalf("val %s is in reg but not live at end of %s", v, b)
}
}
}
// If a value is live at the end of the block and
// isn't in a register, generate a use for the spill location.
// We need to remember this information so that
// the liveness analysis in stackalloc is correct.
for _, e := range s.live[b.ID] {
vi := &s.values[e.ID]
if vi.regs != 0 {
// in a register, we'll use that source for the merge.
continue
}
if vi.rematerializeable {
// we'll rematerialize during the merge.
continue
}
//fmt.Printf("live-at-end spill for %s at %s\n", s.orig[e.ID], b)
spill := s.makeSpill(s.orig[e.ID], b)
s.spillLive[b.ID] = append(s.spillLive[b.ID], spill.ID)
}
// Clear any final uses.
// All that is left should be the pseudo-uses added for values which
// are live at the end of b.
for _, e := range s.live[b.ID] {
u := s.values[e.ID].uses
if u == nil {
f.Fatalf("live at end, no uses v%d", e.ID)
}
if u.next != nil {
f.Fatalf("live at end, too many uses v%d", e.ID)
}
s.values[e.ID].uses = nil
u.next = s.freeUseRecords
s.freeUseRecords = u
}
}
// Decide where the spills we generated will go.
s.placeSpills()
// Anything that didn't get a register gets a stack location here.
// (StoreReg, stack-based phis, inputs, ...)
stacklive := stackalloc(s.f, s.spillLive)
// Fix up all merge edges.
s.shuffle(stacklive)
// Erase any copies we never used.
// Also, an unused copy might be the only use of another copy,
// so continue erasing until we reach a fixed point.
for {
progress := false
for c, used := range s.copies {
if !used && c.Uses == 0 {
if s.f.pass.debug > regDebug {
fmt.Printf("delete copied value %s\n", c.LongString())
}
c.RemoveArg(0)
f.freeValue(c)
delete(s.copies, c)
progress = true
}
}
if !progress {
break
}
}
for _, b := range f.Blocks {
i := 0
for _, v := range b.Values {
if v.Op == OpInvalid {
continue
}
b.Values[i] = v
i++
}
b.Values = b.Values[:i]
}
}
func (s *regAllocState) placeSpills() {
f := s.f
// Precompute some useful info.
phiRegs := make([]regMask, f.NumBlocks())
for _, b := range f.Blocks {
var m regMask
for _, v := range b.Values {
if v.Op == OpRegKill {
continue
}
if v.Op != OpPhi {
break
}
if r, ok := f.getHome(v.ID).(*Register); ok {
m |= regMask(1) << uint(r.num)
}
}
phiRegs[b.ID] = m
}
// Start maps block IDs to the list of spills
// that go at the start of the block (but after any phis).
start := map[ID][]*Value{}
// After maps value IDs to the list of spills
// that go immediately after that value ID.
after := map[ID][]*Value{}
for i := range s.values {
vi := s.values[i]
spill := vi.spill
if spill == nil {
continue
}
if spill.Block != nil {
// Some spills are already fully set up,
// like OpArgs and stack-based phis.
continue
}
v := s.orig[i]
// Walk down the dominator tree looking for a good place to
// put the spill of v. At the start "best" is the best place
// we have found so far.
// TODO: find a way to make this O(1) without arbitrary cutoffs.
best := v.Block
bestArg := v
var bestDepth int16
if l := s.loopnest.b2l[best.ID]; l != nil {
bestDepth = l.depth
}
b := best
const maxSpillSearch = 100
for i := 0; i < maxSpillSearch; i++ {
// Find the child of b in the dominator tree which
// dominates all restores.
p := b
b = nil
for c := s.sdom.Child(p); c != nil && i < maxSpillSearch; c, i = s.sdom.Sibling(c), i+1 {
if s.sdom[c.ID].entry <= vi.restoreMin && s.sdom[c.ID].exit >= vi.restoreMax {
// c also dominates all restores. Walk down into c.
b = c
break
}
}
if b == nil {
// Ran out of blocks which dominate all restores.
break
}
var depth int16
if l := s.loopnest.b2l[b.ID]; l != nil {
depth = l.depth
}
if depth > bestDepth {
// Don't push the spill into a deeper loop.
continue
}
// If v is in a register at the start of b, we can
// place the spill here (after the phis).
if len(b.Preds) == 1 {
for _, e := range s.endRegs[b.Preds[0].b.ID] {
if e.v == v {
// Found a better spot for the spill.
best = b
bestArg = e.c
bestDepth = depth
break
}
}
} else {
for _, e := range s.startRegs[b.ID] {
if e.v == v {
// Found a better spot for the spill.
best = b
bestArg = e.c
bestDepth = depth
break
}
}
}
}
// Put the spill in the best block we found.
spill.Block = best
spill.AddArg(bestArg)
if best == v.Block && v.Op != OpPhi {
// Place immediately after v.
after[v.ID] = append(after[v.ID], spill)
} else {
// Place at the start of best block.
start[best.ID] = append(start[best.ID], spill)
}
}
// Insert spill instructions into the block schedules.
var oldSched []*Value
for _, b := range f.Blocks {
nphi := 0
for _, v := range b.Values {
if v.Op != OpRegKill && v.Op != OpPhi {
break
}
nphi++
}
oldSched = append(oldSched[:0], b.Values[nphi:]...)
b.Values = b.Values[:nphi]
b.Values = append(b.Values, start[b.ID]...)
for _, v := range oldSched {
b.Values = append(b.Values, v)
b.Values = append(b.Values, after[v.ID]...)
}
}
}
// shuffle fixes up all the merge edges (those going into blocks of indegree > 1).
func (s *regAllocState) shuffle(stacklive [][]ID) {
var e edgeState
e.s = s
e.cache = map[ID][]*Value{}
e.contents = map[Location]contentRecord{}
if s.f.pass.debug > regDebug {
fmt.Printf("shuffle %s\n", s.f.Name)
fmt.Println(s.f.String())
}
for _, b := range s.f.Blocks {
if len(b.Preds) <= 1 {
continue
}
e.b = b
for i, edge := range b.Preds {
p := edge.b
e.p = p
e.setup(i, s.endRegs[p.ID], s.startRegs[b.ID], stacklive[p.ID])
e.process()
}
}
}
type edgeState struct {
s *regAllocState
p, b *Block // edge goes from p->b.
// for each pre-regalloc value, a list of equivalent cached values
cache map[ID][]*Value
cachedVals []ID // (superset of) keys of the above map, for deterministic iteration
// map from location to the value it contains
contents map[Location]contentRecord
// desired destination locations
destinations []dstRecord
extra []dstRecord
usedRegs regMask // registers currently holding something
uniqueRegs regMask // registers holding the only copy of a value
finalRegs regMask // registers holding final target
}
type contentRecord struct {
vid ID // pre-regalloc value
c *Value // cached value
final bool // this is a satisfied destination
pos src.XPos // source position of use of the value
}
type dstRecord struct {
loc Location // register or stack slot
vid ID // pre-regalloc value it should contain
splice **Value // place to store reference to the generating instruction
pos src.XPos // source position of use of this location
}
// setup initializes the edge state for shuffling.
func (e *edgeState) setup(idx int, srcReg []endReg, dstReg []startReg, stacklive []ID) {
if e.s.f.pass.debug > regDebug {
fmt.Printf("edge %s->%s\n", e.p, e.b)
}
// Clear state.
for _, vid := range e.cachedVals {
delete(e.cache, vid)
}
e.cachedVals = e.cachedVals[:0]
for k := range e.contents {
delete(e.contents, k)
}
e.usedRegs = 0
e.uniqueRegs = 0
e.finalRegs = 0
// Live registers can be sources.
for _, x := range srcReg {
e.set(&e.s.registers[x.r], x.v.ID, x.c, false, src.NoXPos) // don't care the position of the source
}
// So can all of the spill locations.
for _, spillID := range stacklive {
v := e.s.orig[spillID]
spill := e.s.values[v.ID].spill
if !e.s.sdom.isAncestorEq(spill.Block, e.p) {
// Spills were placed that only dominate the uses found
// during the first regalloc pass. The edge fixup code
// can't use a spill location if the spill doesn't dominate
// the edge.
// We are guaranteed that if the spill doesn't dominate this edge,
// then the value is available in a register (because we called
// makeSpill for every value not in a register at the start
// of an edge).
continue
}
e.set(e.s.f.getHome(spillID), v.ID, spill, false, src.NoXPos) // don't care the position of the source
}
// Figure out all the destinations we need.
dsts := e.destinations[:0]
for _, x := range dstReg {
dsts = append(dsts, dstRecord{&e.s.registers[x.r], x.v.ID, nil, x.pos})
}
// Phis need their args to end up in a specific location.
for _, v := range e.b.Values {
if v.Op == OpRegKill {
continue
}
if v.Op != OpPhi {
break
}
loc := e.s.f.getHome(v.ID)
if loc == nil {
continue
}
dsts = append(dsts, dstRecord{loc, v.Args[idx].ID, &v.Args[idx], v.Pos})
}
e.destinations = dsts
if e.s.f.pass.debug > regDebug {
for _, vid := range e.cachedVals {
a := e.cache[vid]
for _, c := range a {
fmt.Printf("src %s: v%d cache=%s\n", e.s.f.getHome(c.ID), vid, c)
}
}
for _, d := range e.destinations {
fmt.Printf("dst %s: v%d\n", d.loc, d.vid)
}
}
}
// process generates code to move all the values to the right destination locations.
func (e *edgeState) process() {
dsts := e.destinations
// Process the destinations until they are all satisfied.
for len(dsts) > 0 {
i := 0
for _, d := range dsts {
if !e.processDest(d.loc, d.vid, d.splice, d.pos) {
// Failed - save for next iteration.
dsts[i] = d
i++
}
}
if i < len(dsts) {
// Made some progress. Go around again.
dsts = dsts[:i]
// Append any extras destinations we generated.
dsts = append(dsts, e.extra...)
e.extra = e.extra[:0]
continue
}
// We made no progress. That means that any
// remaining unsatisfied moves are in simple cycles.
// For example, A -> B -> C -> D -> A.
// A ----> B
// ^ |
// | |
// | v
// D <---- C
// To break the cycle, we pick an unused register, say R,
// and put a copy of B there.
// A ----> B
// ^ |
// | |
// | v
// D <---- C <---- R=copyofB
// When we resume the outer loop, the A->B move can now proceed,
// and eventually the whole cycle completes.
// Copy any cycle location to a temp register. This duplicates
// one of the cycle entries, allowing the just duplicated value
// to be overwritten and the cycle to proceed.
d := dsts[0]
loc := d.loc
vid := e.contents[loc].vid
c := e.contents[loc].c
r := e.findRegFor(c.Type)
if e.s.f.pass.debug > regDebug {
fmt.Printf("breaking cycle with v%d in %s:%s\n", vid, loc, c)
}
e.erase(r)
if _, isReg := loc.(*Register); isReg {
c = e.p.NewValue1(d.pos, OpCopy, c.Type, c)
} else {
c = e.p.NewValue1(d.pos, OpLoadReg, c.Type, c)
}
e.set(r, vid, c, false, d.pos)
}
}
// processDest generates code to put value vid into location loc. Returns true
// if progress was made.
func (e *edgeState) processDest(loc Location, vid ID, splice **Value, pos src.XPos) bool {
occupant := e.contents[loc]
if occupant.vid == vid {
// Value is already in the correct place.
e.contents[loc] = contentRecord{vid, occupant.c, true, pos}
if splice != nil {
(*splice).Uses--
*splice = occupant.c
occupant.c.Uses++
}
// Note: if splice==nil then c will appear dead. This is
// non-SSA formed code, so be careful after this pass not to run
// deadcode elimination.
if _, ok := e.s.copies[occupant.c]; ok {
// The copy at occupant.c was used to avoid spill.
e.s.copies[occupant.c] = true
}
return true
}
// Check if we're allowed to clobber the destination location.
if len(e.cache[occupant.vid]) == 1 && !e.s.values[occupant.vid].rematerializeable {
// We can't overwrite the last copy
// of a value that needs to survive.
return false
}
// Copy from a source of v, register preferred.
v := e.s.orig[vid]
var c *Value
var src Location
if e.s.f.pass.debug > regDebug {
fmt.Printf("moving v%d to %s\n", vid, loc)
fmt.Printf("sources of v%d:", vid)
}
for _, w := range e.cache[vid] {
h := e.s.f.getHome(w.ID)
if e.s.f.pass.debug > regDebug {
fmt.Printf(" %s:%s", h, w)
}
_, isreg := h.(*Register)
if src == nil || isreg {
c = w
src = h
}
}
if e.s.f.pass.debug > regDebug {
if src != nil {
fmt.Printf(" [use %s]\n", src)
} else {
fmt.Printf(" [no source]\n")
}
}
_, dstReg := loc.(*Register)
// Pre-clobber destination. This avoids the
// following situation:
// - v is currently held in R0 and stacktmp0.
// - We want to copy stacktmp1 to stacktmp0.
// - We choose R0 as the temporary register.
// During the copy, both R0 and stacktmp0 are
// clobbered, losing both copies of v. Oops!
// Erasing the destination early means R0 will not
// be chosen as the temp register, as it will then
// be the last copy of v.
e.erase(loc)
var x *Value
if c == nil {
if !e.s.values[vid].rematerializeable {
e.s.f.Fatalf("can't find source for %s->%s: %s\n", e.p, e.b, v.LongString())
}
if dstReg {
x = v.copyIntoNoXPos(e.p)
} else {
// Rematerialize into stack slot. Need a free
// register to accomplish this.
r := e.findRegFor(v.Type)
e.erase(r)
x = v.copyIntoWithXPos(e.p, pos)
e.set(r, vid, x, false, pos)
// Make sure we spill with the size of the slot, not the
// size of x (which might be wider due to our dropping
// of narrowing conversions).
x = e.p.NewValue1(pos, OpStoreReg, loc.(LocalSlot).Type, x)
}
} else {
// Emit move from src to dst.
_, srcReg := src.(*Register)
if srcReg {
if dstReg {
x = e.p.NewValue1(pos, OpCopy, c.Type, c)
} else {
x = e.p.NewValue1(pos, OpStoreReg, loc.(LocalSlot).Type, c)
}
} else {
if dstReg {
x = e.p.NewValue1(pos, OpLoadReg, c.Type, c)
} else {
// mem->mem. Use temp register.
r := e.findRegFor(c.Type)
e.erase(r)
t := e.p.NewValue1(pos, OpLoadReg, c.Type, c)
e.set(r, vid, t, false, pos)
x = e.p.NewValue1(pos, OpStoreReg, loc.(LocalSlot).Type, t)
}
}
}
e.set(loc, vid, x, true, pos)
if splice != nil {
(*splice).Uses--
*splice = x
x.Uses++
}
return true
}
// set changes the contents of location loc to hold the given value and its cached representative.
func (e *edgeState) set(loc Location, vid ID, c *Value, final bool, pos src.XPos) {
e.s.f.setHome(c, loc)
e.contents[loc] = contentRecord{vid, c, final, pos}
a := e.cache[vid]
if len(a) == 0 {
e.cachedVals = append(e.cachedVals, vid)
}
a = append(a, c)
e.cache[vid] = a
if r, ok := loc.(*Register); ok {
e.usedRegs |= regMask(1) << uint(r.num)
if final {
e.finalRegs |= regMask(1) << uint(r.num)
}
if len(a) == 1 {
e.uniqueRegs |= regMask(1) << uint(r.num)
}
if len(a) == 2 {
if t, ok := e.s.f.getHome(a[0].ID).(*Register); ok {
e.uniqueRegs &^= regMask(1) << uint(t.num)
}
}
}
if e.s.f.pass.debug > regDebug {
fmt.Printf("%s\n", c.LongString())
fmt.Printf("v%d now available in %s:%s\n", vid, loc, c)
}
}
// erase removes any user of loc.
func (e *edgeState) erase(loc Location) {
cr := e.contents[loc]
if cr.c == nil {
return
}
vid := cr.vid
if cr.final {
// Add a destination to move this value back into place.
// Make sure it gets added to the tail of the destination queue
// so we make progress on other moves first.
e.extra = append(e.extra, dstRecord{loc, cr.vid, nil, cr.pos})
}
// Remove c from the list of cached values.
a := e.cache[vid]
for i, c := range a {
if e.s.f.getHome(c.ID) == loc {
if e.s.f.pass.debug > regDebug {
fmt.Printf("v%d no longer available in %s:%s\n", vid, loc, c)
}
a[i], a = a[len(a)-1], a[:len(a)-1]
if e.s.f.Config.ctxt.Flag_locationlists {
if _, isReg := loc.(*Register); isReg && int(c.ID) < len(e.s.valueNames) && len(e.s.valueNames[c.ID]) != 0 {
kill := e.p.NewValue0(src.NoXPos, OpRegKill, types.TypeVoid)
e.s.f.setHome(kill, loc)
for _, name := range e.s.valueNames[c.ID] {
e.s.f.NamedValues[name] = append(e.s.f.NamedValues[name], kill)
}
}
}
break
}
}
e.cache[vid] = a
// Update register masks.
if r, ok := loc.(*Register); ok {
e.usedRegs &^= regMask(1) << uint(r.num)
if cr.final {
e.finalRegs &^= regMask(1) << uint(r.num)
}
}
if len(a) == 1 {
if r, ok := e.s.f.getHome(a[0].ID).(*Register); ok {
e.uniqueRegs |= regMask(1) << uint(r.num)
}
}
}
// findRegFor finds a register we can use to make a temp copy of type typ.
func (e *edgeState) findRegFor(typ *types.Type) Location {
// Which registers are possibilities.
var m regMask
types := &e.s.f.Config.Types
if typ.IsFloat() {
m = e.s.compatRegs(types.Float64)
} else {
m = e.s.compatRegs(types.Int64)
}
// Pick a register. In priority order:
// 1) an unused register
// 2) a non-unique register not holding a final value
// 3) a non-unique register
// 4) TODO: a register holding a rematerializeable value
x := m &^ e.usedRegs
if x != 0 {
return &e.s.registers[pickReg(x)]
}
x = m &^ e.uniqueRegs &^ e.finalRegs
if x != 0 {
return &e.s.registers[pickReg(x)]
}
x = m &^ e.uniqueRegs
if x != 0 {
return &e.s.registers[pickReg(x)]
}
// No register is available.
// Pick a register to spill.
for _, vid := range e.cachedVals {
a := e.cache[vid]
for _, c := range a {
if r, ok := e.s.f.getHome(c.ID).(*Register); ok && m>>uint(r.num)&1 != 0 {
if !c.rematerializeable() {
x := e.p.NewValue1(c.Pos, OpStoreReg, c.Type, c)
// Allocate a temp location to spill a register to.
// The type of the slot is immaterial - it will not be live across
// any safepoint. Just use a type big enough to hold any register.
t := LocalSlot{N: e.s.f.fe.Auto(c.Pos, types.Int64), Type: types.Int64}
// TODO: reuse these slots. They'll need to be erased first.
e.set(t, vid, x, false, c.Pos)
if e.s.f.pass.debug > regDebug {
fmt.Printf(" SPILL %s->%s %s\n", r, t, x.LongString())
}
}
// r will now be overwritten by the caller. At some point
// later, the newly saved value will be moved back to its
// final destination in processDest.
return r
}
}
}
fmt.Printf("m:%d unique:%d final:%d\n", m, e.uniqueRegs, e.finalRegs)
for _, vid := range e.cachedVals {
a := e.cache[vid]
for _, c := range a {
fmt.Printf("v%d: %s %s\n", vid, c, e.s.f.getHome(c.ID))
}
}
e.s.f.Fatalf("can't find empty register on edge %s->%s", e.p, e.b)
return nil
}
// rematerializeable reports whether the register allocator should recompute
// a value instead of spilling/restoring it.
func (v *Value) rematerializeable() bool {
if !opcodeTable[v.Op].rematerializeable {
return false
}
for _, a := range v.Args {
// SP and SB (generated by OpSP and OpSB) are always available.
if a.Op != OpSP && a.Op != OpSB {
return false
}
}
return true
}
type liveInfo struct {
ID ID // ID of value
dist int32 // # of instructions before next use
pos src.XPos // source position of next use
}
// computeLive computes a map from block ID to a list of value IDs live at the end
// of that block. Together with the value ID is a count of how many instructions
// to the next use of that value. The resulting map is stored in s.live.
// computeLive also computes the desired register information at the end of each block.
// This desired register information is stored in s.desired.
// TODO: this could be quadratic if lots of variables are live across lots of
// basic blocks. Figure out a way to make this function (or, more precisely, the user
// of this function) require only linear size & time.
func (s *regAllocState) computeLive() {
f := s.f
s.live = make([][]liveInfo, f.NumBlocks())
s.desired = make([]desiredState, f.NumBlocks())
var phis []*Value
live := newSparseMap(f.NumValues())
t := newSparseMap(f.NumValues())
// Keep track of which value we want in each register.
var desired desiredState
// Instead of iterating over f.Blocks, iterate over their postordering.
// Liveness information flows backward, so starting at the end
// increases the probability that we will stabilize quickly.
// TODO: Do a better job yet. Here's one possibility:
// Calculate the dominator tree and locate all strongly connected components.
// If a value is live in one block of an SCC, it is live in all.
// Walk the dominator tree from end to beginning, just once, treating SCC
// components as single blocks, duplicated calculated liveness information
// out to all of them.
po := f.postorder()
s.loopnest = f.loopnest()
s.loopnest.calculateDepths()
for {
changed := false
for _, b := range po {
// Start with known live values at the end of the block.
// Add len(b.Values) to adjust from end-of-block distance
// to beginning-of-block distance.
live.clear()
for _, e := range s.live[b.ID] {
live.set(e.ID, e.dist+int32(len(b.Values)), e.pos)
}
// Mark control value as live
if b.Control != nil && s.values[b.Control.ID].needReg {
live.set(b.Control.ID, int32(len(b.Values)), b.Pos)
}
// Propagate backwards to the start of the block
// Assumes Values have been scheduled.
phis = phis[:0]
for i := len(b.Values) - 1; i >= 0; i-- {
v := b.Values[i]
live.remove(v.ID)
if v.Op == OpPhi {
// save phi ops for later
phis = append(phis, v)
continue
}
if opcodeTable[v.Op].call {
c := live.contents()
for i := range c {
c[i].val += unlikelyDistance
}
}
for _, a := range v.Args {
if s.values[a.ID].needReg {
live.set(a.ID, int32(i), v.Pos)
}
}
}
// Propagate desired registers backwards.
desired.copy(&s.desired[b.ID])
for i := len(b.Values) - 1; i >= 0; i-- {
v := b.Values[i]
prefs := desired.remove(v.ID)
if v.Op == OpPhi {
// TODO: if v is a phi, save desired register for phi inputs.
// For now, we just drop it and don't propagate
// desired registers back though phi nodes.
continue
}
// Cancel desired registers if they get clobbered.
desired.clobber(opcodeTable[v.Op].reg.clobbers)
// Update desired registers if there are any fixed register inputs.
for _, j := range opcodeTable[v.Op].reg.inputs {
if countRegs(j.regs) != 1 {
continue
}
desired.clobber(j.regs)
desired.add(v.Args[j.idx].ID, pickReg(j.regs))
}
// Set desired register of input 0 if this is a 2-operand instruction.
if opcodeTable[v.Op].resultInArg0 {
if opcodeTable[v.Op].commutative {
desired.addList(v.Args[1].ID, prefs)
}
desired.addList(v.Args[0].ID, prefs)
}
}
// For each predecessor of b, expand its list of live-at-end values.
// invariant: live contains the values live at the start of b (excluding phi inputs)
for i, e := range b.Preds {
p := e.b
// Compute additional distance for the edge.
// Note: delta must be at least 1 to distinguish the control
// value use from the first user in a successor block.
delta := int32(normalDistance)
if len(p.Succs) == 2 {
if p.Succs[0].b == b && p.Likely == BranchLikely ||
p.Succs[1].b == b && p.Likely == BranchUnlikely {
delta = likelyDistance
}
if p.Succs[0].b == b && p.Likely == BranchUnlikely ||
p.Succs[1].b == b && p.Likely == BranchLikely {
delta = unlikelyDistance
}
}
// Update any desired registers at the end of p.
s.desired[p.ID].merge(&desired)
// Start t off with the previously known live values at the end of p.
t.clear()
for _, e := range s.live[p.ID] {
t.set(e.ID, e.dist, e.pos)
}
update := false
// Add new live values from scanning this block.
for _, e := range live.contents() {
d := e.val + delta
if !t.contains(e.key) || d < t.get(e.key) {
update = true
t.set(e.key, d, e.aux)
}
}
// Also add the correct arg from the saved phi values.
// All phis are at distance delta (we consider them
// simultaneously happening at the start of the block).
for _, v := range phis {
id := v.Args[i].ID
if s.values[id].needReg && (!t.contains(id) || delta < t.get(id)) {
update = true
t.set(id, delta, v.Pos)
}
}
if !update {
continue
}
// The live set has changed, update it.
l := s.live[p.ID][:0]
if cap(l) < t.size() {
l = make([]liveInfo, 0, t.size())
}
for _, e := range t.contents() {
l = append(l, liveInfo{e.key, e.val, e.aux})
}
s.live[p.ID] = l
changed = true
}
}
if !changed {
break
}
}
if f.pass.debug > regDebug {
fmt.Println("live values at end of each block")
for _, b := range f.Blocks {
fmt.Printf(" %s:", b)
for _, x := range s.live[b.ID] {
fmt.Printf(" v%d", x.ID)
for _, e := range s.desired[b.ID].entries {
if e.ID != x.ID {
continue
}
fmt.Printf("[")
first := true
for _, r := range e.regs {
if r == noRegister {
continue
}
if !first {
fmt.Printf(",")
}
fmt.Print(&s.registers[r])
first = false
}
fmt.Printf("]")
}
}
fmt.Printf(" avoid=%x", int64(s.desired[b.ID].avoid))
fmt.Println()
}
}
}
// A desiredState represents desired register assignments.
type desiredState struct {
// Desired assignments will be small, so we just use a list
// of valueID+registers entries.
entries []desiredStateEntry
// Registers that other values want to be in. This value will
// contain at least the union of the regs fields of entries, but
// may contain additional entries for values that were once in
// this data structure but are no longer.
avoid regMask
}
type desiredStateEntry struct {
// (pre-regalloc) value
ID ID
// Registers it would like to be in, in priority order.
// Unused slots are filled with noRegister.
regs [4]register
}
func (d *desiredState) clear() {
d.entries = d.entries[:0]
d.avoid = 0
}
// get returns a list of desired registers for value vid.
func (d *desiredState) get(vid ID) [4]register {
for _, e := range d.entries {
if e.ID == vid {
return e.regs
}
}
return [4]register{noRegister, noRegister, noRegister, noRegister}
}
// add records that we'd like value vid to be in register r.
func (d *desiredState) add(vid ID, r register) {
d.avoid |= regMask(1) << r
for i := range d.entries {
e := &d.entries[i]
if e.ID != vid {
continue
}
if e.regs[0] == r {
// Already known and highest priority
return
}
for j := 1; j < len(e.regs); j++ {
if e.regs[j] == r {
// Move from lower priority to top priority
copy(e.regs[1:], e.regs[:j])
e.regs[0] = r
return
}
}
copy(e.regs[1:], e.regs[:])
e.regs[0] = r
return
}
d.entries = append(d.entries, desiredStateEntry{vid, [4]register{r, noRegister, noRegister, noRegister}})
}
func (d *desiredState) addList(vid ID, regs [4]register) {
// regs is in priority order, so iterate in reverse order.
for i := len(regs) - 1; i >= 0; i-- {
r := regs[i]
if r != noRegister {
d.add(vid, r)
}
}
}
// clobber erases any desired registers in the set m.
func (d *desiredState) clobber(m regMask) {
for i := 0; i < len(d.entries); {
e := &d.entries[i]
j := 0
for _, r := range e.regs {
if r != noRegister && m>>r&1 == 0 {
e.regs[j] = r
j++
}
}
if j == 0 {
// No more desired registers for this value.
d.entries[i] = d.entries[len(d.entries)-1]
d.entries = d.entries[:len(d.entries)-1]
continue
}
for ; j < len(e.regs); j++ {
e.regs[j] = noRegister
}
i++
}
d.avoid &^= m
}
// copy copies a desired state from another desiredState x.
func (d *desiredState) copy(x *desiredState) {
d.entries = append(d.entries[:0], x.entries...)
d.avoid = x.avoid
}
// remove removes the desired registers for vid and returns them.
func (d *desiredState) remove(vid ID) [4]register {
for i := range d.entries {
if d.entries[i].ID == vid {
regs := d.entries[i].regs
d.entries[i] = d.entries[len(d.entries)-1]
d.entries = d.entries[:len(d.entries)-1]
return regs
}
}
return [4]register{noRegister, noRegister, noRegister, noRegister}
}
// merge merges another desired state x into d.
func (d *desiredState) merge(x *desiredState) {
d.avoid |= x.avoid
// There should only be a few desired registers, so
// linear insert is ok.
for _, e := range x.entries {
d.addList(e.ID, e.regs)
}
}
func min32(x, y int32) int32 {
if x < y {
return x
}
return y
}
func max32(x, y int32) int32 {
if x > y {
return x
}
return y
}