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                            uint64_t HotThreshold, uint64_t ColdThreshold)
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       HotCountThreshold(HotThreshold), ColdCountThreshold(ColdThreshold) {
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   // Adjust threshold based on call site hotness, only do this for callsite
156   // prioritized inliner because otherwise cost-benefit check is done earlier.
157   unsigned int SampleThreshold = SampleColdCallSiteThreshold;
158   if (Candidate.CallsiteCount > HotCountThreshold)
159     SampleThreshold = SampleHotCallSiteThreshold;
160 
161   // TODO: for small cold functions, we may inlined them and we need to keep
162   // context profile accordingly.
163   if (Candidate.CallsiteCount < ColdCountThreshold)
164     SampleThreshold = SampleColdCallSiteThreshold;
165 
166   return (Candidate.SizeCost < SampleThreshold);
167 }
168 
169 void CSPreInliner::processFunction(const StringRef Name) {
170   FunctionSamples *FSamples = ContextTracker.getBaseSamplesFor(Name);
171   if (!FSamples)
172     return;
173 
174   unsigned FuncSize = getFuncSize(*FSamples);
175   unsigned FuncFinalSize = FuncSize;
176   unsigned SizeLimit = FuncSize * ProfileInlineGrowthLimit;
177   SizeLimit = std::min(SizeLimit, (unsigned)ProfileInlineLimitMax);
178   SizeLimit = std::max(SizeLimit, (unsigned)ProfileInlineLimitMin);
179 
180   LLVM_DEBUG(dbgs() << "Process " << Name
181                     << " for context-sensitive pre-inlining (pre-inline size: "
182                     << FuncSize << ", size limit: " << SizeLimit << ")\n");
183 
184   ProfiledCandidateQueue CQueue;
185   getInlineCandidates(CQueue, FSamples);
186 
187   while (!CQueue.empty() && FuncFinalSize < SizeLimit) {
188     ProfiledInlineCandidate Candidate = CQueue.top();
189     CQueue.pop();
190     bool ShouldInline = false;
191     if ((ShouldInline = shouldInline(Candidate))) {
192       // We mark context as inlined as the corresponding context profile
193       // won't be merged into that function's base profile.
194       ++PreInlNumCSInlined;
195       ContextTracker.markContextSamplesInlined(Candidate.CalleeSamples);
196       Candidate.CalleeSamples->getContext().setAttribute(
197           ContextShouldBeInlined);
198       FuncFinalSize += Candidate.SizeCost;
199       getInlineCandidates(CQueue, Candidate.CalleeSamples);
200     } else {
201       ++PreInlNumCSNotInlined;
202     }
203     LLVM_DEBUG(dbgs() << (ShouldInline ? "  Inlined" : "  Outlined")
204                       << " context profile for: "
205                       << Candidate.CalleeSamples->getContext().toString()
206                       << " (callee size: " << Candidate.SizeCost
207                       << ", call count:" << Candidate.CallsiteCount << ")\n");
208   }
209 
210   if (!CQueue.empty()) {
211     if (SizeLimit == (unsigned)ProfileInlineLimitMax)
212       ++PreInlNumCSInlinedHitMaxLimit;
213     else if (SizeLimit == (unsigned)ProfileInlineLimitMin)
214       ++PreInlNumCSInlinedHitMinLimit;
215     else
216       ++PreInlNumCSInlinedHitGrowthLimit;
217   }
218 
219   LLVM_DEBUG({
220     if (!CQueue.empty())
221       dbgs() << "  Inline candidates ignored due to size limit (inliner "
222                 "original size: "
223              << FuncSize << ", inliner final size: " << FuncFinalSize
224              << ", size limit: " << SizeLimit << ")\n";
225 
226     while (!CQueue.empty()) {
227       ProfiledInlineCandidate Candidate = CQueue.top();
228       CQueue.pop();
229       bool WasInlined =
230           Candidate.CalleeSamples->getContext().hasAttribute(ContextWasInlined);
231       dbgs() << "    " << Candidate.CalleeSamples->getContext().toString()
232              << " (candidate size:" << Candidate.SizeCost
233              << ", call count: " << Candidate.CallsiteCount << ", previously "
234              << (WasInlined ? "inlined)\n" : "not inlined)\n");
235     }
236   });
237 }
238 
239 void CSPreInliner::run() {
240 #ifndef NDEBUG
241   auto printProfileNames = [](SampleProfileMap &Profiles, bool IsInput) {
242     dbgs() << (IsInput ? "Input" : "Output") << " context-sensitive profiles ("
243            << Profiles.size() << " total):\n";
244     for (auto &It : Profiles) {
245       const FunctionSamples &Samples = It.second;
246       dbgs() << "  [" << Samples.getContext().toString() << "] "
247              << Samples.getTotalSamples() << ":" << Samples.getHeadSamples()
248              << "\n";
249     }
250   };
251 #endif
252 
253   LLVM_DEBUG(printProfileNames(ProfileMap, true));
254 
255   // Execute global pre-inliner to estimate a global top-down inline
256   // decision and merge profiles accordingly. This helps with profile
257   // merge for ThinLTO otherwise we won't be able to merge profiles back
258   // to base profile across module/thin-backend boundaries.
259   // It also helps better compress context profile to control profile
260   // size, as we now only need context profile for functions going to
261   // be inlined.
262   for (StringRef FuncName : buildTopDownOrder()) {
263     processFunction(FuncName);
264   }
265 
266   // Not inlined context profiles are merged into its base, so we can
267   // trim out such profiles from the output.
268   std::vector<SampleContext> ProfilesToBeRemoved;
269   for (auto &It : ProfileMap) {
270     SampleContext &Context = It.second.getContext();
271     if (!Context.isBaseContext() && !Context.hasState(InlinedContext)) {
272       assert(Context.hasState(MergedContext) &&
273              "Not inlined context profile should be merged already");
274       ProfilesToBeRemoved.push_back(It.first);
275     }
276   }
277 
278   for (auto &ContextName : ProfilesToBeRemoved) {
279     ProfileMap.erase(ContextName);
280   }
281 
282   // Make sure ProfileMap's key is consistent with FunctionSamples' name.
283   SampleContextTrimmer(ProfileMap).canonicalizeContextProfiles();
284 
285   LLVM_DEBUG(printProfileNames(ProfileMap, false));
286 }
287