[LoopPredication] Support ule, sle latch predicates

[apilipenko]

Summary

This is a follow up for the loop predication change D37569 to support ule, sle latch predicates.

[mkazantsev]

test/Transforms/LoopPredication/basic.ll

158

Consider case %n = 10, %length = -100. The original code will successfully pass through the guard (because 0 <u -100 is true) and then executes normally. After the loop is predicated, the condition icmp slt i32 %n, %length becomes false, and we don't go to the loop and deoptimize. Is it a problem?

[apilipenko]

test/Transforms/LoopPredication/basic.ll

158

From correctness standpoint it's OK since guards are allowed to fail spuriously.

As of why it is happening, we find the first value the guard will fail (-100) and then check that the backedge condition doesn't allow this value. We are not using the information about the backedge IV start, so we end up with an overly conservative check.

It should not be a problem in practice as long as your language doesn't use arrays longer that max signed int.

[mkazantsev]

LGTM.

lib/Transforms/Scalar/LoopPredication.cpp

 //
 //   So M = forall X . (G(X) && B(X + Step)) => G(X + Step) implies
 //   G(I + Step).
 //
 // Note that we can use anything stronger than M, i.e. any condition which
 // implies M.
 //
 // For now the transformation is limited to the following case:
-//   * The loop has a single latch with either ult or slt icmp condition.
+//   * The loop has a single latch with the condition of the form:
+//      ++i <pred> latchLimit, where <pred> is u<, u<=, s<, or s<=.
 //   * The step of the IV used in the latch condition is 1.
 //   * The IV of the latch condition is the same as the post increment IV of the
 //   guard condition.
-//   * The guard condition is ult.
+//   * The guard condition is
+//     i u< guardLimit.
 //
-// In this case the latch is of the from:
-//   ++i u< latchLimit or ++i s< latchLimit
-// and the guard is of the form:
-//   i u< guardLimit
-//
-// For the unsigned latch comparison case M is:
+// For the ult latch comparison case M is:
 //   forall X . X u< guardLimit && (X + 1) u< latchLimit =>
 //      (X + 1) u< guardLimit
 //
 // This is true if latchLimit u<= guardLimit since then
 //   (X + 1) u< latchLimit u<= guardLimit == (X + 1) u< guardLimit.
 //
-// So the widened condition is:
+// So for ult condition the widened condition is:
 //   i.start u< guardLimit && latchLimit u<= guardLimit
+// Similarly for ule condition the widened condition is:
+//   i.start u< guardLimit && latchLimit u< guardLimit
 //
 // For the signed latch comparison case M is:
 //   forall X . X u< guardLimit && (X + 1) s< latchLimit =>
 //      (X + 1) u< guardLimit
 //
 // The only way the antecedent can be true and the consequent can be false is 
 // if
 //   X == guardLimit - 1

 // == forall X . X u< guardLimit && (X + 1) s< guardLimit =>  (X + 1) u< guardLimit
 // == forall X . X in [0, guardLimit) && (X + 1) in [INT_MIN, guardLimit) =>  (X + 1) in [0, guardLimit)
 // == forall X . X in [0, guardLimit) && X in [INT_MAX, guardLimit-1) =>  X in [-1, guardLimit-1)
 // == forall X . X in [0, guardLimit-1) => X in [-1, guardLimit-1)
 // == true
 //
 // So the widened condition is:
 //   i.start u< guardLimit && latchLimit s<= guardLimit
