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