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