If a loop termination compare instruction is the only use of its stride,

and the compaison is against a constant value, try eliminate the stride
by moving the compare instruction to another stride and change its
constant operand accordingly. e.g.

loop:
...
v1 = v1 + 3
v2 = v2 + 1
if (v2 < 10) goto loop
=>
loop:
...
v1 = v1 + 3
if (v1 < 30) goto loop


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

2 files changed, 86 insertions, 0 deletions

diff --git a/test/CodeGen/X86/loop-strength-reduce3.ll b/test/CodeGen/X86/loop-strength-reduce3.ll
new file mode 100644
index 0000000..4e95bdd
--- /dev/null
+++ b/test/CodeGen/X86/loop-strength-reduce3.ll
@@ -0,0 +1,37 @@
+; RUN: llvm-as < %s | llc -march=x86 | grep cmp | grep 240
+; RUN: llvm-as < %s | llc -march=x86 | grep inc | count 1
+
+define i32 @foo(i32 %A, i32 %B, i32 %C, i32 %D) {
+entry:
+	%tmp2955 = icmp sgt i32 %C, 0		; <i1> [#uses=1]
+	br i1 %tmp2955, label %bb26.outer.us, label %bb40.split
+
+bb26.outer.us:		; preds = %bb26.bb32_crit_edge.us, %entry
+	%i.044.0.ph.us = phi i32 [ 0, %entry ], [ %indvar.next57, %bb26.bb32_crit_edge.us ]		; <i32> [#uses=2]
+	%k.1.ph.us = phi i32 [ 0, %entry ], [ %k.0.us, %bb26.bb32_crit_edge.us ]		; <i32> [#uses=1]
+	%tmp3.us = mul i32 %i.044.0.ph.us, 6		; <i32> [#uses=1]
+	br label %bb1.us
+
+bb1.us:		; preds = %bb1.us, %bb26.outer.us
+	%j.053.us = phi i32 [ 0, %bb26.outer.us ], [ %tmp25.us, %bb1.us ]		; <i32> [#uses=2]
+	%k.154.us = phi i32 [ %k.1.ph.us, %bb26.outer.us ], [ %k.0.us, %bb1.us ]		; <i32> [#uses=1]
+	%tmp5.us = add i32 %tmp3.us, %j.053.us		; <i32> [#uses=1]
+	%tmp7.us = shl i32 %D, %tmp5.us		; <i32> [#uses=2]
+	%tmp9.us = icmp eq i32 %tmp7.us, %B		; <i1> [#uses=1]
+	%tmp910.us = zext i1 %tmp9.us to i32		; <i32> [#uses=1]
+	%tmp12.us = and i32 %tmp7.us, %A		; <i32> [#uses=1]
+	%tmp19.us = and i32 %tmp12.us, %tmp910.us		; <i32> [#uses=1]
+	%k.0.us = add i32 %tmp19.us, %k.154.us		; <i32> [#uses=3]
+	%tmp25.us = add i32 %j.053.us, 1		; <i32> [#uses=2]
+	%tmp29.us = icmp slt i32 %tmp25.us, %C		; <i1> [#uses=1]
+	br i1 %tmp29.us, label %bb1.us, label %bb26.bb32_crit_edge.us
+
+bb26.bb32_crit_edge.us:		; preds = %bb1.us
+	%indvar.next57 = add i32 %i.044.0.ph.us, 1		; <i32> [#uses=2]
+	%exitcond = icmp eq i32 %indvar.next57, 40		; <i1> [#uses=1]
+	br i1 %exitcond, label %bb40.split, label %bb26.outer.us
+
+bb40.split:		; preds = %bb26.bb32_crit_edge.us, %entry
+	%k.1.lcssa.lcssa.us-lcssa = phi i32 [ %k.0.us, %bb26.bb32_crit_edge.us ], [ 0, %entry ]		; <i32> [#uses=1]
+	ret i32 %k.1.lcssa.lcssa.us-lcssa
+}
diff --git a/test/CodeGen/X86/loop-strength-reduce4.ll b/test/CodeGen/X86/loop-strength-reduce4.ll
new file mode 100644
index 0000000..711f223
--- /dev/null
+++ b/test/CodeGen/X86/loop-strength-reduce4.ll
@@ -0,0 +1,49 @@
+; RUN: llvm-as < %s | llc -march=x86 | grep cmp | grep 64
+; RUN: llvm-as < %s | llc -march=x86 | not grep inc
+
+@state = external global [0 x i32]		; <[0 x i32]*> [#uses=4]
+@S = external global [0 x i32]		; <[0 x i32]*> [#uses=4]
+
+define i32 @foo() {
+entry:
+	br label %bb
+
+bb:		; preds = %bb, %entry
+	%indvar = phi i32 [ 0, %entry ], [ %indvar.next, %bb ]		; <i32> [#uses=2]
+	%t.063.0 = phi i32 [ 0, %entry ], [ %tmp47, %bb ]		; <i32> [#uses=1]
+	%j.065.0 = shl i32 %indvar, 2		; <i32> [#uses=4]
+	%tmp3 = getelementptr [0 x i32]* @state, i32 0, i32 %j.065.0		; <i32*> [#uses=2]
+	%tmp4 = load i32* %tmp3, align 4		; <i32> [#uses=1]
+	%tmp6 = getelementptr [0 x i32]* @S, i32 0, i32 %t.063.0		; <i32*> [#uses=1]
+	%tmp7 = load i32* %tmp6, align 4		; <i32> [#uses=1]
+	%tmp8 = xor i32 %tmp7, %tmp4		; <i32> [#uses=2]
+	store i32 %tmp8, i32* %tmp3, align 4
+	%tmp1378 = or i32 %j.065.0, 1		; <i32> [#uses=1]
+	%tmp16 = getelementptr [0 x i32]* @state, i32 0, i32 %tmp1378		; <i32*> [#uses=2]
+	%tmp17 = load i32* %tmp16, align 4		; <i32> [#uses=1]
+	%tmp19 = getelementptr [0 x i32]* @S, i32 0, i32 %tmp8		; <i32*> [#uses=1]
+	%tmp20 = load i32* %tmp19, align 4		; <i32> [#uses=1]
+	%tmp21 = xor i32 %tmp20, %tmp17		; <i32> [#uses=2]
+	store i32 %tmp21, i32* %tmp16, align 4
+	%tmp2680 = or i32 %j.065.0, 2		; <i32> [#uses=1]
+	%tmp29 = getelementptr [0 x i32]* @state, i32 0, i32 %tmp2680		; <i32*> [#uses=2]
+	%tmp30 = load i32* %tmp29, align 4		; <i32> [#uses=1]
+	%tmp32 = getelementptr [0 x i32]* @S, i32 0, i32 %tmp21		; <i32*> [#uses=1]
+	%tmp33 = load i32* %tmp32, align 4		; <i32> [#uses=1]
+	%tmp34 = xor i32 %tmp33, %tmp30		; <i32> [#uses=2]
+	store i32 %tmp34, i32* %tmp29, align 4
+	%tmp3982 = or i32 %j.065.0, 3		; <i32> [#uses=1]
+	%tmp42 = getelementptr [0 x i32]* @state, i32 0, i32 %tmp3982		; <i32*> [#uses=2]
+	%tmp43 = load i32* %tmp42, align 4		; <i32> [#uses=1]
+	%tmp45 = getelementptr [0 x i32]* @S, i32 0, i32 %tmp34		; <i32*> [#uses=1]
+	%tmp46 = load i32* %tmp45, align 4		; <i32> [#uses=1]
+	%tmp47 = xor i32 %tmp46, %tmp43		; <i32> [#uses=3]
+	store i32 %tmp47, i32* %tmp42, align 4
+	%indvar.next = add i32 %indvar, 1		; <i32> [#uses=2]
+	%exitcond = icmp eq i32 %indvar.next, 4		; <i1> [#uses=1]
+	br i1 %exitcond, label %bb57, label %bb
+
+bb57:		; preds = %bb
+	%tmp59 = and i32 %tmp47, 255		; <i32> [#uses=1]
+	ret i32 %tmp59
+}