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