diff options
Diffstat (limited to 'test/Transforms/IRCE')
| -rw-r--r-- | test/Transforms/IRCE/bug-mismatched-types.ll | 66 | ||||
| -rw-r--r-- | test/Transforms/IRCE/decrementing-loop.ll | 43 | ||||
| -rw-r--r-- | test/Transforms/IRCE/low-becount.ll | 32 | ||||
| -rw-r--r-- | test/Transforms/IRCE/multiple-access-no-preloop.ll | 66 | ||||
| -rw-r--r-- | test/Transforms/IRCE/not-likely-taken.ll | 40 | ||||
| -rw-r--r-- | test/Transforms/IRCE/single-access-no-preloop.ll | 116 | ||||
| -rw-r--r-- | test/Transforms/IRCE/single-access-with-preloop.ll | 71 | ||||
| -rw-r--r-- | test/Transforms/IRCE/unhandled.ll | 37 | ||||
| -rw-r--r-- | test/Transforms/IRCE/with-parent-loops.ll | 345 |
9 files changed, 816 insertions, 0 deletions
diff --git a/test/Transforms/IRCE/bug-mismatched-types.ll b/test/Transforms/IRCE/bug-mismatched-types.ll new file mode 100644 index 0000000..9ff7249 --- /dev/null +++ b/test/Transforms/IRCE/bug-mismatched-types.ll @@ -0,0 +1,66 @@ +; RUN: opt -irce -S < %s + +; These test cases don't check the correctness of the transform, but +; that the -irce does not crash in the presence of certain things in +; the IR: + +define void @mismatched_types_1() { +; In this test case, the safe range for the only range check in the +; loop is of type [i32, i32) while the backedge taken count is of type +; i64. + +; CHECK-LABEL: mismatched_types_1 +entry: + br label %for.body + +for.body: + %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.inc ] + %0 = trunc i64 %indvars.iv to i32 + %1 = icmp ult i32 %0, 7 + br i1 %1, label %switch.lookup, label %for.inc + +switch.lookup: + br label %for.inc + +for.inc: + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + %cmp55 = icmp slt i64 %indvars.iv.next, 11 + br i1 %cmp55, label %for.body, label %for.end + +for.end: + unreachable +} + +define void @mismatched_types_2() { +; In this test case, there are two range check in the loop, one with a +; safe range of type [i32, i32) and one with a safe range of type +; [i64, i64). + +; CHECK-LABEL: mismatched_types_2 +entry: + br label %for.body.a + +for.body.a: + %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.inc ] + %cond.a = icmp ult i64 %indvars.iv, 7 + br i1 %cond.a, label %switch.lookup.a, label %for.body.b + +switch.lookup.a: + br label %for.body.b + +for.body.b: + %truncated = trunc i64 %indvars.iv to i32 + %cond.b = icmp ult i32 %truncated, 7 + br i1 %cond.b, label %switch.lookup.b, label %for.inc + +switch.lookup.b: + br label %for.inc + +for.inc: + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + %cmp55 = icmp slt i64 %indvars.iv.next, 11 + br i1 %cmp55, label %for.body.a, label %for.end + +for.end: + unreachable +} diff --git a/test/Transforms/IRCE/decrementing-loop.ll b/test/Transforms/IRCE/decrementing-loop.ll new file mode 100644 index 0000000..877a2c2 --- /dev/null +++ b/test/Transforms/IRCE/decrementing-loop.ll @@ -0,0 +1,43 @@ +; RUN: opt -irce -S < %s | FileCheck %s + +define void @decrementing_loop(i32 *%arr, i32 *%a_len_ptr, i32 %n) { + entry: + %len = load i32* %a_len_ptr, !range !0 + %first.itr.check = icmp sgt i32 %n, 0 + %start = sub i32 %n, 1 + br i1 %first.itr.check, label %loop, label %exit + + loop: + %idx = phi i32 [ %start, %entry ] , [ %idx.dec, %in.bounds ] + %idx.dec = sub i32 %idx, 1 + %abc.high = icmp slt i32 %idx, %len + %abc.low = icmp sge i32 %idx, 0 + %abc = and i1 %abc.low, %abc.high + br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !1 + + in.bounds: + %addr = getelementptr i32* %arr, i32 %idx + store i32 0, i32* %addr + %next = icmp sgt i32 %idx.dec, -1 + br i1 %next, label %loop, label %exit + + out.of.bounds: + ret void + + exit: + ret void + +; CHECK: loop.preheader: +; CHECK: [[indvar_start:[^ ]+]] = add i32 %n, -1 +; CHECK: [[not_len:[^ ]+]] = sub i32 -1, %len +; CHECK: [[not_n:[^ ]+]] = sub i32 -1, %n +; CHECK: [[not_len_hiclamp_cmp:[^ ]+]] = icmp sgt i32 [[not_len]], [[not_n]] +; CHECK: [[not_len_hiclamp:[^ ]+]] = select i1 [[not_len_hiclamp_cmp]], i32 [[not_len]], i32 [[not_n]] +; CHECK: [[len_hiclamp:[^ ]+]] = sub i32 -1, [[not_len_hiclamp]] +; CHECK: [[not_exit_preloop_at_cmp:[^ ]+]] = icmp sgt i32 [[len_hiclamp]], 0 +; CHECK: [[not_exit_preloop_at:[^ ]+]] = select i1 [[not_exit_preloop_at_cmp]], i32 [[len_hiclamp]], i32 0 +; CHECK: %exit.preloop.at = add i32 [[not_exit_preloop_at]], -1 +} + +!0 = !{i32 0, i32 2147483647} +!1 = !{!"branch_weights", i32 64, i32 4} diff --git a/test/Transforms/IRCE/low-becount.ll b/test/Transforms/IRCE/low-becount.ll new file mode 100644 index 0000000..2ddaf19 --- /dev/null +++ b/test/Transforms/IRCE/low-becount.ll @@ -0,0 +1,32 @@ +; RUN: opt -irce-print-changed-loops -irce -S < %s 2>&1 | FileCheck %s + +; CHECK-NOT: constrained Loop + +define void @low_profiled_be_count(i32 *%arr, i32 *%a_len_ptr, i32 %n) { + entry: + %len = load i32* %a_len_ptr, !range !0 + %first.itr.check = icmp sgt i32 %n, 0 + br i1 %first.itr.check, label %loop, label %exit + + loop: + %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ] + %idx.next = add i32 %idx, 1 + %abc = icmp slt i32 %idx, %len + br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !1 + + in.bounds: + %addr = getelementptr i32* %arr, i32 %idx + store i32 0, i32* %addr + %next = icmp slt i32 %idx.next, %n + br i1 %next, label %loop, label %exit, !prof !2 + + out.of.bounds: + ret void + + exit: + ret void +} + +!0 = !{i32 0, i32 2147483647} +!1 = !{!"branch_weights", i32 64, i32 4} +!2 = !{!"branch_weights", i32 4, i32 64} diff --git a/test/Transforms/IRCE/multiple-access-no-preloop.ll b/test/Transforms/IRCE/multiple-access-no-preloop.ll new file mode 100644 index 0000000..304bb4d --- /dev/null +++ b/test/Transforms/IRCE/multiple-access-no-preloop.ll @@ -0,0 +1,66 @@ +; RUN: opt -irce -S < %s | FileCheck %s + +define void @multiple_access_no_preloop( + i32* %arr_a, i32* %a_len_ptr, i32* %arr_b, i32* %b_len_ptr, i32 %n) { + + entry: + %len.a = load i32* %a_len_ptr, !range !0 + %len.b = load i32* %b_len_ptr, !range !0 + %first.itr.check = icmp sgt i32 %n, 0 + br i1 %first.itr.check, label %loop, label %exit + + loop: + %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds.b ] + %idx.next = add i32 %idx, 1 + %abc.a = icmp slt i32 %idx, %len.a + br i1 %abc.a, label %in.bounds.a, label %out.of.bounds, !prof !1 + + in.bounds.a: + %addr.a = getelementptr i32* %arr_a, i32 %idx + store i32 0, i32* %addr.a + %abc.b = icmp slt i32 %idx, %len.b + br i1 %abc.b, label %in.bounds.b, label %out.of.bounds, !prof !1 + + in.bounds.b: + %addr.b = getelementptr i32* %arr_b, i32 %idx + store i32 -1, i32* %addr.b + %next = icmp slt i32 %idx.next, %n + br i1 %next, label %loop, label %exit + + out.of.bounds: + ret void + + exit: + ret void +} + +; CHECK-LABEL: multiple_access_no_preloop + +; CHECK-LABEL: loop.preheader: +; CHECK: [[not_len_b:[^ ]+]] = sub i32 -1, %len.b +; CHECK: [[not_len_a:[^ ]+]] = sub i32 -1, %len.a +; CHECK: [[smax_not_len_cond:[^ ]+]] = icmp sgt i32 [[not_len_b]], [[not_len_a]] +; CHECK: [[smax_not_len:[^ ]+]] = select i1 [[smax_not_len_cond]], i32 [[not_len_b]], i32 [[not_len_a]] +; CHECK: [[not_n:[^ ]+]] = sub i32 -1, %n +; CHECK: [[not_upper_limit_cond_loclamp:[^ ]+]] = icmp sgt i32 [[smax_not_len]], [[not_n]] +; CHECK: [[not_upper_limit_loclamp:[^ ]+]] = select i1 [[not_upper_limit_cond_loclamp]], i32 [[smax_not_len]], i32 [[not_n]] +; CHECK: [[upper_limit_loclamp:[^ ]+]] = sub i32 -1, [[not_upper_limit_loclamp]] +; CHECK: [[upper_limit_cmp:[^ ]+]] = icmp sgt i32 [[upper_limit_loclamp]], 0 +; CHECK: [[upper_limit:[^ ]+]] = select i1 [[upper_limit_cmp]], i32 [[upper_limit_loclamp]], i32 0 + +; CHECK-LABEL: loop: +; CHECK: br i1 true, label %in.bounds.a, label %out.of.bounds + +; CHECK-LABEL: in.bounds.a: +; CHECK: br i1 true, label %in.bounds.b, label %out.of.bounds + +; CHECK-LABEL: in.bounds.b: +; CHECK: [[main_loop_cond:[^ ]+]] = icmp slt i32 %idx.next, [[upper_limit]] +; CHECK: br i1 [[main_loop_cond]], label %loop, label %main.exit.selector + +; CHECK-LABEL: in.bounds.b.postloop: +; CHECK: %next.postloop = icmp slt i32 %idx.next.postloop, %n +; CHECK: br i1 %next.postloop, label %loop.postloop, label %exit.loopexit + +!0 = !{i32 0, i32 2147483647} +!1 = !{!"branch_weights", i32 64, i32 4} diff --git a/test/Transforms/IRCE/not-likely-taken.ll b/test/Transforms/IRCE/not-likely-taken.ll new file mode 100644 index 0000000..c044530 --- /dev/null +++ b/test/Transforms/IRCE/not-likely-taken.ll @@ -0,0 +1,40 @@ +; RUN: opt -verify-loop-info -irce-print-changed-loops -irce < %s 2>&1 | FileCheck %s + +; CHECK-NOT: constrained Loop + +define void @multiple_access_no_preloop( + i32* %arr_a, i32* %a_len_ptr, i32* %arr_b, i32* %b_len_ptr, i32 %n) { + + entry: + %len.a = load i32* %a_len_ptr, !range !0 + %len.b = load i32* %b_len_ptr, !range !0 + %first.itr.check = icmp sgt i32 %n, 0 + br i1 %first.itr.check, label %loop, label %exit + + loop: + %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds.b ] + %idx.next = add i32 %idx, 1 + %abc.a = icmp slt i32 %idx, %len.a + br i1 %abc.a, label %in.bounds.a, label %out.of.bounds, !prof !1 + + in.bounds.a: + %addr.a = getelementptr i32* %arr_a, i32 %idx + store i32 0, i32* %addr.a + %abc.b = icmp slt i32 %idx, %len.b + br i1 %abc.b, label %in.bounds.b, label %out.of.bounds, !prof !1 + + in.bounds.b: + %addr.b = getelementptr i32* %arr_b, i32 %idx + store i32 -1, i32* %addr.b + %next = icmp slt i32 %idx.next, %n + br i1 %next, label %loop, label %exit + + out.of.bounds: + ret void + + exit: + ret void +} + +!0 = !{i32 0, i32 2147483647} +!1 = !{!"branch_weights", i32 1, i32 1}
\ No newline at end of file diff --git a/test/Transforms/IRCE/single-access-no-preloop.ll b/test/Transforms/IRCE/single-access-no-preloop.ll new file mode 100644 index 0000000..4d47ba8 --- /dev/null +++ b/test/Transforms/IRCE/single-access-no-preloop.ll @@ -0,0 +1,116 @@ +; RUN: opt -irce -S < %s | FileCheck %s + +define void @single_access_no_preloop_no_offset(i32 *%arr, i32 *%a_len_ptr, i32 %n) { + entry: + %len = load i32* %a_len_ptr, !range !0 + %first.itr.check = icmp sgt i32 %n, 0 + br i1 %first.itr.check, label %loop, label %exit + + loop: + %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ] + %idx.next = add i32 %idx, 1 + %abc = icmp slt i32 %idx, %len + br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !1 + + in.bounds: + %addr = getelementptr i32* %arr, i32 %idx + store i32 0, i32* %addr + %next = icmp slt i32 %idx.next, %n + br i1 %next, label %loop, label %exit + + out.of.bounds: + ret void + + exit: + ret void +} + +; CHECK-LABEL: single_access_no_preloop + +; CHECK-LABEL: loop: +; CHECK: br i1 true, label %in.bounds, label %out.of.bounds + +; CHECK-LABEL: main.exit.selector: +; CHECK-NEXT: [[continue:%[^ ]+]] = icmp slt i32 %idx.next, %n +; CHECK-NEXT: br i1 [[continue]], label %main.pseudo.exit, label %exit.loopexit + +; CHECK-LABEL: main.pseudo.exit: +; CHECK-NEXT: %idx.copy = phi i32 [ 0, %loop.preheader ], [ %idx.next, %main.exit.selector ] +; CHECK-NEXT: %indvar.end = phi i32 [ 0, %loop.preheader ], [ %idx.next, %main.exit.selector ] +; CHECK-NEXT: br label %postloop + +; CHECK-LABEL: postloop: +; CHECK-NEXT: br label %loop.postloop + +; CHECK-LABEL: loop.postloop: +; CHECK-NEXT: %idx.postloop = phi i32 [ %idx.next.postloop, %in.bounds.postloop ], [ %idx.copy, %postloop ] +; CHECK-NEXT: %idx.next.postloop = add i32 %idx.postloop, 1 +; CHECK-NEXT: %abc.postloop = icmp slt i32 %idx.postloop, %len +; CHECK-NEXT: br i1 %abc.postloop, label %in.bounds.postloop, label %out.of.bounds + +; CHECK-LABEL: in.bounds.postloop: +; CHECK-NEXT: %addr.postloop = getelementptr i32* %arr, i32 %idx.postloop +; CHECK-NEXT: store i32 0, i32* %addr.postloop +; CHECK-NEXT: %next.postloop = icmp slt i32 %idx.next.postloop, %n +; CHECK-NEXT: br i1 %next.postloop, label %loop.postloop, label %exit.loopexit + + +define void @single_access_no_preloop_with_offset(i32 *%arr, i32 *%a_len_ptr, i32 %n) { + entry: + %len = load i32* %a_len_ptr, !range !0 + %first.itr.check = icmp sgt i32 %n, 0 + br i1 %first.itr.check, label %loop, label %exit + + loop: + %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ] + %idx.next = add i32 %idx, 1 + %idx.for.abc = add i32 %idx, 4 + %abc = icmp slt i32 %idx.for.abc, %len + br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !1 + + in.bounds: + %addr = getelementptr i32* %arr, i32 %idx.for.abc + store i32 0, i32* %addr + %next = icmp slt i32 %idx.next, %n + br i1 %next, label %loop, label %exit + + out.of.bounds: + ret void + + exit: + ret void +} + +; CHECK-LABEL: single_access_no_preloop_with_offset + +; CHECK-LABEL: loop.preheader: +; CHECK: [[not_n:[^ ]+]] = sub i32 -1, %n +; CHECK: [[not_safe_range_end:[^ ]+]] = sub i32 3, %len +; CHECK: [[not_exit_main_loop_at_hiclamp_cmp:[^ ]+]] = icmp sgt i32 [[not_n]], [[not_safe_range_end]] +; CHECK: [[not_exit_main_loop_at_hiclamp:[^ ]+]] = select i1 [[not_exit_main_loop_at_hiclamp_cmp]], i32 [[not_n]], i32 [[not_safe_range_end]] +; CHECK: [[exit_main_loop_at_hiclamp:[^ ]+]] = sub i32 -1, [[not_exit_main_loop_at_hiclamp]] +; CHECK: [[exit_main_loop_at_loclamp_cmp:[^ ]+]] = icmp sgt i32 [[exit_main_loop_at_hiclamp]], 0 +; CHECK: [[exit_main_loop_at_loclamp:[^ ]+]] = select i1 [[exit_main_loop_at_loclamp_cmp]], i32 [[exit_main_loop_at_hiclamp]], i32 0 +; CHECK: [[enter_main_loop:[^ ]+]] = icmp slt i32 0, [[exit_main_loop_at_loclamp]] +; CHECK: br i1 [[enter_main_loop]], label %loop, label %main.pseudo.exit + +; CHECK-LABEL: loop: +; CHECK: br i1 true, label %in.bounds, label %out.of.bounds + +; CHECK-LABEL: in.bounds: +; CHECK: [[continue_main_loop:[^ ]+]] = icmp slt i32 %idx.next, [[exit_main_loop_at_loclamp]] +; CHECK: br i1 [[continue_main_loop]], label %loop, label %main.exit.selector + +; CHECK-LABEL: main.pseudo.exit: +; CHECK: %idx.copy = phi i32 [ 0, %loop.preheader ], [ %idx.next, %main.exit.selector ] +; CHECK: br label %postloop + +; CHECK-LABEL: loop.postloop: +; CHECK: %idx.postloop = phi i32 [ %idx.next.postloop, %in.bounds.postloop ], [ %idx.copy, %postloop ] + +; CHECK-LABEL: in.bounds.postloop: +; CHECK: %next.postloop = icmp slt i32 %idx.next.postloop, %n +; CHECK: br i1 %next.postloop, label %loop.postloop, label %exit.loopexit + +!0 = !{i32 0, i32 2147483647} +!1 = !{!"branch_weights", i32 64, i32 4} diff --git a/test/Transforms/IRCE/single-access-with-preloop.ll b/test/Transforms/IRCE/single-access-with-preloop.ll new file mode 100644 index 0000000..16426b8 --- /dev/null +++ b/test/Transforms/IRCE/single-access-with-preloop.ll @@ -0,0 +1,71 @@ +; RUN: opt -irce -S < %s | FileCheck %s + +define void @single_access_with_preloop(i32 *%arr, i32 *%a_len_ptr, i32 %n, i32 %offset) { + entry: + %len = load i32* %a_len_ptr, !range !0 + %first.itr.check = icmp sgt i32 %n, 0 + br i1 %first.itr.check, label %loop, label %exit + + loop: + %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ] + %idx.next = add i32 %idx, 1 + %array.idx = add i32 %idx, %offset + %abc.high = icmp slt i32 %array.idx, %len + %abc.low = icmp sge i32 %array.idx, 0 + %abc = and i1 %abc.low, %abc.high + br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !1 + + in.bounds: + %addr = getelementptr i32* %arr, i32 %array.idx + store i32 0, i32* %addr + %next = icmp slt i32 %idx.next, %n + br i1 %next, label %loop, label %exit + + out.of.bounds: + ret void + + exit: + ret void +} + +; CHECK-LABEL: loop.preheader: +; CHECK: [[not_safe_start:[^ ]+]] = add i32 %offset, -1 +; CHECK: [[not_n:[^ ]+]] = sub i32 -1, %n +; CHECK: [[not_exit_preloop_at_cond_loclamp:[^ ]+]] = icmp sgt i32 [[not_safe_start]], [[not_n]] +; CHECK: [[not_exit_preloop_at_loclamp:[^ ]+]] = select i1 [[not_exit_preloop_at_cond_loclamp]], i32 [[not_safe_start]], i32 [[not_n]] +; CHECK: [[exit_preloop_at_loclamp:[^ ]+]] = sub i32 -1, [[not_exit_preloop_at_loclamp]] +; CHECK: [[exit_preloop_at_cond:[^ ]+]] = icmp sgt i32 [[exit_preloop_at_loclamp]], 0 +; CHECK: [[exit_preloop_at:[^ ]+]] = select i1 [[exit_preloop_at_cond]], i32 [[exit_preloop_at_loclamp]], i32 0 + + +; CHECK: [[not_safe_start_2:[^ ]+]] = add i32 %offset, -1 +; CHECK: [[not_safe_end:[^ ]+]] = sub i32 [[not_safe_start_2]], %len +; CHECK: [[not_exit_mainloop_at_cond_loclamp:[^ ]+]] = icmp sgt i32 [[not_safe_end]], [[not_n]] +; CHECK: [[not_exit_mainloop_at_loclamp:[^ ]+]] = select i1 [[not_exit_mainloop_at_cond_loclamp]], i32 [[not_safe_end]], i32 [[not_n]] +; CHECK: [[exit_mainloop_at_loclamp:[^ ]+]] = sub i32 -1, [[not_exit_mainloop_at_loclamp]] +; CHECK: [[exit_mainloop_at_cmp:[^ ]+]] = icmp sgt i32 [[exit_mainloop_at_loclamp]], 0 +; CHECK: [[exit_mainloop_at:[^ ]+]] = select i1 [[exit_mainloop_at_cmp]], i32 [[exit_mainloop_at_loclamp]], i32 0 + + +; CHECK-LABEL: in.bounds: +; CHECK: [[continue_mainloop_cond:[^ ]+]] = icmp slt i32 %idx.next, [[exit_mainloop_at]] +; CHECK: br i1 [[continue_mainloop_cond]], label %loop, label %main.exit.selector + +; CHECK-LABEL: main.exit.selector: +; CHECK: [[mainloop_its_left:[^ ]+]] = icmp slt i32 %idx.next, %n +; CHECK: br i1 [[mainloop_its_left]], label %main.pseudo.exit, label %exit.loopexit + +; CHECK-LABEL: in.bounds.preloop: +; CHECK: [[continue_preloop_cond:[^ ]+]] = icmp slt i32 %idx.next.preloop, [[exit_preloop_at]] +; CHECK: br i1 [[continue_preloop_cond]], label %loop.preloop, label %preloop.exit.selector + +; CHECK-LABEL: preloop.exit.selector: +; CHECK: [[preloop_its_left:[^ ]+]] = icmp slt i32 %idx.next.preloop, %n +; CHECK: br i1 [[preloop_its_left]], label %preloop.pseudo.exit, label %exit.loopexit + +; CHECK-LABEL: in.bounds.postloop: +; CHECK: %next.postloop = icmp slt i32 %idx.next.postloop, %n +; CHECK: br i1 %next.postloop, label %loop.postloop, label %exit.loopexit + +!0 = !{i32 0, i32 2147483647} +!1 = !{!"branch_weights", i32 64, i32 4} diff --git a/test/Transforms/IRCE/unhandled.ll b/test/Transforms/IRCE/unhandled.ll new file mode 100644 index 0000000..3531c48 --- /dev/null +++ b/test/Transforms/IRCE/unhandled.ll @@ -0,0 +1,37 @@ +; RUN: opt -irce-print-changed-loops -irce -S < %s 2>&1 | FileCheck %s + +; Demonstrates that we don't currently handle the general expression +; `A * I + B'. + +define void @general_affine_expressions(i32 *%arr, i32 *%a_len_ptr, i32 %n, + i32 %scale, i32 %offset) { +; CHECK-NOT: constrained Loop at depth + entry: + %len = load i32* %a_len_ptr, !range !0 + %first.itr.check = icmp sgt i32 %n, 0 + br i1 %first.itr.check, label %loop, label %exit + + loop: + %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ] + %idx.next = add i32 %idx, 1 + %idx.mul = mul i32 %idx, %scale + %array.idx = add i32 %idx.mul, %offset + %abc.high = icmp slt i32 %array.idx, %len + %abc.low = icmp sge i32 %array.idx, 0 + %abc = and i1 %abc.low, %abc.high + br i1 %abc, label %in.bounds, label %out.of.bounds + + in.bounds: + %addr = getelementptr i32* %arr, i32 %array.idx + store i32 0, i32* %addr + %next = icmp slt i32 %idx.next, %n + br i1 %next, label %loop, label %exit + + out.of.bounds: + ret void + + exit: + ret void +} + +!0 = !{i32 0, i32 2147483647} diff --git a/test/Transforms/IRCE/with-parent-loops.ll b/test/Transforms/IRCE/with-parent-loops.ll new file mode 100644 index 0000000..f8d6c83 --- /dev/null +++ b/test/Transforms/IRCE/with-parent-loops.ll @@ -0,0 +1,345 @@ +; RUN: opt -verify-loop-info -irce-print-changed-loops -irce < %s 2>&1 | FileCheck %s + +; This test checks if we update the LoopInfo correctly in the presence +; of parents, uncles and cousins. + +; Function Attrs: alwaysinline +define void @inner_loop(i32* %arr, i32* %a_len_ptr, i32 %n) #0 { +; CHECK: irce: in function inner_loop: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting> + +entry: + %len = load i32* %a_len_ptr, !range !0 + %first.itr.check = icmp sgt i32 %n, 0 + br i1 %first.itr.check, label %loop, label %exit + +loop: ; preds = %in.bounds, %entry + %idx = phi i32 [ 0, %entry ], [ %idx.next, %in.bounds ] + %idx.next = add i32 %idx, 1 + %abc = icmp slt i32 %idx, %len + br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !1 + +in.bounds: ; preds = %loop + %addr = getelementptr i32* %arr, i32 %idx + store i32 0, i32* %addr + %next = icmp slt i32 %idx.next, %n + br i1 %next, label %loop, label %exit + +out.of.bounds: ; preds = %loop + ret void + +exit: ; preds = %in.bounds, %entry + ret void +} + +; Function Attrs: alwaysinline +define void @with_parent(i32* %arr, i32* %a_len_ptr, i32 %n, i32 %parent.count) #0 { +; CHECK: irce: in function with_parent: constrained Loop at depth 2 containing: %loop.i<header><exiting>,%in.bounds.i<latch><exiting> + +entry: + br label %loop + +loop: ; preds = %inner_loop.exit, %entry + %idx = phi i32 [ 0, %entry ], [ %idx.next, %inner_loop.exit ] + %idx.next = add i32 %idx, 1 + %next = icmp ult i32 %idx.next, %parent.count + %len.i = load i32* %a_len_ptr, !range !0 + %first.itr.check.i = icmp sgt i32 %n, 0 + br i1 %first.itr.check.i, label %loop.i, label %exit.i + +loop.i: ; preds = %in.bounds.i, %loop + %idx.i = phi i32 [ 0, %loop ], [ %idx.next.i, %in.bounds.i ] + %idx.next.i = add i32 %idx.i, 1 + %abc.i = icmp slt i32 %idx.i, %len.i + br i1 %abc.i, label %in.bounds.i, label %out.of.bounds.i, !prof !1 + +in.bounds.i: ; preds = %loop.i + %addr.i = getelementptr i32* %arr, i32 %idx.i + store i32 0, i32* %addr.i + %next.i = icmp slt i32 %idx.next.i, %n + br i1 %next.i, label %loop.i, label %exit.i + +out.of.bounds.i: ; preds = %loop.i + br label %inner_loop.exit + +exit.i: ; preds = %in.bounds.i, %loop + br label %inner_loop.exit + +inner_loop.exit: ; preds = %exit.i, %out.of.bounds.i + br i1 %next, label %loop, label %exit + +exit: ; preds = %inner_loop.exit + ret void +} + +; Function Attrs: alwaysinline +define void @with_grandparent(i32* %arr, i32* %a_len_ptr, i32 %n, i32 %parent.count, i32 %grandparent.count) #0 { +; CHECK: irce: in function with_grandparent: constrained Loop at depth 3 containing: %loop.i.i<header><exiting>,%in.bounds.i.i<latch><exiting> + +entry: + br label %loop + +loop: ; preds = %with_parent.exit, %entry + %idx = phi i32 [ 0, %entry ], [ %idx.next, %with_parent.exit ] + %idx.next = add i32 %idx, 1 + %next = icmp ult i32 %idx.next, %grandparent.count + br label %loop.i + +loop.i: ; preds = %inner_loop.exit.i, %loop + %idx.i = phi i32 [ 0, %loop ], [ %idx.next.i, %inner_loop.exit.i ] + %idx.next.i = add i32 %idx.i, 1 + %next.i = icmp ult i32 %idx.next.i, %parent.count + %len.i.i = load i32* %a_len_ptr, !range !0 + %first.itr.check.i.i = icmp sgt i32 %n, 0 + br i1 %first.itr.check.i.i, label %loop.i.i, label %exit.i.i + +loop.i.i: ; preds = %in.bounds.i.i, %loop.i + %idx.i.i = phi i32 [ 0, %loop.i ], [ %idx.next.i.i, %in.bounds.i.i ] + %idx.next.i.i = add i32 %idx.i.i, 1 + %abc.i.i = icmp slt i32 %idx.i.i, %len.i.i + br i1 %abc.i.i, label %in.bounds.i.i, label %out.of.bounds.i.i, !prof !1 + +in.bounds.i.i: ; preds = %loop.i.i + %addr.i.i = getelementptr i32* %arr, i32 %idx.i.i + store i32 0, i32* %addr.i.i + %next.i.i = icmp slt i32 %idx.next.i.i, %n + br i1 %next.i.i, label %loop.i.i, label %exit.i.i + +out.of.bounds.i.i: ; preds = %loop.i.i + br label %inner_loop.exit.i + +exit.i.i: ; preds = %in.bounds.i.i, %loop.i + br label %inner_loop.exit.i + +inner_loop.exit.i: ; preds = %exit.i.i, %out.of.bounds.i.i + br i1 %next.i, label %loop.i, label %with_parent.exit + +with_parent.exit: ; preds = %inner_loop.exit.i + br i1 %next, label %loop, label %exit + +exit: ; preds = %with_parent.exit + ret void +} + +; Function Attrs: alwaysinline +define void @with_sibling(i32* %arr, i32* %a_len_ptr, i32 %n, i32 %parent.count) #0 { +; CHECK: irce: in function with_sibling: constrained Loop at depth 2 containing: %loop.i<header><exiting>,%in.bounds.i<latch><exiting> +; CHECK: irce: in function with_sibling: constrained Loop at depth 2 containing: %loop.i6<header><exiting>,%in.bounds.i9<latch><exiting> + +entry: + br label %loop + +loop: ; preds = %inner_loop.exit12, %entry + %idx = phi i32 [ 0, %entry ], [ %idx.next, %inner_loop.exit12 ] + %idx.next = add i32 %idx, 1 + %next = icmp ult i32 %idx.next, %parent.count + %len.i = load i32* %a_len_ptr, !range !0 + %first.itr.check.i = icmp sgt i32 %n, 0 + br i1 %first.itr.check.i, label %loop.i, label %exit.i + +loop.i: ; preds = %in.bounds.i, %loop + %idx.i = phi i32 [ 0, %loop ], [ %idx.next.i, %in.bounds.i ] + %idx.next.i = add i32 %idx.i, 1 + %abc.i = icmp slt i32 %idx.i, %len.i + br i1 %abc.i, label %in.bounds.i, label %out.of.bounds.i, !prof !1 + +in.bounds.i: ; preds = %loop.i + %addr.i = getelementptr i32* %arr, i32 %idx.i + store i32 0, i32* %addr.i + %next.i = icmp slt i32 %idx.next.i, %n + br i1 %next.i, label %loop.i, label %exit.i + +out.of.bounds.i: ; preds = %loop.i + br label %inner_loop.exit + +exit.i: ; preds = %in.bounds.i, %loop + br label %inner_loop.exit + +inner_loop.exit: ; preds = %exit.i, %out.of.bounds.i + %len.i1 = load i32* %a_len_ptr, !range !0 + %first.itr.check.i2 = icmp sgt i32 %n, 0 + br i1 %first.itr.check.i2, label %loop.i6, label %exit.i11 + +loop.i6: ; preds = %in.bounds.i9, %inner_loop.exit + %idx.i3 = phi i32 [ 0, %inner_loop.exit ], [ %idx.next.i4, %in.bounds.i9 ] + %idx.next.i4 = add i32 %idx.i3, 1 + %abc.i5 = icmp slt i32 %idx.i3, %len.i1 + br i1 %abc.i5, label %in.bounds.i9, label %out.of.bounds.i10, !prof !1 + +in.bounds.i9: ; preds = %loop.i6 + %addr.i7 = getelementptr i32* %arr, i32 %idx.i3 + store i32 0, i32* %addr.i7 + %next.i8 = icmp slt i32 %idx.next.i4, %n + br i1 %next.i8, label %loop.i6, label %exit.i11 + +out.of.bounds.i10: ; preds = %loop.i6 + br label %inner_loop.exit12 + +exit.i11: ; preds = %in.bounds.i9, %inner_loop.exit + br label %inner_loop.exit12 + +inner_loop.exit12: ; preds = %exit.i11, %out.of.bounds.i10 + br i1 %next, label %loop, label %exit + +exit: ; preds = %inner_loop.exit12 + ret void +} + +; Function Attrs: alwaysinline +define void @with_cousin(i32* %arr, i32* %a_len_ptr, i32 %n, i32 %parent.count, i32 %grandparent.count) #0 { +; CHECK: irce: in function with_cousin: constrained Loop at depth 3 containing: %loop.i.i<header><exiting>,%in.bounds.i.i<latch><exiting> +; CHECK: irce: in function with_cousin: constrained Loop at depth 3 containing: %loop.i.i10<header><exiting>,%in.bounds.i.i13<latch><exiting> + +entry: + br label %loop + +loop: ; preds = %with_parent.exit17, %entry + %idx = phi i32 [ 0, %entry ], [ %idx.next, %with_parent.exit17 ] + %idx.next = add i32 %idx, 1 + %next = icmp ult i32 %idx.next, %grandparent.count + br label %loop.i + +loop.i: ; preds = %inner_loop.exit.i, %loop + %idx.i = phi i32 [ 0, %loop ], [ %idx.next.i, %inner_loop.exit.i ] + %idx.next.i = add i32 %idx.i, 1 + %next.i = icmp ult i32 %idx.next.i, %parent.count + %len.i.i = load i32* %a_len_ptr, !range !0 + %first.itr.check.i.i = icmp sgt i32 %n, 0 + br i1 %first.itr.check.i.i, label %loop.i.i, label %exit.i.i + +loop.i.i: ; preds = %in.bounds.i.i, %loop.i + %idx.i.i = phi i32 [ 0, %loop.i ], [ %idx.next.i.i, %in.bounds.i.i ] + %idx.next.i.i = add i32 %idx.i.i, 1 + %abc.i.i = icmp slt i32 %idx.i.i, %len.i.i + br i1 %abc.i.i, label %in.bounds.i.i, label %out.of.bounds.i.i, !prof !1 + +in.bounds.i.i: ; preds = %loop.i.i + %addr.i.i = getelementptr i32* %arr, i32 %idx.i.i + store i32 0, i32* %addr.i.i + %next.i.i = icmp slt i32 %idx.next.i.i, %n + br i1 %next.i.i, label %loop.i.i, label %exit.i.i + +out.of.bounds.i.i: ; preds = %loop.i.i + br label %inner_loop.exit.i + +exit.i.i: ; preds = %in.bounds.i.i, %loop.i + br label %inner_loop.exit.i + +inner_loop.exit.i: ; preds = %exit.i.i, %out.of.bounds.i.i + br i1 %next.i, label %loop.i, label %with_parent.exit + +with_parent.exit: ; preds = %inner_loop.exit.i + br label %loop.i6 + +loop.i6: ; preds = %inner_loop.exit.i16, %with_parent.exit + %idx.i1 = phi i32 [ 0, %with_parent.exit ], [ %idx.next.i2, %inner_loop.exit.i16 ] + %idx.next.i2 = add i32 %idx.i1, 1 + %next.i3 = icmp ult i32 %idx.next.i2, %parent.count + %len.i.i4 = load i32* %a_len_ptr, !range !0 + %first.itr.check.i.i5 = icmp sgt i32 %n, 0 + br i1 %first.itr.check.i.i5, label %loop.i.i10, label %exit.i.i15 + +loop.i.i10: ; preds = %in.bounds.i.i13, %loop.i6 + %idx.i.i7 = phi i32 [ 0, %loop.i6 ], [ %idx.next.i.i8, %in.bounds.i.i13 ] + %idx.next.i.i8 = add i32 %idx.i.i7, 1 + %abc.i.i9 = icmp slt i32 %idx.i.i7, %len.i.i4 + br i1 %abc.i.i9, label %in.bounds.i.i13, label %out.of.bounds.i.i14, !prof !1 + +in.bounds.i.i13: ; preds = %loop.i.i10 + %addr.i.i11 = getelementptr i32* %arr, i32 %idx.i.i7 + store i32 0, i32* %addr.i.i11 + %next.i.i12 = icmp slt i32 %idx.next.i.i8, %n + br i1 %next.i.i12, label %loop.i.i10, label %exit.i.i15 + +out.of.bounds.i.i14: ; preds = %loop.i.i10 + br label %inner_loop.exit.i16 + +exit.i.i15: ; preds = %in.bounds.i.i13, %loop.i6 + br label %inner_loop.exit.i16 + +inner_loop.exit.i16: ; preds = %exit.i.i15, %out.of.bounds.i.i14 + br i1 %next.i3, label %loop.i6, label %with_parent.exit17 + +with_parent.exit17: ; preds = %inner_loop.exit.i16 + br i1 %next, label %loop, label %exit + +exit: ; preds = %with_parent.exit17 + ret void +} + +; Function Attrs: alwaysinline +define void @with_uncle(i32* %arr, i32* %a_len_ptr, i32 %n, i32 %parent.count, i32 %grandparent.count) #0 { +; CHECK: irce: in function with_uncle: constrained Loop at depth 2 containing: %loop.i<header><exiting>,%in.bounds.i<latch><exiting> +; CHECK: irce: in function with_uncle: constrained Loop at depth 3 containing: %loop.i.i<header><exiting>,%in.bounds.i.i<latch><exiting> + +entry: + br label %loop + +loop: ; preds = %with_parent.exit, %entry + %idx = phi i32 [ 0, %entry ], [ %idx.next, %with_parent.exit ] + %idx.next = add i32 %idx, 1 + %next = icmp ult i32 %idx.next, %grandparent.count + %len.i = load i32* %a_len_ptr, !range !0 + %first.itr.check.i = icmp sgt i32 %n, 0 + br i1 %first.itr.check.i, label %loop.i, label %exit.i + +loop.i: ; preds = %in.bounds.i, %loop + %idx.i = phi i32 [ 0, %loop ], [ %idx.next.i, %in.bounds.i ] + %idx.next.i = add i32 %idx.i, 1 + %abc.i = icmp slt i32 %idx.i, %len.i + br i1 %abc.i, label %in.bounds.i, label %out.of.bounds.i, !prof !1 + +in.bounds.i: ; preds = %loop.i + %addr.i = getelementptr i32* %arr, i32 %idx.i + store i32 0, i32* %addr.i + %next.i = icmp slt i32 %idx.next.i, %n + br i1 %next.i, label %loop.i, label %exit.i + +out.of.bounds.i: ; preds = %loop.i + br label %inner_loop.exit + +exit.i: ; preds = %in.bounds.i, %loop + br label %inner_loop.exit + +inner_loop.exit: ; preds = %exit.i, %out.of.bounds.i + br label %loop.i4 + +loop.i4: ; preds = %inner_loop.exit.i, %inner_loop.exit + %idx.i1 = phi i32 [ 0, %inner_loop.exit ], [ %idx.next.i2, %inner_loop.exit.i ] + %idx.next.i2 = add i32 %idx.i1, 1 + %next.i3 = icmp ult i32 %idx.next.i2, %parent.count + %len.i.i = load i32* %a_len_ptr, !range !0 + %first.itr.check.i.i = icmp sgt i32 %n, 0 + br i1 %first.itr.check.i.i, label %loop.i.i, label %exit.i.i + +loop.i.i: ; preds = %in.bounds.i.i, %loop.i4 + %idx.i.i = phi i32 [ 0, %loop.i4 ], [ %idx.next.i.i, %in.bounds.i.i ] + %idx.next.i.i = add i32 %idx.i.i, 1 + %abc.i.i = icmp slt i32 %idx.i.i, %len.i.i + br i1 %abc.i.i, label %in.bounds.i.i, label %out.of.bounds.i.i, !prof !1 + +in.bounds.i.i: ; preds = %loop.i.i + %addr.i.i = getelementptr i32* %arr, i32 %idx.i.i + store i32 0, i32* %addr.i.i + %next.i.i = icmp slt i32 %idx.next.i.i, %n + br i1 %next.i.i, label %loop.i.i, label %exit.i.i + +out.of.bounds.i.i: ; preds = %loop.i.i + br label %inner_loop.exit.i + +exit.i.i: ; preds = %in.bounds.i.i, %loop.i4 + br label %inner_loop.exit.i + +inner_loop.exit.i: ; preds = %exit.i.i, %out.of.bounds.i.i + br i1 %next.i3, label %loop.i4, label %with_parent.exit + +with_parent.exit: ; preds = %inner_loop.exit.i + br i1 %next, label %loop, label %exit + +exit: ; preds = %with_parent.exit + ret void +} + +attributes #0 = { alwaysinline } + +!0 = !{i32 0, i32 2147483647} +!1 = !{!"branch_weights", i32 64, i32 4} |