19e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick//===--- BranchProbabilityInfo.h - Branch Probability Analysis --*- C++ -*-===// 29e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick// 39e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick// The LLVM Compiler Infrastructure 49e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick// 59e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick// This file is distributed under the University of Illinois Open Source 69e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick// License. See LICENSE.TXT for details. 79e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick// 89e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick//===----------------------------------------------------------------------===// 99e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick// 109e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick// This pass is used to evaluate branch probabilties. 119e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick// 129e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick//===----------------------------------------------------------------------===// 139e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick 149e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick#ifndef LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H 159e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick#define LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H 169e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick 1712af93ae86cb4a517d1b67f9363fbf21f24f583bJakub Staszak#include "llvm/ADT/DenseMap.h" 18de1c9bb45017e25b5fc2b77e15d3c377f6572075Chandler Carruth#include "llvm/ADT/SmallPtrSet.h" 1936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/CFG.h" 20255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include "llvm/InitializePasses.h" 21255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include "llvm/Pass.h" 22f289df2d9544bd3a0934651daa20e589544413baAndrew Trick#include "llvm/Support/BranchProbability.h" 239e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick 249e76422b963a65f243fdbee0abed61068b82dd98Andrew Tricknamespace llvm { 25b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruthclass LoopInfo; 26f289df2d9544bd3a0934651daa20e589544413baAndrew Trickclass raw_ostream; 27f289df2d9544bd3a0934651daa20e589544413baAndrew Trick 28f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth/// \brief Analysis pass providing branch probability information. 29f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth/// 30f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth/// This is a function analysis pass which provides information on the relative 31f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth/// probabilities of each "edge" in the function's CFG where such an edge is 321a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren/// defined by a pair (PredBlock and an index in the successors). The 331a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren/// probability of an edge from one block is always relative to the 341a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren/// probabilities of other edges from the block. The probabilites of all edges 351a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren/// from a block sum to exactly one (100%). 361a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren/// We use a pair (PredBlock and an index in the successors) to uniquely 371a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren/// identify an edge, since we can have multiple edges from Src to Dst. 381a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren/// As an example, we can have a switch which jumps to Dst with value 0 and 391a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren/// value 10. 409e76422b963a65f243fdbee0abed61068b82dd98Andrew Trickclass BranchProbabilityInfo : public FunctionPass { 419e76422b963a65f243fdbee0abed61068b82dd98Andrew Trickpublic: 429e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick static char ID; 439e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick 449e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick BranchProbabilityInfo() : FunctionPass(ID) { 459e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick initializeBranchProbabilityInfoPass(*PassRegistry::getPassRegistry()); 469e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick } 479e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick 4836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override; 4936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool runOnFunction(Function &F) override; 50dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines void print(raw_ostream &OS, const Module *M = nullptr) const override; 519e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick 52f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// \brief Get an edge's probability, relative to other out-edges of the Src. 53f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// 54f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// This routine provides access to the fractional probability between zero 55f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// (0%) and one (100%) of this edge executing, relative to other edges 56f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// leaving the 'Src' block. The returned probability is never zero, and can 57f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// only be one if the source block has only one successor. 58f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth BranchProbability getEdgeProbability(const BasicBlock *Src, 591a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren unsigned IndexInSuccessors) const; 601a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren 611a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren /// \brief Get the probability of going from Src to Dst. 621a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren /// 631a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren /// It returns the sum of all probabilities for edges from Src to Dst. 641a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren BranchProbability getEdgeProbability(const BasicBlock *Src, 65f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth const BasicBlock *Dst) const; 669e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick 67f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// \brief Test if an edge is hot relative to other out-edges of the Src. 68f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// 69f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// Check whether this edge out of the source block is 'hot'. We define hot 70f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// as having a relative probability >= 80%. 716f6baf1bdd7531da5ddb925ffcfcf38724e9e4aaJakub Staszak bool isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const; 729e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick 73f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// \brief Retrieve the hot successor of a block if one exists. 74f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// 75f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// Given a basic block, look through its successors and if one exists for 76f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// which \see isEdgeHot would return true, return that successor block. 779e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick BasicBlock *getHotSucc(BasicBlock *BB) const; 789e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick 79f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// \brief Print an edge's probability. 80f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// 81f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// Retrieves an edge's probability similarly to \see getEdgeProbability, but 82f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// then prints that probability to the provided stream. That stream is then 83f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// returned. 8414edd314af99ccaad194d071f23e437a1371f176Chandler Carruth raw_ostream &printEdgeProbability(raw_ostream &OS, const BasicBlock *Src, 8514edd314af99ccaad194d071f23e437a1371f176Chandler Carruth const BasicBlock *Dst) const; 86b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth 871a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren /// \brief Get the raw edge weight calculated for the edge. 88f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// 89f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// This returns the raw edge weight. It is guaranteed to fall between 1 and 90f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// UINT32_MAX. Note that the raw edge weight is not meaningful in isolation. 91f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// This interface should be very carefully, and primarily by routines that 92f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// are updating the analysis by later calling setEdgeWeight. 931a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren uint32_t getEdgeWeight(const BasicBlock *Src, 941a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren unsigned IndexInSuccessors) const; 951a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren 961a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren /// \brief Get the raw edge weight calculated for the block pair. 971a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren /// 981a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren /// This returns the sum of all raw edge weights from Src to Dst. 991a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren /// It is guaranteed to fall between 1 and UINT32_MAX. 100f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth uint32_t getEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst) const; 101f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth 10236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines uint32_t getEdgeWeight(const BasicBlock *Src, 10336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines succ_const_iterator Dst) const; 10436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 1051a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren /// \brief Set the raw edge weight for a given edge. 106f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// 1071a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren /// This allows a pass to explicitly set the edge weight for an edge. It can 108f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// be used when updating the CFG to update and preserve the branch 109f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// probability information. Read the implementation of how these edge 110f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// weights are calculated carefully before using! 1111a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren void setEdgeWeight(const BasicBlock *Src, unsigned IndexInSuccessors, 112f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth uint32_t Weight); 113f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth 114b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruthprivate: 1151a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren // Since we allow duplicate edges from one basic block to another, we use 1161a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren // a pair (PredBlock and an index in the successors) to specify an edge. 1171a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren typedef std::pair<const BasicBlock *, unsigned> Edge; 118b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth 119b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth // Default weight value. Used when we don't have information about the edge. 120b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth // TODO: DEFAULT_WEIGHT makes sense during static predication, when none of 121b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth // the successors have a weight yet. But it doesn't make sense when providing 122b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth // weight to an edge that may have siblings with non-zero weights. This can 123b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth // be handled various ways, but it's probably fine for an edge with unknown 124b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth // weight to just "inherit" the non-zero weight of an adjacent successor. 125b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth static const uint32_t DEFAULT_WEIGHT = 16; 126b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth 127b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth DenseMap<Edge, uint32_t> Weights; 128b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth 129b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth /// \brief Handle to the LoopInfo analysis. 130b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth LoopInfo *LI; 131b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth 132b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth /// \brief Track the last function we run over for printing. 133b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth Function *LastF; 134b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth 135de1c9bb45017e25b5fc2b77e15d3c377f6572075Chandler Carruth /// \brief Track the set of blocks directly succeeded by a returning block. 136de1c9bb45017e25b5fc2b77e15d3c377f6572075Chandler Carruth SmallPtrSet<BasicBlock *, 16> PostDominatedByUnreachable; 137de1c9bb45017e25b5fc2b77e15d3c377f6572075Chandler Carruth 13877226a03dca98e6237c1068f2652fe41bea7b687Diego Novillo /// \brief Track the set of blocks that always lead to a cold call. 13977226a03dca98e6237c1068f2652fe41bea7b687Diego Novillo SmallPtrSet<BasicBlock *, 16> PostDominatedByColdCall; 14077226a03dca98e6237c1068f2652fe41bea7b687Diego Novillo 141b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth /// \brief Get sum of the block successors' weights. 142b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth uint32_t getSumForBlock(const BasicBlock *BB) const; 143b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth 144de1c9bb45017e25b5fc2b77e15d3c377f6572075Chandler Carruth bool calcUnreachableHeuristics(BasicBlock *BB); 145b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth bool calcMetadataWeights(BasicBlock *BB); 14677226a03dca98e6237c1068f2652fe41bea7b687Diego Novillo bool calcColdCallHeuristics(BasicBlock *BB); 147b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth bool calcPointerHeuristics(BasicBlock *BB); 148b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth bool calcLoopBranchHeuristics(BasicBlock *BB); 149b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth bool calcZeroHeuristics(BasicBlock *BB); 150b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth bool calcFloatingPointHeuristics(BasicBlock *BB); 1510c34ae88bfe6ab40fc30784f131510992438ea43Bill Wendling bool calcInvokeHeuristics(BasicBlock *BB); 1529e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick}; 1539e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick 1549e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick} 1559e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick 1569e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick#endif 157