LCOV - code coverage report
Current view: top level - lib/Analysis - BranchProbabilityInfo.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 303 310 97.7 %
Date: 2018-02-21 06:32:55 Functions: 32 33 97.0 %
Legend: Lines: hit not hit

          Line data    Source code
       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/Function.h"
      26             : #include "llvm/IR/InstrTypes.h"
      27             : #include "llvm/IR/Instruction.h"
      28             : #include "llvm/IR/Instructions.h"
      29             : #include "llvm/IR/LLVMContext.h"
      30             : #include "llvm/IR/Metadata.h"
      31             : #include "llvm/IR/PassManager.h"
      32             : #include "llvm/IR/Type.h"
      33             : #include "llvm/IR/Value.h"
      34             : #include "llvm/Pass.h"
      35             : #include "llvm/Support/BranchProbability.h"
      36             : #include "llvm/Support/Casting.h"
      37             : #include "llvm/Support/Debug.h"
      38             : #include "llvm/Support/raw_ostream.h"
      39             : #include <cassert>
      40             : #include <cstdint>
      41             : #include <iterator>
      42             : #include <utility>
      43             : 
      44             : using namespace llvm;
      45             : 
      46             : #define DEBUG_TYPE "branch-prob"
      47             : 
      48       97171 : static cl::opt<bool> PrintBranchProb(
      49      194342 :     "print-bpi", cl::init(false), cl::Hidden,
      50      291513 :     cl::desc("Print the branch probability info."));
      51             : 
      52       97171 : cl::opt<std::string> PrintBranchProbFuncName(
      53             :     "print-bpi-func-name", cl::Hidden,
      54       97171 :     cl::desc("The option to specify the name of the function "
      55       97171 :              "whose branch probability info is printed."));
      56             : 
      57       31784 : INITIALIZE_PASS_BEGIN(BranchProbabilityInfoWrapperPass, "branch-prob",
      58             :                       "Branch Probability Analysis", false, true)
      59       31784 : INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
      60       31784 : INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
      61      369886 : INITIALIZE_PASS_END(BranchProbabilityInfoWrapperPass, "branch-prob",
      62             :                     "Branch Probability Analysis", false, true)
      63             : 
      64             : char BranchProbabilityInfoWrapperPass::ID = 0;
      65             : 
      66             : // Weights are for internal use only. They are used by heuristics to help to
      67             : // estimate edges' probability. Example:
      68             : //
      69             : // Using "Loop Branch Heuristics" we predict weights of edges for the
      70             : // block BB2.
      71             : //         ...
      72             : //          |
      73             : //          V
      74             : //         BB1<-+
      75             : //          |   |
      76             : //          |   | (Weight = 124)
      77             : //          V   |
      78             : //         BB2--+
      79             : //          |
      80             : //          | (Weight = 4)
      81             : //          V
      82             : //         BB3
      83             : //
      84             : // Probability of the edge BB2->BB1 = 124 / (124 + 4) = 0.96875
      85             : // Probability of the edge BB2->BB3 = 4 / (124 + 4) = 0.03125
      86             : static const uint32_t LBH_TAKEN_WEIGHT = 124;
      87             : static const uint32_t LBH_NONTAKEN_WEIGHT = 4;
      88             : 
      89             : /// \brief Unreachable-terminating branch taken probability.
      90             : ///
      91             : /// This is the probability for a branch being taken to a block that terminates
      92             : /// (eventually) in unreachable. These are predicted as unlikely as possible.
      93             : /// All reachable probability will equally share the remaining part.
      94       97171 : static const BranchProbability UR_TAKEN_PROB = BranchProbability::getRaw(1);
      95             : 
      96             : /// \brief Weight for a branch taken going into a cold block.
      97             : ///
      98             : /// This is the weight for a branch taken toward a block marked
      99             : /// cold.  A block is marked cold if it's postdominated by a
     100             : /// block containing a call to a cold function.  Cold functions
     101             : /// are those marked with attribute 'cold'.
     102             : static const uint32_t CC_TAKEN_WEIGHT = 4;
     103             : 
     104             : /// \brief Weight for a branch not-taken into a cold block.
     105             : ///
     106             : /// This is the weight for a branch not taken toward a block marked
     107             : /// cold.
     108             : static const uint32_t CC_NONTAKEN_WEIGHT = 64;
     109             : 
     110             : static const uint32_t PH_TAKEN_WEIGHT = 20;
     111             : static const uint32_t PH_NONTAKEN_WEIGHT = 12;
     112             : 
     113             : static const uint32_t ZH_TAKEN_WEIGHT = 20;
     114             : static const uint32_t ZH_NONTAKEN_WEIGHT = 12;
     115             : 
     116             : static const uint32_t FPH_TAKEN_WEIGHT = 20;
     117             : static const uint32_t FPH_NONTAKEN_WEIGHT = 12;
     118             : 
     119             : /// \brief Invoke-terminating normal branch taken weight
     120             : ///
     121             : /// This is the weight for branching to the normal destination of an invoke
     122             : /// instruction. We expect this to happen most of the time. Set the weight to an
     123             : /// absurdly high value so that nested loops subsume it.
     124             : static const uint32_t IH_TAKEN_WEIGHT = 1024 * 1024 - 1;
     125             : 
     126             : /// \brief Invoke-terminating normal branch not-taken weight.
     127             : ///
     128             : /// This is the weight for branching to the unwind destination of an invoke
     129             : /// instruction. This is essentially never taken.
     130             : static const uint32_t IH_NONTAKEN_WEIGHT = 1;
     131             : 
     132             : /// \brief Add \p BB to PostDominatedByUnreachable set if applicable.
     133             : void
     134     1528191 : BranchProbabilityInfo::updatePostDominatedByUnreachable(const BasicBlock *BB) {
     135     1528191 :   const TerminatorInst *TI = BB->getTerminator();
     136     1528191 :   if (TI->getNumSuccessors() == 0) {
     137     1234941 :     if (isa<UnreachableInst>(TI) ||
     138             :         // If this block is terminated by a call to
     139             :         // @llvm.experimental.deoptimize then treat it like an unreachable since
     140             :         // the @llvm.experimental.deoptimize call is expected to practically
     141             :         // never execute.
     142      582430 :         BB->getTerminatingDeoptimizeCall())
     143       70083 :       PostDominatedByUnreachable.insert(BB);
     144             :     return;
     145             :   }
     146             : 
     147             :   // If the terminator is an InvokeInst, check only the normal destination block
     148             :   // as the unwind edge of InvokeInst is also very unlikely taken.
     149             :   if (auto *II = dyn_cast<InvokeInst>(TI)) {
     150      399766 :     if (PostDominatedByUnreachable.count(II->getNormalDest()))
     151        7467 :       PostDominatedByUnreachable.insert(BB);
     152             :     return;
     153             :   }
     154             : 
     155      675797 :   for (auto *I : successors(BB))
     156             :     // If any of successor is not post dominated then BB is also not.
     157      694157 :     if (!PostDominatedByUnreachable.count(I))
     158             :       return;
     159             : 
     160       35879 :   PostDominatedByUnreachable.insert(BB);
     161             : }
     162             : 
     163             : /// \brief Add \p BB to PostDominatedByColdCall set if applicable.
     164             : void
     165     1528191 : BranchProbabilityInfo::updatePostDominatedByColdCall(const BasicBlock *BB) {
     166             :   assert(!PostDominatedByColdCall.count(BB));
     167     1528191 :   const TerminatorInst *TI = BB->getTerminator();
     168     1528191 :   if (TI->getNumSuccessors() == 0)
     169             :     return;
     170             : 
     171             :   // If all of successor are post dominated then BB is also done.
     172      875680 :   if (llvm::all_of(successors(BB), [&](const BasicBlock *SuccBB) {
     173      876452 :         return PostDominatedByColdCall.count(SuccBB);
     174      876452 :       })) {
     175          67 :     PostDominatedByColdCall.insert(BB);
     176          67 :     return;
     177             :   }
     178             : 
     179             :   // If the terminator is an InvokeInst, check only the normal destination
     180             :   // block as the unwind edge of InvokeInst is also very unlikely taken.
     181             :   if (auto *II = dyn_cast<InvokeInst>(TI))
     182      399760 :     if (PostDominatedByColdCall.count(II->getNormalDest())) {
     183         465 :       PostDominatedByColdCall.insert(BB);
     184         465 :       return;
     185             :     }
     186             : 
     187             :   // Otherwise, if the block itself contains a cold function, add it to the
     188             :   // set of blocks post-dominated by a cold call.
     189     9908919 :   for (auto &I : *BB)
     190             :     if (const CallInst *CI = dyn_cast<CallInst>(&I))
     191     1153369 :       if (CI->hasFnAttr(Attribute::Cold)) {
     192         321 :         PostDominatedByColdCall.insert(BB);
     193             :         return;
     194             :       }
     195             : }
     196             : 
     197             : /// \brief Calculate edge weights for successors lead to unreachable.
     198             : ///
     199             : /// Predict that a successor which leads necessarily to an
     200             : /// unreachable-terminated block as extremely unlikely.
     201      437234 : bool BranchProbabilityInfo::calcUnreachableHeuristics(const BasicBlock *BB) {
     202      437234 :   const TerminatorInst *TI = BB->getTerminator();
     203             :   assert(TI->getNumSuccessors() > 1 && "expected more than one successor!");
     204             : 
     205             :   // Return false here so that edge weights for InvokeInst could be decided
     206             :   // in calcInvokeHeuristics().
     207      437234 :   if (isa<InvokeInst>(TI))
     208             :     return false;
     209             : 
     210             :   SmallVector<unsigned, 4> UnreachableEdges;
     211             :   SmallVector<unsigned, 4> ReachableEdges;
     212             : 
     213      964968 :   for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
     214      980532 :     if (PostDominatedByUnreachable.count(*I))
     215       23537 :       UnreachableEdges.push_back(I.getSuccessorIndex());
     216             :     else
     217      466729 :       ReachableEdges.push_back(I.getSuccessorIndex());
     218             : 
     219             :   // Skip probabilities if all were reachable.
     220      237351 :   if (UnreachableEdges.empty())
     221             :     return false;
     222             : 
     223       12924 :   if (ReachableEdges.empty()) {
     224        5921 :     BranchProbability Prob(1, UnreachableEdges.size());
     225       29959 :     for (unsigned SuccIdx : UnreachableEdges)
     226       12019 :       setEdgeProbability(BB, SuccIdx, Prob);
     227             :     return true;
     228             :   }
     229             : 
     230        7003 :   auto UnreachableProb = UR_TAKEN_PROB;
     231             :   auto ReachableProb =
     232        7003 :       (BranchProbability::getOne() - UR_TAKEN_PROB * UnreachableEdges.size()) /
     233       14006 :       ReachableEdges.size();
     234             : 
     235       30039 :   for (unsigned SuccIdx : UnreachableEdges)
     236       11518 :     setEdgeProbability(BB, SuccIdx, UnreachableProb);
     237       23263 :   for (unsigned SuccIdx : ReachableEdges)
     238        8130 :     setEdgeProbability(BB, SuccIdx, ReachableProb);
     239             : 
     240             :   return true;
     241             : }
     242             : 
     243             : // Propagate existing explicit probabilities from either profile data or
     244             : // 'expect' intrinsic processing. Examine metadata against unreachable
     245             : // heuristic. The probability of the edge coming to unreachable block is
     246             : // set to min of metadata and unreachable heuristic.
     247      456630 : bool BranchProbabilityInfo::calcMetadataWeights(const BasicBlock *BB) {
     248      456630 :   const TerminatorInst *TI = BB->getTerminator();
     249             :   assert(TI->getNumSuccessors() > 1 && "expected more than one successor!");
     250      456630 :   if (!(isa<BranchInst>(TI) || isa<SwitchInst>(TI) || isa<IndirectBrInst>(TI)))
     251             :     return false;
     252             : 
     253      256655 :   MDNode *WeightsNode = TI->getMetadata(LLVMContext::MD_prof);
     254      213693 :   if (!WeightsNode)
     255             :     return false;
     256             : 
     257             :   // Check that the number of successors is manageable.
     258             :   assert(TI->getNumSuccessors() < UINT32_MAX && "Too many successors");
     259             : 
     260             :   // Ensure there are weights for all of the successors. Note that the first
     261             :   // operand to the metadata node is a name, not a weight.
     262       19404 :   if (WeightsNode->getNumOperands() != TI->getNumSuccessors() + 1)
     263             :     return false;
     264             : 
     265             :   // Build up the final weights that will be used in a temporary buffer.
     266             :   // Compute the sum of all weights to later decide whether they need to
     267             :   // be scaled to fit in 32 bits.
     268             :   uint64_t WeightSum = 0;
     269             :   SmallVector<uint32_t, 2> Weights;
     270             :   SmallVector<unsigned, 2> UnreachableIdxs;
     271             :   SmallVector<unsigned, 2> ReachableIdxs;
     272       19396 :   Weights.reserve(TI->getNumSuccessors());
     273       58634 :   for (unsigned i = 1, e = WeightsNode->getNumOperands(); i != e; ++i) {
     274             :     ConstantInt *Weight =
     275             :         mdconst::dyn_extract<ConstantInt>(WeightsNode->getOperand(i));
     276             :     if (!Weight)
     277             :       return false;
     278             :     assert(Weight->getValue().getActiveBits() <= 32 &&
     279             :            "Too many bits for uint32_t");
     280       39238 :     Weights.push_back(Weight->getZExtValue());
     281       39238 :     WeightSum += Weights.back();
     282       39238 :     if (PostDominatedByUnreachable.count(TI->getSuccessor(i - 1)))
     283       15354 :       UnreachableIdxs.push_back(i - 1);
     284             :     else
     285       23884 :       ReachableIdxs.push_back(i - 1);
     286             :   }
     287             :   assert(Weights.size() == TI->getNumSuccessors() && "Checked above");
     288             : 
     289             :   // If the sum of weights does not fit in 32 bits, scale every weight down
     290             :   // accordingly.
     291             :   uint64_t ScalingFactor =
     292       19396 :       (WeightSum > UINT32_MAX) ? WeightSum / UINT32_MAX + 1 : 1;
     293             : 
     294             :   if (ScalingFactor > 1) {
     295             :     WeightSum = 0;
     296          84 :     for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
     297         130 :       Weights[i] /= ScalingFactor;
     298          65 :       WeightSum += Weights[i];
     299             :     }
     300             :   }
     301             :   assert(WeightSum <= UINT32_MAX &&
     302             :          "Expected weights to scale down to 32 bits");
     303             : 
     304       38789 :   if (WeightSum == 0 || ReachableIdxs.size() == 0) {
     305          84 :     for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
     306         118 :       Weights[i] = 1;
     307          25 :     WeightSum = TI->getNumSuccessors();
     308             :   }
     309             : 
     310             :   // Set the probability.
     311             :   SmallVector<BranchProbability, 2> BP;
     312       58634 :   for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
     313       78476 :     BP.push_back({ Weights[i], static_cast<uint32_t>(WeightSum) });
     314             : 
     315             :   // Examine the metadata against unreachable heuristic.
     316             :   // If the unreachable heuristic is more strong then we use it for this edge.
     317       34665 :   if (UnreachableIdxs.size() > 0 && ReachableIdxs.size() > 0) {
     318             :     auto ToDistribute = BranchProbability::getZero();
     319       15247 :     auto UnreachableProb = UR_TAKEN_PROB;
     320       45849 :     for (auto i : UnreachableIdxs)
     321       30602 :       if (UnreachableProb < BP[i]) {
     322             :         ToDistribute += BP[i] - UnreachableProb;
     323       15292 :         BP[i] = UnreachableProb;
     324             :       }
     325             : 
     326             :     // If we modified the probability of some edges then we must distribute
     327             :     // the difference between reachable blocks.
     328       15247 :     if (ToDistribute > BranchProbability::getZero()) {
     329       15241 :       BranchProbability PerEdge = ToDistribute / ReachableIdxs.size();
     330       45765 :       for (auto i : ReachableIdxs)
     331       15262 :         BP[i] += PerEdge;
     332             :     }
     333             :   }
     334             : 
     335       58634 :   for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
     336       78476 :     setEdgeProbability(BB, i, BP[i]);
     337             : 
     338             :   return true;
     339             : }
     340             : 
     341             : /// \brief Calculate edge weights for edges leading to cold blocks.
     342             : ///
     343             : /// A cold block is one post-dominated by  a block with a call to a
     344             : /// cold function.  Those edges are unlikely to be taken, so we give
     345             : /// them relatively low weight.
     346             : ///
     347             : /// Return true if we could compute the weights for cold edges.
     348             : /// Return false, otherwise.
     349      424310 : bool BranchProbabilityInfo::calcColdCallHeuristics(const BasicBlock *BB) {
     350      424310 :   const TerminatorInst *TI = BB->getTerminator();
     351             :   assert(TI->getNumSuccessors() > 1 && "expected more than one successor!");
     352             : 
     353             :   // Return false here so that edge weights for InvokeInst could be decided
     354             :   // in calcInvokeHeuristics().
     355      424310 :   if (isa<InvokeInst>(TI))
     356             :     return false;
     357             : 
     358             :   // Determine which successors are post-dominated by a cold block.
     359             :   SmallVector<unsigned, 4> ColdEdges;
     360             :   SmallVector<unsigned, 4> NormalEdges;
     361      907453 :   for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
     362      917198 :     if (PostDominatedByColdCall.count(*I))
     363         322 :       ColdEdges.push_back(I.getSuccessorIndex());
     364             :     else
     365      458277 :       NormalEdges.push_back(I.getSuccessorIndex());
     366             : 
     367             :   // Skip probabilities if no cold edges.
     368      224427 :   if (ColdEdges.empty())
     369             :     return false;
     370             : 
     371         301 :   if (NormalEdges.empty()) {
     372          21 :     BranchProbability Prob(1, ColdEdges.size());
     373         105 :     for (unsigned SuccIdx : ColdEdges)
     374          42 :       setEdgeProbability(BB, SuccIdx, Prob);
     375             :     return true;
     376             :   }
     377             : 
     378             :   auto ColdProb = BranchProbability::getBranchProbability(
     379             :       CC_TAKEN_WEIGHT,
     380         280 :       (CC_TAKEN_WEIGHT + CC_NONTAKEN_WEIGHT) * uint64_t(ColdEdges.size()));
     381             :   auto NormalProb = BranchProbability::getBranchProbability(
     382             :       CC_NONTAKEN_WEIGHT,
     383         280 :       (CC_TAKEN_WEIGHT + CC_NONTAKEN_WEIGHT) * uint64_t(NormalEdges.size()));
     384             : 
     385         840 :   for (unsigned SuccIdx : ColdEdges)
     386         280 :     setEdgeProbability(BB, SuccIdx, ColdProb);
     387         840 :   for (unsigned SuccIdx : NormalEdges)
     388         280 :     setEdgeProbability(BB, SuccIdx, NormalProb);
     389             : 
     390             :   return true;
     391             : }
     392             : 
     393             : // Calculate Edge Weights using "Pointer Heuristics". Predict a comparsion
     394             : // between two pointer or pointer and NULL will fail.
     395      348392 : bool BranchProbabilityInfo::calcPointerHeuristics(const BasicBlock *BB) {
     396      348392 :   const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
     397      186775 :   if (!BI || !BI->isConditional())
     398             :     return false;
     399             : 
     400             :   Value *Cond = BI->getCondition();
     401             :   ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
     402      150789 :   if (!CI || !CI->isEquality())
     403             :     return false;
     404             : 
     405             :   Value *LHS = CI->getOperand(0);
     406             : 
     407      264996 :   if (!LHS->getType()->isPointerTy())
     408             :     return false;
     409             : 
     410             :   assert(CI->getOperand(1)->getType()->isPointerTy());
     411             : 
     412             :   // p != 0   ->   isProb = true
     413             :   // p == 0   ->   isProb = false
     414             :   // p != q   ->   isProb = true
     415             :   // p == q   ->   isProb = false;
     416             :   unsigned TakenIdx = 0, NonTakenIdx = 1;
     417             :   bool isProb = CI->getPredicate() == ICmpInst::ICMP_NE;
     418       69162 :   if (!isProb)
     419             :     std::swap(TakenIdx, NonTakenIdx);
     420             : 
     421             :   BranchProbability TakenProb(PH_TAKEN_WEIGHT,
     422       69162 :                               PH_TAKEN_WEIGHT + PH_NONTAKEN_WEIGHT);
     423       69162 :   setEdgeProbability(BB, TakenIdx, TakenProb);
     424       69162 :   setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
     425       69162 :   return true;
     426             : }
     427             : 
     428             : static int getSCCNum(const BasicBlock *BB,
     429             :                      const BranchProbabilityInfo::SccInfo &SccI) {
     430      311517 :   auto SccIt = SccI.SccNums.find(BB);
     431      311517 :   if (SccIt == SccI.SccNums.end())
     432             :     return -1;
     433        2211 :   return SccIt->second;
     434             : }
     435             : 
     436             : // Consider any block that is an entry point to the SCC as a header.
     437         833 : static bool isSCCHeader(const BasicBlock *BB, int SccNum,
     438             :                         BranchProbabilityInfo::SccInfo &SccI) {
     439             :   assert(getSCCNum(BB, SccI) == SccNum);
     440             : 
     441             :   // Lazily compute the set of headers for a given SCC and cache the results
     442             :   // in the SccHeaderMap.
     443        1666 :   if (SccI.SccHeaders.size() <= static_cast<unsigned>(SccNum))
     444          50 :     SccI.SccHeaders.resize(SccNum + 1);
     445         833 :   auto &HeaderMap = SccI.SccHeaders[SccNum];
     446             :   bool Inserted;
     447             :   BranchProbabilityInfo::SccHeaderMap::iterator HeaderMapIt;
     448        1666 :   std::tie(HeaderMapIt, Inserted) = HeaderMap.insert(std::make_pair(BB, false));
     449         833 :   if (Inserted) {
     450        1782 :     bool IsHeader = llvm::any_of(make_range(pred_begin(BB), pred_end(BB)),
     451        1006 :                                  [&](const BasicBlock *Pred) {
     452        2012 :                                    return getSCCNum(Pred, SccI) != SccNum;
     453        1600 :                                  });
     454         594 :     HeaderMapIt->second = IsHeader;
     455         594 :     return IsHeader;
     456             :   } else
     457         239 :     return HeaderMapIt->second;
     458             : }
     459             : 
     460             : // Calculate Edge Weights using "Loop Branch Heuristics". Predict backedges
     461             : // as taken, exiting edges as not-taken.
     462      424009 : bool BranchProbabilityInfo::calcLoopBranchHeuristics(const BasicBlock *BB,
     463             :                                                      const LoopInfo &LI,
     464             :                                                      SccInfo &SccI) {
     465             :   int SccNum;
     466             :   Loop *L = LI.getLoopFor(BB);
     467      114570 :   if (!L) {
     468             :     SccNum = getSCCNum(BB, SccI);
     469         443 :     if (SccNum < 0)
     470             :       return false;
     471             :   }
     472             : 
     473             :   SmallVector<unsigned, 8> BackEdges;
     474             :   SmallVector<unsigned, 8> ExitingEdges;
     475             :   SmallVector<unsigned, 8> InEdges; // Edges from header to the loop.
     476             : 
     477      462424 :   for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
     478             :     // Use LoopInfo if we have it, otherwise fall-back to SCC info to catch
     479             :     // irreducible loops.
     480      232398 :     if (L) {
     481      231326 :       if (!L->contains(*I))
     482       75477 :         ExitingEdges.push_back(I.getSuccessorIndex());
     483      155849 :       else if (L->getHeader() == *I)
     484       23701 :         BackEdges.push_back(I.getSuccessorIndex());
     485             :       else
     486      132148 :         InEdges.push_back(I.getSuccessorIndex());
     487             :     } else {
     488        1072 :       if (getSCCNum(*I, SccI) != SccNum)
     489         239 :         ExitingEdges.push_back(I.getSuccessorIndex());
     490         833 :       else if (isSCCHeader(*I, SccNum, SccI))
     491          87 :         BackEdges.push_back(I.getSuccessorIndex());
     492             :       else
     493         746 :         InEdges.push_back(I.getSuccessorIndex());
     494             :     }
     495             :   }
     496             : 
     497      115013 :   if (BackEdges.empty() && ExitingEdges.empty())
     498             :     return false;
     499             : 
     500             :   // Collect the sum of probabilities of back-edges/in-edges/exiting-edges, and
     501             :   // normalize them so that they sum up to one.
     502             :   BranchProbability Probs[] = {BranchProbability::getZero(),
     503             :                                BranchProbability::getZero(),
     504             :                                BranchProbability::getZero()};
     505      151234 :   unsigned Denom = (BackEdges.empty() ? 0 : LBH_TAKEN_WEIGHT) +
     506       75617 :                    (InEdges.empty() ? 0 : LBH_TAKEN_WEIGHT) +
     507       75617 :                    (ExitingEdges.empty() ? 0 : LBH_NONTAKEN_WEIGHT);
     508       75617 :   if (!BackEdges.empty())
     509       23723 :     Probs[0] = BranchProbability(LBH_TAKEN_WEIGHT, Denom);
     510       75617 :   if (!InEdges.empty())
     511       52219 :     Probs[1] = BranchProbability(LBH_TAKEN_WEIGHT, Denom);
     512       75617 :   if (!ExitingEdges.empty())
     513       75288 :     Probs[2] = BranchProbability(LBH_NONTAKEN_WEIGHT, Denom);
     514             : 
     515       75617 :   if (uint32_t numBackEdges = BackEdges.size()) {
     516       23723 :     auto Prob = Probs[0] / numBackEdges;
     517       71299 :     for (unsigned SuccIdx : BackEdges)
     518       23788 :       setEdgeProbability(BB, SuccIdx, Prob);
     519             :   }
     520             : 
     521       75617 :   if (uint32_t numInEdges = InEdges.size()) {
     522       52219 :     auto Prob = Probs[1] / numInEdges;
     523      157435 :     for (unsigned SuccIdx : InEdges)
     524       52608 :       setEdgeProbability(BB, SuccIdx, Prob);
     525             :   }
     526             : 
     527       75617 :   if (uint32_t numExitingEdges = ExitingEdges.size()) {
     528       75288 :     auto Prob = Probs[2] / numExitingEdges;
     529      226720 :     for (unsigned SuccIdx : ExitingEdges)
     530       75716 :       setEdgeProbability(BB, SuccIdx, Prob);
     531             :   }
     532             : 
     533             :   return true;
     534             : }
     535             : 
     536      279230 : bool BranchProbabilityInfo::calcZeroHeuristics(const BasicBlock *BB,
     537             :                                                const TargetLibraryInfo *TLI) {
     538      279230 :   const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
     539      117613 :   if (!BI || !BI->isConditional())
     540             :     return false;
     541             : 
     542             :   Value *Cond = BI->getCondition();
     543             :   ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
     544             :   if (!CI)
     545             :     return false;
     546             : 
     547             :   Value *RHS = CI->getOperand(1);
     548             :   ConstantInt *CV = dyn_cast<ConstantInt>(RHS);
     549             :   if (!CV)
     550             :     return false;
     551             : 
     552             :   // If the LHS is the result of AND'ing a value with a single bit bitmask,
     553             :   // we don't have information about probabilities.
     554             :   if (Instruction *LHS = dyn_cast<Instruction>(CI->getOperand(0)))
     555       53480 :     if (LHS->getOpcode() == Instruction::And)
     556        4594 :       if (ConstantInt *AndRHS = dyn_cast<ConstantInt>(LHS->getOperand(1)))
     557        3266 :         if (AndRHS->getValue().isPowerOf2())
     558             :           return false;
     559             : 
     560             :   // Check if the LHS is the return value of a library function
     561       58877 :   LibFunc Func = NumLibFuncs;
     562       58877 :   if (TLI)
     563             :     if (CallInst *Call = dyn_cast<CallInst>(CI->getOperand(0)))
     564             :       if (Function *CalledFn = Call->getCalledFunction())
     565             :         TLI->getLibFunc(*CalledFn, Func);
     566             : 
     567             :   bool isProb;
     568       58877 :   if (Func == LibFunc_strcasecmp ||
     569       58600 :       Func == LibFunc_strcmp ||
     570       58597 :       Func == LibFunc_strncasecmp ||
     571       58486 :       Func == LibFunc_strncmp ||
     572             :       Func == LibFunc_memcmp) {
     573             :     // strcmp and similar functions return zero, negative, or positive, if the
     574             :     // first string is equal, less, or greater than the second. We consider it
     575             :     // likely that the strings are not equal, so a comparison with zero is
     576             :     // probably false, but also a comparison with any other number is also
     577             :     // probably false given that what exactly is returned for nonzero values is
     578             :     // not specified. Any kind of comparison other than equality we know
     579             :     // nothing about.
     580         521 :     switch (CI->getPredicate()) {
     581             :     case CmpInst::ICMP_EQ:
     582             :       isProb = false;
     583             :       break;
     584             :     case CmpInst::ICMP_NE:
     585             :       isProb = true;
     586             :       break;
     587             :     default:
     588             :       return false;
     589             :     }
     590       58356 :   } else if (CV->isZero()) {
     591       41155 :     switch (CI->getPredicate()) {
     592             :     case CmpInst::ICMP_EQ:
     593             :       // X == 0   ->  Unlikely
     594             :       isProb = false;
     595             :       break;
     596             :     case CmpInst::ICMP_NE:
     597             :       // X != 0   ->  Likely
     598             :       isProb = true;
     599             :       break;
     600             :     case CmpInst::ICMP_SLT:
     601             :       // X < 0   ->  Unlikely
     602             :       isProb = false;
     603             :       break;
     604             :     case CmpInst::ICMP_SGT:
     605             :       // X > 0   ->  Likely
     606             :       isProb = true;
     607             :       break;
     608             :     default:
     609             :       return false;
     610             :     }
     611       19003 :   } else if (CV->isOne() && CI->getPredicate() == CmpInst::ICMP_SLT) {
     612             :     // InstCombine canonicalizes X <= 0 into X < 1.
     613             :     // X <= 0   ->  Unlikely
     614             :     isProb = false;
     615       17054 :   } else if (CV->isMinusOne()) {
     616        1446 :     switch (CI->getPredicate()) {
     617             :     case CmpInst::ICMP_EQ:
     618             :       // X == -1  ->  Unlikely
     619             :       isProb = false;
     620             :       break;
     621             :     case CmpInst::ICMP_NE:
     622             :       // X != -1  ->  Likely
     623             :       isProb = true;
     624             :       break;
     625             :     case CmpInst::ICMP_SGT:
     626             :       // InstCombine canonicalizes X >= 0 into X > -1.
     627             :       // X >= 0   ->  Likely
     628             :       isProb = true;
     629             :       break;
     630             :     default:
     631             :       return false;
     632             :     }
     633             :   } else {
     634             :     return false;
     635             :   }
     636             : 
     637             :   unsigned TakenIdx = 0, NonTakenIdx = 1;
     638             : 
     639             :   if (!isProb)
     640             :     std::swap(TakenIdx, NonTakenIdx);
     641             : 
     642             :   BranchProbability TakenProb(ZH_TAKEN_WEIGHT,
     643       43068 :                               ZH_TAKEN_WEIGHT + ZH_NONTAKEN_WEIGHT);
     644       43068 :   setEdgeProbability(BB, TakenIdx, TakenProb);
     645       43068 :   setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
     646       43068 :   return true;
     647             : }
     648             : 
     649      236162 : bool BranchProbabilityInfo::calcFloatingPointHeuristics(const BasicBlock *BB) {
     650      236162 :   const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
     651       74545 :   if (!BI || !BI->isConditional())
     652             :     return false;
     653             : 
     654             :   Value *Cond = BI->getCondition();
     655             :   FCmpInst *FCmp = dyn_cast<FCmpInst>(Cond);
     656             :   if (!FCmp)
     657             :     return false;
     658             : 
     659             :   bool isProb;
     660             :   if (FCmp->isEquality()) {
     661             :     // f1 == f2 -> Unlikely
     662             :     // f1 != f2 -> Likely
     663             :     isProb = !FCmp->isTrueWhenEqual();
     664        1278 :   } else if (FCmp->getPredicate() == FCmpInst::FCMP_ORD) {
     665             :     // !isnan -> Likely
     666             :     isProb = true;
     667        1173 :   } else if (FCmp->getPredicate() == FCmpInst::FCMP_UNO) {
     668             :     // isnan -> Unlikely
     669             :     isProb = false;
     670             :   } else {
     671             :     return false;
     672             :   }
     673             : 
     674             :   unsigned TakenIdx = 0, NonTakenIdx = 1;
     675             : 
     676         505 :   if (!isProb)
     677             :     std::swap(TakenIdx, NonTakenIdx);
     678             : 
     679             :   BranchProbability TakenProb(FPH_TAKEN_WEIGHT,
     680         645 :                               FPH_TAKEN_WEIGHT + FPH_NONTAKEN_WEIGHT);
     681         645 :   setEdgeProbability(BB, TakenIdx, TakenProb);
     682         645 :   setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
     683         645 :   return true;
     684             : }
     685             : 
     686      235517 : bool BranchProbabilityInfo::calcInvokeHeuristics(const BasicBlock *BB) {
     687      235517 :   const InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator());
     688             :   if (!II)
     689             :     return false;
     690             : 
     691             :   BranchProbability TakenProb(IH_TAKEN_WEIGHT,
     692      158698 :                               IH_TAKEN_WEIGHT + IH_NONTAKEN_WEIGHT);
     693      158698 :   setEdgeProbability(BB, 0 /*Index for Normal*/, TakenProb);
     694      158698 :   setEdgeProbability(BB, 1 /*Index for Unwind*/, TakenProb.getCompl());
     695      158698 :   return true;
     696             : }
     697             : 
     698      400440 : void BranchProbabilityInfo::releaseMemory() {
     699      400440 :   Probs.clear();
     700      400440 : }
     701             : 
     702         157 : void BranchProbabilityInfo::print(raw_ostream &OS) const {
     703         157 :   OS << "---- Branch Probabilities ----\n";
     704             :   // We print the probabilities from the last function the analysis ran over,
     705             :   // or the function it is currently running over.
     706             :   assert(LastF && "Cannot print prior to running over a function");
     707        1084 :   for (const auto &BI : *LastF) {
     708        2404 :     for (succ_const_iterator SI = succ_begin(&BI), SE = succ_end(&BI); SI != SE;
     709             :          ++SI) {
     710         864 :       printEdgeProbability(OS << "  ", &BI, *SI);
     711             :     }
     712             :   }
     713         157 : }
     714             : 
     715         866 : bool BranchProbabilityInfo::
     716             : isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const {
     717             :   // Hot probability is at least 4/5 = 80%
     718             :   // FIXME: Compare against a static "hot" BranchProbability.
     719        1732 :   return getEdgeProbability(Src, Dst) > BranchProbability(4, 5);
     720             : }
     721             : 
     722             : const BasicBlock *
     723           0 : BranchProbabilityInfo::getHotSucc(const BasicBlock *BB) const {
     724             :   auto MaxProb = BranchProbability::getZero();
     725             :   const BasicBlock *MaxSucc = nullptr;
     726             : 
     727           0 :   for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
     728             :     const BasicBlock *Succ = *I;
     729           0 :     auto Prob = getEdgeProbability(BB, Succ);
     730           0 :     if (Prob > MaxProb) {
     731             :       MaxProb = Prob;
     732             :       MaxSucc = Succ;
     733             :     }
     734             :   }
     735             : 
     736             :   // Hot probability is at least 4/5 = 80%
     737           0 :   if (MaxProb > BranchProbability(4, 5))
     738           0 :     return MaxSucc;
     739             : 
     740             :   return nullptr;
     741             : }
     742             : 
     743             : /// Get the raw edge probability for the edge. If can't find it, return a
     744             : /// default probability 1/N where N is the number of successors. Here an edge is
     745             : /// specified using PredBlock and an
     746             : /// index to the successors.
     747             : BranchProbability
     748     1147639 : BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
     749             :                                           unsigned IndexInSuccessors) const {
     750     1147639 :   auto I = Probs.find(std::make_pair(Src, IndexInSuccessors));
     751             : 
     752     1147639 :   if (I != Probs.end())
     753      648332 :     return I->second;
     754             : 
     755             :   return {1,
     756      499307 :           static_cast<uint32_t>(std::distance(succ_begin(Src), succ_end(Src)))};
     757             : }
     758             : 
     759             : BranchProbability
     760     1144331 : BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
     761             :                                           succ_const_iterator Dst) const {
     762     1144331 :   return getEdgeProbability(Src, Dst.getSuccessorIndex());
     763             : }
     764             : 
     765             : /// Get the raw edge probability calculated for the block pair. This returns the
     766             : /// sum of all raw edge probabilities from Src to Dst.
     767             : BranchProbability
     768      138262 : BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
     769             :                                           const BasicBlock *Dst) const {
     770             :   auto Prob = BranchProbability::getZero();
     771             :   bool FoundProb = false;
     772      564881 :   for (succ_const_iterator I = succ_begin(Src), E = succ_end(Src); I != E; ++I)
     773      288357 :     if (*I == Dst) {
     774      142545 :       auto MapI = Probs.find(std::make_pair(Src, I.getSuccessorIndex()));
     775      142545 :       if (MapI != Probs.end()) {
     776             :         FoundProb = true;
     777             :         Prob += MapI->second;
     778             :       }
     779             :     }
     780      138262 :   uint32_t succ_num = std::distance(succ_begin(Src), succ_end(Src));
     781      138262 :   return FoundProb ? Prob : BranchProbability(1, succ_num);
     782             : }
     783             : 
     784             : /// Set the edge probability for a given edge specified by PredBlock and an
     785             : /// index to the successors.
     786      766781 : void BranchProbabilityInfo::setEdgeProbability(const BasicBlock *Src,
     787             :                                                unsigned IndexInSuccessors,
     788             :                                                BranchProbability Prob) {
     789     1533562 :   Probs[std::make_pair(Src, IndexInSuccessors)] = Prob;
     790      766781 :   Handles.insert(BasicBlockCallbackVH(Src, this));
     791             :   DEBUG(dbgs() << "set edge " << Src->getName() << " -> " << IndexInSuccessors
     792             :                << " successor probability to " << Prob << "\n");
     793      766781 : }
     794             : 
     795             : raw_ostream &
     796         864 : BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS,
     797             :                                             const BasicBlock *Src,
     798             :                                             const BasicBlock *Dst) const {
     799         864 :   const BranchProbability Prob = getEdgeProbability(Src, Dst);
     800         864 :   OS << "edge " << Src->getName() << " -> " << Dst->getName()
     801         864 :      << " probability is " << Prob
     802         864 :      << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n");
     803             : 
     804         864 :   return OS;
     805             : }
     806             : 
     807       12739 : void BranchProbabilityInfo::eraseBlock(const BasicBlock *BB) {
     808       76318 :   for (auto I = Probs.begin(), E = Probs.end(); I != E; ++I) {
     809       25420 :     auto Key = I->first;
     810       25420 :     if (Key.first == BB)
     811        5476 :       Probs.erase(Key);
     812             :   }
     813       12739 : }
     814             : 
     815      562099 : void BranchProbabilityInfo::calculate(const Function &F, const LoopInfo &LI,
     816             :                                       const TargetLibraryInfo *TLI) {
     817             :   DEBUG(dbgs() << "---- Branch Probability Info : " << F.getName()
     818             :                << " ----\n\n");
     819      562099 :   LastF = &F; // Store the last function we ran on for printing.
     820             :   assert(PostDominatedByUnreachable.empty());
     821             :   assert(PostDominatedByColdCall.empty());
     822             : 
     823             :   // Record SCC numbers of blocks in the CFG to identify irreducible loops.
     824             :   // FIXME: We could only calculate this if the CFG is known to be irreducible
     825             :   // (perhaps cache this info in LoopInfo if we can easily calculate it there?).
     826             :   int SccNum = 0;
     827             :   SccInfo SccI;
     828     3327291 :   for (scc_iterator<const Function *> It = scc_begin(&F); !It.isAtEnd();
     829             :        ++It, ++SccNum) {
     830             :     // Ignore single-block SCCs since they either aren't loops or LoopInfo will
     831             :     // catch them.
     832             :     const std::vector<const BasicBlock *> &Scc = *It;
     833     1382596 :     if (Scc.size() == 1)
     834     1368306 :       continue;
     835             : 
     836             :     DEBUG(dbgs() << "BPI: SCC " << SccNum << ":");
     837      174175 :     for (auto *BB : Scc) {
     838             :       DEBUG(dbgs() << " " << BB->getName());
     839      159885 :       SccI.SccNums[BB] = SccNum;
     840             :     }
     841             :     DEBUG(dbgs() << "\n");
     842             :   }
     843             : 
     844             :   // Walk the basic blocks in post-order so that we can build up state about
     845             :   // the successors of a block iteratively.
     846     4742679 :   for (auto BB : post_order(&F.getEntryBlock())) {
     847             :     DEBUG(dbgs() << "Computing probabilities for " << BB->getName() << "\n");
     848     1528191 :     updatePostDominatedByUnreachable(BB);
     849     1528191 :     updatePostDominatedByColdCall(BB);
     850             :     // If there is no at least two successors, no sense to set probability.
     851     1528191 :     if (BB->getTerminator()->getNumSuccessors() < 2)
     852     1071561 :       continue;
     853      456630 :     if (calcMetadataWeights(BB))
     854       19396 :       continue;
     855      437234 :     if (calcUnreachableHeuristics(BB))
     856       12924 :       continue;
     857      424310 :     if (calcColdCallHeuristics(BB))
     858         301 :       continue;
     859      424009 :     if (calcLoopBranchHeuristics(BB, LI, SccI))
     860       75617 :       continue;
     861      348392 :     if (calcPointerHeuristics(BB))
     862       69162 :       continue;
     863      279230 :     if (calcZeroHeuristics(BB, TLI))
     864       43068 :       continue;
     865      236162 :     if (calcFloatingPointHeuristics(BB))
     866         645 :       continue;
     867      235517 :     calcInvokeHeuristics(BB);
     868             :   }
     869             : 
     870      562099 :   PostDominatedByUnreachable.clear();
     871      562099 :   PostDominatedByColdCall.clear();
     872             : 
     873      562099 :   if (PrintBranchProb &&
     874             :       (PrintBranchProbFuncName.empty() ||
     875      562099 :        F.getName().equals(PrintBranchProbFuncName))) {
     876           0 :     print(dbgs());
     877             :   }
     878      562099 : }
     879             : 
     880       44041 : void BranchProbabilityInfoWrapperPass::getAnalysisUsage(
     881             :     AnalysisUsage &AU) const {
     882             :   AU.addRequired<LoopInfoWrapperPass>();
     883             :   AU.addRequired<TargetLibraryInfoWrapperPass>();
     884             :   AU.setPreservesAll();
     885       44041 : }
     886             : 
     887      400513 : bool BranchProbabilityInfoWrapperPass::runOnFunction(Function &F) {
     888      400513 :   const LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
     889      400513 :   const TargetLibraryInfo &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
     890      400513 :   BPI.calculate(F, LI, &TLI);
     891      400513 :   return false;
     892             : }
     893             : 
     894      400440 : void BranchProbabilityInfoWrapperPass::releaseMemory() { BPI.releaseMemory(); }
     895             : 
     896          76 : void BranchProbabilityInfoWrapperPass::print(raw_ostream &OS,
     897             :                                              const Module *) const {
     898          76 :   BPI.print(OS);
     899          76 : }
     900             : 
     901             : AnalysisKey BranchProbabilityAnalysis::Key;
     902             : BranchProbabilityInfo
     903         875 : BranchProbabilityAnalysis::run(Function &F, FunctionAnalysisManager &AM) {
     904         875 :   BranchProbabilityInfo BPI;
     905         875 :   BPI.calculate(F, AM.getResult<LoopAnalysis>(F), &AM.getResult<TargetLibraryAnalysis>(F));
     906         875 :   return BPI;
     907             : }
     908             : 
     909             : PreservedAnalyses
     910          49 : BranchProbabilityPrinterPass::run(Function &F, FunctionAnalysisManager &AM) {
     911          49 :   OS << "Printing analysis results of BPI for function "
     912          49 :      << "'" << F.getName() << "':"
     913          49 :      << "\n";
     914          49 :   AM.getResult<BranchProbabilityAnalysis>(F).print(OS);
     915          49 :   return PreservedAnalyses::all();
     916      291513 : }

Generated by: LCOV version 1.13