From: Cong Hou Date: Wed, 5 Aug 2015 22:01:20 +0000 (+0000) Subject: Record whether the weights on out-edges from a MBB are normalized. X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=commitdiff_plain;h=3f81410d8cebd10248c2201c701ae8308a0ca2d8 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 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@244154 91177308-0d34-0410-b5e6-96231b3b80d8 --- diff --git a/include/llvm/CodeGen/MachineBasicBlock.h b/include/llvm/CodeGen/MachineBasicBlock.h index 5486f8a5037..7be5cb234ed 100644 --- a/include/llvm/CodeGen/MachineBasicBlock.h +++ b/include/llvm/CodeGen/MachineBasicBlock.h @@ -65,6 +65,10 @@ class MachineBasicBlock : public ilist_node { Instructions Insts; const BasicBlock *BB; int Number; + + /// A flag tracking whether the weights of all successors are normalized. + bool AreSuccWeightsNormalized; + MachineFunction *xParent; /// Keep track of the predecessor / successor basicblocks. @@ -129,6 +133,9 @@ public: const MachineFunction *getParent() const { return xParent; } MachineFunction *getParent() { return xParent; } + /// Return whether all weights of successors are normalized. + bool areSuccWeightsNormalized() const { return AreSuccWeightsNormalized; } + /// MachineBasicBlock iterator that automatically skips over MIs that are /// inside bundles (i.e. walk top level MIs only). template @@ -384,6 +391,12 @@ public: /// Set successor weight of a given iterator. void setSuccWeight(succ_iterator I, uint32_t weight); + /// 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 normalizeSuccWeights(); + /// Remove successor from the successors list of this MachineBasicBlock. The /// Predecessors list of succ is automatically updated. void removeSuccessor(MachineBasicBlock *succ); diff --git a/include/llvm/CodeGen/MachineBranchProbabilityInfo.h b/include/llvm/CodeGen/MachineBranchProbabilityInfo.h index 7ba749559c0..55b96961c35 100644 --- a/include/llvm/CodeGen/MachineBranchProbabilityInfo.h +++ b/include/llvm/CodeGen/MachineBranchProbabilityInfo.h @@ -59,6 +59,10 @@ public: // adjustment. Any edge weights used with the sum should be divided by Scale. uint32_t getSumForBlock(const MachineBasicBlock *MBB, uint32_t &Scale) const; + // Get sum of the block successors' weights, and force normalizing the + // successors' weights of MBB so that their sum fit within 32-bits. + uint32_t getSumForBlock(MachineBasicBlock *MBB) const; + // A 'Hot' edge is an edge which probability is >= 80%. bool isEdgeHot(const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const; @@ -82,8 +86,34 @@ public: raw_ostream &printEdgeProbability(raw_ostream &OS, const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const; + + // Normalize a list of weights by scaling them down so that the sum of them + // doesn't exceed UINT32_MAX. Return the scale. + template + static uint32_t normalizeEdgeWeights(WeightList &Weights); }; +template +uint32_t +MachineBranchProbabilityInfo::normalizeEdgeWeights(WeightList &Weights) { + assert(Weights.size() < UINT32_MAX && "Too many weights in the list!"); + // First we compute the sum with 64-bits of precision. + uint64_t Sum = std::accumulate(Weights.begin(), Weights.end(), uint64_t(0)); + + // If the computed sum fits in 32-bits, we're done. + if (Sum <= UINT32_MAX) + return 1; + + // Otherwise, compute the scale necessary to cause the weights to fit, and + // re-sum with that scale applied. + assert((Sum / UINT32_MAX) < UINT32_MAX && + "The sum of weights exceeds UINT32_MAX^2!"); + uint32_t Scale = (Sum / UINT32_MAX) + 1; + for (auto &W : Weights) + W /= Scale; + return Scale; +} + } diff --git a/lib/CodeGen/IfConversion.cpp b/lib/CodeGen/IfConversion.cpp index ee0532bfc63..8896cdbb176 100644 --- a/lib/CodeGen/IfConversion.cpp +++ b/lib/CodeGen/IfConversion.cpp @@ -1232,15 +1232,17 @@ bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) { 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 @@ bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) { // 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/lib/CodeGen/MachineBasicBlock.cpp b/lib/CodeGen/MachineBasicBlock.cpp index 5d3f7ebaed2..e2f381e6c8e 100644 --- a/lib/CodeGen/MachineBasicBlock.cpp +++ b/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 @@ using namespace llvm; #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 @@ void MachineBasicBlock::addSuccessor(MachineBasicBlock *succ, uint32_t weight) { 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 @@ uint32_t MachineBasicBlock::getSuccWeight(const_succ_iterator Succ) const { 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/lib/CodeGen/MachineBlockPlacement.cpp b/lib/CodeGen/MachineBlockPlacement.cpp index b77c803f77f..ecc093e97f5 100644 --- a/lib/CodeGen/MachineBlockPlacement.cpp +++ b/lib/CodeGen/MachineBlockPlacement.cpp @@ -361,8 +361,7 @@ MachineBlockPlacement::selectBestSuccessor(MachineBasicBlock *BB, // 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 @@ MachineBlockPlacement::selectBestSuccessor(MachineBasicBlock *BB, } 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 @@ MachineBlockPlacement::findBestLoopExit(MachineFunction &F, MachineLoop &L, // 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 @@ MachineBlockPlacement::findBestLoopExit(MachineFunction &F, MachineLoop &L, 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/lib/CodeGen/MachineBranchProbabilityInfo.cpp b/lib/CodeGen/MachineBranchProbabilityInfo.cpp index 6fbc2be7048..fe03d4d0b5f 100644 --- a/lib/CodeGen/MachineBranchProbabilityInfo.cpp +++ b/lib/CodeGen/MachineBranchProbabilityInfo.cpp @@ -28,36 +28,35 @@ char MachineBranchProbabilityInfo::ID = 0; 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; +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(); + + SmallVector 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; - } + E = MBB->succ_end(); + I != E; ++I) + Weights.push_back(getEdgeWeight(MBB, I)); - // If the computed sum fits in 32-bits, we're done. - if (Sum <= UINT32_MAX) - return Sum; + return std::accumulate(Weights.begin(), Weights.end(), 0u); +} - // 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; +uint32_t +MachineBranchProbabilityInfo::getSumForBlock(const MachineBasicBlock *MBB, + uint32_t &Scale) const { + SmallVector 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)); + + if (MBB->areSuccWeightsNormalized()) + Scale = 1; + else + Scale = MachineBranchProbabilityInfo::normalizeEdgeWeights(Weights); + return std::accumulate(Weights.begin(), Weights.end(), 0u); } uint32_t MachineBranchProbabilityInfo::