llvm/test/Analysis/ScalarEvolution/ne-overflow.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
   2 ; RUN: opt %s -passes='print<scalar-evolution>' -scalar-evolution-classify-expressions=0 -disable-output 2>&1 | FileCheck %s
   3
   4 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
   5 target triple = "x86_64-unknown-linux-gnu"
   6
   7 ; A collection of tests focused on exercising logic to prove no-unsigned wrap
   8 ; from mustprogress semantics of loops.
   9
  10 define void @test(i32 %N) mustprogress {
  11 ; CHECK-LABEL: 'test'
  12 ; CHECK-NEXT:  Determining loop execution counts for: @test
  13 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is ((-2 + %N) /u 2)
  14 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is 2147483647
  15 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is ((-2 + %N) /u 2)
  16 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is ((-2 + %N) /u 2)
  17 ; CHECK-NEXT:   Predicates:
  18 ; CHECK-NEXT:  Loop %for.body: Trip multiple is 1
  19 ;
  20 entry:
  21   br label %for.body
  22
  23 for.body:
  24   %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ]
  25   %iv.next = add i32 %iv, 2
  26   %cmp = icmp ne i32 %iv.next, %N
  27   br i1 %cmp, label %for.body, label %for.cond.cleanup
  28
  29 for.cond.cleanup:
  30   ret void
  31 }
  32
  33 define void @test_preinc(i32 %N) mustprogress {
  34 ; CHECK-LABEL: 'test_preinc'
  35 ; CHECK-NEXT:  Determining loop execution counts for: @test_preinc
  36 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is (%N /u 2)
  37 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is 2147483647
  38 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (%N /u 2)
  39 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (%N /u 2)
  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 [ %iv.next, %for.body ], [ 0, %entry ]
  48   %iv.next = add i32 %iv, 2
  49   %cmp = icmp ne i32 %iv, %N
  50   br i1 %cmp, label %for.body, label %for.cond.cleanup
  51
  52 for.cond.cleanup:
  53   ret void
  54
  55 }
  56
  57 @G = external global i32
  58
  59 define void @test_well_defined_infinite_st(i32 %N) mustprogress {
  60 ; CHECK-LABEL: 'test_well_defined_infinite_st'
  61 ; CHECK-NEXT:  Determining loop execution counts for: @test_well_defined_infinite_st
  62 ; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
  63 ; CHECK-NEXT:  Loop %for.body: Unpredictable constant max backedge-taken count.
  64 ; CHECK-NEXT:  Loop %for.body: Unpredictable symbolic max backedge-taken count.
  65 ; CHECK-NEXT:  Loop %for.body: Unpredictable predicated backedge-taken count.
  66 ;
  67 entry:
  68   br label %for.body
  69
  70 for.body:
  71   %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ]
  72   %iv.next = add i32 %iv, 2
  73   store volatile i32 0, ptr @G
  74   %cmp = icmp ne i32 %iv.next, %N
  75   br i1 %cmp, label %for.body, label %for.cond.cleanup
  76
  77 for.cond.cleanup:
  78   ret void
  79 }
  80
  81 define void @test_well_defined_infinite_ld(i32 %N) mustprogress {
  82 ; CHECK-LABEL: 'test_well_defined_infinite_ld'
  83 ; CHECK-NEXT:  Determining loop execution counts for: @test_well_defined_infinite_ld
  84 ; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
  85 ; CHECK-NEXT:  Loop %for.body: Unpredictable constant max backedge-taken count.
  86 ; CHECK-NEXT:  Loop %for.body: Unpredictable symbolic max backedge-taken count.
  87 ; CHECK-NEXT:  Loop %for.body: Unpredictable predicated backedge-taken count.
  88 ;
  89 entry:
  90   br label %for.body
  91
  92 for.body:
  93   %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ]
  94   %iv.next = add i32 %iv, 2
  95   %val = load volatile i32, ptr @G
  96   %cmp = icmp ne i32 %iv.next, %N
  97   br i1 %cmp, label %for.body, label %for.cond.cleanup
  98
  99 for.cond.cleanup:
 100   ret void
 101 }
 102
 103 define void @test_no_mustprogress(i32 %N) {
 104 ; CHECK-LABEL: 'test_no_mustprogress'
 105 ; CHECK-NEXT:  Determining loop execution counts for: @test_no_mustprogress
 106 ; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
 107 ; CHECK-NEXT:  Loop %for.body: Unpredictable constant max backedge-taken count.
 108 ; CHECK-NEXT:  Loop %for.body: Unpredictable symbolic max backedge-taken count.
 109 ; CHECK-NEXT:  Loop %for.body: Unpredictable predicated backedge-taken count.
 110 ;
 111 entry:
 112   br label %for.body
 113
 114 for.body:
 115   %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ]
 116   %iv.next = add i32 %iv, 2
 117   %cmp = icmp ne i32 %iv.next, %N
 118   br i1 %cmp, label %for.body, label %for.cond.cleanup
 119
 120 for.cond.cleanup:
 121   ret void
 122
 123 }
 124
 125
 126 define void @test_1024(i32 %N) mustprogress {
 127 ; CHECK-LABEL: 'test_1024'
 128 ; CHECK-NEXT:  Determining loop execution counts for: @test_1024
 129 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is ((-1024 + %N) /u 1024)
 130 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is 4194303
 131 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is ((-1024 + %N) /u 1024)
 132 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is ((-1024 + %N) /u 1024)
 133 ; CHECK-NEXT:   Predicates:
 134 ; CHECK-NEXT:  Loop %for.body: Trip multiple is 1
 135 ;
 136 entry:
 137   br label %for.body
 138
 139 for.body:
 140   %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ]
 141   %iv.next = add i32 %iv, 1024
 142   %cmp = icmp ne i32 %iv.next, %N
 143   br i1 %cmp, label %for.body, label %for.cond.cleanup
 144
 145 for.cond.cleanup:
 146   ret void
 147 }
 148
 149 define void @test_uneven_divide(i32 %N) mustprogress {
 150 ; CHECK-LABEL: 'test_uneven_divide'
 151 ; CHECK-NEXT:  Determining loop execution counts for: @test_uneven_divide
 152 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + (-1431655765 * %N))
 153 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is -1
 154 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (-1 + (-1431655765 * %N))
 155 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + (-1431655765 * %N))
 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 [ %iv.next, %for.body ], [ 0, %entry ]
 164   %iv.next = add i32 %iv, 3
 165   %cmp = icmp ne i32 %iv.next, %N
 166   br i1 %cmp, label %for.body, label %for.cond.cleanup
 167
 168 for.cond.cleanup:
 169   ret void
 170 }
 171
 172 define void @test_non_invariant_rhs() mustprogress {
 173 ; CHECK-LABEL: 'test_non_invariant_rhs'
 174 ; CHECK-NEXT:  Determining loop execution counts for: @test_non_invariant_rhs
 175 ; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
 176 ; CHECK-NEXT:  Loop %for.body: Unpredictable constant max backedge-taken count.
 177 ; CHECK-NEXT:  Loop %for.body: Unpredictable symbolic max backedge-taken count.
 178 ; CHECK-NEXT:  Loop %for.body: Unpredictable predicated backedge-taken count.
 179 ;
 180 entry:
 181   br label %for.body
 182
 183 for.body:
 184   %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ]
 185   %iv.next = add i32 %iv, 2
 186   %N = load i32, ptr @G
 187   %cmp = icmp ne i32 %iv.next, %N
 188   br i1 %cmp, label %for.body, label %for.cond.cleanup
 189
 190 for.cond.cleanup:
 191   ret void
 192 }
 193
 194 declare void @mayexit()
 195
 196 define void @test_abnormal_exit(i32 %N) mustprogress {
 197 ; CHECK-LABEL: 'test_abnormal_exit'
 198 ; CHECK-NEXT:  Determining loop execution counts for: @test_abnormal_exit
 199 ; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
 200 ; CHECK-NEXT:  Loop %for.body: Unpredictable constant max backedge-taken count.
 201 ; CHECK-NEXT:  Loop %for.body: Unpredictable symbolic max backedge-taken count.
 202 ; CHECK-NEXT:  Loop %for.body: Unpredictable predicated backedge-taken count.
 203 ;
 204 entry:
 205   br label %for.body
 206
 207 for.body:
 208   %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ]
 209   %iv.next = add i32 %iv, 2
 210   call void @mayexit()
 211   %cmp = icmp ne i32 %iv.next, %N
 212   br i1 %cmp, label %for.body, label %for.cond.cleanup
 213
 214 for.cond.cleanup:
 215   ret void
 216 }
 217
 218
 219 define void @test_other_exit(i32 %N) mustprogress {
 220 ; CHECK-LABEL: 'test_other_exit'
 221 ; CHECK-NEXT:  Determining loop execution counts for: @test_other_exit
 222 ; CHECK-NEXT:  Loop %for.body: <multiple exits> Unpredictable backedge-taken count.
 223 ; CHECK-NEXT:    exit count for for.body: 9
 224 ; CHECK-NEXT:    exit count for for.latch: ***COULDNOTCOMPUTE***
 225 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is 9
 226 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is 9
 227 ; CHECK-NEXT:    symbolic max exit count for for.body: 9
 228 ; CHECK-NEXT:    symbolic max exit count for for.latch: ***COULDNOTCOMPUTE***
 229 ; CHECK-NEXT:  Loop %for.body: Unpredictable predicated backedge-taken count.
 230 ;
 231 entry:
 232   br label %for.body
 233
 234 for.body:
 235   %iv = phi i32 [ %iv.next, %for.latch ], [ 0, %entry ]
 236   %iv.next = add i32 %iv, 2
 237   %cmp1 = icmp ne i32 %iv.next, 20
 238   br i1 %cmp1, label %for.latch, label %for.cond.cleanup
 239
 240 for.latch:
 241   %cmp2 = icmp ne i32 %iv.next, %N
 242   br i1 %cmp2, label %for.body, label %for.cond.cleanup
 243
 244 for.cond.cleanup:
 245   ret void
 246 }
 247
 248 define void @test_zext(i64 %N) mustprogress {
 249 ; CHECK-LABEL: 'test_zext'
 250 ; CHECK-NEXT:  Determining loop execution counts for: @test_zext
 251 ; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
 252 ; CHECK-NEXT:  Loop %for.body: Unpredictable constant max backedge-taken count.
 253 ; CHECK-NEXT:  Loop %for.body: Unpredictable symbolic max backedge-taken count.
 254 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (%N /u 2)
 255 ; CHECK-NEXT:   Predicates:
 256 ; CHECK-NEXT:      {0,+,2}<nuw><%for.body> Added Flags: <nusw>
 257 ;
 258 entry:
 259   br label %for.body
 260
 261 for.body:
 262   %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ]
 263   %iv.next = add i32 %iv, 2
 264   %zext = zext i32 %iv to i64
 265   %cmp = icmp ne i64 %zext, %N
 266   br i1 %cmp, label %for.body, label %for.cond.cleanup
 267
 268 for.cond.cleanup:
 269   ret void
 270 }
 271
 272 define void @test_sext(i64 %N) mustprogress {
 273 ; CHECK-LABEL: 'test_sext'
 274 ; CHECK-NEXT:  Determining loop execution counts for: @test_sext
 275 ; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
 276 ; CHECK-NEXT:  Loop %for.body: Unpredictable constant max backedge-taken count.
 277 ; CHECK-NEXT:  Loop %for.body: Unpredictable symbolic max backedge-taken count.
 278 ; CHECK-NEXT:  Loop %for.body: Unpredictable predicated backedge-taken count.
 279 ;
 280 entry:
 281   br label %for.body
 282
 283 for.body:
 284   %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ]
 285   %iv.next = add i32 %iv, 2
 286   %sext = sext i32 %iv to i64
 287   %cmp = icmp ne i64 %sext, %N
 288   br i1 %cmp, label %for.body, label %for.cond.cleanup
 289
 290 for.cond.cleanup:
 291   ret void
 292 }
 293
 294 define void @test_zext_of_sext(i64 %N) mustprogress {
 295 ; CHECK-LABEL: 'test_zext_of_sext'
 296 ; CHECK-NEXT:  Determining loop execution counts for: @test_zext_of_sext
 297 ; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
 298 ; CHECK-NEXT:  Loop %for.body: Unpredictable constant max backedge-taken count.
 299 ; CHECK-NEXT:  Loop %for.body: Unpredictable symbolic max backedge-taken count.
 300 ; CHECK-NEXT:  Loop %for.body: Unpredictable predicated backedge-taken count.
 301 ;
 302 entry:
 303   br label %for.body
 304
 305 for.body:
 306   %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ]
 307   %iv.next = add i32 %iv, 2
 308   %sext = sext i32 %iv to i48
 309   %zext = zext i48 %sext to i64
 310   %cmp = icmp ne i64 %zext, %N
 311   br i1 %cmp, label %for.body, label %for.cond.cleanup
 312
 313 for.cond.cleanup:
 314   ret void
 315 }
 316
 317 define void @test_zext_offset(i64 %N) mustprogress {
 318 ; CHECK-LABEL: 'test_zext_offset'
 319 ; CHECK-NEXT:  Determining loop execution counts for: @test_zext_offset
 320 ; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
 321 ; CHECK-NEXT:  Loop %for.body: Unpredictable constant max backedge-taken count.
 322 ; CHECK-NEXT:  Loop %for.body: Unpredictable symbolic max backedge-taken count.
 323 ; CHECK-NEXT:  Loop %for.body: Unpredictable predicated backedge-taken count.
 324 ;
 325 entry:
 326   br label %for.body
 327
 328 for.body:
 329   %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ]
 330   %iv.next = add i32 %iv, 2
 331   %zext = zext i32 %iv to i64
 332   %offset = add i64 %zext, 21
 333   %cmp = icmp ne i64 %offset, %N
 334   br i1 %cmp, label %for.body, label %for.cond.cleanup
 335
 336 for.cond.cleanup:
 337   ret void
 338 }
 339
 340 define void @test_sext_offset(i64 %N) mustprogress {
 341 ; CHECK-LABEL: 'test_sext_offset'
 342 ; CHECK-NEXT:  Determining loop execution counts for: @test_sext_offset
 343 ; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
 344 ; CHECK-NEXT:  Loop %for.body: Unpredictable constant max backedge-taken count.
 345 ; CHECK-NEXT:  Loop %for.body: Unpredictable symbolic max backedge-taken count.
 346 ; CHECK-NEXT:  Loop %for.body: Unpredictable predicated backedge-taken count.
 347 ;
 348 entry:
 349   br label %for.body
 350
 351 for.body:
 352   %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ]
 353   %iv.next = add i32 %iv, 2
 354   %sext = sext i32 %iv to i64
 355   %offset = add i64 %sext, 21
 356   %cmp = icmp ne i64 %offset, %N
 357   br i1 %cmp, label %for.body, label %for.cond.cleanup
 358
 359 for.cond.cleanup:
 360   ret void
 361 }