Factor the code for collecting IV users out of LSR into an IVUsers class,

and generalize it so that it can be used by IndVarSimplify. Implement the
base IndVarSimplify transformation code using IVUsers. This removes
TestOrigIVForWrap and associated code, as ScalarEvolution now has enough
builtin overflow detection and folding logic to handle all the same cases,
and more. Run "opt -iv-users -analyze -disable-output" on your favorite
loop for an example of what IVUsers does.

This lets IndVarSimplify eliminate IV casts and compute trip counts in
more cases. Also, this happens to finally fix the remaining testcases
in PR1301.

Now that IndVarSimplify is being more aggressive, it occasionally runs
into the problem where ScalarEvolutionExpander's code for avoiding
duplicate expansions makes it difficult to ensure that all expanded
instructions dominate all the instructions that will use them. As a
temporary measure, IndVarSimplify now uses a FixUsesBeforeDefs function
to fix up instructions inserted by SCEVExpander. Fortunately, this code
is contained, and can be easily removed once a more comprehensive
solution is available.


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

8 files changed, 166 insertions, 14 deletions

diff --git a/test/CodeGen/X86/iv-users-in-other-loops.ll b/test/CodeGen/X86/iv-users-in-other-loops.ll
index d11b025..275feba 100644
--- a/test/CodeGen/X86/iv-users-in-other-loops.ll
+++ b/test/CodeGen/X86/iv-users-in-other-loops.ll
@@ -1,10 +1,11 @@
 ; RUN: llvm-as < %s | llc -march=x86-64 -f -o %t
 ; RUN: grep inc %t | count 1
 ; RUN: grep dec %t | count 2
-; RUN: grep addq %t | count 13
-; RUN: grep leaq %t | count 8
-; RUN: grep leal %t | count 4
-; RUN: grep movq %t | count 5
+; RUN: grep addq %t | count 8
+; RUN: grep addb %t | count 2
+; RUN: grep leaq %t | count 12
+; RUN: grep leal %t | count 2
+; RUN: grep movq %t | count 4
 
 ; IV users in each of the loops from other loops shouldn't cause LSR
 ; to insert new induction variables. Previously it would create a
diff --git a/test/CodeGen/X86/masked-iv-safe.ll b/test/CodeGen/X86/masked-iv-safe.ll
index e9b80a4..e102535 100644
--- a/test/CodeGen/X86/masked-iv-safe.ll
+++ b/test/CodeGen/X86/masked-iv-safe.ll
@@ -3,14 +3,13 @@
 ; RUN: not grep movz %t
 ; RUN: not grep sar %t
 ; RUN: not grep shl %t
-; RUN: grep add %t | count 6
-; RUN: grep inc %t | count 2
-; RUN: grep dec %t | count 4
+; RUN: grep add %t | count 2
+; RUN: grep inc %t | count 4
+; RUN: grep dec %t | count 2
 ; RUN: grep lea %t | count 2
 
 ; Optimize away zext-inreg and sext-inreg on the loop induction
 ; variable using trip-count information.
