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