X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FBranchProbabilityInfo.h;h=cfdf218491bdbe473904e0a423a47d5f738278af;hb=84f6badcccd77214a13fb2afefb6d110915c6bb6;hp=6c23f7c3aeb3c074a4b313dadc3444309b4c2ccb;hpb=255f89faee13dc491cb64fbeae3c763e7e2ea4e6;p=oota-llvm.git diff --git a/include/llvm/Analysis/BranchProbabilityInfo.h b/include/llvm/Analysis/BranchProbabilityInfo.h index 6c23f7c3aeb..cfdf218491b 100644 --- a/include/llvm/Analysis/BranchProbabilityInfo.h +++ b/include/llvm/Analysis/BranchProbabilityInfo.h @@ -16,6 +16,7 @@ #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" @@ -24,9 +25,9 @@ namespace llvm { class LoopInfo; class raw_ostream; -/// \brief Analysis pass providing branch probability information. +/// \brief Analysis providing branch probability information. /// -/// This is a function analysis pass which provides information on the relative +/// This is a function analysis 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 @@ -36,17 +37,14 @@ class raw_ostream; /// 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 { +class BranchProbabilityInfo { public: - static char ID; + BranchProbabilityInfo() {} + BranchProbabilityInfo(Function &F, const LoopInfo &LI) { calculate(F, LI); } - BranchProbabilityInfo() : FunctionPass(ID) { - initializeBranchProbabilityInfoPass(*PassRegistry::getPassRegistry()); - } + void releaseMemory(); - void getAnalysisUsage(AnalysisUsage &AU) const; - bool runOnFunction(Function &F); - void print(raw_ostream &OS, const Module *M = 0) const; + void print(raw_ostream &OS) const; /// \brief Get an edge's probability, relative to other out-edges of the Src. /// @@ -63,6 +61,9 @@ public: BranchProbability getEdgeProbability(const BasicBlock *Src, const BasicBlock *Dst) const; + BranchProbability getEdgeProbability(const BasicBlock *Src, + succ_const_iterator 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 @@ -83,29 +84,21 @@ public: 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. + /// \brief Set the raw edge probability for the 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 + /// This allows a pass to explicitly set the edge probability 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); + /// probabilities are calculated carefully before using! + void setEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors, + BranchProbability Prob); + + static BranchProbability getBranchProbStackProtector(bool IsLikely) { + static const BranchProbability LikelyProb((1u << 20) - 1, 1u << 20); + return IsLikely ? LikelyProb : LikelyProb.getCompl(); + } + + void calculate(Function &F, const LoopInfo& LI); private: // Since we allow duplicate edges from one basic block to another, we use @@ -120,10 +113,7 @@ private: // 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; + DenseMap Probs; /// \brief Track the last function we run over for printing. Function *LastF; @@ -131,18 +121,40 @@ private: /// \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; + /// \brief Track the set of blocks that always lead to a cold call. + SmallPtrSet PostDominatedByColdCall; bool calcUnreachableHeuristics(BasicBlock *BB); bool calcMetadataWeights(BasicBlock *BB); + bool calcColdCallHeuristics(BasicBlock *BB); bool calcPointerHeuristics(BasicBlock *BB); - bool calcLoopBranchHeuristics(BasicBlock *BB); + bool calcLoopBranchHeuristics(BasicBlock *BB, const LoopInfo &LI); bool calcZeroHeuristics(BasicBlock *BB); bool calcFloatingPointHeuristics(BasicBlock *BB); bool calcInvokeHeuristics(BasicBlock *BB); }; +/// \brief Legacy analysis pass which computes \c BranchProbabilityInfo. +class BranchProbabilityInfoWrapperPass : public FunctionPass { + BranchProbabilityInfo BPI; + +public: + static char ID; + + BranchProbabilityInfoWrapperPass() : FunctionPass(ID) { + initializeBranchProbabilityInfoWrapperPassPass( + *PassRegistry::getPassRegistry()); + } + + BranchProbabilityInfo &getBPI() { return BPI; } + const BranchProbabilityInfo &getBPI() const { return BPI; } + + void getAnalysisUsage(AnalysisUsage &AU) const override; + bool runOnFunction(Function &F) override; + void releaseMemory() override; + void print(raw_ostream &OS, const Module *M = nullptr) const override; +}; + } #endif