From ee9f2ae5b913cf571997091c4d7cac99eccd29a0 Mon Sep 17 00:00:00 2001 From: Nikita Popov Date: Wed, 27 Mar 2019 20:18:51 +0000 Subject: [PATCH] [ConstantRangeTest] Add exhaustive intersectWith() test Add a test that checks the intersectWith() implementation against all 4-bit range pairs. The test uses a more explicit way of calculating the possible intersections, and checks that the right one is picked out according to the smallest set heuristic. This is in preparation for introducing intersectWith() variants that use different heuristics to pick an intersection range, if there are multiple possibilities. llvm-svn: 357119 --- llvm/unittests/IR/ConstantRangeTest.cpp | 215 +++++++++++++++++++++++--------- 1 file changed, 156 insertions(+), 59 deletions(-) diff --git a/llvm/unittests/IR/ConstantRangeTest.cpp b/llvm/unittests/IR/ConstantRangeTest.cpp index 2cde17f..c9273bc 100644 --- a/llvm/unittests/IR/ConstantRangeTest.cpp +++ b/llvm/unittests/IR/ConstantRangeTest.cpp @@ -25,6 +25,30 @@ protected: static ConstantRange Wrap; }; +template +static void EnumerateTwoConstantRanges(unsigned Bits, Fn TestFn) { + unsigned Max = 1 << Bits; + for (unsigned Lo1 = 0; Lo1 < Max; Lo1++) { + for (unsigned Hi1 = 0; Hi1 < Max; Hi1++) { + // Enforce ConstantRange invariant. + if (Lo1 == Hi1 && Lo1 != 0 && Lo1 != Max - 1) + continue; + + ConstantRange CR1(APInt(Bits, Lo1), APInt(Bits, Hi1)); + for (unsigned Lo2 = 0; Lo2 < Max; Lo2++) { + for (unsigned Hi2 = 0; Hi2 < Max; Hi2++) { + // Enforce ConstantRange invariant. + if (Lo2 == Hi2 && Lo2 != 0 && Lo2 != Max - 1) + continue; + + ConstantRange CR2(APInt(Bits, Lo2), APInt(Bits, Hi2)); + TestFn(CR1, CR2); + } + } + } + } +} + ConstantRange ConstantRangeTest::Full(16, true); ConstantRange ConstantRangeTest::Empty(16, false); ConstantRange ConstantRangeTest::One(APInt(16, 0xa)); @@ -329,6 +353,96 @@ TEST_F(ConstantRangeTest, IntersectWith) { EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 15), APInt(32, 0))); } +TEST_F(ConstantRangeTest, IntersectWithExhaustive) { + unsigned Bits = 4; + EnumerateTwoConstantRanges(Bits, + [=](const ConstantRange &CR1, const ConstantRange &CR2) { + // Collect up to three contiguous unsigned ranges. The HaveInterrupt + // variables are used determine when we have to switch to the next + // range because the previous one ended. + APInt Lower1(Bits, 0), Upper1(Bits, 0); + APInt Lower2(Bits, 0), Upper2(Bits, 0); + APInt Lower3(Bits, 0), Upper3(Bits, 0); + bool HaveRange1 = false, HaveInterrupt1 = false; + bool HaveRange2 = false, HaveInterrupt2 = false; + bool HaveRange3 = false, HaveInterrupt3 = false; + + APInt Num(Bits, 0); + for (unsigned I = 0, Limit = 1 << Bits; I < Limit; ++I, ++Num) { + if (!CR1.contains(Num) || !CR2.contains(Num)) { + if (HaveRange3) + HaveInterrupt3 = true; + else if (HaveRange2) + HaveInterrupt2 = true; + else if (HaveRange1) + HaveInterrupt1 = true; + continue; + } + + if (HaveRange3) { + Upper3 = Num; + } else if (HaveInterrupt2) { + HaveRange3 = true; + Lower3 = Upper3 = Num; + } else if (HaveRange2) { + Upper2 = Num; + } else if (HaveInterrupt1) { + HaveRange2 = true; + Lower2 = Upper2 = Num; + } else if (HaveRange1) { + Upper1 = Num; + } else { + HaveRange1 = true; + Lower1 = Upper1 = Num; + } + } + + assert(!HaveInterrupt3 && "Should have at most three ranges"); + + ConstantRange CR = CR1.intersectWith(CR2); + + if (!HaveRange1) { + EXPECT_TRUE(CR.isEmptySet()); + return; + } + + if (!HaveRange2) { + if (Lower1 == Upper1 + 1) { + EXPECT_TRUE(CR.isFullSet()); + } else { + ConstantRange Expected(Lower1, Upper1 + 1); + EXPECT_EQ(Expected, CR); + } + return; + } + + ConstantRange Variant1(Bits, /*full*/ true); + ConstantRange Variant2(Bits, /*full*/ true); + if (!HaveRange3) { + // Compute the two possible ways to cover two disjoint ranges. + if (Lower1 != Upper2 + 1) + Variant1 = ConstantRange(Lower1, Upper2 + 1); + if (Lower2 != Upper1 + 1) + Variant2 = ConstantRange(Lower2, Upper1 + 1); + } else { + // If we have three ranges, the first and last one have to be adjacent + // to the unsigned domain. It's better to think of this as having two + // holes, and we can construct one range using each hole. + assert(Lower1.isNullValue() && Upper3.isMaxValue()); + Variant1 = ConstantRange(Lower2, Upper1 + 1); + Variant2 = ConstantRange(Lower3, Upper2 + 1); + } + + // The intersection should return the smaller of the two variants. + if (Variant1.isSizeStrictlySmallerThan(Variant2)) + EXPECT_EQ(Variant1, CR); + else if (Variant2.isSizeStrictlySmallerThan(Variant1)) + EXPECT_EQ(Variant2, CR); + else + EXPECT_TRUE(Variant1 == CR || Variant2 == CR); + }); +} + TEST_F(ConstantRangeTest, UnionWith) { EXPECT_EQ(Wrap.unionWith(One), ConstantRange(APInt(16, 0xaaa), APInt(16, 0xb))); @@ -1317,69 +1431,52 @@ template static void TestOverflowExhaustive(Fn1 OverflowFn, Fn2 MayOverflowFn) { // Constant range overflow checks are tested exhaustively on 4-bit numbers. unsigned Bits = 4; - unsigned Max = 1 << Bits; - for (unsigned Lo1 = 0; Lo1 < Max; Lo1++) { - for (unsigned Hi1 = 0; Hi1 < Max; Hi1++) { - // Enforce ConstantRange invariant. - if (Lo1 == Hi1 && Lo1 != 0 && Lo1 != Max - 1) - continue; - - ConstantRange CR1(APInt(Bits, Lo1), APInt(Bits, Hi1)); - unsigned Size1 = CR1.getSetSize().getLimitedValue(); - - for (unsigned Lo2 = 0; Lo2 < Max; Lo2++) { - for (unsigned Hi2 = 0; Hi2 < Max; Hi2++) { - // Enforce ConstantRange invariant. - if (Lo2 == Hi2 && Lo2 != 0 && Lo2 != Max - 1) - continue; - - ConstantRange CR2(APInt(Bits, Lo2), APInt(Bits, Hi2)); - unsigned Size2 = CR2.getSetSize().getLimitedValue(); - - // Loop over all N1 in CR1 and N2 in CR2 and check whether any of the - // operations have overflow / have no overflow. These loops are based - // on Size1/Size2 to properly handle empty/full ranges. - bool RangeHasOverflow = false; - bool RangeHasNoOverflow = false; - APInt N1(Bits, Lo1); - for (unsigned I1 = 0; I1 < Size1; ++I1, ++N1) { - APInt N2(Bits, Lo2); - for (unsigned I2 = 0; I2 < Size2; ++I2, ++N2) { - assert(CR1.contains(N1)); - assert(CR2.contains(N2)); - - if (OverflowFn(N1, N2)) - RangeHasOverflow = true; - else - RangeHasNoOverflow = true; - } + EnumerateTwoConstantRanges(Bits, + [=](const ConstantRange &CR1, const ConstantRange &CR2) { + unsigned Size1 = CR1.getSetSize().getLimitedValue(); + unsigned Size2 = CR2.getSetSize().getLimitedValue(); + + // Loop over all N1 in CR1 and N2 in CR2 and check whether any of the + // operations have overflow / have no overflow. These loops are based + // on Size1/Size2 to properly handle empty/full ranges. + bool RangeHasOverflow = false; + bool RangeHasNoOverflow = false; + APInt N1 = CR1.getLower(); + for (unsigned I1 = 0; I1 < Size1; ++I1, ++N1) { + APInt N2 = CR2.getLower(); + for (unsigned I2 = 0; I2 < Size2; ++I2, ++N2) { + assert(CR1.contains(N1)); + assert(CR2.contains(N2)); + + if (OverflowFn(N1, N2)) + RangeHasOverflow = true; + else + RangeHasNoOverflow = true; } + } - ConstantRange::OverflowResult OR = MayOverflowFn(CR1, CR2); - switch (OR) { - case ConstantRange::OverflowResult::AlwaysOverflows: - EXPECT_TRUE(RangeHasOverflow); - EXPECT_FALSE(RangeHasNoOverflow); + ConstantRange::OverflowResult OR = MayOverflowFn(CR1, CR2); + switch (OR) { + case ConstantRange::OverflowResult::AlwaysOverflows: + EXPECT_TRUE(RangeHasOverflow); + EXPECT_FALSE(RangeHasNoOverflow); + break; + case ConstantRange::OverflowResult::NeverOverflows: + EXPECT_FALSE(RangeHasOverflow); + EXPECT_TRUE(RangeHasNoOverflow); + break; + case ConstantRange::OverflowResult::MayOverflow: + // We return MayOverflow for empty sets as a conservative result, + // but of course neither the RangeHasOverflow nor the + // RangeHasNoOverflow flags will be set. + if (CR1.isEmptySet() || CR2.isEmptySet()) break; - case ConstantRange::OverflowResult::NeverOverflows: - EXPECT_FALSE(RangeHasOverflow); - EXPECT_TRUE(RangeHasNoOverflow); - break; - case ConstantRange::OverflowResult::MayOverflow: - // We return MayOverflow for empty sets as a conservative result, - // but of course neither the RangeHasOverflow nor the - // RangeHasNoOverflow flags will be set. - if (CR1.isEmptySet() || CR2.isEmptySet()) - break; - - EXPECT_TRUE(RangeHasOverflow); - EXPECT_TRUE(RangeHasNoOverflow); - break; - } + + EXPECT_TRUE(RangeHasOverflow); + EXPECT_TRUE(RangeHasNoOverflow); + break; } - } - } - } + }); } TEST_F(ConstantRangeTest, UnsignedAddOverflowExhautive) { -- 2.7.4