[IRCE] Fix intersection between signed and unsigned ranges

IRCE for unsigned latch conditions was temporarily disabled by rL314881. The motivating
example contained an unsigned latch condition and a signed range check. One of the safe
iteration ranges was `[1, SINT_MAX + 1]`. Its right border was incorrectly interpreted as a negative
value in `IntersectRange` function, this lead to a miscompile under which we deleted a range check
without inserting a postloop where it was needed.

This patch brings back IRCE for unsigned latch conditions. Now we treat range intersection more
carefully. If the latch condition was unsigned, we only try to consider a range check for deletion if:
1. The range check is also unsigned, or
2. Safe iteration range of the range check lies within `[0, SINT_MAX]`.
The same is done for signed latch.

Values from `[0, SINT_MAX]` are unambiguous, these values are non-negative under any interpretation,
and all values of a range intersected with such range are also non-negative.

We also use signed/unsigned min/max functions for range intersection depending on type of the
latch condition.

Differential Revision: https://reviews.llvm.org/D38581

llvm-svn: 316552

1 files changed, 73 insertions, 14 deletions

diff --git a/llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp b/llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp
index 9011c0433c9..42c74c3a3cc 100644
--- a/llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp
+++ b/llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp
@@ -112,7 +112,7 @@ static cl::opt<bool> SkipProfitabilityChecks("irce-skip-profitability-checks",
                                              cl::Hidden, cl::init(false));
 
 static cl::opt<bool> AllowUnsignedLatchCondition("irce-allow-unsigned-latch",
-                                                 cl::Hidden, cl::init(false));
+                                                 cl::Hidden, cl::init(true));
 
 static const char *ClonedLoopTag = "irce.loop.clone";
 
