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