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/Constants.h" 15#include "llvm/Function.h" 16#include "llvm/Instructions.h" 17#include "llvm/LLVMContext.h" 18#include "llvm/Metadata.h" 19#include "llvm/Analysis/BranchProbabilityInfo.h" 20#include "llvm/Analysis/LoopInfo.h" 21#include "llvm/ADT/PostOrderIterator.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 72static const uint32_t PH_TAKEN_WEIGHT = 20; 73static const uint32_t PH_NONTAKEN_WEIGHT = 12; 74 75static const uint32_t ZH_TAKEN_WEIGHT = 20; 76static const uint32_t ZH_NONTAKEN_WEIGHT = 12; 77 78static const uint32_t FPH_TAKEN_WEIGHT = 20; 79static const uint32_t FPH_NONTAKEN_WEIGHT = 12; 80 81/// \brief Invoke-terminating normal branch taken weight 82/// 83/// This is the weight for branching to the normal destination of an invoke 84/// instruction. We expect this to happen most of the time. Set the weight to an 85/// absurdly high value so that nested loops subsume it. 86static const uint32_t IH_TAKEN_WEIGHT = 1024 * 1024 - 1; 87 88/// \brief Invoke-terminating normal branch not-taken weight. 89/// 90/// This is the weight for branching to the unwind destination of an invoke 91/// instruction. This is essentially never taken. 92static const uint32_t IH_NONTAKEN_WEIGHT = 1; 93 94// Standard weight value. Used when none of the heuristics set weight for 95// the edge. 96static const uint32_t NORMAL_WEIGHT = 16; 97 98// Minimum weight of an edge. Please note, that weight is NEVER 0. 99static const uint32_t MIN_WEIGHT = 1; 100 101static uint32_t getMaxWeightFor(BasicBlock *BB) { 102 return UINT32_MAX / BB->getTerminator()->getNumSuccessors(); 103} 104 105 106/// \brief Calculate edge weights for successors lead to unreachable. 107/// 108/// Predict that a successor which leads necessarily to an 109/// unreachable-terminated block as extremely unlikely. 110bool BranchProbabilityInfo::calcUnreachableHeuristics(BasicBlock *BB) { 111 TerminatorInst *TI = BB->getTerminator(); 112 if (TI->getNumSuccessors() == 0) { 113 if (isa<UnreachableInst>(TI)) 114 PostDominatedByUnreachable.insert(BB); 115 return false; 116 } 117 118 SmallVector<unsigned, 4> UnreachableEdges; 119 SmallVector<unsigned, 4> ReachableEdges; 120 121 for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) { 122 if (PostDominatedByUnreachable.count(*I)) 123 UnreachableEdges.push_back(I.getSuccessorIndex()); 124 else 125 ReachableEdges.push_back(I.getSuccessorIndex()); 126 } 127 128 // If all successors are in the set of blocks post-dominated by unreachable, 129 // this block is too. 130 if (UnreachableEdges.size() == TI->getNumSuccessors()) 131 PostDominatedByUnreachable.insert(BB); 132 133 // Skip probabilities if this block has a single successor or if all were 134 // reachable. 135 if (TI->getNumSuccessors() == 1 || UnreachableEdges.empty()) 136 return false; 137 138 uint32_t UnreachableWeight = 139 std::max(UR_TAKEN_WEIGHT / (unsigned)UnreachableEdges.size(), MIN_WEIGHT); 140 for (SmallVector<unsigned, 4>::iterator I = UnreachableEdges.begin(), 141 E = UnreachableEdges.end(); 142 I != E; ++I) 143 setEdgeWeight(BB, *I, UnreachableWeight); 144 145 if (ReachableEdges.empty()) 146 return true; 147 uint32_t ReachableWeight = 148 std::max(UR_NONTAKEN_WEIGHT / (unsigned)ReachableEdges.size(), 149 NORMAL_WEIGHT); 150 for (SmallVector<unsigned, 4>::iterator I = ReachableEdges.begin(), 151 E = ReachableEdges.end(); 152 I != E; ++I) 153 setEdgeWeight(BB, *I, ReachableWeight); 154 155 return true; 156} 157 158// Propagate existing explicit probabilities from either profile data or 159// 'expect' intrinsic processing. 160bool BranchProbabilityInfo::calcMetadataWeights(BasicBlock *BB) { 161 TerminatorInst *TI = BB->getTerminator(); 162 if (TI->getNumSuccessors() == 1) 163 return false; 164 if (!isa<BranchInst>(TI) && !isa<SwitchInst>(TI)) 165 return false; 166 167 MDNode *WeightsNode = TI->getMetadata(LLVMContext::MD_prof); 168 if (!WeightsNode) 169 return false; 170 171 // Ensure there are weights for all of the successors. Note that the first 172 // operand to the metadata node is a name, not a weight. 173 if (WeightsNode->getNumOperands() != TI->getNumSuccessors() + 1) 174 return false; 175 176 // Build up the final weights that will be used in a temporary buffer, but 177 // don't add them until all weihts are present. Each weight value is clamped 178 // to [1, getMaxWeightFor(BB)]. 179 uint32_t WeightLimit = getMaxWeightFor(BB); 180 SmallVector<uint32_t, 2> Weights; 181 Weights.reserve(TI->getNumSuccessors()); 182 for (unsigned i = 1, e = WeightsNode->getNumOperands(); i != e; ++i) { 183 ConstantInt *Weight = dyn_cast<ConstantInt>(WeightsNode->getOperand(i)); 184 if (!Weight) 185 return false; 186 Weights.push_back( 187 std::max<uint32_t>(1, Weight->getLimitedValue(WeightLimit))); 188 } 189 assert(Weights.size() == TI->getNumSuccessors() && "Checked above"); 190 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 191 setEdgeWeight(BB, i, Weights[i]); 192 193 return true; 194} 195 196// Calculate Edge Weights using "Pointer Heuristics". Predict a comparsion 197// between two pointer or pointer and NULL will fail. 198bool BranchProbabilityInfo::calcPointerHeuristics(BasicBlock *BB) { 199 BranchInst * BI = dyn_cast<BranchInst>(BB->getTerminator()); 200 if (!BI || !BI->isConditional()) 201 return false; 202 203 Value *Cond = BI->getCondition(); 204 ICmpInst *CI = dyn_cast<ICmpInst>(Cond); 205 if (!CI || !CI->isEquality()) 206 return false; 207 208 Value *LHS = CI->getOperand(0); 209 210 if (!LHS->getType()->isPointerTy()) 211 return false; 212 213 assert(CI->getOperand(1)->getType()->isPointerTy()); 214 215 // p != 0 -> isProb = true 216 // p == 0 -> isProb = false 217 // p != q -> isProb = true 218 // p == q -> isProb = false; 219 unsigned TakenIdx = 0, NonTakenIdx = 1; 220 bool isProb = CI->getPredicate() == ICmpInst::ICMP_NE; 221 if (!isProb) 222 std::swap(TakenIdx, NonTakenIdx); 223 224 setEdgeWeight(BB, TakenIdx, PH_TAKEN_WEIGHT); 225 setEdgeWeight(BB, NonTakenIdx, PH_NONTAKEN_WEIGHT); 226 return true; 227} 228 229// Calculate Edge Weights using "Loop Branch Heuristics". Predict backedges 230// as taken, exiting edges as not-taken. 231bool BranchProbabilityInfo::calcLoopBranchHeuristics(BasicBlock *BB) { 232 Loop *L = LI->getLoopFor(BB); 233 if (!L) 234 return false; 235 236 SmallVector<unsigned, 8> BackEdges; 237 SmallVector<unsigned, 8> ExitingEdges; 238 SmallVector<unsigned, 8> InEdges; // Edges from header to the loop. 239 240 for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) { 241 if (!L->contains(*I)) 242 ExitingEdges.push_back(I.getSuccessorIndex()); 243 else if (L->getHeader() == *I) 244 BackEdges.push_back(I.getSuccessorIndex()); 245 else 246 InEdges.push_back(I.getSuccessorIndex()); 247 } 248 249 if (uint32_t numBackEdges = BackEdges.size()) { 250 uint32_t backWeight = LBH_TAKEN_WEIGHT / numBackEdges; 251 if (backWeight < NORMAL_WEIGHT) 252 backWeight = NORMAL_WEIGHT; 253 254 for (SmallVector<unsigned, 8>::iterator EI = BackEdges.begin(), 255 EE = BackEdges.end(); EI != EE; ++EI) { 256 setEdgeWeight(BB, *EI, backWeight); 257 } 258 } 259 260 if (uint32_t numInEdges = InEdges.size()) { 261 uint32_t inWeight = LBH_TAKEN_WEIGHT / numInEdges; 262 if (inWeight < NORMAL_WEIGHT) 263 inWeight = NORMAL_WEIGHT; 264 265 for (SmallVector<unsigned, 8>::iterator EI = InEdges.begin(), 266 EE = InEdges.end(); EI != EE; ++EI) { 267 setEdgeWeight(BB, *EI, inWeight); 268 } 269 } 270 271 if (uint32_t numExitingEdges = ExitingEdges.size()) { 272 uint32_t exitWeight = LBH_NONTAKEN_WEIGHT / numExitingEdges; 273 if (exitWeight < MIN_WEIGHT) 274 exitWeight = MIN_WEIGHT; 275 276 for (SmallVector<unsigned, 8>::iterator EI = ExitingEdges.begin(), 277 EE = ExitingEdges.end(); EI != EE; ++EI) { 278 setEdgeWeight(BB, *EI, exitWeight); 279 } 280 } 281 282 return true; 283} 284 285bool BranchProbabilityInfo::calcZeroHeuristics(BasicBlock *BB) { 286 BranchInst * BI = dyn_cast<BranchInst>(BB->getTerminator()); 287 if (!BI || !BI->isConditional()) 288 return false; 289 290 Value *Cond = BI->getCondition(); 291 ICmpInst *CI = dyn_cast<ICmpInst>(Cond); 292 if (!CI) 293 return false; 294 295 Value *RHS = CI->getOperand(1); 296 ConstantInt *CV = dyn_cast<ConstantInt>(RHS); 297 if (!CV) 298 return false; 299 300 bool isProb; 301 if (CV->isZero()) { 302 switch (CI->getPredicate()) { 303 case CmpInst::ICMP_EQ: 304 // X == 0 -> Unlikely 305 isProb = false; 306 break; 307 case CmpInst::ICMP_NE: 308 // X != 0 -> Likely 309 isProb = true; 310 break; 311 case CmpInst::ICMP_SLT: 312 // X < 0 -> Unlikely 313 isProb = false; 314 break; 315 case CmpInst::ICMP_SGT: 316 // X > 0 -> Likely 317 isProb = true; 318 break; 319 default: 320 return false; 321 } 322 } else if (CV->isOne() && CI->getPredicate() == CmpInst::ICMP_SLT) { 323 // InstCombine canonicalizes X <= 0 into X < 1. 324 // X <= 0 -> Unlikely 325 isProb = false; 326 } else if (CV->isAllOnesValue() && CI->getPredicate() == CmpInst::ICMP_SGT) { 327 // InstCombine canonicalizes X >= 0 into X > -1. 328 // X >= 0 -> Likely 329 isProb = true; 330 } else { 331 return false; 332 } 333 334 unsigned TakenIdx = 0, NonTakenIdx = 1; 335 336 if (!isProb) 337 std::swap(TakenIdx, NonTakenIdx); 338 339 setEdgeWeight(BB, TakenIdx, ZH_TAKEN_WEIGHT); 340 setEdgeWeight(BB, NonTakenIdx, ZH_NONTAKEN_WEIGHT); 341 342 return true; 343} 344 345bool BranchProbabilityInfo::calcFloatingPointHeuristics(BasicBlock *BB) { 346 BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()); 347 if (!BI || !BI->isConditional()) 348 return false; 349 350 Value *Cond = BI->getCondition(); 351 FCmpInst *FCmp = dyn_cast<FCmpInst>(Cond); 352 if (!FCmp) 353 return false; 354 355 bool isProb; 356 if (FCmp->isEquality()) { 357 // f1 == f2 -> Unlikely 358 // f1 != f2 -> Likely 359 isProb = !FCmp->isTrueWhenEqual(); 360 } else if (FCmp->getPredicate() == FCmpInst::FCMP_ORD) { 361 // !isnan -> Likely 362 isProb = true; 363 } else if (FCmp->getPredicate() == FCmpInst::FCMP_UNO) { 364 // isnan -> Unlikely 365 isProb = false; 366 } else { 367 return false; 368 } 369 370 unsigned TakenIdx = 0, NonTakenIdx = 1; 371 372 if (!isProb) 373 std::swap(TakenIdx, NonTakenIdx); 374 375 setEdgeWeight(BB, TakenIdx, FPH_TAKEN_WEIGHT); 376 setEdgeWeight(BB, NonTakenIdx, FPH_NONTAKEN_WEIGHT); 377 378 return true; 379} 380 381bool BranchProbabilityInfo::calcInvokeHeuristics(BasicBlock *BB) { 382 InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator()); 383 if (!II) 384 return false; 385 386 setEdgeWeight(BB, 0/*Index for Normal*/, IH_TAKEN_WEIGHT); 387 setEdgeWeight(BB, 1/*Index for Unwind*/, IH_NONTAKEN_WEIGHT); 388 return true; 389} 390 391void BranchProbabilityInfo::getAnalysisUsage(AnalysisUsage &AU) const { 392 AU.addRequired<LoopInfo>(); 393 AU.setPreservesAll(); 394} 395 396bool BranchProbabilityInfo::runOnFunction(Function &F) { 397 LastF = &F; // Store the last function we ran on for printing. 398 LI = &getAnalysis<LoopInfo>(); 399 assert(PostDominatedByUnreachable.empty()); 400 401 // Walk the basic blocks in post-order so that we can build up state about 402 // the successors of a block iteratively. 403 for (po_iterator<BasicBlock *> I = po_begin(&F.getEntryBlock()), 404 E = po_end(&F.getEntryBlock()); 405 I != E; ++I) { 406 DEBUG(dbgs() << "Computing probabilities for " << I->getName() << "\n"); 407 if (calcUnreachableHeuristics(*I)) 408 continue; 409 if (calcMetadataWeights(*I)) 410 continue; 411 if (calcLoopBranchHeuristics(*I)) 412 continue; 413 if (calcPointerHeuristics(*I)) 414 continue; 415 if (calcZeroHeuristics(*I)) 416 continue; 417 if (calcFloatingPointHeuristics(*I)) 418 continue; 419 calcInvokeHeuristics(*I); 420 } 421 422 PostDominatedByUnreachable.clear(); 423 return false; 424} 425 426void BranchProbabilityInfo::print(raw_ostream &OS, const Module *) const { 427 OS << "---- Branch Probabilities ----\n"; 428 // We print the probabilities from the last function the analysis ran over, 429 // or the function it is currently running over. 430 assert(LastF && "Cannot print prior to running over a function"); 431 for (Function::const_iterator BI = LastF->begin(), BE = LastF->end(); 432 BI != BE; ++BI) { 433 for (succ_const_iterator SI = succ_begin(BI), SE = succ_end(BI); 434 SI != SE; ++SI) { 435 printEdgeProbability(OS << " ", BI, *SI); 436 } 437 } 438} 439 440uint32_t BranchProbabilityInfo::getSumForBlock(const BasicBlock *BB) const { 441 uint32_t Sum = 0; 442 443 for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) { 444 uint32_t Weight = getEdgeWeight(BB, I.getSuccessorIndex()); 445 uint32_t PrevSum = Sum; 446 447 Sum += Weight; 448 assert(Sum > PrevSum); (void) PrevSum; 449 } 450 451 return Sum; 452} 453 454bool BranchProbabilityInfo:: 455isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const { 456 // Hot probability is at least 4/5 = 80% 457 // FIXME: Compare against a static "hot" BranchProbability. 458 return getEdgeProbability(Src, Dst) > BranchProbability(4, 5); 459} 460 461BasicBlock *BranchProbabilityInfo::getHotSucc(BasicBlock *BB) const { 462 uint32_t Sum = 0; 463 uint32_t MaxWeight = 0; 464 BasicBlock *MaxSucc = 0; 465 466 for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) { 467 BasicBlock *Succ = *I; 468 uint32_t Weight = getEdgeWeight(BB, Succ); 469 uint32_t PrevSum = Sum; 470 471 Sum += Weight; 472 assert(Sum > PrevSum); (void) PrevSum; 473 474 if (Weight > MaxWeight) { 475 MaxWeight = Weight; 476 MaxSucc = Succ; 477 } 478 } 479 480 // Hot probability is at least 4/5 = 80% 481 if (BranchProbability(MaxWeight, Sum) > BranchProbability(4, 5)) 482 return MaxSucc; 483 484 return 0; 485} 486 487/// Get the raw edge weight for the edge. If can't find it, return 488/// DEFAULT_WEIGHT value. Here an edge is specified using PredBlock and an index 489/// to the successors. 490uint32_t BranchProbabilityInfo:: 491getEdgeWeight(const BasicBlock *Src, unsigned IndexInSuccessors) const { 492 DenseMap<Edge, uint32_t>::const_iterator I = 493 Weights.find(std::make_pair(Src, IndexInSuccessors)); 494 495 if (I != Weights.end()) 496 return I->second; 497 498 return DEFAULT_WEIGHT; 499} 500 501/// Get the raw edge weight calculated for the block pair. This returns the sum 502/// of all raw edge weights from Src to Dst. 503uint32_t BranchProbabilityInfo:: 504getEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst) const { 505 uint32_t Weight = 0; 506 DenseMap<Edge, uint32_t>::const_iterator MapI; 507 for (succ_const_iterator I = succ_begin(Src), E = succ_end(Src); I != E; ++I) 508 if (*I == Dst) { 509 MapI = Weights.find(std::make_pair(Src, I.getSuccessorIndex())); 510 if (MapI != Weights.end()) 511 Weight += MapI->second; 512 } 513 return (Weight == 0) ? DEFAULT_WEIGHT : Weight; 514} 515 516/// Set the edge weight for a given edge specified by PredBlock and an index 517/// to the successors. 518void BranchProbabilityInfo:: 519setEdgeWeight(const BasicBlock *Src, unsigned IndexInSuccessors, 520 uint32_t Weight) { 521 Weights[std::make_pair(Src, IndexInSuccessors)] = Weight; 522 DEBUG(dbgs() << "set edge " << Src->getName() << " -> " 523 << IndexInSuccessors << " successor weight to " 524 << Weight << "\n"); 525} 526 527/// Get an edge's probability, relative to other out-edges from Src. 528BranchProbability BranchProbabilityInfo:: 529getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const { 530 uint32_t N = getEdgeWeight(Src, IndexInSuccessors); 531 uint32_t D = getSumForBlock(Src); 532 533 return BranchProbability(N, D); 534} 535 536/// Get the probability of going from Src to Dst. It returns the sum of all 537/// probabilities for edges from Src to Dst. 538BranchProbability BranchProbabilityInfo:: 539getEdgeProbability(const BasicBlock *Src, const BasicBlock *Dst) const { 540 541 uint32_t N = getEdgeWeight(Src, Dst); 542 uint32_t D = getSumForBlock(Src); 543 544 return BranchProbability(N, D); 545} 546 547raw_ostream & 548BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS, 549 const BasicBlock *Src, 550 const BasicBlock *Dst) const { 551 552 const BranchProbability Prob = getEdgeProbability(Src, Dst); 553 OS << "edge " << Src->getName() << " -> " << Dst->getName() 554 << " probability is " << Prob 555 << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n"); 556 557 return OS; 558} 559