schedule.go

     1  // Copyright 2015 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package ssacompile
     6  
     7  import (
     8  	"cmp"
     9  	"container/heap"
    10  	"slices"
    11  	"sort"
    12  
    13  	"cmd/compile/internal/base"
    14  	"cmd/compile/internal/ssa"
    15  	"cmd/compile/internal/ssa/ssaop"
    16  	"cmd/compile/internal/types"
    17  )
    18  
    19  const (
    20  	ScorePhi       = iota // towards top of block
    21  	ScoreArg              // must occur at the top of the entry block
    22  	ScoreInitMem          // after the args - used as mark by debug info generation
    23  	ScoreReadTuple        // must occur immediately after tuple-generating insn (or call)
    24  	ScoreNilCheck
    25  	ScoreMemory
    26  	ScoreReadFlags
    27  	ScoreDefault
    28  	ScoreFlags
    29  	ScoreInductionInc // an increment of an induction variable
    30  	ScoreControl      // towards bottom of block
    31  )
    32  
    33  type ValHeap struct {
    34  	a           []*ssa.Value
    35  	score       []int8
    36  	inBlockUses []bool
    37  }
    38  
    39  func (h ValHeap) Len() int      { return len(h.a) }
    40  func (h ValHeap) Swap(i, j int) { a := h.a; a[i], a[j] = a[j], a[i] }
    41  
    42  func (h *ValHeap) Push(x any) {
    43  	// Push and Pop use pointer receivers because they modify the slice's length,
    44  	// not just its contents.
    45  	v := x.(*ssa.Value)
    46  	h.a = append(h.a, v)
    47  }
    48  func (h *ValHeap) Pop() any {
    49  	old := h.a
    50  	n := len(old)
    51  	x := old[n-1]
    52  	h.a = old[0 : n-1]
    53  	return x
    54  }
    55  func (h ValHeap) Less(i, j int) bool {
    56  	x := h.a[i]
    57  	y := h.a[j]
    58  	sx := h.score[x.ID]
    59  	sy := h.score[y.ID]
    60  	if c := sx - sy; c != 0 {
    61  		return c < 0 // lower scores come earlier.
    62  	}
    63  	// Note: only scores are required for correct scheduling.
    64  	// Everything else is just heuristics.
    65  
    66  	ix := h.inBlockUses[x.ID]
    67  	iy := h.inBlockUses[y.ID]
    68  	if ix != iy {
    69  		return ix // values with in-block uses come earlier
    70  	}
    71  
    72  	if x.Pos != y.Pos { // Favor in-order line stepping
    73  		return x.Pos.Before(y.Pos)
    74  	}
    75  	if x.Op != ssaop.OpPhi {
    76  		if c := len(x.Args) - len(y.Args); c != 0 {
    77  			return c > 0 // smaller args come later
    78  		}
    79  	}
    80  	if c := x.Uses - y.Uses; c != 0 {
    81  		return c > 0 // smaller uses come later
    82  	}
    83  	// These comparisons are fairly arbitrary.
    84  	// The goal here is stability in the face
    85  	// of unrelated changes elsewhere in the compiler.
    86  	if c := x.AuxInt - y.AuxInt; c != 0 {
    87  		return c < 0
    88  	}
    89  	if cmp := x.Type.Compare(y.Type); cmp != types.CMPeq {
    90  		return cmp == types.CMPlt
    91  	}
    92  	return x.ID < y.ID
    93  }
    94  
    95  // Schedule the Values in each Block. After this phase returns, the
    96  // order of b.Values matters and is the order in which those values
    97  // will appear in the assembly output. For now it generates a
    98  // reasonable valid schedule using a priority queue. TODO(khr):
    99  // schedule smarter.
   100  func schedule(f *ssa.Func) {
   101  	// reusable priority queue
   102  	priq := new(ValHeap)
   103  
   104  	// "priority" for a value
   105  	score := f.Cache.AllocInt8Slice(f.NumValues())
   106  	defer f.Cache.FreeInt8Slice(score)
   107  
   108  	// maps mem values to the next live memory value
   109  	nextMem := f.Cache.AllocValueSlice(f.NumValues())
   110  	defer f.Cache.FreeValueSlice(nextMem)
   111  
   112  	// inBlockUses records whether a value is used in the block
   113  	// in which it lives. (block control values don't count as uses.)
   114  	inBlockUses := f.Cache.AllocBoolSlice(f.NumValues())
   115  	defer f.Cache.FreeBoolSlice(inBlockUses)
   116  	if f.Config.Optimize {
   117  		for _, b := range f.Blocks {
   118  			for _, v := range b.Values {
   119  				for _, a := range v.Args {
   120  					if a.Block == b {
   121  						inBlockUses[a.ID] = true
   122  					}
   123  				}
   124  			}
   125  		}
   126  	}
   127  	priq.inBlockUses = inBlockUses
   128  
   129  	for _, b := range f.Blocks {
   130  		// Compute score. Larger numbers are scheduled closer to the end of the block.
   131  		for _, v := range b.Values {
   132  			switch {
   133  			case v.Op.IsLoweredGetClosurePtr():
   134  				// We also score GetLoweredClosurePtr as early as possible to ensure that the
   135  				// context register is not stomped. GetLoweredClosurePtr should only appear
   136  				// in the entry block where there are no phi functions, so there is no
   137  				// conflict or ambiguity here.
   138  				if b != f.Entry {
   139  					f.Fatalf("LoweredGetClosurePtr appeared outside of entry block, b=%s", b.String())
   140  				}
   141  				score[v.ID] = ScorePhi
   142  			case ssaop.OpcodeTable[v.Op].NilCheck:
   143  				// Nil checks must come before loads from the same address.
   144  				score[v.ID] = ScoreNilCheck
   145  			case v.Op == ssaop.OpPhi:
   146  				// We want all the phis first.
   147  				score[v.ID] = ScorePhi
   148  			case v.Op == ssaop.OpArgIntReg || v.Op == ssaop.OpArgFloatReg:
   149  				// In-register args must be scheduled as early as possible to ensure that they
   150  				// are not stomped (similar to the closure pointer above).
   151  				// In particular, they need to come before regular OpArg operations because
   152  				// of how regalloc places spill code (see regalloc.go:placeSpills:mustBeFirst).
   153  				if b != f.Entry {
   154  					f.Fatalf("%s appeared outside of entry block, b=%s", v.Op, b.String())
   155  				}
   156  				score[v.ID] = ScorePhi
   157  			case v.Op == ssaop.OpArg || v.Op == ssaop.OpSP || v.Op == ssaop.OpSB:
   158  				// We want all the args as early as possible, for better debugging.
   159  				score[v.ID] = ScoreArg
   160  			case v.Op == ssaop.OpInitMem:
   161  				// Early, but after args. See debug.go:buildLocationLists
   162  				score[v.ID] = ScoreInitMem
   163  			case v.Type.IsMemory():
   164  				// Schedule stores as early as possible. This tends to
   165  				// reduce register pressure.
   166  				score[v.ID] = ScoreMemory
   167  			case v.Op == ssaop.OpSelect0 || v.Op == ssaop.OpSelect1 || v.Op == ssaop.OpSelectN:
   168  				// Tuple selectors need to appear immediately after the instruction
   169  				// that generates the tuple.
   170  				score[v.ID] = ScoreReadTuple
   171  			case v.HasFlagInput():
   172  				// Schedule flag-reading ops earlier, to minimize the lifetime
   173  				// of flag values.
   174  				score[v.ID] = ScoreReadFlags
   175  			case v.IsFlagOp():
   176  				// Schedule flag register generation as late as possible.
   177  				// This makes sure that we only have one live flags
   178  				// value at a time.
   179  				// Note that this case is after the case above, so values
   180  				// which both read and generate flags are given ScoreReadFlags.
   181  				score[v.ID] = ScoreFlags
   182  			case (len(v.Args) == 1 &&
   183  				v.Args[0].Op == ssaop.OpPhi &&
   184  				v.Args[0].Uses > 1 &&
   185  				len(b.Succs) == 1 &&
   186  				b.Succs[0].B == v.Args[0].Block &&
   187  				v.Args[0].Args[b.Succs[0].I] == v):
   188  				// This is a value computing v++ (or similar) in a loop.
   189  				// Try to schedule it later, so we issue all uses of v before the v++.
   190  				// If we don't, then we need an additional move.
   191  				// loop:
   192  				//     p = (PHI v ...)
   193  				//     ... ok other uses of p ...
   194  				//     v = (ADDQconst [1] p)
   195  				//     ... troublesome other uses of p ...
   196  				//     goto loop
   197  				// We want to allocate p and v to the same register so when we get to
   198  				// the end of the block we don't have to move v back to p's register.
   199  				// But we can only do that if v comes after all the other uses of p.
   200  				// Any "troublesome" use means we have to reg-reg move either p or v
   201  				// somewhere in the loop.
   202  				score[v.ID] = ScoreInductionInc
   203  			default:
   204  				score[v.ID] = ScoreDefault
   205  			}
   206  		}
   207  		for _, c := range b.ControlValues() {
   208  			// Force the control values to be scheduled at the end,
   209  			// unless they have other special priority.
   210  			if c.Block != b || score[c.ID] < ScoreReadTuple {
   211  				continue
   212  			}
   213  			if score[c.ID] == ScoreReadTuple {
   214  				score[c.Args[0].ID] = ScoreControl
   215  				continue
   216  			}
   217  			score[c.ID] = ScoreControl
   218  		}
   219  	}
   220  	priq.score = score
   221  
   222  	// An edge represents a scheduling constraint that x must appear before y in the schedule.
   223  	type edge struct {
   224  		x, y *ssa.Value
   225  	}
   226  	edges := make([]edge, 0, 64)
   227  
   228  	// inEdges is the number of scheduling edges incoming from values that haven't been scheduled yet.
   229  	// i.e. inEdges[y.ID] = |e in edges where e.y == y and e.x is not in the schedule yet|.
   230  	inEdges := f.Cache.AllocInt32Slice(f.NumValues())
   231  	defer f.Cache.FreeInt32Slice(inEdges)
   232  
   233  	for _, b := range f.Blocks {
   234  		edges = edges[:0]
   235  		// Standard edges: from the argument of a value to that value.
   236  		for _, v := range b.Values {
   237  			if v.Op == ssaop.OpPhi {
   238  				// If a value is used by a phi, it does not induce
   239  				// a scheduling edge because that use is from the
   240  				// previous iteration.
   241  				continue
   242  			}
   243  			for _, a := range v.Args {
   244  				if a.Block == b {
   245  					edges = append(edges, edge{a, v})
   246  				}
   247  			}
   248  		}
   249  
   250  		// Find store chain for block.
   251  		// Store chains for different blocks overwrite each other, so
   252  		// the calculated store chain is good only for this block.
   253  		for _, v := range b.Values {
   254  			if v.Op != ssaop.OpPhi && v.Op != ssaop.OpInitMem && v.Type.IsMemory() {
   255  				nextMem[v.MemoryArg().ID] = v
   256  			}
   257  		}
   258  
   259  		// Add edges to enforce that any load must come before the following store.
   260  		for _, v := range b.Values {
   261  			if v.Op == ssaop.OpPhi || v.Type.IsMemory() {
   262  				continue
   263  			}
   264  			w := v.MemoryArg()
   265  			if w == nil {
   266  				continue
   267  			}
   268  			if s := nextMem[w.ID]; s != nil && s.Block == b {
   269  				edges = append(edges, edge{v, s})
   270  			}
   271  		}
   272  
   273  		// Sort all the edges by source Value ID.
   274  		slices.SortFunc(edges, func(a, b edge) int {
   275  			return cmp.Compare(a.x.ID, b.x.ID)
   276  		})
   277  		// Compute inEdges for values in this block.
   278  		for _, e := range edges {
   279  			inEdges[e.y.ID]++
   280  		}
   281  
   282  		// Initialize priority queue with schedulable values.
   283  		priq.a = priq.a[:0]
   284  		for _, v := range b.Values {
   285  			if inEdges[v.ID] == 0 {
   286  				heap.Push(priq, v)
   287  			}
   288  		}
   289  
   290  		// Produce the schedule. Pick the highest priority scheduleable value,
   291  		// add it to the schedule, add any of its uses that are now scheduleable
   292  		// to the queue, and repeat.
   293  		nv := len(b.Values)
   294  		b.Values = b.Values[:0]
   295  		for priq.Len() > 0 {
   296  			// Schedule the next schedulable value in priority order.
   297  			v := heap.Pop(priq).(*ssa.Value)
   298  			b.Values = append(b.Values, v)
   299  
   300  			// Find all the scheduling edges out from this value.
   301  			i := sort.Search(len(edges), func(i int) bool {
   302  				return edges[i].x.ID >= v.ID
   303  			})
   304  			j := sort.Search(len(edges), func(i int) bool {
   305  				return edges[i].x.ID > v.ID
   306  			})
   307  			// Decrement inEdges for each target of edges from v.
   308  			for _, e := range edges[i:j] {
   309  				inEdges[e.y.ID]--
   310  				if inEdges[e.y.ID] == 0 {
   311  					heap.Push(priq, e.y)
   312  				}
   313  			}
   314  		}
   315  		if len(b.Values) != nv {
   316  			f.Fatalf("schedule does not include all values in block %s", b)
   317  		}
   318  	}
   319  
   320  	// Remove SPanchored now that we've scheduled.
   321  	// Also unlink nil checks now that ordering is assured
   322  	// between the nil check and the uses of the nil-checked pointer.
   323  	for _, b := range f.Blocks {
   324  		for _, v := range b.Values {
   325  			for i, a := range v.Args {
   326  				for a.Op == ssaop.OpSPanchored || ssaop.OpcodeTable[a.Op].NilCheck {
   327  					a = a.Args[0]
   328  					v.SetArg(i, a)
   329  				}
   330  			}
   331  		}
   332  		for i, c := range b.ControlValues() {
   333  			for c.Op == ssaop.OpSPanchored || ssaop.OpcodeTable[c.Op].NilCheck {
   334  				c = c.Args[0]
   335  				b.ReplaceControl(i, c)
   336  			}
   337  		}
   338  	}
   339  	for _, b := range f.Blocks {
   340  		i := 0
   341  		for _, v := range b.Values {
   342  			if v.Op == ssaop.OpSPanchored {
   343  				// Free this value
   344  				if v.Uses != 0 {
   345  					base.Fatalf("SPAnchored still has %d uses", v.Uses)
   346  				}
   347  				v.ResetArgs()
   348  				f.FreeValue(v)
   349  			} else {
   350  				if ssaop.OpcodeTable[v.Op].NilCheck {
   351  					if v.Uses != 0 {
   352  						base.Fatalf("nilcheck still has %d uses", v.Uses)
   353  					}
   354  					// We can't delete the nil check, but we mark
   355  					// it as having void type so regalloc won't
   356  					// try to allocate a register for it.
   357  					v.Type = types.TypeVoid
   358  				}
   359  				b.Values[i] = v
   360  				i++
   361  			}
   362  		}
   363  		b.TruncateValues(i)
   364  	}
   365  
   366  	f.Scheduled = true
   367  }
   368  
   369  // storeOrder orders values with respect to stores. That is,
   370  // if v transitively depends on store s, v is ordered after s,
   371  // otherwise v is ordered before s.
   372  // Specifically, values are ordered like
   373  //
   374  //	store1
   375  //	NilCheck that depends on store1
   376  //	other values that depends on store1
   377  //	store2
   378  //	NilCheck that depends on store2
   379  //	other values that depends on store2
   380  //	...
   381  //
   382  // The order of non-store and non-NilCheck values are undefined
   383  // (not necessarily dependency order). This should be cheaper
   384  // than a full scheduling as done above.
   385  // Note that simple dependency order won't work: there is no
   386  // dependency between NilChecks and values like IsNonNil.
   387  // Auxiliary data structures are passed in as arguments, so
   388  // that they can be allocated in the caller and be reused.
   389  // This function takes care of reset them.
   390  func storeOrder(values []*ssa.Value, sset *ssa.SparseSet, storeNumber []int32) []*ssa.Value {
   391  	if len(values) == 0 {
   392  		return values
   393  	}
   394  
   395  	f := values[0].Block.Func
   396  
   397  	// find all stores
   398  
   399  	// Members of values that are store values.
   400  	// A constant bound allows this to be stack-allocated. 64 is
   401  	// enough to cover almost every storeOrder call.
   402  	stores := make([]*ssa.Value, 0, 64)
   403  	hasNilCheck := false
   404  	sset.Clear() // sset is the set of stores that are used in other values
   405  	for _, v := range values {
   406  		if v.Type.IsMemory() {
   407  			stores = append(stores, v)
   408  			if v.Op == ssaop.OpInitMem || v.Op == ssaop.OpPhi {
   409  				continue
   410  			}
   411  			sset.Add(v.MemoryArg().ID) // record that v's memory arg is used
   412  		}
   413  		if v.Op == ssaop.OpNilCheck {
   414  			hasNilCheck = true
   415  		}
   416  	}
   417  	if len(stores) == 0 || !hasNilCheck && f.Pass.Name == "nilcheckelim" {
   418  		// there is no store, the order does not matter
   419  		return values
   420  	}
   421  
   422  	// find last store, which is the one that is not used by other stores
   423  	var last *ssa.Value
   424  	for _, v := range stores {
   425  		if !sset.Contains(v.ID) {
   426  			if last != nil {
   427  				f.Fatalf("two stores live simultaneously: %v and %v", v, last)
   428  			}
   429  			last = v
   430  		}
   431  	}
   432  
   433  	// We assign a store number to each value. Store number is the
   434  	// index of the latest store that this value transitively depends.
   435  	// The i-th store in the current block gets store number 3*i. A nil
   436  	// check that depends on the i-th store gets store number 3*i+1.
   437  	// Other values that depends on the i-th store gets store number 3*i+2.
   438  	// Special case: 0 -- unassigned, 1 or 2 -- the latest store it depends
   439  	// is in the previous block (or no store at all, e.g. value is Const).
   440  	// First we assign the number to all stores by walking back the store chain,
   441  	// then assign the number to other values in DFS order.
   442  	count := make([]int32, 3*(len(stores)+1))
   443  	sset.Clear() // reuse sparse set to ensure that a value is pushed to stack only once
   444  	for n, w := len(stores), last; n > 0; n-- {
   445  		storeNumber[w.ID] = int32(3 * n)
   446  		count[3*n]++
   447  		sset.Add(w.ID)
   448  		if w.Op == ssaop.OpInitMem || w.Op == ssaop.OpPhi {
   449  			if n != 1 {
   450  				f.Fatalf("store order is wrong: there are stores before %v", w)
   451  			}
   452  			break
   453  		}
   454  		w = w.MemoryArg()
   455  	}
   456  	var stack []*ssa.Value
   457  	for _, v := range values {
   458  		if sset.Contains(v.ID) {
   459  			// in sset means v is a store, or already pushed to stack, or already assigned a store number
   460  			continue
   461  		}
   462  		stack = append(stack, v)
   463  		sset.Add(v.ID)
   464  
   465  		for len(stack) > 0 {
   466  			w := stack[len(stack)-1]
   467  			if storeNumber[w.ID] != 0 {
   468  				stack = stack[:len(stack)-1]
   469  				continue
   470  			}
   471  			if w.Op == ssaop.OpPhi {
   472  				// Phi value doesn't depend on store in the current block.
   473  				// Do this early to avoid dependency cycle.
   474  				storeNumber[w.ID] = 2
   475  				count[2]++
   476  				stack = stack[:len(stack)-1]
   477  				continue
   478  			}
   479  
   480  			max := int32(0) // latest store dependency
   481  			argsdone := true
   482  			for _, a := range w.Args {
   483  				if a.Block != w.Block {
   484  					continue
   485  				}
   486  				if !sset.Contains(a.ID) {
   487  					stack = append(stack, a)
   488  					sset.Add(a.ID)
   489  					argsdone = false
   490  					break
   491  				}
   492  				if storeNumber[a.ID]/3 > max {
   493  					max = storeNumber[a.ID] / 3
   494  				}
   495  			}
   496  			if !argsdone {
   497  				continue
   498  			}
   499  
   500  			n := 3*max + 2
   501  			if w.Op == ssaop.OpNilCheck {
   502  				n = 3*max + 1
   503  			}
   504  			storeNumber[w.ID] = n
   505  			count[n]++
   506  			stack = stack[:len(stack)-1]
   507  		}
   508  	}
   509  
   510  	// convert count to prefix sum of counts: count'[i] = sum_{j<=i} count[i]
   511  	for i := range count {
   512  		if i == 0 {
   513  			continue
   514  		}
   515  		count[i] += count[i-1]
   516  	}
   517  	if count[len(count)-1] != int32(len(values)) {
   518  		f.Fatalf("storeOrder: value is missing, total count = %d, values = %v", count[len(count)-1], values)
   519  	}
   520  
   521  	// place values in count-indexed bins, which are in the desired store order
   522  	order := make([]*ssa.Value, len(values))
   523  	for _, v := range values {
   524  		s := storeNumber[v.ID]
   525  		order[count[s-1]] = v
   526  		count[s-1]++
   527  	}
   528  
   529  	// Order nil checks in source order. We want the first in source order to trigger.
   530  	// If two are on the same line, we don't really care which happens first.
   531  	// See issue 18169.
   532  	if hasNilCheck {
   533  		start := -1
   534  		for i, v := range order {
   535  			if v.Op == ssaop.OpNilCheck {
   536  				if start == -1 {
   537  					start = i
   538  				}
   539  			} else {
   540  				if start != -1 {
   541  					slices.SortFunc(order[start:i], valuePosCmp)
   542  					start = -1
   543  				}
   544  			}
   545  		}
   546  		if start != -1 {
   547  			slices.SortFunc(order[start:], valuePosCmp)
   548  		}
   549  	}
   550  
   551  	return order
   552  }
   553  
   554  func valuePosCmp(a, b *ssa.Value) int {
   555  	if a.Pos.Before(b.Pos) {
   556  		return -1
   557  	}
   558  	if a.Pos.After(b.Pos) {
   559  		return +1
   560  	}
   561  	return 0
   562  }
   563
View as plain text