From e2e04eaba9e2b701fc7efce2f563988e572e3cc1 Mon Sep 17 00:00:00 2001 From: Nikita Popov Date: Tue, 23 Apr 2019 18:00:17 +0000 Subject: [PATCH] [ConstantRange] Add urem support Add urem support to ConstantRange, so we can handle in in LVI. This is an approximate implementation that tries to capture the most useful conditions: If the LHS is always strictly smaller than the RHS, then the urem is a no-op and the result is the same as the LHS range. Otherwise the lower bound is zero and the upper bound is min(LHSMax, RHSMax - 1). Differential Revision: https://reviews.llvm.org/D60952 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@359019 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/IR/ConstantRange.h | 5 +++ lib/IR/ConstantRange.cpp | 15 ++++++++ unittests/IR/ConstantRangeTest.cpp | 62 ++++++++++++++++++++++++++---- 3 files changed, 74 insertions(+), 8 deletions(-) diff --git a/include/llvm/IR/ConstantRange.h b/include/llvm/IR/ConstantRange.h index f006a9321fc..5ea3b639d93 100644 --- a/include/llvm/IR/ConstantRange.h +++ b/include/llvm/IR/ConstantRange.h @@ -356,6 +356,11 @@ public: /// \p Other. ConstantRange udiv(const ConstantRange &Other) const; + /// Return a new range representing the possible values resulting + /// from an unsigned remainder operation of a value in this range and a + /// value in \p Other. + ConstantRange urem(const ConstantRange &Other) const; + /// Return a new range representing the possible values resulting /// from a binary-and of a value in this range by a value in \p Other. ConstantRange binaryAnd(const ConstantRange &Other) const; diff --git a/lib/IR/ConstantRange.cpp b/lib/IR/ConstantRange.cpp index b2bdd0abd9c..7e2c6727703 100644 --- a/lib/IR/ConstantRange.cpp +++ b/lib/IR/ConstantRange.cpp @@ -794,6 +794,8 @@ ConstantRange ConstantRange::binaryOp(Instruction::BinaryOps BinOp, return multiply(Other); case Instruction::UDiv: return udiv(Other); + case Instruction::URem: + return urem(Other); case Instruction::Shl: return shl(Other); case Instruction::LShr: @@ -991,6 +993,19 @@ ConstantRange::udiv(const ConstantRange &RHS) const { return getNonEmpty(std::move(Lower), std::move(Upper)); } +ConstantRange ConstantRange::urem(const ConstantRange &RHS) const { + if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isNullValue()) + return getEmpty(); + + // L % R for L < R is L. + if (getUnsignedMax().ult(RHS.getUnsignedMin())) + return *this; + + // L % R is <= L and < R. + APInt Upper = APIntOps::umin(getUnsignedMax(), RHS.getUnsignedMax() - 1) + 1; + return getNonEmpty(APInt::getNullValue(getBitWidth()), std::move(Upper)); +} + ConstantRange ConstantRange::binaryAnd(const ConstantRange &Other) const { if (isEmptySet() || Other.isEmptySet()) diff --git a/unittests/IR/ConstantRangeTest.cpp b/unittests/IR/ConstantRangeTest.cpp index 8e378ff3c75..692d151778e 100644 --- a/unittests/IR/ConstantRangeTest.cpp +++ b/unittests/IR/ConstantRangeTest.cpp @@ -59,20 +59,19 @@ static void ForeachNumInConstantRange(const ConstantRange &CR, Fn TestFn) { } template -static void TestUnsignedBinOpExhaustive(Fn1 RangeFn, Fn2 IntFn) { +static void TestUnsignedBinOpExhaustive( + Fn1 RangeFn, Fn2 IntFn, + bool SkipZeroRHS = false, bool CorrectnessOnly = false) { 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) { + if (SkipZeroRHS && N2 == 0) + return; + APInt N = IntFn(N1, N2); if (N.ult(Min)) Min = N; @@ -81,7 +80,18 @@ static void TestUnsignedBinOpExhaustive(Fn1 RangeFn, Fn2 IntFn) { }); }); - EXPECT_EQ(ConstantRange::getNonEmpty(Min, Max + 1), CR); + ConstantRange CR = RangeFn(CR1, CR2); + if (Min.ugt(Max)) { + EXPECT_TRUE(CR.isEmptySet()); + return; + } + + ConstantRange Exact = ConstantRange::getNonEmpty(Min, Max + 1); + if (CorrectnessOnly) { + EXPECT_TRUE(CR.contains(Exact)); + } else { + EXPECT_EQ(Exact, CR); + } }); } @@ -813,6 +823,42 @@ TEST_F(ConstantRangeTest, UDiv) { EXPECT_EQ(Wrap.udiv(Wrap), Full); } +TEST_F(ConstantRangeTest, URem) { + EXPECT_EQ(Full.urem(Empty), Empty); + EXPECT_EQ(Empty.urem(Full), Empty); + // urem by zero is poison. + EXPECT_EQ(Full.urem(ConstantRange(APInt(16, 0))), Empty); + // urem by full range doesn't contain MaxValue. + EXPECT_EQ(Full.urem(Full), ConstantRange(APInt(16, 0), APInt(16, 0xffff))); + // urem is upper bounded by maximum RHS minus one. + EXPECT_EQ(Full.urem(ConstantRange(APInt(16, 0), APInt(16, 123))), + ConstantRange(APInt(16, 0), APInt(16, 122))); + // urem is upper bounded by maximum LHS. + EXPECT_EQ(ConstantRange(APInt(16, 0), APInt(16, 123)).urem(Full), + ConstantRange(APInt(16, 0), APInt(16, 123))); + // If the LHS is always lower than the RHS, the result is the LHS. + EXPECT_EQ(ConstantRange(APInt(16, 10), APInt(16, 20)) + .urem(ConstantRange(APInt(16, 20), APInt(16, 30))), + ConstantRange(APInt(16, 10), APInt(16, 20))); + // It has to be strictly lower, otherwise the top value may wrap to zero. + EXPECT_EQ(ConstantRange(APInt(16, 10), APInt(16, 20)) + .urem(ConstantRange(APInt(16, 19), APInt(16, 30))), + ConstantRange(APInt(16, 0), APInt(16, 20))); + // [12, 14] % 10 is [2, 4], but we conservatively compute [0, 9]. + EXPECT_EQ(ConstantRange(APInt(16, 12), APInt(16, 15)) + .urem(ConstantRange(APInt(16, 10))), + ConstantRange(APInt(16, 0), APInt(16, 10))); + + TestUnsignedBinOpExhaustive( + [](const ConstantRange &CR1, const ConstantRange &CR2) { + return CR1.urem(CR2); + }, + [](const APInt &N1, const APInt &N2) { + return N1.urem(N2); + }, + /* SkipZeroRHS */ true, /* CorrectnessOnly */ true); +} + TEST_F(ConstantRangeTest, Shl) { ConstantRange Some2(APInt(16, 0xfff), APInt(16, 0x8000)); ConstantRange WrapNullMax(APInt(16, 0x1), APInt(16, 0x0)); -- 2.50.1