llvm/test/Transforms/LoopVectorize/select-min-index.ll

   1 ; RUN: opt -passes=loop-vectorize -force-vector-width=4 -force-vector-interleave=1 -S %s | FileCheck %s
   2 ; RUN: opt -passes=loop-vectorize -force-vector-width=4 -force-vector-interleave=2 -S %s | FileCheck %s
   3 ; RUN: opt -passes=loop-vectorize -force-vector-width=1 -force-vector-interleave=2 -S %s | FileCheck %s
   4
   5 ; Test cases for selecting the index with the minimum value.
   6
   7 define i64 @test_vectorize_select_umin_idx(ptr %src, i64 %n) {
   8 ; CHECK-LABEL: @test_vectorize_select_umin_idx(
   9 ; CHECK-NOT:   vector.body:
  10 ;
  11 entry:
  12   br label %loop
  13
  14 loop:
  15   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
  16   %min.idx = phi i64 [ 0, %entry ], [ %min.idx.next, %loop ]
  17   %min.val = phi i64 [ 0, %entry ], [ %min.val.next, %loop ]
  18   %gep = getelementptr i64, ptr %src, i64 %iv
  19   %l = load i64, ptr %gep
  20   %cmp = icmp ugt i64 %min.val, %l
  21   %min.val.next = tail call i64 @llvm.umin.i64(i64 %min.val, i64 %l)
  22   %min.idx.next = select i1 %cmp, i64 %iv, i64 %min.idx
  23   %iv.next = add nuw nsw i64 %iv, 1
  24   %exitcond.not = icmp eq i64 %iv.next, %n
  25   br i1 %exitcond.not, label %exit, label %loop
  26
  27 exit:
  28   %res = phi i64 [ %min.idx.next, %loop ]
  29   ret i64 %res
  30 }
  31
  32 define i64 @test_vectorize_select_umin_idx_all_exit_inst(ptr %src, ptr %umin, i64 %n) {
  33 ; CHECK-LABEL: @test_vectorize_select_umin_idx_all_exit_inst(
  34 ; CHECK-NOT:   vector.body:
  35 ;
  36 entry:
  37   br label %loop
  38
  39 loop:
  40   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
  41   %min.idx = phi i64 [ 0, %entry ], [ %min.idx.next, %loop ]
  42   %min.val = phi i64 [ 0, %entry ], [ %min.val.next, %loop ]
  43   %gep = getelementptr i64, ptr %src, i64 %iv
  44   %l = load i64, ptr %gep
  45   %cmp = icmp ugt i64 %min.val, %l
  46   %min.val.next = tail call i64 @llvm.umin.i64(i64 %min.val, i64 %l)
  47   %min.idx.next = select i1 %cmp, i64 %iv, i64 %min.idx
  48   %iv.next = add nuw nsw i64 %iv, 1
  49   %exitcond.not = icmp eq i64 %iv.next, %n
  50   br i1 %exitcond.not, label %exit, label %loop
  51
  52 exit:
  53   %res = phi i64 [ %min.idx.next, %loop ]
  54   %res.umin = phi i64 [ %min.val.next, %loop ]
  55   store i64 %res.umin, ptr %umin
  56   ret i64 %res
  57 }
  58
  59 define i64 @test_vectorize_select_umin_idx_min_ops_switched(ptr %src, i64 %n) {
  60 ; CHECK-LABEL: @test_vectorize_select_umin_idx_min_ops_switched(
  61 ; CHECK-NOT:   vector.body:
  62 ;
  63 entry:
  64   br label %loop
  65
  66 loop:
  67   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
  68   %min.idx = phi i64 [ 0, %entry ], [ %min.idx.next, %loop ]
  69   %min.val = phi i64 [ 0, %entry ], [ %min.val.next, %loop ]
  70   %gep = getelementptr i64, ptr %src, i64 %iv
  71   %l = load i64, ptr %gep
  72   %cmp = icmp ugt i64 %min.val, %l
  73   %min.val.next = tail call i64 @llvm.umin.i64(i64 %l, i64 %min.val)
  74   %min.idx.next = select i1 %cmp, i64 %iv, i64 %min.idx
  75   %iv.next = add nuw nsw i64 %iv, 1
  76   %exitcond.not = icmp eq i64 %iv.next, %n
  77   br i1 %exitcond.not, label %exit, label %loop
  78
  79 exit:
  80   %res = phi i64 [ %min.idx.next, %loop ]
  81   ret i64 %res
  82 }
  83
  84 define i64 @test_not_vectorize_select_no_min_reduction(ptr %src, i64 %n) {
  85 ; CHECK-LABEL: @test_not_vectorize_select_no_min_reduction(
  86 ; CHECK-NOT:   vector.body:
  87 ;
  88 entry:
  89   br label %loop
  90
  91 loop:
  92   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
  93   %min.idx = phi i64 [ 0, %entry ], [ %min.idx.next, %loop ]
  94   %min.val = phi i64 [ 0, %entry ], [ %min.val.next, %loop ]
  95   %gep = getelementptr i64, ptr %src, i64 %iv
  96   %l = load i64, ptr %gep
  97   %cmp = icmp ugt i64 %min.val, %l
  98   %min.val.next = add i64 %l, 1
  99   %foo = call i64 @llvm.umin.i64(i64 %min.val, i64 %l)
 100   %min.idx.next = select i1 %cmp, i64 %iv, i64 %min.idx
 101   %iv.next = add nuw nsw i64 %iv, 1
 102   %exitcond.not = icmp eq i64 %iv.next, %n
 103   br i1 %exitcond.not, label %exit, label %loop
 104
 105 exit:
 106   %res = phi i64 [ %min.idx.next, %loop ]
 107   ret i64 %res
 108 }
 109
 110
 111 define i64 @test_not_vectorize_cmp_value(i64 %x, i64 %n) {
 112 ; CHECK-LABEL: @test_not_vectorize_cmp_value(
 113 ; CHECK-NOT:   vector.body:
 114 ;
 115 entry:
 116   br label %loop
 117
 118 loop:
 119   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
 120   %min.idx = phi i64 [ 0, %entry ], [ %min.idx.next, %loop ]
 121   %min.val = phi i64 [ 0, %entry ], [ %min.val.next, %loop ]
 122   %cmp = icmp ugt i64 %min.val, %x
 123   %min.val.next = tail call i64 @llvm.umin.i64(i64 %min.val, i64 0)
 124   %min.idx.next = select i1 %cmp, i64 %iv, i64 %min.idx
 125   %iv.next = add nuw nsw i64 %iv, 1
 126   %exitcond.not = icmp eq i64 %iv.next, %n
 127   br i1 %exitcond.not, label %exit, label %loop
 128
 129 exit:
 130   %res = phi i64 [ %min.idx.next, %loop ]
 131   ret i64 %res
 132 }
 133
 134 define i32 @test_vectorize_select_umin_idx_with_trunc(i64 %n) {
 135 ; CHECK-LABEL: @test_vectorize_select_umin_idx_with_trunc(
 136 ; CHECK-NOT:   vector.body:
 137 ;
 138 entry:
 139   br label %loop
 140
 141 loop:
 142   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
 143   %min.idx = phi i32 [ 0, %entry ], [ %min.idx.next, %loop ]
 144   %min.val = phi i64 [ 0, %entry ], [ %min.val.next, %loop ]
 145   %cmp = icmp ugt i64 %min.val, 0
 146   %min.val.next = tail call i64 @llvm.umin.i64(i64 %min.val, i64 0)
 147   %trunc = trunc i64 %iv to i32
 148   %min.idx.next = select i1 %cmp, i32 %trunc, i32 %min.idx
 149   %iv.next = add nuw nsw i64 %iv, 1
 150   %exitcond.not = icmp eq i64 %iv.next, %n
 151   br i1 %exitcond.not, label %exit, label %loop
 152
 153 exit:
 154   %res = phi i32 [ %min.idx.next, %loop ]
 155   ret i32 %res
 156 }
 157
 158 define ptr @test_with_ptr_index(ptr %start, ptr %end) {
 159 ; CHECK-LABEL: @test_with_ptr_index(
 160 ; CHECK-NOT:   vector.body:
 161 ;
 162 entry:
 163   br label %loop
 164
 165 loop:
 166   %iv = phi ptr [ %start, %entry ], [ %iv.next, %loop ]
 167   %min.idx = phi ptr [ null, %entry ], [ %min.idx.next, %loop ]
 168   %min.val = phi i64 [ 0, %entry ], [ %min.val.next, %loop ]
 169   %cmp7.us = icmp ult i64 0, 0
 170   %min.val.next = tail call i64 @llvm.umin.i64(i64 %min.val, i64 0)
 171   %min.idx.next = select i1 %cmp7.us, ptr %iv, ptr %min.idx
 172   %iv.next = getelementptr i32, ptr %iv, i64 1
 173   %exitcond.not = icmp eq ptr %iv.next, %end
 174   br i1 %exitcond.not, label %exit, label %loop
 175
 176 exit:
 177   %res = phi ptr [ %min.idx.next, %loop ]
 178   ret ptr %res
 179 }
 180
 181 define void @pointer_index(ptr %start) {
 182 ; CHECK-LABEL: @pointer_index(
 183 ; CHECK-NOT:   vector.body:
 184 ;
 185 entry:
 186   br label %loop
 187
 188 loop:
 189   %ptr.iv = phi ptr [ %start, %entry ], [ %ptr.iv.next, %loop ]
 190   %ptr.idx = phi ptr [ %start, %entry ], [ %ptr.select, %loop ]
 191   %cmp.i.i.i.i2531 = icmp ult i16 0, 0
 192   %ptr.select = select i1 %cmp.i.i.i.i2531, ptr %ptr.iv, ptr %ptr.idx
 193   %ptr.iv.next = getelementptr inbounds i16, ptr %ptr.iv, i64 1
 194   %cmp.i.i10.not.i.i.i = icmp eq ptr %ptr.iv.next, null
 195   br i1 %cmp.i.i10.not.i.i.i, label %exit, label %loop
 196
 197 exit:
 198   ret void
 199 }
 200
 201 define ptr @pointer_index_2(ptr %start, ptr %end) {
 202 ; CHECK-LABEL: @pointer_index_2(
 203 ; CHECK-NOT:   vector.body:
 204 ;
 205 entry:
 206   br label %loop
 207
 208 loop:
 209   %min.val  = phi i16 [ 0, %entry ], [ %min.val.next, %loop ]
 210   %ptr.iv = phi ptr [ %start, %entry ], [ %ptr.iv.next, %loop ]
 211   %min.idx = phi ptr [ %start, %entry ], [ %min.idx.next, %loop ]
 212   %cmp.i.i.i.i = icmp ult i16 0, %min.val
 213   %min.val.next = call i16 @llvm.umin.i16(i16 0, i16 %min.val)
 214   %min.idx.next = select i1 %cmp.i.i.i.i, ptr %ptr.iv, ptr %min.idx
 215   %ptr.iv.next = getelementptr inbounds i16, ptr %ptr.iv, i64 1
 216   %exit.cond = icmp eq ptr %ptr.iv.next, %end
 217   br i1 %exit.cond, label %exit, label %loop
 218
 219 exit:
 220   %res = phi ptr [ %min.idx.next, %loop ]
 221   ret ptr %res
 222 }
 223
 224 define i64 @test_no_vectorize_select_iv_decrement(ptr %src) {
 225 ; CHECK-LABEL: @test_no_vectorize_select_iv_decrement(
 226 ; CHECK-NOT:   vector.body:
 227 ;
 228 entry:
 229   br label %loop
 230
 231 loop:
 232   %iv = phi i64 [ 1000, %entry ], [ %iv.next, %loop ]
 233   %min.idx = phi i64 [ 0, %entry ], [ %min.idx.next, %loop ]
 234   %min.val = phi i64 [ 0, %entry ], [ %min.val.next, %loop ]
 235   %gep = getelementptr i64, ptr %src, i64 %iv
 236   %l = load i64, ptr %gep
 237   %cmp = icmp ugt i64 %min.val, %l
 238   %min.val.next = tail call i64 @llvm.umin.i64(i64 %min.val, i64 %l)
 239   %min.idx.next = select i1 %cmp, i64 %iv, i64 %min.idx
 240   %iv.next = add nuw nsw i64 %iv, -1
 241   %exitcond.not = icmp eq i64 %iv.next, 0
 242   br i1 %exitcond.not, label %exit, label %loop
 243
 244 exit:
 245   %res = phi i64 [ %min.idx.next, %loop ]
 246   ret i64 %res
 247 }
 248
 249 define i64 @test_no_vectorize_select_iv_sub(ptr %src) {
 250 ; CHECK-LABEL: @test_no_vectorize_select_iv_sub(
 251 ; CHECK-NOT:   vector.body:
 252 ;
 253 entry:
 254   br label %loop
 255
 256 loop:
 257   %iv = phi i64 [ 1000, %entry ], [ %iv.next, %loop ]
 258   %min.idx = phi i64 [ 0, %entry ], [ %min.idx.next, %loop ]
 259   %min.val = phi i64 [ 0, %entry ], [ %min.val.next, %loop ]
 260   %gep = getelementptr i64, ptr %src, i64 %iv
 261   %l = load i64, ptr %gep
 262   %cmp = icmp ugt i64 %min.val, %l
 263   %min.val.next = tail call i64 @llvm.umin.i64(i64 %min.val, i64 %l)
 264   %min.idx.next = select i1 %cmp, i64 %iv, i64 %min.idx
 265   %iv.next = sub i64 %iv, 1
 266   %exitcond.not = icmp eq i64 %iv.next, 0
 267   br i1 %exitcond.not, label %exit, label %loop
 268
 269 exit:
 270   %res = phi i64 [ %min.idx.next, %loop ]
 271   ret i64 %res
 272 }
 273
 274 define i64 @test_no_vectorize_select_iv_mul(ptr %src) {
 275 ; CHECK-LABEL: @test_no_vectorize_select_iv_mul(
 276 ; CHECK-NOT:   vector.body:
 277 ;
 278 entry:
 279   br label %loop
 280
 281 loop:
 282   %iv = phi i64 [ 1, %entry ], [ %iv.next, %loop ]
 283   %min.idx = phi i64 [ 0, %entry ], [ %min.idx.next, %loop ]
 284   %min.val = phi i64 [ 0, %entry ], [ %min.val.next, %loop ]
 285   %gep = getelementptr i64, ptr %src, i64 %iv
 286   %l = load i64, ptr %gep
 287   %cmp = icmp ugt i64 %min.val, %l
 288   %min.val.next = tail call i64 @llvm.umin.i64(i64 %min.val, i64 %l)
 289   %min.idx.next = select i1 %cmp, i64 %iv, i64 %min.idx
 290   %iv.next = mul i64 %iv, 2
 291   %exitcond.not = icmp eq i64 %iv.next, 128
 292   br i1 %exitcond.not, label %exit, label %loop
 293
 294 exit:
 295   %res = phi i64 [ %min.idx.next, %loop ]
 296   ret i64 %res
 297 }
 298
 299 declare i64 @llvm.umin.i64(i64, i64)
 300 declare i16 @llvm.umin.i16(i16, i16)