1//===- BranchProbabilityInfo.h - Branch Probability Analysis ----*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This pass is used to evaluate branch probabilties. 11// 12//===----------------------------------------------------------------------===// 13 14#ifndef LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H 15#define LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H 16 17#include "llvm/ADT/DenseMap.h" 18#include "llvm/ADT/DenseMapInfo.h" 19#include "llvm/ADT/DenseSet.h" 20#include "llvm/ADT/SmallPtrSet.h" 21#include "llvm/IR/BasicBlock.h" 22#include "llvm/IR/CFG.h" 23#include "llvm/IR/PassManager.h" 24#include "llvm/IR/ValueHandle.h" 25#include "llvm/Pass.h" 26#include "llvm/Support/BranchProbability.h" 27#include "llvm/Support/Casting.h" 28#include <algorithm> 29#include <cassert> 30#include <cstdint> 31#include <utility> 32 33namespace llvm { 34 35class Function; 36class LoopInfo; 37class raw_ostream; 38class TargetLibraryInfo; 39class Value; 40 41/// \brief Analysis providing branch probability information. 42/// 43/// This is a function analysis which provides information on the relative 44/// probabilities of each "edge" in the function's CFG where such an edge is 45/// defined by a pair (PredBlock and an index in the successors). The 46/// probability of an edge from one block is always relative to the 47/// probabilities of other edges from the block. The probabilites of all edges 48/// from a block sum to exactly one (100%). 49/// We use a pair (PredBlock and an index in the successors) to uniquely 50/// identify an edge, since we can have multiple edges from Src to Dst. 51/// As an example, we can have a switch which jumps to Dst with value 0 and 52/// value 10. 53class BranchProbabilityInfo { 54public: 55 BranchProbabilityInfo() = default; 56 57 BranchProbabilityInfo(const Function &F, const LoopInfo &LI, 58 const TargetLibraryInfo *TLI = nullptr) { 59 calculate(F, LI, TLI); 60 } 61 62 BranchProbabilityInfo(BranchProbabilityInfo &&Arg) 63 : Probs(std::move(Arg.Probs)), LastF(Arg.LastF), 64 PostDominatedByUnreachable(std::move(Arg.PostDominatedByUnreachable)), 65 PostDominatedByColdCall(std::move(Arg.PostDominatedByColdCall)) {} 66 67 BranchProbabilityInfo(const BranchProbabilityInfo &) = delete; 68 BranchProbabilityInfo &operator=(const BranchProbabilityInfo &) = delete; 69 70 BranchProbabilityInfo &operator=(BranchProbabilityInfo &&RHS) { 71 releaseMemory(); 72 Probs = std::move(RHS.Probs); 73 PostDominatedByColdCall = std::move(RHS.PostDominatedByColdCall); 74 PostDominatedByUnreachable = std::move(RHS.PostDominatedByUnreachable); 75 return *this; 76 } 77 78 void releaseMemory(); 79 80 void print(raw_ostream &OS) const; 81 82 /// \brief Get an edge's probability, relative to other out-edges of the Src. 83 /// 84 /// This routine provides access to the fractional probability between zero 85 /// (0%) and one (100%) of this edge executing, relative to other edges 86 /// leaving the 'Src' block. The returned probability is never zero, and can 87 /// only be one if the source block has only one successor. 88 BranchProbability getEdgeProbability(const BasicBlock *Src, 89 unsigned IndexInSuccessors) const; 90 91 /// \brief Get the probability of going from Src to Dst. 92 /// 93 /// It returns the sum of all probabilities for edges from Src to Dst. 94 BranchProbability getEdgeProbability(const BasicBlock *Src, 95 const BasicBlock *Dst) const; 96 97 BranchProbability getEdgeProbability(const BasicBlock *Src, 98 succ_const_iterator Dst) const; 99 100 /// \brief Test if an edge is hot relative to other out-edges of the Src. 101 /// 102 /// Check whether this edge out of the source block is 'hot'. We define hot 103 /// as having a relative probability >= 80%. 104 bool isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const; 105 106 /// \brief Retrieve the hot successor of a block if one exists. 107 /// 108 /// Given a basic block, look through its successors and if one exists for 109 /// which \see isEdgeHot would return true, return that successor block. 110 const BasicBlock *getHotSucc(const BasicBlock *BB) const; 111 112 /// \brief Print an edge's probability. 113 /// 114 /// Retrieves an edge's probability similarly to \see getEdgeProbability, but 115 /// then prints that probability to the provided stream. That stream is then 116 /// returned. 117 raw_ostream &printEdgeProbability(raw_ostream &OS, const BasicBlock *Src, 118 const BasicBlock *Dst) const; 119 120 /// \brief Set the raw edge probability for the given edge. 121 /// 122 /// This allows a pass to explicitly set the edge probability for an edge. It 123 /// can be used when updating the CFG to update and preserve the branch 124 /// probability information. Read the implementation of how these edge 125 /// probabilities are calculated carefully before using! 126 void setEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors, 127 BranchProbability Prob); 128 129 static BranchProbability getBranchProbStackProtector(bool IsLikely) { 130 static const BranchProbability LikelyProb((1u << 20) - 1, 1u << 20); 131 return IsLikely ? LikelyProb : LikelyProb.getCompl(); 132 } 133 134 void calculate(const Function &F, const LoopInfo &LI, 135 const TargetLibraryInfo *TLI = nullptr); 136 137 /// Forget analysis results for the given basic block. 138 void eraseBlock(const BasicBlock *BB); 139 140private: 141 // We need to store CallbackVH's in order to correctly handle basic block 142 // removal. 143 class BasicBlockCallbackVH final : public CallbackVH { 144 BranchProbabilityInfo *BPI; 145 146 void deleted() override { 147 assert(BPI != nullptr); 148 BPI->eraseBlock(cast<BasicBlock>(getValPtr())); 149 BPI->Handles.erase(*this); 150 } 151 152 public: 153 BasicBlockCallbackVH(const Value *V, BranchProbabilityInfo *BPI = nullptr) 154 : CallbackVH(const_cast<Value *>(V)), BPI(BPI) {} 155 }; 156 157 DenseSet<BasicBlockCallbackVH, DenseMapInfo<Value*>> Handles; 158 159 // Since we allow duplicate edges from one basic block to another, we use 160 // a pair (PredBlock and an index in the successors) to specify an edge. 161 using Edge = std::pair<const BasicBlock *, unsigned>; 162 163 // Default weight value. Used when we don't have information about the edge. 164 // TODO: DEFAULT_WEIGHT makes sense during static predication, when none of 165 // the successors have a weight yet. But it doesn't make sense when providing 166 // weight to an edge that may have siblings with non-zero weights. This can 167 // be handled various ways, but it's probably fine for an edge with unknown 168 // weight to just "inherit" the non-zero weight of an adjacent successor. 169 static const uint32_t DEFAULT_WEIGHT = 16; 170 171 DenseMap<Edge, BranchProbability> Probs; 172 173 /// \brief Track the last function we run over for printing. 174 const Function *LastF; 175 176 /// \brief Track the set of blocks directly succeeded by a returning block. 177 SmallPtrSet<const BasicBlock *, 16> PostDominatedByUnreachable; 178 179 /// \brief Track the set of blocks that always lead to a cold call. 180 SmallPtrSet<const BasicBlock *, 16> PostDominatedByColdCall; 181 182 void updatePostDominatedByUnreachable(const BasicBlock *BB); 183 void updatePostDominatedByColdCall(const BasicBlock *BB); 184 bool calcUnreachableHeuristics(const BasicBlock *BB); 185 bool calcMetadataWeights(const BasicBlock *BB); 186 bool calcColdCallHeuristics(const BasicBlock *BB); 187 bool calcPointerHeuristics(const BasicBlock *BB); 188 bool calcLoopBranchHeuristics(const BasicBlock *BB, const LoopInfo &LI); 189 bool calcZeroHeuristics(const BasicBlock *BB, const TargetLibraryInfo *TLI); 190 bool calcFloatingPointHeuristics(const BasicBlock *BB); 191 bool calcInvokeHeuristics(const BasicBlock *BB); 192}; 193 194/// \brief Analysis pass which computes \c BranchProbabilityInfo. 195class BranchProbabilityAnalysis 196 : public AnalysisInfoMixin<BranchProbabilityAnalysis> { 197 friend AnalysisInfoMixin<BranchProbabilityAnalysis>; 198 199 static AnalysisKey Key; 200 201public: 202 /// \brief Provide the result type for this analysis pass. 203 using Result = BranchProbabilityInfo; 204 205 /// \brief Run the analysis pass over a function and produce BPI. 206 BranchProbabilityInfo run(Function &F, FunctionAnalysisManager &AM); 207}; 208 209/// \brief Printer pass for the \c BranchProbabilityAnalysis results. 210class BranchProbabilityPrinterPass 211 : public PassInfoMixin<BranchProbabilityPrinterPass> { 212 raw_ostream &OS; 213 214public: 215 explicit BranchProbabilityPrinterPass(raw_ostream &OS) : OS(OS) {} 216 217 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 218}; 219 220/// \brief Legacy analysis pass which computes \c BranchProbabilityInfo. 221class BranchProbabilityInfoWrapperPass : public FunctionPass { 222 BranchProbabilityInfo BPI; 223 224public: 225 static char ID; 226 227 BranchProbabilityInfoWrapperPass() : FunctionPass(ID) { 228 initializeBranchProbabilityInfoWrapperPassPass( 229 *PassRegistry::getPassRegistry()); 230 } 231 232 BranchProbabilityInfo &getBPI() { return BPI; } 233 const BranchProbabilityInfo &getBPI() const { return BPI; } 234 235 void getAnalysisUsage(AnalysisUsage &AU) const override; 236 bool runOnFunction(Function &F) override; 237 void releaseMemory() override; 238 void print(raw_ostream &OS, const Module *M = nullptr) const override; 239}; 240 241} // end namespace llvm 242 243#endif // LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H 244