llvm/test/Analysis/ScalarEvolution/finite-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-max-iterations=0  -scalar-evolution-classify-expressions=0  2>&1 | FileCheck %s
   3
   4 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
   5 target triple = "x86_64-unknown-linux-gnu"
   6
   7 declare void @non_exit_use(i32 %i) #0
   8
   9 define void @sle_pre_inc(i32 %len) willreturn {
  10 ; CHECK-LABEL: 'sle_pre_inc'
  11 ; CHECK-NEXT:  Determining loop execution counts for: @sle_pre_inc
  12 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is (0 smax (1 + %len))
  13 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is 2147483647
  14 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (0 smax (1 + %len))
  15 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (0 smax (1 + %len))
  16 ; CHECK-NEXT:   Predicates:
  17 ; CHECK-NEXT:  Loop %for.body: Trip multiple is 1
  18 ;
  19 entry:
  20   br label %for.body
  21
  22 for.body:
  23   %iv = phi i32 [ %inc, %for.body ], [ 0, %entry ]
  24   call void @non_exit_use(i32 %iv) nounwind willreturn
  25   %inc = add i32 %iv, 1
  26   %cmp = icmp sle i32 %iv, %len
  27   br i1 %cmp, label %for.body, label %for.end
  28
  29 for.end:
  30   ret void
  31 }
  32
  33 define void @sle_post_inc(i32 %len) willreturn {
  34 ; CHECK-LABEL: 'sle_post_inc'
  35 ; CHECK-NEXT:  Determining loop execution counts for: @sle_post_inc
  36 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + (1 smax (1 + %len)))<nsw>
  37 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is 2147483646
  38 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (-1 + (1 smax (1 + %len)))<nsw>
  39 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + (1 smax (1 + %len)))<nsw>
  40 ; CHECK-NEXT:   Predicates:
  41 ; CHECK-NEXT:  Loop %for.body: Trip multiple is 1
  42 ;
  43 entry:
  44   br label %for.body
  45
  46 for.body:
  47   %iv = phi i32 [ %inc, %for.body ], [ 0, %entry ]
  48   call void @non_exit_use(i32 %iv) nounwind willreturn
  49   %inc = add i32 %iv, 1
  50   %cmp = icmp sle i32 %inc, %len
  51   br i1 %cmp, label %for.body, label %for.end
  52
  53 for.end:
  54   ret void
  55 }
  56
  57 define void @sle_pre_inc_infinite(i32 %len) {
  58 ; CHECK-LABEL: 'sle_pre_inc_infinite'
  59 ; CHECK-NEXT:  Determining loop execution counts for: @sle_pre_inc_infinite
  60 ; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
  61 ; CHECK-NEXT:  Loop %for.body: Unpredictable constant max backedge-taken count.
  62 ; CHECK-NEXT:  Loop %for.body: Unpredictable symbolic max backedge-taken count.
  63 ; CHECK-NEXT:  Loop %for.body: Unpredictable predicated backedge-taken count.
  64 ;
  65 entry:
  66   br label %for.body
  67
  68 for.body:
  69   %iv = phi i32 [ %inc, %for.body ], [ 0, %entry ]
  70   call void @non_exit_use(i32 %iv) nounwind willreturn
  71   %inc = add i32 %iv, 1
  72   %cmp = icmp sle i32 %iv, %len
  73   br i1 %cmp, label %for.body, label %for.end
  74
  75 for.end:
  76   ret void
  77 }
  78
  79 define void @ule_pre_inc(i32 %len) willreturn {
  80 ; CHECK-LABEL: 'ule_pre_inc'
  81 ; CHECK-NEXT:  Determining loop execution counts for: @ule_pre_inc
  82 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is (1 + %len)
  83 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is -1
  84 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (1 + %len)
  85 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (1 + %len)
  86 ; CHECK-NEXT:   Predicates:
  87 ; CHECK-NEXT:  Loop %for.body: Trip multiple is 1
  88 ;
  89 entry:
  90   br label %for.body
  91
  92 for.body:
  93   %iv = phi i32 [ %inc, %for.body ], [ 0, %entry ]
  94   call void @non_exit_use(i32 %iv) nounwind willreturn
  95   %inc = add i32 %iv, 1
  96   %cmp = icmp ule i32 %iv, %len
  97   br i1 %cmp, label %for.body, label %for.end
  98
  99 for.end:
 100   ret void
 101 }
 102
 103 define void @ule_post_inc(i32 %len) willreturn {
 104 ; CHECK-LABEL: 'ule_post_inc'
 105 ; CHECK-NEXT:  Determining loop execution counts for: @ule_post_inc
 106 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + (1 umax (1 + %len)))
 107 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is -2
 108 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (-1 + (1 umax (1 + %len)))
 109 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + (1 umax (1 + %len)))
 110 ; CHECK-NEXT:   Predicates:
 111 ; CHECK-NEXT:  Loop %for.body: Trip multiple is 1
 112 ;
 113 entry:
 114   br label %for.body
 115
 116 for.body:
 117   %iv = phi i32 [ %inc, %for.body ], [ 0, %entry ]
 118   call void @non_exit_use(i32 %iv) nounwind willreturn
 119   %inc = add i32 %iv, 1
 120   %cmp = icmp ule i32 %inc, %len
 121   br i1 %cmp, label %for.body, label %for.end
 122
 123 for.end:
 124   ret void
 125 }
 126
 127 define void @ule_pre_inc_infinite(i32 %len) {
 128 ; CHECK-LABEL: 'ule_pre_inc_infinite'
 129 ; CHECK-NEXT:  Determining loop execution counts for: @ule_pre_inc_infinite
 130 ; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
 131 ; CHECK-NEXT:  Loop %for.body: Unpredictable constant max backedge-taken count.
 132 ; CHECK-NEXT:  Loop %for.body: Unpredictable symbolic max backedge-taken count.
 133 ; CHECK-NEXT:  Loop %for.body: Unpredictable predicated backedge-taken count.
 134 ;
 135 entry:
 136   br label %for.body
 137
 138 for.body:
 139   %iv = phi i32 [ %inc, %for.body ], [ 0, %entry ]
 140   call void @non_exit_use(i32 %iv) nounwind willreturn
 141   %inc = add i32 %iv, 1
 142   %cmp = icmp ule i32 %iv, %len
 143   br i1 %cmp, label %for.body, label %for.end
 144
 145 for.end:
 146   ret void
 147 }
 148
 149 define void @sge_pre_inc(i32 %end) willreturn {
 150 ; CHECK-LABEL: 'sge_pre_inc'
 151 ; CHECK-NEXT:  Determining loop execution counts for: @sge_pre_inc
 152 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is (100 + (-1 * (100 smin (-1 + %end))))
 153 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is -2147483548
 154 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (100 + (-1 * (100 smin (-1 + %end))))
 155 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (100 + (-1 * (100 smin (-1 + %end))))
 156 ; CHECK-NEXT:   Predicates:
 157 ; CHECK-NEXT:  Loop %for.body: Trip multiple is 1
 158 ;
 159 entry:
 160   br label %for.body
 161
 162 for.body:
 163   %iv = phi i32 [ %inc, %for.body ], [ 100, %entry ]
 164   call void @non_exit_use(i32 %iv) nounwind willreturn
 165   %inc = add i32 %iv, -1
 166   %cmp = icmp sge i32 %iv, %end
 167   br i1 %cmp, label %for.body, label %for.end
 168
 169 for.end:
 170   ret void
 171 }
 172
 173 define void @sge_post_inc(i32 %end) willreturn {
 174 ; CHECK-LABEL: 'sge_post_inc'
 175 ; CHECK-NEXT:  Determining loop execution counts for: @sge_post_inc
 176 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is (100 + (-1 * (100 smin (-1 + %end))))
 177 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is -2147483548
 178 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (100 + (-1 * (100 smin (-1 + %end))))
 179 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (100 + (-1 * (100 smin (-1 + %end))))
 180 ; CHECK-NEXT:   Predicates:
 181 ; CHECK-NEXT:  Loop %for.body: Trip multiple is 1
 182 ;
 183 entry:
 184   br label %for.body
 185
 186 for.body:
 187   %iv = phi i32 [ %inc, %for.body ], [ 100, %entry ]
 188   call void @non_exit_use(i32 %iv) nounwind willreturn
 189   %inc = add i32 %iv, -1
 190   %cmp = icmp sge i32 %iv, %end
 191   br i1 %cmp, label %for.body, label %for.end
 192
 193 for.end:
 194   ret void
 195 }
 196
 197 define void @sge_pre_inc_infinite(i32 %end) {
 198 ; CHECK-LABEL: 'sge_pre_inc_infinite'
 199 ; CHECK-NEXT:  Determining loop execution counts for: @sge_pre_inc_infinite
 200 ; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
 201 ; CHECK-NEXT:  Loop %for.body: Unpredictable constant max backedge-taken count.
 202 ; CHECK-NEXT:  Loop %for.body: Unpredictable symbolic max backedge-taken count.
 203 ; CHECK-NEXT:  Loop %for.body: Unpredictable predicated backedge-taken count.
 204 ;
 205 entry:
 206   br label %for.body
 207
 208 for.body:
 209   %iv = phi i32 [ %inc, %for.body ], [ 100, %entry ]
 210   call void @non_exit_use(i32 %iv) nounwind willreturn
 211   %inc = add i32 %iv, -1
 212   %cmp = icmp sge i32 %iv, %end
 213   br i1 %cmp, label %for.body, label %for.end
 214
 215 for.end:
 216   ret void
 217 }
 218
 219 define void @use_pre_inc(i32 %end) willreturn {
 220 ; CHECK-LABEL: 'use_pre_inc'
 221 ; CHECK-NEXT:  Determining loop execution counts for: @use_pre_inc
 222 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is (100 + (-1 * (100 umin (-1 + %end)))<nsw>)<nsw>
 223 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is 100
 224 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (100 + (-1 * (100 umin (-1 + %end)))<nsw>)<nsw>
 225 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (100 + (-1 * (100 umin (-1 + %end)))<nsw>)<nsw>
 226 ; CHECK-NEXT:   Predicates:
 227 ; CHECK-NEXT:  Loop %for.body: Trip multiple is 1
 228 ;
 229 entry:
 230   br label %for.body
 231
 232 for.body:
 233   %iv = phi i32 [ %inc, %for.body ], [ 100, %entry ]
 234   call void @non_exit_use(i32 %iv) nounwind willreturn
 235   %inc = add i32 %iv, -1
 236   %cmp = icmp uge i32 %iv, %end
 237   br i1 %cmp, label %for.body, label %for.end
 238
 239 for.end:
 240   ret void
 241 }
 242
 243 define void @use_post_inc(i32 %end) willreturn {
 244 ; CHECK-LABEL: 'use_post_inc'
 245 ; CHECK-NEXT:  Determining loop execution counts for: @use_post_inc
 246 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is (99 + (-1 * (99 umin (-1 + %end)))<nsw>)<nsw>
 247 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is 99
 248 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (99 + (-1 * (99 umin (-1 + %end)))<nsw>)<nsw>
 249 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (99 + (-1 * (99 umin (-1 + %end)))<nsw>)<nsw>
 250 ; CHECK-NEXT:   Predicates:
 251 ; CHECK-NEXT:  Loop %for.body: Trip multiple is 1
 252 ;
 253 entry:
 254   br label %for.body
 255
 256 for.body:
 257   %iv = phi i32 [ %inc, %for.body ], [ 100, %entry ]
 258   call void @non_exit_use(i32 %iv) nounwind willreturn
 259   %inc = add i32 %iv, -1
 260   %cmp = icmp uge i32 %inc, %end
 261   br i1 %cmp, label %for.body, label %for.end
 262
 263 for.end:
 264   ret void
 265 }
 266
 267 define void @uge_pre_inc_infinite(i32 %end) {
 268 ; CHECK-LABEL: 'uge_pre_inc_infinite'
 269 ; CHECK-NEXT:  Determining loop execution counts for: @uge_pre_inc_infinite
 270 ; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
 271 ; CHECK-NEXT:  Loop %for.body: Unpredictable constant max backedge-taken count.
 272 ; CHECK-NEXT:  Loop %for.body: Unpredictable symbolic max backedge-taken count.
 273 ; CHECK-NEXT:  Loop %for.body: Unpredictable predicated backedge-taken count.
 274 ;
 275 entry:
 276   br label %for.body
 277
 278 for.body:
 279   %iv = phi i32 [ %inc, %for.body ], [ 100, %entry ]
 280   call void @non_exit_use(i32 %iv) nounwind willreturn
 281   %inc = add i32 %iv, -1
 282   %cmp = icmp uge i32 %iv, %end
 283   br i1 %cmp, label %for.body, label %for.end
 284
 285 for.end:
 286   ret void
 287 }
 288
 289 define void @pr54191(i64 %n) mustprogress {
 290 ; CHECK-LABEL: 'pr54191'
 291 ; CHECK-NEXT:  Determining loop execution counts for: @pr54191
 292 ; CHECK-NEXT:  Loop %loop: backedge-taken count is ((-2 + %n) /u 2)
 293 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 4611686018427387902
 294 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((-2 + %n) /u 2)
 295 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is ((-2 + %n) /u 2)
 296 ; CHECK-NEXT:   Predicates:
 297 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
 298 ;
 299 entry:
 300   %guard = icmp sgt i64 %n, 1
 301   br i1 %guard, label %loop, label %exit
 302
 303 loop:
 304   %iv = phi i64 [ 2, %entry ], [ %iv.next, %loop ]
 305   %iv.next = add nuw nsw i64 %iv, 2
 306   %cmp = icmp sle i64 %iv.next, %n
 307   br i1 %cmp, label %loop, label %exit
 308
 309 exit:
 310   ret void
 311 }