llvm/test/Transforms/LoopVectorize/trip-count-expansion-may-introduce-ub.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 4
   2 ; RUN: opt -p loop-vectorize -force-vector-width=4 -S %s | FileCheck %s
   3
   4 ; Test cases with trip counts containing UDIV expressions for
   5 ; https://github.com/llvm/llvm-project/issues/89958.
   6
   7 define i64 @multi_exit_1_exit_count_with_udiv_by_value_in_header(ptr %dst, i64 %N) {
   8 ; CHECK-LABEL: define i64 @multi_exit_1_exit_count_with_udiv_by_value_in_header(
   9 ; CHECK-SAME: ptr [[DST:%.*]], i64 [[N:%.*]]) {
  10 ; CHECK-NEXT:  entry:
  11 ; CHECK-NEXT:    [[SMAX:%.*]] = call i64 @llvm.smax.i64(i64 [[N]], i64 0)
  12 ; CHECK-NEXT:    [[TMP0:%.*]] = udiv i64 42, [[N]]
  13 ; CHECK-NEXT:    [[UMIN:%.*]] = call i64 @llvm.umin.i64(i64 [[SMAX]], i64 [[TMP0]])
  14 ; CHECK-NEXT:    [[TMP1:%.*]] = add nuw nsw i64 [[UMIN]], 1
  15 ; CHECK-NEXT:    [[MIN_ITERS_CHECK:%.*]] = icmp ule i64 [[TMP1]], 4
  16 ; CHECK-NEXT:    br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_PH:%.*]]
  17 ; CHECK:       vector.ph:
  18 ; CHECK-NEXT:    [[N_MOD_VF:%.*]] = urem i64 [[TMP1]], 4
  19 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i64 [[N_MOD_VF]], 0
  20 ; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[TMP2]], i64 4, i64 [[N_MOD_VF]]
  21 ; CHECK-NEXT:    [[N_VEC:%.*]] = sub i64 [[TMP1]], [[TMP3]]
  22 ; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]
  23 ; CHECK:       vector.body:
  24 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]
  25 ; CHECK-NEXT:    [[TMP4:%.*]] = add i64 [[INDEX]], 0
  26 ; CHECK-NEXT:    [[TMP5:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP4]]
  27 ; CHECK-NEXT:    [[TMP6:%.*]] = getelementptr inbounds i32, ptr [[TMP5]], i32 0
  28 ; CHECK-NEXT:    store <4 x i32> splat (i32 1), ptr [[TMP6]], align 4
  29 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
  30 ; CHECK-NEXT:    [[TMP7:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
  31 ; CHECK-NEXT:    br i1 [[TMP7]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP0:![0-9]+]]
  32 ; CHECK:       middle.block:
  33 ; CHECK-NEXT:    br label [[SCALAR_PH]]
  34 ; CHECK:       scalar.ph:
  35 ; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY:%.*]] ]
  36 ; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
  37 ; CHECK:       loop.header:
  38 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
  39 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[IV]]
  40 ; CHECK-NEXT:    store i32 1, ptr [[GEP]], align 4
  41 ; CHECK-NEXT:    [[D:%.*]] = udiv i64 42, [[N]]
  42 ; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i64 [[IV]], [[D]]
  43 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_LATCH]], label [[EXIT:%.*]]
  44 ; CHECK:       loop.latch:
  45 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
  46 ; CHECK-NEXT:    [[C_0:%.*]] = icmp slt i64 [[IV]], [[N]]
  47 ; CHECK-NEXT:    br i1 [[C_0]], label [[LOOP_HEADER]], label [[EXIT]], !llvm.loop [[LOOP3:![0-9]+]]
  48 ; CHECK:       exit:
  49 ; CHECK-NEXT:    [[P:%.*]] = phi i64 [ 1, [[LOOP_HEADER]] ], [ 0, [[LOOP_LATCH]] ]
  50 ; CHECK-NEXT:    ret i64 [[P]]
  51 ;
  52 entry:
  53   br label %loop.header
  54
  55 loop.header:
  56   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop.latch ]
  57   %gep = getelementptr inbounds i32, ptr %dst, i64 %iv
  58   store i32 1, ptr %gep
  59   %d = udiv i64 42, %N
  60   %c.1 = icmp slt i64 %iv, %d
  61   br i1 %c.1, label %loop.latch, label %exit
  62
  63 loop.latch:
  64   %iv.next = add i64 %iv, 1
  65   %c.0 = icmp slt i64 %iv, %N
  66   br i1 %c.0, label %loop.header, label %exit
  67
  68 exit:
  69   %p = phi i64 [ 1, %loop.header ], [ 0, %loop.latch]
  70   ret i64 %p
  71 }
  72
  73 define i64 @multi_exit_1_exit_count_with_udiv_by_constant_in_header(ptr %dst, i64 %N) {
  74 ; CHECK-LABEL: define i64 @multi_exit_1_exit_count_with_udiv_by_constant_in_header(
  75 ; CHECK-SAME: ptr [[DST:%.*]], i64 [[N:%.*]]) {
  76 ; CHECK-NEXT:  entry:
  77 ; CHECK-NEXT:    [[SMAX:%.*]] = call i64 @llvm.smax.i64(i64 [[N]], i64 0)
  78 ; CHECK-NEXT:    [[TMP0:%.*]] = udiv i64 [[N]], 42
  79 ; CHECK-NEXT:    [[UMIN:%.*]] = call i64 @llvm.umin.i64(i64 [[SMAX]], i64 [[TMP0]])
  80 ; CHECK-NEXT:    [[TMP1:%.*]] = add nuw nsw i64 [[UMIN]], 1
  81 ; CHECK-NEXT:    [[MIN_ITERS_CHECK:%.*]] = icmp ule i64 [[TMP1]], 4
  82 ; CHECK-NEXT:    br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_PH:%.*]]
  83 ; CHECK:       vector.ph:
  84 ; CHECK-NEXT:    [[N_MOD_VF:%.*]] = urem i64 [[TMP1]], 4
  85 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i64 [[N_MOD_VF]], 0
  86 ; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[TMP2]], i64 4, i64 [[N_MOD_VF]]
  87 ; CHECK-NEXT:    [[N_VEC:%.*]] = sub i64 [[TMP1]], [[TMP3]]
  88 ; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]
  89 ; CHECK:       vector.body:
  90 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]
  91 ; CHECK-NEXT:    [[TMP4:%.*]] = add i64 [[INDEX]], 0
  92 ; CHECK-NEXT:    [[TMP5:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP4]]
  93 ; CHECK-NEXT:    [[TMP6:%.*]] = getelementptr inbounds i32, ptr [[TMP5]], i32 0
  94 ; CHECK-NEXT:    store <4 x i32> splat (i32 1), ptr [[TMP6]], align 4
  95 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
  96 ; CHECK-NEXT:    [[TMP7:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
  97 ; CHECK-NEXT:    br i1 [[TMP7]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP4:![0-9]+]]
  98 ; CHECK:       middle.block:
  99 ; CHECK-NEXT:    br label [[SCALAR_PH]]
 100 ; CHECK:       scalar.ph:
 101 ; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY:%.*]] ]
 102 ; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
 103 ; CHECK:       loop.header:
 104 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
 105 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[IV]]
 106 ; CHECK-NEXT:    store i32 1, ptr [[GEP]], align 4
 107 ; CHECK-NEXT:    [[D:%.*]] = udiv i64 [[N]], 42
 108 ; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i64 [[IV]], [[D]]
 109 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_LATCH]], label [[EXIT:%.*]]
 110 ; CHECK:       loop.latch:
 111 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
 112 ; CHECK-NEXT:    [[C_0:%.*]] = icmp slt i64 [[IV]], [[N]]
 113 ; CHECK-NEXT:    br i1 [[C_0]], label [[LOOP_HEADER]], label [[EXIT]], !llvm.loop [[LOOP5:![0-9]+]]
 114 ; CHECK:       exit:
 115 ; CHECK-NEXT:    [[P:%.*]] = phi i64 [ 1, [[LOOP_HEADER]] ], [ 0, [[LOOP_LATCH]] ]
 116 ; CHECK-NEXT:    ret i64 [[P]]
 117 ;
 118 entry:
 119   br label %loop.header
 120
 121 loop.header:
 122   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop.latch ]
 123   %gep = getelementptr inbounds i32, ptr %dst, i64 %iv
 124   store i32 1, ptr %gep
 125   %d = udiv i64 %N, 42
 126   %c.1 = icmp slt i64 %iv, %d
 127   br i1 %c.1, label %loop.latch, label %exit
 128
 129 loop.latch:
 130   %iv.next = add i64 %iv, 1
 131   %c.0 = icmp slt i64 %iv, %N
 132   br i1 %c.0, label %loop.header, label %exit
 133
 134 exit:
 135   %p = phi i64 [ 1, %loop.header ], [ 0, %loop.latch]
 136   ret i64 %p
 137 }
 138
 139 define i64 @multi_exit_2_exit_count_with_udiv_by_value_in_block_executed_unconditionally(ptr %A, i64 %N) {
 140 ; CHECK-LABEL: define i64 @multi_exit_2_exit_count_with_udiv_by_value_in_block_executed_unconditionally(
 141 ; CHECK-SAME: ptr [[A:%.*]], i64 [[N:%.*]]) {
 142 ; CHECK-NEXT:  entry:
 143 ; CHECK-NEXT:    [[SMAX:%.*]] = call i64 @llvm.smax.i64(i64 [[N]], i64 0)
 144 ; CHECK-NEXT:    [[TMP0:%.*]] = udiv i64 42, [[N]]
 145 ; CHECK-NEXT:    [[UMIN:%.*]] = call i64 @llvm.umin.i64(i64 [[SMAX]], i64 [[TMP0]])
 146 ; CHECK-NEXT:    [[TMP1:%.*]] = add nuw nsw i64 [[UMIN]], 1
 147 ; CHECK-NEXT:    [[MIN_ITERS_CHECK:%.*]] = icmp ule i64 [[TMP1]], 4
 148 ; CHECK-NEXT:    br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[ENTRY:%.*]]
 149 ; CHECK:       vector.ph:
 150 ; CHECK-NEXT:    [[N_MOD_VF:%.*]] = urem i64 [[TMP1]], 4
 151 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i64 [[N_MOD_VF]], 0
 152 ; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[TMP2]], i64 4, i64 [[N_MOD_VF]]
 153 ; CHECK-NEXT:    [[N_VEC:%.*]] = sub i64 [[TMP1]], [[TMP3]]
 154 ; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
 155 ; CHECK:       vector.body:
 156 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
 157 ; CHECK-NEXT:    [[TMP4:%.*]] = add i64 [[IV]], 0
 158 ; CHECK-NEXT:    [[TMP5:%.*]] = getelementptr inbounds i32, ptr [[A]], i64 [[TMP4]]
 159 ; CHECK-NEXT:    [[TMP6:%.*]] = getelementptr inbounds i32, ptr [[TMP5]], i32 0
 160 ; CHECK-NEXT:    [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP6]], align 4
 161 ; CHECK-NEXT:    [[TMP7:%.*]] = icmp eq <4 x i32> [[WIDE_LOAD]], splat (i32 10)
 162 ; CHECK-NEXT:    [[TMP8:%.*]] = extractelement <4 x i1> [[TMP7]], i32 0
 163 ; CHECK-NEXT:    br i1 [[TMP8]], label [[PRED_STORE_IF:%.*]], label [[PRED_STORE_CONTINUE:%.*]]
 164 ; CHECK:       pred.store.if:
 165 ; CHECK-NEXT:    [[TMP9:%.*]] = getelementptr inbounds i32, ptr [[A]], i64 [[TMP4]]
 166 ; CHECK-NEXT:    store i32 1, ptr [[TMP9]], align 4
 167 ; CHECK-NEXT:    br label [[PRED_STORE_CONTINUE]]
 168 ; CHECK:       pred.store.continue:
 169 ; CHECK-NEXT:    [[TMP10:%.*]] = extractelement <4 x i1> [[TMP7]], i32 1
 170 ; CHECK-NEXT:    br i1 [[TMP10]], label [[PRED_STORE_IF1:%.*]], label [[PRED_STORE_CONTINUE2:%.*]]
 171 ; CHECK:       pred.store.if1:
 172 ; CHECK-NEXT:    [[TMP11:%.*]] = add i64 [[IV]], 1
 173 ; CHECK-NEXT:    [[TMP12:%.*]] = getelementptr inbounds i32, ptr [[A]], i64 [[TMP11]]
 174 ; CHECK-NEXT:    store i32 1, ptr [[TMP12]], align 4
 175 ; CHECK-NEXT:    br label [[PRED_STORE_CONTINUE2]]
 176 ; CHECK:       pred.store.continue2:
 177 ; CHECK-NEXT:    [[TMP13:%.*]] = extractelement <4 x i1> [[TMP7]], i32 2
 178 ; CHECK-NEXT:    br i1 [[TMP13]], label [[PRED_STORE_IF3:%.*]], label [[PRED_STORE_CONTINUE4:%.*]]
 179 ; CHECK:       pred.store.if3:
 180 ; CHECK-NEXT:    [[TMP14:%.*]] = add i64 [[IV]], 2
 181 ; CHECK-NEXT:    [[TMP15:%.*]] = getelementptr inbounds i32, ptr [[A]], i64 [[TMP14]]
 182 ; CHECK-NEXT:    store i32 1, ptr [[TMP15]], align 4
 183 ; CHECK-NEXT:    br label [[PRED_STORE_CONTINUE4]]
 184 ; CHECK:       pred.store.continue4:
 185 ; CHECK-NEXT:    [[TMP16:%.*]] = extractelement <4 x i1> [[TMP7]], i32 3
 186 ; CHECK-NEXT:    br i1 [[TMP16]], label [[PRED_STORE_IF5:%.*]], label [[LOOP_LATCH]]
 187 ; CHECK:       pred.store.if5:
 188 ; CHECK-NEXT:    [[TMP17:%.*]] = add i64 [[IV]], 3
 189 ; CHECK-NEXT:    [[TMP18:%.*]] = getelementptr inbounds i32, ptr [[A]], i64 [[TMP17]]
 190 ; CHECK-NEXT:    store i32 1, ptr [[TMP18]], align 4
 191 ; CHECK-NEXT:    br label [[LOOP_LATCH]]
 192 ; CHECK:       pred.store.continue6:
 193 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw i64 [[IV]], 4
 194 ; CHECK-NEXT:    [[TMP19:%.*]] = icmp eq i64 [[IV_NEXT]], [[N_VEC]]
 195 ; CHECK-NEXT:    br i1 [[TMP19]], label [[MIDDLE_BLOCK:%.*]], label [[LOOP_HEADER]], !llvm.loop [[LOOP6:![0-9]+]]
 196 ; CHECK:       middle.block:
 197 ; CHECK-NEXT:    br label [[SCALAR_PH]]
 198 ; CHECK:       scalar.ph:
 199 ; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY1:%.*]] ]
 200 ; CHECK-NEXT:    br label [[LOOP_HEADER1:%.*]]
 201 ; CHECK:       loop.header:
 202 ; CHECK-NEXT:    [[IV1:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[IV_NEXT1:%.*]], [[LOOP_LATCH1:%.*]] ]
 203 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i32, ptr [[A]], i64 [[IV1]]
 204 ; CHECK-NEXT:    [[L:%.*]] = load i32, ptr [[GEP]], align 4
 205 ; CHECK-NEXT:    [[C_2:%.*]] = icmp eq i32 [[L]], 10
 206 ; CHECK-NEXT:    br i1 [[C_2]], label [[THEN:%.*]], label [[CONTINUE:%.*]]
 207 ; CHECK:       then:
 208 ; CHECK-NEXT:    store i32 1, ptr [[GEP]], align 4
 209 ; CHECK-NEXT:    br label [[CONTINUE]]
 210 ; CHECK:       continue:
 211 ; CHECK-NEXT:    [[D:%.*]] = udiv i64 42, [[N]]
 212 ; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i64 [[IV1]], [[D]]
 213 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_LATCH1]], label [[EXIT:%.*]]
 214 ; CHECK:       loop.latch:
 215 ; CHECK-NEXT:    [[IV_NEXT1]] = add i64 [[IV1]], 1
 216 ; CHECK-NEXT:    [[C_0:%.*]] = icmp slt i64 [[IV1]], [[N]]
 217 ; CHECK-NEXT:    br i1 [[C_0]], label [[LOOP_HEADER1]], label [[EXIT]], !llvm.loop [[LOOP7:![0-9]+]]
 218 ; CHECK:       exit:
 219 ; CHECK-NEXT:    [[P:%.*]] = phi i64 [ 1, [[CONTINUE]] ], [ 0, [[LOOP_LATCH1]] ]
 220 ; CHECK-NEXT:    ret i64 [[P]]
 221 ;
 222 entry:
 223   br label %loop.header
 224
 225 loop.header:
 226   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop.latch ]
 227   %gep = getelementptr inbounds i32, ptr %A, i64 %iv
 228   %l = load i32, ptr %gep
 229   %c.2 = icmp eq i32 %l, 10
 230   br i1 %c.2, label %then, label %continue
 231
 232 then:
 233   store i32 1, ptr %gep
 234   br label %continue
 235
 236 continue:
 237   %d = udiv i64 42, %N
 238   %c.1 = icmp slt i64 %iv, %d
 239   br i1 %c.1, label %loop.latch, label %exit
 240
 241 loop.latch:
 242   %iv.next = add i64 %iv, 1
 243   %c.0 = icmp slt i64 %iv, %N
 244   br i1 %c.0, label %loop.header, label %exit
 245
 246 exit:
 247   %p = phi i64 [ 1, %continue ], [ 0, %loop.latch]
 248   ret i64 %p
 249 }
 250
 251 define i64 @multi_exit_2_exit_count_with_udiv_by_constant_in_block_executed_unconditionally(ptr %A, i64 %N) {
 252 ; CHECK-LABEL: define i64 @multi_exit_2_exit_count_with_udiv_by_constant_in_block_executed_unconditionally(
 253 ; CHECK-SAME: ptr [[A:%.*]], i64 [[N:%.*]]) {
 254 ; CHECK-NEXT:  entry:
 255 ; CHECK-NEXT:    [[SMAX:%.*]] = call i64 @llvm.smax.i64(i64 [[N]], i64 0)
 256 ; CHECK-NEXT:    [[TMP0:%.*]] = udiv i64 [[N]], 42
 257 ; CHECK-NEXT:    [[UMIN:%.*]] = call i64 @llvm.umin.i64(i64 [[SMAX]], i64 [[TMP0]])
 258 ; CHECK-NEXT:    [[TMP1:%.*]] = add nuw nsw i64 [[UMIN]], 1
 259 ; CHECK-NEXT:    [[MIN_ITERS_CHECK:%.*]] = icmp ule i64 [[TMP1]], 4
 260 ; CHECK-NEXT:    br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[ENTRY:%.*]]
 261 ; CHECK:       vector.ph:
 262 ; CHECK-NEXT:    [[N_MOD_VF:%.*]] = urem i64 [[TMP1]], 4
 263 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i64 [[N_MOD_VF]], 0
 264 ; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[TMP2]], i64 4, i64 [[N_MOD_VF]]
 265 ; CHECK-NEXT:    [[N_VEC:%.*]] = sub i64 [[TMP1]], [[TMP3]]
 266 ; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
 267 ; CHECK:       vector.body:
 268 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
 269 ; CHECK-NEXT:    [[TMP4:%.*]] = add i64 [[IV]], 0
 270 ; CHECK-NEXT:    [[TMP5:%.*]] = getelementptr inbounds i32, ptr [[A]], i64 [[TMP4]]
 271 ; CHECK-NEXT:    [[TMP6:%.*]] = getelementptr inbounds i32, ptr [[TMP5]], i32 0
 272 ; CHECK-NEXT:    [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP6]], align 4
 273 ; CHECK-NEXT:    [[TMP7:%.*]] = icmp eq <4 x i32> [[WIDE_LOAD]], splat (i32 10)
 274 ; CHECK-NEXT:    [[TMP8:%.*]] = extractelement <4 x i1> [[TMP7]], i32 0
 275 ; CHECK-NEXT:    br i1 [[TMP8]], label [[PRED_STORE_IF:%.*]], label [[PRED_STORE_CONTINUE:%.*]]
 276 ; CHECK:       pred.store.if:
 277 ; CHECK-NEXT:    [[TMP9:%.*]] = getelementptr inbounds i32, ptr [[A]], i64 [[TMP4]]
 278 ; CHECK-NEXT:    store i32 1, ptr [[TMP9]], align 4
 279 ; CHECK-NEXT:    br label [[PRED_STORE_CONTINUE]]
 280 ; CHECK:       pred.store.continue:
 281 ; CHECK-NEXT:    [[TMP10:%.*]] = extractelement <4 x i1> [[TMP7]], i32 1
 282 ; CHECK-NEXT:    br i1 [[TMP10]], label [[PRED_STORE_IF1:%.*]], label [[PRED_STORE_CONTINUE2:%.*]]
 283 ; CHECK:       pred.store.if1:
 284 ; CHECK-NEXT:    [[TMP11:%.*]] = add i64 [[IV]], 1
 285 ; CHECK-NEXT:    [[TMP12:%.*]] = getelementptr inbounds i32, ptr [[A]], i64 [[TMP11]]
 286 ; CHECK-NEXT:    store i32 1, ptr [[TMP12]], align 4
 287 ; CHECK-NEXT:    br label [[PRED_STORE_CONTINUE2]]
 288 ; CHECK:       pred.store.continue2:
 289 ; CHECK-NEXT:    [[TMP13:%.*]] = extractelement <4 x i1> [[TMP7]], i32 2
 290 ; CHECK-NEXT:    br i1 [[TMP13]], label [[PRED_STORE_IF3:%.*]], label [[PRED_STORE_CONTINUE4:%.*]]
 291 ; CHECK:       pred.store.if3:
 292 ; CHECK-NEXT:    [[TMP14:%.*]] = add i64 [[IV]], 2
 293 ; CHECK-NEXT:    [[TMP15:%.*]] = getelementptr inbounds i32, ptr [[A]], i64 [[TMP14]]
 294 ; CHECK-NEXT:    store i32 1, ptr [[TMP15]], align 4
 295 ; CHECK-NEXT:    br label [[PRED_STORE_CONTINUE4]]
 296 ; CHECK:       pred.store.continue4:
 297 ; CHECK-NEXT:    [[TMP16:%.*]] = extractelement <4 x i1> [[TMP7]], i32 3
 298 ; CHECK-NEXT:    br i1 [[TMP16]], label [[PRED_STORE_IF5:%.*]], label [[LOOP_LATCH]]
 299 ; CHECK:       pred.store.if5:
 300 ; CHECK-NEXT:    [[TMP17:%.*]] = add i64 [[IV]], 3
 301 ; CHECK-NEXT:    [[TMP18:%.*]] = getelementptr inbounds i32, ptr [[A]], i64 [[TMP17]]
 302 ; CHECK-NEXT:    store i32 1, ptr [[TMP18]], align 4
 303 ; CHECK-NEXT:    br label [[LOOP_LATCH]]
 304 ; CHECK:       pred.store.continue6:
 305 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw i64 [[IV]], 4
 306 ; CHECK-NEXT:    [[TMP19:%.*]] = icmp eq i64 [[IV_NEXT]], [[N_VEC]]
 307 ; CHECK-NEXT:    br i1 [[TMP19]], label [[MIDDLE_BLOCK:%.*]], label [[LOOP_HEADER]], !llvm.loop [[LOOP8:![0-9]+]]
 308 ; CHECK:       middle.block:
 309 ; CHECK-NEXT:    br label [[SCALAR_PH]]
 310 ; CHECK:       scalar.ph:
 311 ; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY1:%.*]] ]
 312 ; CHECK-NEXT:    br label [[LOOP_HEADER1:%.*]]
 313 ; CHECK:       loop.header:
 314 ; CHECK-NEXT:    [[IV1:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[IV_NEXT1:%.*]], [[LOOP_LATCH1:%.*]] ]
 315 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i32, ptr [[A]], i64 [[IV1]]
 316 ; CHECK-NEXT:    [[L:%.*]] = load i32, ptr [[GEP]], align 4
 317 ; CHECK-NEXT:    [[C_2:%.*]] = icmp eq i32 [[L]], 10
 318 ; CHECK-NEXT:    br i1 [[C_2]], label [[THEN:%.*]], label [[CONTINUE:%.*]]
 319 ; CHECK:       then:
 320 ; CHECK-NEXT:    store i32 1, ptr [[GEP]], align 4
 321 ; CHECK-NEXT:    br label [[CONTINUE]]
 322 ; CHECK:       continue:
 323 ; CHECK-NEXT:    [[D:%.*]] = udiv i64 [[N]], 42
 324 ; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i64 [[IV1]], [[D]]
 325 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_LATCH1]], label [[EXIT:%.*]]
 326 ; CHECK:       loop.latch:
 327 ; CHECK-NEXT:    [[IV_NEXT1]] = add i64 [[IV1]], 1
 328 ; CHECK-NEXT:    [[C_0:%.*]] = icmp slt i64 [[IV1]], [[N]]
 329 ; CHECK-NEXT:    br i1 [[C_0]], label [[LOOP_HEADER1]], label [[EXIT]], !llvm.loop [[LOOP9:![0-9]+]]
 330 ; CHECK:       exit:
 331 ; CHECK-NEXT:    [[P:%.*]] = phi i64 [ 1, [[CONTINUE]] ], [ 0, [[LOOP_LATCH1]] ]
 332 ; CHECK-NEXT:    ret i64 [[P]]
 333 ;
 334 entry:
 335   br label %loop.header
 336
 337 loop.header:
 338   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop.latch ]
 339   %gep = getelementptr inbounds i32, ptr %A, i64 %iv
 340   %l = load i32, ptr %gep
 341   %c.2 = icmp eq i32 %l, 10
 342   br i1 %c.2, label %then, label %continue
 343
 344 then:
 345   store i32 1, ptr %gep
 346   br label %continue
 347
 348 continue:
 349   %d = udiv i64 %N, 42
 350   %c.1 = icmp slt i64 %iv, %d
 351   br i1 %c.1, label %loop.latch, label %exit
 352
 353 loop.latch:
 354   %iv.next = add i64 %iv, 1
 355   %c.0 = icmp slt i64 %iv, %N
 356   br i1 %c.0, label %loop.header, label %exit
 357
 358 exit:
 359   %p = phi i64 [ 1, %continue ], [ 0, %loop.latch]
 360   ret i64 %p
 361 }
 362
 363 define i64 @multi_exit_3_exit_count_with_udiv_by_value_in_block_executed_conditionally(ptr %A, i64 %N) {
 364 ; CHECK-LABEL: define i64 @multi_exit_3_exit_count_with_udiv_by_value_in_block_executed_conditionally(
 365 ; CHECK-SAME: ptr [[A:%.*]], i64 [[N:%.*]]) {
 366 ; CHECK-NEXT:  entry:
 367 ; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
 368 ; CHECK:       loop.header:
 369 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
 370 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i32, ptr [[A]], i64 [[IV]]
 371 ; CHECK-NEXT:    [[L:%.*]] = load i32, ptr [[GEP]], align 4
 372 ; CHECK-NEXT:    [[C_2:%.*]] = icmp eq i32 [[L]], 10
 373 ; CHECK-NEXT:    br i1 [[C_2]], label [[THEN:%.*]], label [[LOOP_LATCH]]
 374 ; CHECK:       then:
 375 ; CHECK-NEXT:    [[D:%.*]] = udiv i64 42, [[N]]
 376 ; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i64 [[IV]], [[D]]
 377 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_LATCH]], label [[EXIT:%.*]]
 378 ; CHECK:       loop.latch:
 379 ; CHECK-NEXT:    store i32 1, ptr [[GEP]], align 4
 380 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
 381 ; CHECK-NEXT:    [[C_0:%.*]] = icmp slt i64 [[IV]], [[N]]
 382 ; CHECK-NEXT:    br i1 [[C_0]], label [[LOOP_HEADER]], label [[EXIT]]
 383 ; CHECK:       exit:
 384 ; CHECK-NEXT:    [[P:%.*]] = phi i64 [ 1, [[THEN]] ], [ 0, [[LOOP_LATCH]] ]
 385 ; CHECK-NEXT:    ret i64 [[P]]
 386 ;
 387 entry:
 388   br label %loop.header
 389
 390 loop.header:
 391   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop.latch ]
 392   %gep = getelementptr inbounds i32, ptr %A, i64 %iv
 393   %l = load i32, ptr %gep
 394   %c.2 = icmp eq i32 %l, 10
 395   br i1 %c.2, label %then, label %loop.latch
 396
 397 then:
 398   %d = udiv i64 42, %N
 399   %c.1 = icmp slt i64 %iv, %d
 400   br i1 %c.1, label %loop.latch, label %exit
 401
 402 loop.latch:
 403   store i32 1, ptr %gep
 404   %iv.next = add i64 %iv, 1
 405   %c.0 = icmp slt i64 %iv, %N
 406   br i1 %c.0, label %loop.header, label %exit
 407
 408 exit:
 409   %p = phi i64 [ 1, %then ], [ 0, %loop.latch]
 410   ret i64 %p
 411 }
 412
 413 define i64 @multi_exit_3_exit_count_with_udiv_by_constant_in_block_executed_conditionally(ptr %A, i64 %N) {
 414 ; CHECK-LABEL: define i64 @multi_exit_3_exit_count_with_udiv_by_constant_in_block_executed_conditionally(
 415 ; CHECK-SAME: ptr [[A:%.*]], i64 [[N:%.*]]) {
 416 ; CHECK-NEXT:  entry:
 417 ; CHECK-NEXT:    [[D:%.*]] = udiv i64 [[N]], 42
 418 ; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
 419 ; CHECK:       loop.header:
 420 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
 421 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i32, ptr [[A]], i64 [[IV]]
 422 ; CHECK-NEXT:    [[L:%.*]] = load i32, ptr [[GEP]], align 4
 423 ; CHECK-NEXT:    [[C_2:%.*]] = icmp ne i32 [[L]], 10
 424 ; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i64 [[IV]], [[D]]
 425 ; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C_2]], i1 true, i1 [[C_1]]
 426 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[LOOP_LATCH]], label [[EXIT:%.*]]
 427 ; CHECK:       loop.latch:
 428 ; CHECK-NEXT:    store i32 1, ptr [[GEP]], align 4
 429 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
 430 ; CHECK-NEXT:    [[C_0:%.*]] = icmp slt i64 [[IV]], [[N]]
 431 ; CHECK-NEXT:    br i1 [[C_0]], label [[LOOP_HEADER]], label [[EXIT]]
 432 ; CHECK:       exit:
 433 ; CHECK-NEXT:    [[P:%.*]] = phi i64 [ 0, [[LOOP_LATCH]] ], [ 1, [[LOOP_HEADER]] ]
 434 ; CHECK-NEXT:    ret i64 [[P]]
 435 ;
 436 entry:
 437   br label %loop.header
 438
 439 loop.header:
 440   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop.latch ]
 441   %gep = getelementptr inbounds i32, ptr %A, i64 %iv
 442   %l = load i32, ptr %gep
 443   %c.2 = icmp eq i32 %l, 10
 444   br i1 %c.2, label %then, label %loop.latch
 445
 446 then:
 447   %d = udiv i64 %N, 42
 448   %c.1 = icmp slt i64 %iv, %d
 449   br i1 %c.1, label %loop.latch, label %exit
 450
 451 loop.latch:
 452   store i32 1, ptr %gep
 453   %iv.next = add i64 %iv, 1
 454   %c.0 = icmp slt i64 %iv, %N
 455   br i1 %c.0, label %loop.header, label %exit
 456
 457 exit:
 458   %p = phi i64 [ 1, %then ], [ 0, %loop.latch]
 459   ret i64 %p
 460 }
 461
 462 define i64 @multi_exit_4_exit_count_with_udiv_by_value_in_latch(ptr %dst, i64 %N) {
 463 ; CHECK-LABEL: define i64 @multi_exit_4_exit_count_with_udiv_by_value_in_latch(
 464 ; CHECK-SAME: ptr [[DST:%.*]], i64 [[N:%.*]]) {
 465 ; CHECK-NEXT:  entry:
 466 ; CHECK-NEXT:    [[TMP10:%.*]] = call i64 @llvm.umax.i64(i64 [[N]], i64 1)
 467 ; CHECK-NEXT:    [[TMP0:%.*]] = udiv i64 42, [[TMP10]]
 468 ; CHECK-NEXT:    [[TMP8:%.*]] = freeze i64 [[TMP0]]
 469 ; CHECK-NEXT:    [[SMAX:%.*]] = call i64 @llvm.smax.i64(i64 [[N]], i64 0)
 470 ; CHECK-NEXT:    [[UMIN:%.*]] = call i64 @llvm.umin.i64(i64 [[TMP8]], i64 [[SMAX]])
 471 ; CHECK-NEXT:    [[TMP1:%.*]] = add nuw nsw i64 [[UMIN]], 1
 472 ; CHECK-NEXT:    [[MIN_ITERS_CHECK:%.*]] = icmp ule i64 [[TMP1]], 4
 473 ; CHECK-NEXT:    br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_PH:%.*]]
 474 ; CHECK:       vector.ph:
 475 ; CHECK-NEXT:    [[N_MOD_VF:%.*]] = urem i64 [[TMP1]], 4
 476 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i64 [[N_MOD_VF]], 0
 477 ; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[TMP2]], i64 4, i64 [[N_MOD_VF]]
 478 ; CHECK-NEXT:    [[N_VEC:%.*]] = sub i64 [[TMP1]], [[TMP3]]
 479 ; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]
 480 ; CHECK:       vector.body:
 481 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]
 482 ; CHECK-NEXT:    [[TMP4:%.*]] = add i64 [[INDEX]], 0
 483 ; CHECK-NEXT:    [[TMP5:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP4]]
 484 ; CHECK-NEXT:    [[TMP6:%.*]] = getelementptr inbounds i32, ptr [[TMP5]], i32 0
 485 ; CHECK-NEXT:    store <4 x i32> splat (i32 1), ptr [[TMP6]], align 4
 486 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
 487 ; CHECK-NEXT:    [[TMP7:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
 488 ; CHECK-NEXT:    br i1 [[TMP7]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP10:![0-9]+]]
 489 ; CHECK:       middle.block:
 490 ; CHECK-NEXT:    br label [[SCALAR_PH]]
 491 ; CHECK:       scalar.ph:
 492 ; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY:%.*]] ]
 493 ; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
 494 ; CHECK:       loop.header:
 495 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
 496 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[IV]]
 497 ; CHECK-NEXT:    store i32 1, ptr [[GEP]], align 4
 498 ; CHECK-NEXT:    [[C_0:%.*]] = icmp slt i64 [[IV]], [[N]]
 499 ; CHECK-NEXT:    br i1 [[C_0]], label [[LOOP_LATCH]], label [[EXIT:%.*]]
 500 ; CHECK:       loop.latch:
 501 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
 502 ; CHECK-NEXT:    [[D:%.*]] = udiv i64 42, [[N]]
 503 ; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i64 [[IV]], [[D]]
 504 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_HEADER]], label [[EXIT]], !llvm.loop [[LOOP11:![0-9]+]]
 505 ; CHECK:       exit:
 506 ; CHECK-NEXT:    [[P:%.*]] = phi i64 [ 1, [[LOOP_HEADER]] ], [ 0, [[LOOP_LATCH]] ]
 507 ; CHECK-NEXT:    ret i64 [[P]]
 508 ;
 509 entry:
 510   br label %loop.header
 511
 512 loop.header:
 513   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop.latch ]
 514   %gep = getelementptr inbounds i32, ptr %dst, i64 %iv
 515   store i32 1, ptr %gep
 516   %c.0 = icmp slt i64 %iv, %N
 517   br i1 %c.0, label %loop.latch, label %exit
 518
 519 loop.latch:
 520   %iv.next = add i64 %iv, 1
 521   %d = udiv i64 42, %N
 522   %c.1 = icmp slt i64 %iv, %d
 523   br i1 %c.1, label %loop.header, label %exit
 524
 525 exit:
 526   %p = phi i64 [ 1, %loop.header ], [ 0, %loop.latch]
 527   ret i64 %p
 528 }
 529
 530 declare void @foo()
 531
 532 define i64 @multi_exit_4_exit_count_with_udiv_by_value_in_latch_call_before_loop(ptr %dst, i64 %N) {
 533 ; CHECK-LABEL: define i64 @multi_exit_4_exit_count_with_udiv_by_value_in_latch_call_before_loop(
 534 ; CHECK-SAME: ptr [[DST:%.*]], i64 [[N:%.*]]) {
 535 ; CHECK-NEXT:  entry:
 536 ; CHECK-NEXT:    call void @foo()
 537 ; CHECK-NEXT:    [[TMP0:%.*]] = freeze i64 [[N]]
 538 ; CHECK-NEXT:    [[TMP1:%.*]] = call i64 @llvm.umax.i64(i64 [[TMP0]], i64 1)
 539 ; CHECK-NEXT:    [[TMP2:%.*]] = udiv i64 42, [[TMP1]]
 540 ; CHECK-NEXT:    [[TMP3:%.*]] = freeze i64 [[TMP2]]
 541 ; CHECK-NEXT:    [[SMAX:%.*]] = call i64 @llvm.smax.i64(i64 [[N]], i64 0)
 542 ; CHECK-NEXT:    [[UMIN:%.*]] = call i64 @llvm.umin.i64(i64 [[TMP3]], i64 [[SMAX]])
 543 ; CHECK-NEXT:    [[TMP4:%.*]] = add nuw nsw i64 [[UMIN]], 1
 544 ; CHECK-NEXT:    [[MIN_ITERS_CHECK:%.*]] = icmp ule i64 [[TMP4]], 4
 545 ; CHECK-NEXT:    br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_PH:%.*]]
 546 ; CHECK:       vector.ph:
 547 ; CHECK-NEXT:    [[N_MOD_VF:%.*]] = urem i64 [[TMP4]], 4
 548 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp eq i64 [[N_MOD_VF]], 0
 549 ; CHECK-NEXT:    [[TMP6:%.*]] = select i1 [[TMP5]], i64 4, i64 [[N_MOD_VF]]
 550 ; CHECK-NEXT:    [[N_VEC:%.*]] = sub i64 [[TMP4]], [[TMP6]]
 551 ; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]
 552 ; CHECK:       vector.body:
 553 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]
 554 ; CHECK-NEXT:    [[TMP7:%.*]] = add i64 [[INDEX]], 0
 555 ; CHECK-NEXT:    [[TMP8:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP7]]
 556 ; CHECK-NEXT:    [[TMP9:%.*]] = getelementptr inbounds i32, ptr [[TMP8]], i32 0
 557 ; CHECK-NEXT:    store <4 x i32> splat (i32 1), ptr [[TMP9]], align 4
 558 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
 559 ; CHECK-NEXT:    [[TMP10:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
 560 ; CHECK-NEXT:    br i1 [[TMP10]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP12:![0-9]+]]
 561 ; CHECK:       middle.block:
 562 ; CHECK-NEXT:    br label [[SCALAR_PH]]
 563 ; CHECK:       scalar.ph:
 564 ; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY:%.*]] ]
 565 ; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
 566 ; CHECK:       loop.header:
 567 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
 568 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[IV]]
 569 ; CHECK-NEXT:    store i32 1, ptr [[GEP]], align 4
 570 ; CHECK-NEXT:    [[C_0:%.*]] = icmp slt i64 [[IV]], [[N]]
 571 ; CHECK-NEXT:    br i1 [[C_0]], label [[LOOP_LATCH]], label [[EXIT:%.*]]
 572 ; CHECK:       loop.latch:
 573 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
 574 ; CHECK-NEXT:    [[D:%.*]] = udiv i64 42, [[N]]
 575 ; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i64 [[IV]], [[D]]
 576 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_HEADER]], label [[EXIT]], !llvm.loop [[LOOP13:![0-9]+]]
 577 ; CHECK:       exit:
 578 ; CHECK-NEXT:    [[P:%.*]] = phi i64 [ 1, [[LOOP_HEADER]] ], [ 0, [[LOOP_LATCH]] ]
 579 ; CHECK-NEXT:    ret i64 [[P]]
 580 ;
 581 entry:
 582   call void @foo()
 583   br label %loop.header
 584
 585 loop.header:
 586   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop.latch ]
 587   %gep = getelementptr inbounds i32, ptr %dst, i64 %iv
 588   store i32 1, ptr %gep
 589   %c.0 = icmp slt i64 %iv, %N
 590   br i1 %c.0, label %loop.latch, label %exit
 591
 592 loop.latch:
 593   %iv.next = add i64 %iv, 1
 594   %d = udiv i64 42, %N
 595   %c.1 = icmp slt i64 %iv, %d
 596   br i1 %c.1, label %loop.header, label %exit
 597
 598 exit:
 599   %p = phi i64 [ 1, %loop.header ], [ 0, %loop.latch]
 600   ret i64 %p
 601 }
 602
 603 define i64 @multi_exit_4_exit_count_with_udiv_by_value_in_latch_loop_may_not_execute(ptr %dst, i64 %N, i1 %c) {
 604 ; CHECK-LABEL: define i64 @multi_exit_4_exit_count_with_udiv_by_value_in_latch_loop_may_not_execute(
 605 ; CHECK-SAME: ptr [[DST:%.*]], i64 [[N:%.*]], i1 [[C:%.*]]) {
 606 ; CHECK-NEXT:  entry:
 607 ; CHECK-NEXT:    br i1 [[C]], label [[LOOP_HEADER_PREHEADER:%.*]], label [[EXIT:%.*]]
 608 ; CHECK:       loop.header.preheader:
 609 ; CHECK-NEXT:    [[TMP0:%.*]] = freeze i64 [[N]]
 610 ; CHECK-NEXT:    [[TMP1:%.*]] = call i64 @llvm.umax.i64(i64 [[TMP0]], i64 1)
 611 ; CHECK-NEXT:    [[TMP2:%.*]] = udiv i64 42, [[TMP1]]
 612 ; CHECK-NEXT:    [[TMP3:%.*]] = freeze i64 [[TMP2]]
 613 ; CHECK-NEXT:    [[SMAX:%.*]] = call i64 @llvm.smax.i64(i64 [[N]], i64 0)
 614 ; CHECK-NEXT:    [[UMIN:%.*]] = call i64 @llvm.umin.i64(i64 [[TMP3]], i64 [[SMAX]])
 615 ; CHECK-NEXT:    [[TMP4:%.*]] = add nuw nsw i64 [[UMIN]], 1
 616 ; CHECK-NEXT:    [[MIN_ITERS_CHECK:%.*]] = icmp ule i64 [[TMP4]], 4
 617 ; CHECK-NEXT:    br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_PH:%.*]]
 618 ; CHECK:       vector.ph:
 619 ; CHECK-NEXT:    [[N_MOD_VF:%.*]] = urem i64 [[TMP4]], 4
 620 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp eq i64 [[N_MOD_VF]], 0
 621 ; CHECK-NEXT:    [[TMP6:%.*]] = select i1 [[TMP5]], i64 4, i64 [[N_MOD_VF]]
 622 ; CHECK-NEXT:    [[N_VEC:%.*]] = sub i64 [[TMP4]], [[TMP6]]
 623 ; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]
 624 ; CHECK:       vector.body:
 625 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]
 626 ; CHECK-NEXT:    [[TMP7:%.*]] = add i64 [[INDEX]], 0
 627 ; CHECK-NEXT:    [[TMP8:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP7]]
 628 ; CHECK-NEXT:    [[TMP9:%.*]] = getelementptr inbounds i32, ptr [[TMP8]], i32 0
 629 ; CHECK-NEXT:    store <4 x i32> splat (i32 1), ptr [[TMP9]], align 4
 630 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
 631 ; CHECK-NEXT:    [[TMP10:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
 632 ; CHECK-NEXT:    br i1 [[TMP10]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP14:![0-9]+]]
 633 ; CHECK:       middle.block:
 634 ; CHECK-NEXT:    br label [[SCALAR_PH]]
 635 ; CHECK:       scalar.ph:
 636 ; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], [[MIDDLE_BLOCK]] ], [ 0, [[LOOP_HEADER_PREHEADER]] ]
 637 ; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
 638 ; CHECK:       loop.header:
 639 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ], [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ]
 640 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[IV]]
 641 ; CHECK-NEXT:    store i32 1, ptr [[GEP]], align 4
 642 ; CHECK-NEXT:    [[C_0:%.*]] = icmp slt i64 [[IV]], [[N]]
 643 ; CHECK-NEXT:    br i1 [[C_0]], label [[LOOP_LATCH]], label [[EXIT_LOOPEXIT:%.*]]
 644 ; CHECK:       loop.latch:
 645 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
 646 ; CHECK-NEXT:    [[D:%.*]] = udiv i64 42, [[N]]
 647 ; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i64 [[IV]], [[D]]
 648 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_HEADER]], label [[EXIT_LOOPEXIT]], !llvm.loop [[LOOP15:![0-9]+]]
 649 ; CHECK:       exit.loopexit:
 650 ; CHECK-NEXT:    [[P_PH:%.*]] = phi i64 [ 0, [[LOOP_LATCH]] ], [ 1, [[LOOP_HEADER]] ]
 651 ; CHECK-NEXT:    br label [[EXIT]]
 652 ; CHECK:       exit:
 653 ; CHECK-NEXT:    [[P:%.*]] = phi i64 [ 2, [[ENTRY:%.*]] ], [ [[P_PH]], [[EXIT_LOOPEXIT]] ]
 654 ; CHECK-NEXT:    ret i64 [[P]]
 655 ;
 656 entry:
 657   br i1 %c, label %loop.header, label %exit
 658
 659 loop.header:
 660   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop.latch ]
 661   %gep = getelementptr inbounds i32, ptr %dst, i64 %iv
 662   store i32 1, ptr %gep
 663   %c.0 = icmp slt i64 %iv, %N
 664   br i1 %c.0, label %loop.latch, label %exit
 665
 666 loop.latch:
 667   %iv.next = add i64 %iv, 1
 668   %d = udiv i64 42, %N
 669   %c.1 = icmp slt i64 %iv, %d
 670   br i1 %c.1, label %loop.header, label %exit
 671
 672 exit:
 673   %p = phi i64 [ 1, %loop.header ], [ 0, %loop.latch], [ 2, %entry ]
 674   ret i64 %p
 675 }
 676
 677 define i64 @multi_exit_4_exit_count_with_udiv_by_value_in_latch_different_bounds(ptr %dst, i64 %N, i64 %M) {
 678 ; CHECK-LABEL: define i64 @multi_exit_4_exit_count_with_udiv_by_value_in_latch_different_bounds(
 679 ; CHECK-SAME: ptr [[DST:%.*]], i64 [[N:%.*]], i64 [[M:%.*]]) {
 680 ; CHECK-NEXT:  entry:
 681 ; CHECK-NEXT:    [[TMP0:%.*]] = freeze i64 [[M]]
 682 ; CHECK-NEXT:    [[TMP1:%.*]] = call i64 @llvm.umax.i64(i64 [[TMP0]], i64 1)
 683 ; CHECK-NEXT:    [[TMP2:%.*]] = udiv i64 42, [[TMP1]]
 684 ; CHECK-NEXT:    [[TMP3:%.*]] = freeze i64 [[TMP2]]
 685 ; CHECK-NEXT:    [[SMAX:%.*]] = call i64 @llvm.smax.i64(i64 [[N]], i64 0)
 686 ; CHECK-NEXT:    [[UMIN:%.*]] = call i64 @llvm.umin.i64(i64 [[TMP3]], i64 [[SMAX]])
 687 ; CHECK-NEXT:    [[TMP4:%.*]] = add nuw nsw i64 [[UMIN]], 1
 688 ; CHECK-NEXT:    [[MIN_ITERS_CHECK:%.*]] = icmp ule i64 [[TMP4]], 4
 689 ; CHECK-NEXT:    br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_PH:%.*]]
 690 ; CHECK:       vector.ph:
 691 ; CHECK-NEXT:    [[N_MOD_VF:%.*]] = urem i64 [[TMP4]], 4
 692 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp eq i64 [[N_MOD_VF]], 0
 693 ; CHECK-NEXT:    [[TMP6:%.*]] = select i1 [[TMP5]], i64 4, i64 [[N_MOD_VF]]
 694 ; CHECK-NEXT:    [[N_VEC:%.*]] = sub i64 [[TMP4]], [[TMP6]]
 695 ; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]
 696 ; CHECK:       vector.body:
 697 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]
 698 ; CHECK-NEXT:    [[TMP7:%.*]] = add i64 [[INDEX]], 0
 699 ; CHECK-NEXT:    [[TMP8:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP7]]
 700 ; CHECK-NEXT:    [[TMP9:%.*]] = getelementptr inbounds i32, ptr [[TMP8]], i32 0
 701 ; CHECK-NEXT:    store <4 x i32> splat (i32 1), ptr [[TMP9]], align 4
 702 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
 703 ; CHECK-NEXT:    [[TMP10:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
 704 ; CHECK-NEXT:    br i1 [[TMP10]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP16:![0-9]+]]
 705 ; CHECK:       middle.block:
 706 ; CHECK-NEXT:    br label [[SCALAR_PH]]
 707 ; CHECK:       scalar.ph:
 708 ; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY:%.*]] ]
 709 ; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
 710 ; CHECK:       loop.header:
 711 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
 712 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[IV]]
 713 ; CHECK-NEXT:    store i32 1, ptr [[GEP]], align 4
 714 ; CHECK-NEXT:    [[C_0:%.*]] = icmp slt i64 [[IV]], [[N]]
 715 ; CHECK-NEXT:    br i1 [[C_0]], label [[LOOP_LATCH]], label [[EXIT:%.*]]
 716 ; CHECK:       loop.latch:
 717 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
 718 ; CHECK-NEXT:    [[D:%.*]] = udiv i64 42, [[M]]
 719 ; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i64 [[IV]], [[D]]
 720 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_HEADER]], label [[EXIT]], !llvm.loop [[LOOP17:![0-9]+]]
 721 ; CHECK:       exit:
 722 ; CHECK-NEXT:    [[P:%.*]] = phi i64 [ 1, [[LOOP_HEADER]] ], [ 0, [[LOOP_LATCH]] ]
 723 ; CHECK-NEXT:    ret i64 [[P]]
 724 ;
 725 entry:
 726   br label %loop.header
 727
 728 loop.header:
 729   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop.latch ]
 730   %gep = getelementptr inbounds i32, ptr %dst, i64 %iv
 731   store i32 1, ptr %gep
 732   %c.0 = icmp slt i64 %iv, %N
 733   br i1 %c.0, label %loop.latch, label %exit
 734
 735 loop.latch:
 736   %iv.next = add i64 %iv, 1
 737   %d = udiv i64 42, %M
 738   %c.1 = icmp slt i64 %iv, %d
 739   br i1 %c.1, label %loop.header, label %exit
 740
 741 exit:
 742   %p = phi i64 [ 1, %loop.header ], [ 0, %loop.latch]
 743   ret i64 %p
 744 }
 745
 746 define i64 @multi_exit_4_exit_count_with_udiv_by_frozen_value_in_latch(ptr %dst, i64 %N) {
 747 ; CHECK-LABEL: define i64 @multi_exit_4_exit_count_with_udiv_by_frozen_value_in_latch(
 748 ; CHECK-SAME: ptr [[DST:%.*]], i64 [[N:%.*]]) {
 749 ; CHECK-NEXT:  entry:
 750 ; CHECK-NEXT:    [[FR_N:%.*]] = freeze i64 [[N]]
 751 ; CHECK-NEXT:    [[TMP1:%.*]] = call i64 @llvm.umax.i64(i64 [[FR_N]], i64 1)
 752 ; CHECK-NEXT:    [[TMP2:%.*]] = udiv i64 42, [[TMP1]]
 753 ; CHECK-NEXT:    [[TMP10:%.*]] = freeze i64 [[TMP2]]
 754 ; CHECK-NEXT:    [[SMAX:%.*]] = call i64 @llvm.smax.i64(i64 [[N]], i64 0)
 755 ; CHECK-NEXT:    [[UMIN:%.*]] = call i64 @llvm.umin.i64(i64 [[TMP10]], i64 [[SMAX]])
 756 ; CHECK-NEXT:    [[TMP3:%.*]] = add nuw nsw i64 [[UMIN]], 1
 757 ; CHECK-NEXT:    [[MIN_ITERS_CHECK:%.*]] = icmp ule i64 [[TMP3]], 4
 758 ; CHECK-NEXT:    br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_PH:%.*]]
 759 ; CHECK:       vector.ph:
 760 ; CHECK-NEXT:    [[N_MOD_VF:%.*]] = urem i64 [[TMP3]], 4
 761 ; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i64 [[N_MOD_VF]], 0
 762 ; CHECK-NEXT:    [[TMP5:%.*]] = select i1 [[TMP4]], i64 4, i64 [[N_MOD_VF]]
 763 ; CHECK-NEXT:    [[N_VEC:%.*]] = sub i64 [[TMP3]], [[TMP5]]
 764 ; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]
 765 ; CHECK:       vector.body:
 766 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]
 767 ; CHECK-NEXT:    [[TMP6:%.*]] = add i64 [[INDEX]], 0
 768 ; CHECK-NEXT:    [[TMP7:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP6]]
 769 ; CHECK-NEXT:    [[TMP8:%.*]] = getelementptr inbounds i32, ptr [[TMP7]], i32 0
 770 ; CHECK-NEXT:    store <4 x i32> splat (i32 1), ptr [[TMP8]], align 4
 771 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
 772 ; CHECK-NEXT:    [[TMP9:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
 773 ; CHECK-NEXT:    br i1 [[TMP9]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP18:![0-9]+]]
 774 ; CHECK:       middle.block:
 775 ; CHECK-NEXT:    br label [[SCALAR_PH]]
 776 ; CHECK:       scalar.ph:
 777 ; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY:%.*]] ]
 778 ; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
 779 ; CHECK:       loop.header:
 780 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
 781 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[IV]]
 782 ; CHECK-NEXT:    store i32 1, ptr [[GEP]], align 4
 783 ; CHECK-NEXT:    [[C_0:%.*]] = icmp slt i64 [[IV]], [[N]]
 784 ; CHECK-NEXT:    br i1 [[C_0]], label [[LOOP_LATCH]], label [[EXIT:%.*]]
 785 ; CHECK:       loop.latch:
 786 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
 787 ; CHECK-NEXT:    [[D:%.*]] = udiv i64 42, [[FR_N]]
 788 ; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i64 [[IV]], [[D]]
 789 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_HEADER]], label [[EXIT]], !llvm.loop [[LOOP19:![0-9]+]]
 790 ; CHECK:       exit:
 791 ; CHECK-NEXT:    [[P:%.*]] = phi i64 [ 1, [[LOOP_HEADER]] ], [ 0, [[LOOP_LATCH]] ]
 792 ; CHECK-NEXT:    ret i64 [[P]]
 793 ;
 794 entry:
 795   %fr.N = freeze i64 %N
 796   br label %loop.header
 797
 798 loop.header:
 799   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop.latch ]
 800   %gep = getelementptr inbounds i32, ptr %dst, i64 %iv
 801   store i32 1, ptr %gep
 802   %c.0 = icmp slt i64 %iv, %N
 803   br i1 %c.0, label %loop.latch, label %exit
 804
 805 loop.latch:
 806   %iv.next = add i64 %iv, 1
 807   %d = udiv i64 42, %fr.N
 808   %c.1 = icmp slt i64 %iv, %d
 809   br i1 %c.1, label %loop.header, label %exit
 810
 811 exit:
 812   %p = phi i64 [ 1, %loop.header ], [ 0, %loop.latch]
 813   ret i64 %p
 814 }
 815
 816
 817 define i64 @multi_exit_4_exit_count_with_udiv_by_constant_in_latch(ptr %dst, i64 %N) {
 818 ; CHECK-LABEL: define i64 @multi_exit_4_exit_count_with_udiv_by_constant_in_latch(
 819 ; CHECK-SAME: ptr [[DST:%.*]], i64 [[N:%.*]]) {
 820 ; CHECK-NEXT:  entry:
 821 ; CHECK-NEXT:    [[SMAX:%.*]] = call i64 @llvm.smax.i64(i64 [[N]], i64 0)
 822 ; CHECK-NEXT:    [[TMP0:%.*]] = udiv i64 [[N]], 42
 823 ; CHECK-NEXT:    [[UMIN:%.*]] = call i64 @llvm.umin.i64(i64 [[SMAX]], i64 [[TMP0]])
 824 ; CHECK-NEXT:    [[TMP1:%.*]] = add nuw nsw i64 [[UMIN]], 1
 825 ; CHECK-NEXT:    [[MIN_ITERS_CHECK:%.*]] = icmp ule i64 [[TMP1]], 4
 826 ; CHECK-NEXT:    br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_PH:%.*]]
 827 ; CHECK:       vector.ph:
 828 ; CHECK-NEXT:    [[N_MOD_VF:%.*]] = urem i64 [[TMP1]], 4
 829 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i64 [[N_MOD_VF]], 0
 830 ; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[TMP2]], i64 4, i64 [[N_MOD_VF]]
 831 ; CHECK-NEXT:    [[N_VEC:%.*]] = sub i64 [[TMP1]], [[TMP3]]
 832 ; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
 833 ; CHECK:       vector.body:
 834 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[LOOP_HEADER]] ]
 835 ; CHECK-NEXT:    [[IV:%.*]] = add i64 [[INDEX]], 0
 836 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[IV]]
 837 ; CHECK-NEXT:    [[TMP6:%.*]] = getelementptr inbounds i32, ptr [[GEP]], i32 0
 838 ; CHECK-NEXT:    store <4 x i32> splat (i32 1), ptr [[TMP6]], align 4
 839 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
 840 ; CHECK-NEXT:    [[TMP7:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
 841 ; CHECK-NEXT:    br i1 [[TMP7]], label [[MIDDLE_BLOCK:%.*]], label [[LOOP_HEADER]], !llvm.loop [[LOOP20:![0-9]+]]
 842 ; CHECK:       middle.block:
 843 ; CHECK-NEXT:    br label [[SCALAR_PH]]
 844 ; CHECK:       scalar.ph:
 845 ; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY:%.*]] ]
 846 ; CHECK-NEXT:    br label [[LOOP_HEADER1:%.*]]
 847 ; CHECK:       loop.header:
 848 ; CHECK-NEXT:    [[IV1:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
 849 ; CHECK-NEXT:    [[GEP1:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[IV1]]
 850 ; CHECK-NEXT:    store i32 1, ptr [[GEP1]], align 4
 851 ; CHECK-NEXT:    [[C_0:%.*]] = icmp slt i64 [[IV1]], [[N]]
 852 ; CHECK-NEXT:    br i1 [[C_0]], label [[LOOP_LATCH]], label [[EXIT:%.*]]
 853 ; CHECK:       loop.latch:
 854 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV1]], 1
 855 ; CHECK-NEXT:    [[D:%.*]] = udiv i64 [[N]], 42
 856 ; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i64 [[IV1]], [[D]]
 857 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_HEADER1]], label [[EXIT]], !llvm.loop [[LOOP21:![0-9]+]]
 858 ; CHECK:       exit:
 859 ; CHECK-NEXT:    [[P:%.*]] = phi i64 [ 1, [[LOOP_HEADER1]] ], [ 0, [[LOOP_LATCH]] ]
 860 ; CHECK-NEXT:    ret i64 [[P]]
 861 ;
 862 entry:
 863   br label %loop.header
 864
 865 loop.header:
 866   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop.latch ]
 867   %gep = getelementptr inbounds i32, ptr %dst, i64 %iv
 868   store i32 1, ptr %gep
 869   %c.0 = icmp slt i64 %iv, %N
 870   br i1 %c.0, label %loop.latch, label %exit
 871
 872 loop.latch:
 873   %iv.next = add i64 %iv, 1
 874   %d = udiv i64 %N, 42
 875   %c.1 = icmp slt i64 %iv, %d
 876   br i1 %c.1, label %loop.header, label %exit
 877
 878 exit:
 879   %p = phi i64 [ 1, %loop.header ], [ 0, %loop.latch]
 880   ret i64 %p
 881 }
 882
 883 define void @single_exit_tc_with_udiv(ptr %dst, i64 %N) {
 884 ; CHECK-LABEL: define void @single_exit_tc_with_udiv(
 885 ; CHECK-SAME: ptr [[DST:%.*]], i64 [[N:%.*]]) {
 886 ; CHECK-NEXT:  entry:
 887 ; CHECK-NEXT:    [[TMP0:%.*]] = udiv i64 42, [[N]]
 888 ; CHECK-NEXT:    [[TMP1:%.*]] = add nuw nsw i64 [[TMP0]], 1
 889 ; CHECK-NEXT:    [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[TMP1]], 4
 890 ; CHECK-NEXT:    br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_PH:%.*]]
 891 ; CHECK:       vector.ph:
 892 ; CHECK-NEXT:    [[N_MOD_VF:%.*]] = urem i64 [[TMP1]], 4
 893 ; CHECK-NEXT:    [[N_VEC:%.*]] = sub i64 [[TMP1]], [[N_MOD_VF]]
 894 ; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]
 895 ; CHECK:       vector.body:
 896 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]
 897 ; CHECK-NEXT:    [[TMP2:%.*]] = add i64 [[INDEX]], 0
 898 ; CHECK-NEXT:    [[TMP3:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP2]]
 899 ; CHECK-NEXT:    [[TMP4:%.*]] = getelementptr inbounds i32, ptr [[TMP3]], i32 0
 900 ; CHECK-NEXT:    store <4 x i32> splat (i32 1), ptr [[TMP4]], align 4
 901 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
 902 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
 903 ; CHECK-NEXT:    br i1 [[TMP5]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP22:![0-9]+]]
 904 ; CHECK:       middle.block:
 905 ; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i64 [[TMP1]], [[N_VEC]]
 906 ; CHECK-NEXT:    br i1 [[CMP_N]], label [[EXIT:%.*]], label [[SCALAR_PH]]
 907 ; CHECK:       scalar.ph:
 908 ; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY:%.*]] ]
 909 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 910 ; CHECK:       loop:
 911 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 912 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[IV]]
 913 ; CHECK-NEXT:    store i32 1, ptr [[GEP]], align 4
 914 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
 915 ; CHECK-NEXT:    [[D:%.*]] = udiv i64 42, [[N]]
 916 ; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i64 [[IV]], [[D]]
 917 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP]], label [[EXIT]], !llvm.loop [[LOOP23:![0-9]+]]
 918 ; CHECK:       exit:
 919 ; CHECK-NEXT:    ret void
 920 ;
 921 entry:
 922   br label %loop
 923
 924 loop:
 925   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
 926   %gep = getelementptr inbounds i32, ptr %dst, i64 %iv
 927   store i32 1, ptr %gep
 928   %iv.next = add i64 %iv, 1
 929   %d = udiv i64 42, %N
 930   %c.1 = icmp slt i64 %iv, %d
 931   br i1 %c.1, label %loop, label %exit
 932
 933 exit:
 934   ret void
 935 }
 936
 937 define i64 @multi_exit_4_exit_count_with_urem_by_value_in_latch(ptr %dst, i64 %N) {
 938 ; CHECK-LABEL: define i64 @multi_exit_4_exit_count_with_urem_by_value_in_latch(
 939 ; CHECK-SAME: ptr [[DST:%.*]], i64 [[N:%.*]]) {
 940 ; CHECK-NEXT:  entry:
 941 ; CHECK-NEXT:    [[TMP12:%.*]] = call i64 @llvm.umax.i64(i64 [[N]], i64 1)
 942 ; CHECK-NEXT:    [[TMP0:%.*]] = udiv i64 42, [[TMP12]]
 943 ; CHECK-NEXT:    [[TMP1:%.*]] = mul nuw i64 [[N]], [[TMP0]]
 944 ; CHECK-NEXT:    [[TMP2:%.*]] = sub i64 42, [[TMP1]]
 945 ; CHECK-NEXT:    [[SMAX1:%.*]] = call i64 @llvm.smax.i64(i64 [[TMP2]], i64 0)
 946 ; CHECK-NEXT:    [[TMP10:%.*]] = freeze i64 [[SMAX1]]
 947 ; CHECK-NEXT:    [[SMAX2:%.*]] = call i64 @llvm.smax.i64(i64 [[N]], i64 0)
 948 ; CHECK-NEXT:    [[UMIN:%.*]] = call i64 @llvm.umin.i64(i64 [[TMP10]], i64 [[SMAX2]])
 949 ; CHECK-NEXT:    [[TMP3:%.*]] = add nuw i64 [[UMIN]], 1
 950 ; CHECK-NEXT:    [[MIN_ITERS_CHECK:%.*]] = icmp ule i64 [[TMP3]], 4
 951 ; CHECK-NEXT:    br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_PH:%.*]]
 952 ; CHECK:       vector.ph:
 953 ; CHECK-NEXT:    [[N_MOD_VF:%.*]] = urem i64 [[TMP3]], 4
 954 ; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i64 [[N_MOD_VF]], 0
 955 ; CHECK-NEXT:    [[TMP5:%.*]] = select i1 [[TMP4]], i64 4, i64 [[N_MOD_VF]]
 956 ; CHECK-NEXT:    [[N_VEC:%.*]] = sub i64 [[TMP3]], [[TMP5]]
 957 ; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]
 958 ; CHECK:       vector.body:
 959 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]
 960 ; CHECK-NEXT:    [[TMP6:%.*]] = add i64 [[INDEX]], 0
 961 ; CHECK-NEXT:    [[TMP7:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP6]]
 962 ; CHECK-NEXT:    [[TMP8:%.*]] = getelementptr inbounds i32, ptr [[TMP7]], i32 0
 963 ; CHECK-NEXT:    store <4 x i32> splat (i32 1), ptr [[TMP8]], align 4
 964 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
 965 ; CHECK-NEXT:    [[TMP9:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
 966 ; CHECK-NEXT:    br i1 [[TMP9]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP24:![0-9]+]]
 967 ; CHECK:       middle.block:
 968 ; CHECK-NEXT:    br label [[SCALAR_PH]]
 969 ; CHECK:       scalar.ph:
 970 ; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY:%.*]] ]
 971 ; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
 972 ; CHECK:       loop.header:
 973 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
 974 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[IV]]
 975 ; CHECK-NEXT:    store i32 1, ptr [[GEP]], align 4
 976 ; CHECK-NEXT:    [[C_0:%.*]] = icmp slt i64 [[IV]], [[N]]
 977 ; CHECK-NEXT:    br i1 [[C_0]], label [[LOOP_LATCH]], label [[EXIT:%.*]]
 978 ; CHECK:       loop.latch:
 979 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
 980 ; CHECK-NEXT:    [[D:%.*]] = urem i64 42, [[N]]
 981 ; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i64 [[IV]], [[D]]
 982 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_HEADER]], label [[EXIT]], !llvm.loop [[LOOP25:![0-9]+]]
 983 ; CHECK:       exit:
 984 ; CHECK-NEXT:    [[P:%.*]] = phi i64 [ 1, [[LOOP_HEADER]] ], [ 0, [[LOOP_LATCH]] ]
 985 ; CHECK-NEXT:    ret i64 [[P]]
 986 ;
 987 entry:
 988   br label %loop.header
 989
 990 loop.header:
 991   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop.latch ]
 992   %gep = getelementptr inbounds i32, ptr %dst, i64 %iv
 993   store i32 1, ptr %gep
 994   %c.0 = icmp slt i64 %iv, %N
 995   br i1 %c.0, label %loop.latch, label %exit
 996
 997 loop.latch:
 998   %iv.next = add i64 %iv, 1
 999   %d = urem i64 42, %N
