diff --git a/llvm/include/llvm/Analysis/BranchProbabilityInfo.h b/llvm/include/llvm/Analysis/BranchProbabilityInfo.h --- a/llvm/include/llvm/Analysis/BranchProbabilityInfo.h +++ b/llvm/include/llvm/Analysis/BranchProbabilityInfo.h @@ -151,13 +151,66 @@ /// Forget analysis results for the given basic block. void eraseBlock(const BasicBlock *BB); - // Use to track SCCs for handling irreducible loops. - using SccMap = DenseMap; - using SccHeaderMap = DenseMap; - using SccHeaderMaps = std::vector; - struct SccInfo { + class SccInfo { + // Enum of types to classify basic blocks in SCC. Basic block belonging to + // SCC is 'Inner' until it is either 'Header' or 'Exiting'. Note that a + // basic block can be 'Header' and 'Exiting' at the same time. + enum SccBlockType { + Inner = 0x0, + Header = 0x1, + Exiting = 0x2, + }; + // Map of basic blocks to SCC IDs they belong to. If basic block doesn't + // belong to any SCC it is not in the map. + using SccMap = DenseMap; + // Each basic block in SCC is attributed with one or several types from + // SccBlockType. Map value has uint32_t type (instead of SccBlockType) + // since basic block may be for example "Header" and "Exiting" at the same + // time and we need to be able to keep more than one value from + // SccBlockType. + using SccBlockTypeMap = DenseMap; + // Vector containing classification of basic blocks for all SCCs where i'th + // vector element corresponds to SCC with ID equal to i. + using SccBlockTypeMaps = std::vector; + SccMap SccNums; - SccHeaderMaps SccHeaders; + SccBlockTypeMaps SccBlocks; + + public: + explicit SccInfo(const Function &F); + + /// If \p BB belongs to some SCC then ID of that SCC is returned, otherwise + /// -1 is returned. If \p BB belongs to more than one SCC at the same time + /// result is undefined. + int getSCCNum(const BasicBlock *BB) const; + /// Returns true if \p BB is a 'header' block in SCC with \p SccNum ID, + /// false otherwise. + bool isSCCHeader(const BasicBlock *BB, int SccNum) const { + return getSccBlockType(BB, SccNum) & Header; + } + /// Returns true if \p BB is an 'exiting' block in SCC with \p SccNum ID, + /// false otherwise. + bool isSCCExitingBlock(const BasicBlock *BB, int SccNum) const { + return getSccBlockType(BB, SccNum) & Exiting; + } + /// Fills in \p Enters vector with all such blocks that don't belong to + /// SCC with \p SccNum ID but there is an edge to a block belonging to the + /// SCC. + void getSccEnterBlocks(int SccNum, + SmallVectorImpl &Enters) const; + /// Fills in \p Exits vector with all such blocks that don't belong to + /// SCC with \p SccNum ID but there is an edge from a block belonging to the + /// SCC. + void getSccExitBlocks(int SccNum, + SmallVectorImpl &Exits) const; + + private: + /// Returns \p BB's type according to classification given by SccBlockType + /// enum. Please note that \p BB must belong to SSC with \p SccNum ID. + uint32_t getSccBlockType(const BasicBlock *BB, int SccNum) const; + /// Calculates \p BB's type and stores it in internal data structures for + /// future use. Please note that \p BB must belong to SSC with \p SccNum ID. + void calculateSccBlockType(const BasicBlock *BB, int SccNum); }; private: @@ -196,6 +249,9 @@ /// Track the last function we run over for printing. const Function *LastF = nullptr; + /// Keeps information about all SCCs in a function. + std::unique_ptr SccI; + /// Track the set of blocks directly succeeded by a returning block. SmallPtrSet PostDominatedByUnreachable; @@ -210,8 +266,7 @@ bool calcMetadataWeights(const BasicBlock *BB); bool calcColdCallHeuristics(const BasicBlock *BB); bool calcPointerHeuristics(const BasicBlock *BB); - bool calcLoopBranchHeuristics(const BasicBlock *BB, const LoopInfo &LI, - SccInfo &SccI); + bool calcLoopBranchHeuristics(const BasicBlock *BB, const LoopInfo &LI); bool calcZeroHeuristics(const BasicBlock *BB, const TargetLibraryInfo *TLI); bool calcFloatingPointHeuristics(const BasicBlock *BB); bool calcInvokeHeuristics(const BasicBlock *BB); diff --git a/llvm/lib/Analysis/BranchProbabilityInfo.cpp b/llvm/lib/Analysis/BranchProbabilityInfo.cpp --- a/llvm/lib/Analysis/BranchProbabilityInfo.cpp +++ b/llvm/lib/Analysis/BranchProbabilityInfo.cpp @@ -148,6 +148,105 @@ /// instruction. This is essentially never taken. static const uint32_t IH_NONTAKEN_WEIGHT = 1; +BranchProbabilityInfo::SccInfo::SccInfo(const Function &F) { + // Record SCC numbers of blocks in the CFG to identify irreducible loops. + // FIXME: We could only calculate this if the CFG is known to be irreducible + // (perhaps cache this info in LoopInfo if we can easily calculate it there?). + int SccNum = 0; + for (scc_iterator It = scc_begin(&F); !It.isAtEnd(); + ++It, ++SccNum) { + // Ignore single-block SCCs since they either aren't loops or LoopInfo will + // catch them. + const std::vector &Scc = *It; + if (Scc.size() == 1) + continue; + + LLVM_DEBUG(dbgs() << "BPI: SCC " << SccNum << ":"); + for (const auto *BB : Scc) { + LLVM_DEBUG(dbgs() << " " << BB->getName()); + SccNums[BB] = SccNum; + calculateSccBlockType(BB, SccNum); + } + LLVM_DEBUG(dbgs() << "\n"); + } +} + +int BranchProbabilityInfo::SccInfo::getSCCNum(const BasicBlock *BB) const { + auto SccIt = SccNums.find(BB); + if (SccIt == SccNums.end()) + return -1; + return SccIt->second; +} + +void BranchProbabilityInfo::SccInfo::getSccEnterBlocks( + int SccNum, SmallVectorImpl &Enters) const { + + for (auto MapIt : SccBlocks[SccNum]) { + const auto *BB = MapIt.first; + if (isSCCHeader(BB, SccNum)) + for (const auto *Pred : predecessors(BB)) + if (getSCCNum(Pred) != SccNum) + Enters.push_back(const_cast(BB)); + } +} + +void BranchProbabilityInfo::SccInfo::getSccExitBlocks( + int SccNum, SmallVectorImpl &Exits) const { + for (auto MapIt : SccBlocks[SccNum]) { + const auto *BB = MapIt.first; + if (isSCCExitingBlock(BB, SccNum)) + for (const auto *Succ : successors(BB)) + if (getSCCNum(Succ) != SccNum) + Exits.push_back(const_cast(BB)); + } +} + +uint32_t BranchProbabilityInfo::SccInfo::getSccBlockType(const BasicBlock *BB, + int SccNum) const { + assert(getSCCNum(BB) == SccNum); + + assert(SccBlocks.size() > static_cast(SccNum) && "Unknown SCC"); + const auto &SccBlockTypes = SccBlocks[SccNum]; + + auto It = SccBlockTypes.find(BB); + if (It != SccBlockTypes.end()) { + return It->second; + } + return Inner; +} + +void BranchProbabilityInfo::SccInfo::calculateSccBlockType(const BasicBlock *BB, + int SccNum) { + assert(getSCCNum(BB) == SccNum); + uint32_t BlockType = Inner; + + if (llvm::any_of(make_range(pred_begin(BB), pred_end(BB)), + [&](const BasicBlock *Pred) { + // Consider any block that is an entry point to the SCC as + // a header. + return getSCCNum(Pred) != SccNum; + })) + BlockType |= Header; + + if (llvm::any_of( + make_range(succ_begin(BB), succ_end(BB)), + [&](const BasicBlock *Succ) { return getSCCNum(Succ) != SccNum; })) + BlockType |= Exiting; + + // Lazily compute the set of headers for a given SCC and cache the results + // in the SccHeaderMap. + if (SccBlocks.size() <= static_cast(SccNum)) + SccBlocks.resize(SccNum + 1); + auto &SccBlockTypes = SccBlocks[SccNum]; + + if (BlockType != Inner) { + bool IsInserted; + std::tie(std::ignore, IsInserted) = + SccBlockTypes.insert(std::make_pair(BB, BlockType)); + assert(IsInserted && "Duplicated block in SCC"); + } +} + static void UpdatePDTWorklist(const BasicBlock *BB, PostDominatorTree *PDT, SmallVectorImpl &WorkList, SmallPtrSetImpl &TargetSet) { @@ -511,38 +610,6 @@ return true; } -static int getSCCNum(const BasicBlock *BB, - const BranchProbabilityInfo::SccInfo &SccI) { - auto SccIt = SccI.SccNums.find(BB); - if (SccIt == SccI.SccNums.end()) - return -1; - return SccIt->second; -} - -// Consider any block that is an entry point to the SCC as a header. -static bool isSCCHeader(const BasicBlock *BB, int SccNum, - BranchProbabilityInfo::SccInfo &SccI) { - assert(getSCCNum(BB, SccI) == SccNum); - - // Lazily compute the set of headers for a given SCC and cache the results - // in the SccHeaderMap. - if (SccI.SccHeaders.size() <= static_cast(SccNum)) - SccI.SccHeaders.resize(SccNum + 1); - auto &HeaderMap = SccI.SccHeaders[SccNum]; - bool Inserted; - BranchProbabilityInfo::SccHeaderMap::iterator HeaderMapIt; - std::tie(HeaderMapIt, Inserted) = HeaderMap.insert(std::make_pair(BB, false)); - if (Inserted) { - bool IsHeader = llvm::any_of(make_range(pred_begin(BB), pred_end(BB)), - [&](const BasicBlock *Pred) { - return getSCCNum(Pred, SccI) != SccNum; - }); - HeaderMapIt->second = IsHeader; - return IsHeader; - } else - return HeaderMapIt->second; -} - // Compute the unlikely successors to the block BB in the loop L, specifically // those that are unlikely because this is a loop, and add them to the // UnlikelyBlocks set. @@ -653,12 +720,11 @@ // Calculate Edge Weights using "Loop Branch Heuristics". Predict backedges // as taken, exiting edges as not-taken. bool BranchProbabilityInfo::calcLoopBranchHeuristics(const BasicBlock *BB, - const LoopInfo &LI, - SccInfo &SccI) { + const LoopInfo &LI) { int SccNum; Loop *L = LI.getLoopFor(BB); if (!L) { - SccNum = getSCCNum(BB, SccI); + SccNum = SccI->getSCCNum(BB); if (SccNum < 0) return false; } @@ -685,9 +751,9 @@ else InEdges.push_back(I.getSuccessorIndex()); } else { - if (getSCCNum(*I, SccI) != SccNum) + if (SccI->getSCCNum(*I) != SccNum) ExitingEdges.push_back(I.getSuccessorIndex()); - else if (isSCCHeader(*I, SccNum, SccI)) + else if (SccI->isSCCHeader(*I, SccNum)) BackEdges.push_back(I.getSuccessorIndex()); else InEdges.push_back(I.getSuccessorIndex()); @@ -1072,26 +1138,7 @@ assert(PostDominatedByUnreachable.empty()); assert(PostDominatedByColdCall.empty()); - // Record SCC numbers of blocks in the CFG to identify irreducible loops. - // FIXME: We could only calculate this if the CFG is known to be irreducible - // (perhaps cache this info in LoopInfo if we can easily calculate it there?). - int SccNum = 0; - SccInfo SccI; - for (scc_iterator It = scc_begin(&F); !It.isAtEnd(); - ++It, ++SccNum) { - // Ignore single-block SCCs since they either aren't loops or LoopInfo will - // catch them. - const std::vector &Scc = *It; - if (Scc.size() == 1) - continue; - - LLVM_DEBUG(dbgs() << "BPI: SCC " << SccNum << ":"); - for (auto *BB : Scc) { - LLVM_DEBUG(dbgs() << " " << BB->getName()); - SccI.SccNums[BB] = SccNum; - } - LLVM_DEBUG(dbgs() << "\n"); - } + SccI = std::make_unique(F); std::unique_ptr PDTPtr; @@ -1119,7 +1166,7 @@ continue; if (calcColdCallHeuristics(BB)) continue; - if (calcLoopBranchHeuristics(BB, LI, SccI)) + if (calcLoopBranchHeuristics(BB, LI)) continue; if (calcPointerHeuristics(BB)) continue; @@ -1131,6 +1178,7 @@ PostDominatedByUnreachable.clear(); PostDominatedByColdCall.clear(); + SccI.release(); if (PrintBranchProb && (PrintBranchProbFuncName.empty() ||