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/ir"
   9         "cmd/compile/internal/typecheck"
  10         "fmt"
  11         "os"
  12 )
  13
  14 // These constants enumerate the set of possible ways/scenarios
  15 // in which we'll adjust the score of a given callsite.
  16 type scoreAdjustTyp uint
  17
  18 const (
  19         panicPathAdj scoreAdjustTyp = (1 << iota)
  20         initFuncAdj
  21         inLoopAdj
  22         passConstToIfAdj
  23         passConstToNestedIfAdj
  24         passConcreteToItfCallAdj
  25         passConcreteToNestedItfCallAdj
  26         passFuncToIndCallAdj
  27         passFuncToNestedIndCallAdj
  28         passInlinableFuncToIndCallAdj
  29         passInlinableFuncToNestedIndCallAdj
  30         lastAdj scoreAdjustTyp = passInlinableFuncToNestedIndCallAdj
  31 )
  32
  33 // This table records the specific values we use to adjust call
  34 // site scores in a given scenario.
  35 // NOTE: these numbers are chosen very arbitrarily; ideally
  36 // we will go through some sort of turning process to decide
  37 // what value for each one produces the best performance.
  38
  39 var adjValues = map[scoreAdjustTyp]int{
  40         panicPathAdj:                        40,
  41         initFuncAdj:                         20,
  42         inLoopAdj:                           -5,
  43         passConstToIfAdj:                    -20,
  44         passConstToNestedIfAdj:              -15,
  45         passConcreteToItfCallAdj:            -30,
  46         passConcreteToNestedItfCallAdj:      -25,
  47         passFuncToIndCallAdj:                -25,
  48         passFuncToNestedIndCallAdj:          -20,
  49         passInlinableFuncToIndCallAdj:       -45,
  50         passInlinableFuncToNestedIndCallAdj: -40,
  51 }
  52
  53 func adjValue(x scoreAdjustTyp) int {
  54         if val, ok := adjValues[x]; ok {
  55                 return val
  56         } else {
  57                 panic("internal error unregistered adjustment type")
  58         }
  59 }
  60
  61 var mayMust = [...]struct{ may, must scoreAdjustTyp }{
  62         {may: passConstToNestedIfAdj, must: passConstToIfAdj},
  63         {may: passConcreteToNestedItfCallAdj, must: passConcreteToItfCallAdj},
  64         {may: passFuncToNestedIndCallAdj, must: passFuncToNestedIndCallAdj},
  65         {may: passInlinableFuncToNestedIndCallAdj, must: passInlinableFuncToIndCallAdj},
  66 }
  67
  68 func isMay(x scoreAdjustTyp) bool {
  69         return mayToMust(x) != 0
  70 }
  71
  72 func isMust(x scoreAdjustTyp) bool {
  73         return mustToMay(x) != 0
  74 }
  75
  76 func mayToMust(x scoreAdjustTyp) scoreAdjustTyp {
  77         for _, v := range mayMust {
  78                 if x == v.may {
  79                         return v.must
  80                 }
  81         }
  82         return 0
  83 }
  84
  85 func mustToMay(x scoreAdjustTyp) scoreAdjustTyp {
  86         for _, v := range mayMust {
  87                 if x == v.must {
  88                         return v.may
  89                 }
  90         }
  91         return 0
  92 }
  93
  94 // computeCallSiteScore takes a given call site whose ir node is 'call' and
  95 // callee function is 'callee' and with previously computed call site
  96 // properties 'csflags', then computes a score for the callsite that
  97 // combines the size cost of the callee with heuristics based on
  98 // previously parameter and function properties.
  99 func computeCallSiteScore(callee *ir.Func, calleeProps *FuncProps, call ir.Node, csflags CSPropBits) (int, scoreAdjustTyp) {
 100         // Start with the size-based score for the callee.
 101         score := int(callee.Inl.Cost)
 102         var tmask scoreAdjustTyp
 103
 104         if debugTrace&debugTraceScoring != 0 {
 105                 fmt.Fprintf(os.Stderr, "=-= scoring call to %s at %s , initial=%d\n",
 106                         callee.Sym().Name, fmtFullPos(call.Pos()), score)
 107         }
 108
 109         // First some score adjustments to discourage inlining in selected cases.
 110         if csflags&CallSiteOnPanicPath != 0 {
 111                 score, tmask = adjustScore(panicPathAdj, score, tmask)
 112         }
 113         if csflags&CallSiteInInitFunc != 0 {
 114                 score, tmask = adjustScore(initFuncAdj, score, tmask)
 115         }
 116
 117         // Then adjustments to encourage inlining in selected cases.
 118         if csflags&CallSiteInLoop != 0 {
 119                 score, tmask = adjustScore(inLoopAdj, score, tmask)
 120         }
 121
 122         // Walk through the actual expressions being passed at the call.
 123         calleeRecvrParms := callee.Type().RecvParams()
 124         ce := call.(*ir.CallExpr)
 125         for idx := range ce.Args {
 126                 // ignore blanks
 127                 if calleeRecvrParms[idx].Sym == nil ||
 128                         calleeRecvrParms[idx].Sym.IsBlank() {
 129                         continue
 130                 }
 131                 arg := ce.Args[idx]
 132                 pflag := calleeProps.ParamFlags[idx]
 133                 if debugTrace&debugTraceScoring != 0 {
 134                         fmt.Fprintf(os.Stderr, "=-= arg %d of %d: val %v flags=%s\n",
 135                                 idx, len(ce.Args), arg, pflag.String())
 136                 }
 137                 _, islit := isLiteral(arg)
 138                 iscci := isConcreteConvIface(arg)
 139                 fname, isfunc, _ := isFuncName(arg)
 140                 if debugTrace&debugTraceScoring != 0 {
 141                         fmt.Fprintf(os.Stderr, "=-= isLit=%v iscci=%v isfunc=%v for arg %v\n", islit, iscci, isfunc, arg)
 142                 }
 143
 144                 if islit {
 145                         if pflag&ParamMayFeedIfOrSwitch != 0 {
 146                                 score, tmask = adjustScore(passConstToNestedIfAdj, score, tmask)
 147                         }
 148                         if pflag&ParamFeedsIfOrSwitch != 0 {
 149                                 score, tmask = adjustScore(passConstToIfAdj, score, tmask)
 150                         }
 151                 }
 152
 153                 if iscci {
 154                         // FIXME: ideally here it would be nice to make a
 155                         // distinction between the inlinable case and the
 156                         // non-inlinable case, but this is hard to do. Example:
 157                         //
 158                         //    type I interface { Tiny() int; Giant() }
 159                         //    type Conc struct { x int }
 160                         //    func (c *Conc) Tiny() int { return 42 }
 161                         //    func (c *Conc) Giant() { <huge amounts of code> }
 162                         //
 163                         //    func passConcToItf(c *Conc) {
 164                         //        makesItfMethodCall(c)
 165                         //    }
 166                         //
 167                         // In the code above, function properties will only tell
 168                         // us that 'makesItfMethodCall' invokes a method on its
 169                         // interface parameter, but we don't know whether it calls
 170                         // "Tiny" or "Giant". If we knew if called "Tiny", then in
 171                         // theory in addition to converting the interface call to
 172                         // a direct call, we could also inline (in which case
 173                         // we'd want to decrease the score even more).
 174                         //
 175                         // One thing we could do (not yet implemented) is iterate
 176                         // through all of the methods of "*Conc" that allow it to
 177                         // satisfy I, and if all are inlinable, then exploit that.
 178                         if pflag&ParamMayFeedInterfaceMethodCall != 0 {
 179                                 score, tmask = adjustScore(passConcreteToNestedItfCallAdj, score, tmask)
 180                         }
 181                         if pflag&ParamFeedsInterfaceMethodCall != 0 {
 182                                 score, tmask = adjustScore(passConcreteToItfCallAdj, score, tmask)
 183                         }
 184                 }
 185
 186                 if isfunc {
 187                         mayadj := passFuncToNestedIndCallAdj
 188                         mustadj := passFuncToIndCallAdj
 189                         if fn := fname.Func; fn != nil && typecheck.HaveInlineBody(fn) {
 190                                 mayadj = passInlinableFuncToNestedIndCallAdj
 191                                 mustadj = passInlinableFuncToIndCallAdj
 192                         }
 193                         if pflag&ParamMayFeedIndirectCall != 0 {
 194                                 score, tmask = adjustScore(mayadj, score, tmask)
 195                         }
 196                         if pflag&ParamFeedsIndirectCall != 0 {
 197                                 score, tmask = adjustScore(mustadj, score, tmask)
 198                         }
 199                 }
 200         }
 201
 202         return score, tmask
 203 }
 204
 205 func adjustScore(typ scoreAdjustTyp, score int, mask scoreAdjustTyp) (int, scoreAdjustTyp) {
 206
 207         if isMust(typ) {
 208                 if mask&typ != 0 {
 209                         return score, mask
 210                 }
 211                 may := mustToMay(typ)
 212                 if mask&may != 0 {
 213                         // promote may to must, so undo may
 214                         score -= adjValue(may)
 215                         mask &^= may
 216                 }
 217         } else if isMay(typ) {
 218                 must := mayToMust(typ)
 219                 if mask&(must|typ) != 0 {
 220                         return score, mask
 221                 }
 222         }
 223         if mask&typ == 0 {
 224                 if debugTrace&debugTraceScoring != 0 {
 225                         fmt.Fprintf(os.Stderr, "=-= applying adj %d for %s\n",
 226                                 adjValue(typ), typ.String())
 227                 }
 228                 score += adjValue(typ)
 229                 mask |= typ
 230         }
 231         return score, mask
 232 }