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