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