From 32cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604 Mon Sep 17 00:00:00 2001 From: Nick Lewycky Date: Mon, 6 Sep 2010 23:52:49 +0000 Subject: [PATCH] Add a new isSignWrappedSet() method to ConstantRange. Fix zeroExtend and signExtend to support empty sets, and to return the smallest possible result set which contains the extension of each element in their inputs. For example zext i8 [100, 10) to i16 is now [0, 256), not i16 [100, 10) which contains 63446 members. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@113187 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Support/ConstantRange.h | 5 +++++ lib/Support/ConstantRange.cpp | 18 ++++++++++++++--- unittests/Support/ConstantRangeTest.cpp | 26 +++++++++++++++++++++---- 3 files changed, 42 insertions(+), 7 deletions(-) diff --git a/include/llvm/Support/ConstantRange.h b/include/llvm/Support/ConstantRange.h index 29086b2ac4f..2af2cf61eae 100644 --- a/include/llvm/Support/ConstantRange.h +++ b/include/llvm/Support/ConstantRange.h @@ -92,6 +92,11 @@ public: /// bool isWrappedSet() const; + /// isSignWrappedSet - Return true if this set wraps around the INT_MIN of + /// its bitwidth, for example: i8 [120, 140). + /// + bool isSignWrappedSet() const; + /// contains - Return true if the specified value is in the set. /// bool contains(const APInt &Val) const; diff --git a/lib/Support/ConstantRange.cpp b/lib/Support/ConstantRange.cpp index 8ef3785f533..defb8189b62 100644 --- a/lib/Support/ConstantRange.cpp +++ b/lib/Support/ConstantRange.cpp @@ -115,6 +115,14 @@ bool ConstantRange::isWrappedSet() const { return Lower.ugt(Upper); } +/// isSignWrappedSet - Return true if this set wraps around the INT_MIN of +/// its bitwidth, for example: i8 [120, 140). +/// +bool ConstantRange::isSignWrappedSet() const { + return contains(APInt::getSignedMaxValue(getBitWidth())) && + contains(APInt::getSignedMinValue(getBitWidth())); +} + /// getSetSize - Return the number of elements in this set. /// APInt ConstantRange::getSetSize() const { @@ -408,10 +416,12 @@ ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const { /// correspond to the possible range of values as if the source range had been /// zero extended. ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const { + if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false); + unsigned SrcTySize = getBitWidth(); assert(SrcTySize < DstTySize && "Not a value extension"); - if (isFullSet()) - // Change a source full set into [0, 1 << 8*numbytes) + if (isFullSet() || isWrappedSet()) + // Change into [0, 1 << src bit width) return ConstantRange(APInt(DstTySize,0), APInt(DstTySize,1).shl(SrcTySize)); APInt L = Lower; L.zext(DstTySize); @@ -424,9 +434,11 @@ ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const { /// correspond to the possible range of values as if the source range had been /// sign extended. ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const { + if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false); + unsigned SrcTySize = getBitWidth(); assert(SrcTySize < DstTySize && "Not a value extension"); - if (isFullSet()) { + if (isFullSet() || isSignWrappedSet()) { return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1), APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1); } diff --git a/unittests/Support/ConstantRangeTest.cpp b/unittests/Support/ConstantRangeTest.cpp index 091ecd4aade..1cedeae50af 100644 --- a/unittests/Support/ConstantRangeTest.cpp +++ b/unittests/Support/ConstantRangeTest.cpp @@ -146,6 +146,22 @@ TEST_F(ConstantRangeTest, GetMinsAndMaxes) { APInt(4, 7)); } +TEST_F(ConstantRangeTest, SignWrapped) { + EXPECT_TRUE(Full.isSignWrappedSet()); + EXPECT_FALSE(Empty.isSignWrappedSet()); + EXPECT_FALSE(One.isSignWrappedSet()); + EXPECT_FALSE(Some.isSignWrappedSet()); + EXPECT_TRUE(Wrap.isSignWrappedSet()); + + EXPECT_FALSE(ConstantRange(APInt(8, 127), APInt(8, 128)).isSignWrappedSet()); + EXPECT_TRUE(ConstantRange(APInt(8, 127), APInt(8, 129)).isSignWrappedSet()); + EXPECT_FALSE(ConstantRange(APInt(8, 128), APInt(8, 129)).isSignWrappedSet()); + EXPECT_TRUE(ConstantRange(APInt(8, 10), APInt(8, 9)).isSignWrappedSet()); + EXPECT_TRUE(ConstantRange(APInt(8, 10), APInt(8, 250)).isSignWrappedSet()); + EXPECT_FALSE(ConstantRange(APInt(8, 250), APInt(8, 10)).isSignWrappedSet()); + EXPECT_FALSE(ConstantRange(APInt(8, 250), APInt(8, 251)).isSignWrappedSet()); +} + TEST_F(ConstantRangeTest, Trunc) { ConstantRange TFull = Full.truncate(10); ConstantRange TEmpty = Empty.truncate(10); @@ -171,8 +187,7 @@ TEST_F(ConstantRangeTest, ZExt) { APInt(One.getUpper()).zext(20))); EXPECT_EQ(ZSome, ConstantRange(APInt(Some.getLower()).zext(20), APInt(Some.getUpper()).zext(20))); - EXPECT_EQ(ZWrap, ConstantRange(APInt(Wrap.getLower()).zext(20), - APInt(Wrap.getUpper()).zext(20))); + EXPECT_EQ(ZWrap, ConstantRange(APInt(20, 0), APInt(20, 0x10000))); } TEST_F(ConstantRangeTest, SExt) { @@ -188,8 +203,11 @@ TEST_F(ConstantRangeTest, SExt) { APInt(One.getUpper()).sext(20))); EXPECT_EQ(SSome, ConstantRange(APInt(Some.getLower()).sext(20), APInt(Some.getUpper()).sext(20))); - EXPECT_EQ(SWrap, ConstantRange(APInt(Wrap.getLower()).sext(20), - APInt(Wrap.getUpper()).sext(20))); + EXPECT_EQ(SWrap, ConstantRange(APInt(20, (uint64_t)INT16_MIN, true), + APInt(20, INT16_MAX + 1, true))); + + EXPECT_EQ(ConstantRange(APInt(8, 120), APInt(8, 140)).signExtend(16), + ConstantRange(APInt(16, -128), APInt(16, 128))); } TEST_F(ConstantRangeTest, IntersectWith) { -- 2.34.1