src/cmd/compile/internal/inline/inlheur/score_callresult_uses.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         "fmt"
  10         "os"
  11 )
  12
  13 // This file contains code to re-score callsites based on how the
  14 // results of the call were used.  Example:
  15 //
  16 //    func foo() {
  17 //       x, fptr := bar()
  18 //       switch x {
  19 //         case 10: fptr = baz()
  20 //         default: blix()
  21 //       }
  22 //       fptr(100)
  23 //     }
  24 //
  25 // The initial scoring pass will assign a score to "bar()" based on
  26 // various criteria, however once the first pass of scoring is done,
  27 // we look at the flags on the result from bar, and check to see
  28 // how those results are used. If bar() always returns the same constant
  29 // for its first result, and if the variable receiving that result
  30 // isn't redefined, and if that variable feeds into an if/switch
  31 // condition, then we will try to adjust the score for "bar" (on the
  32 // theory that if we inlined, we can constant fold / deadcode).
  33
  34 type resultPropAndCS struct {
  35         defcs *CallSite
  36         props ResultPropBits
  37 }
  38
  39 type resultUseAnalyzer struct {
  40         resultNameTab map[*ir.Name]resultPropAndCS
  41         fn            *ir.Func
  42         cstab         CallSiteTab
  43         *condLevelTracker
  44 }
  45
  46 // rescoreBasedOnCallResultUses examines how call results are used,
  47 // and tries to update the scores of calls based on how their results
  48 // are used in the function.
  49 func rescoreBasedOnCallResultUses(fn *ir.Func, resultNameTab map[*ir.Name]resultPropAndCS, cstab CallSiteTab) {
  50         enableDebugTraceIfEnv()
  51         rua := &resultUseAnalyzer{
  52                 resultNameTab:    resultNameTab,
  53                 fn:               fn,
  54                 cstab:            cstab,
  55                 condLevelTracker: new(condLevelTracker),
  56         }
  57         var doNode func(ir.Node) bool
  58         doNode = func(n ir.Node) bool {
  59                 rua.nodeVisitPre(n)
  60                 ir.DoChildren(n, doNode)
  61                 rua.nodeVisitPost(n)
  62                 return false
  63         }
  64         doNode(fn)
  65         disableDebugTrace()
  66 }
  67
  68 func examineCallResults(cs *CallSite, resultNameTab map[*ir.Name]resultPropAndCS) {
  69         if debugTrace&debugTraceScoring != 0 {
  70                 fmt.Fprintf(os.Stderr, "=-= examining call results for %q\n",
  71                         EncodeCallSiteKey(cs))
  72         }
  73
  74         // Invoke a helper to pick out the specific ir.Name's the results
  75         // from this call are assigned into, e.g. "x, y := fooBar()". If
  76         // the call is not part of an assignment statement, or if the
  77         // variables in question are not newly defined, then we'll receive
  78         // an empty list here.
  79         //
  80         names, autoTemps, props := namesDefined(cs)
  81         if len(names) == 0 {
  82                 return
  83         }
  84
  85         if debugTrace&debugTraceScoring != 0 {
  86                 fmt.Fprintf(os.Stderr, "=-= %d names defined\n", len(names))
  87         }
  88
  89         // For each returned value, if the value has interesting
  90         // properties (ex: always returns the same constant), and the name
  91         // in question is never redefined, then make an entry in the
  92         // result table for it.
  93         const interesting = (ResultIsConcreteTypeConvertedToInterface |
  94                 ResultAlwaysSameConstant | ResultAlwaysSameInlinableFunc | ResultAlwaysSameFunc)
  95         for idx, n := range names {
  96                 rprop := props.ResultFlags[idx]
  97
  98                 if debugTrace&debugTraceScoring != 0 {
  99                         fmt.Fprintf(os.Stderr, "=-= props for ret %d %q: %s\n",
 100                                 idx, n.Sym().Name, rprop.String())
 101                 }
 102
 103                 if rprop&interesting == 0 {
 104                         continue
 105                 }
 106                 if ir.Reassigned(n) {
 107                         continue
 108                 }
 109                 if _, ok := resultNameTab[n]; ok {
 110                         panic("should never happen")
 111                 }
 112                 entry := resultPropAndCS{
 113                         defcs: cs,
 114                         props: rprop,
 115                 }
 116                 resultNameTab[n] = entry
 117                 if autoTemps[idx] != nil {
 118                         resultNameTab[autoTemps[idx]] = entry
 119                 }
 120                 if debugTrace&debugTraceScoring != 0 {
 121                         fmt.Fprintf(os.Stderr, "=-= add resultNameTab table entry n=%v autotemp=%v props=%s\n", n, autoTemps[idx], rprop.String())
 122                 }
 123         }
 124 }
 125
 126 // namesDefined returns a list of ir.Name's corresponding to locals
 127 // that receive the results from the call at site 'cs', plus the
 128 // properties object for the called function. If a given result
 129 // isn't cleanly assigned to a newly defined local, the
 130 // slot for that result in the returned list will be nil. Example:
 131 //
 132 //      call                             returned name list
 133 //
 134 //      x := foo()                       [ x ]
 135 //      z, y := bar()                    [ nil, nil ]
 136 //      _, q := baz()                    [ nil, q ]
 137 //
 138 // In the case of a multi-return call, such as "x, y := foo()",
 139 // the pattern we see from the front end will be a call op
 140 // assigning to auto-temps, and then an assignment of the auto-temps
 141 // to the user-level variables. In such cases we return
 142 // first the user-level variable (in the first func result)
 143 // and then the auto-temp name in the second result.
 144 func namesDefined(cs *CallSite) ([]*ir.Name, []*ir.Name, *FuncProps) {
 145         // If this call doesn't feed into an assignment (and of course not
 146         // all calls do), then we don't have anything to work with here.
 147         if cs.Assign == nil {
 148                 return nil, nil, nil
 149         }
 150         funcInlHeur, ok := fpmap[cs.Callee]
 151         if !ok {
 152                 // TODO: add an assert/panic here.
 153                 return nil, nil, nil
 154         }
 155         if len(funcInlHeur.props.ResultFlags) == 0 {
 156                 return nil, nil, nil
 157         }
 158
 159         // Single return case.
 160         if len(funcInlHeur.props.ResultFlags) == 1 {
 161                 asgn, ok := cs.Assign.(*ir.AssignStmt)
 162                 if !ok {
 163                         return nil, nil, nil
 164                 }
 165                 // locate name being assigned
 166                 aname, ok := asgn.X.(*ir.Name)
 167                 if !ok {
 168                         return nil, nil, nil
 169                 }
 170                 return []*ir.Name{aname}, []*ir.Name{nil}, funcInlHeur.props
 171         }
 172
 173         // Multi-return case
 174         asgn, ok := cs.Assign.(*ir.AssignListStmt)
 175         if !ok || !asgn.Def {
 176                 return nil, nil, nil
 177         }
 178         userVars := make([]*ir.Name, len(funcInlHeur.props.ResultFlags))
 179         autoTemps := make([]*ir.Name, len(funcInlHeur.props.ResultFlags))
 180         for idx, x := range asgn.Lhs {
 181                 if n, ok := x.(*ir.Name); ok {
 182                         userVars[idx] = n
 183                         r := asgn.Rhs[idx]
 184                         if r.Op() == ir.OCONVNOP {
 185                                 r = r.(*ir.ConvExpr).X
 186                         }
 187                         if ir.IsAutoTmp(r) {
 188                                 autoTemps[idx] = r.(*ir.Name)
 189                         }
 190                         if debugTrace&debugTraceScoring != 0 {
 191                                 fmt.Fprintf(os.Stderr, "=-= multi-ret namedef uv=%v at=%v\n",
 192                                         x, autoTemps[idx])
 193                         }
 194                 } else {
 195                         return nil, nil, nil
 196                 }
 197         }
 198         return userVars, autoTemps, funcInlHeur.props
 199 }
 200
 201 func (rua *resultUseAnalyzer) nodeVisitPost(n ir.Node) {
 202         rua.condLevelTracker.post(n)
 203 }
 204
 205 func (rua *resultUseAnalyzer) nodeVisitPre(n ir.Node) {
 206         rua.condLevelTracker.pre(n)
 207         switch n.Op() {
 208         case ir.OCALLINTER:
 209                 if debugTrace&debugTraceScoring != 0 {
 210                         fmt.Fprintf(os.Stderr, "=-= rescore examine iface call %v:\n", n)
 211                 }
 212                 rua.callTargetCheckResults(n)
 213         case ir.OCALLFUNC:
 214                 if debugTrace&debugTraceScoring != 0 {
 215                         fmt.Fprintf(os.Stderr, "=-= rescore examine call %v:\n", n)
 216                 }
 217                 rua.callTargetCheckResults(n)
 218         case ir.OIF:
 219                 ifst := n.(*ir.IfStmt)
 220                 rua.foldCheckResults(ifst.Cond)
 221         case ir.OSWITCH:
 222                 swst := n.(*ir.SwitchStmt)
 223                 if swst.Tag != nil {
 224                         rua.foldCheckResults(swst.Tag)
 225                 }
 226
 227         }
 228 }
 229
 230 // callTargetCheckResults examines a given call to see whether the
 231 // callee expression is potentially an inlinable function returned
 232 // from a potentially inlinable call. Examples:
 233 //
 234 //      Scenario 1: named intermediate
 235 //
 236 //         fn1 := foo()         conc := bar()
 237 //         fn1("blah")          conc.MyMethod()
 238 //
 239 //      Scenario 2: returned func or concrete object feeds directly to call
 240 //
 241 //         foo()("blah")        bar().MyMethod()
 242 //
 243 // In the second case although at the source level the result of the
 244 // direct call feeds right into the method call or indirect call,
 245 // we're relying on the front end having inserted an auto-temp to
 246 // capture the value.
 247 func (rua *resultUseAnalyzer) callTargetCheckResults(call ir.Node) {
 248         ce := call.(*ir.CallExpr)
 249         rname := rua.getCallResultName(ce)
 250         if rname == nil {
 251                 return
 252         }
 253         if debugTrace&debugTraceScoring != 0 {
 254                 fmt.Fprintf(os.Stderr, "=-= staticvalue returns %v:\n",
 255                         rname)
 256         }
 257         if rname.Class != ir.PAUTO {
 258                 return
 259         }
 260         switch call.Op() {
 261         case ir.OCALLINTER:
 262                 if debugTrace&debugTraceScoring != 0 {
 263                         fmt.Fprintf(os.Stderr, "=-= in %s checking %v for cci prop:\n",
 264                                 rua.fn.Sym().Name, rname)
 265                 }
 266                 if cs := rua.returnHasProp(rname, ResultIsConcreteTypeConvertedToInterface); cs != nil {
 267
 268                         adj := returnFeedsConcreteToInterfaceCallAdj
 269                         cs.Score, cs.ScoreMask = adjustScore(adj, cs.Score, cs.ScoreMask)
 270                 }
 271         case ir.OCALLFUNC:
 272                 if debugTrace&debugTraceScoring != 0 {
 273                         fmt.Fprintf(os.Stderr, "=-= in %s checking %v for samefunc props:\n",
 274                                 rua.fn.Sym().Name, rname)
 275                         v, ok := rua.resultNameTab[rname]
 276                         if !ok {
 277                                 fmt.Fprintf(os.Stderr, "=-= no entry for %v in rt\n", rname)
 278                         } else {
 279                                 fmt.Fprintf(os.Stderr, "=-= props for %v: %q\n", rname, v.props.String())
 280                         }
 281                 }
 282                 if cs := rua.returnHasProp(rname, ResultAlwaysSameInlinableFunc); cs != nil {
 283                         adj := returnFeedsInlinableFuncToIndCallAdj
 284                         cs.Score, cs.ScoreMask = adjustScore(adj, cs.Score, cs.ScoreMask)
 285                 } else if cs := rua.returnHasProp(rname, ResultAlwaysSameFunc); cs != nil {
 286                         adj := returnFeedsFuncToIndCallAdj
 287                         cs.Score, cs.ScoreMask = adjustScore(adj, cs.Score, cs.ScoreMask)
 288
 289                 }
 290         }
 291 }
 292
 293 // foldCheckResults examines the specified if/switch condition 'cond'
 294 // to see if it refers to locals defined by a (potentially inlinable)
 295 // function call at call site C, and if so, whether 'cond' contains
 296 // only combinations of simple references to all of the names in
 297 // 'names' with selected constants + operators. If these criteria are
 298 // met, then we adjust the score for call site C to reflect the
 299 // fact that inlining will enable deadcode and/or constant propagation.
 300 // Note: for this heuristic to kick in, the names in question have to
 301 // be all from the same callsite. Examples:
 302 //
 303 //        q, r := baz()     x, y := foo()
 304 //        switch q+r {          a, b, c := bar()
 305 //              ...                         if x && y && a && b && c {
 306 //        }                                        ...
 307 //                                          }
 308 //
 309 // For the call to "baz" above we apply a score adjustment, but not
 310 // for the calls to "foo" or "bar".
 311 func (rua *resultUseAnalyzer) foldCheckResults(cond ir.Node) {
 312         namesUsed := collectNamesUsed(cond)
 313         if len(namesUsed) == 0 {
 314                 return
 315         }
 316         var cs *CallSite
 317         for _, n := range namesUsed {
 318                 rpcs, found := rua.resultNameTab[n]
 319                 if !found {
 320                         return
 321                 }
 322                 if cs != nil && rpcs.defcs != cs {
 323                         return
 324                 }
 325                 cs = rpcs.defcs
 326                 if rpcs.props&ResultAlwaysSameConstant == 0 {
 327                         return
 328                 }
 329         }
 330         if debugTrace&debugTraceScoring != 0 {
 331                 nls := func(nl []*ir.Name) string {
 332                         r := ""
 333                         for _, n := range nl {
 334                                 r += " " + n.Sym().Name
 335                         }
 336                         return r
 337                 }
 338                 fmt.Fprintf(os.Stderr, "=-= calling ShouldFoldIfNameConstant on names={%s} cond=%v\n", nls(namesUsed), cond)
 339         }
 340
 341         if !ShouldFoldIfNameConstant(cond, namesUsed) {
 342                 return
 343         }
 344         adj := returnFeedsConstToIfAdj
 345         cs.Score, cs.ScoreMask = adjustScore(adj, cs.Score, cs.ScoreMask)
 346 }
 347
 348 func collectNamesUsed(expr ir.Node) []*ir.Name {
 349         res := []*ir.Name{}
 350         ir.Visit(expr, func(n ir.Node) {
 351                 if n.Op() != ir.ONAME {
 352                         return
 353                 }
 354                 nn := n.(*ir.Name)
 355                 if nn.Class != ir.PAUTO {
 356                         return
 357                 }
 358                 res = append(res, nn)
 359         })
 360         return res
 361 }
 362
 363 func (rua *resultUseAnalyzer) returnHasProp(name *ir.Name, prop ResultPropBits) *CallSite {
 364         v, ok := rua.resultNameTab[name]
 365         if !ok {
 366                 return nil
 367         }
 368         if v.props&prop == 0 {
 369                 return nil
 370         }
 371         return v.defcs
 372 }
 373
 374 func (rua *resultUseAnalyzer) getCallResultName(ce *ir.CallExpr) *ir.Name {
 375         var callTarg ir.Node
 376         if sel, ok := ce.Fun.(*ir.SelectorExpr); ok {
 377                 // method call
 378                 callTarg = sel.X
 379         } else if ctarg, ok := ce.Fun.(*ir.Name); ok {
 380                 // regular call
 381                 callTarg = ctarg
 382         } else {
 383                 return nil
 384         }
 385         r := ir.StaticValue(callTarg)
 386         if debugTrace&debugTraceScoring != 0 {
 387                 fmt.Fprintf(os.Stderr, "=-= staticname on %v returns %v:\n",
 388                         callTarg, r)
 389         }
 390         if r.Op() == ir.OCALLFUNC {
 391                 // This corresponds to the "x := foo()" case; here
 392                 // ir.StaticValue has brought us all the way back to
 393                 // the call expression itself. We need to back off to
 394                 // the name defined by the call; do this by looking up
 395                 // the callsite.
 396                 ce := r.(*ir.CallExpr)
 397                 cs, ok := rua.cstab[ce]
 398                 if !ok {
 399                         return nil
 400                 }
 401                 names, _, _ := namesDefined(cs)
 402                 if len(names) == 0 {
 403                         return nil
 404                 }
 405                 return names[0]
 406         } else if r.Op() == ir.ONAME {
 407                 return r.(*ir.Name)
 408         }
 409         return nil
 410 }