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