[Loop Predication] Teach LP about reverse loops with uge and sge latch conditions

Add support of uge and sge latch condition to Loop Prediction for
reverse loops.

Reviewers: apilipenko, mkazantsev, sanjoy, anna
Reviewed By: anna
Subscribers: llvm-commits
Differential Revision: https://reviews.llvm.org/D42837

llvm-svn: 324589

1 files changed, 105 insertions, 0 deletions

diff --git a/llvm/test/Transforms/LoopPredication/reverse.ll b/llvm/test/Transforms/LoopPredication/reverse.ll
index b8da664fc84..3d695d1b4ff 100644
--- a/llvm/test/Transforms/LoopPredication/reverse.ll
+++ b/llvm/test/Transforms/LoopPredication/reverse.ll
@@ -138,3 +138,108 @@ exit:
   %result = phi i32 [ 0, %entry ], [ %loop.acc.next, %loop ]
   ret i32 %result
 }
+
+define i32 @signed_reverse_loop_n_to_lower_limit_equal(i32* %array, i32 %length, i32 %n, i32 %lowerlimit) {
+; CHECK-LABEL: @signed_reverse_loop_n_to_lower_limit_equal(
+entry:
+  %tmp5 = icmp eq i32 %n, 0
+  br i1 %tmp5, label %exit, label %loop.preheader
+
+; CHECK:       loop.preheader:
+; CHECK-NEXT:    [[range_start:%.*]] = add i32 %n, -1
+; CHECK-NEXT:    [[first_iteration_check:%.*]] = icmp ult i32 [[range_start]], %length
+; CHECK-NEXT:    [[no_wrap_check:%.*]] = icmp sgt i32 %lowerlimit, 1
+; CHECK-NEXT:    [[wide_cond:%.*]] = and i1 [[first_iteration_check]], [[no_wrap_check]]
+loop.preheader:
+  br label %loop
+
+; CHECK: loop:
+; CHECK:    call void (i1, ...) @llvm.experimental.guard(i1 [[wide_cond]], i32 9) [ "deopt"() ]
+loop:
+  %loop.acc = phi i32 [ %loop.acc.next, %loop ], [ 0, %loop.preheader ]
+  %i = phi i32 [ %i.next, %loop ], [ %n, %loop.preheader ]
+  %i.next = add nsw i32 %i, -1
+  %within.bounds = icmp ult i32 %i.next, %length
+  call void (i1, ...) @llvm.experimental.guard(i1 %within.bounds, i32 9) [ "deopt"() ]
+  %i.i64 = zext i32 %i.next to i64
+  %array.i.ptr = getelementptr inbounds i32, i32* %array, i64 %i.i64
+  %array.i = load i32, i32* %array.i.ptr, align 4
+  %loop.acc.next = add i32 %loop.acc, %array.i
+  %continue = icmp sge i32 %i, %lowerlimit
+  br i1 %continue, label %loop, label %exit
+
+exit:
+  %result = phi i32 [ 0, %entry ], [ %loop.acc.next, %loop ]
+  ret i32 %result
+}
+
+define i32 @unsigned_reverse_loop_n_to_lower_limit_equal(i32* %array, i32 %length, i32 %n, i32 %lowerlimit) {
+; CHECK-LABEL: @unsigned_reverse_loop_n_to_lower_limit_equal(
+entry:
+  %tmp5 = icmp eq i32 %n, 0
+  br i1 %tmp5, label %exit, label %loop.preheader
+
+; CHECK:       loop.preheader:
+; CHECK-NEXT:    [[range_start:%.*]] = add i32 %n, -1
+; CHECK-NEXT:    [[first_iteration_check:%.*]] = icmp ult i32 [[range_start]], %length
+; CHECK-NEXT:    [[no_wrap_check:%.*]] = icmp ugt i32 %lowerlimit, 1
+; CHECK-NEXT:    [[wide_cond:%.*]] = and i1 [[first_iteration_check]], [[no_wrap_check]]
+loop.preheader:
+  br label %loop
+
+; CHECK: loop:
+; CHECK:    call void (i1, ...) @llvm.experimental.guard(i1 [[wide_cond]], i32 9) [ "deopt"() ]
+loop:
+  %loop.acc = phi i32 [ %loop.acc.next, %loop ], [ 0, %loop.preheader ]
+  %i = phi i32 [ %i.next, %loop ], [ %n, %loop.preheader ]
+  %i.next = add nsw i32 %i, -1
+  %within.bounds = icmp ult i32 %i.next, %length
+  call void (i1, ...) @llvm.experimental.guard(i1 %within.bounds, i32 9) [ "deopt"() ]
+  %i.i64 = zext i32 %i.next to i64
+  %array.i.ptr = getelementptr inbounds i32, i32* %array, i64 %i.i64
+  %array.i = load i32, i32* %array.i.ptr, align 4
+  %loop.acc.next = add i32 %loop.acc, %array.i
+  %continue = icmp uge i32 %i, %lowerlimit
+  br i1 %continue, label %loop, label %exit
+
+exit:
+  %result = phi i32 [ 0, %entry ], [ %loop.acc.next, %loop ]
+  ret i32 %result
+}
+
+
+; if we predicated the loop, the guard will definitely fail and we will
+; deoptimize early on.
+define i32 @unsigned_reverse_loop_n_to_1(i32* %array, i32 %length, i32 %n, i32 %lowerlimit) {
+; CHECK-LABEL: @unsigned_reverse_loop_n_to_1(
+entry:
+  %tmp5 = icmp eq i32 %n, 0
+  br i1 %tmp5, label %exit, label %loop.preheader
+
+; CHECK:       loop.preheader:
+; CHECK-NEXT:    [[range_start:%.*]] = add i32 %n, -1
+; CHECK-NEXT:    [[first_iteration_check:%.*]] = icmp ult i32 [[range_start]], %length
+; CHECK-NEXT:    [[wide_cond:%.*]] = and i1 [[first_iteration_check]], false
+loop.preheader:
+  br label %loop
+
+; CHECK: loop:
+; CHECK:    call void (i1, ...) @llvm.experimental.guard(i1 [[wide_cond]], i32 9) [ "deopt"() ]
+loop:
+  %loop.acc = phi i32 [ %loop.acc.next, %loop ], [ 0, %loop.preheader ]
+  %i = phi i32 [ %i.next, %loop ], [ %n, %loop.preheader ]
+  %i.next = add nsw i32 %i, -1
+  %within.bounds = icmp ult i32 %i.next, %length
+  call void (i1, ...) @llvm.experimental.guard(i1 %within.bounds, i32 9) [ "deopt"() ]
+  %i.i64 = zext i32 %i.next to i64
+  %array.i.ptr = getelementptr inbounds i32, i32* %array, i64 %i.i64
+  %array.i = load i32, i32* %array.i.ptr, align 4
+  %loop.acc.next = add i32 %loop.acc, %array.i
+  %continue = icmp uge i32 %i, 1
+  br i1 %continue, label %loop, label %exit
+
+exit:
+  %result = phi i32 [ 0, %entry ], [ %loop.acc.next, %loop ]
+  ret i32 %result
+}
+