LCOV - code coverage report
Current view: top level - lib/Analysis - BranchProbabilityInfo.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 321 336 95.5 %
Date: 2017-09-14 15:23:50 Functions: 29 31 93.5 %
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/STLExtras.h"
      17             : #include "llvm/ADT/SmallVector.h"
      18             : #include "llvm/Analysis/LoopInfo.h"
      19             : #include "llvm/Analysis/TargetLibraryInfo.h"
      20             : #include "llvm/IR/Attributes.h"
      21             : #include "llvm/IR/BasicBlock.h"
      22             : #include "llvm/IR/CFG.h"
      23             : #include "llvm/IR/Constants.h"
      24             : #include "llvm/IR/Function.h"
      25             : #include "llvm/IR/InstrTypes.h"
      26             : #include "llvm/IR/Instruction.h"
      27             : #include "llvm/IR/Instructions.h"
      28             : #include "llvm/IR/LLVMContext.h"
      29             : #include "llvm/IR/Metadata.h"
      30             : #include "llvm/IR/PassManager.h"
      31             : #include "llvm/IR/Type.h"
      32             : #include "llvm/IR/Value.h"
      33             : #include "llvm/Pass.h"
      34             : #include "llvm/Support/BranchProbability.h"
      35             : #include "llvm/Support/Casting.h"
      36             : #include "llvm/Support/Debug.h"
      37             : #include "llvm/Support/raw_ostream.h"
      38             : #include <cassert>
      39             : #include <cstdint>
      40             : #include <iterator>
      41             : #include <utility>
      42             : 
      43             : using namespace llvm;
      44             : 
      45             : #define DEBUG_TYPE "branch-prob"
      46             : 
      47       72306 : static cl::opt<bool> PrintBranchProb(
      48      216918 :     "print-bpi", cl::init(false), cl::Hidden,
      49      289224 :     cl::desc("Print the branch probability info."));
      50             : 
      51       72306 : cl::opt<std::string> PrintBranchProbFuncName(
      52             :     "print-bpi-func-name", cl::Hidden,
      53      216918 :     cl::desc("The option to specify the name of the function "
      54       72306 :              "whose branch probability info is printed."));
      55             : 
      56       27083 : INITIALIZE_PASS_BEGIN(BranchProbabilityInfoWrapperPass, "branch-prob",
      57             :                       "Branch Probability Analysis", false, true)
      58       27083 : INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
      59       27083 : INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
      60      461002 : INITIALIZE_PASS_END(BranchProbabilityInfoWrapperPass, "branch-prob",
      61             :                     "Branch Probability Analysis", false, true)
      62             : 
      63             : char BranchProbabilityInfoWrapperPass::ID = 0;
      64             : 
      65             : // Weights are for internal use only. They are used by heuristics to help to
      66             : // estimate edges' probability. Example:
      67             : //
      68             : // Using "Loop Branch Heuristics" we predict weights of edges for the
      69             : // block BB2.
      70             : //         ...
      71             : //          |
      72             : //          V
      73             : //         BB1<-+
      74             : //          |   |
      75             : //          |   | (Weight = 124)
      76             : //          V   |
      77             : //         BB2--+
      78             : //          |
      79             : //          | (Weight = 4)
      80             : //          V
      81             : //         BB3
      82             : //
      83             : // Probability of the edge BB2->BB1 = 124 / (124 + 4) = 0.96875
      84             : // Probability of the edge BB2->BB3 = 4 / (124 + 4) = 0.03125
      85             : static const uint32_t LBH_TAKEN_WEIGHT = 124;
      86             : static const uint32_t LBH_NONTAKEN_WEIGHT = 4;
      87             : 
      88             : /// \brief Unreachable-terminating branch taken probability.
      89             : ///
      90             : /// This is the probability for a branch being taken to a block that terminates
      91             : /// (eventually) in unreachable. These are predicted as unlikely as possible.
      92             : /// All reachable probability will equally share the remaining part.
      93       72306 : static const BranchProbability UR_TAKEN_PROB = BranchProbability::getRaw(1);
      94             : 
      95             : /// \brief Weight for a branch taken going into a cold block.
      96             : ///
      97             : /// This is the weight for a branch taken toward a block marked
      98             : /// cold.  A block is marked cold if it's postdominated by a
      99             : /// block containing a call to a cold function.  Cold functions
     100             : /// are those marked with attribute 'cold'.
     101             : static const uint32_t CC_TAKEN_WEIGHT = 4;
     102             : 
     103             : /// \brief Weight for a branch not-taken into a cold block.
     104             : ///
     105             : /// This is the weight for a branch not taken toward a block marked
     106             : /// cold.
     107             : static const uint32_t CC_NONTAKEN_WEIGHT = 64;
     108             : 
     109             : static const uint32_t PH_TAKEN_WEIGHT = 20;
     110             : static const uint32_t PH_NONTAKEN_WEIGHT = 12;
     111             : 
     112             : static const uint32_t ZH_TAKEN_WEIGHT = 20;
     113             : static const uint32_t ZH_NONTAKEN_WEIGHT = 12;
     114             : 
     115             : static const uint32_t FPH_TAKEN_WEIGHT = 20;
     116             : static const uint32_t FPH_NONTAKEN_WEIGHT = 12;
     117             : 
     118             : /// \brief Invoke-terminating normal branch taken weight
     119             : ///
     120             : /// This is the weight for branching to the normal destination of an invoke
     121             : /// instruction. We expect this to happen most of the time. Set the weight to an
     122             : /// absurdly high value so that nested loops subsume it.
     123             : static const uint32_t IH_TAKEN_WEIGHT = 1024 * 1024 - 1;
     124             : 
     125             : /// \brief Invoke-terminating normal branch not-taken weight.
     126             : ///
     127             : /// This is the weight for branching to the unwind destination of an invoke
     128             : /// instruction. This is essentially never taken.
     129             : static const uint32_t IH_NONTAKEN_WEIGHT = 1;
     130             : 
     131             : /// \brief Add \p BB to PostDominatedByUnreachable set if applicable.
     132             : void
     133     1112972 : BranchProbabilityInfo::updatePostDominatedByUnreachable(const BasicBlock *BB) {
     134     1112972 :   const TerminatorInst *TI = BB->getTerminator();
     135     1112972 :   if (TI->getNumSuccessors() == 0) {
     136     1219005 :     if (isa<UnreachableInst>(TI) ||
     137             :         // If this block is terminated by a call to
     138             :         // @llvm.experimental.deoptimize then treat it like an unreachable since
     139             :         // the @llvm.experimental.deoptimize call is expected to practically
     140             :         // never execute.
     141      368139 :         BB->getTerminatingDeoptimizeCall())
     142       57296 :       PostDominatedByUnreachable.insert(BB);
     143             :     return;
     144             :   }
     145             : 
     146             :   // If the terminator is an InvokeInst, check only the normal destination block
     147             :   // as the unwind edge of InvokeInst is also very unlikely taken.
     148      847231 :   if (auto *II = dyn_cast<InvokeInst>(TI)) {
     149      319384 :     if (PostDominatedByUnreachable.count(II->getNormalDest()))
     150        6321 :       PostDominatedByUnreachable.insert(BB);
     151             :     return;
     152             :   }
     153             : 
     154     1649230 :   for (auto *I : successors(BB))
     155             :     // If any of successor is not post dominated then BB is also not.
     156      543456 :     if (!PostDominatedByUnreachable.count(I))
     157             :       return;
     158             : 
     159       34471 :   PostDominatedByUnreachable.insert(BB);
     160             : }
     161             : 
     162             : /// \brief Add \p BB to PostDominatedByColdCall set if applicable.
     163             : void
     164     1112972 : BranchProbabilityInfo::updatePostDominatedByColdCall(const BasicBlock *BB) {
     165             :   assert(!PostDominatedByColdCall.count(BB));
     166     1112972 :   const TerminatorInst *TI = BB->getTerminator();
     167     1112972 :   if (TI->getNumSuccessors() == 0)
     168             :     return;
     169             : 
     170             :   // If all of successor are post dominated then BB is also done.
     171      687539 :   if (llvm::all_of(successors(BB), [&](const BasicBlock *SuccBB) {
     172      688249 :         return PostDominatedByColdCall.count(SuccBB);
     173      688249 :       })) {
     174          59 :     PostDominatedByColdCall.insert(BB);
     175          59 :     return;
     176             :   }
     177             : 
     178             :   // If the terminator is an InvokeInst, check only the normal destination
     179             :   // block as the unwind edge of InvokeInst is also very unlikely taken.
     180      159689 :   if (auto *II = dyn_cast<InvokeInst>(TI))
     181      319378 :     if (PostDominatedByColdCall.count(II->getNormalDest())) {
     182         423 :       PostDominatedByColdCall.insert(BB);
     183         423 :       return;
     184             :     }
     185             : 
     186             :   // Otherwise, if the block itself contains a cold function, add it to the
     187             :   // set of blocks post-dominated by a cold call.
     188     9348842 :   for (auto &I : *BB)
     189      884007 :     if (const CallInst *CI = dyn_cast<CallInst>(&I))
     190      884007 :       if (CI->hasFnAttr(Attribute::Cold)) {
     191         295 :         PostDominatedByColdCall.insert(BB);
     192         295 :         return;
     193             :       }
     194             : }
     195             : 
     196             : /// \brief Calculate edge weights for successors lead to unreachable.
     197             : ///
     198             : /// Predict that a successor which leads necessarily to an
     199             : /// unreachable-terminated block as extremely unlikely.
     200      344513 : bool BranchProbabilityInfo::calcUnreachableHeuristics(const BasicBlock *BB) {
     201      344513 :   const TerminatorInst *TI = BB->getTerminator();
     202             :   assert(TI->getNumSuccessors() > 1 && "expected more than one successor!");
     203             : 
     204             :   // Return false here so that edge weights for InvokeInst could be decided
     205             :   // in calcInvokeHeuristics().
     206      689026 :   if (isa<InvokeInst>(TI))
     207             :     return false;
     208             : 
     209      184821 :   SmallVector<unsigned, 4> UnreachableEdges;
     210      369642 :   SmallVector<unsigned, 4> ReachableEdges;
     211             : 
     212      751784 :   for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
     213      764284 :     if (PostDominatedByUnreachable.count(*I))
     214       20940 :       UnreachableEdges.push_back(I.getSuccessorIndex());
     215             :     else
     216      361202 :       ReachableEdges.push_back(I.getSuccessorIndex());
     217             : 
     218             :   // Skip probabilities if all were reachable.
     219      184821 :   if (UnreachableEdges.empty())
     220             :     return false;
     221             : 
     222       10973 :   if (ReachableEdges.empty()) {
     223        5459 :     BranchProbability Prob(1, UnreachableEdges.size());
     224       27426 :     for (unsigned SuccIdx : UnreachableEdges)
     225       11049 :       setEdgeProbability(BB, SuccIdx, Prob);
     226             :     return true;
     227             :   }
     228             : 
     229        5514 :   auto UnreachableProb = UR_TAKEN_PROB;
     230             :   auto ReachableProb =
     231       22056 :       (BranchProbability::getOne() - UR_TAKEN_PROB * UnreachableEdges.size()) /
     232       11028 :       ReachableEdges.size();
     233             : 
     234       15405 :   for (unsigned SuccIdx : UnreachableEdges)
     235        9891 :     setEdgeProbability(BB, SuccIdx, UnreachableProb);
     236       22856 :   for (unsigned SuccIdx : ReachableEdges)
     237        6314 :     setEdgeProbability(BB, SuccIdx, ReachableProb);
     238             : 
     239             :   return true;
     240             : }
     241             : 
     242             : // Propagate existing explicit probabilities from either profile data or
     243             : // 'expect' intrinsic processing. Examine metadata against unreachable
     244             : // heuristic. The probability of the edge coming to unreachable block is
     245             : // set to min of metadata and unreachable heuristic.
     246      359998 : bool BranchProbabilityInfo::calcMetadataWeights(const BasicBlock *BB) {
     247      359998 :   const TerminatorInst *TI = BB->getTerminator();
     248             :   assert(TI->getNumSuccessors() > 1 && "expected more than one successor!");
     249     1042419 :   if (!(isa<BranchInst>(TI) || isa<SwitchInst>(TI) || isa<IndirectBrInst>(TI)))
     250             :     return false;
     251             : 
     252      371908 :   MDNode *WeightsNode = TI->getMetadata(LLVMContext::MD_prof);
     253      171664 :   if (!WeightsNode)
     254             :     return false;
     255             : 
     256             :   // Check that the number of successors is manageable.
     257             :   assert(TI->getNumSuccessors() < UINT32_MAX && "Too many successors");
     258             : 
     259             :   // Ensure there are weights for all of the successors. Note that the first
     260             :   // operand to the metadata node is a name, not a weight.
     261       15490 :   if (WeightsNode->getNumOperands() != TI->getNumSuccessors() + 1)
     262             :     return false;
     263             : 
     264             :   // Build up the final weights that will be used in a temporary buffer.
     265             :   // Compute the sum of all weights to later decide whether they need to
     266             :   // be scaled to fit in 32 bits.
     267       15485 :   uint64_t WeightSum = 0;
     268       15485 :   SmallVector<uint32_t, 2> Weights;
     269       30970 :   SmallVector<unsigned, 2> UnreachableIdxs;
     270       30970 :   SmallVector<unsigned, 2> ReachableIdxs;
     271       15485 :   Weights.reserve(TI->getNumSuccessors());
     272       46764 :   for (unsigned i = 1, e = WeightsNode->getNumOperands(); i != e; ++i) {
     273             :     ConstantInt *Weight =
     274       62558 :         mdconst::dyn_extract<ConstantInt>(WeightsNode->getOperand(i));
     275             :     if (!Weight)
     276             :       return false;
     277             :     assert(Weight->getValue().getActiveBits() <= 32 &&
     278             :            "Too many bits for uint32_t");
     279       31279 :     Weights.push_back(Weight->getZExtValue());
     280       62558 :     WeightSum += Weights.back();
     281       31279 :     if (PostDominatedByUnreachable.count(TI->getSuccessor(i - 1)))
     282       12638 :       UnreachableIdxs.push_back(i - 1);
     283             :     else
     284       18641 :       ReachableIdxs.push_back(i - 1);
     285             :   }
     286             :   assert(Weights.size() == TI->getNumSuccessors() && "Checked above");
     287             : 
     288             :   // If the sum of weights does not fit in 32 bits, scale every weight down
     289             :   // accordingly.
     290          16 :   uint64_t ScalingFactor =
     291       15485 :       (WeightSum > UINT32_MAX) ? WeightSum / UINT32_MAX + 1 : 1;
     292             : 
     293             :   if (ScalingFactor > 1) {
     294          16 :     WeightSum = 0;
     295          66 :     for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
     296         100 :       Weights[i] /= ScalingFactor;
     297         100 :       WeightSum += Weights[i];
     298             :     }
     299             :   }
     300             :   assert(WeightSum <= UINT32_MAX &&
     301             :          "Expected weights to scale down to 32 bits");
     302             : 
     303       30967 :   if (WeightSum == 0 || ReachableIdxs.size() == 0) {
     304          66 :     for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
     305          94 :       Weights[i] = 1;
     306          19 :     WeightSum = TI->getNumSuccessors();
     307             :   }
     308             : 
     309             :   // Set the probability.
     310       15485 :   SmallVector<BranchProbability, 2> BP;
     311       46764 :   for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
     312       62558 :     BP.push_back({ Weights[i], static_cast<uint32_t>(WeightSum) });
     313             : 
     314             :   // Examine the metadata against unreachable heuristic.
     315             :   // If the unreachable heuristic is more strong then we use it for this edge.
     316       28044 :   if (UnreachableIdxs.size() > 0 && ReachableIdxs.size() > 0) {
     317       12543 :     auto ToDistribute = BranchProbability::getZero();
     318       12543 :     auto UnreachableProb = UR_TAKEN_PROB;
     319       25140 :     for (auto i : UnreachableIdxs)
     320       25194 :       if (UnreachableProb < BP[i]) {
     321       50352 :         ToDistribute += BP[i] - UnreachableProb;
     322       25176 :         BP[i] = UnreachableProb;
     323             :       }
     324             : 
     325             :     // If we modified the probability of some edges then we must distribute
     326             :     // the difference between reachable blocks.
     327       25086 :     if (ToDistribute > BranchProbability::getZero()) {
     328       25074 :       BranchProbability PerEdge = ToDistribute / ReachableIdxs.size();
     329       25095 :       for (auto i : ReachableIdxs)
     330       37674 :         BP[i] += PerEdge;
     331             :     }
     332             :   }
     333             : 
     334       46764 :   for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
     335       62558 :     setEdgeProbability(BB, i, BP[i]);
     336             : 
     337       15485 :   return true;
     338             : }
     339             : 
     340             : /// \brief Calculate edge weights for edges leading to cold blocks.
     341             : ///
     342             : /// A cold block is one post-dominated by  a block with a call to a
     343             : /// cold function.  Those edges are unlikely to be taken, so we give
     344             : /// them relatively low weight.
     345             : ///
     346             : /// Return true if we could compute the weights for cold edges.
     347             : /// Return false, otherwise.
     348      333540 : bool BranchProbabilityInfo::calcColdCallHeuristics(const BasicBlock *BB) {
     349      333540 :   const TerminatorInst *TI = BB->getTerminator();
     350             :   assert(TI->getNumSuccessors() > 1 && "expected more than one successor!");
     351             : 
     352             :   // Return false here so that edge weights for InvokeInst could be decided
     353             :   // in calcInvokeHeuristics().
     354      667080 :   if (isa<InvokeInst>(TI))
     355             :     return false;
     356             : 
     357             :   // Determine which successors are post-dominated by a cold block.
     358      173848 :   SmallVector<unsigned, 4> ColdEdges;
     359      347696 :   SmallVector<unsigned, 4> NormalEdges;
     360      702584 :   for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
     361      709776 :     if (PostDominatedByColdCall.count(*I))
     362         299 :       ColdEdges.push_back(I.getSuccessorIndex());
     363             :     else
     364      354589 :       NormalEdges.push_back(I.getSuccessorIndex());
     365             : 
     366             :   // Skip probabilities if no cold edges.
     367      173848 :   if (ColdEdges.empty())
     368             :     return false;
     369             : 
     370         281 :   if (NormalEdges.empty()) {
     371          18 :     BranchProbability Prob(1, ColdEdges.size());
     372          90 :     for (unsigned SuccIdx : ColdEdges)
     373          36 :       setEdgeProbability(BB, SuccIdx, Prob);
     374             :     return true;
     375             :   }
     376             : 
     377             :   auto ColdProb = BranchProbability::getBranchProbability(
     378             :       CC_TAKEN_WEIGHT,
     379         263 :       (CC_TAKEN_WEIGHT + CC_NONTAKEN_WEIGHT) * uint64_t(ColdEdges.size()));
     380             :   auto NormalProb = BranchProbability::getBranchProbability(
     381             :       CC_NONTAKEN_WEIGHT,
     382         263 :       (CC_TAKEN_WEIGHT + CC_NONTAKEN_WEIGHT) * uint64_t(NormalEdges.size()));
     383             : 
     384        1052 :   for (unsigned SuccIdx : ColdEdges)
     385         263 :     setEdgeProbability(BB, SuccIdx, ColdProb);
     386        1052 :   for (unsigned SuccIdx : NormalEdges)
     387         263 :     setEdgeProbability(BB, SuccIdx, NormalProb);
     388             : 
     389             :   return true;
     390             : }
     391             : 
     392             : // Calculate Edge Weights using "Pointer Heuristics". Predict a comparsion
     393             : // between two pointer or pointer and NULL will fail.
     394      277470 : bool BranchProbabilityInfo::calcPointerHeuristics(const BasicBlock *BB) {
     395      423899 :   const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
     396      146429 :   if (!BI || !BI->isConditional())
     397             :     return false;
     398             : 
     399      146429 :   Value *Cond = BI->getCondition();
     400      119344 :   ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
     401      119344 :   if (!CI || !CI->isEquality())
     402             :     return false;
     403             : 
     404      212342 :   Value *LHS = CI->getOperand(0);
     405             : 
     406      212342 :   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       55960 :   unsigned TakenIdx = 0, NonTakenIdx = 1;
     416      111920 :   bool isProb = CI->getPredicate() == ICmpInst::ICMP_NE;
     417       55960 :   if (!isProb)
     418             :     std::swap(TakenIdx, NonTakenIdx);
     419             : 
     420             :   BranchProbability TakenProb(PH_TAKEN_WEIGHT,
     421       55960 :                               PH_TAKEN_WEIGHT + PH_NONTAKEN_WEIGHT);
     422       55960 :   setEdgeProbability(BB, TakenIdx, TakenProb);
     423       55960 :   setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
     424       55960 :   return true;
     425             : }
     426             : 
     427             : // Calculate Edge Weights using "Loop Branch Heuristics". Predict backedges
     428             : // as taken, exiting edges as not-taken.
     429      333259 : bool BranchProbabilityInfo::calcLoopBranchHeuristics(const BasicBlock *BB,
     430             :                                                      const LoopInfo &LI) {
     431      666518 :   Loop *L = LI.getLoopFor(BB);
     432       85283 :   if (!L)
     433             :     return false;
     434             : 
     435       85283 :   SmallVector<unsigned, 8> BackEdges;
     436      170566 :   SmallVector<unsigned, 8> ExitingEdges;
     437      170566 :   SmallVector<unsigned, 8> InEdges; // Edges from header to the loop.
     438             : 
     439      342952 :   for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
     440      517158 :     if (!L->contains(*I))
     441       55690 :       ExitingEdges.push_back(I.getSuccessorIndex());
     442      350088 :     else if (L->getHeader() == *I)
     443       16838 :       BackEdges.push_back(I.getSuccessorIndex());
     444             :     else
     445       99858 :       InEdges.push_back(I.getSuccessorIndex());
     446             :   }
     447             : 
     448       85283 :   if (BackEdges.empty() && ExitingEdges.empty())
     449             :     return false;
     450             : 
     451             :   // Collect the sum of probabilities of back-edges/in-edges/exiting-edges, and
     452             :   // normalize them so that they sum up to one.
     453             :   BranchProbability Probs[] = {BranchProbability::getZero(),
     454             :                                BranchProbability::getZero(),
     455      167367 :                                BranchProbability::getZero()};
     456      111578 :   unsigned Denom = (BackEdges.empty() ? 0 : LBH_TAKEN_WEIGHT) +
     457       55789 :                    (InEdges.empty() ? 0 : LBH_TAKEN_WEIGHT) +
     458       55789 :                    (ExitingEdges.empty() ? 0 : LBH_NONTAKEN_WEIGHT);
     459       55789 :   if (!BackEdges.empty())
     460       16837 :     Probs[0] = BranchProbability(LBH_TAKEN_WEIGHT, Denom);
     461       55789 :   if (!InEdges.empty())
     462       39289 :     Probs[1] = BranchProbability(LBH_TAKEN_WEIGHT, Denom);
     463       55789 :   if (!ExitingEdges.empty())
     464       55512 :     Probs[2] = BranchProbability(LBH_NONTAKEN_WEIGHT, Denom);
     465             : 
     466       55789 :   if (uint32_t numBackEdges = BackEdges.size()) {
     467       16837 :     auto Prob = Probs[0] / numBackEdges;
     468       33675 :     for (unsigned SuccIdx : BackEdges)
     469       16838 :       setEdgeProbability(BB, SuccIdx, Prob);
     470             :   }
     471             : 
     472       55789 :   if (uint32_t numInEdges = InEdges.size()) {
     473       39289 :     auto Prob = Probs[1] / numInEdges;
     474       78874 :     for (unsigned SuccIdx : InEdges)
     475       39585 :       setEdgeProbability(BB, SuccIdx, Prob);
     476             :   }
     477             : 
     478       55789 :   if (uint32_t numExitingEdges = ExitingEdges.size()) {
     479       55512 :     auto Prob = Probs[2] / numExitingEdges;
     480      111202 :     for (unsigned SuccIdx : ExitingEdges)
     481       55690 :       setEdgeProbability(BB, SuccIdx, Prob);
     482             :   }
     483             : 
     484             :   return true;
     485             : }
     486             : 
     487      221510 : bool BranchProbabilityInfo::calcZeroHeuristics(const BasicBlock *BB,
     488             :                                                const TargetLibraryInfo *TLI) {
     489      311979 :   const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
     490       90469 :   if (!BI || !BI->isConditional())
     491             :     return false;
     492             : 
     493       90469 :   Value *Cond = BI->getCondition();
     494       63384 :   ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
     495             :   if (!CI)
     496             :     return false;
     497             : 
     498      126768 :   Value *RHS = CI->getOperand(1);
     499       47106 :   ConstantInt *CV = dyn_cast<ConstantInt>(RHS);
     500             :   if (!CV)
     501             :     return false;
     502             : 
     503             :   // If the LHS is the result of AND'ing a value with a single bit bitmask,
     504             :   // we don't have information about probabilities.
     505      136264 :   if (Instruction *LHS = dyn_cast<Instruction>(CI->getOperand(0)))
     506       42052 :     if (LHS->getOpcode() == Instruction::And)
     507        8696 :       if (ConstantInt *AndRHS = dyn_cast<ConstantInt>(LHS->getOperand(1)))
     508        2166 :         if (AndRHS->getValue().isPowerOf2())
     509             :           return false;
     510             : 
     511             :   // Check if the LHS is the return value of a library function
     512       45847 :   LibFunc Func = NumLibFuncs;
     513       45847 :   if (TLI)
     514       94653 :     if (CallInst *Call = dyn_cast<CallInst>(CI->getOperand(0)))
     515        3092 :       if (Function *CalledFn = Call->getCalledFunction())
     516             :         TLI->getLibFunc(*CalledFn, Func);
     517             : 
     518             :   bool isProb;
     519       45847 :   if (Func == LibFunc_strcasecmp ||
     520       45572 :       Func == LibFunc_strcmp ||
     521       45569 :       Func == LibFunc_strncasecmp ||
     522       45458 :       Func == LibFunc_strncmp ||
     523             :       Func == LibFunc_memcmp) {
     524             :     // strcmp and similar functions return zero, negative, or positive, if the
     525             :     // first string is equal, less, or greater than the second. We consider it
     526             :     // likely that the strings are not equal, so a comparison with zero is
     527             :     // probably false, but also a comparison with any other number is also
     528             :     // probably false given that what exactly is returned for nonzero values is
     529             :     // not specified. Any kind of comparison other than equality we know
     530             :     // nothing about.
     531         954 :     switch (CI->getPredicate()) {
     532             :     case CmpInst::ICMP_EQ:
     533             :       isProb = false;
     534             :       break;
     535             :     case CmpInst::ICMP_NE:
     536             :       isProb = true;
     537             :       break;
     538             :     default:
     539             :       return false;
     540             :     }
     541       45370 :   } else if (CV->isZero()) {
     542       64888 :     switch (CI->getPredicate()) {
     543             :     case CmpInst::ICMP_EQ:
     544             :       // X == 0   ->  Unlikely
     545             :       isProb = false;
     546             :       break;
     547             :     case CmpInst::ICMP_NE:
     548             :       // X != 0   ->  Likely
     549             :       isProb = true;
     550             :       break;
     551             :     case CmpInst::ICMP_SLT:
     552             :       // X < 0   ->  Unlikely
     553             :       isProb = false;
     554             :       break;
     555             :     case CmpInst::ICMP_SGT:
     556             :       // X > 0   ->  Likely
     557             :       isProb = true;
     558             :       break;
     559             :     default:
     560             :       return false;
     561             :     }
     562       14189 :   } else if (CV->isOne() && CI->getPredicate() == CmpInst::ICMP_SLT) {
     563             :     // InstCombine canonicalizes X <= 0 into X < 1.
     564             :     // X <= 0   ->  Unlikely
     565             :     isProb = false;
     566       12830 :   } else if (CV->isMinusOne()) {
     567        1986 :     switch (CI->getPredicate()) {
     568             :     case CmpInst::ICMP_EQ:
     569             :       // X == -1  ->  Unlikely
     570             :       isProb = false;
     571             :       break;
     572             :     case CmpInst::ICMP_NE:
     573             :       // X != -1  ->  Likely
     574             :       isProb = true;
     575             :       break;
     576             :     case CmpInst::ICMP_SGT:
     577             :       // InstCombine canonicalizes X >= 0 into X > -1.
     578             :       // X >= 0   ->  Likely
     579             :       isProb = true;
     580             :       break;
     581             :     default:
     582             :       return false;
     583             :     }
     584             :   } else {
     585             :     return false;
     586             :   }
     587             : 
     588             :   unsigned TakenIdx = 0, NonTakenIdx = 1;
     589             : 
     590             :   if (!isProb)
     591             :     std::swap(TakenIdx, NonTakenIdx);
     592             : 
     593             :   BranchProbability TakenProb(ZH_TAKEN_WEIGHT,
     594       33894 :                               ZH_TAKEN_WEIGHT + ZH_NONTAKEN_WEIGHT);
     595       33894 :   setEdgeProbability(BB, TakenIdx, TakenProb);
     596       33894 :   setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
     597       33894 :   return true;
     598             : }
     599             : 
     600      187616 : bool BranchProbabilityInfo::calcFloatingPointHeuristics(const BasicBlock *BB) {
     601      244191 :   const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
     602       56575 :   if (!BI || !BI->isConditional())
     603             :     return false;
     604             : 
     605       56575 :   Value *Cond = BI->getCondition();
     606        1152 :   FCmpInst *FCmp = dyn_cast<FCmpInst>(Cond);
     607             :   if (!FCmp)
     608             :     return false;
     609             : 
     610             :   bool isProb;
     611         784 :   if (FCmp->isEquality()) {
     612             :     // f1 == f2 -> Unlikely
     613             :     // f1 != f2 -> Likely
     614         736 :     isProb = !FCmp->isTrueWhenEqual();
     615        1568 :   } else if (FCmp->getPredicate() == FCmpInst::FCMP_ORD) {
     616             :     // !isnan -> Likely
     617             :     isProb = true;
     618        1506 :   } else if (FCmp->getPredicate() == FCmpInst::FCMP_UNO) {
     619             :     // isnan -> Unlikely
     620             :     isProb = false;
     621             :   } else {
     622             :     return false;
     623             :   }
     624             : 
     625         368 :   unsigned TakenIdx = 0, NonTakenIdx = 1;
     626             : 
     627         368 :   if (!isProb)
     628             :     std::swap(TakenIdx, NonTakenIdx);
     629             : 
     630             :   BranchProbability TakenProb(FPH_TAKEN_WEIGHT,
     631         421 :                               FPH_TAKEN_WEIGHT + FPH_NONTAKEN_WEIGHT);
     632         421 :   setEdgeProbability(BB, TakenIdx, TakenProb);
     633         421 :   setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
     634         421 :   return true;
     635             : }
     636             : 
     637      187195 : bool BranchProbabilityInfo::calcInvokeHeuristics(const BasicBlock *BB) {
     638      316029 :   const InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator());
     639             :   if (!II)
     640             :     return false;
     641             : 
     642             :   BranchProbability TakenProb(IH_TAKEN_WEIGHT,
     643      128834 :                               IH_TAKEN_WEIGHT + IH_NONTAKEN_WEIGHT);
     644      128834 :   setEdgeProbability(BB, 0 /*Index for Normal*/, TakenProb);
     645      128834 :   setEdgeProbability(BB, 1 /*Index for Unwind*/, TakenProb.getCompl());
     646      128834 :   return true;
     647             : }
     648             : 
     649      351478 : void BranchProbabilityInfo::releaseMemory() {
     650      351478 :   Probs.clear();
     651      351478 : }
     652             : 
     653         155 : void BranchProbabilityInfo::print(raw_ostream &OS) const {
     654         155 :   OS << "---- Branch Probabilities ----\n";
     655             :   // We print the probabilities from the last function the analysis ran over,
     656             :   // or the function it is currently running over.
     657             :   assert(LastF && "Cannot print prior to running over a function");
     658        1221 :   for (const auto &BI : *LastF) {
     659        2358 :     for (succ_const_iterator SI = succ_begin(&BI), SE = succ_end(&BI); SI != SE;
     660             :          ++SI) {
     661        1692 :       printEdgeProbability(OS << "  ", &BI, *SI);
     662             :     }
     663             :   }
     664         155 : }
     665             : 
     666         848 : bool BranchProbabilityInfo::
     667             : isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const {
     668             :   // Hot probability is at least 4/5 = 80%
     669             :   // FIXME: Compare against a static "hot" BranchProbability.
     670        1696 :   return getEdgeProbability(Src, Dst) > BranchProbability(4, 5);
     671             : }
     672             : 
     673             : const BasicBlock *
     674           0 : BranchProbabilityInfo::getHotSucc(const BasicBlock *BB) const {
     675           0 :   auto MaxProb = BranchProbability::getZero();
     676           0 :   const BasicBlock *MaxSucc = nullptr;
     677             : 
     678           0 :   for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
     679           0 :     const BasicBlock *Succ = *I;
     680           0 :     auto Prob = getEdgeProbability(BB, Succ);
     681           0 :     if (Prob > MaxProb) {
     682           0 :       MaxProb = Prob;
     683           0 :       MaxSucc = Succ;
     684             :     }
     685             :   }
     686             : 
     687             :   // Hot probability is at least 4/5 = 80%
     688           0 :   if (MaxProb > BranchProbability(4, 5))
     689           0 :     return MaxSucc;
     690             : 
     691             :   return nullptr;
     692             : }
     693             : 
     694             : /// Get the raw edge probability for the edge. If can't find it, return a
     695             : /// default probability 1/N where N is the number of successors. Here an edge is
     696             : /// specified using PredBlock and an
     697             : /// index to the successors.
     698             : BranchProbability
     699        3118 : BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
     700             :                                           unsigned IndexInSuccessors) const {
     701        6236 :   auto I = Probs.find(std::make_pair(Src, IndexInSuccessors));
     702             : 
     703        6236 :   if (I != Probs.end())
     704        1035 :     return I->second;
     705             : 
     706             :   return {1,
     707        6249 :           static_cast<uint32_t>(std::distance(succ_begin(Src), succ_end(Src)))};
     708             : }
     709             : 
     710             : BranchProbability
     711           0 : BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
     712             :                                           succ_const_iterator Dst) const {
     713           0 :   return getEdgeProbability(Src, Dst.getSuccessorIndex());
     714             : }
     715             : 
     716             : /// Get the raw edge probability calculated for the block pair. This returns the
     717             : /// sum of all raw edge probabilities from Src to Dst.
     718             : BranchProbability
     719      996790 : BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
     720             :                                           const BasicBlock *Dst) const {
     721      996790 :   auto Prob = BranchProbability::getZero();
     722      996790 :   bool FoundProb = false;
     723     4866252 :   for (succ_const_iterator I = succ_begin(Src), E = succ_end(Src); I != E; ++I)
     724     3751764 :     if (*I == Dst) {
     725     2059802 :       auto MapI = Probs.find(std::make_pair(Src, I.getSuccessorIndex()));
     726     2059802 :       if (MapI != Probs.end()) {
     727      613372 :         FoundProb = true;
     728      613372 :         Prob += MapI->second;
     729             :       }
     730             :     }
     731     2990370 :   uint32_t succ_num = std::distance(succ_begin(Src), succ_end(Src));
     732      996790 :   return FoundProb ? Prob : BranchProbability(1, succ_num);
     733             : }
     734             : 
     735             : /// Set the edge probability for a given edge specified by PredBlock and an
     736             : /// index to the successors.
     737      609438 : void BranchProbabilityInfo::setEdgeProbability(const BasicBlock *Src,
     738             :                                                unsigned IndexInSuccessors,
     739             :                                                BranchProbability Prob) {
     740     1828314 :   Probs[std::make_pair(Src, IndexInSuccessors)] = Prob;
     741     2437752 :   Handles.insert(BasicBlockCallbackVH(Src, this));
     742             :   DEBUG(dbgs() << "set edge " << Src->getName() << " -> " << IndexInSuccessors
     743             :                << " successor probability to " << Prob << "\n");
     744      609438 : }
     745             : 
     746             : raw_ostream &
     747         846 : BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS,
     748             :                                             const BasicBlock *Src,
     749             :                                             const BasicBlock *Dst) const {
     750         846 :   const BranchProbability Prob = getEdgeProbability(Src, Dst);
     751         846 :   OS << "edge " << Src->getName() << " -> " << Dst->getName()
     752        1692 :      << " probability is " << Prob
     753         846 :      << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n");
     754             : 
     755         846 :   return OS;
     756             : }
     757             : 
     758       10547 : void BranchProbabilityInfo::eraseBlock(const BasicBlock *BB) {
     759       42671 :   for (auto I = Probs.begin(), E = Probs.end(); I != E; ++I) {
     760        5515 :     auto Key = I->first;
     761        5515 :     if (Key.first == BB)
     762        4213 :       Probs.erase(Key);
     763             :   }
     764       10547 : }
     765             : 
     766      352801 : void BranchProbabilityInfo::calculate(const Function &F, const LoopInfo &LI,
     767             :                                       const TargetLibraryInfo *TLI) {
     768             :   DEBUG(dbgs() << "---- Branch Probability Info : " << F.getName()
     769             :                << " ----\n\n");
     770      352801 :   LastF = &F; // Store the last function we ran on for printing.
     771             :   assert(PostDominatedByUnreachable.empty());
     772             :   assert(PostDominatedByColdCall.empty());
     773             : 
     774             :   // Walk the basic blocks in post-order so that we can build up state about
     775             :   // the successors of a block iteratively.
     776     3989949 :   for (auto BB : post_order(&F.getEntryBlock())) {
     777             :     DEBUG(dbgs() << "Computing probabilities for " << BB->getName() << "\n");
     778     1112972 :     updatePostDominatedByUnreachable(BB);
     779     1112972 :     updatePostDominatedByColdCall(BB);
     780             :     // If there is no at least two successors, no sense to set probability.
     781     1112972 :     if (BB->getTerminator()->getNumSuccessors() < 2)
     782      752974 :       continue;
     783      359998 :     if (calcMetadataWeights(BB))
     784       15485 :       continue;
     785      344513 :     if (calcUnreachableHeuristics(BB))
     786       10973 :       continue;
     787      333540 :     if (calcColdCallHeuristics(BB))
     788         281 :       continue;
     789      333259 :     if (calcLoopBranchHeuristics(BB, LI))
     790       55789 :       continue;
     791      277470 :     if (calcPointerHeuristics(BB))
     792       55960 :       continue;
     793      221510 :     if (calcZeroHeuristics(BB, TLI))
     794       33894 :       continue;
     795      187616 :     if (calcFloatingPointHeuristics(BB))
     796         421 :       continue;
     797      187195 :     calcInvokeHeuristics(BB);
     798             :   }
     799             : 
     800      352801 :   PostDominatedByUnreachable.clear();
     801      352801 :   PostDominatedByColdCall.clear();
     802             : 
     803      352801 :   if (PrintBranchProb &&
     804           0 :       (PrintBranchProbFuncName.empty() ||
     805      705602 :        F.getName().equals(PrintBranchProbFuncName))) {
     806           0 :     print(dbgs());
     807             :   }
     808      352801 : }
     809             : 
     810       37017 : void BranchProbabilityInfoWrapperPass::getAnalysisUsage(
     811             :     AnalysisUsage &AU) const {
     812       37017 :   AU.addRequired<LoopInfoWrapperPass>();
     813       37017 :   AU.addRequired<TargetLibraryInfoWrapperPass>();
     814       37017 :   AU.setPreservesAll();
     815       37017 : }
     816             : 
     817      351551 : bool BranchProbabilityInfoWrapperPass::runOnFunction(Function &F) {
     818      703102 :   const LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
     819      703102 :   const TargetLibraryInfo &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
     820      351551 :   BPI.calculate(F, LI, &TLI);
     821      351551 :   return false;
     822             : }
     823             : 
     824      351478 : void BranchProbabilityInfoWrapperPass::releaseMemory() { BPI.releaseMemory(); }
     825             : 
     826          75 : void BranchProbabilityInfoWrapperPass::print(raw_ostream &OS,
     827             :                                              const Module *) const {
     828          75 :   BPI.print(OS);
     829          75 : }
     830             : 
     831             : AnalysisKey BranchProbabilityAnalysis::Key;
     832             : BranchProbabilityInfo
     833         799 : BranchProbabilityAnalysis::run(Function &F, FunctionAnalysisManager &AM) {
     834         799 :   BranchProbabilityInfo BPI;
     835        1598 :   BPI.calculate(F, AM.getResult<LoopAnalysis>(F), &AM.getResult<TargetLibraryAnalysis>(F));
     836         799 :   return BPI;
     837             : }
     838             : 
     839             : PreservedAnalyses
     840          48 : BranchProbabilityPrinterPass::run(Function &F, FunctionAnalysisManager &AM) {
     841          48 :   OS << "Printing analysis results of BPI for function "
     842          48 :      << "'" << F.getName() << "':"
     843          48 :      << "\n";
     844          48 :   AM.getResult<BranchProbabilityAnalysis>(F).print(OS);
     845          48 :   return PreservedAnalyses::all();
     846      216918 : }

Generated by: LCOV version 1.13