Revert "[LoopDeletion] Allows deletion of possibly infinite side-effect free loops"

[bgraur]

Summary

Test clang/test/Misc/loop-opt-setup.c fails when executed in Release.

This reverts commit 6f1503d59854b331f1f970d39839619b0a26bbc7.

clang/test/Misc/loop-opt-setup.c

 // 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;
 int foo(void) {
 #pragma unroll
   for (int i = 0; i < 16; ++i)
     a[i] = b += 2;
   return b;
void Helper() {
   while (num_active)
 #pragma clang loop unroll(full)
     for (int i = 0; i < 5; ++i)
       if (nodes[i])
         --num_active;
 }
 
 // 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

llvm/include/llvm/Transforms/Utils/LoopUtils.h

makeFollowupLoopID(MDNode *OrigLoopID, ArrayRef<StringRef> FollowupAttrs,
                    bool AlwaysNew = false);
 
 /// Look for the loop attribute that disables all transformation heuristic.
 bool hasDisableAllTransformsHint(const Loop *L);
 
 /// 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
   /// be applied.
   TM_Unspecified,
 
   /// The transformation should be applied without considering a cost model.
   TM_Enable,

llvm/lib/Transforms/Scalar/LoopDeletion.cpp

static bool isLoopNeverExecuted(Loop *L) {
   assert(!pred_empty(Preheader) &&
          "Preheader should have predecessors at this point!");
   // All the predecessors have the loop preheader as not-taken target.
   return true;
 }
 
 /// 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.
 ///
 /// \returns true if any changes were made. This may mutate the loop even if it
 /// is unable to delete it due to hoisting trivially loop invariant
 /// instructions out of the loop.
 static LoopDeletionResult deleteLoopIfDead(Loop *L, DominatorTree &DT,
static LoopDeletionResult deleteLoopIfDead(Loop *L, DominatorTree &DT,
   // 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");
     return Changed ? LoopDeletionResult::Modified
                    : 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<SCEVCouldNotCompute>(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<SCEVCouldNotCompute>(S)) {
+    LLVM_DEBUG(dbgs() << "Could not compute SCEV MaxBackedgeTakenCount.\n");
     return Changed ? LoopDeletionResult::Modified
                    : LoopDeletionResult::Unmodified;
   }
 
   LLVM_DEBUG(dbgs() << "Loop is invariant, delete it!");
   ORE.emit([&]() {
     return OptimizationRemark(DEBUG_TYPE, "Invariant", L->getStartLoc(),
                               L->getHeader())

llvm/lib/Transforms/Utils/LoopUtils.cpp

static cl::opt<bool> ForceReductionIntrinsic(
     "force-reduction-intrinsics", cl::Hidden,
     cl::desc("Force creating reduction intrinsics for testing."),
     cl::init(false));
 
 #define DEBUG_TYPE "loop-utils"
 
 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,
                                    bool PreserveLCSSA) {
   bool Changed = false;
 
   // We re-use a vector for the in-loop predecesosrs.
   SmallVector<BasicBlock *, 4> InLoopPredecessors;

 bool llvm::hasDisableAllTransformsHint(const Loop *L) {
   return getBooleanLoopAttribute(L, LLVMLoopDisableNonforced);
 }
 
 bool llvm::hasDisableLICMTransformsHint(const Loop *L) {
   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;
 
   Optional<int> Count =
       getOptionalIntLoopAttribute(L, "llvm.loop.unroll.count");
   if (Count.hasValue())
     return Count.getValue() == 1 ? TM_SuppressedByUser : TM_ForcedByUser;
void llvm::deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE,
   // source block to the exit block. Consider the case where the unexecuted loop
   // branches back to an outer loop. If we deleted the loop and removed the edge
   // coming to this inner loop, this will break the outer loop structure (by
   // 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);
 
   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!");
 
     Builder.CreateCondBr(Builder.getFalse(), L->getHeader(), ExitBlock);
     // Remove the old branch. The conditional branch becomes a new terminator.
     OldBr->eraseFromParent();
 
for (PHINode &P : ExitBlock->phis()) {
       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();
       }
     }
 
     // Disconnect the loop body by branching directly to its exit.
     Builder.SetInsertPoint(Preheader->getTerminator());
     Builder.CreateBr(ExitBlock);
     // Remove the old branch.
     Preheader->getTerminator()->eraseFromParent();
-  } 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);
+        MSSAU->applyUpdates(
+            {{DominatorTree::Delete, Preheader, L->getHeader()}}, *DT);
         SmallSetVector<BasicBlock *, 8> 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<std::pair<DIVariable *, DIExpression *>, 4> DeadDebugSet;
   llvm::SmallVector<DbgVariableIntrinsic *, 4> DeadDebugInst;
 
   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

llvm/test/Transforms/LoopDeletion/mustprogress.ll

-; 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}

llvm/test/Transforms/LoopDeletion/no-exit-blocks.ll

 ; 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
+; 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
 
   %.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 }