[IRCE] Smarter detection of empty ranges using SCEV

[mkazantsev]

Summary

For a SCEV range, this patch replaces the naive emptiness check for SCEV ranges
which looks like Begin == End with a SCEV check. The range is guaranteed to be
empty of Begin >= End. We should filter such ranges out and do not try to perform
IRCE for them.

For example, we can get such range when intersecting range [A, B) and [C, D)
where A < B < C < D. The resulting range is [max(A, C), min(B, D)) = [C, B).
This range is empty, but its Begin does not match with End.

Making IRCE for an empty range is basically safe, but unprofitable because we
never actually get into the main loop where the range checks are supposed to
be eliminated. This patch uses SCEV mechanisms to treat loops with proved
Begin >= End as empty.

[anna]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

185

SCEV's isKnownPredicate is actually really good in most cases to identify the empty range (BEGIN >= END).
However, there's a stronger version of isKnownPredicate in DependenceInfo::isKnownPredicate.

Specifically, it first checks SCEV's version of isKnownPredicate and if it fails, it does a further analysis using the Delta between Begin and End and checking the Delta based on the predicate passed in.

I'm wondering if SCEV's form maybe weaker and hence we may fire the assert added about empty ranges at line 1756?

test/Transforms/IRCE/empty_ranges.ll

9

So, in this case, from now on, only the first range check is removed, i.e. we will not remove range checks where the safe iteration space intersected with the "true" iteration space is empty. By true iteration space, I mean, the set where the guard is always true.

[mkazantsev]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

185

Assert on 1756 should never fire. If you look into IntersectRange, we check range on isEmpty() and return None if it is true. We make check before return and check in assert with the same isEmpty(), so we just cannot end up with one returning true and another returning false.

Thanks for pointing me out of DependenceInfo::isKnownPredicate, I will see if I can use it here.

test/Transforms/IRCE/empty_ranges.ll

9

That was the intension. Checks in pre- and postloop are not eliminated, and if the safe iteration space is empty, we will never get to the mainloop (where something was removed). Removing at least something from the main loop which remains reachable may be good by itself. For example, if there was a load between range checks 1 and 2, we can now correctly hoist it out of the main loop because it becomes guaranteed to execute now.

[mkazantsev]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

185

I don't really like this idea after looking into its code. The reasons are:

1. To use it, we need to factor this method out of dependency analysis ( e.g. into an utility function which takes ScalarEvolution as a parameter);
2. It does not currently support unsigned comparisons failing with llvm_unreachable("unexpected predicate in isKnownPredicate");, and we do need them;
3. If what it does with Delta is really profitable for symbolics, I don't see why it shouldn't be moved to ScalarEvolution::isKnownPredicate. This code doesn't need anything but ScalarEvolution.

So I would rather leave it as it is and consider this extra stuff from DependenceInfo::isKnownPredicate for factoring into SCEV in case if it is proved to make any sense.

[mkazantsev]

test/Transforms/IRCE/empty_ranges.ll

9

For example, if the 2nd range check wasn't leaving the loop, the transform would also be profitable.

[anna]

LGTM.

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

185

agreed. I was just curious about how the further Delta checks helps here (if any), and it looks like it won't help us?

[mkazantsev]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

185

In theory, they can help if we iterate from symbilic to symbolic; in practice, I think in most such cases we won't be able to prove anything if we don't have a known range for them, and if we know the range, we can prove isKnownPredicate basing on it.

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

public:
   public:
     Range(const SCEV *Begin, const SCEV *End) : Begin(Begin), End(End) {
       assert(Begin->getType() == End->getType() && "ill-typed range!");
     }
 
     Type *getType() const { return Begin->getType(); }
     const SCEV *getBegin() const { return Begin; }
     const SCEV *getEnd() const { return End; }
-    bool isEmpty() const { return Begin == End; }
+    bool isEmpty(ScalarEvolution &SE, bool IsSigned) const {
+      if (Begin == End)
+        return true;
+      if (IsSigned)
+        return SE.isKnownPredicate(ICmpInst::ICMP_SGE, Begin, End);
+      else
+        return SE.isKnownPredicate(ICmpInst::ICMP_UGE, Begin, End);
+    }
   };
 
   /// This is the value the condition of the branch needs to evaluate to for the
   /// branch to take the hot successor (see (1) above).
   bool getPassingDirection() { return true; }
 
   /// Computes a range for the induction variable (IndVar) in which the range
   /// check is redundant and can be constant-folded away.  The induction
InductiveRangeCheck::computeSafeIterationSpace(
   const SCEV *End = SE.getMinusSCEV(UpperLimit, M);
   return InductiveRangeCheck::Range(Begin, End);
 }
 
 static Optional<InductiveRangeCheck::Range>
 IntersectRange(ScalarEvolution &SE,
                const Optional<InductiveRangeCheck::Range> &R1,
                const InductiveRangeCheck::Range &R2) {
-  if (R2.isEmpty())
+  if (R2.isEmpty(SE, /* IsSigned */ true))
     return None;
   if (!R1.hasValue())
     return R2;
   auto &R1Value = R1.getValue();
   // We never return empty ranges from this function, and R1 is supposed to be
   // a result of intersection. Thus, R1 is never empty.
-  assert(!R1Value.isEmpty() && "We should never have empty R1!");
+  assert(!R1Value.isEmpty(SE, /* IsSigned */ true) &&
+         "We should never have empty R1!");
 
   // TODO: we could widen the smaller range and have this work; but for now we
   // bail out to keep things simple.
   if (R1Value.getType() != R2.getType())
     return None;
 
   const SCEV *NewBegin = SE.getSMaxExpr(R1Value.getBegin(), R2.getBegin());
   const SCEV *NewEnd = SE.getSMinExpr(R1Value.getEnd(), R2.getEnd());
 
   // If the resulting range is empty, just return None.
   auto Ret = InductiveRangeCheck::Range(NewBegin, NewEnd);
-  if (Ret.isEmpty())
+  if (Ret.isEmpty(SE, /* IsSigned */ true))
     return None;
   return Ret;
 }
 
 bool InductiveRangeCheckElimination::runOnLoop(Loop *L, LPPassManager &LPM) {
   if (skipLoop(L))
     return false;
 
bool InductiveRangeCheckElimination::runOnLoop(Loop *L, LPPassManager &LPM) {
 
   IRBuilder<> B(ExprInsertPt);
   for (InductiveRangeCheck &IRC : RangeChecks) {
     auto Result = IRC.computeSafeIterationSpace(SE, IndVar);
     if (Result.hasValue()) {
       auto MaybeSafeIterRange =
           IntersectRange(SE, SafeIterRange, Result.getValue());
       if (MaybeSafeIterRange.hasValue()) {
-        assert(!MaybeSafeIterRange.getValue().isEmpty() &&
-               "We should never return empty ranges!");
+        assert(
+            !MaybeSafeIterRange.getValue().isEmpty(SE, LS.IsSignedPredicate) &&
         RangeChecksToEliminate.push_back(IRC);
         SafeIterRange = MaybeSafeIterRange.getValue();
       }
     }
   }
 
   if (!SafeIterRange.hasValue())
     return false;

test/Transforms/IRCE/clamp.ll

+; This test demonstrates the confusion in ranges: we have unsigned ranges here,
+; but signed comparisons in IntersectRanges produce bad results. We temporarily
+; disable it and re-enable once the unsigned ranges are supported again.
+; XFAIL: *
 ; RUN: opt -verify-loop-info -irce-print-changed-loops -irce -irce-allow-unsigned-latch=true -S < %s 2>&1 | FileCheck %s
 
 ; The test demonstrates that incorrect behavior of Clamp may lead to incorrect
 ; calculation of post-loop exit condition.
 
 ; CHECK: irce: in function test: constrained Loop at depth 1 containing: %loop<header><exiting>,%in_bounds<exiting>,%not_zero<latch><exiting>
 
 define void @test() {

test/Transforms/IRCE/empty_ranges.ll

+; RUN: opt -verify-loop-info -irce-print-changed-loops -irce -irce-allow-unsigned-latch=true -S
+
+
+; Make sure that IRCE doesn't apply in case of empty ranges.
+; (i + 30 < 40) if i in [-30, 10).
+; Intersected with iteration space, it is [0, 10).
+; (i - 60 < 40) if i in [60 , 100).
+; The intersection with safe iteration space is the empty range [60, 10).
+; It is better to eliminate one range check than attempt to eliminate both given
+; that we will never go to the main loop in the latter case and basically
+; only duplicate code with no benefits.
+
+define void @test_01(i32* %arr, i32* %a_len_ptr) #0 {
+
+; CHECK-LABEL: test_01(
+; CHECK-NOT:   preloop
+; CHECK:       entry:
+; CHECK-NEXT:    br i1 true, label %loop.preheader, label %main.pseudo.exit
+; CHECK:       in.bounds.1:
+; CHECK-NEXT:    %addr = getelementptr i32, i32* %arr, i32 %idx
+; CHECK-NEXT:    store i32 0, i32* %addr
+; CHECK-NEXT:    %off1 = add i32 %idx, 30
+; CHECK-NEXT:    %c2 = icmp slt i32 %off1, 40
+; CHECK-NEXT:    br i1 true, label %in.bounds.2, label %exit.loopexit2
+; CHECK:       in.bounds.2:
+; CHECK-NEXT:    %off2 = add i32 %idx, -60
+; CHECK-NEXT:    %c3 = icmp slt i32 %off2, 40
+; CHECK-NEXT:    br i1 %c3, label %in.bounds.3, label %exit.loopexit2
+; CHECK:       in.bounds.3:
+; CHECK-NEXT:    %next = icmp ult i32 %idx.next, 100
+; CHECK-NEXT:    [[COND1:%[^ ]+]] = icmp ult i32 %idx.next, 10
+; CHECK-NEXT:    br i1 [[COND1]], label %loop, label %main.exit.selector
+; CHECK:       main.exit.selector:
+; CHECK-NEXT:    %idx.next.lcssa = phi i32 [ %idx.next, %in.bounds.3 ]
+; CHECK-NEXT:    [[COND2:%[^ ]+]] = icmp ult i32 %idx.next.lcssa, 100
+; CHECK-NEXT:    br i1 [[COND2]], label %main.pseudo.exit, label %exit
+; CHECK:       postloop:
+
+entry:
+  br label %loop
+
+loop:
+  %idx = phi i32 [ 0, %entry ], [ %idx.next, %in.bounds.3 ]
+  %idx.next = add nsw nuw i32 %idx, 1
+  %c1 = icmp slt i32 %idx, 20
+  br i1 %c1, label %in.bounds.1, label %out.of.bounds
+
+in.bounds.1:
+  %addr = getelementptr i32, i32* %arr, i32 %idx
+  store i32 0, i32* %addr
+  %off1 = add i32 %idx, 30
+  %c2 = icmp slt i32 %off1, 40
+  br i1 %c2, label %in.bounds.2, label %exit
+
+in.bounds.2:
+  %off2 = add i32 %idx, -60
+  %c3 = icmp slt i32 %off2, 40
+  br i1 %c3, label %in.bounds.3, label %exit
+
+in.bounds.3:
+  %next = icmp ult i32 %idx.next, 100
+  br i1 %next, label %loop, label %exit
+
+out.of.bounds:
+  ret void
+
+exit:
+  ret void
+}