1//===-- CSPreInliner.cpp - Profile guided preinliner -------------- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "CSPreInliner.h"
10#include "ProfiledBinary.h"
11#include "llvm/ADT/SCCIterator.h"
12#include "llvm/ADT/Statistic.h"
13#include "llvm/Transforms/IPO/SampleProfile.h"
14#include <cstdint>
15
16#define DEBUG_TYPE "cs-preinliner"
17
18using namespace llvm;
19using namespace sampleprof;
20
21STATISTIC(PreInlNumCSInlined,
22 "Number of functions inlined with context sensitive profile");
23STATISTIC(PreInlNumCSNotInlined,
24 "Number of functions not inlined with context sensitive profile");
25STATISTIC(PreInlNumCSInlinedHitMinLimit,
26 "Number of functions with FDO inline stopped due to min size limit");
27STATISTIC(PreInlNumCSInlinedHitMaxLimit,
28 "Number of functions with FDO inline stopped due to max size limit");
29STATISTIC(
30 PreInlNumCSInlinedHitGrowthLimit,
31 "Number of functions with FDO inline stopped due to growth size limit");
32
33// The switches specify inline thresholds used in SampleProfileLoader inlining.
34// TODO: the actual threshold to be tuned here because the size here is based
35// on machine code not LLVM IR.
36namespace llvm {
37cl::opt<bool> EnableCSPreInliner(
38 "csspgo-preinliner", cl::Hidden, cl::init(Val: true),
39 cl::desc("Run a global pre-inliner to merge context profile based on "
40 "estimated global top-down inline decisions"));
41
42cl::opt<bool> UseContextCostForPreInliner(
43 "use-context-cost-for-preinliner", cl::Hidden, cl::init(Val: true),
44 cl::desc("Use context-sensitive byte size cost for preinliner decisions"));
45} // namespace llvm
46
47static cl::opt<bool> SamplePreInlineReplay(
48 "csspgo-replay-preinline", cl::Hidden, cl::init(Val: false),
49 cl::desc(
50 "Replay previous inlining and adjust context profile accordingly"));
51
52static cl::opt<int> CSPreinlMultiplierForPrevInl(
53 "csspgo-preinliner-multiplier-for-previous-inlining", cl::Hidden,
54 cl::init(Val: 100),
55 cl::desc(
56 "Multiplier to bump up callsite threshold for previous inlining."));
57
58CSPreInliner::CSPreInliner(SampleContextTracker &Tracker,
59 ProfiledBinary &Binary, ProfileSummary *Summary)
60 : UseContextCost(UseContextCostForPreInliner),
61 // TODO: Pass in a guid-to-name map in order for
62 // ContextTracker.getFuncNameFor to work, if `Profiles` can have md5 codes
63 // as their profile context.
64 ContextTracker(Tracker), Binary(Binary), Summary(Summary) {
65 // Set default preinliner hot/cold call site threshold tuned with CSSPGO.
66 // for good performance with reasonable profile size.
67 if (!SampleHotCallSiteThreshold.getNumOccurrences())
68 SampleHotCallSiteThreshold = 1500;
69 if (!SampleColdCallSiteThreshold.getNumOccurrences())
70 SampleColdCallSiteThreshold = 0;
71 if (!ProfileInlineLimitMax.getNumOccurrences())
72 ProfileInlineLimitMax = 50000;
73}
74
75std::vector<FunctionId> CSPreInliner::buildTopDownOrder() {
76 std::vector<FunctionId> Order;
77 // Trim cold edges to get a more stable call graph. This allows for a more
78 // stable top-down order which in turns helps the stablity of the generated
79 // profile from run to run.
80 uint64_t ColdCountThreshold = ProfileSummaryBuilder::getColdCountThreshold(
81 DS: (Summary->getDetailedSummary()));
82 ProfiledCallGraph ProfiledCG(ContextTracker, ColdCountThreshold);
83
84 // Now that we have a profiled call graph, construct top-down order
85 // by building up SCC and reversing SCC order.
86 scc_iterator<ProfiledCallGraph *> I = scc_begin(G: &ProfiledCG);
87 while (!I.isAtEnd()) {
88 auto Range = *I;
89 if (SortProfiledSCC) {
90 // Sort nodes in one SCC based on callsite hotness.
91 scc_member_iterator<ProfiledCallGraph *> SI(*I);
92 Range = *SI;
93 }
94 for (auto *Node : Range) {
95 if (Node != ProfiledCG.getEntryNode())
96 Order.push_back(x: Node->Name);
97 }
98 ++I;
99 }
100 std::reverse(first: Order.begin(), last: Order.end());
101
102 return Order;
103}
104
105bool CSPreInliner::getInlineCandidates(ProfiledCandidateQueue &CQueue,
106 const FunctionSamples *CallerSamples) {
107 assert(CallerSamples && "Expect non-null caller samples");
108
109 // Ideally we want to consider everything a function calls, but as far as
110 // context profile is concerned, only those frames that are children of
111 // current one in the trie is relavent. So we walk the trie instead of call
112 // targets from function profile.
113 ContextTrieNode *CallerNode =
114 ContextTracker.getContextNodeForProfile(FSamples: CallerSamples);
115
116 bool HasNewCandidate = false;
117 for (auto &Child : CallerNode->getAllChildContext()) {
118 ContextTrieNode *CalleeNode = &Child.second;
119 FunctionSamples *CalleeSamples = CalleeNode->getFunctionSamples();
120 if (!CalleeSamples)
121 continue;
122
123 // Call site count is more reliable, so we look up the corresponding call
124 // target profile in caller's context profile to retrieve call site count.
125 uint64_t CalleeEntryCount = CalleeSamples->getHeadSamplesEstimate();
126 uint64_t CallsiteCount = 0;
127 LineLocation Callsite = CalleeNode->getCallSiteLoc();
128 if (auto CallTargets = CallerSamples->findCallTargetMapAt(CallSite: Callsite)) {
129 auto It = CallTargets->find(Key: CalleeSamples->getFunction());
130 if (It != CallTargets->end())
131 CallsiteCount = It->second;
132 }
133
134 // TODO: call site and callee entry count should be mostly consistent, add
135 // check for that.
136 HasNewCandidate = true;
137 uint32_t CalleeSize = getFuncSize(ContextNode: CalleeNode);
138 CQueue.emplace(args&: CalleeSamples, args: std::max(a: CallsiteCount, b: CalleeEntryCount),
139 args&: CalleeSize);
140 }
141
142 return HasNewCandidate;
143}
144
145uint32_t CSPreInliner::getFuncSize(const ContextTrieNode *ContextNode) {
146 if (UseContextCost)
147 return Binary.getFuncSizeForContext(ContextNode);
148
149 return ContextNode->getFunctionSamples()->getBodySamples().size();
150}
151
152bool CSPreInliner::shouldInline(ProfiledInlineCandidate &Candidate) {
153 bool WasInlined =
154 Candidate.CalleeSamples->getContext().hasAttribute(A: ContextWasInlined);
155 // If replay inline is requested, simply follow the inline decision of the
156 // profiled binary.
157 if (SamplePreInlineReplay)
158 return WasInlined;
159
160 unsigned int SampleThreshold = SampleColdCallSiteThreshold;
161 uint64_t ColdCountThreshold = ProfileSummaryBuilder::getColdCountThreshold(
162 DS: (Summary->getDetailedSummary()));
163
164 if (Candidate.CallsiteCount <= ColdCountThreshold)
165 SampleThreshold = SampleColdCallSiteThreshold;
166 else {
167 // Linearly adjust threshold based on normalized hotness, i.e, a value in
168 // [0,1]. Use 10% cutoff instead of the max count as the normalization
169 // upperbound for stability.
170 double NormalizationUpperBound =
171 ProfileSummaryBuilder::getEntryForPercentile(
172 DS: Summary->getDetailedSummary(), Percentile: 100000 /* 10% */)
173 .MinCount;
174 double NormalizationLowerBound = ColdCountThreshold;
175 double NormalizedHotness =
176 (Candidate.CallsiteCount - NormalizationLowerBound) /
177 (NormalizationUpperBound - NormalizationLowerBound);
178 if (NormalizedHotness > 1.0)
179 NormalizedHotness = 1.0;
180 // Add 1 to ensure hot callsites get a non-zero threshold, which could
181 // happen when SampleColdCallSiteThreshold is 0. This is when we do not
182 // want any inlining for cold callsites.
183 SampleThreshold = SampleHotCallSiteThreshold * NormalizedHotness * 100 +
184 SampleColdCallSiteThreshold + 1;
185 // Bump up the threshold to favor previous compiler inline decision. The
186 // compiler has more insight and knowledge about functions based on their IR
187 // and attribures and should be able to make a more reasonable inline
188 // decision.
189 if (WasInlined)
190 SampleThreshold *= CSPreinlMultiplierForPrevInl;
191 }
192
193 return (Candidate.SizeCost < SampleThreshold);
194}
195
196void CSPreInliner::processFunction(const FunctionId Name) {
197 FunctionSamples *FSamples = ContextTracker.getBaseSamplesFor(Name);
198 if (!FSamples)
199 return;
200
201 unsigned FuncSize =
202 getFuncSize(ContextNode: ContextTracker.getContextNodeForProfile(FSamples));
203 unsigned FuncFinalSize = FuncSize;
204 unsigned SizeLimit = FuncSize * ProfileInlineGrowthLimit;
205 SizeLimit = std::min(a: SizeLimit, b: (unsigned)ProfileInlineLimitMax);
206 SizeLimit = std::max(a: SizeLimit, b: (unsigned)ProfileInlineLimitMin);
207
208 LLVM_DEBUG(dbgs() << "Process " << Name
209 << " for context-sensitive pre-inlining (pre-inline size: "
210 << FuncSize << ", size limit: " << SizeLimit << ")\n");
211
212 ProfiledCandidateQueue CQueue;
213 getInlineCandidates(CQueue, CallerSamples: FSamples);
214
215 while (!CQueue.empty() && FuncFinalSize < SizeLimit) {
216 ProfiledInlineCandidate Candidate = CQueue.top();
217 CQueue.pop();
218 bool ShouldInline = false;
219 if ((ShouldInline = shouldInline(Candidate))) {
220 // We mark context as inlined as the corresponding context profile
221 // won't be merged into that function's base profile.
222 ++PreInlNumCSInlined;
223 ContextTracker.markContextSamplesInlined(InlinedSamples: Candidate.CalleeSamples);
224 Candidate.CalleeSamples->getContext().setAttribute(
225 ContextShouldBeInlined);
226 FuncFinalSize += Candidate.SizeCost;
227 getInlineCandidates(CQueue, CallerSamples: Candidate.CalleeSamples);
228 } else {
229 ++PreInlNumCSNotInlined;
230 }
231 LLVM_DEBUG(
232 dbgs() << (ShouldInline ? " Inlined" : " Outlined")
233 << " context profile for: "
234 << ContextTracker.getContextString(*Candidate.CalleeSamples)
235 << " (callee size: " << Candidate.SizeCost
236 << ", call count:" << Candidate.CallsiteCount << ")\n");
237 }
238
239 if (!CQueue.empty()) {
240 if (SizeLimit == (unsigned)ProfileInlineLimitMax)
241 ++PreInlNumCSInlinedHitMaxLimit;
242 else if (SizeLimit == (unsigned)ProfileInlineLimitMin)
243 ++PreInlNumCSInlinedHitMinLimit;
244 else
245 ++PreInlNumCSInlinedHitGrowthLimit;
246 }
247
248 LLVM_DEBUG({
249 if (!CQueue.empty())
250 dbgs() << " Inline candidates ignored due to size limit (inliner "
251 "original size: "
252 << FuncSize << ", inliner final size: " << FuncFinalSize
253 << ", size limit: " << SizeLimit << ")\n";
254
255 while (!CQueue.empty()) {
256 ProfiledInlineCandidate Candidate = CQueue.top();
257 CQueue.pop();
258 bool WasInlined =
259 Candidate.CalleeSamples->getContext().hasAttribute(ContextWasInlined);
260 dbgs() << " "
261 << ContextTracker.getContextString(*Candidate.CalleeSamples)
262 << " (candidate size:" << Candidate.SizeCost
263 << ", call count: " << Candidate.CallsiteCount << ", previously "
264 << (WasInlined ? "inlined)\n" : "not inlined)\n");
265 }
266 });
267}
268
269void CSPreInliner::run() {
270#ifndef NDEBUG
271 auto printProfileNames = [](SampleContextTracker &ContextTracker,
272 bool IsInput) {
273 uint32_t Size = 0;
274 for (auto *Node : ContextTracker) {
275 FunctionSamples *FSamples = Node->getFunctionSamples();
276 if (FSamples) {
277 Size++;
278 dbgs() << " [" << ContextTracker.getContextString(Node) << "] "
279 << FSamples->getTotalSamples() << ":"
280 << FSamples->getHeadSamples() << "\n";
281 }
282 }
283 dbgs() << (IsInput ? "Input" : "Output") << " context-sensitive profiles ("
284 << Size << " total):\n";
285 };
286#endif
287
288 LLVM_DEBUG(printProfileNames(ContextTracker, true));
289
290 // Execute global pre-inliner to estimate a global top-down inline
291 // decision and merge profiles accordingly. This helps with profile
292 // merge for ThinLTO otherwise we won't be able to merge profiles back
293 // to base profile across module/thin-backend boundaries.
294 // It also helps better compress context profile to control profile
295 // size, as we now only need context profile for functions going to
296 // be inlined.
297 for (FunctionId FuncName : buildTopDownOrder()) {
298 processFunction(Name: FuncName);
299 }
300
301 // Not inlined context profiles are merged into its base, so we can
302 // trim out such profiles from the output.
303 for (auto *Node : ContextTracker) {
304 FunctionSamples *FProfile = Node->getFunctionSamples();
305 if (FProfile &&
306 (Node->getParentContext() != &ContextTracker.getRootContext() &&
307 !FProfile->getContext().hasState(S: InlinedContext))) {
308 Node->setFunctionSamples(nullptr);
309 }
310 }
311 FunctionSamples::ProfileIsPreInlined = true;
312
313 LLVM_DEBUG(printProfileNames(ContextTracker, false));
314}
315