[ConstantRange] Add makeExactNoWrapRegion()

[nikic]

Summary

I got confused on the terminology, and the change in D60598 was not correct. I was thinking of "exact" in terms of the result being non-approximate. However, the relevant distinction here is whether the result is

• Largest range such that: Forall Y in Other: Forall X in Result: X BinOp Y does not wrap. (makeGuaranteedNoWrapRegion)
• Smallest range such that: Forall Y in Other: Forall X not in Result: X BinOp Y wraps. (A hypothetical makeAllowedNoWrapRegion)
• Both. (makeExactNoWrapRegion)

I'm adding a separate makeExactNoWrapRegion method accepting a single APInt (same as makeExactICmpRegion) and using it in the places where the guarantee is relevant.

Sorry for the confusion...

[lebedev.ri]

Does this needs tests?

[nikic]

Add (indirect) test. In the makeGuaranteedNoWrapRegion() tests check that the result for single-element ranges is indeed exact.

[lebedev.ri]

Hmm, it's concerning that i missed the difference in the original change.
Could someone else please also take a look here?

[sanjoy]

I got confused on the terminology

Any suggestions on how we can improve the terminology to be less confusing?

llvm/include/llvm/IR/ConstantRange.h

127

Does this always return the *largest* such range? (Just double-checking that this language is intentional.)

147

Up to you, but there is a standard way of describing this: "Returns the range such that X is in returned range if and only if X binop Y does not overflow."

[nikic]

llvm/include/llvm/IR/ConstantRange.h

127

Yep, this is indeed the largest range. We have some tests to check that.

llvm/include/llvm/IR/ConstantRange.h

public:
   /// returns the exact answer when the superset of 'union over all y in Other
   /// is exactly same as the subset of intersection over all y in Other.
   /// { x : icmp op x y is true}'.
   ///
   /// Example: Pred = ult and Other = i8 3 returns [0, 3)
   static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred,
                                            const APInt &Other);
 
-  /// Return the exact range containing all X such that "X BinOpC Y" is
-  /// guaranteed not to wrap (overflow) for all Y in Other.
+  /// 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:
   ///  typedef OverflowingBinaryOperator OBO;
   ///  #define MGNR makeGuaranteedNoWrapRegion
   ///  MGNR(Add, [i8 1, 2), OBO::NoSignedWrap) == [-128, 127)
   ///  MGNR(Add, [i8 1, 2), OBO::NoUnsignedWrap) == [0, -1)
   ///  MGNR(Add, [i8 0, 1), OBO::NoUnsignedWrap) == Full Set
   ///  MGNR(Add, [i8 -1, 6), OBO::NoSignedWrap) == [INT_MIN+1, INT_MAX-4)
   ///  MGNR(Sub, [i8 1, 2), OBO::NoSignedWrap) == [-127, 128)
   ///  MGNR(Sub, [i8 1, 2), OBO::NoUnsignedWrap) == [1, 0)
   static ConstantRange makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp,
                                                   const ConstantRange &Other,
                                                   unsigned NoWrapKind);
 
+  /// Produce the exact range containing all X such that "X BinOp Y" is
+  /// guaranteed not to wrap. The converse also holds: If a value X is not
+  /// contained in the result, then "X BinOp Y" must wrap.
+  static ConstantRange makeExactNoWrapRegion(Instruction::BinaryOps BinOp,
+                                             const APInt &Other,
+                                             unsigned NoWrapKind);
+
   /// Set up \p Pred and \p RHS such that
   /// ConstantRange::makeExactICmpRegion(Pred, RHS) == *this.  Return true if
   /// successful.
   bool getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS) const;
 
   /// Return the lower value for this range.
   const APInt &getLower() const { return Lower; }
 

llvm/lib/Analysis/LazyValueInfo.cpp

