1 //===-- BranchProbabilityInfo.cpp - Branch Probability Analysis -*- C++ -*-===// 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/Instructions.h" 16 #include "llvm/LLVMContext.h" 17 #include "llvm/Metadata.h" 18 #include "llvm/Analysis/BranchProbabilityInfo.h" 19 #include "llvm/Analysis/LoopInfo.h" 20 #include "llvm/Support/Debug.h" 21 22 using namespace llvm; 23 24 INITIALIZE_PASS_BEGIN(BranchProbabilityInfo, "branch-prob", 25 "Branch Probability Analysis", false, true) 26 INITIALIZE_PASS_DEPENDENCY(LoopInfo) 27 INITIALIZE_PASS_END(BranchProbabilityInfo, "branch-prob", 28 "Branch Probability Analysis", false, true) 29 30 char BranchProbabilityInfo::ID = 0; 31 32 namespace { 33 // Please note that BranchProbabilityAnalysis is not a FunctionPass. 34 // It is created by BranchProbabilityInfo (which is a FunctionPass), which 35 // provides a clear interface. Thanks to that, all heuristics and other 36 // private methods are hidden in the .cpp file. 37 class BranchProbabilityAnalysis { 38 39 typedef std::pair<const BasicBlock *, const BasicBlock *> Edge; 40 41 DenseMap<Edge, uint32_t> *Weights; 42 43 BranchProbabilityInfo *BP; 44 45 LoopInfo *LI; 46 47 48 // Weights are for internal use only. They are used by heuristics to help to 49 // estimate edges' probability. Example: 50 // 51 // Using "Loop Branch Heuristics" we predict weights of edges for the 52 // block BB2. 53 // ... 54 // | 55 // V 56 // BB1<-+ 57 // | | 58 // | | (Weight = 124) 59 // V | 60 // BB2--+ 61 // | 62 // | (Weight = 4) 63 // V 64 // BB3 65 // 66 // Probability of the edge BB2->BB1 = 124 / (124 + 4) = 0.96875 67 // Probability of the edge BB2->BB3 = 4 / (124 + 4) = 0.03125 68 69 static const uint32_t LBH_TAKEN_WEIGHT = 124; 70 static const uint32_t LBH_NONTAKEN_WEIGHT = 4; 71 72 static const uint32_t RH_TAKEN_WEIGHT = 24; 73 static const uint32_t RH_NONTAKEN_WEIGHT = 8; 74 75 static const uint32_t PH_TAKEN_WEIGHT = 20; 76 static const uint32_t PH_NONTAKEN_WEIGHT = 12; 77 78 static const uint32_t ZH_TAKEN_WEIGHT = 20; 79 static const uint32_t ZH_NONTAKEN_WEIGHT = 12; 80 81 // Standard weight value. Used when none of the heuristics set weight for 82 // the edge. 83 static const uint32_t NORMAL_WEIGHT = 16; 84 85 // Minimum weight of an edge. Please note, that weight is NEVER 0. 86 static const uint32_t MIN_WEIGHT = 1; 87 88 // Return TRUE if BB leads directly to a Return Instruction. 89 static bool isReturningBlock(BasicBlock *BB) { 90 SmallPtrSet<BasicBlock *, 8> Visited; 91 92 while (true) { 93 TerminatorInst *TI = BB->getTerminator(); 94 if (isa<ReturnInst>(TI)) 95 return true; 96 97 if (TI->getNumSuccessors() > 1) 98 break; 99 100 // It is unreachable block which we can consider as a return instruction. 101 if (TI->getNumSuccessors() == 0) 102 return true; 103 104 Visited.insert(BB); 105 BB = TI->getSuccessor(0); 106 107 // Stop if cycle is detected. 108 if (Visited.count(BB)) 109 return false; 110 } 111 112 return false; 113 } 114 115 uint32_t getMaxWeightFor(BasicBlock *BB) const { 116 return UINT32_MAX / BB->getTerminator()->getNumSuccessors(); 117 } 118 119 public: 120 BranchProbabilityAnalysis(DenseMap<Edge, uint32_t> *W, 121 BranchProbabilityInfo *BP, LoopInfo *LI) 122 : Weights(W), BP(BP), LI(LI) { 123 } 124 125 // Metadata Weights 126 bool calcMetadataWeights(BasicBlock *BB); 127 128 // Return Heuristics 129 bool calcReturnHeuristics(BasicBlock *BB); 130 131 // Pointer Heuristics 132 bool calcPointerHeuristics(BasicBlock *BB); 133 134 // Loop Branch Heuristics 135 bool calcLoopBranchHeuristics(BasicBlock *BB); 136 137 // Zero Heurestics 138 bool calcZeroHeuristics(BasicBlock *BB); 139 140 bool runOnFunction(Function &F); 141 }; 142 } // end anonymous namespace 143 144 // Propagate existing explicit probabilities from either profile data or 145 // 'expect' intrinsic processing. 146 bool BranchProbabilityAnalysis::calcMetadataWeights(BasicBlock *BB) { 147 TerminatorInst *TI = BB->getTerminator(); 148 if (TI->getNumSuccessors() == 1) 149 return false; 150 if (!isa<BranchInst>(TI) && !isa<SwitchInst>(TI)) 151 return false; 152 153 MDNode *WeightsNode = TI->getMetadata(LLVMContext::MD_prof); 154 if (!WeightsNode) 155 return false; 156 157 // Ensure there are weights for all of the successors. Note that the first 158 // operand to the metadata node is a name, not a weight. 159 if (WeightsNode->getNumOperands() != TI->getNumSuccessors() + 1) 160 return false; 161 162 // Build up the final weights that will be used in a temporary buffer, but 163 // don't add them until all weihts are present. Each weight value is clamped 164 // to [1, getMaxWeightFor(BB)]. 165 uint32_t WeightLimit = getMaxWeightFor(BB); 166 SmallVector<uint32_t, 2> Weights; 167 Weights.reserve(TI->getNumSuccessors()); 168 for (unsigned i = 1, e = WeightsNode->getNumOperands(); i != e; ++i) { 169 ConstantInt *Weight = dyn_cast<ConstantInt>(WeightsNode->getOperand(i)); 170 if (!Weight) 171 return false; 172 Weights.push_back( 173 std::max<uint32_t>(1, Weight->getLimitedValue(WeightLimit))); 174 } 175 assert(Weights.size() == TI->getNumSuccessors() && "Checked above"); 176 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 177 BP->setEdgeWeight(BB, TI->getSuccessor(i), Weights[i]); 178 179 return true; 180 } 181 182 // Calculate Edge Weights using "Return Heuristics". Predict a successor which 183 // leads directly to Return Instruction will not be taken. 184 bool BranchProbabilityAnalysis::calcReturnHeuristics(BasicBlock *BB){ 185 if (BB->getTerminator()->getNumSuccessors() == 1) 186 return false; 187 188 SmallPtrSet<BasicBlock *, 4> ReturningEdges; 189 SmallPtrSet<BasicBlock *, 4> StayEdges; 190 191 for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) { 192 BasicBlock *Succ = *I; 193 if (isReturningBlock(Succ)) 194 ReturningEdges.insert(Succ); 195 else 196 StayEdges.insert(Succ); 197 } 198 199 if (uint32_t numStayEdges = StayEdges.size()) { 200 uint32_t stayWeight = RH_TAKEN_WEIGHT / numStayEdges; 201 if (stayWeight < NORMAL_WEIGHT) 202 stayWeight = NORMAL_WEIGHT; 203 204 for (SmallPtrSet<BasicBlock *, 4>::iterator I = StayEdges.begin(), 205 E = StayEdges.end(); I != E; ++I) 206 BP->setEdgeWeight(BB, *I, stayWeight); 207 } 208 209 if (uint32_t numRetEdges = ReturningEdges.size()) { 210 uint32_t retWeight = RH_NONTAKEN_WEIGHT / numRetEdges; 211 if (retWeight < MIN_WEIGHT) 212 retWeight = MIN_WEIGHT; 213 for (SmallPtrSet<BasicBlock *, 4>::iterator I = ReturningEdges.begin(), 214 E = ReturningEdges.end(); I != E; ++I) { 215 BP->setEdgeWeight(BB, *I, retWeight); 216 } 217 } 218 219 return ReturningEdges.size() > 0; 220 } 221 222 // Calculate Edge Weights using "Pointer Heuristics". Predict a comparsion 223 // between two pointer or pointer and NULL will fail. 224 bool BranchProbabilityAnalysis::calcPointerHeuristics(BasicBlock *BB) { 225 BranchInst * BI = dyn_cast<BranchInst>(BB->getTerminator()); 226 if (!BI || !BI->isConditional()) 227 return false; 228 229 Value *Cond = BI->getCondition(); 230 ICmpInst *CI = dyn_cast<ICmpInst>(Cond); 231 if (!CI || !CI->isEquality()) 232 return false; 233 234 Value *LHS = CI->getOperand(0); 235 236 if (!LHS->getType()->isPointerTy()) 237 return false; 238 239 assert(CI->getOperand(1)->getType()->isPointerTy()); 240 241 BasicBlock *Taken = BI->getSuccessor(0); 242 BasicBlock *NonTaken = BI->getSuccessor(1); 243 244 // p != 0 -> isProb = true 245 // p == 0 -> isProb = false 246 // p != q -> isProb = true 247 // p == q -> isProb = false; 248 bool isProb = CI->getPredicate() == ICmpInst::ICMP_NE; 249 if (!isProb) 250 std::swap(Taken, NonTaken); 251 252 BP->setEdgeWeight(BB, Taken, PH_TAKEN_WEIGHT); 253 BP->setEdgeWeight(BB, NonTaken, PH_NONTAKEN_WEIGHT); 254 return true; 255 } 256 257 // Calculate Edge Weights using "Loop Branch Heuristics". Predict backedges 258 // as taken, exiting edges as not-taken. 259 bool BranchProbabilityAnalysis::calcLoopBranchHeuristics(BasicBlock *BB) { 260 uint32_t numSuccs = BB->getTerminator()->getNumSuccessors(); 261 262 Loop *L = LI->getLoopFor(BB); 263 if (!L) 264 return false; 265 266 SmallPtrSet<BasicBlock *, 8> BackEdges; 267 SmallPtrSet<BasicBlock *, 8> ExitingEdges; 268 SmallPtrSet<BasicBlock *, 8> InEdges; // Edges from header to the loop. 269 270 bool isHeader = BB == L->getHeader(); 271 272 for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) { 273 BasicBlock *Succ = *I; 274 Loop *SuccL = LI->getLoopFor(Succ); 275 if (SuccL != L) 276 ExitingEdges.insert(Succ); 277 else if (Succ == L->getHeader()) 278 BackEdges.insert(Succ); 279 else if (isHeader) 280 InEdges.insert(Succ); 281 } 282 283 if (uint32_t numBackEdges = BackEdges.size()) { 284 uint32_t backWeight = LBH_TAKEN_WEIGHT / numBackEdges; 285 if (backWeight < NORMAL_WEIGHT) 286 backWeight = NORMAL_WEIGHT; 287 288 for (SmallPtrSet<BasicBlock *, 8>::iterator EI = BackEdges.begin(), 289 EE = BackEdges.end(); EI != EE; ++EI) { 290 BasicBlock *Back = *EI; 291 BP->setEdgeWeight(BB, Back, backWeight); 292 } 293 } 294 295 if (uint32_t numInEdges = InEdges.size()) { 296 uint32_t inWeight = LBH_TAKEN_WEIGHT / numInEdges; 297 if (inWeight < NORMAL_WEIGHT) 298 inWeight = NORMAL_WEIGHT; 299 300 for (SmallPtrSet<BasicBlock *, 8>::iterator EI = InEdges.begin(), 301 EE = InEdges.end(); EI != EE; ++EI) { 302 BasicBlock *Back = *EI; 303 BP->setEdgeWeight(BB, Back, inWeight); 304 } 305 } 306 307 uint32_t numExitingEdges = ExitingEdges.size(); 308 if (uint32_t numNonExitingEdges = numSuccs - numExitingEdges) { 309 uint32_t exitWeight = LBH_NONTAKEN_WEIGHT / numNonExitingEdges; 310 if (exitWeight < MIN_WEIGHT) 311 exitWeight = MIN_WEIGHT; 312 313 for (SmallPtrSet<BasicBlock *, 8>::iterator EI = ExitingEdges.begin(), 314 EE = ExitingEdges.end(); EI != EE; ++EI) { 315 BasicBlock *Exiting = *EI; 316 BP->setEdgeWeight(BB, Exiting, exitWeight); 317 } 318 } 319 320 return true; 321 } 322 323 bool BranchProbabilityAnalysis::calcZeroHeuristics(BasicBlock *BB) { 324 BranchInst * BI = dyn_cast<BranchInst>(BB->getTerminator()); 325 if (!BI || !BI->isConditional()) 326 return false; 327 328 Value *Cond = BI->getCondition(); 329 ICmpInst *CI = dyn_cast<ICmpInst>(Cond); 330 if (!CI) 331 return false; 332 333 Value *RHS = CI->getOperand(1); 334 ConstantInt *CV = dyn_cast<ConstantInt>(RHS); 335 if (!CV) 336 return false; 337 338 bool isProb; 339 if (CV->isZero()) { 340 switch (CI->getPredicate()) { 341 case CmpInst::ICMP_EQ: 342 // X == 0 -> Unlikely 343 isProb = false; 344 break; 345 case CmpInst::ICMP_NE: 346 // X != 0 -> Likely 347 isProb = true; 348 break; 349 case CmpInst::ICMP_SLT: 350 // X < 0 -> Unlikely 351 isProb = false; 352 break; 353 case CmpInst::ICMP_SGT: 354 // X > 0 -> Likely 355 isProb = true; 356 break; 357 default: 358 return false; 359 } 360 } else if (CV->isOne() && CI->getPredicate() == CmpInst::ICMP_SLT) { 361 // InstCombine canonicalizes X <= 0 into X < 1. 362 // X <= 0 -> Unlikely 363 isProb = false; 364 } else if (CV->isAllOnesValue() && CI->getPredicate() == CmpInst::ICMP_SGT) { 365 // InstCombine canonicalizes X >= 0 into X > -1. 366 // X >= 0 -> Likely 367 isProb = true; 368 } else { 369 return false; 370 } 371 372 BasicBlock *Taken = BI->getSuccessor(0); 373 BasicBlock *NonTaken = BI->getSuccessor(1); 374 375 if (!isProb) 376 std::swap(Taken, NonTaken); 377 378 BP->setEdgeWeight(BB, Taken, ZH_TAKEN_WEIGHT); 379 BP->setEdgeWeight(BB, NonTaken, ZH_NONTAKEN_WEIGHT); 380 381 return true; 382 } 383 384 385 bool BranchProbabilityAnalysis::runOnFunction(Function &F) { 386 387 for (Function::iterator I = F.begin(), E = F.end(); I != E; ) { 388 BasicBlock *BB = I++; 389 390 if (calcMetadataWeights(BB)) 391 continue; 392 393 if (calcLoopBranchHeuristics(BB)) 394 continue; 395 396 if (calcReturnHeuristics(BB)) 397 continue; 398 399 if (calcPointerHeuristics(BB)) 400 continue; 401 402 calcZeroHeuristics(BB); 403 } 404 405 return false; 406 } 407 408 void BranchProbabilityInfo::getAnalysisUsage(AnalysisUsage &AU) const { 409 AU.addRequired<LoopInfo>(); 410 AU.setPreservesAll(); 411 } 412 413 bool BranchProbabilityInfo::runOnFunction(Function &F) { 414 LoopInfo &LI = getAnalysis<LoopInfo>(); 415 BranchProbabilityAnalysis BPA(&Weights, this, &LI); 416 return BPA.runOnFunction(F); 417 } 418 419 uint32_t BranchProbabilityInfo::getSumForBlock(const BasicBlock *BB) const { 420 uint32_t Sum = 0; 421 422 for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) { 423 const BasicBlock *Succ = *I; 424 uint32_t Weight = getEdgeWeight(BB, Succ); 425 uint32_t PrevSum = Sum; 426 427 Sum += Weight; 428 assert(Sum > PrevSum); (void) PrevSum; 429 } 430 431 return Sum; 432 } 433 434 bool BranchProbabilityInfo:: 435 isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const { 436 // Hot probability is at least 4/5 = 80% 437 uint32_t Weight = getEdgeWeight(Src, Dst); 438 uint32_t Sum = getSumForBlock(Src); 439 440 // FIXME: Implement BranchProbability::compare then change this code to 441 // compare this BranchProbability against a static "hot" BranchProbability. 442 return (uint64_t)Weight * 5 > (uint64_t)Sum * 4; 443 } 444 445 BasicBlock *BranchProbabilityInfo::getHotSucc(BasicBlock *BB) const { 446 uint32_t Sum = 0; 447 uint32_t MaxWeight = 0; 448 BasicBlock *MaxSucc = 0; 449 450 for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) { 451 BasicBlock *Succ = *I; 452 uint32_t Weight = getEdgeWeight(BB, Succ); 453 uint32_t PrevSum = Sum; 454 455 Sum += Weight; 456 assert(Sum > PrevSum); (void) PrevSum; 457 458 if (Weight > MaxWeight) { 459 MaxWeight = Weight; 460 MaxSucc = Succ; 461 } 462 } 463 464 // FIXME: Use BranchProbability::compare. 465 if ((uint64_t)MaxWeight * 5 > (uint64_t)Sum * 4) 466 return MaxSucc; 467 468 return 0; 469 } 470 471 // Return edge's weight. If can't find it, return DEFAULT_WEIGHT value. 472 uint32_t BranchProbabilityInfo:: 473 getEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst) const { 474 Edge E(Src, Dst); 475 DenseMap<Edge, uint32_t>::const_iterator I = Weights.find(E); 476 477 if (I != Weights.end()) 478 return I->second; 479 480 return DEFAULT_WEIGHT; 481 } 482 483 void BranchProbabilityInfo:: 484 setEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst, uint32_t Weight) { 485 Weights[std::make_pair(Src, Dst)] = Weight; 486 DEBUG(dbgs() << "set edge " << Src->getNameStr() << " -> " 487 << Dst->getNameStr() << " weight to " << Weight 488 << (isEdgeHot(Src, Dst) ? " [is HOT now]\n" : "\n")); 489 } 490 491 492 BranchProbability BranchProbabilityInfo:: 493 getEdgeProbability(const BasicBlock *Src, const BasicBlock *Dst) const { 494 495 uint32_t N = getEdgeWeight(Src, Dst); 496 uint32_t D = getSumForBlock(Src); 497 498 return BranchProbability(N, D); 499 } 500 501 raw_ostream & 502 BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS, BasicBlock *Src, 503 BasicBlock *Dst) const { 504 505 const BranchProbability Prob = getEdgeProbability(Src, Dst); 506 OS << "edge " << Src->getNameStr() << " -> " << Dst->getNameStr() 507 << " probability is " << Prob 508 << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n"); 509 510 return OS; 511 } 512
