llvm/test/Analysis/ScalarEvolution/exit-count-non-strict.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 4
   2 ; RUN: opt -disable-output "-passes=print<scalar-evolution>" -scalar-evolution-classify-expressions=0 < %s 2>&1 | FileCheck %s
   3
   4 define void @ule_from_zero(i32 %M, i32 %N) {
   5 ; CHECK-LABEL: 'ule_from_zero'
   6 ; CHECK-NEXT:  Determining loop execution counts for: @ule_from_zero
   7 ; CHECK-NEXT:  Loop %loop: <multiple exits> backedge-taken count is ((zext i32 %N to i64) umin (1 + (zext i32 %M to i64))<nuw><nsw>)
   8 ; CHECK-NEXT:    exit count for loop: (1 + (zext i32 %M to i64))<nuw><nsw>
   9 ; CHECK-NEXT:    exit count for latch: %N
  10 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i64 4294967295
  11 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((zext i32 %N to i64) umin (1 + (zext i32 %M to i64))<nuw><nsw>)
  12 ; CHECK-NEXT:    symbolic max exit count for loop: (1 + (zext i32 %M to i64))<nuw><nsw>
  13 ; CHECK-NEXT:    symbolic max exit count for latch: %N
  14 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
  15 ;
  16 entry:
  17   br label %loop
  18
  19 loop:
  20   %iv = phi i32 [ 0, %entry ], [ %iv.next, %latch ]
  21   %cmp1 = icmp ule i32 %iv, %M
  22   br i1 %cmp1, label %latch, label %exit
  23
  24 latch:
  25   %iv.next = add nuw i32 %iv, 1
  26   %exitcond.not = icmp eq i32 %iv, %N
  27   br i1 %exitcond.not, label %exit, label %loop
  28
  29 exit:
  30   ret void
  31 }
  32
  33 define void @ule_from_one(i32 %M, i32 %N) {
  34 ; CHECK-LABEL: 'ule_from_one'
  35 ; CHECK-NEXT:  Determining loop execution counts for: @ule_from_one
  36 ; CHECK-NEXT:  Loop %loop: <multiple exits> backedge-taken count is (%M umin_seq (-1 + %N))
  37 ; CHECK-NEXT:    exit count for loop: %M
  38 ; CHECK-NEXT:    exit count for latch: (-1 + %N)
  39 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 -1
  40 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (%M umin_seq (-1 + %N))
  41 ; CHECK-NEXT:    symbolic max exit count for loop: %M
  42 ; CHECK-NEXT:    symbolic max exit count for latch: (-1 + %N)
  43 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
  44 ;
  45 entry:
  46   br label %loop
  47
  48 loop:
  49   %iv = phi i32 [ 1, %entry ], [ %iv.next, %latch ]
  50   %cmp1 = icmp ule i32 %iv, %M
  51   br i1 %cmp1, label %latch, label %exit
  52
  53 latch:
  54   %iv.next = add nuw i32 %iv, 1
  55   %exitcond.not = icmp eq i32 %iv, %N
  56   br i1 %exitcond.not, label %exit, label %loop
  57
  58 exit:
  59   ret void
  60 }
  61
  62 define void @ule_from_unknown(i32 %M, i32 %N, i32 %S) {
  63 ; CHECK-LABEL: 'ule_from_unknown'
  64 ; CHECK-NEXT:  Determining loop execution counts for: @ule_from_unknown
  65 ; CHECK-NEXT:  Loop %loop: <multiple exits> backedge-taken count is (((-1 * (zext i32 %S to i64))<nsw> + ((zext i32 %S to i64) umax (1 + (zext i32 %M to i64))<nuw><nsw>)) umin_seq (zext i32 ((-1 * %S) + %N) to i64))
  66 ; CHECK-NEXT:    exit count for loop: ((-1 * (zext i32 %S to i64))<nsw> + ((zext i32 %S to i64) umax (1 + (zext i32 %M to i64))<nuw><nsw>))
  67 ; CHECK-NEXT:    exit count for latch: ((-1 * %S) + %N)
  68 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i64 4294967295
  69 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (((-1 * (zext i32 %S to i64))<nsw> + ((zext i32 %S to i64) umax (1 + (zext i32 %M to i64))<nuw><nsw>)) umin_seq (zext i32 ((-1 * %S) + %N) to i64))
  70 ; CHECK-NEXT:    symbolic max exit count for loop: ((-1 * (zext i32 %S to i64))<nsw> + ((zext i32 %S to i64) umax (1 + (zext i32 %M to i64))<nuw><nsw>))
  71 ; CHECK-NEXT:    symbolic max exit count for latch: ((-1 * %S) + %N)
  72 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
  73 ;
  74 entry:
  75   br label %loop
  76
  77 loop:
  78   %iv = phi i32 [ %S, %entry ], [ %iv.next, %latch ]
  79   %cmp1 = icmp ule i32 %iv, %M
  80   br i1 %cmp1, label %latch, label %exit
  81
  82 latch:
  83   %iv.next = add nuw i32 %iv, 1
  84   %exitcond.not = icmp eq i32 %iv, %N
  85   br i1 %exitcond.not, label %exit, label %loop
  86
  87 exit:
  88   ret void
  89 }
  90
  91 define void @ule_from_zero_no_nuw(i32 %M, i32 %N) {
  92 ; CHECK-LABEL: 'ule_from_zero_no_nuw'
  93 ; CHECK-NEXT:  Determining loop execution counts for: @ule_from_zero_no_nuw
  94 ; CHECK-NEXT:  Loop %loop: <multiple exits> Unpredictable backedge-taken count.
  95 ; CHECK-NEXT:    exit count for loop: ***COULDNOTCOMPUTE***
  96 ; CHECK-NEXT:    predicated exit count for loop: (1 + (zext i32 %M to i64))<nuw><nsw>
  97 ; CHECK-NEXT:     Predicates:
  98 ; CHECK-NEXT:      {0,+,1}<%loop> Added Flags: <nusw>
  99 ; CHECK-EMPTY:
 100 ; CHECK-NEXT:    exit count for latch: %N
 101 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 -1
 102 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is %N
 103 ; CHECK-NEXT:    symbolic max exit count for loop: ***COULDNOTCOMPUTE***
 104 ; CHECK-NEXT:    predicated symbolic max exit count for loop: (1 + (zext i32 %M to i64))<nuw><nsw>
 105 ; CHECK-NEXT:     Predicates:
 106 ; CHECK-NEXT:      {0,+,1}<%loop> Added Flags: <nusw>
 107 ; CHECK-EMPTY:
 108 ; CHECK-NEXT:    symbolic max exit count for latch: %N
 109 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is ((zext i32 %N to i64) umin (1 + (zext i32 %M to i64))<nuw><nsw>)
 110 ; CHECK-NEXT:   Predicates:
 111 ; CHECK-NEXT:      {0,+,1}<%loop> Added Flags: <nusw>
 112 ; CHECK-NEXT:  Loop %loop: Predicated constant max backedge-taken count is i64 4294967295
 113 ; CHECK-NEXT:   Predicates:
 114 ; CHECK-NEXT:      {0,+,1}<%loop> Added Flags: <nusw>
 115 ; CHECK-NEXT:  Loop %loop: Predicated symbolic max backedge-taken count is ((zext i32 %N to i64) umin (1 + (zext i32 %M to i64))<nuw><nsw>)
 116 ; CHECK-NEXT:   Predicates:
 117 ; CHECK-NEXT:      {0,+,1}<%loop> Added Flags: <nusw>
 118 ;
 119 entry:
 120   br label %loop
 121
 122 loop:
 123   %iv = phi i32 [ 0, %entry ], [ %iv.next, %latch ]
 124   %cmp1 = icmp ule i32 %iv, %M
 125   br i1 %cmp1, label %latch, label %exit
 126
 127 latch:
 128   %iv.next = add i32 %iv, 1
 129   %exitcond.not = icmp eq i32 %iv, %N
 130   br i1 %exitcond.not, label %exit, label %loop
 131
 132 exit:
 133   ret void
 134 }
 135
 136 define void @sle_from_int_min(i32 %M, i32 %N) {
 137 ; CHECK-LABEL: 'sle_from_int_min'
 138 ; CHECK-NEXT:  Determining loop execution counts for: @sle_from_int_min
 139 ; CHECK-NEXT:  Loop %loop: <multiple exits> backedge-taken count is ((zext i32 (-2147483648 + %N) to i64) umin (2147483649 + (sext i32 %M to i64))<nsw>)
 140 ; CHECK-NEXT:    exit count for loop: (2147483649 + (sext i32 %M to i64))<nsw>
 141 ; CHECK-NEXT:    exit count for latch: (-2147483648 + %N)
 142 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i64 4294967295
 143 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((zext i32 (-2147483648 + %N) to i64) umin (2147483649 + (sext i32 %M to i64))<nsw>)
 144 ; CHECK-NEXT:    symbolic max exit count for loop: (2147483649 + (sext i32 %M to i64))<nsw>
 145 ; CHECK-NEXT:    symbolic max exit count for latch: (-2147483648 + %N)
 146 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
 147 ;
 148 entry:
 149   br label %loop
 150
 151 loop:
 152   %iv = phi i32 [ u0x80000000, %entry ], [ %iv.next, %latch ]
 153   %cmp1 = icmp sle i32 %iv, %M
 154   br i1 %cmp1, label %latch, label %exit
 155
 156 latch:
 157   %iv.next = add nsw i32 %iv, 1
 158   %exitcond.not = icmp eq i32 %iv, %N
 159   br i1 %exitcond.not, label %exit, label %loop
 160
 161 exit:
 162   ret void
 163 }
 164
 165 define void @sle_from_int_min_plus_one(i32 %M, i32 %N) {
 166 ; CHECK-LABEL: 'sle_from_int_min_plus_one'
 167 ; CHECK-NEXT:  Determining loop execution counts for: @sle_from_int_min_plus_one
 168 ; CHECK-NEXT:  Loop %loop: <multiple exits> backedge-taken count is ((-2147483648 + %M) umin_seq (2147483647 + %N))
 169 ; CHECK-NEXT:    exit count for loop: (-2147483648 + %M)
 170 ; CHECK-NEXT:    exit count for latch: (2147483647 + %N)
 171 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 -1
 172 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((-2147483648 + %M) umin_seq (2147483647 + %N))
 173 ; CHECK-NEXT:    symbolic max exit count for loop: (-2147483648 + %M)
 174 ; CHECK-NEXT:    symbolic max exit count for latch: (2147483647 + %N)
 175 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
 176 ;
 177 entry:
 178   br label %loop
 179
 180 loop:
 181   %iv = phi i32 [ u0x80000001, %entry ], [ %iv.next, %latch ]
 182   %cmp1 = icmp sle i32 %iv, %M
 183   br i1 %cmp1, label %latch, label %exit
 184
 185 latch:
 186   %iv.next = add nsw i32 %iv, 1
 187   %exitcond.not = icmp eq i32 %iv, %N
 188   br i1 %exitcond.not, label %exit, label %loop
 189
 190 exit:
 191   ret void
 192 }
 193
 194 define void @sle_from_unknown(i32 %M, i32 %N, i32 %S) {
 195 ; CHECK-LABEL: 'sle_from_unknown'
 196 ; CHECK-NEXT:  Determining loop execution counts for: @sle_from_unknown
 197 ; CHECK-NEXT:  Loop %loop: <multiple exits> backedge-taken count is (((-1 * (sext i32 %S to i64))<nsw> + ((sext i32 %S to i64) smax (1 + (sext i32 %M to i64))<nsw>)) umin_seq (zext i32 ((-1 * %S) + %N) to i64))
 198 ; CHECK-NEXT:    exit count for loop: ((-1 * (sext i32 %S to i64))<nsw> + ((sext i32 %S to i64) smax (1 + (sext i32 %M to i64))<nsw>))
 199 ; CHECK-NEXT:    exit count for latch: ((-1 * %S) + %N)
 200 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i64 4294967295
 201 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (((-1 * (sext i32 %S to i64))<nsw> + ((sext i32 %S to i64) smax (1 + (sext i32 %M to i64))<nsw>)) umin_seq (zext i32 ((-1 * %S) + %N) to i64))
 202 ; CHECK-NEXT:    symbolic max exit count for loop: ((-1 * (sext i32 %S to i64))<nsw> + ((sext i32 %S to i64) smax (1 + (sext i32 %M to i64))<nsw>))
 203 ; CHECK-NEXT:    symbolic max exit count for latch: ((-1 * %S) + %N)
 204 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
 205 ;
 206 entry:
 207   br label %loop
 208
 209 loop:
 210   %iv = phi i32 [ %S, %entry ], [ %iv.next, %latch ]
 211   %cmp1 = icmp sle i32 %iv, %M
 212   br i1 %cmp1, label %latch, label %exit
 213
 214 latch:
 215   %iv.next = add nsw i32 %iv, 1
 216   %exitcond.not = icmp eq i32 %iv, %N
 217   br i1 %exitcond.not, label %exit, label %loop
 218
 219 exit:
 220   ret void
 221 }
 222
 223 define void @sle_from_int_min_no_nsw(i32 %M, i32 %N) {
 224 ; CHECK-LABEL: 'sle_from_int_min_no_nsw'
 225 ; CHECK-NEXT:  Determining loop execution counts for: @sle_from_int_min_no_nsw
 226 ; CHECK-NEXT:  Loop %loop: <multiple exits> Unpredictable backedge-taken count.
 227 ; CHECK-NEXT:    exit count for loop: ***COULDNOTCOMPUTE***
 228 ; CHECK-NEXT:    predicated exit count for loop: (2147483649 + (sext i32 %M to i64))<nsw>
 229 ; CHECK-NEXT:     Predicates:
 230 ; CHECK-NEXT:      {-2147483648,+,1}<%loop> Added Flags: <nssw>
 231 ; CHECK-EMPTY:
 232 ; CHECK-NEXT:    exit count for latch: (-2147483648 + %N)
 233 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 -1
 234 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-2147483648 + %N)
 235 ; CHECK-NEXT:    symbolic max exit count for loop: ***COULDNOTCOMPUTE***
 236 ; CHECK-NEXT:    predicated symbolic max exit count for loop: (2147483649 + (sext i32 %M to i64))<nsw>
 237 ; CHECK-NEXT:     Predicates:
 238 ; CHECK-NEXT:      {-2147483648,+,1}<%loop> Added Flags: <nssw>
 239 ; CHECK-EMPTY:
 240 ; CHECK-NEXT:    symbolic max exit count for latch: (-2147483648 + %N)
 241 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is ((zext i32 (-2147483648 + %N) to i64) umin (2147483649 + (sext i32 %M to i64))<nsw>)
 242 ; CHECK-NEXT:   Predicates:
 243 ; CHECK-NEXT:      {-2147483648,+,1}<%loop> Added Flags: <nssw>
 244 ; CHECK-NEXT:  Loop %loop: Predicated constant max backedge-taken count is i64 4294967295
 245 ; CHECK-NEXT:   Predicates:
 246 ; CHECK-NEXT:      {-2147483648,+,1}<%loop> Added Flags: <nssw>
 247 ; CHECK-NEXT:  Loop %loop: Predicated symbolic max backedge-taken count is ((zext i32 (-2147483648 + %N) to i64) umin (2147483649 + (sext i32 %M to i64))<nsw>)
 248 ; CHECK-NEXT:   Predicates:
 249 ; CHECK-NEXT:      {-2147483648,+,1}<%loop> Added Flags: <nssw>
 250 ;
 251 entry:
 252   br label %loop
 253
 254 loop:
 255   %iv = phi i32 [ u0x80000000, %entry ], [ %iv.next, %latch ]
 256   %cmp1 = icmp sle i32 %iv, %M
 257   br i1 %cmp1, label %latch, label %exit
 258
 259 latch:
 260   %iv.next = add i32 %iv, 1
 261   %exitcond.not = icmp eq i32 %iv, %N
 262   br i1 %exitcond.not, label %exit, label %loop
 263
 264 exit:
 265   ret void
 266 }