[IndVars] Fix PR26974: make sure replaceCongruentIVs doesn't break LCSSA

Summary:
replaceCongruentIVs can break LCSSA when trying to replace IV increments
since it tries to replace all uses of a phi node with another phi node
while both of the phi nodes are not necessarily in the processed loop.
This will cause an assert in IndVars.

To fix this, we add a check to make sure that the replacement maintains
LCSSA.

Reviewers: sanjoy

Subscribers: mzolotukhin, llvm-commits

Differential Revision: http://reviews.llvm.org/D18266

llvm-svn: 263941

2 files changed, 61 insertions, 0 deletions

diff --git a/llvm/lib/Analysis/ScalarEvolutionExpander.cpp b/llvm/lib/Analysis/ScalarEvolutionExpander.cpp
index d083037a90f..4db3c7fb7f9 100644
--- a/llvm/lib/Analysis/ScalarEvolutionExpander.cpp
+++ b/llvm/lib/Analysis/ScalarEvolutionExpander.cpp
@@ -1820,6 +1820,7 @@ unsigned SCEVExpander::replaceCongruentIVs(Loop *L, const DominatorTree *DT,
                                                    IsomorphicInc->getType());
       if (OrigInc != IsomorphicInc
           && TruncExpr == SE.getSCEV(IsomorphicInc)
+          && SE.LI.replacementPreservesLCSSAForm(IsomorphicInc, OrigInc)
           && ((isa<PHINode>(OrigInc) && isa<PHINode>(IsomorphicInc))
               || hoistIVInc(OrigInc, IsomorphicInc))) {
         DEBUG_WITH_TYPE(DebugType, dbgs()
diff --git a/llvm/test/Transforms/IndVarSimplify/pr26974.ll b/llvm/test/Transforms/IndVarSimplify/pr26974.ll
new file mode 100644
index 00000000000..28a736441cd
--- /dev/null
+++ b/llvm/test/Transforms/IndVarSimplify/pr26974.ll
@@ -0,0 +1,60 @@
+; RUN: opt -indvars  -S < %s | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+; indvars will try to replace %b.0.lcssa with %t.1. If it does this,
+; it will break LCSSA.
+
+@c = external global i32, align 4
+
+; CHECK-LABEL: @fn1
+define void @fn1() {
+entry:
+  br label %for.body
+
+for.cond1.preheader:                              ; preds = %for.body
+  %0 = load i32, i32* @c, align 4
+  br i1 undef, label %for.cond1.us.preheader, label %for.cond1
+
+for.cond1.us.preheader:                           ; preds = %for.cond1.preheader
+  br label %for.cond1.us
+
+for.cond1.us:                                     ; preds = %for.cond1.us, %for.cond1.us.preheader
+  br label %for.cond1.us
+
+for.body:                                         ; preds = %for.body, %entry
+  br i1 undef, label %for.body, label %for.cond1.preheader
+
+for.cond1:                                        ; preds = %for.cond1.preheader
+  br i1 true, label %for.body9.lr.ph, label %for.cond13.preheader
+
+for.body9.lr.ph:                                  ; preds = %for.cond1
+  br i1 undef, label %for.body9.us.preheader, label %for.body9
+
+for.body9.us.preheader:                           ; preds = %for.body9.lr.ph
+  br label %for.body9.us
+
+for.body9.us:                                     ; preds = %for.body9.us, %for.body9.us.preheader
+  br label %for.body9.us
+
+for.cond13.preheader:                             ; preds = %for.body9, %for.cond1
+  %b.0.lcssa = phi i32 [ %0, %for.body9 ], [ 0, %for.cond1 ]
+  br label %for.cond13
+
+for.body9:                                        ; preds = %for.body9.lr.ph
+  br label %for.cond13.preheader
+
+for.cond13:                                       ; preds = %for.cond13, %for.cond13.preheader
+  %d.1 = phi i32 [ %t.1, %for.cond13 ], [ %0, %for.cond13.preheader ]
+  %t.1 = phi i32 [ %b.0.lcssa, %for.cond13 ], [ %0, %for.cond13.preheader ]
+  br i1 undef, label %for.cond18.preheader, label %for.cond13
+
+for.cond18.preheader:                             ; preds = %for.cond13
+  br label %for.cond18
+
+for.cond18:                                       ; preds = %for.cond18, %for.cond18.preheader
+  %b.1 = phi i32 [ %xor, %for.cond18 ], [ %b.0.lcssa, %for.cond18.preheader ]
+  %add = add nsw i32 %b.1, %d.1
+  %xor = xor i32 %add, %b.1
+  br label %for.cond18
+}