[ConstantRange] Clarify makeGuaranteedNoWrapRegion() guarantees

[nikic]

Summary

makeGuaranteedNoWrapRegion() is actually makeExactNoWrapRegion() as long as only one of NUW or NSW is specified. This is not obvious from the current documentation, and some code seems to think that it is only exact for single-element ranges. Clarify docs and add tests to be more confident this really holds.

There are currently no users of makeGuaranteedNoWrapRegion() that pass both NUW and NSW. I think it would be best to drop support for this entirely and then rename the function to makeExactNoWrapRegion().

Knowing that the no-wrap region is exact is useful, because we can backwards-constrain values. What I have in mind in particular is that LVI should be able to constrain values on edges where the with.overflow overflow flag is false.

[lebedev.ri]

This is NFC since it only clarifies docs and adds respective test coverage, thanks.

llvm/unittests/IR/ConstantRangeTest.cpp

1177–1178 ↗

(On Diff #194809)

Can we test/guarantee anything about the subset that will be returned if both are specified?
Naive guess - the most constrained range will be returned, the NSW one?

llvm/trunk/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);
 
   /// Return the largest range containing all X such that "X BinOpC Y" is
   /// guaranteed not to wrap (overflow) for all Y in Other.
   ///
-  /// NB! The returned set does *not* contain **all** possible values of X for
-  /// which "X BinOpC Y" does not wrap -- some viable values of X may be
-  /// missing, so you cannot use this to constrain X's range.  E.g. in the
+  /// If only one of NoUnsignedWrap or NoSignedWrap is specified, the returned
+  /// range is exact: It contains *all* possible values of X for which
+  /// "X BinOpC Y" does not wrap. However, if both NUW and NSW are specified, it
+  /// may return only a subset of non-wrapping values. In this case the
+  /// returned region cannot be used to constrain X's range. E.g. in the
   /// fourth example, "(-2) + 1" is both nsw and nuw (so the "X" could be -2),
   /// but (-2) is not in the set returned.
   ///
   /// 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)

llvm/trunk/lib/IR/ConstantRange.cpp

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 since we are
-  // passing a single element range.
+  // makeGuaranteedNoWrapRegion will produce an exact NSW range.
   auto NSWRange = ConstantRange::makeGuaranteedNoWrapRegion(BinaryOperator::Add,
                                       ConstantRange(Other),
                                       OverflowingBinaryOperator::NoSignedWrap);
   auto NSWConstrainedRange = intersectWith(NSWRange);
 
   return NSWConstrainedRange.add(ConstantRange(Other));
 }
 

llvm/trunk/unittests/IR/ConstantRangeTest.cpp

EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
                 Instruction::Sub, One, OBO::NoUnsignedWrap),
             ConstantRange(APInt::getMinValue(32) + 1, APInt::getMinValue(32)));
   EXPECT_EQ(
       ConstantRange::makeGuaranteedNoWrapRegion(
           Instruction::Sub, One, OBO::NoUnsignedWrap | OBO::NoSignedWrap),
       ConstantRange(APInt::getMinValue(32) + 1, APInt::getSignedMinValue(32)));
 }
 
+template<typename Fn>
+void TestNoWrapRegionExhaustive(Instruction::BinaryOps BinOp,
+                                unsigned NoWrapKind, Fn OverflowFn) {
+  // When using 4 bits this test needs ~3s on a debug build.
+  unsigned Bits = 3;
+  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;
+          ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
+            if (OverflowFn(N1, N2))
+              NoOverflow = false;
+          });
+          EXPECT_EQ(NoOverflow, NoWrap.contains(N1));
+        });
+      });
+}
+
+// Show that makeGuaranteedNoWrapRegion is precise if only one of
+// NoUnsignedWrap or NoSignedWrap is used.
+TEST(ConstantRange, NoWrapRegionExhaustive) {
+  TestNoWrapRegionExhaustive(
+      Instruction::Add, OverflowingBinaryOperator::NoUnsignedWrap,
+      [](const APInt &N1, const APInt &N2) {
+        bool Overflow;
+        (void) N1.uadd_ov(N2, Overflow);
+        return Overflow;
+      });
+  TestNoWrapRegionExhaustive(
+      Instruction::Add, OverflowingBinaryOperator::NoSignedWrap,
+      [](const APInt &N1, const APInt &N2) {
+        bool Overflow;
+        (void) N1.sadd_ov(N2, Overflow);
+        return Overflow;
+      });
+  TestNoWrapRegionExhaustive(
+      Instruction::Sub, OverflowingBinaryOperator::NoUnsignedWrap,
+      [](const APInt &N1, const APInt &N2) {
+        bool Overflow;
+        (void) N1.usub_ov(N2, Overflow);
+        return Overflow;
+      });
+  TestNoWrapRegionExhaustive(
+      Instruction::Sub, OverflowingBinaryOperator::NoSignedWrap,
+      [](const APInt &N1, const APInt &N2) {
+        bool Overflow;
+        (void) N1.ssub_ov(N2, Overflow);
+        return Overflow;
+      });
+  TestNoWrapRegionExhaustive(
+      Instruction::Mul, OverflowingBinaryOperator::NoUnsignedWrap,
+      [](const APInt &N1, const APInt &N2) {
+        bool Overflow;
+        (void) N1.umul_ov(N2, Overflow);
+        return Overflow;
+      });
+  TestNoWrapRegionExhaustive(
+      Instruction::Mul, OverflowingBinaryOperator::NoSignedWrap,
+      [](const APInt &N1, const APInt &N2) {
+        bool Overflow;
+        (void) N1.smul_ov(N2, Overflow);
+        return Overflow;
+      });
+}
+
 TEST(ConstantRange, GetEquivalentICmp) {
   APInt RHS;
   CmpInst::Predicate Pred;
 
   EXPECT_TRUE(ConstantRange(APInt::getMinValue(32), APInt(32, 100))
                   .getEquivalentICmp(Pred, RHS));
   EXPECT_EQ(Pred, CmpInst::ICMP_ULT);
   EXPECT_EQ(RHS, APInt(32, 100));