Reapply r198478 "Fix PR18361: Invalidate LoopDispositions after LoopSimplify hoists things."

Now with a fix for PR18384: ValueHandleBase::ValueIsDeleted.

We need to invalidate SCEV's loop info when we delete a block, even if no values are hoisted.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@198631 91177308-0d34-0410-b5e6-96231b3b80d8

4 files changed, 211 insertions, 7 deletions

diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h
index a397046315..26dd4dd5fc 100644
--- a/include/llvm/Analysis/ScalarEvolution.h
+++ b/include/llvm/Analysis/ScalarEvolution.h
@@ -784,6 +784,13 @@ namespace llvm {
     /// disconnect it from a def-use chain linking it to a loop.
     void forgetValue(Value *V);
 
+    /// \brief Called when the client has changed the disposition of values in
+    /// this loop.
+    ///
+    /// We don't have a way to invalidate per-loop dispositions. Clear and
+    /// recompute is simpler.
+    void forgetLoopDispositions(const Loop *L) { LoopDispositions.clear(); }
+
     /// GetMinTrailingZeros - Determine the minimum number of zero bits that S
     /// is guaranteed to end in (at every loop iteration).  It is, at the same
     /// time, the minimum number of times S is divisible by 2.  For example,
diff --git a/lib/Transforms/Utils/LoopSimplify.cpp b/lib/Transforms/Utils/LoopSimplify.cpp
index 6d5f16ca33..07cc43f885 100644
--- a/lib/Transforms/Utils/LoopSimplify.cpp
+++ b/lib/Transforms/Utils/LoopSimplify.cpp
@@ -309,6 +309,7 @@ ReprocessLoop:
       // Attempt to hoist out all instructions except for the
       // comparison and the branch.
       bool AllInvariant = true;
+      bool AnyInvariant = false;
       for (BasicBlock::iterator I = ExitingBlock->begin(); &*I != BI; ) {
         Instruction *Inst = I++;
         // Skip debug info intrinsics.
@@ -316,12 +317,19 @@ ReprocessLoop:
           continue;
         if (Inst == CI)
           continue;
-        if (!L->makeLoopInvariant(Inst, Changed,
-                                  Preheader ? Preheader->getTerminator() : 0)) {
+        if (!L->makeLoopInvariant(Inst, AnyInvariant,
+                                 Preheader ? Preheader->getTerminator() : 0)) {
           AllInvariant = false;
           break;
         }
       }
+      if (AnyInvariant) {
+        Changed = true;
+        // The loop disposition of all SCEV expressions that depend on any
+        // hoisted values have also changed.
+        if (SE)
+          SE->forgetLoopDispositions(L);
+      }
       if (!AllInvariant) continue;
 
       // The block has now been cleared of all instructions except for
@@ -334,11 +342,10 @@ ReprocessLoop:
       DEBUG(dbgs() << "LoopSimplify: Eliminating exiting block "
                    << ExitingBlock->getName() << "\n");
 
-      // If any reachable control flow within this loop has changed, notify
-      // ScalarEvolution. Currently assume the parent loop doesn't change
-      // (spliting edges doesn't count). If blocks, CFG edges, or other values
-      // in the parent loop change, then we need call to forgetLoop() for the
-      // parent instead.
+      // Notify ScalarEvolution before deleting this block. Currently assume the
+      // parent loop doesn't change (spliting edges doesn't count). If blocks,
+      // CFG edges, or other values in the parent loop change, then we need call
+      // to forgetLoop() for the parent instead.
       if (SE)
         SE->forgetLoop(L);
 
diff --git a/test/Transforms/LoopSimplify/ashr-crash.ll b/test/Transforms/LoopSimplify/ashr-crash.ll
new file mode 100644
index 0000000000..f736eefc9b
--- /dev/null
+++ b/test/Transforms/LoopSimplify/ashr-crash.ll
@@ -0,0 +1,80 @@
+; RUN: opt -basicaa -loop-rotate -licm -instcombine -indvars -loop-unroll -S %s | FileCheck %s
+;
+; PR18361: ScalarEvolution::getAddRecExpr():
+;          Assertion `isLoopInvariant(Operands[i],...
+;
+; After a series of loop optimizations, SCEV's LoopDispositions grow stale.
+; In particular, LoopSimplify hoists %cmp4, resulting in this SCEV for %add:
+; {(zext i1 %cmp4 to i32),+,1}<nw><%for.cond1.preheader>
+;
+; When recomputing the SCEV for %ashr, we truncate the operands to get:
+; (zext i1 %cmp4 to i16)
+;
+; This SCEV was never mapped to a value so never invalidated. It's
+; loop disposition is still marked as non-loop-invariant, which is
+; inconsistent with the AddRec.
+
+target datalayout = "e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx"
+
+@d = common global i32 0, align 4
+@a = common global i32 0, align 4
+@c = common global i32 0, align 4
+@b = common global i32 0, align 4
+
+; Check that the def-use chain that leads to the bad SCEV is still
+; there, and part of it is hoisted to the entry block.
+;
+; CHECK-LABEL: @foo
+; CHECK-LABEL: entry:
+; CHECK: %cmp4
+; CHECK-LABEL: for.cond1.preheader:
+; CHECK-LABEL: for.body3:
+; CHECK: %1 = zext i1 %cmp4 to i32
+; CHECK: %xor = xor i32 %1, 1
+define void @foo() {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc7, %entry
+  %storemerge = phi i32 [ 0, %entry ], [ %inc8, %for.inc7 ]
+  %f.0 = phi i32 [ undef, %entry ], [ %f.1, %for.inc7 ]
+  store i32 %storemerge, i32* @d, align 4
+  %cmp = icmp slt i32 %storemerge, 1
+  br i1 %cmp, label %for.cond1, label %for.end9
+
+for.cond1:                                        ; preds = %for.cond, %for.body3
+  %storemerge1 = phi i32 [ %inc, %for.body3 ], [ 0, %for.cond ]
+  %f.1 = phi i32 [ %xor, %for.body3 ], [ %f.0, %for.cond ]
+  store i32 %storemerge1, i32* @a, align 4
+  %cmp2 = icmp slt i32 %storemerge1, 1
+  br i1 %cmp2, label %for.body3, label %for.inc7
+
+for.body3:                                        ; preds = %for.cond1
+  %0 = load i32* @c, align 4
+  %cmp4 = icmp sge i32 %storemerge1, %0
+  %conv = zext i1 %cmp4 to i32
+  %1 = load i32* @d, align 4
+  %add = add nsw i32 %conv, %1
+  %sext = shl i32 %add, 16
+  %conv6 = ashr exact i32 %sext, 16
+  %xor = xor i32 %conv6, 1
+  %inc = add nsw i32 %storemerge1, 1
+  br label %for.cond1
+
+for.inc7:                                         ; preds = %for.cond1
+  %2 = load i32* @d, align 4
+  %inc8 = add nsw i32 %2, 1
+  br label %for.cond
+
+for.end9:                                         ; preds = %for.cond
+  %cmp10 = icmp sgt i32 %f.0, 0
+  br i1 %cmp10, label %if.then, label %if.end
+
+if.then:                                          ; preds = %for.end9
+  store i32 0, i32* @b, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %if.then, %for.end9
+  ret void
+}
diff --git a/test/Transforms/LoopSimplify/notify-scev.ll b/test/Transforms/LoopSimplify/notify-scev.ll
new file mode 100644
index 0000000000..ee8e2eec9b
--- /dev/null
+++ b/test/Transforms/LoopSimplify/notify-scev.ll
@@ -0,0 +1,110 @@
+; RUN: opt -indvars -S %s | FileCheck %s
+;
+; PR18384: ValueHandleBase::ValueIsDeleted.
+;
+; Ensure that LoopSimplify calls ScalarEvolution::forgetLoop before
+; deleting a block, regardless of whether any values were hoisted out
+; of the block.
+
+target datalayout = "e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-darwin"
+
+%struct.Params = type { [2 x [4 x [16 x i16]]] }
+
+; Verify that the loop tail is deleted, and we don't crash!
+;
+; CHECK-LABEL: @t
+; CHECK-LABEL: for.cond127.preheader:
+; CHECK-NOT: for.cond127:
+; CHECK-LABEL: for.body129:
+define void @t() {
+entry:
+  br label %for.body102
+
+for.body102:
+  br i1 undef, label %for.cond127.preheader, label %for.inc203
+
+for.cond127.preheader:
+  br label %for.body129
+
+for.cond127:
+  %cmp128 = icmp slt i32 %inc191, 2
+  br i1 %cmp128, label %for.body129, label %for.end192
+
+for.body129:
+  %uv.013 = phi i32 [ 0, %for.cond127.preheader ], [ %inc191, %for.cond127 ]
+  %idxprom130 = sext i32 %uv.013 to i64
+  br i1 undef, label %for.cond135.preheader.lr.ph, label %for.end185
+
+for.cond135.preheader.lr.ph:
+  br i1 undef, label %for.cond135.preheader.lr.ph.split.us, label %for.cond135.preheader.lr.ph.split_crit_edge
+
+for.cond135.preheader.lr.ph.split_crit_edge:
+  br label %for.cond135.preheader.lr.ph.split
+
+for.cond135.preheader.lr.ph.split.us:
+  br label %for.cond135.preheader.us
+
+for.cond135.preheader.us:
+  %block_y.09.us = phi i32 [ 0, %for.cond135.preheader.lr.ph.split.us ], [ %add184.us, %for.cond132.us ]
+  br i1 true, label %for.cond138.preheader.lr.ph.us, label %for.end178.us
+
+for.end178.us:
+  %add184.us = add nsw i32 %block_y.09.us, 4
+  br i1 undef, label %for.end185split.us-lcssa.us, label %for.cond132.us
+
+for.end174.us:
+  br i1 undef, label %for.cond138.preheader.us, label %for.cond135.for.end178_crit_edge.us
+
+for.inc172.us:
+  br i1 undef, label %for.cond142.preheader.us, label %for.end174.us
+
+for.body145.us:
+  %arrayidx163.us = getelementptr inbounds %struct.Params* undef, i64 0, i32 0, i64 %idxprom130, i64 %idxprom146.us
+  br i1 undef, label %for.body145.us, label %for.inc172.us
+
+for.cond142.preheader.us:
+  %j.04.us = phi i32 [ %block_y.09.us, %for.cond138.preheader.us ], [ undef, %for.inc172.us ]
+  %idxprom146.us = sext i32 %j.04.us to i64
+  br label %for.body145.us
+
+for.cond138.preheader.us:
+  br label %for.cond142.preheader.us
+
+for.cond132.us:
+  br i1 undef, label %for.cond135.preheader.us, label %for.cond132.for.end185_crit_edge.us-lcssa.us
+
+for.cond138.preheader.lr.ph.us:
+  br label %for.cond138.preheader.us
+
+for.cond135.for.end178_crit_edge.us:
+  br label %for.end178.us
+
+for.end185split.us-lcssa.us:
+  br label %for.end185split
+
+for.cond132.for.end185_crit_edge.us-lcssa.us:
+  br label %for.cond132.for.end185_crit_edge
+
+for.cond135.preheader.lr.ph.split:
+  br label %for.end185split
+
+for.end185split:
+  br label %for.end185
+
+for.cond132.for.end185_crit_edge:
+  br label %for.end185
+
+for.end185:
+  %inc191 = add nsw i32 %uv.013, 1
+  br i1 false, label %for.end192, label %for.cond127
+
+for.end192:
+  br label %for.inc203
+
+for.inc203:
+  br label %for.end205
+
+for.end205:
+  ret void
+}