1//===- SampleProfile.cpp - Incorporate sample profiles into the IR --------===//
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// This file implements the SampleProfileLoader transformation. This pass
10// reads a profile file generated by a sampling profiler (e.g. Linux Perf -
11// http://perf.wiki.kernel.org/) and generates IR metadata to reflect the
12// profile information in the given profile.
13//
14// This pass generates branch weight annotations on the IR:
15//
16// - prof: Represents branch weights. This annotation is added to branches
17// to indicate the weights of each edge coming out of the branch.
18// The weight of each edge is the weight of the target block for
19// that edge. The weight of a block B is computed as the maximum
20// number of samples found in B.
21//
22//===----------------------------------------------------------------------===//
23
24#include "llvm/Transforms/IPO/SampleProfile.h"
25#include "llvm/ADT/ArrayRef.h"
26#include "llvm/ADT/DenseMap.h"
27#include "llvm/ADT/DenseSet.h"
28#include "llvm/ADT/MapVector.h"
29#include "llvm/ADT/PriorityQueue.h"
30#include "llvm/ADT/SCCIterator.h"
31#include "llvm/ADT/SmallVector.h"
32#include "llvm/ADT/Statistic.h"
33#include "llvm/ADT/StringRef.h"
34#include "llvm/ADT/Twine.h"
35#include "llvm/Analysis/AssumptionCache.h"
36#include "llvm/Analysis/BlockFrequencyInfoImpl.h"
37#include "llvm/Analysis/InlineAdvisor.h"
38#include "llvm/Analysis/InlineCost.h"
39#include "llvm/Analysis/LazyCallGraph.h"
40#include "llvm/Analysis/OptimizationRemarkEmitter.h"
41#include "llvm/Analysis/ProfileSummaryInfo.h"
42#include "llvm/Analysis/ReplayInlineAdvisor.h"
43#include "llvm/Analysis/TargetLibraryInfo.h"
44#include "llvm/Analysis/TargetTransformInfo.h"
45#include "llvm/IR/BasicBlock.h"
46#include "llvm/IR/DebugLoc.h"
47#include "llvm/IR/DiagnosticInfo.h"
48#include "llvm/IR/Function.h"
49#include "llvm/IR/GlobalValue.h"
50#include "llvm/IR/InstrTypes.h"
51#include "llvm/IR/Instruction.h"
52#include "llvm/IR/Instructions.h"
53#include "llvm/IR/IntrinsicInst.h"
54#include "llvm/IR/LLVMContext.h"
55#include "llvm/IR/MDBuilder.h"
56#include "llvm/IR/Module.h"
57#include "llvm/IR/PassManager.h"
58#include "llvm/IR/ProfDataUtils.h"
59#include "llvm/IR/PseudoProbe.h"
60#include "llvm/IR/ValueSymbolTable.h"
61#include "llvm/ProfileData/InstrProf.h"
62#include "llvm/ProfileData/SampleProf.h"
63#include "llvm/ProfileData/SampleProfReader.h"
64#include "llvm/Support/Casting.h"
65#include "llvm/Support/CommandLine.h"
66#include "llvm/Support/Debug.h"
67#include "llvm/Support/ErrorOr.h"
68#include "llvm/Support/VirtualFileSystem.h"
69#include "llvm/Support/raw_ostream.h"
70#include "llvm/Transforms/IPO.h"
71#include "llvm/Transforms/IPO/ProfiledCallGraph.h"
72#include "llvm/Transforms/IPO/SampleContextTracker.h"
73#include "llvm/Transforms/IPO/SampleProfileMatcher.h"
74#include "llvm/Transforms/IPO/SampleProfileProbe.h"
75#include "llvm/Transforms/Utils/CallPromotionUtils.h"
76#include "llvm/Transforms/Utils/Cloning.h"
77#include "llvm/Transforms/Utils/Instrumentation.h"
78#include "llvm/Transforms/Utils/MisExpect.h"
79#include "llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h"
80#include "llvm/Transforms/Utils/SampleProfileLoaderBaseUtil.h"
81#include <algorithm>
82#include <cassert>
83#include <cstdint>
84#include <functional>
85#include <limits>
86#include <memory>
87#include <queue>
88#include <string>
89#include <system_error>
90#include <utility>
91#include <vector>
92
93using namespace llvm;
94using namespace sampleprof;
95using namespace llvm::sampleprofutil;
96#define DEBUG_TYPE "sample-profile"
97#define CSINLINE_DEBUG DEBUG_TYPE "-inline"
98
99STATISTIC(NumCSInlined,
100 "Number of functions inlined with context sensitive profile");
101STATISTIC(NumCSNotInlined,
102 "Number of functions not inlined with context sensitive profile");
103STATISTIC(NumMismatchedProfile,
104 "Number of functions with CFG mismatched profile");
105STATISTIC(NumMatchedProfile, "Number of functions with CFG matched profile");
106STATISTIC(NumDuplicatedInlinesite,
107 "Number of inlined callsites with a partial distribution factor");
108
109STATISTIC(NumCSInlinedHitMinLimit,
110 "Number of functions with FDO inline stopped due to min size limit");
111STATISTIC(NumCSInlinedHitMaxLimit,
112 "Number of functions with FDO inline stopped due to max size limit");
113STATISTIC(
114 NumCSInlinedHitGrowthLimit,
115 "Number of functions with FDO inline stopped due to growth size limit");
116
117namespace llvm {
118
119// Command line option to specify the file to read samples from. This is
120// mainly used for debugging.
121cl::opt<std::string> SampleProfileFile(
122 "sample-profile-file", cl::init(Val: ""), cl::value_desc("filename"),
123 cl::desc("Profile file loaded by -sample-profile"), cl::Hidden);
124
125// The named file contains a set of transformations that may have been applied
126// to the symbol names between the program from which the sample data was
127// collected and the current program's symbols.
128static cl::opt<std::string> SampleProfileRemappingFile(
129 "sample-profile-remapping-file", cl::init(Val: ""), cl::value_desc("filename"),
130 cl::desc("Profile remapping file loaded by -sample-profile"), cl::Hidden);
131
132cl::opt<bool> SalvageStaleProfile(
133 "salvage-stale-profile", cl::Hidden, cl::init(Val: false),
134 cl::desc("Salvage stale profile by fuzzy matching and use the remapped "
135 "location for sample profile query."));
136cl::opt<bool>
137 SalvageUnusedProfile("salvage-unused-profile", cl::Hidden, cl::init(Val: false),
138 cl::desc("Salvage unused profile by matching with new "
139 "functions on call graph."));
140
141cl::opt<bool> ReportProfileStaleness(
142 "report-profile-staleness", cl::Hidden, cl::init(Val: false),
143 cl::desc("Compute and report stale profile statistical metrics."));
144
145cl::opt<bool> PersistProfileStaleness(
146 "persist-profile-staleness", cl::Hidden, cl::init(Val: false),
147 cl::desc("Compute stale profile statistical metrics and write it into the "
148 "native object file(.llvm_stats section)."));
149
150static cl::opt<bool> ProfileSampleAccurate(
151 "profile-sample-accurate", cl::Hidden, cl::init(Val: false),
152 cl::desc("If the sample profile is accurate, we will mark all un-sampled "
153 "callsite and function as having 0 samples. Otherwise, treat "
154 "un-sampled callsites and functions conservatively as unknown. "));
155
156static cl::opt<bool> ProfileSampleBlockAccurate(
157 "profile-sample-block-accurate", cl::Hidden, cl::init(Val: false),
158 cl::desc("If the sample profile is accurate, we will mark all un-sampled "
159 "branches and calls as having 0 samples. Otherwise, treat "
160 "them conservatively as unknown. "));
161
162static cl::opt<bool> ProfileAccurateForSymsInList(
163 "profile-accurate-for-symsinlist", cl::Hidden, cl::init(Val: true),
164 cl::desc("For symbols in profile symbol list, regard their profiles to "
165 "be accurate. It may be overridden by profile-sample-accurate. "));
166
167static cl::opt<bool> ProfileMergeInlinee(
168 "sample-profile-merge-inlinee", cl::Hidden, cl::init(Val: true),
169 cl::desc("Merge past inlinee's profile to outline version if sample "
170 "profile loader decided not to inline a call site. It will "
171 "only be enabled when top-down order of profile loading is "
172 "enabled. "));
173
174static cl::opt<bool> ProfileTopDownLoad(
175 "sample-profile-top-down-load", cl::Hidden, cl::init(Val: true),
176 cl::desc("Do profile annotation and inlining for functions in top-down "
177 "order of call graph during sample profile loading. It only "
178 "works for new pass manager. "));
179
180static cl::opt<bool>
181 UseProfiledCallGraph("use-profiled-call-graph", cl::init(Val: true), cl::Hidden,
182 cl::desc("Process functions in a top-down order "
183 "defined by the profiled call graph when "
184 "-sample-profile-top-down-load is on."));
185
186static cl::opt<bool> ProfileSizeInline(
187 "sample-profile-inline-size", cl::Hidden, cl::init(Val: false),
188 cl::desc("Inline cold call sites in profile loader if it's beneficial "
189 "for code size."));
190
191// Since profiles are consumed by many passes, turning on this option has
192// side effects. For instance, pre-link SCC inliner would see merged profiles
193// and inline the hot functions (that are skipped in this pass).
194static cl::opt<bool> DisableSampleLoaderInlining(
195 "disable-sample-loader-inlining", cl::Hidden, cl::init(Val: false),
196 cl::desc(
197 "If true, artificially skip inline transformation in sample-loader "
198 "pass, and merge (or scale) profiles (as configured by "
199 "--sample-profile-merge-inlinee)."));
200
201cl::opt<bool>
202 SortProfiledSCC("sort-profiled-scc-member", cl::init(Val: true), cl::Hidden,
203 cl::desc("Sort profiled recursion by edge weights."));
204
205cl::opt<int> ProfileInlineGrowthLimit(
206 "sample-profile-inline-growth-limit", cl::Hidden, cl::init(Val: 12),
207 cl::desc("The size growth ratio limit for proirity-based sample profile "
208 "loader inlining."));
209
210cl::opt<int> ProfileInlineLimitMin(
211 "sample-profile-inline-limit-min", cl::Hidden, cl::init(Val: 100),
212 cl::desc("The lower bound of size growth limit for "
213 "proirity-based sample profile loader inlining."));
214
215cl::opt<int> ProfileInlineLimitMax(
216 "sample-profile-inline-limit-max", cl::Hidden, cl::init(Val: 10000),
217 cl::desc("The upper bound of size growth limit for "
218 "proirity-based sample profile loader inlining."));
219
220cl::opt<int> SampleHotCallSiteThreshold(
221 "sample-profile-hot-inline-threshold", cl::Hidden, cl::init(Val: 3000),
222 cl::desc("Hot callsite threshold for proirity-based sample profile loader "
223 "inlining."));
224
225cl::opt<int> SampleColdCallSiteThreshold(
226 "sample-profile-cold-inline-threshold", cl::Hidden, cl::init(Val: 45),
227 cl::desc("Threshold for inlining cold callsites"));
228} // namespace llvm
229
230static cl::opt<unsigned> ProfileICPRelativeHotness(
231 "sample-profile-icp-relative-hotness", cl::Hidden, cl::init(Val: 25),
232 cl::desc(
233 "Relative hotness percentage threshold for indirect "
234 "call promotion in proirity-based sample profile loader inlining."));
235
236static cl::opt<unsigned> ProfileICPRelativeHotnessSkip(
237 "sample-profile-icp-relative-hotness-skip", cl::Hidden, cl::init(Val: 1),
238 cl::desc(
239 "Skip relative hotness check for ICP up to given number of targets."));
240
241static cl::opt<unsigned> HotFuncCutoffForStalenessError(
242 "hot-func-cutoff-for-staleness-error", cl::Hidden, cl::init(Val: 800000),
243 cl::desc("A function is considered hot for staleness error check if its "
244 "total sample count is above the specified percentile"));
245
246static cl::opt<unsigned> MinfuncsForStalenessError(
247 "min-functions-for-staleness-error", cl::Hidden, cl::init(Val: 50),
248 cl::desc("Skip the check if the number of hot functions is smaller than "
249 "the specified number."));
250
251static cl::opt<unsigned> PrecentMismatchForStalenessError(
252 "precent-mismatch-for-staleness-error", cl::Hidden, cl::init(Val: 80),
253 cl::desc("Reject the profile if the mismatch percent is higher than the "
254 "given number."));
255
256static cl::opt<bool> CallsitePrioritizedInline(
257 "sample-profile-prioritized-inline", cl::Hidden,
258 cl::desc("Use call site prioritized inlining for sample profile loader. "
259 "Currently only CSSPGO is supported."));
260
261static cl::opt<bool> UsePreInlinerDecision(
262 "sample-profile-use-preinliner", cl::Hidden,
263 cl::desc("Use the preinliner decisions stored in profile context."));
264
265static cl::opt<bool> AllowRecursiveInline(
266 "sample-profile-recursive-inline", cl::Hidden,
267 cl::desc("Allow sample loader inliner to inline recursive calls."));
268
269static cl::opt<bool> RemoveProbeAfterProfileAnnotation(
270 "sample-profile-remove-probe", cl::Hidden, cl::init(Val: false),
271 cl::desc("Remove pseudo-probe after sample profile annotation."));
272
273static cl::opt<std::string> ProfileInlineReplayFile(
274 "sample-profile-inline-replay", cl::init(Val: ""), cl::value_desc("filename"),
275 cl::desc(
276 "Optimization remarks file containing inline remarks to be replayed "
277 "by inlining from sample profile loader."),
278 cl::Hidden);
279
280static cl::opt<ReplayInlinerSettings::Scope> ProfileInlineReplayScope(
281 "sample-profile-inline-replay-scope",
282 cl::init(Val: ReplayInlinerSettings::Scope::Function),
283 cl::values(clEnumValN(ReplayInlinerSettings::Scope::Function, "Function",
284 "Replay on functions that have remarks associated "
285 "with them (default)"),
286 clEnumValN(ReplayInlinerSettings::Scope::Module, "Module",
287 "Replay on the entire module")),
288 cl::desc("Whether inline replay should be applied to the entire "
289 "Module or just the Functions (default) that are present as "
290 "callers in remarks during sample profile inlining."),
291 cl::Hidden);
292
293static cl::opt<ReplayInlinerSettings::Fallback> ProfileInlineReplayFallback(
294 "sample-profile-inline-replay-fallback",
295 cl::init(Val: ReplayInlinerSettings::Fallback::Original),
296 cl::values(
297 clEnumValN(
298 ReplayInlinerSettings::Fallback::Original, "Original",
299 "All decisions not in replay send to original advisor (default)"),
300 clEnumValN(ReplayInlinerSettings::Fallback::AlwaysInline,
301 "AlwaysInline", "All decisions not in replay are inlined"),
302 clEnumValN(ReplayInlinerSettings::Fallback::NeverInline, "NeverInline",
303 "All decisions not in replay are not inlined")),
304 cl::desc("How sample profile inline replay treats sites that don't come "
305 "from the replay. Original: defers to original advisor, "
306 "AlwaysInline: inline all sites not in replay, NeverInline: "
307 "inline no sites not in replay"),
308 cl::Hidden);
309
310static cl::opt<CallSiteFormat::Format> ProfileInlineReplayFormat(
311 "sample-profile-inline-replay-format",
312 cl::init(Val: CallSiteFormat::Format::LineColumnDiscriminator),
313 cl::values(
314 clEnumValN(CallSiteFormat::Format::Line, "Line", "<Line Number>"),
315 clEnumValN(CallSiteFormat::Format::LineColumn, "LineColumn",
316 "<Line Number>:<Column Number>"),
317 clEnumValN(CallSiteFormat::Format::LineDiscriminator,
318 "LineDiscriminator", "<Line Number>.<Discriminator>"),
319 clEnumValN(CallSiteFormat::Format::LineColumnDiscriminator,
320 "LineColumnDiscriminator",
321 "<Line Number>:<Column Number>.<Discriminator> (default)")),
322 cl::desc("How sample profile inline replay file is formatted"), cl::Hidden);
323
324static cl::opt<unsigned>
325 MaxNumPromotions("sample-profile-icp-max-prom", cl::init(Val: 3), cl::Hidden,
326 cl::desc("Max number of promotions for a single indirect "
327 "call callsite in sample profile loader"));
328
329static cl::opt<bool> OverwriteExistingWeights(
330 "overwrite-existing-weights", cl::Hidden, cl::init(Val: false),
331 cl::desc("Ignore existing branch weights on IR and always overwrite."));
332
333static cl::opt<bool> AnnotateSampleProfileInlinePhase(
334 "annotate-sample-profile-inline-phase", cl::Hidden, cl::init(Val: false),
335 cl::desc("Annotate LTO phase (prelink / postlink), or main (no LTO) for "
336 "sample-profile inline pass name."));
337
338namespace llvm {
339extern cl::opt<bool> EnableExtTspBlockPlacement;
340}
341
342namespace {
343
344using BlockWeightMap = DenseMap<const BasicBlock *, uint64_t>;
345using EquivalenceClassMap = DenseMap<const BasicBlock *, const BasicBlock *>;
346using Edge = std::pair<const BasicBlock *, const BasicBlock *>;
347using EdgeWeightMap = DenseMap<Edge, uint64_t>;
348using BlockEdgeMap =
349 DenseMap<const BasicBlock *, SmallVector<const BasicBlock *, 8>>;
350
351class GUIDToFuncNameMapper {
352public:
353 GUIDToFuncNameMapper(Module &M, SampleProfileReader &Reader,
354 DenseMap<uint64_t, StringRef> &GUIDToFuncNameMap)
355 : CurrentReader(Reader), CurrentModule(M),
356 CurrentGUIDToFuncNameMap(GUIDToFuncNameMap) {
357 if (!CurrentReader.useMD5())
358 return;
359
360 for (const auto &F : CurrentModule) {
361 StringRef OrigName = F.getName();
362 CurrentGUIDToFuncNameMap.insert(
363 KV: {Function::getGUIDAssumingExternalLinkage(GlobalName: OrigName), OrigName});
364
365 // Local to global var promotion used by optimization like thinlto
366 // will rename the var and add suffix like ".llvm.xxx" to the
367 // original local name. In sample profile, the suffixes of function
368 // names are all stripped. Since it is possible that the mapper is
369 // built in post-thin-link phase and var promotion has been done,
370 // we need to add the substring of function name without the suffix
371 // into the GUIDToFuncNameMap.
372 StringRef CanonName = FunctionSamples::getCanonicalFnName(F);
373 if (CanonName != OrigName)
374 CurrentGUIDToFuncNameMap.insert(
375 KV: {Function::getGUIDAssumingExternalLinkage(GlobalName: CanonName), CanonName});
376 }
377
378 // Update GUIDToFuncNameMap for each function including inlinees.
379 SetGUIDToFuncNameMapForAll(&CurrentGUIDToFuncNameMap);
380 }
381
382 ~GUIDToFuncNameMapper() {
383 if (!CurrentReader.useMD5())
384 return;
385
386 CurrentGUIDToFuncNameMap.clear();
387
388 // Reset GUIDToFuncNameMap for of each function as they're no
389 // longer valid at this point.
390 SetGUIDToFuncNameMapForAll(nullptr);
391 }
392
393private:
394 void SetGUIDToFuncNameMapForAll(DenseMap<uint64_t, StringRef> *Map) {
395 std::queue<FunctionSamples *> FSToUpdate;
396 for (auto &IFS : CurrentReader.getProfiles()) {
397 FSToUpdate.push(x: &IFS.second);
398 }
399
400 while (!FSToUpdate.empty()) {
401 FunctionSamples *FS = FSToUpdate.front();
402 FSToUpdate.pop();
403 FS->GUIDToFuncNameMap = Map;
404 for (const auto &ICS : FS->getCallsiteSamples()) {
405 const FunctionSamplesMap &FSMap = ICS.second;
406 for (const auto &IFS : FSMap) {
407 FunctionSamples &FS = const_cast<FunctionSamples &>(IFS.second);
408 FSToUpdate.push(x: &FS);
409 }
410 }
411 }
412 }
413
414 SampleProfileReader &CurrentReader;
415 Module &CurrentModule;
416 DenseMap<uint64_t, StringRef> &CurrentGUIDToFuncNameMap;
417};
418
419// Inline candidate used by iterative callsite prioritized inliner
420struct InlineCandidate {
421 CallBase *CallInstr;
422 const FunctionSamples *CalleeSamples;
423 // Prorated callsite count, which will be used to guide inlining. For example,
424 // if a callsite is duplicated in LTO prelink, then in LTO postlink the two
425 // copies will get their own distribution factors and their prorated counts
426 // will be used to decide if they should be inlined independently.
427 uint64_t CallsiteCount;
428 // Call site distribution factor to prorate the profile samples for a
429 // duplicated callsite. Default value is 1.0.
430 float CallsiteDistribution;
431};
432
433// Inline candidate comparer using call site weight
434struct CandidateComparer {
435 bool operator()(const InlineCandidate &LHS, const InlineCandidate &RHS) {
436 if (LHS.CallsiteCount != RHS.CallsiteCount)
437 return LHS.CallsiteCount < RHS.CallsiteCount;
438
439 const FunctionSamples *LCS = LHS.CalleeSamples;
440 const FunctionSamples *RCS = RHS.CalleeSamples;
441 // In inline replay mode, CalleeSamples may be null and the order doesn't
442 // matter.
443 if (!LCS || !RCS)
444 return LCS;
445
446 // Tie breaker using number of samples try to favor smaller functions first
447 if (LCS->getBodySamples().size() != RCS->getBodySamples().size())
448 return LCS->getBodySamples().size() > RCS->getBodySamples().size();
449
450 // Tie breaker using GUID so we have stable/deterministic inlining order
451 return LCS->getGUID() < RCS->getGUID();
452 }
453};
454
455using CandidateQueue =
456 PriorityQueue<InlineCandidate, std::vector<InlineCandidate>,
457 CandidateComparer>;
458
459/// Sample profile pass.
460///
461/// This pass reads profile data from the file specified by
462/// -sample-profile-file and annotates every affected function with the
463/// profile information found in that file.
464class SampleProfileLoader final : public SampleProfileLoaderBaseImpl<Function> {
465public:
466 SampleProfileLoader(
467 StringRef Name, StringRef RemapName, ThinOrFullLTOPhase LTOPhase,
468 IntrusiveRefCntPtr<vfs::FileSystem> FS,
469 std::function<AssumptionCache &(Function &)> GetAssumptionCache,
470 std::function<TargetTransformInfo &(Function &)> GetTargetTransformInfo,
471 std::function<const TargetLibraryInfo &(Function &)> GetTLI,
472 LazyCallGraph &CG, bool DisableSampleProfileInlining,
473 bool UseFlattenedProfile)
474 : SampleProfileLoaderBaseImpl(std::string(Name), std::string(RemapName),
475 std::move(FS)),
476 GetAC(std::move(GetAssumptionCache)),
477 GetTTI(std::move(GetTargetTransformInfo)), GetTLI(std::move(GetTLI)),
478 CG(CG), LTOPhase(LTOPhase),
479 AnnotatedPassName(AnnotateSampleProfileInlinePhase
480 ? llvm::AnnotateInlinePassName(IC: InlineContext{
481 .LTOPhase: LTOPhase, .Pass: InlinePass::SampleProfileInliner})
482 : CSINLINE_DEBUG),
483 DisableSampleProfileInlining(DisableSampleProfileInlining),
484 UseFlattenedProfile(UseFlattenedProfile) {}
485
486 bool doInitialization(Module &M, FunctionAnalysisManager *FAM = nullptr);
487 bool runOnModule(Module &M, ModuleAnalysisManager &AM,
488 ProfileSummaryInfo *_PSI);
489
490protected:
491 bool runOnFunction(Function &F, ModuleAnalysisManager &AM);
492 bool emitAnnotations(Function &F);
493 ErrorOr<uint64_t> getInstWeight(const Instruction &I) override;
494 const FunctionSamples *findCalleeFunctionSamples(const CallBase &I) const;
495 const FunctionSamples *
496 findFunctionSamples(const Instruction &I) const override;
497 std::vector<const FunctionSamples *>
498 findIndirectCallFunctionSamples(const Instruction &I, uint64_t &Sum) const;
499 void findExternalInlineCandidate(CallBase *CB, const FunctionSamples *Samples,
500 DenseSet<GlobalValue::GUID> &InlinedGUIDs,
501 uint64_t Threshold);
502 // Attempt to promote indirect call and also inline the promoted call
503 bool tryPromoteAndInlineCandidate(
504 Function &F, InlineCandidate &Candidate, uint64_t SumOrigin,
505 uint64_t &Sum, SmallVector<CallBase *, 8> *InlinedCallSites = nullptr);
506
507 bool inlineHotFunctions(Function &F,
508 DenseSet<GlobalValue::GUID> &InlinedGUIDs);
509 std::optional<InlineCost> getExternalInlineAdvisorCost(CallBase &CB);
510 bool getExternalInlineAdvisorShouldInline(CallBase &CB);
511 InlineCost shouldInlineCandidate(InlineCandidate &Candidate);
512 bool getInlineCandidate(InlineCandidate *NewCandidate, CallBase *CB);
513 bool
514 tryInlineCandidate(InlineCandidate &Candidate,
515 SmallVector<CallBase *, 8> *InlinedCallSites = nullptr);
516 bool
517 inlineHotFunctionsWithPriority(Function &F,
518 DenseSet<GlobalValue::GUID> &InlinedGUIDs);
519 // Inline cold/small functions in addition to hot ones
520 bool shouldInlineColdCallee(CallBase &CallInst);
521 void emitOptimizationRemarksForInlineCandidates(
522 const SmallVectorImpl<CallBase *> &Candidates, const Function &F,
523 bool Hot);
524 void promoteMergeNotInlinedContextSamples(
525 MapVector<CallBase *, const FunctionSamples *> NonInlinedCallSites,
526 const Function &F);
527 std::vector<Function *> buildFunctionOrder(Module &M, LazyCallGraph &CG);
528 std::unique_ptr<ProfiledCallGraph> buildProfiledCallGraph(Module &M);
529 void generateMDProfMetadata(Function &F);
530 bool rejectHighStalenessProfile(Module &M, ProfileSummaryInfo *PSI,
531 const SampleProfileMap &Profiles);
532 void removePseudoProbeInstsDiscriminator(Module &M);
533
534 /// Map from function name to Function *. Used to find the function from
535 /// the function name. If the function name contains suffix, additional
536 /// entry is added to map from the stripped name to the function if there
537 /// is one-to-one mapping.
538 HashKeyMap<DenseMap, FunctionId, Function *> SymbolMap;
539
540 /// Map from function name to profile name generated by call-graph based
541 /// profile fuzzy matching(--salvage-unused-profile).
542 HashKeyMap<DenseMap, FunctionId, FunctionId> FuncNameToProfNameMap;
543
544 std::function<AssumptionCache &(Function &)> GetAC;
545 std::function<TargetTransformInfo &(Function &)> GetTTI;
546 std::function<const TargetLibraryInfo &(Function &)> GetTLI;
547 LazyCallGraph &CG;
548
549 /// Profile tracker for different context.
550 std::unique_ptr<SampleContextTracker> ContextTracker;
551
552 /// Flag indicating which LTO/ThinLTO phase the pass is invoked in.
553 ///
554 /// We need to know the LTO phase because for example in ThinLTOPrelink
555 /// phase, in annotation, we should not promote indirect calls. Instead,
556 /// we will mark GUIDs that needs to be annotated to the function.
557 const ThinOrFullLTOPhase LTOPhase;
558 const std::string AnnotatedPassName;
559
560 /// Profle Symbol list tells whether a function name appears in the binary
561 /// used to generate the current profile.
562 std::shared_ptr<ProfileSymbolList> PSL;
563
564 // Information recorded when we declined to inline a call site
565 // because we have determined it is too cold is accumulated for
566 // each callee function. Initially this is just the entry count.
567 struct NotInlinedProfileInfo {
568 uint64_t entryCount;
569 };
570 DenseMap<Function *, NotInlinedProfileInfo> notInlinedCallInfo;
571
572 // GUIDToFuncNameMap saves the mapping from GUID to the symbol name, for
573 // all the function symbols defined or declared in current module.
574 DenseMap<uint64_t, StringRef> GUIDToFuncNameMap;
575
576 // For symbol in profile symbol list, whether to regard their profiles
577 // to be accurate. It is mainly decided by existance of profile symbol
578 // list and -profile-accurate-for-symsinlist flag, but it can be
579 // overriden by -profile-sample-accurate or profile-sample-accurate
580 // attribute.
581 bool ProfAccForSymsInList;
582
583 bool DisableSampleProfileInlining;
584
585 bool UseFlattenedProfile;
586
587 // External inline advisor used to replay inline decision from remarks.
588 std::unique_ptr<InlineAdvisor> ExternalInlineAdvisor;
589
590 // A helper to implement the sample profile matching algorithm.
591 std::unique_ptr<SampleProfileMatcher> MatchingManager;
592
593private:
594 const char *getAnnotatedRemarkPassName() const {
595 return AnnotatedPassName.c_str();
596 }
597};
598} // end anonymous namespace
599
600namespace llvm {
601template <>
602inline bool SampleProfileInference<Function>::isExit(const BasicBlock *BB) {
603 return succ_empty(BB);
604}
605
606template <>
607inline void SampleProfileInference<Function>::findUnlikelyJumps(
608 const std::vector<const BasicBlockT *> &BasicBlocks,
609 BlockEdgeMap &Successors, FlowFunction &Func) {
610 for (auto &Jump : Func.Jumps) {
611 const auto *BB = BasicBlocks[Jump.Source];
612 const auto *Succ = BasicBlocks[Jump.Target];
613 const Instruction *TI = BB->getTerminator();
614 // Check if a block ends with InvokeInst and mark non-taken branch unlikely.
615 // In that case block Succ should be a landing pad
616 const auto &Succs = Successors[BB];
617 if (Succs.size() == 2 && Succs.back() == Succ) {
618 if (isa<InvokeInst>(Val: TI)) {
619 Jump.IsUnlikely = true;
620 }
621 }
622 const Instruction *SuccTI = Succ->getTerminator();
623 // Check if the target block contains UnreachableInst and mark it unlikely
624 if (SuccTI->getNumSuccessors() == 0) {
625 if (isa<UnreachableInst>(Val: SuccTI)) {
626 Jump.IsUnlikely = true;
627 }
628 }
629 }
630}
631
632template <>
633void SampleProfileLoaderBaseImpl<Function>::computeDominanceAndLoopInfo(
634 Function &F) {
635 DT.reset(p: new DominatorTree);
636 DT->recalculate(Func&: F);
637
638 PDT.reset(p: new PostDominatorTree(F));
639
640 LI.reset(p: new LoopInfo);
641 LI->analyze(DomTree: *DT);
642}
643} // namespace llvm
644
645ErrorOr<uint64_t> SampleProfileLoader::getInstWeight(const Instruction &Inst) {
646 if (FunctionSamples::ProfileIsProbeBased)
647 return getProbeWeight(Inst);
648
649 const DebugLoc &DLoc = Inst.getDebugLoc();
650 if (!DLoc)
651 return std::error_code();
652
653 // Ignore all intrinsics, phinodes and branch instructions.
654 // Branch and phinodes instruction usually contains debug info from sources
655 // outside of the residing basic block, thus we ignore them during annotation.
656 if (isa<UncondBrInst, CondBrInst, IntrinsicInst, PHINode>(Val: Inst))
657 return std::error_code();
658
659 // For non-CS profile, if a direct call/invoke instruction is inlined in
660 // profile (findCalleeFunctionSamples returns non-empty result), but not
661 // inlined here, it means that the inlined callsite has no sample, thus the
662 // call instruction should have 0 count.
663 // For CS profile, the callsite count of previously inlined callees is
664 // populated with the entry count of the callees.
665 if (!FunctionSamples::ProfileIsCS)
666 if (const auto *CB = dyn_cast<CallBase>(Val: &Inst))
667 if (!CB->isIndirectCall() && findCalleeFunctionSamples(I: *CB))
668 return 0;
669
670 return getInstWeightImpl(Inst);
671}
672
673/// Get the FunctionSamples for a call instruction.
674///
675/// The FunctionSamples of a call/invoke instruction \p Inst is the inlined
676/// instance in which that call instruction is calling to. It contains
677/// all samples that resides in the inlined instance. We first find the
678/// inlined instance in which the call instruction is from, then we
679/// traverse its children to find the callsite with the matching
680/// location.
681///
682/// \param Inst Call/Invoke instruction to query.
683///
684/// \returns The FunctionSamples pointer to the inlined instance.
685const FunctionSamples *
686SampleProfileLoader::findCalleeFunctionSamples(const CallBase &Inst) const {
687 const DILocation *DIL = Inst.getDebugLoc();
688 if (!DIL) {
689 return nullptr;
690 }
691
692 StringRef CalleeName;
693 if (Function *Callee = Inst.getCalledFunction())
694 CalleeName = Callee->getName();
695
696 if (FunctionSamples::ProfileIsCS)
697 return ContextTracker->getCalleeContextSamplesFor(Inst, CalleeName);
698
699 const FunctionSamples *FS = findFunctionSamples(I: Inst);
700 if (FS == nullptr)
701 return nullptr;
702
703 return FS->findFunctionSamplesAt(Loc: FunctionSamples::getCallSiteIdentifier(DIL),
704 CalleeName, Remapper: Reader->getRemapper(),
705 FuncNameToProfNameMap: &FuncNameToProfNameMap);
706}
707
708/// Returns a vector of FunctionSamples that are the indirect call targets
709/// of \p Inst. The vector is sorted by the total number of samples. Stores
710/// the total call count of the indirect call in \p Sum.
711std::vector<const FunctionSamples *>
712SampleProfileLoader::findIndirectCallFunctionSamples(
713 const Instruction &Inst, uint64_t &Sum) const {
714 const DILocation *DIL = Inst.getDebugLoc();
715 std::vector<const FunctionSamples *> R;
716
717 if (!DIL) {
718 return R;
719 }
720
721 auto FSCompare = [](const FunctionSamples *L, const FunctionSamples *R) {
722 assert(L && R && "Expect non-null FunctionSamples");
723 if (L->getHeadSamplesEstimate() != R->getHeadSamplesEstimate())
724 return L->getHeadSamplesEstimate() > R->getHeadSamplesEstimate();
725 return L->getGUID() < R->getGUID();
726 };
727
728 if (FunctionSamples::ProfileIsCS) {
729 auto CalleeSamples =
730 ContextTracker->getIndirectCalleeContextSamplesFor(DIL);
731 if (CalleeSamples.empty())
732 return R;
733
734 // For CSSPGO, we only use target context profile's entry count
735 // as that already includes both inlined callee and non-inlined ones..
736 Sum = 0;
737 for (const auto *const FS : CalleeSamples) {
738 Sum += FS->getHeadSamplesEstimate();
739 R.push_back(x: FS);
740 }
741 llvm::sort(C&: R, Comp: FSCompare);
742 return R;
743 }
744
745 const FunctionSamples *FS = findFunctionSamples(I: Inst);
746 if (FS == nullptr)
747 return R;
748
749 auto CallSite = FunctionSamples::getCallSiteIdentifier(DIL);
750 Sum = 0;
751 if (auto T = FS->findCallTargetMapAt(CallSite))
752 for (const auto &T_C : *T)
753 Sum += T_C.second;
754 if (const FunctionSamplesMap *M = FS->findFunctionSamplesMapAt(Loc: CallSite)) {
755 if (M->empty())
756 return R;
757 for (const auto &NameFS : *M) {
758 Sum += NameFS.second.getHeadSamplesEstimate();
759 R.push_back(x: &NameFS.second);
760 }
761 llvm::sort(C&: R, Comp: FSCompare);
762 }
763 return R;
764}
765
766const FunctionSamples *
767SampleProfileLoader::findFunctionSamples(const Instruction &Inst) const {
768 if (FunctionSamples::ProfileIsProbeBased) {
769 std::optional<PseudoProbe> Probe = extractProbe(Inst);
770 if (!Probe)
771 return nullptr;
772 }
773
774 const DILocation *DIL = Inst.getDebugLoc();
775 if (!DIL)
776 return Samples;
777
778 auto it = DILocation2SampleMap.try_emplace(Key: DIL,Args: nullptr);
779 if (it.second) {
780 if (FunctionSamples::ProfileIsCS)
781 it.first->second = ContextTracker->getContextSamplesFor(DIL);
782 else
783 it.first->second = Samples->findFunctionSamples(
784 DIL, Remapper: Reader->getRemapper(), FuncNameToProfNameMap: &FuncNameToProfNameMap);
785 }
786 return it.first->second;
787}
788
789/// Check whether the indirect call promotion history of \p Inst allows
790/// the promotion for \p Candidate.
791/// If the profile count for the promotion candidate \p Candidate is
792/// NOMORE_ICP_MAGICNUM, it means \p Candidate has already been promoted
793/// for \p Inst. If we already have at least MaxNumPromotions
794/// NOMORE_ICP_MAGICNUM count values in the value profile of \p Inst, we
795/// cannot promote for \p Inst anymore.
796static bool doesHistoryAllowICP(const Instruction &Inst, StringRef Candidate) {
797 uint64_t TotalCount = 0;
798 auto ValueData = getValueProfDataFromInst(Inst, ValueKind: IPVK_IndirectCallTarget,
799 MaxNumValueData: MaxNumPromotions, TotalC&: TotalCount, GetNoICPValue: true);
800 // No valid value profile so no promoted targets have been recorded
801 // before. Ok to do ICP.
802 if (ValueData.empty())
803 return true;
804
805 unsigned NumPromoted = 0;
806 for (const auto &V : ValueData) {
807 if (V.Count != NOMORE_ICP_MAGICNUM)
808 continue;
809
810 // If the promotion candidate has NOMORE_ICP_MAGICNUM count in the
811 // metadata, it means the candidate has been promoted for this
812 // indirect call.
813 if (V.Value == Function::getGUIDAssumingExternalLinkage(GlobalName: Candidate))
814 return false;
815 NumPromoted++;
816 // If already have MaxNumPromotions promotion, don't do it anymore.
817 if (NumPromoted == MaxNumPromotions)
818 return false;
819 }
820 return true;
821}
822
823/// Update indirect call target profile metadata for \p Inst.
824/// Usually \p Sum is the sum of counts of all the targets for \p Inst.
825/// If it is 0, it means updateIDTMetaData is used to mark a
826/// certain target to be promoted already. If it is not zero,
827/// we expect to use it to update the total count in the value profile.
828static void
829updateIDTMetaData(Instruction &Inst,
830 const SmallVectorImpl<InstrProfValueData> &CallTargets,
831 uint64_t Sum) {
832 // Bail out early if MaxNumPromotions is zero.
833 // This prevents allocating an array of zero length below.
834 //
835 // Note `updateIDTMetaData` is called in two places so check
836 // `MaxNumPromotions` inside it.
837 if (MaxNumPromotions == 0)
838 return;
839 // OldSum is the existing total count in the value profile data.
840 uint64_t OldSum = 0;
841 auto ValueData = getValueProfDataFromInst(Inst, ValueKind: IPVK_IndirectCallTarget,
842 MaxNumValueData: MaxNumPromotions, TotalC&: OldSum, GetNoICPValue: true);
843
844 DenseMap<uint64_t, uint64_t> ValueCountMap;
845 if (Sum == 0) {
846 assert((CallTargets.size() == 1 &&
847 CallTargets[0].Count == NOMORE_ICP_MAGICNUM) &&
848 "If sum is 0, assume only one element in CallTargets "
849 "with count being NOMORE_ICP_MAGICNUM");
850 // Initialize ValueCountMap with existing value profile data.
851 for (const auto &V : ValueData)
852 ValueCountMap[V.Value] = V.Count;
853 auto Pair =
854 ValueCountMap.try_emplace(Key: CallTargets[0].Value, Args: CallTargets[0].Count);
855 // If the target already exists in value profile, decrease the total
856 // count OldSum and reset the target's count to NOMORE_ICP_MAGICNUM.
857 if (!Pair.second) {
858 OldSum -= Pair.first->second;
859 Pair.first->second = NOMORE_ICP_MAGICNUM;
860 }
861 Sum = OldSum;
862 } else {
863 // Initialize ValueCountMap with existing NOMORE_ICP_MAGICNUM
864 // counts in the value profile.
865 for (const auto &V : ValueData) {
866 if (V.Count == NOMORE_ICP_MAGICNUM)
867 ValueCountMap[V.Value] = V.Count;
868 }
869
870 for (const auto &Data : CallTargets) {
871 auto Pair = ValueCountMap.try_emplace(Key: Data.Value, Args: Data.Count);
872 if (Pair.second)
873 continue;
874 // The target represented by Data.Value has already been promoted.
875 // Keep the count as NOMORE_ICP_MAGICNUM in the profile and decrease
876 // Sum by Data.Count.
877 assert(Sum >= Data.Count && "Sum should never be less than Data.Count");
878 Sum -= Data.Count;
879 }
880 }
881
882 SmallVector<InstrProfValueData, 8> NewCallTargets;
883 for (const auto &ValueCount : ValueCountMap) {
884 NewCallTargets.emplace_back(
885 Args: InstrProfValueData{.Value: ValueCount.first, .Count: ValueCount.second});
886 }
887
888 llvm::sort(C&: NewCallTargets,
889 Comp: [](const InstrProfValueData &L, const InstrProfValueData &R) {
890 return std::tie(args: L.Count, args: L.Value) > std::tie(args: R.Count, args: R.Value);
891 });
892
893 uint32_t MaxMDCount =
894 std::min(a: NewCallTargets.size(), b: static_cast<size_t>(MaxNumPromotions));
895 annotateValueSite(M&: *Inst.getParent()->getParent()->getParent(), Inst,
896 VDs: NewCallTargets, Sum, ValueKind: IPVK_IndirectCallTarget, MaxMDCount);
897}
898
899/// Attempt to promote indirect call and also inline the promoted call.
900///
901/// \param F Caller function.
902/// \param Candidate ICP and inline candidate.
903/// \param SumOrigin Original sum of target counts for indirect call before
904/// promoting given candidate.
905/// \param Sum Prorated sum of remaining target counts for indirect call
906/// after promoting given candidate.
907/// \param InlinedCallSite Output vector for new call sites exposed after
908/// inlining.
909bool SampleProfileLoader::tryPromoteAndInlineCandidate(
910 Function &F, InlineCandidate &Candidate, uint64_t SumOrigin, uint64_t &Sum,
911 SmallVector<CallBase *, 8> *InlinedCallSite) {
912 // Bail out early if sample-loader inliner is disabled.
913 if (DisableSampleProfileInlining)
914 return false;
915
916 // Bail out early if MaxNumPromotions is zero.
917 // This prevents allocating an array of zero length in callees below.
918 if (MaxNumPromotions == 0)
919 return false;
920 auto CalleeFunctionName = Candidate.CalleeSamples->getFunction();
921 auto R = SymbolMap.find(Key: CalleeFunctionName);
922 if (R == SymbolMap.end() || !R->second)
923 return false;
924
925 auto &CI = *Candidate.CallInstr;
926 if (!doesHistoryAllowICP(Inst: CI, Candidate: R->second->getName()))
927 return false;
928
929 const char *Reason = "Callee function not available";
930 // R->getValue() != &F is to prevent promoting a recursive call.
931 // If it is a recursive call, we do not inline it as it could bloat
932 // the code exponentially. There is way to better handle this, e.g.
933 // clone the caller first, and inline the cloned caller if it is
934 // recursive. As llvm does not inline recursive calls, we will
935 // simply ignore it instead of handling it explicitly.
936 if (!R->second->isDeclaration() && R->second->getSubprogram() &&
937 R->second->hasFnAttribute(Kind: "use-sample-profile") &&
938 R->second != &F && isLegalToPromote(CB: CI, Callee: R->second, FailureReason: &Reason)) {
939 // For promoted target, set its value with NOMORE_ICP_MAGICNUM count
940 // in the value profile metadata so the target won't be promoted again.
941 SmallVector<InstrProfValueData, 1> SortedCallTargets = {InstrProfValueData{
942 .Value: Function::getGUIDAssumingExternalLinkage(GlobalName: R->second->getName()),
943 .Count: NOMORE_ICP_MAGICNUM}};
944 updateIDTMetaData(Inst&: CI, CallTargets: SortedCallTargets, Sum: 0);
945
946 auto *DI = &pgo::promoteIndirectCall(
947 CB&: CI, F: R->second, Count: Candidate.CallsiteCount, TotalCount: Sum, AttachProfToDirectCall: false, ORE);
948 if (DI) {
949 Sum -= Candidate.CallsiteCount;
950 // Do not prorate the indirect callsite distribution since the original
951 // distribution will be used to scale down non-promoted profile target
952 // counts later. By doing this we lose track of the real callsite count
953 // for the leftover indirect callsite as a trade off for accurate call
954 // target counts.
955 // TODO: Ideally we would have two separate factors, one for call site
956 // counts and one is used to prorate call target counts.
957 // Do not update the promoted direct callsite distribution at this
958 // point since the original distribution combined with the callee profile
959 // will be used to prorate callsites from the callee if inlined. Once not
960 // inlined, the direct callsite distribution should be prorated so that
961 // the it will reflect the real callsite counts.
962 Candidate.CallInstr = DI;
963 if (isa<CallInst>(Val: DI) || isa<InvokeInst>(Val: DI)) {
964 bool Inlined = tryInlineCandidate(Candidate, InlinedCallSites: InlinedCallSite);
965 if (!Inlined) {
966 // Prorate the direct callsite distribution so that it reflects real
967 // callsite counts.
968 setProbeDistributionFactor(
969 Inst&: *DI, Factor: static_cast<float>(Candidate.CallsiteCount) / SumOrigin);
970 }
971 return Inlined;
972 }
973 }
974 } else {
975 LLVM_DEBUG(dbgs() << "\nFailed to promote indirect call to "
976 << FunctionSamples::getCanonicalFnName(
977 Candidate.CallInstr->getName())<< " because "
978 << Reason << "\n");
979 }
980 return false;
981}
982
983bool SampleProfileLoader::shouldInlineColdCallee(CallBase &CallInst) {
984 if (!ProfileSizeInline)
985 return false;
986
987 Function *Callee = CallInst.getCalledFunction();
988 if (Callee == nullptr)
989 return false;
990
991 InlineCost Cost = getInlineCost(Call&: CallInst, Params: getInlineParams(), CalleeTTI&: GetTTI(*Callee),
992 GetAssumptionCache: GetAC, GetTLI);
993
994 if (Cost.isNever())
995 return false;
996
997 if (Cost.isAlways())
998 return true;
999
1000 return Cost.getCost() <= SampleColdCallSiteThreshold;
1001}
1002
1003void SampleProfileLoader::emitOptimizationRemarksForInlineCandidates(
1004 const SmallVectorImpl<CallBase *> &Candidates, const Function &F,
1005 bool Hot) {
1006 for (auto *I : Candidates) {
1007 Function *CalledFunction = I->getCalledFunction();
1008 if (CalledFunction) {
1009 ORE->emit(OptDiag: OptimizationRemarkAnalysis(getAnnotatedRemarkPassName(),
1010 "InlineAttempt", I->getDebugLoc(),
1011 I->getParent())
1012 << "previous inlining reattempted for "
1013 << (Hot ? "hotness: '" : "size: '")
1014 << ore::NV("Callee", CalledFunction) << "' into '"
1015 << ore::NV("Caller", &F) << "'");
1016 }
1017 }
1018}
1019
1020void SampleProfileLoader::findExternalInlineCandidate(
1021 CallBase *CB, const FunctionSamples *Samples,
1022 DenseSet<GlobalValue::GUID> &InlinedGUIDs, uint64_t Threshold) {
1023
1024 // If ExternalInlineAdvisor(ReplayInlineAdvisor) wants to inline an external
1025 // function make sure it's imported
1026 if (CB && getExternalInlineAdvisorShouldInline(CB&: *CB)) {
1027 // Samples may not exist for replayed function, if so
1028 // just add the direct GUID and move on
1029 if (!Samples) {
1030 InlinedGUIDs.insert(V: Function::getGUIDAssumingExternalLinkage(
1031 GlobalName: CB->getCalledFunction()->getName()));
1032 return;
1033 }
1034 // Otherwise, drop the threshold to import everything that we can
1035 Threshold = 0;
1036 }
1037
1038 // In some rare cases, call instruction could be changed after being pushed
1039 // into inline candidate queue, this is because earlier inlining may expose
1040 // constant propagation which can change indirect call to direct call. When
1041 // this happens, we may fail to find matching function samples for the
1042 // candidate later, even if a match was found when the candidate was enqueued.
1043 if (!Samples)
1044 return;
1045
1046 // For AutoFDO profile, retrieve candidate profiles by walking over
1047 // the nested inlinee profiles.
1048 if (!FunctionSamples::ProfileIsCS) {
1049 // Set threshold to zero to honor pre-inliner decision.
1050 if (UsePreInlinerDecision)
1051 Threshold = 0;
1052 Samples->findInlinedFunctions(S&: InlinedGUIDs, SymbolMap, Threshold);
1053 return;
1054 }
1055
1056 ContextTrieNode *Caller = ContextTracker->getContextNodeForProfile(FSamples: Samples);
1057 std::queue<ContextTrieNode *> CalleeList;
1058 CalleeList.push(x: Caller);
1059 while (!CalleeList.empty()) {
1060 ContextTrieNode *Node = CalleeList.front();
1061 CalleeList.pop();
1062 FunctionSamples *CalleeSample = Node->getFunctionSamples();
1063 // For CSSPGO profile, retrieve candidate profile by walking over the
1064 // trie built for context profile. Note that also take call targets
1065 // even if callee doesn't have a corresponding context profile.
1066 if (!CalleeSample)
1067 continue;
1068
1069 // If pre-inliner decision is used, honor that for importing as well.
1070 bool PreInline =
1071 UsePreInlinerDecision &&
1072 CalleeSample->getContext().hasAttribute(A: ContextShouldBeInlined);
1073 if (!PreInline && CalleeSample->getHeadSamplesEstimate() < Threshold)
1074 continue;
1075
1076 Function *Func = SymbolMap.lookup(Key: CalleeSample->getFunction());
1077 // Add to the import list only when it's defined out of module.
1078 if (!Func || Func->isDeclaration())
1079 InlinedGUIDs.insert(V: CalleeSample->getGUID());
1080
1081 // Import hot CallTargets, which may not be available in IR because full
1082 // profile annotation cannot be done until backend compilation in ThinLTO.
1083 for (const auto &BS : CalleeSample->getBodySamples())
1084 for (const auto &TS : BS.second.getCallTargets())
1085 if (TS.second > Threshold) {
1086 const Function *Callee = SymbolMap.lookup(Key: TS.first);
1087 if (!Callee || Callee->isDeclaration())
1088 InlinedGUIDs.insert(V: TS.first.getHashCode());
1089 }
1090
1091 // Import hot child context profile associted with callees. Note that this
1092 // may have some overlap with the call target loop above, but doing this
1093 // based child context profile again effectively allow us to use the max of
1094 // entry count and call target count to determine importing.
1095 for (auto &Child : Node->getAllChildContext()) {
1096 ContextTrieNode *CalleeNode = &Child.second;
1097 CalleeList.push(x: CalleeNode);
1098 }
1099 }
1100}
1101
1102/// Iteratively inline hot callsites of a function.
1103///
1104/// Iteratively traverse all callsites of the function \p F, so as to
1105/// find out callsites with corresponding inline instances.
1106///
1107/// For such callsites,
1108/// - If it is hot enough, inline the callsites and adds callsites of the callee
1109/// into the caller. If the call is an indirect call, first promote
1110/// it to direct call. Each indirect call is limited with a single target.
1111///
1112/// - If a callsite is not inlined, merge the its profile to the outline
1113/// version (if --sample-profile-merge-inlinee is true), or scale the
1114/// counters of standalone function based on the profile of inlined
1115/// instances (if --sample-profile-merge-inlinee is false).
1116///
1117/// Later passes may consume the updated profiles.
1118///
1119/// \param F function to perform iterative inlining.
1120/// \param InlinedGUIDs a set to be updated to include all GUIDs that are
1121/// inlined in the profiled binary.
1122///
1123/// \returns True if there is any inline happened.
1124bool SampleProfileLoader::inlineHotFunctions(
1125 Function &F, DenseSet<GlobalValue::GUID> &InlinedGUIDs) {
1126 // ProfAccForSymsInList is used in callsiteIsHot. The assertion makes sure
1127 // Profile symbol list is ignored when profile-sample-accurate is on.
1128 assert((!ProfAccForSymsInList ||
1129 (!ProfileSampleAccurate &&
1130 !F.hasFnAttribute("profile-sample-accurate"))) &&
1131 "ProfAccForSymsInList should be false when profile-sample-accurate "
1132 "is enabled");
1133
1134 MapVector<CallBase *, const FunctionSamples *> LocalNotInlinedCallSites;
1135 bool Changed = false;
1136 bool LocalChanged = true;
1137 while (LocalChanged) {
1138 LocalChanged = false;
1139 SmallVector<CallBase *, 10> CIS;
1140 for (auto &BB : F) {
1141 bool Hot = false;
1142 SmallVector<CallBase *, 10> AllCandidates;
1143 SmallVector<CallBase *, 10> ColdCandidates;
1144 for (auto &I : BB) {
1145 const FunctionSamples *FS = nullptr;
1146 if (auto *CB = dyn_cast<CallBase>(Val: &I)) {
1147 if (!isa<IntrinsicInst>(Val: I)) {
1148 if ((FS = findCalleeFunctionSamples(Inst: *CB))) {
1149 assert((!FunctionSamples::UseMD5 || FS->GUIDToFuncNameMap) &&
1150 "GUIDToFuncNameMap has to be populated");
1151 AllCandidates.push_back(Elt: CB);
1152 if (FS->getHeadSamplesEstimate() > 0 ||
1153 FunctionSamples::ProfileIsCS)
1154 LocalNotInlinedCallSites.insert(KV: {CB, FS});
1155 if (callsiteIsHot(CallsiteFS: FS, PSI, ProfAccForSymsInList))
1156 Hot = true;
1157 else if (shouldInlineColdCallee(CallInst&: *CB))
1158 ColdCandidates.push_back(Elt: CB);
1159 } else if (getExternalInlineAdvisorShouldInline(CB&: *CB)) {
1160 AllCandidates.push_back(Elt: CB);
1161 }
1162 }
1163 }
1164 }
1165 if (Hot || ExternalInlineAdvisor) {
1166 CIS.insert(I: CIS.begin(), From: AllCandidates.begin(), To: AllCandidates.end());
1167 emitOptimizationRemarksForInlineCandidates(Candidates: AllCandidates, F, Hot: true);
1168 } else {
1169 CIS.insert(I: CIS.begin(), From: ColdCandidates.begin(), To: ColdCandidates.end());
1170 emitOptimizationRemarksForInlineCandidates(Candidates: ColdCandidates, F, Hot: false);
1171 }
1172 }
1173 for (CallBase *I : CIS) {
1174 Function *CalledFunction = I->getCalledFunction();
1175 InlineCandidate Candidate = {.CallInstr: I, .CalleeSamples: LocalNotInlinedCallSites.lookup(Key: I),
1176 .CallsiteCount: 0 /* dummy count */,
1177 .CallsiteDistribution: 1.0 /* dummy distribution factor */};
1178 // Do not inline recursive calls.
1179 if (CalledFunction == &F)
1180 continue;
1181 if (I->isIndirectCall()) {
1182 uint64_t Sum;
1183 for (const auto *FS : findIndirectCallFunctionSamples(Inst: *I, Sum)) {
1184 uint64_t SumOrigin = Sum;
1185 if (LTOPhase == ThinOrFullLTOPhase::ThinLTOPreLink) {
1186 findExternalInlineCandidate(CB: I, Samples: FS, InlinedGUIDs,
1187 Threshold: PSI->getOrCompHotCountThreshold());
1188 continue;
1189 }
1190 if (!callsiteIsHot(CallsiteFS: FS, PSI, ProfAccForSymsInList))
1191 continue;
1192
1193 Candidate = {.CallInstr: I, .CalleeSamples: FS, .CallsiteCount: FS->getHeadSamplesEstimate(), .CallsiteDistribution: 1.0};
1194 if (tryPromoteAndInlineCandidate(F, Candidate, SumOrigin, Sum)) {
1195 LocalNotInlinedCallSites.erase(Key: I);
1196 LocalChanged = true;
1197 }
1198 }
1199 } else if (CalledFunction && CalledFunction->getSubprogram() &&
1200 !CalledFunction->isDeclaration()) {
1201 if (tryInlineCandidate(Candidate)) {
1202 LocalNotInlinedCallSites.erase(Key: I);
1203 LocalChanged = true;
1204 }
1205 } else if (LTOPhase == ThinOrFullLTOPhase::ThinLTOPreLink) {
1206 findExternalInlineCandidate(CB: I, Samples: findCalleeFunctionSamples(Inst: *I),
1207 InlinedGUIDs,
1208 Threshold: PSI->getOrCompHotCountThreshold());
1209 }
1210 }
1211 Changed |= LocalChanged;
1212 }
1213
1214 // For CS profile, profile for not inlined context will be merged when
1215 // base profile is being retrieved.
1216 if (!FunctionSamples::ProfileIsCS)
1217 promoteMergeNotInlinedContextSamples(NonInlinedCallSites: LocalNotInlinedCallSites, F);
1218 return Changed;
1219}
1220
1221bool SampleProfileLoader::tryInlineCandidate(
1222 InlineCandidate &Candidate, SmallVector<CallBase *, 8> *InlinedCallSites) {
1223 // Do not attempt to inline a candidate if
1224 // --disable-sample-loader-inlining is true.
1225 if (DisableSampleProfileInlining)
1226 return false;
1227
1228 CallBase &CB = *Candidate.CallInstr;
1229 Function *CalledFunction = CB.getCalledFunction();
1230 assert(CalledFunction && "Expect a callee with definition");
1231 DebugLoc DLoc = CB.getDebugLoc();
1232 BasicBlock *BB = CB.getParent();
1233
1234 InlineCost Cost = shouldInlineCandidate(Candidate);
1235 if (Cost.isNever()) {
1236 ORE->emit(OptDiag: OptimizationRemarkAnalysis(getAnnotatedRemarkPassName(),
1237 "InlineFail", DLoc, BB)
1238 << "incompatible inlining");
1239 return false;
1240 }
1241
1242 if (!Cost)
1243 return false;
1244
1245 InlineFunctionInfo IFI(GetAC);
1246 IFI.UpdateProfile = false;
1247 InlineResult IR = InlineFunction(CB, IFI,
1248 /*MergeAttributes=*/true);
1249 if (!IR.isSuccess())
1250 return false;
1251
1252 // The call to InlineFunction erases I, so we can't pass it here.
1253 emitInlinedIntoBasedOnCost(ORE&: *ORE, DLoc, Block: BB, Callee: *CalledFunction, Caller: *BB->getParent(),
1254 IC: Cost, ForProfileContext: true, PassName: getAnnotatedRemarkPassName());
1255
1256 // Now populate the list of newly exposed call sites.
1257 if (InlinedCallSites) {
1258 InlinedCallSites->clear();
1259 llvm::append_range(C&: *InlinedCallSites, R&: IFI.InlinedCallSites);
1260 }
1261
1262 if (FunctionSamples::ProfileIsCS)
1263 ContextTracker->markContextSamplesInlined(InlinedSamples: Candidate.CalleeSamples);
1264 ++NumCSInlined;
1265
1266 // Prorate inlined probes for a duplicated inlining callsite which probably
1267 // has a distribution less than 100%. Samples for an inlinee should be
1268 // distributed among the copies of the original callsite based on each
1269 // callsite's distribution factor for counts accuracy. Note that an inlined
1270 // probe may come with its own distribution factor if it has been duplicated
1271 // in the inlinee body. The two factor are multiplied to reflect the
1272 // aggregation of duplication.
1273 if (Candidate.CallsiteDistribution < 1) {
1274 for (auto &I : IFI.InlinedCallSites) {
1275 if (std::optional<PseudoProbe> Probe = extractProbe(Inst: *I))
1276 setProbeDistributionFactor(Inst&: *I, Factor: Probe->Factor *
1277 Candidate.CallsiteDistribution);
1278 }
1279 NumDuplicatedInlinesite++;
1280 }
1281
1282 return true;
1283}
1284
1285bool SampleProfileLoader::getInlineCandidate(InlineCandidate *NewCandidate,
1286 CallBase *CB) {
1287 assert(CB && "Expect non-null call instruction");
1288
1289 if (isa<IntrinsicInst>(Val: CB))
1290 return false;
1291
1292 // Find the callee's profile. For indirect call, find hottest target profile.
1293 const FunctionSamples *CalleeSamples = findCalleeFunctionSamples(Inst: *CB);
1294 // If ExternalInlineAdvisor wants to inline this site, do so even
1295 // if Samples are not present.
1296 if (!CalleeSamples && !getExternalInlineAdvisorShouldInline(CB&: *CB))
1297 return false;
1298
1299 float Factor = 1.0;
1300 if (std::optional<PseudoProbe> Probe = extractProbe(Inst: *CB))
1301 Factor = Probe->Factor;
1302
1303 uint64_t CallsiteCount =
1304 CalleeSamples ? CalleeSamples->getHeadSamplesEstimate() * Factor : 0;
1305 *NewCandidate = {.CallInstr: CB, .CalleeSamples: CalleeSamples, .CallsiteCount: CallsiteCount, .CallsiteDistribution: Factor};
1306 return true;
1307}
1308
1309std::optional<InlineCost>
1310SampleProfileLoader::getExternalInlineAdvisorCost(CallBase &CB) {
1311 std::unique_ptr<InlineAdvice> Advice = nullptr;
1312 if (ExternalInlineAdvisor) {
1313 Advice = ExternalInlineAdvisor->getAdvice(CB);
1314 if (Advice) {
1315 if (!Advice->isInliningRecommended()) {
1316 Advice->recordUnattemptedInlining();
1317 return InlineCost::getNever(Reason: "not previously inlined");
1318 }
1319 Advice->recordInlining();
1320 return InlineCost::getAlways(Reason: "previously inlined");
1321 }
1322 }
1323
1324 return {};
1325}
1326
1327bool SampleProfileLoader::getExternalInlineAdvisorShouldInline(CallBase &CB) {
1328 std::optional<InlineCost> Cost = getExternalInlineAdvisorCost(CB);
1329 return Cost ? !!*Cost : false;
1330}
1331
1332InlineCost
1333SampleProfileLoader::shouldInlineCandidate(InlineCandidate &Candidate) {
1334 if (std::optional<InlineCost> ReplayCost =
1335 getExternalInlineAdvisorCost(CB&: *Candidate.CallInstr))
1336 return *ReplayCost;
1337 // Adjust threshold based on call site hotness, only do this for callsite
1338 // prioritized inliner because otherwise cost-benefit check is done earlier.
1339 int SampleThreshold = SampleColdCallSiteThreshold;
1340 if (CallsitePrioritizedInline) {
1341 if (Candidate.CallsiteCount > PSI->getHotCountThreshold())
1342 SampleThreshold = SampleHotCallSiteThreshold;
1343 else if (!ProfileSizeInline)
1344 return InlineCost::getNever(Reason: "cold callsite");
1345 }
1346
1347 Function *Callee = Candidate.CallInstr->getCalledFunction();
1348 assert(Callee && "Expect a definition for inline candidate of direct call");
1349
1350 InlineParams Params = getInlineParams();
1351 // We will ignore the threshold from inline cost, so always get full cost.
1352 Params.ComputeFullInlineCost = true;
1353 Params.AllowRecursiveCall = AllowRecursiveInline;
1354 // Checks if there is anything in the reachable portion of the callee at
1355 // this callsite that makes this inlining potentially illegal. Need to
1356 // set ComputeFullInlineCost, otherwise getInlineCost may return early
1357 // when cost exceeds threshold without checking all IRs in the callee.
1358 // The acutal cost does not matter because we only checks isNever() to
1359 // see if it is legal to inline the callsite.
1360 InlineCost Cost = getInlineCost(Call&: *Candidate.CallInstr, Callee, Params,
1361 CalleeTTI&: GetTTI(*Callee), GetAssumptionCache: GetAC, GetTLI);
1362
1363 // Honor always inline and never inline from call analyzer
1364 if (Cost.isNever() || Cost.isAlways())
1365 return Cost;
1366
1367 // With CSSPGO, the preinliner in llvm-profgen can estimate global inline
1368 // decisions based on hotness as well as accurate function byte sizes for
1369 // given context using function/inlinee sizes from previous build. It
1370 // stores the decision in profile, and also adjust/merge context profile
1371 // aiming at better context-sensitive post-inline profile quality, assuming
1372 // all inline decision estimates are going to be honored by compiler. Here
1373 // we replay that inline decision under `sample-profile-use-preinliner`.
1374 // Note that we don't need to handle negative decision from preinliner as
1375 // context profile for not inlined calls are merged by preinliner already.
1376 if (UsePreInlinerDecision && Candidate.CalleeSamples) {
1377 // Once two node are merged due to promotion, we're losing some context
1378 // so the original context-sensitive preinliner decision should be ignored
1379 // for SyntheticContext.
1380 SampleContext &Context = Candidate.CalleeSamples->getContext();
1381 if (!Context.hasState(S: SyntheticContext) &&
1382 Context.hasAttribute(A: ContextShouldBeInlined))
1383 return InlineCost::getAlways(Reason: "preinliner");
1384 }
1385
1386 // For old FDO inliner, we inline the call site if it is below hot threshold,
1387 // even if the function is hot based on sample profile data. This is to
1388 // prevent huge functions from being inlined.
1389 if (!CallsitePrioritizedInline) {
1390 return InlineCost::get(Cost: Cost.getCost(), Threshold: SampleHotCallSiteThreshold);
1391 }
1392
1393 // Otherwise only use the cost from call analyzer, but overwite threshold with
1394 // Sample PGO threshold.
1395 return InlineCost::get(Cost: Cost.getCost(), Threshold: SampleThreshold);
1396}
1397
1398bool SampleProfileLoader::inlineHotFunctionsWithPriority(
1399 Function &F, DenseSet<GlobalValue::GUID> &InlinedGUIDs) {
1400 // ProfAccForSymsInList is used in callsiteIsHot. The assertion makes sure
1401 // Profile symbol list is ignored when profile-sample-accurate is on.
1402 assert((!ProfAccForSymsInList ||
1403 (!ProfileSampleAccurate &&
1404 !F.hasFnAttribute("profile-sample-accurate"))) &&
1405 "ProfAccForSymsInList should be false when profile-sample-accurate "
1406 "is enabled");
1407
1408 // Populating worklist with initial call sites from root inliner, along
1409 // with call site weights.
1410 CandidateQueue CQueue;
1411 InlineCandidate NewCandidate;
1412 for (auto &BB : F) {
1413 for (auto &I : BB) {
1414 auto *CB = dyn_cast<CallBase>(Val: &I);
1415 if (!CB)
1416 continue;
1417 if (getInlineCandidate(NewCandidate: &NewCandidate, CB))
1418 CQueue.push(x: NewCandidate);
1419 }
1420 }
1421
1422 // Cap the size growth from profile guided inlining. This is needed even
1423 // though cost of each inline candidate already accounts for callee size,
1424 // because with top-down inlining, we can grow inliner size significantly
1425 // with large number of smaller inlinees each pass the cost check.
1426 assert(ProfileInlineLimitMax >= ProfileInlineLimitMin &&
1427 "Max inline size limit should not be smaller than min inline size "
1428 "limit.");
1429 unsigned SizeLimit = F.getInstructionCount() * ProfileInlineGrowthLimit;
1430 SizeLimit = std::min(a: SizeLimit, b: (unsigned)ProfileInlineLimitMax);
1431 SizeLimit = std::max(a: SizeLimit, b: (unsigned)ProfileInlineLimitMin);
1432 if (ExternalInlineAdvisor)
1433 SizeLimit = std::numeric_limits<unsigned>::max();
1434
1435 MapVector<CallBase *, const FunctionSamples *> LocalNotInlinedCallSites;
1436
1437 // Perform iterative BFS call site prioritized inlining
1438 bool Changed = false;
1439 while (!CQueue.empty() && F.getInstructionCount() < SizeLimit) {
1440 InlineCandidate Candidate = CQueue.top();
1441 CQueue.pop();
1442 CallBase *I = Candidate.CallInstr;
1443 Function *CalledFunction = I->getCalledFunction();
1444
1445 if (CalledFunction == &F)
1446 continue;
1447 if (I->isIndirectCall()) {
1448 uint64_t Sum = 0;
1449 auto CalleeSamples = findIndirectCallFunctionSamples(Inst: *I, Sum);
1450 uint64_t SumOrigin = Sum;
1451 Sum *= Candidate.CallsiteDistribution;
1452 unsigned ICPCount = 0;
1453 for (const auto *FS : CalleeSamples) {
1454 // TODO: Consider disable pre-lTO ICP for MonoLTO as well
1455 if (LTOPhase == ThinOrFullLTOPhase::ThinLTOPreLink) {
1456 findExternalInlineCandidate(CB: I, Samples: FS, InlinedGUIDs,
1457 Threshold: PSI->getOrCompHotCountThreshold());
1458 continue;
1459 }
1460 uint64_t EntryCountDistributed =
1461 FS->getHeadSamplesEstimate() * Candidate.CallsiteDistribution;
1462 // In addition to regular inline cost check, we also need to make sure
1463 // ICP isn't introducing excessive speculative checks even if individual
1464 // target looks beneficial to promote and inline. That means we should
1465 // only do ICP when there's a small number dominant targets.
1466 if (ICPCount >= ProfileICPRelativeHotnessSkip &&
1467 EntryCountDistributed * 100 < SumOrigin * ProfileICPRelativeHotness)
1468 break;
1469 // TODO: Fix CallAnalyzer to handle all indirect calls.
1470 // For indirect call, we don't run CallAnalyzer to get InlineCost
1471 // before actual inlining. This is because we could see two different
1472 // types from the same definition, which makes CallAnalyzer choke as
1473 // it's expecting matching parameter type on both caller and callee
1474 // side. See example from PR18962 for the triggering cases (the bug was
1475 // fixed, but we generate different types).
1476 if (!PSI->isHotCount(C: EntryCountDistributed))
1477 break;
1478 SmallVector<CallBase *, 8> InlinedCallSites;
1479 // Attach function profile for promoted indirect callee, and update
1480 // call site count for the promoted inline candidate too.
1481 Candidate = {.CallInstr: I, .CalleeSamples: FS, .CallsiteCount: EntryCountDistributed,
1482 .CallsiteDistribution: Candidate.CallsiteDistribution};
1483 if (tryPromoteAndInlineCandidate(F, Candidate, SumOrigin, Sum,
1484 InlinedCallSite: &InlinedCallSites)) {
1485 for (auto *CB : InlinedCallSites) {
1486 if (getInlineCandidate(NewCandidate: &NewCandidate, CB))
1487 CQueue.emplace(args&: NewCandidate);
1488 }
1489 ICPCount++;
1490 Changed = true;
1491 } else if (!ContextTracker) {
1492 LocalNotInlinedCallSites.insert(KV: {I, FS});
1493 }
1494 }
1495 } else if (CalledFunction && CalledFunction->getSubprogram() &&
1496 !CalledFunction->isDeclaration()) {
1497 SmallVector<CallBase *, 8> InlinedCallSites;
1498 if (tryInlineCandidate(Candidate, InlinedCallSites: &InlinedCallSites)) {
1499 for (auto *CB : InlinedCallSites) {
1500 if (getInlineCandidate(NewCandidate: &NewCandidate, CB))
1501 CQueue.emplace(args&: NewCandidate);
1502 }
1503 Changed = true;
1504 } else if (!ContextTracker) {
1505 LocalNotInlinedCallSites.insert(KV: {I, Candidate.CalleeSamples});
1506 }
1507 } else if (LTOPhase == ThinOrFullLTOPhase::ThinLTOPreLink) {
1508 findExternalInlineCandidate(CB: I, Samples: findCalleeFunctionSamples(Inst: *I),
1509 InlinedGUIDs,
1510 Threshold: PSI->getOrCompHotCountThreshold());
1511 }
1512 }
1513
1514 if (!CQueue.empty()) {
1515 if (SizeLimit == (unsigned)ProfileInlineLimitMax)
1516 ++NumCSInlinedHitMaxLimit;
1517 else if (SizeLimit == (unsigned)ProfileInlineLimitMin)
1518 ++NumCSInlinedHitMinLimit;
1519 else
1520 ++NumCSInlinedHitGrowthLimit;
1521 }
1522
1523 // For CS profile, profile for not inlined context will be merged when
1524 // base profile is being retrieved.
1525 if (!FunctionSamples::ProfileIsCS)
1526 promoteMergeNotInlinedContextSamples(NonInlinedCallSites: LocalNotInlinedCallSites, F);
1527 return Changed;
1528}
1529
1530void SampleProfileLoader::promoteMergeNotInlinedContextSamples(
1531 MapVector<CallBase *, const FunctionSamples *> NonInlinedCallSites,
1532 const Function &F) {
1533 // Accumulate not inlined callsite information into notInlinedSamples
1534 for (const auto &Pair : NonInlinedCallSites) {
1535 CallBase *I = Pair.first;
1536 Function *Callee = I->getCalledFunction();
1537 if (!Callee || Callee->isDeclaration())
1538 continue;
1539
1540 ORE->emit(
1541 OptDiag: OptimizationRemarkAnalysis(getAnnotatedRemarkPassName(), "NotInline",
1542 I->getDebugLoc(), I->getParent())
1543 << "previous inlining not repeated: '" << ore::NV("Callee", Callee)
1544 << "' into '" << ore::NV("Caller", &F) << "'");
1545
1546 ++NumCSNotInlined;
1547 const FunctionSamples *FS = Pair.second;
1548 if (FS->getTotalSamples() == 0 && FS->getHeadSamplesEstimate() == 0) {
1549 continue;
1550 }
1551
1552 // Do not merge a context that is already duplicated into the base profile.
1553 if (FS->getContext().hasAttribute(A: sampleprof::ContextDuplicatedIntoBase))
1554 continue;
1555
1556 if (ProfileMergeInlinee) {
1557 // A function call can be replicated by optimizations like callsite
1558 // splitting or jump threading and the replicates end up sharing the
1559 // sample nested callee profile instead of slicing the original
1560 // inlinee's profile. We want to do merge exactly once by filtering out
1561 // callee profiles with a non-zero head sample count.
1562 if (FS->getHeadSamples() == 0) {
1563 // Use entry samples as head samples during the merge, as inlinees
1564 // don't have head samples.
1565 const_cast<FunctionSamples *>(FS)->addHeadSamples(
1566 Num: FS->getHeadSamplesEstimate());
1567
1568 // Note that we have to do the merge right after processing function.
1569 // This allows OutlineFS's profile to be used for annotation during
1570 // top-down processing of functions' annotation.
1571 FunctionSamples *OutlineFS = Reader->getSamplesFor(F: *Callee);
1572 // If outlined function does not exist in the profile, add it to a
1573 // separate map so that it does not rehash the original profile.
1574 if (!OutlineFS)
1575 OutlineFS = &OutlineFunctionSamples[
1576 FunctionId(FunctionSamples::getCanonicalFnName(FnName: Callee->getName()))];
1577 OutlineFS->merge(Other: *FS, Weight: 1);
1578 // Set outlined profile to be synthetic to not bias the inliner.
1579 OutlineFS->setContextSynthetic();
1580 }
1581 } else {
1582 auto pair =
1583 notInlinedCallInfo.try_emplace(Key: Callee, Args: NotInlinedProfileInfo{.entryCount: 0});
1584 pair.first->second.entryCount += FS->getHeadSamplesEstimate();
1585 }
1586 }
1587}
1588
1589/// Returns the sorted CallTargetMap \p M by count in descending order.
1590static SmallVector<InstrProfValueData, 2>
1591GetSortedValueDataFromCallTargets(const SampleRecord::CallTargetMap &M) {
1592 SmallVector<InstrProfValueData, 2> R;
1593 for (const auto &I : SampleRecord::sortCallTargets(Targets: M)) {
1594 R.emplace_back(
1595 Args: InstrProfValueData{.Value: I.first.getHashCode(), .Count: I.second});
1596 }
1597 return R;
1598}
1599
1600// Generate MD_prof metadata for every branch instruction using the
1601// edge weights computed during propagation.
1602void SampleProfileLoader::generateMDProfMetadata(Function &F) {
1603 // Generate MD_prof metadata for every branch instruction using the
1604 // edge weights computed during propagation.
1605 LLVM_DEBUG(dbgs() << "\nPropagation complete. Setting branch weights\n");
1606 LLVMContext &Ctx = F.getContext();
1607 MDBuilder MDB(Ctx);
1608 for (auto &BI : F) {
1609 BasicBlock *BB = &BI;
1610
1611 if (BlockWeights[BB]) {
1612 for (auto &I : *BB) {
1613 if (!isa<CallInst>(Val: I) && !isa<InvokeInst>(Val: I))
1614 continue;
1615 if (!cast<CallBase>(Val&: I).getCalledFunction()) {
1616 const DebugLoc &DLoc = I.getDebugLoc();
1617 if (!DLoc)
1618 continue;
1619 const DILocation *DIL = DLoc;
1620 const FunctionSamples *FS = findFunctionSamples(Inst: I);
1621 if (!FS)
1622 continue;
1623 auto CallSite = FunctionSamples::getCallSiteIdentifier(DIL);
1624 ErrorOr<SampleRecord::CallTargetMap> T =
1625 FS->findCallTargetMapAt(CallSite);
1626 if (!T || T.get().empty())
1627 continue;
1628 if (FunctionSamples::ProfileIsProbeBased) {
1629 // Prorate the callsite counts based on the pre-ICP distribution
1630 // factor to reflect what is already done to the callsite before
1631 // ICP, such as calliste cloning.
1632 if (std::optional<PseudoProbe> Probe = extractProbe(Inst: I)) {
1633 if (Probe->Factor < 1)
1634 T = SampleRecord::adjustCallTargets(Targets: T.get(), DistributionFactor: Probe->Factor);
1635 }
1636 }
1637 SmallVector<InstrProfValueData, 2> SortedCallTargets =
1638 GetSortedValueDataFromCallTargets(M: T.get());
1639 uint64_t Sum = 0;
1640 for (const auto &C : T.get())
1641 Sum += C.second;
1642 // With CSSPGO all indirect call targets are counted torwards the
1643 // original indirect call site in the profile, including both
1644 // inlined and non-inlined targets.
1645 if (!FunctionSamples::ProfileIsCS) {
1646 if (const FunctionSamplesMap *M =
1647 FS->findFunctionSamplesMapAt(Loc: CallSite)) {
1648 for (const auto &NameFS : *M)
1649 Sum += NameFS.second.getHeadSamplesEstimate();
1650 }
1651 }
1652 if (Sum)
1653 updateIDTMetaData(Inst&: I, CallTargets: SortedCallTargets, Sum);
1654 else if (OverwriteExistingWeights)
1655 I.setMetadata(KindID: LLVMContext::MD_prof, Node: nullptr);
1656 } else if (!isa<IntrinsicInst>(Val: &I)) {
1657 setBranchWeights(
1658 I, Weights: ArrayRef<uint32_t>{static_cast<uint32_t>(BlockWeights[BB])},
1659 /*IsExpected=*/false);
1660 }
1661 }
1662 } else if (OverwriteExistingWeights || ProfileSampleBlockAccurate) {
1663 // Set profile metadata (possibly annotated by LTO prelink) to zero or
1664 // clear it for cold code.
1665 for (auto &I : *BB) {
1666 if (isa<CallInst>(Val: I) || isa<InvokeInst>(Val: I)) {
1667 if (cast<CallBase>(Val&: I).isIndirectCall()) {
1668 I.setMetadata(KindID: LLVMContext::MD_prof, Node: nullptr);
1669 } else {
1670 setBranchWeights(I, Weights: ArrayRef<uint32_t>{uint32_t(0)},
1671 /*IsExpected=*/false);
1672 }
1673 }
1674 }
1675 }
1676
1677 Instruction *TI = BB->getTerminator();
1678 if (TI->getNumSuccessors() == 1)
1679 continue;
1680 if (!isa<CondBrInst>(Val: TI) && !isa<SwitchInst>(Val: TI) &&
1681 !isa<IndirectBrInst>(Val: TI))
1682 continue;
1683
1684 DebugLoc BranchLoc = TI->getDebugLoc();
1685 LLVM_DEBUG(dbgs() << "\nGetting weights for branch at line "
1686 << ((BranchLoc) ? Twine(BranchLoc.getLine())
1687 : Twine("<UNKNOWN LOCATION>"))
1688 << ".\n");
1689 SmallVector<uint32_t, 4> Weights;
1690 uint32_t MaxWeight = 0;
1691 Instruction *MaxDestInst;
1692 // Since profi treats multiple edges (multiway branches) as a single edge,
1693 // we need to distribute the computed weight among the branches. We do
1694 // this by evenly splitting the edge weight among destinations.
1695 DenseMap<const BasicBlock *, uint64_t> EdgeMultiplicity;
1696 std::vector<uint64_t> EdgeIndex;
1697 if (SampleProfileUseProfi) {
1698 EdgeIndex.resize(new_size: TI->getNumSuccessors());
1699 for (unsigned I = 0; I < TI->getNumSuccessors(); ++I) {
1700 const BasicBlock *Succ = TI->getSuccessor(Idx: I);
1701 EdgeIndex[I] = EdgeMultiplicity[Succ];
1702 EdgeMultiplicity[Succ]++;
1703 }
1704 }
1705 for (unsigned I = 0; I < TI->getNumSuccessors(); ++I) {
1706 BasicBlock *Succ = TI->getSuccessor(Idx: I);
1707 Edge E = std::make_pair(x&: BB, y&: Succ);
1708 uint64_t Weight = EdgeWeights[E];
1709 LLVM_DEBUG(dbgs() << "\t"; printEdgeWeight(dbgs(), E));
1710 // Use uint32_t saturated arithmetic to adjust the incoming weights,
1711 // if needed. Sample counts in profiles are 64-bit unsigned values,
1712 // but internally branch weights are expressed as 32-bit values.
1713 if (Weight > std::numeric_limits<uint32_t>::max()) {
1714 LLVM_DEBUG(dbgs() << " (saturated due to uint32_t overflow)\n");
1715 Weight = std::numeric_limits<uint32_t>::max();
1716 }
1717 if (!SampleProfileUseProfi) {
1718 // Weight is added by one to avoid propagation errors introduced by
1719 // 0 weights.
1720 Weights.push_back(Elt: static_cast<uint32_t>(
1721 Weight == std::numeric_limits<uint32_t>::max() ? Weight
1722 : Weight + 1));
1723 } else {
1724 // Profi creates proper weights that do not require "+1" adjustments but
1725 // we evenly split the weight among branches with the same destination.
1726 uint64_t W = Weight / EdgeMultiplicity[Succ];
1727 // Rounding up, if needed, so that first branches are hotter.
1728 if (EdgeIndex[I] < Weight % EdgeMultiplicity[Succ])
1729 W++;
1730 Weights.push_back(Elt: static_cast<uint32_t>(W));
1731 }
1732 if (Weight != 0) {
1733 if (Weight > MaxWeight) {
1734 MaxWeight = Weight;
1735 MaxDestInst = &*Succ->getFirstNonPHIOrDbgOrLifetime();
1736 }
1737 }
1738 }
1739
1740 misexpect::checkExpectAnnotations(I: *TI, ExistingWeights: Weights, /*IsFrontend=*/false);
1741
1742 uint64_t TempWeight;
1743 // Only set weights if there is at least one non-zero weight.
1744 // In any other case, let the analyzer set weights.
1745 // Do not set weights if the weights are present unless under
1746 // OverwriteExistingWeights. In ThinLTO, the profile annotation is done
1747 // twice. If the first annotation already set the weights, the second pass
1748 // does not need to set it. With OverwriteExistingWeights, Blocks with zero
1749 // weight should have their existing metadata (possibly annotated by LTO
1750 // prelink) cleared.
1751 if (MaxWeight > 0 &&
1752 (!TI->extractProfTotalWeight(TotalVal&: TempWeight) || OverwriteExistingWeights)) {
1753 LLVM_DEBUG(dbgs() << "SUCCESS. Found non-zero weights.\n");
1754 setBranchWeights(I&: *TI, Weights, /*IsExpected=*/false);
1755 ORE->emit(RemarkBuilder: [&]() {
1756 return OptimizationRemark(DEBUG_TYPE, "PopularDest", MaxDestInst)
1757 << "most popular destination for conditional branches at "
1758 << ore::NV("CondBranchesLoc", BranchLoc);
1759 });
1760 } else {
1761 if (OverwriteExistingWeights) {
1762 TI->setMetadata(KindID: LLVMContext::MD_prof, Node: nullptr);
1763 LLVM_DEBUG(dbgs() << "CLEARED. All branch weights are zero.\n");
1764 } else {
1765 LLVM_DEBUG(dbgs() << "SKIPPED. All branch weights are zero.\n");
1766 }
1767 }
1768 }
1769}
1770
1771/// Once all the branch weights are computed, we emit the MD_prof
1772/// metadata on BB using the computed values for each of its branches.
1773///
1774/// \param F The function to query.
1775///
1776/// \returns true if \p F was modified. Returns false, otherwise.
1777bool SampleProfileLoader::emitAnnotations(Function &F) {
1778 bool Changed = false;
1779
1780 if (FunctionSamples::ProfileIsProbeBased) {
1781 LLVM_DEBUG({
1782 if (!ProbeManager->getDesc(F))
1783 dbgs() << "Probe descriptor missing for Function " << F.getName()
1784 << "\n";
1785 });
1786
1787 if (ProbeManager->profileIsValid(F, Samples: *Samples)) {
1788 ++NumMatchedProfile;
1789 } else {
1790 ++NumMismatchedProfile;
1791 LLVM_DEBUG(
1792 dbgs() << "Profile is invalid due to CFG mismatch for Function "
1793 << F.getName() << "\n");
1794 if (!SalvageStaleProfile)
1795 return false;
1796 }
1797 } else {
1798 if (getFunctionLoc(F) == 0)
1799 return false;
1800
1801 LLVM_DEBUG(dbgs() << "Line number for the first instruction in "
1802 << F.getName() << ": " << getFunctionLoc(F) << "\n");
1803 }
1804
1805 DenseSet<GlobalValue::GUID> InlinedGUIDs;
1806 if (CallsitePrioritizedInline)
1807 Changed |= inlineHotFunctionsWithPriority(F, InlinedGUIDs);
1808 else
1809 Changed |= inlineHotFunctions(F, InlinedGUIDs);
1810
1811 Changed |= computeAndPropagateWeights(F, InlinedGUIDs);
1812
1813 if (Changed)
1814 generateMDProfMetadata(F);
1815
1816 emitCoverageRemarks(F);
1817 return Changed;
1818}
1819
1820std::unique_ptr<ProfiledCallGraph>
1821SampleProfileLoader::buildProfiledCallGraph(Module &M) {
1822 std::unique_ptr<ProfiledCallGraph> ProfiledCG;
1823 if (FunctionSamples::ProfileIsCS)
1824 ProfiledCG = std::make_unique<ProfiledCallGraph>(args&: *ContextTracker);
1825 else
1826 ProfiledCG = std::make_unique<ProfiledCallGraph>(args&: Reader->getProfiles());
1827
1828 // Add all functions into the profiled call graph even if they are not in
1829 // the profile. This makes sure functions missing from the profile still
1830 // gets a chance to be processed.
1831 for (Function &F : M) {
1832 if (skipProfileForFunction(F))
1833 continue;
1834 ProfiledCG->addProfiledFunction(
1835 Name: getRepInFormat(Name: FunctionSamples::getCanonicalFnName(F)));
1836 }
1837
1838 return ProfiledCG;
1839}
1840
1841std::vector<Function *>
1842SampleProfileLoader::buildFunctionOrder(Module &M, LazyCallGraph &CG) {
1843 std::vector<Function *> FunctionOrderList;
1844 FunctionOrderList.reserve(n: M.size());
1845
1846 if (!ProfileTopDownLoad && UseProfiledCallGraph)
1847 errs() << "WARNING: -use-profiled-call-graph ignored, should be used "
1848 "together with -sample-profile-top-down-load.\n";
1849
1850 if (!ProfileTopDownLoad) {
1851 if (ProfileMergeInlinee) {
1852 // Disable ProfileMergeInlinee if profile is not loaded in top down order,
1853 // because the profile for a function may be used for the profile
1854 // annotation of its outline copy before the profile merging of its
1855 // non-inlined inline instances, and that is not the way how
1856 // ProfileMergeInlinee is supposed to work.
1857 ProfileMergeInlinee = false;
1858 }
1859
1860 for (Function &F : M)
1861 if (!skipProfileForFunction(F))
1862 FunctionOrderList.push_back(x: &F);
1863 return FunctionOrderList;
1864 }
1865
1866 if (UseProfiledCallGraph || (FunctionSamples::ProfileIsCS &&
1867 !UseProfiledCallGraph.getNumOccurrences())) {
1868 // Use profiled call edges to augment the top-down order. There are cases
1869 // that the top-down order computed based on the static call graph doesn't
1870 // reflect real execution order. For example
1871 //
1872 // 1. Incomplete static call graph due to unknown indirect call targets.
1873 // Adjusting the order by considering indirect call edges from the
1874 // profile can enable the inlining of indirect call targets by allowing
1875 // the caller processed before them.
1876 // 2. Mutual call edges in an SCC. The static processing order computed for
1877 // an SCC may not reflect the call contexts in the context-sensitive
1878 // profile, thus may cause potential inlining to be overlooked. The
1879 // function order in one SCC is being adjusted to a top-down order based
1880 // on the profile to favor more inlining. This is only a problem with CS
1881 // profile.
1882 // 3. Transitive indirect call edges due to inlining. When a callee function
1883 // (say B) is inlined into a caller function (say A) in LTO prelink,
1884 // every call edge originated from the callee B will be transferred to
1885 // the caller A. If any transferred edge (say A->C) is indirect, the
1886 // original profiled indirect edge B->C, even if considered, would not
1887 // enforce a top-down order from the caller A to the potential indirect
1888 // call target C in LTO postlink since the inlined callee B is gone from
1889 // the static call graph.
1890 // 4. #3 can happen even for direct call targets, due to functions defined
1891 // in header files. A header function (say A), when included into source
1892 // files, is defined multiple times but only one definition survives due
1893 // to ODR. Therefore, the LTO prelink inlining done on those dropped
1894 // definitions can be useless based on a local file scope. More
1895 // importantly, the inlinee (say B), once fully inlined to a
1896 // to-be-dropped A, will have no profile to consume when its outlined
1897 // version is compiled. This can lead to a profile-less prelink
1898 // compilation for the outlined version of B which may be called from
1899 // external modules. while this isn't easy to fix, we rely on the
1900 // postlink AutoFDO pipeline to optimize B. Since the survived copy of
1901 // the A can be inlined in its local scope in prelink, it may not exist
1902 // in the merged IR in postlink, and we'll need the profiled call edges
1903 // to enforce a top-down order for the rest of the functions.
1904 //
1905 // Considering those cases, a profiled call graph completely independent of
1906 // the static call graph is constructed based on profile data, where
1907 // function objects are not even needed to handle case #3 and case 4.
1908 //
1909 // Note that static callgraph edges are completely ignored since they
1910 // can be conflicting with profiled edges for cyclic SCCs and may result in
1911 // an SCC order incompatible with profile-defined one. Using strictly
1912 // profile order ensures a maximum inlining experience. On the other hand,
1913 // static call edges are not so important when they don't correspond to a
1914 // context in the profile.
1915
1916 std::unique_ptr<ProfiledCallGraph> ProfiledCG = buildProfiledCallGraph(M);
1917 scc_iterator<ProfiledCallGraph *> CGI = scc_begin(G: ProfiledCG.get());
1918 while (!CGI.isAtEnd()) {
1919 auto Range = *CGI;
1920 if (SortProfiledSCC) {
1921 // Sort nodes in one SCC based on callsite hotness.
1922 scc_member_iterator<ProfiledCallGraph *> SI(*CGI);
1923 Range = *SI;
1924 }
1925 for (auto *Node : Range) {
1926 Function *F = SymbolMap.lookup(Key: Node->Name);
1927 if (F && !skipProfileForFunction(F: *F))
1928 FunctionOrderList.push_back(x: F);
1929 }
1930 ++CGI;
1931 }
1932 std::reverse(first: FunctionOrderList.begin(), last: FunctionOrderList.end());
1933 } else
1934 buildTopDownFuncOrder(CG, FunctionOrderList);
1935
1936 LLVM_DEBUG({
1937 dbgs() << "Function processing order:\n";
1938 for (auto F : FunctionOrderList) {
1939 dbgs() << F->getName() << "\n";
1940 }
1941 });
1942
1943 return FunctionOrderList;
1944}
1945
1946bool SampleProfileLoader::doInitialization(Module &M,
1947 FunctionAnalysisManager *FAM) {
1948 auto &Ctx = M.getContext();
1949
1950 auto ReaderOrErr = SampleProfileReader::create(
1951 Filename, C&: Ctx, FS&: *FS, P: FSDiscriminatorPass::Base, RemapFilename: RemappingFilename);
1952 if (std::error_code EC = ReaderOrErr.getError()) {
1953 std::string Msg = "Could not open profile: " + EC.message();
1954 Ctx.diagnose(DI: DiagnosticInfoSampleProfile(Filename, Msg));
1955 return false;
1956 }
1957 Reader = std::move(ReaderOrErr.get());
1958 Reader->setSkipFlatProf(LTOPhase == ThinOrFullLTOPhase::ThinLTOPostLink);
1959 // set module before reading the profile so reader may be able to only
1960 // read the function profiles which are used by the current module.
1961 Reader->setModule(&M);
1962 if (std::error_code EC = Reader->read()) {
1963 std::string Msg = "profile reading failed: " + EC.message();
1964 Ctx.diagnose(DI: DiagnosticInfoSampleProfile(Filename, Msg));
1965 return false;
1966 }
1967
1968 PSL = Reader->getProfileSymbolList();
1969
1970 if (DisableSampleLoaderInlining.getNumOccurrences())
1971 DisableSampleProfileInlining = DisableSampleLoaderInlining;
1972
1973 if (UseFlattenedProfile)
1974 ProfileConverter::flattenProfile(ProfileMap&: Reader->getProfiles(),
1975 ProfileIsCS: Reader->profileIsCS());
1976
1977 // While profile-sample-accurate is on, ignore symbol list.
1978 ProfAccForSymsInList =
1979 ProfileAccurateForSymsInList && PSL && !ProfileSampleAccurate;
1980 if (ProfAccForSymsInList)
1981 CoverageTracker.setProfAccForSymsInList(true);
1982
1983 if (FAM && !ProfileInlineReplayFile.empty()) {
1984 ExternalInlineAdvisor = getReplayInlineAdvisor(
1985 M, FAM&: *FAM, Context&: Ctx, /*OriginalAdvisor=*/nullptr,
1986 ReplaySettings: ReplayInlinerSettings{.ReplayFile: ProfileInlineReplayFile,
1987 .ReplayScope: ProfileInlineReplayScope,
1988 .ReplayFallback: ProfileInlineReplayFallback,
1989 .ReplayFormat: {.OutputFormat: ProfileInlineReplayFormat}},
1990 /*EmitRemarks=*/false, IC: InlineContext{.LTOPhase: LTOPhase, .Pass: InlinePass::ReplaySampleProfileInliner});
1991 }
1992
1993 // Apply tweaks if context-sensitive or probe-based profile is available.
1994 if (Reader->profileIsCS() || Reader->profileIsPreInlined() ||
1995 Reader->profileIsProbeBased()) {
1996 if (!UseIterativeBFIInference.getNumOccurrences())
1997 UseIterativeBFIInference = true;
1998 if (!SampleProfileUseProfi.getNumOccurrences())
1999 SampleProfileUseProfi = true;
2000 if (!EnableExtTspBlockPlacement.getNumOccurrences())
2001 EnableExtTspBlockPlacement = true;
2002 // Enable priority-base inliner and size inline by default for CSSPGO.
2003 if (!ProfileSizeInline.getNumOccurrences())
2004 ProfileSizeInline = true;
2005 if (!CallsitePrioritizedInline.getNumOccurrences())
2006 CallsitePrioritizedInline = true;
2007 // For CSSPGO, we also allow recursive inline to best use context profile.
2008 if (!AllowRecursiveInline.getNumOccurrences())
2009 AllowRecursiveInline = true;
2010
2011 if (Reader->profileIsPreInlined()) {
2012 if (!UsePreInlinerDecision.getNumOccurrences())
2013 UsePreInlinerDecision = true;
2014 }
2015
2016 // Enable stale profile matching by default for probe-based profile.
2017 // Currently the matching relies on if the checksum mismatch is detected,
2018 // which is currently only available for pseudo-probe mode. Removing the
2019 // checksum check could cause regressions for some cases, so further tuning
2020 // might be needed if we want to enable it for all cases.
2021 if (Reader->profileIsProbeBased()) {
2022 if (!SalvageStaleProfile.getNumOccurrences())
2023 SalvageStaleProfile = true;
2024 if (!SalvageUnusedProfile.getNumOccurrences())
2025 SalvageUnusedProfile = true;
2026 }
2027
2028 if (!Reader->profileIsCS()) {
2029 // Non-CS profile should be fine without a function size budget for the
2030 // inliner since the contexts in the profile are either all from inlining
2031 // in the prevoius build or pre-computed by the preinliner with a size
2032 // cap, thus they are bounded.
2033 if (!ProfileInlineLimitMin.getNumOccurrences())
2034 ProfileInlineLimitMin = std::numeric_limits<unsigned>::max();
2035 if (!ProfileInlineLimitMax.getNumOccurrences())
2036 ProfileInlineLimitMax = std::numeric_limits<unsigned>::max();
2037 }
2038 }
2039
2040 if (Reader->profileIsCS()) {
2041 // Tracker for profiles under different context
2042 ContextTracker = std::make_unique<SampleContextTracker>(
2043 args&: Reader->getProfiles(), args: &GUIDToFuncNameMap);
2044 }
2045
2046 // Load pseudo probe descriptors for probe-based function samples.
2047 if (Reader->profileIsProbeBased()) {
2048 ProbeManager = std::make_unique<PseudoProbeManager>(args&: M);
2049 if (!ProbeManager->moduleIsProbed(M)) {
2050 const char *Msg =
2051 "Pseudo-probe-based profile requires SampleProfileProbePass";
2052 Ctx.diagnose(DI: DiagnosticInfoSampleProfile(M.getModuleIdentifier(), Msg,
2053 DS_Warning));
2054 return false;
2055 }
2056 }
2057
2058 if (ReportProfileStaleness || PersistProfileStaleness ||
2059 SalvageStaleProfile) {
2060 MatchingManager = std::make_unique<SampleProfileMatcher>(
2061 args&: M, args&: *Reader, args&: CG, args: ProbeManager.get(), args: LTOPhase, args&: SymbolMap, args&: PSL,
2062 args&: FuncNameToProfNameMap);
2063 }
2064
2065 return true;
2066}
2067
2068// Note that this is a module-level check. Even if one module is errored out,
2069// the entire build will be errored out. However, the user could make big
2070// changes to functions in single module but those changes might not be
2071// performance significant to the whole binary. Therefore, to avoid those false
2072// positives, we select a reasonable big set of hot functions that are supposed
2073// to be globally performance significant, only compute and check the mismatch
2074// within those functions. The function selection is based on two criteria:
2075// 1) The function is hot enough, which is tuned by a hotness-based
2076// flag(HotFuncCutoffForStalenessError). 2) The num of function is large enough
2077// which is tuned by the MinfuncsForStalenessError flag.
2078bool SampleProfileLoader::rejectHighStalenessProfile(
2079 Module &M, ProfileSummaryInfo *PSI, const SampleProfileMap &Profiles) {
2080 assert(FunctionSamples::ProfileIsProbeBased &&
2081 "Only support for probe-based profile");
2082 uint64_t TotalHotFunc = 0;
2083 uint64_t NumMismatchedFunc = 0;
2084 for (const auto &I : Profiles) {
2085 const auto &FS = I.second;
2086 const auto *FuncDesc = ProbeManager->getDesc(GUID: FS.getGUID());
2087 if (!FuncDesc)
2088 continue;
2089
2090 // Use a hotness-based threshold to control the function selection.
2091 if (!PSI->isHotCountNthPercentile(PercentileCutoff: HotFuncCutoffForStalenessError,
2092 C: FS.getTotalSamples()))
2093 continue;
2094
2095 TotalHotFunc++;
2096 if (ProbeManager->profileIsHashMismatched(FuncDesc: *FuncDesc, Samples: FS) &&
2097 !ProbeManager->probeFromWeakSymbol(GUID: FS.getGUID()))
2098 NumMismatchedFunc++;
2099 }
2100 // Make sure that the num of selected function is not too small to distinguish
2101 // from the user's benign changes.
2102 if (TotalHotFunc < MinfuncsForStalenessError)
2103 return false;
2104
2105 // Finally check the mismatch percentage against the threshold.
2106 if (NumMismatchedFunc * 100 >=
2107 TotalHotFunc * PrecentMismatchForStalenessError) {
2108 auto &Ctx = M.getContext();
2109 const char *Msg =
2110 "The input profile significantly mismatches current source code. "
2111 "Please recollect profile to avoid performance regression.";
2112 Ctx.diagnose(DI: DiagnosticInfoSampleProfile(M.getModuleIdentifier(), Msg));
2113 return true;
2114 }
2115 return false;
2116}
2117
2118void SampleProfileLoader::removePseudoProbeInstsDiscriminator(Module &M) {
2119 for (auto &F : M) {
2120 std::vector<Instruction *> InstsToDel;
2121 for (auto &BB : F) {
2122 for (auto &I : BB) {
2123 if (isa<PseudoProbeInst>(Val: &I))
2124 InstsToDel.push_back(x: &I);
2125 else if (isa<CallBase>(Val: &I))
2126 if (const DILocation *DIL = I.getDebugLoc().get()) {
2127 // Restore dwarf discriminator for call.
2128 unsigned Discriminator = DIL->getDiscriminator();
2129 if (DILocation::isPseudoProbeDiscriminator(Discriminator)) {
2130 std::optional<uint32_t> DwarfDiscriminator =
2131 PseudoProbeDwarfDiscriminator::extractDwarfBaseDiscriminator(
2132 Value: Discriminator);
2133 I.setDebugLoc(
2134 DIL->cloneWithDiscriminator(Discriminator: DwarfDiscriminator.value_or(u: 0)));
2135 }
2136 }
2137 }
2138 }
2139 for (auto *I : InstsToDel)
2140 I->eraseFromParent();
2141 }
2142}
2143
2144bool SampleProfileLoader::runOnModule(Module &M, ModuleAnalysisManager &AM,
2145 ProfileSummaryInfo *_PSI) {
2146 GUIDToFuncNameMapper Mapper(M, *Reader, GUIDToFuncNameMap);
2147
2148 PSI = _PSI;
2149 if (M.getProfileSummary(/* IsCS */ false) == nullptr) {
2150 M.setProfileSummary(M: Reader->getSummary().getMD(Context&: M.getContext()),
2151 Kind: ProfileSummary::PSK_Sample);
2152 PSI->refresh();
2153 }
2154
2155 if (FunctionSamples::ProfileIsProbeBased &&
2156 rejectHighStalenessProfile(M, PSI, Profiles: Reader->getProfiles()))
2157 return false;
2158
2159 auto Remapper = Reader->getRemapper();
2160 // Populate the symbol map.
2161 for (const auto &N_F : M.getValueSymbolTable()) {
2162 StringRef OrigName = N_F.getKey();
2163 Function *F = dyn_cast<Function>(Val: N_F.getValue());
2164 if (F == nullptr || OrigName.empty())
2165 continue;
2166 SymbolMap[FunctionId(OrigName)] = F;
2167 StringRef NewName = FunctionSamples::getCanonicalFnName(F: *F);
2168 if (OrigName != NewName && !NewName.empty()) {
2169 auto r = SymbolMap.emplace(Args: FunctionId(NewName), Args&: F);
2170 // Failiing to insert means there is already an entry in SymbolMap,
2171 // thus there are multiple functions that are mapped to the same
2172 // stripped name. In this case of name conflicting, set the value
2173 // to nullptr to avoid confusion.
2174 if (!r.second)
2175 r.first->second = nullptr;
2176 OrigName = NewName;
2177 }
2178 // Insert the remapped names into SymbolMap.
2179 if (Remapper) {
2180 if (auto MapName = Remapper->lookUpNameInProfile(FunctionName: OrigName)) {
2181 if (*MapName != OrigName && !MapName->empty())
2182 SymbolMap.emplace(Args: FunctionId(*MapName), Args&: F);
2183 }
2184 }
2185 }
2186
2187 // Stale profile matching.
2188 if (ReportProfileStaleness || PersistProfileStaleness ||
2189 SalvageStaleProfile) {
2190 MatchingManager->runOnModule();
2191 MatchingManager->clearMatchingData();
2192 }
2193 assert(SymbolMap.count(FunctionId()) == 0 &&
2194 "No empty StringRef should be added in SymbolMap");
2195 assert((SalvageUnusedProfile || FuncNameToProfNameMap.empty()) &&
2196 "FuncNameToProfNameMap is not empty when --salvage-unused-profile is "
2197 "not enabled");
2198
2199 bool retval = false;
2200 for (auto *F : buildFunctionOrder(M, CG)) {
2201 assert(!F->isDeclaration());
2202 clearFunctionData();
2203 retval |= runOnFunction(F&: *F, AM);
2204 }
2205
2206 // Account for cold calls not inlined....
2207 if (!FunctionSamples::ProfileIsCS)
2208 for (const std::pair<Function *, NotInlinedProfileInfo> &pair :
2209 notInlinedCallInfo)
2210 updateProfileCallee(Callee: pair.first, EntryDelta: pair.second.entryCount);
2211
2212 if (RemoveProbeAfterProfileAnnotation &&
2213 FunctionSamples::ProfileIsProbeBased) {
2214 removePseudoProbeInstsDiscriminator(M);
2215 if (auto *FuncInfo = M.getNamedMetadata(Name: PseudoProbeDescMetadataName))
2216 M.eraseNamedMetadata(NMD: FuncInfo);
2217 }
2218
2219 return retval;
2220}
2221
2222bool SampleProfileLoader::runOnFunction(Function &F,
2223 ModuleAnalysisManager &AM) {
2224 LLVM_DEBUG(dbgs() << "\n\nProcessing Function " << F.getName() << "\n");
2225 DILocation2SampleMap.clear();
2226 // By default the entry count is initialized to -1, which will be treated
2227 // conservatively by getEntryCount as the same as unknown (None). This is
2228 // to avoid newly added code to be treated as cold. If we have samples
2229 // this will be overwritten in emitAnnotations.
2230 uint64_t initialEntryCount = -1;
2231
2232 ProfAccForSymsInList = ProfileAccurateForSymsInList && PSL;
2233 if (ProfileSampleAccurate || F.hasFnAttribute(Kind: "profile-sample-accurate")) {
2234 // initialize all the function entry counts to 0. It means all the
2235 // functions without profile will be regarded as cold.
2236 initialEntryCount = 0;
2237 // profile-sample-accurate is a user assertion which has a higher precedence
2238 // than symbol list. When profile-sample-accurate is on, ignore symbol list.
2239 ProfAccForSymsInList = false;
2240 }
2241 CoverageTracker.setProfAccForSymsInList(ProfAccForSymsInList);
2242
2243 // PSL -- profile symbol list include all the symbols in sampled binary.
2244 // If ProfileAccurateForSymsInList is enabled, PSL is used to treat
2245 // old functions without samples being cold, without having to worry
2246 // about new and hot functions being mistakenly treated as cold.
2247 if (ProfAccForSymsInList) {
2248 // Initialize the entry count to 0 for functions in the list.
2249 if (PSL->contains(Name: F.getName()))
2250 initialEntryCount = 0;
2251
2252 // Function in the symbol list but without sample will be regarded as
2253 // cold. To minimize the potential negative performance impact it could
2254 // have, we want to be a little conservative here saying if a function
2255 // shows up in the profile, no matter as outline function, inline instance
2256 // or call targets, treat the function as not being cold. This will handle
2257 // the cases such as most callsites of a function are inlined in sampled
2258 // binary but not inlined in current build (because of source code drift,
2259 // imprecise debug information, or the callsites are all cold individually
2260 // but not cold accumulatively...), so the outline function showing up as
2261 // cold in sampled binary will actually not be cold after current build.
2262 StringRef CanonName = FunctionSamples::getCanonicalFnName(F);
2263 if (FunctionSamples::UseMD5
2264 ? Reader->contains(
2265 GUID: Function::getGUIDAssumingExternalLinkage(GlobalName: CanonName))
2266 : Reader->contains(Key: CanonName))
2267 initialEntryCount = -1;
2268 }
2269
2270 // Initialize entry count when the function has no existing entry
2271 // count value.
2272 if (!F.getEntryCount())
2273 F.setEntryCount(Count: initialEntryCount);
2274 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(IR&: *F.getParent())
2275 .getManager();
2276 ORE = &FAM.getResult<OptimizationRemarkEmitterAnalysis>(IR&: F);
2277
2278 if (FunctionSamples::ProfileIsCS)
2279 Samples = ContextTracker->getBaseSamplesFor(Func: F);
2280 else {
2281 Samples = Reader->getSamplesFor(F);
2282 // Try search in previously inlined functions that were split or duplicated
2283 // into base.
2284 if (!Samples) {
2285 StringRef CanonName = FunctionSamples::getCanonicalFnName(F);
2286 auto It = OutlineFunctionSamples.find(x: FunctionId(CanonName));
2287 if (It != OutlineFunctionSamples.end()) {
2288 Samples = &It->second;
2289 } else if (auto Remapper = Reader->getRemapper()) {
2290 if (auto RemppedName = Remapper->lookUpNameInProfile(FunctionName: CanonName)) {
2291 It = OutlineFunctionSamples.find(x: FunctionId(*RemppedName));
2292 if (It != OutlineFunctionSamples.end())
2293 Samples = &It->second;
2294 }
2295 }
2296 }
2297 }
2298
2299 if (Samples && !Samples->empty())
2300 return emitAnnotations(F);
2301 return false;
2302}
2303SampleProfileLoaderPass::SampleProfileLoaderPass(
2304 std::string File, std::string RemappingFile, ThinOrFullLTOPhase LTOPhase,
2305 IntrusiveRefCntPtr<vfs::FileSystem> FS, bool DisableSampleProfileInlining,
2306 bool UseFlattenedProfile)
2307 : ProfileFileName(File), ProfileRemappingFileName(RemappingFile),
2308 LTOPhase(LTOPhase), FS(std::move(FS)),
2309 DisableSampleProfileInlining(DisableSampleProfileInlining),
2310 UseFlattenedProfile(UseFlattenedProfile) {}
2311
2312PreservedAnalyses SampleProfileLoaderPass::run(Module &M,
2313 ModuleAnalysisManager &AM) {
2314 FunctionAnalysisManager &FAM =
2315 AM.getResult<FunctionAnalysisManagerModuleProxy>(IR&: M).getManager();
2316
2317 auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & {
2318 return FAM.getResult<AssumptionAnalysis>(IR&: F);
2319 };
2320 auto GetTTI = [&](Function &F) -> TargetTransformInfo & {
2321 return FAM.getResult<TargetIRAnalysis>(IR&: F);
2322 };
2323 auto GetTLI = [&](Function &F) -> const TargetLibraryInfo & {
2324 return FAM.getResult<TargetLibraryAnalysis>(IR&: F);
2325 };
2326
2327 if (!FS)
2328 FS = vfs::getRealFileSystem();
2329 LazyCallGraph &CG = AM.getResult<LazyCallGraphAnalysis>(IR&: M);
2330
2331 SampleProfileLoader SampleLoader(
2332 ProfileFileName.empty() ? SampleProfileFile : ProfileFileName,
2333 ProfileRemappingFileName.empty() ? SampleProfileRemappingFile
2334 : ProfileRemappingFileName,
2335 LTOPhase, FS, GetAssumptionCache, GetTTI, GetTLI, CG,
2336 DisableSampleProfileInlining, UseFlattenedProfile);
2337 if (!SampleLoader.doInitialization(M, FAM: &FAM))
2338 return PreservedAnalyses::all();
2339
2340 ProfileSummaryInfo *PSI = &AM.getResult<ProfileSummaryAnalysis>(IR&: M);
2341 if (!SampleLoader.runOnModule(M, AM, PSI: PSI))
2342 return PreservedAnalyses::all();
2343
2344 return PreservedAnalyses::none();
2345}
2346