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 ssacompile
     6  
     7  import (
     8  	"cmd/compile/internal/ssa"
     9  	"cmd/compile/internal/ssa/block"
    10  	"cmd/compile/internal/ssa/ssaop"
    11  )
    12  
    13  const (
    14  	blDEFAULT = 0
    15  	blMin     = blDEFAULT
    16  	blCALL    = 1
    17  	blRET     = 2
    18  	blEXIT    = 3
    19  )
    20  
    21  var bllikelies = [4]string{"default", "call", "ret", "exit"}
    22  
    23  func describePredictionAgrees(b *ssa.Block, prediction ssa.BranchPrediction) string {
    24  	s := ""
    25  	if prediction == b.Likely {
    26  		s = " (agrees with previous)"
    27  	} else if b.Likely != ssa.BranchUnknown {
    28  		s = " (disagrees with previous, ignored)"
    29  	}
    30  	return s
    31  }
    32  
    33  func describeBranchPrediction(f *ssa.Func, b *ssa.Block, likely, not int8, prediction ssa.BranchPrediction) {
    34  	f.Warnl(b.Pos, "Branch prediction rule %s < %s%s",
    35  		bllikelies[likely-blMin], bllikelies[not-blMin], describePredictionAgrees(b, prediction))
    36  }
    37  
    38  func likelyadjust(f *ssa.Func) {
    39  	// The values assigned to certain and local only matter
    40  	// in their rank order.  0 is default, more positive
    41  	// is less likely. It's possible to assign a negative
    42  	// unlikeliness (though not currently the case).
    43  	certain := f.Cache.AllocInt8Slice(f.NumBlocks()) // In the long run, all outcomes are at least this bad. Mainly for Exit
    44  	defer f.Cache.FreeInt8Slice(certain)
    45  	local := f.Cache.AllocInt8Slice(f.NumBlocks()) // for our immediate predecessors.
    46  	defer f.Cache.FreeInt8Slice(local)
    47  
    48  	po := f.Postorder()
    49  	nest := f.Loopnest()
    50  	b2l := nest.B2L
    51  
    52  	for _, b := range po {
    53  		switch b.Kind {
    54  		case block.BlockExit:
    55  			// Very unlikely.
    56  			local[b.ID] = blEXIT
    57  			certain[b.ID] = blEXIT
    58  
    59  			// Ret, it depends.
    60  		case block.BlockRet, block.BlockRetJmp:
    61  			local[b.ID] = blRET
    62  			certain[b.ID] = blRET
    63  
    64  			// Calls. TODO not all calls are equal, names give useful clues.
    65  			// Any name-based heuristics are only relative to other calls,
    66  			// and less influential than inferences from loop structure.
    67  		case block.BlockDefer:
    68  			local[b.ID] = blCALL
    69  			certain[b.ID] = max(blCALL, certain[b.Succs[0].B.ID])
    70  
    71  		default:
    72  			if len(b.Succs) == 1 {
    73  				certain[b.ID] = certain[b.Succs[0].B.ID]
    74  			} else if len(b.Succs) == 2 {
    75  				// If successor is an unvisited backedge, it's in loop and we don't care.
    76  				// Its default unlikely is also zero which is consistent with favoring loop edges.
    77  				// Notice that this can act like a "reset" on unlikeliness at loops; the
    78  				// default "everything returns" unlikeliness is erased by min with the
    79  				// backedge likeliness; however a loop with calls on every path will be
    80  				// tagged with call cost. Net effect is that loop entry is favored.
    81  				b0 := b.Succs[0].B.ID
    82  				b1 := b.Succs[1].B.ID
    83  				certain[b.ID] = min(certain[b0], certain[b1])
    84  
    85  				l := b2l[b.ID]
    86  				l0 := b2l[b0]
    87  				l1 := b2l[b1]
    88  
    89  				prediction := b.Likely
    90  				// Weak loop heuristic -- both source and at least one dest are in loops,
    91  				// and there is a difference in the destinations.
    92  				// TODO what is best arrangement for nested loops?
    93  				if l != nil && l0 != l1 {
    94  					noprediction := false
    95  					switch {
    96  					// prefer not to exit loops
    97  					case l1 == nil:
    98  						prediction = ssa.BranchLikely
    99  					case l0 == nil:
   100  						prediction = ssa.BranchUnlikely
   101  
   102  						// prefer to stay in loop, not exit to outer.
   103  					case l == l0:
   104  						prediction = ssa.BranchLikely
   105  					case l == l1:
   106  						prediction = ssa.BranchUnlikely
   107  					default:
   108  						noprediction = true
   109  					}
   110  					if f.Pass.Debug > 0 && !noprediction {
   111  						f.Warnl(b.Pos, "Branch prediction rule stay in loop%s",
   112  							describePredictionAgrees(b, prediction))
   113  					}
   114  
   115  				} else {
   116  					// Lacking loop structure, fall back on heuristics.
   117  					if certain[b1] > certain[b0] {
   118  						prediction = ssa.BranchLikely
   119  						if f.Pass.Debug > 0 {
   120  							describeBranchPrediction(f, b, certain[b0], certain[b1], prediction)
   121  						}
   122  					} else if certain[b0] > certain[b1] {
   123  						prediction = ssa.BranchUnlikely
   124  						if f.Pass.Debug > 0 {
   125  							describeBranchPrediction(f, b, certain[b1], certain[b0], prediction)
   126  						}
   127  					} else if local[b1] > local[b0] {
   128  						prediction = ssa.BranchLikely
   129  						if f.Pass.Debug > 0 {
   130  							describeBranchPrediction(f, b, local[b0], local[b1], prediction)
   131  						}
   132  					} else if local[b0] > local[b1] {
   133  						prediction = ssa.BranchUnlikely
   134  						if f.Pass.Debug > 0 {
   135  							describeBranchPrediction(f, b, local[b1], local[b0], prediction)
   136  						}
   137  					}
   138  				}
   139  				if b.Likely != prediction {
   140  					if b.Likely == ssa.BranchUnknown {
   141  						b.Likely = prediction
   142  					}
   143  				}
   144  			}
   145  			// Look for calls in the block.  If there is one, make this block unlikely.
   146  			for _, v := range b.Values {
   147  				if ssaop.OpcodeTable[v.Op].Call {
   148  					local[b.ID] = blCALL
   149  					certain[b.ID] = max(blCALL, certain[b.Succs[0].B.ID])
   150  					break
   151  				}
   152  			}
   153  		}
   154  		if f.Pass.Debug > 2 {
   155  			f.Warnl(b.Pos, "BP: Block %s, local=%s, certain=%s", b, bllikelies[local[b.ID]-blMin], bllikelies[certain[b.ID]-blMin])
   156  		}
   157  
   158  	}
   159  }
   160
View as plain text