1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py 2 ; RUN: opt -verify-loop-info -irce-print-changed-loops -irce -S < %s 2>&1 | FileCheck %s 3 ; RUN: opt -verify-loop-info -irce-print-changed-loops -passes='require<branch-prob>,loop(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(i32 *%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 !0 22 ; CHECK: in.bounds: 23 ; CHECK-NEXT: [[ADDR:%.*]] = getelementptr i32, i32* [[ARR:%.*]], i32 [[IDX]] 24 ; CHECK-NEXT: store i32 0, i32* [[ADDR]] 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, i32* %arr, i32 %idx 47 store i32 0, i32* %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(i32 *%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 !0 71 ; CHECK: in.bounds: 72 ; CHECK-NEXT: [[ADDR:%.*]] = getelementptr i32, i32* [[ARR:%.*]], i32 [[IDX]] 73 ; CHECK-NEXT: store i32 0, i32* [[ADDR]] 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, i32* %arr, i32 %idx 96 store i32 0, i32* %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(i32 *%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: [[TMP1:%.*]] = icmp sgt i32 [[TMP0]], 0 117 ; CHECK-NEXT: [[SMAX:%.*]] = select i1 [[TMP1]], i32 [[TMP0]], i32 0 118 ; CHECK-NEXT: [[TMP2:%.*]] = sub i32 [[BOUND]], [[SMAX]] 119 ; CHECK-NEXT: [[TMP3:%.*]] = sub i32 -1, [[BOUND]] 120 ; CHECK-NEXT: [[TMP4:%.*]] = icmp sgt i32 [[TMP3]], -1 121 ; CHECK-NEXT: [[SMAX1:%.*]] = select i1 [[TMP4]], i32 [[TMP3]], i32 -1 122 ; CHECK-NEXT: [[TMP5:%.*]] = sub i32 -1, [[SMAX1]] 123 ; CHECK-NEXT: [[TMP6:%.*]] = icmp sgt i32 [[TMP5]], -1 124 ; CHECK-NEXT: [[SMAX2:%.*]] = select i1 [[TMP6]], i32 [[TMP5]], i32 -1 125 ; CHECK-NEXT: [[TMP7:%.*]] = add i32 [[SMAX2]], 1 126 ; CHECK-NEXT: [[TMP8:%.*]] = mul i32 [[TMP2]], [[TMP7]] 127 ; CHECK-NEXT: [[TMP9:%.*]] = sub i32 -1, [[TMP8]] 128 ; CHECK-NEXT: [[TMP10:%.*]] = sub i32 -1, [[N]] 129 ; CHECK-NEXT: [[TMP11:%.*]] = icmp sgt i32 [[TMP9]], [[TMP10]] 130 ; CHECK-NEXT: [[SMAX3:%.*]] = select i1 [[TMP11]], i32 [[TMP9]], i32 [[TMP10]] 131 ; CHECK-NEXT: [[TMP12:%.*]] = sub i32 -1, [[SMAX3]] 132 ; CHECK-NEXT: [[TMP13:%.*]] = icmp sgt i32 [[TMP12]], 0 133 ; CHECK-NEXT: [[EXIT_MAINLOOP_AT:%.*]] = select i1 [[TMP13]], i32 [[TMP12]], i32 0 134 ; CHECK-NEXT: [[TMP14:%.*]] = icmp slt i32 0, [[EXIT_MAINLOOP_AT]] 135 ; CHECK-NEXT: br i1 [[TMP14]], label [[LOOP_PREHEADER5:%.*]], label [[MAIN_PSEUDO_EXIT:%.*]] 136 ; CHECK: loop.preheader5: 137 ; CHECK-NEXT: br label [[LOOP:%.*]] 138 ; CHECK: loop: 139 ; CHECK-NEXT: [[IDX:%.*]] = phi i32 [ [[IDX_NEXT:%.*]], [[IN_BOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER5]] ] 140 ; CHECK-NEXT: [[IDX_NEXT]] = add i32 [[IDX]], 1 141 ; CHECK-NEXT: [[ABC:%.*]] = icmp slt i32 [[IDX]], [[BOUND]] 142 ; CHECK-NEXT: br i1 true, label [[IN_BOUNDS]], label [[OUT_OF_BOUNDS_LOOPEXIT6:%.*]], !prof !0 143 ; CHECK: in.bounds: 144 ; CHECK-NEXT: [[ADDR:%.*]] = getelementptr i32, i32* [[ARR:%.*]], i32 [[IDX]] 145 ; CHECK-NEXT: store i32 0, i32* [[ADDR]] 146 ; CHECK-NEXT: [[NEXT:%.*]] = icmp slt i32 [[IDX_NEXT]], [[N]] 147 ; CHECK-NEXT: [[TMP15:%.*]] = icmp slt i32 [[IDX_NEXT]], [[EXIT_MAINLOOP_AT]] 148 ; CHECK-NEXT: br i1 [[TMP15]], label [[LOOP]], label [[MAIN_EXIT_SELECTOR:%.*]] 149 ; CHECK: main.exit.selector: 150 ; CHECK-NEXT: [[IDX_NEXT_LCSSA:%.*]] = phi i32 [ [[IDX_NEXT]], [[IN_BOUNDS]] ] 151 ; CHECK-NEXT: [[TMP16:%.*]] = icmp slt i32 [[IDX_NEXT_LCSSA]], [[N]] 152 ; CHECK-NEXT: br i1 [[TMP16]], label [[MAIN_PSEUDO_EXIT]], label [[EXIT_LOOPEXIT:%.*]] 153 ; CHECK: main.pseudo.exit: 154 ; CHECK-NEXT: [[IDX_COPY:%.*]] = phi i32 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ] 155 ; CHECK-NEXT: [[INDVAR_END:%.*]] = phi i32 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ] 156 ; CHECK-NEXT: br label [[POSTLOOP:%.*]] 157 ; CHECK: out.of.bounds.loopexit: 158 ; CHECK-NEXT: br label [[OUT_OF_BOUNDS:%.*]] 159 ; CHECK: out.of.bounds.loopexit6: 160 ; CHECK-NEXT: br label [[OUT_OF_BOUNDS]] 161 ; CHECK: out.of.bounds: 162 ; CHECK-NEXT: ret void 163 ; CHECK: exit.loopexit.loopexit: 164 ; CHECK-NEXT: br label [[EXIT_LOOPEXIT]] 165 ; CHECK: exit.loopexit: 166 ; CHECK-NEXT: br label [[EXIT]] 167 ; CHECK: exit: 168 ; CHECK-NEXT: ret void 169 ; CHECK: postloop: 170 ; CHECK-NEXT: br label [[LOOP_POSTLOOP:%.*]] 171 ; CHECK: loop.postloop: 172 ; CHECK-NEXT: [[IDX_POSTLOOP:%.*]] = phi i32 [ [[IDX_NEXT_POSTLOOP:%.*]], [[IN_BOUNDS_POSTLOOP:%.*]] ], [ [[IDX_COPY]], [[POSTLOOP]] ] 173 ; CHECK-NEXT: [[IDX_NEXT_POSTLOOP]] = add i32 [[IDX_POSTLOOP]], 1 174 ; CHECK-NEXT: [[ABC_POSTLOOP:%.*]] = icmp slt i32 [[IDX_POSTLOOP]], [[BOUND]] 175 ; CHECK-NEXT: br i1 [[ABC_POSTLOOP]], label [[IN_BOUNDS_POSTLOOP]], label [[OUT_OF_BOUNDS_LOOPEXIT:%.*]], !prof !0 176 ; CHECK: in.bounds.postloop: 177 ; CHECK-NEXT: [[ADDR_POSTLOOP:%.*]] = getelementptr i32, i32* [[ARR]], i32 [[IDX_POSTLOOP]] 178 ; CHECK-NEXT: store i32 0, i32* [[ADDR_POSTLOOP]] 179 ; CHECK-NEXT: [[NEXT_POSTLOOP:%.*]] = icmp slt i32 [[IDX_NEXT_POSTLOOP]], [[N]] 180 ; CHECK-NEXT: br i1 [[NEXT_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT:%.*]], !llvm.loop !1, !irce.loop.clone !6 181 ; 182 183 entry: 184 %first.itr.check = icmp sgt i32 %n, 0 185 br i1 %first.itr.check, label %loop, label %exit 186 187 loop: 188 %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ] 189 %idx.next = add i32 %idx, 1 190 %abc = icmp slt i32 %idx, %bound 191 br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !0 192 193 in.bounds: 194 %addr = getelementptr i32, i32* %arr, i32 %idx 195 store i32 0, i32* %addr 196 %next = icmp slt i32 %idx.next, %n 197 br i1 %next, label %loop, label %exit 198 199 out.of.bounds: 200 ret void 201 202 exit: 203 ret void 204 } 205 206 ; RC against a value which is not known to be non-negative. Here we should 207 ; expand runtime checks against bound being positive or negative. 208 define void @test_04(i32 *%arr, i32 %n, i32 %bound) { 209 ; CHECK-LABEL: @test_04( 210 ; CHECK-NEXT: entry: 211 ; CHECK-NEXT: [[FIRST_ITR_CHECK:%.*]] = icmp sgt i32 [[N:%.*]], 0 212 ; CHECK-NEXT: br i1 [[FIRST_ITR_CHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]] 213 ; CHECK: loop.preheader: 214 ; CHECK-NEXT: [[TMP0:%.*]] = sub i32 -1, [[BOUND:%.*]] 215 ; CHECK-NEXT: [[TMP1:%.*]] = icmp sgt i32 [[TMP0]], -1 216 ; CHECK-NEXT: [[SMAX:%.*]] = select i1 [[TMP1]], i32 [[TMP0]], i32 -1 217 ; CHECK-NEXT: [[TMP2:%.*]] = add i32 [[BOUND]], [[SMAX]] 218 ; CHECK-NEXT: [[TMP3:%.*]] = add i32 [[TMP2]], 1 219 ; CHECK-NEXT: [[TMP4:%.*]] = sub i32 -1, [[SMAX]] 220 ; CHECK-NEXT: [[TMP5:%.*]] = icmp sgt i32 [[TMP4]], -1 221 ; CHECK-NEXT: [[SMAX1:%.*]] = select i1 [[TMP5]], i32 [[TMP4]], i32 -1 222 ; CHECK-NEXT: [[TMP6:%.*]] = add i32 [[SMAX1]], 1 223 ; CHECK-NEXT: [[TMP7:%.*]] = mul i32 [[TMP3]], [[TMP6]] 224 ; CHECK-NEXT: [[TMP8:%.*]] = sub i32 -1, [[TMP7]] 225 ; CHECK-NEXT: [[TMP9:%.*]] = sub i32 -1, [[N]] 226 ; CHECK-NEXT: [[TMP10:%.*]] = icmp ugt i32 [[TMP8]], [[TMP9]] 227 ; CHECK-NEXT: [[UMAX:%.*]] = select i1 [[TMP10]], i32 [[TMP8]], i32 [[TMP9]] 228 ; CHECK-NEXT: [[EXIT_MAINLOOP_AT:%.*]] = sub i32 -1, [[UMAX]] 229 ; CHECK-NEXT: [[TMP11:%.*]] = icmp ult i32 0, [[EXIT_MAINLOOP_AT]] 230 ; CHECK-NEXT: br i1 [[TMP11]], label [[LOOP_PREHEADER2:%.*]], label [[MAIN_PSEUDO_EXIT:%.*]] 231 ; CHECK: loop.preheader2: 232 ; CHECK-NEXT: br label [[LOOP:%.*]] 233 ; CHECK: loop: 234 ; CHECK-NEXT: [[IDX:%.*]] = phi i32 [ [[IDX_NEXT:%.*]], [[IN_BOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER2]] ] 235 ; CHECK-NEXT: [[IDX_NEXT]] = add i32 [[IDX]], 1 236 ; CHECK-NEXT: [[ABC:%.*]] = icmp slt i32 [[IDX]], [[BOUND]] 237 ; CHECK-NEXT: br i1 true, label [[IN_BOUNDS]], label [[OUT_OF_BOUNDS_LOOPEXIT3:%.*]], !prof !0 238 ; CHECK: in.bounds: 239 ; CHECK-NEXT: [[ADDR:%.*]] = getelementptr i32, i32* [[ARR:%.*]], i32 [[IDX]] 240 ; CHECK-NEXT: store i32 0, i32* [[ADDR]] 241 ; CHECK-NEXT: [[NEXT:%.*]] = icmp ult i32 [[IDX_NEXT]], [[N]] 242 ; CHECK-NEXT: [[TMP12:%.*]] = icmp ult i32 [[IDX_NEXT]], [[EXIT_MAINLOOP_AT]] 243 ; CHECK-NEXT: br i1 [[TMP12]], label [[LOOP]], label [[MAIN_EXIT_SELECTOR:%.*]] 244 ; CHECK: main.exit.selector: 245 ; CHECK-NEXT: [[IDX_NEXT_LCSSA:%.*]] = phi i32 [ [[IDX_NEXT]], [[IN_BOUNDS]] ] 246 ; CHECK-NEXT: [[TMP13:%.*]] = icmp ult i32 [[IDX_NEXT_LCSSA]], [[N]] 247 ; CHECK-NEXT: br i1 [[TMP13]], label [[MAIN_PSEUDO_EXIT]], label [[EXIT_LOOPEXIT:%.*]] 248 ; CHECK: main.pseudo.exit: 249 ; CHECK-NEXT: [[IDX_COPY:%.*]] = phi i32 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ] 250 ; CHECK-NEXT: [[INDVAR_END:%.*]] = phi i32 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ] 251 ; CHECK-NEXT: br label [[POSTLOOP:%.*]] 252 ; CHECK: out.of.bounds.loopexit: 253 ; CHECK-NEXT: br label [[OUT_OF_BOUNDS:%.*]] 254 ; CHECK: out.of.bounds.loopexit3: 255 ; CHECK-NEXT: br label [[OUT_OF_BOUNDS]] 256 ; CHECK: out.of.bounds: 257 ; CHECK-NEXT: ret void 258 ; CHECK: exit.loopexit.loopexit: 259 ; CHECK-NEXT: br label [[EXIT_LOOPEXIT]] 260 ; CHECK: exit.loopexit: 261 ; CHECK-NEXT: br label [[EXIT]] 262 ; CHECK: exit: 263 ; CHECK-NEXT: ret void 264 ; CHECK: postloop: 265 ; CHECK-NEXT: br label [[LOOP_POSTLOOP:%.*]] 266 ; CHECK: loop.postloop: 267 ; CHECK-NEXT: [[IDX_POSTLOOP:%.*]] = phi i32 [ [[IDX_NEXT_POSTLOOP:%.*]], [[IN_BOUNDS_POSTLOOP:%.*]] ], [ [[IDX_COPY]], [[POSTLOOP]] ] 268 ; CHECK-NEXT: [[IDX_NEXT_POSTLOOP]] = add i32 [[IDX_POSTLOOP]], 1 269 ; CHECK-NEXT: [[ABC_POSTLOOP:%.*]] = icmp slt i32 [[IDX_POSTLOOP]], [[BOUND]] 270 ; CHECK-NEXT: br i1 [[ABC_POSTLOOP]], label [[IN_BOUNDS_POSTLOOP]], label [[OUT_OF_BOUNDS_LOOPEXIT:%.*]], !prof !0 271 ; CHECK: in.bounds.postloop: 272 ; CHECK-NEXT: [[ADDR_POSTLOOP:%.*]] = getelementptr i32, i32* [[ARR]], i32 [[IDX_POSTLOOP]] 273 ; CHECK-NEXT: store i32 0, i32* [[ADDR_POSTLOOP]] 274 ; CHECK-NEXT: [[NEXT_POSTLOOP:%.*]] = icmp ult i32 [[IDX_NEXT_POSTLOOP]], [[N]] 275 ; CHECK-NEXT: br i1 [[NEXT_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT:%.*]], !llvm.loop !7, !irce.loop.clone !6 276 ; 277 278 entry: 279 %first.itr.check = icmp sgt i32 %n, 0 280 br i1 %first.itr.check, label %loop, label %exit 281 282 loop: 283 %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ] 284 %idx.next = add i32 %idx, 1 285 %abc = icmp slt i32 %idx, %bound 286 br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !0 287 288 in.bounds: 289 %addr = getelementptr i32, i32* %arr, i32 %idx 290 store i32 0, i32* %addr 291 %next = icmp ult i32 %idx.next, %n 292 br i1 %next, label %loop, label %exit 293 294 out.of.bounds: 295 ret void 296 297 exit: 298 ret void 299 } 300 301 ; Same as test_01, unsigned range check. 302 ; FIXME: We could remove the range check here, but it does not happen due to the 303 ; limintation we posed to fix the miscompile (see comments in the method 304 ; computeSafeIterationSpace). 305 define void @test_05(i32 *%arr, i32 %n) { 306 ; CHECK-LABEL: @test_05( 307 ; CHECK-NEXT: entry: 308 ; CHECK-NEXT: [[FIRST_ITR_CHECK:%.*]] = icmp sgt i32 [[N:%.*]], 0 309 ; CHECK-NEXT: br i1 [[FIRST_ITR_CHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]] 310 ; CHECK: loop.preheader: 311 ; CHECK-NEXT: br label [[LOOP:%.*]] 312 ; CHECK: loop: 313 ; CHECK-NEXT: [[IDX:%.*]] = phi i32 [ [[IDX_NEXT:%.*]], [[IN_BOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER]] ] 314 ; CHECK-NEXT: [[IDX_NEXT]] = add i32 [[IDX]], 1 315 ; CHECK-NEXT: [[ABC:%.*]] = icmp ult i32 [[IDX]], -9 316 ; CHECK-NEXT: br i1 [[ABC]], label [[IN_BOUNDS]], label [[OUT_OF_BOUNDS:%.*]], !prof !0 317 ; CHECK: in.bounds: 318 ; CHECK-NEXT: [[ADDR:%.*]] = getelementptr i32, i32* [[ARR:%.*]], i32 [[IDX]] 319 ; CHECK-NEXT: store i32 0, i32* [[ADDR]] 320 ; CHECK-NEXT: [[NEXT:%.*]] = icmp slt i32 [[IDX_NEXT]], [[N]] 321 ; CHECK-NEXT: br i1 [[NEXT]], label [[LOOP]], label [[EXIT_LOOPEXIT:%.*]] 322 ; CHECK: out.of.bounds: 323 ; CHECK-NEXT: ret void 324 ; CHECK: exit.loopexit: 325 ; CHECK-NEXT: br label [[EXIT]] 326 ; CHECK: exit: 327 ; CHECK-NEXT: ret void 328 ; 329 entry: 330 %first.itr.check = icmp sgt i32 %n, 0 331 br i1 %first.itr.check, label %loop, label %exit 332 333 loop: 334 %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ] 335 %idx.next = add i32 %idx, 1 336 %abc = icmp ult i32 %idx, -9 337 br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !0 338 339 in.bounds: 340 %addr = getelementptr i32, i32* %arr, i32 %idx 341 store i32 0, i32* %addr 342 %next = icmp slt i32 %idx.next, %n 343 br i1 %next, label %loop, label %exit 344 345 out.of.bounds: 346 ret void 347 348 exit: 349 ret void 350 } 351 352 ; Same as test_02, unsigned range check. 353 ; FIXME: We could remove the range check here, but it does not happen due to the 354 ; limintation we posed to fix the miscompile (see comments in the method 355 ; computeSafeIterationSpace). 356 define void @test_06(i32 *%arr, i32 %n) { 357 ; CHECK-LABEL: @test_06( 358 ; CHECK-NEXT: entry: 359 ; CHECK-NEXT: [[FIRST_ITR_CHECK:%.*]] = icmp sgt i32 [[N:%.*]], 0 360 ; CHECK-NEXT: br i1 [[FIRST_ITR_CHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]] 361 ; CHECK: loop.preheader: 362 ; CHECK-NEXT: br label [[LOOP:%.*]] 363 ; CHECK: loop: 364 ; CHECK-NEXT: [[IDX:%.*]] = phi i32 [ [[IDX_NEXT:%.*]], [[IN_BOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER]] ] 365 ; CHECK-NEXT: [[IDX_NEXT]] = add i32 [[IDX]], 1 366 ; CHECK-NEXT: [[ABC:%.*]] = icmp ult i32 [[IDX]], -9 367 ; CHECK-NEXT: br i1 [[ABC]], label [[IN_BOUNDS]], label [[OUT_OF_BOUNDS:%.*]], !prof !0 368 ; CHECK: in.bounds: 369 ; CHECK-NEXT: [[ADDR:%.*]] = getelementptr i32, i32* [[ARR:%.*]], i32 [[IDX]] 370 ; CHECK-NEXT: store i32 0, i32* [[ADDR]] 371 ; CHECK-NEXT: [[NEXT:%.*]] = icmp ult i32 [[IDX_NEXT]], [[N]] 372 ; CHECK-NEXT: br i1 [[NEXT]], label [[LOOP]], label [[EXIT_LOOPEXIT:%.*]] 373 ; CHECK: out.of.bounds: 374 ; CHECK-NEXT: ret void 375 ; CHECK: exit.loopexit: 376 ; CHECK-NEXT: br label [[EXIT]] 377 ; CHECK: exit: 378 ; CHECK-NEXT: ret void 379 ; 380 entry: 381 %first.itr.check = icmp sgt i32 %n, 0 382 br i1 %first.itr.check, label %loop, label %exit 383 384 loop: 385 %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ] 386 %idx.next = add i32 %idx, 1 387 %abc = icmp ult i32 %idx, -9 388 br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !0 389 390 in.bounds: 391 %addr = getelementptr i32, i32* %arr, i32 %idx 392 store i32 0, i32* %addr 393 %next = icmp ult i32 %idx.next, %n 394 br i1 %next, label %loop, label %exit 395 396 out.of.bounds: 397 ret void 398 399 exit: 400 ret void 401 } 402 403 ; Same as test_03, unsigned range check. 404 ; FIXME: Currently we remove the check, but we will not execute the main loop if 405 ; %bound is negative (i.e. in [SINT_MAX + 1, UINT_MAX)). We should be able to 406 ; safely remove this check (see comments in the method 407 ; computeSafeIterationSpace). 408 define void @test_07(i32 *%arr, i32 %n, i32 %bound) { 409 ; CHECK-LABEL: @test_07( 410 ; CHECK-NEXT: entry: 411 ; CHECK-NEXT: [[FIRST_ITR_CHECK:%.*]] = icmp sgt i32 [[N:%.*]], 0 412 ; CHECK-NEXT: br i1 [[FIRST_ITR_CHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]] 413 ; CHECK: loop.preheader: 414 ; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[BOUND:%.*]], -2147483647 415 ; CHECK-NEXT: [[TMP1:%.*]] = icmp sgt i32 [[TMP0]], 0 416 ; CHECK-NEXT: [[SMAX:%.*]] = select i1 [[TMP1]], i32 [[TMP0]], i32 0 417 ; CHECK-NEXT: [[TMP2:%.*]] = sub i32 [[BOUND]], [[SMAX]] 418 ; CHECK-NEXT: [[TMP3:%.*]] = sub i32 -1, [[BOUND]] 419 ; CHECK-NEXT: [[TMP4:%.*]] = icmp sgt i32 [[TMP3]], -1 420 ; CHECK-NEXT: [[SMAX1:%.*]] = select i1 [[TMP4]], i32 [[TMP3]], i32 -1 421 ; CHECK-NEXT: [[TMP5:%.*]] = sub i32 -1, [[SMAX1]] 422 ; CHECK-NEXT: [[TMP6:%.*]] = icmp sgt i32 [[TMP5]], -1 423 ; CHECK-NEXT: [[SMAX2:%.*]] = select i1 [[TMP6]], i32 [[TMP5]], i32 -1 424 ; CHECK-NEXT: [[TMP7:%.*]] = add i32 [[SMAX2]], 1 425 ; CHECK-NEXT: [[TMP8:%.*]] = mul i32 [[TMP2]], [[TMP7]] 426 ; CHECK-NEXT: [[TMP9:%.*]] = sub i32 -1, [[TMP8]] 427 ; CHECK-NEXT: [[TMP10:%.*]] = sub i32 -1, [[N]] 428 ; CHECK-NEXT: [[TMP11:%.*]] = icmp sgt i32 [[TMP9]], [[TMP10]] 429 ; CHECK-NEXT: [[SMAX3:%.*]] = select i1 [[TMP11]], i32 [[TMP9]], i32 [[TMP10]] 430 ; CHECK-NEXT: [[TMP12:%.*]] = sub i32 -1, [[SMAX3]] 431 ; CHECK-NEXT: [[TMP13:%.*]] = icmp sgt i32 [[TMP12]], 0 432 ; CHECK-NEXT: [[EXIT_MAINLOOP_AT:%.*]] = select i1 [[TMP13]], i32 [[TMP12]], i32 0 433 ; CHECK-NEXT: [[TMP14:%.*]] = icmp slt i32 0, [[EXIT_MAINLOOP_AT]] 434 ; CHECK-NEXT: br i1 [[TMP14]], label [[LOOP_PREHEADER5:%.*]], label [[MAIN_PSEUDO_EXIT:%.*]] 435 ; CHECK: loop.preheader5: 436 ; CHECK-NEXT: br label [[LOOP:%.*]] 437 ; CHECK: loop: 438 ; CHECK-NEXT: [[IDX:%.*]] = phi i32 [ [[IDX_NEXT:%.*]], [[IN_BOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER5]] ] 439 ; CHECK-NEXT: [[IDX_NEXT]] = add i32 [[IDX]], 1 440 ; CHECK-NEXT: [[ABC:%.*]] = icmp ult i32 [[IDX]], [[BOUND]] 441 ; CHECK-NEXT: br i1 true, label [[IN_BOUNDS]], label [[OUT_OF_BOUNDS_LOOPEXIT6:%.*]], !prof !0 442 ; CHECK: in.bounds: 443 ; CHECK-NEXT: [[ADDR:%.*]] = getelementptr i32, i32* [[ARR:%.*]], i32 [[IDX]] 444 ; CHECK-NEXT: store i32 0, i32* [[ADDR]] 445 ; CHECK-NEXT: [[NEXT:%.*]] = icmp slt i32 [[IDX_NEXT]], [[N]] 446 ; CHECK-NEXT: [[TMP15:%.*]] = icmp slt i32 [[IDX_NEXT]], [[EXIT_MAINLOOP_AT]] 447 ; CHECK-NEXT: br i1 [[TMP15]], label [[LOOP]], label [[MAIN_EXIT_SELECTOR:%.*]] 448 ; CHECK: main.exit.selector: 449 ; CHECK-NEXT: [[IDX_NEXT_LCSSA:%.*]] = phi i32 [ [[IDX_NEXT]], [[IN_BOUNDS]] ] 450 ; CHECK-NEXT: [[TMP16:%.*]] = icmp slt i32 [[IDX_NEXT_LCSSA]], [[N]] 451 ; CHECK-NEXT: br i1 [[TMP16]], label [[MAIN_PSEUDO_EXIT]], label [[EXIT_LOOPEXIT:%.*]] 452 ; CHECK: main.pseudo.exit: 453 ; CHECK-NEXT: [[IDX_COPY:%.*]] = phi i32 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ] 454 ; CHECK-NEXT: [[INDVAR_END:%.*]] = phi i32 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ] 455 ; CHECK-NEXT: br label [[POSTLOOP:%.*]] 456 ; CHECK: out.of.bounds.loopexit: 457 ; CHECK-NEXT: br label [[OUT_OF_BOUNDS:%.*]] 458 ; CHECK: out.of.bounds.loopexit6: 459 ; CHECK-NEXT: br label [[OUT_OF_BOUNDS]] 460 ; CHECK: out.of.bounds: 461 ; CHECK-NEXT: ret void 462 ; CHECK: exit.loopexit.loopexit: 463 ; CHECK-NEXT: br label [[EXIT_LOOPEXIT]] 464 ; CHECK: exit.loopexit: 465 ; CHECK-NEXT: br label [[EXIT]] 466 ; CHECK: exit: 467 ; CHECK-NEXT: ret void 468 ; CHECK: postloop: 469 ; CHECK-NEXT: br label [[LOOP_POSTLOOP:%.*]] 470 ; CHECK: loop.postloop: 471 ; CHECK-NEXT: [[IDX_POSTLOOP:%.*]] = phi i32 [ [[IDX_NEXT_POSTLOOP:%.*]], [[IN_BOUNDS_POSTLOOP:%.*]] ], [ [[IDX_COPY]], [[POSTLOOP]] ] 472 ; CHECK-NEXT: [[IDX_NEXT_POSTLOOP]] = add i32 [[IDX_POSTLOOP]], 1 473 ; CHECK-NEXT: [[ABC_POSTLOOP:%.*]] = icmp ult i32 [[IDX_POSTLOOP]], [[BOUND]] 474 ; CHECK-NEXT: br i1 [[ABC_POSTLOOP]], label [[IN_BOUNDS_POSTLOOP]], label [[OUT_OF_BOUNDS_LOOPEXIT:%.*]], !prof !0 475 ; CHECK: in.bounds.postloop: 476 ; CHECK-NEXT: [[ADDR_POSTLOOP:%.*]] = getelementptr i32, i32* [[ARR]], i32 [[IDX_POSTLOOP]] 477 ; CHECK-NEXT: store i32 0, i32* [[ADDR_POSTLOOP]] 478 ; CHECK-NEXT: [[NEXT_POSTLOOP:%.*]] = icmp slt i32 [[IDX_NEXT_POSTLOOP]], [[N]] 479 ; CHECK-NEXT: br i1 [[NEXT_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT:%.*]], !llvm.loop !8, !irce.loop.clone !6 480 ; 481 entry: 482 %first.itr.check = icmp sgt i32 %n, 0 483 br i1 %first.itr.check, label %loop, label %exit 484 485 loop: 486 %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ] 487 %idx.next = add i32 %idx, 1 488 %abc = icmp ult i32 %idx, %bound 489 br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !0 490 491 in.bounds: 492 %addr = getelementptr i32, i32* %arr, i32 %idx 493 store i32 0, i32* %addr 494 %next = icmp slt i32 %idx.next, %n 495 br i1 %next, label %loop, label %exit 496 497 out.of.bounds: 498 ret void 499 500 exit: 501 ret void 502 } 503 504 ; Same as test_04, unsigned range check. 505 ; FIXME: Currently we remove the check, but we will not execute the main loop if 506 ; %bound is negative (i.e. in [SINT_MAX + 1, UINT_MAX)). We should be able to 507 ; safely remove this check (see comments in the method 508 ; computeSafeIterationSpace). 509 define void @test_08(i32 *%arr, i32 %n, i32 %bound) { 510 ; CHECK-LABEL: @test_08( 511 ; CHECK-NEXT: entry: 512 ; CHECK-NEXT: [[FIRST_ITR_CHECK:%.*]] = icmp sgt i32 [[N:%.*]], 0 513 ; CHECK-NEXT: br i1 [[FIRST_ITR_CHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]] 514 ; CHECK: loop.preheader: 515 ; CHECK-NEXT: [[TMP0:%.*]] = sub i32 -1, [[BOUND:%.*]] 516 ; CHECK-NEXT: [[TMP1:%.*]] = icmp sgt i32 [[TMP0]], -1 517 ; CHECK-NEXT: [[SMAX:%.*]] = select i1 [[TMP1]], i32 [[TMP0]], i32 -1 518 ; CHECK-NEXT: [[TMP2:%.*]] = add i32 [[BOUND]], [[SMAX]] 519 ; CHECK-NEXT: [[TMP3:%.*]] = add i32 [[TMP2]], 1 520 ; CHECK-NEXT: [[TMP4:%.*]] = sub i32 -1, [[SMAX]] 521 ; CHECK-NEXT: [[TMP5:%.*]] = icmp sgt i32 [[TMP4]], -1 522 ; CHECK-NEXT: [[SMAX1:%.*]] = select i1 [[TMP5]], i32 [[TMP4]], i32 -1 523 ; CHECK-NEXT: [[TMP6:%.*]] = add i32 [[SMAX1]], 1 524 ; CHECK-NEXT: [[TMP7:%.*]] = mul i32 [[TMP3]], [[TMP6]] 525 ; CHECK-NEXT: [[TMP8:%.*]] = sub i32 -1, [[TMP7]] 526 ; CHECK-NEXT: [[TMP9:%.*]] = sub i32 -1, [[N]] 527 ; CHECK-NEXT: [[TMP10:%.*]] = icmp ugt i32 [[TMP8]], [[TMP9]] 528 ; CHECK-NEXT: [[UMAX:%.*]] = select i1 [[TMP10]], i32 [[TMP8]], i32 [[TMP9]] 529 ; CHECK-NEXT: [[EXIT_MAINLOOP_AT:%.*]] = sub i32 -1, [[UMAX]] 530 ; CHECK-NEXT: [[TMP11:%.*]] = icmp ult i32 0, [[EXIT_MAINLOOP_AT]] 531 ; CHECK-NEXT: br i1 [[TMP11]], label [[LOOP_PREHEADER2:%.*]], label [[MAIN_PSEUDO_EXIT:%.*]] 532 ; CHECK: loop.preheader2: 533 ; CHECK-NEXT: br label [[LOOP:%.*]] 534 ; CHECK: loop: 535 ; CHECK-NEXT: [[IDX:%.*]] = phi i32 [ [[IDX_NEXT:%.*]], [[IN_BOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER2]] ] 536 ; CHECK-NEXT: [[IDX_NEXT]] = add i32 [[IDX]], 1 537 ; CHECK-NEXT: [[ABC:%.*]] = icmp ult i32 [[IDX]], [[BOUND]] 538 ; CHECK-NEXT: br i1 true, label [[IN_BOUNDS]], label [[OUT_OF_BOUNDS_LOOPEXIT3:%.*]], !prof !0 539 ; CHECK: in.bounds: 540 ; CHECK-NEXT: [[ADDR:%.*]] = getelementptr i32, i32* [[ARR:%.*]], i32 [[IDX]] 541 ; CHECK-NEXT: store i32 0, i32* [[ADDR]] 542 ; CHECK-NEXT: [[NEXT:%.*]] = icmp ult i32 [[IDX_NEXT]], [[N]] 543 ; CHECK-NEXT: [[TMP12:%.*]] = icmp ult i32 [[IDX_NEXT]], [[EXIT_MAINLOOP_AT]] 544 ; CHECK-NEXT: br i1 [[TMP12]], label [[LOOP]], label [[MAIN_EXIT_SELECTOR:%.*]] 545 ; CHECK: main.exit.selector: 546 ; CHECK-NEXT: [[IDX_NEXT_LCSSA:%.*]] = phi i32 [ [[IDX_NEXT]], [[IN_BOUNDS]] ] 547 ; CHECK-NEXT: [[TMP13:%.*]] = icmp ult i32 [[IDX_NEXT_LCSSA]], [[N]] 548 ; CHECK-NEXT: br i1 [[TMP13]], label [[MAIN_PSEUDO_EXIT]], label [[EXIT_LOOPEXIT:%.*]] 549 ; CHECK: main.pseudo.exit: 550 ; CHECK-NEXT: [[IDX_COPY:%.*]] = phi i32 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ] 551 ; CHECK-NEXT: [[INDVAR_END:%.*]] = phi i32 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ] 552 ; CHECK-NEXT: br label [[POSTLOOP:%.*]] 553 ; CHECK: out.of.bounds.loopexit: 554 ; CHECK-NEXT: br label [[OUT_OF_BOUNDS:%.*]] 555 ; CHECK: out.of.bounds.loopexit3: 556 ; CHECK-NEXT: br label [[OUT_OF_BOUNDS]] 557 ; CHECK: out.of.bounds: 558 ; CHECK-NEXT: ret void 559 ; CHECK: exit.loopexit.loopexit: 560 ; CHECK-NEXT: br label [[EXIT_LOOPEXIT]] 561 ; CHECK: exit.loopexit: 562 ; CHECK-NEXT: br label [[EXIT]] 563 ; CHECK: exit: 564 ; CHECK-NEXT: ret void 565 ; CHECK: postloop: 566 ; CHECK-NEXT: br label [[LOOP_POSTLOOP:%.*]] 567 ; CHECK: loop.postloop: 568 ; CHECK-NEXT: [[IDX_POSTLOOP:%.*]] = phi i32 [ [[IDX_NEXT_POSTLOOP:%.*]], [[IN_BOUNDS_POSTLOOP:%.*]] ], [ [[IDX_COPY]], [[POSTLOOP]] ] 569 ; CHECK-NEXT: [[IDX_NEXT_POSTLOOP]] = add i32 [[IDX_POSTLOOP]], 1 570 ; CHECK-NEXT: [[ABC_POSTLOOP:%.*]] = icmp ult i32 [[IDX_POSTLOOP]], [[BOUND]] 571 ; CHECK-NEXT: br i1 [[ABC_POSTLOOP]], label [[IN_BOUNDS_POSTLOOP]], label [[OUT_OF_BOUNDS_LOOPEXIT:%.*]], !prof !0 572 ; CHECK: in.bounds.postloop: 573 ; CHECK-NEXT: [[ADDR_POSTLOOP:%.*]] = getelementptr i32, i32* [[ARR]], i32 [[IDX_POSTLOOP]] 574 ; CHECK-NEXT: store i32 0, i32* [[ADDR_POSTLOOP]] 575 ; CHECK-NEXT: [[NEXT_POSTLOOP:%.*]] = icmp ult i32 [[IDX_NEXT_POSTLOOP]], [[N]] 576 ; CHECK-NEXT: br i1 [[NEXT_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT:%.*]], !llvm.loop !9, !irce.loop.clone !6 577 ; 578 entry: 579 %first.itr.check = icmp sgt i32 %n, 0 580 br i1 %first.itr.check, label %loop, label %exit 581 582 loop: 583 %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ] 584 %idx.next = add i32 %idx, 1 585 %abc = icmp ult i32 %idx, %bound 586 br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !0 587 588 in.bounds: 589 %addr = getelementptr i32, i32* %arr, i32 %idx 590 store i32 0, i32* %addr 591 %next = icmp ult i32 %idx.next, %n 592 br i1 %next, label %loop, label %exit 593 594 out.of.bounds: 595 ret void 596 597 exit: 598 ret void 599 } 600 !0 = !{!"branch_weights", i32 64, i32 4} 601
