1223013Sdim//===--- BranchProbabilityInfo.h - Branch Probability Analysis --*- C++ -*-===// 2223013Sdim// 3223013Sdim// The LLVM Compiler Infrastructure 4223013Sdim// 5223013Sdim// This file is distributed under the University of Illinois Open Source 6223013Sdim// License. See LICENSE.TXT for details. 7223013Sdim// 8223013Sdim//===----------------------------------------------------------------------===// 9223013Sdim// 10223013Sdim// This pass is used to evaluate branch probabilties. 11223013Sdim// 12223013Sdim//===----------------------------------------------------------------------===// 13223013Sdim 14223013Sdim#ifndef LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H 15223013Sdim#define LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H 16223013Sdim 17249423Sdim#include "llvm/ADT/DenseMap.h" 18249423Sdim#include "llvm/ADT/SmallPtrSet.h" 19223013Sdim#include "llvm/InitializePasses.h" 20224145Sdim#include "llvm/Pass.h" 21223013Sdim#include "llvm/Support/BranchProbability.h" 22223013Sdim 23223013Sdimnamespace llvm { 24234353Sdimclass LoopInfo; 25223013Sdimclass raw_ostream; 26223013Sdim 27234353Sdim/// \brief Analysis pass providing branch probability information. 28234353Sdim/// 29234353Sdim/// This is a function analysis pass which provides information on the relative 30234353Sdim/// probabilities of each "edge" in the function's CFG where such an edge is 31243830Sdim/// defined by a pair (PredBlock and an index in the successors). The 32243830Sdim/// probability of an edge from one block is always relative to the 33243830Sdim/// probabilities of other edges from the block. The probabilites of all edges 34243830Sdim/// from a block sum to exactly one (100%). 35243830Sdim/// We use a pair (PredBlock and an index in the successors) to uniquely 36243830Sdim/// identify an edge, since we can have multiple edges from Src to Dst. 37243830Sdim/// As an example, we can have a switch which jumps to Dst with value 0 and 38243830Sdim/// value 10. 39223013Sdimclass BranchProbabilityInfo : public FunctionPass { 40223013Sdimpublic: 41223013Sdim static char ID; 42223013Sdim 43223013Sdim BranchProbabilityInfo() : FunctionPass(ID) { 44223013Sdim initializeBranchProbabilityInfoPass(*PassRegistry::getPassRegistry()); 45223013Sdim } 46223013Sdim 47224145Sdim void getAnalysisUsage(AnalysisUsage &AU) const; 48223013Sdim bool runOnFunction(Function &F); 49234353Sdim void print(raw_ostream &OS, const Module *M = 0) const; 50223013Sdim 51234353Sdim /// \brief Get an edge's probability, relative to other out-edges of the Src. 52234353Sdim /// 53234353Sdim /// This routine provides access to the fractional probability between zero 54234353Sdim /// (0%) and one (100%) of this edge executing, relative to other edges 55234353Sdim /// leaving the 'Src' block. The returned probability is never zero, and can 56234353Sdim /// only be one if the source block has only one successor. 57234353Sdim BranchProbability getEdgeProbability(const BasicBlock *Src, 58243830Sdim unsigned IndexInSuccessors) const; 59243830Sdim 60243830Sdim /// \brief Get the probability of going from Src to Dst. 61243830Sdim /// 62243830Sdim /// It returns the sum of all probabilities for edges from Src to Dst. 63243830Sdim BranchProbability getEdgeProbability(const BasicBlock *Src, 64234353Sdim const BasicBlock *Dst) const; 65234353Sdim 66234353Sdim /// \brief Test if an edge is hot relative to other out-edges of the Src. 67234353Sdim /// 68234353Sdim /// Check whether this edge out of the source block is 'hot'. We define hot 69234353Sdim /// as having a relative probability >= 80%. 70234353Sdim bool isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const; 71234353Sdim 72234353Sdim /// \brief Retrieve the hot successor of a block if one exists. 73234353Sdim /// 74234353Sdim /// Given a basic block, look through its successors and if one exists for 75234353Sdim /// which \see isEdgeHot would return true, return that successor block. 76234353Sdim BasicBlock *getHotSucc(BasicBlock *BB) const; 77234353Sdim 78234353Sdim /// \brief Print an edge's probability. 79234353Sdim /// 80234353Sdim /// Retrieves an edge's probability similarly to \see getEdgeProbability, but 81234353Sdim /// then prints that probability to the provided stream. That stream is then 82234353Sdim /// returned. 83234353Sdim raw_ostream &printEdgeProbability(raw_ostream &OS, const BasicBlock *Src, 84234353Sdim const BasicBlock *Dst) const; 85234353Sdim 86243830Sdim /// \brief Get the raw edge weight calculated for the edge. 87234353Sdim /// 88234353Sdim /// This returns the raw edge weight. It is guaranteed to fall between 1 and 89234353Sdim /// UINT32_MAX. Note that the raw edge weight is not meaningful in isolation. 90234353Sdim /// This interface should be very carefully, and primarily by routines that 91234353Sdim /// are updating the analysis by later calling setEdgeWeight. 92243830Sdim uint32_t getEdgeWeight(const BasicBlock *Src, 93243830Sdim unsigned IndexInSuccessors) const; 94243830Sdim 95243830Sdim /// \brief Get the raw edge weight calculated for the block pair. 96243830Sdim /// 97243830Sdim /// This returns the sum of all raw edge weights from Src to Dst. 98243830Sdim /// It is guaranteed to fall between 1 and UINT32_MAX. 99226633Sdim uint32_t getEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst) const; 100223013Sdim 101243830Sdim /// \brief Set the raw edge weight for a given edge. 102234353Sdim /// 103243830Sdim /// This allows a pass to explicitly set the edge weight for an edge. It can 104234353Sdim /// be used when updating the CFG to update and preserve the branch 105234353Sdim /// probability information. Read the implementation of how these edge 106234353Sdim /// weights are calculated carefully before using! 107243830Sdim void setEdgeWeight(const BasicBlock *Src, unsigned IndexInSuccessors, 108226633Sdim uint32_t Weight); 109223013Sdim 110234353Sdimprivate: 111243830Sdim // Since we allow duplicate edges from one basic block to another, we use 112243830Sdim // a pair (PredBlock and an index in the successors) to specify an edge. 113243830Sdim typedef std::pair<const BasicBlock *, unsigned> Edge; 114223013Sdim 115234353Sdim // Default weight value. Used when we don't have information about the edge. 116234353Sdim // TODO: DEFAULT_WEIGHT makes sense during static predication, when none of 117234353Sdim // the successors have a weight yet. But it doesn't make sense when providing 118234353Sdim // weight to an edge that may have siblings with non-zero weights. This can 119234353Sdim // be handled various ways, but it's probably fine for an edge with unknown 120234353Sdim // weight to just "inherit" the non-zero weight of an adjacent successor. 121234353Sdim static const uint32_t DEFAULT_WEIGHT = 16; 122223013Sdim 123234353Sdim DenseMap<Edge, uint32_t> Weights; 124223013Sdim 125234353Sdim /// \brief Handle to the LoopInfo analysis. 126234353Sdim LoopInfo *LI; 127234353Sdim 128234353Sdim /// \brief Track the last function we run over for printing. 129234353Sdim Function *LastF; 130234353Sdim 131234353Sdim /// \brief Track the set of blocks directly succeeded by a returning block. 132234353Sdim SmallPtrSet<BasicBlock *, 16> PostDominatedByUnreachable; 133234353Sdim 134263508Sdim /// \brief Track the set of blocks that always lead to a cold call. 135263508Sdim SmallPtrSet<BasicBlock *, 16> PostDominatedByColdCall; 136263508Sdim 137234353Sdim /// \brief Get sum of the block successors' weights. 138234353Sdim uint32_t getSumForBlock(const BasicBlock *BB) const; 139234353Sdim 140234353Sdim bool calcUnreachableHeuristics(BasicBlock *BB); 141234353Sdim bool calcMetadataWeights(BasicBlock *BB); 142263508Sdim bool calcColdCallHeuristics(BasicBlock *BB); 143234353Sdim bool calcPointerHeuristics(BasicBlock *BB); 144234353Sdim bool calcLoopBranchHeuristics(BasicBlock *BB); 145234353Sdim bool calcZeroHeuristics(BasicBlock *BB); 146234353Sdim bool calcFloatingPointHeuristics(BasicBlock *BB); 147239462Sdim bool calcInvokeHeuristics(BasicBlock *BB); 148223013Sdim}; 149223013Sdim 150223013Sdim} 151223013Sdim 152223013Sdim#endif 153