///
class ConstantRange {
APInt Lower, Upper;
- static ConstantRange intersect1Wrapped(const ConstantRange &LHS,
- const ConstantRange &RHS);
public:
/// Initialize a full (the default) or empty set for the specified bit width.
ConstantRange sextOrTrunc(uint32_t BitWidth) const;
/// add - Return a new range representing the possible values resulting
- /// from an addition of a value in this range and a value in Other.
+ /// from an addition of a value in this range and a value in \p Other.
ConstantRange add(const ConstantRange &Other) const;
+ /// sub - Return a new range representing the possible values resulting
+ /// from a subtraction of a value in this range and a value in \p Other.
+ ConstantRange sub(const ConstantRange &Other) const;
+
/// multiply - Return a new range representing the possible values resulting
- /// from a multiplication of a value in this range and a value in Other.
+ /// from a multiplication of a value in this range and a value in \p Other.
/// TODO: This isn't fully implemented yet.
ConstantRange multiply(const ConstantRange &Other) const;
/// smax - Return a new range representing the possible values resulting
- /// from a signed maximum of a value in this range and a value in Other.
+ /// from a signed maximum of a value in this range and a value in \p Other.
ConstantRange smax(const ConstantRange &Other) const;
/// umax - Return a new range representing the possible values resulting
- /// from an unsigned maximum of a value in this range and a value in Other.
+ /// from an unsigned maximum of a value in this range and a value in \p Other.
ConstantRange umax(const ConstantRange &Other) const;
/// udiv - Return a new range representing the possible values resulting
- /// from an unsigned division of a value in this range and a value in Other.
- /// TODO: This isn't fully implemented yet.
+ /// from an unsigned division of a value in this range and a value in
+ /// \p Other.
ConstantRange udiv(const ConstantRange &Other) const;
/// shl - Return a new range representing the possible values resulting
- /// from a left shift of a value in this range by the Amount value.
- ConstantRange shl(const ConstantRange &Amount) const;
-
- /// ashr - Return a new range representing the possible values resulting from
- /// an arithmetic right shift of a value in this range by the Amount value.
- ConstantRange ashr(const ConstantRange &Amount) const;
+ /// from a left shift of a value in this range by a value in \p Other.
+ /// TODO: This isn't fully implemented yet.
+ ConstantRange shl(const ConstantRange &Other) const;
- /// shr - Return a new range representing the possible values resulting
- /// from a logical right shift of a value in this range by the Amount value.
- ConstantRange lshr(const ConstantRange &Amount) const;
+ /// lshr - Return a new range representing the possible values resulting
+ /// from a logical right shift of a value in this range and a value in
+ /// \p Other.
+ ConstantRange lshr(const ConstantRange &Other) const;
/// inverse - Return a new range that is the logical not of the current set.
+ ///
ConstantRange inverse() const;
/// print - Print out the bounds to a stream...
/// Initialize a range to hold the single specified value.
///
-ConstantRange::ConstantRange(const APInt & V) : Lower(V), Upper(V + 1) {}
+ConstantRange::ConstantRange(const APInt &V) : Lower(V), Upper(V + 1) {}
ConstantRange::ConstantRange(const APInt &L, const APInt &U) :
Lower(L), Upper(U) {
}
/// contains - Return true if the argument is a subset of this range.
-/// Two equal set contain each other. The empty set is considered to be
-/// contained by all other sets.
+/// Two equal sets contain each other. The empty set contained by all other
+/// sets.
///
bool ConstantRange::contains(const ConstantRange &Other) const {
- if (isFullSet()) return true;
- if (Other.isFullSet()) return false;
- if (Other.isEmptySet()) return true;
- if (isEmptySet()) return false;
+ if (isFullSet() || Other.isEmptySet()) return true;
+ if (isEmptySet() || Other.isFullSet()) return false;
if (!isWrappedSet()) {
if (Other.isWrappedSet())
return ConstantRange(Lower - Val, Upper - Val);
}
-
-// intersect1Wrapped - This helper function is used to intersect two ranges when
-// it is known that LHS is wrapped and RHS isn't.
-//
-ConstantRange
-ConstantRange::intersect1Wrapped(const ConstantRange &LHS,
- const ConstantRange &RHS) {
- assert(LHS.isWrappedSet() && !RHS.isWrappedSet());
-
- // Check to see if we overlap on the Left side of RHS...
- //
- if (RHS.Lower.ult(LHS.Upper)) {
- // We do overlap on the left side of RHS, see if we overlap on the right of
- // RHS...
- if (RHS.Upper.ugt(LHS.Lower)) {
- // Ok, the result overlaps on both the left and right sides. See if the
- // resultant interval will be smaller if we wrap or not...
- //
- if (LHS.getSetSize().ult(RHS.getSetSize()))
- return LHS;
- else
- return RHS;
-
- } else {
- // No overlap on the right, just on the left.
- return ConstantRange(RHS.Lower, LHS.Upper);
- }
- } else {
- // We don't overlap on the left side of RHS, see if we overlap on the right
- // of RHS...
- if (RHS.Upper.ugt(LHS.Lower)) {
- // Simple overlap...
- return ConstantRange(LHS.Lower, RHS.Upper);
- } else {
- // No overlap...
- return ConstantRange(LHS.getBitWidth(), false);
- }
- }
-}
-
/// intersectWith - Return the range that results from the intersection of this
/// range with another range. The resultant range is guaranteed to include all
/// elements contained in both input ranges, and to have the smallest possible
assert(SrcTySize > DstTySize && "Not a value truncation");
APInt Size(APInt::getLowBitsSet(SrcTySize, DstTySize));
if (isFullSet() || getSetSize().ugt(Size))
- return ConstantRange(DstTySize);
+ return ConstantRange(DstTySize, /*isFullSet=*/true);
APInt L = Lower; L.trunc(DstTySize);
APInt U = Upper; U.trunc(DstTySize);
return X;
}
+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.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))
+ // 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
}
ConstantRange
-ConstantRange::shl(const ConstantRange &Amount) const {
- if (isEmptySet())
- return *this;
+ConstantRange::shl(const ConstantRange &Other) const {
+ if (isEmptySet() || Other.isEmptySet())
+ return ConstantRange(getBitWidth(), /*isFullSet=*/false);
- APInt min = getUnsignedMin() << Amount.getUnsignedMin();
- APInt max = getUnsignedMax() << Amount.getUnsignedMax();
+ APInt min = getUnsignedMin().shl(Other.getUnsignedMin());
+ APInt max = getUnsignedMax().shl(Other.getUnsignedMax());
// there's no overflow!
APInt Zeros(getBitWidth(), getUnsignedMax().countLeadingZeros());
- if (Zeros.uge(Amount.getUnsignedMax()))
- return ConstantRange(min, max);
+ if (Zeros.ugt(Other.getUnsignedMax()))
+ return ConstantRange(min, max + 1);
// FIXME: implement the other tricky cases
- return ConstantRange(getBitWidth());
+ return ConstantRange(getBitWidth(), /*isFullSet=*/true);
}
ConstantRange
-ConstantRange::ashr(const ConstantRange &Amount) const {
- if (isEmptySet())
- return *this;
-
- APInt min = getUnsignedMax().ashr(Amount.getUnsignedMin());
- APInt max = getUnsignedMin().ashr(Amount.getUnsignedMax());
- return ConstantRange(min, max);
-}
-
-ConstantRange
-ConstantRange::lshr(const ConstantRange &Amount) const {
- if (isEmptySet())
- return *this;
+ConstantRange::lshr(const ConstantRange &Other) const {
+ if (isEmptySet() || Other.isEmptySet())
+ return ConstantRange(getBitWidth(), /*isFullSet=*/false);
- APInt min = getUnsignedMax().lshr(Amount.getUnsignedMin());
- APInt max = getUnsignedMin().lshr(Amount.getUnsignedMax());
- return ConstantRange(min, max);
+ APInt max = getUnsignedMax().lshr(Other.getUnsignedMin());
+ APInt min = getUnsignedMin().lshr(Other.getUnsignedMax());
+ if (min == max + 1)
+ return ConstantRange(getBitWidth(), /*isFullSet=*/true);
+
+ return ConstantRange(min, max + 1);
}
ConstantRange ConstantRange::inverse() const {
if (isFullSet()) {
- return ConstantRange(APInt::getNullValue(Lower.getBitWidth()),
- APInt::getNullValue(Lower.getBitWidth()));
+ return ConstantRange(getBitWidth(), /*isFullSet=*/false);
} else if (isEmptySet()) {
- return ConstantRange(APInt::getAllOnesValue(Lower.getBitWidth()),
- APInt::getAllOnesValue(Lower.getBitWidth()));
+ return ConstantRange(getBitWidth(), /*isFullSet=*/true);
}
return ConstantRange(Upper, Lower);
}
void ConstantRange::dump() const {
print(dbgs());
}
-
-
EXPECT_EQ(Empty.add(Wrap), Empty);
EXPECT_EQ(Empty.add(APInt(16, 4)), Empty);
EXPECT_EQ(Some.add(APInt(16, 4)),
- ConstantRange(APInt(16, 0xe), APInt(16, 0xaae)));
+ ConstantRange(APInt(16, 0xe), APInt(16, 0xaae)));
EXPECT_EQ(Wrap.add(APInt(16, 4)),
- ConstantRange(APInt(16, 0xaae), APInt(16, 0xe)));
+ ConstantRange(APInt(16, 0xaae), APInt(16, 0xe)));
EXPECT_EQ(One.add(APInt(16, 4)),
- ConstantRange(APInt(16, 0xe)));
+ ConstantRange(APInt(16, 0xe)));
+}
+
+TEST_F(ConstantRangeTest, Sub) {
+ EXPECT_EQ(Full.sub(APInt(16, 4)), Full);
+ EXPECT_EQ(Full.sub(Full), Full);
+ EXPECT_EQ(Full.sub(Empty), Empty);
+ EXPECT_EQ(Full.sub(One), Full);
+ EXPECT_EQ(Full.sub(Some), Full);
+ EXPECT_EQ(Full.sub(Wrap), Full);
+ EXPECT_EQ(Empty.sub(Empty), Empty);
+ EXPECT_EQ(Empty.sub(One), Empty);
+ EXPECT_EQ(Empty.sub(Some), Empty);
+ EXPECT_EQ(Empty.sub(Wrap), Empty);
+ EXPECT_EQ(Empty.sub(APInt(16, 4)), Empty);
+ EXPECT_EQ(Some.sub(APInt(16, 4)),
+ ConstantRange(APInt(16, 0x6), APInt(16, 0xaa6)));
+ EXPECT_EQ(Wrap.sub(APInt(16, 4)),
+ ConstantRange(APInt(16, 0xaa6), APInt(16, 0x6)));
+ EXPECT_EQ(One.sub(APInt(16, 4)),
+ ConstantRange(APInt(16, 0x6)));
}
TEST_F(ConstantRangeTest, Multiply) {
EXPECT_EQ(Wrap.udiv(Wrap), Full);
}
+TEST_F(ConstantRangeTest, Shl) {
+ EXPECT_EQ(Full.shl(Full), Full);
+ EXPECT_EQ(Full.shl(Empty), Empty);
+ EXPECT_EQ(Full.shl(One), Full); // TODO: [0, (-1 << 0xa) + 1)
+ EXPECT_EQ(Full.shl(Some), Full); // TODO: [0, (-1 << 0xa) + 1)
+ EXPECT_EQ(Full.shl(Wrap), Full);
+ EXPECT_EQ(Empty.shl(Empty), Empty);
+ EXPECT_EQ(Empty.shl(One), Empty);
+ EXPECT_EQ(Empty.shl(Some), Empty);
+ EXPECT_EQ(Empty.shl(Wrap), Empty);
+ EXPECT_EQ(One.shl(One), ConstantRange(APInt(16, 0xa << 0xa),
+ APInt(16, (0xa << 0xa) + 1)));
+ EXPECT_EQ(One.shl(Some), Full); // TODO: [0xa << 0xa, 0)
+ EXPECT_EQ(One.shl(Wrap), Full); // TODO: [0xa, 0xa << 14 + 1)
+ EXPECT_EQ(Some.shl(Some), Full); // TODO: [0xa << 0xa, 0xfc01)
+ EXPECT_EQ(Some.shl(Wrap), Full); // TODO: [0xa, 0x7ff << 0x5 + 1)
+ EXPECT_EQ(Wrap.shl(Wrap), Full);
+}
+
+TEST_F(ConstantRangeTest, Lshr) {
+ EXPECT_EQ(Full.lshr(Full), Full);
+ EXPECT_EQ(Full.lshr(Empty), Empty);
+ EXPECT_EQ(Full.lshr(One), ConstantRange(APInt(16, 0),
+ APInt(16, (0xffff >> 0xa) + 1)));
+ EXPECT_EQ(Full.lshr(Some), ConstantRange(APInt(16, 0),
+ APInt(16, (0xffff >> 0xa) + 1)));
+ EXPECT_EQ(Full.lshr(Wrap), Full);
+ EXPECT_EQ(Empty.lshr(Empty), Empty);
+ EXPECT_EQ(Empty.lshr(One), Empty);
+ EXPECT_EQ(Empty.lshr(Some), Empty);
+ EXPECT_EQ(Empty.lshr(Wrap), Empty);
+ EXPECT_EQ(One.lshr(One), ConstantRange(APInt(16, 0)));
+ EXPECT_EQ(One.lshr(Some), ConstantRange(APInt(16, 0)));
+ EXPECT_EQ(One.lshr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
+ EXPECT_EQ(Some.lshr(Some), ConstantRange(APInt(16, 0),
+ APInt(16, (0xaaa >> 0xa) + 1)));
+ EXPECT_EQ(Some.lshr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
+ EXPECT_EQ(Wrap.lshr(Wrap), Full);
+}
+
} // anonymous namespace
projects / oota-llvm.git / commitdiff