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 25 using namespace llvm; 26 27 INITIALIZE_PASS_BEGIN(BranchProbabilityInfo, "branch-prob", 28 "Branch Probability Analysis", false, true) 29 INITIALIZE_PASS_DEPENDENCY(LoopInfo) 30 INITIALIZE_PASS_END(BranchProbabilityInfo, "branch-prob", 31 "Branch Probability Analysis", false, true) 32 33 char 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 55 static const uint32_t LBH_TAKEN_WEIGHT = 124; 56 static 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. 62 static 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. 70 static 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'. 78 static 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. 84 static const uint32_t CC_NONTAKEN_WEIGHT = 64; 85 86 static const uint32_t PH_TAKEN_WEIGHT = 20; 87 static const uint32_t PH_NONTAKEN_WEIGHT = 12; 88 89 static const uint32_t ZH_TAKEN_WEIGHT = 20; 90 static const uint32_t ZH_NONTAKEN_WEIGHT = 12; 91 92 static const uint32_t FPH_TAKEN_WEIGHT = 20; 93 static 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. 100 static 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. 106 static const uint32_t IH_NONTAKEN_WEIGHT = 1; 107 108 // Standard weight value. Used when none of the heuristics set weight for 109 // the edge. 110 static const uint32_t NORMAL_WEIGHT = 16; 111 112 // Minimum weight of an edge. Please note, that weight is NEVER 0. 113 static const uint32_t MIN_WEIGHT = 1; 114 115 static 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. 124 bool 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. 174 bool 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. 218 bool 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. 273 bool 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. 306 bool 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 360 bool 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 420 bool 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 456 bool 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 466 void BranchProbabilityInfo::getAnalysisUsage(AnalysisUsage &AU) const { 467 AU.addRequired<LoopInfo>(); 468 AU.setPreservesAll(); 469 } 470 471 bool 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 505 void 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 519 uint32_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 533 bool BranchProbabilityInfo:: 534 isEdgeHot(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 540 BasicBlock *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. 569 uint32_t BranchProbabilityInfo:: 570 getEdgeWeight(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. 582 uint32_t BranchProbabilityInfo:: 583 getEdgeWeight(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. 597 void BranchProbabilityInfo:: 598 setEdgeWeight(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. 607 BranchProbability BranchProbabilityInfo:: 608 getEdgeProbability(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. 617 BranchProbability BranchProbabilityInfo:: 618 getEdgeProbability(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 626 raw_ostream & 627 BranchProbabilityInfo::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