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