Source file src/pkg/cmd/compile/internal/ssa/likelyadjust.go

     1	// Copyright 2016 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		"fmt"
     9	)
    10	
    11	type loop struct {
    12		header *Block // The header node of this (reducible) loop
    13		outer  *loop  // loop containing this loop
    14	
    15		// By default, children, exits, and depth are not initialized.
    16		children []*loop  // loops nested directly within this loop. Initialized by assembleChildren().
    17		exits    []*Block // exits records blocks reached by exits from this loop. Initialized by findExits().
    18	
    19		// Next three fields used by regalloc and/or
    20		// aid in computation of inner-ness and list of blocks.
    21		nBlocks int32 // Number of blocks in this loop but not within inner loops
    22		depth   int16 // Nesting depth of the loop; 1 is outermost. Initialized by calculateDepths().
    23		isInner bool  // True if never discovered to contain a loop
    24	
    25		// register allocation uses this.
    26		containsUnavoidableCall bool // True if all paths through the loop have a call
    27	}
    28	
    29	// outerinner records that outer contains inner
    30	func (sdom SparseTree) outerinner(outer, inner *loop) {
    31		// There could be other outer loops found in some random order,
    32		// locate the new outer loop appropriately among them.
    33	
    34		// Outer loop headers dominate inner loop headers.
    35		// Use this to put the "new" "outer" loop in the right place.
    36		oldouter := inner.outer
    37		for oldouter != nil && sdom.isAncestor(outer.header, oldouter.header) {
    38			inner = oldouter
    39			oldouter = inner.outer
    40		}
    41		if outer == oldouter {
    42			return
    43		}
    44		if oldouter != nil {
    45			sdom.outerinner(oldouter, outer)
    46		}
    47	
    48		inner.outer = outer
    49		outer.isInner = false
    50	}
    51	
    52	func checkContainsCall(bb *Block) bool {
    53		if bb.Kind == BlockDefer {
    54			return true
    55		}
    56		for _, v := range bb.Values {
    57			if opcodeTable[v.Op].call {
    58				return true
    59			}
    60		}
    61		return false
    62	}
    63	
    64	type loopnest struct {
    65		f              *Func
    66		b2l            []*loop
    67		po             []*Block
    68		sdom           SparseTree
    69		loops          []*loop
    70		hasIrreducible bool // TODO current treatment of irreducible loops is very flaky, if accurate loops are needed, must punt at function level.
    71	
    72		// Record which of the lazily initialized fields have actually been initialized.
    73		initializedChildren, initializedDepth, initializedExits bool
    74	}
    75	
    76	func min8(a, b int8) int8 {
    77		if a < b {
    78			return a
    79		}
    80		return b
    81	}
    82	
    83	func max8(a, b int8) int8 {
    84		if a > b {
    85			return a
    86		}
    87		return b
    88	}
    89	
    90	const (
    91		blDEFAULT = 0
    92		blMin     = blDEFAULT
    93		blCALL    = 1
    94		blRET     = 2
    95		blEXIT    = 3
    96	)
    97	
    98	var bllikelies = [4]string{"default", "call", "ret", "exit"}
    99	
   100	func describePredictionAgrees(b *Block, prediction BranchPrediction) string {
   101		s := ""
   102		if prediction == b.Likely {
   103			s = " (agrees with previous)"
   104		} else if b.Likely != BranchUnknown {
   105			s = " (disagrees with previous, ignored)"
   106		}
   107		return s
   108	}
   109	
   110	func describeBranchPrediction(f *Func, b *Block, likely, not int8, prediction BranchPrediction) {
   111		f.Warnl(b.Pos, "Branch prediction rule %s < %s%s",
   112			bllikelies[likely-blMin], bllikelies[not-blMin], describePredictionAgrees(b, prediction))
   113	}
   114	
   115	func likelyadjust(f *Func) {
   116		// The values assigned to certain and local only matter
   117		// in their rank order.  0 is default, more positive
   118		// is less likely. It's possible to assign a negative
   119		// unlikeliness (though not currently the case).
   120		certain := make([]int8, f.NumBlocks()) // In the long run, all outcomes are at least this bad. Mainly for Exit
   121		local := make([]int8, f.NumBlocks())   // for our immediate predecessors.
   122	
   123		po := f.postorder()
   124		nest := f.loopnest()
   125		b2l := nest.b2l
   126	
   127		for _, b := range po {
   128			switch b.Kind {
   129			case BlockExit:
   130				// Very unlikely.
   131				local[b.ID] = blEXIT
   132				certain[b.ID] = blEXIT
   133	
   134				// Ret, it depends.
   135			case BlockRet, BlockRetJmp:
   136				local[b.ID] = blRET
   137				certain[b.ID] = blRET
   138	
   139				// Calls. TODO not all calls are equal, names give useful clues.
   140				// Any name-based heuristics are only relative to other calls,
   141				// and less influential than inferences from loop structure.
   142			case BlockDefer:
   143				local[b.ID] = blCALL
   144				certain[b.ID] = max8(blCALL, certain[b.Succs[0].b.ID])
   145	
   146			default:
   147				if len(b.Succs) == 1 {
   148					certain[b.ID] = certain[b.Succs[0].b.ID]
   149				} else if len(b.Succs) == 2 {
   150					// If successor is an unvisited backedge, it's in loop and we don't care.
   151					// Its default unlikely is also zero which is consistent with favoring loop edges.
   152					// Notice that this can act like a "reset" on unlikeliness at loops; the
   153					// default "everything returns" unlikeliness is erased by min with the
   154					// backedge likeliness; however a loop with calls on every path will be
   155					// tagged with call cost. Net effect is that loop entry is favored.
   156					b0 := b.Succs[0].b.ID
   157					b1 := b.Succs[1].b.ID
   158					certain[b.ID] = min8(certain[b0], certain[b1])
   159	
   160					l := b2l[b.ID]
   161					l0 := b2l[b0]
   162					l1 := b2l[b1]
   163	
   164					prediction := b.Likely
   165					// Weak loop heuristic -- both source and at least one dest are in loops,
   166					// and there is a difference in the destinations.
   167					// TODO what is best arrangement for nested loops?
   168					if l != nil && l0 != l1 {
   169						noprediction := false
   170						switch {
   171						// prefer not to exit loops
   172						case l1 == nil:
   173							prediction = BranchLikely
   174						case l0 == nil:
   175							prediction = BranchUnlikely
   176	
   177							// prefer to stay in loop, not exit to outer.
   178						case l == l0:
   179							prediction = BranchLikely
   180						case l == l1:
   181							prediction = BranchUnlikely
   182						default:
   183							noprediction = true
   184						}
   185						if f.pass.debug > 0 && !noprediction {
   186							f.Warnl(b.Pos, "Branch prediction rule stay in loop%s",
   187								describePredictionAgrees(b, prediction))
   188						}
   189	
   190					} else {
   191						// Lacking loop structure, fall back on heuristics.
   192						if certain[b1] > certain[b0] {
   193							prediction = BranchLikely
   194							if f.pass.debug > 0 {
   195								describeBranchPrediction(f, b, certain[b0], certain[b1], prediction)
   196							}
   197						} else if certain[b0] > certain[b1] {
   198							prediction = BranchUnlikely
   199							if f.pass.debug > 0 {
   200								describeBranchPrediction(f, b, certain[b1], certain[b0], prediction)
   201							}
   202						} else if local[b1] > local[b0] {
   203							prediction = BranchLikely
   204							if f.pass.debug > 0 {
   205								describeBranchPrediction(f, b, local[b0], local[b1], prediction)
   206							}
   207						} else if local[b0] > local[b1] {
   208							prediction = BranchUnlikely
   209							if f.pass.debug > 0 {
   210								describeBranchPrediction(f, b, local[b1], local[b0], prediction)
   211							}
   212						}
   213					}
   214					if b.Likely != prediction {
   215						if b.Likely == BranchUnknown {
   216							b.Likely = prediction
   217						}
   218					}
   219				}
   220				// Look for calls in the block.  If there is one, make this block unlikely.
   221				for _, v := range b.Values {
   222					if opcodeTable[v.Op].call {
   223						local[b.ID] = blCALL
   224						certain[b.ID] = max8(blCALL, certain[b.Succs[0].b.ID])
   225					}
   226				}
   227			}
   228			if f.pass.debug > 2 {
   229				f.Warnl(b.Pos, "BP: Block %s, local=%s, certain=%s", b, bllikelies[local[b.ID]-blMin], bllikelies[certain[b.ID]-blMin])
   230			}
   231	
   232		}
   233	}
   234	
   235	func (l *loop) String() string {
   236		return fmt.Sprintf("hdr:%s", l.header)
   237	}
   238	
   239	func (l *loop) LongString() string {
   240		i := ""
   241		o := ""
   242		if l.isInner {
   243			i = ", INNER"
   244		}
   245		if l.outer != nil {
   246			o = ", o=" + l.outer.header.String()
   247		}
   248		return fmt.Sprintf("hdr:%s%s%s", l.header, i, o)
   249	}
   250	
   251	func (l *loop) isWithinOrEq(ll *loop) bool {
   252		if ll == nil { // nil means whole program
   253			return true
   254		}
   255		for ; l != nil; l = l.outer {
   256			if l == ll {
   257				return true
   258			}
   259		}
   260		return false
   261	}
   262	
   263	// nearestOuterLoop returns the outer loop of loop most nearly
   264	// containing block b; the header must dominate b.  loop itself
   265	// is assumed to not be that loop. For acceptable performance,
   266	// we're relying on loop nests to not be terribly deep.
   267	func (l *loop) nearestOuterLoop(sdom SparseTree, b *Block) *loop {
   268		var o *loop
   269		for o = l.outer; o != nil && !sdom.isAncestorEq(o.header, b); o = o.outer {
   270		}
   271		return o
   272	}
   273	
   274	func loopnestfor(f *Func) *loopnest {
   275		po := f.postorder()
   276		sdom := f.sdom()
   277		b2l := make([]*loop, f.NumBlocks())
   278		loops := make([]*loop, 0)
   279		visited := make([]bool, f.NumBlocks())
   280		sawIrred := false
   281	
   282		if f.pass.debug > 2 {
   283			fmt.Printf("loop finding in %s\n", f.Name)
   284		}
   285	
   286		// Reducible-loop-nest-finding.
   287		for _, b := range po {
   288			if f.pass != nil && f.pass.debug > 3 {
   289				fmt.Printf("loop finding at %s\n", b)
   290			}
   291	
   292			var innermost *loop // innermost header reachable from this block
   293	
   294			// IF any successor s of b is in a loop headed by h
   295			// AND h dominates b
   296			// THEN b is in the loop headed by h.
   297			//
   298			// Choose the first/innermost such h.
   299			//
   300			// IF s itself dominates b, then s is a loop header;
   301			// and there may be more than one such s.
   302			// Since there's at most 2 successors, the inner/outer ordering
   303			// between them can be established with simple comparisons.
   304			for _, e := range b.Succs {
   305				bb := e.b
   306				l := b2l[bb.ID]
   307	
   308				if sdom.isAncestorEq(bb, b) { // Found a loop header
   309					if f.pass != nil && f.pass.debug > 4 {
   310						fmt.Printf("loop finding    succ %s of %s is header\n", bb.String(), b.String())
   311					}
   312					if l == nil {
   313						l = &loop{header: bb, isInner: true}
   314						loops = append(loops, l)
   315						b2l[bb.ID] = l
   316					}
   317				} else if !visited[bb.ID] { // Found an irreducible loop
   318					sawIrred = true
   319					if f.pass != nil && f.pass.debug > 4 {
   320						fmt.Printf("loop finding    succ %s of %s is IRRED, in %s\n", bb.String(), b.String(), f.Name)
   321					}
   322				} else if l != nil {
   323					// TODO handle case where l is irreducible.
   324					// Perhaps a loop header is inherited.
   325					// is there any loop containing our successor whose
   326					// header dominates b?
   327					if !sdom.isAncestorEq(l.header, b) {
   328						l = l.nearestOuterLoop(sdom, b)
   329					}
   330					if f.pass != nil && f.pass.debug > 4 {
   331						if l == nil {
   332							fmt.Printf("loop finding    succ %s of %s has no loop\n", bb.String(), b.String())
   333						} else {
   334							fmt.Printf("loop finding    succ %s of %s provides loop with header %s\n", bb.String(), b.String(), l.header.String())
   335						}
   336					}
   337				} else { // No loop
   338					if f.pass != nil && f.pass.debug > 4 {
   339						fmt.Printf("loop finding    succ %s of %s has no loop\n", bb.String(), b.String())
   340					}
   341	
   342				}
   343	
   344				if l == nil || innermost == l {
   345					continue
   346				}
   347	
   348				if innermost == nil {
   349					innermost = l
   350					continue
   351				}
   352	
   353				if sdom.isAncestor(innermost.header, l.header) {
   354					sdom.outerinner(innermost, l)
   355					innermost = l
   356				} else if sdom.isAncestor(l.header, innermost.header) {
   357					sdom.outerinner(l, innermost)
   358				}
   359			}
   360	
   361			if innermost != nil {
   362				b2l[b.ID] = innermost
   363				innermost.nBlocks++
   364			}
   365			visited[b.ID] = true
   366		}
   367	
   368		ln := &loopnest{f: f, b2l: b2l, po: po, sdom: sdom, loops: loops, hasIrreducible: sawIrred}
   369	
   370		// Calculate containsUnavoidableCall for regalloc
   371		dominatedByCall := make([]bool, f.NumBlocks())
   372		for _, b := range po {
   373			if checkContainsCall(b) {
   374				dominatedByCall[b.ID] = true
   375			}
   376		}
   377		// Run dfs to find path through the loop that avoids all calls.
   378		// Such path either escapes loop or return back to header.
   379		// It isn't enough to have exit not dominated by any call, for example:
   380		// ... some loop
   381		// call1   call2
   382		//   \      /
   383		//     exit
   384		// ...
   385		// exit is not dominated by any call, but we don't have call-free path to it.
   386		for _, l := range loops {
   387			// Header contains call.
   388			if dominatedByCall[l.header.ID] {
   389				l.containsUnavoidableCall = true
   390				continue
   391			}
   392			callfreepath := false
   393			tovisit := make([]*Block, 0, len(l.header.Succs))
   394			// Push all non-loop non-exit successors of header onto toVisit.
   395			for _, s := range l.header.Succs {
   396				nb := s.Block()
   397				// This corresponds to loop with zero iterations.
   398				if !l.iterationEnd(nb, b2l) {
   399					tovisit = append(tovisit, nb)
   400				}
   401			}
   402			for len(tovisit) > 0 {
   403				cur := tovisit[len(tovisit)-1]
   404				tovisit = tovisit[:len(tovisit)-1]
   405				if dominatedByCall[cur.ID] {
   406					continue
   407				}
   408				// Record visited in dominatedByCall.
   409				dominatedByCall[cur.ID] = true
   410				for _, s := range cur.Succs {
   411					nb := s.Block()
   412					if l.iterationEnd(nb, b2l) {
   413						callfreepath = true
   414					}
   415					if !dominatedByCall[nb.ID] {
   416						tovisit = append(tovisit, nb)
   417					}
   418	
   419				}
   420				if callfreepath {
   421					break
   422				}
   423			}
   424			if !callfreepath {
   425				l.containsUnavoidableCall = true
   426			}
   427		}
   428	
   429		// Curious about the loopiness? "-d=ssa/likelyadjust/stats"
   430		if f.pass != nil && f.pass.stats > 0 && len(loops) > 0 {
   431			ln.assembleChildren()
   432			ln.calculateDepths()
   433			ln.findExits()
   434	
   435			// Note stats for non-innermost loops are slightly flawed because
   436			// they don't account for inner loop exits that span multiple levels.
   437	
   438			for _, l := range loops {
   439				x := len(l.exits)
   440				cf := 0
   441				if !l.containsUnavoidableCall {
   442					cf = 1
   443				}
   444				inner := 0
   445				if l.isInner {
   446					inner++
   447				}
   448	
   449				f.LogStat("loopstats:",
   450					l.depth, "depth", x, "exits",
   451					inner, "is_inner", cf, "always_calls", l.nBlocks, "n_blocks")
   452			}
   453		}
   454	
   455		if f.pass != nil && f.pass.debug > 1 && len(loops) > 0 {
   456			fmt.Printf("Loops in %s:\n", f.Name)
   457			for _, l := range loops {
   458				fmt.Printf("%s, b=", l.LongString())
   459				for _, b := range f.Blocks {
   460					if b2l[b.ID] == l {
   461						fmt.Printf(" %s", b)
   462					}
   463				}
   464				fmt.Print("\n")
   465			}
   466			fmt.Printf("Nonloop blocks in %s:", f.Name)
   467			for _, b := range f.Blocks {
   468				if b2l[b.ID] == nil {
   469					fmt.Printf(" %s", b)
   470				}
   471			}
   472			fmt.Print("\n")
   473		}
   474		return ln
   475	}
   476	
   477	// assembleChildren initializes the children field of each
   478	// loop in the nest.  Loop A is a child of loop B if A is
   479	// directly nested within B (based on the reducible-loops
   480	// detection above)
   481	func (ln *loopnest) assembleChildren() {
   482		if ln.initializedChildren {
   483			return
   484		}
   485		for _, l := range ln.loops {
   486			if l.outer != nil {
   487				l.outer.children = append(l.outer.children, l)
   488			}
   489		}
   490		ln.initializedChildren = true
   491	}
   492	
   493	// calculateDepths uses the children field of loops
   494	// to determine the nesting depth (outer=1) of each
   495	// loop.  This is helpful for finding exit edges.
   496	func (ln *loopnest) calculateDepths() {
   497		if ln.initializedDepth {
   498			return
   499		}
   500		ln.assembleChildren()
   501		for _, l := range ln.loops {
   502			if l.outer == nil {
   503				l.setDepth(1)
   504			}
   505		}
   506		ln.initializedDepth = true
   507	}
   508	
   509	// findExits uses loop depth information to find the
   510	// exits from a loop.
   511	func (ln *loopnest) findExits() {
   512		if ln.initializedExits {
   513			return
   514		}
   515		ln.calculateDepths()
   516		b2l := ln.b2l
   517		for _, b := range ln.po {
   518			l := b2l[b.ID]
   519			if l != nil && len(b.Succs) == 2 {
   520				sl := b2l[b.Succs[0].b.ID]
   521				if recordIfExit(l, sl, b.Succs[0].b) {
   522					continue
   523				}
   524				sl = b2l[b.Succs[1].b.ID]
   525				if recordIfExit(l, sl, b.Succs[1].b) {
   526					continue
   527				}
   528			}
   529		}
   530		ln.initializedExits = true
   531	}
   532	
   533	// depth returns the loop nesting level of block b.
   534	func (ln *loopnest) depth(b ID) int16 {
   535		if l := ln.b2l[b]; l != nil {
   536			return l.depth
   537		}
   538		return 0
   539	}
   540	
   541	// recordIfExit checks sl (the loop containing b) to see if it
   542	// is outside of loop l, and if so, records b as an exit block
   543	// from l and returns true.
   544	func recordIfExit(l, sl *loop, b *Block) bool {
   545		if sl != l {
   546			if sl == nil || sl.depth <= l.depth {
   547				l.exits = append(l.exits, b)
   548				return true
   549			}
   550			// sl is not nil, and is deeper than l
   551			// it's possible for this to be a goto into an irreducible loop made from gotos.
   552			for sl.depth > l.depth {
   553				sl = sl.outer
   554			}
   555			if sl != l {
   556				l.exits = append(l.exits, b)
   557				return true
   558			}
   559		}
   560		return false
   561	}
   562	
   563	func (l *loop) setDepth(d int16) {
   564		l.depth = d
   565		for _, c := range l.children {
   566			c.setDepth(d + 1)
   567		}
   568	}
   569	
   570	// iterationEnd checks if block b ends iteration of loop l.
   571	// Ending iteration means either escaping to outer loop/code or
   572	// going back to header
   573	func (l *loop) iterationEnd(b *Block, b2l []*loop) bool {
   574		return b == l.header || b2l[b.ID] == nil || (b2l[b.ID] != l && b2l[b.ID].depth <= l.depth)
   575	}
   576	

View as plain text