X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FBranchProbabilityInfo.cpp;h=9c54a7eadd491a20acb96d2f8ee29a6688e506ed;hb=50fa74e8d2f2ac15a60d008a78649b83e1615d8f;hp=bdea338f21d04a39864cfdca13c1c3a699b891eb;hpb=e0058b4b0c4d162a3b3ff2ad8a87c979928ba016;p=oota-llvm.git diff --git a/lib/Analysis/BranchProbabilityInfo.cpp b/lib/Analysis/BranchProbabilityInfo.cpp index bdea338f21d..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; @@ -72,6 +73,9 @@ class BranchProbabilityAnalysis { 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; @@ -125,6 +129,9 @@ public: // Loop Branch Heuristics bool calcLoopBranchHeuristics(BasicBlock *BB); + // Zero Heurestics + bool calcZeroHeuristics(BasicBlock *BB); + bool runOnFunction(Function &F); }; } // end anonymous namespace @@ -135,15 +142,15 @@ bool BranchProbabilityAnalysis::calcReturnHeuristics(BasicBlock *BB){ if (BB->getTerminator()->getNumSuccessors() == 1) return false; - SmallVector ReturningEdges; - SmallVector StayEdges; + SmallPtrSet ReturningEdges; + SmallPtrSet StayEdges; for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) { BasicBlock *Succ = *I; if (isReturningBlock(Succ)) - ReturningEdges.push_back(Succ); + ReturningEdges.insert(Succ); else - StayEdges.push_back(Succ); + StayEdges.insert(Succ); } if (uint32_t numStayEdges = StayEdges.size()) { @@ -151,7 +158,7 @@ bool BranchProbabilityAnalysis::calcReturnHeuristics(BasicBlock *BB){ if (stayWeight < NORMAL_WEIGHT) stayWeight = NORMAL_WEIGHT; - for (SmallVector::iterator I = StayEdges.begin(), + for (SmallPtrSet::iterator I = StayEdges.begin(), E = StayEdges.end(); I != E; ++I) BP->setEdgeWeight(BB, *I, stayWeight); } @@ -160,7 +167,7 @@ bool BranchProbabilityAnalysis::calcReturnHeuristics(BasicBlock *BB){ uint32_t retWeight = RH_NONTAKEN_WEIGHT / numRetEdges; if (retWeight < MIN_WEIGHT) retWeight = MIN_WEIGHT; - for (SmallVector::iterator I = ReturningEdges.begin(), + for (SmallPtrSet::iterator I = ReturningEdges.begin(), E = ReturningEdges.end(); I != E; ++I) { BP->setEdgeWeight(BB, *I, retWeight); } @@ -213,9 +220,9 @@ bool BranchProbabilityAnalysis::calcLoopBranchHeuristics(BasicBlock *BB) { if (!L) return false; - SmallVector BackEdges; - SmallVector ExitingEdges; - SmallVector InEdges; // Edges from header to the loop. + SmallPtrSet BackEdges; + SmallPtrSet ExitingEdges; + SmallPtrSet InEdges; // Edges from header to the loop. bool isHeader = BB == L->getHeader(); @@ -223,11 +230,11 @@ bool BranchProbabilityAnalysis::calcLoopBranchHeuristics(BasicBlock *BB) { 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.push_back(Succ); + InEdges.insert(Succ); } if (uint32_t numBackEdges = BackEdges.size()) { @@ -235,7 +242,7 @@ bool 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); @@ -247,7 +254,7 @@ bool BranchProbabilityAnalysis::calcLoopBranchHeuristics(BasicBlock *BB) { if (inWeight < NORMAL_WEIGHT) inWeight = NORMAL_WEIGHT; - for (SmallVector::iterator EI = InEdges.begin(), + for (SmallPtrSet::iterator EI = InEdges.begin(), EE = InEdges.end(); EI != EE; ++EI) { BasicBlock *Back = *EI; BP->setEdgeWeight(BB, Back, inWeight); @@ -260,7 +267,7 @@ bool BranchProbabilityAnalysis::calcLoopBranchHeuristics(BasicBlock *BB) { 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); @@ -270,21 +277,83 @@ bool BranchProbabilityAnalysis::calcLoopBranchHeuristics(BasicBlock *BB) { 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. if (calcLoopBranchHeuristics(BB)) continue; - // PH and RH use only incEdgeWeight and decEwdgeWeight methods to - // not efface LBH results. if (calcReturnHeuristics(BB)) continue; - calcPointerHeuristics(BB); + if (calcPointerHeuristics(BB)) + continue; + + calcZeroHeuristics(BB); } return false; @@ -301,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; @@ -316,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); @@ -353,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); @@ -364,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 @@ -374,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);