BranchProbabilityInfo.h revision 0c34ae88bfe6ab40fc30784f131510992438ea43
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 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 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%). 36class BranchProbabilityInfo : public FunctionPass { 37public: 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 94private: 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 bool calcInvokeHeuristics(BasicBlock *BB); 126}; 127 128} 129 130#endif 131