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