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 @@ -32,6 +32,7 @@ namespace llvm { class Function; +class Loop; class LoopInfo; class raw_ostream; class PostDominatorTree; @@ -230,6 +231,32 @@ : CallbackVH(const_cast(V)), BPI(BPI) {} }; + /// Pair of Loop and SCC ID number. Used to unify handling of normal and + /// SCC based loop representations. + using LoopData = std::pair; + /// Helper class to keep basic block along with its loop data information. + class LoopBlock { + public: + explicit LoopBlock(const BasicBlock *BB, const LoopInfo &LI, + const SccInfo &SccI); + + const BasicBlock *getBlock() const { return BB; } + Loop *getLoop() const { return LD.first; } + int getSccNum() const { return LD.second; } + + bool belongsToLoop() const { return getLoop() || getSccNum() != -1; } + bool belongsToSameLoop(const LoopBlock &LB) const { + return (LB.getLoop() && getLoop() == LB.getLoop()) || + (LB.getSccNum() != -1 && getSccNum() == LB.getSccNum()); + } + + private: + const BasicBlock *const BB = nullptr; + LoopData LD = {nullptr, -1}; + }; + // Pair of LoopBlocks representing an edge from first to second block. + using LoopEdge = std::pair; + DenseSet> Handles; // Since we allow duplicate edges from one basic block to another, we use @@ -258,6 +285,27 @@ /// Track the set of blocks that always lead to a cold call. SmallPtrSet PostDominatedByColdCall; + /// Returns true if destination block belongs to some loop and source block is + /// either doesn't belong to any loop or belongs to a loop which is not inner + /// relative to the destination block. + bool isLoopEnteringEdge(const LoopEdge &Edge) const; + /// Returns true if source block belongs to some loop and destination block is + /// either doesn't belong to any loop or belongs to a loop which is not inner + /// relative to the source block. + bool isLoopExitingEdge(const LoopEdge &Edge) const; + /// Returns true if \p Edge is either enters to or exits from some loop, false + /// in all other cases. + bool isLoopEnteringExitingEdge(const LoopEdge &Edge) const; + /// Returns true if source and destination blocks belongs to the same loop and + /// destination block is loop header. + bool isLoopBackEdge(const LoopEdge &Edge) const; + // Fills in \p Enters vector with all "enter" blocks to a loop \LB belongs to. + void getLoopEnterBlocks(const LoopBlock &LB, + SmallVectorImpl &Enters) const; + // Fills in \p Exits vector with all "exit" blocks from a loop \LB belongs to. + void getLoopExitBlocks(const LoopBlock &LB, + SmallVectorImpl &Exits) const; + void computePostDominatedByUnreachable(const Function &F, PostDominatorTree *PDT); void computePostDominatedByColdCall(const Function &F, 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 @@ -247,6 +247,66 @@ } } +BranchProbabilityInfo::LoopBlock::LoopBlock(const BasicBlock *BB, + const LoopInfo &LI, + const SccInfo &SccI) + : BB(BB) { + LD.first = LI.getLoopFor(BB); + if (!LD.first) { + LD.second = SccI.getSCCNum(BB); + } +} + +bool BranchProbabilityInfo::isLoopEnteringEdge(const LoopEdge &Edge) const { + const auto &SrcBlock = Edge.first; + const auto &DstBlock = Edge.second; + return (DstBlock.getLoop() && + !DstBlock.getLoop()->contains(SrcBlock.getLoop())) || + // Assume that SCCs can't be nested. + (DstBlock.getSccNum() != -1 && + SrcBlock.getSccNum() != DstBlock.getSccNum()); +} + +bool BranchProbabilityInfo::isLoopExitingEdge(const LoopEdge &Edge) const { + return isLoopEnteringEdge({Edge.second, Edge.first}); +} + +bool BranchProbabilityInfo::isLoopEnteringExitingEdge( + const LoopEdge &Edge) const { + return isLoopEnteringEdge(Edge) || isLoopExitingEdge(Edge); +} + +bool BranchProbabilityInfo::isLoopBackEdge(const LoopEdge &Edge) const { + const auto &SrcBlock = Edge.first; + const auto &DstBlock = Edge.second; + return SrcBlock.belongsToSameLoop(DstBlock) && + ((DstBlock.getLoop() && + DstBlock.getLoop()->getHeader() == DstBlock.getBlock()) || + (DstBlock.getSccNum() != -1 && + SccI->isSCCHeader(DstBlock.getBlock(), DstBlock.getSccNum()))); +} + +void BranchProbabilityInfo::getLoopEnterBlocks( + const LoopBlock &LB, SmallVectorImpl &Enters) const { + if (LB.getLoop()) { + auto *Header = LB.getLoop()->getHeader(); + Enters.append(pred_begin(Header), pred_end(Header)); + } else { + assert(LB.getSccNum() != -1 && "LB doesn't belong to any loop?"); + SccI->getSccEnterBlocks(LB.getSccNum(), Enters); + } +} + +void BranchProbabilityInfo::getLoopExitBlocks( + const LoopBlock &LB, SmallVectorImpl &Exits) const { + if (LB.getLoop()) { + LB.getLoop()->getExitBlocks(Exits); + } else { + assert(LB.getSccNum() != -1 && "LB doesn't belong to any loop?"); + SccI->getSccExitBlocks(LB.getSccNum(), Exits); + } +} + static void UpdatePDTWorklist(const BasicBlock *BB, PostDominatorTree *PDT, SmallVectorImpl &WorkList, SmallPtrSetImpl &TargetSet) { @@ -720,17 +780,13 @@ // as taken, exiting edges as not-taken. bool BranchProbabilityInfo::calcLoopBranchHeuristics(const BasicBlock *BB, const LoopInfo &LI) { - int SccNum; - Loop *L = LI.getLoopFor(BB); - if (!L) { - SccNum = SccI->getSCCNum(BB); - if (SccNum < 0) - return false; - } + LoopBlock LB(BB, LI, *SccI.get()); + if (!LB.belongsToLoop()) + return false; SmallPtrSet UnlikelyBlocks; - if (L) - computeUnlikelySuccessors(BB, L, UnlikelyBlocks); + if (LB.getLoop()) + computeUnlikelySuccessors(BB, LB.getLoop(), UnlikelyBlocks); SmallVector BackEdges; SmallVector ExitingEdges; @@ -738,24 +794,19 @@ SmallVector UnlikelyEdges; for (const_succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) { - // Use LoopInfo if we have it, otherwise fall-back to SCC info to catch - // irreducible loops. - if (L) { - if (UnlikelyBlocks.count(*I) != 0) - UnlikelyEdges.push_back(I.getSuccessorIndex()); - else if (!L->contains(*I)) - ExitingEdges.push_back(I.getSuccessorIndex()); - else if (L->getHeader() == *I) - BackEdges.push_back(I.getSuccessorIndex()); - else - InEdges.push_back(I.getSuccessorIndex()); - } else { - if (SccI->getSCCNum(*I) != SccNum) - ExitingEdges.push_back(I.getSuccessorIndex()); - else if (SccI->isSCCHeader(*I, SccNum)) - BackEdges.push_back(I.getSuccessorIndex()); - else - InEdges.push_back(I.getSuccessorIndex()); + LoopBlock SuccLB(*I, LI, *SccI.get()); + LoopEdge Edge(LB, SuccLB); + bool IsUnlikelyEdge = + LB.getLoop() && (UnlikelyBlocks.find(*I) != UnlikelyBlocks.end()); + + if (IsUnlikelyEdge) + UnlikelyEdges.push_back(I.getSuccessorIndex()); + else if (isLoopExitingEdge(Edge)) + ExitingEdges.push_back(I.getSuccessorIndex()); + else if (isLoopBackEdge(Edge)) + BackEdges.push_back(I.getSuccessorIndex()); + else { + InEdges.push_back(I.getSuccessorIndex()); } }