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 ; Be careful with this one. If %n is INT4_MAX, %i.next will wrap. The nsw bit
 124 ; says that the result is undefined, but ScalarEvolution must respect that
 125 ; subsequent passes may result the undefined behavior in predictable ways.
 126 ; CHECK: Determining loop execution counts for: @nsw_step2
 127 ; CHECK: Loop %loop: Unpredictable backedge-taken count.
 128 ; CHECK: Loop %loop: Unpredictable max backedge-taken count.
 129 define void @nsw_step2(i4 %n) {
 130 entry:
 131   %s = icmp sgt i4 %n, 0
 132   br i1 %s, label %loop, label %exit
 133 loop:
 134   %i = phi i4 [ 0, %entry ], [ %i.next, %loop ]
 135   %i.next = add nsw i4 %i, 2
 136   %t = icmp slt i4 %i.next, %n
 137   br i1 %t, label %loop, label %exit
 138 exit:
 139   ret void
 140 }
 141
 142 ; CHECK: Determining loop execution counts for: @nsw_start1
 143 ; CHECK: Loop %loop: backedge-taken count is (-2 + (2 smax %n))
 144 ; CHECK: Loop %loop: max backedge-taken count is 5
 145 define void @nsw_start1(i4 %n) {
 146 entry:
 147   %s = icmp sgt i4 %n, 0
 148   br i1 %s, label %loop, label %exit
 149 loop:
 150   %i = phi i4 [ 1, %entry ], [ %i.next, %loop ]
 151   %i.next = add nsw i4 %i, 1
 152   %t = icmp slt i4 %i.next, %n
 153   br i1 %t, label %loop, label %exit
 154 exit:
 155   ret void
 156 }
 157
 158 ; CHECK: Determining loop execution counts for: @nsw_start1_step2
 159 ; CHECK: Loop %loop: Unpredictable backedge-taken count.
 160 ; CHECK: Loop %loop: Unpredictable max backedge-taken count.
 161 define void @nsw_start1_step2(i4 %n) {
 162 entry:
 163   %s = icmp sgt i4 %n, 0
 164   br i1 %s, label %loop, label %exit
 165 loop:
 166   %i = phi i4 [ 1, %entry ], [ %i.next, %loop ]
 167   %i.next = add nsw i4 %i, 2
 168   %t = icmp slt i4 %i.next, %n
 169   br i1 %t, label %loop, label %exit
 170 exit:
 171   ret void
 172 }
 173
 174 ; CHECK: Determining loop execution counts for: @nsw_startx
 175 ; CHECK: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax %n))
 176 ; CHECK: Loop %loop: max backedge-taken count is -1
 177 define void @nsw_startx(i4 %n, i4 %x) {
 178 entry:
 179   %s = icmp sgt i4 %n, 0
 180   br i1 %s, label %loop, label %exit
 181 loop:
 182   %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]
 183   %i.next = add nsw i4 %i, 1
 184   %t = icmp slt i4 %i.next, %n
 185   br i1 %t, label %loop, label %exit
 186 exit:
 187   ret void
 188 }
 189
 190 ; CHECK: Determining loop execution counts for: @nsw_startx_step2
 191 ; CHECK: Loop %loop: Unpredictable backedge-taken count.
 192 ; CHECK: Loop %loop: Unpredictable max backedge-taken count.
 193 define void @nsw_startx_step2(i4 %n, i4 %x) {
 194 entry:
 195   %s = icmp sgt i4 %n, 0
 196   br i1 %s, label %loop, label %exit
 197 loop:
 198   %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]
 199   %i.next = add nsw i4 %i, 2
 200   %t = icmp slt i4 %i.next, %n
 201   br i1 %t, label %loop, label %exit
 202 exit:
 203   ret void
 204 }
 205
 206 ; CHECK: Determining loop execution counts for: @even
 207 ; CHECK: Loop %loop: backedge-taken count is (-1 + (2 * %n))
 208 ; CHECK: Loop %loop: max backedge-taken count is 5
 209 define void @even(i4 %n) {
 210 entry:
 211   %m = shl i4 %n, 1
 212   %s = icmp sgt i4 %m, 0
 213   br i1 %s, label %loop, label %exit
 214 loop:
 215   %i = phi i4 [ 0, %entry ], [ %i.next, %loop ]
 216   %i.next = add i4 %i, 1
 217   %t = icmp slt i4 %i.next, %m
 218   br i1 %t, label %loop, label %exit
 219 exit:
 220   ret void
 221 }
 222
 223 ; CHECK: Determining loop execution counts for: @even_step2
 224 ; CHECK: Loop %loop: Unpredictable backedge-taken count.
 225 ; CHECK: Loop %loop: max backedge-taken count is 2
 226 define void @even_step2(i4 %n) {
 227 entry:
 228   %m = shl i4 %n, 1
 229   %s = icmp sgt i4 %m, 0
 230   br i1 %s, label %loop, label %exit
 231 loop:
 232   %i = phi i4 [ 0, %entry ], [ %i.next, %loop ]
 233   %i.next = add i4 %i, 2
 234   %t = icmp slt i4 %i.next, %m
 235   br i1 %t, label %loop, label %exit
 236 exit:
 237   ret void
 238 }
 239
 240 ; CHECK: Determining loop execution counts for: @even_start1
 241 ; CHECK: Loop %loop: backedge-taken count is (-2 + (2 smax (2 * %n)))
 242 ; CHECK: Loop %loop: max backedge-taken count is 4
 243 define void @even_start1(i4 %n) {
 244 entry:
 245   %m = shl i4 %n, 1
 246   %s = icmp sgt i4 %m, 0
 247   br i1 %s, label %loop, label %exit
 248 loop:
 249   %i = phi i4 [ 1, %entry ], [ %i.next, %loop ]
 250   %i.next = add i4 %i, 1
 251   %t = icmp slt i4 %i.next, %m
 252   br i1 %t, label %loop, label %exit
 253 exit:
 254   ret void
 255 }
 256
 257 ; CHECK: Determining loop execution counts for: @even_start1_step2
 258 ; CHECK: Loop %loop: Unpredictable backedge-taken count.
 259 ; CHECK: Loop %loop: max backedge-taken count is 2
 260 define void @even_start1_step2(i4 %n) {
 261 entry:
 262   %m = shl i4 %n, 1
 263   %s = icmp sgt i4 %m, 0
 264   br i1 %s, label %loop, label %exit
 265 loop:
 266   %i = phi i4 [ 1, %entry ], [ %i.next, %loop ]
 267   %i.next = add i4 %i, 2
 268   %t = icmp slt i4 %i.next, %m
 269   br i1 %t, label %loop, label %exit
 270 exit:
 271   ret void
 272 }
 273
 274 ; CHECK: Determining loop execution counts for: @even_startx
 275 ; CHECK: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax (2 * %n)))
 276 ; CHECK: Loop %loop: max backedge-taken count is -1
 277 define void @even_startx(i4 %n, i4 %x) {
 278 entry:
 279   %m = shl i4 %n, 1
 280   %s = icmp sgt i4 %m, 0
 281   br i1 %s, label %loop, label %exit
 282 loop:
 283   %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]
 284   %i.next = add i4 %i, 1
 285   %t = icmp slt i4 %i.next, %m
 286   br i1 %t, label %loop, label %exit
 287 exit:
 288   ret void
 289 }
 290
 291 ; CHECK: Determining loop execution counts for: @even_startx_step2
 292 ; CHECK: Loop %loop: Unpredictable backedge-taken count.
 293 ; CHECK: Loop %loop: max backedge-taken count is 7
 294 define void @even_startx_step2(i4 %n, i4 %x) {
 295 entry:
 296   %m = shl i4 %n, 1
 297   %s = icmp sgt i4 %m, 0
 298   br i1 %s, label %loop, label %exit
 299 loop:
 300   %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]
 301   %i.next = add i4 %i, 2
 302   %t = icmp slt i4 %i.next, %m
 303   br i1 %t, label %loop, label %exit
 304 exit:
 305   ret void
 306 }
 307
 308 ; CHECK: Determining loop execution counts for: @even_nsw
 309 ; CHECK: Loop %loop: backedge-taken count is (-1 + (2 * %n))
 310 ; CHECK: Loop %loop: max backedge-taken count is 5
 311 define void @even_nsw(i4 %n) {
 312 entry:
 313   %m = shl i4 %n, 1
 314   %s = icmp sgt i4 %m, 0
 315   br i1 %s, label %loop, label %exit
 316 loop:
 317   %i = phi i4 [ 0, %entry ], [ %i.next, %loop ]
 318   %i.next = add nsw i4 %i, 1
 319   %t = icmp slt i4 %i.next, %m
 320   br i1 %t, label %loop, label %exit
 321 exit:
 322   ret void
 323 }
 324
 325 ; CHECK: Determining loop execution counts for: @even_nsw_step2
 326 ; CHECK: Loop %loop: backedge-taken count is ((-1 + (2 * %n)) /u 2)
 327 ; CHECK: Loop %loop: max backedge-taken count is 2
 328 define void @even_nsw_step2(i4 %n) {
 329 entry:
 330   %m = shl i4 %n, 1
 331   %s = icmp sgt i4 %m, 0
 332   br i1 %s, label %loop, label %exit
 333 loop:
 334   %i = phi i4 [ 0, %entry ], [ %i.next, %loop ]
 335   %i.next = add nsw i4 %i, 2
 336   %t = icmp slt i4 %i.next, %m
 337   br i1 %t, label %loop, label %exit
 338 exit:
 339   ret void
 340 }
 341
 342 ; CHECK: Determining loop execution counts for: @even_nsw_start1
 343 ; CHECK: Loop %loop: backedge-taken count is (-2 + (2 smax (2 * %n)))
 344 ; CHECK: Loop %loop: max backedge-taken count is 4
 345 define void @even_nsw_start1(i4 %n) {
 346 entry:
 347   %m = shl i4 %n, 1
 348   %s = icmp sgt i4 %m, 0
 349   br i1 %s, label %loop, label %exit
 350 loop:
 351   %i = phi i4 [ 1, %entry ], [ %i.next, %loop ]
 352   %i.next = add nsw i4 %i, 1
 353   %t = icmp slt i4 %i.next, %m
 354   br i1 %t, label %loop, label %exit
 355 exit:
 356   ret void
 357 }
 358
 359 ; CHECK: Determining loop execution counts for: @even_nsw_start1_step2
 360 ; CHECK: Loop %loop: backedge-taken count is ((-2 + (3 smax (2 * %n))) /u 2)
 361 ; CHECK: Loop %loop: max backedge-taken count is 2
 362 define void @even_nsw_start1_step2(i4 %n) {
 363 entry:
 364   %m = shl i4 %n, 1
 365   %s = icmp sgt i4 %m, 0
 366   br i1 %s, label %loop, label %exit
 367 loop:
 368   %i = phi i4 [ 1, %entry ], [ %i.next, %loop ]
 369   %i.next = add nsw i4 %i, 2
 370   %t = icmp slt i4 %i.next, %m
 371   br i1 %t, label %loop, label %exit
 372 exit:
 373   ret void
 374 }
 375
 376 ; CHECK: Determining loop execution counts for: @even_nsw_startx
 377 ; CHECK: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax (2 * %n)))
 378 ; CHECK: Loop %loop: max backedge-taken count is -1
 379 define void @even_nsw_startx(i4 %n, i4 %x) {
 380 entry:
 381   %m = shl i4 %n, 1
 382   %s = icmp sgt i4 %m, 0
 383   br i1 %s, label %loop, label %exit
 384 loop:
 385   %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]
 386   %i.next = add nsw i4 %i, 1
 387   %t = icmp slt i4 %i.next, %m
 388   br i1 %t, label %loop, label %exit
 389 exit:
 390   ret void
 391 }
 392
 393 ; CHECK: Determining loop execution counts for: @even_nsw_startx_step2
 394 ; CHECK: Loop %loop: backedge-taken count is ((-1 + (-1 * %x) + ((2 + %x) smax (2 * %n))) /u 2)
 395 ; CHECK: Loop %loop: max backedge-taken count is 7
 396 define void @even_nsw_startx_step2(i4 %n, i4 %x) {
 397 entry:
 398   %m = shl i4 %n, 1
 399   %s = icmp sgt i4 %m, 0
 400   br i1 %s, label %loop, label %exit
 401 loop:
 402   %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]
 403   %i.next = add nsw i4 %i, 2
 404   %t = icmp slt i4 %i.next, %m
 405   br i1 %t, label %loop, label %exit
 406 exit:
 407   ret void
 408 }