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

[skatkov]

Summary

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

[anna]

lib/Transforms/Scalar/LoopPredication.cpp

451 ↗

(On Diff #132550)

pls land this as a separate NFC after separating out getLatchPredicateForGuard.

[skatkov]

Please take a look.

[anna]

LGTM.
Btw, I actually meant separating out getLatchPredicateForGuard as NFC for just the conditions supported without this change (i.e. everything except SGE, UGE).
Then, in this change, adding support for UGE and SGE in that function and in IsUnsupportedPredicate, so that only changes related to SGE/UGE are in this patch :)

llvm/trunk/lib/Transforms/Scalar/LoopPredication.cpp

 //     latchStart + guardLimit - 1 - guardStart s>= latchLimit
 //   For sle condition the widened condition is:
 //     guardStart u< guardLimit &&
 //     latchStart + guardLimit - 1 - guardStart s> latchLimit
 //
 // When S = -1 (i.e. reverse iterating loop), the transformation is supported
 // when:
 //   * The loop has a single latch with the condition of the form:
-//     B(X) = X <pred> latchLimit, where <pred> is u> or s>.
+//     B(X) = X <pred> latchLimit, where <pred> is u>, u>=, s>, or s>=.
 //   * The guard condition is of the form
 //     G(X) = X - 1 u< guardLimit
 //
 //   For the ugt latch comparison case M is:
 //     forall X. X-1 u< guardLimit and X u> latchLimit => X-2 u< guardLimit
 //
 //   The only way the antecedent can be true and the consequent can be false is if
 //     X == 1.
 //   If X == 1 then the second half of the antecedent is
 //     1 u> latchLimit, and its negation is latchLimit u>= 1.
 //
 //   So the widened condition is:
 //     guardStart u< guardLimit && latchLimit u>= 1.
 //   Similarly for sgt condition the widened condition is:
 //     guardStart u< guardLimit && latchLimit s>= 1.
+//   For uge condition the widened condition is:
+//     guardStart u< guardLimit && latchLimit u> 1.
+//   For sge condition the widened condition is:
+//     guardStart u< guardLimit && latchLimit s> 1.
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar/LoopPredication.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionExpander.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
if (RangeCheck.IV != PostDecLatchCheckIV) {
     return None;
   }
 
   // Generate the widened condition for CountDownLoop:
   // guardStart u< guardLimit &&
   // latchLimit <pred> 1.
   // See the header comment for reasoning of the checks.
   Instruction *InsertAt = Preheader->getTerminator();
-  auto LimitCheckPred = ICmpInst::isSigned(LatchCheck.Pred)
-                            ? ICmpInst::ICMP_SGE
-                            : ICmpInst::ICMP_UGE;
+  auto LimitCheckPred = getLatchPredicateForGuard(LatchCheck.Pred);
   auto *FirstIterationCheck = expandCheck(Expander, Builder, ICmpInst::ICMP_ULT,
                                           GuardStart, GuardLimit, InsertAt);
   auto *LimitCheck = expandCheck(Expander, Builder, LimitCheckPred, LatchLimit,
                                  SE->getOne(Ty), InsertAt);
   return Builder.CreateAnd(FirstIterationCheck, LimitCheck);
 }
 
 /// If ICI can be widened to a loop invariant condition emits the loop
Optional<LoopPredication::LoopICmp> LoopPredication::parseLoopLatchICmp() {
   }
 
   auto IsUnsupportedPredicate = [](const SCEV *Step, ICmpInst::Predicate Pred) {
     if (Step->isOne()) {
       return Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_SLT &&
              Pred != ICmpInst::ICMP_ULE && Pred != ICmpInst::ICMP_SLE;
     } else {
       assert(Step->isAllOnesValue() && "Step should be -1!");
-      return Pred != ICmpInst::ICMP_UGT && Pred != ICmpInst::ICMP_SGT;
+      return Pred != ICmpInst::ICMP_UGT && Pred != ICmpInst::ICMP_SGT &&
+             Pred != ICmpInst::ICMP_UGE && Pred != ICmpInst::ICMP_SGE;
     }
   };
 
   if (IsUnsupportedPredicate(Step, Result->Pred)) {
     DEBUG(dbgs() << "Unsupported loop latch predicate(" << Result->Pred
                  << ")!\n");
     return None;
   }

llvm/trunk/test/Transforms/LoopPredication/reverse.ll

loop:
   %loop.acc.next = add i32 %loop.acc, %array.i
   %continue = icmp ugt i32 %i, 65534
   br i1 %continue, label %loop, label %exit
 
 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
+}
+