14#ifndef LLVM_ANALYSIS_BLOCKFREQUENCYINFOIMPL_H
15#define LLVM_ANALYSIS_BLOCKFREQUENCYINFOIMPL_H
52#define DEBUG_TYPE "block-freq"
61class BranchProbabilityInfo;
65class MachineBasicBlock;
66class MachineBranchProbabilityInfo;
102 return BlockMass(std::numeric_limits<uint64_t>::max());
107 bool isFull()
const {
return Mass == std::numeric_limits<uint64_t>::max(); }
117 Mass = Sum < Mass ? std::numeric_limits<uint64_t>::max() : Sum;
127 Mass = Diff > Mass ? 0 : Diff;
132 Mass =
P.scale(Mass);
210 return std::numeric_limits<uint32_t>::max() - 1;
241 template <
class It1,
class It2>
298 return Loop->Parent->Parent;
316 return L ? L->getHeader() :
Node;
323 while (L->Parent && L->Parent->IsPackaged)
338 return Loop->Parent->Mass;
468 std::list<LoopData>::iterator Insert);
526 std::optional<uint64_t>
528 bool AllowSynthetic =
false)
const;
529 std::optional<uint64_t>
531 bool AllowSynthetic =
false)
const;
542 return Freqs[0].Integer;
546namespace bfi_detail {
566template <
class BlockT,
class BFIImplT>
577 assert(BB &&
"Unexpected nullptr");
578 auto MachineName =
"BB" +
Twine(BB->getNumber());
579 if (BB->getBasicBlock())
580 return (MachineName +
"[" + BB->getName() +
"]").str();
581 return MachineName.str();
585 assert(BB &&
"Unexpected nullptr");
616 using iterator = std::deque<const IrrNode *>::const_iterator;
637 template <
class BlockEdgesAdder>
643 template <
class BlockEdgesAdder>
644 void initialize(
const BFIBase::LoopData *OuterLoop,
655 template <
class BlockEdgesAdder>
659 const BFIBase::LoopData *OuterLoop);
662template <
class BlockEdgesAdder>
667 for (
auto N : OuterLoop->
Nodes)
677template <
class BlockEdgesAdder>
687 if (Working.isAPackage())
688 for (
const auto &
I : Working.Loop->Exits)
691 addBlockEdges(*
this, Irr, OuterLoop);
856 using BranchProbabilityInfoT =
865 const BranchProbabilityInfoT *BPI =
nullptr;
866 const LoopInfoT *LI =
nullptr;
867 const FunctionT *
F =
nullptr;
870 std::vector<const BlockT *> RPOT;
873 using rpot_iterator =
typename std::vector<const BlockT *>::const_iterator;
875 rpot_iterator rpot_begin()
const {
return RPOT.
begin(); }
876 rpot_iterator rpot_end()
const {
return RPOT.end(); }
878 size_t getIndex(
const rpot_iterator &
I)
const {
return I - rpot_begin(); }
880 BlockNode getNode(
const rpot_iterator &
I)
const {
884 BlockNode getNode(
const BlockT *BB)
const {
return Nodes.
lookup(BB).first; }
888 return RPOT[
Node.Index];
894 void initializeRPOT();
903 void initializeLoops();
931 bool tryToComputeMassInFunction();
945 void computeIrreducibleMass(
LoopData *OuterLoop,
946 std::list<LoopData>::iterator Insert);
957 void computeMassInLoops();
965 void computeMassInFunction();
981 bool needIterativeInference()
const;
984 void applyIterativeInference();
986 using ProbMatrixType = std::vector<std::vector<std::pair<size_t, Scaled64>>>;
989 void iterativeInference(
const ProbMatrixType &ProbMatrix,
990 std::vector<Scaled64> &Freq)
const;
994 void findReachableBlocks(std::vector<const BlockT *> &
Blocks)
const;
998 void initTransitionProbabilities(
999 const std::vector<const BlockT *> &
Blocks,
1001 ProbMatrixType &ProbMatrix)
const;
1006 Scaled64 discrepancy(
const ProbMatrixType &ProbMatrix,
1007 const std::vector<Scaled64> &Freq)
const;
1015 void calculate(
const FunctionT &
F,
const BranchProbabilityInfoT &BPI,
1016 const LoopInfoT &LI);
1024 std::optional<uint64_t>
1026 bool AllowSynthetic =
false)
const {
1031 std::optional<uint64_t>
1033 bool AllowSynthetic =
false)
const {
1055 const BranchProbabilityInfoT &
getBPI()
const {
return *BPI; }
1080namespace bfi_detail {
1082template <
class BFIImplT>
1095 BFIImpl->forgetBlock(cast<BasicBlock>(getValPtr()));
1101template <
class BFIImplT>
1112 const BranchProbabilityInfoT &BPI,
1113 const LoopInfoT &LI) {
1126 <<
"\n================="
1127 << std::string(
F.getName().size(),
'=') <<
"\n");
1133 computeMassInLoops();
1134 computeMassInFunction();
1138 if (needIterativeInference())
1139 applyIterativeInference();
1146 for (
const BlockT &BB :
F)
1147 if (!Nodes.count(&BB))
1148 setBlockFreq(&BB, 0);
1154 if (Nodes.count(BB))
1162 Freqs.emplace_back();
1168 const BlockT *Entry = &
F->front();
1169 RPOT.reserve(
F->size());
1170 std::copy(
po_begin(Entry),
po_end(Entry), std::back_inserter(RPOT));
1171 std::reverse(RPOT.begin(), RPOT.end());
1173 assert(RPOT.size() - 1 <= BlockNode::getMaxIndex() &&
1174 "More nodes in function than Block Frequency Info supports");
1177 for (rpot_iterator
I = rpot_begin(),
E = rpot_end();
I !=
E; ++
I) {
1178 BlockNode
Node = getNode(
I);
1181 Nodes[*
I] = {
Node, BFICallbackVH(*
I,
this)};
1184 Working.reserve(RPOT.size());
1186 Working.emplace_back(
Index);
1187 Freqs.resize(RPOT.size());
1190template <
class BT>
void BlockFrequencyInfoImpl<BT>::initializeLoops() {
1196 std::deque<std::pair<const LoopT *, LoopData *>> Q;
1197 for (
const LoopT *L : *LI)
1198 Q.emplace_back(L,
nullptr);
1199 while (!Q.empty()) {
1200 const LoopT *Loop = Q.front().first;
1201 LoopData *Parent = Q.front().second;
1204 BlockNode Header = getNode(Loop->getHeader());
1205 assert(Header.isValid());
1207 Loops.emplace_back(Parent, Header);
1208 Working[Header.Index].Loop = &
Loops.back();
1211 for (
const LoopT *L : *Loop)
1212 Q.emplace_back(L, &
Loops.back());
1219 if (Working[
Index].isLoopHeader()) {
1220 LoopData *ContainingLoop = Working[
Index].getContainingLoop();
1222 ContainingLoop->Nodes.push_back(
Index);
1226 const LoopT *Loop = LI->getLoopFor(RPOT[
Index]);
1231 BlockNode Header = getNode(Loop->getHeader());
1232 assert(Header.isValid());
1233 const auto &HeaderData = Working[Header.Index];
1234 assert(HeaderData.isLoopHeader());
1236 Working[
Index].Loop = HeaderData.Loop;
1237 HeaderData.Loop->Nodes.push_back(
Index);
1243template <
class BT>
void BlockFrequencyInfoImpl<BT>::computeMassInLoops() {
1245 for (
auto L =
Loops.rbegin(),
E =
Loops.rend(); L !=
E; ++L) {
1246 if (computeMassInLoop(*L))
1248 auto Next = std::next(L);
1249 computeIrreducibleMass(&*L,
L.base());
1250 L = std::prev(Next);
1251 if (computeMassInLoop(*L))
1258bool BlockFrequencyInfoImpl<BT>::computeMassInLoop(LoopData &Loop) {
1260 LLVM_DEBUG(
dbgs() <<
"compute-mass-in-loop: " << getLoopName(Loop) <<
"\n");
1262 if (Loop.isIrreducible()) {
1265 unsigned NumHeadersWithWeight = 0;
1266 std::optional<uint64_t> MinHeaderWeight;
1267 DenseSet<uint32_t> HeadersWithoutWeight;
1268 HeadersWithoutWeight.reserve(Loop.NumHeaders);
1270 auto &HeaderNode = Loop.Nodes[
H];
1271 const BlockT *
Block = getBlock(HeaderNode);
1272 IsIrrLoopHeader.set(Loop.Nodes[
H].Index);
1273 std::optional<uint64_t> HeaderWeight =
Block->getIrrLoopHeaderWeight();
1274 if (!HeaderWeight) {
1277 HeadersWithoutWeight.insert(
H);
1281 <<
" has irr loop header weight " << *HeaderWeight
1283 NumHeadersWithWeight++;
1284 uint64_t HeaderWeightValue = *HeaderWeight;
1285 if (!MinHeaderWeight || HeaderWeightValue < MinHeaderWeight)
1286 MinHeaderWeight = HeaderWeightValue;
1287 if (HeaderWeightValue) {
1288 Dist.addLocal(HeaderNode, HeaderWeightValue);
1297 if (!MinHeaderWeight)
1298 MinHeaderWeight = 1;
1299 for (
uint32_t H : HeadersWithoutWeight) {
1300 auto &HeaderNode = Loop.Nodes[
H];
1301 assert(!getBlock(HeaderNode)->getIrrLoopHeaderWeight() &&
1302 "Shouldn't have a weight metadata");
1303 uint64_t MinWeight = *MinHeaderWeight;
1307 Dist.addLocal(HeaderNode, MinWeight);
1309 distributeIrrLoopHeaderMass(Dist);
1310 for (
const BlockNode &M : Loop.Nodes)
1311 if (!propagateMassToSuccessors(&Loop, M))
1313 if (NumHeadersWithWeight == 0)
1315 adjustLoopHeaderMass(Loop);
1317 Working[Loop.getHeader().Index].getMass() = BlockMass::getFull();
1318 if (!propagateMassToSuccessors(&Loop, Loop.getHeader()))
1320 for (
const BlockNode &M : Loop.members())
1321 if (!propagateMassToSuccessors(&Loop, M))
1326 computeLoopScale(Loop);
1332bool BlockFrequencyInfoImpl<BT>::tryToComputeMassInFunction() {
1335 assert(!Working.empty() &&
"no blocks in function");
1336 assert(!Working[0].isLoopHeader() &&
"entry block is a loop header");
1338 Working[0].getMass() = BlockMass::getFull();
1339 for (rpot_iterator
I = rpot_begin(), IE = rpot_end();
I !=
IE; ++
I) {
1341 BlockNode
Node = getNode(
I);
1342 if (Working[
Node.Index].isPackaged())
1345 if (!propagateMassToSuccessors(
nullptr,
Node))
1351template <
class BT>
void BlockFrequencyInfoImpl<BT>::computeMassInFunction() {
1352 if (tryToComputeMassInFunction())
1354 computeIrreducibleMass(
nullptr,
Loops.begin());
1355 if (tryToComputeMassInFunction())
1361bool BlockFrequencyInfoImpl<BT>::needIterativeInference()
const {
1364 if (!
F->getFunction().hasProfileData())
1368 for (
auto L =
Loops.rbegin(),
E =
Loops.rend(); L !=
E; ++L) {
1369 if (
L->isIrreducible())
1375template <
class BT>
void BlockFrequencyInfoImpl<BT>::applyIterativeInference() {
1380 std::vector<const BlockT *> ReachableBlocks;
1381 findReachableBlocks(ReachableBlocks);
1382 if (ReachableBlocks.empty())
1387 DenseMap<const BlockT *, size_t> BlockIndex;
1389 auto Freq = std::vector<Scaled64>(ReachableBlocks.size());
1391 for (
size_t I = 0;
I < ReachableBlocks.size();
I++) {
1392 const BlockT *BB = ReachableBlocks[
I];
1394 Freq[
I] = getFloatingBlockFreq(BB);
1397 assert(!SumFreq.isZero() &&
"empty initial block frequencies");
1399 LLVM_DEBUG(
dbgs() <<
"Applying iterative inference for " <<
F->getName()
1400 <<
" with " << ReachableBlocks.size() <<
" blocks\n");
1403 for (
auto &Value : Freq) {
1409 ProbMatrixType ProbMatrix;
1410 initTransitionProbabilities(ReachableBlocks, BlockIndex, ProbMatrix);
1413 iterativeInference(ProbMatrix, Freq);
1416 for (
const BlockT &BB : *
F) {
1417 auto Node = getNode(&BB);
1418 if (!
Node.isValid())
1420 if (BlockIndex.count(&BB)) {
1421 Freqs[
Node.Index].Scaled = Freq[BlockIndex[&BB]];
1423 Freqs[
Node.Index].Scaled = Scaled64::getZero();
1429void BlockFrequencyInfoImpl<BT>::iterativeInference(
1430 const ProbMatrixType &ProbMatrix, std::vector<Scaled64> &Freq)
const {
1432 "incorrectly specified precision");
1434 const auto Precision =
1440 << discrepancy(ProbMatrix, Freq).
toString() <<
"\n");
1444 auto Successors = std::vector<std::vector<size_t>>(Freq.size());
1445 for (
size_t I = 0;
I < Freq.size();
I++) {
1446 for (
const auto &Jump : ProbMatrix[
I]) {
1447 Successors[Jump.first].push_back(
I);
1455 auto IsActive = BitVector(Freq.size(),
false);
1456 std::queue<size_t> ActiveSet;
1457 for (
size_t I = 0;
I < Freq.size();
I++) {
1466 while (It++ < MaxIterations && !ActiveSet.empty()) {
1467 size_t I = ActiveSet.front();
1469 IsActive[
I] =
false;
1475 Scaled64 OneMinusSelfProb = Scaled64::getOne();
1476 for (
const auto &Jump : ProbMatrix[
I]) {
1477 if (Jump.first ==
I) {
1478 OneMinusSelfProb -= Jump.second;
1480 NewFreq += Freq[Jump.first] * Jump.second;
1483 if (OneMinusSelfProb != Scaled64::getOne())
1484 NewFreq /= OneMinusSelfProb;
1488 auto Change = Freq[
I] >= NewFreq ? Freq[
I] - NewFreq : NewFreq - Freq[
I];
1489 if (Change > Precision) {
1492 for (
size_t Succ : Successors[
I]) {
1493 if (!IsActive[Succ]) {
1494 ActiveSet.push(Succ);
1495 IsActive[Succ] =
true;
1504 LLVM_DEBUG(
dbgs() <<
" Completed " << It <<
" inference iterations"
1505 <<
format(
" (%0.0f per block)",
double(It) / Freq.size())
1509 << discrepancy(ProbMatrix, Freq).
toString() <<
"\n");
1514void BlockFrequencyInfoImpl<BT>::findReachableBlocks(
1515 std::vector<const BlockT *> &
Blocks)
const {
1518 std::queue<const BlockT *>
Queue;
1519 SmallPtrSet<const BlockT *, 8> Reachable;
1520 const BlockT *Entry = &
F->front();
1522 Reachable.insert(Entry);
1523 while (!
Queue.empty()) {
1524 const BlockT *SrcBB =
Queue.front();
1526 for (
const BlockT *DstBB : children<const BlockT *>(SrcBB)) {
1527 auto EP = BPI->getEdgeProbability(SrcBB, DstBB);
1530 if (Reachable.insert(DstBB).second)
1537 SmallPtrSet<const BlockT *, 8> InverseReachable;
1538 for (
const BlockT &BB : *
F) {
1540 bool HasSucc = GraphTraits<const BlockT *>::child_begin(&BB) !=
1541 GraphTraits<const BlockT *>::child_end(&BB);
1542 if (!HasSucc && Reachable.count(&BB)) {
1544 InverseReachable.insert(&BB);
1547 while (!
Queue.empty()) {
1548 const BlockT *SrcBB =
Queue.front();
1550 for (
const BlockT *DstBB :
children<Inverse<const BlockT *>>(SrcBB)) {
1551 auto EP = BPI->getEdgeProbability(DstBB, SrcBB);
1554 if (InverseReachable.insert(DstBB).second)
1561 for (
const BlockT &BB : *
F) {
1562 if (Reachable.count(&BB) && InverseReachable.count(&BB)) {
1569void BlockFrequencyInfoImpl<BT>::initTransitionProbabilities(
1570 const std::vector<const BlockT *> &
Blocks,
1571 const DenseMap<const BlockT *, size_t> &BlockIndex,
1572 ProbMatrixType &ProbMatrix)
const {
1573 const size_t NumBlocks =
Blocks.size();
1574 auto Succs = std::vector<std::vector<std::pair<size_t, Scaled64>>>(NumBlocks);
1575 auto SumProb = std::vector<Scaled64>(NumBlocks);
1578 for (
size_t Src = 0; Src < NumBlocks; Src++) {
1579 const BlockT *BB =
Blocks[Src];
1580 SmallPtrSet<const BlockT *, 2> UniqueSuccs;
1581 for (
const auto SI : children<const BlockT *>(BB)) {
1583 if (BlockIndex.find(SI) == BlockIndex.end())
1586 if (!UniqueSuccs.insert(SI).second)
1589 auto EP = BPI->getEdgeProbability(BB, SI);
1594 Scaled64::getFraction(EP.getNumerator(), EP.getDenominator());
1595 size_t Dst = BlockIndex.find(SI)->second;
1596 Succs[Src].push_back(std::make_pair(Dst, EdgeProb));
1597 SumProb[Src] += EdgeProb;
1602 ProbMatrix = ProbMatrixType(NumBlocks);
1603 for (
size_t Src = 0; Src < NumBlocks; Src++) {
1605 if (Succs[Src].empty())
1608 assert(!SumProb[Src].
isZero() &&
"Zero sum probability of non-exit block");
1609 for (
auto &Jump : Succs[Src]) {
1610 size_t Dst = Jump.first;
1612 ProbMatrix[Dst].push_back(std::make_pair(Src, Prob / SumProb[Src]));
1617 size_t EntryIdx = BlockIndex.find(&
F->front())->second;
1618 for (
size_t Src = 0; Src < NumBlocks; Src++) {
1619 if (Succs[Src].empty()) {
1620 ProbMatrix[EntryIdx].push_back(std::make_pair(Src, Scaled64::getOne()));
1628 const ProbMatrixType &ProbMatrix,
const std::vector<Scaled64> &Freq)
const {
1629 assert(Freq[0] > 0 &&
"Incorrectly computed frequency of the entry block");
1631 for (
size_t I = 0;
I < ProbMatrix.size();
I++) {
1633 for (
const auto &Jump : ProbMatrix[
I]) {
1634 Sum += Freq[Jump.first] * Jump.second;
1636 Discrepancy += Freq[
I] >= Sum ? Freq[
I] - Sum : Sum - Freq[
I];
1639 return Discrepancy / Freq[0];
1644namespace bfi_detail {
1659 for (
const auto *Succ : children<const BlockT *>(BB))
1660 G.addEdge(Irr,
BFI.getNode(Succ), OuterLoop);
1667void BlockFrequencyInfoImpl<BT>::computeIrreducibleMass(
1668 LoopData *OuterLoop, std::list<LoopData>::iterator Insert) {
1670 if (OuterLoop)
dbgs()
1671 <<
"loop: " << getLoopName(*OuterLoop) <<
"\n";
1672 else dbgs() <<
"function\n");
1674 using namespace bfi_detail;
1678 BlockEdgesAdder<BT> addBlockEdges(*
this);
1679 IrreducibleGraph
G(*
this, OuterLoop, addBlockEdges);
1681 for (
auto &L : analyzeIrreducible(
G, OuterLoop, Insert))
1682 computeMassInLoop(L);
1686 updateLoopWithIrreducible(*OuterLoop);
1696BlockFrequencyInfoImpl<BT>::propagateMassToSuccessors(LoopData *OuterLoop,
1697 const BlockNode &
Node) {
1701 if (
auto *Loop = Working[
Node.Index].getPackagedLoop()) {
1702 assert(Loop != OuterLoop &&
"Cannot propagate mass in a packaged loop");
1703 if (!addLoopSuccessorsToDist(OuterLoop, *Loop, Dist))
1707 const BlockT *BB = getBlock(
Node);
1708 for (
auto SI = GraphTraits<const BlockT *>::child_begin(BB),
1709 SE = GraphTraits<const BlockT *>::child_end(BB);
1712 Dist, OuterLoop,
Node, getNode(*SI),
1720 distributeMass(
Node, OuterLoop, Dist);
1728 OS <<
"block-frequency-info: " <<
F->getName() <<
"\n";
1729 for (
const BlockT &BB : *
F) {
1731 getFloatingBlockFreq(&BB).print(
OS, 5)
1732 <<
", int = " << getBlockFreq(&BB).getFrequency();
1735 F->getFunction(), getNode(&BB)))
1737 if (std::optional<uint64_t> IrrLoopHeaderWeight =
1738 BB.getIrrLoopHeaderWeight())
1739 OS <<
", irr_loop_header_weight = " << *IrrLoopHeaderWeight;
1754 for (
auto &Entry : Nodes) {
1755 const BlockT *BB = Entry.first;
1757 ValidNodes[BB] = Entry.second.first;
1760 for (
auto &Entry :
Other.Nodes) {
1761 const BlockT *BB = Entry.first;
1763 OtherValidNodes[BB] = Entry.second.first;
1766 unsigned NumValidNodes = ValidNodes.
size();
1767 unsigned NumOtherValidNodes = OtherValidNodes.
size();
1768 if (NumValidNodes != NumOtherValidNodes) {
1770 dbgs() <<
"Number of blocks mismatch: " << NumValidNodes <<
" vs "
1771 << NumOtherValidNodes <<
"\n";
1773 for (
auto &Entry : ValidNodes) {
1774 const BlockT *BB = Entry.first;
1776 if (OtherValidNodes.
count(BB)) {
1777 BlockNode OtherNode = OtherValidNodes[BB];
1778 const auto &Freq = Freqs[
Node.Index];
1779 const auto &OtherFreq =
Other.Freqs[OtherNode.
Index];
1780 if (Freq.Integer != OtherFreq.Integer) {
1783 << Freq.Integer <<
" vs " << OtherFreq.Integer <<
"\n";
1788 <<
Node.Index <<
" does not exist in Other.\n";
1797 dbgs() <<
"Other\n";
1808template <
class BlockFrequencyInfoT,
class BranchProbabilityInfoT>
1821 return G->getFunction()->getName();
1825 unsigned HotPercentThreshold = 0) {
1827 if (!HotPercentThreshold)
1832 for (
NodeIter I = GTraits::nodes_begin(Graph),
1833 E = GTraits::nodes_end(Graph);
1837 std::max(
MaxFrequency, Graph->getBlockFreq(
N).getFrequency());
1849 OS <<
"color=\"red\"";
1855 GVDAGType GType,
int layout_order = -1) {
1859 if (layout_order != -1)
1860 OS <<
Node->getName() <<
"[" << layout_order <<
"] : ";
1862 OS <<
Node->getName() <<
" : ";
1865 Graph->printBlockFreq(
OS,
Node);
1868 OS << Graph->getBlockFreq(
Node).getFrequency();
1871 auto Count = Graph->getBlockProfileCount(
Node);
1880 "never reach this point.");
1886 const BlockFrequencyInfoT *BFI,
1887 const BranchProbabilityInfoT *BPI,
1888 unsigned HotPercentThreshold = 0) {
1900 if (HotPercentThreshold) {
1905 if (EFreq >= HotFreq) {
1906 OS <<
",color=\"red\"";
This file implements the BitVector class.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
DenseMap< Block *, BlockRelaxAux > Blocks
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
This file defines the little GraphTraits<X> template class that should be specialized by classes that...
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
Branch Probability Basic Block static false std::string getBlockName(const MachineBasicBlock *BB)
Helper to print the name of a MBB.
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the SparseBitVector class.
ScaledNumber< uint64_t > Scaled64
Value handle that asserts if the Value is deleted.
LLVM Basic Block Representation.
Base class for BlockFrequencyInfoImpl.
std::vector< WorkingData > Working
Loop data: see initializeLoops().
virtual ~BlockFrequencyInfoImplBase()=default
Virtual destructor.
std::list< LoopData > Loops
Indexed information about loops.
raw_ostream & printBlockFreq(raw_ostream &OS, const BlockNode &Node) const
bool addLoopSuccessorsToDist(const LoopData *OuterLoop, LoopData &Loop, Distribution &Dist)
Add all edges out of a packaged loop to the distribution.
ScaledNumber< uint64_t > Scaled64
std::string getLoopName(const LoopData &Loop) const
bool isIrrLoopHeader(const BlockNode &Node)
void computeLoopScale(LoopData &Loop)
Compute the loop scale for a loop.
void packageLoop(LoopData &Loop)
Package up a loop.
virtual raw_ostream & print(raw_ostream &OS) const
virtual std::string getBlockName(const BlockNode &Node) const
void finalizeMetrics()
Finalize frequency metrics.
void setBlockFreq(const BlockNode &Node, uint64_t Freq)
void updateLoopWithIrreducible(LoopData &OuterLoop)
Update a loop after packaging irreducible SCCs inside of it.
void clear()
Clear all memory.
std::optional< uint64_t > getBlockProfileCount(const Function &F, const BlockNode &Node, bool AllowSynthetic=false) const
BlockFrequency getBlockFreq(const BlockNode &Node) const
uint64_t getEntryFreq() const
void distributeIrrLoopHeaderMass(Distribution &Dist)
iterator_range< std::list< LoopData >::iterator > analyzeIrreducible(const bfi_detail::IrreducibleGraph &G, LoopData *OuterLoop, std::list< LoopData >::iterator Insert)
Analyze irreducible SCCs.
bool addToDist(Distribution &Dist, const LoopData *OuterLoop, const BlockNode &Pred, const BlockNode &Succ, uint64_t Weight)
Add an edge to the distribution.
void unwrapLoops()
Unwrap loops.
Scaled64 getFloatingBlockFreq(const BlockNode &Node) const
void distributeMass(const BlockNode &Source, LoopData *OuterLoop, Distribution &Dist)
Distribute mass according to a distribution.
SparseBitVector IsIrrLoopHeader
Whether each block is an irreducible loop header.
std::vector< FrequencyData > Freqs
Data about each block. This is used downstream.
std::optional< uint64_t > getProfileCountFromFreq(const Function &F, uint64_t Freq, bool AllowSynthetic=false) const
void adjustLoopHeaderMass(LoopData &Loop)
Adjust the mass of all headers in an irreducible loop.
Shared implementation for block frequency analysis.
bool isIrrLoopHeader(const BlockT *BB)
std::optional< uint64_t > getBlockProfileCount(const Function &F, const BlockT *BB, bool AllowSynthetic=false) const
const BranchProbabilityInfoT & getBPI() const
const FunctionT * getFunction() const
std::optional< uint64_t > getProfileCountFromFreq(const Function &F, uint64_t Freq, bool AllowSynthetic=false) const
void verifyMatch(BlockFrequencyInfoImpl< BT > &Other) const
Scaled64 getFloatingBlockFreq(const BlockT *BB) const
void calculate(const FunctionT &F, const BranchProbabilityInfoT &BPI, const LoopInfoT &LI)
raw_ostream & printBlockFreq(raw_ostream &OS, const BlockT *BB) const
void setBlockFreq(const BlockT *BB, uint64_t Freq)
BlockFrequencyInfoImpl()=default
raw_ostream & print(raw_ostream &OS) const override
Print the frequencies for the current function.
void forgetBlock(const BlockT *BB)
BlockFrequency getBlockFreq(const BlockT *BB) const
Analysis providing branch probability information.
static BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
static uint32_t getDenominator()
uint32_t getNumerator() const
Value handle with callbacks on RAUW and destruction.
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
bool erase(const KeyT &Val)
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Class to represent profile counts.
Represents a single loop in the control flow graph.
Simple representation of a scaled number.
iterator insert(iterator I, T &&Elt)
StringRef - Represent a constant reference to a string, i.e.
std::string str() const
str - Get the contents as an std::string.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
The instances of the Type class are immutable: once they are created, they are never changed.
StringRef getName() const
Return a constant reference to the value's name.
void deleted() override
Callback for Value destruction.
BFICallbackVH(const BasicBlock *BB, BFIImplT *BFIImpl)
virtual ~BFICallbackVH()=default
BFICallbackVH(const MachineBasicBlock *, BFIImplT *)
bool operator<(BlockMass X) const
bool operator>(BlockMass X) const
raw_ostream & print(raw_ostream &OS) const
bool operator==(BlockMass X) const
static BlockMass getEmpty()
BlockMass & operator-=(BlockMass X)
Subtract another mass.
bool operator<=(BlockMass X) const
BlockMass & operator*=(BranchProbability P)
static BlockMass getFull()
bool operator!=(BlockMass X) const
BlockMass & operator+=(BlockMass X)
Add another mass.
bool operator>=(BlockMass X) const
ScaledNumber< uint64_t > toScaled() const
Convert to scaled number.
A range adaptor for a pair of iterators.
This class implements an extremely fast bulk output stream that can only output to a stream.
A raw_ostream that writes to an std::string.
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
std::string getBlockName(const BlockT *BB)
Get the name of a MachineBasicBlock.
BlockMass operator*(BlockMass L, BranchProbability R)
BlockMass operator+(BlockMass L, BlockMass R)
raw_ostream & operator<<(raw_ostream &OS, BlockMass X)
BlockMass operator-(BlockMass L, BlockMass R)
std::optional< const char * > toString(const std::optional< DWARFFormValue > &V)
Take an optional DWARFFormValue and try to extract a string value from it.
This is an optimization pass for GlobalISel generic memory operations.
uint32_t getWeightFromBranchProb(const BranchProbability Prob)
Function::ProfileCount ProfileCount
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
llvm::cl::opt< unsigned > IterativeBFIMaxIterationsPerBlock
po_iterator< T > po_begin(const T &G)
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
llvm::cl::opt< bool > UseIterativeBFIInference
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
format_object< Ts... > format(const char *Fmt, const Ts &... Vals)
These are helper functions used to produce formatted output.
llvm::cl::opt< bool > CheckBFIUnknownBlockQueries
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)
po_iterator< T > po_end(const T &G)
llvm::cl::opt< double > IterativeBFIPrecision
std::string getNodeAttributes(NodeRef Node, const BlockFrequencyInfoT *Graph, unsigned HotPercentThreshold=0)
typename GTraits::nodes_iterator NodeIter
typename GTraits::NodeRef NodeRef
typename GTraits::ChildIteratorType EdgeIter
std::string getNodeLabel(NodeRef Node, const BlockFrequencyInfoT *Graph, GVDAGType GType, int layout_order=-1)
std::string getEdgeAttributes(NodeRef Node, EdgeIter EI, const BlockFrequencyInfoT *BFI, const BranchProbabilityInfoT *BPI, unsigned HotPercentThreshold=0)
BFIDOTGraphTraitsBase(bool isSimple=false)
static StringRef getGraphName(const BlockFrequencyInfoT *G)
Representative of a block.
bool operator==(const BlockNode &X) const
bool operator!=(const BlockNode &X) const
bool operator<(const BlockNode &X) const
bool operator>=(const BlockNode &X) const
BlockNode(IndexType Index)
static size_t getMaxIndex()
bool operator<=(const BlockNode &X) const
bool operator>(const BlockNode &X) const
Distribution of unscaled probability weight.
void addBackedge(const BlockNode &Node, uint64_t Amount)
WeightList Weights
Individual successor weights.
uint64_t Total
Sum of all weights.
void normalize()
Normalize the distribution.
void addExit(const BlockNode &Node, uint64_t Amount)
bool DidOverflow
Whether Total did overflow.
void addLocal(const BlockNode &Node, uint64_t Amount)
Stats about a block itself.
bool isHeader(const BlockNode &Node) const
LoopData * Parent
The parent loop.
LoopData(LoopData *Parent, It1 FirstHeader, It1 LastHeader, It2 FirstOther, It2 LastOther)
ExitMap Exits
Successor edges (and weights).
uint32_t NumHeaders
Number of headers.
bool IsPackaged
Whether this has been packaged.
LoopData(LoopData *Parent, const BlockNode &Header)
NodeList::const_iterator members_end() const
NodeList::const_iterator members_begin() const
bool isIrreducible() const
BlockNode getHeader() const
NodeList Nodes
Header and the members of the loop.
HeaderMassList BackedgeMass
Mass returned to each loop header.
HeaderMassList::difference_type getHeaderIndex(const BlockNode &B)
iterator_range< NodeList::const_iterator > members() const
Unscaled probability weight.
Weight(DistType Type, BlockNode TargetNode, uint64_t Amount)
Index of loop information.
bool isPackaged() const
Has ContainingLoop been packaged up?
BlockMass Mass
Mass distribution from the entry block.
BlockMass & getMass()
Get the appropriate mass for a node.
WorkingData(const BlockNode &Node)
bool isAPackage() const
Has Loop been packaged up?
bool isLoopHeader() const
bool isDoubleLoopHeader() const
LoopData * Loop
The loop this block is inside.
LoopData * getContainingLoop() const
LoopData * getPackagedLoop() const
BlockNode getResolvedNode() const
Resolve a node to its representative.
bool isADoublePackage() const
Has Loop been packaged up twice?
DefaultDOTGraphTraits - This class provides the default implementations of all of the DOTGraphTraits ...
typename GraphType::UnknownGraphTypeError NodeRef
BlockEdgesAdder(const BlockFrequencyInfoImpl< BT > &BFI)
const BlockFrequencyInfoImpl< BT > & BFI
void operator()(IrreducibleGraph &G, IrreducibleGraph::IrrNode &Irr, const LoopData *OuterLoop)
iterator pred_end() const
IrrNode(const BlockNode &Node)
iterator pred_begin() const
iterator succ_begin() const
std::deque< const IrrNode * >::const_iterator iterator
std::deque< const IrrNode * > Edges
iterator succ_end() const
Graph of irreducible control flow.
void addNodesInFunction()
IrreducibleGraph(BFIBase &BFI, const BFIBase::LoopData *OuterLoop, BlockEdgesAdder addBlockEdges)
Construct an explicit graph containing irreducible control flow.
void addEdge(IrrNode &Irr, const BlockNode &Succ, const BFIBase::LoopData *OuterLoop)
void addEdges(const BlockNode &Node, const BFIBase::LoopData *OuterLoop, BlockEdgesAdder addBlockEdges)
BFIBase::BlockNode BlockNode
std::vector< IrrNode > Nodes
SmallDenseMap< uint32_t, IrrNode *, 4 > Lookup
void initialize(const BFIBase::LoopData *OuterLoop, BlockEdgesAdder addBlockEdges)
void addNode(const BlockNode &Node)
void addNodesInLoop(const BFIBase::LoopData &OuterLoop)