From ef2d9799435807d0b4143ff4975336842c7eab0b Mon Sep 17 00:00:00 2001 From: Nikita Popov Date: Sun, 17 Mar 2019 20:24:02 +0000 Subject: [PATCH] [ConstantRange] Add fromKnownBits() method Following the suggestion in D59450, I'm moving the code for constructing a ConstantRange from KnownBits out of ValueTracking, which also allows us to test this code independently. I'm adding this method to ConstantRange rather than KnownBits (which would have been a bit nicer API wise) to avoid creating a dependency from Support to IR, where ConstantRange lives. Differential Revision: https://reviews.llvm.org/D59475 llvm-svn: 356339 --- llvm/include/llvm/IR/ConstantRange.h | 6 +++ llvm/lib/Analysis/ValueTracking.cpp | 19 ++++------ llvm/lib/IR/ConstantRange.cpp | 19 ++++++++++ llvm/unittests/IR/ConstantRangeTest.cpp | 65 +++++++++++++++++++++++++++++++++ 4 files changed, 98 insertions(+), 11 deletions(-) diff --git a/llvm/include/llvm/IR/ConstantRange.h b/llvm/include/llvm/IR/ConstantRange.h index 456df52..2356b70 100644 --- a/llvm/include/llvm/IR/ConstantRange.h +++ b/llvm/include/llvm/IR/ConstantRange.h @@ -41,6 +41,7 @@ namespace llvm { class MDNode; class raw_ostream; +struct KnownBits; /// This class represents a range of values. class LLVM_NODISCARD ConstantRange { @@ -58,6 +59,11 @@ public: /// assert out if the two APInt's are not the same bit width. ConstantRange(APInt Lower, APInt Upper); + /// Initialize a range based on a known bits constraint. The IsSigned flag + /// indicates whether the constant range should not wrap in the signed or + /// unsigned domain. + static ConstantRange fromKnownBits(const KnownBits &Known, bool IsSigned); + /// Produce the smallest range such that all values that may satisfy the given /// predicate with any value contained within Other is contained in the /// returned range. Formally, this returns a superset of diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp index 9a87667..f0c02ee 100644 --- a/llvm/lib/Analysis/ValueTracking.cpp +++ b/llvm/lib/Analysis/ValueTracking.cpp @@ -4077,13 +4077,6 @@ static OverflowResult mapOverflowResult(ConstantRange::OverflowResult OR) { llvm_unreachable("Unknown OverflowResult"); } -static ConstantRange constantRangeFromKnownBits(const KnownBits &Known) { - if (Known.isUnknown()) - return ConstantRange(Known.getBitWidth(), /* full */ true); - - return ConstantRange(Known.One, ~Known.Zero + 1); -} - OverflowResult llvm::computeOverflowForUnsignedAdd( const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, @@ -4092,8 +4085,10 @@ OverflowResult llvm::computeOverflowForUnsignedAdd( nullptr, UseInstrInfo); KnownBits RHSKnown = computeKnownBits(RHS, DL, /*Depth=*/0, AC, CxtI, DT, nullptr, UseInstrInfo); - ConstantRange LHSRange = constantRangeFromKnownBits(LHSKnown); - ConstantRange RHSRange = constantRangeFromKnownBits(RHSKnown); + ConstantRange LHSRange = + ConstantRange::fromKnownBits(LHSKnown, /*signed*/ false); + ConstantRange RHSRange = + ConstantRange::fromKnownBits(RHSKnown, /*signed*/ false); return mapOverflowResult(LHSRange.unsignedAddMayOverflow(RHSRange)); } @@ -4208,8 +4203,10 @@ OverflowResult llvm::computeOverflowForUnsignedSub(const Value *LHS, const DominatorTree *DT) { KnownBits LHSKnown = computeKnownBits(LHS, DL, /*Depth=*/0, AC, CxtI, DT); KnownBits RHSKnown = computeKnownBits(RHS, DL, /*Depth=*/0, AC, CxtI, DT); - ConstantRange LHSRange = constantRangeFromKnownBits(LHSKnown); - ConstantRange RHSRange = constantRangeFromKnownBits(RHSKnown); + ConstantRange LHSRange = + ConstantRange::fromKnownBits(LHSKnown, /*signed*/ false); + ConstantRange RHSRange = + ConstantRange::fromKnownBits(RHSKnown, /*signed*/ false); return mapOverflowResult(LHSRange.unsignedSubMayOverflow(RHSRange)); } diff --git a/llvm/lib/IR/ConstantRange.cpp b/llvm/lib/IR/ConstantRange.cpp index 23737bb..d41914b 100644 --- a/llvm/lib/IR/ConstantRange.cpp +++ b/llvm/lib/IR/ConstantRange.cpp @@ -31,6 +31,7 @@ #include "llvm/Support/Compiler.h" #include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/KnownBits.h" #include "llvm/Support/raw_ostream.h" #include #include @@ -53,6 +54,24 @@ ConstantRange::ConstantRange(APInt L, APInt U) "Lower == Upper, but they aren't min or max value!"); } +ConstantRange ConstantRange::fromKnownBits(const KnownBits &Known, + bool IsSigned) { + if (Known.isUnknown()) + return ConstantRange(Known.getBitWidth(), /* full */ true); + + // For unsigned ranges, or signed ranges with known sign bit, create a simple + // range between the smallest and largest possible value. + if (!IsSigned || Known.isNegative() || Known.isNonNegative()) + return ConstantRange(Known.One, ~Known.Zero + 1); + + // If we don't know the sign bit, pick the lower bound as a negative number + // and the upper bound as a non-negative one. + APInt Lower = Known.One, Upper = ~Known.Zero; + Lower.setSignBit(); + Upper.clearSignBit(); + return ConstantRange(Lower, Upper + 1); +} + ConstantRange ConstantRange::makeAllowedICmpRegion(CmpInst::Predicate Pred, const ConstantRange &CR) { if (CR.isEmptySet()) diff --git a/llvm/unittests/IR/ConstantRangeTest.cpp b/llvm/unittests/IR/ConstantRangeTest.cpp index 393a810..2469d86 100644 --- a/llvm/unittests/IR/ConstantRangeTest.cpp +++ b/llvm/unittests/IR/ConstantRangeTest.cpp @@ -9,6 +9,7 @@ #include "llvm/IR/ConstantRange.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/Operator.h" +#include "llvm/Support/KnownBits.h" #include "gtest/gtest.h" using namespace llvm; @@ -1406,4 +1407,68 @@ TEST_F(ConstantRangeTest, SignedSubOverflowExhautive) { }); } +TEST_F(ConstantRangeTest, FromKnownBits) { + KnownBits Unknown(16); + EXPECT_EQ(Full, ConstantRange::fromKnownBits(Unknown, /*signed*/false)); + EXPECT_EQ(Full, ConstantRange::fromKnownBits(Unknown, /*signed*/true)); + + // .10..01. -> unsigned 01000010 (66) to 11011011 (219) + // -> signed 11000010 (194) to 01011011 (91) + KnownBits Known(8); + Known.Zero = 36; + Known.One = 66; + ConstantRange Unsigned(APInt(8, 66), APInt(8, 219 + 1)); + ConstantRange Signed(APInt(8, 194), APInt(8, 91 + 1)); + EXPECT_EQ(Unsigned, ConstantRange::fromKnownBits(Known, /*signed*/false)); + EXPECT_EQ(Signed, ConstantRange::fromKnownBits(Known, /*signed*/true)); + + // 1.10.10. -> 10100100 (164) to 11101101 (237) + Known.Zero = 18; + Known.One = 164; + ConstantRange CR1(APInt(8, 164), APInt(8, 237 + 1)); + EXPECT_EQ(CR1, ConstantRange::fromKnownBits(Known, /*signed*/false)); + EXPECT_EQ(CR1, ConstantRange::fromKnownBits(Known, /*signed*/true)); + + // 01.0.1.0 -> 01000100 (68) to 01101110 (110) + Known.Zero = 145; + Known.One = 68; + ConstantRange CR2(APInt(8, 68), APInt(8, 110 + 1)); + EXPECT_EQ(CR2, ConstantRange::fromKnownBits(Known, /*signed*/false)); + EXPECT_EQ(CR2, ConstantRange::fromKnownBits(Known, /*signed*/true)); +} + +TEST_F(ConstantRangeTest, FromKnownBitsExhaustive) { + unsigned Bits = 4; + unsigned Max = 1 << Bits; + KnownBits Known(Bits); + for (unsigned Zero = 0; Zero < Max; ++Zero) { + for (unsigned One = 0; One < Max; ++One) { + Known.Zero = Zero; + Known.One = One; + if (Known.hasConflict() || Known.isUnknown()) + continue; + + APInt MinUnsigned = APInt::getMaxValue(Bits); + APInt MaxUnsigned = APInt::getMinValue(Bits); + APInt MinSigned = APInt::getSignedMaxValue(Bits); + APInt MaxSigned = APInt::getSignedMinValue(Bits); + for (unsigned N = 0; N < Max; ++N) { + APInt Num(Bits, N); + if ((Num & Known.Zero) != 0 || (~Num & Known.One) != 0) + continue; + + if (Num.ult(MinUnsigned)) MinUnsigned = Num; + if (Num.ugt(MaxUnsigned)) MaxUnsigned = Num; + if (Num.slt(MinSigned)) MinSigned = Num; + if (Num.sgt(MaxSigned)) MaxSigned = Num; + } + + ConstantRange UnsignedCR(MinUnsigned, MaxUnsigned + 1); + ConstantRange SignedCR(MinSigned, MaxSigned + 1); + EXPECT_EQ(UnsignedCR, ConstantRange::fromKnownBits(Known, false)); + EXPECT_EQ(SignedCR, ConstantRange::fromKnownBits(Known, true)); + } + } +} + } // anonymous namespace -- 2.7.4