test/Transforms/IRCE/unsigned_comparisons_ult.ll

   1 ; RUN: opt -verify-loop-info -irce-print-changed-loops -irce -S < %s 2>&1 | FileCheck %s
   2 ; RUN: opt -verify-loop-info -irce-print-changed-loops -passes='require<branch-prob>,loop(irce)' -S < %s 2>&1 | FileCheck %s
   3
   4 ; CHECK: irce: in function test_01: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
   5 ; CHECK: irce: in function test_02: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
   6 ; CHECK: irce: in function test_03: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
   7 ; CHECK: irce: in function test_04: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
   8 ; CHECK: irce: in function test_05: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
   9 ; CHECK: irce: in function test_06: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
  10 ; CHECK-NOT: irce: in function test_07: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
  11 ; CHECK: irce: in function test_08: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
  12 ; CHECK-NOT: irce: in function test_09: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
  13
  14 ; ULT condition for increasing loop.
  15 define void @test_01(i32* %arr, i32* %a_len_ptr) #0 {
  16
  17 ; CHECK:      test_01
  18 ; CHECK:        entry:
  19 ; CHECK-NEXT:     %exit.mainloop.at = load i32, i32* %a_len_ptr, !range !0
  20 ; CHECK-NEXT:     [[COND:%[^ ]+]] = icmp ult i32 0, %exit.mainloop.at
  21 ; CHECK-NEXT:     br i1 [[COND]], label %loop.preheader, label %main.pseudo.exit
  22 ; CHECK:        loop:
  23 ; CHECK-NEXT:     %idx = phi i32 [ %idx.next, %in.bounds ], [ 0, %loop.preheader ]
  24 ; CHECK-NEXT:     %idx.next = add nuw nsw i32 %idx, 1
  25 ; CHECK-NEXT:     %abc = icmp ult i32 %idx, %exit.mainloop.at
  26 ; CHECK-NEXT:     br i1 true, label %in.bounds, label %out.of.bounds.loopexit1
  27 ; CHECK-NOT:    loop.preloop:
  28 ; CHECK:        loop.postloop:
  29 ; CHECK-NEXT:     %idx.postloop = phi i32 [ %idx.copy, %postloop ], [ %idx.next.postloop, %in.bounds.postloop ]
  30 ; CHECK-NEXT:     %idx.next.postloop = add nuw nsw i32 %idx.postloop, 1
  31 ; CHECK-NEXT:     %abc.postloop = icmp ult i32 %idx.postloop, %exit.mainloop.at
  32 ; CHECK-NEXT:     br i1 %abc.postloop, label %in.bounds.postloop, label %out.of.bounds.loopexit
  33
  34 entry:
  35   %len = load i32, i32* %a_len_ptr, !range !0
  36   br label %loop
  37
  38 loop:
  39   %idx = phi i32 [ 0, %entry ], [ %idx.next, %in.bounds ]
  40   %idx.next = add nsw nuw i32 %idx, 1
  41   %abc = icmp ult i32 %idx, %len
  42   br i1 %abc, label %in.bounds, label %out.of.bounds
  43
  44 in.bounds:
  45   %addr = getelementptr i32, i32* %arr, i32 %idx
  46   store i32 0, i32* %addr
  47   %next = icmp ult i32 %idx.next, 100
  48   br i1 %next, label %loop, label %exit
  49
  50 out.of.bounds:
  51   ret void
  52
  53 exit:
  54   ret void
  55 }
  56
  57 ; ULT condition for decreasing loops.
  58 define void @test_02(i32* %arr, i32* %a_len_ptr) #0 {
  59
  60 ; CHECK: test_02(
  61 ; CHECK:        entry:
  62 ; CHECK-NEXT:     %len = load i32, i32* %a_len_ptr, !range !0
  63 ; CHECK-NEXT:     [[COND1:%[^ ]+]] = icmp ugt i32 %len, 1
  64 ; CHECK-NEXT:     [[UMIN:%[^ ]+]] = select i1 [[COND1]], i32 %len, i32 1
  65 ; CHECK-NEXT:     %exit.preloop.at = add nsw i32 [[UMIN]], -1
  66 ; CHECK-NEXT:     [[COND2:%[^ ]+]] = icmp ugt i32 100, %exit.preloop.at
  67 ; CHECK-NEXT:     br i1 [[COND2]], label %loop.preloop.preheader, label %preloop.pseudo.exit
  68 ; CHECK:        mainloop:
  69 ; CHECK-NEXT:     br label %loop
  70 ; CHECK:        loop:
  71 ; CHECK-NEXT:     %idx = phi i32 [ %idx.preloop.copy, %mainloop ], [ %idx.next, %in.bounds ]
  72 ; CHECK-NEXT:     %idx.next = add i32 %idx, -1
  73 ; CHECK-NEXT:     %abc = icmp ult i32 %idx, %len
  74 ; CHECK-NEXT:     br i1 true, label %in.bounds, label %out.of.bounds.loopexit1
  75 ; CHECK-NOT:    loop.postloop:
  76 ; CHECK:        loop.preloop:
  77 ; CHECK-NEXT:     %idx.preloop = phi i32 [ %idx.next.preloop, %in.bounds.preloop ], [ 100, %loop.preloop.preheader ]
  78 ; CHECK-NEXT:     %idx.next.preloop = add i32 %idx.preloop, -1
  79 ; CHECK-NEXT:     %abc.preloop = icmp ult i32 %idx.preloop, %len
  80 ; CHECK-NEXT:     br i1 %abc.preloop, label %in.bounds.preloop, label %out.of.bounds.loopexit
  81
  82 entry:
  83   %len = load i32, i32* %a_len_ptr, !range !0
  84   br label %loop
  85
  86 loop:
  87   %idx = phi i32 [ 100, %entry ], [ %idx.next, %in.bounds ]
  88   %idx.next = add i32 %idx, -1
  89   %abc = icmp ult i32 %idx, %len
  90   br i1 %abc, label %in.bounds, label %out.of.bounds
  91
  92 in.bounds:
  93   %addr = getelementptr i32, i32* %arr, i32 %idx
  94   store i32 0, i32* %addr
  95   %next = icmp ult i32 %idx.next, 1
  96   br i1 %next, label %exit, label %loop
  97
  98 out.of.bounds:
  99   ret void
 100
 101 exit:
 102   ret void
 103 }
 104
 105 ; Check SINT_MAX.
 106 define void @test_03(i32* %arr, i32* %a_len_ptr) #0 {
 107
 108 ; CHECK:      test_03
 109 ; CHECK:        entry:
 110 ; CHECK-NEXT:     %exit.mainloop.at = load i32, i32* %a_len_ptr, !range !0
 111 ; CHECK-NEXT:     [[COND:%[^ ]+]] = icmp ult i32 0, %exit.mainloop.at
 112 ; CHECK-NEXT:     br i1 [[COND]], label %loop.preheader, label %main.pseudo.exit
 113 ; CHECK:        loop:
 114 ; CHECK-NEXT:     %idx = phi i32 [ %idx.next, %in.bounds ], [ 0, %loop.preheader ]
 115 ; CHECK-NEXT:     %idx.next = add nuw nsw i32 %idx, 1
 116 ; CHECK-NEXT:     %abc = icmp ult i32 %idx, %exit.mainloop.at
 117 ; CHECK-NEXT:     br i1 true, label %in.bounds, label %out.of.bounds.loopexit1
 118 ; CHECK-NOT:    loop.preloop:
 119 ; CHECK:        loop.postloop:
 120 ; CHECK-NEXT:     %idx.postloop = phi i32 [ %idx.copy, %postloop ], [ %idx.next.postloop, %in.bounds.postloop ]
 121 ; CHECK-NEXT:     %idx.next.postloop = add nuw nsw i32 %idx.postloop, 1
 122 ; CHECK-NEXT:     %abc.postloop = icmp ult i32 %idx.postloop, %exit.mainloop.at
 123 ; CHECK-NEXT:     br i1 %abc.postloop, label %in.bounds.postloop, label %out.of.bounds.loopexit
 124
 125 entry:
 126   %len = load i32, i32* %a_len_ptr, !range !0
 127   br label %loop
 128
 129 loop:
 130   %idx = phi i32 [ 0, %entry ], [ %idx.next, %in.bounds ]
 131   %idx.next = add nsw nuw i32 %idx, 1
 132   %abc = icmp ult i32 %idx, %len
 133   br i1 %abc, label %in.bounds, label %out.of.bounds
 134
 135 in.bounds:
 136   %addr = getelementptr i32, i32* %arr, i32 %idx
 137   store i32 0, i32* %addr
 138   %next = icmp ult i32 %idx.next, 2147483647
 139   br i1 %next, label %loop, label %exit
 140
 141 out.of.bounds:
 142   ret void
 143
 144 exit:
 145   ret void
 146 }
 147
 148 ; Check SINT_MAX + 1, test is similar to test_01.
 149 define void @test_04(i32* %arr, i32* %a_len_ptr) #0 {
 150
 151 ; CHECK:      test_04
 152 ; CHECK:        entry:
 153 ; CHECK-NEXT:     %exit.mainloop.at = load i32, i32* %a_len_ptr, !range !0
 154 ; CHECK-NEXT:     [[COND:%[^ ]+]] = icmp ult i32 0, %exit.mainloop.at
 155 ; CHECK-NEXT:     br i1 [[COND]], label %loop.preheader, label %main.pseudo.exit
 156 ; CHECK:        loop:
 157 ; CHECK-NEXT:     %idx = phi i32 [ %idx.next, %in.bounds ], [ 0, %loop.preheader ]
 158 ; CHECK-NEXT:     %idx.next = add nuw nsw i32 %idx, 1
 159 ; CHECK-NEXT:     %abc = icmp ult i32 %idx, %exit.mainloop.at
 160 ; CHECK-NEXT:     br i1 true, label %in.bounds, label %out.of.bounds.loopexit1
 161 ; CHECK-NOT:    loop.preloop:
 162 ; CHECK:        loop.postloop:
 163 ; CHECK-NEXT:     %idx.postloop = phi i32 [ %idx.copy, %postloop ], [ %idx.next.postloop, %in.bounds.postloop ]
 164 ; CHECK-NEXT:     %idx.next.postloop = add nuw nsw i32 %idx.postloop, 1
 165 ; CHECK-NEXT:     %abc.postloop = icmp ult i32 %idx.postloop, %exit.mainloop.at
 166 ; CHECK-NEXT:     br i1 %abc.postloop, label %in.bounds.postloop, label %out.of.bounds.loopexit
 167
 168 entry:
 169   %len = load i32, i32* %a_len_ptr, !range !0
 170   br label %loop
 171
 172 loop:
 173   %idx = phi i32 [ 0, %entry ], [ %idx.next, %in.bounds ]
 174   %idx.next = add nsw nuw i32 %idx, 1
 175   %abc = icmp ult i32 %idx, %len
 176   br i1 %abc, label %in.bounds, label %out.of.bounds
 177
 178 in.bounds:
 179   %addr = getelementptr i32, i32* %arr, i32 %idx
 180   store i32 0, i32* %addr
 181   %next = icmp ult i32 %idx.next, 2147483648
 182   br i1 %next, label %loop, label %exit
 183
 184 out.of.bounds:
 185   ret void
 186
 187 exit:
 188   ret void
 189 }
 190
 191 ; Check SINT_MAX + 1, test is similar to test_02.
 192 define void @test_05(i32* %arr, i32* %a_len_ptr) #0 {
 193 ; CHECK: test_05(
 194 ; CHECK:        entry:
 195 ; CHECK-NEXT:     %len = load i32, i32* %a_len_ptr, !range !0
 196 ; CHECK-NEXT:     [[COND1:%[^ ]+]] = icmp ugt i32 %len, 1
 197 ; CHECK-NEXT:     [[UMIN:%[^ ]+]] = select i1 [[COND1]], i32 %len, i32 1
 198 ; CHECK-NEXT:     %exit.preloop.at = add nsw i32 [[UMIN]], -1
 199 ; CHECK-NEXT:     [[COND2:%[^ ]+]] = icmp ugt i32 -2147483648, %exit.preloop.at
 200 ; CHECK-NEXT:     br i1 [[COND2]], label %loop.preloop.preheader, label %preloop.pseudo.exit
 201 ; CHECK:        mainloop:
 202 ; CHECK-NEXT:     br label %loop
 203 ; CHECK:        loop:
 204 ; CHECK-NEXT:     %idx = phi i32 [ %idx.preloop.copy, %mainloop ], [ %idx.next, %in.bounds ]
 205 ; CHECK-NEXT:     %idx.next = add i32 %idx, -1
 206 ; CHECK-NEXT:     %abc = icmp ult i32 %idx, %len
 207 ; CHECK-NEXT:     br i1 true, label %in.bounds, label %out.of.bounds.loopexit1
 208 ; CHECK-NOT:    loop.postloop:
 209 ; CHECK:        loop.preloop:
 210 ; CHECK-NEXT:     %idx.preloop = phi i32 [ %idx.next.preloop, %in.bounds.preloop ], [ -2147483648, %loop.preloop.preheader ]
 211 ; CHECK-NEXT:     %idx.next.preloop = add i32 %idx.preloop, -1
 212 ; CHECK-NEXT:     %abc.preloop = icmp ult i32 %idx.preloop, %len
 213 ; CHECK-NEXT:     br i1 %abc.preloop, label %in.bounds.preloop, label %out.of.bounds.loopexit
 214
 215 entry:
 216   %len = load i32, i32* %a_len_ptr, !range !0
 217   br label %loop
 218
 219 loop:
 220   %idx = phi i32 [ 2147483648, %entry ], [ %idx.next, %in.bounds ]
 221   %idx.next = add i32 %idx, -1
 222   %abc = icmp ult i32 %idx, %len
 223   br i1 %abc, label %in.bounds, label %out.of.bounds
 224
 225 in.bounds:
 226   %addr = getelementptr i32, i32* %arr, i32 %idx
 227   store i32 0, i32* %addr
 228   %next = icmp ult i32 %idx.next, 1
 229   br i1 %next, label %exit, label %loop
 230
 231 out.of.bounds:
 232   ret void
 233
 234 exit:
 235   ret void
 236 }
 237
 238 ; Increasing loop, UINT_MAX. Positive test.
 239 define void @test_06(i32* %arr, i32* %a_len_ptr) #0 {
 240
 241 ; CHECK:      test_06
 242 ; CHECK:        entry:
 243 ; CHECK-NEXT:     %exit.mainloop.at = load i32, i32* %a_len_ptr, !range !0
 244 ; CHECK-NEXT:     [[COND:%[^ ]+]] = icmp ult i32 0, %exit.mainloop.at
 245 ; CHECK-NEXT:     br i1 [[COND]], label %loop.preheader, label %main.pseudo.exit
 246 ; CHECK:        loop:
 247 ; CHECK-NEXT:     %idx = phi i32 [ %idx.next, %in.bounds ], [ 0, %loop.preheader ]
 248 ; CHECK-NEXT:     %idx.next = add nuw nsw i32 %idx, 1
 249 ; CHECK-NEXT:     %abc = icmp ult i32 %idx, %exit.mainloop.at
 250 ; CHECK-NEXT:     br i1 true, label %in.bounds, label %out.of.bounds.loopexit1
 251 ; CHECK-NOT:    loop.preloop:
 252 ; CHECK:        loop.postloop:
 253 ; CHECK-NEXT:     %idx.postloop = phi i32 [ %idx.copy, %postloop ], [ %idx.next.postloop, %in.bounds.postloop ]
 254 ; CHECK-NEXT:     %idx.next.postloop = add nuw nsw i32 %idx.postloop, 1
 255 ; CHECK-NEXT:     %abc.postloop = icmp ult i32 %idx.postloop, %exit.mainloop.at
 256 ; CHECK-NEXT:     br i1 %abc.postloop, label %in.bounds.postloop, label %out.of.bounds.loopexit
 257
 258 entry:
 259   %len = load i32, i32* %a_len_ptr, !range !0
 260   br label %loop
 261
 262 loop:
 263   %idx = phi i32 [ 0, %entry ], [ %idx.next, %in.bounds ]
 264   %idx.next = add nsw nuw i32 %idx, 1
 265   %abc = icmp ult i32 %idx, %len
 266   br i1 %abc, label %in.bounds, label %out.of.bounds
 267
 268 in.bounds:
 269   %addr = getelementptr i32, i32* %arr, i32 %idx
 270   store i32 0, i32* %addr
 271   %next = icmp ult i32 %idx.next, 4294967295
 272   br i1 %next, label %loop, label %exit
 273
 274 out.of.bounds:
 275   ret void
 276
 277 exit:
 278   ret void
 279 }
 280
 281 ; Decreasing loop, UINT_MAX. Negative test: we cannot substract -1 from 0.
 282 define void @test_07(i32* %arr, i32* %a_len_ptr) #0 {
 283
 284 ; CHECK: test_07(
 285 ; CHECK-NOT:    loop.preloop:
 286 ; CHECK-NOT:    loop.postloop:
 287
 288 entry:
 289   %len = load i32, i32* %a_len_ptr, !range !0
 290   br label %loop
 291
 292 loop:
 293   %idx = phi i32 [ 4294967295, %entry ], [ %idx.next, %in.bounds ]
 294   %idx.next = add nuw i32 %idx, -1
 295   %abc = icmp ult i32 %idx, %len
 296   br i1 %abc, label %in.bounds, label %out.of.bounds
 297
 298 in.bounds:
 299   %addr = getelementptr i32, i32* %arr, i32 %idx
 300   store i32 0, i32* %addr
 301   %next = icmp ult i32 %idx.next, 0
 302   br i1 %next, label %exit, label %loop
 303
 304 out.of.bounds:
 305   ret void
 306
 307 exit:
 308   ret void
 309 }
 310
 311 ; Unsigned walking through signed border is allowed.
 312 ; Iteration space [0; UINT_MAX - 99), the fact that SINT_MAX is within this
 313 ; range does not prevent us from performing IRCE.
 314
 315 define void @test_08(i32* %arr, i32* %a_len_ptr) #0 {
 316
 317 ; CHECK:      test_08
 318 ; CHECK:        entry:
 319 ; CHECK-NEXT:     %exit.mainloop.at = load i32, i32* %a_len_ptr, !range !0
 320 ; CHECK-NEXT:     [[COND:%[^ ]+]] = icmp ult i32 0, %exit.mainloop.at
 321 ; CHECK-NEXT:     br i1 [[COND]], label %loop.preheader, label %main.pseudo.exit
 322 ; CHECK:        loop:
 323 ; CHECK-NEXT:     %idx = phi i32 [ %idx.next, %in.bounds ], [ 0, %loop.preheader ]
 324 ; CHECK-NEXT:     %idx.next = add i32 %idx, 1
 325 ; CHECK-NEXT:     %abc = icmp ult i32 %idx, %exit.mainloop.at
 326 ; CHECK-NEXT:     br i1 true, label %in.bounds, label %out.of.bounds.loopexit1
 327 ; CHECK-NOT:    loop.preloop:
 328 ; CHECK:        loop.postloop:
 329 ; CHECK-NEXT:     %idx.postloop = phi i32 [ %idx.copy, %postloop ], [ %idx.next.postloop, %in.bounds.postloop ]
 330 ; CHECK-NEXT:     %idx.next.postloop = add i32 %idx.postloop, 1
 331 ; CHECK-NEXT:     %abc.postloop = icmp ult i32 %idx.postloop, %exit.mainloop.at
 332 ; CHECK-NEXT:     br i1 %abc.postloop, label %in.bounds.postloop, label %out.of.bounds.loopexit
 333
 334 entry:
 335   %len = load i32, i32* %a_len_ptr, !range !0
 336   br label %loop
 337
 338 loop:
 339   %idx = phi i32 [ 0, %entry ], [ %idx.next, %in.bounds ]
 340   %idx.next = add i32 %idx, 1
 341   %abc = icmp ult i32 %idx, %len
 342   br i1 %abc, label %in.bounds, label %out.of.bounds
 343
 344 in.bounds:
 345   %addr = getelementptr i32, i32* %arr, i32 %idx
 346   store i32 0, i32* %addr
 347   %next = icmp ult i32 %idx.next, -100
 348   br i1 %next, label %loop, label %exit
 349
 350 out.of.bounds:
 351   ret void
 352
 353 exit:
 354   ret void
 355 }
 356
 357 ; Walking through the border of unsigned range is not allowed
 358 ; (iteration space [-100; 100)). Negative test.
 359
 360 define void @test_09(i32* %arr, i32* %a_len_ptr) #0 {
 361
 362 ; CHECK:      test_09
 363 ; CHECK-NOT:  preloop
 364 ; CHECK-NOT:  postloop
 365 ; CHECK-NOT:  br i1 false
 366 ; CHECK-NOT:  br i1 true
 367
 368 entry:
 369   %len = load i32, i32* %a_len_ptr, !range !0
 370   br label %loop
 371
 372 loop:
 373   %idx = phi i32 [ -100, %entry ], [ %idx.next, %in.bounds ]
 374   %idx.next = add i32 %idx, 1
 375   %abc = icmp ult i32 %idx, %len
 376   br i1 %abc, label %in.bounds, label %out.of.bounds
 377
 378 in.bounds:
 379   %addr = getelementptr i32, i32* %arr, i32 %idx
 380   store i32 0, i32* %addr
 381   %next = icmp ult i32 %idx.next, 100
 382   br i1 %next, label %loop, label %exit
 383
 384 out.of.bounds:
 385   ret void
 386
 387 exit:
 388   ret void
 389 }
 390
 391 !0 = !{i32 0, i32 50}