llvm/test/Transforms/LoopVectorize/pr30654-phiscev-sext-trunc.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt -S -passes=loop-vectorize -force-vector-width=4 -force-vector-interleave=1 < %s 2>&1 | FileCheck %s
   3
   4 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
   5
   6 ; Check that the vectorizer identifies the %p.09 phi,
   7 ; as an induction variable, despite the potential overflow
   8 ; due to the truncation from 32bit to 8bit.
   9 ; SCEV will detect the pattern "sext(trunc(%p.09)) + %step"
  10 ; and generate the required runtime checks under which
  11 ; we can assume no overflow. We check here that we generate
  12 ; exactly two runtime checks:
  13 ; 1) an overflow check:
  14 ;    {0,+,(trunc i32 %step to i8)}<%for.body> Added Flags: <nssw>
  15 ; 2) an equality check verifying that the step of the induction
  16 ;    is equal to sext(trunc(step)):
  17 ;    Equal predicate: %step == (sext i8 (trunc i32 %step to i8) to i32)
  18 ;
  19 ; See also pr30654.
  20 ;
  21 ; int a[N];
  22 ; void doit1(int n, int step) {
  23 ;   int i;
  24 ;   char p = 0;
  25 ;   for (i = 0; i < n; i++) {
  26 ;      a[i] = p;
  27 ;      p = p + step;
  28 ;   }
  29 ; }
  30 ;
  31
  32 @a = common local_unnamed_addr global [250 x i32] zeroinitializer, align 16
  33
  34 ; Function Attrs: norecurse nounwind uwtable
  35 define void @doit1(i32 %n, i32 %step) local_unnamed_addr {
  36 ; CHECK-LABEL: @doit1(
  37 ; CHECK-NEXT:  entry:
  38 ; CHECK-NEXT:    [[CMP7:%.*]] = icmp sgt i32 [[N:%.*]], 0
  39 ; CHECK-NEXT:    br i1 [[CMP7]], label [[FOR_BODY_PREHEADER:%.*]], label [[FOR_END:%.*]]
  40 ; CHECK:       for.body.preheader:
  41 ; CHECK-NEXT:    [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[N]] to i64
  42 ; CHECK-NEXT:    [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[WIDE_TRIP_COUNT]], 4
  43 ; CHECK-NEXT:    br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_SCEVCHECK:%.*]]
  44 ; CHECK:       vector.scevcheck:
  45 ; CHECK-NEXT:    [[TMP0:%.*]] = add nsw i64 [[WIDE_TRIP_COUNT]], -1
  46 ; CHECK-NEXT:    [[TMP1:%.*]] = trunc i32 [[STEP:%.*]] to i8
  47 ; CHECK-NEXT:    [[TMP2:%.*]] = sub i8 0, [[TMP1]]
  48 ; CHECK-NEXT:    [[TMP3:%.*]] = icmp slt i8 [[TMP1]], 0
  49 ; CHECK-NEXT:    [[TMP4:%.*]] = select i1 [[TMP3]], i8 [[TMP2]], i8 [[TMP1]]
  50 ; CHECK-NEXT:    [[TMP5:%.*]] = trunc i64 [[TMP0]] to i8
  51 ; CHECK-NEXT:    [[MUL:%.*]] = call { i8, i1 } @llvm.umul.with.overflow.i8(i8 [[TMP4]], i8 [[TMP5]])
  52 ; CHECK-NEXT:    [[MUL_RESULT:%.*]] = extractvalue { i8, i1 } [[MUL]], 0
  53 ; CHECK-NEXT:    [[MUL_OVERFLOW:%.*]] = extractvalue { i8, i1 } [[MUL]], 1
  54 ; CHECK-NEXT:    [[TMP6:%.*]] = sub i8 0, [[MUL_RESULT]]
  55 ; CHECK-NEXT:    [[TMP7:%.*]] = icmp slt i8 [[MUL_RESULT]], 0
  56 ; CHECK-NEXT:    [[TMP8:%.*]] = icmp sgt i8 [[TMP6]], 0
  57 ; CHECK-NEXT:    [[TMP9:%.*]] = select i1 [[TMP3]], i1 [[TMP8]], i1 [[TMP7]]
  58 ; CHECK-NEXT:    [[TMP10:%.*]] = or i1 [[TMP9]], [[MUL_OVERFLOW]]
  59 ; CHECK-NEXT:    [[TMP11:%.*]] = icmp ugt i64 [[TMP0]], 255
  60 ; CHECK-NEXT:    [[TMP12:%.*]] = icmp ne i8 [[TMP1]], 0
  61 ; CHECK-NEXT:    [[TMP13:%.*]] = and i1 [[TMP11]], [[TMP12]]
  62 ; CHECK-NEXT:    [[TMP14:%.*]] = or i1 [[TMP10]], [[TMP13]]
  63 ; CHECK-NEXT:    [[TMP15:%.*]] = sext i8 [[TMP1]] to i32
  64 ; CHECK-NEXT:    [[IDENT_CHECK:%.*]] = icmp ne i32 [[STEP]], [[TMP15]]
  65 ; CHECK-NEXT:    [[TMP16:%.*]] = or i1 [[TMP14]], [[IDENT_CHECK]]
  66 ; CHECK-NEXT:    br i1 [[TMP16]], label [[SCALAR_PH]], label [[VECTOR_PH:%.*]]
  67 ; CHECK:       vector.ph:
  68 ; CHECK-NEXT:    [[N_MOD_VF:%.*]] = urem i64 [[WIDE_TRIP_COUNT]], 4
  69 ; CHECK-NEXT:    [[N_VEC:%.*]] = sub i64 [[WIDE_TRIP_COUNT]], [[N_MOD_VF]]
  70 ; CHECK-NEXT:    [[DOTCAST:%.*]] = trunc i64 [[N_VEC]] to i32
  71 ; CHECK-NEXT:    [[IND_END:%.*]] = mul i32 [[DOTCAST]], [[STEP]]
  72 ; CHECK-NEXT:    [[DOTSPLATINSERT:%.*]] = insertelement <4 x i32> poison, i32 [[STEP]], i64 0
  73 ; CHECK-NEXT:    [[DOTSPLAT:%.*]] = shufflevector <4 x i32> [[DOTSPLATINSERT]], <4 x i32> poison, <4 x i32> zeroinitializer
  74 ; CHECK-NEXT:    [[TMP17:%.*]] = mul <4 x i32> <i32 0, i32 1, i32 2, i32 3>, [[DOTSPLAT]]
  75 ; CHECK-NEXT:    [[INDUCTION:%.*]] = add <4 x i32> zeroinitializer, [[TMP17]]
  76 ; CHECK-NEXT:    [[TMP18:%.*]] = mul i32 [[STEP]], 4
  77 ; CHECK-NEXT:    [[DOTSPLATINSERT2:%.*]] = insertelement <4 x i32> poison, i32 [[TMP18]], i64 0
  78 ; CHECK-NEXT:    [[DOTSPLAT3:%.*]] = shufflevector <4 x i32> [[DOTSPLATINSERT2]], <4 x i32> poison, <4 x i32> zeroinitializer
  79 ; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]
  80 ; CHECK:       vector.body:
  81 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]
  82 ; CHECK-NEXT:    [[VEC_IND:%.*]] = phi <4 x i32> [ [[INDUCTION]], [[VECTOR_PH]] ], [ [[VEC_IND_NEXT:%.*]], [[VECTOR_BODY]] ]
  83 ; CHECK-NEXT:    [[TMP19:%.*]] = add i64 [[INDEX]], 0
  84 ; CHECK-NEXT:    [[TMP20:%.*]] = getelementptr inbounds [250 x i32], ptr @a, i64 0, i64 [[TMP19]]
  85 ; CHECK-NEXT:    [[TMP21:%.*]] = getelementptr inbounds i32, ptr [[TMP20]], i32 0
  86 ; CHECK-NEXT:    store <4 x i32> [[VEC_IND]], ptr [[TMP21]], align 4
  87 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
  88 ; CHECK-NEXT:    [[VEC_IND_NEXT]] = add <4 x i32> [[VEC_IND]], [[DOTSPLAT3]]
  89 ; CHECK-NEXT:    [[TMP22:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
  90 ; CHECK-NEXT:    br i1 [[TMP22]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP0:![0-9]+]]
  91 ; CHECK:       middle.block:
  92 ; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i64 [[WIDE_TRIP_COUNT]], [[N_VEC]]
  93 ; CHECK-NEXT:    br i1 [[CMP_N]], label [[FOR_END_LOOPEXIT:%.*]], label [[SCALAR_PH]]
  94 ; CHECK:       scalar.ph:
  95 ; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], [[MIDDLE_BLOCK]] ], [ 0, [[VECTOR_SCEVCHECK]] ], [ 0, [[FOR_BODY_PREHEADER]] ]
  96 ; CHECK-NEXT:    [[BC_RESUME_VAL1:%.*]] = phi i32 [ [[IND_END]], [[MIDDLE_BLOCK]] ], [ 0, [[VECTOR_SCEVCHECK]] ], [ 0, [[FOR_BODY_PREHEADER]] ]
  97 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
  98 ; CHECK:       for.body:
  99 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY]] ], [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ]
 100 ; CHECK-NEXT:    [[P_09:%.*]] = phi i32 [ [[ADD:%.*]], [[FOR_BODY]] ], [ [[BC_RESUME_VAL1]], [[SCALAR_PH]] ]
 101 ; CHECK-NEXT:    [[SEXT:%.*]] = shl i32 [[P_09]], 24
 102 ; CHECK-NEXT:    [[CONV:%.*]] = ashr exact i32 [[SEXT]], 24
 103 ; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds [250 x i32], ptr @a, i64 0, i64 [[INDVARS_IV]]
 104 ; CHECK-NEXT:    store i32 [[CONV]], ptr [[ARRAYIDX]], align 4
 105 ; CHECK-NEXT:    [[ADD]] = add nsw i32 [[CONV]], [[STEP]]
 106 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
 107 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], [[WIDE_TRIP_COUNT]]
 108 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END_LOOPEXIT]], label [[FOR_BODY]], !llvm.loop [[LOOP3:![0-9]+]]
 109 ; CHECK:       for.end.loopexit:
 110 ; CHECK-NEXT:    br label [[FOR_END]]
 111 ; CHECK:       for.end:
 112 ; CHECK-NEXT:    ret void
 113 ;
 114 entry:
 115   %cmp7 = icmp sgt i32 %n, 0
 116   br i1 %cmp7, label %for.body.preheader, label %for.end
 117
 118 for.body.preheader:
 119   %wide.trip.count = zext i32 %n to i64
 120   br label %for.body
 121
 122 for.body:
 123   %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %for.body.preheader ]
 124   %p.09 = phi i32 [ %add, %for.body ], [ 0, %for.body.preheader ]
 125   %sext = shl i32 %p.09, 24
 126   %conv = ashr exact i32 %sext, 24
 127   %arrayidx = getelementptr inbounds [250 x i32], ptr @a, i64 0, i64 %indvars.iv
 128   store i32 %conv, ptr %arrayidx, align 4
 129   %add = add nsw i32 %conv, %step
 130   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
 131   %exitcond = icmp eq i64 %indvars.iv.next, %wide.trip.count
 132   br i1 %exitcond, label %for.end.loopexit, label %for.body
 133
 134 for.end.loopexit:
 135   br label %for.end
 136
 137 for.end:
 138   ret void
 139 }
 140
 141 ; Same as above, but for checking the SCEV "zext(trunc(%p.09)) + %step".
 142 ; Here we expect the following two predicates to be added for runtime checking:
 143 ; 1) {0,+,(trunc i32 %step to i8)}<%for.body> Added Flags: <nusw>
 144 ; 2) Equal predicate: %step == (sext i8 (trunc i32 %step to i8) to i32)
 145 ;
 146 ; int a[N];
 147 ; void doit2(int n, int step) {
 148 ;   int i;
 149 ;   unsigned char p = 0;
 150 ;   for (i = 0; i < n; i++) {
 151 ;      a[i] = p;
 152 ;      p = p + step;
 153 ;   }
 154 ; }
 155 ;
 156
 157
 158 ; Function Attrs: norecurse nounwind uwtable
 159 define void @doit2(i32 %n, i32 %step) local_unnamed_addr  {
 160 ; CHECK-LABEL: @doit2(
 161 ; CHECK-NEXT:  entry:
 162 ; CHECK-NEXT:    [[CMP7:%.*]] = icmp sgt i32 [[N:%.*]], 0
 163 ; CHECK-NEXT:    br i1 [[CMP7]], label [[FOR_BODY_PREHEADER:%.*]], label [[FOR_END:%.*]]
 164 ; CHECK:       for.body.preheader:
 165 ; CHECK-NEXT:    [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[N]] to i64
 166 ; CHECK-NEXT:    [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[WIDE_TRIP_COUNT]], 4
 167 ; CHECK-NEXT:    br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_SCEVCHECK:%.*]]
 168 ; CHECK:       vector.scevcheck:
 169 ; CHECK-NEXT:    [[TMP0:%.*]] = add nsw i64 [[WIDE_TRIP_COUNT]], -1
 170 ; CHECK-NEXT:    [[TMP1:%.*]] = trunc i32 [[STEP:%.*]] to i8
 171 ; CHECK-NEXT:    [[TMP2:%.*]] = sub i8 0, [[TMP1]]
 172 ; CHECK-NEXT:    [[TMP3:%.*]] = icmp slt i8 [[TMP1]], 0
 173 ; CHECK-NEXT:    [[TMP4:%.*]] = select i1 [[TMP3]], i8 [[TMP2]], i8 [[TMP1]]
 174 ; CHECK-NEXT:    [[TMP5:%.*]] = trunc i64 [[TMP0]] to i8
 175 ; CHECK-NEXT:    [[MUL:%.*]] = call { i8, i1 } @llvm.umul.with.overflow.i8(i8 [[TMP4]], i8 [[TMP5]])
 176 ; CHECK-NEXT:    [[MUL_RESULT:%.*]] = extractvalue { i8, i1 } [[MUL]], 0
 177 ; CHECK-NEXT:    [[MUL_OVERFLOW:%.*]] = extractvalue { i8, i1 } [[MUL]], 1
 178 ; CHECK-NEXT:    [[TMP6:%.*]] = sub i8 0, [[MUL_RESULT]]
 179 ; CHECK-NEXT:    [[TMP7:%.*]] = icmp ugt i8 [[TMP6]], 0
 180 ; CHECK-NEXT:    [[TMP8:%.*]] = select i1 [[TMP3]], i1 [[TMP7]], i1 false
 181 ; CHECK-NEXT:    [[TMP9:%.*]] = or i1 [[TMP8]], [[MUL_OVERFLOW]]
 182 ; CHECK-NEXT:    [[TMP10:%.*]] = icmp ugt i64 [[TMP0]], 255
 183 ; CHECK-NEXT:    [[TMP11:%.*]] = icmp ne i8 [[TMP1]], 0
 184 ; CHECK-NEXT:    [[TMP12:%.*]] = and i1 [[TMP10]], [[TMP11]]
 185 ; CHECK-NEXT:    [[TMP13:%.*]] = or i1 [[TMP9]], [[TMP12]]
 186 ; CHECK-NEXT:    [[TMP14:%.*]] = sext i8 [[TMP1]] to i32
 187 ; CHECK-NEXT:    [[IDENT_CHECK:%.*]] = icmp ne i32 [[STEP]], [[TMP14]]
 188 ; CHECK-NEXT:    [[TMP15:%.*]] = or i1 [[TMP13]], [[IDENT_CHECK]]
 189 ; CHECK-NEXT:    br i1 [[TMP15]], label [[SCALAR_PH]], label [[VECTOR_PH:%.*]]
 190 ; CHECK:       vector.ph:
 191 ; CHECK-NEXT:    [[N_MOD_VF:%.*]] = urem i64 [[WIDE_TRIP_COUNT]], 4
 192 ; CHECK-NEXT:    [[N_VEC:%.*]] = sub i64 [[WIDE_TRIP_COUNT]], [[N_MOD_VF]]
 193 ; CHECK-NEXT:    [[DOTCAST:%.*]] = trunc i64 [[N_VEC]] to i32
 194 ; CHECK-NEXT:    [[IND_END:%.*]] = mul i32 [[DOTCAST]], [[STEP]]
 195 ; CHECK-NEXT:    [[DOTSPLATINSERT:%.*]] = insertelement <4 x i32> poison, i32 [[STEP]], i64 0
 196 ; CHECK-NEXT:    [[DOTSPLAT:%.*]] = shufflevector <4 x i32> [[DOTSPLATINSERT]], <4 x i32> poison, <4 x i32> zeroinitializer
 197 ; CHECK-NEXT:    [[TMP16:%.*]] = mul <4 x i32> <i32 0, i32 1, i32 2, i32 3>, [[DOTSPLAT]]
 198 ; CHECK-NEXT:    [[INDUCTION:%.*]] = add <4 x i32> zeroinitializer, [[TMP16]]
 199 ; CHECK-NEXT:    [[TMP17:%.*]] = mul i32 [[STEP]], 4
 200 ; CHECK-NEXT:    [[DOTSPLATINSERT2:%.*]] = insertelement <4 x i32> poison, i32 [[TMP17]], i64 0
 201 ; CHECK-NEXT:    [[DOTSPLAT3:%.*]] = shufflevector <4 x i32> [[DOTSPLATINSERT2]], <4 x i32> poison, <4 x i32> zeroinitializer
 202 ; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]
 203 ; CHECK:       vector.body:
 204 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]
 205 ; CHECK-NEXT:    [[VEC_IND:%.*]] = phi <4 x i32> [ [[INDUCTION]], [[VECTOR_PH]] ], [ [[VEC_IND_NEXT:%.*]], [[VECTOR_BODY]] ]
 206 ; CHECK-NEXT:    [[TMP18:%.*]] = add i64 [[INDEX]], 0
 207 ; CHECK-NEXT:    [[TMP19:%.*]] = getelementptr inbounds [250 x i32], ptr @a, i64 0, i64 [[TMP18]]
 208 ; CHECK-NEXT:    [[TMP20:%.*]] = getelementptr inbounds i32, ptr [[TMP19]], i32 0
 209 ; CHECK-NEXT:    store <4 x i32> [[VEC_IND]], ptr [[TMP20]], align 4
 210 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
 211 ; CHECK-NEXT:    [[VEC_IND_NEXT]] = add <4 x i32> [[VEC_IND]], [[DOTSPLAT3]]
 212 ; CHECK-NEXT:    [[TMP21:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
 213 ; CHECK-NEXT:    br i1 [[TMP21]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP4:![0-9]+]]
 214 ; CHECK:       middle.block:
 215 ; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i64 [[WIDE_TRIP_COUNT]], [[N_VEC]]
 216 ; CHECK-NEXT:    br i1 [[CMP_N]], label [[FOR_END_LOOPEXIT:%.*]], label [[SCALAR_PH]]
 217 ; CHECK:       scalar.ph:
 218 ; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], [[MIDDLE_BLOCK]] ], [ 0, [[VECTOR_SCEVCHECK]] ], [ 0, [[FOR_BODY_PREHEADER]] ]
 219 ; CHECK-NEXT:    [[BC_RESUME_VAL1:%.*]] = phi i32 [ [[IND_END]], [[MIDDLE_BLOCK]] ], [ 0, [[VECTOR_SCEVCHECK]] ], [ 0, [[FOR_BODY_PREHEADER]] ]
 220 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 221 ; CHECK:       for.body:
 222 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY]] ], [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ]
 223 ; CHECK-NEXT:    [[P_09:%.*]] = phi i32 [ [[ADD:%.*]], [[FOR_BODY]] ], [ [[BC_RESUME_VAL1]], [[SCALAR_PH]] ]
 224 ; CHECK-NEXT:    [[CONV:%.*]] = and i32 [[P_09]], 255
 225 ; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds [250 x i32], ptr @a, i64 0, i64 [[INDVARS_IV]]
 226 ; CHECK-NEXT:    store i32 [[CONV]], ptr [[ARRAYIDX]], align 4
 227 ; CHECK-NEXT:    [[ADD]] = add nsw i32 [[CONV]], [[STEP]]
 228 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
 229 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], [[WIDE_TRIP_COUNT]]
 230 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END_LOOPEXIT]], label [[FOR_BODY]], !llvm.loop [[LOOP5:![0-9]+]]
 231 ; CHECK:       for.end.loopexit:
 232 ; CHECK-NEXT:    br label [[FOR_END]]
 233 ; CHECK:       for.end:
 234 ; CHECK-NEXT:    ret void
 235 ;
 236 entry:
 237   %cmp7 = icmp sgt i32 %n, 0
 238   br i1 %cmp7, label %for.body.preheader, label %for.end
 239
 240 for.body.preheader:
 241   %wide.trip.count = zext i32 %n to i64
 242   br label %for.body
 243
 244 for.body:
 245   %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %for.body.preheader ]
 246   %p.09 = phi i32 [ %add, %for.body ], [ 0, %for.body.preheader ]
 247   %conv = and i32 %p.09, 255
 248   %arrayidx = getelementptr inbounds [250 x i32], ptr @a, i64 0, i64 %indvars.iv
 249   store i32 %conv, ptr %arrayidx, align 4
 250   %add = add nsw i32 %conv, %step
 251   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
 252   %exitcond = icmp eq i64 %indvars.iv.next, %wide.trip.count
 253   br i1 %exitcond, label %for.end.loopexit, label %for.body
 254
 255 for.end.loopexit:
 256   br label %for.end
 257
 258 for.end:
 259   ret void
 260 }
 261
 262 ; Here we check that the same phi scev analysis would fail
 263 ; to create the runtime checks because the step is not invariant.
 264 ; As a result vectorization will fail.
 265 ;
 266 ; int a[N];
 267 ; void doit3(int n, int step) {
 268 ;   int i;
 269 ;   char p = 0;
 270 ;   for (i = 0; i < n; i++) {
 271 ;      a[i] = p;
 272 ;      p = p + step;
 273 ;      step += 2;
 274 ;   }
 275 ; }
 276 ;
 277
 278
 279 ; Function Attrs: norecurse nounwind uwtable
 280 define void @doit3(i32 %n, i32 %step) local_unnamed_addr {
 281 ; CHECK-LABEL: @doit3(
 282 ; CHECK-NEXT:  entry:
 283 ; CHECK-NEXT:    [[CMP9:%.*]] = icmp sgt i32 [[N:%.*]], 0
 284 ; CHECK-NEXT:    br i1 [[CMP9]], label [[FOR_BODY_PREHEADER:%.*]], label [[FOR_END:%.*]]
 285 ; CHECK:       for.body.preheader:
 286 ; CHECK-NEXT:    [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[N]] to i64
 287 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 288 ; CHECK:       for.body:
 289 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY]] ], [ 0, [[FOR_BODY_PREHEADER]] ]
 290 ; CHECK-NEXT:    [[P_012:%.*]] = phi i32 [ [[ADD:%.*]], [[FOR_BODY]] ], [ 0, [[FOR_BODY_PREHEADER]] ]
 291 ; CHECK-NEXT:    [[STEP_ADDR_010:%.*]] = phi i32 [ [[ADD3:%.*]], [[FOR_BODY]] ], [ [[STEP:%.*]], [[FOR_BODY_PREHEADER]] ]
 292 ; CHECK-NEXT:    [[SEXT:%.*]] = shl i32 [[P_012]], 24
 293 ; CHECK-NEXT:    [[CONV:%.*]] = ashr exact i32 [[SEXT]], 24
 294 ; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds [250 x i32], ptr @a, i64 0, i64 [[INDVARS_IV]]
 295 ; CHECK-NEXT:    store i32 [[CONV]], ptr [[ARRAYIDX]], align 4
 296 ; CHECK-NEXT:    [[ADD]] = add nsw i32 [[CONV]], [[STEP_ADDR_010]]
 297 ; CHECK-NEXT:    [[ADD3]] = add nsw i32 [[STEP_ADDR_010]], 2
 298 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
 299 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], [[WIDE_TRIP_COUNT]]
 300 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END_LOOPEXIT:%.*]], label [[FOR_BODY]]
 301 ; CHECK:       for.end.loopexit:
 302 ; CHECK-NEXT:    br label [[FOR_END]]
 303 ; CHECK:       for.end:
 304 ; CHECK-NEXT:    ret void
 305 ;
 306 entry:
 307   %cmp9 = icmp sgt i32 %n, 0
 308   br i1 %cmp9, label %for.body.preheader, label %for.end
 309
 310 for.body.preheader:
 311   %wide.trip.count = zext i32 %n to i64
 312   br label %for.body
 313
 314 for.body:
 315   %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %for.body.preheader ]
 316   %p.012 = phi i32 [ %add, %for.body ], [ 0, %for.body.preheader ]
 317   %step.addr.010 = phi i32 [ %add3, %for.body ], [ %step, %for.body.preheader ]
 318   %sext = shl i32 %p.012, 24
 319   %conv = ashr exact i32 %sext, 24
 320   %arrayidx = getelementptr inbounds [250 x i32], ptr @a, i64 0, i64 %indvars.iv
 321   store i32 %conv, ptr %arrayidx, align 4
 322   %add = add nsw i32 %conv, %step.addr.010
 323   %add3 = add nsw i32 %step.addr.010, 2
 324   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
 325   %exitcond = icmp eq i64 %indvars.iv.next, %wide.trip.count
 326   br i1 %exitcond, label %for.end.loopexit, label %for.body
 327
 328 for.end.loopexit:
 329   br label %for.end
 330
 331 for.end:
 332   ret void
 333 }
 334
 335
 336 ; Lastly, we also check the case where we can tell at compile time that
 337 ; the step of the induction is equal to sext(trunc(step)), in which case
 338 ; we don't have to check this equality at runtime (we only need the
 339 ; runtime overflow check). Therefore only the following overflow predicate
 340 ; will be added for runtime checking:
 341 ; {0,+,%cstep}<%for.body> Added Flags: <nssw>
 342 ;
 343 ; a[N];
 344 ; void doit4(int n, char cstep) {
 345 ;   int i;
 346 ;   char p = 0;
 347 ;   int istep = cstep;
 348 ;  for (i = 0; i < n; i++) {
 349 ;      a[i] = p;
 350 ;      p = p + istep;
 351 ;   }
 352 ; }
 353
 354
 355 ; Function Attrs: norecurse nounwind uwtable
 356 define void @doit4(i32 %n, i8 signext %cstep) local_unnamed_addr {
 357 ; CHECK-LABEL: @doit4(
 358 ; CHECK-NEXT:  entry:
 359 ; CHECK-NEXT:    [[CONV:%.*]] = sext i8 [[CSTEP:%.*]] to i32
 360 ; CHECK-NEXT:    [[CMP10:%.*]] = icmp sgt i32 [[N:%.*]], 0
 361 ; CHECK-NEXT:    br i1 [[CMP10]], label [[FOR_BODY_PREHEADER:%.*]], label [[FOR_END:%.*]]
 362 ; CHECK:       for.body.preheader:
 363 ; CHECK-NEXT:    [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[N]] to i64
 364 ; CHECK-NEXT:    [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[WIDE_TRIP_COUNT]], 4
 365 ; CHECK-NEXT:    br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_SCEVCHECK:%.*]]
 366 ; CHECK:       vector.scevcheck:
 367 ; CHECK-NEXT:    [[TMP0:%.*]] = add nsw i64 [[WIDE_TRIP_COUNT]], -1
 368 ; CHECK-NEXT:    [[TMP1:%.*]] = sub i8 0, [[CSTEP]]
 369 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp slt i8 [[CSTEP]], 0
 370 ; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[TMP2]], i8 [[TMP1]], i8 [[CSTEP]]
 371 ; CHECK-NEXT:    [[TMP4:%.*]] = trunc i64 [[TMP0]] to i8
 372 ; CHECK-NEXT:    [[MUL:%.*]] = call { i8, i1 } @llvm.umul.with.overflow.i8(i8 [[TMP3]], i8 [[TMP4]])
 373 ; CHECK-NEXT:    [[MUL_RESULT:%.*]] = extractvalue { i8, i1 } [[MUL]], 0
 374 ; CHECK-NEXT:    [[MUL_OVERFLOW:%.*]] = extractvalue { i8, i1 } [[MUL]], 1
 375 ; CHECK-NEXT:    [[TMP5:%.*]] = sub i8 0, [[MUL_RESULT]]
 376 ; CHECK-NEXT:    [[TMP6:%.*]] = icmp slt i8 [[MUL_RESULT]], 0
 377 ; CHECK-NEXT:    [[TMP7:%.*]] = icmp sgt i8 [[TMP5]], 0
 378 ; CHECK-NEXT:    [[TMP8:%.*]] = select i1 [[TMP2]], i1 [[TMP7]], i1 [[TMP6]]
 379 ; CHECK-NEXT:    [[TMP9:%.*]] = or i1 [[TMP8]], [[MUL_OVERFLOW]]
 380 ; CHECK-NEXT:    [[TMP10:%.*]] = icmp ugt i64 [[TMP0]], 255
 381 ; CHECK-NEXT:    [[TMP11:%.*]] = icmp ne i8 [[CSTEP]], 0
 382 ; CHECK-NEXT:    [[TMP12:%.*]] = and i1 [[TMP10]], [[TMP11]]
 383 ; CHECK-NEXT:    [[TMP13:%.*]] = or i1 [[TMP9]], [[TMP12]]
 384 ; CHECK-NEXT:    br i1 [[TMP13]], label [[SCALAR_PH]], label [[VECTOR_PH:%.*]]
 385 ; CHECK:       vector.ph:
 386 ; CHECK-NEXT:    [[N_MOD_VF:%.*]] = urem i64 [[WIDE_TRIP_COUNT]], 4
 387 ; CHECK-NEXT:    [[N_VEC:%.*]] = sub i64 [[WIDE_TRIP_COUNT]], [[N_MOD_VF]]
 388 ; CHECK-NEXT:    [[DOTCAST:%.*]] = trunc i64 [[N_VEC]] to i32
 389 ; CHECK-NEXT:    [[IND_END:%.*]] = mul i32 [[DOTCAST]], [[CONV]]
 390 ; CHECK-NEXT:    [[DOTSPLATINSERT:%.*]] = insertelement <4 x i32> poison, i32 [[CONV]], i64 0
 391 ; CHECK-NEXT:    [[DOTSPLAT:%.*]] = shufflevector <4 x i32> [[DOTSPLATINSERT]], <4 x i32> poison, <4 x i32> zeroinitializer
 392 ; CHECK-NEXT:    [[TMP14:%.*]] = mul <4 x i32> <i32 0, i32 1, i32 2, i32 3>, [[DOTSPLAT]]
 393 ; CHECK-NEXT:    [[INDUCTION:%.*]] = add <4 x i32> zeroinitializer, [[TMP14]]
 394 ; CHECK-NEXT:    [[TMP15:%.*]] = mul i32 [[CONV]], 4
 395 ; CHECK-NEXT:    [[DOTSPLATINSERT2:%.*]] = insertelement <4 x i32> poison, i32 [[TMP15]], i64 0
 396 ; CHECK-NEXT:    [[DOTSPLAT3:%.*]] = shufflevector <4 x i32> [[DOTSPLATINSERT2]], <4 x i32> poison, <4 x i32> zeroinitializer
 397 ; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]
 398 ; CHECK:       vector.body:
 399 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]
 400 ; CHECK-NEXT:    [[VEC_IND:%.*]] = phi <4 x i32> [ [[INDUCTION]], [[VECTOR_PH]] ], [ [[VEC_IND_NEXT:%.*]], [[VECTOR_BODY]] ]
 401 ; CHECK-NEXT:    [[TMP16:%.*]] = add i64 [[INDEX]], 0
 402 ; CHECK-NEXT:    [[TMP17:%.*]] = getelementptr inbounds [250 x i32], ptr @a, i64 0, i64 [[TMP16]]
 403 ; CHECK-NEXT:    [[TMP18:%.*]] = getelementptr inbounds i32, ptr [[TMP17]], i32 0
 404 ; CHECK-NEXT:    store <4 x i32> [[VEC_IND]], ptr [[TMP18]], align 4
 405 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
 406 ; CHECK-NEXT:    [[VEC_IND_NEXT]] = add <4 x i32> [[VEC_IND]], [[DOTSPLAT3]]
 407 ; CHECK-NEXT:    [[TMP19:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
 408 ; CHECK-NEXT:    br i1 [[TMP19]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP6:![0-9]+]]
 409 ; CHECK:       middle.block:
 410 ; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i64 [[WIDE_TRIP_COUNT]], [[N_VEC]]
 411 ; CHECK-NEXT:    br i1 [[CMP_N]], label [[FOR_END_LOOPEXIT:%.*]], label [[SCALAR_PH]]
 412 ; CHECK:       scalar.ph:
 413 ; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], [[MIDDLE_BLOCK]] ], [ 0, [[VECTOR_SCEVCHECK]] ], [ 0, [[FOR_BODY_PREHEADER]] ]
 414 ; CHECK-NEXT:    [[BC_RESUME_VAL1:%.*]] = phi i32 [ [[IND_END]], [[MIDDLE_BLOCK]] ], [ 0, [[VECTOR_SCEVCHECK]] ], [ 0, [[FOR_BODY_PREHEADER]] ]
 415 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 416 ; CHECK:       for.body:
 417 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY]] ], [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ]
 418 ; CHECK-NEXT:    [[P_011:%.*]] = phi i32 [ [[ADD:%.*]], [[FOR_BODY]] ], [ [[BC_RESUME_VAL1]], [[SCALAR_PH]] ]
 419 ; CHECK-NEXT:    [[SEXT:%.*]] = shl i32 [[P_011]], 24
 420 ; CHECK-NEXT:    [[CONV2:%.*]] = ashr exact i32 [[SEXT]], 24
 421 ; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds [250 x i32], ptr @a, i64 0, i64 [[INDVARS_IV]]
 422 ; CHECK-NEXT:    store i32 [[CONV2]], ptr [[ARRAYIDX]], align 4
 423 ; CHECK-NEXT:    [[ADD]] = add nsw i32 [[CONV2]], [[CONV]]
 424 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
 425 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], [[WIDE_TRIP_COUNT]]
 426 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_END_LOOPEXIT]], label [[FOR_BODY]], !llvm.loop [[LOOP7:![0-9]+]]
 427 ; CHECK:       for.end.loopexit:
 428 ; CHECK-NEXT:    br label [[FOR_END]]
 429 ; CHECK:       for.end:
 430 ; CHECK-NEXT:    ret void
 431 ;
 432 entry:
 433   %conv = sext i8 %cstep to i32
 434   %cmp10 = icmp sgt i32 %n, 0
 435   br i1 %cmp10, label %for.body.preheader, label %for.end
 436
 437 for.body.preheader:
 438   %wide.trip.count = zext i32 %n to i64
 439   br label %for.body
 440
 441 for.body:
 442   %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %for.body.preheader ]
 443   %p.011 = phi i32 [ %add, %for.body ], [ 0, %for.body.preheader ]
 444   %sext = shl i32 %p.011, 24
 445   %conv2 = ashr exact i32 %sext, 24
 446   %arrayidx = getelementptr inbounds [250 x i32], ptr @a, i64 0, i64 %indvars.iv
 447   store i32 %conv2, ptr %arrayidx, align 4
 448   %add = add nsw i32 %conv2, %conv
 449   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
 450   %exitcond = icmp eq i64 %indvars.iv.next, %wide.trip.count
 451   br i1 %exitcond, label %for.end.loopexit, label %for.body
 452
 453 for.end.loopexit:
 454   br label %for.end
 455
 456 for.end:
 457   ret void
 458 }