Add a new pass "inductive range check elimination"

IRCE eliminates range checks of the form

  0 <= A * I + B < Length

by splitting a loop's iteration space into three segments in a way
that the check is completely redundant in the middle segment.  As an
example, IRCE will convert

  len = < known positive >
  for (i = 0; i < n; i++) {
    if (0 <= i && i < len) {
      do_something();
    } else {
      throw_out_of_bounds();
    }
  }

to

  len = < known positive >
  limit = smin(n, len)
  // no first segment
  for (i = 0; i < limit; i++) {
    if (0 <= i && i < len) { // this check is fully redundant
      do_something();
    } else {
      throw_out_of_bounds();
    }
  }
  for (i = limit; i < n; i++) {
    if (0 <= i && i < len) {
      do_something();
    } else {
      throw_out_of_bounds();
    }
  }


IRCE can deal with multiple range checks in the same loop (it takes
the intersection of the ranges that will make each of them redundant
individually).

Currently IRCE does not do any profitability analysis.  That is a
TODO.

Please note that the status of this pass is *experimental*, and it is
not part of any default pass pipeline.  Having said that, I will love
to get feedback and general input from people interested in trying
this out.

Differential Revision: http://reviews.llvm.org/D6693

llvm-svn: 226201

5 files changed, 609 insertions, 0 deletions

diff --git a/llvm/test/Transforms/IRCE/multiple-access-no-preloop.ll b/llvm/test/Transforms/IRCE/multiple-access-no-preloop.ll
new file mode 100644
index 00000000000..56b7b7b6c65
--- /dev/null
+++ b/llvm/test/Transforms/IRCE/multiple-access-no-preloop.ll
@@ -0,0 +1,59 @@
+; 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
+
+ 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
+
+ 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: [[smaller_len_cmp:[^ ]+]] = icmp slt i32 %len.a, %len.b
+; CHECK: [[smaller_len:[^ ]+]] = select i1 [[smaller_len_cmp]], i32 %len.a, i32 %len.b
+; CHECK: [[upper_bound_cmp:[^ ]+]] = icmp slt i32 %n, %3
+; CHECK: [[upper_bound:[^ ]+]] = select i1 %5, i32 %n, i32 %3
+
+; 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_bound]]
+; 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}
diff --git a/llvm/test/Transforms/IRCE/single-access-no-preloop.ll b/llvm/test/Transforms/IRCE/single-access-no-preloop.ll
new file mode 100644
index 00000000000..cf073b359a7
--- /dev/null
+++ b/llvm/test/Transforms/IRCE/single-access-no-preloop.ll
@@ -0,0 +1,110 @@
+; 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
+
+ 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: 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
+
+ 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: [[safe_range_end:[^ ]+]] = sub i32 %len, 4
+; CHECK: [[exit_main_loop_at_cmp:[^ ]+]] = icmp slt i32 %n, [[safe_range_end]]
+; CHECK: [[exit_main_loop_at:[^ ]+]] = select i1 [[exit_main_loop_at_cmp]], i32 %n, i32 [[safe_range_end]]
+; CHECK: [[enter_main_loop:[^ ]+]] = icmp slt i32 0, [[exit_main_loop_at]]
+; 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]]
+; 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}
diff --git a/llvm/test/Transforms/IRCE/single-access-with-preloop.ll b/llvm/test/Transforms/IRCE/single-access-with-preloop.ll
new file mode 100644
index 00000000000..6775d335a04
--- /dev/null
+++ b/llvm/test/Transforms/IRCE/single-access-with-preloop.ll
@@ -0,0 +1,59 @@
+; 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
+
+ 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: [[safe_start:[^ ]+]] = sub i32 0, %offset
+; CHECK: [[safe_end:[^ ]+]] = sub i32 %len, %offset
+; CHECK: [[exit_preloop_at_cond:[^ ]+]] = icmp slt i32 %n, [[safe_start]]
+; CHECK: [[exit_preloop_at:[^ ]+]] = select i1 [[exit_preloop_at_cond]], i32 %n, i32 [[safe_start]]
+; CHECK: [[exit_mainloop_at_cond:[^ ]+]] = icmp slt i32 %n, [[safe_end]]
+; CHECK: [[exit_mainloop_at:[^ ]+]] = select i1 [[exit_mainloop_at_cond]], i32 %n, i32 [[safe_end]]
+
+; 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}
diff --git a/llvm/test/Transforms/IRCE/unhandled.ll b/llvm/test/Transforms/IRCE/unhandled.ll
new file mode 100644
index 00000000000..3531c482ba5
--- /dev/null
+++ b/llvm/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/llvm/test/Transforms/IRCE/with-parent-loops.ll b/llvm/test/Transforms/IRCE/with-parent-loops.ll
new file mode 100644
index 00000000000..25dfb133f54
--- /dev/null
+++ b/llvm/test/Transforms/IRCE/with-parent-loops.ll
@@ -0,0 +1,344 @@
+; 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
+
+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
+
+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
+
+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
+
+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
+
+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
+
+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
+
+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
+
+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
+
+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}