[LoopDeletion] Also consider loops with subloops for deletion.

[fhahn]

Summary

Currently, LoopDeletion does skip loops that have sub-loops, but this
means we currently fail to remove some no-op loops.

One example are inner loops with live-out values. Those cannot be
removed by itself. But the containing loop may itself be a no-op and the
whole loop-nest can be deleted.

The legality checks do not seem to rely on analyzing inner-loops only
for correctness.

With LoopDeletion being a LoopPass, the change means that we now
unfortunately need to do some extra work in parent loops, by checking
some conditions we already checked. But there appears to be no
noticeable compile time impact:
http://llvm-compile-time-tracker.com/compare.php?from=02d11f3cda2ab5b8bf4fc02639fd1f4b8c45963e&to=843201e9cf3b6871e18c52aede5897a22994c36c&stat=instructions

This changes patch leads to ~10 more loops being deleted on
MultiSource, SPEC2000, SPEC2006 with -O3 & LTO

This patch is also required (together with a few others) to eliminate a
no-op loop in omnetpp as discussed on llvm-dev 'LoopDeletion / removal of
empty loops.' (http://lists.llvm.org/pipermail/llvm-dev/2020-December/147462.html)

This change becomes relevant after removing potentially infinite loops
is made possible in 'must-progress' loops (D86844).

Note that I added a function call with side-effects to an outer loop in
llvm/test/Transforms/LoopDeletion/update-scev.ll to preserve the
original spirit of the test.

[reames]

LGTM

Reading through the code, I had a couple of separate thoughts. If you're interested, feel free to follow up on these. If not, feel free to disregard.

1. It's not clear to my why the unreachable loop case requires an exit block. That seems like an overly strict check for the transformation.

2. I was surprised we didn't break the backedge of loops with exit count == 0. This isn't strictly loop deletion, but it sure seems analogous. We seem to rely on simplifycfg for this today which seems likely to cause pass ordering problems.

3. Extending the invariant case to handle multiple exits where all but one are trivially dead might be useful. (IndVarSimplify likes to produce exactly that form. Again, we rely on simplifycfg for cleanup before loop deletion and thus pass ordering is an issue.)

[fhahn]

In D93716#2468772, @reames wrote:

LGTM

Reading through the code, I had a couple of separate thoughts. If you're interested, feel free to follow up on these. If not, feel free to disregard.

1. It's not clear to my why the unreachable loop case requires an exit block. That seems like an overly strict check for the transformation.

2. I was surprised we didn't break the backedge of loops with exit count == 0. This isn't strictly loop deletion, but it sure seems analogous. We seem to rely on simplifycfg for this today which seems likely to cause pass ordering problems.

3. Extending the invariant case to handle multiple exits where all but one are trivially dead might be useful. (IndVarSimplify likes to produce exactly that form. Again, we rely on simplifycfg for cleanup before loop deletion and thus pass ordering is an issue.)

Thank you very much for taking a loop Philip!

Thanks for also sharing the additional thoughts, I'll try to look into them when I have a bit more time. IIUC 2) is already fixed by D93906.

llvm/lib/Transforms/Scalar/LoopDeletion.cpp

