[LoopDeletion] Consider infinite loops alive, unless mustprogress.

[fhahn]

Summary

The current loop or any of its sub-loops may be infinite. Unless the
function or the loops are marked as mustprogress, this in itself makes
the loop *not* dead.

This patch moves the logic to check whether the current loop is finite
or mustprogress to isLoopDead and also extends it to check the
sub-loops. This should fix PR50511.

[nikic]

This looks okay with one caveat: We could still have an irreducible inner cycle, which will not be represented in LoopInfo. Any thoughts on what to do about that?

llvm/lib/Transforms/Scalar/LoopDeletion.cpp

142

Just to double check, subloops also includes recursive subloops, right?

llvm/test/Transforms/LoopDeletion/noop-loops-with-subloops.ll

217

This is probably not checking what you want, because you also have the mustprogress function attribute, next to the loop metadata.

298

You probably meant to use %c3 here.

llvm/test/Transforms/LoopDeletion/unreachable-loops.ll

339

This remark shouldn't be there anymore ... possibly matches a future remark?

[fhahn]

Updated to visit all sub-loops, after adding additional tests in 5c9fe816e3b6. That commit should also addresses the other test-specific comments.

In D103382#2788736, @nikic wrote:

This looks okay with one caveat: We could still have an irreducible inner cycle, which will not be represented in LoopInfo. Any thoughts on what to do about that?

Ah yes, I forgot to mentioned that in the description. Irreducible cycles have never been handled properly in loop-deletion, so I think it would make sense to fix that separately. I don't think there's much we can do other than bailing out on functions that contain irreducible control-flow for now. To do that in loop passes we might need a better way to cache the result of the analysis.

[fhahn]

llvm/lib/Transforms/Scalar/LoopDeletion.cpp

142

I initially thought that all cases should be covered by the tests, but we need to visit all sub-loops recursively. I updated the code. Relevant additional tests in 5c9fe816e3b6

llvm/test/Transforms/LoopDeletion/unreachable-loops.ll

339

I think there's still a loop removed (L2), as the comment indicates.

[nikic]

In D103382#2788736, @nikic wrote:

This looks okay with one caveat: We could still have an irreducible inner cycle, which will not be represented in LoopInfo. Any thoughts on what to do about that?

Ah yes, I forgot to mentioned that in the description. Irreducible cycles have never been handled properly in loop-deletion, so I think it would make sense to fix that separately. I don't think there's much we can do other than bailing out on functions that contain irreducible control-flow for now. To do that in loop passes we might need a better way to cache the result of the analysis.

Yes, I agree that this should be handled separately.

llvm/lib/Transforms/Scalar/LoopDeletion.cpp

118–122

Apart from FnMustProgress, aren't these checks redundant with the ones in the worklist loop?

llvm/test/Transforms/LoopDeletion/unreachable-loops.ll

339

Oh right.

[fhahn]

Simplify code: move checks into loop, remove lambda.

[fhahn]

llvm/lib/Transforms/Scalar/LoopDeletion.cpp

118–122

yes, the lambda is not really necessary any longer, I moved the checks in the loop directly.

[nikic]

LGTM

llvm/lib/Transforms/Scalar/LoopDeletion.cpp

static bool isLoopDead(Loop *L, ScalarEvolution &SE,
   // 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() && !I.isDroppable();
         }))
       return false;
+
+  // The loop or any of its sub-loops looping infinitely is legal. The loop can
+  // only be considered dead if either
+  // a. the function is mustprogress.
+  // b. all (sub-)loops are mustprogress or have a known trip-count.
+  if (L->getHeader()->getParent()->mustProgress())
+    return true;
+
+  SmallVector<Loop *, 8> WorkList;
+  WorkList.push_back(L);
+  while (!WorkList.empty()) {
+    Loop *Current = WorkList.pop_back_val();
+    if (hasMustProgress(Current))
+      continue;
+
+    const SCEV *S = SE.getConstantMaxBackedgeTakenCount(Current);
+    if (isa<SCEVCouldNotCompute>(S)) {
+      LLVM_DEBUG(
+          dbgs() << "Could not compute SCEV MaxBackedgeTakenCount and was "
+                    "not required to make progress.\n");
+      return false;
+    }
+    WorkList.append(Current->begin(), Current->end());
+  }
   return true;
 }
 
 /// This function returns true if there is no viable path from the
 /// entry block to the header of \p L. Right now, it only does
 /// a local search to save compile time.
 static bool isLoopNeverExecuted(Loop *L) {
   using namespace PatternMatch;
 
   auto *Preheader = L->getLoopPreheader();
   // TODO: We can relax this constraint, since we just need a loop
   // predecessor.
   assert(Preheader && "Needs preheader!");
 
   if (Preheader->isEntryBlock())
     return false;
   // All predecessors of the preheader should have a constant conditional
   // branch, with the loop's preheader as not-taken.
   for (auto *Pred: predecessors(Preheader)) {
     BasicBlock *Taken, *NotTaken;
     ConstantInt *Cond;
     if (!match(Pred->getTerminator(),
                m_Br(m_ConstantInt(Cond), Taken, NotTaken)))
       return false;
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.
-  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");
-    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())
            << "Loop deleted because it is invariant";
   });
   deleteDeadLoop(L, &DT, &SE, &LI, MSSA);
   ++NumDeleted;

