Make ScalarEvolution::isKnownPredicate a little smarter

[hfinkel]

Summary

First, the motivation for this patch is to allow LLVM to optimize this code as one might hope:

void foo (int *a, int *b, int n) {
  for (int i = 0; i < n; ++i) {
    if (i > n)
      a[i] = b[i] + 1;
  }
}

As i is less than n in the loop, the conditional (i > n) can be folded to false.

With this relatively-simple change, we can perform the simplification in the default pipeline: indvars can perform the folding using SCEV.

Now the obvious question is: is it correct? For now, I've XFAIL'ed two tests:

I believe that the test/Transforms/IndVarSimplify/backedge-on-min-max.ll changes are legitimate (some of the loops in those tests are actually infinite loops, this change causes indvars to make that explicit instead of making other changes - unfortunately, I've been unable to fix the tests to serve their original purpose).

The test/Transforms/LoopStrengthReduce/X86/pr17473.ll changes look more dubious, and I'd certainly appreciate a second opinion. I'll attach some screen shots with the diffs.

[hfinkel]

To hopefully make things easier, I've attached screenshots of the diffs of the changed tests.

-Hal

• Original Message -----

From: [e-mail]
To: [e-mail], [e-mail], [e-mail]
Cc: [e-mail]
Sent: Monday, August 17, 2015 2:41:38 AM
Subject: [PATCH] D12073: Make ScalarEvolution::isKnownPredicate a little smarter

hfinkel created this revision.
hfinkel added reviewers: sanjoy, atrick.
hfinkel added a subscriber: llvm-commits.
hfinkel set the repository for this revision to rL LLVM.
Herald added a subscriber: sanjoy.

First, the motivation for this patch is to allow LLVM to optimize
this code as one might hope:

void foo (int *a, int *b, int n) {
  for (int i = 0; i < n; ++i) {
    if (i > n)
      a[i] = b[i] + 1;
  }
}

As i is less than n in the loop, the conditional (i > n) can be
folded to false.

With this relatively-simple change, we can perform the simplification
in the default pipeline: indvars can perform the folding using SCEV.

Now the obvious question is: is it correct? For now, I've XFAIL'ed
two tests:

I believe that the
test/Transforms/IndVarSimplify/backedge-on-min-max.ll changes are
legitimate (some of the loops in those tests are actually infinite
loops, this change causes indvars to make that explicit instead of
making other changes - unfortunately, I've been unable to fix the
tests to serve their original purpose).

The test/Transforms/LoopStrengthReduce/X86/pr17473.ll changes look
more dubious, and I'd certainly appreciate a second opinion. I'll
attach some screen shots with the diffs.

Repository:

rL LLVM

http://reviews.llvm.org/D12073

Files:

lib/Analysis/ScalarEvolution.cpp
test/Transforms/IndVarSimplify/backedge-on-min-max.ll
test/Transforms/IndVarSimplify/bec-cmp.ll
test/Transforms/LoopStrengthReduce/X86/pr17473.ll

[sanjoy]

I'd solve this differently -- if I understand the problem correctly, you should really only need to teach SCEV that {0,+,1}<nsw> is slt {1,+,1}<nsw> (or something similar to that) in isImpliedCondOperandsHelper.

lib/Analysis/ScalarEvolution.cpp

6873

This should probably live in ScalarEvolution::isKnownPredicate or ScalarEvolution::isImpliedCondOperandsHelper, not here.

6892

I'm not sure this is sound w.r.t. overflow. For instance, if LHS = i8 127 and RHS = i8 -1 then !(LHS < RHS) but LHS - RHS = i8 128 < 0

6904

Same comment as above on overflow.

[hfinkel]

In D12073#225873, @sanjoy wrote:

I'd solve this differently -- if I understand the problem correctly, you should really only need to teach SCEV that {0,+,1}<nsw> is slt {1,+,1}<nsw> (or something similar to that) in isImpliedCondOperandsHelper.

That's correct (but it triggers in some other cases too); I need to look at this in more detail, but a quick check reveals that for this code:

$ cat /tmp/t.c
void foo (int *a, int *b, int n) {
  for (int i = 0; i < n; ++i) {
    if (i > n)
      a[i] = b[i] + 1;
  }
}

these statements trigger to do the following:

• proving that {0,+,1}<nuw><nsw><%for.body> sle {1,+,1}<nuw><nsw><%for.body> (the subtraction simplifies to -1)
• proving that (sext i32 %n to i64) sle (1 + (sext i32 %n to i64))<nsw> (again, the subtraction simplifies to -1)

for this code (which differs from the above only by the +4):

$ cat /tmp/t4.c
void foo (int *a, int *b, int n) {
  for (int i = 0; i < n; ++i) {
    if (i > n + 4)
      a[i] = b[i] + 1;
  }
}

this code is used to:

• prove that %n sle (4 + %n) (the subtraction simplifies to -4)
• prove that {0,+,1}<nuw><nsw><%for.body> sle {1,+,1}<nuw><nsw><%for.body> (the subtraction simplifies to -1)

In the pr17473.ll test case, the statements trigger to:

• prove that 0 sle {1,+,1}<%for.body> (the subtraction simplifies to {-1,+,-1}<%for.body>
• prove that 127 sle {-2,+,-1}<%for.body> (the subtraction simplifies to {-127,+,1}<%for.body>)

That last one does indeed seem wrong (certainly justifying your point below).

lib/Analysis/ScalarEvolution.cpp

6873

I put these here as they exactly mirror the check done below as part of the ICmpInst::ICMP_NE case below (which could certainly also be moved if we'd like).

6892

This is precisely what was worrying me w.r.t. to correctness, and given the output, it seems this is exactly what happens. Sign-extending first would fix that, right?

[hfinkel]

To look at this a bit more (i.e. why does this actually make the test case pass), we have this:

SimplifyIndvar::eliminateIVComparison has this code:

} else if (SE->isKnownPredicate(ICmpInst::getInversePredicate(Pred), S, X)) {
  ICmp->replaceAllUsesWith(ConstantInt::getFalse(ICmp->getContext()));
  DeadInsts.emplace_back(ICmp);
  DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n');

Pred is CmpInst::ICMP_SGT, so the inverse predicate is ICMP_SLE.

And is calling it with:

S = {0,+,1}<nuw><nsw><%for.body> and X = %n

ScalarEvolution::isKnownPredicate first calls SimplifyICmpOperands, which rewrites LHS and RHS to be:

LHS = {-1,+,1}<nsw><%for.body>, RHS = %n, and sets Pred = CmpInst::ICMP_SLT

ScalarEvolution::isKnownPredicate then ends of here:

if (LAR) {
  const Loop *L = LAR->getLoop();
  if (isLoopEntryGuardedByCond(L, Pred, LAR->getStart(), RHS) &&
      isLoopBackedgeGuardedByCond(L, Pred, LAR->getPostIncExpr(*this), RHS)) {
    if (!RAR) return true;

(where RAR is nullptr here because %n is not an AddRec).

At this point, we end up in ScalarEvolution::isLoopBackedgeGuardedByCond where
we have:

Pred = CmpInst::ICMP_SLT, LHS = {0,+,1}<nuw><nsw><%for.body> and RHS = %n

ScalarEvolution::isLoopBackedgeGuardedByCond finds the loop backedge predicate:

br i1 %cmp, label %for.body, label %for.cond.for.cond.cleanup_crit_edge

being fed by:

%cmp = icmp slt i32 %inc, %n

and calls ScalarEvolution::isImpliedCond, and that calls ScalarEvolution::isImpliedCondOperands with:

FoundLHS = {1,+,1}<nuw><nsw><%for.body>, FoundRHS = %n

where we still have:

LHS = {0,+,1}<nuw><nsw><%for.body>, RHS = %n

that calls ScalarEvolution::isImpliedCondOperandsHelper, and that ends up here:

case ICmpInst::ICMP_SLT:
case ICmpInst::ICMP_SLE:
  if (IsKnownPredicateFull(ICmpInst::ICMP_SLE, LHS, FoundLHS) &&
      IsKnownPredicateFull(ICmpInst::ICMP_SGE, RHS, FoundRHS))
    return true;

IsKnownPredicateFull is this lambda function:

auto IsKnownPredicateFull =
  [this](ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS) {
    return isKnownPredicateWithRanges(Pred, LHS, RHS) ||
           IsKnownPredicateViaMinOrMax(*this, Pred, LHS, RHS);
};

and it is this call to ScalarEvolution::isKnownPredicateWithRanges, with:

LHS = {0,+,1}<nuw><nsw><%for.body> and RHS = {1,+,1}<nuw><nsw><%for.body> that the code added in this patch triggers to provide an answer we could not previously provide.

And so, yes, you're right, putting this logic in isImpliedCondOperandsHelper seems like a practical place.

lib/Analysis/ScalarEvolution.cpp

6892

As it turns out, sign extending works, but can't be used here. The problem is that, under certain circumstances, getSignExtendExpr calls isLoopBackedgeGuardedByCond, and that calls isKnownPredicateWithRanges (yielding an infinite recursion).

[hfinkel]

As suggested, move logic into ScalarEvolution::isImpliedCondOperandsHelper, and sign-extend before the subtraction to deal with potential overflow in the subtraction.

There are now three failing tests, mostly due to IV widening that now does not happen. The new known-predicate results are:

test/Transforms/IndVarSimplify/elim-extend.ll:

• {%init,+,1}<nsw><%loop> sle {(1 + %init),+,1}<nsw><%loop>
• {(sext i32 %init to i64),+,1}<nsw><%loop> sle {(1 + (sext i32 %init to i64)),+,1}<nsw><%loop>
• {-1,+,1}<nsw><%outerloop> sle {1,+,1}<nuw><%outerloop>
• {-1,+,1}<nsw><%outerloop> sle {1,+,1}<nuw><nsw><%outerloop>

test/Transforms/IndVarSimplify/iv-sext.ll:

• {-1,+,1}<nsw><%bb> sle {1,+,1}<nuw><%bb>
• {-1,+,1}<nsw><%bb> sle {1,+,1}<nuw><nsw><%bb>

test/Transforms/IndVarSimplify/strengthen-overflow.ll:

• {%init,+,1}<nsw><%loop> sle {(1 + %init),+,1}<nsw><%loop>

These look right, but some consumer of the information seems to make a worse no-wrap deductions as a result (thus, this patch is still WIP).

[sanjoy]

In D12073#226151, @hfinkel wrote:

There are now three failing tests, mostly due to IV widening that now does not happen. The new known-predicate results are:

test/Transforms/IndVarSimplify/elim-extend.ll:

• {%init,+,1}<nsw><%loop> sle {(1 + %init),+,1}<nsw><%loop>
• {(sext i32 %init to i64),+,1}<nsw><%loop> sle {(1 + (sext i32 %init to i64)),+,1}<nsw><%loop>
• {-1,+,1}<nsw><%outerloop> sle {1,+,1}<nuw><%outerloop>
• {-1,+,1}<nsw><%outerloop> sle {1,+,1}<nuw><nsw><%outerloop>

test/Transforms/IndVarSimplify/iv-sext.ll:

• {-1,+,1}<nsw><%bb> sle {1,+,1}<nuw><%bb>
• {-1,+,1}<nsw><%bb> sle {1,+,1}<nuw><nsw><%bb>

test/Transforms/IndVarSimplify/strengthen-overflow.ll:

• {%init,+,1}<nsw><%loop> sle {(1 + %init),+,1}<nsw><%loop>

These look right, but some consumer of the information seems to make a worse no-wrap deductions as a result (thus, this patch is still WIP).

I suspect (haven't verified) this is due to SCEV's caching mechanism. You end up creating a "Sext(LHS)" too soon, before proving all of the things needed to show that LHS is nsw. Then this suboptimal result gets cached.

In other words, I suspect the stack trace looks like this (youngest frame at top) initially:

== false because of PendingLoopPredicates, set in frame (A)
getImpliedCond(...)  // ends up looking at VAL
getLoopBackedgeCount(...)
getSignExtend(VAL)  // due to your change
getImpliedCond(...)  // ends up looking at VAL .. (A)
getLoopBackedgeCount(...)
getSignExtend(VAL)

This goes on as

  getSignExtend(VAL)  ==> no simplification, and we end up with
        UniqueSCEVs[(SignExtend, VAL)] = SignExtendExpr VAL, and
	does not set the <nsw> bit in VAL
  getImpliedCond(...)  // ends up looking at VAL .. (A)
  getLoopBackedgeCount(...)
  getSignExtend(VAL)

And then finally the oldest frame returns:

getSignExtend(VAL)  // this returns a widened version of VAL (instead of
  an explicit sign extend), and also set VAL's nsw bit

However, the damage has been done since UniqueSCEVs[(SignExtend, VAL)] == (SignExtendExpr VAL) and that's the value ScalarEvolution::getSignExtendExpr will return from now on.

If you implement your check without actually creating a sign extend, but by directly inferring no-overflow from the nsw or nuw flags, then I suspect this won't happen.

lib/Analysis/ScalarEvolution.cpp

7355

I think this change would be cleaner if SignedDiff took explicit LHS and RHS arguments.

[hfinkel]

In D12073#226385, @sanjoy wrote:

In D12073#226151, @hfinkel wrote:

There are now three failing tests, mostly due to IV widening that now does not happen. The new known-predicate results are:

test/Transforms/IndVarSimplify/elim-extend.ll:

• {%init,+,1}<nsw><%loop> sle {(1 + %init),+,1}<nsw><%loop>
• {(sext i32 %init to i64),+,1}<nsw><%loop> sle {(1 + (sext i32 %init to i64)),+,1}<nsw><%loop>
• {-1,+,1}<nsw><%outerloop> sle {1,+,1}<nuw><%outerloop>
• {-1,+,1}<nsw><%outerloop> sle {1,+,1}<nuw><nsw><%outerloop>

test/Transforms/IndVarSimplify/iv-sext.ll:

• {-1,+,1}<nsw><%bb> sle {1,+,1}<nuw><%bb>
• {-1,+,1}<nsw><%bb> sle {1,+,1}<nuw><nsw><%bb>

test/Transforms/IndVarSimplify/strengthen-overflow.ll:

• {%init,+,1}<nsw><%loop> sle {(1 + %init),+,1}<nsw><%loop>

These look right, but some consumer of the information seems to make a worse no-wrap deductions as a result (thus, this patch is still WIP).

I suspect (haven't verified) this is due to SCEV's caching mechanism. You end up creating a "Sext(LHS)" too soon, before proving all of the things needed to show that LHS is nsw. Then this suboptimal result gets cached.

In other words, I suspect the stack trace looks like this (youngest frame at top) initially:

== false because of PendingLoopPredicates, set in frame (A)
getImpliedCond(...)  // ends up looking at VAL
getLoopBackedgeCount(...)
getSignExtend(VAL)  // due to your change
getImpliedCond(...)  // ends up looking at VAL .. (A)
getLoopBackedgeCount(...)
getSignExtend(VAL)

This goes on as

  getSignExtend(VAL)  ==> no simplification, and we end up with
        UniqueSCEVs[(SignExtend, VAL)] = SignExtendExpr VAL, and
	does not set the <nsw> bit in VAL
  getImpliedCond(...)  // ends up looking at VAL .. (A)
  getLoopBackedgeCount(...)
  getSignExtend(VAL)

And then finally the oldest frame returns:

getSignExtend(VAL)  // this returns a widened version of VAL (instead of
  an explicit sign extend), and also set VAL's nsw bit

However, the damage has been done since UniqueSCEVs[(SignExtend, VAL)] == (SignExtendExpr VAL) and that's the value ScalarEvolution::getSignExtendExpr will return from now on.

If you implement your check without actually creating a sign extend, but by directly inferring no-overflow from the nsw or nuw flags, then I suspect this won't happen.

Looking at the test/Transforms/IndVarSimplify/strengthen-overflow.ll test case, for example, here's (in part) what is going on, at least in terms of initial behavior:

SimplifyIndvar::strengthenOverflowingOperation has code that looks like this:

if (!BO->hasNoUnsignedWrap()) {
  const SCEV *ExtendAfterOp = SE->getZeroExtendExpr(SE->getSCEV(BO), WideTy);
  const SCEV *OpAfterExtend = (SE->*GetExprForBO)(
    SE->getZeroExtendExpr(LHS, WideTy), SE->getZeroExtendExpr(RHS, WideTy),
    SCEV::FlagAnyWrap);
  if (ExtendAfterOp == OpAfterExtend) {
    BO->setHasNoUnsignedWrap();
    SE->forgetValue(BO);
    Changed = true;
  }
}

if (!BO->hasNoSignedWrap()) {
  const SCEV *ExtendAfterOp = SE->getSignExtendExpr(SE->getSCEV(BO), WideTy);
  const SCEV *OpAfterExtend = (SE->*GetExprForBO)(
    SE->getSignExtendExpr(LHS, WideTy), SE->getSignExtendExpr(RHS, WideTy),
    SCEV::FlagAnyWrap);
  if (ExtendAfterOp == OpAfterExtend) {
    BO->setHasNoSignedWrap();
    SE->forgetValue(BO);
    Changed = true;
  }
}

Now the fun part is that the new code actually triggers as part of the checks done under if (!BO->hasNoUnsignedWrap()), but we can't prove nuw regardless, but it changes things such that the code under if (!BO->hasNoSignedWrap()) no longer works as well as it did previously.

We start with LHS = {%init,+,1}<%loop>, RHS = 1, and as part of computing OpAfterExtend (in the unsigned case), we hit this part of ScalarEvolution::getSignExtendExpr:

  // If the backedge is guarded by a comparison with the pre-inc value
  // the addrec is safe. Also, if the entry is guarded by a comparison
  // with the start value and the backedge is guarded by a comparison
  // with the post-inc value, the addrec is safe.
  ICmpInst::Predicate Pred;
  const SCEV *OverflowLimit =
      getSignedOverflowLimitForStep(Step, &Pred, this);
  if (OverflowLimit &&
      (isLoopBackedgeGuardedByCond(L, Pred, AR, OverflowLimit) ||
       (isLoopEntryGuardedByCond(L, Pred, Start, OverflowLimit) &&
        isLoopBackedgeGuardedByCond(L, Pred, AR->getPostIncExpr(*this),
                                    OverflowLimit)))) {
    // Cache knowledge of AR NSW, then propagate NSW to the wide AddRec.
    const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNSW);
    return getAddRecExpr(
        getExtendAddRecStart<SCEVSignExtendExpr>(AR, Ty, this),
        getSignExtendExpr(Step, Ty), L, AR->getNoWrapFlags());
  }
}

and this cached nsw flag ends up on our RHS, so we now have:

LHS = {%init,+,1}<nsw><%loop>, RHS = 1

and so the call to SE->getSignExtendExpr(LHS, WideTy) now returns:

(sext i32 {%init,+,1}<nsw><%loop> to i64)

instead of returning:

{(sext i32 %init to i64),+,1}<nsw><%loop> (as it does without this patch).

as a result, we get:

ExtendAfterOp == {(1 + (sext i32 %init to i64)),+,1}<nsw><%loop>
OpAfterExtend == (1 + (sext i32 {%init,+,1}<nsw><%loop> to i64))

instead of:

ExtendAfterOp == OpAfterExtend == {(1 + (sext i32 %init to i64)),+,1}<nsw><%loop>

interestingly, the results in the nuw case are also slightly different (although in neither case are equal because we can't provide nuw regardless). With the patch we get this:

ExtendAfterOp == (zext i32 {(1 + %init),+,1}<nsw><%loop> to i64)
OpAfterExtend == (1 + (zext i32 {%init,+,1}<nsw><%loop> to i64))

whereas currently we get:

ExtendAfterOp == (zext i32 {(1 + %init),+,1}<%loop> to i64)
OpAfterExtend == (1 + (zext i32 {%init,+,1}<%loop> to i64))

(so we get some extra <nsw>s for our trouble)

[hfinkel]

If you implement your check without actually creating a sign extend, but by directly inferring no-overflow from the nsw or nuw flags, then I suspect this won't happen.

If both LHS and RHS are AddRecs, and both are nsw and both have the same stride, then comparing the starting values seems as though it would be sufficient. Is there a straightforward way to do any better than that?

[hfinkel]

In D12073#226397, @hfinkel wrote:

In D12073#226385, @sanjoy wrote:

In D12073#226151, @hfinkel wrote:

There are now three failing tests, mostly due to IV widening that now does not happen. The new known-predicate results are:

test/Transforms/IndVarSimplify/elim-extend.ll:

• {%init,+,1}<nsw><%loop> sle {(1 + %init),+,1}<nsw><%loop>
• {(sext i32 %init to i64),+,1}<nsw><%loop> sle {(1 + (sext i32 %init to i64)),+,1}<nsw><%loop>
• {-1,+,1}<nsw><%outerloop> sle {1,+,1}<nuw><%outerloop>
• {-1,+,1}<nsw><%outerloop> sle {1,+,1}<nuw><nsw><%outerloop>

test/Transforms/IndVarSimplify/iv-sext.ll:

• {-1,+,1}<nsw><%bb> sle {1,+,1}<nuw><%bb>
• {-1,+,1}<nsw><%bb> sle {1,+,1}<nuw><nsw><%bb>

test/Transforms/IndVarSimplify/strengthen-overflow.ll:

• {%init,+,1}<nsw><%loop> sle {(1 + %init),+,1}<nsw><%loop>

These look right, but some consumer of the information seems to make a worse no-wrap deductions as a result (thus, this patch is still WIP).

I suspect (haven't verified) this is due to SCEV's caching mechanism. You end up creating a "Sext(LHS)" too soon, before proving all of the things needed to show that LHS is nsw. Then this suboptimal result gets cached.

In other words, I suspect the stack trace looks like this (youngest frame at top) initially:

== false because of PendingLoopPredicates, set in frame (A)
getImpliedCond(...)  // ends up looking at VAL
getLoopBackedgeCount(...)
getSignExtend(VAL)  // due to your change
getImpliedCond(...)  // ends up looking at VAL .. (A)
getLoopBackedgeCount(...)
getSignExtend(VAL)

This goes on as

  getSignExtend(VAL)  ==> no simplification, and we end up with
        UniqueSCEVs[(SignExtend, VAL)] = SignExtendExpr VAL, and
	does not set the <nsw> bit in VAL
  getImpliedCond(...)  // ends up looking at VAL .. (A)
  getLoopBackedgeCount(...)
  getSignExtend(VAL)

And then finally the oldest frame returns:

getSignExtend(VAL)  // this returns a widened version of VAL (instead of
  an explicit sign extend), and also set VAL's nsw bit

However, the damage has been done since UniqueSCEVs[(SignExtend, VAL)] == (SignExtendExpr VAL) and that's the value ScalarEvolution::getSignExtendExpr will return from now on.

If you implement your check without actually creating a sign extend, but by directly inferring no-overflow from the nsw or nuw flags, then I suspect this won't happen.

After looking at this more, your hypothesis is correct. We end up recursing on getSignExtendExpr {%init,+,1}<%loop>, which is broken by something (PendingLoopPredicates makes sense), and thus we cache a bad answer for the sign extension. Later, we retrieve the bad answer from the cache. Thus the problem. Thanks!

[hfinkel]

Update the patch to deal more-manually with AddRec expressions where we have wrapping guarantees on both sides and can otherwise reduce the problem to a comparison on the recursion starting values. As Sanjoy hypothesized, in writing it this way, there is no longer collateral damage to other regression tests.

[hfinkel]

We actually don't need to check the positivity of the recursion step because we're checking for equality (so both addrecs move in lock-step and it does not matter in which direction since neither will wrap).

[sanjoy]

lib/Analysis/ScalarEvolution.cpp

7357

Optional: I'd have just folded the null checks into this condition.

7367

I'd use CmpInst::isSigned(Pred) here.

7368

Why not return AR->getNoWrapFlags(SCEV::FlagNSW); here, and return AR->getNoWrapFlags(SCEV::FlagNUW); in the else block?

[hfinkel]

lib/Analysis/ScalarEvolution.cpp

7357

I did not do that so that I could easily avoid the second dyn_cast should the first one fail.

7367

Good suggestion.

7368

Also a good suggestion.

[hfinkel]

Implemented Sanjoy's suggestions.

[sanjoy]

lgtm.

[hfinkel]

r245400, thanks!

lib/Analysis/ScalarEvolution.cpp

bool ScalarEvolution::isLoopInvariantPredicate(
 
   InvariantPred = Pred;
   InvariantLHS = ArLHS->getStart();
   InvariantRHS = RHS;
   return true;
 }
 
 bool
 ScalarEvolution::isKnownPredicateWithRanges(ICmpInst::Predicate Pred,
                                             const SCEV *LHS, const SCEV *RHS) {
   if (HasSameValue(LHS, RHS))
     return ICmpInst::isTrueWhenEqual(Pred);
 
   // This code is split out from isKnownPredicate because it is called from
   // within isLoopEntryGuardedByCond.
   switch (Pred) {
   default:
     llvm_unreachable("Unexpected ICmpInst::Predicate value!");
   case ICmpInst::ICMP_SGT:
     std::swap(LHS, RHS);
   case ICmpInst::ICMP_SLT: {
     ConstantRange LHSRange = getSignedRange(LHS);
     ConstantRange RHSRange = getSignedRange(RHS);
     if (LHSRange.getSignedMax().slt(RHSRange.getSignedMin()))
       return true;
     if (LHSRange.getSignedMin().sge(RHSRange.getSignedMax()))
       return false;
     break;
   }
   case ICmpInst::ICMP_SGE:
     std::swap(LHS, RHS);
   case ICmpInst::ICMP_SLE: {
     ConstantRange LHSRange = getSignedRange(LHS);
     ConstantRange RHSRange = getSignedRange(RHS);
     if (LHSRange.getSignedMax().sle(RHSRange.getSignedMin()))
       return true;
     if (LHSRange.getSignedMin().sgt(RHSRange.getSignedMax()))
       return false;
     break;
   }
   case ICmpInst::ICMP_UGT:
     std::swap(LHS, RHS);
   case ICmpInst::ICMP_ULT: {
     ConstantRange LHSRange = getUnsignedRange(LHS);
     ConstantRange RHSRange = getUnsignedRange(RHS);
     if (LHSRange.getUnsignedMax().ult(RHSRange.getUnsignedMin()))
       return true;
     if (LHSRange.getUnsignedMin().uge(RHSRange.getUnsignedMax()))
static bool IsMinConsistingOf(ScalarEvolution &SE,
                               const SCEV *Candidate) {
   const SCEV *MaybeMaxExpr = MatchNotExpr(MaybeMinExpr);
   if (!MaybeMaxExpr)
     return false;
 
   return IsMaxConsistingOf<MaxExprType>(MaybeMaxExpr, SE.getNotSCEV(Candidate));
 }
 
+static bool IsKnownPredicateViaSubRange(ScalarEvolution &SE,
+                                        ICmpInst::Predicate Pred,
+                                        const SCEV *LHS, const SCEV *RHS) {
+  auto SignedDiff = [&]() -> const SCEV * {
+    unsigned BitWidth = SE.getTypeSizeInBits(LHS->getType());
+    Type *WideTy = IntegerType::get(SE.getContext(), BitWidth * 2);
+    return SE.getMinusSCEV(SE.getSignExtendExpr(LHS, WideTy),
+                           SE.getSignExtendExpr(RHS, WideTy));
+  };
+
+  switch (Pred) {
+  default: break;
+  case ICmpInst::ICMP_SGT:
+    std::swap(LHS, RHS);
+  case ICmpInst::ICMP_SLT:
+    if (SE.isKnownNegative(SignedDiff()))
+      return true;
+    break;
+  case ICmpInst::ICMP_SGE:
+    std::swap(LHS, RHS);
+  case ICmpInst::ICMP_SLE:
+    if (SE.isKnownNonPositive(SignedDiff()))
+      return true;
+    break;
+  }
+
+  return false;
+}
 
 /// Is LHS `Pred` RHS true on the virtue of LHS or RHS being a Min or Max
 /// expression?
 static bool IsKnownPredicateViaMinOrMax(ScalarEvolution &SE,
                                         ICmpInst::Predicate Pred,
                                         const SCEV *LHS, const SCEV *RHS) {
   switch (Pred) {
   default:
     return false;

 bool
 ScalarEvolution::isImpliedCondOperandsHelper(ICmpInst::Predicate Pred,
                                              const SCEV *LHS, const SCEV *RHS,
                                              const SCEV *FoundLHS,
                                              const SCEV *FoundRHS) {
   auto IsKnownPredicateFull =
       [this](ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS) {
     return isKnownPredicateWithRanges(Pred, LHS, RHS) ||
-        IsKnownPredicateViaMinOrMax(*this, Pred, LHS, RHS);
+        IsKnownPredicateViaMinOrMax(*this, Pred, LHS, RHS) ||
+        IsKnownPredicateViaSubRange(*this, Pred, LHS, RHS);
   };
 
   switch (Pred) {
   default: llvm_unreachable("Unexpected ICmpInst::Predicate value!");
   case ICmpInst::ICMP_EQ:
   case ICmpInst::ICMP_NE:
     if (HasSameValue(LHS, FoundLHS) && HasSameValue(RHS, FoundRHS))
       return true;

test/Transforms/IndVarSimplify/bec-cmp.ll

+; RUN: opt -S -indvars < %s | FileCheck %s
+target datalayout = "E-m:e-i64:64-n32:64"
+target triple = "powerpc64-unknown-linux-gnu"
+
+; Function Attrs: nounwind
+define void @foo(i32* nocapture %a, i32* nocapture readonly %b, i32 signext %n) #0 {
+entry:
+
+; CHECK-LABEL: @foo
+
+  %cmp.10 = icmp sgt i32 %n, 0
+  br i1 %cmp.10, label %for.body.lr.ph, label %for.cond.cleanup
+
+for.body.lr.ph:                                   ; preds = %entry
+  br label %for.body
+
+for.cond.for.cond.cleanup_crit_edge:              ; preds = %for.inc
+  br label %for.cond.cleanup
+
+for.cond.cleanup:                                 ; preds = %for.cond.for.cond.cleanup_crit_edge, %entry
+  ret void
+
+for.body:                                         ; preds = %for.body.lr.ph, %for.inc
+  %i.011 = phi i32 [ 0, %for.body.lr.ph ], [ %inc, %for.inc ]
+  %cmp1 = icmp sgt i32 %i.011, %n
+  br i1 %cmp1, label %if.then, label %for.inc
+
+; CHECK-NOT: br i1 %cmp1, label %if.then, label %for.inc
+; CHECK: br i1 false, label %if.then, label %for.inc
+
+if.then:                                          ; preds = %for.body
+  %idxprom = sext i32 %i.011 to i64
+  %arrayidx = getelementptr inbounds i32, i32* %b, i64 %idxprom
+  %0 = load i32, i32* %arrayidx, align 4
+  %add = add nsw i32 %0, 1
+  %arrayidx3 = getelementptr inbounds i32, i32* %a, i64 %idxprom
+  store i32 %add, i32* %arrayidx3, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body, %if.then
+  %inc = add nsw i32 %i.011, 1
+  %cmp = icmp slt i32 %inc, %n
+  br i1 %cmp, label %for.body, label %for.cond.for.cond.cleanup_crit_edge
+}
+
+attributes #0 = { nounwind }
+

test/Transforms/IndVarSimplify/elim-extend.ll

 innerpreheader:
   %innerprecmp = icmp sgt i32 %limitdec, %innercount
   br i1 %innerprecmp, label %innerloop, label %outermerge
 
 ; CHECK: innerloop:
 ;
 ; Eliminate %ofs2 after widening inneriv.
 ; Eliminate %ofs3 after normalizing sext(innerpostiv)
-; CHECK-NOT: sext
+; FIXME: For some reason, making isKnownPredicate smarter causes us to not
+; widen %limitdec, and thus not eliminate %ofs2 and %ofs3.
 ; CHECK: getelementptr
 ;
 ; FIXME: We should check that indvars does not increase the number of
 ; IVs in this loop. sext elimination plus LFTR currently results in 2 final
 ; IVs. Waiting to remove LFTR.
 innerloop:
   %inneriv = phi i32 [ %innerpostiv, %innerloop ], [ %innercount, %innerpreheader ]
   %innerpostiv = add i32 %inneriv, 1

test/Transforms/IndVarSimplify/iv-sext.ll

bb5.preheader:    ; preds = %bb3.bb5.preheader_crit_edge, %bb3.preheader
   %.not10 = fcmp olt float %distERBhi.0.ph, 2.500000e+00    ; <i1> [#uses=1]
   %tmp26 = icmp sgt i32 %tmp3, %hiPart.119    ; <i1> [#uses=1]
   %or.cond11 = and i1 %tmp26, %.not10   ; <i1> [#uses=1]
   br i1 %or.cond11, label %bb.nph12, label %bb7
 
 bb.nph12:   ; preds = %bb5.preheader
   br label %bb4
 ; CHECK: bb4:
-; CHECK: phi i64
+; FIXME: For some reason, making isKnownPredicate smarter causes us not to
+; widen the variable.
+; CHECK: phi i32
 ; CHECK-NOT: phi i64
-; CHECK-NOT: sext
+; CHECK: sext
 bb4:    ; preds = %bb5, %bb.nph12
   %distERBhi.29 = phi float [ %tmp30, %bb5 ], [ %distERBhi.0.ph, %bb.nph12 ]    ; <float> [#uses=1]
   %hiPart.08 = phi i32 [ %tmp31, %bb5 ], [ %hiPart.119, %bb.nph12 ]    ; <i32> [#uses=2]
   %peakCount.27 = phi float [ %tmp35, %bb5 ], [ %peakCount.0.lcssa, %bb.nph12 ]    ; <float> [#uses=1]
   %tmp27 = sext i32 %hiPart.08 to i64   ; <i64> [#uses=1]
   %tmp28 = getelementptr float, float* %pTmp1, i64 %tmp27    ; <float*> [#uses=1]
   %tmp29 = load float, float* %tmp28, align 4    ; <float> [#uses=1]
   %tmp30 = fadd float %tmp29, %distERBhi.29    ; <float> [#uses=3]

test/Transforms/IndVarSimplify/strengthen-overflow.ll

 ; RUN: opt < %s -indvars -S | FileCheck %s
 
 define i32 @test.signed.add.0(i32* %array, i32 %length, i32 %init) {
 ; CHECK-LABEL: @test.signed.add.0
  entry:
   %upper = icmp slt i32 %init, %length
   br i1 %upper, label %loop, label %exit
 
  loop:
 ; CHECK-LABEL: loop
   %civ = phi i32 [ %init, %entry ], [ %civ.inc, %latch ]
   %civ.inc = add i32 %civ, 1
-; CHECK: %civ.inc = add nsw i32 %civ, 1
+; FIXME: Making isKnownPrecidate smarter prevents adding nsw: %civ.inc = add nsw i32 %civ, 1
   %cmp = icmp slt i32 %civ.inc, %length
   br i1 %cmp, label %latch, label %break
 
  latch:
   store i32 0, i32* %array
   %check = icmp slt i32 %civ.inc, %length
   br i1 %check, label %loop, label %break