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.
8 "cmd/compile/internal/base"
9 "cmd/compile/internal/ir"
10 "cmd/compile/internal/pgo"
11 "cmd/compile/internal/typecheck"
12 "cmd/compile/internal/types"
18 // These constants enumerate the set of possible ways/scenarios
19 // in which we'll adjust the score of a given callsite.
20 type scoreAdjustTyp uint
22 // These constants capture the various ways in which the inliner's
23 // scoring phase can adjust a callsite score based on heuristics. They
24 // fall broadly into three categories:
26 // 1) adjustments based solely on the callsite context (ex: call
27 // appears on panic path)
29 // 2) adjustments that take into account specific interesting values
30 // passed at a call site (ex: passing a constant that could result in
31 // cprop/deadcode in the caller)
33 // 3) adjustments that take into account values returned from the call
34 // at a callsite (ex: call always returns the same inlinable function,
35 // and return value flows unmodified into an indirect call)
37 // For categories 2 and 3 above, each adjustment can have either a
38 // "must" version and a "may" version (but not both). Here the idea is
39 // that in the "must" version the value flow is unconditional: if the
40 // callsite executes, then the condition we're interested in (ex:
41 // param feeding call) is guaranteed to happen. For the "may" version,
42 // there may be control flow that could cause the benefit to be
45 // Catgegory 1 adjustments (see above)
46 panicPathAdj scoreAdjustTyp = (1 << iota)
50 // Category 2 adjustments (see above).
52 passConstToNestedIfAdj
53 passConcreteToItfCallAdj
54 passConcreteToNestedItfCallAdj
56 passFuncToNestedIndCallAdj
57 passInlinableFuncToIndCallAdj
58 passInlinableFuncToNestedIndCallAdj
60 // Category 3 adjustments.
61 returnFeedsConstToIfAdj
62 returnFeedsFuncToIndCallAdj
63 returnFeedsInlinableFuncToIndCallAdj
64 returnFeedsConcreteToInterfaceCallAdj
67 // This table records the specific values we use to adjust call
68 // site scores in a given scenario.
69 // NOTE: these numbers are chosen very arbitrarily; ideally
70 // we will go through some sort of turning process to decide
71 // what value for each one produces the best performance.
73 var adjValues = map[scoreAdjustTyp]int{
77 passConstToIfAdj: -20,
78 passConstToNestedIfAdj: -15,
79 passConcreteToItfCallAdj: -30,
80 passConcreteToNestedItfCallAdj: -25,
81 passFuncToIndCallAdj: -25,
82 passFuncToNestedIndCallAdj: -20,
83 passInlinableFuncToIndCallAdj: -45,
84 passInlinableFuncToNestedIndCallAdj: -40,
85 returnFeedsConstToIfAdj: -15,
86 returnFeedsFuncToIndCallAdj: -25,
87 returnFeedsInlinableFuncToIndCallAdj: -40,
88 returnFeedsConcreteToInterfaceCallAdj: -25,
91 func adjValue(x scoreAdjustTyp) int {
92 if val, ok := adjValues[x]; ok {
95 panic("internal error unregistered adjustment type")
99 var mayMust = [...]struct{ may, must scoreAdjustTyp }{
100 {may: passConstToNestedIfAdj, must: passConstToIfAdj},
101 {may: passConcreteToNestedItfCallAdj, must: passConcreteToItfCallAdj},
102 {may: passFuncToNestedIndCallAdj, must: passFuncToNestedIndCallAdj},
103 {may: passInlinableFuncToNestedIndCallAdj, must: passInlinableFuncToIndCallAdj},
106 func isMay(x scoreAdjustTyp) bool {
107 return mayToMust(x) != 0
110 func isMust(x scoreAdjustTyp) bool {
111 return mustToMay(x) != 0
114 func mayToMust(x scoreAdjustTyp) scoreAdjustTyp {
115 for _, v := range mayMust {
123 func mustToMay(x scoreAdjustTyp) scoreAdjustTyp {
124 for _, v := range mayMust {
132 // computeCallSiteScore takes a given call site whose ir node is 'call' and
133 // callee function is 'callee' and with previously computed call site
134 // properties 'csflags', then computes a score for the callsite that
135 // combines the size cost of the callee with heuristics based on
136 // previously parameter and function properties.
137 func computeCallSiteScore(callee *ir.Func, calleeProps *FuncProps, call ir.Node, csflags CSPropBits) (int, scoreAdjustTyp) {
138 // Start with the size-based score for the callee.
139 score := int(callee.Inl.Cost)
140 var tmask scoreAdjustTyp
142 if debugTrace&debugTraceScoring != 0 {
143 fmt.Fprintf(os.Stderr, "=-= scoring call to %s at %s , initial=%d\n",
144 callee.Sym().Name, fmtFullPos(call.Pos()), score)
147 // First some score adjustments to discourage inlining in selected cases.
148 if csflags&CallSiteOnPanicPath != 0 {
149 score, tmask = adjustScore(panicPathAdj, score, tmask)
151 if csflags&CallSiteInInitFunc != 0 {
152 score, tmask = adjustScore(initFuncAdj, score, tmask)
155 // Then adjustments to encourage inlining in selected cases.
156 if csflags&CallSiteInLoop != 0 {
157 score, tmask = adjustScore(inLoopAdj, score, tmask)
160 // Walk through the actual expressions being passed at the call.
161 calleeRecvrParms := callee.Type().RecvParams()
162 ce := call.(*ir.CallExpr)
163 for idx := range ce.Args {
165 if calleeRecvrParms[idx].Sym == nil ||
166 calleeRecvrParms[idx].Sym.IsBlank() {
170 pflag := calleeProps.ParamFlags[idx]
171 if debugTrace&debugTraceScoring != 0 {
172 fmt.Fprintf(os.Stderr, "=-= arg %d of %d: val %v flags=%s\n",
173 idx, len(ce.Args), arg, pflag.String())
175 _, islit := isLiteral(arg)
176 iscci := isConcreteConvIface(arg)
177 fname, isfunc, _ := isFuncName(arg)
178 if debugTrace&debugTraceScoring != 0 {
179 fmt.Fprintf(os.Stderr, "=-= isLit=%v iscci=%v isfunc=%v for arg %v\n", islit, iscci, isfunc, arg)
183 if pflag&ParamMayFeedIfOrSwitch != 0 {
184 score, tmask = adjustScore(passConstToNestedIfAdj, score, tmask)
186 if pflag&ParamFeedsIfOrSwitch != 0 {
187 score, tmask = adjustScore(passConstToIfAdj, score, tmask)
192 // FIXME: ideally here it would be nice to make a
193 // distinction between the inlinable case and the
194 // non-inlinable case, but this is hard to do. Example:
196 // type I interface { Tiny() int; Giant() }
197 // type Conc struct { x int }
198 // func (c *Conc) Tiny() int { return 42 }
199 // func (c *Conc) Giant() { <huge amounts of code> }
201 // func passConcToItf(c *Conc) {
202 // makesItfMethodCall(c)
205 // In the code above, function properties will only tell
206 // us that 'makesItfMethodCall' invokes a method on its
207 // interface parameter, but we don't know whether it calls
208 // "Tiny" or "Giant". If we knew if called "Tiny", then in
209 // theory in addition to converting the interface call to
210 // a direct call, we could also inline (in which case
211 // we'd want to decrease the score even more).
213 // One thing we could do (not yet implemented) is iterate
214 // through all of the methods of "*Conc" that allow it to
215 // satisfy I, and if all are inlinable, then exploit that.
216 if pflag&ParamMayFeedInterfaceMethodCall != 0 {
217 score, tmask = adjustScore(passConcreteToNestedItfCallAdj, score, tmask)
219 if pflag&ParamFeedsInterfaceMethodCall != 0 {
220 score, tmask = adjustScore(passConcreteToItfCallAdj, score, tmask)
225 mayadj := passFuncToNestedIndCallAdj
226 mustadj := passFuncToIndCallAdj
227 if fn := fname.Func; fn != nil && typecheck.HaveInlineBody(fn) {
228 mayadj = passInlinableFuncToNestedIndCallAdj
229 mustadj = passInlinableFuncToIndCallAdj
231 if pflag&ParamMayFeedIndirectCall != 0 {
232 score, tmask = adjustScore(mayadj, score, tmask)
234 if pflag&ParamFeedsIndirectCall != 0 {
235 score, tmask = adjustScore(mustadj, score, tmask)
243 func adjustScore(typ scoreAdjustTyp, score int, mask scoreAdjustTyp) (int, scoreAdjustTyp) {
249 may := mustToMay(typ)
251 // promote may to must, so undo may
252 score -= adjValue(may)
255 } else if isMay(typ) {
256 must := mayToMust(typ)
257 if mask&(must|typ) != 0 {
262 if debugTrace&debugTraceScoring != 0 {
263 fmt.Fprintf(os.Stderr, "=-= applying adj %d for %s\n",
264 adjValue(typ), typ.String())
266 score += adjValue(typ)
272 // DumpInlCallSiteScores is invoked by the inliner if the debug flag
273 // "-d=dumpinlcallsitescores" is set; it dumps out a human-readable
274 // summary of all (potentially) inlinable callsites in the package,
275 // along with info on call site scoring and the adjustments made to a
276 // given score. Here profile is the PGO profile in use (may be
277 // nil), budgetCallback is a callback that can be invoked to find out
278 // the original pre-adjustment hairyness limit for the function, and
279 // inlineHotMaxBudget is the constant of the same name used in the
280 // inliner. Sample output lines:
282 // Score Adjustment Status Callee CallerPos ScoreFlags
283 // 115 40 DEMOTED cmd/compile/internal/abi.(*ABIParamAssignment).Offset expand_calls.go:1679:14|6 panicPathAdj
284 // 76 -5n PROMOTED runtime.persistentalloc mcheckmark.go:48:45|3 inLoopAdj
285 // 201 0 --- PGO unicode.DecodeRuneInString utf8.go:312:30|1
286 // 7 -5 --- PGO internal/abi.Name.DataChecked type.go:625:22|0 inLoopAdj
288 // In the dump above, "Score" is the final score calculated for the
289 // callsite, "Adjustment" is the amount added to or subtracted from
290 // the original hairyness estimate to form the score. "Status" shows
291 // whether anything changed with the site -- did the adjustment bump
292 // it down just below the threshold ("PROMOTED") or instead bump it
293 // above the threshold ("DEMOTED"); this will be blank ("---") if no
294 // threshold was crossed as a result of the heuristics. Note that
295 // "Status" also shows whether PGO was involved. "Callee" is the name
296 // of the function called, "CallerPos" is the position of the
297 // callsite, and "ScoreFlags" is a digest of the specific properties
298 // we used to make adjustments to callsite score via heuristics.
299 func DumpInlCallSiteScores(profile *pgo.Profile, budgetCallback func(fn *ir.Func, profile *pgo.Profile) (int32, bool)) {
301 fmt.Fprintf(os.Stdout, "# scores for package %s\n", types.LocalPkg.Path)
303 genstatus := func(cs *CallSite, prof *pgo.Profile) string {
304 hairyval := cs.Callee.Inl.Cost
305 bud, isPGO := budgetCallback(cs.Callee, prof)
306 score := int32(cs.Score)
310 case hairyval <= bud && score <= bud:
311 // "Normal" inlined case: hairy val sufficiently low that
312 // it would have been inlined anyway without heuristics.
313 case hairyval > bud && score > bud:
314 // "Normal" not inlined case: hairy val sufficiently high
315 // and scoring didn't lower it.
316 case hairyval > bud && score <= bud:
317 // Promoted: we would not have inlined it before, but
318 // after score adjustment we decided to inline.
320 case hairyval <= bud && score > bud:
321 // Demoted: we would have inlined it before, but after
322 // score adjustment we decided not to inline.
331 if base.Debug.DumpInlCallSiteScores != 0 {
333 for _, funcInlHeur := range fpmap {
334 for _, cs := range funcInlHeur.cstab {
338 sort.Slice(sl, func(i, j int) bool {
339 if sl[i].Score != sl[j].Score {
340 return sl[i].Score < sl[j].Score
342 fni := ir.PkgFuncName(sl[i].Callee)
343 fnj := ir.PkgFuncName(sl[j].Callee)
347 ecsi := EncodeCallSiteKey(sl[i])
348 ecsj := EncodeCallSiteKey(sl[j])
352 mkname := func(fn *ir.Func) string {
354 if fn == nil || fn.Nname == nil {
357 if fn.Sym().Pkg == types.LocalPkg {
358 n = "ยท" + fn.Sym().Name
360 n = ir.PkgFuncName(fn)
362 // don't try to print super-long names
366 return n[:32] + "..." + n[len(n)-32:len(n)]
370 fmt.Fprintf(os.Stdout, "Score Adjustment Status Callee CallerPos Flags ScoreFlags\n")
372 for _, cs := range sl {
373 hairyval := cs.Callee.Inl.Cost
374 adj := int32(cs.Score) - hairyval
375 fmt.Fprintf(os.Stdout, "%d %d\t%s\t%s\t%s\t%s\n",
376 cs.Score, adj, genstatus(cs, profile),
378 EncodeCallSiteKey(cs),
379 cs.ScoreMask.String())