xref: /aosp_15_r20/prebuilts/go/linux-x86/src/cmd/compile/internal/inline/inlheur/analyze_func_params.go

// Copyright 2023 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package inlheur

import (
	"cmd/compile/internal/ir"
	"fmt"
	"os"
)

// paramsAnalyzer holds state information for the phase that computes
// flags for a Go functions parameters, for use in inline heuristics.
// Note that the params slice below includes entries for blanks.
type paramsAnalyzer struct {
	fname  string
	values []ParamPropBits
	params []*ir.Name
	top    []bool
	*condLevelTracker
	*nameFinder
}

// getParams returns an *ir.Name slice containing all params for the
// function (plus rcvr as well if applicable).
func getParams(fn *ir.Func) []*ir.Name {
	sig := fn.Type()
	numParams := sig.NumRecvs() + sig.NumParams()
	return fn.Dcl[:numParams]
}

// addParamsAnalyzer creates a new paramsAnalyzer helper object for
// the function fn, appends it to the analyzers list, and returns the
// new list. If the function in question doesn't have any interesting
// parameters then the analyzer list is returned unchanged, and the
// params flags in "fp" are updated accordingly.
func addParamsAnalyzer(fn *ir.Func, analyzers []propAnalyzer, fp *FuncProps, nf *nameFinder) []propAnalyzer {
	pa, props := makeParamsAnalyzer(fn, nf)
	if pa != nil {
		analyzers = append(analyzers, pa)
	} else {
		fp.ParamFlags = props
	}
	return analyzers
}

// makeParamsAnalyzer creates a new helper object to analyze parameters
// of function fn. If the function doesn't have any interesting
// params, a nil helper is returned along with a set of default param
// flags for the func.
func makeParamsAnalyzer(fn *ir.Func, nf *nameFinder) (*paramsAnalyzer, []ParamPropBits) {
	params := getParams(fn) // includes receiver if applicable
	if len(params) == 0 {
		return nil, nil
	}
	vals := make([]ParamPropBits, len(params))
	if fn.Inl == nil {
		return nil, vals
	}
	top := make([]bool, len(params))
	interestingToAnalyze := false
	for i, pn := range params {
		if pn == nil {
			continue
		}
		pt := pn.Type()
		if !pt.IsScalar() && !pt.HasNil() {
			// existing properties not applicable here (for things
			// like structs, arrays, slices, etc).
			continue
		}
		// If param is reassigned, skip it.
		if ir.Reassigned(pn) {
			continue
		}
		top[i] = true
		interestingToAnalyze = true
	}
	if !interestingToAnalyze {
		return nil, vals
	}

	if debugTrace&debugTraceParams != 0 {
		fmt.Fprintf(os.Stderr, "=-= param analysis of func %v:\n",
			fn.Sym().Name)
		for i := range vals {
			n := "_"
			if params[i] != nil {
				n = params[i].Sym().String()
			}
			fmt.Fprintf(os.Stderr, "=-=  %d: %q %s top=%v\n",
				i, n, vals[i].String(), top[i])
		}
	}
	pa := &paramsAnalyzer{
		fname:            fn.Sym().Name,
		values:           vals,
		params:           params,
		top:              top,
		condLevelTracker: new(condLevelTracker),
		nameFinder:       nf,
	}
	return pa, nil
}

func (pa *paramsAnalyzer) setResults(funcProps *FuncProps) {
	funcProps.ParamFlags = pa.values
}

func (pa *paramsAnalyzer) findParamIdx(n *ir.Name) int {
	if n == nil {
		panic("bad")
	}
	for i := range pa.params {
		if pa.params[i] == n {
			return i
		}
	}
	return -1
}

type testfType func(x ir.Node, param *ir.Name, idx int) (bool, bool)

