262 lines · plain
1; RUN: opt -verify-loop-info -passes=irce -S < %s | FileCheck %s2; RUN: opt -verify-loop-info -passes='require<branch-prob>,irce' -S < %s | FileCheck %s3 4define void @decrementing_loop(ptr %arr, ptr %a_len_ptr, i32 %n) {5 entry:6 %len = load i32, ptr %a_len_ptr, !range !07 %first.itr.check = icmp sgt i32 %n, 08 %start = sub i32 %n, 19 br i1 %first.itr.check, label %loop, label %exit10 11 loop:12 %idx = phi i32 [ %start, %entry ] , [ %idx.dec, %in.bounds ]13 %idx.dec = sub i32 %idx, 114 %abc.high = icmp slt i32 %idx, %len15 %abc.low = icmp sge i32 %idx, 016 %abc = and i1 %abc.low, %abc.high17 br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !118 19 in.bounds:20 %addr = getelementptr i32, ptr %arr, i32 %idx21 store i32 0, ptr %addr22 %next = icmp sgt i32 %idx.dec, -123 br i1 %next, label %loop, label %exit24 25 out.of.bounds:26 ret void27 28 exit:29 ret void30 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]], -135}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_0143; CHECK: mainloop:44; CHECK-NEXT: br label %loop45; CHECK: loop:46; CHECK: %rc = and i1 true, true47; CHECK: loop.preloop:48 49 entry:50 %len.a = load i32, ptr %a_len_ptr, !range !051 %len.b = load i32, ptr %b_len_ptr, !range !052 %first.itr.check = icmp ne i32 %len.a, 053 br i1 %first.itr.check, label %loop, label %exit54 55 loop:56 %idx = phi i32 [ %len.a, %entry ] , [ %idx.next, %in.bounds ]57 %idx.next = sub i32 %idx, 158 %rca = icmp ult i32 %idx.next, %len.a59 %rcb = icmp ult i32 %idx.next, %len.b60 %rc = and i1 %rca, %rcb61 br i1 %rc, label %in.bounds, label %out.of.bounds, !prof !162 63 in.bounds:64 %el.a = getelementptr i32, ptr %a, i32 %idx.next65 %el.b = getelementptr i32, ptr %b, i32 %idx.next66 %v = load i32, ptr %el.a67 store i32 %v, ptr %el.b68 %loop.cond = icmp slt i32 %idx, 269 br i1 %loop.cond, label %exit, label %loop70 71 out.of.bounds:72 ret void73 74 exit:75 ret void76}77 78; Same as test_01, but the latch condition is unsigned79define void @test_02(ptr %a, ptr %b, ptr %a_len_ptr, ptr %b_len_ptr) {80 81; CHECK-LABEL: test_0282; CHECK: mainloop:83; CHECK-NEXT: br label %loop84; CHECK: loop:85; CHECK: %rc = and i1 true, true86; CHECK: loop.preloop:87 88 entry:89 %len.a = load i32, ptr %a_len_ptr, !range !090 %len.b = load i32, ptr %b_len_ptr, !range !091 %first.itr.check = icmp ne i32 %len.a, 092 br i1 %first.itr.check, label %loop, label %exit93 94 loop:95 %idx = phi i32 [ %len.a, %entry ] , [ %idx.next, %in.bounds ]96 %idx.next = sub i32 %idx, 197 %rca = icmp ult i32 %idx.next, %len.a98 %rcb = icmp ult i32 %idx.next, %len.b99 %rc = and i1 %rca, %rcb100 br i1 %rc, label %in.bounds, label %out.of.bounds, !prof !1101 102 in.bounds:103 %el.a = getelementptr i32, ptr %a, i32 %idx.next104 %el.b = getelementptr i32, ptr %b, i32 %idx.next105 %v = load i32, ptr %el.a106 store i32 %v, ptr %el.b107 %loop.cond = icmp ult i32 %idx, 2108 br i1 %loop.cond, label %exit, label %loop109 110 out.of.bounds:111 ret void112 113 exit:114 ret void115}116 117; Check that we can figure out that IV is non-negative via implication through118; Phi node.119define void @test_03(ptr %a, ptr %a_len_ptr, i1 %cond) {120 121; CHECK-LABEL: test_03122; CHECK: mainloop:123; CHECK-NEXT: br label %loop124; CHECK: loop:125; CHECK: br i1 true, label %in.bounds, label %out.of.bounds126; CHECK: loop.preloop:127 128 entry:129 %len.a = load i32, ptr %a_len_ptr, !range !0130 %len.minus.one = sub nsw i32 %len.a, 1131 %len.minus.two = sub nsw i32 %len.a, 2132 br i1 %cond, label %if.true, label %if.false133 134if.true:135 br label %merge136 137if.false:138 br label %merge139 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, 3143 br i1 %first.itr.check, label %loop, label %exit144 145loop:146 %idx = phi i32 [ %starting.value, %merge ] , [ %idx.next, %in.bounds ]147 %idx.next = sub i32 %idx, 1148 %rc = icmp ult i32 %idx.next, %len.a149 br i1 %rc, label %in.bounds, label %out.of.bounds, !prof !1150 151in.bounds:152 %el.a = getelementptr i32, ptr %a, i32 %idx.next153 %v = load i32, ptr %el.a154 %loop.cond = icmp slt i32 %idx, 2155 br i1 %loop.cond, label %exit, label %loop156 157out.of.bounds:158 ret void159 160exit:161 ret void162}163 164; Check that we can figure out that IV is non-negative via implication through165; two Phi nodes.166define void @test_04(ptr %a, ptr %a_len_ptr, i1 %cond) {167 168; CHECK-LABEL: test_04169; CHECK: mainloop:170; CHECK-NEXT: br label %loop171; CHECK: loop:172; CHECK: br i1 true, label %in.bounds, label %out.of.bounds173; CHECK: loop.preloop:174 175 entry:176 %len.a = load i32, ptr %a_len_ptr, !range !0177 %len.minus.one = sub nsw i32 %len.a, 1178 %len.plus.one = add nsw i32 %len.a, 1179 %len.minus.two = sub nsw i32 %len.a, 2180 br i1 %cond, label %if.true, label %if.false181 182if.true:183 br label %merge184 185if.false:186 br label %merge187 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, 3192 br i1 %first.itr.check, label %loop, label %exit193 194loop:195 %idx = phi i32 [ %starting.value, %merge ] , [ %idx.next, %in.bounds ]196 %idx.next = sub i32 %idx, 1197 %rc = icmp ult i32 %idx.next, %len.phi198 br i1 %rc, label %in.bounds, label %out.of.bounds, !prof !1199 200in.bounds:201 %el.a = getelementptr i32, ptr %a, i32 %idx.next202 %v = load i32, ptr %el.a203 %loop.cond = icmp slt i32 %idx, 2204 br i1 %loop.cond, label %exit, label %loop205 206out.of.bounds:207 ret void208 209exit:210 ret void211}212 213; Check that we can figure out that IV is non-negative via implication through214; two Phi nodes, one being AddRec.215define void @test_05(ptr %a, ptr %a_len_ptr, i1 %cond) {216 217; CHECK-LABEL: test_05218; CHECK: mainloop:219; CHECK-NEXT: br label %loop220; CHECK: loop:221; CHECK: br i1 true, label %in.bounds, label %out.of.bounds222; CHECK: loop.preloop:223 224 entry:225 %len.a = load i32, ptr %a_len_ptr, !range !0226 %len.minus.one = sub nsw i32 %len.a, 1227 %len.plus.one = add nsw i32 %len.a, 1228 %len.minus.two = sub nsw i32 %len.a, 2229 br label %merge230 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, 1235 br i1 true, label %first.iter.check, label %merge236 237first.iter.check:238 %first.itr.check = icmp sgt i32 %len.a, 3239 br i1 %first.itr.check, label %loop, label %exit240 241loop:242 %idx = phi i32 [ %starting.value, %first.iter.check ] , [ %idx.next, %in.bounds ]243 %idx.next = sub i32 %idx, 1244 %rc = icmp ult i32 %idx.next, %len.phi245 br i1 %rc, label %in.bounds, label %out.of.bounds, !prof !1246 247in.bounds:248 %el.a = getelementptr i32, ptr %a, i32 %idx.next249 %v = load i32, ptr %el.a250 %loop.cond = icmp slt i32 %idx, 2251 br i1 %loop.cond, label %exit, label %loop252 253out.of.bounds:254 ret void255 256exit:257 ret void258}259 260!0 = !{i32 0, i32 2147483647}261!1 = !{!"branch_weights", i32 64, i32 4}262