BranchProbabilityInfo.cpp revision 263508
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()) { 402 switch (CI->getPredicate()) { 403 case CmpInst::ICMP_EQ: 404 // X == -1 -> Unlikely 405 isProb = false; 406 break; 407 case CmpInst::ICMP_NE: 408 // X != -1 -> Likely 409 isProb = true; 410 break; 411 case CmpInst::ICMP_SGT: 412 // InstCombine canonicalizes X >= 0 into X > -1. 413 // X >= 0 -> Likely 414 isProb = true; 415 break; 416 default: 417 return false; 418 } 419 } else { 420 return false; 421 } 422 423 unsigned TakenIdx = 0, NonTakenIdx = 1; 424 425 if (!isProb) 426 std::swap(TakenIdx, NonTakenIdx); 427 428 setEdgeWeight(BB, TakenIdx, ZH_TAKEN_WEIGHT); 429 setEdgeWeight(BB, NonTakenIdx, ZH_NONTAKEN_WEIGHT); 430 431 return true; 432} 433 434bool BranchProbabilityInfo::calcFloatingPointHeuristics(BasicBlock *BB) { 435 BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()); 436 if (!BI || !BI->isConditional()) 437 return false; 438 439 Value *Cond = BI->getCondition(); 440 FCmpInst *FCmp = dyn_cast<FCmpInst>(Cond); 441 if (!FCmp) 442 return false; 443 444 bool isProb; 445 if (FCmp->isEquality()) { 446 // f1 == f2 -> Unlikely 447 // f1 != f2 -> Likely 448 isProb = !FCmp->isTrueWhenEqual(); 449 } else if (FCmp->getPredicate() == FCmpInst::FCMP_ORD) { 450 // !isnan -> Likely 451 isProb = true; 452 } else if (FCmp->getPredicate() == FCmpInst::FCMP_UNO) { 453 // isnan -> Unlikely 454 isProb = false; 455 } else { 456 return false; 457 } 458 459 unsigned TakenIdx = 0, NonTakenIdx = 1; 460 461 if (!isProb) 462 std::swap(TakenIdx, NonTakenIdx); 463 464 setEdgeWeight(BB, TakenIdx, FPH_TAKEN_WEIGHT); 465 setEdgeWeight(BB, NonTakenIdx, FPH_NONTAKEN_WEIGHT); 466 467 return true; 468} 469 470bool BranchProbabilityInfo::calcInvokeHeuristics(BasicBlock *BB) { 471 InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator()); 472 if (!II) 473 return false; 474 475 setEdgeWeight(BB, 0/*Index for Normal*/, IH_TAKEN_WEIGHT); 476 setEdgeWeight(BB, 1/*Index for Unwind*/, IH_NONTAKEN_WEIGHT); 477 return true; 478} 479 480void BranchProbabilityInfo::getAnalysisUsage(AnalysisUsage &AU) const { 481 AU.addRequired<LoopInfo>(); 482 AU.setPreservesAll(); 483} 484 485bool BranchProbabilityInfo::runOnFunction(Function &F) { 486 LastF = &F; // Store the last function we ran on for printing. 487 LI = &getAnalysis<LoopInfo>(); 488 assert(PostDominatedByUnreachable.empty()); 489 assert(PostDominatedByColdCall.empty()); 490 491 // Walk the basic blocks in post-order so that we can build up state about 492 // the successors of a block iteratively. 493 for (po_iterator<BasicBlock *> I = po_begin(&F.getEntryBlock()), 494 E = po_end(&F.getEntryBlock()); 495 I != E; ++I) { 496 DEBUG(dbgs() << "Computing probabilities for " << I->getName() << "\n"); 497 if (calcUnreachableHeuristics(*I)) 498 continue; 499 if (calcMetadataWeights(*I)) 500 continue; 501 if (calcColdCallHeuristics(*I)) 502 continue; 503 if (calcLoopBranchHeuristics(*I)) 504 continue; 505 if (calcPointerHeuristics(*I)) 506 continue; 507 if (calcZeroHeuristics(*I)) 508 continue; 509 if (calcFloatingPointHeuristics(*I)) 510 continue; 511 calcInvokeHeuristics(*I); 512 } 513 514 PostDominatedByUnreachable.clear(); 515 PostDominatedByColdCall.clear(); 516 return false; 517} 518 519void BranchProbabilityInfo::print(raw_ostream &OS, const Module *) const { 520 OS << "---- Branch Probabilities ----\n"; 521 // We print the probabilities from the last function the analysis ran over, 522 // or the function it is currently running over. 523 assert(LastF && "Cannot print prior to running over a function"); 524 for (Function::const_iterator BI = LastF->begin(), BE = LastF->end(); 525 BI != BE; ++BI) { 526 for (succ_const_iterator SI = succ_begin(BI), SE = succ_end(BI); 527 SI != SE; ++SI) { 528 printEdgeProbability(OS << " ", BI, *SI); 529 } 530 } 531} 532 533uint32_t BranchProbabilityInfo::getSumForBlock(const BasicBlock *BB) const { 534 uint32_t Sum = 0; 535 536 for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) { 537 uint32_t Weight = getEdgeWeight(BB, I.getSuccessorIndex()); 538 uint32_t PrevSum = Sum; 539 540 Sum += Weight; 541 assert(Sum > PrevSum); (void) PrevSum; 542 } 543 544 return Sum; 545} 546 547bool BranchProbabilityInfo:: 548isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const { 549 // Hot probability is at least 4/5 = 80% 550 // FIXME: Compare against a static "hot" BranchProbability. 551 return getEdgeProbability(Src, Dst) > BranchProbability(4, 5); 552} 553 554BasicBlock *BranchProbabilityInfo::getHotSucc(BasicBlock *BB) const { 555 uint32_t Sum = 0; 556 uint32_t MaxWeight = 0; 557 BasicBlock *MaxSucc = 0; 558 559 for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) { 560 BasicBlock *Succ = *I; 561 uint32_t Weight = getEdgeWeight(BB, Succ); 562 uint32_t PrevSum = Sum; 563 564 Sum += Weight; 565 assert(Sum > PrevSum); (void) PrevSum; 566 567 if (Weight > MaxWeight) { 568 MaxWeight = Weight; 569 MaxSucc = Succ; 570 } 571 } 572 573 // Hot probability is at least 4/5 = 80% 574 if (BranchProbability(MaxWeight, Sum) > BranchProbability(4, 5)) 575 return MaxSucc; 576 577 return 0; 578} 579 580/// Get the raw edge weight for the edge. If can't find it, return 581/// DEFAULT_WEIGHT value. Here an edge is specified using PredBlock and an index 582/// to the successors. 583uint32_t BranchProbabilityInfo:: 584getEdgeWeight(const BasicBlock *Src, unsigned IndexInSuccessors) const { 585 DenseMap<Edge, uint32_t>::const_iterator I = 586 Weights.find(std::make_pair(Src, IndexInSuccessors)); 587 588 if (I != Weights.end()) 589 return I->second; 590 591 return DEFAULT_WEIGHT; 592} 593 594/// Get the raw edge weight calculated for the block pair. This returns the sum 595/// of all raw edge weights from Src to Dst. 596uint32_t BranchProbabilityInfo:: 597getEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst) const { 598 uint32_t Weight = 0; 599 DenseMap<Edge, uint32_t>::const_iterator MapI; 600 for (succ_const_iterator I = succ_begin(Src), E = succ_end(Src); I != E; ++I) 601 if (*I == Dst) { 602 MapI = Weights.find(std::make_pair(Src, I.getSuccessorIndex())); 603 if (MapI != Weights.end()) 604 Weight += MapI->second; 605 } 606 return (Weight == 0) ? DEFAULT_WEIGHT : Weight; 607} 608 609/// Set the edge weight for a given edge specified by PredBlock and an index 610/// to the successors. 611void BranchProbabilityInfo:: 612setEdgeWeight(const BasicBlock *Src, unsigned IndexInSuccessors, 613 uint32_t Weight) { 614 Weights[std::make_pair(Src, IndexInSuccessors)] = Weight; 615 DEBUG(dbgs() << "set edge " << Src->getName() << " -> " 616 << IndexInSuccessors << " successor weight to " 617 << Weight << "\n"); 618} 619 620/// Get an edge's probability, relative to other out-edges from Src. 621BranchProbability BranchProbabilityInfo:: 622getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const { 623 uint32_t N = getEdgeWeight(Src, IndexInSuccessors); 624 uint32_t D = getSumForBlock(Src); 625 626 return BranchProbability(N, D); 627} 628 629/// Get the probability of going from Src to Dst. It returns the sum of all 630/// probabilities for edges from Src to Dst. 631BranchProbability BranchProbabilityInfo:: 632getEdgeProbability(const BasicBlock *Src, const BasicBlock *Dst) const { 633 634 uint32_t N = getEdgeWeight(Src, Dst); 635 uint32_t D = getSumForBlock(Src); 636 637 return BranchProbability(N, D); 638} 639 640raw_ostream & 641BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS, 642 const BasicBlock *Src, 643 const BasicBlock *Dst) const { 644 645 const BranchProbability Prob = getEdgeProbability(Src, Dst); 646 OS << "edge " << Src->getName() << " -> " << Dst->getName() 647 << " probability is " << Prob 648 << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n"); 649 650 return OS; 651} 652