1 //===- BranchProbabilityInfo.cpp - Branch Probability Analysis ------------===// 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 // Loops should be simplified before this analysis. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "llvm/Analysis/BranchProbabilityInfo.h" 14 #include "llvm/ADT/PostOrderIterator.h" 15 #include "llvm/ADT/SCCIterator.h" 16 #include "llvm/ADT/STLExtras.h" 17 #include "llvm/ADT/SmallVector.h" 18 #include "llvm/Analysis/ConstantFolding.h" 19 #include "llvm/Analysis/LoopInfo.h" 20 #include "llvm/Analysis/PostDominators.h" 21 #include "llvm/Analysis/TargetLibraryInfo.h" 22 #include "llvm/IR/Attributes.h" 23 #include "llvm/IR/BasicBlock.h" 24 #include "llvm/IR/CFG.h" 25 #include "llvm/IR/Constants.h" 26 #include "llvm/IR/Dominators.h" 27 #include "llvm/IR/Function.h" 28 #include "llvm/IR/InstrTypes.h" 29 #include "llvm/IR/Instruction.h" 30 #include "llvm/IR/Instructions.h" 31 #include "llvm/IR/LLVMContext.h" 32 #include "llvm/IR/Metadata.h" 33 #include "llvm/IR/PassManager.h" 34 #include "llvm/IR/ProfDataUtils.h" 35 #include "llvm/IR/Type.h" 36 #include "llvm/IR/Value.h" 37 #include "llvm/InitializePasses.h" 38 #include "llvm/Pass.h" 39 #include "llvm/Support/BranchProbability.h" 40 #include "llvm/Support/Casting.h" 41 #include "llvm/Support/CommandLine.h" 42 #include "llvm/Support/Debug.h" 43 #include "llvm/Support/raw_ostream.h" 44 #include <cassert> 45 #include <cstdint> 46 #include <iterator> 47 #include <map> 48 #include <utility> 49 50 using namespace llvm; 51 52 #define DEBUG_TYPE "branch-prob" 53 54 static cl::opt<bool> PrintBranchProb( 55 "print-bpi", cl::init(false), cl::Hidden, 56 cl::desc("Print the branch probability info.")); 57 58 cl::opt<std::string> PrintBranchProbFuncName( 59 "print-bpi-func-name", cl::Hidden, 60 cl::desc("The option to specify the name of the function " 61 "whose branch probability info is printed.")); 62 63 INITIALIZE_PASS_BEGIN(BranchProbabilityInfoWrapperPass, "branch-prob", 64 "Branch Probability Analysis", false, true) 65 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) 66 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) 67 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 68 INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass) 69 INITIALIZE_PASS_END(BranchProbabilityInfoWrapperPass, "branch-prob", 70 "Branch Probability Analysis", false, true) 71 72 BranchProbabilityInfoWrapperPass::BranchProbabilityInfoWrapperPass() 73 : FunctionPass(ID) { 74 initializeBranchProbabilityInfoWrapperPassPass( 75 *PassRegistry::getPassRegistry()); 76 } 77 78 char BranchProbabilityInfoWrapperPass::ID = 0; 79 80 // Weights are for internal use only. They are used by heuristics to help to 81 // estimate edges' probability. Example: 82 // 83 // Using "Loop Branch Heuristics" we predict weights of edges for the 84 // block BB2. 85 // ... 86 // | 87 // V 88 // BB1<-+ 89 // | | 90 // | | (Weight = 124) 91 // V | 92 // BB2--+ 93 // | 94 // | (Weight = 4) 95 // V 96 // BB3 97 // 98 // Probability of the edge BB2->BB1 = 124 / (124 + 4) = 0.96875 99 // Probability of the edge BB2->BB3 = 4 / (124 + 4) = 0.03125 100 static const uint32_t LBH_TAKEN_WEIGHT = 124; 101 static const uint32_t LBH_NONTAKEN_WEIGHT = 4; 102 103 /// Unreachable-terminating branch taken probability. 104 /// 105 /// This is the probability for a branch being taken to a block that terminates 106 /// (eventually) in unreachable. These are predicted as unlikely as possible. 107 /// All reachable probability will proportionally share the remaining part. 108 static const BranchProbability UR_TAKEN_PROB = BranchProbability::getRaw(1); 109 110 /// Heuristics and lookup tables for non-loop branches: 111 /// Pointer Heuristics (PH) 112 static const uint32_t PH_TAKEN_WEIGHT = 20; 113 static const uint32_t PH_NONTAKEN_WEIGHT = 12; 114 static const BranchProbability 115 PtrTakenProb(PH_TAKEN_WEIGHT, PH_TAKEN_WEIGHT + PH_NONTAKEN_WEIGHT); 116 static const BranchProbability 117 PtrUntakenProb(PH_NONTAKEN_WEIGHT, PH_TAKEN_WEIGHT + PH_NONTAKEN_WEIGHT); 118 119 using ProbabilityList = SmallVector<BranchProbability>; 120 using ProbabilityTable = std::map<CmpInst::Predicate, ProbabilityList>; 121 122 /// Pointer comparisons: 123 static const ProbabilityTable PointerTable{ 124 {ICmpInst::ICMP_NE, {PtrTakenProb, PtrUntakenProb}}, /// p != q -> Likely 125 {ICmpInst::ICMP_EQ, {PtrUntakenProb, PtrTakenProb}}, /// p == q -> Unlikely 126 }; 127 128 /// Zero Heuristics (ZH) 129 static const uint32_t ZH_TAKEN_WEIGHT = 20; 130 static const uint32_t ZH_NONTAKEN_WEIGHT = 12; 131 static const BranchProbability 132 ZeroTakenProb(ZH_TAKEN_WEIGHT, ZH_TAKEN_WEIGHT + ZH_NONTAKEN_WEIGHT); 133 static const BranchProbability 134 ZeroUntakenProb(ZH_NONTAKEN_WEIGHT, ZH_TAKEN_WEIGHT + ZH_NONTAKEN_WEIGHT); 135 136 /// Integer compares with 0: 137 static const ProbabilityTable ICmpWithZeroTable{ 138 {CmpInst::ICMP_EQ, {ZeroUntakenProb, ZeroTakenProb}}, /// X == 0 -> Unlikely 139 {CmpInst::ICMP_NE, {ZeroTakenProb, ZeroUntakenProb}}, /// X != 0 -> Likely 140 {CmpInst::ICMP_SLT, {ZeroUntakenProb, ZeroTakenProb}}, /// X < 0 -> Unlikely 141 {CmpInst::ICMP_SGT, {ZeroTakenProb, ZeroUntakenProb}}, /// X > 0 -> Likely 142 }; 143 144 /// Integer compares with -1: 145 static const ProbabilityTable ICmpWithMinusOneTable{ 146 {CmpInst::ICMP_EQ, {ZeroUntakenProb, ZeroTakenProb}}, /// X == -1 -> Unlikely 147 {CmpInst::ICMP_NE, {ZeroTakenProb, ZeroUntakenProb}}, /// X != -1 -> Likely 148 // InstCombine canonicalizes X >= 0 into X > -1 149 {CmpInst::ICMP_SGT, {ZeroTakenProb, ZeroUntakenProb}}, /// X >= 0 -> Likely 150 }; 151 152 /// Integer compares with 1: 153 static const ProbabilityTable ICmpWithOneTable{ 154 // InstCombine canonicalizes X <= 0 into X < 1 155 {CmpInst::ICMP_SLT, {ZeroUntakenProb, ZeroTakenProb}}, /// X <= 0 -> Unlikely 156 }; 157 158 /// strcmp and similar functions return zero, negative, or positive, if the 159 /// first string is equal, less, or greater than the second. We consider it 160 /// likely that the strings are not equal, so a comparison with zero is 161 /// probably false, but also a comparison with any other number is also 162 /// probably false given that what exactly is returned for nonzero values is 163 /// not specified. Any kind of comparison other than equality we know 164 /// nothing about. 165 static const ProbabilityTable ICmpWithLibCallTable{ 166 {CmpInst::ICMP_EQ, {ZeroUntakenProb, ZeroTakenProb}}, 167 {CmpInst::ICMP_NE, {ZeroTakenProb, ZeroUntakenProb}}, 168 }; 169 170 // Floating-Point Heuristics (FPH) 171 static const uint32_t FPH_TAKEN_WEIGHT = 20; 172 static const uint32_t FPH_NONTAKEN_WEIGHT = 12; 173 174 /// This is the probability for an ordered floating point comparison. 175 static const uint32_t FPH_ORD_WEIGHT = 1024 * 1024 - 1; 176 /// This is the probability for an unordered floating point comparison, it means 177 /// one or two of the operands are NaN. Usually it is used to test for an 178 /// exceptional case, so the result is unlikely. 179 static const uint32_t FPH_UNO_WEIGHT = 1; 180 181 static const BranchProbability FPOrdTakenProb(FPH_ORD_WEIGHT, 182 FPH_ORD_WEIGHT + FPH_UNO_WEIGHT); 183 static const BranchProbability 184 FPOrdUntakenProb(FPH_UNO_WEIGHT, FPH_ORD_WEIGHT + FPH_UNO_WEIGHT); 185 static const BranchProbability 186 FPTakenProb(FPH_TAKEN_WEIGHT, FPH_TAKEN_WEIGHT + FPH_NONTAKEN_WEIGHT); 187 static const BranchProbability 188 FPUntakenProb(FPH_NONTAKEN_WEIGHT, FPH_TAKEN_WEIGHT + FPH_NONTAKEN_WEIGHT); 189 190 /// Floating-Point compares: 191 static const ProbabilityTable FCmpTable{ 192 {FCmpInst::FCMP_ORD, {FPOrdTakenProb, FPOrdUntakenProb}}, /// !isnan -> Likely 193 {FCmpInst::FCMP_UNO, {FPOrdUntakenProb, FPOrdTakenProb}}, /// isnan -> Unlikely 194 }; 195 196 /// Set of dedicated "absolute" execution weights for a block. These weights are 197 /// meaningful relative to each other and their derivatives only. 198 enum class BlockExecWeight : std::uint32_t { 199 /// Special weight used for cases with exact zero probability. 200 ZERO = 0x0, 201 /// Minimal possible non zero weight. 202 LOWEST_NON_ZERO = 0x1, 203 /// Weight to an 'unreachable' block. 204 UNREACHABLE = ZERO, 205 /// Weight to a block containing non returning call. 206 NORETURN = LOWEST_NON_ZERO, 207 /// Weight to 'unwind' block of an invoke instruction. 208 UNWIND = LOWEST_NON_ZERO, 209 /// Weight to a 'cold' block. Cold blocks are the ones containing calls marked 210 /// with attribute 'cold'. 211 COLD = 0xffff, 212 /// Default weight is used in cases when there is no dedicated execution 213 /// weight set. It is not propagated through the domination line either. 214 DEFAULT = 0xfffff 215 }; 216 217 BranchProbabilityInfo::SccInfo::SccInfo(const Function &F) { 218 // Record SCC numbers of blocks in the CFG to identify irreducible loops. 219 // FIXME: We could only calculate this if the CFG is known to be irreducible 220 // (perhaps cache this info in LoopInfo if we can easily calculate it there?). 221 int SccNum = 0; 222 for (scc_iterator<const Function *> It = scc_begin(&F); !It.isAtEnd(); 223 ++It, ++SccNum) { 224 // Ignore single-block SCCs since they either aren't loops or LoopInfo will 225 // catch them. 226 const std::vector<const BasicBlock *> &Scc = *It; 227 if (Scc.size() == 1) 228 continue; 229 230 LLVM_DEBUG(dbgs() << "BPI: SCC " << SccNum << ":"); 231 for (const auto *BB : Scc) { 232 LLVM_DEBUG(dbgs() << " " << BB->getName()); 233 SccNums[BB] = SccNum; 234 calculateSccBlockType(BB, SccNum); 235 } 236 LLVM_DEBUG(dbgs() << "\n"); 237 } 238 } 239 240 int BranchProbabilityInfo::SccInfo::getSCCNum(const BasicBlock *BB) const { 241 auto SccIt = SccNums.find(BB); 242 if (SccIt == SccNums.end()) 243 return -1; 244 return SccIt->second; 245 } 246 247 void BranchProbabilityInfo::SccInfo::getSccEnterBlocks( 248 int SccNum, SmallVectorImpl<BasicBlock *> &Enters) const { 249 250 for (auto MapIt : SccBlocks[SccNum]) { 251 const auto *BB = MapIt.first; 252 if (isSCCHeader(BB, SccNum)) 253 for (const auto *Pred : predecessors(BB)) 254 if (getSCCNum(Pred) != SccNum) 255 Enters.push_back(const_cast<BasicBlock *>(BB)); 256 } 257 } 258 259 void BranchProbabilityInfo::SccInfo::getSccExitBlocks( 260 int SccNum, SmallVectorImpl<BasicBlock *> &Exits) const { 261 for (auto MapIt : SccBlocks[SccNum]) { 262 const auto *BB = MapIt.first; 263 if (isSCCExitingBlock(BB, SccNum)) 264 for (const auto *Succ : successors(BB)) 265 if (getSCCNum(Succ) != SccNum) 266 Exits.push_back(const_cast<BasicBlock *>(Succ)); 267 } 268 } 269 270 uint32_t BranchProbabilityInfo::SccInfo::getSccBlockType(const BasicBlock *BB, 271 int SccNum) const { 272 assert(getSCCNum(BB) == SccNum); 273 274 assert(SccBlocks.size() > static_cast<unsigned>(SccNum) && "Unknown SCC"); 275 const auto &SccBlockTypes = SccBlocks[SccNum]; 276 277 auto It = SccBlockTypes.find(BB); 278 if (It != SccBlockTypes.end()) { 279 return It->second; 280 } 281 return Inner; 282 } 283 284 void BranchProbabilityInfo::SccInfo::calculateSccBlockType(const BasicBlock *BB, 285 int SccNum) { 286 assert(getSCCNum(BB) == SccNum); 287 uint32_t BlockType = Inner; 288 289 if (llvm::any_of(predecessors(BB), [&](const BasicBlock *Pred) { 290 // Consider any block that is an entry point to the SCC as 291 // a header. 292 return getSCCNum(Pred) != SccNum; 293 })) 294 BlockType |= Header; 295 296 if (llvm::any_of(successors(BB), [&](const BasicBlock *Succ) { 297 return getSCCNum(Succ) != SccNum; 298 })) 299 BlockType |= Exiting; 300 301 // Lazily compute the set of headers for a given SCC and cache the results 302 // in the SccHeaderMap. 303 if (SccBlocks.size() <= static_cast<unsigned>(SccNum)) 304 SccBlocks.resize(SccNum + 1); 305 auto &SccBlockTypes = SccBlocks[SccNum]; 306 307 if (BlockType != Inner) { 308 bool IsInserted; 309 std::tie(std::ignore, IsInserted) = 310 SccBlockTypes.insert(std::make_pair(BB, BlockType)); 311 assert(IsInserted && "Duplicated block in SCC"); 312 } 313 } 314 315 BranchProbabilityInfo::LoopBlock::LoopBlock(const BasicBlock *BB, 316 const LoopInfo &LI, 317 const SccInfo &SccI) 318 : BB(BB) { 319 LD.first = LI.getLoopFor(BB); 320 if (!LD.first) { 321 LD.second = SccI.getSCCNum(BB); 322 } 323 } 324 325 bool BranchProbabilityInfo::isLoopEnteringEdge(const LoopEdge &Edge) const { 326 const auto &SrcBlock = Edge.first; 327 const auto &DstBlock = Edge.second; 328 return (DstBlock.getLoop() && 329 !DstBlock.getLoop()->contains(SrcBlock.getLoop())) || 330 // Assume that SCCs can't be nested. 331 (DstBlock.getSccNum() != -1 && 332 SrcBlock.getSccNum() != DstBlock.getSccNum()); 333 } 334 335 bool BranchProbabilityInfo::isLoopExitingEdge(const LoopEdge &Edge) const { 336 return isLoopEnteringEdge({Edge.second, Edge.first}); 337 } 338 339 bool BranchProbabilityInfo::isLoopEnteringExitingEdge( 340 const LoopEdge &Edge) const { 341 return isLoopEnteringEdge(Edge) || isLoopExitingEdge(Edge); 342 } 343 344 bool BranchProbabilityInfo::isLoopBackEdge(const LoopEdge &Edge) const { 345 const auto &SrcBlock = Edge.first; 346 const auto &DstBlock = Edge.second; 347 return SrcBlock.belongsToSameLoop(DstBlock) && 348 ((DstBlock.getLoop() && 349 DstBlock.getLoop()->getHeader() == DstBlock.getBlock()) || 350 (DstBlock.getSccNum() != -1 && 351 SccI->isSCCHeader(DstBlock.getBlock(), DstBlock.getSccNum()))); 352 } 353 354 void BranchProbabilityInfo::getLoopEnterBlocks( 355 const LoopBlock &LB, SmallVectorImpl<BasicBlock *> &Enters) const { 356 if (LB.getLoop()) { 357 auto *Header = LB.getLoop()->getHeader(); 358 Enters.append(pred_begin(Header), pred_end(Header)); 359 } else { 360 assert(LB.getSccNum() != -1 && "LB doesn't belong to any loop?"); 361 SccI->getSccEnterBlocks(LB.getSccNum(), Enters); 362 } 363 } 364 365 void BranchProbabilityInfo::getLoopExitBlocks( 366 const LoopBlock &LB, SmallVectorImpl<BasicBlock *> &Exits) const { 367 if (LB.getLoop()) { 368 LB.getLoop()->getExitBlocks(Exits); 369 } else { 370 assert(LB.getSccNum() != -1 && "LB doesn't belong to any loop?"); 371 SccI->getSccExitBlocks(LB.getSccNum(), Exits); 372 } 373 } 374 375 // Propagate existing explicit probabilities from either profile data or 376 // 'expect' intrinsic processing. Examine metadata against unreachable 377 // heuristic. The probability of the edge coming to unreachable block is 378 // set to min of metadata and unreachable heuristic. 379 bool BranchProbabilityInfo::calcMetadataWeights(const BasicBlock *BB) { 380 const Instruction *TI = BB->getTerminator(); 381 assert(TI->getNumSuccessors() > 1 && "expected more than one successor!"); 382 if (!(isa<BranchInst>(TI) || isa<SwitchInst>(TI) || isa<IndirectBrInst>(TI) || 383 isa<InvokeInst>(TI) || isa<CallBrInst>(TI))) 384 return false; 385 386 MDNode *WeightsNode = getValidBranchWeightMDNode(*TI); 387 if (!WeightsNode) 388 return false; 389 390 // Check that the number of successors is manageable. 391 assert(TI->getNumSuccessors() < UINT32_MAX && "Too many successors"); 392 393 // Build up the final weights that will be used in a temporary buffer. 394 // Compute the sum of all weights to later decide whether they need to 395 // be scaled to fit in 32 bits. 396 uint64_t WeightSum = 0; 397 SmallVector<uint32_t, 2> Weights; 398 SmallVector<unsigned, 2> UnreachableIdxs; 399 SmallVector<unsigned, 2> ReachableIdxs; 400 401 extractBranchWeights(WeightsNode, Weights); 402 for (unsigned I = 0, E = Weights.size(); I != E; ++I) { 403 WeightSum += Weights[I]; 404 const LoopBlock SrcLoopBB = getLoopBlock(BB); 405 const LoopBlock DstLoopBB = getLoopBlock(TI->getSuccessor(I)); 406 auto EstimatedWeight = getEstimatedEdgeWeight({SrcLoopBB, DstLoopBB}); 407 if (EstimatedWeight && 408 *EstimatedWeight <= static_cast<uint32_t>(BlockExecWeight::UNREACHABLE)) 409 UnreachableIdxs.push_back(I); 410 else 411 ReachableIdxs.push_back(I); 412 } 413 assert(Weights.size() == TI->getNumSuccessors() && "Checked above"); 414 415 // If the sum of weights does not fit in 32 bits, scale every weight down 416 // accordingly. 417 uint64_t ScalingFactor = 418 (WeightSum > UINT32_MAX) ? WeightSum / UINT32_MAX + 1 : 1; 419 420 if (ScalingFactor > 1) { 421 WeightSum = 0; 422 for (unsigned I = 0, E = TI->getNumSuccessors(); I != E; ++I) { 423 Weights[I] /= ScalingFactor; 424 WeightSum += Weights[I]; 425 } 426 } 427 assert(WeightSum <= UINT32_MAX && 428 "Expected weights to scale down to 32 bits"); 429 430 if (WeightSum == 0 || ReachableIdxs.size() == 0) { 431 for (unsigned I = 0, E = TI->getNumSuccessors(); I != E; ++I) 432 Weights[I] = 1; 433 WeightSum = TI->getNumSuccessors(); 434 } 435 436 // Set the probability. 437 SmallVector<BranchProbability, 2> BP; 438 for (unsigned I = 0, E = TI->getNumSuccessors(); I != E; ++I) 439 BP.push_back({ Weights[I], static_cast<uint32_t>(WeightSum) }); 440 441 // Examine the metadata against unreachable heuristic. 442 // If the unreachable heuristic is more strong then we use it for this edge. 443 if (UnreachableIdxs.size() == 0 || ReachableIdxs.size() == 0) { 444 setEdgeProbability(BB, BP); 445 return true; 446 } 447 448 auto UnreachableProb = UR_TAKEN_PROB; 449 for (auto I : UnreachableIdxs) 450 if (UnreachableProb < BP[I]) { 451 BP[I] = UnreachableProb; 452 } 453 454 // Sum of all edge probabilities must be 1.0. If we modified the probability 455 // of some edges then we must distribute the introduced difference over the 456 // reachable blocks. 457 // 458 // Proportional distribution: the relation between probabilities of the 459 // reachable edges is kept unchanged. That is for any reachable edges i and j: 460 // newBP[i] / newBP[j] == oldBP[i] / oldBP[j] => 461 // newBP[i] / oldBP[i] == newBP[j] / oldBP[j] == K 462 // Where K is independent of i,j. 463 // newBP[i] == oldBP[i] * K 464 // We need to find K. 465 // Make sum of all reachables of the left and right parts: 466 // sum_of_reachable(newBP) == K * sum_of_reachable(oldBP) 467 // Sum of newBP must be equal to 1.0: 468 // sum_of_reachable(newBP) + sum_of_unreachable(newBP) == 1.0 => 469 // sum_of_reachable(newBP) = 1.0 - sum_of_unreachable(newBP) 470 // Where sum_of_unreachable(newBP) is what has been just changed. 471 // Finally: 472 // K == sum_of_reachable(newBP) / sum_of_reachable(oldBP) => 473 // K == (1.0 - sum_of_unreachable(newBP)) / sum_of_reachable(oldBP) 474 BranchProbability NewUnreachableSum = BranchProbability::getZero(); 475 for (auto I : UnreachableIdxs) 476 NewUnreachableSum += BP[I]; 477 478 BranchProbability NewReachableSum = 479 BranchProbability::getOne() - NewUnreachableSum; 480 481 BranchProbability OldReachableSum = BranchProbability::getZero(); 482 for (auto I : ReachableIdxs) 483 OldReachableSum += BP[I]; 484 485 if (OldReachableSum != NewReachableSum) { // Anything to dsitribute? 486 if (OldReachableSum.isZero()) { 487 // If all oldBP[i] are zeroes then the proportional distribution results 488 // in all zero probabilities and the error stays big. In this case we 489 // evenly spread NewReachableSum over the reachable edges. 490 BranchProbability PerEdge = NewReachableSum / ReachableIdxs.size(); 491 for (auto I : ReachableIdxs) 492 BP[I] = PerEdge; 493 } else { 494 for (auto I : ReachableIdxs) { 495 // We use uint64_t to avoid double rounding error of the following 496 // calculation: BP[i] = BP[i] * NewReachableSum / OldReachableSum 497 // The formula is taken from the private constructor 498 // BranchProbability(uint32_t Numerator, uint32_t Denominator) 499 uint64_t Mul = static_cast<uint64_t>(NewReachableSum.getNumerator()) * 500 BP[I].getNumerator(); 501 uint32_t Div = static_cast<uint32_t>( 502 divideNearest(Mul, OldReachableSum.getNumerator())); 503 BP[I] = BranchProbability::getRaw(Div); 504 } 505 } 506 } 507 508 setEdgeProbability(BB, BP); 509 510 return true; 511 } 512 513 // Calculate Edge Weights using "Pointer Heuristics". Predict a comparison 514 // between two pointer or pointer and NULL will fail. 515 bool BranchProbabilityInfo::calcPointerHeuristics(const BasicBlock *BB) { 516 const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()); 517 if (!BI || !BI->isConditional()) 518 return false; 519 520 Value *Cond = BI->getCondition(); 521 ICmpInst *CI = dyn_cast<ICmpInst>(Cond); 522 if (!CI || !CI->isEquality()) 523 return false; 524 525 Value *LHS = CI->getOperand(0); 526 527 if (!LHS->getType()->isPointerTy()) 528 return false; 529 530 assert(CI->getOperand(1)->getType()->isPointerTy()); 531 532 auto Search = PointerTable.find(CI->getPredicate()); 533 if (Search == PointerTable.end()) 534 return false; 535 setEdgeProbability(BB, Search->second); 536 return true; 537 } 538 539 // Compute the unlikely successors to the block BB in the loop L, specifically 540 // those that are unlikely because this is a loop, and add them to the 541 // UnlikelyBlocks set. 542 static void 543 computeUnlikelySuccessors(const BasicBlock *BB, Loop *L, 544 SmallPtrSetImpl<const BasicBlock*> &UnlikelyBlocks) { 545 // Sometimes in a loop we have a branch whose condition is made false by 546 // taking it. This is typically something like 547 // int n = 0; 548 // while (...) { 549 // if (++n >= MAX) { 550 // n = 0; 551 // } 552 // } 553 // In this sort of situation taking the branch means that at the very least it 554 // won't be taken again in the next iteration of the loop, so we should 555 // consider it less likely than a typical branch. 556 // 557 // We detect this by looking back through the graph of PHI nodes that sets the 558 // value that the condition depends on, and seeing if we can reach a successor 559 // block which can be determined to make the condition false. 560 // 561 // FIXME: We currently consider unlikely blocks to be half as likely as other 562 // blocks, but if we consider the example above the likelyhood is actually 563 // 1/MAX. We could therefore be more precise in how unlikely we consider 564 // blocks to be, but it would require more careful examination of the form 565 // of the comparison expression. 566 const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()); 567 if (!BI || !BI->isConditional()) 568 return; 569 570 // Check if the branch is based on an instruction compared with a constant 571 CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition()); 572 if (!CI || !isa<Instruction>(CI->getOperand(0)) || 573 !isa<Constant>(CI->getOperand(1))) 574 return; 575 576 // Either the instruction must be a PHI, or a chain of operations involving 577 // constants that ends in a PHI which we can then collapse into a single value 578 // if the PHI value is known. 579 Instruction *CmpLHS = dyn_cast<Instruction>(CI->getOperand(0)); 580 PHINode *CmpPHI = dyn_cast<PHINode>(CmpLHS); 581 Constant *CmpConst = dyn_cast<Constant>(CI->getOperand(1)); 582 // Collect the instructions until we hit a PHI 583 SmallVector<BinaryOperator *, 1> InstChain; 584 while (!CmpPHI && CmpLHS && isa<BinaryOperator>(CmpLHS) && 585 isa<Constant>(CmpLHS->getOperand(1))) { 586 // Stop if the chain extends outside of the loop 587 if (!L->contains(CmpLHS)) 588 return; 589 InstChain.push_back(cast<BinaryOperator>(CmpLHS)); 590 CmpLHS = dyn_cast<Instruction>(CmpLHS->getOperand(0)); 591 if (CmpLHS) 592 CmpPHI = dyn_cast<PHINode>(CmpLHS); 593 } 594 if (!CmpPHI || !L->contains(CmpPHI)) 595 return; 596 597 // Trace the phi node to find all values that come from successors of BB 598 SmallPtrSet<PHINode*, 8> VisitedInsts; 599 SmallVector<PHINode*, 8> WorkList; 600 WorkList.push_back(CmpPHI); 601 VisitedInsts.insert(CmpPHI); 602 while (!WorkList.empty()) { 603 PHINode *P = WorkList.pop_back_val(); 604 for (BasicBlock *B : P->blocks()) { 605 // Skip blocks that aren't part of the loop 606 if (!L->contains(B)) 607 continue; 608 Value *V = P->getIncomingValueForBlock(B); 609 // If the source is a PHI add it to the work list if we haven't 610 // already visited it. 611 if (PHINode *PN = dyn_cast<PHINode>(V)) { 612 if (VisitedInsts.insert(PN).second) 613 WorkList.push_back(PN); 614 continue; 615 } 616 // If this incoming value is a constant and B is a successor of BB, then 617 // we can constant-evaluate the compare to see if it makes the branch be 618 // taken or not. 619 Constant *CmpLHSConst = dyn_cast<Constant>(V); 620 if (!CmpLHSConst || !llvm::is_contained(successors(BB), B)) 621 continue; 622 // First collapse InstChain 623 const DataLayout &DL = BB->getModule()->getDataLayout(); 624 for (Instruction *I : llvm::reverse(InstChain)) { 625 CmpLHSConst = ConstantFoldBinaryOpOperands( 626 I->getOpcode(), CmpLHSConst, cast<Constant>(I->getOperand(1)), DL); 627 if (!CmpLHSConst) 628 break; 629 } 630 if (!CmpLHSConst) 631 continue; 632 // Now constant-evaluate the compare 633 Constant *Result = ConstantExpr::getCompare(CI->getPredicate(), 634 CmpLHSConst, CmpConst, true); 635 // If the result means we don't branch to the block then that block is 636 // unlikely. 637 if (Result && 638 ((Result->isZeroValue() && B == BI->getSuccessor(0)) || 639 (Result->isOneValue() && B == BI->getSuccessor(1)))) 640 UnlikelyBlocks.insert(B); 641 } 642 } 643 } 644 645 std::optional<uint32_t> 646 BranchProbabilityInfo::getEstimatedBlockWeight(const BasicBlock *BB) const { 647 auto WeightIt = EstimatedBlockWeight.find(BB); 648 if (WeightIt == EstimatedBlockWeight.end()) 649 return std::nullopt; 650 return WeightIt->second; 651 } 652 653 std::optional<uint32_t> 654 BranchProbabilityInfo::getEstimatedLoopWeight(const LoopData &L) const { 655 auto WeightIt = EstimatedLoopWeight.find(L); 656 if (WeightIt == EstimatedLoopWeight.end()) 657 return std::nullopt; 658 return WeightIt->second; 659 } 660 661 std::optional<uint32_t> 662 BranchProbabilityInfo::getEstimatedEdgeWeight(const LoopEdge &Edge) const { 663 // For edges entering a loop take weight of a loop rather than an individual 664 // block in the loop. 665 return isLoopEnteringEdge(Edge) 666 ? getEstimatedLoopWeight(Edge.second.getLoopData()) 667 : getEstimatedBlockWeight(Edge.second.getBlock()); 668 } 669 670 template <class IterT> 671 std::optional<uint32_t> BranchProbabilityInfo::getMaxEstimatedEdgeWeight( 672 const LoopBlock &SrcLoopBB, iterator_range<IterT> Successors) const { 673 SmallVector<uint32_t, 4> Weights; 674 std::optional<uint32_t> MaxWeight; 675 for (const BasicBlock *DstBB : Successors) { 676 const LoopBlock DstLoopBB = getLoopBlock(DstBB); 677 auto Weight = getEstimatedEdgeWeight({SrcLoopBB, DstLoopBB}); 678 679 if (!Weight) 680 return std::nullopt; 681 682 if (!MaxWeight || *MaxWeight < *Weight) 683 MaxWeight = Weight; 684 } 685 686 return MaxWeight; 687 } 688 689 // Updates \p LoopBB's weight and returns true. If \p LoopBB has already 690 // an associated weight it is unchanged and false is returned. 691 // 692 // Please note by the algorithm the weight is not expected to change once set 693 // thus 'false' status is used to track visited blocks. 694 bool BranchProbabilityInfo::updateEstimatedBlockWeight( 695 LoopBlock &LoopBB, uint32_t BBWeight, 696 SmallVectorImpl<BasicBlock *> &BlockWorkList, 697 SmallVectorImpl<LoopBlock> &LoopWorkList) { 698 BasicBlock *BB = LoopBB.getBlock(); 699 700 // In general, weight is assigned to a block when it has final value and 701 // can't/shouldn't be changed. However, there are cases when a block 702 // inherently has several (possibly "contradicting") weights. For example, 703 // "unwind" block may also contain "cold" call. In that case the first 704 // set weight is favored and all consequent weights are ignored. 705 if (!EstimatedBlockWeight.insert({BB, BBWeight}).second) 706 return false; 707 708 for (BasicBlock *PredBlock : predecessors(BB)) { 709 LoopBlock PredLoop = getLoopBlock(PredBlock); 710 // Add affected block/loop to a working list. 711 if (isLoopExitingEdge({PredLoop, LoopBB})) { 712 if (!EstimatedLoopWeight.count(PredLoop.getLoopData())) 713 LoopWorkList.push_back(PredLoop); 714 } else if (!EstimatedBlockWeight.count(PredBlock)) 715 BlockWorkList.push_back(PredBlock); 716 } 717 return true; 718 } 719 720 // Starting from \p BB traverse through dominator blocks and assign \p BBWeight 721 // to all such blocks that are post dominated by \BB. In other words to all 722 // blocks that the one is executed if and only if another one is executed. 723 // Importantly, we skip loops here for two reasons. First weights of blocks in 724 // a loop should be scaled by trip count (yet possibly unknown). Second there is 725 // no any value in doing that because that doesn't give any additional 726 // information regarding distribution of probabilities inside the loop. 727 // Exception is loop 'enter' and 'exit' edges that are handled in a special way 728 // at calcEstimatedHeuristics. 729 // 730 // In addition, \p WorkList is populated with basic blocks if at leas one 731 // successor has updated estimated weight. 732 void BranchProbabilityInfo::propagateEstimatedBlockWeight( 733 const LoopBlock &LoopBB, DominatorTree *DT, PostDominatorTree *PDT, 734 uint32_t BBWeight, SmallVectorImpl<BasicBlock *> &BlockWorkList, 735 SmallVectorImpl<LoopBlock> &LoopWorkList) { 736 const BasicBlock *BB = LoopBB.getBlock(); 737 const auto *DTStartNode = DT->getNode(BB); 738 const auto *PDTStartNode = PDT->getNode(BB); 739 740 // TODO: Consider propagating weight down the domination line as well. 741 for (const auto *DTNode = DTStartNode; DTNode != nullptr; 742 DTNode = DTNode->getIDom()) { 743 auto *DomBB = DTNode->getBlock(); 744 // Consider blocks which lie on one 'line'. 745 if (!PDT->dominates(PDTStartNode, PDT->getNode(DomBB))) 746 // If BB doesn't post dominate DomBB it will not post dominate dominators 747 // of DomBB as well. 748 break; 749 750 LoopBlock DomLoopBB = getLoopBlock(DomBB); 751 const LoopEdge Edge{DomLoopBB, LoopBB}; 752 // Don't propagate weight to blocks belonging to different loops. 753 if (!isLoopEnteringExitingEdge(Edge)) { 754 if (!updateEstimatedBlockWeight(DomLoopBB, BBWeight, BlockWorkList, 755 LoopWorkList)) 756 // If DomBB has weight set then all it's predecessors are already 757 // processed (since we propagate weight up to the top of IR each time). 758 break; 759 } else if (isLoopExitingEdge(Edge)) { 760 LoopWorkList.push_back(DomLoopBB); 761 } 762 } 763 } 764 765 std::optional<uint32_t> 766 BranchProbabilityInfo::getInitialEstimatedBlockWeight(const BasicBlock *BB) { 767 // Returns true if \p BB has call marked with "NoReturn" attribute. 768 auto hasNoReturn = [&](const BasicBlock *BB) { 769 for (const auto &I : reverse(*BB)) 770 if (const CallInst *CI = dyn_cast<CallInst>(&I)) 771 if (CI->hasFnAttr(Attribute::NoReturn)) 772 return true; 773 774 return false; 775 }; 776 777 // Important note regarding the order of checks. They are ordered by weight 778 // from lowest to highest. Doing that allows to avoid "unstable" results 779 // when several conditions heuristics can be applied simultaneously. 780 if (isa<UnreachableInst>(BB->getTerminator()) || 781 // If this block is terminated by a call to 782 // @llvm.experimental.deoptimize then treat it like an unreachable 783 // since it is expected to practically never execute. 784 // TODO: Should we actually treat as never returning call? 785 BB->getTerminatingDeoptimizeCall()) 786 return hasNoReturn(BB) 787 ? static_cast<uint32_t>(BlockExecWeight::NORETURN) 788 : static_cast<uint32_t>(BlockExecWeight::UNREACHABLE); 789 790 // Check if the block is 'unwind' handler of some invoke instruction. 791 for (const auto *Pred : predecessors(BB)) 792 if (Pred) 793 if (const auto *II = dyn_cast<InvokeInst>(Pred->getTerminator())) 794 if (II->getUnwindDest() == BB) 795 return static_cast<uint32_t>(BlockExecWeight::UNWIND); 796 797 // Check if the block contains 'cold' call. 798 for (const auto &I : *BB) 799 if (const CallInst *CI = dyn_cast<CallInst>(&I)) 800 if (CI->hasFnAttr(Attribute::Cold)) 801 return static_cast<uint32_t>(BlockExecWeight::COLD); 802 803 return std::nullopt; 804 } 805 806 // Does RPO traversal over all blocks in \p F and assigns weights to 807 // 'unreachable', 'noreturn', 'cold', 'unwind' blocks. In addition it does its 808 // best to propagate the weight to up/down the IR. 809 void BranchProbabilityInfo::computeEestimateBlockWeight( 810 const Function &F, DominatorTree *DT, PostDominatorTree *PDT) { 811 SmallVector<BasicBlock *, 8> BlockWorkList; 812 SmallVector<LoopBlock, 8> LoopWorkList; 813 814 // By doing RPO we make sure that all predecessors already have weights 815 // calculated before visiting theirs successors. 816 ReversePostOrderTraversal<const Function *> RPOT(&F); 817 for (const auto *BB : RPOT) 818 if (auto BBWeight = getInitialEstimatedBlockWeight(BB)) 819 // If we were able to find estimated weight for the block set it to this 820 // block and propagate up the IR. 821 propagateEstimatedBlockWeight(getLoopBlock(BB), DT, PDT, *BBWeight, 822 BlockWorkList, LoopWorkList); 823 824 // BlockWorklist/LoopWorkList contains blocks/loops with at least one 825 // successor/exit having estimated weight. Try to propagate weight to such 826 // blocks/loops from successors/exits. 827 // Process loops and blocks. Order is not important. 828 do { 829 while (!LoopWorkList.empty()) { 830 const LoopBlock LoopBB = LoopWorkList.pop_back_val(); 831 832 if (EstimatedLoopWeight.count(LoopBB.getLoopData())) 833 continue; 834 835 SmallVector<BasicBlock *, 4> Exits; 836 getLoopExitBlocks(LoopBB, Exits); 837 auto LoopWeight = getMaxEstimatedEdgeWeight( 838 LoopBB, make_range(Exits.begin(), Exits.end())); 839 840 if (LoopWeight) { 841 // If we never exit the loop then we can enter it once at maximum. 842 if (LoopWeight <= static_cast<uint32_t>(BlockExecWeight::UNREACHABLE)) 843 LoopWeight = static_cast<uint32_t>(BlockExecWeight::LOWEST_NON_ZERO); 844 845 EstimatedLoopWeight.insert({LoopBB.getLoopData(), *LoopWeight}); 846 // Add all blocks entering the loop into working list. 847 getLoopEnterBlocks(LoopBB, BlockWorkList); 848 } 849 } 850 851 while (!BlockWorkList.empty()) { 852 // We can reach here only if BlockWorkList is not empty. 853 const BasicBlock *BB = BlockWorkList.pop_back_val(); 854 if (EstimatedBlockWeight.count(BB)) 855 continue; 856 857 // We take maximum over all weights of successors. In other words we take 858 // weight of "hot" path. In theory we can probably find a better function 859 // which gives higher accuracy results (comparing to "maximum") but I 860 // can't 861 // think of any right now. And I doubt it will make any difference in 862 // practice. 863 const LoopBlock LoopBB = getLoopBlock(BB); 864 auto MaxWeight = getMaxEstimatedEdgeWeight(LoopBB, successors(BB)); 865 866 if (MaxWeight) 867 propagateEstimatedBlockWeight(LoopBB, DT, PDT, *MaxWeight, 868 BlockWorkList, LoopWorkList); 869 } 870 } while (!BlockWorkList.empty() || !LoopWorkList.empty()); 871 } 872 873 // Calculate edge probabilities based on block's estimated weight. 874 // Note that gathered weights were not scaled for loops. Thus edges entering 875 // and exiting loops requires special processing. 876 bool BranchProbabilityInfo::calcEstimatedHeuristics(const BasicBlock *BB) { 877 assert(BB->getTerminator()->getNumSuccessors() > 1 && 878 "expected more than one successor!"); 879 880 const LoopBlock LoopBB = getLoopBlock(BB); 881 882 SmallPtrSet<const BasicBlock *, 8> UnlikelyBlocks; 883 uint32_t TC = LBH_TAKEN_WEIGHT / LBH_NONTAKEN_WEIGHT; 884 if (LoopBB.getLoop()) 885 computeUnlikelySuccessors(BB, LoopBB.getLoop(), UnlikelyBlocks); 886 887 // Changed to 'true' if at least one successor has estimated weight. 888 bool FoundEstimatedWeight = false; 889 SmallVector<uint32_t, 4> SuccWeights; 890 uint64_t TotalWeight = 0; 891 // Go over all successors of BB and put their weights into SuccWeights. 892 for (const BasicBlock *SuccBB : successors(BB)) { 893 std::optional<uint32_t> Weight; 894 const LoopBlock SuccLoopBB = getLoopBlock(SuccBB); 895 const LoopEdge Edge{LoopBB, SuccLoopBB}; 896 897 Weight = getEstimatedEdgeWeight(Edge); 898 899 if (isLoopExitingEdge(Edge) && 900 // Avoid adjustment of ZERO weight since it should remain unchanged. 901 Weight != static_cast<uint32_t>(BlockExecWeight::ZERO)) { 902 // Scale down loop exiting weight by trip count. 903 Weight = std::max( 904 static_cast<uint32_t>(BlockExecWeight::LOWEST_NON_ZERO), 905 Weight.value_or(static_cast<uint32_t>(BlockExecWeight::DEFAULT)) / 906 TC); 907 } 908 bool IsUnlikelyEdge = LoopBB.getLoop() && UnlikelyBlocks.contains(SuccBB); 909 if (IsUnlikelyEdge && 910 // Avoid adjustment of ZERO weight since it should remain unchanged. 911 Weight != static_cast<uint32_t>(BlockExecWeight::ZERO)) { 912 // 'Unlikely' blocks have twice lower weight. 913 Weight = std::max( 914 static_cast<uint32_t>(BlockExecWeight::LOWEST_NON_ZERO), 915 Weight.value_or(static_cast<uint32_t>(BlockExecWeight::DEFAULT)) / 2); 916 } 917 918 if (Weight) 919 FoundEstimatedWeight = true; 920 921 auto WeightVal = 922 Weight.value_or(static_cast<uint32_t>(BlockExecWeight::DEFAULT)); 923 TotalWeight += WeightVal; 924 SuccWeights.push_back(WeightVal); 925 } 926 927 // If non of blocks have estimated weight bail out. 928 // If TotalWeight is 0 that means weight of each successor is 0 as well and 929 // equally likely. Bail out early to not deal with devision by zero. 930 if (!FoundEstimatedWeight || TotalWeight == 0) 931 return false; 932 933 assert(SuccWeights.size() == succ_size(BB) && "Missed successor?"); 934 const unsigned SuccCount = SuccWeights.size(); 935 936 // If the sum of weights does not fit in 32 bits, scale every weight down 937 // accordingly. 938 if (TotalWeight > UINT32_MAX) { 939 uint64_t ScalingFactor = TotalWeight / UINT32_MAX + 1; 940 TotalWeight = 0; 941 for (unsigned Idx = 0; Idx < SuccCount; ++Idx) { 942 SuccWeights[Idx] /= ScalingFactor; 943 if (SuccWeights[Idx] == static_cast<uint32_t>(BlockExecWeight::ZERO)) 944 SuccWeights[Idx] = 945 static_cast<uint32_t>(BlockExecWeight::LOWEST_NON_ZERO); 946 TotalWeight += SuccWeights[Idx]; 947 } 948 assert(TotalWeight <= UINT32_MAX && "Total weight overflows"); 949 } 950 951 // Finally set probabilities to edges according to estimated block weights. 952 SmallVector<BranchProbability, 4> EdgeProbabilities( 953 SuccCount, BranchProbability::getUnknown()); 954 955 for (unsigned Idx = 0; Idx < SuccCount; ++Idx) { 956 EdgeProbabilities[Idx] = 957 BranchProbability(SuccWeights[Idx], (uint32_t)TotalWeight); 958 } 959 setEdgeProbability(BB, EdgeProbabilities); 960 return true; 961 } 962 963 bool BranchProbabilityInfo::calcZeroHeuristics(const BasicBlock *BB, 964 const TargetLibraryInfo *TLI) { 965 const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()); 966 if (!BI || !BI->isConditional()) 967 return false; 968 969 Value *Cond = BI->getCondition(); 970 ICmpInst *CI = dyn_cast<ICmpInst>(Cond); 971 if (!CI) 972 return false; 973 974 auto GetConstantInt = [](Value *V) { 975 if (auto *I = dyn_cast<BitCastInst>(V)) 976 return dyn_cast<ConstantInt>(I->getOperand(0)); 977 return dyn_cast<ConstantInt>(V); 978 }; 979 980 Value *RHS = CI->getOperand(1); 981 ConstantInt *CV = GetConstantInt(RHS); 982 if (!CV) 983 return false; 984 985 // If the LHS is the result of AND'ing a value with a single bit bitmask, 986 // we don't have information about probabilities. 987 if (Instruction *LHS = dyn_cast<Instruction>(CI->getOperand(0))) 988 if (LHS->getOpcode() == Instruction::And) 989 if (ConstantInt *AndRHS = GetConstantInt(LHS->getOperand(1))) 990 if (AndRHS->getValue().isPowerOf2()) 991 return false; 992 993 // Check if the LHS is the return value of a library function 994 LibFunc Func = NumLibFuncs; 995 if (TLI) 996 if (CallInst *Call = dyn_cast<CallInst>(CI->getOperand(0))) 997 if (Function *CalledFn = Call->getCalledFunction()) 998 TLI->getLibFunc(*CalledFn, Func); 999 1000 ProbabilityTable::const_iterator Search; 1001 if (Func == LibFunc_strcasecmp || 1002 Func == LibFunc_strcmp || 1003 Func == LibFunc_strncasecmp || 1004 Func == LibFunc_strncmp || 1005 Func == LibFunc_memcmp || 1006 Func == LibFunc_bcmp) { 1007 Search = ICmpWithLibCallTable.find(CI->getPredicate()); 1008 if (Search == ICmpWithLibCallTable.end()) 1009 return false; 1010 } else if (CV->isZero()) { 1011 Search = ICmpWithZeroTable.find(CI->getPredicate()); 1012 if (Search == ICmpWithZeroTable.end()) 1013 return false; 1014 } else if (CV->isOne()) { 1015 Search = ICmpWithOneTable.find(CI->getPredicate()); 1016 if (Search == ICmpWithOneTable.end()) 1017 return false; 1018 } else if (CV->isMinusOne()) { 1019 Search = ICmpWithMinusOneTable.find(CI->getPredicate()); 1020 if (Search == ICmpWithMinusOneTable.end()) 1021 return false; 1022 } else { 1023 return false; 1024 } 1025 1026 setEdgeProbability(BB, Search->second); 1027 return true; 1028 } 1029 1030 bool BranchProbabilityInfo::calcFloatingPointHeuristics(const BasicBlock *BB) { 1031 const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()); 1032 if (!BI || !BI->isConditional()) 1033 return false; 1034 1035 Value *Cond = BI->getCondition(); 1036 FCmpInst *FCmp = dyn_cast<FCmpInst>(Cond); 1037 if (!FCmp) 1038 return false; 1039 1040 ProbabilityList ProbList; 1041 if (FCmp->isEquality()) { 1042 ProbList = !FCmp->isTrueWhenEqual() ? 1043 // f1 == f2 -> Unlikely 1044 ProbabilityList({FPTakenProb, FPUntakenProb}) : 1045 // f1 != f2 -> Likely 1046 ProbabilityList({FPUntakenProb, FPTakenProb}); 1047 } else { 1048 auto Search = FCmpTable.find(FCmp->getPredicate()); 1049 if (Search == FCmpTable.end()) 1050 return false; 1051 ProbList = Search->second; 1052 } 1053 1054 setEdgeProbability(BB, ProbList); 1055 return true; 1056 } 1057 1058 void BranchProbabilityInfo::releaseMemory() { 1059 Probs.clear(); 1060 Handles.clear(); 1061 } 1062 1063 bool BranchProbabilityInfo::invalidate(Function &, const PreservedAnalyses &PA, 1064 FunctionAnalysisManager::Invalidator &) { 1065 // Check whether the analysis, all analyses on functions, or the function's 1066 // CFG have been preserved. 1067 auto PAC = PA.getChecker<BranchProbabilityAnalysis>(); 1068 return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() || 1069 PAC.preservedSet<CFGAnalyses>()); 1070 } 1071 1072 void BranchProbabilityInfo::print(raw_ostream &OS) const { 1073 OS << "---- Branch Probabilities ----\n"; 1074 // We print the probabilities from the last function the analysis ran over, 1075 // or the function it is currently running over. 1076 assert(LastF && "Cannot print prior to running over a function"); 1077 for (const auto &BI : *LastF) { 1078 for (const BasicBlock *Succ : successors(&BI)) 1079 printEdgeProbability(OS << " ", &BI, Succ); 1080 } 1081 } 1082 1083 bool BranchProbabilityInfo:: 1084 isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const { 1085 // Hot probability is at least 4/5 = 80% 1086 // FIXME: Compare against a static "hot" BranchProbability. 1087 return getEdgeProbability(Src, Dst) > BranchProbability(4, 5); 1088 } 1089 1090 /// Get the raw edge probability for the edge. If can't find it, return a 1091 /// default probability 1/N where N is the number of successors. Here an edge is 1092 /// specified using PredBlock and an 1093 /// index to the successors. 1094 BranchProbability 1095 BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src, 1096 unsigned IndexInSuccessors) const { 1097 auto I = Probs.find(std::make_pair(Src, IndexInSuccessors)); 1098 assert((Probs.end() == Probs.find(std::make_pair(Src, 0))) == 1099 (Probs.end() == I) && 1100 "Probability for I-th successor must always be defined along with the " 1101 "probability for the first successor"); 1102 1103 if (I != Probs.end()) 1104 return I->second; 1105 1106 return {1, static_cast<uint32_t>(succ_size(Src))}; 1107 } 1108 1109 BranchProbability 1110 BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src, 1111 const_succ_iterator Dst) const { 1112 return getEdgeProbability(Src, Dst.getSuccessorIndex()); 1113 } 1114 1115 /// Get the raw edge probability calculated for the block pair. This returns the 1116 /// sum of all raw edge probabilities from Src to Dst. 1117 BranchProbability 1118 BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src, 1119 const BasicBlock *Dst) const { 1120 if (!Probs.count(std::make_pair(Src, 0))) 1121 return BranchProbability(llvm::count(successors(Src), Dst), succ_size(Src)); 1122 1123 auto Prob = BranchProbability::getZero(); 1124 for (const_succ_iterator I = succ_begin(Src), E = succ_end(Src); I != E; ++I) 1125 if (*I == Dst) 1126 Prob += Probs.find(std::make_pair(Src, I.getSuccessorIndex()))->second; 1127 1128 return Prob; 1129 } 1130 1131 /// Set the edge probability for all edges at once. 1132 void BranchProbabilityInfo::setEdgeProbability( 1133 const BasicBlock *Src, const SmallVectorImpl<BranchProbability> &Probs) { 1134 assert(Src->getTerminator()->getNumSuccessors() == Probs.size()); 1135 eraseBlock(Src); // Erase stale data if any. 1136 if (Probs.size() == 0) 1137 return; // Nothing to set. 1138 1139 Handles.insert(BasicBlockCallbackVH(Src, this)); 1140 uint64_t TotalNumerator = 0; 1141 for (unsigned SuccIdx = 0; SuccIdx < Probs.size(); ++SuccIdx) { 1142 this->Probs[std::make_pair(Src, SuccIdx)] = Probs[SuccIdx]; 1143 LLVM_DEBUG(dbgs() << "set edge " << Src->getName() << " -> " << SuccIdx 1144 << " successor probability to " << Probs[SuccIdx] 1145 << "\n"); 1146 TotalNumerator += Probs[SuccIdx].getNumerator(); 1147 } 1148 1149 // Because of rounding errors the total probability cannot be checked to be 1150 // 1.0 exactly. That is TotalNumerator == BranchProbability::getDenominator. 1151 // Instead, every single probability in Probs must be as accurate as possible. 1152 // This results in error 1/denominator at most, thus the total absolute error 1153 // should be within Probs.size / BranchProbability::getDenominator. 1154 assert(TotalNumerator <= BranchProbability::getDenominator() + Probs.size()); 1155 assert(TotalNumerator >= BranchProbability::getDenominator() - Probs.size()); 1156 (void)TotalNumerator; 1157 } 1158 1159 void BranchProbabilityInfo::copyEdgeProbabilities(BasicBlock *Src, 1160 BasicBlock *Dst) { 1161 eraseBlock(Dst); // Erase stale data if any. 1162 unsigned NumSuccessors = Src->getTerminator()->getNumSuccessors(); 1163 assert(NumSuccessors == Dst->getTerminator()->getNumSuccessors()); 1164 if (NumSuccessors == 0) 1165 return; // Nothing to set. 1166 if (!this->Probs.contains(std::make_pair(Src, 0))) 1167 return; // No probability is set for edges from Src. Keep the same for Dst. 1168 1169 Handles.insert(BasicBlockCallbackVH(Dst, this)); 1170 for (unsigned SuccIdx = 0; SuccIdx < NumSuccessors; ++SuccIdx) { 1171 auto Prob = this->Probs[std::make_pair(Src, SuccIdx)]; 1172 this->Probs[std::make_pair(Dst, SuccIdx)] = Prob; 1173 LLVM_DEBUG(dbgs() << "set edge " << Dst->getName() << " -> " << SuccIdx 1174 << " successor probability to " << Prob << "\n"); 1175 } 1176 } 1177 1178 void BranchProbabilityInfo::swapSuccEdgesProbabilities(const BasicBlock *Src) { 1179 assert(Src->getTerminator()->getNumSuccessors() == 2); 1180 if (!Probs.contains(std::make_pair(Src, 0))) 1181 return; // No probability is set for edges from Src 1182 assert(Probs.contains(std::make_pair(Src, 1))); 1183 std::swap(Probs[std::make_pair(Src, 0)], Probs[std::make_pair(Src, 1)]); 1184 } 1185 1186 raw_ostream & 1187 BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS, 1188 const BasicBlock *Src, 1189 const BasicBlock *Dst) const { 1190 const BranchProbability Prob = getEdgeProbability(Src, Dst); 1191 OS << "edge "; 1192 Src->printAsOperand(OS, false, Src->getModule()); 1193 OS << " -> "; 1194 Dst->printAsOperand(OS, false, Dst->getModule()); 1195 OS << " probability is " << Prob 1196 << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n"); 1197 1198 return OS; 1199 } 1200 1201 void BranchProbabilityInfo::eraseBlock(const BasicBlock *BB) { 1202 LLVM_DEBUG(dbgs() << "eraseBlock " << BB->getName() << "\n"); 1203 1204 // Note that we cannot use successors of BB because the terminator of BB may 1205 // have changed when eraseBlock is called as a BasicBlockCallbackVH callback. 1206 // Instead we remove prob data for the block by iterating successors by their 1207 // indices from 0 till the last which exists. There could not be prob data for 1208 // a pair (BB, N) if there is no data for (BB, N-1) because the data is always 1209 // set for all successors from 0 to M at once by the method 1210 // setEdgeProbability(). 1211 Handles.erase(BasicBlockCallbackVH(BB, this)); 1212 for (unsigned I = 0;; ++I) { 1213 auto MapI = Probs.find(std::make_pair(BB, I)); 1214 if (MapI == Probs.end()) { 1215 assert(Probs.count(std::make_pair(BB, I + 1)) == 0 && 1216 "Must be no more successors"); 1217 return; 1218 } 1219 Probs.erase(MapI); 1220 } 1221 } 1222 1223 void BranchProbabilityInfo::calculate(const Function &F, const LoopInfo &LoopI, 1224 const TargetLibraryInfo *TLI, 1225 DominatorTree *DT, 1226 PostDominatorTree *PDT) { 1227 LLVM_DEBUG(dbgs() << "---- Branch Probability Info : " << F.getName() 1228 << " ----\n\n"); 1229 LastF = &F; // Store the last function we ran on for printing. 1230 LI = &LoopI; 1231 1232 SccI = std::make_unique<SccInfo>(F); 1233 1234 assert(EstimatedBlockWeight.empty()); 1235 assert(EstimatedLoopWeight.empty()); 1236 1237 std::unique_ptr<DominatorTree> DTPtr; 1238 std::unique_ptr<PostDominatorTree> PDTPtr; 1239 1240 if (!DT) { 1241 DTPtr = std::make_unique<DominatorTree>(const_cast<Function &>(F)); 1242 DT = DTPtr.get(); 1243 } 1244 1245 if (!PDT) { 1246 PDTPtr = std::make_unique<PostDominatorTree>(const_cast<Function &>(F)); 1247 PDT = PDTPtr.get(); 1248 } 1249 1250 computeEestimateBlockWeight(F, DT, PDT); 1251 1252 // Walk the basic blocks in post-order so that we can build up state about 1253 // the successors of a block iteratively. 1254 for (const auto *BB : post_order(&F.getEntryBlock())) { 1255 LLVM_DEBUG(dbgs() << "Computing probabilities for " << BB->getName() 1256 << "\n"); 1257 // If there is no at least two successors, no sense to set probability. 1258 if (BB->getTerminator()->getNumSuccessors() < 2) 1259 continue; 1260 if (calcMetadataWeights(BB)) 1261 continue; 1262 if (calcEstimatedHeuristics(BB)) 1263 continue; 1264 if (calcPointerHeuristics(BB)) 1265 continue; 1266 if (calcZeroHeuristics(BB, TLI)) 1267 continue; 1268 if (calcFloatingPointHeuristics(BB)) 1269 continue; 1270 } 1271 1272 EstimatedLoopWeight.clear(); 1273 EstimatedBlockWeight.clear(); 1274 SccI.reset(); 1275 1276 if (PrintBranchProb && 1277 (PrintBranchProbFuncName.empty() || 1278 F.getName().equals(PrintBranchProbFuncName))) { 1279 print(dbgs()); 1280 } 1281 } 1282 1283 void BranchProbabilityInfoWrapperPass::getAnalysisUsage( 1284 AnalysisUsage &AU) const { 1285 // We require DT so it's available when LI is available. The LI updating code 1286 // asserts that DT is also present so if we don't make sure that we have DT 1287 // here, that assert will trigger. 1288 AU.addRequired<DominatorTreeWrapperPass>(); 1289 AU.addRequired<LoopInfoWrapperPass>(); 1290 AU.addRequired<TargetLibraryInfoWrapperPass>(); 1291 AU.addRequired<DominatorTreeWrapperPass>(); 1292 AU.addRequired<PostDominatorTreeWrapperPass>(); 1293 AU.setPreservesAll(); 1294 } 1295 1296 bool BranchProbabilityInfoWrapperPass::runOnFunction(Function &F) { 1297 const LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 1298 const TargetLibraryInfo &TLI = 1299 getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F); 1300 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 1301 PostDominatorTree &PDT = 1302 getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree(); 1303 BPI.calculate(F, LI, &TLI, &DT, &PDT); 1304 return false; 1305 } 1306 1307 void BranchProbabilityInfoWrapperPass::releaseMemory() { BPI.releaseMemory(); } 1308 1309 void BranchProbabilityInfoWrapperPass::print(raw_ostream &OS, 1310 const Module *) const { 1311 BPI.print(OS); 1312 } 1313 1314 AnalysisKey BranchProbabilityAnalysis::Key; 1315 BranchProbabilityInfo 1316 BranchProbabilityAnalysis::run(Function &F, FunctionAnalysisManager &AM) { 1317 auto &LI = AM.getResult<LoopAnalysis>(F); 1318 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F); 1319 auto &DT = AM.getResult<DominatorTreeAnalysis>(F); 1320 auto &PDT = AM.getResult<PostDominatorTreeAnalysis>(F); 1321 BranchProbabilityInfo BPI; 1322 BPI.calculate(F, LI, &TLI, &DT, &PDT); 1323 return BPI; 1324 } 1325 1326 PreservedAnalyses 1327 BranchProbabilityPrinterPass::run(Function &F, FunctionAnalysisManager &AM) { 1328 OS << "Printing analysis 'Branch Probability Analysis' for function '" 1329 << F.getName() << "':\n"; 1330 AM.getResult<BranchProbabilityAnalysis>(F).print(OS); 1331 return PreservedAnalyses::all(); 1332 } 1333