15#ifndef LLVM_TRANSFORMS_UTILS_SAMPLEPROFILELOADERBASEIMPL_H
16#define LLVM_TRANSFORMS_UTILS_SAMPLEPROFILELOADERBASEIMPL_H
48using namespace sampleprof;
49using namespace sampleprofutil;
56#define DEBUG_TYPE "sample-profile-impl"
58namespace afdo_detail {
77 return &
F->getEntryBlock();
95 for (
const auto *Operand : FuncInfo->operands()) {
96 const auto *MD = cast<MDNode>(Operand);
97 auto GUID = mdconst::dyn_extract<ConstantInt>(MD->getOperand(0))
99 auto Hash = mdconst::dyn_extract<ConstantInt>(MD->getOperand(1))
107 auto I = GUIDToProbeDescMap.
find(GUID);
108 return I == GUIDToProbeDescMap.
end() ? nullptr : &
I->second;
130 bool IsAvailableExternallyLinkage =
144 if (IsAvailableExternallyLinkage || !
Desc)
145 return !
F.hasFnAttribute(
"profile-checksum-mismatch");
156 return F.isDeclaration() || !
F.hasFnAttribute(
"use-sample-profile");
161 std::vector<Function *> &FunctionOrderList) {
168 FunctionOrderList.push_back(&
F);
172 std::reverse(FunctionOrderList.begin(), FunctionOrderList.end());
183 using BT = std::remove_pointer_t<NodeRef>;
207 using Edge = std::pair<const BasicBlockT *, const BasicBlockT *>;
306 std::unique_ptr<SampleProfileReader>
Reader;
336template <
typename BT>
338 BlockWeights.clear();
340 VisitedBlocks.clear();
341 VisitedEdges.clear();
342 EquivalenceClass.clear();
348 Predecessors.clear();
350 CoverageTracker.clear();
358template <
typename BT>
360 OS <<
"weight[" <<
E.first->getName() <<
"->" <<
E.second->getName()
361 <<
"]: " << EdgeWeights[
E] <<
"\n";
368template <
typename BT>
372 OS <<
"equivalence[" << BB->getName()
373 <<
"]: " << ((Equiv) ? EquivalenceClass[BB]->
getName() :
"NONE") <<
"\n";
380template <
typename BT>
383 const auto &
I = BlockWeights.find(BB);
384 uint64_t W = (
I == BlockWeights.end() ? 0 :
I->second);
385 OS <<
"weight[" << BB->getName() <<
"]: " << W <<
"\n";
400template <
typename BT>
404 return getProbeWeight(Inst);
405 return getInstWeightImpl(Inst);
408template <
typename BT>
413 return std::error_code();
415 const DebugLoc &DLoc = Inst.getDebugLoc();
417 return std::error_code();
423 Discriminator = DIL->getDiscriminator();
430 CoverageTracker.markSamplesUsed(FS, LineOffset, Discriminator, R.get());
435 Remark <<
" samples from profile (offset: ";
446 << Inst <<
" (line offset: " << LineOffset <<
"."
447 << Discriminator <<
" - weight: " << R.get() <<
")\n");
455template <
typename BT>
459 "Profile is not pseudo probe based");
464 return std::error_code();
479 auto R = FS->findSamplesAt(Probe->Id, Probe->Discriminator);
481 uint64_t Samples = R.get() * Probe->Factor;
482 bool FirstMark = CoverageTracker.markSamplesUsed(FS, Probe->Id, 0, Samples);
487 Remark <<
" samples from profile (ProbeId=";
489 if (Probe->Discriminator) {
495 Remark <<
", OriginalSamples=";
502 if (Probe->Discriminator)
503 dbgs() <<
"." << Probe->Discriminator;
504 dbgs() <<
":" << Inst <<
" - weight: " << R.get()
505 <<
" - factor: " <<
format(
"%0.2f", Probe->Factor) <<
")\n";});
519template <
typename BT>
523 bool HasWeight =
false;
524 for (
auto &
I : *BB) {
527 Max = std::max(Max, R.get());
540template <
typename BT>
542 bool Changed =
false;
544 for (
const auto &BB :
F) {
547 BlockWeights[&BB] = Weight.
get();
548 VisitedBlocks.insert(&BB);
566template <
typename BT>
573 auto it = DILocation2SampleMap.try_emplace(DIL,
nullptr);
575 it.first->second = Samples->findFunctionSamples(DIL, Reader->getRemapper());
577 return it.first->second;
603template <
typename BT>
609 for (
const auto *BB2 : Descendants) {
610 bool IsDomParent = DomTree->dominates(BB2, BB1);
611 bool IsInSameLoop = LI->getLoopFor(BB1) == LI->getLoopFor(BB2);
612 if (BB1 != BB2 && IsDomParent && IsInSameLoop) {
613 EquivalenceClass[BB2] = EC;
615 if (VisitedBlocks.count(BB2)) {
616 VisitedBlocks.insert(EC);
627 Weight = std::max(Weight, BlockWeights[BB2]);
630 const BasicBlockT *EntryBB = getEntryBB(EC->getParent());
632 BlockWeights[EC] = Samples->getHeadSamples() + 1;
634 BlockWeights[EC] = Weight;
647template <
typename BT>
656 if (EquivalenceClass.count(BB1)) {
662 EquivalenceClass[BB1] = BB1;
674 DominatedBBs.
clear();
675 DT->getDescendants(BB1, DominatedBBs);
676 findEquivalencesFor(BB1, DominatedBBs, &*PDT);
688 dbgs() <<
"\nAssign the same weight to all blocks in the same class\n");
693 BlockWeights[BB] = BlockWeights[EquivBB];
708template <
typename BT>
710 unsigned *NumUnknownEdges,
712 if (!VisitedEdges.count(
E)) {
713 (*NumUnknownEdges)++;
718 return EdgeWeights[
E];
734template <
typename BT>
737 bool Changed =
false;
739 for (
const auto &BI :
F) {
748 for (
unsigned i = 0; i < 2; i++) {
750 unsigned NumUnknownEdges = 0, NumTotalEdges = 0;
751 Edge UnknownEdge, SelfReferentialEdge, SingleEdge;
755 NumTotalEdges = Predecessors[BB].size();
756 for (
auto *Pred : Predecessors[BB]) {
757 Edge E = std::make_pair(Pred, BB);
758 TotalWeight += visitEdge(
E, &NumUnknownEdges, &UnknownEdge);
759 if (
E.first ==
E.second)
760 SelfReferentialEdge =
E;
762 if (NumTotalEdges == 1) {
763 SingleEdge = std::make_pair(Predecessors[BB][0], BB);
767 NumTotalEdges = Successors[BB].size();
768 for (
auto *Succ : Successors[BB]) {
769 Edge E = std::make_pair(BB, Succ);
770 TotalWeight += visitEdge(
E, &NumUnknownEdges, &UnknownEdge);
772 if (NumTotalEdges == 1) {
773 SingleEdge = std::make_pair(BB, Successors[BB][0]);
800 if (NumUnknownEdges <= 1) {
801 uint64_t &BBWeight = BlockWeights[EC];
802 if (NumUnknownEdges == 0) {
803 if (!VisitedBlocks.count(EC)) {
807 if (TotalWeight > BBWeight) {
808 BBWeight = TotalWeight;
811 <<
" known. Set weight for block: ";
812 printBlockWeight(
dbgs(), BB););
814 }
else if (NumTotalEdges == 1 &&
815 EdgeWeights[SingleEdge] < BlockWeights[EC]) {
818 EdgeWeights[SingleEdge] = BlockWeights[EC];
821 }
else if (NumUnknownEdges == 1 && VisitedBlocks.count(EC)) {
824 if (BBWeight >= TotalWeight)
825 EdgeWeights[UnknownEdge] = BBWeight - TotalWeight;
827 EdgeWeights[UnknownEdge] = 0;
830 OtherEC = EquivalenceClass[UnknownEdge.first];
832 OtherEC = EquivalenceClass[UnknownEdge.second];
834 if (VisitedBlocks.count(OtherEC) &&
835 EdgeWeights[UnknownEdge] > BlockWeights[OtherEC])
836 EdgeWeights[UnknownEdge] = BlockWeights[OtherEC];
837 VisitedEdges.insert(UnknownEdge);
840 printEdgeWeight(
dbgs(), UnknownEdge));
842 }
else if (VisitedBlocks.count(EC) && BlockWeights[EC] == 0) {
845 for (
auto *Pred : Predecessors[BB]) {
846 Edge E = std::make_pair(Pred, BB);
848 VisitedEdges.insert(
E);
851 for (
auto *Succ : Successors[BB]) {
852 Edge E = std::make_pair(BB, Succ);
854 VisitedEdges.insert(
E);
857 }
else if (SelfReferentialEdge.first && VisitedBlocks.count(EC)) {
858 uint64_t &BBWeight = BlockWeights[BB];
860 if (BBWeight >= TotalWeight)
861 EdgeWeights[SelfReferentialEdge] = BBWeight - TotalWeight;
863 EdgeWeights[SelfReferentialEdge] = 0;
864 VisitedEdges.insert(SelfReferentialEdge);
867 printEdgeWeight(
dbgs(), SelfReferentialEdge));
869 if (UpdateBlockCount && !VisitedBlocks.count(EC) && TotalWeight > 0) {
870 BlockWeights[EC] = TotalWeight;
871 VisitedBlocks.insert(EC);
884template <
typename BT>
891 if (!Predecessors[B1].empty())
893 for (
auto *B2 : getPredecessors(B1))
894 if (Visited.
insert(B2).second)
895 Predecessors[B1].push_back(B2);
899 if (!Successors[B1].empty())
901 for (
auto *B2 : getSuccessors(B1))
902 if (Visited.
insert(B2).second)
903 Successors[B1].push_back(B2);
924template <
typename BT>
931 for (
const auto &BI :
F) {
934 SampleBlockWeights[&BI] = Weight.
get();
937 applyProfi(
F, Successors, SampleBlockWeights, BlockWeights, EdgeWeights);
946 LoopT *L = LI->getLoopFor(BB);
951 if (Header && BlockWeights[BB] > BlockWeights[Header]) {
952 BlockWeights[Header] = BlockWeights[BB];
958 Changed = propagateThroughEdges(
F,
false);
964 VisitedEdges.clear();
967 Changed = propagateThroughEdges(
F,
false);
974 Changed = propagateThroughEdges(
F,
true);
979template <
typename FT>
984 Infer.apply(BlockWeights, EdgeWeights);
1033template <
typename BT>
1036 bool Changed = (InlinedGUIDs.
size() != 0);
1039 Changed |= computeBlockWeights(
F);
1043 initWeightPropagation(
F, InlinedGUIDs);
1046 propagateWeights(
F);
1049 finalizeWeightPropagation(
F, InlinedGUIDs);
1055template <
typename BT>
1069 computeDominanceAndLoopInfo(
F);
1072 findEquivalenceClasses(
F);
1083template <
typename BT>
1095 if (BlockWeights[EntryBB] > 0) {
1103template <
typename BT>
1108 unsigned Used = CoverageTracker.countUsedRecords(Samples, PSI);
1109 unsigned Total = CoverageTracker.countBodyRecords(Samples, PSI);
1110 unsigned Coverage = CoverageTracker.computeCoverage(Used,
Total);
1113 Func.getSubprogram()->getFilename(), getFunctionLoc(
F),
1114 Twine(Used) +
" of " +
Twine(
Total) +
" available profile records (" +
1115 Twine(Coverage) +
"%) were applied",
1121 uint64_t Used = CoverageTracker.getTotalUsedSamples();
1122 uint64_t Total = CoverageTracker.countBodySamples(Samples, PSI);
1123 unsigned Coverage = CoverageTracker.computeCoverage(Used,
Total);
1126 Func.getSubprogram()->getFilename(), getFunctionLoc(
F),
1127 Twine(Used) +
" of " +
Twine(
Total) +
" available profile samples (" +
1128 Twine(Coverage) +
"%) were applied",
1145template <
typename BT>
1149 return S->getLine();
1157 "No debug information found in function " + Func.getName() +
1158 ": Function profile not used",
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
static Function * getFunction(Constant *C)
This file defines a set of templates that efficiently compute a dominator tree over a generic graph.
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
This file defines the RefCountedBase, ThreadSafeRefCountedBase, and IntrusiveRefCntPtr classes.
Implements a lazy call graph analysis and related passes for the new pass manager.
Module.h This file contains the declarations for the Module class.
static StringRef getName(Value *V)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file provides the interface for the profile inference algorithm, profi.
This file provides the utility functions for the sampled PGO loader base implementation.
This file defines the SmallPtrSet class.
This file defines the SmallSet class.
This file defines the SmallVector class.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
LLVM Basic Block Representation.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
unsigned getBaseDiscriminator() const
Returns the base discriminator stored in the discriminator.
iterator find(const_arg_type_t< KeyT > Val)
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&... Args)
Implements a dense probed hash-table based set.
Diagnostic information for the sample profiler.
Represents either an error or a value T.
Class to represent profile counts.
void setEntryCount(ProfileCount Count, const DenseSet< GlobalValue::GUID > *Imports=nullptr)
Set the entry count for this function.
static bool isAvailableExternallyLinkage(LinkageTypes Linkage)
GUID getGUID() const
Return a 64-bit global unique ID constructed from global value name (i.e.
A smart pointer to a reference-counted object that inherits from RefCountedBase or ThreadSafeRefCount...
A node in the call graph.
A RefSCC of the call graph.
An SCC of the call graph.
A lazily constructed view of the call graph of a module.
iterator_range< postorder_ref_scc_iterator > postorder_ref_sccs()
Represents a single loop in the control flow graph.
A Module instance is used to store all the information related to an LLVM module.
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
Analysis providing profile information.
uint64_t getFunctionHash() const
const PseudoProbeDescriptor * getDesc(StringRef FProfileName) const
bool profileIsHashMismatched(const PseudoProbeDescriptor &FuncDesc, const FunctionSamples &Samples) const
const PseudoProbeDescriptor * getDesc(const Function &F) const
bool moduleIsProbed(const Module &M) const
bool profileIsValid(const Function &F, const FunctionSamples &Samples) const
PseudoProbeManager(const Module &M)
const PseudoProbeDescriptor * getDesc(uint64_t GUID) const
Sample profile inference pass.
bool computeAndPropagateWeights(FunctionT &F, const DenseSet< GlobalValue::GUID > &InlinedGUIDs)
Generate branch weight metadata for all branches in F.
void computeDominanceAndLoopInfo(FunctionT &F)
typename afdo_detail::IRTraits< BT >::BasicBlockT BasicBlockT
IntrusiveRefCntPtr< vfs::FileSystem > FS
VirtualFileSystem to load profile files from.
typename afdo_detail::IRTraits< BT >::OptRemarkAnalysisT OptRemarkAnalysisT
typename afdo_detail::IRTraits< BT >::SuccRangeT SuccRangeT
EdgeWeightMap EdgeWeights
Map edges to their computed weights.
Function & getFunction(FunctionT &F)
SmallSet< Edge, 32 > VisitedEdges
Set of visited edges during propagation.
std::map< SampleContext, FunctionSamples > OutlineFunctionSamples
Synthetic samples created by duplicating the samples of inlined functions from the original profile a...
OptRemarkEmitterT * ORE
Optimization Remark Emitter used to emit diagnostic remarks.
const BasicBlockT * getEntryBB(const FunctionT *F)
ErrorOr< uint64_t > getBlockWeight(const BasicBlockT *BB)
Compute the weight of a basic block.
unsigned getFunctionLoc(FunctionT &Func)
Get the line number for the function header.
PredRangeT getPredecessors(BasicBlockT *BB)
ErrorOr< uint64_t > getInstWeightImpl(const InstructionT &Inst)
virtual ErrorOr< uint64_t > getInstWeight(const InstructionT &Inst)
Get the weight for an instruction.
SmallPtrSet< const BasicBlockT *, 32 > VisitedBlocks
Set of visited blocks during propagation.
EquivalenceClassMap EquivalenceClass
Equivalence classes for block weights.
typename afdo_detail::IRTraits< BT >::DominatorTreePtrT DominatorTreePtrT
SampleCoverageTracker CoverageTracker
Profile coverage tracker.
typename afdo_detail::IRTraits< BT >::LoopT LoopT
typename GraphTraits< FT * >::NodeRef NodeRef
std::unique_ptr< SampleProfileReader > Reader
Profile reader object.
typename afdo_detail::IRTraits< BT >::OptRemarkEmitterT OptRemarkEmitterT
void printBlockWeight(raw_ostream &OS, const BasicBlockT *BB) const
Print the weight of block BB on stream OS.
DominatorTreePtrT DT
Dominance, post-dominance and loop information.
void printBlockEquivalence(raw_ostream &OS, const BasicBlockT *BB)
Print the equivalence class of block BB on stream OS.
std::remove_pointer_t< NodeRef > BT
SampleProfileLoaderBaseImpl(std::string Name, std::string RemapName, IntrusiveRefCntPtr< vfs::FileSystem > FS)
std::unique_ptr< PseudoProbeManager > ProbeManager
~SampleProfileLoaderBaseImpl()=default
typename afdo_detail::IRTraits< BT >::LoopInfoPtrT LoopInfoPtrT
void emitCoverageRemarks(FunctionT &F)
SuccRangeT getSuccessors(BasicBlockT *BB)
std::string Filename
Name of the profile file to load.
bool propagateThroughEdges(FunctionT &F, bool UpdateBlockCount)
Propagate weights through incoming/outgoing edges.
PostDominatorTreePtrT PDT
typename afdo_detail::IRTraits< BT >::InstructionT InstructionT
uint64_t visitEdge(Edge E, unsigned *NumUnknownEdges, Edge *UnknownEdge)
Visit the given edge to decide if it has a valid weight.
typename afdo_detail::IRTraits< BT >::PostDominatorTreePtrT PostDominatorTreePtrT
void initWeightPropagation(FunctionT &F, const DenseSet< GlobalValue::GUID > &InlinedGUIDs)
BlockEdgeMap Predecessors
Predecessors for each basic block in the CFG.
void finalizeWeightPropagation(FunctionT &F, const DenseSet< GlobalValue::GUID > &InlinedGUIDs)
bool computeBlockWeights(FunctionT &F)
Compute and store the weights of every basic block.
virtual const FunctionSamples * findFunctionSamples(const InstructionT &I) const
Get the FunctionSamples for an instruction.
typename afdo_detail::IRTraits< BT >::PostDominatorTreeT PostDominatorTreeT
virtual ErrorOr< uint64_t > getProbeWeight(const InstructionT &Inst)
std::string RemappingFilename
Name of the profile remapping file to load.
typename afdo_detail::IRTraits< BT >::PredRangeT PredRangeT
void applyProfi(FunctionT &F, BlockEdgeMap &Successors, BlockWeightMap &SampleBlockWeights, BlockWeightMap &BlockWeights, EdgeWeightMap &EdgeWeights)
typename afdo_detail::IRTraits< BT >::BlockFrequencyInfoT BlockFrequencyInfoT
BlockEdgeMap Successors
Successors for each basic block in the CFG.
FunctionSamples * Samples
Samples collected for the body of this function.
void findEquivalenceClasses(FunctionT &F)
Find equivalence classes.
std::pair< const BasicBlockT *, const BasicBlockT * > Edge
ProfileSummaryInfo * PSI
Profile Summary Info computed from sample profile.
void clearFunctionData(bool ResetDT=true)
Clear all the per-function data used to load samples and propagate weights.
DenseMap< const DILocation *, const FunctionSamples * > DILocation2SampleMap
void buildEdges(FunctionT &F)
Build in/out edge lists for each basic block in the CFG.
void findEquivalencesFor(BasicBlockT *BB1, ArrayRef< BasicBlockT * > Descendants, PostDominatorTreeT *DomTree)
Find equivalence classes for the given block.
void printEdgeWeight(raw_ostream &OS, Edge E)
Print the weight of edge E on stream OS.
typename afdo_detail::IRTraits< BT >::FunctionT FunctionT
BlockWeightMap BlockWeights
Map basic blocks to their computed weights.
void propagateWeights(FunctionT &F)
Propagate weights into edges.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
StringRef - Represent a constant reference to a string, i.e.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
A range adaptor for a pair of iterators.
This class implements an extremely fast bulk output stream that can only output to a stream.
Representation of the samples collected for a function.
uint64_t getFunctionHash() const
static bool ProfileIsProbeBased
static StringRef getCanonicalFnName(const Function &F)
Return the canonical name for a function, taking into account suffix elision policy attributes.
static unsigned getOffset(const DILocation *DIL)
Returns the line offset to the start line of the subprogram.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ C
The default llvm calling convention, compatible with C.
DiagnosticInfoOptimizationBase::Argument NV
This is an optimization pass for GlobalISel generic memory operations.
Function::ProfileCount ProfileCount
auto successors(const MachineBasicBlock *BB)
cl::opt< unsigned > SampleProfileSampleCoverage
static void buildTopDownFuncOrder(LazyCallGraph &CG, std::vector< Function * > &FunctionOrderList)
cl::opt< unsigned > SampleProfileRecordCoverage
cl::opt< unsigned > SampleProfileMaxPropagateIterations
cl::opt< bool > SampleProfileUseProfi
cl::opt< bool > EnableFSDiscriminator
std::optional< PseudoProbe > extractProbe(const Instruction &Inst)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
iterator_range< succ_iterator > succ_range
cl::opt< bool > NoWarnSampleUnused
format_object< Ts... > format(const char *Fmt, const Ts &... Vals)
These are helper functions used to produce formatted output.
iterator_range< pred_iterator > pred_range
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
static bool skipProfileForFunction(const Function &F)
auto predecessors(const MachineBasicBlock *BB)
constexpr const char * PseudoProbeDescMetadataName
Implement std::hash so that hash_code can be used in STL containers.
Description of the encoding of one expression Op.
typename GraphType::UnknownGraphTypeError NodeRef
std::unique_ptr< LoopInfo > LoopInfoPtrT
std::unique_ptr< PostDominatorTree > PostDominatorTreePtrT
static Function & getFunction(Function &F)
static pred_range getPredecessors(BasicBlock *BB)
static succ_range getSuccessors(BasicBlock *BB)
std::unique_ptr< DominatorTree > DominatorTreePtrT
static const BasicBlock * getEntryBB(const Function *F)