[IR] Add a `makeNoWrapRegion` method to `ConstantRange`

[sanjoy]

Summary

This will be used in a future change to ScalarEvolution.

[nlewycky]

The logic looks correct, and I really like the test!

include/llvm/IR/ConstantRange.h

89–93 ↗

(On Diff #37008)

Example in comments don't match function declaration? Did you want to make it an 'int WrappingFlags'? (I see that you actually use it as a bool, but I really like the named flags API shown in the comment much more.)

lib/IR/ConstantRange.cpp

138 ↗

(On Diff #37008)

use BitWidth here

140 ↗

(On Diff #37008)

C.isMinValue() is fully defined in the header.

151 ↗

(On Diff #37008)

I think that's locally obvious enough that we don't need an assert. :)

[sanjoy]

include/llvm/IR/ConstantRange.h

89–93 ↗

(On Diff #37008)

I initially did have it as a int WrappingFlags (and I forgot to update the comments when I changed this to use a bool), but using AddOperator::... here seemed arbitrary (for instance, is it okay to have BinOp be Instruction::Mul and pass in AddOperator::NoSignedWrap?

However, I share your preference for named parameters :), so I'll happily change this back to use AddOperator::NoUnsignedWrap if you're okay with it. I can also introduce an enum inside ConstantRange if that sounds better.

[sanjoy]

• address Nick's review

[sanjoy]

include/llvm/IR/ConstantRange.h

89–93 ↗

(On Diff #37008)

Changed to use OverflowingBinaryOperator::NoXXXWrap.

[nlewycky]

lib/IR/ConstantRange.cpp

138–139 ↗

(On Diff #37147)

Please sink this below the test for BinOp being Add. It's not a misuse of the API to call it with OBO::Exact or some other flag if the BinOp is not an add.

150 ↗

(On Diff #37147)

Please handle the case where NoWrapKind = NoUnsignedWrap | NoSignedWrap.

[sanjoy]

lib/IR/ConstantRange.cpp

138–139 ↗

(On Diff #37147)

But the API is called makeNoWrapRegion, so I'd say calling it with OBO::Exact or other flags unrelated to wrapping is a misuse.

(I don't have a very strong opinion on this, and will change it if you insist.

[nlewycky]

lib/IR/ConstantRange.cpp

138–139 ↗

(On Diff #37147)

Oh, good point. I was imagining generalizing this function for all the optimization flags, but right now it's clearly labelled for wrapping. We can change that later when it's required.

[sanjoy]

• address review, and bugfix

[sanjoy]

I was using intersectWith incorrect. I've fixed the problem now (see PreciseIntersect).

[sanjoy]

ping!

[nlewycky]

include/llvm/IR/ConstantRange.h

91 ↗

(On Diff #37207)

There is no OBO::UnsignedWrap??

lib/IR/ConstantRange.cpp

139 ↗

(On Diff #37207)

ExclusiveIntersect? MinimalIntersect? SubsetIntersect? I don't feel like precise conveys meaning here (what's not precise about intersectWith? It's not about precision, it's about whether we choose to include all points in the intersection or choose to include only pointer in the intersection).

[sanjoy]

• address review

[sanjoy]

Addressed reviews

[nlewycky]

LGTM

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

public:
   /// '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 largest range containing all X such that "X BinOpC C" does not
+  /// wrap (overflow).
+  ///
+  /// Example:
+  ///  typedef OverflowingBinaryOperator OBO;
+  ///  makeNoWrapRegion(Add, i8 1, OBO::NoSignedWrap) == [-128, 127)
+  ///  makeNoWrapRegion(Add, i8 1, OBO::NoUnsignedWrap) == [0, -1)
+  ///  makeNoWrapRegion(Add, i8 0, OBO::NoUnsignedWrap) == Full Set
+  static ConstantRange makeNoWrapRegion(Instruction::BinaryOps BinOp,
+                                        const APInt &C, unsigned NoWrapKind);
+
   /// 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; }
 

llvm/trunk/lib/IR/ConstantRange.cpp

 //
 //  [F, F) = {}     = Empty set
 //  [T, F) = {T}
 //  [F, T) = {F}
 //  [T, T) = {F, T} = Full set
 //
 //===----------------------------------------------------------------------===//
 
+#include "llvm/IR/Instruction.h"
 #include "llvm/IR/InstrTypes.h"
+#include "llvm/IR/Operator.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 using namespace llvm;
 
 /// Initialize a full (the default) or empty set for the specified type.
 ///
 ConstantRange::ConstantRange(uint32_t BitWidth, bool Full) {
ConstantRange ConstantRange::makeSatisfyingICmpRegion(CmpInst::Predicate Pred,
   // Follows from De-Morgan's laws:
   //
   // ~(~A union ~B) == A intersect B.
   //
   return makeAllowedICmpRegion(CmpInst::getInversePredicate(Pred), CR)
       .inverse();
 }
 
+ConstantRange ConstantRange::makeNoWrapRegion(Instruction::BinaryOps BinOp,
+                                              const APInt &C,
+                                              unsigned NoWrapKind) {
+  typedef OverflowingBinaryOperator OBO;
+
+  // Computes the intersection of CR0 and CR1.  It is different from
+  // intersectWith in that the ConstantRange returned will only contain elements
+  // in both CR0 and CR1 (i.e. SubsetIntersect(X, Y) is a *subset*, proper or
+  // not, of both X and Y).
+  auto SubsetIntersect =
+      [](const ConstantRange &CR0, const ConstantRange &CR1) {
+    return CR0.inverse().unionWith(CR1.inverse()).inverse();
+  };
+
+  assert(BinOp >= Instruction::BinaryOpsBegin &&
+         BinOp < Instruction::BinaryOpsEnd && "Binary operators only!");
+
+  assert((NoWrapKind == OBO::NoSignedWrap ||
+          NoWrapKind == OBO::NoUnsignedWrap ||
+          NoWrapKind == (OBO::NoUnsignedWrap | OBO::NoSignedWrap)) &&
+         "NoWrapKind invalid!");
+
+  unsigned BitWidth = C.getBitWidth();
+  if (BinOp != Instruction::Add)
+    // Conservative answer: empty set
+    return ConstantRange(BitWidth, false);
+
+  if (C.isMinValue())
+    // Full set: nothing signed / unsigned wraps when added to 0.
+    return ConstantRange(BitWidth);
+
+  ConstantRange Result(BitWidth);
+
+  if (NoWrapKind & OBO::NoUnsignedWrap)
+    Result = SubsetIntersect(Result,
+                             ConstantRange(APInt::getNullValue(BitWidth), -C));
+
+  if (NoWrapKind & OBO::NoSignedWrap) {
+    if (C.isStrictlyPositive())
+      Result = SubsetIntersect(
+          Result, ConstantRange(APInt::getSignedMinValue(BitWidth),
+                                APInt::getSignedMinValue(BitWidth) - C));
+    else
+      Result = SubsetIntersect(
+          Result, ConstantRange(APInt::getSignedMinValue(BitWidth) - C,
+                                APInt::getSignedMinValue(BitWidth)));
+  }
+
+  return Result;
+}
+
 /// 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.
 ///

llvm/trunk/unittests/IR/ConstantRangeTest.cpp

 //===- ConstantRangeTest.cpp - ConstantRange tests ------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Instructions.h"
+#include "llvm/IR/Operator.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
 
 namespace {
 
 class ConstantRangeTest : public ::testing::Test {
 protected:
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)));
 }
 
+TEST(ConstantRange, MakeOverflowingRegion) {
+  const int IntMin4Bits = 8;
+  const int IntMax4Bits = 7;
+  typedef OverflowingBinaryOperator OBO;
+
+  for (int Const : {0, -1, -2, 1, 2, IntMin4Bits, IntMax4Bits}) {
+    APInt C(4, Const, true /* = isSigned */);
+
+    auto NUWRegion =
+      ConstantRange::makeNoWrapRegion(Instruction::Add, C, OBO::NoUnsignedWrap);
+
+    EXPECT_FALSE(NUWRegion.isEmptySet());
+
+    auto NSWRegion =
+      ConstantRange::makeNoWrapRegion(Instruction::Add, C, OBO::NoSignedWrap);
+
+    EXPECT_FALSE(NSWRegion.isEmptySet());
+
+    auto NoWrapRegion = ConstantRange::makeNoWrapRegion(
+        Instruction::Add, C, OBO::NoSignedWrap | OBO::NoUnsignedWrap);
+
+    EXPECT_FALSE(NoWrapRegion.isEmptySet());
+    EXPECT_TRUE(NUWRegion.intersectWith(NSWRegion).contains(NoWrapRegion));
+
+    for (APInt I = NUWRegion.getLower(), E = NUWRegion.getUpper(); I != E;
+         ++I) {
+      bool Overflow = false;
+      I.uadd_ov(C, Overflow);
+      EXPECT_FALSE(Overflow);
+    }
+
+    for (APInt I = NSWRegion.getLower(), E = NSWRegion.getUpper(); I != E;
+         ++I) {
+      bool Overflow = false;
+      I.sadd_ov(C, Overflow);
+      EXPECT_FALSE(Overflow);
+    }
+
+    for (APInt I = NoWrapRegion.getLower(), E = NoWrapRegion.getUpper(); I != E;
+         ++I) {
+      bool Overflow = false;
+
+      I.sadd_ov(C, Overflow);
+      EXPECT_FALSE(Overflow);
+
+      I.uadd_ov(C, Overflow);
+      EXPECT_FALSE(Overflow);
+    }
+  }
+}
+
 }  // anonymous namespace