[ConstantRange] Split makeICmpRegion.

[sanjoy]

Summary

This change splits makeICmpRegion into makeAllowedICmpRegion and makeSatisfyingICmpRegion with slightly different contracts. The first one is useful for determining what values some expression may take, while the second one is useful for determining what values are guaranteed to satisfy a given icmp.

[sanjoy]

Address Nick's comments: split make makeICmpRegion into
makeAllowedICmpRegion and makeSatisfyingICmpRegion with clearly
specified contracts.

[nlewycky]

include/llvm/IR/ConstantRange.h

64

Optional suggestion: ... predicate with *any* value contained within Other is contained *in* the ...

70–83

Result = [0, 4) right? Or Pred = ule, either way?

lib/IR/ConstantRange.cpp

122

Optional: I'd leave out the "== ~~(A intersect B)" part.

[sanjoy]

include/llvm/IR/ConstantRange.h

64

Will fix.

70–83

Will fix, thanks for catching!

lib/IR/ConstantRange.cpp

122

Will fix.

[sanjoy]

• Address Nick's review.

[nlewycky]

LGTM

include/llvm/IR/ConstantRange.h

 // unsigned ranges.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_IR_CONSTANTRANGE_H
 #define LLVM_IR_CONSTANTRANGE_H
 
 #include "llvm/ADT/APInt.h"
