[IRCE] Fix intersection between signed and unsigned ranges

[mkazantsev]

Summary

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.

[anna]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

900 ↗

(On Diff #117797)

How about leaving this here to quickly find any problems in the future?

984 ↗

(On Diff #117797)

Ditto here.

1753 ↗

(On Diff #117797)

Is this enough for proving range is non-negative?

Looking at this lambda alone with no context here, we can have [5, 2] and still have range wrap around.
Is there a way to add an assert that getBegin < getEnd?

[mkazantsev]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

900 ↗

(On Diff #117797)

Ok, I'll update the patch preserving the option (and set it to false by default).

1753 ↗

(On Diff #117797)

In parseLoopStructure we assert that the IV HasNoSignedWrap. Interesting detail is that currently it only checks for nsw. My guess is that we should check nuw for unsigned IVs instead. I will check with that and possibly add some tests.

But generally, we assume that the IV does not have wraparound, and ranges for range checks are also in canonical form from a smaller value to a greater value.

[mkazantsev]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

1753 ↗

(On Diff #117797)

Thanks for pointing this situation out! Indeed, it wasn't handled before. As result, sometimes IRCE applied to safe ranges like [5, 2) ending up with making completely unprofitable transformations.

We cannot assert that Begin < End because in the most common situation we don't know it (for example, iteration from 0 to N where N is non-negative is potentially an empty loop, as well as iteration from A to B; we might be not able to say anything from SCEVs, however if we knew that we iterated from A to B with nsw flag, that would give us this piece of information). So this check is over-conservative.

Rather than asserting that Begin < End which is not always known without context (about the indvar and so on), I've prepared a patch https://reviews.llvm.org/D39082 that trats ranges for which we know that Begin >= End as empty.

[mkazantsev]

Added corner tests to unsigned_comparisons_ult.ll, rebased on the patch that improves work with empty ranges.

[anna]

Some clarification questions and comments inline.

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

1753 ↗

(On Diff #117797)

thanks for the clarification! I have added comments on the other review thread about detecting empty ranges.

test/Transforms/IRCE/unsigned_comparisons_ult.ll

345 ↗

(On Diff #119556)

Am I right that because of the ult for the compare, -100 is actually UINT_MAX - 99, i.e. the 2's complement of the number.
So, the iteration space is within [0, SINT_MAX].

360 ↗

(On Diff #119556)

Please add checks here as CHECK-NOT for pre and post loops.

[mkazantsev]

test/Transforms/IRCE/unsigned_comparisons_ult.ll

345 ↗

(On Diff #119556)

The iteration space here is [0, UINT_MAX - 100). SINT_MAX is within the iteration range. The comment before test about [100; -100) is misleading, i'll fix it.

360 ↗

(On Diff #119556)

On line 11, we had a check that IRCE didn't apply to the test:
; CHECK-NOT: irce: in function test_09: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
But OK, I will add these asserts as well. :)

[mkazantsev]

test/Transforms/IRCE/unsigned_comparisons_ult.ll

345 ↗

(On Diff #119556)

[0, UINT_MAX - 99) fixed

[mkazantsev]

Fixed misleading comments in test, added some checks.

[anna]

LGTM . Since context is not here but the actual logic was correct and unchanged wrt the previous review, I went by that.

test/Transforms/IRCE/unsigned_comparisons_ult.ll

360 ↗

(On Diff #119556)

ah yes, missed that. Thanks for making it clearer here!

[reames]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

1810 ↗

(On Diff #119633)

This is correct, but a likely cleaner strategy overall would be normalize ranges at the point of construction. If, for instance, all strictly positive ranges were always considered unsigned, then this check would disappear.

Might be a good standalone cleanup change after this goes in.

1753 ↗

(On Diff #117797)

One possibility, you could assert that we don't know that End <= Begin. As before, we might not be able to confirm that, but then at least if we do, we know we have a problem.

I suspect SCEV already has a function which takes a Predicate and two SCEVs, and returns an optional bool. If it doesn't, adding one might be reasonable and easily extractable.

This would be a good stand alone change to land separately.

llvm/trunk/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

 
 static cl::opt<int> MaxExitProbReciprocal("irce-max-exit-prob-reciprocal",
                                           cl::Hidden, cl::init(10));
 
 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";
 
 #define DEBUG_TYPE "irce"
 
 namespace {
 
 /// An inductive range check is conditional branch in a loop with
class InductiveRangeCheck {
 
   static StringRef rangeCheckKindToStr(RangeCheckKind);
 
   const SCEV *Offset = nullptr;
   const SCEV *Scale = nullptr;
   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,
                              SmallVectorImpl<InductiveRangeCheck> &Checks,
                              SmallPtrSetImpl<Value *> &Visited);
 
 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";
     OS << "  Kind: " << rangeCheckKindToStr(Kind) << "\n";
     OS << "  Offset: ";
     Offset->print(OS);
     OS << "  Scale: ";
     Scale->print(OS);

 /// be interpreted as a range check, return `RANGE_CHECK_UNKNOWN` and set
 /// `Index` and `Length` to `nullptr`.  Otherwise set `Index` to the value being
 /// range checked, and set `Length` to the upper limit `Index` is being range
 /// checked with if (and only if) the range check type is stronger or equal to
 /// RANGE_CHECK_UPPER.
 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))
       return false;
 
     return SE.getLoopDisposition(S, L) == ScalarEvolution::LoopInvariant &&
            SE.isKnownNonNegative(S);
   };
 
   ICmpInst::Predicate Pred = ICI->getPredicate();
   Value *LHS = ICI->getOperand(0);
   Value *RHS = ICI->getOperand(1);
 
   switch (Pred) {
   default:
     return RANGE_CHECK_UNKNOWN;
 
   case ICmpInst::ICMP_SLE:
     std::swap(LHS, RHS);
     LLVM_FALLTHROUGH;
   case ICmpInst::ICMP_SGE:
+    IsSigned = true;
     if (match(RHS, m_ConstantInt<0>())) {
       Index = LHS;
       return RANGE_CHECK_LOWER;
     }
     return RANGE_CHECK_UNKNOWN;
 
   case ICmpInst::ICMP_SLT:
     std::swap(LHS, RHS);
     LLVM_FALLTHROUGH;
   case ICmpInst::ICMP_SGT:
+    IsSigned = true;
     if (match(RHS, m_ConstantInt<-1>())) {
       Index = LHS;
       return RANGE_CHECK_LOWER;
     }
 
     if (IsNonNegativeAndNotLoopVarying(LHS)) {
       Index = RHS;
       Length = LHS;
       return RANGE_CHECK_UPPER;
     }
     return RANGE_CHECK_UNKNOWN;
 
   case ICmpInst::ICMP_ULT:
     std::swap(LHS, RHS);
     LLVM_FALLTHROUGH;
   case ICmpInst::ICMP_UGT:
+    IsSigned = false;
     if (IsNonNegativeAndNotLoopVarying(LHS)) {
       Index = RHS;
       Length = LHS;
       return RANGE_CHECK_BOTH;
     }
     return RANGE_CHECK_UNKNOWN;
   }
 
extractRangeChecksFromCond(L, SE, cast<User>(Condition)->getOperandUse(1),
                                SubChecks, Visited);
 
     if (SubChecks.size() == 2) {
       // Handle a special case where we know how to merge two checks separately
       // checking the upper and lower bounds into a full range check.
       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
         // together they form a RANGE_CHECK_BOTH.
         SubChecks[0].Kind =
             (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();
       }
     }
 
     Checks.insert(Checks.end(), SubChecks.begin(), SubChecks.end());
     return;
   }
 
   ICmpInst *ICI = dyn_cast<ICmpInst>(Condition);
   if (!ICI)
     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;
 
   const auto *IndexAddRec = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(Index));
   bool IsAffineIndex =
       IndexAddRec && (IndexAddRec->getLoop() == L) && IndexAddRec->isAffine();
 
   if (!IsAffineIndex)
     return;
 
   InductiveRangeCheck IRC;
   IRC.Length = Length;
   IRC.Offset = IndexAddRec->getStart();
   IRC.Scale = IndexAddRec->getStepRecurrence(SE);
   IRC.CheckUse = &ConditionUse;
   IRC.Kind = RCKind;
+  IRC.IsSigned = IsSigned;
   Checks.push_back(IRC);
 }
 
 void InductiveRangeCheck::extractRangeChecksFromBranch(
     BranchInst *BI, Loop *L, ScalarEvolution &SE, BranchProbabilityInfo &BPI,
     SmallVectorImpl<InductiveRangeCheck> &Checks) {
   if (BI->isUnconditional() || BI->getParent() == L->getLoopLatch())
     return;
if (IsIncreasing) {
     if (!FoundExpectedPred) {
       FailureReason = "expected icmp slt semantically, found something else";
       return None;
     }
 
     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;
     }
 
     // The predicate that we need to check that the induction variable lies
     // within bounds.
     ICmpInst::Predicate BoundPred =
if (IsIncreasing) {
     if (!FoundExpectedPred) {
       FailureReason = "expected icmp sgt semantically, found something else";
       return None;
     }
 
     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;
     }
 
     // The predicate that we need to check that the induction variable lies
     // within bounds.
     ICmpInst::Predicate BoundPred =
if (Value *V = getLength()) {
     UpperLimit = SE.getConstant(APInt::getSignedMaxValue(BitWidth));
   }
 
   const SCEV *End = SE.getMinusSCEV(UpperLimit, M);
   return InductiveRangeCheck::Range(Begin, End);
 }
 
 static Optional<InductiveRangeCheck::Range>
-IntersectRange(ScalarEvolution &SE,
+IntersectSignedRange(ScalarEvolution &SE,
                      const Optional<InductiveRangeCheck::Range> &R1,
                      const InductiveRangeCheck::Range &R2) {
   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(SE, /* IsSigned */ true) &&
IntersectSignedRange(ScalarEvolution &SE,
 
   // If the resulting range is empty, just return None.
   auto Ret = InductiveRangeCheck::Range(NewBegin, NewEnd);
   if (Ret.isEmpty(SE, /* IsSigned */ true))
     return None;
   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;
 
   if (L->getBlocks().size() >= LoopSizeCutoff) {
     DEBUG(dbgs() << "irce: giving up constraining loop, too large\n";);
     return false;
   }
bool InductiveRangeCheckElimination::runOnLoop(Loop *L, LPPassManager &LPM) {
   LoopStructure LS = MaybeLoopStructure.getValue();
   const SCEVAddRecExpr *IndVar =
       cast<SCEVAddRecExpr>(SE.getMinusSCEV(SE.getSCEV(LS.IndVarBase), SE.getSCEV(LS.IndVarStep)));
 
   Optional<InductiveRangeCheck::Range> SafeIterRange;
   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()) {
         assert(
             !MaybeSafeIterRange.getValue().isEmpty(SE, LS.IsSignedPredicate) &&
             "We should never return empty ranges!");
         RangeChecksToEliminate.push_back(IRC);
         SafeIterRange = MaybeSafeIterRange.getValue();

llvm/trunk/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
+; RUN: opt -verify-loop-info -irce-print-changed-loops -irce -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() {
 entry:
   %indvars.iv.next467 = add nuw nsw i64 2, 1
   %length.i167 = load i32, i32 addrspace(1)* undef, align 8
   %tmp21 = zext i32 %length.i167 to i64
   %tmp34 = load atomic i32, i32 addrspace(1)* undef unordered, align 4
   %tmp35 = add i32 %tmp34, -9581
   %tmp36 = icmp ugt i32 %length.i167, 1
   br i1 %tmp36, label %preheader, label %exit
 
 exit:                                          ; preds = %in_bounds, %loop, %not_zero, %entry
   ret void
 
 preheader:                                 ; preds = %entry
 ; CHECK:      preheader:
 ; CHECK-NEXT:   %length_gep.i146 = getelementptr inbounds i8, i8 addrspace(1)* undef, i64 8
 ; CHECK-NEXT:   %length_gep_typed.i147 = bitcast i8 addrspace(1)* undef to i32 addrspace(1)*
 ; CHECK-NEXT:   %tmp43 = icmp ult i64 %indvars.iv.next467, %tmp21
-; CHECK-NEXT:   br i1 false, label %loop.preheader, label %main.pseudo.exit
+; CHECK-NEXT:   [[C0:%[^ ]+]] = icmp ugt i64 %tmp21, 1
+; CHECK-NEXT:   %exit.mainloop.at = select i1 [[C0]], i64 %tmp21, i64 1
+; CHECK-NEXT:   [[C1:%[^ ]+]] = icmp ult i64 1, %exit.mainloop.at
+; CHECK-NEXT:   br i1 [[C1]], label %loop.preheader, label %main.pseudo.exit
 
   %length_gep.i146 = getelementptr inbounds i8, i8 addrspace(1)* undef, i64 8
   %length_gep_typed.i147 = bitcast i8 addrspace(1)* undef to i32 addrspace(1)*
   %tmp43 = icmp ult i64 %indvars.iv.next467, %tmp21
   br label %loop
 
 not_zero:                                       ; preds = %in_bounds
 ; CHECK:      not_zero:
 ; CHECK:        %tmp56 = icmp ult i64 %indvars.iv.next, %tmp21
-; CHECK-NEXT:   [[COND:%[^ ]+]] = icmp ult i64 %indvars.iv.next, 1
+; CHECK-NEXT:   [[COND:%[^ ]+]] = icmp ult i64 %indvars.iv.next, %exit.mainloop.at
 ; CHECK-NEXT:   br i1 [[COND]], label %loop, label %main.exit.selector
 
   %tmp51 = trunc i64 %indvars.iv.next to i32
   %tmp53 = mul i32 %tmp51, %tmp51
   %tmp54 = add i32 %tmp53, -9582
   %tmp55 = add i32 %tmp54, %tmp62
   %tmp56 = icmp ult i64 %indvars.iv.next, %tmp21
   br i1 %tmp56, label %loop, label %exit

llvm/trunk/test/Transforms/IRCE/correct-loop-info.ll

 ; CHECK:       innerheader.preheader:
 ; CHECK-NEXT:    br label [[INNERHEADER:%.*]]
 ; CHECK:       innerheader:
 ; CHECK-NEXT:    [[TMP4:%.*]] = phi i32 [ [[TMP6:%.*]], [[BB8:%.*]] ], [ [[TMP4_PRELOOP_COPY:%.*]], [[INNERHEADER_PREHEADER]] ]
 ; CHECK-NEXT:    invoke void @pluto()
 ; CHECK-NEXT:    to label [[BB5:%.*]] unwind label %outer_exiting.loopexit.split-lp.loopexit.split-lp
 ; CHECK:       bb5:
 ; CHECK-NEXT:    [[TMP6]] = add i32 [[TMP4]], 1
-; CHECK-NEXT:    [[TMP7:%.*]] = icmp ult i32 [[TMP6]], 1
+; CHECK-NEXT:    [[TMP7:%.*]] = icmp slt i32 [[TMP6]], 1
 ; CHECK-NEXT:    br i1 true, label [[BB8]], label [[EXIT3_LOOPEXIT5:%.*]]
 ; CHECK:       bb8:
 ; CHECK-NEXT:    [[TMP9:%.*]] = icmp slt i32 [[TMP6]], 84
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i32 [[TMP6]], 0
 ; CHECK-NEXT:    br i1 [[TMP1]], label [[INNERHEADER]], label [[MAIN_EXIT_SELECTOR:%.*]]
 ; CHECK:       main.exit.selector:
 ; CHECK-NEXT:    [[TMP6_LCSSA:%.*]] = phi i32 [ [[TMP6]], [[BB8]] ]
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp slt i32 [[TMP6_LCSSA]], 84

 ; CHECK:       exit2:
 ; CHECK-NEXT:    ret void
 ; CHECK:       innerheader.preloop:
 ; CHECK-NEXT:    [[TMP4_PRELOOP:%.*]] = phi i32 [ [[TMP6_PRELOOP:%.*]], [[BB8_PRELOOP:%.*]] ], [ undef, [[INNERHEADER_PRELOOP_PREHEADER]] ]
 ; CHECK-NEXT:    invoke void @pluto()
 ; CHECK-NEXT:    to label [[BB5_PRELOOP:%.*]] unwind label [[OUTER_EXITING_LOOPEXIT:%.*]]
 ; CHECK:       bb5.preloop:
 ; CHECK-NEXT:    [[TMP6_PRELOOP]] = add i32 [[TMP4_PRELOOP]], 1
-; CHECK-NEXT:    [[TMP7_PRELOOP:%.*]] = icmp ult i32 [[TMP6_PRELOOP]], 1
+; CHECK-NEXT:    [[TMP7_PRELOOP:%.*]] = icmp slt i32 [[TMP6_PRELOOP]], 1
 ; CHECK-NEXT:    br i1 [[TMP7_PRELOOP]], label [[BB8_PRELOOP]], label [[EXIT3_LOOPEXIT:%.*]]
 ; CHECK:       bb8.preloop:
 ; CHECK-NEXT:    [[TMP9_PRELOOP:%.*]] = icmp slt i32 [[TMP6_PRELOOP]], 84
 ; CHECK-NEXT:    [[TMP3:%.*]] = icmp slt i32 [[TMP6_PRELOOP]], -1
 ; CHECK-NEXT:    br i1 [[TMP3]], label [[INNERHEADER_PRELOOP]], label [[PRELOOP_EXIT_SELECTOR:%.*]], !llvm.loop !0, !irce.loop.clone !5
 ; CHECK:       preloop.exit.selector:
 ; CHECK-NEXT:    [[TMP6_PRELOOP_LCSSA:%.*]] = phi i32 [ [[TMP6_PRELOOP]], [[BB8_PRELOOP]] ]
 ; CHECK-NEXT:    [[TMP4:%.*]] = icmp slt i32 [[TMP6_PRELOOP_LCSSA]], 84
 ; CHECK-NEXT:    br i1 [[TMP4]], label [[PRELOOP_PSEUDO_EXIT]], label [[BB13]]
 ; CHECK:       preloop.pseudo.exit:
 ; CHECK-NEXT:    [[TMP4_PRELOOP_COPY]] = phi i32 [ undef, [[BB2]] ], [ [[TMP6_PRELOOP_LCSSA]], [[PRELOOP_EXIT_SELECTOR]] ]
 ; CHECK-NEXT:    [[INDVAR_END]] = phi i32 [ undef, [[BB2]] ], [ [[TMP6_PRELOOP_LCSSA]], [[PRELOOP_EXIT_SELECTOR]] ]
 ; CHECK-NEXT:    br label [[MAINLOOP]]
 ; CHECK:       postloop:
 ; CHECK-NEXT:    br label [[INNERHEADER_POSTLOOP:%.*]]
 ; CHECK:       innerheader.postloop:
 ; CHECK-NEXT:    [[TMP4_POSTLOOP:%.*]] = phi i32 [ [[TMP6_POSTLOOP:%.*]], [[BB8_POSTLOOP:%.*]] ], [ [[TMP4_COPY]], [[POSTLOOP]] ]
 ; CHECK-NEXT:    invoke void @pluto()
 ; CHECK-NEXT:    to label [[BB5_POSTLOOP:%.*]] unwind label %outer_exiting.loopexit.split-lp.loopexit
 ; CHECK:       bb5.postloop:
 ; CHECK-NEXT:    [[TMP6_POSTLOOP]] = add i32 [[TMP4_POSTLOOP]], 1
-; CHECK-NEXT:    [[TMP7_POSTLOOP:%.*]] = icmp ult i32 [[TMP6_POSTLOOP]], 1
+; CHECK-NEXT:    [[TMP7_POSTLOOP:%.*]] = icmp slt i32 [[TMP6_POSTLOOP]], 1
 ; CHECK-NEXT:    br i1 [[TMP7_POSTLOOP]], label [[BB8_POSTLOOP]], label [[EXIT3_LOOPEXIT4:%.*]]
 ; CHECK:       bb8.postloop:
 ; CHECK-NEXT:    [[TMP9_POSTLOOP:%.*]] = icmp slt i32 [[TMP6_POSTLOOP]], 84
 ; CHECK-NEXT:    br i1 [[TMP9_POSTLOOP]], label [[INNERHEADER_POSTLOOP]], label [[BB13_LOOPEXIT:%.*]], !llvm.loop !6, !irce.loop.clone !5
 ;
 bb:
   br label %outerheader
 
 outerheader:                                              ; preds = %bb14, %bb
   %tmp = icmp slt i32 undef, 84
   br i1 %tmp, label %bb2, label %bb16
 
 bb2:                                              ; preds = %outerheader
   br label %innerheader
 
 innerheader:                                              ; preds = %bb8, %bb2
   %tmp4 = phi i32 [ %tmp6, %bb8 ], [ undef, %bb2 ]
   invoke void @pluto()
   to label %bb5 unwind label %outer_exiting
 
 bb5:                                              ; preds = %innerheader
   %tmp6 = add i32 %tmp4, 1
-  %tmp7 = icmp ult i32 %tmp6, 1
+  %tmp7 = icmp slt i32 %tmp6, 1
   br i1 %tmp7, label %bb8, label %exit3
 
 bb8:                                              ; preds = %bb5
   %tmp9 = icmp slt i32 %tmp6, 84
   br i1 %tmp9, label %innerheader, label %bb13
 
 outer_exiting:                                             ; preds = %innerheader
   %tmp11 = landingpad { i8*, i32 }

llvm/trunk/test/Transforms/IRCE/empty_ranges.ll

-; RUN: opt -verify-loop-info -irce-print-changed-loops -irce -irce-allow-unsigned-latch=true -S
-
+; RUN: opt -verify-loop-info -irce-print-changed-loops -irce -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

llvm/trunk/test/Transforms/IRCE/eq_ne.ll

-; RUN: opt -verify-loop-info -irce-print-changed-loops -irce -irce-allow-unsigned-latch=true -S < %s 2>&1 | FileCheck %s
+; RUN: opt -verify-loop-info -irce-print-changed-loops -irce -S < %s 2>&1 | FileCheck %s
 
 ; CHECK: irce: in function test_01: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
 ; CHECK: irce: in function test_01u: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
 ; CHECK-NOT: irce: in function test_02: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
 ; CHECK: irce: in function test_03: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
 ; CHECK-NOT: irce: in function test_04: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
 ; CHECK: irce: in function test_05: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
 ; CHECK-NOT: irce: in function test_06: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>

llvm/trunk/test/Transforms/IRCE/range_intersect_miscompile.ll

-; RUN: opt -irce -S < %s 2>&1 | FileCheck %s
+; RUN: opt -verify-loop-info -irce-print-changed-loops -irce -S < %s 2>&1 | FileCheck %s
 
-; This test demonstrates a miscompile: the outer loop's IV iterates in range of
-; [2, 400) and the range check is done against value 331. Due to a bug in range
-; intersection IRCE manages to eliminate the range check without inserting a
-; postloop, which is incorrect. So far IRCE is prohibited for this case.
+; CHECK-LABEL: irce: in function test_01: constrained Loop at depth 1 containing:
+; CHECK-LABEL: irce: in function test_02: constrained Loop at depth 1 containing:
+; CHECK-NOT: irce: in function test_03: constrained Loop
+; CHECK-NOT: irce: in function test_04: constrained Loop
+; CHECK-LABEL: irce: in function test_05: constrained Loop at depth 1 containing:
+
+; This test used to demonstrate a miscompile: the outer loop's IV iterates in
+; range of [2, 400) and the range check is done against value 331. Due to a bug
+; in range intersection IRCE manages to eliminate the range check without
+; inserting a postloop, which is incorrect. We treat the range of this test as
+; an unsigned range and are able to intersect ranges correctly and insert a
+; postloop.
 
 define void @test_01() {
 
 ; CHECK-LABEL: test_01
-; CHECK-NOT:   br i1 true
+; CHECK-NOT:     preloop
+; CHECK:         range_check_block:                                ; preds = %inner_loop
+; CHECK-NEXT:      %range_check = icmp slt i32 %iv, 331
+; CHECK-NEXT:      br i1 true, label %loop_latch
+; CHECK:         loop_latch:
+; CHECK-NEXT:      %iv_next = add i32 %iv, 1
+; CHECK-NEXT:      %loop_cond = icmp ult i32 %iv_next, 400
+; CHECK-NEXT:      [[COND:%[^ ]+]] = icmp ult i32 %iv_next, 331
+; CHECK-NEXT:      br i1 [[COND]], label %loop_header, label %main.exit.selector
+; CHECK:         main.exit.selector:                               ; preds = %loop_latch
+; CHECK-NEXT:      %iv_next.lcssa = phi i32 [ %iv_next, %loop_latch ]
+; CHECK-NEXT:      %iv.lcssa = phi i32 [ %iv, %loop_latch ]
+; CHECK-NEXT:      [[MES_COND:%[^ ]+]] = icmp ult i32 %iv_next.lcssa, 400
+; CHECK-NEXT:      br i1 [[MES_COND]], label %main.pseudo.exit, label %exit
+; CHECK:         loop_latch.postloop:                              ; preds = %range_check_block.postloop
+; CHECK-NEXT:      %iv_next.postloop = add i32 %iv.postloop, 1
+; CHECK-NEXT:      %loop_cond.postloop = icmp ult i32 %iv_next.postloop, 400
+; CHECK-NEXT:      br i1 %loop_cond.postloop, label %loop_header.postloop, label %exit.loopexit
 
 entry:
   br label %loop_header
 
 loop_header:                            ; preds = %loop_latch, %entry
   %iv = phi i32 [ 2, %entry ], [ %iv_next, %loop_latch ]
   %iv.prev = phi i32 [ 1, %entry ], [ %iv, %loop_latch ]
   %tmp2 = icmp sgt i32 %iv.prev, -1

 loop_latch:                                         ; preds = %range_check_block
   %iv_next = add i32 %iv, 1
   %loop_cond = icmp ult i32 %iv_next, 400
   br i1 %loop_cond, label %loop_header, label %exit
 
 deopt:                                          ; preds = %range_check_block
   ret void
 }
+
+; Similar to test_01, but here the range check is done against 450. No postloop
+; is required.
+
+define void @test_02() {
+
+; CHECK-LABEL: test_02
+; CHECK-NOT:     preloop
+; CHECK-NOT:     postloop
+; CHECK:         range_check_block:                                ; preds = %inner_loop
+; CHECK-NEXT:      %range_check = icmp slt i32 %iv, 450
+; CHECK-NEXT:      br i1 true, label %loop_latch
+; CHECK:         loop_latch:                                       ; preds = %range_check_block
+; CHECK-NEXT:      %iv_next = add i32 %iv, 1
+; CHECK-NEXT:      %loop_cond = icmp ult i32 %iv_next, 400
+; CHECK-NEXT:      br i1 %loop_cond, label %loop_header, label %exit
+
+entry:
+  br label %loop_header
+
+loop_header:                            ; preds = %loop_latch, %entry
+  %iv = phi i32 [ 2, %entry ], [ %iv_next, %loop_latch ]
+  %iv.prev = phi i32 [ 1, %entry ], [ %iv, %loop_latch ]
+  %tmp2 = icmp sgt i32 %iv.prev, -1
+  br i1 %tmp2, label %loop_header.split.us, label %exit
+
+loop_header.split.us:                   ; preds = %loop_header
+  br label %inner_loop
+
+inner_loop:                                   ; preds = %inner_loop, %loop_header.split.us
+  %inner_iv = phi i32 [ 1, %loop_header.split.us ], [ %inner_iv_next, %inner_loop ]
+  %inner_iv_next = add nuw nsw i32 %inner_iv, 1
+  %inner_cond = icmp ult i32 %inner_iv_next, 31
+  br i1 %inner_cond, label %inner_loop, label %range_check_block
+
+exit:                                            ; preds = %loop_latch, %loop_header
+  ret void
+
+range_check_block:                                          ; preds = %inner_loop
+  %range_check = icmp slt i32 %iv, 450
+  br i1 %range_check, label %loop_latch, label %deopt
+
+loop_latch:                                         ; preds = %range_check_block
+  %iv_next = add i32 %iv, 1
+  %loop_cond = icmp ult i32 %iv_next, 400
+  br i1 %loop_cond, label %loop_header, label %exit
+
+deopt:                                          ; preds = %range_check_block
+  ret void
+}
+
+; Range check is made against 0, so the safe iteration range is empty. IRCE
+; should not apply.
+
+define void @test_03() {
+
+; CHECK-LABEL: test_03
+
+entry:
+  br label %loop_header
+
+loop_header:                            ; preds = %loop_latch, %entry
+  %iv = phi i32 [ 2, %entry ], [ %iv_next, %loop_latch ]
+  %iv.prev = phi i32 [ 1, %entry ], [ %iv, %loop_latch ]
+  %tmp2 = icmp sgt i32 %iv.prev, -1
+  br i1 %tmp2, label %loop_header.split.us, label %exit
+
+loop_header.split.us:                   ; preds = %loop_header
+  br label %inner_loop
+
+inner_loop:                                   ; preds = %inner_loop, %loop_header.split.us
+  %inner_iv = phi i32 [ 1, %loop_header.split.us ], [ %inner_iv_next, %inner_loop ]
+  %inner_iv_next = add nuw nsw i32 %inner_iv, 1
+  %inner_cond = icmp ult i32 %inner_iv_next, 31
+  br i1 %inner_cond, label %inner_loop, label %range_check_block
+
+exit:                                            ; preds = %loop_latch, %loop_header
+  ret void
+
+range_check_block:                                          ; preds = %inner_loop
+  %range_check = icmp slt i32 %iv, 0
+  br i1 %range_check, label %loop_latch, label %deopt
+
+loop_latch:                                         ; preds = %range_check_block
+  %iv_next = add i32 %iv, 1
+  %loop_cond = icmp ult i32 %iv_next, 400
+  br i1 %loop_cond, label %loop_header, label %exit
+
+deopt:                                          ; preds = %range_check_block
+  ret void
+}
+
+; We do not know whether %n is positive or negative, so we prohibit IRCE in
+; order to avoid incorrect intersection of signed and unsigned ranges.
+
+define void @test_04(i32* %p) {
+
+; CHECK-LABEL: test_04
+
+entry:
+  %n = load i32, i32* %p
+  br label %loop_header
+
+loop_header:                            ; preds = %loop_latch, %entry
+  %iv = phi i32 [ 2, %entry ], [ %iv_next, %loop_latch ]
+  %iv.prev = phi i32 [ 1, %entry ], [ %iv, %loop_latch ]
+  %tmp2 = icmp sgt i32 %iv.prev, -1
+  br i1 %tmp2, label %loop_header.split.us, label %exit
+
+loop_header.split.us:                   ; preds = %loop_header
+  br label %inner_loop
+
+inner_loop:                                   ; preds = %inner_loop, %loop_header.split.us
+  %inner_iv = phi i32 [ 1, %loop_header.split.us ], [ %inner_iv_next, %inner_loop ]
+  %inner_iv_next = add nuw nsw i32 %inner_iv, 1
+  %inner_cond = icmp ult i32 %inner_iv_next, 31
+  br i1 %inner_cond, label %inner_loop, label %range_check_block
+
+exit:                                            ; preds = %loop_latch, %loop_header
+  ret void
+
+range_check_block:                                          ; preds = %inner_loop
+  %range_check = icmp slt i32 %iv, %n
+  br i1 %range_check, label %loop_latch, label %deopt
+
+loop_latch:                                         ; preds = %range_check_block
+  %iv_next = add i32 %iv, 1
+  %loop_cond = icmp ult i32 %iv_next, 400
+  br i1 %loop_cond, label %loop_header, label %exit
+
+deopt:                                          ; preds = %range_check_block
+  ret void
+}
+
+; Same as test_04, but range guarantees that %n is positive. So we can safely
+; intersect ranges (with insertion of postloop).
+
+define void @test_05(i32* %p) {
+
+; CHECK-LABEL: test_05
+; CHECK-NOT:     preloop
+; CHECK:         entry:
+; CHECK-NEXT:      %n = load i32, i32* %p, !range !6
+; CHECK-NEXT:      [[CMP_1:%[^ ]+]] = icmp ugt i32 %n, 2
+; CHECK-NEXT:      %exit.mainloop.at = select i1 [[CMP_1]], i32 %n, i32 2
+; CHECK-NEXT:      [[CMP_2:%[^ ]+]] = icmp ult i32 2, %exit.mainloop.at
+; CHECK-NEXT:      br i1 [[CMP_2]], label %loop_header.preheader, label %main.pseudo.exit
+; CHECK:         range_check_block:                                ; preds = %inner_loop
+; CHECK-NEXT:      %range_check = icmp slt i32 %iv, %n
+; CHECK-NEXT:      br i1 true, label %loop_latch, label %deopt.loopexit2
+; CHECK:         loop_latch:                                       ; preds = %range_check_block
+; CHECK-NEXT:      %iv_next = add i32 %iv, 1
+; CHECK-NEXT:      %loop_cond = icmp ult i32 %iv_next, 400
+; CHECK-NEXT:      [[COND:%[^ ]+]] = icmp ult i32 %iv_next, %exit.mainloop.at
+; CHECK-NEXT:      br i1 [[COND]], label %loop_header, label %main.exit.selector
+; CHECK:         main.exit.selector:                               ; preds = %loop_latch
+; CHECK-NEXT:      %iv_next.lcssa = phi i32 [ %iv_next, %loop_latch ]
+; CHECK-NEXT:      %iv.lcssa = phi i32 [ %iv, %loop_latch ]
+; CHECK-NEXT:      [[MES_COND:%[^ ]+]] = icmp ult i32 %iv_next.lcssa, 400
+; CHECK-NEXT:      br i1 [[MES_COND]], label %main.pseudo.exit, label %exit
+; CHECK:         loop_latch.postloop:                              ; preds = %range_check_block.postloop
+; CHECK-NEXT:      %iv_next.postloop = add i32 %iv.postloop, 1
+; CHECK-NEXT:      %loop_cond.postloop = icmp ult i32 %iv_next.postloop, 400
+; CHECK-NEXT:      br i1 %loop_cond.postloop, label %loop_header.postloop, label %exit.loopexit
+
+entry:
+  %n = load i32, i32* %p, !range !0
+  br label %loop_header
+
+loop_header:                            ; preds = %loop_latch, %entry
+  %iv = phi i32 [ 2, %entry ], [ %iv_next, %loop_latch ]
+  %iv.prev = phi i32 [ 1, %entry ], [ %iv, %loop_latch ]
+  %tmp2 = icmp sgt i32 %iv.prev, -1
+  br i1 %tmp2, label %loop_header.split.us, label %exit
+
+loop_header.split.us:                   ; preds = %loop_header
+  br label %inner_loop
+
+inner_loop:                                   ; preds = %inner_loop, %loop_header.split.us
+  %inner_iv = phi i32 [ 1, %loop_header.split.us ], [ %inner_iv_next, %inner_loop ]
+  %inner_iv_next = add nuw nsw i32 %inner_iv, 1
+  %inner_cond = icmp ult i32 %inner_iv_next, 31
+  br i1 %inner_cond, label %inner_loop, label %range_check_block
+
+exit:                                            ; preds = %loop_latch, %loop_header
+  ret void
+
+range_check_block:                                          ; preds = %inner_loop
+  %range_check = icmp slt i32 %iv, %n
+  br i1 %range_check, label %loop_latch, label %deopt
+
+loop_latch:                                         ; preds = %range_check_block
+  %iv_next = add i32 %iv, 1
+  %loop_cond = icmp ult i32 %iv_next, 400
+  br i1 %loop_cond, label %loop_header, label %exit
+
+deopt:                                          ; preds = %range_check_block
+  ret void
+}
+
+!0 = !{i32 0, i32 50}

llvm/trunk/test/Transforms/IRCE/stride_more_than_1.ll

-; RUN: opt -verify-loop-info -irce-print-changed-loops -irce -irce-allow-unsigned-latch=true -S < %s 2>&1 | FileCheck %s
+; RUN: opt -verify-loop-info -irce-print-changed-loops -irce -S < %s 2>&1 | FileCheck %s
 
 ; 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>
 ; CHECK: irce: in function test_03: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
 ; CHECK-NOT: irce: in function test_04: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
 ; CHECK: irce: in function test_05: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
 ; CHECK: irce: in function test_06: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
 ; CHECK-NOT: irce: in function test_07: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>

llvm/trunk/test/Transforms/IRCE/unsigned_comparisons_ugt.ll

-; RUN: opt -verify-loop-info -irce-print-changed-loops -irce -irce-allow-unsigned-latch=true -S < %s 2>&1 | FileCheck %s
+; RUN: opt -verify-loop-info -irce-print-changed-loops -irce -S < %s 2>&1 | FileCheck %s
 
 ; 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>
 ; CHECK: irce: in function test_03: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
 ; CHECK: irce: in function test_04: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
 ; CHECK-NOT: irce: in function test_05: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
 ; CHECK: irce: in function test_06: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
 

llvm/trunk/test/Transforms/IRCE/unsigned_comparisons_ult.ll

-; RUN: opt -verify-loop-info -irce-print-changed-loops -irce -irce-allow-unsigned-latch=true -S < %s 2>&1 | FileCheck %s
+; RUN: opt -verify-loop-info -irce-print-changed-loops -irce -S < %s 2>&1 | FileCheck %s
 
 ; 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>
 ; CHECK: irce: in function test_03: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
 ; CHECK: irce: in function test_04: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
 ; CHECK: irce: in function test_05: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
 ; CHECK: irce: in function test_06: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
 ; CHECK-NOT: irce: in function test_07: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
+; CHECK: irce: in function test_08: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
+; CHECK-NOT: irce: in function test_09: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
 
 ; ULT condition for increasing loop.
 define void @test_01(i32* %arr, i32* %a_len_ptr) #0 {
 
 ; CHECK:      test_01
 ; CHECK:        entry:
 ; CHECK-NEXT:     %exit.mainloop.at = load i32, i32* %a_len_ptr, !range !0
 ; CHECK-NEXT:     [[COND:%[^ ]+]] = icmp ult i32 0, %exit.mainloop.at

 
 out.of.bounds:
   ret void
 
 exit:
   ret void
 }
 
+; Unsigned walking through signed border is allowed.
+; Iteration space [0; UINT_MAX - 99), the fact that SINT_MAX is within this
+; range does not prevent us from performing IRCE.
+
+define void @test_08(i32* %arr, i32* %a_len_ptr) #0 {
+
+; CHECK:      test_08
+; CHECK:        entry:
+; CHECK-NEXT:     %exit.mainloop.at = load i32, i32* %a_len_ptr, !range !0
+; CHECK-NEXT:     [[COND:%[^ ]+]] = icmp ult i32 0, %exit.mainloop.at
+; CHECK-NEXT:     br i1 [[COND]], label %loop.preheader, label %main.pseudo.exit
+; CHECK:        loop:
+; CHECK-NEXT:     %idx = phi i32 [ %idx.next, %in.bounds ], [ 0, %loop.preheader ]
+; CHECK-NEXT:     %idx.next = add i32 %idx, 1
+; CHECK-NEXT:     %abc = icmp ult i32 %idx, %exit.mainloop.at
+; CHECK-NEXT:     br i1 true, label %in.bounds, label %out.of.bounds.loopexit1
+; CHECK-NOT:    loop.preloop:
+; CHECK:        loop.postloop:
+; CHECK-NEXT:     %idx.postloop = phi i32 [ %idx.copy, %postloop ], [ %idx.next.postloop, %in.bounds.postloop ]
+; CHECK-NEXT:     %idx.next.postloop = add i32 %idx.postloop, 1
+; CHECK-NEXT:     %abc.postloop = icmp ult i32 %idx.postloop, %exit.mainloop.at
+; CHECK-NEXT:     br i1 %abc.postloop, label %in.bounds.postloop, label %out.of.bounds.loopexit
+
+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 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.next, -100
+  br i1 %next, label %loop, label %exit
+
+out.of.bounds:
+  ret void
+
+exit:
+  ret void
+}
+
+; Walking through the border of unsigned range is not allowed
+; (iteration space [-100; 100)). Negative test.
+
+define void @test_09(i32* %arr, i32* %a_len_ptr) #0 {
+
+; CHECK:      test_09
+; CHECK-NOT:  preloop
+; CHECK-NOT:  postloop
+; CHECK-NOT:  br i1 false
+; CHECK-NOT:  br i1 true
+
+entry:
+  %len = load i32, i32* %a_len_ptr, !range !0
+  br label %loop
+
+loop:
+  %idx = phi i32 [ -100, %entry ], [ %idx.next, %in.bounds ]
+  %idx.next = add 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.next, 100
+  br i1 %next, label %loop, label %exit
+
+out.of.bounds:
+  ret void
+
+exit:
+  ret void
+}
+
 !0 = !{i32 0, i32 50}