llvm/test/Analysis/ScalarEvolution/implied-via-division.ll

   1 ; RUN: opt < %s -analyze -enable-new-pm=0 -scalar-evolution | FileCheck %s
   2 ; RUN: opt < %s -disable-output "-passes=print<scalar-evolution>" 2>&1 | FileCheck %s
   3
   4 declare void @llvm.experimental.guard(i1, ...)
   5
   6 define void @test_1(i32 %n) nounwind {
   7 ; Prove that (n > 1) ===> (n / 2 > 0).
   8 ; CHECK:         Determining loop execution counts for: @test_1
   9 ; CHECK:         Loop %header: backedge-taken count is (-1 + %n.div.2)<nsw>
  10 entry:
  11   %cmp1 = icmp sgt i32 %n, 1
  12   %n.div.2 = sdiv i32 %n, 2
  13   call void(i1, ...) @llvm.experimental.guard(i1 %cmp1) [ "deopt"() ]
  14   br label %header
  15
  16 header:
  17   %indvar = phi i32 [ %indvar.next, %header ], [ 0, %entry ]
  18   %indvar.next = add i32 %indvar, 1
  19   %exitcond = icmp sgt i32 %n.div.2, %indvar.next
  20   br i1 %exitcond, label %header, label %exit
  21
  22 exit:
  23   ret void
  24 }
  25
  26 define void @test_1neg(i32 %n) nounwind {
  27 ; Prove that (n > 0) =\=> (n / 2 > 0).
  28 ; CHECK:         Determining loop execution counts for: @test_1neg
  29 ; CHECK:         Loop %header: backedge-taken count is (-1 + (1 smax %n.div.2))<nsw>
  30 entry:
  31   %cmp1 = icmp sgt i32 %n, 0
  32   %n.div.2 = sdiv i32 %n, 2
  33   call void(i1, ...) @llvm.experimental.guard(i1 %cmp1) [ "deopt"() ]
  34   br label %header
  35
  36 header:
  37   %indvar = phi i32 [ %indvar.next, %header ], [ 0, %entry ]
  38   %indvar.next = add i32 %indvar, 1
  39   %exitcond = icmp sgt i32 %n.div.2, %indvar.next
  40   br i1 %exitcond, label %header, label %exit
  41
  42 exit:
  43   ret void
  44 }
  45
  46 define void @test_2(i32 %n) nounwind {
  47 ; Prove that (n >= 2) ===> (n / 2 > 0).
  48 ; CHECK:         Determining loop execution counts for: @test_2
  49 ; CHECK:         Loop %header: backedge-taken count is (-1 + %n.div.2)<nsw>
  50 entry:
  51   %cmp1 = icmp sge i32 %n, 2
  52   %n.div.2 = sdiv i32 %n, 2
  53   call void(i1, ...) @llvm.experimental.guard(i1 %cmp1) [ "deopt"() ]
  54   br label %header
  55
  56 header:
  57   %indvar = phi i32 [ %indvar.next, %header ], [ 0, %entry ]
  58   %indvar.next = add i32 %indvar, 1
  59   %exitcond = icmp sgt i32 %n.div.2, %indvar.next
  60   br i1 %exitcond, label %header, label %exit
  61
  62 exit:
  63   ret void
  64 }
  65
  66 define void @test_2neg(i32 %n) nounwind {
  67 ; Prove that (n >= 1) =\=> (n / 2 > 0).
  68 ; CHECK:         Determining loop execution counts for: @test_2neg
  69 ; CHECK:         Loop %header: backedge-taken count is (-1 + (1 smax %n.div.2))<nsw>
  70 entry:
  71   %cmp1 = icmp sge i32 %n, 1
  72   %n.div.2 = sdiv i32 %n, 2
  73   call void(i1, ...) @llvm.experimental.guard(i1 %cmp1) [ "deopt"() ]
  74   br label %header
  75
  76 header:
  77   %indvar = phi i32 [ %indvar.next, %header ], [ 0, %entry ]
  78   %indvar.next = add i32 %indvar, 1
  79   %exitcond = icmp sgt i32 %n.div.2, %indvar.next
  80   br i1 %exitcond, label %header, label %exit
  81
  82 exit:
  83   ret void
  84 }
  85
  86 define void @test_3(i32 %n) nounwind {
  87 ; Prove that (n > -2) ===> (n / 2 >= 0).
  88 ; CHECK:         Determining loop execution counts for: @test_3
  89 ; CHECK:         Loop %header: backedge-taken count is (1 + %n.div.2)<nsw>
  90 entry:
  91   %cmp1 = icmp sgt i32 %n, -2
  92   %n.div.2 = sdiv i32 %n, 2
  93   call void(i1, ...) @llvm.experimental.guard(i1 %cmp1) [ "deopt"() ]
  94   br label %header
  95
  96 header:
  97   %indvar = phi i32 [ %indvar.next, %header ], [ 0, %entry ]
  98   %indvar.next = add i32 %indvar, 1
  99   %exitcond = icmp sge i32 %n.div.2, %indvar
 100   br i1 %exitcond, label %header, label %exit
 101
 102 exit:
 103   ret void
 104 }
 105
 106 define void @test_3neg(i32 %n) nounwind {
 107 ; Prove that (n > -3) =\=> (n / 2 >= 0).
 108 ; CHECK:         Determining loop execution counts for: @test_3neg
 109 ; CHECK:         Loop %header: backedge-taken count is (0 smax (1 + %n.div.2)<nsw>)
 110 entry:
 111   %cmp1 = icmp sgt i32 %n, -3
 112   %n.div.2 = sdiv i32 %n, 2
 113   call void(i1, ...) @llvm.experimental.guard(i1 %cmp1) [ "deopt"() ]
 114   br label %header
 115
 116 header:
 117   %indvar = phi i32 [ %indvar.next, %header ], [ 0, %entry ]
 118   %indvar.next = add i32 %indvar, 1
 119   %exitcond = icmp sge i32 %n.div.2, %indvar
 120   br i1 %exitcond, label %header, label %exit
 121
 122 exit:
 123   ret void
 124 }
 125
 126 define void @test_4(i32 %n) nounwind {
 127 ; Prove that (n >= -1) ===> (n / 2 >= 0).
 128 ; CHECK:         Determining loop execution counts for: @test_4
 129 ; CHECK:         Loop %header: backedge-taken count is (1 + %n.div.2)<nsw>
 130 entry:
 131   %cmp1 = icmp sge i32 %n, -1
 132   %n.div.2 = sdiv i32 %n, 2
 133   call void(i1, ...) @llvm.experimental.guard(i1 %cmp1) [ "deopt"() ]
 134   br label %header
 135
 136 header:
 137   %indvar = phi i32 [ %indvar.next, %header ], [ 0, %entry ]
 138   %indvar.next = add i32 %indvar, 1
 139   %exitcond = icmp sge i32 %n.div.2, %indvar
 140   br i1 %exitcond, label %header, label %exit
 141
 142 exit:
 143   ret void
 144 }
 145
 146 define void @test_4neg(i32 %n) nounwind {
 147 ; Prove that (n >= -2) =\=> (n / 2 >= 0).
 148 ; CHECK:         Determining loop execution counts for: @test_4neg
 149 ; CHECK:         Loop %header: backedge-taken count is (0 smax (1 + %n.div.2)<nsw>)
 150 entry:
 151   %cmp1 = icmp sge i32 %n, -2
 152   %n.div.2 = sdiv i32 %n, 2
 153   call void(i1, ...) @llvm.experimental.guard(i1 %cmp1) [ "deopt"() ]
 154   br label %header
 155
 156 header:
 157   %indvar = phi i32 [ %indvar.next, %header ], [ 0, %entry ]
 158   %indvar.next = add i32 %indvar, 1
 159   %exitcond = icmp sge i32 %n.div.2, %indvar
 160   br i1 %exitcond, label %header, label %exit
 161
 162 exit:
 163   ret void
 164 }
 165
 166 define void @test_ext_01(i32 %n) nounwind {
 167 ; Prove that (n > 1) ===> (n / 2 > 0).
 168 ; CHECK:         Determining loop execution counts for: @test_ext_01
 169 ; CHECK:         Loop %header: backedge-taken count is (-1 + (sext i32 %n.div.2 to i64))<nsw>
 170 entry:
 171   %cmp1 = icmp sgt i32 %n, 1
 172   %n.div.2 = sdiv i32 %n, 2
 173   %n.div.2.ext = sext i32 %n.div.2 to i64
 174   call void(i1, ...) @llvm.experimental.guard(i1 %cmp1) [ "deopt"() ]
 175   br label %header
 176
 177 header:
 178   %indvar = phi i64 [ %indvar.next, %header ], [ 0, %entry ]
 179   %indvar.next = add i64 %indvar, 1
 180   %exitcond = icmp sgt i64 %n.div.2.ext, %indvar.next
 181   br i1 %exitcond, label %header, label %exit
 182
 183 exit:
 184   ret void
 185 }
 186
 187 define void @test_ext_01neg(i32 %n) nounwind {
 188 ; Prove that (n > 0) =\=> (n / 2 > 0).
 189 ; CHECK:         Determining loop execution counts for: @test_ext_01neg
 190 ; CHECK:         Loop %header: backedge-taken count is (-1 + (1 smax (sext i32 %n.div.2 to i64)))<nsw>
 191 entry:
 192   %cmp1 = icmp sgt i32 %n, 0
 193   %n.div.2 = sdiv i32 %n, 2
 194   %n.div.2.ext = sext i32 %n.div.2 to i64
 195   call void(i1, ...) @llvm.experimental.guard(i1 %cmp1) [ "deopt"() ]
 196   br label %header
 197
 198 header:
 199   %indvar = phi i64 [ %indvar.next, %header ], [ 0, %entry ]
 200   %indvar.next = add i64 %indvar, 1
 201   %exitcond = icmp sgt i64 %n.div.2.ext, %indvar.next
 202   br i1 %exitcond, label %header, label %exit
 203
 204 exit:
 205   ret void
 206 }
 207
 208 define void @test_ext_02(i32 %n) nounwind {
 209 ; Prove that (n >= 2) ===> (n / 2 > 0).
 210 ; CHECK:         Determining loop execution counts for: @test_ext_02
 211 ; CHECK:         Loop %header: backedge-taken count is (-1 + (sext i32 %n.div.2 to i64))<nsw>
 212 entry:
 213   %cmp1 = icmp sge i32 %n, 2
 214   %n.div.2 = sdiv i32 %n, 2
 215   %n.div.2.ext = sext i32 %n.div.2 to i64
 216   call void(i1, ...) @llvm.experimental.guard(i1 %cmp1) [ "deopt"() ]
 217   br label %header
 218
 219 header:
 220   %indvar = phi i64 [ %indvar.next, %header ], [ 0, %entry ]
 221   %indvar.next = add i64 %indvar, 1
 222   %exitcond = icmp sgt i64 %n.div.2.ext, %indvar.next
 223   br i1 %exitcond, label %header, label %exit
 224
 225 exit:
 226   ret void
 227 }
 228
 229 define void @test_ext_02neg(i32 %n) nounwind {
 230 ; Prove that (n >= 1) =\=> (n / 2 > 0).
 231 ; CHECK:         Determining loop execution counts for: @test_ext_02neg
 232 ; CHECK:         Loop %header: backedge-taken count is (-1 + (1 smax (sext i32 %n.div.2 to i64)))<nsw>
 233 entry:
 234   %cmp1 = icmp sge i32 %n, 1
 235   %n.div.2 = sdiv i32 %n, 2
 236   %n.div.2.ext = sext i32 %n.div.2 to i64
 237   call void(i1, ...) @llvm.experimental.guard(i1 %cmp1) [ "deopt"() ]
 238   br label %header
 239
 240 header:
 241   %indvar = phi i64 [ %indvar.next, %header ], [ 0, %entry ]
 242   %indvar.next = add i64 %indvar, 1
 243   %exitcond = icmp sgt i64 %n.div.2.ext, %indvar.next
 244   br i1 %exitcond, label %header, label %exit
 245
 246 exit:
 247   ret void
 248 }
 249
 250 define void @test_ext_03(i32 %n) nounwind {
 251 ; Prove that (n > -2) ===> (n / 2 >= 0).
 252 ; CHECK:         Determining loop execution counts for: @test_ext_03
 253 ; CHECK:         Loop %header: backedge-taken count is (1 + (sext i32 %n.div.2 to i64))<nsw>
 254 entry:
 255   %cmp1 = icmp sgt i32 %n, -2
 256   %n.div.2 = sdiv i32 %n, 2
 257   %n.div.2.ext = sext i32 %n.div.2 to i64
 258   call void(i1, ...) @llvm.experimental.guard(i1 %cmp1) [ "deopt"() ]
 259   br label %header
 260
 261 header:
 262   %indvar = phi i64 [ %indvar.next, %header ], [ 0, %entry ]
 263   %indvar.next = add i64 %indvar, 1
 264   %exitcond = icmp sge i64 %n.div.2.ext, %indvar
 265   br i1 %exitcond, label %header, label %exit
 266
 267 exit:
 268   ret void
 269 }
 270
 271 define void @test_ext_03neg(i32 %n) nounwind {
 272 ; Prove that (n > -3) =\=> (n / 2 >= 0).
 273 ; CHECK:         Determining loop execution counts for: @test_ext_03neg
 274 ; CHECK:         Loop %header: backedge-taken count is (0 smax (1 + (sext i32 %n.div.2 to i64))<nsw>)
 275 entry:
 276   %cmp1 = icmp sgt i32 %n, -3
 277   %n.div.2 = sdiv i32 %n, 2
 278   %n.div.2.ext = sext i32 %n.div.2 to i64
 279   call void(i1, ...) @llvm.experimental.guard(i1 %cmp1) [ "deopt"() ]
 280   br label %header
 281
 282 header:
 283   %indvar = phi i64 [ %indvar.next, %header ], [ 0, %entry ]
 284   %indvar.next = add i64 %indvar, 1
 285   %exitcond = icmp sge i64 %n.div.2.ext, %indvar
 286   br i1 %exitcond, label %header, label %exit
 287
 288 exit:
 289   ret void
 290 }
 291
 292 define void @test_ext_04(i32 %n) nounwind {
 293 ; Prove that (n >= -1) ===> (n / 2 >= 0).
 294 ; CHECK:         Determining loop execution counts for: @test_ext_04
 295 ; CHECK:         Loop %header: backedge-taken count is (1 + (sext i32 %n.div.2 to i64))<nsw>
 296 entry:
 297   %cmp1 = icmp sge i32 %n, -1
 298   %n.div.2 = sdiv i32 %n, 2
 299   %n.div.2.ext = sext i32 %n.div.2 to i64
 300   call void(i1, ...) @llvm.experimental.guard(i1 %cmp1) [ "deopt"() ]
 301   br label %header
 302
 303 header:
 304   %indvar = phi i64 [ %indvar.next, %header ], [ 0, %entry ]
 305   %indvar.next = add i64 %indvar, 1
 306   %exitcond = icmp sge i64 %n.div.2.ext, %indvar
 307   br i1 %exitcond, label %header, label %exit
 308
 309 exit:
 310   ret void
 311 }
 312
 313 define void @test_ext_04neg(i32 %n) nounwind {
 314 ; Prove that (n >= -2) =\=> (n / 2 >= 0).
 315 ; CHECK:         Determining loop execution counts for: @test_ext_04neg
 316 ; CHECK:         Loop %header: backedge-taken count is (0 smax (1 + (sext i32 %n.div.2 to i64))<nsw>)
 317 entry:
 318   %cmp1 = icmp sge i32 %n, -2
 319   %n.div.2 = sdiv i32 %n, 2
 320   %n.div.2.ext = sext i32 %n.div.2 to i64
 321   call void(i1, ...) @llvm.experimental.guard(i1 %cmp1) [ "deopt"() ]
 322   br label %header
 323
 324 header:
 325   %indvar = phi i64 [ %indvar.next, %header ], [ 0, %entry ]
 326   %indvar.next = add i64 %indvar, 1
 327   %exitcond = icmp sge i64 %n.div.2.ext, %indvar
 328   br i1 %exitcond, label %header, label %exit
 329
 330 exit:
 331   ret void
 332 }