Introduce ConstantRange.addWithNoSignedWrap

[apilipenko]

Summary

To be used by upcoming change to IndVarSimplify

[sanjoy]

I think the algorithm in ConstantRange::addWithNoSignedWrap can be improved (see inline), but what you have here looks correct and most likely precise enough for the cases people will care about.

So I'd say let's move ahead with what's here and improve the implementation ConstantRange::addWithNoSignedWrap in parallel with working on the patches that will use this addWithNoSignedWrap interface.

lib/IR/ConstantRange.cpp

682 ↗

(On Diff #75030)

Nice trick!

Nit: I'd use auto here.

However, this isn't precise for the following case (in i8):

Other = 20
*this = [50, -50)

Then I think your algorithm will have

NSWRange = [128, 108)
NSWConstrainedRange = full set // I've not verified this
Result = full set

However, we could have returned [70, -30) (naively, without considering the nsw) or [-108, 128), both of which are more precise.

I'm now wondering if the best algorithm is actually to first add Other to *this and then subtract out the portion that could not have resulted from an overflowing add (e.g. adding 5 rules out the result from containing [INT_MIN, INT_MIN + 5)).

llvm/trunk/include/llvm/IR/ConstantRange.h

public:
   /// Make this range have the bit width given by \p BitWidth. The
   /// value is sign extended, truncated, or left alone to make it that width.
   ConstantRange sextOrTrunc(uint32_t BitWidth) const;
 
   /// Return a new range representing the possible values resulting
   /// from an addition of a value in this range and a value in \p Other.
   ConstantRange add(const ConstantRange &Other) const;
 
+  /// Return a new range representing the possible values resulting from a
+  /// known NSW addition of a value in this range and \p Other constant.
+  ConstantRange addWithNoSignedWrap(const APInt &Other) const;
+
   /// Return a new range representing the possible values resulting
   /// from a subtraction of a value in this range and a value in \p Other.
   ConstantRange sub(const ConstantRange &Other) const;
 
   /// Return a new range representing the possible values resulting
   /// from a multiplication of a value in this range and a value in \p Other,
   /// treating both this and \p Other as unsigned ranges.
   ConstantRange multiply(const ConstantRange &Other) const;

llvm/trunk/lib/IR/ConstantRange.cpp

ConstantRange::add(const ConstantRange &Other) const {
   ConstantRange X = ConstantRange(NewLower, NewUpper);
   if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y))
     // We've wrapped, therefore, full set.
     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 
   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.
+  auto NSWRange = ConstantRange::makeGuaranteedNoWrapRegion(BinaryOperator::Add,
+                                      ConstantRange(Other),
+                                      OverflowingBinaryOperator::NoSignedWrap);
+  auto NSWConstrainedRange = intersectWith(NSWRange);
+
+  return NSWConstrainedRange.add(ConstantRange(Other));
+}
+
 ConstantRange
 ConstantRange::sub(const ConstantRange &Other) const {
   if (isEmptySet() || Other.isEmptySet())
     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
   if (isFullSet() || Other.isFullSet())
     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 
   APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize();

llvm/trunk/unittests/IR/ConstantRangeTest.cpp

TEST_F(ConstantRangeTest, Add) {
   EXPECT_EQ(Some.add(APInt(16, 4)),
             ConstantRange(APInt(16, 0xe), APInt(16, 0xaae)));
   EXPECT_EQ(Wrap.add(APInt(16, 4)),
             ConstantRange(APInt(16, 0xaae), APInt(16, 0xe)));
   EXPECT_EQ(One.add(APInt(16, 4)),
             ConstantRange(APInt(16, 0xe)));
 }
 
+TEST_F(ConstantRangeTest, AddWithNoSignedWrap) {
+  EXPECT_EQ(Empty.addWithNoSignedWrap(APInt(16, 1)), Empty);
+  EXPECT_EQ(Full.addWithNoSignedWrap(APInt(16, 1)),
+            ConstantRange(APInt(16, INT16_MIN+1), APInt(16, INT16_MIN)));
+  EXPECT_EQ(ConstantRange(APInt(8, -50), APInt(8, 50)).addWithNoSignedWrap(APInt(8, 10)),
+            ConstantRange(APInt(8, -40), APInt(8, 60)));
+  EXPECT_EQ(ConstantRange(APInt(8, -50), APInt(8, 120)).addWithNoSignedWrap(APInt(8, 10)),
+            ConstantRange(APInt(8, -40), APInt(8, INT8_MIN)));
+  EXPECT_EQ(ConstantRange(APInt(8, 120), APInt(8, -10)).addWithNoSignedWrap(APInt(8, 5)),
+            ConstantRange(APInt(8, 125), APInt(8, -5)));
+  EXPECT_EQ(ConstantRange(APInt(8, 120), APInt(8, -120)).addWithNoSignedWrap(APInt(8, 10)),
+            ConstantRange(APInt(8, INT8_MIN+10), APInt(8, -110)));
+
+  EXPECT_EQ(Empty.addWithNoSignedWrap(APInt(16, -1)), Empty);
+  EXPECT_EQ(Full.addWithNoSignedWrap(APInt(16, -1)),
+            ConstantRange(APInt(16, INT16_MIN), APInt(16, INT16_MAX)));
+  EXPECT_EQ(ConstantRange(APInt(8, -50), APInt(8, 50)).addWithNoSignedWrap(APInt(8, -10)),
+            ConstantRange(APInt(8, -60), APInt(8, 40)));
+  EXPECT_EQ(ConstantRange(APInt(8, -120), APInt(8, 50)).addWithNoSignedWrap(APInt(8, -10)),
+            ConstantRange(APInt(8, INT8_MIN), APInt(8, 40)));
+  EXPECT_EQ(ConstantRange(APInt(8, 120), APInt(8, -120)).addWithNoSignedWrap(APInt(8, -5)),
+            ConstantRange(APInt(8, 115), APInt(8, -125)));
+  EXPECT_EQ(ConstantRange(APInt(8, 120), APInt(8, -120)).addWithNoSignedWrap(APInt(8, -10)),
+            ConstantRange(APInt(8, 110), APInt(8, INT8_MIN-10)));
+}
+
 TEST_F(ConstantRangeTest, Sub) {
   EXPECT_EQ(Full.sub(APInt(16, 4)), Full);
   EXPECT_EQ(Full.sub(Full), Full);
   EXPECT_EQ(Full.sub(Empty), Empty);
   EXPECT_EQ(Full.sub(One), Full);
   EXPECT_EQ(Full.sub(Some), Full);
   EXPECT_EQ(Full.sub(Wrap), Full);
   EXPECT_EQ(Empty.sub(Empty), Empty);