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

Generated by: LCOV version 1.13