Vendor import of llvm trunk r161861:

http://llvm.org/svn/llvm-project/llvm/trunk@161861

12 files changed, 774 insertions, 9 deletions

diff --git a/test/Transforms/LoopStrengthReduce/2012-07-13-ExpandUDiv.ll b/test/Transforms/LoopStrengthReduce/2012-07-13-ExpandUDiv.ll
new file mode 100644
index 0000000..a122208
--- /dev/null
+++ b/test/Transforms/LoopStrengthReduce/2012-07-13-ExpandUDiv.ll
@@ -0,0 +1,90 @@
+; RUN: opt -loop-reduce -S < %s | FileCheck %s
+;
+; PR11356: likely wrong code bug
+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-S128"
+target triple = "x86_64-apple-darwin"
+
+@g_66 = global [1 x i32] zeroinitializer, align 4
+@g_775 = global i32 0, align 4
+@g_752 = global i32 0, align 4
+@g_3 = global i32 0, align 4
+
+; Ensure that %div.i.i.us is not hoisted.
+; CHECK: @main
+; CHECK: for.body.i.i.us:
+; CHECK: %div.i.i.i.us
+; CHECK: %cmp5.i.i.us
+define i32 @main() nounwind uwtable ssp {
+entry:
+  %l_2 = alloca [1 x i32], align 4
+  %arrayidx = getelementptr inbounds [1 x i32]* %l_2, i64 0, i64 0
+  store i32 0, i32* %arrayidx, align 4, !tbaa !0
+  %tmp = load i32* @g_3, align 4, !tbaa !0
+  %idxprom = sext i32 %tmp to i64
+  %arrayidx1 = getelementptr inbounds [1 x i32]* %l_2, i64 0, i64 %idxprom
+  %tmp1 = load i32* %arrayidx1, align 4, !tbaa !0
+  %conv.i.i = and i32 %tmp1, 65535
+  %tobool.i.i.i = icmp ne i32 %tmp, 0
+  br label %codeRepl
+
+codeRepl.loopexit.us-lcssa:                       ; preds = %for.body.i.i, %codeRepl5
+  br label %codeRepl.loopexit
+
+codeRepl.loopexit:                                ; preds = %codeRepl.loopexit.us-lcssa.us, %codeRepl.loopexit.us-lcssa
+  br label %codeRepl
+
+codeRepl:                                         ; preds = %codeRepl.loopexit, %entry
+  br i1 %tobool.i.i.i, label %codeRepl.split.us, label %codeRepl.codeRepl.split_crit_edge
+
+codeRepl.codeRepl.split_crit_edge:                ; preds = %codeRepl
+  br label %codeRepl.split
+
+codeRepl.split.us:                                ; preds = %codeRepl
+  br label %for.cond.i.i.us
+
+for.cond.i.i.us:                                  ; preds = %for.inc.i.i.us, %codeRepl.split.us
+  %tmp2 = phi i32 [ 0, %codeRepl.split.us ], [ %add.i.i.us, %for.inc.i.i.us ]
+  br label %codeRepl5.us
+
+for.inc.i.i.us:                                   ; preds = %for.body.i.i.us
+  %add.i.i.us = add nsw i32 %tmp2, 1
+  store i32 %add.i.i.us, i32* @g_752, align 4, !tbaa !0
+  br label %for.cond.i.i.us
+
+for.body.i.i.us:                                  ; preds = %codeRepl5.us
+  %div.i.i.i.us = udiv i32 1, %conv.i.i
+  %cmp5.i.i.us = icmp eq i32 %div.i.i.i.us, %tmp2
+  br i1 %cmp5.i.i.us, label %codeRepl.loopexit.us-lcssa.us, label %for.inc.i.i.us
+
+codeRepl5.us:                                     ; preds = %for.cond.i.i.us
+  br i1 true, label %codeRepl.loopexit.us-lcssa.us, label %for.body.i.i.us
+
+codeRepl.loopexit.us-lcssa.us:                    ; preds = %codeRepl5.us, %for.body.i.i.us
+  br label %codeRepl.loopexit
+
+codeRepl.split:                                   ; preds = %codeRepl.codeRepl.split_crit_edge
+  br label %for.cond.i.i
+
+for.cond.i.i:                                     ; preds = %for.inc.i.i, %codeRepl.split
+  %tmp3 = phi i32 [ 0, %codeRepl.split ], [ %add.i.i, %for.inc.i.i ]
+  br label %codeRepl5
+
+codeRepl5:                                        ; preds = %for.cond.i.i
+  br i1 true, label %codeRepl.loopexit.us-lcssa, label %for.body.i.i
+
+for.body.i.i:                                     ; preds = %codeRepl5
+  %cmp5.i.i = icmp eq i32 0, %tmp3
+  br i1 %cmp5.i.i, label %codeRepl.loopexit.us-lcssa, label %for.inc.i.i
+
+for.inc.i.i:                                      ; preds = %for.body.i.i
+  %add.i.i = add nsw i32 %tmp3, 1
+  store i32 %add.i.i, i32* @g_752, align 4, !tbaa !0
+  br label %for.cond.i.i
+
+func_4.exit:                                      ; No predecessors!
+  ret i32 0
+}
+
+!0 = metadata !{metadata !"int", metadata !1}
+!1 = metadata !{metadata !"omnipotent char", metadata !2}
+!2 = metadata !{metadata !"Simple C/C++ TBAA", null}
diff --git a/test/Transforms/LoopStrengthReduce/2012-07-18-LimitReassociate.ll b/test/Transforms/LoopStrengthReduce/2012-07-18-LimitReassociate.ll
new file mode 100644
index 0000000..3793bac
--- /dev/null
+++ b/test/Transforms/LoopStrengthReduce/2012-07-18-LimitReassociate.ll
@@ -0,0 +1,517 @@
+; RUN: opt -loop-reduce -disable-output -debug-only=loop-reduce %s 2> %t
+; RUN: FileCheck %s < %t
+; REQUIRES: asserts
+;
+; PR13361: LSR + SCEV "hangs" on reasonably sized test with sequence of loops
+;
+; Without limits on CollectSubexpr, we have thousands of formulae for
+; the use that crosses loops. With limits we have five.
+; CHECK: LSR on loop %bb221:
+; CHECK: After generating reuse formulae:
+; CHECK: LSR is examining the following uses:
+; CHECK: LSR Use: Kind=Special
+; CHECK: {{.*reg\(\{\{\{\{\{\{\{\{\{}}
+; CHECK: {{.*reg\(\{\{\{\{\{\{\{\{\{}}
+; CHECK: {{.*reg\(\{\{\{\{\{\{\{\{\{}}
+; CHECK: {{.*reg\(\{\{\{\{\{\{\{\{\{}}
+; CHECK: {{.*reg\(\{\{\{\{\{\{\{\{\{}}
+; CHECK-NOT:reg
+; CHECK: Filtering for use
+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-S128"
+target triple = "x86_64-unknown-freebsd9"
+
+%struct.snork = type { %struct.fuga, i32, i32, i32, i32, i32, i32 }
+%struct.fuga = type { %struct.gork, i64 }
+%struct.gork = type { i8*, i32, i32, %struct.noot* }
+%struct.noot = type opaque
+%struct.jim = type { [5120 x i8], i32, i32, [2048 x i8], i32, [256 x i8] }
+
+@global = external global %struct.snork, align 8
+@global1 = external hidden unnamed_addr constant [52 x i8], align 1
+@global2 = external hidden unnamed_addr constant [18 x i8], align 1
+@global3 = external hidden global %struct.jim, align 32
+@global4 = external hidden unnamed_addr constant [40 x i8], align 1
+
+declare void @snork(...) nounwind
+
+declare fastcc void @blarg() nounwind uwtable readonly
+
+define hidden fastcc void @boogle() nounwind uwtable {
+bb:
+  %tmp = trunc i64 0 to i32
+  %tmp1 = icmp slt i32 %tmp, 2047
+  %tmp2 = add i32 0, -1
+  %tmp3 = icmp ult i32 %tmp2, 255
+  %tmp4 = and i1 %tmp1, %tmp3
+  br i1 %tmp4, label %bb6, label %bb5
+
+bb5:                                              ; preds = %bb
+  tail call void (...)* @snork(i8* getelementptr inbounds ([52 x i8]* @global1, i64 0, i64 0), i32 2021) nounwind
+  tail call void (...)* @snork(i8* getelementptr inbounds (%struct.jim* @global3, i64 0, i32 3, i64 1), i32 -2146631418) nounwind
+  unreachable
+
+bb6:                                              ; preds = %bb
+  tail call void @zot(i8* getelementptr inbounds (%struct.jim* @global3, i64 0, i32 5, i64 0), i8* getelementptr inbounds (%struct.jim* @global3, i64 0, i32 3, i64 1), i64 undef, i32 1, i1 false) nounwind
+  %tmp7 = getelementptr inbounds %struct.jim* @global3, i64 0, i32 5, i64 undef
+  store i8 0, i8* %tmp7, align 1
+  %tmp8 = add nsw i32 0, 1
+  %tmp9 = sext i32 %tmp8 to i64
+  %tmp10 = add i64 %tmp9, 1
+  %tmp11 = getelementptr inbounds %struct.jim* @global3, i64 0, i32 3, i64 %tmp10
+  %tmp12 = sub i64 2047, %tmp9
+  %tmp13 = icmp eq i32 undef, 1
+  br i1 %tmp13, label %bb14, label %bb15
+
+bb14:                                             ; preds = %bb6
+  tail call fastcc void @blarg()
+  unreachable
+
+bb15:                                             ; preds = %bb6
+  %tmp16 = trunc i64 %tmp12 to i32
+  br label %bb17
+
+bb17:                                             ; preds = %bb26, %bb15
+  %tmp18 = phi i64 [ %tmp28, %bb26 ], [ 0, %bb15 ]
+  %tmp19 = phi i32 [ %tmp29, %bb26 ], [ 0, %bb15 ]
+  %tmp20 = trunc i64 %tmp18 to i32
+  %tmp21 = icmp slt i32 %tmp20, %tmp16
+  br i1 %tmp21, label %bb22, label %bb32
+
+bb22:                                             ; preds = %bb17
+  %tmp23 = getelementptr inbounds %struct.jim* @global3, i64 0, i32 3, i64 0
+  %tmp24 = load i8* %tmp23, align 1
+  %tmp25 = icmp eq i8 %tmp24, 58
+  br i1 %tmp25, label %bb30, label %bb26
+
+bb26:                                             ; preds = %bb22
+  %tmp27 = icmp eq i8 %tmp24, 0
+  %tmp28 = add i64 %tmp18, 1
+  %tmp29 = add nsw i32 %tmp19, 1
+  br i1 %tmp27, label %bb32, label %bb17
+
+bb30:                                             ; preds = %bb22
+  %tmp31 = icmp ult i32 undef, 255
+  br i1 %tmp31, label %bb33, label %bb32
+
+bb32:                                             ; preds = %bb30, %bb26, %bb17
+  tail call void (...)* @snork(i8* getelementptr inbounds ([52 x i8]* @global1, i64 0, i64 0), i32 2038) nounwind
+  tail call void (...)* @snork(i8* %tmp11, i32 -2146631418) nounwind
+  unreachable
+
+bb33:                                             ; preds = %bb30
+  tail call void @zot(i8* getelementptr inbounds (%struct.jim* @global3, i64 0, i32 5, i64 0), i8* %tmp11, i64 undef, i32 1, i1 false) nounwind
+  %tmp34 = getelementptr inbounds %struct.jim* @global3, i64 0, i32 5, i64 undef
+  store i8 0, i8* %tmp34, align 1
+  %tmp35 = add nsw i32 %tmp19, 1
+  %tmp36 = sext i32 %tmp35 to i64
+  %tmp37 = add i64 %tmp36, %tmp10
+  %tmp38 = getelementptr inbounds %struct.jim* @global3, i64 0, i32 3, i64 %tmp37
+  %tmp39 = sub i64 %tmp12, %tmp36
+  br i1 false, label %bb40, label %bb41
+
+bb40:                                             ; preds = %bb33
+  br label %bb41
+
+bb41:                                             ; preds = %bb40, %bb33
+  %tmp42 = trunc i64 %tmp39 to i32
+  br label %bb43
+
+bb43:                                             ; preds = %bb52, %bb41
+  %tmp44 = phi i64 [ %tmp53, %bb52 ], [ 0, %bb41 ]
+  %tmp45 = phi i32 [ %tmp54, %bb52 ], [ 0, %bb41 ]
+  %tmp46 = trunc i64 %tmp44 to i32
+  %tmp47 = icmp slt i32 %tmp46, %tmp42
+  br i1 %tmp47, label %bb48, label %bb58
+
+bb48:                                             ; preds = %bb43
+  %tmp49 = add i64 %tmp44, %tmp37
+  %tmp50 = load i8* undef, align 1
+  %tmp51 = icmp eq i8 %tmp50, 58
+  br i1 %tmp51, label %bb55, label %bb52
+
+bb52:                                             ; preds = %bb48
+  %tmp53 = add i64 %tmp44, 1
+  %tmp54 = add nsw i32 %tmp45, 1
+  br i1 undef, label %bb58, label %bb43
+
+bb55:                                             ; preds = %bb48
+  %tmp56 = add i32 %tmp45, -1
+  %tmp57 = icmp ult i32 %tmp56, 255
+  br i1 %tmp57, label %bb59, label %bb58
+
+bb58:                                             ; preds = %bb55, %bb52, %bb43
+  tail call void (...)* @snork(i8* getelementptr inbounds ([52 x i8]* @global1, i64 0, i64 0), i32 2055) nounwind
+  tail call void (...)* @snork(i8* %tmp38, i32 -2146631418) nounwind
+  br label %bb247
+
+bb59:                                             ; preds = %bb55
+  %tmp60 = sext i32 %tmp45 to i64
+  tail call void @zot(i8* getelementptr inbounds (%struct.jim* @global3, i64 0, i32 5, i64 0), i8* %tmp38, i64 %tmp60, i32 1, i1 false) nounwind
+  %tmp61 = getelementptr inbounds %struct.jim* @global3, i64 0, i32 5, i64 %tmp60
+  store i8 0, i8* %tmp61, align 1
+  %tmp62 = add nsw i32 %tmp45, 1
+  %tmp63 = sext i32 %tmp62 to i64
+  %tmp64 = add i64 %tmp63, %tmp37
+  %tmp65 = sub i64 %tmp39, %tmp63
+  %tmp66 = icmp eq i32 undef, 2
+  br i1 %tmp66, label %bb67, label %bb68
+
+bb67:                                             ; preds = %bb59
+  tail call fastcc void @blarg()
+  unreachable
+
+bb68:                                             ; preds = %bb59
+  switch i32 undef, label %bb71 [
+    i32 0, label %bb74
+    i32 -1, label %bb69
+  ]
+
+bb69:                                             ; preds = %bb68
+  tail call void (...)* @snork(i8* getelementptr inbounds ([52 x i8]* @global1, i64 0, i64 0), i32 2071) nounwind
+  %tmp70 = load i32* getelementptr inbounds (%struct.snork* @global, i64 0, i32 2), align 4
+  unreachable
+
+bb71:                                             ; preds = %bb68
+  %tmp72 = load i32* getelementptr inbounds (%struct.snork* @global, i64 0, i32 4), align 4
+  %tmp73 = icmp eq i32 undef, 0
+  br i1 %tmp73, label %bb247, label %bb74
+
+bb74:                                             ; preds = %bb71, %bb68
+  %tmp75 = trunc i64 %tmp65 to i32
+  br label %bb76
+
+bb76:                                             ; preds = %bb82, %bb74
+  %tmp77 = phi i64 [ %tmp84, %bb82 ], [ 0, %bb74 ]
+  %tmp78 = phi i32 [ %tmp85, %bb82 ], [ 0, %bb74 ]
+  %tmp79 = trunc i64 %tmp77 to i32
+  %tmp80 = icmp slt i32 %tmp79, %tmp75
+  br i1 %tmp80, label %bb81, label %bb87
+
+bb81:                                             ; preds = %bb76
+  br i1 false, label %bb86, label %bb82
+
+bb82:                                             ; preds = %bb81
+  %tmp83 = icmp eq i8 0, 0
+  %tmp84 = add i64 %tmp77, 1
+  %tmp85 = add nsw i32 %tmp78, 1
+  br i1 %tmp83, label %bb87, label %bb76
+
+bb86:                                             ; preds = %bb81
+  br i1 undef, label %bb88, label %bb87
+
+bb87:                                             ; preds = %bb86, %bb82, %bb76
+  unreachable
+
+bb88:                                             ; preds = %bb86
+  %tmp89 = add nsw i32 %tmp78, 1
+  %tmp90 = sext i32 %tmp89 to i64
+  %tmp91 = add i64 %tmp90, %tmp64
+  %tmp92 = sub i64 %tmp65, %tmp90
+  br i1 false, label %bb93, label %bb94
+
+bb93:                                             ; preds = %bb88
+  unreachable
+
+bb94:                                             ; preds = %bb88
+  %tmp95 = trunc i64 %tmp92 to i32
+  br label %bb96
+
+bb96:                                             ; preds = %bb102, %bb94
+  %tmp97 = phi i64 [ %tmp103, %bb102 ], [ 0, %bb94 ]
+  %tmp98 = phi i32 [ %tmp104, %bb102 ], [ 0, %bb94 ]
+  %tmp99 = trunc i64 %tmp97 to i32
+  %tmp100 = icmp slt i32 %tmp99, %tmp95
+  br i1 %tmp100, label %bb101, label %bb106
+
+bb101:                                            ; preds = %bb96
+  br i1 undef, label %bb105, label %bb102
+
+bb102:                                            ; preds = %bb101
+  %tmp103 = add i64 %tmp97, 1
+  %tmp104 = add nsw i32 %tmp98, 1
+  br i1 false, label %bb106, label %bb96
+
+bb105:                                            ; preds = %bb101
+  br i1 undef, label %bb107, label %bb106
+
+bb106:                                            ; preds = %bb105, %bb102, %bb96
+  br label %bb247
+
+bb107:                                            ; preds = %bb105
+  %tmp108 = add nsw i32 %tmp98, 1
+  %tmp109 = sext i32 %tmp108 to i64
+  %tmp110 = add i64 %tmp109, %tmp91
+  %tmp111 = sub i64 %tmp92, %tmp109
+  br i1 false, label %bb112, label %bb113
+
+bb112:                                            ; preds = %bb107
+  unreachable
+
+bb113:                                            ; preds = %bb107
+  %tmp114 = trunc i64 %tmp111 to i32
+  br label %bb115
+
+bb115:                                            ; preds = %bb121, %bb113
+  %tmp116 = phi i64 [ %tmp122, %bb121 ], [ 0, %bb113 ]
+  %tmp117 = phi i32 [ %tmp123, %bb121 ], [ 0, %bb113 ]
+  %tmp118 = trunc i64 %tmp116 to i32
+  %tmp119 = icmp slt i32 %tmp118, %tmp114
+  br i1 %tmp119, label %bb120, label %bb125
+
+bb120:                                            ; preds = %bb115
+  br i1 undef, label %bb124, label %bb121
+
+bb121:                                            ; preds = %bb120
+  %tmp122 = add i64 %tmp116, 1
+  %tmp123 = add nsw i32 %tmp117, 1
+  br i1 false, label %bb125, label %bb115
+
+bb124:                                            ; preds = %bb120
+  br i1 false, label %bb126, label %bb125
+
+bb125:                                            ; preds = %bb124, %bb121, %bb115
+  unreachable
+
+bb126:                                            ; preds = %bb124
+  %tmp127 = add nsw i32 %tmp117, 1
+  %tmp128 = sext i32 %tmp127 to i64
+  %tmp129 = add i64 %tmp128, %tmp110
+  %tmp130 = sub i64 %tmp111, %tmp128
+  tail call fastcc void @blarg()
+  br i1 false, label %bb132, label %bb131
+
+bb131:                                            ; preds = %bb126
+  unreachable
+
+bb132:                                            ; preds = %bb126
+  %tmp133 = trunc i64 %tmp130 to i32
+  br label %bb134
+
+bb134:                                            ; preds = %bb140, %bb132
+  %tmp135 = phi i64 [ %tmp141, %bb140 ], [ 0, %bb132 ]
+  %tmp136 = phi i32 [ %tmp142, %bb140 ], [ 0, %bb132 ]
+  %tmp137 = trunc i64 %tmp135 to i32
+  %tmp138 = icmp slt i32 %tmp137, %tmp133
+  br i1 %tmp138, label %bb139, label %bb144
+
+bb139:                                            ; preds = %bb134
+  br i1 false, label %bb143, label %bb140
+
+bb140:                                            ; preds = %bb139
+  %tmp141 = add i64 %tmp135, 1
+  %tmp142 = add nsw i32 %tmp136, 1
+  br i1 false, label %bb144, label %bb134
+
+bb143:                                            ; preds = %bb139
+  br i1 false, label %bb145, label %bb144
+
+bb144:                                            ; preds = %bb143, %bb140, %bb134
+  br label %bb247
+
+bb145:                                            ; preds = %bb143
+  %tmp146 = add nsw i32 %tmp136, 1
+  %tmp147 = sext i32 %tmp146 to i64
+  %tmp148 = add i64 %tmp147, %tmp129
+  %tmp149 = sub i64 %tmp130, %tmp147
+  switch i32 0, label %bb152 [
+    i32 0, label %bb150
+    i32 16, label %bb150
+    i32 32, label %bb150
+    i32 48, label %bb150
+    i32 64, label %bb150
+    i32 256, label %bb150
+    i32 4096, label %bb150
+  ]
+
+bb150:                                            ; preds = %bb145, %bb145, %bb145, %bb145, %bb145, %bb145, %bb145
+  %tmp151 = trunc i64 %tmp149 to i32
+  br label %bb153
+
+bb152:                                            ; preds = %bb145
+  unreachable
+
+bb153:                                            ; preds = %bb160, %bb150
+  %tmp154 = phi i64 [ %tmp161, %bb160 ], [ 0, %bb150 ]
+  %tmp155 = phi i32 [ %tmp162, %bb160 ], [ 0, %bb150 ]
+  %tmp156 = trunc i64 %tmp154 to i32
+  %tmp157 = icmp slt i32 %tmp156, %tmp151
+  br i1 %tmp157, label %bb158, label %bb166
+
+bb158:                                            ; preds = %bb153
+  %tmp159 = add i64 %tmp154, %tmp148
+  br i1 false, label %bb163, label %bb160
+
+bb160:                                            ; preds = %bb158
+  %tmp161 = add i64 %tmp154, 1
+  %tmp162 = add nsw i32 %tmp155, 1
+  br i1 false, label %bb166, label %bb153
+
+bb163:                                            ; preds = %bb158
+  %tmp164 = add i32 %tmp155, -1
+  %tmp165 = icmp ult i32 %tmp164, 255
+  br i1 %tmp165, label %bb167, label %bb166
+
+bb166:                                            ; preds = %bb163, %bb160, %bb153
+  unreachable
+
+bb167:                                            ; preds = %bb163
+  %tmp168 = add nsw i32 %tmp155, 1
+  %tmp169 = sext i32 %tmp168 to i64
+  %tmp170 = add i64 %tmp169, %tmp148
+  %tmp171 = sub i64 %tmp149, %tmp169
+  br i1 false, label %bb173, label %bb172
+
+bb172:                                            ; preds = %bb167
+  unreachable
+
+bb173:                                            ; preds = %bb167
+  %tmp174 = trunc i64 %tmp171 to i32
+  br label %bb175
+
+bb175:                                            ; preds = %bb181, %bb173
+  %tmp176 = phi i64 [ %tmp183, %bb181 ], [ 0, %bb173 ]
+  %tmp177 = phi i32 [ %tmp184, %bb181 ], [ 0, %bb173 ]
+  %tmp178 = trunc i64 %tmp176 to i32
+  %tmp179 = icmp slt i32 %tmp178, %tmp174
+  br i1 %tmp179, label %bb180, label %bb186
+
+bb180:                                            ; preds = %bb175
+  br i1 false, label %bb185, label %bb181
+
+bb181:                                            ; preds = %bb180
+  %tmp182 = icmp eq i8 0, 0
+  %tmp183 = add i64 %tmp176, 1
+  %tmp184 = add nsw i32 %tmp177, 1
+  br i1 %tmp182, label %bb186, label %bb175
+
+bb185:                                            ; preds = %bb180
+  br i1 false, label %bb187, label %bb186
+
+bb186:                                            ; preds = %bb185, %bb181, %bb175
+  unreachable
+
+bb187:                                            ; preds = %bb185
+  %tmp188 = add nsw i32 %tmp177, 1
+  %tmp189 = sext i32 %tmp188 to i64
+  %tmp190 = sub i64 %tmp171, %tmp189
+  br i1 false, label %bb192, label %bb191
+
+bb191:                                            ; preds = %bb187
+  unreachable
+
+bb192:                                            ; preds = %bb187
+  %tmp193 = trunc i64 %tmp190 to i32
+  br label %bb194
+
+bb194:                                            ; preds = %bb200, %bb192
+  %tmp195 = phi i64 [ %tmp201, %bb200 ], [ 0, %bb192 ]
+  %tmp196 = phi i32 [ %tmp202, %bb200 ], [ 0, %bb192 ]
+  %tmp197 = trunc i64 %tmp195 to i32
+  %tmp198 = icmp slt i32 %tmp197, %tmp193
+  br i1 %tmp198, label %bb199, label %bb204
+
+bb199:                                            ; preds = %bb194
+  br i1 false, label %bb203, label %bb200
+
+bb200:                                            ; preds = %bb199
+  %tmp201 = add i64 %tmp195, 1
+  %tmp202 = add nsw i32 %tmp196, 1
+  br i1 false, label %bb204, label %bb194
+
+bb203:                                            ; preds = %bb199
+  br i1 undef, label %bb205, label %bb204
+
+bb204:                                            ; preds = %bb203, %bb200, %bb194
+  unreachable
+
+bb205:                                            ; preds = %bb203
+  %tmp206 = add nsw i32 %tmp196, 1
+  %tmp207 = sext i32 %tmp206 to i64
+  %tmp208 = add i64 %tmp207, 0
+  %tmp209 = sub i64 %tmp190, %tmp207
+  br i1 %tmp13, label %bb210, label %bb211
+
+bb210:                                            ; preds = %bb205
+  unreachable
+
+bb211:                                            ; preds = %bb205
+  %tmp212 = trunc i64 %tmp209 to i32
+  %tmp213 = icmp slt i32 0, %tmp212
+  br i1 false, label %bb215, label %bb214
+
+bb214:                                            ; preds = %bb211
+  unreachable
+
+bb215:                                            ; preds = %bb211
+  %tmp216 = add i64 undef, %tmp208
+  %tmp217 = sub i64 %tmp209, undef
+  br i1 false, label %bb218, label %bb219
+
+bb218:                                            ; preds = %bb215
+  br label %bb219
+
+bb219:                                            ; preds = %bb218, %bb215
+  %tmp220 = trunc i64 %tmp217 to i32
+  br label %bb221
+
+bb221:                                            ; preds = %bb230, %bb219
+  %tmp222 = phi i64 [ %tmp231, %bb230 ], [ 0, %bb219 ]
+  %tmp223 = phi i32 [ %tmp232, %bb230 ], [ 0, %bb219 ]
+  %tmp224 = trunc i64 %tmp222 to i32
+  %tmp225 = icmp slt i32 %tmp224, %tmp220
+  br i1 %tmp225, label %bb226, label %bb234
+
+bb226:                                            ; preds = %bb221
+  %tmp227 = add i64 %tmp222, %tmp216
+  %tmp228 = getelementptr inbounds %struct.jim* @global3, i64 0, i32 3, i64 %tmp227
+  %tmp229 = load i8* %tmp228, align 1
+  br i1 false, label %bb233, label %bb230
+
+bb230:                                            ; preds = %bb226
+  %tmp231 = add i64 %tmp222, 1
+  %tmp232 = add nsw i32 %tmp223, 1
+  br i1 undef, label %bb234, label %bb221
+
+bb233:                                            ; preds = %bb226
+  br i1 undef, label %bb235, label %bb234
+
+bb234:                                            ; preds = %bb233, %bb230, %bb221
+  br label %bb247
+
+bb235:                                            ; preds = %bb233
+  %tmp236 = add nsw i32 %tmp223, 1
+  %tmp237 = sext i32 %tmp236 to i64
+  %tmp238 = sub i64 %tmp217, %tmp237
+  br i1 %tmp66, label %bb239, label %bb240
+
+bb239:                                            ; preds = %bb235
+  unreachable
+
+bb240:                                            ; preds = %bb235
+  switch i32 0, label %bb244 [
+    i32 0, label %bb241
+    i32 1, label %bb241
+    i32 4, label %bb241
+    i32 6, label %bb241
+    i32 9, label %bb241
+  ]
+
+bb241:                                            ; preds = %bb240, %bb240, %bb240, %bb240, %bb240
+  %tmp242 = trunc i64 %tmp238 to i32
+  %tmp243 = icmp slt i32 0, %tmp242
+  br i1 false, label %bb246, label %bb245
+
+bb244:                                            ; preds = %bb240
+  unreachable
+
+bb245:                                            ; preds = %bb241
+  unreachable
+
+bb246:                                            ; preds = %bb241
+  unreachable
+
+bb247:                                            ; preds = %bb234, %bb144, %bb106, %bb71, %bb58
+  ret void
+}
+
+declare void @zot(i8* nocapture, i8* nocapture, i64, i32, i1) nounwind
diff --git a/test/Transforms/LoopStrengthReduce/ARM/2012-06-15-lsr-noaddrmode.ll b/test/Transforms/LoopStrengthReduce/ARM/2012-06-15-lsr-noaddrmode.ll
new file mode 100644
index 0000000..b5124ea
--- /dev/null
+++ b/test/Transforms/LoopStrengthReduce/ARM/2012-06-15-lsr-noaddrmode.ll
@@ -0,0 +1,102 @@
+; RUN: llc < %s -O3 -march=thumb -mcpu=cortex-a8 | FileCheck %s
+;
+; LSR should only check for valid address modes when the IV user is a
+; memory address.
+; svn r158536, rdar://11635990
+;
+; Note that we still don't produce the best code here because we fail
+; to coalesce the IV. See <rdar://problem/11680670> [coalescer] IVs
+; need to be scheduled to expose coalescing.
+
+; LSR before the fix:
+;The chosen solution requires 4 regs, with addrec cost 1, plus 3 base adds, plus 2 setup cost:
+;  LSR Use: Kind=Special, Offsets={0}, all-fixups-outside-loop, widest fixup type: i32
+;    reg(%v3) + reg({0,+,-1}<%while.cond.i.i>) + imm(1)
+;  LSR Use: Kind=ICmpZero, Offsets={0}, widest fixup type: i32
+;    reg(%v3) + reg({0,+,-1}<%while.cond.i.i>)
+;  LSR Use: Kind=Address of i32, Offsets={0}, widest fixup type: i32*
+;    reg((-4 + (4 * %v3) + %v1)) + 4*reg({0,+,-1}<%while.cond.i.i>)
+;  LSR Use: Kind=Address of i32, Offsets={0}, widest fixup type: i32*
+;    reg((-4 + (4 * %v3) + %v4)) + 4*reg({0,+,-1}<%while.cond.i.i>)
+;  LSR Use: Kind=Special, Offsets={0}, all-fixups-outside-loop, widest fixup type: i32
+;    reg(%v3)
+;
+; LSR after the fix:
+;The chosen solution requires 4 regs, with addrec cost 1, plus 1 base add, plus 2 setup cost:
+;  LSR Use: Kind=Special, Offsets={0}, all-fixups-outside-loop, widest fixup type: i32
+;    reg({%v3,+,-1}<nsw><%while.cond.i.i>) + imm(1)
+;  LSR Use: Kind=ICmpZero, Offsets={0}, widest fixup type: i32
+;    reg({%v3,+,-1}<nsw><%while.cond.i.i>)
+;  LSR Use: Kind=Address of i32, Offsets={0}, widest fixup type: i32*
+;    reg((-4 + %v1)) + 4*reg({%v3,+,-1}<nsw><%while.cond.i.i>)
+;  LSR Use: Kind=Address of i32, Offsets={0}, widest fixup type: i32*
+;    reg((-4 + %v4)) + 4*reg({%v3,+,-1}<nsw><%while.cond.i.i>)
+;  LSR Use: Kind=Special, Offsets={0}, all-fixups-outside-loop, widest fixup type: i32
+;    reg(%v3)
+
+
+%s = type { i32* }
+
+@ncol = external global i32, align 4
+
+declare i32* @getptr() nounwind
+declare %s* @getstruct() nounwind
+
+; CHECK: @main
+; Check that the loop preheader contains no address computation.
+; CHECK: %end_of_chain
+; CHECK-NOT: add{{.*}}lsl
+; CHECK: ldr{{.*}}lsl #2
+; CHECK: ldr{{.*}}lsl #2
+define i32 @main() nounwind ssp {
+entry:
+  %v0 = load i32* @ncol, align 4, !tbaa !0
+  %v1 = tail call i32* @getptr() nounwind
+  %cmp10.i = icmp eq i32 %v0, 0
+  br label %while.cond.outer
+
+while.cond.outer:
+  %call18 = tail call %s* @getstruct() nounwind
+  br label %while.cond
+
+while.cond:
+  %cmp20 = icmp eq i32* %v1, null
+  br label %while.body
+
+while.body:
+  %v3 = load i32* @ncol, align 4, !tbaa !0
+  br label %end_of_chain
+
+end_of_chain:
+  %state.i = getelementptr inbounds %s* %call18, i32 0, i32 0
+  %v4 = load i32** %state.i, align 4, !tbaa !3
+  br label %while.cond.i.i
+
+while.cond.i.i:
+  %counter.0.i.i = phi i32 [ %v3, %end_of_chain ], [ %dec.i.i, %land.rhs.i.i ]
+  %dec.i.i = add nsw i32 %counter.0.i.i, -1
+  %tobool.i.i = icmp eq i32 %counter.0.i.i, 0
+  br i1 %tobool.i.i, label %where.exit, label %land.rhs.i.i
+
+land.rhs.i.i:
+  %arrayidx.i.i = getelementptr inbounds i32* %v4, i32 %dec.i.i
+  %v5 = load i32* %arrayidx.i.i, align 4, !tbaa !0
+  %arrayidx1.i.i = getelementptr inbounds i32* %v1, i32 %dec.i.i
+  %v6 = load i32* %arrayidx1.i.i, align 4, !tbaa !0
+  %cmp.i.i = icmp eq i32 %v5, %v6
+  br i1 %cmp.i.i, label %while.cond.i.i, label %equal_data.exit.i
+
+equal_data.exit.i:
+  ret i32 %counter.0.i.i
+
+where.exit:
+  br label %while.end.i
+
+while.end.i:
+  ret i32 %v3
+}
+
+!0 = metadata !{metadata !"int", metadata !1}
+!1 = metadata !{metadata !"omnipotent char", metadata !2}
+!2 = metadata !{metadata !"Simple C/C++ TBAA"}
+!3 = metadata !{metadata !"any pointer", metadata !1}
diff --git a/test/Transforms/LoopStrengthReduce/X86/2012-01-13-phielim.ll b/test/Transforms/LoopStrengthReduce/X86/2012-01-13-phielim.ll
index ed32ca8..c3b8b89 100644
--- a/test/Transforms/LoopStrengthReduce/X86/2012-01-13-phielim.ll
+++ b/test/Transforms/LoopStrengthReduce/X86/2012-01-13-phielim.ll
@@ -90,3 +90,59 @@ for.inc498:                                       ; preds = %for.inc498, %for.bo
 while.end:                                        ; preds = %entry
   ret void
 }
+
+; PR12898: SCEVExpander crash
+; Test redundant phi elimination when the deleted phi's increment is
+; itself a phi.
+;
+; CHECK: @test3
+; CHECK: %for.body3.lr.ph.us.i.loopexit
+; CHECK-NEXT: in Loop: Header
+; CHECK-NEXT: incq
+; CHECK-NEXT: %for.body3.us.i
+; CHECK-NEXT: Inner Loop
+; CHECK: testb
+; CHECK: jne
+; CHECK: jmp
+define fastcc void @test3(double* nocapture %u) nounwind uwtable ssp {
+entry:
+  br i1 undef, label %meshBB1, label %meshBB5
+
+for.inc8.us.i:                                    ; preds = %for.body3.us.i
+  br i1 undef, label %meshBB1, label %meshBB
+
+for.body3.us.i:                                   ; preds = %meshBB, %for.body3.lr.ph.us.i
+  %indvars.iv.i.SV.phi = phi i64 [ %indvars.iv.next.i, %meshBB ], [ 0, %for.body3.lr.ph.us.i ]
+  %storemerge13.us.i.SV.phi = phi i32 [ 0, %meshBB ], [ 0, %for.body3.lr.ph.us.i ]
+  %Opq.sa.calc12 = sub i32 undef, 227
+  %0 = add nsw i64 %indvars.iv.i.SV.phi, %indvars.iv8.i.SV.phi26
+  %1 = trunc i64 %0 to i32
+  %mul.i.us.i = mul nsw i32 0, %1
+  %arrayidx5.us.i = getelementptr inbounds double* %u, i64 %indvars.iv.i.SV.phi
+  %2 = load double* %arrayidx5.us.i, align 8
+  %indvars.iv.next.i = add i64 %indvars.iv.i.SV.phi, 1
+  br i1 undef, label %for.inc8.us.i, label %meshBB
+
+for.body3.lr.ph.us.i:                             ; preds = %meshBB1, %meshBB
+  %indvars.iv8.i.SV.phi26 = phi i64 [ undef, %meshBB1 ], [ %indvars.iv8.i.SV.phi24, %meshBB ]
+  %arrayidx.us.i = getelementptr inbounds double* undef, i64 %indvars.iv8.i.SV.phi26
+  %3 = add i64 %indvars.iv8.i.SV.phi26, 1
+  br label %for.body3.us.i
+
+for.inc8.us.i2:                                   ; preds = %meshBB5
+  unreachable
+
+eval_At_times_u.exit:                             ; preds = %meshBB5
+  ret void
+
+meshBB:                                           ; preds = %for.body3.us.i, %for.inc8.us.i
+  %indvars.iv8.i.SV.phi24 = phi i64 [ undef, %for.body3.us.i ], [ %3, %for.inc8.us.i ]
+  %meshStackVariable.phi = phi i32 [ %Opq.sa.calc12, %for.body3.us.i ], [ undef, %for.inc8.us.i ]
+  br i1 undef, label %for.body3.lr.ph.us.i, label %for.body3.us.i
+
+meshBB1:                                          ; preds = %for.inc8.us.i, %entry
+  br label %for.body3.lr.ph.us.i
+
+meshBB5:                                          ; preds = %entry
+  br i1 undef, label %eval_At_times_u.exit, label %for.inc8.us.i2
+}
diff --git a/test/Transforms/LoopStrengthReduce/dont-hoist-simple-loop-constants.ll b/test/Transforms/LoopStrengthReduce/dont-hoist-simple-loop-constants.ll
index 4136486..f7a82f6 100644
--- a/test/Transforms/LoopStrengthReduce/dont-hoist-simple-loop-constants.ll
+++ b/test/Transforms/LoopStrengthReduce/dont-hoist-simple-loop-constants.ll
@@ -1,5 +1,5 @@
 ; RUN: opt < %s -loop-reduce -S | \
-; RUN:   not grep {bitcast i32 1 to i32}
+; RUN:   not grep "bitcast i32 1 to i32"
 ; END.
 ; 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.
diff --git a/test/Transforms/LoopStrengthReduce/dont_reverse.ll b/test/Transforms/LoopStrengthReduce/dont_reverse.ll
index 4c5db04..d65213d 100644
--- a/test/Transforms/LoopStrengthReduce/dont_reverse.ll
+++ b/test/Transforms/LoopStrengthReduce/dont_reverse.ll
@@ -1,5 +1,5 @@
 ; RUN: opt < %s -loop-reduce -S \
-; RUN:    | grep {icmp eq i2 %lsr.iv.next, %xmp4344}
+; RUN:    | grep "icmp eq i2 %lsr.iv.next, %xmp4344"
 
 ; Don't reverse the iteration if the rhs of the compare is defined
 ; inside the loop.
diff --git a/test/Transforms/LoopStrengthReduce/invariant_value_first.ll b/test/Transforms/LoopStrengthReduce/invariant_value_first.ll
index 2ca6787..5c18809 100644
--- a/test/Transforms/LoopStrengthReduce/invariant_value_first.ll
+++ b/test/Transforms/LoopStrengthReduce/invariant_value_first.ll
@@ -1,6 +1,6 @@
 ; Check that the index of 'P[outer]' is pulled out of the loop.
 ; RUN: opt < %s -loop-reduce -S | \
-; RUN:   not grep {getelementptr.*%outer.*%INDVAR}
+; RUN:   not grep "getelementptr.*%outer.*%INDVAR"
 
 target datalayout = "e-p:32:32:32-n8:16:32"
 declare i1 @pred()
diff --git a/test/Transforms/LoopStrengthReduce/invariant_value_first_arg.ll b/test/Transforms/LoopStrengthReduce/invariant_value_first_arg.ll
index 86c4d91..8eb8f05 100644
--- a/test/Transforms/LoopStrengthReduce/invariant_value_first_arg.ll
+++ b/test/Transforms/LoopStrengthReduce/invariant_value_first_arg.ll
@@ -1,6 +1,6 @@
 ; Check that the index of 'P[outer]' is pulled out of the loop.
 ; RUN: opt < %s -loop-reduce -S | \
-; RUN:   not grep {getelementptr.*%outer.*%INDVAR}
+; RUN:   not grep "getelementptr.*%outer.*%INDVAR"
 
 target datalayout = "e-p:32:32:32-n32"
 declare i1 @pred()
diff --git a/test/Transforms/LoopStrengthReduce/pr2570.ll b/test/Transforms/LoopStrengthReduce/pr2570.ll
index 80efb9f..7b56971 100644
--- a/test/Transforms/LoopStrengthReduce/pr2570.ll
+++ b/test/Transforms/LoopStrengthReduce/pr2570.ll
@@ -1,4 +1,4 @@
-; RUN: opt < %s -loop-reduce -S | grep {phi\\>} | count 8
+; RUN: opt < %s -loop-reduce -S | grep "phi\>" | count 8
 ; PR2570
 
 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-f80:32:32"
diff --git a/test/Transforms/LoopStrengthReduce/quadradic-exit-value.ll b/test/Transforms/LoopStrengthReduce/quadradic-exit-value.ll
index 59f14fc..0118241 100644
--- a/test/Transforms/LoopStrengthReduce/quadradic-exit-value.ll
+++ b/test/Transforms/LoopStrengthReduce/quadradic-exit-value.ll
@@ -1,4 +1,4 @@
-; RUN: opt < %s -analyze -iv-users | grep {\{1,+,3,+,2\}<%loop> (post-inc with loop %loop)}
+; RUN: opt < %s -analyze -iv-users | grep "{1,+,3,+,2}<%loop> (post-inc with loop %loop)"
 
 ; The value of %r is dependent on a polynomial iteration expression.
 
diff --git a/test/Transforms/LoopStrengthReduce/use_postinc_value_outside_loop.ll b/test/Transforms/LoopStrengthReduce/use_postinc_value_outside_loop.ll
index 5ed37dd..005e4c6 100644
--- a/test/Transforms/LoopStrengthReduce/use_postinc_value_outside_loop.ll
+++ b/test/Transforms/LoopStrengthReduce/use_postinc_value_outside_loop.ll
@@ -1,5 +1,5 @@
 ; RUN: opt < %s -loop-reduce -S | \
-; RUN:   grep {add i32 %indvar630.ui, 1}
+; RUN:   grep "add i32 %indvar630.ui, 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 
diff --git a/test/Transforms/LoopStrengthReduce/var_stride_used_by_compare.ll b/test/Transforms/LoopStrengthReduce/var_stride_used_by_compare.ll
index 64ef4f9..3405b26 100644
--- a/test/Transforms/LoopStrengthReduce/var_stride_used_by_compare.ll
+++ b/test/Transforms/LoopStrengthReduce/var_stride_used_by_compare.ll
@@ -1,10 +1,10 @@
 ; Base should not be i*3, it should be i*2.
 ; RUN: opt < %s -loop-reduce -S | \
-; RUN:   not grep {mul.*%i, 3}
+; RUN:   not grep "mul.*%i, 3"
 
 ; Indvar should not start at zero:
 ; RUN: opt < %s -loop-reduce -S | \
-; RUN:   not grep {phi i32 .* 0}
+; RUN:   not grep "phi i32 .* 0"
 ; END.
 
 ; mul uint %i, 3