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