llvm/test/Analysis/ScalarEvolution/trip-count-negative-stride.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
   2 ; RUN: opt < %s -disable-output "-passes=print<scalar-evolution>"  -scalar-evolution-classify-expressions=0 2>&1 | FileCheck %s
   3
   4 ; A collection of tests which exercise SCEV's ability to compute trip counts
   5 ; for negative steps.
   6
   7 ; Unsigned Comparisons
   8 ; --------------------
   9
  10 ; Case where we wrap the induction variable (without generating poison), and
  11 ; thus can't currently compute a trip count.
  12 define void @ult_wrap() {
  13 ; CHECK-LABEL: 'ult_wrap'
  14 ; CHECK-NEXT:  Determining loop execution counts for: @ult_wrap
  15 ; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
  16 ; CHECK-NEXT:  Loop %for.body: Unpredictable constant max backedge-taken count.
  17 ; CHECK-NEXT:  Loop %for.body: Unpredictable symbolic max backedge-taken count.
  18 ;
  19 entry:
  20   br label %for.body
  21
  22 for.body:                                         ; preds = %entry, %for.body
  23   %i.05 = phi i8 [ %add, %for.body ], [ 0, %entry ]
  24   %add = add i8 %i.05, 254
  25   %cmp = icmp ult i8 %add, 255
  26   br i1 %cmp, label %for.body, label %for.end
  27
  28 for.end:                                          ; preds = %for.body, %entry
  29   ret void
  30 }
  31
  32 ; This IV cycles between 0, and 128, never causing the loop to exit
  33 ; (This is well defined.)
  34 define void @ult_infinite() {
  35 ; CHECK-LABEL: 'ult_infinite'
  36 ; CHECK-NEXT:  Determining loop execution counts for: @ult_infinite
  37 ; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
  38 ; CHECK-NEXT:  Loop %for.body: Unpredictable constant max backedge-taken count.
  39 ; CHECK-NEXT:  Loop %for.body: Unpredictable symbolic max backedge-taken count.
  40 ;
  41 entry:
  42   br label %for.body
  43
  44 for.body:                                         ; preds = %entry, %for.body
  45   %i.05 = phi i8 [ %add, %for.body ], [ 0, %entry ]
  46   %add = add i8 %i.05, 128
  47   %cmp = icmp ult i8 %add, 255
  48   br i1 %cmp, label %for.body, label %for.end
  49
  50 for.end:                                          ; preds = %for.body, %entry
  51   ret void
  52 }
  53
  54 ; Same as ult_infinite, except that the loop is ill defined due to the
  55 ; must progress attribute
  56 define void @ult_infinite_ub() mustprogress {
  57 ; CHECK-LABEL: 'ult_infinite_ub'
  58 ; CHECK-NEXT:  Determining loop execution counts for: @ult_infinite_ub
  59 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is i8 1
  60 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is i8 1
  61 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is i8 1
  62 ; CHECK-NEXT:  Loop %for.body: Trip multiple is 2
  63 ;
  64 entry:
  65   br label %for.body
  66
  67 for.body:                                         ; preds = %entry, %for.body
  68   %i.05 = phi i8 [ %add, %for.body ], [ 0, %entry ]
  69   %add = add i8 %i.05, 128
  70   %cmp = icmp ult i8 %add, 255
  71   br i1 %cmp, label %for.body, label %for.end
  72
  73 for.end:                                          ; preds = %for.body, %entry
  74   ret void
  75 }
  76
  77
  78 ; Backedge is not taken
  79 define void @ult_129_not_taken() {
  80 ; CHECK-LABEL: 'ult_129_not_taken'
  81 ; CHECK-NEXT:  Determining loop execution counts for: @ult_129_not_taken
  82 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is i8 0
  83 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is i8 0
  84 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is i8 0
  85 ; CHECK-NEXT:  Loop %for.body: Trip multiple is 1
  86 ;
  87 entry:
  88   br label %for.body
  89
  90 for.body:                                         ; preds = %entry, %for.body
  91   %i.05 = phi i8 [ %add, %for.body ], [ 0, %entry ]
  92   %add = add i8 %i.05, 129
  93   %cmp = icmp ult i8 %add, 128
  94   br i1 %cmp, label %for.body, label %for.end
  95
  96 for.end:                                          ; preds = %for.body, %entry
  97   ret void
  98 }
  99
 100 define void @ult_129_unknown_start(i8 %start) mustprogress {
 101 ; CHECK-LABEL: 'ult_129_unknown_start'
 102 ; CHECK-NEXT:  Determining loop execution counts for: @ult_129_unknown_start
 103 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is i8 0
 104 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is i8 0
 105 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is i8 0
 106 ; CHECK-NEXT:  Loop %for.body: Trip multiple is 1
 107 ;
 108 entry:
 109   br label %for.body
 110
 111 for.body:                                         ; preds = %entry, %for.body
 112   %i.05 = phi i8 [ %add, %for.body ], [ %start, %entry ]
 113   %add = add nuw i8 %i.05, 129
 114   %cmp = icmp ult i8 %add, 128
 115   br i1 %cmp, label %for.body, label %for.end
 116
 117 for.end:                                          ; preds = %for.body, %entry
 118   ret void
 119 }
 120
 121
 122 ; A case with a non-constant stride where the backedge is not taken
 123 define void @ult_not_taken(i8 %step) {
 124 ; CHECK-LABEL: 'ult_not_taken'
 125 ; CHECK-NEXT:  Determining loop execution counts for: @ult_not_taken
 126 ; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
 127 ; CHECK-NEXT:  Loop %for.body: Unpredictable constant max backedge-taken count.
 128 ; CHECK-NEXT:  Loop %for.body: Unpredictable symbolic max backedge-taken count.
 129 ;
 130 entry:
 131   %assume = icmp ult i8 128, %step
 132   call void @llvm.assume(i1 %assume)
 133   br label %for.body
 134
 135 for.body:                                         ; preds = %entry, %for.body
 136   %i.05 = phi i8 [ %add, %for.body ], [ 0, %entry ]
 137   %add = add i8 %i.05, %step
 138   %cmp = icmp ult i8 %add, 128
 139   br i1 %cmp, label %for.body, label %for.end
 140
 141 for.end:                                          ; preds = %for.body, %entry
 142   ret void
 143 }
 144
 145
 146
 147 ; IV does wrap, and thus causes us to branch on poison.  This loop is
 148 ; ill defined.
 149 define void @ult_ub1() {
 150 ; CHECK-LABEL: 'ult_ub1'
 151 ; CHECK-NEXT:  Determining loop execution counts for: @ult_ub1
 152 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is i32 2
 153 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is i32 2
 154 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is i32 2
 155 ; CHECK-NEXT:  Loop %for.body: Trip multiple is 3
 156 ;
 157 entry:
 158   br label %for.body
 159
 160 for.body:                                         ; preds = %entry, %for.body
 161   %i.05 = phi i8 [ %add, %for.body ], [ 2, %entry ]
 162   %add = add nuw i8 %i.05, 255
 163   %cmp = icmp ult i8 %add, 128
 164   br i1 %cmp, label %for.body, label %for.end
 165
 166 for.end:                                          ; preds = %for.body, %entry
 167   ret void
 168 }
 169
 170 ; This loop is ill defined because we violate the nsw flag on the first
 171 ; iteration.
 172 define void @ult_ub2() {
 173 ; CHECK-LABEL: 'ult_ub2'
 174 ; CHECK-NEXT:  Determining loop execution counts for: @ult_ub2
 175 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is i8 0
 176 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is i8 0
 177 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is i8 0
 178 ; CHECK-NEXT:  Loop %for.body: Trip multiple is 1
 179 ;
 180 entry:
 181   br label %for.body
 182
 183 for.body:                                         ; preds = %entry, %for.body
 184   %i.05 = phi i8 [ %add, %for.body ], [ 0, %entry ]
 185   %add = add nsw nuw i8 %i.05, 129
 186   %cmp = icmp ult i8 %add, 128
 187   br i1 %cmp, label %for.body, label %for.end
 188
 189 for.end:                                          ; preds = %for.body, %entry
 190   ret void
 191 }
 192
 193 ; Large stride, poison produced for %add on second iteration, but not
 194 ; branched on.
 195 define void @ult_129_preinc() {
 196 ; CHECK-LABEL: 'ult_129_preinc'
 197 ; CHECK-NEXT:  Determining loop execution counts for: @ult_129_preinc
 198 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is i8 1
 199 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is i8 1
 200 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is i8 1
 201 ; CHECK-NEXT:  Loop %for.body: Trip multiple is 2
 202 ;
 203 entry:
 204   br label %for.body
 205
 206 for.body:                                         ; preds = %entry, %for.body
 207   %i.05 = phi i8 [ %add, %for.body ], [ 0, %entry ]
 208   %add = add nuw i8 %i.05, 129
 209   %cmp = icmp ult i8 %i.05, 128
 210   br i1 %cmp, label %for.body, label %for.end
 211
 212 for.end:                                          ; preds = %for.body, %entry
 213   ret void
 214 }
 215
 216 define void @ult_preinc(i8 %step) {
 217 ; CHECK-LABEL: 'ult_preinc'
 218 ; CHECK-NEXT:  Determining loop execution counts for: @ult_preinc
 219 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is i8 1
 220 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is i8 1
 221 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is i8 1
 222 ; CHECK-NEXT:  Loop %for.body: Trip multiple is 2
 223 ;
 224 entry:
 225   %assume = icmp ult i8 128, %step
 226   call void @llvm.assume(i1 %assume)
 227   br label %for.body
 228
 229 for.body:                                         ; preds = %entry, %for.body
 230   %i.05 = phi i8 [ %add, %for.body ], [ 0, %entry ]
 231   %add = add nuw i8 %i.05, 129
 232   %cmp = icmp ult i8 %i.05, 128
 233   br i1 %cmp, label %for.body, label %for.end
 234
 235 for.end:                                          ; preds = %for.body, %entry
 236   ret void
 237 }
 238
 239 define void @ult_129_varying_rhs(ptr %n_p) {
 240 ; CHECK-LABEL: 'ult_129_varying_rhs'
 241 ; CHECK-NEXT:  Determining loop execution counts for: @ult_129_varying_rhs
 242 ; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
 243 ; CHECK-NEXT:  Loop %for.body: Unpredictable constant max backedge-taken count.
 244 ; CHECK-NEXT:  Loop %for.body: Unpredictable symbolic max backedge-taken count.
 245 ;
 246 entry:
 247   br label %for.body
 248
 249 for.body:                                         ; preds = %entry, %for.body
 250   %i.05 = phi i8 [ %add, %for.body ], [ 0, %entry ]
 251   %add = add nuw i8 %i.05, 129
 252   %n = load i8, ptr %n_p
 253   %cmp = icmp ult i8 %add, %n
 254   br i1 %cmp, label %for.body, label %for.end
 255
 256 for.end:                                          ; preds = %for.body, %entry
 257   ret void
 258 }
 259
 260 define void @ult_symbolic_varying_rhs(ptr %n_p, i8 %step) {
 261 ; CHECK-LABEL: 'ult_symbolic_varying_rhs'
 262 ; CHECK-NEXT:  Determining loop execution counts for: @ult_symbolic_varying_rhs
 263 ; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
 264 ; CHECK-NEXT:  Loop %for.body: Unpredictable constant max backedge-taken count.
 265 ; CHECK-NEXT:  Loop %for.body: Unpredictable symbolic max backedge-taken count.
 266 ;
 267 entry:
 268   %assume = icmp ult i8 128, %step
 269   call void @llvm.assume(i1 %assume)
 270   br label %for.body
 271
 272 for.body:                                         ; preds = %entry, %for.body
 273   %i.05 = phi i8 [ %add, %for.body ], [ 0, %entry ]
 274   %add = add nuw i8 %i.05, %step
 275   %n = load i8, ptr %n_p
 276   %cmp = icmp ult i8 %add, %n
 277   br i1 %cmp, label %for.body, label %for.end
 278
 279 for.end:                                          ; preds = %for.body, %entry
 280   ret void
 281 }
 282
 283
 284 ; Signed Comparisons
 285 ; ------------------
 286
 287 ; Case where we wrap the induction variable (without generating poison), and
 288 ; thus can't currently compute a trip count.
 289 define void @slt_wrap() {
 290 ; CHECK-LABEL: 'slt_wrap'
 291 ; CHECK-NEXT:  Determining loop execution counts for: @slt_wrap
 292 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is i8 63
 293 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is i8 63
 294 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is i8 63
 295 ; CHECK-NEXT:  Loop %for.body: Trip multiple is 64
 296 ;
 297 entry:
 298   br label %for.body
 299
 300 for.body:                                         ; preds = %entry, %for.body
 301   %i.05 = phi i8 [ %add, %for.body ], [ 255, %entry ]
 302   %add = add i8 %i.05, 254
 303   %cmp = icmp slt i8 %add, 127
 304   br i1 %cmp, label %for.body, label %for.end
 305
 306 for.end:                                          ; preds = %for.body, %entry
 307   ret void
 308 }
 309
 310 ; This IV cycles between 0, and int_min (128), never causing the loop to exit
 311 ; (This is well defined.)
 312 define void @slt_infinite() {
 313 ; CHECK-LABEL: 'slt_infinite'
 314 ; CHECK-NEXT:  Determining loop execution counts for: @slt_infinite
 315 ; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
 316 ; CHECK-NEXT:  Loop %for.body: Unpredictable constant max backedge-taken count.
 317 ; CHECK-NEXT:  Loop %for.body: Unpredictable symbolic max backedge-taken count.
 318 ;
 319 entry:
 320   br label %for.body
 321
 322 for.body:                                         ; preds = %entry, %for.body
 323   %i.05 = phi i8 [ %add, %for.body ], [ 0, %entry ]
 324   %add = add i8 %i.05, 128
 325   %cmp = icmp slt i8 %add, 127
 326   br i1 %cmp, label %for.body, label %for.end
 327
 328 for.end:                                          ; preds = %for.body, %entry
 329   ret void
 330 }
 331
 332 ; Same as slt_infinite, except that the loop is ill defined due to the
 333 ; must progress attribute
 334 define void @slt_infinite_ub() mustprogress {
 335 ; CHECK-LABEL: 'slt_infinite_ub'
 336 ; CHECK-NEXT:  Determining loop execution counts for: @slt_infinite_ub
 337 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is i8 0
 338 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is i8 0
 339 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is i8 0
 340 ; CHECK-NEXT:  Loop %for.body: Trip multiple is 1
 341 ;
 342 entry:
 343   br label %for.body
 344
 345 for.body:                                         ; preds = %entry, %for.body
 346   %i.05 = phi i8 [ %add, %for.body ], [ 0, %entry ]
 347   %add = add i8 %i.05, 128
 348   %cmp = icmp slt i8 %add, 127
 349   br i1 %cmp, label %for.body, label %for.end
 350
 351 for.end:                                          ; preds = %for.body, %entry
 352   ret void
 353 }
 354
 355
 356 ; Backedge is not taken
 357 define void @slt_129_not_taken() {
 358 ; CHECK-LABEL: 'slt_129_not_taken'
 359 ; CHECK-NEXT:  Determining loop execution counts for: @slt_129_not_taken
 360 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is i8 0
 361 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is i8 0
 362 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is i8 0
 363 ; CHECK-NEXT:  Loop %for.body: Trip multiple is 1
 364 ;
 365 entry:
 366   br label %for.body
 367
 368 for.body:                                         ; preds = %entry, %for.body
 369   %i.05 = phi i8 [ %add, %for.body ], [ -128, %entry ]
 370   %add = add i8 %i.05, 129
 371   %cmp = icmp slt i8 %add, 0
 372   br i1 %cmp, label %for.body, label %for.end
 373
 374 for.end:                                          ; preds = %for.body, %entry
 375   ret void
 376 }
 377
 378 ; A case with a non-constant stride where the backedge is not taken
 379 define void @slt_not_taken(i8 %step) {
 380 ; CHECK-LABEL: 'slt_not_taken'
 381 ; CHECK-NEXT:  Determining loop execution counts for: @slt_not_taken
 382 ; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
 383 ; CHECK-NEXT:  Loop %for.body: Unpredictable constant max backedge-taken count.
 384 ; CHECK-NEXT:  Loop %for.body: Unpredictable symbolic max backedge-taken count.
 385 ;
 386 entry:
 387   %assume = icmp ult i8 128, %step
 388   call void @llvm.assume(i1 %assume)
 389   br label %for.body
 390
 391 for.body:                                         ; preds = %entry, %for.body
 392   %i.05 = phi i8 [ %add, %for.body ], [ -128, %entry ]
 393   %add = add i8 %i.05, %step
 394   %cmp = icmp slt i8 %add, 0
 395   br i1 %cmp, label %for.body, label %for.end
 396
 397 for.end:                                          ; preds = %for.body, %entry
 398   ret void
 399 }
 400
 401 define void @slt_129_unknown_start(i8 %start) mustprogress {
 402 ; CHECK-LABEL: 'slt_129_unknown_start'
 403 ; CHECK-NEXT:  Determining loop execution counts for: @slt_129_unknown_start
 404 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is (((127 + (-1 * (1 umin (127 + (-1 * %start) + (0 smax (-127 + %start)<nsw>))))<nuw><nsw> + (-1 * %start) + (0 smax (-127 + %start)<nsw>)) /u -127) + (1 umin (127 + (-1 * %start) + (0 smax (-127 + %start)<nsw>))))
 405 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is i8 2
 406 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (((127 + (-1 * (1 umin (127 + (-1 * %start) + (0 smax (-127 + %start)<nsw>))))<nuw><nsw> + (-1 * %start) + (0 smax (-127 + %start)<nsw>)) /u -127) + (1 umin (127 + (-1 * %start) + (0 smax (-127 + %start)<nsw>))))
 407 ; CHECK-NEXT:  Loop %for.body: Trip multiple is 1
 408 ;
 409 entry:
 410   br label %for.body
 411
 412 for.body:                                         ; preds = %entry, %for.body
 413   %i.05 = phi i8 [ %add, %for.body ], [ %start, %entry ]
 414   %add = add nsw i8 %i.05, 129
 415   %cmp = icmp slt i8 %add, 0
 416   br i1 %cmp, label %for.body, label %for.end
 417
 418 for.end:                                          ; preds = %for.body, %entry
 419   ret void
 420 }
 421
 422
 423 ; IV does wrap, and thus causes us to branch on poison.  This loop is
 424 ; ill defined.
 425 define void @slt_ub1() {
 426 ; CHECK-LABEL: 'slt_ub1'
 427 ; CHECK-NEXT:  Determining loop execution counts for: @slt_ub1
 428 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is i1 false
 429 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is i1 false
 430 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is i1 false
 431 ; CHECK-NEXT:  Loop %for.body: Trip multiple is 1
 432 ;
 433 entry:
 434   br label %for.body
 435
 436 for.body:                                         ; preds = %entry, %for.body
 437   %i.05 = phi i8 [ %add, %for.body ], [ 2, %entry ]
 438   %add = add nuw i8 %i.05, 255
 439   %cmp = icmp slt i8 %add, 128
 440   br i1 %cmp, label %for.body, label %for.end
 441
 442 for.end:                                          ; preds = %for.body, %entry
 443   ret void
 444 }
 445
 446 ; This loop is ill defined because we violate the nsw flag on the first
 447 ; iteration.
 448 define void @slt_ub2() {
 449 ; CHECK-LABEL: 'slt_ub2'
 450 ; CHECK-NEXT:  Determining loop execution counts for: @slt_ub2
 451 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is i1 false
 452 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is i1 false
 453 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is i1 false
 454 ; CHECK-NEXT:  Loop %for.body: Trip multiple is 1
 455 ;
 456 entry:
 457   br label %for.body
 458
 459 for.body:                                         ; preds = %entry, %for.body
 460   %i.05 = phi i8 [ %add, %for.body ], [ 0, %entry ]
 461   %add = add nsw nuw i8 %i.05, 129
 462   %cmp = icmp slt i8 %add, 128
 463   br i1 %cmp, label %for.body, label %for.end
 464
 465 for.end:                                          ; preds = %for.body, %entry
 466   ret void
 467 }
 468
 469 ; Large stride, poison produced for %add on second iteration, but not
 470 ; branched on.
 471 define void @slt_129_preinc() {
 472 ; CHECK-LABEL: 'slt_129_preinc'
 473 ; CHECK-NEXT:  Determining loop execution counts for: @slt_129_preinc
 474 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is i8 1
 475 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is i8 1
 476 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is i8 1
 477 ; CHECK-NEXT:  Loop %for.body: Trip multiple is 2
 478 ;
 479 entry:
 480   br label %for.body
 481
 482 for.body:                                         ; preds = %entry, %for.body
 483   %i.05 = phi i8 [ %add, %for.body ], [ -128, %entry ]
 484   %add = add nuw i8 %i.05, 129
 485   %cmp = icmp slt i8 %i.05, 0
 486   br i1 %cmp, label %for.body, label %for.end
 487
 488 for.end:                                          ; preds = %for.body, %entry
 489   ret void
 490 }
 491
 492 define void @slt_preinc(i8 %step) {
 493 ; CHECK-LABEL: 'slt_preinc'
 494 ; CHECK-NEXT:  Determining loop execution counts for: @slt_preinc
 495 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is i8 1
 496 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is i8 1
 497 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is i8 1
 498 ; CHECK-NEXT:  Loop %for.body: Trip multiple is 2
 499 ;
 500 entry:
 501   %assume = icmp ult i8 128, %step
 502   call void @llvm.assume(i1 %assume)
 503   br label %for.body
 504
 505 for.body:                                         ; preds = %entry, %for.body
 506   %i.05 = phi i8 [ %add, %for.body ], [ -128, %entry ]
 507   %add = add nuw i8 %i.05, 129
 508   %cmp = icmp slt i8 %i.05, 0
 509   br i1 %cmp, label %for.body, label %for.end
 510
 511 for.end:                                          ; preds = %for.body, %entry
 512   ret void
 513 }
 514
 515 define void @slt_129_varying_rhs(ptr %n_p) {
 516 ; CHECK-LABEL: 'slt_129_varying_rhs'
 517 ; CHECK-NEXT:  Determining loop execution counts for: @slt_129_varying_rhs
 518 ; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
 519 ; CHECK-NEXT:  Loop %for.body: Unpredictable constant max backedge-taken count.
 520 ; CHECK-NEXT:  Loop %for.body: Unpredictable symbolic max backedge-taken count.
 521 ;
 522 entry:
 523   br label %for.body
 524
 525 for.body:                                         ; preds = %entry, %for.body
 526   %i.05 = phi i8 [ %add, %for.body ], [ -128, %entry ]
 527   %add = add nsw i8 %i.05, 129
 528   %n = load i8, ptr %n_p
 529   %cmp = icmp slt i8 %add, %n
 530   br i1 %cmp, label %for.body, label %for.end
 531
 532 for.end:                                          ; preds = %for.body, %entry
 533   ret void
 534 }
 535
 536 define void @slt_symbolic_varying_rhs(ptr %n_p, i8 %step) {
 537 ; CHECK-LABEL: 'slt_symbolic_varying_rhs'
 538 ; CHECK-NEXT:  Determining loop execution counts for: @slt_symbolic_varying_rhs
 539 ; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
 540 ; CHECK-NEXT:  Loop %for.body: Unpredictable constant max backedge-taken count.
 541 ; CHECK-NEXT:  Loop %for.body: Unpredictable symbolic max backedge-taken count.
 542 ;
 543 entry:
 544   %assume = icmp ult i8 128, %step
 545   call void @llvm.assume(i1 %assume)
 546   br label %for.body
 547
 548 for.body:                                         ; preds = %entry, %for.body
 549   %i.05 = phi i8 [ %add, %for.body ], [ -128, %entry ]
 550   %add = add nsw i8 %i.05, %step
 551   %n = load i8, ptr %n_p
 552   %cmp = icmp slt i8 %add, %n
 553   br i1 %cmp, label %for.body, label %for.end
 554
 555 for.end:                                          ; preds = %for.body, %entry
 556   ret void
 557 }
 558
 559 declare void @llvm.assume(i1)
 560
 561 ; Test case for PR57818.
 562 define void @step_is_neg_addrec_slt_8(i64 %n) {
 563 ; CHECK-LABEL: 'step_is_neg_addrec_slt_8'
 564 ; CHECK-NEXT:  Determining loop execution counts for: @step_is_neg_addrec_slt_8
 565 ; CHECK-NEXT:  Loop %inner: backedge-taken count is (7 /u {0,+,-1}<%outer.header>)
 566 ; CHECK-NEXT:  Loop %inner: constant max backedge-taken count is i32 8
 567 ; CHECK-NEXT:  Loop %inner: symbolic max backedge-taken count is (7 /u {0,+,-1}<%outer.header>)
 568 ; CHECK-NEXT:  Loop %inner: Trip multiple is 1
 569 ; CHECK-NEXT:  Loop %outer.header: backedge-taken count is i64 0
 570 ; CHECK-NEXT:  Loop %outer.header: constant max backedge-taken count is i64 0
 571 ; CHECK-NEXT:  Loop %outer.header: symbolic max backedge-taken count is i64 0
 572 ; CHECK-NEXT:  Loop %outer.header: Trip multiple is 1
 573 ;
 574 entry:
 575   br label %outer.header
 576
 577 outer.header:
 578   %outer.iv = phi i64 [ 0, %entry ], [ %outer.iv.next, %outer.latch ]
 579   %ec.1 = icmp eq i64 %outer.iv, 100
 580   br i1 %ec.1, label %inner.ph, label %exit
 581
 582 inner.ph:
 583   %outer.trunc = trunc i64 %outer.iv to i32
 584   br label %inner
 585
 586 inner:
 587   %inner.iv = phi i32 [ 0, %inner.ph ], [ %inner.iv.next, %inner ]
 588   %inner.iv.next = add nsw i32 %inner.iv, %outer.trunc
 589   %inner.c = icmp slt i32 %inner.iv.next, 8
 590   br i1 %inner.c, label %inner, label %outer.latch, !llvm.loop !0
 591
 592 outer.latch:
 593   %outer.iv.next = add nsw i64 %outer.iv, -1
 594   br label %outer.header
 595
 596 exit:
 597   ret void
 598 }
 599
 600 define void @step_is_neg_addrec_slt_var(i32 %n) {
 601 ; CHECK-LABEL: 'step_is_neg_addrec_slt_var'
 602 ; CHECK-NEXT:  Determining loop execution counts for: @step_is_neg_addrec_slt_var
 603 ; CHECK-NEXT:  Loop %inner: backedge-taken count is ({0,+,1}<nuw><nsw><%outer.header> + ({0,+,-1}<nsw><%outer.header> smax %n))
 604 ; CHECK-NEXT:  Loop %inner: constant max backedge-taken count is i32 2147483647
 605 ; CHECK-NEXT:  Loop %inner: symbolic max backedge-taken count is ({0,+,1}<nuw><nsw><%outer.header> + ({0,+,-1}<nsw><%outer.header> smax %n))
 606 ; CHECK-NEXT:  Loop %inner: Trip multiple is 1
 607 ; CHECK-NEXT:  Loop %outer.header: backedge-taken count is i64 0
 608 ; CHECK-NEXT:  Loop %outer.header: constant max backedge-taken count is i64 0
 609 ; CHECK-NEXT:  Loop %outer.header: symbolic max backedge-taken count is i64 0
 610 ; CHECK-NEXT:  Loop %outer.header: Trip multiple is 1
 611 ;
 612 entry:
 613   br label %outer.header
 614
 615 outer.header:
 616   %outer.iv = phi i64 [ 0, %entry ], [ %outer.iv.next, %outer.latch ]
 617   %ec.1 = icmp eq i64 %outer.iv, 100
 618   br i1 %ec.1, label %inner.ph, label %exit
 619
 620 inner.ph:
 621   %outer.trunc = trunc i64 %outer.iv to i32
 622   br label %inner
 623
 624 inner:
 625   %inner.iv = phi i32 [ 0, %inner.ph ], [ %inner.iv.next, %inner ]
 626   %inner.iv.next = add nsw i32 %inner.iv, %outer.trunc
 627   %inner.c = icmp slt i32 %inner.iv.next, %n
 628   br i1 %inner.c, label %inner, label %outer.latch, !llvm.loop !0
 629
 630 outer.latch:
 631   %outer.iv.next = add nsw i64 %outer.iv, -1
 632   br label %outer.header
 633
 634 exit:
 635   ret void
 636 }
 637
 638 define void @step_is_neg_addrec_unknown_start(i32 %n) {
 639 ; CHECK-LABEL: 'step_is_neg_addrec_unknown_start'
 640 ; CHECK-NEXT:  Determining loop execution counts for: @step_is_neg_addrec_unknown_start
 641 ; CHECK-NEXT:  Loop %inner: backedge-taken count is ({(-1 * %n),+,1}<nw><%outer.header> + (8 smax {%n,+,-1}<nsw><%outer.header>))
 642 ; CHECK-NEXT:  Loop %inner: constant max backedge-taken count is i32 -2147483640
 643 ; CHECK-NEXT:  Loop %inner: symbolic max backedge-taken count is ({(-1 * %n),+,1}<nw><%outer.header> + (8 smax {%n,+,-1}<nsw><%outer.header>))
 644 ; CHECK-NEXT:  Loop %inner: Trip multiple is 1
 645 ; CHECK-NEXT:  Loop %outer.header: backedge-taken count is i64 0
 646 ; CHECK-NEXT:  Loop %outer.header: constant max backedge-taken count is i64 0
 647 ; CHECK-NEXT:  Loop %outer.header: symbolic max backedge-taken count is i64 0
 648 ; CHECK-NEXT:  Loop %outer.header: Trip multiple is 1
 649 ;
 650 entry:
 651   br label %outer.header
 652
 653 outer.header:
 654   %outer.iv = phi i64 [ 0, %entry ], [ %outer.iv.next, %outer.latch ]
 655   %ec.1 = icmp eq i64 %outer.iv, 100
 656   br i1 %ec.1, label %inner.ph, label %exit
 657
 658 inner.ph:
 659   %outer.trunc = trunc i64 %outer.iv to i32
 660   br label %inner
 661
 662 inner:
 663   %inner.iv = phi i32 [ %n, %inner.ph ], [ %inner.iv.next, %inner ]
 664   %inner.iv.next = add nsw i32 %inner.iv, %outer.trunc
 665   %inner.c = icmp slt i32 %inner.iv.next, 8
 666   br i1 %inner.c, label %inner, label %outer.latch, !llvm.loop !0
 667
 668 outer.latch:
 669   %outer.iv.next = add nsw i64 %outer.iv, -1
 670   br label %outer.header
 671
 672 exit:
 673   ret void
 674 }
 675
 676 !0 = distinct !{!0, !1}
 677 !1 = !{!"llvm.loop.mustprogress"}