-; Also, the loop-reversal algorithm kicks in twice.
 
 define void @count_up(double* %d, i64 %n) nounwind {
 entry:
diff --git a/test/CodeGen/X86/subreg-to-reg-5.ll b/test/CodeGen/X86/subreg-to-reg-5.ll
index eee751a..81b262a 100644
--- a/test/CodeGen/X86/subreg-to-reg-5.ll
+++ b/test/CodeGen/X86/subreg-to-reg-5.ll
@@ -8,7 +8,8 @@ entry:
 
 bb2:		; preds = %bb3, %entry
 	%B_addr.0.rec = phi i64 [ %indvar.next154, %bb3 ], [ 0, %entry ]		; <i64> [#uses=2]
-	br i1 false, label %bb3, label %bb4
+        %z = icmp slt i64 %B_addr.0.rec, 20000
+	br i1 %z, label %bb3, label %bb4
 
 bb3:		; preds = %bb2
 	%indvar.next154 = add i64 %B_addr.0.rec, 1		; <i64> [#uses=1]
@@ -17,7 +18,7 @@ bb3:		; preds = %bb2
 bb4:		; preds = %bb2
 	%B_addr.0 = getelementptr float* %B, i64 %B_addr.0.rec		; <float*> [#uses=1]
 	%t1 = ptrtoint float* %B_addr.0 to i64		; <i64> [#uses=1]
-	%t2 = and i64 %t1, 15		; <i64> [#uses=1]
+	%t2 = and i64 %t1, 4294967295		; <i64> [#uses=1]
 	%t3 = icmp eq i64 %t2, 0		; <i1> [#uses=1]
 	br i1 %t3, label %bb5, label %bb10.preheader
 
@@ -25,7 +26,7 @@ bb10.preheader:		; preds = %bb4
 	br label %bb9
 
 bb5:		; preds = %bb4
-	unreachable
+	ret float 7.0
 
 bb9:		; preds = %bb10.preheader
 	%t5 = getelementptr float* %B, i64 0		; <float*> [#uses=1]
diff --git a/test/Transforms/IndVarSimplify/2009-04-15-shorten-iv-vars-2.ll b/test/Transforms/IndVarSimplify/2009-04-15-shorten-iv-vars-2.ll
index 5cc595e..4d26803 100644
--- a/test/Transforms/IndVarSimplify/2009-04-15-shorten-iv-vars-2.ll
+++ b/test/Transforms/IndVarSimplify/2009-04-15-shorten-iv-vars-2.ll
@@ -1,5 +1,4 @@
-; RUN: llvm-as < %s | opt -indvars | llvm-dis | not grep {sext}
-; RUN: llvm-as < %s | opt -indvars | llvm-dis | not grep {zext}
+; RUN: llvm-as < %s | opt -indvars -instcombine | llvm-dis | not grep {\[sz\]ext}
 ; ModuleID = '<stdin>'
 ;extern int *a, *b, *c, *d, *e, *f;  /* 64 bit */
 ;extern int K[256];
diff --git a/test/Transforms/IndVarSimplify/ada-loops.ll b/test/Transforms/IndVarSimplify/ada-loops.ll
new file mode 100644
index 0000000..56325b3
--- /dev/null
+++ b/test/Transforms/IndVarSimplify/ada-loops.ll
@@ -0,0 +1,90 @@
+; RUN: llvm-as < %s | opt -indvars | llvm-dis > %t
+; RUN: grep phi %t | count 4
+; RUN: grep {= phi i32} %t | count 4
+; RUN: not grep {sext i} %t
+; RUN: not grep {zext i} %t
+; RUN: not grep {trunc i} %t
+; RUN: not grep {add i8} %t
+; PR1301
+
+; Do a bunch of analysis and prove that the loops can use an i32 trip
+; count without casting.
+
+; ModuleID = 'ada.bc'
+target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64"
+target triple = "i686-pc-linux-gnu"
+
+define void @kinds__sbytezero([256 x i32]* nocapture %a) nounwind {
+bb.thread:
+	%tmp46 = getelementptr [256 x i32]* %a, i32 0, i32 0		; <i32*> [#uses=1]
+	store i32 0, i32* %tmp46
+	br label %bb
+
+bb:		; preds = %bb, %bb.thread
+	%i.0.reg2mem.0 = phi i8 [ -128, %bb.thread ], [ %tmp8, %bb ]		; <i8> [#uses=1]
+	%tmp8 = add i8 %i.0.reg2mem.0, 1		; <i8> [#uses=3]
+	%tmp1 = sext i8 %tmp8 to i32		; <i32> [#uses=1]
+	%tmp3 = add i32 %tmp1, 128		; <i32> [#uses=1]
+	%tmp4 = getelementptr [256 x i32]* %a, i32 0, i32 %tmp3		; <i32*> [#uses=1]
+	store i32 0, i32* %tmp4
+	%0 = icmp eq i8 %tmp8, 127		; <i1> [#uses=1]
+	br i1 %0, label %return, label %bb
+
+return:		; preds = %bb
+	ret void
+}
+
+define void @kinds__ubytezero([256 x i32]* nocapture %a) nounwind {
+bb.thread:
+	%tmp35 = getelementptr [256 x i32]* %a, i32 0, i32 0		; <i32*> [#uses=1]
+	store i32 0, i32* %tmp35
+	br label %bb
+
+bb:		; preds = %bb, %bb.thread
+	%i.0.reg2mem.0 = phi i8 [ 0, %bb.thread ], [ %tmp7, %bb ]		; <i8> [#uses=1]
+	%tmp7 = add i8 %i.0.reg2mem.0, 1		; <i8> [#uses=3]
+	%tmp1 = zext i8 %tmp7 to i32		; <i32> [#uses=1]
+	%tmp3 = getelementptr [256 x i32]* %a, i32 0, i32 %tmp1		; <i32*> [#uses=1]
+	store i32 0, i32* %tmp3
+	%0 = icmp eq i8 %tmp7, -1		; <i1> [#uses=1]
+	br i1 %0, label %return, label %bb
+
+return:		; preds = %bb
+	ret void
+}
+
+define void @kinds__srangezero([21 x i32]* nocapture %a) nounwind {
+bb.thread:
+	br label %bb
+
+bb:		; preds = %bb, %bb.thread
+	%i.0.reg2mem.0 = phi i8 [ -10, %bb.thread ], [ %tmp7, %bb ]		; <i8> [#uses=2]
+	%tmp12 = sext i8 %i.0.reg2mem.0 to i32		; <i32> [#uses=1]
+	%tmp4 = add i32 %tmp12, 10		; <i32> [#uses=1]
+	%tmp5 = getelementptr [21 x i32]* %a, i32 0, i32 %tmp4		; <i32*> [#uses=1]
+	store i32 0, i32* %tmp5
+	%tmp7 = add i8 %i.0.reg2mem.0, 1		; <i8> [#uses=2]
+	%0 = icmp sgt i8 %tmp7, 10		; <i1> [#uses=1]
+	br i1 %0, label %return, label %bb
+
+return:		; preds = %bb
+	ret void
+}
+
+define void @kinds__urangezero([21 x i32]* nocapture %a) nounwind {
+bb.thread:
+	br label %bb
+
+bb:		; preds = %bb, %bb.thread
+	%i.0.reg2mem.0 = phi i8 [ 10, %bb.thread ], [ %tmp7, %bb ]		; <i8> [#uses=2]
+	%tmp12 = sext i8 %i.0.reg2mem.0 to i32		; <i32> [#uses=1]
+	%tmp4 = add i32 %tmp12, -10		; <i32> [#uses=1]
+	%tmp5 = getelementptr [21 x i32]* %a, i32 0, i32 %tmp4		; <i32*> [#uses=1]
+	store i32 0, i32* %tmp5
+	%tmp7 = add i8 %i.0.reg2mem.0, 1		; <i8> [#uses=2]
+	%0 = icmp sgt i8 %tmp7, 30		; <i1> [#uses=1]
+	br i1 %0, label %return, label %bb
+
+return:		; preds = %bb
+	ret void
+}
diff --git a/test/Transforms/IndVarSimplify/iv-zext.ll b/test/Transforms/IndVarSimplify/iv-zext.ll
new file mode 100644
index 0000000..76d48de
--- /dev/null
+++ b/test/Transforms/IndVarSimplify/iv-zext.ll
@@ -0,0 +1,33 @@
+; RUN: llvm-as < %s | opt -indvars | llvm-dis > %t
+; RUN: not grep and %t
+; RUN: not grep zext %t
+
+target datalayout = "-p:64:64:64"
+
+define void @foo(double* %d, i64 %n) nounwind {
+entry:
+	br label %loop
+
+loop:
+	%indvar = phi i64 [ 0, %entry ], [ %indvar.next, %loop ]
+	%indvar.i8 = and i64 %indvar, 255
+	%t0 = getelementptr double* %d, i64 %indvar.i8
+	%t1 = load double* %t0
+	%t2 = mul double %t1, 0.1
+	store double %t2, double* %t0
+	%indvar.i24 = and i64 %indvar, 16777215
+	%t3 = getelementptr double* %d, i64 %indvar.i24
+	%t4 = load double* %t3
+	%t5 = mul double %t4, 2.3
+	store double %t5, double* %t3
+	%t6 = getelementptr double* %d, i64 %indvar
+	%t7 = load double* %t6
+	%t8 = mul double %t7, 4.5
+	store double %t8, double* %t6
+	%indvar.next = add i64 %indvar, 1
+	%exitcond = icmp eq i64 %indvar.next, 10
+	br i1 %exitcond, label %return, label %loop
+
+return:
+	ret void
+}
diff --git a/test/Transforms/IndVarSimplify/loop_evaluate_6.ll b/test/Transforms/IndVarSimplify/loop_evaluate_6.ll
new file mode 100644
index 0000000..35fbf52
--- /dev/null
+++ b/test/Transforms/IndVarSimplify/loop_evaluate_6.ll
@@ -0,0 +1,29 @@
+; RUN: llvm-as < %s | opt -indvars -loop-deletion | llvm-dis | grep phi | count 1
+
+; Indvars should be able to evaluate this loop, allowing loop deletion
+; to delete it.
+
+define i32 @test(i32 %x_offs) nounwind readnone {
+entry:
+	%0 = icmp sgt i32 %x_offs, 4		; <i1> [#uses=1]
+	br i1 %0, label %bb.nph, label %bb2
+
+bb.nph:		; preds = %entry
+	br label %bb
+
+bb:		; preds = %bb1, %bb.nph
+	%x_offs_addr.01 = phi i32 [ %1, %bb1 ], [ %x_offs, %bb.nph ]		; <i32> [#uses=1]
+	%1 = add i32 %x_offs_addr.01, -4		; <i32> [#uses=3]
+	br label %bb1
+
+bb1:		; preds = %bb
+	%2 = icmp sgt i32 %1, 4		; <i1> [#uses=1]
+	br i1 %2, label %bb, label %bb1.bb2_crit_edge
+
+bb1.bb2_crit_edge:		; preds = %bb1
+	br label %bb2
+
+bb2:		; preds = %bb1.bb2_crit_edge, %entry
+	%x_offs_addr.0.lcssa = phi i32 [ %1, %bb1.bb2_crit_edge ], [ %x_offs, %entry ]		; <i32> [#uses=1]
+	ret i32 %x_offs_addr.0.lcssa
+}
diff --git a/test/Transforms/LoopStrengthReduce/2009-04-28-no-reduce-mul.ll b/test/Transforms/LoopStrengthReduce/2009-04-28-no-reduce-mul.ll
index 153a181..f873b3d 100644
--- a/test/Transforms/LoopStrengthReduce/2009-04-28-no-reduce-mul.ll
+++ b/test/Transforms/LoopStrengthReduce/2009-04-28-no-reduce-mul.ll
@@ -1,4 +1,4 @@
-; RUN: llvm-as < %s | opt -loop-reduce | llvm-dis | grep mul | count 3
+; RUN: llvm-as < %s | opt -loop-reduce | llvm-dis | grep {mul.*%lsr.iv} | count 2
 ; The multiply in bb2 must not be reduced to an add, as the sext causes the
 ; %1 argument to become negative after a while.
 ; ModuleID = '<stdin>'