+// Similarly for sle condition the widened condition is:
+//   i.start u< guardLimit && latchLimit s< guardLimit
 //
 //===----------------------------------------------------------------------===//
 
 #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"

 /// returns None.
 Optional<Value *> LoopPredication::widenICmpRangeCheck(ICmpInst *ICI,
                                                        SCEVExpander &Expander,
                                                        IRBuilder<> &Builder) {
   DEBUG(dbgs() << "Analyzing ICmpInst condition:\n");
   DEBUG(ICI->dump());
 
   // parseLoopStructure guarantees that the latch condition is:
-  //   ++i u< latchLimit or ++i s< latchLimit
+  //   ++i <pred> latchLimit, where <pred> is u<, u<=, s<, or s<=.
   // We are looking for the range checks of the form:
   //   i u< guardLimit
   auto RangeCheck = parseLoopICmp(ICI);
   if (!RangeCheck) {
     DEBUG(dbgs() << "Failed to parse the loop latch condition!\n");
     return None;
   }
   if (RangeCheck->Pred != ICmpInst::ICMP_ULT) {
     DEBUG(dbgs() << "Unsupported range check predicate(" << RangeCheck->Pred
                  << ")!\n");
     return None;
   }
   auto *RangeCheckIV = RangeCheck->IV;
   auto *PostIncRangeCheckIV = RangeCheckIV->getPostIncExpr(*SE);
   if (LatchCheck.IV != PostIncRangeCheckIV) {
     DEBUG(dbgs() << "Post increment range check IV (" << *PostIncRangeCheckIV
                  << ") is not the same as latch IV (" << *LatchCheck.IV
                  << ")!\n");
     return None;
   }
   assert(RangeCheckIV->getStepRecurrence(*SE)->isOne() && "must be one");
   const SCEV *Start = RangeCheckIV->getStart();
 
-  // Generate the widened condition. See the file header comment for reasoning.
-  // If the latch condition is unsigned:
-  //   i.start u< guardLimit && latchLimit u<= guardLimit
-  // If the latch condition is signed:
-  //   i.start u< guardLimit && latchLimit s<= guardLimit
-
-  auto LimitCheckPred = ICmpInst::isSigned(LatchCheck.Pred)
-                                           ? ICmpInst::ICMP_SLE
-                                           : ICmpInst::ICMP_ULE;
+  // Generate the widened condition:
+  //   i.start u< guardLimit && latchLimit <pred> guardLimit
+  // where <pred> depends on the latch condition predicate. See the file
+  // header comment for the reasoning.
+  ICmpInst::Predicate LimitCheckPred;
+  switch (LatchCheck.Pred) {
+  case ICmpInst::ICMP_ULT:
+    LimitCheckPred = ICmpInst::ICMP_ULE;
+    break;
+  case ICmpInst::ICMP_ULE:
+    LimitCheckPred = ICmpInst::ICMP_ULT;
+    break;
+  case ICmpInst::ICMP_SLT:
+    LimitCheckPred = ICmpInst::ICMP_SLE;
+    break;
+  case ICmpInst::ICMP_SLE:
+    LimitCheckPred = ICmpInst::ICMP_SLT;
+    break;
+  default:
+    llvm_unreachable("Unsupported loop latch!");
+  }
 
   auto CanExpand = [this](const SCEV *S) {
     return SE->isLoopInvariant(S, L) && isSafeToExpand(S, *SE);
   };
   if (!CanExpand(Start) || !CanExpand(LatchCheck.Limit) ||
       !CanExpand(RangeCheck->Limit))
     return None;
 
Optional<LoopPredication::LoopICmp> LoopPredication::parseLoopLatchICmp() {
 
   auto Result = parseLoopICmp(Pred, LHS, RHS);
   if (!Result) {
     DEBUG(dbgs() << "Failed to parse the loop latch condition!\n");
     return None;
   }
 
   if (Result->Pred != ICmpInst::ICMP_ULT &&
-      Result->Pred != ICmpInst::ICMP_SLT) {
+      Result->Pred != ICmpInst::ICMP_SLT &&
+      Result->Pred != ICmpInst::ICMP_ULE &&
+      Result->Pred != ICmpInst::ICMP_SLE) {
     DEBUG(dbgs() << "Unsupported loop latch predicate(" << Result->Pred
                  << ")!\n");
     return None;
   }
 
   // Check affine first, so if it's not we don't try to compute the step
   // recurrence.
   if (!Result->IV->isAffine()) {

test/Transforms/LoopPredication/basic.ll

; CHECK: call void (i1, ...) @llvm.experimental.guard(i1 [[wide_cond]], i32 9) [ "deopt"() ]
   %continue = icmp ult i32 %i.next, %n
   br i1 %continue, label %loop, label %exit
 
 exit:
   %result = phi i32 [ 0, %entry ], [ %loop.acc.next, %loop ]
   ret i32 %result
 }
 
+define i32 @unsigned_loop_0_to_n_ule_latch_ult_check(i32* %array, i32 %length, i32 %n) {
+; CHECK-LABEL: @unsigned_loop_0_to_n_ule_latch_ult_check
+entry:
+  %tmp5 = icmp eq i32 %n, 0
+  br i1 %tmp5, label %exit, label %loop.preheader
+
+loop.preheader:
+; CHECK: loop.preheader:
+; CHECK: [[first_iteration_check:[^ ]+]] = icmp ult i32 0, %length
+; CHECK-NEXT: [[limit_check:[^ ]+]] = icmp ult i32 %n, %length
+; CHECK-NEXT: [[wide_cond:[^ ]+]] = and i1 [[first_iteration_check]], [[limit_check]]
+; CHECK-NEXT: br label %loop
+  br label %loop
+
+loop:
+; CHECK: loop:
+; CHECK: call void (i1, ...) @llvm.experimental.guard(i1 [[wide_cond]], i32 9) [ "deopt"() ]
+  %loop.acc = phi i32 [ %loop.acc.next, %loop ], [ 0, %loop.preheader ]
+  %i = phi i32 [ %i.next, %loop ], [ 0, %loop.preheader ]
+  %within.bounds = icmp ult i32 %i, %length
+  call void (i1, ...) @llvm.experimental.guard(i1 %within.bounds, i32 9) [ "deopt"() ]
+
+  %i.i64 = zext i32 %i 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
+
+  %i.next = add nuw i32 %i, 1
+  %continue = icmp ule i32 %i.next, %n
+  br i1 %continue, label %loop, label %exit
+
+exit:
+  %result = phi i32 [ 0, %entry ], [ %loop.acc.next, %loop ]
+  ret i32 %result
+}
+
 define i32 @unsigned_loop_0_to_n_ugt_check(i32* %array, i32 %length, i32 %n) {
 ; CHECK-LABEL: @unsigned_loop_0_to_n_ugt_check
 entry:
   %tmp5 = icmp eq i32 %n, 0
   br i1 %tmp5, label %exit, label %loop.preheader
 
 loop.preheader:
 ; CHECK: loop.preheader:
; CHECK: call void (i1, ...) @llvm.experimental.guard(i1 [[wide_cond]], i32 9) [ "deopt"() ]
   %continue = icmp slt i32 %i.next, %n
   br i1 %continue, label %loop, label %exit
 
 exit:
   %result = phi i32 [ 0, %entry ], [ %loop.acc.next, %loop ]
   ret i32 %result
 }
 
+define i32 @signed_loop_0_to_n_inverse_latch_predicate(i32* %array, i32 %length, i32 %n) {
+; CHECK-LABEL: @signed_loop_0_to_n_inverse_latch_predicate
+entry:
+  %tmp5 = icmp sle i32 %n, 0
+  br i1 %tmp5, label %exit, label %loop.preheader
+
+loop.preheader:
+; CHECK: loop.preheader:
+; CHECK: [[first_iteration_check:[^ ]+]] = icmp ult i32 0, %length
+; CHECK-NEXT: [[limit_check:[^ ]+]] = icmp slt i32 %n, %length
+; CHECK-NEXT: [[wide_cond:[^ ]+]] = and i1 [[first_iteration_check]], [[limit_check]]
+; CHECK-NEXT: br label %loop
+  br label %loop
+
+loop:
+; CHECK: loop:
+; CHECK: call void (i1, ...) @llvm.experimental.guard(i1 [[wide_cond]], i32 9) [ "deopt"() ]
+  %loop.acc = phi i32 [ %loop.acc.next, %loop ], [ 0, %loop.preheader ]
+  %i = phi i32 [ %i.next, %loop ], [ 0, %loop.preheader ]
+  %within.bounds = icmp ult i32 %i, %length
+  call void (i1, ...) @llvm.experimental.guard(i1 %within.bounds, i32 9) [ "deopt"() ]
+
+  %i.i64 = zext i32 %i 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
+
+  %i.next = add nuw i32 %i, 1
+  %continue = icmp sgt i32 %i.next, %n
+  br i1 %continue, label %exit, label %loop
+
+exit:
+  %result = phi i32 [ 0, %entry ], [ %loop.acc.next, %loop ]
+  ret i32 %result
+}
+
+define i32 @signed_loop_0_to_n_sle_latch_ult_check(i32* %array, i32 %length, i32 %n) {
+; CHECK-LABEL: @signed_loop_0_to_n_sle_latch_ult_check
+entry:
+  %tmp5 = icmp sle i32 %n, 0
+  br i1 %tmp5, label %exit, label %loop.preheader
+
+loop.preheader:
+; CHECK: loop.preheader:
+; CHECK: [[first_iteration_check:[^ ]+]] = icmp ult i32 0, %length
+; CHECK-NEXT: [[limit_check:[^ ]+]] = icmp slt i32 %n, %length
+; CHECK-NEXT: [[wide_cond:[^ ]+]] = and i1 [[first_iteration_check]], [[limit_check]]
+; CHECK-NEXT: br label %loop
+  br label %loop
+
+loop:
+; CHECK: loop:
+; CHECK: call void (i1, ...) @llvm.experimental.guard(i1 [[wide_cond]], i32 9) [ "deopt"() ]
+  %loop.acc = phi i32 [ %loop.acc.next, %loop ], [ 0, %loop.preheader ]
+  %i = phi i32 [ %i.next, %loop ], [ 0, %loop.preheader ]
+  %within.bounds = icmp ult i32 %i, %length
+  call void (i1, ...) @llvm.experimental.guard(i1 %within.bounds, i32 9) [ "deopt"() ]
+
+  %i.i64 = zext i32 %i 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
+
+  %i.next = add nuw i32 %i, 1
+  %continue = icmp sle i32 %i.next, %n
+  br i1 %continue, label %loop, label %exit
+
+exit:
+  %result = phi i32 [ 0, %entry ], [ %loop.acc.next, %loop ]
+  ret i32 %result
+}
+
 define i32 @unsupported_latch_pred_loop_0_to_n(i32* %array, i32 %length, i32 %n) {
 ; CHECK-LABEL: @unsupported_latch_pred_loop_0_to_n
 entry:
   %tmp5 = icmp sle i32 %n, 0
   br i1 %tmp5, label %exit, label %loop.preheader
 
 loop.preheader:
 ; CHECK: loop.preheader: