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/ADT/DenseMap.h" 18#include "llvm/ADT/SmallPtrSet.h" 19#include "llvm/InitializePasses.h" 20#include "llvm/Pass.h" 21#include "llvm/Support/BranchProbability.h" 22 23namespace llvm { 24class LoopInfo; 25class 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 (PredBlock and an index in the successors). The 32/// probability of an edge from one block is always relative to the 33/// probabilities of other edges from the block. The probabilites of all edges 34/// from a block sum to exactly one (100%). 35/// We use a pair (PredBlock and an index in the successors) to uniquely 36/// identify an edge, since we can have multiple edges from Src to Dst. 37/// As an example, we can have a switch which jumps to Dst with value 0 and 38/// value 10. 39class BranchProbabilityInfo : public FunctionPass { 40public: 41 static char ID; 42 43 BranchProbabilityInfo() : FunctionPass(ID) { 44 initializeBranchProbabilityInfoPass(*PassRegistry::getPassRegistry()); 45 } 46 47 void getAnalysisUsage(AnalysisUsage &AU) const; 48 bool runOnFunction(Function &F); 49 void print(raw_ostream &OS, const Module *M = 0) const; 50 51 /// \brief Get an edge's probability, relative to other out-edges of the Src. 52 /// 53 /// This routine provides access to the fractional probability between zero 54 /// (0%) and one (100%) of this edge executing, relative to other edges 55 /// leaving the 'Src' block. The returned probability is never zero, and can 56 /// only be one if the source block has only one successor. 57 BranchProbability getEdgeProbability(const BasicBlock *Src, 58 unsigned IndexInSuccessors) const; 59 60 /// \brief Get the probability of going from Src to Dst. 61 /// 62 /// It returns the sum of all probabilities for edges from Src to Dst. 63 BranchProbability getEdgeProbability(const BasicBlock *Src, 64 const BasicBlock *Dst) const; 65 66 /// \brief Test if an edge is hot relative to other out-edges of the Src. 67 /// 68 /// Check whether this edge out of the source block is 'hot'. We define hot 69 /// as having a relative probability >= 80%. 70 bool isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const; 71 72 /// \brief Retrieve the hot successor of a block if one exists. 73 /// 74 /// Given a basic block, look through its successors and if one exists for 75 /// which \see isEdgeHot would return true, return that successor block. 76 BasicBlock *getHotSucc(BasicBlock *BB) const; 77 78 /// \brief Print an edge's probability. 79 /// 80 /// Retrieves an edge's probability similarly to \see getEdgeProbability, but 81 /// then prints that probability to the provided stream. That stream is then 82 /// returned. 83 raw_ostream &printEdgeProbability(raw_ostream &OS, const BasicBlock *Src, 84 const BasicBlock *Dst) const; 85 86 /// \brief Get the raw edge weight calculated for the edge. 87 /// 88 /// This returns the raw edge weight. It is guaranteed to fall between 1 and 89 /// UINT32_MAX. Note that the raw edge weight is not meaningful in isolation. 90 /// This interface should be very carefully, and primarily by routines that 91 /// are updating the analysis by later calling setEdgeWeight. 92 uint32_t getEdgeWeight(const BasicBlock *Src, 93 unsigned IndexInSuccessors) const; 94 95 /// \brief Get the raw edge weight calculated for the block pair. 96 /// 97 /// This returns the sum of all raw edge weights from Src to Dst. 98 /// It is guaranteed to fall between 1 and UINT32_MAX. 99 uint32_t getEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst) const; 100 101 /// \brief Set the raw edge weight for a given edge. 102 /// 103 /// This allows a pass to explicitly set the edge weight for an edge. It can 104 /// be used when updating the CFG to update and preserve the branch 105 /// probability information. Read the implementation of how these edge 106 /// weights are calculated carefully before using! 107 void setEdgeWeight(const BasicBlock *Src, unsigned IndexInSuccessors, 108 uint32_t Weight); 109 110private: 111 // Since we allow duplicate edges from one basic block to another, we use 112 // a pair (PredBlock and an index in the successors) to specify an edge. 113 typedef std::pair<const BasicBlock *, unsigned> Edge; 114 115 // Default weight value. Used when we don't have information about the edge. 116 // TODO: DEFAULT_WEIGHT makes sense during static predication, when none of 117 // the successors have a weight yet. But it doesn't make sense when providing 118 // weight to an edge that may have siblings with non-zero weights. This can 119 // be handled various ways, but it's probably fine for an edge with unknown 120 // weight to just "inherit" the non-zero weight of an adjacent successor. 121 static const uint32_t DEFAULT_WEIGHT = 16; 122 123 DenseMap<Edge, uint32_t> Weights; 124 125 /// \brief Handle to the LoopInfo analysis. 126 LoopInfo *LI; 127 128 /// \brief Track the last function we run over for printing. 129 Function *LastF; 130 131 /// \brief Track the set of blocks directly succeeded by a returning block. 132 SmallPtrSet<BasicBlock *, 16> PostDominatedByUnreachable; 133 134 /// \brief Get sum of the block successors' weights. 135 uint32_t getSumForBlock(const BasicBlock *BB) const; 136 137 bool calcUnreachableHeuristics(BasicBlock *BB); 138 bool calcMetadataWeights(BasicBlock *BB); 139 bool calcPointerHeuristics(BasicBlock *BB); 140 bool calcLoopBranchHeuristics(BasicBlock *BB); 141 bool calcZeroHeuristics(BasicBlock *BB); 142 bool calcFloatingPointHeuristics(BasicBlock *BB); 143 bool calcInvokeHeuristics(BasicBlock *BB); 144}; 145 146} 147 148#endif 149