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