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" 19255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include "llvm/InitializePasses.h" 20255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include "llvm/Pass.h" 21f289df2d9544bd3a0934651daa20e589544413baAndrew Trick#include "llvm/Support/BranchProbability.h" 229e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick 239e76422b963a65f243fdbee0abed61068b82dd98Andrew Tricknamespace llvm { 24b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruthclass LoopInfo; 25f289df2d9544bd3a0934651daa20e589544413baAndrew Trickclass raw_ostream; 26f289df2d9544bd3a0934651daa20e589544413baAndrew Trick 27f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth/// \brief Analysis pass providing branch probability information. 28f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth/// 29f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth/// This is a function analysis pass which provides information on the relative 30f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth/// probabilities of each "edge" in the function's CFG where such an edge is 311a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren/// defined by a pair (PredBlock and an index in the successors). The 321a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren/// probability of an edge from one block is always relative to the 331a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren/// probabilities of other edges from the block. The probabilites of all edges 341a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren/// from a block sum to exactly one (100%). 351a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren/// We use a pair (PredBlock and an index in the successors) to uniquely 361a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren/// identify an edge, since we can have multiple edges from Src to Dst. 371a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren/// As an example, we can have a switch which jumps to Dst with value 0 and 381a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren/// value 10. 399e76422b963a65f243fdbee0abed61068b82dd98Andrew Trickclass BranchProbabilityInfo : public FunctionPass { 409e76422b963a65f243fdbee0abed61068b82dd98Andrew Trickpublic: 419e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick static char ID; 429e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick 439e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick BranchProbabilityInfo() : FunctionPass(ID) { 449e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick initializeBranchProbabilityInfoPass(*PassRegistry::getPassRegistry()); 459e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick } 469e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick 4712af93ae86cb4a517d1b67f9363fbf21f24f583bJakub Staszak void getAnalysisUsage(AnalysisUsage &AU) const; 489e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick bool runOnFunction(Function &F); 4914edd314af99ccaad194d071f23e437a1371f176Chandler Carruth void print(raw_ostream &OS, const Module *M = 0) const; 509e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick 51f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// \brief Get an edge's probability, relative to other out-edges of the Src. 52f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// 53f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// This routine provides access to the fractional probability between zero 54f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// (0%) and one (100%) of this edge executing, relative to other edges 55f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// leaving the 'Src' block. The returned probability is never zero, and can 56f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// only be one if the source block has only one successor. 57f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth BranchProbability getEdgeProbability(const BasicBlock *Src, 581a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren unsigned IndexInSuccessors) const; 591a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren 601a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren /// \brief Get the probability of going from Src to Dst. 611a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren /// 621a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren /// It returns the sum of all probabilities for edges from Src to Dst. 631a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren BranchProbability getEdgeProbability(const BasicBlock *Src, 64f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth const BasicBlock *Dst) const; 659e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick 66f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// \brief Test if an edge is hot relative to other out-edges of the Src. 67f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// 68f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// Check whether this edge out of the source block is 'hot'. We define hot 69f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// as having a relative probability >= 80%. 706f6baf1bdd7531da5ddb925ffcfcf38724e9e4aaJakub Staszak bool isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const; 719e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick 72f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// \brief Retrieve the hot successor of a block if one exists. 73f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// 74f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// Given a basic block, look through its successors and if one exists for 75f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// which \see isEdgeHot would return true, return that successor block. 769e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick BasicBlock *getHotSucc(BasicBlock *BB) const; 779e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick 78f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// \brief Print an edge's probability. 79f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// 80f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// Retrieves an edge's probability similarly to \see getEdgeProbability, but 81f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// then prints that probability to the provided stream. That stream is then 82f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// returned. 8314edd314af99ccaad194d071f23e437a1371f176Chandler Carruth raw_ostream &printEdgeProbability(raw_ostream &OS, const BasicBlock *Src, 8414edd314af99ccaad194d071f23e437a1371f176Chandler Carruth const BasicBlock *Dst) const; 85b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth 861a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren /// \brief Get the raw edge weight calculated for the edge. 87f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// 88f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// This returns the raw edge weight. It is guaranteed to fall between 1 and 89f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// UINT32_MAX. Note that the raw edge weight is not meaningful in isolation. 90f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// This interface should be very carefully, and primarily by routines that 91f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// are updating the analysis by later calling setEdgeWeight. 921a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren uint32_t getEdgeWeight(const BasicBlock *Src, 931a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren unsigned IndexInSuccessors) const; 941a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren 951a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren /// \brief Get the raw edge weight calculated for the block pair. 961a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren /// 971a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren /// This returns the sum of all raw edge weights from Src to Dst. 981a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren /// It is guaranteed to fall between 1 and UINT32_MAX. 99f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth uint32_t getEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst) const; 100f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth 1011a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren /// \brief Set the raw edge weight for a given edge. 102f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// 1031a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren /// This allows a pass to explicitly set the edge weight for an edge. It can 104f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// be used when updating the CFG to update and preserve the branch 105f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// probability information. Read the implementation of how these edge 106f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth /// weights are calculated carefully before using! 1071a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren void setEdgeWeight(const BasicBlock *Src, unsigned IndexInSuccessors, 108f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth uint32_t Weight); 109f46c674a16669518dbb24d4cdd4bfc904dd3b505Chandler Carruth 110b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruthprivate: 1111a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren // Since we allow duplicate edges from one basic block to another, we use 1121a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren // a pair (PredBlock and an index in the successors) to specify an edge. 1131a710fdde197b00107ef55df51054925b9a5d2a2Manman Ren typedef std::pair<const BasicBlock *, unsigned> Edge; 114b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth 115b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth // Default weight value. Used when we don't have information about the edge. 116b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth // TODO: DEFAULT_WEIGHT makes sense during static predication, when none of 117b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth // the successors have a weight yet. But it doesn't make sense when providing 118b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth // weight to an edge that may have siblings with non-zero weights. This can 119b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth // be handled various ways, but it's probably fine for an edge with unknown 120b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth // weight to just "inherit" the non-zero weight of an adjacent successor. 121b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth static const uint32_t DEFAULT_WEIGHT = 16; 122b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth 123b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth DenseMap<Edge, uint32_t> Weights; 124b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth 125b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth /// \brief Handle to the LoopInfo analysis. 126b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth LoopInfo *LI; 127b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth 128b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth /// \brief Track the last function we run over for printing. 129b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth Function *LastF; 130b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth 131de1c9bb45017e25b5fc2b77e15d3c377f6572075Chandler Carruth /// \brief Track the set of blocks directly succeeded by a returning block. 132de1c9bb45017e25b5fc2b77e15d3c377f6572075Chandler Carruth SmallPtrSet<BasicBlock *, 16> PostDominatedByUnreachable; 133de1c9bb45017e25b5fc2b77e15d3c377f6572075Chandler Carruth 134b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth /// \brief Get sum of the block successors' weights. 135b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth uint32_t getSumForBlock(const BasicBlock *BB) const; 136b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth 137de1c9bb45017e25b5fc2b77e15d3c377f6572075Chandler Carruth bool calcUnreachableHeuristics(BasicBlock *BB); 138b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth bool calcMetadataWeights(BasicBlock *BB); 139b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth bool calcPointerHeuristics(BasicBlock *BB); 140b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth bool calcLoopBranchHeuristics(BasicBlock *BB); 141b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth bool calcZeroHeuristics(BasicBlock *BB); 142b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth bool calcFloatingPointHeuristics(BasicBlock *BB); 1430c34ae88bfe6ab40fc30784f131510992438ea43Bill Wendling bool calcInvokeHeuristics(BasicBlock *BB); 1449e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick}; 1459e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick 1469e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick} 1479e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick 1489e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick#endif 149