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