diff options
Diffstat (limited to 'include/llvm/Analysis/BranchProbabilityInfo.h')
| -rw-r--r-- | include/llvm/Analysis/BranchProbabilityInfo.h | 116 |
1 files changed, 81 insertions, 35 deletions
diff --git a/include/llvm/Analysis/BranchProbabilityInfo.h b/include/llvm/Analysis/BranchProbabilityInfo.h index a2c12ab..2ced796 100644 --- a/include/llvm/Analysis/BranchProbabilityInfo.h +++ b/include/llvm/Analysis/BranchProbabilityInfo.h @@ -17,29 +17,23 @@ #include "llvm/InitializePasses.h" #include "llvm/Pass.h" #include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallPtrSet.h" #include "llvm/Support/BranchProbability.h" namespace llvm { - +class LoopInfo; class raw_ostream; +/// \brief Analysis pass providing branch probability information. +/// +/// This is a function analysis pass which provides information on the relative +/// probabilities of each "edge" in the function's CFG where such an edge is +/// defined by a pair of basic blocks. The probability for a given block and +/// a successor block are always relative to the probabilities of the other +/// successor blocks. Another way of looking at it is that the probabilities +/// for a given block B and each of its successors should sum to exactly +/// one (100%). class BranchProbabilityInfo : public FunctionPass { - - // Default weight value. Used when we don't have information about the edge. - // TODO: DEFAULT_WEIGHT makes sense during static predication, when none of - // the successors have a weight yet. But it doesn't make sense when providing - // weight to an edge that may have siblings with non-zero weights. This can - // be handled various ways, but it's probably fine for an edge with unknown - // weight to just "inherit" the non-zero weight of an adjacent successor. - static const uint32_t DEFAULT_WEIGHT = 16; - - typedef std::pair<const BasicBlock *, const BasicBlock *> Edge; - - DenseMap<Edge, uint32_t> Weights; - - // Get sum of the block successors' weights. - uint32_t getSumForBlock(const BasicBlock *BB) const; - public: static char ID; @@ -48,34 +42,86 @@ public: } void getAnalysisUsage(AnalysisUsage &AU) const; - bool runOnFunction(Function &F); + void print(raw_ostream &OS, const Module *M = 0) const; + + /// \brief Get an edge's probability, relative to other out-edges of the Src. + /// + /// This routine provides access to the fractional probability between zero + /// (0%) and one (100%) of this edge executing, relative to other edges + /// leaving the 'Src' block. The returned probability is never zero, and can + /// only be one if the source block has only one successor. + BranchProbability getEdgeProbability(const BasicBlock *Src, + const BasicBlock *Dst) const; + + /// \brief Test if an edge is hot relative to other out-edges of the Src. + /// + /// Check whether this edge out of the source block is 'hot'. We define hot + /// as having a relative probability >= 80%. + bool isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const; - // Returned value is between 1 and UINT32_MAX. Look at - // BranchProbabilityInfo.cpp for details. + /// \brief Retrieve the hot successor of a block if one exists. + /// + /// Given a basic block, look through its successors and if one exists for + /// which \see isEdgeHot would return true, return that successor block. + BasicBlock *getHotSucc(BasicBlock *BB) const; + + /// \brief Print an edge's probability. + /// + /// Retrieves an edge's probability similarly to \see getEdgeProbability, but + /// then prints that probability to the provided stream. That stream is then + /// returned. + raw_ostream &printEdgeProbability(raw_ostream &OS, const BasicBlock *Src, + const BasicBlock *Dst) const; + + /// \brief Get the raw edge weight calculated for the block pair. + /// + /// This returns the raw edge weight. It is guaranteed to fall between 1 and + /// UINT32_MAX. Note that the raw edge weight is not meaningful in isolation. + /// This interface should be very carefully, and primarily by routines that + /// are updating the analysis by later calling setEdgeWeight. uint32_t getEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst) const; - // Look at BranchProbabilityInfo.cpp for details. Use it with caution! + /// \brief Set the raw edge weight for the block pair. + /// + /// This allows a pass to explicitly set the edge weight for a block. It can + /// be used when updating the CFG to update and preserve the branch + /// probability information. Read the implementation of how these edge + /// weights are calculated carefully before using! void setEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst, uint32_t Weight); - // A 'Hot' edge is an edge which probability is >= 80%. - bool isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const; +private: + typedef std::pair<const BasicBlock *, const BasicBlock *> Edge; - // Return a hot successor for the block BB or null if there isn't one. - BasicBlock *getHotSucc(BasicBlock *BB) const; + // Default weight value. Used when we don't have information about the edge. + // TODO: DEFAULT_WEIGHT makes sense during static predication, when none of + // the successors have a weight yet. But it doesn't make sense when providing + // weight to an edge that may have siblings with non-zero weights. This can + // be handled various ways, but it's probably fine for an edge with unknown + // weight to just "inherit" the non-zero weight of an adjacent successor. + static const uint32_t DEFAULT_WEIGHT = 16; - // Return a probability as a fraction 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. - BranchProbability getEdgeProbability(const BasicBlock *Src, - const BasicBlock *Dst) const; + DenseMap<Edge, uint32_t> Weights; + + /// \brief Handle to the LoopInfo analysis. + LoopInfo *LI; + + /// \brief Track the last function we run over for printing. + Function *LastF; + + /// \brief Track the set of blocks directly succeeded by a returning block. + SmallPtrSet<BasicBlock *, 16> PostDominatedByUnreachable; + + /// \brief Get sum of the block successors' weights. + uint32_t getSumForBlock(const 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; + bool calcUnreachableHeuristics(BasicBlock *BB); + bool calcMetadataWeights(BasicBlock *BB); + bool calcPointerHeuristics(BasicBlock *BB); + bool calcLoopBranchHeuristics(BasicBlock *BB); + bool calcZeroHeuristics(BasicBlock *BB); + bool calcFloatingPointHeuristics(BasicBlock *BB); }; } |
