scoring.go

     1  // Copyright 2023 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 inlheur
     6  
     7  import (
     8  	"cmd/compile/internal/base"
     9  	"cmd/compile/internal/ir"
    10  	"cmd/compile/internal/pgoir"
    11  	"cmd/compile/internal/types"
    12  	"cmp"
    13  	"fmt"
    14  	"os"
    15  	"slices"
    16  	"strconv"
    17  	"strings"
    18  )
    19  
    20  // These constants enumerate the set of possible ways/scenarios
    21  // in which we'll adjust the score of a given callsite.
    22  type scoreAdjustTyp uint
    23  
    24  // These constants capture the various ways in which the inliner's
    25  // scoring phase can adjust a callsite score based on heuristics. They
    26  // fall broadly into three categories:
    27  //
    28  // 1) adjustments based solely on the callsite context (ex: call
    29  // appears on panic path)
    30  //
    31  // 2) adjustments that take into account specific interesting values
    32  // passed at a call site (ex: passing a constant that could result in
    33  // cprop/deadcode in the caller)
    34  //
    35  // 3) adjustments that take into account values returned from the call
    36  // at a callsite (ex: call always returns the same inlinable function,
    37  // and return value flows unmodified into an indirect call)
    38  //
    39  // For categories 2 and 3 above, each adjustment can have either a
    40  // "must" version and a "may" version (but not both). Here the idea is
    41  // that in the "must" version the value flow is unconditional: if the
    42  // callsite executes, then the condition we're interested in (ex:
    43  // param feeding call) is guaranteed to happen. For the "may" version,
    44  // there may be control flow that could cause the benefit to be
    45  // bypassed.
    46  const (
    47  	// Category 1 adjustments (see above)
    48  	panicPathAdj scoreAdjustTyp = (1 << iota)
    49  	initFuncAdj
    50  	inLoopAdj
    51  
    52  	// Category 2 adjustments (see above).
    53  	passConstToIfAdj
    54  	passConstToNestedIfAdj
    55  	passConcreteToItfCallAdj
    56  	passConcreteToNestedItfCallAdj
    57  	passFuncToIndCallAdj
    58  	passFuncToNestedIndCallAdj
    59  	passInlinableFuncToIndCallAdj
    60  	passInlinableFuncToNestedIndCallAdj
    61  
    62  	// Category 3 adjustments.
    63  	returnFeedsConstToIfAdj
    64  	returnFeedsFuncToIndCallAdj
    65  	returnFeedsInlinableFuncToIndCallAdj
    66  	returnFeedsConcreteToInterfaceCallAdj
    67  
    68  	sentinelScoreAdj // sentinel; not a real adjustment
    69  )
    70  
    71  // This table records the specific values we use to adjust call
    72  // site scores in a given scenario.
    73  // NOTE: these numbers are chosen very arbitrarily; ideally
    74  // we will go through some sort of turning process to decide
    75  // what value for each one produces the best performance.
    76  
    77  var adjValues = map[scoreAdjustTyp]int{
    78  	panicPathAdj:                          40,
    79  	initFuncAdj:                           20,
    80  	inLoopAdj:                             -5,
    81  	passConstToIfAdj:                      -20,
    82  	passConstToNestedIfAdj:                -15,
    83  	passConcreteToItfCallAdj:              -30,
    84  	passConcreteToNestedItfCallAdj:        -25,
    85  	passFuncToIndCallAdj:                  -25,
    86  	passFuncToNestedIndCallAdj:            -20,
    87  	passInlinableFuncToIndCallAdj:         -45,
    88  	passInlinableFuncToNestedIndCallAdj:   -40,
    89  	returnFeedsConstToIfAdj:               -15,
    90  	returnFeedsFuncToIndCallAdj:           -25,
    91  	returnFeedsInlinableFuncToIndCallAdj:  -40,
    92  	returnFeedsConcreteToInterfaceCallAdj: -25,
    93  }
    94  
    95  // SetupScoreAdjustments interprets the value of the -d=inlscoreadj
    96  // debugging option, if set. The value of this flag is expected to be
    97  // a series of "/"-separated clauses of the form adj1:value1. Example:
    98  // -d=inlscoreadj=inLoopAdj=0/passConstToIfAdj=-99
    99  func SetupScoreAdjustments() {
   100  	if base.Debug.InlScoreAdj == "" {
   101  		return
   102  	}
   103  	if err := parseScoreAdj(base.Debug.InlScoreAdj); err != nil {
   104  		base.Fatalf("malformed -d=inlscoreadj argument %q: %v",
   105  			base.Debug.InlScoreAdj, err)
   106  	}
   107  }
   108  
   109  func adjStringToVal(s string) (scoreAdjustTyp, bool) {
   110  	for adj := scoreAdjustTyp(1); adj < sentinelScoreAdj; adj <<= 1 {
   111  		if adj.String() == s {
   112  			return adj, true
   113  		}
   114  	}
   115  	return 0, false
   116  }
   117  
   118  func parseScoreAdj(val string) error {
   119  	clauses := strings.Split(val, "/")
   120  	if len(clauses) == 0 {
   121  		return fmt.Errorf("no clauses")
   122  	}
   123  	for _, clause := range clauses {
   124  		elems := strings.Split(clause, ":")
   125  		if len(elems) < 2 {
   126  			return fmt.Errorf("clause %q: expected colon", clause)
   127  		}
   128  		if len(elems) != 2 {
   129  			return fmt.Errorf("clause %q has %d elements, wanted 2", clause,
   130  				len(elems))
   131  		}
   132  		adj, ok := adjStringToVal(elems[0])
   133  		if !ok {
   134  			return fmt.Errorf("clause %q: unknown adjustment", clause)
   135  		}
   136  		val, err := strconv.Atoi(elems[1])
   137  		if err != nil {
   138  			return fmt.Errorf("clause %q: malformed value: %v", clause, err)
   139  		}
   140  		adjValues[adj] = val
   141  	}
   142  	return nil
   143  }
   144  
   145  func adjValue(x scoreAdjustTyp) int {
   146  	if val, ok := adjValues[x]; ok {
   147  		return val
   148  	} else {
   149  		panic("internal error unregistered adjustment type")
   150  	}
   151  }
   152  
   153  var mayMustAdj = [...]struct{ may, must scoreAdjustTyp }{
   154  	{may: passConstToNestedIfAdj, must: passConstToIfAdj},
   155  	{may: passConcreteToNestedItfCallAdj, must: passConcreteToItfCallAdj},
   156  	{may: passFuncToNestedIndCallAdj, must: passFuncToNestedIndCallAdj},
   157  	{may: passInlinableFuncToNestedIndCallAdj, must: passInlinableFuncToIndCallAdj},
   158  }
   159  
   160  func isMay(x scoreAdjustTyp) bool {
   161  	return mayToMust(x) != 0
   162  }
   163  
   164  func isMust(x scoreAdjustTyp) bool {
   165  	return mustToMay(x) != 0
   166  }
   167  
   168  func mayToMust(x scoreAdjustTyp) scoreAdjustTyp {
   169  	for _, v := range mayMustAdj {
   170  		if x == v.may {
   171  			return v.must
   172  		}
   173  	}
   174  	return 0
   175  }
   176  
   177  func mustToMay(x scoreAdjustTyp) scoreAdjustTyp {
   178  	for _, v := range mayMustAdj {
   179  		if x == v.must {
   180  			return v.may
   181  		}
   182  	}
   183  	return 0
   184  }
   185  
   186  // computeCallSiteScore takes a given call site whose ir node is
   187  // 'call' and callee function is 'callee' and with previously computed
   188  // call site properties 'csflags', then computes a score for the
   189  // callsite that combines the size cost of the callee with heuristics
   190  // based on previously computed argument and function properties,
   191  // then stores the score and the adjustment mask in the appropriate
   192  // fields in 'cs'
   193  func (cs *CallSite) computeCallSiteScore(csa *callSiteAnalyzer, calleeProps *FuncProps) {
   194  	callee := cs.Callee
   195  	csflags := cs.Flags
   196  	call := cs.Call
   197  
   198  	// Start with the size-based score for the callee.
   199  	score := int(callee.Inl.Cost)
   200  	var tmask scoreAdjustTyp
   201  
   202  	if debugTrace&debugTraceScoring != 0 {
   203  		fmt.Fprintf(os.Stderr, "=-= scoring call to %s at %s , initial=%d\n",
   204  			callee.Sym().Name, fmtFullPos(call.Pos()), score)
   205  	}
   206  
   207  	// First some score adjustments to discourage inlining in selected cases.
   208  	if csflags&CallSiteOnPanicPath != 0 {
   209  		score, tmask = adjustScore(panicPathAdj, score, tmask)
   210  	}
   211  	if csflags&CallSiteInInitFunc != 0 {
   212  		score, tmask = adjustScore(initFuncAdj, score, tmask)
   213  	}
   214  
   215  	// Then adjustments to encourage inlining in selected cases.
   216  	if csflags&CallSiteInLoop != 0 {
   217  		score, tmask = adjustScore(inLoopAdj, score, tmask)
   218  	}
   219  
   220  	// Stop here if no callee props.
   221  	if calleeProps == nil {
   222  		cs.Score, cs.ScoreMask = score, tmask
   223  		return
   224  	}
   225  
   226  	// Walk through the actual expressions being passed at the call.
   227  	calleeRecvrParms := callee.Type().RecvParams()
   228  	for idx := range call.Args {
   229  		// ignore blanks
   230  		if calleeRecvrParms[idx].Sym == nil ||
   231  			calleeRecvrParms[idx].Sym.IsBlank() {
   232  			continue
   233  		}
   234  		arg := call.Args[idx]
   235  		pflag := calleeProps.ParamFlags[idx]
   236  		if debugTrace&debugTraceScoring != 0 {
   237  			fmt.Fprintf(os.Stderr, "=-= arg %d of %d: val %v flags=%s\n",
   238  				idx, len(call.Args), arg, pflag.String())
   239  		}
   240  
   241  		if len(cs.ArgProps) == 0 {
   242  			continue
   243  		}
   244  		argProps := cs.ArgProps[idx]
   245  
   246  		if debugTrace&debugTraceScoring != 0 {
   247  			fmt.Fprintf(os.Stderr, "=-= arg %d props %s value %v\n",
   248  				idx, argProps.String(), arg)
   249  		}
   250  
   251  		if argProps&ActualExprConstant != 0 {
   252  			if pflag&ParamMayFeedIfOrSwitch != 0 {
   253  				score, tmask = adjustScore(passConstToNestedIfAdj, score, tmask)
   254  			}
   255  			if pflag&ParamFeedsIfOrSwitch != 0 {
   256  				score, tmask = adjustScore(passConstToIfAdj, score, tmask)
   257  			}
   258  		}
   259  
   260  		if argProps&ActualExprIsConcreteConvIface != 0 {
   261  			// FIXME: ideally here it would be nice to make a
   262  			// distinction between the inlinable case and the
   263  			// non-inlinable case, but this is hard to do. Example:
   264  			//
   265  			//    type I interface { Tiny() int; Giant() }
   266  			//    type Conc struct { x int }
   267  			//    func (c *Conc) Tiny() int { return 42 }
   268  			//    func (c *Conc) Giant() { <huge amounts of code> }
   269  			//
   270  			//    func passConcToItf(c *Conc) {
   271  			//        makesItfMethodCall(c)
   272  			//    }
   273  			//
   274  			// In the code above, function properties will only tell
   275  			// us that 'makesItfMethodCall' invokes a method on its
   276  			// interface parameter, but we don't know whether it calls
   277  			// "Tiny" or "Giant". If we knew if called "Tiny", then in
   278  			// theory in addition to converting the interface call to
   279  			// a direct call, we could also inline (in which case
   280  			// we'd want to decrease the score even more).
   281  			//
   282  			// One thing we could do (not yet implemented) is iterate
   283  			// through all of the methods of "*Conc" that allow it to
   284  			// satisfy I, and if all are inlinable, then exploit that.
   285  			if pflag&ParamMayFeedInterfaceMethodCall != 0 {
   286  				score, tmask = adjustScore(passConcreteToNestedItfCallAdj, score, tmask)
   287  			}
   288  			if pflag&ParamFeedsInterfaceMethodCall != 0 {
   289  				score, tmask = adjustScore(passConcreteToItfCallAdj, score, tmask)
   290  			}
   291  		}
   292  
   293  		if argProps&(ActualExprIsFunc|ActualExprIsInlinableFunc) != 0 {
   294  			mayadj := passFuncToNestedIndCallAdj
   295  			mustadj := passFuncToIndCallAdj
   296  			if argProps&ActualExprIsInlinableFunc != 0 {
   297  				mayadj = passInlinableFuncToNestedIndCallAdj
   298  				mustadj = passInlinableFuncToIndCallAdj
   299  			}
   300  			if pflag&ParamMayFeedIndirectCall != 0 {
   301  				score, tmask = adjustScore(mayadj, score, tmask)
   302  			}
   303  			if pflag&ParamFeedsIndirectCall != 0 {
   304  				score, tmask = adjustScore(mustadj, score, tmask)
   305  			}
   306  		}
   307  	}
   308  
   309  	cs.Score, cs.ScoreMask = score, tmask
   310  }
   311  
   312  func adjustScore(typ scoreAdjustTyp, score int, mask scoreAdjustTyp) (int, scoreAdjustTyp) {
   313  
   314  	if isMust(typ) {
   315  		if mask&typ != 0 {
   316  			return score, mask
   317  		}
   318  		may := mustToMay(typ)
   319  		if mask&may != 0 {
   320  			// promote may to must, so undo may
   321  			score -= adjValue(may)
   322  			mask &^= may
   323  		}
   324  	} else if isMay(typ) {
   325  		must := mayToMust(typ)
   326  		if mask&(must|typ) != 0 {
   327  			return score, mask
   328  		}
   329  	}
   330  	if mask&typ == 0 {
   331  		if debugTrace&debugTraceScoring != 0 {
   332  			fmt.Fprintf(os.Stderr, "=-= applying adj %d for %s\n",
   333  				adjValue(typ), typ.String())
   334  		}
   335  		score += adjValue(typ)
   336  		mask |= typ
   337  	}
   338  	return score, mask
   339  }
   340  
   341  var resultFlagToPositiveAdj map[ResultPropBits]scoreAdjustTyp
   342  var paramFlagToPositiveAdj map[ParamPropBits]scoreAdjustTyp
   343  
   344  func setupFlagToAdjMaps() {
   345  	resultFlagToPositiveAdj = map[ResultPropBits]scoreAdjustTyp{
   346  		ResultIsAllocatedMem:     returnFeedsConcreteToInterfaceCallAdj,
   347  		ResultAlwaysSameFunc:     returnFeedsFuncToIndCallAdj,
   348  		ResultAlwaysSameConstant: returnFeedsConstToIfAdj,
   349  	}
   350  	paramFlagToPositiveAdj = map[ParamPropBits]scoreAdjustTyp{
   351  		ParamMayFeedInterfaceMethodCall: passConcreteToNestedItfCallAdj,
   352  		ParamFeedsInterfaceMethodCall:   passConcreteToItfCallAdj,
   353  		ParamMayFeedIndirectCall:        passInlinableFuncToNestedIndCallAdj,
   354  		ParamFeedsIndirectCall:          passInlinableFuncToIndCallAdj,
   355  	}
   356  }
   357  
   358  // LargestNegativeScoreAdjustment tries to estimate the largest possible
   359  // negative score adjustment that could be applied to a call of the
   360  // function with the specified props. Example:
   361  //
   362  //	func foo() {                  func bar(x int, p *int) int {
   363  //	   ...                          if x < 0 { *p = x }
   364  //	}                               return 99
   365  //	                              }
   366  //
   367  // Function 'foo' above on the left has no interesting properties,
   368  // thus as a result the most we'll adjust any call to is the value for
   369  // "call in loop". If the calculated cost of the function is 150, and
   370  // the in-loop adjustment is 5 (for example), then there is not much
   371  // point treating it as inlinable. On the other hand "bar" has a param
   372  // property (parameter "x" feeds unmodified to an "if" statement) and
   373  // a return property (always returns same constant) meaning that a
   374  // given call _could_ be rescored down as much as -35 points-- thus if
   375  // the size of "bar" is 100 (for example) then there is at least a
   376  // chance that scoring will enable inlining.
   377  func LargestNegativeScoreAdjustment(fn *ir.Func, props *FuncProps) int {
   378  	if resultFlagToPositiveAdj == nil {
   379  		setupFlagToAdjMaps()
   380  	}
   381  	var tmask scoreAdjustTyp
   382  	score := adjValues[inLoopAdj] // any call can be in a loop
   383  	for _, pf := range props.ParamFlags {
   384  		if adj, ok := paramFlagToPositiveAdj[pf]; ok {
   385  			score, tmask = adjustScore(adj, score, tmask)
   386  		}
   387  	}
   388  	for _, rf := range props.ResultFlags {
   389  		if adj, ok := resultFlagToPositiveAdj[rf]; ok {
   390  			score, tmask = adjustScore(adj, score, tmask)
   391  		}
   392  	}
   393  
   394  	if debugTrace&debugTraceScoring != 0 {
   395  		fmt.Fprintf(os.Stderr, "=-= largestScore(%v) is %d\n",
   396  			fn, score)
   397  	}
   398  
   399  	return score
   400  }
   401  
   402  // callSiteTab contains entries for each call in the function
   403  // currently being processed by InlineCalls; this variable will either
   404  // be set to 'cstabCache' below (for non-inlinable routines) or to the
   405  // local 'cstab' entry in the fnInlHeur object for inlinable routines.
   406  //
   407  // NOTE: this assumes that inlining operations are happening in a serial,
   408  // single-threaded fashion,f which is true today but probably won't hold
   409  // in the future (for example, we might want to score the callsites
   410  // in multiple functions in parallel); if the inliner evolves in this
   411  // direction we'll need to come up with a different approach here.
   412  var callSiteTab CallSiteTab
   413  
   414  // scoreCallsCache caches a call site table and call site list between
   415  // invocations of ScoreCalls so that we can reuse previously allocated
   416  // storage.
   417  var scoreCallsCache scoreCallsCacheType
   418  
   419  type scoreCallsCacheType struct {
   420  	tab CallSiteTab
   421  	csl []*CallSite
   422  }
   423  
   424  // ScoreCalls assigns numeric scores to each of the callsites in
   425  // function 'fn'; the lower the score, the more helpful we think it
   426  // will be to inline.
   427  //
   428  // Unlike a lot of the other inline heuristics machinery, callsite
   429  // scoring can't be done as part of the CanInline call for a function,
   430  // due to fact that we may be working on a non-trivial SCC. So for
   431  // example with this SCC:
   432  //
   433  //	func foo(x int) {           func bar(x int, f func()) {
   434  //	  if x != 0 {                  f()
   435  //	    bar(x, func(){})           foo(x-1)
   436  //	  }                         }
   437  //	}
   438  //
   439  // We don't want to perform scoring for the 'foo' call in "bar" until
   440  // after foo has been analyzed, but it's conceivable that CanInline
   441  // might visit bar before foo for this SCC.
   442  func ScoreCalls(fn *ir.Func) {
   443  	if len(fn.Body) == 0 {
   444  		return
   445  	}
   446  	enableDebugTraceIfEnv()
   447  
   448  	nameFinder := newNameFinder(fn)
   449  
   450  	if debugTrace&debugTraceScoring != 0 {
   451  		fmt.Fprintf(os.Stderr, "=-= ScoreCalls(%v)\n", ir.FuncName(fn))
   452  	}
   453  
   454  	// If this is an inlinable function, use the precomputed
   455  	// call site table for it. If the function wasn't an inline
   456  	// candidate, collect a callsite table for it now.
   457  	var cstab CallSiteTab
   458  	if funcInlHeur, ok := fpmap[fn]; ok {
   459  		cstab = funcInlHeur.cstab
   460  	} else {
   461  		if len(scoreCallsCache.tab) != 0 {
   462  			panic("missing call to ScoreCallsCleanup")
   463  		}
   464  		if scoreCallsCache.tab == nil {
   465  			scoreCallsCache.tab = make(CallSiteTab)
   466  		}
   467  		if debugTrace&debugTraceScoring != 0 {
   468  			fmt.Fprintf(os.Stderr, "=-= building cstab for non-inl func %s\n",
   469  				ir.FuncName(fn))
   470  		}
   471  		cstab = computeCallSiteTable(fn, fn.Body, scoreCallsCache.tab, nil, 0,
   472  			nameFinder)
   473  	}
   474  
   475  	csa := makeCallSiteAnalyzer(fn)
   476  	const doCallResults = true
   477  	csa.scoreCallsRegion(fn, fn.Body, cstab, doCallResults, nil)
   478  
   479  	disableDebugTrace()
   480  }
   481  
   482  // scoreCallsRegion assigns numeric scores to each of the callsites in
   483  // region 'region' within function 'fn'. This can be called on
   484  // an entire function, or with 'region' set to a chunk of
   485  // code corresponding to an inlined call.
   486  func (csa *callSiteAnalyzer) scoreCallsRegion(fn *ir.Func, region ir.Nodes, cstab CallSiteTab, doCallResults bool, ic *ir.InlinedCallExpr) {
   487  	if debugTrace&debugTraceScoring != 0 {
   488  		fmt.Fprintf(os.Stderr, "=-= scoreCallsRegion(%v, %s) len(cstab)=%d\n",
   489  			ir.FuncName(fn), region[0].Op().String(), len(cstab))
   490  	}
   491  
   492  	// Sort callsites to avoid any surprises with non deterministic
   493  	// map iteration order (this is probably not needed, but here just
   494  	// in case).
   495  	csl := scoreCallsCache.csl[:0]
   496  	for _, cs := range cstab {
   497  		csl = append(csl, cs)
   498  	}
   499  	scoreCallsCache.csl = csl[:0]
   500  	slices.SortFunc(csl, func(a, b *CallSite) int {
   501  		return cmp.Compare(a.ID, b.ID)
   502  	})
   503  
   504  	// Score each call site.
   505  	var resultNameTab map[*ir.Name]resultPropAndCS
   506  	for _, cs := range csl {
   507  		var cprops *FuncProps
   508  		fihcprops := false
   509  		desercprops := false
   510  		if funcInlHeur, ok := fpmap[cs.Callee]; ok {
   511  			cprops = funcInlHeur.props
   512  			fihcprops = true
   513  		} else if cs.Callee.Inl != nil {
   514  			cprops = DeserializeFromString(cs.Callee.Inl.Properties)
   515  			desercprops = true
   516  		} else {
   517  			if base.Debug.DumpInlFuncProps != "" {
   518  				fmt.Fprintf(os.Stderr, "=-= *** unable to score call to %s from %s\n", cs.Callee.Sym().Name, fmtFullPos(cs.Call.Pos()))
   519  				panic("should never happen")
   520  			} else {
   521  				continue
   522  			}
   523  		}
   524  		cs.computeCallSiteScore(csa, cprops)
   525  
   526  		if doCallResults {
   527  			if debugTrace&debugTraceScoring != 0 {
   528  				fmt.Fprintf(os.Stderr, "=-= examineCallResults at %s: flags=%d score=%d funcInlHeur=%v deser=%v\n", fmtFullPos(cs.Call.Pos()), cs.Flags, cs.Score, fihcprops, desercprops)
   529  			}
   530  			resultNameTab = csa.examineCallResults(cs, resultNameTab)
   531  		}
   532  
   533  		if debugTrace&debugTraceScoring != 0 {
   534  			fmt.Fprintf(os.Stderr, "=-= scoring call at %s: flags=%d score=%d funcInlHeur=%v deser=%v\n", fmtFullPos(cs.Call.Pos()), cs.Flags, cs.Score, fihcprops, desercprops)
   535  		}
   536  	}
   537  
   538  	if resultNameTab != nil {
   539  		csa.rescoreBasedOnCallResultUses(fn, resultNameTab, cstab)
   540  	}
   541  
   542  	disableDebugTrace()
   543  
   544  	if ic != nil && callSiteTab != nil {
   545  		// Integrate the calls from this cstab into the table for the caller.
   546  		if err := callSiteTab.merge(cstab); err != nil {
   547  			base.FatalfAt(ic.Pos(), "%v", err)
   548  		}
   549  	} else {
   550  		callSiteTab = cstab
   551  	}
   552  }
   553  
   554  // ScoreCallsCleanup resets the state of the callsite cache
   555  // once ScoreCalls is done with a function.
   556  func ScoreCallsCleanup() {
   557  	if base.Debug.DumpInlCallSiteScores != 0 {
   558  		if allCallSites == nil {
   559  			allCallSites = make(CallSiteTab)
   560  		}
   561  		for call, cs := range callSiteTab {
   562  			allCallSites[call] = cs
   563  		}
   564  	}
   565  	clear(scoreCallsCache.tab)
   566  }
   567  
   568  // GetCallSiteScore returns the previously calculated score for call
   569  // within fn.
   570  func GetCallSiteScore(fn *ir.Func, call *ir.CallExpr) (int, bool) {
   571  	if funcInlHeur, ok := fpmap[fn]; ok {
   572  		if cs, ok := funcInlHeur.cstab[call]; ok {
   573  			return cs.Score, true
   574  		}
   575  	}
   576  	if cs, ok := callSiteTab[call]; ok {
   577  		return cs.Score, true
   578  	}
   579  	return 0, false
   580  }
   581  
   582  // BudgetExpansion returns the amount to relax/expand the base
   583  // inlining budget when the new inliner is turned on; the inliner
   584  // will add the returned value to the hairiness budget.
   585  //
   586  // Background: with the new inliner, the score for a given callsite
   587  // can be adjusted down by some amount due to heuristics, however we
   588  // won't know whether this is going to happen until much later after
   589  // the CanInline call. This function returns the amount to relax the
   590  // budget initially (to allow for a large score adjustment); later on
   591  // in RevisitInlinability we'll look at each individual function to
   592  // demote it if needed.
   593  func BudgetExpansion(maxBudget int32) int32 {
   594  	if base.Debug.InlBudgetSlack != 0 {
   595  		return int32(base.Debug.InlBudgetSlack)
   596  	}
   597  	// In the default case, return maxBudget, which will effectively
   598  	// double the budget from 80 to 160; this should be good enough
   599  	// for most cases.
   600  	return maxBudget
   601  }
   602  
   603  var allCallSites CallSiteTab
   604  
   605  // DumpInlCallSiteScores is invoked by the inliner if the debug flag
   606  // "-d=dumpinlcallsitescores" is set; it dumps out a human-readable
   607  // summary of all (potentially) inlinable callsites in the package,
   608  // along with info on call site scoring and the adjustments made to a
   609  // given score. Here profile is the PGO profile in use (may be
   610  // nil), budgetCallback is a callback that can be invoked to find out
   611  // the original pre-adjustment hairiness limit for the function, and
   612  // inlineHotMaxBudget is the constant of the same name used in the
   613  // inliner. Sample output lines:
   614  //
   615  // Score  Adjustment  Status  Callee  CallerPos ScoreFlags
   616  // 115    40          DEMOTED cmd/compile/internal/abi.(*ABIParamAssignment).Offset     expand_calls.go:1679:14|6       panicPathAdj
   617  // 76     -5n         PROMOTED runtime.persistentalloc   mcheckmark.go:48:45|3   inLoopAdj
   618  // 201    0           --- PGO  unicode.DecodeRuneInString        utf8.go:312:30|1
   619  // 7      -5          --- PGO  internal/abi.Name.DataChecked     type.go:625:22|0        inLoopAdj
   620  //
   621  // In the dump above, "Score" is the final score calculated for the
   622  // callsite, "Adjustment" is the amount added to or subtracted from
   623  // the original hairiness estimate to form the score. "Status" shows
   624  // whether anything changed with the site -- did the adjustment bump
   625  // it down just below the threshold ("PROMOTED") or instead bump it
   626  // above the threshold ("DEMOTED"); this will be blank ("---") if no
   627  // threshold was crossed as a result of the heuristics. Note that
   628  // "Status" also shows whether PGO was involved. "Callee" is the name
   629  // of the function called, "CallerPos" is the position of the
   630  // callsite, and "ScoreFlags" is a digest of the specific properties
   631  // we used to make adjustments to callsite score via heuristics.
   632  func DumpInlCallSiteScores(profile *pgoir.Profile, budgetCallback func(fn *ir.Func, profile *pgoir.Profile) (int32, bool)) {
   633  
   634  	var indirectlyDueToPromotion func(cs *CallSite) bool
   635  	indirectlyDueToPromotion = func(cs *CallSite) bool {
   636  		bud, _ := budgetCallback(cs.Callee, profile)
   637  		hairyval := cs.Callee.Inl.Cost
   638  		score := int32(cs.Score)
   639  		if hairyval > bud && score <= bud {
   640  			return true
   641  		}
   642  		if cs.parent != nil {
   643  			return indirectlyDueToPromotion(cs.parent)
   644  		}
   645  		return false
   646  	}
   647  
   648  	genstatus := func(cs *CallSite) string {
   649  		hairyval := cs.Callee.Inl.Cost
   650  		bud, isPGO := budgetCallback(cs.Callee, profile)
   651  		score := int32(cs.Score)
   652  		st := "---"
   653  		expinl := false
   654  		switch {
   655  		case hairyval <= bud && score <= bud:
   656  			// "Normal" inlined case: hairy val sufficiently low that
   657  			// it would have been inlined anyway without heuristics.
   658  			expinl = true
   659  		case hairyval > bud && score > bud:
   660  			// "Normal" not inlined case: hairy val sufficiently high
   661  			// and scoring didn't lower it.
   662  		case hairyval > bud && score <= bud:
   663  			// Promoted: we would not have inlined it before, but
   664  			// after score adjustment we decided to inline.
   665  			st = "PROMOTED"
   666  			expinl = true
   667  		case hairyval <= bud && score > bud:
   668  			// Demoted: we would have inlined it before, but after
   669  			// score adjustment we decided not to inline.
   670  			st = "DEMOTED"
   671  		}
   672  		inlined := cs.aux&csAuxInlined != 0
   673  		indprom := false
   674  		if cs.parent != nil {
   675  			indprom = indirectlyDueToPromotion(cs.parent)
   676  		}
   677  		if inlined && indprom {
   678  			st += "|INDPROM"
   679  		}
   680  		if inlined && !expinl {
   681  			st += "|[NI?]"
   682  		} else if !inlined && expinl {
   683  			st += "|[IN?]"
   684  		}
   685  		if isPGO {
   686  			st += "|PGO"
   687  		}
   688  		return st
   689  	}
   690  
   691  	if base.Debug.DumpInlCallSiteScores != 0 {
   692  		var sl []*CallSite
   693  		for _, cs := range allCallSites {
   694  			sl = append(sl, cs)
   695  		}
   696  		slices.SortFunc(sl, func(a, b *CallSite) int {
   697  			if a.Score != b.Score {
   698  				return cmp.Compare(a.Score, b.Score)
   699  			}
   700  			fni := ir.PkgFuncName(a.Callee)
   701  			fnj := ir.PkgFuncName(b.Callee)
   702  			if fni != fnj {
   703  				return cmp.Compare(fni, fnj)
   704  			}
   705  			ecsi := EncodeCallSiteKey(a)
   706  			ecsj := EncodeCallSiteKey(b)
   707  			return cmp.Compare(ecsi, ecsj)
   708  		})
   709  
   710  		mkname := func(fn *ir.Func) string {
   711  			var n string
   712  			if fn == nil || fn.Nname == nil {
   713  				return "<nil>"
   714  			}
   715  			if fn.Sym().Pkg == types.LocalPkg {
   716  				n = "·" + fn.Sym().Name
   717  			} else {
   718  				n = ir.PkgFuncName(fn)
   719  			}
   720  			// don't try to print super-long names
   721  			if len(n) <= 64 {
   722  				return n
   723  			}
   724  			return n[:32] + "..." + n[len(n)-32:len(n)]
   725  		}
   726  
   727  		if len(sl) != 0 {
   728  			fmt.Fprintf(os.Stdout, "# scores for package %s\n", types.LocalPkg.Path)
   729  			fmt.Fprintf(os.Stdout, "# Score  Adjustment  Status  Callee  CallerPos Flags ScoreFlags\n")
   730  		}
   731  		for _, cs := range sl {
   732  			hairyval := cs.Callee.Inl.Cost
   733  			adj := int32(cs.Score) - hairyval
   734  			nm := mkname(cs.Callee)
   735  			ecc := EncodeCallSiteKey(cs)
   736  			fmt.Fprintf(os.Stdout, "%d  %d\t%s\t%s\t%s\t%s\n",
   737  				cs.Score, adj, genstatus(cs),
   738  				nm, ecc,
   739  				cs.ScoreMask.String())
   740  		}
   741  	}
   742  }
   743
View as plain text