5 files changed, 294 insertions, 8 deletions
diff --git a/test/Transforms/IndVarSimplify/elim-extend.ll b/test/Transforms/IndVarSimplify/elim-extend.ll
new file mode 100644
index 0000000..0367e11
--- /dev/null
+++ b/test/Transforms/IndVarSimplify/elim-extend.ll
@@ -0,0 +1,153 @@
+; RUN: opt < %s -indvars -disable-iv-rewrite -S | FileCheck %s
+
+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"
+
+; IV with constant start, preinc and postinc sign extends, with and without NSW.
+; IV rewrite only removes one sext. WidenIVs removes all three.
+define void @postincConstIV(i8* %base, i32 %limit) nounwind {
+entry:
+  br label %loop
+; CHECK: loop:
+; CHECK-NOT: sext
+; CHECK: exit:
+loop:
+  %iv = phi i32 [ %postiv, %loop ], [ 0, %entry ]
+  %ivnsw = phi i32 [ %postivnsw, %loop ], [ 0, %entry ]
+  %preofs = sext i32 %iv to i64
+  %preadr = getelementptr i8* %base, i64 %preofs
+  store i8 0, i8* %preadr
+  %postiv = add i32 %iv, 1
+  %postofs = sext i32 %postiv to i64
+  %postadr = getelementptr i8* %base, i64 %postofs
+  store i8 0, i8* %postadr
+  %postivnsw = add nsw i32 %ivnsw, 1
+  %postofsnsw = sext i32 %postivnsw to i64
+  %postadrnsw = getelementptr i8* %base, i64 %postofsnsw
+  store i8 0, i8* %postadrnsw
+  %cond = icmp sgt i32 %limit, %iv
+  br i1 %cond, label %loop, label %exit
+exit:
+  br label %return
+return:
+  ret void
+}
+
+; IV with nonconstant start, preinc and postinc sign extends,
+; with and without NSW.
+; As with postincConstIV, WidenIVs removes all three sexts.
+define void @postincVarIV(i8* %base, i32 %init, i32 %limit) nounwind {
+entry:
+  %precond = icmp sgt i32 %limit, %init
+  br i1 %precond, label %loop, label %return
+; CHECK: loop:
+; CHECK-NOT: sext
+; CHECK: exit:
+loop:
+  %iv = phi i32 [ %postiv, %loop ], [ %init, %entry ]
+  %ivnsw = phi i32 [ %postivnsw, %loop ], [ %init, %entry ]
+  %preofs = sext i32 %iv to i64
+  %preadr = getelementptr i8* %base, i64 %preofs
+  store i8 0, i8* %preadr
+  %postiv = add i32 %iv, 1
+  %postofs = sext i32 %postiv to i64
+  %postadr = getelementptr i8* %base, i64 %postofs
+  store i8 0, i8* %postadr
+  %postivnsw = add nsw i32 %ivnsw, 1
+  %postofsnsw = sext i32 %postivnsw to i64
+  %postadrnsw = getelementptr i8* %base, i64 %postofsnsw
+  store i8 0, i8* %postadrnsw
+  %cond = icmp sgt i32 %limit, %postiv
+  br i1 %cond, label %loop, label %exit
+exit:
+  br label %return
+return:
+  ret void
+}
+
+; Test sign extend elimination in the inner and outer loop.
+; %outercount is straightforward to widen, besides being in an outer loop.
+; %innercount is currently blocked by lcssa, so is not widened.
+; %inneriv can be widened only after proving it has no signed-overflow
+;   based on the loop test.
+define void @nestedIV(i8* %address, i32 %limit) nounwind {
+entry:
+  %limitdec = add i32 %limit, -1
+  br label %outerloop
+
+; CHECK: outerloop:
+;
+; Eliminate %ofs1 after widening outercount.
+; CHECK-NOT: sext
+; CHECK: getelementptr
+;
+; IV rewriting hoists a gep into this block. We don't like that.
+; CHECK-NOT: getelementptr
+outerloop:
+  %outercount   = phi i32 [ %outerpostcount, %outermerge ], [ 0, %entry ]
+  %innercount = phi i32 [ %innercount.merge, %outermerge ], [ 0, %entry ]
+
+  %outercountdec = add i32 %outercount, -1
+  %ofs1 = sext i32 %outercountdec to i64
+  %adr1 = getelementptr i8* %address, i64 %ofs1
+  store i8 0, i8* %adr1
+
+  br label %innerpreheader
+
+innerpreheader:
+  %innerprecmp = icmp sgt i32 %limitdec, %innercount
+  br i1 %innerprecmp, label %innerloop, label %outermerge
+
+; CHECK: innerloop:
+;
+; Eliminate %ofs2 after widening inneriv.
+; Eliminate %ofs3 after normalizing sext(innerpostiv)
+; CHECK-NOT: sext
+; CHECK: getelementptr
+;
+; FIXME: We should check that indvars does not increase the number of
+; IVs in this loop. sext elimination plus LFTR currently results in 2 final
+; IVs. Waiting to remove LFTR.
+innerloop:
+  %inneriv = phi i32 [ %innerpostiv, %innerloop ], [ %innercount, %innerpreheader ]
+  %innerpostiv = add i32 %inneriv, 1
+
+  %ofs2 = sext i32 %inneriv to i64
+  %adr2 = getelementptr i8* %address, i64 %ofs2
+  store i8 0, i8* %adr2
+
+  %ofs3 = sext i32 %innerpostiv to i64
+  %adr3 = getelementptr i8* %address, i64 %ofs3
+  store i8 0, i8* %adr3
+
+  %innercmp = icmp sgt i32 %limitdec, %innerpostiv
+  br i1 %innercmp, label %innerloop, label %innerexit
+
+innerexit:
+  %innercount.lcssa = phi i32 [ %innerpostiv, %innerloop ]
+  br label %outermerge
+
+; CHECK: outermerge:
+;
+; Eliminate %ofs4 after widening outercount
+; CHECK-NOT: sext
+; CHECK: getelementptr
+;
+; TODO: Eliminate %ofs5 after removing lcssa
+outermerge:
+  %innercount.merge = phi i32 [ %innercount.lcssa, %innerexit ], [ %innercount, %innerpreheader ]
+
+  %ofs4 = sext i32 %outercount to i64
+  %adr4 = getelementptr i8* %address, i64 %ofs4
+  store i8 0, i8* %adr4
+
+  %ofs5 = sext i32 %innercount.merge to i64
+  %adr5 = getelementptr i8* %address, i64 %ofs5
+  store i8 0, i8* %adr5
+
+  %outerpostcount = add i32 %outercount, 1
+  %tmp47 = icmp slt i32 %outerpostcount, %limit
+  br i1 %tmp47, label %outerloop, label %return
+
+return:
+  ret void
+}
diff --git a/test/Transforms/IndVarSimplify/iv-sext.ll b/test/Transforms/IndVarSimplify/iv-sext.ll
index 3e90873..6c7a627 100644
--- a/test/Transforms/IndVarSimplify/iv-sext.ll
+++ b/test/Transforms/IndVarSimplify/iv-sext.ll
@@ -1,6 +1,4 @@
-; RUN: opt < %s -indvars -S > %t
-; RUN: grep {= sext} %t | count 4
-; RUN: grep {phi i64} %t | count 2
+; RUN: opt < %s -indvars -S | FileCheck %s
 
 ; Indvars should be able to promote the hiPart induction variable in the
 ; inner loop to i64.
