X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FBranchProbabilityInfo.h;h=6c23f7c3aeb3c074a4b313dadc3444309b4c2ccb;hb=b09c146b116359616f6cbd4c8b3328607e00ff42;hp=180d230b4c542a69f64164516f697b4a97a66fd0;hpb=14edd314af99ccaad194d071f23e437a1371f176;p=oota-llvm.git diff --git a/include/llvm/Analysis/BranchProbabilityInfo.h b/include/llvm/Analysis/BranchProbabilityInfo.h index 180d230b4c5..6c23f7c3aeb 100644 --- a/include/llvm/Analysis/BranchProbabilityInfo.h +++ b/include/llvm/Analysis/BranchProbabilityInfo.h @@ -14,35 +14,29 @@ #ifndef LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H #define LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallPtrSet.h" #include "llvm/InitializePasses.h" #include "llvm/Pass.h" -#include "llvm/ADT/DenseMap.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 (PredBlock and an index in the successors). The +/// probability of an edge from one block is always relative to the +/// probabilities of other edges from the block. The probabilites of all edges +/// from a block sum to exactly one (100%). +/// We use a pair (PredBlock and an index in the successors) to uniquely +/// identify an edge, since we can have multiple edges from Src to Dst. +/// As an example, we can have a switch which jumps to Dst with value 0 and +/// value 10. 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 Edge; - - DenseMap Weights; - - /// \brief Track the last function we run over for printing. - Function *LastF; - - // Get sum of the block successors' weights. - uint32_t getSumForBlock(const BasicBlock *BB) const; - public: static char ID; @@ -54,31 +48,99 @@ public: bool runOnFunction(Function &F); void print(raw_ostream &OS, const Module *M = 0) const; - // Returned value is between 1 and UINT32_MAX. Look at - // BranchProbabilityInfo.cpp for details. - uint32_t getEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst) 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, + unsigned IndexInSuccessors) const; - // Look at BranchProbabilityInfo.cpp for details. Use it with caution! - void setEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst, - uint32_t Weight); + /// \brief Get the probability of going from Src to Dst. + /// + /// It returns the sum of all probabilities for edges from Src to Dst. + BranchProbability getEdgeProbability(const BasicBlock *Src, + const BasicBlock *Dst) const; - // A 'Hot' edge is an edge which probability is >= 80%. + /// \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; - // Return a hot successor for the block BB or null if there isn't one. + /// \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; - // 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; - - // 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. + /// \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 edge. + /// + /// 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, + unsigned IndexInSuccessors) const; + + /// \brief Get the raw edge weight calculated for the block pair. + /// + /// This returns the sum of all raw edge weights from Src to Dst. + /// It is guaranteed to fall between 1 and UINT32_MAX. + uint32_t getEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst) const; + + /// \brief Set the raw edge weight for a given edge. + /// + /// This allows a pass to explicitly set the edge weight for an edge. 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, unsigned IndexInSuccessors, + uint32_t Weight); + +private: + // Since we allow duplicate edges from one basic block to another, we use + // a pair (PredBlock and an index in the successors) to specify an edge. + typedef std::pair Edge; + + // 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; + + DenseMap 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 PostDominatedByUnreachable; + + /// \brief Get sum of the block successors' weights. + uint32_t getSumForBlock(const BasicBlock *BB) 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); + bool calcInvokeHeuristics(BasicBlock *BB); }; }