diff --git a/llvm/include/llvm/Analysis/LoopInfo.h b/llvm/include/llvm/Analysis/LoopInfo.h --- a/llvm/include/llvm/Analysis/LoopInfo.h +++ b/llvm/include/llvm/Analysis/LoopInfo.h @@ -302,6 +302,9 @@ /// Otherwise return null. BlockT *getUniqueExitBlock() const; + /// Return true if this loop does not have any exit blocks. + bool hasNoExitBlocks() const; + /// Edge type. typedef std::pair Edge; diff --git a/llvm/include/llvm/Analysis/LoopInfoImpl.h b/llvm/include/llvm/Analysis/LoopInfoImpl.h --- a/llvm/include/llvm/Analysis/LoopInfoImpl.h +++ b/llvm/include/llvm/Analysis/LoopInfoImpl.h @@ -68,6 +68,13 @@ ExitBlocks.push_back(Succ); } +template +bool LoopBase::hasNoExitBlocks() const { + SmallVector UniqueExitBlocks; + getExitBlocks(UniqueExitBlocks); + return UniqueExitBlocks.empty(); +} + /// getExitBlock - If getExitBlocks would return exactly one block, /// return that block. Otherwise return null. template diff --git a/llvm/lib/Transforms/Scalar/LoopDeletion.cpp b/llvm/lib/Transforms/Scalar/LoopDeletion.cpp --- a/llvm/lib/Transforms/Scalar/LoopDeletion.cpp +++ b/llvm/lib/Transforms/Scalar/LoopDeletion.cpp @@ -53,26 +53,28 @@ // of the loop. bool AllEntriesInvariant = true; bool AllOutgoingValuesSame = true; - for (PHINode &P : ExitBlock->phis()) { - Value *incoming = P.getIncomingValueForBlock(ExitingBlocks[0]); - - // Make sure all exiting blocks produce the same incoming value for the - // block. If there are different incoming values for different exiting - // blocks, then it is impossible to statically determine which value should - // be used. - AllOutgoingValuesSame = - all_of(makeArrayRef(ExitingBlocks).slice(1), [&](BasicBlock *BB) { - return incoming == P.getIncomingValueForBlock(BB); - }); - - if (!AllOutgoingValuesSame) - break; - - if (Instruction *I = dyn_cast(incoming)) - if (!L->makeLoopInvariant(I, Changed, Preheader->getTerminator())) { - AllEntriesInvariant = false; + if (!L->hasNoExitBlocks()) { + for (PHINode &P : ExitBlock->phis()) { + Value *incoming = P.getIncomingValueForBlock(ExitingBlocks[0]); + + // Make sure all exiting blocks produce the same incoming value for the + // block. If there are different incoming values for different exiting + // blocks, then it is impossible to statically determine which value + // should be used. + AllOutgoingValuesSame = + all_of(makeArrayRef(ExitingBlocks).slice(1), [&](BasicBlock *BB) { + return incoming == P.getIncomingValueForBlock(BB); + }); + + if (!AllOutgoingValuesSame) break; - } + + if (Instruction *I = dyn_cast(incoming)) + if (!L->makeLoopInvariant(I, Changed, Preheader->getTerminator())) { + AllEntriesInvariant = false; + break; + } + } } if (Changed) @@ -189,12 +191,13 @@ SmallVector ExitingBlocks; L->getExitingBlocks(ExitingBlocks); - // We require that the loop only have a single exit block. Otherwise, we'd - // be in the situation of needing to be able to solve statically which exit - // block will be branched to, or trying to preserve the branching logic in - // a loop invariant manner. - if (!ExitBlock) { - LLVM_DEBUG(dbgs() << "Deletion requires single exit block\n"); + // We require that the loop only have a single exit block or no exit blocks. + // Otherwise, we'd be in the situation of needing to be able to solve + // statically which exit block will be branched to, or trying to preserve the + // branching logic in a loop invariant manner. + if (!ExitBlock && !L->hasNoExitBlocks()) { + LLVM_DEBUG( + dbgs() << "Deletion requires single exit block or no exit blocks\n"); return LoopDeletionResult::Unmodified; } // Finally, we have to check that the loop really is dead. diff --git a/llvm/lib/Transforms/Utils/LoopUtils.cpp b/llvm/lib/Transforms/Utils/LoopUtils.cpp --- a/llvm/lib/Transforms/Utils/LoopUtils.cpp +++ b/llvm/lib/Transforms/Utils/LoopUtils.cpp @@ -547,10 +547,6 @@ if (SE) SE->forgetLoop(L); - auto *ExitBlock = L->getUniqueExitBlock(); - assert(ExitBlock && "Should have a unique exit block!"); - assert(L->hasDedicatedExits() && "Loop should have dedicated exits!"); - auto *OldBr = dyn_cast(Preheader->getTerminator()); assert(OldBr && "Preheader must end with a branch"); assert(OldBr->isUnconditional() && "Preheader must have a single successor"); @@ -580,60 +576,74 @@ // deleting the backedge of the outer loop). If the outer loop is indeed a // non-loop, it will be deleted in a future iteration of loop deletion pass. IRBuilder<> Builder(OldBr); - Builder.CreateCondBr(Builder.getFalse(), L->getHeader(), ExitBlock); - // Remove the old branch. The conditional branch becomes a new terminator. - OldBr->eraseFromParent(); - - // Rewrite phis in the exit block to get their inputs from the Preheader - // instead of the exiting block. - for (PHINode &P : ExitBlock->phis()) { - // Set the zero'th element of Phi to be from the preheader and remove all - // other incoming values. Given the loop has dedicated exits, all other - // incoming values must be from the exiting blocks. - int PredIndex = 0; - P.setIncomingBlock(PredIndex, Preheader); - // Removes all incoming values from all other exiting blocks (including - // duplicate values from an exiting block). - // Nuke all entries except the zero'th entry which is the preheader entry. - // NOTE! We need to remove Incoming Values in the reverse order as done - // below, to keep the indices valid for deletion (removeIncomingValues - // updates getNumIncomingValues and shifts all values down into the operand - // being deleted). - for (unsigned i = 0, e = P.getNumIncomingValues() - 1; i != e; ++i) - P.removeIncomingValue(e - i, false); - - assert((P.getNumIncomingValues() == 1 && - P.getIncomingBlock(PredIndex) == Preheader) && - "Should have exactly one value and that's from the preheader!"); - } - DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager); - if (DT) { - DTU.applyUpdates({{DominatorTree::Insert, Preheader, ExitBlock}}); - if (MSSA) { - MSSAU->applyUpdates({{DominatorTree::Insert, Preheader, ExitBlock}}, *DT); - if (VerifyMemorySSA) - MSSA->verifyMemorySSA(); + auto *ExitBlock = L->getUniqueExitBlock(); + if (ExitBlock) { + assert(ExitBlock && "Should have a unique exit block!"); + assert(L->hasDedicatedExits() && "Loop should have dedicated exits!"); + + Builder.CreateCondBr(Builder.getFalse(), L->getHeader(), ExitBlock); + // Remove the old branch. The conditional branch becomes a new terminator. + OldBr->eraseFromParent(); + + // Rewrite phis in the exit block to get their inputs from the Preheader + // instead of the exiting block. + for (PHINode &P : ExitBlock->phis()) { + // Set the zero'th element of Phi to be from the preheader and remove all + // other incoming values. Given the loop has dedicated exits, all other + // incoming values must be from the exiting blocks. + int PredIndex = 0; + P.setIncomingBlock(PredIndex, Preheader); + // Removes all incoming values from all other exiting blocks (including + // duplicate values from an exiting block). + // Nuke all entries except the zero'th entry which is the preheader entry. + // NOTE! We need to remove Incoming Values in the reverse order as done + // below, to keep the indices valid for deletion (removeIncomingValues + // updates getNumIncomingValues and shifts all values down into the + // operand being deleted). + for (unsigned i = 0, e = P.getNumIncomingValues() - 1; i != e; ++i) + P.removeIncomingValue(e - i, false); + + assert((P.getNumIncomingValues() == 1 && + P.getIncomingBlock(PredIndex) == Preheader) && + "Should have exactly one value and that's from the preheader!"); } - } - // Disconnect the loop body by branching directly to its exit. - Builder.SetInsertPoint(Preheader->getTerminator()); - Builder.CreateBr(ExitBlock); - // Remove the old branch. - Preheader->getTerminator()->eraseFromParent(); - - if (DT) { - DTU.applyUpdates({{DominatorTree::Delete, Preheader, L->getHeader()}}); - if (MSSA) { - MSSAU->applyUpdates({{DominatorTree::Delete, Preheader, L->getHeader()}}, - *DT); - SmallSetVector DeadBlockSet(L->block_begin(), - L->block_end()); - MSSAU->removeBlocks(DeadBlockSet); - if (VerifyMemorySSA) - MSSA->verifyMemorySSA(); + DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager); + if (DT) { + DTU.applyUpdates({{DominatorTree::Insert, Preheader, ExitBlock}}); + if (MSSA) { + MSSAU->applyUpdates({{DominatorTree::Insert, Preheader, ExitBlock}}, + *DT); + if (VerifyMemorySSA) + MSSA->verifyMemorySSA(); + } } + + // Disconnect the loop body by branching directly to its exit. + Builder.SetInsertPoint(Preheader->getTerminator()); + Builder.CreateBr(ExitBlock); + // Remove the old branch. + Preheader->getTerminator()->eraseFromParent(); + + if (DT) { + DTU.applyUpdates({{DominatorTree::Delete, Preheader, L->getHeader()}}); + if (MSSA) { + MSSAU->applyUpdates( + {{DominatorTree::Delete, Preheader, L->getHeader()}}, *DT); + SmallSetVector DeadBlockSet(L->block_begin(), + L->block_end()); + MSSAU->removeBlocks(DeadBlockSet); + if (VerifyMemorySSA) + MSSA->verifyMemorySSA(); + } + } + } else { + assert(L->hasNoExitBlocks() && + "Loop should have either zero or one exit blocks."); + Builder.SetInsertPoint(OldBr); + Builder.CreateUnreachable(); + Preheader->getTerminator()->eraseFromParent(); } // Use a map to unique and a vector to guarantee deterministic ordering. @@ -679,15 +689,17 @@ // Since debug values in the loop have been deleted, inserting an undef // dbg.value truncates the range of any dbg.value before the loop where the // loop used to be. This is particularly important for constant values. - DIBuilder DIB(*ExitBlock->getModule()); - Instruction *InsertDbgValueBefore = ExitBlock->getFirstNonPHI(); - assert(InsertDbgValueBefore && - "There should be a non-PHI instruction in exit block, else these " - "instructions will have no parent."); - for (auto *DVI : DeadDebugInst) - DIB.insertDbgValueIntrinsic(UndefValue::get(Builder.getInt32Ty()), - DVI->getVariable(), DVI->getExpression(), - DVI->getDebugLoc(), InsertDbgValueBefore); + if (ExitBlock) { + DIBuilder DIB(*ExitBlock->getModule()); + Instruction *InsertDbgValueBefore = ExitBlock->getFirstNonPHI(); + assert(InsertDbgValueBefore && + "There should be a non-PHI instruction in exit block, else these " + "instructions will have no parent."); + for (auto *DVI : DeadDebugInst) + DIB.insertDbgValueIntrinsic(UndefValue::get(Builder.getInt32Ty()), + DVI->getVariable(), DVI->getExpression(), + DVI->getDebugLoc(), InsertDbgValueBefore); + } // Remove the block from the reference counting scheme, so that we can // delete it freely later. diff --git a/llvm/test/Transforms/LoopDeletion/mustprogress.ll b/llvm/test/Transforms/LoopDeletion/mustprogress.ll --- a/llvm/test/Transforms/LoopDeletion/mustprogress.ll +++ b/llvm/test/Transforms/LoopDeletion/mustprogress.ll @@ -14,9 +14,7 @@ ; CHECK-NEXT: entry: ; CHECK-NEXT: br label [[FOR_END:%.*]] ; CHECK: for.end: -; CHECK-NEXT: br label [[FOR_COND1:%.*]] -; CHECK: for.cond1: -; CHECK-NEXT: br label [[FOR_COND1]] +; CHECK-NEXT: unreachable ; entry: br label %for.cond @@ -45,9 +43,7 @@ ; CHECK-NEXT: entry: ; CHECK-NEXT: br label [[FOR_END:%.*]] ; CHECK: for.end: -; CHECK-NEXT: br label [[FOR_COND1:%.*]] -; CHECK: for.cond1: -; CHECK-NEXT: br label [[FOR_COND1]] +; CHECK-NEXT: unreachable ; entry: br label %for.cond diff --git a/llvm/test/Transforms/LoopDeletion/no-exit-blocks.ll b/llvm/test/Transforms/LoopDeletion/no-exit-blocks.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/LoopDeletion/no-exit-blocks.ll @@ -0,0 +1,20 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature --check-attributes +; RUN: opt < %s -loop-deletion -S | FileCheck %s + +define void @f() #0 { +; CHECK: Function Attrs: mustprogress +; CHECK-LABEL: define {{[^@]+}}@f +; CHECK-SAME: () [[ATTR0:#.*]] { +; CHECK-NEXT: unreachable +; + br label %1 + + %.01 = phi i32 [ 1, %0 ], [ %3, %2 ] + %.0 = phi i32 [ 1, %0 ], [ %3, %2 ] + br label %2 + + %3 = add nsw i32 %.01, %.0 + br label %1 +} + +attributes #0 = { mustprogress }