1000   %c.1 = icmp slt i64 %iv, %d
1001   br i1 %c.1, label %loop.header, label %exit
1002
1003 exit:
1004   %p = phi i64 [ 1, %loop.header ], [ 0, %loop.latch]
1005   ret i64 %p
1006 }
1007
1008 define i64 @multi_exit_4_exit_count_with_urem_by_constant_in_latch(ptr %dst, i64 %N) {
1009 ; CHECK-LABEL: define i64 @multi_exit_4_exit_count_with_urem_by_constant_in_latch(
1010 ; CHECK-SAME: ptr [[DST:%.*]], i64 [[N:%.*]]) {
1011 ; CHECK-NEXT:  entry:
1012 ; CHECK-NEXT:    [[SMAX:%.*]] = call i64 @llvm.smax.i64(i64 [[N]], i64 0)
1013 ; CHECK-NEXT:    [[TMP0:%.*]] = urem i64 [[N]], 42
1014 ; CHECK-NEXT:    [[SMAX1:%.*]] = call i64 @llvm.smax.i64(i64 [[TMP0]], i64 0)
1015 ; CHECK-NEXT:    [[UMIN:%.*]] = call i64 @llvm.umin.i64(i64 [[SMAX]], i64 [[SMAX1]])
1016 ; CHECK-NEXT:    [[TMP1:%.*]] = add nuw i64 [[UMIN]], 1
1017 ; CHECK-NEXT:    [[MIN_ITERS_CHECK:%.*]] = icmp ule i64 [[TMP1]], 4
1018 ; CHECK-NEXT:    br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_PH:%.*]]
1019 ; CHECK:       vector.ph:
1020 ; CHECK-NEXT:    [[N_MOD_VF:%.*]] = urem i64 [[TMP1]], 4
1021 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i64 [[N_MOD_VF]], 0
1022 ; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[TMP2]], i64 4, i64 [[N_MOD_VF]]
1023 ; CHECK-NEXT:    [[N_VEC:%.*]] = sub i64 [[TMP1]], [[TMP3]]
1024 ; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
1025 ; CHECK:       vector.body:
1026 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[LOOP_HEADER]] ]
1027 ; CHECK-NEXT:    [[IV:%.*]] = add i64 [[INDEX]], 0
1028 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[IV]]
1029 ; CHECK-NEXT:    [[TMP6:%.*]] = getelementptr inbounds i32, ptr [[GEP]], i32 0
1030 ; CHECK-NEXT:    store <4 x i32> splat (i32 1), ptr [[TMP6]], align 4
1031 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
1032 ; CHECK-NEXT:    [[TMP7:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
1033 ; CHECK-NEXT:    br i1 [[TMP7]], label [[MIDDLE_BLOCK:%.*]], label [[LOOP_HEADER]], !llvm.loop [[LOOP26:![0-9]+]]
1034 ; CHECK:       middle.block:
1035 ; CHECK-NEXT:    br label [[SCALAR_PH]]
1036 ; CHECK:       scalar.ph:
1037 ; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY:%.*]] ]
1038 ; CHECK-NEXT:    br label [[LOOP_HEADER1:%.*]]
1039 ; CHECK:       loop.header:
1040 ; CHECK-NEXT:    [[IV1:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
1041 ; CHECK-NEXT:    [[GEP1:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[IV1]]
1042 ; CHECK-NEXT:    store i32 1, ptr [[GEP1]], align 4
1043 ; CHECK-NEXT:    [[C_0:%.*]] = icmp slt i64 [[IV1]], [[N]]
1044 ; CHECK-NEXT:    br i1 [[C_0]], label [[LOOP_LATCH]], label [[EXIT:%.*]]
1045 ; CHECK:       loop.latch:
1046 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV1]], 1
1047 ; CHECK-NEXT:    [[D:%.*]] = urem i64 [[N]], 42
1048 ; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i64 [[IV1]], [[D]]
1049 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_HEADER1]], label [[EXIT]], !llvm.loop [[LOOP27:![0-9]+]]
1050 ; CHECK:       exit:
1051 ; CHECK-NEXT:    [[P:%.*]] = phi i64 [ 1, [[LOOP_HEADER1]] ], [ 0, [[LOOP_LATCH]] ]
1052 ; CHECK-NEXT:    ret i64 [[P]]
1053 ;
1054 entry:
1055   br label %loop.header
1056
1057 loop.header:
1058   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop.latch ]
1059   %gep = getelementptr inbounds i32, ptr %dst, i64 %iv
1060   store i32 1, ptr %gep
1061   %c.0 = icmp slt i64 %iv, %N
1062   br i1 %c.0, label %loop.latch, label %exit
1063
1064 loop.latch:
1065   %iv.next = add i64 %iv, 1
1066   %d = urem i64 %N, 42
1067   %c.1 = icmp slt i64 %iv, %d
1068   br i1 %c.1, label %loop.header, label %exit
1069
1070 exit:
1071   %p = phi i64 [ 1, %loop.header ], [ 0, %loop.latch]
1072   ret i64 %p
1073 }
1074
1075 define i64 @multi_exit_4_exit_count_with_srem_by_value_in_latch(ptr %dst, i64 %N) {
1076 ; CHECK-LABEL: define i64 @multi_exit_4_exit_count_with_srem_by_value_in_latch(
1077 ; CHECK-SAME: ptr [[DST:%.*]], i64 [[N:%.*]]) {
1078 ; CHECK-NEXT:  entry:
1079 ; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
1080 ; CHECK:       loop.header:
1081 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
1082 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[IV]]
1083 ; CHECK-NEXT:    store i32 1, ptr [[GEP]], align 4
1084 ; CHECK-NEXT:    [[C_0:%.*]] = icmp slt i64 [[IV]], [[N]]
1085 ; CHECK-NEXT:    br i1 [[C_0]], label [[LOOP_LATCH]], label [[EXIT:%.*]]
1086 ; CHECK:       loop.latch:
1087 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
1088 ; CHECK-NEXT:    [[D:%.*]] = srem i64 42, [[N]]
1089 ; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i64 [[IV]], [[D]]
1090 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_HEADER]], label [[EXIT]]
1091 ; CHECK:       exit:
1092 ; CHECK-NEXT:    [[P:%.*]] = phi i64 [ 1, [[LOOP_HEADER]] ], [ 0, [[LOOP_LATCH]] ]
1093 ; CHECK-NEXT:    ret i64 [[P]]
1094 ;
1095 entry:
1096   br label %loop.header
1097
1098 loop.header:
1099   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop.latch ]
1100   %gep = getelementptr inbounds i32, ptr %dst, i64 %iv
1101   store i32 1, ptr %gep
1102   %c.0 = icmp slt i64 %iv, %N
1103   br i1 %c.0, label %loop.latch, label %exit
1104
1105 loop.latch:
1106   %iv.next = add i64 %iv, 1
1107   %d = srem i64 42, %N
1108   %c.1 = icmp slt i64 %iv, %d
1109   br i1 %c.1, label %loop.header, label %exit
1110
1111 exit:
1112   %p = phi i64 [ 1, %loop.header ], [ 0, %loop.latch]
1113   ret i64 %p
1114 }
1115
1116 define i64 @multi_exit_4_exit_count_with_sdiv_by_value_in_latch(ptr %dst, i64 %N) {
1117 ; CHECK-LABEL: define i64 @multi_exit_4_exit_count_with_sdiv_by_value_in_latch(
1118 ; CHECK-SAME: ptr [[DST:%.*]], i64 [[N:%.*]]) {
1119 ; CHECK-NEXT:  entry:
1120 ; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
1121 ; CHECK:       loop.header:
1122 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
1123 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[IV]]
1124 ; CHECK-NEXT:    store i32 1, ptr [[GEP]], align 4
1125 ; CHECK-NEXT:    [[C_0:%.*]] = icmp slt i64 [[IV]], [[N]]
1126 ; CHECK-NEXT:    br i1 [[C_0]], label [[LOOP_LATCH]], label [[EXIT:%.*]]
1127 ; CHECK:       loop.latch:
1128 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
1129 ; CHECK-NEXT:    [[D:%.*]] = sdiv i64 42, [[N]]
1130 ; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i64 [[IV]], [[D]]
1131 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_HEADER]], label [[EXIT]]
1132 ; CHECK:       exit:
1133 ; CHECK-NEXT:    [[P:%.*]] = phi i64 [ 1, [[LOOP_HEADER]] ], [ 0, [[LOOP_LATCH]] ]
1134 ; CHECK-NEXT:    ret i64 [[P]]
1135 ;
1136 entry:
1137   br label %loop.header
1138
1139 loop.header:
1140   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop.latch ]
1141   %gep = getelementptr inbounds i32, ptr %dst, i64 %iv
1142   store i32 1, ptr %gep
1143   %c.0 = icmp slt i64 %iv, %N
1144   br i1 %c.0, label %loop.latch, label %exit
1145
1146 loop.latch:
1147   %iv.next = add i64 %iv, 1
1148   %d = sdiv i64 42, %N
1149   %c.1 = icmp slt i64 %iv, %d
1150   br i1 %c.1, label %loop.header, label %exit
1151
1152 exit:
1153   %p = phi i64 [ 1, %loop.header ], [ 0, %loop.latch]
1154   ret i64 %p
1155 }
1156
1157 define i64 @multi_exit_4_exit_count_with_udiv_by_value_in_latch1(ptr %dst, i64 %N) {
1158 ; CHECK-LABEL: define i64 @multi_exit_4_exit_count_with_udiv_by_value_in_latch1(
1159 ; CHECK-SAME: ptr [[DST:%.*]], i64 [[N:%.*]]) {
1160 ; CHECK-NEXT:  entry:
1161 ; CHECK-NEXT:    [[TMP8:%.*]] = call i64 @llvm.umax.i64(i64 [[N]], i64 1)
1162 ; CHECK-NEXT:    [[TMP9:%.*]] = udiv i64 42, [[TMP8]]
1163 ; CHECK-NEXT:    [[TMP10:%.*]] = freeze i64 [[TMP9]]
1164 ; CHECK-NEXT:    [[SMAX:%.*]] = call i64 @llvm.smax.i64(i64 [[N]], i64 0)
1165 ; CHECK-NEXT:    [[UMIN:%.*]] = call i64 @llvm.umin.i64(i64 [[TMP10]], i64 [[SMAX]])
1166 ; CHECK-NEXT:    [[TMP1:%.*]] = add nuw nsw i64 [[UMIN]], 1
1167 ; CHECK-NEXT:    [[MIN_ITERS_CHECK:%.*]] = icmp ule i64 [[TMP1]], 4
1168 ; CHECK-NEXT:    br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_PH:%.*]]
1169 ; CHECK:       vector.ph:
1170 ; CHECK-NEXT:    [[N_MOD_VF:%.*]] = urem i64 [[TMP1]], 4
1171 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i64 [[N_MOD_VF]], 0
1172 ; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[TMP2]], i64 4, i64 [[N_MOD_VF]]
1173 ; CHECK-NEXT:    [[N_VEC:%.*]] = sub i64 [[TMP1]], [[TMP3]]
1174 ; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]
1175 ; CHECK:       vector.body:
1176 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]
1177 ; CHECK-NEXT:    [[TMP4:%.*]] = add i64 [[INDEX]], 0
1178 ; CHECK-NEXT:    [[TMP5:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP4]]
1179 ; CHECK-NEXT:    [[TMP6:%.*]] = getelementptr inbounds i32, ptr [[TMP5]], i32 0
1180 ; CHECK-NEXT:    store <4 x i32> splat (i32 1), ptr [[TMP6]], align 4
1181 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
1182 ; CHECK-NEXT:    [[TMP7:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
1183 ; CHECK-NEXT:    br i1 [[TMP7]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP28:![0-9]+]]
1184 ; CHECK:       middle.block:
1185 ; CHECK-NEXT:    br label [[SCALAR_PH]]
1186 ; CHECK:       scalar.ph:
1187 ; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY:%.*]] ]
1188 ; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
1189 ; CHECK:       loop.header:
1190 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
1191 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[IV]]
1192 ; CHECK-NEXT:    store i32 1, ptr [[GEP]], align 4
1193 ; CHECK-NEXT:    [[C_0:%.*]] = icmp slt i64 [[IV]], [[N]]
1194 ; CHECK-NEXT:    br i1 [[C_0]], label [[LOOP_LATCH]], label [[EXIT:%.*]]
1195 ; CHECK:       loop.latch:
1196 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
1197 ; CHECK-NEXT:    [[D:%.*]] = udiv i64 42, [[N]]
1198 ; CHECK-NEXT:    [[X:%.*]] = sub i64 100, [[D]]
1199 ; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i64 [[IV]], [[D]]
1200 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_HEADER]], label [[EXIT]], !llvm.loop [[LOOP29:![0-9]+]]
1201 ; CHECK:       exit:
1202 ; CHECK-NEXT:    [[P:%.*]] = phi i64 [ 1, [[LOOP_HEADER]] ], [ 0, [[LOOP_LATCH]] ]
1203 ; CHECK-NEXT:    ret i64 [[P]]
1204 ;
1205 entry:
1206   br label %loop.header
1207
1208 loop.header:
1209   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop.latch ]
1210   %gep = getelementptr inbounds i32, ptr %dst, i64 %iv
1211   store i32 1, ptr %gep
1212   %c.0 = icmp slt i64 %iv, %N
1213   br i1 %c.0, label %loop.latch, label %exit
1214
1215 loop.latch:
1216   %iv.next = add i64 %iv, 1
1217   %d = udiv i64 42, %N
1218   %x = sub i64 100, %d
1219   %c.1 = icmp slt i64 %iv, %d
1220   br i1 %c.1, label %loop.header, label %exit
1221
1222 exit:
1223   %p = phi i64 [ 1, %loop.header ], [ 0, %loop.latch]
1224   ret i64 %p
1225 }
1226
1227 define i64 @multi_exit_exit_count_with_udiv_by_0_in_latch(ptr %dst, i64 %N) {
1228 ; CHECK-LABEL: define i64 @multi_exit_exit_count_with_udiv_by_0_in_latch(
1229 ; CHECK-SAME: ptr [[DST:%.*]], i64 [[N:%.*]]) {
1230 ; CHECK-NEXT:  entry:
1231 ; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
1232 ; CHECK:       loop.header:
1233 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
1234 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[IV]]
1235 ; CHECK-NEXT:    store i32 1, ptr [[GEP]], align 4
1236 ; CHECK-NEXT:    [[C_0:%.*]] = icmp slt i64 [[IV]], [[N]]
1237 ; CHECK-NEXT:    br i1 [[C_0]], label [[LOOP_LATCH]], label [[EXIT:%.*]]
1238 ; CHECK:       loop.latch:
1239 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
1240 ; CHECK-NEXT:    [[D:%.*]] = udiv i64 42, 0
1241 ; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i64 [[IV]], [[D]]
1242 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_HEADER]], label [[EXIT]]
1243 ; CHECK:       exit:
1244 ; CHECK-NEXT:    [[P:%.*]] = phi i64 [ 1, [[LOOP_HEADER]] ], [ 0, [[LOOP_LATCH]] ]
1245 ; CHECK-NEXT:    ret i64 [[P]]
1246 ;
1247 entry:
1248   br label %loop.header
1249
1250 loop.header:
1251   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop.latch ]
1252   %gep = getelementptr inbounds i32, ptr %dst, i64 %iv
1253   store i32 1, ptr %gep
1254   %c.0 = icmp slt i64 %iv, %N
1255   br i1 %c.0, label %loop.latch, label %exit
1256
1257 loop.latch:
1258   %iv.next = add i64 %iv, 1
1259   %d = udiv i64 42, 0
1260   %c.1 = icmp slt i64 %iv, %d
1261   br i1 %c.1, label %loop.header, label %exit
1262
1263 exit:
1264   %p = phi i64 [ 1, %loop.header ], [ 0, %loop.latch]
1265   ret i64 %p
1266 }
1267
1268 define i64 @multi_exit_count_with_udiv_by_value_in_latch_different_bounds_divisor_non_zero_may_be_poison(ptr %dst, i64 %N, i64 %M) {
1269 ; CHECK-LABEL: define i64 @multi_exit_count_with_udiv_by_value_in_latch_different_bounds_divisor_non_zero_may_be_poison(
1270 ; CHECK-SAME: ptr [[DST:%.*]], i64 [[N:%.*]], i64 [[M:%.*]]) {
1271 ; CHECK-NEXT:  entry:
1272 ; CHECK-NEXT:    [[M_1:%.*]] = call i64 @llvm.umax.i64(i64 [[M]], i64 1)
1273 ; CHECK-NEXT:    [[TMP9:%.*]] = freeze i64 [[M_1]]
1274 ; CHECK-NEXT:    [[TMP10:%.*]] = call i64 @llvm.umax.i64(i64 [[TMP9]], i64 1)
1275 ; CHECK-NEXT:    [[TMP0:%.*]] = udiv i64 42, [[TMP10]]
1276 ; CHECK-NEXT:    [[TMP1:%.*]] = freeze i64 [[TMP0]]
1277 ; CHECK-NEXT:    [[SMAX:%.*]] = call i64 @llvm.smax.i64(i64 [[N]], i64 0)
1278 ; CHECK-NEXT:    [[UMIN:%.*]] = call i64 @llvm.umin.i64(i64 [[TMP1]], i64 [[SMAX]])
1279 ; CHECK-NEXT:    [[TMP2:%.*]] = add nuw nsw i64 [[UMIN]], 1
1280 ; CHECK-NEXT:    [[MIN_ITERS_CHECK:%.*]] = icmp ule i64 [[TMP2]], 4
1281 ; CHECK-NEXT:    br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_PH:%.*]]
1282 ; CHECK:       vector.ph:
1283 ; CHECK-NEXT:    [[N_MOD_VF:%.*]] = urem i64 [[TMP2]], 4
1284 ; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i64 [[N_MOD_VF]], 0
1285 ; CHECK-NEXT:    [[TMP4:%.*]] = select i1 [[TMP3]], i64 4, i64 [[N_MOD_VF]]
1286 ; CHECK-NEXT:    [[N_VEC:%.*]] = sub i64 [[TMP2]], [[TMP4]]
1287 ; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]
1288 ; CHECK:       vector.body:
1289 ; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]
1290 ; CHECK-NEXT:    [[TMP5:%.*]] = add i64 [[INDEX]], 0
1291 ; CHECK-NEXT:    [[TMP6:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP5]]
1292 ; CHECK-NEXT:    [[TMP7:%.*]] = getelementptr inbounds i32, ptr [[TMP6]], i32 0
1293 ; CHECK-NEXT:    store <4 x i32> splat (i32 1), ptr [[TMP7]], align 4
1294 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
1295 ; CHECK-NEXT:    [[TMP8:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
1296 ; CHECK-NEXT:    br i1 [[TMP8]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP30:![0-9]+]]
1297 ; CHECK:       middle.block:
1298 ; CHECK-NEXT:    br label [[SCALAR_PH]]
1299 ; CHECK:       scalar.ph:
1300 ; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY:%.*]] ]
1301 ; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
1302 ; CHECK:       loop.header:
1303 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
1304 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[IV]]
1305 ; CHECK-NEXT:    store i32 1, ptr [[GEP]], align 4
1306 ; CHECK-NEXT:    [[C_0:%.*]] = icmp slt i64 [[IV]], [[N]]
1307 ; CHECK-NEXT:    br i1 [[C_0]], label [[LOOP_LATCH]], label [[EXIT:%.*]]
1308 ; CHECK:       loop.latch:
1309 ; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
1310 ; CHECK-NEXT:    [[D:%.*]] = udiv i64 42, [[M_1]]
1311 ; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i64 [[IV]], [[D]]
1312 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_HEADER]], label [[EXIT]], !llvm.loop [[LOOP31:![0-9]+]]
1313 ; CHECK:       exit:
1314 ; CHECK-NEXT:    [[P:%.*]] = phi i64 [ 1, [[LOOP_HEADER]] ], [ 0, [[LOOP_LATCH]] ]
1315 ; CHECK-NEXT:    ret i64 [[P]]
1316 ;
1317 entry:
1318   %M.1 = call i64 @llvm.umax.i64(i64 %M, i64 1)
1319   br label %loop.header
1320
1321 loop.header:
1322   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop.latch ]
1323   %gep = getelementptr inbounds i32, ptr %dst, i64 %iv
1324   store i32 1, ptr %gep
1325   %c.0 = icmp slt i64 %iv, %N
1326   br i1 %c.0, label %loop.latch, label %exit
1327
1328 loop.latch:
1329   %iv.next = add i64 %iv, 1
1330   %d = udiv i64 42, %M.1
1331   %c.1 = icmp slt i64 %iv, %d
1332   br i1 %c.1, label %loop.header, label %exit
1333
1334 exit:
1335   %p = phi i64 [ 1, %loop.header ], [ 0, %loop.latch]
1336   ret i64 %p
1337 }
1338
1339 declare i64 @llvm.umax.i64(i64, i64)
1340
1341
1342 ;.
1343 ; CHECK: [[LOOP0]] = distinct !{[[LOOP0]], [[META1:![0-9]+]], [[META2:![0-9]+]]}
1344 ; CHECK: [[META1]] = !{!"llvm.loop.isvectorized", i32 1}
1345 ; CHECK: [[META2]] = !{!"llvm.loop.unroll.runtime.disable"}
1346 ; CHECK: [[LOOP3]] = distinct !{[[LOOP3]], [[META2]], [[META1]]}
1347 ; CHECK: [[LOOP4]] = distinct !{[[LOOP4]], [[META1]], [[META2]]}
1348 ; CHECK: [[LOOP5]] = distinct !{[[LOOP5]], [[META2]], [[META1]]}
1349 ; CHECK: [[LOOP6]] = distinct !{[[LOOP6]], [[META1]], [[META2]]}
1350 ; CHECK: [[LOOP7]] = distinct !{[[LOOP7]], [[META2]], [[META1]]}
1351 ; CHECK: [[LOOP8]] = distinct !{[[LOOP8]], [[META1]], [[META2]]}
1352 ; CHECK: [[LOOP9]] = distinct !{[[LOOP9]], [[META2]], [[META1]]}
1353 ; CHECK: [[LOOP10]] = distinct !{[[LOOP10]], [[META1]], [[META2]]}
1354 ; CHECK: [[LOOP11]] = distinct !{[[LOOP11]], [[META2]], [[META1]]}
1355 ; CHECK: [[LOOP12]] = distinct !{[[LOOP12]], [[META1]], [[META2]]}
1356 ; CHECK: [[LOOP13]] = distinct !{[[LOOP13]], [[META2]], [[META1]]}
1357 ; CHECK: [[LOOP14]] = distinct !{[[LOOP14]], [[META1]], [[META2]]}
1358 ; CHECK: [[LOOP15]] = distinct !{[[LOOP15]], [[META2]], [[META1]]}
1359 ; CHECK: [[LOOP16]] = distinct !{[[LOOP16]], [[META1]], [[META2]]}
1360 ; CHECK: [[LOOP17]] = distinct !{[[LOOP17]], [[META2]], [[META1]]}
1361 ; CHECK: [[LOOP18]] = distinct !{[[LOOP18]], [[META1]], [[META2]]}
1362 ; CHECK: [[LOOP19]] = distinct !{[[LOOP19]], [[META2]], [[META1]]}
1363 ; CHECK: [[LOOP20]] = distinct !{[[LOOP20]], [[META1]], [[META2]]}
1364 ; CHECK: [[LOOP21]] = distinct !{[[LOOP21]], [[META2]], [[META1]]}
1365 ; CHECK: [[LOOP22]] = distinct !{[[LOOP22]], [[META1]], [[META2]]}
1366 ; CHECK: [[LOOP23]] = distinct !{[[LOOP23]], [[META2]], [[META1]]}
1367 ; CHECK: [[LOOP24]] = distinct !{[[LOOP24]], [[META1]], [[META2]]}
1368 ; CHECK: [[LOOP25]] = distinct !{[[LOOP25]], [[META2]], [[META1]]}
1369 ; CHECK: [[LOOP26]] = distinct !{[[LOOP26]], [[META1]], [[META2]]}
1370 ; CHECK: [[LOOP27]] = distinct !{[[LOOP27]], [[META2]], [[META1]]}
1371 ; CHECK: [[LOOP28]] = distinct !{[[LOOP28]], [[META1]], [[META2]]}
1372 ; CHECK: [[LOOP29]] = distinct !{[[LOOP29]], [[META2]], [[META1]]}
1373 ; CHECK: [[LOOP30]] = distinct !{[[LOOP30]], [[META1]], [[META2]]}
1374 ; CHECK: [[LOOP31]] = distinct !{[[LOOP31]], [[META2]], [[META1]]}
1375 ;.