[IRCE] Add tests for conservative bound check

[jaykang10]

Summary

Prevent cases in which the start value of IV is bigger than bound for increasing or the start value of IV is smaller than bound for decreasing.

[samparker]

Hi,

I think this looks fine to me, and now I'm trying to remember what the difference was which these functions and cannotBe[Min/Max]InLoop. Have you looked into using these?

[jaykang10]

In D101174#2716329, @samparker wrote:

Hi,

I think this looks fine to me, and now I'm trying to remember what the difference was which these functions and cannotBe[Min/Max]InLoop. Have you looked into using these?

Hi Sam,

For increasing, it looked the cannotBeMinInLoop checks bound > min and isSafeIncreasingBound checks start < bound < limit.

For Decreasing, the cannotBeMaxInLoop checks bound < max and isSafeDecreasingBound checks limit < bound < start.

They check different thing such as lower bound/upper bound and vice versa.

I thought it is ok to keep the two functions.

If I missed something, please let me know.

[samparker]

Okay, thanks. Could you just add a couple more tests then, so that we cover steps other than one. Also, if they don't exist already, a couple of tests where the start value is already at the limit.

[jaykang10]

Following comments of @samparker, added test cases.

[jaykang10]

@samparker I have added more tests. Please check it.

[jaykang10]

Fixed typo

[samparker]

Thanks, LGTM

[fhahn]

llvm/test/Transforms/IRCE/variable-loop-bounds.ll

370

I personally find tests with a lot of numbered BBs and instructions quite hard to read. IMO it would improve readability & maintainability of those tests if the blocks and instructions would have descriptive labels :)

[fhahn]

llvm/test/Transforms/IRCE/variable-loop-bounds.ll

362

Also, should we have tests checking the actual IR, at least the important bits like most other test do here?

[jaykang10]

llvm/test/Transforms/IRCE/variable-loop-bounds.ll

362

Yep, I will update it.

370

Yep, I will update it.

[jaykang10]

In D101174#2718888, @samparker wrote:

Thanks, LGTM

Thanks @samparker! After updating tests following comments of @fhahn , I will push this change.

[lebedev.ri]

Won't this regress old-pm, or break again if/when new-pm is switched to populate loops in the other direction?

[jaykang10]

In D101174#2719038, @lebedev.ri wrote:

Won't this regress old-pm, or break again if/when new-pm is switched to populate loops in the other direction?

IRCE pass has not been enabled in the pipeline of old-pm and new-pm. The previous bound check was ok but it was a bit too conservative and it blocked for IRCE pass to handle loops which can be handled by the pass. The population order of loops affects SCEV and the SCEV blocks the IRCE pass. I think this change is fine. As next step, I will start to discussion to enable IRCE pass in the pipeline of new-pm.

[lebedev.ri]

In D101174#2719140, @jaykang10 wrote:

In D101174#2719038, @lebedev.ri wrote:

Won't this regress old-pm, or break again if/when new-pm is switched to populate loops in the other direction?

IRCE pass has not been enabled in the pipeline of old-pm and new-pm.

Yes, i know.

The previous bound check was ok but it was a bit too conservative and it blocked for IRCE pass to handle loops which can be handled by the pass.
The population order of loops affects SCEV and the SCEV blocks the IRCE pass. I think this change is fine.

I think you didn't answer the question though.

As next step, I will start to discussion to enable IRCE pass in the pipeline of new-pm.

[lebedev.ri]

llvm/test/Transforms/IRCE/variable-loop-bounds.ll

374

This doesn't make sense.
%8 is -1 then: https://alive2.llvm.org/ce/z/SeYHXr

[jaykang10]

I think you didn't answer the question though.

From my opinion, it will not regress old-pm and it will not be affected by the population order of loops in new-pm. This change just relieves the bound check for new loop. If it is not proper answer for your question, please let me know.

[lebedev.ri]

With the order, if there are sibling loops, the target loop's predecessor could be located in previously processed loop which has complex CFG from optimization. From this situation, it is not easy to expect isLoopEntryGuardedByCond returns true.

I'm having a hard time parsing your messages :/
What does "is not easy" mean?
Is there some particular pattern that SCEV doesn't handle?
Perhaps it can be easily taught about it.

