[SCEV] Handle `less` predicates for FoundPred = NE

[mkazantsev]

Summary

Currently these predicates are ignored, yet their handling is
pretty simple. I could not find a single test where it would
actually change something, but it's only because isImpliedCondOperands
is not smart enough to prove it further on. Yet the situation when
we come there with less predicate is pretty common.

[fhahn]

Would it be worth adding a C++ unit test for those cases that just passes in suitable predicates + SCEV expression?

[mkazantsev]

Yes, I will try to construct such test.

[mkazantsev]

Actually I'm not sure we need this. I could not construct a test where it would succeed.

[mkazantsev]

It seems that there is no way that SCEV can now both make this query and return true for it. I'm currently building a chain of patch that will fix the query responds. Hopefully with them we will be able to construct a test for it.

Or can we just merge it basing on obviousness of this logic?

[fhahn]

In D87890#2287035, @mkazantsev wrote:

It seems that there is no way that SCEV can now both make this query and return true for it. I'm currently building a chain of patch that will fix the query responds. Hopefully with them we will be able to construct a test for it.

Or can we just merge it basing on obviousness of this logic?

Sure that is fine, if there will be patches to make use of it in the near future.

LGTM, thanks.

llvm/lib/Analysis/ScalarEvolution.cpp

9763

nit: Might be good to mention both the LE & LT variants and say that both LHS <= RHS and LHS < RHS are handled in the same way as RHS >= LHS and RHS > LHS respectively.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

9763

Ok.

[mkazantsev]

Thanks Florian! One example of where it helps is ULT check in test of D88087 (fails without this patch).

llvm/lib/Analysis/ScalarEvolution.cpp

if (Min == C->getAPInt()) {
           //
           //       V `Pred` Min || V == Min && !(V == Min)
           //   =>  V `Pred` Min
           //
           // If V `Pred` Min implies LHS `Pred` RHS, we're done.
 
           if (isImpliedCondOperands(Pred, LHS, RHS, V, getConstant(Min)))
             return true;
+          break;
+
+        // `LHS < RHS` and `LHS <= RHS` are handled in the same way as `RHS > LHS` and `RHS >= LHS` respectively.
+        case ICmpInst::ICMP_SLE:
+        case ICmpInst::ICMP_ULE:
+          if (isImpliedCondOperands(CmpInst::getSwappedPredicate(Pred), RHS,
+                                    LHS, V, getConstant(SharperMin)))
+            return true;
           LLVM_FALLTHROUGH;
 
+        case ICmpInst::ICMP_SLT:
+        case ICmpInst::ICMP_ULT:
+          if (isImpliedCondOperands(CmpInst::getSwappedPredicate(Pred), RHS,
+                                    LHS, V, getConstant(Min)))
+            return true;
+          break;
+
         default:
           // No change
           break;
       }
     }
   }
 
   // Check whether the actual condition is beyond sufficient.