static LoopDeletionResult deleteLoopIfDead(Loop *L, DominatorTree &DT,
   // of trouble.
   BasicBlock *Preheader = L->getLoopPreheader();
   if (!Preheader || !L->hasDedicatedExits()) {
     LLVM_DEBUG(
         dbgs()
         << "Deletion requires Loop with preheader and dedicated exits.\n");
     return LoopDeletionResult::Unmodified;
   }
-  // We can't remove loops that contain subloops.  If the subloops were dead,
-  // they would already have been removed in earlier executions of this pass.
-  if (L->begin() != L->end()) {
-    LLVM_DEBUG(dbgs() << "Loop contains subloops.\n");
-    return LoopDeletionResult::Unmodified;
-  }
-
 
   BasicBlock *ExitBlock = L->getUniqueExitBlock();
 
   if (ExitBlock && isLoopNeverExecuted(L)) {
     LLVM_DEBUG(dbgs() << "Loop is proven to never execute, delete it!");
     // We need to forget the loop before setting the incoming values of the exit
     // phis to undef, so we properly invalidate the SCEV expressions for those
     // phis.

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -loop-deletion -verify-dom-info -S | FileCheck %s
 
 target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64"
 
 %pair_t = type { i64, i64 }
 
 ; The loop %inner cannot be removed, because it has outgoing values. But the
 ; outer loop is a no-op and can be removed.
 define void @test1(i64 %N, i64 %M, %pair_t* %ptr) willreturn {
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br label [[OUTER_HEADER:%.*]]
-; CHECK:       outer.header:
-; CHECK-NEXT:    [[OUTER_IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[OUTER_IV_NEXT:%.*]], [[OUTER_LATCH:%.*]] ]
-; CHECK-NEXT:    br label [[INNER:%.*]]
-; CHECK:       inner:
-; CHECK-NEXT:    [[INNER_IV:%.*]] = phi i64 [ 0, [[OUTER_HEADER]] ], [ [[INNER_IV_NEXT:%.*]], [[INNER]] ]
-; CHECK-NEXT:    [[GEP:%.*]] = getelementptr [[PAIR_T:%.*]], %pair_t* [[PTR:%.*]], i64 [[INNER_IV]]
-; CHECK-NEXT:    [[P:%.*]] = load [[PAIR_T]], %pair_t* [[GEP]], align 4
-; CHECK-NEXT:    [[V_0:%.*]] = extractvalue [[PAIR_T]] [[P]], 0
-; CHECK-NEXT:    [[V_1:%.*]] = extractvalue [[PAIR_T]] [[P]], 1
-; CHECK-NEXT:    [[INNER_EC:%.*]] = icmp ult i64 [[V_0]], [[V_1]]
-; CHECK-NEXT:    [[INNER_IV_NEXT]] = add i64 [[INNER_IV]], 1
-; CHECK-NEXT:    br i1 [[INNER_EC]], label [[OUTER_LATCH]], label [[INNER]]
-; CHECK:       outer.latch:
-; CHECK-NEXT:    [[LCSSA:%.*]] = phi i64 [ [[V_1]], [[INNER]] ]
-; CHECK-NEXT:    [[OUTER_EC:%.*]] = icmp ult i64 [[OUTER_IV]], [[LCSSA]]
-; CHECK-NEXT:    [[OUTER_IV_NEXT]] = add i64 [[OUTER_IV]], 1
-; CHECK-NEXT:    br i1 [[OUTER_EC]], label [[EXIT:%.*]], label [[OUTER_HEADER]]
+; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %outer.header
 
 outer.header:
   %outer.iv = phi i64 [ 0, %entry ], [ %outer.iv.next, %outer.latch ]

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

 
 exit:
  ret void
 }
 
 
 ; Delete a loop (L2) which has subloop (L3).
 ; Here we delete loop L2, but leave L3 as is.
-; FIXME: Can delete L3 as well, by iteratively going backward through the single
-; predecessor of L3 until we reach L1's block that guarantees L3 is never
-; executed.
 define void @test9(i64 %n) {
 ; CHECK-LABEL: test9
-; CHECK-LABEL: L2.preheader:
-; CHECK-NEXT: br label %L3.preheader
-; CHECK-NOT: L2:
-; CHECK-LABEL: L3.preheader:
-; CHECK-NEXT: %y.L2.lcssa = phi i64 [ undef, %L2.preheader ]
-; CHECK-NEXT: br label %L3
-; CHECK-LABEL: L3:
-; CHECK: br i1 %cond2, label %L3, label %L1.loopexit
+; CHECK-LABEL: entry:
+; CHECK-NEXT:    br label %exit
+; CHECK-LABEL: exit:
+; CHECK-NEXT:    ret  void
 ; REMARKS-LABEL: Function: test9
 ; REMARKS: Loop deleted because it never executes
-entry: 
+entry:
   br label %L1
 
 L1:
   br i1 true, label %exit, label %L2
 
 L2:
   %x = phi i64 [ 0, %L1 ], [ %x.next, %L2 ]
   %x.next = add i64 %x, 1
   %y.L2 = call i64 @foo(i64 %x.next)
   %cond = icmp slt i64 %x.next, %n
   br i1 %cond, label %L2, label %L3
 
 L3: 
   %cond2 = icmp slt i64 %y.L2, %n
   br i1 %cond2, label %L3, label %L1
 
 exit:
  ret void
 }
 
 ; We cannot delete L3 because of call within it.
 ; Since L3 is not deleted, and entirely contained within L2, L2 is also not
 ; deleted.
-; FIXME: We can delete unexecutable loops having
-; subloops contained entirely within them.
 define void @test10(i64 %n) {
 ; CHECK-LABEL: test10
-; CHECK: L2:
-; CHECK: L3:
+; CHECK-LABEL: entry:
+; CHECK-NEXT:   br label %exit
+; CHECK-LABEL: exit:
+; CHECK-NEXT:    ret void
 entry: 
   br label %L1
 
 L1:
   br i1 true, label %exit, label %L2
 
 L2:
   %x = phi i64 [ 0, %L1 ], [ %x.next, %L3 ]

llvm/test/Transforms/LoopDeletion/update-scev.ll

for.body6:                                        ; preds = %for.body6, %for.body
   %cmp9 = icmp eq i32 %conv8, %f.0
   %conv10 = zext i1 %cmp9 to i32
   %and = and i32 %conv10, %g.138
   %inc = add i32 %h.039, 1
   br i1 undef, label %for.inc11, label %for.body6
 
 for.inc11:                                        ; preds = %for.body6
   %and.lcssa = phi i32 [ %and, %for.body6 ]
+  call void @sideeffect(i32 %and.lcssa)
   %inc12 = add nsw i32 %val, 1
   %tobool = icmp eq i32 %inc12, 0
   br i1 %tobool, label %for.cond14, label %for.body
 
 for.cond14:                                       ; preds = %for.cond14, %for.inc11
   br i1 undef, label %for.cond, label %for.cond14
 }
 
+declare void @sideeffect(i32)
+
 ; LoopDeletion removes the loop %for.body7.1. Make sure %inc.lcssa.1 in the loop
 ; exit block is correctly invalidated.
 
 define void @test2(double* %bx, i64 %by) local_unnamed_addr align 2 {
 ; IR-AFTER-TRANSFORM-LABEL: @test2(
 ; IR-AFTER-TRANSFORM-NOT: for.body7.1:
 
 ; SCEV-EXPRS-LABEL: test2