[SCEV] Try to get RHS from sext in implication via operations

[mkazantsev]

Summary

When proving implication via operations and LHS was taken from sext, it makes sense to try
to take RHS from extension also in case of type sizes mismatch.

[sanjoy]

Can you please write a test for this?

[mkazantsev]

Well, this situation is not something that can be reached easily (mostly because normal add does not propagate nsw flag), but I will try.

[sanjoy]

In D31598#716967, @mkazantsev wrote:

Well, this situation is not something that can be reached easily (mostly because normal add does not propagate nsw flag), but I will try.

One way is to change it to an assert and then try to bootstrap clang[1], and see what breaks. :)

[1]: http://llvm.org/docs/AdvancedBuilds.html#id2

lib/Analysis/ScalarEvolution.cpp

return isKnownViaSimpleReasoning(ICmpInst::ICMP_SGT, S1, S2) ||
                                   FoundRHS, Depth + 1);
   };
 
   if (auto *LHSAddExpr = dyn_cast<SCEVAddExpr>(LHS)) {
     // We want to avoid creation of any new non-constant SCEV. Since we are
     // going to compare the operands to RHS, we should be certain that we don't
     // need any size extensions for this. So let's decline all cases when the
     // sizes of types of LHS and RHS do not match.
-    // TODO: Maybe try to get RHS from sext to catch more cases?
-    if (getTypeSizeInBits(LHS->getType()) != getTypeSizeInBits(RHS->getType()))
+    auto *LTy = LHS->getType();
+    // If RHS has a wider type, there is a chance that RHS can be stripped from
+    // extension.
+    if (getTypeSizeInBits(LTy) < getTypeSizeInBits(RHS->getType()))
+      RHS = GetOpFromSExt(RHS);
+
+    // If the sizes still don't match, there is nothing we can do.
+    if (getTypeSizeInBits(LTy) != getTypeSizeInBits(RHS->getType()))
       return false;
 
     // Should not overflow.
     if (!LHSAddExpr->hasNoSignedWrap())
       return false;
 
     auto *LL = LHSAddExpr->getOperand(0);
     auto *LR = LHSAddExpr->getOperand(1);
-    auto *MinusOne = getNegativeSCEV(getOne(RHS->getType()));
+    auto *MinusOne = getNegativeSCEV(getOne(LTy));
 
     // Checks that S1 >= 0 && S2 > RHS, trivially or using the found context.
     auto IsSumGreaterThanRHS = [&](const SCEV *S1, const SCEV *S2) {
       return IsSGTViaContext(S1, MinusOne) && IsSGTViaContext(S2, RHS);
     };
     // Try to prove the following rule:
     // (LHS = LL + LR) && (LL >= 0) && (LR > RHS) => (LHS > RHS).
     // (LHS = LL + LR) && (LR >= 0) && (LL > RHS) => (LHS > RHS).