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