Home | History | Annotate | Download | only in Analysis 
      1 //===-- BranchProbabilityInfo.cpp - Branch Probability Analysis -----------===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 //
     10 // Loops should be simplified before this analysis.
     11 //
     12 //===----------------------------------------------------------------------===//
     13 
     14 #include "llvm/Analysis/BranchProbabilityInfo.h"
     15 #include "llvm/ADT/PostOrderIterator.h"
     16 #include "llvm/Analysis/LoopInfo.h"
     17 #include "llvm/IR/Constants.h"
     18 #include "llvm/IR/Function.h"
     19 #include "llvm/IR/Instructions.h"
     20 #include "llvm/IR/LLVMContext.h"
     21 #include "llvm/IR/Metadata.h"
     22 #include "llvm/Support/CFG.h"
     23 #include "llvm/Support/Debug.h"
     24 
     25 using namespace llvm;
     26 
     27 INITIALIZE_PASS_BEGIN(BranchProbabilityInfo, "branch-prob",
     28                       "Branch Probability Analysis", false, true)
     29 INITIALIZE_PASS_DEPENDENCY(LoopInfo)
     30 INITIALIZE_PASS_END(BranchProbabilityInfo, "branch-prob",
     31                     "Branch Probability Analysis", false, true)
     32 
     33 char 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
     55 static const uint32_t LBH_TAKEN_WEIGHT = 124;
     56 static 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.
     62 static 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.
     70 static const uint32_t UR_NONTAKEN_WEIGHT = 1024*1024 - 1;
     71 
     72 static const uint32_t PH_TAKEN_WEIGHT = 20;
     73 static const uint32_t PH_NONTAKEN_WEIGHT = 12;
     74 
     75 static const uint32_t ZH_TAKEN_WEIGHT = 20;
     76 static const uint32_t ZH_NONTAKEN_WEIGHT = 12;
     77 
     78 static const uint32_t FPH_TAKEN_WEIGHT = 20;
     79 static 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.
     86 static 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.
     92 static const uint32_t IH_NONTAKEN_WEIGHT = 1;
     93 
     94 // Standard weight value. Used when none of the heuristics set weight for
     95 // the edge.
     96 static const uint32_t NORMAL_WEIGHT = 16;
     97 
     98 // Minimum weight of an edge. Please note, that weight is NEVER 0.
     99 static const uint32_t MIN_WEIGHT = 1;
    100 
    101 static 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.
    110 bool 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.
    160 bool 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.
    198 bool 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.
    231 bool 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 
    285 bool 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 
    345 bool 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 
    381 bool 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 
    391 void BranchProbabilityInfo::getAnalysisUsage(AnalysisUsage &AU) const {
    392   AU.addRequired<LoopInfo>();
    393   AU.setPreservesAll();
    394 }
    395 
    396 bool 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 
    426 void 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 
    440 uint32_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 
    454 bool BranchProbabilityInfo::
    455 isEdgeHot(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 
    461 BasicBlock *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.
    490 uint32_t BranchProbabilityInfo::
    491 getEdgeWeight(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.
    503 uint32_t BranchProbabilityInfo::
    504 getEdgeWeight(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.
    518 void BranchProbabilityInfo::
    519 setEdgeWeight(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.
    528 BranchProbability BranchProbabilityInfo::
    529 getEdgeProbability(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.
    538 BranchProbability BranchProbabilityInfo::
    539 getEdgeProbability(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 
    547 raw_ostream &
    548 BranchProbabilityInfo::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