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

View as plain text