[ConstantRange] Reduce the number of allocations in ConstantRange::makeGuaranteedNoWrapRegion

[craig.topper]

Summary

Currently, makeGuaranteedNoWrapRegion creates 3 temporary APInts each time it calls SubsetIntersect. Two to hold the inverses of CR0 and CR1 and one to hold the result before inverting for the return. If the APInt is larger than 64-bits, each of these represents an allocation. We're also doing extra inversions on Result if SubsetIntersect is called multiple time.

This patch adds an inverseInPlace method that will turn a ConstantRange to its inverse without creating a new object. This can help remove the temporary allocations.

Additionally, we now store Result in its inverse form through all of the possible calls to SubsetIntersect and only invert it at the end before the return. I've modified the lambda to write to read/write Result through a capture so that it no longer looks like a generic function. It also takes Other by value now so that we can capture the temporary ConstantRange that's always passed to it and call inverseInPlace on it.

[craig.topper]

Ping

[sanjoy]

Hi Craig,

I think this change makes makeGuaranteedNoWrapRegion less readable. Did you take a look at implementing a ConstantRange::subsetIntersectWith directly? That'll be more work, but I think the end result will be cleaner.

[craig.topper]

Add a new subsetIntersectWith method that doesn't rely on inverting and calling unionWith.

I'll work on some unit tests, but wanted another set of eyes on the various cases.

[davide]

This patch switches a one-liner with a much larger function.
Overall, I don't think this is necessarily unreasonable, but the increased complexity needs to be justified.
Craig, were you able to measure any measurable performance impact (in compile time) from the reduced malloc traffic?
If so, can you show the numbers?

[craig.topper]

This was based on reviewing the output of callgrind on one file and seeing what places create a lot of wider than 64-bit APInts. I can try to collect a larger data set of real numbers.

Thinking about this more, I wonder if this is even the right interface for the question some of the callers are trying to determine.

Several of the callers call this and then check if the nowrap range fully contains another range. But the makeGuaranteedNoWrap register sometimes makes compromises where it has to decide pick two different possible ranges to return by deciding which choice is larger. You can see this in the two places in where we compute d1 and d2 in my last patch. But its possible the range the caller wants to check is contained inside the smaller choice, but not the larger choice. Should we instead have a method to ask if the addition of two ranges won't cause overflow directly without having to create a possibly compromised nowrap region?

include/llvm/IR/ConstantRange.h

public:
 
   /// Return the range that results from the union of this range
   /// with another range.  The resultant range is guaranteed to include the
   /// elements of both sets, but may contain more.  For example, [3, 9) union
   /// [12,15) is [3, 15), which includes 9, 10, and 11, which were not included
   /// in either set before.
   ConstantRange unionWith(const ConstantRange &CR) const;
 
+  /// Computes the intersection of this range with another range. It is
+  /// different from intersectWith in that the ConstantRange returned will only
+  /// contain elements in both CR0 and CR1 (i.e. subsetIntersectWith(X, Y) is a
+  /// *subset*, proper or not, of both X and Y).
+  ConstantRange subsetIntersectWith(const ConstantRange &CR) const;
+
   /// Return a new range representing the possible values resulting
   /// from an application of the specified cast operator to this range. \p
   /// BitWidth is the target bitwidth of the cast.  For casts which don't
   /// change bitwidth, it must be the same as the source bitwidth.  For casts
   /// which do change bitwidth, the bitwidth must be consistent with the
   /// requested cast and source bitwidth.
   ConstantRange castOp(Instruction::CastOps CastOp,
                        uint32_t BitWidth) const;

lib/IR/ConstantRange.cpp

 }
 
 ConstantRange
 ConstantRange::makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp,
                                           const ConstantRange &Other,
                                           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 = Other.getBitWidth();
   if (BinOp != Instruction::Add)
     // Conservative answer: empty set
-    return ConstantRange(BitWidth, false);
+    return ConstantRange(BitWidth, /* empty */ false);
 
   if (auto *C = Other.getSingleElement())
     if (C->isNullValue())
       // Full set: nothing signed / unsigned wraps when added to 0.
-      return ConstantRange(BitWidth);
+      return ConstantRange(BitWidth, /* full */ true);
 
   ConstantRange Result(BitWidth);
 
   if (NoWrapKind & OBO::NoUnsignedWrap)