In D101174#2719193, @jaykang10 wrote:

I think you didn't answer the question though.

From my opinion, it will not regress old-pm and it will not be affected by the population order of loops in new-pm. This change just relieves the bound check for new loop. If it is not proper answer for your question, please let me know.

Okay. So am i understanding correctly that we simply don't need that other check, and we don't have correctness problems when omitting it?

No further comments from me, thanks.

llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

715

Does this need a SE.isKnownPositive(Step), like one in isSafeDecreasingBound()?

[jaykang10]

@samparker @fhahn @lebedev.ri. I am so sorry for spending your time. I have found several regressions which cause redundant loops. It looks the conservative bound check is needed in order to avoid it. I will close this review. I am sorry again.

[nikic]

@jaykang10 Maybe you can add a test for the problem you encountered, to make sure it's not broken in the future?

[jaykang10]

In D101174#2719958, @nikic wrote:

@jaykang10 Maybe you can add a test for the problem you encountered, to make sure it's not broken in the future?

Yep, let me add the test cases.

[jaykang10]

Added tests which causes redundant loops with this change.

[lebedev.ri]

If they reproduce the miscompile then please proceed :)

[jaykang10]

In D101174#2722093, @lebedev.ri wrote:

If they reproduce the miscompile then please proceed :)

Thanks @lebedev.ri!

Even though the test cases have weird loops, I think the pass needs to detect it. Let me push it.

llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

assert(LatchBrExitIdx == 0 &&
          "LatchBrExitIdx should be either 0 or 1");
 
   const SCEV *StepPlusOne = SE.getAddExpr(Step, SE.getOne(Step->getType()));
   unsigned BitWidth = cast<IntegerType>(BoundSCEV->getType())->getBitWidth();
   APInt Min = IsSigned ? APInt::getSignedMinValue(BitWidth) :
     APInt::getMinValue(BitWidth);
   const SCEV *Limit = SE.getMinusSCEV(SE.getConstant(Min), StepPlusOne);
 
