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         if os.Getenv("THANM_DEBUG") != "" {
  51                 return
  52         }
  53         enableDebugTraceIfEnv()
  54         rua := &resultUseAnalyzer{
  55                 resultNameTab:    resultNameTab,
  56                 fn:               fn,
  57                 cstab:            cstab,
  58                 condLevelTracker: new(condLevelTracker),
  59         }
  60         var doNode func(ir.Node) bool
  61         doNode = func(n ir.Node) bool {
  62                 rua.nodeVisitPre(n)
  63                 ir.DoChildren(n, doNode)
  64                 rua.nodeVisitPost(n)
  65                 return false
  66         }
  67         doNode(fn)
  68         disableDebugTrace()
  69 }
  70
  71 func examineCallResults(cs *CallSite, resultNameTab map[*ir.Name]resultPropAndCS) {
  72         if debugTrace&debugTraceScoring != 0 {
  73                 fmt.Fprintf(os.Stderr, "=-= examining call results for %q\n",
  74                         EncodeCallSiteKey(cs))
  75         }
  76
  77         // Invoke a helper to pick out the specific ir.Name's the results
  78         // from this call are assigned into, e.g. "x, y := fooBar()". If
  79         // the call is not part of an assignment statement, or if the
  80         // variables in question are not newly defined, then we'll receive
  81         // an empty list here.
  82         //
  83         names, autoTemps, props := namesDefined(cs)
  84         if len(names) == 0 {
  85                 return
  86         }
  87
  88         if debugTrace&debugTraceScoring != 0 {
  89                 fmt.Fprintf(os.Stderr, "=-= %d names defined\n", len(names))
  90         }
  91
  92         // For each returned value, if the value has interesting
  93         // properties (ex: always returns the same constant), and the name
  94         // in question is never redefined, then make an entry in the
  95         // result table for it.
  96         const interesting = (ResultIsConcreteTypeConvertedToInterface |
  97                 ResultAlwaysSameConstant | ResultAlwaysSameInlinableFunc | ResultAlwaysSameFunc)
  98         for idx, n := range names {
  99                 rprop := props.ResultFlags[idx]
 100
 101                 if debugTrace&debugTraceScoring != 0 {
 102                         fmt.Fprintf(os.Stderr, "=-= props for ret %d %q: %s\n",
 103                                 idx, n.Sym().Name, rprop.String())
 104                 }
 105
 106                 if rprop&interesting == 0 {
 107                         continue
 108                 }
 109                 if ir.Reassigned(n) {
 110                         continue
 111                 }
 112                 if _, ok := resultNameTab[n]; ok {
 113                         panic("should never happen")
 114                 }
 115                 entry := resultPropAndCS{
 116                         defcs: cs,
 117                         props: rprop,
 118                 }
 119                 resultNameTab[n] = entry
 120                 if autoTemps[idx] != nil {
 121                         resultNameTab[autoTemps[idx]] = entry
 122                 }
 123                 if debugTrace&debugTraceScoring != 0 {
 124                         fmt.Fprintf(os.Stderr, "=-= add resultNameTab table entry n=%v autotemp=%v props=%s\n", n, autoTemps[idx], rprop.String())
 125                 }
 126         }
 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         fih, ok := fpmap[cs.Callee]
 154         if !ok {
 155                 // TODO: add an assert/panic here.
 156                 return nil, nil, nil
 157         }
 158         if len(fih.props.ResultFlags) == 0 {
 159                 return nil, nil, nil
 160         }
 161
 162         // Single return case.
 163         if len(fih.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}, fih.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(fih.props.ResultFlags))
 182         autoTemps := make([]*ir.Name, len(fih.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, fih.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                         // FIXME: add cond level support here
 271                         adj := passConcreteToItfCallAdj
 272                         cs.Score, cs.ScoreMask = adjustScore(adj, cs.Score, cs.ScoreMask)
 273                         adj = callResultRescoreAdj
 274                         cs.Score, cs.ScoreMask = adjustScore(adj, cs.Score, cs.ScoreMask)
 275                 }
 276         case ir.OCALLFUNC:
 277                 if debugTrace&debugTraceScoring != 0 {
 278                         fmt.Fprintf(os.Stderr, "=-= in %s checking %v for samefunc props:\n",
 279                                 rua.fn.Sym().Name, rname)
 280                         v, ok := rua.resultNameTab[rname]
 281                         if !ok {
 282                                 fmt.Fprintf(os.Stderr, "=-= no entry for %v in rt\n", rname)
 283                         } else {
 284                                 fmt.Fprintf(os.Stderr, "=-= props for %v: %q\n", rname, v.props.String())
 285                         }
 286                 }
 287                 if cs := rua.returnHasProp(rname, ResultAlwaysSameInlinableFunc); cs != nil {
 288                         // FIXME: add cond level support here
 289                         adj := passInlinableFuncToIndCallAdj
 290                         cs.Score, cs.ScoreMask = adjustScore(adj, cs.Score, cs.ScoreMask)
 291                         adj = callResultRescoreAdj
 292                         cs.Score, cs.ScoreMask = adjustScore(adj, cs.Score, cs.ScoreMask)
 293                 } else if cs := rua.returnHasProp(rname, ResultAlwaysSameFunc); cs != nil {
 294                         // FIXME: add cond level support here
 295                         adj := passFuncToIndCallAdj
 296                         cs.Score, cs.ScoreMask = adjustScore(adj, cs.Score, cs.ScoreMask)
 297                         adj = callResultRescoreAdj
 298                         cs.Score, cs.ScoreMask = adjustScore(adj, cs.Score, cs.ScoreMask)
 299                 }
 300         }
 301 }
 302
 303 // foldCheckResults examines the specified if/switch condition 'cond'
 304 // to see if it refers to locals defined by a (potentially inlinable)
 305 // function call at call site C, and if so, whether 'cond' contains
 306 // only combinations of simple references to all of the names in
 307 // 'names' with selected constants + operators. If these criteria are
 308 // met, then we adjust the score for call site C to reflect the
 309 // fact that inlining will enable deadcode and/or constant propagation.
 310 // Note: for this heuristic to kick in, the names in question have to
 311 // be all from the same callsite. Examples:
 312 //
 313 //        q, r := baz()     x, y := foo()
 314 //        switch q+r {          a, b, c := bar()
 315 //              ...                         if x && y && a && b && c {
 316 //        }                                        ...
 317 //                                          }
 318 //
 319 // For the call to "baz" above we apply a score adjustment, but not
 320 // for the calls to "foo" or "bar".
 321 func (rua *resultUseAnalyzer) foldCheckResults(cond ir.Node) {
 322         namesUsed := collectNamesUsed(cond)
 323         if len(namesUsed) == 0 {
 324                 return
 325         }
 326         var cs *CallSite
 327         for _, n := range namesUsed {
 328                 rpcs, found := rua.resultNameTab[n]
 329                 if !found {
 330                         return
 331                 }
 332                 if cs != nil && rpcs.defcs != cs {
 333                         return
 334                 }
 335                 cs = rpcs.defcs
 336                 if rpcs.props&ResultAlwaysSameConstant == 0 {
 337                         return
 338                 }
 339         }
 340         if debugTrace&debugTraceScoring != 0 {
 341                 nls := func(nl []*ir.Name) string {
 342                         r := ""
 343                         for _, n := range nl {
 344                                 r += " " + n.Sym().Name
 345                         }
 346                         return r
 347                 }
 348                 fmt.Fprintf(os.Stderr, "=-= calling ShouldFoldIfNameConstant on names={%s} cond=%v\n", nls(namesUsed), cond)
 349         }
 350
 351         if !ShouldFoldIfNameConstant(cond, namesUsed) {
 352                 return
 353         }
 354         // FIXME: add cond level support here
 355         adj := passConstToIfAdj
 356         cs.Score, cs.ScoreMask = adjustScore(adj, cs.Score, cs.ScoreMask)
 357         adj = callResultRescoreAdj
 358         cs.Score, cs.ScoreMask = adjustScore(adj, cs.Score, cs.ScoreMask)
 359 }
 360
 361 func collectNamesUsed(expr ir.Node) []*ir.Name {
 362         res := []*ir.Name{}
 363         ir.Visit(expr, func(n ir.Node) {
 364                 if n.Op() != ir.ONAME {
 365                         return
 366                 }
 367                 nn := n.(*ir.Name)
 368                 if nn.Class != ir.PAUTO {
 369                         return
 370                 }
 371                 res = append(res, nn)
 372         })
 373         return res
 374 }
 375
 376 func (rua *resultUseAnalyzer) returnHasProp(name *ir.Name, prop ResultPropBits) *CallSite {
 377         v, ok := rua.resultNameTab[name]
 378         if !ok {
 379                 return nil
 380         }
 381         if v.props&prop == 0 {
 382                 return nil
 383         }
 384         return v.defcs
 385 }
 386
 387 func (rua *resultUseAnalyzer) getCallResultName(ce *ir.CallExpr) *ir.Name {
 388         var callTarg ir.Node
 389         if sel, ok := ce.X.(*ir.SelectorExpr); ok {
 390                 // method call
 391                 callTarg = sel.X
 392         } else if ctarg, ok := ce.X.(*ir.Name); ok {
 393                 // regular call
 394                 callTarg = ctarg
 395         } else {
 396                 return nil
 397         }
 398         r := ir.StaticValue(callTarg)
 399         if debugTrace&debugTraceScoring != 0 {
 400                 fmt.Fprintf(os.Stderr, "=-= staticname on %v returns %v:\n",
 401                         callTarg, r)
 402         }
 403         if r.Op() == ir.OCALLFUNC {
 404                 // This corresponds to the "x := foo()" case; here
 405                 // ir.StaticValue has brought us all the way back to
 406                 // the call expression itself. We need to back off to
 407                 // the name defined by the call; do this by looking up
 408                 // the callsite.
 409                 ce := r.(*ir.CallExpr)
 410                 cs, ok := rua.cstab[ce]
 411                 if !ok {
 412                         return nil
 413                 }
 414                 names, _, _ := namesDefined(cs)
 415                 if len(names) == 0 {
 416                         return nil
 417                 }
 418                 return names[0]
 419         } else if r.Op() == ir.ONAME {
 420                 return r.(*ir.Name)
 421         }
 422         return nil
 423 }