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 interleaved implements the interleaved devirtualization and
6// inlining pass.
7package interleaved
8
9import (
10	"cmd/compile/internal/base"
11	"cmd/compile/internal/devirtualize"
12	"cmd/compile/internal/inline"
13	"cmd/compile/internal/inline/inlheur"
14	"cmd/compile/internal/ir"
15	"cmd/compile/internal/pgoir"
16	"cmd/compile/internal/typecheck"
17	"fmt"
18)
19
20// DevirtualizeAndInlinePackage interleaves devirtualization and inlining on
21// all functions within pkg.
22func DevirtualizeAndInlinePackage(pkg *ir.Package, profile *pgoir.Profile) {
23	if profile != nil && base.Debug.PGODevirtualize > 0 {
24		// TODO(mdempsky): Integrate into DevirtualizeAndInlineFunc below.
25		ir.VisitFuncsBottomUp(typecheck.Target.Funcs, func(list []*ir.Func, recursive bool) {
26			for _, fn := range list {
27				devirtualize.ProfileGuided(fn, profile)
28			}
29		})
30		ir.CurFunc = nil
31	}
32
33	if base.Flag.LowerL != 0 {
34		inlheur.SetupScoreAdjustments()
35	}
36
37	var inlProfile *pgoir.Profile // copy of profile for inlining
38	if base.Debug.PGOInline != 0 {
39		inlProfile = profile
40	}
41
42	// First compute inlinability of all functions in the package.
43	inline.CanInlineFuncs(pkg.Funcs, inlProfile)
44
45	// Now we make a second pass to do devirtualization and inlining of
46	// calls. Order here should not matter.
47	for _, fn := range pkg.Funcs {
48		DevirtualizeAndInlineFunc(fn, inlProfile)
49	}
50
51	if base.Flag.LowerL != 0 {
52		// Perform a garbage collection of hidden closures functions that
53		// are no longer reachable from top-level functions following
54		// inlining. See #59404 and #59638 for more context.
55		inline.GarbageCollectUnreferencedHiddenClosures()
56
57		if base.Debug.DumpInlFuncProps != "" {
58			inlheur.DumpFuncProps(nil, base.Debug.DumpInlFuncProps)
59		}
60		if inlheur.Enabled() {
61			inline.PostProcessCallSites(inlProfile)
62			inlheur.TearDown()
63		}
64	}
65}
66
67// DevirtualizeAndInlineFunc interleaves devirtualization and inlining
68// on a single function.
69func DevirtualizeAndInlineFunc(fn *ir.Func, profile *pgoir.Profile) {
70	ir.WithFunc(fn, func() {
71		if base.Flag.LowerL != 0 {
72			if inlheur.Enabled() && !fn.Wrapper() {
73				inlheur.ScoreCalls(fn)
74				defer inlheur.ScoreCallsCleanup()
75			}
76			if base.Debug.DumpInlFuncProps != "" && !fn.Wrapper() {
77				inlheur.DumpFuncProps(fn, base.Debug.DumpInlFuncProps)
78			}
79		}
80
81		bigCaller := base.Flag.LowerL != 0 && inline.IsBigFunc(fn)
82		if bigCaller && base.Flag.LowerM > 1 {
83			fmt.Printf("%v: function %v considered 'big'; reducing max cost of inlinees\n", ir.Line(fn), fn)
84		}
85
86		match := func(n ir.Node) bool {
87			switch n := n.(type) {
88			case *ir.CallExpr:
89				return true
90			case *ir.TailCallStmt:
91				n.Call.NoInline = true // can't inline yet
92			}
93			return false
94		}
95
96		edit := func(n ir.Node) ir.Node {
97			call, ok := n.(*ir.CallExpr)
98			if !ok { // previously inlined
99				return nil
100			}
101
102			devirtualize.StaticCall(call)
103			if inlCall := inline.TryInlineCall(fn, call, bigCaller, profile); inlCall != nil {
104				return inlCall
105			}
106			return nil
107		}
108
109		fixpoint(fn, match, edit)
110	})
111}
112
113// fixpoint repeatedly edits a function until it stabilizes.
114//
115// First, fixpoint applies match to every node n within fn. Then it
116// iteratively applies edit to each node satisfying match(n).
117//
118// If edit(n) returns nil, no change is made. Otherwise, the result
119// replaces n in fn's body, and fixpoint iterates at least once more.
120//
121// After an iteration where all edit calls return nil, fixpoint
122// returns.
123func fixpoint(fn *ir.Func, match func(ir.Node) bool, edit func(ir.Node) ir.Node) {
124	// Consider the expression "f(g())". We want to be able to replace
125	// "g()" in-place with its inlined representation. But if we first
126	// replace "f(...)" with its inlined representation, then "g()" will
127	// instead appear somewhere within this new AST.
128	//
129	// To mitigate this, each matched node n is wrapped in a ParenExpr,
130	// so we can reliably replace n in-place by assigning ParenExpr.X.
131	// It's safe to use ParenExpr here, because typecheck already
132	// removed them all.
133
134	var parens []*ir.ParenExpr
135	var mark func(ir.Node) ir.Node
136	mark = func(n ir.Node) ir.Node {
137		if _, ok := n.(*ir.ParenExpr); ok {
138			return n // already visited n.X before wrapping
139		}
140
141		ok := match(n)
142
143		ir.EditChildren(n, mark)
144
145		if ok {
146			paren := ir.NewParenExpr(n.Pos(), n)
147			paren.SetType(n.Type())
148			paren.SetTypecheck(n.Typecheck())
149
150			parens = append(parens, paren)
151			n = paren
152		}
153
154		return n
155	}
156	ir.EditChildren(fn, mark)
157
158	// Edit until stable.
159	for {
160		done := true
161
162		for i := 0; i < len(parens); i++ { // can't use "range parens" here
163			paren := parens[i]
164			if new := edit(paren.X); new != nil {
165				// Update AST and recursively mark nodes.
166				paren.X = new
167				ir.EditChildren(new, mark) // mark may append to parens
168				done = false
169			}
170		}
171
172		if done {
173			break
174		}
175	}
176
177	// Finally, remove any parens we inserted.
178	if len(parens) == 0 {
179		return // short circuit
180	}
181	var unparen func(ir.Node) ir.Node
182	unparen = func(n ir.Node) ir.Node {
183		if paren, ok := n.(*ir.ParenExpr); ok {
184			n = paren.X
185		}
186		ir.EditChildren(n, unparen)
187		return n
188	}
189	ir.EditChildren(fn, unparen)
190}
191