llvm/test/Analysis/ScalarEvolution/max-trip-count.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 4
   2 ; RUN: opt < %s -disable-output "-passes=print<scalar-evolution>" -scalar-evolution-classify-expressions=0 2>&1 | FileCheck %s
   3
   4 ; ScalarEvolution should be able to understand the loop and eliminate the casts.
   5
   6
   7 define void @foo(ptr nocapture %d, i32 %n) nounwind {
   8 ; CHECK-LABEL: 'foo'
   9 ; CHECK-NEXT:  Determining loop execution counts for: @foo
  10 ; CHECK-NEXT:  Loop %bb: backedge-taken count is (-1 + %n)
  11 ; CHECK-NEXT:  Loop %bb: constant max backedge-taken count is i32 2147483646
  12 ; CHECK-NEXT:  Loop %bb: symbolic max backedge-taken count is (-1 + %n)
  13 ; CHECK-NEXT:  Loop %bb: Trip multiple is 1
  14 ;
  15 entry:
  16         %0 = icmp sgt i32 %n, 0         ; <i1> [#uses=1]
  17         br i1 %0, label %bb.nph, label %return
  18
  19 bb.nph:         ; preds = %entry
  20         br label %bb
  21
  22 bb:             ; preds = %bb1, %bb.nph
  23         %i.02 = phi i32 [ %5, %bb1 ], [ 0, %bb.nph ]            ; <i32> [#uses=2]
  24         %p.01 = phi i8 [ %4, %bb1 ], [ -1, %bb.nph ]            ; <i8> [#uses=2]
  25         %1 = sext i8 %p.01 to i32               ; <i32> [#uses=1]
  26         %2 = sext i32 %i.02 to i64              ; <i64> [#uses=1]
  27         %3 = getelementptr i32, ptr %d, i64 %2          ; <ptr> [#uses=1]
  28         store i32 %1, ptr %3, align 4
  29         %4 = add i8 %p.01, 1            ; <i8> [#uses=1]
  30         %5 = add i32 %i.02, 1           ; <i32> [#uses=2]
  31         br label %bb1
  32
  33 bb1:            ; preds = %bb
  34         %6 = icmp slt i32 %5, %n                ; <i1> [#uses=1]
  35         br i1 %6, label %bb, label %bb1.return_crit_edge
  36
  37 bb1.return_crit_edge:           ; preds = %bb1
  38         br label %return
  39
  40 return:         ; preds = %bb1.return_crit_edge, %entry
  41         ret void
  42 }
  43
  44 ; ScalarEvolution should be able to find the maximum tripcount
  45 ; of this multiple-exit loop, and if it doesn't know the exact
  46 ; count, it should say so.
  47
  48 ; PR7845
  49
  50 @.str = private constant [4 x i8] c"%d\0A\00"     ; <ptr> [#uses=2]
  51
  52 define i32 @main() nounwind {
  53 ; CHECK-LABEL: 'main'
  54 ; CHECK-NEXT:  Determining loop execution counts for: @main
  55 ; CHECK-NEXT:  Loop %for.cond: <multiple exits> Unpredictable backedge-taken count.
  56 ; CHECK-NEXT:    exit count for for.cond: i32 5
  57 ; CHECK-NEXT:    exit count for for.body: ***COULDNOTCOMPUTE***
  58 ; CHECK-NEXT:  Loop %for.cond: constant max backedge-taken count is i32 5
  59 ; CHECK-NEXT:  Loop %for.cond: symbolic max backedge-taken count is i32 5
  60 ; CHECK-NEXT:    symbolic max exit count for for.cond: i32 5
  61 ; CHECK-NEXT:    symbolic max exit count for for.body: ***COULDNOTCOMPUTE***
  62 ;
  63 entry:
  64   br label %for.cond
  65
  66 for.cond:                                         ; preds = %for.inc, %entry
  67   %g_4.0 = phi i32 [ 0, %entry ], [ %add, %for.inc ] ; <i32> [#uses=5]
  68   %cmp = icmp slt i32 %g_4.0, 5                   ; <i1> [#uses=1]
  69   br i1 %cmp, label %for.body, label %for.end
  70
  71 for.body:                                         ; preds = %for.cond
  72   %conv = trunc i32 %g_4.0 to i16                 ; <i16> [#uses=1]
  73   %tobool.not = icmp eq i16 %conv, 0              ; <i1> [#uses=1]
  74   %tobool3 = icmp ne i32 %g_4.0, 0                ; <i1> [#uses=1]
  75   %or.cond = and i1 %tobool.not, %tobool3         ; <i1> [#uses=1]
  76   br i1 %or.cond, label %for.end, label %for.inc
  77
  78 for.inc:                                          ; preds = %for.body
  79   %add = add nsw i32 %g_4.0, 1                    ; <i32> [#uses=1]
  80   br label %for.cond
  81
  82 for.end:                                          ; preds = %for.body, %for.cond
  83   %call = call i32 (ptr, ...) @printf(ptr @.str, i32 %g_4.0) nounwind ; <i32> [#uses=0]
  84   ret i32 0
  85 }
  86
  87 declare i32 @printf(ptr, ...)
  88
  89 define void @test(ptr %a, i32 %n) nounwind {
  90 ; CHECK-LABEL: 'test'
  91 ; CHECK-NEXT:  Determining loop execution counts for: @test
  92 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + (zext i32 %n to i64))<nsw>
  93 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is i64 2147483646
  94 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (-1 + (zext i32 %n to i64))<nsw>
  95 ; CHECK-NEXT:  Loop %for.body: Trip multiple is 1
  96 ;
  97 entry:
  98   %cmp1 = icmp sgt i32 %n, 0
  99   br i1 %cmp1, label %for.body.lr.ph, label %for.end
 100
 101 for.body.lr.ph:                                   ; preds = %entry
 102   %tmp = zext i32 %n to i64
 103   br label %for.body
 104
 105 for.body:                                         ; preds = %for.body, %for.body.lr.ph
 106   %indvar = phi i64 [ %indvar.next, %for.body ], [ 0, %for.body.lr.ph ]
 107   %arrayidx = getelementptr i8, ptr %a, i64 %indvar
 108   store i8 0, ptr %arrayidx, align 1
 109   %indvar.next = add i64 %indvar, 1
 110   %exitcond = icmp ne i64 %indvar.next, %tmp
 111   br i1 %exitcond, label %for.body, label %for.cond.for.end_crit_edge
 112
 113 for.cond.for.end_crit_edge:                       ; preds = %for.body
 114   br label %for.end
 115
 116 for.end:                                          ; preds = %for.cond.for.end_crit_edge, %entry
 117   ret void
 118 }
 119
 120
 121 ; PR19799: Indvars miscompile due to an incorrect max backedge taken count from SCEV.
 122 @a = common global i32 0, align 4
 123
 124 define i32 @pr19799() {
 125 ; CHECK-LABEL: 'pr19799'
 126 ; CHECK-NEXT:  Determining loop execution counts for: @pr19799
 127 ; CHECK-NEXT:  Loop %for.body.i: <multiple exits> Unpredictable backedge-taken count.
 128 ; CHECK-NEXT:    exit count for for.body.i: ***COULDNOTCOMPUTE***
 129 ; CHECK-NEXT:    exit count for for.cond.i: i32 1
 130 ; CHECK-NEXT:  Loop %for.body.i: constant max backedge-taken count is i32 1
 131 ; CHECK-NEXT:  Loop %for.body.i: symbolic max backedge-taken count is i32 1
 132 ; CHECK-NEXT:    symbolic max exit count for for.body.i: ***COULDNOTCOMPUTE***
 133 ; CHECK-NEXT:    symbolic max exit count for for.cond.i: i32 1
 134 ;
 135 entry:
 136   store i32 -1, ptr @a, align 4
 137   br label %for.body.i
 138
 139 for.body.i:                                       ; preds = %for.cond.i, %entry
 140   %storemerge1.i = phi i32 [ -1, %entry ], [ %add.i.i, %for.cond.i ]
 141   %tobool.i = icmp eq i32 %storemerge1.i, 0
 142   %add.i.i = add nsw i32 %storemerge1.i, 2
 143   br i1 %tobool.i, label %bar.exit, label %for.cond.i
 144
 145 for.cond.i:                                       ; preds = %for.body.i
 146   store i32 %add.i.i, ptr @a, align 4
 147   %cmp.i = icmp slt i32 %storemerge1.i, 0
 148   br i1 %cmp.i, label %for.body.i, label %bar.exit
 149
 150 bar.exit:                                         ; preds = %for.cond.i, %for.body.i
 151   ret i32 0
 152 }
 153
 154 ; PR18886: Indvars miscompile due to an incorrect max backedge taken count from SCEV.
 155 @aa = global i64 0, align 8
 156
 157 define i32 @pr18886() {
 158 ; CHECK-LABEL: 'pr18886'
 159 ; CHECK-NEXT:  Determining loop execution counts for: @pr18886
 160 ; CHECK-NEXT:  Loop %for.body: <multiple exits> Unpredictable backedge-taken count.
 161 ; CHECK-NEXT:    exit count for for.body: ***COULDNOTCOMPUTE***
 162 ; CHECK-NEXT:    exit count for for.cond: i64 3
 163 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is i64 3
 164 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is i64 3
 165 ; CHECK-NEXT:    symbolic max exit count for for.body: ***COULDNOTCOMPUTE***
 166 ; CHECK-NEXT:    symbolic max exit count for for.cond: i64 3
 167 ;
 168 entry:
 169   store i64 -21, ptr @aa, align 8
 170   br label %for.body
 171
 172 for.body:
 173   %storemerge1 = phi i64 [ -21, %entry ], [ %add, %for.cond ]
 174   %tobool = icmp eq i64 %storemerge1, 0
 175   %add = add nsw i64 %storemerge1, 8
 176   br i1 %tobool, label %return, label %for.cond
 177
 178 for.cond:
 179   store i64 %add, ptr @aa, align 8
 180   %cmp = icmp slt i64 %add, 9
 181   br i1 %cmp, label %for.body, label %return
 182
 183 return:
 184   %retval.0 = phi i32 [ 1, %for.body ], [ 0, %for.cond ]
 185   ret i32 %retval.0
 186 }
 187
 188 ; Here we have a must-exit loop latch that is not computable and a
 189 ; may-exit early exit that can only have one non-exiting iteration
 190 ; before the check is forever skipped.
 191 ;
 192 @b = common global i32 0, align 4
 193
 194 define i32 @cannot_compute_mustexit() {
 195 ; CHECK-LABEL: 'cannot_compute_mustexit'
 196 ; CHECK-NEXT:  Determining loop execution counts for: @cannot_compute_mustexit
 197 ; CHECK-NEXT:  Loop %for.body.i: <multiple exits> Unpredictable backedge-taken count.
 198 ; CHECK-NEXT:    exit count for for.body.i: ***COULDNOTCOMPUTE***
 199 ; CHECK-NEXT:    exit count for for.cond.i: ***COULDNOTCOMPUTE***
 200 ; CHECK-NEXT:  Loop %for.body.i: Unpredictable constant max backedge-taken count.
 201 ; CHECK-NEXT:  Loop %for.body.i: Unpredictable symbolic max backedge-taken count.
 202 ; CHECK-NEXT:    symbolic max exit count for for.body.i: ***COULDNOTCOMPUTE***
 203 ; CHECK-NEXT:    symbolic max exit count for for.cond.i: ***COULDNOTCOMPUTE***
 204 ;
 205 entry:
 206   store i32 -1, ptr @a, align 4
 207   br label %for.body.i
 208
 209 for.body.i:                                       ; preds = %for.cond.i, %entry
 210   %storemerge1.i = phi i32 [ -1, %entry ], [ %add.i.i, %for.cond.i ]
 211   %tobool.i = icmp eq i32 %storemerge1.i, 0
 212   %add.i.i = add nsw i32 %storemerge1.i, 2
 213   br i1 %tobool.i, label %bar.exit, label %for.cond.i
 214
 215 for.cond.i:                                       ; preds = %for.body.i
 216   store i32 %add.i.i, ptr @a, align 4
 217   %ld = load volatile i32, ptr @b
 218   %cmp.i = icmp ne i32 %ld, 0
 219   br i1 %cmp.i, label %for.body.i, label %bar.exit
 220
 221 bar.exit:                                         ; preds = %for.cond.i, %for.body.i
 222   ret i32 0
 223 }
 224
 225 ; This loop has two must-exits, both of which dominate the latch. The
 226 ; MaxBECount should be the minimum of them.
 227 ;
 228 define i32 @two_mustexit() {
 229 ; CHECK-LABEL: 'two_mustexit'
 230 ; CHECK-NEXT:  Determining loop execution counts for: @two_mustexit
 231 ; CHECK-NEXT:  Loop %for.body.i: <multiple exits> backedge-taken count is i32 1
 232 ; CHECK-NEXT:    exit count for for.body.i: i32 1
 233 ; CHECK-NEXT:    exit count for for.cond.i: i32 2
 234 ; CHECK-NEXT:  Loop %for.body.i: constant max backedge-taken count is i32 1
 235 ; CHECK-NEXT:  Loop %for.body.i: symbolic max backedge-taken count is i32 1
 236 ; CHECK-NEXT:    symbolic max exit count for for.body.i: i32 1
 237 ; CHECK-NEXT:    symbolic max exit count for for.cond.i: i32 2
 238 ; CHECK-NEXT:  Loop %for.body.i: Trip multiple is 1
 239 ;
 240 entry:
 241   store i32 -1, ptr @a, align 4
 242   br label %for.body.i
 243
 244 for.body.i:                                       ; preds = %for.cond.i, %entry
 245   %storemerge1.i = phi i32 [ -1, %entry ], [ %add.i.i, %for.cond.i ]
 246   %tobool.i = icmp sgt i32 %storemerge1.i, 0
 247   %add.i.i = add nsw i32 %storemerge1.i, 2
 248   br i1 %tobool.i, label %bar.exit, label %for.cond.i
 249
 250 for.cond.i:                                       ; preds = %for.body.i
 251   store i32 %add.i.i, ptr @a, align 4
 252   %cmp.i = icmp slt i32 %storemerge1.i, 3
 253   br i1 %cmp.i, label %for.body.i, label %bar.exit
 254
 255 bar.exit:                                         ; preds = %for.cond.i, %for.body.i
 256   ret i32 0
 257 }
 258
 259 define i32 @ne_max_trip_count_1(i32 %n) {
 260 ; CHECK-LABEL: 'ne_max_trip_count_1'
 261 ; CHECK-NEXT:  Determining loop execution counts for: @ne_max_trip_count_1
 262 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is (zext i3 (trunc i32 %n to i3) to i32)
 263 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is i32 7
 264 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (zext i3 (trunc i32 %n to i3) to i32)
 265 ; CHECK-NEXT:  Loop %for.body: Trip multiple is 1
 266 ;
 267 entry:
 268   %masked = and i32 %n, 7
 269   br label %for.body
 270
 271 for.body:
 272   %i = phi i32 [ 0, %entry ], [ %add, %for.body ]
 273   %add = add nsw i32 %i, 1
 274   %cmp = icmp ne i32 %i, %masked
 275   br i1 %cmp, label %for.body, label %bar.exit
 276
 277 bar.exit:
 278   ret i32 0
 279 }
 280
 281 define i32 @ne_max_trip_count_2(i32 %n) {
 282 ; CHECK-LABEL: 'ne_max_trip_count_2'
 283 ; CHECK-NEXT:  Determining loop execution counts for: @ne_max_trip_count_2
 284 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + (zext i3 (trunc i32 %n to i3) to i32))<nsw>
 285 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is i32 -1
 286 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (-1 + (zext i3 (trunc i32 %n to i3) to i32))<nsw>
 287 ; CHECK-NEXT:  Loop %for.body: Trip multiple is 1
 288 ;
 289 entry:
 290   %masked = and i32 %n, 7
 291   br label %for.body
 292
 293 for.body:
 294   %i = phi i32 [ 0, %entry ], [ %add, %for.body ]
 295   %add = add nsw i32 %i, 1
 296   %cmp = icmp ne i32 %add, %masked
 297   br i1 %cmp, label %for.body, label %bar.exit
 298
 299 bar.exit:
 300   ret i32 0
 301 }
 302
 303 define i32 @ne_max_trip_count_3(i32 %n) {
 304 ; CHECK-LABEL: 'ne_max_trip_count_3'
 305 ; CHECK-NEXT:  Determining loop execution counts for: @ne_max_trip_count_3
 306 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + (zext i3 (trunc i32 %n to i3) to i32))<nsw>
 307 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is i32 6
 308 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (-1 + (zext i3 (trunc i32 %n to i3) to i32))<nsw>
 309 ; CHECK-NEXT:  Loop %for.body: Trip multiple is 1
 310 ;
 311 entry:
 312   %masked = and i32 %n, 7
 313   %guard = icmp eq i32 %masked, 0
 314   br i1 %guard, label %exit, label %for.preheader
 315
 316 for.preheader:
 317   br label %for.body
 318
 319 for.body:
 320   %i = phi i32 [ 0, %for.preheader ], [ %add, %for.body ]
 321   %add = add nsw i32 %i, 1
 322   %cmp = icmp ne i32 %add, %masked
 323   br i1 %cmp, label %for.body, label %loop.exit
 324
 325 loop.exit:
 326   br label %exit
 327
 328 exit:
 329   ret i32 0
 330 }
 331
 332 define i32 @ne_max_trip_count_4(i32 %n) {
 333 ; CHECK-LABEL: 'ne_max_trip_count_4'
 334 ; CHECK-NEXT:  Determining loop execution counts for: @ne_max_trip_count_4
 335 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + %n)
 336 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is i32 -2
 337 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (-1 + %n)
 338 ; CHECK-NEXT:  Loop %for.body: Trip multiple is 1
 339 ;
 340 entry:
 341   %guard = icmp eq i32 %n, 0
 342   br i1 %guard, label %exit, label %for.preheader
 343
 344 for.preheader:
 345   br label %for.body
 346
 347 for.body:
 348   %i = phi i32 [ 0, %for.preheader ], [ %add, %for.body ]
 349   %add = add nsw i32 %i, 1
 350   %cmp = icmp ne i32 %add, %n
 351   br i1 %cmp, label %for.body, label %loop.exit
 352
 353 loop.exit:
 354   br label %exit
 355
 356 exit:
 357   ret i32 0
 358 }
 359
 360 ; The end bound of the loop can change between iterations, so the exact trip
 361 ; count is unknown, but SCEV can calculate the max trip count.
 362 define void @changing_end_bound(ptr %n_addr, ptr %addr) {
 363 ; CHECK-LABEL: 'changing_end_bound'
 364 ; CHECK-NEXT:  Determining loop execution counts for: @changing_end_bound
 365 ; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
 366 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 2147483646
 367 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is i32 2147483646
 368 ;
 369 entry:
 370   br label %loop
 371
 372 loop:
 373   %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]
 374   %acc = phi i32 [ 0, %entry ], [ %acc.next, %loop ]
 375   %val = load atomic i32, ptr %addr unordered, align 4
 376   fence acquire
 377   %acc.next = add i32 %acc, %val
 378   %iv.next = add nsw i32 %iv, 1
 379   %n = load atomic i32, ptr %n_addr unordered, align 4
 380   %cmp = icmp slt i32 %iv.next, %n
 381   br i1 %cmp, label %loop, label %loop.exit
 382
 383 loop.exit:
 384   ret void
 385 }
 386
 387 ; Similar test as above, but unknown start value.
 388 ; Also, there's no nsw on the iv.next, but SCEV knows
 389 ; the termination condition is LT, so the IV cannot wrap.
 390 define void @changing_end_bound2(i32 %start, ptr %n_addr, ptr %addr) {
 391 ; CHECK-LABEL: 'changing_end_bound2'
 392 ; CHECK-NEXT:  Determining loop execution counts for: @changing_end_bound2
 393 ; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
 394 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 -1
 395 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is i32 -1
 396 ;
 397 entry:
 398   br label %loop
 399
 400 loop:
 401   %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ]
 402   %acc = phi i32 [ 0, %entry ], [ %acc.next, %loop ]
 403   %val = load atomic i32, ptr %addr unordered, align 4
 404   fence acquire
 405   %acc.next = add i32 %acc, %val
 406   %iv.next = add i32 %iv, 1
 407   %n = load atomic i32, ptr %n_addr unordered, align 4
 408   %cmp = icmp slt i32 %iv.next, %n
 409   br i1 %cmp, label %loop, label %loop.exit
 410
 411 loop.exit:
 412   ret void
 413 }
 414
 415 ; changing end bound and greater than one stride
 416 define void @changing_end_bound3(i32 %start, ptr %n_addr, ptr %addr) {
 417 ; CHECK-LABEL: 'changing_end_bound3'
 418 ; CHECK-NEXT:  Determining loop execution counts for: @changing_end_bound3
 419 ; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
 420 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 1073741823
 421 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is i32 1073741823
 422 ;
 423 entry:
 424   br label %loop
 425
 426 loop:
 427   %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ]
 428   %acc = phi i32 [ 0, %entry ], [ %acc.next, %loop ]
 429   %val = load atomic i32, ptr %addr unordered, align 4
 430   fence acquire
 431   %acc.next = add i32 %acc, %val
 432   %iv.next = add nsw i32 %iv, 4
 433   %n = load atomic i32, ptr %n_addr unordered, align 4
 434   %cmp = icmp slt i32 %iv.next, %n
 435   br i1 %cmp, label %loop, label %loop.exit
 436
 437 loop.exit:
 438   ret void
 439 }
 440
 441 ; same as above test, but the IV can wrap around.
 442 ; so the max backedge taken count is unpredictable.
 443 define void @changing_end_bound4(i32 %start, ptr %n_addr, ptr %addr) {
 444 ; CHECK-LABEL: 'changing_end_bound4'
 445 ; CHECK-NEXT:  Determining loop execution counts for: @changing_end_bound4
 446 ; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
 447 ; CHECK-NEXT:  Loop %loop: Unpredictable constant max backedge-taken count.
 448 ; CHECK-NEXT:  Loop %loop: Unpredictable symbolic max backedge-taken count.
 449 ;
 450 entry:
 451   br label %loop
 452
 453 loop:
 454   %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ]
 455   %acc = phi i32 [ 0, %entry ], [ %acc.next, %loop ]
 456   %val = load atomic i32, ptr %addr unordered, align 4
 457   fence acquire
 458   %acc.next = add i32 %acc, %val
 459   %iv.next = add i32 %iv, 4
 460   %n = load atomic i32, ptr %n_addr unordered, align 4
 461   %cmp = icmp slt i32 %iv.next, %n
 462   br i1 %cmp, label %loop, label %loop.exit
 463
 464 loop.exit:
 465   ret void
 466 }
 467
 468 ; unknown stride. Since it's not knownPositive, we do not estimate the max
 469 ; backedge taken count.
 470 define void @changing_end_bound5(i32 %stride, i32 %start, ptr %n_addr, ptr %addr) {
 471 ; CHECK-LABEL: 'changing_end_bound5'
 472 ; CHECK-NEXT:  Determining loop execution counts for: @changing_end_bound5
 473 ; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
 474 ; CHECK-NEXT:  Loop %loop: Unpredictable constant max backedge-taken count.
 475 ; CHECK-NEXT:  Loop %loop: Unpredictable symbolic max backedge-taken count.
 476 ;
 477 entry:
 478   br label %loop
 479
 480 loop:
 481   %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ]
 482   %acc = phi i32 [ 0, %entry ], [ %acc.next, %loop ]
 483   %val = load atomic i32, ptr %addr unordered, align 4
 484   fence acquire
 485   %acc.next = add i32 %acc, %val
 486   %iv.next = add nsw i32 %iv, %stride
 487   %n = load atomic i32, ptr %n_addr unordered, align 4
 488   %cmp = icmp slt i32 %iv.next, %n
 489   br i1 %cmp, label %loop, label %loop.exit
 490
 491 loop.exit:
 492   ret void
 493 }
 494
 495 ; negative stride value
 496 define void @changing_end_bound6(i32 %start, ptr %n_addr, ptr %addr) {
 497 ; CHECK-LABEL: 'changing_end_bound6'
 498 ; CHECK-NEXT:  Determining loop execution counts for: @changing_end_bound6
 499 ; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
 500 ; CHECK-NEXT:  Loop %loop: Unpredictable constant max backedge-taken count.
 501 ; CHECK-NEXT:  Loop %loop: Unpredictable symbolic max backedge-taken count.
 502 ;
 503 entry:
 504   br label %loop
 505
 506 loop:
 507   %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ]
 508   %acc = phi i32 [ 0, %entry ], [ %acc.next, %loop ]
 509   %val = load atomic i32, ptr %addr unordered, align 4
 510   fence acquire
 511   %acc.next = add i32 %acc, %val
 512   %iv.next = add nsw i32 %iv, -1
 513   %n = load atomic i32, ptr %n_addr unordered, align 4
 514   %cmp = icmp slt i32 %iv.next, %n
 515   br i1 %cmp, label %loop, label %loop.exit
 516
 517 loop.exit:
 518   ret void
 519 }
 520
 521 ; sgt with negative stride
 522 define void @changing_end_bound7(i32 %start, ptr %n_addr, ptr %addr) {
 523 ; CHECK-LABEL: 'changing_end_bound7'
 524 ; CHECK-NEXT:  Determining loop execution counts for: @changing_end_bound7
 525 ; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
 526 ; CHECK-NEXT:  Loop %loop: Unpredictable constant max backedge-taken count.
 527 ; CHECK-NEXT:  Loop %loop: Unpredictable symbolic max backedge-taken count.
 528 ;
 529 entry:
 530   br label %loop
 531
 532 loop:
 533   %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ]
 534   %acc = phi i32 [ 0, %entry ], [ %acc.next, %loop ]
 535   %val = load atomic i32, ptr %addr unordered, align 4
 536   fence acquire
 537   %acc.next = add i32 %acc, %val
 538   %iv.next = add i32 %iv, -1
 539   %n = load atomic i32, ptr %n_addr unordered, align 4
 540   %cmp = icmp sgt i32 %iv.next, %n
 541   br i1 %cmp, label %loop, label %loop.exit
 542
 543 loop.exit:
 544   ret void
 545 }
 546
 547 define void @max_overflow_se(i8 %n) mustprogress {
 548 ; CHECK-LABEL: 'max_overflow_se'
 549 ; CHECK-NEXT:  Determining loop execution counts for: @max_overflow_se
 550 ; CHECK-NEXT:  Loop %loop: backedge-taken count is i8 0
 551 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i8 0
 552 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is i8 0
 553 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
 554 ;
 555 entry:
 556   br label %loop
 557
 558 loop:
 559   %i = phi i8 [ 63, %entry ], [ %i.next, %loop ]
 560   %i.next = add nsw i8 %i, 63
 561   %t = icmp slt i8 %i.next, %n
 562   br i1 %t, label %loop, label %exit
 563
 564 exit:
 565   ret void
 566 }
 567
 568 ; Show that we correctly realize that %i can overflow here as long as
 569 ; the early exit is taken before we branch on poison.
 570 define void @max_overflow_me(i8 %n) mustprogress {
 571 ; CHECK-LABEL: 'max_overflow_me'
 572 ; CHECK-NEXT:  Determining loop execution counts for: @max_overflow_me
 573 ; CHECK-NEXT:  Loop %loop: <multiple exits> Unpredictable backedge-taken count.
 574 ; CHECK-NEXT:    exit count for loop: i8 1
 575 ; CHECK-NEXT:    exit count for latch: ***COULDNOTCOMPUTE***
 576 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i8 1
 577 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is i8 1
 578 ; CHECK-NEXT:    symbolic max exit count for loop: i8 1
 579 ; CHECK-NEXT:    symbolic max exit count for latch: ***COULDNOTCOMPUTE***
 580 ;
 581 entry:
 582   br label %loop
 583
 584 loop:
 585   %i = phi i8 [ 63, %entry ], [ %i.next, %latch ]
 586   %j = phi i8 [  0, %entry ], [ %j.next, %latch ]
 587   %early.exit = icmp ne i8 %j, 1
 588   br i1 %early.exit, label %latch, label %exit
 589 latch:
 590   %i.next = add nsw i8 %i, 63
 591   %j.next = add nsw nuw i8 %j, 1
 592   %t = icmp slt i8 %i.next, %n
 593   br i1 %t, label %loop, label %exit
 594
 595 exit:
 596   ret void
 597 }
 598
 599
 600 ; Max backedge-taken count is zero.
 601 define void @bool_stride(i1 %s, i1 %n) mustprogress {
 602 ; CHECK-LABEL: 'bool_stride'
 603 ; CHECK-NEXT:  Determining loop execution counts for: @bool_stride
 604 ; CHECK-NEXT:  Loop %loop: backedge-taken count is i1 false
 605 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i1 false
 606 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is i1 false
 607 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
 608 ;
 609 entry:
 610   br label %loop
 611
 612 loop:
 613   %i = phi i1 [ -1, %entry ], [ %i.next, %loop ]
 614   %i.next = add nsw i1 %i, %s
 615   %t = icmp slt i1 %i.next, %n
 616   br i1 %t, label %loop, label %exit
 617
 618 exit:
 619   ret void
 620 }
 621
 622 ; This is a case where our max-backedge taken count logic happens to be
 623 ; able to prove a zero btc, but our symbolic logic doesn't due to a lack
 624 ; of context sensativity.
 625 define void @ne_zero_max_btc(i32 %a) {
 626 ; CHECK-LABEL: 'ne_zero_max_btc'
 627 ; CHECK-NEXT:  Determining loop execution counts for: @ne_zero_max_btc
 628 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is i64 0
 629 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is i64 0
 630 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is i64 0
 631 ; CHECK-NEXT:  Loop %for.body: Trip multiple is 1
 632 ;
 633 entry:
 634   %cmp = icmp slt i32 %a, 1
 635   %spec.select = select i1 %cmp, i32 %a, i32 1
 636   %cmp8 = icmp sgt i32 %a, 0
 637   br i1 %cmp8, label %for.body.preheader, label %loopexit
 638
 639 for.body.preheader:                         ; preds = %if.then4.i.i
 640   %umax = call i32 @llvm.umax.i32(i32 %spec.select, i32 1)
 641   %umax.i.i = zext i32 %umax to i64
 642   br label %for.body
 643
 644 for.body:                                   ; preds = %for.inc, %for.body.preheader
 645   %indvars.iv = phi i64 [ 0, %for.body.preheader ], [ %indvars.iv.next, %for.inc ]
 646   call void @unknown()
 647   br label %for.inc
 648
 649 for.inc:                                    ; preds = %for.body
 650   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
 651   %exitcond.i.not.i534 = icmp ne i64 %indvars.iv.next, %umax.i.i
 652   br i1 %exitcond.i.not.i534, label %for.body, label %loopexit
 653
 654 loopexit:
 655   ret void
 656 }
 657
 658 declare void @unknown()
 659 declare i32 @llvm.umax.i32(i32, i32)