Regression is gone, don't try to find it on clean target.

llvm-svn: 33296

22 files changed, 616 insertions, 0 deletions

diff --git a/llvm/test/Transforms/LoopStrengthReduce/.cvsignore b/llvm/test/Transforms/LoopStrengthReduce/.cvsignore
new file mode 100644
index 00000000000..7f2443f2f31
--- /dev/null
+++ b/llvm/test/Transforms/LoopStrengthReduce/.cvsignore
@@ -0,0 +1,3 @@
+Output
+*.log
+*.sum
diff --git a/llvm/test/Transforms/LoopStrengthReduce/2005-08-15-AddRecIV.ll b/llvm/test/Transforms/LoopStrengthReduce/2005-08-15-AddRecIV.ll
new file mode 100644
index 00000000000..b2104051c9d
--- /dev/null
+++ b/llvm/test/Transforms/LoopStrengthReduce/2005-08-15-AddRecIV.ll
@@ -0,0 +1,77 @@
+; RUN: llvm-upgrade < %s | llvm-as | opt -loop-reduce -disable-output
+
+void %try_swap() {
+entry:
+	br bool false, label %cond_continue.0.i, label %cond_false.0.i
+
+cond_false.0.i:		; preds = %entry
+	ret void
+
+cond_continue.0.i:		; preds = %entry
+	br bool false, label %cond_continue.1.i, label %cond_false.1.i
+
+cond_false.1.i:		; preds = %cond_continue.0.i
+	ret void
+
+cond_continue.1.i:		; preds = %cond_continue.0.i
+	br bool false, label %endif.3.i, label %else.0.i
+
+endif.3.i:		; preds = %cond_continue.1.i
+	br bool false, label %my_irand.exit82, label %endif.0.i62
+
+else.0.i:		; preds = %cond_continue.1.i
+	ret void
+
+endif.0.i62:		; preds = %endif.3.i
+	ret void
+
+my_irand.exit82:		; preds = %endif.3.i
+	br bool false, label %else.2, label %then.4
+
+then.4:		; preds = %my_irand.exit82
+	ret void
+
+else.2:		; preds = %my_irand.exit82
+	br bool false, label %find_affected_nets.exit, label %loopentry.1.i107.outer.preheader
+
+loopentry.1.i107.outer.preheader:		; preds = %else.2
+	ret void
+
+find_affected_nets.exit:		; preds = %else.2
+	br bool false, label %save_region_occ.exit, label %loopentry.1
+
+save_region_occ.exit:		; preds = %find_affected_nets.exit
+	br bool false, label %no_exit.1.preheader, label %loopexit.1
+
+loopentry.1:		; preds = %find_affected_nets.exit
+	ret void
+
+no_exit.1.preheader:		; preds = %save_region_occ.exit
+	ret void
+
+loopexit.1:		; preds = %save_region_occ.exit
+	br bool false, label %then.10, label %loopentry.3
+
+then.10:		; preds = %loopexit.1
+	ret void
+
+loopentry.3:		; preds = %endif.16, %loopexit.1
+	%indvar342 = phi uint [ %indvar.next343, %endif.16 ], [ 0, %loopexit.1 ]		; <uint> [#uses=2]
+	br bool false, label %loopexit.3, label %endif.16
+
+endif.16:		; preds = %loopentry.3
+	%indvar.next343 = add uint %indvar342, 1		; <uint> [#uses=1]
+	br label %loopentry.3
+
+loopexit.3:		; preds = %loopentry.3
+	br label %loopentry.4
+
+loopentry.4:		; preds = %loopentry.4, %loopexit.3
+	%indvar340 = phi uint [ 0, %loopexit.3 ], [ %indvar.next341, %loopentry.4 ]		; <uint> [#uses=2]
+	%tmp. = add uint %indvar340, %indvar342		; <uint> [#uses=1]
+	%tmp.526 = load int** null		; <int*> [#uses=1]
+	%tmp.528 = getelementptr int* %tmp.526, uint %tmp.		; <int*> [#uses=1]
+	store int 0, int* %tmp.528
+	%indvar.next341 = add uint %indvar340, 1		; <uint> [#uses=1]
+	br label %loopentry.4
+}
diff --git a/llvm/test/Transforms/LoopStrengthReduce/2005-08-17-OutOfLoopVariant.ll b/llvm/test/Transforms/LoopStrengthReduce/2005-08-17-OutOfLoopVariant.ll
new file mode 100644
index 00000000000..5724bad72c0
--- /dev/null
+++ b/llvm/test/Transforms/LoopStrengthReduce/2005-08-17-OutOfLoopVariant.ll
@@ -0,0 +1,18 @@
+; RUN: llvm-upgrade < %s | llvm-as | opt -loop-reduce -disable-output
+
+int %image_to_texture(uint %indvar454) {
+loopentry.1.outer:
+	%j.2.1.ph = cast uint %indvar454 to int		; <int> [#uses=1]
+	br label %loopentry.1
+
+loopentry.1:		; preds = %label.5, %loopentry.1.outer
+	%i.3 = phi int [ 0, %loopentry.1.outer ], [ %i.3.be, %loopentry.1 ]
+	%tmp.390 = load int* null		; <int> [#uses=1]
+	%tmp.392 = mul int %tmp.390, %j.2.1.ph		; <int> [#uses=1]
+	%tmp.394 = add int %tmp.392, %i.3		; <int> [#uses=1]
+	%i.3.be = add int %i.3, 1		; <int> [#uses=1]
+	br bool false, label %loopentry.1, label %label.6
+
+label.6:		; preds = %no_exit.1
+	ret int %tmp.394
+}
diff --git a/llvm/test/Transforms/LoopStrengthReduce/2005-09-12-UsesOutOutsideOfLoop.ll b/llvm/test/Transforms/LoopStrengthReduce/2005-09-12-UsesOutOutsideOfLoop.ll
new file mode 100644
index 00000000000..81d3c25128d
--- /dev/null
+++ b/llvm/test/Transforms/LoopStrengthReduce/2005-09-12-UsesOutOutsideOfLoop.ll
@@ -0,0 +1,43 @@
+; RUN: llvm-upgrade < %s | llvm-as | opt -loop-reduce -disable-output
+
+void %main() {
+entry:
+	br label %loopentry.0
+
+loopentry.0:		; preds = %then.5, %entry
+	%arg_index.1.ph = phi int [ 1, %entry ], [ %arg_index.1.ph.be, %then.5 ]		; <int> [#uses=1]
+	br bool false, label %no_exit.0, label %loopexit.0
+
+no_exit.0:		; preds = %loopentry.0
+	%arg_index.1.1 = add int 0, %arg_index.1.ph		; <int> [#uses=2]
+	br bool false, label %then.i55, label %endif.i61
+
+then.i55:		; preds = %no_exit.0
+	br bool false, label %then.4, label %else.1
+
+endif.i61:		; preds = %no_exit.0
+	ret void
+
+then.4:		; preds = %then.i55
+	%tmp.19993 = add int %arg_index.1.1, 2		; <int> [#uses=0]
+	ret void
+
+else.1:		; preds = %then.i55
+	br bool false, label %then.i86, label %loopexit.i97
+
+then.i86:		; preds = %else.1
+	ret void
+
+loopexit.i97:		; preds = %else.1
+	br bool false, label %then.5, label %else.2
+
+then.5:		; preds = %loopexit.i97
+	%arg_index.1.ph.be = add int %arg_index.1.1, 2		; <int> [#uses=1]
+	br label %loopentry.0
+
+else.2:		; preds = %loopexit.i97
+	ret void
+
+loopexit.0:		; preds = %loopentry.0
+	ret void
+}
diff --git a/llvm/test/Transforms/LoopStrengthReduce/dg.exp b/llvm/test/Transforms/LoopStrengthReduce/dg.exp
new file mode 100644
index 00000000000..142de8a6c8f
--- /dev/null
+++ b/llvm/test/Transforms/LoopStrengthReduce/dg.exp
@@ -0,0 +1,3 @@
+load_lib llvm-dg.exp
+
+llvm-runtest [lsort [glob -nocomplain $srcdir/$subdir/*.{ll,llx,c,cpp,tr}]] $objdir $srcdir $subdir $target_triplet $llvmgcc $llvmgxx $prcontext $llvmgcc_version
diff --git a/llvm/test/Transforms/LoopStrengthReduce/different-type-ivs.ll b/llvm/test/Transforms/LoopStrengthReduce/different-type-ivs.ll
new file mode 100644
index 00000000000..1383fd692f0
--- /dev/null
+++ b/llvm/test/Transforms/LoopStrengthReduce/different-type-ivs.ll
@@ -0,0 +1,26 @@
+; RUN: llvm-upgrade < %s | llvm-as | opt -loop-reduce -disable-output
+; Test to make sure that loop-reduce never crashes on IV's 
+; with different types but identical strides.
+
+void %foo() {
+entry:
+	br label %no_exit
+
+no_exit:		; preds = %no_exit, %entry
+	%indvar = phi uint [ 0, %entry ], [ %indvar.next, %no_exit ]		; <uint> [#uses=3]
+	%indvar = cast uint %indvar to short		; <short> [#uses=1]
+	%X.0.0 = mul short %indvar, 1234		; <short> [#uses=1]
+	%tmp. = mul uint %indvar, 1234		; <uint> [#uses=1]
+	%tmp.5 = cast short %X.0.0 to int		; <int> [#uses=1]
+	%tmp.3 = call int (...)* %bar( int %tmp.5, uint %tmp. )		; <int> [#uses=0]
+	%tmp.0 = call bool %pred( )		; <int> [#uses=1]
+	%indvar.next = add uint %indvar, 1		; <uint> [#uses=1]
+	br bool %tmp.0, label %return, label %no_exit
+
+return:
+	ret void
+}
+
+declare bool %pred()
+
+declare int %bar(...)
diff --git a/llvm/test/Transforms/LoopStrengthReduce/dont-hoist-simple-loop-constants.ll b/llvm/test/Transforms/LoopStrengthReduce/dont-hoist-simple-loop-constants.ll
new file mode 100644
index 00000000000..b8f318b307f
--- /dev/null
+++ b/llvm/test/Transforms/LoopStrengthReduce/dont-hoist-simple-loop-constants.ll
@@ -0,0 +1,24 @@
+; RUN: llvm-upgrade < %s | llvm-as | opt -loop-reduce | llvm-dis | not grep 'cast uint 1 to uint'
+; The setlt wants to use a value that is incremented one more than the dominant
+; IV.  Don't insert the 1 outside the loop, preventing folding it into the add.
+
+implementation   ; Functions:
+
+void %test([700 x int]* %nbeaux_.0__558, int* %i_.16574) {
+then.0:
+        br label %no_exit.2
+
+no_exit.2:              ; preds = %no_exit.2, %then.0
+        %indvar630 = phi uint [ 0, %then.0 ], [ %indvar.next631, %no_exit.2 ]           ; <uint> [#uses=3]
+        %indvar630 = cast uint %indvar630 to int                ; <int> [#uses=1]
+        %tmp.38 = getelementptr [700 x int]* %nbeaux_.0__558, int 0, uint %indvar630            ; <int*> [#uses=1]
+        store int 0, int* %tmp.38
+        %inc.2 = add int %indvar630, 2          ; <int> [#uses=2]
+        %tmp.34 = setlt int %inc.2, 701         ; <bool> [#uses=1]
+        %indvar.next631 = add uint %indvar630, 1                ; <uint> [#uses=1]
+        br bool %tmp.34, label %no_exit.2, label %loopexit.2.loopexit
+
+loopexit.2.loopexit:            ; preds = %no_exit.2
+        store int %inc.2, int* %i_.16574
+        ret void
+}
diff --git a/llvm/test/Transforms/LoopStrengthReduce/dont_insert_redundant_ops.ll b/llvm/test/Transforms/LoopStrengthReduce/dont_insert_redundant_ops.ll
new file mode 100644
index 00000000000..aecade80d79
--- /dev/null
+++ b/llvm/test/Transforms/LoopStrengthReduce/dont_insert_redundant_ops.ll
@@ -0,0 +1,40 @@
+; Check that this test makes INDVAR and related stuff dead.
+; RUN: llvm-upgrade < %s | llvm-as | opt -loop-reduce | llvm-dis | grep phi | wc -l | grep 2
+
+declare bool %pred()
+
+void %test1({ int, int }* %P) {
+	br label %Loop
+Loop:
+	%INDVAR = phi int [0, %0], [%INDVAR2, %Loop]
+
+	%gep1 = getelementptr { int, int}* %P, int %INDVAR, uint 0
+	store int 0, int* %gep1
+
+	%gep2 = getelementptr { int, int}* %P, int %INDVAR, uint 1
+	store int 0, int* %gep2
+
+	%INDVAR2 = add int %INDVAR, 1
+	%cond = call bool %pred()
+	br bool %cond, label %Loop, label %Out
+Out:
+	ret void
+}
+
+void %test2([2 x int]* %P) {
+	br label %Loop
+Loop:
+	%INDVAR = phi int [0, %0], [%INDVAR2, %Loop]
+
+	%gep1 = getelementptr [2 x int]* %P, int %INDVAR, uint 0
+	store int 0, int* %gep1
+
+	%gep2 = getelementptr [2 x int]* %P, int %INDVAR, uint 1
+	store int 0, int* %gep2
+
+	%INDVAR2 = add int %INDVAR, 1
+	%cond = call bool %pred()
+	br bool %cond, label %Loop, label %Out
+Out:
+	ret void
+}
diff --git a/llvm/test/Transforms/LoopStrengthReduce/dont_reduce_bytes.ll b/llvm/test/Transforms/LoopStrengthReduce/dont_reduce_bytes.ll
new file mode 100644
index 00000000000..2c679800a7a
--- /dev/null
+++ b/llvm/test/Transforms/LoopStrengthReduce/dont_reduce_bytes.ll
@@ -0,0 +1,21 @@
+; Don't reduce the byte access to P[i], at least not on targets that 
+; support an efficient 'mem[r1+r2]' addressing mode.
+
+; RUN: llvm-upgrade < %s | llvm-as | opt -loop-reduce -disable-output
+
+declare bool %pred(int)
+
+void %test(sbyte* %PTR) {
+	br label %Loop
+Loop:
+	%INDVAR = phi int [0, %0], [%INDVAR2, %Loop]
+
+	%STRRED = getelementptr sbyte* %PTR, int %INDVAR
+	store sbyte 0, sbyte* %STRRED
+
+	%INDVAR2 = add int %INDVAR, 1
+	%cond = call bool %pred(int %INDVAR2)  ;; cannot eliminate indvar
+	br bool %cond, label %Loop, label %Out
+Out:
+	ret void
+}
diff --git a/llvm/test/Transforms/LoopStrengthReduce/exit_compare_live_range.ll b/llvm/test/Transforms/LoopStrengthReduce/exit_compare_live_range.ll
new file mode 100644
index 00000000000..79beb0bff74
--- /dev/null
+++ b/llvm/test/Transforms/LoopStrengthReduce/exit_compare_live_range.ll
@@ -0,0 +1,21 @@
+; Make sure that the compare instruction occurs after the increment to avoid
+; having overlapping live ranges that result in copies.  We want the setcc 
+; instruction immediately before the conditional branch.
+;
+; RUN: llvm-upgrade < %s | llvm-as | opt -loop-reduce | llvm-dis | \
+; RUN:    %prcontext 'br i1' 1 | grep icmp
+
+void %foo(float* %D, uint %E) {
+entry:
+	br label %no_exit
+
+no_exit:
+	%indvar = phi uint [ 0, %entry ], [ %indvar.next, %no_exit ]
+	volatile store float 0.0, float* %D
+	%indvar.next = add uint %indvar, 1		; <uint> [#uses=2]
+	%exitcond = seteq uint %indvar.next, %E		; <bool> [#uses=1]
+	br bool %exitcond, label %loopexit, label %no_exit
+
+loopexit:
+	ret void
+}
diff --git a/llvm/test/Transforms/LoopStrengthReduce/invariant_value_first.ll b/llvm/test/Transforms/LoopStrengthReduce/invariant_value_first.ll
new file mode 100644
index 00000000000..5e05e755508
--- /dev/null
+++ b/llvm/test/Transforms/LoopStrengthReduce/invariant_value_first.ll
@@ -0,0 +1,21 @@
+; Check that the index of 'P[outer]' is pulled out of the loop.
+; RUN: llvm-upgrade < %s | llvm-as | opt -loop-reduce | llvm-dis | not grep 'getelementptr.*%outer.*%INDVAR'
+
+declare bool %pred()
+declare int %foo()
+
+void %test([10000 x int]* %P) {
+	%outer = call int %foo()
+	br label %Loop
+Loop:
+	%INDVAR = phi int [0, %0], [%INDVAR2, %Loop]
+
+	%STRRED = getelementptr [10000 x int]* %P, int %outer, int %INDVAR
+	store int 0, int* %STRRED
+
+	%INDVAR2 = add int %INDVAR, 1
+	%cond = call bool %pred()
+	br bool %cond, label %Loop, label %Out
+Out:
+	ret void
+}
diff --git a/llvm/test/Transforms/LoopStrengthReduce/invariant_value_first_arg.ll b/llvm/test/Transforms/LoopStrengthReduce/invariant_value_first_arg.ll
new file mode 100644
index 00000000000..0289badddc4
--- /dev/null
+++ b/llvm/test/Transforms/LoopStrengthReduce/invariant_value_first_arg.ll
@@ -0,0 +1,19 @@
+; Check that the index of 'P[outer]' is pulled out of the loop.
+; RUN: llvm-upgrade < %s | llvm-as | opt -loop-reduce | llvm-dis | not grep 'getelementptr.*%outer.*%INDVAR'
+
+declare bool %pred()
+
+void %test([10000 x int]* %P, int %outer) {
+	br label %Loop
+Loop:
+	%INDVAR = phi int [0, %0], [%INDVAR2, %Loop]
+
+	%STRRED = getelementptr [10000 x int]* %P, int %outer, int %INDVAR
+	store int 0, int* %STRRED
+
+	%INDVAR2 = add int %INDVAR, 1
+	%cond = call bool %pred()
+	br bool %cond, label %Loop, label %Out
+Out:
+	ret void
+}
diff --git a/llvm/test/Transforms/LoopStrengthReduce/nested-reduce.ll b/llvm/test/Transforms/LoopStrengthReduce/nested-reduce.ll
new file mode 100644
index 00000000000..1959832d51c
--- /dev/null
+++ b/llvm/test/Transforms/LoopStrengthReduce/nested-reduce.ll
@@ -0,0 +1,57 @@
+; RUN: llvm-upgrade < %s | llvm-as | opt -loop-reduce &&
+; RUN: llvm-upgrade < %s | llvm-as | opt -loop-reduce | llvm-dis | not grep mul
+
+; Make sure we don't get a multiply by 6 in this loop.
+
+int %foo(int %A, int %B, int %C, int %D) {
+entry:
+	%tmp.5 = setgt int %C, 0		; <bool> [#uses=1]
+	%tmp.25 = and int %A, 1		; <int> [#uses=1]
+	br label %loopentry.1
+
+loopentry.1:		; preds = %loopexit.1, %entry
+	%indvar20 = phi uint [ 0, %entry ], [ %indvar.next21, %loopexit.1 ]		; <uint> [#uses=2]
+	%k.1 = phi int [ 0, %entry ], [ %k.1.3, %loopexit.1 ]		; <int> [#uses=2]
+	br bool %tmp.5, label %no_exit.1.preheader, label %loopexit.1
+
+no_exit.1.preheader:		; preds = %loopentry.1
+	%i.0.0 = cast uint %indvar20 to int		; <int> [#uses=1]
+	%tmp.9 = mul int %i.0.0, 6		; <int> [#uses=1]
+	br label %no_exit.1.outer
+
+no_exit.1.outer:		; preds = %cond_true, %no_exit.1.preheader
+	%k.1.2.ph = phi int [ %k.1, %no_exit.1.preheader ], [ %k.09, %cond_true ]		; <int> [#uses=2]
+	%j.1.2.ph = phi int [ 0, %no_exit.1.preheader ], [ %inc.1, %cond_true ]		; <int> [#uses=1]
+	br label %no_exit.1
+
+no_exit.1:		; preds = %cond_continue, %no_exit.1.outer
+	%indvar.ui = phi uint [ 0, %no_exit.1.outer ], [ %indvar.next, %cond_continue ]		; <uint> [#uses=2]
+	%indvar = cast uint %indvar.ui to int		; <int> [#uses=1]
+	%j.1.2 = add int %indvar, %j.1.2.ph		; <int> [#uses=2]
+	%tmp.11 = add int %j.1.2, %tmp.9		; <int> [#uses=1]
+	%tmp.12 = cast int %tmp.11 to ubyte		; <ubyte> [#uses=1]
+	%tmp.13 = shl int %D, ubyte %tmp.12		; <int> [#uses=2]
+	%tmp.15 = seteq int %tmp.13, %B		; <bool> [#uses=1]
+	%inc.1 = add int %j.1.2, 1		; <int> [#uses=3]
+	br bool %tmp.15, label %cond_true, label %cond_continue
+
+cond_true:		; preds = %no_exit.1
+	%tmp.26 = and int %tmp.25, %tmp.13		; <int> [#uses=1]
+	%k.09 = add int %tmp.26, %k.1.2.ph		; <int> [#uses=2]
+	%tmp.517 = setlt int %inc.1, %C		; <bool> [#uses=1]
+	br bool %tmp.517, label %no_exit.1.outer, label %loopexit.1
+
+cond_continue:		; preds = %no_exit.1
+	%tmp.519 = setlt int %inc.1, %C		; <bool> [#uses=1]
+	%indvar.next = add uint %indvar.ui, 1		; <uint> [#uses=1]
+	br bool %tmp.519, label %no_exit.1, label %loopexit.1
+
+loopexit.1:		; preds = %cond_continue, %cond_true, %loopentry.1
+	%k.1.3 = phi int [ %k.1, %loopentry.1 ], [ %k.09, %cond_true ], [ %k.1.2.ph, %cond_continue ]		; <int> [#uses=2]
+	%indvar.next21 = add uint %indvar20, 1		; <uint> [#uses=2]
+	%exitcond = seteq uint %indvar.next21, 4		; <bool> [#uses=1]
+	br bool %exitcond, label %loopexit.0, label %loopentry.1
+
+loopexit.0:		; preds = %loopexit.1
+	ret int %k.1.3
+}
diff --git a/llvm/test/Transforms/LoopStrengthReduce/ops_after_indvar.ll b/llvm/test/Transforms/LoopStrengthReduce/ops_after_indvar.ll
new file mode 100644
index 00000000000..59da48b9e57
--- /dev/null
+++ b/llvm/test/Transforms/LoopStrengthReduce/ops_after_indvar.ll
@@ -0,0 +1,22 @@
+; Check that this test makes INDVAR and related stuff dead, because P[indvar]
+; gets reduced, making INDVAR dead.
+
+; RUN: llvm-upgrade < %s | llvm-as | opt -loop-reduce | llvm-dis | not grep INDVAR
+
+declare bool %pred()
+declare int %getidx()
+
+void %test([10000 x int]* %P) {
+	br label %Loop
+Loop:
+	%INDVAR = phi int [0, %0], [%INDVAR2, %Loop]
+	%idx = call int %getidx()
+	%STRRED = getelementptr [10000 x int]* %P, int %INDVAR, int %idx
+	store int 0, int* %STRRED
+
+	%INDVAR2 = add int %INDVAR, 1
+	%cond = call bool %pred()
+	br bool %cond, label %Loop, label %Out
+Out:
+	ret void
+}
diff --git a/llvm/test/Transforms/LoopStrengthReduce/phi_node_update_multiple_preds.ll b/llvm/test/Transforms/LoopStrengthReduce/phi_node_update_multiple_preds.ll
new file mode 100644
index 00000000000..cd0afe1936b
--- /dev/null
+++ b/llvm/test/Transforms/LoopStrengthReduce/phi_node_update_multiple_preds.ll
@@ -0,0 +1,29 @@
+; RUN: llvm-upgrade < %s | llvm-as | opt -loop-reduce -disable-output
+; LSR should not crash on this.
+
+fastcc void %loadloop() {
+entry:
+	switch sbyte 0, label %shortcirc_next [
+		 sbyte 32, label %loopexit.2
+		 sbyte 59, label %loopexit.2
+	]
+
+shortcirc_next:		; preds = %no_exit.2, %entry
+	%indvar37 = phi uint [ 0, %entry ], [ %indvar.next38, %no_exit.2 ]		; <uint> [#uses=3]
+	%wp.2.4 = getelementptr sbyte* null, uint %indvar37		; <sbyte*> [#uses=1]
+	br bool false, label %loopexit.2, label %no_exit.2
+
+no_exit.2:		; preds = %shortcirc_next
+	%wp.2.4.rec = cast uint %indvar37 to int		; <int> [#uses=1]
+	%inc.1.rec = add int %wp.2.4.rec, 1		; <int> [#uses=1]
+	%inc.1 = getelementptr sbyte* null, int %inc.1.rec		; <sbyte*> [#uses=2]
+	%indvar.next38 = add uint %indvar37, 1		; <uint> [#uses=1]
+	switch sbyte 0, label %shortcirc_next [
+		 sbyte 32, label %loopexit.2
+		 sbyte 59, label %loopexit.2
+	]
+
+loopexit.2:		; preds = %no_exit.2, %no_exit.2, %shortcirc_next, %entry, %entry
+	%wp.2.7 = phi sbyte* [ null, %entry ], [ null, %entry ], [ %wp.2.4, %shortcirc_next ], [ %inc.1, %no_exit.2 ], [ %inc.1, %no_exit.2 ]		; <sbyte*> [#uses=0]
+	ret void
+}
diff --git a/llvm/test/Transforms/LoopStrengthReduce/related_indvars.ll b/llvm/test/Transforms/LoopStrengthReduce/related_indvars.ll
new file mode 100644
index 00000000000..533279b9eb1
--- /dev/null
+++ b/llvm/test/Transforms/LoopStrengthReduce/related_indvars.ll
@@ -0,0 +1,28 @@
+; RUN: llvm-upgrade < %s | llvm-as | opt -loop-reduce | llvm-dis | grep phi | wc -l | grep 1
+
+; This should only result in one PHI node!
+
+; void foo(double *D, double *E, double F) {
+;   while (D != E)
+;     *D++ = F;
+; }
+
+void %foo(double* %D, double* %E, double %F) {
+entry:
+	%tmp.24 = seteq double* %D, %E		; <bool> [#uses=1]
+	br bool %tmp.24, label %return, label %no_exit
+
+no_exit:		; preds = %no_exit, %entry
+	%indvar = phi uint [ 0, %entry ], [ %indvar.next, %no_exit ]		; <uint> [#uses=3]
+	%D_addr.0.0.rec = cast uint %indvar to int		; <int> [#uses=1]
+	%D_addr.0.0 = getelementptr double* %D, int %D_addr.0.0.rec		; <double*> [#uses=1]
+	%inc.rec = add int %D_addr.0.0.rec, 1		; <int> [#uses=1]
+	%inc = getelementptr double* %D, int %inc.rec		; <double*> [#uses=1]
+	store double %F, double* %D_addr.0.0
+	%tmp.2 = seteq double* %inc, %E		; <bool> [#uses=1]
+	%indvar.next = add uint %indvar, 1		; <uint> [#uses=1]
+	br bool %tmp.2, label %return, label %no_exit
+
+return:		; preds = %no_exit, %entry
+	ret void
+}
diff --git a/llvm/test/Transforms/LoopStrengthReduce/remove_indvar.ll b/llvm/test/Transforms/LoopStrengthReduce/remove_indvar.ll
new file mode 100644
index 00000000000..517180b7f02
--- /dev/null
+++ b/llvm/test/Transforms/LoopStrengthReduce/remove_indvar.ll
@@ -0,0 +1,19 @@
+; Check that this test makes INDVAR and related stuff dead.
+; RUN: llvm-upgrade < %s | llvm-as | opt -loop-reduce | llvm-dis | not grep INDVAR
+
+declare bool %pred()
+
+void %test(int* %P) {
+	br label %Loop
+Loop:
+	%INDVAR = phi int [0, %0], [%INDVAR2, %Loop]
+
+	%STRRED = getelementptr int* %P, int %INDVAR
+	store int 0, int* %STRRED
+
+	%INDVAR2 = add int %INDVAR, 1
+	%cond = call bool %pred()
+	br bool %cond, label %Loop, label %Out
+Out:
+	ret void
+}
diff --git a/llvm/test/Transforms/LoopStrengthReduce/share_code_in_preheader.ll b/llvm/test/Transforms/LoopStrengthReduce/share_code_in_preheader.ll
new file mode 100644
index 00000000000..d8316a52bcc
--- /dev/null
+++ b/llvm/test/Transforms/LoopStrengthReduce/share_code_in_preheader.ll
@@ -0,0 +1,28 @@
+; RUN: llvm-upgrade < %s | llvm-as | opt -loop-reduce | llvm-dis | grep mul | wc -l | grep 1
+; LSR should not make two copies of the Q*L expression in the preheader!
+
+sbyte %test(sbyte* %A, sbyte* %B, int %L, int %Q, int %N.s) {
+entry:
+	%tmp.6 = mul int %Q, %L		; <int> [#uses=1]
+	%N = cast int %N.s to uint		; <uint> [#uses=1]
+	br label %no_exit
+
+no_exit:		; preds = %no_exit, %no_exit.preheader
+	%indvar.ui = phi uint [ 0, %entry], [ %indvar.next, %no_exit ]		; <uint> [#uses=2]
+	%Sum.0.0 = phi sbyte [ 0, %entry], [ %tmp.21, %no_exit ]		; <sbyte> [#uses=1]
+	%indvar = cast uint %indvar.ui to int		; <int> [#uses=1]
+	%N_addr.0.0 = sub int %N.s, %indvar		; <int> [#uses=1]
+	%tmp.8 = add int %N_addr.0.0, %tmp.6		; <int> [#uses=2]
+	%tmp.9 = getelementptr sbyte* %A, int %tmp.8		; <sbyte*> [#uses=1]
+	%tmp.10 = load sbyte* %tmp.9		; <sbyte> [#uses=1]
+	%tmp.17 = getelementptr sbyte* %B, int %tmp.8		; <sbyte*> [#uses=1]
+	%tmp.18 = load sbyte* %tmp.17		; <sbyte> [#uses=1]
+	%tmp.19 = sub sbyte %tmp.10, %tmp.18		; <sbyte> [#uses=1]
+	%tmp.21 = add sbyte %tmp.19, %Sum.0.0		; <sbyte> [#uses=2]
+	%indvar.next = add uint %indvar.ui, 1		; <uint> [#uses=2]
+	%exitcond = seteq uint %indvar.next, %N		; <bool> [#uses=1]
+	br bool %exitcond, label %loopexit, label %no_exit
+
+loopexit:
+	ret sbyte %tmp.21
+}
diff --git a/llvm/test/Transforms/LoopStrengthReduce/share_ivs.ll b/llvm/test/Transforms/LoopStrengthReduce/share_ivs.ll
new file mode 100644
index 00000000000..76bfe1d529c
--- /dev/null
+++ b/llvm/test/Transforms/LoopStrengthReduce/share_ivs.ll
@@ -0,0 +1,24 @@
+; RUN: llvm-upgrade < %s | llvm-as | opt -loop-reduce | llvm-dis | grep phi | wc -l | grep 1
+
+; This testcase should have ONE stride 18 indvar, the other use should have a
+; loop invariant value (B) added to it inside of the loop, instead of having
+; a whole indvar based on B for it.
+
+declare bool %cond(uint)
+
+void %test(uint %B) {
+	br label %Loop
+Loop:
+	%IV = phi uint [0, %0], [%IVn, %Loop]
+
+	%C = mul uint %IV, 18
+	%D = mul uint %IV, 18
+	%E = add uint %D, %B
+
+	%cnd = call bool %cond(uint %E)
+	call bool %cond(uint %C)
+	%IVn = add uint %IV, 1
+	br bool %cnd, label %Loop, label %Out
+Out:
+	ret void
+}
diff --git a/llvm/test/Transforms/LoopStrengthReduce/use_postinc_value_outside_loop.ll b/llvm/test/Transforms/LoopStrengthReduce/use_postinc_value_outside_loop.ll
new file mode 100644
index 00000000000..028400c47f0
--- /dev/null
+++ b/llvm/test/Transforms/LoopStrengthReduce/use_postinc_value_outside_loop.ll
@@ -0,0 +1,28 @@
+; RUN: llvm-upgrade < %s | llvm-as | opt -loop-reduce | llvm-dis | grep 'add i32 %iv.*inc, 1'
+;
+; Make sure that the use of the IV outside of the loop (the store) uses the 
+; post incremented value of the IV, not the preincremented value.  This 
+; prevents the loop from having to keep the post and pre-incremented value
+; around for the duration of the loop, adding a copy and an extra register
+; to the loop.
+
+declare bool %pred(int %X)
+
+void %test([700 x int]* %nbeaux_.0__558, int* %i_.16574) {
+then.0:
+        br label %no_exit.2
+
+no_exit.2:              ; preds = %no_exit.2, %then.0
+        %indvar630.ui = phi uint [ 0, %then.0 ], [ %indvar.next631, %no_exit.2 ]           ; <uint> [#uses=3]
+        %indvar630 = cast uint %indvar630.ui to int                ; <int> [#uses=1]
+        %tmp.38 = getelementptr [700 x int]* %nbeaux_.0__558, int 0, uint %indvar630.ui            ; <int*> [#uses=1]
+        store int 0, int* %tmp.38
+        %inc.2 = add int %indvar630, 2          ; <int> [#uses=2]
+        %tmp.34 = call bool %pred(int %indvar630)
+        %indvar.next631 = add uint %indvar630.ui, 1                ; <uint> [#uses=1]
+        br bool %tmp.34, label %no_exit.2, label %loopexit.2.loopexit
+
+loopexit.2.loopexit:            ; preds = %no_exit.2
+        store int %inc.2, int* %i_.16574
+        ret void
+}
diff --git a/llvm/test/Transforms/LoopStrengthReduce/var_stride_used_by_compare.ll b/llvm/test/Transforms/LoopStrengthReduce/var_stride_used_by_compare.ll
new file mode 100644
index 00000000000..3e8f63abe3b
--- /dev/null
+++ b/llvm/test/Transforms/LoopStrengthReduce/var_stride_used_by_compare.ll
@@ -0,0 +1,48 @@
+; RUN: llvm-upgrade < %s | llvm-as | opt -loop-reduce | llvm-dis &&
+
+; Base should not be i*3, it should be i*2.
+; RUN: llvm-upgrade < %s | llvm-as | opt -loop-reduce | llvm-dis | not grep 'mul.*%i, 3' &&
+
+; Indvar should not start at zero:
+; RUN: llvm-upgrade < %s | llvm-as | opt -loop-reduce | llvm-dis | not grep 'phi uint .* 0'
+
+; mul uint %i, 3
+
+; ModuleID = 't.bc'
+target datalayout = "e-p:32:32"
+target endian = little
+target pointersize = 32
+target triple = "i686-apple-darwin8"
+%flags2 = external global [8193 x sbyte], align 32		; <[8193 x sbyte]*> [#uses=1]
+
+implementation   ; Functions:
+
+void %foo(int %k, int %i.s) {
+entry:
+	%i = cast int %i.s to uint		; <uint> [#uses=2]
+	%k_addr.012 = shl int %i.s, ubyte 1		; <int> [#uses=1]
+	%tmp14 = setgt int %k_addr.012, 8192		; <bool> [#uses=1]
+	br bool %tmp14, label %return, label %bb.preheader
+
+bb.preheader:		; preds = %entry
+	%tmp. = shl uint %i, ubyte 1		; <uint> [#uses=1]
+	br label %bb
+
+bb:		; preds = %bb, %bb.preheader
+	%indvar = phi uint [ %indvar.next, %bb ], [ 0, %bb.preheader ]		; <uint> [#uses=2]
+	%tmp.15 = mul uint %indvar, %i		; <uint> [#uses=1]
+	%tmp.16 = add uint %tmp.15, %tmp.		; <uint> [#uses=2]
+	%k_addr.0.0 = cast uint %tmp.16 to int		; <int> [#uses=1]
+	%tmp = getelementptr [8193 x sbyte]* %flags2, int 0, uint %tmp.16		; <sbyte*> [#uses=1]
+	store sbyte 0, sbyte* %tmp
+	%k_addr.0 = add int %k_addr.0.0, %i.s		; <int> [#uses=1]
+	%tmp = setgt int %k_addr.0, 8192		; <bool> [#uses=1]
+	%indvar.next = add uint %indvar, 1		; <uint> [#uses=1]
+	br bool %tmp, label %return.loopexit, label %bb
+
+return.loopexit:		; preds = %bb
+	br label %return
+
+return:		; preds = %return.loopexit, %entry
+	ret void
+}
diff --git a/llvm/test/Transforms/LoopStrengthReduce/variable_stride.ll b/llvm/test/Transforms/LoopStrengthReduce/variable_stride.ll
new file mode 100644
index 00000000000..83aeaa6a9c6
--- /dev/null
+++ b/llvm/test/Transforms/LoopStrengthReduce/variable_stride.ll
@@ -0,0 +1,17 @@
+; Check that variable strides are reduced to adds instead of multiplies.
+; RUN: llvm-upgrade < %s | llvm-as | opt -loop-reduce | llvm-dis | not grep 'mul'
+
+declare bool %pred(int)
+
+void %test([10000 x int]* %P, int %STRIDE) {
+	br label %Loop
+Loop:
+	%INDVAR = phi int [0, %0], [%INDVAR2, %Loop]
+	%Idx = mul int %INDVAR, %STRIDE
+
+	%cond = call bool %pred(int %Idx)
+	%INDVAR2 = add int %INDVAR, 1
+	br bool %cond, label %Loop, label %Out
+Out:
+	ret void
+}