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) 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 resultNameTab
  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 resultNameTab == nil {
 110                         resultNameTab = make(map[*ir.Name]resultPropAndCS)
 111                 } else if _, ok := resultNameTab[n]; ok {
 112                         panic("should never happen")
 113                 }
 114                 entry := resultPropAndCS{
 115                         defcs: cs,
 116                         props: rprop,
 117                 }
 118                 resultNameTab[n] = entry
 119                 if autoTemps[idx] != nil {
 120                         resultNameTab[autoTemps[idx]] = entry
 121                 }
 122                 if debugTrace&debugTraceScoring != 0 {
 123                         fmt.Fprintf(os.Stderr, "=-= add resultNameTab table entry n=%v autotemp=%v props=%s\n", n, autoTemps[idx], rprop.String())
 124                 }
 125         }
 126         return resultNameTab
 127 }
 128
 129 // namesDefined returns a list of ir.Name's corresponding to locals
 130 // that receive the results from the call at site 'cs', plus the
 131 // properties object for the called function. If a given result
 132 // isn't cleanly assigned to a newly defined local, the
 133 // slot for that result in the returned list will be nil. Example:
 134 //
 135 //      call                             returned name list
 136 //
 137 //      x := foo()                       [ x ]
 138 //      z, y := bar()                    [ nil, nil ]
 139 //      _, q := baz()                    [ nil, q ]
 140 //
 141 // In the case of a multi-return call, such as "x, y := foo()",
 142 // the pattern we see from the front end will be a call op
 143 // assigning to auto-temps, and then an assignment of the auto-temps
 144 // to the user-level variables. In such cases we return
 145 // first the user-level variable (in the first func result)
 146 // and then the auto-temp name in the second result.
 147 func namesDefined(cs *CallSite) ([]*ir.Name, []*ir.Name, *FuncProps) {
 148         // If this call doesn't feed into an assignment (and of course not
 149         // all calls do), then we don't have anything to work with here.
 150         if cs.Assign == nil {
 151                 return nil, nil, nil
 152         }
 153         funcInlHeur, ok := fpmap[cs.Callee]
 154         if !ok {
 155                 // TODO: add an assert/panic here.
 156                 return nil, nil, nil
 157         }
 158         if len(funcInlHeur.props.ResultFlags) == 0 {
 159                 return nil, nil, nil
 160         }
 161
 162         // Single return case.
 163         if len(funcInlHeur.props.ResultFlags) == 1 {
 164                 asgn, ok := cs.Assign.(*ir.AssignStmt)
 165                 if !ok {
 166                         return nil, nil, nil
 167                 }
 168                 // locate name being assigned
 169                 aname, ok := asgn.X.(*ir.Name)
 170                 if !ok {
 171                         return nil, nil, nil
 172                 }
 173                 return []*ir.Name{aname}, []*ir.Name{nil}, funcInlHeur.props
 174         }
 175
 176         // Multi-return case
 177         asgn, ok := cs.Assign.(*ir.AssignListStmt)
 178         if !ok || !asgn.Def {
 179                 return nil, nil, nil
 180         }
 181         userVars := make([]*ir.Name, len(funcInlHeur.props.ResultFlags))
 182         autoTemps := make([]*ir.Name, len(funcInlHeur.props.ResultFlags))
 183         for idx, x := range asgn.Lhs {
 184                 if n, ok := x.(*ir.Name); ok {
 185                         userVars[idx] = n
 186                         r := asgn.Rhs[idx]
 187                         if r.Op() == ir.OCONVNOP {
 188                                 r = r.(*ir.ConvExpr).X
 189                         }
 190                         if ir.IsAutoTmp(r) {
 191                                 autoTemps[idx] = r.(*ir.Name)
 192                         }
 193                         if debugTrace&debugTraceScoring != 0 {
 194                                 fmt.Fprintf(os.Stderr, "=-= multi-ret namedef uv=%v at=%v\n",
 195                                         x, autoTemps[idx])
 196                         }
 197                 } else {
 198                         return nil, nil, nil
 199                 }
 200         }
 201         return userVars, autoTemps, funcInlHeur.props
 202 }
 203
 204 func (rua *resultUseAnalyzer) nodeVisitPost(n ir.Node) {
 205         rua.condLevelTracker.post(n)
 206 }
 207
 208 func (rua *resultUseAnalyzer) nodeVisitPre(n ir.Node) {
 209         rua.condLevelTracker.pre(n)
 210         switch n.Op() {
 211         case ir.OCALLINTER:
 212                 if debugTrace&debugTraceScoring != 0 {
 213                         fmt.Fprintf(os.Stderr, "=-= rescore examine iface call %v:\n", n)
 214                 }
 215                 rua.callTargetCheckResults(n)
 216         case ir.OCALLFUNC:
 217                 if debugTrace&debugTraceScoring != 0 {
 218                         fmt.Fprintf(os.Stderr, "=-= rescore examine call %v:\n", n)
 219                 }
 220                 rua.callTargetCheckResults(n)
 221         case ir.OIF:
 222                 ifst := n.(*ir.IfStmt)
 223                 rua.foldCheckResults(ifst.Cond)
 224         case ir.OSWITCH:
 225                 swst := n.(*ir.SwitchStmt)
 226                 if swst.Tag != nil {
 227                         rua.foldCheckResults(swst.Tag)
 228                 }
 229
 230         }
 231 }
 232
 233 // callTargetCheckResults examines a given call to see whether the
 234 // callee expression is potentially an inlinable function returned
 235 // from a potentially inlinable call. Examples:
 236 //
 237 //      Scenario 1: named intermediate
 238 //
 239 //         fn1 := foo()         conc := bar()
 240 //         fn1("blah")          conc.MyMethod()
 241 //
 242 //      Scenario 2: returned func or concrete object feeds directly to call
 243 //
 244 //         foo()("blah")        bar().MyMethod()
 245 //
 246 // In the second case although at the source level the result of the
 247 // direct call feeds right into the method call or indirect call,
 248 // we're relying on the front end having inserted an auto-temp to
 249 // capture the value.
 250 func (rua *resultUseAnalyzer) callTargetCheckResults(call ir.Node) {
 251         ce := call.(*ir.CallExpr)
 252         rname := rua.getCallResultName(ce)
 253         if rname == nil {
 254                 return
 255         }
 256         if debugTrace&debugTraceScoring != 0 {
 257                 fmt.Fprintf(os.Stderr, "=-= staticvalue returns %v:\n",
 258                         rname)
 259         }
 260         if rname.Class != ir.PAUTO {
 261                 return
 262         }
 263         switch call.Op() {
 264         case ir.OCALLINTER:
 265                 if debugTrace&debugTraceScoring != 0 {
 266                         fmt.Fprintf(os.Stderr, "=-= in %s checking %v for cci prop:\n",
 267                                 rua.fn.Sym().Name, rname)
 268                 }
 269                 if cs := rua.returnHasProp(rname, ResultIsConcreteTypeConvertedToInterface); cs != nil {
 270
 271                         adj := returnFeedsConcreteToInterfaceCallAdj
 272                         cs.Score, cs.ScoreMask = adjustScore(adj, cs.Score, cs.ScoreMask)
 273                 }
 274         case ir.OCALLFUNC:
 275                 if debugTrace&debugTraceScoring != 0 {
 276                         fmt.Fprintf(os.Stderr, "=-= in %s checking %v for samefunc props:\n",
 277                                 rua.fn.Sym().Name, rname)
 278                         v, ok := rua.resultNameTab[rname]
 279                         if !ok {
 280                                 fmt.Fprintf(os.Stderr, "=-= no entry for %v in rt\n", rname)
 281                         } else {
 282                                 fmt.Fprintf(os.Stderr, "=-= props for %v: %q\n", rname, v.props.String())
 283                         }
 284                 }
 285                 if cs := rua.returnHasProp(rname, ResultAlwaysSameInlinableFunc); cs != nil {
 286                         adj := returnFeedsInlinableFuncToIndCallAdj
 287                         cs.Score, cs.ScoreMask = adjustScore(adj, cs.Score, cs.ScoreMask)
 288                 } else if cs := rua.returnHasProp(rname, ResultAlwaysSameFunc); cs != nil {
 289                         adj := returnFeedsFuncToIndCallAdj
 290                         cs.Score, cs.ScoreMask = adjustScore(adj, cs.Score, cs.ScoreMask)
 291
 292                 }
 293         }
 294 }
 295
 296 // foldCheckResults examines the specified if/switch condition 'cond'
 297 // to see if it refers to locals defined by a (potentially inlinable)
 298 // function call at call site C, and if so, whether 'cond' contains
 299 // only combinations of simple references to all of the names in
 300 // 'names' with selected constants + operators. If these criteria are
 301 // met, then we adjust the score for call site C to reflect the
 302 // fact that inlining will enable deadcode and/or constant propagation.
 303 // Note: for this heuristic to kick in, the names in question have to
 304 // be all from the same callsite. Examples:
 305 //
 306 //        q, r := baz()     x, y := foo()
 307 //        switch q+r {          a, b, c := bar()
 308 //              ...                         if x && y && a && b && c {
 309 //        }                                        ...
 310 //                                          }
 311 //
 312 // For the call to "baz" above we apply a score adjustment, but not
 313 // for the calls to "foo" or "bar".
 314 func (rua *resultUseAnalyzer) foldCheckResults(cond ir.Node) {
 315         namesUsed := collectNamesUsed(cond)
 316         if len(namesUsed) == 0 {
 317                 return
 318         }
 319         var cs *CallSite
 320         for _, n := range namesUsed {
 321                 rpcs, found := rua.resultNameTab[n]
 322                 if !found {
 323                         return
 324                 }
 325                 if cs != nil && rpcs.defcs != cs {
 326                         return
 327                 }
 328                 cs = rpcs.defcs
 329                 if rpcs.props&ResultAlwaysSameConstant == 0 {
 330                         return
 331                 }
 332         }
 333         if debugTrace&debugTraceScoring != 0 {
 334                 nls := func(nl []*ir.Name) string {
 335                         r := ""
 336                         for _, n := range nl {
 337                                 r += " " + n.Sym().Name
 338                         }
 339                         return r
 340                 }
 341                 fmt.Fprintf(os.Stderr, "=-= calling ShouldFoldIfNameConstant on names={%s} cond=%v\n", nls(namesUsed), cond)
 342         }
 343
 344         if !ShouldFoldIfNameConstant(cond, namesUsed) {
 345                 return
 346         }
 347         adj := returnFeedsConstToIfAdj
 348         cs.Score, cs.ScoreMask = adjustScore(adj, cs.Score, cs.ScoreMask)
 349 }
 350
 351 func collectNamesUsed(expr ir.Node) []*ir.Name {
 352         res := []*ir.Name{}
 353         ir.Visit(expr, func(n ir.Node) {
 354                 if n.Op() != ir.ONAME {
 355                         return
 356                 }
 357                 nn := n.(*ir.Name)
 358                 if nn.Class != ir.PAUTO {
 359                         return
 360                 }
 361                 res = append(res, nn)
 362         })
 363         return res
 364 }
 365
 366 func (rua *resultUseAnalyzer) returnHasProp(name *ir.Name, prop ResultPropBits) *CallSite {
 367         v, ok := rua.resultNameTab[name]
 368         if !ok {
 369                 return nil
 370         }
 371         if v.props&prop == 0 {
 372                 return nil
 373         }
 374         return v.defcs
 375 }
 376
 377 func (rua *resultUseAnalyzer) getCallResultName(ce *ir.CallExpr) *ir.Name {
 378         var callTarg ir.Node
 379         if sel, ok := ce.Fun.(*ir.SelectorExpr); ok {
 380                 // method call
 381                 callTarg = sel.X
 382         } else if ctarg, ok := ce.Fun.(*ir.Name); ok {
 383                 // regular call
 384                 callTarg = ctarg
 385         } else {
 386                 return nil
 387         }
 388         r := ir.StaticValue(callTarg)
 389         if debugTrace&debugTraceScoring != 0 {
 390                 fmt.Fprintf(os.Stderr, "=-= staticname on %v returns %v:\n",
 391                         callTarg, r)
 392         }
 393         if r.Op() == ir.OCALLFUNC {
 394                 // This corresponds to the "x := foo()" case; here
 395                 // ir.StaticValue has brought us all the way back to
 396                 // the call expression itself. We need to back off to
 397                 // the name defined by the call; do this by looking up
 398                 // the callsite.
 399                 ce := r.(*ir.CallExpr)
 400                 cs, ok := rua.cstab[ce]
 401                 if !ok {
 402                         return nil
 403                 }
 404                 names, _, _ := namesDefined(cs)
 405                 if len(names) == 0 {
 406                         return nil
 407                 }
 408                 return names[0]
 409         } else if r.Op() == ir.ONAME {
 410                 return r.(*ir.Name)
 411         }
 412         return nil
 413 }