15#ifndef LLVM_TRANSFORMS_UTILS_SAMPLEPROFILELOADERBASEIMPL_H
16#define LLVM_TRANSFORMS_UTILS_SAMPLEPROFILELOADERBASEIMPL_H
47using namespace sampleprof;
48using namespace sampleprofutil;
55#define DEBUG_TYPE "sample-profile-impl"
57namespace afdo_detail {
76 return &
F->getEntryBlock();
94 for (
const auto *Operand : FuncInfo->operands()) {
95 const auto *MD = cast<MDNode>(Operand);
96 auto GUID = mdconst::dyn_extract<ConstantInt>(MD->getOperand(0))
98 auto Hash = mdconst::dyn_extract<ConstantInt>(MD->getOperand(1))
106 auto I = GUIDToProbeDescMap.
find(GUID);
107 return I == GUIDToProbeDescMap.
end() ? nullptr : &
I->second;
129 bool IsAvailableExternallyLinkage =
143 if (IsAvailableExternallyLinkage || !
Desc)
144 return !
F.hasFnAttribute(
"profile-checksum-mismatch");
155 return F.isDeclaration() || !
F.hasFnAttribute(
"use-sample-profile");
166 using BT = std::remove_pointer_t<NodeRef>;
190 using Edge = std::pair<const BasicBlockT *, const BasicBlockT *>;
289 std::unique_ptr<SampleProfileReader>
Reader;
319template <
typename BT>
321 BlockWeights.clear();
323 VisitedBlocks.clear();
324 VisitedEdges.clear();
325 EquivalenceClass.clear();
331 Predecessors.clear();
333 CoverageTracker.clear();
341template <
typename BT>
343 OS <<
"weight[" <<
E.first->getName() <<
"->" <<
E.second->getName()
344 <<
"]: " << EdgeWeights[
E] <<
"\n";
351template <
typename BT>
355 OS <<
"equivalence[" << BB->getName()
356 <<
"]: " << ((Equiv) ? EquivalenceClass[BB]->
getName() :
"NONE") <<
"\n";
363template <
typename BT>
366 const auto &
I = BlockWeights.find(BB);
367 uint64_t W = (
I == BlockWeights.end() ? 0 :
I->second);
368 OS <<
"weight[" << BB->getName() <<
"]: " << W <<
"\n";
383template <
typename BT>
387 return getProbeWeight(Inst);
388 return getInstWeightImpl(Inst);
391template <
typename BT>
396 return std::error_code();
398 const DebugLoc &DLoc = Inst.getDebugLoc();
400 return std::error_code();
406 Discriminator = DIL->getDiscriminator();
413 CoverageTracker.markSamplesUsed(FS, LineOffset, Discriminator, R.get());
418 Remark <<
" samples from profile (offset: ";
429 << Inst <<
" (line offset: " << LineOffset <<
"."
430 << Discriminator <<
" - weight: " << R.get() <<
")\n");
438template <
typename BT>
442 "Profile is not pseudo probe based");
447 return std::error_code();
462 auto R = FS->findSamplesAt(Probe->Id, Probe->Discriminator);
464 uint64_t Samples = R.get() * Probe->Factor;
465 bool FirstMark = CoverageTracker.markSamplesUsed(FS, Probe->Id, 0, Samples);
470 Remark <<
" samples from profile (ProbeId=";
472 if (Probe->Discriminator) {
478 Remark <<
", OriginalSamples=";
485 if (Probe->Discriminator)
486 dbgs() <<
"." << Probe->Discriminator;
487 dbgs() <<
":" << Inst <<
" - weight: " << R.get()
488 <<
" - factor: " <<
format(
"%0.2f", Probe->Factor) <<
")\n";});
502template <
typename BT>
506 bool HasWeight =
false;
507 for (
auto &
I : *BB) {
510 Max = std::max(Max, R.get());
523template <
typename BT>
525 bool Changed =
false;
527 for (
const auto &BB :
F) {
530 BlockWeights[&BB] = Weight.
get();
531 VisitedBlocks.insert(&BB);
549template <
typename BT>
556 auto it = DILocation2SampleMap.try_emplace(DIL,
nullptr);
558 it.first->second = Samples->findFunctionSamples(DIL, Reader->getRemapper());
560 return it.first->second;
586template <
typename BT>
592 for (
const auto *BB2 : Descendants) {
593 bool IsDomParent = DomTree->dominates(BB2, BB1);
594 bool IsInSameLoop = LI->getLoopFor(BB1) == LI->getLoopFor(BB2);
595 if (BB1 != BB2 && IsDomParent && IsInSameLoop) {
596 EquivalenceClass[BB2] = EC;
598 if (VisitedBlocks.count(BB2)) {
599 VisitedBlocks.insert(EC);
610 Weight = std::max(Weight, BlockWeights[BB2]);
613 const BasicBlockT *EntryBB = getEntryBB(EC->getParent());
615 BlockWeights[EC] = Samples->getHeadSamples() + 1;
617 BlockWeights[EC] = Weight;
630template <
typename BT>
639 if (EquivalenceClass.count(BB1)) {
645 EquivalenceClass[BB1] = BB1;
657 DominatedBBs.
clear();
658 DT->getDescendants(BB1, DominatedBBs);
659 findEquivalencesFor(BB1, DominatedBBs, &*PDT);
671 dbgs() <<
"\nAssign the same weight to all blocks in the same class\n");
676 BlockWeights[BB] = BlockWeights[EquivBB];
691template <
typename BT>
693 unsigned *NumUnknownEdges,
695 if (!VisitedEdges.count(
E)) {
696 (*NumUnknownEdges)++;
701 return EdgeWeights[
E];
717template <
typename BT>
720 bool Changed =
false;
722 for (
const auto &BI :
F) {
731 for (
unsigned i = 0; i < 2; i++) {
733 unsigned NumUnknownEdges = 0, NumTotalEdges = 0;
734 Edge UnknownEdge, SelfReferentialEdge, SingleEdge;
738 NumTotalEdges = Predecessors[BB].size();
739 for (
auto *Pred : Predecessors[BB]) {
740 Edge E = std::make_pair(Pred, BB);
741 TotalWeight += visitEdge(
E, &NumUnknownEdges, &UnknownEdge);
742 if (
E.first ==
E.second)
743 SelfReferentialEdge =
E;
745 if (NumTotalEdges == 1) {
746 SingleEdge = std::make_pair(Predecessors[BB][0], BB);
750 NumTotalEdges = Successors[BB].size();
751 for (
auto *Succ : Successors[BB]) {
752 Edge E = std::make_pair(BB, Succ);
753 TotalWeight += visitEdge(
E, &NumUnknownEdges, &UnknownEdge);
755 if (NumTotalEdges == 1) {
756 SingleEdge = std::make_pair(BB, Successors[BB][0]);
783 if (NumUnknownEdges <= 1) {
784 uint64_t &BBWeight = BlockWeights[EC];
785 if (NumUnknownEdges == 0) {
786 if (!VisitedBlocks.count(EC)) {
790 if (TotalWeight > BBWeight) {
791 BBWeight = TotalWeight;
794 <<
" known. Set weight for block: ";
795 printBlockWeight(
dbgs(), BB););
797 }
else if (NumTotalEdges == 1 &&
798 EdgeWeights[SingleEdge] < BlockWeights[EC]) {
801 EdgeWeights[SingleEdge] = BlockWeights[EC];
804 }
else if (NumUnknownEdges == 1 && VisitedBlocks.count(EC)) {
807 if (BBWeight >= TotalWeight)
808 EdgeWeights[UnknownEdge] = BBWeight - TotalWeight;
810 EdgeWeights[UnknownEdge] = 0;
813 OtherEC = EquivalenceClass[UnknownEdge.first];
815 OtherEC = EquivalenceClass[UnknownEdge.second];
817 if (VisitedBlocks.count(OtherEC) &&
818 EdgeWeights[UnknownEdge] > BlockWeights[OtherEC])
819 EdgeWeights[UnknownEdge] = BlockWeights[OtherEC];
820 VisitedEdges.insert(UnknownEdge);
823 printEdgeWeight(
dbgs(), UnknownEdge));
825 }
else if (VisitedBlocks.count(EC) && BlockWeights[EC] == 0) {
828 for (
auto *Pred : Predecessors[BB]) {
829 Edge E = std::make_pair(Pred, BB);
831 VisitedEdges.insert(
E);
834 for (
auto *Succ : Successors[BB]) {
835 Edge E = std::make_pair(BB, Succ);
837 VisitedEdges.insert(
E);
840 }
else if (SelfReferentialEdge.first && VisitedBlocks.count(EC)) {
841 uint64_t &BBWeight = BlockWeights[BB];
843 if (BBWeight >= TotalWeight)
844 EdgeWeights[SelfReferentialEdge] = BBWeight - TotalWeight;
846 EdgeWeights[SelfReferentialEdge] = 0;
847 VisitedEdges.insert(SelfReferentialEdge);
850 printEdgeWeight(
dbgs(), SelfReferentialEdge));
852 if (UpdateBlockCount && !VisitedBlocks.count(EC) && TotalWeight > 0) {
853 BlockWeights[EC] = TotalWeight;
854 VisitedBlocks.insert(EC);
867template <
typename BT>
874 if (!Predecessors[B1].empty())
876 for (
auto *B2 : getPredecessors(B1))
877 if (Visited.
insert(B2).second)
878 Predecessors[B1].push_back(B2);
882 if (!Successors[B1].empty())
884 for (
auto *B2 : getSuccessors(B1))
885 if (Visited.
insert(B2).second)
886 Successors[B1].push_back(B2);
907template <
typename BT>
914 for (
const auto &BI :
F) {
917 SampleBlockWeights[&BI] = Weight.
get();
920 applyProfi(
F, Successors, SampleBlockWeights, BlockWeights, EdgeWeights);
929 LoopT *L = LI->getLoopFor(BB);
934 if (Header && BlockWeights[BB] > BlockWeights[Header]) {
935 BlockWeights[Header] = BlockWeights[BB];
941 Changed = propagateThroughEdges(
F,
false);
947 VisitedEdges.clear();
950 Changed = propagateThroughEdges(
F,
false);
957 Changed = propagateThroughEdges(
F,
true);
962template <
typename FT>
967 Infer.apply(BlockWeights, EdgeWeights);
1016template <
typename BT>
1019 bool Changed = (InlinedGUIDs.
size() != 0);
1022 Changed |= computeBlockWeights(
F);
1026 initWeightPropagation(
F, InlinedGUIDs);
1029 propagateWeights(
F);
1032 finalizeWeightPropagation(
F, InlinedGUIDs);
1038template <
typename BT>
1052 computeDominanceAndLoopInfo(
F);
1055 findEquivalenceClasses(
F);
1066template <
typename BT>
1078 if (BlockWeights[EntryBB] > 0) {
1086template <
typename BT>
1091 unsigned Used = CoverageTracker.countUsedRecords(Samples, PSI);
1092 unsigned Total = CoverageTracker.countBodyRecords(Samples, PSI);
1093 unsigned Coverage = CoverageTracker.computeCoverage(Used,
Total);
1096 Func.getSubprogram()->getFilename(), getFunctionLoc(
F),
1097 Twine(Used) +
" of " +
Twine(
Total) +
" available profile records (" +
1098 Twine(Coverage) +
"%) were applied",
1104 uint64_t Used = CoverageTracker.getTotalUsedSamples();
1105 uint64_t Total = CoverageTracker.countBodySamples(Samples, PSI);
1106 unsigned Coverage = CoverageTracker.computeCoverage(Used,
Total);
1109 Func.getSubprogram()->getFilename(), getFunctionLoc(
F),
1110 Twine(Used) +
" of " +
Twine(
Total) +
" available profile samples (" +
1111 Twine(Coverage) +
"%) were applied",
1128template <
typename BT>
1132 return S->getLine();
1140 "No debug information found in function " + Func.getName() +
1141 ": 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.
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...
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.
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
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)