@@ -154,10 +154,11 @@ class InductiveRangeCheck {
   Value *Length = nullptr;
   Use *CheckUse = nullptr;
   RangeCheckKind Kind = RANGE_CHECK_UNKNOWN;
+  bool IsSigned = true;
 
   static RangeCheckKind parseRangeCheckICmp(Loop *L, ICmpInst *ICI,
                                             ScalarEvolution &SE, Value *&Index,
-                                            Value *&Length);
+                                            Value *&Length, bool &IsSigned);
 
   static void
   extractRangeChecksFromCond(Loop *L, ScalarEvolution &SE, Use &ConditionUse,
@@ -168,6 +169,7 @@ public:
   const SCEV *getOffset() const { return Offset; }
   const SCEV *getScale() const { return Scale; }
   Value *getLength() const { return Length; }
+  bool isSigned() const { return IsSigned; }
 
   void print(raw_ostream &OS) const {
     OS << "InductiveRangeCheck:\n";
@@ -295,7 +297,7 @@ StringRef InductiveRangeCheck::rangeCheckKindToStr(
 InductiveRangeCheck::RangeCheckKind
 InductiveRangeCheck::parseRangeCheckICmp(Loop *L, ICmpInst *ICI,
                                          ScalarEvolution &SE, Value *&Index,
-                                         Value *&Length) {
+                                         Value *&Length, bool &IsSigned) {
   auto IsNonNegativeAndNotLoopVarying = [&SE, L](Value *V) {
     const SCEV *S = SE.getSCEV(V);
     if (isa<SCEVCouldNotCompute>(S))
@@ -317,6 +319,7 @@ InductiveRangeCheck::parseRangeCheckICmp(Loop *L, ICmpInst *ICI,
     std::swap(LHS, RHS);
     LLVM_FALLTHROUGH;
   case ICmpInst::ICMP_SGE:
+    IsSigned = true;
     if (match(RHS, m_ConstantInt<0>())) {
       Index = LHS;
       return RANGE_CHECK_LOWER;
@@ -327,6 +330,7 @@ InductiveRangeCheck::parseRangeCheckICmp(Loop *L, ICmpInst *ICI,
     std::swap(LHS, RHS);
     LLVM_FALLTHROUGH;
   case ICmpInst::ICMP_SGT:
+    IsSigned = true;
     if (match(RHS, m_ConstantInt<-1>())) {
       Index = LHS;
       return RANGE_CHECK_LOWER;
@@ -343,6 +347,7 @@ InductiveRangeCheck::parseRangeCheckICmp(Loop *L, ICmpInst *ICI,
     std::swap(LHS, RHS);
     LLVM_FALLTHROUGH;
   case ICmpInst::ICMP_UGT:
+    IsSigned = false;
     if (IsNonNegativeAndNotLoopVarying(LHS)) {
       Index = RHS;
       Length = LHS;
@@ -375,7 +380,8 @@ void InductiveRangeCheck::extractRangeChecksFromCond(
       const auto &RChkA = SubChecks[0];
       const auto &RChkB = SubChecks[1];
       if ((RChkA.Length == RChkB.Length || !RChkA.Length || !RChkB.Length) &&
-          RChkA.Offset == RChkB.Offset && RChkA.Scale == RChkB.Scale) {
+          RChkA.Offset == RChkB.Offset && RChkA.Scale == RChkB.Scale &&
+          RChkA.IsSigned == RChkB.IsSigned) {
         // If RChkA.Kind == RChkB.Kind then we just found two identical checks.
         // But if one of them is a RANGE_CHECK_LOWER and the other is a
         // RANGE_CHECK_UPPER (only possibility if they're different) then
@@ -384,6 +390,7 @@ void InductiveRangeCheck::extractRangeChecksFromCond(
             (InductiveRangeCheck::RangeCheckKind)(RChkA.Kind | RChkB.Kind);
         SubChecks[0].Length = RChkA.Length ? RChkA.Length : RChkB.Length;
         SubChecks[0].CheckUse = &ConditionUse;
+        SubChecks[0].IsSigned = RChkA.IsSigned;
 
         // We updated one of the checks in place, now erase the other.
         SubChecks.pop_back();
@@ -399,7 +406,8 @@ void InductiveRangeCheck::extractRangeChecksFromCond(
     return;
 
   Value *Length = nullptr, *Index;
-  auto RCKind = parseRangeCheckICmp(L, ICI, SE, Index, Length);
+  bool IsSigned;
+  auto RCKind = parseRangeCheckICmp(L, ICI, SE, Index, Length, IsSigned);
   if (RCKind == InductiveRangeCheck::RANGE_CHECK_UNKNOWN)
     return;
 
@@ -416,6 +424,7 @@ void InductiveRangeCheck::extractRangeChecksFromCond(
   IRC.Scale = IndexAddRec->getStepRecurrence(SE);
   IRC.CheckUse = &ConditionUse;
   IRC.Kind = RCKind;
+  IRC.IsSigned = IsSigned;
   Checks.push_back(IRC);
 }
 
@@ -917,9 +926,6 @@ LoopStructure::parseLoopStructure(ScalarEvolution &SE,
     IsSignedPredicate =
         Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGT;
 
-    // FIXME: We temporarily disable unsigned latch conditions by default
-    // because of found problems with intersecting signed and unsigned ranges.
-    // We are going to turn it on once the problems are fixed.
     if (!IsSignedPredicate && !AllowUnsignedLatchCondition) {
       FailureReason = "unsigned latch conditions are explicitly prohibited";
       return None;
@@ -1001,9 +1007,6 @@ LoopStructure::parseLoopStructure(ScalarEvolution &SE,
     IsSignedPredicate =
         Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGT;
 
-    // FIXME: We temporarily disable unsigned latch conditions by default
-    // because of found problems with intersecting signed and unsigned ranges.
-    // We are going to turn it on once the problems are fixed.
     if (!IsSignedPredicate && !AllowUnsignedLatchCondition) {
       FailureReason = "unsigned latch conditions are explicitly prohibited";
       return None;
@@ -1670,9 +1673,9 @@ InductiveRangeCheck::computeSafeIterationSpace(
 }
 
 static Optional<InductiveRangeCheck::Range>
-IntersectRange(ScalarEvolution &SE,
-               const Optional<InductiveRangeCheck::Range> &R1,
-               const InductiveRangeCheck::Range &R2) {
+IntersectSignedRange(ScalarEvolution &SE,
+                     const Optional<InductiveRangeCheck::Range> &R1,
+                     const InductiveRangeCheck::Range &R2) {
   if (R2.isEmpty(SE, /* IsSigned */ true))
     return None;
   if (!R1.hasValue())
@@ -1698,6 +1701,35 @@ IntersectRange(ScalarEvolution &SE,
   return Ret;
 }
 
+static Optional<InductiveRangeCheck::Range>
+IntersectUnsignedRange(ScalarEvolution &SE,
+                       const Optional<InductiveRangeCheck::Range> &R1,
+                       const InductiveRangeCheck::Range &R2) {
+  if (R2.isEmpty(SE, /* IsSigned */ false))
+    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(SE, /* IsSigned */ false) &&
+         "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.getUMaxExpr(R1Value.getBegin(), R2.getBegin());
+  const SCEV *NewEnd = SE.getUMinExpr(R1Value.getEnd(), R2.getEnd());
+
+  // If the resulting range is empty, just return None.
+  auto Ret = InductiveRangeCheck::Range(NewBegin, NewEnd);
+  if (Ret.isEmpty(SE, /* IsSigned */ false))
+    return None;
+  return Ret;
+}
+
 bool InductiveRangeCheckElimination::runOnLoop(Loop *L, LPPassManager &LPM) {
   if (skipLoop(L))
     return false;
@@ -1756,11 +1788,38 @@ bool InductiveRangeCheckElimination::runOnLoop(Loop *L, LPPassManager &LPM) {
   Instruction *ExprInsertPt = Preheader->getTerminator();
 
   SmallVector<InductiveRangeCheck, 4> RangeChecksToEliminate;
+  auto RangeIsNonNegative = [&](InductiveRangeCheck::Range &R) {
+    return SE.isKnownNonNegative(R.getBegin()) &&
+           SE.isKnownNonNegative(R.getEnd());
+  };
+  // Basing on the type of latch predicate, we interpret the IV iteration range
+  // as signed or unsigned range. We use different min/max functions (signed or
+  // unsigned) when intersecting this range with safe iteration ranges implied
+  // by range checks.
+  auto IntersectRange =
+      LS.IsSignedPredicate ? IntersectSignedRange : IntersectUnsignedRange;
 
   IRBuilder<> B(ExprInsertPt);
   for (InductiveRangeCheck &IRC : RangeChecks) {
     auto Result = IRC.computeSafeIterationSpace(SE, IndVar);
     if (Result.hasValue()) {
+      // Intersecting a signed and an unsigned ranges may produce incorrect
+      // results because we can use neither signed nor unsigned min/max for
+      // reliably correct intersection if a range contains negative values
+      // which are either actually negative or big positive. Intersection is
+      // safe in two following cases:
+      // 1. Both ranges are signed/unsigned, then we use signed/unsigned min/max
+      //    respectively for their intersection;
+      // 2. IRC safe iteration space only contains values from [0, SINT_MAX].
+      //    The interpretation of these values is unambiguous.
+      // We take the type of IV iteration range as a reference (we will
+      // intersect it with the resulting range of all IRC's later in
+      // calculateSubRanges). Only ranges of IRC of the same type are considered
+      // for removal unless we prove that its range doesn't contain ambiguous
+      // values.
+      if (IRC.isSigned() != LS.IsSignedPredicate &&
+          !RangeIsNonNegative(Result.getValue()))
+        continue;
       auto MaybeSafeIterRange =
           IntersectRange(SE, SafeIterRange, Result.getValue());
       if (MaybeSafeIterRange.hasValue()) {