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;
131 <<
F.getName() <<
"\n");
155 using BT = std::remove_pointer_t<NodeRef>;
179 using Edge = std::pair<const BasicBlockT *, const BasicBlockT *>;
278 std::unique_ptr<SampleProfileReader>
Reader;
308template <
typename BT>
310 BlockWeights.clear();
312 VisitedBlocks.clear();
313 VisitedEdges.clear();
314 EquivalenceClass.clear();
320 Predecessors.clear();
322 CoverageTracker.clear();
330template <
typename BT>
332 OS <<
"weight[" <<
E.first->getName() <<
"->" <<
E.second->getName()
333 <<
"]: " << EdgeWeights[
E] <<
"\n";
340template <
typename BT>
344 OS <<
"equivalence[" << BB->getName()
345 <<
"]: " << ((Equiv) ? EquivalenceClass[BB]->
getName() :
"NONE") <<
"\n";
352template <
typename BT>
355 const auto &
I = BlockWeights.find(BB);
356 uint64_t W = (
I == BlockWeights.end() ? 0 :
I->second);
357 OS <<
"weight[" << BB->getName() <<
"]: " << W <<
"\n";
372template <
typename BT>
376 return getProbeWeight(Inst);
377 return getInstWeightImpl(Inst);
380template <
typename BT>
385 return std::error_code();
387 const DebugLoc &DLoc = Inst.getDebugLoc();
389 return std::error_code();
395 Discriminator = DIL->getDiscriminator();
402 CoverageTracker.markSamplesUsed(FS, LineOffset, Discriminator, R.get());
407 Remark <<
" samples from profile (offset: ";
418 << Inst <<
" (line offset: " << LineOffset <<
"."
419 << Discriminator <<
" - weight: " << R.get() <<
")\n");
427template <
typename BT>
431 "Profile is not pseudo probe based");
436 return std::error_code();
451 auto R = FS->findSamplesAt(Probe->Id, Probe->Discriminator);
453 uint64_t Samples = R.get() * Probe->Factor;
454 bool FirstMark = CoverageTracker.markSamplesUsed(FS, Probe->Id, 0, Samples);
459 Remark <<
" samples from profile (ProbeId=";
461 if (Probe->Discriminator) {
467 Remark <<
", OriginalSamples=";
474 if (Probe->Discriminator)
475 dbgs() <<
"." << Probe->Discriminator;
476 dbgs() <<
":" << Inst <<
" - weight: " << R.get()
477 <<
" - factor: " <<
format(
"%0.2f", Probe->Factor) <<
")\n";});
491template <
typename BT>
495 bool HasWeight =
false;
496 for (
auto &
I : *BB) {
499 Max = std::max(Max, R.get());
512template <
typename BT>
514 bool Changed =
false;
516 for (
const auto &BB :
F) {
519 BlockWeights[&BB] = Weight.
get();
520 VisitedBlocks.insert(&BB);
538template <
typename BT>
545 auto it = DILocation2SampleMap.try_emplace(DIL,
nullptr);
547 it.first->second = Samples->findFunctionSamples(DIL, Reader->getRemapper());
549 return it.first->second;
575template <
typename BT>
581 for (
const auto *BB2 : Descendants) {
582 bool IsDomParent = DomTree->dominates(BB2, BB1);
583 bool IsInSameLoop = LI->getLoopFor(BB1) == LI->getLoopFor(BB2);
584 if (BB1 != BB2 && IsDomParent && IsInSameLoop) {
585 EquivalenceClass[BB2] = EC;
587 if (VisitedBlocks.count(BB2)) {
588 VisitedBlocks.insert(EC);
599 Weight = std::max(Weight, BlockWeights[BB2]);
602 const BasicBlockT *EntryBB = getEntryBB(EC->getParent());
604 BlockWeights[EC] = Samples->getHeadSamples() + 1;
606 BlockWeights[EC] = Weight;
619template <
typename BT>
628 if (EquivalenceClass.count(BB1)) {
634 EquivalenceClass[BB1] = BB1;
646 DominatedBBs.
clear();
647 DT->getDescendants(BB1, DominatedBBs);
648 findEquivalencesFor(BB1, DominatedBBs, &*PDT);
660 dbgs() <<
"\nAssign the same weight to all blocks in the same class\n");
665 BlockWeights[BB] = BlockWeights[EquivBB];
680template <
typename BT>
682 unsigned *NumUnknownEdges,
684 if (!VisitedEdges.count(
E)) {
685 (*NumUnknownEdges)++;
690 return EdgeWeights[
E];
706template <
typename BT>
709 bool Changed =
false;
711 for (
const auto &BI :
F) {
720 for (
unsigned i = 0; i < 2; i++) {
722 unsigned NumUnknownEdges = 0, NumTotalEdges = 0;
723 Edge UnknownEdge, SelfReferentialEdge, SingleEdge;
727 NumTotalEdges = Predecessors[BB].size();
728 for (
auto *Pred : Predecessors[BB]) {
729 Edge E = std::make_pair(Pred, BB);
730 TotalWeight += visitEdge(
E, &NumUnknownEdges, &UnknownEdge);
731 if (
E.first ==
E.second)
732 SelfReferentialEdge =
E;
734 if (NumTotalEdges == 1) {
735 SingleEdge = std::make_pair(Predecessors[BB][0], BB);
739 NumTotalEdges = Successors[BB].size();
740 for (
auto *Succ : Successors[BB]) {
741 Edge E = std::make_pair(BB, Succ);
742 TotalWeight += visitEdge(
E, &NumUnknownEdges, &UnknownEdge);
744 if (NumTotalEdges == 1) {
745 SingleEdge = std::make_pair(BB, Successors[BB][0]);
772 if (NumUnknownEdges <= 1) {
773 uint64_t &BBWeight = BlockWeights[EC];
774 if (NumUnknownEdges == 0) {
775 if (!VisitedBlocks.count(EC)) {
779 if (TotalWeight > BBWeight) {
780 BBWeight = TotalWeight;
783 <<
" known. Set weight for block: ";
784 printBlockWeight(
dbgs(), BB););
786 }
else if (NumTotalEdges == 1 &&
787 EdgeWeights[SingleEdge] < BlockWeights[EC]) {
790 EdgeWeights[SingleEdge] = BlockWeights[EC];
793 }
else if (NumUnknownEdges == 1 && VisitedBlocks.count(EC)) {
796 if (BBWeight >= TotalWeight)
797 EdgeWeights[UnknownEdge] = BBWeight - TotalWeight;
799 EdgeWeights[UnknownEdge] = 0;
802 OtherEC = EquivalenceClass[UnknownEdge.first];
804 OtherEC = EquivalenceClass[UnknownEdge.second];
806 if (VisitedBlocks.count(OtherEC) &&
807 EdgeWeights[UnknownEdge] > BlockWeights[OtherEC])
808 EdgeWeights[UnknownEdge] = BlockWeights[OtherEC];
809 VisitedEdges.insert(UnknownEdge);
812 printEdgeWeight(
dbgs(), UnknownEdge));
814 }
else if (VisitedBlocks.count(EC) && BlockWeights[EC] == 0) {
817 for (
auto *Pred : Predecessors[BB]) {
818 Edge E = std::make_pair(Pred, BB);
820 VisitedEdges.insert(
E);
823 for (
auto *Succ : Successors[BB]) {
824 Edge E = std::make_pair(BB, Succ);
826 VisitedEdges.insert(
E);
829 }
else if (SelfReferentialEdge.first && VisitedBlocks.count(EC)) {
830 uint64_t &BBWeight = BlockWeights[BB];
832 if (BBWeight >= TotalWeight)
833 EdgeWeights[SelfReferentialEdge] = BBWeight - TotalWeight;
835 EdgeWeights[SelfReferentialEdge] = 0;
836 VisitedEdges.insert(SelfReferentialEdge);
839 printEdgeWeight(
dbgs(), SelfReferentialEdge));
841 if (UpdateBlockCount && !VisitedBlocks.count(EC) && TotalWeight > 0) {
842 BlockWeights[EC] = TotalWeight;
843 VisitedBlocks.insert(EC);
856template <
typename BT>
863 if (!Predecessors[B1].empty())
865 for (
auto *B2 : getPredecessors(B1))
866 if (Visited.
insert(B2).second)
867 Predecessors[B1].push_back(B2);
871 if (!Successors[B1].empty())
873 for (
auto *B2 : getSuccessors(B1))
874 if (Visited.
insert(B2).second)
875 Successors[B1].push_back(B2);
896template <
typename BT>
903 for (
const auto &BI :
F) {
906 SampleBlockWeights[&BI] = Weight.
get();
909 applyProfi(
F, Successors, SampleBlockWeights, BlockWeights, EdgeWeights);
918 LoopT *L = LI->getLoopFor(BB);
923 if (Header && BlockWeights[BB] > BlockWeights[Header]) {
924 BlockWeights[Header] = BlockWeights[BB];
930 Changed = propagateThroughEdges(
F,
false);
936 VisitedEdges.clear();
939 Changed = propagateThroughEdges(
F,
false);
946 Changed = propagateThroughEdges(
F,
true);
951template <
typename FT>
956 Infer.apply(BlockWeights, EdgeWeights);
1005template <
typename BT>
1008 bool Changed = (InlinedGUIDs.
size() != 0);
1011 Changed |= computeBlockWeights(
F);
1015 initWeightPropagation(
F, InlinedGUIDs);
1018 propagateWeights(
F);
1021 finalizeWeightPropagation(
F, InlinedGUIDs);
1027template <
typename BT>
1041 computeDominanceAndLoopInfo(
F);
1044 findEquivalenceClasses(
F);
1055template <
typename BT>
1067 if (BlockWeights[EntryBB] > 0) {
1075template <
typename BT>
1080 unsigned Used = CoverageTracker.countUsedRecords(Samples, PSI);
1081 unsigned Total = CoverageTracker.countBodyRecords(Samples, PSI);
1082 unsigned Coverage = CoverageTracker.computeCoverage(Used,
Total);
1085 Func.getSubprogram()->getFilename(), getFunctionLoc(
F),
1086 Twine(Used) +
" of " +
Twine(
Total) +
" available profile records (" +
1087 Twine(Coverage) +
"%) were applied",
1093 uint64_t Used = CoverageTracker.getTotalUsedSamples();
1094 uint64_t Total = CoverageTracker.countBodySamples(Samples, PSI);
1095 unsigned Coverage = CoverageTracker.computeCoverage(Used,
Total);
1098 Func.getSubprogram()->getFilename(), getFunctionLoc(
F),
1099 Twine(Used) +
" of " +
Twine(
Total) +
" available profile samples (" +
1100 Twine(Coverage) +
"%) were applied",
1117template <
typename BT>
1121 return S->getLine();
1129 "No debug information found in function " + Func.getName() +
1130 ": 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.
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.
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)