+#include "llvm/IR/InstrTypes.h"
 #include "llvm/Support/DataTypes.h"
 
 namespace llvm {
 
 /// This class represents a range of values.
 ///
 class ConstantRange {
   APInt Lower, Upper;
public:
   ///
   ConstantRange(APIntMoveTy Value);
 
   /// @brief Initialize a range of values explicitly. This will assert out if
   /// Lower==Upper and Lower != Min or Max value for its type. It will also
   /// assert out if the two APInt's are not the same bit width.
   ConstantRange(APIntMoveTy Lower, APIntMoveTy Upper);
 
-  /// Produce the smallest range that contains all values that
-  /// might satisfy the comparison specified by Pred when compared to any value
-  /// contained within Other.
-  ///
-  /// Solves for range X in 'for all x in X, there exists a y in Y such that
-  /// icmp op x, y is true'. Every value that might make the comparison true
-  /// is included in the resulting range.
-  static ConstantRange makeICmpRegion(unsigned Pred,
+  /// Produce the smallest range such that all values that may satisfy the given
+  /// predicate with any value contained within Other is contained in the
+  /// returned range.  Formally, this returns a superset of
+  /// 'union over all y in Other . { x : icmp op x y is true }'.  If the exact
+  /// answer is not representable as a ConstantRange, the return value will be a
+  /// proper superset of the above.
+  ///
+  /// Example: Pred = ult and Other = i8 [2, 5) returns Result = [0, 4)
+  static ConstantRange makeAllowedICmpRegion(CmpInst::Predicate Pred,
+                                             const ConstantRange &Other);
+
+  /// Produce the largest range such that all values in the returned range
+  /// satisfy the given predicate with all values contained within Other.
+  /// Formally, this returns a subset of
+  /// 'intersection over all y in Other . { x : icmp op x y is true }'.  If the
+  /// exact answer is not representable as a ConstantRange, the return value
+  /// will be a proper subset of the above.
+  ///
+  /// Example: Pred = ult and Other = i8 [2, 5) returns [0, 2)
+  static ConstantRange makeSatisfyingICmpRegion(CmpInst::Predicate Pred,
                                                 const ConstantRange &Other);
 
   /// Return the lower value for this range.
   ///
   const APInt &getLower() const { return Lower; }
 
   /// Return the upper value for this range.
   ///
   const APInt &getUpper() const { return Upper; }

lib/Analysis/LazyValueInfo.cpp

if (ICI && isa<Constant>(ICI->getOperand(1))) {
     // (X-C1) u< C2 --> [C1, C1+C2)
     ConstantInt *NegOffset = nullptr;
     if (ICI->getPredicate() == ICmpInst::ICMP_ULT)
       match(ICI->getOperand(0), m_Add(m_Specific(Val),
                                       m_ConstantInt(NegOffset)));
 
     ConstantInt *CI = dyn_cast<ConstantInt>(ICI->getOperand(1));
     if (CI && (ICI->getOperand(0) == Val || NegOffset)) {
-      // Calculate the range of values that would satisfy the comparison.
+      // Calculate the range of values that are allowed by the comparision
       ConstantRange CmpRange(CI->getValue());
       ConstantRange TrueValues =
-        ConstantRange::makeICmpRegion(ICI->getPredicate(), CmpRange);
+          ConstantRange::makeAllowedICmpRegion(ICI->getPredicate(), CmpRange);
 
       if (NegOffset) // Apply the offset from above.
         TrueValues = TrueValues.subtract(NegOffset->getValue());
 
       // If we're interested in the false dest, invert the condition.
       if (!isTrueDest) TrueValues = TrueValues.inverse();
 
       Result = LVILatticeVal::getRange(TrueValues);

lib/IR/ConstantRange.cpp

 ConstantRange::ConstantRange(APIntMoveTy L, APIntMoveTy U)
     : Lower(std::move(L)), Upper(std::move(U)) {
   assert(Lower.getBitWidth() == Upper.getBitWidth() &&
          "ConstantRange with unequal bit widths");
   assert((Lower != Upper || (Lower.isMaxValue() || Lower.isMinValue())) &&
          "Lower == Upper, but they aren't min or max value!");
 }
 
-ConstantRange ConstantRange::makeICmpRegion(unsigned Pred,
+ConstantRange ConstantRange::makeAllowedICmpRegion(CmpInst::Predicate Pred,
                                                    const ConstantRange &CR) {
   if (CR.isEmptySet())
     return CR;
 
   uint32_t W = CR.getBitWidth();
   switch (Pred) {
-    default: llvm_unreachable("Invalid ICmp predicate to makeICmpRegion()");
+  default:
+    llvm_unreachable("Invalid ICmp predicate to makeAllowedICmpRegion()");
     case CmpInst::ICMP_EQ:
       return CR;
     case CmpInst::ICMP_NE:
       if (CR.isSingleElement())
         return ConstantRange(CR.getUpper(), CR.getLower());
       return ConstantRange(W);
     case CmpInst::ICMP_ULT: {
       APInt UMax(CR.getUnsignedMax());
case CmpInst::ICMP_SGE: {
       APInt SMin(CR.getSignedMin());
       if (SMin.isMinSignedValue())
         return ConstantRange(W);
       return ConstantRange(SMin, APInt::getSignedMinValue(W));
     }
   }
 }
 
+ConstantRange ConstantRange::makeSatisfyingICmpRegion(CmpInst::Predicate Pred,
+                                                      const ConstantRange &CR) {
+  // Follows from De-Morgan's laws:
+  //
+  // ~(~A union ~B) == A intersect B.
+  //
+  return makeAllowedICmpRegion(CmpInst::getInversePredicate(Pred), CR)
+      .inverse();
+}
+
 /// isFullSet - Return true if this set contains all of the elements possible
 /// for this data-type
 bool ConstantRange::isFullSet() const {
   return Lower == Upper && Lower.isMaxValue();
 }
 
 /// isEmptySet - Return true if this set contains no members.
 ///

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

if (LHSCC == ICmpInst::ICMP_UGE || LHSCC == ICmpInst::ICMP_ULE ||
       RHSCC == ICmpInst::ICMP_UGE || RHSCC == ICmpInst::ICMP_ULE ||
       LHSCC == ICmpInst::ICMP_SGE || LHSCC == ICmpInst::ICMP_SLE ||
       RHSCC == ICmpInst::ICMP_SGE || RHSCC == ICmpInst::ICMP_SLE)
     return nullptr;
 
   // Make a constant range that's the intersection of the two icmp ranges.
   // If the intersection is empty, we know that the result is false.
   ConstantRange LHSRange =
-    ConstantRange::makeICmpRegion(LHSCC, LHSCst->getValue());
+      ConstantRange::makeAllowedICmpRegion(LHSCC, LHSCst->getValue());
   ConstantRange RHSRange =
-    ConstantRange::makeICmpRegion(RHSCC, RHSCst->getValue());
+      ConstantRange::makeAllowedICmpRegion(RHSCC, RHSCst->getValue());
 
   if (LHSRange.intersectWith(RHSRange).isEmptySet())
     return ConstantInt::get(CmpInst::makeCmpResultType(LHS->getType()), 0);
 
   // We can't fold (ugt x, C) & (sgt x, C2).
   if (!PredicatesFoldable(LHSCC, RHSCC))
     return nullptr;
 

lib/Transforms/Utils/SimplifyCFG.cpp

if (ICI->getPredicate() == (isEQ ? ICmpInst::ICMP_EQ:ICmpInst::ICMP_NE)) {
         return false;
 
       UsedICmps++;
       Vals.push_back(C);
       return ICI->getOperand(0);
     }
 
     // If we have "x ult 3", for example, then we can add 0,1,2 to the set.
-    ConstantRange Span = ConstantRange::makeICmpRegion(ICI->getPredicate(),
-                                                       C->getValue());
+    ConstantRange Span = ConstantRange::makeAllowedICmpRegion(
+        ICI->getPredicate(), C->getValue());
 
     // Shift the range if the compare is fed by an add. This is the range
     // compare idiom as emitted by instcombine.
     Value *CandidateVal = I->getOperand(0);
     if(match(I->getOperand(0), m_Add(m_Value(RHSVal), m_ConstantInt(RHSC)))) {
       Span = Span.subtract(RHSC->getValue());
       CandidateVal = RHSVal;
     }

unittests/IR/ConstantRangeTest.cpp

TEST_F(ConstantRangeTest, Lshr) {
   EXPECT_EQ(One.lshr(Some), ConstantRange(APInt(16, 0)));
   EXPECT_EQ(One.lshr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
   EXPECT_EQ(Some.lshr(Some), ConstantRange(APInt(16, 0),
                                            APInt(16, (0xaaa >> 0xa) + 1)));
   EXPECT_EQ(Some.lshr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
   EXPECT_EQ(Wrap.lshr(Wrap), Full);
 }
 
-TEST(ConstantRange, MakeICmpRegion) {
+TEST(ConstantRange, MakeAllowedICmpRegion) {
   // PR8250
   ConstantRange SMax = ConstantRange(APInt::getSignedMaxValue(32));
-  EXPECT_TRUE(ConstantRange::makeICmpRegion(ICmpInst::ICMP_SGT,
-                                            SMax).isEmptySet());
+  EXPECT_TRUE(ConstantRange::makeAllowedICmpRegion(ICmpInst::ICMP_SGT, SMax)
+                  .isEmptySet());
+}
+
+TEST(ConstantRange, MakeSatisfyingICmpRegion) {
+  ConstantRange LowHalf(APInt(8, 0), APInt(8, 128));
+  ConstantRange HighHalf(APInt(8, 128), APInt(8, 0));
+  ConstantRange EmptySet(8, /* isFullSet = */ false);
+
+  EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_NE, LowHalf),
+            HighHalf);
+
+  EXPECT_EQ(
+      ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_NE, HighHalf),
+      LowHalf);
+
+  EXPECT_TRUE(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_EQ,
+                                                      HighHalf).isEmptySet());
+
+  ConstantRange UnsignedSample(APInt(8, 5), APInt(8, 200));
+
+  EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_ULT,
+                                                    UnsignedSample),
+            ConstantRange(APInt(8, 0), APInt(8, 5)));
+
+  EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_ULE,
+                                                    UnsignedSample),
+            ConstantRange(APInt(8, 0), APInt(8, 6)));
+
+  EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_UGT,
+                                                    UnsignedSample),
+            ConstantRange(APInt(8, 200), APInt(8, 0)));
+
+  EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_UGE,
+                                                    UnsignedSample),
+            ConstantRange(APInt(8, 199), APInt(8, 0)));
+
+  ConstantRange SignedSample(APInt(8, -5), APInt(8, 5));
+
+  EXPECT_EQ(
+      ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SLT, SignedSample),
+      ConstantRange(APInt(8, -128), APInt(8, -5)));
+
+  EXPECT_EQ(
+      ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SLE, SignedSample),
+      ConstantRange(APInt(8, -128), APInt(8, -4)));
+
+  EXPECT_EQ(
+      ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SGT, SignedSample),
+      ConstantRange(APInt(8, 5), APInt(8, -128)));
+
+  EXPECT_EQ(
+      ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SGE, SignedSample),
+      ConstantRange(APInt(8, 4), APInt(8, -128)));
 }
 
 }  // anonymous namespace