//
//===----------------------------------------------------------------------===//
+#include "llvm/Constants.h"
#include "llvm/Instructions.h"
#include "llvm/Analysis/BranchProbabilityInfo.h"
#include "llvm/Analysis/LoopInfo.h"
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;
// Loop Branch Heuristics
bool calcLoopBranchHeuristics(BasicBlock *BB);
+ // Zero Heurestics
+ bool calcZeroHeuristics(BasicBlock *BB);
+
bool runOnFunction(Function &F);
};
} // end anonymous namespace
if (BB->getTerminator()->getNumSuccessors() == 1)
return false;
- SmallVector<BasicBlock *, 4> ReturningEdges;
- SmallVector<BasicBlock *, 4> StayEdges;
+ SmallPtrSet<BasicBlock *, 4> ReturningEdges;
+ SmallPtrSet<BasicBlock *, 4> 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()) {
if (stayWeight < NORMAL_WEIGHT)
stayWeight = NORMAL_WEIGHT;
- for (SmallVector<BasicBlock *, 4>::iterator I = StayEdges.begin(),
+ for (SmallPtrSet<BasicBlock *, 4>::iterator I = StayEdges.begin(),
E = StayEdges.end(); I != E; ++I)
BP->setEdgeWeight(BB, *I, stayWeight);
}
uint32_t retWeight = RH_NONTAKEN_WEIGHT / numRetEdges;
if (retWeight < MIN_WEIGHT)
retWeight = MIN_WEIGHT;
- for (SmallVector<BasicBlock *, 4>::iterator I = ReturningEdges.begin(),
+ for (SmallPtrSet<BasicBlock *, 4>::iterator I = ReturningEdges.begin(),
E = ReturningEdges.end(); I != E; ++I) {
BP->setEdgeWeight(BB, *I, retWeight);
}
if (!L)
return false;
- SmallVector<BasicBlock *, 8> BackEdges;
- SmallVector<BasicBlock *, 8> ExitingEdges;
- SmallVector<BasicBlock *, 8> InEdges; // Edges from header to the loop.
+ SmallPtrSet<BasicBlock *, 8> BackEdges;
+ SmallPtrSet<BasicBlock *, 8> ExitingEdges;
+ SmallPtrSet<BasicBlock *, 8> InEdges; // Edges from header to the loop.
bool isHeader = BB == L->getHeader();
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()) {
if (backWeight < NORMAL_WEIGHT)
backWeight = NORMAL_WEIGHT;
- for (SmallVector<BasicBlock *, 8>::iterator EI = BackEdges.begin(),
+ for (SmallPtrSet<BasicBlock *, 8>::iterator EI = BackEdges.begin(),
EE = BackEdges.end(); EI != EE; ++EI) {
BasicBlock *Back = *EI;
BP->setEdgeWeight(BB, Back, backWeight);
if (inWeight < NORMAL_WEIGHT)
inWeight = NORMAL_WEIGHT;
- for (SmallVector<BasicBlock *, 8>::iterator EI = InEdges.begin(),
+ for (SmallPtrSet<BasicBlock *, 8>::iterator EI = InEdges.begin(),
EE = InEdges.end(); EI != EE; ++EI) {
BasicBlock *Back = *EI;
BP->setEdgeWeight(BB, Back, inWeight);
if (exitWeight < MIN_WEIGHT)
exitWeight = MIN_WEIGHT;
- for (SmallVector<BasicBlock *, 8>::iterator EI = ExitingEdges.begin(),
+ for (SmallPtrSet<BasicBlock *, 8>::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<BranchInst>(BB->getTerminator());
+ if (!BI || !BI->isConditional())
+ return false;
+
+ Value *Cond = BI->getCondition();
+ ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
+ if (!CI)
+ return false;
+
+ Value *RHS = CI->getOperand(1);
+ ConstantInt *CV = dyn_cast<ConstantInt>(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;