diff options
| -rw-r--r-- | include/llvm/Analysis/BranchProbabilityInfo.h | 68 | ||||
| -rw-r--r-- | include/llvm/InitializePasses.h | 1 | ||||
| -rw-r--r-- | lib/Analysis/Analysis.cpp | 1 | ||||
| -rw-r--r-- | lib/Analysis/BranchProbabilityInfo.cpp | 348 | ||||
| -rw-r--r-- | lib/Analysis/CMakeLists.txt | 1 |
5 files changed, 419 insertions, 0 deletions
diff --git a/include/llvm/Analysis/BranchProbabilityInfo.h b/include/llvm/Analysis/BranchProbabilityInfo.h new file mode 100644 index 0000000..bf2a6a7 --- /dev/null +++ b/include/llvm/Analysis/BranchProbabilityInfo.h @@ -0,0 +1,68 @@ +//===--- BranchProbabilityInfo.h - Branch Probability Analysis --*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass is used to evaluate branch probabilties. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H +#define LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H + +#include "llvm/InitializePasses.h" +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Support/Debug.h" + +namespace llvm { + +class BranchProbabilityInfo : public FunctionPass { + + // Default weight value. Used when we don't have information about the edge. + static const unsigned int DEFAULT_WEIGHT = 16; + + typedef std::pair<BasicBlock *, BasicBlock *> Edge; + + DenseMap<Edge, unsigned> Weights; + +public: + static char ID; + + BranchProbabilityInfo() : FunctionPass(ID) { + initializeBranchProbabilityInfoPass(*PassRegistry::getPassRegistry()); + } + + void getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequired<LoopInfo>(); + AU.setPreservesAll(); + } + + bool runOnFunction(Function &F); + + // Returned value is between 1 and UINT_MAX. Look at BranchProbabilityInfo.cpp + // for details. + unsigned getEdgeWeight(BasicBlock *Src, BasicBlock *Dst) const; + + // Look at BranchProbabilityInfo.cpp for details. Use it with caution! + void setEdgeWeight(BasicBlock *Src, BasicBlock *Dst, unsigned Weight); + + // A 'Hot' edge is an edge which probability is >= 80%. + bool isEdgeHot(BasicBlock *Src, BasicBlock *Dst) const; + + // Return a hot successor for the block BB or null if there isn't one. + BasicBlock *getHotSucc(BasicBlock *BB) const; + + // Print value between 0 (0% probability) and 1 (100% probability), + // however the value is never equal to 0, and can be 1 only iff SRC block + // has only one successor. + raw_ostream &printEdgeProbability(raw_ostream &OS, BasicBlock *Src, + BasicBlock *Dst) const; +}; + +} + +#endif diff --git a/include/llvm/InitializePasses.h b/include/llvm/InitializePasses.h index cca0194..372eaba 100644 --- a/include/llvm/InitializePasses.h +++ b/include/llvm/InitializePasses.h @@ -66,6 +66,7 @@ void initializeBasicAliasAnalysisPass(PassRegistry&); void initializeBasicCallGraphPass(PassRegistry&); void initializeBlockExtractorPassPass(PassRegistry&); void initializeBlockPlacementPass(PassRegistry&); +void initializeBranchProbabilityInfoPass(PassRegistry&); void initializeBreakCriticalEdgesPass(PassRegistry&); void initializeCFGOnlyPrinterPass(PassRegistry&); void initializeCFGOnlyViewerPass(PassRegistry&); diff --git a/lib/Analysis/Analysis.cpp b/lib/Analysis/Analysis.cpp index 6ebe100..e57ba78 100644 --- a/lib/Analysis/Analysis.cpp +++ b/lib/Analysis/Analysis.cpp @@ -23,6 +23,7 @@ void llvm::initializeAnalysis(PassRegistry &Registry) { initializeAliasSetPrinterPass(Registry); initializeNoAAPass(Registry); initializeBasicAliasAnalysisPass(Registry); + initializeBranchProbabilityInfoPass(Registry); initializeCFGViewerPass(Registry); initializeCFGPrinterPass(Registry); initializeCFGOnlyViewerPass(Registry); diff --git a/lib/Analysis/BranchProbabilityInfo.cpp b/lib/Analysis/BranchProbabilityInfo.cpp new file mode 100644 index 0000000..57a2579 --- /dev/null +++ b/lib/Analysis/BranchProbabilityInfo.cpp @@ -0,0 +1,348 @@ +//===-- BranchProbabilityInfo.cpp - Branch Probability Analysis -*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Loops should be simplified before this analysis. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Instructions.h" +#include "llvm/Analysis/BranchProbabilityInfo.h" + +using namespace llvm; + +INITIALIZE_PASS_BEGIN(BranchProbabilityInfo, "branch-prob", + "Branch Probability Analysis", false, true) +INITIALIZE_PASS_DEPENDENCY(LoopInfo) +INITIALIZE_PASS_END(BranchProbabilityInfo, "branch-prob", + "Branch Probability Analysis", false, true) + +char BranchProbabilityInfo::ID = 0; + + +// 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<BasicBlock *, BasicBlock *> Edge; + + DenseMap<Edge, unsigned> *Weights; + + BranchProbabilityInfo *BP; + + LoopInfo *LI; + + + // Weights are for internal use only. They are used by heuristics to help to + // estimate edges' probability. Example: + // + // Using "Loop Branch Heuristics" we predict weights of edges for the + // block BB2. + // ... + // | + // V + // BB1<-+ + // | | + // | | (Weight = 128) + // V | + // BB2--+ + // | + // | (Weight = 4) + // V + // BB3 + // + // Probability of the edge BB2->BB1 = 128 / (128 + 4) = 0.9696.. + // Probability of the edge BB2->BB3 = 4 / (128 + 4) = 0.0303.. + + static const unsigned int LBH_TAKEN_WEIGHT = 128; + static const unsigned int LBH_NONTAKEN_WEIGHT = 4; + + // Standard weight value. Used when none of the heuristics set weight for + // the edge. + static const unsigned int NORMAL_WEIGHT = 16; + + // Minimum weight of an edge. Please note, that weight is NEVER 0. + static const unsigned int MIN_WEIGHT = 1; + + // Return TRUE if BB leads directly to a Return Instruction. + static bool isReturningBlock(BasicBlock *BB) { + SmallPtrSet<BasicBlock *, 8> Visited; + + while (true) { + TerminatorInst *TI = BB->getTerminator(); + if (isa<ReturnInst>(TI)) + return true; + + if (TI->getNumSuccessors() > 1) + break; + + // It is unreachable block which we can consider as a return instruction. + if (TI->getNumSuccessors() == 0) + return true; + + Visited.insert(BB); + BB = TI->getSuccessor(0); + + // Stop if cycle is detected. + if (Visited.count(BB)) + return false; + } + + 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(); + } + +public: + BranchProbabilityAnalysis(DenseMap<Edge, unsigned> *W, + BranchProbabilityInfo *BP, LoopInfo *LI) + : Weights(W), BP(BP), LI(LI) { + } + + // Return Heuristics + void calcReturnHeuristics(BasicBlock *BB); + + // Pointer Heuristics + void calcPointerHeuristics(BasicBlock *BB); + + // Loop Branch Heuristics + void calcLoopBranchHeuristics(BasicBlock *BB); + + bool runOnFunction(Function &F); +}; + +// Calculate Edge Weights using "Return Heuristics". Predict a successor which +// leads directly to Return Instruction will not be taken. +void BranchProbabilityAnalysis::calcReturnHeuristics(BasicBlock *BB){ + if (BB->getTerminator()->getNumSuccessors() == 1) + return; + + for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) { + BasicBlock *Succ = *I; + if (isReturningBlock(Succ)) { + decEdgeWeight(BB, Succ); + } + } +} + +// Calculate Edge Weights using "Pointer Heuristics". Predict a comparsion +// between two pointer or pointer and NULL will fail. +void BranchProbabilityAnalysis::calcPointerHeuristics(BasicBlock *BB) { + BranchInst * BI = dyn_cast<BranchInst>(BB->getTerminator()); + if (!BI || !BI->isConditional()) + return; + + Value *Cond = BI->getCondition(); + ICmpInst *CI = dyn_cast<ICmpInst>(Cond); + if (!CI) + return; + + Value *LHS = CI->getOperand(0); + Value *RHS = CI->getOperand(1); + + if (!LHS->getType()->isPointerTy()) + return; + + assert(RHS->getType()->isPointerTy()); + + BasicBlock *Taken = BI->getSuccessor(0); + BasicBlock *NonTaken = BI->getSuccessor(1); + + // p != 0 -> isProb = true + // p == 0 -> isProb = false + // p != q -> isProb = true + // p == q -> isProb = false; + bool isProb = !CI->isEquality(); + if (!isProb) + std::swap(Taken, NonTaken); + + incEdgeWeight(BB, Taken); + decEdgeWeight(BB, NonTaken); +} + +// 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(); + + Loop *L = LI->getLoopFor(BB); + if (!L) + return; + + SmallVector<BasicBlock *, 8> BackEdges; + SmallVector<BasicBlock *, 8> ExitingEdges; + + 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); + else if (Succ == L->getHeader()) + BackEdges.push_back(Succ); + } + + if (unsigned numBackEdges = BackEdges.size()) { + unsigned backWeight = LBH_TAKEN_WEIGHT / numBackEdges; + if (backWeight < NORMAL_WEIGHT) + backWeight = NORMAL_WEIGHT; + + for (SmallVector<BasicBlock *, 8>::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 (exitWeight < MIN_WEIGHT) + exitWeight = MIN_WEIGHT; + + for (SmallVector<BasicBlock *, 8>::iterator EI = ExitingEdges.begin(), + EE = ExitingEdges.end(); EI != EE; ++EI) { + BasicBlock *Exiting = *EI; + BP->setEdgeWeight(BB, Exiting, exitWeight); + } + } +} + +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); + + // PH and RH use only incEdgeWeight and decEwdgeWeight methods to + // not efface LBH results. + calcPointerHeuristics(BB); + calcReturnHeuristics(BB); + } + + return false; +} + + +bool BranchProbabilityInfo::runOnFunction(Function &F) { + LoopInfo &LI = getAnalysis<LoopInfo>(); + BranchProbabilityAnalysis BPA(&Weights, this, &LI); + bool ret = BPA.runOnFunction(F); + return ret; +} + +// 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; + + Sum += Weight; + assert(Sum > PrevSum); (void) PrevSum; + } + + return getEdgeWeight(Src, Dst) * 5 > Sum * 4; +} + +BasicBlock *BranchProbabilityInfo::getHotSucc(BasicBlock *BB) const { + unsigned Sum = 0; + unsigned 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; + + Sum += Weight; + assert(Sum > PrevSum); (void) PrevSum; + + if (Weight > MaxWeight) { + MaxWeight = Weight; + MaxSucc = Succ; + } + } + + if (MaxWeight * 5 > 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 { + Edge E(Src, Dst); + DenseMap<Edge, unsigned>::const_iterator I = Weights.find(E); + + if (I != Weights.end()) + return I->second; + + return DEFAULT_WEIGHT; +} + +void BranchProbabilityInfo::setEdgeWeight(BasicBlock *Src, BasicBlock *Dst, + unsigned 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")); +} + +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; + + Sum += Weight; + assert(Sum > PrevSum); (void) PrevSum; + } + + double Prob = (double)getEdgeWeight(Src, Dst) / Sum; + OS << "probability (" << Src->getNameStr() << " --> " << Dst->getNameStr() + << ") = " << Prob << "\n"; + + return OS; +} diff --git a/lib/Analysis/CMakeLists.txt b/lib/Analysis/CMakeLists.txt index 6be5617..1a975bf 100644 --- a/lib/Analysis/CMakeLists.txt +++ b/lib/Analysis/CMakeLists.txt @@ -6,6 +6,7 @@ add_llvm_library(LLVMAnalysis AliasSetTracker.cpp Analysis.cpp BasicAliasAnalysis.cpp + BranchProbabilityInfo.cpp CFGPrinter.cpp CaptureTracking.cpp ConstantFolding.cpp |