Source file src/pkg/cmd/compile/internal/ssa/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		"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 priq.Len() > 0 {
   237				// Find highest priority schedulable value.
   238				// Note that schedule is assembled backwards.
   239	
   240				v := heap.Pop(priq).(*Value)
   241	
   242				// Add it to the schedule.
   243				// Do not emit tuple-reading ops until we're ready to emit the tuple-generating op.
   244				//TODO: maybe remove ReadTuple score above, if it does not help on performance
   245				switch {
   246				case v.Op == OpSelect0:
   247					if tuples[v.Args[0].ID] == nil {
   248						tuples[v.Args[0].ID] = make([]*Value, 2)
   249					}
   250					tuples[v.Args[0].ID][0] = v
   251				case v.Op == OpSelect1:
   252					if tuples[v.Args[0].ID] == nil {
   253						tuples[v.Args[0].ID] = make([]*Value, 2)
   254					}
   255					tuples[v.Args[0].ID][1] = v
   256				case v.Type.IsTuple() && tuples[v.ID] != nil:
   257					if tuples[v.ID][1] != nil {
   258						order = append(order, tuples[v.ID][1])
   259					}
   260					if tuples[v.ID][0] != nil {
   261						order = append(order, tuples[v.ID][0])
   262					}
   263					delete(tuples, v.ID)
   264					fallthrough
   265				default:
   266					order = append(order, v)
   267				}
   268	
   269				// Update use counts of arguments.
   270				for _, w := range v.Args {
   271					if w.Block != b {
   272						continue
   273					}
   274					uses[w.ID]--
   275					if uses[w.ID] == 0 {
   276						// All uses scheduled, w is now schedulable.
   277						heap.Push(priq, w)
   278					}
   279				}
   280				for _, w := range additionalArgs[v.ID] {
   281					uses[w.ID]--
   282					if uses[w.ID] == 0 {
   283						// All uses scheduled, w is now schedulable.
   284						heap.Push(priq, w)
   285					}
   286				}
   287			}
   288			if len(order) != len(b.Values) {
   289				f.Fatalf("schedule does not include all values in block %s", b)
   290			}
   291			for i := 0; i < len(b.Values); i++ {
   292				b.Values[i] = order[len(b.Values)-1-i]
   293			}
   294		}
   295	
   296		f.scheduled = true
   297	}
   298	
   299	// storeOrder orders values with respect to stores. That is,
   300	// if v transitively depends on store s, v is ordered after s,
   301	// otherwise v is ordered before s.
   302	// Specifically, values are ordered like
   303	//   store1
   304	//   NilCheck that depends on store1
   305	//   other values that depends on store1
   306	//   store2
   307	//   NilCheck that depends on store2
   308	//   other values that depends on store2
   309	//   ...
   310	// The order of non-store and non-NilCheck values are undefined
   311	// (not necessarily dependency order). This should be cheaper
   312	// than a full scheduling as done above.
   313	// Note that simple dependency order won't work: there is no
   314	// dependency between NilChecks and values like IsNonNil.
   315	// Auxiliary data structures are passed in as arguments, so
   316	// that they can be allocated in the caller and be reused.
   317	// This function takes care of reset them.
   318	func storeOrder(values []*Value, sset *sparseSet, storeNumber []int32) []*Value {
   319		if len(values) == 0 {
   320			return values
   321		}
   322	
   323		f := values[0].Block.Func
   324	
   325		// find all stores
   326	
   327		// Members of values that are store values.
   328		// A constant bound allows this to be stack-allocated. 64 is
   329		// enough to cover almost every storeOrder call.
   330		stores := make([]*Value, 0, 64)
   331		hasNilCheck := false
   332		sset.clear() // sset is the set of stores that are used in other values
   333		for _, v := range values {
   334			if v.Type.IsMemory() {
   335				stores = append(stores, v)
   336				if v.Op == OpInitMem || v.Op == OpPhi {
   337					continue
   338				}
   339				sset.add(v.MemoryArg().ID) // record that v's memory arg is used
   340			}
   341			if v.Op == OpNilCheck {
   342				hasNilCheck = true
   343			}
   344		}
   345		if len(stores) == 0 || !hasNilCheck && f.pass.name == "nilcheckelim" {
   346			// there is no store, the order does not matter
   347			return values
   348		}
   349	
   350		// find last store, which is the one that is not used by other stores
   351		var last *Value
   352		for _, v := range stores {
   353			if !sset.contains(v.ID) {
   354				if last != nil {
   355					f.Fatalf("two stores live simultaneously: %v and %v", v, last)
   356				}
   357				last = v
   358			}
   359		}
   360	
   361		// We assign a store number to each value. Store number is the
   362		// index of the latest store that this value transitively depends.
   363		// The i-th store in the current block gets store number 3*i. A nil
   364		// check that depends on the i-th store gets store number 3*i+1.
   365		// Other values that depends on the i-th store gets store number 3*i+2.
   366		// Special case: 0 -- unassigned, 1 or 2 -- the latest store it depends
   367		// is in the previous block (or no store at all, e.g. value is Const).
   368		// First we assign the number to all stores by walking back the store chain,
   369		// then assign the number to other values in DFS order.
   370		count := make([]int32, 3*(len(stores)+1))
   371		sset.clear() // reuse sparse set to ensure that a value is pushed to stack only once
   372		for n, w := len(stores), last; n > 0; n-- {
   373			storeNumber[w.ID] = int32(3 * n)
   374			count[3*n]++
   375			sset.add(w.ID)
   376			if w.Op == OpInitMem || w.Op == OpPhi {
   377				if n != 1 {
   378					f.Fatalf("store order is wrong: there are stores before %v", w)
   379				}
   380				break
   381			}
   382			w = w.MemoryArg()
   383		}
   384		var stack []*Value
   385		for _, v := range values {
   386			if sset.contains(v.ID) {
   387				// in sset means v is a store, or already pushed to stack, or already assigned a store number
   388				continue
   389			}
   390			stack = append(stack, v)
   391			sset.add(v.ID)
   392	
   393			for len(stack) > 0 {
   394				w := stack[len(stack)-1]
   395				if storeNumber[w.ID] != 0 {
   396					stack = stack[:len(stack)-1]
   397					continue
   398				}
   399				if w.Op == OpPhi {
   400					// Phi value doesn't depend on store in the current block.
   401					// Do this early to avoid dependency cycle.
   402					storeNumber[w.ID] = 2
   403					count[2]++
   404					stack = stack[:len(stack)-1]
   405					continue
   406				}
   407	
   408				max := int32(0) // latest store dependency
   409				argsdone := true
   410				for _, a := range w.Args {
   411					if a.Block != w.Block {
   412						continue
   413					}
   414					if !sset.contains(a.ID) {
   415						stack = append(stack, a)
   416						sset.add(a.ID)
   417						argsdone = false
   418						break
   419					}
   420					if storeNumber[a.ID]/3 > max {
   421						max = storeNumber[a.ID] / 3
   422					}
   423				}
   424				if !argsdone {
   425					continue
   426				}
   427	
   428				n := 3*max + 2
   429				if w.Op == OpNilCheck {
   430					n = 3*max + 1
   431				}
   432				storeNumber[w.ID] = n
   433				count[n]++
   434				stack = stack[:len(stack)-1]
   435			}
   436		}
   437	
   438		// convert count to prefix sum of counts: count'[i] = sum_{j<=i} count[i]
   439		for i := range count {
   440			if i == 0 {
   441				continue
   442			}
   443			count[i] += count[i-1]
   444		}
   445		if count[len(count)-1] != int32(len(values)) {
   446			f.Fatalf("storeOrder: value is missing, total count = %d, values = %v", count[len(count)-1], values)
   447		}
   448	
   449		// place values in count-indexed bins, which are in the desired store order
   450		order := make([]*Value, len(values))
   451		for _, v := range values {
   452			s := storeNumber[v.ID]
   453			order[count[s-1]] = v
   454			count[s-1]++
   455		}
   456	
   457		// Order nil checks in source order. We want the first in source order to trigger.
   458		// If two are on the same line, we don't really care which happens first.
   459		// See issue 18169.
   460		if hasNilCheck {
   461			start := -1
   462			for i, v := range order {
   463				if v.Op == OpNilCheck {
   464					if start == -1 {
   465						start = i
   466					}
   467				} else {
   468					if start != -1 {
   469						sort.Sort(bySourcePos(order[start:i]))
   470						start = -1
   471					}
   472				}
   473			}
   474			if start != -1 {
   475				sort.Sort(bySourcePos(order[start:]))
   476			}
   477		}
   478	
   479		return order
   480	}
   481	
   482	type bySourcePos []*Value
   483	
   484	func (s bySourcePos) Len() int           { return len(s) }
   485	func (s bySourcePos) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
   486	func (s bySourcePos) Less(i, j int) bool { return s[i].Pos.Before(s[j].Pos) }
   487	

View as plain text