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