[ConstantRange] Add setSizeSmallerThanOf method.

[mzolotukhin]

Summary

ConstantRange class currently has a method getSetSize, which is mostly used to
compare set sizes of two constant ranges (there is only one spot where it's used
in a slightly different scenario). This patch introduces setSizeSmallerThanOf
method, which does such comparison in a more efficient way. In the original
method we have to extend our types to (BitWidth+1), which can result it using
slow case of APInt, extra memory allocations, etc.

The change is supposed to not change any functionality, but it slightly improves
compile time. Here is compile time improvements that I observed on CTMark:

• tramp3d-v4 -2.02%
• pairlocalalign -1.82%
• lencod -1.67%

[sanjoy]

Nice catch! LGTM.

include/llvm/IR/ConstantRange.h

187 ↗

(On Diff #92204)

Comment?

lib/IR/ConstantRange.cpp

276 ↗

(On Diff #92204)

How about calling this isStrictlySmallerThan?

Also, please add a comment on why you're not simply using getSetSize here. Otherwise a later "cleanup change" may break your optimization.

[sanjoy]

lib/IR/ConstantRange.cpp

276 ↗

(On Diff #92204)

Actually, "smaller than" can be misinterpreted.

How about isSizeStrictlySmallerThanOf?

I'm mainly trying to address two things:

• Since this is a predicate, I'd rather have its name start with is
• The set in the beginning is redundant, IMO

[mzolotukhin]

• Address review remarks.

[mzolotukhin]

Thanks for the review, Sanjoy!

A follow-up question: do we want to keep getSetSize? It's currently only used in SimplifyCFG.cpp:

if (Span.getSetSize().ugt(8) || Span.isEmptySet())

which can be replaced with something like if (!Span.isSizeStrictlySmallerThanOf(ConstantRange(8, /*full=*/ true)) || Span.isEmptySet()).

[sanjoy]

In D31104#705089, @mzolotukhin wrote:

Thanks for the review, Sanjoy!

A follow-up question: do we want to keep getSetSize? It's currently only used in SimplifyCFG.cpp:

if (Span.getSetSize().ugt(8) || Span.isEmptySet())

which can be replaced with something like if (!Span.isSizeStrictlySmallerThanOf(ConstantRange(8, /*full=*/ true)) || Span.isEmptySet()).

Won't you need !Span.isSizeStrictlySmallerThanOf(ConstantRange(3, /*full=*/ true))?

I'd actually propose adding a isSizeStrictlySmallerThan that takes an APInt, and calling it with 8.

In D31104#705089, @mzolotukhin wrote:

Thanks for the review, Sanjoy!

A follow-up question: do we want to keep getSetSize? It's currently only used in SimplifyCFG.cpp:

if (Span.getSetSize().ugt(8) || Span.isEmptySet())

which can be replaced with something like if (!Span.isSizeStrictlySmallerThanOf(ConstantRange(8, /*full=*/ true)) || Span.isEmptySet()).

I'd rather have a isSizeStrictlySmallerThan that takes a set size directly.

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

public:
   /// Return true if this set contains exactly one member.
   ///
   bool isSingleElement() const { return getSingleElement() != nullptr; }
 
   /// Return the number of elements in this set.
   ///
   APInt getSetSize() const;
 
+  /// Compare set size of this range with the range CR.
+  ///
+  bool isSizeStrictlySmallerThanOf(const ConstantRange &CR) const;
+
   /// Return the largest unsigned value contained in the ConstantRange.
   ///
   APInt getUnsignedMax() const;
 
   /// Return the smallest unsigned value contained in the ConstantRange.
   ///
   APInt getUnsignedMin() const;
 

llvm/trunk/lib/IR/ConstantRange.cpp

if (isFullSet()) {
     Size.setBit(getBitWidth());
     return Size;
   }
 
   // This is also correct for wrapped sets.
   return (Upper - Lower).zext(getBitWidth()+1);
 }
 
+/// isSizeStrictlySmallerThanOf - Compare set size of this range with the range
+/// CR.
+/// This function is faster than comparing results of getSetSize for the two
+/// ranges, because we don't need to extend bitwidth of APInts we're operating
+/// with.
+///
+bool
+ConstantRange::isSizeStrictlySmallerThanOf(const ConstantRange &Other) const {
+  assert(getBitWidth() == Other.getBitWidth());
+  if (isFullSet())
+    return false;
+  if (Other.isFullSet())
+    return true;
+  return (Upper - Lower).ult(Other.Upper - Other.Lower);
+}
+
 /// getUnsignedMax - Return the largest unsigned value contained in the
 /// ConstantRange.
 ///
 APInt ConstantRange::getUnsignedMax() const {
   if (isFullSet() || isWrappedSet())
     return APInt::getMaxValue(getBitWidth());
   return getUpper() - 1;
 }
ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
   if (isWrappedSet() && !CR.isWrappedSet()) {
     if (CR.Lower.ult(Upper)) {
       if (CR.Upper.ult(Upper))
         return CR;
 
       if (CR.Upper.ule(Lower))
         return ConstantRange(CR.Lower, Upper);
 
-      if (getSetSize().ult(CR.getSetSize()))
+      if (isSizeStrictlySmallerThanOf(CR))
         return *this;
       return CR;
     }
     if (CR.Lower.ult(Lower)) {
       if (CR.Upper.ule(Lower))
         return ConstantRange(getBitWidth(), false);
 
       return ConstantRange(Lower, CR.Upper);
     }
     return CR;
   }
 
   if (CR.Upper.ult(Upper)) {
     if (CR.Lower.ult(Upper)) {
-      if (getSetSize().ult(CR.getSetSize()))
+      if (isSizeStrictlySmallerThanOf(CR))
         return *this;
       return CR;
     }
 
     if (CR.Lower.ult(Lower))
       return ConstantRange(Lower, CR.Upper);
 
     return CR;
   }
   if (CR.Upper.ule(Lower)) {
     if (CR.Lower.ult(Lower))
       return *this;
 
     return ConstantRange(CR.Lower, Upper);
   }
-  if (getSetSize().ult(CR.getSetSize()))
+  if (isSizeStrictlySmallerThanOf(CR))
     return *this;
   return CR;
 }
 
 
 /// unionWith - 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

 
 ConstantRange
 ConstantRange::add(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();
   APInt NewLower = getLower() + Other.getLower();
   APInt NewUpper = getUpper() + Other.getUpper() - 1;
   if (NewLower == NewUpper)
     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 
   ConstantRange X = ConstantRange(NewLower, NewUpper);
-  if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y))
+  if (X.isSizeStrictlySmallerThanOf(*this) ||
+      X.isSizeStrictlySmallerThanOf(Other))
     // 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();
   APInt NewLower = getLower() - Other.getUpper() + 1;
   APInt NewUpper = getUpper() - Other.getLower();
   if (NewLower == NewUpper)
     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 
   ConstantRange X = ConstantRange(NewLower, NewUpper);
