[IRCE] Only check for NSW on equality predicates

[samparker]

Summary

After investigation discussed in D45439, it would seem that the nsw flag restriction is unnecessary in most cases. So the IsInductionVar lambda has been removed, the functionality extracted, and now only require nsw when using eq/ne predicates.

[mkazantsev]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

933 ↗

(On Diff #142378)

How about non-constant steps?

[mkazantsev]

For me it looks fine, but please let me run some tests with this patch. I don't see obvious problem, and if they aren't revealed by this testing, I'll give my approval. It will take few hours.

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

933 ↗

(On Diff #142378)

Never mind, it's checked above. Could have been a dyn_cast on line 923.

[mkazantsev]

test/Transforms/IRCE/stride_more_than_1.ll

221 ↗

(On Diff #142378)

Will you please add a check that the postloop is generated? It looks like we should have one here, am I correct?

[mkazantsev]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

923 ↗

(On Diff #142378)

Please do affinity check first and take StepRecurrence only if it passes, it will save you some compile time on non-affine phis. Also can be dyn_cast.

[mkazantsev]

My tasting has passed. LGTM with minor changes (comments inline).

[samparker]

test/Transforms/IRCE/stride_more_than_1.ll

221 ↗

(On Diff #142378)

sure. you're correct.

[mkazantsev]

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

928

Hi Sam, there is a bug here. dyn_cast may return nullptr and then we still access it, which is UB. I've fixed it in https://reviews.llvm.org/rL331508. Please review post-commit if you can.

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

if (ExtendAfterOp) {
       if (NoSignedWrap)
         return true;
     }
 
     // We may have proved this when computing the sign extension above.
     return AR->getNoWrapFlags(SCEV::FlagNSW) != SCEV::FlagAnyWrap;
   };
 
-  // Here we check whether the suggested AddRec is an induction variable that
-  // can be handled (i.e. with known constant step), and if yes, calculate its
-  // step and identify whether it is increasing or decreasing.
-  auto IsInductionVar = [&](const SCEVAddRecExpr *AR, bool &IsIncreasing,
-                            ConstantInt *&StepCI) {
-    if (!AR->isAffine())
-      return false;
-
-    // Currently we only work with induction variables that have been proved to
-    // not wrap.  This restriction can potentially be lifted in the future.
-
-    if (!HasNoSignedWrap(AR))
-      return false;
-
-    if (const SCEVConstant *StepExpr =
-            dyn_cast<SCEVConstant>(AR->getStepRecurrence(SE))) {
-      StepCI = StepExpr->getValue();
-      assert(!StepCI->isZero() && "Zero step?");
-      IsIncreasing = !StepCI->isNegative();
-      return true;
-    }
-
-    return false;
-  };
-
   // `ICI` is interpreted as taking the backedge if the *next* value of the
   // induction variable satisfies some constraint.
 
   const SCEVAddRecExpr *IndVarBase = cast<SCEVAddRecExpr>(LeftSCEV);
-  bool IsIncreasing = false;
-  bool IsSignedPredicate = true;
-  ConstantInt *StepCI;
-  if (!IsInductionVar(IndVarBase, IsIncreasing, StepCI)) {
+  if (!IndVarBase->isAffine()) {
     FailureReason = "LHS in icmp not induction variable";
     return None;
   }
+  const SCEV* StepRec = IndVarBase->getStepRecurrence(SE);
+  ConstantInt *StepCI = dyn_cast<SCEVConstant>(StepRec)->getValue();
+  if (!StepCI) {
+    FailureReason = "LHS in icmp not induction variable";
+    return None;
+  }
+  if (ICI->isEquality() && !HasNoSignedWrap(IndVarBase)) {
+    FailureReason = "LHS in icmp needs nsw for equality predicates";
+    return None;
+  }
 
+  assert(!StepCI->isZero() && "Zero step?");
+  bool IsIncreasing = !StepCI->isNegative();
+  bool IsSignedPredicate = ICmpInst::isSigned(Pred);
   const SCEV *StartNext = IndVarBase->getStart();
   const SCEV *Addend = SE.getNegativeSCEV(IndVarBase->getStepRecurrence(SE));
   const SCEV *IndVarStart = SE.getAddExpr(StartNext, Addend);
   const SCEV *Step = SE.getSCEV(StepCI);
 
   ConstantInt *One = ConstantInt::get(IndVarTy, 1);
   if (IsIncreasing) {
     bool DecreasedRightValueByOne = false;

llvm/trunk/test/Transforms/IRCE/stride_more_than_1.ll

 ; RUN: opt -verify-loop-info -irce-print-changed-loops -irce -S < %s 2>&1 | FileCheck %s
 ; RUN: opt -verify-loop-info -irce-print-changed-loops -passes='require<branch-prob>,loop(irce)' -S < %s 2>&1 | FileCheck %s
 
 ; CHECK: irce: in function test_01: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
 ; CHECK: irce: in function test_02: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
 ; CHECK: irce: in function test_03: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
-; CHECK-NOT: irce: in function test_04: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
+; CHECK: irce: in function test_04: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
 ; CHECK: irce: in function test_05: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
 ; CHECK: irce: in function test_06: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
 ; CHECK-NOT: irce: in function test_07: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
 ; CHECK: irce: in function test_08: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
 
 ; IV = 0; IV <s 100; IV += 7; 0 <= Len <= 50. IRCE is allowed.
 define void @test_01(i32* %arr, i32* %a_len_ptr) {
 

 
 out.of.bounds:
   ret void
 
 exit:
   ret void
 }
 
-; IV = 0; IV <s MAX_INT; IV += 7; 0 <= Len <= MAX_INT - 6. IRCE is not allowed,
-; because we cannot guarantee that IV + 7 will not exceed MAX_INT.
-; Negative test.
+; IV = 0; IV <s MAX_INT; IV += 7; 0 <= Len <= MAX_INT - 6. IRCE is allowed
+; because the branch would fail once idx.next == MAX_INT - 1 keeping the
+; access in bounds.
 define void @test_04(i32* %arr, i32* %a_len_ptr) {
-
-; CHECK:      @test_04(
+  ; CHECK:  @test_04(
+  ; CHECK:  loop:
+  ; CHECK:  [[IV:%[^ ]+]] = phi i32
+  ; CHECK:  [[IDX_NEXT:%[^ ]+]] = add i32 [[IV]], 7
+
+  ; CHECK:  main.exit.selector:
+  ; CHECK:  [[PSEUDO_PHI:%[^ ]+]] =  phi i32 [ [[IDX_NEXT]], %in.bounds ]
+  ; CHECK:  [[COND:%[^ ]+]] = icmp slt i32 [[PSEUDO_PHI]], 2147483647
+  ; CHECK:  br i1 [[COND]], label %main.pseudo.exit, label %exit
+
+  ; CHECK: loop.postloop:
+  ; CHECK: [[IDX_POST:%[^ ]+]] = phi i32
+  ; CHECK: [[COND_POST:%[^ ]+]] = icmp slt i32 [[IDX_POST]], %exit.mainloop.at
+  ; CHECK: br i1 [[COND_POST]], label %in.bounds.postloop, label %out.of.bounds.loopexit
 
 entry:
   %len = load i32, i32* %a_len_ptr, !range !2
   br label %loop
 
 loop:
   %idx = phi i32 [ 0, %entry ], [ %idx.next, %in.bounds ]
   %idx.next = add i32 %idx, 7