llvm/test/Transforms/LoopDeletion/noop-loops-with-subloops.ll

 exit:
   ret void
 }
 
 ; The inner loop may not terminate, so we cannot remove it, unless the
 ; function/loop is mustprogress. Test case from PR50511.
 define void @inner_loop_may_be_infinite(i1 %c1, i1 %c2) {
 ; CHECK-LABEL: @inner_loop_may_be_infinite(
-; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK-NEXT:    br label [[LOOP1:%.*]]
+; CHECK:       loop1:
+; CHECK-NEXT:    br i1 [[C1:%.*]], label [[LOOP1_LATCH:%.*]], label [[LOOP2_PREHEADER:%.*]]
+; CHECK:       loop2.preheader:
+; CHECK-NEXT:    br label [[LOOP2:%.*]]
+; CHECK:       loop2:
+; CHECK-NEXT:    br i1 [[C2:%.*]], label [[LOOP1_LATCH_LOOPEXIT:%.*]], label [[LOOP2]]
+; CHECK:       loop1.latch.loopexit:
+; CHECK-NEXT:    br label [[LOOP1_LATCH]]
+; CHECK:       loop1.latch:
+; CHECK-NEXT:    br i1 false, label [[LOOP1_LATCH_LOOP1_CRIT_EDGE:%.*]], label [[EXIT:%.*]]
+; CHECK:       loop1.latch.loop1_crit_edge:
+; CHECK-NEXT:    unreachable
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
   br label %loop1
 
 loop1:
   br i1 %c1, label %loop1.latch, label %loop2
 
loop1.latch:
   br i1 false, label %loop1, label %exit
 
 exit:
   ret void
 }
 
 ; Similar to @inner_loop_may_be_infinite, but the parent loop loop1 is marked
 ; as mustprogress. The loops can be removed.
 define void @inner_loop_may_be_infinite_but_top_loop_mustprogress(i1 %c1, i1 %c2) {
 ; CHECK-LABEL: @inner_loop_may_be_infinite_but_top_loop_mustprogress(
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
   br label %loop1
 
 loop1:

 exit:
   ret void
 }
 
 ; Cannot remove loop3 or loop1, as they are not mustprogress. loop2 is
 ; mustprogress and can be removed.
 define void @loop2_mustprogress_but_not_sibling_loop(i1 %c1, i1 %c2, i1 %c3) {
 ; CHECK-LABEL: @loop2_mustprogress_but_not_sibling_loop(
-; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK-NEXT:    br label [[LOOP1:%.*]]
+; CHECK:       loop1:
+; CHECK-NEXT:    br i1 [[C1:%.*]], label [[LOOP1_LATCH:%.*]], label [[LOOP2_PREHEADER:%.*]]
+; CHECK:       loop2.preheader:
+; CHECK-NEXT:    br label [[LOOP3_PREHEADER:%.*]]
+; CHECK:       loop3.preheader:
+; CHECK-NEXT:    br label [[LOOP3:%.*]]
+; CHECK:       loop3:
+; CHECK-NEXT:    br i1 [[C3:%.*]], label [[LOOP1_LATCH_LOOPEXIT:%.*]], label [[LOOP3]]
+; CHECK:       loop1.latch.loopexit:
+; CHECK-NEXT:    br label [[LOOP1_LATCH]]
+; CHECK:       loop1.latch:
+; CHECK-NEXT:    br i1 false, label [[LOOP1_LATCH_LOOP1_CRIT_EDGE:%.*]], label [[EXIT:%.*]]
+; CHECK:       loop1.latch.loop1_crit_edge:
+; CHECK-NEXT:    unreachable
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
   br label %loop1
 
 loop1:
   br i1 %c1, label %loop1.latch, label %loop2
 
 loop2:
   br i1 %c2, label %loop3, label %loop2, !llvm.loop !4
 
 loop3:
   br i1 %c3, label %loop1.latch, label %loop3
 
 loop1.latch:
   br i1 false, label %loop1, label %exit
 
 exit:
   ret void
 }
 
 define void @loop2_finite_but_child_is_not(i1 %c1, i1 %c2, i1 %c3) {
 ; CHECK-LABEL: @loop2_finite_but_child_is_not(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK-NEXT:    br label [[LOOP1:%.*]]
+; CHECK:       loop1:
+; CHECK-NEXT:    [[IV1:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV1_NEXT:%.*]], [[LOOP1_LATCH:%.*]] ]
+; CHECK-NEXT:    br i1 [[C1:%.*]], label [[LOOP1_LATCH]], label [[LOOP2_PREHEADER:%.*]]
+; CHECK:       loop2.preheader:
+; CHECK-NEXT:    br label [[LOOP2:%.*]]
+; CHECK:       loop2:
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_NEXT:%.*]], [[LOOP2_LATCH:%.*]] ], [ 0, [[LOOP2_PREHEADER]] ]
+; CHECK-NEXT:    br label [[LOOP3:%.*]]
+; CHECK:       loop3:
+; CHECK-NEXT:    br i1 [[C2:%.*]], label [[LOOP2_LATCH]], label [[LOOP3]]
+; CHECK:       loop2.latch:
+; CHECK-NEXT:    [[IV_NEXT]] = add nuw i32 [[IV]], 1
+; CHECK-NEXT:    [[C:%.*]] = icmp ugt i32 [[IV]], 200
+; CHECK-NEXT:    br i1 [[C]], label [[LOOP1_LATCH_LOOPEXIT:%.*]], label [[LOOP2]]
+; CHECK:       loop1.latch.loopexit:
+; CHECK-NEXT:    br label [[LOOP1_LATCH]]
+; CHECK:       loop1.latch:
+; CHECK-NEXT:    [[IV1_NEXT]] = add nuw i32 [[IV1]], 1
+; CHECK-NEXT:    [[C4:%.*]] = icmp ult i32 [[IV1_NEXT]], 200
+; CHECK-NEXT:    br i1 [[C4]], label [[LOOP1]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %loop1
 
 loop1:
   %iv1 = phi i32 [ 0, %entry ], [ %iv1.next, %loop1.latch ]

llvm/test/Transforms/LoopDeletion/unreachable-loops.ll

 }
 
 
 ; Delete a loop (L2) which has subloop (L3).
 ; Here we delete loop L2, but leave L3 as is.
 define void @test9(i64 %n) {
 ; CHECK-LABEL: @test9(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK-NEXT:    br label [[L1:%.*]]
+; CHECK:       L1.loopexit:
+; CHECK-NEXT:    br label [[L1_LOOPEXIT_SPLIT:%.*]]
+; CHECK:       L1.loopexit.split:
+; CHECK-NEXT:    unreachable
+; CHECK:       L1:
+; CHECK-NEXT:    br i1 true, label [[EXIT:%.*]], label [[L2_PREHEADER:%.*]]
+; CHECK:       L2.preheader:
+; CHECK-NEXT:    br label [[L3_PREHEADER:%.*]]
+; CHECK:       L3.preheader:
+; CHECK-NEXT:    [[Y_L2_LCSSA:%.*]] = phi i64 [ undef, [[L2_PREHEADER]] ]
+; CHECK-NEXT:    br label [[L3:%.*]]
+; CHECK:       L3:
+; CHECK-NEXT:    [[COND2:%.*]] = icmp slt i64 [[Y_L2_LCSSA]], [[N:%.*]]
+; CHECK-NEXT:    br i1 [[COND2]], label [[L3]], label [[L1_LOOPEXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
 ; REMARKS-LABEL: Function: test9
 ; REMARKS: Loop deleted because it never executes
 entry:
   br label %L1
 
 L1:
   br i1 true, label %exit, label %L2
 
 L2:
   %x = phi i64 [ 0, %L1 ], [ %x.next, %L2 ]