X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FBranchProbabilityInfo.cpp;h=8cd6ea46d3c57e6ae7142995b6001bd3565a334e;hb=7b9135922626f04652da8d8e5312fe9193d891d9;hp=a6481cf359bfbab8d28037a28e0e55c0a6c71af0;hpb=fe808927ac50545ee434f14a4dd6bff44ac48a30;p=oota-llvm.git diff --git a/lib/Analysis/BranchProbabilityInfo.cpp b/lib/Analysis/BranchProbabilityInfo.cpp index a6481cf359b..8cd6ea46d3c 100644 --- a/lib/Analysis/BranchProbabilityInfo.cpp +++ b/lib/Analysis/BranchProbabilityInfo.cpp @@ -14,19 +14,21 @@ #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" using namespace llvm; +#define DEBUG_TYPE "branch-prob" + INITIALIZE_PASS_BEGIN(BranchProbabilityInfo, "branch-prob", "Branch Probability Analysis", false, true) -INITIALIZE_PASS_DEPENDENCY(LoopInfo) +INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) INITIALIZE_PASS_END(BranchProbabilityInfo, "branch-prob", "Branch Probability Analysis", false, true) @@ -151,8 +153,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 +163,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); @@ -194,7 +196,8 @@ bool BranchProbabilityInfo::calcMetadataWeights(BasicBlock *BB) { 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( @@ -251,8 +254,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); @@ -260,8 +263,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); @@ -321,12 +324,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); } @@ -337,7 +343,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); } @@ -348,7 +354,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); } @@ -398,10 +404,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; } @@ -464,13 +484,15 @@ bool BranchProbabilityInfo::calcInvokeHeuristics(BasicBlock *BB) { } void BranchProbabilityInfo::getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired(); + AU.addRequired(); AU.setPreservesAll(); } bool BranchProbabilityInfo::runOnFunction(Function &F) { + DEBUG(dbgs() << "---- Branch Probability Info : " << F.getName() + << " ----\n\n"); LastF = &F; // Store the last function we ran on for printing. - LI = &getAnalysis(); + LI = &getAnalysis().getLoopInfo(); assert(PostDominatedByUnreachable.empty()); assert(PostDominatedByColdCall.empty()); @@ -540,7 +562,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; @@ -560,7 +582,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 @@ -577,6 +599,11 @@ 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::