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 @single_access_no_preloop_no_offset(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 br i1 %first.itr.check, label %loop, label %exit 9 10 loop: 11 %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ] 12 %idx.next = add i32 %idx, 1 13 %abc = icmp slt i32 %idx, %len 14 br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !1 15 16 in.bounds: 17 %addr = getelementptr i32, ptr %arr, i32 %idx 18 store i32 0, ptr %addr 19 %next = icmp slt i32 %idx.next, %n 20 br i1 %next, label %loop, label %exit 21 22 out.of.bounds: 23 ret void 24 25 exit: 26 ret void 27} 28 29; CHECK-LABEL: @single_access_no_preloop_no_offset( 30 31; CHECK: loop: 32; CHECK: br i1 true, label %in.bounds, label %out.of.bounds 33 34; CHECK: main.exit.selector: 35; CHECK-NEXT: %idx.next.lcssa = phi i32 [ %idx.next, %in.bounds ] 36; CHECK-NEXT: [[continue:%[^ ]+]] = icmp slt i32 %idx.next.lcssa, %n 37; CHECK-NEXT: br i1 [[continue]], label %main.pseudo.exit, label %exit.loopexit 38 39; CHECK: main.pseudo.exit: 40; CHECK-NEXT: %idx.copy = phi i32 [ 0, %loop.preheader ], [ %idx.next.lcssa, %main.exit.selector ] 41; CHECK-NEXT: %indvar.end = phi i32 [ 0, %loop.preheader ], [ %idx.next.lcssa, %main.exit.selector ] 42; CHECK-NEXT: br label %postloop 43 44; CHECK: postloop: 45; CHECK-NEXT: br label %loop.postloop 46 47; CHECK: loop.postloop: 48; CHECK-NEXT: %idx.postloop = phi i32 [ %idx.next.postloop, %in.bounds.postloop ], [ %idx.copy, %postloop ] 49; CHECK-NEXT: %idx.next.postloop = add i32 %idx.postloop, 1 50; CHECK-NEXT: %abc.postloop = icmp slt i32 %idx.postloop, %len 51; CHECK-NEXT: br i1 %abc.postloop, label %in.bounds.postloop, label %out.of.bounds 52 53; CHECK: in.bounds.postloop: 54; CHECK-NEXT: %addr.postloop = getelementptr i32, ptr %arr, i32 %idx.postloop 55; CHECK-NEXT: store i32 0, ptr %addr.postloop 56; CHECK-NEXT: %next.postloop = icmp slt i32 %idx.next.postloop, %n 57; CHECK-NEXT: br i1 %next.postloop, label %loop.postloop, label %exit.loopexit 58 59 60define void @single_access_no_preloop_with_offset(ptr %arr, ptr %a_len_ptr, i32 %n) { 61 entry: 62 %len = load i32, ptr %a_len_ptr, !range !0 63 %first.itr.check = icmp sgt i32 %n, 0 64 br i1 %first.itr.check, label %loop, label %exit 65 66 loop: 67 %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ] 68 %idx.next = add i32 %idx, 1 69 %idx.for.abc = add i32 %idx, 4 70 %abc = icmp slt i32 %idx.for.abc, %len 71 br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !1 72 73 in.bounds: 74 %addr = getelementptr i32, ptr %arr, i32 %idx.for.abc 75 store i32 0, ptr %addr 76 %next = icmp slt i32 %idx.next, %n 77 br i1 %next, label %loop, label %exit 78 79 out.of.bounds: 80 ret void 81 82 exit: 83 ret void 84} 85 86; CHECK-LABEL: @single_access_no_preloop_with_offset( 87 88; CHECK: loop.preheader: 89; CHECK: [[safe_range_end:[^ ]+]] = add nsw i32 %len, -4 90; CHECK: [[exit_main_loop_at_hiclamp:[^ ]+]] = call i32 @llvm.smin.i32(i32 %n, i32 [[safe_range_end]]) 91; CHECK: [[exit_main_loop_at_loclamp:[^ ]+]] = call i32 @llvm.smax.i32(i32 [[exit_main_loop_at_hiclamp]], i32 0) 92; CHECK: [[enter_main_loop:[^ ]+]] = icmp slt i32 0, [[exit_main_loop_at_loclamp]] 93; CHECK: br i1 [[enter_main_loop]], label %[[loop_preheader:[^ ,]+]], label %main.pseudo.exit 94 95; CHECK: loop: 96; CHECK: br i1 true, label %in.bounds, label %out.of.bounds 97 98; CHECK: in.bounds: 99; CHECK: [[continue_main_loop:[^ ]+]] = icmp slt i32 %idx.next, [[exit_main_loop_at_loclamp]] 100; CHECK: br i1 [[continue_main_loop]], label %loop, label %main.exit.selector 101 102; CHECK: main.pseudo.exit: 103; CHECK: %idx.copy = phi i32 [ 0, %loop.preheader ], [ %idx.next.lcssa, %main.exit.selector ] 104; CHECK: br label %postloop 105 106; CHECK: loop.postloop: 107; CHECK: %idx.postloop = phi i32 [ %idx.next.postloop, %in.bounds.postloop ], [ %idx.copy, %postloop ] 108 109; CHECK: in.bounds.postloop: 110; CHECK: %next.postloop = icmp slt i32 %idx.next.postloop, %n 111; CHECK: br i1 %next.postloop, label %loop.postloop, label %exit.loopexit 112 113; Make sure that we do not do IRCE if we know that the safe iteration range of 114; the main loop is empty. 115 116define void @single_access_empty_range(ptr %arr, ptr %a_len_ptr, i32 %n) { 117 entry: 118 %len = load i32, ptr %a_len_ptr, !range !0 119 %first.itr.check = icmp sgt i32 %n, 0 120 br i1 %first.itr.check, label %loop, label %exit 121 122 loop: 123 %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ] 124 %idx.next = add i32 %idx, 1 125 %abc = icmp slt i32 %idx, 0 126 br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !1 127 128 in.bounds: 129 %addr = getelementptr i32, ptr %arr, i32 %idx 130 store i32 0, ptr %addr 131 %next = icmp slt i32 %idx.next, %n 132 br i1 %next, label %loop, label %exit 133 134 out.of.bounds: 135 ret void 136 137 exit: 138 ret void 139} 140 141; CHECK-LABEL: @single_access_empty_range( 142; CHECK-NOT: br i1 false 143; CHECK-NOT: preloop 144; CHECK-NOT: postloop 145 146define void @single_access_empty_range_2(ptr %arr, ptr %a_len_ptr, i32 %n) { 147 entry: 148 %len = load i32, ptr %a_len_ptr, !range !0 149 %first.itr.check = icmp sgt i32 %n, 0 150 br i1 %first.itr.check, label %loop, label %exit 151 152 loop: 153 %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds2 ] 154 %idx.next = add i32 %idx, 1 155 %abc = icmp slt i32 %idx, 60 156 br i1 %abc, label %in.bounds1, label %out.of.bounds, !prof !1 157 158 in.bounds1: 159 %def = icmp slt i32 %idx, 0 160 br i1 %def, label %in.bounds2, label %out.of.bounds, !prof !1 161 162in.bounds2: 163 %addr = getelementptr i32, ptr %arr, i32 %idx 164 store i32 0, ptr %addr 165 %next = icmp slt i32 %idx.next, %n 166 br i1 %next, label %loop, label %exit 167 168 out.of.bounds: 169 ret void 170 171 exit: 172 ret void 173} 174 175; CHECK-LABEL: @single_access_empty_range_2( 176; CHECK-NOT: br i1 false 177; CHECK-NOT: preloop 178 179define void @single_access_no_preloop_no_offset_phi_len(ptr %arr, ptr %a_len_ptr, ptr %b_len_ptr, i32 %n, i1 %unknown_cond) { 180 entry: 181 br i1 %unknown_cond, label %if.true, label %if.false 182 183if.true: 184 %len_a = load i32, ptr %a_len_ptr, !range !0 185 br label %merge 186 187if.false: 188 %len_b = load i32, ptr %b_len_ptr, !range !0 189 br label %merge 190 191merge: 192 %len = phi i32 [ %len_a, %if.true ], [ %len_b, %if.false ] 193 %first.itr.check = icmp sgt i32 %n, 0 194 br i1 %first.itr.check, label %loop, label %exit 195 196 loop: 197 %idx = phi i32 [ 0, %merge ] , [ %idx.next, %in.bounds ] 198 %idx.next = add i32 %idx, 1 199 %abc = icmp slt i32 %idx, %len 200 br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !1 201 202 in.bounds: 203 %addr = getelementptr i32, ptr %arr, i32 %idx 204 store i32 0, ptr %addr 205 %next = icmp slt i32 %idx.next, %n 206 br i1 %next, label %loop, label %exit 207 208 out.of.bounds: 209 ret void 210 211 exit: 212 ret void 213} 214 215; CHECK-LABEL: @single_access_no_preloop_no_offset_phi_len( 216 217; CHECK: loop: 218; CHECK: br i1 true, label %in.bounds, label %out.of.bounds 219 220; CHECK: main.exit.selector: 221; CHECK-NEXT: %idx.next.lcssa = phi i32 [ %idx.next, %in.bounds ] 222; CHECK-NEXT: [[continue:%[^ ]+]] = icmp slt i32 %idx.next.lcssa, %n 223; CHECK-NEXT: br i1 [[continue]], label %main.pseudo.exit, label %exit.loopexit 224 225; CHECK: main.pseudo.exit: 226; CHECK-NEXT: %idx.copy = phi i32 [ 0, %loop.preheader ], [ %idx.next.lcssa, %main.exit.selector ] 227; CHECK-NEXT: %indvar.end = phi i32 [ 0, %loop.preheader ], [ %idx.next.lcssa, %main.exit.selector ] 228; CHECK-NEXT: br label %postloop 229 230; CHECK: postloop: 231; CHECK-NEXT: br label %loop.postloop 232 233; CHECK: loop.postloop: 234; CHECK-NEXT: %idx.postloop = phi i32 [ %idx.next.postloop, %in.bounds.postloop ], [ %idx.copy, %postloop ] 235; CHECK-NEXT: %idx.next.postloop = add i32 %idx.postloop, 1 236; CHECK-NEXT: %abc.postloop = icmp slt i32 %idx.postloop, %len 237; CHECK-NEXT: br i1 %abc.postloop, label %in.bounds.postloop, label %out.of.bounds 238 239; CHECK: in.bounds.postloop: 240; CHECK-NEXT: %addr.postloop = getelementptr i32, ptr %arr, i32 %idx.postloop 241; CHECK-NEXT: store i32 0, ptr %addr.postloop 242; CHECK-NEXT: %next.postloop = icmp slt i32 %idx.next.postloop, %n 243; CHECK-NEXT: br i1 %next.postloop, label %loop.postloop, label %exit.loopexit 244 245!0 = !{i32 0, i32 2147483647} 246!1 = !{!"branch_weights", i32 64, i32 4} 247