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