Index: llvm/include/llvm/Analysis/LoopInfo.h =================================================================== --- llvm/include/llvm/Analysis/LoopInfo.h +++ llvm/include/llvm/Analysis/LoopInfo.h @@ -274,6 +274,14 @@ /// dedicated exits. void getUniqueExitBlocks(SmallVectorImpl &ExitBlocks) const; + /// Return all unique successor blocks of this loop except successors from + /// Latch block are not considered. If the exit comes from Latch has also + /// non Latch predecessor in a loop it will be added to ExitBlocks. + /// These are the blocks _outside of the current loop_ which are branched to. + /// This assumes that loop exits are in canonical form, i.e. all exits are + /// dedicated exits. + void getUniqueNonLatchExitBlocks(SmallVectorImpl &ExitBlocks) const; + /// If getUniqueExitBlocks would return exactly one block, return that block. /// Otherwise return null. BlockT *getUniqueExitBlock() const; Index: llvm/include/llvm/Analysis/LoopInfoImpl.h =================================================================== --- llvm/include/llvm/Analysis/LoopInfoImpl.h +++ llvm/include/llvm/Analysis/LoopInfoImpl.h @@ -95,21 +95,27 @@ return true; } +// Helper function to get unique loop exits. if ExcludeBB is not nullptr +// the exits coming from it will be ignored. template -void LoopBase::getUniqueExitBlocks( - SmallVectorImpl &ExitBlocks) const { +void getUniqueExitBlocksHelper(const LoopT *L, + SmallVectorImpl &ExitBlocks, + const BlockT *ExcludeBB) { typedef GraphTraits BlockTraits; typedef GraphTraits> InvBlockTraits; - assert(hasDedicatedExits() && + assert(L->hasDedicatedExits() && "getUniqueExitBlocks assumes the loop has canonical form exits!"); SmallVector SwitchExitBlocks; - for (BlockT *Block : this->blocks()) { + for (BlockT *Block : L->blocks()) { + if (Block == ExcludeBB) + continue; + SwitchExitBlocks.clear(); for (BlockT *Successor : children(Block)) { // If block is inside the loop then it is not an exit block. - if (contains(Successor)) + if (L->contains(Successor)) continue; BlockT *FirstPred = *InvBlockTraits::child_begin(Successor); @@ -141,6 +147,20 @@ } template +void LoopBase::getUniqueExitBlocks( + SmallVectorImpl &ExitBlocks) const { + getUniqueExitBlocksHelper(this, ExitBlocks, + static_cast(nullptr) /* get all exits */); +} + +template +void LoopBase::getUniqueNonLatchExitBlocks( + SmallVectorImpl &ExitBlocks) const { + assert(getLoopLatch() && "Latch block must exists"); + getUniqueExitBlocksHelper(this, ExitBlocks, getLoopLatch()); +} + +template BlockT *LoopBase::getUniqueExitBlock() const { SmallVector UniqueExitBlocks; getUniqueExitBlocks(UniqueExitBlocks); Index: llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp =================================================================== --- llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp +++ llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp @@ -424,10 +424,9 @@ /// Returns true if we can safely unroll a multi-exit/exiting loop. OtherExits /// is populated with all the loop exit blocks other than the LatchExit block. -static bool -canSafelyUnrollMultiExitLoop(Loop *L, SmallVectorImpl &OtherExits, - BasicBlock *LatchExit, bool PreserveLCSSA, - bool UseEpilogRemainder) { +static bool canSafelyUnrollMultiExitLoop(Loop *L, BasicBlock *LatchExit, + bool PreserveLCSSA, + bool UseEpilogRemainder) { // We currently have some correctness constrains in unrolling a multi-exit // loop. Check for these below. @@ -435,11 +434,6 @@ // We rely on LCSSA form being preserved when the exit blocks are transformed. if (!PreserveLCSSA) return false; - SmallVector Exits; - L->getUniqueExitBlocks(Exits); - for (auto *BB : Exits) - if (BB != LatchExit) - OtherExits.push_back(BB); // TODO: Support multiple exiting blocks jumping to the `LatchExit` when // UnrollRuntimeMultiExit is true. This will need updating the logic in @@ -469,9 +463,8 @@ bool PreserveLCSSA, bool UseEpilogRemainder) { #if !defined(NDEBUG) - SmallVector OtherExitsDummyCheck; - assert(canSafelyUnrollMultiExitLoop(L, OtherExitsDummyCheck, LatchExit, - PreserveLCSSA, UseEpilogRemainder) && + assert(canSafelyUnrollMultiExitLoop(L, LatchExit, PreserveLCSSA, + UseEpilogRemainder) && "Should be safe to unroll before checking profitability!"); #endif @@ -595,8 +588,9 @@ // These are exit blocks other than the target of the latch exiting block. SmallVector OtherExits; + L->getUniqueNonLatchExitBlocks(OtherExits); bool isMultiExitUnrollingEnabled = - canSafelyUnrollMultiExitLoop(L, OtherExits, LatchExit, PreserveLCSSA, + canSafelyUnrollMultiExitLoop(L, LatchExit, PreserveLCSSA, UseEpilogRemainder) && canProfitablyUnrollMultiExitLoop(L, OtherExits, LatchExit, PreserveLCSSA, UseEpilogRemainder);