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 @@ -227,6 +227,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 @@ -46,48 +46,56 @@ SmallVectorImpl &ExitingBlocks, BasicBlock *ExitBlock, bool &Changed, BasicBlock *Preheader) { - // Make sure that all PHI entries coming from the loop are loop invariant. - // Because the code is in LCSSA form, any values used outside of the loop - // must pass through a PHI in the exit block, meaning that this check is - // sufficient to guarantee that no loop-variant values are used outside - // 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 this loop was explicitly required to make progress, or if the function + // is required to make progress, or if the function is known to return, we + // can remove this loop. + if (hasMustProgress(L) || L->getHeader()->getParent()->mustProgress()) { + // Make sure that all PHI entries coming from the loop are loop invariant. + // Because the code is in LCSSA form, any values used outside of the loop + // must pass through a PHI in the exit block, meaning that this check is + // sufficient to guarantee that no loop-variant values are used outside + // 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 (Changed) - SE.forgetLoopDispositions(L); + if (Instruction *I = dyn_cast(incoming)) + if (!L->makeLoopInvariant(I, Changed, Preheader->getTerminator())) { + AllEntriesInvariant = false; + break; + } + } - if (!AllEntriesInvariant || !AllOutgoingValuesSame) - return false; + if (Changed) + SE.forgetLoopDispositions(L); - // Make sure that no instructions in the block have potential side-effects. - // This includes instructions that could write to memory, and loads that are - // marked volatile. - for (auto &I : L->blocks()) - if (any_of(*I, [](Instruction &I) { return I.mayHaveSideEffects(); })) + if (!AllEntriesInvariant || !AllOutgoingValuesSame) return false; - return true; + + // Make sure that no instructions in the block have potential side-effects. + // This includes instructions that could write to memory, and loads that are + // marked volatile. + for (auto &I : L->blocks()) + if (any_of(*I, [](Instruction &I) { return I.mayHaveSideEffects(); })) + return false; + return true; + } else { + LLVM_DEBUG(dbgs() << "Loop is not required to make progress.\n"); + return false; + } } /// This function returns true if there is no viable path from the @@ -194,7 +202,8 @@ // Finally, we have to check that the loop really is dead. bool Changed = false; if (!isLoopDead(L, SE, ExitingBlocks, ExitBlock, Changed, Preheader)) { - LLVM_DEBUG(dbgs() << "Loop is not invariant, cannot delete.\n"); + LLVM_DEBUG(dbgs() << "Loop is not invariant or is not required to make " + "progress, cannot delete.\n"); return Changed ? LoopDeletionResult::Modified : LoopDeletionResult::Unmodified; } @@ -202,7 +211,8 @@ // 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)) { + if (isa(S) && + !L->getHeader()->getParent()->mustProgress() && !hasMustProgress(L)) { 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,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, @@ -404,6 +405,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; diff --git a/llvm/test/Analysis/ScalarEvolution/2012-03-26-LoadConstant.ll b/llvm/test/Analysis/ScalarEvolution/2012-03-26-LoadConstant.ll --- a/llvm/test/Analysis/ScalarEvolution/2012-03-26-LoadConstant.ll +++ b/llvm/test/Analysis/ScalarEvolution/2012-03-26-LoadConstant.ll @@ -1,4 +1,4 @@ -; RUN: opt < %s -basic-aa -globalopt -instcombine -loop-rotate -licm -instcombine -indvars -loop-deletion -constmerge -S | FileCheck %s +; RUN: opt < %s -basic-aa -globalopt -instcombine -loop-rotate -licm -instcombine -indvars -loop-deletion -constmerge -simplifycfg -S | FileCheck %s ; PR11882: ComputeLoadConstantCompareExitLimit crash. ; ; for.body is deleted leaving a loop-invariant load. 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/IndVarSimplify/exit_value_tests.ll b/llvm/test/Transforms/IndVarSimplify/exit_value_tests.ll --- a/llvm/test/Transforms/IndVarSimplify/exit_value_tests.ll +++ b/llvm/test/Transforms/IndVarSimplify/exit_value_tests.ll @@ -8,7 +8,8 @@ define i32 @polynomial_constant() { ;