summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/CodeGen')
-rw-r--r--llvm/lib/CodeGen/BranchFolding.cpp9
-rw-r--r--llvm/lib/CodeGen/IfConversion.cpp155
-rw-r--r--llvm/lib/CodeGen/MIRParser/MIParser.cpp3
-rw-r--r--llvm/lib/CodeGen/MIRPrinter.cpp4
-rw-r--r--llvm/lib/CodeGen/MachineBasicBlock.cpp142
-rw-r--r--llvm/lib/CodeGen/MachineBlockPlacement.cpp71
-rw-r--r--llvm/lib/CodeGen/MachineBranchProbabilityInfo.cpp82
-rw-r--r--llvm/lib/CodeGen/TailDuplication.cpp6
8 files changed, 301 insertions, 171 deletions
diff --git a/llvm/lib/CodeGen/BranchFolding.cpp b/llvm/lib/CodeGen/BranchFolding.cpp
index ba21d9cc9d5..0b2495cc996 100644
--- a/llvm/lib/CodeGen/BranchFolding.cpp
+++ b/llvm/lib/CodeGen/BranchFolding.cpp
@@ -1099,16 +1099,13 @@ void BranchFolder::setCommonTailEdgeWeights(MachineBasicBlock &TailMBB) {
if (TailMBB.succ_size() <= 1)
return;
- auto SumEdgeFreq =
- std::accumulate(EdgeFreqLs.begin(), EdgeFreqLs.end(), BlockFrequency(0))
- .getFrequency();
+ auto MaxEdgeFreq = *std::max_element(EdgeFreqLs.begin(), EdgeFreqLs.end());
+ uint64_t Scale = MaxEdgeFreq.getFrequency() / UINT32_MAX + 1;
auto EdgeFreq = EdgeFreqLs.begin();
for (auto SuccI = TailMBB.succ_begin(), SuccE = TailMBB.succ_end();
SuccI != SuccE; ++SuccI, ++EdgeFreq)
- TailMBB.setSuccProbability(
- SuccI, BranchProbability::getBranchProbability(EdgeFreq->getFrequency(),
- SumEdgeFreq));
+ TailMBB.setSuccWeight(SuccI, EdgeFreq->getFrequency() / Scale);
}
//===----------------------------------------------------------------------===//
diff --git a/llvm/lib/CodeGen/IfConversion.cpp b/llvm/lib/CodeGen/IfConversion.cpp
index ff28f95cc33..0b2f3ea165f 100644
--- a/llvm/lib/CodeGen/IfConversion.cpp
+++ b/llvm/lib/CodeGen/IfConversion.cpp
@@ -32,7 +32,6 @@
#include "llvm/Target/TargetLowering.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Target/TargetSubtargetInfo.h"
-#include <algorithm>
using namespace llvm;
@@ -1152,6 +1151,28 @@ bool IfConverter::IfConvertSimple(BBInfo &BBI, IfcvtKind Kind) {
return true;
}
+/// Scale down weights to fit into uint32_t. NewTrue is the new weight
+/// for successor TrueBB, and NewFalse is the new weight for successor
+/// FalseBB.
+static void ScaleWeights(uint64_t NewTrue, uint64_t NewFalse,
+ MachineBasicBlock *MBB,
+ const MachineBasicBlock *TrueBB,
+ const MachineBasicBlock *FalseBB,
+ const MachineBranchProbabilityInfo *MBPI) {
+ uint64_t NewMax = (NewTrue > NewFalse) ? NewTrue : NewFalse;
+ uint32_t Scale = (NewMax / UINT32_MAX) + 1;
+ for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
+ SE = MBB->succ_end();
+ SI != SE; ++SI) {
+ if (*SI == TrueBB)
+ MBB->setSuccWeight(SI, (uint32_t)(NewTrue / Scale));
+ else if (*SI == FalseBB)
+ MBB->setSuccWeight(SI, (uint32_t)(NewFalse / Scale));
+ else
+ MBB->setSuccWeight(SI, MBPI->getEdgeWeight(MBB, SI) / Scale);
+ }
+}
+
/// IfConvertTriangle - If convert a triangle sub-CFG.
///
bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) {
@@ -1208,14 +1229,16 @@ bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) {
DontKill.clear();
bool HasEarlyExit = CvtBBI->FalseBB != nullptr;
- BranchProbability CvtNext, CvtFalse, BBNext, BBCvt;
+ uint64_t CvtNext = 0, CvtFalse = 0, BBNext = 0, BBCvt = 0, SumWeight = 0;
+ uint32_t WeightScale = 0;
if (HasEarlyExit) {
- // Get probabilities before modifying CvtBBI->BB and BBI.BB.
- CvtNext = MBPI->getEdgeProbability(CvtBBI->BB, NextBBI->BB);
- CvtFalse = MBPI->getEdgeProbability(CvtBBI->BB, CvtBBI->FalseBB);
- BBNext = MBPI->getEdgeProbability(BBI.BB, NextBBI->BB);
- BBCvt = MBPI->getEdgeProbability(BBI.BB, CvtBBI->BB);
+ // Get weights before modifying CvtBBI->BB and BBI.BB.
+ CvtNext = MBPI->getEdgeWeight(CvtBBI->BB, NextBBI->BB);
+ CvtFalse = MBPI->getEdgeWeight(CvtBBI->BB, CvtBBI->FalseBB);
+ BBNext = MBPI->getEdgeWeight(BBI.BB, NextBBI->BB);
+ BBCvt = MBPI->getEdgeWeight(BBI.BB, CvtBBI->BB);
+ SumWeight = MBPI->getSumForBlock(CvtBBI->BB, WeightScale);
}
if (CvtBBI->BB->pred_size() > 1) {
@@ -1243,24 +1266,22 @@ bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) {
CvtBBI->BrCond.end());
if (TII->ReverseBranchCondition(RevCond))
llvm_unreachable("Unable to reverse branch condition!");
-
- // Update the edge probability for both CvtBBI->FalseBB and NextBBI.
- // NewNext = New_Prob(BBI.BB, NextBBI->BB) =
- // Prob(BBI.BB, NextBBI->BB) +
- // Prob(BBI.BB, CvtBBI->BB) * Prob(CvtBBI->BB, NextBBI->BB)
- // NewFalse = New_Prob(BBI.BB, CvtBBI->FalseBB) =
- // Prob(BBI.BB, CvtBBI->BB) * Prob(CvtBBI->BB, CvtBBI->FalseBB)
- auto NewTrueBB = getNextBlock(BBI.BB);
- auto NewNext = BBNext + BBCvt * CvtNext;
- auto NewTrueBBIter =
- std::find(BBI.BB->succ_begin(), BBI.BB->succ_end(), NewTrueBB);
- assert(NewTrueBBIter != BBI.BB->succ_end() &&
- "NewTrueBB is not a successor of BBI.BB.");
- BBI.BB->setSuccProbability(NewTrueBBIter, NewNext);
-
- auto NewFalse = BBCvt * CvtFalse;
TII->InsertBranch(*BBI.BB, CvtBBI->FalseBB, nullptr, RevCond, dl);
- BBI.BB->addSuccessor(CvtBBI->FalseBB, NewFalse);
+ BBI.BB->addSuccessor(CvtBBI->FalseBB);
+ // Update the edge weight for both CvtBBI->FalseBB and NextBBI.
+ // New_Weight(BBI.BB, NextBBI->BB) =
+ // Weight(BBI.BB, NextBBI->BB) * getSumForBlock(CvtBBI->BB) +
+ // Weight(BBI.BB, CvtBBI->BB) * Weight(CvtBBI->BB, NextBBI->BB)
+ // New_Weight(BBI.BB, CvtBBI->FalseBB) =
+ // Weight(BBI.BB, CvtBBI->BB) * Weight(CvtBBI->BB, CvtBBI->FalseBB)
+
+ uint64_t NewNext = BBNext * SumWeight + (BBCvt * CvtNext) / WeightScale;
+ uint64_t NewFalse = (BBCvt * CvtFalse) / WeightScale;
+ // We need to scale down all weights of BBI.BB to fit uint32_t.
+ // Here BBI.BB is connected to CvtBBI->FalseBB and will fall through to
+ // the next block.
+ ScaleWeights(NewNext, NewFalse, BBI.BB, getNextBlock(BBI.BB),
+ CvtBBI->FalseBB, MBPI);
}
// Merge in the 'false' block if the 'false' block has no other
@@ -1503,7 +1524,7 @@ bool IfConverter::IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind,
MergeBlocks(BBI, TailBBI);
TailBBI.IsDone = true;
} else {
- BBI.BB->addSuccessor(TailBB, BranchProbability::getOne());
+ BBI.BB->addSuccessor(TailBB);
InsertUncondBranch(BBI.BB, TailBB, TII);
BBI.HasFallThrough = false;
}
@@ -1667,26 +1688,21 @@ void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI, bool AddEdges) {
FromBBI.BB->succ_end());
MachineBasicBlock *NBB = getNextBlock(FromBBI.BB);
MachineBasicBlock *FallThrough = FromBBI.HasFallThrough ? NBB : nullptr;
- // The edge probability from ToBBI.BB to FromBBI.BB, which is only needed when
- // AddEdges is true and FromBBI.BB is a successor of ToBBI.BB.
- auto To2FromProb = BranchProbability::getZero();
- if (AddEdges && ToBBI.BB->isSuccessor(FromBBI.BB)) {
- To2FromProb = MBPI->getEdgeProbability(ToBBI.BB, FromBBI.BB);
- // Set the edge probability from ToBBI.BB to FromBBI.BB to zero to avoid the
- // edge probability being merged to other edges when this edge is removed
- // later.
- ToBBI.BB->setSuccProbability(
- std::find(ToBBI.BB->succ_begin(), ToBBI.BB->succ_end(), FromBBI.BB),
- BranchProbability::getZero());
- }
+ // The edge weight from ToBBI.BB to FromBBI.BB, which is only needed when
+ // AddEdges is true and FromBBI.BB is a successor of ToBBI.BB.
+ uint32_t To2FromWeight = 0;
+ // WeightScale and SumWeight are for calculating successor probabilities of
+ // FromBBI.BB.
+ uint32_t WeightScale = 0;
+ uint32_t SumWeight = 0;
if (AddEdges && ToBBI.BB->isSuccessor(FromBBI.BB)) {
- // Set the edge probability from ToBBI.BB to FromBBI.BB to zero to avoid the
- // edge probability being merged to other edges when this edge is removed
- // later.
- ToBBI.BB->setSuccProbability(
- std::find(ToBBI.BB->succ_begin(), ToBBI.BB->succ_end(), FromBBI.BB),
- BranchProbability::getZero());
+ To2FromWeight = MBPI->getEdgeWeight(ToBBI.BB, FromBBI.BB);
+ // Set the edge weight from ToBBI.BB to FromBBI.BB to zero to avoid the edge
+ // weight being merged to other edges when this edge is removed later.
+ ToBBI.BB->setSuccWeight(
+ std::find(ToBBI.BB->succ_begin(), ToBBI.BB->succ_end(), FromBBI.BB), 0);
+ SumWeight = MBPI->getSumForBlock(FromBBI.BB, WeightScale);
}
for (unsigned i = 0, e = FromSuccs.size(); i != e; ++i) {
@@ -1695,38 +1711,39 @@ void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI, bool AddEdges) {
if (Succ == FallThrough)
continue;
- auto NewProb = BranchProbability::getZero();
+ uint32_t NewWeight = 0;
if (AddEdges) {
- // Calculate the edge probability for the edge from ToBBI.BB to Succ,
- // which is a portion of the edge probability from FromBBI.BB to Succ. The
- // portion ratio is the edge probability from ToBBI.BB to FromBBI.BB (if
- // FromBBI is a successor of ToBBI.BB. See comment below for excepion).
- NewProb = MBPI->getEdgeProbability(FromBBI.BB, Succ);
+ // Calculate the edge weight for the edge from ToBBI.BB to Succ, which is
+ // a portion of the edge weight from FromBBI.BB to Succ. The portion ratio
+ // is the edge probability from ToBBI.BB to FromBBI.BB (if FromBBI is a
+ // successor of ToBBI.BB. See comment below for excepion).
+ NewWeight = MBPI->getEdgeWeight(FromBBI.BB, Succ);
- // To2FromProb is 0 when FromBBI.BB is not a successor of ToBBI.BB. This
+ // To2FromWeight is 0 when FromBBI.BB is not a successor of ToBBI.BB. This
// only happens when if-converting a diamond CFG and FromBBI.BB is the
// tail BB. In this case FromBBI.BB post-dominates ToBBI.BB and hence we
- // could just use the probabilities on FromBBI.BB's out-edges when adding
- // new successors.
- if (!To2FromProb.isZero())
- NewProb *= To2FromProb;
+ // could just use the weights on FromBBI.BB's out-edges when adding new
+ // successors.
+ if (To2FromWeight > 0) {
+ BranchProbability Prob(NewWeight / WeightScale, SumWeight);
+ NewWeight = Prob.scale(To2FromWeight);
+ }
}
FromBBI.BB->removeSuccessor(Succ);
if (AddEdges) {
- // If the edge from ToBBI.BB to Succ already exists, update the
- // probability of this edge by adding NewWeight to it. An example is shown
- // below, in which A is ToBBI.BB and B is FromBBI.BB. In this case we
- // don't have to set C as A's successor as it already is. We only need to
- // update the edge probability on A->C. Note that B will not be
- // immediately removed from A's successors. It is possible that B->D is
- // not removed either if D is a fallthrough of B. Later the edge A->D
- // (generated here) and B->D will be combined into one edge. To maintain
- // correct edge probability of this combined edge, we need to set the edge
- // probability of A->B to zero, which is already done above. The edge
- // probability on A->D is calculated by scaling the original probability
- // on A->B by the probability of B->D.
+ // If the edge from ToBBI.BB to Succ already exists, update the weight of
+ // this edge by adding NewWeight to it. An example is shown below, in
+ // which A is ToBBI.BB and B is FromBBI.BB. In this case we don't have to
+ // set C as A's successor as it already is. We only need to update the
+ // edge weight on A->C. Note that B will not be immediately removed from
+ // A's successors. It is possible that B->D is not removed either if D is
+ // a fallthrough of B. Later the edge A->D (generated here) and B->D will
+ // be combined into one edge. To maintain correct edge weight of this
+ // combined edge, we need to set the edge weight of A->B to zero, which is
+ // already done above. The edge weight on A->D is calculated by scaling
+ // the original weight on A->B by the probability of B->D.
//
// Before ifcvt: After ifcvt (assume B->D is kept):
//
@@ -1738,11 +1755,11 @@ void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI, bool AddEdges) {
// C D C D
//
if (ToBBI.BB->isSuccessor(Succ))
- ToBBI.BB->setSuccProbability(
+ ToBBI.BB->setSuccWeight(
std::find(ToBBI.BB->succ_begin(), ToBBI.BB->succ_end(), Succ),
- MBPI->getEdgeProbability(ToBBI.BB, Succ) + NewProb);
+ MBPI->getEdgeWeight(ToBBI.BB, Succ) + NewWeight);
else
- ToBBI.BB->addSuccessor(Succ, NewProb);
+ ToBBI.BB->addSuccessor(Succ, NewWeight);
}
}
diff --git a/llvm/lib/CodeGen/MIRParser/MIParser.cpp b/llvm/lib/CodeGen/MIRParser/MIParser.cpp
index c9c2d62cec3..5a8e96df760 100644
--- a/llvm/lib/CodeGen/MIRParser/MIParser.cpp
+++ b/llvm/lib/CodeGen/MIRParser/MIParser.cpp
@@ -459,9 +459,8 @@ bool MIParser::parseBasicBlockSuccessors(MachineBasicBlock &MBB) {
if (expectAndConsume(MIToken::rparen))
return true;
}
- MBB.addSuccessor(SuccMBB, BranchProbability::getRaw(Weight));
+ MBB.addSuccessor(SuccMBB, Weight);
} while (consumeIfPresent(MIToken::comma));
- MBB.normalizeSuccProbs();
return false;
}
diff --git a/llvm/lib/CodeGen/MIRPrinter.cpp b/llvm/lib/CodeGen/MIRPrinter.cpp
index 175cb0d5143..0be7807064f 100644
--- a/llvm/lib/CodeGen/MIRPrinter.cpp
+++ b/llvm/lib/CodeGen/MIRPrinter.cpp
@@ -461,8 +461,8 @@ void MIPrinter::print(const MachineBasicBlock &MBB) {
if (I != MBB.succ_begin())
OS << ", ";
printMBBReference(**I);
- if (MBB.hasSuccessorProbabilities())
- OS << '(' << MBB.getSuccProbability(I) << ')';
+ if (MBB.hasSuccessorWeights())
+ OS << '(' << MBB.getSuccWeight(I) << ')';
}
OS << "\n";
HasLineAttributes = true;
diff --git a/llvm/lib/CodeGen/MachineBasicBlock.cpp b/llvm/lib/CodeGen/MachineBasicBlock.cpp
index c9c6a9d6246..602b75182fc 100644
--- a/llvm/lib/CodeGen/MachineBasicBlock.cpp
+++ b/llvm/lib/CodeGen/MachineBasicBlock.cpp
@@ -319,8 +319,8 @@ void MachineBasicBlock::print(raw_ostream &OS, ModuleSlotTracker &MST,
OS << " Successors according to CFG:";
for (const_succ_iterator SI = succ_begin(), E = succ_end(); SI != E; ++SI) {
OS << " BB#" << (*SI)->getNumber();
- if (!Probs.empty())
- OS << '(' << *getProbabilityIterator(SI) << ')';
+ if (!Weights.empty())
+ OS << '(' << *getWeightIterator(SI) << ')';
}
OS << '\n';
}
@@ -506,16 +506,34 @@ void MachineBasicBlock::updateTerminator() {
}
}
+void MachineBasicBlock::addSuccessor(MachineBasicBlock *Succ, uint32_t Weight) {
+ // Weight list is either empty (if successor list isn't empty, this means
+ // disabled optimization) or has the same size as successor list.
+ if (!(Weights.empty() && !Successors.empty()))
+ Weights.push_back(Weight);
+ Successors.push_back(Succ);
+ Succ->addPredecessor(this);
+}
+
+void MachineBasicBlock::addSuccessorWithoutWeight(MachineBasicBlock *Succ) {
+ // We need to make sure weight list is either empty or has the same size of
+ // successor list. When this function is called, we can safely delete all
+ // weight in the list.
+ Weights.clear();
+ Successors.push_back(Succ);
+ Succ->addPredecessor(this);
+}
+
void MachineBasicBlock::addSuccessor(MachineBasicBlock *Succ,
BranchProbability Prob) {
// Probability list is either empty (if successor list isn't empty, this means
// disabled optimization) or has the same size as successor list.
if (!(Probs.empty() && !Successors.empty())) {
- assert((Probs.empty() || (Prob.isUnknown() && Probs.back().isUnknown()) ||
- (!Prob.isUnknown() && !Probs.back().isUnknown())) &&
- "Successors with both known and unknwon probabilities are not "
- "allowed.");
Probs.push_back(Prob);
+ // FIXME: Temporarily use the numerator of the probability to represent edge
+ // weight. This will be removed once all weight-version interfaces in MBB
+ // are replaced with probability-version interfaces.
+ Weights.push_back(Prob.getNumerator());
}
Successors.push_back(Succ);
Succ->addPredecessor(this);
@@ -526,6 +544,7 @@ void MachineBasicBlock::addSuccessorWithoutProb(MachineBasicBlock *Succ) {
// of successor list. When this function is called, we can safely delete all
// probability in the list.
Probs.clear();
+ Weights.clear();
Successors.push_back(Succ);
Succ->addPredecessor(this);
}
@@ -539,12 +558,23 @@ MachineBasicBlock::succ_iterator
MachineBasicBlock::removeSuccessor(succ_iterator I) {
assert(I != Successors.end() && "Not a current successor!");
+ // If Weight list is empty it means we don't use it (disabled optimization).
+ if (!Weights.empty()) {
+ weight_iterator WI = getWeightIterator(I);
+ Weights.erase(WI);
+ }
+
+ // FIXME: Temporarily comment the following code as probabilities are now only
+ // used during instruction lowering, but this interface is called in later
+ // passes. Uncomment it once all edge weights are replaced with probabilities.
+#if 0
// If probability list is empty it means we don't use it (disabled
// optimization).
if (!Probs.empty()) {
probability_iterator WI = getProbabilityIterator(I);
Probs.erase(WI);
}
+#endif
(*I)->removePredecessor(this);
return Successors.erase(I);
@@ -581,12 +611,17 @@ void MachineBasicBlock::replaceSuccessor(MachineBasicBlock *Old,
}
// New is already a successor.
+ // Update its weight instead of adding a duplicate edge.
+ if (!Weights.empty())
+ *getWeightIterator(NewI) += *getWeightIterator(OldI);
+ // FIXME: Temporarily comment the following code as probabilities are now only
+ // used during instruction lowering, but this interface is called in later
+ // passes. Uncomment it once all edge weights are replaced with probabilities.
+#if 0
// Update its probability instead of adding a duplicate edge.
- if (!Probs.empty()) {
- auto ProbIter = getProbabilityIterator(NewI);
- if (!ProbIter->isUnknown())
- *ProbIter += *getProbabilityIterator(OldI);
- }
+ if (!Probs.empty())
+ *getProbabilityIterator(NewI) += *getProbabilityIterator(OldI);
+#endif
removeSuccessor(OldI);
}
@@ -606,14 +641,13 @@ void MachineBasicBlock::transferSuccessors(MachineBasicBlock *FromMBB) {
while (!FromMBB->succ_empty()) {
MachineBasicBlock *Succ = *FromMBB->succ_begin();
+ uint32_t Weight = 0;
- // If probability list is empty it means we don't use it (disabled optimization).
- if (!FromMBB->Probs.empty()) {
- auto Prob = *FromMBB->Probs.begin();
- addSuccessor(Succ, Prob);
- } else
- addSuccessorWithoutProb(Succ);
+ // If Weight list is empty it means we don't use it (disabled optimization).
+ if (!FromMBB->Weights.empty())
+ Weight = *FromMBB->Weights.begin();
+ addSuccessor(Succ, Weight);
FromMBB->removeSuccessor(Succ);
}
}
@@ -625,11 +659,10 @@ MachineBasicBlock::transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB) {
while (!FromMBB->succ_empty()) {
MachineBasicBlock *Succ = *FromMBB->succ_begin();
- if (!FromMBB->Probs.empty()) {
- auto Prob = *FromMBB->Probs.begin();
- addSuccessor(Succ, Prob);
- } else
- addSuccessorWithoutProb(Succ);
+ uint32_t Weight = 0;
+ if (!FromMBB->Weights.empty())
+ Weight = *FromMBB->Weights.begin();
+ addSuccessor(Succ, Weight);
FromMBB->removeSuccessor(Succ);
// Fix up any PHI nodes in the successor.
@@ -1113,32 +1146,65 @@ MachineBasicBlock::findDebugLoc(instr_iterator MBBI) {
return DL;
}
-/// Return probability of the edge from this block to MBB.
+/// Return weight of the edge from this block to MBB.
+uint32_t MachineBasicBlock::getSuccWeight(const_succ_iterator Succ) const {
+ if (Weights.empty())
+ return 0;
+
+ return *getWeightIterator(Succ);
+}
+
+/// Return probability of the edge from this block to MBB. If probability list
+/// is empty, return a default probability which is 1/N, where N is the number
+/// of successors. If the probability of the given successor is unknown, then
+/// sum up all known probabilities and return the complement of the sum divided
+/// by the number of unknown probabilities.
BranchProbability
MachineBasicBlock::getSuccProbability(const_succ_iterator Succ) const {
- if (Probs.empty() || Probs.back().isUnknown())
+ if (Probs.empty())
return BranchProbability(1, succ_size());
- return *getProbabilityIterator(Succ);
+ auto Prob = *getProbabilityIterator(Succ);
+ assert(!Prob.isUnknown());
+ return Prob;
+}
+
+/// Set successor weight of a given iterator.
+void MachineBasicBlock::setSuccWeight(succ_iterator I, uint32_t Weight) {
+ if (Weights.empty())
+ return;
+ *getWeightIterator(I) = Weight;
}
/// Set successor probability of a given iterator.
void MachineBasicBlock::setSuccProbability(succ_iterator I,
BranchProbability Prob) {
assert(!Prob.isUnknown());
- if (Probs.empty())
+ if (Probs.empty() || Weights.empty())
return;
*getProbabilityIterator(I) = Prob;
+ // FIXME: Temporarily use the numerator of the probability to represent edge
+ // weight. This will be removed once all weight-version interfaces in MBB
+ // are replaces with probability-version interfaces.
+ *getWeightIterator(I) = Prob.getNumerator();
}
-/// Return probability iterator corresonding to the I successor iterator
-MachineBasicBlock::const_probability_iterator
-MachineBasicBlock::getProbabilityIterator(
- MachineBasicBlock::const_succ_iterator I) const {
- assert(Probs.size() == Successors.size() && "Async probability list!");
+/// Return wight iterator corresonding to the I successor iterator.
+MachineBasicBlock::weight_iterator MachineBasicBlock::
+getWeightIterator(MachineBasicBlock::succ_iterator I) {
+ assert(Weights.size() == Successors.size() && "Async weight list!");
+ size_t index = std::distance(Successors.begin(), I);
+ assert(index < Weights.size() && "Not a current successor!");
+ return Weights.begin() + index;
+}
+
+/// Return wight iterator corresonding to the I successor iterator.
+MachineBasicBlock::const_weight_iterator MachineBasicBlock::
+getWeightIterator(MachineBasicBlock::const_succ_iterator I) const {
+ assert(Weights.size() == Successors.size() && "Async weight list!");
const size_t index = std::distance(Successors.begin(), I);
- assert(index < Probs.size() && "Not a current successor!");
- return Probs.begin() + index;
+ assert(index < Weights.size() && "Not a current successor!");
+ return Weights.begin() + index;
}
/// Return probability iterator corresonding to the I successor iterator.
@@ -1150,6 +1216,16 @@ MachineBasicBlock::getProbabilityIterator(MachineBasicBlock::succ_iterator I) {
return Probs.begin() + index;
}
+/// Return probability iterator corresonding to the I successor iterator
+MachineBasicBlock::const_probability_iterator
+MachineBasicBlock::getProbabilityIterator(
+ MachineBasicBlock::const_succ_iterator I) const {
+ assert(Probs.size() == Successors.size() && "Async probability list!");
+ const size_t index = std::distance(Successors.begin(), I);
+ assert(index < Probs.size() && "Not a current successor!");
+ return Probs.begin() + index;
+}
+
/// Return whether (physical) register "Reg" has been <def>ined and not <kill>ed
/// as of just before "MI".
///
diff --git a/llvm/lib/CodeGen/MachineBlockPlacement.cpp b/llvm/lib/CodeGen/MachineBlockPlacement.cpp
index fcddf346cf6..fba33eb93d5 100644
--- a/llvm/lib/CodeGen/MachineBlockPlacement.cpp
+++ b/llvm/lib/CodeGen/MachineBlockPlacement.cpp
@@ -380,11 +380,19 @@ MachineBlockPlacement::selectBestSuccessor(MachineBasicBlock *BB,
const BranchProbability HotProb(4, 5); // 80%
MachineBasicBlock *BestSucc = nullptr;
- auto BestProb = BranchProbability::getZero();
-
- // Adjust edge probabilities by excluding edges pointing to blocks that is
- // either not in BlockFilter or is already in the current chain. Consider the
- // following CFG:
+ // FIXME: Due to the performance of the probability and weight routines in
+ // the MBPI analysis, we manually compute probabilities using the edge
+ // weights. This is suboptimal as it means that the somewhat subtle
+ // definition of edge weight semantics is encoded here as well. We should
+ // improve the MBPI interface to efficiently support query patterns such as
+ // this.
+ uint32_t BestWeight = 0;
+ uint32_t WeightScale = 0;
+ uint32_t SumWeight = MBPI->getSumForBlock(BB, WeightScale);
+
+ // Adjust sum of weights by excluding weights on edges pointing to blocks that
+ // is either not in BlockFilter or is already in the current chain. Consider
+ // the following CFG:
//
// --->A
// | / \
@@ -398,7 +406,7 @@ MachineBlockPlacement::selectBestSuccessor(MachineBasicBlock *BB,
// HotProb). If we exclude E that is not in BlockFilter when calculating the
// probability of C->D, D will be selected and we will get A C D B as the
// layout of this loop.
- auto AdjustedSumProb = BranchProbability::getOne();
+ uint32_t AdjustedSumWeight = SumWeight;
SmallVector<MachineBasicBlock *, 4> Successors;
for (MachineBasicBlock *Succ : BB->successors()) {
bool SkipSucc = false;
@@ -416,20 +424,15 @@ MachineBlockPlacement::selectBestSuccessor(MachineBasicBlock *BB,
}
}
if (SkipSucc)
- AdjustedSumProb -= MBPI->getEdgeProbability(BB, Succ);
+ AdjustedSumWeight -= MBPI->getEdgeWeight(BB, Succ) / WeightScale;
else
Successors.push_back(Succ);
}
DEBUG(dbgs() << "Attempting merge from: " << getBlockName(BB) << "\n");
for (MachineBasicBlock *Succ : Successors) {
- BranchProbability SuccProb;
- uint32_t SuccProbN = MBPI->getEdgeProbability(BB, Succ).getNumerator();
- uint32_t SuccProbD = AdjustedSumProb.getNumerator();
- if (SuccProbN >= SuccProbD)
- SuccProb = BranchProbability::getOne();
- else
- SuccProb = BranchProbability(SuccProbN, SuccProbD);
+ uint32_t SuccWeight = MBPI->getEdgeWeight(BB, Succ);
+ BranchProbability SuccProb(SuccWeight / WeightScale, AdjustedSumWeight);
// If we outline optional branches, look whether Succ is unavoidable, i.e.
// dominates all terminators of the MachineFunction. If it does, other
@@ -467,7 +470,7 @@ MachineBlockPlacement::selectBestSuccessor(MachineBasicBlock *BB,
// Make sure that a hot successor doesn't have a globally more
// important predecessor.
- auto RealSuccProb = MBPI->getEdgeProbability(BB, Succ);
+ BranchProbability RealSuccProb(SuccWeight / WeightScale, SumWeight);
BlockFrequency CandidateEdgeFreq =
MBFI->getBlockFreq(BB) * RealSuccProb * HotProb.getCompl();
bool BadCFGConflict = false;
@@ -493,10 +496,10 @@ MachineBlockPlacement::selectBestSuccessor(MachineBasicBlock *BB,
<< " (prob)"
<< (SuccChain.LoopPredecessors != 0 ? " (CFG break)" : "")
<< "\n");
- if (BestSucc && BestProb >= SuccProb)
+ if (BestSucc && BestWeight >= SuccWeight)
continue;
BestSucc = Succ;
- BestProb = SuccProb;
+ BestWeight = SuccWeight;
}
return BestSucc;
}
@@ -725,6 +728,11 @@ MachineBlockPlacement::findBestLoopExit(MachineFunction &F, MachineLoop &L,
MachineBasicBlock *OldExitingBB = ExitingBB;
BlockFrequency OldBestExitEdgeFreq = BestExitEdgeFreq;
bool HasLoopingSucc = false;
+ // FIXME: Due to the performance of the probability and weight routines in
+ // the MBPI analysis, we use the internal weights and manually compute the
+ // probabilities to avoid quadratic behavior.
+ uint32_t WeightScale = 0;
+ uint32_t SumWeight = MBPI->getSumForBlock(MBB, WeightScale);
for (MachineBasicBlock *Succ : MBB->successors()) {
if (Succ->isEHPad())
continue;
@@ -738,10 +746,10 @@ MachineBlockPlacement::findBestLoopExit(MachineFunction &F, MachineLoop &L,
continue;
}
- auto SuccProb = MBPI->getEdgeProbability(MBB, Succ);
+ uint32_t SuccWeight = MBPI->getEdgeWeight(MBB, Succ);
if (LoopBlockSet.count(Succ)) {
DEBUG(dbgs() << " looping: " << getBlockName(MBB) << " -> "
- << getBlockName(Succ) << " (" << SuccProb << ")\n");
+ << getBlockName(Succ) << " (" << SuccWeight << ")\n");
HasLoopingSucc = true;
continue;
}
@@ -753,6 +761,7 @@ MachineBlockPlacement::findBestLoopExit(MachineFunction &F, MachineLoop &L,
BlocksExitingToOuterLoop.insert(MBB);
}
+ BranchProbability SuccProb(SuccWeight / WeightScale, SumWeight);
BlockFrequency ExitEdgeFreq = MBFI->getBlockFreq(MBB) * SuccProb;
DEBUG(dbgs() << " exiting: " << getBlockName(MBB) << " -> "
<< getBlockName(Succ) << " [L:" << SuccLoopDepth << "] (";
@@ -895,17 +904,21 @@ void MachineBlockPlacement::rotateLoopWithProfile(
// edge from the tail of the loop chain.
SmallVector<std::pair<MachineBasicBlock *, BlockFrequency>, 4> ExitsWithFreq;
for (auto BB : LoopChain) {
- auto LargestExitEdgeProb = BranchProbability::getZero();
+ uint32_t LargestExitEdgeWeight = 0;
for (auto *Succ : BB->successors()) {
BlockChain *SuccChain = BlockToChain[Succ];
if (!LoopBlockSet.count(Succ) &&
(!SuccChain || Succ == *SuccChain->begin())) {
- auto SuccProb = MBPI->getEdgeProbability(BB, Succ);
- LargestExitEdgeProb = std::max(LargestExitEdgeProb, SuccProb);
+ uint32_t SuccWeight = MBPI->getEdgeWeight(BB, Succ);
+ LargestExitEdgeWeight = std::max(LargestExitEdgeWeight, SuccWeight);
}
}
- if (LargestExitEdgeProb > BranchProbability::getZero()) {
- auto ExitFreq = MBFI->getBlockFreq(BB) * LargestExitEdgeProb;
+ if (LargestExitEdgeWeight > 0) {
+ uint32_t WeightScale = 0;
+ uint32_t SumWeight = MBPI->getSumForBlock(BB, WeightScale);
+ auto ExitFreq =
+ MBFI->getBlockFreq(BB) *
+ BranchProbability(LargestExitEdgeWeight / WeightScale, SumWeight);
ExitsWithFreq.emplace_back(BB, ExitFreq);
}
}
@@ -1277,16 +1290,14 @@ void MachineBlockPlacement::buildCFGChains(MachineFunction &F) {
}
// If PrevBB has a two-way branch, try to re-order the branches
- // such that we branch to the successor with higher probability first.
+ // such that we branch to the successor with higher weight first.
if (TBB && !Cond.empty() && FBB &&
- MBPI->getEdgeProbability(PrevBB, FBB) >
- MBPI->getEdgeProbability(PrevBB, TBB) &&
+ MBPI->getEdgeWeight(PrevBB, FBB) > MBPI->getEdgeWeight(PrevBB, TBB) &&
!TII->ReverseBranchCondition(Cond)) {
DEBUG(dbgs() << "Reverse order of the two branches: "
<< getBlockName(PrevBB) << "\n");
- DEBUG(dbgs() << " Edge probability: "
- << MBPI->getEdgeProbability(PrevBB, FBB) << " vs "
- << MBPI->getEdgeProbability(PrevBB, TBB) << "\n");
+ DEBUG(dbgs() << " Edge weight: " << MBPI->getEdgeWeight(PrevBB, FBB)
+ << " vs " << MBPI->getEdgeWeight(PrevBB, TBB) << "\n");
DebugLoc dl; // FIXME: this is nowhere
TII->RemoveBranch(*PrevBB);
TII->InsertBranch(*PrevBB, FBB, TBB, Cond, dl);
diff --git a/llvm/lib/CodeGen/MachineBranchProbabilityInfo.cpp b/llvm/lib/CodeGen/MachineBranchProbabilityInfo.cpp
index 5478dcba261..6fbc2be7048 100644
--- a/llvm/lib/CodeGen/MachineBranchProbabilityInfo.cpp
+++ b/llvm/lib/CodeGen/MachineBranchProbabilityInfo.cpp
@@ -28,61 +28,91 @@ char MachineBranchProbabilityInfo::ID = 0;
void MachineBranchProbabilityInfo::anchor() { }
-uint32_t MachineBranchProbabilityInfo::getEdgeWeight(
- const MachineBasicBlock *Src,
- MachineBasicBlock::const_succ_iterator Dst) const {
- return Src->getSuccProbability(Dst).getNumerator();
-}
+uint32_t MachineBranchProbabilityInfo::
+getSumForBlock(const MachineBasicBlock *MBB, uint32_t &Scale) const {
+ // First we compute the sum with 64-bits of precision, ensuring that cannot
+ // overflow by bounding the number of weights considered. Hopefully no one
+ // actually needs 2^32 successors.
+ assert(MBB->succ_size() < UINT32_MAX);
+ uint64_t Sum = 0;
+ Scale = 1;
+ for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(),
+ E = MBB->succ_end(); I != E; ++I) {
+ uint32_t Weight = getEdgeWeight(MBB, I);
+ Sum += Weight;
+ }
-uint32_t MachineBranchProbabilityInfo::getEdgeWeight(
- const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const {
- // This is a linear search. Try to use the const_succ_iterator version when
- // possible.
- return getEdgeWeight(Src, std::find(Src->succ_begin(), Src->succ_end(), Dst));
+ // If the computed sum fits in 32-bits, we're done.
+ if (Sum <= UINT32_MAX)
+ return Sum;
+
+ // Otherwise, compute the scale necessary to cause the weights to fit, and
+ // re-sum with that scale applied.
+ assert((Sum / UINT32_MAX) < UINT32_MAX);
+ Scale = (Sum / UINT32_MAX) + 1;
+ Sum = 0;
+ for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(),
+ E = MBB->succ_end(); I != E; ++I) {
+ uint32_t Weight = getEdgeWeight(MBB, I);
+ Sum += Weight / Scale;
+ }
+ assert(Sum <= UINT32_MAX);
+ return Sum;
}
-BranchProbability MachineBranchProbabilityInfo::getEdgeProbability(
- const MachineBasicBlock *Src,
- MachineBasicBlock::const_succ_iterator Dst) const {
- return Src->getSuccProbability(Dst);
+uint32_t MachineBranchProbabilityInfo::
+getEdgeWeight(const MachineBasicBlock *Src,
+ MachineBasicBlock::const_succ_iterator Dst) const {
+ uint32_t Weight = Src->getSuccWeight(Dst);
+ if (!Weight)
+ return DEFAULT_WEIGHT;
+ return Weight;
}
-BranchProbability MachineBranchProbabilityInfo::getEdgeProbability(
- const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const {
+uint32_t MachineBranchProbabilityInfo::
+getEdgeWeight(const MachineBasicBlock *Src,
+ const MachineBasicBlock *Dst) const {
// This is a linear search. Try to use the const_succ_iterator version when
// possible.
- return getEdgeProbability(Src,
- std::find(Src->succ_begin(), Src->succ_end(), Dst));
+ return getEdgeWeight(Src, std::find(Src->succ_begin(), Src->succ_end(), Dst));
}
bool
MachineBranchProbabilityInfo::isEdgeHot(const MachineBasicBlock *Src,
const MachineBasicBlock *Dst) const {
// Hot probability is at least 4/5 = 80%
- static BranchProbability HotProb(4, 5);
- return getEdgeProbability(Src, Dst) > HotProb;
+ // FIXME: Compare against a static "hot" BranchProbability.
+ return getEdgeProbability(Src, Dst) > BranchProbability(4, 5);
}
MachineBasicBlock *
MachineBranchProbabilityInfo::getHotSucc(MachineBasicBlock *MBB) const {
- auto MaxProb = BranchProbability::getZero();
+ uint32_t MaxWeight = 0;
MachineBasicBlock *MaxSucc = nullptr;
for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(),
E = MBB->succ_end(); I != E; ++I) {
- auto Prob = getEdgeProbability(MBB, I);
- if (Prob > MaxProb) {
- MaxProb = Prob;
+ uint32_t Weight = getEdgeWeight(MBB, I);
+ if (Weight > MaxWeight) {
+ MaxWeight = Weight;
MaxSucc = *I;
}
}
- static BranchProbability HotProb(4, 5);
- if (getEdgeProbability(MBB, MaxSucc) >= HotProb)
+ if (getEdgeProbability(MBB, MaxSucc) >= BranchProbability(4, 5))
return MaxSucc;
return nullptr;
}
+BranchProbability MachineBranchProbabilityInfo::getEdgeProbability(
+ const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const {
+ uint32_t Scale = 1;
+ uint32_t D = getSumForBlock(Src, Scale);
+ uint32_t N = getEdgeWeight(Src, Dst) / Scale;
+
+ return BranchProbability(N, D);
+}
+
raw_ostream &MachineBranchProbabilityInfo::printEdgeProbability(
raw_ostream &OS, const MachineBasicBlock *Src,
const MachineBasicBlock *Dst) const {
diff --git a/llvm/lib/CodeGen/TailDuplication.cpp b/llvm/lib/CodeGen/TailDuplication.cpp
index 1f5b54866ac..ff86dabfac5 100644
--- a/llvm/lib/CodeGen/TailDuplication.cpp
+++ b/llvm/lib/CodeGen/TailDuplication.cpp
@@ -745,12 +745,12 @@ TailDuplicatePass::duplicateSimpleBB(MachineBasicBlock *TailBB,
if (PredTBB)
TII->InsertBranch(*PredBB, PredTBB, PredFBB, PredCond, DebugLoc());
- auto Prob = MBPI->getEdgeProbability(PredBB, TailBB);
+ uint32_t Weight = MBPI->getEdgeWeight(PredBB, TailBB);
PredBB->removeSuccessor(TailBB);
unsigned NumSuccessors = PredBB->succ_size();
assert(NumSuccessors <= 1);
if (NumSuccessors == 0 || *PredBB->succ_begin() != NewTarget)
- PredBB->addSuccessor(NewTarget, Prob);
+ PredBB->addSuccessor(NewTarget, Weight);
TDBBs.push_back(PredBB);
}
@@ -858,7 +858,7 @@ TailDuplicatePass::TailDuplicate(MachineBasicBlock *TailBB,
"TailDuplicate called on block with multiple successors!");
for (MachineBasicBlock::succ_iterator I = TailBB->succ_begin(),
E = TailBB->succ_end(); I != E; ++I)
- PredBB->addSuccessor(*I, MBPI->getEdgeProbability(TailBB, I));
+ PredBB->addSuccessor(*I, MBPI->getEdgeWeight(TailBB, I));
Changed = true;
++NumTailDups;
OpenPOWER on IntegriCloud