@@ -18,6 +16,9 @@ bb.nph22:		; preds = %entry
 	%tmp3 = add i32 %bandEdgeIndex, -1		; <i32> [#uses=2]
 	br label %bb
 
+; CHECK: bb:
+; CHECK: phi i64
+; CHECK-NOT: phi i64
 bb:		; preds = %bb8, %bb.nph22
 	%distERBhi.121 = phi float [ %distERBhi.2.lcssa, %bb8 ], [ 0.000000e+00, %bb.nph22 ]		; <float> [#uses=2]
 	%distERBlo.120 = phi float [ %distERBlo.0.lcssa, %bb8 ], [ 0.000000e+00, %bb.nph22 ]		; <float> [#uses=2]
@@ -28,6 +29,7 @@ bb:		; preds = %bb8, %bb.nph22
 	%tmp4 = icmp sgt i32 %part.016, 0		; <i1> [#uses=1]
 	br i1 %tmp4, label %bb1, label %bb3.preheader
 
+; CHECK: bb1:
 bb1:		; preds = %bb
 	%tmp5 = add i32 %part.016, -1		; <i32> [#uses=1]
 	%tmp6 = sext i32 %tmp5 to i64		; <i64> [#uses=1]
@@ -86,7 +88,10 @@ bb5.preheader:		; preds = %bb3.bb5.preheader_crit_edge, %bb3.preheader
 
 bb.nph12:		; preds = %bb5.preheader
 	br label %bb4
-
+; CHECK: bb4:
+; CHECK: phi i64
+; CHECK-NOT: phi i64
+; CHECK-NOT: sext
 bb4:		; preds = %bb5, %bb.nph12
 	%distERBhi.29 = phi float [ %tmp30, %bb5 ], [ %distERBhi.0.ph, %bb.nph12 ]		; <float> [#uses=1]
 	%hiPart.08 = phi i32 [ %tmp31, %bb5 ], [ %hiPart.119, %bb.nph12 ]		; <i32> [#uses=2]
@@ -102,6 +107,7 @@ bb4:		; preds = %bb5, %bb.nph12
 	%tmp35 = fadd float %tmp34, %peakCount.27		; <float> [#uses=2]
 	br label %bb5
 
+; CHECK: bb5:
 bb5:		; preds = %bb4
 	%.not = fcmp olt float %tmp30, 2.500000e+00		; <i1> [#uses=1]
 	%tmp36 = icmp sgt i32 %tmp3, %tmp31		; <i1> [#uses=1]
diff --git a/test/Transforms/IndVarSimplify/iv-zext.ll b/test/Transforms/IndVarSimplify/iv-zext.ll
index 80a77b6..00018ec 100644
--- a/test/Transforms/IndVarSimplify/iv-zext.ll
+++ b/test/Transforms/IndVarSimplify/iv-zext.ll
@@ -1,6 +1,6 @@
-; RUN: opt < %s -indvars -S > %t
-; RUN: not grep and %t
-; RUN: not grep zext %t
+; RUN: opt < %s -indvars -S | FileCheck %s
+; CHECK-NOT: and
+; CHECK-NOT: zext
 
 target datalayout = "-p:64:64:64-n:32:64"
 
diff --git a/test/Transforms/IndVarSimplify/no-iv-rewrite.ll b/test/Transforms/IndVarSimplify/no-iv-rewrite.ll
new file mode 100644
index 0000000..c35feef
--- /dev/null
+++ b/test/Transforms/IndVarSimplify/no-iv-rewrite.ll
@@ -0,0 +1,123 @@
+; RUN: opt < %s -indvars -disable-iv-rewrite -S | FileCheck %s
+;
+; Make sure that indvars isn't inserting canonical IVs.
+; This is kinda hard to do until linear function test replacement is removed.
+
+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 i32 @sum(i32* %arr, i32 %n) nounwind {
+entry:
+  %precond = icmp slt i32 0, %n
+  br i1 %precond, label %ph, label %return
+
+ph:
+  br label %loop
+
+; CHECK: loop:
+;
+; We should only have 2 IVs.
+; CHECK: phi
+; CHECK: phi
+; CHECK-NOT: phi
+;
+; sext should be eliminated while preserving gep inboundsness.
+; CHECK-NOT: sext
+; CHECK: getelementptr inbounds
+loop:
+  %i.02 = phi i32 [ 0, %ph ], [ %iinc, %loop ]
+  %s.01 = phi i32 [ 0, %ph ], [ %sinc, %loop ]
+  %ofs = sext i32 %i.02 to i64
+  %adr = getelementptr inbounds i32* %arr, i64 %ofs
+  %val = load i32* %adr
+  %sinc = add nsw i32 %s.01, %val
+  %iinc = add nsw i32 %i.02, 1
+  %cond = icmp slt i32 %iinc, %n
+  br i1 %cond, label %loop, label %exit
+
+exit:
+  %s.lcssa = phi i32 [ %sinc, %loop ]
+  br label %return
+
+return:
+  %s.0.lcssa = phi i32 [ %s.lcssa, %exit ], [ 0, %entry ]
+  ret i32 %s.0.lcssa
+}
+
+define i64 @suml(i32* %arr, i32 %n) nounwind {
+entry:
+  %precond = icmp slt i32 0, %n
+  br i1 %precond, label %ph, label %return
+
+ph:
+  br label %loop
+
+; CHECK: loop:
+;
+; We should only have 2 IVs.
+; CHECK: phi
+; CHECK: phi
+; CHECK-NOT: phi
+;
+; %ofs sext should be eliminated while preserving gep inboundsness.
+; CHECK-NOT: sext
+; CHECK: getelementptr inbounds
+; %vall sext should obviously not be eliminated
+; CHECK: sext
+loop:
+  %i.02 = phi i32 [ 0, %ph ], [ %iinc, %loop ]
+  %s.01 = phi i64 [ 0, %ph ], [ %sinc, %loop ]
+  %ofs = sext i32 %i.02 to i64
+  %adr = getelementptr inbounds i32* %arr, i64 %ofs
+  %val = load i32* %adr
+  %vall = sext i32 %val to i64
+  %sinc = add nsw i64 %s.01, %vall
+  %iinc = add nsw i32 %i.02, 1
+  %cond = icmp slt i32 %iinc, %n
+  br i1 %cond, label %loop, label %exit
+
+exit:
+  %s.lcssa = phi i64 [ %sinc, %loop ]
+  br label %return
+
+return:
+  %s.0.lcssa = phi i64 [ %s.lcssa, %exit ], [ 0, %entry ]
+  ret i64 %s.0.lcssa
+}
+
+define void @outofbounds(i32* %first, i32* %last, i32 %idx) nounwind {
+  %precond = icmp ne i32* %first, %last
+  br i1 %precond, label %ph, label %return
+
+; CHECK: ph:
+; It's not indvars' job to perform LICM on %ofs
+; CHECK-NOT: sext
+ph:
+  br label %loop
+
+; CHECK: loop:
+;
+; Preserve exactly one pointer type IV.
+; CHECK: phi i32*
+; CHECK-NOT: phi
+;
+; Don't create any extra adds.
+; CHECK-NOT: add
+;
+; Preserve gep inboundsness, and don't factor it.
+; CHECK: getelementptr inbounds i32* %ptriv, i32 1
+; CHECK-NOT: add
+loop:
+  %ptriv = phi i32* [ %first, %ph ], [ %ptrpost, %loop ]
+  %ofs = sext i32 %idx to i64
+  %adr = getelementptr inbounds i32* %ptriv, i64 %ofs
+  store i32 3, i32* %adr
+  %ptrpost = getelementptr inbounds i32* %ptriv, i32 1
+  %cond = icmp ne i32* %ptrpost, %last
+  br i1 %cond, label %loop, label %exit
+
+exit:
+  br label %return
+
+return:
+  ret void
+}
diff --git a/test/Transforms/IndVarSimplify/phi-uses-value-multiple-times.ll b/test/Transforms/IndVarSimplify/phi-uses-value-multiple-times.ll
index 34d432b..52c9e5c 100644
--- a/test/Transforms/IndVarSimplify/phi-uses-value-multiple-times.ll
+++ b/test/Transforms/IndVarSimplify/phi-uses-value-multiple-times.ll
@@ -1,4 +1,8 @@
-; RUN: opt < %s -indvars
+; RUN: opt < %s -indvars -disable-output -stats -info-output-file - | FileCheck %s
+; Check that IndVarSimplify is not creating unnecessary canonical IVs
+; that will never be used.
+; CHECK-NOT: indvars
+
 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"
 
 @ue = external global i64