1 //===-- BranchProbabilityInfo.cpp - Branch Probability Analysis -----------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // Loops should be simplified before this analysis. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/Analysis/BranchProbabilityInfo.h" 15 #include "llvm/ADT/PostOrderIterator.h" 16 #include "llvm/Analysis/LoopInfo.h" 17 #include "llvm/IR/CFG.h" 18 #include "llvm/IR/Constants.h" 19 #include "llvm/IR/Function.h" 20 #include "llvm/IR/Instructions.h" 21 #include "llvm/IR/LLVMContext.h" 22 #include "llvm/IR/Metadata.h" 23 #include "llvm/Support/Debug.h" 24 #include "llvm/Support/raw_ostream.h" 25 26 using namespace llvm; 27 28 #define DEBUG_TYPE "branch-prob" 29 30 INITIALIZE_PASS_BEGIN(BranchProbabilityInfoWrapperPass, "branch-prob", 31 "Branch Probability Analysis", false, true) 32 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) 33 INITIALIZE_PASS_END(BranchProbabilityInfoWrapperPass, "branch-prob", 34 "Branch Probability Analysis", false, true) 35 36 char BranchProbabilityInfoWrapperPass::ID = 0; 37 38 // Weights are for internal use only. They are used by heuristics to help to 39 // estimate edges' probability. Example: 40 // 41 // Using "Loop Branch Heuristics" we predict weights of edges for the 42 // block BB2. 43 // ... 44 // | 45 // V 46 // BB1<-+ 47 // | | 48 // | | (Weight = 124) 49 // V | 50 // BB2--+ 51 // | 52 // | (Weight = 4) 53 // V 54 // BB3 55 // 56 // Probability of the edge BB2->BB1 = 124 / (124 + 4) = 0.96875 57 // Probability of the edge BB2->BB3 = 4 / (124 + 4) = 0.03125 58 static const uint32_t LBH_TAKEN_WEIGHT = 124; 59 static const uint32_t LBH_NONTAKEN_WEIGHT = 4; 60 61 /// \brief Unreachable-terminating branch taken weight. 62 /// 63 /// This is the weight for a branch being taken to a block that terminates 64 /// (eventually) in unreachable. These are predicted as unlikely as possible. 65 static const uint32_t UR_TAKEN_WEIGHT = 1; 66 67 /// \brief Unreachable-terminating branch not-taken weight. 68 /// 69 /// This is the weight for a branch not being taken toward a block that 70 /// terminates (eventually) in unreachable. Such a branch is essentially never 71 /// taken. Set the weight to an absurdly high value so that nested loops don't 72 /// easily subsume it. 73 static const uint32_t UR_NONTAKEN_WEIGHT = 1024*1024 - 1; 74 75 /// \brief Weight for a branch taken going into a cold block. 76 /// 77 /// This is the weight for a branch taken toward a block marked 78 /// cold. A block is marked cold if it's postdominated by a 79 /// block containing a call to a cold function. Cold functions 80 /// are those marked with attribute 'cold'. 81 static const uint32_t CC_TAKEN_WEIGHT = 4; 82 83 /// \brief Weight for a branch not-taken into a cold block. 84 /// 85 /// This is the weight for a branch not taken toward a block marked 86 /// cold. 87 static const uint32_t CC_NONTAKEN_WEIGHT = 64; 88 89 static const uint32_t PH_TAKEN_WEIGHT = 20; 90 static const uint32_t PH_NONTAKEN_WEIGHT = 12; 91 92 static const uint32_t ZH_TAKEN_WEIGHT = 20; 93 static const uint32_t ZH_NONTAKEN_WEIGHT = 12; 94 95 static const uint32_t FPH_TAKEN_WEIGHT = 20; 96 static const uint32_t FPH_NONTAKEN_WEIGHT = 12; 97 98 /// \brief Invoke-terminating normal branch taken weight 99 /// 100 /// This is the weight for branching to the normal destination of an invoke 101 /// instruction. We expect this to happen most of the time. Set the weight to an 102 /// absurdly high value so that nested loops subsume it. 103 static const uint32_t IH_TAKEN_WEIGHT = 1024 * 1024 - 1; 104 105 /// \brief Invoke-terminating normal branch not-taken weight. 106 /// 107 /// This is the weight for branching to the unwind destination of an invoke 108 /// instruction. This is essentially never taken. 109 static const uint32_t IH_NONTAKEN_WEIGHT = 1; 110 111 /// \brief Calculate edge weights for successors lead to unreachable. 112 /// 113 /// Predict that a successor which leads necessarily to an 114 /// unreachable-terminated block as extremely unlikely. 115 bool BranchProbabilityInfo::calcUnreachableHeuristics(const BasicBlock *BB) { 116 const TerminatorInst *TI = BB->getTerminator(); 117 if (TI->getNumSuccessors() == 0) { 118 if (isa<UnreachableInst>(TI) || 119 // If this block is terminated by a call to 120 // @llvm.experimental.deoptimize then treat it like an unreachable since 121 // the @llvm.experimental.deoptimize call is expected to practically 122 // never execute. 123 BB->getTerminatingDeoptimizeCall()) 124 PostDominatedByUnreachable.insert(BB); 125 return false; 126 } 127 128 SmallVector<unsigned, 4> UnreachableEdges; 129 SmallVector<unsigned, 4> ReachableEdges; 130 131 for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) { 132 if (PostDominatedByUnreachable.count(*I)) 133 UnreachableEdges.push_back(I.getSuccessorIndex()); 134 else 135 ReachableEdges.push_back(I.getSuccessorIndex()); 136 } 137 138 // If all successors are in the set of blocks post-dominated by unreachable, 139 // this block is too. 140 if (UnreachableEdges.size() == TI->getNumSuccessors()) 141 PostDominatedByUnreachable.insert(BB); 142 143 // Skip probabilities if this block has a single successor or if all were 144 // reachable. 145 if (TI->getNumSuccessors() == 1 || UnreachableEdges.empty()) 146 return false; 147 148 // If the terminator is an InvokeInst, check only the normal destination block 149 // as the unwind edge of InvokeInst is also very unlikely taken. 150 if (auto *II = dyn_cast<InvokeInst>(TI)) 151 if (PostDominatedByUnreachable.count(II->getNormalDest())) { 152 PostDominatedByUnreachable.insert(BB); 153 // Return false here so that edge weights for InvokeInst could be decided 154 // in calcInvokeHeuristics(). 155 return false; 156 } 157 158 if (ReachableEdges.empty()) { 159 BranchProbability Prob(1, UnreachableEdges.size()); 160 for (unsigned SuccIdx : UnreachableEdges) 161 setEdgeProbability(BB, SuccIdx, Prob); 162 return true; 163 } 164 165 BranchProbability UnreachableProb(UR_TAKEN_WEIGHT, 166 (UR_TAKEN_WEIGHT + UR_NONTAKEN_WEIGHT) * 167 UnreachableEdges.size()); 168 BranchProbability ReachableProb(UR_NONTAKEN_WEIGHT, 169 (UR_TAKEN_WEIGHT + UR_NONTAKEN_WEIGHT) * 170 ReachableEdges.size()); 171 172 for (unsigned SuccIdx : UnreachableEdges) 173 setEdgeProbability(BB, SuccIdx, UnreachableProb); 174 for (unsigned SuccIdx : ReachableEdges) 175 setEdgeProbability(BB, SuccIdx, ReachableProb); 176 177 return true; 178 } 179 180 // Propagate existing explicit probabilities from either profile data or 181 // 'expect' intrinsic processing. 182 bool BranchProbabilityInfo::calcMetadataWeights(const BasicBlock *BB) { 183 const TerminatorInst *TI = BB->getTerminator(); 184 if (TI->getNumSuccessors() == 1) 185 return false; 186 if (!isa<BranchInst>(TI) && !isa<SwitchInst>(TI)) 187 return false; 188 189 MDNode *WeightsNode = TI->getMetadata(LLVMContext::MD_prof); 190 if (!WeightsNode) 191 return false; 192 193 // Check that the number of successors is manageable. 194 assert(TI->getNumSuccessors() < UINT32_MAX && "Too many successors"); 195 196 // Ensure there are weights for all of the successors. Note that the first 197 // operand to the metadata node is a name, not a weight. 198 if (WeightsNode->getNumOperands() != TI->getNumSuccessors() + 1) 199 return false; 200 201 // Build up the final weights that will be used in a temporary buffer. 202 // Compute the sum of all weights to later decide whether they need to 203 // be scaled to fit in 32 bits. 204 uint64_t WeightSum = 0; 205 SmallVector<uint32_t, 2> Weights; 206 Weights.reserve(TI->getNumSuccessors()); 207 for (unsigned i = 1, e = WeightsNode->getNumOperands(); i != e; ++i) { 208 ConstantInt *Weight = 209 mdconst::dyn_extract<ConstantInt>(WeightsNode->getOperand(i)); 210 if (!Weight) 211 return false; 212 assert(Weight->getValue().getActiveBits() <= 32 && 213 "Too many bits for uint32_t"); 214 Weights.push_back(Weight->getZExtValue()); 215 WeightSum += Weights.back(); 216 } 217 assert(Weights.size() == TI->getNumSuccessors() && "Checked above"); 218 219 // If the sum of weights does not fit in 32 bits, scale every weight down 220 // accordingly. 221 uint64_t ScalingFactor = 222 (WeightSum > UINT32_MAX) ? WeightSum / UINT32_MAX + 1 : 1; 223 224 WeightSum = 0; 225 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) { 226 Weights[i] /= ScalingFactor; 227 WeightSum += Weights[i]; 228 } 229 230 if (WeightSum == 0) { 231 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 232 setEdgeProbability(BB, i, {1, e}); 233 } else { 234 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 235 setEdgeProbability(BB, i, {Weights[i], static_cast<uint32_t>(WeightSum)}); 236 } 237 238 assert(WeightSum <= UINT32_MAX && 239 "Expected weights to scale down to 32 bits"); 240 241 return true; 242 } 243 244 /// \brief Calculate edge weights for edges leading to cold blocks. 245 /// 246 /// A cold block is one post-dominated by a block with a call to a 247 /// cold function. Those edges are unlikely to be taken, so we give 248 /// them relatively low weight. 249 /// 250 /// Return true if we could compute the weights for cold edges. 251 /// Return false, otherwise. 252 bool BranchProbabilityInfo::calcColdCallHeuristics(const BasicBlock *BB) { 253 const TerminatorInst *TI = BB->getTerminator(); 254 if (TI->getNumSuccessors() == 0) 255 return false; 256 257 // Determine which successors are post-dominated by a cold block. 258 SmallVector<unsigned, 4> ColdEdges; 259 SmallVector<unsigned, 4> NormalEdges; 260 for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) 261 if (PostDominatedByColdCall.count(*I)) 262 ColdEdges.push_back(I.getSuccessorIndex()); 263 else 264 NormalEdges.push_back(I.getSuccessorIndex()); 265 266 // If all successors are in the set of blocks post-dominated by cold calls, 267 // this block is in the set post-dominated by cold calls. 268 if (ColdEdges.size() == TI->getNumSuccessors()) 269 PostDominatedByColdCall.insert(BB); 270 else { 271 // Otherwise, if the block itself contains a cold function, add it to the 272 // set of blocks postdominated by a cold call. 273 assert(!PostDominatedByColdCall.count(BB)); 274 for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I != E; ++I) 275 if (const CallInst *CI = dyn_cast<CallInst>(I)) 276 if (CI->hasFnAttr(Attribute::Cold)) { 277 PostDominatedByColdCall.insert(BB); 278 break; 279 } 280 } 281 282 // Skip probabilities if this block has a single successor. 283 if (TI->getNumSuccessors() == 1 || ColdEdges.empty()) 284 return false; 285 286 if (NormalEdges.empty()) { 287 BranchProbability Prob(1, ColdEdges.size()); 288 for (unsigned SuccIdx : ColdEdges) 289 setEdgeProbability(BB, SuccIdx, Prob); 290 return true; 291 } 292 293 BranchProbability ColdProb(CC_TAKEN_WEIGHT, 294 (CC_TAKEN_WEIGHT + CC_NONTAKEN_WEIGHT) * 295 ColdEdges.size()); 296 BranchProbability NormalProb(CC_NONTAKEN_WEIGHT, 297 (CC_TAKEN_WEIGHT + CC_NONTAKEN_WEIGHT) * 298 NormalEdges.size()); 299 300 for (unsigned SuccIdx : ColdEdges) 301 setEdgeProbability(BB, SuccIdx, ColdProb); 302 for (unsigned SuccIdx : NormalEdges) 303 setEdgeProbability(BB, SuccIdx, NormalProb); 304 305 return true; 306 } 307 308 // Calculate Edge Weights using "Pointer Heuristics". Predict a comparsion 309 // between two pointer or pointer and NULL will fail. 310 bool BranchProbabilityInfo::calcPointerHeuristics(const BasicBlock *BB) { 311 const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()); 312 if (!BI || !BI->isConditional()) 313 return false; 314 315 Value *Cond = BI->getCondition(); 316 ICmpInst *CI = dyn_cast<ICmpInst>(Cond); 317 if (!CI || !CI->isEquality()) 318 return false; 319 320 Value *LHS = CI->getOperand(0); 321 322 if (!LHS->getType()->isPointerTy()) 323 return false; 324 325 assert(CI->getOperand(1)->getType()->isPointerTy()); 326 327 // p != 0 -> isProb = true 328 // p == 0 -> isProb = false 329 // p != q -> isProb = true 330 // p == q -> isProb = false; 331 unsigned TakenIdx = 0, NonTakenIdx = 1; 332 bool isProb = CI->getPredicate() == ICmpInst::ICMP_NE; 333 if (!isProb) 334 std::swap(TakenIdx, NonTakenIdx); 335 336 BranchProbability TakenProb(PH_TAKEN_WEIGHT, 337 PH_TAKEN_WEIGHT + PH_NONTAKEN_WEIGHT); 338 setEdgeProbability(BB, TakenIdx, TakenProb); 339 setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl()); 340 return true; 341 } 342 343 // Calculate Edge Weights using "Loop Branch Heuristics". Predict backedges 344 // as taken, exiting edges as not-taken. 345 bool BranchProbabilityInfo::calcLoopBranchHeuristics(const BasicBlock *BB, 346 const LoopInfo &LI) { 347 Loop *L = LI.getLoopFor(BB); 348 if (!L) 349 return false; 350 351 SmallVector<unsigned, 8> BackEdges; 352 SmallVector<unsigned, 8> ExitingEdges; 353 SmallVector<unsigned, 8> InEdges; // Edges from header to the loop. 354 355 for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) { 356 if (!L->contains(*I)) 357 ExitingEdges.push_back(I.getSuccessorIndex()); 358 else if (L->getHeader() == *I) 359 BackEdges.push_back(I.getSuccessorIndex()); 360 else 361 InEdges.push_back(I.getSuccessorIndex()); 362 } 363 364 if (BackEdges.empty() && ExitingEdges.empty()) 365 return false; 366 367 // Collect the sum of probabilities of back-edges/in-edges/exiting-edges, and 368 // normalize them so that they sum up to one. 369 BranchProbability Probs[] = {BranchProbability::getZero(), 370 BranchProbability::getZero(), 371 BranchProbability::getZero()}; 372 unsigned Denom = (BackEdges.empty() ? 0 : LBH_TAKEN_WEIGHT) + 373 (InEdges.empty() ? 0 : LBH_TAKEN_WEIGHT) + 374 (ExitingEdges.empty() ? 0 : LBH_NONTAKEN_WEIGHT); 375 if (!BackEdges.empty()) 376 Probs[0] = BranchProbability(LBH_TAKEN_WEIGHT, Denom); 377 if (!InEdges.empty()) 378 Probs[1] = BranchProbability(LBH_TAKEN_WEIGHT, Denom); 379 if (!ExitingEdges.empty()) 380 Probs[2] = BranchProbability(LBH_NONTAKEN_WEIGHT, Denom); 381 382 if (uint32_t numBackEdges = BackEdges.size()) { 383 auto Prob = Probs[0] / numBackEdges; 384 for (unsigned SuccIdx : BackEdges) 385 setEdgeProbability(BB, SuccIdx, Prob); 386 } 387 388 if (uint32_t numInEdges = InEdges.size()) { 389 auto Prob = Probs[1] / numInEdges; 390 for (unsigned SuccIdx : InEdges) 391 setEdgeProbability(BB, SuccIdx, Prob); 392 } 393 394 if (uint32_t numExitingEdges = ExitingEdges.size()) { 395 auto Prob = Probs[2] / numExitingEdges; 396 for (unsigned SuccIdx : ExitingEdges) 397 setEdgeProbability(BB, SuccIdx, Prob); 398 } 399 400 return true; 401 } 402 403 bool BranchProbabilityInfo::calcZeroHeuristics(const BasicBlock *BB) { 404 const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()); 405 if (!BI || !BI->isConditional()) 406 return false; 407 408 Value *Cond = BI->getCondition(); 409 ICmpInst *CI = dyn_cast<ICmpInst>(Cond); 410 if (!CI) 411 return false; 412 413 Value *RHS = CI->getOperand(1); 414 ConstantInt *CV = dyn_cast<ConstantInt>(RHS); 415 if (!CV) 416 return false; 417 418 // If the LHS is the result of AND'ing a value with a single bit bitmask, 419 // we don't have information about probabilities. 420 if (Instruction *LHS = dyn_cast<Instruction>(CI->getOperand(0))) 421 if (LHS->getOpcode() == Instruction::And) 422 if (ConstantInt *AndRHS = dyn_cast<ConstantInt>(LHS->getOperand(1))) 423 if (AndRHS->getUniqueInteger().isPowerOf2()) 424 return false; 425 426 bool isProb; 427 if (CV->isZero()) { 428 switch (CI->getPredicate()) { 429 case CmpInst::ICMP_EQ: 430 // X == 0 -> Unlikely 431 isProb = false; 432 break; 433 case CmpInst::ICMP_NE: 434 // X != 0 -> Likely 435 isProb = true; 436 break; 437 case CmpInst::ICMP_SLT: 438 // X < 0 -> Unlikely 439 isProb = false; 440 break; 441 case CmpInst::ICMP_SGT: 442 // X > 0 -> Likely 443 isProb = true; 444 break; 445 default: 446 return false; 447 } 448 } else if (CV->isOne() && CI->getPredicate() == CmpInst::ICMP_SLT) { 449 // InstCombine canonicalizes X <= 0 into X < 1. 450 // X <= 0 -> Unlikely 451 isProb = false; 452 } else if (CV->isAllOnesValue()) { 453 switch (CI->getPredicate()) { 454 case CmpInst::ICMP_EQ: 455 // X == -1 -> Unlikely 456 isProb = false; 457 break; 458 case CmpInst::ICMP_NE: 459 // X != -1 -> Likely 460 isProb = true; 461 break; 462 case CmpInst::ICMP_SGT: 463 // InstCombine canonicalizes X >= 0 into X > -1. 464 // X >= 0 -> Likely 465 isProb = true; 466 break; 467 default: 468 return false; 469 } 470 } else { 471 return false; 472 } 473 474 unsigned TakenIdx = 0, NonTakenIdx = 1; 475 476 if (!isProb) 477 std::swap(TakenIdx, NonTakenIdx); 478 479 BranchProbability TakenProb(ZH_TAKEN_WEIGHT, 480 ZH_TAKEN_WEIGHT + ZH_NONTAKEN_WEIGHT); 481 setEdgeProbability(BB, TakenIdx, TakenProb); 482 setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl()); 483 return true; 484 } 485 486 bool BranchProbabilityInfo::calcFloatingPointHeuristics(const BasicBlock *BB) { 487 const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()); 488 if (!BI || !BI->isConditional()) 489 return false; 490 491 Value *Cond = BI->getCondition(); 492 FCmpInst *FCmp = dyn_cast<FCmpInst>(Cond); 493 if (!FCmp) 494 return false; 495 496 bool isProb; 497 if (FCmp->isEquality()) { 498 // f1 == f2 -> Unlikely 499 // f1 != f2 -> Likely 500 isProb = !FCmp->isTrueWhenEqual(); 501 } else if (FCmp->getPredicate() == FCmpInst::FCMP_ORD) { 502 // !isnan -> Likely 503 isProb = true; 504 } else if (FCmp->getPredicate() == FCmpInst::FCMP_UNO) { 505 // isnan -> Unlikely 506 isProb = false; 507 } else { 508 return false; 509 } 510 511 unsigned TakenIdx = 0, NonTakenIdx = 1; 512 513 if (!isProb) 514 std::swap(TakenIdx, NonTakenIdx); 515 516 BranchProbability TakenProb(FPH_TAKEN_WEIGHT, 517 FPH_TAKEN_WEIGHT + FPH_NONTAKEN_WEIGHT); 518 setEdgeProbability(BB, TakenIdx, TakenProb); 519 setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl()); 520 return true; 521 } 522 523 bool BranchProbabilityInfo::calcInvokeHeuristics(const BasicBlock *BB) { 524 const InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator()); 525 if (!II) 526 return false; 527 528 BranchProbability TakenProb(IH_TAKEN_WEIGHT, 529 IH_TAKEN_WEIGHT + IH_NONTAKEN_WEIGHT); 530 setEdgeProbability(BB, 0 /*Index for Normal*/, TakenProb); 531 setEdgeProbability(BB, 1 /*Index for Unwind*/, TakenProb.getCompl()); 532 return true; 533 } 534 535 void BranchProbabilityInfo::releaseMemory() { 536 Probs.clear(); 537 } 538 539 void BranchProbabilityInfo::print(raw_ostream &OS) const { 540 OS << "---- Branch Probabilities ----\n"; 541 // We print the probabilities from the last function the analysis ran over, 542 // or the function it is currently running over. 543 assert(LastF && "Cannot print prior to running over a function"); 544 for (const auto &BI : *LastF) { 545 for (succ_const_iterator SI = succ_begin(&BI), SE = succ_end(&BI); SI != SE; 546 ++SI) { 547 printEdgeProbability(OS << " ", &BI, *SI); 548 } 549 } 550 } 551 552 bool BranchProbabilityInfo:: 553 isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const { 554 // Hot probability is at least 4/5 = 80% 555 // FIXME: Compare against a static "hot" BranchProbability. 556 return getEdgeProbability(Src, Dst) > BranchProbability(4, 5); 557 } 558 559 const BasicBlock * 560 BranchProbabilityInfo::getHotSucc(const BasicBlock *BB) const { 561 auto MaxProb = BranchProbability::getZero(); 562 const BasicBlock *MaxSucc = nullptr; 563 564 for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) { 565 const BasicBlock *Succ = *I; 566 auto Prob = getEdgeProbability(BB, Succ); 567 if (Prob > MaxProb) { 568 MaxProb = Prob; 569 MaxSucc = Succ; 570 } 571 } 572 573 // Hot probability is at least 4/5 = 80% 574 if (MaxProb > BranchProbability(4, 5)) 575 return MaxSucc; 576 577 return nullptr; 578 } 579 580 /// Get the raw edge probability for the edge. If can't find it, return a 581 /// default probability 1/N where N is the number of successors. Here an edge is 582 /// specified using PredBlock and an 583 /// index to the successors. 584 BranchProbability 585 BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src, 586 unsigned IndexInSuccessors) const { 587 auto I = Probs.find(std::make_pair(Src, IndexInSuccessors)); 588 589 if (I != Probs.end()) 590 return I->second; 591 592 return {1, 593 static_cast<uint32_t>(std::distance(succ_begin(Src), succ_end(Src)))}; 594 } 595 596 BranchProbability 597 BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src, 598 succ_const_iterator Dst) const { 599 return getEdgeProbability(Src, Dst.getSuccessorIndex()); 600 } 601 602 /// Get the raw edge probability calculated for the block pair. This returns the 603 /// sum of all raw edge probabilities from Src to Dst. 604 BranchProbability 605 BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src, 606 const BasicBlock *Dst) const { 607 auto Prob = BranchProbability::getZero(); 608 bool FoundProb = false; 609 for (succ_const_iterator I = succ_begin(Src), E = succ_end(Src); I != E; ++I) 610 if (*I == Dst) { 611 auto MapI = Probs.find(std::make_pair(Src, I.getSuccessorIndex())); 612 if (MapI != Probs.end()) { 613 FoundProb = true; 614 Prob += MapI->second; 615 } 616 } 617 uint32_t succ_num = std::distance(succ_begin(Src), succ_end(Src)); 618 return FoundProb ? Prob : BranchProbability(1, succ_num); 619 } 620 621 /// Set the edge probability for a given edge specified by PredBlock and an 622 /// index to the successors. 623 void BranchProbabilityInfo::setEdgeProbability(const BasicBlock *Src, 624 unsigned IndexInSuccessors, 625 BranchProbability Prob) { 626 Probs[std::make_pair(Src, IndexInSuccessors)] = Prob; 627 DEBUG(dbgs() << "set edge " << Src->getName() << " -> " << IndexInSuccessors 628 << " successor probability to " << Prob << "\n"); 629 } 630 631 raw_ostream & 632 BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS, 633 const BasicBlock *Src, 634 const BasicBlock *Dst) const { 635 636 const BranchProbability Prob = getEdgeProbability(Src, Dst); 637 OS << "edge " << Src->getName() << " -> " << Dst->getName() 638 << " probability is " << Prob 639 << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n"); 640 641 return OS; 642 } 643 644 void BranchProbabilityInfo::calculate(const Function &F, const LoopInfo &LI) { 645 DEBUG(dbgs() << "---- Branch Probability Info : " << F.getName() 646 << " ----\n\n"); 647 LastF = &F; // Store the last function we ran on for printing. 648 assert(PostDominatedByUnreachable.empty()); 649 assert(PostDominatedByColdCall.empty()); 650 651 // Walk the basic blocks in post-order so that we can build up state about 652 // the successors of a block iteratively. 653 for (auto BB : post_order(&F.getEntryBlock())) { 654 DEBUG(dbgs() << "Computing probabilities for " << BB->getName() << "\n"); 655 if (calcUnreachableHeuristics(BB)) 656 continue; 657 if (calcMetadataWeights(BB)) 658 continue; 659 if (calcColdCallHeuristics(BB)) 660 continue; 661 if (calcLoopBranchHeuristics(BB, LI)) 662 continue; 663 if (calcPointerHeuristics(BB)) 664 continue; 665 if (calcZeroHeuristics(BB)) 666 continue; 667 if (calcFloatingPointHeuristics(BB)) 668 continue; 669 calcInvokeHeuristics(BB); 670 } 671 672 PostDominatedByUnreachable.clear(); 673 PostDominatedByColdCall.clear(); 674 } 675 676 void BranchProbabilityInfoWrapperPass::getAnalysisUsage( 677 AnalysisUsage &AU) const { 678 AU.addRequired<LoopInfoWrapperPass>(); 679 AU.setPreservesAll(); 680 } 681 682 bool BranchProbabilityInfoWrapperPass::runOnFunction(Function &F) { 683 const LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 684 BPI.calculate(F, LI); 685 return false; 686 } 687 688 void BranchProbabilityInfoWrapperPass::releaseMemory() { BPI.releaseMemory(); } 689 690 void BranchProbabilityInfoWrapperPass::print(raw_ostream &OS, 691 const Module *) const { 692 BPI.print(OS); 693 } 694 695 char BranchProbabilityAnalysis::PassID; 696 BranchProbabilityInfo 697 BranchProbabilityAnalysis::run(Function &F, AnalysisManager<Function> &AM) { 698 BranchProbabilityInfo BPI; 699 BPI.calculate(F, AM.getResult<LoopAnalysis>(F)); 700 return BPI; 701 } 702 703 PreservedAnalyses 704 BranchProbabilityPrinterPass::run(Function &F, AnalysisManager<Function> &AM) { 705 OS << "Printing analysis results of BPI for function " 706 << "'" << F.getName() << "':" 707 << "\n"; 708 AM.getResult<BranchProbabilityAnalysis>(F).print(OS); 709 return PreservedAnalyses::all(); 710 } 711