diff options
Diffstat (limited to 'include/llvm/Analysis/BranchProbabilityInfo.h')
-rw-r--r-- | include/llvm/Analysis/BranchProbabilityInfo.h | 156 |
1 files changed, 156 insertions, 0 deletions
diff --git a/include/llvm/Analysis/BranchProbabilityInfo.h b/include/llvm/Analysis/BranchProbabilityInfo.h new file mode 100644 index 0000000..4414c84 --- /dev/null +++ b/include/llvm/Analysis/BranchProbabilityInfo.h @@ -0,0 +1,156 @@ +//===--- BranchProbabilityInfo.h - Branch Probability Analysis --*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass is used to evaluate branch probabilties. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H +#define LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/IR/CFG.h" +#include "llvm/InitializePasses.h" +#include "llvm/Pass.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 { +public: + static char ID; + + BranchProbabilityInfo() : FunctionPass(ID) { + initializeBranchProbabilityInfoPass(*PassRegistry::getPassRegistry()); + } + + void getAnalysisUsage(AnalysisUsage &AU) const override; + bool runOnFunction(Function &F) override; + void print(raw_ostream &OS, const Module *M = nullptr) const override; + + /// \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; + + /// \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; + + /// \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; + + /// \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 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; + + uint32_t getEdgeWeight(const BasicBlock *Src, + succ_const_iterator 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<const BasicBlock *, unsigned> 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<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 Track the set of blocks that always lead to a cold call. + SmallPtrSet<BasicBlock *, 16> PostDominatedByColdCall; + + /// \brief Get sum of the block successors' weights. + uint32_t getSumForBlock(const BasicBlock *BB) const; + + bool calcUnreachableHeuristics(BasicBlock *BB); + bool calcMetadataWeights(BasicBlock *BB); + bool calcColdCallHeuristics(BasicBlock *BB); + bool calcPointerHeuristics(BasicBlock *BB); + bool calcLoopBranchHeuristics(BasicBlock *BB); + bool calcZeroHeuristics(BasicBlock *BB); + bool calcFloatingPointHeuristics(BasicBlock *BB); + bool calcInvokeHeuristics(BasicBlock *BB); +}; + +} + +#endif |