From 956daf0f7f7fa473cf92c8193905a8a441932b69 Mon Sep 17 00:00:00 2001 From: Nick Lewycky Date: Sun, 12 Jul 2009 05:18:18 +0000 Subject: [PATCH] Implement udiv for ConstantRanges. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@75413 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Support/ConstantRange.cpp | 30 +++++++++++++++++++++---- unittests/Support/ConstantRangeTest.cpp | 22 ++++++++---------- 2 files changed, 35 insertions(+), 17 deletions(-) diff --git a/lib/Support/ConstantRange.cpp b/lib/Support/ConstantRange.cpp index 7fe156835db..04a1b68e072 100644 --- a/lib/Support/ConstantRange.cpp +++ b/lib/Support/ConstantRange.cpp @@ -592,10 +592,32 @@ ConstantRange::umax(const ConstantRange &Other) const { } ConstantRange -ConstantRange::udiv(const ConstantRange &Other) const { - // TODO: Implement udiv. - return ConstantRange(getBitWidth(), - !(isEmptySet() || Other.isEmptySet())); +ConstantRange::udiv(const ConstantRange &RHS) const { + if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax() == 0) + return ConstantRange(getBitWidth(), /*isFullSet=*/false); + if (RHS.isFullSet()) + return ConstantRange(getBitWidth(), /*isFullSet=*/true); + + APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax()); + + APInt RHS_umin = RHS.getUnsignedMin(); + if (RHS_umin == 0) { + // We want the lowest value in RHS excluding zero. Usually that would be 1 + // except for a range in the form of [X, 1) in which case it would be X. + if (RHS.getUpper() == 1) + RHS_umin = RHS.getLower(); + else + RHS_umin = APInt(getBitWidth(), 1); + } + + APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1; + + // If the LHS is Full and the RHS is a wrapped interval containing 1 then + // this could occur. + if (Lower == Upper) + return ConstantRange(getBitWidth(), /*isFullSet=*/true); + + return ConstantRange(Lower, Upper); } /// print - Print out the bounds to a stream... diff --git a/unittests/Support/ConstantRangeTest.cpp b/unittests/Support/ConstantRangeTest.cpp index d11d776970c..891c209f11c 100644 --- a/unittests/Support/ConstantRangeTest.cpp +++ b/unittests/Support/ConstantRangeTest.cpp @@ -319,24 +319,20 @@ TEST_F(ConstantRangeTest, SMax) { TEST_F(ConstantRangeTest, UDiv) { EXPECT_EQ(Full.udiv(Full), Full); EXPECT_EQ(Full.udiv(Empty), Empty); - EXPECT_EQ(Full.udiv(One), Full); - EXPECT_EQ(Full.udiv(Some), Full); + EXPECT_EQ(Full.udiv(One), ConstantRange(APInt(16, 0), + APInt(16, 0xffff / 0xa + 1))); + EXPECT_EQ(Full.udiv(Some), ConstantRange(APInt(16, 0), + APInt(16, 0xffff / 0xa + 1))); EXPECT_EQ(Full.udiv(Wrap), Full); EXPECT_EQ(Empty.udiv(Empty), Empty); EXPECT_EQ(Empty.udiv(One), Empty); EXPECT_EQ(Empty.udiv(Some), Empty); EXPECT_EQ(Empty.udiv(Wrap), Empty); - // TODO: ConstantRange is currently over-conservative here. - EXPECT_EQ(One.udiv(One), Full); - // TODO: ConstantRange is currently over-conservative here. - EXPECT_EQ(One.udiv(Some), Full); - // TODO: ConstantRange is currently over-conservative here. - EXPECT_EQ(One.udiv(Wrap), Full); - // TODO: ConstantRange is currently over-conservative here. - EXPECT_EQ(Some.udiv(Some), Full); - // TODO: ConstantRange is currently over-conservative here. - EXPECT_EQ(Some.udiv(Wrap), Full); - // TODO: ConstantRange is currently over-conservative here. + EXPECT_EQ(One.udiv(One), ConstantRange(APInt(16, 1))); + EXPECT_EQ(One.udiv(Some), ConstantRange(APInt(16, 0), APInt(16, 2))); + EXPECT_EQ(One.udiv(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xb))); + EXPECT_EQ(Some.udiv(Some), ConstantRange(APInt(16, 0), APInt(16, 0x111))); + EXPECT_EQ(Some.udiv(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa))); EXPECT_EQ(Wrap.udiv(Wrap), Full); } -- 2.34.1