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. 10define 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. 59define 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. 109define 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. 208define 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). 305define 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). 356define 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). 408define 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). 509define 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