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()) {