X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FBranchProbabilityInfo.cpp;h=9c54a7eadd491a20acb96d2f8ee29a6688e506ed;hb=6053cd956fa6c781a4ee05cbc99ab15db3cf3d13;hp=57a2579ecb4d6d0317e4a06365dbfc631b057a28;hpb=9e76422b963a65f243fdbee0abed61068b82dd98;p=oota-llvm.git diff --git a/lib/Analysis/BranchProbabilityInfo.cpp b/lib/Analysis/BranchProbabilityInfo.cpp index 57a2579ecb4..9c54a7eadd4 100644 --- a/lib/Analysis/BranchProbabilityInfo.cpp +++ b/lib/Analysis/BranchProbabilityInfo.cpp @@ -11,8 +11,11 @@ // //===----------------------------------------------------------------------===// +#include "llvm/Constants.h" #include "llvm/Instructions.h" #include "llvm/Analysis/BranchProbabilityInfo.h" +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Support/Debug.h" using namespace llvm; @@ -24,16 +27,16 @@ INITIALIZE_PASS_END(BranchProbabilityInfo, "branch-prob", char BranchProbabilityInfo::ID = 0; - +namespace { // Please note that BranchProbabilityAnalysis is not a FunctionPass. // It is created by BranchProbabilityInfo (which is a FunctionPass), which // provides a clear interface. Thanks to that, all heuristics and other // private methods are hidden in the .cpp file. class BranchProbabilityAnalysis { - typedef std::pair Edge; + typedef std::pair Edge; - DenseMap *Weights; + DenseMap *Weights; BranchProbabilityInfo *BP; @@ -50,7 +53,7 @@ class BranchProbabilityAnalysis { // V // BB1<-+ // | | - // | | (Weight = 128) + // | | (Weight = 124) // V | // BB2--+ // | @@ -58,18 +61,27 @@ class BranchProbabilityAnalysis { // V // BB3 // - // Probability of the edge BB2->BB1 = 128 / (128 + 4) = 0.9696.. - // Probability of the edge BB2->BB3 = 4 / (128 + 4) = 0.0303.. + // Probability of the edge BB2->BB1 = 124 / (124 + 4) = 0.96875 + // Probability of the edge BB2->BB3 = 4 / (124 + 4) = 0.03125 + + static const uint32_t LBH_TAKEN_WEIGHT = 124; + static const uint32_t LBH_NONTAKEN_WEIGHT = 4; + + static const uint32_t RH_TAKEN_WEIGHT = 24; + static const uint32_t RH_NONTAKEN_WEIGHT = 8; - static const unsigned int LBH_TAKEN_WEIGHT = 128; - static const unsigned int LBH_NONTAKEN_WEIGHT = 4; + static const uint32_t PH_TAKEN_WEIGHT = 20; + static const uint32_t PH_NONTAKEN_WEIGHT = 12; + + static const uint32_t ZH_TAKEN_WEIGHT = 20; + static const uint32_t ZH_NONTAKEN_WEIGHT = 12; // Standard weight value. Used when none of the heuristics set weight for // the edge. - static const unsigned int NORMAL_WEIGHT = 16; + static const uint32_t NORMAL_WEIGHT = 16; // Minimum weight of an edge. Please note, that weight is NEVER 0. - static const unsigned int MIN_WEIGHT = 1; + static const uint32_t MIN_WEIGHT = 1; // Return TRUE if BB leads directly to a Return Instruction. static bool isReturningBlock(BasicBlock *BB) { @@ -98,84 +110,90 @@ class BranchProbabilityAnalysis { return false; } - // Multiply Edge Weight by two. - void incEdgeWeight(BasicBlock *Src, BasicBlock *Dst) { - unsigned Weight = BP->getEdgeWeight(Src, Dst); - unsigned MaxWeight = getMaxWeightFor(Src); - - if (Weight * 2 > MaxWeight) - BP->setEdgeWeight(Src, Dst, MaxWeight); - else - BP->setEdgeWeight(Src, Dst, Weight * 2); - } - - // Divide Edge Weight by two. - void decEdgeWeight(BasicBlock *Src, BasicBlock *Dst) { - unsigned Weight = BP->getEdgeWeight(Src, Dst); - - assert(Weight > 0); - if (Weight / 2 < MIN_WEIGHT) - BP->setEdgeWeight(Src, Dst, MIN_WEIGHT); - else - BP->setEdgeWeight(Src, Dst, Weight / 2); - } - - - unsigned getMaxWeightFor(BasicBlock *BB) const { - return UINT_MAX / BB->getTerminator()->getNumSuccessors(); + uint32_t getMaxWeightFor(BasicBlock *BB) const { + return UINT32_MAX / BB->getTerminator()->getNumSuccessors(); } public: - BranchProbabilityAnalysis(DenseMap *W, + BranchProbabilityAnalysis(DenseMap *W, BranchProbabilityInfo *BP, LoopInfo *LI) : Weights(W), BP(BP), LI(LI) { } // Return Heuristics - void calcReturnHeuristics(BasicBlock *BB); + bool calcReturnHeuristics(BasicBlock *BB); // Pointer Heuristics - void calcPointerHeuristics(BasicBlock *BB); + bool calcPointerHeuristics(BasicBlock *BB); // Loop Branch Heuristics - void calcLoopBranchHeuristics(BasicBlock *BB); + bool calcLoopBranchHeuristics(BasicBlock *BB); + + // Zero Heurestics + bool calcZeroHeuristics(BasicBlock *BB); bool runOnFunction(Function &F); }; +} // end anonymous namespace // Calculate Edge Weights using "Return Heuristics". Predict a successor which // leads directly to Return Instruction will not be taken. -void BranchProbabilityAnalysis::calcReturnHeuristics(BasicBlock *BB){ +bool BranchProbabilityAnalysis::calcReturnHeuristics(BasicBlock *BB){ if (BB->getTerminator()->getNumSuccessors() == 1) - return; + return false; + + SmallPtrSet ReturningEdges; + SmallPtrSet StayEdges; for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) { BasicBlock *Succ = *I; - if (isReturningBlock(Succ)) { - decEdgeWeight(BB, Succ); + if (isReturningBlock(Succ)) + ReturningEdges.insert(Succ); + else + StayEdges.insert(Succ); + } + + if (uint32_t numStayEdges = StayEdges.size()) { + uint32_t stayWeight = RH_TAKEN_WEIGHT / numStayEdges; + if (stayWeight < NORMAL_WEIGHT) + stayWeight = NORMAL_WEIGHT; + + for (SmallPtrSet::iterator I = StayEdges.begin(), + E = StayEdges.end(); I != E; ++I) + BP->setEdgeWeight(BB, *I, stayWeight); + } + + if (uint32_t numRetEdges = ReturningEdges.size()) { + uint32_t retWeight = RH_NONTAKEN_WEIGHT / numRetEdges; + if (retWeight < MIN_WEIGHT) + retWeight = MIN_WEIGHT; + for (SmallPtrSet::iterator I = ReturningEdges.begin(), + E = ReturningEdges.end(); I != E; ++I) { + BP->setEdgeWeight(BB, *I, retWeight); } } + + return ReturningEdges.size() > 0; } // Calculate Edge Weights using "Pointer Heuristics". Predict a comparsion // between two pointer or pointer and NULL will fail. -void BranchProbabilityAnalysis::calcPointerHeuristics(BasicBlock *BB) { +bool BranchProbabilityAnalysis::calcPointerHeuristics(BasicBlock *BB) { BranchInst * BI = dyn_cast(BB->getTerminator()); if (!BI || !BI->isConditional()) - return; + return false; Value *Cond = BI->getCondition(); ICmpInst *CI = dyn_cast(Cond); - if (!CI) - return; + if (!CI || !CI->isEquality()) + return false; Value *LHS = CI->getOperand(0); - Value *RHS = CI->getOperand(1); if (!LHS->getType()->isPointerTy()) - return; + return false; - assert(RHS->getType()->isPointerTy()); + assert(CI->getOperand(1)->getType()->isPointerTy()); BasicBlock *Taken = BI->getSuccessor(0); BasicBlock *NonTaken = BI->getSuccessor(1); @@ -184,112 +202,209 @@ void BranchProbabilityAnalysis::calcPointerHeuristics(BasicBlock *BB) { // p == 0 -> isProb = false // p != q -> isProb = true // p == q -> isProb = false; - bool isProb = !CI->isEquality(); + bool isProb = CI->getPredicate() == ICmpInst::ICMP_NE; if (!isProb) std::swap(Taken, NonTaken); - incEdgeWeight(BB, Taken); - decEdgeWeight(BB, NonTaken); + BP->setEdgeWeight(BB, Taken, PH_TAKEN_WEIGHT); + BP->setEdgeWeight(BB, NonTaken, PH_NONTAKEN_WEIGHT); + return true; } // Calculate Edge Weights using "Loop Branch Heuristics". Predict backedges // as taken, exiting edges as not-taken. -void BranchProbabilityAnalysis::calcLoopBranchHeuristics(BasicBlock *BB) { - unsigned numSuccs = BB->getTerminator()->getNumSuccessors(); +bool BranchProbabilityAnalysis::calcLoopBranchHeuristics(BasicBlock *BB) { + uint32_t numSuccs = BB->getTerminator()->getNumSuccessors(); Loop *L = LI->getLoopFor(BB); if (!L) - return; + return false; - SmallVector BackEdges; - SmallVector ExitingEdges; + SmallPtrSet BackEdges; + SmallPtrSet ExitingEdges; + SmallPtrSet InEdges; // Edges from header to the loop. + + bool isHeader = BB == L->getHeader(); for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) { BasicBlock *Succ = *I; Loop *SuccL = LI->getLoopFor(Succ); if (SuccL != L) - ExitingEdges.push_back(Succ); + ExitingEdges.insert(Succ); else if (Succ == L->getHeader()) - BackEdges.push_back(Succ); + BackEdges.insert(Succ); + else if (isHeader) + InEdges.insert(Succ); } - if (unsigned numBackEdges = BackEdges.size()) { - unsigned backWeight = LBH_TAKEN_WEIGHT / numBackEdges; + 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 (SmallPtrSet::iterator EI = BackEdges.begin(), EE = BackEdges.end(); EI != EE; ++EI) { BasicBlock *Back = *EI; BP->setEdgeWeight(BB, Back, backWeight); } } - unsigned numExitingEdges = ExitingEdges.size(); - if (unsigned numNonExitingEdges = numSuccs - numExitingEdges) { - unsigned exitWeight = LBH_NONTAKEN_WEIGHT / numNonExitingEdges; + if (uint32_t numInEdges = InEdges.size()) { + uint32_t inWeight = LBH_TAKEN_WEIGHT / numInEdges; + if (inWeight < NORMAL_WEIGHT) + inWeight = NORMAL_WEIGHT; + + for (SmallPtrSet::iterator EI = InEdges.begin(), + EE = InEdges.end(); EI != EE; ++EI) { + BasicBlock *Back = *EI; + BP->setEdgeWeight(BB, Back, inWeight); + } + } + + uint32_t numExitingEdges = ExitingEdges.size(); + if (uint32_t numNonExitingEdges = numSuccs - numExitingEdges) { + uint32_t exitWeight = LBH_NONTAKEN_WEIGHT / numNonExitingEdges; if (exitWeight < MIN_WEIGHT) exitWeight = MIN_WEIGHT; - for (SmallVector::iterator EI = ExitingEdges.begin(), + for (SmallPtrSet::iterator EI = ExitingEdges.begin(), EE = ExitingEdges.end(); EI != EE; ++EI) { BasicBlock *Exiting = *EI; BP->setEdgeWeight(BB, Exiting, exitWeight); } } + + return true; } +bool BranchProbabilityAnalysis::calcZeroHeuristics(BasicBlock *BB) { + BranchInst * BI = dyn_cast(BB->getTerminator()); + if (!BI || !BI->isConditional()) + return false; + + Value *Cond = BI->getCondition(); + ICmpInst *CI = dyn_cast(Cond); + if (!CI) + return false; + + Value *RHS = CI->getOperand(1); + ConstantInt *CV = dyn_cast(RHS); + if (!CV) + return false; + + bool isProb; + if (CV->isZero()) { + switch (CI->getPredicate()) { + case CmpInst::ICMP_EQ: + // X == 0 -> Unlikely + isProb = false; + break; + case CmpInst::ICMP_NE: + // X != 0 -> Likely + isProb = true; + break; + case CmpInst::ICMP_SLT: + // X < 0 -> Unlikely + isProb = false; + break; + case CmpInst::ICMP_SGT: + // X > 0 -> Likely + isProb = true; + break; + default: + return false; + } + } else if (CV->isOne() && CI->getPredicate() == CmpInst::ICMP_SLT) { + // 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 { + return false; + } + + BasicBlock *Taken = BI->getSuccessor(0); + BasicBlock *NonTaken = BI->getSuccessor(1); + + if (!isProb) + std::swap(Taken, NonTaken); + + BP->setEdgeWeight(BB, Taken, ZH_TAKEN_WEIGHT); + BP->setEdgeWeight(BB, NonTaken, ZH_NONTAKEN_WEIGHT); + + return true; +} + + bool BranchProbabilityAnalysis::runOnFunction(Function &F) { for (Function::iterator I = F.begin(), E = F.end(); I != E; ) { BasicBlock *BB = I++; - // Only LBH uses setEdgeWeight method. - calcLoopBranchHeuristics(BB); + if (calcLoopBranchHeuristics(BB)) + continue; + + if (calcReturnHeuristics(BB)) + continue; + + if (calcPointerHeuristics(BB)) + continue; - // PH and RH use only incEdgeWeight and decEwdgeWeight methods to - // not efface LBH results. - calcPointerHeuristics(BB); - calcReturnHeuristics(BB); + calcZeroHeuristics(BB); } return false; } +void BranchProbabilityInfo::getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequired(); + AU.setPreservesAll(); +} bool BranchProbabilityInfo::runOnFunction(Function &F) { LoopInfo &LI = getAnalysis(); BranchProbabilityAnalysis BPA(&Weights, this, &LI); - bool ret = BPA.runOnFunction(F); - return ret; + return BPA.runOnFunction(F); } -// TODO: This currently hardcodes 80% as a fraction 4/5. We will soon add a -// BranchProbability class to encapsulate the fractional probability and -// define a few static instances of the class for use as predefined thresholds. -bool BranchProbabilityInfo::isEdgeHot(BasicBlock *Src, BasicBlock *Dst) const { - unsigned Sum = 0; - for (succ_iterator I = succ_begin(Src), E = succ_end(Src); I != E; ++I) { - BasicBlock *Succ = *I; - unsigned Weight = getEdgeWeight(Src, Succ); - unsigned PrevSum = Sum; +uint32_t BranchProbabilityInfo::getSumForBlock(const BasicBlock *BB) const { + uint32_t Sum = 0; + + for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) { + const BasicBlock *Succ = *I; + uint32_t Weight = getEdgeWeight(BB, Succ); + uint32_t PrevSum = Sum; Sum += Weight; assert(Sum > PrevSum); (void) PrevSum; } - return getEdgeWeight(Src, Dst) * 5 > Sum * 4; + return Sum; +} + +bool BranchProbabilityInfo:: +isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const { + // Hot probability is at least 4/5 = 80% + uint32_t Weight = getEdgeWeight(Src, Dst); + uint32_t Sum = getSumForBlock(Src); + + // FIXME: Implement BranchProbability::compare then change this code to + // compare this BranchProbability against a static "hot" BranchProbability. + return (uint64_t)Weight * 5 > (uint64_t)Sum * 4; } BasicBlock *BranchProbabilityInfo::getHotSucc(BasicBlock *BB) const { - unsigned Sum = 0; - unsigned MaxWeight = 0; + uint32_t Sum = 0; + uint32_t MaxWeight = 0; BasicBlock *MaxSucc = 0; for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) { BasicBlock *Succ = *I; - unsigned Weight = getEdgeWeight(BB, Succ); - unsigned PrevSum = Sum; + uint32_t Weight = getEdgeWeight(BB, Succ); + uint32_t PrevSum = Sum; Sum += Weight; assert(Sum > PrevSum); (void) PrevSum; @@ -300,17 +415,18 @@ BasicBlock *BranchProbabilityInfo::getHotSucc(BasicBlock *BB) const { } } - if (MaxWeight * 5 > Sum * 4) + // FIXME: Use BranchProbability::compare. + if ((uint64_t)MaxWeight * 5 > (uint64_t)Sum * 4) return MaxSucc; return 0; } // Return edge's weight. If can't find it, return DEFAULT_WEIGHT value. -unsigned -BranchProbabilityInfo::getEdgeWeight(BasicBlock *Src, BasicBlock *Dst) const { +uint32_t BranchProbabilityInfo:: +getEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst) const { Edge E(Src, Dst); - DenseMap::const_iterator I = Weights.find(E); + DenseMap::const_iterator I = Weights.find(E); if (I != Weights.end()) return I->second; @@ -318,31 +434,32 @@ BranchProbabilityInfo::getEdgeWeight(BasicBlock *Src, BasicBlock *Dst) const { return DEFAULT_WEIGHT; } -void BranchProbabilityInfo::setEdgeWeight(BasicBlock *Src, BasicBlock *Dst, - unsigned Weight) { +void BranchProbabilityInfo:: +setEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst, uint32_t Weight) { Weights[std::make_pair(Src, Dst)] = Weight; - DEBUG(dbgs() << "setEdgeWeight: " << Src->getNameStr() << " -> " - << Dst->getNameStr() << " to " << Weight - << (isEdgeHot(Src, Dst) ? " [is HOT now]\n" : "\n")); + DEBUG(dbgs() << "set edge " << Src->getNameStr() << " -> " + << Dst->getNameStr() << " weight to " << Weight + << (isEdgeHot(Src, Dst) ? " [is HOT now]\n" : "\n")); } -raw_ostream & -BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS, BasicBlock *Src, - BasicBlock *Dst) const { - unsigned Sum = 0; - for (succ_iterator I = succ_begin(Src), E = succ_end(Src); I != E; ++I) { - BasicBlock *Succ = *I; - unsigned Weight = getEdgeWeight(Src, Succ); - unsigned PrevSum = Sum; +BranchProbability BranchProbabilityInfo:: +getEdgeProbability(const BasicBlock *Src, const BasicBlock *Dst) const { - Sum += Weight; - assert(Sum > PrevSum); (void) PrevSum; - } + uint32_t N = getEdgeWeight(Src, Dst); + uint32_t D = getSumForBlock(Src); + + return BranchProbability(N, D); +} + +raw_ostream & +BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS, BasicBlock *Src, + BasicBlock *Dst) const { - double Prob = (double)getEdgeWeight(Src, Dst) / Sum; - OS << "probability (" << Src->getNameStr() << " --> " << Dst->getNameStr() - << ") = " << Prob << "\n"; + const BranchProbability Prob = getEdgeProbability(Src, Dst); + OS << "edge " << Src->getNameStr() << " -> " << Dst->getNameStr() + << " probability is " << Prob + << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n"); return OS; }