-    Result =
-        SubsetIntersect(Result, ConstantRange(APInt::getNullValue(BitWidth),
-                                              -Other.getUnsignedMax()));
+    Result = Result.subsetIntersectWith(
+        ConstantRange(APInt::getNullValue(BitWidth), -Other.getUnsignedMax()));
 
   if (NoWrapKind & OBO::NoSignedWrap) {
     const APInt &SignedMin = Other.getSignedMin();
     const APInt &SignedMax = Other.getSignedMax();
 
     if (SignedMax.isStrictlyPositive())
-      Result = SubsetIntersect(
-          Result,
+      Result = Result.subsetIntersectWith(
           ConstantRange(APInt::getSignedMinValue(BitWidth),
                         APInt::getSignedMinValue(BitWidth) - SignedMax));
 
     if (SignedMin.isNegative())
-      Result = SubsetIntersect(
-          Result, ConstantRange(APInt::getSignedMinValue(BitWidth) - SignedMin,
-                                APInt::getSignedMinValue(BitWidth)));
+      Result = Result.subsetIntersectWith(
+          ConstantRange(APInt::getSignedMinValue(BitWidth) - SignedMin,
   }
 
   return Result;
 }
 
 bool ConstantRange::isFullSet() const {
   return Lower == Upper && Lower.isMaxValue();
 }
if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper))
     return ConstantRange(getBitWidth());
 
   APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
   APInt U = CR.Upper.ugt(Upper) ? CR.Upper : Upper;
 
   return ConstantRange(std::move(L), std::move(U));
 }
 
+ConstantRange
+ConstantRange::subsetIntersectWith(const ConstantRange &CR) const {
+  assert(getBitWidth() == CR.getBitWidth() &&
+         "ConstantRange types don't agree!");
+
+  if (isFullSet() || CR.isEmptySet())
+    return CR;
+  if (CR.isFullSet() || isEmptySet())
+    return *this;
+
+  if (!isWrappedSet() && CR.isWrappedSet())
+    return CR.subsetIntersectWith(*this);
+
+  if (!isWrappedSet() && !CR.isWrappedSet()) {
+    // If the ranges are disjoint, return empty set.
+    if (CR.Upper.ule(Lower) || Upper.ule(CR.Lower))
+      return ConstantRange(getBitWidth(), /* empty */ false);
+
+    // Ranges overlap.
+    APInt L = CR.Lower.ugt(Lower) ? CR.Lower : Lower;
+    APInt U = (CR.Upper - 1).ult(Upper - 1) ? CR.Upper : Upper;
+
+    assert(L != U);
+
+    return ConstantRange(std::move(L), std::move(U));
+  }
+
+  if (!CR.isWrappedSet()) {
+    // ------U   L-----  and  ------U   L----- : this
+    //   L--U                            L--U  : CR
+    if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower))
+      return CR;
+
+    // ------U   L----- : this
+    //    L---------U   : CR
+    if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper)) {
+      // Find the largest range and return it.
+      APInt d1 = Upper - CR.Lower; APInt d2 = CR.Upper - Lower;
+      if (d1.uge(d2))
+        return ConstantRange(CR.Lower, Upper);
+      return ConstantRange(Lower, CR.Upper);
+    }
+
+    // ----U       L---- : this
+    //       L---U       : CR
+    //    <d1>  <d2>
+    if (Upper.ule(CR.Lower) && CR.Upper.ule(Lower))
+      return ConstantRange(getBitWidth(), /* empty */ false);
+
+    // ----U     L----- : this
+    //        L----U    : CR
+    if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper))
+      return ConstantRange(Lower, CR.Upper);
+
+    // ------U    L---- : this
+    //    L-----U       : CR
+    assert(CR.Lower.ult(Upper) && CR.Upper.ult(Lower) &&
+           "ConstantRange::subsetIntersectWith missed a case with one range "
+           "wrapped");
+    return ConstantRange(CR.Lower, Upper);
+  }
+
+  // ------U    L----  and  ------U    L---- : this
+  // -U  L-----------  and  ------------U  L : CR
+  if (CR.Lower.ult(Upper) || Lower.ult(CR.Upper)) {
+    APInt d1 = Upper - CR.Lower; APInt d2 = CR.Upper - Lower;
+    if (d1.uge(d2))
+      return ConstantRange(CR.Lower, Upper);
+    return ConstantRange(Lower, CR.Upper);
+  }
+
+  APInt L = CR.Lower.ugt(Lower) ? CR.Lower : Lower;
+  APInt U = CR.Upper.ult(Upper) ? CR.Upper: Upper;
+
+  return ConstantRange(std::move(L), std::move(U));
+}
+
 ConstantRange ConstantRange::castOp(Instruction::CastOps CastOp,
                                     uint32_t ResultBitWidth) const {
   switch (CastOp) {
   default:
     llvm_unreachable("unsupported cast type");
   case Instruction::Trunc:
     return truncate(ResultBitWidth);
   case Instruction::SExt: