[IRCE] Return "Identify loops with latch comparison against current IV value"

[mkazantsev]

Summary

The patch was reverted by rL312783 due to failures on internal tests. The failures are fixed
in this revision, specifically the previous version of the patch missed updates of GreatestSeen
and Smallest values in case of comparison against current IV value.

Current implementation of parseLoopStructure interprets the latch comparison as a
comarison against iv.next. If the actual comparison is made against the iv current value
then the loop may be rejected, because this misinterpretation leads to incorrect evaluation
of the latch start value.

This patch teaches the IRCE to distinguish this kind of loops and perform the optimization
for them. Now we use IndVarBase variable which can be either next or current value of the
induction variable (previously we used IndVarNext which was always the value on next iteration).

[mkazantsev]

Our internal testing has detected some bugs with this patch, so I will fix them and re-submit the fixed version.

[mkazantsev]

Fixed the bug that was found on internal testing, extended tests.

[mkazantsev]

Ping

[mkazantsev]

Split into two parts (NFC rename and new logic) to make it easier to review.

[mkazantsev]

One more (rare) failure was found on internal testing. Need to investigate it. Also need to extend the test base.

[mkazantsev]

Fixed the problem with incorrect end value in changeIterationSpaceEnd, updated tests wrt this change.

[anna]

Comments inline.

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

464

Pls add a comment for what IndVarBase and IndVarNext means. It's pretty clear in the summary of the bug, but add it as a comment in the code as well.

838

Pls add a comment that this checks that the comparison is made against iv.next.

845

I'm not sure if this is enough to identify that it's from the current IV.

What if we had some "noop" operations on that phi node, and the result of that operation was used in the comparison? Wouldn't we incorrectly mark as this is from iv.next, whereas it's infact from the current IV.

header:
iv = phi [0, entry] [iv.next, latch]
...

latch:
iv.trunc =  trunc iv to 16
iv.next = iv + 1
%cmp = slt iv.trunc, 100
br %cmp, header, exit

It could be bitcast or trunc or any other such operations. I think we need to "look through these operations" rather than directly comparing against a phi node.

Please add test cases as well.

[mkazantsev]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

845

In current implementation, such case will be still recognized as comparison against iv.next. That's an interesting point, I need to think on it. Thanks for noticing that!

[mkazantsev]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

845

I checked that they follow by iv.next branch and get rejected on iteration range safety stage. Given that this behavior also exists without this patch, this doesn't seem to produce bugs. Added a TODO to handle these cases by the first branch as a scope improvement.

[mkazantsev]

Added some clarifying comments & tests.

[anna]

Max, could you please update the patch with full context?

[mkazantsev]

Oh. My bad. Re-uploaded version with context.

[anna]

LGTM

[mkazantsev]

This one was reverted due to found bug, I'm working on fix.

[mkazantsev]

Fixed buggy tests & code, added a new test.

[mkazantsev]

The patch was reverted by rL312783 due to failures on internal tests. The failures are fixed
in this revision, specifically the previous version of the patch missed updates of GreatestSeen
and Smallest values in case of comparison against current IV value.

Failures fix, resubmitting for review.

[mkazantsev]

Need to simplify the new tests slightly.

[mkazantsev]

Simplified tests 06-09 (that exercise the last found problem) slightly. Also added a comment.

[mkazantsev]

Needs to be ported on top of current code base.

[mkazantsev]

Rebased

[mkazantsev]

No plan to return it in near future, maybe will be required later.

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

struct LoopStructure {
   //   ... body ...
 
   Value *IndVarNext;
   Value *IndVarStart;
   Value *IndVarStep;
   Value *LoopExitAt;
   bool IndVarIncreasing;
   bool IsSignedPredicate;
 
   LoopStructure()
       : Tag(""), Header(nullptr), Latch(nullptr), LatchBr(nullptr),
         LatchExit(nullptr), LatchBrExitIdx(-1), IndVarNext(nullptr),
         IndVarStart(nullptr), IndVarStep(nullptr), LoopExitAt(nullptr),
         IndVarIncreasing(false), IsSignedPredicate(true) {}
 
