15#ifndef LLVM_TRANSFORMS_UTILS_SAMPLEPROFILELOADERBASEIMPL_H
16#define LLVM_TRANSFORMS_UTILS_SAMPLEPROFILELOADERBASEIMPL_H
45using namespace sampleprof;
46using namespace sampleprofutil;
49#define DEBUG_TYPE "sample-profile-impl"
51namespace afdo_detail {
70 return &
F->getEntryBlock();
109 using Edge = std::pair<const BasicBlockT *, const BasicBlockT *>;
207 std::unique_ptr<SampleProfileReader>
Reader;
226template <
typename BT>
228 BlockWeights.clear();
230 VisitedBlocks.clear();
231 VisitedEdges.clear();
232 EquivalenceClass.clear();
238 Predecessors.clear();
240 CoverageTracker.clear();
248template <
typename BT>
250 OS <<
"weight[" <<
E.first->getName() <<
"->" <<
E.second->getName()
251 <<
"]: " << EdgeWeights[
E] <<
"\n";
258template <
typename BT>
262 OS <<
"equivalence[" << BB->getName()
263 <<
"]: " << ((Equiv) ? EquivalenceClass[BB]->
getName() :
"NONE") <<
"\n";
270template <
typename BT>
273 const auto &
I = BlockWeights.find(BB);
274 uint64_t W = (
I == BlockWeights.end() ? 0 :
I->second);
275 OS <<
"weight[" << BB->getName() <<
"]: " << W <<
"\n";
290template <
typename BT>
293 return getInstWeightImpl(Inst);
296template <
typename BT>
301 return std::error_code();
303 const DebugLoc &DLoc = Inst.getDebugLoc();
305 return std::error_code();
311 Discriminator = DIL->getDiscriminator();
318 CoverageTracker.markSamplesUsed(FS, LineOffset, Discriminator, R.get());
323 Remark <<
" samples from profile (offset: ";
334 << Inst <<
" (line offset: " << LineOffset <<
"."
335 << Discriminator <<
" - weight: " << R.get() <<
")\n");
348template <
typename BT>
352 bool HasWeight =
false;
353 for (
auto &
I : *BB) {
356 Max = std::max(Max, R.get());
369template <
typename BT>
371 bool Changed =
false;
373 for (
const auto &BB :
F) {
376 BlockWeights[&BB] = Weight.
get();
377 VisitedBlocks.insert(&BB);
395template <
typename BT>
402 auto it = DILocation2SampleMap.try_emplace(DIL,
nullptr);
404 it.first->second = Samples->findFunctionSamples(DIL, Reader->getRemapper());
406 return it.first->second;
432template <
typename BT>
438 for (
const auto *BB2 : Descendants) {
439 bool IsDomParent = DomTree->dominates(BB2, BB1);
440 bool IsInSameLoop = LI->getLoopFor(BB1) == LI->getLoopFor(BB2);
441 if (BB1 != BB2 && IsDomParent && IsInSameLoop) {
442 EquivalenceClass[BB2] = EC;
444 if (VisitedBlocks.count(BB2)) {
445 VisitedBlocks.insert(EC);
456 Weight = std::max(Weight, BlockWeights[BB2]);
459 const BasicBlockT *EntryBB = getEntryBB(EC->getParent());
461 BlockWeights[EC] = Samples->getHeadSamples() + 1;
463 BlockWeights[EC] = Weight;
476template <
typename BT>
485 if (EquivalenceClass.count(BB1)) {
491 EquivalenceClass[BB1] = BB1;
503 DominatedBBs.
clear();
504 DT->getDescendants(BB1, DominatedBBs);
505 findEquivalencesFor(BB1, DominatedBBs, &*PDT);
517 dbgs() <<
"\nAssign the same weight to all blocks in the same class\n");
522 BlockWeights[BB] = BlockWeights[EquivBB];
537template <
typename BT>
539 unsigned *NumUnknownEdges,
541 if (!VisitedEdges.count(
E)) {
542 (*NumUnknownEdges)++;
547 return EdgeWeights[
E];
563template <
typename BT>
566 bool Changed =
false;
568 for (
const auto &BI :
F) {
577 for (
unsigned i = 0; i < 2; i++) {
579 unsigned NumUnknownEdges = 0, NumTotalEdges = 0;
580 Edge UnknownEdge, SelfReferentialEdge, SingleEdge;
584 NumTotalEdges = Predecessors[BB].size();
585 for (
auto *Pred : Predecessors[BB]) {
586 Edge E = std::make_pair(Pred, BB);
587 TotalWeight += visitEdge(
E, &NumUnknownEdges, &UnknownEdge);
588 if (
E.first ==
E.second)
589 SelfReferentialEdge =
E;
591 if (NumTotalEdges == 1) {
592 SingleEdge = std::make_pair(Predecessors[BB][0], BB);
596 NumTotalEdges = Successors[BB].size();
597 for (
auto *Succ : Successors[BB]) {
598 Edge E = std::make_pair(BB, Succ);
599 TotalWeight += visitEdge(
E, &NumUnknownEdges, &UnknownEdge);
601 if (NumTotalEdges == 1) {
602 SingleEdge = std::make_pair(BB, Successors[BB][0]);
629 if (NumUnknownEdges <= 1) {
630 uint64_t &BBWeight = BlockWeights[EC];
631 if (NumUnknownEdges == 0) {
632 if (!VisitedBlocks.count(EC)) {
636 if (TotalWeight > BBWeight) {
637 BBWeight = TotalWeight;
640 <<
" known. Set weight for block: ";
641 printBlockWeight(
dbgs(), BB););
643 }
else if (NumTotalEdges == 1 &&
644 EdgeWeights[SingleEdge] < BlockWeights[EC]) {
647 EdgeWeights[SingleEdge] = BlockWeights[EC];
650 }
else if (NumUnknownEdges == 1 && VisitedBlocks.count(EC)) {
653 if (BBWeight >= TotalWeight)
654 EdgeWeights[UnknownEdge] = BBWeight - TotalWeight;
656 EdgeWeights[UnknownEdge] = 0;
659 OtherEC = EquivalenceClass[UnknownEdge.first];
661 OtherEC = EquivalenceClass[UnknownEdge.second];
663 if (VisitedBlocks.count(OtherEC) &&
664 EdgeWeights[UnknownEdge] > BlockWeights[OtherEC])
665 EdgeWeights[UnknownEdge] = BlockWeights[OtherEC];
666 VisitedEdges.insert(UnknownEdge);
669 printEdgeWeight(
dbgs(), UnknownEdge));
671 }
else if (VisitedBlocks.count(EC) && BlockWeights[EC] == 0) {
674 for (
auto *Pred : Predecessors[BB]) {
675 Edge E = std::make_pair(Pred, BB);
677 VisitedEdges.insert(
E);
680 for (
auto *Succ : Successors[BB]) {
681 Edge E = std::make_pair(BB, Succ);
683 VisitedEdges.insert(
E);
686 }
else if (SelfReferentialEdge.first && VisitedBlocks.count(EC)) {
687 uint64_t &BBWeight = BlockWeights[BB];
689 if (BBWeight >= TotalWeight)
690 EdgeWeights[SelfReferentialEdge] = BBWeight - TotalWeight;
692 EdgeWeights[SelfReferentialEdge] = 0;
693 VisitedEdges.insert(SelfReferentialEdge);
696 printEdgeWeight(
dbgs(), SelfReferentialEdge));
698 if (UpdateBlockCount && !VisitedBlocks.count(EC) && TotalWeight > 0) {
699 BlockWeights[EC] = TotalWeight;
700 VisitedBlocks.insert(EC);
713template <
typename BT>
720 if (!Predecessors[B1].empty())
722 for (
auto *B2 : getPredecessors(B1))
723 if (Visited.
insert(B2).second)
724 Predecessors[B1].push_back(B2);
728 if (!Successors[B1].empty())
730 for (
auto *B2 : getSuccessors(B1))
731 if (Visited.
insert(B2).second)
732 Successors[B1].push_back(B2);
753template <
typename BT>
760 for (
const auto &BI :
F) {
763 SampleBlockWeights[&BI] = Weight.
get();
766 applyProfi(
F, Successors, SampleBlockWeights, BlockWeights, EdgeWeights);
775 LoopT *L = LI->getLoopFor(BB);
780 if (Header && BlockWeights[BB] > BlockWeights[Header]) {
781 BlockWeights[Header] = BlockWeights[BB];
787 Changed = propagateThroughEdges(
F,
false);
793 VisitedEdges.clear();
796 Changed = propagateThroughEdges(
F,
false);
803 Changed = propagateThroughEdges(
F,
true);
808template <
typename BT>
813 Infer.apply(BlockWeights, EdgeWeights);
862template <
typename BT>
865 bool Changed = (InlinedGUIDs.
size() != 0);
868 Changed |= computeBlockWeights(
F);
872 initWeightPropagation(
F, InlinedGUIDs);
878 finalizeWeightPropagation(
F, InlinedGUIDs);
884template <
typename BT>
898 computeDominanceAndLoopInfo(
F);
901 findEquivalenceClasses(
F);
912template <
typename BT>
924 if (BlockWeights[EntryBB] > 0) {
932template <
typename BT>
937 unsigned Used = CoverageTracker.countUsedRecords(Samples, PSI);
938 unsigned Total = CoverageTracker.countBodyRecords(Samples, PSI);
939 unsigned Coverage = CoverageTracker.computeCoverage(Used,
Total);
942 Func.getSubprogram()->getFilename(), getFunctionLoc(
F),
944 Twine(Coverage) +
"%) were applied",
950 uint64_t Used = CoverageTracker.getTotalUsedSamples();
951 uint64_t Total = CoverageTracker.countBodySamples(Samples, PSI);
952 unsigned Coverage = CoverageTracker.computeCoverage(Used,
Total);
955 Func.getSubprogram()->getFilename(), getFunctionLoc(
F),
957 Twine(Coverage) +
"%) were applied",
974template <
typename BT>
986 "No debug information found in function " + Func.getName() +
987 ": Function profile not used",
992template <
typename BT>
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...
Module.h This file contains the declarations for the Module class.
static StringRef getName(Value *V)
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.
Implements a dense probed hash-table based set.
Diagnostic information for the sample profiler.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
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.
Represents a single loop in the control flow graph.
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
Analysis providing profile information.
Sample profile inference pass.
bool computeAndPropagateWeights(FunctionT &F, const DenseSet< GlobalValue::GUID > &InlinedGUIDs)
Generate branch weight metadata for all branches in F.
typename afdo_detail::IRTraits< BT >::BlockFrequencyInfoT BlockFrequencyInfoT
std::string Filename
Name of the profile file to load.
EquivalenceClassMap EquivalenceClass
Equivalence classes for block weights.
const BasicBlockT * getEntryBB(const FunctionT *F)
typename afdo_detail::IRTraits< BT >::OptRemarkEmitterT OptRemarkEmitterT
ErrorOr< uint64_t > getBlockWeight(const BasicBlockT *BB)
Compute the weight of a basic block.
ProfileSummaryInfo * PSI
Profile Summary Info computed from sample profile.
typename afdo_detail::IRTraits< BT >::PostDominatorTreeT PostDominatorTreeT
unsigned getFunctionLoc(FunctionT &Func)
Get the line number for the function header.
SuccRangeT getSuccessors(BasicBlockT *BB)
ErrorOr< uint64_t > getInstWeightImpl(const InstructionT &Inst)
~SampleProfileLoaderBaseImpl()=default
virtual ErrorOr< uint64_t > getInstWeight(const InstructionT &Inst)
Get the weight for an instruction.
typename afdo_detail::IRTraits< BT >::DominatorTreePtrT DominatorTreePtrT
SmallPtrSet< const BasicBlockT *, 32 > VisitedBlocks
Set of visited blocks during propagation.
SampleProfileLoaderBaseImpl(std::string Name, std::string RemapName)
typename afdo_detail::IRTraits< BT >::PredRangeT PredRangeT
void applyProfi(FunctionT &F, BlockEdgeMap &Successors, BlockWeightMap &SampleBlockWeights, BlockWeightMap &BlockWeights, EdgeWeightMap &EdgeWeights)
typename afdo_detail::IRTraits< BT >::PostDominatorTreePtrT PostDominatorTreePtrT
void printBlockWeight(raw_ostream &OS, const BasicBlockT *BB) const
Print the weight of block BB on stream OS.
void printBlockEquivalence(raw_ostream &OS, const BasicBlockT *BB)
Print the equivalence class of block BB on stream OS.
std::string RemappingFilename
Name of the profile remapping file to load.
SampleCoverageTracker CoverageTracker
Profile coverage tracker.
Function & getFunction(FunctionT &F)
SmallSet< Edge, 32 > VisitedEdges
Set of visited edges during propagation.
BlockEdgeMap Predecessors
Predecessors for each basic block in the CFG.
void emitCoverageRemarks(FunctionT &F)
EdgeWeightMap EdgeWeights
Map edges to their computed weights.
void computeDominanceAndLoopInfo(FunctionT &F)
bool propagateThroughEdges(FunctionT &F, bool UpdateBlockCount)
Propagate weights through incoming/outgoing edges.
typename afdo_detail::IRTraits< BT >::FunctionT FunctionT
uint64_t visitEdge(Edge E, unsigned *NumUnknownEdges, Edge *UnknownEdge)
Visit the given edge to decide if it has a valid weight.
void initWeightPropagation(FunctionT &F, const DenseSet< GlobalValue::GUID > &InlinedGUIDs)
typename afdo_detail::IRTraits< BT >::InstructionT InstructionT
BlockEdgeMap Successors
Successors for each basic block in the CFG.
PostDominatorTreePtrT PDT
void finalizeWeightPropagation(FunctionT &F, const DenseSet< GlobalValue::GUID > &InlinedGUIDs)
typename afdo_detail::IRTraits< BT >::SuccRangeT SuccRangeT
bool computeBlockWeights(FunctionT &F)
Compute and store the weights of every basic block.
typename afdo_detail::IRTraits< BT >::OptRemarkAnalysisT OptRemarkAnalysisT
virtual const FunctionSamples * findFunctionSamples(const InstructionT &I) const
Get the FunctionSamples for an instruction.
FunctionSamples * Samples
Samples collected for the body of this function.
PredRangeT getPredecessors(BasicBlockT *BB)
BlockWeightMap BlockWeights
Map basic blocks to their computed weights.
typename afdo_detail::IRTraits< BT >::LoopT LoopT
void findEquivalenceClasses(FunctionT &F)
Find equivalence classes.
OptRemarkEmitterT * ORE
Optimization Remark Emitter used to emit diagnostic remarks.
void clearFunctionData(bool ResetDT=true)
Clear all the per-function data used to load samples and propagate weights.
typename afdo_detail::IRTraits< BT >::BasicBlockT BasicBlockT
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.
DominatorTreePtrT DT
Dominance, post-dominance and loop information.
DenseMap< const DILocation *, const FunctionSamples * > DILocation2SampleMap
void printEdgeWeight(raw_ostream &OS, Edge E)
Print the weight of edge E on stream OS.
typename afdo_detail::IRTraits< BT >::LoopInfoPtrT LoopInfoPtrT
void propagateWeights(FunctionT &F)
Propagate weights into edges.
std::pair< const BasicBlockT *, const BasicBlockT * > Edge
std::unique_ptr< SampleProfileReader > Reader
Profile reader object.
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.
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.
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
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
iterator_range< pred_iterator > pred_range
auto predecessors(const MachineBasicBlock *BB)
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)