[ConstantRange] Sign-flipping of signedness-invariant comparisons

[lebedev.ri]

Summary

For certain combination of LHS and RHS constant ranges,
the signedness of the relational comparison predicate is irrelevant.

This implements complete and precise model for all predicates, as confirmed by the brute-force tests.
(although i've conjured this some time ago, so unless i'm not seeing why the test is misleading)

In a follow-up, CVP will make use of this.

Not sure how to generalize ConstantRange::areInsensitiveToSignednessOfSwappedICmpPredicate()

[lebedev.ri]

Ok, doesn't seem useful for SCEV.
Not sure if CVP-based fold is useful, so not really looking for review i guess.

[lebedev.ri]

As discussed/motivated by D111836, let's at least land the ConstantRange support.
I'd be fine landing this as-is, not sure if there is much to review here.

[nikic]

llvm/unittests/IR/ConstantRangeTest.cpp

2560

As a drive-by note without having looked at the rest yet: I'd love to have this publicly available somewhere. Could be used in https://github.com/llvm/llvm-project/blob/2c4a9e830cbb3b91a57902f7ecd508c544701819/llvm/lib/IR/ConstantFold.cpp#L1795-L1807 and I've wanted this on other occasions as well. Not sure where, maybe it could be a static method directly on ICmpInst?

[lebedev.ri]

Consolidated ICmpInst::compare().

[nikic]

llvm/lib/IR/ConstantRange.cpp

171

This implementation reads really confused to me. You should be able to reduce it to just:

if (CR1.isEmptySet() || CR2.isEmptySet())
  return true;

return (CR1.isAllNonNegative() && CR2.isAllNonNegative()) ||
       (CR1.isAllNegative() && CR2.isAllNegative());

I checked that this still passes your tests.

llvm/unittests/IR/ConstantRangeTest.cpp

2561

Use seq_inclusive() to avoid the back and forth casts?

[lebedev.ri]

Nits.

[nikic]

llvm/lib/IR/ConstantRange.cpp

159

Personally I'd convert this to areInsensitiveToSignednessOfInvertedICmpPredicate(), in which case the implementation would be the direct conjugate of the above, i.e.

if (CR1.isEmptySet() || CR2.isEmptySet())
  return true;
      
return (CR1.isAllNonNegative() && CR2.isAllNegative()) ||
       (CR1.isAllNegative() && CR2.isAllNonNegative());

I believe the only difference would be in the treatment of ranges that have a single element intersection (in which case the right canonicalization is probably towards an equality comparison rather than a different sign).

llvm/unittests/IR/ConstantRangeTest.cpp

2561

Isn't it possible to drop the (ICmpInst::Predicate) casts if seq_inclusive is used?

[lebedev.ri]

Thank you for taking a look!
Improved areInsensitiveToSignednessOfICmpPredicate().

llvm/lib/IR/ConstantRange.cpp

159

Hmm, tests suggest that said implementation is (also) precise.
I'm not seeing any obvious bugs in exhaustive test coverage,
so let's do that instead. Again, i don't really recall why this was
the way it it, perhaps i just got discouraged in non-applicability
of this in SCEV, and didn't get it fully cleaned up.

171

Hmm, indeed. I don't really recall why i ended up with that,
i was looking for a complex solution, so i didn't end up
converging on the simplest one.

[lebedev.ri]

Do not pass around srcpred in tests, NFC.

[nikic]

LGTM, thanks!

llvm/include/llvm/IR/ConstantRange.h

146

nit: "maybe inverted" now

Might be worth mentioning that BAD_ICMP_PREDICATE is returned on failure.

149

I find it slightly odd that the other two are static methods but this one is an instance method -- any particular reason for that choice?

[lebedev.ri]

Nits.

[lebedev.ri]

llvm/include/llvm/IR/ConstantRange.h

149

Nothing particular, but i think we are consistently inconsistent with this.
Let's go with static.

llvm/include/llvm/IR/ConstantRange.h

public:
   /// Example: Pred = ult and Other = i8 3 returns [0, 3)
   static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred,
                                            const APInt &Other);
 
   /// Does the predicate \p Pred hold between ranges this and \p Other?
   /// NOTE: false does not mean that inverse predicate holds!
   bool icmp(CmpInst::Predicate Pred, const ConstantRange &Other) const;
 
+  /// Return true iff CR1 ult CR2 is equivalent to CR1 slt CR2.
+  /// Does not depend on strictness/direction of the predicate.
+  static bool
+  areInsensitiveToSignednessOfICmpPredicate(const ConstantRange &CR1,
+                                            const ConstantRange &CR2);
+
+  /// Return true iff CR1 ult CR2 is equivalent to CR1 sgt CR2.
+  /// Does not depend on strictness/direction of the predicate.
+  static bool
+  areInsensitiveToSignednessOfSwappedICmpPredicate(const ConstantRange &CR1,
+                                                   const ConstantRange &CR2);
+
+  /// If the comparison between constant ranges this and Other
+  /// is insensitive to the signedness of the comparison predicate,
+  /// return a predicate equivalent to \p Pred, with flipped signedness
+  /// (i.e. unsigned instead of signed or vice versa), and maybe swapped.
+  CmpInst::Predicate
+  getEquivalentPredWithFlippedSignedness(CmpInst::Predicate Pred,
+                                         const ConstantRange &Other) const;
+
   /// Produce the largest range containing all X such that "X BinOp Y" is
   /// guaranteed not to wrap (overflow) for *all* Y in Other. However, there may
   /// be *some* Y in Other for which additional X not contained in the result
   /// also do not overflow.
   ///
   /// NoWrapKind must be one of OBO::NoUnsignedWrap or OBO::NoSignedWrap.
   ///
   /// Examples:

llvm/lib/IR/ConstantRange.cpp

ConstantRange ConstantRange::makeExactICmpRegion(CmpInst::Predicate Pred,
   // when RHS is a singleton such as an APInt and so the assert is valid.
   // However for non-singleton RHS, for example ult [2,5) makeAllowedICmpRegion
   // returns [0,4) but makeSatisfyICmpRegion returns [0,2).
   //
   assert(makeAllowedICmpRegion(Pred, C) == makeSatisfyingICmpRegion(Pred, C));
   return makeAllowedICmpRegion(Pred, C);
 }
 
+bool ConstantRange::areInsensitiveToSignednessOfICmpPredicate(
+    const ConstantRange &CR1, const ConstantRange &CR2) {
+  if (CR1.isEmptySet() || CR2.isEmptySet())
+    return true;
+
+  if (CR1.isFullSet() || CR2.isFullSet())
+    return false;
+  if (CR1.isWrappedSet() || CR2.isWrappedSet())
+    return false;
+  if (CR1.isSignWrappedSet() || CR2.isSignWrappedSet())
+    return false;
+
+  if (CR1.contains(CR2) || CR2.contains(CR1))
+    return true;
+
+  if (CR1.isAllNonNegative() && CR2.isAllNonNegative())
+    return true;
+
+  if (CR1.isAllNegative() && CR2.isAllNegative())
+    return !CR1.isUpperWrapped() || !CR2.isUpperWrapped();
+
+  return false;
+}
+
+bool ConstantRange::areInsensitiveToSignednessOfSwappedICmpPredicate(
+    const ConstantRange &CR1, const ConstantRange &CR2) {
+  if (CR1.isEmptySet() || CR2.isEmptySet())
+    return true;
+  if (CR1.isFullSet() || CR2.isFullSet())
+    return false;
+
+  bool TrulyEquivalent = true;
+
+  for (auto N1 : {CR1.getUnsignedMin(), CR1.getUnsignedMax(),
+                  CR1.getSignedMin(), CR1.getSignedMax()})
+    for (auto N2 : {CR2.getUnsignedMin(), CR2.getUnsignedMax(),
+                    CR2.getSignedMin(), CR2.getSignedMax()})
+      TrulyEquivalent &= N1.slt(N2) == N1.ugt(N2);
+
+  return TrulyEquivalent;
+}
+
+CmpInst::Predicate ConstantRange::getEquivalentPredWithFlippedSignedness(
+    CmpInst::Predicate Pred, const ConstantRange &Other) const {
+  assert(CmpInst::isIntPredicate(Pred) && CmpInst::isRelational(Pred) &&
+         "Only for relational integer predicates!");
+
+  CmpInst::Predicate FlippedSignednessPred =
+      CmpInst::getFlippedSignednessPredicate(Pred);
+
+  if (areInsensitiveToSignednessOfICmpPredicate(*this, Other))
+    return FlippedSignednessPred;
+
+  if (areInsensitiveToSignednessOfSwappedICmpPredicate(*this, Other))
+    return CmpInst::getSwappedPredicate(FlippedSignednessPred);
+
+  return CmpInst::Predicate::BAD_ICMP_PREDICATE;
+}
+
 bool ConstantRange::getEquivalentICmp(CmpInst::Predicate &Pred,
                                       APInt &RHS) const {
   bool Success = false;
 
   if (isFullSet() || isEmptySet()) {
     Pred = isEmptySet() ? CmpInst::ICMP_ULT : CmpInst::ICMP_UGE;
     RHS = APInt(getBitWidth(), 0);
     Success = true;

llvm/unittests/IR/ConstantRangeTest.cpp

TestUnaryOpExhaustive(
       [](const APInt &N) { return ~N; }, PreferSmallest);
   TestUnaryOpExhaustive(
       [](const ConstantRange &CR) {
         return ConstantRange(APInt::getAllOnes(CR.getBitWidth())).binaryXor(CR);
       },
       [](const APInt &N) { return ~N; }, PreferSmallest);
 }
 
-}  // anonymous namespace
+bool compare(const APInt &LHS, const APInt &RHS, ICmpInst::Predicate Pred) {
+  assert(ICmpInst::isIntPredicate(Pred) && "Only for integer predicates!");
+  switch (Pred) {
+  case ICmpInst::Predicate::ICMP_EQ:
+    return LHS.eq(RHS);
+  case ICmpInst::Predicate::ICMP_NE:
+    return LHS.ne(RHS);
+  case ICmpInst::Predicate::ICMP_UGT:
+    return LHS.ugt(RHS);
+  case ICmpInst::Predicate::ICMP_UGE:
+    return LHS.uge(RHS);
+  case ICmpInst::Predicate::ICMP_ULT:
+    return LHS.ult(RHS);
+  case ICmpInst::Predicate::ICMP_ULE:
+    return LHS.ule(RHS);
+  case ICmpInst::Predicate::ICMP_SGT:
+    return LHS.sgt(RHS);
+  case ICmpInst::Predicate::ICMP_SGE:
+    return LHS.sge(RHS);
+  case ICmpInst::Predicate::ICMP_SLT:
+    return LHS.slt(RHS);
+  case ICmpInst::Predicate::ICMP_SLE:
+    return LHS.sle(RHS);
+  default:
+    llvm_unreachable("Unexpected non-integer predicate.");
+  };
+}
+
+template <typename T>
+void testConstantRangeICmpPredEquivalence(ICmpInst::Predicate SrcPred, T Func) {
+  unsigned Bits = 4;
+  EnumerateTwoConstantRanges(Bits, [&](const ConstantRange &CR1,
+                                       const ConstantRange &CR2) {
+    ICmpInst::Predicate TgtPred;
+    bool ExpectedEquivalent;
+    std::tie(TgtPred, ExpectedEquivalent) = Func(CR1, CR2, SrcPred);
+    if (TgtPred == CmpInst::Predicate::BAD_ICMP_PREDICATE)
+      return;
+    bool TrulyEquivalent = true;
+    ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
+      if (!TrulyEquivalent)
+        return;
+      ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
+        if (!TrulyEquivalent)
+          return;
+        TrulyEquivalent &= compare(N1, N2, SrcPred) == compare(N1, N2, TgtPred);
+      });
+    });
+    ASSERT_EQ(TrulyEquivalent, ExpectedEquivalent);
+  });
+}
+
+TEST_F(ConstantRangeTest, areInsensitiveToSignednessOfICmpPredicate) {
+  for (auto Pred : seq((unsigned)ICmpInst::Predicate::FIRST_ICMP_PREDICATE,
+                       ICmpInst::Predicate::LAST_ICMP_PREDICATE + 1)) {
+    if (ICmpInst::isEquality((ICmpInst::Predicate)Pred))
+      continue;
+    ICmpInst::Predicate FlippedSignednessPred =
+        ICmpInst::getFlippedSignednessPredicate((ICmpInst::Predicate)Pred);
+    testConstantRangeICmpPredEquivalence(
+        (ICmpInst::Predicate)Pred,
+        [FlippedSignednessPred](const ConstantRange &CR1,
+                                const ConstantRange &CR2,
+                                ICmpInst::Predicate SrcPred) {
+          return std::make_pair(
+              FlippedSignednessPred,
+              ConstantRange::areInsensitiveToSignednessOfICmpPredicate(CR1,
+                                                                       CR2));
+        });
+  }
+}
+
+TEST_F(ConstantRangeTest, areInsensitiveToSignednessOfSwappedICmpPredicate) {
+  for (auto Pred : seq((unsigned)ICmpInst::Predicate::FIRST_ICMP_PREDICATE,
+                       ICmpInst::Predicate::LAST_ICMP_PREDICATE + 1)) {
+    if (ICmpInst::isEquality((ICmpInst::Predicate)Pred))
+      continue;
+    ICmpInst::Predicate FlippedSignednessPred =
+        ICmpInst::getFlippedSignednessPredicate((ICmpInst::Predicate)Pred);
+    ICmpInst::Predicate SwappedFlippedSignednessPred =
+        ICmpInst::getSwappedPredicate(FlippedSignednessPred);
+    testConstantRangeICmpPredEquivalence(
+        (ICmpInst::Predicate)Pred,
+        [SwappedFlippedSignednessPred](const ConstantRange &CR1,
+                                       const ConstantRange &CR2,
+                                       ICmpInst::Predicate SrcPred) {
+          return std::make_pair(
+              SwappedFlippedSignednessPred,
+              ConstantRange::areInsensitiveToSignednessOfSwappedICmpPredicate(
+                  CR1, CR2));
+        });
+  }
+}
+
+TEST_F(ConstantRangeTest, getEquivalentPredWithFlippedSignedness) {
+  for (auto Pred : seq((unsigned)ICmpInst::Predicate::FIRST_ICMP_PREDICATE,
+                       ICmpInst::Predicate::LAST_ICMP_PREDICATE + 1)) {
+    if (ICmpInst::isEquality((ICmpInst::Predicate)Pred))
+      continue;
+    testConstantRangeICmpPredEquivalence(
+        (ICmpInst::Predicate)Pred,
+        [](const ConstantRange &CR1, const ConstantRange &CR2,
+           ICmpInst::Predicate SrcPred) {
+          return std::make_pair(
+              CR1.getEquivalentPredWithFlippedSignedness(SrcPred, CR2), true);
+        });
+  }
+}
+
+} // anonymous namespace