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

   1 ; RUN: opt < %s -analyze -enable-new-pm=0 -scalar-evolution -scalar-evolution-classify-expressions=0 | FileCheck %s
   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 ; CHECK-LABEL: Determining loop execution counts for: @ult_wrap
  13 ; CHECK: Loop %for.body: Unpredictable backedge-taken count
  14 ; CHECK: Loop %for.body: Unpredictable max backedge-taken count
  15 define void @ult_wrap() {
  16 entry:
  17   br label %for.body
  18
  19 for.body:                                         ; preds = %entry, %for.body
  20   %i.05 = phi i8 [ %add, %for.body ], [ 0, %entry ]
  21   %add = add i8 %i.05, 254
  22   %cmp = icmp ult i8 %add, 255
  23   br i1 %cmp, label %for.body, label %for.end
  24
  25 for.end:                                          ; preds = %for.body, %entry
  26   ret void
  27 }
  28
  29 ; This IV cycles between 0, and 128, never causing the loop to exit
  30 ; (This is well defined.)
  31 ; CHECK-LABEL: Determining loop execution counts for: @ult_infinite
  32 ; CHECK: Loop %for.body: Unpredictable backedge-taken count
  33 ; CHECK: Loop %for.body: Unpredictable max backedge-taken count
  34 define void @ult_infinite() {
  35 entry:
  36   br label %for.body
  37
  38 for.body:                                         ; preds = %entry, %for.body
  39   %i.05 = phi i8 [ %add, %for.body ], [ 0, %entry ]
  40   %add = add i8 %i.05, 128
  41   %cmp = icmp ult i8 %add, 255
  42   br i1 %cmp, label %for.body, label %for.end
  43
  44 for.end:                                          ; preds = %for.body, %entry
  45   ret void
  46 }
  47
  48 ; Same as ult_infinite, except that the loop is ill defined due to the
  49 ; must progress attribute
  50 ; CHECK-LABEL: Determining loop execution counts for: @ult_infinite_ub
  51 ; CHECK: Loop %for.body: Unpredictable backedge-taken count
  52 ; CHECK: Loop %for.body: Unpredictable max backedge-taken count
  53 define void @ult_infinite_ub() mustprogress {
  54 entry:
  55   br label %for.body
  56
  57 for.body:                                         ; preds = %entry, %for.body
  58   %i.05 = phi i8 [ %add, %for.body ], [ 0, %entry ]
  59   %add = add i8 %i.05, 128
  60   %cmp = icmp ult i8 %add, 255
  61   br i1 %cmp, label %for.body, label %for.end
  62
  63 for.end:                                          ; preds = %for.body, %entry
  64   ret void
  65 }
  66
  67
  68 ; Backedge is not taken
  69 ; CHECK-LABEL: Determining loop execution counts for: @ult_129_not_taken
  70 ; CHECK: Loop %for.body: backedge-taken count is 0
  71 ; CHECK: Loop %for.body: max backedge-taken count is 0
  72
  73 define void @ult_129_not_taken() {
  74 entry:
  75   br label %for.body
  76
  77 for.body:                                         ; preds = %entry, %for.body
  78   %i.05 = phi i8 [ %add, %for.body ], [ 0, %entry ]
  79   %add = add i8 %i.05, 129
  80   %cmp = icmp ult i8 %add, 128
  81   br i1 %cmp, label %for.body, label %for.end
  82
  83 for.end:                                          ; preds = %for.body, %entry
  84   ret void
  85 }
  86
  87 ; CHECK-LABEL: Determining loop execution counts for: @ult_129_unknown_start
  88 ; CHECK: Loop %for.body: Unpredictable backedge-taken count
  89 ; CHECK: Loop %for.body: Unpredictable max backedge-taken count
  90
  91 define void @ult_129_unknown_start(i8 %start) mustprogress {
  92 entry:
  93   br label %for.body
  94
  95 for.body:                                         ; preds = %entry, %for.body
  96   %i.05 = phi i8 [ %add, %for.body ], [ %start, %entry ]
  97   %add = add nuw i8 %i.05, 129
  98   %cmp = icmp ult i8 %add, 128
  99   br i1 %cmp, label %for.body, label %for.end
 100
 101 for.end:                                          ; preds = %for.body, %entry
 102   ret void
 103 }
 104
 105
 106 ; A case with a non-constant stride where the backedge is not taken
 107 ; CHECK-LABEL: Determining loop execution counts for: @ult_not_taken
 108 ; CHECK: Loop %for.body: Unpredictable backedge-taken count
 109 ; CHECK: Loop %for.body: Unpredictable max backedge-taken count
 110
 111 define void @ult_not_taken(i8 %step) {
 112 entry:
 113   %assume = icmp ult i8 128, %step
 114   call void @llvm.assume(i1 %assume)
 115   br label %for.body
 116
 117 for.body:                                         ; preds = %entry, %for.body
 118   %i.05 = phi i8 [ %add, %for.body ], [ 0, %entry ]
 119   %add = add i8 %i.05, %step
 120   %cmp = icmp ult i8 %add, 128
 121   br i1 %cmp, label %for.body, label %for.end
 122
 123 for.end:                                          ; preds = %for.body, %entry
 124   ret void
 125 }
 126
 127
 128
 129 ; IV does wrap, and thus causes us to branch on poison.  This loop is
 130 ; ill defined.
 131 ; CHECK-LABEL: Determining loop execution counts for: @ult_ub1
 132 ; CHECK: Loop %for.body: backedge-taken count is 2
 133 ; CHECK: Loop %for.body: max backedge-taken count is 2
 134
 135 define void @ult_ub1() {
 136 entry:
 137   br label %for.body
 138
 139 for.body:                                         ; preds = %entry, %for.body
 140   %i.05 = phi i8 [ %add, %for.body ], [ 2, %entry ]
 141   %add = add nuw i8 %i.05, 255
 142   %cmp = icmp ult i8 %add, 128
 143   br i1 %cmp, label %for.body, label %for.end
 144
 145 for.end:                                          ; preds = %for.body, %entry
 146   ret void
 147 }
 148
 149 ; This loop is ill defined because we violate the nsw flag on the first
 150 ; iteration.
 151 ; CHECK-LABEL: Determining loop execution counts for: @ult_ub2
 152 ; CHECK: Loop %for.body: backedge-taken count is 0
 153 ; CHECK: Loop %for.body: max backedge-taken count is 0
 154
 155 define void @ult_ub2() {
 156 entry:
 157   br label %for.body
 158
 159 for.body:                                         ; preds = %entry, %for.body
 160   %i.05 = phi i8 [ %add, %for.body ], [ 0, %entry ]
 161   %add = add nsw nuw i8 %i.05, 129
 162   %cmp = icmp ult i8 %add, 128
 163   br i1 %cmp, label %for.body, label %for.end
 164
 165 for.end:                                          ; preds = %for.body, %entry
 166   ret void
 167 }
 168
 169 ; Large stride, poison produced for %add on second iteration, but not
 170 ; branched on.
 171 ; CHECK-LABEL: Determining loop execution counts for: @ult_129_preinc
 172 ; CHECK: Loop %for.body: backedge-taken count is 1
 173 ; CHECK: Loop %for.body: max backedge-taken count is 1
 174
 175 define void @ult_129_preinc() {
 176 entry:
 177   br label %for.body
 178
 179 for.body:                                         ; preds = %entry, %for.body
 180   %i.05 = phi i8 [ %add, %for.body ], [ 0, %entry ]
 181   %add = add nuw i8 %i.05, 129
 182   %cmp = icmp ult i8 %i.05, 128
 183   br i1 %cmp, label %for.body, label %for.end
 184
 185 for.end:                                          ; preds = %for.body, %entry
 186   ret void
 187 }
 188
 189 ; CHECK-LABEL: Determining loop execution counts for: @ult_preinc
 190 ; CHECK: Loop %for.body: backedge-taken count is 1
 191 ; CHECK: Loop %for.body: max backedge-taken count is 1
 192
 193 define void @ult_preinc(i8 %step) {
 194 entry:
 195   %assume = icmp ult i8 128, %step
 196   call void @llvm.assume(i1 %assume)
 197   br label %for.body
 198
 199 for.body:                                         ; preds = %entry, %for.body
 200   %i.05 = phi i8 [ %add, %for.body ], [ 0, %entry ]
 201   %add = add nuw i8 %i.05, 129
 202   %cmp = icmp ult i8 %i.05, 128
 203   br i1 %cmp, label %for.body, label %for.end
 204
 205 for.end:                                          ; preds = %for.body, %entry
 206   ret void
 207 }
 208
 209 ; CHECK-LABEL: Determining loop execution counts for: @ult_129_varying_rhs
 210 ; CHECK: Loop %for.body: Unpredictable backedge-taken count.
 211 ; CHECK: Loop %for.body: Unpredictable max backedge-taken count
 212
 213 define void @ult_129_varying_rhs(i8* %n_p) {
 214 entry:
 215   br label %for.body
 216
 217 for.body:                                         ; preds = %entry, %for.body
 218   %i.05 = phi i8 [ %add, %for.body ], [ 0, %entry ]
 219   %add = add nuw i8 %i.05, 129
 220   %n = load i8, i8* %n_p
 221   %cmp = icmp ult i8 %add, %n
 222   br i1 %cmp, label %for.body, label %for.end
 223
 224 for.end:                                          ; preds = %for.body, %entry
 225   ret void
 226 }
 227
 228 ; CHECK-LABEL: Determining loop execution counts for: @ult_symbolic_varying_rhs
 229 ; CHECK: Loop %for.body: Unpredictable backedge-taken count.
 230 ; CHECK: Loop %for.body: Unpredictable max backedge-taken count
 231
 232 define void @ult_symbolic_varying_rhs(i8* %n_p, i8 %step) {
 233 entry:
 234   %assume = icmp ult i8 128, %step
 235   call void @llvm.assume(i1 %assume)
 236   br label %for.body
 237
 238 for.body:                                         ; preds = %entry, %for.body
 239   %i.05 = phi i8 [ %add, %for.body ], [ 0, %entry ]
 240   %add = add nuw i8 %i.05, %step
 241   %n = load i8, i8* %n_p
 242   %cmp = icmp ult i8 %add, %n
 243   br i1 %cmp, label %for.body, label %for.end
 244
 245 for.end:                                          ; preds = %for.body, %entry
 246   ret void
 247 }
 248
 249
 250 ; Signed Comparisons
 251 ; ------------------
 252
 253 ; Case where we wrap the induction variable (without generating poison), and
 254 ; thus can't currently compute a trip count.
 255 ; CHECK-LABEL: Determining loop execution counts for: @slt_wrap
 256 ; CHECK: Loop %for.body: backedge-taken count is 63
 257 ; CHECK: Loop %for.body: max backedge-taken count is 63
 258 define void @slt_wrap() {
 259 entry:
 260   br label %for.body
 261
 262 for.body:                                         ; preds = %entry, %for.body
 263   %i.05 = phi i8 [ %add, %for.body ], [ 255, %entry ]
 264   %add = add i8 %i.05, 254
 265   %cmp = icmp slt i8 %add, 127
 266   br i1 %cmp, label %for.body, label %for.end
 267
 268 for.end:                                          ; preds = %for.body, %entry
 269   ret void
 270 }
 271
 272 ; This IV cycles between 0, and int_min (128), never causing the loop to exit
 273 ; (This is well defined.)
 274 ; CHECK-LABEL: Determining loop execution counts for: @slt_infinite
 275 ; CHECK: Loop %for.body: Unpredictable backedge-taken count
 276 ; CHECK: Loop %for.body: Unpredictable max backedge-taken count
 277 define void @slt_infinite() {
 278 entry:
 279   br label %for.body
 280
 281 for.body:                                         ; preds = %entry, %for.body
 282   %i.05 = phi i8 [ %add, %for.body ], [ 0, %entry ]
 283   %add = add i8 %i.05, 128
 284   %cmp = icmp slt i8 %add, 127
 285   br i1 %cmp, label %for.body, label %for.end
 286
 287 for.end:                                          ; preds = %for.body, %entry
 288   ret void
 289 }
 290
 291 ; Same as slt_infinite, except that the loop is ill defined due to the
 292 ; must progress attribute
 293 ; CHECK-LABEL: Determining loop execution counts for: @slt_infinite_ub
 294 ; CHECK: Loop %for.body: Unpredictable backedge-taken count
 295 ; CHECK: Loop %for.body: Unpredictable max backedge-taken count
 296 define void @slt_infinite_ub() mustprogress {
 297 entry:
 298   br label %for.body
 299
 300 for.body:                                         ; preds = %entry, %for.body
 301   %i.05 = phi i8 [ %add, %for.body ], [ 0, %entry ]
 302   %add = add i8 %i.05, 128
 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
 311 ; Backedge is not taken
 312 ; CHECK-LABEL: Determining loop execution counts for: @slt_129_not_taken
 313 ; CHECK: Loop %for.body: backedge-taken count is 0
 314 ; CHECK: Loop %for.body: max backedge-taken count is 0
 315
 316 define void @slt_129_not_taken() {
 317 entry:
 318   br label %for.body
 319
 320 for.body:                                         ; preds = %entry, %for.body
 321   %i.05 = phi i8 [ %add, %for.body ], [ -128, %entry ]
 322   %add = add i8 %i.05, 129
 323   %cmp = icmp slt i8 %add, 0
 324   br i1 %cmp, label %for.body, label %for.end
 325
 326 for.end:                                          ; preds = %for.body, %entry
 327   ret void
 328 }
 329
 330 ; A case with a non-constant stride where the backedge is not taken
 331 ; CHECK-LABEL: Determining loop execution counts for: @slt_not_taken
 332 ; CHECK: Loop %for.body: Unpredictable backedge-taken count
 333 ; CHECK: Loop %for.body: Unpredictable max backedge-taken count
 334
 335 define void @slt_not_taken(i8 %step) {
 336 entry:
 337   %assume = icmp ult i8 128, %step
 338   call void @llvm.assume(i1 %assume)
 339   br label %for.body
 340
 341 for.body:                                         ; preds = %entry, %for.body
 342   %i.05 = phi i8 [ %add, %for.body ], [ -128, %entry ]
 343   %add = add i8 %i.05, %step
 344   %cmp = icmp slt i8 %add, 0
 345   br i1 %cmp, label %for.body, label %for.end
 346
 347 for.end:                                          ; preds = %for.body, %entry
 348   ret void
 349 }
 350
 351 ; CHECK-LABEL: Determining loop execution counts for: @slt_129_unknown_start
 352 ; CHECK: Loop %for.body: Unpredictable backedge-taken count
 353 ; CHECK: Loop %for.body: Unpredictable max backedge-taken count
 354
 355 define void @slt_129_unknown_start(i8 %start) mustprogress {
 356 entry:
 357   br label %for.body
 358
 359 for.body:                                         ; preds = %entry, %for.body
 360   %i.05 = phi i8 [ %add, %for.body ], [ %start, %entry ]
 361   %add = add nsw i8 %i.05, 129
 362   %cmp = icmp slt i8 %add, 0
 363   br i1 %cmp, label %for.body, label %for.end
 364
 365 for.end:                                          ; preds = %for.body, %entry
 366   ret void
 367 }
 368
 369
 370 ; IV does wrap, and thus causes us to branch on poison.  This loop is
 371 ; ill defined.
 372 ; CHECK-LABEL: Determining loop execution counts for: @slt_ub
 373 ; CHECK: Loop %for.body: backedge-taken count is false
 374 ; CHECK: Loop %for.body: max backedge-taken count is false
 375
 376 define void @slt_ub1() {
 377 entry:
 378   br label %for.body
 379
 380 for.body:                                         ; preds = %entry, %for.body
 381   %i.05 = phi i8 [ %add, %for.body ], [ 2, %entry ]
 382   %add = add nuw i8 %i.05, 255
 383   %cmp = icmp slt i8 %add, 128
 384   br i1 %cmp, label %for.body, label %for.end
 385
 386 for.end:                                          ; preds = %for.body, %entry
 387   ret void
 388 }
 389
 390 ; This loop is ill defined because we violate the nsw flag on the first
 391 ; iteration.
 392 ; CHECK-LABEL: Determining loop execution counts for: @slt_ub2
 393 ; CHECK: Loop %for.body: backedge-taken count is false
 394 ; CHECK: Loop %for.body: max backedge-taken count is false
 395
 396 define void @slt_ub2() {
 397 entry:
 398   br label %for.body
 399
 400 for.body:                                         ; preds = %entry, %for.body
 401   %i.05 = phi i8 [ %add, %for.body ], [ 0, %entry ]
 402   %add = add nsw nuw i8 %i.05, 129
 403   %cmp = icmp slt i8 %add, 128
 404   br i1 %cmp, label %for.body, label %for.end
 405
 406 for.end:                                          ; preds = %for.body, %entry
 407   ret void
 408 }
 409
 410 ; Large stride, poison produced for %add on second iteration, but not
 411 ; branched on.
 412 ; CHECK-LABEL: Determining loop execution counts for: @slt_129_preinc
 413 ; CHECK: Loop %for.body: backedge-taken count is 1
 414 ; CHECK: Loop %for.body: max backedge-taken count is 1
 415
 416 define void @slt_129_preinc() {
 417 entry:
 418   br label %for.body
 419
 420 for.body:                                         ; preds = %entry, %for.body
 421   %i.05 = phi i8 [ %add, %for.body ], [ -128, %entry ]
 422   %add = add nuw i8 %i.05, 129
 423   %cmp = icmp slt i8 %i.05, 0
 424   br i1 %cmp, label %for.body, label %for.end
 425
 426 for.end:                                          ; preds = %for.body, %entry
 427   ret void
 428 }
 429
 430 ; CHECK-LABEL: Determining loop execution counts for: @slt_preinc
 431 ; CHECK: Loop %for.body: backedge-taken count is 1
 432 ; CHECK: Loop %for.body: max backedge-taken count is 1
 433
 434 define void @slt_preinc(i8 %step) {
 435 entry:
 436   %assume = icmp ult i8 128, %step
 437   call void @llvm.assume(i1 %assume)
 438   br label %for.body
 439
 440 for.body:                                         ; preds = %entry, %for.body
 441   %i.05 = phi i8 [ %add, %for.body ], [ -128, %entry ]
 442   %add = add nuw i8 %i.05, 129
 443   %cmp = icmp slt i8 %i.05, 0
 444   br i1 %cmp, label %for.body, label %for.end
 445
 446 for.end:                                          ; preds = %for.body, %entry
 447   ret void
 448 }
 449
 450 ; CHECK-LABEL: Determining loop execution counts for: @slt_129_varying_rhs
 451 ; CHECK: Loop %for.body: Unpredictable backedge-taken count.
 452 ; CHECK: Loop %for.body: Unpredictable max backedge-taken count
 453
 454 define void @slt_129_varying_rhs(i8* %n_p) {
 455 entry:
 456   br label %for.body
 457
 458 for.body:                                         ; preds = %entry, %for.body
 459   %i.05 = phi i8 [ %add, %for.body ], [ -128, %entry ]
 460   %add = add nsw i8 %i.05, 129
 461   %n = load i8, i8* %n_p
 462   %cmp = icmp slt i8 %add, %n
 463   br i1 %cmp, label %for.body, label %for.end
 464
 465 for.end:                                          ; preds = %for.body, %entry
 466   ret void
 467 }
 468
 469 ; CHECK-LABEL: Determining loop execution counts for: @slt_symbolic_varying_rhs
 470 ; CHECK: Loop %for.body: Unpredictable backedge-taken count.
 471 ; CHECK: Loop %for.body: Unpredictable max backedge-taken count
 472
 473 define void @slt_symbolic_varying_rhs(i8* %n_p, i8 %step) {
 474 entry:
 475   %assume = icmp ult i8 128, %step
 476   call void @llvm.assume(i1 %assume)
 477   br label %for.body
 478
 479 for.body:                                         ; preds = %entry, %for.body
 480   %i.05 = phi i8 [ %add, %for.body ], [ -128, %entry ]
 481   %add = add nsw i8 %i.05, %step
 482   %n = load i8, i8* %n_p
 483   %cmp = icmp slt i8 %add, %n
 484   br i1 %cmp, label %for.body, label %for.end
 485
 486 for.end:                                          ; preds = %for.body, %entry
 487   ret void
 488 }
 489
 490 declare void @llvm.assume(i1)
 491
 492