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,4 +1,5 @@ // 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; @@ -24,7 +25,12 @@ } // 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 -// CHECK: br label -// CHECK-NOT: br i1 -// CHECK: br label +// C99: br label +// C99-NOT: br i1 +// C99: br label +// CHECK: entry: +// CHECK-NOT: br i1 +// CHECK-NEXT: ret void 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,6 +255,9 @@ /// 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,10 +128,11 @@ /// Remove a loop if it is dead. /// -/// 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. +/// 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. /// /// This entire process relies pretty heavily on LoopSimplify form and LCSSA in /// order to make various safety checks work. @@ -207,11 +208,13 @@ : LoopDeletionResult::Unmodified; } - // 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. + // 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. const SCEV *S = SE.getConstantMaxBackedgeTakenCount(L); - if (isa(S)) { - LLVM_DEBUG(dbgs() << "Could not compute SCEV MaxBackedgeTakenCount.\n"); + 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"); 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,6 +63,7 @@ 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, @@ -419,6 +420,10 @@ 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; @@ -589,6 +594,7 @@ 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!"); @@ -620,7 +626,6 @@ "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) { @@ -636,27 +641,28 @@ 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 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 -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,14 +5,7 @@ ; CHECK: Function Attrs: mustprogress ; CHECK-LABEL: define {{[^@]+}}@f ; CHECK-SAME: () [[ATTR0:#.*]] { -; 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]] +; CHECK-NEXT: unreachable ; br label %1