-  const SCEV *MinusOne =
-    SE.getMinusSCEV(BoundSCEV, SE.getOne(BoundSCEV->getType()));
-
-  return SE.isLoopEntryGuardedByCond(L, BoundPred, Start, MinusOne) &&
-         SE.isLoopEntryGuardedByCond(L, BoundPred, BoundSCEV, Limit);
-
+  return SE.isLoopEntryGuardedByCond(L, BoundPred, BoundSCEV, Limit);
 }
 
 /// Given a loop with an increasing induction variable, is it possible to
 /// safely calculate the bounds of a new loop using the given Predicate.
 static bool isSafeIncreasingBound(const SCEV *Start,
                                   const SCEV *BoundSCEV, const SCEV *Step,
                                   ICmpInst::Predicate Pred,
                                   unsigned LatchBrExitIdx,
                                   Loop *L, ScalarEvolution &SE) {
   if (Pred != ICmpInst::ICMP_SLT && Pred != ICmpInst::ICMP_SGT &&
       Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_UGT)
     return false;
 
   if (!SE.isAvailableAtLoopEntry(BoundSCEV, L))
     return false;
 
   LLVM_DEBUG(dbgs() << "irce: isSafeIncreasingBound with:\n");
   LLVM_DEBUG(dbgs() << "irce: Start: " << *Start << "\n");
   LLVM_DEBUG(dbgs() << "irce: Step: " << *Step << "\n");
   LLVM_DEBUG(dbgs() << "irce: BoundSCEV: " << *BoundSCEV << "\n");
   LLVM_DEBUG(dbgs() << "irce: Pred: " << ICmpInst::getPredicateName(Pred)
                     << "\n");
   LLVM_DEBUG(dbgs() << "irce: LatchExitBrIdx: " << LatchBrExitIdx << "\n");
 
static bool isSafeIncreasingBound(const SCEV *Start,
 
   const SCEV *StepMinusOne =
     SE.getMinusSCEV(Step, SE.getOne(Step->getType()));
   unsigned BitWidth = cast<IntegerType>(BoundSCEV->getType())->getBitWidth();
   APInt Max = IsSigned ? APInt::getSignedMaxValue(BitWidth) :
     APInt::getMaxValue(BitWidth);
   const SCEV *Limit = SE.getMinusSCEV(SE.getConstant(Max), StepMinusOne);
 
-  return (SE.isLoopEntryGuardedByCond(L, BoundPred, Start,
-                                      SE.getAddExpr(BoundSCEV, Step)) &&
-          SE.isLoopEntryGuardedByCond(L, BoundPred, BoundSCEV, Limit));
+  return SE.isLoopEntryGuardedByCond(L, BoundPred, BoundSCEV, Limit);
 }
 
 Optional<LoopStructure>
 LoopStructure::parseLoopStructure(ScalarEvolution &SE, Loop &L,
                                   const char *&FailureReason) {
   if (!L.isLoopSimplifyForm()) {
     FailureReason = "loop not in LoopSimplify form";
     return None;

llvm/test/Transforms/IRCE/variable-loop-bounds.ll

 ; RUN: opt -irce -S -verify-loop-info -irce-print-changed-loops -irce-skip-profitability-checks < %s 2>&1 | FileCheck %s
 
 ; CHECK: irce: in function test_inc_eq: constrained Loop at depth 1 containing: %for.body<header>,%if.else,%if.then,%for.inc<latch><exiting>
 ; CHECK: irce: in function test_inc_ne: constrained Loop at depth 1 containing: %for.body<header>,%if.else,%if.then,%for.inc<latch><exiting>
 ; CHECK: irce: in function test_inc_slt: constrained Loop at depth 1 containing: %for.body<header>,%if.else,%if.then,%for.inc<latch><exiting>
 ; CHECK: irce: in function test_inc_ult: constrained Loop at depth 1 containing: %for.body<header>,%if.else,%if.then,%for.inc<latch><exiting>
 ; CHECK: irce: in function signed_var_imm_dec_sgt: constrained Loop at depth 1 containing: %for.body<header>,%if.else,%for.inc<latch><exiting>
 ; CHECK-NOT: irce: in function signed_var_imm_dec_slt: constrained Loop at depth 1 containing: %for.body<header>,%if.else,%for.inc<latch><exiting>
 ; CHECK: irce: in function signed_var_imm_dec_sge: constrained Loop at depth 1 containing: %for.body<header>,%if.else,%for.inc<latch><exiting>
 ; CHECK: irce: in function signed_var_imm_dec_ne: constrained Loop at depth 1 containing: %for.body<header>,%if.else,%for.inc<latch><exiting>
 ; CHECK-NOT: irce: in function signed_var_imm_dec_eq: constrained Loop at depth 1 containing: %for.body<header>,%if.else,%for.inc<latch><exiting>
+; CHECK: irce: in function test_dec_bound: constrained Loop at depth 1 containing: %7<header>,%10,%11<latch><exiting>
+; CHECK: irce: in function test_inc_bound: constrained Loop at depth 1 containing: %2<header>,%5,%6<latch><exiting>
+; CHECK-NOT: irce: in function test_dec_bound_with_step_not_one: constrained Loop at depth 1 containing: %7<header>,%10,%11<latch><exiting>
+; CHECK-NOT: irce: in function test_inc_bound_with_step_not_one: constrained Loop at depth 1 containing: %2<header>,%5,%6<latch><exiting>
+; CHECK-NOT: irce: in function test_dec_bound_with_min_start: constrained Loop at depth 1 containing: %7<header>,%10,%11<latch><exiting>
+; CHECK-NOT: irce: in function test_inc_bound_with_max_start: constrained Loop at depth 1 containing: %2<header>,%5,%6<latch><exiting>
 
 ; CHECK-LABEL: test_inc_eq(
 ; CHECK: main.exit.selector:
 ; CHECK: [[PSEUDO_PHI:%[^ ]+]] = phi i32 [ %inc, %for.inc ]
 ; CHECK: [[COND:%[^ ]+]] = icmp ult i32 [[PSEUDO_PHI]], %N
 ; CHECK: br i1 [[COND]], label %main.pseudo.exit, label %for.cond.cleanup.loopexit
 define void @test_inc_eq(i32* nocapture %a, i32* nocapture readonly %b, i32* nocapture readonly %c, i32 %N) {
 entry:

 
 for.inc:                                          ; preds = %for.body, %if.else
   %storemerge = phi i32 [ %add, %if.else ], [ %mul, %for.body ]
   store i32 %storemerge, i32* %arrayidx3, align 4
   %dec = add nsw i32 %iv, -1
   %cmp = icmp eq i32 %dec, %M
   br i1 %cmp, label %for.cond.cleanup, label %for.body
 }
+
+define void @test_dec_bound(i64 %0, i64 %1) {
+  br label %3
+
+3:                                                ; preds = %7, %2
+  %4 = phi i64 [ %8, %7 ], [ %1, %2 ]
+  %5 = icmp slt i64 %4, %0
+  br i1 %5, label %6, label %7
+
+6:                                                ; preds = %3
+  br label %7
+
+7:                                                ; preds = %6, %3
+  %8 = add nuw nsw i64 %4, -1
+  %9 = icmp eq i64 %8, 0
+  br i1 %9, label %10, label %3
+
+10:                                               ; preds = %7
+  ret void
+}
+
+define void @test_inc_bound(i64 %0) {
+  br label %2
+
+2:                                                ; preds = %6, %1
+  %3 = phi i64 [ %7, %6 ], [ 1, %1 ]
+  %4 = icmp slt i64 %3, %0
+  br i1 %4, label %5, label %6
+
+5:                                                ; preds = %2
+  br label %6
+
+6:                                                ; preds = %5, %2
+  %7 = add nuw nsw i64 %3, 1
+  %8 = icmp eq i64 %7, 0
+  br i1 %8, label %9, label %2
+
+9:                                                ; preds = %6
+  ret void
+}
+
+define void @test_dec_bound_with_step_not_one(i64 %0, i64 %1) {
+  br label %3
+
+3:                                                ; preds = %7, %2
+  %4 = phi i64 [ %8, %7 ], [ %1, %2 ]
+  %5 = icmp slt i64 %4, %0
+  br i1 %5, label %6, label %7
+
+6:                                                ; preds = %3
+  br label %7
+
+7:                                                ; preds = %6, %3
+  %8 = add nuw nsw i64 %4, -2
+  %9 = icmp eq i64 %8, 0
+  br i1 %9, label %10, label %3
+
+10:                                               ; preds = %7
+  ret void
+}
+
+define void @test_inc_bound_with_step_not_one(i64 %0) {
+  br label %2
+
+2:                                                ; preds = %6, %1
+  %3 = phi i64 [ %7, %6 ], [ 1, %1 ]
+  %4 = icmp slt i64 %3, %0
+  br i1 %4, label %5, label %6
+
+5:                                                ; preds = %2
+  br label %6
+
+6:                                                ; preds = %5, %2
+  %7 = add nuw nsw i64 %3, 2
+  %8 = icmp eq i64 %7, 0
+  br i1 %8, label %9, label %2
+
+9:                                                ; preds = %6
+  ret void
+}
+
+define void @test_dec_bound_with_max_start(i32 %0, i32 %1) {
+  br label %3
+
+3:                                                ; preds = %7, %2
+  %4 = phi i32 [ %8, %7 ], [ -2147483648, %2 ]
+  %5 = icmp slt i32 %4, %0
+  br i1 %5, label %6, label %7
+
+6:                                                ; preds = %3
+  br label %7
+
+7:                                                ; preds = %6, %3
+  %8 = add nsw i32 %4, -2
+  %9 = icmp eq i32 %8, 0
+  br i1 %9, label %10, label %3
+
+10:                                               ; preds = %7
+  ret void
+}
+
+define void @test_inc_bound_with_max_start(i32 %0) {
+  br label %2
+
+2:                                                ; preds = %6, %1
+  %3 = phi i32 [ %7, %6 ], [ 2147483648, %1 ]
+  %4 = icmp slt i32 %3, %0
+  br i1 %4, label %5, label %6
+
+5:                                                ; preds = %2
+  br label %6
+
+6:                                                ; preds = %5, %2
+  %7 = add nuw i32 %3, 1
+  %8 = icmp eq i32 %7, 0
+  br i1 %8, label %9, label %2
+
+9:                                                ; preds = %6
+  ret void
+}