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

View as plain text