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/types"
     9  	"container/heap"
    10  	"sort"
    11  )
    12  
    13  const (
    14  	ScorePhi = iota // towards top of block
    15  	ScoreArg
    16  	ScoreNilCheck
    17  	ScoreReadTuple
    18  	ScoreVarDef
    19  	ScoreMemory
    20  	ScoreReadFlags
    21  	ScoreDefault
    22  	ScoreFlags
    23  	ScoreControl // towards bottom of block
    24  )
    25  
    26  type ValHeap struct {
    27  	a     []*Value
    28  	score []int8
    29  }
    30  
    31  func (h ValHeap) Len() int      { return len(h.a) }
    32  func (h ValHeap) Swap(i, j int) { a := h.a; a[i], a[j] = a[j], a[i] }
    33  
    34  func (h *ValHeap) Push(x interface{}) {
    35  	// Push and Pop use pointer receivers because they modify the slice's length,
    36  	// not just its contents.
    37  	v := x.(*Value)
    38  	h.a = append(h.a, v)
    39  }
    40  func (h *ValHeap) Pop() interface{} {
    41  	old := h.a
    42  	n := len(old)
    43  	x := old[n-1]
    44  	h.a = old[0 : n-1]
    45  	return x
    46  }
    47  func (h ValHeap) Less(i, j int) bool {
    48  	x := h.a[i]
    49  	y := h.a[j]
    50  	sx := h.score[x.ID]
    51  	sy := h.score[y.ID]
    52  	if c := sx - sy; c != 0 {
    53  		return c > 0 // higher score comes later.
    54  	}
    55  	if x.Pos != y.Pos { // Favor in-order line stepping
    56  		return x.Pos.After(y.Pos)
    57  	}
    58  	if x.Op != OpPhi {
    59  		if c := len(x.Args) - len(y.Args); c != 0 {
    60  			return c < 0 // smaller args comes later
    61  		}
    62  	}
    63  	if c := x.Uses - y.Uses; c != 0 {
    64  		return c < 0 // smaller uses come later
    65  	}
    66  	// These comparisons are fairly arbitrary.
    67  	// The goal here is stability in the face
    68  	// of unrelated changes elsewhere in the compiler.
    69  	if c := x.AuxInt - y.AuxInt; c != 0 {
    70  		return c > 0
    71  	}
    72  	if cmp := x.Type.Compare(y.Type); cmp != types.CMPeq {
    73  		return cmp == types.CMPgt
    74  	}
    75  	return x.ID > y.ID
    76  }
    77  
    78  func (op Op) isLoweredGetClosurePtr() bool {
    79  	switch op {
    80  	case OpAMD64LoweredGetClosurePtr, OpPPC64LoweredGetClosurePtr, OpARMLoweredGetClosurePtr, OpARM64LoweredGetClosurePtr,
    81  		Op386LoweredGetClosurePtr, OpMIPS64LoweredGetClosurePtr, OpS390XLoweredGetClosurePtr, OpMIPSLoweredGetClosurePtr,
    82  		OpRISCV64LoweredGetClosurePtr, OpWasmLoweredGetClosurePtr:
    83  		return true
    84  	}
    85  	return false
    86  }
    87  
    88  // Schedule the Values in each Block. After this phase returns, the
    89  // order of b.Values matters and is the order in which those values
    90  // will appear in the assembly output. For now it generates a
    91  // reasonable valid schedule using a priority queue. TODO(khr):
    92  // schedule smarter.
    93  func schedule(f *Func) {
    94  	// For each value, the number of times it is used in the block
    95  	// by values that have not been scheduled yet.
    96  	uses := make([]int32, f.NumValues())
    97  
    98  	// reusable priority queue
    99  	priq := new(ValHeap)
   100  
   101  	// "priority" for a value
   102  	score := make([]int8, f.NumValues())
   103  
   104  	// scheduling order. We queue values in this list in reverse order.
   105  	// A constant bound allows this to be stack-allocated. 64 is
   106  	// enough to cover almost every schedule call.
   107  	order := make([]*Value, 0, 64)
   108  
   109  	// maps mem values to the next live memory value
   110  	nextMem := make([]*Value, f.NumValues())
   111  	// additional pretend arguments for each Value. Used to enforce load/store ordering.
   112  	additionalArgs := make([][]*Value, f.NumValues())
   113  
   114  	for _, b := range f.Blocks {
   115  		// Compute score. Larger numbers are scheduled closer to the end of the block.
   116  		for _, v := range b.Values {
   117  			switch {
   118  			case v.Op.isLoweredGetClosurePtr():
   119  				// We also score GetLoweredClosurePtr as early as possible to ensure that the
   120  				// context register is not stomped. GetLoweredClosurePtr should only appear
   121  				// in the entry block where there are no phi functions, so there is no
   122  				// conflict or ambiguity here.
   123  				if b != f.Entry {
   124  					f.Fatalf("LoweredGetClosurePtr appeared outside of entry block, b=%s", b.String())
   125  				}
   126  				score[v.ID] = ScorePhi
   127  			case v.Op == OpAMD64LoweredNilCheck || v.Op == OpPPC64LoweredNilCheck ||
   128  				v.Op == OpARMLoweredNilCheck || v.Op == OpARM64LoweredNilCheck ||
   129  				v.Op == Op386LoweredNilCheck || v.Op == OpMIPS64LoweredNilCheck ||
   130  				v.Op == OpS390XLoweredNilCheck || v.Op == OpMIPSLoweredNilCheck ||
   131  				v.Op == OpRISCV64LoweredNilCheck || v.Op == OpWasmLoweredNilCheck:
   132  				// Nil checks must come before loads from the same address.
   133  				score[v.ID] = ScoreNilCheck
   134  			case v.Op == OpPhi:
   135  				// We want all the phis first.
   136  				score[v.ID] = ScorePhi
   137  			case v.Op == OpVarDef:
   138  				// We want all the vardefs next.
   139  				score[v.ID] = ScoreVarDef
   140  			case v.Op == OpArgIntReg || v.Op == OpArgFloatReg:
   141  				// In-register args must be scheduled as early as possible to ensure that the
   142  				// context register is not stomped. They should only appear in the entry block.
   143  				if b != f.Entry {
   144  					f.Fatalf("%s appeared outside of entry block, b=%s", v.Op, b.String())
   145  				}
   146  				score[v.ID] = ScorePhi
   147  			case v.Op == OpArg:
   148  				// We want all the args as early as possible, for better debugging.
   149  				score[v.ID] = ScoreArg
   150  			case v.Type.IsMemory():
   151  				// Schedule stores as early as possible. This tends to
   152  				// reduce register pressure. It also helps make sure
   153  				// VARDEF ops are scheduled before the corresponding LEA.
   154  				score[v.ID] = ScoreMemory
   155  			case v.Op == OpSelect0 || v.Op == OpSelect1 || v.Op == OpSelectN:
   156  				// Schedule the pseudo-op of reading part of a tuple
   157  				// immediately after the tuple-generating op, since
   158  				// this value is already live. This also removes its
   159  				// false dependency on the other part of the tuple.
   160  				// Also ensures tuple is never spilled.
   161  				score[v.ID] = ScoreReadTuple
   162  			case v.Type.IsFlags() || v.Type.IsTuple() && v.Type.FieldType(1).IsFlags():
   163  				// Schedule flag register generation as late as possible.
   164  				// This makes sure that we only have one live flags
   165  				// value at a time.
   166  				score[v.ID] = ScoreFlags
   167  			default:
   168  				score[v.ID] = ScoreDefault
   169  				// If we're reading flags, schedule earlier to keep flag lifetime short.
   170  				for _, a := range v.Args {
   171  					if a.Type.IsFlags() {
   172  						score[v.ID] = ScoreReadFlags
   173  					}
   174  				}
   175  			}
   176  		}
   177  	}
   178  
   179  	for _, b := range f.Blocks {
   180  		// Find store chain for block.
   181  		// Store chains for different blocks overwrite each other, so
   182  		// the calculated store chain is good only for this block.
   183  		for _, v := range b.Values {
   184  			if v.Op != OpPhi && v.Type.IsMemory() {
   185  				for _, w := range v.Args {
   186  					if w.Type.IsMemory() {
   187  						nextMem[w.ID] = v
   188  					}
   189  				}
   190  			}
   191  		}
   192  
   193  		// Compute uses.
   194  		for _, v := range b.Values {
   195  			if v.Op == OpPhi {
   196  				// If a value is used by a phi, it does not induce
   197  				// a scheduling edge because that use is from the
   198  				// previous iteration.
   199  				continue
   200  			}
   201  			for _, w := range v.Args {
   202  				if w.Block == b {
   203  					uses[w.ID]++
   204  				}
   205  				// Any load must come before the following store.
   206  				if !v.Type.IsMemory() && w.Type.IsMemory() {
   207  					// v is a load.
   208  					s := nextMem[w.ID]
   209  					if s == nil || s.Block != b {
   210  						continue
   211  					}
   212  					additionalArgs[s.ID] = append(additionalArgs[s.ID], v)
   213  					uses[v.ID]++
   214  				}
   215  			}
   216  		}
   217  
   218  		for _, c := range b.ControlValues() {
   219  			// Force the control values to be scheduled at the end,
   220  			// unless they are phi values (which must be first).
   221  			// OpArg also goes first -- if it is stack it register allocates
   222  			// to a LoadReg, if it is register it is from the beginning anyway.
   223  			if score[c.ID] == ScorePhi || score[c.ID] == ScoreArg {
   224  				continue
   225  			}
   226  			score[c.ID] = ScoreControl
   227  
   228  			// Schedule values dependent on the control values at the end.
   229  			// This reduces the number of register spills. We don't find
   230  			// all values that depend on the controls, just values with a
   231  			// direct dependency. This is cheaper and in testing there
   232  			// was no difference in the number of spills.
   233  			for _, v := range b.Values {
   234  				if v.Op != OpPhi {
   235  					for _, a := range v.Args {
   236  						if a == c {
   237  							score[v.ID] = ScoreControl
   238  						}
   239  					}
   240  				}
   241  			}
   242  
   243  		}
   244  
   245  		// To put things into a priority queue
   246  		// The values that should come last are least.
   247  		priq.score = score
   248  		priq.a = priq.a[:0]
   249  
   250  		// Initialize priority queue with schedulable values.
   251  		for _, v := range b.Values {
   252  			if uses[v.ID] == 0 {
   253  				heap.Push(priq, v)
   254  			}
   255  		}
   256  
   257  		// Schedule highest priority value, update use counts, repeat.
   258  		order = order[:0]
   259  		tuples := make(map[ID][]*Value)
   260  		for priq.Len() > 0 {
   261  			// Find highest priority schedulable value.
   262  			// Note that schedule is assembled backwards.
   263  
   264  			v := heap.Pop(priq).(*Value)
   265  
   266  			// Add it to the schedule.
   267  			// Do not emit tuple-reading ops until we're ready to emit the tuple-generating op.
   268  			//TODO: maybe remove ReadTuple score above, if it does not help on performance
   269  			switch {
   270  			case v.Op == OpSelect0:
   271  				if tuples[v.Args[0].ID] == nil {
   272  					tuples[v.Args[0].ID] = make([]*Value, 2)
   273  				}
   274  				tuples[v.Args[0].ID][0] = v
   275  			case v.Op == OpSelect1:
   276  				if tuples[v.Args[0].ID] == nil {
   277  					tuples[v.Args[0].ID] = make([]*Value, 2)
   278  				}
   279  				tuples[v.Args[0].ID][1] = v
   280  			case v.Op == OpSelectN:
   281  				if tuples[v.Args[0].ID] == nil {
   282  					tuples[v.Args[0].ID] = make([]*Value, v.Args[0].Type.NumFields())
   283  				}
   284  				tuples[v.Args[0].ID][v.AuxInt] = v
   285  			case v.Type.IsResults() && tuples[v.ID] != nil:
   286  				tup := tuples[v.ID]
   287  				for i := len(tup) - 1; i >= 0; i-- {
   288  					if tup[i] != nil {
   289  						order = append(order, tup[i])
   290  					}
   291  				}
   292  				delete(tuples, v.ID)
   293  				order = append(order, v)
   294  			case v.Type.IsTuple() && tuples[v.ID] != nil:
   295  				if tuples[v.ID][1] != nil {
   296  					order = append(order, tuples[v.ID][1])
   297  				}
   298  				if tuples[v.ID][0] != nil {
   299  					order = append(order, tuples[v.ID][0])
   300  				}
   301  				delete(tuples, v.ID)
   302  				fallthrough
   303  			default:
   304  				order = append(order, v)
   305  			}
   306  
   307  			// Update use counts of arguments.
   308  			for _, w := range v.Args {
   309  				if w.Block != b {
   310  					continue
   311  				}
   312  				uses[w.ID]--
   313  				if uses[w.ID] == 0 {
   314  					// All uses scheduled, w is now schedulable.
   315  					heap.Push(priq, w)
   316  				}
   317  			}
   318  			for _, w := range additionalArgs[v.ID] {
   319  				uses[w.ID]--
   320  				if uses[w.ID] == 0 {
   321  					// All uses scheduled, w is now schedulable.
   322  					heap.Push(priq, w)
   323  				}
   324  			}
   325  		}
   326  		if len(order) != len(b.Values) {
   327  			f.Fatalf("schedule does not include all values in block %s", b)
   328  		}
   329  		for i := 0; i < len(b.Values); i++ {
   330  			b.Values[i] = order[len(b.Values)-1-i]
   331  		}
   332  	}
   333  
   334  	f.scheduled = true
   335  }
   336  
   337  // storeOrder orders values with respect to stores. That is,
   338  // if v transitively depends on store s, v is ordered after s,
   339  // otherwise v is ordered before s.
   340  // Specifically, values are ordered like
   341  //   store1
   342  //   NilCheck that depends on store1
   343  //   other values that depends on store1
   344  //   store2
   345  //   NilCheck that depends on store2
   346  //   other values that depends on store2
   347  //   ...
   348  // The order of non-store and non-NilCheck values are undefined
   349  // (not necessarily dependency order). This should be cheaper
   350  // than a full scheduling as done above.
   351  // Note that simple dependency order won't work: there is no
   352  // dependency between NilChecks and values like IsNonNil.
   353  // Auxiliary data structures are passed in as arguments, so
   354  // that they can be allocated in the caller and be reused.
   355  // This function takes care of reset them.
   356  func storeOrder(values []*Value, sset *sparseSet, storeNumber []int32) []*Value {
   357  	if len(values) == 0 {
   358  		return values
   359  	}
   360  
   361  	f := values[0].Block.Func
   362  
   363  	// find all stores
   364  
   365  	// Members of values that are store values.
   366  	// A constant bound allows this to be stack-allocated. 64 is
   367  	// enough to cover almost every storeOrder call.
   368  	stores := make([]*Value, 0, 64)
   369  	hasNilCheck := false
   370  	sset.clear() // sset is the set of stores that are used in other values
   371  	for _, v := range values {
   372  		if v.Type.IsMemory() {
   373  			stores = append(stores, v)
   374  			if v.Op == OpInitMem || v.Op == OpPhi {
   375  				continue
   376  			}
   377  			sset.add(v.MemoryArg().ID) // record that v's memory arg is used
   378  		}
   379  		if v.Op == OpNilCheck {
   380  			hasNilCheck = true
   381  		}
   382  	}
   383  	if len(stores) == 0 || !hasNilCheck && f.pass.name == "nilcheckelim" {
   384  		// there is no store, the order does not matter
   385  		return values
   386  	}
   387  
   388  	// find last store, which is the one that is not used by other stores
   389  	var last *Value
   390  	for _, v := range stores {
   391  		if !sset.contains(v.ID) {
   392  			if last != nil {
   393  				f.Fatalf("two stores live simultaneously: %v and %v", v, last)
   394  			}
   395  			last = v
   396  		}
   397  	}
   398  
   399  	// We assign a store number to each value. Store number is the
   400  	// index of the latest store that this value transitively depends.
   401  	// The i-th store in the current block gets store number 3*i. A nil
   402  	// check that depends on the i-th store gets store number 3*i+1.
   403  	// Other values that depends on the i-th store gets store number 3*i+2.
   404  	// Special case: 0 -- unassigned, 1 or 2 -- the latest store it depends
   405  	// is in the previous block (or no store at all, e.g. value is Const).
   406  	// First we assign the number to all stores by walking back the store chain,
   407  	// then assign the number to other values in DFS order.
   408  	count := make([]int32, 3*(len(stores)+1))
   409  	sset.clear() // reuse sparse set to ensure that a value is pushed to stack only once
   410  	for n, w := len(stores), last; n > 0; n-- {
   411  		storeNumber[w.ID] = int32(3 * n)
   412  		count[3*n]++
   413  		sset.add(w.ID)
   414  		if w.Op == OpInitMem || w.Op == OpPhi {
   415  			if n != 1 {
   416  				f.Fatalf("store order is wrong: there are stores before %v", w)
   417  			}
   418  			break
   419  		}
   420  		w = w.MemoryArg()
   421  	}
   422  	var stack []*Value
   423  	for _, v := range values {
   424  		if sset.contains(v.ID) {
   425  			// in sset means v is a store, or already pushed to stack, or already assigned a store number
   426  			continue
   427  		}
   428  		stack = append(stack, v)
   429  		sset.add(v.ID)
   430  
   431  		for len(stack) > 0 {
   432  			w := stack[len(stack)-1]
   433  			if storeNumber[w.ID] != 0 {
   434  				stack = stack[:len(stack)-1]
   435  				continue
   436  			}
   437  			if w.Op == OpPhi {
   438  				// Phi value doesn't depend on store in the current block.
   439  				// Do this early to avoid dependency cycle.
   440  				storeNumber[w.ID] = 2
   441  				count[2]++
   442  				stack = stack[:len(stack)-1]
   443  				continue
   444  			}
   445  
   446  			max := int32(0) // latest store dependency
   447  			argsdone := true
   448  			for _, a := range w.Args {
   449  				if a.Block != w.Block {
   450  					continue
   451  				}
   452  				if !sset.contains(a.ID) {
   453  					stack = append(stack, a)
   454  					sset.add(a.ID)
   455  					argsdone = false
   456  					break
   457  				}
   458  				if storeNumber[a.ID]/3 > max {
   459  					max = storeNumber[a.ID] / 3
   460  				}
   461  			}
   462  			if !argsdone {
   463  				continue
   464  			}
   465  
   466  			n := 3*max + 2
   467  			if w.Op == OpNilCheck {
   468  				n = 3*max + 1
   469  			}
   470  			storeNumber[w.ID] = n
   471  			count[n]++
   472  			stack = stack[:len(stack)-1]
   473  		}
   474  	}
   475  
   476  	// convert count to prefix sum of counts: count'[i] = sum_{j<=i} count[i]
   477  	for i := range count {
   478  		if i == 0 {
   479  			continue
   480  		}
   481  		count[i] += count[i-1]
   482  	}
   483  	if count[len(count)-1] != int32(len(values)) {
   484  		f.Fatalf("storeOrder: value is missing, total count = %d, values = %v", count[len(count)-1], values)
   485  	}
   486  
   487  	// place values in count-indexed bins, which are in the desired store order
   488  	order := make([]*Value, len(values))
   489  	for _, v := range values {
   490  		s := storeNumber[v.ID]
   491  		order[count[s-1]] = v
   492  		count[s-1]++
   493  	}
   494  
   495  	// Order nil checks in source order. We want the first in source order to trigger.
   496  	// If two are on the same line, we don't really care which happens first.
   497  	// See issue 18169.
   498  	if hasNilCheck {
   499  		start := -1
   500  		for i, v := range order {
   501  			if v.Op == OpNilCheck {
   502  				if start == -1 {
   503  					start = i
   504  				}
   505  			} else {
   506  				if start != -1 {
   507  					sort.Sort(bySourcePos(order[start:i]))
   508  					start = -1
   509  				}
   510  			}
   511  		}
   512  		if start != -1 {
   513  			sort.Sort(bySourcePos(order[start:]))
   514  		}
   515  	}
   516  
   517  	return order
   518  }
   519  
   520  type bySourcePos []*Value
   521  
   522  func (s bySourcePos) Len() int           { return len(s) }
   523  func (s bySourcePos) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
   524  func (s bySourcePos) Less(i, j int) bool { return s[i].Pos.Before(s[j].Pos) }
   525
View as plain text