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