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 33namespace llvm { 34 35class Function; 36class Loop; 37class LoopInfo; 38class raw_ostream; 39class DominatorTree; 40class PostDominatorTree; 41class TargetLibraryInfo; 42class 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. 115class BranchProbabilityInfo { 116public: 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 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 /// Retrieve the hot successor of a block if one exists. 172 /// 173 /// Given a basic block, look through its successors and if one exists for 174 /// which \see isEdgeHot would return true, return that successor block. 175 const BasicBlock *getHotSucc(const BasicBlock *BB) const; 176 177 /// Print an edge's probability. 178 /// 179 /// Retrieves an edge's probability similarly to \see getEdgeProbability, but 180 /// then prints that probability to the provided stream. That stream is then 181 /// returned. 182 raw_ostream &printEdgeProbability(raw_ostream &OS, const BasicBlock *Src, 183 const BasicBlock *Dst) const; 184 185public: 186 /// Set the raw probabilities for all edges from the given block. 187 /// 188 /// This allows a pass to explicitly set edge probabilities for a block. It 189 /// can be used when updating the CFG to update the branch probability 190 /// information. 191 void setEdgeProbability(const BasicBlock *Src, 192 const SmallVectorImpl<BranchProbability> &Probs); 193 194 /// Copy outgoing edge probabilities from \p Src to \p Dst. 195 /// 196 /// This allows to keep probabilities unset for the destination if they were 197 /// unset for source. 198 void copyEdgeProbabilities(BasicBlock *Src, BasicBlock *Dst); 199 200 static BranchProbability getBranchProbStackProtector(bool IsLikely) { 201 static const BranchProbability LikelyProb((1u << 20) - 1, 1u << 20); 202 return IsLikely ? LikelyProb : LikelyProb.getCompl(); 203 } 204 205 void calculate(const Function &F, const LoopInfo &LI, 206 const TargetLibraryInfo *TLI, DominatorTree *DT, 207 PostDominatorTree *PDT); 208 209 /// Forget analysis results for the given basic block. 210 void eraseBlock(const BasicBlock *BB); 211 212 // Data structure to track SCCs for handling irreducible loops. 213 class SccInfo { 214 // Enum of types to classify basic blocks in SCC. Basic block belonging to 215 // SCC is 'Inner' until it is either 'Header' or 'Exiting'. Note that a 216 // basic block can be 'Header' and 'Exiting' at the same time. 217 enum SccBlockType { 218 Inner = 0x0, 219 Header = 0x1, 220 Exiting = 0x2, 221 }; 222 // Map of basic blocks to SCC IDs they belong to. If basic block doesn't 223 // belong to any SCC it is not in the map. 224 using SccMap = DenseMap<const BasicBlock *, int>; 225 // Each basic block in SCC is attributed with one or several types from 226 // SccBlockType. Map value has uint32_t type (instead of SccBlockType) 227 // since basic block may be for example "Header" and "Exiting" at the same 228 // time and we need to be able to keep more than one value from 229 // SccBlockType. 230 using SccBlockTypeMap = DenseMap<const BasicBlock *, uint32_t>; 231 // Vector containing classification of basic blocks for all SCCs where i'th 232 // vector element corresponds to SCC with ID equal to i. 233 using SccBlockTypeMaps = std::vector<SccBlockTypeMap>; 234 235 SccMap SccNums; 236 SccBlockTypeMaps SccBlocks; 237 238 public: 239 explicit SccInfo(const Function &F); 240 241 /// If \p BB belongs to some SCC then ID of that SCC is returned, otherwise 242 /// -1 is returned. If \p BB belongs to more than one SCC at the same time 243 /// result is undefined. 244 int getSCCNum(const BasicBlock *BB) const; 245 /// Returns true if \p BB is a 'header' block in SCC with \p SccNum ID, 246 /// false otherwise. 247 bool isSCCHeader(const BasicBlock *BB, int SccNum) const { 248 return getSccBlockType(BB, SccNum) & Header; 249 } 250 /// Returns true if \p BB is an 'exiting' block in SCC with \p SccNum ID, 251 /// false otherwise. 252 bool isSCCExitingBlock(const BasicBlock *BB, int SccNum) const { 253 return getSccBlockType(BB, SccNum) & Exiting; 254 } 255 /// Fills in \p Enters vector with all such blocks that don't belong to 256 /// SCC with \p SccNum ID but there is an edge to a block belonging to the 257 /// SCC. 258 void getSccEnterBlocks(int SccNum, 259 SmallVectorImpl<BasicBlock *> &Enters) const; 260 /// Fills in \p Exits vector with all such blocks that don't belong to 261 /// SCC with \p SccNum ID but there is an edge from a block belonging to the 262 /// SCC. 263 void getSccExitBlocks(int SccNum, 264 SmallVectorImpl<BasicBlock *> &Exits) const; 265 266 private: 267 /// Returns \p BB's type according to classification given by SccBlockType 268 /// enum. Please note that \p BB must belong to SSC with \p SccNum ID. 269 uint32_t getSccBlockType(const BasicBlock *BB, int SccNum) const; 270 /// Calculates \p BB's type and stores it in internal data structures for 271 /// future use. Please note that \p BB must belong to SSC with \p SccNum ID. 272 void calculateSccBlockType(const BasicBlock *BB, int SccNum); 273 }; 274 275private: 276 // We need to store CallbackVH's in order to correctly handle basic block 277 // removal. 278 class BasicBlockCallbackVH final : public CallbackVH { 279 BranchProbabilityInfo *BPI; 280 281 void deleted() override { 282 assert(BPI != nullptr); 283 BPI->eraseBlock(cast<BasicBlock>(getValPtr())); 284 } 285 286 public: 287 BasicBlockCallbackVH(const Value *V, BranchProbabilityInfo *BPI = nullptr) 288 : CallbackVH(const_cast<Value *>(V)), BPI(BPI) {} 289 }; 290 291 /// Pair of Loop and SCC ID number. Used to unify handling of normal and 292 /// SCC based loop representations. 293 using LoopData = std::pair<Loop *, int>; 294 /// Helper class to keep basic block along with its loop data information. 295 class LoopBlock { 296 public: 297 explicit LoopBlock(const BasicBlock *BB, const LoopInfo &LI, 298 const SccInfo &SccI); 299 300 const BasicBlock *getBlock() const { return BB; } 301 BasicBlock *getBlock() { return const_cast<BasicBlock *>(BB); } 302 LoopData getLoopData() const { return LD; } 303 Loop *getLoop() const { return LD.first; } 304 int getSccNum() const { return LD.second; } 305 306 bool belongsToLoop() const { return getLoop() || getSccNum() != -1; } 307 bool belongsToSameLoop(const LoopBlock &LB) const { 308 return (LB.getLoop() && getLoop() == LB.getLoop()) || 309 (LB.getSccNum() != -1 && getSccNum() == LB.getSccNum()); 310 } 311 312 private: 313 const BasicBlock *const BB = nullptr; 314 LoopData LD = {nullptr, -1}; 315 }; 316 317 // Pair of LoopBlocks representing an edge from first to second block. 318 using LoopEdge = std::pair<const LoopBlock &, const LoopBlock &>; 319 320 DenseSet<BasicBlockCallbackVH, DenseMapInfo<Value*>> Handles; 321 322 // Since we allow duplicate edges from one basic block to another, we use 323 // a pair (PredBlock and an index in the successors) to specify an edge. 324 using Edge = std::pair<const BasicBlock *, unsigned>; 325 326 DenseMap<Edge, BranchProbability> Probs; 327 328 /// Track the last function we run over for printing. 329 const Function *LastF = nullptr; 330 331 const LoopInfo *LI = nullptr; 332 333 /// Keeps information about all SCCs in a function. 334 std::unique_ptr<const SccInfo> SccI; 335 336 /// Keeps mapping of a basic block to its estimated weight. 337 SmallDenseMap<const BasicBlock *, uint32_t> EstimatedBlockWeight; 338 339 /// Keeps mapping of a loop to estimated weight to enter the loop. 340 SmallDenseMap<LoopData, uint32_t> EstimatedLoopWeight; 341 342 /// Helper to construct LoopBlock for \p BB. 343 LoopBlock getLoopBlock(const BasicBlock *BB) const { 344 return LoopBlock(BB, *LI, *SccI.get()); 345 } 346 347 /// Returns true if destination block belongs to some loop and source block is 348 /// either doesn't belong to any loop or belongs to a loop which is not inner 349 /// relative to the destination block. 350 bool isLoopEnteringEdge(const LoopEdge &Edge) const; 351 /// Returns true if source block belongs to some loop and destination block is 352 /// either doesn't belong to any loop or belongs to a loop which is not inner 353 /// relative to the source block. 354 bool isLoopExitingEdge(const LoopEdge &Edge) const; 355 /// Returns true if \p Edge is either enters to or exits from some loop, false 356 /// in all other cases. 357 bool isLoopEnteringExitingEdge(const LoopEdge &Edge) const; 358 /// Returns true if source and destination blocks belongs to the same loop and 359 /// destination block is loop header. 360 bool isLoopBackEdge(const LoopEdge &Edge) const; 361 // Fills in \p Enters vector with all "enter" blocks to a loop \LB belongs to. 362 void getLoopEnterBlocks(const LoopBlock &LB, 363 SmallVectorImpl<BasicBlock *> &Enters) const; 364 // Fills in \p Exits vector with all "exit" blocks from a loop \LB belongs to. 365 void getLoopExitBlocks(const LoopBlock &LB, 366 SmallVectorImpl<BasicBlock *> &Exits) const; 367 368 /// Returns estimated weight for \p BB. None if \p BB has no estimated weight. 369 Optional<uint32_t> getEstimatedBlockWeight(const BasicBlock *BB) const; 370 371 /// Returns estimated weight to enter \p L. In other words it is weight of 372 /// loop's header block not scaled by trip count. Returns None if \p L has no 373 /// no estimated weight. 374 Optional<uint32_t> getEstimatedLoopWeight(const LoopData &L) const; 375 376 /// Return estimated weight for \p Edge. Returns None if estimated weight is 377 /// unknown. 378 Optional<uint32_t> getEstimatedEdgeWeight(const LoopEdge &Edge) const; 379 380 /// Iterates over all edges leading from \p SrcBB to \p Successors and 381 /// returns maximum of all estimated weights. If at least one edge has unknown 382 /// estimated weight None is returned. 383 template <class IterT> 384 Optional<uint32_t> 385 getMaxEstimatedEdgeWeight(const LoopBlock &SrcBB, 386 iterator_range<IterT> Successors) const; 387 388 /// If \p LoopBB has no estimated weight then set it to \p BBWeight and 389 /// return true. Otherwise \p BB's weight remains unchanged and false is 390 /// returned. In addition all blocks/loops that might need their weight to be 391 /// re-estimated are put into BlockWorkList/LoopWorkList. 392 bool updateEstimatedBlockWeight(LoopBlock &LoopBB, uint32_t BBWeight, 393 SmallVectorImpl<BasicBlock *> &BlockWorkList, 394 SmallVectorImpl<LoopBlock> &LoopWorkList); 395 396 /// Starting from \p LoopBB (including \p LoopBB itself) propagate \p BBWeight 397 /// up the domination tree. 398 void propagateEstimatedBlockWeight(const LoopBlock &LoopBB, DominatorTree *DT, 399 PostDominatorTree *PDT, uint32_t BBWeight, 400 SmallVectorImpl<BasicBlock *> &WorkList, 401 SmallVectorImpl<LoopBlock> &LoopWorkList); 402 403 /// Returns block's weight encoded in the IR. 404 Optional<uint32_t> getInitialEstimatedBlockWeight(const BasicBlock *BB); 405 406 // Computes estimated weights for all blocks in \p F. 407 void computeEestimateBlockWeight(const Function &F, DominatorTree *DT, 408 PostDominatorTree *PDT); 409 410 /// Based on computed weights by \p computeEstimatedBlockWeight set 411 /// probabilities on branches. 412 bool calcEstimatedHeuristics(const BasicBlock *BB); 413 bool calcMetadataWeights(const BasicBlock *BB); 414 bool calcPointerHeuristics(const BasicBlock *BB); 415 bool calcZeroHeuristics(const BasicBlock *BB, const TargetLibraryInfo *TLI); 416 bool calcFloatingPointHeuristics(const BasicBlock *BB); 417}; 418 419/// Analysis pass which computes \c BranchProbabilityInfo. 420class BranchProbabilityAnalysis 421 : public AnalysisInfoMixin<BranchProbabilityAnalysis> { 422 friend AnalysisInfoMixin<BranchProbabilityAnalysis>; 423 424 static AnalysisKey Key; 425 426public: 427 /// Provide the result type for this analysis pass. 428 using Result = BranchProbabilityInfo; 429 430 /// Run the analysis pass over a function and produce BPI. 431 BranchProbabilityInfo run(Function &F, FunctionAnalysisManager &AM); 432}; 433 434/// Printer pass for the \c BranchProbabilityAnalysis results. 435class BranchProbabilityPrinterPass 436 : public PassInfoMixin<BranchProbabilityPrinterPass> { 437 raw_ostream &OS; 438 439public: 440 explicit BranchProbabilityPrinterPass(raw_ostream &OS) : OS(OS) {} 441 442 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 443}; 444 445/// Legacy analysis pass which computes \c BranchProbabilityInfo. 446class BranchProbabilityInfoWrapperPass : public FunctionPass { 447 BranchProbabilityInfo BPI; 448 449public: 450 static char ID; 451 452 BranchProbabilityInfoWrapperPass(); 453 454 BranchProbabilityInfo &getBPI() { return BPI; } 455 const BranchProbabilityInfo &getBPI() const { return BPI; } 456 457 void getAnalysisUsage(AnalysisUsage &AU) const override; 458 bool runOnFunction(Function &F) override; 459 void releaseMemory() override; 460 void print(raw_ostream &OS, const Module *M = nullptr) const override; 461}; 462 463} // end namespace llvm 464 465#endif // LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H 466