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

View as plain text