Adding upstream version 1.16.10.upstream/1.16.10upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 2696 insertions, 0 deletions

diff --git a/src/cmd/compile/internal/ssa/regalloc.go b/src/cmd/compile/internal/ssa/regalloc.go
new file mode 100644
index 0000000..0339b07
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/regalloc.go
@@ -0,0 +1,2696 @@
+// Copyright 2015 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Register allocation.
+//
+// We use a version of a linear scan register allocator. We treat the
+// whole function as a single long basic block and run through
+// it using a greedy register allocator. Then all merge edges
+// (those targeting a block with len(Preds)>1) are processed to
+// shuffle data into the place that the target of the edge expects.
+//
+// The greedy allocator moves values into registers just before they
+// are used, spills registers only when necessary, and spills the
+// value whose next use is farthest in the future.
+//
+// The register allocator requires that a block is not scheduled until
+// at least one of its predecessors have been scheduled. The most recent
+// such predecessor provides the starting register state for a block.
+//
+// It also requires that there are no critical edges (critical =
+// comes from a block with >1 successor and goes to a block with >1
+// predecessor).  This makes it easy to add fixup code on merge edges -
+// the source of a merge edge has only one successor, so we can add
+// fixup code to the end of that block.
+
+// Spilling
+//
+// During the normal course of the allocator, we might throw a still-live
+// value out of all registers. When that value is subsequently used, we must
+// load it from a slot on the stack. We must also issue an instruction to
+// initialize that stack location with a copy of v.
+//
+// pre-regalloc:
+//   (1) v = Op ...
+//   (2) x = Op ...
+//   (3) ... = Op v ...
+//
+// post-regalloc:
+//   (1) v = Op ...    : AX // computes v, store result in AX
+//       s = StoreReg v     // spill v to a stack slot
+//   (2) x = Op ...    : AX // some other op uses AX
+//       c = LoadReg s : CX // restore v from stack slot
+//   (3) ... = Op c ...     // use the restored value
+//
+// Allocation occurs normally until we reach (3) and we realize we have
+// a use of v and it isn't in any register. At that point, we allocate
+// a spill (a StoreReg) for v. We can't determine the correct place for
+// the spill at this point, so we allocate the spill as blockless initially.
+// The restore is then generated to load v back into a register so it can
+// be used. Subsequent uses of v will use the restored value c instead.
+//
+// What remains is the question of where to schedule the spill.
+// During allocation, we keep track of the dominator of all restores of v.
+// The spill of v must dominate that block. The spill must also be issued at
+// a point where v is still in a register.
+//
+// To find the right place, start at b, the block which dominates all restores.
+//  - If b is v.Block, then issue the spill right after v.
+//    It is known to be in a register at that point, and dominates any restores.
+//  - Otherwise, if v is in a register at the start of b,
+//    put the spill of v at the start of b.
+//  - Otherwise, set b = immediate dominator of b, and repeat.
+//
+// Phi values are special, as always. We define two kinds of phis, those
+// where the merge happens in a register (a "register" phi) and those where
+// the merge happens in a stack location (a "stack" phi).
+//
+// A register phi must have the phi and all of its inputs allocated to the
+// same register. Register phis are spilled similarly to regular ops.
+//
+// A stack phi must have the phi and all of its inputs allocated to the same
+// stack location. Stack phis start out life already spilled - each phi
+// input must be a store (using StoreReg) at the end of the corresponding
+// predecessor block.
+//     b1: y = ... : AX        b2: z = ... : BX
+//         y2 = StoreReg y         z2 = StoreReg z
+//         goto b3                 goto b3
+//     b3: x = phi(y2, z2)
+// The stack allocator knows that StoreReg args of stack-allocated phis
+// must be allocated to the same stack slot as the phi that uses them.
+// x is now a spilled value and a restore must appear before its first use.
+
+// TODO
+
+// Use an affinity graph to mark two values which should use the
+// same register. This affinity graph will be used to prefer certain
+// registers for allocation. This affinity helps eliminate moves that
+// are required for phi implementations and helps generate allocations
+// for 2-register architectures.
+
+// Note: regalloc generates a not-quite-SSA output. If we have:
+//
+//             b1: x = ... : AX
+//                 x2 = StoreReg x
+//                 ... AX gets reused for something else ...
+//                 if ... goto b3 else b4
+//
+//   b3: x3 = LoadReg x2 : BX       b4: x4 = LoadReg x2 : CX
+//       ... use x3 ...                 ... use x4 ...
+//
+//             b2: ... use x3 ...
+//
+// If b3 is the primary predecessor of b2, then we use x3 in b2 and
+// add a x4:CX->BX copy at the end of b4.
+// But the definition of x3 doesn't dominate b2.  We should really
+// insert a dummy phi at the start of b2 (x5=phi(x3,x4):BX) to keep
+// SSA form. For now, we ignore this problem as remaining in strict
+// SSA form isn't needed after regalloc. We'll just leave the use
+// of x3 not dominated by the definition of x3, and the CX->BX copy
+// will have no use (so don't run deadcode after regalloc!).
+// TODO: maybe we should introduce these extra phis?
+
+package ssa
+
+import (
+	"cmd/compile/internal/types"
+	"cmd/internal/objabi"
+	"cmd/internal/src"
+	"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
+
+// 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
+
+	// for each block, its primary predecessor.
+	// A predecessor of b is primary if it is the closest
+	// predecessor that appears before b in the layout order.
+	// We record the index in the Preds list where the primary predecessor sits.
+	primary []int32
+
+	// live values at the end of each block.  live[b.ID] is a list of value IDs
+	// which are live at the end of b, together with a count of how many instructions
+	// forward to the next use.
+	live [][]liveInfo
+	// desired register assignments at the end of each block.
+	// Note that this is a static map computed before allocation occurs. Dynamic
+	// register desires (from partially completed allocations) will trump
+	// this information.
+	desired []desiredState
+
+	// current state of each (preregalloc) Value
+	values []valState
+
+	// 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
+}
+
+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))
+	}
+}
+
+// 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.Framepointer_enabled && s.f.Config.FPReg >= 0 {
+		s.allocatable &^= 1 << uint(s.f.Config.FPReg)
+	}
+	if s.f.Config.LinkReg != -1 {
+		if isLeaf(f) {
+			// Leaf functions don't save/restore the link register.
+			s.allocatable &^= 1 << uint(s.f.Config.LinkReg)
+		}
+		if s.f.Config.arch == "arm" && objabi.GOARM == 5 {
+			// On ARMv5 we insert softfloat calls at each FP instruction.
+			// This clobbers LR almost everywhere. Disable allocating LR
+			// on ARMv5.
+			s.allocatable &^= 1 << uint(s.f.Config.LinkReg)
+		}
+	}
+	if s.f.Config.ctxt.Flag_dynlink {
+		switch s.f.Config.arch {
+		case "amd64":
+			s.allocatable &^= 1 << 15 // R15
+		case "arm":
+			s.allocatable &^= 1 << 9 // R9
+		case "ppc64le": // R2 already reserved.
+			// nothing to do
+		case "arm64":
+			// nothing to do?
+		case "386":
+			// nothing to do.
+			// Note that for Flag_shared (position independent code)
+			// we do need to be careful, but that carefulness is hidden
+			// in the rewrite rules so we always have a free register
+			// available for global load/stores. See gen/386.rules (search for Flag_shared).
+		case "s390x":
+			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.
+	blockOrder := make([]int32, f.NumBlocks())
+	for i, b := range s.visitOrder {
+		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()
+
+	// Compute primary predecessors.
+	s.primary = make([]int32, f.NumBlocks())
+	for _, b := range s.visitOrder {
+		best := -1
+		for i, e := range b.Preds {
+			p := e.b
+			if blockOrder[p.ID] >= blockOrder[b.ID] {
+				continue // backward edge
+			}
+			if best == -1 || blockOrder[p.ID] > blockOrder[b.Preds[best].b.ID] {
+				best = i
+			}
+		}
+		s.primary[b.ID] = int32(best)
+	}
+
+	s.endRegs = make([][]endReg, f.NumBlocks())
+	s.startRegs = make([][]startReg, f.NumBlocks())
+	s.spillLive = make([][]ID, f.NumBlocks())
+	s.sdom = f.Sdom()
+
+	// 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)
+					}
+				}
+			}
+		}
+	}
+}
+
+// Adds a use record for id at distance dist from the start of the block.
+// All calls to addUse must happen with nonincreasing dist.
+func (s *regAllocState) addUse(id ID, dist int32, pos src.XPos) {
+	r := s.freeUseRecords
+	if r != nil {
+		s.freeUseRecords = r.next
+	} else {
+		r = &use{}
+	}
+	r.dist = dist
+	r.pos = pos
+	r.next = s.values[id].uses
+	s.values[id].uses = r
+	if r.next != nil && dist > r.next.dist {
+		s.f.Fatalf("uses added in wrong order")
+	}
+}
+
+// advanceUses advances the uses of v's args from the state before v to the state after v.
+// Any values which have no more uses are deallocated from registers.
+func (s *regAllocState) advanceUses(v *Value) {
+	for _, a := range v.Args {
+		if !s.values[a.ID].needReg {
+			continue
+		}
+		ai := &s.values[a.ID]
+		r := ai.uses
+		ai.uses = r.next
+		if r.next == nil {
+			// Value is dead, free all registers that hold it.
+			s.freeRegs(ai.regs)
+		}
+		r.next = s.freeUseRecords
+		s.freeUseRecords = r
+	}
+}
+
+// liveAfterCurrentInstruction reports whether v is live after
+// the current instruction is completed.  v must be used by the
+// current instruction.
+func (s *regAllocState) liveAfterCurrentInstruction(v *Value) bool {
+	u := s.values[v.ID].uses
+	d := u.dist
+	for u != nil && u.dist == d {
+		u = u.next
+	}
+	return u != nil && u.dist > d
+}
+
+// Sets the state of the registers to that encoded in regs.
+func (s *regAllocState) setState(regs []endReg) {
+	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.Etype == types.TFLOAT32 && s.f.Config.fp32RegMask != 0 {
+			m = s.f.Config.fp32RegMask
+		} else if t.Etype == 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(op Op) regInfo {
+	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}}}
+	}
+	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 primary predecessor
+			idx := s.primary[b.ID]
+			if idx < 0 {
+				f.Fatalf("block with no primary predecessor %s", b)
+			}
+			p := b.Preds[idx].b
+			s.setState(s.endRegs[p.ID])
+
+			if s.f.pass.debug > regDebug {
+				fmt.Printf("starting merge block %s with end state of %s:\n", b, p)
+				for _, x := range s.endRegs[p.ID] {
+					fmt.Printf("  %s: orig:%s cache:%s\n", &s.registers[x.r], x.v, x.c)
+				}
+			}
+
+			// Decide on registers for phi ops. Use the registers determined
+			// by the primary predecessor if we can.
+			// TODO: pick best of (already processed) predecessors?
+			// Majority vote? Deepest nesting level?
+			phiRegs = phiRegs[:0]
+			var phiUsed regMask
+
+			for _, v := range phis {
+				if !s.values[v.ID].needReg {
+					phiRegs = append(phiRegs, noRegister)
+					continue
+				}
+				a := v.Args[idx]
+				// Some instructions target not-allocatable registers.
+				// They're not suitable for further (phi-function) allocation.
+				m := s.values[a.ID].regs &^ phiUsed & s.allocatable
+				if m != 0 {
+					r := pickReg(m)
+					phiUsed |= regMask(1) << r
+					phiRegs = append(phiRegs, r)
+				} else {
+					phiRegs = append(phiRegs, noRegister)
+				}
+			}
+
+			// Second pass - deallocate 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 int32(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.Op)
+			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.Op)
+			if v.Op == OpPhi {
+				f.Fatalf("phi %s not at start of block", v)
+			}
+			if v.Op == OpSP {
+				s.assignReg(s.SPReg, v, v)
+				b.Values = append(b.Values, v)
+				s.advanceUses(v)
+				s.sp = v.ID
+				continue
+			}
+			if v.Op == OpSB {
+				s.assignReg(s.SBReg, v, v)
+				b.Values = append(b.Values, v)
+				s.advanceUses(v)
+				s.sb = v.ID
+				continue
+			}
+			if v.Op == OpSelect0 || v.Op == OpSelect1 {
+				if s.values[v.ID].needReg {
+					var i = 0
+					if v.Op == OpSelect1 {
+						i = 1
+					}
+					s.assignReg(register(s.f.getHome(v.Args[0].ID).(LocPair)[i].(*Register).num), v, v)
+				}
+				b.Values = append(b.Values, v)
+				s.advanceUses(v)
+				goto issueSpill
+			}
+			if v.Op == OpGetG && s.f.Config.hasGReg {
+				// use hardware g register
+				if s.regs[s.GReg].v != nil {
+					s.freeReg(s.GReg) // kick out the old value
+				}
+				s.assignReg(s.GReg, v, v)
+				b.Values = append(b.Values, v)
+				s.advanceUses(v)
+				goto issueSpill
+			}
+			if v.Op == OpArg {
+				// Args are "pre-spilled" values. We don't allocate
+				// any register here. We just set up the spill pointer to
+				// point at itself and any later user will restore it to use it.
+				s.values[v.ID].spill = v
+				b.Values = append(b.Values, v)
+				s.advanceUses(v)
+				continue
+			}
+			if v.Op == OpKeepAlive {
+				// Make sure the argument to v is still live here.
+				s.advanceUses(v)
+				a := v.Args[0]
+				vi := &s.values[a.ID]
+				if vi.regs == 0 && !vi.rematerializeable {
+					// Use the spill location.
+					// This forces later liveness analysis to make the
+					// value live at this point.
+					v.SetArg(0, s.makeSpill(a, b))
+				} else if _, ok := a.Aux.(GCNode); 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)
+				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
+			s.freeRegs(regspec.clobbers)
+			s.tmpused |= regspec.clobbers
+
+			// Pick registers for outputs.
+			{
+				outRegs := [2]register{noRegister, noRegister}
+				var used regMask
+				for _, out := range regspec.outputs {
+					mask := out.regs & s.allocatable &^ used
+					if mask == 0 {
+						continue
+					}
+					if opcodeTable[v.Op].resultInArg0 && out.idx == 0 {
+						if !opcodeTable[v.Op].commutative {
+							// Output must use the same register as input 0.
+							r := register(s.f.getHome(args[0].ID).(*Register).num)
+							mask = regMask(1) << r
+						} else {
+							// Output must use the same register as input 0 or 1.
+							r0 := register(s.f.getHome(args[0].ID).(*Register).num)
+							r1 := register(s.f.getHome(args[1].ID).(*Register).num)
+							// Check r0 and r1 for desired output register.
+							found := false
+							for _, r := range dinfo[idx].out {
+								if (r == r0 || r == r1) && (mask&^s.used)>>r&1 != 0 {
+									mask = regMask(1) << r
+									found = true
+									if r == r1 {
+										args[0], args[1] = args[1], args[0]
+									}
+									break
+								}
+							}
+							if !found {
+								// Neither are desired, pick r0.
+								mask = regMask(1) << r0
+							}
+						}
+					}
+					for _, r := range dinfo[idx].out {
+						if r != noRegister && (mask&^s.used)>>r&1 != 0 {
+							// Desired register is allowed and unused.
+							mask = regMask(1) << r
+							break
+						}
+					}
+					// Avoid registers we're saving for other values.
+					if mask&^desired.avoid&^s.nospill != 0 {
+						mask &^= desired.avoid
+					}
+					r := s.allocReg(mask, v)
+					outRegs[out.idx] = r
+					used |= regMask(1) << r
+					s.tmpused |= regMask(1) << r
+				}
+				// Record register choices
+				if v.Type.IsTuple() {
+					var outLocs LocPair
+					if r := outRegs[0]; r != noRegister {
+						outLocs[0] = &s.registers[r]
+					}
+					if r := outRegs[1]; r != noRegister {
+						outLocs[1] = &s.registers[r]
+					}
+					s.f.setHome(v, outLocs)
+					// Note that subsequent SelectX instructions will do the assignReg calls.
+				} else {
+					if r := outRegs[0]; r != noRegister {
+						s.assignReg(r, v, v)
+					}
+				}
+			}
+
+			// deallocate dead args, if we have not done so
+			if opcodeTable[v.Op].resultNotInArgs {
+				s.nospill = 0
+				s.advanceUses(v) // frees any registers holding args that are no longer live
+			}
+			s.tmpused = 0
+
+			// Issue the Value itself.
+			for i, a := range args {
+				v.SetArg(i, a) // use register version of arguments
+			}
+			b.Values = append(b.Values, v)
+
+		issueSpill:
+		}
+
+		// 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.
+		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.Op)
+				// 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
+}