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;
543 BlockFrequency Freq);
545namespace bfi_detail {
565template <
class BlockT,
class BFIImplT>
576 assert(BB &&
"Unexpected nullptr");
577 auto MachineName =
"BB" +
Twine(BB->getNumber());
578 if (BB->getBasicBlock())
579 return (MachineName +
"[" + BB->getName() +
"]").str();
580 return MachineName.str();
584 assert(BB &&
"Unexpected nullptr");
615 using iterator = std::deque<const IrrNode *>::const_iterator;
636 template <
class BlockEdgesAdder>
642 template <
class BlockEdgesAdder>
643 void initialize(
const BFIBase::LoopData *OuterLoop,
654 template <
class BlockEdgesAdder>
658 const BFIBase::LoopData *OuterLoop);
661template <
class BlockEdgesAdder>
666 for (
auto N : OuterLoop->
Nodes)
676template <
class BlockEdgesAdder>
686 if (Working.isAPackage())
687 for (
const auto &
I : Working.Loop->Exits)
690 addBlockEdges(*
this, Irr, OuterLoop);
855 using BranchProbabilityInfoT =
864 const BranchProbabilityInfoT *BPI =
nullptr;
865 const LoopInfoT *LI =
nullptr;
866 const FunctionT *
F =
nullptr;
869 std::vector<const BlockT *> RPOT;
872 using rpot_iterator =
typename std::vector<const BlockT *>::const_iterator;
874 rpot_iterator rpot_begin()
const {
return RPOT.
begin(); }
875 rpot_iterator rpot_end()
const {
return RPOT.end(); }
877 size_t getIndex(
const rpot_iterator &
I)
const {
return I - rpot_begin(); }
879 BlockNode getNode(
const rpot_iterator &
I)
const {
883 BlockNode getNode(
const BlockT *BB)
const {
return Nodes.
lookup(BB).first; }
887 return RPOT[
Node.Index];
893 void initializeRPOT();
902 void initializeLoops();
930 bool tryToComputeMassInFunction();
944 void computeIrreducibleMass(
LoopData *OuterLoop,
945 std::list<LoopData>::iterator Insert);
956 void computeMassInLoops();
964 void computeMassInFunction();
980 bool needIterativeInference()
const;
983 void applyIterativeInference();
985 using ProbMatrixType = std::vector<std::vector<std::pair<size_t, Scaled64>>>;
988 void iterativeInference(
const ProbMatrixType &ProbMatrix,
989 std::vector<Scaled64> &Freq)
const;
993 void findReachableBlocks(std::vector<const BlockT *> &
Blocks)
const;
997 void initTransitionProbabilities(
998 const std::vector<const BlockT *> &
Blocks,
1000 ProbMatrixType &ProbMatrix)
const;
1005 Scaled64 discrepancy(
const ProbMatrixType &ProbMatrix,
1006 const std::vector<Scaled64> &Freq)
const;
1014 void calculate(
const FunctionT &
F,
const BranchProbabilityInfoT &BPI,
1015 const LoopInfoT &LI);
1023 std::optional<uint64_t>
1025 bool AllowSynthetic =
false)
const {
1030 std::optional<uint64_t>
1032 bool AllowSynthetic =
false)
const {
1054 const BranchProbabilityInfoT &
getBPI()
const {
return *BPI; }
1074namespace bfi_detail {
1076template <
class BFIImplT>
1089 BFIImpl->forgetBlock(cast<BasicBlock>(getValPtr()));
1095template <
class BFIImplT>
1106 const BranchProbabilityInfoT &BPI,
1107 const LoopInfoT &LI) {
1120 <<
"\n================="
1121 << std::string(
F.getName().size(),
'=') <<
"\n");
1127 computeMassInLoops();
1128 computeMassInFunction();
1132 if (needIterativeInference())
1133 applyIterativeInference();
1140 for (
const BlockT &BB :
F)
1141 if (!Nodes.count(&BB))
1149 if (Nodes.count(BB))
1157 Freqs.emplace_back();
1163 const BlockT *Entry = &
F->front();
1164 RPOT.reserve(
F->size());
1165 std::copy(
po_begin(Entry),
po_end(Entry), std::back_inserter(RPOT));
1166 std::reverse(RPOT.begin(), RPOT.end());
1168 assert(RPOT.size() - 1 <= BlockNode::getMaxIndex() &&
1169 "More nodes in function than Block Frequency Info supports");
1172 for (rpot_iterator
I = rpot_begin(),
E = rpot_end();
I !=
E; ++
I) {
1173 BlockNode
Node = getNode(
I);
1176 Nodes[*
I] = {
Node, BFICallbackVH(*
I,
this)};
1179 Working.reserve(RPOT.size());
1181 Working.emplace_back(
Index);
1182 Freqs.resize(RPOT.size());
1185template <
class BT>
void BlockFrequencyInfoImpl<BT>::initializeLoops() {
1191 std::deque<std::pair<const LoopT *, LoopData *>> Q;
1192 for (
const LoopT *L : *LI)
1193 Q.emplace_back(L,
nullptr);
1194 while (!Q.empty()) {
1195 const LoopT *Loop = Q.front().first;
1196 LoopData *Parent = Q.front().second;
1199 BlockNode Header = getNode(Loop->getHeader());
1200 assert(Header.isValid());
1202 Loops.emplace_back(Parent, Header);
1203 Working[Header.Index].Loop = &
Loops.back();
1206 for (
const LoopT *L : *Loop)
1207 Q.emplace_back(L, &
Loops.back());
1214 if (Working[
Index].isLoopHeader()) {
1215 LoopData *ContainingLoop = Working[
Index].getContainingLoop();
1217 ContainingLoop->Nodes.push_back(
Index);
1221 const LoopT *Loop = LI->getLoopFor(RPOT[
Index]);
1226 BlockNode Header = getNode(Loop->getHeader());
1227 assert(Header.isValid());
1228 const auto &HeaderData = Working[Header.Index];
1229 assert(HeaderData.isLoopHeader());
1231 Working[
Index].Loop = HeaderData.Loop;
1232 HeaderData.Loop->Nodes.push_back(
Index);
1238template <
class BT>
void BlockFrequencyInfoImpl<BT>::computeMassInLoops() {
1240 for (
auto L =
Loops.rbegin(),
E =
Loops.rend(); L !=
E; ++L) {
1241 if (computeMassInLoop(*L))
1243 auto Next = std::next(L);
1244 computeIrreducibleMass(&*L,
L.base());
1245 L = std::prev(Next);
1246 if (computeMassInLoop(*L))
1253bool BlockFrequencyInfoImpl<BT>::computeMassInLoop(LoopData &Loop) {
1255 LLVM_DEBUG(
dbgs() <<
"compute-mass-in-loop: " << getLoopName(Loop) <<
"\n");
1257 if (Loop.isIrreducible()) {
1260 unsigned NumHeadersWithWeight = 0;
1261 std::optional<uint64_t> MinHeaderWeight;
1262 DenseSet<uint32_t> HeadersWithoutWeight;
1263 HeadersWithoutWeight.reserve(Loop.NumHeaders);
1265 auto &HeaderNode = Loop.Nodes[
H];
1266 const BlockT *
Block = getBlock(HeaderNode);
1267 IsIrrLoopHeader.set(Loop.Nodes[
H].Index);
1268 std::optional<uint64_t> HeaderWeight =
Block->getIrrLoopHeaderWeight();
1269 if (!HeaderWeight) {
1272 HeadersWithoutWeight.insert(
H);
1276 <<
" has irr loop header weight " << *HeaderWeight
1278 NumHeadersWithWeight++;
1279 uint64_t HeaderWeightValue = *HeaderWeight;
1280 if (!MinHeaderWeight || HeaderWeightValue < MinHeaderWeight)
1281 MinHeaderWeight = HeaderWeightValue;
1282 if (HeaderWeightValue) {
1283 Dist.addLocal(HeaderNode, HeaderWeightValue);
1292 if (!MinHeaderWeight)
1293 MinHeaderWeight = 1;
1294 for (
uint32_t H : HeadersWithoutWeight) {
1295 auto &HeaderNode = Loop.Nodes[
H];
1296 assert(!getBlock(HeaderNode)->getIrrLoopHeaderWeight() &&
1297 "Shouldn't have a weight metadata");
1298 uint64_t MinWeight = *MinHeaderWeight;
1302 Dist.addLocal(HeaderNode, MinWeight);
1304 distributeIrrLoopHeaderMass(Dist);
1305 for (
const BlockNode &M : Loop.Nodes)
1306 if (!propagateMassToSuccessors(&Loop, M))
1308 if (NumHeadersWithWeight == 0)
1310 adjustLoopHeaderMass(Loop);
1312 Working[Loop.getHeader().Index].getMass() = BlockMass::getFull();
1313 if (!propagateMassToSuccessors(&Loop, Loop.getHeader()))
1315 for (
const BlockNode &M : Loop.members())
1316 if (!propagateMassToSuccessors(&Loop, M))
1321 computeLoopScale(Loop);
1327bool BlockFrequencyInfoImpl<BT>::tryToComputeMassInFunction() {
1330 assert(!Working.empty() &&
"no blocks in function");
1331 assert(!Working[0].isLoopHeader() &&
"entry block is a loop header");
1333 Working[0].getMass() = BlockMass::getFull();
1334 for (rpot_iterator
I = rpot_begin(), IE = rpot_end();
I !=
IE; ++
I) {
1336 BlockNode
Node = getNode(
I);
1337 if (Working[
Node.Index].isPackaged())
1340 if (!propagateMassToSuccessors(
nullptr,
Node))
1346template <
class BT>
void BlockFrequencyInfoImpl<BT>::computeMassInFunction() {
1347 if (tryToComputeMassInFunction())
1349 computeIrreducibleMass(
nullptr,
Loops.begin());
1350 if (tryToComputeMassInFunction())
1356bool BlockFrequencyInfoImpl<BT>::needIterativeInference()
const {
1359 if (!
F->getFunction().hasProfileData())
1363 for (
auto L =
Loops.rbegin(),
E =
Loops.rend(); L !=
E; ++L) {
1364 if (
L->isIrreducible())
1370template <
class BT>
void BlockFrequencyInfoImpl<BT>::applyIterativeInference() {
1375 std::vector<const BlockT *> ReachableBlocks;
1376 findReachableBlocks(ReachableBlocks);
1377 if (ReachableBlocks.empty())
1382 DenseMap<const BlockT *, size_t> BlockIndex;
1384 auto Freq = std::vector<Scaled64>(ReachableBlocks.size());
1386 for (
size_t I = 0;
I < ReachableBlocks.size();
I++) {
1387 const BlockT *BB = ReachableBlocks[
I];
1389 Freq[
I] = getFloatingBlockFreq(BB);
1392 assert(!SumFreq.isZero() &&
"empty initial block frequencies");
1394 LLVM_DEBUG(
dbgs() <<
"Applying iterative inference for " <<
F->getName()
1395 <<
" with " << ReachableBlocks.size() <<
" blocks\n");
1398 for (
auto &Value : Freq) {
1404 ProbMatrixType ProbMatrix;
1405 initTransitionProbabilities(ReachableBlocks, BlockIndex, ProbMatrix);
1408 iterativeInference(ProbMatrix, Freq);
1411 for (
const BlockT &BB : *
F) {
1412 auto Node = getNode(&BB);
1413 if (!
Node.isValid())
1415 if (BlockIndex.count(&BB)) {
1416 Freqs[
Node.Index].Scaled = Freq[BlockIndex[&BB]];
1418 Freqs[
Node.Index].Scaled = Scaled64::getZero();
1424void BlockFrequencyInfoImpl<BT>::iterativeInference(
1425 const ProbMatrixType &ProbMatrix, std::vector<Scaled64> &Freq)
const {
1427 "incorrectly specified precision");
1429 const auto Precision =
1435 << discrepancy(ProbMatrix, Freq).
toString() <<
"\n");
1439 auto Successors = std::vector<std::vector<size_t>>(Freq.size());
1440 for (
size_t I = 0;
I < Freq.size();
I++) {
1441 for (
const auto &Jump : ProbMatrix[
I]) {
1442 Successors[Jump.first].push_back(
I);
1450 auto IsActive = BitVector(Freq.size(),
false);
1451 std::queue<size_t> ActiveSet;
1452 for (
size_t I = 0;
I < Freq.size();
I++) {
1461 while (It++ < MaxIterations && !ActiveSet.empty()) {
1462 size_t I = ActiveSet.front();
1464 IsActive[
I] =
false;
1470 Scaled64 OneMinusSelfProb = Scaled64::getOne();
1471 for (
const auto &Jump : ProbMatrix[
I]) {
1472 if (Jump.first ==
I) {
1473 OneMinusSelfProb -= Jump.second;
1475 NewFreq += Freq[Jump.first] * Jump.second;
1478 if (OneMinusSelfProb != Scaled64::getOne())
1479 NewFreq /= OneMinusSelfProb;
1483 auto Change = Freq[
I] >= NewFreq ? Freq[
I] - NewFreq : NewFreq - Freq[
I];
1484 if (Change > Precision) {
1487 for (
size_t Succ : Successors[
I]) {
1488 if (!IsActive[Succ]) {
1489 ActiveSet.push(Succ);
1490 IsActive[Succ] =
true;
1499 LLVM_DEBUG(
dbgs() <<
" Completed " << It <<
" inference iterations"
1500 <<
format(
" (%0.0f per block)",
double(It) / Freq.size())
1504 << discrepancy(ProbMatrix, Freq).
toString() <<
"\n");
1509void BlockFrequencyInfoImpl<BT>::findReachableBlocks(
1510 std::vector<const BlockT *> &
Blocks)
const {
1513 std::queue<const BlockT *>
Queue;
1514 SmallPtrSet<const BlockT *, 8> Reachable;
1515 const BlockT *Entry = &
F->front();
1517 Reachable.insert(Entry);
1518 while (!
Queue.empty()) {
1519 const BlockT *SrcBB =
Queue.front();
1521 for (
const BlockT *DstBB : children<const BlockT *>(SrcBB)) {
1522 auto EP = BPI->getEdgeProbability(SrcBB, DstBB);
1525 if (Reachable.insert(DstBB).second)
1532 SmallPtrSet<const BlockT *, 8> InverseReachable;
1533 for (
const BlockT &BB : *
F) {
1535 bool HasSucc = GraphTraits<const BlockT *>::child_begin(&BB) !=
1536 GraphTraits<const BlockT *>::child_end(&BB);
1537 if (!HasSucc && Reachable.count(&BB)) {
1539 InverseReachable.insert(&BB);
1542 while (!
Queue.empty()) {
1543 const BlockT *SrcBB =
Queue.front();
1545 for (
const BlockT *DstBB :
children<Inverse<const BlockT *>>(SrcBB)) {
1546 auto EP = BPI->getEdgeProbability(DstBB, SrcBB);
1549 if (InverseReachable.insert(DstBB).second)
1556 for (
const BlockT &BB : *
F) {
1557 if (Reachable.count(&BB) && InverseReachable.count(&BB)) {
1564void BlockFrequencyInfoImpl<BT>::initTransitionProbabilities(
1565 const std::vector<const BlockT *> &
Blocks,
1566 const DenseMap<const BlockT *, size_t> &BlockIndex,
1567 ProbMatrixType &ProbMatrix)
const {
1568 const size_t NumBlocks =
Blocks.size();
1569 auto Succs = std::vector<std::vector<std::pair<size_t, Scaled64>>>(NumBlocks);
1570 auto SumProb = std::vector<Scaled64>(NumBlocks);
1573 for (
size_t Src = 0; Src < NumBlocks; Src++) {
1574 const BlockT *BB =
Blocks[Src];
1575 SmallPtrSet<const BlockT *, 2> UniqueSuccs;
1576 for (
const auto SI : children<const BlockT *>(BB)) {
1578 if (!BlockIndex.contains(SI))
1581 if (!UniqueSuccs.insert(SI).second)
1584 auto EP = BPI->getEdgeProbability(BB, SI);
1589 Scaled64::getFraction(EP.getNumerator(), EP.getDenominator());
1590 size_t Dst = BlockIndex.find(SI)->second;
1591 Succs[Src].push_back(std::make_pair(Dst, EdgeProb));
1592 SumProb[Src] += EdgeProb;
1597 ProbMatrix = ProbMatrixType(NumBlocks);
1598 for (
size_t Src = 0; Src < NumBlocks; Src++) {
1600 if (Succs[Src].empty())
1603 assert(!SumProb[Src].
isZero() &&
"Zero sum probability of non-exit block");
1604 for (
auto &Jump : Succs[Src]) {
1605 size_t Dst = Jump.first;
1607 ProbMatrix[Dst].push_back(std::make_pair(Src, Prob / SumProb[Src]));
1612 size_t EntryIdx = BlockIndex.find(&
F->front())->second;
1613 for (
size_t Src = 0; Src < NumBlocks; Src++) {
1614 if (Succs[Src].empty()) {
1615 ProbMatrix[EntryIdx].push_back(std::make_pair(Src, Scaled64::getOne()));
1623 const ProbMatrixType &ProbMatrix,
const std::vector<Scaled64> &Freq)
const {
1624 assert(Freq[0] > 0 &&
"Incorrectly computed frequency of the entry block");
1626 for (
size_t I = 0;
I < ProbMatrix.size();
I++) {
1628 for (
const auto &Jump : ProbMatrix[
I]) {
1629 Sum += Freq[Jump.first] * Jump.second;
1631 Discrepancy += Freq[
I] >= Sum ? Freq[
I] - Sum : Sum - Freq[
I];
1634 return Discrepancy / Freq[0];
1639namespace bfi_detail {
1654 for (
const auto *Succ : children<const BlockT *>(BB))
1655 G.addEdge(Irr,
BFI.getNode(Succ), OuterLoop);
1662void BlockFrequencyInfoImpl<BT>::computeIrreducibleMass(
1663 LoopData *OuterLoop, std::list<LoopData>::iterator Insert) {
1665 if (OuterLoop)
dbgs()
1666 <<
"loop: " << getLoopName(*OuterLoop) <<
"\n";
1667 else dbgs() <<
"function\n");
1669 using namespace bfi_detail;
1673 BlockEdgesAdder<BT> addBlockEdges(*
this);
1674 IrreducibleGraph
G(*
this, OuterLoop, addBlockEdges);
1676 for (
auto &L : analyzeIrreducible(
G, OuterLoop, Insert))
1677 computeMassInLoop(L);
1681 updateLoopWithIrreducible(*OuterLoop);
1691BlockFrequencyInfoImpl<BT>::propagateMassToSuccessors(LoopData *OuterLoop,
1692 const BlockNode &
Node) {
1696 if (
auto *Loop = Working[
Node.Index].getPackagedLoop()) {
1697 assert(Loop != OuterLoop &&
"Cannot propagate mass in a packaged loop");
1698 if (!addLoopSuccessorsToDist(OuterLoop, *Loop, Dist))
1702 const BlockT *BB = getBlock(
Node);
1703 for (
auto SI = GraphTraits<const BlockT *>::child_begin(BB),
1704 SE = GraphTraits<const BlockT *>::child_end(BB);
1707 Dist, OuterLoop,
Node, getNode(*SI),
1715 distributeMass(
Node, OuterLoop, Dist);
1723 OS <<
"block-frequency-info: " <<
F->getName() <<
"\n";
1724 for (
const BlockT &BB : *
F) {
1726 getFloatingBlockFreq(&BB).print(
OS, 5)
1727 <<
", int = " << getBlockFreq(&BB).getFrequency();
1730 F->getFunction(), getNode(&BB)))
1732 if (std::optional<uint64_t> IrrLoopHeaderWeight =
1733 BB.getIrrLoopHeaderWeight())
1734 OS <<
", irr_loop_header_weight = " << *IrrLoopHeaderWeight;
1749 for (
auto &Entry : Nodes) {
1750 const BlockT *BB = Entry.first;
1752 ValidNodes[BB] = Entry.second.first;
1755 for (
auto &Entry :
Other.Nodes) {
1756 const BlockT *BB = Entry.first;
1758 OtherValidNodes[BB] = Entry.second.first;
1761 unsigned NumValidNodes = ValidNodes.
size();
1762 unsigned NumOtherValidNodes = OtherValidNodes.
size();
1763 if (NumValidNodes != NumOtherValidNodes) {
1765 dbgs() <<
"Number of blocks mismatch: " << NumValidNodes <<
" vs "
1766 << NumOtherValidNodes <<
"\n";
1768 for (
auto &Entry : ValidNodes) {
1769 const BlockT *BB = Entry.first;
1771 if (OtherValidNodes.
count(BB)) {
1772 BlockNode OtherNode = OtherValidNodes[BB];
1773 const auto &Freq = Freqs[
Node.Index];
1774 const auto &OtherFreq =
Other.Freqs[OtherNode.
Index];
1775 if (Freq.Integer != OtherFreq.Integer) {
1778 << Freq.Integer <<
" vs " << OtherFreq.Integer <<
"\n";
1783 <<
Node.Index <<
" does not exist in Other.\n";
1792 dbgs() <<
"Other\n";
1803template <
class BlockFrequencyInfoT,
class BranchProbabilityInfoT>
1816 return G->getFunction()->getName();
1820 unsigned HotPercentThreshold = 0) {
1822 if (!HotPercentThreshold)
1827 for (
NodeIter I = GTraits::nodes_begin(Graph),
1828 E = GTraits::nodes_end(Graph);
1832 std::max(
MaxFrequency, Graph->getBlockFreq(
N).getFrequency());
1844 OS <<
"color=\"red\"";
1850 GVDAGType GType,
int layout_order = -1) {
1854 if (layout_order != -1)
1855 OS <<
Node->getName() <<
"[" << layout_order <<
"] : ";
1857 OS <<
Node->getName() <<
" : ";
1863 OS << Graph->getBlockFreq(
Node).getFrequency();
1866 auto Count = Graph->getBlockProfileCount(
Node);
1875 "never reach this point.");
1881 const BlockFrequencyInfoT *BFI,
1882 const BranchProbabilityInfoT *BPI,
1883 unsigned HotPercentThreshold = 0) {
1895 if (HotPercentThreshold) {
1900 if (EFreq >= HotFreq) {
1901 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.
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)
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.
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
void printBlockFreqImpl(raw_ostream &OS, BlockFrequency EntryFreq, BlockFrequency Freq)
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
iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)
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)