Record whether the weights on out-edges from a MBB are normalized.
1. Create a utility function normalizeEdgeWeights() in MachineBranchProbabilityInfo that normalizes a list of edge weights so that the sum of then can fit in uint32_t.
2. Provide an interface in MachineBasicBlock to normalize its successors' weights.
3. Add a flag in MachineBasicBlock that tracks whether its successors' weights are normalized.
4. Provide an overload of getSumForBlock that accepts a non-const pointer to a MBB so that it can force normalizing this MBB's successors' weights.
5. Update several uses of getSumForBlock() by eliminating the once needed weight scale.
Differential Revision: http://reviews.llvm.org/D11442
llvm-svn: 244154
diff --git a/llvm/lib/CodeGen/IfConversion.cpp b/llvm/lib/CodeGen/IfConversion.cpp
index ee0532b..8896cdb 100644
--- a/llvm/lib/CodeGen/IfConversion.cpp
+++ b/llvm/lib/CodeGen/IfConversion.cpp
@@ -1232,15 +1232,17 @@
bool HasEarlyExit = CvtBBI->FalseBB != nullptr;
uint64_t CvtNext = 0, CvtFalse = 0, BBNext = 0, BBCvt = 0, SumWeight = 0;
- uint32_t WeightScale = 0;
if (HasEarlyExit) {
// Get weights before modifying CvtBBI->BB and BBI.BB.
+ // Explictly normalize the weights of all edges from CvtBBI->BB so that we
+ // are aware that the edge weights obtained below are normalized.
+ CvtBBI->BB->normalizeSuccWeights();
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);
+ SumWeight = MBPI->getSumForBlock(CvtBBI->BB);
}
if (CvtBBI->BB->pred_size() > 1) {
@@ -1277,8 +1279,8 @@
// 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;
+ uint64_t NewNext = BBNext * SumWeight + BBCvt * CvtNext;
+ uint64_t NewFalse = BBCvt * CvtFalse;
// 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.
diff --git a/llvm/lib/CodeGen/MachineBasicBlock.cpp b/llvm/lib/CodeGen/MachineBasicBlock.cpp
index 5d3f7eb..e2f381e 100644
--- a/llvm/lib/CodeGen/MachineBasicBlock.cpp
+++ b/llvm/lib/CodeGen/MachineBasicBlock.cpp
@@ -16,6 +16,7 @@
#include "llvm/ADT/SmallString.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/LiveVariables.h"
+#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
@@ -39,8 +40,9 @@
#define DEBUG_TYPE "codegen"
MachineBasicBlock::MachineBasicBlock(MachineFunction &mf, const BasicBlock *bb)
- : BB(bb), Number(-1), xParent(&mf), Alignment(0), IsLandingPad(false),
- AddressTaken(false), CachedMCSymbol(nullptr) {
+ : BB(bb), Number(-1), AreSuccWeightsNormalized(false), xParent(&mf),
+ Alignment(0), IsLandingPad(false), AddressTaken(false),
+ CachedMCSymbol(nullptr) {
Insts.Parent = this;
}
@@ -481,8 +483,10 @@
if (weight != 0 && Weights.empty())
Weights.resize(Successors.size());
- if (weight != 0 || !Weights.empty())
+ if (weight != 0 || !Weights.empty()) {
Weights.push_back(weight);
+ AreSuccWeightsNormalized = false;
+ }
Successors.push_back(succ);
succ->addPredecessor(this);
@@ -1096,7 +1100,25 @@
void MachineBasicBlock::setSuccWeight(succ_iterator I, uint32_t weight) {
if (Weights.empty())
return;
- *getWeightIterator(I) = weight;
+ auto WeightIter = getWeightIterator(I);
+ uint32_t OldWeight = *WeightIter;
+ *WeightIter = weight;
+ if (weight > OldWeight)
+ AreSuccWeightsNormalized = false;
+}
+
+/// Normalize all succesor weights so that the sum of them does not exceed
+/// UINT32_MAX. Return true if the weights are modified and false otherwise.
+/// Note that weights that are modified after calling this function are not
+/// guaranteed to be normalized.
+bool MachineBasicBlock::normalizeSuccWeights() {
+ if (!AreSuccWeightsNormalized) {
+ uint32_t Scale =
+ MachineBranchProbabilityInfo::normalizeEdgeWeights(Weights);
+ AreSuccWeightsNormalized = true;
+ return Scale != 1;
+ }
+ return false;
}
/// getWeightIterator - Return wight iterator corresonding to the I successor
diff --git a/llvm/lib/CodeGen/MachineBlockPlacement.cpp b/llvm/lib/CodeGen/MachineBlockPlacement.cpp
index b77c803..ecc093e 100644
--- a/llvm/lib/CodeGen/MachineBlockPlacement.cpp
+++ b/llvm/lib/CodeGen/MachineBlockPlacement.cpp
@@ -361,8 +361,7 @@
// 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);
+ uint32_t SumWeight = MBPI->getSumForBlock(BB);
DEBUG(dbgs() << "Attempting merge from: " << getBlockName(BB) << "\n");
for (MachineBasicBlock *Succ : BB->successors()) {
if (BlockFilter && !BlockFilter->count(Succ))
@@ -378,7 +377,7 @@
}
uint32_t SuccWeight = MBPI->getEdgeWeight(BB, Succ);
- BranchProbability SuccProb(SuccWeight / WeightScale, SumWeight);
+ BranchProbability SuccProb(SuccWeight, SumWeight);
// If we outline optional branches, look whether Succ is unavoidable, i.e.
// dominates all terminators of the MachineFunction. If it does, other
@@ -675,8 +674,7 @@
// 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);
+ uint32_t SumWeight = MBPI->getSumForBlock(MBB);
for (MachineBasicBlock *Succ : MBB->successors()) {
if (Succ->isLandingPad())
continue;
@@ -705,7 +703,7 @@
BlocksExitingToOuterLoop.insert(MBB);
}
- BranchProbability SuccProb(SuccWeight / WeightScale, SumWeight);
+ BranchProbability SuccProb(SuccWeight, SumWeight);
BlockFrequency ExitEdgeFreq = MBFI->getBlockFreq(MBB) * SuccProb;
DEBUG(dbgs() << " exiting: " << getBlockName(MBB) << " -> "
<< getBlockName(Succ) << " [L:" << SuccLoopDepth << "] (";
diff --git a/llvm/lib/CodeGen/MachineBranchProbabilityInfo.cpp b/llvm/lib/CodeGen/MachineBranchProbabilityInfo.cpp
index 6fbc2be..fe03d4d 100644
--- a/llvm/lib/CodeGen/MachineBranchProbabilityInfo.cpp
+++ b/llvm/lib/CodeGen/MachineBranchProbabilityInfo.cpp
@@ -28,36 +28,35 @@
void MachineBranchProbabilityInfo::anchor() { }
-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::getSumForBlock(MachineBasicBlock *MBB) const {
+ // Normalize the weights of MBB's all successors so that the sum is guaranteed
+ // to be no greater than UINT32_MAX.
+ MBB->normalizeSuccWeights();
- // 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;
+ SmallVector<uint32_t, 8> Weights;
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;
+ E = MBB->succ_end();
+ I != E; ++I)
+ Weights.push_back(getEdgeWeight(MBB, I));
+
+ return std::accumulate(Weights.begin(), Weights.end(), 0u);
+}
+
+uint32_t
+MachineBranchProbabilityInfo::getSumForBlock(const MachineBasicBlock *MBB,
+ uint32_t &Scale) const {
+ SmallVector<uint32_t, 8> Weights;
+ for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(),
+ E = MBB->succ_end();
+ I != E; ++I)
+ Weights.push_back(getEdgeWeight(MBB, I));
+
+ if (MBB->areSuccWeightsNormalized())
+ Scale = 1;
+ else
+ Scale = MachineBranchProbabilityInfo::normalizeEdgeWeights(Weights);
+ return std::accumulate(Weights.begin(), Weights.end(), 0u);
}
uint32_t MachineBranchProbabilityInfo::