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>,irce' -S < %s 2>&1 | FileCheck %s 3 4; CHECK-LABEL: irce: in function test_01: constrained Loop at depth 1 containing: 5; CHECK-LABEL: irce: in function test_02: constrained Loop at depth 1 containing: 6; CHECK-LABEL: irce: in function test_03: constrained Loop at depth 1 containing: 7; CHECK-LABEL: irce: in function test_04: constrained Loop at depth 1 containing: 8; CHECK-LABEL: irce: in function test_05: constrained Loop at depth 1 containing: 9 10; This test used to demonstrate a miscompile: the outer loop's IV iterates in 11; range of [2, 400) and the range check is done against value 331. Due to a bug 12; in range intersection IRCE manages to eliminate the range check without 13; inserting a postloop, which is incorrect. We treat the range of this test as 14; an unsigned range and are able to intersect ranges correctly and insert a 15; postloop. 16 17define void @test_01() { 18 19; CHECK-LABEL: test_01 20; CHECK-NOT: preloop 21; CHECK: range_check_block: ; preds = %inner_loop 22; CHECK-NEXT: %range_check = icmp slt i32 %iv, 331 23; CHECK-NEXT: br i1 true, label %loop_latch 24; CHECK: loop_latch: 25; CHECK-NEXT: %iv_next = add i32 %iv, 1 26; CHECK-NEXT: %loop_cond = icmp ult i32 %iv_next, 400 27; CHECK-NEXT: [[COND:%[^ ]+]] = icmp ult i32 %iv_next, 331 28; CHECK-NEXT: br i1 [[COND]], label %loop_header, label %main.exit.selector 29; CHECK: main.exit.selector: ; preds = %loop_latch 30; CHECK-NEXT: %iv_next.lcssa = phi i32 [ %iv_next, %loop_latch ] 31; CHECK-NEXT: %iv.lcssa = phi i32 [ %iv, %loop_latch ] 32; CHECK-NEXT: [[MES_COND:%[^ ]+]] = icmp ult i32 %iv_next.lcssa, 400 33; CHECK-NEXT: br i1 [[MES_COND]], label %main.pseudo.exit, label %exit 34; CHECK: loop_latch.postloop: ; preds = %range_check_block.postloop 35; CHECK-NEXT: %iv_next.postloop = add i32 %iv.postloop, 1 36; CHECK-NEXT: %loop_cond.postloop = icmp ult i32 %iv_next.postloop, 400 37; CHECK-NEXT: br i1 %loop_cond.postloop, label %loop_header.postloop, label %exit.loopexit 38 39entry: 40 br label %loop_header 41 42loop_header: ; preds = %loop_latch, %entry 43 %iv = phi i32 [ 2, %entry ], [ %iv_next, %loop_latch ] 44 %iv.prev = phi i32 [ 1, %entry ], [ %iv, %loop_latch ] 45 %tmp2 = icmp sgt i32 %iv.prev, -1 46 br i1 %tmp2, label %loop_header.split.us, label %exit 47 48loop_header.split.us: ; preds = %loop_header 49 br label %inner_loop 50 51inner_loop: ; preds = %inner_loop, %loop_header.split.us 52 %inner_iv = phi i32 [ 1, %loop_header.split.us ], [ %inner_iv_next, %inner_loop ] 53 %inner_iv_next = add nuw nsw i32 %inner_iv, 1 54 %inner_cond = icmp ult i32 %inner_iv_next, 31 55 br i1 %inner_cond, label %inner_loop, label %range_check_block 56 57exit: ; preds = %loop_latch, %loop_header 58 ret void 59 60range_check_block: ; preds = %inner_loop 61 %range_check = icmp slt i32 %iv, 331 62 br i1 %range_check, label %loop_latch, label %deopt 63 64loop_latch: ; preds = %range_check_block 65 %iv_next = add i32 %iv, 1 66 %loop_cond = icmp ult i32 %iv_next, 400 67 br i1 %loop_cond, label %loop_header, label %exit 68 69deopt: ; preds = %range_check_block 70 ret void 71} 72 73; Similar to test_01, but here the range check is done against 450. No postloop 74; is required. 75 76define void @test_02() { 77 78; CHECK-LABEL: test_02 79; CHECK-NOT: preloop 80; CHECK-NOT: postloop 81; CHECK: range_check_block: ; preds = %inner_loop 82; CHECK-NEXT: %range_check = icmp slt i32 %iv, 450 83; CHECK-NEXT: br i1 true, label %loop_latch 84; CHECK: loop_latch: ; preds = %range_check_block 85; CHECK-NEXT: %iv_next = add i32 %iv, 1 86; CHECK-NEXT: %loop_cond = icmp ult i32 %iv_next, 400 87; CHECK-NEXT: br i1 %loop_cond, label %loop_header, label %exit 88 89entry: 90 br label %loop_header 91 92loop_header: ; preds = %loop_latch, %entry 93 %iv = phi i32 [ 2, %entry ], [ %iv_next, %loop_latch ] 94 %iv.prev = phi i32 [ 1, %entry ], [ %iv, %loop_latch ] 95 %tmp2 = icmp sgt i32 %iv.prev, -1 96 br i1 %tmp2, label %loop_header.split.us, label %exit 97 98loop_header.split.us: ; preds = %loop_header 99 br label %inner_loop 100 101inner_loop: ; preds = %inner_loop, %loop_header.split.us 102 %inner_iv = phi i32 [ 1, %loop_header.split.us ], [ %inner_iv_next, %inner_loop ] 103 %inner_iv_next = add nuw nsw i32 %inner_iv, 1 104 %inner_cond = icmp ult i32 %inner_iv_next, 31 105 br i1 %inner_cond, label %inner_loop, label %range_check_block 106 107exit: ; preds = %loop_latch, %loop_header 108 ret void 109 110range_check_block: ; preds = %inner_loop 111 %range_check = icmp slt i32 %iv, 450 112 br i1 %range_check, label %loop_latch, label %deopt 113 114loop_latch: ; preds = %range_check_block 115 %iv_next = add i32 %iv, 1 116 %loop_cond = icmp ult i32 %iv_next, 400 117 br i1 %loop_cond, label %loop_header, label %exit 118 119deopt: ; preds = %range_check_block 120 ret void 121} 122 123; Range check is made against 0, so the safe iteration range is empty. IRCE 124; should not apply to the inner loop. The condition %tmp2 can be eliminated. 125 126define void @test_03() { 127 128; CHECK-LABEL: test_03 129; CHECK-NOT: preloop 130; CHECK-NOT: postloop 131; CHECK: %tmp2 = icmp sgt i32 %iv.prev, -1 132; CHECK-NEXT: br i1 true, label %loop_header.split.us, label %exit 133; CHECK: range_check_block: 134; CHECK-NEXT: %range_check = icmp slt i32 %iv, 0 135; CHECK-NEXT: br i1 %range_check, label %loop_latch, label %deopt 136 137entry: 138 br label %loop_header 139 140loop_header: ; preds = %loop_latch, %entry 141 %iv = phi i32 [ 2, %entry ], [ %iv_next, %loop_latch ] 142 %iv.prev = phi i32 [ 1, %entry ], [ %iv, %loop_latch ] 143 %tmp2 = icmp sgt i32 %iv.prev, -1 144 br i1 %tmp2, label %loop_header.split.us, label %exit 145 146loop_header.split.us: ; preds = %loop_header 147 br label %inner_loop 148 149inner_loop: ; preds = %inner_loop, %loop_header.split.us 150 %inner_iv = phi i32 [ 1, %loop_header.split.us ], [ %inner_iv_next, %inner_loop ] 151 %inner_iv_next = add nuw nsw i32 %inner_iv, 1 152 %inner_cond = icmp ult i32 %inner_iv_next, 31 153 br i1 %inner_cond, label %inner_loop, label %range_check_block 154 155exit: ; preds = %loop_latch, %loop_header 156 ret void 157 158range_check_block: ; preds = %inner_loop 159 %range_check = icmp slt i32 %iv, 0 160 br i1 %range_check, label %loop_latch, label %deopt 161 162loop_latch: ; preds = %range_check_block 163 %iv_next = add i32 %iv, 1 164 %loop_cond = icmp ult i32 %iv_next, 400 165 br i1 %loop_cond, label %loop_header, label %exit 166 167deopt: ; preds = %range_check_block 168 ret void 169} 170 171; We can also properly eliminate range check against %n which is not always 172; known positive. 173 174define void @test_04(i32* %p) { 175 176; CHECK-LABEL: test_04 177; CHECK: entry 178; CHECK-NOT: preloop 179; CHECK: %tmp2 = icmp sgt i32 %iv.prev, -1 180; CHECK-NEXT: br i1 true, label %loop_header.split.us, label %exit 181; CHECK: range_check_block: 182; CHECK-NEXT: %range_check = icmp slt i32 %iv, %n 183; CHECK-NEXT: br i1 true, label %loop_latch, label %deopt 184; CHECK: postloop: 185 186entry: 187 %n = load i32, i32* %p 188 br label %loop_header 189 190loop_header: ; preds = %loop_latch, %entry 191 %iv = phi i32 [ 2, %entry ], [ %iv_next, %loop_latch ] 192 %iv.prev = phi i32 [ 1, %entry ], [ %iv, %loop_latch ] 193 %tmp2 = icmp sgt i32 %iv.prev, -1 194 br i1 %tmp2, label %loop_header.split.us, label %exit 195 196loop_header.split.us: ; preds = %loop_header 197 br label %inner_loop 198 199inner_loop: ; preds = %inner_loop, %loop_header.split.us 200 %inner_iv = phi i32 [ 1, %loop_header.split.us ], [ %inner_iv_next, %inner_loop ] 201 %inner_iv_next = add nuw nsw i32 %inner_iv, 1 202 %inner_cond = icmp ult i32 %inner_iv_next, 31 203 br i1 %inner_cond, label %inner_loop, label %range_check_block 204 205exit: ; preds = %loop_latch, %loop_header 206 ret void 207 208range_check_block: ; preds = %inner_loop 209 %range_check = icmp slt i32 %iv, %n 210 br i1 %range_check, label %loop_latch, label %deopt 211 212loop_latch: ; preds = %range_check_block 213 %iv_next = add i32 %iv, 1 214 %loop_cond = icmp ult i32 %iv_next, 400 215 br i1 %loop_cond, label %loop_header, label %exit 216 217deopt: ; preds = %range_check_block 218 ret void 219} 220 221; Same as test_04, but range guarantees that %n is positive. So we can safely 222; intersect ranges (with insertion of postloop). 223 224define void @test_05(i32* %p) { 225 226; CHECK-LABEL: test_05 227; CHECK-NOT: preloop 228; CHECK: entry: 229; CHECK-NEXT: %n = load i32, i32* %p, align 4, !range ! 230; CHECK-NEXT: [[CMP_1:%[^ ]+]] = icmp ugt i32 %n, 2 231; CHECK-NEXT: %exit.mainloop.at = select i1 [[CMP_1]], i32 %n, i32 2 232; CHECK-NEXT: [[CMP_2:%[^ ]+]] = icmp ult i32 2, %exit.mainloop.at 233; CHECK-NEXT: br i1 [[CMP_2]], label %loop_header.preheader, label %main.pseudo.exit 234; CHECK: range_check_block: ; preds = %inner_loop 235; CHECK-NEXT: %range_check = icmp slt i32 %iv, %n 236; CHECK-NEXT: br i1 true, label %loop_latch, label %deopt.loopexit2 237; CHECK: loop_latch: ; preds = %range_check_block 238; CHECK-NEXT: %iv_next = add i32 %iv, 1 239; CHECK-NEXT: %loop_cond = icmp ult i32 %iv_next, 400 240; CHECK-NEXT: [[COND:%[^ ]+]] = icmp ult i32 %iv_next, %exit.mainloop.at 241; CHECK-NEXT: br i1 [[COND]], label %loop_header, label %main.exit.selector 242; CHECK: main.exit.selector: ; preds = %loop_latch 243; CHECK-NEXT: %iv_next.lcssa = phi i32 [ %iv_next, %loop_latch ] 244; CHECK-NEXT: %iv.lcssa = phi i32 [ %iv, %loop_latch ] 245; CHECK-NEXT: [[MES_COND:%[^ ]+]] = icmp ult i32 %iv_next.lcssa, 400 246; CHECK-NEXT: br i1 [[MES_COND]], label %main.pseudo.exit, label %exit 247; CHECK: loop_latch.postloop: ; preds = %range_check_block.postloop 248; CHECK-NEXT: %iv_next.postloop = add i32 %iv.postloop, 1 249; CHECK-NEXT: %loop_cond.postloop = icmp ult i32 %iv_next.postloop, 400 250; CHECK-NEXT: br i1 %loop_cond.postloop, label %loop_header.postloop, label %exit.loopexit 251 252entry: 253 %n = load i32, i32* %p, !range !0 254 br label %loop_header 255 256loop_header: ; preds = %loop_latch, %entry 257 %iv = phi i32 [ 2, %entry ], [ %iv_next, %loop_latch ] 258 %iv.prev = phi i32 [ 1, %entry ], [ %iv, %loop_latch ] 259 %tmp2 = icmp sgt i32 %iv.prev, -1 260 br i1 %tmp2, label %loop_header.split.us, label %exit 261 262loop_header.split.us: ; preds = %loop_header 263 br label %inner_loop 264 265inner_loop: ; preds = %inner_loop, %loop_header.split.us 266 %inner_iv = phi i32 [ 1, %loop_header.split.us ], [ %inner_iv_next, %inner_loop ] 267 %inner_iv_next = add nuw nsw i32 %inner_iv, 1 268 %inner_cond = icmp ult i32 %inner_iv_next, 31 269 br i1 %inner_cond, label %inner_loop, label %range_check_block 270 271exit: ; preds = %loop_latch, %loop_header 272 ret void 273 274range_check_block: ; preds = %inner_loop 275 %range_check = icmp slt i32 %iv, %n 276 br i1 %range_check, label %loop_latch, label %deopt 277 278loop_latch: ; preds = %range_check_block 279 %iv_next = add i32 %iv, 1 280 %loop_cond = icmp ult i32 %iv_next, 400 281 br i1 %loop_cond, label %loop_header, label %exit 282 283deopt: ; preds = %range_check_block 284 ret void 285} 286 287!0 = !{i32 0, i32 50} 288