[LoopDeletion] Forget loop before setting values to undef

[fhahn]

Summary

After D71539, we need to forget the loop before setting the incoming
values of phi nodes in exit blocks, because we are looking through those
phi nodes now and the SCEV expression could depend on the loop phi. If
we update the phi nodes before forgetting the loop, we miss those users
during invalidation.

[nikic]

llvm/lib/Transforms/Utils/LoopUtils.cpp

729

This call performs an unconditional SCEV verification, probably not what you intended. Should be behind NDEBUG at least.

[fhahn]

llvm/lib/Transforms/Utils/LoopUtils.cpp

729

Yes, should be done in 7bae2bc5a8dd11c016c895e3a691fb93575773f3, thanks!

[uabelho]

Hi!

I just wrote
https://bugs.llvm.org/show_bug.cgi?id=47753
about a failure that starts occuring with this patch.

[mkazantsev]

llvm/lib/Transforms/Utils/LoopUtils.cpp

729

I wonder if *all* SCEV has to be correct at this point. I mean, you are only deleting one single loop while possibly doing something else in some other place and plan to invalidate SCEV later. I don't think it's a right place for an assert.

We have a test failing on this, but I cannot figure out how to make a simple repro unfortunately. The failure seems not related to the loop in question. The point is that it fails this assertion but passes when we verify all IR after each pass.

[mkazantsev]

llvm/lib/Transforms/Utils/LoopUtils.cpp

729

In my case, the test fails even if we verify SCEV in the beginning on this method. So I don't think it's correct to verify it here since the whole thing can be called on broken SCEV which we plan to fully drop later.

llvm/lib/Transforms/Scalar/LoopDeletion.cpp

