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 PostDominatorTree; 38 class TargetLibraryInfo; 39 class Value; 40 41 /// 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. 53 class BranchProbabilityInfo { 54 public: 55 BranchProbabilityInfo() = default; 56 57 BranchProbabilityInfo(const Function &F, const LoopInfo &LI, 58 const TargetLibraryInfo *TLI = nullptr) { 59 calculate(F, LI, TLI); 60 } 61 BranchProbabilityInfo(BranchProbabilityInfo && Arg)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 /// 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 /// 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 /// 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 /// 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 /// 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 /// 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 getBranchProbStackProtector(bool IsLikely)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 140 // Use to track SCCs for handling irreducible loops. 141 using SccMap = DenseMap<const BasicBlock *, int>; 142 using SccHeaderMap = DenseMap<const BasicBlock *, bool>; 143 using SccHeaderMaps = std::vector<SccHeaderMap>; 144 struct SccInfo { 145 SccMap SccNums; 146 SccHeaderMaps SccHeaders; 147 }; 148 149 private: 150 // We need to store CallbackVH's in order to correctly handle basic block 151 // removal. 152 class BasicBlockCallbackVH final : public CallbackVH { 153 BranchProbabilityInfo *BPI; 154 deleted()155 void deleted() override { 156 assert(BPI != nullptr); 157 BPI->eraseBlock(cast<BasicBlock>(getValPtr())); 158 BPI->Handles.erase(*this); 159 } 160 161 public: 162 BasicBlockCallbackVH(const Value *V, BranchProbabilityInfo *BPI = nullptr) CallbackVH(const_cast<Value * > (V))163 : CallbackVH(const_cast<Value *>(V)), BPI(BPI) {} 164 }; 165 166 DenseSet<BasicBlockCallbackVH, DenseMapInfo<Value*>> Handles; 167 168 // Since we allow duplicate edges from one basic block to another, we use 169 // a pair (PredBlock and an index in the successors) to specify an edge. 170 using Edge = std::pair<const BasicBlock *, unsigned>; 171 172 // Default weight value. Used when we don't have information about the edge. 173 // TODO: DEFAULT_WEIGHT makes sense during static predication, when none of 174 // the successors have a weight yet. But it doesn't make sense when providing 175 // weight to an edge that may have siblings with non-zero weights. This can 176 // be handled various ways, but it's probably fine for an edge with unknown 177 // weight to just "inherit" the non-zero weight of an adjacent successor. 178 static const uint32_t DEFAULT_WEIGHT = 16; 179 180 DenseMap<Edge, BranchProbability> Probs; 181 182 /// Track the last function we run over for printing. 183 const Function *LastF = nullptr; 184 185 /// Track the set of blocks directly succeeded by a returning block. 186 SmallPtrSet<const BasicBlock *, 16> PostDominatedByUnreachable; 187 188 /// Track the set of blocks that always lead to a cold call. 189 SmallPtrSet<const BasicBlock *, 16> PostDominatedByColdCall; 190 191 void computePostDominatedByUnreachable(const Function &F, 192 PostDominatorTree *PDT); 193 void computePostDominatedByColdCall(const Function &F, 194 PostDominatorTree *PDT); 195 bool calcUnreachableHeuristics(const BasicBlock *BB); 196 bool calcMetadataWeights(const BasicBlock *BB); 197 bool calcColdCallHeuristics(const BasicBlock *BB); 198 bool calcPointerHeuristics(const BasicBlock *BB); 199 bool calcLoopBranchHeuristics(const BasicBlock *BB, const LoopInfo &LI, 200 SccInfo &SccI); 201 bool calcZeroHeuristics(const BasicBlock *BB, const TargetLibraryInfo *TLI); 202 bool calcFloatingPointHeuristics(const BasicBlock *BB); 203 bool calcInvokeHeuristics(const BasicBlock *BB); 204 }; 205 206 /// Analysis pass which computes \c BranchProbabilityInfo. 207 class BranchProbabilityAnalysis 208 : public AnalysisInfoMixin<BranchProbabilityAnalysis> { 209 friend AnalysisInfoMixin<BranchProbabilityAnalysis>; 210 211 static AnalysisKey Key; 212 213 public: 214 /// Provide the result type for this analysis pass. 215 using Result = BranchProbabilityInfo; 216 217 /// Run the analysis pass over a function and produce BPI. 218 BranchProbabilityInfo run(Function &F, FunctionAnalysisManager &AM); 219 }; 220 221 /// Printer pass for the \c BranchProbabilityAnalysis results. 222 class BranchProbabilityPrinterPass 223 : public PassInfoMixin<BranchProbabilityPrinterPass> { 224 raw_ostream &OS; 225 226 public: BranchProbabilityPrinterPass(raw_ostream & OS)227 explicit BranchProbabilityPrinterPass(raw_ostream &OS) : OS(OS) {} 228 229 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 230 }; 231 232 /// Legacy analysis pass which computes \c BranchProbabilityInfo. 233 class BranchProbabilityInfoWrapperPass : public FunctionPass { 234 BranchProbabilityInfo BPI; 235 236 public: 237 static char ID; 238 239 BranchProbabilityInfoWrapperPass(); 240 getBPI()241 BranchProbabilityInfo &getBPI() { return BPI; } getBPI()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