   template <typename M> LoopStructure map(M Map) const {
     LoopStructure Result;
if (const SCEVConstant *StepExpr =
       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.
+  // `ICI` can either be a comparison against IV or a comparison of IV.next.
+  // Depending on the interpretation, we calculate the start value differently.
 
-  const SCEVAddRecExpr *IndVarNext = cast<SCEVAddRecExpr>(LeftSCEV);
+  const SCEVAddRecExpr *IVRec = cast<SCEVAddRecExpr>(LeftSCEV);
   bool IsIncreasing = false;
   bool IsSignedPredicate = true;
   ConstantInt *StepCI;
-  if (!IsInductionVar(IndVarNext, IsIncreasing, StepCI)) {
+  if (!IsInductionVar(IVRec, IsIncreasing, StepCI)) {
     FailureReason = "LHS in icmp not induction variable";
     return None;
   }
 
-  const SCEV *StartNext = IndVarNext->getStart();
-  const SCEV *Addend = SE.getNegativeSCEV(IndVarNext->getStepRecurrence(SE));
-  const SCEV *IndVarStart = SE.getAddExpr(StartNext, Addend);
+  const SCEV *IndVarStart;
+  Value *IndVarNext;
+  if (isa<PHINode>(LeftValue) &&
+      cast<PHINode>(LeftValue)->getParent() == Header) {
+    // The comparison is made against IV.
+    IndVarStart = IVRec->getStart();
+    IndVarNext = cast<PHINode>(LeftValue)->getIncomingValueForBlock(Latch);
+  } else {
+    // Assume that the comparison is made against IV.next.
+    const SCEV *StartNext = IVRec->getStart();
+    const SCEV *Addend = SE.getNegativeSCEV(IVRec->getStepRecurrence(SE));
+    IndVarStart = SE.getAddExpr(StartNext, Addend);
+    IndVarNext = LeftValue;
+  }
   const SCEV *Step = SE.getSCEV(StepCI);
 
   ConstantInt *One = ConstantInt::get(IndVarTy, 1);
   if (IsIncreasing) {
     bool DecreasedRightValueByOne = false;
     if (StepCI->isOne()) {
       // Try to turn eq/ne predicates to those we can work with.
       if (Pred == ICmpInst::ICMP_NE && LatchBrExitIdx == 1)
LoopStructure::parseLoopStructure(ScalarEvolution &SE,
   Result.Tag = "main";
   Result.Header = Header;
   Result.Latch = Latch;
   Result.LatchBr = LatchBr;
   Result.LatchExit = LatchExit;
   Result.LatchBrExitIdx = LatchBrExitIdx;
   Result.IndVarStart = IndVarStartV;
   Result.IndVarStep = StepCI;
-  Result.IndVarNext = LeftValue;
+  Result.IndVarNext = IndVarNext;
   Result.IndVarIncreasing = IsIncreasing;
   Result.LoopExitAt = RightValue;
   Result.IsSignedPredicate = IsSignedPredicate;
 
   FailureReason = nullptr;
 
   return Result;
 }

test/Transforms/IRCE/latch-comparison-against-current-value.ll

+; RUN: opt -verify-loop-info -irce-print-changed-loops -irce -S < %s 2>&1 | FileCheck %s
+
+; Check that IRCE is able to deal with loops where the latch comparison is
+; done against current value of the IV, not the IV.next.
+
+; 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>
+
+; SLT condition for increasing loop from MIN_SINT to 100.
+define void @test_01(i32* %arr, i32* %a_len_ptr) #0 {
+
+; CHECK:      test_01
+; CHECK:        main.exit.selector:
+; CHECK-NEXT:     [[PSEUDO_PHI:%[^ ]+]] = phi i32 [ %idx.next, %in.bounds ]
+; CHECK-NEXT:     [[COND:%[^ ]+]] = icmp slt i32 [[PSEUDO_PHI]], 100
+; CHECK-NEXT:     br i1 [[COND]]
+
+entry:
+  %len = load i32, i32* %a_len_ptr, !range !0
+  br label %loop
+
+loop:
+  %idx = phi i32 [ -2147483648, %entry ], [ %idx.next, %in.bounds ]
+  %idx.next = add nsw nuw i32 %idx, 1
+  %abc = icmp slt i32 %idx, %len
+  br i1 %abc, label %in.bounds, label %out.of.bounds
+
+in.bounds:
+  %addr = getelementptr i32, i32* %arr, i32 %idx
+  store i32 0, i32* %addr
+  %next = icmp slt i32 %idx, 100
+  br i1 %next, label %loop, label %exit
+
+out.of.bounds:
+  ret void
+
+exit:
+  ret void
+}
+
+; ULT condition for increasing loop from MIN_UINT to 100.
+define void @test_02(i32* %arr, i32* %a_len_ptr) #0 {
+
+; CHECK:      test_02
+; CHECK:        main.exit.selector:
+; CHECK-NEXT:     [[PSEUDO_PHI:%[^ ]+]] = phi i32 [ %idx.next, %in.bounds ]
+; CHECK-NEXT:     [[COND:%[^ ]+]] = icmp ult i32 [[PSEUDO_PHI]], 100
+; CHECK-NEXT:     br i1 [[COND]]
+
+entry:
+  %len = load i32, i32* %a_len_ptr, !range !0
+  br label %loop
+
+loop:
+  %idx = phi i32 [ 0, %entry ], [ %idx.next, %in.bounds ]
+  %idx.next = add nsw nuw i32 %idx, 1
+  %abc = icmp ult i32 %idx, %len
+  br i1 %abc, label %in.bounds, label %out.of.bounds
+
+in.bounds:
+  %addr = getelementptr i32, i32* %arr, i32 %idx
+  store i32 0, i32* %addr
+  %next = icmp ult i32 %idx, 100
+  br i1 %next, label %loop, label %exit
+
+out.of.bounds:
+  ret void
+
+exit:
+  ret void
+}
+
+!0 = !{i32 0, i32 50}