diff --git a/clang/test/Misc/loop-opt-setup.c b/clang/test/Misc/loop-opt-setup.c --- a/clang/test/Misc/loop-opt-setup.c +++ b/clang/test/Misc/loop-opt-setup.c @@ -1,5 +1,4 @@ // RUN: %clang -O1 -fno-unroll-loops -S -o - %s -emit-llvm | FileCheck %s -// RUN: %clang -std=c99 -O1 -fno-unroll-loops -S -o - %s -emit-llvm | FileCheck %s --check-prefix C99 extern int a[16]; int b = 0; @@ -25,12 +24,7 @@ } // Check br i1 to make sure the loop is gone, there will still be a label branch for the infinite loop. -// In C99, there was no forward progress requirement, so we expect the infinite loop to still exist, -// but for C11 and onwards, the infinite loop can be deleted. // CHECK-LABEL: Helper -// C99: br label -// C99-NOT: br i1 -// C99: br label -// CHECK: entry: -// CHECK-NOT: br i1 -// CHECK-NEXT: ret void +// CHECK: br label +// CHECK-NOT: br i1 +// CHECK: br label diff --git a/llvm/include/llvm/Transforms/Utils/LoopUtils.h b/llvm/include/llvm/Transforms/Utils/LoopUtils.h --- a/llvm/include/llvm/Transforms/Utils/LoopUtils.h +++ b/llvm/include/llvm/Transforms/Utils/LoopUtils.h @@ -255,9 +255,6 @@ /// Look for the loop attribute that disables the LICM transformation heuristics. bool hasDisableLICMTransformsHint(const Loop *L); -/// Look for the loop attribute that requires progress within the loop. -bool hasMustProgress(const Loop *L); - /// The mode sets how eager a transformation should be applied. enum TransformationMode { /// The pass can use heuristics to determine whether a transformation should 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 @@ -128,11 +128,10 @@ /// Remove a loop if it is dead. /// -/// A loop is considered dead either if it does not impact the observable -/// behavior of the program other than finite running time, or if it is -/// required to make progress by an attribute such as 'mustprogress' or -/// 'llvm.loop.mustprogress' and does not make any. This may remove -/// infinite loops that have been required to make progress. +/// A loop is considered dead if it does not impact the observable behavior of +/// the program other than finite running time. This never removes a loop that +/// might be infinite (unless it is never executed), as doing so could change +/// the halting/non-halting nature of a program. /// /// This entire process relies pretty heavily on LoopSimplify form and LCSSA in /// order to make various safety checks work. @@ -208,13 +207,11 @@ : LoopDeletionResult::Unmodified; } - // Don't remove loops for which we can't solve the trip count unless the loop - // was required to make progress but has been determined to be dead. + // Don't remove loops for which we can't solve the trip count. + // They could be infinite, in which case we'd be changing program behavior. const SCEV *S = SE.getConstantMaxBackedgeTakenCount(L); - if (isa(S) && - !L->getHeader()->getParent()->mustProgress() && !hasMustProgress(L)) { - LLVM_DEBUG(dbgs() << "Could not compute SCEV MaxBackedgeTakenCount and was " - "not required to make progress.\n"); + if (isa(S)) { + LLVM_DEBUG(dbgs() << "Could not compute SCEV MaxBackedgeTakenCount.\n"); return Changed ? LoopDeletionResult::Modified : LoopDeletionResult::Unmodified; } 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 @@ -63,7 +63,6 @@ static const char *LLVMLoopDisableNonforced = "llvm.loop.disable_nonforced"; static const char *LLVMLoopDisableLICM = "llvm.licm.disable"; -static const char *LLVMLoopMustProgress = "llvm.loop.mustprogress"; bool llvm::formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, @@ -420,10 +419,6 @@ return getBooleanLoopAttribute(L, LLVMLoopDisableLICM); } -bool llvm::hasMustProgress(const Loop *L) { - return getBooleanLoopAttribute(L, LLVMLoopMustProgress); -} - TransformationMode llvm::hasUnrollTransformation(Loop *L) { if (getBooleanLoopAttribute(L, "llvm.loop.unroll.disable")) return TM_SuppressedByUser; @@ -594,7 +589,6 @@ IRBuilder<> Builder(OldBr); auto *ExitBlock = L->getUniqueExitBlock(); - DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager); if (ExitBlock) { assert(ExitBlock && "Should have a unique exit block!"); assert(L->hasDedicatedExits() && "Loop should have dedicated exits!"); @@ -626,6 +620,7 @@ "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) { @@ -641,28 +636,27 @@ 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(); } - 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(); - } - } - // Use a map to unique and a vector to guarantee deterministic ordering. llvm::SmallDenseSet, 4> DeadDebugSet; llvm::SmallVector DeadDebugInst; diff --git a/llvm/test/Transforms/LoopDeletion/mustprogress.ll b/llvm/test/Transforms/LoopDeletion/mustprogress.ll deleted file mode 100644 --- a/llvm/test/Transforms/LoopDeletion/mustprogress.ll +++ /dev/null @@ -1,237 +0,0 @@ -; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature --check-attributes -; RUN: opt < %s -loop-deletion -verify-dom-info -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 --- a/llvm/test/Transforms/LoopDeletion/no-exit-blocks.ll +++ b/llvm/test/Transforms/LoopDeletion/no-exit-blocks.ll @@ -5,7 +5,14 @@ ; CHECK: Function Attrs: mustprogress ; CHECK-LABEL: define {{[^@]+}}@f ; CHECK-SAME: () [[ATTR0:#.*]] { -; CHECK-NEXT: unreachable +; CHECK-NEXT: br label [[TMP1:%.*]] +; CHECK: 1: +; CHECK-NEXT: [[DOT01:%.*]] = phi i32 [ 1, [[TMP0:%.*]] ], [ [[TMP3:%.*]], [[TMP2:%.*]] ] +; CHECK-NEXT: [[DOT0:%.*]] = phi i32 [ 1, [[TMP0]] ], [ [[TMP3]], [[TMP2]] ] +; CHECK-NEXT: br label [[TMP2]] +; CHECK: 2: +; CHECK-NEXT: [[TMP3]] = add nsw i32 [[DOT01]], [[DOT0]] +; CHECK-NEXT: br label [[TMP1]] ; br label %1