...
Run Format

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

View as plain text