1; RUN: opt -verify-loop-info -passes=irce -S < %s | FileCheck %s 2; RUN: opt -verify-loop-info -passes='require<branch-prob>,irce' -S < %s | FileCheck %s 3 4define void @decrementing_loop(ptr %arr, ptr %a_len_ptr, i32 %n) { 5 entry: 6 %len = load i32, ptr %a_len_ptr, !range !0 7 %first.itr.check = icmp sgt i32 %n, 0 8 %start = sub i32 %n, 1 9 br i1 %first.itr.check, label %loop, label %exit 10 11 loop: 12 %idx = phi i32 [ %start, %entry ] , [ %idx.dec, %in.bounds ] 13 %idx.dec = sub i32 %idx, 1 14 %abc.high = icmp slt i32 %idx, %len 15 %abc.low = icmp sge i32 %idx, 0 16 %abc = and i1 %abc.low, %abc.high 17 br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !1 18 19 in.bounds: 20 %addr = getelementptr i32, ptr %arr, i32 %idx 21 store i32 0, ptr %addr 22 %next = icmp sgt i32 %idx.dec, -1 23 br i1 %next, label %loop, label %exit 24 25 out.of.bounds: 26 ret void 27 28 exit: 29 ret void 30 31; CHECK: loop.preheader: 32; CHECK: [[len_hiclamp:[^ ]+]] = call i32 @llvm.smin.i32(i32 %len, i32 %n) 33; CHECK: [[not_exit_preloop_at:[^ ]+]] = call i32 @llvm.smax.i32(i32 [[len_hiclamp]], i32 0) 34; CHECK: %exit.preloop.at = add nsw i32 [[not_exit_preloop_at]], -1 35} 36 37; Make sure that we can eliminate the range check when the loop looks like: 38; for (i = len.a - 1; i >= 0; --i) 39; b[i] = a[i]; 40define void @test_01(ptr %a, ptr %b, ptr %a_len_ptr, ptr %b_len_ptr) { 41 42; CHECK-LABEL: test_01 43; CHECK: mainloop: 44; CHECK-NEXT: br label %loop 45; CHECK: loop: 46; CHECK: %rc = and i1 true, true 47; CHECK: loop.preloop: 48 49 entry: 50 %len.a = load i32, ptr %a_len_ptr, !range !0 51 %len.b = load i32, ptr %b_len_ptr, !range !0 52 %first.itr.check = icmp ne i32 %len.a, 0 53 br i1 %first.itr.check, label %loop, label %exit 54 55 loop: 56 %idx = phi i32 [ %len.a, %entry ] , [ %idx.next, %in.bounds ] 57 %idx.next = sub i32 %idx, 1 58 %rca = icmp ult i32 %idx.next, %len.a 59 %rcb = icmp ult i32 %idx.next, %len.b 60 %rc = and i1 %rca, %rcb 61 br i1 %rc, label %in.bounds, label %out.of.bounds, !prof !1 62 63 in.bounds: 64 %el.a = getelementptr i32, ptr %a, i32 %idx.next 65 %el.b = getelementptr i32, ptr %b, i32 %idx.next 66 %v = load i32, ptr %el.a 67 store i32 %v, ptr %el.b 68 %loop.cond = icmp slt i32 %idx, 2 69 br i1 %loop.cond, label %exit, label %loop 70 71 out.of.bounds: 72 ret void 73 74 exit: 75 ret void 76} 77 78; Same as test_01, but the latch condition is unsigned 79define void @test_02(ptr %a, ptr %b, ptr %a_len_ptr, ptr %b_len_ptr) { 80 81; CHECK-LABEL: test_02 82; CHECK: mainloop: 83; CHECK-NEXT: br label %loop 84; CHECK: loop: 85; CHECK: %rc = and i1 true, true 86; CHECK: loop.preloop: 87 88 entry: 89 %len.a = load i32, ptr %a_len_ptr, !range !0 90 %len.b = load i32, ptr %b_len_ptr, !range !0 91 %first.itr.check = icmp ne i32 %len.a, 0 92 br i1 %first.itr.check, label %loop, label %exit 93 94 loop: 95 %idx = phi i32 [ %len.a, %entry ] , [ %idx.next, %in.bounds ] 96 %idx.next = sub i32 %idx, 1 97 %rca = icmp ult i32 %idx.next, %len.a 98 %rcb = icmp ult i32 %idx.next, %len.b 99 %rc = and i1 %rca, %rcb 100 br i1 %rc, label %in.bounds, label %out.of.bounds, !prof !1 101 102 in.bounds: 103 %el.a = getelementptr i32, ptr %a, i32 %idx.next 104 %el.b = getelementptr i32, ptr %b, i32 %idx.next 105 %v = load i32, ptr %el.a 106 store i32 %v, ptr %el.b 107 %loop.cond = icmp ult i32 %idx, 2 108 br i1 %loop.cond, label %exit, label %loop 109 110 out.of.bounds: 111 ret void 112 113 exit: 114 ret void 115} 116 117; Check that we can figure out that IV is non-negative via implication through 118; Phi node. 119define void @test_03(ptr %a, ptr %a_len_ptr, i1 %cond) { 120 121; CHECK-LABEL: test_03 122; CHECK: mainloop: 123; CHECK-NEXT: br label %loop 124; CHECK: loop: 125; CHECK: br i1 true, label %in.bounds, label %out.of.bounds 126; CHECK: loop.preloop: 127 128 entry: 129 %len.a = load i32, ptr %a_len_ptr, !range !0 130 %len.minus.one = sub nsw i32 %len.a, 1 131 %len.minus.two = sub nsw i32 %len.a, 2 132 br i1 %cond, label %if.true, label %if.false 133 134if.true: 135 br label %merge 136 137if.false: 138 br label %merge 139 140merge: 141 %starting.value = phi i32 [ %len.minus.two, %if.true ], [ %len.minus.one, %if.false ] 142 %first.itr.check = icmp sgt i32 %len.a, 3 143 br i1 %first.itr.check, label %loop, label %exit 144 145loop: 146 %idx = phi i32 [ %starting.value, %merge ] , [ %idx.next, %in.bounds ] 147 %idx.next = sub i32 %idx, 1 148 %rc = icmp ult i32 %idx.next, %len.a 149 br i1 %rc, label %in.bounds, label %out.of.bounds, !prof !1 150 151in.bounds: 152 %el.a = getelementptr i32, ptr %a, i32 %idx.next 153 %v = load i32, ptr %el.a 154 %loop.cond = icmp slt i32 %idx, 2 155 br i1 %loop.cond, label %exit, label %loop 156 157out.of.bounds: 158 ret void 159 160exit: 161 ret void 162} 163 164; Check that we can figure out that IV is non-negative via implication through 165; two Phi nodes. 166define void @test_04(ptr %a, ptr %a_len_ptr, i1 %cond) { 167 168; CHECK-LABEL: test_04 169; CHECK: mainloop: 170; CHECK-NEXT: br label %loop 171; CHECK: loop: 172; CHECK: br i1 true, label %in.bounds, label %out.of.bounds 173; CHECK: loop.preloop: 174 175 entry: 176 %len.a = load i32, ptr %a_len_ptr, !range !0 177 %len.minus.one = sub nsw i32 %len.a, 1 178 %len.plus.one = add nsw i32 %len.a, 1 179 %len.minus.two = sub nsw i32 %len.a, 2 180 br i1 %cond, label %if.true, label %if.false 181 182if.true: 183 br label %merge 184 185if.false: 186 br label %merge 187 188merge: 189 %starting.value = phi i32 [ %len.minus.two, %if.true ], [ %len.minus.one, %if.false ] 190 %len.phi = phi i32 [ %len.a, %if.true ], [ %len.plus.one, %if.false ] 191 %first.itr.check = icmp sgt i32 %len.a, 3 192 br i1 %first.itr.check, label %loop, label %exit 193 194loop: 195 %idx = phi i32 [ %starting.value, %merge ] , [ %idx.next, %in.bounds ] 196 %idx.next = sub i32 %idx, 1 197 %rc = icmp ult i32 %idx.next, %len.phi 198 br i1 %rc, label %in.bounds, label %out.of.bounds, !prof !1 199 200in.bounds: 201 %el.a = getelementptr i32, ptr %a, i32 %idx.next 202 %v = load i32, ptr %el.a 203 %loop.cond = icmp slt i32 %idx, 2 204 br i1 %loop.cond, label %exit, label %loop 205 206out.of.bounds: 207 ret void 208 209exit: 210 ret void 211} 212 213; Check that we can figure out that IV is non-negative via implication through 214; two Phi nodes, one being AddRec. 215define void @test_05(ptr %a, ptr %a_len_ptr, i1 %cond) { 216 217; CHECK-LABEL: test_05 218; CHECK: mainloop: 219; CHECK-NEXT: br label %loop 220; CHECK: loop: 221; CHECK: br i1 true, label %in.bounds, label %out.of.bounds 222; CHECK: loop.preloop: 223 224 entry: 225 %len.a = load i32, ptr %a_len_ptr, !range !0 226 %len.minus.one = sub nsw i32 %len.a, 1 227 %len.plus.one = add nsw i32 %len.a, 1 228 %len.minus.two = sub nsw i32 %len.a, 2 229 br label %merge 230 231merge: 232 %starting.value = phi i32 [ %len.minus.two, %entry ], [ %len.minus.one, %merge ] 233 %len.phi = phi i32 [ %len.a, %entry ], [ %len.phi.next, %merge ] 234 %len.phi.next = add nsw i32 %len.phi, 1 235 br i1 true, label %first.iter.check, label %merge 236 237first.iter.check: 238 %first.itr.check = icmp sgt i32 %len.a, 3 239 br i1 %first.itr.check, label %loop, label %exit 240 241loop: 242 %idx = phi i32 [ %starting.value, %first.iter.check ] , [ %idx.next, %in.bounds ] 243 %idx.next = sub i32 %idx, 1 244 %rc = icmp ult i32 %idx.next, %len.phi 245 br i1 %rc, label %in.bounds, label %out.of.bounds, !prof !1 246 247in.bounds: 248 %el.a = getelementptr i32, ptr %a, i32 %idx.next 249 %v = load i32, ptr %el.a 250 %loop.cond = icmp slt i32 %idx, 2 251 br i1 %loop.cond, label %exit, label %loop 252 253out.of.bounds: 254 ret void 255 256exit: 257 ret void 258} 259 260!0 = !{i32 0, i32 2147483647} 261!1 = !{!"branch_weights", i32 64, i32 4} 262