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