[ConstantRange] Add makeAllowedNoWrapRegion()

[nikic]

Summary

This adds a counterpart to makeGuaranteedNoWrapRegion(): While makeGNWR creates an LHS range which will never cause overflow, makeANWR creates a range outside of which will always cause overflow (more specifically: the smallest such range -- a conservative implementation would be to always return the full range). The intended use-case is to intersect the LHS operand of nuw/nsw operations with it.

The implementation is to the most part exactly the same as makeGNWR but with min/max swapped. The only non-trivial case is signed multiplication, where we need to take into account both the smallest non-negative value and the largest negative one (insofar as they exist). These are extracted by intersecting with the signed half-spaces.

[lebedev.ri]

This kinds fell off my radar (best to ping weekly).
I should ask, can this be implemented in terms of some other function[s], to reduce code duplication?

[nikic]

@lebedev.ri For the mul part I think I have already extracted the reusable parts (the exact nuw/nsw calculation). For add/sub the code for guaranteed and allowed nowrap region is really similar, the only difference is basically that min/max is swapped everywhere. However, I'm not sure how I can share this code in a way that makes sense semantically.

One possibility that comes to mind is to extract more "exact" (single value) helper functions like this:

static ConstantRange makeExactAddNSWRegion(const APInt &V) {
  APInt SignedMinVal = APInt::getSignedMinValue(V.getBitWidth());
  if (V.isNegative())
    return ConstantRange::getNonEmpty(SignedMinVal - V, SignedMinVal);
  else
    return ConstantRange::getNonEmpty(SignedMinVal, SignedMinVal - V);
}

and then compute guaranteed/allowed as either an intersection or union of them:

// guaranteed
makeExactAddNSWRegion(Other.getSignedMin())
    .intersectWith(Other.getSignedMax())
// allowed
makeExactAddNSWRegion(Other.getSignedMin())
    .unionWith(Other.getSignedMax())

That would maybe be semantically cleaner, though less efficient than explicitly constructing the result range.

[lebedev.ri]

I'm sorry.
I was initially hoping someone else would comment on the semantics (@sanjoy ?),
but then this has completely fallen off my radar.

I think this is ok, but it would be good to have at least one actual piece of code that actually uses this.

[nikic]

Abandoning this revision, as we didn't end up having a use-case for this after all. This was intended for use with nowrap CR implementations, but turned out to not be sufficient for that purpose.

llvm/include/llvm/IR/ConstantRange.h

public:
   ///  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 smallest range such that for all Y in Other and all X *not*
+  /// in the result, "X BinOp Y" wraps. This can be seen as the inverse of a
+  /// "guaranteed always wrap region". The AllowedNoWrapRegion can be used to
+  /// restrict the range of the LHS operand, as any value outside of it must
+  /// wrap regardless of the RHS value.
+  static ConstantRange makeAllowedNoWrapRegion(Instruction::BinaryOps BinOp,
+                                               const ConstantRange &Other,
+                                               unsigned NoWrapKind);
+
   /// Produce the range that contains X if and only if "X BinOp Other" does
   /// not 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

llvm/lib/IR/ConstantRange.cpp

case Instruction::Mul:
     if (Unsigned)
       return makeExactMulNUWRegion(Other.getUnsignedMax());
 
     return makeExactMulNSWRegion(Other.getSignedMin())
         .intersectWith(makeExactMulNSWRegion(Other.getSignedMax()));
   }
 }
 
+ConstantRange
+ConstantRange::makeAllowedNoWrapRegion(Instruction::BinaryOps BinOp,
+                                       const ConstantRange &Other,
+                                       unsigned NoWrapKind) {
+  using OBO = OverflowingBinaryOperator;
+  assert((NoWrapKind == OBO::NoSignedWrap ||
+          NoWrapKind == OBO::NoUnsignedWrap) &&
+         "NoWrapKind invalid!");
+
+  bool Unsigned = NoWrapKind == OBO::NoUnsignedWrap;
+  unsigned BitWidth = Other.getBitWidth();
+
+  switch (BinOp) {
+  default:
+    llvm_unreachable("Unsupported binary op");
+
+  case Instruction::Add: {
+    if (Unsigned)
+      return getNonEmpty(APInt::getNullValue(BitWidth),
+                         -Other.getUnsignedMin());
+
+    APInt SignedMinVal = APInt::getSignedMinValue(BitWidth);
+    APInt SMin = Other.getSignedMin(), SMax = Other.getSignedMax();
+    return getNonEmpty(
+        SMax.isNegative() ? SignedMinVal - SMax : SignedMinVal,
+        SMin.isStrictlyPositive() ? SignedMinVal - SMin : SignedMinVal);
+  }
+
+  case Instruction::Sub: {
+    if (Unsigned)
+      return getNonEmpty(Other.getUnsignedMin(), APInt::getMinValue(BitWidth));
+
+    APInt SignedMinVal = APInt::getSignedMinValue(BitWidth);
+    APInt SMin = Other.getSignedMin(), SMax = Other.getSignedMax();
+    return getNonEmpty(
+        SMin.isStrictlyPositive() ? SignedMinVal + SMin : SignedMinVal,
+        SMax.isNegative() ? SignedMinVal + SMax : SignedMinVal);
+  }
+
+  case Instruction::Mul: {
+    if (Unsigned)
+      return makeExactMulNUWRegion(Other.getUnsignedMin());
+
+    ConstantRange NonNegCR = Other.intersectWith(
+        ConstantRange(APInt(BitWidth, 0),
+                      APInt::getSignedMinValue(BitWidth)));
+    ConstantRange NegCR = Other.intersectWith(
+        ConstantRange(APInt::getSignedMinValue(BitWidth),
+                      APInt::getNullValue(BitWidth)));
+    ConstantRange Result(BitWidth, /* full */ false);
+    if (!NonNegCR.isEmptySet())
+      Result = makeExactMulNSWRegion(NonNegCR.Lower);
+    if (!NegCR.isEmptySet())
+      Result = Result.unionWith(makeExactMulNSWRegion(NegCR.Upper - 1));
+    return Result;
+  }
+  }
+}
+
 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);
 }
 

llvm/unittests/IR/ConstantRangeTest.cpp

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 GuaranteedNoWrap =
             ConstantRange::makeGuaranteedNoWrapRegion(BinOp, CR2, NoWrapKind);
+        ConstantRange AllowedNoWrap =
+            ConstantRange::makeAllowedNoWrapRegion(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));
+          EXPECT_EQ(NoOverflow, GuaranteedNoWrap.contains(N1));
+          EXPECT_EQ(Overflow, !AllowedNoWrap.contains(N1));
 
           // The no-wrap range is exact for single-element ranges.
           if (CR2.isSingleElement()) {
-            EXPECT_EQ(Overflow, !NoWrap.contains(N1));
+            EXPECT_EQ(GuaranteedNoWrap, AllowedNoWrap);
           }
         });
       });
 }
 
 // Show that makeGuaranteedNoWrapRegion() is maximal, and for single-element
 // ranges also exact.
 TEST(ConstantRange, NoWrapRegionExhaustive) {