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  // resultsAnalyzer 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 resultsAnalyzer struct {
    19  	fname           string
    20  	props           []ResultPropBits
    21  	values          []resultVal
    22  	inlineMaxBudget int
    23  	*nameFinder
    24  }
    25  
    26  // resultVal captures information about a specific result returned from
    27  // the function we're analyzing; we are interested in cases where
    28  // the func always returns the same constant, or always returns
    29  // the same function, etc. This container stores info on a the specific
    30  // scenarios we're looking for.
    31  type resultVal struct {
    32  	cval    constant.Value
    33  	fn      *ir.Name
    34  	fnClo   bool
    35  	top     bool
    36  	derived bool // see deriveReturnFlagsFromCallee below
    37  }
    38  
    39  // addResultsAnalyzer creates a new resultsAnalyzer helper object for
    40  // the function fn, appends it to the analyzers list, and returns the
    41  // new list. If the function in question doesn't have any returns (or
    42  // any interesting returns) then the analyzer list is left as is, and
    43  // the result flags in "fp" are updated accordingly.
    44  func addResultsAnalyzer(fn *ir.Func, analyzers []propAnalyzer, fp *FuncProps, inlineMaxBudget int, nf *nameFinder) []propAnalyzer {
    45  	ra, props := makeResultsAnalyzer(fn, inlineMaxBudget, nf)
    46  	if ra != nil {
    47  		analyzers = append(analyzers, ra)
    48  	} else {
    49  		fp.ResultFlags = props
    50  	}
    51  	return analyzers
    52  }
    53  
    54  // makeResultsAnalyzer creates a new helper object to analyze results
    55  // in function fn. If the function doesn't have any interesting
    56  // results, a nil helper is returned along with a set of default
    57  // result flags for the func.
    58  func makeResultsAnalyzer(fn *ir.Func, inlineMaxBudget int, nf *nameFinder) (*resultsAnalyzer, []ResultPropBits) {
    59  	results := fn.Type().Results()
    60  	if len(results) == 0 {
    61  		return nil, nil
    62  	}
    63  	props := make([]ResultPropBits, len(results))
    64  	if fn.Inl == nil {
    65  		return nil, props
    66  	}
    67  	vals := make([]resultVal, len(results))
    68  	interestingToAnalyze := false
    69  	for i := range results {
    70  		rt := results[i].Type
    71  		if !rt.IsScalar() && !rt.HasNil() {
    72  			// existing properties not applicable here (for things
    73  			// like structs, arrays, slices, etc).
    74  			continue
    75  		}
    76  		// set the "top" flag (as in "top element of data flow lattice")
    77  		// meaning "we have no info yet, but we might later on".
    78  		vals[i].top = true
    79  		interestingToAnalyze = true
    80  	}
    81  	if !interestingToAnalyze {
    82  		return nil, props
    83  	}
    84  	ra := &resultsAnalyzer{
    85  		props:           props,
    86  		values:          vals,
    87  		inlineMaxBudget: inlineMaxBudget,
    88  		nameFinder:      nf,
    89  	}
    90  	return ra, nil
    91  }
    92  
    93  // setResults transfers the calculated result properties for this
    94  // function to 'funcProps'.
    95  func (ra *resultsAnalyzer) setResults(funcProps *FuncProps) {
    96  	// Promote ResultAlwaysSameFunc to ResultAlwaysSameInlinableFunc
    97  	for i := range ra.values {
    98  		if ra.props[i] == ResultAlwaysSameFunc && !ra.values[i].derived {
    99  			f := ra.values[i].fn.Func
   100  			// HACK: in order to allow for call site score
   101  			// adjustments, we used a relaxed inline budget in
   102  			// determining inlinability. For the check below, however,
   103  			// we want to know is whether the func in question is
   104  			// likely to be inlined, as opposed to whether it might
   105  			// possibly be inlined if all the right score adjustments
   106  			// happened, so do a simple check based on the cost.
   107  			if f.Inl != nil && f.Inl.Cost <= int32(ra.inlineMaxBudget) {
   108  				ra.props[i] = ResultAlwaysSameInlinableFunc
   109  			}
   110  		}
   111  	}
   112  	funcProps.ResultFlags = ra.props
   113  }
   114  
   115  func (ra *resultsAnalyzer) pessimize() {
   116  	for i := range ra.props {
   117  		ra.props[i] = ResultNoInfo
   118  	}
   119  }
   120  
   121  func (ra *resultsAnalyzer) nodeVisitPre(n ir.Node) {
   122  }
   123  
   124  func (ra *resultsAnalyzer) nodeVisitPost(n ir.Node) {
   125  	if len(ra.values) == 0 {
   126  		return
   127  	}
   128  	if n.Op() != ir.ORETURN {
   129  		return
   130  	}
   131  	if debugTrace&debugTraceResults != 0 {
   132  		fmt.Fprintf(os.Stderr, "=+= returns nodevis %v %s\n",
   133  			ir.Line(n), n.Op().String())
   134  	}
   135  
   136  	// No support currently for named results, so if we see an empty
   137  	// "return" stmt, be conservative.
   138  	rs := n.(*ir.ReturnStmt)
   139  	if len(rs.Results) != len(ra.values) {
   140  		ra.pessimize()
   141  		return
   142  	}
   143  	for i, r := range rs.Results {
   144  		ra.analyzeResult(i, r)
   145  	}
   146  }
   147  
   148  // analyzeResult examines the expression 'n' being returned as the
   149  // 'ii'th argument in some return statement to see whether has
   150  // interesting characteristics (for example, returns a constant), then
   151  // applies a dataflow "meet" operation to combine this result with any
   152  // previous result (for the given return slot) that we've already
   153  // processed.
   154  func (ra *resultsAnalyzer) analyzeResult(ii int, n ir.Node) {
   155  	isAllocMem := ra.isAllocatedMem(n)
   156  	isConcConvItf := ra.isConcreteConvIface(n)
   157  	constVal := ra.constValue(n)
   158  	isConst := (constVal != nil)
   159  	isNil := ra.isNil(n)
   160  	rfunc := ra.funcName(n)
   161  	isFunc := (rfunc != nil)
   162  	isClo := (rfunc != nil && rfunc.Func.OClosure != nil)
   163  	curp := ra.props[ii]
   164  	dprops, isDerivedFromCall := ra.deriveReturnFlagsFromCallee(n)
   165  	newp := ResultNoInfo
   166  	var newcval constant.Value
   167  	var newfunc *ir.Name
   168  
   169  	if debugTrace&debugTraceResults != 0 {
   170  		fmt.Fprintf(os.Stderr, "=-= %v: analyzeResult n=%s ismem=%v isconcconv=%v isconst=%v isnil=%v isfunc=%v isclo=%v\n", ir.Line(n), n.Op().String(), isAllocMem, isConcConvItf, isConst, isNil, isFunc, isClo)
   171  	}
   172  
   173  	if ra.values[ii].top {
   174  		ra.values[ii].top = false
   175  		// this is the first return we've seen; record
   176  		// whatever properties it has.
   177  		switch {
   178  		case isAllocMem:
   179  			newp = ResultIsAllocatedMem
   180  		case isConcConvItf:
   181  			newp = ResultIsConcreteTypeConvertedToInterface
   182  		case isFunc:
   183  			newp = ResultAlwaysSameFunc
   184  			newfunc = rfunc
   185  		case isConst:
   186  			newp = ResultAlwaysSameConstant
   187  			newcval = constVal
   188  		case isNil:
   189  			newp = ResultAlwaysSameConstant
   190  			newcval = nil
   191  		case isDerivedFromCall:
   192  			newp = dprops
   193  			ra.values[ii].derived = true
   194  		}
   195  	} else {
   196  		if !ra.values[ii].derived {
   197  			// this is not the first return we've seen; apply
   198  			// what amounts of a "meet" operator to combine
   199  			// the properties we see here with what we saw on
   200  			// the previous returns.
   201  			switch curp {
   202  			case ResultIsAllocatedMem:
   203  				if isAllocMem {
   204  					newp = ResultIsAllocatedMem
   205  				}
   206  			case ResultIsConcreteTypeConvertedToInterface:
   207  				if isConcConvItf {
   208  					newp = ResultIsConcreteTypeConvertedToInterface
   209  				}
   210  			case ResultAlwaysSameConstant:
   211  				if isNil && ra.values[ii].cval == nil {
   212  					newp = ResultAlwaysSameConstant
   213  					newcval = nil
   214  				} else if isConst && constant.Compare(constVal, token.EQL, ra.values[ii].cval) {
   215  					newp = ResultAlwaysSameConstant
   216  					newcval = constVal
   217  				}
   218  			case ResultAlwaysSameFunc:
   219  				if isFunc && isSameFuncName(rfunc, ra.values[ii].fn) {
   220  					newp = ResultAlwaysSameFunc
   221  					newfunc = rfunc
   222  				}
   223  			}
   224  		}
   225  	}
   226  	ra.values[ii].fn = newfunc
   227  	ra.values[ii].fnClo = isClo
   228  	ra.values[ii].cval = newcval
   229  	ra.props[ii] = newp
   230  
   231  	if debugTrace&debugTraceResults != 0 {
   232  		fmt.Fprintf(os.Stderr, "=-= %v: analyzeResult newp=%s\n",
   233  			ir.Line(n), newp)
   234  	}
   235  }
   236  
   237  // deriveReturnFlagsFromCallee tries to set properties for a given
   238  // return result where we're returning call expression; return value
   239  // is a return property value and a boolean indicating whether the
   240  // prop is valid. Examples:
   241  //
   242  //	func foo() int { return bar() }
   243  //	func bar() int { return 42 }
   244  //	func blix() int { return 43 }
   245  //	func two(y int) int {
   246  //	  if y < 0 { return bar() } else { return blix() }
   247  //	}
   248  //
   249  // Since "foo" always returns the result of a call to "bar", we can
   250  // set foo's return property to that of bar. In the case of "two", however,
   251  // even though each return path returns a constant, we don't know
   252  // whether the constants are identical, hence we need to be conservative.
   253  func (ra *resultsAnalyzer) deriveReturnFlagsFromCallee(n ir.Node) (ResultPropBits, bool) {
   254  	if n.Op() != ir.OCALLFUNC {
   255  		return 0, false
   256  	}
   257  	ce := n.(*ir.CallExpr)
   258  	if ce.Fun.Op() != ir.ONAME {
   259  		return 0, false
   260  	}
   261  	called := ir.StaticValue(ce.Fun)
   262  	if called.Op() != ir.ONAME {
   263  		return 0, false
   264  	}
   265  	cname := ra.funcName(called)
   266  	if cname == nil {
   267  		return 0, false
   268  	}
   269  	calleeProps := propsForFunc(cname.Func)
   270  	if calleeProps == nil {
   271  		return 0, false
   272  	}
   273  	if len(calleeProps.ResultFlags) != 1 {
   274  		return 0, false
   275  	}
   276  	return calleeProps.ResultFlags[0], true
   277  }
   278
View as plain text