llvm/test/Transforms/LoopVectorize/first-order-recurrence-chains.ll

   1 ; RUN: opt -passes=loop-vectorize -force-vector-width=4 -force-vector-interleave=1 -S %s | FileCheck %s
   2
   3 define i16 @test_chained_first_order_recurrences_1(ptr %ptr) {
   4 ; CHECK-LABEL: @test_chained_first_order_recurrences_1
   5 ; CHECK:       vector.body:
   6 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, %vector.ph ], [ [[INDEX_NEXT:%.*]], %vector.body ]
   7 ; CHECK-NEXT:    [[VECTOR_RECUR:%.*]] = phi <4 x i16> [ <i16 poison, i16 poison, i16 poison, i16 22>, %vector.ph ], [ [[WIDE_LOAD:%.*]], %vector.body ]
   8 ; CHECK-NEXT:    [[VECTOR_RECUR1:%.*]] = phi <4 x i16> [ <i16 poison, i16 poison, i16 poison, i16 33>, %vector.ph ], [ [[TMP4:%.*]], %vector.body ]
   9 ; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[INDEX]], 0
  10 ; CHECK-NEXT:    [[TMP1:%.*]] = getelementptr inbounds i16, ptr [[PTR:%.*]], i64 [[TMP0]]
  11 ; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds i16, ptr [[TMP1]], i32 0
  12 ; CHECK-NEXT:    [[WIDE_LOAD]] = load <4 x i16>, ptr [[TMP2]], align 2
  13 ; CHECK-NEXT:    [[TMP4]] = shufflevector <4 x i16> [[VECTOR_RECUR]], <4 x i16> [[WIDE_LOAD]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
  14 ; CHECK-NEXT:    [[TMP5:%.*]] = shufflevector <4 x i16> [[VECTOR_RECUR1]], <4 x i16> [[TMP4]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
  15 ; CHECK-NEXT:    [[TMP6:%.*]] = add <4 x i16> [[TMP4]], [[TMP5]]
  16 ; CHECK-NEXT:    store <4 x i16> [[TMP6]], ptr [[TMP2]], align 2
  17 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
  18 ; CHECK-NEXT:    [[TMP8:%.*]] = icmp eq i64 [[INDEX_NEXT]], 1000
  19 ; CHECK-NEXT:    br i1 [[TMP8]], label %middle.block, label %vector.body
  20 ; CHECK:       middle.block:
  21 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT_FOR_PHI:%.*]] = extractelement <4 x i16> [[WIDE_LOAD]], i32 2
  22 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT_FOR_PHI3:%.*]] = extractelement <4 x i16> [[TMP4]], i32 2
  23 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT:%.*]] = extractelement <4 x i16> [[WIDE_LOAD]], i32 3
  24 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT2:%.*]] = extractelement <4 x i16> [[TMP4]], i32 3
  25 ;
  26 entry:
  27   br label %loop
  28
  29 loop:
  30   %for.1 = phi i16 [ 22, %entry ], [ %for.1.next, %loop ]
  31   %for.2 = phi i16 [ 33, %entry ], [ %for.1, %loop ]
  32   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
  33   %iv.next = add nuw nsw i64 %iv, 1
  34   %gep.ptr = getelementptr inbounds i16, ptr %ptr, i64 %iv
  35   %for.1.next = load i16, ptr %gep.ptr, align 2
  36   %add = add i16 %for.1, %for.2
  37   store i16 %add, ptr %gep.ptr
  38   %exitcond.not = icmp eq i64 %iv.next, 1000
  39   br i1 %exitcond.not, label %exit, label %loop
  40
  41 exit:
  42   %res = add i16 %for.1, %for.2
  43   ret i16 %res
  44 }
  45
  46 define i16 @test_chained_first_order_recurrences_2(ptr %ptr) {
  47 ; CHECK-LABEL: @test_chained_first_order_recurrences_2
  48 ; CHECK:       vector.body:
  49 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, %vector.ph ], [ [[INDEX_NEXT:%.*]], %vector.body ]
  50 ; CHECK-NEXT:    [[VECTOR_RECUR:%.*]] = phi <4 x i16> [ <i16 poison, i16 poison, i16 poison, i16 33>, %vector.ph ], [ [[TMP4:%.*]], %vector.body ]
  51 ; CHECK-NEXT:    [[VECTOR_RECUR1:%.*]] = phi <4 x i16> [ <i16 poison, i16 poison, i16 poison, i16 22>, %vector.ph ], [ [[WIDE_LOAD:%.*]], %vector.body ]
  52 ; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[INDEX]], 0
  53 ; CHECK-NEXT:    [[TMP1:%.*]] = getelementptr inbounds i16, ptr [[PTR:%.*]], i64 [[TMP0]]
  54 ; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds i16, ptr [[TMP1]], i32 0
  55 ; CHECK-NEXT:    [[WIDE_LOAD]] = load <4 x i16>, ptr [[TMP2]], align 2
  56 ; CHECK-NEXT:    [[TMP4]] = shufflevector <4 x i16> [[VECTOR_RECUR1]], <4 x i16> [[WIDE_LOAD]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
  57 ; CHECK-NEXT:    [[TMP5:%.*]] = shufflevector <4 x i16> [[VECTOR_RECUR]], <4 x i16> [[TMP4]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
  58 ; CHECK-NEXT:    [[TMP6:%.*]] = add <4 x i16> [[TMP4]], [[TMP5]]
  59 ; CHECK-NEXT:    store <4 x i16> [[TMP6]], ptr [[TMP2]], align 2
  60 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
  61 ; CHECK-NEXT:    [[TMP8:%.*]] = icmp eq i64 [[INDEX_NEXT]], 1000
  62 ; CHECK-NEXT:    br i1 [[TMP8]], label %middle.block, label %vector.body, !llvm.loop [[LOOP4:![0-9]+]]
  63 ; CHECK:      middle.block:
  64 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT_FOR_PHI:%.*]] = extractelement <4 x i16> [[TMP4]], i32 2
  65 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT_FOR_PHI3:%.*]] = extractelement <4 x i16> [[WIDE_LOAD]], i32 2
  66 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT:%.*]] = extractelement <4 x i16> [[TMP4]], i32 3
  67 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT2:%.*]] = extractelement <4 x i16> [[WIDE_LOAD]], i32 3
  68 ;
  69 entry:
  70   br label %loop
  71
  72 loop:
  73   %for.2 = phi i16 [ 33, %entry ], [ %for.1, %loop ]
  74   %for.1 = phi i16 [ 22, %entry ], [ %for.1.next, %loop ]
  75   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
  76   %iv.next = add nuw nsw i64 %iv, 1
  77   %gep.ptr = getelementptr inbounds i16, ptr %ptr, i64 %iv
  78   %for.1.next = load i16, ptr %gep.ptr, align 2
  79   %add = add i16 %for.1, %for.2
  80   store i16 %add, ptr %gep.ptr
  81   %exitcond.not = icmp eq i64 %iv.next, 1000
  82   br i1 %exitcond.not, label %exit, label %loop
  83
  84 exit:
  85   %res = add i16 %for.1, %for.2
  86   ret i16 %res
  87 }
  88
  89 define i16 @test_chained_first_order_recurrences_3(ptr %ptr) {
  90 ; CHECK-LABEL: @test_chained_first_order_recurrences_3
  91 ; CHECK:       vector.body:
  92 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, %vector.ph ], [ [[INDEX_NEXT:%.*]], %vector.body ]
  93 ; CHECK-NEXT:    [[VECTOR_RECUR:%.*]] = phi <4 x i16> [ <i16 poison, i16 poison, i16 poison, i16 22>, %vector.ph ], [ [[WIDE_LOAD:%.*]], %vector.body ]
  94 ; CHECK-NEXT:    [[VECTOR_RECUR1:%.*]] = phi <4 x i16> [ <i16 poison, i16 poison, i16 poison, i16 33>, %vector.ph ], [ [[TMP4:%.*]], %vector.body ]
  95 ; CHECK-NEXT:    [[VECTOR_RECUR2:%.*]] = phi <4 x i16> [ <i16 poison, i16 poison, i16 poison, i16 33>, %vector.ph ], [ [[TMP5:%.*]], %vector.body ]
  96 ; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[INDEX]], 0
  97 ; CHECK-NEXT:    [[TMP1:%.*]] = getelementptr inbounds i16, ptr [[PTR:%.*]], i64 [[TMP0]]
  98 ; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds i16, ptr [[TMP1]], i32 0
  99 ; CHECK-NEXT:    [[WIDE_LOAD]] = load <4 x i16>, ptr [[TMP2]], align 2
 100 ; CHECK-NEXT:    [[TMP4]] = shufflevector <4 x i16> [[VECTOR_RECUR]], <4 x i16> [[WIDE_LOAD]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
 101 ; CHECK-NEXT:    [[TMP5]] = shufflevector <4 x i16> [[VECTOR_RECUR1]], <4 x i16> [[TMP4]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
 102 ; CHECK-NEXT:    [[TMP6:%.*]] = shufflevector <4 x i16> [[VECTOR_RECUR2]], <4 x i16> [[TMP5]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
 103 ; CHECK-NEXT:    [[TMP7:%.*]] = add <4 x i16> [[TMP4]], [[TMP5]]
 104 ; CHECK-NEXT:    [[TMP8:%.*]] = add <4 x i16> [[TMP7]], [[TMP6]]
 105 ; CHECK-NEXT:    store <4 x i16> [[TMP8]], ptr [[TMP2]], align 2
 106 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
 107 ; CHECK-NEXT:    [[TMP10:%.*]] = icmp eq i64 [[INDEX_NEXT]], 1000
 108 ; CHECK-NEXT:    br i1 [[TMP10]], label %middle.block, label %vector.body, !llvm.loop [[LOOP6:![0-9]+]]
 109 ; CHECK:      middle.block:
 110 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT_FOR_PHI:%.*]] = extractelement <4 x i16> [[WIDE_LOAD]], i32 2
 111 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT_FOR_PHI4:%.*]] = extractelement <4 x i16> [[TMP4]], i32 2
 112 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT_FOR_PHI8:%.*]] = extractelement <4 x i16> [[TMP5]], i32 2
 113 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT:%.*]] = extractelement <4 x i16> [[WIDE_LOAD]], i32 3
 114 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT3:%.*]] = extractelement <4 x i16> [[TMP4]], i32 3
 115 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT7:%.*]] = extractelement <4 x i16> [[TMP5]], i32 3
 116 ;
 117 entry:
 118   br label %loop
 119
 120 loop:
 121   %for.1 = phi i16 [ 22, %entry ], [ %for.1.next, %loop ]
 122   %for.2 = phi i16 [ 33, %entry ], [ %for.1, %loop ]
 123   %for.3 = phi i16 [ 33, %entry ], [ %for.2, %loop ]
 124   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
 125   %iv.next = add nuw nsw i64 %iv, 1
 126   %gep.ptr = getelementptr inbounds i16, ptr %ptr, i64 %iv
 127   %for.1.next = load i16, ptr %gep.ptr, align 2
 128   %add.1 = add i16 %for.1, %for.2
 129   %add.2 = add i16 %add.1, %for.3
 130   store i16 %add.2, ptr %gep.ptr
 131   %exitcond.not = icmp eq i64 %iv.next, 1000
 132   br i1 %exitcond.not, label %exit, label %loop
 133
 134 exit:
 135   %res.1 = add i16 %for.1, %for.2
 136   %res.2 = add i16 %res.1, %for.3
 137   ret i16 %res.2
 138 }
 139
 140 define void @test_cyclic_phis(ptr %ptr) {
 141 ; CHECK-LABEL: @test_cyclic_phis
 142 ; CHECK-NOT: vector.body:
 143 ;
 144 entry:
 145   br label %loop
 146
 147 loop:
 148   %for.1 = phi i16 [ 22, %entry ], [ %for.2, %loop ]
 149   %for.2 = phi i16 [ 33, %entry ], [ %for.1, %loop ]
 150   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
 151   %iv.next = add nuw nsw i64 %iv, 1
 152   %gep.ptr = getelementptr inbounds i16, ptr %ptr, i64 %iv
 153   %for.1.next = load i16, ptr %gep.ptr, align 2
 154   %add = add i16 %for.1, %for.2
 155   store i16 %add, ptr %gep.ptr
 156   %exitcond.not = icmp eq i64 %iv.next, 1000
 157   br i1 %exitcond.not, label %exit, label %loop
 158
 159 exit:
 160   ret void
 161 }
 162
 163 define void @test_first_order_recurrences_incoming_cycle_preheader(ptr %ptr) {
 164 ; CHECK-LABEL: @test_first_order_recurrences_incoming_cycle_preheader
 165 ; CHECK:       vector.body:
 166 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, %vector.ph ], [ [[INDEX_NEXT:%.*]], %vector.body ]
 167 ; CHECK-NEXT:    [[VECTOR_RECUR:%.*]] = phi <4 x i16> [ <i16 poison, i16 poison, i16 poison, i16 0>, %vector.ph ], [ [[WIDE_LOAD:%.*]], %vector.body ]
 168 ; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[INDEX]], 0
 169 ; CHECK-NEXT:    [[TMP1:%.*]] = getelementptr inbounds i16, ptr [[PTR:%.*]], i64 [[TMP0]]
 170 ; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds i16, ptr [[TMP1]], i32 0
 171 ; CHECK-NEXT:    [[WIDE_LOAD]] = load <4 x i16>, ptr [[TMP2]], align 2
 172 ; CHECK-NEXT:    [[TMP4:%.*]] = shufflevector <4 x i16> [[VECTOR_RECUR]], <4 x i16> [[WIDE_LOAD]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
 173 ; CHECK-NEXT:    [[TMP5:%.*]] = add <4 x i16> [[TMP4]], splat (i16 10)
 174 ; CHECK-NEXT:    store <4 x i16> [[TMP5]], ptr [[TMP2]], align 2
 175 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
 176 ; CHECK-NEXT:    [[TMP7:%.*]] = icmp eq i64 [[INDEX_NEXT]], 1000
 177 ; CHECK-NEXT:    br i1 [[TMP7]], label %middle.block, label %vector.body
 178 ;
 179 entry:
 180   br label %loop.1
 181
 182 loop.1:
 183   %p = phi i16 [ 0, %entry ], [ %p, %loop.1 ]
 184   br i1 true, label %loop, label %loop.1
 185
 186 loop:
 187   %for.1 = phi i16 [ %p, %loop.1 ], [ %for.1.next, %loop ]
 188   %iv = phi i64 [ 0, %loop.1 ], [ %iv.next, %loop ]
 189   %iv.next = add nuw nsw i64 %iv, 1
 190   %gep.ptr = getelementptr inbounds i16, ptr %ptr, i64 %iv
 191   %for.1.next = load i16, ptr %gep.ptr, align 2
 192   %add = add i16 %for.1, 10
 193   store i16 %add, ptr %gep.ptr
 194   %exitcond.not = icmp eq i64 %iv.next, 1000
 195   br i1 %exitcond.not, label %exit, label %loop
 196
 197 exit:
 198   ret void
 199 }
 200
 201 define i16 @test_chained_first_order_recurrences_3_reordered_1(ptr %ptr) {
 202 ; CHECK-LABEL: @test_chained_first_order_recurrences_3_reordered_1
 203 ; CHECK:       vector.body:
 204 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, %vector.ph ], [ [[INDEX_NEXT:%.*]], %vector.body ]
 205 ; CHECK-NEXT:    [[VECTOR_RECUR2:%.*]] = phi <4 x i16> [ <i16 poison, i16 poison, i16 poison, i16 33>, %vector.ph ], [ [[TMP5:%.*]], %vector.body ]
 206 ; CHECK-NEXT:    [[VECTOR_RECUR1:%.*]] = phi <4 x i16> [ <i16 poison, i16 poison, i16 poison, i16 33>, %vector.ph ], [ [[TMP4:%.*]], %vector.body ]
 207 ; CHECK-NEXT:    [[VECTOR_RECUR:%.*]] = phi <4 x i16> [ <i16 poison, i16 poison, i16 poison, i16 22>, %vector.ph ], [ [[WIDE_LOAD:%.*]], %vector.body ]
 208 ; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[INDEX]], 0
 209 ; CHECK-NEXT:    [[TMP1:%.*]] = getelementptr inbounds i16, ptr [[PTR:%.*]], i64 [[TMP0]]
 210 ; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds i16, ptr [[TMP1]], i32 0
 211 ; CHECK-NEXT:    [[WIDE_LOAD]] = load <4 x i16>, ptr [[TMP2]], align 2
 212 ; CHECK-NEXT:    [[TMP4]] = shufflevector <4 x i16> [[VECTOR_RECUR]], <4 x i16> [[WIDE_LOAD]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
 213 ; CHECK-NEXT:    [[TMP5]] = shufflevector <4 x i16> [[VECTOR_RECUR1]], <4 x i16> [[TMP4]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
 214 ; CHECK-NEXT:    [[TMP6:%.*]] = shufflevector <4 x i16> [[VECTOR_RECUR2]], <4 x i16> [[TMP5]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
 215 ; CHECK-NEXT:    [[TMP7:%.*]] = add <4 x i16> [[TMP4]], [[TMP5]]
 216 ; CHECK-NEXT:    [[TMP8:%.*]] = add <4 x i16> [[TMP7]], [[TMP6]]
 217 ; CHECK-NEXT:    store <4 x i16> [[TMP8]], ptr [[TMP2]], align 2
 218 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
 219 ; CHECK-NEXT:    [[TMP10:%.*]] = icmp eq i64 [[INDEX_NEXT]], 1000
 220 ; CHECK-NEXT:    br i1 [[TMP10]], label %middle.block, label %vector.body, !llvm.loop [[LOOP6:![0-9]+]]
 221 ; CHECK:      middle.block:
 222 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT_FOR_PHI8:%.*]] = extractelement <4 x i16> [[TMP5]], i32 2
 223 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT_FOR_PHI4:%.*]] = extractelement <4 x i16> [[TMP4]], i32 2
 224 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT_FOR_PHI:%.*]] = extractelement <4 x i16> [[WIDE_LOAD]], i32 2
 225 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT7:%.*]] = extractelement <4 x i16> [[TMP5]], i32 3
 226 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT3:%.*]] = extractelement <4 x i16> [[TMP4]], i32 3
 227 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT:%.*]] = extractelement <4 x i16> [[WIDE_LOAD]], i32 3
 228 ;
 229 entry:
 230   br label %loop
 231
 232 loop:
 233   %for.3 = phi i16 [ 33, %entry ], [ %for.2, %loop ]
 234   %for.2 = phi i16 [ 33, %entry ], [ %for.1, %loop ]
 235   %for.1 = phi i16 [ 22, %entry ], [ %for.1.next, %loop ]
 236   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
 237   %iv.next = add nuw nsw i64 %iv, 1
 238   %gep.ptr = getelementptr inbounds i16, ptr %ptr, i64 %iv
 239   %for.1.next = load i16, ptr %gep.ptr, align 2
 240   %add.1 = add i16 %for.1, %for.2
 241   %add.2 = add i16 %add.1, %for.3
 242   store i16 %add.2, ptr %gep.ptr
 243   %exitcond.not = icmp eq i64 %iv.next, 1000
 244   br i1 %exitcond.not, label %exit, label %loop
 245
 246 exit:
 247   %res.1 = add i16 %for.1, %for.2
 248   %res.2 = add i16 %res.1, %for.3
 249   ret i16 %res.2
 250 }
 251
 252 define i16 @test_chained_first_order_recurrences_3_reordered_2(ptr %ptr) {
 253 ; CHECK-LABEL: @test_chained_first_order_recurrences_3_reordered_2
 254 ; CHECK:       vector.body:
 255 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, %vector.ph ], [ [[INDEX_NEXT:%.*]], %vector.body ]
 256 ; CHECK-NEXT:    [[VECTOR_RECUR1:%.*]] = phi <4 x i16> [ <i16 poison, i16 poison, i16 poison, i16 33>, %vector.ph ], [ [[TMP4:%.*]], %vector.body ]
 257 ; CHECK-NEXT:    [[VECTOR_RECUR2:%.*]] = phi <4 x i16> [ <i16 poison, i16 poison, i16 poison, i16 33>, %vector.ph ], [ [[TMP5:%.*]], %vector.body ]
 258 ; CHECK-NEXT:    [[VECTOR_RECUR:%.*]] = phi <4 x i16> [ <i16 poison, i16 poison, i16 poison, i16 22>, %vector.ph ], [ [[WIDE_LOAD:%.*]], %vector.body ]
 259 ; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[INDEX]], 0
 260 ; CHECK-NEXT:    [[TMP1:%.*]] = getelementptr inbounds i16, ptr [[PTR:%.*]], i64 [[TMP0]]
 261 ; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds i16, ptr [[TMP1]], i32 0
 262 ; CHECK-NEXT:    [[WIDE_LOAD]] = load <4 x i16>, ptr [[TMP2]], align 2
 263 ; CHECK-NEXT:    [[TMP4]] = shufflevector <4 x i16> [[VECTOR_RECUR]], <4 x i16> [[WIDE_LOAD]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
 264 ; CHECK-NEXT:    [[TMP5]] = shufflevector <4 x i16> [[VECTOR_RECUR1]], <4 x i16> [[TMP4]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
 265 ; CHECK-NEXT:    [[TMP6:%.*]] = shufflevector <4 x i16> [[VECTOR_RECUR2]], <4 x i16> [[TMP5]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
 266 ; CHECK-NEXT:    [[TMP7:%.*]] = add <4 x i16> [[TMP4]], [[TMP5]]
 267 ; CHECK-NEXT:    [[TMP8:%.*]] = add <4 x i16> [[TMP7]], [[TMP6]]
 268 ; CHECK-NEXT:    store <4 x i16> [[TMP8]], ptr [[TMP2]], align 2
 269 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
 270 ; CHECK-NEXT:    [[TMP10:%.*]] = icmp eq i64 [[INDEX_NEXT]], 1000
 271 ; CHECK-NEXT:    br i1 [[TMP10]], label %middle.block, label %vector.body, !llvm.loop [[LOOP6:![0-9]+]]
 272 ; CHECK:      middle.block:
 273 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT_FOR_PHI4:%.*]] = extractelement <4 x i16> [[TMP4]], i32 2
 274 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT_FOR_PHI8:%.*]] = extractelement <4 x i16> [[TMP5]], i32 2
 275 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT_FOR_PHI:%.*]] = extractelement <4 x i16> [[WIDE_LOAD]], i32 2
 276 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT3:%.*]] = extractelement <4 x i16> [[TMP4]], i32 3
 277 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT7:%.*]] = extractelement <4 x i16> [[TMP5]], i32 3
 278 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT:%.*]] = extractelement <4 x i16> [[WIDE_LOAD]], i32 3
 279 ;
 280 entry:
 281   br label %loop
 282
 283 loop:
 284   %for.2 = phi i16 [ 33, %entry ], [ %for.1, %loop ]
 285   %for.3 = phi i16 [ 33, %entry ], [ %for.2, %loop ]
 286   %for.1 = phi i16 [ 22, %entry ], [ %for.1.next, %loop ]
 287   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
 288   %iv.next = add nuw nsw i64 %iv, 1
 289   %gep.ptr = getelementptr inbounds i16, ptr %ptr, i64 %iv
 290   %for.1.next = load i16, ptr %gep.ptr, align 2
 291   %add.1 = add i16 %for.1, %for.2
 292   %add.2 = add i16 %add.1, %for.3
 293   store i16 %add.2, ptr %gep.ptr
 294   %exitcond.not = icmp eq i64 %iv.next, 1000
 295   br i1 %exitcond.not, label %exit, label %loop
 296
 297 exit:
 298   %res.1 = add i16 %for.1, %for.2
 299   %res.2 = add i16 %res.1, %for.3
 300   ret i16 %res.2
 301 }
 302
 303 define i16 @test_chained_first_order_recurrences_3_for2_no_other_uses(ptr %ptr) {
 304 ; CHECK-LABEL: @test_chained_first_order_recurrences_3_for2_no_other_uses
 305 ; CHECK:       vector.body:
 306 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, %vector.ph ], [ [[INDEX_NEXT:%.*]], %vector.body ]
 307 ; CHECK-NEXT:    [[VECTOR_RECUR:%.*]] = phi <4 x i16> [ <i16 poison, i16 poison, i16 poison, i16 22>, %vector.ph ], [ [[WIDE_LOAD:%.*]], %vector.body ]
 308 ; CHECK-NEXT:    [[VECTOR_RECUR1:%.*]] = phi <4 x i16> [ <i16 poison, i16 poison, i16 poison, i16 33>, %vector.ph ], [ [[TMP4:%.*]], %vector.body ]
 309 ; CHECK-NEXT:    [[VECTOR_RECUR2:%.*]] = phi <4 x i16> [ <i16 poison, i16 poison, i16 poison, i16 33>, %vector.ph ], [ [[TMP5:%.*]], %vector.body ]
 310 ; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[INDEX]], 0
 311 ; CHECK-NEXT:    [[TMP1:%.*]] = getelementptr inbounds i16, ptr [[PTR:%.*]], i64 [[TMP0]]
 312 ; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds i16, ptr [[TMP1]], i32 0
 313 ; CHECK-NEXT:    [[WIDE_LOAD]] = load <4 x i16>, ptr [[TMP2]], align 2
 314 ; CHECK-NEXT:    [[TMP4]] = shufflevector <4 x i16> [[VECTOR_RECUR]], <4 x i16> [[WIDE_LOAD]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
 315 ; CHECK-NEXT:    [[TMP5]] = shufflevector <4 x i16> [[VECTOR_RECUR1]], <4 x i16> [[TMP4]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
 316 ; CHECK-NEXT:    [[TMP6:%.*]] = shufflevector <4 x i16> [[VECTOR_RECUR2]], <4 x i16> [[TMP5]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
 317 ; CHECK-NEXT:    [[TMP7:%.*]] = add <4 x i16> [[TMP4]], splat (i16 10)
 318 ; CHECK-NEXT:    [[TMP8:%.*]] = add <4 x i16> [[TMP7]], [[TMP6]]
 319 ; CHECK-NEXT:    store <4 x i16> [[TMP8]], ptr [[TMP2]], align 2
 320 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
 321 ; CHECK-NEXT:    [[TMP10:%.*]] = icmp eq i64 [[INDEX_NEXT]], 1000
 322 ; CHECK-NEXT:    br i1 [[TMP10]], label %middle.block, label %vector.body, !llvm.loop [[LOOP6:![0-9]+]]
 323 ; CHECK:      middle.block:
 324 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT_FOR_PHI:%.*]] = extractelement <4 x i16> [[WIDE_LOAD]], i32 2
 325 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT_FOR_PHI4:%.*]] = extractelement <4 x i16> [[TMP4]], i32 2
 326 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT_FOR_PHI8:%.*]] = extractelement <4 x i16> [[TMP5]], i32 2
 327 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT:%.*]] = extractelement <4 x i16> [[WIDE_LOAD]], i32 3
 328 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT3:%.*]] = extractelement <4 x i16> [[TMP4]], i32 3
 329 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT7:%.*]] = extractelement <4 x i16> [[TMP5]], i32 3
 330 ;
 331 entry:
 332   br label %loop
 333
 334 loop:
 335   %for.1 = phi i16 [ 22, %entry ], [ %for.1.next, %loop ]
 336   %for.2 = phi i16 [ 33, %entry ], [ %for.1, %loop ]
 337   %for.3 = phi i16 [ 33, %entry ], [ %for.2, %loop ]
 338   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
 339   %iv.next = add nuw nsw i64 %iv, 1
 340   %gep.ptr = getelementptr inbounds i16, ptr %ptr, i64 %iv
 341   %for.1.next = load i16, ptr %gep.ptr, align 2
 342   %add.1 = add i16 %for.1, 10
 343   %add.2 = add i16 %add.1, %for.3
 344   store i16 %add.2, ptr %gep.ptr
 345   %exitcond.not = icmp eq i64 %iv.next, 1000
 346   br i1 %exitcond.not, label %exit, label %loop
 347
 348 exit:
 349   %res.1 = add i16 %for.1, %for.2
 350   %res.2 = add i16 %res.1, %for.3
 351   ret i16 %res.2
 352 }
 353
 354 define i16 @test_chained_first_order_recurrences_3_for1_for2_no_other_uses(ptr %ptr) {
 355 ; CHECK-LABEL: @test_chained_first_order_recurrences_3_for1_for2_no_other_uses
 356 ; CHECK:       vector.body:
 357 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, %vector.ph ], [ [[INDEX_NEXT:%.*]], %vector.body ]
 358 ; CHECK-NEXT:    [[VECTOR_RECUR:%.*]] = phi <4 x i16> [ <i16 poison, i16 poison, i16 poison, i16 22>, %vector.ph ], [ [[WIDE_LOAD:%.*]], %vector.body ]
 359 ; CHECK-NEXT:    [[VECTOR_RECUR1:%.*]] = phi <4 x i16> [ <i16 poison, i16 poison, i16 poison, i16 33>, %vector.ph ], [ [[TMP4:%.*]], %vector.body ]
 360 ; CHECK-NEXT:    [[VECTOR_RECUR2:%.*]] = phi <4 x i16> [ <i16 poison, i16 poison, i16 poison, i16 33>, %vector.ph ], [ [[TMP5:%.*]], %vector.body ]
 361 ; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[INDEX]], 0
 362 ; CHECK-NEXT:    [[TMP1:%.*]] = getelementptr inbounds i16, ptr [[PTR:%.*]], i64 [[TMP0]]
 363 ; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds i16, ptr [[TMP1]], i32 0
 364 ; CHECK-NEXT:    [[WIDE_LOAD]] = load <4 x i16>, ptr [[TMP2]], align 2
 365 ; CHECK-NEXT:    [[TMP4]] = shufflevector <4 x i16> [[VECTOR_RECUR]], <4 x i16> [[WIDE_LOAD]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
 366 ; CHECK-NEXT:    [[TMP5]] = shufflevector <4 x i16> [[VECTOR_RECUR1]], <4 x i16> [[TMP4]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
 367 ; CHECK-NEXT:    [[TMP6:%.*]] = shufflevector <4 x i16> [[VECTOR_RECUR2]], <4 x i16> [[TMP5]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
 368 ; CHECK-NEXT:    [[TMP8:%.*]] = add <4 x i16> [[TMP6]], splat (i16 10)
 369 ; CHECK-NEXT:    store <4 x i16> [[TMP8]], ptr [[TMP2]], align 2
 370 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
 371 ; CHECK-NEXT:    [[TMP10:%.*]] = icmp eq i64 [[INDEX_NEXT]], 1000
 372 ; CHECK-NEXT:    br i1 [[TMP10]], label %middle.block, label %vector.body, !llvm.loop [[LOOP6:![0-9]+]]
 373 ; CHECK:      middle.block:
 374 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT_FOR_PHI:%.*]] = extractelement <4 x i16> [[WIDE_LOAD]], i32 2
 375 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT_FOR_PHI4:%.*]] = extractelement <4 x i16> [[TMP4]], i32 2
 376 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT_FOR_PHI8:%.*]] = extractelement <4 x i16> [[TMP5]], i32 2
 377 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT:%.*]] = extractelement <4 x i16> [[WIDE_LOAD]], i32 3
 378 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT3:%.*]] = extractelement <4 x i16> [[TMP4]], i32 3
 379 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT7:%.*]] = extractelement <4 x i16> [[TMP5]], i32 3
 380 ;
 381 entry:
 382   br label %loop
 383
 384 loop:
 385   %for.1 = phi i16 [ 22, %entry ], [ %for.1.next, %loop ]
 386   %for.2 = phi i16 [ 33, %entry ], [ %for.1, %loop ]
 387   %for.3 = phi i16 [ 33, %entry ], [ %for.2, %loop ]
 388   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
 389   %iv.next = add nuw nsw i64 %iv, 1
 390   %gep.ptr = getelementptr inbounds i16, ptr %ptr, i64 %iv
 391   %for.1.next = load i16, ptr %gep.ptr, align 2
 392   %add.1 = add i16 %for.3, 10
 393   store i16 %add.1, ptr %gep.ptr
 394   %exitcond.not = icmp eq i64 %iv.next, 1000
 395   br i1 %exitcond.not, label %exit, label %loop
 396
 397 exit:
 398   %res.1 = add i16 %for.1, %for.2
 399   %res.2 = add i16 %res.1, %for.3
 400   ret i16 %res.2
 401 }
 402
 403 define double @test_chained_first_order_recurrence_sink_users_1(ptr %ptr) {
 404 ; CHECK-LABEL: @test_chained_first_order_recurrence_sink_users_1
 405 ; CHECK:       vector.body:
 406 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, %vector.ph ], [ [[INDEX_NEXT:%.*]], %vector.body ]
 407 ; CHECK-NEXT:    [[VECTOR_RECUR:%.*]] = phi <4 x double> [ <double poison, double poison, double poison, double 1.000000e+01>, %vector.ph ], [ [[WIDE_LOAD:%.*]], %vector.body ]
 408 ; CHECK-NEXT:    [[VECTOR_RECUR1:%.*]] = phi <4 x double> [ <double poison, double poison, double poison, double 2.000000e+01>, %vector.ph ], [ [[TMP4:%.*]], %vector.body ]
 409 ; CHECK-NEXT:    [[OFFSET_IDX:%.*]] = add i64 1, [[INDEX]]
 410 ; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[OFFSET_IDX]], 0
 411 ; CHECK-NEXT:    [[TMP1:%.*]] = getelementptr inbounds double, ptr [[PTR:%.*]], i64 [[TMP0]]
 412 ; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds double, ptr [[TMP1]], i32 0
 413 ; CHECK-NEXT:    [[WIDE_LOAD]] = load <4 x double>, ptr [[TMP2]], align 8
 414 ; CHECK-NEXT:    [[TMP4]] = shufflevector <4 x double> [[VECTOR_RECUR]], <4 x double> [[WIDE_LOAD]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
 415 ; CHECK-NEXT:    [[TMP5:%.*]] = shufflevector <4 x double> [[VECTOR_RECUR1]], <4 x double> [[TMP4]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
 416 ; CHECK-NEXT:    [[TMP6:%.*]] = fadd <4 x double> splat (double 1.000000e+01), [[TMP5]]
 417 ; CHECK-NEXT:    [[TMP7:%.*]] = fadd <4 x double> [[TMP6]], [[TMP4]]
 418 ; CHECK-NEXT:    store <4 x double> [[TMP7]], ptr [[TMP2]], align 8
 419 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
 420 ; CHECK-NEXT:    [[TMP9:%.*]] = icmp eq i64 [[INDEX_NEXT]], 996
 421 ; CHECK-NEXT:    br i1 [[TMP9]], label %middle.block, label %vector.body, !llvm.loop [[LOOP10:![0-9]+]]
 422 ; CHECK:       middle.block:
 423 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT_FOR_PHI:%.*]] = extractelement <4 x double> [[WIDE_LOAD]], i32 2
 424 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT_FOR_PHI3:%.*]] = extractelement <4 x double> [[TMP4]], i32 2
 425 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT:%.*]] = extractelement <4 x double> [[WIDE_LOAD]], i32 3
 426 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT2:%.*]] = extractelement <4 x double> [[TMP4]], i32 3
 427 ;
 428 entry:
 429   br label %loop
 430
 431 loop:
 432   %for.1 = phi double [ 10.0, %entry ], [ %for.1.next, %loop ]
 433   %for.2 = phi double [ 20.0, %entry ], [ %for.1, %loop ]
 434   %iv = phi i64 [ 1, %entry ], [ %iv.next, %loop ]
 435   %add.1 = fadd double 10.0, %for.2
 436   %add.2 = fadd double %add.1, %for.1
 437   %iv.next = add nuw nsw i64 %iv, 1
 438   %gep.ptr = getelementptr inbounds double, ptr %ptr, i64 %iv
 439   %for.1.next  = load double, ptr %gep.ptr, align 8
 440   store double %add.2, ptr %gep.ptr
 441   %exitcond.not = icmp eq i64 %iv.next, 1000
 442   br i1 %exitcond.not, label %exit, label %loop
 443
 444 exit:
 445   %res = fadd double %for.1, %for.2
 446   ret double %res
 447 }
 448
 449 define void @test_first_order_recurrences_and_reduction(ptr %ptr) {
 450 ; CHECK-LABEL: @test_first_order_recurrences_and_reduction(
 451 ; CHECK-NOT:   vector.body:
 452 ;
 453 entry:
 454   br label %loop
 455
 456 loop:
 457   %for.1 = phi i16 [ 22, %entry ], [ %red, %loop ]
 458   %red = phi i16 [ 33, %entry ], [ %red.next, %loop ]
 459   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
 460   %iv.next = add nuw nsw i64 %iv, 1
 461   %gep.ptr = getelementptr inbounds i16, ptr %ptr, i64 %iv
 462   %lv = load i16, ptr %gep.ptr
 463   %for.1.next = load i16, ptr %gep.ptr, align 2
 464   %add.1 = add i16 %for.1, 10
 465   %red.next = add i16 %red, %lv
 466   store i16 %add.1, ptr %gep.ptr
 467   %exitcond.not = icmp eq i64 %iv.next, 1000
 468   br i1 %exitcond.not, label %exit, label %loop
 469
 470 exit:
 471   ret void
 472 }
 473
 474 define i64 @test_first_order_recurrences_and_induction(ptr %ptr) {
 475 ; CHECK-LABEL: @test_first_order_recurrences_and_induction(
 476 ; CHECK:       vector.body:
 477 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, %vector.ph ], [ [[INDEX_NEXT:%.*]], %vector.body ]
 478 ; CHECK-NEXT:    [[VECTOR_RECUR:%.*]] = phi <4 x i64> [ <i64 poison, i64 poison, i64 poison, i64 22>, %vector.ph ], [ [[VEC_IND:%.*]], %vector.body ]
 479 ; CHECK-NEXT:    [[VEC_IND]] = phi <4 x i64> [ <i64 0, i64 1, i64 2, i64 3>, %vector.ph ], [ [[VEC_IND_NEXT:%.*]], %vector.body ]
 480 ; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[INDEX]], 0
 481 ; CHECK-NEXT:    [[TMP1:%.*]] = shufflevector <4 x i64> [[VECTOR_RECUR]], <4 x i64> [[VEC_IND]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
 482 ; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds i64, ptr [[PTR:%.*]], i64 [[TMP0]]
 483 ; CHECK-NEXT:    [[TMP4:%.*]] = add <4 x i64> [[TMP1]], splat (i64 10)
 484 ; CHECK-NEXT:    [[TMP3:%.*]] = getelementptr inbounds i64, ptr [[TMP2]], i32 0
 485 ; CHECK-NEXT:    store <4 x i64> [[TMP4]], ptr [[TMP3]], align 4
 486 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
 487 ; CHECK-NEXT:    [[VEC_IND_NEXT]] = add <4 x i64> [[VEC_IND]], splat (i64 4)
 488 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp eq i64 [[INDEX_NEXT]], 1000
 489 ; CHECK-NEXT:    br i1 [[TMP5]], label %middle.block, label %vector.body
 490 ; CHECK:       middle.block:
 491 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT_FOR_PHI:%.*]] = extractelement <4 x i64> [[VEC_IND]], i32 2
 492 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT:%.*]] = extractelement <4 x i64> [[VEC_IND]], i32 3
 493 ; CHECK-NEXT:    br i1 true
 494
 495 entry:
 496   br label %loop
 497
 498 loop:
 499   %for.1 = phi i64 [ 22, %entry ], [ %iv, %loop ]
 500   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
 501   %iv.next = add nuw nsw i64 %iv, 1
 502   %gep.ptr = getelementptr inbounds i64, ptr %ptr, i64 %iv
 503   %add.1 = add i64 %for.1, 10
 504   store i64 %add.1, ptr %gep.ptr
 505   %exitcond.not = icmp eq i64 %iv.next, 1000
 506   br i1 %exitcond.not, label %exit, label %loop
 507
 508 exit:
 509   ret i64 %for.1
 510 }
 511
 512 ; Same as @test_first_order_recurrences_and_induction but with order of phis
 513 ; flipped.
 514 define i64 @test_first_order_recurrences_and_induction2(ptr %ptr) {
 515 ; CHECK-LABEL: @test_first_order_recurrences_and_induction2(
 516 ; CHECK:       vector.body:
 517 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, %vector.ph ], [ [[INDEX_NEXT:%.*]], %vector.body ]
 518 ; CHECK-NEXT:    [[VEC_IND:%.*]] = phi <4 x i64> [ <i64 0, i64 1, i64 2, i64 3>, %vector.ph ], [ [[VEC_IND_NEXT:%.*]], %vector.body ]
 519 ; CHECK-NEXT:    [[VECTOR_RECUR:%.*]] = phi <4 x i64> [ <i64 poison, i64 poison, i64 poison, i64 22>, %vector.ph ], [ [[VEC_IND]], %vector.body ]
 520 ; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[INDEX]], 0
 521 ; CHECK-NEXT:    [[TMP1:%.*]] = shufflevector <4 x i64> [[VECTOR_RECUR]], <4 x i64> [[VEC_IND]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
 522 ; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds i64, ptr [[PTR:%.*]], i64 [[TMP0]]
 523 ; CHECK-NEXT:    [[TMP4:%.*]] = add <4 x i64> [[TMP1]], splat (i64 10)
 524 ; CHECK-NEXT:    [[TMP3:%.*]] = getelementptr inbounds i64, ptr [[TMP2]], i32 0
 525 ; CHECK-NEXT:    store <4 x i64> [[TMP4]], ptr [[TMP3]], align 4
 526 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
 527 ; CHECK-NEXT:    [[VEC_IND_NEXT]] = add <4 x i64> [[VEC_IND]], splat (i64 4)
 528 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp eq i64 [[INDEX_NEXT]], 1000
 529 ; CHECK-NEXT:    br i1 [[TMP5]], label %middle.block, label %vector.body
 530 ; CHECK:       middle.block:
 531 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT_FOR_PHI:%.*]] = extractelement <4 x i64> [[VEC_IND]], i32 2
 532 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT:%.*]] = extractelement <4 x i64> [[VEC_IND]], i32 3
 533 ; CHECK-NEXT:    br i1 true
 534 ;
 535 entry:
 536   br label %loop
 537
 538 loop:
 539   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
 540   %for.1 = phi i64 [ 22, %entry ], [ %iv, %loop ]
 541   %iv.next = add nuw nsw i64 %iv, 1
 542   %gep.ptr = getelementptr inbounds i64, ptr %ptr, i64 %iv
 543   %add.1 = add i64 %for.1, 10
 544   store i64 %add.1, ptr %gep.ptr
 545   %exitcond.not = icmp eq i64 %iv.next, 1000
 546   br i1 %exitcond.not, label %exit, label %loop
 547
 548 exit:
 549   ret i64 %for.1
 550 }
 551
 552 define ptr @test_first_order_recurrences_and_pointer_induction1(ptr %ptr) {
 553 ; CHECK-LABEL: @test_first_order_recurrences_and_pointer_induction1(
 554 ; CHECK:       vector.ph:
 555 ; CHECK-NEXT:    [[IND_END:%.*]] = getelementptr i8, ptr [[PTR:%.*]], i64 4000
 556 ; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]
 557 ; CHECK:       vector.body:
 558 ; CHECK-NEXT:    [[POINTER_PHI:%.*]] = phi ptr [ [[PTR]], %vector.ph ], [ [[PTR_IND:%.*]], %vector.body ]
 559 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, %vector.ph ], [ [[INDEX_NEXT:%.*]], %vector.body ]
 560 ; CHECK-NEXT:    [[VECTOR_RECUR:%.*]] = phi <4 x ptr> [ <ptr poison, ptr poison, ptr poison, ptr null>, %vector.ph ], [ [[TMP0:%.*]], %vector.body ]
 561 ; CHECK-NEXT:    [[TMP0]] = getelementptr i8, ptr [[POINTER_PHI]], <4 x i64> <i64 0, i64 4, i64 8, i64 12>
 562 ; CHECK-NEXT:    [[TMP1:%.*]] = add i64 [[INDEX]], 0
 563 ; CHECK-NEXT:    [[TMP3:%.*]] = getelementptr inbounds ptr, ptr [[PTR]], i64 [[TMP1]]
 564 ; CHECK-NEXT:    [[TMP4:%.*]] = getelementptr inbounds ptr, ptr [[TMP3]], i32 0
 565 ; CHECK-NEXT:    store <4 x ptr> [[TMP0]], ptr [[TMP4]], align 8
 566 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
 567 ; CHECK-NEXT:    [[PTR_IND]] = getelementptr i8, ptr [[POINTER_PHI]], i64 16
 568 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp eq i64 [[INDEX_NEXT]], 1000
 569 ; CHECK-NEXT:    br i1 [[TMP5]], label %middle.block, label %vector.body
 570 ; CHECK:       middle.block:
 571 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT_FOR_PHI:%.*]] = extractelement <4 x ptr> [[TMP0]], i32 2
 572 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT:%.*]] = extractelement <4 x ptr> [[TMP0]], i32 3
 573 ; CHECK-NEXT:    br i1 true
 574 ;
 575 entry:
 576   br label %loop
 577
 578 loop:
 579   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
 580   %for.1 = phi ptr [ null, %entry ], [ %ptr.iv, %loop ]
 581   %ptr.iv = phi ptr [ %ptr, %entry ], [ %ptr.iv.next, %loop ]
 582   %iv.next = add nuw nsw i64 %iv, 1
 583   %gep.ptr = getelementptr inbounds ptr, ptr %ptr, i64 %iv
 584   store ptr %ptr.iv, ptr %gep.ptr
 585   %ptr.iv.next = getelementptr i32, ptr %ptr.iv, i64 1
 586   %exitcond.not = icmp eq i64 %iv.next, 1000
 587   br i1 %exitcond.not, label %exit, label %loop
 588
 589 exit:
 590   ret ptr %for.1
 591 }
 592
 593 ; same as @test_first_order_recurrences_and_pointer_induction1 but with order
 594 ; of phis flipped.
 595 define ptr @test_first_order_recurrences_and_pointer_induction2(ptr %ptr) {
 596 ; CHECK-LABEL: @test_first_order_recurrences_and_pointer_induction2(
 597 ; CHECK:       vector.ph:
 598 ; CHECK-NEXT:    [[IND_END:%.*]] = getelementptr i8, ptr [[PTR:%.*]], i64 4000
 599 ; CHECK-NEXT:    br label %vector.body
 600 ; CHECK:       vector.body:
 601 ; CHECK-NEXT:    [[POINTER_PHI:%.*]] = phi ptr [ [[PTR]], %vector.ph ], [ [[PTR_IND:%.*]], %vector.body ]
 602 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, %vector.ph ], [ [[INDEX_NEXT:%.*]], %vector.body ]
 603 ; CHECK-NEXT:    [[VECTOR_RECUR:%.*]] = phi <4 x ptr> [ <ptr poison, ptr poison, ptr poison, ptr null>, %vector.ph ], [ [[TMP0:%.*]], %vector.body ]
 604 ; CHECK-NEXT:    [[TMP0]] = getelementptr i8, ptr [[POINTER_PHI]], <4 x i64> <i64 0, i64 4, i64 8, i64 12>
 605 ; CHECK-NEXT:    [[TMP1:%.*]] = add i64 [[INDEX]], 0
 606 ; CHECK-NEXT:    [[TMP3:%.*]] = getelementptr inbounds ptr, ptr [[PTR]], i64 [[TMP1]]
 607 ; CHECK-NEXT:    [[TMP4:%.*]] = getelementptr inbounds ptr, ptr [[TMP3]], i32 0
 608 ; CHECK-NEXT:    store <4 x ptr> [[TMP0]], ptr [[TMP4]], align 8
 609 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
 610 ; CHECK-NEXT:    [[PTR_IND]] = getelementptr i8, ptr [[POINTER_PHI]], i64 16
 611 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp eq i64 [[INDEX_NEXT]], 1000
 612 ; CHECK-NEXT:    br i1 [[TMP5]], label %middle.block, label %vector.body
 613 ; CHECK:       middle.block:
 614 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT_FOR_PHI:%.*]] = extractelement <4 x ptr> [[TMP0]], i32 2
 615 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT:%.*]] = extractelement <4 x ptr> [[TMP0]], i32 3
 616 ; CHECK-NEXT:    br i1 true
 617 ;
 618 entry:
 619   br label %loop
 620
 621 loop:
 622   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
 623   %ptr.iv = phi ptr [ %ptr, %entry ], [ %ptr.iv.next, %loop ]
 624   %for.1 = phi ptr [ null, %entry ], [ %ptr.iv, %loop ]
 625   %iv.next = add nuw nsw i64 %iv, 1
 626   %gep.ptr = getelementptr inbounds ptr, ptr %ptr, i64 %iv
 627   store ptr %ptr.iv, ptr %gep.ptr
 628   %ptr.iv.next = getelementptr i32, ptr %ptr.iv, i64 1
 629   %exitcond.not = icmp eq i64 %iv.next, 1000
 630   br i1 %exitcond.not, label %exit, label %loop
 631
 632 exit:
 633   ret ptr %for.1
 634 }
 635
 636 ; In this test case, %USE_2_FORS uses 2 different fixed-order recurrences and
 637 ; it needs to be sunk past the previous value for both recurrences.
 638 define double @test_resinking_required(ptr %p, ptr noalias %a, ptr noalias %b) {
 639 ; CHECK-LABEL: @test_resinking_required(
 640 ; CHECK:       vector.body:
 641 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, %vector.ph ], [ [[INDEX_NEXT:%.*]], %vector.body ]
 642 ; CHECK-NEXT:    [[VECTOR_RECUR:%.*]] = phi <4 x double> [ <double poison, double poison, double poison, double 0.000000e+00>, %vector.ph ], [ [[BROADCAST_SPLAT:%.*]], %vector.body ]
 643 ; CHECK-NEXT:    [[VECTOR_RECUR1:%.*]] = phi <4 x double> [ <double poison, double poison, double poison, double 0.000000e+00>, %vector.ph ], [ [[BROADCAST_SPLAT4:%.*]], %vector.body ]
 644 ; CHECK-NEXT:    [[VECTOR_RECUR2:%.*]] = phi <4 x double> [ <double poison, double poison, double poison, double 0.000000e+00>, %vector.ph ], [ [[TMP4:%.*]], %vector.body ]
 645 ; CHECK-NEXT:    [[TMP0:%.*]] = load double, ptr %a, align 8
 646 ; CHECK-NEXT:    [[BROADCAST_SPLATINSERT:%.*]] = insertelement <4 x double> poison, double [[TMP0]], i64 0
 647 ; CHECK-NEXT:    [[BROADCAST_SPLAT]] = shufflevector <4 x double> [[BROADCAST_SPLATINSERT]], <4 x double> poison, <4 x i32> zeroinitializer
 648 ; CHECK-NEXT:    [[TMP1:%.*]] = shufflevector <4 x double> [[VECTOR_RECUR]], <4 x double> [[BROADCAST_SPLAT]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
 649 ; CHECK-NEXT:    [[TMP2:%.*]] = fdiv <4 x double> zeroinitializer, [[TMP1]]
 650 ; CHECK-NEXT:    [[TMP3:%.*]] = load double, ptr %b, align 8
 651 ; CHECK-NEXT:    [[BROADCAST_SPLATINSERT3:%.*]] = insertelement <4 x double> poison, double [[TMP3]], i64 0
 652 ; CHECK-NEXT:    [[BROADCAST_SPLAT4]] = shufflevector <4 x double> [[BROADCAST_SPLATINSERT3]], <4 x double> poison, <4 x i32> zeroinitializer
 653 ; CHECK-NEXT:    [[TMP4]] = shufflevector <4 x double> [[VECTOR_RECUR1]], <4 x double> [[BROADCAST_SPLAT4]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
 654 ; CHECK-NEXT:    [[TMP6:%.*]] = extractelement <4 x double> [[TMP2]], i32 3
 655 ; CHECK-NEXT:    store double [[TMP6]], ptr [[P:%.*]], align 8
 656 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
 657 ; CHECK-NEXT:    [[TMP7:%.*]] = icmp eq i64 [[INDEX_NEXT]], 1000
 658 ; CHECK-NEXT:    br i1 [[TMP7]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP28:![0-9]+]]
 659 ; CHECK:       middle.block:
 660 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT_FOR_PHI10:%.*]] = extractelement <4 x double> [[TMP4]], i32 2
 661 ; CHECK-NEXT:    [[VECTOR_RECUR_EXTRACT9:%.*]] = extractelement <4 x double> [[TMP4]], i32 3
 662 ; CHECK-NEXT:    br i1 true, label %End, label %scalar.ph
 663 ; CHECK:       scalar.ph:
 664 ; CHECK-NEXT:    phi double [ [[TMP0]], %middle.block ], [ 0.000000e+00, %Entry ]
 665 ; CHECK-NEXT:    phi double [ [[TMP3]], %middle.block ], [ 0.000000e+00, %Entry ]
 666 ; CHECK-NEXT:    phi double [ [[VECTOR_RECUR_EXTRACT9]], %middle.block ], [ 0.000000e+00, %Entry ]
 667 ; CHECK-NEXT:    %bc.resume.val = phi i64 [ 1000, %middle.block ], [ 0, %Entry ]
 668 ; CHECK:      End:
 669 ; CHECK-NEXT:    = phi double [ {{.+}}, %Loop ], [ [[TMP0]], %middle.block ]
 670 ; CHECK-NEXT:    = phi double [ {{.+}}, %Loop ], [ [[TMP3]], %middle.block ]
 671 ; CHECK-NEXT:    = phi double [ {{.+}}, %Loop ], [ [[VECTOR_RECUR_EXTRACT_FOR_PHI10]], %middle.block ]
 672 ;
 673 Entry:
 674   br label %Loop
 675
 676 Loop:
 677   %for.1 = phi double [ %l1, %Loop ], [ 0.000000e+00, %Entry ]
 678   %for.2 = phi double [ %l2, %Loop ], [ 0.000000e+00, %Entry ]
 679   %for.3 = phi double [ %for.2, %Loop ], [ 0.000000e+00, %Entry ]
 680   %iv = phi i64 [ %iv.next, %Loop ], [ 0, %Entry ]
 681   %USE_2_FORS = fdiv double %for.3, %for.1
 682   %div = fdiv double 0.000000e+00, %for.1
 683   %l1 = load double, ptr %a, align 8
 684   %iv.next= add nuw nsw i64 %iv, 1
 685   %l2 = load double, ptr %b, align 8
 686   store double %div, ptr %p, align 8
 687   %cond = icmp eq i64 %iv.next, 1000
 688   br i1 %cond, label %End, label %Loop
 689
 690 End:
 691   %res.1 = fadd double %for.1, %for.2
 692   %res.2 = fadd double %res.1, %for.3
 693   ret double %res.2
 694 }