Skip to content

Commit

Permalink
[ConstantRange] Add setSizeSmallerThanOf method.
Browse files Browse the repository at this point in the history
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%

Reviewers: sanjoy, atrick, pete

Subscribers: llvm-commits

Differential Revision: https://reviews.llvm.org/D31104

llvm-svn: 298236
  • Loading branch information
Michael Zolotukhin committed Mar 20, 2017
1 parent b5c2bfa commit c69955c
Showing 2 changed files with 28 additions and 10 deletions.
4 changes: 4 additions & 0 deletions llvm/include/llvm/IR/ConstantRange.h
Original file line number Diff line number Diff line change
@@ -184,6 +184,10 @@ class ConstantRange {
///
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;
34 changes: 24 additions & 10 deletions llvm/lib/IR/ConstantRange.cpp
Original file line number Diff line number Diff line change
@@ -272,6 +272,22 @@ APInt ConstantRange::getSetSize() const {
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.
///
@@ -414,7 +430,7 @@ ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
if (CR.Upper.ule(Lower))
return ConstantRange(CR.Lower, Upper);

if (getSetSize().ult(CR.getSetSize()))
if (isSizeStrictlySmallerThanOf(CR))
return *this;
return CR;
}
@@ -429,7 +445,7 @@ ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {

if (CR.Upper.ult(Upper)) {
if (CR.Lower.ult(Upper)) {
if (getSetSize().ult(CR.getSetSize()))
if (isSizeStrictlySmallerThanOf(CR))
return *this;
return CR;
}
@@ -445,7 +461,7 @@ ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {

return ConstantRange(CR.Lower, Upper);
}
if (getSetSize().ult(CR.getSetSize()))
if (isSizeStrictlySmallerThanOf(CR))
return *this;
return CR;
}
@@ -739,17 +755,16 @@ ConstantRange::add(const ConstantRange &Other) const {
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;
}

@@ -773,17 +788,16 @@ ConstantRange::sub(const ConstantRange &Other) const {
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;
}

@@ -837,7 +851,7 @@ ConstantRange::multiply(const ConstantRange &Other) const {
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

0 comments on commit c69955c

Please sign in to comment.