X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FBranchProbabilityInfo.cpp;h=6cdf43a06a9f559f47a725814e327420d9144f0b;hb=0123bc6beac1ca9a06450e98d8e829d32ce52498;hp=54c148ed29303cb0817a6b010ecd4e9e63a38bcf;hpb=77226a03dca98e6237c1068f2652fe41bea7b687;p=oota-llvm.git diff --git a/lib/Analysis/BranchProbabilityInfo.cpp b/lib/Analysis/BranchProbabilityInfo.cpp index 54c148ed293..6cdf43a06a9 100644 --- a/lib/Analysis/BranchProbabilityInfo.cpp +++ b/lib/Analysis/BranchProbabilityInfo.cpp @@ -14,23 +14,26 @@ #include "llvm/Analysis/BranchProbabilityInfo.h" #include "llvm/ADT/PostOrderIterator.h" #include "llvm/Analysis/LoopInfo.h" +#include "llvm/IR/CFG.h" #include "llvm/IR/Constants.h" #include "llvm/IR/Function.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/LLVMContext.h" #include "llvm/IR/Metadata.h" -#include "llvm/Support/CFG.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" using namespace llvm; -INITIALIZE_PASS_BEGIN(BranchProbabilityInfo, "branch-prob", +#define DEBUG_TYPE "branch-prob" + +INITIALIZE_PASS_BEGIN(BranchProbabilityInfoWrapperPass, "branch-prob", "Branch Probability Analysis", false, true) -INITIALIZE_PASS_DEPENDENCY(LoopInfo) -INITIALIZE_PASS_END(BranchProbabilityInfo, "branch-prob", +INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) +INITIALIZE_PASS_END(BranchProbabilityInfoWrapperPass, "branch-prob", "Branch Probability Analysis", false, true) -char BranchProbabilityInfo::ID = 0; +char BranchProbabilityInfoWrapperPass::ID = 0; // Weights are for internal use only. They are used by heuristics to help to // estimate edges' probability. Example: @@ -112,11 +115,6 @@ static const uint32_t NORMAL_WEIGHT = 16; // Minimum weight of an edge. Please note, that weight is NEVER 0. static const uint32_t MIN_WEIGHT = 1; -static uint32_t getMaxWeightFor(BasicBlock *BB) { - return UINT32_MAX / BB->getTerminator()->getNumSuccessors(); -} - - /// \brief Calculate edge weights for successors lead to unreachable. /// /// Predict that a successor which leads necessarily to an @@ -151,8 +149,8 @@ bool BranchProbabilityInfo::calcUnreachableHeuristics(BasicBlock *BB) { uint32_t UnreachableWeight = std::max(UR_TAKEN_WEIGHT / (unsigned)UnreachableEdges.size(), MIN_WEIGHT); - for (SmallVector::iterator I = UnreachableEdges.begin(), - E = UnreachableEdges.end(); + for (SmallVectorImpl::iterator I = UnreachableEdges.begin(), + E = UnreachableEdges.end(); I != E; ++I) setEdgeWeight(BB, *I, UnreachableWeight); @@ -161,8 +159,8 @@ bool BranchProbabilityInfo::calcUnreachableHeuristics(BasicBlock *BB) { uint32_t ReachableWeight = std::max(UR_NONTAKEN_WEIGHT / (unsigned)ReachableEdges.size(), NORMAL_WEIGHT); - for (SmallVector::iterator I = ReachableEdges.begin(), - E = ReachableEdges.end(); + for (SmallVectorImpl::iterator I = ReachableEdges.begin(), + E = ReachableEdges.end(); I != E; ++I) setEdgeWeight(BB, *I, ReachableWeight); @@ -182,27 +180,45 @@ bool BranchProbabilityInfo::calcMetadataWeights(BasicBlock *BB) { if (!WeightsNode) return false; + // Check that the number of successors is manageable. + assert(TI->getNumSuccessors() < UINT32_MAX && "Too many successors"); + // Ensure there are weights for all of the successors. Note that the first // operand to the metadata node is a name, not a weight. if (WeightsNode->getNumOperands() != TI->getNumSuccessors() + 1) return false; - // Build up the final weights that will be used in a temporary buffer, but - // don't add them until all weihts are present. Each weight value is clamped - // to [1, getMaxWeightFor(BB)]. - uint32_t WeightLimit = getMaxWeightFor(BB); + // Build up the final weights that will be used in a temporary buffer. + // Compute the sum of all weights to later decide whether they need to + // be scaled to fit in 32 bits. + uint64_t WeightSum = 0; SmallVector Weights; Weights.reserve(TI->getNumSuccessors()); for (unsigned i = 1, e = WeightsNode->getNumOperands(); i != e; ++i) { - ConstantInt *Weight = dyn_cast(WeightsNode->getOperand(i)); + ConstantInt *Weight = + mdconst::dyn_extract(WeightsNode->getOperand(i)); if (!Weight) return false; - Weights.push_back( - std::max(1, Weight->getLimitedValue(WeightLimit))); + assert(Weight->getValue().getActiveBits() <= 32 && + "Too many bits for uint32_t"); + Weights.push_back(Weight->getZExtValue()); + WeightSum += Weights.back(); } assert(Weights.size() == TI->getNumSuccessors() && "Checked above"); - for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) - setEdgeWeight(BB, i, Weights[i]); + + // If the sum of weights does not fit in 32 bits, scale every weight down + // accordingly. + uint64_t ScalingFactor = + (WeightSum > UINT32_MAX) ? WeightSum / UINT32_MAX + 1 : 1; + + WeightSum = 0; + for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) { + uint32_t W = Weights[i] / ScalingFactor; + WeightSum += W; + setEdgeWeight(BB, i, W); + } + assert(WeightSum <= UINT32_MAX && + "Expected weights to scale down to 32 bits"); return true; } @@ -222,9 +238,7 @@ bool BranchProbabilityInfo::calcColdCallHeuristics(BasicBlock *BB) { // Determine which successors are post-dominated by a cold block. SmallVector ColdEdges; - ColdEdges.reserve(TI->getNumSuccessors()); SmallVector NormalEdges; - NormalEdges.reserve(TI->getNumSuccessors()); for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) if (PostDominatedByColdCall.count(*I)) ColdEdges.push_back(I.getSuccessorIndex()); @@ -253,8 +267,8 @@ bool BranchProbabilityInfo::calcColdCallHeuristics(BasicBlock *BB) { uint32_t ColdWeight = std::max(CC_TAKEN_WEIGHT / (unsigned) ColdEdges.size(), MIN_WEIGHT); - for (SmallVector::iterator I = ColdEdges.begin(), - E = ColdEdges.end(); + for (SmallVectorImpl::iterator I = ColdEdges.begin(), + E = ColdEdges.end(); I != E; ++I) setEdgeWeight(BB, *I, ColdWeight); @@ -262,8 +276,8 @@ bool BranchProbabilityInfo::calcColdCallHeuristics(BasicBlock *BB) { return true; uint32_t NormalWeight = std::max( CC_NONTAKEN_WEIGHT / (unsigned) NormalEdges.size(), NORMAL_WEIGHT); - for (SmallVector::iterator I = NormalEdges.begin(), - E = NormalEdges.end(); + for (SmallVectorImpl::iterator I = NormalEdges.begin(), + E = NormalEdges.end(); I != E; ++I) setEdgeWeight(BB, *I, NormalWeight); @@ -305,8 +319,9 @@ bool BranchProbabilityInfo::calcPointerHeuristics(BasicBlock *BB) { // Calculate Edge Weights using "Loop Branch Heuristics". Predict backedges // as taken, exiting edges as not-taken. -bool BranchProbabilityInfo::calcLoopBranchHeuristics(BasicBlock *BB) { - Loop *L = LI->getLoopFor(BB); +bool BranchProbabilityInfo::calcLoopBranchHeuristics(BasicBlock *BB, + const LoopInfo &LI) { + Loop *L = LI.getLoopFor(BB); if (!L) return false; @@ -323,12 +338,15 @@ bool BranchProbabilityInfo::calcLoopBranchHeuristics(BasicBlock *BB) { InEdges.push_back(I.getSuccessorIndex()); } + if (BackEdges.empty() && ExitingEdges.empty()) + return false; + if (uint32_t numBackEdges = BackEdges.size()) { uint32_t backWeight = LBH_TAKEN_WEIGHT / numBackEdges; if (backWeight < NORMAL_WEIGHT) backWeight = NORMAL_WEIGHT; - for (SmallVector::iterator EI = BackEdges.begin(), + for (SmallVectorImpl::iterator EI = BackEdges.begin(), EE = BackEdges.end(); EI != EE; ++EI) { setEdgeWeight(BB, *EI, backWeight); } @@ -339,7 +357,7 @@ bool BranchProbabilityInfo::calcLoopBranchHeuristics(BasicBlock *BB) { if (inWeight < NORMAL_WEIGHT) inWeight = NORMAL_WEIGHT; - for (SmallVector::iterator EI = InEdges.begin(), + for (SmallVectorImpl::iterator EI = InEdges.begin(), EE = InEdges.end(); EI != EE; ++EI) { setEdgeWeight(BB, *EI, inWeight); } @@ -350,7 +368,7 @@ bool BranchProbabilityInfo::calcLoopBranchHeuristics(BasicBlock *BB) { if (exitWeight < MIN_WEIGHT) exitWeight = MIN_WEIGHT; - for (SmallVector::iterator EI = ExitingEdges.begin(), + for (SmallVectorImpl::iterator EI = ExitingEdges.begin(), EE = ExitingEdges.end(); EI != EE; ++EI) { setEdgeWeight(BB, *EI, exitWeight); } @@ -374,6 +392,14 @@ bool BranchProbabilityInfo::calcZeroHeuristics(BasicBlock *BB) { if (!CV) return false; + // If the LHS is the result of AND'ing a value with a single bit bitmask, + // we don't have information about probabilities. + if (Instruction *LHS = dyn_cast(CI->getOperand(0))) + if (LHS->getOpcode() == Instruction::And) + if (ConstantInt *AndRHS = dyn_cast(LHS->getOperand(1))) + if (AndRHS->getUniqueInteger().isPowerOf2()) + return false; + bool isProb; if (CV->isZero()) { switch (CI->getPredicate()) { @@ -400,10 +426,24 @@ bool BranchProbabilityInfo::calcZeroHeuristics(BasicBlock *BB) { // InstCombine canonicalizes X <= 0 into X < 1. // X <= 0 -> Unlikely isProb = false; - } else if (CV->isAllOnesValue() && CI->getPredicate() == CmpInst::ICMP_SGT) { - // InstCombine canonicalizes X >= 0 into X > -1. - // X >= 0 -> Likely - isProb = true; + } else if (CV->isAllOnesValue()) { + switch (CI->getPredicate()) { + case CmpInst::ICMP_EQ: + // X == -1 -> Unlikely + isProb = false; + break; + case CmpInst::ICMP_NE: + // X != -1 -> Likely + isProb = true; + break; + case CmpInst::ICMP_SGT: + // InstCombine canonicalizes X >= 0 into X > -1. + // X >= 0 -> Likely + isProb = true; + break; + default: + return false; + } } else { return false; } @@ -465,55 +505,19 @@ bool BranchProbabilityInfo::calcInvokeHeuristics(BasicBlock *BB) { return true; } -void BranchProbabilityInfo::getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired(); - AU.setPreservesAll(); +void BranchProbabilityInfo::releaseMemory() { + Weights.clear(); } -bool BranchProbabilityInfo::runOnFunction(Function &F) { - LastF = &F; // Store the last function we ran on for printing. - LI = &getAnalysis(); - assert(PostDominatedByUnreachable.empty()); - assert(PostDominatedByColdCall.empty()); - - // Walk the basic blocks in post-order so that we can build up state about - // the successors of a block iteratively. - for (po_iterator I = po_begin(&F.getEntryBlock()), - E = po_end(&F.getEntryBlock()); - I != E; ++I) { - DEBUG(dbgs() << "Computing probabilities for " << I->getName() << "\n"); - if (calcUnreachableHeuristics(*I)) - continue; - if (calcMetadataWeights(*I)) - continue; - if (calcColdCallHeuristics(*I)) - continue; - if (calcLoopBranchHeuristics(*I)) - continue; - if (calcPointerHeuristics(*I)) - continue; - if (calcZeroHeuristics(*I)) - continue; - if (calcFloatingPointHeuristics(*I)) - continue; - calcInvokeHeuristics(*I); - } - - PostDominatedByUnreachable.clear(); - PostDominatedByColdCall.clear(); - return false; -} - -void BranchProbabilityInfo::print(raw_ostream &OS, const Module *) const { +void BranchProbabilityInfo::print(raw_ostream &OS) const { OS << "---- Branch Probabilities ----\n"; // We print the probabilities from the last function the analysis ran over, // or the function it is currently running over. assert(LastF && "Cannot print prior to running over a function"); - for (Function::const_iterator BI = LastF->begin(), BE = LastF->end(); - BI != BE; ++BI) { - for (succ_const_iterator SI = succ_begin(BI), SE = succ_end(BI); - SI != SE; ++SI) { - printEdgeProbability(OS << " ", BI, *SI); + for (const auto &BI : *LastF) { + for (succ_const_iterator SI = succ_begin(&BI), SE = succ_end(&BI); SI != SE; + ++SI) { + printEdgeProbability(OS << " ", &BI, *SI); } } } @@ -526,7 +530,7 @@ uint32_t BranchProbabilityInfo::getSumForBlock(const BasicBlock *BB) const { uint32_t PrevSum = Sum; Sum += Weight; - assert(Sum > PrevSum); (void) PrevSum; + assert(Sum >= PrevSum); (void) PrevSum; } return Sum; @@ -542,7 +546,7 @@ isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const { BasicBlock *BranchProbabilityInfo::getHotSucc(BasicBlock *BB) const { uint32_t Sum = 0; uint32_t MaxWeight = 0; - BasicBlock *MaxSucc = 0; + BasicBlock *MaxSucc = nullptr; for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) { BasicBlock *Succ = *I; @@ -562,7 +566,7 @@ BasicBlock *BranchProbabilityInfo::getHotSucc(BasicBlock *BB) const { if (BranchProbability(MaxWeight, Sum) > BranchProbability(4, 5)) return MaxSucc; - return 0; + return nullptr; } /// Get the raw edge weight for the edge. If can't find it, return @@ -579,19 +583,27 @@ getEdgeWeight(const BasicBlock *Src, unsigned IndexInSuccessors) const { return DEFAULT_WEIGHT; } +uint32_t BranchProbabilityInfo::getEdgeWeight(const BasicBlock *Src, + succ_const_iterator Dst) const { + return getEdgeWeight(Src, Dst.getSuccessorIndex()); +} + /// Get the raw edge weight calculated for the block pair. This returns the sum /// of all raw edge weights from Src to Dst. uint32_t BranchProbabilityInfo:: getEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst) const { uint32_t Weight = 0; + bool FoundWeight = false; DenseMap::const_iterator MapI; for (succ_const_iterator I = succ_begin(Src), E = succ_end(Src); I != E; ++I) if (*I == Dst) { MapI = Weights.find(std::make_pair(Src, I.getSuccessorIndex())); - if (MapI != Weights.end()) + if (MapI != Weights.end()) { + FoundWeight = true; Weight += MapI->second; + } } - return (Weight == 0) ? DEFAULT_WEIGHT : Weight; + return (!FoundWeight) ? DEFAULT_WEIGHT : Weight; } /// Set the edge weight for a given edge specified by PredBlock and an index @@ -611,6 +623,11 @@ getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const { uint32_t N = getEdgeWeight(Src, IndexInSuccessors); uint32_t D = getSumForBlock(Src); + // It is possible that the edge weight on the only successor edge of Src is + // zero, in which case we return 100%. + if (N == 0 && D == 0) + return BranchProbability::getOne(); + return BranchProbability(N, D); } @@ -622,9 +639,20 @@ getEdgeProbability(const BasicBlock *Src, const BasicBlock *Dst) const { uint32_t N = getEdgeWeight(Src, Dst); uint32_t D = getSumForBlock(Src); + // It is possible that the edge weight on the only successor edge of Src is + // zero, in which case we return 100%. + if (N == 0 && D == 0) + return BranchProbability::getOne(); + return BranchProbability(N, D); } +BranchProbability +BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src, + succ_const_iterator Dst) const { + return getEdgeProbability(Src, Dst.getSuccessorIndex()); +} + raw_ostream & BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS, const BasicBlock *Src, @@ -637,3 +665,54 @@ BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS, return OS; } + +void BranchProbabilityInfo::calculate(Function &F, const LoopInfo& LI) { + DEBUG(dbgs() << "---- Branch Probability Info : " << F.getName() + << " ----\n\n"); + LastF = &F; // Store the last function we ran on for printing. + assert(PostDominatedByUnreachable.empty()); + assert(PostDominatedByColdCall.empty()); + + // Walk the basic blocks in post-order so that we can build up state about + // the successors of a block iteratively. + for (auto BB : post_order(&F.getEntryBlock())) { + DEBUG(dbgs() << "Computing probabilities for " << BB->getName() << "\n"); + if (calcUnreachableHeuristics(BB)) + continue; + if (calcMetadataWeights(BB)) + continue; + if (calcColdCallHeuristics(BB)) + continue; + if (calcLoopBranchHeuristics(BB, LI)) + continue; + if (calcPointerHeuristics(BB)) + continue; + if (calcZeroHeuristics(BB)) + continue; + if (calcFloatingPointHeuristics(BB)) + continue; + calcInvokeHeuristics(BB); + } + + PostDominatedByUnreachable.clear(); + PostDominatedByColdCall.clear(); +} + +void BranchProbabilityInfoWrapperPass::getAnalysisUsage( + AnalysisUsage &AU) const { + AU.addRequired(); + AU.setPreservesAll(); +} + +bool BranchProbabilityInfoWrapperPass::runOnFunction(Function &F) { + const LoopInfo &LI = getAnalysis().getLoopInfo(); + BPI.calculate(F, LI); + return false; +} + +void BranchProbabilityInfoWrapperPass::releaseMemory() { BPI.releaseMemory(); } + +void BranchProbabilityInfoWrapperPass::print(raw_ostream &OS, + const Module *) const { + BPI.print(OS); +}