From 66c5f5714a29da8b50f94829bd4261e044c84335 Mon Sep 17 00:00:00 2001 From: Nikita Popov Date: Sun, 21 Apr 2019 15:23:05 +0000 Subject: [PATCH] [ConstantRange] Add saturating add/sub methods Add support for uadd_sat and friends to ConstantRange, so we can handle uadd.sat and friends in LVI. The implementation is forwarding to the corresponding APInt methods with appropriate bounds. One thing worth pointing out here is that the handling of wrapping ranges is not maximally accurate. A simple example is that adding 0 to a wrapped range will return a full range, rather than the original wrapped range. The tests also only check that the non-wrapping envelope is correct and minimal. Differential Revision: https://reviews.llvm.org/D60946 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@358855 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/IR/ConstantRange.h | 12 ++++ lib/IR/ConstantRange.cpp | 36 ++++++++++++ unittests/IR/ConstantRangeTest.cpp | 94 ++++++++++++++++++++++++++++++ 3 files changed, 142 insertions(+) diff --git a/include/llvm/IR/ConstantRange.h b/include/llvm/IR/ConstantRange.h index 6dbe4053994..f006a9321fc 100644 --- a/include/llvm/IR/ConstantRange.h +++ b/include/llvm/IR/ConstantRange.h @@ -377,6 +377,18 @@ public: /// arithmetic right shift of a value in this range and a value in \p Other. ConstantRange ashr(const ConstantRange &Other) const; + /// Perform an unsigned saturating addition of two constant ranges. + ConstantRange uadd_sat(const ConstantRange &Other) const; + + /// Perform a signed saturating addition of two constant ranges. + ConstantRange sadd_sat(const ConstantRange &Other) const; + + /// Perform an unsigned saturating subtraction of two constant ranges. + ConstantRange usub_sat(const ConstantRange &Other) const; + + /// Perform a signed saturating subtraction of two constant ranges. + ConstantRange ssub_sat(const ConstantRange &Other) const; + /// Return a new range that is the logical not of the current set. ConstantRange inverse() const; diff --git a/lib/IR/ConstantRange.cpp b/lib/IR/ConstantRange.cpp index 7bd14e62dc1..b2bdd0abd9c 100644 --- a/lib/IR/ConstantRange.cpp +++ b/lib/IR/ConstantRange.cpp @@ -1099,6 +1099,42 @@ ConstantRange::ashr(const ConstantRange &Other) const { return getNonEmpty(std::move(min), std::move(max)); } +ConstantRange ConstantRange::uadd_sat(const ConstantRange &Other) const { + if (isEmptySet() || Other.isEmptySet()) + return getEmpty(); + + APInt NewL = getUnsignedMin().uadd_sat(Other.getUnsignedMin()); + APInt NewU = getUnsignedMax().uadd_sat(Other.getUnsignedMax()) + 1; + return getNonEmpty(std::move(NewL), std::move(NewU)); +} + +ConstantRange ConstantRange::sadd_sat(const ConstantRange &Other) const { + if (isEmptySet() || Other.isEmptySet()) + return getEmpty(); + + APInt NewL = getSignedMin().sadd_sat(Other.getSignedMin()); + APInt NewU = getSignedMax().sadd_sat(Other.getSignedMax()) + 1; + return getNonEmpty(std::move(NewL), std::move(NewU)); +} + +ConstantRange ConstantRange::usub_sat(const ConstantRange &Other) const { + if (isEmptySet() || Other.isEmptySet()) + return getEmpty(); + + APInt NewL = getUnsignedMin().usub_sat(Other.getUnsignedMax()); + APInt NewU = getUnsignedMax().usub_sat(Other.getUnsignedMin()) + 1; + return getNonEmpty(std::move(NewL), std::move(NewU)); +} + +ConstantRange ConstantRange::ssub_sat(const ConstantRange &Other) const { + if (isEmptySet() || Other.isEmptySet()) + return getEmpty(); + + APInt NewL = getSignedMin().ssub_sat(Other.getSignedMax()); + APInt NewU = getSignedMax().ssub_sat(Other.getSignedMin()) + 1; + return getNonEmpty(std::move(NewL), std::move(NewU)); +} + ConstantRange ConstantRange::inverse() const { if (isFullSet()) return getEmpty(); diff --git a/unittests/IR/ConstantRangeTest.cpp b/unittests/IR/ConstantRangeTest.cpp index 060d69126e2..3306fe3ea69 100644 --- a/unittests/IR/ConstantRangeTest.cpp +++ b/unittests/IR/ConstantRangeTest.cpp @@ -1647,4 +1647,98 @@ TEST_F(ConstantRangeTest, Negative) { }); } +template +static void TestUnsignedBinOpExhaustive(Fn1 RangeFn, Fn2 IntFn) { + unsigned Bits = 4; + EnumerateTwoConstantRanges(Bits, [&](const ConstantRange &CR1, + const ConstantRange &CR2) { + ConstantRange CR = RangeFn(CR1, CR2); + if (CR1.isEmptySet() || CR2.isEmptySet()) { + EXPECT_TRUE(CR.isEmptySet()); + return; + } + + APInt Min = APInt::getMaxValue(Bits); + APInt Max = APInt::getMinValue(Bits); + ForeachNumInConstantRange(CR1, [&](const APInt &N1) { + ForeachNumInConstantRange(CR2, [&](const APInt &N2) { + APInt N = IntFn(N1, N2); + if (N.ult(Min)) + Min = N; + if (N.ugt(Max)) + Max = N; + }); + }); + + EXPECT_EQ(ConstantRange::getNonEmpty(Min, Max + 1), CR); + }); +} + +template +static void TestSignedBinOpExhaustive(Fn1 RangeFn, Fn2 IntFn) { + unsigned Bits = 4; + EnumerateTwoConstantRanges(Bits, [&](const ConstantRange &CR1, + const ConstantRange &CR2) { + ConstantRange CR = RangeFn(CR1, CR2); + if (CR1.isEmptySet() || CR2.isEmptySet()) { + EXPECT_TRUE(CR.isEmptySet()); + return; + } + + APInt Min = APInt::getSignedMaxValue(Bits); + APInt Max = APInt::getSignedMinValue(Bits); + ForeachNumInConstantRange(CR1, [&](const APInt &N1) { + ForeachNumInConstantRange(CR2, [&](const APInt &N2) { + APInt N = IntFn(N1, N2); + if (N.slt(Min)) + Min = N; + if (N.sgt(Max)) + Max = N; + }); + }); + + EXPECT_EQ(ConstantRange::getNonEmpty(Min, Max + 1), CR); + }); +} + +TEST_F(ConstantRangeTest, UAddSat) { + TestUnsignedBinOpExhaustive( + [](const ConstantRange &CR1, const ConstantRange &CR2) { + return CR1.uadd_sat(CR2); + }, + [](const APInt &N1, const APInt &N2) { + return N1.uadd_sat(N2); + }); +} + +TEST_F(ConstantRangeTest, USubSat) { + TestUnsignedBinOpExhaustive( + [](const ConstantRange &CR1, const ConstantRange &CR2) { + return CR1.usub_sat(CR2); + }, + [](const APInt &N1, const APInt &N2) { + return N1.usub_sat(N2); + }); +} + +TEST_F(ConstantRangeTest, SAddSat) { + TestSignedBinOpExhaustive( + [](const ConstantRange &CR1, const ConstantRange &CR2) { + return CR1.sadd_sat(CR2); + }, + [](const APInt &N1, const APInt &N2) { + return N1.sadd_sat(N2); + }); +} + +TEST_F(ConstantRangeTest, SSubSat) { + TestSignedBinOpExhaustive( + [](const ConstantRange &CR1, const ConstantRange &CR2) { + return CR1.ssub_sat(CR2); + }, + [](const APInt &N1, const APInt &N2) { + return N1.ssub_sat(N2); + }); +} + } // anonymous namespace -- 2.50.1