Go to the documentation of this file.
15 #ifndef LLVM_TRANSFORMS_UTILS_SAMPLEPROFILELOADERBASEIMPL_H
16 #define LLVM_TRANSFORMS_UTILS_SAMPLEPROFILELOADERBASEIMPL_H
45 using namespace sampleprof;
46 using namespace sampleprofutil;
49 #define DEBUG_TYPE "sample-profile-impl"
51 namespace afdo_detail {
70 return &
F->getEntryBlock();
84 : Filename(
Name), RemappingFilename(RemapName) {}
85 void dump() { Reader->dump(); }
110 using Edge = std::pair<const BasicBlockT *, const BasicBlockT *>;
132 unsigned getFunctionLoc(FunctionT &Func);
154 bool propagateThroughEdges(
FunctionT &
F,
bool UpdateBlockCount);
155 void clearFunctionData(
bool ResetDT =
true);
156 void computeDominanceAndLoopInfo(
FunctionT &
F);
208 std::unique_ptr<SampleProfileReader>
Reader;
227 template <
typename BT>
229 BlockWeights.clear();
231 VisitedBlocks.clear();
232 VisitedEdges.clear();
233 EquivalenceClass.clear();
239 Predecessors.clear();
241 CoverageTracker.clear();
249 template <
typename BT>
251 OS <<
"weight[" <<
E.first->getName() <<
"->" <<
E.second->getName()
252 <<
"]: " << EdgeWeights[
E] <<
"\n";
259 template <
typename BT>
263 OS <<
"equivalence[" <<
BB->getName()
264 <<
"]: " << ((Equiv) ? EquivalenceClass[
BB]->
getName() :
"NONE") <<
"\n";
271 template <
typename BT>
274 const auto &
I = BlockWeights.find(
BB);
275 uint64_t W = (
I == BlockWeights.end() ? 0 :
I->second);
276 OS <<
"weight[" <<
BB->getName() <<
"]: " <<
W <<
"\n";
291 template <
typename BT>
294 return getInstWeightImpl(Inst);
297 template <
typename BT>
302 return std::error_code();
304 const DebugLoc &DLoc = Inst.getDebugLoc();
306 return std::error_code();
312 Discriminator = DIL->getDiscriminator();
319 CoverageTracker.markSamplesUsed(
FS, LineOffset, Discriminator,
R.get());
324 Remark <<
" samples from profile (offset: ";
335 << Inst <<
" (line offset: " << LineOffset <<
"."
336 << Discriminator <<
" - weight: " <<
R.get() <<
")\n");
349 template <
typename BT>
353 bool HasWeight =
false;
354 for (
auto &
I : *
BB) {
370 template <
typename BT>
372 bool Changed =
false;
374 for (
const auto &
BB :
F) {
377 BlockWeights[&
BB] = Weight.
get();
378 VisitedBlocks.insert(&
BB);
396 template <
typename BT>
403 auto it = DILocation2SampleMap.try_emplace(DIL,
nullptr);
405 it.first->second = Samples->findFunctionSamples(DIL, Reader->getRemapper());
407 return it.first->second;
433 template <
typename BT>
439 for (
const auto *BB2 : Descendants) {
440 bool IsDomParent = DomTree->dominates(BB2, BB1);
441 bool IsInSameLoop = LI->getLoopFor(BB1) == LI->getLoopFor(BB2);
442 if (BB1 != BB2 && IsDomParent && IsInSameLoop) {
443 EquivalenceClass[BB2] = EC;
445 if (VisitedBlocks.count(BB2)) {
446 VisitedBlocks.insert(EC);
457 Weight =
std::max(Weight, BlockWeights[BB2]);
460 const BasicBlockT *EntryBB = getEntryBB(EC->getParent());
462 BlockWeights[EC] = Samples->getHeadSamples() + 1;
464 BlockWeights[EC] = Weight;
477 template <
typename BT>
486 if (EquivalenceClass.count(BB1)) {
492 EquivalenceClass[BB1] = BB1;
504 DominatedBBs.
clear();
505 DT->getDescendants(BB1, DominatedBBs);
506 findEquivalencesFor(BB1, DominatedBBs, &*PDT);
518 dbgs() <<
"\nAssign the same weight to all blocks in the same class\n");
523 BlockWeights[
BB] = BlockWeights[EquivBB];
538 template <
typename BT>
540 unsigned *NumUnknownEdges,
542 if (!VisitedEdges.count(
E)) {
543 (*NumUnknownEdges)++;
548 return EdgeWeights[
E];
564 template <
typename BT>
567 bool Changed =
false;
569 for (
const auto &BI :
F) {
578 for (
unsigned i = 0;
i < 2;
i++) {
580 unsigned NumUnknownEdges = 0, NumTotalEdges = 0;
581 Edge UnknownEdge, SelfReferentialEdge, SingleEdge;
585 NumTotalEdges = Predecessors[
BB].size();
586 for (
auto *Pred : Predecessors[
BB]) {
587 Edge E = std::make_pair(Pred,
BB);
588 TotalWeight +=
visitEdge(
E, &NumUnknownEdges, &UnknownEdge);
589 if (
E.first ==
E.second)
590 SelfReferentialEdge =
E;
592 if (NumTotalEdges == 1) {
593 SingleEdge = std::make_pair(Predecessors[
BB][0],
BB);
597 NumTotalEdges = Successors[
BB].size();
598 for (
auto *Succ : Successors[
BB]) {
599 Edge E = std::make_pair(
BB, Succ);
600 TotalWeight +=
visitEdge(
E, &NumUnknownEdges, &UnknownEdge);
602 if (NumTotalEdges == 1) {
603 SingleEdge = std::make_pair(
BB, Successors[
BB][0]);
630 if (NumUnknownEdges <= 1) {
631 uint64_t &BBWeight = BlockWeights[EC];
632 if (NumUnknownEdges == 0) {
633 if (!VisitedBlocks.count(EC)) {
637 if (TotalWeight > BBWeight) {
638 BBWeight = TotalWeight;
641 <<
" known. Set weight for block: ";
642 printBlockWeight(
dbgs(),
BB););
644 }
else if (NumTotalEdges == 1 &&
645 EdgeWeights[SingleEdge] < BlockWeights[EC]) {
648 EdgeWeights[SingleEdge] = BlockWeights[EC];
651 }
else if (NumUnknownEdges == 1 && VisitedBlocks.count(EC)) {
654 if (BBWeight >= TotalWeight)
655 EdgeWeights[UnknownEdge] = BBWeight - TotalWeight;
657 EdgeWeights[UnknownEdge] = 0;
660 OtherEC = EquivalenceClass[UnknownEdge.first];
662 OtherEC = EquivalenceClass[UnknownEdge.second];
664 if (VisitedBlocks.count(OtherEC) &&
665 EdgeWeights[UnknownEdge] > BlockWeights[OtherEC])
666 EdgeWeights[UnknownEdge] = BlockWeights[OtherEC];
667 VisitedEdges.insert(UnknownEdge);
670 printEdgeWeight(
dbgs(), UnknownEdge));
672 }
else if (VisitedBlocks.count(EC) && BlockWeights[EC] == 0) {
675 for (
auto *Pred : Predecessors[
BB]) {
676 Edge E = std::make_pair(Pred,
BB);
678 VisitedEdges.insert(
E);
681 for (
auto *Succ : Successors[
BB]) {
682 Edge E = std::make_pair(
BB, Succ);
684 VisitedEdges.insert(
E);
687 }
else if (SelfReferentialEdge.first && VisitedBlocks.count(EC)) {
690 if (BBWeight >= TotalWeight)
691 EdgeWeights[SelfReferentialEdge] = BBWeight - TotalWeight;
693 EdgeWeights[SelfReferentialEdge] = 0;
694 VisitedEdges.insert(SelfReferentialEdge);
697 printEdgeWeight(
dbgs(), SelfReferentialEdge));
699 if (UpdateBlockCount && !VisitedBlocks.count(EC) && TotalWeight > 0) {
700 BlockWeights[EC] = TotalWeight;
701 VisitedBlocks.insert(EC);
714 template <
typename BT>
723 for (
auto *B2 : getPredecessors(
B1))
724 if (Visited.
insert(B2).second)
725 Predecessors[
B1].push_back(B2);
731 for (
auto *B2 : getSuccessors(
B1))
732 if (Visited.
insert(B2).second)
733 Successors[
B1].push_back(B2);
754 template <
typename BT>
761 for (
const auto &BI :
F) {
764 SampleBlockWeights[&BI] = Weight.
get();
767 applyProfi(
F, Successors, SampleBlockWeights, BlockWeights, EdgeWeights);
781 if (Header && BlockWeights[
BB] > BlockWeights[Header]) {
782 BlockWeights[Header] = BlockWeights[
BB];
788 Changed = propagateThroughEdges(
F,
false);
794 VisitedEdges.clear();
797 Changed = propagateThroughEdges(
F,
false);
804 Changed = propagateThroughEdges(
F,
true);
809 template <
typename BT>
814 Infer.apply(BlockWeights, EdgeWeights);
863 template <
typename BT>
866 bool Changed = (InlinedGUIDs.
size() != 0);
869 Changed |= computeBlockWeights(
F);
873 initWeightPropagation(
F, InlinedGUIDs);
879 finalizeWeightPropagation(
F, InlinedGUIDs);
885 template <
typename BT>
899 computeDominanceAndLoopInfo(
F);
902 findEquivalenceClasses(
F);
913 template <
typename BT>
925 if (BlockWeights[EntryBB] > 0 &&
934 template <
typename BT>
939 unsigned Used = CoverageTracker.countUsedRecords(Samples, PSI);
940 unsigned Total = CoverageTracker.countBodyRecords(Samples, PSI);
941 unsigned Coverage = CoverageTracker.computeCoverage(Used, Total);
944 Func.getSubprogram()->getFilename(), getFunctionLoc(
F),
945 Twine(Used) +
" of " +
Twine(Total) +
" available profile records (" +
946 Twine(Coverage) +
"%) were applied",
952 uint64_t Used = CoverageTracker.getTotalUsedSamples();
953 uint64_t Total = CoverageTracker.countBodySamples(Samples, PSI);
954 unsigned Coverage = CoverageTracker.computeCoverage(Used, Total);
957 Func.getSubprogram()->getFilename(), getFunctionLoc(
F),
958 Twine(Used) +
" of " +
Twine(Total) +
" available profile samples (" +
959 Twine(Coverage) +
"%) were applied",
976 template <
typename BT>
988 "No debug information found in function " + Func.getName() +
989 ": Function profile not used",
994 template <
typename BT>
1009 #endif // LLVM_TRANSFORMS_UTILS_SAMPLEPROFILELOADERBASEIMPL_H
const BasicBlockT * getEntryBB(const FunctionT *F)
static StringRef getName(Value *V)
This is an optimization pass for GlobalISel generic memory operations.
typename afdo_detail::IRTraits< MachineBasicBlock >::OptRemarkAnalysisT OptRemarkAnalysisT
into xmm2 addss xmm2 xmm1 xmm3 addss xmm3 movaps xmm0 unpcklps xmm0 ret seems silly when it could just be one addps Expand libm rounding functions main should enable SSE DAZ mode and other fast SSE modes Think about doing i64 math in SSE regs on x86 This testcase should have no SSE instructions in it
Function & getFunction(FunctionT &F)
uint64_t visitEdge(Edge E, unsigned *NumUnknownEdges, Edge *UnknownEdge)
Visit the given edge to decide if it has a valid weight.
static Function * getFunction(Constant *C)
Represents a single loop in the control flow graph.
typename afdo_detail::IRTraits< MachineBasicBlock >::SuccRangeT SuccRangeT
std::unique_ptr< PostDominatorTree > PostDominatorTreePtrT
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
BlockEdgeMap Predecessors
Predecessors for each basic block in the CFG.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
BlockEdgeMap Successors
Successors for each basic block in the CFG.
cl::opt< bool > EnableFSDiscriminator
static succ_range getSuccessors(BasicBlock *BB)
DominatorTreePtrT DT
Dominance, post-dominance and loop information.
DiagnosticInfoOptimizationBase::Argument NV
auto successors(MachineBasicBlock *BB)
typename afdo_detail::IRTraits< MachineBasicBlock >::BlockFrequencyInfoT BlockFrequencyInfoT
static Function & getFunction(Function &F)
LLVM Basic Block Representation.
void initWeightPropagation(FunctionT &F, const DenseSet< GlobalValue::GUID > &InlinedGUIDs)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
ErrorOr< uint64_t > getBlockWeight(const BasicBlockT *BB)
Compute the weight of a basic block.
cl::opt< bool > SampleProfileUseProfi
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
bool propagateThroughEdges(FunctionT &F, bool UpdateBlockCount)
Propagate weights through incoming/outgoing edges.
void printBlockEquivalence(raw_ostream &OS, const BasicBlockT *BB)
Print the equivalence class of block BB on stream OS.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static const BasicBlock * getEntryBB(const Function *F)
BlockWeightMap BlockWeights
Map basic blocks to their computed weights.
std::string Filename
Name of the profile file to load.
void computeDominanceAndLoopInfo(FunctionT &F)
auto predecessors(MachineBasicBlock *BB)
This class implements an extremely fast bulk output stream that can only output to a stream.
void printEdgeWeight(raw_ostream &OS, Edge E)
Print the weight of edge E on stream OS.
typename afdo_detail::IRTraits< MachineBasicBlock >::LoopInfoPtrT LoopInfoPtrT
typename afdo_detail::IRTraits< MachineBasicBlock >::PostDominatorTreeT PostDominatorTreeT
virtual const FunctionSamples * findFunctionSamples(const InstructionT &I) const
Get the FunctionSamples for an instruction.
virtual ErrorOr< uint64_t > getInstWeight(const InstructionT &Inst)
Get the weight for an instruction.
std::unique_ptr< SampleProfileReader > Reader
Profile reader object.
void emitCoverageRemarks(FunctionT &F)
SampleProfileLoaderBaseImpl(std::string Name, std::string RemapName)
void clearFunctionData(bool ResetDT=true)
Clear all the per-function data used to load samples and propagate weights.
Analysis providing profile information.
typename afdo_detail::IRTraits< MachineBasicBlock >::PredRangeT PredRangeT
unsigned getFunctionLoc(FunctionT &Func)
Get the line number for the function header.
Implements a dense probed hash-table based set.
bool computeAndPropagateWeights(FunctionT &F, const DenseSet< GlobalValue::GUID > &InlinedGUIDs)
Generate branch weight metadata for all branches in F.
Function::ProfileCount ProfileCount
bool computeBlockWeights(FunctionT &F)
Compute and store the weights of every basic block.
typename afdo_detail::IRTraits< MachineBasicBlock >::DominatorTreePtrT DominatorTreePtrT
iterator_range< succ_iterator > succ_range
PostDominatorTreePtrT PDT
Representation of the samples collected for a function.
typename afdo_detail::IRTraits< MachineBasicBlock >::InstructionT InstructionT
SampleCoverageTracker CoverageTracker
Profile coverage tracker.
ErrorOr< uint64_t > getInstWeightImpl(const InstructionT &Inst)
static pred_range getPredecessors(BasicBlock *BB)
void findEquivalenceClasses(FunctionT &F)
Find equivalence classes.
cl::opt< bool > SampleProfileInferEntryCount
EquivalenceClassMap EquivalenceClass
Equivalence classes for block weights.
SmallPtrSet< const BasicBlockT *, 32 > VisitedBlocks
Set of visited blocks during propagation.
void visitEdge(LinkGraph &G, Block *B, Edge &E)
Base case for edge-visitors where the visitor-list is empty.
@ BasicBlock
Various leaf nodes.
typename afdo_detail::IRTraits< MachineBasicBlock >::PostDominatorTreePtrT PostDominatorTreePtrT
void buildEdges(FunctionT &F)
Build in/out edge lists for each basic block in the CFG.
static unsigned getOffset(const DILocation *DIL)
Returns the line offset to the start line of the subprogram.
Diagnostic information for the sample profiler.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
cl::opt< unsigned > SampleProfileSampleCoverage
typename afdo_detail::IRTraits< MachineBasicBlock >::LoopT LoopT
std::string RemappingFilename
Name of the profile remapping file to load.
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
typename afdo_detail::IRTraits< MachineBasicBlock >::BasicBlockT BasicBlockT
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
void applyProfi(FunctionT &F, BlockEdgeMap &Successors, BlockWeightMap &SampleBlockWeights, BlockWeightMap &BlockWeights, EdgeWeightMap &EdgeWeights)
void propagateWeights(FunctionT &F)
Propagate weights into edges.
void printBlockWeight(raw_ostream &OS, const BasicBlockT *BB) const
Print the weight of block BB on stream OS.
void findEquivalencesFor(BasicBlockT *BB1, ArrayRef< BasicBlockT * > Descendants, PostDominatorTreeT *DomTree)
Find equivalence classes for the given block.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
SmallSet< Edge, 32 > VisitedEdges
Set of visited edges during propagation.
std::unique_ptr< DominatorTree > DominatorTreePtrT
void finalizeWeightPropagation(FunctionT &F, const DenseSet< GlobalValue::GUID > &InlinedGUIDs)
PredRangeT getPredecessors(BasicBlockT *BB)
unsigned getBaseDiscriminator() const
Returns the base discriminator stored in the discriminator.
std::pair< const BasicBlockT *, const BasicBlockT * > Edge
Sample profile inference pass.
iterator_range< pred_iterator > pred_range
SuccRangeT getSuccessors(BasicBlockT *BB)
Represents either an error or a value T.
cl::opt< unsigned > SampleProfileRecordCoverage
Align max(MaybeAlign Lhs, Align Rhs)
cl::opt< unsigned > SampleProfileMaxPropagateIterations
A range adaptor for a pair of iterators.
EdgeWeightMap EdgeWeights
Map edges to their computed weights.
typename afdo_detail::IRTraits< MachineBasicBlock >::FunctionT FunctionT
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Class to represent profile counts.
typename afdo_detail::IRTraits< MachineBasicBlock >::OptRemarkEmitterT OptRemarkEmitterT
std::unique_ptr< LoopInfo > LoopInfoPtrT
DenseMap< const DILocation *, const FunctionSamples * > DILocation2SampleMap
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
cl::opt< bool > NoWarnSampleUnused