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;
542namespace bfi_detail {
562template <
class BlockT,
class BFIImplT>
573 assert(BB &&
"Unexpected nullptr");
574 auto MachineName =
"BB" +
Twine(BB->getNumber());
575 if (BB->getBasicBlock())
576 return (MachineName +
"[" + BB->getName() +
"]").str();
577 return MachineName.str();
581 assert(BB &&
"Unexpected nullptr");
612 using iterator = std::deque<const IrrNode *>::const_iterator;
633 template <
class BlockEdgesAdder>
639 template <
class BlockEdgesAdder>
640 void initialize(
const BFIBase::LoopData *OuterLoop,
651 template <
class BlockEdgesAdder>
655 const BFIBase::LoopData *OuterLoop);
658template <
class BlockEdgesAdder>
663 for (
auto N : OuterLoop->
Nodes)
673template <
class BlockEdgesAdder>
683 if (Working.isAPackage())
684 for (
const auto &
I : Working.Loop->Exits)
687 addBlockEdges(*
this, Irr, OuterLoop);
852 using BranchProbabilityInfoT =
861 const BranchProbabilityInfoT *BPI =
nullptr;
862 const LoopInfoT *LI =
nullptr;
863 const FunctionT *
F =
nullptr;
866 std::vector<const BlockT *> RPOT;
869 using rpot_iterator =
typename std::vector<const BlockT *>::const_iterator;
871 rpot_iterator rpot_begin()
const {
return RPOT.
begin(); }
872 rpot_iterator rpot_end()
const {
return RPOT.end(); }
874 size_t getIndex(
const rpot_iterator &
I)
const {
return I - rpot_begin(); }
884 return RPOT[
Node.Index];
890 void initializeRPOT();
899 void initializeLoops();
927 bool tryToComputeMassInFunction();
941 void computeIrreducibleMass(
LoopData *OuterLoop,
942 std::list<LoopData>::iterator Insert);
953 void computeMassInLoops();
961 void computeMassInFunction();
977 bool needIterativeInference()
const;
980 void applyIterativeInference();
982 using ProbMatrixType = std::vector<std::vector<std::pair<size_t, Scaled64>>>;
985 void iterativeInference(
const ProbMatrixType &ProbMatrix,
986 std::vector<Scaled64> &Freq)
const;
990 void findReachableBlocks(std::vector<const BlockT *> &
Blocks)
const;
994 void initTransitionProbabilities(
995 const std::vector<const BlockT *> &
Blocks,
997 ProbMatrixType &ProbMatrix)
const;
1002 Scaled64 discrepancy(
const ProbMatrixType &ProbMatrix,
1003 const std::vector<Scaled64> &Freq)
const;
1011 void calculate(
const FunctionT &
F,
const BranchProbabilityInfoT &BPI,
1012 const LoopInfoT &LI);
1020 std::optional<uint64_t>
1022 bool AllowSynthetic =
false)
const {
1027 std::optional<uint64_t>
1029 bool AllowSynthetic =
false)
const {
1051 const BranchProbabilityInfoT &
getBPI()
const {
return *BPI; }
1071namespace bfi_detail {
1073template <
class BFIImplT>
1086 BFIImpl->forgetBlock(cast<BasicBlock>(getValPtr()));
1092template <
class BFIImplT>
1103 const BranchProbabilityInfoT &BPI,
1104 const LoopInfoT &LI) {
1117 <<
"\n================="
1118 << std::string(
F.getName().size(),
'=') <<
"\n");
1124 computeMassInLoops();
1125 computeMassInFunction();
1129 if (needIterativeInference())
1130 applyIterativeInference();
1137 for (
const BlockT &BB :
F)
1138 if (!Nodes.count(&BB))
1146 if (Nodes.count(BB))
1154 Freqs.emplace_back();
1160 const BlockT *Entry = &
F->front();
1161 RPOT.reserve(
F->size());
1162 std::copy(
po_begin(Entry),
po_end(Entry), std::back_inserter(RPOT));
1163 std::reverse(RPOT.begin(), RPOT.end());
1165 assert(RPOT.size() - 1 <= BlockNode::getMaxIndex() &&
1166 "More nodes in function than Block Frequency Info supports");
1169 for (rpot_iterator
I = rpot_begin(),
E = rpot_end();
I !=
E; ++
I) {
1173 Nodes[*
I] = {
Node, BFICallbackVH(*
I,
this)};
1176 Working.reserve(RPOT.size());
1178 Working.emplace_back(
Index);
1179 Freqs.resize(RPOT.size());
1182template <
class BT>
void BlockFrequencyInfoImpl<BT>::initializeLoops() {
1188 std::deque<std::pair<const LoopT *, LoopData *>> Q;
1189 for (
const LoopT *L : *LI)
1190 Q.emplace_back(L,
nullptr);
1191 while (!Q.empty()) {
1192 const LoopT *Loop = Q.front().first;
1193 LoopData *Parent = Q.front().second;
1196 BlockNode Header =
getNode(Loop->getHeader());
1197 assert(Header.isValid());
1199 Loops.emplace_back(Parent, Header);
1200 Working[Header.Index].Loop = &
Loops.back();
1203 for (
const LoopT *L : *Loop)
1204 Q.emplace_back(L, &
Loops.back());
1211 if (Working[
Index].isLoopHeader()) {
1212 LoopData *ContainingLoop = Working[
Index].getContainingLoop();
1214 ContainingLoop->Nodes.push_back(
Index);
1218 const LoopT *Loop = LI->getLoopFor(RPOT[
Index]);
1223 BlockNode Header =
getNode(Loop->getHeader());
1224 assert(Header.isValid());
1225 const auto &HeaderData = Working[Header.Index];
1226 assert(HeaderData.isLoopHeader());
1228 Working[
Index].Loop = HeaderData.Loop;
1229 HeaderData.Loop->Nodes.push_back(
Index);
1235template <
class BT>
void BlockFrequencyInfoImpl<BT>::computeMassInLoops() {
1237 for (
auto L =
Loops.rbegin(),
E =
Loops.rend(); L !=
E; ++L) {
1238 if (computeMassInLoop(*L))
1240 auto Next = std::next(L);
1241 computeIrreducibleMass(&*L,
L.base());
1242 L = std::prev(Next);
1243 if (computeMassInLoop(*L))
1250bool BlockFrequencyInfoImpl<BT>::computeMassInLoop(LoopData &Loop) {
1252 LLVM_DEBUG(
dbgs() <<
"compute-mass-in-loop: " << getLoopName(Loop) <<
"\n");
1254 if (Loop.isIrreducible()) {
1257 unsigned NumHeadersWithWeight = 0;
1258 std::optional<uint64_t> MinHeaderWeight;
1259 DenseSet<uint32_t> HeadersWithoutWeight;
1260 HeadersWithoutWeight.reserve(Loop.NumHeaders);
1262 auto &HeaderNode = Loop.Nodes[
H];
1263 const BlockT *
Block = getBlock(HeaderNode);
1264 IsIrrLoopHeader.set(Loop.Nodes[
H].Index);
1265 std::optional<uint64_t> HeaderWeight =
Block->getIrrLoopHeaderWeight();
1266 if (!HeaderWeight) {
1269 HeadersWithoutWeight.insert(
H);
1273 <<
" has irr loop header weight " << *HeaderWeight
1275 NumHeadersWithWeight++;
1276 uint64_t HeaderWeightValue = *HeaderWeight;
1277 if (!MinHeaderWeight || HeaderWeightValue < MinHeaderWeight)
1278 MinHeaderWeight = HeaderWeightValue;
1279 if (HeaderWeightValue) {
1280 Dist.addLocal(HeaderNode, HeaderWeightValue);
1289 if (!MinHeaderWeight)
1290 MinHeaderWeight = 1;
1291 for (
uint32_t H : HeadersWithoutWeight) {
1292 auto &HeaderNode = Loop.Nodes[
H];
1293 assert(!getBlock(HeaderNode)->getIrrLoopHeaderWeight() &&
1294 "Shouldn't have a weight metadata");
1295 uint64_t MinWeight = *MinHeaderWeight;
1299 Dist.addLocal(HeaderNode, MinWeight);
1301 distributeIrrLoopHeaderMass(Dist);
1302 for (
const BlockNode &M : Loop.Nodes)
1303 if (!propagateMassToSuccessors(&Loop, M))
1305 if (NumHeadersWithWeight == 0)
1307 adjustLoopHeaderMass(Loop);
1309 Working[Loop.getHeader().Index].getMass() = BlockMass::getFull();
1310 if (!propagateMassToSuccessors(&Loop, Loop.getHeader()))
1312 for (
const BlockNode &M : Loop.members())
1313 if (!propagateMassToSuccessors(&Loop, M))
1318 computeLoopScale(Loop);
1324bool BlockFrequencyInfoImpl<BT>::tryToComputeMassInFunction() {
1327 assert(!Working.empty() &&
"no blocks in function");
1328 assert(!Working[0].isLoopHeader() &&
"entry block is a loop header");
1330 Working[0].getMass() = BlockMass::getFull();
1331 for (rpot_iterator
I = rpot_begin(), IE = rpot_end();
I !=
IE; ++
I) {
1334 if (Working[
Node.Index].isPackaged())
1337 if (!propagateMassToSuccessors(
nullptr,
Node))
1343template <
class BT>
void BlockFrequencyInfoImpl<BT>::computeMassInFunction() {
1344 if (tryToComputeMassInFunction())
1346 computeIrreducibleMass(
nullptr,
Loops.begin());
1347 if (tryToComputeMassInFunction())
1353bool BlockFrequencyInfoImpl<BT>::needIterativeInference()
const {
1356 if (!
F->getFunction().hasProfileData())
1360 for (
auto L =
Loops.rbegin(),
E =
Loops.rend(); L !=
E; ++L) {
1361 if (
L->isIrreducible())
1367template <
class BT>
void BlockFrequencyInfoImpl<BT>::applyIterativeInference() {
1372 std::vector<const BlockT *> ReachableBlocks;
1373 findReachableBlocks(ReachableBlocks);
1374 if (ReachableBlocks.empty())
1379 DenseMap<const BlockT *, size_t> BlockIndex;
1381 auto Freq = std::vector<Scaled64>(ReachableBlocks.size());
1383 for (
size_t I = 0;
I < ReachableBlocks.size();
I++) {
1384 const BlockT *BB = ReachableBlocks[
I];
1386 Freq[
I] = getFloatingBlockFreq(BB);
1389 assert(!SumFreq.isZero() &&
"empty initial block frequencies");
1391 LLVM_DEBUG(
dbgs() <<
"Applying iterative inference for " <<
F->getName()
1392 <<
" with " << ReachableBlocks.size() <<
" blocks\n");
1395 for (
auto &Value : Freq) {
1401 ProbMatrixType ProbMatrix;
1402 initTransitionProbabilities(ReachableBlocks, BlockIndex, ProbMatrix);
1405 iterativeInference(ProbMatrix, Freq);
1408 for (
const BlockT &BB : *
F) {
1410 if (!
Node.isValid())
1412 if (
auto It = BlockIndex.find(&BB); It != BlockIndex.end())
1413 Freqs[
Node.Index].Scaled = Freq[It->second];
1415 Freqs[
Node.Index].Scaled = Scaled64::getZero();
1420void BlockFrequencyInfoImpl<BT>::iterativeInference(
1421 const ProbMatrixType &ProbMatrix, std::vector<Scaled64> &Freq)
const {
1423 "incorrectly specified precision");
1425 const auto Precision =
1431 << discrepancy(ProbMatrix, Freq).
toString() <<
"\n");
1435 auto Successors = std::vector<std::vector<size_t>>(Freq.size());
1436 for (
size_t I = 0;
I < Freq.size();
I++) {
1437 for (
const auto &Jump : ProbMatrix[
I]) {
1438 Successors[Jump.first].push_back(
I);
1446 auto IsActive = BitVector(Freq.size(),
false);
1447 std::queue<size_t> ActiveSet;
1448 for (
size_t I = 0;
I < Freq.size();
I++) {
1457 while (It++ < MaxIterations && !ActiveSet.empty()) {
1458 size_t I = ActiveSet.front();
1460 IsActive[
I] =
false;
1466 Scaled64 OneMinusSelfProb = Scaled64::getOne();
1467 for (
const auto &Jump : ProbMatrix[
I]) {
1468 if (Jump.first ==
I) {
1469 OneMinusSelfProb -= Jump.second;
1471 NewFreq += Freq[Jump.first] * Jump.second;
1474 if (OneMinusSelfProb != Scaled64::getOne())
1475 NewFreq /= OneMinusSelfProb;
1479 auto Change = Freq[
I] >= NewFreq ? Freq[
I] - NewFreq : NewFreq - Freq[
I];
1480 if (Change > Precision) {
1483 for (
size_t Succ : Successors[
I]) {
1484 if (!IsActive[Succ]) {
1485 ActiveSet.push(Succ);
1486 IsActive[Succ] =
true;
1495 LLVM_DEBUG(
dbgs() <<
" Completed " << It <<
" inference iterations"
1496 <<
format(
" (%0.0f per block)",
double(It) / Freq.size())
1500 << discrepancy(ProbMatrix, Freq).
toString() <<
"\n");
1505void BlockFrequencyInfoImpl<BT>::findReachableBlocks(
1506 std::vector<const BlockT *> &
Blocks)
const {
1509 std::queue<const BlockT *>
Queue;
1510 SmallPtrSet<const BlockT *, 8> Reachable;
1511 const BlockT *
Entry = &
F->front();
1513 Reachable.insert(Entry);
1514 while (!
Queue.empty()) {
1515 const BlockT *SrcBB =
Queue.front();
1517 for (
const BlockT *DstBB : children<const BlockT *>(SrcBB)) {
1518 auto EP = BPI->getEdgeProbability(SrcBB, DstBB);
1521 if (Reachable.insert(DstBB).second)
1528 SmallPtrSet<const BlockT *, 8> InverseReachable;
1529 for (
const BlockT &BB : *
F) {
1531 bool HasSucc = !llvm::children<const BlockT *>(&BB).empty();
1532 if (!HasSucc && Reachable.count(&BB)) {
1534 InverseReachable.insert(&BB);
1537 while (!
Queue.empty()) {
1538 const BlockT *SrcBB =
Queue.front();
1540 for (
const BlockT *DstBB : inverse_children<const BlockT *>(SrcBB)) {
1541 auto EP = BPI->getEdgeProbability(DstBB, SrcBB);
1544 if (InverseReachable.insert(DstBB).second)
1551 for (
const BlockT &BB : *
F) {
1552 if (Reachable.count(&BB) && InverseReachable.count(&BB)) {
1559void BlockFrequencyInfoImpl<BT>::initTransitionProbabilities(
1560 const std::vector<const BlockT *> &
Blocks,
1561 const DenseMap<const BlockT *, size_t> &BlockIndex,
1562 ProbMatrixType &ProbMatrix)
const {
1563 const size_t NumBlocks =
Blocks.size();
1564 auto Succs = std::vector<std::vector<std::pair<size_t, Scaled64>>>(NumBlocks);
1565 auto SumProb = std::vector<Scaled64>(NumBlocks);
1568 for (
size_t Src = 0; Src < NumBlocks; Src++) {
1569 const BlockT *BB =
Blocks[Src];
1570 SmallPtrSet<const BlockT *, 2> UniqueSuccs;
1571 for (
const auto SI : children<const BlockT *>(BB)) {
1573 if (!BlockIndex.contains(SI))
1576 if (!UniqueSuccs.insert(SI).second)
1579 auto EP = BPI->getEdgeProbability(BB, SI);
1584 Scaled64::getFraction(EP.getNumerator(), EP.getDenominator());
1585 size_t Dst = BlockIndex.find(SI)->second;
1586 Succs[Src].push_back(std::make_pair(Dst, EdgeProb));
1587 SumProb[Src] += EdgeProb;
1592 ProbMatrix = ProbMatrixType(NumBlocks);
1593 for (
size_t Src = 0; Src < NumBlocks; Src++) {
1595 if (Succs[Src].empty())
1598 assert(!SumProb[Src].
isZero() &&
"Zero sum probability of non-exit block");
1599 for (
auto &Jump : Succs[Src]) {
1600 size_t Dst = Jump.first;
1601 Scaled64 Prob = Jump.second;
1602 ProbMatrix[Dst].push_back(std::make_pair(Src, Prob / SumProb[Src]));
1607 size_t EntryIdx = BlockIndex.find(&
F->front())->second;
1608 for (
size_t Src = 0; Src < NumBlocks; Src++) {
1609 if (Succs[Src].empty()) {
1610 ProbMatrix[EntryIdx].push_back(std::make_pair(Src, Scaled64::getOne()));
1618 const ProbMatrixType &ProbMatrix,
const std::vector<Scaled64> &Freq)
const {
1619 assert(Freq[0] > 0 &&
"Incorrectly computed frequency of the entry block");
1620 Scaled64 Discrepancy;
1621 for (
size_t I = 0;
I < ProbMatrix.size();
I++) {
1623 for (
const auto &Jump : ProbMatrix[
I]) {
1624 Sum += Freq[Jump.first] * Jump.second;
1626 Discrepancy += Freq[
I] >= Sum ? Freq[
I] - Sum : Sum - Freq[
I];
1629 return Discrepancy / Freq[0];
1634namespace bfi_detail {
1649 for (
const auto *Succ : children<const BlockT *>(BB))
1650 G.addEdge(Irr,
BFI.getNode(Succ), OuterLoop);
1657void BlockFrequencyInfoImpl<BT>::computeIrreducibleMass(
1658 LoopData *OuterLoop, std::list<LoopData>::iterator Insert) {
1660 if (OuterLoop)
dbgs()
1661 <<
"loop: " << getLoopName(*OuterLoop) <<
"\n";
1662 else dbgs() <<
"function\n");
1664 using namespace bfi_detail;
1668 BlockEdgesAdder<BT> addBlockEdges(*
this);
1669 IrreducibleGraph
G(*
this, OuterLoop, addBlockEdges);
1671 for (
auto &L : analyzeIrreducible(
G, OuterLoop, Insert))
1672 computeMassInLoop(L);
1676 updateLoopWithIrreducible(*OuterLoop);
1686BlockFrequencyInfoImpl<BT>::propagateMassToSuccessors(LoopData *OuterLoop,
1687 const BlockNode &
Node) {
1691 if (
auto *Loop = Working[
Node.Index].getPackagedLoop()) {
1692 assert(Loop != OuterLoop &&
"Cannot propagate mass in a packaged loop");
1693 if (!addLoopSuccessorsToDist(OuterLoop, *Loop, Dist))
1697 const BlockT *BB = getBlock(
Node);
1698 for (
auto SI = GraphTraits<const BlockT *>::child_begin(BB),
1699 SE = GraphTraits<const BlockT *>::child_end(BB);
1710 distributeMass(
Node, OuterLoop, Dist);
1718 OS <<
"block-frequency-info: " <<
F->getName() <<
"\n";
1719 for (
const BlockT &BB : *
F) {
1721 getFloatingBlockFreq(&BB).print(
OS, 5)
1722 <<
", int = " << getBlockFreq(&BB).getFrequency();
1727 if (std::optional<uint64_t> IrrLoopHeaderWeight =
1728 BB.getIrrLoopHeaderWeight())
1729 OS <<
", irr_loop_header_weight = " << *IrrLoopHeaderWeight;
1744 for (
auto &Entry : Nodes) {
1745 const BlockT *BB = Entry.first;
1747 ValidNodes[BB] = Entry.second.first;
1750 for (
auto &Entry :
Other.Nodes) {
1751 const BlockT *BB = Entry.first;
1753 OtherValidNodes[BB] = Entry.second.first;
1756 unsigned NumValidNodes = ValidNodes.
size();
1757 unsigned NumOtherValidNodes = OtherValidNodes.
size();
1758 if (NumValidNodes != NumOtherValidNodes) {
1760 dbgs() <<
"Number of blocks mismatch: " << NumValidNodes <<
" vs "
1761 << NumOtherValidNodes <<
"\n";
1763 for (
auto &Entry : ValidNodes) {
1764 const BlockT *BB = Entry.first;
1766 if (
auto It = OtherValidNodes.
find(BB); It != OtherValidNodes.
end()) {
1768 const auto &Freq = Freqs[
Node.Index];
1769 const auto &OtherFreq =
Other.Freqs[OtherNode.
Index];
1770 if (Freq.Integer != OtherFreq.Integer) {
1773 << Freq.Integer <<
" vs " << OtherFreq.Integer <<
"\n";
1778 <<
Node.Index <<
" does not exist in Other.\n";
1787 dbgs() <<
"Other\n";
1798template <
class BlockFrequencyInfoT,
class BranchProbabilityInfoT>
1811 return G->getFunction()->getName();
1815 unsigned HotPercentThreshold = 0) {
1817 if (!HotPercentThreshold)
1822 for (
NodeIter I = GTraits::nodes_begin(Graph),
1823 E = GTraits::nodes_end(Graph);
1827 std::max(
MaxFrequency, Graph->getBlockFreq(
N).getFrequency());
1839 OS <<
"color=\"red\"";
1845 GVDAGType GType,
int layout_order = -1) {
1849 if (layout_order != -1)
1850 OS <<
Node->getName() <<
"[" << layout_order <<
"] : ";
1852 OS <<
Node->getName() <<
" : ";
1858 OS << Graph->getBlockFreq(
Node).getFrequency();
1861 auto Count = Graph->getBlockProfileCount(
Node);
1870 "never reach this point.");
1876 const BlockFrequencyInfoT *BFI,
1877 const BranchProbabilityInfoT *BPI,
1878 unsigned HotPercentThreshold = 0) {
1890 if (HotPercentThreshold) {
1895 if (EFreq >= HotFreq) {
1896 OS <<
",color=\"red\"";
static msgpack::DocNode getNode(msgpack::DocNode DN, msgpack::Type Type, MCValue Val)
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.
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.
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, BlockFrequency Freq)
BlockFrequency getEntryFreq() const
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
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.
std::optional< uint64_t > getProfileCountFromFreq(const Function &F, BlockFrequency Freq, bool AllowSynthetic=false) const
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.
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
void verifyMatch(BlockFrequencyInfoImpl< BT > &Other) const
Scaled64 getFloatingBlockFreq(const BlockT *BB) const
std::optional< uint64_t > getProfileCountFromFreq(const Function &F, BlockFrequency Freq, bool AllowSynthetic=false) const
void calculate(const FunctionT &F, const BranchProbabilityInfoT &BPI, const LoopInfoT &LI)
void setBlockFreq(const BlockT *BB, BlockFrequency 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...
iterator find(const_arg_type_t< KeyT > Val)
bool erase(const KeyT &Val)
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)
This is an optimization pass for GlobalISel generic memory operations.
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
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.
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
llvm::cl::opt< unsigned > IterativeBFIMaxIterationsPerBlock
po_iterator< T > po_begin(const T &G)
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
const char * toString(DWARFSectionKind Kind)
Printable printBlockFreq(const BlockFrequencyInfo &BFI, BlockFrequency Freq)
Print the block frequency Freq relative to the current functions entry frequency.
po_iterator< T > po_end(const T &G)
llvm::cl::opt< double > IterativeBFIPrecision
Implement std::hash so that hash_code can be used in STL containers.
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)