test/Transforms/IRCE/wide_indvar.ll

   1 ; RUN: opt -verify-loop-info -irce-print-changed-loops -irce -irce-allow-narrow-latch=true -S < %s 2>&1 | FileCheck %s
   2 ; RUN: opt -verify-loop-info -irce-print-changed-loops -passes='require<branch-prob>,loop(irce)' -irce-allow-narrow-latch=true -S < %s 2>&1 | FileCheck %s
   3
   4 ; Check that we can remove trivially non-failing range check.
   5 define i32 @test_increasing_slt_slt_wide_simple_no_postloop() {
   6
   7 ; CHECK-LABEL: @test_increasing_slt_slt_wide_simple_no_postloop(
   8 ; CHECK-NOT:   preloop
   9 ; CHECK-NOT:   postloop
  10 ; CHECK:       loop:
  11 ; CHECK:       br i1 true, label %backedge, label %check_failed
  12
  13 entry:
  14   br label %loop
  15
  16 loop:
  17   %iv = phi i64 [ 0, %entry ], [ %iv.next, %backedge ]
  18   %rc = icmp slt i64 %iv, 100
  19   br i1 %rc, label %backedge, label %check_failed
  20
  21 backedge:
  22   %iv.next = add i64 %iv, 1
  23   %narrow.iv = trunc i64 %iv.next to i32
  24   %latch.cond = icmp slt i32 %narrow.iv, 100
  25   br i1 %latch.cond, label %loop, label %exit
  26
  27 exit:
  28   ret i32 %narrow.iv
  29
  30 check_failed:
  31   ret i32 -1
  32 }
  33
  34 ; This range check fails on the last iteration, so it needs a postloop.
  35 define i32 @test_increasing_slt_slt_wide_simple_postloop() {
  36
  37 ; CHECK-LABEL: @test_increasing_slt_slt_wide_simple_postloop(
  38 ; CHECK-NOT:   preloop
  39 ; CHECK:       loop:
  40 ; CHECK:       br i1 true, label %backedge, label %check_failed
  41 ; CHECK:       backedge
  42 ; CHECK:       [[COND:%[^ ]+]] = icmp slt i64 %wide.narrow.iv, 99
  43 ; CHECK:       br i1 [[COND]], label %loop, label %main.exit.selector
  44 ; CHECK:       postloop
  45
  46 entry:
  47   br label %loop
  48
  49 loop:
  50   %iv = phi i64 [ 0, %entry ], [ %iv.next, %backedge ]
  51   %rc = icmp slt i64 %iv, 99
  52   br i1 %rc, label %backedge, label %check_failed
  53
  54 backedge:
  55   %iv.next = add i64 %iv, 1
  56   %narrow.iv = trunc i64 %iv.next to i32
  57   %latch.cond = icmp slt i32 %narrow.iv, 100
  58   br i1 %latch.cond, label %loop, label %exit
  59
  60 exit:
  61   ret i32 %narrow.iv
  62
  63 check_failed:
  64   ret i32 -1
  65 }
  66
  67 ; General case. If both %N and %M are non-negative, we do not need a preloop.
  68 define i32 @test_increasing_slt_slt_wide_non-negative(i32* %n_ptr, i64* %m_ptr) {
  69
  70 ; CHECK-LABEL: @test_increasing_slt_slt_wide_non-negative(
  71 ; CHECK-NOT:   preloop
  72 ; CHECK:       loop:
  73 ; CHECK:       br i1 true, label %backedge, label %check_failed
  74 ; CHECK:       backedge
  75 ; CHECK:       [[COND:%[^ ]+]] = icmp slt i64 %wide.narrow.iv, %exit.mainloop.at
  76 ; CHECK:       br i1 [[COND]], label %loop, label %main.exit.selector
  77 ; CHECK:       postloop
  78
  79 entry:
  80   %N = load i32, i32* %n_ptr, !range !2
  81   %M = load i64, i64* %m_ptr, !range !1
  82   br label %loop
  83
  84 loop:
  85   %iv = phi i64 [ 0, %entry ], [ %iv.next, %backedge ]
  86   %rc = icmp slt i64 %iv, %M
  87   br i1 %rc, label %backedge, label %check_failed
  88
  89 backedge:
  90   %iv.next = add i64 %iv, 1
  91   %narrow.iv = trunc i64 %iv.next to i32
  92   %latch.cond = icmp slt i32 %narrow.iv, %N
  93   br i1 %latch.cond, label %loop, label %exit
  94
  95 exit:
  96   ret i32 %narrow.iv
  97
  98 check_failed:
  99   ret i32 -1
 100 }
 101
 102 ; General case. Even though %M may be negative, we do not need a preloop because
 103 ; we make a non-negativity runtime check against M and do not go to main loop if
 104 ; M was negative.
 105 define i32 @test_increasing_slt_slt_wide_general(i32* %n_ptr, i64* %m_ptr) {
 106
 107 ; CHECK-LABEL: @test_increasing_slt_slt_wide_general(
 108 ; CHECK-NOT:   preloop
 109 ; CHECK:       loop:
 110 ; CHECK:       br i1 true, label %backedge, label %check_failed
 111 ; CHECK:       backedge
 112 ; CHECK:       [[COND:%[^ ]+]] = icmp slt i64
 113 ; CHECK:       br i1 [[COND]], label %loop, label %main.exit.selector
 114 ; CHECK:       postloop
 115
 116 entry:
 117   %N = load i32, i32* %n_ptr, !range !2
 118   %M = load i64, i64* %m_ptr
 119   br label %loop
 120
 121 loop:
 122   %iv = phi i64 [ 0, %entry ], [ %iv.next, %backedge ]
 123   %rc = icmp slt i64 %iv, %M
 124   br i1 %rc, label %backedge, label %check_failed
 125
 126 backedge:
 127   %iv.next = add i64 %iv, 1
 128   %narrow.iv = trunc i64 %iv.next to i32
 129   %latch.cond = icmp slt i32 %narrow.iv, %N
 130   br i1 %latch.cond, label %loop, label %exit
 131
 132 exit:
 133   ret i32 %narrow.iv
 134
 135 check_failed:
 136   ret i32 -1
 137 }
 138
 139 ; General case with preloop.
 140 define i32 @test_increasing_slt_slt_wide_general_preloop(i32* %n_ptr, i64* %m_ptr) {
 141
 142 ; CHECK-LABEL: @test_increasing_slt_slt_wide_general_preloop(
 143 ; CHECK:       loop:
 144 ; CHECK:       br i1 true, label %backedge, label %check_failed
 145 ; CHECK:       backedge
 146 ; CHECK:       [[COND:%[^ ]+]] = icmp slt i64
 147 ; CHECK:       br i1 [[COND]], label %loop, label %main.exit.selector
 148 ; CHECK:       preloop
 149 ; CHECK:       postloop
 150
 151 entry:
 152   %N = load i32, i32* %n_ptr, !range !2
 153   %M = load i64, i64* %m_ptr
 154   br label %loop
 155
 156 loop:
 157   %iv = phi i64 [ 0, %entry ], [ %iv.next, %backedge ]
 158   %rc = icmp slt i64 %iv, %M
 159   br i1 %rc, label %backedge, label %check_failed
 160
 161 backedge:
 162   %iv.next = add i64 %iv, 1
 163   %narrow.iv = trunc i64 %iv to i32
 164   %latch.cond = icmp slt i32 %narrow.iv, %N
 165   br i1 %latch.cond, label %loop, label %exit
 166
 167 exit:
 168   ret i32 %narrow.iv
 169
 170 check_failed:
 171   ret i32 -1
 172 }
 173
 174 ; Same as above, multiple checks.
 175 define i32 @test_increasing_slt_slt_wide_multiple_checks(i32* %n_ptr, i64* %m1_ptr, i64* %m2_ptr, i64* %m3_ptr, i64* %m4_ptr) {
 176 ; CHECK-LABEL: @test_increasing_slt_slt_wide_multiple_checks(
 177 ; CHECK-NOT:   preloop
 178 ; CHECK:       loop:
 179 ; CHECK:       %c1 = and i1 true, true
 180 ; CHECK:       %c2 = and i1 %c1, true
 181 ; CHECK:       %rc = and i1 %c2, true
 182 ; CHECK:       br i1 %rc, label %backedge, label %check_failed.loopexit
 183 ; CHECK:       backedge
 184 ; CHECK:       [[COND:%[^ ]+]] = icmp slt i64
 185 ; CHECK:       br i1 [[COND]], label %loop, label %main.exit.selector
 186 ; CHECK:       postloop
 187
 188 entry:
 189   %N = load i32, i32* %n_ptr, !range !2
 190   %M1 = load i64, i64* %m1_ptr
 191   %M2 = load i64, i64* %m2_ptr
 192   %M3 = load i64, i64* %m3_ptr
 193   %M4 = load i64, i64* %m4_ptr
 194   br label %loop
 195
 196 loop:
 197   %iv = phi i64 [ 0, %entry ], [ %iv.next, %backedge ]
 198   %rc1 = icmp slt i64 %iv, %M1
 199   %rc2 = icmp slt i64 %iv, %M2
 200   %rc3 = icmp slt i64 %iv, %M3
 201   %rc4 = icmp slt i64 %iv, %M4
 202   %c1 = and i1 %rc1, %rc2
 203   %c2 = and i1 %c1, %rc3
 204   %rc = and i1 %c2, %rc4
 205   br i1 %rc, label %backedge, label %check_failed
 206
 207 backedge:
 208   %iv.next = add i64 %iv, 1
 209   %narrow.iv = trunc i64 %iv.next to i32
 210   %latch.cond = icmp slt i32 %narrow.iv, %N
 211   br i1 %latch.cond, label %loop, label %exit
 212
 213 exit:
 214   ret i32 %narrow.iv
 215
 216 check_failed:
 217   ret i32 -1
 218 }
 219
 220 ; Wide IV against narrow range check. We don't currently support it.
 221 define i32 @test_increasing_slt_slt_wide_simple_negtest_narrow_rc() {
 222
 223 ; CHECK-LABEL: @test_increasing_slt_slt_wide_simple_negtest_narrow_rc(
 224 ; CHECK-NOT:   i1 true
 225 ; CHECK-NOT:   main
 226
 227 entry:
 228   br label %loop
 229
 230 loop:
 231   %iv = phi i64 [ 0, %entry ], [ %iv.next, %backedge ]
 232   %narrow.iv = trunc i64 %iv to i32
 233   %rc = icmp slt i32 %narrow.iv, 101
 234   br i1 %rc, label %backedge, label %check_failed
 235
 236 backedge:
 237   %iv.next = add i64 %iv, 1
 238   %latch.cond = icmp slt i64 %iv, 100
 239   br i1 %latch.cond, label %loop, label %exit
 240
 241 exit:
 242   ret i32 %narrow.iv
 243
 244 check_failed:
 245   ret i32 -1
 246 }
 247
 248 ; Check that we can remove trivially non-failing range check.
 249 define i32 @test_increasing_ult_ult_wide_simple_no_postloop() {
 250
 251 ; CHECK-LABEL: @test_increasing_ult_ult_wide_simple_no_postloop(
 252 ; CHECK-NOT:   preloop
 253 ; CHECK-NOT:   postloop
 254 ; CHECK:       loop:
 255 ; CHECK:       br i1 true, label %backedge, label %check_failed
 256
 257 entry:
 258   br label %loop
 259
 260 loop:
 261   %iv = phi i64 [ 0, %entry ], [ %iv.next, %backedge ]
 262   %rc = icmp ult i64 %iv, 100
 263   br i1 %rc, label %backedge, label %check_failed
 264
 265 backedge:
 266   %iv.next = add i64 %iv, 1
 267   %narrow.iv = trunc i64 %iv.next to i32
 268   %latch.cond = icmp ult i32 %narrow.iv, 100
 269   br i1 %latch.cond, label %loop, label %exit
 270
 271 exit:
 272   ret i32 %narrow.iv
 273
 274 check_failed:
 275   ret i32 -1
 276 }
 277
 278 ; This range check fails on the last iteration, so it needs a postloop.
 279 define i32 @test_increasing_ult_ult_wide_simple_postloop() {
 280
 281 ; CHECK-LABEL: @test_increasing_ult_ult_wide_simple_postloop(
 282 ; CHECK-NOT:   preloop
 283 ; CHECK:       loop:
 284 ; CHECK:       br i1 true, label %backedge, label %check_failed
 285 ; CHECK:       backedge
 286 ; CHECK:       [[COND:%[^ ]+]] = icmp ult i64 %wide.narrow.iv, 99
 287 ; CHECK:       br i1 [[COND]], label %loop, label %main.exit.selector
 288 ; CHECK:       postloop
 289
 290 entry:
 291   br label %loop
 292
 293 loop:
 294   %iv = phi i64 [ 0, %entry ], [ %iv.next, %backedge ]
 295   %rc = icmp ult i64 %iv, 99
 296   br i1 %rc, label %backedge, label %check_failed
 297
 298 backedge:
 299   %iv.next = add i64 %iv, 1
 300   %narrow.iv = trunc i64 %iv.next to i32
 301   %latch.cond = icmp ult i32 %narrow.iv, 100
 302   br i1 %latch.cond, label %loop, label %exit
 303
 304 exit:
 305   ret i32 %narrow.iv
 306
 307 check_failed:
 308   ret i32 -1
 309 }
 310
 311 ; General case. If both %N and %M are non-negative, we do not need a preloop.
 312 define i32 @test_increasing_ult_ult_wide_non-negative(i32* %n_ptr, i64* %m_ptr) {
 313
 314 ; CHECK-LABEL: @test_increasing_ult_ult_wide_non-negative(
 315 ; CHECK-NOT:   preloop
 316 ; CHECK:       loop:
 317 ; CHECK:       br i1 true, label %backedge, label %check_failed
 318 ; CHECK:       backedge
 319 ; CHECK:       [[COND:%[^ ]+]] = icmp ult i64 %wide.narrow.iv, %exit.mainloop.at
 320 ; CHECK:       br i1 [[COND]], label %loop, label %main.exit.selector
 321 ; CHECK:       postloop
 322
 323 entry:
 324   %N = load i32, i32* %n_ptr, !range !2
 325   %M = load i64, i64* %m_ptr, !range !1
 326   br label %loop
 327
 328 loop:
 329   %iv = phi i64 [ 0, %entry ], [ %iv.next, %backedge ]
 330   %rc = icmp ult i64 %iv, %M
 331   br i1 %rc, label %backedge, label %check_failed
 332
 333 backedge:
 334   %iv.next = add i64 %iv, 1
 335   %narrow.iv = trunc i64 %iv.next to i32
 336   %latch.cond = icmp ult i32 %narrow.iv, %N
 337   br i1 %latch.cond, label %loop, label %exit
 338
 339 exit:
 340   ret i32 %narrow.iv
 341
 342 check_failed:
 343   ret i32 -1
 344 }
 345
 346 ; General case. Even though %M may be negative, we do not need a preloop because
 347 ; we make a non-negativity runtime check against M and do not go to main loop if
 348 ; M was negative.
 349 define i32 @test_increasing_ult_ult_wide_general(i32* %n_ptr, i64* %m_ptr) {
 350
 351 ; CHECK-LABEL: @test_increasing_ult_ult_wide_general(
 352 ; CHECK-NOT:   preloop
 353 ; CHECK:       loop:
 354 ; CHECK:       br i1 true, label %backedge, label %check_failed
 355 ; CHECK:       backedge
 356 ; CHECK:       [[COND:%[^ ]+]] = icmp ult i64
 357 ; CHECK:       br i1 [[COND]], label %loop, label %main.exit.selector
 358 ; CHECK:       postloop
 359
 360 entry:
 361   %N = load i32, i32* %n_ptr, !range !2
 362   %M = load i64, i64* %m_ptr
 363   br label %loop
 364
 365 loop:
 366   %iv = phi i64 [ 0, %entry ], [ %iv.next, %backedge ]
 367   %rc = icmp ult i64 %iv, %M
 368   br i1 %rc, label %backedge, label %check_failed
 369
 370 backedge:
 371   %iv.next = add i64 %iv, 1
 372   %narrow.iv = trunc i64 %iv.next to i32
 373   %latch.cond = icmp ult i32 %narrow.iv, %N
 374   br i1 %latch.cond, label %loop, label %exit
 375
 376 exit:
 377   ret i32 %narrow.iv
 378
 379 check_failed:
 380   ret i32 -1
 381 }
 382
 383 ; Same as above, multiple checks.
 384 define i32 @test_increasing_ult_ult_wide_multiple_checks(i32* %n_ptr, i64* %m1_ptr, i64* %m2_ptr, i64* %m3_ptr, i64* %m4_ptr) {
 385 ; CHECK-LABEL: @test_increasing_ult_ult_wide_multiple_checks(
 386 ; CHECK-NOT:   preloop
 387 ; CHECK:       loop:
 388 ; CHECK:       %c1 = and i1 true, true
 389 ; CHECK:       %c2 = and i1 %c1, true
 390 ; CHECK:       %rc = and i1 %c2, true
 391 ; CHECK:       br i1 %rc, label %backedge, label %check_failed.loopexit
 392 ; CHECK:       backedge
 393 ; CHECK:       [[COND:%[^ ]+]] = icmp ult i64
 394 ; CHECK:       br i1 [[COND]], label %loop, label %main.exit.selector
 395 ; CHECK:       postloop
 396
 397 entry:
 398   %N = load i32, i32* %n_ptr, !range !2
 399   %M1 = load i64, i64* %m1_ptr
 400   %M2 = load i64, i64* %m2_ptr
 401   %M3 = load i64, i64* %m3_ptr
 402   %M4 = load i64, i64* %m4_ptr
 403   br label %loop
 404
 405 loop:
 406   %iv = phi i64 [ 0, %entry ], [ %iv.next, %backedge ]
 407   %rc1 = icmp ult i64 %iv, %M1
 408   %rc2 = icmp ult i64 %iv, %M2
 409   %rc3 = icmp ult i64 %iv, %M3
 410   %rc4 = icmp ult i64 %iv, %M4
 411   %c1 = and i1 %rc1, %rc2
 412   %c2 = and i1 %c1, %rc3
 413   %rc = and i1 %c2, %rc4
 414   br i1 %rc, label %backedge, label %check_failed
 415
 416 backedge:
 417   %iv.next = add i64 %iv, 1
 418   %narrow.iv = trunc i64 %iv.next to i32
 419   %latch.cond = icmp ult i32 %narrow.iv, %N
 420   br i1 %latch.cond, label %loop, label %exit
 421
 422 exit:
 423   ret i32 %narrow.iv
 424
 425 check_failed:
 426   ret i32 -1
 427 }
 428
 429 ; Wide IV against narrow range check. We don't currently support it.
 430 define i32 @test_increasing_ult_ult_wide_simple_negtest_narrow_rc() {
 431
 432 ; CHECK-LABEL: @test_increasing_ult_ult_wide_simple_negtest_narrow_rc(
 433 ; CHECK-NOT:   i1 true
 434 ; CHECK-NOT:   main
 435
 436 entry:
 437   br label %loop
 438
 439 loop:
 440   %iv = phi i64 [ 0, %entry ], [ %iv.next, %backedge ]
 441   %narrow.iv = trunc i64 %iv to i32
 442   %rc = icmp ult i32 %narrow.iv, 101
 443   br i1 %rc, label %backedge, label %check_failed
 444
 445 backedge:
 446   %iv.next = add i64 %iv, 1
 447   %latch.cond = icmp ult i64 %iv, 100
 448   br i1 %latch.cond, label %loop, label %exit
 449
 450 exit:
 451   ret i32 %narrow.iv
 452
 453 check_failed:
 454   ret i32 -1
 455 }
 456
 457 !0 = !{i32 0, i32 2147483647}
 458 !1 = !{i64 0, i64 9223372036854775807}
 459 !2 = !{i32 1, i32 2147483647}