llvm/test/Transforms/IRCE/rc-negative-bound.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt -verify-loop-info -irce-print-changed-loops -passes=irce -S < %s 2>&1 | FileCheck %s
   3 ; RUN: opt -verify-loop-info -irce-print-changed-loops -passes='require<branch-prob>,irce' -S < %s 2>&1 | FileCheck %s
   4
   5 ; CHECK-NOT: irce: in function test_01: constrained Loop
   6 ; CHECK-NOT: irce: in function test_02: constrained Loop
   7 ; CHECK: irce: in function test_03: constrained Loop
   8
   9 ; RC against known negative value. We should not do IRCE here.
  10 define void @test_01(ptr %arr, i32 %n) {
  11 ; CHECK-LABEL: @test_01(
  12 ; CHECK-NEXT:  entry:
  13 ; CHECK-NEXT:    [[FIRST_ITR_CHECK:%.*]] = icmp sgt i32 [[N:%.*]], 0
  14 ; CHECK-NEXT:    br i1 [[FIRST_ITR_CHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
  15 ; CHECK:       loop.preheader:
  16 ; CHECK-NEXT:    br label [[LOOP:%.*]]
  17 ; CHECK:       loop:
  18 ; CHECK-NEXT:    [[IDX:%.*]] = phi i32 [ [[IDX_NEXT:%.*]], [[IN_BOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
  19 ; CHECK-NEXT:    [[IDX_NEXT]] = add i32 [[IDX]], 1
  20 ; CHECK-NEXT:    [[ABC:%.*]] = icmp slt i32 [[IDX]], -9
  21 ; CHECK-NEXT:    br i1 [[ABC]], label [[IN_BOUNDS]], label [[OUT_OF_BOUNDS:%.*]], !prof [[PROF0:![0-9]+]]
  22 ; CHECK:       in.bounds:
  23 ; CHECK-NEXT:    [[ADDR:%.*]] = getelementptr i32, ptr [[ARR:%.*]], i32 [[IDX]]
  24 ; CHECK-NEXT:    store i32 0, ptr [[ADDR]], align 4
  25 ; CHECK-NEXT:    [[NEXT:%.*]] = icmp slt i32 [[IDX_NEXT]], [[N]]
  26 ; CHECK-NEXT:    br i1 [[NEXT]], label [[LOOP]], label [[EXIT_LOOPEXIT:%.*]]
  27 ; CHECK:       out.of.bounds:
  28 ; CHECK-NEXT:    ret void
  29 ; CHECK:       exit.loopexit:
  30 ; CHECK-NEXT:    br label [[EXIT]]
  31 ; CHECK:       exit:
  32 ; CHECK-NEXT:    ret void
  33 ;
  34
  35   entry:
  36   %first.itr.check = icmp sgt i32 %n, 0
  37   br i1 %first.itr.check, label %loop, label %exit
  38
  39   loop:
  40   %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ]
  41   %idx.next = add i32 %idx, 1
  42   %abc = icmp slt i32 %idx, -9
  43   br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !0
  44
  45   in.bounds:
  46   %addr = getelementptr i32, ptr %arr, i32 %idx
  47   store i32 0, ptr %addr
  48   %next = icmp slt i32 %idx.next, %n
  49   br i1 %next, label %loop, label %exit
  50
  51   out.of.bounds:
  52   ret void
  53
  54   exit:
  55   ret void
  56 }
  57
  58 ; Same as test_01, but the latch condition is unsigned.
  59 define void @test_02(ptr %arr, i32 %n) {
  60 ; CHECK-LABEL: @test_02(
  61 ; CHECK-NEXT:  entry:
  62 ; CHECK-NEXT:    [[FIRST_ITR_CHECK:%.*]] = icmp sgt i32 [[N:%.*]], 0
  63 ; CHECK-NEXT:    br i1 [[FIRST_ITR_CHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
  64 ; CHECK:       loop.preheader:
  65 ; CHECK-NEXT:    br label [[LOOP:%.*]]
  66 ; CHECK:       loop:
  67 ; CHECK-NEXT:    [[IDX:%.*]] = phi i32 [ [[IDX_NEXT:%.*]], [[IN_BOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
  68 ; CHECK-NEXT:    [[IDX_NEXT]] = add i32 [[IDX]], 1
  69 ; CHECK-NEXT:    [[ABC:%.*]] = icmp slt i32 [[IDX]], -9
  70 ; CHECK-NEXT:    br i1 [[ABC]], label [[IN_BOUNDS]], label [[OUT_OF_BOUNDS:%.*]], !prof [[PROF0]]
  71 ; CHECK:       in.bounds:
  72 ; CHECK-NEXT:    [[ADDR:%.*]] = getelementptr i32, ptr [[ARR:%.*]], i32 [[IDX]]
  73 ; CHECK-NEXT:    store i32 0, ptr [[ADDR]], align 4
  74 ; CHECK-NEXT:    [[NEXT:%.*]] = icmp ult i32 [[IDX_NEXT]], [[N]]
  75 ; CHECK-NEXT:    br i1 [[NEXT]], label [[LOOP]], label [[EXIT_LOOPEXIT:%.*]]
  76 ; CHECK:       out.of.bounds:
  77 ; CHECK-NEXT:    ret void
  78 ; CHECK:       exit.loopexit:
  79 ; CHECK-NEXT:    br label [[EXIT]]
  80 ; CHECK:       exit:
  81 ; CHECK-NEXT:    ret void
  82 ;
  83
  84   entry:
  85   %first.itr.check = icmp sgt i32 %n, 0
  86   br i1 %first.itr.check, label %loop, label %exit
  87
  88   loop:
  89   %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ]
  90   %idx.next = add i32 %idx, 1
  91   %abc = icmp slt i32 %idx, -9
  92   br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !0
  93
  94   in.bounds:
  95   %addr = getelementptr i32, ptr %arr, i32 %idx
  96   store i32 0, ptr %addr
  97   %next = icmp ult i32 %idx.next, %n
  98   br i1 %next, label %loop, label %exit
  99
 100   out.of.bounds:
 101   ret void
 102
 103   exit:
 104   ret void
 105 }
 106
 107 ; RC against a value which is not known to be non-negative. Here we should
 108 ; expand runtime checks against bound being positive or negative.
 109 define void @test_03(ptr %arr, i32 %n, i32 %bound) {
 110 ; CHECK-LABEL: @test_03(
 111 ; CHECK-NEXT:  entry:
 112 ; CHECK-NEXT:    [[FIRST_ITR_CHECK:%.*]] = icmp sgt i32 [[N:%.*]], 0
 113 ; CHECK-NEXT:    br i1 [[FIRST_ITR_CHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
 114 ; CHECK:       loop.preheader:
 115 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[BOUND:%.*]], -2147483647
 116 ; CHECK-NEXT:    [[SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[TMP0]], i32 0)
 117 ; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 [[BOUND]], [[SMAX]]
 118 ; CHECK-NEXT:    [[SMIN:%.*]] = call i32 @llvm.smin.i32(i32 [[BOUND]], i32 0)
 119 ; CHECK-NEXT:    [[SMAX1:%.*]] = call i32 @llvm.smax.i32(i32 [[SMIN]], i32 -1)
 120 ; CHECK-NEXT:    [[TMP2:%.*]] = add nsw i32 [[SMAX1]], 1
 121 ; CHECK-NEXT:    [[TMP3:%.*]] = mul i32 [[TMP1]], [[TMP2]]
 122 ; CHECK-NEXT:    [[SMIN2:%.*]] = call i32 @llvm.smin.i32(i32 [[N]], i32 [[TMP3]])
 123 ; CHECK-NEXT:    [[EXIT_MAINLOOP_AT:%.*]] = call i32 @llvm.smax.i32(i32 [[SMIN2]], i32 0)
 124 ; CHECK-NEXT:    [[TMP4:%.*]] = icmp slt i32 0, [[EXIT_MAINLOOP_AT]]
 125 ; CHECK-NEXT:    br i1 [[TMP4]], label [[LOOP_PREHEADER4:%.*]], label [[MAIN_PSEUDO_EXIT:%.*]]
 126 ; CHECK:       loop.preheader4:
 127 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 128 ; CHECK:       loop:
 129 ; CHECK-NEXT:    [[IDX:%.*]] = phi i32 [ [[IDX_NEXT:%.*]], [[IN_BOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER4]] ]
 130 ; CHECK-NEXT:    [[IDX_NEXT]] = add nsw i32 [[IDX]], 1
 131 ; CHECK-NEXT:    [[ABC:%.*]] = icmp slt i32 [[IDX]], [[BOUND]]
 132 ; CHECK-NEXT:    br i1 true, label [[IN_BOUNDS]], label [[OUT_OF_BOUNDS_LOOPEXIT5:%.*]], !prof [[PROF0]]
 133 ; CHECK:       in.bounds:
 134 ; CHECK-NEXT:    [[ADDR:%.*]] = getelementptr i32, ptr [[ARR:%.*]], i32 [[IDX]]
 135 ; CHECK-NEXT:    store i32 0, ptr [[ADDR]], align 4
 136 ; CHECK-NEXT:    [[NEXT:%.*]] = icmp slt i32 [[IDX_NEXT]], [[N]]
 137 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp slt i32 [[IDX_NEXT]], [[EXIT_MAINLOOP_AT]]
 138 ; CHECK-NEXT:    br i1 [[TMP5]], label [[LOOP]], label [[MAIN_EXIT_SELECTOR:%.*]]
 139 ; CHECK:       main.exit.selector:
 140 ; CHECK-NEXT:    [[IDX_NEXT_LCSSA:%.*]] = phi i32 [ [[IDX_NEXT]], [[IN_BOUNDS]] ]
 141 ; CHECK-NEXT:    [[TMP6:%.*]] = icmp slt i32 [[IDX_NEXT_LCSSA]], [[N]]
 142 ; CHECK-NEXT:    br i1 [[TMP6]], label [[MAIN_PSEUDO_EXIT]], label [[EXIT_LOOPEXIT:%.*]]
 143 ; CHECK:       main.pseudo.exit:
 144 ; CHECK-NEXT:    [[IDX_COPY:%.*]] = phi i32 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]
 145 ; CHECK-NEXT:    [[INDVAR_END:%.*]] = phi i32 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]
 146 ; CHECK-NEXT:    br label [[POSTLOOP:%.*]]
 147 ; CHECK:       out.of.bounds.loopexit:
 148 ; CHECK-NEXT:    br label [[OUT_OF_BOUNDS:%.*]]
 149 ; CHECK:       out.of.bounds.loopexit5:
 150 ; CHECK-NEXT:    br label [[OUT_OF_BOUNDS]]
 151 ; CHECK:       out.of.bounds:
 152 ; CHECK-NEXT:    ret void
 153 ; CHECK:       exit.loopexit.loopexit:
 154 ; CHECK-NEXT:    br label [[EXIT_LOOPEXIT]]
 155 ; CHECK:       exit.loopexit:
 156 ; CHECK-NEXT:    br label [[EXIT]]
 157 ; CHECK:       exit:
 158 ; CHECK-NEXT:    ret void
 159 ; CHECK:       postloop:
 160 ; CHECK-NEXT:    br label [[LOOP_POSTLOOP:%.*]]
 161 ; CHECK:       loop.postloop:
 162 ; CHECK-NEXT:    [[IDX_POSTLOOP:%.*]] = phi i32 [ [[IDX_NEXT_POSTLOOP:%.*]], [[IN_BOUNDS_POSTLOOP:%.*]] ], [ [[IDX_COPY]], [[POSTLOOP]] ]
 163 ; CHECK-NEXT:    [[IDX_NEXT_POSTLOOP]] = add i32 [[IDX_POSTLOOP]], 1
 164 ; CHECK-NEXT:    [[ABC_POSTLOOP:%.*]] = icmp slt i32 [[IDX_POSTLOOP]], [[BOUND]]
 165 ; CHECK-NEXT:    br i1 [[ABC_POSTLOOP]], label [[IN_BOUNDS_POSTLOOP]], label [[OUT_OF_BOUNDS_LOOPEXIT:%.*]], !prof [[PROF0]]
 166 ; CHECK:       in.bounds.postloop:
 167 ; CHECK-NEXT:    [[ADDR_POSTLOOP:%.*]] = getelementptr i32, ptr [[ARR]], i32 [[IDX_POSTLOOP]]
 168 ; CHECK-NEXT:    store i32 0, ptr [[ADDR_POSTLOOP]], align 4
 169 ; CHECK-NEXT:    [[NEXT_POSTLOOP:%.*]] = icmp slt i32 [[IDX_NEXT_POSTLOOP]], [[N]]
 170 ; CHECK-NEXT:    br i1 [[NEXT_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT:%.*]], !llvm.loop [[LOOP1:![0-9]+]], !loop_constrainer.loop.clone [[META6:![0-9]+]]
 171 ;
 172
 173   entry:
 174   %first.itr.check = icmp sgt i32 %n, 0
 175   br i1 %first.itr.check, label %loop, label %exit
 176
 177   loop:
 178   %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ]
 179   %idx.next = add i32 %idx, 1
 180   %abc = icmp slt i32 %idx, %bound
 181   br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !0
 182
 183   in.bounds:
 184   %addr = getelementptr i32, ptr %arr, i32 %idx
 185   store i32 0, ptr %addr
 186   %next = icmp slt i32 %idx.next, %n
 187   br i1 %next, label %loop, label %exit
 188
 189   out.of.bounds:
 190   ret void
 191
 192   exit:
 193   ret void
 194 }
 195
 196 ; RC against a value which is not known to be non-negative. Here we should
 197 ; expand runtime checks against bound being positive or negative.
 198 define void @test_04(ptr %arr, i32 %n, i32 %bound) {
 199 ; CHECK-LABEL: @test_04(
 200 ; CHECK-NEXT:  entry:
 201 ; CHECK-NEXT:    [[FIRST_ITR_CHECK:%.*]] = icmp sgt i32 [[N:%.*]], 0
 202 ; CHECK-NEXT:    br i1 [[FIRST_ITR_CHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
 203 ; CHECK:       loop.preheader:
 204 ; CHECK-NEXT:    [[SMIN:%.*]] = call i32 @llvm.smin.i32(i32 [[BOUND:%.*]], i32 0)
 205 ; CHECK-NEXT:    [[TMP0:%.*]] = sub i32 [[BOUND]], [[SMIN]]
 206 ; CHECK-NEXT:    [[SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[SMIN]], i32 -1)
 207 ; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i32 [[SMAX]], 1
 208 ; CHECK-NEXT:    [[TMP2:%.*]] = mul i32 [[TMP0]], [[TMP1]]
 209 ; CHECK-NEXT:    [[EXIT_MAINLOOP_AT:%.*]] = call i32 @llvm.umin.i32(i32 [[N]], i32 [[TMP2]])
 210 ; CHECK-NEXT:    [[TMP3:%.*]] = icmp ult i32 0, [[EXIT_MAINLOOP_AT]]
 211 ; CHECK-NEXT:    br i1 [[TMP3]], label [[LOOP_PREHEADER1:%.*]], label [[MAIN_PSEUDO_EXIT:%.*]]
 212 ; CHECK:       loop.preheader1:
 213 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 214 ; CHECK:       loop:
 215 ; CHECK-NEXT:    [[IDX:%.*]] = phi i32 [ [[IDX_NEXT:%.*]], [[IN_BOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER1]] ]
 216 ; CHECK-NEXT:    [[IDX_NEXT]] = add i32 [[IDX]], 1
 217 ; CHECK-NEXT:    [[ABC:%.*]] = icmp slt i32 [[IDX]], [[BOUND]]
 218 ; CHECK-NEXT:    br i1 true, label [[IN_BOUNDS]], label [[OUT_OF_BOUNDS_LOOPEXIT2:%.*]], !prof [[PROF0]]
 219 ; CHECK:       in.bounds:
 220 ; CHECK-NEXT:    [[ADDR:%.*]] = getelementptr i32, ptr [[ARR:%.*]], i32 [[IDX]]
 221 ; CHECK-NEXT:    store i32 0, ptr [[ADDR]], align 4
 222 ; CHECK-NEXT:    [[NEXT:%.*]] = icmp ult i32 [[IDX_NEXT]], [[N]]
 223 ; CHECK-NEXT:    [[TMP4:%.*]] = icmp ult i32 [[IDX_NEXT]], [[EXIT_MAINLOOP_AT]]
 224 ; CHECK-NEXT:    br i1 [[TMP4]], label [[LOOP]], label [[MAIN_EXIT_SELECTOR:%.*]]
 225 ; CHECK:       main.exit.selector:
 226 ; CHECK-NEXT:    [[IDX_NEXT_LCSSA:%.*]] = phi i32 [ [[IDX_NEXT]], [[IN_BOUNDS]] ]
 227 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp ult i32 [[IDX_NEXT_LCSSA]], [[N]]
 228 ; CHECK-NEXT:    br i1 [[TMP5]], label [[MAIN_PSEUDO_EXIT]], label [[EXIT_LOOPEXIT:%.*]]
 229 ; CHECK:       main.pseudo.exit:
 230 ; CHECK-NEXT:    [[IDX_COPY:%.*]] = phi i32 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]
 231 ; CHECK-NEXT:    [[INDVAR_END:%.*]] = phi i32 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]
 232 ; CHECK-NEXT:    br label [[POSTLOOP:%.*]]
 233 ; CHECK:       out.of.bounds.loopexit:
 234 ; CHECK-NEXT:    br label [[OUT_OF_BOUNDS:%.*]]
 235 ; CHECK:       out.of.bounds.loopexit2:
 236 ; CHECK-NEXT:    br label [[OUT_OF_BOUNDS]]
 237 ; CHECK:       out.of.bounds:
 238 ; CHECK-NEXT:    ret void
 239 ; CHECK:       exit.loopexit.loopexit:
 240 ; CHECK-NEXT:    br label [[EXIT_LOOPEXIT]]
 241 ; CHECK:       exit.loopexit:
 242 ; CHECK-NEXT:    br label [[EXIT]]
 243 ; CHECK:       exit:
 244 ; CHECK-NEXT:    ret void
 245 ; CHECK:       postloop:
 246 ; CHECK-NEXT:    br label [[LOOP_POSTLOOP:%.*]]
 247 ; CHECK:       loop.postloop:
 248 ; CHECK-NEXT:    [[IDX_POSTLOOP:%.*]] = phi i32 [ [[IDX_NEXT_POSTLOOP:%.*]], [[IN_BOUNDS_POSTLOOP:%.*]] ], [ [[IDX_COPY]], [[POSTLOOP]] ]
 249 ; CHECK-NEXT:    [[IDX_NEXT_POSTLOOP]] = add i32 [[IDX_POSTLOOP]], 1
 250 ; CHECK-NEXT:    [[ABC_POSTLOOP:%.*]] = icmp slt i32 [[IDX_POSTLOOP]], [[BOUND]]
 251 ; CHECK-NEXT:    br i1 [[ABC_POSTLOOP]], label [[IN_BOUNDS_POSTLOOP]], label [[OUT_OF_BOUNDS_LOOPEXIT:%.*]], !prof [[PROF0]]
 252 ; CHECK:       in.bounds.postloop:
 253 ; CHECK-NEXT:    [[ADDR_POSTLOOP:%.*]] = getelementptr i32, ptr [[ARR]], i32 [[IDX_POSTLOOP]]
 254 ; CHECK-NEXT:    store i32 0, ptr [[ADDR_POSTLOOP]], align 4
 255 ; CHECK-NEXT:    [[NEXT_POSTLOOP:%.*]] = icmp ult i32 [[IDX_NEXT_POSTLOOP]], [[N]]
 256 ; CHECK-NEXT:    br i1 [[NEXT_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT:%.*]], !llvm.loop [[LOOP7:![0-9]+]], !loop_constrainer.loop.clone [[META6]]
 257 ;
 258
 259   entry:
 260   %first.itr.check = icmp sgt i32 %n, 0
 261   br i1 %first.itr.check, label %loop, label %exit
 262
 263   loop:
 264   %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ]
 265   %idx.next = add i32 %idx, 1
 266   %abc = icmp slt i32 %idx, %bound
 267   br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !0
 268
 269   in.bounds:
 270   %addr = getelementptr i32, ptr %arr, i32 %idx
 271   store i32 0, ptr %addr
 272   %next = icmp ult i32 %idx.next, %n
 273   br i1 %next, label %loop, label %exit
 274
 275   out.of.bounds:
 276   ret void
 277
 278   exit:
 279   ret void
 280 }
 281
 282 ; Same as test_01, unsigned range check.
 283 ; FIXME: We could remove the range check here, but it does not happen due to the
 284 ; limintation we posed to fix the miscompile (see comments in the method
 285 ; computeSafeIterationSpace).
 286 define void @test_05(ptr %arr, i32 %n) {
 287 ; CHECK-LABEL: @test_05(
 288 ; CHECK-NEXT:  entry:
 289 ; CHECK-NEXT:    [[FIRST_ITR_CHECK:%.*]] = icmp sgt i32 [[N:%.*]], 0
 290 ; CHECK-NEXT:    br i1 [[FIRST_ITR_CHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
 291 ; CHECK:       loop.preheader:
 292 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 293 ; CHECK:       loop:
 294 ; CHECK-NEXT:    [[IDX:%.*]] = phi i32 [ [[IDX_NEXT:%.*]], [[IN_BOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
 295 ; CHECK-NEXT:    [[IDX_NEXT]] = add i32 [[IDX]], 1
 296 ; CHECK-NEXT:    [[ABC:%.*]] = icmp ult i32 [[IDX]], -9
 297 ; CHECK-NEXT:    br i1 [[ABC]], label [[IN_BOUNDS]], label [[OUT_OF_BOUNDS:%.*]], !prof [[PROF0]]
 298 ; CHECK:       in.bounds:
 299 ; CHECK-NEXT:    [[ADDR:%.*]] = getelementptr i32, ptr [[ARR:%.*]], i32 [[IDX]]
 300 ; CHECK-NEXT:    store i32 0, ptr [[ADDR]], align 4
 301 ; CHECK-NEXT:    [[NEXT:%.*]] = icmp slt i32 [[IDX_NEXT]], [[N]]
 302 ; CHECK-NEXT:    br i1 [[NEXT]], label [[LOOP]], label [[EXIT_LOOPEXIT:%.*]]
 303 ; CHECK:       out.of.bounds:
 304 ; CHECK-NEXT:    ret void
 305 ; CHECK:       exit.loopexit:
 306 ; CHECK-NEXT:    br label [[EXIT]]
 307 ; CHECK:       exit:
 308 ; CHECK-NEXT:    ret void
 309 ;
 310   entry:
 311   %first.itr.check = icmp sgt i32 %n, 0
 312   br i1 %first.itr.check, label %loop, label %exit
 313
 314   loop:
 315   %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ]
 316   %idx.next = add i32 %idx, 1
 317   %abc = icmp ult i32 %idx, -9
 318   br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !0
 319
 320   in.bounds:
 321   %addr = getelementptr i32, ptr %arr, i32 %idx
 322   store i32 0, ptr %addr
 323   %next = icmp slt i32 %idx.next, %n
 324   br i1 %next, label %loop, label %exit
 325
 326   out.of.bounds:
 327   ret void
 328
 329   exit:
 330   ret void
 331 }
 332
 333 ; Same as test_02, unsigned range check.
 334 ; FIXME: We could remove the range check here, but it does not happen due to the
 335 ; limintation we posed to fix the miscompile (see comments in the method
 336 ; computeSafeIterationSpace).
 337 define void @test_06(ptr %arr, i32 %n) {
 338 ; CHECK-LABEL: @test_06(
 339 ; CHECK-NEXT:  entry:
 340 ; CHECK-NEXT:    [[FIRST_ITR_CHECK:%.*]] = icmp sgt i32 [[N:%.*]], 0
 341 ; CHECK-NEXT:    br i1 [[FIRST_ITR_CHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
 342 ; CHECK:       loop.preheader:
 343 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 344 ; CHECK:       loop:
 345 ; CHECK-NEXT:    [[IDX:%.*]] = phi i32 [ [[IDX_NEXT:%.*]], [[IN_BOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
 346 ; CHECK-NEXT:    [[IDX_NEXT]] = add i32 [[IDX]], 1
 347 ; CHECK-NEXT:    [[ABC:%.*]] = icmp ult i32 [[IDX]], -9
 348 ; CHECK-NEXT:    br i1 [[ABC]], label [[IN_BOUNDS]], label [[OUT_OF_BOUNDS:%.*]], !prof [[PROF0]]
 349 ; CHECK:       in.bounds:
 350 ; CHECK-NEXT:    [[ADDR:%.*]] = getelementptr i32, ptr [[ARR:%.*]], i32 [[IDX]]
 351 ; CHECK-NEXT:    store i32 0, ptr [[ADDR]], align 4
 352 ; CHECK-NEXT:    [[NEXT:%.*]] = icmp ult i32 [[IDX_NEXT]], [[N]]
 353 ; CHECK-NEXT:    br i1 [[NEXT]], label [[LOOP]], label [[EXIT_LOOPEXIT:%.*]]
 354 ; CHECK:       out.of.bounds:
 355 ; CHECK-NEXT:    ret void
 356 ; CHECK:       exit.loopexit:
 357 ; CHECK-NEXT:    br label [[EXIT]]
 358 ; CHECK:       exit:
 359 ; CHECK-NEXT:    ret void
 360 ;
 361   entry:
 362   %first.itr.check = icmp sgt i32 %n, 0
 363   br i1 %first.itr.check, label %loop, label %exit
 364
 365   loop:
 366   %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ]
 367   %idx.next = add i32 %idx, 1
 368   %abc = icmp ult i32 %idx, -9
 369   br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !0
 370
 371   in.bounds:
 372   %addr = getelementptr i32, ptr %arr, i32 %idx
 373   store i32 0, ptr %addr
 374   %next = icmp ult i32 %idx.next, %n
 375   br i1 %next, label %loop, label %exit
 376
 377   out.of.bounds:
 378   ret void
 379
 380   exit:
 381   ret void
 382 }
 383
 384 ; Same as test_03, unsigned range check.
 385 ; FIXME: Currently we remove the check, but we will not execute the main loop if
 386 ; %bound is negative (i.e. in [SINT_MAX + 1, UINT_MAX)). We should be able to
 387 ; safely remove this check (see comments in the method
 388 ; computeSafeIterationSpace).
 389 define void @test_07(ptr %arr, i32 %n, i32 %bound) {
 390 ; CHECK-LABEL: @test_07(
 391 ; CHECK-NEXT:  entry:
 392 ; CHECK-NEXT:    [[FIRST_ITR_CHECK:%.*]] = icmp sgt i32 [[N:%.*]], 0
 393 ; CHECK-NEXT:    br i1 [[FIRST_ITR_CHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
 394 ; CHECK:       loop.preheader:
 395 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[BOUND:%.*]], -2147483647
 396 ; CHECK-NEXT:    [[SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[TMP0]], i32 0)
 397 ; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 [[BOUND]], [[SMAX]]
 398 ; CHECK-NEXT:    [[SMIN:%.*]] = call i32 @llvm.smin.i32(i32 [[BOUND]], i32 0)
 399 ; CHECK-NEXT:    [[SMAX1:%.*]] = call i32 @llvm.smax.i32(i32 [[SMIN]], i32 -1)
 400 ; CHECK-NEXT:    [[TMP2:%.*]] = add nsw i32 [[SMAX1]], 1
 401 ; CHECK-NEXT:    [[TMP3:%.*]] = mul i32 [[TMP1]], [[TMP2]]
 402 ; CHECK-NEXT:    [[SMIN2:%.*]] = call i32 @llvm.smin.i32(i32 [[N]], i32 [[TMP3]])
 403 ; CHECK-NEXT:    [[EXIT_MAINLOOP_AT:%.*]] = call i32 @llvm.smax.i32(i32 [[SMIN2]], i32 0)
 404 ; CHECK-NEXT:    [[TMP4:%.*]] = icmp slt i32 0, [[EXIT_MAINLOOP_AT]]
 405 ; CHECK-NEXT:    br i1 [[TMP4]], label [[LOOP_PREHEADER4:%.*]], label [[MAIN_PSEUDO_EXIT:%.*]]
 406 ; CHECK:       loop.preheader4:
 407 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 408 ; CHECK:       loop:
 409 ; CHECK-NEXT:    [[IDX:%.*]] = phi i32 [ [[IDX_NEXT:%.*]], [[IN_BOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER4]] ]
 410 ; CHECK-NEXT:    [[IDX_NEXT]] = add nsw i32 [[IDX]], 1
 411 ; CHECK-NEXT:    [[ABC:%.*]] = icmp ult i32 [[IDX]], [[BOUND]]
 412 ; CHECK-NEXT:    br i1 true, label [[IN_BOUNDS]], label [[OUT_OF_BOUNDS_LOOPEXIT5:%.*]], !prof [[PROF0]]
 413 ; CHECK:       in.bounds:
 414 ; CHECK-NEXT:    [[ADDR:%.*]] = getelementptr i32, ptr [[ARR:%.*]], i32 [[IDX]]
 415 ; CHECK-NEXT:    store i32 0, ptr [[ADDR]], align 4
 416 ; CHECK-NEXT:    [[NEXT:%.*]] = icmp slt i32 [[IDX_NEXT]], [[N]]
 417 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp slt i32 [[IDX_NEXT]], [[EXIT_MAINLOOP_AT]]
 418 ; CHECK-NEXT:    br i1 [[TMP5]], label [[LOOP]], label [[MAIN_EXIT_SELECTOR:%.*]]
 419 ; CHECK:       main.exit.selector:
 420 ; CHECK-NEXT:    [[IDX_NEXT_LCSSA:%.*]] = phi i32 [ [[IDX_NEXT]], [[IN_BOUNDS]] ]
 421 ; CHECK-NEXT:    [[TMP6:%.*]] = icmp slt i32 [[IDX_NEXT_LCSSA]], [[N]]
 422 ; CHECK-NEXT:    br i1 [[TMP6]], label [[MAIN_PSEUDO_EXIT]], label [[EXIT_LOOPEXIT:%.*]]
 423 ; CHECK:       main.pseudo.exit:
 424 ; CHECK-NEXT:    [[IDX_COPY:%.*]] = phi i32 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]
 425 ; CHECK-NEXT:    [[INDVAR_END:%.*]] = phi i32 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]
 426 ; CHECK-NEXT:    br label [[POSTLOOP:%.*]]
 427 ; CHECK:       out.of.bounds.loopexit:
 428 ; CHECK-NEXT:    br label [[OUT_OF_BOUNDS:%.*]]
 429 ; CHECK:       out.of.bounds.loopexit5:
 430 ; CHECK-NEXT:    br label [[OUT_OF_BOUNDS]]
 431 ; CHECK:       out.of.bounds:
 432 ; CHECK-NEXT:    ret void
 433 ; CHECK:       exit.loopexit.loopexit:
 434 ; CHECK-NEXT:    br label [[EXIT_LOOPEXIT]]
 435 ; CHECK:       exit.loopexit:
 436 ; CHECK-NEXT:    br label [[EXIT]]
 437 ; CHECK:       exit:
 438 ; CHECK-NEXT:    ret void
 439 ; CHECK:       postloop:
 440 ; CHECK-NEXT:    br label [[LOOP_POSTLOOP:%.*]]
 441 ; CHECK:       loop.postloop:
 442 ; CHECK-NEXT:    [[IDX_POSTLOOP:%.*]] = phi i32 [ [[IDX_NEXT_POSTLOOP:%.*]], [[IN_BOUNDS_POSTLOOP:%.*]] ], [ [[IDX_COPY]], [[POSTLOOP]] ]
 443 ; CHECK-NEXT:    [[IDX_NEXT_POSTLOOP]] = add i32 [[IDX_POSTLOOP]], 1
 444 ; CHECK-NEXT:    [[ABC_POSTLOOP:%.*]] = icmp ult i32 [[IDX_POSTLOOP]], [[BOUND]]
 445 ; CHECK-NEXT:    br i1 [[ABC_POSTLOOP]], label [[IN_BOUNDS_POSTLOOP]], label [[OUT_OF_BOUNDS_LOOPEXIT:%.*]], !prof [[PROF0]]
 446 ; CHECK:       in.bounds.postloop:
 447 ; CHECK-NEXT:    [[ADDR_POSTLOOP:%.*]] = getelementptr i32, ptr [[ARR]], i32 [[IDX_POSTLOOP]]
 448 ; CHECK-NEXT:    store i32 0, ptr [[ADDR_POSTLOOP]], align 4
 449 ; CHECK-NEXT:    [[NEXT_POSTLOOP:%.*]] = icmp slt i32 [[IDX_NEXT_POSTLOOP]], [[N]]
 450 ; CHECK-NEXT:    br i1 [[NEXT_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT:%.*]], !llvm.loop [[LOOP8:![0-9]+]], !loop_constrainer.loop.clone [[META6]]
 451 ;
 452   entry:
 453   %first.itr.check = icmp sgt i32 %n, 0
 454   br i1 %first.itr.check, label %loop, label %exit
 455
 456   loop:
 457   %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ]
 458   %idx.next = add i32 %idx, 1
 459   %abc = icmp ult i32 %idx, %bound
 460   br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !0
 461
 462   in.bounds:
 463   %addr = getelementptr i32, ptr %arr, i32 %idx
 464   store i32 0, ptr %addr
 465   %next = icmp slt i32 %idx.next, %n
 466   br i1 %next, label %loop, label %exit
 467
 468   out.of.bounds:
 469   ret void
 470
 471   exit:
 472   ret void
 473 }
 474
 475 ; Same as test_04, unsigned range check.
 476 ; FIXME: Currently we remove the check, but we will not execute the main loop if
 477 ; %bound is negative (i.e. in [SINT_MAX + 1, UINT_MAX)). We should be able to
 478 ; safely remove this check (see comments in the method
 479 ; computeSafeIterationSpace).
 480 define void @test_08(ptr %arr, i32 %n, i32 %bound) {
 481 ; CHECK-LABEL: @test_08(
 482 ; CHECK-NEXT:  entry:
 483 ; CHECK-NEXT:    [[FIRST_ITR_CHECK:%.*]] = icmp sgt i32 [[N:%.*]], 0
 484 ; CHECK-NEXT:    br i1 [[FIRST_ITR_CHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
 485 ; CHECK:       loop.preheader:
 486 ; CHECK-NEXT:    [[SMIN:%.*]] = call i32 @llvm.smin.i32(i32 [[BOUND:%.*]], i32 0)
 487 ; CHECK-NEXT:    [[TMP0:%.*]] = sub i32 [[BOUND]], [[SMIN]]
 488 ; CHECK-NEXT:    [[SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[SMIN]], i32 -1)
 489 ; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i32 [[SMAX]], 1
 490 ; CHECK-NEXT:    [[TMP2:%.*]] = mul i32 [[TMP0]], [[TMP1]]
 491 ; CHECK-NEXT:    [[EXIT_MAINLOOP_AT:%.*]] = call i32 @llvm.umin.i32(i32 [[N]], i32 [[TMP2]])
 492 ; CHECK-NEXT:    [[TMP3:%.*]] = icmp ult i32 0, [[EXIT_MAINLOOP_AT]]
 493 ; CHECK-NEXT:    br i1 [[TMP3]], label [[LOOP_PREHEADER1:%.*]], label [[MAIN_PSEUDO_EXIT:%.*]]
 494 ; CHECK:       loop.preheader1:
 495 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 496 ; CHECK:       loop:
 497 ; CHECK-NEXT:    [[IDX:%.*]] = phi i32 [ [[IDX_NEXT:%.*]], [[IN_BOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER1]] ]
 498 ; CHECK-NEXT:    [[IDX_NEXT]] = add i32 [[IDX]], 1
 499 ; CHECK-NEXT:    [[ABC:%.*]] = icmp ult i32 [[IDX]], [[BOUND]]
 500 ; CHECK-NEXT:    br i1 true, label [[IN_BOUNDS]], label [[OUT_OF_BOUNDS_LOOPEXIT2:%.*]], !prof [[PROF0]]
 501 ; CHECK:       in.bounds:
 502 ; CHECK-NEXT:    [[ADDR:%.*]] = getelementptr i32, ptr [[ARR:%.*]], i32 [[IDX]]
 503 ; CHECK-NEXT:    store i32 0, ptr [[ADDR]], align 4
 504 ; CHECK-NEXT:    [[NEXT:%.*]] = icmp ult i32 [[IDX_NEXT]], [[N]]
 505 ; CHECK-NEXT:    [[TMP4:%.*]] = icmp ult i32 [[IDX_NEXT]], [[EXIT_MAINLOOP_AT]]
 506 ; CHECK-NEXT:    br i1 [[TMP4]], label [[LOOP]], label [[MAIN_EXIT_SELECTOR:%.*]]
 507 ; CHECK:       main.exit.selector:
 508 ; CHECK-NEXT:    [[IDX_NEXT_LCSSA:%.*]] = phi i32 [ [[IDX_NEXT]], [[IN_BOUNDS]] ]
 509 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp ult i32 [[IDX_NEXT_LCSSA]], [[N]]
 510 ; CHECK-NEXT:    br i1 [[TMP5]], label [[MAIN_PSEUDO_EXIT]], label [[EXIT_LOOPEXIT:%.*]]
 511 ; CHECK:       main.pseudo.exit:
 512 ; CHECK-NEXT:    [[IDX_COPY:%.*]] = phi i32 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]
 513 ; CHECK-NEXT:    [[INDVAR_END:%.*]] = phi i32 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]
 514 ; CHECK-NEXT:    br label [[POSTLOOP:%.*]]
 515 ; CHECK:       out.of.bounds.loopexit:
 516 ; CHECK-NEXT:    br label [[OUT_OF_BOUNDS:%.*]]
 517 ; CHECK:       out.of.bounds.loopexit2:
 518 ; CHECK-NEXT:    br label [[OUT_OF_BOUNDS]]
 519 ; CHECK:       out.of.bounds:
 520 ; CHECK-NEXT:    ret void
 521 ; CHECK:       exit.loopexit.loopexit:
 522 ; CHECK-NEXT:    br label [[EXIT_LOOPEXIT]]
 523 ; CHECK:       exit.loopexit:
 524 ; CHECK-NEXT:    br label [[EXIT]]
 525 ; CHECK:       exit:
 526 ; CHECK-NEXT:    ret void
 527 ; CHECK:       postloop:
 528 ; CHECK-NEXT:    br label [[LOOP_POSTLOOP:%.*]]
 529 ; CHECK:       loop.postloop:
 530 ; CHECK-NEXT:    [[IDX_POSTLOOP:%.*]] = phi i32 [ [[IDX_NEXT_POSTLOOP:%.*]], [[IN_BOUNDS_POSTLOOP:%.*]] ], [ [[IDX_COPY]], [[POSTLOOP]] ]
 531 ; CHECK-NEXT:    [[IDX_NEXT_POSTLOOP]] = add i32 [[IDX_POSTLOOP]], 1
 532 ; CHECK-NEXT:    [[ABC_POSTLOOP:%.*]] = icmp ult i32 [[IDX_POSTLOOP]], [[BOUND]]
 533 ; CHECK-NEXT:    br i1 [[ABC_POSTLOOP]], label [[IN_BOUNDS_POSTLOOP]], label [[OUT_OF_BOUNDS_LOOPEXIT:%.*]], !prof [[PROF0]]
 534 ; CHECK:       in.bounds.postloop:
 535 ; CHECK-NEXT:    [[ADDR_POSTLOOP:%.*]] = getelementptr i32, ptr [[ARR]], i32 [[IDX_POSTLOOP]]
 536 ; CHECK-NEXT:    store i32 0, ptr [[ADDR_POSTLOOP]], align 4
 537 ; CHECK-NEXT:    [[NEXT_POSTLOOP:%.*]] = icmp ult i32 [[IDX_NEXT_POSTLOOP]], [[N]]
 538 ; CHECK-NEXT:    br i1 [[NEXT_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT:%.*]], !llvm.loop [[LOOP9:![0-9]+]], !loop_constrainer.loop.clone [[META6]]
 539 ;
 540   entry:
 541   %first.itr.check = icmp sgt i32 %n, 0
 542   br i1 %first.itr.check, label %loop, label %exit
 543
 544   loop:
 545   %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ]
 546   %idx.next = add i32 %idx, 1
 547   %abc = icmp ult i32 %idx, %bound
 548   br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !0
 549
 550   in.bounds:
 551   %addr = getelementptr i32, ptr %arr, i32 %idx
 552   store i32 0, ptr %addr
 553   %next = icmp ult i32 %idx.next, %n
 554   br i1 %next, label %loop, label %exit
 555
 556   out.of.bounds:
 557   ret void
 558
 559   exit:
 560   ret void
 561 }
 562 !0 = !{!"branch_weights", i32 64, i32 4}