[gostls13.git] / src / cmd / compile / internal / ssa / regalloc.go

// 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 an extra 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/base"
        "cmd/compile/internal/ir"
        "cmd/compile/internal/types"
        "cmd/internal/objabi"
        "cmd/internal/src"
        "cmd/internal/sys"
        "fmt"
        "math/bits"
        "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

// For bulk initializing
var noRegisters [32]register = [32]register{
        noRegister, noRegister, noRegister, noRegister, noRegister, noRegister, noRegister, noRegister,
        noRegister, noRegister, noRegister, noRegister, noRegister, noRegister, noRegister, noRegister,
        noRegister, noRegister, noRegister, noRegister, noRegister, noRegister, noRegister, noRegister,
        noRegister, noRegister, noRegister, noRegister, noRegister, noRegister, noRegister, noRegister,
}

// A regMask encodes a set of machine registers.
// TODO: regMask -> regSet?
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
}

func (s *regAllocState) RegMaskString(m regMask) string {
        str := ""
        for r := register(0); m != 0; r++ {
                if m>>r&1 == 0 {
                        continue
                }
                m &^= regMask(1) << r
                if str != "" {
                        str += " "
                }
                str += s.registers[r].String()
        }
        return str
}

// countRegs returns the number of set bits in the register mask.
func countRegs(r regMask) int {
        return bits.OnesCount64(uint64(r))
}

// pickReg picks an arbitrary register from the register mask.
func pickReg(r regMask) register {
        if r == 0 {
                panic("can't pick a register from an empty set")
        }
        // pick the lowest one
        return register(bits.TrailingZeros64(uint64(r)))
}

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

        // 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

        // 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

        // choose a good order in which to visit blocks for allocation purposes.
        visitOrder []*Block

        // blockOrder[b.ID] corresponds to the index of block b in visitOrder.
        blockOrder []int32

        // whether to insert instructions that clobber dead registers at call sites
        doClobber bool
}

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) {
        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)
        }
        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))
        }
}

// clobberRegs inserts instructions that clobber registers listed in m.
func (s *regAllocState) clobberRegs(m regMask) {
        m &= s.allocatable & s.f.Config.gpRegMask // only integer register can contain pointers, only clobber them
        for m != 0 {
                r := pickReg(m)
                m &^= 1 << r
                x := s.curBlock.NewValue0(src.NoXPos, OpClobberReg, types.TypeVoid)
                s.f.setHome(x, &s.registers[r])
        }
}

