1 //===--- BranchProbabilityInfo.h - Branch Probability Analysis --*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This pass is used to evaluate branch probabilties. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H 15 #define LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H 16 17 #include "llvm/InitializePasses.h" 18 #include "llvm/Pass.h" 19 #include "llvm/ADT/DenseMap.h" 20 #include "llvm/ADT/SmallPtrSet.h" 21 #include "llvm/Support/BranchProbability.h" 22 23 namespace llvm { 24 class LoopInfo; 25 class raw_ostream; 26 27 /// \brief Analysis pass providing branch probability information. 28 /// 29 /// This is a function analysis pass which provides information on the relative 30 /// probabilities of each "edge" in the function's CFG where such an edge is 31 /// defined by a pair of basic blocks. The probability for a given block and 32 /// a successor block are always relative to the probabilities of the other 33 /// successor blocks. Another way of looking at it is that the probabilities 34 /// for a given block B and each of its successors should sum to exactly 35 /// one (100%). 36 class BranchProbabilityInfo : public FunctionPass { 37 public: 38 static char ID; 39 40 BranchProbabilityInfo() : FunctionPass(ID) { 41 initializeBranchProbabilityInfoPass(*PassRegistry::getPassRegistry()); 42 } 43 44 void getAnalysisUsage(AnalysisUsage &AU) const; 45 bool runOnFunction(Function &F); 46 void print(raw_ostream &OS, const Module *M = 0) const; 47 48 /// \brief Get an edge's probability, relative to other out-edges of the Src. 49 /// 50 /// This routine provides access to the fractional probability between zero 51 /// (0%) and one (100%) of this edge executing, relative to other edges 52 /// leaving the 'Src' block. The returned probability is never zero, and can 53 /// only be one if the source block has only one successor. 54 BranchProbability getEdgeProbability(const BasicBlock *Src, 55 const BasicBlock *Dst) const; 56 57 /// \brief Test if an edge is hot relative to other out-edges of the Src. 58 /// 59 /// Check whether this edge out of the source block is 'hot'. We define hot 60 /// as having a relative probability >= 80%. 61 bool isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const; 62 63 /// \brief Retrieve the hot successor of a block if one exists. 64 /// 65 /// Given a basic block, look through its successors and if one exists for 66 /// which \see isEdgeHot would return true, return that successor block. 67 BasicBlock *getHotSucc(BasicBlock *BB) const; 68 69 /// \brief Print an edge's probability. 70 /// 71 /// Retrieves an edge's probability similarly to \see getEdgeProbability, but 72 /// then prints that probability to the provided stream. That stream is then 73 /// returned. 74 raw_ostream &printEdgeProbability(raw_ostream &OS, const BasicBlock *Src, 75 const BasicBlock *Dst) const; 76 77 /// \brief Get the raw edge weight calculated for the block pair. 78 /// 79 /// This returns the raw edge weight. It is guaranteed to fall between 1 and 80 /// UINT32_MAX. Note that the raw edge weight is not meaningful in isolation. 81 /// This interface should be very carefully, and primarily by routines that 82 /// are updating the analysis by later calling setEdgeWeight. 83 uint32_t getEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst) const; 84 85 /// \brief Set the raw edge weight for the block pair. 86 /// 87 /// This allows a pass to explicitly set the edge weight for a block. It can 88 /// be used when updating the CFG to update and preserve the branch 89 /// probability information. Read the implementation of how these edge 90 /// weights are calculated carefully before using! 91 void setEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst, 92 uint32_t Weight); 93 94 private: 95 typedef std::pair<const BasicBlock *, const BasicBlock *> Edge; 96 97 // Default weight value. Used when we don't have information about the edge. 98 // TODO: DEFAULT_WEIGHT makes sense during static predication, when none of 99 // the successors have a weight yet. But it doesn't make sense when providing 100 // weight to an edge that may have siblings with non-zero weights. This can 101 // be handled various ways, but it's probably fine for an edge with unknown 102 // weight to just "inherit" the non-zero weight of an adjacent successor. 103 static const uint32_t DEFAULT_WEIGHT = 16; 104 105 DenseMap<Edge, uint32_t> Weights; 106 107 /// \brief Handle to the LoopInfo analysis. 108 LoopInfo *LI; 109 110 /// \brief Track the last function we run over for printing. 111 Function *LastF; 112 113 /// \brief Track the set of blocks directly succeeded by a returning block. 114 SmallPtrSet<BasicBlock *, 16> PostDominatedByUnreachable; 115 116 /// \brief Get sum of the block successors' weights. 117 uint32_t getSumForBlock(const BasicBlock *BB) const; 118 119 bool calcUnreachableHeuristics(BasicBlock *BB); 120 bool calcMetadataWeights(BasicBlock *BB); 121 bool calcPointerHeuristics(BasicBlock *BB); 122 bool calcLoopBranchHeuristics(BasicBlock *BB); 123 bool calcZeroHeuristics(BasicBlock *BB); 124 bool calcFloatingPointHeuristics(BasicBlock *BB); 125 }; 126 127 } 128 129 #endif 130