if (L->begin() != L->end()) {
     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.
+    SE.forgetLoop(L);
     // Set incoming value to undef for phi nodes in the exit block.
     for (PHINode &P : ExitBlock->phis()) {
       std::fill(P.incoming_values().begin(), P.incoming_values().end(),
                 UndefValue::get(P.getType()));
     }
     ORE.emit([&]() {
       return OptimizationRemark(DEBUG_TYPE, "NeverExecutes", L->getStartLoc(),
                                 L->getHeader())

llvm/lib/Transforms/Utils/LoopUtils.cpp

if (Loop *ParentLoop = L->getParentLoop()) {
       ParentLoop->removeChildLoop(I);
     } else {
       Loop::iterator I = find(*LI, L);
       assert(I != LI->end() && "Couldn't find loop");
       LI->removeLoop(I);
     }
     LI->destroy(L);
   }
+
+  if (SE)
+    SE->verify();
 }
 
 /// Checks if \p L has single exit through latch block except possibly
 /// "deoptimizing" exits. Returns branch instruction terminating the loop
 /// latch if above check is successful, nullptr otherwise.
 static BranchInst *getExpectedExitLoopLatchBranch(Loop *L) {
   BasicBlock *Latch = L->getLoopLatch();
   if (!Latch)

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

-; RUN: opt -S -analyze -scalar-evolution -loop-deletion -scalar-evolution < %s | FileCheck %s --check-prefix=SCEV-EXPRS
+; RUN: opt -S -analyze -scalar-evolution -loop-deletion -scalar-evolution -verify-scev < %s | FileCheck %s --check-prefix=SCEV-EXPRS
 ; RUN: opt -S -loop-deletion < %s | FileCheck %s --check-prefix=IR-AFTER-TRANSFORM
 ; RUN: opt -S -indvars -loop-deletion -indvars < %s | FileCheck %s --check-prefix=ORIGINAL-CRASH
 
 ; Checking for a crash.  Loop-deletion would change the loop
 ; disposition of an instruction, but not update SCEV.
 
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-macosx10.11.0"
for.inc11:                                        ; preds = %for.body6
   %and.lcssa = phi i32 [ %and, %for.body6 ]
   %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
 }
+
+; 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
+; SCEV-EXPRS:     %inc.lcssa.1 = phi i64 [ undef, %for.body7.preheader.1 ]
+; SCEV-EXPRS-NEXT: -->  undef
+entry:
+  %cmp = icmp sgt i64 %by, 0
+  br label %for.cond.preheader
+
+for.cond.preheader:                               ; preds = %entry
+  br i1 %cmp, label %for.cond5.preheader.lr.ph, label %for.end14
+
+for.cond5.preheader.lr.ph:                        ; preds = %for.cond.preheader
+  br label %for.cond5.preheader
+
+for.cond.loopexit.loopexit:                       ; preds = %for.body10
+  %inc11.lcssa = phi i64 [ %inc11, %for.body10 ]
+  br label %for.cond.loopexit
+
+for.cond.loopexit:                                ; preds = %for.cond8.preheader, %for.cond.loopexit.loopexit
+  %ca.3.lcssa = phi i64 [ %ca.2.lcssa, %for.cond8.preheader ], [ %inc11.lcssa, %for.cond.loopexit.loopexit ]
+  br i1 %cmp, label %for.cond5.preheader, label %for.end14.loopexit
+
+for.cond5.preheader:                              ; preds = %for.cond.loopexit, %for.cond5.preheader.lr.ph
+  %ca.19 = phi i64 [ 0, %for.cond5.preheader.lr.ph ], [ %ca.3.lcssa, %for.cond.loopexit ]
+  br i1 false, label %for.cond8.preheader, label %for.body7.preheader
+
+for.body7.preheader:                              ; preds = %for.cond5.preheader
+  br label %for.body7
+
+for.cond8.preheader.loopexit:                     ; preds = %for.body7
+  %inc.lcssa = phi i64 [ %inc, %for.body7 ]
+  br label %for.cond8.preheader
+
+for.cond8.preheader:                              ; preds = %for.cond8.preheader.loopexit, %for.cond5.preheader
+  %ca.2.lcssa = phi i64 [ %ca.19, %for.cond5.preheader ], [ %inc.lcssa, %for.cond8.preheader.loopexit ]
+  br i1 true, label %for.body10.preheader, label %for.cond.loopexit
+
+for.body10.preheader:                             ; preds = %for.cond8.preheader
+  br label %for.body10
+
+for.body7:                                        ; preds = %for.body7, %for.body7.preheader
+  %ca.26 = phi i64 [ %inc, %for.body7 ], [ %ca.19, %for.body7.preheader ]
+  %inc = add nsw i64 %ca.26, 1
+  %arrayidx = getelementptr inbounds double, double* %bx, i64 %ca.26
+  store double 0.000000e+00, double* %arrayidx, align 8
+  br i1 false, label %for.cond8.preheader.loopexit, label %for.body7
+
+for.body10:                                       ; preds = %for.body10, %for.body10.preheader
+  %ca.37 = phi i64 [ %inc11, %for.body10 ], [ %ca.2.lcssa, %for.body10.preheader ]
+  %inc11 = add nsw i64 %ca.37, 1
+  br i1 true, label %for.body10, label %for.cond.loopexit.loopexit
+
+for.end14.loopexit:                               ; preds = %for.cond.loopexit
+  br label %for.end14
+
+for.end14:                                        ; preds = %for.end14.loopexit, %for.cond.preheader
+  br i1 %cmp, label %for.cond5.preheader.lr.ph.1, label %for.end14.1
+
+for.cond5.preheader.lr.ph.1:                      ; preds = %for.end14
+  br label %for.cond5.preheader.1
+
+for.cond5.preheader.1:                            ; preds = %for.cond.loopexit.1, %for.cond5.preheader.lr.ph.1
+  %ca.19.1 = phi i64 [ 0, %for.cond5.preheader.lr.ph.1 ], [ %ca.3.lcssa.1, %for.cond.loopexit.1 ]
+  br i1 true, label %for.cond8.preheader.1, label %for.body7.preheader.1
+
+for.body7.preheader.1:                            ; preds = %for.cond5.preheader.1
+  br label %for.body7.1
+
+for.body7.1:                                      ; preds = %for.body7.1, %for.body7.preheader.1
+  %ca.26.1 = phi i64 [ %inc.1, %for.body7.1 ], [ %ca.19.1, %for.body7.preheader.1 ]
+  %inc.1 = add nsw i64 %ca.26.1, 1
+  %arrayidx.1 = getelementptr inbounds double, double* %bx, i64 %ca.26.1
+  store double 0.000000e+00, double* %arrayidx.1, align 8
+  br i1 true, label %for.cond8.preheader.loopexit.1, label %for.body7.1
+
+for.cond8.preheader.loopexit.1:                   ; preds = %for.body7.1
+  %inc.lcssa.1 = phi i64 [ %inc.1, %for.body7.1 ]
+  br label %for.cond8.preheader.1
+
+for.cond8.preheader.1:                            ; preds = %for.cond8.preheader.loopexit.1, %for.cond5.preheader.1
+  %ca.2.lcssa.1 = phi i64 [ %ca.19.1, %for.cond5.preheader.1 ], [ %inc.lcssa.1, %for.cond8.preheader.loopexit.1 ]
+  br i1 false, label %for.body10.preheader.1, label %for.cond.loopexit.1
+
+for.body10.preheader.1:                           ; preds = %for.cond8.preheader.1
+  br label %for.body10.1
+
+for.body10.1:                                     ; preds = %for.body10.1, %for.body10.preheader.1
+  %ca.37.1 = phi i64 [ %inc11.1, %for.body10.1 ], [ %ca.2.lcssa.1, %for.body10.preheader.1 ]
+  %inc11.1 = add nsw i64 %ca.37.1, 1
+  br i1 false, label %for.body10.1, label %for.cond.loopexit.loopexit.1
+
+for.cond.loopexit.loopexit.1:                     ; preds = %for.body10.1
+  %inc11.lcssa.1 = phi i64 [ %inc11.1, %for.body10.1 ]
+  br label %for.cond.loopexit.1
+
+for.cond.loopexit.1:                              ; preds = %for.cond.loopexit.loopexit.1, %for.cond8.preheader.1
+  %ca.3.lcssa.1 = phi i64 [ %ca.2.lcssa.1, %for.cond8.preheader.1 ], [ %inc11.lcssa.1, %for.cond.loopexit.loopexit.1 ]
+  br i1 %cmp, label %for.cond5.preheader.1, label %for.end14.loopexit.1
+
+for.end14.loopexit.1:                             ; preds = %for.cond.loopexit.1
+  br label %for.end14.1
+
+for.end14.1:                                      ; preds = %for.end14.loopexit.1, %for.end14
+  ret void
+}