// 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 {
        if v.OnWasmStack {
                return noRegister
        }

        mask &= s.allocatable
        mask &^= s.nospill
        if mask == 0 {
                s.f.Fatalf("no register available for %s", v.LongString())
        }

        // 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")
        }

        if s.f.Config.ctxt.Arch.Arch == sys.ArchWasm {
                // TODO(neelance): In theory this should never happen, because all wasm registers are equal.
                // So if there is still a free register, the allocation should have picked that one in the first place instead of
                // trying to kick some other value out. In practice, this case does happen and it breaks the stack optimization.
                s.freeReg(r)
                return r
        }

        // 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 {
        if s.f.Config.ctxt.Arch.Arch == sys.ArchWasm && v.rematerializeable() {
                c := v.copyIntoWithXPos(s.curBlock, pos)
                c.OnWasmStack = true
                s.setOrig(c, v)
                return c
        }
        if v.OnWasmStack {
                return v
        }

        vi := &s.values[v.ID]
        pos = pos.WithNotStmt()
        // 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
        }

        var r register
        // If nospill is set, the value is used immediately, so it can live on the WebAssembly stack.
        onWasmStack := nospill && s.f.Config.ctxt.Arch.Arch == sys.ArchWasm
        if !onWasmStack {
                // 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)

        if onWasmStack {
                c.OnWasmStack = true
                return c
        }

        s.assignReg(r, v, c)
        if c.Op == OpLoadReg && s.isGReg(r) {
                s.f.Fatalf("allocValToReg.OpLoadReg targeting g: " + c.LongString())
        }
        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 objabi.FramePointerEnabled && 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.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":
                        s.allocatable &^= 1 << 11 // R11
                default:
                        s.f.fe.Fatalf(src.NoXPos, "arch %s not implemented", s.f.Config.arch)
                }
        }

        // Linear scan register allocation can be influenced by the order in which blocks appear.
        // Decouple the register allocation order from the generated block order.
        // This also creates an opportunity for experiments to find a better order.
        s.visitOrder = layoutRegallocOrder(f)

        // Compute block order. This array allows us to distinguish forward edges
        // from backward edges and compute how far they go.
        s.blockOrder = make([]int32, f.NumBlocks())
        for i, b := range s.visitOrder {
                s.blockOrder[b.ID] = int32(i)
        }

        s.regs = make([]regState, s.numRegs)
        nv := f.NumValues()
        if cap(s.f.Cache.regallocValues) >= nv {
                s.f.Cache.regallocValues = s.f.Cache.regallocValues[:nv]
        } else {
                s.f.Cache.regallocValues = make([]valState, nv)
        }
        s.values = s.f.Cache.regallocValues
        s.orig = make([]*Value, nv)
        s.copies = make(map[*Value]bool)
        for _, b := range s.visitOrder {
                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()

        s.endRegs = make([][]endReg, f.NumBlocks())
        s.startRegs = make([][]startReg, f.NumBlocks())
        s.spillLive = make([][]ID, f.NumBlocks())
        s.sdom = f.Sdom()

        // wasm: Mark instructions that can be optimized to have their values only on the WebAssembly stack.
        if f.Config.ctxt.Arch.Arch == sys.ArchWasm {
                canLiveOnStack := f.newSparseSet(f.NumValues())
                defer f.retSparseSet(canLiveOnStack)
                for _, b := range f.Blocks {
                        // New block. Clear candidate set.
                        canLiveOnStack.clear()
                        for _, c := range b.ControlValues() {
                                if c.Uses == 1 && !opcodeTable[c.Op].generic {
                                        canLiveOnStack.add(c.ID)
                                }
                        }
                        // Walking backwards.
                        for i := len(b.Values) - 1; i >= 0; i-- {
                                v := b.Values[i]
                                if canLiveOnStack.contains(v.ID) {
                                        v.OnWasmStack = true
                                } else {
                                        // Value can not live on stack. Values are not allowed to be reordered, so clear candidate set.
                                        canLiveOnStack.clear()
                                }
                                for _, arg := range v.Args {
                                        // Value can live on the stack if:
                                        // - it is only used once
                                        // - it is used in the same basic block
                                        // - it is not a "mem" value
                                        // - it is a WebAssembly op
                                        if arg.Uses == 1 && arg.Block == v.Block && !arg.Type.IsMemory() && !opcodeTable[arg.Op].generic {
                                                canLiveOnStack.add(arg.ID)
                                        }
                                }
                        }
                }
        }

        // The clobberdeadreg experiment inserts code to clobber dead registers
        // at call sites.
        // Ignore huge functions to avoid doing too much work.
        if base.Flag.ClobberDeadReg && len(s.f.Blocks) <= 10000 {
                // TODO: honor GOCLOBBERDEADHASH, or maybe GOSSAHASH.
                s.doClobber = true
        }
}

// 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
        if u == nil {
                panic(fmt.Errorf("u is nil, v = %s, s.values[v.ID] = %v", v.LongString(), s.values[v.ID]))
        }
        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) {
        s.freeRegs(s.used)
        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 {
                if t.Kind() == types.TFLOAT32 && s.f.Config.fp32RegMask != 0 {
                        m = s.f.Config.fp32RegMask
                } else if t.Kind() == types.TFLOAT64 && s.f.Config.fp64RegMask != 0 {
                        m = s.f.Config.fp64RegMask
                } else {
                        m = s.f.Config.fpRegMask
                }
        } else {
                m = s.f.Config.gpRegMask
        }
        return m & s.allocatable
}

