From d72eb9c9854d638ca04c1e245e7edfb0ae04f11c Mon Sep 17 00:00:00 2001
From: Florian Hahn <flo@fhahn.com>
Date: Fri, 23 Sep 2022 15:13:30 +0100
Subject: [PATCH] [LoopDeletion] Invalidate SCEV after moving instruction.

LoopDeletion may hoist instructions out of a loop using
makeLoopInvariant without invalidating the SCEV for the moved
instruction.

Moving the instruction to a different block may change its
cached block disposition, so invalidate the cached info.

Fixes #57837.
---
 llvm/lib/Transforms/Scalar/LoopDeletion.cpp        |  8 ++-
 .../pr57837-invalidate-scev-after-hoisting.ll      | 75 ++++++++++++++++++++++
 2 files changed, 82 insertions(+), 1 deletion(-)
 create mode 100644 llvm/test/Transforms/LoopDeletion/pr57837-invalidate-scev-after-hoisting.ll

diff --git a/llvm/lib/Transforms/Scalar/LoopDeletion.cpp b/llvm/lib/Transforms/Scalar/LoopDeletion.cpp
index 1a538dd..d969126 100644
--- a/llvm/lib/Transforms/Scalar/LoopDeletion.cpp
+++ b/llvm/lib/Transforms/Scalar/LoopDeletion.cpp
@@ -89,11 +89,17 @@ static bool isLoopDead(Loop *L, ScalarEvolution &SE,
       if (!AllOutgoingValuesSame)
         break;
 
-      if (Instruction *I = dyn_cast<Instruction>(incoming))
+      if (Instruction *I = dyn_cast<Instruction>(incoming)) {
         if (!L->makeLoopInvariant(I, Changed, Preheader->getTerminator())) {
           AllEntriesInvariant = false;
           break;
         }
+        if (Changed) {
+          // Moving I to a different location may change its block disposition,
+          // so invalidate its SCEV.
+          SE.forgetValue(I);
+        }
+      }
     }
   }
 
diff --git a/llvm/test/Transforms/LoopDeletion/pr57837-invalidate-scev-after-hoisting.ll b/llvm/test/Transforms/LoopDeletion/pr57837-invalidate-scev-after-hoisting.ll
new file mode 100644
index 0000000..0635540a
--- /dev/null
+++ b/llvm/test/Transforms/LoopDeletion/pr57837-invalidate-scev-after-hoisting.ll
@@ -0,0 +1,75 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -passes='loop(indvars,loop-deletion),verify<scalar-evolution>,print<scalar-evolution>' -S %s 2>&1| FileCheck %s
+
+; Make sure the SCEV for %invar is invalidated properly when the instruction is
+; moved by LoopDeletion.
+
+; CHECK:      Determining loop execution counts for: @test
+; CHECK-NEXT: Loop %inner: backedge-taken count is (405 + %invar)<nuw><nsw>
+; CHECK-NEXT: Loop %inner: max backedge-taken count is 405
+; CHECK-NEXT: Loop %inner: Predicated backedge-taken count is (405 + %invar)<nuw><nsw>
+
+define void @test() {
+; CHECK-LABEL: @test(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    br label [[OUTER_HEADER:%.*]]
+; CHECK:       outer.header:
+; CHECK-NEXT:    br i1 true, label [[INNER_PH:%.*]], label [[OUTER_LATCH:%.*]]
+; CHECK:       inner.ph:
+; CHECK-NEXT:    [[INVAR:%.*]] = ashr i32 0, 3
+; CHECK-NEXT:    br label [[INNER:%.*]]
+; CHECK:       inner:
+; CHECK-NEXT:    [[P:%.*]] = phi i32 [ poison, [[INNER_PH]] ], [ [[INVAR]], [[INNER]] ]
+; CHECK-NEXT:    [[INNER_IV:%.*]] = phi i32 [ 1, [[INNER_PH]] ], [ [[INNER_IV_NEXT:%.*]], [[INNER]] ]
+; CHECK-NEXT:    [[ADD_1:%.*]] = add i32 [[P]], 30586
+; CHECK-NEXT:    call void @use(i32 [[ADD_1]])
+; CHECK-NEXT:    [[INNER_IV_NEXT]] = add nuw nsw i32 [[INNER_IV]], 1
+; CHECK-NEXT:    [[INVAR_ADD:%.*]] = add i32 [[INVAR]], 407
+; CHECK-NEXT:    [[INNER_CMP:%.*]] = icmp ult i32 [[INNER_IV_NEXT]], [[INVAR_ADD]]
+; CHECK-NEXT:    br i1 [[INNER_CMP]], label [[INNER]], label [[INNER_EXIT:%.*]]
+; CHECK:       inner.exit:
+; CHECK-NEXT:    [[INVAR_LCSSA:%.*]] = phi i32 [ [[INVAR]], [[INNER]] ]
+; CHECK-NEXT:    br label [[OUTER_LATCH]]
+; CHECK:       outer.latch:
+; CHECK-NEXT:    [[MERGE:%.*]] = phi i32 [ 0, [[OUTER_HEADER]] ], [ [[INVAR_LCSSA]], [[INNER_EXIT]] ]
+; CHECK-NEXT:    call void @use(i32 [[MERGE]])
+; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+bb:
+  br label %outer.header
+
+outer.header:                                              ; preds = %bb19, %bb
+  %outer.iv = phi i32 [ 0, %bb ], [ %tmp21, %outer.latch ]
+  %outer.cmp = icmp ult i32 %outer.iv, 400
+  br i1 %outer.cmp, label %inner.ph, label %outer.latch
+
+inner.ph:
+  br label %inner
+
+inner:
+  %p = phi i32 [ poison, %inner.ph ], [ %invar, %inner ]
+  %inner.iv = phi i32 [ 1, %inner.ph ], [ %inner.iv.next , %inner ]
+  %add.1 = add i32 %p, 30586
+  call void @use(i32 %add.1)
+  %invar = ashr i32 0, 3
+  %inner.iv.next = add nuw nsw i32 %inner.iv, 1
+  %invar.add = add i32 %invar, 407
+  %inner.cmp = icmp slt i32 %inner.iv.next, %invar.add
+  br i1 %inner.cmp, label %inner, label %inner.exit
+
+inner.exit:
+  br label %outer.latch
+
+outer.latch:
+  %merge = phi i32 [ 0, %outer.header ], [ %invar, %inner.exit ]
+  call void @use(i32 %merge)
+  %tmp21 = add i32 %outer.iv, 1
+  br i1 true, label %exit, label %outer.header
+
+exit:
+  ret void
+}
+
+declare void @use(i32)
-- 
2.7.4