X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FBranchProbabilityInfo.cpp;h=9c54a7eadd491a20acb96d2f8ee29a6688e506ed;hb=6053cd956fa6c781a4ee05cbc99ab15db3cf3d13;hp=e39cd221b5a70a02fde274833d11a8fd1465fad8;hpb=12af93ae86cb4a517d1b67f9363fbf21f24f583b;p=oota-llvm.git diff --git a/lib/Analysis/BranchProbabilityInfo.cpp b/lib/Analysis/BranchProbabilityInfo.cpp index e39cd221b5a..9c54a7eadd4 100644 --- a/lib/Analysis/BranchProbabilityInfo.cpp +++ b/lib/Analysis/BranchProbabilityInfo.cpp @@ -11,6 +11,7 @@ // //===----------------------------------------------------------------------===// +#include "llvm/Constants.h" #include "llvm/Instructions.h" #include "llvm/Analysis/BranchProbabilityInfo.h" #include "llvm/Analysis/LoopInfo.h" @@ -33,7 +34,7 @@ namespace { // private methods are hidden in the .cpp file. class BranchProbabilityAnalysis { - typedef std::pair Edge; + typedef std::pair Edge; DenseMap *Weights; @@ -52,7 +53,7 @@ class BranchProbabilityAnalysis { // V // BB1<-+ // | | - // | | (Weight = 128) + // | | (Weight = 124) // V | // BB2--+ // | @@ -60,12 +61,21 @@ 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 = 128; + 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 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 uint32_t NORMAL_WEIGHT = 16; @@ -100,29 +110,6 @@ class BranchProbabilityAnalysis { return false; } - // Multiply Edge Weight by two. - void incEdgeWeight(BasicBlock *Src, BasicBlock *Dst) { - uint32_t Weight = BP->getEdgeWeight(Src, Dst); - uint32_t 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) { - uint32_t 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); - } - - uint32_t getMaxWeightFor(BasicBlock *BB) const { return UINT32_MAX / BB->getTerminator()->getNumSuccessors(); } @@ -134,13 +121,16 @@ public: } // 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); }; @@ -148,34 +138,60 @@ public: // 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 || !CI->isEquality()) - return; + return false; Value *LHS = CI->getOperand(0); if (!LHS->getType()->isPointerTy()) - return; + return false; assert(CI->getOperand(1)->getType()->isPointerTy()); @@ -190,29 +206,35 @@ void BranchProbabilityAnalysis::calcPointerHeuristics(BasicBlock *BB) { 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) { +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 (uint32_t numBackEdges = BackEdges.size()) { @@ -220,39 +242,118 @@ void BranchProbabilityAnalysis::calcLoopBranchHeuristics(BasicBlock *BB) { 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); } } + 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; - // PH and RH use only incEdgeWeight and decEwdgeWeight methods to - // not efface LBH results. - calcPointerHeuristics(BB); - calcReturnHeuristics(BB); + if (calcPointerHeuristics(BB)) + continue; + + calcZeroHeuristics(BB); } return false; @@ -269,11 +370,11 @@ bool BranchProbabilityInfo::runOnFunction(Function &F) { return BPA.runOnFunction(F); } -uint32_t BranchProbabilityInfo::getSumForBlock(BasicBlock *BB) const { +uint32_t BranchProbabilityInfo::getSumForBlock(const BasicBlock *BB) const { uint32_t Sum = 0; - for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) { - BasicBlock *Succ = *I; + 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; @@ -284,7 +385,8 @@ uint32_t BranchProbabilityInfo::getSumForBlock(BasicBlock *BB) const { return Sum; } -bool BranchProbabilityInfo::isEdgeHot(BasicBlock *Src, BasicBlock *Dst) const { +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); @@ -321,8 +423,8 @@ BasicBlock *BranchProbabilityInfo::getHotSucc(BasicBlock *BB) const { } // Return edge's weight. If can't find it, return DEFAULT_WEIGHT value. -uint32_t -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); @@ -332,8 +434,8 @@ BranchProbabilityInfo::getEdgeWeight(BasicBlock *Src, BasicBlock *Dst) const { return DEFAULT_WEIGHT; } -void BranchProbabilityInfo::setEdgeWeight(BasicBlock *Src, BasicBlock *Dst, - uint32_t Weight) { +void BranchProbabilityInfo:: +setEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst, uint32_t Weight) { Weights[std::make_pair(Src, Dst)] = Weight; DEBUG(dbgs() << "set edge " << Src->getNameStr() << " -> " << Dst->getNameStr() << " weight to " << Weight @@ -342,7 +444,7 @@ void BranchProbabilityInfo::setEdgeWeight(BasicBlock *Src, BasicBlock *Dst, BranchProbability BranchProbabilityInfo:: -getEdgeProbability(BasicBlock *Src, BasicBlock *Dst) const { +getEdgeProbability(const BasicBlock *Src, const BasicBlock *Dst) const { uint32_t N = getEdgeWeight(Src, Dst); uint32_t D = getSumForBlock(Src);