llvm/test/Transforms/LoopVectorize/no_outside_user.ll

   1 ; RUN: opt -S -passes=loop-vectorize -force-vector-interleave=1 -force-vector-width=2 < %s 2>&1 | FileCheck %s
   2
   3 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-n8:16:32-S128"
   4
   5 @f = common global i32 0, align 4
   6 @.str = private unnamed_addr constant [4 x i8] c"%d\0A\00", align 1
   7 @c = common global i32 0, align 4
   8 @a = common global i32 0, align 4
   9 @b = common global i32 0, align 4
  10 @e = common global i32 0, align 4
  11
  12 ; It has a value that is used outside of the loop
  13 ; and is not a recognized reduction variable "tmp17".
  14 ; However, tmp17 is a non-header phi which is an allowed exit.
  15
  16 ; CHECK-LABEL: @test1(
  17 ; CHECK: %vec.ind = phi <2 x i32>
  18 ; CHECK: [[CMP:%[a-zA-Z0-9.]+]] = icmp sgt <2 x i32> %vec.ind, <i32 10, i32 10>
  19 ; CHECK: %predphi = select <2 x i1> [[CMP]], <2 x i32> <i32 1, i32 1>, <2 x i32> zeroinitializer
  20
  21 ; CHECK-LABEL: middle.block:
  22 ; CHECK:          [[E1:%[a-zA-Z0-9.]+]] = extractelement <2 x i32> %predphi, i32 1
  23
  24 ; CHECK-LABEL: f1.exit.loopexit:
  25 ; CHECK:          %.lcssa = phi i32 [ %tmp17, %bb16 ], [ [[E1]], %middle.block ]
  26
  27 define i32 @test1()  {
  28 bb:
  29   %b.promoted = load i32, ptr @b, align 4
  30   br label %.lr.ph.i
  31
  32 .lr.ph.i:
  33   %tmp8 = phi i32 [ %tmp18, %bb16 ], [ %b.promoted, %bb ]
  34   %tmp2 = icmp sgt i32 %tmp8, 10
  35   br i1 %tmp2, label %bb16, label %bb10
  36
  37 bb10:
  38   br label %bb16
  39
  40 bb16:
  41   %tmp17 = phi i32 [ 0, %bb10 ], [ 1, %.lr.ph.i ]
  42   %tmp18 = add nsw i32 %tmp8, 1
  43   %tmp19 = icmp slt i32 %tmp18, 4
  44   br i1 %tmp19, label %.lr.ph.i, label %f1.exit.loopexit
  45
  46 f1.exit.loopexit:
  47   %.lcssa = phi i32 [ %tmp17, %bb16 ]
  48   ret i32 %.lcssa
  49 }
  50
  51 ; non-hdr phi depends on header phi.
  52 ; CHECK-LABEL: @test2(
  53 ; CHECK: %vec.ind = phi <2 x i32>
  54 ; CHECK: [[CMP:%[a-zA-Z0-9.]+]] = icmp sgt <2 x i32> %vec.ind, <i32 10, i32 10>
  55 ; CHECK: %predphi = select <2 x i1> [[CMP]], <2 x i32> <i32 1, i32 1>, <2 x i32> %vec.ind
  56
  57 ; CHECK-LABEL: middle.block:
  58 ; CHECK:          [[E1:%[a-zA-Z0-9.]+]] = extractelement <2 x i32> %predphi, i32 1
  59
  60 ; CHECK-LABEL: f1.exit.loopexit:
  61 ; CHECK:          %.lcssa = phi i32 [ %tmp17, %bb16 ], [ [[E1]], %middle.block ]
  62 define i32 @test2()  {
  63 bb:
  64   %b.promoted = load i32, ptr @b, align 4
  65   br label %.lr.ph.i
  66
  67 .lr.ph.i:
  68   %tmp8 = phi i32 [ %tmp18, %bb16 ], [ %b.promoted, %bb ]
  69   %tmp2 = icmp sgt i32 %tmp8, 10
  70   br i1 %tmp2, label %bb16, label %bb10
  71
  72 bb10:
  73   br label %bb16
  74
  75 bb16:
  76   %tmp17 = phi i32 [ %tmp8, %bb10 ], [ 1, %.lr.ph.i ]
  77   %tmp18 = add nsw i32 %tmp8, 1
  78   %tmp19 = icmp slt i32 %tmp18, 4
  79   br i1 %tmp19, label %.lr.ph.i, label %f1.exit.loopexit
  80
  81 f1.exit.loopexit:
  82   %.lcssa = phi i32 [ %tmp17, %bb16 ]
  83   ret i32 %.lcssa
  84 }
  85
  86 ; more than 2 incoming values for tmp17 phi that is used outside loop.
  87 ; CHECK-LABEL: test3(
  88 ; CHECK-LABEL: vector.body:
  89 ; CHECK:          %predphi = select <2 x i1> %{{.*}}, <2 x i32> <i32 1, i32 1>, <2 x i32> zeroinitializer
  90 ; CHECK:          %predphi1 = select <2 x i1> %{{.*}}, <2 x i32> <i32 2, i32 2>, <2 x i32> %predphi
  91
  92 ; CHECK-LABEL: middle.block:
  93 ; CHECK:          [[E1:%[a-zA-Z0-9.]+]] = extractelement <2 x i32> %predphi1, i32 1
  94
  95 ; CHECK-LABEL: f1.exit.loopexit:
  96 ; CHECK:          phi i32 [ %tmp17, %bb16 ], [ [[E1]], %middle.block ]
  97 define i32 @test3(i32 %N)  {
  98 bb:
  99   %b.promoted = load i32, ptr @b, align 4
 100   br label %.lr.ph.i
 101
 102 .lr.ph.i:
 103   %tmp8 = phi i32 [ %tmp18, %bb16 ], [ %b.promoted, %bb ]
 104   %tmp2 = icmp sgt i32 %tmp8, 10
 105   br i1 %tmp2, label %bb16, label %bb10
 106
 107 bb10:
 108   %cmp = icmp sgt i32 %tmp8, %N
 109   br i1  %cmp, label %bb12, label %bb16
 110
 111 bb12:
 112   br label %bb16
 113
 114 bb16:
 115   %tmp17 = phi i32 [ 0, %bb10 ], [ 1, %.lr.ph.i ], [ 2, %bb12 ]
 116   %tmp18 = add nsw i32 %tmp8, 1
 117   %tmp19 = icmp slt i32 %tmp18, 4
 118   br i1 %tmp19, label %.lr.ph.i, label %f1.exit.loopexit
 119
 120 f1.exit.loopexit:
 121   %.lcssa = phi i32 [ %tmp17, %bb16 ]
 122   ret i32 %.lcssa
 123 }
 124
 125 ; more than one incoming value for outside user: %.lcssa
 126 ; CHECK-LABEL: test4(
 127 ; CHECK-LABEL: vector.body:
 128 ; CHECK:          %predphi = select <2 x i1>
 129
 130 ; CHECK-LABEL: middle.block:
 131 ; CHECK:          [[E1:%[a-zA-Z0-9.]+]] = extractelement <2 x i32> %predphi, i32 1
 132
 133 ; CHECK-LABEL: f1.exit.loopexit.loopexit:
 134 ; CHECK:          %tmp17.lcssa = phi i32 [ %tmp17, %bb16 ], [ [[E1]], %middle.block ]
 135 ; CHECK-NEXT:     br label %f1.exit.loopexit
 136
 137 ; CHECK-LABEL: f1.exit.loopexit:
 138 ; CHECK:          %.lcssa = phi i32 [ 2, %bb ], [ %tmp17.lcssa, %f1.exit.loopexit.loopexit ]
 139 define i32 @test4(i32 %N)  {
 140 bb:
 141   %b.promoted = load i32, ptr @b, align 4
 142   %icmp = icmp slt i32 %b.promoted, %N
 143   br i1 %icmp, label %f1.exit.loopexit, label %.lr.ph.i
 144
 145 .lr.ph.i:
 146   %tmp8 = phi i32 [ %tmp18, %bb16 ], [ %b.promoted, %bb ]
 147   %tmp2 = icmp sgt i32 %tmp8, 10
 148   br i1 %tmp2, label %bb16, label %bb10
 149
 150 bb10:
 151   br label %bb16
 152
 153 bb16:
 154   %tmp17 = phi i32 [ 0, %bb10 ], [ 1, %.lr.ph.i ]
 155   %tmp18 = add nsw i32 %tmp8, 1
 156   %tmp19 = icmp slt i32 %tmp18, 4
 157   br i1 %tmp19, label %.lr.ph.i, label %f1.exit.loopexit
 158
 159 f1.exit.loopexit:
 160   %.lcssa = phi i32 [ %tmp17, %bb16 ], [ 2, %bb ]
 161   ret i32 %.lcssa
 162 }
 163
 164 ; non hdr phi that depends on reduction and is used outside the loop.
 165 ; reduction phis are only allowed to have bump or reduction operations as the inside user, so we should
 166 ; not vectorize this.
 167 ; CHECK-LABEL: reduction_sum(
 168 ; CHECK-NOT: <2 x i32>
 169 define i32 @reduction_sum(i32 %n, ptr noalias nocapture %A, ptr noalias nocapture %B) nounwind uwtable readonly noinline ssp {
 170 entry:
 171   %c1 = icmp sgt i32 %n, 0
 172   br i1 %c1, label %header, label %._crit_edge
 173
 174 header:                                           ; preds = %0, %.lr.ph
 175   %indvars.iv = phi i64 [ %indvars.iv.next, %bb16 ], [ 0, %entry ]
 176   %sum.02 = phi i32 [ %c9, %bb16 ], [ 0, %entry ]
 177   %c2 = getelementptr inbounds i32, ptr %A, i64 %indvars.iv
 178   %c3 = load i32, ptr %c2, align 4
 179   %c4 = getelementptr inbounds i32, ptr %B, i64 %indvars.iv
 180   %c5 = load i32, ptr %c4, align 4
 181   %tmp2 = icmp sgt i32 %sum.02, 10
 182   br i1 %tmp2, label %bb16, label %bb10
 183
 184 bb10:
 185   br label %bb16
 186
 187 bb16:
 188   %tmp17 = phi i32 [ %sum.02, %bb10 ], [ 1, %header ]
 189   %c6 = trunc i64 %indvars.iv to i32
 190   %c7 = add i32 %sum.02, %c6
 191   %c8 = add i32 %c7, %c3
 192   %c9 = add i32 %c8, %c5
 193   %indvars.iv.next = add i64 %indvars.iv, 1
 194   %lftr.wideiv = trunc i64 %indvars.iv.next to i32
 195   %exitcond = icmp eq i32 %lftr.wideiv, %n
 196   br i1 %exitcond, label %._crit_edge, label %header
 197
 198 ._crit_edge:                                      ; preds = %.lr.ph, %0
 199   %sum.0.lcssa = phi i32 [ 0, %entry ], [ %c9, %bb16 ]
 200   %nonhdr.lcssa = phi i32 [ 1, %entry], [ %tmp17, %bb16 ]
 201   ret i32 %sum.0.lcssa
 202 }
 203
 204 ; invalid cyclic dependency with header phi iv, which prevents iv from being
 205 ; recognized as induction var.
 206 ; cannot vectorize.
 207 ; CHECK-LABEL: cyclic_dep_with_indvar(
 208 ; CHECK-NOT: <2 x i32>
 209 define i32 @cyclic_dep_with_indvar()  {
 210 bb:
 211   %b.promoted = load i32, ptr @b, align 4
 212   br label %.lr.ph.i
 213
 214 .lr.ph.i:
 215   %iv = phi i32 [ %ivnext, %bb16 ], [ %b.promoted, %bb ]
 216   %tmp2 = icmp sgt i32 %iv, 10
 217   br i1 %tmp2, label %bb16, label %bb10
 218
 219 bb10:
 220   br label %bb16
 221
 222 bb16:
 223   %tmp17 = phi i32 [ 0, %bb10 ], [ %iv, %.lr.ph.i ]
 224   %ivnext = add nsw i32 %tmp17, 1
 225   %tmp19 = icmp slt i32 %ivnext, 4
 226   br i1 %tmp19, label %.lr.ph.i, label %f1.exit.loopexit
 227
 228 f1.exit.loopexit:
 229   %.lcssa = phi i32 [ %tmp17, %bb16 ]
 230   ret i32 %.lcssa
 231 }
 232
 233 ; non-reduction phi 'tmp17' used outside loop has cyclic dependence with %x.05 phi
 234 ; cannot vectorize.
 235 ; CHECK-LABEL: not_valid_reduction(
 236 ; CHECK-NOT: <2 x i32>
 237 define i32 @not_valid_reduction(i32 %n, ptr noalias nocapture %A) nounwind uwtable readonly {
 238 entry:
 239   %cmp4 = icmp sgt i32 %n, 0
 240   br i1 %cmp4, label %for.body, label %for.end
 241
 242 for.body:                                         ; preds = %entry, %for.body
 243   %indvars.iv = phi i64 [ %indvars.iv.next, %latch ], [ 0, %entry ]
 244   %x.05 = phi i32 [ %tmp17, %latch ], [ 0, %entry ]
 245   %arrayidx = getelementptr inbounds i32, ptr %A, i64 %indvars.iv
 246   %tmp0 = load i32, ptr %arrayidx, align 4
 247   %tmp2 = icmp sgt i64 %indvars.iv, 10
 248   %sub = sub nsw i32 %x.05, %tmp0
 249   br i1 %tmp2, label %bb16, label %bb10
 250
 251 bb10:
 252   br label %bb16
 253
 254 bb16:
 255   %tmp17 = phi i32 [ 1, %bb10 ], [ %sub, %for.body ]
 256   br label %latch
 257
 258 latch:
 259   %indvars.iv.next = add i64 %indvars.iv, 1
 260   %lftr.wideiv = trunc i64 %indvars.iv.next to i32
 261   %exitcond = icmp eq i32 %lftr.wideiv, %n
 262   br i1 %exitcond, label %for.end, label %for.body
 263
 264 for.end:                                          ; preds = %for.body, %entry
 265   %x.0.lcssa = phi i32 [ 0, %entry ], [ %tmp17 , %latch ]
 266   ret i32 %x.0.lcssa
 267 }
 268
 269
 270 ; CHECK-LABEL: @outside_user_non_phi(
 271 ; CHECK: %vec.ind = phi <2 x i32>
 272 ; CHECK: [[CMP:%[a-zA-Z0-9.]+]] = icmp sgt <2 x i32> %vec.ind, <i32 10, i32 10>
 273 ; CHECK: %predphi = select <2 x i1> [[CMP]], <2 x i32> <i32 1, i32 1>, <2 x i32> zeroinitializer
 274 ; CHECK: [[TRUNC:%[a-zA-Z0-9.]+]] = trunc <2 x i32> %predphi to <2 x i8>
 275
 276 ; CHECK-LABEL: middle.block:
 277 ; CHECK:          [[E1:%[a-zA-Z0-9.]+]] = extractelement <2 x i8> [[TRUNC]], i32 1
 278
 279 ; CHECK-LABEL: f1.exit.loopexit:
 280 ; CHECK:          %.lcssa = phi i8 [ %tmp17.trunc, %bb16 ], [ [[E1]], %middle.block ]
 281 define i8 @outside_user_non_phi()  {
 282 bb:
 283   %b.promoted = load i32, ptr @b, align 4
 284   br label %.lr.ph.i
 285
 286 .lr.ph.i:
 287   %tmp8 = phi i32 [ %tmp18, %bb16 ], [ %b.promoted, %bb ]
 288   %tmp2 = icmp sgt i32 %tmp8, 10
 289   br i1 %tmp2, label %bb16, label %bb10
 290
 291 bb10:
 292   br label %bb16
 293
 294 bb16:
 295   %tmp17 = phi i32 [ 0, %bb10 ], [ 1, %.lr.ph.i ]
 296   %tmp17.trunc = trunc i32 %tmp17 to i8
 297   %tmp18 = add nsw i32 %tmp8, 1
 298   %tmp19 = icmp slt i32 %tmp18, 4
 299   br i1 %tmp19, label %.lr.ph.i, label %f1.exit.loopexit
 300
 301 f1.exit.loopexit:
 302   %.lcssa = phi i8 [ %tmp17.trunc, %bb16 ]
 303   ret i8 %.lcssa
 304 }
 305
 306 ; CHECK-LABEL: no_vectorize_reduction_with_outside_use(
 307 ; CHECK-NOT: <2 x i32>
 308 define i32 @no_vectorize_reduction_with_outside_use(i32 %n, ptr nocapture %A, ptr nocapture %B) nounwind uwtable readonly {
 309 entry:
 310   %cmp7 = icmp sgt i32 %n, 0
 311   br i1 %cmp7, label %for.body, label %for.end
 312
 313 for.body:                                         ; preds = %entry, %for.body
 314   %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %entry ]
 315   %result.08 = phi i32 [ %or, %for.body ], [ 0, %entry ]
 316   %arrayidx = getelementptr inbounds i32, ptr %A, i64 %indvars.iv
 317   %0 = load i32, ptr %arrayidx, align 4
 318   %arrayidx2 = getelementptr inbounds i32, ptr %B, i64 %indvars.iv
 319   %1 = load i32, ptr %arrayidx2, align 4
 320   %add = add nsw i32 %1, %0
 321   %or = or i32 %add, %result.08
 322   %indvars.iv.next = add i64 %indvars.iv, 1
 323   %lftr.wideiv = trunc i64 %indvars.iv.next to i32
 324   %exitcond = icmp eq i32 %lftr.wideiv, %n
 325   br i1 %exitcond, label %for.end, label %for.body
 326
 327 for.end:                                          ; preds = %for.body, %entry
 328   %result.0.lcssa = phi i32 [ 0, %entry ], [ %1, %for.body ]
 329   ret i32 %result.0.lcssa
 330 }
 331
 332
 333 ; vectorize c[i] = a[i] + b[i] loop where result of c[i] is used outside the
 334 ; loop
 335 ; CHECK-LABEL: sum_arrays_outside_use(
 336 ; CHECK-LABEL: vector.memcheck:
 337 ; CHECK:         br i1 %conflict.rdx, label %scalar.ph, label %vector.ph
 338
 339 ; CHECK-LABEL: vector.body:
 340 ; CHECK:          %wide.load = load <2 x i32>, ptr
 341 ; CHECK:          %wide.load5 = load <2 x i32>, ptr
 342 ; CHECK:          [[ADD:%[a-zA-Z0-9.]+]] = add nsw <2 x i32> %wide.load, %wide.load5
 343 ; CHECK:          store <2 x i32>
 344
 345 ; CHECK-LABEL: middle.block:
 346 ; CHECK:          [[E1:%[a-zA-Z0-9.]+]] = extractelement <2 x i32> [[ADD]], i32 1
 347
 348 ; CHECK-LABEL: f1.exit.loopexit:
 349 ; CHECK:          %.lcssa = phi i32 [ %sum, %.lr.ph.i ], [ [[E1]], %middle.block ]
 350 define i32 @sum_arrays_outside_use(ptr %B, ptr %A, ptr %C, i32 %N)  {
 351 bb:
 352   %b.promoted = load i32, ptr @b, align 4
 353   br label %.lr.ph.i
 354
 355 .lr.ph.i:
 356   %iv = phi i32 [ %ivnext, %.lr.ph.i ], [ %b.promoted, %bb ]
 357   %indvars.iv = sext i32 %iv to i64
 358   %arrayidx2 = getelementptr inbounds i32, ptr %B, i64 %indvars.iv
 359   %Bload = load i32, ptr %arrayidx2, align 4
 360   %arrayidx = getelementptr inbounds i32, ptr %A, i64 %indvars.iv
 361   %Aload = load i32, ptr %arrayidx, align 4
 362   %sum = add nsw i32 %Bload, %Aload
 363   %arrayidx3 = getelementptr inbounds i32, ptr %C, i64 %indvars.iv
 364   store i32 %sum, ptr %arrayidx3, align 4
 365   %ivnext = add nsw i32 %iv, 1
 366   %tmp19 = icmp slt i32 %ivnext, %N
 367   br i1 %tmp19, label %.lr.ph.i, label %f1.exit.loopexit
 368
 369 f1.exit.loopexit:
 370   %.lcssa = phi i32 [ %sum, %.lr.ph.i ]
 371   ret i32 %.lcssa
 372 }
 373
 374 @tab = common global [32 x i8] zeroinitializer, align 1
 375
 376 ; CHECK-LABEL: non_uniform_live_out()
 377 ; CHECK-LABEL:   vector.body:
 378 ; CHECK:           %vec.ind = phi <2 x i32> [ <i32 0, i32 1>, %vector.ph ], [ %vec.ind.next, %vector.body ]
 379 ; CHECK:           [[ADD:%[a-zA-Z0-9.]+]] = add <2 x i32> %vec.ind, <i32 7, i32 7>
 380 ; CHECK:           [[EE:%[a-zA-Z0-9.]+]] = extractelement <2 x i32> [[ADD]], i32 0
 381 ; CHECK:           [[GEP:%[a-zA-Z0-9.]+]] = getelementptr inbounds [32 x i8], ptr @tab, i32 0, i32 [[EE]]
 382 ; CHECK-NEXT:      [[GEP2:%[a-zA-Z0-9.]+]] = getelementptr inbounds i8, ptr [[GEP]], i32 0
 383 ; CHECK-NEXT:      %wide.load = load <2 x i8>, ptr [[GEP2]]
 384 ; CHECK-NEXT:      [[ADD2:%[a-zA-Z0-9.]+]] = add <2 x i8> %wide.load, <i8 1, i8 1>
 385 ; CHECK:           store <2 x i8> [[ADD2]], ptr
 386
 387 ; CHECK-LABEL:  middle.block:
 388 ; CHECK:           [[ADDEE:%[a-zA-Z0-9.]+]] = extractelement <2 x i32> [[ADD]], i32 1
 389
 390 ; CHECK-LABEL:  for.end:
 391 ; CHECK:           %lcssa = phi i32 [ %i.09, %for.body ], [ [[ADDEE]], %middle.block ]
 392 ; CHECK:           %arrayidx.out = getelementptr inbounds [32 x i8], ptr @tab, i32 0, i32 %lcssa
 393 define i32 @non_uniform_live_out() {
 394 entry:
 395  br label %for.body
 396
 397 for.body:                                         ; preds = %for.body, %entry
 398  %i.08 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
 399  %i.09 = add i32 %i.08, 7
 400  %arrayidx = getelementptr inbounds [32 x i8], ptr @tab, i32 0, i32 %i.09
 401  %0 = load i8, ptr %arrayidx, align 1
 402  %bump = add i8 %0, 1
 403  store i8 %bump, ptr %arrayidx, align 1
 404  %inc = add nsw i32 %i.08, 1
 405  %exitcond = icmp eq i32 %i.08, 20000
 406  br i1 %exitcond, label %for.end, label %for.body
 407
 408 for.end:                                          ; preds = %for.body
 409  %lcssa = phi i32 [%i.09, %for.body]
 410  %arrayidx.out = getelementptr inbounds [32 x i8], ptr @tab, i32 0, i32 %lcssa
 411  store i8 42, ptr %arrayidx.out, align 1
 412  ret i32 0
 413 }