src/cmd/compile/internal/inline/inlheur/analyze_func_returns.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         "go/constant"
  11         "go/token"
  12         "os"
  13 )
  14
  15 // returnsAnalyzer stores state information for the process of
  16 // computing flags/properties for the return values of a specific Go
  17 // function, as part of inline heuristics synthesis.
  18 type returnsAnalyzer struct {
  19         fname     string
  20         props     []ResultPropBits
  21         values    []resultVal
  22         canInline func(*ir.Func)
  23 }
  24
  25 // resultVal captures information about a specific result returned from
  26 // the function we're analyzing; we are interested in cases where
  27 // the func always returns the same constant, or always returns
  28 // the same function, etc. This container stores info on a the specific
  29 // scenarios we're looking for.
  30 type resultVal struct {
  31         lit     constant.Value
  32         fn      *ir.Name
  33         fnClo   bool
  34         top     bool
  35         derived bool // see deriveReturnFlagsFromCallee below
  36 }
  37
  38 func makeResultsAnalyzer(fn *ir.Func, canInline func(*ir.Func)) *returnsAnalyzer {
  39         results := fn.Type().Results()
  40         props := make([]ResultPropBits, len(results))
  41         vals := make([]resultVal, len(results))
  42         for i := range results {
  43                 rt := results[i].Type
  44                 if !rt.IsScalar() && !rt.HasNil() {
  45                         // existing properties not applicable here (for things
  46                         // like structs, arrays, slices, etc).
  47                         props[i] = ResultNoInfo
  48                         continue
  49                 }
  50                 // set the "top" flag (as in "top element of data flow lattice")
  51                 // meaning "we have no info yet, but we might later on".
  52                 vals[i].top = true
  53         }
  54         return &returnsAnalyzer{
  55                 props:     props,
  56                 values:    vals,
  57                 canInline: canInline,
  58         }
  59 }
  60
  61 // setResults transfers the calculated result properties for this
  62 // function to 'fp'.
  63 func (ra *returnsAnalyzer) setResults(fp *FuncProps) {
  64         // Promote ResultAlwaysSameFunc to ResultAlwaysSameInlinableFunc
  65         for i := range ra.values {
  66                 if ra.props[i] == ResultAlwaysSameFunc && !ra.values[i].derived {
  67                         f := ra.values[i].fn.Func
  68                         // If the function being returns is a closure that hasn't
  69                         // yet been checked by CanInline, invoke it now. NB: this
  70                         // is hacky, it would be better if things were structured
  71                         // so that all closures were visited ahead of time.
  72                         if ra.values[i].fnClo {
  73                                 if f != nil && !f.InlinabilityChecked() {
  74                                         ra.canInline(f)
  75                                 }
  76                         }
  77                         if f.Inl != nil {
  78                                 ra.props[i] = ResultAlwaysSameInlinableFunc
  79                         }
  80                 }
  81         }
  82         fp.ResultFlags = ra.props
  83 }
  84
  85 func (ra *returnsAnalyzer) pessimize() {
  86         for i := range ra.props {
  87                 ra.props[i] = ResultNoInfo
  88         }
  89 }
  90
  91 func (ra *returnsAnalyzer) nodeVisitPre(n ir.Node) {
  92 }
  93
  94 func (ra *returnsAnalyzer) nodeVisitPost(n ir.Node) {
  95         if len(ra.values) == 0 {
  96                 return
  97         }
  98         if n.Op() != ir.ORETURN {
  99                 return
 100         }
 101         if debugTrace&debugTraceResults != 0 {
 102                 fmt.Fprintf(os.Stderr, "=+= returns nodevis %v %s\n",
 103                         ir.Line(n), n.Op().String())
 104         }
 105
 106         // No support currently for named results, so if we see an empty
 107         // "return" stmt, be conservative.
 108         rs := n.(*ir.ReturnStmt)
 109         if len(rs.Results) != len(ra.values) {
 110                 ra.pessimize()
 111                 return
 112         }
 113         for i, r := range rs.Results {
 114                 ra.analyzeResult(i, r)
 115         }
 116 }
 117
 118 // isFuncName returns the *ir.Name for the func or method
 119 // corresponding to node 'n', along with a boolean indicating success,
 120 // and another boolean indicating whether the func is closure.
 121 func isFuncName(n ir.Node) (*ir.Name, bool, bool) {
 122         sv := ir.StaticValue(n)
 123         if sv.Op() == ir.ONAME {
 124                 name := sv.(*ir.Name)
 125                 if name.Sym() != nil && name.Class == ir.PFUNC {
 126                         return name, true, false
 127                 }
 128         }
 129         if sv.Op() == ir.OCLOSURE {
 130                 cloex := sv.(*ir.ClosureExpr)
 131                 return cloex.Func.Nname, true, true
 132         }
 133         if sv.Op() == ir.OMETHEXPR {
 134                 if mn := ir.MethodExprName(sv); mn != nil {
 135                         return mn, true, false
 136                 }
 137         }
 138         return nil, false, false
 139 }
 140
 141 // analyzeResult examines the expression 'n' being returned as the
 142 // 'ii'th argument in some return statement to see whether has
 143 // interesting characteristics (for example, returns a constant), then
 144 // applies a dataflow "meet" operation to combine this result with any
 145 // previous result (for the given return slot) that we've already
 146 // processed.
 147 func (ra *returnsAnalyzer) analyzeResult(ii int, n ir.Node) {
 148         isAllocMem := isAllocatedMem(n)
 149         isConcConvItf := isConcreteConvIface(n)
 150         lit, isConst := isLiteral(n)
 151         rfunc, isFunc, isClo := isFuncName(n)
 152         curp := ra.props[ii]
 153         dprops, isDerivedFromCall := deriveReturnFlagsFromCallee(n)
 154         newp := ResultNoInfo
 155         var newlit constant.Value
 156         var newfunc *ir.Name
 157
 158         if debugTrace&debugTraceResults != 0 {
 159                 fmt.Fprintf(os.Stderr, "=-= %v: analyzeResult n=%s ismem=%v isconcconv=%v isconst=%v isfunc=%v isclo=%v\n", ir.Line(n), n.Op().String(), isAllocMem, isConcConvItf, isConst, isFunc, isClo)
 160         }
 161
 162         if ra.values[ii].top {
 163                 ra.values[ii].top = false
 164                 // this is the first return we've seen; record
 165                 // whatever properties it has.
 166                 switch {
 167                 case isAllocMem:
 168                         newp = ResultIsAllocatedMem
 169                 case isConcConvItf:
 170                         newp = ResultIsConcreteTypeConvertedToInterface
 171                 case isFunc:
 172                         newp = ResultAlwaysSameFunc
 173                         newfunc = rfunc
 174                 case isConst:
 175                         newp = ResultAlwaysSameConstant
 176                         newlit = lit
 177                 case isDerivedFromCall:
 178                         newp = dprops
 179                         ra.values[ii].derived = true
 180                 }
 181         } else {
 182                 if !ra.values[ii].derived {
 183                         // this is not the first return we've seen; apply
 184                         // what amounts of a "meet" operator to combine
 185                         // the properties we see here with what we saw on
 186                         // the previous returns.
 187                         switch curp {
 188                         case ResultIsAllocatedMem:
 189                                 if isAllocatedMem(n) {
 190                                         newp = ResultIsAllocatedMem
 191                                 }
 192                         case ResultIsConcreteTypeConvertedToInterface:
 193                                 if isConcreteConvIface(n) {
 194                                         newp = ResultIsConcreteTypeConvertedToInterface
 195                                 }
 196                         case ResultAlwaysSameConstant:
 197                                 if isConst && isSameLiteral(lit, ra.values[ii].lit) {
 198                                         newp = ResultAlwaysSameConstant
 199                                         newlit = lit
 200                                 }
 201                         case ResultAlwaysSameFunc:
 202                                 if isFunc && isSameFuncName(rfunc, ra.values[ii].fn) {
 203                                         newp = ResultAlwaysSameFunc
 204                                         newfunc = rfunc
 205                                 }
 206                         }
 207                 }
 208         }
 209         ra.values[ii].fn = newfunc
 210         ra.values[ii].fnClo = isClo
 211         ra.values[ii].lit = newlit
 212         ra.props[ii] = newp
 213
 214         if debugTrace&debugTraceResults != 0 {
 215                 fmt.Fprintf(os.Stderr, "=-= %v: analyzeResult newp=%s\n",
 216                         ir.Line(n), newp)
 217         }
 218 }
 219
 220 func isAllocatedMem(n ir.Node) bool {
 221         sv := ir.StaticValue(n)
 222         switch sv.Op() {
 223         case ir.OMAKESLICE, ir.ONEW, ir.OPTRLIT, ir.OSLICELIT:
 224                 return true
 225         }
 226         return false
 227 }
 228
 229 // deriveReturnFlagsFromCallee tries to set properties for a given
 230 // return result where we're returning call expression; return value
 231 // is a return property value and a boolean indicating whether the
 232 // prop is valid. Examples:
 233 //
 234 //      func foo() int { return bar() }
 235 //      func bar() int { return 42 }
 236 //      func blix() int { return 43 }
 237 //      func two(y int) int {
 238 //        if y < 0 { return bar() } else { return blix() }
 239 //      }
 240 //
 241 // Since "foo" always returns the result of a call to "bar", we can
 242 // set foo's return property to that of bar. In the case of "two", however,
 243 // even though each return path returns a constant, we don't know
 244 // whether the constants are identical, hence we need to be conservative.
 245 func deriveReturnFlagsFromCallee(n ir.Node) (ResultPropBits, bool) {
 246         if n.Op() != ir.OCALLFUNC {
 247                 return 0, false
 248         }
 249         ce := n.(*ir.CallExpr)
 250         if ce.Fun.Op() != ir.ONAME {
 251                 return 0, false
 252         }
 253         called := ir.StaticValue(ce.Fun)
 254         if called.Op() != ir.ONAME {
 255                 return 0, false
 256         }
 257         cname, isFunc, _ := isFuncName(called)
 258         if !isFunc {
 259                 return 0, false
 260         }
 261         calleeProps := propsForFunc(cname.Func)
 262         if calleeProps == nil {
 263                 return 0, false
 264         }
 265         if len(calleeProps.ResultFlags) != 1 {
 266                 return 0, false
 267         }
 268         return calleeProps.ResultFlags[0], true
 269 }
 270
 271 func isLiteral(n ir.Node) (constant.Value, bool) {
 272         sv := ir.StaticValue(n)
 273         switch sv.Op() {
 274         case ir.ONIL:
 275                 return nil, true
 276         case ir.OLITERAL:
 277                 return sv.Val(), true
 278         }
 279         return nil, false
 280 }
 281
 282 // isSameLiteral checks to see if 'v1' and 'v2' correspond to the same
 283 // literal value, or if they are both nil.
 284 func isSameLiteral(v1, v2 constant.Value) bool {
 285         if v1 == nil && v2 == nil {
 286                 return true
 287         }
 288         if v1 == nil || v2 == nil {
 289                 return false
 290         }
 291         return constant.Compare(v1, token.EQL, v2)
 292 }
 293
 294 func isConcreteConvIface(n ir.Node) bool {
 295         sv := ir.StaticValue(n)
 296         if sv.Op() != ir.OCONVIFACE {
 297                 return false
 298         }
 299         return !sv.(*ir.ConvExpr).X.Type().IsInterface()
 300 }
 301
 302 func isSameFuncName(v1, v2 *ir.Name) bool {
 303         // NB: there are a few corner cases where pointer equality
 304         // doesn't work here, but this should be good enough for
 305         // our purposes here.
 306         return v1 == v2
 307 }