[LPM] Fix PR18642, a pretty nasty bug in IndVars that "never mattered"

because of the inside-out run of LoopSimplify in the LoopPassManager and
the fact that LoopSimplify couldn't be "preserved" across two
independent LoopPassManagers.

Anyways, in that case, IndVars wasn't correctly preserving an LCSSA PHI
node because it thought it was rewriting (via SCEV) the incoming value
to a loop invariant value. While it may well be invariant for the
current loop, it may be rewritten in terms of an enclosing loop's
values. This in and of itself is fine, as the LCSSA PHI node in the
enclosing loop for the inner loop value we're rewriting will have its
own LCSSA PHI node if used outside of the enclosing loop. With me so
far?

Well, the current loop and the enclosing loop may share an exiting
block and exit block, and when they do they also share LCSSA PHI nodes.
In this case, its not valid to RAUW through the LCSSA PHI node.

Expected crazy test included.

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

2 files changed, 74 insertions, 7 deletions

diff --git a/lib/Transforms/Scalar/IndVarSimplify.cpp b/lib/Transforms/Scalar/IndVarSimplify.cpp
index 6f32549fdd..dfcd11fb4c 100644
--- a/lib/Transforms/Scalar/IndVarSimplify.cpp
+++ b/lib/Transforms/Scalar/IndVarSimplify.cpp
@@ -497,6 +497,21 @@ void IndVarSimplify::RewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter) {
 
     unsigned NumPreds = PN->getNumIncomingValues();
 
+    // We would like to be able to RAUW single-incoming value PHI nodes. We
+    // have to be certain this is safe even when this is an LCSSA PHI node.
+    // While the computed exit value is no longer varying in *this* loop, the
+    // exit block may be an exit block for an outer containing loop as well,
+    // the exit value may be varying in the outer loop, and thus it may still
+    // require an LCSSA PHI node. The safe case is when this is
+    // single-predecessor PHI node (LCSSA) and the exit block containing it is
+    // part of the enclosing loop, or this is the outer most loop of the nest.
+    // In either case the exit value could (at most) be varying in the same
+    // loop body as the phi node itself. Thus if it is in turn used outside of
+    // an enclosing loop it will only be via a separate LCSSA node.
+    bool LCSSASafePhiForRAUW =
+        NumPreds == 1 &&
+        (!L->getParentLoop() || L->getParentLoop() == LI->getLoopFor(ExitBB));
+
     // Iterate over all of the PHI nodes.
     BasicBlock::iterator BBI = ExitBB->begin();
     while ((PN = dyn_cast<PHINode>(BBI++))) {
@@ -597,17 +612,18 @@ void IndVarSimplify::RewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter) {
         if (isInstructionTriviallyDead(Inst, TLI))
           DeadInsts.push_back(Inst);
 
-        if (NumPreds == 1) {
-          // Completely replace a single-pred PHI. This is safe, because the
-          // NewVal won't be variant in the loop, so we don't need an LCSSA phi
-          // node anymore.
+        // If we determined that this PHI is safe to replace even if an LCSSA
+        // PHI, do so.
+        if (LCSSASafePhiForRAUW) {
           PN->replaceAllUsesWith(ExitVal);
           PN->eraseFromParent();
         }
       }
-      if (NumPreds != 1) {
-        // Clone the PHI and delete the original one. This lets IVUsers and
-        // any other maps purge the original user from their records.
+
+      // If we were unable to completely replace the PHI node, clone the PHI
+      // and delete the original one. This lets IVUsers and any other maps
+      // purge the original user from their records.
+      if (!LCSSASafePhiForRAUW) {
         PHINode *NewPN = cast<PHINode>(PN->clone());
         NewPN->takeName(PN);
         NewPN->insertBefore(PN);
diff --git a/test/Transforms/IndVarSimplify/lcssa-preservation.ll b/test/Transforms/IndVarSimplify/lcssa-preservation.ll
new file mode 100644
index 0000000000..f69c96ce02
--- /dev/null
+++ b/test/Transforms/IndVarSimplify/lcssa-preservation.ll
@@ -0,0 +1,51 @@
+; RUN: opt < %s -indvars -S | FileCheck %s
+;
+; Make sure IndVars preserves LCSSA form, especially across loop nests. 
+
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
+
+define void @PR18642(i32 %x) {
+; CHECK-LABEL: @PR18642(
+entry:
+  br label %outer.header
+; CHECK:   br label %outer.header
+
+outer.header:
+; CHECK: outer.header:
+  %outer.iv = phi i32 [ 0, %entry ], [ %x, %outer.latch ]
+  br label %inner.header
+; CHECK:   %[[SCEV_EXPANDED:.*]] = add i32
+; CHECK:   br label %inner.header
+
+inner.header:
+; CHECK: inner.header:
+  %inner.iv = phi i32 [ undef, %outer.header ], [ %inc, %inner.latch ]
+  %cmp1 = icmp slt i32 %inner.iv, %outer.iv
+  br i1 %cmp1, label %inner.latch, label %outer.latch
+; CHECK:   br i1 {{.*}}, label %inner.latch, label %outer.latch
+
+inner.latch:
+; CHECK: inner.latch:
+  %inc = add nsw i32 %inner.iv, 1
+  %cmp2 = icmp slt i32 %inner.iv, %outer.iv
+  br i1 %cmp2, label %inner.header, label %exit
+; CHECK:   br i1 {{.*}}, label %inner.header, label %[[EXIT_FROM_INNER:.*]]
+
+outer.latch:
+; CHECK: outer.latch:
+  br i1 undef, label %outer.header, label %exit
+; CHECK:   br i1 {{.*}}, label %outer.header, label %[[EXIT_FROM_OUTER:.*]]
+
+; CHECK: [[EXIT_FROM_INNER]]:
+; CHECK-NEXT: %[[LCSSA:.*]] = phi i32 [ %[[SCEV_EXPANDED]], %inner.latch ]
+; CHECK-NEXT: br label %exit
+
+; CHECK: [[EXIT_FROM_OUTER]]:
+; CHECK-NEXT: br label %exit
+
+exit:
+; CHECK: exit:
+  %exit.phi = phi i32 [ %inc, %inner.latch ], [ undef, %outer.latch ]
+; CHECK-NEXT: phi i32 [ %[[LCSSA]], %[[EXIT_FROM_INNER]] ], [ undef, %[[EXIT_FROM_OUTER]] ]
+  ret void
+}