// regspec returns the regInfo for operation op.
func (s *regAllocState) regspec(v *Value) regInfo {
        op := v.Op
        if op == OpConvert {
                // OpConvert is a generic op, so it doesn't have a
                // register set in the static table. It can use any
                // allocatable integer register.
                m := s.allocatable & s.f.Config.gpRegMask
                return regInfo{inputs: []inputInfo{{regs: m}}, outputs: []outputInfo{{regs: m}}}
        }
        if op == OpArgIntReg {
                reg := v.Block.Func.Config.intParamRegs[v.AuxInt8()]
                return regInfo{outputs: []outputInfo{{regs: 1 << uint(reg)}}}
        }
        if op == OpArgFloatReg {
                reg := v.Block.Func.Config.floatParamRegs[v.AuxInt8()]
                return regInfo{outputs: []outputInfo{{regs: 1 << uint(reg)}}}
        }
        if op.IsCall() {
                if ac, ok := v.Aux.(*AuxCall); ok && ac.reg != nil {
                        return *ac.Reg(&opcodeTable[op].reg, s.f.Config)
                }
        }
        if op == OpMakeResult && s.f.OwnAux.reg != nil {
                return *s.f.OwnAux.ResultReg(s.f.Config)
        }
        return opcodeTable[op].reg
}

