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