src/cmd/compile/internal/inline/inlheur/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/pgo"
  11         "cmd/compile/internal/typecheck"
  12         "cmd/compile/internal/types"
  13         "fmt"
  14         "os"
  15         "sort"
  16 )
  17
  18 // These constants enumerate the set of possible ways/scenarios
  19 // in which we'll adjust the score of a given callsite.
  20 type scoreAdjustTyp uint
  21
  22 // These constants capture the various ways in which the inliner's
  23 // scoring phase can adjust a callsite score based on heuristics. They
  24 // fall broadly into three categories:
  25 //
  26 // 1) adjustments based solely on the callsite context (ex: call
  27 // appears on panic path)
  28 //
  29 // 2) adjustments that take into account specific interesting values
  30 // passed at a call site (ex: passing a constant that could result in
  31 // cprop/deadcode in the caller)
  32 //
  33 // 3) adjustments that take into account values returned from the call
  34 // at a callsite (ex: call always returns the same inlinable function,
  35 // and return value flows unmodified into an indirect call)
  36 //
  37 // For categories 2 and 3 above, each adjustment can have either a
  38 // "must" version and a "may" version (but not both). Here the idea is
  39 // that in the "must" version the value flow is unconditional: if the
  40 // callsite executes, then the condition we're interested in (ex:
  41 // param feeding call) is guaranteed to happen. For the "may" version,
  42 // there may be control flow that could cause the benefit to be
  43 // bypassed.
  44 const (
  45         // Catgegory 1 adjustments (see above)
  46         panicPathAdj scoreAdjustTyp = (1 << iota)
  47         initFuncAdj
  48         inLoopAdj
  49
  50         // Category 2 adjustments (see above).
  51         passConstToIfAdj
  52         passConstToNestedIfAdj
  53         passConcreteToItfCallAdj
  54         passConcreteToNestedItfCallAdj
  55         passFuncToIndCallAdj
  56         passFuncToNestedIndCallAdj
  57         passInlinableFuncToIndCallAdj
  58         passInlinableFuncToNestedIndCallAdj
  59
  60         // Category 3 adjustments.
  61         returnFeedsConstToIfAdj
  62         returnFeedsFuncToIndCallAdj
  63         returnFeedsInlinableFuncToIndCallAdj
  64         returnFeedsConcreteToInterfaceCallAdj
  65 )
  66
  67 // This table records the specific values we use to adjust call
  68 // site scores in a given scenario.
  69 // NOTE: these numbers are chosen very arbitrarily; ideally
  70 // we will go through some sort of turning process to decide
  71 // what value for each one produces the best performance.
  72
  73 var adjValues = map[scoreAdjustTyp]int{
  74         panicPathAdj:                          40,
  75         initFuncAdj:                           20,
  76         inLoopAdj:                             -5,
  77         passConstToIfAdj:                      -20,
  78         passConstToNestedIfAdj:                -15,
  79         passConcreteToItfCallAdj:              -30,
  80         passConcreteToNestedItfCallAdj:        -25,
  81         passFuncToIndCallAdj:                  -25,
  82         passFuncToNestedIndCallAdj:            -20,
  83         passInlinableFuncToIndCallAdj:         -45,
  84         passInlinableFuncToNestedIndCallAdj:   -40,
  85         returnFeedsConstToIfAdj:               -15,
  86         returnFeedsFuncToIndCallAdj:           -25,
  87         returnFeedsInlinableFuncToIndCallAdj:  -40,
  88         returnFeedsConcreteToInterfaceCallAdj: -25,
  89 }
  90
  91 func adjValue(x scoreAdjustTyp) int {
  92         if val, ok := adjValues[x]; ok {
  93                 return val
  94         } else {
  95                 panic("internal error unregistered adjustment type")
  96         }
  97 }
  98
  99 var mayMust = [...]struct{ may, must scoreAdjustTyp }{
 100         {may: passConstToNestedIfAdj, must: passConstToIfAdj},
 101         {may: passConcreteToNestedItfCallAdj, must: passConcreteToItfCallAdj},
 102         {may: passFuncToNestedIndCallAdj, must: passFuncToNestedIndCallAdj},
 103         {may: passInlinableFuncToNestedIndCallAdj, must: passInlinableFuncToIndCallAdj},
 104 }
 105
 106 func isMay(x scoreAdjustTyp) bool {
 107         return mayToMust(x) != 0
 108 }
 109
 110 func isMust(x scoreAdjustTyp) bool {
 111         return mustToMay(x) != 0
 112 }
 113
 114 func mayToMust(x scoreAdjustTyp) scoreAdjustTyp {
 115         for _, v := range mayMust {
 116                 if x == v.may {
 117                         return v.must
 118                 }
 119         }
 120         return 0
 121 }
 122
 123 func mustToMay(x scoreAdjustTyp) scoreAdjustTyp {
 124         for _, v := range mayMust {
 125                 if x == v.must {
 126                         return v.may
 127                 }
 128         }
 129         return 0
 130 }
 131
 132 // computeCallSiteScore takes a given call site whose ir node is 'call' and
 133 // callee function is 'callee' and with previously computed call site
 134 // properties 'csflags', then computes a score for the callsite that
 135 // combines the size cost of the callee with heuristics based on
 136 // previously parameter and function properties.
 137 func computeCallSiteScore(callee *ir.Func, calleeProps *FuncProps, call ir.Node, csflags CSPropBits) (int, scoreAdjustTyp) {
 138         // Start with the size-based score for the callee.
 139         score := int(callee.Inl.Cost)
 140         var tmask scoreAdjustTyp
 141
 142         if debugTrace&debugTraceScoring != 0 {
 143                 fmt.Fprintf(os.Stderr, "=-= scoring call to %s at %s , initial=%d\n",
 144                         callee.Sym().Name, fmtFullPos(call.Pos()), score)
 145         }
 146
 147         // First some score adjustments to discourage inlining in selected cases.
 148         if csflags&CallSiteOnPanicPath != 0 {
 149                 score, tmask = adjustScore(panicPathAdj, score, tmask)
 150         }
 151         if csflags&CallSiteInInitFunc != 0 {
 152                 score, tmask = adjustScore(initFuncAdj, score, tmask)
 153         }
 154
 155         // Then adjustments to encourage inlining in selected cases.
 156         if csflags&CallSiteInLoop != 0 {
 157                 score, tmask = adjustScore(inLoopAdj, score, tmask)
 158         }
 159
 160         // Walk through the actual expressions being passed at the call.
 161         calleeRecvrParms := callee.Type().RecvParams()
 162         ce := call.(*ir.CallExpr)
 163         for idx := range ce.Args {
 164                 // ignore blanks
 165                 if calleeRecvrParms[idx].Sym == nil ||
 166                         calleeRecvrParms[idx].Sym.IsBlank() {
 167                         continue
 168                 }
 169                 arg := ce.Args[idx]
 170                 pflag := calleeProps.ParamFlags[idx]
 171                 if debugTrace&debugTraceScoring != 0 {
 172                         fmt.Fprintf(os.Stderr, "=-= arg %d of %d: val %v flags=%s\n",
 173                                 idx, len(ce.Args), arg, pflag.String())
 174                 }
 175                 _, islit := isLiteral(arg)
 176                 iscci := isConcreteConvIface(arg)
 177                 fname, isfunc, _ := isFuncName(arg)
 178                 if debugTrace&debugTraceScoring != 0 {
 179                         fmt.Fprintf(os.Stderr, "=-= isLit=%v iscci=%v isfunc=%v for arg %v\n", islit, iscci, isfunc, arg)
 180                 }
 181
 182                 if islit {
 183                         if pflag&ParamMayFeedIfOrSwitch != 0 {
 184                                 score, tmask = adjustScore(passConstToNestedIfAdj, score, tmask)
 185                         }
 186                         if pflag&ParamFeedsIfOrSwitch != 0 {
 187                                 score, tmask = adjustScore(passConstToIfAdj, score, tmask)
 188                         }
 189                 }
 190
 191                 if iscci {
 192                         // FIXME: ideally here it would be nice to make a
 193                         // distinction between the inlinable case and the
 194                         // non-inlinable case, but this is hard to do. Example:
 195                         //
 196                         //    type I interface { Tiny() int; Giant() }
 197                         //    type Conc struct { x int }
 198                         //    func (c *Conc) Tiny() int { return 42 }
 199                         //    func (c *Conc) Giant() { <huge amounts of code> }
 200                         //
 201                         //    func passConcToItf(c *Conc) {
 202                         //        makesItfMethodCall(c)
 203                         //    }
 204                         //
 205                         // In the code above, function properties will only tell
 206                         // us that 'makesItfMethodCall' invokes a method on its
 207                         // interface parameter, but we don't know whether it calls
 208                         // "Tiny" or "Giant". If we knew if called "Tiny", then in
 209                         // theory in addition to converting the interface call to
 210                         // a direct call, we could also inline (in which case
 211                         // we'd want to decrease the score even more).
 212                         //
 213                         // One thing we could do (not yet implemented) is iterate
 214                         // through all of the methods of "*Conc" that allow it to
 215                         // satisfy I, and if all are inlinable, then exploit that.
 216                         if pflag&ParamMayFeedInterfaceMethodCall != 0 {
 217                                 score, tmask = adjustScore(passConcreteToNestedItfCallAdj, score, tmask)
 218                         }
 219                         if pflag&ParamFeedsInterfaceMethodCall != 0 {
 220                                 score, tmask = adjustScore(passConcreteToItfCallAdj, score, tmask)
 221                         }
 222                 }
 223
 224                 if isfunc {
 225                         mayadj := passFuncToNestedIndCallAdj
 226                         mustadj := passFuncToIndCallAdj
 227                         if fn := fname.Func; fn != nil && typecheck.HaveInlineBody(fn) {
 228                                 mayadj = passInlinableFuncToNestedIndCallAdj
 229                                 mustadj = passInlinableFuncToIndCallAdj
 230                         }
 231                         if pflag&ParamMayFeedIndirectCall != 0 {
 232                                 score, tmask = adjustScore(mayadj, score, tmask)
 233                         }
 234                         if pflag&ParamFeedsIndirectCall != 0 {
 235                                 score, tmask = adjustScore(mustadj, score, tmask)
 236                         }
 237                 }
 238         }
 239
 240         return score, tmask
 241 }
 242
 243 func adjustScore(typ scoreAdjustTyp, score int, mask scoreAdjustTyp) (int, scoreAdjustTyp) {
 244
 245         if isMust(typ) {
 246                 if mask&typ != 0 {
 247                         return score, mask
 248                 }
 249                 may := mustToMay(typ)
 250                 if mask&may != 0 {
 251                         // promote may to must, so undo may
 252                         score -= adjValue(may)
 253                         mask &^= may
 254                 }
 255         } else if isMay(typ) {
 256                 must := mayToMust(typ)
 257                 if mask&(must|typ) != 0 {
 258                         return score, mask
 259                 }
 260         }
 261         if mask&typ == 0 {
 262                 if debugTrace&debugTraceScoring != 0 {
 263                         fmt.Fprintf(os.Stderr, "=-= applying adj %d for %s\n",
 264                                 adjValue(typ), typ.String())
 265                 }
 266                 score += adjValue(typ)
 267                 mask |= typ
 268         }
 269         return score, mask
 270 }
 271
 272 // DumpInlCallSiteScores is invoked by the inliner if the debug flag
 273 // "-d=dumpinlcallsitescores" is set; it dumps out a human-readable
 274 // summary of all (potentially) inlinable callsites in the package,
 275 // along with info on call site scoring and the adjustments made to a
 276 // given score. Here profile is the PGO profile in use (may be
 277 // nil), budgetCallback is a callback that can be invoked to find out
 278 // the original pre-adjustment hairyness limit for the function, and
 279 // inlineHotMaxBudget is the constant of the same name used in the
 280 // inliner. Sample output lines:
 281 //
 282 // Score  Adjustment  Status  Callee  CallerPos ScoreFlags
 283 // 115    40          DEMOTED cmd/compile/internal/abi.(*ABIParamAssignment).Offset     expand_calls.go:1679:14|6       panicPathAdj
 284 // 76     -5n           PROMOTED runtime.persistentalloc   mcheckmark.go:48:45|3   inLoopAdj
 285 // 201    0           --- PGO  unicode.DecodeRuneInString        utf8.go:312:30|1
 286 // 7      -5          --- PGO  internal/abi.Name.DataChecked     type.go:625:22|0        inLoopAdj
 287 //
 288 // In the dump above, "Score" is the final score calculated for the
 289 // callsite, "Adjustment" is the amount added to or subtracted from
 290 // the original hairyness estimate to form the score. "Status" shows
 291 // whether anything changed with the site -- did the adjustment bump
 292 // it down just below the threshold ("PROMOTED") or instead bump it
 293 // above the threshold ("DEMOTED"); this will be blank ("---") if no
 294 // threshold was crossed as a result of the heuristics. Note that
 295 // "Status" also shows whether PGO was involved. "Callee" is the name
 296 // of the function called, "CallerPos" is the position of the
 297 // callsite, and "ScoreFlags" is a digest of the specific properties
 298 // we used to make adjustments to callsite score via heuristics.
 299 func DumpInlCallSiteScores(profile *pgo.Profile, budgetCallback func(fn *ir.Func, profile *pgo.Profile) (int32, bool)) {
 300
 301         fmt.Fprintf(os.Stdout, "# scores for package %s\n", types.LocalPkg.Path)
 302         cstab := CallSiteTable()
 303
 304         genstatus := func(cs *CallSite, prof *pgo.Profile) string {
 305                 hairyval := cs.Callee.Inl.Cost
 306                 bud, isPGO := budgetCallback(cs.Callee, prof)
 307                 score := int32(cs.Score)
 308                 st := "---"
 309
 310                 switch {
 311                 case hairyval <= bud && score <= bud:
 312                         // "Normal" inlined case: hairy val sufficiently low that
 313                         // it would have been inlined anyway without heuristics.
 314                 case hairyval > bud && score > bud:
 315                         // "Normal" not inlined case: hairy val sufficiently high
 316                         // and scoring didn't lower it.
 317                 case hairyval > bud && score <= bud:
 318                         // Promoted: we would not have inlined it before, but
 319                         // after score adjustment we decided to inline.
 320                         st = "PROMOTED"
 321                 case hairyval <= bud && score > bud:
 322                         // Demoted: we would have inlined it before, but after
 323                         // score adjustment we decided not to inline.
 324                         st = "DEMOTED"
 325                 }
 326                 if isPGO {
 327                         st += " PGO"
 328                 }
 329                 return st
 330         }
 331
 332         if base.Debug.DumpInlCallSiteScores != 0 {
 333                 sl := make([]*CallSite, 0, len(cstab))
 334                 for _, v := range cstab {
 335                         sl = append(sl, v)
 336                 }
 337                 sort.Slice(sl, func(i, j int) bool {
 338                         if sl[i].Score != sl[j].Score {
 339                                 return sl[i].Score < sl[j].Score
 340                         }
 341                         fni := ir.PkgFuncName(sl[i].Callee)
 342                         fnj := ir.PkgFuncName(sl[j].Callee)
 343                         if fni != fnj {
 344                                 return fni < fnj
 345                         }
 346                         ecsi := EncodeCallSiteKey(sl[i])
 347                         ecsj := EncodeCallSiteKey(sl[j])
 348                         return ecsi < ecsj
 349                 })
 350
 351                 mkname := func(fn *ir.Func) string {
 352                         var n string
 353                         if fn == nil || fn.Nname == nil {
 354                                 return "<nil>"
 355                         }
 356                         if fn.Sym().Pkg == types.LocalPkg {
 357                                 n = "·" + fn.Sym().Name
 358                         } else {
 359                                 n = ir.PkgFuncName(fn)
 360                         }
 361                         // don't try to print super-long names
 362                         if len(n) <= 64 {
 363                                 return n
 364                         }
 365                         return n[:32] + "..." + n[len(n)-32:len(n)]
 366                 }
 367
 368                 if len(sl) != 0 {
 369                         fmt.Fprintf(os.Stdout, "Score  Adjustment  Status  Callee  CallerPos Flags ScoreFlags\n")
 370                 }
 371                 for _, cs := range sl {
 372                         hairyval := cs.Callee.Inl.Cost
 373                         adj := int32(cs.Score) - hairyval
 374                         fmt.Fprintf(os.Stdout, "%d  %d\t%s\t%s\t%s\t%s\n",
 375                                 cs.Score, adj, genstatus(cs, profile),
 376                                 mkname(cs.Callee),
 377                                 EncodeCallSiteKey(cs),
 378                                 cs.ScoreMask.String())
 379                 }
 380         }
 381 }