func (s *regAllocState) isGReg(r register) bool {
        return s.f.Config.hasGReg && s.GReg == r
}

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 s.visitOrder {
                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)
                }
                for _, v := range b.ControlValues() {
                        if s.values[v.ID].needReg {
                                s.addUse(v.ID, int32(len(b.Values)), b.Pos) // pseudo-use by control values
                                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("use distances for %s\n", 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 predecessor with least spill values.
                        // This is based on the following points:
                        // 1, The less spill value indicates that the register pressure of this path is smaller,
                        //    so the values of this block are more likely to be allocated to registers.
                        // 2, Avoid the predecessor that contains the function call, because the predecessor that
                        //    contains the function call usually generates a lot of spills and lose the previous
                        //    allocation state.
                        // TODO: Improve this part. At least the size of endRegs of the predecessor also has
                        // an impact on the code size and compiler speed. But it is not easy to find a simple
                        // and efficient method that combines multiple factors.
                        idx := -1
                        for i, p := range b.Preds {
                                // If the predecessor has not been visited yet, skip it because its end state
                                // (redRegs and spillLive) has not been computed yet.
                                pb := p.b
                                if s.blockOrder[pb.ID] >= s.blockOrder[b.ID] {
                                        continue
                                }
                                if idx == -1 {
                                        idx = i
                                        continue
                                }
                                pSel := b.Preds[idx].b
                                if len(s.spillLive[pb.ID]) < len(s.spillLive[pSel.ID]) {
                                        idx = i
                                } else if len(s.spillLive[pb.ID]) == len(s.spillLive[pSel.ID]) {
                                        // Use a bit of likely information. After critical pass, pb and pSel must
                                        // be plain blocks, so check edge pb->pb.Preds instead of edge pb->b.
                                        // TODO: improve the prediction of the likely predecessor. The following
                                        // method is only suitable for the simplest cases. For complex cases,
                                        // the prediction may be inaccurate, but this does not affect the
                                        // correctness of the program.
                                        // According to the layout algorithm, the predecessor with the
                                        // smaller blockOrder is the true branch, and the test results show
                                        // that it is better to choose the predecessor with a smaller
                                        // blockOrder than no choice.
                                        if pb.likelyBranch() && !pSel.likelyBranch() || s.blockOrder[pb.ID] < s.blockOrder[pSel.ID] {
                                                idx = i
                                        }
                                }
                        }
                        if idx < 0 {
                                f.Fatalf("bad visitOrder, no predecessor of %s has been visited before it", 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 all in-register phi inputs.
                        for i, v := range phis {
                                if !s.values[v.ID].needReg {
                                        continue
                                }
                                a := v.Args[idx]
                                r := phiRegs[i]
                                if r == noRegister {
                                        continue
                                }
                                if regValLiveSet.contains(a.ID) {
                                        // Input value is still live (it is used by something other than Phi).
                                        // 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 later if never used.
                                        //
                                        // 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 input
                        // was not in a register in the primary predecessor.
                        for i, v := range phis {
                                if !s.values[v.ID].needReg {
                                        continue
                                }
                                if phiRegs[i] != noRegister {
                                        continue
                                }
                                m := s.compatRegs(v.Type) &^ phiUsed &^ s.used
                                // If one of the other inputs of v is in a register, and the register is available,
                                // select this register, which can save some unnecessary copies.
                                for i, pe := range b.Preds {
                                        if i == idx {
                                                continue
                                        }
                                        ri := noRegister
                                        for _, er := range s.endRegs[pe.b.ID] {
                                                if er.v == s.orig[v.Args[i].ID] {
                                                        ri = er.r
                                                        break
                                                }
                                        }
                                        if ri != noRegister && m>>ri&1 != 0 {
                                                m = regMask(1) << ri
                                                break
                                        }
                                }
                                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.
                        // We append to a stack allocated variable that we'll
                        // later copy into s.startRegs in one fell swoop, to save
                        // on allocations.
                        regList := make([]startReg, 0, 32)
                        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] = make([]startReg, len(regList))
                        copy(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.
                if l := len(oldSched); cap(dinfo) < l {
                        dinfo = make([]dentry, l)
                } else {
                        dinfo = dinfo[:l]
                        for i := range dinfo {
                                dinfo[i] = 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 {
                                        break
                                }
                                if !s.values[v.ID].needReg {
                                        continue
                                }
                                rp, ok := s.f.getHome(v.ID).(*Register)
                                if !ok {
                                        // If v is not assigned a register, pick a register assigned to one of v's inputs.
                                        // Hopefully v will get assigned that register later.
                                        // If the inputs have allocated register information, add it to desired,
                                        // which may reduce spill or copy operations when the register is available.
                                        for _, a := range v.Args {
                                                rp, ok = s.f.getHome(a.ID).(*Register)
                                                if ok {
                                                        break
                                                }
                                        }
                                        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)
                        regspec := s.regspec(v)
                        desired.clobber(regspec.clobbers)
                        for _, j := range regspec.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 := s.regspec(v)
                        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 || v.Op == OpSelectN {
                                if s.values[v.ID].needReg {
                                        if v.Op == OpSelectN {
                                                s.assignReg(register(s.f.getHome(v.Args[0].ID).(LocResults)[int(v.AuxInt)].(*Register).num), v, v)
                                        } else {
                                                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 if _, ok := a.Aux.(*ir.Name); ok && vi.rematerializeable {
                                        // Rematerializeable value with a gc.Node. This is the address of
                                        // a stack object (e.g. an LEAQ). Keep the object live.
                                        // Change it to VarLive, which is what plive expects for locals.
                                        v.Op = OpVarLive
                                        v.SetArgs1(v.Args[1])
                                        v.Aux = a.Aux
                                } 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)
                                if s.doClobber && v.Op.IsCall() {
                                        s.clobberRegs(regspec.clobbers)
                                }
                                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 opcodeTable[v.Op].commutative && !s.liveAfterCurrentInstruction(v.Args[1]) {
                                        args[0], args[1] = args[1], args[0]
                                        goto ok
                                }
                                if s.values[v.Args[0].ID].rematerializeable {
                                        // We can rematerialize the input, don't worry about clobbering it.
                                        goto ok
                                }
                                if opcodeTable[v.Op].commutative && s.values[v.Args[1].ID].rematerializeable {
                                        args[0], args[1] = args[1], args[0]
                                        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 && 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
                        if s.doClobber && v.Op.IsCall() {
                                // clobber registers that are marked as clobber in regmask, but
                                // don't clobber inputs.
                                s.clobberRegs(regspec.clobbers &^ s.tmpused &^ s.nospill)
                        }
                        s.freeRegs(regspec.clobbers)
                        s.tmpused |= regspec.clobbers

                        // Pick registers for outputs.
                        {
                                outRegs := noRegisters // TODO if this is costly, hoist and clear incrementally below.
                                maxOutIdx := -1
                                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&^s.nospill != 0 {
                                                mask &^= desired.avoid
                                        }
                                        r := s.allocReg(mask, v)
                                        if out.idx > maxOutIdx {
                                                maxOutIdx = out.idx
                                        }
                                        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 v.Type.IsResults() {
                                        // preallocate outLocs to the right size, which is maxOutIdx+1
                                        outLocs := make(LocResults, maxOutIdx+1, maxOutIdx+1)
                                        for i := 0; i <= maxOutIdx; i++ {
                                                if r := outRegs[i]; r != noRegister {
                                                        outLocs[i] = &s.registers[r]
                                                }
                                        }
                                        s.f.setHome(v, outLocs)
                                } 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:
                }

                // Copy the control values - we need this so we can reduce the
                // uses property of these values later.
                controls := append(make([]*Value, 0, 2), b.ControlValues()...)

                // Load control values into registers.
                for i, v := range b.ControlValues() {
                        if !s.values[v.ID].needReg {
                                continue
                        }
                        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.ReplaceControl(i, s.allocValToReg(v, s.compatRegs(v.Type), false, b.Pos))
                }

                // Reduce the uses of the control values once registers have been loaded.
                // This loop is equivalent to the advanceUses method.
                for _, v := range controls {
                        vi := &s.values[v.ID]
                        if !vi.needReg {
                                continue
                        }
                        // Remove this use from the uses list.
                        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
                }

                // 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 {
                        if s.f.Config.hasGReg && s.regs[s.GReg].v != nil {
                                s.freeReg(s.GReg) // Spill value in G register before any merge.
                        }
                        // 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.containsUnavoidableCall {
                                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]
                                m := s.compatRegs(v.Type) &^ s.used
                                // Used desired register if available.
                        outerloop:
                                for _, e := range desired.entries {
                                        if e.ID != v.ID {
                                                continue
                                        }
                                        for _, r := range e.regs {
                                                if r != noRegister && m>>r&1 != 0 {
                                                        m = regMask(1) << r
                                                        break outerloop
                                                }
                                        }
                                }
                                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
                        }
                        if s.f.pass.debug > regDebug {
                                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 s.visitOrder {
                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 s.visitOrder {
                var m regMask
                for _, v := range b.Values {
                        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.
                if v == nil {
                        panic(fmt.Errorf("nil v, s.orig[%d], vi = %v, spill = %s", i, vi, spill.LongString()))
                }
                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 s.visitOrder {
                nphi := 0
                for _, v := range b.Values {
                        if 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.visitOrder {
                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()
                }
        }

        if s.f.pass.debug > regDebug {
                fmt.Printf("post shuffle %s\n", s.f.Name)
                fmt.Println(s.f.String())
        }
}

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
        rematerializeableRegs regMask // registers that hold rematerializeable values
}

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
        e.rematerializeableRegs = 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 != 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)
                pos := d.pos.WithNotStmt()
                if _, isReg := loc.(*Register); isReg {
                        c = e.p.NewValue1(pos, OpCopy, c.Type, c)
                } else {
                        c = e.p.NewValue1(pos, OpLoadReg, c.Type, c)
                }
                e.set(r, vid, c, false, pos)
                if c.Op == OpLoadReg && e.s.isGReg(register(r.(*Register).num)) {
                        e.s.f.Fatalf("process.OpLoadReg targeting g: " + c.LongString())
                }
        }
}

// 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 {
        pos = pos.WithNotStmt()
        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 || e.s.values[vid].rematerializeable {
                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.copyInto(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 x.Op == OpLoadReg && e.s.isGReg(register(loc.(*Register).num)) {
                e.s.f.Fatalf("processDest.OpLoadReg targeting g: " + x.LongString())
        }
        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 {
                if e.usedRegs&(regMask(1)<<uint(r.num)) != 0 {
                        e.s.f.Fatalf("%v is already set (v%d/%v)", r, vid, c)
                }
                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.values[vid].rematerializeable {
                        e.rematerializeableRegs |= regMask(1) << uint(r.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]
                        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)
                }
                e.rematerializeableRegs &^= 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.
        types := &e.s.f.Config.Types
        m := e.s.compatRegs(typ)

        // 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) 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)]
        }
        x = m & e.rematerializeableRegs
        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 rematerializable:%d\n", m, e.uniqueRegs, e.finalRegs, e.rematerializeableRegs)
        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 := f.newSparseMap(f.NumValues())
        defer f.retSparseMap(live)
        t := f.newSparseMap(f.NumValues())
        defer f.retSparseMap(t)

        // 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 values as live
                        for _, c := range b.ControlValues() {
                                if s.values[c.ID].needReg {
                                        live.set(c.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
                                }
                                regspec := s.regspec(v)
                                // Cancel desired registers if they get clobbered.
                                desired.clobber(regspec.clobbers)
                                // Update desired registers if there are any fixed register inputs.
                                for _, j := range regspec.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(%d)", x.ID, x.dist)
                                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("]")
                                }
                        }
                        if avoid := s.desired[b.ID].avoid; avoid != 0 {
                                fmt.Printf(" avoid=%v", s.RegMaskString(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
}