test/Analysis/ScalarEvolution/trip-count9.ll

   1 ; RUN: opt -analyze -scalar-evolution -S < %s | FileCheck %s
   2
   3 ; Every combination of
   4 ;  - starting at 0, 1, or %x
   5 ;  - steping by 1 or 2
   6 ;  - stopping at %n or %n*2
   7 ;  - using nsw, or not
   8
   9 ; Some of these represent missed opportunities.
  10
  11 ; CHECK: Determining loop execution counts for: @foo
  12 ; CHECK: Loop %loop: backedge-taken count is (-1 + %n)
  13 ; CHECK: Loop %loop: max backedge-taken count is 6
  14 define void @foo(i4 %n) {
  15 entry:
  16   %s = icmp sgt i4 %n, 0
  17   br i1 %s, label %loop, label %exit
  18 loop:
  19   %i = phi i4 [ 0, %entry ], [ %i.next, %loop ]
  20   %i.next = add i4 %i, 1
  21   %t = icmp slt i4 %i.next, %n
  22   br i1 %t, label %loop, label %exit
  23 exit:
  24   ret void
  25 }
  26
  27 ; CHECK: Determining loop execution counts for: @step2
  28 ; CHECK: Loop %loop: Unpredictable backedge-taken count.
  29 ; CHECK: Loop %loop: Unpredictable max backedge-taken count.
  30 define void @step2(i4 %n) {
  31 entry:
  32   %s = icmp sgt i4 %n, 0
  33   br i1 %s, label %loop, label %exit
  34 loop:
  35   %i = phi i4 [ 0, %entry ], [ %i.next, %loop ]
  36   %i.next = add i4 %i, 2
  37   %t = icmp slt i4 %i.next, %n
  38   br i1 %t, label %loop, label %exit
  39 exit:
  40   ret void
  41 }
  42
  43 ; CHECK: Determining loop execution counts for: @start1
  44 ; CHECK: Loop %loop: backedge-taken count is (-2 + (2 smax %n))
  45 ; CHECK: Loop %loop: max backedge-taken count is 5
  46 define void @start1(i4 %n) {
  47 entry:
  48   %s = icmp sgt i4 %n, 0
  49   br i1 %s, label %loop, label %exit
  50 loop:
  51   %i = phi i4 [ 1, %entry ], [ %i.next, %loop ]
  52   %i.next = add i4 %i, 1
  53   %t = icmp slt i4 %i.next, %n
  54   br i1 %t, label %loop, label %exit
  55 exit:
  56   ret void
  57 }
  58
  59 ; CHECK: Determining loop execution counts for: @start1_step2
  60 ; CHECK: Loop %loop: Unpredictable backedge-taken count.
  61 ; CHECK: Loop %loop: Unpredictable max backedge-taken count.
  62 define void @start1_step2(i4 %n) {
  63 entry:
  64   %s = icmp sgt i4 %n, 0
  65   br i1 %s, label %loop, label %exit
  66 loop:
  67   %i = phi i4 [ 1, %entry ], [ %i.next, %loop ]
  68   %i.next = add i4 %i, 2
  69   %t = icmp slt i4 %i.next, %n
  70   br i1 %t, label %loop, label %exit
  71 exit:
  72   ret void
  73 }
  74
  75 ; CHECK: Determining loop execution counts for: @startx
  76 ; CHECK: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax %n))
  77 ; CHECK: Loop %loop: max backedge-taken count is -1
  78 define void @startx(i4 %n, i4 %x) {
  79 entry:
  80   %s = icmp sgt i4 %n, 0
  81   br i1 %s, label %loop, label %exit
  82 loop:
  83   %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]
  84   %i.next = add i4 %i, 1
  85   %t = icmp slt i4 %i.next, %n
  86   br i1 %t, label %loop, label %exit
  87 exit:
  88   ret void
  89 }
  90
  91 ; CHECK: Determining loop execution counts for: @startx_step2
  92 ; CHECK: Loop %loop: Unpredictable backedge-taken count.
  93 ; CHECK: Loop %loop: Unpredictable max backedge-taken count.
  94 define void @startx_step2(i4 %n, i4 %x) {
  95 entry:
  96   %s = icmp sgt i4 %n, 0
  97   br i1 %s, label %loop, label %exit
  98 loop:
  99   %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]
 100   %i.next = add i4 %i, 2
 101   %t = icmp slt i4 %i.next, %n
 102   br i1 %t, label %loop, label %exit
 103 exit:
 104   ret void
 105 }
 106
 107 ; CHECK: Determining loop execution counts for: @nsw
 108 ; CHECK: Loop %loop: backedge-taken count is (-1 + %n)
 109 ; CHECK: Loop %loop: max backedge-taken count is 6
 110 define void @nsw(i4 %n) {
 111 entry:
 112   %s = icmp sgt i4 %n, 0
 113   br i1 %s, label %loop, label %exit
 114 loop:
 115   %i = phi i4 [ 0, %entry ], [ %i.next, %loop ]
 116   %i.next = add nsw i4 %i, 1
 117   %t = icmp slt i4 %i.next, %n
 118   br i1 %t, label %loop, label %exit
 119 exit:
 120   ret void
 121 }
 122
 123 ; If %n is INT4_MAX, %i.next will wrap. The nsw bit says that the
 124 ; result is undefined. Therefore, after the loop's second iteration,
 125 ; we are free to assume that the loop exits. This is valid because:
 126 ; (a) %i.next is a poison value after the second iteration, which can
 127 ; also be considered an undef value.
 128 ; (b) the return instruction enacts a side effect that is control
 129 ; dependent on the poison value.
 130 ;
 131 ; CHECK-LABEL: nsw_step2
 132 ; CHECK: Determining loop execution counts for: @nsw_step2
 133 ; CHECK: Loop %loop: backedge-taken count is ((-1 + %n) /u 2)
 134 ; CHECK: Loop %loop: max backedge-taken count is 2
 135 define void @nsw_step2(i4 %n) {
 136 entry:
 137   %s = icmp sgt i4 %n, 0
 138   br i1 %s, label %loop, label %exit
 139 loop:
 140   %i = phi i4 [ 0, %entry ], [ %i.next, %loop ]
 141   %i.next = add nsw i4 %i, 2
 142   %t = icmp slt i4 %i.next, %n
 143   br i1 %t, label %loop, label %exit
 144 exit:
 145   ret void
 146 }
 147
 148 ; CHECK-LABEL: nsw_start1
 149 ; CHECK: Determining loop execution counts for: @nsw_start1
 150 ; CHECK: Loop %loop: backedge-taken count is (-2 + (2 smax %n))
 151 ; CHECK: Loop %loop: max backedge-taken count is 5
 152 define void @nsw_start1(i4 %n) {
 153 entry:
 154   %s = icmp sgt i4 %n, 0
 155   br i1 %s, label %loop, label %exit
 156 loop:
 157   %i = phi i4 [ 1, %entry ], [ %i.next, %loop ]
 158   %i.next = add nsw i4 %i, 1
 159   %t = icmp slt i4 %i.next, %n
 160   br i1 %t, label %loop, label %exit
 161 exit:
 162   ret void
 163 }
 164
 165 ; CHECK: Determining loop execution counts for: @nsw_start1_step2
 166 ; CHECK: Loop %loop: backedge-taken count is ((-2 + (3 smax %n)) /u 2)
 167 ; CHECK: Loop %loop: max backedge-taken count is 2
 168 define void @nsw_start1_step2(i4 %n) {
 169 entry:
 170   %s = icmp sgt i4 %n, 0
 171   br i1 %s, label %loop, label %exit
 172 loop:
 173   %i = phi i4 [ 1, %entry ], [ %i.next, %loop ]
 174   %i.next = add nsw i4 %i, 2
 175   %t = icmp slt i4 %i.next, %n
 176   br i1 %t, label %loop, label %exit
 177 exit:
 178   ret void
 179 }
 180
 181 ; CHECK: Determining loop execution counts for: @nsw_startx
 182 ; CHECK: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax %n))
 183 ; CHECK: Loop %loop: max backedge-taken count is -1
 184 define void @nsw_startx(i4 %n, i4 %x) {
 185 entry:
 186   %s = icmp sgt i4 %n, 0
 187   br i1 %s, label %loop, label %exit
 188 loop:
 189   %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]
 190   %i.next = add nsw i4 %i, 1
 191   %t = icmp slt i4 %i.next, %n
 192   br i1 %t, label %loop, label %exit
 193 exit:
 194   ret void
 195 }
 196
 197 ; CHECK: Determining loop execution counts for: @nsw_startx_step2
 198 ; CHECK: Loop %loop: backedge-taken count is ((-1 + (-1 * %x) + ((2 + %x) smax %n)) /u 2)
 199 ; CHECK: Loop %loop: max backedge-taken count is 7
 200 define void @nsw_startx_step2(i4 %n, i4 %x) {
 201 entry:
 202   %s = icmp sgt i4 %n, 0
 203   br i1 %s, label %loop, label %exit
 204 loop:
 205   %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]
 206   %i.next = add nsw i4 %i, 2
 207   %t = icmp slt i4 %i.next, %n
 208   br i1 %t, label %loop, label %exit
 209 exit:
 210   ret void
 211 }
 212
 213 ; CHECK: Determining loop execution counts for: @even
 214 ; CHECK: Loop %loop: backedge-taken count is (-1 + (2 * %n))
 215 ; CHECK: Loop %loop: max backedge-taken count is 5
 216 define void @even(i4 %n) {
 217 entry:
 218   %m = shl i4 %n, 1
 219   %s = icmp sgt i4 %m, 0
 220   br i1 %s, label %loop, label %exit
 221 loop:
 222   %i = phi i4 [ 0, %entry ], [ %i.next, %loop ]
 223   %i.next = add i4 %i, 1
 224   %t = icmp slt i4 %i.next, %m
 225   br i1 %t, label %loop, label %exit
 226 exit:
 227   ret void
 228 }
 229
 230 ; CHECK: Determining loop execution counts for: @even_step2
 231 ; CHECK: Loop %loop: backedge-taken count is ((-1 + (2 * %n)) /u 2)
 232 ; CHECK: Loop %loop: max backedge-taken count is 2
 233 define void @even_step2(i4 %n) {
 234 entry:
 235   %m = shl i4 %n, 1
 236   %s = icmp sgt i4 %m, 0
 237   br i1 %s, label %loop, label %exit
 238 loop:
 239   %i = phi i4 [ 0, %entry ], [ %i.next, %loop ]
 240   %i.next = add i4 %i, 2
 241   %t = icmp slt i4 %i.next, %m
 242   br i1 %t, label %loop, label %exit
 243 exit:
 244   ret void
 245 }
 246
 247 ; CHECK: Determining loop execution counts for: @even_start1
 248 ; CHECK: Loop %loop: backedge-taken count is (-2 + (2 smax (2 * %n)))
 249 ; CHECK: Loop %loop: max backedge-taken count is 4
 250 define void @even_start1(i4 %n) {
 251 entry:
 252   %m = shl i4 %n, 1
 253   %s = icmp sgt i4 %m, 0
 254   br i1 %s, label %loop, label %exit
 255 loop:
 256   %i = phi i4 [ 1, %entry ], [ %i.next, %loop ]
 257   %i.next = add i4 %i, 1
 258   %t = icmp slt i4 %i.next, %m
 259   br i1 %t, label %loop, label %exit
 260 exit:
 261   ret void
 262 }
 263
 264 ; CHECK: Determining loop execution counts for: @even_start1_step2
 265 ; CHECK: Loop %loop: backedge-taken count is ((-2 + (3 smax (2 * %n))) /u 2)
 266 ; CHECK: Loop %loop: max backedge-taken count is 2
 267 define void @even_start1_step2(i4 %n) {
 268 entry:
 269   %m = shl i4 %n, 1
 270   %s = icmp sgt i4 %m, 0
 271   br i1 %s, label %loop, label %exit
 272 loop:
 273   %i = phi i4 [ 1, %entry ], [ %i.next, %loop ]
 274   %i.next = add i4 %i, 2
 275   %t = icmp slt i4 %i.next, %m
 276   br i1 %t, label %loop, label %exit
 277 exit:
 278   ret void
 279 }
 280
 281 ; CHECK: Determining loop execution counts for: @even_startx
 282 ; CHECK: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax (2 * %n)))
 283 ; CHECK: Loop %loop: max backedge-taken count is -2
 284 define void @even_startx(i4 %n, i4 %x) {
 285 entry:
 286   %m = shl i4 %n, 1
 287   %s = icmp sgt i4 %m, 0
 288   br i1 %s, label %loop, label %exit
 289 loop:
 290   %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]
 291   %i.next = add i4 %i, 1
 292   %t = icmp slt i4 %i.next, %m
 293   br i1 %t, label %loop, label %exit
 294 exit:
 295   ret void
 296 }
 297
 298 ; CHECK: Determining loop execution counts for: @even_startx_step2
 299 ; CHECK: Loop %loop: backedge-taken count is ((-1 + (-1 * %x) + ((2 + %x) smax (2 * %n))) /u 2)
 300 ; CHECK: Loop %loop: max backedge-taken count is 7
 301 define void @even_startx_step2(i4 %n, i4 %x) {
 302 entry:
 303   %m = shl i4 %n, 1
 304   %s = icmp sgt i4 %m, 0
 305   br i1 %s, label %loop, label %exit
 306 loop:
 307   %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]
 308   %i.next = add i4 %i, 2
 309   %t = icmp slt i4 %i.next, %m
 310   br i1 %t, label %loop, label %exit
 311 exit:
 312   ret void
 313 }
 314
 315 ; CHECK: Determining loop execution counts for: @even_nsw
 316 ; CHECK: Loop %loop: backedge-taken count is (-1 + (2 * %n))
 317 ; CHECK: Loop %loop: max backedge-taken count is 5
 318 define void @even_nsw(i4 %n) {
 319 entry:
 320   %m = shl i4 %n, 1
 321   %s = icmp sgt i4 %m, 0
 322   br i1 %s, label %loop, label %exit
 323 loop:
 324   %i = phi i4 [ 0, %entry ], [ %i.next, %loop ]
 325   %i.next = add nsw i4 %i, 1
 326   %t = icmp slt i4 %i.next, %m
 327   br i1 %t, label %loop, label %exit
 328 exit:
 329   ret void
 330 }
 331
 332 ; CHECK: Determining loop execution counts for: @even_nsw_step2
 333 ; CHECK: Loop %loop: backedge-taken count is ((-1 + (2 * %n)) /u 2)
 334 ; CHECK: Loop %loop: max backedge-taken count is 2
 335 define void @even_nsw_step2(i4 %n) {
 336 entry:
 337   %m = shl i4 %n, 1
 338   %s = icmp sgt i4 %m, 0
 339   br i1 %s, label %loop, label %exit
 340 loop:
 341   %i = phi i4 [ 0, %entry ], [ %i.next, %loop ]
 342   %i.next = add nsw i4 %i, 2
 343   %t = icmp slt i4 %i.next, %m
 344   br i1 %t, label %loop, label %exit
 345 exit:
 346   ret void
 347 }
 348
 349 ; CHECK: Determining loop execution counts for: @even_nsw_start1
 350 ; CHECK: Loop %loop: backedge-taken count is (-2 + (2 smax (2 * %n)))
 351 ; CHECK: Loop %loop: max backedge-taken count is 4
 352 define void @even_nsw_start1(i4 %n) {
 353 entry:
 354   %m = shl i4 %n, 1
 355   %s = icmp sgt i4 %m, 0
 356   br i1 %s, label %loop, label %exit
 357 loop:
 358   %i = phi i4 [ 1, %entry ], [ %i.next, %loop ]
 359   %i.next = add nsw i4 %i, 1
 360   %t = icmp slt i4 %i.next, %m
 361   br i1 %t, label %loop, label %exit
 362 exit:
 363   ret void
 364 }
 365
 366 ; CHECK: Determining loop execution counts for: @even_nsw_start1_step2
 367 ; CHECK: Loop %loop: backedge-taken count is ((-2 + (3 smax (2 * %n))) /u 2)
 368 ; CHECK: Loop %loop: max backedge-taken count is 2
 369 define void @even_nsw_start1_step2(i4 %n) {
 370 entry:
 371   %m = shl i4 %n, 1
 372   %s = icmp sgt i4 %m, 0
 373   br i1 %s, label %loop, label %exit
 374 loop:
 375   %i = phi i4 [ 1, %entry ], [ %i.next, %loop ]
 376   %i.next = add nsw i4 %i, 2
 377   %t = icmp slt i4 %i.next, %m
 378   br i1 %t, label %loop, label %exit
 379 exit:
 380   ret void
 381 }
 382
 383 ; CHECK: Determining loop execution counts for: @even_nsw_startx
 384 ; CHECK: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax (2 * %n)))
 385 ; CHECK: Loop %loop: max backedge-taken count is -2
 386 define void @even_nsw_startx(i4 %n, i4 %x) {
 387 entry:
 388   %m = shl i4 %n, 1
 389   %s = icmp sgt i4 %m, 0
 390   br i1 %s, label %loop, label %exit
 391 loop:
 392   %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]
 393   %i.next = add nsw i4 %i, 1
 394   %t = icmp slt i4 %i.next, %m
 395   br i1 %t, label %loop, label %exit
 396 exit:
 397   ret void
 398 }
 399
 400 ; CHECK: Determining loop execution counts for: @even_nsw_startx_step2
 401 ; CHECK: Loop %loop: backedge-taken count is ((-1 + (-1 * %x) + ((2 + %x) smax (2 * %n))) /u 2)
 402 ; CHECK: Loop %loop: max backedge-taken count is 7
 403 define void @even_nsw_startx_step2(i4 %n, i4 %x) {
 404 entry:
 405   %m = shl i4 %n, 1
 406   %s = icmp sgt i4 %m, 0
 407   br i1 %s, label %loop, label %exit
 408 loop:
 409   %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]
 410   %i.next = add nsw i4 %i, 2
 411   %t = icmp slt i4 %i.next, %m
 412   br i1 %t, label %loop, label %exit
 413 exit:
 414   ret void
 415 }