-  if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y))
+  if (X.isSizeStrictlySmallerThanOf(*this) ||
+      X.isSizeStrictlySmallerThanOf(Other))
     // We've wrapped, therefore, full set.
     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
-
   return X;
 }
 
 ConstantRange
 ConstantRange::multiply(const ConstantRange &Other) const {
   // TODO: If either operand is a single element and the multiply is known to
   // be non-wrapping, round the result min and max value to the appropriate
   // multiple of that element. If wrapping is possible, at least adjust the
ConstantRange::multiply(const ConstantRange &Other) const {
   Other_max = Other.getSignedMax().sext(getBitWidth() * 2);
   
   auto L = {this_min * Other_min, this_min * Other_max,
             this_max * Other_min, this_max * Other_max};
   auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };
   ConstantRange Result_sext(std::min(L, Compare), std::max(L, Compare) + 1);
   ConstantRange SR = Result_sext.truncate(getBitWidth());
 
-  return UR.getSetSize().ult(SR.getSetSize()) ? UR : SR;
+  return UR.isSizeStrictlySmallerThanOf(SR) ? UR : SR;
 }
 
 ConstantRange
 ConstantRange::smax(const ConstantRange &Other) const {
   // X smax Y is: range(smax(X_smin, Y_smin),
   //                    smax(X_smax, Y_smax))
   if (isEmptySet() || Other.isEmptySet())
     return ConstantRange(getBitWidth(), /*isFullSet=*/false);