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  	"cmp"
   123  	"fmt"
   124  	"internal/buildcfg"
   125  	"math"
   126  	"math/bits"
   127  	"slices"
   128  	"unsafe"
   129  )
   130  
   131  const (
   132  	moveSpills = iota
   133  	logSpills
   134  	regDebug
   135  	stackDebug
   136  )
   137  
   138  // distance is a measure of how far into the future values are used.
   139  // distance is measured in units of instructions.
   140  const (
   141  	likelyDistance   = 1
   142  	normalDistance   = 10
   143  	unlikelyDistance = 100
   144  )
   145  
   146  // regalloc performs register allocation on f. It sets f.RegAlloc
   147  // to the resulting allocation.
   148  func regalloc(f *Func) {
   149  	var s regAllocState
   150  	s.init(f)
   151  	s.regalloc(f)
   152  	s.close()
   153  }
   154  
   155  type register uint8
   156  
   157  const noRegister register = 255
   158  
   159  // For bulk initializing
   160  var noRegisters [32]register = [32]register{
   161  	noRegister, noRegister, noRegister, noRegister, noRegister, noRegister, noRegister, noRegister,
   162  	noRegister, noRegister, noRegister, noRegister, noRegister, noRegister, noRegister, noRegister,
   163  	noRegister, noRegister, noRegister, noRegister, noRegister, noRegister, noRegister, noRegister,
   164  	noRegister, noRegister, noRegister, noRegister, noRegister, noRegister, noRegister, noRegister,
   165  }
   166  
   167  // A regMask encodes a set of machine registers.
   168  type regMask struct {
   169  	v1, v2 uint64
   170  }
   171  
   172  func (r regMask) intersect(s regMask) regMask {
   173  	return regMask{r.v1 & s.v1, r.v2 & s.v2}
   174  }
   175  
   176  func (r regMask) union(s regMask) regMask {
   177  	return regMask{r.v1 | s.v1, r.v2 | s.v2}
   178  }
   179  
   180  func (r regMask) minus(s regMask) regMask {
   181  	return regMask{r.v1 &^ s.v1, r.v2 &^ s.v2}
   182  }
   183  
   184  func (r regMask) empty() bool {
   185  	return r.v1 == 0 && r.v2 == 0
   186  }
   187  
   188  func (r regMask) pickReg() register {
   189  	if r.empty() {
   190  		panic("can't pick a register from an empty set")
   191  	}
   192  	// pick the lowest one
   193  	if r.v1 != 0 {
   194  		return register(bits.TrailingZeros64(r.v1))
   195  	}
   196  	return register(bits.TrailingZeros64(r.v2) + 64)
   197  }
   198  
   199  func regMaskAt(i register) regMask {
   200  	if i < 64 {
   201  		return regMask{v1: 1 << i}
   202  	}
   203  	return regMask{v2: 1 << (i - 64)}
   204  }
   205  
   206  func (r regMask) addReg(i register) regMask {
   207  	if i < 64 {
   208  		return regMask{r.v1 | 1<<i, r.v2}
   209  	}
   210  	return regMask{r.v1, r.v2 | 1<<(i-64)}
   211  }
   212  
   213  func (r regMask) removeReg(i register) regMask {
   214  	if i < 64 {
   215  		return regMask{r.v1 &^ (1 << i), r.v2}
   216  	}
   217  	return regMask{r.v1, r.v2 &^ (1 << (i - 64))}
   218  }
   219  
   220  func (r regMask) hasReg(i register) bool {
   221  	if i < 64 {
   222  		return (r.v1>>i)&1 != 0
   223  	}
   224  	return (r.v2>>(i-64))&1 != 0
   225  }
   226  
   227  func (m regMask) String() string {
   228  	s := ""
   229  	for r := register(0); !m.empty(); r++ {
   230  		if !m.hasReg(r) {
   231  			continue
   232  		}
   233  		m = m.removeReg(r)
   234  		if s != "" {
   235  			s += " "
   236  		}
   237  		s += fmt.Sprintf("r%d", r)
   238  	}
   239  	return s
   240  }
   241  
   242  func (s *regAllocState) RegMaskString(m regMask) string {
   243  	str := ""
   244  	for r := register(0); !m.empty(); r++ {
   245  		if !m.hasReg(r) {
   246  			continue
   247  		}
   248  		m = m.removeReg(r)
   249  		if str != "" {
   250  			str += " "
   251  		}
   252  		str += s.registers[r].String()
   253  	}
   254  	return str
   255  }
   256  
   257  // countRegs returns the number of set bits in the register mask.
   258  func countRegs(r regMask) int {
   259  	return bits.OnesCount64(r.v1) + bits.OnesCount64(r.v2)
   260  }
   261  
   262  // pickReg picks a register from the register mask.
   263  func (s *regAllocState) pickReg(rm regMask) register {
   264  	if s.f.Config.ctxt.Arch.Arch == sys.ArchRISCV64 {
   265  		// Prefer x8-x15 and f8-f15 to enable increased use of compressed instructions.
   266  		riscv64CompressedMask := rm.intersect(regMask{v1: 0x0000ff000000ff00})
   267  		if !riscv64CompressedMask.empty() {
   268  			rm = riscv64CompressedMask
   269  		}
   270  	}
   271  	return rm.pickReg()
   272  }
   273  
   274  type use struct {
   275  	// distance from start of the block to a use of a value
   276  	//   dist == 0                 used by first instruction in block
   277  	//   dist == len(b.Values)-1   used by last instruction in block
   278  	//   dist == len(b.Values)     used by block's control value
   279  	//   dist  > len(b.Values)     used by a subsequent block
   280  	dist int32
   281  	pos  src.XPos // source position of the use
   282  	next *use     // linked list of uses of a value in nondecreasing dist order
   283  }
   284  
   285  // A valState records the register allocation state for a (pre-regalloc) value.
   286  type valState struct {
   287  	regs              regMask // the set of registers holding a Value (usually just one)
   288  	uses              *use    // list of uses in this block
   289  	spill             *Value  // spilled copy of the Value (if any)
   290  	restoreMin        int32   // minimum of all restores' blocks' sdom.entry
   291  	restoreMax        int32   // maximum of all restores' blocks' sdom.exit
   292  	needReg           bool    // cached value of !v.Type.IsMemory() && !v.Type.IsVoid() && !.v.Type.IsFlags()
   293  	rematerializeable bool    // cached value of v.rematerializeable()
   294  }
   295  
   296  type regState struct {
   297  	v *Value // Original (preregalloc) Value stored in this register.
   298  	c *Value // A Value equal to v which is currently in a register.  Might be v or a copy of it.
   299  	// If a register is unused, v==c==nil
   300  }
   301  
   302  type regAllocState struct {
   303  	f *Func
   304  
   305  	sdom        SparseTree
   306  	registers   []Register
   307  	numRegs     register
   308  	SPReg       register
   309  	SBReg       register
   310  	GReg        register
   311  	ZeroIntReg  register
   312  	allocatable regMask
   313  
   314  	// live values at the end of each block.  live[b.ID] is a list of value IDs
   315  	// which are live at the end of b, together with a count of how many instructions
   316  	// forward to the next use.
   317  	live [][]liveInfo
   318  	// desired register assignments at the end of each block.
   319  	// Note that this is a static map computed before allocation occurs. Dynamic
   320  	// register desires (from partially completed allocations) will trump
   321  	// this information.
   322  	desired []desiredState
   323  
   324  	// current state of each (preregalloc) Value
   325  	values []valState
   326  
   327  	// ID of SP, SB values
   328  	sp, sb ID
   329  
   330  	// For each Value, map from its value ID back to the
   331  	// preregalloc Value it was derived from.
   332  	orig []*Value
   333  
   334  	// current state of each register.
   335  	// Includes only registers in allocatable.
   336  	regs []regState
   337  
   338  	// registers that contain values which can't be kicked out
   339  	nospill regMask
   340  
   341  	// mask of registers currently in use
   342  	used regMask
   343  
   344  	// mask of registers used since the start of the current block
   345  	usedSinceBlockStart regMask
   346  
   347  	// mask of registers used in the current instruction
   348  	tmpused regMask
   349  
   350  	// current block we're working on
   351  	curBlock *Block
   352  
   353  	// cache of use records
   354  	freeUseRecords *use
   355  
   356  	// endRegs[blockid] is the register state at the end of each block.
   357  	// encoded as a set of endReg records.
   358  	endRegs [][]endReg
   359  
   360  	// startRegs[blockid] is the register state at the start of merge blocks.
   361  	// saved state does not include the state of phi ops in the block.
   362  	startRegs [][]startReg
   363  
   364  	// startRegsMask is a mask of the registers in startRegs[curBlock.ID].
   365  	// Registers dropped from startRegsMask are later synchronoized back to
   366  	// startRegs by dropping from there as well.
   367  	startRegsMask regMask
   368  
   369  	// spillLive[blockid] is the set of live spills at the end of each block
   370  	spillLive [][]ID
   371  
   372  	// a set of copies we generated to move things around, and
   373  	// whether it is used in shuffle. Unused copies will be deleted.
   374  	copies map[*Value]bool
   375  
   376  	loopnest *loopnest
   377  
   378  	// choose a good order in which to visit blocks for allocation purposes.
   379  	visitOrder []*Block
   380  
   381  	// blockOrder[b.ID] corresponds to the index of block b in visitOrder.
   382  	blockOrder []int32
   383  
   384  	// whether to insert instructions that clobber dead registers at call sites
   385  	doClobber bool
   386  
   387  	// For each instruction index in a basic block, the index of the next call
   388  	// at or after that instruction index.
   389  	// If there is no next call, returns maxInt32.
   390  	// nextCall for a call instruction points to itself.
   391  	// (Indexes and results are pre-regalloc.)
   392  	nextCall []int32
   393  
   394  	// Index of the instruction we're currently working on.
   395  	// Index is expressed in terms of the pre-regalloc b.Values list.
   396  	curIdx int
   397  }
   398  
   399  type endReg struct {
   400  	r register
   401  	v *Value // pre-regalloc value held in this register (TODO: can we use ID here?)
   402  	c *Value // cached version of the value
   403  }
   404  
   405  type startReg struct {
   406  	r   register
   407  	v   *Value   // pre-regalloc value needed in this register
   408  	c   *Value   // cached version of the value
   409  	pos src.XPos // source position of use of this register
   410  }
   411  
   412  // freeReg frees up register r. Any current user of r is kicked out.
   413  func (s *regAllocState) freeReg(r register) {
   414  	if !s.allocatable.hasReg(r) && !s.isGReg(r) {
   415  		return
   416  	}
   417  	v := s.regs[r].v
   418  	if v == nil {
   419  		s.f.Fatalf("tried to free an already free register %d\n", r)
   420  	}
   421  
   422  	// Mark r as unused.
   423  	if s.f.pass.debug > regDebug {
   424  		fmt.Printf("freeReg %s (dump %s/%s)\n", &s.registers[r], v, s.regs[r].c)
   425  	}
   426  	s.regs[r] = regState{}
   427  	s.values[v.ID].regs = s.values[v.ID].regs.removeReg(r)
   428  	s.used = s.used.removeReg(r)
   429  }
   430  
   431  // freeRegs frees up all registers listed in m.
   432  func (s *regAllocState) freeRegs(m regMask) {
   433  	for !m.intersect(s.used).empty() {
   434  		s.freeReg(s.pickReg(m.intersect(s.used)))
   435  	}
   436  }
   437  
   438  // clobberRegs inserts instructions that clobber registers listed in m.
   439  func (s *regAllocState) clobberRegs(m regMask) {
   440  	m = m.intersect(s.allocatable.intersect(s.f.Config.gpRegMask)) // only integer register can contain pointers, only clobber them
   441  	for !m.empty() {
   442  		r := s.pickReg(m)
   443  		m = m.removeReg(r)
   444  		x := s.curBlock.NewValue0(src.NoXPos, OpClobberReg, types.TypeVoid)
   445  		s.f.setHome(x, &s.registers[r])
   446  	}
   447  }
   448  
   449  // setOrig records that c's original value is the same as
   450  // v's original value.
   451  func (s *regAllocState) setOrig(c *Value, v *Value) {
   452  	if int(c.ID) >= cap(s.orig) {
   453  		x := s.f.Cache.allocValueSlice(int(c.ID) + 1)
   454  		copy(x, s.orig)
   455  		s.f.Cache.freeValueSlice(s.orig)
   456  		s.orig = x
   457  	}
   458  	for int(c.ID) >= len(s.orig) {
   459  		s.orig = append(s.orig, nil)
   460  	}
   461  	if s.orig[c.ID] != nil {
   462  		s.f.Fatalf("orig value set twice %s %s", c, v)
   463  	}
   464  	s.orig[c.ID] = s.orig[v.ID]
   465  }
   466  
   467  // assignReg assigns register r to hold c, a copy of v.
   468  // r must be unused.
   469  func (s *regAllocState) assignReg(r register, v *Value, c *Value) {
   470  	if s.f.pass.debug > regDebug {
   471  		fmt.Printf("assignReg %s %s/%s\n", &s.registers[r], v, c)
   472  	}
   473  	// Allocate v to r.
   474  	s.values[v.ID].regs = s.values[v.ID].regs.addReg(r)
   475  	s.f.setHome(c, &s.registers[r])
   476  
   477  	// Allocate r to v.
   478  	if !s.allocatable.hasReg(r) && !s.isGReg(r) {
   479  		return
   480  	}
   481  	if s.regs[r].v != nil {
   482  		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)
   483  	}
   484  	s.regs[r] = regState{v, c}
   485  	s.used = s.used.addReg(r)
   486  }
   487  
   488  // allocReg chooses a register from the set of registers in mask.
   489  // If there is no unused register, a Value will be kicked out of
   490  // a register to make room.
   491  func (s *regAllocState) allocReg(mask regMask, v *Value) register {
   492  	if v.OnWasmStack {
   493  		return noRegister
   494  	}
   495  
   496  	mask = mask.intersect(s.allocatable)
   497  	mask = mask.minus(s.nospill)
   498  	if mask.empty() {
   499  		s.f.Fatalf("no register available for %s", v.LongString())
   500  	}
   501  
   502  	// Pick an unused register if one is available.
   503  	if !mask.minus(s.used).empty() {
   504  		r := s.pickReg(mask.minus(s.used))
   505  		s.usedSinceBlockStart = s.usedSinceBlockStart.addReg(r)
   506  		return r
   507  	}
   508  
   509  	// Pick a value to spill. Spill the value with the
   510  	// farthest-in-the-future use.
   511  	// TODO: Prefer registers with already spilled Values?
   512  	// TODO: Modify preference using affinity graph.
   513  	// TODO: if a single value is in multiple registers, spill one of them
   514  	// before spilling a value in just a single register.
   515  
   516  	// Find a register to spill. We spill the register containing the value
   517  	// whose next use is as far in the future as possible.
   518  	// https://en.wikipedia.org/wiki/Page_replacement_algorithm#The_theoretically_optimal_page_replacement_algorithm
   519  	var r register
   520  	maxuse := int32(-1)
   521  	for t := register(0); t < s.numRegs; t++ {
   522  		if !mask.hasReg(t) {
   523  			continue
   524  		}
   525  		v := s.regs[t].v
   526  		if n := s.values[v.ID].uses.dist; n > maxuse {
   527  			// v's next use is farther in the future than any value
   528  			// we've seen so far. A new best spill candidate.
   529  			r = t
   530  			maxuse = n
   531  		}
   532  	}
   533  	if maxuse == -1 {
   534  		s.f.Fatalf("couldn't find register to spill")
   535  	}
   536  
   537  	if s.f.Config.ctxt.Arch.Arch == sys.ArchWasm {
   538  		// TODO(neelance): In theory this should never happen, because all wasm registers are equal.
   539  		// So if there is still a free register, the allocation should have picked that one in the first place instead of
   540  		// trying to kick some other value out. In practice, this case does happen and it breaks the stack optimization.
   541  		s.freeReg(r)
   542  		return r
   543  	}
   544  
   545  	// Try to move it around before kicking out, if there is a free register.
   546  	// We generate a Copy and record it. It will be deleted if never used.
   547  	v2 := s.regs[r].v
   548  	m := s.compatRegs(v2.Type).minus(s.used).minus(s.tmpused).removeReg(r)
   549  	if !m.empty() && !s.values[v2.ID].rematerializeable && countRegs(s.values[v2.ID].regs) == 1 {
   550  		s.usedSinceBlockStart = s.usedSinceBlockStart.addReg(r)
   551  		r2 := s.pickReg(m)
   552  		c := s.curBlock.NewValue1(v2.Pos, OpCopy, v2.Type, s.regs[r].c)
   553  		s.copies[c] = false
   554  		if s.f.pass.debug > regDebug {
   555  			fmt.Printf("copy %s to %s : %s\n", v2, c, &s.registers[r2])
   556  		}
   557  		s.setOrig(c, v2)
   558  		s.assignReg(r2, v2, c)
   559  	}
   560  
   561  	// If the evicted register isn't used between the start of the block
   562  	// and now then there is no reason to even request it on entry. We can
   563  	// drop from startRegs in that case.
   564  	if !s.usedSinceBlockStart.hasReg(r) {
   565  		if s.startRegsMask.hasReg(r) {
   566  			if s.f.pass.debug > regDebug {
   567  				fmt.Printf("dropped from startRegs: %s\n", &s.registers[r])
   568  			}
   569  			s.startRegsMask = s.startRegsMask.removeReg(r)
   570  		}
   571  	}
   572  
   573  	s.freeReg(r)
   574  	s.usedSinceBlockStart = s.usedSinceBlockStart.addReg(r)
   575  	return r
   576  }
   577  
   578  // makeSpill returns a Value which represents the spilled value of v.
   579  // b is the block in which the spill is used.
   580  func (s *regAllocState) makeSpill(v *Value, b *Block) *Value {
   581  	vi := &s.values[v.ID]
   582  	if vi.spill != nil {
   583  		// Final block not known - keep track of subtree where restores reside.
   584  		vi.restoreMin = min(vi.restoreMin, s.sdom[b.ID].entry)
   585  		vi.restoreMax = max(vi.restoreMax, s.sdom[b.ID].exit)
   586  		return vi.spill
   587  	}
   588  	// Make a spill for v. We don't know where we want
   589  	// to put it yet, so we leave it blockless for now.
   590  	spill := s.f.newValueNoBlock(OpStoreReg, v.Type, v.Pos)
   591  	// We also don't know what the spill's arg will be.
   592  	// Leave it argless for now.
   593  	s.setOrig(spill, v)
   594  	vi.spill = spill
   595  	vi.restoreMin = s.sdom[b.ID].entry
   596  	vi.restoreMax = s.sdom[b.ID].exit
   597  	return spill
   598  }
   599  
   600  // allocValToReg allocates v to a register selected from regMask and
   601  // returns the register copy of v. Any previous user is kicked out and spilled
   602  // (if necessary). Load code is added at the current pc. If nospill is set the
   603  // allocated register is marked nospill so the assignment cannot be
   604  // undone until the caller allows it by clearing nospill. Returns a
   605  // *Value which is either v or a copy of v allocated to the chosen register.
   606  func (s *regAllocState) allocValToReg(v *Value, mask regMask, nospill bool, pos src.XPos) *Value {
   607  	if s.f.Config.ctxt.Arch.Arch == sys.ArchWasm && v.rematerializeable() {
   608  		c := v.copyIntoWithXPos(s.curBlock, pos)
   609  		c.OnWasmStack = true
   610  		s.setOrig(c, v)
   611  		return c
   612  	}
   613  	if v.OnWasmStack {
   614  		return v
   615  	}
   616  
   617  	vi := &s.values[v.ID]
   618  	pos = pos.WithNotStmt()
   619  	// Check if v is already in a requested register.
   620  	if !mask.intersect(vi.regs).empty() {
   621  		mask = mask.intersect(vi.regs)
   622  		r := s.pickReg(mask)
   623  		if mask.hasReg(s.SPReg) {
   624  			// Prefer the stack pointer if it is allowed.
   625  			// (Needed because the op might have an Aux symbol
   626  			// that needs SP as its base.)
   627  			r = s.SPReg
   628  		}
   629  		if !s.allocatable.hasReg(r) {
   630  			return v // v is in a fixed register
   631  		}
   632  		if s.regs[r].v != v || s.regs[r].c == nil {
   633  			panic("bad register state")
   634  		}
   635  		if nospill {
   636  			s.nospill = s.nospill.addReg(r)
   637  		}
   638  		s.usedSinceBlockStart = s.usedSinceBlockStart.addReg(r)
   639  		return s.regs[r].c
   640  	}
   641  
   642  	var r register
   643  	// If nospill is set, the value is used immediately, so it can live on the WebAssembly stack.
   644  	onWasmStack := nospill && s.f.Config.ctxt.Arch.Arch == sys.ArchWasm
   645  	if !onWasmStack {
   646  		// Allocate a register.
   647  		r = s.allocReg(mask, v)
   648  	}
   649  
   650  	// Allocate v to the new register.
   651  	var c *Value
   652  	if !vi.regs.empty() {
   653  		// Copy from a register that v is already in.
   654  		var current *Value
   655  		if !vi.regs.minus(s.allocatable).empty() {
   656  			// v is in a fixed register, prefer that
   657  			current = v
   658  		} else {
   659  			r2 := s.pickReg(vi.regs)
   660  			if s.regs[r2].v != v {
   661  				panic("bad register state")
   662  			}
   663  			current = s.regs[r2].c
   664  			s.usedSinceBlockStart = s.usedSinceBlockStart.addReg(r2)
   665  		}
   666  		c = s.curBlock.NewValue1(pos, OpCopy, v.Type, current)
   667  	} else if v.rematerializeable() {
   668  		// Rematerialize instead of loading from the spill location.
   669  		c = v.copyIntoWithXPos(s.curBlock, pos)
   670  		// We need to consider its output mask and potentially issue a Copy
   671  		// if there are register mask conflicts.
   672  		// This currently happens for the SIMD package only between GP and FP
   673  		// register. Because Intel's vector extension can put integer value into
   674  		// FP, which is seen as a vector. Example instruction: VPSLL[BWDQ]
   675  		// Because GP and FP masks do not overlap, mask & outputMask == 0
   676  		// detects this situation thoroughly.
   677  		sourceMask := s.regspec(c).outputs[0].regs
   678  		if mask.intersect(sourceMask).empty() && !onWasmStack {
   679  			s.setOrig(c, v)
   680  			s.assignReg(s.allocReg(sourceMask, v), v, c)
   681  			// v.Type for the new OpCopy is likely wrong and it might delay the problem
   682  			// until ssa to asm lowering, which might need the types to generate the right
   683  			// assembly for OpCopy. For Intel's GP to FP move, it happens to be that
   684  			// MOV instruction has such a variant so it happens to be right.
   685  			// But it's unclear for other architectures or situations, and the problem
   686  			// might be exposed when the assembler sees illegal instructions.
   687  			// Right now make we still pick v.Type, because at least its size should be correct
   688  			// for the rematerialization case the amd64 SIMD package exposed.
   689  			// TODO: We might need to figure out a way to find the correct type or make
   690  			// the asm lowering use reg info only for OpCopy.
   691  			c = s.curBlock.NewValue1(pos, OpCopy, v.Type, c)
   692  		}
   693  	} else {
   694  		// Load v from its spill location.
   695  		spill := s.makeSpill(v, s.curBlock)
   696  		if s.f.pass.debug > logSpills {
   697  			s.f.Warnl(vi.spill.Pos, "load spill for %v from %v", v, spill)
   698  		}
   699  		c = s.curBlock.NewValue1(pos, OpLoadReg, v.Type, spill)
   700  		sourceMask := s.compatRegs(v.Type)
   701  		if !sourceMask.hasReg(r) && !onWasmStack {
   702  			// Assign a temporary register that can be copied to the desired destination;
   703  			// this at least works where it is currently a problem (x86).
   704  			// This happens processing e.g. ASAN/TSAN with SIMD *simdtype methods.
   705  			s.setOrig(c, v)
   706  			s.assignReg(s.allocReg(sourceMask, v), v, c)
   707  			c = s.curBlock.NewValue1(pos, OpCopy, v.Type, c)
   708  		}
   709  	}
   710  
   711  	s.setOrig(c, v)
   712  
   713  	if onWasmStack {
   714  		c.OnWasmStack = true
   715  		return c
   716  	}
   717  
   718  	s.assignReg(r, v, c)
   719  	if c.Op == OpLoadReg && s.isGReg(r) {
   720  		s.f.Fatalf("allocValToReg.OpLoadReg targeting g: " + c.LongString())
   721  	}
   722  	if nospill {
   723  		s.nospill = s.nospill.addReg(r)
   724  	}
   725  	return c
   726  }
   727  
   728  // isLeaf reports whether f performs any calls.
   729  func isLeaf(f *Func) bool {
   730  	for _, b := range f.Blocks {
   731  		for _, v := range b.Values {
   732  			if v.Op.IsCall() && !v.Op.IsTailCall() {
   733  				// tail call is not counted as it does not save the return PC or need a frame
   734  				return false
   735  			}
   736  		}
   737  	}
   738  	return true
   739  }
   740  
   741  // needRegister reports whether v needs a register.
   742  func (v *Value) needRegister() bool {
   743  	return !v.Type.IsMemory() && !v.Type.IsVoid() && !v.Type.IsFlags() && !v.Type.IsTuple()
   744  }
   745  
   746  func (s *regAllocState) init(f *Func) {
   747  	s.f = f
   748  	s.f.RegAlloc = s.f.Cache.locs[:0]
   749  	s.registers = f.Config.registers
   750  	if nr := len(s.registers); nr == 0 || nr > int(noRegister) || nr > int(unsafe.Sizeof(regMask{})*8) {
   751  		s.f.Fatalf("bad number of registers: %d", nr)
   752  	} else {
   753  		s.numRegs = register(nr)
   754  	}
   755  	// Locate SP, SB, and g registers.
   756  	s.SPReg = noRegister
   757  	s.SBReg = noRegister
   758  	s.GReg = noRegister
   759  	s.ZeroIntReg = noRegister
   760  	for r := register(0); r < s.numRegs; r++ {
   761  		switch s.registers[r].String() {
   762  		case "SP":
   763  			s.SPReg = r
   764  		case "SB":
   765  			s.SBReg = r
   766  		case "g":
   767  			s.GReg = r
   768  		case "ZERO": // TODO: arch-specific?
   769  			s.ZeroIntReg = r
   770  		}
   771  	}
   772  	// Make sure we found all required registers.
   773  	switch noRegister {
   774  	case s.SPReg:
   775  		s.f.Fatalf("no SP register found")
   776  	case s.SBReg:
   777  		s.f.Fatalf("no SB register found")
   778  	case s.GReg:
   779  		if f.Config.hasGReg {
   780  			s.f.Fatalf("no g register found")
   781  		}
   782  	}
   783  
   784  	// Figure out which registers we're allowed to use.
   785  	s.allocatable = s.f.Config.gpRegMask.union(s.f.Config.fpRegMask).union(s.f.Config.specialRegMask).union(s.f.Config.simdRegMask)
   786  	s.allocatable = s.allocatable.removeReg(s.SPReg)
   787  	s.allocatable = s.allocatable.removeReg(s.SBReg)
   788  	if s.f.Config.hasGReg {
   789  		s.allocatable = s.allocatable.removeReg(s.GReg)
   790  	}
   791  	if s.ZeroIntReg != noRegister {
   792  		s.allocatable = s.allocatable.removeReg(s.ZeroIntReg)
   793  	}
   794  	if buildcfg.FramePointerEnabled && s.f.Config.FPReg >= 0 {
   795  		s.allocatable = s.allocatable.removeReg(register(s.f.Config.FPReg))
   796  	}
   797  	if s.f.Config.LinkReg != -1 {
   798  		if isLeaf(f) {
   799  			// Leaf functions don't save/restore the link register.
   800  			s.allocatable = s.allocatable.removeReg(register(s.f.Config.LinkReg))
   801  		}
   802  	}
   803  	if s.f.Config.ctxt.Flag_dynlink {
   804  		switch s.f.Config.arch {
   805  		case "386":
   806  			// nothing to do.
   807  			// Note that for Flag_shared (position independent code)
   808  			// we do need to be careful, but that carefulness is hidden
   809  			// in the rewrite rules so we always have a free register
   810  			// available for global load/stores. See _gen/386.rules (search for Flag_shared).
   811  		case "amd64":
   812  			s.allocatable = s.allocatable.removeReg(15) // R15
   813  		case "arm":
   814  			s.allocatable = s.allocatable.removeReg(9) // R9
   815  		case "arm64":
   816  			// nothing to do
   817  		case "loong64": // R2 (aka TP) already reserved.
   818  			// nothing to do
   819  		case "ppc64", "ppc64le": // R2 already reserved.
   820  			// nothing to do
   821  		case "riscv64": // X3 (aka GP) and X4 (aka TP) already reserved.
   822  			// nothing to do
   823  		case "s390x":
   824  			s.allocatable = s.allocatable.removeReg(11) // R11
   825  		default:
   826  			s.f.fe.Fatalf(src.NoXPos, "arch %s not implemented", s.f.Config.arch)
   827  		}
   828  	}
   829  
   830  	// Linear scan register allocation can be influenced by the order in which blocks appear.
   831  	// Decouple the register allocation order from the generated block order.
   832  	// This also creates an opportunity for experiments to find a better order.
   833  	s.visitOrder = layoutRegallocOrder(f)
   834  
   835  	// Compute block order. This array allows us to distinguish forward edges
   836  	// from backward edges and compute how far they go.
   837  	s.blockOrder = make([]int32, f.NumBlocks())
   838  	for i, b := range s.visitOrder {
   839  		s.blockOrder[b.ID] = int32(i)
   840  	}
   841  
   842  	s.regs = make([]regState, s.numRegs)
   843  	nv := f.NumValues()
   844  	if cap(s.f.Cache.regallocValues) >= nv {
   845  		s.f.Cache.regallocValues = s.f.Cache.regallocValues[:nv]
   846  	} else {
   847  		s.f.Cache.regallocValues = make([]valState, nv)
   848  	}
   849  	s.values = s.f.Cache.regallocValues
   850  	s.orig = s.f.Cache.allocValueSlice(nv)
   851  	s.copies = make(map[*Value]bool)
   852  	for _, b := range s.visitOrder {
   853  		for _, v := range b.Values {
   854  			if v.needRegister() {
   855  				s.values[v.ID].needReg = true
   856  				s.values[v.ID].rematerializeable = v.rematerializeable()
   857  				s.orig[v.ID] = v
   858  			}
   859  			// Note: needReg is false for values returning Tuple types.
   860  			// Instead, we mark the corresponding Selects as needReg.
   861  		}
   862  	}
   863  	s.computeLive()
   864  
   865  	s.endRegs = make([][]endReg, f.NumBlocks())
   866  	s.startRegs = make([][]startReg, f.NumBlocks())
   867  	s.spillLive = make([][]ID, f.NumBlocks())
   868  	s.sdom = f.Sdom()
   869  
   870  	// wasm: Mark instructions that can be optimized to have their values only on the WebAssembly stack.
   871  	if f.Config.ctxt.Arch.Arch == sys.ArchWasm {
   872  		canLiveOnStack := f.newSparseSet(f.NumValues())
   873  		defer f.retSparseSet(canLiveOnStack)
   874  		for _, b := range f.Blocks {
   875  			// New block. Clear candidate set.
   876  			canLiveOnStack.clear()
   877  			for _, c := range b.ControlValues() {
   878  				if c.Uses == 1 && !opcodeTable[c.Op].generic {
   879  					canLiveOnStack.add(c.ID)
   880  				}
   881  			}
   882  			// Walking backwards.
   883  			for i := len(b.Values) - 1; i >= 0; i-- {
   884  				v := b.Values[i]
   885  				if canLiveOnStack.contains(v.ID) {
   886  					v.OnWasmStack = true
   887  				} else {
   888  					// Value can not live on stack. Values are not allowed to be reordered, so clear candidate set.
   889  					canLiveOnStack.clear()
   890  				}
   891  				for _, arg := range v.Args {
   892  					// Value can live on the stack if:
   893  					// - it is only used once
   894  					// - it is used in the same basic block
   895  					// - it is not a "mem" value
   896  					// - it is a WebAssembly op
   897  					if arg.Uses == 1 && arg.Block == v.Block && !arg.Type.IsMemory() && !opcodeTable[arg.Op].generic {
   898  						canLiveOnStack.add(arg.ID)
   899  					}
   900  				}
   901  			}
   902  		}
   903  	}
   904  
   905  	// The clobberdeadreg experiment inserts code to clobber dead registers
   906  	// at call sites.
   907  	// Ignore huge functions to avoid doing too much work.
   908  	if base.Flag.ClobberDeadReg && len(s.f.Blocks) <= 10000 {
   909  		// TODO: honor GOCLOBBERDEADHASH, or maybe GOSSAHASH.
   910  		s.doClobber = true
   911  	}
   912  }
   913  
   914  func (s *regAllocState) close() {
   915  	s.f.Cache.freeValueSlice(s.orig)
   916  }
   917  
   918  // Adds a use record for id at distance dist from the start of the block.
   919  // All calls to addUse must happen with nonincreasing dist.
   920  func (s *regAllocState) addUse(id ID, dist int32, pos src.XPos) {
   921  	r := s.freeUseRecords
   922  	if r != nil {
   923  		s.freeUseRecords = r.next
   924  	} else {
   925  		r = &use{}
   926  	}
   927  	r.dist = dist
   928  	r.pos = pos
   929  	r.next = s.values[id].uses
   930  	s.values[id].uses = r
   931  	if r.next != nil && dist > r.next.dist {
   932  		s.f.Fatalf("uses added in wrong order")
   933  	}
   934  }
   935  
   936  // advanceUses advances the uses of v's args from the state before v to the state after v.
   937  // Any values which have no more uses are deallocated from registers.
   938  func (s *regAllocState) advanceUses(v *Value) {
   939  	for _, a := range v.Args {
   940  		if !s.values[a.ID].needReg {
   941  			continue
   942  		}
   943  		ai := &s.values[a.ID]
   944  		r := ai.uses
   945  		ai.uses = r.next
   946  		if r.next == nil || (!opcodeTable[a.Op].fixedReg && r.next.dist > s.nextCall[s.curIdx]) {
   947  			// Value is dead (or is not used again until after a call), free all registers that hold it.
   948  			s.freeRegs(ai.regs)
   949  		}
   950  		r.next = s.freeUseRecords
   951  		s.freeUseRecords = r
   952  	}
   953  	s.dropIfUnused(v)
   954  }
   955  
   956  // Drop v from registers if it isn't used again, or its only uses are after
   957  // a call instruction.
   958  func (s *regAllocState) dropIfUnused(v *Value) {
   959  	if !s.values[v.ID].needReg {
   960  		return
   961  	}
   962  	vi := &s.values[v.ID]
   963  	r := vi.uses
   964  	nextCall := s.nextCall[s.curIdx]
   965  	if opcodeTable[v.Op].call {
   966  		if s.curIdx == len(s.nextCall)-1 {
   967  			nextCall = math.MaxInt32
   968  		} else {
   969  			nextCall = s.nextCall[s.curIdx+1]
   970  		}
   971  	}
   972  	if r == nil || (!opcodeTable[v.Op].fixedReg && r.dist > nextCall) {
   973  		s.freeRegs(vi.regs)
   974  	}
   975  }
   976  
   977  // liveAfterCurrentInstruction reports whether v is live after
   978  // the current instruction is completed.  v must be used by the
   979  // current instruction.
   980  func (s *regAllocState) liveAfterCurrentInstruction(v *Value) bool {
   981  	u := s.values[v.ID].uses
   982  	if u == nil {
   983  		panic(fmt.Errorf("u is nil, v = %s, s.values[v.ID] = %v", v.LongString(), s.values[v.ID]))
   984  	}
   985  	d := u.dist
   986  	for u != nil && u.dist == d {
   987  		u = u.next
   988  	}
   989  	return u != nil && u.dist > d
   990  }
   991  
   992  // Sets the state of the registers to that encoded in regs.
   993  func (s *regAllocState) setState(regs []endReg) {
   994  	s.freeRegs(s.used)
   995  	for _, x := range regs {
   996  		s.assignReg(x.r, x.v, x.c)
   997  	}
   998  }
   999  
  1000  // compatRegs returns the set of registers which can store a type t.
  1001  func (s *regAllocState) compatRegs(t *types.Type) regMask {
  1002  	var m regMask
  1003  	if t.IsTuple() || t.IsFlags() {
  1004  		return regMask{}
  1005  	}
  1006  	if t.IsSIMD() {
  1007  		if t.Size() > 8 {
  1008  			return s.f.Config.simdRegMask.intersect(s.allocatable)
  1009  		} else {
  1010  			// K mask
  1011  			return s.f.Config.gpRegMask.intersect(s.allocatable)
  1012  		}
  1013  	}
  1014  	if t.IsFloat() || t == types.TypeInt128 {
  1015  		if t.Kind() == types.TFLOAT32 && !s.f.Config.fp32RegMask.empty() {
  1016  			m = s.f.Config.fp32RegMask
  1017  		} else if t.Kind() == types.TFLOAT64 && !s.f.Config.fp64RegMask.empty() {
  1018  			m = s.f.Config.fp64RegMask
  1019  		} else {
  1020  			m = s.f.Config.fpRegMask
  1021  		}
  1022  	} else {
  1023  		m = s.f.Config.gpRegMask
  1024  	}
  1025  	return m.intersect(s.allocatable)
  1026  }
  1027  
  1028  // regspec returns the regInfo for operation op.
  1029  func (s *regAllocState) regspec(v *Value) regInfo {
  1030  	op := v.Op
  1031  	if op == OpConvert {
  1032  		// OpConvert is a generic op, so it doesn't have a
  1033  		// register set in the static table. It can use any
  1034  		// allocatable integer register.
  1035  		m := s.allocatable.intersect(s.f.Config.gpRegMask)
  1036  		return regInfo{inputs: []inputInfo{{regs: m}}, outputs: []outputInfo{{regs: m}}}
  1037  	}
  1038  	if op == OpArgIntReg {
  1039  		reg := v.Block.Func.Config.intParamRegs[v.AuxInt8()]
  1040  		return regInfo{outputs: []outputInfo{{regs: regMaskAt(register(reg))}}}
  1041  	}
  1042  	if op == OpArgFloatReg {
  1043  		reg := v.Block.Func.Config.floatParamRegs[v.AuxInt8()]
  1044  		return regInfo{outputs: []outputInfo{{regs: regMaskAt(register(reg))}}}
  1045  	}
  1046  	if op.IsCall() {
  1047  		if ac, ok := v.Aux.(*AuxCall); ok && ac.reg != nil {
  1048  			return *ac.Reg(&opcodeTable[op].reg, s.f.Config)
  1049  		}
  1050  	}
  1051  	if op == OpMakeResult && s.f.OwnAux.reg != nil {
  1052  		return *s.f.OwnAux.ResultReg(s.f.Config)
  1053  	}
  1054  	return opcodeTable[op].reg
  1055  }
  1056  
  1057  func (s *regAllocState) isGReg(r register) bool {
  1058  	return s.f.Config.hasGReg && s.GReg == r
  1059  }
  1060  
  1061  // Dummy value used to represent the value being held in a temporary register.
  1062  var tmpVal Value
  1063  
  1064  func (s *regAllocState) regalloc(f *Func) {
  1065  	regValLiveSet := f.newSparseSet(f.NumValues()) // set of values that may be live in register
  1066  	defer f.retSparseSet(regValLiveSet)
  1067  	var oldSched []*Value
  1068  	var phis []*Value
  1069  	var phiRegs []register
  1070  	var args []*Value
  1071  
  1072  	// Data structure used for computing desired registers.
  1073  	var desired desiredState
  1074  	desiredSecondReg := map[ID][4]register{} // desired register allocation for 2nd part of a tuple
  1075  
  1076  	// Desired registers for inputs & outputs for each instruction in the block.
  1077  	type dentry struct {
  1078  		out [4]register    // desired output registers
  1079  		in  [3][4]register // desired input registers (for inputs 0,1, and 2)
  1080  	}
  1081  	var dinfo []dentry
  1082  
  1083  	if f.Entry != f.Blocks[0] {
  1084  		f.Fatalf("entry block must be first")
  1085  	}
  1086  
  1087  	for _, b := range s.visitOrder {
  1088  		if s.f.pass.debug > regDebug {
  1089  			fmt.Printf("Begin processing block %v\n", b)
  1090  		}
  1091  		s.curBlock = b
  1092  		s.startRegsMask = regMask{}
  1093  		s.usedSinceBlockStart = regMask{}
  1094  		clear(desiredSecondReg)
  1095  
  1096  		// Initialize regValLiveSet and uses fields for this block.
  1097  		// Walk backwards through the block doing liveness analysis.
  1098  		regValLiveSet.clear()
  1099  		if s.live != nil {
  1100  			for _, e := range s.live[b.ID] {
  1101  				s.addUse(e.ID, int32(len(b.Values))+e.dist, e.pos) // pseudo-uses from beyond end of block
  1102  				regValLiveSet.add(e.ID)
  1103  			}
  1104  		}
  1105  		for _, v := range b.ControlValues() {
  1106  			if s.values[v.ID].needReg {
  1107  				s.addUse(v.ID, int32(len(b.Values)), b.Pos) // pseudo-use by control values
  1108  				regValLiveSet.add(v.ID)
  1109  			}
  1110  		}
  1111  		if cap(s.nextCall) < len(b.Values) {
  1112  			c := cap(s.nextCall)
  1113  			s.nextCall = append(s.nextCall[:c], make([]int32, len(b.Values)-c)...)
  1114  		} else {
  1115  			s.nextCall = s.nextCall[:len(b.Values)]
  1116  		}
  1117  		var nextCall int32 = math.MaxInt32
  1118  		for i := len(b.Values) - 1; i >= 0; i-- {
  1119  			v := b.Values[i]
  1120  			regValLiveSet.remove(v.ID)
  1121  			if v.Op == OpPhi {
  1122  				// Remove v from the live set, but don't add
  1123  				// any inputs. This is the state the len(b.Preds)>1
  1124  				// case below desires; it wants to process phis specially.
  1125  				s.nextCall[i] = nextCall
  1126  				continue
  1127  			}
  1128  			if opcodeTable[v.Op].call {
  1129  				// Function call clobbers all the registers but SP and SB.
  1130  				regValLiveSet.clear()
  1131  				if s.sp != 0 && s.values[s.sp].uses != nil {
  1132  					regValLiveSet.add(s.sp)
  1133  				}
  1134  				if s.sb != 0 && s.values[s.sb].uses != nil {
  1135  					regValLiveSet.add(s.sb)
  1136  				}
  1137  				nextCall = int32(i)
  1138  			}
  1139  			for _, a := range v.Args {
  1140  				if !s.values[a.ID].needReg {
  1141  					continue
  1142  				}
  1143  				s.addUse(a.ID, int32(i), v.Pos)
  1144  				regValLiveSet.add(a.ID)
  1145  			}
  1146  			s.nextCall[i] = nextCall
  1147  		}
  1148  		if s.f.pass.debug > regDebug {
  1149  			fmt.Printf("use distances for %s\n", b)
  1150  			for i := range s.values {
  1151  				vi := &s.values[i]
  1152  				u := vi.uses
  1153  				if u == nil {
  1154  					continue
  1155  				}
  1156  				fmt.Printf("  v%d:", i)
  1157  				for u != nil {
  1158  					fmt.Printf(" %d", u.dist)
  1159  					u = u.next
  1160  				}
  1161  				fmt.Println()
  1162  			}
  1163  		}
  1164  
  1165  		// Make a copy of the block schedule so we can generate a new one in place.
  1166  		// We make a separate copy for phis and regular values.
  1167  		nphi := 0
  1168  		for _, v := range b.Values {
  1169  			if v.Op != OpPhi {
  1170  				break
  1171  			}
  1172  			nphi++
  1173  		}
  1174  		phis = append(phis[:0], b.Values[:nphi]...)
  1175  		oldSched = append(oldSched[:0], b.Values[nphi:]...)
  1176  		b.Values = b.Values[:0]
  1177  
  1178  		// Initialize start state of block.
  1179  		if b == f.Entry {
  1180  			// Regalloc state is empty to start.
  1181  			if nphi > 0 {
  1182  				f.Fatalf("phis in entry block")
  1183  			}
  1184  		} else if len(b.Preds) == 1 {
  1185  			// Start regalloc state with the end state of the previous block.
  1186  			s.setState(s.endRegs[b.Preds[0].b.ID])
  1187  			if nphi > 0 {
  1188  				f.Fatalf("phis in single-predecessor block")
  1189  			}
  1190  			// Drop any values which are no longer live.
  1191  			// This may happen because at the end of p, a value may be
  1192  			// live but only used by some other successor of p.
  1193  			for r := register(0); r < s.numRegs; r++ {
  1194  				v := s.regs[r].v
  1195  				if v != nil && !regValLiveSet.contains(v.ID) {
  1196  					s.freeReg(r)
  1197  				}
  1198  			}
  1199  		} else {
  1200  			// This is the complicated case. We have more than one predecessor,
  1201  			// which means we may have Phi ops.
  1202  
  1203  			// Start with the final register state of the predecessor with least spill values.
  1204  			// This is based on the following points:
  1205  			// 1, The less spill value indicates that the register pressure of this path is smaller,
  1206  			//    so the values of this block are more likely to be allocated to registers.
  1207  			// 2, Avoid the predecessor that contains the function call, because the predecessor that
  1208  			//    contains the function call usually generates a lot of spills and lose the previous
  1209  			//    allocation state.
  1210  			// TODO: Improve this part. At least the size of endRegs of the predecessor also has
  1211  			// an impact on the code size and compiler speed. But it is not easy to find a simple
  1212  			// and efficient method that combines multiple factors.
  1213  			idx := -1
  1214  			for i, p := range b.Preds {
  1215  				// If the predecessor has not been visited yet, skip it because its end state
  1216  				// (redRegs and spillLive) has not been computed yet.
  1217  				pb := p.b
  1218  				if s.blockOrder[pb.ID] >= s.blockOrder[b.ID] {
  1219  					continue
  1220  				}
  1221  				if idx == -1 {
  1222  					idx = i
  1223  					continue
  1224  				}
  1225  				pSel := b.Preds[idx].b
  1226  				if len(s.spillLive[pb.ID]) < len(s.spillLive[pSel.ID]) {
  1227  					idx = i
  1228  				} else if len(s.spillLive[pb.ID]) == len(s.spillLive[pSel.ID]) {
  1229  					// Use a bit of likely information. After critical pass, pb and pSel must
  1230  					// be plain blocks, so check edge pb->pb.Preds instead of edge pb->b.
  1231  					// TODO: improve the prediction of the likely predecessor. The following
  1232  					// method is only suitable for the simplest cases. For complex cases,
  1233  					// the prediction may be inaccurate, but this does not affect the
  1234  					// correctness of the program.
  1235  					// According to the layout algorithm, the predecessor with the
  1236  					// smaller blockOrder is the true branch, and the test results show
  1237  					// that it is better to choose the predecessor with a smaller
  1238  					// blockOrder than no choice.
  1239  					if pb.likelyBranch() && !pSel.likelyBranch() || s.blockOrder[pb.ID] < s.blockOrder[pSel.ID] {
  1240  						idx = i
  1241  					}
  1242  				}
  1243  			}
  1244  			if idx < 0 {
  1245  				f.Fatalf("bad visitOrder, no predecessor of %s has been visited before it", b)
  1246  			}
  1247  			p := b.Preds[idx].b
  1248  			s.setState(s.endRegs[p.ID])
  1249  
  1250  			if s.f.pass.debug > regDebug {
  1251  				fmt.Printf("starting merge block %s with end state of %s:\n", b, p)
  1252  				for _, x := range s.endRegs[p.ID] {
  1253  					fmt.Printf("  %s: orig:%s cache:%s\n", &s.registers[x.r], x.v, x.c)
  1254  				}
  1255  			}
  1256  
  1257  			// Decide on registers for phi ops. Use the registers determined
  1258  			// by the primary predecessor if we can.
  1259  			// TODO: pick best of (already processed) predecessors?
  1260  			// Majority vote? Deepest nesting level?
  1261  			phiRegs = phiRegs[:0]
  1262  			var phiUsed regMask
  1263  
  1264  			for _, v := range phis {
  1265  				if !s.values[v.ID].needReg {
  1266  					phiRegs = append(phiRegs, noRegister)
  1267  					continue
  1268  				}
  1269  				a := v.Args[idx]
  1270  				// Some instructions target not-allocatable registers.
  1271  				// They're not suitable for further (phi-function) allocation.
  1272  				m := s.values[a.ID].regs.minus(phiUsed).intersect(s.allocatable)
  1273  				if !m.empty() {
  1274  					r := s.pickReg(m)
  1275  					phiUsed = phiUsed.addReg(r)
  1276  					phiRegs = append(phiRegs, r)
  1277  				} else {
  1278  					phiRegs = append(phiRegs, noRegister)
  1279  				}
  1280  			}
  1281  
  1282  			// Second pass - deallocate all in-register phi inputs.
  1283  			for i, v := range phis {
  1284  				if !s.values[v.ID].needReg {
  1285  					continue
  1286  				}
  1287  				a := v.Args[idx]
  1288  				r := phiRegs[i]
  1289  				if r == noRegister {
  1290  					continue
  1291  				}
  1292  				if regValLiveSet.contains(a.ID) {
  1293  					// Input value is still live (it is used by something other than Phi).
  1294  					// Try to move it around before kicking out, if there is a free register.
  1295  					// We generate a Copy in the predecessor block and record it. It will be
  1296  					// deleted later if never used.
  1297  					//
  1298  					// Pick a free register. At this point some registers used in the predecessor
  1299  					// block may have been deallocated. Those are the ones used for Phis. Exclude
  1300  					// them (and they are not going to be helpful anyway).
  1301  					m := s.compatRegs(a.Type).minus(s.used).minus(phiUsed)
  1302  					if !m.empty() && !s.values[a.ID].rematerializeable && countRegs(s.values[a.ID].regs) == 1 {
  1303  						r2 := s.pickReg(m)
  1304  						c := p.NewValue1(a.Pos, OpCopy, a.Type, s.regs[r].c)
  1305  						s.copies[c] = false
  1306  						if s.f.pass.debug > regDebug {
  1307  							fmt.Printf("copy %s to %s : %s\n", a, c, &s.registers[r2])
  1308  						}
  1309  						s.setOrig(c, a)
  1310  						s.assignReg(r2, a, c)
  1311  						s.endRegs[p.ID] = append(s.endRegs[p.ID], endReg{r2, a, c})
  1312  					}
  1313  				}
  1314  				s.freeReg(r)
  1315  			}
  1316  
  1317  			// Copy phi ops into new schedule.
  1318  			b.Values = append(b.Values, phis...)
  1319  
  1320  			// Third pass - pick registers for phis whose input
  1321  			// was not in a register in the primary predecessor.
  1322  			for i, v := range phis {
  1323  				if !s.values[v.ID].needReg {
  1324  					continue
  1325  				}
  1326  				if phiRegs[i] != noRegister {
  1327  					continue
  1328  				}
  1329  				m := s.compatRegs(v.Type).minus(phiUsed).minus(s.used)
  1330  				// If one of the other inputs of v is in a register, and the register is available,
  1331  				// select this register, which can save some unnecessary copies.
  1332  				for i, pe := range b.Preds {
  1333  					if i == idx {
  1334  						continue
  1335  					}
  1336  					ri := noRegister
  1337  					for _, er := range s.endRegs[pe.b.ID] {
  1338  						if er.v == s.orig[v.Args[i].ID] {
  1339  							ri = er.r
  1340  							break
  1341  						}
  1342  					}
  1343  					if ri != noRegister && m.hasReg(ri) {
  1344  						m = regMaskAt(ri)
  1345  						break
  1346  					}
  1347  				}
  1348  				if !m.empty() {
  1349  					r := s.pickReg(m)
  1350  					phiRegs[i] = r
  1351  					phiUsed = phiUsed.addReg(r)
  1352  				}
  1353  			}
  1354  
  1355  			// Set registers for phis. Add phi spill code.
  1356  			for i, v := range phis {
  1357  				if !s.values[v.ID].needReg {
  1358  					continue
  1359  				}
  1360  				r := phiRegs[i]
  1361  				if r == noRegister {
  1362  					// stack-based phi
  1363  					// Spills will be inserted in all the predecessors below.
  1364  					s.values[v.ID].spill = v // v starts life spilled
  1365  					continue
  1366  				}
  1367  				// register-based phi
  1368  				s.assignReg(r, v, v)
  1369  			}
  1370  
  1371  			// Deallocate any values which are no longer live. Phis are excluded.
  1372  			for r := register(0); r < s.numRegs; r++ {
  1373  				if phiUsed.hasReg(r) {
  1374  					continue
  1375  				}
  1376  				v := s.regs[r].v
  1377  				if v != nil && !regValLiveSet.contains(v.ID) {
  1378  					s.freeReg(r)
  1379  				}
  1380  			}
  1381  
  1382  			// Save the starting state for use by merge edges.
  1383  			// We append to a stack allocated variable that we'll
  1384  			// later copy into s.startRegs in one fell swoop, to save
  1385  			// on allocations.
  1386  			regList := make([]startReg, 0, 32)
  1387  			for r := register(0); r < s.numRegs; r++ {
  1388  				v := s.regs[r].v
  1389  				if v == nil {
  1390  					continue
  1391  				}
  1392  				if phiUsed.hasReg(r) {
  1393  					// Skip registers that phis used, we'll handle those
  1394  					// specially during merge edge processing.
  1395  					continue
  1396  				}
  1397  				regList = append(regList, startReg{r, v, s.regs[r].c, s.values[v.ID].uses.pos})
  1398  				s.startRegsMask = s.startRegsMask.addReg(r)
  1399  			}
  1400  			s.startRegs[b.ID] = make([]startReg, len(regList))
  1401  			copy(s.startRegs[b.ID], regList)
  1402  
  1403  			if s.f.pass.debug > regDebug {
  1404  				fmt.Printf("after phis\n")
  1405  				for _, x := range s.startRegs[b.ID] {
  1406  					fmt.Printf("  %s: v%d\n", &s.registers[x.r], x.v.ID)
  1407  				}
  1408  			}
  1409  		}
  1410  
  1411  		// Drop phis from registers if they immediately go dead.
  1412  		for i, v := range phis {
  1413  			s.curIdx = i
  1414  			s.dropIfUnused(v)
  1415  		}
  1416  
  1417  		// Allocate space to record the desired registers for each value.
  1418  		if l := len(oldSched); cap(dinfo) < l {
  1419  			dinfo = make([]dentry, l)
  1420  		} else {
  1421  			dinfo = dinfo[:l]
  1422  			clear(dinfo)
  1423  		}
  1424  
  1425  		// Load static desired register info at the end of the block.
  1426  		if s.desired != nil {
  1427  			desired.copy(&s.desired[b.ID])
  1428  		}
  1429  
  1430  		// Check actual assigned registers at the start of the next block(s).
  1431  		// Dynamically assigned registers will trump the static
  1432  		// desired registers computed during liveness analysis.
  1433  		// Note that we do this phase after startRegs is set above, so that
  1434  		// we get the right behavior for a block which branches to itself.
  1435  		for _, e := range b.Succs {
  1436  			succ := e.b
  1437  			// TODO: prioritize likely successor?
  1438  			for _, x := range s.startRegs[succ.ID] {
  1439  				desired.add(x.v.ID, x.r)
  1440  			}
  1441  			// Process phi ops in succ.
  1442  			pidx := e.i
  1443  			for _, v := range succ.Values {
  1444  				if v.Op != OpPhi {
  1445  					break
  1446  				}
  1447  				if !s.values[v.ID].needReg {
  1448  					continue
  1449  				}
  1450  				rp, ok := s.f.getHome(v.ID).(*Register)
  1451  				if !ok {
  1452  					// If v is not assigned a register, pick a register assigned to one of v's inputs.
  1453  					// Hopefully v will get assigned that register later.
  1454  					// If the inputs have allocated register information, add it to desired,
  1455  					// which may reduce spill or copy operations when the register is available.
  1456  					for _, a := range v.Args {
  1457  						rp, ok = s.f.getHome(a.ID).(*Register)
  1458  						if ok {
  1459  							break
  1460  						}
  1461  					}
  1462  					if !ok {
  1463  						continue
  1464  					}
  1465  				}
  1466  				desired.add(v.Args[pidx].ID, register(rp.num))
  1467  			}
  1468  		}
  1469  		// Walk values backwards computing desired register info.
  1470  		// See computeDesired for more comments.
  1471  		for i := len(oldSched) - 1; i >= 0; i-- {
  1472  			v := oldSched[i]
  1473  			prefs := desired.remove(v.ID)
  1474  			regspec := s.regspec(v)
  1475  			desired.clobber(regspec.clobbers)
  1476  			for _, j := range regspec.inputs {
  1477  				if countRegs(j.regs) != 1 {
  1478  					continue
  1479  				}
  1480  				desired.clobber(j.regs)
  1481  				desired.add(v.Args[j.idx].ID, s.pickReg(j.regs))
  1482  			}
  1483  			if opcodeTable[v.Op].resultInArg0 || v.Op == OpAMD64ADDQconst || v.Op == OpAMD64ADDLconst || v.Op == OpSelect0 {
  1484  				if opcodeTable[v.Op].commutative {
  1485  					desired.addList(v.Args[1].ID, prefs)
  1486  				}
  1487  				desired.addList(v.Args[0].ID, prefs)
  1488  			}
  1489  			// Save desired registers for this value.
  1490  			dinfo[i].out = prefs
  1491  			for j, a := range v.Args {
  1492  				if j >= len(dinfo[i].in) {
  1493  					break
  1494  				}
  1495  				dinfo[i].in[j] = desired.get(a.ID)
  1496  			}
  1497  			if v.Op == OpSelect1 && prefs[0] != noRegister {
  1498  				// Save desired registers of select1 for
  1499  				// use by the tuple generating instruction.
  1500  				desiredSecondReg[v.Args[0].ID] = prefs
  1501  			}
  1502  		}
  1503  
  1504  		// Process all the non-phi values.
  1505  		for idx, v := range oldSched {
  1506  			s.curIdx = nphi + idx
  1507  			tmpReg := noRegister
  1508  			if s.f.pass.debug > regDebug {
  1509  				fmt.Printf("  processing %s\n", v.LongString())
  1510  			}
  1511  			regspec := s.regspec(v)
  1512  			if v.Op == OpPhi {
  1513  				f.Fatalf("phi %s not at start of block", v)
  1514  			}
  1515  			if opcodeTable[v.Op].fixedReg {
  1516  				switch v.Op {
  1517  				case OpSP:
  1518  					s.assignReg(s.SPReg, v, v)
  1519  					s.sp = v.ID
  1520  				case OpSB:
  1521  					s.assignReg(s.SBReg, v, v)
  1522  					s.sb = v.ID
  1523  				case OpARM64ZERO, OpLOONG64ZERO, OpMIPS64ZERO:
  1524  					s.assignReg(s.ZeroIntReg, v, v)
  1525  				case OpAMD64Zero128, OpAMD64Zero256, OpAMD64Zero512:
  1526  					regspec := s.regspec(v)
  1527  					m := regspec.outputs[0].regs
  1528  					if countRegs(m) != 1 {
  1529  						f.Fatalf("bad fixed-register op %s", v)
  1530  					}
  1531  					s.assignReg(s.pickReg(m), v, v)
  1532  				default:
  1533  					f.Fatalf("unknown fixed-register op %s", v)
  1534  				}
  1535  				b.Values = append(b.Values, v)
  1536  				s.advanceUses(v)
  1537  				continue
  1538  			}
  1539  			if v.Op == OpSelect0 || v.Op == OpSelect1 || v.Op == OpSelectN {
  1540  				if s.values[v.ID].needReg {
  1541  					if v.Op == OpSelectN {
  1542  						s.assignReg(register(s.f.getHome(v.Args[0].ID).(LocResults)[int(v.AuxInt)].(*Register).num), v, v)
  1543  					} else {
  1544  						var i = 0
  1545  						if v.Op == OpSelect1 {
  1546  							i = 1
  1547  						}
  1548  						s.assignReg(register(s.f.getHome(v.Args[0].ID).(LocPair)[i].(*Register).num), v, v)
  1549  					}
  1550  				}
  1551  				b.Values = append(b.Values, v)
  1552  				s.advanceUses(v)
  1553  				continue
  1554  			}
  1555  			if v.Op == OpGetG && s.f.Config.hasGReg {
  1556  				// use hardware g register
  1557  				if s.regs[s.GReg].v != nil {
  1558  					s.freeReg(s.GReg) // kick out the old value
  1559  				}
  1560  				s.assignReg(s.GReg, v, v)
  1561  				b.Values = append(b.Values, v)
  1562  				s.advanceUses(v)
  1563  				continue
  1564  			}
  1565  			if v.Op == OpArg {
  1566  				// Args are "pre-spilled" values. We don't allocate
  1567  				// any register here. We just set up the spill pointer to
  1568  				// point at itself and any later user will restore it to use it.
  1569  				s.values[v.ID].spill = v
  1570  				b.Values = append(b.Values, v)
  1571  				s.advanceUses(v)
  1572  				continue
  1573  			}
  1574  			if v.Op == OpKeepAlive {
  1575  				// Make sure the argument to v is still live here.
  1576  				s.advanceUses(v)
  1577  				a := v.Args[0]
  1578  				vi := &s.values[a.ID]
  1579  				if vi.regs.empty() && !vi.rematerializeable {
  1580  					// Use the spill location.
  1581  					// This forces later liveness analysis to make the
  1582  					// value live at this point.
  1583  					v.SetArg(0, s.makeSpill(a, b))
  1584  				} else if _, ok := a.Aux.(*ir.Name); ok && vi.rematerializeable {
  1585  					// Rematerializeable value with a *ir.Name. This is the address of
  1586  					// a stack object (e.g. an LEAQ). Keep the object live.
  1587  					// Change it to VarLive, which is what plive expects for locals.
  1588  					v.Op = OpVarLive
  1589  					v.SetArgs1(v.Args[1])
  1590  					v.Aux = a.Aux
  1591  				} else {
  1592  					// In-register and rematerializeable values are already live.
  1593  					// These are typically rematerializeable constants like nil,
  1594  					// or values of a variable that were modified since the last call.
  1595  					v.Op = OpCopy
  1596  					v.SetArgs1(v.Args[1])
  1597  				}
  1598  				b.Values = append(b.Values, v)
  1599  				continue
  1600  			}
  1601  			if len(regspec.inputs) == 0 && len(regspec.outputs) == 0 {
  1602  				// No register allocation required (or none specified yet)
  1603  				if s.doClobber && v.Op.IsCall() {
  1604  					s.clobberRegs(regspec.clobbers)
  1605  				}
  1606  				s.freeRegs(regspec.clobbers)
  1607  				b.Values = append(b.Values, v)
  1608  				s.advanceUses(v)
  1609  				continue
  1610  			}
  1611  
  1612  			if s.values[v.ID].rematerializeable {
  1613  				// Value is rematerializeable, don't issue it here.
  1614  				// It will get issued just before each use (see
  1615  				// allocValueToReg).
  1616  				for _, a := range v.Args {
  1617  					a.Uses--
  1618  				}
  1619  				s.advanceUses(v)
  1620  				continue
  1621  			}
  1622  
  1623  			if s.f.pass.debug > regDebug {
  1624  				fmt.Printf("value %s\n", v.LongString())
  1625  				fmt.Printf("  out:")
  1626  				for _, r := range dinfo[idx].out {
  1627  					if r != noRegister {
  1628  						fmt.Printf(" %s", &s.registers[r])
  1629  					}
  1630  				}
  1631  				fmt.Println()
  1632  				for i := 0; i < len(v.Args) && i < 3; i++ {
  1633  					fmt.Printf("  in%d:", i)
  1634  					for _, r := range dinfo[idx].in[i] {
  1635  						if r != noRegister {
  1636  							fmt.Printf(" %s", &s.registers[r])
  1637  						}
  1638  					}
  1639  					fmt.Println()
  1640  				}
  1641  			}
  1642  
  1643  			// Move arguments to registers.
  1644  			// First, if an arg must be in a specific register and it is already
  1645  			// in place, keep it.
  1646  			args = append(args[:0], make([]*Value, len(v.Args))...)
  1647  			for i, a := range v.Args {
  1648  				if !s.values[a.ID].needReg {
  1649  					args[i] = a
  1650  				}
  1651  			}
  1652  			for _, i := range regspec.inputs {
  1653  				mask := i.regs
  1654  				if countRegs(mask) == 1 && !mask.intersect(s.values[v.Args[i.idx].ID].regs).empty() {
  1655  					args[i.idx] = s.allocValToReg(v.Args[i.idx], mask, true, v.Pos)
  1656  				}
  1657  			}
  1658  			// Then, if an arg must be in a specific register and that
  1659  			// register is free, allocate that one. Otherwise when processing
  1660  			// another input we may kick a value into the free register, which
  1661  			// then will be kicked out again.
  1662  			// This is a common case for passing-in-register arguments for
  1663  			// function calls.
  1664  			for {
  1665  				freed := false
  1666  				for _, i := range regspec.inputs {
  1667  					if args[i.idx] != nil {
  1668  						continue // already allocated
  1669  					}
  1670  					mask := i.regs
  1671  					if countRegs(mask) == 1 && !mask.minus(s.used).empty() {
  1672  						args[i.idx] = s.allocValToReg(v.Args[i.idx], mask, true, v.Pos)
  1673  						// If the input is in other registers that will be clobbered by v,
  1674  						// or the input is dead, free the registers. This may make room
  1675  						// for other inputs.
  1676  						oldregs := s.values[v.Args[i.idx].ID].regs
  1677  						if oldregs.minus(regspec.clobbers).empty() || !s.liveAfterCurrentInstruction(v.Args[i.idx]) {
  1678  							s.freeRegs(oldregs.minus(mask).minus(s.nospill))
  1679  							freed = true
  1680  						}
  1681  					}
  1682  				}
  1683  				if !freed {
  1684  					break
  1685  				}
  1686  			}
  1687  			// Last, allocate remaining ones, in an ordering defined
  1688  			// by the register specification (most constrained first).
  1689  			for _, i := range regspec.inputs {
  1690  				if args[i.idx] != nil {
  1691  					continue // already allocated
  1692  				}
  1693  				mask := i.regs
  1694  				if mask.intersect(s.values[v.Args[i.idx].ID].regs).empty() {
  1695  					// Need a new register for the input.
  1696  					mask = mask.intersect(s.allocatable)
  1697  					mask = mask.minus(s.nospill)
  1698  					// Used desired register if available.
  1699  					if i.idx < 3 {
  1700  						for _, r := range dinfo[idx].in[i.idx] {
  1701  							if r != noRegister && mask.minus(s.used).hasReg(r) {
  1702  								// Desired register is allowed and unused.
  1703  								mask = regMaskAt(r)
  1704  								break
  1705  							}
  1706  						}
  1707  					}
  1708  					// Avoid registers we're saving for other values.
  1709  					if !mask.minus(desired.avoid).empty() {
  1710  						mask = mask.minus(desired.avoid)
  1711  					}
  1712  				}
  1713  				if mask.intersect(s.values[v.Args[i.idx].ID].regs).hasReg(s.SPReg) {
  1714  					// Prefer SP register. This ensures that local variables
  1715  					// use SP as their base register (instead of a copy of the
  1716  					// stack pointer living in another register). See issue 74836.
  1717  					mask = regMaskAt(s.SPReg)
  1718  				}
  1719  				args[i.idx] = s.allocValToReg(v.Args[i.idx], mask, true, v.Pos)
  1720  			}
  1721  
  1722  			// If the output clobbers the input register, make sure we have
  1723  			// at least two copies of the input register so we don't
  1724  			// have to reload the value from the spill location.
  1725  			if opcodeTable[v.Op].resultInArg0 {
  1726  				var m regMask
  1727  				if !s.liveAfterCurrentInstruction(v.Args[0]) {
  1728  					// arg0 is dead.  We can clobber its register.
  1729  					goto ok
  1730  				}
  1731  				if opcodeTable[v.Op].commutative && !s.liveAfterCurrentInstruction(v.Args[1]) {
  1732  					args[0], args[1] = args[1], args[0]
  1733  					goto ok
  1734  				}
  1735  				if s.values[v.Args[0].ID].rematerializeable {
  1736  					// We can rematerialize the input, don't worry about clobbering it.
  1737  					goto ok
  1738  				}
  1739  				if opcodeTable[v.Op].commutative && s.values[v.Args[1].ID].rematerializeable {
  1740  					args[0], args[1] = args[1], args[0]
  1741  					goto ok
  1742  				}
  1743  				if countRegs(s.values[v.Args[0].ID].regs) >= 2 {
  1744  					// we have at least 2 copies of arg0.  We can afford to clobber one.
  1745  					goto ok
  1746  				}
  1747  				if opcodeTable[v.Op].commutative && countRegs(s.values[v.Args[1].ID].regs) >= 2 {
  1748  					args[0], args[1] = args[1], args[0]
  1749  					goto ok
  1750  				}
  1751  
  1752  				// We can't overwrite arg0 (or arg1, if commutative).  So we
  1753  				// need to make a copy of an input so we have a register we can modify.
  1754  
  1755  				// Possible new registers to copy into.
  1756  				m = s.compatRegs(v.Args[0].Type).minus(s.used)
  1757  				if m.empty() {
  1758  					// No free registers.  In this case we'll just clobber
  1759  					// an input and future uses of that input must use a restore.
  1760  					// TODO(khr): We should really do this like allocReg does it,
  1761  					// spilling the value with the most distant next use.
  1762  					goto ok
  1763  				}
  1764  
  1765  				// Try to move an input to the desired output, if allowed.
  1766  				for _, r := range dinfo[idx].out {
  1767  					if r != noRegister && m.intersect(regspec.outputs[0].regs).hasReg(r) {
  1768  						m = regMaskAt(r)
  1769  						args[0] = s.allocValToReg(v.Args[0], m, true, v.Pos)
  1770  						// Note: we update args[0] so the instruction will
  1771  						// use the register copy we just made.
  1772  						goto ok
  1773  					}
  1774  				}
  1775  				// Try to copy input to its desired location & use its old
  1776  				// location as the result register.
  1777  				for _, r := range dinfo[idx].in[0] {
  1778  					if r != noRegister && m.hasReg(r) {
  1779  						m = regMaskAt(r)
  1780  						c := s.allocValToReg(v.Args[0], m, true, v.Pos)
  1781  						s.copies[c] = false
  1782  						// Note: no update to args[0] so the instruction will
  1783  						// use the original copy.
  1784  						goto ok
  1785  					}
  1786  				}
  1787  				if opcodeTable[v.Op].commutative {
  1788  					for _, r := range dinfo[idx].in[1] {
  1789  						if r != noRegister && m.hasReg(r) {
  1790  							m = regMaskAt(r)
  1791  							c := s.allocValToReg(v.Args[1], m, true, v.Pos)
  1792  							s.copies[c] = false
  1793  							args[0], args[1] = args[1], args[0]
  1794  							goto ok
  1795  						}
  1796  					}
  1797  				}
  1798  
  1799  				// Avoid future fixed uses if we can.
  1800  				if !m.minus(desired.avoid).empty() {
  1801  					m = m.minus(desired.avoid)
  1802  				}
  1803  				// Save input 0 to a new register so we can clobber it.
  1804  				c := s.allocValToReg(v.Args[0], m, true, v.Pos)
  1805  				s.copies[c] = false
  1806  
  1807  				// Normally we use the register of the old copy of input 0 as the target.
  1808  				// However, if input 0 is already in its desired register then we use
  1809  				// the register of the new copy instead.
  1810  				if regspec.outputs[0].regs.hasReg(register(s.f.getHome(c.ID).(*Register).num)) {
  1811  					if rp, ok := s.f.getHome(args[0].ID).(*Register); ok {
  1812  						r := register(rp.num)
  1813  						for _, r2 := range dinfo[idx].in[0] {
  1814  							if r == r2 {
  1815  								args[0] = c
  1816  								break
  1817  							}
  1818  						}
  1819  					}
  1820  				}
  1821  			}
  1822  		ok:
  1823  			for i := 0; i < 2; i++ {
  1824  				if !(i == 0 && regspec.clobbersArg0 || i == 1 && regspec.clobbersArg1) {
  1825  					continue
  1826  				}
  1827  				if !s.liveAfterCurrentInstruction(v.Args[i]) {
  1828  					// arg is dead.  We can clobber its register.
  1829  					continue
  1830  				}
  1831  				if s.values[v.Args[i].ID].rematerializeable {
  1832  					// We can rematerialize the input, don't worry about clobbering it.
  1833  					continue
  1834  				}
  1835  				if countRegs(s.values[v.Args[i].ID].regs) >= 2 {
  1836  					// We have at least 2 copies of arg.  We can afford to clobber one.
  1837  					continue
  1838  				}
  1839  				// Possible new registers to copy into.
  1840  				m := s.compatRegs(v.Args[i].Type).minus(s.used)
  1841  				if m.empty() {
  1842  					// No free registers.  In this case we'll just clobber the
  1843  					// input and future uses of that input must use a restore.
  1844  					// TODO(khr): We should really do this like allocReg does it,
  1845  					// spilling the value with the most distant next use.
  1846  					continue
  1847  				}
  1848  				// Copy input to a different register that won't be clobbered.
  1849  				c := s.allocValToReg(v.Args[i], m, true, v.Pos)
  1850  				s.copies[c] = false
  1851  			}
  1852  
  1853  			// Pick a temporary register if needed.
  1854  			// It should be distinct from all the input registers, so we
  1855  			// allocate it after all the input registers, but before
  1856  			// the input registers are freed via advanceUses below.
  1857  			// (Not all instructions need that distinct part, but it is conservative.)
  1858  			// We also ensure it is not any of the single-choice output registers.
  1859  			if opcodeTable[v.Op].needIntTemp {
  1860  				m := s.allocatable.intersect(s.f.Config.gpRegMask)
  1861  				for _, out := range regspec.outputs {
  1862  					if countRegs(out.regs) == 1 {
  1863  						m = m.minus(out.regs)
  1864  					}
  1865  				}
  1866  				if !m.minus(desired.avoid).minus(s.nospill).empty() {
  1867  					m = m.minus(desired.avoid)
  1868  				}
  1869  				tmpReg = s.allocReg(m, &tmpVal)
  1870  				s.nospill = s.nospill.addReg(tmpReg)
  1871  				s.tmpused = s.tmpused.addReg(tmpReg)
  1872  			}
  1873  
  1874  			if regspec.clobbersArg0 {
  1875  				s.freeReg(register(s.f.getHome(args[0].ID).(*Register).num))
  1876  			}
  1877  			if regspec.clobbersArg1 && !(regspec.clobbersArg0 && s.f.getHome(args[0].ID) == s.f.getHome(args[1].ID)) {
  1878  				s.freeReg(register(s.f.getHome(args[1].ID).(*Register).num))
  1879  			}
  1880  
  1881  			// Now that all args are in regs, we're ready to issue the value itself.
  1882  			// Before we pick a register for the output value, allow input registers
  1883  			// to be deallocated. We do this here so that the output can use the
  1884  			// same register as a dying input.
  1885  			if !opcodeTable[v.Op].resultNotInArgs {
  1886  				s.tmpused = s.nospill
  1887  				s.nospill = regMask{}
  1888  				s.advanceUses(v) // frees any registers holding args that are no longer live
  1889  			}
  1890  
  1891  			// Dump any registers which will be clobbered
  1892  			if s.doClobber && v.Op.IsCall() {
  1893  				// clobber registers that are marked as clobber in regmask, but
  1894  				// don't clobber inputs.
  1895  				s.clobberRegs(regspec.clobbers.minus(s.tmpused).minus(s.nospill))
  1896  			}
  1897  			s.freeRegs(regspec.clobbers)
  1898  			s.tmpused = s.tmpused.union(regspec.clobbers)
  1899  
  1900  			// Pick registers for outputs.
  1901  			{
  1902  				outRegs := noRegisters // TODO if this is costly, hoist and clear incrementally below.
  1903  				maxOutIdx := -1
  1904  				var used regMask
  1905  				if tmpReg != noRegister {
  1906  					// Ensure output registers are distinct from the temporary register.
  1907  					// (Not all instructions need that distinct part, but it is conservative.)
  1908  					used = used.addReg(tmpReg)
  1909  				}
  1910  				for _, out := range regspec.outputs {
  1911  					if out.regs.empty() {
  1912  						continue
  1913  					}
  1914  					mask := out.regs.intersect(s.allocatable).minus(used)
  1915  					if mask.empty() {
  1916  						s.f.Fatalf("can't find any output register %s", v.LongString())
  1917  					}
  1918  					if opcodeTable[v.Op].resultInArg0 && out.idx == 0 {
  1919  						if !opcodeTable[v.Op].commutative {
  1920  							// Output must use the same register as input 0.
  1921  							r := register(s.f.getHome(args[0].ID).(*Register).num)
  1922  							if !mask.hasReg(r) {
  1923  								s.f.Fatalf("resultInArg0 value's input %v cannot be an output of %s", s.f.getHome(args[0].ID).(*Register), v.LongString())
  1924  							}
  1925  							mask = regMaskAt(r)
  1926  						} else {
  1927  							// Output must use the same register as input 0 or 1.
  1928  							r0 := register(s.f.getHome(args[0].ID).(*Register).num)
  1929  							r1 := register(s.f.getHome(args[1].ID).(*Register).num)
  1930  							// Check r0 and r1 for desired output register.
  1931  							found := false
  1932  							for _, r := range dinfo[idx].out {
  1933  								if (r == r0 || r == r1) && mask.minus(s.used).hasReg(r) {
  1934  									mask = regMaskAt(r)
  1935  									found = true
  1936  									if r == r1 {
  1937  										args[0], args[1] = args[1], args[0]
  1938  									}
  1939  									break
  1940  								}
  1941  							}
  1942  							if !found {
  1943  								// Neither are desired, pick r0.
  1944  								mask = regMaskAt(r0)
  1945  							}
  1946  						}
  1947  					}
  1948  					if out.idx == 0 { // desired registers only apply to the first element of a tuple result
  1949  						for _, r := range dinfo[idx].out {
  1950  							if r != noRegister && mask.minus(s.used).hasReg(r) {
  1951  								// Desired register is allowed and unused.
  1952  								mask = regMaskAt(r)
  1953  								break
  1954  							}
  1955  						}
  1956  					}
  1957  					if out.idx == 1 {
  1958  						if prefs, ok := desiredSecondReg[v.ID]; ok {
  1959  							for _, r := range prefs {
  1960  								if r != noRegister && mask.minus(s.used).hasReg(r) {
  1961  									// Desired register is allowed and unused.
  1962  									mask = regMaskAt(r)
  1963  									break
  1964  								}
  1965  							}
  1966  						}
  1967  					}
  1968  					// Avoid registers we're saving for other values.
  1969  					if !mask.minus(desired.avoid).minus(s.nospill).minus(s.used).empty() {
  1970  						mask = mask.minus(desired.avoid)
  1971  					}
  1972  					r := s.allocReg(mask, v)
  1973  					if out.idx > maxOutIdx {
  1974  						maxOutIdx = out.idx
  1975  					}
  1976  					outRegs[out.idx] = r
  1977  					used = used.addReg(r)
  1978  					s.tmpused = s.tmpused.addReg(r)
  1979  				}
  1980  				// Record register choices
  1981  				if v.Type.IsTuple() {
  1982  					var outLocs LocPair
  1983  					if r := outRegs[0]; r != noRegister {
  1984  						outLocs[0] = &s.registers[r]
  1985  					}
  1986  					if r := outRegs[1]; r != noRegister {
  1987  						outLocs[1] = &s.registers[r]
  1988  					}
  1989  					s.f.setHome(v, outLocs)
  1990  					// Note that subsequent SelectX instructions will do the assignReg calls.
  1991  				} else if v.Type.IsResults() {
  1992  					// preallocate outLocs to the right size, which is maxOutIdx+1
  1993  					outLocs := make(LocResults, maxOutIdx+1, maxOutIdx+1)
  1994  					for i := 0; i <= maxOutIdx; i++ {
  1995  						if r := outRegs[i]; r != noRegister {
  1996  							outLocs[i] = &s.registers[r]
  1997  						}
  1998  					}
  1999  					s.f.setHome(v, outLocs)
  2000  				} else {
  2001  					if r := outRegs[0]; r != noRegister {
  2002  						s.assignReg(r, v, v)
  2003  					}
  2004  				}
  2005  				if tmpReg != noRegister {
  2006  					// Remember the temp register allocation, if any.
  2007  					if s.f.tempRegs == nil {
  2008  						s.f.tempRegs = map[ID]*Register{}
  2009  					}
  2010  					s.f.tempRegs[v.ID] = &s.registers[tmpReg]
  2011  				}
  2012  			}
  2013  
  2014  			// deallocate dead args, if we have not done so
  2015  			if opcodeTable[v.Op].resultNotInArgs {
  2016  				s.nospill = regMask{}
  2017  				s.advanceUses(v) // frees any registers holding args that are no longer live
  2018  			}
  2019  			s.tmpused = regMask{}
  2020  
  2021  			// Issue the Value itself.
  2022  			for i, a := range args {
  2023  				v.SetArg(i, a) // use register version of arguments
  2024  			}
  2025  			b.Values = append(b.Values, v)
  2026  			s.dropIfUnused(v)
  2027  		}
  2028  
  2029  		// Copy the control values - we need this so we can reduce the
  2030  		// uses property of these values later.
  2031  		controls := append(make([]*Value, 0, 2), b.ControlValues()...)
  2032  
  2033  		// Load control values into registers.
  2034  		for i, v := range b.ControlValues() {
  2035  			if !s.values[v.ID].needReg {
  2036  				continue
  2037  			}
  2038  			if s.f.pass.debug > regDebug {
  2039  				fmt.Printf("  processing control %s\n", v.LongString())
  2040  			}
  2041  			// We assume that a control input can be passed in any
  2042  			// type-compatible register. If this turns out not to be true,
  2043  			// we'll need to introduce a regspec for a block's control value.
  2044  			b.ReplaceControl(i, s.allocValToReg(v, s.compatRegs(v.Type), false, b.Pos))
  2045  		}
  2046  
  2047  		// Reduce the uses of the control values once registers have been loaded.
  2048  		// This loop is equivalent to the advanceUses method.
  2049  		for _, v := range controls {
  2050  			vi := &s.values[v.ID]
  2051  			if !vi.needReg {
  2052  				continue
  2053  			}
  2054  			// Remove this use from the uses list.
  2055  			u := vi.uses
  2056  			vi.uses = u.next
  2057  			if u.next == nil {
  2058  				s.freeRegs(vi.regs) // value is dead
  2059  			}
  2060  			u.next = s.freeUseRecords
  2061  			s.freeUseRecords = u
  2062  		}
  2063  
  2064  		// If we are approaching a merge point and we are the primary
  2065  		// predecessor of it, find live values that we use soon after
  2066  		// the merge point and promote them to registers now.
  2067  		if len(b.Succs) == 1 {
  2068  			if s.f.Config.hasGReg && s.regs[s.GReg].v != nil {
  2069  				s.freeReg(s.GReg) // Spill value in G register before any merge.
  2070  			}
  2071  			if s.blockOrder[b.ID] > s.blockOrder[b.Succs[0].b.ID] {
  2072  				// No point if we've already regalloc'd the destination.
  2073  				goto badloop
  2074  			}
  2075  			// For this to be worthwhile, the loop must have no calls in it.
  2076  			top := b.Succs[0].b
  2077  			loop := s.loopnest.b2l[top.ID]
  2078  			if loop == nil || loop.header != top || loop.containsUnavoidableCall {
  2079  				goto badloop
  2080  			}
  2081  
  2082  			// Look into target block, find Phi arguments that come from b.
  2083  			phiArgs := regValLiveSet // reuse this space
  2084  			phiArgs.clear()
  2085  			for _, v := range b.Succs[0].b.Values {
  2086  				if v.Op == OpPhi {
  2087  					phiArgs.add(v.Args[b.Succs[0].i].ID)
  2088  				}
  2089  			}
  2090  
  2091  			// Get mask of all registers that might be used soon in the destination.
  2092  			// We don't want to kick values out of these registers, but we will
  2093  			// kick out an unlikely-to-be-used value for a likely-to-be-used one.
  2094  			var likelyUsedRegs regMask
  2095  			for _, live := range s.live[b.ID] {
  2096  				if live.dist < unlikelyDistance {
  2097  					likelyUsedRegs = likelyUsedRegs.union(s.values[live.ID].regs)
  2098  				}
  2099  			}
  2100  			// Promote values we're going to use soon in the destination to registers.
  2101  			// Note that this iterates nearest-use first, as we sorted
  2102  			// live lists by distance in computeLive.
  2103  			for _, live := range s.live[b.ID] {
  2104  				if live.dist >= unlikelyDistance {
  2105  					// Don't preload anything live after the loop.
  2106  					continue
  2107  				}
  2108  				vid := live.ID
  2109  				vi := &s.values[vid]
  2110  				v := s.orig[vid]
  2111  				if phiArgs.contains(vid) {
  2112  					// A phi argument needs its value in a regular register,
  2113  					// as returned by compatRegs. Being in a fixed register
  2114  					// (e.g. the zero register) or being easily
  2115  					// rematerializeable isn't enough.
  2116  					if !vi.regs.intersect(s.compatRegs(v.Type)).empty() {
  2117  						continue
  2118  					}
  2119  				} else {
  2120  					if !vi.regs.empty() {
  2121  						continue
  2122  					}
  2123  					if vi.rematerializeable {
  2124  						// TODO: maybe we should not skip rematerializeable
  2125  						// values here. One rematerialization outside the loop
  2126  						// is better than N in the loop. But rematerializations
  2127  						// are cheap, and spilling another value may not be.
  2128  						// And we don't want to materialize the zero register
  2129  						// into a different register when it is just the
  2130  						// argument to a store.
  2131  						continue
  2132  					}
  2133  				}
  2134  				if vi.rematerializeable && s.f.Config.ctxt.Arch.Arch == sys.ArchWasm {
  2135  					continue
  2136  				}
  2137  				// Registers we could load v into.
  2138  				// Don't kick out other likely-used values.
  2139  				m := s.compatRegs(v.Type).minus(likelyUsedRegs)
  2140  				if m.empty() {
  2141  					// To many likely-used values to give them all a register.
  2142  					continue
  2143  				}
  2144  
  2145  				// Used desired register if available.
  2146  			outerloop:
  2147  				for _, e := range desired.entries {
  2148  					if e.ID != v.ID {
  2149  						continue
  2150  					}
  2151  					for _, r := range e.regs {
  2152  						if r != noRegister && m.hasReg(r) {
  2153  							m = regMaskAt(r)
  2154  							break outerloop
  2155  						}
  2156  					}
  2157  				}
  2158  				if !m.minus(desired.avoid).empty() {
  2159  					m = m.minus(desired.avoid)
  2160  				}
  2161  				s.allocValToReg(v, m, false, b.Pos)
  2162  				likelyUsedRegs = likelyUsedRegs.union(s.values[v.ID].regs)
  2163  			}
  2164  		}
  2165  	badloop:
  2166  		;
  2167  
  2168  		// Save end-of-block register state.
  2169  		// First count how many, this cuts allocations in half.
  2170  		k := 0
  2171  		for r := register(0); r < s.numRegs; r++ {
  2172  			v := s.regs[r].v
  2173  			if v == nil {
  2174  				continue
  2175  			}
  2176  			k++
  2177  		}
  2178  		regList := make([]endReg, 0, k)
  2179  		for r := register(0); r < s.numRegs; r++ {
  2180  			v := s.regs[r].v
  2181  			if v == nil {
  2182  				continue
  2183  			}
  2184  			regList = append(regList, endReg{r, v, s.regs[r].c})
  2185  		}
  2186  		s.endRegs[b.ID] = regList
  2187  
  2188  		if checkEnabled {
  2189  			regValLiveSet.clear()
  2190  			if s.live != nil {
  2191  				for _, x := range s.live[b.ID] {
  2192  					regValLiveSet.add(x.ID)
  2193  				}
  2194  			}
  2195  			for r := register(0); r < s.numRegs; r++ {
  2196  				v := s.regs[r].v
  2197  				if v == nil {
  2198  					continue
  2199  				}
  2200  				if !regValLiveSet.contains(v.ID) {
  2201  					s.f.Fatalf("val %s is in reg but not live at end of %s", v, b)
  2202  				}
  2203  			}
  2204  		}
  2205  
  2206  		// If a value is live at the end of the block and
  2207  		// isn't in a register, generate a use for the spill location.
  2208  		// We need to remember this information so that
  2209  		// the liveness analysis in stackalloc is correct.
  2210  		if s.live != nil {
  2211  			for _, e := range s.live[b.ID] {
  2212  				vi := &s.values[e.ID]
  2213  				if !vi.regs.empty() {
  2214  					// in a register, we'll use that source for the merge.
  2215  					continue
  2216  				}
  2217  				if vi.rematerializeable {
  2218  					// we'll rematerialize during the merge.
  2219  					continue
  2220  				}
  2221  				if s.f.pass.debug > regDebug {
  2222  					fmt.Printf("live-at-end spill for %s at %s\n", s.orig[e.ID], b)
  2223  				}
  2224  				spill := s.makeSpill(s.orig[e.ID], b)
  2225  				s.spillLive[b.ID] = append(s.spillLive[b.ID], spill.ID)
  2226  			}
  2227  
  2228  			// Clear any final uses.
  2229  			// All that is left should be the pseudo-uses added for values which
  2230  			// are live at the end of b.
  2231  			for _, e := range s.live[b.ID] {
  2232  				u := s.values[e.ID].uses
  2233  				if u == nil {
  2234  					f.Fatalf("live at end, no uses v%d", e.ID)
  2235  				}
  2236  				if u.next != nil {
  2237  					f.Fatalf("live at end, too many uses v%d", e.ID)
  2238  				}
  2239  				s.values[e.ID].uses = nil
  2240  				u.next = s.freeUseRecords
  2241  				s.freeUseRecords = u
  2242  			}
  2243  		}
  2244  
  2245  		// allocReg may have dropped registers from startRegsMask that
  2246  		// aren't actually needed in startRegs. Synchronize back to
  2247  		// startRegs.
  2248  		//
  2249  		// This must be done before placing spills, which will look at
  2250  		// startRegs to decide if a block is a valid block for a spill.
  2251  		if c := countRegs(s.startRegsMask); c != len(s.startRegs[b.ID]) {
  2252  			regs := make([]startReg, 0, c)
  2253  			for _, sr := range s.startRegs[b.ID] {
  2254  				if !s.startRegsMask.hasReg(sr.r) {
  2255  					continue
  2256  				}
  2257  				regs = append(regs, sr)
  2258  			}
  2259  			s.startRegs[b.ID] = regs
  2260  		}
  2261  	}
  2262  
  2263  	// Decide where the spills we generated will go.
  2264  	s.placeSpills()
  2265  
  2266  	// Anything that didn't get a register gets a stack location here.
  2267  	// (StoreReg, stack-based phis, inputs, ...)
  2268  	stacklive := stackalloc(s.f, s.spillLive)
  2269  
  2270  	// Fix up all merge edges.
  2271  	s.shuffle(stacklive)
  2272  
  2273  	// Erase any copies we never used.
  2274  	// Also, an unused copy might be the only use of another copy,
  2275  	// so continue erasing until we reach a fixed point.
  2276  	for {
  2277  		progress := false
  2278  		for c, used := range s.copies {
  2279  			if !used && c.Uses == 0 {
  2280  				if s.f.pass.debug > regDebug {
  2281  					fmt.Printf("delete copied value %s\n", c.LongString())
  2282  				}
  2283  				c.resetArgs()
  2284  				f.freeValue(c)
  2285  				delete(s.copies, c)
  2286  				progress = true
  2287  			}
  2288  		}
  2289  		if !progress {
  2290  			break
  2291  		}
  2292  	}
  2293  
  2294  	for _, b := range s.visitOrder {
  2295  		i := 0
  2296  		for _, v := range b.Values {
  2297  			if v.Op == OpInvalid {
  2298  				continue
  2299  			}
  2300  			b.Values[i] = v
  2301  			i++
  2302  		}
  2303  		b.Values = b.Values[:i]
  2304  	}
  2305  }
  2306  
  2307  func (s *regAllocState) placeSpills() {
  2308  	mustBeFirst := func(op Op) bool {
  2309  		return op.isLoweredGetClosurePtr() || op == OpPhi || op == OpArgIntReg || op == OpArgFloatReg
  2310  	}
  2311  
  2312  	// Start maps block IDs to the list of spills
  2313  	// that go at the start of the block (but after any phis).
  2314  	start := map[ID][]*Value{}
  2315  	// After maps value IDs to the list of spills
  2316  	// that go immediately after that value ID.
  2317  	after := map[ID][]*Value{}
  2318  
  2319  	for i := range s.values {
  2320  		vi := s.values[i]
  2321  		spill := vi.spill
  2322  		if spill == nil {
  2323  			continue
  2324  		}
  2325  		if spill.Block != nil {
  2326  			// Some spills are already fully set up,
  2327  			// like OpArgs and stack-based phis.
  2328  			continue
  2329  		}
  2330  		v := s.orig[i]
  2331  
  2332  		// Walk down the dominator tree looking for a good place to
  2333  		// put the spill of v.  At the start "best" is the best place
  2334  		// we have found so far.
  2335  		// TODO: find a way to make this O(1) without arbitrary cutoffs.
  2336  		if v == nil {
  2337  			panic(fmt.Errorf("nil v, s.orig[%d], vi = %v, spill = %s", i, vi, spill.LongString()))
  2338  		}
  2339  		best := v.Block
  2340  		bestArg := v
  2341  		var bestDepth int16
  2342  		if s.loopnest != nil && s.loopnest.b2l[best.ID] != nil {
  2343  			bestDepth = s.loopnest.b2l[best.ID].depth
  2344  		}
  2345  		b := best
  2346  		const maxSpillSearch = 100
  2347  		for i := 0; i < maxSpillSearch; i++ {
  2348  			// Find the child of b in the dominator tree which
  2349  			// dominates all restores.
  2350  			p := b
  2351  			b = nil
  2352  			for c := s.sdom.Child(p); c != nil && i < maxSpillSearch; c, i = s.sdom.Sibling(c), i+1 {
  2353  				if s.sdom[c.ID].entry <= vi.restoreMin && s.sdom[c.ID].exit >= vi.restoreMax {
  2354  					// c also dominates all restores.  Walk down into c.
  2355  					b = c
  2356  					break
  2357  				}
  2358  			}
  2359  			if b == nil {
  2360  				// Ran out of blocks which dominate all restores.
  2361  				break
  2362  			}
  2363  
  2364  			var depth int16
  2365  			if s.loopnest != nil && s.loopnest.b2l[b.ID] != nil {
  2366  				depth = s.loopnest.b2l[b.ID].depth
  2367  			}
  2368  			if depth > bestDepth {
  2369  				// Don't push the spill into a deeper loop.
  2370  				continue
  2371  			}
  2372  
  2373  			// If v is in a register at the start of b, we can
  2374  			// place the spill here (after the phis).
  2375  			if len(b.Preds) == 1 {
  2376  				for _, e := range s.endRegs[b.Preds[0].b.ID] {
  2377  					if e.v == v {
  2378  						// Found a better spot for the spill.
  2379  						best = b
  2380  						bestArg = e.c
  2381  						bestDepth = depth
  2382  						break
  2383  					}
  2384  				}
  2385  			} else {
  2386  				for _, e := range s.startRegs[b.ID] {
  2387  					if e.v == v {
  2388  						// Found a better spot for the spill.
  2389  						best = b
  2390  						bestArg = e.c
  2391  						bestDepth = depth
  2392  						break
  2393  					}
  2394  				}
  2395  			}
  2396  		}
  2397  
  2398  		// Put the spill in the best block we found.
  2399  		spill.Block = best
  2400  		spill.AddArg(bestArg)
  2401  		if best == v.Block && !mustBeFirst(v.Op) {
  2402  			// Place immediately after v.
  2403  			after[v.ID] = append(after[v.ID], spill)
  2404  		} else {
  2405  			// Place at the start of best block.
  2406  			start[best.ID] = append(start[best.ID], spill)
  2407  		}
  2408  	}
  2409  
  2410  	// Insert spill instructions into the block schedules.
  2411  	var oldSched []*Value
  2412  	for _, b := range s.visitOrder {
  2413  		nfirst := 0
  2414  		for _, v := range b.Values {
  2415  			if !mustBeFirst(v.Op) {
  2416  				break
  2417  			}
  2418  			nfirst++
  2419  		}
  2420  		oldSched = append(oldSched[:0], b.Values[nfirst:]...)
  2421  		b.Values = b.Values[:nfirst]
  2422  		b.Values = append(b.Values, start[b.ID]...)
  2423  		for _, v := range oldSched {
  2424  			b.Values = append(b.Values, v)
  2425  			b.Values = append(b.Values, after[v.ID]...)
  2426  		}
  2427  	}
  2428  }
  2429  
  2430  // shuffle fixes up all the merge edges (those going into blocks of indegree > 1).
  2431  func (s *regAllocState) shuffle(stacklive [][]ID) {
  2432  	var e edgeState
  2433  	e.s = s
  2434  	e.cache = map[ID][]*Value{}
  2435  	e.contents = map[Location]contentRecord{}
  2436  	if s.f.pass.debug > regDebug {
  2437  		fmt.Printf("shuffle %s\n", s.f.Name)
  2438  		fmt.Println(s.f.String())
  2439  	}
  2440  
  2441  	for _, b := range s.visitOrder {
  2442  		if len(b.Preds) <= 1 {
  2443  			continue
  2444  		}
  2445  		e.b = b
  2446  		for i, edge := range b.Preds {
  2447  			p := edge.b
  2448  			e.p = p
  2449  			e.setup(i, s.endRegs[p.ID], s.startRegs[b.ID], stacklive[p.ID])
  2450  			e.process()
  2451  		}
  2452  	}
  2453  
  2454  	if s.f.pass.debug > regDebug {
  2455  		fmt.Printf("post shuffle %s\n", s.f.Name)
  2456  		fmt.Println(s.f.String())
  2457  	}
  2458  }
  2459  
  2460  type edgeState struct {
  2461  	s    *regAllocState
  2462  	p, b *Block // edge goes from p->b.
  2463  
  2464  	// for each pre-regalloc value, a list of equivalent cached values
  2465  	cache      map[ID][]*Value
  2466  	cachedVals []ID // (superset of) keys of the above map, for deterministic iteration
  2467  
  2468  	// map from location to the value it contains
  2469  	contents map[Location]contentRecord
  2470  
  2471  	// desired destination locations
  2472  	destinations []dstRecord
  2473  	extra        []dstRecord
  2474  
  2475  	usedRegs              regMask // registers currently holding something
  2476  	uniqueRegs            regMask // registers holding the only copy of a value
  2477  	finalRegs             regMask // registers holding final target
  2478  	rematerializeableRegs regMask // registers that hold rematerializeable values
  2479  }
  2480  
  2481  type contentRecord struct {
  2482  	vid   ID       // pre-regalloc value
  2483  	c     *Value   // cached value
  2484  	final bool     // this is a satisfied destination
  2485  	pos   src.XPos // source position of use of the value
  2486  }
  2487  
  2488  type dstRecord struct {
  2489  	loc    Location // register or stack slot
  2490  	vid    ID       // pre-regalloc value it should contain
  2491  	splice **Value  // place to store reference to the generating instruction
  2492  	pos    src.XPos // source position of use of this location
  2493  }
  2494  
  2495  // setup initializes the edge state for shuffling.
  2496  func (e *edgeState) setup(idx int, srcReg []endReg, dstReg []startReg, stacklive []ID) {
  2497  	if e.s.f.pass.debug > regDebug {
  2498  		fmt.Printf("edge %s->%s\n", e.p, e.b)
  2499  	}
  2500  
  2501  	// Clear state.
  2502  	clear(e.cache)
  2503  	e.cachedVals = e.cachedVals[:0]
  2504  	clear(e.contents)
  2505  	e.usedRegs = regMask{}
  2506  	e.uniqueRegs = regMask{}
  2507  	e.finalRegs = regMask{}
  2508  	e.rematerializeableRegs = regMask{}
  2509  
  2510  	// Live registers can be sources.
  2511  	for _, x := range srcReg {
  2512  		e.set(&e.s.registers[x.r], x.v.ID, x.c, false, src.NoXPos) // don't care the position of the source
  2513  	}
  2514  	// So can all of the spill locations.
  2515  	for _, spillID := range stacklive {
  2516  		v := e.s.orig[spillID]
  2517  		spill := e.s.values[v.ID].spill
  2518  		if !e.s.sdom.IsAncestorEq(spill.Block, e.p) {
  2519  			// Spills were placed that only dominate the uses found
  2520  			// during the first regalloc pass. The edge fixup code
  2521  			// can't use a spill location if the spill doesn't dominate
  2522  			// the edge.
  2523  			// We are guaranteed that if the spill doesn't dominate this edge,
  2524  			// then the value is available in a register (because we called
  2525  			// makeSpill for every value not in a register at the start
  2526  			// of an edge).
  2527  			continue
  2528  		}
  2529  		e.set(e.s.f.getHome(spillID), v.ID, spill, false, src.NoXPos) // don't care the position of the source
  2530  	}
  2531  
  2532  	// Figure out all the destinations we need.
  2533  	dsts := e.destinations[:0]
  2534  	for _, x := range dstReg {
  2535  		dsts = append(dsts, dstRecord{&e.s.registers[x.r], x.v.ID, nil, x.pos})
  2536  	}
  2537  	// Phis need their args to end up in a specific location.
  2538  	for _, v := range e.b.Values {
  2539  		if v.Op != OpPhi {
  2540  			break
  2541  		}
  2542  		loc := e.s.f.getHome(v.ID)
  2543  		if loc == nil {
  2544  			continue
  2545  		}
  2546  		dsts = append(dsts, dstRecord{loc, v.Args[idx].ID, &v.Args[idx], v.Pos})
  2547  	}
  2548  	e.destinations = dsts
  2549  
  2550  	if e.s.f.pass.debug > regDebug {
  2551  		for _, vid := range e.cachedVals {
  2552  			a := e.cache[vid]
  2553  			for _, c := range a {
  2554  				fmt.Printf("src %s: v%d cache=%s\n", e.s.f.getHome(c.ID), vid, c)
  2555  			}
  2556  		}
  2557  		for _, d := range e.destinations {
  2558  			fmt.Printf("dst %s: v%d\n", d.loc, d.vid)
  2559  		}
  2560  	}
  2561  }
  2562  
  2563  // process generates code to move all the values to the right destination locations.
  2564  func (e *edgeState) process() {
  2565  	dsts := e.destinations
  2566  
  2567  	// Process the destinations until they are all satisfied.
  2568  	for len(dsts) > 0 {
  2569  		i := 0
  2570  		for _, d := range dsts {
  2571  			if !e.processDest(d.loc, d.vid, d.splice, d.pos) {
  2572  				// Failed - save for next iteration.
  2573  				dsts[i] = d
  2574  				i++
  2575  			}
  2576  		}
  2577  		if i < len(dsts) {
  2578  			// Made some progress. Go around again.
  2579  			dsts = dsts[:i]
  2580  
  2581  			// Append any extras destinations we generated.
  2582  			dsts = append(dsts, e.extra...)
  2583  			e.extra = e.extra[:0]
  2584  			continue
  2585  		}
  2586  
  2587  		// We made no progress. That means that any
  2588  		// remaining unsatisfied moves are in simple cycles.
  2589  		// For example, A -> B -> C -> D -> A.
  2590  		//   A ----> B
  2591  		//   ^       |
  2592  		//   |       |
  2593  		//   |       v
  2594  		//   D <---- C
  2595  
  2596  		// To break the cycle, we pick an unused register, say R,
  2597  		// and put a copy of B there.
  2598  		//   A ----> B
  2599  		//   ^       |
  2600  		//   |       |
  2601  		//   |       v
  2602  		//   D <---- C <---- R=copyofB
  2603  		// When we resume the outer loop, the A->B move can now proceed,
  2604  		// and eventually the whole cycle completes.
  2605  
  2606  		// Copy any cycle location to a temp register. This duplicates
  2607  		// one of the cycle entries, allowing the just duplicated value
  2608  		// to be overwritten and the cycle to proceed.
  2609  		d := dsts[0]
  2610  		loc := d.loc
  2611  		vid := e.contents[loc].vid
  2612  		c := e.contents[loc].c
  2613  		r := e.findRegFor(c.Type)
  2614  		if e.s.f.pass.debug > regDebug {
  2615  			fmt.Printf("breaking cycle with v%d in %s:%s\n", vid, loc, c)
  2616  		}
  2617  		e.erase(r)
  2618  		pos := d.pos.WithNotStmt()
  2619  		if _, isReg := loc.(*Register); isReg {
  2620  			c = e.p.NewValue1(pos, OpCopy, c.Type, c)
  2621  		} else {
  2622  			c = e.p.NewValue1(pos, OpLoadReg, c.Type, c)
  2623  		}
  2624  		e.set(r, vid, c, false, pos)
  2625  		if c.Op == OpLoadReg && e.s.isGReg(register(r.(*Register).num)) {
  2626  			e.s.f.Fatalf("process.OpLoadReg targeting g: " + c.LongString())
  2627  		}
  2628  	}
  2629  }
  2630  
  2631  // processDest generates code to put value vid into location loc. Returns true
  2632  // if progress was made.
  2633  func (e *edgeState) processDest(loc Location, vid ID, splice **Value, pos src.XPos) bool {
  2634  	pos = pos.WithNotStmt()
  2635  	occupant := e.contents[loc]
  2636  	if occupant.vid == vid {
  2637  		// Value is already in the correct place.
  2638  		e.contents[loc] = contentRecord{vid, occupant.c, true, pos}
  2639  		if splice != nil {
  2640  			(*splice).Uses--
  2641  			*splice = occupant.c
  2642  			occupant.c.Uses++
  2643  		}
  2644  		// Note: if splice==nil then c will appear dead. This is
  2645  		// non-SSA formed code, so be careful after this pass not to run
  2646  		// deadcode elimination.
  2647  		if _, ok := e.s.copies[occupant.c]; ok {
  2648  			// The copy at occupant.c was used to avoid spill.
  2649  			e.s.copies[occupant.c] = true
  2650  		}
  2651  		return true
  2652  	}
  2653  
  2654  	// Check if we're allowed to clobber the destination location.
  2655  	if len(e.cache[occupant.vid]) == 1 && !e.s.values[occupant.vid].rematerializeable && !opcodeTable[e.s.orig[occupant.vid].Op].fixedReg {
  2656  		// We can't overwrite the last copy
  2657  		// of a value that needs to survive.
  2658  		return false
  2659  	}
  2660  
  2661  	// Copy from a source of v, register preferred.
  2662  	v := e.s.orig[vid]
  2663  	var c *Value
  2664  	var src Location
  2665  	if e.s.f.pass.debug > regDebug {
  2666  		fmt.Printf("moving v%d to %s\n", vid, loc)
  2667  		fmt.Printf("sources of v%d:", vid)
  2668  	}
  2669  	if opcodeTable[v.Op].fixedReg {
  2670  		c = v
  2671  		src = e.s.f.getHome(v.ID)
  2672  	} else {
  2673  		for _, w := range e.cache[vid] {
  2674  			h := e.s.f.getHome(w.ID)
  2675  			if e.s.f.pass.debug > regDebug {
  2676  				fmt.Printf(" %s:%s", h, w)
  2677  			}
  2678  			_, isreg := h.(*Register)
  2679  			if src == nil || isreg {
  2680  				c = w
  2681  				src = h
  2682  			}
  2683  		}
  2684  	}
  2685  	if e.s.f.pass.debug > regDebug {
  2686  		if src != nil {
  2687  			fmt.Printf(" [use %s]\n", src)
  2688  		} else {
  2689  			fmt.Printf(" [no source]\n")
  2690  		}
  2691  	}
  2692  	_, dstReg := loc.(*Register)
  2693  
  2694  	// Pre-clobber destination. This avoids the
  2695  	// following situation:
  2696  	//   - v is currently held in R0 and stacktmp0.
  2697  	//   - We want to copy stacktmp1 to stacktmp0.
  2698  	//   - We choose R0 as the temporary register.
  2699  	// During the copy, both R0 and stacktmp0 are
  2700  	// clobbered, losing both copies of v. Oops!
  2701  	// Erasing the destination early means R0 will not
  2702  	// be chosen as the temp register, as it will then
  2703  	// be the last copy of v.
  2704  	e.erase(loc)
  2705  	var x *Value
  2706  	if c == nil || e.s.values[vid].rematerializeable {
  2707  		if !e.s.values[vid].rematerializeable {
  2708  			e.s.f.Fatalf("can't find source for %s->%s: %s\n", e.p, e.b, v.LongString())
  2709  		}
  2710  		if dstReg {
  2711  			// We want to rematerialize v into a register that is incompatible with v's op's register mask.
  2712  			// Instead of setting the wrong register for the rematerialized v, we should find the right register
  2713  			// for it and emit an additional copy to move to the desired register.
  2714  			// For #70451.
  2715  			if !e.s.regspec(v).outputs[0].regs.hasReg(register(loc.(*Register).num)) {
  2716  				_, srcReg := src.(*Register)
  2717  				if srcReg {
  2718  					// It exists in a valid register already, so just copy it to the desired register
  2719  					// If src is a Register, c must have already been set.
  2720  					x = e.p.NewValue1(pos, OpCopy, c.Type, c)
  2721  				} else {
  2722  					// We need a tmp register
  2723  					x = v.copyInto(e.p)
  2724  					r := e.findRegFor(x.Type)
  2725  					e.erase(r)
  2726  					// Rematerialize to the tmp register
  2727  					e.set(r, vid, x, false, pos)
  2728  					// Copy from tmp to the desired register
  2729  					x = e.p.NewValue1(pos, OpCopy, x.Type, x)
  2730  				}
  2731  			} else {
  2732  				x = v.copyInto(e.p)
  2733  			}
  2734  		} else {
  2735  			// Rematerialize into stack slot. Need a free
  2736  			// register to accomplish this.
  2737  			r := e.findRegFor(v.Type)
  2738  			e.erase(r)
  2739  			x = v.copyIntoWithXPos(e.p, pos)
  2740  			e.set(r, vid, x, false, pos)
  2741  			// Make sure we spill with the size of the slot, not the
  2742  			// size of x (which might be wider due to our dropping
  2743  			// of narrowing conversions).
  2744  			x = e.p.NewValue1(pos, OpStoreReg, loc.(LocalSlot).Type, x)
  2745  		}
  2746  	} else {
  2747  		// Emit move from src to dst.
  2748  		_, srcReg := src.(*Register)
  2749  		if srcReg {
  2750  			if dstReg {
  2751  				x = e.p.NewValue1(pos, OpCopy, c.Type, c)
  2752  			} else {
  2753  				x = e.p.NewValue1(pos, OpStoreReg, loc.(LocalSlot).Type, c)
  2754  			}
  2755  		} else {
  2756  			if dstReg {
  2757  				x = e.p.NewValue1(pos, OpLoadReg, c.Type, c)
  2758  			} else {
  2759  				// mem->mem. Use temp register.
  2760  				r := e.findRegFor(c.Type)
  2761  				e.erase(r)
  2762  				t := e.p.NewValue1(pos, OpLoadReg, c.Type, c)
  2763  				e.set(r, vid, t, false, pos)
  2764  				x = e.p.NewValue1(pos, OpStoreReg, loc.(LocalSlot).Type, t)
  2765  			}
  2766  		}
  2767  	}
  2768  	e.set(loc, vid, x, true, pos)
  2769  	if x.Op == OpLoadReg && e.s.isGReg(register(loc.(*Register).num)) {
  2770  		e.s.f.Fatalf("processDest.OpLoadReg targeting g: " + x.LongString())
  2771  	}
  2772  	if splice != nil {
  2773  		(*splice).Uses--
  2774  		*splice = x
  2775  		x.Uses++
  2776  	}
  2777  	return true
  2778  }
  2779  
  2780  // set changes the contents of location loc to hold the given value and its cached representative.
  2781  func (e *edgeState) set(loc Location, vid ID, c *Value, final bool, pos src.XPos) {
  2782  	e.s.f.setHome(c, loc)
  2783  	e.contents[loc] = contentRecord{vid, c, final, pos}
  2784  	a := e.cache[vid]
  2785  	if len(a) == 0 {
  2786  		e.cachedVals = append(e.cachedVals, vid)
  2787  	}
  2788  	a = append(a, c)
  2789  	e.cache[vid] = a
  2790  	if r, ok := loc.(*Register); ok {
  2791  		if e.usedRegs.hasReg(register(r.num)) {
  2792  			e.s.f.Fatalf("%v is already set (v%d/%v)", r, vid, c)
  2793  		}
  2794  		e.usedRegs = e.usedRegs.addReg(register(r.num))
  2795  		if final {
  2796  			e.finalRegs = e.finalRegs.addReg(register(r.num))
  2797  		}
  2798  		if len(a) == 1 {
  2799  			e.uniqueRegs = e.uniqueRegs.addReg(register(r.num))
  2800  		}
  2801  		if len(a) == 2 {
  2802  			if t, ok := e.s.f.getHome(a[0].ID).(*Register); ok {
  2803  				e.uniqueRegs = e.uniqueRegs.removeReg(register(t.num))
  2804  			}
  2805  		}
  2806  		if e.s.values[vid].rematerializeable {
  2807  			e.rematerializeableRegs = e.rematerializeableRegs.addReg(register(r.num))
  2808  		}
  2809  	}
  2810  	if e.s.f.pass.debug > regDebug {
  2811  		fmt.Printf("%s\n", c.LongString())
  2812  		fmt.Printf("v%d now available in %s:%s\n", vid, loc, c)
  2813  	}
  2814  }
  2815  
  2816  // erase removes any user of loc.
  2817  func (e *edgeState) erase(loc Location) {
  2818  	cr := e.contents[loc]
  2819  	if cr.c == nil {
  2820  		return
  2821  	}
  2822  	vid := cr.vid
  2823  
  2824  	if cr.final {
  2825  		// Add a destination to move this value back into place.
  2826  		// Make sure it gets added to the tail of the destination queue
  2827  		// so we make progress on other moves first.
  2828  		e.extra = append(e.extra, dstRecord{loc, cr.vid, nil, cr.pos})
  2829  	}
  2830  
  2831  	// Remove c from the list of cached values.
  2832  	a := e.cache[vid]
  2833  	for i, c := range a {
  2834  		if e.s.f.getHome(c.ID) == loc {
  2835  			if e.s.f.pass.debug > regDebug {
  2836  				fmt.Printf("v%d no longer available in %s:%s\n", vid, loc, c)
  2837  			}
  2838  			a[i], a = a[len(a)-1], a[:len(a)-1]
  2839  			break
  2840  		}
  2841  	}
  2842  	e.cache[vid] = a
  2843  
  2844  	// Update register masks.
  2845  	if r, ok := loc.(*Register); ok {
  2846  		e.usedRegs = e.usedRegs.removeReg(register(r.num))
  2847  		if cr.final {
  2848  			e.finalRegs = e.finalRegs.removeReg(register(r.num))
  2849  		}
  2850  		e.rematerializeableRegs = e.rematerializeableRegs.removeReg(register(r.num))
  2851  	}
  2852  	if len(a) == 1 {
  2853  		if r, ok := e.s.f.getHome(a[0].ID).(*Register); ok {
  2854  			e.uniqueRegs = e.uniqueRegs.addReg(register(r.num))
  2855  		}
  2856  	}
  2857  }
  2858  
  2859  // findRegFor finds a register we can use to make a temp copy of type typ.
  2860  func (e *edgeState) findRegFor(typ *types.Type) Location {
  2861  	// Which registers are possibilities.
  2862  	m := e.s.compatRegs(typ)
  2863  
  2864  	// Pick a register. In priority order:
  2865  	// 1) an unused register
  2866  	// 2) a non-unique register not holding a final value
  2867  	// 3) a non-unique register
  2868  	// 4) a register holding a rematerializeable value
  2869  	x := m.minus(e.usedRegs)
  2870  	if !x.empty() {
  2871  		return &e.s.registers[e.s.pickReg(x)]
  2872  	}
  2873  	x = m.minus(e.uniqueRegs).minus(e.finalRegs)
  2874  	if !x.empty() {
  2875  		return &e.s.registers[e.s.pickReg(x)]
  2876  	}
  2877  	x = m.minus(e.uniqueRegs)
  2878  	if !x.empty() {
  2879  		return &e.s.registers[e.s.pickReg(x)]
  2880  	}
  2881  	x = m.intersect(e.rematerializeableRegs)
  2882  	if !x.empty() {
  2883  		return &e.s.registers[e.s.pickReg(x)]
  2884  	}
  2885  
  2886  	// No register is available.
  2887  	// Pick a register to spill.
  2888  	for _, vid := range e.cachedVals {
  2889  		a := e.cache[vid]
  2890  		for _, c := range a {
  2891  			if r, ok := e.s.f.getHome(c.ID).(*Register); ok && m.hasReg(register(r.num)) {
  2892  				if !c.rematerializeable() {
  2893  					x := e.p.NewValue1(c.Pos, OpStoreReg, c.Type, c)
  2894  					// Allocate a temp location to spill a register to.
  2895  					t := LocalSlot{N: e.s.f.NewLocal(c.Pos, c.Type), Type: c.Type}
  2896  					// TODO: reuse these slots. They'll need to be erased first.
  2897  					e.set(t, vid, x, false, c.Pos)
  2898  					if e.s.f.pass.debug > regDebug {
  2899  						fmt.Printf("  SPILL %s->%s %s\n", r, t, x.LongString())
  2900  					}
  2901  				}
  2902  				// r will now be overwritten by the caller. At some point
  2903  				// later, the newly saved value will be moved back to its
  2904  				// final destination in processDest.
  2905  				return r
  2906  			}
  2907  		}
  2908  	}
  2909  
  2910  	fmt.Printf("m:%d unique:%d final:%d rematerializable:%d\n", m, e.uniqueRegs, e.finalRegs, e.rematerializeableRegs)
  2911  	for _, vid := range e.cachedVals {
  2912  		a := e.cache[vid]
  2913  		for _, c := range a {
  2914  			fmt.Printf("v%d: %s %s\n", vid, c, e.s.f.getHome(c.ID))
  2915  		}
  2916  	}
  2917  	e.s.f.Fatalf("can't find empty register on edge %s->%s", e.p, e.b)
  2918  	return nil
  2919  }
  2920  
  2921  // rematerializeable reports whether the register allocator should recompute
  2922  // a value instead of spilling/restoring it.
  2923  func (v *Value) rematerializeable() bool {
  2924  	if !opcodeTable[v.Op].rematerializeable {
  2925  		return false
  2926  	}
  2927  	for _, a := range v.Args {
  2928  		// Fixed-register allocations (SP, SB, etc.) are always available.
  2929  		// Any other argument of an opcode makes it not rematerializeable.
  2930  		if !opcodeTable[a.Op].fixedReg {
  2931  			return false
  2932  		}
  2933  	}
  2934  	return true
  2935  }
  2936  
  2937  type liveInfo struct {
  2938  	ID   ID       // ID of value
  2939  	dist int32    // # of instructions before next use
  2940  	pos  src.XPos // source position of next use
  2941  }
  2942  
  2943  // computeLive computes a map from block ID to a list of value IDs live at the end
  2944  // of that block. Together with the value ID is a count of how many instructions
  2945  // to the next use of that value. The resulting map is stored in s.live.
  2946  func (s *regAllocState) computeLive() {
  2947  	f := s.f
  2948  	// single block functions do not have variables that are live across
  2949  	// branches
  2950  	if len(f.Blocks) == 1 {
  2951  		return
  2952  	}
  2953  	po := f.postorder()
  2954  	s.live = make([][]liveInfo, f.NumBlocks())
  2955  	s.desired = make([]desiredState, f.NumBlocks())
  2956  	s.loopnest = f.loopnest()
  2957  
  2958  	rematIDs := make([]ID, 0, 64)
  2959  
  2960  	live := f.newSparseMapPos(f.NumValues())
  2961  	defer f.retSparseMapPos(live)
  2962  	t := f.newSparseMapPos(f.NumValues())
  2963  	defer f.retSparseMapPos(t)
  2964  
  2965  	s.loopnest.computeUnavoidableCalls()
  2966  
  2967  	// Liveness analysis.
  2968  	// This is an adapted version of the algorithm described in chapter 2.4.2
  2969  	// of Fabrice Rastello's On Sparse Intermediate Representations.
  2970  	//   https://web.archive.org/web/20240417212122if_/https://inria.hal.science/hal-00761555/file/habilitation.pdf#section.50
  2971  	//
  2972  	// For our implementation, we fall back to a traditional iterative algorithm when we encounter
  2973  	// Irreducible CFGs. They are very uncommon in Go code because they need to be constructed with
  2974  	// gotos and our current loopnest definition does not compute all the information that
  2975  	// we'd need to compute the loop ancestors for that step of the algorithm.
  2976  	//
  2977  	// Additionally, instead of only considering non-loop successors in the initial DFS phase,
  2978  	// we compute the liveout as the union of all successors. This larger liveout set is a subset
  2979  	// of the final liveout for the block and adding this information in the DFS phase means that
  2980  	// we get slightly more accurate distance information.
  2981  	var loopLiveIn map[*loop][]liveInfo
  2982  	var numCalls []int32
  2983  	if len(s.loopnest.loops) > 0 && !s.loopnest.hasIrreducible {
  2984  		loopLiveIn = make(map[*loop][]liveInfo)
  2985  		numCalls = f.Cache.allocInt32Slice(f.NumBlocks())
  2986  		defer f.Cache.freeInt32Slice(numCalls)
  2987  	}
  2988  
  2989  	for {
  2990  		changed := false
  2991  
  2992  		for _, b := range po {
  2993  			// Start with known live values at the end of the block.
  2994  			live.clear()
  2995  			for _, e := range s.live[b.ID] {
  2996  				live.set(e.ID, e.dist, e.pos)
  2997  			}
  2998  			update := false
  2999  			// arguments to phi nodes are live at this blocks out
  3000  			for _, e := range b.Succs {
  3001  				succ := e.b
  3002  				delta := branchDistance(b, succ)
  3003  				for _, v := range succ.Values {
  3004  					if v.Op != OpPhi {
  3005  						break
  3006  					}
  3007  					arg := v.Args[e.i]
  3008  					if s.values[arg.ID].needReg && (!live.contains(arg.ID) || delta < live.get(arg.ID)) {
  3009  						live.set(arg.ID, delta, v.Pos)
  3010  						update = true
  3011  					}
  3012  				}
  3013  			}
  3014  			if update {
  3015  				s.live[b.ID] = updateLive(live, s.live[b.ID])
  3016  			}
  3017  			// Add len(b.Values) to adjust from end-of-block distance
  3018  			// to beginning-of-block distance.
  3019  			c := live.contents()
  3020  			for i := range c {
  3021  				c[i].val += int32(len(b.Values))
  3022  			}
  3023  
  3024  			// Mark control values as live
  3025  			for _, c := range b.ControlValues() {
  3026  				if s.values[c.ID].needReg {
  3027  					live.set(c.ID, int32(len(b.Values)), b.Pos)
  3028  				}
  3029  			}
  3030  
  3031  			for i := len(b.Values) - 1; i >= 0; i-- {
  3032  				v := b.Values[i]
  3033  				live.remove(v.ID)
  3034  				if v.Op == OpPhi {
  3035  					continue
  3036  				}
  3037  				if opcodeTable[v.Op].call {
  3038  					if numCalls != nil {
  3039  						numCalls[b.ID]++
  3040  					}
  3041  					rematIDs = rematIDs[:0]
  3042  					c := live.contents()
  3043  					for i := range c {
  3044  						c[i].val += unlikelyDistance
  3045  						vid := c[i].key
  3046  						if s.values[vid].rematerializeable {
  3047  							rematIDs = append(rematIDs, vid)
  3048  						}
  3049  					}
  3050  					// We don't spill rematerializeable values, and assuming they
  3051  					// are live across a call would only force shuffle to add some
  3052  					// (dead) constant rematerialization. Remove them.
  3053  					for _, r := range rematIDs {
  3054  						live.remove(r)
  3055  					}
  3056  				}
  3057  				for _, a := range v.Args {
  3058  					if s.values[a.ID].needReg {
  3059  						live.set(a.ID, int32(i), v.Pos)
  3060  					}
  3061  				}
  3062  			}
  3063  			// This is a loop header, save our live-in so that
  3064  			// we can use it to fill in the loop bodies later
  3065  			if loopLiveIn != nil {
  3066  				loop := s.loopnest.b2l[b.ID]
  3067  				if loop != nil && loop.header.ID == b.ID {
  3068  					loopLiveIn[loop] = updateLive(live, nil)
  3069  				}
  3070  			}
  3071  			// For each predecessor of b, expand its list of live-at-end values.
  3072  			// invariant: live contains the values live at the start of b
  3073  			for _, e := range b.Preds {
  3074  				p := e.b
  3075  				delta := branchDistance(p, b)
  3076  
  3077  				// Start t off with the previously known live values at the end of p.
  3078  				t.clear()
  3079  				for _, e := range s.live[p.ID] {
  3080  					t.set(e.ID, e.dist, e.pos)
  3081  				}
  3082  				update := false
  3083  
  3084  				// Add new live values from scanning this block.
  3085  				for _, e := range live.contents() {
  3086  					d := e.val + delta
  3087  					if !t.contains(e.key) || d < t.get(e.key) {
  3088  						update = true
  3089  						t.set(e.key, d, e.pos)
  3090  					}
  3091  				}
  3092  
  3093  				if !update {
  3094  					continue
  3095  				}
  3096  				s.live[p.ID] = updateLive(t, s.live[p.ID])
  3097  				changed = true
  3098  			}
  3099  		}
  3100  
  3101  		// Doing a traditional iterative algorithm and have run
  3102  		// out of changes
  3103  		if !changed {
  3104  			break
  3105  		}
  3106  
  3107  		// Doing a pre-pass and will fill in the liveness information
  3108  		// later
  3109  		if loopLiveIn != nil {
  3110  			break
  3111  		}
  3112  		// For loopless code, we have full liveness info after a single
  3113  		// iteration
  3114  		if len(s.loopnest.loops) == 0 {
  3115  			break
  3116  		}
  3117  	}
  3118  	if f.pass.debug > regDebug {
  3119  		s.debugPrintLive("after dfs walk", f, s.live, s.desired)
  3120  	}
  3121  
  3122  	// irreducible CFGs and functions without loops are already
  3123  	// done, compute their desired registers and return
  3124  	if loopLiveIn == nil {
  3125  		s.computeDesired()
  3126  		return
  3127  	}
  3128  
  3129  	// Walk the loopnest from outer to inner, adding
  3130  	// all live-in values from their parent. Instead of
  3131  	// a recursive algorithm, iterate in depth order.
  3132  	// TODO(dmo): can we permute the loopnest? can we avoid this copy?
  3133  	loops := slices.Clone(s.loopnest.loops)
  3134  	slices.SortFunc(loops, func(a, b *loop) int {
  3135  		return cmp.Compare(a.depth, b.depth)
  3136  	})
  3137  
  3138  	loopset := f.newSparseMapPos(f.NumValues())
  3139  	defer f.retSparseMapPos(loopset)
  3140  	for _, loop := range loops {
  3141  		if loop.outer == nil {
  3142  			continue
  3143  		}
  3144  		livein := loopLiveIn[loop]
  3145  		loopset.clear()
  3146  		for _, l := range livein {
  3147  			loopset.set(l.ID, l.dist, l.pos)
  3148  		}
  3149  		update := false
  3150  		for _, l := range loopLiveIn[loop.outer] {
  3151  			if !loopset.contains(l.ID) {
  3152  				loopset.set(l.ID, l.dist, l.pos)
  3153  				update = true
  3154  			}
  3155  		}
  3156  		if update {
  3157  			loopLiveIn[loop] = updateLive(loopset, livein)
  3158  		}
  3159  	}
  3160  	// unknownDistance is a sentinel value for when we know a variable
  3161  	// is live at any given block, but we do not yet know how far until it's next
  3162  	// use. The distance will be computed later.
  3163  	const unknownDistance = -1
  3164  
  3165  	// add live-in values of the loop headers to their children.
  3166  	// This includes the loop headers themselves, since they can have values
  3167  	// that die in the middle of the block and aren't live-out
  3168  	for _, b := range po {
  3169  		loop := s.loopnest.b2l[b.ID]
  3170  		if loop == nil {
  3171  			continue
  3172  		}
  3173  		headerLive := loopLiveIn[loop]
  3174  		loopset.clear()
  3175  		for _, l := range s.live[b.ID] {
  3176  			loopset.set(l.ID, l.dist, l.pos)
  3177  		}
  3178  		update := false
  3179  		for _, l := range headerLive {
  3180  			if !loopset.contains(l.ID) {
  3181  				loopset.set(l.ID, unknownDistance, src.NoXPos)
  3182  				update = true
  3183  			}
  3184  		}
  3185  		if update {
  3186  			s.live[b.ID] = updateLive(loopset, s.live[b.ID])
  3187  		}
  3188  	}
  3189  	if f.pass.debug > regDebug {
  3190  		s.debugPrintLive("after live loop prop", f, s.live, s.desired)
  3191  	}
  3192  	// Filling in liveness from loops leaves some blocks with no distance information
  3193  	// Run over them and fill in the information from their successors.
  3194  	// To stabilize faster, we quit when no block has missing values and we only
  3195  	// look at blocks that still have missing values in subsequent iterations
  3196  	unfinishedBlocks := f.Cache.allocBlockSlice(len(po))
  3197  	defer f.Cache.freeBlockSlice(unfinishedBlocks)
  3198  	copy(unfinishedBlocks, po)
  3199  
  3200  	for len(unfinishedBlocks) > 0 {
  3201  		n := 0
  3202  		for _, b := range unfinishedBlocks {
  3203  			live.clear()
  3204  			unfinishedValues := 0
  3205  			for _, l := range s.live[b.ID] {
  3206  				if l.dist == unknownDistance {
  3207  					unfinishedValues++
  3208  				}
  3209  				live.set(l.ID, l.dist, l.pos)
  3210  			}
  3211  			update := false
  3212  			for _, e := range b.Succs {
  3213  				succ := e.b
  3214  				for _, l := range s.live[succ.ID] {
  3215  					if !live.contains(l.ID) || l.dist == unknownDistance {
  3216  						continue
  3217  					}
  3218  					dist := int32(len(succ.Values)) + l.dist + branchDistance(b, succ)
  3219  					dist += numCalls[succ.ID] * unlikelyDistance
  3220  					val := live.get(l.ID)
  3221  					switch {
  3222  					case val == unknownDistance:
  3223  						unfinishedValues--
  3224  						fallthrough
  3225  					case dist < val:
  3226  						update = true
  3227  						live.set(l.ID, dist, l.pos)
  3228  					}
  3229  				}
  3230  			}
  3231  			if update {
  3232  				s.live[b.ID] = updateLive(live, s.live[b.ID])
  3233  			}
  3234  			if unfinishedValues > 0 {
  3235  				unfinishedBlocks[n] = b
  3236  				n++
  3237  			}
  3238  		}
  3239  		unfinishedBlocks = unfinishedBlocks[:n]
  3240  	}
  3241  
  3242  	// Sort live values in order of their nearest next use.
  3243  	// Useful for promoting values to registers, nearest use first.
  3244  	for _, b := range f.Blocks {
  3245  		slices.SortFunc(s.live[b.ID], func(a, b liveInfo) int {
  3246  			if a.dist != b.dist {
  3247  				return cmp.Compare(a.dist, b.dist)
  3248  			}
  3249  			return cmp.Compare(a.ID, b.ID) // for deterministic sorting
  3250  		})
  3251  	}
  3252  
  3253  	s.computeDesired()
  3254  
  3255  	if f.pass.debug > regDebug {
  3256  		s.debugPrintLive("final", f, s.live, s.desired)
  3257  	}
  3258  }
  3259  
  3260  // computeDesired computes the desired register information at the end of each block.
  3261  // It is essentially a liveness analysis on machine registers instead of SSA values
  3262  // The desired register information is stored in s.desired.
  3263  func (s *regAllocState) computeDesired() {
  3264  
  3265  	// TODO: Can we speed this up using the liveness information we have already
  3266  	// from computeLive?
  3267  	var desired desiredState
  3268  	f := s.f
  3269  	po := f.postorder()
  3270  	maxPreds := 0
  3271  	for _, b := range f.Blocks {
  3272  		maxPreds = max(maxPreds, len(b.Preds))
  3273  	}
  3274  	// phiPrefs[i] collects desired registers for phi inputs coming from b.Preds[i].
  3275  	phiPrefs := make([]desiredState, maxPreds)
  3276  	for {
  3277  		changed := false
  3278  		for _, b := range po {
  3279  			desired.copy(&s.desired[b.ID])
  3280  			for i := range b.Preds {
  3281  				phiPrefs[i].reset()
  3282  			}
  3283  			var headerLoop *loop // loop whose header is b, if any
  3284  			if l := s.loopnest.b2l[b.ID]; l != nil && l.header == b {
  3285  				headerLoop = l
  3286  			}
  3287  			// Process non-phis, then phis.
  3288  			i := len(b.Values) - 1
  3289  			for ; i >= 0; i-- {
  3290  				v := b.Values[i]
  3291  				if v.Op == OpPhi {
  3292  					break
  3293  				}
  3294  				prefs := desired.remove(v.ID)
  3295  				regspec := s.regspec(v)
  3296  				// Cancel desired registers if they get clobbered.
  3297  				desired.clobber(regspec.clobbers)
  3298  				// Update desired registers if there are any fixed register inputs.
  3299  				for _, j := range regspec.inputs {
  3300  					if countRegs(j.regs) != 1 {
  3301  						continue
  3302  					}
  3303  					desired.clobber(j.regs)
  3304  					desired.add(v.Args[j.idx].ID, s.pickReg(j.regs))
  3305  				}
  3306  				// Set desired register of input 0 if this is a 2-operand instruction.
  3307  				if opcodeTable[v.Op].resultInArg0 || v.Op == OpAMD64ADDQconst || v.Op == OpAMD64ADDLconst || v.Op == OpSelect0 {
  3308  					// ADDQconst is added here because we want to treat it as resultInArg0 for
  3309  					// the purposes of desired registers, even though it is not an absolute requirement.
  3310  					// This is because we'd rather implement it as ADDQ instead of LEAQ.
  3311  					// Same for ADDLconst
  3312  					// Select0 is added here to propagate the desired register to the tuple-generating instruction.
  3313  					if opcodeTable[v.Op].commutative {
  3314  						desired.addList(v.Args[1].ID, prefs)
  3315  					}
  3316  					desired.addList(v.Args[0].ID, prefs)
  3317  				}
  3318  			}
  3319  			for ; i >= 0; i-- {
  3320  				v := b.Values[i]
  3321  				prefs := desired.remove(v.ID)
  3322  				if prefs[0] == noRegister {
  3323  					continue
  3324  				}
  3325  				// Phi desires go to phiPrefs (per-pred), so drop them from desired.avoid.
  3326  				// The merge below re-adds any bits other entries still need.
  3327  				for _, r := range prefs {
  3328  					if r != noRegister {
  3329  						desired.avoid = desired.avoid.minus(regMaskAt(r))
  3330  					}
  3331  				}
  3332  				// Propagate v's desired registers back to its args.
  3333  				for pidx, a := range v.Args {
  3334  					if headerLoop != nil && s.loopnest.b2l[b.Preds[pidx].b.ID] == headerLoop {
  3335  						// Skip direct back-edges to avoid pessimizing the loop body to skip a single reg-reg move.
  3336  						// We check only the immediate loop; it is simple and empirically sufficient.
  3337  						continue
  3338  					}
  3339  					phiPrefs[pidx].addList(a.ID, prefs)
  3340  				}
  3341  			}
  3342  			for pidx, e := range b.Preds {
  3343  				p := e.b
  3344  				changed = s.desired[p.ID].merge(&desired) || changed
  3345  				changed = s.desired[p.ID].merge(&phiPrefs[pidx]) || changed
  3346  			}
  3347  		}
  3348  		if !changed || (!s.loopnest.hasIrreducible && len(s.loopnest.loops) == 0) {
  3349  			break
  3350  		}
  3351  	}
  3352  }
  3353  
  3354  // updateLive updates a given liveInfo slice with the contents of t
  3355  func updateLive(t *sparseMapPos, live []liveInfo) []liveInfo {
  3356  	live = live[:0]
  3357  	if cap(live) < t.size() {
  3358  		live = make([]liveInfo, 0, t.size())
  3359  	}
  3360  	for _, e := range t.contents() {
  3361  		live = append(live, liveInfo{e.key, e.val, e.pos})
  3362  	}
  3363  	return live
  3364  }
  3365  
  3366  // branchDistance calculates the distance between a block and a
  3367  // successor in pseudo-instructions. This is used to indicate
  3368  // likeliness
  3369  func branchDistance(b *Block, s *Block) int32 {
  3370  	if len(b.Succs) == 2 {
  3371  		if b.Succs[0].b == s && b.Likely == BranchLikely ||
  3372  			b.Succs[1].b == s && b.Likely == BranchUnlikely {
  3373  			return likelyDistance
  3374  		}
  3375  		if b.Succs[0].b == s && b.Likely == BranchUnlikely ||
  3376  			b.Succs[1].b == s && b.Likely == BranchLikely {
  3377  			return unlikelyDistance
  3378  		}
  3379  	}
  3380  	// Note: the branch distance must be at least 1 to distinguish the control
  3381  	// value use from the first user in a successor block.
  3382  	return normalDistance
  3383  }
  3384  
  3385  func (s *regAllocState) debugPrintLive(stage string, f *Func, live [][]liveInfo, desired []desiredState) {
  3386  	fmt.Printf("%s: live values at end of each block: %s\n", stage, f.Name)
  3387  	for _, b := range f.Blocks {
  3388  		s.debugPrintLiveBlock(b, live[b.ID], &desired[b.ID])
  3389  	}
  3390  }
  3391  
  3392  func (s *regAllocState) debugPrintLiveBlock(b *Block, live []liveInfo, desired *desiredState) {
  3393  	fmt.Printf("  %s:", b)
  3394  	slices.SortFunc(live, func(a, b liveInfo) int {
  3395  		return cmp.Compare(a.ID, b.ID)
  3396  	})
  3397  	for _, x := range live {
  3398  		fmt.Printf(" v%d(%d)", x.ID, x.dist)
  3399  		for _, e := range desired.entries {
  3400  			if e.ID != x.ID {
  3401  				continue
  3402  			}
  3403  			fmt.Printf("[")
  3404  			first := true
  3405  			for _, r := range e.regs {
  3406  				if r == noRegister {
  3407  					continue
  3408  				}
  3409  				if !first {
  3410  					fmt.Printf(",")
  3411  				}
  3412  				fmt.Print(&s.registers[r])
  3413  				first = false
  3414  			}
  3415  			fmt.Printf("]")
  3416  		}
  3417  	}
  3418  	if avoid := desired.avoid; !avoid.empty() {
  3419  		fmt.Printf(" avoid=%v", s.RegMaskString(avoid))
  3420  	}
  3421  	fmt.Println()
  3422  }
  3423  
  3424  // A desiredState represents desired register assignments.
  3425  type desiredState struct {
  3426  	// Desired assignments will be small, so we just use a list
  3427  	// of valueID+registers entries.
  3428  	entries []desiredStateEntry
  3429  	// Registers that other values want to be in.  This value will
  3430  	// contain at least the union of the regs fields of entries, but
  3431  	// may contain additional entries for values that were once in
  3432  	// this data structure but are no longer.
  3433  	avoid regMask
  3434  }
  3435  type desiredStateEntry struct {
  3436  	// (pre-regalloc) value
  3437  	ID ID
  3438  	// Registers it would like to be in, in priority order.
  3439  	// Unused slots are filled with noRegister.
  3440  	// For opcodes that return tuples, we track desired registers only
  3441  	// for the first element of the tuple (see desiredSecondReg for
  3442  	// tracking the desired register for second part of a tuple).
  3443  	regs [4]register
  3444  }
  3445  
  3446  // get returns a list of desired registers for value vid.
  3447  func (d *desiredState) get(vid ID) [4]register {
  3448  	for _, e := range d.entries {
  3449  		if e.ID == vid {
  3450  			return e.regs
  3451  		}
  3452  	}
  3453  	return [4]register{noRegister, noRegister, noRegister, noRegister}
  3454  }
  3455  
  3456  // add records that we'd like value vid to be in register r.
  3457  func (d *desiredState) add(vid ID, r register) {
  3458  	d.avoid = d.avoid.addReg(r)
  3459  	for i := range d.entries {
  3460  		e := &d.entries[i]
  3461  		if e.ID != vid {
  3462  			continue
  3463  		}
  3464  		if e.regs[0] == r {
  3465  			// Already known and highest priority
  3466  			return
  3467  		}
  3468  		for j := 1; j < len(e.regs); j++ {
  3469  			if e.regs[j] == r {
  3470  				// Move from lower priority to top priority
  3471  				copy(e.regs[1:], e.regs[:j])
  3472  				e.regs[0] = r
  3473  				return
  3474  			}
  3475  		}
  3476  		copy(e.regs[1:], e.regs[:])
  3477  		e.regs[0] = r
  3478  		return
  3479  	}
  3480  	d.entries = append(d.entries, desiredStateEntry{vid, [4]register{r, noRegister, noRegister, noRegister}})
  3481  }
  3482  
  3483  func (d *desiredState) addList(vid ID, regs [4]register) {
  3484  	// regs is in priority order, so iterate in reverse order.
  3485  	for i := len(regs) - 1; i >= 0; i-- {
  3486  		r := regs[i]
  3487  		if r != noRegister {
  3488  			d.add(vid, r)
  3489  		}
  3490  	}
  3491  }
  3492  
  3493  // clobber erases any desired registers in the set m.
  3494  func (d *desiredState) clobber(m regMask) {
  3495  	for i := 0; i < len(d.entries); {
  3496  		e := &d.entries[i]
  3497  		j := 0
  3498  		for _, r := range e.regs {
  3499  			if r != noRegister && !m.hasReg(r) {
  3500  				e.regs[j] = r
  3501  				j++
  3502  			}
  3503  		}
  3504  		if j == 0 {
  3505  			// No more desired registers for this value.
  3506  			d.entries[i] = d.entries[len(d.entries)-1]
  3507  			d.entries = d.entries[:len(d.entries)-1]
  3508  			continue
  3509  		}
  3510  		for ; j < len(e.regs); j++ {
  3511  			e.regs[j] = noRegister
  3512  		}
  3513  		i++
  3514  	}
  3515  	d.avoid = d.avoid.minus(m)
  3516  }
  3517  
  3518  // reset prepares d for re-use.
  3519  func (d *desiredState) reset() {
  3520  	d.entries = d.entries[:0]
  3521  	d.avoid = regMask{}
  3522  }
  3523  
  3524  // copy copies a desired state from another desiredState x.
  3525  func (d *desiredState) copy(x *desiredState) {
  3526  	d.entries = append(d.entries[:0], x.entries...)
  3527  	d.avoid = x.avoid
  3528  }
  3529  
  3530  // remove removes the desired registers for vid and returns them.
  3531  func (d *desiredState) remove(vid ID) [4]register {
  3532  	for i := range d.entries {
  3533  		if d.entries[i].ID == vid {
  3534  			regs := d.entries[i].regs
  3535  			d.entries[i] = d.entries[len(d.entries)-1]
  3536  			d.entries = d.entries[:len(d.entries)-1]
  3537  			return regs
  3538  		}
  3539  	}
  3540  	return [4]register{noRegister, noRegister, noRegister, noRegister}
  3541  }
  3542  
  3543  // merge merges another desired state x into d. Returns whether the set has
  3544  // changed
  3545  func (d *desiredState) merge(x *desiredState) bool {
  3546  	oldAvoid := d.avoid
  3547  	d.avoid = d.avoid.union(x.avoid)
  3548  	// There should only be a few desired registers, so
  3549  	// linear insert is ok.
  3550  	for _, e := range x.entries {
  3551  		d.addList(e.ID, e.regs)
  3552  	}
  3553  	return oldAvoid != d.avoid
  3554  }
  3555  
  3556  // computeUnavoidableCalls computes the containsUnavoidableCall fields in the loop nest.
  3557  func (loopnest *loopnest) computeUnavoidableCalls() {
  3558  	f := loopnest.f
  3559  
  3560  	hasCall := f.Cache.allocBoolSlice(f.NumBlocks())
  3561  	defer f.Cache.freeBoolSlice(hasCall)
  3562  	for _, b := range f.Blocks {
  3563  		if b.containsCall() {
  3564  			hasCall[b.ID] = true
  3565  		}
  3566  	}
  3567  	found := f.Cache.allocSparseSet(f.NumBlocks())
  3568  	defer f.Cache.freeSparseSet(found)
  3569  	// Run dfs to find path through the loop that avoids all calls.
  3570  	// Such path either escapes the loop or returns back to the header.
  3571  	// It isn't enough to have exit not dominated by any call, for example:
  3572  	// ... some loop
  3573  	// call1    call2
  3574  	//   \       /
  3575  	//     block
  3576  	// ...
  3577  	// block is not dominated by any single call, but we don't have call-free path to it.
  3578  loopLoop:
  3579  	for _, l := range loopnest.loops {
  3580  		found.clear()
  3581  		tovisit := make([]*Block, 0, 8)
  3582  		tovisit = append(tovisit, l.header)
  3583  		for len(tovisit) > 0 {
  3584  			cur := tovisit[len(tovisit)-1]
  3585  			tovisit = tovisit[:len(tovisit)-1]
  3586  			if hasCall[cur.ID] {
  3587  				continue
  3588  			}
  3589  			for _, s := range cur.Succs {
  3590  				nb := s.Block()
  3591  				if nb == l.header {
  3592  					// Found a call-free path around the loop.
  3593  					continue loopLoop
  3594  				}
  3595  				if found.contains(nb.ID) {
  3596  					// Already found via another path.
  3597  					continue
  3598  				}
  3599  				nl := loopnest.b2l[nb.ID]
  3600  				if nl == nil || (nl.depth <= l.depth && nl != l) {
  3601  					// Left the loop.
  3602  					continue
  3603  				}
  3604  				tovisit = append(tovisit, nb)
  3605  				found.add(nb.ID)
  3606  			}
  3607  		}
  3608  		// No call-free path was found.
  3609  		l.containsUnavoidableCall = true
  3610  	}
  3611  }
  3612  
  3613  func (b *Block) containsCall() bool {
  3614  	if b.Kind == BlockDefer {
  3615  		return true
  3616  	}
  3617  	for _, v := range b.Values {
  3618  		if opcodeTable[v.Op].call {
  3619  			return true
  3620  		}
  3621  	}
  3622  	return false
  3623  }
  3624  

View as plain text