xref: /freebsd-src/contrib/llvm-project/llvm/lib/Analysis/BranchProbabilityInfo.cpp (revision 0fca6ea1d4eea4c934cfff25ac9ee8ad6fe95583)
10b57cec5SDimitry Andric //===- BranchProbabilityInfo.cpp - Branch Probability Analysis ------------===//
20b57cec5SDimitry Andric //
30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
60b57cec5SDimitry Andric //
70b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
80b57cec5SDimitry Andric //
90b57cec5SDimitry Andric // Loops should be simplified before this analysis.
100b57cec5SDimitry Andric //
110b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
120b57cec5SDimitry Andric 
130b57cec5SDimitry Andric #include "llvm/Analysis/BranchProbabilityInfo.h"
140b57cec5SDimitry Andric #include "llvm/ADT/PostOrderIterator.h"
150b57cec5SDimitry Andric #include "llvm/ADT/SCCIterator.h"
160b57cec5SDimitry Andric #include "llvm/ADT/STLExtras.h"
170b57cec5SDimitry Andric #include "llvm/ADT/SmallVector.h"
18753f127fSDimitry Andric #include "llvm/Analysis/ConstantFolding.h"
190b57cec5SDimitry Andric #include "llvm/Analysis/LoopInfo.h"
20480093f4SDimitry Andric #include "llvm/Analysis/PostDominators.h"
210b57cec5SDimitry Andric #include "llvm/Analysis/TargetLibraryInfo.h"
220b57cec5SDimitry Andric #include "llvm/IR/Attributes.h"
230b57cec5SDimitry Andric #include "llvm/IR/BasicBlock.h"
240b57cec5SDimitry Andric #include "llvm/IR/CFG.h"
250b57cec5SDimitry Andric #include "llvm/IR/Constants.h"
260b57cec5SDimitry Andric #include "llvm/IR/Dominators.h"
270b57cec5SDimitry Andric #include "llvm/IR/Function.h"
280b57cec5SDimitry Andric #include "llvm/IR/InstrTypes.h"
290b57cec5SDimitry Andric #include "llvm/IR/Instruction.h"
300b57cec5SDimitry Andric #include "llvm/IR/Instructions.h"
310b57cec5SDimitry Andric #include "llvm/IR/LLVMContext.h"
320b57cec5SDimitry Andric #include "llvm/IR/Metadata.h"
330b57cec5SDimitry Andric #include "llvm/IR/PassManager.h"
34bdd1243dSDimitry Andric #include "llvm/IR/ProfDataUtils.h"
350b57cec5SDimitry Andric #include "llvm/IR/Type.h"
360b57cec5SDimitry Andric #include "llvm/IR/Value.h"
37480093f4SDimitry Andric #include "llvm/InitializePasses.h"
380b57cec5SDimitry Andric #include "llvm/Pass.h"
390b57cec5SDimitry Andric #include "llvm/Support/BranchProbability.h"
400b57cec5SDimitry Andric #include "llvm/Support/Casting.h"
41480093f4SDimitry Andric #include "llvm/Support/CommandLine.h"
420b57cec5SDimitry Andric #include "llvm/Support/Debug.h"
430b57cec5SDimitry Andric #include "llvm/Support/raw_ostream.h"
440b57cec5SDimitry Andric #include <cassert>
450b57cec5SDimitry Andric #include <cstdint>
460b57cec5SDimitry Andric #include <iterator>
4704eeddc0SDimitry Andric #include <map>
480b57cec5SDimitry Andric #include <utility>
490b57cec5SDimitry Andric 
500b57cec5SDimitry Andric using namespace llvm;
510b57cec5SDimitry Andric 
520b57cec5SDimitry Andric #define DEBUG_TYPE "branch-prob"
530b57cec5SDimitry Andric 
540b57cec5SDimitry Andric static cl::opt<bool> PrintBranchProb(
550b57cec5SDimitry Andric     "print-bpi", cl::init(false), cl::Hidden,
560b57cec5SDimitry Andric     cl::desc("Print the branch probability info."));
570b57cec5SDimitry Andric 
580b57cec5SDimitry Andric cl::opt<std::string> PrintBranchProbFuncName(
590b57cec5SDimitry Andric     "print-bpi-func-name", cl::Hidden,
600b57cec5SDimitry Andric     cl::desc("The option to specify the name of the function "
610b57cec5SDimitry Andric              "whose branch probability info is printed."));
620b57cec5SDimitry Andric 
630b57cec5SDimitry Andric INITIALIZE_PASS_BEGIN(BranchProbabilityInfoWrapperPass, "branch-prob",
640b57cec5SDimitry Andric                       "Branch Probability Analysis", false, true)
650b57cec5SDimitry Andric INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
660b57cec5SDimitry Andric INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
67e8d8bef9SDimitry Andric INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
685ffd83dbSDimitry Andric INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
690b57cec5SDimitry Andric INITIALIZE_PASS_END(BranchProbabilityInfoWrapperPass, "branch-prob",
700b57cec5SDimitry Andric                     "Branch Probability Analysis", false, true)
710b57cec5SDimitry Andric 
72480093f4SDimitry Andric BranchProbabilityInfoWrapperPass::BranchProbabilityInfoWrapperPass()
73480093f4SDimitry Andric     : FunctionPass(ID) {
74480093f4SDimitry Andric   initializeBranchProbabilityInfoWrapperPassPass(
75480093f4SDimitry Andric       *PassRegistry::getPassRegistry());
76480093f4SDimitry Andric }
77480093f4SDimitry Andric 
780b57cec5SDimitry Andric char BranchProbabilityInfoWrapperPass::ID = 0;
790b57cec5SDimitry Andric 
800b57cec5SDimitry Andric // Weights are for internal use only. They are used by heuristics to help to
810b57cec5SDimitry Andric // estimate edges' probability. Example:
820b57cec5SDimitry Andric //
830b57cec5SDimitry Andric // Using "Loop Branch Heuristics" we predict weights of edges for the
840b57cec5SDimitry Andric // block BB2.
850b57cec5SDimitry Andric //         ...
860b57cec5SDimitry Andric //          |
870b57cec5SDimitry Andric //          V
880b57cec5SDimitry Andric //         BB1<-+
890b57cec5SDimitry Andric //          |   |
900b57cec5SDimitry Andric //          |   | (Weight = 124)
910b57cec5SDimitry Andric //          V   |
920b57cec5SDimitry Andric //         BB2--+
930b57cec5SDimitry Andric //          |
940b57cec5SDimitry Andric //          | (Weight = 4)
950b57cec5SDimitry Andric //          V
960b57cec5SDimitry Andric //         BB3
970b57cec5SDimitry Andric //
980b57cec5SDimitry Andric // Probability of the edge BB2->BB1 = 124 / (124 + 4) = 0.96875
990b57cec5SDimitry Andric // Probability of the edge BB2->BB3 = 4 / (124 + 4) = 0.03125
1000b57cec5SDimitry Andric static const uint32_t LBH_TAKEN_WEIGHT = 124;
1010b57cec5SDimitry Andric static const uint32_t LBH_NONTAKEN_WEIGHT = 4;
1020b57cec5SDimitry Andric 
1030b57cec5SDimitry Andric /// Unreachable-terminating branch taken probability.
1040b57cec5SDimitry Andric ///
1050b57cec5SDimitry Andric /// This is the probability for a branch being taken to a block that terminates
1060b57cec5SDimitry Andric /// (eventually) in unreachable. These are predicted as unlikely as possible.
1075ffd83dbSDimitry Andric /// All reachable probability will proportionally share the remaining part.
1080b57cec5SDimitry Andric static const BranchProbability UR_TAKEN_PROB = BranchProbability::getRaw(1);
1090b57cec5SDimitry Andric 
1104824e7fdSDimitry Andric /// Heuristics and lookup tables for non-loop branches:
1114824e7fdSDimitry Andric /// Pointer Heuristics (PH)
1120b57cec5SDimitry Andric static const uint32_t PH_TAKEN_WEIGHT = 20;
1130b57cec5SDimitry Andric static const uint32_t PH_NONTAKEN_WEIGHT = 12;
1144824e7fdSDimitry Andric static const BranchProbability
1154824e7fdSDimitry Andric     PtrTakenProb(PH_TAKEN_WEIGHT, PH_TAKEN_WEIGHT + PH_NONTAKEN_WEIGHT);
1164824e7fdSDimitry Andric static const BranchProbability
1174824e7fdSDimitry Andric     PtrUntakenProb(PH_NONTAKEN_WEIGHT, PH_TAKEN_WEIGHT + PH_NONTAKEN_WEIGHT);
1180b57cec5SDimitry Andric 
1194824e7fdSDimitry Andric using ProbabilityList = SmallVector<BranchProbability>;
1204824e7fdSDimitry Andric using ProbabilityTable = std::map<CmpInst::Predicate, ProbabilityList>;
1214824e7fdSDimitry Andric 
1224824e7fdSDimitry Andric /// Pointer comparisons:
1234824e7fdSDimitry Andric static const ProbabilityTable PointerTable{
1244824e7fdSDimitry Andric     {ICmpInst::ICMP_NE, {PtrTakenProb, PtrUntakenProb}}, /// p != q -> Likely
1254824e7fdSDimitry Andric     {ICmpInst::ICMP_EQ, {PtrUntakenProb, PtrTakenProb}}, /// p == q -> Unlikely
1264824e7fdSDimitry Andric };
1274824e7fdSDimitry Andric 
1284824e7fdSDimitry Andric /// Zero Heuristics (ZH)
1290b57cec5SDimitry Andric static const uint32_t ZH_TAKEN_WEIGHT = 20;
1300b57cec5SDimitry Andric static const uint32_t ZH_NONTAKEN_WEIGHT = 12;
1314824e7fdSDimitry Andric static const BranchProbability
1324824e7fdSDimitry Andric     ZeroTakenProb(ZH_TAKEN_WEIGHT, ZH_TAKEN_WEIGHT + ZH_NONTAKEN_WEIGHT);
1334824e7fdSDimitry Andric static const BranchProbability
1344824e7fdSDimitry Andric     ZeroUntakenProb(ZH_NONTAKEN_WEIGHT, ZH_TAKEN_WEIGHT + ZH_NONTAKEN_WEIGHT);
1350b57cec5SDimitry Andric 
1364824e7fdSDimitry Andric /// Integer compares with 0:
1374824e7fdSDimitry Andric static const ProbabilityTable ICmpWithZeroTable{
1384824e7fdSDimitry Andric     {CmpInst::ICMP_EQ, {ZeroUntakenProb, ZeroTakenProb}},  /// X == 0 -> Unlikely
1394824e7fdSDimitry Andric     {CmpInst::ICMP_NE, {ZeroTakenProb, ZeroUntakenProb}},  /// X != 0 -> Likely
1404824e7fdSDimitry Andric     {CmpInst::ICMP_SLT, {ZeroUntakenProb, ZeroTakenProb}}, /// X < 0  -> Unlikely
1414824e7fdSDimitry Andric     {CmpInst::ICMP_SGT, {ZeroTakenProb, ZeroUntakenProb}}, /// X > 0  -> Likely
1424824e7fdSDimitry Andric };
1434824e7fdSDimitry Andric 
1444824e7fdSDimitry Andric /// Integer compares with -1:
1454824e7fdSDimitry Andric static const ProbabilityTable ICmpWithMinusOneTable{
1464824e7fdSDimitry Andric     {CmpInst::ICMP_EQ, {ZeroUntakenProb, ZeroTakenProb}},  /// X == -1 -> Unlikely
1474824e7fdSDimitry Andric     {CmpInst::ICMP_NE, {ZeroTakenProb, ZeroUntakenProb}},  /// X != -1 -> Likely
1484824e7fdSDimitry Andric     // InstCombine canonicalizes X >= 0 into X > -1
1494824e7fdSDimitry Andric     {CmpInst::ICMP_SGT, {ZeroTakenProb, ZeroUntakenProb}}, /// X >= 0  -> Likely
1504824e7fdSDimitry Andric };
1514824e7fdSDimitry Andric 
1524824e7fdSDimitry Andric /// Integer compares with 1:
1534824e7fdSDimitry Andric static const ProbabilityTable ICmpWithOneTable{
1544824e7fdSDimitry Andric     // InstCombine canonicalizes X <= 0 into X < 1
1554824e7fdSDimitry Andric     {CmpInst::ICMP_SLT, {ZeroUntakenProb, ZeroTakenProb}}, /// X <= 0 -> Unlikely
1564824e7fdSDimitry Andric };
1574824e7fdSDimitry Andric 
1584824e7fdSDimitry Andric /// strcmp and similar functions return zero, negative, or positive, if the
1594824e7fdSDimitry Andric /// first string is equal, less, or greater than the second. We consider it
1604824e7fdSDimitry Andric /// likely that the strings are not equal, so a comparison with zero is
1614824e7fdSDimitry Andric /// probably false, but also a comparison with any other number is also
1624824e7fdSDimitry Andric /// probably false given that what exactly is returned for nonzero values is
1634824e7fdSDimitry Andric /// not specified. Any kind of comparison other than equality we know
1644824e7fdSDimitry Andric /// nothing about.
1654824e7fdSDimitry Andric static const ProbabilityTable ICmpWithLibCallTable{
1664824e7fdSDimitry Andric     {CmpInst::ICMP_EQ, {ZeroUntakenProb, ZeroTakenProb}},
1674824e7fdSDimitry Andric     {CmpInst::ICMP_NE, {ZeroTakenProb, ZeroUntakenProb}},
1684824e7fdSDimitry Andric };
1694824e7fdSDimitry Andric 
1704824e7fdSDimitry Andric // Floating-Point Heuristics (FPH)
1710b57cec5SDimitry Andric static const uint32_t FPH_TAKEN_WEIGHT = 20;
1720b57cec5SDimitry Andric static const uint32_t FPH_NONTAKEN_WEIGHT = 12;
1730b57cec5SDimitry Andric 
1748bcb0991SDimitry Andric /// This is the probability for an ordered floating point comparison.
1758bcb0991SDimitry Andric static const uint32_t FPH_ORD_WEIGHT = 1024 * 1024 - 1;
1768bcb0991SDimitry Andric /// This is the probability for an unordered floating point comparison, it means
1778bcb0991SDimitry Andric /// one or two of the operands are NaN. Usually it is used to test for an
1788bcb0991SDimitry Andric /// exceptional case, so the result is unlikely.
1798bcb0991SDimitry Andric static const uint32_t FPH_UNO_WEIGHT = 1;
1808bcb0991SDimitry Andric 
1814824e7fdSDimitry Andric static const BranchProbability FPOrdTakenProb(FPH_ORD_WEIGHT,
1824824e7fdSDimitry Andric                                               FPH_ORD_WEIGHT + FPH_UNO_WEIGHT);
1834824e7fdSDimitry Andric static const BranchProbability
1844824e7fdSDimitry Andric     FPOrdUntakenProb(FPH_UNO_WEIGHT, FPH_ORD_WEIGHT + FPH_UNO_WEIGHT);
1854824e7fdSDimitry Andric static const BranchProbability
1864824e7fdSDimitry Andric     FPTakenProb(FPH_TAKEN_WEIGHT, FPH_TAKEN_WEIGHT + FPH_NONTAKEN_WEIGHT);
1874824e7fdSDimitry Andric static const BranchProbability
1884824e7fdSDimitry Andric     FPUntakenProb(FPH_NONTAKEN_WEIGHT, FPH_TAKEN_WEIGHT + FPH_NONTAKEN_WEIGHT);
1894824e7fdSDimitry Andric 
1904824e7fdSDimitry Andric /// Floating-Point compares:
1914824e7fdSDimitry Andric static const ProbabilityTable FCmpTable{
1924824e7fdSDimitry Andric     {FCmpInst::FCMP_ORD, {FPOrdTakenProb, FPOrdUntakenProb}}, /// !isnan -> Likely
1934824e7fdSDimitry Andric     {FCmpInst::FCMP_UNO, {FPOrdUntakenProb, FPOrdTakenProb}}, /// isnan -> Unlikely
1944824e7fdSDimitry Andric };
1954824e7fdSDimitry Andric 
196e8d8bef9SDimitry Andric /// Set of dedicated "absolute" execution weights for a block. These weights are
197e8d8bef9SDimitry Andric /// meaningful relative to each other and their derivatives only.
198e8d8bef9SDimitry Andric enum class BlockExecWeight : std::uint32_t {
199e8d8bef9SDimitry Andric   /// Special weight used for cases with exact zero probability.
200e8d8bef9SDimitry Andric   ZERO = 0x0,
201e8d8bef9SDimitry Andric   /// Minimal possible non zero weight.
202e8d8bef9SDimitry Andric   LOWEST_NON_ZERO = 0x1,
203e8d8bef9SDimitry Andric   /// Weight to an 'unreachable' block.
204e8d8bef9SDimitry Andric   UNREACHABLE = ZERO,
205e8d8bef9SDimitry Andric   /// Weight to a block containing non returning call.
206e8d8bef9SDimitry Andric   NORETURN = LOWEST_NON_ZERO,
207e8d8bef9SDimitry Andric   /// Weight to 'unwind' block of an invoke instruction.
208e8d8bef9SDimitry Andric   UNWIND = LOWEST_NON_ZERO,
209e8d8bef9SDimitry Andric   /// Weight to a 'cold' block. Cold blocks are the ones containing calls marked
210e8d8bef9SDimitry Andric   /// with attribute 'cold'.
211e8d8bef9SDimitry Andric   COLD = 0xffff,
212e8d8bef9SDimitry Andric   /// Default weight is used in cases when there is no dedicated execution
213e8d8bef9SDimitry Andric   /// weight set. It is not propagated through the domination line either.
214e8d8bef9SDimitry Andric   DEFAULT = 0xfffff
215e8d8bef9SDimitry Andric };
2160b57cec5SDimitry Andric 
217e8d8bef9SDimitry Andric BranchProbabilityInfo::SccInfo::SccInfo(const Function &F) {
218e8d8bef9SDimitry Andric   // Record SCC numbers of blocks in the CFG to identify irreducible loops.
219e8d8bef9SDimitry Andric   // FIXME: We could only calculate this if the CFG is known to be irreducible
220e8d8bef9SDimitry Andric   // (perhaps cache this info in LoopInfo if we can easily calculate it there?).
221e8d8bef9SDimitry Andric   int SccNum = 0;
222e8d8bef9SDimitry Andric   for (scc_iterator<const Function *> It = scc_begin(&F); !It.isAtEnd();
223e8d8bef9SDimitry Andric        ++It, ++SccNum) {
224e8d8bef9SDimitry Andric     // Ignore single-block SCCs since they either aren't loops or LoopInfo will
225e8d8bef9SDimitry Andric     // catch them.
226e8d8bef9SDimitry Andric     const std::vector<const BasicBlock *> &Scc = *It;
227e8d8bef9SDimitry Andric     if (Scc.size() == 1)
228480093f4SDimitry Andric       continue;
229e8d8bef9SDimitry Andric 
230e8d8bef9SDimitry Andric     LLVM_DEBUG(dbgs() << "BPI: SCC " << SccNum << ":");
231e8d8bef9SDimitry Andric     for (const auto *BB : Scc) {
232e8d8bef9SDimitry Andric       LLVM_DEBUG(dbgs() << " " << BB->getName());
233e8d8bef9SDimitry Andric       SccNums[BB] = SccNum;
234e8d8bef9SDimitry Andric       calculateSccBlockType(BB, SccNum);
235480093f4SDimitry Andric     }
236e8d8bef9SDimitry Andric     LLVM_DEBUG(dbgs() << "\n");
237e8d8bef9SDimitry Andric   }
238e8d8bef9SDimitry Andric }
239e8d8bef9SDimitry Andric 
240e8d8bef9SDimitry Andric int BranchProbabilityInfo::SccInfo::getSCCNum(const BasicBlock *BB) const {
241e8d8bef9SDimitry Andric   auto SccIt = SccNums.find(BB);
242e8d8bef9SDimitry Andric   if (SccIt == SccNums.end())
243e8d8bef9SDimitry Andric     return -1;
244e8d8bef9SDimitry Andric   return SccIt->second;
245e8d8bef9SDimitry Andric }
246e8d8bef9SDimitry Andric 
247e8d8bef9SDimitry Andric void BranchProbabilityInfo::SccInfo::getSccEnterBlocks(
248e8d8bef9SDimitry Andric     int SccNum, SmallVectorImpl<BasicBlock *> &Enters) const {
249e8d8bef9SDimitry Andric 
250e8d8bef9SDimitry Andric   for (auto MapIt : SccBlocks[SccNum]) {
251e8d8bef9SDimitry Andric     const auto *BB = MapIt.first;
252e8d8bef9SDimitry Andric     if (isSCCHeader(BB, SccNum))
253e8d8bef9SDimitry Andric       for (const auto *Pred : predecessors(BB))
254e8d8bef9SDimitry Andric         if (getSCCNum(Pred) != SccNum)
255e8d8bef9SDimitry Andric           Enters.push_back(const_cast<BasicBlock *>(BB));
256e8d8bef9SDimitry Andric   }
257e8d8bef9SDimitry Andric }
258e8d8bef9SDimitry Andric 
259e8d8bef9SDimitry Andric void BranchProbabilityInfo::SccInfo::getSccExitBlocks(
260e8d8bef9SDimitry Andric     int SccNum, SmallVectorImpl<BasicBlock *> &Exits) const {
261e8d8bef9SDimitry Andric   for (auto MapIt : SccBlocks[SccNum]) {
262e8d8bef9SDimitry Andric     const auto *BB = MapIt.first;
263e8d8bef9SDimitry Andric     if (isSCCExitingBlock(BB, SccNum))
264e8d8bef9SDimitry Andric       for (const auto *Succ : successors(BB))
265e8d8bef9SDimitry Andric         if (getSCCNum(Succ) != SccNum)
266349cc55cSDimitry Andric           Exits.push_back(const_cast<BasicBlock *>(Succ));
267e8d8bef9SDimitry Andric   }
268e8d8bef9SDimitry Andric }
269e8d8bef9SDimitry Andric 
270e8d8bef9SDimitry Andric uint32_t BranchProbabilityInfo::SccInfo::getSccBlockType(const BasicBlock *BB,
271e8d8bef9SDimitry Andric                                                          int SccNum) const {
272e8d8bef9SDimitry Andric   assert(getSCCNum(BB) == SccNum);
273e8d8bef9SDimitry Andric 
274e8d8bef9SDimitry Andric   assert(SccBlocks.size() > static_cast<unsigned>(SccNum) && "Unknown SCC");
275e8d8bef9SDimitry Andric   const auto &SccBlockTypes = SccBlocks[SccNum];
276e8d8bef9SDimitry Andric 
277e8d8bef9SDimitry Andric   auto It = SccBlockTypes.find(BB);
278e8d8bef9SDimitry Andric   if (It != SccBlockTypes.end()) {
279e8d8bef9SDimitry Andric     return It->second;
280e8d8bef9SDimitry Andric   }
281e8d8bef9SDimitry Andric   return Inner;
282e8d8bef9SDimitry Andric }
283e8d8bef9SDimitry Andric 
284e8d8bef9SDimitry Andric void BranchProbabilityInfo::SccInfo::calculateSccBlockType(const BasicBlock *BB,
285e8d8bef9SDimitry Andric                                                            int SccNum) {
286e8d8bef9SDimitry Andric   assert(getSCCNum(BB) == SccNum);
287e8d8bef9SDimitry Andric   uint32_t BlockType = Inner;
288e8d8bef9SDimitry Andric 
289e8d8bef9SDimitry Andric   if (llvm::any_of(predecessors(BB), [&](const BasicBlock *Pred) {
290e8d8bef9SDimitry Andric         // Consider any block that is an entry point to the SCC as
291e8d8bef9SDimitry Andric         // a header.
292e8d8bef9SDimitry Andric         return getSCCNum(Pred) != SccNum;
293480093f4SDimitry Andric       }))
294e8d8bef9SDimitry Andric     BlockType |= Header;
2950b57cec5SDimitry Andric 
296e8d8bef9SDimitry Andric   if (llvm::any_of(successors(BB), [&](const BasicBlock *Succ) {
297e8d8bef9SDimitry Andric         return getSCCNum(Succ) != SccNum;
298480093f4SDimitry Andric       }))
299e8d8bef9SDimitry Andric     BlockType |= Exiting;
300e8d8bef9SDimitry Andric 
301e8d8bef9SDimitry Andric   // Lazily compute the set of headers for a given SCC and cache the results
302e8d8bef9SDimitry Andric   // in the SccHeaderMap.
303e8d8bef9SDimitry Andric   if (SccBlocks.size() <= static_cast<unsigned>(SccNum))
304e8d8bef9SDimitry Andric     SccBlocks.resize(SccNum + 1);
305e8d8bef9SDimitry Andric   auto &SccBlockTypes = SccBlocks[SccNum];
306e8d8bef9SDimitry Andric 
307e8d8bef9SDimitry Andric   if (BlockType != Inner) {
308e8d8bef9SDimitry Andric     bool IsInserted;
309e8d8bef9SDimitry Andric     std::tie(std::ignore, IsInserted) =
310e8d8bef9SDimitry Andric         SccBlockTypes.insert(std::make_pair(BB, BlockType));
311e8d8bef9SDimitry Andric     assert(IsInserted && "Duplicated block in SCC");
3120b57cec5SDimitry Andric   }
3130b57cec5SDimitry Andric }
3140b57cec5SDimitry Andric 
315e8d8bef9SDimitry Andric BranchProbabilityInfo::LoopBlock::LoopBlock(const BasicBlock *BB,
316e8d8bef9SDimitry Andric                                             const LoopInfo &LI,
317e8d8bef9SDimitry Andric                                             const SccInfo &SccI)
318e8d8bef9SDimitry Andric     : BB(BB) {
319e8d8bef9SDimitry Andric   LD.first = LI.getLoopFor(BB);
320e8d8bef9SDimitry Andric   if (!LD.first) {
321e8d8bef9SDimitry Andric     LD.second = SccI.getSCCNum(BB);
322e8d8bef9SDimitry Andric   }
3230b57cec5SDimitry Andric }
3240b57cec5SDimitry Andric 
325e8d8bef9SDimitry Andric bool BranchProbabilityInfo::isLoopEnteringEdge(const LoopEdge &Edge) const {
326e8d8bef9SDimitry Andric   const auto &SrcBlock = Edge.first;
327e8d8bef9SDimitry Andric   const auto &DstBlock = Edge.second;
328e8d8bef9SDimitry Andric   return (DstBlock.getLoop() &&
329e8d8bef9SDimitry Andric           !DstBlock.getLoop()->contains(SrcBlock.getLoop())) ||
330e8d8bef9SDimitry Andric          // Assume that SCCs can't be nested.
331e8d8bef9SDimitry Andric          (DstBlock.getSccNum() != -1 &&
332e8d8bef9SDimitry Andric           SrcBlock.getSccNum() != DstBlock.getSccNum());
333e8d8bef9SDimitry Andric }
3340b57cec5SDimitry Andric 
335e8d8bef9SDimitry Andric bool BranchProbabilityInfo::isLoopExitingEdge(const LoopEdge &Edge) const {
336e8d8bef9SDimitry Andric   return isLoopEnteringEdge({Edge.second, Edge.first});
337e8d8bef9SDimitry Andric }
3380b57cec5SDimitry Andric 
339e8d8bef9SDimitry Andric bool BranchProbabilityInfo::isLoopEnteringExitingEdge(
340e8d8bef9SDimitry Andric     const LoopEdge &Edge) const {
341e8d8bef9SDimitry Andric   return isLoopEnteringEdge(Edge) || isLoopExitingEdge(Edge);
342e8d8bef9SDimitry Andric }
343e8d8bef9SDimitry Andric 
344e8d8bef9SDimitry Andric bool BranchProbabilityInfo::isLoopBackEdge(const LoopEdge &Edge) const {
345e8d8bef9SDimitry Andric   const auto &SrcBlock = Edge.first;
346e8d8bef9SDimitry Andric   const auto &DstBlock = Edge.second;
347e8d8bef9SDimitry Andric   return SrcBlock.belongsToSameLoop(DstBlock) &&
348e8d8bef9SDimitry Andric          ((DstBlock.getLoop() &&
349e8d8bef9SDimitry Andric            DstBlock.getLoop()->getHeader() == DstBlock.getBlock()) ||
350e8d8bef9SDimitry Andric           (DstBlock.getSccNum() != -1 &&
351e8d8bef9SDimitry Andric            SccI->isSCCHeader(DstBlock.getBlock(), DstBlock.getSccNum())));
352e8d8bef9SDimitry Andric }
353e8d8bef9SDimitry Andric 
354e8d8bef9SDimitry Andric void BranchProbabilityInfo::getLoopEnterBlocks(
355e8d8bef9SDimitry Andric     const LoopBlock &LB, SmallVectorImpl<BasicBlock *> &Enters) const {
356e8d8bef9SDimitry Andric   if (LB.getLoop()) {
357e8d8bef9SDimitry Andric     auto *Header = LB.getLoop()->getHeader();
358e8d8bef9SDimitry Andric     Enters.append(pred_begin(Header), pred_end(Header));
359e8d8bef9SDimitry Andric   } else {
360e8d8bef9SDimitry Andric     assert(LB.getSccNum() != -1 && "LB doesn't belong to any loop?");
361e8d8bef9SDimitry Andric     SccI->getSccEnterBlocks(LB.getSccNum(), Enters);
362e8d8bef9SDimitry Andric   }
363e8d8bef9SDimitry Andric }
364e8d8bef9SDimitry Andric 
365e8d8bef9SDimitry Andric void BranchProbabilityInfo::getLoopExitBlocks(
366e8d8bef9SDimitry Andric     const LoopBlock &LB, SmallVectorImpl<BasicBlock *> &Exits) const {
367e8d8bef9SDimitry Andric   if (LB.getLoop()) {
368e8d8bef9SDimitry Andric     LB.getLoop()->getExitBlocks(Exits);
369e8d8bef9SDimitry Andric   } else {
370e8d8bef9SDimitry Andric     assert(LB.getSccNum() != -1 && "LB doesn't belong to any loop?");
371e8d8bef9SDimitry Andric     SccI->getSccExitBlocks(LB.getSccNum(), Exits);
372e8d8bef9SDimitry Andric   }
3730b57cec5SDimitry Andric }
3740b57cec5SDimitry Andric 
3750b57cec5SDimitry Andric // Propagate existing explicit probabilities from either profile data or
3760b57cec5SDimitry Andric // 'expect' intrinsic processing. Examine metadata against unreachable
3770b57cec5SDimitry Andric // heuristic. The probability of the edge coming to unreachable block is
3780b57cec5SDimitry Andric // set to min of metadata and unreachable heuristic.
3790b57cec5SDimitry Andric bool BranchProbabilityInfo::calcMetadataWeights(const BasicBlock *BB) {
3800b57cec5SDimitry Andric   const Instruction *TI = BB->getTerminator();
3810b57cec5SDimitry Andric   assert(TI->getNumSuccessors() > 1 && "expected more than one successor!");
3825ffd83dbSDimitry Andric   if (!(isa<BranchInst>(TI) || isa<SwitchInst>(TI) || isa<IndirectBrInst>(TI) ||
383bdd1243dSDimitry Andric         isa<InvokeInst>(TI) || isa<CallBrInst>(TI)))
3840b57cec5SDimitry Andric     return false;
3850b57cec5SDimitry Andric 
386bdd1243dSDimitry Andric   MDNode *WeightsNode = getValidBranchWeightMDNode(*TI);
3870b57cec5SDimitry Andric   if (!WeightsNode)
3880b57cec5SDimitry Andric     return false;
3890b57cec5SDimitry Andric 
3900b57cec5SDimitry Andric   // Check that the number of successors is manageable.
3910b57cec5SDimitry Andric   assert(TI->getNumSuccessors() < UINT32_MAX && "Too many successors");
3920b57cec5SDimitry Andric 
3930b57cec5SDimitry Andric   // Build up the final weights that will be used in a temporary buffer.
3940b57cec5SDimitry Andric   // Compute the sum of all weights to later decide whether they need to
3950b57cec5SDimitry Andric   // be scaled to fit in 32 bits.
3960b57cec5SDimitry Andric   uint64_t WeightSum = 0;
3970b57cec5SDimitry Andric   SmallVector<uint32_t, 2> Weights;
3980b57cec5SDimitry Andric   SmallVector<unsigned, 2> UnreachableIdxs;
3990b57cec5SDimitry Andric   SmallVector<unsigned, 2> ReachableIdxs;
400bdd1243dSDimitry Andric 
401bdd1243dSDimitry Andric   extractBranchWeights(WeightsNode, Weights);
402bdd1243dSDimitry Andric   for (unsigned I = 0, E = Weights.size(); I != E; ++I) {
403bdd1243dSDimitry Andric     WeightSum += Weights[I];
404e8d8bef9SDimitry Andric     const LoopBlock SrcLoopBB = getLoopBlock(BB);
405bdd1243dSDimitry Andric     const LoopBlock DstLoopBB = getLoopBlock(TI->getSuccessor(I));
406e8d8bef9SDimitry Andric     auto EstimatedWeight = getEstimatedEdgeWeight({SrcLoopBB, DstLoopBB});
407e8d8bef9SDimitry Andric     if (EstimatedWeight &&
40881ad6265SDimitry Andric         *EstimatedWeight <= static_cast<uint32_t>(BlockExecWeight::UNREACHABLE))
409bdd1243dSDimitry Andric       UnreachableIdxs.push_back(I);
4100b57cec5SDimitry Andric     else
411bdd1243dSDimitry Andric       ReachableIdxs.push_back(I);
4120b57cec5SDimitry Andric   }
4130b57cec5SDimitry Andric   assert(Weights.size() == TI->getNumSuccessors() && "Checked above");
4140b57cec5SDimitry Andric 
4150b57cec5SDimitry Andric   // If the sum of weights does not fit in 32 bits, scale every weight down
4160b57cec5SDimitry Andric   // accordingly.
4170b57cec5SDimitry Andric   uint64_t ScalingFactor =
4180b57cec5SDimitry Andric       (WeightSum > UINT32_MAX) ? WeightSum / UINT32_MAX + 1 : 1;
4190b57cec5SDimitry Andric 
4200b57cec5SDimitry Andric   if (ScalingFactor > 1) {
4210b57cec5SDimitry Andric     WeightSum = 0;
4225ffd83dbSDimitry Andric     for (unsigned I = 0, E = TI->getNumSuccessors(); I != E; ++I) {
4235ffd83dbSDimitry Andric       Weights[I] /= ScalingFactor;
4245ffd83dbSDimitry Andric       WeightSum += Weights[I];
4250b57cec5SDimitry Andric     }
4260b57cec5SDimitry Andric   }
4270b57cec5SDimitry Andric   assert(WeightSum <= UINT32_MAX &&
4280b57cec5SDimitry Andric          "Expected weights to scale down to 32 bits");
4290b57cec5SDimitry Andric 
4300b57cec5SDimitry Andric   if (WeightSum == 0 || ReachableIdxs.size() == 0) {
4315ffd83dbSDimitry Andric     for (unsigned I = 0, E = TI->getNumSuccessors(); I != E; ++I)
4325ffd83dbSDimitry Andric       Weights[I] = 1;
4330b57cec5SDimitry Andric     WeightSum = TI->getNumSuccessors();
4340b57cec5SDimitry Andric   }
4350b57cec5SDimitry Andric 
4360b57cec5SDimitry Andric   // Set the probability.
4370b57cec5SDimitry Andric   SmallVector<BranchProbability, 2> BP;
4385ffd83dbSDimitry Andric   for (unsigned I = 0, E = TI->getNumSuccessors(); I != E; ++I)
4395ffd83dbSDimitry Andric     BP.push_back({ Weights[I], static_cast<uint32_t>(WeightSum) });
4400b57cec5SDimitry Andric 
4410b57cec5SDimitry Andric   // Examine the metadata against unreachable heuristic.
4420b57cec5SDimitry Andric   // If the unreachable heuristic is more strong then we use it for this edge.
4435ffd83dbSDimitry Andric   if (UnreachableIdxs.size() == 0 || ReachableIdxs.size() == 0) {
4445ffd83dbSDimitry Andric     setEdgeProbability(BB, BP);
4455ffd83dbSDimitry Andric     return true;
4465ffd83dbSDimitry Andric   }
4475ffd83dbSDimitry Andric 
4480b57cec5SDimitry Andric   auto UnreachableProb = UR_TAKEN_PROB;
4495ffd83dbSDimitry Andric   for (auto I : UnreachableIdxs)
4505ffd83dbSDimitry Andric     if (UnreachableProb < BP[I]) {
4515ffd83dbSDimitry Andric       BP[I] = UnreachableProb;
4520b57cec5SDimitry Andric     }
4530b57cec5SDimitry Andric 
4545ffd83dbSDimitry Andric   // Sum of all edge probabilities must be 1.0. If we modified the probability
4555ffd83dbSDimitry Andric   // of some edges then we must distribute the introduced difference over the
4565ffd83dbSDimitry Andric   // reachable blocks.
4575ffd83dbSDimitry Andric   //
4585ffd83dbSDimitry Andric   // Proportional distribution: the relation between probabilities of the
4595ffd83dbSDimitry Andric   // reachable edges is kept unchanged. That is for any reachable edges i and j:
4605ffd83dbSDimitry Andric   //   newBP[i] / newBP[j] == oldBP[i] / oldBP[j] =>
4615ffd83dbSDimitry Andric   //   newBP[i] / oldBP[i] == newBP[j] / oldBP[j] == K
4625ffd83dbSDimitry Andric   // Where K is independent of i,j.
4635ffd83dbSDimitry Andric   //   newBP[i] == oldBP[i] * K
4645ffd83dbSDimitry Andric   // We need to find K.
4655ffd83dbSDimitry Andric   // Make sum of all reachables of the left and right parts:
4665ffd83dbSDimitry Andric   //   sum_of_reachable(newBP) == K * sum_of_reachable(oldBP)
4675ffd83dbSDimitry Andric   // Sum of newBP must be equal to 1.0:
4685ffd83dbSDimitry Andric   //   sum_of_reachable(newBP) + sum_of_unreachable(newBP) == 1.0 =>
4695ffd83dbSDimitry Andric   //   sum_of_reachable(newBP) = 1.0 - sum_of_unreachable(newBP)
4705ffd83dbSDimitry Andric   // Where sum_of_unreachable(newBP) is what has been just changed.
4715ffd83dbSDimitry Andric   // Finally:
4725ffd83dbSDimitry Andric   //   K == sum_of_reachable(newBP) / sum_of_reachable(oldBP) =>
4735ffd83dbSDimitry Andric   //   K == (1.0 - sum_of_unreachable(newBP)) / sum_of_reachable(oldBP)
4745ffd83dbSDimitry Andric   BranchProbability NewUnreachableSum = BranchProbability::getZero();
4755ffd83dbSDimitry Andric   for (auto I : UnreachableIdxs)
4765ffd83dbSDimitry Andric     NewUnreachableSum += BP[I];
4775ffd83dbSDimitry Andric 
4785ffd83dbSDimitry Andric   BranchProbability NewReachableSum =
4795ffd83dbSDimitry Andric       BranchProbability::getOne() - NewUnreachableSum;
4805ffd83dbSDimitry Andric 
4815ffd83dbSDimitry Andric   BranchProbability OldReachableSum = BranchProbability::getZero();
4825ffd83dbSDimitry Andric   for (auto I : ReachableIdxs)
4835ffd83dbSDimitry Andric     OldReachableSum += BP[I];
4845ffd83dbSDimitry Andric 
4855ffd83dbSDimitry Andric   if (OldReachableSum != NewReachableSum) { // Anything to dsitribute?
4865ffd83dbSDimitry Andric     if (OldReachableSum.isZero()) {
4875ffd83dbSDimitry Andric       // If all oldBP[i] are zeroes then the proportional distribution results
4885ffd83dbSDimitry Andric       // in all zero probabilities and the error stays big. In this case we
4895ffd83dbSDimitry Andric       // evenly spread NewReachableSum over the reachable edges.
4905ffd83dbSDimitry Andric       BranchProbability PerEdge = NewReachableSum / ReachableIdxs.size();
4915ffd83dbSDimitry Andric       for (auto I : ReachableIdxs)
4925ffd83dbSDimitry Andric         BP[I] = PerEdge;
4935ffd83dbSDimitry Andric     } else {
4945ffd83dbSDimitry Andric       for (auto I : ReachableIdxs) {
4955ffd83dbSDimitry Andric         // We use uint64_t to avoid double rounding error of the following
4965ffd83dbSDimitry Andric         // calculation: BP[i] = BP[i] * NewReachableSum / OldReachableSum
4975ffd83dbSDimitry Andric         // The formula is taken from the private constructor
4985ffd83dbSDimitry Andric         // BranchProbability(uint32_t Numerator, uint32_t Denominator)
4995ffd83dbSDimitry Andric         uint64_t Mul = static_cast<uint64_t>(NewReachableSum.getNumerator()) *
5005ffd83dbSDimitry Andric                        BP[I].getNumerator();
5015ffd83dbSDimitry Andric         uint32_t Div = static_cast<uint32_t>(
5025ffd83dbSDimitry Andric             divideNearest(Mul, OldReachableSum.getNumerator()));
5035ffd83dbSDimitry Andric         BP[I] = BranchProbability::getRaw(Div);
5045ffd83dbSDimitry Andric       }
5050b57cec5SDimitry Andric     }
5060b57cec5SDimitry Andric   }
5070b57cec5SDimitry Andric 
5085ffd83dbSDimitry Andric   setEdgeProbability(BB, BP);
5090b57cec5SDimitry Andric 
5100b57cec5SDimitry Andric   return true;
5110b57cec5SDimitry Andric }
5120b57cec5SDimitry Andric 
5130b57cec5SDimitry Andric // Calculate Edge Weights using "Pointer Heuristics". Predict a comparison
5140b57cec5SDimitry Andric // between two pointer or pointer and NULL will fail.
5150b57cec5SDimitry Andric bool BranchProbabilityInfo::calcPointerHeuristics(const BasicBlock *BB) {
5160b57cec5SDimitry Andric   const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
5170b57cec5SDimitry Andric   if (!BI || !BI->isConditional())
5180b57cec5SDimitry Andric     return false;
5190b57cec5SDimitry Andric 
5200b57cec5SDimitry Andric   Value *Cond = BI->getCondition();
5210b57cec5SDimitry Andric   ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
5220b57cec5SDimitry Andric   if (!CI || !CI->isEquality())
5230b57cec5SDimitry Andric     return false;
5240b57cec5SDimitry Andric 
5250b57cec5SDimitry Andric   Value *LHS = CI->getOperand(0);
5260b57cec5SDimitry Andric 
5270b57cec5SDimitry Andric   if (!LHS->getType()->isPointerTy())
5280b57cec5SDimitry Andric     return false;
5290b57cec5SDimitry Andric 
5300b57cec5SDimitry Andric   assert(CI->getOperand(1)->getType()->isPointerTy());
5310b57cec5SDimitry Andric 
5324824e7fdSDimitry Andric   auto Search = PointerTable.find(CI->getPredicate());
5334824e7fdSDimitry Andric   if (Search == PointerTable.end())
5344824e7fdSDimitry Andric     return false;
5354824e7fdSDimitry Andric   setEdgeProbability(BB, Search->second);
5360b57cec5SDimitry Andric   return true;
5370b57cec5SDimitry Andric }
5380b57cec5SDimitry Andric 
5390b57cec5SDimitry Andric // Compute the unlikely successors to the block BB in the loop L, specifically
5400b57cec5SDimitry Andric // those that are unlikely because this is a loop, and add them to the
5410b57cec5SDimitry Andric // UnlikelyBlocks set.
5420b57cec5SDimitry Andric static void
5430b57cec5SDimitry Andric computeUnlikelySuccessors(const BasicBlock *BB, Loop *L,
5440b57cec5SDimitry Andric                           SmallPtrSetImpl<const BasicBlock*> &UnlikelyBlocks) {
5450b57cec5SDimitry Andric   // Sometimes in a loop we have a branch whose condition is made false by
5460b57cec5SDimitry Andric   // taking it. This is typically something like
5470b57cec5SDimitry Andric   //  int n = 0;
5480b57cec5SDimitry Andric   //  while (...) {
5490b57cec5SDimitry Andric   //    if (++n >= MAX) {
5500b57cec5SDimitry Andric   //      n = 0;
5510b57cec5SDimitry Andric   //    }
5520b57cec5SDimitry Andric   //  }
5530b57cec5SDimitry Andric   // In this sort of situation taking the branch means that at the very least it
5540b57cec5SDimitry Andric   // won't be taken again in the next iteration of the loop, so we should
5550b57cec5SDimitry Andric   // consider it less likely than a typical branch.
5560b57cec5SDimitry Andric   //
5570b57cec5SDimitry Andric   // We detect this by looking back through the graph of PHI nodes that sets the
5580b57cec5SDimitry Andric   // value that the condition depends on, and seeing if we can reach a successor
5590b57cec5SDimitry Andric   // block which can be determined to make the condition false.
5600b57cec5SDimitry Andric   //
5610b57cec5SDimitry Andric   // FIXME: We currently consider unlikely blocks to be half as likely as other
5620b57cec5SDimitry Andric   // blocks, but if we consider the example above the likelyhood is actually
5630b57cec5SDimitry Andric   // 1/MAX. We could therefore be more precise in how unlikely we consider
5640b57cec5SDimitry Andric   // blocks to be, but it would require more careful examination of the form
5650b57cec5SDimitry Andric   // of the comparison expression.
5660b57cec5SDimitry Andric   const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
5670b57cec5SDimitry Andric   if (!BI || !BI->isConditional())
5680b57cec5SDimitry Andric     return;
5690b57cec5SDimitry Andric 
5700b57cec5SDimitry Andric   // Check if the branch is based on an instruction compared with a constant
5710b57cec5SDimitry Andric   CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition());
5720b57cec5SDimitry Andric   if (!CI || !isa<Instruction>(CI->getOperand(0)) ||
5730b57cec5SDimitry Andric       !isa<Constant>(CI->getOperand(1)))
5740b57cec5SDimitry Andric     return;
5750b57cec5SDimitry Andric 
5760b57cec5SDimitry Andric   // Either the instruction must be a PHI, or a chain of operations involving
5770b57cec5SDimitry Andric   // constants that ends in a PHI which we can then collapse into a single value
5780b57cec5SDimitry Andric   // if the PHI value is known.
5790b57cec5SDimitry Andric   Instruction *CmpLHS = dyn_cast<Instruction>(CI->getOperand(0));
5800b57cec5SDimitry Andric   PHINode *CmpPHI = dyn_cast<PHINode>(CmpLHS);
5810b57cec5SDimitry Andric   Constant *CmpConst = dyn_cast<Constant>(CI->getOperand(1));
5820b57cec5SDimitry Andric   // Collect the instructions until we hit a PHI
5830b57cec5SDimitry Andric   SmallVector<BinaryOperator *, 1> InstChain;
5840b57cec5SDimitry Andric   while (!CmpPHI && CmpLHS && isa<BinaryOperator>(CmpLHS) &&
5850b57cec5SDimitry Andric          isa<Constant>(CmpLHS->getOperand(1))) {
5860b57cec5SDimitry Andric     // Stop if the chain extends outside of the loop
5870b57cec5SDimitry Andric     if (!L->contains(CmpLHS))
5880b57cec5SDimitry Andric       return;
5890b57cec5SDimitry Andric     InstChain.push_back(cast<BinaryOperator>(CmpLHS));
5900b57cec5SDimitry Andric     CmpLHS = dyn_cast<Instruction>(CmpLHS->getOperand(0));
5910b57cec5SDimitry Andric     if (CmpLHS)
5920b57cec5SDimitry Andric       CmpPHI = dyn_cast<PHINode>(CmpLHS);
5930b57cec5SDimitry Andric   }
5940b57cec5SDimitry Andric   if (!CmpPHI || !L->contains(CmpPHI))
5950b57cec5SDimitry Andric     return;
5960b57cec5SDimitry Andric 
5970b57cec5SDimitry Andric   // Trace the phi node to find all values that come from successors of BB
5980b57cec5SDimitry Andric   SmallPtrSet<PHINode*, 8> VisitedInsts;
5990b57cec5SDimitry Andric   SmallVector<PHINode*, 8> WorkList;
6000b57cec5SDimitry Andric   WorkList.push_back(CmpPHI);
6010b57cec5SDimitry Andric   VisitedInsts.insert(CmpPHI);
6020b57cec5SDimitry Andric   while (!WorkList.empty()) {
603fe6060f1SDimitry Andric     PHINode *P = WorkList.pop_back_val();
6040b57cec5SDimitry Andric     for (BasicBlock *B : P->blocks()) {
6050b57cec5SDimitry Andric       // Skip blocks that aren't part of the loop
6060b57cec5SDimitry Andric       if (!L->contains(B))
6070b57cec5SDimitry Andric         continue;
6080b57cec5SDimitry Andric       Value *V = P->getIncomingValueForBlock(B);
6090b57cec5SDimitry Andric       // If the source is a PHI add it to the work list if we haven't
6100b57cec5SDimitry Andric       // already visited it.
6110b57cec5SDimitry Andric       if (PHINode *PN = dyn_cast<PHINode>(V)) {
6120b57cec5SDimitry Andric         if (VisitedInsts.insert(PN).second)
6130b57cec5SDimitry Andric           WorkList.push_back(PN);
6140b57cec5SDimitry Andric         continue;
6150b57cec5SDimitry Andric       }
6160b57cec5SDimitry Andric       // If this incoming value is a constant and B is a successor of BB, then
6170b57cec5SDimitry Andric       // we can constant-evaluate the compare to see if it makes the branch be
6180b57cec5SDimitry Andric       // taken or not.
6190b57cec5SDimitry Andric       Constant *CmpLHSConst = dyn_cast<Constant>(V);
620e8d8bef9SDimitry Andric       if (!CmpLHSConst || !llvm::is_contained(successors(BB), B))
6210b57cec5SDimitry Andric         continue;
6220b57cec5SDimitry Andric       // First collapse InstChain
623*0fca6ea1SDimitry Andric       const DataLayout &DL = BB->getDataLayout();
6240b57cec5SDimitry Andric       for (Instruction *I : llvm::reverse(InstChain)) {
625753f127fSDimitry Andric         CmpLHSConst = ConstantFoldBinaryOpOperands(
626753f127fSDimitry Andric             I->getOpcode(), CmpLHSConst, cast<Constant>(I->getOperand(1)), DL);
6270b57cec5SDimitry Andric         if (!CmpLHSConst)
6280b57cec5SDimitry Andric           break;
6290b57cec5SDimitry Andric       }
6300b57cec5SDimitry Andric       if (!CmpLHSConst)
6310b57cec5SDimitry Andric         continue;
6320b57cec5SDimitry Andric       // Now constant-evaluate the compare
633*0fca6ea1SDimitry Andric       Constant *Result = ConstantFoldCompareInstOperands(
634*0fca6ea1SDimitry Andric           CI->getPredicate(), CmpLHSConst, CmpConst, DL);
6350b57cec5SDimitry Andric       // If the result means we don't branch to the block then that block is
6360b57cec5SDimitry Andric       // unlikely.
6370b57cec5SDimitry Andric       if (Result &&
6380b57cec5SDimitry Andric           ((Result->isZeroValue() && B == BI->getSuccessor(0)) ||
6390b57cec5SDimitry Andric            (Result->isOneValue() && B == BI->getSuccessor(1))))
6400b57cec5SDimitry Andric         UnlikelyBlocks.insert(B);
6410b57cec5SDimitry Andric     }
6420b57cec5SDimitry Andric   }
6430b57cec5SDimitry Andric }
6440b57cec5SDimitry Andric 
645bdd1243dSDimitry Andric std::optional<uint32_t>
646e8d8bef9SDimitry Andric BranchProbabilityInfo::getEstimatedBlockWeight(const BasicBlock *BB) const {
647e8d8bef9SDimitry Andric   auto WeightIt = EstimatedBlockWeight.find(BB);
648e8d8bef9SDimitry Andric   if (WeightIt == EstimatedBlockWeight.end())
649bdd1243dSDimitry Andric     return std::nullopt;
650e8d8bef9SDimitry Andric   return WeightIt->second;
6510b57cec5SDimitry Andric }
6520b57cec5SDimitry Andric 
653bdd1243dSDimitry Andric std::optional<uint32_t>
654e8d8bef9SDimitry Andric BranchProbabilityInfo::getEstimatedLoopWeight(const LoopData &L) const {
655e8d8bef9SDimitry Andric   auto WeightIt = EstimatedLoopWeight.find(L);
656e8d8bef9SDimitry Andric   if (WeightIt == EstimatedLoopWeight.end())
657bdd1243dSDimitry Andric     return std::nullopt;
658e8d8bef9SDimitry Andric   return WeightIt->second;
659e8d8bef9SDimitry Andric }
660e8d8bef9SDimitry Andric 
661bdd1243dSDimitry Andric std::optional<uint32_t>
662e8d8bef9SDimitry Andric BranchProbabilityInfo::getEstimatedEdgeWeight(const LoopEdge &Edge) const {
663e8d8bef9SDimitry Andric   // For edges entering a loop take weight of a loop rather than an individual
664e8d8bef9SDimitry Andric   // block in the loop.
665e8d8bef9SDimitry Andric   return isLoopEnteringEdge(Edge)
666e8d8bef9SDimitry Andric              ? getEstimatedLoopWeight(Edge.second.getLoopData())
667e8d8bef9SDimitry Andric              : getEstimatedBlockWeight(Edge.second.getBlock());
668e8d8bef9SDimitry Andric }
669e8d8bef9SDimitry Andric 
670e8d8bef9SDimitry Andric template <class IterT>
671bdd1243dSDimitry Andric std::optional<uint32_t> BranchProbabilityInfo::getMaxEstimatedEdgeWeight(
672e8d8bef9SDimitry Andric     const LoopBlock &SrcLoopBB, iterator_range<IterT> Successors) const {
673e8d8bef9SDimitry Andric   SmallVector<uint32_t, 4> Weights;
674bdd1243dSDimitry Andric   std::optional<uint32_t> MaxWeight;
675e8d8bef9SDimitry Andric   for (const BasicBlock *DstBB : Successors) {
676e8d8bef9SDimitry Andric     const LoopBlock DstLoopBB = getLoopBlock(DstBB);
677e8d8bef9SDimitry Andric     auto Weight = getEstimatedEdgeWeight({SrcLoopBB, DstLoopBB});
678e8d8bef9SDimitry Andric 
679e8d8bef9SDimitry Andric     if (!Weight)
680bdd1243dSDimitry Andric       return std::nullopt;
681e8d8bef9SDimitry Andric 
68281ad6265SDimitry Andric     if (!MaxWeight || *MaxWeight < *Weight)
683e8d8bef9SDimitry Andric       MaxWeight = Weight;
684e8d8bef9SDimitry Andric   }
685e8d8bef9SDimitry Andric 
686e8d8bef9SDimitry Andric   return MaxWeight;
687e8d8bef9SDimitry Andric }
688e8d8bef9SDimitry Andric 
689e8d8bef9SDimitry Andric // Updates \p LoopBB's weight and returns true. If \p LoopBB has already
690e8d8bef9SDimitry Andric // an associated weight it is unchanged and false is returned.
691e8d8bef9SDimitry Andric //
692e8d8bef9SDimitry Andric // Please note by the algorithm the weight is not expected to change once set
693e8d8bef9SDimitry Andric // thus 'false' status is used to track visited blocks.
694e8d8bef9SDimitry Andric bool BranchProbabilityInfo::updateEstimatedBlockWeight(
695e8d8bef9SDimitry Andric     LoopBlock &LoopBB, uint32_t BBWeight,
696e8d8bef9SDimitry Andric     SmallVectorImpl<BasicBlock *> &BlockWorkList,
697e8d8bef9SDimitry Andric     SmallVectorImpl<LoopBlock> &LoopWorkList) {
698e8d8bef9SDimitry Andric   BasicBlock *BB = LoopBB.getBlock();
699e8d8bef9SDimitry Andric 
700e8d8bef9SDimitry Andric   // In general, weight is assigned to a block when it has final value and
701e8d8bef9SDimitry Andric   // can't/shouldn't be changed.  However, there are cases when a block
702e8d8bef9SDimitry Andric   // inherently has several (possibly "contradicting") weights. For example,
703e8d8bef9SDimitry Andric   // "unwind" block may also contain "cold" call. In that case the first
704e8d8bef9SDimitry Andric   // set weight is favored and all consequent weights are ignored.
705e8d8bef9SDimitry Andric   if (!EstimatedBlockWeight.insert({BB, BBWeight}).second)
706e8d8bef9SDimitry Andric     return false;
707e8d8bef9SDimitry Andric 
708e8d8bef9SDimitry Andric   for (BasicBlock *PredBlock : predecessors(BB)) {
709e8d8bef9SDimitry Andric     LoopBlock PredLoop = getLoopBlock(PredBlock);
710e8d8bef9SDimitry Andric     // Add affected block/loop to a working list.
711e8d8bef9SDimitry Andric     if (isLoopExitingEdge({PredLoop, LoopBB})) {
712e8d8bef9SDimitry Andric       if (!EstimatedLoopWeight.count(PredLoop.getLoopData()))
713e8d8bef9SDimitry Andric         LoopWorkList.push_back(PredLoop);
714e8d8bef9SDimitry Andric     } else if (!EstimatedBlockWeight.count(PredBlock))
715e8d8bef9SDimitry Andric       BlockWorkList.push_back(PredBlock);
716e8d8bef9SDimitry Andric   }
717e8d8bef9SDimitry Andric   return true;
718e8d8bef9SDimitry Andric }
719e8d8bef9SDimitry Andric 
720e8d8bef9SDimitry Andric // Starting from \p BB traverse through dominator blocks and assign \p BBWeight
721e8d8bef9SDimitry Andric // to all such blocks that are post dominated by \BB. In other words to all
722e8d8bef9SDimitry Andric // blocks that the one is executed if and only if another one is executed.
723e8d8bef9SDimitry Andric // Importantly, we skip loops here for two reasons. First weights of blocks in
724e8d8bef9SDimitry Andric // a loop should be scaled by trip count (yet possibly unknown). Second there is
725e8d8bef9SDimitry Andric // no any value in doing that because that doesn't give any additional
726e8d8bef9SDimitry Andric // information regarding distribution of probabilities inside the loop.
727e8d8bef9SDimitry Andric // Exception is loop 'enter' and 'exit' edges that are handled in a special way
728e8d8bef9SDimitry Andric // at calcEstimatedHeuristics.
729e8d8bef9SDimitry Andric //
730e8d8bef9SDimitry Andric // In addition, \p WorkList is populated with basic blocks if at leas one
731e8d8bef9SDimitry Andric // successor has updated estimated weight.
732e8d8bef9SDimitry Andric void BranchProbabilityInfo::propagateEstimatedBlockWeight(
733e8d8bef9SDimitry Andric     const LoopBlock &LoopBB, DominatorTree *DT, PostDominatorTree *PDT,
734e8d8bef9SDimitry Andric     uint32_t BBWeight, SmallVectorImpl<BasicBlock *> &BlockWorkList,
735e8d8bef9SDimitry Andric     SmallVectorImpl<LoopBlock> &LoopWorkList) {
736e8d8bef9SDimitry Andric   const BasicBlock *BB = LoopBB.getBlock();
737e8d8bef9SDimitry Andric   const auto *DTStartNode = DT->getNode(BB);
738e8d8bef9SDimitry Andric   const auto *PDTStartNode = PDT->getNode(BB);
739e8d8bef9SDimitry Andric 
740e8d8bef9SDimitry Andric   // TODO: Consider propagating weight down the domination line as well.
741e8d8bef9SDimitry Andric   for (const auto *DTNode = DTStartNode; DTNode != nullptr;
742e8d8bef9SDimitry Andric        DTNode = DTNode->getIDom()) {
743e8d8bef9SDimitry Andric     auto *DomBB = DTNode->getBlock();
744e8d8bef9SDimitry Andric     // Consider blocks which lie on one 'line'.
745e8d8bef9SDimitry Andric     if (!PDT->dominates(PDTStartNode, PDT->getNode(DomBB)))
746e8d8bef9SDimitry Andric       // If BB doesn't post dominate DomBB it will not post dominate dominators
747e8d8bef9SDimitry Andric       // of DomBB as well.
748e8d8bef9SDimitry Andric       break;
749e8d8bef9SDimitry Andric 
750e8d8bef9SDimitry Andric     LoopBlock DomLoopBB = getLoopBlock(DomBB);
751e8d8bef9SDimitry Andric     const LoopEdge Edge{DomLoopBB, LoopBB};
752e8d8bef9SDimitry Andric     // Don't propagate weight to blocks belonging to different loops.
753e8d8bef9SDimitry Andric     if (!isLoopEnteringExitingEdge(Edge)) {
754e8d8bef9SDimitry Andric       if (!updateEstimatedBlockWeight(DomLoopBB, BBWeight, BlockWorkList,
755e8d8bef9SDimitry Andric                                       LoopWorkList))
756e8d8bef9SDimitry Andric         // If DomBB has weight set then all it's predecessors are already
757e8d8bef9SDimitry Andric         // processed (since we propagate weight up to the top of IR each time).
758e8d8bef9SDimitry Andric         break;
759e8d8bef9SDimitry Andric     } else if (isLoopExitingEdge(Edge)) {
760e8d8bef9SDimitry Andric       LoopWorkList.push_back(DomLoopBB);
761e8d8bef9SDimitry Andric     }
762e8d8bef9SDimitry Andric   }
763e8d8bef9SDimitry Andric }
764e8d8bef9SDimitry Andric 
765bdd1243dSDimitry Andric std::optional<uint32_t>
766bdd1243dSDimitry Andric BranchProbabilityInfo::getInitialEstimatedBlockWeight(const BasicBlock *BB) {
767e8d8bef9SDimitry Andric   // Returns true if \p BB has call marked with "NoReturn" attribute.
768e8d8bef9SDimitry Andric   auto hasNoReturn = [&](const BasicBlock *BB) {
769e8d8bef9SDimitry Andric     for (const auto &I : reverse(*BB))
770e8d8bef9SDimitry Andric       if (const CallInst *CI = dyn_cast<CallInst>(&I))
771e8d8bef9SDimitry Andric         if (CI->hasFnAttr(Attribute::NoReturn))
772e8d8bef9SDimitry Andric           return true;
773e8d8bef9SDimitry Andric 
774e8d8bef9SDimitry Andric     return false;
775e8d8bef9SDimitry Andric   };
776e8d8bef9SDimitry Andric 
777e8d8bef9SDimitry Andric   // Important note regarding the order of checks. They are ordered by weight
778e8d8bef9SDimitry Andric   // from lowest to highest. Doing that allows to avoid "unstable" results
779e8d8bef9SDimitry Andric   // when several conditions heuristics can be applied simultaneously.
780e8d8bef9SDimitry Andric   if (isa<UnreachableInst>(BB->getTerminator()) ||
781e8d8bef9SDimitry Andric       // If this block is terminated by a call to
782e8d8bef9SDimitry Andric       // @llvm.experimental.deoptimize then treat it like an unreachable
783e8d8bef9SDimitry Andric       // since it is expected to practically never execute.
784e8d8bef9SDimitry Andric       // TODO: Should we actually treat as never returning call?
785e8d8bef9SDimitry Andric       BB->getTerminatingDeoptimizeCall())
786e8d8bef9SDimitry Andric     return hasNoReturn(BB)
787e8d8bef9SDimitry Andric                ? static_cast<uint32_t>(BlockExecWeight::NORETURN)
788e8d8bef9SDimitry Andric                : static_cast<uint32_t>(BlockExecWeight::UNREACHABLE);
789e8d8bef9SDimitry Andric 
790*0fca6ea1SDimitry Andric   // Check if the block is an exception handling block.
791*0fca6ea1SDimitry Andric   if (BB->isEHPad())
792e8d8bef9SDimitry Andric     return static_cast<uint32_t>(BlockExecWeight::UNWIND);
793e8d8bef9SDimitry Andric 
794e8d8bef9SDimitry Andric   // Check if the block contains 'cold' call.
795e8d8bef9SDimitry Andric   for (const auto &I : *BB)
796e8d8bef9SDimitry Andric     if (const CallInst *CI = dyn_cast<CallInst>(&I))
797e8d8bef9SDimitry Andric       if (CI->hasFnAttr(Attribute::Cold))
798e8d8bef9SDimitry Andric         return static_cast<uint32_t>(BlockExecWeight::COLD);
799e8d8bef9SDimitry Andric 
800bdd1243dSDimitry Andric   return std::nullopt;
801e8d8bef9SDimitry Andric }
802e8d8bef9SDimitry Andric 
803e8d8bef9SDimitry Andric // Does RPO traversal over all blocks in \p F and assigns weights to
804e8d8bef9SDimitry Andric // 'unreachable', 'noreturn', 'cold', 'unwind' blocks. In addition it does its
805e8d8bef9SDimitry Andric // best to propagate the weight to up/down the IR.
806e8d8bef9SDimitry Andric void BranchProbabilityInfo::computeEestimateBlockWeight(
807e8d8bef9SDimitry Andric     const Function &F, DominatorTree *DT, PostDominatorTree *PDT) {
808e8d8bef9SDimitry Andric   SmallVector<BasicBlock *, 8> BlockWorkList;
809e8d8bef9SDimitry Andric   SmallVector<LoopBlock, 8> LoopWorkList;
810*0fca6ea1SDimitry Andric   SmallDenseMap<LoopData, SmallVector<BasicBlock *, 4>> LoopExitBlocks;
811e8d8bef9SDimitry Andric 
812e8d8bef9SDimitry Andric   // By doing RPO we make sure that all predecessors already have weights
813e8d8bef9SDimitry Andric   // calculated before visiting theirs successors.
814e8d8bef9SDimitry Andric   ReversePostOrderTraversal<const Function *> RPOT(&F);
815e8d8bef9SDimitry Andric   for (const auto *BB : RPOT)
816e8d8bef9SDimitry Andric     if (auto BBWeight = getInitialEstimatedBlockWeight(BB))
817e8d8bef9SDimitry Andric       // If we were able to find estimated weight for the block set it to this
818e8d8bef9SDimitry Andric       // block and propagate up the IR.
819bdd1243dSDimitry Andric       propagateEstimatedBlockWeight(getLoopBlock(BB), DT, PDT, *BBWeight,
820753f127fSDimitry Andric                                     BlockWorkList, LoopWorkList);
821e8d8bef9SDimitry Andric 
822e8d8bef9SDimitry Andric   // BlockWorklist/LoopWorkList contains blocks/loops with at least one
823e8d8bef9SDimitry Andric   // successor/exit having estimated weight. Try to propagate weight to such
824e8d8bef9SDimitry Andric   // blocks/loops from successors/exits.
825e8d8bef9SDimitry Andric   // Process loops and blocks. Order is not important.
826e8d8bef9SDimitry Andric   do {
827e8d8bef9SDimitry Andric     while (!LoopWorkList.empty()) {
828e8d8bef9SDimitry Andric       const LoopBlock LoopBB = LoopWorkList.pop_back_val();
829*0fca6ea1SDimitry Andric       const LoopData LD = LoopBB.getLoopData();
830*0fca6ea1SDimitry Andric       if (EstimatedLoopWeight.count(LD))
831e8d8bef9SDimitry Andric         continue;
832e8d8bef9SDimitry Andric 
833*0fca6ea1SDimitry Andric       auto Res = LoopExitBlocks.try_emplace(LD);
834*0fca6ea1SDimitry Andric       SmallVectorImpl<BasicBlock *> &Exits = Res.first->second;
835*0fca6ea1SDimitry Andric       if (Res.second)
836e8d8bef9SDimitry Andric         getLoopExitBlocks(LoopBB, Exits);
837e8d8bef9SDimitry Andric       auto LoopWeight = getMaxEstimatedEdgeWeight(
838e8d8bef9SDimitry Andric           LoopBB, make_range(Exits.begin(), Exits.end()));
839e8d8bef9SDimitry Andric 
840e8d8bef9SDimitry Andric       if (LoopWeight) {
841e8d8bef9SDimitry Andric         // If we never exit the loop then we can enter it once at maximum.
842e8d8bef9SDimitry Andric         if (LoopWeight <= static_cast<uint32_t>(BlockExecWeight::UNREACHABLE))
843e8d8bef9SDimitry Andric           LoopWeight = static_cast<uint32_t>(BlockExecWeight::LOWEST_NON_ZERO);
844e8d8bef9SDimitry Andric 
845*0fca6ea1SDimitry Andric         EstimatedLoopWeight.insert({LD, *LoopWeight});
846e8d8bef9SDimitry Andric         // Add all blocks entering the loop into working list.
847e8d8bef9SDimitry Andric         getLoopEnterBlocks(LoopBB, BlockWorkList);
848e8d8bef9SDimitry Andric       }
849e8d8bef9SDimitry Andric     }
850e8d8bef9SDimitry Andric 
851e8d8bef9SDimitry Andric     while (!BlockWorkList.empty()) {
852e8d8bef9SDimitry Andric       // We can reach here only if BlockWorkList is not empty.
853e8d8bef9SDimitry Andric       const BasicBlock *BB = BlockWorkList.pop_back_val();
854e8d8bef9SDimitry Andric       if (EstimatedBlockWeight.count(BB))
855e8d8bef9SDimitry Andric         continue;
856e8d8bef9SDimitry Andric 
857e8d8bef9SDimitry Andric       // We take maximum over all weights of successors. In other words we take
858e8d8bef9SDimitry Andric       // weight of "hot" path. In theory we can probably find a better function
859e8d8bef9SDimitry Andric       // which gives higher accuracy results (comparing to "maximum") but I
860e8d8bef9SDimitry Andric       // can't
861e8d8bef9SDimitry Andric       // think of any right now. And I doubt it will make any difference in
862e8d8bef9SDimitry Andric       // practice.
863e8d8bef9SDimitry Andric       const LoopBlock LoopBB = getLoopBlock(BB);
864e8d8bef9SDimitry Andric       auto MaxWeight = getMaxEstimatedEdgeWeight(LoopBB, successors(BB));
865e8d8bef9SDimitry Andric 
866e8d8bef9SDimitry Andric       if (MaxWeight)
86781ad6265SDimitry Andric         propagateEstimatedBlockWeight(LoopBB, DT, PDT, *MaxWeight,
868e8d8bef9SDimitry Andric                                       BlockWorkList, LoopWorkList);
869e8d8bef9SDimitry Andric     }
870e8d8bef9SDimitry Andric   } while (!BlockWorkList.empty() || !LoopWorkList.empty());
871e8d8bef9SDimitry Andric }
872e8d8bef9SDimitry Andric 
873e8d8bef9SDimitry Andric // Calculate edge probabilities based on block's estimated weight.
874e8d8bef9SDimitry Andric // Note that gathered weights were not scaled for loops. Thus edges entering
875e8d8bef9SDimitry Andric // and exiting loops requires special processing.
876e8d8bef9SDimitry Andric bool BranchProbabilityInfo::calcEstimatedHeuristics(const BasicBlock *BB) {
877e8d8bef9SDimitry Andric   assert(BB->getTerminator()->getNumSuccessors() > 1 &&
878e8d8bef9SDimitry Andric          "expected more than one successor!");
879e8d8bef9SDimitry Andric 
880e8d8bef9SDimitry Andric   const LoopBlock LoopBB = getLoopBlock(BB);
881e8d8bef9SDimitry Andric 
8820b57cec5SDimitry Andric   SmallPtrSet<const BasicBlock *, 8> UnlikelyBlocks;
883e8d8bef9SDimitry Andric   uint32_t TC = LBH_TAKEN_WEIGHT / LBH_NONTAKEN_WEIGHT;
884e8d8bef9SDimitry Andric   if (LoopBB.getLoop())
885e8d8bef9SDimitry Andric     computeUnlikelySuccessors(BB, LoopBB.getLoop(), UnlikelyBlocks);
8860b57cec5SDimitry Andric 
887e8d8bef9SDimitry Andric   // Changed to 'true' if at least one successor has estimated weight.
888e8d8bef9SDimitry Andric   bool FoundEstimatedWeight = false;
889e8d8bef9SDimitry Andric   SmallVector<uint32_t, 4> SuccWeights;
890e8d8bef9SDimitry Andric   uint64_t TotalWeight = 0;
891e8d8bef9SDimitry Andric   // Go over all successors of BB and put their weights into SuccWeights.
892fe6060f1SDimitry Andric   for (const BasicBlock *SuccBB : successors(BB)) {
893bdd1243dSDimitry Andric     std::optional<uint32_t> Weight;
894e8d8bef9SDimitry Andric     const LoopBlock SuccLoopBB = getLoopBlock(SuccBB);
895e8d8bef9SDimitry Andric     const LoopEdge Edge{LoopBB, SuccLoopBB};
896e8d8bef9SDimitry Andric 
897e8d8bef9SDimitry Andric     Weight = getEstimatedEdgeWeight(Edge);
898e8d8bef9SDimitry Andric 
899e8d8bef9SDimitry Andric     if (isLoopExitingEdge(Edge) &&
900e8d8bef9SDimitry Andric         // Avoid adjustment of ZERO weight since it should remain unchanged.
901e8d8bef9SDimitry Andric         Weight != static_cast<uint32_t>(BlockExecWeight::ZERO)) {
902e8d8bef9SDimitry Andric       // Scale down loop exiting weight by trip count.
903e8d8bef9SDimitry Andric       Weight = std::max(
904e8d8bef9SDimitry Andric           static_cast<uint32_t>(BlockExecWeight::LOWEST_NON_ZERO),
90581ad6265SDimitry Andric           Weight.value_or(static_cast<uint32_t>(BlockExecWeight::DEFAULT)) /
906e8d8bef9SDimitry Andric               TC);
9070b57cec5SDimitry Andric     }
908e8d8bef9SDimitry Andric     bool IsUnlikelyEdge = LoopBB.getLoop() && UnlikelyBlocks.contains(SuccBB);
909e8d8bef9SDimitry Andric     if (IsUnlikelyEdge &&
910e8d8bef9SDimitry Andric         // Avoid adjustment of ZERO weight since it should remain unchanged.
911e8d8bef9SDimitry Andric         Weight != static_cast<uint32_t>(BlockExecWeight::ZERO)) {
912e8d8bef9SDimitry Andric       // 'Unlikely' blocks have twice lower weight.
913e8d8bef9SDimitry Andric       Weight = std::max(
914e8d8bef9SDimitry Andric           static_cast<uint32_t>(BlockExecWeight::LOWEST_NON_ZERO),
91581ad6265SDimitry Andric           Weight.value_or(static_cast<uint32_t>(BlockExecWeight::DEFAULT)) / 2);
9160b57cec5SDimitry Andric     }
9170b57cec5SDimitry Andric 
918e8d8bef9SDimitry Andric     if (Weight)
919e8d8bef9SDimitry Andric       FoundEstimatedWeight = true;
920e8d8bef9SDimitry Andric 
921e8d8bef9SDimitry Andric     auto WeightVal =
92281ad6265SDimitry Andric         Weight.value_or(static_cast<uint32_t>(BlockExecWeight::DEFAULT));
923e8d8bef9SDimitry Andric     TotalWeight += WeightVal;
924e8d8bef9SDimitry Andric     SuccWeights.push_back(WeightVal);
925e8d8bef9SDimitry Andric   }
926e8d8bef9SDimitry Andric 
927e8d8bef9SDimitry Andric   // If non of blocks have estimated weight bail out.
928e8d8bef9SDimitry Andric   // If TotalWeight is 0 that means weight of each successor is 0 as well and
929e8d8bef9SDimitry Andric   // equally likely. Bail out early to not deal with devision by zero.
930e8d8bef9SDimitry Andric   if (!FoundEstimatedWeight || TotalWeight == 0)
9310b57cec5SDimitry Andric     return false;
9320b57cec5SDimitry Andric 
933e8d8bef9SDimitry Andric   assert(SuccWeights.size() == succ_size(BB) && "Missed successor?");
934e8d8bef9SDimitry Andric   const unsigned SuccCount = SuccWeights.size();
9350b57cec5SDimitry Andric 
936e8d8bef9SDimitry Andric   // If the sum of weights does not fit in 32 bits, scale every weight down
937e8d8bef9SDimitry Andric   // accordingly.
938e8d8bef9SDimitry Andric   if (TotalWeight > UINT32_MAX) {
939e8d8bef9SDimitry Andric     uint64_t ScalingFactor = TotalWeight / UINT32_MAX + 1;
940e8d8bef9SDimitry Andric     TotalWeight = 0;
941e8d8bef9SDimitry Andric     for (unsigned Idx = 0; Idx < SuccCount; ++Idx) {
942e8d8bef9SDimitry Andric       SuccWeights[Idx] /= ScalingFactor;
943e8d8bef9SDimitry Andric       if (SuccWeights[Idx] == static_cast<uint32_t>(BlockExecWeight::ZERO))
944e8d8bef9SDimitry Andric         SuccWeights[Idx] =
945e8d8bef9SDimitry Andric             static_cast<uint32_t>(BlockExecWeight::LOWEST_NON_ZERO);
946e8d8bef9SDimitry Andric       TotalWeight += SuccWeights[Idx];
947e8d8bef9SDimitry Andric     }
948e8d8bef9SDimitry Andric     assert(TotalWeight <= UINT32_MAX && "Total weight overflows");
949e8d8bef9SDimitry Andric   }
950e8d8bef9SDimitry Andric 
951e8d8bef9SDimitry Andric   // Finally set probabilities to edges according to estimated block weights.
9525ffd83dbSDimitry Andric   SmallVector<BranchProbability, 4> EdgeProbabilities(
953e8d8bef9SDimitry Andric       SuccCount, BranchProbability::getUnknown());
9540b57cec5SDimitry Andric 
955e8d8bef9SDimitry Andric   for (unsigned Idx = 0; Idx < SuccCount; ++Idx) {
956e8d8bef9SDimitry Andric     EdgeProbabilities[Idx] =
957e8d8bef9SDimitry Andric         BranchProbability(SuccWeights[Idx], (uint32_t)TotalWeight);
9580b57cec5SDimitry Andric   }
9595ffd83dbSDimitry Andric   setEdgeProbability(BB, EdgeProbabilities);
9600b57cec5SDimitry Andric   return true;
9610b57cec5SDimitry Andric }
9620b57cec5SDimitry Andric 
9630b57cec5SDimitry Andric bool BranchProbabilityInfo::calcZeroHeuristics(const BasicBlock *BB,
9640b57cec5SDimitry Andric                                                const TargetLibraryInfo *TLI) {
9650b57cec5SDimitry Andric   const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
9660b57cec5SDimitry Andric   if (!BI || !BI->isConditional())
9670b57cec5SDimitry Andric     return false;
9680b57cec5SDimitry Andric 
9690b57cec5SDimitry Andric   Value *Cond = BI->getCondition();
9700b57cec5SDimitry Andric   ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
9710b57cec5SDimitry Andric   if (!CI)
9720b57cec5SDimitry Andric     return false;
9730b57cec5SDimitry Andric 
9740b57cec5SDimitry Andric   auto GetConstantInt = [](Value *V) {
9750b57cec5SDimitry Andric     if (auto *I = dyn_cast<BitCastInst>(V))
9760b57cec5SDimitry Andric       return dyn_cast<ConstantInt>(I->getOperand(0));
9770b57cec5SDimitry Andric     return dyn_cast<ConstantInt>(V);
9780b57cec5SDimitry Andric   };
9790b57cec5SDimitry Andric 
9800b57cec5SDimitry Andric   Value *RHS = CI->getOperand(1);
9810b57cec5SDimitry Andric   ConstantInt *CV = GetConstantInt(RHS);
9820b57cec5SDimitry Andric   if (!CV)
9830b57cec5SDimitry Andric     return false;
9840b57cec5SDimitry Andric 
9850b57cec5SDimitry Andric   // If the LHS is the result of AND'ing a value with a single bit bitmask,
9860b57cec5SDimitry Andric   // we don't have information about probabilities.
9870b57cec5SDimitry Andric   if (Instruction *LHS = dyn_cast<Instruction>(CI->getOperand(0)))
9880b57cec5SDimitry Andric     if (LHS->getOpcode() == Instruction::And)
989e8d8bef9SDimitry Andric       if (ConstantInt *AndRHS = GetConstantInt(LHS->getOperand(1)))
9900b57cec5SDimitry Andric         if (AndRHS->getValue().isPowerOf2())
9910b57cec5SDimitry Andric           return false;
9920b57cec5SDimitry Andric 
9930b57cec5SDimitry Andric   // Check if the LHS is the return value of a library function
9940b57cec5SDimitry Andric   LibFunc Func = NumLibFuncs;
9950b57cec5SDimitry Andric   if (TLI)
9960b57cec5SDimitry Andric     if (CallInst *Call = dyn_cast<CallInst>(CI->getOperand(0)))
9970b57cec5SDimitry Andric       if (Function *CalledFn = Call->getCalledFunction())
9980b57cec5SDimitry Andric         TLI->getLibFunc(*CalledFn, Func);
9990b57cec5SDimitry Andric 
10004824e7fdSDimitry Andric   ProbabilityTable::const_iterator Search;
10010b57cec5SDimitry Andric   if (Func == LibFunc_strcasecmp ||
10020b57cec5SDimitry Andric       Func == LibFunc_strcmp ||
10030b57cec5SDimitry Andric       Func == LibFunc_strncasecmp ||
10040b57cec5SDimitry Andric       Func == LibFunc_strncmp ||
1005e8d8bef9SDimitry Andric       Func == LibFunc_memcmp ||
1006e8d8bef9SDimitry Andric       Func == LibFunc_bcmp) {
10074824e7fdSDimitry Andric     Search = ICmpWithLibCallTable.find(CI->getPredicate());
10084824e7fdSDimitry Andric     if (Search == ICmpWithLibCallTable.end())
10090b57cec5SDimitry Andric       return false;
10100b57cec5SDimitry Andric   } else if (CV->isZero()) {
10114824e7fdSDimitry Andric     Search = ICmpWithZeroTable.find(CI->getPredicate());
10124824e7fdSDimitry Andric     if (Search == ICmpWithZeroTable.end())
10130b57cec5SDimitry Andric       return false;
10144824e7fdSDimitry Andric   } else if (CV->isOne()) {
10154824e7fdSDimitry Andric     Search = ICmpWithOneTable.find(CI->getPredicate());
10164824e7fdSDimitry Andric     if (Search == ICmpWithOneTable.end())
10174824e7fdSDimitry Andric       return false;
10180b57cec5SDimitry Andric   } else if (CV->isMinusOne()) {
10194824e7fdSDimitry Andric     Search = ICmpWithMinusOneTable.find(CI->getPredicate());
10204824e7fdSDimitry Andric     if (Search == ICmpWithMinusOneTable.end())
10210b57cec5SDimitry Andric       return false;
10220b57cec5SDimitry Andric   } else {
10230b57cec5SDimitry Andric     return false;
10240b57cec5SDimitry Andric   }
10250b57cec5SDimitry Andric 
10264824e7fdSDimitry Andric   setEdgeProbability(BB, Search->second);
10270b57cec5SDimitry Andric   return true;
10280b57cec5SDimitry Andric }
10290b57cec5SDimitry Andric 
10300b57cec5SDimitry Andric bool BranchProbabilityInfo::calcFloatingPointHeuristics(const BasicBlock *BB) {
10310b57cec5SDimitry Andric   const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
10320b57cec5SDimitry Andric   if (!BI || !BI->isConditional())
10330b57cec5SDimitry Andric     return false;
10340b57cec5SDimitry Andric 
10350b57cec5SDimitry Andric   Value *Cond = BI->getCondition();
10360b57cec5SDimitry Andric   FCmpInst *FCmp = dyn_cast<FCmpInst>(Cond);
10370b57cec5SDimitry Andric   if (!FCmp)
10380b57cec5SDimitry Andric     return false;
10390b57cec5SDimitry Andric 
10404824e7fdSDimitry Andric   ProbabilityList ProbList;
10410b57cec5SDimitry Andric   if (FCmp->isEquality()) {
10424824e7fdSDimitry Andric     ProbList = !FCmp->isTrueWhenEqual() ?
10430b57cec5SDimitry Andric       // f1 == f2 -> Unlikely
10444824e7fdSDimitry Andric       ProbabilityList({FPTakenProb, FPUntakenProb}) :
10450b57cec5SDimitry Andric       // f1 != f2 -> Likely
10464824e7fdSDimitry Andric       ProbabilityList({FPUntakenProb, FPTakenProb});
10470b57cec5SDimitry Andric   } else {
10484824e7fdSDimitry Andric     auto Search = FCmpTable.find(FCmp->getPredicate());
10494824e7fdSDimitry Andric     if (Search == FCmpTable.end())
10500b57cec5SDimitry Andric       return false;
10514824e7fdSDimitry Andric     ProbList = Search->second;
10520b57cec5SDimitry Andric   }
10530b57cec5SDimitry Andric 
10544824e7fdSDimitry Andric   setEdgeProbability(BB, ProbList);
10550b57cec5SDimitry Andric   return true;
10560b57cec5SDimitry Andric }
10570b57cec5SDimitry Andric 
10580b57cec5SDimitry Andric void BranchProbabilityInfo::releaseMemory() {
10590b57cec5SDimitry Andric   Probs.clear();
10605ffd83dbSDimitry Andric   Handles.clear();
10615ffd83dbSDimitry Andric }
10625ffd83dbSDimitry Andric 
10635ffd83dbSDimitry Andric bool BranchProbabilityInfo::invalidate(Function &, const PreservedAnalyses &PA,
10645ffd83dbSDimitry Andric                                        FunctionAnalysisManager::Invalidator &) {
10655ffd83dbSDimitry Andric   // Check whether the analysis, all analyses on functions, or the function's
10665ffd83dbSDimitry Andric   // CFG have been preserved.
10675ffd83dbSDimitry Andric   auto PAC = PA.getChecker<BranchProbabilityAnalysis>();
10685ffd83dbSDimitry Andric   return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
10695ffd83dbSDimitry Andric            PAC.preservedSet<CFGAnalyses>());
10700b57cec5SDimitry Andric }
10710b57cec5SDimitry Andric 
10720b57cec5SDimitry Andric void BranchProbabilityInfo::print(raw_ostream &OS) const {
10730b57cec5SDimitry Andric   OS << "---- Branch Probabilities ----\n";
10740b57cec5SDimitry Andric   // We print the probabilities from the last function the analysis ran over,
10750b57cec5SDimitry Andric   // or the function it is currently running over.
10760b57cec5SDimitry Andric   assert(LastF && "Cannot print prior to running over a function");
10770b57cec5SDimitry Andric   for (const auto &BI : *LastF) {
1078fe6060f1SDimitry Andric     for (const BasicBlock *Succ : successors(&BI))
1079fe6060f1SDimitry Andric       printEdgeProbability(OS << "  ", &BI, Succ);
10800b57cec5SDimitry Andric   }
10810b57cec5SDimitry Andric }
10820b57cec5SDimitry Andric 
10830b57cec5SDimitry Andric bool BranchProbabilityInfo::
10840b57cec5SDimitry Andric isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const {
10850b57cec5SDimitry Andric   // Hot probability is at least 4/5 = 80%
10860b57cec5SDimitry Andric   // FIXME: Compare against a static "hot" BranchProbability.
10870b57cec5SDimitry Andric   return getEdgeProbability(Src, Dst) > BranchProbability(4, 5);
10880b57cec5SDimitry Andric }
10890b57cec5SDimitry Andric 
10900b57cec5SDimitry Andric /// Get the raw edge probability for the edge. If can't find it, return a
10910b57cec5SDimitry Andric /// default probability 1/N where N is the number of successors. Here an edge is
10920b57cec5SDimitry Andric /// specified using PredBlock and an
10930b57cec5SDimitry Andric /// index to the successors.
10940b57cec5SDimitry Andric BranchProbability
10950b57cec5SDimitry Andric BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
10960b57cec5SDimitry Andric                                           unsigned IndexInSuccessors) const {
10970b57cec5SDimitry Andric   auto I = Probs.find(std::make_pair(Src, IndexInSuccessors));
1098e8d8bef9SDimitry Andric   assert((Probs.end() == Probs.find(std::make_pair(Src, 0))) ==
1099e8d8bef9SDimitry Andric              (Probs.end() == I) &&
1100e8d8bef9SDimitry Andric          "Probability for I-th successor must always be defined along with the "
1101e8d8bef9SDimitry Andric          "probability for the first successor");
11020b57cec5SDimitry Andric 
11030b57cec5SDimitry Andric   if (I != Probs.end())
11040b57cec5SDimitry Andric     return I->second;
11050b57cec5SDimitry Andric 
11060b57cec5SDimitry Andric   return {1, static_cast<uint32_t>(succ_size(Src))};
11070b57cec5SDimitry Andric }
11080b57cec5SDimitry Andric 
11090b57cec5SDimitry Andric BranchProbability
11100b57cec5SDimitry Andric BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
11115ffd83dbSDimitry Andric                                           const_succ_iterator Dst) const {
11120b57cec5SDimitry Andric   return getEdgeProbability(Src, Dst.getSuccessorIndex());
11130b57cec5SDimitry Andric }
11140b57cec5SDimitry Andric 
11150b57cec5SDimitry Andric /// Get the raw edge probability calculated for the block pair. This returns the
11160b57cec5SDimitry Andric /// sum of all raw edge probabilities from Src to Dst.
11170b57cec5SDimitry Andric BranchProbability
11180b57cec5SDimitry Andric BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
11190b57cec5SDimitry Andric                                           const BasicBlock *Dst) const {
1120e8d8bef9SDimitry Andric   if (!Probs.count(std::make_pair(Src, 0)))
1121e8d8bef9SDimitry Andric     return BranchProbability(llvm::count(successors(Src), Dst), succ_size(Src));
11220b57cec5SDimitry Andric 
1123e8d8bef9SDimitry Andric   auto Prob = BranchProbability::getZero();
1124e8d8bef9SDimitry Andric   for (const_succ_iterator I = succ_begin(Src), E = succ_end(Src); I != E; ++I)
1125e8d8bef9SDimitry Andric     if (*I == Dst)
1126e8d8bef9SDimitry Andric       Prob += Probs.find(std::make_pair(Src, I.getSuccessorIndex()))->second;
1127e8d8bef9SDimitry Andric 
1128e8d8bef9SDimitry Andric   return Prob;
11290b57cec5SDimitry Andric }
11300b57cec5SDimitry Andric 
11315ffd83dbSDimitry Andric /// Set the edge probability for all edges at once.
11325ffd83dbSDimitry Andric void BranchProbabilityInfo::setEdgeProbability(
11335ffd83dbSDimitry Andric     const BasicBlock *Src, const SmallVectorImpl<BranchProbability> &Probs) {
11345ffd83dbSDimitry Andric   assert(Src->getTerminator()->getNumSuccessors() == Probs.size());
1135e8d8bef9SDimitry Andric   eraseBlock(Src); // Erase stale data if any.
11365ffd83dbSDimitry Andric   if (Probs.size() == 0)
11375ffd83dbSDimitry Andric     return; // Nothing to set.
11385ffd83dbSDimitry Andric 
1139e8d8bef9SDimitry Andric   Handles.insert(BasicBlockCallbackVH(Src, this));
11405ffd83dbSDimitry Andric   uint64_t TotalNumerator = 0;
11415ffd83dbSDimitry Andric   for (unsigned SuccIdx = 0; SuccIdx < Probs.size(); ++SuccIdx) {
1142e8d8bef9SDimitry Andric     this->Probs[std::make_pair(Src, SuccIdx)] = Probs[SuccIdx];
1143e8d8bef9SDimitry Andric     LLVM_DEBUG(dbgs() << "set edge " << Src->getName() << " -> " << SuccIdx
1144e8d8bef9SDimitry Andric                       << " successor probability to " << Probs[SuccIdx]
1145e8d8bef9SDimitry Andric                       << "\n");
11465ffd83dbSDimitry Andric     TotalNumerator += Probs[SuccIdx].getNumerator();
11475ffd83dbSDimitry Andric   }
11485ffd83dbSDimitry Andric 
11495ffd83dbSDimitry Andric   // Because of rounding errors the total probability cannot be checked to be
11505ffd83dbSDimitry Andric   // 1.0 exactly. That is TotalNumerator == BranchProbability::getDenominator.
11515ffd83dbSDimitry Andric   // Instead, every single probability in Probs must be as accurate as possible.
11525ffd83dbSDimitry Andric   // This results in error 1/denominator at most, thus the total absolute error
11535ffd83dbSDimitry Andric   // should be within Probs.size / BranchProbability::getDenominator.
11545ffd83dbSDimitry Andric   assert(TotalNumerator <= BranchProbability::getDenominator() + Probs.size());
11555ffd83dbSDimitry Andric   assert(TotalNumerator >= BranchProbability::getDenominator() - Probs.size());
1156fe6060f1SDimitry Andric   (void)TotalNumerator;
11575ffd83dbSDimitry Andric }
11585ffd83dbSDimitry Andric 
1159e8d8bef9SDimitry Andric void BranchProbabilityInfo::copyEdgeProbabilities(BasicBlock *Src,
1160e8d8bef9SDimitry Andric                                                   BasicBlock *Dst) {
1161e8d8bef9SDimitry Andric   eraseBlock(Dst); // Erase stale data if any.
1162e8d8bef9SDimitry Andric   unsigned NumSuccessors = Src->getTerminator()->getNumSuccessors();
1163e8d8bef9SDimitry Andric   assert(NumSuccessors == Dst->getTerminator()->getNumSuccessors());
1164e8d8bef9SDimitry Andric   if (NumSuccessors == 0)
1165e8d8bef9SDimitry Andric     return; // Nothing to set.
116606c3fb27SDimitry Andric   if (!this->Probs.contains(std::make_pair(Src, 0)))
1167e8d8bef9SDimitry Andric     return; // No probability is set for edges from Src. Keep the same for Dst.
1168e8d8bef9SDimitry Andric 
1169e8d8bef9SDimitry Andric   Handles.insert(BasicBlockCallbackVH(Dst, this));
1170e8d8bef9SDimitry Andric   for (unsigned SuccIdx = 0; SuccIdx < NumSuccessors; ++SuccIdx) {
1171e8d8bef9SDimitry Andric     auto Prob = this->Probs[std::make_pair(Src, SuccIdx)];
1172e8d8bef9SDimitry Andric     this->Probs[std::make_pair(Dst, SuccIdx)] = Prob;
1173e8d8bef9SDimitry Andric     LLVM_DEBUG(dbgs() << "set edge " << Dst->getName() << " -> " << SuccIdx
1174e8d8bef9SDimitry Andric                       << " successor probability to " << Prob << "\n");
1175e8d8bef9SDimitry Andric   }
1176e8d8bef9SDimitry Andric }
1177e8d8bef9SDimitry Andric 
117806c3fb27SDimitry Andric void BranchProbabilityInfo::swapSuccEdgesProbabilities(const BasicBlock *Src) {
117906c3fb27SDimitry Andric   assert(Src->getTerminator()->getNumSuccessors() == 2);
118006c3fb27SDimitry Andric   if (!Probs.contains(std::make_pair(Src, 0)))
118106c3fb27SDimitry Andric     return; // No probability is set for edges from Src
118206c3fb27SDimitry Andric   assert(Probs.contains(std::make_pair(Src, 1)));
118306c3fb27SDimitry Andric   std::swap(Probs[std::make_pair(Src, 0)], Probs[std::make_pair(Src, 1)]);
118406c3fb27SDimitry Andric }
118506c3fb27SDimitry Andric 
11860b57cec5SDimitry Andric raw_ostream &
11870b57cec5SDimitry Andric BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS,
11880b57cec5SDimitry Andric                                             const BasicBlock *Src,
11890b57cec5SDimitry Andric                                             const BasicBlock *Dst) const {
11900b57cec5SDimitry Andric   const BranchProbability Prob = getEdgeProbability(Src, Dst);
11915f757f3fSDimitry Andric   OS << "edge ";
11925f757f3fSDimitry Andric   Src->printAsOperand(OS, false, Src->getModule());
11935f757f3fSDimitry Andric   OS << " -> ";
11945f757f3fSDimitry Andric   Dst->printAsOperand(OS, false, Dst->getModule());
11955f757f3fSDimitry Andric   OS << " probability is " << Prob
11960b57cec5SDimitry Andric      << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n");
11970b57cec5SDimitry Andric 
11980b57cec5SDimitry Andric   return OS;
11990b57cec5SDimitry Andric }
12000b57cec5SDimitry Andric 
12010b57cec5SDimitry Andric void BranchProbabilityInfo::eraseBlock(const BasicBlock *BB) {
1202e8d8bef9SDimitry Andric   LLVM_DEBUG(dbgs() << "eraseBlock " << BB->getName() << "\n");
1203e8d8bef9SDimitry Andric 
1204e8d8bef9SDimitry Andric   // Note that we cannot use successors of BB because the terminator of BB may
1205e8d8bef9SDimitry Andric   // have changed when eraseBlock is called as a BasicBlockCallbackVH callback.
1206e8d8bef9SDimitry Andric   // Instead we remove prob data for the block by iterating successors by their
1207e8d8bef9SDimitry Andric   // indices from 0 till the last which exists. There could not be prob data for
1208e8d8bef9SDimitry Andric   // a pair (BB, N) if there is no data for (BB, N-1) because the data is always
1209e8d8bef9SDimitry Andric   // set for all successors from 0 to M at once by the method
1210e8d8bef9SDimitry Andric   // setEdgeProbability().
1211e8d8bef9SDimitry Andric   Handles.erase(BasicBlockCallbackVH(BB, this));
1212e8d8bef9SDimitry Andric   for (unsigned I = 0;; ++I) {
1213e8d8bef9SDimitry Andric     auto MapI = Probs.find(std::make_pair(BB, I));
1214e8d8bef9SDimitry Andric     if (MapI == Probs.end()) {
1215e8d8bef9SDimitry Andric       assert(Probs.count(std::make_pair(BB, I + 1)) == 0 &&
1216e8d8bef9SDimitry Andric              "Must be no more successors");
1217e8d8bef9SDimitry Andric       return;
1218e8d8bef9SDimitry Andric     }
12195ffd83dbSDimitry Andric     Probs.erase(MapI);
12200b57cec5SDimitry Andric   }
12210b57cec5SDimitry Andric }
12220b57cec5SDimitry Andric 
1223e8d8bef9SDimitry Andric void BranchProbabilityInfo::calculate(const Function &F, const LoopInfo &LoopI,
12245ffd83dbSDimitry Andric                                       const TargetLibraryInfo *TLI,
1225e8d8bef9SDimitry Andric                                       DominatorTree *DT,
12265ffd83dbSDimitry Andric                                       PostDominatorTree *PDT) {
12270b57cec5SDimitry Andric   LLVM_DEBUG(dbgs() << "---- Branch Probability Info : " << F.getName()
12280b57cec5SDimitry Andric                     << " ----\n\n");
12290b57cec5SDimitry Andric   LastF = &F; // Store the last function we ran on for printing.
1230e8d8bef9SDimitry Andric   LI = &LoopI;
12310b57cec5SDimitry Andric 
1232e8d8bef9SDimitry Andric   SccI = std::make_unique<SccInfo>(F);
12330b57cec5SDimitry Andric 
1234e8d8bef9SDimitry Andric   assert(EstimatedBlockWeight.empty());
1235e8d8bef9SDimitry Andric   assert(EstimatedLoopWeight.empty());
12360b57cec5SDimitry Andric 
1237e8d8bef9SDimitry Andric   std::unique_ptr<DominatorTree> DTPtr;
12385ffd83dbSDimitry Andric   std::unique_ptr<PostDominatorTree> PDTPtr;
12395ffd83dbSDimitry Andric 
1240e8d8bef9SDimitry Andric   if (!DT) {
1241e8d8bef9SDimitry Andric     DTPtr = std::make_unique<DominatorTree>(const_cast<Function &>(F));
1242e8d8bef9SDimitry Andric     DT = DTPtr.get();
1243e8d8bef9SDimitry Andric   }
1244e8d8bef9SDimitry Andric 
12455ffd83dbSDimitry Andric   if (!PDT) {
12465ffd83dbSDimitry Andric     PDTPtr = std::make_unique<PostDominatorTree>(const_cast<Function &>(F));
12475ffd83dbSDimitry Andric     PDT = PDTPtr.get();
12485ffd83dbSDimitry Andric   }
12495ffd83dbSDimitry Andric 
1250e8d8bef9SDimitry Andric   computeEestimateBlockWeight(F, DT, PDT);
1251480093f4SDimitry Andric 
12520b57cec5SDimitry Andric   // Walk the basic blocks in post-order so that we can build up state about
12530b57cec5SDimitry Andric   // the successors of a block iteratively.
1254fcaf7f86SDimitry Andric   for (const auto *BB : post_order(&F.getEntryBlock())) {
12550b57cec5SDimitry Andric     LLVM_DEBUG(dbgs() << "Computing probabilities for " << BB->getName()
12560b57cec5SDimitry Andric                       << "\n");
12570b57cec5SDimitry Andric     // If there is no at least two successors, no sense to set probability.
12580b57cec5SDimitry Andric     if (BB->getTerminator()->getNumSuccessors() < 2)
12590b57cec5SDimitry Andric       continue;
12600b57cec5SDimitry Andric     if (calcMetadataWeights(BB))
12610b57cec5SDimitry Andric       continue;
1262e8d8bef9SDimitry Andric     if (calcEstimatedHeuristics(BB))
12630b57cec5SDimitry Andric       continue;
12640b57cec5SDimitry Andric     if (calcPointerHeuristics(BB))
12650b57cec5SDimitry Andric       continue;
12660b57cec5SDimitry Andric     if (calcZeroHeuristics(BB, TLI))
12670b57cec5SDimitry Andric       continue;
12680b57cec5SDimitry Andric     if (calcFloatingPointHeuristics(BB))
12690b57cec5SDimitry Andric       continue;
12700b57cec5SDimitry Andric   }
12710b57cec5SDimitry Andric 
1272e8d8bef9SDimitry Andric   EstimatedLoopWeight.clear();
1273e8d8bef9SDimitry Andric   EstimatedBlockWeight.clear();
1274e8d8bef9SDimitry Andric   SccI.reset();
12750b57cec5SDimitry Andric 
1276*0fca6ea1SDimitry Andric   if (PrintBranchProb && (PrintBranchProbFuncName.empty() ||
1277*0fca6ea1SDimitry Andric                           F.getName() == PrintBranchProbFuncName)) {
12780b57cec5SDimitry Andric     print(dbgs());
12790b57cec5SDimitry Andric   }
12800b57cec5SDimitry Andric }
12810b57cec5SDimitry Andric 
12820b57cec5SDimitry Andric void BranchProbabilityInfoWrapperPass::getAnalysisUsage(
12830b57cec5SDimitry Andric     AnalysisUsage &AU) const {
12840b57cec5SDimitry Andric   // We require DT so it's available when LI is available. The LI updating code
12850b57cec5SDimitry Andric   // asserts that DT is also present so if we don't make sure that we have DT
12860b57cec5SDimitry Andric   // here, that assert will trigger.
12870b57cec5SDimitry Andric   AU.addRequired<DominatorTreeWrapperPass>();
12880b57cec5SDimitry Andric   AU.addRequired<LoopInfoWrapperPass>();
12890b57cec5SDimitry Andric   AU.addRequired<TargetLibraryInfoWrapperPass>();
1290e8d8bef9SDimitry Andric   AU.addRequired<DominatorTreeWrapperPass>();
12915ffd83dbSDimitry Andric   AU.addRequired<PostDominatorTreeWrapperPass>();
12920b57cec5SDimitry Andric   AU.setPreservesAll();
12930b57cec5SDimitry Andric }
12940b57cec5SDimitry Andric 
12950b57cec5SDimitry Andric bool BranchProbabilityInfoWrapperPass::runOnFunction(Function &F) {
12960b57cec5SDimitry Andric   const LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
12978bcb0991SDimitry Andric   const TargetLibraryInfo &TLI =
12988bcb0991SDimitry Andric       getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
1299e8d8bef9SDimitry Andric   DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
13005ffd83dbSDimitry Andric   PostDominatorTree &PDT =
13015ffd83dbSDimitry Andric       getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
1302e8d8bef9SDimitry Andric   BPI.calculate(F, LI, &TLI, &DT, &PDT);
13030b57cec5SDimitry Andric   return false;
13040b57cec5SDimitry Andric }
13050b57cec5SDimitry Andric 
13060b57cec5SDimitry Andric void BranchProbabilityInfoWrapperPass::releaseMemory() { BPI.releaseMemory(); }
13070b57cec5SDimitry Andric 
13080b57cec5SDimitry Andric void BranchProbabilityInfoWrapperPass::print(raw_ostream &OS,
13090b57cec5SDimitry Andric                                              const Module *) const {
13100b57cec5SDimitry Andric   BPI.print(OS);
13110b57cec5SDimitry Andric }
13120b57cec5SDimitry Andric 
13130b57cec5SDimitry Andric AnalysisKey BranchProbabilityAnalysis::Key;
13140b57cec5SDimitry Andric BranchProbabilityInfo
13150b57cec5SDimitry Andric BranchProbabilityAnalysis::run(Function &F, FunctionAnalysisManager &AM) {
131606c3fb27SDimitry Andric   auto &LI = AM.getResult<LoopAnalysis>(F);
131706c3fb27SDimitry Andric   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
131806c3fb27SDimitry Andric   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
131906c3fb27SDimitry Andric   auto &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);
13200b57cec5SDimitry Andric   BranchProbabilityInfo BPI;
132106c3fb27SDimitry Andric   BPI.calculate(F, LI, &TLI, &DT, &PDT);
13220b57cec5SDimitry Andric   return BPI;
13230b57cec5SDimitry Andric }
13240b57cec5SDimitry Andric 
13250b57cec5SDimitry Andric PreservedAnalyses
13260b57cec5SDimitry Andric BranchProbabilityPrinterPass::run(Function &F, FunctionAnalysisManager &AM) {
13275f757f3fSDimitry Andric   OS << "Printing analysis 'Branch Probability Analysis' for function '"
13285f757f3fSDimitry Andric      << F.getName() << "':\n";
13290b57cec5SDimitry Andric   AM.getResult<BranchProbabilityAnalysis>(F).print(OS);
13300b57cec5SDimitry Andric   return PreservedAnalyses::all();
13310b57cec5SDimitry Andric }
1332