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