// paramsAnalyzer invokes function 'testf' on the specified expression
// 'x' for each parameter, and if the result is TRUE, or's 'flag' into
// the flags for that param.
func (pa *paramsAnalyzer) checkParams(x ir.Node, flag ParamPropBits, mayflag ParamPropBits, testf testfType) {
	for idx, p := range pa.params {
		if !pa.top[idx] && pa.values[idx] == ParamNoInfo {
			continue
		}
		result, may := testf(x, p, idx)
		if debugTrace&debugTraceParams != 0 {
			fmt.Fprintf(os.Stderr, "=-= test expr %v param %s result=%v flag=%s\n", x, p.Sym().Name, result, flag.String())
		}
		if result {
			v := flag
			if pa.condLevel != 0 || may {
				v = mayflag
			}
			pa.values[idx] |= v
			pa.top[idx] = false
		}
	}
}

// foldCheckParams checks expression 'x' (an 'if' condition or
// 'switch' stmt expr) to see if the expr would fold away if a
// specific parameter had a constant value.
func (pa *paramsAnalyzer) foldCheckParams(x ir.Node) {
	pa.checkParams(x, ParamFeedsIfOrSwitch, ParamMayFeedIfOrSwitch,
		func(x ir.Node, p *ir.Name, idx int) (bool, bool) {
			return ShouldFoldIfNameConstant(x, []*ir.Name{p}), false
		})
}

// callCheckParams examines the target of call expression 'ce' to see
// if it is making a call to the value passed in for some parameter.
func (pa *paramsAnalyzer) callCheckParams(ce *ir.CallExpr) {
	switch ce.Op() {
	case ir.OCALLINTER:
		if ce.Op() != ir.OCALLINTER {
			return
		}
		sel := ce.Fun.(*ir.SelectorExpr)
		r := pa.staticValue(sel.X)
		if r.Op() != ir.ONAME {
			return
		}
		name := r.(*ir.Name)
		if name.Class != ir.PPARAM {
			return
		}
		pa.checkParams(r, ParamFeedsInterfaceMethodCall,
			ParamMayFeedInterfaceMethodCall,
			func(x ir.Node, p *ir.Name, idx int) (bool, bool) {
				name := x.(*ir.Name)
				return name == p, false
			})
	case ir.OCALLFUNC:
		if ce.Fun.Op() != ir.ONAME {
			return
		}
		called := ir.StaticValue(ce.Fun)
		if called.Op() != ir.ONAME {
			return
		}
		name := called.(*ir.Name)
		if name.Class == ir.PPARAM {
			pa.checkParams(called, ParamFeedsIndirectCall,
				ParamMayFeedIndirectCall,
				func(x ir.Node, p *ir.Name, idx int) (bool, bool) {
					name := x.(*ir.Name)
					return name == p, false
				})
		} else {
			cname := pa.funcName(called)
			if cname != nil {
				pa.deriveFlagsFromCallee(ce, cname.Func)
			}
		}
	}
}

