14 files changed, 699 insertions, 39 deletions

diff --git a/test/Transforms/Reassociate/2005-08-24-Crash.ll b/test/Transforms/Reassociate/2005-08-24-Crash.ll
deleted file mode 100644
index 9864de4..0000000
--- a/test/Transforms/Reassociate/2005-08-24-Crash.ll
+++ /dev/null
@@ -1,13 +0,0 @@
-; RUN: opt < %s -reassociate -disable-output
-
-define void @test(i32 %a, i32 %b, i32 %c, i32 %d) {
-	%tmp.2 = xor i32 %a, %b		; <i32> [#uses=1]
-	%tmp.5 = xor i32 %c, %d		; <i32> [#uses=1]
-	%tmp.6 = xor i32 %tmp.2, %tmp.5		; <i32> [#uses=1]
-	%tmp.9 = xor i32 %c, %a		; <i32> [#uses=1]
-	%tmp.12 = xor i32 %b, %d		; <i32> [#uses=1]
-	%tmp.13 = xor i32 %tmp.9, %tmp.12		; <i32> [#uses=1]
-	%tmp.16 = xor i32 %tmp.6, %tmp.13		; <i32> [#uses=0]
-	ret void
-}
-
diff --git a/test/Transforms/Reassociate/2005-09-01-ArrayOutOfBounds.ll b/test/Transforms/Reassociate/2005-09-01-ArrayOutOfBounds.ll
index 33e44d4..f66148b 100644
--- a/test/Transforms/Reassociate/2005-09-01-ArrayOutOfBounds.ll
+++ b/test/Transforms/Reassociate/2005-09-01-ArrayOutOfBounds.ll
@@ -1,5 +1,5 @@
 ; RUN: opt < %s -reassociate -instcombine -S |\
-; RUN:   grep {ret i32 0}
+; RUN:   grep "ret i32 0"
 
 define i32 @f(i32 %a0, i32 %a1, i32 %a2, i32 %a3, i32 %a4) {
 	%tmp.2 = add i32 %a4, %a3		; <i32> [#uses=1]
diff --git a/test/Transforms/Reassociate/2012-05-08-UndefLeak.ll b/test/Transforms/Reassociate/2012-05-08-UndefLeak.ll
new file mode 100644
index 0000000..2f5a53e
--- /dev/null
+++ b/test/Transforms/Reassociate/2012-05-08-UndefLeak.ll
@@ -0,0 +1,85 @@
+; RUN: opt < %s -reassociate -S | FileCheck %s
+; PR12169
+; PR12764
+; XFAIL: *
+; Transform disabled until PR13021 is fixed.
+
+define i64 @f(i64 %x0) {
+; CHECK: @f
+; CHECK-NEXT: mul i64 %x0, 208
+; CHECK-NEXT: add i64 %{{.*}}, 1617
+; CHECK-NEXT: ret i64
+  %t0 = add i64 %x0, 1
+  %t1 = add i64 %x0, 2
+  %t2 = add i64 %x0, 3
+  %t3 = add i64 %x0, 4
+  %t4 = add i64 %x0, 5
+  %t5 = add i64 %x0, 6
+  %t6 = add i64 %x0, 7
+  %t7 = add i64 %x0, 8
+  %t8 = add i64 %x0, 9
+  %t9 = add i64 %x0, 10
+  %t10 = add i64 %x0, 11
+  %t11 = add i64 %x0, 12
+  %t12 = add i64 %x0, 13
+  %t13 = add i64 %x0, 14
+  %t14 = add i64 %x0, 15
+  %t15 = add i64 %x0, 16
+  %t16 = add i64 %x0, 17
+  %t17 = add i64 %x0, 18
+  %t18 = add i64 %t17, %t0
+  %t19 = add i64 %t18, %t1
+  %t20 = add i64 %t19, %t2
+  %t21 = add i64 %t20, %t3
+  %t22 = add i64 %t21, %t4
+  %t23 = add i64 %t22, %t5
+  %t24 = add i64 %t23, %t6
+  %t25 = add i64 %t24, %t7
+  %t26 = add i64 %t25, %t8
+  %t27 = add i64 %t26, %t9
+  %t28 = add i64 %t27, %t10
+  %t29 = add i64 %t28, %t11
+  %t30 = add i64 %t29, %t12
+  %t31 = add i64 %t30, %t13
+  %t32 = add i64 %t31, %t14
+  %t33 = add i64 %t32, %t15
+  %t34 = add i64 %t33, %t16
+  %t35 = add i64 %t34, %x0
+  %t36 = add i64 %t0, %t1
+  %t37 = add i64 %t36, %t2
+  %t38 = add i64 %t37, %t3
+  %t39 = add i64 %t38, %t4
+  %t40 = add i64 %t39, %t5
+  %t41 = add i64 %t40, %t6
+  %t42 = add i64 %t41, %t7
+  %t43 = add i64 %t42, %t8
+  %t44 = add i64 %t43, %t9
+  %t45 = add i64 %t44, %t10
+  %t46 = add i64 %t45, %t11
+  %t47 = add i64 %t46, %t12
+  %t48 = add i64 %t47, %t13
+  %t49 = add i64 %t48, %t14
+  %t50 = add i64 %t49, %t15
+  %t51 = add i64 %t50, %t16
+  %t52 = add i64 %t51, %t17
+  %t53 = add i64 %t52, %t18
+  %t54 = add i64 %t53, %t19
+  %t55 = add i64 %t54, %t20
+  %t56 = add i64 %t55, %t21
+  %t57 = add i64 %t56, %t22
+  %t58 = add i64 %t57, %t23
+  %t59 = add i64 %t58, %t24
+  %t60 = add i64 %t59, %t25
+  %t61 = add i64 %t60, %t26
+  %t62 = add i64 %t61, %t27
+  %t63 = add i64 %t62, %t28
+  %t64 = add i64 %t63, %t29
+  %t65 = add i64 %t64, %t30
+  %t66 = add i64 %t65, %t31
+  %t67 = add i64 %t66, %t32
+  %t68 = add i64 %t67, %t33
+  %t69 = add i64 %t68, %t34
+  %t70 = add i64 %t69, %t35
+  %t71 = add i64 %t70, %x0
+  ret i64 %t71
+}
diff --git a/test/Transforms/Reassociate/2012-06-08-InfiniteLoop.ll b/test/Transforms/Reassociate/2012-06-08-InfiniteLoop.ll
new file mode 100644
index 0000000..6e62a28
--- /dev/null
+++ b/test/Transforms/Reassociate/2012-06-08-InfiniteLoop.ll
@@ -0,0 +1,21 @@
+; RUN: opt < %s -reassociate -disable-output
+; PR13041
+
+define void @foo() {
+entry:
+  br label %while.cond
+
+while.cond:                                       ; preds = %while.body, %entry
+  %b.0 = phi i32 [ undef, %entry ], [ %sub2, %while.body ]
+  %c.0 = phi i32 [ undef, %entry ], [ %sub3, %while.body ]
+  br i1 undef, label %while.end, label %while.body
+
+while.body:                                       ; preds = %while.cond
+  %sub = sub nsw i32 0, %b.0
+  %sub2 = sub nsw i32 %sub, %c.0
+  %sub3 = sub nsw i32 0, %c.0
+  br label %while.cond
+
+while.end:                                        ; preds = %while.cond
+  ret void
+}
diff --git a/test/Transforms/Reassociate/absorption.ll b/test/Transforms/Reassociate/absorption.ll
new file mode 100644
index 0000000..2ccc2b5
--- /dev/null
+++ b/test/Transforms/Reassociate/absorption.ll
@@ -0,0 +1,11 @@
+; RUN: opt -S -reassociate < %s | FileCheck %s
+
+; Check that if constants combine to an absorbing value then the expression is
+; evaluated as the absorbing value.
+define i8 @foo(i8 %x) {
+  %tmp1 = or i8 %x, 127
+  %tmp2 = or i8 %tmp1, 128
+  ret i8 %tmp2
+; CHECK: @foo
+; CHECK: ret i8 -1
+}
diff --git a/test/Transforms/Reassociate/crash.ll b/test/Transforms/Reassociate/crash.ll
index 7a81942..ce586e1 100644
--- a/test/Transforms/Reassociate/crash.ll
+++ b/test/Transforms/Reassociate/crash.ll
@@ -67,3 +67,80 @@ _33:                                              ; preds = %_33, %_
   %tmp367 = add i32 %tmp365, %tmp366
   br label %_33
 }
+
+define void @test(i32 %a, i32 %b, i32 %c, i32 %d) {
+  %tmp.2 = xor i32 %a, %b		; <i32> [#uses=1]
+  %tmp.5 = xor i32 %c, %d		; <i32> [#uses=1]
+  %tmp.6 = xor i32 %tmp.2, %tmp.5		; <i32> [#uses=1]
+  %tmp.9 = xor i32 %c, %a		; <i32> [#uses=1]
+  %tmp.12 = xor i32 %b, %d		; <i32> [#uses=1]
+  %tmp.13 = xor i32 %tmp.9, %tmp.12		; <i32> [#uses=1]
+  %tmp.16 = xor i32 %tmp.6, %tmp.13		; <i32> [#uses=0]
+  ret void
+}
+
+define i128 @foo() {
+  %mul = mul i128 0, 0
+  ret i128 %mul
+}
+
+define void @infinite_loop() {
+entry:
+  br label %loop
+loop:
+  %x = phi i32 [undef, %entry], [%x, %loop]
+  %dead = add i32 %x, 0
+  br label %loop
+unreachable1:
+  %y1 = add i32 %y1, 0
+  %z1 = add i32 %y1, 0
+  ret void
+unreachable2:
+  %y2 = add i32 %y2, 0
+  %z2 = add i32 %y2, %y2
+  ret void
+unreachable3:
+  %y3 = add i32 %y3, %y3
+  %z3 = add i32 %y3, 0
+  ret void
+unreachable4:
+  %y4 = add i32 %y4, %y4
+  %z4 = add i32 %y4, %y4
+  ret void
+}
+
+; PR13185
+define void @pr13185(i16 %p) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.cond, %entry
+  %x.0 = phi i32 [ undef, %entry ], [ %conv, %for.cond ]
+  %conv = zext i16 %p to i32
+  br label %for.cond
+}
+
+; PR12963
+@a = external global i8
+define i8 @f0(i8 %x) {
+  %t0 = load i8* @a
+  %t1 = mul i8 %x, %x
+  %t2 = mul i8 %t1, %t1
+  %t3 = mul i8 %t2, %t2
+  %t4 = mul i8 %t3, %x
+  %t5 = mul i8 %t4, %t4
+  %t6 = mul i8 %t5, %x
+  %t7 = mul i8 %t6, %t0
+  ret i8 %t7
+}
+
+define i32 @sozefx_(i32 %x, i32 %y) {
+  %t0 = sub i32 %x, %x
+  %t1 = mul i32 %t0, %t0
+  %t2 = mul i32 %x, %t0
+  %t3 = mul i32 %t1, %t1
+  %t4 = add i32 %t2, %t3
+  %t5 = mul i32 %x, %y
+  %t6 = add i32 %t4, %t5
+  ret i32 %t6
+}
diff --git a/test/Transforms/Reassociate/fp-commute.ll b/test/Transforms/Reassociate/fp-commute.ll
new file mode 100644
index 0000000..025689b
--- /dev/null
+++ b/test/Transforms/Reassociate/fp-commute.ll
@@ -0,0 +1,18 @@
+; RUN: opt -reassociate -S < %s | FileCheck %s
+
+target triple = "armv7-apple-ios"
+
+declare void @use(float)
+
+; CHECK: test
+define void @test(float %x, float %y) {
+entry:
+; CHECK: fmul float %x, %y
+; CHECK: fmul float %x, %y
+  %0 = fmul float %x, %y
+  %1 = fmul float %y, %x
+  %2 = fsub float %0, %1
+  call void @use(float %0)
+  call void @use(float %2)
+  ret void
+}
diff --git a/test/Transforms/Reassociate/mightymul.ll b/test/Transforms/Reassociate/mightymul.ll
new file mode 100644
index 0000000..cfbc485
--- /dev/null
+++ b/test/Transforms/Reassociate/mightymul.ll
@@ -0,0 +1,35 @@
+; RUN: opt < %s -reassociate
+; PR13021
+
+define i32 @foo(i32 %x) {
+  %t0 = mul i32 %x, %x
+  %t1 = mul i32 %t0, %t0
+  %t2 = mul i32 %t1, %t1
+  %t3 = mul i32 %t2, %t2
+  %t4 = mul i32 %t3, %t3
+  %t5 = mul i32 %t4, %t4
+  %t6 = mul i32 %t5, %t5
+  %t7 = mul i32 %t6, %t6
+  %t8 = mul i32 %t7, %t7
+  %t9 = mul i32 %t8, %t8
+  %t10 = mul i32 %t9, %t9
+  %t11 = mul i32 %t10, %t10
+  %t12 = mul i32 %t11, %t11
+  %t13 = mul i32 %t12, %t12
+  %t14 = mul i32 %t13, %t13
+  %t15 = mul i32 %t14, %t14
+  %t16 = mul i32 %t15, %t15
+  %t17 = mul i32 %t16, %t16
+  %t18 = mul i32 %t17, %t17
+  %t19 = mul i32 %t18, %t18
+  %t20 = mul i32 %t19, %t19
+  %t21 = mul i32 %t20, %t20
+  %t22 = mul i32 %t21, %t21
+  %t23 = mul i32 %t22, %t22
+  %t24 = mul i32 %t23, %t23
+  %t25 = mul i32 %t24, %t24
+  %t26 = mul i32 %t25, %t25
+  %t27 = mul i32 %t26, %t26
+  %t28 = mul i32 %t27, %t27
+  ret i32 %t28
+}
diff --git a/test/Transforms/Reassociate/mulfactor.ll b/test/Transforms/Reassociate/mulfactor.ll
index f279727..6c099b4 100644
--- a/test/Transforms/Reassociate/mulfactor.ll
+++ b/test/Transforms/Reassociate/mulfactor.ll
@@ -1,14 +1,134 @@
-; RUN: opt < %s -reassociate -instcombine -S | grep mul | count 2
+; RUN: opt < %s -reassociate -S | FileCheck %s
 
-; This should have exactly 2 multiplies when we're done.
+define i32 @test1(i32 %a, i32 %b) {
+; CHECK: @test1
+; CHECK: mul i32 %a, %a
+; CHECK-NEXT: mul i32 %a, 2
+; CHECK-NEXT: add
+; CHECK-NEXT: mul
+; CHECK-NEXT: add
+; CHECK-NEXT: ret
 
-define i32 @f(i32 %a, i32 %b) {
-	%tmp.2 = mul i32 %a, %a		; <i32> [#uses=1]
-	%tmp.5 = shl i32 %a, 1		; <i32> [#uses=1]
-	%tmp.6 = mul i32 %tmp.5, %b		; <i32> [#uses=1]
-	%tmp.10 = mul i32 %b, %b		; <i32> [#uses=1]
-	%tmp.7 = add i32 %tmp.6, %tmp.2		; <i32> [#uses=1]
-	%tmp.11 = add i32 %tmp.7, %tmp.10		; <i32> [#uses=1]
+entry:
+	%tmp.2 = mul i32 %a, %a
+	%tmp.5 = shl i32 %a, 1
+	%tmp.6 = mul i32 %tmp.5, %b
+	%tmp.10 = mul i32 %b, %b
+	%tmp.7 = add i32 %tmp.6, %tmp.2
+	%tmp.11 = add i32 %tmp.7, %tmp.10
 	ret i32 %tmp.11
 }
 
+define i32 @test2(i32 %t) {
+; CHECK: @test2
+; CHECK: mul
+; CHECK-NEXT: add
+; CHECK-NEXT: ret
+
+entry:
+	%a = mul i32 %t, 6
+	%b = mul i32 %t, 36
+	%c = add i32 %b, 15
+	%d = add i32 %c, %a
+	ret i32 %d
+}
+
+define i32 @test3(i32 %x) {
+; (x^8)
+; CHECK: @test3
+; CHECK: mul
+; CHECK-NEXT: mul
+; CHECK-NEXT: mul
+; CHECK-NEXT: ret
+
+entry:
+  %a = mul i32 %x, %x
+  %b = mul i32 %a, %x
+  %c = mul i32 %b, %x
+  %d = mul i32 %c, %x
+  %e = mul i32 %d, %x
+  %f = mul i32 %e, %x
+  %g = mul i32 %f, %x
+  ret i32 %g
+}
+
+define i32 @test4(i32 %x) {
+; (x^7)
+; CHECK: @test4
+; CHECK: mul
+; CHECK-NEXT: mul
+; CHECK-NEXT: mul
+; CHECK-NEXT: mul
+; CHECK-NEXT: ret
+
+entry:
+  %a = mul i32 %x, %x
+  %b = mul i32 %a, %x
+  %c = mul i32 %b, %x
+  %d = mul i32 %c, %x
+  %e = mul i32 %d, %x
+  %f = mul i32 %e, %x
+  ret i32 %f
+}
+
+define i32 @test5(i32 %x, i32 %y) {
+; (x^4) * (y^2)
+; CHECK: @test5
+; CHECK: mul
+; CHECK-NEXT: mul
+; CHECK-NEXT: mul
+; CHECK-NEXT: ret
+
+entry:
+  %a = mul i32 %x, %y
+  %b = mul i32 %a, %y
+  %c = mul i32 %b, %x
+  %d = mul i32 %c, %x
+  %e = mul i32 %d, %x
+  ret i32 %e
+}
+
+define i32 @test6(i32 %x, i32 %y, i32 %z) {
+; (x^5) * (y^3) * z
+; CHECK: @test6
+; CHECK: mul
+; CHECK-NEXT: mul
+; CHECK-NEXT: mul
+; CHECK-NEXT: mul
+; CHECK-NEXT: mul
+; CHECK-NEXT: mul
+; CHECK-NEXT: ret
+
+entry:
+  %a = mul i32 %x, %y
+  %b = mul i32 %a, %x
+  %c = mul i32 %b, %y
+  %d = mul i32 %c, %x
+  %e = mul i32 %d, %y
+  %f = mul i32 %e, %x
+  %g = mul i32 %f, %z
+  %h = mul i32 %g, %x
+  ret i32 %h
+}
+
+define i32 @test7(i32 %x, i32 %y, i32 %z) {
+; (x^4) * (y^3) * (z^2)
+; CHECK: @test7
+; CHECK: mul
+; CHECK-NEXT: mul
+; CHECK-NEXT: mul
+; CHECK-NEXT: mul
+; CHECK-NEXT: mul
+; CHECK-NEXT: ret
+
+entry:
+  %a = mul i32 %y, %x
+  %b = mul i32 %a, %z
+  %c = mul i32 %b, %z
+  %d = mul i32 %c, %x
+  %e = mul i32 %d, %y
+  %f = mul i32 %e, %y
+  %g = mul i32 %f, %x
+  %h = mul i32 %g, %x
+  ret i32 %h
+}
diff --git a/test/Transforms/Reassociate/mulfactor2.ll b/test/Transforms/Reassociate/mulfactor2.ll
deleted file mode 100644
index 8116554..0000000
--- a/test/Transforms/Reassociate/mulfactor2.ll
+++ /dev/null
@@ -1,15 +0,0 @@
-; This should turn into one multiply and one add.
-
-; RUN: opt < %s -instcombine -reassociate -instcombine -S > %t
-; RUN: grep mul %t | count 1
-; RUN: grep add %t | count 1
-
-define i32 @main(i32 %t) {
-	%tmp.3 = mul i32 %t, 12		; <i32> [#uses=1]
-	%tmp.4 = add i32 %tmp.3, 5		; <i32> [#uses=1]
-	%tmp.6 = mul i32 %t, 6		; <i32> [#uses=1]
-	%tmp.8 = mul i32 %tmp.4, 3		; <i32> [#uses=1]
-	%tmp.9 = add i32 %tmp.8, %tmp.6		; <i32> [#uses=1]
-	ret i32 %tmp.9
-}
-
diff --git a/test/Transforms/Reassociate/multistep.ll b/test/Transforms/Reassociate/multistep.ll
new file mode 100644
index 0000000..7466d2e
--- /dev/null
+++ b/test/Transforms/Reassociate/multistep.ll
@@ -0,0 +1,31 @@
+; RUN: opt < %s -reassociate -S | FileCheck %s
+
+define i64 @multistep1(i64 %a, i64 %b, i64 %c) {
+; Check that a*a*b+a*a*c is turned into a*(a*(b+c)).
+; CHECK: @multistep1
+  %t0 = mul i64 %a, %b
+  %t1 = mul i64 %a, %t0 ; a*(a*b)
+  %t2 = mul i64 %a, %c
+  %t3 = mul i64 %a, %t2 ; a*(a*c)
+  %t4 = add i64 %t1, %t3
+; CHECK-NEXT: add i64 %c, %b
+; CHECK-NEXT: mul i64 %tmp{{.*}}, %a
+; CHECK-NEXT: mul i64 %tmp{{.*}}, %a
+; CHECK-NEXT: ret
+  ret i64 %t4
+}
+
+define i64 @multistep2(i64 %a, i64 %b, i64 %c, i64 %d) {
+; Check that a*b+a*c+d is turned into a*(b+c)+d.
+; CHECK: @multistep2
+  %t0 = mul i64 %a, %b
+  %t1 = mul i64 %a, %c
+  %t2 = add i64 %t1, %d ; a*c+d
+  %t3 = add i64 %t0, %t2 ; a*b+(a*c+d)
+; CHECK-NEXT: add i64 %c, %b
+; CHECK-NEXT: mul i64 %tmp{{.*}}, %a
+; CHECK-NEXT: add i64 %tmp{{.*}}, %d
+; CHECK-NEXT: ret
+  ret i64 %t3
+}
+
diff --git a/test/Transforms/Reassociate/no-op.ll b/test/Transforms/Reassociate/no-op.ll
new file mode 100644
index 0000000..0444cf0
--- /dev/null
+++ b/test/Transforms/Reassociate/no-op.ll
@@ -0,0 +1,38 @@
+; RUN: opt < %s -reassociate -S | FileCheck %s
+
+; When there is nothing to do, or not much to do, check that reassociate leaves
+; things alone.
+
+declare void @use(i32)
+
+define void @test1(i32 %a, i32 %b) {
+; Shouldn't change or move any of the add instructions.  Should commute but
+; otherwise not change or move any of the mul instructions.
+; CHECK: @test1
+  %a0 = add nsw i32 %a, 1
+; CHECK-NEXT: %a0 = add nsw i32 %a, 1
+  %m0 = mul nsw i32 3, %a
+; CHECK-NEXT: %m0 = mul nsw i32 %a, 3
+  %a1 = add nsw i32 %a0, %b
+; CHECK-NEXT: %a1 = add nsw i32 %a0, %b
+  %m1 = mul nsw i32 %b, %m0
+; CHECK-NEXT: %m1 = mul nsw i32 %m0, %b
+  call void @use(i32 %a1)
+; CHECK-NEXT: call void @use
+  call void @use(i32 %m1)
+  ret void
+}
+
+define void @test2(i32 %a, i32 %b, i32 %c, i32 %d) {
+; The initial add doesn't change so should not lose the nsw flag.
+; CHECK: @test2
+  %a0 = add nsw i32 %b, %a
+; CHECK-NEXT: %a0 = add nsw i32 %b, %a
+  %a1 = add nsw i32 %a0, %d
+; CHECK-NEXT: %a1 = add i32 %a0, %c
+  %a2 = add nsw i32 %a1, %c
+; CHECK-NEXT: %a2 = add i32 %a1, %d
+  call void @use(i32 %a2)
+; CHECK-NEXT: call void @use
+  ret void
+}
diff --git a/test/Transforms/Reassociate/repeats.ll b/test/Transforms/Reassociate/repeats.ll
new file mode 100644
index 0000000..6a02047
--- /dev/null
+++ b/test/Transforms/Reassociate/repeats.ll
@@ -0,0 +1,252 @@
+; RUN: opt < %s -reassociate -S | FileCheck %s
+
+; Tests involving repeated operations on the same value.
+
+define i8 @nilpotent(i8 %x) {
+; CHECK: @nilpotent
+  %tmp = xor i8 %x, %x
+  ret i8 %tmp
+; CHECK: ret i8 0
+}
+
+define i2 @idempotent(i2 %x) {
+; CHECK: @idempotent
+  %tmp1 = and i2 %x, %x
+  %tmp2 = and i2 %tmp1, %x
+  %tmp3 = and i2 %tmp2, %x
+  ret i2 %tmp3
+; CHECK: ret i2 %x
+}
+
+define i2 @add(i2 %x) {
+; CHECK: @add
+  %tmp1 = add i2 %x, %x
+  %tmp2 = add i2 %tmp1, %x
+  %tmp3 = add i2 %tmp2, %x
+  ret i2 %tmp3
+; CHECK: ret i2 0
+}
+
+define i2 @cst_add() {
+; CHECK: @cst_add
+  %tmp1 = add i2 1, 1
+  %tmp2 = add i2 %tmp1, 1
+  ret i2 %tmp2
+; CHECK: ret i2 -1
+}
+
+define i8 @cst_mul() {
+; CHECK: @cst_mul
+  %tmp1 = mul i8 3, 3
+  %tmp2 = mul i8 %tmp1, 3
+  %tmp3 = mul i8 %tmp2, 3
+  %tmp4 = mul i8 %tmp3, 3
+  ret i8 %tmp4
+; CHECK: ret i8 -13
+}
+
+define i3 @foo3x5(i3 %x) {
+; Can be done with two multiplies.
+; CHECK: @foo3x5
+; CHECK-NEXT: mul
+; CHECK-NEXT: mul
+; CHECK-NEXT: ret
+  %tmp1 = mul i3 %x, %x
+  %tmp2 = mul i3 %tmp1, %x
+  %tmp3 = mul i3 %tmp2, %x
+  %tmp4 = mul i3 %tmp3, %x
+  ret i3 %tmp4
+}
+
+define i3 @foo3x6(i3 %x) {
+; Can be done with two multiplies.
+; CHECK: @foo3x6
+; CHECK-NEXT: mul
+; CHECK-NEXT: mul
+; CHECK-NEXT: ret
+  %tmp1 = mul i3 %x, %x
+  %tmp2 = mul i3 %tmp1, %x
+  %tmp3 = mul i3 %tmp2, %x
+  %tmp4 = mul i3 %tmp3, %x
+  %tmp5 = mul i3 %tmp4, %x
+  ret i3 %tmp5
+}
+
+define i3 @foo3x7(i3 %x) {
+; Can be done with two multiplies.
+; CHECK: @foo3x7
+; CHECK-NEXT: mul
+; CHECK-NEXT: mul
+; CHECK-NEXT: ret
+  %tmp1 = mul i3 %x, %x
+  %tmp2 = mul i3 %tmp1, %x
+  %tmp3 = mul i3 %tmp2, %x
+  %tmp4 = mul i3 %tmp3, %x
+  %tmp5 = mul i3 %tmp4, %x
+  %tmp6 = mul i3 %tmp5, %x
+  ret i3 %tmp6
+}
+
+define i4 @foo4x8(i4 %x) {
+; Can be done with two multiplies.
+; CHECK: @foo4x8
+; CHECK-NEXT: mul
+; CHECK-NEXT: mul
+; CHECK-NEXT: ret
+  %tmp1 = mul i4 %x, %x
+  %tmp2 = mul i4 %tmp1, %x
+  %tmp3 = mul i4 %tmp2, %x
+  %tmp4 = mul i4 %tmp3, %x
+  %tmp5 = mul i4 %tmp4, %x
+  %tmp6 = mul i4 %tmp5, %x
+  %tmp7 = mul i4 %tmp6, %x
+  ret i4 %tmp7
+}
+
+define i4 @foo4x9(i4 %x) {
+; Can be done with three multiplies.
+; CHECK: @foo4x9
+; CHECK-NEXT: mul
+; CHECK-NEXT: mul
+; CHECK-NEXT: mul
+; CHECK-NEXT: ret
+  %tmp1 = mul i4 %x, %x
+  %tmp2 = mul i4 %tmp1, %x
+  %tmp3 = mul i4 %tmp2, %x
+  %tmp4 = mul i4 %tmp3, %x
+  %tmp5 = mul i4 %tmp4, %x
+  %tmp6 = mul i4 %tmp5, %x
+  %tmp7 = mul i4 %tmp6, %x
+  %tmp8 = mul i4 %tmp7, %x
+  ret i4 %tmp8
+}
+
+define i4 @foo4x10(i4 %x) {
+; Can be done with three multiplies.
+; CHECK: @foo4x10
+; CHECK-NEXT: mul
+; CHECK-NEXT: mul
+; CHECK-NEXT: mul
+; CHECK-NEXT: ret
+  %tmp1 = mul i4 %x, %x
+  %tmp2 = mul i4 %tmp1, %x
+  %tmp3 = mul i4 %tmp2, %x
+  %tmp4 = mul i4 %tmp3, %x
+  %tmp5 = mul i4 %tmp4, %x
+  %tmp6 = mul i4 %tmp5, %x
+  %tmp7 = mul i4 %tmp6, %x
+  %tmp8 = mul i4 %tmp7, %x
+  %tmp9 = mul i4 %tmp8, %x
+  ret i4 %tmp9
+}
+
+define i4 @foo4x11(i4 %x) {
+; Can be done with four multiplies.
+; CHECK: @foo4x11
+; CHECK-NEXT: mul
+; CHECK-NEXT: mul
+; CHECK-NEXT: mul
+; CHECK-NEXT: mul
+; CHECK-NEXT: ret
+  %tmp1 = mul i4 %x, %x
+  %tmp2 = mul i4 %tmp1, %x
+  %tmp3 = mul i4 %tmp2, %x
+  %tmp4 = mul i4 %tmp3, %x
+  %tmp5 = mul i4 %tmp4, %x
+  %tmp6 = mul i4 %tmp5, %x
+  %tmp7 = mul i4 %tmp6, %x
+  %tmp8 = mul i4 %tmp7, %x
+  %tmp9 = mul i4 %tmp8, %x
+  %tmp10 = mul i4 %tmp9, %x
+  ret i4 %tmp10
+}
+
+define i4 @foo4x12(i4 %x) {
+; Can be done with two multiplies.
+; CHECK: @foo4x12
+; CHECK-NEXT: mul
+; CHECK-NEXT: mul
+; CHECK-NEXT: ret
+  %tmp1 = mul i4 %x, %x
+  %tmp2 = mul i4 %tmp1, %x
+  %tmp3 = mul i4 %tmp2, %x
+  %tmp4 = mul i4 %tmp3, %x
+  %tmp5 = mul i4 %tmp4, %x
+  %tmp6 = mul i4 %tmp5, %x
+  %tmp7 = mul i4 %tmp6, %x
+  %tmp8 = mul i4 %tmp7, %x
+  %tmp9 = mul i4 %tmp8, %x
+  %tmp10 = mul i4 %tmp9, %x
+  %tmp11 = mul i4 %tmp10, %x
+  ret i4 %tmp11
+}
+
+define i4 @foo4x13(i4 %x) {
+; Can be done with three multiplies.
+; CHECK: @foo4x13
+; CHECK-NEXT: mul
+; CHECK-NEXT: mul
+; CHECK-NEXT: mul
+; CHECK-NEXT: ret
+  %tmp1 = mul i4 %x, %x
+  %tmp2 = mul i4 %tmp1, %x
+  %tmp3 = mul i4 %tmp2, %x
+  %tmp4 = mul i4 %tmp3, %x
+  %tmp5 = mul i4 %tmp4, %x
+  %tmp6 = mul i4 %tmp5, %x
+  %tmp7 = mul i4 %tmp6, %x
+  %tmp8 = mul i4 %tmp7, %x
+  %tmp9 = mul i4 %tmp8, %x
+  %tmp10 = mul i4 %tmp9, %x
+  %tmp11 = mul i4 %tmp10, %x
+  %tmp12 = mul i4 %tmp11, %x
+  ret i4 %tmp12
+}
+
+define i4 @foo4x14(i4 %x) {
+; Can be done with three multiplies.
+; CHECK: @foo4x14
+; CHECK-NEXT: mul
+; CHECK-NEXT: mul
+; CHECK-NEXT: mul
+; CHECK-NEXT: ret
+  %tmp1 = mul i4 %x, %x
+  %tmp2 = mul i4 %tmp1, %x
+  %tmp3 = mul i4 %tmp2, %x
+  %tmp4 = mul i4 %tmp3, %x
+  %tmp5 = mul i4 %tmp4, %x
+  %tmp6 = mul i4 %tmp5, %x
+  %tmp7 = mul i4 %tmp6, %x
+  %tmp8 = mul i4 %tmp7, %x
+  %tmp9 = mul i4 %tmp8, %x
+  %tmp10 = mul i4 %tmp9, %x
+  %tmp11 = mul i4 %tmp10, %x
+  %tmp12 = mul i4 %tmp11, %x
+  %tmp13 = mul i4 %tmp12, %x
+  ret i4 %tmp13
+}
+
+define i4 @foo4x15(i4 %x) {
+; Can be done with four multiplies.
+; CHECK: @foo4x15
+; CHECK-NEXT: mul
+; CHECK-NEXT: mul
+; CHECK-NEXT: mul
+; CHECK-NEXT: mul
+; CHECK-NEXT: ret
+  %tmp1 = mul i4 %x, %x
+  %tmp2 = mul i4 %tmp1, %x
+  %tmp3 = mul i4 %tmp2, %x
+  %tmp4 = mul i4 %tmp3, %x
+  %tmp5 = mul i4 %tmp4, %x
+  %tmp6 = mul i4 %tmp5, %x
+  %tmp7 = mul i4 %tmp6, %x
+  %tmp8 = mul i4 %tmp7, %x
+  %tmp9 = mul i4 %tmp8, %x
+  %tmp10 = mul i4 %tmp9, %x
+  %tmp11 = mul i4 %tmp10, %x
+  %tmp12 = mul i4 %tmp11, %x
+  %tmp13 = mul i4 %tmp12, %x
+  %tmp14 = mul i4 %tmp13, %x
+  ret i4 %tmp14
+}
diff --git a/test/Transforms/Reassociate/shifttest.ll b/test/Transforms/Reassociate/shifttest.ll
index 8b2cbc9..d9a5336 100644
--- a/test/Transforms/Reassociate/shifttest.ll
+++ b/test/Transforms/Reassociate/shifttest.ll
@@ -1,7 +1,7 @@
 ; With shl->mul reassociation, we can see that this is (shl A, 9) * A
 ;
 ; RUN: opt < %s -reassociate -instcombine -S |\
-; RUN:    grep {shl .*, 9}
+; RUN:    grep "shl .*, 9"
 
 define i32 @test(i32 %A, i32 %B) {
 	%X = shl i32 %A, 5		; <i32> [#uses=1]