[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

65

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

70

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

lib/IR/ConstantRange.cpp

121

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

[sanjoy]

include/llvm/IR/ConstantRange.h

65

Will fix.

70

Will fix, thanks for catching!

lib/IR/ConstantRange.cpp

121

Will fix.

[sanjoy]

• Address Nick's review.

[nlewycky]

LGTM

include/llvm/IR/ConstantRange.h

public:
   /// @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,
                                       const ConstantRange &Other);
 
+  /// Produce the range that contains exactly all the values that might satisfy
+  /// the comparison specified by Pred when compared to Other.  This is similar
+  /// to makeICmpRegion except for the additional exactness constraint -- the
+  /// resultant range does not contain any value that for which the predicate is
+  /// false.
+  ///
+  static ConstantRange makeExactICmpRegion(unsigned Pred, const APInt &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/IR/ConstantRange.cpp

case CmpInst::ICMP_SGE: {
       APInt SMin(CR.getSignedMin());
       if (SMin.isMinSignedValue())
         return ConstantRange(W);
       return ConstantRange(SMin, APInt::getSignedMinValue(W));
     }
   }
 }
 
+ConstantRange ConstantRange::makeExactICmpRegion(unsigned Pred,
+                                                 const APInt &AI) {
+  uint32_t W = AI.getBitWidth();
+  switch (Pred) {
+  default:
+    llvm_unreachable("Invalid ICmp predicate to makeICmpRegion()");
+  case CmpInst::ICMP_EQ:
+    return ConstantRange(AI);
+  case CmpInst::ICMP_NE:
+    return ConstantRange(AI + 1, AI);
+  case CmpInst::ICMP_ULT: {
+    if (AI.isMinValue())
+      return ConstantRange(W, /* isFullSet = */ false);
+    return ConstantRange(APInt::getMinValue(W), AI);
+  }
+  case CmpInst::ICMP_SLT: {
+    if (AI.isMinSignedValue())
+      return ConstantRange(W, /* isFullSet = */ false);
+    return ConstantRange(APInt::getSignedMinValue(W), AI);
+  }
+  case CmpInst::ICMP_ULE: {
+    if (AI.isMaxValue())
+      return ConstantRange(W);
+    return ConstantRange(APInt::getMinValue(W), AI + 1);
+  }
+  case CmpInst::ICMP_SLE: {
+    if (AI.isMaxSignedValue())
+      return ConstantRange(W);
+    return ConstantRange(APInt::getSignedMinValue(W), AI + 1);
+  }
+  case CmpInst::ICMP_UGT: {
+    if (AI.isMaxValue())
+      return ConstantRange(W, /* isFullSet = */ false);
+    return ConstantRange(AI + 1, APInt::getNullValue(W));
+  }
+  case CmpInst::ICMP_SGT: {
+    if (AI.isMaxSignedValue())
+      return ConstantRange(W, /* isFullSet = */ false);
+    return ConstantRange(AI + 1, APInt::getSignedMinValue(W));
+  }
+  case CmpInst::ICMP_UGE: {
+    if (AI.isMinValue())
+      return ConstantRange(W);
+    return ConstantRange(AI, APInt::getNullValue(W));
+  }
+  case CmpInst::ICMP_SGE: {
+    if (AI.isMinSignedValue())
+      return ConstantRange(W);
+    return ConstantRange(AI, APInt::getSignedMinValue(W));
+  }
+  }
+}
+
 /// 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.
 ///

unittests/IR/ConstantRangeTest.cpp

 
 TEST(ConstantRange, MakeICmpRegion) {
   // PR8250
   ConstantRange SMax = ConstantRange(APInt::getSignedMaxValue(32));
   EXPECT_TRUE(ConstantRange::makeICmpRegion(ICmpInst::ICMP_SGT,
                                             SMax).isEmptySet());
 }
 
+TEST(ConstantRange, MakeICmpRegionExact) {
+  EXPECT_TRUE(ConstantRange::makeExactICmpRegion(ICmpInst::ICMP_SGT,
+                                                 APInt::getSignedMaxValue(2))
+                  .isEmptySet());
+  EXPECT_TRUE(ConstantRange::makeExactICmpRegion(
+                  ICmpInst::ICMP_SGE, APInt::getSignedMinValue(2)).isFullSet());
+  EXPECT_EQ(ConstantRange::makeExactICmpRegion(
+                ICmpInst::ICMP_ULT, APInt::getSignedMinValue(2)).getSetSize(),
+            2);
+  EXPECT_EQ(ConstantRange::makeExactICmpRegion(
+                ICmpInst::ICMP_UGT, APInt::getSignedMinValue(2)).getSetSize(),
+            1);
+  EXPECT_EQ(ConstantRange::makeExactICmpRegion(
+                ICmpInst::ICMP_NE, APInt::getMinValue(2)).getSetSize(),
+            3);
+  EXPECT_EQ(ConstantRange::makeExactICmpRegion(
+                ICmpInst::ICMP_EQ, APInt::getMinValue(2)).getSetSize(),
+            1);
+}
+
 }  // anonymous namespace