// deriveFlagsFromCallee tries to derive flags for the current
// function based on a call this function makes to some other
// function. Example:
//
//	/* Simple */                /* Derived from callee */
//	func foo(f func(int)) {     func foo(f func(int)) {
//	  f(2)                        bar(32, f)
//	}                           }
//	                            func bar(x int, f func()) {
//	                              f(x)
//	                            }
//
// Here we can set the "param feeds indirect call" flag for
// foo's param 'f' since we know that bar has that flag set for
// its second param, and we're passing that param a function.
func (pa *paramsAnalyzer) deriveFlagsFromCallee(ce *ir.CallExpr, callee *ir.Func) {
	calleeProps := propsForFunc(callee)
	if calleeProps == nil {
		return
	}
	if debugTrace&debugTraceParams != 0 {
		fmt.Fprintf(os.Stderr, "=-= callee props for %v:\n%s",
			callee.Sym().Name, calleeProps.String())
	}

	must := []ParamPropBits{ParamFeedsInterfaceMethodCall, ParamFeedsIndirectCall, ParamFeedsIfOrSwitch}
	may := []ParamPropBits{ParamMayFeedInterfaceMethodCall, ParamMayFeedIndirectCall, ParamMayFeedIfOrSwitch}

	for pidx, arg := range ce.Args {
		// Does the callee param have any interesting properties?
		// If not we can skip this one.
		pflag := calleeProps.ParamFlags[pidx]
		if pflag == 0 {
			continue
		}
		// See if one of the caller's parameters is flowing unmodified
		// into this actual expression.
		r := pa.staticValue(arg)
		if r.Op() != ir.ONAME {
			return
		}
		name := r.(*ir.Name)
		if name.Class != ir.PPARAM {
			return
		}
		callerParamIdx := pa.findParamIdx(name)
		// note that callerParamIdx may return -1 in the case where
		// the param belongs not to the current closure func we're
		// analyzing but to an outer enclosing func.
		if callerParamIdx == -1 {
			return
		}
		if pa.params[callerParamIdx] == nil {
			panic("something went wrong")
		}
		if !pa.top[callerParamIdx] &&
			pa.values[callerParamIdx] == ParamNoInfo {
			continue
		}
		if debugTrace&debugTraceParams != 0 {
			fmt.Fprintf(os.Stderr, "=-= pflag for arg %d is %s\n",
				pidx, pflag.String())
		}
		for i := range must {
			mayv := may[i]
			mustv := must[i]
			if pflag&mustv != 0 && pa.condLevel == 0 {
				pa.values[callerParamIdx] |= mustv
			} else if pflag&(mustv|mayv) != 0 {
				pa.values[callerParamIdx] |= mayv
			}
		}
		pa.top[callerParamIdx] = false
	}
}

func (pa *paramsAnalyzer) nodeVisitPost(n ir.Node) {
	if len(pa.values) == 0 {
		return
	}
	pa.condLevelTracker.post(n)
	switch n.Op() {
	case ir.OCALLFUNC:
		ce := n.(*ir.CallExpr)
		pa.callCheckParams(ce)
	case ir.OCALLINTER:
		ce := n.(*ir.CallExpr)
		pa.callCheckParams(ce)
	case ir.OIF:
		ifst := n.(*ir.IfStmt)
		pa.foldCheckParams(ifst.Cond)
	case ir.OSWITCH:
		swst := n.(*ir.SwitchStmt)
		if swst.Tag != nil {
			pa.foldCheckParams(swst.Tag)
		}
	}
}

func (pa *paramsAnalyzer) nodeVisitPre(n ir.Node) {
	if len(pa.values) == 0 {
		return
	}
	pa.condLevelTracker.pre(n)
}

// condLevelTracker helps keeps track very roughly of "level of conditional
// nesting", e.g. how many "if" statements you have to go through to
// get to the point where a given stmt executes. Example:
//
//	                      cond nesting level
//	func foo() {
//	 G = 1                   0
//	 if x < 10 {             0
//	  if y < 10 {            1
//	   G = 0                 2
//	  }
//	 }
//	}
//
// The intent here is to provide some sort of very abstract relative
// hotness metric, e.g. "G = 1" above is expected to be executed more
// often than "G = 0" (in the aggregate, across large numbers of
// functions).
type condLevelTracker struct {
	condLevel int
}

func (c *condLevelTracker) pre(n ir.Node) {
	// Increment level of "conditional testing" if we see
	// an "if" or switch statement, and decrement if in
	// a loop.
	switch n.Op() {
	case ir.OIF, ir.OSWITCH:
		c.condLevel++
	case ir.OFOR, ir.ORANGE:
		c.condLevel--
	}
}

func (c *condLevelTracker) post(n ir.Node) {
	switch n.Op() {
	case ir.OFOR, ir.ORANGE:
		c.condLevel++
	case ir.OIF:
		c.condLevel--
	case ir.OSWITCH:
		c.condLevel--
	}
}