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 ExitBlocks; + getExitBlocks(ExitBlocks); + return ExitBlocks.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 exit - // 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,12 @@ 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 has at most one 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 && !L->hasNoExitBlocks()) { + LLVM_DEBUG(dbgs() << "Deletion requires at most one exit block.\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 @@ -542,10 +542,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"); @@ -575,114 +571,132 @@ // 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. llvm::SmallDenseSet, 4> DeadDebugSet; llvm::SmallVector DeadDebugInst; - // Given LCSSA form is satisfied, we should not have users of instructions - // within the dead loop outside of the loop. However, LCSSA doesn't take - // unreachable uses into account. We handle them here. - // We could do it after drop all references (in this case all users in the - // loop will be already eliminated and we have less work to do but according - // to API doc of User::dropAllReferences only valid operation after dropping - // references, is deletion. So let's substitute all usages of - // instruction from the loop with undef value of corresponding type first. - for (auto *Block : L->blocks()) - for (Instruction &I : *Block) { - auto *Undef = UndefValue::get(I.getType()); - for (Value::use_iterator UI = I.use_begin(), E = I.use_end(); UI != E;) { - Use &U = *UI; - ++UI; - if (auto *Usr = dyn_cast(U.getUser())) - if (L->contains(Usr->getParent())) - continue; - // If we have a DT then we can check that uses outside a loop only in - // unreachable block. - if (DT) - assert(!DT->isReachableFromEntry(U) && - "Unexpected user in reachable block"); - U.set(Undef); + if (ExitBlock) { + // Given LCSSA form is satisfied, we should not have users of instructions + // within the dead loop outside of the loop. However, LCSSA doesn't take + // unreachable uses into account. We handle them here. + // We could do it after drop all references (in this case all users in the + // loop will be already eliminated and we have less work to do but according + // to API doc of User::dropAllReferences only valid operation after dropping + // references, is deletion. So let's substitute all usages of + // instruction from the loop with undef value of corresponding type first. + for (auto *Block : L->blocks()) + for (Instruction &I : *Block) { + auto *Undef = UndefValue::get(I.getType()); + for (Value::use_iterator UI = I.use_begin(), E = I.use_end(); + UI != E;) { + Use &U = *UI; + ++UI; + if (auto *Usr = dyn_cast(U.getUser())) + if (L->contains(Usr->getParent())) + continue; + // If we have a DT then we can check that uses outside a loop only in + // unreachable block. + if (DT) + assert(!DT->isReachableFromEntry(U) && + "Unexpected user in reachable block"); + U.set(Undef); + } + auto *DVI = dyn_cast(&I); + if (!DVI) + continue; + auto Key = + DeadDebugSet.find({DVI->getVariable(), DVI->getExpression()}); + if (Key != DeadDebugSet.end()) + continue; + DeadDebugSet.insert({DVI->getVariable(), DVI->getExpression()}); + DeadDebugInst.push_back(DVI); } - auto *DVI = dyn_cast(&I); - if (!DVI) - continue; - auto Key = DeadDebugSet.find({DVI->getVariable(), DVI->getExpression()}); - if (Key != DeadDebugSet.end()) - continue; - DeadDebugSet.insert({DVI->getVariable(), DVI->getExpression()}); - DeadDebugInst.push_back(DVI); - } - // After the loop has been deleted all the values defined and modified - // inside the loop are going to be unavailable. - // 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); + // After the loop has been deleted all the values defined and modified + // inside the loop are going to be unavailable. + // 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); + } // 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 new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/LoopDeletion/mustprogress.ll @@ -0,0 +1,237 @@ +; 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 + +;; Original C Code: +;; void unknown_tripcount_mustprogress_attr_mustprogress_loopmd(int a, int b) { +;; for (; a < b;) ; +;; for (;;) ; +;; } + +define void @unknown_tripcount_mustprogress_attr_mustprogress_loopmd(i32 %a, i32 %b) #0 { +; CHECK: Function Attrs: mustprogress +; CHECK-LABEL: define {{[^@]+}}@unknown_tripcount_mustprogress_attr_mustprogress_loopmd +; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]]) [[ATTR0:#.*]] { +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[FOR_END:%.*]] +; CHECK: for.end: +; CHECK-NEXT: unreachable +; +entry: + br label %for.cond +for.cond: + %cmp = icmp slt i32 %a, %b + br i1 %cmp, label %for.body, label %for.end +for.body: + br label %for.cond, !llvm.loop !2 +for.end: + br label %for.cond1 +for.cond1: + br label %for.cond1 +} + +;; Original C Code: +;; void unknown_tripcount_mustprogress_attr_no_mustprogress_loopmd(int a, int b) { +;; for (; a < b;) ; +;; for (;;) ; +;; } +;; => Removed mustprogress loop attribute + +define void @unknown_tripcount_mustprogress_attr_no_mustprogess_loopmd(i32 %a, i32 %b) #0 { +; CHECK: Function Attrs: mustprogress +; CHECK-LABEL: define {{[^@]+}}@unknown_tripcount_mustprogress_attr_no_mustprogess_loopmd +; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]]) [[ATTR0]] { +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[FOR_END:%.*]] +; CHECK: for.end: +; CHECK-NEXT: unreachable +; +entry: + br label %for.cond +for.cond: + %cmp = icmp slt i32 %a, %b + br i1 %cmp, label %for.body, label %for.end +for.body: + br label %for.cond +for.end: + br label %for.cond1 +for.cond1: + br label %for.cond1 +} + +;; Original C Code: +;; void known_tripcount_no_mustprogress_attr_no_mustprogress_loopmd() { +;; for (int i = 0; i < 5; i++) ; +;; } + +define void @known_tripcount_no_mustprogress_attr_no_mustprogress_loopmd() { +; CHECK-LABEL: define {{[^@]+}}@known_tripcount_no_mustprogress_attr_no_mustprogress_loopmd() { +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[FOR_END:%.*]] +; CHECK: for.end: +; CHECK-NEXT: ret void +; +entry: + br label %for.cond +for.cond: + %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ] + %cmp = icmp slt i32 %i.0, 5 + br i1 %cmp, label %for.body, label %for.end +for.body: + br label %for.inc +for.inc: + %inc = add nsw i32 %i.0, 1 + br label %for.cond +for.end: + ret void +} + +;; Original C Code: +;; void known_tripcount_no_mustprogress_attr_mustprogress_loopmd() { +;; for (int i = 0; i < 5; i++) ; +;; } +;; => Added mustprogress loop attribute + +define void @known_tripcount_no_mustprogress_attr_mustprogress_loopmd() { +; CHECK-LABEL: define {{[^@]+}}@known_tripcount_no_mustprogress_attr_mustprogress_loopmd() { +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[FOR_END:%.*]] +; CHECK: for.end: +; CHECK-NEXT: ret void +; +entry: + br label %for.cond +for.cond: + %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ] + %cmp = icmp slt i32 %i.0, 5 + br i1 %cmp, label %for.body, label %for.end +for.body: + br label %for.inc +for.inc: + %inc = add nsw i32 %i.0, 1 + br label %for.cond, !llvm.loop !4 +for.end: + ret void +} + +;; Original C Code: +;; void known_tripcount_mustprogress_attr_no_mustprogress_loopmd() { +;; for (int i = 0; i < 5; i++) ; +;; } +;; => Added mustprogress function attribute + +define void @known_tripcount_mustprogress_attr_no_mustprogress_loopmd() #0 { +; CHECK: Function Attrs: mustprogress +; CHECK-LABEL: define {{[^@]+}}@known_tripcount_mustprogress_attr_no_mustprogress_loopmd +; CHECK-SAME: () [[ATTR0]] { +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[FOR_END:%.*]] +; CHECK: for.end: +; CHECK-NEXT: ret void +; +entry: + br label %for.cond +for.cond: + %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ] + %cmp = icmp slt i32 %i.0, 5 + br i1 %cmp, label %for.body, label %for.end +for.body: + br label %for.inc +for.inc: + %inc = add nsw i32 %i.0, 1 + br label %for.cond +for.end: + ret void +} + +;; Original C Code: +;; void known_tripcount_mustprogress_attr_mustprogress_loopmd() { +;; for (int i = 0; i < 5; i++) ; +;; } +;; => Added mustprogress function and mustprogress loop attribute + +define void @known_tripcount_mustprogress_attr_mustprogress_loopmd() #0 { +; CHECK: Function Attrs: mustprogress +; CHECK-LABEL: define {{[^@]+}}@known_tripcount_mustprogress_attr_mustprogress_loopmd +; CHECK-SAME: () [[ATTR0]] { +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[FOR_END:%.*]] +; CHECK: for.end: +; CHECK-NEXT: ret void +; +entry: + br label %for.cond +for.cond: + %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ] + %cmp = icmp slt i32 %i.0, 5 + br i1 %cmp, label %for.body, label %for.end +for.body: + br label %for.inc +for.inc: + %inc = add nsw i32 %i.0, 1 + br label %for.cond, !llvm.loop !5 +for.end: + ret void +} + +;; Original C Code: +;; void unknown_tripcount_no_mustprogress_attr_mustprogress_loopmd(int a, int b) { +;; for (; a < b;) ; +;; } +;; => Added mustprogress loop attribute + +define void @unknown_tripcount_no_mustprogress_attr_mustprogress_loopmd(i32 %a, i32 %b) { +; CHECK-LABEL: define {{[^@]+}}@unknown_tripcount_no_mustprogress_attr_mustprogress_loopmd +; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]]) { +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[FOR_END:%.*]] +; CHECK: for.end: +; CHECK-NEXT: ret void +; +entry: + br label %for.cond +for.cond: + %cmp = icmp slt i32 %a, %b + br i1 %cmp, label %for.body, label %for.end +for.body: + br label %for.cond, !llvm.loop !6 +for.end: + ret void +} + +;; Original C Code: +;; void unknown_tripcount_no_mustprogress_attr_no_mustprogress_loopmd(int a, int b) { +;; for (; a < b;) ; +;; } + +define void @unknown_tripcount_no_mustprogress_attr_no_mustprogress_loopmd(i32 %a, i32 %b) { +; CHECK-LABEL: define {{[^@]+}}@unknown_tripcount_no_mustprogress_attr_no_mustprogress_loopmd +; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]]) { +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[FOR_COND:%.*]] +; CHECK: for.cond: +; CHECK-NEXT: [[CMP:%.*]] = icmp slt i32 [[A]], [[B]] +; CHECK-NEXT: br i1 [[CMP]], label [[FOR_BODY:%.*]], label [[FOR_END:%.*]] +; CHECK: for.body: +; CHECK-NEXT: br label [[FOR_COND]] +; CHECK: for.end: +; CHECK-NEXT: ret void +; +entry: + br label %for.cond +for.cond: + %cmp = icmp slt i32 %a, %b + br i1 %cmp, label %for.body, label %for.end +for.body: + br label %for.cond +for.end: + ret void +} + +; CHECK: attributes [[ATTR0]] = { mustprogress } + +attributes #0 = { mustprogress } +!2 = distinct !{!2, !3} +!3 = !{!"llvm.loop.mustprogress"} +!4 = distinct !{!4, !3} +!5 = distinct !{!5, !3} +!6 = distinct !{!6, !3} 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 }