Replace all weight-based interfaces in MBB with probability-based interfaces, and update all uses of old interfaces.
The patch in http://reviews.llvm.org/D13745 is broken into four parts:
1. New interfaces without functional changes (http://reviews.llvm.org/D13908).
2. Use new interfaces in SelectionDAG, while in other passes treat probabilities
as weights (http://reviews.llvm.org/D14361).
3. Use new interfaces in all other passes.
4. Remove old interfaces.
This patch is 3+4 above. In this patch, MBB won't provide weight-based
interfaces any more, which are totally replaced by probability-based ones.
The interface addSuccessor() is redesigned so that the default probability is
unknown. We allow unknown probabilities but don't allow using it together
with known probabilities in successor list. That is to say, we either have a
list of successors with all known probabilities, or all unknown
probabilities. In the latter case, we assume each successor has 1/N
probability where N is the number of successors. An assertion checks if the
user is attempting to add a successor with the disallowed mixed use as stated
above. This can help us catch many misuses.
All uses of weight-based interfaces are now updated to use probability-based
ones.
Differential revision: http://reviews.llvm.org/D14973
llvm-svn: 254348
diff --git a/llvm/lib/CodeGen/IfConversion.cpp b/llvm/lib/CodeGen/IfConversion.cpp
index 0b2f3ea..ff28f95 100644
--- a/llvm/lib/CodeGen/IfConversion.cpp
+++ b/llvm/lib/CodeGen/IfConversion.cpp
@@ -32,6 +32,7 @@
#include "llvm/Target/TargetLowering.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Target/TargetSubtargetInfo.h"
+#include <algorithm>
using namespace llvm;
@@ -1151,28 +1152,6 @@
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) {
@@ -1229,16 +1208,14 @@
DontKill.clear();
bool HasEarlyExit = CvtBBI->FalseBB != nullptr;
- uint64_t CvtNext = 0, CvtFalse = 0, BBNext = 0, BBCvt = 0, SumWeight = 0;
- uint32_t WeightScale = 0;
+ BranchProbability CvtNext, CvtFalse, BBNext, BBCvt;
if (HasEarlyExit) {
- // 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);
+ // 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);
}
if (CvtBBI->BB->pred_size() > 1) {
@@ -1266,22 +1243,24 @@
CvtBBI->BrCond.end());
if (TII->ReverseBranchCondition(RevCond))
llvm_unreachable("Unable to reverse branch condition!");
- TII->InsertBranch(*BBI.BB, CvtBBI->FalseBB, nullptr, RevCond, dl);
- 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);
+ // 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);
}
// Merge in the 'false' block if the 'false' block has no other
@@ -1524,7 +1503,7 @@
MergeBlocks(BBI, TailBBI);
TailBBI.IsDone = true;
} else {
- BBI.BB->addSuccessor(TailBB);
+ BBI.BB->addSuccessor(TailBB, BranchProbability::getOne());
InsertUncondBranch(BBI.BB, TailBB, TII);
BBI.HasFallThrough = false;
}
@@ -1688,21 +1667,26 @@
FromBBI.BB->succ_end());
MachineBasicBlock *NBB = getNextBlock(FromBBI.BB);
MachineBasicBlock *FallThrough = FromBBI.HasFallThrough ? NBB : nullptr;
-
- // The edge weight from ToBBI.BB to FromBBI.BB, which is only needed when
+ // 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.
- uint32_t To2FromWeight = 0;
- // WeightScale and SumWeight are for calculating successor probabilities of
- // FromBBI.BB.
- uint32_t WeightScale = 0;
- uint32_t SumWeight = 0;
+ auto To2FromProb = BranchProbability::getZero();
if (AddEdges && ToBBI.BB->isSuccessor(FromBBI.BB)) {
- 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);
+ 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());
+ }
+
+ 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());
}
for (unsigned i = 0, e = FromSuccs.size(); i != e; ++i) {
@@ -1711,39 +1695,38 @@
if (Succ == FallThrough)
continue;
- uint32_t NewWeight = 0;
+ auto NewProb = BranchProbability::getZero();
if (AddEdges) {
- // 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);
+ // 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);
- // To2FromWeight is 0 when FromBBI.BB is not a successor of ToBBI.BB. This
+ // To2FromProb 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 weights on FromBBI.BB's out-edges when adding new
- // successors.
- if (To2FromWeight > 0) {
- BranchProbability Prob(NewWeight / WeightScale, SumWeight);
- NewWeight = Prob.scale(To2FromWeight);
- }
+ // could just use the probabilities on FromBBI.BB's out-edges when adding
+ // new successors.
+ if (!To2FromProb.isZero())
+ NewProb *= To2FromProb;
}
FromBBI.BB->removeSuccessor(Succ);
if (AddEdges) {
- // 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.
+ // 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.
//
// Before ifcvt: After ifcvt (assume B->D is kept):
//
@@ -1755,11 +1738,11 @@
// C D C D
//
if (ToBBI.BB->isSuccessor(Succ))
- ToBBI.BB->setSuccWeight(
+ ToBBI.BB->setSuccProbability(
std::find(ToBBI.BB->succ_begin(), ToBBI.BB->succ_end(), Succ),
- MBPI->getEdgeWeight(ToBBI.BB, Succ) + NewWeight);
+ MBPI->getEdgeProbability(ToBBI.BB, Succ) + NewProb);
else
- ToBBI.BB->addSuccessor(Succ, NewWeight);
+ ToBBI.BB->addSuccessor(Succ, NewProb);
}
}