Source file src/cmd/compile/internal/ssa/regalloc.go

     1  // Copyright 2015 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  // Register allocation.
     6  //
     7  // We use a version of a linear scan register allocator. We treat the
     8  // whole function as a single long basic block and run through
     9  // it using a greedy register allocator. Then all merge edges
    10  // (those targeting a block with len(Preds)>1) are processed to
    11  // shuffle data into the place that the target of the edge expects.
    12  //
    13  // The greedy allocator moves values into registers just before they
    14  // are used, spills registers only when necessary, and spills the
    15  // value whose next use is farthest in the future.
    16  //
    17  // The register allocator requires that a block is not scheduled until
    18  // at least one of its predecessors have been scheduled. The most recent
    19  // such predecessor provides the starting register state for a block.
    20  //
    21  // It also requires that there are no critical edges (critical =
    22  // comes from a block with >1 successor and goes to a block with >1
    23  // predecessor).  This makes it easy to add fixup code on merge edges -
    24  // the source of a merge edge has only one successor, so we can add
    25  // fixup code to the end of that block.
    26  
    27  // Spilling
    28  //
    29  // During the normal course of the allocator, we might throw a still-live
    30  // value out of all registers. When that value is subsequently used, we must
    31  // load it from a slot on the stack. We must also issue an instruction to
    32  // initialize that stack location with a copy of v.
    33  //
    34  // pre-regalloc:
    35  //   (1) v = Op ...
    36  //   (2) x = Op ...
    37  //   (3) ... = Op v ...
    38  //
    39  // post-regalloc:
    40  //   (1) v = Op ...    : AX // computes v, store result in AX
    41  //       s = StoreReg v     // spill v to a stack slot
    42  //   (2) x = Op ...    : AX // some other op uses AX
    43  //       c = LoadReg s : CX // restore v from stack slot
    44  //   (3) ... = Op c ...     // use the restored value
    45  //
    46  // Allocation occurs normally until we reach (3) and we realize we have
    47  // a use of v and it isn't in any register. At that point, we allocate
    48  // a spill (a StoreReg) for v. We can't determine the correct place for
    49  // the spill at this point, so we allocate the spill as blockless initially.
    50  // The restore is then generated to load v back into a register so it can
    51  // be used. Subsequent uses of v will use the restored value c instead.
    52  //
    53  // What remains is the question of where to schedule the spill.
    54  // During allocation, we keep track of the dominator of all restores of v.
    55  // The spill of v must dominate that block. The spill must also be issued at
    56  // a point where v is still in a register.
    57  //
    58  // To find the right place, start at b, the block which dominates all restores.
    59  //  - If b is v.Block, then issue the spill right after v.
    60  //    It is known to be in a register at that point, and dominates any restores.
    61  //  - Otherwise, if v is in a register at the start of b,
    62  //    put the spill of v at the start of b.
    63  //  - Otherwise, set b = immediate dominator of b, and repeat.
    64  //
    65  // Phi values are special, as always. We define two kinds of phis, those
    66  // where the merge happens in a register (a "register" phi) and those where
    67  // the merge happens in a stack location (a "stack" phi).
    68  //
    69  // A register phi must have the phi and all of its inputs allocated to the
    70  // same register. Register phis are spilled similarly to regular ops.
    71  //
    72  // A stack phi must have the phi and all of its inputs allocated to the same
    73  // stack location. Stack phis start out life already spilled - each phi
    74  // input must be a store (using StoreReg) at the end of the corresponding
    75  // predecessor block.
    76  //     b1: y = ... : AX        b2: z = ... : BX
    77  //         y2 = StoreReg y         z2 = StoreReg z
    78  //         goto b3                 goto b3
    79  //     b3: x = phi(y2, z2)
    80  // The stack allocator knows that StoreReg args of stack-allocated phis
    81  // must be allocated to the same stack slot as the phi that uses them.
    82  // x is now a spilled value and a restore must appear before its first use.
    83  
    84  // TODO
    85  
    86  // Use an affinity graph to mark two values which should use the
    87  // same register. This affinity graph will be used to prefer certain
    88  // registers for allocation. This affinity helps eliminate moves that
    89  // are required for phi implementations and helps generate allocations
    90  // for 2-register architectures.
    91  
    92  // Note: regalloc generates a not-quite-SSA output. If we have:
    93  //
    94  //             b1: x = ... : AX
    95  //                 x2 = StoreReg x
    96  //                 ... AX gets reused for something else ...
    97  //                 if ... goto b3 else b4
    98  //
    99  //   b3: x3 = LoadReg x2 : BX       b4: x4 = LoadReg x2 : CX
   100  //       ... use x3 ...                 ... use x4 ...
   101  //
   102  //             b2: ... use x3 ...
   103  //
   104  // If b3 is the primary predecessor of b2, then we use x3 in b2 and
   105  // add a x4:CX->BX copy at the end of b4.
   106  // But the definition of x3 doesn't dominate b2.  We should really
   107  // insert an extra phi at the start of b2 (x5=phi(x3,x4):BX) to keep
   108  // SSA form. For now, we ignore this problem as remaining in strict
   109  // SSA form isn't needed after regalloc. We'll just leave the use
   110  // of x3 not dominated by the definition of x3, and the CX->BX copy
   111  // will have no use (so don't run deadcode after regalloc!).
   112  // TODO: maybe we should introduce these extra phis?
   113  
   114  package ssa
   115  
   116  import (
   117  	"cmd/compile/internal/base"
   118  	"cmd/compile/internal/ir"
   119  	"cmd/compile/internal/types"
   120  	"cmd/internal/src"
   121  	"cmd/internal/sys"
   122  	"fmt"
   123  	"internal/buildcfg"
   124  	"math"
   125  	"math/bits"
   126  	"unsafe"
   127  )
   128  
   129  const (
   130  	moveSpills = iota
   131  	logSpills
   132  	regDebug
   133  	stackDebug
   134  )
   135  
   136  // distance is a measure of how far into the future values are used.
   137  // distance is measured in units of instructions.
   138  const (
   139  	likelyDistance   = 1
   140  	normalDistance   = 10
   141  	unlikelyDistance = 100
   142  )
   143  
   144  // regalloc performs register allocation on f. It sets f.RegAlloc
   145  // to the resulting allocation.
   146  func regalloc(f *Func) {
   147  	var s regAllocState
   148  	s.init(f)
   149  	s.regalloc(f)
   150  	s.close()
   151  }
   152  
   153  type register uint8
   154  
   155  const noRegister register = 255
   156  
   157  // For bulk initializing
   158  var noRegisters [32]register = [32]register{
   159  	noRegister, noRegister, noRegister, noRegister, noRegister, noRegister, noRegister, noRegister,
   160  	noRegister, noRegister, noRegister, noRegister, noRegister, noRegister, noRegister, noRegister,
   161  	noRegister, noRegister, noRegister, noRegister, noRegister, noRegister, noRegister, noRegister,
   162  	noRegister, noRegister, noRegister, noRegister, noRegister, noRegister, noRegister, noRegister,
   163  }
   164  
   165  // A regMask encodes a set of machine registers.
   166  // TODO: regMask -> regSet?
   167  type regMask uint64
   168  
   169  func (m regMask) String() string {
   170  	s := ""
   171  	for r := register(0); m != 0; r++ {
   172  		if m>>r&1 == 0 {
   173  			continue
   174  		}
   175  		m &^= regMask(1) << r
   176  		if s != "" {
   177  			s += " "
   178  		}
   179  		s += fmt.Sprintf("r%d", r)
   180  	}
   181  	return s
   182  }
   183  
   184  func (s *regAllocState) RegMaskString(m regMask) string {
   185  	str := ""
   186  	for r := register(0); m != 0; r++ {
   187  		if m>>r&1 == 0 {
   188  			continue
   189  		}
   190  		m &^= regMask(1) << r
   191  		if str != "" {
   192  			str += " "
   193  		}
   194  		str += s.registers[r].String()
   195  	}
   196  	return str
   197  }
   198  
   199  // countRegs returns the number of set bits in the register mask.
   200  func countRegs(r regMask) int {
   201  	return bits.OnesCount64(uint64(r))
   202  }
   203  
   204  // pickReg picks an arbitrary register from the register mask.
   205  func pickReg(r regMask) register {
   206  	if r == 0 {
   207  		panic("can't pick a register from an empty set")
   208  	}
   209  	// pick the lowest one
   210  	return register(bits.TrailingZeros64(uint64(r)))
   211  }
   212  
   213  type use struct {
   214  	// distance from start of the block to a use of a value
   215  	//   dist == 0                 used by first instruction in block
   216  	//   dist == len(b.Values)-1   used by last instruction in block
   217  	//   dist == len(b.Values)     used by block's control value
   218  	//   dist  > len(b.Values)     used by a subsequent block
   219  	dist int32
   220  	pos  src.XPos // source position of the use
   221  	next *use     // linked list of uses of a value in nondecreasing dist order
   222  }
   223  
   224  // A valState records the register allocation state for a (pre-regalloc) value.
   225  type valState struct {
   226  	regs              regMask // the set of registers holding a Value (usually just one)
   227  	uses              *use    // list of uses in this block
   228  	spill             *Value  // spilled copy of the Value (if any)
   229  	restoreMin        int32   // minimum of all restores' blocks' sdom.entry
   230  	restoreMax        int32   // maximum of all restores' blocks' sdom.exit
   231  	needReg           bool    // cached value of !v.Type.IsMemory() && !v.Type.IsVoid() && !.v.Type.IsFlags()
   232  	rematerializeable bool    // cached value of v.rematerializeable()
   233  }
   234  
   235  type regState struct {
   236  	v *Value // Original (preregalloc) Value stored in this register.
   237  	c *Value // A Value equal to v which is currently in a register.  Might be v or a copy of it.
   238  	// If a register is unused, v==c==nil
   239  }
   240  
   241  type regAllocState struct {
   242  	f *Func
   243  
   244  	sdom        SparseTree
   245  	registers   []Register
   246  	numRegs     register
   247  	SPReg       register
   248  	SBReg       register
   249  	GReg        register
   250  	allocatable regMask
   251  
   252  	// live values at the end of each block.  live[b.ID] is a list of value IDs
   253  	// which are live at the end of b, together with a count of how many instructions
   254  	// forward to the next use.
   255  	live [][]liveInfo
   256  	// desired register assignments at the end of each block.
   257  	// Note that this is a static map computed before allocation occurs. Dynamic
   258  	// register desires (from partially completed allocations) will trump
   259  	// this information.
   260  	desired []desiredState
   261  
   262  	// current state of each (preregalloc) Value
   263  	values []valState
   264  
   265  	// ID of SP, SB values
   266  	sp, sb ID
   267  
   268  	// For each Value, map from its value ID back to the
   269  	// preregalloc Value it was derived from.
   270  	orig []*Value
   271  
   272  	// current state of each register
   273  	regs []regState
   274  
   275  	// registers that contain values which can't be kicked out
   276  	nospill regMask
   277  
   278  	// mask of registers currently in use
   279  	used regMask
   280  
   281  	// mask of registers used since the start of the current block
   282  	usedSinceBlockStart regMask
   283  
   284  	// mask of registers used in the current instruction
   285  	tmpused regMask
   286  
   287  	// current block we're working on
   288  	curBlock *Block
   289  
   290  	// cache of use records
   291  	freeUseRecords *use
   292  
   293  	// endRegs[blockid] is the register state at the end of each block.
   294  	// encoded as a set of endReg records.
   295  	endRegs [][]endReg
   296  
   297  	// startRegs[blockid] is the register state at the start of merge blocks.
   298  	// saved state does not include the state of phi ops in the block.
   299  	startRegs [][]startReg
   300  
   301  	// startRegsMask is a mask of the registers in startRegs[curBlock.ID].
   302  	// Registers dropped from startRegsMask are later synchronoized back to
   303  	// startRegs by dropping from there as well.
   304  	startRegsMask regMask
   305  
   306  	// spillLive[blockid] is the set of live spills at the end of each block
   307  	spillLive [][]ID
   308  
   309  	// a set of copies we generated to move things around, and
   310  	// whether it is used in shuffle. Unused copies will be deleted.
   311  	copies map[*Value]bool
   312  
   313  	loopnest *loopnest
   314  
   315  	// choose a good order in which to visit blocks for allocation purposes.
   316  	visitOrder []*Block
   317  
   318  	// blockOrder[b.ID] corresponds to the index of block b in visitOrder.
   319  	blockOrder []int32
   320  
   321  	// whether to insert instructions that clobber dead registers at call sites
   322  	doClobber bool
   323  
   324  	// For each instruction index in a basic block, the index of the next call
   325  	// at or after that instruction index.
   326  	// If there is no next call, returns maxInt32.
   327  	// nextCall for a call instruction points to itself.
   328  	// (Indexes and results are pre-regalloc.)
   329  	nextCall []int32
   330  
   331  	// Index of the instruction we're currently working on.
   332  	// Index is expressed in terms of the pre-regalloc b.Values list.
   333  	curIdx int
   334  }
   335  
   336  type endReg struct {
   337  	r register
   338  	v *Value // pre-regalloc value held in this register (TODO: can we use ID here?)
   339  	c *Value // cached version of the value
   340  }
   341  
   342  type startReg struct {
   343  	r   register
   344  	v   *Value   // pre-regalloc value needed in this register
   345  	c   *Value   // cached version of the value
   346  	pos src.XPos // source position of use of this register
   347  }
   348  
   349  // freeReg frees up register r. Any current user of r is kicked out.
   350  func (s *regAllocState) freeReg(r register) {
   351  	v := s.regs[r].v
   352  	if v == nil {
   353  		s.f.Fatalf("tried to free an already free register %d\n", r)
   354  	}
   355  
   356  	// Mark r as unused.
   357  	if s.f.pass.debug > regDebug {
   358  		fmt.Printf("freeReg %s (dump %s/%s)\n", &s.registers[r], v, s.regs[r].c)
   359  	}
   360  	s.regs[r] = regState{}
   361  	s.values[v.ID].regs &^= regMask(1) << r
   362  	s.used &^= regMask(1) << r
   363  }
   364  
   365  // freeRegs frees up all registers listed in m.
   366  func (s *regAllocState) freeRegs(m regMask) {
   367  	for m&s.used != 0 {
   368  		s.freeReg(pickReg(m & s.used))
   369  	}
   370  }
   371  
   372  // clobberRegs inserts instructions that clobber registers listed in m.
   373  func (s *regAllocState) clobberRegs(m regMask) {
   374  	m &= s.allocatable & s.f.Config.gpRegMask // only integer register can contain pointers, only clobber them
   375  	for m != 0 {
   376  		r := pickReg(m)
   377  		m &^= 1 << r
   378  		x := s.curBlock.NewValue0(src.NoXPos, OpClobberReg, types.TypeVoid)
   379  		s.f.setHome(x, &s.registers[r])
   380  	}
   381  }
   382  
   383  // setOrig records that c's original value is the same as
   384  // v's original value.
   385  func (s *regAllocState) setOrig(c *Value, v *Value) {
   386  	if int(c.ID) >= cap(s.orig) {
   387  		x := s.f.Cache.allocValueSlice(int(c.ID) + 1)
   388  		copy(x, s.orig)
   389  		s.f.Cache.freeValueSlice(s.orig)
   390  		s.orig = x
   391  	}
   392  	for int(c.ID) >= len(s.orig) {
   393  		s.orig = append(s.orig, nil)
   394  	}
   395  	if s.orig[c.ID] != nil {
   396  		s.f.Fatalf("orig value set twice %s %s", c, v)
   397  	}
   398  	s.orig[c.ID] = s.orig[v.ID]
   399  }
   400  
   401  // assignReg assigns register r to hold c, a copy of v.
   402  // r must be unused.
   403  func (s *regAllocState) assignReg(r register, v *Value, c *Value) {
   404  	if s.f.pass.debug > regDebug {
   405  		fmt.Printf("assignReg %s %s/%s\n", &s.registers[r], v, c)
   406  	}
   407  	if s.regs[r].v != nil {
   408  		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)
   409  	}
   410  
   411  	// Update state.
   412  	s.regs[r] = regState{v, c}
   413  	s.values[v.ID].regs |= regMask(1) << r
   414  	s.used |= regMask(1) << r
   415  	s.f.setHome(c, &s.registers[r])
   416  }
   417  
   418  // allocReg chooses a register from the set of registers in mask.
   419  // If there is no unused register, a Value will be kicked out of
   420  // a register to make room.
   421  func (s *regAllocState) allocReg(mask regMask, v *Value) register {
   422  	if v.OnWasmStack {
   423  		return noRegister
   424  	}
   425  
   426  	mask &= s.allocatable
   427  	mask &^= s.nospill
   428  	if mask == 0 {
   429  		s.f.Fatalf("no register available for %s", v.LongString())
   430  	}
   431  
   432  	// Pick an unused register if one is available.
   433  	if mask&^s.used != 0 {
   434  		r := pickReg(mask &^ s.used)
   435  		s.usedSinceBlockStart |= regMask(1) << r
   436  		return r
   437  	}
   438  
   439  	// Pick a value to spill. Spill the value with the
   440  	// farthest-in-the-future use.
   441  	// TODO: Prefer registers with already spilled Values?
   442  	// TODO: Modify preference using affinity graph.
   443  	// TODO: if a single value is in multiple registers, spill one of them
   444  	// before spilling a value in just a single register.
   445  
   446  	// Find a register to spill. We spill the register containing the value
   447  	// whose next use is as far in the future as possible.
   448  	// https://en.wikipedia.org/wiki/Page_replacement_algorithm#The_theoretically_optimal_page_replacement_algorithm
   449  	var r register
   450  	maxuse := int32(-1)
   451  	for t := register(0); t < s.numRegs; t++ {
   452  		if mask>>t&1 == 0 {
   453  			continue
   454  		}
   455  		v := s.regs[t].v
   456  		if n := s.values[v.ID].uses.dist; n > maxuse {
   457  			// v's next use is farther in the future than any value
   458  			// we've seen so far. A new best spill candidate.
   459  			r = t
   460  			maxuse = n
   461  		}
   462  	}
   463  	if maxuse == -1 {
   464  		s.f.Fatalf("couldn't find register to spill")
   465  	}
   466  
   467  	if s.f.Config.ctxt.Arch.Arch == sys.ArchWasm {
   468  		// TODO(neelance): In theory this should never happen, because all wasm registers are equal.
   469  		// So if there is still a free register, the allocation should have picked that one in the first place instead of
   470  		// trying to kick some other value out. In practice, this case does happen and it breaks the stack optimization.
   471  		s.freeReg(r)
   472  		return r
   473  	}
   474  
   475  	// Try to move it around before kicking out, if there is a free register.
   476  	// We generate a Copy and record it. It will be deleted if never used.
   477  	v2 := s.regs[r].v
   478  	m := s.compatRegs(v2.Type) &^ s.used &^ s.tmpused &^ (regMask(1) << r)
   479  	if m != 0 && !s.values[v2.ID].rematerializeable && countRegs(s.values[v2.ID].regs) == 1 {
   480  		s.usedSinceBlockStart |= regMask(1) << r
   481  		r2 := pickReg(m)
   482  		c := s.curBlock.NewValue1(v2.Pos, OpCopy, v2.Type, s.regs[r].c)
   483  		s.copies[c] = false
   484  		if s.f.pass.debug > regDebug {
   485  			fmt.Printf("copy %s to %s : %s\n", v2, c, &s.registers[r2])
   486  		}
   487  		s.setOrig(c, v2)
   488  		s.assignReg(r2, v2, c)
   489  	}
   490  
   491  	// If the evicted register isn't used between the start of the block
   492  	// and now then there is no reason to even request it on entry. We can
   493  	// drop from startRegs in that case.
   494  	if s.usedSinceBlockStart&(regMask(1)<<r) == 0 {
   495  		if s.startRegsMask&(regMask(1)<<r) == 1 {
   496  			if s.f.pass.debug > regDebug {
   497  				fmt.Printf("dropped from startRegs: %s\n", &s.registers[r])
   498  			}
   499  			s.startRegsMask &^= regMask(1) << r
   500  		}
   501  	}
   502  
   503  	s.freeReg(r)
   504  	s.usedSinceBlockStart |= regMask(1) << r
   505  	return r
   506  }
   507  
   508  // makeSpill returns a Value which represents the spilled value of v.
   509  // b is the block in which the spill is used.
   510  func (s *regAllocState) makeSpill(v *Value, b *Block) *Value {
   511  	vi := &s.values[v.ID]
   512  	if vi.spill != nil {
   513  		// Final block not known - keep track of subtree where restores reside.
   514  		vi.restoreMin = min(vi.restoreMin, s.sdom[b.ID].entry)
   515  		vi.restoreMax = max(vi.restoreMax, s.sdom[b.ID].exit)
   516  		return vi.spill
   517  	}
   518  	// Make a spill for v. We don't know where we want
   519  	// to put it yet, so we leave it blockless for now.
   520  	spill := s.f.newValueNoBlock(OpStoreReg, v.Type, v.Pos)
   521  	// We also don't know what the spill's arg will be.
   522  	// Leave it argless for now.
   523  	s.setOrig(spill, v)
   524  	vi.spill = spill
   525  	vi.restoreMin = s.sdom[b.ID].entry
   526  	vi.restoreMax = s.sdom[b.ID].exit
   527  	return spill
   528  }
   529  
   530  // allocValToReg allocates v to a register selected from regMask and
   531  // returns the register copy of v. Any previous user is kicked out and spilled
   532  // (if necessary). Load code is added at the current pc. If nospill is set the
   533  // allocated register is marked nospill so the assignment cannot be
   534  // undone until the caller allows it by clearing nospill. Returns a
   535  // *Value which is either v or a copy of v allocated to the chosen register.
   536  func (s *regAllocState) allocValToReg(v *Value, mask regMask, nospill bool, pos src.XPos) *Value {
   537  	if s.f.Config.ctxt.Arch.Arch == sys.ArchWasm && v.rematerializeable() {
   538  		c := v.copyIntoWithXPos(s.curBlock, pos)
   539  		c.OnWasmStack = true
   540  		s.setOrig(c, v)
   541  		return c
   542  	}
   543  	if v.OnWasmStack {
   544  		return v
   545  	}
   546  
   547  	vi := &s.values[v.ID]
   548  	pos = pos.WithNotStmt()
   549  	// Check if v is already in a requested register.
   550  	if mask&vi.regs != 0 {
   551  		r := pickReg(mask & vi.regs)
   552  		if s.regs[r].v != v || s.regs[r].c == nil {
   553  			panic("bad register state")
   554  		}
   555  		if nospill {
   556  			s.nospill |= regMask(1) << r
   557  		}
   558  		s.usedSinceBlockStart |= regMask(1) << r
   559  		return s.regs[r].c
   560  	}
   561  
   562  	var r register
   563  	// If nospill is set, the value is used immediately, so it can live on the WebAssembly stack.
   564  	onWasmStack := nospill && s.f.Config.ctxt.Arch.Arch == sys.ArchWasm
   565  	if !onWasmStack {
   566  		// Allocate a register.
   567  		r = s.allocReg(mask, v)
   568  	}
   569  
   570  	// Allocate v to the new register.
   571  	var c *Value
   572  	if vi.regs != 0 {
   573  		// Copy from a register that v is already in.
   574  		r2 := pickReg(vi.regs)
   575  		if s.regs[r2].v != v {
   576  			panic("bad register state")
   577  		}
   578  		s.usedSinceBlockStart |= regMask(1) << r2
   579  		c = s.curBlock.NewValue1(pos, OpCopy, v.Type, s.regs[r2].c)
   580  	} else if v.rematerializeable() {
   581  		// Rematerialize instead of loading from the spill location.
   582  		c = v.copyIntoWithXPos(s.curBlock, pos)
   583  	} else {
   584  		// Load v from its spill location.
   585  		spill := s.makeSpill(v, s.curBlock)
   586  		if s.f.pass.debug > logSpills {
   587  			s.f.Warnl(vi.spill.Pos, "load spill for %v from %v", v, spill)
   588  		}
   589  		c = s.curBlock.NewValue1(pos, OpLoadReg, v.Type, spill)
   590  	}
   591  
   592  	s.setOrig(c, v)
   593  
   594  	if onWasmStack {
   595  		c.OnWasmStack = true
   596  		return c
   597  	}
   598  
   599  	s.assignReg(r, v, c)
   600  	if c.Op == OpLoadReg && s.isGReg(r) {
   601  		s.f.Fatalf("allocValToReg.OpLoadReg targeting g: " + c.LongString())
   602  	}
   603  	if nospill {
   604  		s.nospill |= regMask(1) << r
   605  	}
   606  	return c
   607  }
   608  
   609  // isLeaf reports whether f performs any calls.
   610  func isLeaf(f *Func) bool {
   611  	for _, b := range f.Blocks {
   612  		for _, v := range b.Values {
   613  			if v.Op.IsCall() && !v.Op.IsTailCall() {
   614  				// tail call is not counted as it does not save the return PC or need a frame
   615  				return false
   616  			}
   617  		}
   618  	}
   619  	return true
   620  }
   621  
   622  // needRegister reports whether v needs a register.
   623  func (v *Value) needRegister() bool {
   624  	return !v.Type.IsMemory() && !v.Type.IsVoid() && !v.Type.IsFlags() && !v.Type.IsTuple()
   625  }
   626  
   627  func (s *regAllocState) init(f *Func) {
   628  	s.f = f
   629  	s.f.RegAlloc = s.f.Cache.locs[:0]
   630  	s.registers = f.Config.registers
   631  	if nr := len(s.registers); nr == 0 || nr > int(noRegister) || nr > int(unsafe.Sizeof(regMask(0))*8) {
   632  		s.f.Fatalf("bad number of registers: %d", nr)
   633  	} else {
   634  		s.numRegs = register(nr)
   635  	}
   636  	// Locate SP, SB, and g registers.
   637  	s.SPReg = noRegister
   638  	s.SBReg = noRegister
   639  	s.GReg = noRegister
   640  	for r := register(0); r < s.numRegs; r++ {
   641  		switch s.registers[r].String() {
   642  		case "SP":
   643  			s.SPReg = r
   644  		case "SB":
   645  			s.SBReg = r
   646  		case "g":
   647  			s.GReg = r
   648  		}
   649  	}
   650  	// Make sure we found all required registers.
   651  	switch noRegister {
   652  	case s.SPReg:
   653  		s.f.Fatalf("no SP register found")
   654  	case s.SBReg:
   655  		s.f.Fatalf("no SB register found")
   656  	case s.GReg:
   657  		if f.Config.hasGReg {
   658  			s.f.Fatalf("no g register found")
   659  		}
   660  	}
   661  
   662  	// Figure out which registers we're allowed to use.
   663  	s.allocatable = s.f.Config.gpRegMask | s.f.Config.fpRegMask | s.f.Config.specialRegMask
   664  	s.allocatable &^= 1 << s.SPReg
   665  	s.allocatable &^= 1 << s.SBReg
   666  	if s.f.Config.hasGReg {
   667  		s.allocatable &^= 1 << s.GReg
   668  	}
   669  	if buildcfg.FramePointerEnabled && s.f.Config.FPReg >= 0 {
   670  		s.allocatable &^= 1 << uint(s.f.Config.FPReg)
   671  	}
   672  	if s.f.Config.LinkReg != -1 {
   673  		if isLeaf(f) {
   674  			// Leaf functions don't save/restore the link register.
   675  			s.allocatable &^= 1 << uint(s.f.Config.LinkReg)
   676  		}
   677  	}
   678  	if s.f.Config.ctxt.Flag_dynlink {
   679  		switch s.f.Config.arch {
   680  		case "386":
   681  			// nothing to do.
   682  			// Note that for Flag_shared (position independent code)
   683  			// we do need to be careful, but that carefulness is hidden
   684  			// in the rewrite rules so we always have a free register
   685  			// available for global load/stores. See _gen/386.rules (search for Flag_shared).
   686  		case "amd64":
   687  			s.allocatable &^= 1 << 15 // R15
   688  		case "arm":
   689  			s.allocatable &^= 1 << 9 // R9
   690  		case "arm64":
   691  			// nothing to do
   692  		case "loong64": // R2 (aka TP) already reserved.
   693  			// nothing to do
   694  		case "ppc64le": // R2 already reserved.
   695  			// nothing to do
   696  		case "riscv64": // X3 (aka GP) and X4 (aka TP) already reserved.
   697  			// nothing to do
   698  		case "s390x":
   699  			s.allocatable &^= 1 << 11 // R11
   700  		default:
   701  			s.f.fe.Fatalf(src.NoXPos, "arch %s not implemented", s.f.Config.arch)
   702  		}
   703  	}
   704  
   705  	// Linear scan register allocation can be influenced by the order in which blocks appear.
   706  	// Decouple the register allocation order from the generated block order.
   707  	// This also creates an opportunity for experiments to find a better order.
   708  	s.visitOrder = layoutRegallocOrder(f)
   709  
   710  	// Compute block order. This array allows us to distinguish forward edges
   711  	// from backward edges and compute how far they go.
   712  	s.blockOrder = make([]int32, f.NumBlocks())
   713  	for i, b := range s.visitOrder {
   714  		s.blockOrder[b.ID] = int32(i)
   715  	}
   716  
   717  	s.regs = make([]regState, s.numRegs)
   718  	nv := f.NumValues()
   719  	if cap(s.f.Cache.regallocValues) >= nv {
   720  		s.f.Cache.regallocValues = s.f.Cache.regallocValues[:nv]
   721  	} else {
   722  		s.f.Cache.regallocValues = make([]valState, nv)
   723  	}
   724  	s.values = s.f.Cache.regallocValues
   725  	s.orig = s.f.Cache.allocValueSlice(nv)
   726  	s.copies = make(map[*Value]bool)
   727  	for _, b := range s.visitOrder {
   728  		for _, v := range b.Values {
   729  			if v.needRegister() {
   730  				s.values[v.ID].needReg = true
   731  				s.values[v.ID].rematerializeable = v.rematerializeable()
   732  				s.orig[v.ID] = v
   733  			}
   734  			// Note: needReg is false for values returning Tuple types.
   735  			// Instead, we mark the corresponding Selects as needReg.
   736  		}
   737  	}
   738  	s.computeLive()
   739  
   740  	s.endRegs = make([][]endReg, f.NumBlocks())
   741  	s.startRegs = make([][]startReg, f.NumBlocks())
   742  	s.spillLive = make([][]ID, f.NumBlocks())
   743  	s.sdom = f.Sdom()
   744  
   745  	// wasm: Mark instructions that can be optimized to have their values only on the WebAssembly stack.
   746  	if f.Config.ctxt.Arch.Arch == sys.ArchWasm {
   747  		canLiveOnStack := f.newSparseSet(f.NumValues())
   748  		defer f.retSparseSet(canLiveOnStack)
   749  		for _, b := range f.Blocks {
   750  			// New block. Clear candidate set.
   751  			canLiveOnStack.clear()
   752  			for _, c := range b.ControlValues() {
   753  				if c.Uses == 1 && !opcodeTable[c.Op].generic {
   754  					canLiveOnStack.add(c.ID)
   755  				}
   756  			}
   757  			// Walking backwards.
   758  			for i := len(b.Values) - 1; i >= 0; i-- {
   759  				v := b.Values[i]
   760  				if canLiveOnStack.contains(v.ID) {
   761  					v.OnWasmStack = true
   762  				} else {
   763  					// Value can not live on stack. Values are not allowed to be reordered, so clear candidate set.
   764  					canLiveOnStack.clear()
   765  				}
   766  				for _, arg := range v.Args {
   767  					// Value can live on the stack if:
   768  					// - it is only used once
   769  					// - it is used in the same basic block
   770  					// - it is not a "mem" value
   771  					// - it is a WebAssembly op
   772  					if arg.Uses == 1 && arg.Block == v.Block && !arg.Type.IsMemory() && !opcodeTable[arg.Op].generic {
   773  						canLiveOnStack.add(arg.ID)
   774  					}
   775  				}
   776  			}
   777  		}
   778  	}
   779  
   780  	// The clobberdeadreg experiment inserts code to clobber dead registers
   781  	// at call sites.
   782  	// Ignore huge functions to avoid doing too much work.
   783  	if base.Flag.ClobberDeadReg && len(s.f.Blocks) <= 10000 {
   784  		// TODO: honor GOCLOBBERDEADHASH, or maybe GOSSAHASH.
   785  		s.doClobber = true
   786  	}
   787  }
   788  
   789  func (s *regAllocState) close() {
   790  	s.f.Cache.freeValueSlice(s.orig)
   791  }
   792  
   793  // Adds a use record for id at distance dist from the start of the block.
   794  // All calls to addUse must happen with nonincreasing dist.
   795  func (s *regAllocState) addUse(id ID, dist int32, pos src.XPos) {
   796  	r := s.freeUseRecords
   797  	if r != nil {
   798  		s.freeUseRecords = r.next
   799  	} else {
   800  		r = &use{}
   801  	}
   802  	r.dist = dist
   803  	r.pos = pos
   804  	r.next = s.values[id].uses
   805  	s.values[id].uses = r
   806  	if r.next != nil && dist > r.next.dist {
   807  		s.f.Fatalf("uses added in wrong order")
   808  	}
   809  }
   810  
   811  // advanceUses advances the uses of v's args from the state before v to the state after v.
   812  // Any values which have no more uses are deallocated from registers.
   813  func (s *regAllocState) advanceUses(v *Value) {
   814  	for _, a := range v.Args {
   815  		if !s.values[a.ID].needReg {
   816  			continue
   817  		}
   818  		ai := &s.values[a.ID]
   819  		r := ai.uses
   820  		ai.uses = r.next
   821  		if r.next == nil || (a.Op != OpSP && a.Op != OpSB && r.next.dist > s.nextCall[s.curIdx]) {
   822  			// Value is dead (or is not used again until after a call), free all registers that hold it.
   823  			s.freeRegs(ai.regs)
   824  		}
   825  		r.next = s.freeUseRecords
   826  		s.freeUseRecords = r
   827  	}
   828  	s.dropIfUnused(v)
   829  }
   830  
   831  // Drop v from registers if it isn't used again, or its only uses are after
   832  // a call instruction.
   833  func (s *regAllocState) dropIfUnused(v *Value) {
   834  	if !s.values[v.ID].needReg {
   835  		return
   836  	}
   837  	vi := &s.values[v.ID]
   838  	r := vi.uses
   839  	if r == nil || (v.Op != OpSP && v.Op != OpSB && r.dist > s.nextCall[s.curIdx]) {
   840  		s.freeRegs(vi.regs)
   841  	}
   842  }
   843  
   844  // liveAfterCurrentInstruction reports whether v is live after
   845  // the current instruction is completed.  v must be used by the
   846  // current instruction.
   847  func (s *regAllocState) liveAfterCurrentInstruction(v *Value) bool {
   848  	u := s.values[v.ID].uses
   849  	if u == nil {
   850  		panic(fmt.Errorf("u is nil, v = %s, s.values[v.ID] = %v", v.LongString(), s.values[v.ID]))
   851  	}
   852  	d := u.dist
   853  	for u != nil && u.dist == d {
   854  		u = u.next
   855  	}
   856  	return u != nil && u.dist > d
   857  }
   858  
   859  // Sets the state of the registers to that encoded in regs.
   860  func (s *regAllocState) setState(regs []endReg) {
   861  	s.freeRegs(s.used)
   862  	for _, x := range regs {
   863  		s.assignReg(x.r, x.v, x.c)
   864  	}
   865  }
   866  
   867  // compatRegs returns the set of registers which can store a type t.
   868  func (s *regAllocState) compatRegs(t *types.Type) regMask {
   869  	var m regMask
   870  	if t.IsTuple() || t.IsFlags() {
   871  		return 0
   872  	}
   873  	if t.IsFloat() || t == types.TypeInt128 {
   874  		if t.Kind() == types.TFLOAT32 && s.f.Config.fp32RegMask != 0 {
   875  			m = s.f.Config.fp32RegMask
   876  		} else if t.Kind() == types.TFLOAT64 && s.f.Config.fp64RegMask != 0 {
   877  			m = s.f.Config.fp64RegMask
   878  		} else {
   879  			m = s.f.Config.fpRegMask
   880  		}
   881  	} else {
   882  		m = s.f.Config.gpRegMask
   883  	}
   884  	return m & s.allocatable
   885  }
   886  
   887  // regspec returns the regInfo for operation op.
   888  func (s *regAllocState) regspec(v *Value) regInfo {
   889  	op := v.Op
   890  	if op == OpConvert {
   891  		// OpConvert is a generic op, so it doesn't have a
   892  		// register set in the static table. It can use any
   893  		// allocatable integer register.
   894  		m := s.allocatable & s.f.Config.gpRegMask
   895  		return regInfo{inputs: []inputInfo{{regs: m}}, outputs: []outputInfo{{regs: m}}}
   896  	}
   897  	if op == OpArgIntReg {
   898  		reg := v.Block.Func.Config.intParamRegs[v.AuxInt8()]
   899  		return regInfo{outputs: []outputInfo{{regs: 1 << uint(reg)}}}
   900  	}
   901  	if op == OpArgFloatReg {
   902  		reg := v.Block.Func.Config.floatParamRegs[v.AuxInt8()]
   903  		return regInfo{outputs: []outputInfo{{regs: 1 << uint(reg)}}}
   904  	}
   905  	if op.IsCall() {
   906  		if ac, ok := v.Aux.(*AuxCall); ok && ac.reg != nil {
   907  			return *ac.Reg(&opcodeTable[op].reg, s.f.Config)
   908  		}
   909  	}
   910  	if op == OpMakeResult && s.f.OwnAux.reg != nil {
   911  		return *s.f.OwnAux.ResultReg(s.f.Config)
   912  	}
   913  	return opcodeTable[op].reg
   914  }
   915  
   916  func (s *regAllocState) isGReg(r register) bool {
   917  	return s.f.Config.hasGReg && s.GReg == r
   918  }
   919  
   920  // Dummy value used to represent the value being held in a temporary register.
   921  var tmpVal Value
   922  
   923  func (s *regAllocState) regalloc(f *Func) {
   924  	regValLiveSet := f.newSparseSet(f.NumValues()) // set of values that may be live in register
   925  	defer f.retSparseSet(regValLiveSet)
   926  	var oldSched []*Value
   927  	var phis []*Value
   928  	var phiRegs []register
   929  	var args []*Value
   930  
   931  	// Data structure used for computing desired registers.
   932  	var desired desiredState
   933  
   934  	// Desired registers for inputs & outputs for each instruction in the block.
   935  	type dentry struct {
   936  		out [4]register    // desired output registers
   937  		in  [3][4]register // desired input registers (for inputs 0,1, and 2)
   938  	}
   939  	var dinfo []dentry
   940  
   941  	if f.Entry != f.Blocks[0] {
   942  		f.Fatalf("entry block must be first")
   943  	}
   944  
   945  	for _, b := range s.visitOrder {
   946  		if s.f.pass.debug > regDebug {
   947  			fmt.Printf("Begin processing block %v\n", b)
   948  		}
   949  		s.curBlock = b
   950  		s.startRegsMask = 0
   951  		s.usedSinceBlockStart = 0
   952  
   953  		// Initialize regValLiveSet and uses fields for this block.
   954  		// Walk backwards through the block doing liveness analysis.
   955  		regValLiveSet.clear()
   956  		for _, e := range s.live[b.ID] {
   957  			s.addUse(e.ID, int32(len(b.Values))+e.dist, e.pos) // pseudo-uses from beyond end of block
   958  			regValLiveSet.add(e.ID)
   959  		}
   960  		for _, v := range b.ControlValues() {
   961  			if s.values[v.ID].needReg {
   962  				s.addUse(v.ID, int32(len(b.Values)), b.Pos) // pseudo-use by control values
   963  				regValLiveSet.add(v.ID)
   964  			}
   965  		}
   966  		if len(s.nextCall) < len(b.Values) {
   967  			s.nextCall = append(s.nextCall, make([]int32, len(b.Values)-len(s.nextCall))...)
   968  		}
   969  		var nextCall int32 = math.MaxInt32
   970  		for i := len(b.Values) - 1; i >= 0; i-- {
   971  			v := b.Values[i]
   972  			regValLiveSet.remove(v.ID)
   973  			if v.Op == OpPhi {
   974  				// Remove v from the live set, but don't add
   975  				// any inputs. This is the state the len(b.Preds)>1
   976  				// case below desires; it wants to process phis specially.
   977  				s.nextCall[i] = nextCall
   978  				continue
   979  			}
   980  			if opcodeTable[v.Op].call {
   981  				// Function call clobbers all the registers but SP and SB.
   982  				regValLiveSet.clear()
   983  				if s.sp != 0 && s.values[s.sp].uses != nil {
   984  					regValLiveSet.add(s.sp)
   985  				}
   986  				if s.sb != 0 && s.values[s.sb].uses != nil {
   987  					regValLiveSet.add(s.sb)
   988  				}
   989  				nextCall = int32(i)
   990  			}
   991  			for _, a := range v.Args {
   992  				if !s.values[a.ID].needReg {
   993  					continue
   994  				}
   995  				s.addUse(a.ID, int32(i), v.Pos)
   996  				regValLiveSet.add(a.ID)
   997  			}
   998  			s.nextCall[i] = nextCall
   999  		}
  1000  		if s.f.pass.debug > regDebug {
  1001  			fmt.Printf("use distances for %s\n", b)
  1002  			for i := range s.values {
  1003  				vi := &s.values[i]
  1004  				u := vi.uses
  1005  				if u == nil {
  1006  					continue
  1007  				}
  1008  				fmt.Printf("  v%d:", i)
  1009  				for u != nil {
  1010  					fmt.Printf(" %d", u.dist)
  1011  					u = u.next
  1012  				}
  1013  				fmt.Println()
  1014  			}
  1015  		}
  1016  
  1017  		// Make a copy of the block schedule so we can generate a new one in place.
  1018  		// We make a separate copy for phis and regular values.
  1019  		nphi := 0
  1020  		for _, v := range b.Values {
  1021  			if v.Op != OpPhi {
  1022  				break
  1023  			}
  1024  			nphi++
  1025  		}
  1026  		phis = append(phis[:0], b.Values[:nphi]...)
  1027  		oldSched = append(oldSched[:0], b.Values[nphi:]...)
  1028  		b.Values = b.Values[:0]
  1029  
  1030  		// Initialize start state of block.
  1031  		if b == f.Entry {
  1032  			// Regalloc state is empty to start.
  1033  			if nphi > 0 {
  1034  				f.Fatalf("phis in entry block")
  1035  			}
  1036  		} else if len(b.Preds) == 1 {
  1037  			// Start regalloc state with the end state of the previous block.
  1038  			s.setState(s.endRegs[b.Preds[0].b.ID])
  1039  			if nphi > 0 {
  1040  				f.Fatalf("phis in single-predecessor block")
  1041  			}
  1042  			// Drop any values which are no longer live.
  1043  			// This may happen because at the end of p, a value may be
  1044  			// live but only used by some other successor of p.
  1045  			for r := register(0); r < s.numRegs; r++ {
  1046  				v := s.regs[r].v
  1047  				if v != nil && !regValLiveSet.contains(v.ID) {
  1048  					s.freeReg(r)
  1049  				}
  1050  			}
  1051  		} else {
  1052  			// This is the complicated case. We have more than one predecessor,
  1053  			// which means we may have Phi ops.
  1054  
  1055  			// Start with the final register state of the predecessor with least spill values.
  1056  			// This is based on the following points:
  1057  			// 1, The less spill value indicates that the register pressure of this path is smaller,
  1058  			//    so the values of this block are more likely to be allocated to registers.
  1059  			// 2, Avoid the predecessor that contains the function call, because the predecessor that
  1060  			//    contains the function call usually generates a lot of spills and lose the previous
  1061  			//    allocation state.
  1062  			// TODO: Improve this part. At least the size of endRegs of the predecessor also has
  1063  			// an impact on the code size and compiler speed. But it is not easy to find a simple
  1064  			// and efficient method that combines multiple factors.
  1065  			idx := -1
  1066  			for i, p := range b.Preds {
  1067  				// If the predecessor has not been visited yet, skip it because its end state
  1068  				// (redRegs and spillLive) has not been computed yet.
  1069  				pb := p.b
  1070  				if s.blockOrder[pb.ID] >= s.blockOrder[b.ID] {
  1071  					continue
  1072  				}
  1073  				if idx == -1 {
  1074  					idx = i
  1075  					continue
  1076  				}
  1077  				pSel := b.Preds[idx].b
  1078  				if len(s.spillLive[pb.ID]) < len(s.spillLive[pSel.ID]) {
  1079  					idx = i
  1080  				} else if len(s.spillLive[pb.ID]) == len(s.spillLive[pSel.ID]) {
  1081  					// Use a bit of likely information. After critical pass, pb and pSel must
  1082  					// be plain blocks, so check edge pb->pb.Preds instead of edge pb->b.
  1083  					// TODO: improve the prediction of the likely predecessor. The following
  1084  					// method is only suitable for the simplest cases. For complex cases,
  1085  					// the prediction may be inaccurate, but this does not affect the
  1086  					// correctness of the program.
  1087  					// According to the layout algorithm, the predecessor with the
  1088  					// smaller blockOrder is the true branch, and the test results show
  1089  					// that it is better to choose the predecessor with a smaller
  1090  					// blockOrder than no choice.
  1091  					if pb.likelyBranch() && !pSel.likelyBranch() || s.blockOrder[pb.ID] < s.blockOrder[pSel.ID] {
  1092  						idx = i
  1093  					}
  1094  				}
  1095  			}
  1096  			if idx < 0 {
  1097  				f.Fatalf("bad visitOrder, no predecessor of %s has been visited before it", b)
  1098  			}
  1099  			p := b.Preds[idx].b
  1100  			s.setState(s.endRegs[p.ID])
  1101  
  1102  			if s.f.pass.debug > regDebug {
  1103  				fmt.Printf("starting merge block %s with end state of %s:\n", b, p)
  1104  				for _, x := range s.endRegs[p.ID] {
  1105  					fmt.Printf("  %s: orig:%s cache:%s\n", &s.registers[x.r], x.v, x.c)
  1106  				}
  1107  			}
  1108  
  1109  			// Decide on registers for phi ops. Use the registers determined
  1110  			// by the primary predecessor if we can.
  1111  			// TODO: pick best of (already processed) predecessors?
  1112  			// Majority vote? Deepest nesting level?
  1113  			phiRegs = phiRegs[:0]
  1114  			var phiUsed regMask
  1115  
  1116  			for _, v := range phis {
  1117  				if !s.values[v.ID].needReg {
  1118  					phiRegs = append(phiRegs, noRegister)
  1119  					continue
  1120  				}
  1121  				a := v.Args[idx]
  1122  				// Some instructions target not-allocatable registers.
  1123  				// They're not suitable for further (phi-function) allocation.
  1124  				m := s.values[a.ID].regs &^ phiUsed & s.allocatable
  1125  				if m != 0 {
  1126  					r := pickReg(m)
  1127  					phiUsed |= regMask(1) << r
  1128  					phiRegs = append(phiRegs, r)
  1129  				} else {
  1130  					phiRegs = append(phiRegs, noRegister)
  1131  				}
  1132  			}
  1133  
  1134  			// Second pass - deallocate all in-register phi inputs.
  1135  			for i, v := range phis {
  1136  				if !s.values[v.ID].needReg {
  1137  					continue
  1138  				}
  1139  				a := v.Args[idx]
  1140  				r := phiRegs[i]
  1141  				if r == noRegister {
  1142  					continue
  1143  				}
  1144  				if regValLiveSet.contains(a.ID) {
  1145  					// Input value is still live (it is used by something other than Phi).
  1146  					// Try to move it around before kicking out, if there is a free register.
  1147  					// We generate a Copy in the predecessor block and record it. It will be
  1148  					// deleted later if never used.
  1149  					//
  1150  					// Pick a free register. At this point some registers used in the predecessor
  1151  					// block may have been deallocated. Those are the ones used for Phis. Exclude
  1152  					// them (and they are not going to be helpful anyway).
  1153  					m := s.compatRegs(a.Type) &^ s.used &^ phiUsed
  1154  					if m != 0 && !s.values[a.ID].rematerializeable && countRegs(s.values[a.ID].regs) == 1 {
  1155  						r2 := pickReg(m)
  1156  						c := p.NewValue1(a.Pos, OpCopy, a.Type, s.regs[r].c)
  1157  						s.copies[c] = false
  1158  						if s.f.pass.debug > regDebug {
  1159  							fmt.Printf("copy %s to %s : %s\n", a, c, &s.registers[r2])
  1160  						}
  1161  						s.setOrig(c, a)
  1162  						s.assignReg(r2, a, c)
  1163  						s.endRegs[p.ID] = append(s.endRegs[p.ID], endReg{r2, a, c})
  1164  					}
  1165  				}
  1166  				s.freeReg(r)
  1167  			}
  1168  
  1169  			// Copy phi ops into new schedule.
  1170  			b.Values = append(b.Values, phis...)
  1171  
  1172  			// Third pass - pick registers for phis whose input
  1173  			// was not in a register in the primary predecessor.
  1174  			for i, v := range phis {
  1175  				if !s.values[v.ID].needReg {
  1176  					continue
  1177  				}
  1178  				if phiRegs[i] != noRegister {
  1179  					continue
  1180  				}
  1181  				m := s.compatRegs(v.Type) &^ phiUsed &^ s.used
  1182  				// If one of the other inputs of v is in a register, and the register is available,
  1183  				// select this register, which can save some unnecessary copies.
  1184  				for i, pe := range b.Preds {
  1185  					if i == idx {
  1186  						continue
  1187  					}
  1188  					ri := noRegister
  1189  					for _, er := range s.endRegs[pe.b.ID] {
  1190  						if er.v == s.orig[v.Args[i].ID] {
  1191  							ri = er.r
  1192  							break
  1193  						}
  1194  					}
  1195  					if ri != noRegister && m>>ri&1 != 0 {
  1196  						m = regMask(1) << ri
  1197  						break
  1198  					}
  1199  				}
  1200  				if m != 0 {
  1201  					r := pickReg(m)
  1202  					phiRegs[i] = r
  1203  					phiUsed |= regMask(1) << r
  1204  				}
  1205  			}
  1206  
  1207  			// Set registers for phis. Add phi spill code.
  1208  			for i, v := range phis {
  1209  				if !s.values[v.ID].needReg {
  1210  					continue
  1211  				}
  1212  				r := phiRegs[i]
  1213  				if r == noRegister {
  1214  					// stack-based phi
  1215  					// Spills will be inserted in all the predecessors below.
  1216  					s.values[v.ID].spill = v // v starts life spilled
  1217  					continue
  1218  				}
  1219  				// register-based phi
  1220  				s.assignReg(r, v, v)
  1221  			}
  1222  
  1223  			// Deallocate any values which are no longer live. Phis are excluded.
  1224  			for r := register(0); r < s.numRegs; r++ {
  1225  				if phiUsed>>r&1 != 0 {
  1226  					continue
  1227  				}
  1228  				v := s.regs[r].v
  1229  				if v != nil && !regValLiveSet.contains(v.ID) {
  1230  					s.freeReg(r)
  1231  				}
  1232  			}
  1233  
  1234  			// Save the starting state for use by merge edges.
  1235  			// We append to a stack allocated variable that we'll
  1236  			// later copy into s.startRegs in one fell swoop, to save
  1237  			// on allocations.
  1238  			regList := make([]startReg, 0, 32)
  1239  			for r := register(0); r < s.numRegs; r++ {
  1240  				v := s.regs[r].v
  1241  				if v == nil {
  1242  					continue
  1243  				}
  1244  				if phiUsed>>r&1 != 0 {
  1245  					// Skip registers that phis used, we'll handle those
  1246  					// specially during merge edge processing.
  1247  					continue
  1248  				}
  1249  				regList = append(regList, startReg{r, v, s.regs[r].c, s.values[v.ID].uses.pos})
  1250  				s.startRegsMask |= regMask(1) << r
  1251  			}
  1252  			s.startRegs[b.ID] = make([]startReg, len(regList))
  1253  			copy(s.startRegs[b.ID], regList)
  1254  
  1255  			if s.f.pass.debug > regDebug {
  1256  				fmt.Printf("after phis\n")
  1257  				for _, x := range s.startRegs[b.ID] {
  1258  					fmt.Printf("  %s: v%d\n", &s.registers[x.r], x.v.ID)
  1259  				}
  1260  			}
  1261  		}
  1262  
  1263  		// Drop phis from registers if they immediately go dead.
  1264  		for i, v := range phis {
  1265  			s.curIdx = i
  1266  			s.dropIfUnused(v)
  1267  		}
  1268  
  1269  		// Allocate space to record the desired registers for each value.
  1270  		if l := len(oldSched); cap(dinfo) < l {
  1271  			dinfo = make([]dentry, l)
  1272  		} else {
  1273  			dinfo = dinfo[:l]
  1274  			for i := range dinfo {
  1275  				dinfo[i] = dentry{}
  1276  			}
  1277  		}
  1278  
  1279  		// Load static desired register info at the end of the block.
  1280  		desired.copy(&s.desired[b.ID])
  1281  
  1282  		// Check actual assigned registers at the start of the next block(s).
  1283  		// Dynamically assigned registers will trump the static
  1284  		// desired registers computed during liveness analysis.
  1285  		// Note that we do this phase after startRegs is set above, so that
  1286  		// we get the right behavior for a block which branches to itself.
  1287  		for _, e := range b.Succs {
  1288  			succ := e.b
  1289  			// TODO: prioritize likely successor?
  1290  			for _, x := range s.startRegs[succ.ID] {
  1291  				desired.add(x.v.ID, x.r)
  1292  			}
  1293  			// Process phi ops in succ.
  1294  			pidx := e.i
  1295  			for _, v := range succ.Values {
  1296  				if v.Op != OpPhi {
  1297  					break
  1298  				}
  1299  				if !s.values[v.ID].needReg {
  1300  					continue
  1301  				}
  1302  				rp, ok := s.f.getHome(v.ID).(*Register)
  1303  				if !ok {
  1304  					// If v is not assigned a register, pick a register assigned to one of v's inputs.
  1305  					// Hopefully v will get assigned that register later.
  1306  					// If the inputs have allocated register information, add it to desired,
  1307  					// which may reduce spill or copy operations when the register is available.
  1308  					for _, a := range v.Args {
  1309  						rp, ok = s.f.getHome(a.ID).(*Register)
  1310  						if ok {
  1311  							break
  1312  						}
  1313  					}
  1314  					if !ok {
  1315  						continue
  1316  					}
  1317  				}
  1318  				desired.add(v.Args[pidx].ID, register(rp.num))
  1319  			}
  1320  		}
  1321  		// Walk values backwards computing desired register info.
  1322  		// See computeLive for more comments.
  1323  		for i := len(oldSched) - 1; i >= 0; i-- {
  1324  			v := oldSched[i]
  1325  			prefs := desired.remove(v.ID)
  1326  			regspec := s.regspec(v)
  1327  			desired.clobber(regspec.clobbers)
  1328  			for _, j := range regspec.inputs {
  1329  				if countRegs(j.regs) != 1 {
  1330  					continue
  1331  				}
  1332  				desired.clobber(j.regs)
  1333  				desired.add(v.Args[j.idx].ID, pickReg(j.regs))
  1334  			}
  1335  			if opcodeTable[v.Op].resultInArg0 || v.Op == OpAMD64ADDQconst || v.Op == OpAMD64ADDLconst || v.Op == OpSelect0 {
  1336  				if opcodeTable[v.Op].commutative {
  1337  					desired.addList(v.Args[1].ID, prefs)
  1338  				}
  1339  				desired.addList(v.Args[0].ID, prefs)
  1340  			}
  1341  			// Save desired registers for this value.
  1342  			dinfo[i].out = prefs
  1343  			for j, a := range v.Args {
  1344  				if j >= len(dinfo[i].in) {
  1345  					break
  1346  				}
  1347  				dinfo[i].in[j] = desired.get(a.ID)
  1348  			}
  1349  		}
  1350  
  1351  		// Process all the non-phi values.
  1352  		for idx, v := range oldSched {
  1353  			s.curIdx = nphi + idx
  1354  			tmpReg := noRegister
  1355  			if s.f.pass.debug > regDebug {
  1356  				fmt.Printf("  processing %s\n", v.LongString())
  1357  			}
  1358  			regspec := s.regspec(v)
  1359  			if v.Op == OpPhi {
  1360  				f.Fatalf("phi %s not at start of block", v)
  1361  			}
  1362  			if v.Op == OpSP {
  1363  				s.assignReg(s.SPReg, v, v)
  1364  				b.Values = append(b.Values, v)
  1365  				s.advanceUses(v)
  1366  				s.sp = v.ID
  1367  				continue
  1368  			}
  1369  			if v.Op == OpSB {
  1370  				s.assignReg(s.SBReg, v, v)
  1371  				b.Values = append(b.Values, v)
  1372  				s.advanceUses(v)
  1373  				s.sb = v.ID
  1374  				continue
  1375  			}
  1376  			if v.Op == OpSelect0 || v.Op == OpSelect1 || v.Op == OpSelectN {
  1377  				if s.values[v.ID].needReg {
  1378  					if v.Op == OpSelectN {
  1379  						s.assignReg(register(s.f.getHome(v.Args[0].ID).(LocResults)[int(v.AuxInt)].(*Register).num), v, v)
  1380  					} else {
  1381  						var i = 0
  1382  						if v.Op == OpSelect1 {
  1383  							i = 1
  1384  						}
  1385  						s.assignReg(register(s.f.getHome(v.Args[0].ID).(LocPair)[i].(*Register).num), v, v)
  1386  					}
  1387  				}
  1388  				b.Values = append(b.Values, v)
  1389  				s.advanceUses(v)
  1390  				continue
  1391  			}
  1392  			if v.Op == OpGetG && s.f.Config.hasGReg {
  1393  				// use hardware g register
  1394  				if s.regs[s.GReg].v != nil {
  1395  					s.freeReg(s.GReg) // kick out the old value
  1396  				}
  1397  				s.assignReg(s.GReg, v, v)
  1398  				b.Values = append(b.Values, v)
  1399  				s.advanceUses(v)
  1400  				continue
  1401  			}
  1402  			if v.Op == OpArg {
  1403  				// Args are "pre-spilled" values. We don't allocate
  1404  				// any register here. We just set up the spill pointer to
  1405  				// point at itself and any later user will restore it to use it.
  1406  				s.values[v.ID].spill = v
  1407  				b.Values = append(b.Values, v)
  1408  				s.advanceUses(v)
  1409  				continue
  1410  			}
  1411  			if v.Op == OpKeepAlive {
  1412  				// Make sure the argument to v is still live here.
  1413  				s.advanceUses(v)
  1414  				a := v.Args[0]
  1415  				vi := &s.values[a.ID]
  1416  				if vi.regs == 0 && !vi.rematerializeable {
  1417  					// Use the spill location.
  1418  					// This forces later liveness analysis to make the
  1419  					// value live at this point.
  1420  					v.SetArg(0, s.makeSpill(a, b))
  1421  				} else if _, ok := a.Aux.(*ir.Name); ok && vi.rematerializeable {
  1422  					// Rematerializeable value with a gc.Node. This is the address of
  1423  					// a stack object (e.g. an LEAQ). Keep the object live.
  1424  					// Change it to VarLive, which is what plive expects for locals.
  1425  					v.Op = OpVarLive
  1426  					v.SetArgs1(v.Args[1])
  1427  					v.Aux = a.Aux
  1428  				} else {
  1429  					// In-register and rematerializeable values are already live.
  1430  					// These are typically rematerializeable constants like nil,
  1431  					// or values of a variable that were modified since the last call.
  1432  					v.Op = OpCopy
  1433  					v.SetArgs1(v.Args[1])
  1434  				}
  1435  				b.Values = append(b.Values, v)
  1436  				continue
  1437  			}
  1438  			if len(regspec.inputs) == 0 && len(regspec.outputs) == 0 {
  1439  				// No register allocation required (or none specified yet)
  1440  				if s.doClobber && v.Op.IsCall() {
  1441  					s.clobberRegs(regspec.clobbers)
  1442  				}
  1443  				s.freeRegs(regspec.clobbers)
  1444  				b.Values = append(b.Values, v)
  1445  				s.advanceUses(v)
  1446  				continue
  1447  			}
  1448  
  1449  			if s.values[v.ID].rematerializeable {
  1450  				// Value is rematerializeable, don't issue it here.
  1451  				// It will get issued just before each use (see
  1452  				// allocValueToReg).
  1453  				for _, a := range v.Args {
  1454  					a.Uses--
  1455  				}
  1456  				s.advanceUses(v)
  1457  				continue
  1458  			}
  1459  
  1460  			if s.f.pass.debug > regDebug {
  1461  				fmt.Printf("value %s\n", v.LongString())
  1462  				fmt.Printf("  out:")
  1463  				for _, r := range dinfo[idx].out {
  1464  					if r != noRegister {
  1465  						fmt.Printf(" %s", &s.registers[r])
  1466  					}
  1467  				}
  1468  				fmt.Println()
  1469  				for i := 0; i < len(v.Args) && i < 3; i++ {
  1470  					fmt.Printf("  in%d:", i)
  1471  					for _, r := range dinfo[idx].in[i] {
  1472  						if r != noRegister {
  1473  							fmt.Printf(" %s", &s.registers[r])
  1474  						}
  1475  					}
  1476  					fmt.Println()
  1477  				}
  1478  			}
  1479  
  1480  			// Move arguments to registers.
  1481  			// First, if an arg must be in a specific register and it is already
  1482  			// in place, keep it.
  1483  			args = append(args[:0], make([]*Value, len(v.Args))...)
  1484  			for i, a := range v.Args {
  1485  				if !s.values[a.ID].needReg {
  1486  					args[i] = a
  1487  				}
  1488  			}
  1489  			for _, i := range regspec.inputs {
  1490  				mask := i.regs
  1491  				if countRegs(mask) == 1 && mask&s.values[v.Args[i.idx].ID].regs != 0 {
  1492  					args[i.idx] = s.allocValToReg(v.Args[i.idx], mask, true, v.Pos)
  1493  				}
  1494  			}
  1495  			// Then, if an arg must be in a specific register and that
  1496  			// register is free, allocate that one. Otherwise when processing
  1497  			// another input we may kick a value into the free register, which
  1498  			// then will be kicked out again.
  1499  			// This is a common case for passing-in-register arguments for
  1500  			// function calls.
  1501  			for {
  1502  				freed := false
  1503  				for _, i := range regspec.inputs {
  1504  					if args[i.idx] != nil {
  1505  						continue // already allocated
  1506  					}
  1507  					mask := i.regs
  1508  					if countRegs(mask) == 1 && mask&^s.used != 0 {
  1509  						args[i.idx] = s.allocValToReg(v.Args[i.idx], mask, true, v.Pos)
  1510  						// If the input is in other registers that will be clobbered by v,
  1511  						// or the input is dead, free the registers. This may make room
  1512  						// for other inputs.
  1513  						oldregs := s.values[v.Args[i.idx].ID].regs
  1514  						if oldregs&^regspec.clobbers == 0 || !s.liveAfterCurrentInstruction(v.Args[i.idx]) {
  1515  							s.freeRegs(oldregs &^ mask &^ s.nospill)
  1516  							freed = true
  1517  						}
  1518  					}
  1519  				}
  1520  				if !freed {
  1521  					break
  1522  				}
  1523  			}
  1524  			// Last, allocate remaining ones, in an ordering defined
  1525  			// by the register specification (most constrained first).
  1526  			for _, i := range regspec.inputs {
  1527  				if args[i.idx] != nil {
  1528  					continue // already allocated
  1529  				}
  1530  				mask := i.regs
  1531  				if mask&s.values[v.Args[i.idx].ID].regs == 0 {
  1532  					// Need a new register for the input.
  1533  					mask &= s.allocatable
  1534  					mask &^= s.nospill
  1535  					// Used desired register if available.
  1536  					if i.idx < 3 {
  1537  						for _, r := range dinfo[idx].in[i.idx] {
  1538  							if r != noRegister && (mask&^s.used)>>r&1 != 0 {
  1539  								// Desired register is allowed and unused.
  1540  								mask = regMask(1) << r
  1541  								break
  1542  							}
  1543  						}
  1544  					}
  1545  					// Avoid registers we're saving for other values.
  1546  					if mask&^desired.avoid != 0 {
  1547  						mask &^= desired.avoid
  1548  					}
  1549  				}
  1550  				args[i.idx] = s.allocValToReg(v.Args[i.idx], mask, true, v.Pos)
  1551  			}
  1552  
  1553  			// If the output clobbers the input register, make sure we have
  1554  			// at least two copies of the input register so we don't
  1555  			// have to reload the value from the spill location.
  1556  			if opcodeTable[v.Op].resultInArg0 {
  1557  				var m regMask
  1558  				if !s.liveAfterCurrentInstruction(v.Args[0]) {
  1559  					// arg0 is dead.  We can clobber its register.
  1560  					goto ok
  1561  				}
  1562  				if opcodeTable[v.Op].commutative && !s.liveAfterCurrentInstruction(v.Args[1]) {
  1563  					args[0], args[1] = args[1], args[0]
  1564  					goto ok
  1565  				}
  1566  				if s.values[v.Args[0].ID].rematerializeable {
  1567  					// We can rematerialize the input, don't worry about clobbering it.
  1568  					goto ok
  1569  				}
  1570  				if opcodeTable[v.Op].commutative && s.values[v.Args[1].ID].rematerializeable {
  1571  					args[0], args[1] = args[1], args[0]
  1572  					goto ok
  1573  				}
  1574  				if countRegs(s.values[v.Args[0].ID].regs) >= 2 {
  1575  					// we have at least 2 copies of arg0.  We can afford to clobber one.
  1576  					goto ok
  1577  				}
  1578  				if opcodeTable[v.Op].commutative && countRegs(s.values[v.Args[1].ID].regs) >= 2 {
  1579  					args[0], args[1] = args[1], args[0]
  1580  					goto ok
  1581  				}
  1582  
  1583  				// We can't overwrite arg0 (or arg1, if commutative).  So we
  1584  				// need to make a copy of an input so we have a register we can modify.
  1585  
  1586  				// Possible new registers to copy into.
  1587  				m = s.compatRegs(v.Args[0].Type) &^ s.used
  1588  				if m == 0 {
  1589  					// No free registers.  In this case we'll just clobber
  1590  					// an input and future uses of that input must use a restore.
  1591  					// TODO(khr): We should really do this like allocReg does it,
  1592  					// spilling the value with the most distant next use.
  1593  					goto ok
  1594  				}
  1595  
  1596  				// Try to move an input to the desired output, if allowed.
  1597  				for _, r := range dinfo[idx].out {
  1598  					if r != noRegister && (m&regspec.outputs[0].regs)>>r&1 != 0 {
  1599  						m = regMask(1) << r
  1600  						args[0] = s.allocValToReg(v.Args[0], m, true, v.Pos)
  1601  						// Note: we update args[0] so the instruction will
  1602  						// use the register copy we just made.
  1603  						goto ok
  1604  					}
  1605  				}
  1606  				// Try to copy input to its desired location & use its old
  1607  				// location as the result register.
  1608  				for _, r := range dinfo[idx].in[0] {
  1609  					if r != noRegister && m>>r&1 != 0 {
  1610  						m = regMask(1) << r
  1611  						c := s.allocValToReg(v.Args[0], m, true, v.Pos)
  1612  						s.copies[c] = false
  1613  						// Note: no update to args[0] so the instruction will
  1614  						// use the original copy.
  1615  						goto ok
  1616  					}
  1617  				}
  1618  				if opcodeTable[v.Op].commutative {
  1619  					for _, r := range dinfo[idx].in[1] {
  1620  						if r != noRegister && m>>r&1 != 0 {
  1621  							m = regMask(1) << r
  1622  							c := s.allocValToReg(v.Args[1], m, true, v.Pos)
  1623  							s.copies[c] = false
  1624  							args[0], args[1] = args[1], args[0]
  1625  							goto ok
  1626  						}
  1627  					}
  1628  				}
  1629  
  1630  				// Avoid future fixed uses if we can.
  1631  				if m&^desired.avoid != 0 {
  1632  					m &^= desired.avoid
  1633  				}
  1634  				// Save input 0 to a new register so we can clobber it.
  1635  				c := s.allocValToReg(v.Args[0], m, true, v.Pos)
  1636  				s.copies[c] = false
  1637  
  1638  				// Normally we use the register of the old copy of input 0 as the target.
  1639  				// However, if input 0 is already in its desired register then we use
  1640  				// the register of the new copy instead.
  1641  				if regspec.outputs[0].regs>>s.f.getHome(c.ID).(*Register).num&1 != 0 {
  1642  					if rp, ok := s.f.getHome(args[0].ID).(*Register); ok {
  1643  						r := register(rp.num)
  1644  						for _, r2 := range dinfo[idx].in[0] {
  1645  							if r == r2 {
  1646  								args[0] = c
  1647  								break
  1648  							}
  1649  						}
  1650  					}
  1651  				}
  1652  			}
  1653  
  1654  		ok:
  1655  			// Pick a temporary register if needed.
  1656  			// It should be distinct from all the input registers, so we
  1657  			// allocate it after all the input registers, but before
  1658  			// the input registers are freed via advanceUses below.
  1659  			// (Not all instructions need that distinct part, but it is conservative.)
  1660  			// We also ensure it is not any of the single-choice output registers.
  1661  			if opcodeTable[v.Op].needIntTemp {
  1662  				m := s.allocatable & s.f.Config.gpRegMask
  1663  				for _, out := range regspec.outputs {
  1664  					if countRegs(out.regs) == 1 {
  1665  						m &^= out.regs
  1666  					}
  1667  				}
  1668  				if m&^desired.avoid&^s.nospill != 0 {
  1669  					m &^= desired.avoid
  1670  				}
  1671  				tmpReg = s.allocReg(m, &tmpVal)
  1672  				s.nospill |= regMask(1) << tmpReg
  1673  				s.tmpused |= regMask(1) << tmpReg
  1674  			}
  1675  
  1676  			// Now that all args are in regs, we're ready to issue the value itself.
  1677  			// Before we pick a register for the output value, allow input registers
  1678  			// to be deallocated. We do this here so that the output can use the
  1679  			// same register as a dying input.
  1680  			if !opcodeTable[v.Op].resultNotInArgs {
  1681  				s.tmpused = s.nospill
  1682  				s.nospill = 0
  1683  				s.advanceUses(v) // frees any registers holding args that are no longer live
  1684  			}
  1685  
  1686  			// Dump any registers which will be clobbered
  1687  			if s.doClobber && v.Op.IsCall() {
  1688  				// clobber registers that are marked as clobber in regmask, but
  1689  				// don't clobber inputs.
  1690  				s.clobberRegs(regspec.clobbers &^ s.tmpused &^ s.nospill)
  1691  			}
  1692  			s.freeRegs(regspec.clobbers)
  1693  			s.tmpused |= regspec.clobbers
  1694  
  1695  			// Pick registers for outputs.
  1696  			{
  1697  				outRegs := noRegisters // TODO if this is costly, hoist and clear incrementally below.
  1698  				maxOutIdx := -1
  1699  				var used regMask
  1700  				if tmpReg != noRegister {
  1701  					// Ensure output registers are distinct from the temporary register.
  1702  					// (Not all instructions need that distinct part, but it is conservative.)
  1703  					used |= regMask(1) << tmpReg
  1704  				}
  1705  				for _, out := range regspec.outputs {
  1706  					if out.regs == 0 {
  1707  						continue
  1708  					}
  1709  					mask := out.regs & s.allocatable &^ used
  1710  					if mask == 0 {
  1711  						s.f.Fatalf("can't find any output register %s", v.LongString())
  1712  					}
  1713  					if opcodeTable[v.Op].resultInArg0 && out.idx == 0 {
  1714  						if !opcodeTable[v.Op].commutative {
  1715  							// Output must use the same register as input 0.
  1716  							r := register(s.f.getHome(args[0].ID).(*Register).num)
  1717  							if mask>>r&1 == 0 {
  1718  								s.f.Fatalf("resultInArg0 value's input %v cannot be an output of %s", s.f.getHome(args[0].ID).(*Register), v.LongString())
  1719  							}
  1720  							mask = regMask(1) << r
  1721  						} else {
  1722  							// Output must use the same register as input 0 or 1.
  1723  							r0 := register(s.f.getHome(args[0].ID).(*Register).num)
  1724  							r1 := register(s.f.getHome(args[1].ID).(*Register).num)
  1725  							// Check r0 and r1 for desired output register.
  1726  							found := false
  1727  							for _, r := range dinfo[idx].out {
  1728  								if (r == r0 || r == r1) && (mask&^s.used)>>r&1 != 0 {
  1729  									mask = regMask(1) << r
  1730  									found = true
  1731  									if r == r1 {
  1732  										args[0], args[1] = args[1], args[0]
  1733  									}
  1734  									break
  1735  								}
  1736  							}
  1737  							if !found {
  1738  								// Neither are desired, pick r0.
  1739  								mask = regMask(1) << r0
  1740  							}
  1741  						}
  1742  					}
  1743  					if out.idx == 0 { // desired registers only apply to the first element of a tuple result
  1744  						for _, r := range dinfo[idx].out {
  1745  							if r != noRegister && (mask&^s.used)>>r&1 != 0 {
  1746  								// Desired register is allowed and unused.
  1747  								mask = regMask(1) << r
  1748  								break
  1749  							}
  1750  						}
  1751  					}
  1752  					// Avoid registers we're saving for other values.
  1753  					if mask&^desired.avoid&^s.nospill&^s.used != 0 {
  1754  						mask &^= desired.avoid
  1755  					}
  1756  					r := s.allocReg(mask, v)
  1757  					if out.idx > maxOutIdx {
  1758  						maxOutIdx = out.idx
  1759  					}
  1760  					outRegs[out.idx] = r
  1761  					used |= regMask(1) << r
  1762  					s.tmpused |= regMask(1) << r
  1763  				}
  1764  				// Record register choices
  1765  				if v.Type.IsTuple() {
  1766  					var outLocs LocPair
  1767  					if r := outRegs[0]; r != noRegister {
  1768  						outLocs[0] = &s.registers[r]
  1769  					}
  1770  					if r := outRegs[1]; r != noRegister {
  1771  						outLocs[1] = &s.registers[r]
  1772  					}
  1773  					s.f.setHome(v, outLocs)
  1774  					// Note that subsequent SelectX instructions will do the assignReg calls.
  1775  				} else if v.Type.IsResults() {
  1776  					// preallocate outLocs to the right size, which is maxOutIdx+1
  1777  					outLocs := make(LocResults, maxOutIdx+1, maxOutIdx+1)
  1778  					for i := 0; i <= maxOutIdx; i++ {
  1779  						if r := outRegs[i]; r != noRegister {
  1780  							outLocs[i] = &s.registers[r]
  1781  						}
  1782  					}
  1783  					s.f.setHome(v, outLocs)
  1784  				} else {
  1785  					if r := outRegs[0]; r != noRegister {
  1786  						s.assignReg(r, v, v)
  1787  					}
  1788  				}
  1789  				if tmpReg != noRegister {
  1790  					// Remember the temp register allocation, if any.
  1791  					if s.f.tempRegs == nil {
  1792  						s.f.tempRegs = map[ID]*Register{}
  1793  					}
  1794  					s.f.tempRegs[v.ID] = &s.registers[tmpReg]
  1795  				}
  1796  			}
  1797  
  1798  			// deallocate dead args, if we have not done so
  1799  			if opcodeTable[v.Op].resultNotInArgs {
  1800  				s.nospill = 0
  1801  				s.advanceUses(v) // frees any registers holding args that are no longer live
  1802  			}
  1803  			s.tmpused = 0
  1804  
  1805  			// Issue the Value itself.
  1806  			for i, a := range args {
  1807  				v.SetArg(i, a) // use register version of arguments
  1808  			}
  1809  			b.Values = append(b.Values, v)
  1810  			s.dropIfUnused(v)
  1811  		}
  1812  
  1813  		// Copy the control values - we need this so we can reduce the
  1814  		// uses property of these values later.
  1815  		controls := append(make([]*Value, 0, 2), b.ControlValues()...)
  1816  
  1817  		// Load control values into registers.
  1818  		for i, v := range b.ControlValues() {
  1819  			if !s.values[v.ID].needReg {
  1820  				continue
  1821  			}
  1822  			if s.f.pass.debug > regDebug {
  1823  				fmt.Printf("  processing control %s\n", v.LongString())
  1824  			}
  1825  			// We assume that a control input can be passed in any
  1826  			// type-compatible register. If this turns out not to be true,
  1827  			// we'll need to introduce a regspec for a block's control value.
  1828  			b.ReplaceControl(i, s.allocValToReg(v, s.compatRegs(v.Type), false, b.Pos))
  1829  		}
  1830  
  1831  		// Reduce the uses of the control values once registers have been loaded.
  1832  		// This loop is equivalent to the advanceUses method.
  1833  		for _, v := range controls {
  1834  			vi := &s.values[v.ID]
  1835  			if !vi.needReg {
  1836  				continue
  1837  			}
  1838  			// Remove this use from the uses list.
  1839  			u := vi.uses
  1840  			vi.uses = u.next
  1841  			if u.next == nil {
  1842  				s.freeRegs(vi.regs) // value is dead
  1843  			}
  1844  			u.next = s.freeUseRecords
  1845  			s.freeUseRecords = u
  1846  		}
  1847  
  1848  		// If we are approaching a merge point and we are the primary
  1849  		// predecessor of it, find live values that we use soon after
  1850  		// the merge point and promote them to registers now.
  1851  		if len(b.Succs) == 1 {
  1852  			if s.f.Config.hasGReg && s.regs[s.GReg].v != nil {
  1853  				s.freeReg(s.GReg) // Spill value in G register before any merge.
  1854  			}
  1855  			// For this to be worthwhile, the loop must have no calls in it.
  1856  			top := b.Succs[0].b
  1857  			loop := s.loopnest.b2l[top.ID]
  1858  			if loop == nil || loop.header != top || loop.containsUnavoidableCall {
  1859  				goto badloop
  1860  			}
  1861  
  1862  			// TODO: sort by distance, pick the closest ones?
  1863  			for _, live := range s.live[b.ID] {
  1864  				if live.dist >= unlikelyDistance {
  1865  					// Don't preload anything live after the loop.
  1866  					continue
  1867  				}
  1868  				vid := live.ID
  1869  				vi := &s.values[vid]
  1870  				if vi.regs != 0 {
  1871  					continue
  1872  				}
  1873  				if vi.rematerializeable {
  1874  					continue
  1875  				}
  1876  				v := s.orig[vid]
  1877  				m := s.compatRegs(v.Type) &^ s.used
  1878  				// Used desired register if available.
  1879  			outerloop:
  1880  				for _, e := range desired.entries {
  1881  					if e.ID != v.ID {
  1882  						continue
  1883  					}
  1884  					for _, r := range e.regs {
  1885  						if r != noRegister && m>>r&1 != 0 {
  1886  							m = regMask(1) << r
  1887  							break outerloop
  1888  						}
  1889  					}
  1890  				}
  1891  				if m&^desired.avoid != 0 {
  1892  					m &^= desired.avoid
  1893  				}
  1894  				if m != 0 {
  1895  					s.allocValToReg(v, m, false, b.Pos)
  1896  				}
  1897  			}
  1898  		}
  1899  	badloop:
  1900  		;
  1901  
  1902  		// Save end-of-block register state.
  1903  		// First count how many, this cuts allocations in half.
  1904  		k := 0
  1905  		for r := register(0); r < s.numRegs; r++ {
  1906  			v := s.regs[r].v
  1907  			if v == nil {
  1908  				continue
  1909  			}
  1910  			k++
  1911  		}
  1912  		regList := make([]endReg, 0, k)
  1913  		for r := register(0); r < s.numRegs; r++ {
  1914  			v := s.regs[r].v
  1915  			if v == nil {
  1916  				continue
  1917  			}
  1918  			regList = append(regList, endReg{r, v, s.regs[r].c})
  1919  		}
  1920  		s.endRegs[b.ID] = regList
  1921  
  1922  		if checkEnabled {
  1923  			regValLiveSet.clear()
  1924  			for _, x := range s.live[b.ID] {
  1925  				regValLiveSet.add(x.ID)
  1926  			}
  1927  			for r := register(0); r < s.numRegs; r++ {
  1928  				v := s.regs[r].v
  1929  				if v == nil {
  1930  					continue
  1931  				}
  1932  				if !regValLiveSet.contains(v.ID) {
  1933  					s.f.Fatalf("val %s is in reg but not live at end of %s", v, b)
  1934  				}
  1935  			}
  1936  		}
  1937  
  1938  		// If a value is live at the end of the block and
  1939  		// isn't in a register, generate a use for the spill location.
  1940  		// We need to remember this information so that
  1941  		// the liveness analysis in stackalloc is correct.
  1942  		for _, e := range s.live[b.ID] {
  1943  			vi := &s.values[e.ID]
  1944  			if vi.regs != 0 {
  1945  				// in a register, we'll use that source for the merge.
  1946  				continue
  1947  			}
  1948  			if vi.rematerializeable {
  1949  				// we'll rematerialize during the merge.
  1950  				continue
  1951  			}
  1952  			if s.f.pass.debug > regDebug {
  1953  				fmt.Printf("live-at-end spill for %s at %s\n", s.orig[e.ID], b)
  1954  			}
  1955  			spill := s.makeSpill(s.orig[e.ID], b)
  1956  			s.spillLive[b.ID] = append(s.spillLive[b.ID], spill.ID)
  1957  		}
  1958  
  1959  		// Clear any final uses.
  1960  		// All that is left should be the pseudo-uses added for values which
  1961  		// are live at the end of b.
  1962  		for _, e := range s.live[b.ID] {
  1963  			u := s.values[e.ID].uses
  1964  			if u == nil {
  1965  				f.Fatalf("live at end, no uses v%d", e.ID)
  1966  			}
  1967  			if u.next != nil {
  1968  				f.Fatalf("live at end, too many uses v%d", e.ID)
  1969  			}
  1970  			s.values[e.ID].uses = nil
  1971  			u.next = s.freeUseRecords
  1972  			s.freeUseRecords = u
  1973  		}
  1974  
  1975  		// allocReg may have dropped registers from startRegsMask that
  1976  		// aren't actually needed in startRegs. Synchronize back to
  1977  		// startRegs.
  1978  		//
  1979  		// This must be done before placing spills, which will look at
  1980  		// startRegs to decide if a block is a valid block for a spill.
  1981  		if c := countRegs(s.startRegsMask); c != len(s.startRegs[b.ID]) {
  1982  			regs := make([]startReg, 0, c)
  1983  			for _, sr := range s.startRegs[b.ID] {
  1984  				if s.startRegsMask&(regMask(1)<<sr.r) == 0 {
  1985  					continue
  1986  				}
  1987  				regs = append(regs, sr)
  1988  			}
  1989  			s.startRegs[b.ID] = regs
  1990  		}
  1991  	}
  1992  
  1993  	// Decide where the spills we generated will go.
  1994  	s.placeSpills()
  1995  
  1996  	// Anything that didn't get a register gets a stack location here.
  1997  	// (StoreReg, stack-based phis, inputs, ...)
  1998  	stacklive := stackalloc(s.f, s.spillLive)
  1999  
  2000  	// Fix up all merge edges.
  2001  	s.shuffle(stacklive)
  2002  
  2003  	// Erase any copies we never used.
  2004  	// Also, an unused copy might be the only use of another copy,
  2005  	// so continue erasing until we reach a fixed point.
  2006  	for {
  2007  		progress := false
  2008  		for c, used := range s.copies {
  2009  			if !used && c.Uses == 0 {
  2010  				if s.f.pass.debug > regDebug {
  2011  					fmt.Printf("delete copied value %s\n", c.LongString())
  2012  				}
  2013  				c.resetArgs()
  2014  				f.freeValue(c)
  2015  				delete(s.copies, c)
  2016  				progress = true
  2017  			}
  2018  		}
  2019  		if !progress {
  2020  			break
  2021  		}
  2022  	}
  2023  
  2024  	for _, b := range s.visitOrder {
  2025  		i := 0
  2026  		for _, v := range b.Values {
  2027  			if v.Op == OpInvalid {
  2028  				continue
  2029  			}
  2030  			b.Values[i] = v
  2031  			i++
  2032  		}
  2033  		b.Values = b.Values[:i]
  2034  	}
  2035  }
  2036  
  2037  func (s *regAllocState) placeSpills() {
  2038  	mustBeFirst := func(op Op) bool {
  2039  		return op.isLoweredGetClosurePtr() || op == OpPhi || op == OpArgIntReg || op == OpArgFloatReg
  2040  	}
  2041  
  2042  	// Start maps block IDs to the list of spills
  2043  	// that go at the start of the block (but after any phis).
  2044  	start := map[ID][]*Value{}
  2045  	// After maps value IDs to the list of spills
  2046  	// that go immediately after that value ID.
  2047  	after := map[ID][]*Value{}
  2048  
  2049  	for i := range s.values {
  2050  		vi := s.values[i]
  2051  		spill := vi.spill
  2052  		if spill == nil {
  2053  			continue
  2054  		}
  2055  		if spill.Block != nil {
  2056  			// Some spills are already fully set up,
  2057  			// like OpArgs and stack-based phis.
  2058  			continue
  2059  		}
  2060  		v := s.orig[i]
  2061  
  2062  		// Walk down the dominator tree looking for a good place to
  2063  		// put the spill of v.  At the start "best" is the best place
  2064  		// we have found so far.
  2065  		// TODO: find a way to make this O(1) without arbitrary cutoffs.
  2066  		if v == nil {
  2067  			panic(fmt.Errorf("nil v, s.orig[%d], vi = %v, spill = %s", i, vi, spill.LongString()))
  2068  		}
  2069  		best := v.Block
  2070  		bestArg := v
  2071  		var bestDepth int16
  2072  		if l := s.loopnest.b2l[best.ID]; l != nil {
  2073  			bestDepth = l.depth
  2074  		}
  2075  		b := best
  2076  		const maxSpillSearch = 100
  2077  		for i := 0; i < maxSpillSearch; i++ {
  2078  			// Find the child of b in the dominator tree which
  2079  			// dominates all restores.
  2080  			p := b
  2081  			b = nil
  2082  			for c := s.sdom.Child(p); c != nil && i < maxSpillSearch; c, i = s.sdom.Sibling(c), i+1 {
  2083  				if s.sdom[c.ID].entry <= vi.restoreMin && s.sdom[c.ID].exit >= vi.restoreMax {
  2084  					// c also dominates all restores.  Walk down into c.
  2085  					b = c
  2086  					break
  2087  				}
  2088  			}
  2089  			if b == nil {
  2090  				// Ran out of blocks which dominate all restores.
  2091  				break
  2092  			}
  2093  
  2094  			var depth int16
  2095  			if l := s.loopnest.b2l[b.ID]; l != nil {
  2096  				depth = l.depth
  2097  			}
  2098  			if depth > bestDepth {
  2099  				// Don't push the spill into a deeper loop.
  2100  				continue
  2101  			}
  2102  
  2103  			// If v is in a register at the start of b, we can
  2104  			// place the spill here (after the phis).
  2105  			if len(b.Preds) == 1 {
  2106  				for _, e := range s.endRegs[b.Preds[0].b.ID] {
  2107  					if e.v == v {
  2108  						// Found a better spot for the spill.
  2109  						best = b
  2110  						bestArg = e.c
  2111  						bestDepth = depth
  2112  						break
  2113  					}
  2114  				}
  2115  			} else {
  2116  				for _, e := range s.startRegs[b.ID] {
  2117  					if e.v == v {
  2118  						// Found a better spot for the spill.
  2119  						best = b
  2120  						bestArg = e.c
  2121  						bestDepth = depth
  2122  						break
  2123  					}
  2124  				}
  2125  			}
  2126  		}
  2127  
  2128  		// Put the spill in the best block we found.
  2129  		spill.Block = best
  2130  		spill.AddArg(bestArg)
  2131  		if best == v.Block && !mustBeFirst(v.Op) {
  2132  			// Place immediately after v.
  2133  			after[v.ID] = append(after[v.ID], spill)
  2134  		} else {
  2135  			// Place at the start of best block.
  2136  			start[best.ID] = append(start[best.ID], spill)
  2137  		}
  2138  	}
  2139  
  2140  	// Insert spill instructions into the block schedules.
  2141  	var oldSched []*Value
  2142  	for _, b := range s.visitOrder {
  2143  		nfirst := 0
  2144  		for _, v := range b.Values {
  2145  			if !mustBeFirst(v.Op) {
  2146  				break
  2147  			}
  2148  			nfirst++
  2149  		}
  2150  		oldSched = append(oldSched[:0], b.Values[nfirst:]...)
  2151  		b.Values = b.Values[:nfirst]
  2152  		b.Values = append(b.Values, start[b.ID]...)
  2153  		for _, v := range oldSched {
  2154  			b.Values = append(b.Values, v)
  2155  			b.Values = append(b.Values, after[v.ID]...)
  2156  		}
  2157  	}
  2158  }
  2159  
  2160  // shuffle fixes up all the merge edges (those going into blocks of indegree > 1).
  2161  func (s *regAllocState) shuffle(stacklive [][]ID) {
  2162  	var e edgeState
  2163  	e.s = s
  2164  	e.cache = map[ID][]*Value{}
  2165  	e.contents = map[Location]contentRecord{}
  2166  	if s.f.pass.debug > regDebug {
  2167  		fmt.Printf("shuffle %s\n", s.f.Name)
  2168  		fmt.Println(s.f.String())
  2169  	}
  2170  
  2171  	for _, b := range s.visitOrder {
  2172  		if len(b.Preds) <= 1 {
  2173  			continue
  2174  		}
  2175  		e.b = b
  2176  		for i, edge := range b.Preds {
  2177  			p := edge.b
  2178  			e.p = p
  2179  			e.setup(i, s.endRegs[p.ID], s.startRegs[b.ID], stacklive[p.ID])
  2180  			e.process()
  2181  		}
  2182  	}
  2183  
  2184  	if s.f.pass.debug > regDebug {
  2185  		fmt.Printf("post shuffle %s\n", s.f.Name)
  2186  		fmt.Println(s.f.String())
  2187  	}
  2188  }
  2189  
  2190  type edgeState struct {
  2191  	s    *regAllocState
  2192  	p, b *Block // edge goes from p->b.
  2193  
  2194  	// for each pre-regalloc value, a list of equivalent cached values
  2195  	cache      map[ID][]*Value
  2196  	cachedVals []ID // (superset of) keys of the above map, for deterministic iteration
  2197  
  2198  	// map from location to the value it contains
  2199  	contents map[Location]contentRecord
  2200  
  2201  	// desired destination locations
  2202  	destinations []dstRecord
  2203  	extra        []dstRecord
  2204  
  2205  	usedRegs              regMask // registers currently holding something
  2206  	uniqueRegs            regMask // registers holding the only copy of a value
  2207  	finalRegs             regMask // registers holding final target
  2208  	rematerializeableRegs regMask // registers that hold rematerializeable values
  2209  }
  2210  
  2211  type contentRecord struct {
  2212  	vid   ID       // pre-regalloc value
  2213  	c     *Value   // cached value
  2214  	final bool     // this is a satisfied destination
  2215  	pos   src.XPos // source position of use of the value
  2216  }
  2217  
  2218  type dstRecord struct {
  2219  	loc    Location // register or stack slot
  2220  	vid    ID       // pre-regalloc value it should contain
  2221  	splice **Value  // place to store reference to the generating instruction
  2222  	pos    src.XPos // source position of use of this location
  2223  }
  2224  
  2225  // setup initializes the edge state for shuffling.
  2226  func (e *edgeState) setup(idx int, srcReg []endReg, dstReg []startReg, stacklive []ID) {
  2227  	if e.s.f.pass.debug > regDebug {
  2228  		fmt.Printf("edge %s->%s\n", e.p, e.b)
  2229  	}
  2230  
  2231  	// Clear state.
  2232  	clear(e.cache)
  2233  	e.cachedVals = e.cachedVals[:0]
  2234  	clear(e.contents)
  2235  	e.usedRegs = 0
  2236  	e.uniqueRegs = 0
  2237  	e.finalRegs = 0
  2238  	e.rematerializeableRegs = 0
  2239  
  2240  	// Live registers can be sources.
  2241  	for _, x := range srcReg {
  2242  		e.set(&e.s.registers[x.r], x.v.ID, x.c, false, src.NoXPos) // don't care the position of the source
  2243  	}
  2244  	// So can all of the spill locations.
  2245  	for _, spillID := range stacklive {
  2246  		v := e.s.orig[spillID]
  2247  		spill := e.s.values[v.ID].spill
  2248  		if !e.s.sdom.IsAncestorEq(spill.Block, e.p) {
  2249  			// Spills were placed that only dominate the uses found
  2250  			// during the first regalloc pass. The edge fixup code
  2251  			// can't use a spill location if the spill doesn't dominate
  2252  			// the edge.
  2253  			// We are guaranteed that if the spill doesn't dominate this edge,
  2254  			// then the value is available in a register (because we called
  2255  			// makeSpill for every value not in a register at the start
  2256  			// of an edge).
  2257  			continue
  2258  		}
  2259  		e.set(e.s.f.getHome(spillID), v.ID, spill, false, src.NoXPos) // don't care the position of the source
  2260  	}
  2261  
  2262  	// Figure out all the destinations we need.
  2263  	dsts := e.destinations[:0]
  2264  	for _, x := range dstReg {
  2265  		dsts = append(dsts, dstRecord{&e.s.registers[x.r], x.v.ID, nil, x.pos})
  2266  	}
  2267  	// Phis need their args to end up in a specific location.
  2268  	for _, v := range e.b.Values {
  2269  		if v.Op != OpPhi {
  2270  			break
  2271  		}
  2272  		loc := e.s.f.getHome(v.ID)
  2273  		if loc == nil {
  2274  			continue
  2275  		}
  2276  		dsts = append(dsts, dstRecord{loc, v.Args[idx].ID, &v.Args[idx], v.Pos})
  2277  	}
  2278  	e.destinations = dsts
  2279  
  2280  	if e.s.f.pass.debug > regDebug {
  2281  		for _, vid := range e.cachedVals {
  2282  			a := e.cache[vid]
  2283  			for _, c := range a {
  2284  				fmt.Printf("src %s: v%d cache=%s\n", e.s.f.getHome(c.ID), vid, c)
  2285  			}
  2286  		}
  2287  		for _, d := range e.destinations {
  2288  			fmt.Printf("dst %s: v%d\n", d.loc, d.vid)
  2289  		}
  2290  	}
  2291  }
  2292  
  2293  // process generates code to move all the values to the right destination locations.
  2294  func (e *edgeState) process() {
  2295  	dsts := e.destinations
  2296  
  2297  	// Process the destinations until they are all satisfied.
  2298  	for len(dsts) > 0 {
  2299  		i := 0
  2300  		for _, d := range dsts {
  2301  			if !e.processDest(d.loc, d.vid, d.splice, d.pos) {
  2302  				// Failed - save for next iteration.
  2303  				dsts[i] = d
  2304  				i++
  2305  			}
  2306  		}
  2307  		if i < len(dsts) {
  2308  			// Made some progress. Go around again.
  2309  			dsts = dsts[:i]
  2310  
  2311  			// Append any extras destinations we generated.
  2312  			dsts = append(dsts, e.extra...)
  2313  			e.extra = e.extra[:0]
  2314  			continue
  2315  		}
  2316  
  2317  		// We made no progress. That means that any
  2318  		// remaining unsatisfied moves are in simple cycles.
  2319  		// For example, A -> B -> C -> D -> A.
  2320  		//   A ----> B
  2321  		//   ^       |
  2322  		//   |       |
  2323  		//   |       v
  2324  		//   D <---- C
  2325  
  2326  		// To break the cycle, we pick an unused register, say R,
  2327  		// and put a copy of B there.
  2328  		//   A ----> B
  2329  		//   ^       |
  2330  		//   |       |
  2331  		//   |       v
  2332  		//   D <---- C <---- R=copyofB
  2333  		// When we resume the outer loop, the A->B move can now proceed,
  2334  		// and eventually the whole cycle completes.
  2335  
  2336  		// Copy any cycle location to a temp register. This duplicates
  2337  		// one of the cycle entries, allowing the just duplicated value
  2338  		// to be overwritten and the cycle to proceed.
  2339  		d := dsts[0]
  2340  		loc := d.loc
  2341  		vid := e.contents[loc].vid
  2342  		c := e.contents[loc].c
  2343  		r := e.findRegFor(c.Type)
  2344  		if e.s.f.pass.debug > regDebug {
  2345  			fmt.Printf("breaking cycle with v%d in %s:%s\n", vid, loc, c)
  2346  		}
  2347  		e.erase(r)
  2348  		pos := d.pos.WithNotStmt()
  2349  		if _, isReg := loc.(*Register); isReg {
  2350  			c = e.p.NewValue1(pos, OpCopy, c.Type, c)
  2351  		} else {
  2352  			c = e.p.NewValue1(pos, OpLoadReg, c.Type, c)
  2353  		}
  2354  		e.set(r, vid, c, false, pos)
  2355  		if c.Op == OpLoadReg && e.s.isGReg(register(r.(*Register).num)) {
  2356  			e.s.f.Fatalf("process.OpLoadReg targeting g: " + c.LongString())
  2357  		}
  2358  	}
  2359  }
  2360  
  2361  // processDest generates code to put value vid into location loc. Returns true
  2362  // if progress was made.
  2363  func (e *edgeState) processDest(loc Location, vid ID, splice **Value, pos src.XPos) bool {
  2364  	pos = pos.WithNotStmt()
  2365  	occupant := e.contents[loc]
  2366  	if occupant.vid == vid {
  2367  		// Value is already in the correct place.
  2368  		e.contents[loc] = contentRecord{vid, occupant.c, true, pos}
  2369  		if splice != nil {
  2370  			(*splice).Uses--
  2371  			*splice = occupant.c
  2372  			occupant.c.Uses++
  2373  		}
  2374  		// Note: if splice==nil then c will appear dead. This is
  2375  		// non-SSA formed code, so be careful after this pass not to run
  2376  		// deadcode elimination.
  2377  		if _, ok := e.s.copies[occupant.c]; ok {
  2378  			// The copy at occupant.c was used to avoid spill.
  2379  			e.s.copies[occupant.c] = true
  2380  		}
  2381  		return true
  2382  	}
  2383  
  2384  	// Check if we're allowed to clobber the destination location.
  2385  	if len(e.cache[occupant.vid]) == 1 && !e.s.values[occupant.vid].rematerializeable {
  2386  		// We can't overwrite the last copy
  2387  		// of a value that needs to survive.
  2388  		return false
  2389  	}
  2390  
  2391  	// Copy from a source of v, register preferred.
  2392  	v := e.s.orig[vid]
  2393  	var c *Value
  2394  	var src Location
  2395  	if e.s.f.pass.debug > regDebug {
  2396  		fmt.Printf("moving v%d to %s\n", vid, loc)
  2397  		fmt.Printf("sources of v%d:", vid)
  2398  	}
  2399  	for _, w := range e.cache[vid] {
  2400  		h := e.s.f.getHome(w.ID)
  2401  		if e.s.f.pass.debug > regDebug {
  2402  			fmt.Printf(" %s:%s", h, w)
  2403  		}
  2404  		_, isreg := h.(*Register)
  2405  		if src == nil || isreg {
  2406  			c = w
  2407  			src = h
  2408  		}
  2409  	}
  2410  	if e.s.f.pass.debug > regDebug {
  2411  		if src != nil {
  2412  			fmt.Printf(" [use %s]\n", src)
  2413  		} else {
  2414  			fmt.Printf(" [no source]\n")
  2415  		}
  2416  	}
  2417  	_, dstReg := loc.(*Register)
  2418  
  2419  	// Pre-clobber destination. This avoids the
  2420  	// following situation:
  2421  	//   - v is currently held in R0 and stacktmp0.
  2422  	//   - We want to copy stacktmp1 to stacktmp0.
  2423  	//   - We choose R0 as the temporary register.
  2424  	// During the copy, both R0 and stacktmp0 are
  2425  	// clobbered, losing both copies of v. Oops!
  2426  	// Erasing the destination early means R0 will not
  2427  	// be chosen as the temp register, as it will then
  2428  	// be the last copy of v.
  2429  	e.erase(loc)
  2430  	var x *Value
  2431  	if c == nil || e.s.values[vid].rematerializeable {
  2432  		if !e.s.values[vid].rematerializeable {
  2433  			e.s.f.Fatalf("can't find source for %s->%s: %s\n", e.p, e.b, v.LongString())
  2434  		}
  2435  		if dstReg {
  2436  			x = v.copyInto(e.p)
  2437  		} else {
  2438  			// Rematerialize into stack slot. Need a free
  2439  			// register to accomplish this.
  2440  			r := e.findRegFor(v.Type)
  2441  			e.erase(r)
  2442  			x = v.copyIntoWithXPos(e.p, pos)
  2443  			e.set(r, vid, x, false, pos)
  2444  			// Make sure we spill with the size of the slot, not the
  2445  			// size of x (which might be wider due to our dropping
  2446  			// of narrowing conversions).
  2447  			x = e.p.NewValue1(pos, OpStoreReg, loc.(LocalSlot).Type, x)
  2448  		}
  2449  	} else {
  2450  		// Emit move from src to dst.
  2451  		_, srcReg := src.(*Register)
  2452  		if srcReg {
  2453  			if dstReg {
  2454  				x = e.p.NewValue1(pos, OpCopy, c.Type, c)
  2455  			} else {
  2456  				x = e.p.NewValue1(pos, OpStoreReg, loc.(LocalSlot).Type, c)
  2457  			}
  2458  		} else {
  2459  			if dstReg {
  2460  				x = e.p.NewValue1(pos, OpLoadReg, c.Type, c)
  2461  			} else {
  2462  				// mem->mem. Use temp register.
  2463  				r := e.findRegFor(c.Type)
  2464  				e.erase(r)
  2465  				t := e.p.NewValue1(pos, OpLoadReg, c.Type, c)
  2466  				e.set(r, vid, t, false, pos)
  2467  				x = e.p.NewValue1(pos, OpStoreReg, loc.(LocalSlot).Type, t)
  2468  			}
  2469  		}
  2470  	}
  2471  	e.set(loc, vid, x, true, pos)
  2472  	if x.Op == OpLoadReg && e.s.isGReg(register(loc.(*Register).num)) {
  2473  		e.s.f.Fatalf("processDest.OpLoadReg targeting g: " + x.LongString())
  2474  	}
  2475  	if splice != nil {
  2476  		(*splice).Uses--
  2477  		*splice = x
  2478  		x.Uses++
  2479  	}
  2480  	return true
  2481  }
  2482  
  2483  // set changes the contents of location loc to hold the given value and its cached representative.
  2484  func (e *edgeState) set(loc Location, vid ID, c *Value, final bool, pos src.XPos) {
  2485  	e.s.f.setHome(c, loc)
  2486  	e.contents[loc] = contentRecord{vid, c, final, pos}
  2487  	a := e.cache[vid]
  2488  	if len(a) == 0 {
  2489  		e.cachedVals = append(e.cachedVals, vid)
  2490  	}
  2491  	a = append(a, c)
  2492  	e.cache[vid] = a
  2493  	if r, ok := loc.(*Register); ok {
  2494  		if e.usedRegs&(regMask(1)<<uint(r.num)) != 0 {
  2495  			e.s.f.Fatalf("%v is already set (v%d/%v)", r, vid, c)
  2496  		}
  2497  		e.usedRegs |= regMask(1) << uint(r.num)
  2498  		if final {
  2499  			e.finalRegs |= regMask(1) << uint(r.num)
  2500  		}
  2501  		if len(a) == 1 {
  2502  			e.uniqueRegs |= regMask(1) << uint(r.num)
  2503  		}
  2504  		if len(a) == 2 {
  2505  			if t, ok := e.s.f.getHome(a[0].ID).(*Register); ok {
  2506  				e.uniqueRegs &^= regMask(1) << uint(t.num)
  2507  			}
  2508  		}
  2509  		if e.s.values[vid].rematerializeable {
  2510  			e.rematerializeableRegs |= regMask(1) << uint(r.num)
  2511  		}
  2512  	}
  2513  	if e.s.f.pass.debug > regDebug {
  2514  		fmt.Printf("%s\n", c.LongString())
  2515  		fmt.Printf("v%d now available in %s:%s\n", vid, loc, c)
  2516  	}
  2517  }
  2518  
  2519  // erase removes any user of loc.
  2520  func (e *edgeState) erase(loc Location) {
  2521  	cr := e.contents[loc]
  2522  	if cr.c == nil {
  2523  		return
  2524  	}
  2525  	vid := cr.vid
  2526  
  2527  	if cr.final {
  2528  		// Add a destination to move this value back into place.
  2529  		// Make sure it gets added to the tail of the destination queue
  2530  		// so we make progress on other moves first.
  2531  		e.extra = append(e.extra, dstRecord{loc, cr.vid, nil, cr.pos})
  2532  	}
  2533  
  2534  	// Remove c from the list of cached values.
  2535  	a := e.cache[vid]
  2536  	for i, c := range a {
  2537  		if e.s.f.getHome(c.ID) == loc {
  2538  			if e.s.f.pass.debug > regDebug {
  2539  				fmt.Printf("v%d no longer available in %s:%s\n", vid, loc, c)
  2540  			}
  2541  			a[i], a = a[len(a)-1], a[:len(a)-1]
  2542  			break
  2543  		}
  2544  	}
  2545  	e.cache[vid] = a
  2546  
  2547  	// Update register masks.
  2548  	if r, ok := loc.(*Register); ok {
  2549  		e.usedRegs &^= regMask(1) << uint(r.num)
  2550  		if cr.final {
  2551  			e.finalRegs &^= regMask(1) << uint(r.num)
  2552  		}
  2553  		e.rematerializeableRegs &^= regMask(1) << uint(r.num)
  2554  	}
  2555  	if len(a) == 1 {
  2556  		if r, ok := e.s.f.getHome(a[0].ID).(*Register); ok {
  2557  			e.uniqueRegs |= regMask(1) << uint(r.num)
  2558  		}
  2559  	}
  2560  }
  2561  
  2562  // findRegFor finds a register we can use to make a temp copy of type typ.
  2563  func (e *edgeState) findRegFor(typ *types.Type) Location {
  2564  	// Which registers are possibilities.
  2565  	types := &e.s.f.Config.Types
  2566  	m := e.s.compatRegs(typ)
  2567  
  2568  	// Pick a register. In priority order:
  2569  	// 1) an unused register
  2570  	// 2) a non-unique register not holding a final value
  2571  	// 3) a non-unique register
  2572  	// 4) a register holding a rematerializeable value
  2573  	x := m &^ e.usedRegs
  2574  	if x != 0 {
  2575  		return &e.s.registers[pickReg(x)]
  2576  	}
  2577  	x = m &^ e.uniqueRegs &^ e.finalRegs
  2578  	if x != 0 {
  2579  		return &e.s.registers[pickReg(x)]
  2580  	}
  2581  	x = m &^ e.uniqueRegs
  2582  	if x != 0 {
  2583  		return &e.s.registers[pickReg(x)]
  2584  	}
  2585  	x = m & e.rematerializeableRegs
  2586  	if x != 0 {
  2587  		return &e.s.registers[pickReg(x)]
  2588  	}
  2589  
  2590  	// No register is available.
  2591  	// Pick a register to spill.
  2592  	for _, vid := range e.cachedVals {
  2593  		a := e.cache[vid]
  2594  		for _, c := range a {
  2595  			if r, ok := e.s.f.getHome(c.ID).(*Register); ok && m>>uint(r.num)&1 != 0 {
  2596  				if !c.rematerializeable() {
  2597  					x := e.p.NewValue1(c.Pos, OpStoreReg, c.Type, c)
  2598  					// Allocate a temp location to spill a register to.
  2599  					// The type of the slot is immaterial - it will not be live across
  2600  					// any safepoint. Just use a type big enough to hold any register.
  2601  					t := LocalSlot{N: e.s.f.NewLocal(c.Pos, types.Int64), Type: types.Int64}
  2602  					// TODO: reuse these slots. They'll need to be erased first.
  2603  					e.set(t, vid, x, false, c.Pos)
  2604  					if e.s.f.pass.debug > regDebug {
  2605  						fmt.Printf("  SPILL %s->%s %s\n", r, t, x.LongString())
  2606  					}
  2607  				}
  2608  				// r will now be overwritten by the caller. At some point
  2609  				// later, the newly saved value will be moved back to its
  2610  				// final destination in processDest.
  2611  				return r
  2612  			}
  2613  		}
  2614  	}
  2615  
  2616  	fmt.Printf("m:%d unique:%d final:%d rematerializable:%d\n", m, e.uniqueRegs, e.finalRegs, e.rematerializeableRegs)
  2617  	for _, vid := range e.cachedVals {
  2618  		a := e.cache[vid]
  2619  		for _, c := range a {
  2620  			fmt.Printf("v%d: %s %s\n", vid, c, e.s.f.getHome(c.ID))
  2621  		}
  2622  	}
  2623  	e.s.f.Fatalf("can't find empty register on edge %s->%s", e.p, e.b)
  2624  	return nil
  2625  }
  2626  
  2627  // rematerializeable reports whether the register allocator should recompute
  2628  // a value instead of spilling/restoring it.
  2629  func (v *Value) rematerializeable() bool {
  2630  	if !opcodeTable[v.Op].rematerializeable {
  2631  		return false
  2632  	}
  2633  	for _, a := range v.Args {
  2634  		// SP and SB (generated by OpSP and OpSB) are always available.
  2635  		if a.Op != OpSP && a.Op != OpSB {
  2636  			return false
  2637  		}
  2638  	}
  2639  	return true
  2640  }
  2641  
  2642  type liveInfo struct {
  2643  	ID   ID       // ID of value
  2644  	dist int32    // # of instructions before next use
  2645  	pos  src.XPos // source position of next use
  2646  }
  2647  
  2648  // computeLive computes a map from block ID to a list of value IDs live at the end
  2649  // of that block. Together with the value ID is a count of how many instructions
  2650  // to the next use of that value. The resulting map is stored in s.live.
  2651  // computeLive also computes the desired register information at the end of each block.
  2652  // This desired register information is stored in s.desired.
  2653  // TODO: this could be quadratic if lots of variables are live across lots of
  2654  // basic blocks. Figure out a way to make this function (or, more precisely, the user
  2655  // of this function) require only linear size & time.
  2656  func (s *regAllocState) computeLive() {
  2657  	f := s.f
  2658  	s.live = make([][]liveInfo, f.NumBlocks())
  2659  	s.desired = make([]desiredState, f.NumBlocks())
  2660  	var phis []*Value
  2661  
  2662  	live := f.newSparseMapPos(f.NumValues())
  2663  	defer f.retSparseMapPos(live)
  2664  	t := f.newSparseMapPos(f.NumValues())
  2665  	defer f.retSparseMapPos(t)
  2666  
  2667  	// Keep track of which value we want in each register.
  2668  	var desired desiredState
  2669  
  2670  	// Instead of iterating over f.Blocks, iterate over their postordering.
  2671  	// Liveness information flows backward, so starting at the end
  2672  	// increases the probability that we will stabilize quickly.
  2673  	// TODO: Do a better job yet. Here's one possibility:
  2674  	// Calculate the dominator tree and locate all strongly connected components.
  2675  	// If a value is live in one block of an SCC, it is live in all.
  2676  	// Walk the dominator tree from end to beginning, just once, treating SCC
  2677  	// components as single blocks, duplicated calculated liveness information
  2678  	// out to all of them.
  2679  	po := f.postorder()
  2680  	s.loopnest = f.loopnest()
  2681  	s.loopnest.calculateDepths()
  2682  	for {
  2683  		changed := false
  2684  
  2685  		for _, b := range po {
  2686  			// Start with known live values at the end of the block.
  2687  			// Add len(b.Values) to adjust from end-of-block distance
  2688  			// to beginning-of-block distance.
  2689  			live.clear()
  2690  			for _, e := range s.live[b.ID] {
  2691  				live.set(e.ID, e.dist+int32(len(b.Values)), e.pos)
  2692  			}
  2693  
  2694  			// Mark control values as live
  2695  			for _, c := range b.ControlValues() {
  2696  				if s.values[c.ID].needReg {
  2697  					live.set(c.ID, int32(len(b.Values)), b.Pos)
  2698  				}
  2699  			}
  2700  
  2701  			// Propagate backwards to the start of the block
  2702  			// Assumes Values have been scheduled.
  2703  			phis = phis[:0]
  2704  			for i := len(b.Values) - 1; i >= 0; i-- {
  2705  				v := b.Values[i]
  2706  				live.remove(v.ID)
  2707  				if v.Op == OpPhi {
  2708  					// save phi ops for later
  2709  					phis = append(phis, v)
  2710  					continue
  2711  				}
  2712  				if opcodeTable[v.Op].call {
  2713  					c := live.contents()
  2714  					for i := range c {
  2715  						c[i].val += unlikelyDistance
  2716  					}
  2717  				}
  2718  				for _, a := range v.Args {
  2719  					if s.values[a.ID].needReg {
  2720  						live.set(a.ID, int32(i), v.Pos)
  2721  					}
  2722  				}
  2723  			}
  2724  			// Propagate desired registers backwards.
  2725  			desired.copy(&s.desired[b.ID])
  2726  			for i := len(b.Values) - 1; i >= 0; i-- {
  2727  				v := b.Values[i]
  2728  				prefs := desired.remove(v.ID)
  2729  				if v.Op == OpPhi {
  2730  					// TODO: if v is a phi, save desired register for phi inputs.
  2731  					// For now, we just drop it and don't propagate
  2732  					// desired registers back though phi nodes.
  2733  					continue
  2734  				}
  2735  				regspec := s.regspec(v)
  2736  				// Cancel desired registers if they get clobbered.
  2737  				desired.clobber(regspec.clobbers)
  2738  				// Update desired registers if there are any fixed register inputs.
  2739  				for _, j := range regspec.inputs {
  2740  					if countRegs(j.regs) != 1 {
  2741  						continue
  2742  					}
  2743  					desired.clobber(j.regs)
  2744  					desired.add(v.Args[j.idx].ID, pickReg(j.regs))
  2745  				}
  2746  				// Set desired register of input 0 if this is a 2-operand instruction.
  2747  				if opcodeTable[v.Op].resultInArg0 || v.Op == OpAMD64ADDQconst || v.Op == OpAMD64ADDLconst || v.Op == OpSelect0 {
  2748  					// ADDQconst is added here because we want to treat it as resultInArg0 for
  2749  					// the purposes of desired registers, even though it is not an absolute requirement.
  2750  					// This is because we'd rather implement it as ADDQ instead of LEAQ.
  2751  					// Same for ADDLconst
  2752  					// Select0 is added here to propagate the desired register to the tuple-generating instruction.
  2753  					if opcodeTable[v.Op].commutative {
  2754  						desired.addList(v.Args[1].ID, prefs)
  2755  					}
  2756  					desired.addList(v.Args[0].ID, prefs)
  2757  				}
  2758  			}
  2759  
  2760  			// For each predecessor of b, expand its list of live-at-end values.
  2761  			// invariant: live contains the values live at the start of b (excluding phi inputs)
  2762  			for i, e := range b.Preds {
  2763  				p := e.b
  2764  				// Compute additional distance for the edge.
  2765  				// Note: delta must be at least 1 to distinguish the control
  2766  				// value use from the first user in a successor block.
  2767  				delta := int32(normalDistance)
  2768  				if len(p.Succs) == 2 {
  2769  					if p.Succs[0].b == b && p.Likely == BranchLikely ||
  2770  						p.Succs[1].b == b && p.Likely == BranchUnlikely {
  2771  						delta = likelyDistance
  2772  					}
  2773  					if p.Succs[0].b == b && p.Likely == BranchUnlikely ||
  2774  						p.Succs[1].b == b && p.Likely == BranchLikely {
  2775  						delta = unlikelyDistance
  2776  					}
  2777  				}
  2778  
  2779  				// Update any desired registers at the end of p.
  2780  				s.desired[p.ID].merge(&desired)
  2781  
  2782  				// Start t off with the previously known live values at the end of p.
  2783  				t.clear()
  2784  				for _, e := range s.live[p.ID] {
  2785  					t.set(e.ID, e.dist, e.pos)
  2786  				}
  2787  				update := false
  2788  
  2789  				// Add new live values from scanning this block.
  2790  				for _, e := range live.contents() {
  2791  					d := e.val + delta
  2792  					if !t.contains(e.key) || d < t.get(e.key) {
  2793  						update = true
  2794  						t.set(e.key, d, e.pos)
  2795  					}
  2796  				}
  2797  				// Also add the correct arg from the saved phi values.
  2798  				// All phis are at distance delta (we consider them
  2799  				// simultaneously happening at the start of the block).
  2800  				for _, v := range phis {
  2801  					id := v.Args[i].ID
  2802  					if s.values[id].needReg && (!t.contains(id) || delta < t.get(id)) {
  2803  						update = true
  2804  						t.set(id, delta, v.Pos)
  2805  					}
  2806  				}
  2807  
  2808  				if !update {
  2809  					continue
  2810  				}
  2811  				// The live set has changed, update it.
  2812  				l := s.live[p.ID][:0]
  2813  				if cap(l) < t.size() {
  2814  					l = make([]liveInfo, 0, t.size())
  2815  				}
  2816  				for _, e := range t.contents() {
  2817  					l = append(l, liveInfo{e.key, e.val, e.pos})
  2818  				}
  2819  				s.live[p.ID] = l
  2820  				changed = true
  2821  			}
  2822  		}
  2823  
  2824  		if !changed {
  2825  			break
  2826  		}
  2827  	}
  2828  	if f.pass.debug > regDebug {
  2829  		fmt.Println("live values at end of each block")
  2830  		for _, b := range f.Blocks {
  2831  			fmt.Printf("  %s:", b)
  2832  			for _, x := range s.live[b.ID] {
  2833  				fmt.Printf(" v%d(%d)", x.ID, x.dist)
  2834  				for _, e := range s.desired[b.ID].entries {
  2835  					if e.ID != x.ID {
  2836  						continue
  2837  					}
  2838  					fmt.Printf("[")
  2839  					first := true
  2840  					for _, r := range e.regs {
  2841  						if r == noRegister {
  2842  							continue
  2843  						}
  2844  						if !first {
  2845  							fmt.Printf(",")
  2846  						}
  2847  						fmt.Print(&s.registers[r])
  2848  						first = false
  2849  					}
  2850  					fmt.Printf("]")
  2851  				}
  2852  			}
  2853  			if avoid := s.desired[b.ID].avoid; avoid != 0 {
  2854  				fmt.Printf(" avoid=%v", s.RegMaskString(avoid))
  2855  			}
  2856  			fmt.Println()
  2857  		}
  2858  	}
  2859  }
  2860  
  2861  // A desiredState represents desired register assignments.
  2862  type desiredState struct {
  2863  	// Desired assignments will be small, so we just use a list
  2864  	// of valueID+registers entries.
  2865  	entries []desiredStateEntry
  2866  	// Registers that other values want to be in.  This value will
  2867  	// contain at least the union of the regs fields of entries, but
  2868  	// may contain additional entries for values that were once in
  2869  	// this data structure but are no longer.
  2870  	avoid regMask
  2871  }
  2872  type desiredStateEntry struct {
  2873  	// (pre-regalloc) value
  2874  	ID ID
  2875  	// Registers it would like to be in, in priority order.
  2876  	// Unused slots are filled with noRegister.
  2877  	// For opcodes that return tuples, we track desired registers only
  2878  	// for the first element of the tuple.
  2879  	regs [4]register
  2880  }
  2881  
  2882  func (d *desiredState) clear() {
  2883  	d.entries = d.entries[:0]
  2884  	d.avoid = 0
  2885  }
  2886  
  2887  // get returns a list of desired registers for value vid.
  2888  func (d *desiredState) get(vid ID) [4]register {
  2889  	for _, e := range d.entries {
  2890  		if e.ID == vid {
  2891  			return e.regs
  2892  		}
  2893  	}
  2894  	return [4]register{noRegister, noRegister, noRegister, noRegister}
  2895  }
  2896  
  2897  // add records that we'd like value vid to be in register r.
  2898  func (d *desiredState) add(vid ID, r register) {
  2899  	d.avoid |= regMask(1) << r
  2900  	for i := range d.entries {
  2901  		e := &d.entries[i]
  2902  		if e.ID != vid {
  2903  			continue
  2904  		}
  2905  		if e.regs[0] == r {
  2906  			// Already known and highest priority
  2907  			return
  2908  		}
  2909  		for j := 1; j < len(e.regs); j++ {
  2910  			if e.regs[j] == r {
  2911  				// Move from lower priority to top priority
  2912  				copy(e.regs[1:], e.regs[:j])
  2913  				e.regs[0] = r
  2914  				return
  2915  			}
  2916  		}
  2917  		copy(e.regs[1:], e.regs[:])
  2918  		e.regs[0] = r
  2919  		return
  2920  	}
  2921  	d.entries = append(d.entries, desiredStateEntry{vid, [4]register{r, noRegister, noRegister, noRegister}})
  2922  }
  2923  
  2924  func (d *desiredState) addList(vid ID, regs [4]register) {
  2925  	// regs is in priority order, so iterate in reverse order.
  2926  	for i := len(regs) - 1; i >= 0; i-- {
  2927  		r := regs[i]
  2928  		if r != noRegister {
  2929  			d.add(vid, r)
  2930  		}
  2931  	}
  2932  }
  2933  
  2934  // clobber erases any desired registers in the set m.
  2935  func (d *desiredState) clobber(m regMask) {
  2936  	for i := 0; i < len(d.entries); {
  2937  		e := &d.entries[i]
  2938  		j := 0
  2939  		for _, r := range e.regs {
  2940  			if r != noRegister && m>>r&1 == 0 {
  2941  				e.regs[j] = r
  2942  				j++
  2943  			}
  2944  		}
  2945  		if j == 0 {
  2946  			// No more desired registers for this value.
  2947  			d.entries[i] = d.entries[len(d.entries)-1]
  2948  			d.entries = d.entries[:len(d.entries)-1]
  2949  			continue
  2950  		}
  2951  		for ; j < len(e.regs); j++ {
  2952  			e.regs[j] = noRegister
  2953  		}
  2954  		i++
  2955  	}
  2956  	d.avoid &^= m
  2957  }
  2958  
  2959  // copy copies a desired state from another desiredState x.
  2960  func (d *desiredState) copy(x *desiredState) {
  2961  	d.entries = append(d.entries[:0], x.entries...)
  2962  	d.avoid = x.avoid
  2963  }
  2964  
  2965  // remove removes the desired registers for vid and returns them.
  2966  func (d *desiredState) remove(vid ID) [4]register {
  2967  	for i := range d.entries {
  2968  		if d.entries[i].ID == vid {
  2969  			regs := d.entries[i].regs
  2970  			d.entries[i] = d.entries[len(d.entries)-1]
  2971  			d.entries = d.entries[:len(d.entries)-1]
  2972  			return regs
  2973  		}
  2974  	}
  2975  	return [4]register{noRegister, noRegister, noRegister, noRegister}
  2976  }
  2977  
  2978  // merge merges another desired state x into d.
  2979  func (d *desiredState) merge(x *desiredState) {
  2980  	d.avoid |= x.avoid
  2981  	// There should only be a few desired registers, so
  2982  	// linear insert is ok.
  2983  	for _, e := range x.entries {
  2984  		d.addList(e.ID, e.regs)
  2985  	}
  2986  }
  2987  

View as plain text