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

Documentation: cmd/compile/internal/ssa

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

View as plain text