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; @@ -25,6 +26,9 @@ // Check br i1 to make sure the loop is gone, there will still be a label branch for the infinite loop. // 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/Other/loop-deletion-printer.ll b/llvm/test/Other/loop-deletion-printer.ll --- a/llvm/test/Other/loop-deletion-printer.ll +++ b/llvm/test/Other/loop-deletion-printer.ll @@ -14,7 +14,7 @@ ; DELETED-BUT-PRINTED: IR Dump {{.*}}LoopDeletionPass {{.*invalidated:}} ; DELETED-BUT-PRINTED-NOT: IR Dump {{.*}}LoopInstSimplifyPass -define void @deleteme() { +define void @deleteme() willreturn { entry: br label %loop loop: diff --git a/llvm/test/Other/loop-pm-invalidation.ll b/llvm/test/Other/loop-pm-invalidation.ll --- a/llvm/test/Other/loop-pm-invalidation.ll +++ b/llvm/test/Other/loop-pm-invalidation.ll @@ -227,7 +227,7 @@ ret void } -define void @dead_loop() { +define void @dead_loop() willreturn { ; CHECK-LOOP-INV: Starting {{.*}}Function pass manager run ; CHECK-LOOP-INV-NEXT: Starting {{.*}}Function pass manager run ; CHECK-LOOP-INV-NEXT: Running pass: LoopSimplifyPass diff --git a/llvm/test/Transforms/LICM/2003-02-27-PreheaderProblem.ll b/llvm/test/Transforms/LICM/2003-02-27-PreheaderProblem.ll --- a/llvm/test/Transforms/LICM/2003-02-27-PreheaderProblem.ll +++ b/llvm/test/Transforms/LICM/2003-02-27-PreheaderProblem.ll @@ -6,7 +6,7 @@ ; RUN: opt < %s -licm -loop-deletion -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -S | \ ; RUN: not grep "br " -define i32 @main(i32 %argc) { +define i32 @main(i32 %argc) willreturn { ;