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 <memory> 31 #include <utility> 32 33 namespace llvm { 34 35 class Function; 36 class Loop; 37 class LoopInfo; 38 class raw_ostream; 39 class DominatorTree; 40 class PostDominatorTree; 41 class TargetLibraryInfo; 42 class Value; 43 44 /// Analysis providing branch probability information. 45 /// 46 /// This is a function analysis which provides information on the relative 47 /// probabilities of each "edge" in the function's CFG where such an edge is 48 /// defined by a pair (PredBlock and an index in the successors). The 49 /// probability of an edge from one block is always relative to the 50 /// probabilities of other edges from the block. The probabilites of all edges 51 /// from a block sum to exactly one (100%). 52 /// We use a pair (PredBlock and an index in the successors) to uniquely 53 /// identify an edge, since we can have multiple edges from Src to Dst. 54 /// As an example, we can have a switch which jumps to Dst with value 0 and 55 /// value 10. 56 /// 57 /// Process of computing branch probabilities can be logically viewed as three 58 /// step process: 59 /// 60 /// First, if there is a profile information associated with the branch then 61 /// it is trivially translated to branch probabilities. There is one exception 62 /// from this rule though. Probabilities for edges leading to "unreachable" 63 /// blocks (blocks with the estimated weight not greater than 64 /// UNREACHABLE_WEIGHT) are evaluated according to static estimation and 65 /// override profile information. If no branch probabilities were calculated 66 /// on this step then take the next one. 67 /// 68 /// Second, estimate absolute execution weights for each block based on 69 /// statically known information. Roots of such information are "cold", 70 /// "unreachable", "noreturn" and "unwind" blocks. Those blocks get their 71 /// weights set to BlockExecWeight::COLD, BlockExecWeight::UNREACHABLE, 72 /// BlockExecWeight::NORETURN and BlockExecWeight::UNWIND respectively. Then the 73 /// weights are propagated to the other blocks up the domination line. In 74 /// addition, if all successors have estimated weights set then maximum of these 75 /// weights assigned to the block itself (while this is not ideal heuristic in 76 /// theory it's simple and works reasonably well in most cases) and the process 77 /// repeats. Once the process of weights propagation converges branch 78 /// probabilities are set for all such branches that have at least one successor 79 /// with the weight set. Default execution weight (BlockExecWeight::DEFAULT) is 80 /// used for any successors which doesn't have its weight set. For loop back 81 /// branches we use their weights scaled by loop trip count equal to 82 /// 'LBH_TAKEN_WEIGHT/LBH_NOTTAKEN_WEIGHT'. 83 /// 84 /// Here is a simple example demonstrating how the described algorithm works. 85 /// 86 /// BB1 87 /// / \ 88 /// v v 89 /// BB2 BB3 90 /// / \ 91 /// v v 92 /// ColdBB UnreachBB 93 /// 94 /// Initially, ColdBB is associated with COLD_WEIGHT and UnreachBB with 95 /// UNREACHABLE_WEIGHT. COLD_WEIGHT is set to BB2 as maximum between its 96 /// successors. BB1 and BB3 has no explicit estimated weights and assumed to 97 /// have DEFAULT_WEIGHT. Based on assigned weights branches will have the 98 /// following probabilities: 99 /// P(BB1->BB2) = COLD_WEIGHT/(COLD_WEIGHT + DEFAULT_WEIGHT) = 100 /// 0xffff / (0xffff + 0xfffff) = 0.0588(5.9%) 101 /// P(BB1->BB3) = DEFAULT_WEIGHT_WEIGHT/(COLD_WEIGHT + DEFAULT_WEIGHT) = 102 /// 0xfffff / (0xffff + 0xfffff) = 0.941(94.1%) 103 /// P(BB2->ColdBB) = COLD_WEIGHT/(COLD_WEIGHT + UNREACHABLE_WEIGHT) = 1(100%) 104 /// P(BB2->UnreachBB) = 105 /// UNREACHABLE_WEIGHT/(COLD_WEIGHT+UNREACHABLE_WEIGHT) = 0(0%) 106 /// 107 /// If no branch probabilities were calculated on this step then take the next 108 /// one. 109 /// 110 /// Third, apply different kinds of local heuristics for each individual 111 /// branch until first match. For example probability of a pointer to be null is 112 /// estimated as PH_TAKEN_WEIGHT/(PH_TAKEN_WEIGHT + PH_NONTAKEN_WEIGHT). If 113 /// no local heuristic has been matched then branch is left with no explicit 114 /// probability set and assumed to have default probability. 115 class BranchProbabilityInfo { 116 public: 117 BranchProbabilityInfo() = default; 118 119 BranchProbabilityInfo(const Function &F, const LoopInfo &LI, 120 const TargetLibraryInfo *TLI = nullptr, 121 DominatorTree *DT = nullptr, 122 PostDominatorTree *PDT = nullptr) { 123 calculate(F, LI, TLI, DT, PDT); 124 } 125 BranchProbabilityInfo(BranchProbabilityInfo && Arg)126 BranchProbabilityInfo(BranchProbabilityInfo &&Arg) 127 : Probs(std::move(Arg.Probs)), LastF(Arg.LastF), 128 EstimatedBlockWeight(std::move(Arg.EstimatedBlockWeight)) {} 129 130 BranchProbabilityInfo(const BranchProbabilityInfo &) = delete; 131 BranchProbabilityInfo &operator=(const BranchProbabilityInfo &) = delete; 132 133 BranchProbabilityInfo &operator=(BranchProbabilityInfo &&RHS) { 134 releaseMemory(); 135 Probs = std::move(RHS.Probs); 136 EstimatedBlockWeight = std::move(RHS.EstimatedBlockWeight); 137 return *this; 138 } 139 140 bool invalidate(Function &, const PreservedAnalyses &PA, 141 FunctionAnalysisManager::Invalidator &); 142 143 void releaseMemory(); 144 145 void print(raw_ostream &OS) const; 146 147 /// Get an edge's probability, relative to other out-edges of the Src. 148 /// 149 /// This routine provides access to the fractional probability between zero 150 /// (0%) and one (100%) of this edge executing, relative to other edges 151 /// leaving the 'Src' block. The returned probability is never zero, and can 152 /// only be one if the source block has only one successor. 153 BranchProbability getEdgeProbability(const BasicBlock *Src, 154 unsigned IndexInSuccessors) const; 155 156 /// Get the probability of going from Src to Dst. 157 /// 158 /// It returns the sum of all probabilities for edges from Src to Dst. 159 BranchProbability getEdgeProbability(const BasicBlock *Src, 160 const BasicBlock *Dst) const; 161 162 BranchProbability getEdgeProbability(const BasicBlock *Src, 163 const_succ_iterator Dst) const; 164 165 /// Test if an edge is hot relative to other out-edges of the Src. 166 /// 167 /// Check whether this edge out of the source block is 'hot'. We define hot 168 /// as having a relative probability >= 80%. 169 bool isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const; 170 171 /// Print an edge's probability. 172 /// 173 /// Retrieves an edge's probability similarly to \see getEdgeProbability, but 174 /// then prints that probability to the provided stream. That stream is then 175 /// returned. 176 raw_ostream &printEdgeProbability(raw_ostream &OS, const BasicBlock *Src, 177 const BasicBlock *Dst) const; 178 179 public: 180 /// Set the raw probabilities for all edges from the given block. 181 /// 182 /// This allows a pass to explicitly set edge probabilities for a block. It 183 /// can be used when updating the CFG to update the branch probability 184 /// information. 185 void setEdgeProbability(const BasicBlock *Src, 186 const SmallVectorImpl<BranchProbability> &Probs); 187 188 /// Copy outgoing edge probabilities from \p Src to \p Dst. 189 /// 190 /// This allows to keep probabilities unset for the destination if they were 191 /// unset for source. 192 void copyEdgeProbabilities(BasicBlock *Src, BasicBlock *Dst); 193 getBranchProbStackProtector(bool IsLikely)194 static BranchProbability getBranchProbStackProtector(bool IsLikely) { 195 static const BranchProbability LikelyProb((1u << 20) - 1, 1u << 20); 196 return IsLikely ? LikelyProb : LikelyProb.getCompl(); 197 } 198 199 void calculate(const Function &F, const LoopInfo &LI, 200 const TargetLibraryInfo *TLI, DominatorTree *DT, 201 PostDominatorTree *PDT); 202 203 /// Forget analysis results for the given basic block. 204 void eraseBlock(const BasicBlock *BB); 205 206 // Data structure to track SCCs for handling irreducible loops. 207 class SccInfo { 208 // Enum of types to classify basic blocks in SCC. Basic block belonging to 209 // SCC is 'Inner' until it is either 'Header' or 'Exiting'. Note that a 210 // basic block can be 'Header' and 'Exiting' at the same time. 211 enum SccBlockType { 212 Inner = 0x0, 213 Header = 0x1, 214 Exiting = 0x2, 215 }; 216 // Map of basic blocks to SCC IDs they belong to. If basic block doesn't 217 // belong to any SCC it is not in the map. 218 using SccMap = DenseMap<const BasicBlock *, int>; 219 // Each basic block in SCC is attributed with one or several types from 220 // SccBlockType. Map value has uint32_t type (instead of SccBlockType) 221 // since basic block may be for example "Header" and "Exiting" at the same 222 // time and we need to be able to keep more than one value from 223 // SccBlockType. 224 using SccBlockTypeMap = DenseMap<const BasicBlock *, uint32_t>; 225 // Vector containing classification of basic blocks for all SCCs where i'th 226 // vector element corresponds to SCC with ID equal to i. 227 using SccBlockTypeMaps = std::vector<SccBlockTypeMap>; 228 229 SccMap SccNums; 230 SccBlockTypeMaps SccBlocks; 231 232 public: 233 explicit SccInfo(const Function &F); 234 235 /// If \p BB belongs to some SCC then ID of that SCC is returned, otherwise 236 /// -1 is returned. If \p BB belongs to more than one SCC at the same time 237 /// result is undefined. 238 int getSCCNum(const BasicBlock *BB) const; 239 /// Returns true if \p BB is a 'header' block in SCC with \p SccNum ID, 240 /// false otherwise. isSCCHeader(const BasicBlock * BB,int SccNum)241 bool isSCCHeader(const BasicBlock *BB, int SccNum) const { 242 return getSccBlockType(BB, SccNum) & Header; 243 } 244 /// Returns true if \p BB is an 'exiting' block in SCC with \p SccNum ID, 245 /// false otherwise. isSCCExitingBlock(const BasicBlock * BB,int SccNum)246 bool isSCCExitingBlock(const BasicBlock *BB, int SccNum) const { 247 return getSccBlockType(BB, SccNum) & Exiting; 248 } 249 /// Fills in \p Enters vector with all such blocks that don't belong to 250 /// SCC with \p SccNum ID but there is an edge to a block belonging to the 251 /// SCC. 252 void getSccEnterBlocks(int SccNum, 253 SmallVectorImpl<BasicBlock *> &Enters) const; 254 /// Fills in \p Exits vector with all such blocks that don't belong to 255 /// SCC with \p SccNum ID but there is an edge from a block belonging to the 256 /// SCC. 257 void getSccExitBlocks(int SccNum, 258 SmallVectorImpl<BasicBlock *> &Exits) const; 259 260 private: 261 /// Returns \p BB's type according to classification given by SccBlockType 262 /// enum. Please note that \p BB must belong to SSC with \p SccNum ID. 263 uint32_t getSccBlockType(const BasicBlock *BB, int SccNum) const; 264 /// Calculates \p BB's type and stores it in internal data structures for 265 /// future use. Please note that \p BB must belong to SSC with \p SccNum ID. 266 void calculateSccBlockType(const BasicBlock *BB, int SccNum); 267 }; 268 269 private: 270 // We need to store CallbackVH's in order to correctly handle basic block 271 // removal. 272 class BasicBlockCallbackVH final : public CallbackVH { 273 BranchProbabilityInfo *BPI; 274 deleted()275 void deleted() override { 276 assert(BPI != nullptr); 277 BPI->eraseBlock(cast<BasicBlock>(getValPtr())); 278 } 279 280 public: 281 BasicBlockCallbackVH(const Value *V, BranchProbabilityInfo *BPI = nullptr) CallbackVH(const_cast<Value * > (V))282 : CallbackVH(const_cast<Value *>(V)), BPI(BPI) {} 283 }; 284 285 /// Pair of Loop and SCC ID number. Used to unify handling of normal and 286 /// SCC based loop representations. 287 using LoopData = std::pair<Loop *, int>; 288 /// Helper class to keep basic block along with its loop data information. 289 class LoopBlock { 290 public: 291 explicit LoopBlock(const BasicBlock *BB, const LoopInfo &LI, 292 const SccInfo &SccI); 293 getBlock()294 const BasicBlock *getBlock() const { return BB; } getBlock()295 BasicBlock *getBlock() { return const_cast<BasicBlock *>(BB); } getLoopData()296 LoopData getLoopData() const { return LD; } getLoop()297 Loop *getLoop() const { return LD.first; } getSccNum()298 int getSccNum() const { return LD.second; } 299 belongsToLoop()300 bool belongsToLoop() const { return getLoop() || getSccNum() != -1; } belongsToSameLoop(const LoopBlock & LB)301 bool belongsToSameLoop(const LoopBlock &LB) const { 302 return (LB.getLoop() && getLoop() == LB.getLoop()) || 303 (LB.getSccNum() != -1 && getSccNum() == LB.getSccNum()); 304 } 305 306 private: 307 const BasicBlock *const BB = nullptr; 308 LoopData LD = {nullptr, -1}; 309 }; 310 311 // Pair of LoopBlocks representing an edge from first to second block. 312 using LoopEdge = std::pair<const LoopBlock &, const LoopBlock &>; 313 314 DenseSet<BasicBlockCallbackVH, DenseMapInfo<Value*>> Handles; 315 316 // Since we allow duplicate edges from one basic block to another, we use 317 // a pair (PredBlock and an index in the successors) to specify an edge. 318 using Edge = std::pair<const BasicBlock *, unsigned>; 319 320 DenseMap<Edge, BranchProbability> Probs; 321 322 /// Track the last function we run over for printing. 323 const Function *LastF = nullptr; 324 325 const LoopInfo *LI = nullptr; 326 327 /// Keeps information about all SCCs in a function. 328 std::unique_ptr<const SccInfo> SccI; 329 330 /// Keeps mapping of a basic block to its estimated weight. 331 SmallDenseMap<const BasicBlock *, uint32_t> EstimatedBlockWeight; 332 333 /// Keeps mapping of a loop to estimated weight to enter the loop. 334 SmallDenseMap<LoopData, uint32_t> EstimatedLoopWeight; 335 336 /// Helper to construct LoopBlock for \p BB. getLoopBlock(const BasicBlock * BB)337 LoopBlock getLoopBlock(const BasicBlock *BB) const { 338 return LoopBlock(BB, *LI, *SccI.get()); 339 } 340 341 /// Returns true if destination block belongs to some loop and source block is 342 /// either doesn't belong to any loop or belongs to a loop which is not inner 343 /// relative to the destination block. 344 bool isLoopEnteringEdge(const LoopEdge &Edge) const; 345 /// Returns true if source block belongs to some loop and destination block is 346 /// either doesn't belong to any loop or belongs to a loop which is not inner 347 /// relative to the source block. 348 bool isLoopExitingEdge(const LoopEdge &Edge) const; 349 /// Returns true if \p Edge is either enters to or exits from some loop, false 350 /// in all other cases. 351 bool isLoopEnteringExitingEdge(const LoopEdge &Edge) const; 352 /// Returns true if source and destination blocks belongs to the same loop and 353 /// destination block is loop header. 354 bool isLoopBackEdge(const LoopEdge &Edge) const; 355 // Fills in \p Enters vector with all "enter" blocks to a loop \LB belongs to. 356 void getLoopEnterBlocks(const LoopBlock &LB, 357 SmallVectorImpl<BasicBlock *> &Enters) const; 358 // Fills in \p Exits vector with all "exit" blocks from a loop \LB belongs to. 359 void getLoopExitBlocks(const LoopBlock &LB, 360 SmallVectorImpl<BasicBlock *> &Exits) const; 361 362 /// Returns estimated weight for \p BB. None if \p BB has no estimated weight. 363 Optional<uint32_t> getEstimatedBlockWeight(const BasicBlock *BB) const; 364 365 /// Returns estimated weight to enter \p L. In other words it is weight of 366 /// loop's header block not scaled by trip count. Returns None if \p L has no 367 /// no estimated weight. 368 Optional<uint32_t> getEstimatedLoopWeight(const LoopData &L) const; 369 370 /// Return estimated weight for \p Edge. Returns None if estimated weight is 371 /// unknown. 372 Optional<uint32_t> getEstimatedEdgeWeight(const LoopEdge &Edge) const; 373 374 /// Iterates over all edges leading from \p SrcBB to \p Successors and 375 /// returns maximum of all estimated weights. If at least one edge has unknown 376 /// estimated weight None is returned. 377 template <class IterT> 378 Optional<uint32_t> 379 getMaxEstimatedEdgeWeight(const LoopBlock &SrcBB, 380 iterator_range<IterT> Successors) const; 381 382 /// If \p LoopBB has no estimated weight then set it to \p BBWeight and 383 /// return true. Otherwise \p BB's weight remains unchanged and false is 384 /// returned. In addition all blocks/loops that might need their weight to be 385 /// re-estimated are put into BlockWorkList/LoopWorkList. 386 bool updateEstimatedBlockWeight(LoopBlock &LoopBB, uint32_t BBWeight, 387 SmallVectorImpl<BasicBlock *> &BlockWorkList, 388 SmallVectorImpl<LoopBlock> &LoopWorkList); 389 390 /// Starting from \p LoopBB (including \p LoopBB itself) propagate \p BBWeight 391 /// up the domination tree. 392 void propagateEstimatedBlockWeight(const LoopBlock &LoopBB, DominatorTree *DT, 393 PostDominatorTree *PDT, uint32_t BBWeight, 394 SmallVectorImpl<BasicBlock *> &WorkList, 395 SmallVectorImpl<LoopBlock> &LoopWorkList); 396 397 /// Returns block's weight encoded in the IR. 398 Optional<uint32_t> getInitialEstimatedBlockWeight(const BasicBlock *BB); 399 400 // Computes estimated weights for all blocks in \p F. 401 void computeEestimateBlockWeight(const Function &F, DominatorTree *DT, 402 PostDominatorTree *PDT); 403 404 /// Based on computed weights by \p computeEstimatedBlockWeight set 405 /// probabilities on branches. 406 bool calcEstimatedHeuristics(const BasicBlock *BB); 407 bool calcMetadataWeights(const BasicBlock *BB); 408 bool calcPointerHeuristics(const BasicBlock *BB); 409 bool calcZeroHeuristics(const BasicBlock *BB, const TargetLibraryInfo *TLI); 410 bool calcFloatingPointHeuristics(const BasicBlock *BB); 411 }; 412 413 /// Analysis pass which computes \c BranchProbabilityInfo. 414 class BranchProbabilityAnalysis 415 : public AnalysisInfoMixin<BranchProbabilityAnalysis> { 416 friend AnalysisInfoMixin<BranchProbabilityAnalysis>; 417 418 static AnalysisKey Key; 419 420 public: 421 /// Provide the result type for this analysis pass. 422 using Result = BranchProbabilityInfo; 423 424 /// Run the analysis pass over a function and produce BPI. 425 BranchProbabilityInfo run(Function &F, FunctionAnalysisManager &AM); 426 }; 427 428 /// Printer pass for the \c BranchProbabilityAnalysis results. 429 class BranchProbabilityPrinterPass 430 : public PassInfoMixin<BranchProbabilityPrinterPass> { 431 raw_ostream &OS; 432 433 public: BranchProbabilityPrinterPass(raw_ostream & OS)434 explicit BranchProbabilityPrinterPass(raw_ostream &OS) : OS(OS) {} 435 436 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 437 }; 438 439 /// Legacy analysis pass which computes \c BranchProbabilityInfo. 440 class BranchProbabilityInfoWrapperPass : public FunctionPass { 441 BranchProbabilityInfo BPI; 442 443 public: 444 static char ID; 445 446 BranchProbabilityInfoWrapperPass(); 447 getBPI()448 BranchProbabilityInfo &getBPI() { return BPI; } getBPI()449 const BranchProbabilityInfo &getBPI() const { return BPI; } 450 451 void getAnalysisUsage(AnalysisUsage &AU) const override; 452 bool runOnFunction(Function &F) override; 453 void releaseMemory() override; 454 void print(raw_ostream &OS, const Module *M = nullptr) const override; 455 }; 456 457 } // end namespace llvm 458 459 #endif // LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H 460