1 //===- SampleProfile.cpp - Incorporate sample profiles into the IR --------===//
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
7 //===----------------------------------------------------------------------===//
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.
14 // This pass generates branch weight annotations on the IR:
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.
22 //===----------------------------------------------------------------------===//
24 #include "llvm/Transforms/IPO/SampleProfile.h"
25 #include "llvm/ADT/ArrayRef.h"
26 #include "llvm/ADT/DenseMap.h"
27 #include "llvm/ADT/DenseSet.h"
28 #include "llvm/ADT/None.h"
29 #include "llvm/ADT/SmallPtrSet.h"
30 #include "llvm/ADT/SmallSet.h"
31 #include "llvm/ADT/SmallVector.h"
32 #include "llvm/ADT/StringMap.h"
33 #include "llvm/ADT/StringRef.h"
34 #include "llvm/ADT/Twine.h"
35 #include "llvm/Analysis/AssumptionCache.h"
36 #include "llvm/Analysis/InlineCost.h"
37 #include "llvm/Analysis/LoopInfo.h"
38 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
39 #include "llvm/Analysis/PostDominators.h"
40 #include "llvm/Analysis/ProfileSummaryInfo.h"
41 #include "llvm/Analysis/TargetTransformInfo.h"
42 #include "llvm/IR/BasicBlock.h"
43 #include "llvm/IR/CFG.h"
44 #include "llvm/IR/CallSite.h"
45 #include "llvm/IR/DebugInfoMetadata.h"
46 #include "llvm/IR/DebugLoc.h"
47 #include "llvm/IR/DiagnosticInfo.h"
48 #include "llvm/IR/Dominators.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"
53 #include "llvm/IR/Instructions.h"
54 #include "llvm/IR/IntrinsicInst.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"
59 #include "llvm/IR/ValueSymbolTable.h"
60 #include "llvm/Pass.h"
61 #include "llvm/ProfileData/InstrProf.h"
62 #include "llvm/ProfileData/SampleProf.h"
63 #include "llvm/ProfileData/SampleProfReader.h"
64 #include "llvm/Support/Casting.h"
65 #include "llvm/Support/CommandLine.h"
66 #include "llvm/Support/Debug.h"
67 #include "llvm/Support/ErrorHandling.h"
68 #include "llvm/Support/ErrorOr.h"
69 #include "llvm/Support/GenericDomTree.h"
70 #include "llvm/Support/raw_ostream.h"
71 #include "llvm/Transforms/IPO.h"
72 #include "llvm/Transforms/Instrumentation.h"
73 #include "llvm/Transforms/Utils/CallPromotionUtils.h"
74 #include "llvm/Transforms/Utils/Cloning.h"
84 #include <system_error>
89 using namespace sampleprof
;
90 using ProfileCount
= Function::ProfileCount
;
91 #define DEBUG_TYPE "sample-profile"
93 // Command line option to specify the file to read samples from. This is
94 // mainly used for debugging.
95 static cl::opt
<std::string
> SampleProfileFile(
96 "sample-profile-file", cl::init(""), cl::value_desc("filename"),
97 cl::desc("Profile file loaded by -sample-profile"), cl::Hidden
);
99 // The named file contains a set of transformations that may have been applied
100 // to the symbol names between the program from which the sample data was
101 // collected and the current program's symbols.
102 static cl::opt
<std::string
> SampleProfileRemappingFile(
103 "sample-profile-remapping-file", cl::init(""), cl::value_desc("filename"),
104 cl::desc("Profile remapping file loaded by -sample-profile"), cl::Hidden
);
106 static cl::opt
<unsigned> SampleProfileMaxPropagateIterations(
107 "sample-profile-max-propagate-iterations", cl::init(100),
108 cl::desc("Maximum number of iterations to go through when propagating "
109 "sample block/edge weights through the CFG."));
111 static cl::opt
<unsigned> SampleProfileRecordCoverage(
112 "sample-profile-check-record-coverage", cl::init(0), cl::value_desc("N"),
113 cl::desc("Emit a warning if less than N% of records in the input profile "
114 "are matched to the IR."));
116 static cl::opt
<unsigned> SampleProfileSampleCoverage(
117 "sample-profile-check-sample-coverage", cl::init(0), cl::value_desc("N"),
118 cl::desc("Emit a warning if less than N% of samples in the input profile "
119 "are matched to the IR."));
121 static cl::opt
<bool> NoWarnSampleUnused(
122 "no-warn-sample-unused", cl::init(false), cl::Hidden
,
123 cl::desc("Use this option to turn off/on warnings about function with "
124 "samples but without debug information to use those samples. "));
126 static cl::opt
<bool> ProfileSampleAccurate(
127 "profile-sample-accurate", cl::Hidden
, cl::init(false),
128 cl::desc("If the sample profile is accurate, we will mark all un-sampled "
129 "callsite and function as having 0 samples. Otherwise, treat "
130 "un-sampled callsites and functions conservatively as unknown. "));
134 using BlockWeightMap
= DenseMap
<const BasicBlock
*, uint64_t>;
135 using EquivalenceClassMap
= DenseMap
<const BasicBlock
*, const BasicBlock
*>;
136 using Edge
= std::pair
<const BasicBlock
*, const BasicBlock
*>;
137 using EdgeWeightMap
= DenseMap
<Edge
, uint64_t>;
139 DenseMap
<const BasicBlock
*, SmallVector
<const BasicBlock
*, 8>>;
141 class SampleCoverageTracker
{
143 SampleCoverageTracker() = default;
145 bool markSamplesUsed(const FunctionSamples
*FS
, uint32_t LineOffset
,
146 uint32_t Discriminator
, uint64_t Samples
);
147 unsigned computeCoverage(unsigned Used
, unsigned Total
) const;
148 unsigned countUsedRecords(const FunctionSamples
*FS
,
149 ProfileSummaryInfo
*PSI
) const;
150 unsigned countBodyRecords(const FunctionSamples
*FS
,
151 ProfileSummaryInfo
*PSI
) const;
152 uint64_t getTotalUsedSamples() const { return TotalUsedSamples
; }
153 uint64_t countBodySamples(const FunctionSamples
*FS
,
154 ProfileSummaryInfo
*PSI
) const;
157 SampleCoverage
.clear();
158 TotalUsedSamples
= 0;
162 using BodySampleCoverageMap
= std::map
<LineLocation
, unsigned>;
163 using FunctionSamplesCoverageMap
=
164 DenseMap
<const FunctionSamples
*, BodySampleCoverageMap
>;
166 /// Coverage map for sampling records.
168 /// This map keeps a record of sampling records that have been matched to
169 /// an IR instruction. This is used to detect some form of staleness in
170 /// profiles (see flag -sample-profile-check-coverage).
172 /// Each entry in the map corresponds to a FunctionSamples instance. This is
173 /// another map that counts how many times the sample record at the
174 /// given location has been used.
175 FunctionSamplesCoverageMap SampleCoverage
;
177 /// Number of samples used from the profile.
179 /// When a sampling record is used for the first time, the samples from
180 /// that record are added to this accumulator. Coverage is later computed
181 /// based on the total number of samples available in this function and
184 /// Note that this accumulator tracks samples used from a single function
185 /// and all the inlined callsites. Strictly, we should have a map of counters
186 /// keyed by FunctionSamples pointers, but these stats are cleared after
187 /// every function, so we just need to keep a single counter.
188 uint64_t TotalUsedSamples
= 0;
191 class GUIDToFuncNameMapper
{
193 GUIDToFuncNameMapper(Module
&M
, SampleProfileReader
&Reader
,
194 DenseMap
<uint64_t, StringRef
> &GUIDToFuncNameMap
)
195 : CurrentReader(Reader
), CurrentModule(M
),
196 CurrentGUIDToFuncNameMap(GUIDToFuncNameMap
) {
197 if (CurrentReader
.getFormat() != SPF_Compact_Binary
)
200 for (const auto &F
: CurrentModule
) {
201 StringRef OrigName
= F
.getName();
202 CurrentGUIDToFuncNameMap
.insert(
203 {Function::getGUID(OrigName
), OrigName
});
205 // Local to global var promotion used by optimization like thinlto
206 // will rename the var and add suffix like ".llvm.xxx" to the
207 // original local name. In sample profile, the suffixes of function
208 // names are all stripped. Since it is possible that the mapper is
209 // built in post-thin-link phase and var promotion has been done,
210 // we need to add the substring of function name without the suffix
211 // into the GUIDToFuncNameMap.
212 StringRef CanonName
= FunctionSamples::getCanonicalFnName(F
);
213 if (CanonName
!= OrigName
)
214 CurrentGUIDToFuncNameMap
.insert(
215 {Function::getGUID(CanonName
), CanonName
});
218 // Update GUIDToFuncNameMap for each function including inlinees.
219 SetGUIDToFuncNameMapForAll(&CurrentGUIDToFuncNameMap
);
222 ~GUIDToFuncNameMapper() {
223 if (CurrentReader
.getFormat() != SPF_Compact_Binary
)
226 CurrentGUIDToFuncNameMap
.clear();
228 // Reset GUIDToFuncNameMap for of each function as they're no
229 // longer valid at this point.
230 SetGUIDToFuncNameMapForAll(nullptr);
234 void SetGUIDToFuncNameMapForAll(DenseMap
<uint64_t, StringRef
> *Map
) {
235 std::queue
<FunctionSamples
*> FSToUpdate
;
236 for (auto &IFS
: CurrentReader
.getProfiles()) {
237 FSToUpdate
.push(&IFS
.second
);
240 while (!FSToUpdate
.empty()) {
241 FunctionSamples
*FS
= FSToUpdate
.front();
243 FS
->GUIDToFuncNameMap
= Map
;
244 for (const auto &ICS
: FS
->getCallsiteSamples()) {
245 const FunctionSamplesMap
&FSMap
= ICS
.second
;
246 for (auto &IFS
: FSMap
) {
247 FunctionSamples
&FS
= const_cast<FunctionSamples
&>(IFS
.second
);
248 FSToUpdate
.push(&FS
);
254 SampleProfileReader
&CurrentReader
;
255 Module
&CurrentModule
;
256 DenseMap
<uint64_t, StringRef
> &CurrentGUIDToFuncNameMap
;
259 /// Sample profile pass.
261 /// This pass reads profile data from the file specified by
262 /// -sample-profile-file and annotates every affected function with the
263 /// profile information found in that file.
264 class SampleProfileLoader
{
267 StringRef Name
, StringRef RemapName
, bool IsThinLTOPreLink
,
268 std::function
<AssumptionCache
&(Function
&)> GetAssumptionCache
,
269 std::function
<TargetTransformInfo
&(Function
&)> GetTargetTransformInfo
)
270 : GetAC(std::move(GetAssumptionCache
)),
271 GetTTI(std::move(GetTargetTransformInfo
)), Filename(Name
),
272 RemappingFilename(RemapName
), IsThinLTOPreLink(IsThinLTOPreLink
) {}
274 bool doInitialization(Module
&M
);
275 bool runOnModule(Module
&M
, ModuleAnalysisManager
*AM
,
276 ProfileSummaryInfo
*_PSI
);
278 void dump() { Reader
->dump(); }
281 bool runOnFunction(Function
&F
, ModuleAnalysisManager
*AM
);
282 unsigned getFunctionLoc(Function
&F
);
283 bool emitAnnotations(Function
&F
);
284 ErrorOr
<uint64_t> getInstWeight(const Instruction
&I
);
285 ErrorOr
<uint64_t> getBlockWeight(const BasicBlock
*BB
);
286 const FunctionSamples
*findCalleeFunctionSamples(const Instruction
&I
) const;
287 std::vector
<const FunctionSamples
*>
288 findIndirectCallFunctionSamples(const Instruction
&I
, uint64_t &Sum
) const;
289 mutable DenseMap
<const DILocation
*, const FunctionSamples
*> DILocation2SampleMap
;
290 const FunctionSamples
*findFunctionSamples(const Instruction
&I
) const;
291 bool inlineCallInstruction(Instruction
*I
);
292 bool inlineHotFunctions(Function
&F
,
293 DenseSet
<GlobalValue::GUID
> &InlinedGUIDs
);
294 void printEdgeWeight(raw_ostream
&OS
, Edge E
);
295 void printBlockWeight(raw_ostream
&OS
, const BasicBlock
*BB
) const;
296 void printBlockEquivalence(raw_ostream
&OS
, const BasicBlock
*BB
);
297 bool computeBlockWeights(Function
&F
);
298 void findEquivalenceClasses(Function
&F
);
299 template <bool IsPostDom
>
300 void findEquivalencesFor(BasicBlock
*BB1
, ArrayRef
<BasicBlock
*> Descendants
,
301 DominatorTreeBase
<BasicBlock
, IsPostDom
> *DomTree
);
303 void propagateWeights(Function
&F
);
304 uint64_t visitEdge(Edge E
, unsigned *NumUnknownEdges
, Edge
*UnknownEdge
);
305 void buildEdges(Function
&F
);
306 bool propagateThroughEdges(Function
&F
, bool UpdateBlockCount
);
307 void computeDominanceAndLoopInfo(Function
&F
);
308 void clearFunctionData();
310 /// Map basic blocks to their computed weights.
312 /// The weight of a basic block is defined to be the maximum
313 /// of all the instruction weights in that block.
314 BlockWeightMap BlockWeights
;
316 /// Map edges to their computed weights.
318 /// Edge weights are computed by propagating basic block weights in
319 /// SampleProfile::propagateWeights.
320 EdgeWeightMap EdgeWeights
;
322 /// Set of visited blocks during propagation.
323 SmallPtrSet
<const BasicBlock
*, 32> VisitedBlocks
;
325 /// Set of visited edges during propagation.
326 SmallSet
<Edge
, 32> VisitedEdges
;
328 /// Equivalence classes for block weights.
330 /// Two blocks BB1 and BB2 are in the same equivalence class if they
331 /// dominate and post-dominate each other, and they are in the same loop
332 /// nest. When this happens, the two blocks are guaranteed to execute
333 /// the same number of times.
334 EquivalenceClassMap EquivalenceClass
;
336 /// Map from function name to Function *. Used to find the function from
337 /// the function name. If the function name contains suffix, additional
338 /// entry is added to map from the stripped name to the function if there
339 /// is one-to-one mapping.
340 StringMap
<Function
*> SymbolMap
;
342 /// Dominance, post-dominance and loop information.
343 std::unique_ptr
<DominatorTree
> DT
;
344 std::unique_ptr
<PostDominatorTree
> PDT
;
345 std::unique_ptr
<LoopInfo
> LI
;
347 std::function
<AssumptionCache
&(Function
&)> GetAC
;
348 std::function
<TargetTransformInfo
&(Function
&)> GetTTI
;
350 /// Predecessors for each basic block in the CFG.
351 BlockEdgeMap Predecessors
;
353 /// Successors for each basic block in the CFG.
354 BlockEdgeMap Successors
;
356 SampleCoverageTracker CoverageTracker
;
358 /// Profile reader object.
359 std::unique_ptr
<SampleProfileReader
> Reader
;
361 /// Samples collected for the body of this function.
362 FunctionSamples
*Samples
= nullptr;
364 /// Name of the profile file to load.
365 std::string Filename
;
367 /// Name of the profile remapping file to load.
368 std::string RemappingFilename
;
370 /// Flag indicating whether the profile input loaded successfully.
371 bool ProfileIsValid
= false;
373 /// Flag indicating if the pass is invoked in ThinLTO compile phase.
375 /// In this phase, in annotation, we should not promote indirect calls.
376 /// Instead, we will mark GUIDs that needs to be annotated to the function.
377 bool IsThinLTOPreLink
;
379 /// Profile Summary Info computed from sample profile.
380 ProfileSummaryInfo
*PSI
= nullptr;
382 /// Total number of samples collected in this profile.
384 /// This is the sum of all the samples collected in all the functions executed
386 uint64_t TotalCollectedSamples
= 0;
388 /// Optimization Remark Emitter used to emit diagnostic remarks.
389 OptimizationRemarkEmitter
*ORE
= nullptr;
391 // Information recorded when we declined to inline a call site
392 // because we have determined it is too cold is accumulated for
393 // each callee function. Initially this is just the entry count.
394 struct NotInlinedProfileInfo
{
397 DenseMap
<Function
*, NotInlinedProfileInfo
> notInlinedCallInfo
;
399 // GUIDToFuncNameMap saves the mapping from GUID to the symbol name, for
400 // all the function symbols defined or declared in current module.
401 DenseMap
<uint64_t, StringRef
> GUIDToFuncNameMap
;
404 class SampleProfileLoaderLegacyPass
: public ModulePass
{
406 // Class identification, replacement for typeinfo
409 SampleProfileLoaderLegacyPass(StringRef Name
= SampleProfileFile
,
410 bool IsThinLTOPreLink
= false)
412 SampleLoader(Name
, SampleProfileRemappingFile
, IsThinLTOPreLink
,
413 [&](Function
&F
) -> AssumptionCache
& {
414 return ACT
->getAssumptionCache(F
);
416 [&](Function
&F
) -> TargetTransformInfo
& {
417 return TTIWP
->getTTI(F
);
419 initializeSampleProfileLoaderLegacyPassPass(
420 *PassRegistry::getPassRegistry());
423 void dump() { SampleLoader
.dump(); }
425 bool doInitialization(Module
&M
) override
{
426 return SampleLoader
.doInitialization(M
);
429 StringRef
getPassName() const override
{ return "Sample profile pass"; }
430 bool runOnModule(Module
&M
) override
;
432 void getAnalysisUsage(AnalysisUsage
&AU
) const override
{
433 AU
.addRequired
<AssumptionCacheTracker
>();
434 AU
.addRequired
<TargetTransformInfoWrapperPass
>();
435 AU
.addRequired
<ProfileSummaryInfoWrapperPass
>();
439 SampleProfileLoader SampleLoader
;
440 AssumptionCacheTracker
*ACT
= nullptr;
441 TargetTransformInfoWrapperPass
*TTIWP
= nullptr;
444 } // end anonymous namespace
446 /// Return true if the given callsite is hot wrt to hot cutoff threshold.
448 /// Functions that were inlined in the original binary will be represented
449 /// in the inline stack in the sample profile. If the profile shows that
450 /// the original inline decision was "good" (i.e., the callsite is executed
451 /// frequently), then we will recreate the inline decision and apply the
452 /// profile from the inlined callsite.
454 /// To decide whether an inlined callsite is hot, we compare the callsite
455 /// sample count with the hot cutoff computed by ProfileSummaryInfo, it is
456 /// regarded as hot if the count is above the cutoff value.
457 static bool callsiteIsHot(const FunctionSamples
*CallsiteFS
,
458 ProfileSummaryInfo
*PSI
) {
460 return false; // The callsite was not inlined in the original binary.
462 assert(PSI
&& "PSI is expected to be non null");
463 uint64_t CallsiteTotalSamples
= CallsiteFS
->getTotalSamples();
464 return PSI
->isHotCount(CallsiteTotalSamples
);
467 /// Mark as used the sample record for the given function samples at
468 /// (LineOffset, Discriminator).
470 /// \returns true if this is the first time we mark the given record.
471 bool SampleCoverageTracker::markSamplesUsed(const FunctionSamples
*FS
,
473 uint32_t Discriminator
,
475 LineLocation
Loc(LineOffset
, Discriminator
);
476 unsigned &Count
= SampleCoverage
[FS
][Loc
];
477 bool FirstTime
= (++Count
== 1);
479 TotalUsedSamples
+= Samples
;
483 /// Return the number of sample records that were applied from this profile.
485 /// This count does not include records from cold inlined callsites.
487 SampleCoverageTracker::countUsedRecords(const FunctionSamples
*FS
,
488 ProfileSummaryInfo
*PSI
) const {
489 auto I
= SampleCoverage
.find(FS
);
491 // The size of the coverage map for FS represents the number of records
492 // that were marked used at least once.
493 unsigned Count
= (I
!= SampleCoverage
.end()) ? I
->second
.size() : 0;
495 // If there are inlined callsites in this function, count the samples found
496 // in the respective bodies. However, do not bother counting callees with 0
497 // total samples, these are callees that were never invoked at runtime.
498 for (const auto &I
: FS
->getCallsiteSamples())
499 for (const auto &J
: I
.second
) {
500 const FunctionSamples
*CalleeSamples
= &J
.second
;
501 if (callsiteIsHot(CalleeSamples
, PSI
))
502 Count
+= countUsedRecords(CalleeSamples
, PSI
);
508 /// Return the number of sample records in the body of this profile.
510 /// This count does not include records from cold inlined callsites.
512 SampleCoverageTracker::countBodyRecords(const FunctionSamples
*FS
,
513 ProfileSummaryInfo
*PSI
) const {
514 unsigned Count
= FS
->getBodySamples().size();
516 // Only count records in hot callsites.
517 for (const auto &I
: FS
->getCallsiteSamples())
518 for (const auto &J
: I
.second
) {
519 const FunctionSamples
*CalleeSamples
= &J
.second
;
520 if (callsiteIsHot(CalleeSamples
, PSI
))
521 Count
+= countBodyRecords(CalleeSamples
, PSI
);
527 /// Return the number of samples collected in the body of this profile.
529 /// This count does not include samples from cold inlined callsites.
531 SampleCoverageTracker::countBodySamples(const FunctionSamples
*FS
,
532 ProfileSummaryInfo
*PSI
) const {
534 for (const auto &I
: FS
->getBodySamples())
535 Total
+= I
.second
.getSamples();
537 // Only count samples in hot callsites.
538 for (const auto &I
: FS
->getCallsiteSamples())
539 for (const auto &J
: I
.second
) {
540 const FunctionSamples
*CalleeSamples
= &J
.second
;
541 if (callsiteIsHot(CalleeSamples
, PSI
))
542 Total
+= countBodySamples(CalleeSamples
, PSI
);
548 /// Return the fraction of sample records used in this profile.
550 /// The returned value is an unsigned integer in the range 0-100 indicating
551 /// the percentage of sample records that were used while applying this
552 /// profile to the associated function.
553 unsigned SampleCoverageTracker::computeCoverage(unsigned Used
,
554 unsigned Total
) const {
555 assert(Used
<= Total
&&
556 "number of used records cannot exceed the total number of records");
557 return Total
> 0 ? Used
* 100 / Total
: 100;
560 /// Clear all the per-function data used to load samples and propagate weights.
561 void SampleProfileLoader::clearFunctionData() {
562 BlockWeights
.clear();
564 VisitedBlocks
.clear();
565 VisitedEdges
.clear();
566 EquivalenceClass
.clear();
570 Predecessors
.clear();
572 CoverageTracker
.clear();
576 /// Print the weight of edge \p E on stream \p OS.
578 /// \param OS Stream to emit the output to.
579 /// \param E Edge to print.
580 void SampleProfileLoader::printEdgeWeight(raw_ostream
&OS
, Edge E
) {
581 OS
<< "weight[" << E
.first
->getName() << "->" << E
.second
->getName()
582 << "]: " << EdgeWeights
[E
] << "\n";
585 /// Print the equivalence class of block \p BB on stream \p OS.
587 /// \param OS Stream to emit the output to.
588 /// \param BB Block to print.
589 void SampleProfileLoader::printBlockEquivalence(raw_ostream
&OS
,
590 const BasicBlock
*BB
) {
591 const BasicBlock
*Equiv
= EquivalenceClass
[BB
];
592 OS
<< "equivalence[" << BB
->getName()
593 << "]: " << ((Equiv
) ? EquivalenceClass
[BB
]->getName() : "NONE") << "\n";
596 /// Print the weight of block \p BB on stream \p OS.
598 /// \param OS Stream to emit the output to.
599 /// \param BB Block to print.
600 void SampleProfileLoader::printBlockWeight(raw_ostream
&OS
,
601 const BasicBlock
*BB
) const {
602 const auto &I
= BlockWeights
.find(BB
);
603 uint64_t W
= (I
== BlockWeights
.end() ? 0 : I
->second
);
604 OS
<< "weight[" << BB
->getName() << "]: " << W
<< "\n";
608 /// Get the weight for an instruction.
610 /// The "weight" of an instruction \p Inst is the number of samples
611 /// collected on that instruction at runtime. To retrieve it, we
612 /// need to compute the line number of \p Inst relative to the start of its
613 /// function. We use HeaderLineno to compute the offset. We then
614 /// look up the samples collected for \p Inst using BodySamples.
616 /// \param Inst Instruction to query.
618 /// \returns the weight of \p Inst.
619 ErrorOr
<uint64_t> SampleProfileLoader::getInstWeight(const Instruction
&Inst
) {
620 const DebugLoc
&DLoc
= Inst
.getDebugLoc();
622 return std::error_code();
624 const FunctionSamples
*FS
= findFunctionSamples(Inst
);
626 return std::error_code();
628 // Ignore all intrinsics, phinodes and branch instructions.
629 // Branch and phinodes instruction usually contains debug info from sources outside of
630 // the residing basic block, thus we ignore them during annotation.
631 if (isa
<BranchInst
>(Inst
) || isa
<IntrinsicInst
>(Inst
) || isa
<PHINode
>(Inst
))
632 return std::error_code();
634 // If a direct call/invoke instruction is inlined in profile
635 // (findCalleeFunctionSamples returns non-empty result), but not inlined here,
636 // it means that the inlined callsite has no sample, thus the call
637 // instruction should have 0 count.
638 if ((isa
<CallInst
>(Inst
) || isa
<InvokeInst
>(Inst
)) &&
639 !ImmutableCallSite(&Inst
).isIndirectCall() &&
640 findCalleeFunctionSamples(Inst
))
643 const DILocation
*DIL
= DLoc
;
644 uint32_t LineOffset
= FunctionSamples::getOffset(DIL
);
645 uint32_t Discriminator
= DIL
->getBaseDiscriminator();
646 ErrorOr
<uint64_t> R
= FS
->findSamplesAt(LineOffset
, Discriminator
);
649 CoverageTracker
.markSamplesUsed(FS
, LineOffset
, Discriminator
, R
.get());
652 OptimizationRemarkAnalysis
Remark(DEBUG_TYPE
, "AppliedSamples", &Inst
);
653 Remark
<< "Applied " << ore::NV("NumSamples", *R
);
654 Remark
<< " samples from profile (offset: ";
655 Remark
<< ore::NV("LineOffset", LineOffset
);
658 Remark
<< ore::NV("Discriminator", Discriminator
);
664 LLVM_DEBUG(dbgs() << " " << DLoc
.getLine() << "."
665 << DIL
->getBaseDiscriminator() << ":" << Inst
666 << " (line offset: " << LineOffset
<< "."
667 << DIL
->getBaseDiscriminator() << " - weight: " << R
.get()
673 /// Compute the weight of a basic block.
675 /// The weight of basic block \p BB is the maximum weight of all the
676 /// instructions in BB.
678 /// \param BB The basic block to query.
680 /// \returns the weight for \p BB.
681 ErrorOr
<uint64_t> SampleProfileLoader::getBlockWeight(const BasicBlock
*BB
) {
683 bool HasWeight
= false;
684 for (auto &I
: BB
->getInstList()) {
685 const ErrorOr
<uint64_t> &R
= getInstWeight(I
);
687 Max
= std::max(Max
, R
.get());
691 return HasWeight
? ErrorOr
<uint64_t>(Max
) : std::error_code();
694 /// Compute and store the weights of every basic block.
696 /// This populates the BlockWeights map by computing
697 /// the weights of every basic block in the CFG.
699 /// \param F The function to query.
700 bool SampleProfileLoader::computeBlockWeights(Function
&F
) {
701 bool Changed
= false;
702 LLVM_DEBUG(dbgs() << "Block weights\n");
703 for (const auto &BB
: F
) {
704 ErrorOr
<uint64_t> Weight
= getBlockWeight(&BB
);
706 BlockWeights
[&BB
] = Weight
.get();
707 VisitedBlocks
.insert(&BB
);
710 LLVM_DEBUG(printBlockWeight(dbgs(), &BB
));
716 /// Get the FunctionSamples for a call instruction.
718 /// The FunctionSamples of a call/invoke instruction \p Inst is the inlined
719 /// instance in which that call instruction is calling to. It contains
720 /// all samples that resides in the inlined instance. We first find the
721 /// inlined instance in which the call instruction is from, then we
722 /// traverse its children to find the callsite with the matching
725 /// \param Inst Call/Invoke instruction to query.
727 /// \returns The FunctionSamples pointer to the inlined instance.
728 const FunctionSamples
*
729 SampleProfileLoader::findCalleeFunctionSamples(const Instruction
&Inst
) const {
730 const DILocation
*DIL
= Inst
.getDebugLoc();
735 StringRef CalleeName
;
736 if (const CallInst
*CI
= dyn_cast
<CallInst
>(&Inst
))
737 if (Function
*Callee
= CI
->getCalledFunction())
738 CalleeName
= Callee
->getName();
740 const FunctionSamples
*FS
= findFunctionSamples(Inst
);
744 return FS
->findFunctionSamplesAt(LineLocation(FunctionSamples::getOffset(DIL
),
745 DIL
->getBaseDiscriminator()),
749 /// Returns a vector of FunctionSamples that are the indirect call targets
750 /// of \p Inst. The vector is sorted by the total number of samples. Stores
751 /// the total call count of the indirect call in \p Sum.
752 std::vector
<const FunctionSamples
*>
753 SampleProfileLoader::findIndirectCallFunctionSamples(
754 const Instruction
&Inst
, uint64_t &Sum
) const {
755 const DILocation
*DIL
= Inst
.getDebugLoc();
756 std::vector
<const FunctionSamples
*> R
;
762 const FunctionSamples
*FS
= findFunctionSamples(Inst
);
766 uint32_t LineOffset
= FunctionSamples::getOffset(DIL
);
767 uint32_t Discriminator
= DIL
->getBaseDiscriminator();
769 auto T
= FS
->findCallTargetMapAt(LineOffset
, Discriminator
);
772 for (const auto &T_C
: T
.get())
774 if (const FunctionSamplesMap
*M
= FS
->findFunctionSamplesMapAt(LineLocation(
775 FunctionSamples::getOffset(DIL
), DIL
->getBaseDiscriminator()))) {
778 for (const auto &NameFS
: *M
) {
779 Sum
+= NameFS
.second
.getEntrySamples();
780 R
.push_back(&NameFS
.second
);
782 llvm::sort(R
, [](const FunctionSamples
*L
, const FunctionSamples
*R
) {
783 if (L
->getEntrySamples() != R
->getEntrySamples())
784 return L
->getEntrySamples() > R
->getEntrySamples();
785 return FunctionSamples::getGUID(L
->getName()) <
786 FunctionSamples::getGUID(R
->getName());
792 /// Get the FunctionSamples for an instruction.
794 /// The FunctionSamples of an instruction \p Inst is the inlined instance
795 /// in which that instruction is coming from. We traverse the inline stack
796 /// of that instruction, and match it with the tree nodes in the profile.
798 /// \param Inst Instruction to query.
800 /// \returns the FunctionSamples pointer to the inlined instance.
801 const FunctionSamples
*
802 SampleProfileLoader::findFunctionSamples(const Instruction
&Inst
) const {
803 const DILocation
*DIL
= Inst
.getDebugLoc();
807 auto it
= DILocation2SampleMap
.try_emplace(DIL
,nullptr);
809 it
.first
->second
= Samples
->findFunctionSamples(DIL
);
810 return it
.first
->second
;
813 bool SampleProfileLoader::inlineCallInstruction(Instruction
*I
) {
814 assert(isa
<CallInst
>(I
) || isa
<InvokeInst
>(I
));
816 Function
*CalledFunction
= CS
.getCalledFunction();
817 assert(CalledFunction
);
818 DebugLoc DLoc
= I
->getDebugLoc();
819 BasicBlock
*BB
= I
->getParent();
820 InlineParams Params
= getInlineParams();
821 Params
.ComputeFullInlineCost
= true;
822 // Checks if there is anything in the reachable portion of the callee at
823 // this callsite that makes this inlining potentially illegal. Need to
824 // set ComputeFullInlineCost, otherwise getInlineCost may return early
825 // when cost exceeds threshold without checking all IRs in the callee.
826 // The acutal cost does not matter because we only checks isNever() to
827 // see if it is legal to inline the callsite.
829 getInlineCost(cast
<CallBase
>(*I
), Params
, GetTTI(*CalledFunction
), GetAC
,
830 None
, nullptr, nullptr);
831 if (Cost
.isNever()) {
832 ORE
->emit(OptimizationRemark(DEBUG_TYPE
, "Not inline", DLoc
, BB
)
833 << "incompatible inlining");
836 InlineFunctionInfo
IFI(nullptr, &GetAC
);
837 if (InlineFunction(CS
, IFI
)) {
838 // The call to InlineFunction erases I, so we can't pass it here.
839 ORE
->emit(OptimizationRemark(DEBUG_TYPE
, "HotInline", DLoc
, BB
)
840 << "inlined hot callee '" << ore::NV("Callee", CalledFunction
)
841 << "' into '" << ore::NV("Caller", BB
->getParent()) << "'");
847 /// Iteratively inline hot callsites of a function.
849 /// Iteratively traverse all callsites of the function \p F, and find if
850 /// the corresponding inlined instance exists and is hot in profile. If
851 /// it is hot enough, inline the callsites and adds new callsites of the
852 /// callee into the caller. If the call is an indirect call, first promote
853 /// it to direct call. Each indirect call is limited with a single target.
855 /// \param F function to perform iterative inlining.
856 /// \param InlinedGUIDs a set to be updated to include all GUIDs that are
857 /// inlined in the profiled binary.
859 /// \returns True if there is any inline happened.
860 bool SampleProfileLoader::inlineHotFunctions(
861 Function
&F
, DenseSet
<GlobalValue::GUID
> &InlinedGUIDs
) {
862 DenseSet
<Instruction
*> PromotedInsns
;
864 DenseMap
<Instruction
*, const FunctionSamples
*> localNotInlinedCallSites
;
865 bool Changed
= false;
867 bool LocalChanged
= false;
868 SmallVector
<Instruction
*, 10> CIS
;
871 SmallVector
<Instruction
*, 10> Candidates
;
872 for (auto &I
: BB
.getInstList()) {
873 const FunctionSamples
*FS
= nullptr;
874 if ((isa
<CallInst
>(I
) || isa
<InvokeInst
>(I
)) &&
875 !isa
<IntrinsicInst
>(I
) && (FS
= findCalleeFunctionSamples(I
))) {
876 Candidates
.push_back(&I
);
877 if (FS
->getEntrySamples() > 0)
878 localNotInlinedCallSites
.try_emplace(&I
, FS
);
879 if (callsiteIsHot(FS
, PSI
))
884 CIS
.insert(CIS
.begin(), Candidates
.begin(), Candidates
.end());
888 Function
*CalledFunction
= CallSite(I
).getCalledFunction();
889 // Do not inline recursive calls.
890 if (CalledFunction
== &F
)
892 if (CallSite(I
).isIndirectCall()) {
893 if (PromotedInsns
.count(I
))
896 for (const auto *FS
: findIndirectCallFunctionSamples(*I
, Sum
)) {
897 if (IsThinLTOPreLink
) {
898 FS
->findInlinedFunctions(InlinedGUIDs
, F
.getParent(),
899 PSI
->getOrCompHotCountThreshold());
902 auto CalleeFunctionName
= FS
->getFuncNameInModule(F
.getParent());
903 // If it is a recursive call, we do not inline it as it could bloat
904 // the code exponentially. There is way to better handle this, e.g.
905 // clone the caller first, and inline the cloned caller if it is
906 // recursive. As llvm does not inline recursive calls, we will
907 // simply ignore it instead of handling it explicitly.
908 if (CalleeFunctionName
== F
.getName())
911 if (!callsiteIsHot(FS
, PSI
))
914 const char *Reason
= "Callee function not available";
915 auto R
= SymbolMap
.find(CalleeFunctionName
);
916 if (R
!= SymbolMap
.end() && R
->getValue() &&
917 !R
->getValue()->isDeclaration() &&
918 R
->getValue()->getSubprogram() &&
919 isLegalToPromote(CallSite(I
), R
->getValue(), &Reason
)) {
920 uint64_t C
= FS
->getEntrySamples();
922 pgo::promoteIndirectCall(I
, R
->getValue(), C
, Sum
, false, ORE
);
924 PromotedInsns
.insert(I
);
925 // If profile mismatches, we should not attempt to inline DI.
926 if ((isa
<CallInst
>(DI
) || isa
<InvokeInst
>(DI
)) &&
927 inlineCallInstruction(DI
)) {
928 localNotInlinedCallSites
.erase(I
);
933 << "\nFailed to promote indirect call to "
934 << CalleeFunctionName
<< " because " << Reason
<< "\n");
937 } else if (CalledFunction
&& CalledFunction
->getSubprogram() &&
938 !CalledFunction
->isDeclaration()) {
939 if (inlineCallInstruction(I
)) {
940 localNotInlinedCallSites
.erase(I
);
943 } else if (IsThinLTOPreLink
) {
944 findCalleeFunctionSamples(*I
)->findInlinedFunctions(
945 InlinedGUIDs
, F
.getParent(), PSI
->getOrCompHotCountThreshold());
955 // Accumulate not inlined callsite information into notInlinedSamples
956 for (const auto &Pair
: localNotInlinedCallSites
) {
957 Instruction
*I
= Pair
.getFirst();
958 Function
*Callee
= CallSite(I
).getCalledFunction();
959 if (!Callee
|| Callee
->isDeclaration())
961 const FunctionSamples
*FS
= Pair
.getSecond();
963 notInlinedCallInfo
.try_emplace(Callee
, NotInlinedProfileInfo
{0});
964 pair
.first
->second
.entryCount
+= FS
->getEntrySamples();
969 /// Find equivalence classes for the given block.
971 /// This finds all the blocks that are guaranteed to execute the same
972 /// number of times as \p BB1. To do this, it traverses all the
973 /// descendants of \p BB1 in the dominator or post-dominator tree.
975 /// A block BB2 will be in the same equivalence class as \p BB1 if
976 /// the following holds:
978 /// 1- \p BB1 is a descendant of BB2 in the opposite tree. So, if BB2
979 /// is a descendant of \p BB1 in the dominator tree, then BB2 should
980 /// dominate BB1 in the post-dominator tree.
982 /// 2- Both BB2 and \p BB1 must be in the same loop.
984 /// For every block BB2 that meets those two requirements, we set BB2's
985 /// equivalence class to \p BB1.
987 /// \param BB1 Block to check.
988 /// \param Descendants Descendants of \p BB1 in either the dom or pdom tree.
989 /// \param DomTree Opposite dominator tree. If \p Descendants is filled
990 /// with blocks from \p BB1's dominator tree, then
991 /// this is the post-dominator tree, and vice versa.
992 template <bool IsPostDom
>
993 void SampleProfileLoader::findEquivalencesFor(
994 BasicBlock
*BB1
, ArrayRef
<BasicBlock
*> Descendants
,
995 DominatorTreeBase
<BasicBlock
, IsPostDom
> *DomTree
) {
996 const BasicBlock
*EC
= EquivalenceClass
[BB1
];
997 uint64_t Weight
= BlockWeights
[EC
];
998 for (const auto *BB2
: Descendants
) {
999 bool IsDomParent
= DomTree
->dominates(BB2
, BB1
);
1000 bool IsInSameLoop
= LI
->getLoopFor(BB1
) == LI
->getLoopFor(BB2
);
1001 if (BB1
!= BB2
&& IsDomParent
&& IsInSameLoop
) {
1002 EquivalenceClass
[BB2
] = EC
;
1003 // If BB2 is visited, then the entire EC should be marked as visited.
1004 if (VisitedBlocks
.count(BB2
)) {
1005 VisitedBlocks
.insert(EC
);
1008 // If BB2 is heavier than BB1, make BB2 have the same weight
1011 // Note that we don't worry about the opposite situation here
1012 // (when BB2 is lighter than BB1). We will deal with this
1013 // during the propagation phase. Right now, we just want to
1014 // make sure that BB1 has the largest weight of all the
1015 // members of its equivalence set.
1016 Weight
= std::max(Weight
, BlockWeights
[BB2
]);
1019 if (EC
== &EC
->getParent()->getEntryBlock()) {
1020 BlockWeights
[EC
] = Samples
->getHeadSamples() + 1;
1022 BlockWeights
[EC
] = Weight
;
1026 /// Find equivalence classes.
1028 /// Since samples may be missing from blocks, we can fill in the gaps by setting
1029 /// the weights of all the blocks in the same equivalence class to the same
1030 /// weight. To compute the concept of equivalence, we use dominance and loop
1031 /// information. Two blocks B1 and B2 are in the same equivalence class if B1
1032 /// dominates B2, B2 post-dominates B1 and both are in the same loop.
1034 /// \param F The function to query.
1035 void SampleProfileLoader::findEquivalenceClasses(Function
&F
) {
1036 SmallVector
<BasicBlock
*, 8> DominatedBBs
;
1037 LLVM_DEBUG(dbgs() << "\nBlock equivalence classes\n");
1038 // Find equivalence sets based on dominance and post-dominance information.
1039 for (auto &BB
: F
) {
1040 BasicBlock
*BB1
= &BB
;
1042 // Compute BB1's equivalence class once.
1043 if (EquivalenceClass
.count(BB1
)) {
1044 LLVM_DEBUG(printBlockEquivalence(dbgs(), BB1
));
1048 // By default, blocks are in their own equivalence class.
1049 EquivalenceClass
[BB1
] = BB1
;
1051 // Traverse all the blocks dominated by BB1. We are looking for
1052 // every basic block BB2 such that:
1054 // 1- BB1 dominates BB2.
1055 // 2- BB2 post-dominates BB1.
1056 // 3- BB1 and BB2 are in the same loop nest.
1058 // If all those conditions hold, it means that BB2 is executed
1059 // as many times as BB1, so they are placed in the same equivalence
1060 // class by making BB2's equivalence class be BB1.
1061 DominatedBBs
.clear();
1062 DT
->getDescendants(BB1
, DominatedBBs
);
1063 findEquivalencesFor(BB1
, DominatedBBs
, PDT
.get());
1065 LLVM_DEBUG(printBlockEquivalence(dbgs(), BB1
));
1068 // Assign weights to equivalence classes.
1070 // All the basic blocks in the same equivalence class will execute
1071 // the same number of times. Since we know that the head block in
1072 // each equivalence class has the largest weight, assign that weight
1073 // to all the blocks in that equivalence class.
1075 dbgs() << "\nAssign the same weight to all blocks in the same class\n");
1076 for (auto &BI
: F
) {
1077 const BasicBlock
*BB
= &BI
;
1078 const BasicBlock
*EquivBB
= EquivalenceClass
[BB
];
1080 BlockWeights
[BB
] = BlockWeights
[EquivBB
];
1081 LLVM_DEBUG(printBlockWeight(dbgs(), BB
));
1085 /// Visit the given edge to decide if it has a valid weight.
1087 /// If \p E has not been visited before, we copy to \p UnknownEdge
1088 /// and increment the count of unknown edges.
1090 /// \param E Edge to visit.
1091 /// \param NumUnknownEdges Current number of unknown edges.
1092 /// \param UnknownEdge Set if E has not been visited before.
1094 /// \returns E's weight, if known. Otherwise, return 0.
1095 uint64_t SampleProfileLoader::visitEdge(Edge E
, unsigned *NumUnknownEdges
,
1096 Edge
*UnknownEdge
) {
1097 if (!VisitedEdges
.count(E
)) {
1098 (*NumUnknownEdges
)++;
1103 return EdgeWeights
[E
];
1106 /// Propagate weights through incoming/outgoing edges.
1108 /// If the weight of a basic block is known, and there is only one edge
1109 /// with an unknown weight, we can calculate the weight of that edge.
1111 /// Similarly, if all the edges have a known count, we can calculate the
1112 /// count of the basic block, if needed.
1114 /// \param F Function to process.
1115 /// \param UpdateBlockCount Whether we should update basic block counts that
1116 /// has already been annotated.
1118 /// \returns True if new weights were assigned to edges or blocks.
1119 bool SampleProfileLoader::propagateThroughEdges(Function
&F
,
1120 bool UpdateBlockCount
) {
1121 bool Changed
= false;
1122 LLVM_DEBUG(dbgs() << "\nPropagation through edges\n");
1123 for (const auto &BI
: F
) {
1124 const BasicBlock
*BB
= &BI
;
1125 const BasicBlock
*EC
= EquivalenceClass
[BB
];
1127 // Visit all the predecessor and successor edges to determine
1128 // which ones have a weight assigned already. Note that it doesn't
1129 // matter that we only keep track of a single unknown edge. The
1130 // only case we are interested in handling is when only a single
1131 // edge is unknown (see setEdgeOrBlockWeight).
1132 for (unsigned i
= 0; i
< 2; i
++) {
1133 uint64_t TotalWeight
= 0;
1134 unsigned NumUnknownEdges
= 0, NumTotalEdges
= 0;
1135 Edge UnknownEdge
, SelfReferentialEdge
, SingleEdge
;
1138 // First, visit all predecessor edges.
1139 NumTotalEdges
= Predecessors
[BB
].size();
1140 for (auto *Pred
: Predecessors
[BB
]) {
1141 Edge E
= std::make_pair(Pred
, BB
);
1142 TotalWeight
+= visitEdge(E
, &NumUnknownEdges
, &UnknownEdge
);
1143 if (E
.first
== E
.second
)
1144 SelfReferentialEdge
= E
;
1146 if (NumTotalEdges
== 1) {
1147 SingleEdge
= std::make_pair(Predecessors
[BB
][0], BB
);
1150 // On the second round, visit all successor edges.
1151 NumTotalEdges
= Successors
[BB
].size();
1152 for (auto *Succ
: Successors
[BB
]) {
1153 Edge E
= std::make_pair(BB
, Succ
);
1154 TotalWeight
+= visitEdge(E
, &NumUnknownEdges
, &UnknownEdge
);
1156 if (NumTotalEdges
== 1) {
1157 SingleEdge
= std::make_pair(BB
, Successors
[BB
][0]);
1161 // After visiting all the edges, there are three cases that we
1162 // can handle immediately:
1164 // - All the edge weights are known (i.e., NumUnknownEdges == 0).
1165 // In this case, we simply check that the sum of all the edges
1166 // is the same as BB's weight. If not, we change BB's weight
1167 // to match. Additionally, if BB had not been visited before,
1168 // we mark it visited.
1170 // - Only one edge is unknown and BB has already been visited.
1171 // In this case, we can compute the weight of the edge by
1172 // subtracting the total block weight from all the known
1173 // edge weights. If the edges weight more than BB, then the
1174 // edge of the last remaining edge is set to zero.
1176 // - There exists a self-referential edge and the weight of BB is
1177 // known. In this case, this edge can be based on BB's weight.
1178 // We add up all the other known edges and set the weight on
1179 // the self-referential edge as we did in the previous case.
1181 // In any other case, we must continue iterating. Eventually,
1182 // all edges will get a weight, or iteration will stop when
1183 // it reaches SampleProfileMaxPropagateIterations.
1184 if (NumUnknownEdges
<= 1) {
1185 uint64_t &BBWeight
= BlockWeights
[EC
];
1186 if (NumUnknownEdges
== 0) {
1187 if (!VisitedBlocks
.count(EC
)) {
1188 // If we already know the weight of all edges, the weight of the
1189 // basic block can be computed. It should be no larger than the sum
1190 // of all edge weights.
1191 if (TotalWeight
> BBWeight
) {
1192 BBWeight
= TotalWeight
;
1194 LLVM_DEBUG(dbgs() << "All edge weights for " << BB
->getName()
1195 << " known. Set weight for block: ";
1196 printBlockWeight(dbgs(), BB
););
1198 } else if (NumTotalEdges
== 1 &&
1199 EdgeWeights
[SingleEdge
] < BlockWeights
[EC
]) {
1200 // If there is only one edge for the visited basic block, use the
1201 // block weight to adjust edge weight if edge weight is smaller.
1202 EdgeWeights
[SingleEdge
] = BlockWeights
[EC
];
1205 } else if (NumUnknownEdges
== 1 && VisitedBlocks
.count(EC
)) {
1206 // If there is a single unknown edge and the block has been
1207 // visited, then we can compute E's weight.
1208 if (BBWeight
>= TotalWeight
)
1209 EdgeWeights
[UnknownEdge
] = BBWeight
- TotalWeight
;
1211 EdgeWeights
[UnknownEdge
] = 0;
1212 const BasicBlock
*OtherEC
;
1214 OtherEC
= EquivalenceClass
[UnknownEdge
.first
];
1216 OtherEC
= EquivalenceClass
[UnknownEdge
.second
];
1217 // Edge weights should never exceed the BB weights it connects.
1218 if (VisitedBlocks
.count(OtherEC
) &&
1219 EdgeWeights
[UnknownEdge
] > BlockWeights
[OtherEC
])
1220 EdgeWeights
[UnknownEdge
] = BlockWeights
[OtherEC
];
1221 VisitedEdges
.insert(UnknownEdge
);
1223 LLVM_DEBUG(dbgs() << "Set weight for edge: ";
1224 printEdgeWeight(dbgs(), UnknownEdge
));
1226 } else if (VisitedBlocks
.count(EC
) && BlockWeights
[EC
] == 0) {
1227 // If a block Weights 0, all its in/out edges should weight 0.
1229 for (auto *Pred
: Predecessors
[BB
]) {
1230 Edge E
= std::make_pair(Pred
, BB
);
1232 VisitedEdges
.insert(E
);
1235 for (auto *Succ
: Successors
[BB
]) {
1236 Edge E
= std::make_pair(BB
, Succ
);
1238 VisitedEdges
.insert(E
);
1241 } else if (SelfReferentialEdge
.first
&& VisitedBlocks
.count(EC
)) {
1242 uint64_t &BBWeight
= BlockWeights
[BB
];
1243 // We have a self-referential edge and the weight of BB is known.
1244 if (BBWeight
>= TotalWeight
)
1245 EdgeWeights
[SelfReferentialEdge
] = BBWeight
- TotalWeight
;
1247 EdgeWeights
[SelfReferentialEdge
] = 0;
1248 VisitedEdges
.insert(SelfReferentialEdge
);
1250 LLVM_DEBUG(dbgs() << "Set self-referential edge weight to: ";
1251 printEdgeWeight(dbgs(), SelfReferentialEdge
));
1253 if (UpdateBlockCount
&& !VisitedBlocks
.count(EC
) && TotalWeight
> 0) {
1254 BlockWeights
[EC
] = TotalWeight
;
1255 VisitedBlocks
.insert(EC
);
1264 /// Build in/out edge lists for each basic block in the CFG.
1266 /// We are interested in unique edges. If a block B1 has multiple
1267 /// edges to another block B2, we only add a single B1->B2 edge.
1268 void SampleProfileLoader::buildEdges(Function
&F
) {
1269 for (auto &BI
: F
) {
1270 BasicBlock
*B1
= &BI
;
1272 // Add predecessors for B1.
1273 SmallPtrSet
<BasicBlock
*, 16> Visited
;
1274 if (!Predecessors
[B1
].empty())
1275 llvm_unreachable("Found a stale predecessors list in a basic block.");
1276 for (pred_iterator PI
= pred_begin(B1
), PE
= pred_end(B1
); PI
!= PE
; ++PI
) {
1277 BasicBlock
*B2
= *PI
;
1278 if (Visited
.insert(B2
).second
)
1279 Predecessors
[B1
].push_back(B2
);
1282 // Add successors for B1.
1284 if (!Successors
[B1
].empty())
1285 llvm_unreachable("Found a stale successors list in a basic block.");
1286 for (succ_iterator SI
= succ_begin(B1
), SE
= succ_end(B1
); SI
!= SE
; ++SI
) {
1287 BasicBlock
*B2
= *SI
;
1288 if (Visited
.insert(B2
).second
)
1289 Successors
[B1
].push_back(B2
);
1294 /// Returns the sorted CallTargetMap \p M by count in descending order.
1295 static SmallVector
<InstrProfValueData
, 2> GetSortedValueDataFromCallTargets(
1296 const SampleRecord::CallTargetMap
& M
) {
1297 SmallVector
<InstrProfValueData
, 2> R
;
1298 for (const auto &I
: SampleRecord::SortCallTargets(M
)) {
1299 R
.emplace_back(InstrProfValueData
{FunctionSamples::getGUID(I
.first
), I
.second
});
1304 /// Propagate weights into edges
1306 /// The following rules are applied to every block BB in the CFG:
1308 /// - If BB has a single predecessor/successor, then the weight
1309 /// of that edge is the weight of the block.
1311 /// - If all incoming or outgoing edges are known except one, and the
1312 /// weight of the block is already known, the weight of the unknown
1313 /// edge will be the weight of the block minus the sum of all the known
1314 /// edges. If the sum of all the known edges is larger than BB's weight,
1315 /// we set the unknown edge weight to zero.
1317 /// - If there is a self-referential edge, and the weight of the block is
1318 /// known, the weight for that edge is set to the weight of the block
1319 /// minus the weight of the other incoming edges to that block (if
1321 void SampleProfileLoader::propagateWeights(Function
&F
) {
1322 bool Changed
= true;
1325 // If BB weight is larger than its corresponding loop's header BB weight,
1326 // use the BB weight to replace the loop header BB weight.
1327 for (auto &BI
: F
) {
1328 BasicBlock
*BB
= &BI
;
1329 Loop
*L
= LI
->getLoopFor(BB
);
1333 BasicBlock
*Header
= L
->getHeader();
1334 if (Header
&& BlockWeights
[BB
] > BlockWeights
[Header
]) {
1335 BlockWeights
[Header
] = BlockWeights
[BB
];
1339 // Before propagation starts, build, for each block, a list of
1340 // unique predecessors and successors. This is necessary to handle
1341 // identical edges in multiway branches. Since we visit all blocks and all
1342 // edges of the CFG, it is cleaner to build these lists once at the start
1346 // Propagate until we converge or we go past the iteration limit.
1347 while (Changed
&& I
++ < SampleProfileMaxPropagateIterations
) {
1348 Changed
= propagateThroughEdges(F
, false);
1351 // The first propagation propagates BB counts from annotated BBs to unknown
1352 // BBs. The 2nd propagation pass resets edges weights, and use all BB weights
1353 // to propagate edge weights.
1354 VisitedEdges
.clear();
1356 while (Changed
&& I
++ < SampleProfileMaxPropagateIterations
) {
1357 Changed
= propagateThroughEdges(F
, false);
1360 // The 3rd propagation pass allows adjust annotated BB weights that are
1363 while (Changed
&& I
++ < SampleProfileMaxPropagateIterations
) {
1364 Changed
= propagateThroughEdges(F
, true);
1367 // Generate MD_prof metadata for every branch instruction using the
1368 // edge weights computed during propagation.
1369 LLVM_DEBUG(dbgs() << "\nPropagation complete. Setting branch weights\n");
1370 LLVMContext
&Ctx
= F
.getContext();
1372 for (auto &BI
: F
) {
1373 BasicBlock
*BB
= &BI
;
1375 if (BlockWeights
[BB
]) {
1376 for (auto &I
: BB
->getInstList()) {
1377 if (!isa
<CallInst
>(I
) && !isa
<InvokeInst
>(I
))
1380 if (!CS
.getCalledFunction()) {
1381 const DebugLoc
&DLoc
= I
.getDebugLoc();
1384 const DILocation
*DIL
= DLoc
;
1385 uint32_t LineOffset
= FunctionSamples::getOffset(DIL
);
1386 uint32_t Discriminator
= DIL
->getBaseDiscriminator();
1388 const FunctionSamples
*FS
= findFunctionSamples(I
);
1391 auto T
= FS
->findCallTargetMapAt(LineOffset
, Discriminator
);
1392 if (!T
|| T
.get().empty())
1394 SmallVector
<InstrProfValueData
, 2> SortedCallTargets
=
1395 GetSortedValueDataFromCallTargets(T
.get());
1397 findIndirectCallFunctionSamples(I
, Sum
);
1398 annotateValueSite(*I
.getParent()->getParent()->getParent(), I
,
1399 SortedCallTargets
, Sum
, IPVK_IndirectCallTarget
,
1400 SortedCallTargets
.size());
1401 } else if (!isa
<IntrinsicInst
>(&I
)) {
1402 I
.setMetadata(LLVMContext::MD_prof
,
1403 MDB
.createBranchWeights(
1404 {static_cast<uint32_t>(BlockWeights
[BB
])}));
1408 Instruction
*TI
= BB
->getTerminator();
1409 if (TI
->getNumSuccessors() == 1)
1411 if (!isa
<BranchInst
>(TI
) && !isa
<SwitchInst
>(TI
))
1414 DebugLoc BranchLoc
= TI
->getDebugLoc();
1415 LLVM_DEBUG(dbgs() << "\nGetting weights for branch at line "
1416 << ((BranchLoc
) ? Twine(BranchLoc
.getLine())
1417 : Twine("<UNKNOWN LOCATION>"))
1419 SmallVector
<uint32_t, 4> Weights
;
1420 uint32_t MaxWeight
= 0;
1421 Instruction
*MaxDestInst
;
1422 for (unsigned I
= 0; I
< TI
->getNumSuccessors(); ++I
) {
1423 BasicBlock
*Succ
= TI
->getSuccessor(I
);
1424 Edge E
= std::make_pair(BB
, Succ
);
1425 uint64_t Weight
= EdgeWeights
[E
];
1426 LLVM_DEBUG(dbgs() << "\t"; printEdgeWeight(dbgs(), E
));
1427 // Use uint32_t saturated arithmetic to adjust the incoming weights,
1428 // if needed. Sample counts in profiles are 64-bit unsigned values,
1429 // but internally branch weights are expressed as 32-bit values.
1430 if (Weight
> std::numeric_limits
<uint32_t>::max()) {
1431 LLVM_DEBUG(dbgs() << " (saturated due to uint32_t overflow)");
1432 Weight
= std::numeric_limits
<uint32_t>::max();
1434 // Weight is added by one to avoid propagation errors introduced by
1436 Weights
.push_back(static_cast<uint32_t>(Weight
+ 1));
1438 if (Weight
> MaxWeight
) {
1440 MaxDestInst
= Succ
->getFirstNonPHIOrDbgOrLifetime();
1445 uint64_t TempWeight
;
1446 // Only set weights if there is at least one non-zero weight.
1447 // In any other case, let the analyzer set weights.
1448 // Do not set weights if the weights are present. In ThinLTO, the profile
1449 // annotation is done twice. If the first annotation already set the
1450 // weights, the second pass does not need to set it.
1451 if (MaxWeight
> 0 && !TI
->extractProfTotalWeight(TempWeight
)) {
1452 LLVM_DEBUG(dbgs() << "SUCCESS. Found non-zero weights.\n");
1453 TI
->setMetadata(LLVMContext::MD_prof
,
1454 MDB
.createBranchWeights(Weights
));
1456 return OptimizationRemark(DEBUG_TYPE
, "PopularDest", MaxDestInst
)
1457 << "most popular destination for conditional branches at "
1458 << ore::NV("CondBranchesLoc", BranchLoc
);
1461 LLVM_DEBUG(dbgs() << "SKIPPED. All branch weights are zero.\n");
1466 /// Get the line number for the function header.
1468 /// This looks up function \p F in the current compilation unit and
1469 /// retrieves the line number where the function is defined. This is
1470 /// line 0 for all the samples read from the profile file. Every line
1471 /// number is relative to this line.
1473 /// \param F Function object to query.
1475 /// \returns the line number where \p F is defined. If it returns 0,
1476 /// it means that there is no debug information available for \p F.
1477 unsigned SampleProfileLoader::getFunctionLoc(Function
&F
) {
1478 if (DISubprogram
*S
= F
.getSubprogram())
1479 return S
->getLine();
1481 if (NoWarnSampleUnused
)
1484 // If the start of \p F is missing, emit a diagnostic to inform the user
1485 // about the missed opportunity.
1486 F
.getContext().diagnose(DiagnosticInfoSampleProfile(
1487 "No debug information found in function " + F
.getName() +
1488 ": Function profile not used",
1493 void SampleProfileLoader::computeDominanceAndLoopInfo(Function
&F
) {
1494 DT
.reset(new DominatorTree
);
1497 PDT
.reset(new PostDominatorTree(F
));
1499 LI
.reset(new LoopInfo
);
1503 /// Generate branch weight metadata for all branches in \p F.
1505 /// Branch weights are computed out of instruction samples using a
1506 /// propagation heuristic. Propagation proceeds in 3 phases:
1508 /// 1- Assignment of block weights. All the basic blocks in the function
1509 /// are initial assigned the same weight as their most frequently
1510 /// executed instruction.
1512 /// 2- Creation of equivalence classes. Since samples may be missing from
1513 /// blocks, we can fill in the gaps by setting the weights of all the
1514 /// blocks in the same equivalence class to the same weight. To compute
1515 /// the concept of equivalence, we use dominance and loop information.
1516 /// Two blocks B1 and B2 are in the same equivalence class if B1
1517 /// dominates B2, B2 post-dominates B1 and both are in the same loop.
1519 /// 3- Propagation of block weights into edges. This uses a simple
1520 /// propagation heuristic. The following rules are applied to every
1521 /// block BB in the CFG:
1523 /// - If BB has a single predecessor/successor, then the weight
1524 /// of that edge is the weight of the block.
1526 /// - If all the edges are known except one, and the weight of the
1527 /// block is already known, the weight of the unknown edge will
1528 /// be the weight of the block minus the sum of all the known
1529 /// edges. If the sum of all the known edges is larger than BB's weight,
1530 /// we set the unknown edge weight to zero.
1532 /// - If there is a self-referential edge, and the weight of the block is
1533 /// known, the weight for that edge is set to the weight of the block
1534 /// minus the weight of the other incoming edges to that block (if
1537 /// Since this propagation is not guaranteed to finalize for every CFG, we
1538 /// only allow it to proceed for a limited number of iterations (controlled
1539 /// by -sample-profile-max-propagate-iterations).
1541 /// FIXME: Try to replace this propagation heuristic with a scheme
1542 /// that is guaranteed to finalize. A work-list approach similar to
1543 /// the standard value propagation algorithm used by SSA-CCP might
1546 /// Once all the branch weights are computed, we emit the MD_prof
1547 /// metadata on BB using the computed values for each of its branches.
1549 /// \param F The function to query.
1551 /// \returns true if \p F was modified. Returns false, otherwise.
1552 bool SampleProfileLoader::emitAnnotations(Function
&F
) {
1553 bool Changed
= false;
1555 if (getFunctionLoc(F
) == 0)
1558 LLVM_DEBUG(dbgs() << "Line number for the first instruction in "
1559 << F
.getName() << ": " << getFunctionLoc(F
) << "\n");
1561 DenseSet
<GlobalValue::GUID
> InlinedGUIDs
;
1562 Changed
|= inlineHotFunctions(F
, InlinedGUIDs
);
1564 // Compute basic block weights.
1565 Changed
|= computeBlockWeights(F
);
1568 // Add an entry count to the function using the samples gathered at the
1570 // Sets the GUIDs that are inlined in the profiled binary. This is used
1571 // for ThinLink to make correct liveness analysis, and also make the IR
1572 // match the profiled binary before annotation.
1574 ProfileCount(Samples
->getHeadSamples() + 1, Function::PCT_Real
),
1577 // Compute dominance and loop info needed for propagation.
1578 computeDominanceAndLoopInfo(F
);
1580 // Find equivalence classes.
1581 findEquivalenceClasses(F
);
1583 // Propagate weights to all edges.
1584 propagateWeights(F
);
1587 // If coverage checking was requested, compute it now.
1588 if (SampleProfileRecordCoverage
) {
1589 unsigned Used
= CoverageTracker
.countUsedRecords(Samples
, PSI
);
1590 unsigned Total
= CoverageTracker
.countBodyRecords(Samples
, PSI
);
1591 unsigned Coverage
= CoverageTracker
.computeCoverage(Used
, Total
);
1592 if (Coverage
< SampleProfileRecordCoverage
) {
1593 F
.getContext().diagnose(DiagnosticInfoSampleProfile(
1594 F
.getSubprogram()->getFilename(), getFunctionLoc(F
),
1595 Twine(Used
) + " of " + Twine(Total
) + " available profile records (" +
1596 Twine(Coverage
) + "%) were applied",
1601 if (SampleProfileSampleCoverage
) {
1602 uint64_t Used
= CoverageTracker
.getTotalUsedSamples();
1603 uint64_t Total
= CoverageTracker
.countBodySamples(Samples
, PSI
);
1604 unsigned Coverage
= CoverageTracker
.computeCoverage(Used
, Total
);
1605 if (Coverage
< SampleProfileSampleCoverage
) {
1606 F
.getContext().diagnose(DiagnosticInfoSampleProfile(
1607 F
.getSubprogram()->getFilename(), getFunctionLoc(F
),
1608 Twine(Used
) + " of " + Twine(Total
) + " available profile samples (" +
1609 Twine(Coverage
) + "%) were applied",
1616 char SampleProfileLoaderLegacyPass::ID
= 0;
1618 INITIALIZE_PASS_BEGIN(SampleProfileLoaderLegacyPass
, "sample-profile",
1619 "Sample Profile loader", false, false)
1620 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker
)
1621 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass
)
1622 INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass
)
1623 INITIALIZE_PASS_END(SampleProfileLoaderLegacyPass
, "sample-profile",
1624 "Sample Profile loader", false, false)
1626 bool SampleProfileLoader::doInitialization(Module
&M
) {
1627 auto &Ctx
= M
.getContext();
1628 auto ReaderOrErr
= SampleProfileReader::create(Filename
, Ctx
);
1629 if (std::error_code EC
= ReaderOrErr
.getError()) {
1630 std::string Msg
= "Could not open profile: " + EC
.message();
1631 Ctx
.diagnose(DiagnosticInfoSampleProfile(Filename
, Msg
));
1634 Reader
= std::move(ReaderOrErr
.get());
1635 Reader
->collectFuncsToUse(M
);
1636 ProfileIsValid
= (Reader
->read() == sampleprof_error::success
);
1638 if (!RemappingFilename
.empty()) {
1639 // Apply profile remappings to the loaded profile data if requested.
1640 // For now, we only support remapping symbols encoded using the Itanium
1641 // C++ ABI's name mangling scheme.
1642 ReaderOrErr
= SampleProfileReaderItaniumRemapper::create(
1643 RemappingFilename
, Ctx
, std::move(Reader
));
1644 if (std::error_code EC
= ReaderOrErr
.getError()) {
1645 std::string Msg
= "Could not open profile remapping file: " + EC
.message();
1646 Ctx
.diagnose(DiagnosticInfoSampleProfile(Filename
, Msg
));
1649 Reader
= std::move(ReaderOrErr
.get());
1650 ProfileIsValid
= (Reader
->read() == sampleprof_error::success
);
1655 ModulePass
*llvm::createSampleProfileLoaderPass() {
1656 return new SampleProfileLoaderLegacyPass();
1659 ModulePass
*llvm::createSampleProfileLoaderPass(StringRef Name
) {
1660 return new SampleProfileLoaderLegacyPass(Name
);
1663 bool SampleProfileLoader::runOnModule(Module
&M
, ModuleAnalysisManager
*AM
,
1664 ProfileSummaryInfo
*_PSI
) {
1665 GUIDToFuncNameMapper
Mapper(M
, *Reader
, GUIDToFuncNameMap
);
1666 if (!ProfileIsValid
)
1670 if (M
.getProfileSummary(/* IsCS */ false) == nullptr)
1671 M
.setProfileSummary(Reader
->getSummary().getMD(M
.getContext()),
1672 ProfileSummary::PSK_Sample
);
1674 // Compute the total number of samples collected in this profile.
1675 for (const auto &I
: Reader
->getProfiles())
1676 TotalCollectedSamples
+= I
.second
.getTotalSamples();
1678 // Populate the symbol map.
1679 for (const auto &N_F
: M
.getValueSymbolTable()) {
1680 StringRef OrigName
= N_F
.getKey();
1681 Function
*F
= dyn_cast
<Function
>(N_F
.getValue());
1684 SymbolMap
[OrigName
] = F
;
1685 auto pos
= OrigName
.find('.');
1686 if (pos
!= StringRef::npos
) {
1687 StringRef NewName
= OrigName
.substr(0, pos
);
1688 auto r
= SymbolMap
.insert(std::make_pair(NewName
, F
));
1689 // Failiing to insert means there is already an entry in SymbolMap,
1690 // thus there are multiple functions that are mapped to the same
1691 // stripped name. In this case of name conflicting, set the value
1692 // to nullptr to avoid confusion.
1694 r
.first
->second
= nullptr;
1698 bool retval
= false;
1700 if (!F
.isDeclaration()) {
1701 clearFunctionData();
1702 retval
|= runOnFunction(F
, AM
);
1705 // Account for cold calls not inlined....
1706 for (const std::pair
<Function
*, NotInlinedProfileInfo
> &pair
:
1708 updateProfileCallee(pair
.first
, pair
.second
.entryCount
);
1713 bool SampleProfileLoaderLegacyPass::runOnModule(Module
&M
) {
1714 ACT
= &getAnalysis
<AssumptionCacheTracker
>();
1715 TTIWP
= &getAnalysis
<TargetTransformInfoWrapperPass
>();
1716 ProfileSummaryInfo
*PSI
=
1717 &getAnalysis
<ProfileSummaryInfoWrapperPass
>().getPSI();
1718 return SampleLoader
.runOnModule(M
, nullptr, PSI
);
1721 bool SampleProfileLoader::runOnFunction(Function
&F
, ModuleAnalysisManager
*AM
) {
1723 DILocation2SampleMap
.clear();
1724 // By default the entry count is initialized to -1, which will be treated
1725 // conservatively by getEntryCount as the same as unknown (None). This is
1726 // to avoid newly added code to be treated as cold. If we have samples
1727 // this will be overwritten in emitAnnotations.
1728 // If ProfileSampleAccurate is true or F has profile-sample-accurate
1729 // attribute, initialize the entry count to 0 so callsites or functions
1730 // unsampled will be treated as cold.
1731 uint64_t initialEntryCount
=
1732 (ProfileSampleAccurate
|| F
.hasFnAttribute("profile-sample-accurate"))
1735 F
.setEntryCount(ProfileCount(initialEntryCount
, Function::PCT_Real
));
1736 std::unique_ptr
<OptimizationRemarkEmitter
> OwnedORE
;
1739 AM
->getResult
<FunctionAnalysisManagerModuleProxy
>(*F
.getParent())
1741 ORE
= &FAM
.getResult
<OptimizationRemarkEmitterAnalysis
>(F
);
1743 OwnedORE
= std::make_unique
<OptimizationRemarkEmitter
>(&F
);
1744 ORE
= OwnedORE
.get();
1746 Samples
= Reader
->getSamplesFor(F
);
1747 if (Samples
&& !Samples
->empty())
1748 return emitAnnotations(F
);
1752 PreservedAnalyses
SampleProfileLoaderPass::run(Module
&M
,
1753 ModuleAnalysisManager
&AM
) {
1754 FunctionAnalysisManager
&FAM
=
1755 AM
.getResult
<FunctionAnalysisManagerModuleProxy
>(M
).getManager();
1757 auto GetAssumptionCache
= [&](Function
&F
) -> AssumptionCache
& {
1758 return FAM
.getResult
<AssumptionAnalysis
>(F
);
1760 auto GetTTI
= [&](Function
&F
) -> TargetTransformInfo
& {
1761 return FAM
.getResult
<TargetIRAnalysis
>(F
);
1764 SampleProfileLoader
SampleLoader(
1765 ProfileFileName
.empty() ? SampleProfileFile
: ProfileFileName
,
1766 ProfileRemappingFileName
.empty() ? SampleProfileRemappingFile
1767 : ProfileRemappingFileName
,
1768 IsThinLTOPreLink
, GetAssumptionCache
, GetTTI
);
1770 SampleLoader
.doInitialization(M
);
1772 ProfileSummaryInfo
*PSI
= &AM
.getResult
<ProfileSummaryAnalysis
>(M
);
1773 if (!SampleLoader
.runOnModule(M
, &AM
, PSI
))
1774 return PreservedAnalyses::all();
1776 return PreservedAnalyses::none();