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/ADT/SCCIterator.h" 17 #include "llvm/ADT/STLExtras.h" 18 #include "llvm/ADT/SmallVector.h" 19 #include "llvm/Analysis/LoopInfo.h" 20 #include "llvm/Analysis/TargetLibraryInfo.h" 21 #include "llvm/IR/Attributes.h" 22 #include "llvm/IR/BasicBlock.h" 23 #include "llvm/IR/CFG.h" 24 #include "llvm/IR/Constants.h" 25 #include "llvm/IR/Dominators.h" 26 #include "llvm/IR/Function.h" 27 #include "llvm/IR/InstrTypes.h" 28 #include "llvm/IR/Instruction.h" 29 #include "llvm/IR/Instructions.h" 30 #include "llvm/IR/LLVMContext.h" 31 #include "llvm/IR/Metadata.h" 32 #include "llvm/IR/PassManager.h" 33 #include "llvm/IR/Type.h" 34 #include "llvm/IR/Value.h" 35 #include "llvm/Pass.h" 36 #include "llvm/Support/BranchProbability.h" 37 #include "llvm/Support/Casting.h" 38 #include "llvm/Support/Debug.h" 39 #include "llvm/Support/raw_ostream.h" 40 #include <cassert> 41 #include <cstdint> 42 #include <iterator> 43 #include <utility> 44 45 using namespace llvm; 46 47 #define DEBUG_TYPE "branch-prob" 48 49 static cl::opt<bool> PrintBranchProb( 50 "print-bpi", cl::init(false), cl::Hidden, 51 cl::desc("Print the branch probability info.")); 52 53 cl::opt<std::string> PrintBranchProbFuncName( 54 "print-bpi-func-name", cl::Hidden, 55 cl::desc("The option to specify the name of the function " 56 "whose branch probability info is printed.")); 57 58 INITIALIZE_PASS_BEGIN(BranchProbabilityInfoWrapperPass, "branch-prob", 59 "Branch Probability Analysis", false, true) 60 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) 61 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) 62 INITIALIZE_PASS_END(BranchProbabilityInfoWrapperPass, "branch-prob", 63 "Branch Probability Analysis", false, true) 64 65 char BranchProbabilityInfoWrapperPass::ID = 0; 66 67 // Weights are for internal use only. They are used by heuristics to help to 68 // estimate edges' probability. Example: 69 // 70 // Using "Loop Branch Heuristics" we predict weights of edges for the 71 // block BB2. 72 // ... 73 // | 74 // V 75 // BB1<-+ 76 // | | 77 // | | (Weight = 124) 78 // V | 79 // BB2--+ 80 // | 81 // | (Weight = 4) 82 // V 83 // BB3 84 // 85 // Probability of the edge BB2->BB1 = 124 / (124 + 4) = 0.96875 86 // Probability of the edge BB2->BB3 = 4 / (124 + 4) = 0.03125 87 static const uint32_t LBH_TAKEN_WEIGHT = 124; 88 static const uint32_t LBH_NONTAKEN_WEIGHT = 4; 89 // Unlikely edges within a loop are half as likely as other edges 90 static const uint32_t LBH_UNLIKELY_WEIGHT = 62; 91 92 /// Unreachable-terminating branch taken probability. 93 /// 94 /// This is the probability for a branch being taken to a block that terminates 95 /// (eventually) in unreachable. These are predicted as unlikely as possible. 96 /// All reachable probability will equally share the remaining part. 97 static const BranchProbability UR_TAKEN_PROB = BranchProbability::getRaw(1); 98 99 /// Weight for a branch taken going into a cold block. 100 /// 101 /// This is the weight for a branch taken toward a block marked 102 /// cold. A block is marked cold if it's postdominated by a 103 /// block containing a call to a cold function. Cold functions 104 /// are those marked with attribute 'cold'. 105 static const uint32_t CC_TAKEN_WEIGHT = 4; 106 107 /// Weight for a branch not-taken into a cold block. 108 /// 109 /// This is the weight for a branch not taken toward a block marked 110 /// cold. 111 static const uint32_t CC_NONTAKEN_WEIGHT = 64; 112 113 static const uint32_t PH_TAKEN_WEIGHT = 20; 114 static const uint32_t PH_NONTAKEN_WEIGHT = 12; 115 116 static const uint32_t ZH_TAKEN_WEIGHT = 20; 117 static const uint32_t ZH_NONTAKEN_WEIGHT = 12; 118 119 static const uint32_t FPH_TAKEN_WEIGHT = 20; 120 static const uint32_t FPH_NONTAKEN_WEIGHT = 12; 121 122 /// Invoke-terminating normal branch taken weight 123 /// 124 /// This is the weight for branching to the normal destination of an invoke 125 /// instruction. We expect this to happen most of the time. Set the weight to an 126 /// absurdly high value so that nested loops subsume it. 127 static const uint32_t IH_TAKEN_WEIGHT = 1024 * 1024 - 1; 128 129 /// Invoke-terminating normal branch not-taken weight. 130 /// 131 /// This is the weight for branching to the unwind destination of an invoke 132 /// instruction. This is essentially never taken. 133 static const uint32_t IH_NONTAKEN_WEIGHT = 1; 134 135 /// Add \p BB to PostDominatedByUnreachable set if applicable. 136 void 137 BranchProbabilityInfo::updatePostDominatedByUnreachable(const BasicBlock *BB) { 138 const TerminatorInst *TI = BB->getTerminator(); 139 if (TI->getNumSuccessors() == 0) { 140 if (isa<UnreachableInst>(TI) || 141 // If this block is terminated by a call to 142 // @llvm.experimental.deoptimize then treat it like an unreachable since 143 // the @llvm.experimental.deoptimize call is expected to practically 144 // never execute. 145 BB->getTerminatingDeoptimizeCall()) 146 PostDominatedByUnreachable.insert(BB); 147 return; 148 } 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; 156 } 157 158 for (auto *I : successors(BB)) 159 // If any of successor is not post dominated then BB is also not. 160 if (!PostDominatedByUnreachable.count(I)) 161 return; 162 163 PostDominatedByUnreachable.insert(BB); 164 } 165 166 /// Add \p BB to PostDominatedByColdCall set if applicable. 167 void 168 BranchProbabilityInfo::updatePostDominatedByColdCall(const BasicBlock *BB) { 169 assert(!PostDominatedByColdCall.count(BB)); 170 const TerminatorInst *TI = BB->getTerminator(); 171 if (TI->getNumSuccessors() == 0) 172 return; 173 174 // If all of successor are post dominated then BB is also done. 175 if (llvm::all_of(successors(BB), [&](const BasicBlock *SuccBB) { 176 return PostDominatedByColdCall.count(SuccBB); 177 })) { 178 PostDominatedByColdCall.insert(BB); 179 return; 180 } 181 182 // If the terminator is an InvokeInst, check only the normal destination 183 // block as the unwind edge of InvokeInst is also very unlikely taken. 184 if (auto *II = dyn_cast<InvokeInst>(TI)) 185 if (PostDominatedByColdCall.count(II->getNormalDest())) { 186 PostDominatedByColdCall.insert(BB); 187 return; 188 } 189 190 // Otherwise, if the block itself contains a cold function, add it to the 191 // set of blocks post-dominated by a cold call. 192 for (auto &I : *BB) 193 if (const CallInst *CI = dyn_cast<CallInst>(&I)) 194 if (CI->hasFnAttr(Attribute::Cold)) { 195 PostDominatedByColdCall.insert(BB); 196 return; 197 } 198 } 199 200 /// Calculate edge weights for successors lead to unreachable. 201 /// 202 /// Predict that a successor which leads necessarily to an 203 /// unreachable-terminated block as extremely unlikely. 204 bool BranchProbabilityInfo::calcUnreachableHeuristics(const BasicBlock *BB) { 205 const TerminatorInst *TI = BB->getTerminator(); 206 (void) TI; 207 assert(TI->getNumSuccessors() > 1 && "expected more than one successor!"); 208 assert(!isa<InvokeInst>(TI) && 209 "Invokes should have already been handled by calcInvokeHeuristics"); 210 211 SmallVector<unsigned, 4> UnreachableEdges; 212 SmallVector<unsigned, 4> ReachableEdges; 213 214 for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) 215 if (PostDominatedByUnreachable.count(*I)) 216 UnreachableEdges.push_back(I.getSuccessorIndex()); 217 else 218 ReachableEdges.push_back(I.getSuccessorIndex()); 219 220 // Skip probabilities if all were reachable. 221 if (UnreachableEdges.empty()) 222 return false; 223 224 if (ReachableEdges.empty()) { 225 BranchProbability Prob(1, UnreachableEdges.size()); 226 for (unsigned SuccIdx : UnreachableEdges) 227 setEdgeProbability(BB, SuccIdx, Prob); 228 return true; 229 } 230 231 auto UnreachableProb = UR_TAKEN_PROB; 232 auto ReachableProb = 233 (BranchProbability::getOne() - UR_TAKEN_PROB * UnreachableEdges.size()) / 234 ReachableEdges.size(); 235 236 for (unsigned SuccIdx : UnreachableEdges) 237 setEdgeProbability(BB, SuccIdx, UnreachableProb); 238 for (unsigned SuccIdx : ReachableEdges) 239 setEdgeProbability(BB, SuccIdx, ReachableProb); 240 241 return true; 242 } 243 244 // Propagate existing explicit probabilities from either profile data or 245 // 'expect' intrinsic processing. Examine metadata against unreachable 246 // heuristic. The probability of the edge coming to unreachable block is 247 // set to min of metadata and unreachable heuristic. 248 bool BranchProbabilityInfo::calcMetadataWeights(const BasicBlock *BB) { 249 const TerminatorInst *TI = BB->getTerminator(); 250 assert(TI->getNumSuccessors() > 1 && "expected more than one successor!"); 251 if (!(isa<BranchInst>(TI) || isa<SwitchInst>(TI) || isa<IndirectBrInst>(TI))) 252 return false; 253 254 MDNode *WeightsNode = TI->getMetadata(LLVMContext::MD_prof); 255 if (!WeightsNode) 256 return false; 257 258 // Check that the number of successors is manageable. 259 assert(TI->getNumSuccessors() < UINT32_MAX && "Too many successors"); 260 261 // Ensure there are weights for all of the successors. Note that the first 262 // operand to the metadata node is a name, not a weight. 263 if (WeightsNode->getNumOperands() != TI->getNumSuccessors() + 1) 264 return false; 265 266 // Build up the final weights that will be used in a temporary buffer. 267 // Compute the sum of all weights to later decide whether they need to 268 // be scaled to fit in 32 bits. 269 uint64_t WeightSum = 0; 270 SmallVector<uint32_t, 2> Weights; 271 SmallVector<unsigned, 2> UnreachableIdxs; 272 SmallVector<unsigned, 2> ReachableIdxs; 273 Weights.reserve(TI->getNumSuccessors()); 274 for (unsigned i = 1, e = WeightsNode->getNumOperands(); i != e; ++i) { 275 ConstantInt *Weight = 276 mdconst::dyn_extract<ConstantInt>(WeightsNode->getOperand(i)); 277 if (!Weight) 278 return false; 279 assert(Weight->getValue().getActiveBits() <= 32 && 280 "Too many bits for uint32_t"); 281 Weights.push_back(Weight->getZExtValue()); 282 WeightSum += Weights.back(); 283 if (PostDominatedByUnreachable.count(TI->getSuccessor(i - 1))) 284 UnreachableIdxs.push_back(i - 1); 285 else 286 ReachableIdxs.push_back(i - 1); 287 } 288 assert(Weights.size() == TI->getNumSuccessors() && "Checked above"); 289 290 // If the sum of weights does not fit in 32 bits, scale every weight down 291 // accordingly. 292 uint64_t ScalingFactor = 293 (WeightSum > UINT32_MAX) ? WeightSum / UINT32_MAX + 1 : 1; 294 295 if (ScalingFactor > 1) { 296 WeightSum = 0; 297 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) { 298 Weights[i] /= ScalingFactor; 299 WeightSum += Weights[i]; 300 } 301 } 302 assert(WeightSum <= UINT32_MAX && 303 "Expected weights to scale down to 32 bits"); 304 305 if (WeightSum == 0 || ReachableIdxs.size() == 0) { 306 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 307 Weights[i] = 1; 308 WeightSum = TI->getNumSuccessors(); 309 } 310 311 // Set the probability. 312 SmallVector<BranchProbability, 2> BP; 313 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 314 BP.push_back({ Weights[i], static_cast<uint32_t>(WeightSum) }); 315 316 // Examine the metadata against unreachable heuristic. 317 // If the unreachable heuristic is more strong then we use it for this edge. 318 if (UnreachableIdxs.size() > 0 && ReachableIdxs.size() > 0) { 319 auto ToDistribute = BranchProbability::getZero(); 320 auto UnreachableProb = UR_TAKEN_PROB; 321 for (auto i : UnreachableIdxs) 322 if (UnreachableProb < BP[i]) { 323 ToDistribute += BP[i] - UnreachableProb; 324 BP[i] = UnreachableProb; 325 } 326 327 // If we modified the probability of some edges then we must distribute 328 // the difference between reachable blocks. 329 if (ToDistribute > BranchProbability::getZero()) { 330 BranchProbability PerEdge = ToDistribute / ReachableIdxs.size(); 331 for (auto i : ReachableIdxs) 332 BP[i] += PerEdge; 333 } 334 } 335 336 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 337 setEdgeProbability(BB, i, BP[i]); 338 339 return true; 340 } 341 342 /// Calculate edge weights for edges leading to cold blocks. 343 /// 344 /// A cold block is one post-dominated by a block with a call to a 345 /// cold function. Those edges are unlikely to be taken, so we give 346 /// them relatively low weight. 347 /// 348 /// Return true if we could compute the weights for cold edges. 349 /// Return false, otherwise. 350 bool BranchProbabilityInfo::calcColdCallHeuristics(const BasicBlock *BB) { 351 const TerminatorInst *TI = BB->getTerminator(); 352 (void) TI; 353 assert(TI->getNumSuccessors() > 1 && "expected more than one successor!"); 354 assert(!isa<InvokeInst>(TI) && 355 "Invokes should have already been handled by calcInvokeHeuristics"); 356 357 // Determine which successors are post-dominated by a cold block. 358 SmallVector<unsigned, 4> ColdEdges; 359 SmallVector<unsigned, 4> NormalEdges; 360 for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) 361 if (PostDominatedByColdCall.count(*I)) 362 ColdEdges.push_back(I.getSuccessorIndex()); 363 else 364 NormalEdges.push_back(I.getSuccessorIndex()); 365 366 // Skip probabilities if no cold edges. 367 if (ColdEdges.empty()) 368 return false; 369 370 if (NormalEdges.empty()) { 371 BranchProbability Prob(1, ColdEdges.size()); 372 for (unsigned SuccIdx : ColdEdges) 373 setEdgeProbability(BB, SuccIdx, Prob); 374 return true; 375 } 376 377 auto ColdProb = BranchProbability::getBranchProbability( 378 CC_TAKEN_WEIGHT, 379 (CC_TAKEN_WEIGHT + CC_NONTAKEN_WEIGHT) * uint64_t(ColdEdges.size())); 380 auto NormalProb = BranchProbability::getBranchProbability( 381 CC_NONTAKEN_WEIGHT, 382 (CC_TAKEN_WEIGHT + CC_NONTAKEN_WEIGHT) * uint64_t(NormalEdges.size())); 383 384 for (unsigned SuccIdx : ColdEdges) 385 setEdgeProbability(BB, SuccIdx, ColdProb); 386 for (unsigned SuccIdx : NormalEdges) 387 setEdgeProbability(BB, SuccIdx, NormalProb); 388 389 return true; 390 } 391 392 // Calculate Edge Weights using "Pointer Heuristics". Predict a comparison 393 // between two pointer or pointer and NULL will fail. 394 bool BranchProbabilityInfo::calcPointerHeuristics(const BasicBlock *BB) { 395 const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()); 396 if (!BI || !BI->isConditional()) 397 return false; 398 399 Value *Cond = BI->getCondition(); 400 ICmpInst *CI = dyn_cast<ICmpInst>(Cond); 401 if (!CI || !CI->isEquality()) 402 return false; 403 404 Value *LHS = CI->getOperand(0); 405 406 if (!LHS->getType()->isPointerTy()) 407 return false; 408 409 assert(CI->getOperand(1)->getType()->isPointerTy()); 410 411 // p != 0 -> isProb = true 412 // p == 0 -> isProb = false 413 // p != q -> isProb = true 414 // p == q -> isProb = false; 415 unsigned TakenIdx = 0, NonTakenIdx = 1; 416 bool isProb = CI->getPredicate() == ICmpInst::ICMP_NE; 417 if (!isProb) 418 std::swap(TakenIdx, NonTakenIdx); 419 420 BranchProbability TakenProb(PH_TAKEN_WEIGHT, 421 PH_TAKEN_WEIGHT + PH_NONTAKEN_WEIGHT); 422 setEdgeProbability(BB, TakenIdx, TakenProb); 423 setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl()); 424 return true; 425 } 426 427 static int getSCCNum(const BasicBlock *BB, 428 const BranchProbabilityInfo::SccInfo &SccI) { 429 auto SccIt = SccI.SccNums.find(BB); 430 if (SccIt == SccI.SccNums.end()) 431 return -1; 432 return SccIt->second; 433 } 434 435 // Consider any block that is an entry point to the SCC as a header. 436 static bool isSCCHeader(const BasicBlock *BB, int SccNum, 437 BranchProbabilityInfo::SccInfo &SccI) { 438 assert(getSCCNum(BB, SccI) == SccNum); 439 440 // Lazily compute the set of headers for a given SCC and cache the results 441 // in the SccHeaderMap. 442 if (SccI.SccHeaders.size() <= static_cast<unsigned>(SccNum)) 443 SccI.SccHeaders.resize(SccNum + 1); 444 auto &HeaderMap = SccI.SccHeaders[SccNum]; 445 bool Inserted; 446 BranchProbabilityInfo::SccHeaderMap::iterator HeaderMapIt; 447 std::tie(HeaderMapIt, Inserted) = HeaderMap.insert(std::make_pair(BB, false)); 448 if (Inserted) { 449 bool IsHeader = llvm::any_of(make_range(pred_begin(BB), pred_end(BB)), 450 [&](const BasicBlock *Pred) { 451 return getSCCNum(Pred, SccI) != SccNum; 452 }); 453 HeaderMapIt->second = IsHeader; 454 return IsHeader; 455 } else 456 return HeaderMapIt->second; 457 } 458 459 // Compute the unlikely successors to the block BB in the loop L, specifically 460 // those that are unlikely because this is a loop, and add them to the 461 // UnlikelyBlocks set. 462 static void 463 computeUnlikelySuccessors(const BasicBlock *BB, Loop *L, 464 SmallPtrSetImpl<const BasicBlock*> &UnlikelyBlocks) { 465 // Sometimes in a loop we have a branch whose condition is made false by 466 // taking it. This is typically something like 467 // int n = 0; 468 // while (...) { 469 // if (++n >= MAX) { 470 // n = 0; 471 // } 472 // } 473 // In this sort of situation taking the branch means that at the very least it 474 // won't be taken again in the next iteration of the loop, so we should 475 // consider it less likely than a typical branch. 476 // 477 // We detect this by looking back through the graph of PHI nodes that sets the 478 // value that the condition depends on, and seeing if we can reach a successor 479 // block which can be determined to make the condition false. 480 // 481 // FIXME: We currently consider unlikely blocks to be half as likely as other 482 // blocks, but if we consider the example above the likelyhood is actually 483 // 1/MAX. We could therefore be more precise in how unlikely we consider 484 // blocks to be, but it would require more careful examination of the form 485 // of the comparison expression. 486 const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()); 487 if (!BI || !BI->isConditional()) 488 return; 489 490 // Check if the branch is based on an instruction compared with a constant 491 CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition()); 492 if (!CI || !isa<Instruction>(CI->getOperand(0)) || 493 !isa<Constant>(CI->getOperand(1))) 494 return; 495 496 // Either the instruction must be a PHI, or a chain of operations involving 497 // constants that ends in a PHI which we can then collapse into a single value 498 // if the PHI value is known. 499 Instruction *CmpLHS = dyn_cast<Instruction>(CI->getOperand(0)); 500 PHINode *CmpPHI = dyn_cast<PHINode>(CmpLHS); 501 Constant *CmpConst = dyn_cast<Constant>(CI->getOperand(1)); 502 // Collect the instructions until we hit a PHI 503 SmallVector<BinaryOperator *, 1> InstChain; 504 while (!CmpPHI && CmpLHS && isa<BinaryOperator>(CmpLHS) && 505 isa<Constant>(CmpLHS->getOperand(1))) { 506 // Stop if the chain extends outside of the loop 507 if (!L->contains(CmpLHS)) 508 return; 509 InstChain.push_back(cast<BinaryOperator>(CmpLHS)); 510 CmpLHS = dyn_cast<Instruction>(CmpLHS->getOperand(0)); 511 if (CmpLHS) 512 CmpPHI = dyn_cast<PHINode>(CmpLHS); 513 } 514 if (!CmpPHI || !L->contains(CmpPHI)) 515 return; 516 517 // Trace the phi node to find all values that come from successors of BB 518 SmallPtrSet<PHINode*, 8> VisitedInsts; 519 SmallVector<PHINode*, 8> WorkList; 520 WorkList.push_back(CmpPHI); 521 VisitedInsts.insert(CmpPHI); 522 while (!WorkList.empty()) { 523 PHINode *P = WorkList.back(); 524 WorkList.pop_back(); 525 for (BasicBlock *B : P->blocks()) { 526 // Skip blocks that aren't part of the loop 527 if (!L->contains(B)) 528 continue; 529 Value *V = P->getIncomingValueForBlock(B); 530 // If the source is a PHI add it to the work list if we haven't 531 // already visited it. 532 if (PHINode *PN = dyn_cast<PHINode>(V)) { 533 if (VisitedInsts.insert(PN).second) 534 WorkList.push_back(PN); 535 continue; 536 } 537 // If this incoming value is a constant and B is a successor of BB, then 538 // we can constant-evaluate the compare to see if it makes the branch be 539 // taken or not. 540 Constant *CmpLHSConst = dyn_cast<Constant>(V); 541 if (!CmpLHSConst || 542 std::find(succ_begin(BB), succ_end(BB), B) == succ_end(BB)) 543 continue; 544 // First collapse InstChain 545 for (Instruction *I : llvm::reverse(InstChain)) { 546 CmpLHSConst = ConstantExpr::get(I->getOpcode(), CmpLHSConst, 547 cast<Constant>(I->getOperand(1)), true); 548 if (!CmpLHSConst) 549 break; 550 } 551 if (!CmpLHSConst) 552 continue; 553 // Now constant-evaluate the compare 554 Constant *Result = ConstantExpr::getCompare(CI->getPredicate(), 555 CmpLHSConst, CmpConst, true); 556 // If the result means we don't branch to the block then that block is 557 // unlikely. 558 if (Result && 559 ((Result->isZeroValue() && B == BI->getSuccessor(0)) || 560 (Result->isOneValue() && B == BI->getSuccessor(1)))) 561 UnlikelyBlocks.insert(B); 562 } 563 } 564 } 565 566 // Calculate Edge Weights using "Loop Branch Heuristics". Predict backedges 567 // as taken, exiting edges as not-taken. 568 bool BranchProbabilityInfo::calcLoopBranchHeuristics(const BasicBlock *BB, 569 const LoopInfo &LI, 570 SccInfo &SccI) { 571 int SccNum; 572 Loop *L = LI.getLoopFor(BB); 573 if (!L) { 574 SccNum = getSCCNum(BB, SccI); 575 if (SccNum < 0) 576 return false; 577 } 578 579 SmallPtrSet<const BasicBlock*, 8> UnlikelyBlocks; 580 if (L) 581 computeUnlikelySuccessors(BB, L, UnlikelyBlocks); 582 583 SmallVector<unsigned, 8> BackEdges; 584 SmallVector<unsigned, 8> ExitingEdges; 585 SmallVector<unsigned, 8> InEdges; // Edges from header to the loop. 586 SmallVector<unsigned, 8> UnlikelyEdges; 587 588 for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) { 589 // Use LoopInfo if we have it, otherwise fall-back to SCC info to catch 590 // irreducible loops. 591 if (L) { 592 if (UnlikelyBlocks.count(*I) != 0) 593 UnlikelyEdges.push_back(I.getSuccessorIndex()); 594 else if (!L->contains(*I)) 595 ExitingEdges.push_back(I.getSuccessorIndex()); 596 else if (L->getHeader() == *I) 597 BackEdges.push_back(I.getSuccessorIndex()); 598 else 599 InEdges.push_back(I.getSuccessorIndex()); 600 } else { 601 if (getSCCNum(*I, SccI) != SccNum) 602 ExitingEdges.push_back(I.getSuccessorIndex()); 603 else if (isSCCHeader(*I, SccNum, SccI)) 604 BackEdges.push_back(I.getSuccessorIndex()); 605 else 606 InEdges.push_back(I.getSuccessorIndex()); 607 } 608 } 609 610 if (BackEdges.empty() && ExitingEdges.empty() && UnlikelyEdges.empty()) 611 return false; 612 613 // Collect the sum of probabilities of back-edges/in-edges/exiting-edges, and 614 // normalize them so that they sum up to one. 615 unsigned Denom = (BackEdges.empty() ? 0 : LBH_TAKEN_WEIGHT) + 616 (InEdges.empty() ? 0 : LBH_TAKEN_WEIGHT) + 617 (UnlikelyEdges.empty() ? 0 : LBH_UNLIKELY_WEIGHT) + 618 (ExitingEdges.empty() ? 0 : LBH_NONTAKEN_WEIGHT); 619 620 if (uint32_t numBackEdges = BackEdges.size()) { 621 BranchProbability TakenProb = BranchProbability(LBH_TAKEN_WEIGHT, Denom); 622 auto Prob = TakenProb / numBackEdges; 623 for (unsigned SuccIdx : BackEdges) 624 setEdgeProbability(BB, SuccIdx, Prob); 625 } 626 627 if (uint32_t numInEdges = InEdges.size()) { 628 BranchProbability TakenProb = BranchProbability(LBH_TAKEN_WEIGHT, Denom); 629 auto Prob = TakenProb / numInEdges; 630 for (unsigned SuccIdx : InEdges) 631 setEdgeProbability(BB, SuccIdx, Prob); 632 } 633 634 if (uint32_t numExitingEdges = ExitingEdges.size()) { 635 BranchProbability NotTakenProb = BranchProbability(LBH_NONTAKEN_WEIGHT, 636 Denom); 637 auto Prob = NotTakenProb / numExitingEdges; 638 for (unsigned SuccIdx : ExitingEdges) 639 setEdgeProbability(BB, SuccIdx, Prob); 640 } 641 642 if (uint32_t numUnlikelyEdges = UnlikelyEdges.size()) { 643 BranchProbability UnlikelyProb = BranchProbability(LBH_UNLIKELY_WEIGHT, 644 Denom); 645 auto Prob = UnlikelyProb / numUnlikelyEdges; 646 for (unsigned SuccIdx : UnlikelyEdges) 647 setEdgeProbability(BB, SuccIdx, Prob); 648 } 649 650 return true; 651 } 652 653 bool BranchProbabilityInfo::calcZeroHeuristics(const BasicBlock *BB, 654 const TargetLibraryInfo *TLI) { 655 const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()); 656 if (!BI || !BI->isConditional()) 657 return false; 658 659 Value *Cond = BI->getCondition(); 660 ICmpInst *CI = dyn_cast<ICmpInst>(Cond); 661 if (!CI) 662 return false; 663 664 Value *RHS = CI->getOperand(1); 665 ConstantInt *CV = dyn_cast<ConstantInt>(RHS); 666 if (!CV) 667 return false; 668 669 // If the LHS is the result of AND'ing a value with a single bit bitmask, 670 // we don't have information about probabilities. 671 if (Instruction *LHS = dyn_cast<Instruction>(CI->getOperand(0))) 672 if (LHS->getOpcode() == Instruction::And) 673 if (ConstantInt *AndRHS = dyn_cast<ConstantInt>(LHS->getOperand(1))) 674 if (AndRHS->getValue().isPowerOf2()) 675 return false; 676 677 // Check if the LHS is the return value of a library function 678 LibFunc Func = NumLibFuncs; 679 if (TLI) 680 if (CallInst *Call = dyn_cast<CallInst>(CI->getOperand(0))) 681 if (Function *CalledFn = Call->getCalledFunction()) 682 TLI->getLibFunc(*CalledFn, Func); 683 684 bool isProb; 685 if (Func == LibFunc_strcasecmp || 686 Func == LibFunc_strcmp || 687 Func == LibFunc_strncasecmp || 688 Func == LibFunc_strncmp || 689 Func == LibFunc_memcmp) { 690 // strcmp and similar functions return zero, negative, or positive, if the 691 // first string is equal, less, or greater than the second. We consider it 692 // likely that the strings are not equal, so a comparison with zero is 693 // probably false, but also a comparison with any other number is also 694 // probably false given that what exactly is returned for nonzero values is 695 // not specified. Any kind of comparison other than equality we know 696 // nothing about. 697 switch (CI->getPredicate()) { 698 case CmpInst::ICMP_EQ: 699 isProb = false; 700 break; 701 case CmpInst::ICMP_NE: 702 isProb = true; 703 break; 704 default: 705 return false; 706 } 707 } else if (CV->isZero()) { 708 switch (CI->getPredicate()) { 709 case CmpInst::ICMP_EQ: 710 // X == 0 -> Unlikely 711 isProb = false; 712 break; 713 case CmpInst::ICMP_NE: 714 // X != 0 -> Likely 715 isProb = true; 716 break; 717 case CmpInst::ICMP_SLT: 718 // X < 0 -> Unlikely 719 isProb = false; 720 break; 721 case CmpInst::ICMP_SGT: 722 // X > 0 -> Likely 723 isProb = true; 724 break; 725 default: 726 return false; 727 } 728 } else if (CV->isOne() && CI->getPredicate() == CmpInst::ICMP_SLT) { 729 // InstCombine canonicalizes X <= 0 into X < 1. 730 // X <= 0 -> Unlikely 731 isProb = false; 732 } else if (CV->isMinusOne()) { 733 switch (CI->getPredicate()) { 734 case CmpInst::ICMP_EQ: 735 // X == -1 -> Unlikely 736 isProb = false; 737 break; 738 case CmpInst::ICMP_NE: 739 // X != -1 -> Likely 740 isProb = true; 741 break; 742 case CmpInst::ICMP_SGT: 743 // InstCombine canonicalizes X >= 0 into X > -1. 744 // X >= 0 -> Likely 745 isProb = true; 746 break; 747 default: 748 return false; 749 } 750 } else { 751 return false; 752 } 753 754 unsigned TakenIdx = 0, NonTakenIdx = 1; 755 756 if (!isProb) 757 std::swap(TakenIdx, NonTakenIdx); 758 759 BranchProbability TakenProb(ZH_TAKEN_WEIGHT, 760 ZH_TAKEN_WEIGHT + ZH_NONTAKEN_WEIGHT); 761 setEdgeProbability(BB, TakenIdx, TakenProb); 762 setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl()); 763 return true; 764 } 765 766 bool BranchProbabilityInfo::calcFloatingPointHeuristics(const BasicBlock *BB) { 767 const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()); 768 if (!BI || !BI->isConditional()) 769 return false; 770 771 Value *Cond = BI->getCondition(); 772 FCmpInst *FCmp = dyn_cast<FCmpInst>(Cond); 773 if (!FCmp) 774 return false; 775 776 bool isProb; 777 if (FCmp->isEquality()) { 778 // f1 == f2 -> Unlikely 779 // f1 != f2 -> Likely 780 isProb = !FCmp->isTrueWhenEqual(); 781 } else if (FCmp->getPredicate() == FCmpInst::FCMP_ORD) { 782 // !isnan -> Likely 783 isProb = true; 784 } else if (FCmp->getPredicate() == FCmpInst::FCMP_UNO) { 785 // isnan -> Unlikely 786 isProb = false; 787 } else { 788 return false; 789 } 790 791 unsigned TakenIdx = 0, NonTakenIdx = 1; 792 793 if (!isProb) 794 std::swap(TakenIdx, NonTakenIdx); 795 796 BranchProbability TakenProb(FPH_TAKEN_WEIGHT, 797 FPH_TAKEN_WEIGHT + FPH_NONTAKEN_WEIGHT); 798 setEdgeProbability(BB, TakenIdx, TakenProb); 799 setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl()); 800 return true; 801 } 802 803 bool BranchProbabilityInfo::calcInvokeHeuristics(const BasicBlock *BB) { 804 const InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator()); 805 if (!II) 806 return false; 807 808 BranchProbability TakenProb(IH_TAKEN_WEIGHT, 809 IH_TAKEN_WEIGHT + IH_NONTAKEN_WEIGHT); 810 setEdgeProbability(BB, 0 /*Index for Normal*/, TakenProb); 811 setEdgeProbability(BB, 1 /*Index for Unwind*/, TakenProb.getCompl()); 812 return true; 813 } 814 815 void BranchProbabilityInfo::releaseMemory() { 816 Probs.clear(); 817 } 818 819 void BranchProbabilityInfo::print(raw_ostream &OS) const { 820 OS << "---- Branch Probabilities ----\n"; 821 // We print the probabilities from the last function the analysis ran over, 822 // or the function it is currently running over. 823 assert(LastF && "Cannot print prior to running over a function"); 824 for (const auto &BI : *LastF) { 825 for (succ_const_iterator SI = succ_begin(&BI), SE = succ_end(&BI); SI != SE; 826 ++SI) { 827 printEdgeProbability(OS << " ", &BI, *SI); 828 } 829 } 830 } 831 832 bool BranchProbabilityInfo:: 833 isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const { 834 // Hot probability is at least 4/5 = 80% 835 // FIXME: Compare against a static "hot" BranchProbability. 836 return getEdgeProbability(Src, Dst) > BranchProbability(4, 5); 837 } 838 839 const BasicBlock * 840 BranchProbabilityInfo::getHotSucc(const BasicBlock *BB) const { 841 auto MaxProb = BranchProbability::getZero(); 842 const BasicBlock *MaxSucc = nullptr; 843 844 for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) { 845 const BasicBlock *Succ = *I; 846 auto Prob = getEdgeProbability(BB, Succ); 847 if (Prob > MaxProb) { 848 MaxProb = Prob; 849 MaxSucc = Succ; 850 } 851 } 852 853 // Hot probability is at least 4/5 = 80% 854 if (MaxProb > BranchProbability(4, 5)) 855 return MaxSucc; 856 857 return nullptr; 858 } 859 860 /// Get the raw edge probability for the edge. If can't find it, return a 861 /// default probability 1/N where N is the number of successors. Here an edge is 862 /// specified using PredBlock and an 863 /// index to the successors. 864 BranchProbability 865 BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src, 866 unsigned IndexInSuccessors) const { 867 auto I = Probs.find(std::make_pair(Src, IndexInSuccessors)); 868 869 if (I != Probs.end()) 870 return I->second; 871 872 return {1, static_cast<uint32_t>(succ_size(Src))}; 873 } 874 875 BranchProbability 876 BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src, 877 succ_const_iterator Dst) const { 878 return getEdgeProbability(Src, Dst.getSuccessorIndex()); 879 } 880 881 /// Get the raw edge probability calculated for the block pair. This returns the 882 /// sum of all raw edge probabilities from Src to Dst. 883 BranchProbability 884 BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src, 885 const BasicBlock *Dst) const { 886 auto Prob = BranchProbability::getZero(); 887 bool FoundProb = false; 888 for (succ_const_iterator I = succ_begin(Src), E = succ_end(Src); I != E; ++I) 889 if (*I == Dst) { 890 auto MapI = Probs.find(std::make_pair(Src, I.getSuccessorIndex())); 891 if (MapI != Probs.end()) { 892 FoundProb = true; 893 Prob += MapI->second; 894 } 895 } 896 uint32_t succ_num = std::distance(succ_begin(Src), succ_end(Src)); 897 return FoundProb ? Prob : BranchProbability(1, succ_num); 898 } 899 900 /// Set the edge probability for a given edge specified by PredBlock and an 901 /// index to the successors. 902 void BranchProbabilityInfo::setEdgeProbability(const BasicBlock *Src, 903 unsigned IndexInSuccessors, 904 BranchProbability Prob) { 905 Probs[std::make_pair(Src, IndexInSuccessors)] = Prob; 906 Handles.insert(BasicBlockCallbackVH(Src, this)); 907 LLVM_DEBUG(dbgs() << "set edge " << Src->getName() << " -> " 908 << IndexInSuccessors << " successor probability to " << Prob 909 << "\n"); 910 } 911 912 raw_ostream & 913 BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS, 914 const BasicBlock *Src, 915 const BasicBlock *Dst) const { 916 const BranchProbability Prob = getEdgeProbability(Src, Dst); 917 OS << "edge " << Src->getName() << " -> " << Dst->getName() 918 << " probability is " << Prob 919 << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n"); 920 921 return OS; 922 } 923 924 void BranchProbabilityInfo::eraseBlock(const BasicBlock *BB) { 925 for (auto I = Probs.begin(), E = Probs.end(); I != E; ++I) { 926 auto Key = I->first; 927 if (Key.first == BB) 928 Probs.erase(Key); 929 } 930 } 931 932 void BranchProbabilityInfo::calculate(const Function &F, const LoopInfo &LI, 933 const TargetLibraryInfo *TLI) { 934 LLVM_DEBUG(dbgs() << "---- Branch Probability Info : " << F.getName() 935 << " ----\n\n"); 936 LastF = &F; // Store the last function we ran on for printing. 937 assert(PostDominatedByUnreachable.empty()); 938 assert(PostDominatedByColdCall.empty()); 939 940 // Record SCC numbers of blocks in the CFG to identify irreducible loops. 941 // FIXME: We could only calculate this if the CFG is known to be irreducible 942 // (perhaps cache this info in LoopInfo if we can easily calculate it there?). 943 int SccNum = 0; 944 SccInfo SccI; 945 for (scc_iterator<const Function *> It = scc_begin(&F); !It.isAtEnd(); 946 ++It, ++SccNum) { 947 // Ignore single-block SCCs since they either aren't loops or LoopInfo will 948 // catch them. 949 const std::vector<const BasicBlock *> &Scc = *It; 950 if (Scc.size() == 1) 951 continue; 952 953 LLVM_DEBUG(dbgs() << "BPI: SCC " << SccNum << ":"); 954 for (auto *BB : Scc) { 955 LLVM_DEBUG(dbgs() << " " << BB->getName()); 956 SccI.SccNums[BB] = SccNum; 957 } 958 LLVM_DEBUG(dbgs() << "\n"); 959 } 960 961 // Walk the basic blocks in post-order so that we can build up state about 962 // the successors of a block iteratively. 963 for (auto BB : post_order(&F.getEntryBlock())) { 964 LLVM_DEBUG(dbgs() << "Computing probabilities for " << BB->getName() 965 << "\n"); 966 updatePostDominatedByUnreachable(BB); 967 updatePostDominatedByColdCall(BB); 968 // If there is no at least two successors, no sense to set probability. 969 if (BB->getTerminator()->getNumSuccessors() < 2) 970 continue; 971 if (calcMetadataWeights(BB)) 972 continue; 973 if (calcInvokeHeuristics(BB)) 974 continue; 975 if (calcUnreachableHeuristics(BB)) 976 continue; 977 if (calcColdCallHeuristics(BB)) 978 continue; 979 if (calcLoopBranchHeuristics(BB, LI, SccI)) 980 continue; 981 if (calcPointerHeuristics(BB)) 982 continue; 983 if (calcZeroHeuristics(BB, TLI)) 984 continue; 985 if (calcFloatingPointHeuristics(BB)) 986 continue; 987 } 988 989 PostDominatedByUnreachable.clear(); 990 PostDominatedByColdCall.clear(); 991 992 if (PrintBranchProb && 993 (PrintBranchProbFuncName.empty() || 994 F.getName().equals(PrintBranchProbFuncName))) { 995 print(dbgs()); 996 } 997 } 998 999 void BranchProbabilityInfoWrapperPass::getAnalysisUsage( 1000 AnalysisUsage &AU) const { 1001 // We require DT so it's available when LI is available. The LI updating code 1002 // asserts that DT is also present so if we don't make sure that we have DT 1003 // here, that assert will trigger. 1004 AU.addRequired<DominatorTreeWrapperPass>(); 1005 AU.addRequired<LoopInfoWrapperPass>(); 1006 AU.addRequired<TargetLibraryInfoWrapperPass>(); 1007 AU.setPreservesAll(); 1008 } 1009 1010 bool BranchProbabilityInfoWrapperPass::runOnFunction(Function &F) { 1011 const LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 1012 const TargetLibraryInfo &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(); 1013 BPI.calculate(F, LI, &TLI); 1014 return false; 1015 } 1016 1017 void BranchProbabilityInfoWrapperPass::releaseMemory() { BPI.releaseMemory(); } 1018 1019 void BranchProbabilityInfoWrapperPass::print(raw_ostream &OS, 1020 const Module *) const { 1021 BPI.print(OS); 1022 } 1023 1024 AnalysisKey BranchProbabilityAnalysis::Key; 1025 BranchProbabilityInfo 1026 BranchProbabilityAnalysis::run(Function &F, FunctionAnalysisManager &AM) { 1027 BranchProbabilityInfo BPI; 1028 BPI.calculate(F, AM.getResult<LoopAnalysis>(F), &AM.getResult<TargetLibraryAnalysis>(F)); 1029 return BPI; 1030 } 1031 1032 PreservedAnalyses 1033 BranchProbabilityPrinterPass::run(Function &F, FunctionAnalysisManager &AM) { 1034 OS << "Printing analysis results of BPI for function " 1035 << "'" << F.getName() << "':" 1036 << "\n"; 1037 AM.getResult<BranchProbabilityAnalysis>(F).print(OS); 1038 return PreservedAnalyses::all(); 1039 } 1040