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 (BlockIndex.count(&BB)) {
1413 Freqs[
Node.Index].Scaled = Freq[BlockIndex[&BB]];
1415 Freqs[
Node.Index].Scaled = Scaled64::getZero();
1421void BlockFrequencyInfoImpl<BT>::iterativeInference(
1422 const ProbMatrixType &ProbMatrix, std::vector<Scaled64> &Freq)
const {
1424 "incorrectly specified precision");
1426 const auto Precision =
1432 << discrepancy(ProbMatrix, Freq).
toString() <<
"\n");
1436 auto Successors = std::vector<std::vector<size_t>>(Freq.size());
1437 for (
size_t I = 0;
I < Freq.size();
I++) {
1438 for (
const auto &Jump : ProbMatrix[
I]) {
1439 Successors[Jump.first].push_back(
I);
1447 auto IsActive = BitVector(Freq.size(),
false);
1448 std::queue<size_t> ActiveSet;
1449 for (
size_t I = 0;
I < Freq.size();
I++) {
1458 while (It++ < MaxIterations && !ActiveSet.empty()) {
1459 size_t I = ActiveSet.front();
1461 IsActive[
I] =
false;
1467 Scaled64 OneMinusSelfProb = Scaled64::getOne();
1468 for (
const auto &Jump : ProbMatrix[
I]) {
1469 if (Jump.first ==
I) {
1470 OneMinusSelfProb -= Jump.second;
1472 NewFreq += Freq[Jump.first] * Jump.second;
1475 if (OneMinusSelfProb != Scaled64::getOne())
1476 NewFreq /= OneMinusSelfProb;
1480 auto Change = Freq[
I] >= NewFreq ? Freq[
I] - NewFreq : NewFreq - Freq[
I];
1481 if (Change > Precision) {
1484 for (
size_t Succ : Successors[
I]) {
1485 if (!IsActive[Succ]) {
1486 ActiveSet.push(Succ);
1487 IsActive[Succ] =
true;
1496 LLVM_DEBUG(
dbgs() <<
" Completed " << It <<
" inference iterations"
1497 <<
format(
" (%0.0f per block)",
double(It) / Freq.size())
1501 << discrepancy(ProbMatrix, Freq).
toString() <<
"\n");
1506void BlockFrequencyInfoImpl<BT>::findReachableBlocks(
1507 std::vector<const BlockT *> &
Blocks)
const {
1510 std::queue<const BlockT *>
Queue;
1511 SmallPtrSet<const BlockT *, 8> Reachable;
1512 const BlockT *
Entry = &
F->front();
1514 Reachable.insert(Entry);
1515 while (!
Queue.empty()) {
1516 const BlockT *SrcBB =
Queue.front();
1518 for (
const BlockT *DstBB : children<const BlockT *>(SrcBB)) {
1519 auto EP = BPI->getEdgeProbability(SrcBB, DstBB);
1522 if (Reachable.insert(DstBB).second)
1529 SmallPtrSet<const BlockT *, 8> InverseReachable;
1530 for (
const BlockT &BB : *
F) {
1532 bool HasSucc = !llvm::children<const BlockT *>(&BB).empty();
1533 if (!HasSucc && Reachable.count(&BB)) {
1535 InverseReachable.insert(&BB);
1538 while (!
Queue.empty()) {
1539 const BlockT *SrcBB =
Queue.front();
1541 for (
const BlockT *DstBB : inverse_children<const BlockT *>(SrcBB)) {
1542 auto EP = BPI->getEdgeProbability(DstBB, SrcBB);
1545 if (InverseReachable.insert(DstBB).second)
1552 for (
const BlockT &BB : *
F) {
1553 if (Reachable.count(&BB) && InverseReachable.count(&BB)) {
1560void BlockFrequencyInfoImpl<BT>::initTransitionProbabilities(
1561 const std::vector<const BlockT *> &
Blocks,
1562 const DenseMap<const BlockT *, size_t> &BlockIndex,
1563 ProbMatrixType &ProbMatrix)
const {
1564 const size_t NumBlocks =
Blocks.size();
1565 auto Succs = std::vector<std::vector<std::pair<size_t, Scaled64>>>(NumBlocks);
1566 auto SumProb = std::vector<Scaled64>(NumBlocks);
1569 for (
size_t Src = 0; Src < NumBlocks; Src++) {
1570 const BlockT *BB =
Blocks[Src];
1571 SmallPtrSet<const BlockT *, 2> UniqueSuccs;
1572 for (
const auto SI : children<const BlockT *>(BB)) {
1574 if (!BlockIndex.contains(SI))
1577 if (!UniqueSuccs.insert(SI).second)
1580 auto EP = BPI->getEdgeProbability(BB, SI);
1585 Scaled64::getFraction(EP.getNumerator(), EP.getDenominator());
1586 size_t Dst = BlockIndex.find(SI)->second;
1587 Succs[Src].push_back(std::make_pair(Dst, EdgeProb));
1588 SumProb[Src] += EdgeProb;
1593 ProbMatrix = ProbMatrixType(NumBlocks);
1594 for (
size_t Src = 0; Src < NumBlocks; Src++) {
1596 if (Succs[Src].empty())
1599 assert(!SumProb[Src].
isZero() &&
"Zero sum probability of non-exit block");
1600 for (
auto &Jump : Succs[Src]) {
1601 size_t Dst = Jump.first;
1602 Scaled64 Prob = Jump.second;
1603 ProbMatrix[Dst].push_back(std::make_pair(Src, Prob / SumProb[Src]));
1608 size_t EntryIdx = BlockIndex.find(&
F->front())->second;
1609 for (
size_t Src = 0; Src < NumBlocks; Src++) {
1610 if (Succs[Src].empty()) {
1611 ProbMatrix[EntryIdx].push_back(std::make_pair(Src, Scaled64::getOne()));
1619 const ProbMatrixType &ProbMatrix,
const std::vector<Scaled64> &Freq)
const {
1620 assert(Freq[0] > 0 &&
"Incorrectly computed frequency of the entry block");
1621 Scaled64 Discrepancy;
1622 for (
size_t I = 0;
I < ProbMatrix.size();
I++) {
1624 for (
const auto &Jump : ProbMatrix[
I]) {
1625 Sum += Freq[Jump.first] * Jump.second;
1627 Discrepancy += Freq[
I] >= Sum ? Freq[
I] - Sum : Sum - Freq[
I];
1630 return Discrepancy / Freq[0];
1635namespace bfi_detail {
1650 for (
const auto *Succ : children<const BlockT *>(BB))
1651 G.addEdge(Irr,
BFI.getNode(Succ), OuterLoop);
1658void BlockFrequencyInfoImpl<BT>::computeIrreducibleMass(
1659 LoopData *OuterLoop, std::list<LoopData>::iterator Insert) {
1661 if (OuterLoop)
dbgs()
1662 <<
"loop: " << getLoopName(*OuterLoop) <<
"\n";
1663 else dbgs() <<
"function\n");
1665 using namespace bfi_detail;
1669 BlockEdgesAdder<BT> addBlockEdges(*
this);
1670 IrreducibleGraph
G(*
this, OuterLoop, addBlockEdges);
1672 for (
auto &L : analyzeIrreducible(
G, OuterLoop, Insert))
1673 computeMassInLoop(L);
1677 updateLoopWithIrreducible(*OuterLoop);
1687BlockFrequencyInfoImpl<BT>::propagateMassToSuccessors(LoopData *OuterLoop,
1688 const BlockNode &
Node) {
1692 if (
auto *Loop = Working[
Node.Index].getPackagedLoop()) {
1693 assert(Loop != OuterLoop &&
"Cannot propagate mass in a packaged loop");
1694 if (!addLoopSuccessorsToDist(OuterLoop, *Loop, Dist))
1698 const BlockT *BB = getBlock(
Node);
1699 for (
auto SI = GraphTraits<const BlockT *>::child_begin(BB),
1700 SE = GraphTraits<const BlockT *>::child_end(BB);
1711 distributeMass(
Node, OuterLoop, Dist);
1719 OS <<
"block-frequency-info: " <<
F->getName() <<
"\n";
1720 for (
const BlockT &BB : *
F) {
1722 getFloatingBlockFreq(&BB).print(
OS, 5)
1723 <<
", int = " << getBlockFreq(&BB).getFrequency();
1728 if (std::optional<uint64_t> IrrLoopHeaderWeight =
1729 BB.getIrrLoopHeaderWeight())
1730 OS <<
", irr_loop_header_weight = " << *IrrLoopHeaderWeight;
1745 for (
auto &Entry : Nodes) {
1746 const BlockT *BB = Entry.first;
1748 ValidNodes[BB] = Entry.second.first;
1751 for (
auto &Entry :
Other.Nodes) {
1752 const BlockT *BB = Entry.first;
1754 OtherValidNodes[BB] = Entry.second.first;
1757 unsigned NumValidNodes = ValidNodes.
size();
1758 unsigned NumOtherValidNodes = OtherValidNodes.
size();
1759 if (NumValidNodes != NumOtherValidNodes) {
1761 dbgs() <<
"Number of blocks mismatch: " << NumValidNodes <<
" vs "
1762 << NumOtherValidNodes <<
"\n";
1764 for (
auto &Entry : ValidNodes) {
1765 const BlockT *BB = Entry.first;
1767 if (OtherValidNodes.
count(BB)) {
1768 BlockNode OtherNode = OtherValidNodes[BB];
1769 const auto &Freq = Freqs[
Node.Index];
1770 const auto &OtherFreq =
Other.Freqs[OtherNode.
Index];
1771 if (Freq.Integer != OtherFreq.Integer) {
1774 << Freq.Integer <<
" vs " << OtherFreq.Integer <<
"\n";
1779 <<
Node.Index <<
" does not exist in Other.\n";
1788 dbgs() <<
"Other\n";
1799template <
class BlockFrequencyInfoT,
class BranchProbabilityInfoT>
1812 return G->getFunction()->getName();
1816 unsigned HotPercentThreshold = 0) {
1818 if (!HotPercentThreshold)
1823 for (
NodeIter I = GTraits::nodes_begin(Graph),
1824 E = GTraits::nodes_end(Graph);
1828 std::max(
MaxFrequency, Graph->getBlockFreq(
N).getFrequency());
1840 OS <<
"color=\"red\"";
1846 GVDAGType GType,
int layout_order = -1) {
1850 if (layout_order != -1)
1851 OS <<
Node->getName() <<
"[" << layout_order <<
"] : ";
1853 OS <<
Node->getName() <<
" : ";
1859 OS << Graph->getBlockFreq(
Node).getFrequency();
1862 auto Count = Graph->getBlockProfileCount(
Node);
1871 "never reach this point.");
1877 const BlockFrequencyInfoT *BFI,
1878 const BranchProbabilityInfoT *BPI,
1879 unsigned HotPercentThreshold = 0) {
1891 if (HotPercentThreshold) {
1896 if (EFreq >= HotFreq) {
1897 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...
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)
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)