static ValueLatticeElement getValueFromOverflowCondition(
   // TODO: This only works with a constant RHS for now. We could also compute
   // the range of the RHS, but this doesn't fit into the current structure of
   // the edge value calculation.
   const APInt *C;
   if (WO->getLHS() != Val || !match(WO->getRHS(), m_APInt(C)))
     return ValueLatticeElement::getOverdefined();
 
   // Calculate the possible values of %x for which no overflow occurs.
-  ConstantRange NWR = ConstantRange::makeGuaranteedNoWrapRegion(
-      WO->getBinaryOp(), ConstantRange(*C), WO->getNoWrapKind());
+  ConstantRange NWR = ConstantRange::makeExactNoWrapRegion(
+      WO->getBinaryOp(), *C, WO->getNoWrapKind());
 
   // If overflow is false, %x is constrained to NWR. If overflow is true, %x is
   // constrained to it's inverse (all values that might cause overflow).
   if (IsTrueDest)
     NWR = NWR.inverse();
   return ValueLatticeElement::getRange(NWR);
 }
 

llvm/lib/IR/ConstantRange.cpp

if (Unsigned)
       return makeSingleValueRegion(Other.getUnsignedMax());
 
     return SubsetIntersect(makeSingleValueRegion(Other.getSignedMin()),
                            makeSingleValueRegion(Other.getSignedMax()));
   }
   }
 }
 
+ConstantRange ConstantRange::makeExactNoWrapRegion(Instruction::BinaryOps BinOp,
+                                                   const APInt &Other,
+                                                   unsigned NoWrapKind) {
+  // makeGuaranteedNoWrapRegion() is exact for single-element ranges, as
+  // "for all" and "for any" coincide in this case.
+  return makeGuaranteedNoWrapRegion(BinOp, ConstantRange(Other), NoWrapKind);
+}
+
 bool ConstantRange::isFullSet() const {
   return Lower == Upper && Lower.isMaxValue();
 }
 
 bool ConstantRange::isEmptySet() const {
   return Lower == Upper && Lower.isMinValue();
 }
 
if (X.isSizeStrictlySmallerThan(*this) ||
     // We've wrapped, therefore, full set.
     return getFull();
   return X;
 }
 
 ConstantRange ConstantRange::addWithNoSignedWrap(const APInt &Other) const {
   // Calculate the subset of this range such that "X + Other" is
   // guaranteed not to wrap (overflow) for all X in this subset.
-  // makeGuaranteedNoWrapRegion will produce an exact NSW range.
-  auto NSWRange = ConstantRange::makeGuaranteedNoWrapRegion(BinaryOperator::Add,
-                                      ConstantRange(Other),
-                                      OverflowingBinaryOperator::NoSignedWrap);
+  auto NSWRange = ConstantRange::makeExactNoWrapRegion(
+      BinaryOperator::Add, Other, OverflowingBinaryOperator::NoSignedWrap);
   auto NSWConstrainedRange = intersectWith(NSWRange);
 
   return NSWConstrainedRange.add(ConstantRange(Other));
 }
 
 ConstantRange
 ConstantRange::sub(const ConstantRange &Other) const {
   if (isEmptySet() || Other.isEmptySet())

llvm/unittests/IR/ConstantRangeTest.cpp

EnumerateTwoConstantRanges(Bits,
       [&](const ConstantRange &CR1, const ConstantRange &CR2) {
         if (CR2.isEmptySet())
           return;
 
         ConstantRange NoWrap =
             ConstantRange::makeGuaranteedNoWrapRegion(BinOp, CR2, NoWrapKind);
         ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
           bool NoOverflow = true;
+          bool Overflow = true;
           ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
             if (OverflowFn(N1, N2))
               NoOverflow = false;
+            else
+              Overflow = false;
           });
           EXPECT_EQ(NoOverflow, NoWrap.contains(N1));
+
+          // The no-wrap range is exact for single-element ranges.
+          if (CR2.isSingleElement()) {
+            EXPECT_EQ(Overflow, !NoWrap.contains(N1));
+          }
         });
       });
 }
 
-// Show that makeGuaranteedNoWrapRegion is precise if only one of
-// NoUnsignedWrap or NoSignedWrap is used.
+// Show that makeGuaranteedNoWrapRegion() is maximal, and for single-element
+// ranges also exact.
 TEST(ConstantRange, NoWrapRegionExhaustive) {
   TestNoWrapRegionExhaustive(
       Instruction::Add, OverflowingBinaryOperator::NoUnsignedWrap,
       [](const APInt &N1, const APInt &N2) {
         bool Overflow;
         (void) N1.uadd_ov(N2, Overflow);
         return Overflow;
       });