Index: llvm/unittests/IR/ConstantRangeTest.cpp =================================================================== --- llvm/unittests/IR/ConstantRangeTest.cpp +++ llvm/unittests/IR/ConstantRangeTest.cpp @@ -7,6 +7,7 @@ //===----------------------------------------------------------------------===// #include "llvm/ADT/BitVector.h" +#include "llvm/ADT/SmallBitVector.h" #include "llvm/IR/ConstantRange.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/Operator.h" @@ -59,6 +60,137 @@ } } +static unsigned GetRangeSize(const ConstantRange &CR) { + if (CR.isFullSet()) + return 1 << CR.getBitWidth(); + return (CR.getUpper() - CR.getLower()).getZExtValue(); +} + +using FilterFn = llvm::function_ref; + +bool FilterUnsigned(const ConstantRange &CR) { + return !CR.isWrappedSet(); +} + +bool FilterSigned(const ConstantRange &CR) { + return !CR.isSignWrappedSet(); +} + +bool FilterAll(const ConstantRange &) { + return true; +} + +// Check whether constant range CR is an optimal approximation of the set +// Elems if only ranges satisfying RangeFilter are considered. This function +// checks both correctness (all elements in Elems must be in CR) and +// size-optimality (CR must be one of the smallest ranges that both contain +// all Elems and satisfy RangeFilter). +static void TestRange(const ConstantRange &CR, const SmallBitVector &Elems, + FilterFn RangeFilter) { + unsigned BitWidth = CR.getBitWidth(); + + // Check conservative correctness. + for (unsigned Elem : Elems.set_bits()) { + EXPECT_TRUE(CR.contains(APInt(BitWidth, Elem))); + } + + // Make sure we have at least two elements for the code below. + if (Elems.none()) { + EXPECT_TRUE(CR.isEmptySet()); + return; + } + + if (Elems.count() == 1) { + EXPECT_TRUE(CR.isSingleElement()); + return; + } + + // Look at all pairs of adjacent elements and the slack-free ranges + // [Elem, PrevElem] they imply. For ranges allowed by RangeFilter, check if + // CR matches at least one, and find smallest range size. + unsigned SmallestRangeSize = UINT_MAX; + bool FoundMatchingRange = false; + int FirstElem = Elems.find_first(); + int PrevElem = FirstElem, Elem; + do { + Elem = Elems.find_next(PrevElem); + if (Elem < 0) + Elem = FirstElem; // Wrap around to first element. + + ConstantRange PossibleCR = + ConstantRange::getNonEmpty(APInt(BitWidth, Elem), + APInt(BitWidth, PrevElem) + 1); + + // Only consider ranges allowed by the filter function. + if (RangeFilter(PossibleCR)) { + FoundMatchingRange |= PossibleCR == CR; + SmallestRangeSize = std::min(SmallestRangeSize, GetRangeSize(PossibleCR)); + } + + PrevElem = Elem; + } while (Elem != FirstElem); + + // Our range must be the same as one of the possible ranges. + EXPECT_TRUE(FoundMatchingRange); + + // Additionally, it must have the smallest possible size (though there may + // be multipple ranges with the same size). + EXPECT_EQ(SmallestRangeSize, GetRangeSize(CR)); +} + +using UnaryRangeFn = llvm::function_ref; +using UnaryIntFn = llvm::function_ref(const APInt &)>; + +static void TestUnaryOpExhaustive(UnaryRangeFn RangeFn, UnaryIntFn IntFn, + FilterFn RangeFilter = FilterAll) { + unsigned Bits = 4; + EnumerateConstantRanges(Bits, [&](const ConstantRange &CR) { + SmallBitVector Elems(1 << Bits); + ForeachNumInConstantRange(CR, [&](const APInt &N) { + if (Optional ResultN = IntFn(N)) + Elems.set(ResultN->getZExtValue()); + }); + TestRange(RangeFn(CR), Elems, RangeFilter); + }); +} + +using BinaryRangeFn = llvm::function_ref; +using BinaryIntFn = llvm::function_ref(const APInt &, + const APInt &)>; + +static void TestBinaryOpExhaustive(BinaryRangeFn RangeFn, BinaryIntFn IntFn, + FilterFn RangeFilter = FilterAll) { + unsigned Bits = 4; + EnumerateTwoConstantRanges( + Bits, [&](const ConstantRange &CR1, const ConstantRange &CR2) { + SmallBitVector Elems(1 << Bits); + ForeachNumInConstantRange(CR1, [&](const APInt &N1) { + ForeachNumInConstantRange(CR2, [&](const APInt &N2) { + if (Optional ResultN = IntFn(N1, N2)) + Elems.set(ResultN->getZExtValue()); + }); + }); + TestRange(RangeFn(CR1, CR2), Elems, RangeFilter); + }); +} + +static void TestBinaryOpExhaustiveCorrectnessOnly(BinaryRangeFn RangeFn, + BinaryIntFn IntFn) { + unsigned Bits = 4; + EnumerateTwoConstantRanges( + Bits, [&](const ConstantRange &CR1, const ConstantRange &CR2) { + ConstantRange ResultCR = RangeFn(CR1, CR2); + ForeachNumInConstantRange(CR1, [&](const APInt &N1) { + ForeachNumInConstantRange(CR2, [&](const APInt &N2) { + if (Optional ResultN = IntFn(N1, N2)) { + EXPECT_TRUE(ResultCR.contains(*ResultN)); + } + }); + }); + }); +} + struct OpRangeGathererBase { void account(const APInt &N); ConstantRange getRange(); @@ -107,84 +239,6 @@ } }; -template -static void TestUnsignedUnaryOpExhaustive(Fn1 RangeFn, Fn2 IntFn, - bool SkipSignedIntMin = false) { - unsigned Bits = 4; - EnumerateConstantRanges(Bits, [&](const ConstantRange &CR) { - UnsignedOpRangeGatherer R(CR.getBitWidth()); - ForeachNumInConstantRange(CR, [&](const APInt &N) { - if (SkipSignedIntMin && N.isMinSignedValue()) - return; - R.account(IntFn(N)); - }); - - ConstantRange ExactCR = R.getRange(); - ConstantRange ActualCR = RangeFn(CR); - - EXPECT_EQ(ExactCR, ActualCR); - }); -} - -template -static void TestUnsignedBinOpExhaustive(Fn1 RangeFn, Fn2 IntFn, - bool SkipZeroRHS = false, - bool CorrectnessOnly = false) { - unsigned Bits = 4; - EnumerateTwoConstantRanges( - Bits, [&](const ConstantRange &CR1, const ConstantRange &CR2) { - UnsignedOpRangeGatherer R(CR1.getBitWidth()); - ForeachNumInConstantRange(CR1, [&](const APInt &N1) { - ForeachNumInConstantRange(CR2, [&](const APInt &N2) { - if (SkipZeroRHS && N2 == 0) - return; - R.account(IntFn(N1, N2)); - }); - }); - - ConstantRange CR = RangeFn(CR1, CR2); - - ConstantRange Exact = R.getRange(); - - if (!CorrectnessOnly) { - EXPECT_EQ(Exact, CR); - return; - } - - EXPECT_TRUE(CR.contains(Exact)); - if (Exact.isEmptySet()) - EXPECT_TRUE(CR.isEmptySet()); - }); -} - -template -static void TestSignedBinOpExhaustive(Fn1 RangeFn, Fn2 IntFn, - bool SkipZeroRHS = false, - bool CorrectnessOnly = false) { - unsigned Bits = 4; - EnumerateTwoConstantRanges( - Bits, [&](const ConstantRange &CR1, const ConstantRange &CR2) { - SignedOpRangeGatherer R(CR1.getBitWidth()); - ForeachNumInConstantRange(CR1, [&](const APInt &N1) { - ForeachNumInConstantRange(CR2, [&](const APInt &N2) { - if (SkipZeroRHS && N2 == 0) - return; - - R.account(IntFn(N1, N2)); - }); - }); - - ConstantRange CR = RangeFn(CR1, CR2); - - ConstantRange Exact = R.getRange(); - if (CorrectnessOnly) { - EXPECT_TRUE(CR.contains(Exact)); - } else { - EXPECT_EQ(Exact, CR); - } - }); -} - ConstantRange ConstantRangeTest::Full(16, true); ConstantRange ConstantRangeTest::Empty(16, false); ConstantRange ConstantRangeTest::One(APInt(16, 0xa)); @@ -746,6 +800,14 @@ ConstantRange(APInt(16, 0xaae), APInt(16, 0xe))); EXPECT_EQ(One.add(APInt(16, 4)), ConstantRange(APInt(16, 0xe))); + + TestBinaryOpExhaustive( + [](const ConstantRange &CR1, const ConstantRange &CR2) { + return CR1.add(CR2); + }, + [](const APInt &N1, const APInt &N2) { + return N1 + N2; + }); } template @@ -1015,6 +1077,14 @@ ConstantRange(APInt(16, 0xaa6), APInt(16, 0x6))); EXPECT_EQ(One.sub(APInt(16, 4)), ConstantRange(APInt(16, 0x6))); + + TestBinaryOpExhaustive( + [](const ConstantRange &CR1, const ConstantRange &CR2) { + return CR1.sub(CR2); + }, + [](const APInt &N1, const APInt &N2) { + return N1 - N2; + }); } TEST_F(ConstantRangeTest, SubWithNoWrap) { @@ -1282,14 +1352,15 @@ .urem(ConstantRange(APInt(16, 10))), ConstantRange(APInt(16, 0), APInt(16, 10))); - TestUnsignedBinOpExhaustive( + TestBinaryOpExhaustiveCorrectnessOnly( [](const ConstantRange &CR1, const ConstantRange &CR2) { return CR1.urem(CR2); }, - [](const APInt &N1, const APInt &N2) { + [](const APInt &N1, const APInt &N2) -> Optional { + if (N2.isNullValue()) + return None; return N1.urem(N2); - }, - /* SkipZeroRHS */ true, /* CorrectnessOnly */ true); + }); } TEST_F(ConstantRangeTest, SRem) { @@ -1355,14 +1426,15 @@ .srem(ConstantRange(APInt(16, 10))), ConstantRange(APInt(16, 0), APInt(16, 10))); - TestSignedBinOpExhaustive( + TestBinaryOpExhaustiveCorrectnessOnly( [](const ConstantRange &CR1, const ConstantRange &CR2) { return CR1.srem(CR2); }, - [](const APInt &N1, const APInt &N2) { + [](const APInt &N1, const APInt &N2) -> Optional { + if (N2.isNullValue()) + return None; return N1.srem(N2); - }, - /* SkipZeroRHS */ true, /* CorrectnessOnly */ true); + }); } TEST_F(ConstantRangeTest, Shl) { @@ -2277,88 +2349,97 @@ } TEST_F(ConstantRangeTest, UAddSat) { - TestUnsignedBinOpExhaustive( + TestBinaryOpExhaustive( [](const ConstantRange &CR1, const ConstantRange &CR2) { return CR1.uadd_sat(CR2); }, [](const APInt &N1, const APInt &N2) { return N1.uadd_sat(N2); - }); + }, + FilterUnsigned); } TEST_F(ConstantRangeTest, USubSat) { - TestUnsignedBinOpExhaustive( + TestBinaryOpExhaustive( [](const ConstantRange &CR1, const ConstantRange &CR2) { return CR1.usub_sat(CR2); }, [](const APInt &N1, const APInt &N2) { return N1.usub_sat(N2); - }); + }, + FilterUnsigned); } TEST_F(ConstantRangeTest, UMulSat) { - TestUnsignedBinOpExhaustive( + TestBinaryOpExhaustive( [](const ConstantRange &CR1, const ConstantRange &CR2) { return CR1.umul_sat(CR2); }, - [](const APInt &N1, const APInt &N2) { return N1.umul_sat(N2); }); + [](const APInt &N1, const APInt &N2) { return N1.umul_sat(N2); }, + FilterUnsigned); } TEST_F(ConstantRangeTest, UShlSat) { - TestUnsignedBinOpExhaustive( + TestBinaryOpExhaustive( [](const ConstantRange &CR1, const ConstantRange &CR2) { return CR1.ushl_sat(CR2); }, - [](const APInt &N1, const APInt &N2) { return N1.ushl_sat(N2); }); + [](const APInt &N1, const APInt &N2) { return N1.ushl_sat(N2); }, + FilterUnsigned); } TEST_F(ConstantRangeTest, SAddSat) { - TestSignedBinOpExhaustive( + TestBinaryOpExhaustive( [](const ConstantRange &CR1, const ConstantRange &CR2) { return CR1.sadd_sat(CR2); }, [](const APInt &N1, const APInt &N2) { return N1.sadd_sat(N2); - }); + }, + FilterSigned); } TEST_F(ConstantRangeTest, SSubSat) { - TestSignedBinOpExhaustive( + TestBinaryOpExhaustive( [](const ConstantRange &CR1, const ConstantRange &CR2) { return CR1.ssub_sat(CR2); }, [](const APInt &N1, const APInt &N2) { return N1.ssub_sat(N2); - }); + }, + FilterSigned); } TEST_F(ConstantRangeTest, SMulSat) { - TestSignedBinOpExhaustive( + TestBinaryOpExhaustive( [](const ConstantRange &CR1, const ConstantRange &CR2) { return CR1.smul_sat(CR2); }, - [](const APInt &N1, const APInt &N2) { return N1.smul_sat(N2); }); + [](const APInt &N1, const APInt &N2) { return N1.smul_sat(N2); }, + FilterSigned); } TEST_F(ConstantRangeTest, SShlSat) { - TestSignedBinOpExhaustive( + TestBinaryOpExhaustive( [](const ConstantRange &CR1, const ConstantRange &CR2) { return CR1.sshl_sat(CR2); }, - [](const APInt &N1, const APInt &N2) { return N1.sshl_sat(N2); }); + [](const APInt &N1, const APInt &N2) { return N1.sshl_sat(N2); }, + FilterSigned); } TEST_F(ConstantRangeTest, Abs) { - // We're working with unsigned integers here, because it makes the signed - // min case non-wrapping. - TestUnsignedUnaryOpExhaustive( + TestUnaryOpExhaustive( [](const ConstantRange &CR) { return CR.abs(); }, [](const APInt &N) { return N.abs(); }); - TestUnsignedUnaryOpExhaustive( + TestUnaryOpExhaustive( [](const ConstantRange &CR) { return CR.abs(/*IntMinIsPoison=*/true); }, - [](const APInt &N) { return N.abs(); }, - /*SkipSignedIntMin=*/true); + [](const APInt &N) -> Optional { + if (N.isMinSignedValue()) + return None; + return N.abs(); + }); } TEST_F(ConstantRangeTest, castOps) { @@ -2400,21 +2481,25 @@ } TEST_F(ConstantRangeTest, binaryNot) { - TestUnsignedUnaryOpExhaustive( + // TODO: Improve binaryNot() implement to remove the need for FilterUnsigned. + TestUnaryOpExhaustive( [](const ConstantRange &CR) { return CR.binaryNot(); }, - [](const APInt &N) { return ~N; }); - TestUnsignedUnaryOpExhaustive( + [](const APInt &N) { return ~N; }, + FilterUnsigned); + TestUnaryOpExhaustive( [](const ConstantRange &CR) { return CR.binaryXor( ConstantRange(APInt::getAllOnesValue(CR.getBitWidth()))); }, - [](const APInt &N) { return ~N; }); - TestUnsignedUnaryOpExhaustive( + [](const APInt &N) { return ~N; }, + FilterUnsigned); + TestUnaryOpExhaustive( [](const ConstantRange &CR) { return ConstantRange(APInt::getAllOnesValue(CR.getBitWidth())) .binaryXor(CR); }, - [](const APInt &N) { return ~N; }); + [](const APInt &N) { return ~N; }, + FilterUnsigned); } } // anonymous namespace