| // 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 := ¶msAnalyzer{ |
| 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-- |
| } |
| } |