llvm/test/Analysis/ScalarEvolution/overflow-intrinsics-trip-count.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 declare { i16, i1 } @llvm.sadd.with.overflow.i16(i16, i16) nounwind readnone
   5 declare { i16, i1 } @llvm.uadd.with.overflow.i16(i16, i16) nounwind readnone
   6 declare { i16, i1 } @llvm.ssub.with.overflow.i16(i16, i16) nounwind readnone
   7 declare { i16, i1 } @llvm.usub.with.overflow.i16(i16, i16) nounwind readnone
   8 declare { i16, i1 } @llvm.smul.with.overflow.i16(i16, i16) nounwind readnone
   9 declare { i16, i1 } @llvm.umul.with.overflow.i16(i16, i16) nounwind readnone
  10
  11 define void @uadd_exhaustive() {
  12 ; CHECK-LABEL: 'uadd_exhaustive'
  13 ; CHECK-NEXT:  Determining loop execution counts for: @uadd_exhaustive
  14 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is 35
  15 ; CHECK-NEXT:  Loop %for.body: max backedge-taken count is 35
  16 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is 35
  17 ; CHECK-NEXT:   Predicates:
  18 ; CHECK:       Loop %for.body: Trip multiple is 36
  19 ;
  20 entry:
  21   br i1 undef, label %for.end, label %for.body.preheader
  22
  23 for.body.preheader:                               ; preds = %entry
  24   br label %for.body
  25
  26 for.body:                                         ; preds = %for.body.preheader, %for.body
  27   %indvars.iv = phi i16 [ %math, %for.body ], [ 65500, %for.body.preheader ]
  28   %0 = call { i16, i1 } @llvm.uadd.with.overflow.i16(i16 %indvars.iv, i16 1)
  29   %math = extractvalue { i16, i1 } %0, 0
  30   %ov = extractvalue { i16, i1 } %0, 1
  31   br i1 %ov, label %for.end, label %for.body
  32
  33 for.end:                                          ; preds = %for.body, %entry
  34   ret void
  35 }
  36
  37 define void @sadd_exhaustive() {
  38 ; CHECK-LABEL: 'sadd_exhaustive'
  39 ; CHECK-NEXT:  Determining loop execution counts for: @sadd_exhaustive
  40 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is 67
  41 ; CHECK-NEXT:  Loop %for.body: max backedge-taken count is 67
  42 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is 67
  43 ; CHECK-NEXT:   Predicates:
  44 ; CHECK:       Loop %for.body: Trip multiple is 68
  45 ;
  46 entry:
  47   br i1 undef, label %for.end, label %for.body.preheader
  48
  49 for.body.preheader:                               ; preds = %entry
  50   br label %for.body
  51
  52 for.body:                                         ; preds = %for.body.preheader, %for.body
  53   %indvars.iv = phi i16 [ %math, %for.body ], [ 32700, %for.body.preheader ]
  54   %0 = call { i16, i1 } @llvm.sadd.with.overflow.i16(i16 %indvars.iv, i16 1)
  55   %math = extractvalue { i16, i1 } %0, 0
  56   %ov = extractvalue { i16, i1 } %0, 1
  57   br i1 %ov, label %for.end, label %for.body
  58
  59 for.end:                                          ; preds = %for.body, %entry
  60   ret void
  61 }
  62
  63 define void @usub_exhaustive() {
  64 ; CHECK-LABEL: 'usub_exhaustive'
  65 ; CHECK-NEXT:  Determining loop execution counts for: @usub_exhaustive
  66 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is 50
  67 ; CHECK-NEXT:  Loop %for.body: max backedge-taken count is 50
  68 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is 50
  69 ; CHECK-NEXT:   Predicates:
  70 ; CHECK:       Loop %for.body: Trip multiple is 51
  71 ;
  72 entry:
  73   br i1 undef, label %for.end, label %for.body.preheader
  74
  75 for.body.preheader:                               ; preds = %entry
  76   br label %for.body
  77
  78 for.body:                                         ; preds = %for.body.preheader, %for.body
  79   %indvars.iv = phi i16 [ %math, %for.body ], [ 50, %for.body.preheader ]
  80   %0 = call { i16, i1 } @llvm.usub.with.overflow.i16(i16 %indvars.iv, i16 1)
  81   %math = extractvalue { i16, i1 } %0, 0
  82   %ov = extractvalue { i16, i1 } %0, 1
  83   br i1 %ov, label %for.end, label %for.body
  84
  85 for.end:                                          ; preds = %for.body, %entry
  86   ret void
  87 }
  88
  89 define void @ssub_exhaustive() {
  90 ; CHECK-LABEL: 'ssub_exhaustive'
  91 ; CHECK-NEXT:  Determining loop execution counts for: @ssub_exhaustive
  92 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is 68
  93 ; CHECK-NEXT:  Loop %for.body: max backedge-taken count is 68
  94 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is 68
  95 ; CHECK-NEXT:   Predicates:
  96 ; CHECK:       Loop %for.body: Trip multiple is 69
  97 ;
  98 entry:
  99   br i1 undef, label %for.end, label %for.body.preheader
 100
 101 for.body.preheader:                               ; preds = %entry
 102   br label %for.body
 103
 104 for.body:                                         ; preds = %for.body.preheader, %for.body
 105   %indvars.iv = phi i16 [ %math, %for.body ], [ -32700, %for.body.preheader ]
 106   %0 = call { i16, i1 } @llvm.ssub.with.overflow.i16(i16 %indvars.iv, i16 1)
 107   %math = extractvalue { i16, i1 } %0, 0
 108   %ov = extractvalue { i16, i1 } %0, 1
 109   br i1 %ov, label %for.end, label %for.body
 110
 111 for.end:                                          ; preds = %for.body, %entry
 112   ret void
 113 }
 114
 115 define void @smul_exhaustive() {
 116 ; CHECK-LABEL: 'smul_exhaustive'
 117 ; CHECK-NEXT:  Determining loop execution counts for: @smul_exhaustive
 118 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is 14
 119 ; CHECK-NEXT:  Loop %for.body: max backedge-taken count is 14
 120 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is 14
 121 ; CHECK-NEXT:   Predicates:
 122 ; CHECK:       Loop %for.body: Trip multiple is 15
 123 ;
 124 entry:
 125   br i1 undef, label %for.end, label %for.body.preheader
 126
 127 for.body.preheader:                               ; preds = %entry
 128   br label %for.body
 129
 130 for.body:                                         ; preds = %for.body.preheader, %for.body
 131   %indvars.iv = phi i16 [ %math, %for.body ], [ 1, %for.body.preheader ]
 132   %0 = call { i16, i1 } @llvm.smul.with.overflow.i16(i16 %indvars.iv, i16 2)
 133   %math = extractvalue { i16, i1 } %0, 0
 134   %ov = extractvalue { i16, i1 } %0, 1
 135   br i1 %ov, label %for.end, label %for.body
 136
 137 for.end:                                          ; preds = %for.body, %entry
 138   ret void
 139 }
 140
 141 define void @umul_exhaustive() {
 142 ; CHECK-LABEL: 'umul_exhaustive'
 143 ; CHECK-NEXT:  Determining loop execution counts for: @umul_exhaustive
 144 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is 15
 145 ; CHECK-NEXT:  Loop %for.body: max backedge-taken count is 15
 146 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is 15
 147 ; CHECK-NEXT:   Predicates:
 148 ; CHECK:       Loop %for.body: Trip multiple is 16
 149 ;
 150 entry:
 151   br i1 undef, label %for.end, label %for.body.preheader
 152
 153 for.body.preheader:                               ; preds = %entry
 154   br label %for.body
 155
 156 for.body:                                         ; preds = %for.body.preheader, %for.body
 157   %indvars.iv = phi i16 [ %math, %for.body ], [ 1, %for.body.preheader ]
 158   %0 = call { i16, i1 } @llvm.umul.with.overflow.i16(i16 %indvars.iv, i16 2)
 159   %math = extractvalue { i16, i1 } %0, 0
 160   %ov = extractvalue { i16, i1 } %0, 1
 161   br i1 %ov, label %for.end, label %for.body
 162
 163 for.end:                                          ; preds = %for.body, %entry
 164   ret void
 165 }
 166
 167 define void @uadd_symbolic_start(i16 %start) {
 168 ; CHECK-LABEL: 'uadd_symbolic_start'
 169 ; CHECK-NEXT:  Determining loop execution counts for: @uadd_symbolic_start
 170 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + (-1 * %start))
 171 ; CHECK-NEXT:  Loop %for.body: max backedge-taken count is -1
 172 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + (-1 * %start))
 173 ; CHECK-NEXT:   Predicates:
 174 ; CHECK:       Loop %for.body: Trip multiple is 1
 175 ;
 176 entry:
 177   br i1 undef, label %for.end, label %for.body.preheader
 178
 179 for.body.preheader:                               ; preds = %entry
 180   br label %for.body
 181
 182 for.body:                                         ; preds = %for.body.preheader, %for.body
 183   %indvars.iv = phi i16 [ %math, %for.body ], [ %start, %for.body.preheader ]
 184   %0 = call { i16, i1 } @llvm.uadd.with.overflow.i16(i16 %indvars.iv, i16 1)
 185   %math = extractvalue { i16, i1 } %0, 0
 186   %ov = extractvalue { i16, i1 } %0, 1
 187   br i1 %ov, label %for.end, label %for.body
 188
 189 for.end:                                          ; preds = %for.body, %entry
 190   ret void
 191 }
 192
 193 define void @sadd_symbolic_start(i16 %start) {
 194 ; CHECK-LABEL: 'sadd_symbolic_start'
 195 ; CHECK-NEXT:  Determining loop execution counts for: @sadd_symbolic_start
 196 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is (32767 + (-1 * %start))
 197 ; CHECK-NEXT:  Loop %for.body: max backedge-taken count is -1
 198 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (32767 + (-1 * %start))
 199 ; CHECK-NEXT:   Predicates:
 200 ; CHECK:       Loop %for.body: Trip multiple is 1
 201 ;
 202 entry:
 203   br i1 undef, label %for.end, label %for.body.preheader
 204
 205 for.body.preheader:                               ; preds = %entry
 206   br label %for.body
 207
 208 for.body:                                         ; preds = %for.body.preheader, %for.body
 209   %indvars.iv = phi i16 [ %math, %for.body ], [ %start, %for.body.preheader ]
 210   %0 = call { i16, i1 } @llvm.sadd.with.overflow.i16(i16 %indvars.iv, i16 1)
 211   %math = extractvalue { i16, i1 } %0, 0
 212   %ov = extractvalue { i16, i1 } %0, 1
 213   br i1 %ov, label %for.end, label %for.body
 214
 215 for.end:                                          ; preds = %for.body, %entry
 216   ret void
 217 }
 218
 219 define void @sadd_symbolic_start2(i16 %start) {
 220 ; CHECK-LABEL: 'sadd_symbolic_start2'
 221 ; CHECK-NEXT:  Determining loop execution counts for: @sadd_symbolic_start2
 222 ; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
 223 ; CHECK-NEXT:  Loop %for.body: Unpredictable max backedge-taken count.
 224 ; CHECK-NEXT:  Loop %for.body: Unpredictable predicated backedge-taken count.
 225 ;
 226 entry:
 227   br i1 undef, label %for.end, label %for.body.preheader
 228
 229 for.body.preheader:                               ; preds = %entry
 230   br label %for.body
 231
 232 for.body:                                         ; preds = %for.body.preheader, %for.body
 233   %indvars.iv = phi i16 [ %math, %for.body ], [ %start, %for.body.preheader ]
 234   %0 = call { i16, i1 } @llvm.sadd.with.overflow.i16(i16 %indvars.iv, i16 1)
 235   %math = extractvalue { i16, i1 } %0, 0
 236   %ov = extractvalue { i16, i1 } %0, 1
 237   %not = xor i1 true, %ov
 238   br i1 %not, label %for.body, label %for.end
 239
 240 for.end:                                          ; preds = %for.body, %entry
 241   ret void
 242 }
 243
 244 define void @sadd_symbolic_swapped(i16 %start) {
 245 ; CHECK-LABEL: 'sadd_symbolic_swapped'
 246 ; CHECK-NEXT:  Determining loop execution counts for: @sadd_symbolic_swapped
 247 ; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
 248 ; CHECK-NEXT:  Loop %for.body: Unpredictable max backedge-taken count.
 249 ; CHECK-NEXT:  Loop %for.body: Unpredictable predicated backedge-taken count.
 250 ;
 251 entry:
 252   br i1 undef, label %for.end, label %for.body.preheader
 253
 254 for.body.preheader:                               ; preds = %entry
 255   br label %for.body
 256
 257 for.body:                                         ; preds = %for.body.preheader, %for.body
 258   %indvars.iv = phi i16 [ %math, %for.body ], [ %start, %for.body.preheader ]
 259   %0 = call { i16, i1 } @llvm.sadd.with.overflow.i16(i16 %indvars.iv, i16 1)
 260   %math = extractvalue { i16, i1 } %0, 0
 261   %ov = extractvalue { i16, i1 } %0, 1
 262   br i1 %ov, label %for.body, label %for.end
 263
 264 for.end:                                          ; preds = %for.body, %entry
 265   ret void
 266 }
 267
 268 define void @usub_symbolic_start(i16 %start) {
 269 ; CHECK-LABEL: 'usub_symbolic_start'
 270 ; CHECK-NEXT:  Determining loop execution counts for: @usub_symbolic_start
 271 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is %start
 272 ; CHECK-NEXT:  Loop %for.body: max backedge-taken count is -1
 273 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is %start
 274 ; CHECK-NEXT:   Predicates:
 275 ; CHECK:       Loop %for.body: Trip multiple is 1
 276 ;
 277 entry:
 278   br i1 undef, label %for.end, label %for.body.preheader
 279
 280 for.body.preheader:                               ; preds = %entry
 281   br label %for.body
 282
 283 for.body:                                         ; preds = %for.body.preheader, %for.body
 284   %indvars.iv = phi i16 [ %math, %for.body ], [ %start, %for.body.preheader ]
 285   %0 = call { i16, i1 } @llvm.usub.with.overflow.i16(i16 %indvars.iv, i16 1)
 286   %math = extractvalue { i16, i1 } %0, 0
 287   %ov = extractvalue { i16, i1 } %0, 1
 288   br i1 %ov, label %for.end, label %for.body
 289
 290 for.end:                                          ; preds = %for.body, %entry
 291   ret void
 292 }
 293
 294 define void @ssub_symbolic_start(i16 %start) {
 295 ; CHECK-LABEL: 'ssub_symbolic_start'
 296 ; CHECK-NEXT:  Determining loop execution counts for: @ssub_symbolic_start
 297 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-32768 + %start)
 298 ; CHECK-NEXT:  Loop %for.body: max backedge-taken count is -1
 299 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-32768 + %start)
 300 ; CHECK-NEXT:   Predicates:
 301 ; CHECK:       Loop %for.body: Trip multiple is 1
 302 ;
 303 entry:
 304   br i1 undef, label %for.end, label %for.body.preheader
 305
 306 for.body.preheader:                               ; preds = %entry
 307   br label %for.body
 308
 309 for.body:                                         ; preds = %for.body.preheader, %for.body
 310   %indvars.iv = phi i16 [ %math, %for.body ], [ %start, %for.body.preheader ]
 311   %0 = call { i16, i1 } @llvm.ssub.with.overflow.i16(i16 %indvars.iv, i16 1)
 312   %math = extractvalue { i16, i1 } %0, 0
 313   %ov = extractvalue { i16, i1 } %0, 1
 314   br i1 %ov, label %for.end, label %for.body
 315
 316 for.end:                                          ; preds = %for.body, %entry
 317   ret void
 318 }
 319
 320 define void @smul_symbolic_start(i16 %start) {
 321 ; CHECK-LABEL: 'smul_symbolic_start'
 322 ; CHECK-NEXT:  Determining loop execution counts for: @smul_symbolic_start
 323 ; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
 324 ; CHECK-NEXT:  Loop %for.body: Unpredictable max backedge-taken count.
 325 ; CHECK-NEXT:  Loop %for.body: Unpredictable predicated backedge-taken count.
 326 ;
 327 entry:
 328   br i1 undef, label %for.end, label %for.body.preheader
 329
 330 for.body.preheader:                               ; preds = %entry
 331   br label %for.body
 332
 333 for.body:                                         ; preds = %for.body.preheader, %for.body
 334   %indvars.iv = phi i16 [ %math, %for.body ], [ %start, %for.body.preheader ]
 335   %0 = call { i16, i1 } @llvm.smul.with.overflow.i16(i16 %indvars.iv, i16 2)
 336   %math = extractvalue { i16, i1 } %0, 0
 337   %ov = extractvalue { i16, i1 } %0, 1
 338   br i1 %ov, label %for.end, label %for.body
 339
 340 for.end:                                          ; preds = %for.body, %entry
 341   ret void
 342 }
 343
 344 define void @umul_symbolic_start(i16 %start) {
 345 ; CHECK-LABEL: 'umul_symbolic_start'
 346 ; CHECK-NEXT:  Determining loop execution counts for: @umul_symbolic_start
 347 ; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
 348 ; CHECK-NEXT:  Loop %for.body: Unpredictable max backedge-taken count.
 349 ; CHECK-NEXT:  Loop %for.body: Unpredictable predicated backedge-taken count.
 350 ;
 351 entry:
 352   br i1 undef, label %for.end, label %for.body.preheader
 353
 354 for.body.preheader:                               ; preds = %entry
 355   br label %for.body
 356
 357 for.body:                                         ; preds = %for.body.preheader, %for.body
 358   %indvars.iv = phi i16 [ %math, %for.body ], [ %start, %for.body.preheader ]
 359   %0 = call { i16, i1 } @llvm.umul.with.overflow.i16(i16 %indvars.iv, i16 2)
 360   %math = extractvalue { i16, i1 } %0, 0
 361   %ov = extractvalue { i16, i1 } %0, 1
 362   br i1 %ov, label %for.end, label %for.body
 363
 364 for.end:                                          ; preds = %for.body, %entry
 365   ret void
 366 }
 367
 368 define void @sadd_symbolic_non_latch(i16 %start) {
 369 ; CHECK-LABEL: 'sadd_symbolic_non_latch'
 370 ; CHECK-NEXT:  Determining loop execution counts for: @sadd_symbolic_non_latch
 371 ; CHECK-NEXT:  Loop %for.body: <multiple exits> backedge-taken count is ((230 + (-1 * %start)) umin (32767 + (-1 * %start)))
 372 ; CHECK-NEXT:    exit count for for.body: (32767 + (-1 * %start))
 373 ; CHECK-NEXT:    exit count for for.latch: (230 + (-1 * %start))
 374 ; CHECK-NEXT:  Loop %for.body: max backedge-taken count is -1
 375 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is ((230 + (-1 * %start)) umin (32767 + (-1 * %start)))
 376 ; CHECK-NEXT:   Predicates:
 377 ; CHECK:       Loop %for.body: Trip multiple is 1
 378 ;
 379 entry:
 380   br i1 undef, label %for.end, label %for.body.preheader
 381
 382 for.body.preheader:                               ; preds = %entry
 383   br label %for.body
 384
 385 for.body:                                         ; preds = %for.body.preheader, %for.body
 386   %indvars.iv = phi i16 [ %math, %for.latch ], [ %start, %for.body.preheader ]
 387   %0 = call { i16, i1 } @llvm.sadd.with.overflow.i16(i16 %indvars.iv, i16 1)
 388   %math = extractvalue { i16, i1 } %0, 0
 389   %ov = extractvalue { i16, i1 } %0, 1
 390   br i1 %ov, label %for.end, label %for.latch
 391
 392 for.latch:
 393   %cmp = icmp eq i16 %math, 231
 394   br i1 %cmp, label %for.end, label %for.body
 395
 396 for.end:                                          ; preds = %for.body, %entry
 397   ret void
 398 }