Index: llvm/trunk/include/llvm/IR/ConstantRange.h =================================================================== --- llvm/trunk/include/llvm/IR/ConstantRange.h +++ llvm/trunk/include/llvm/IR/ConstantRange.h @@ -33,6 +33,7 @@ #define LLVM_IR_CONSTANTRANGE_H #include "llvm/ADT/APInt.h" +#include "llvm/IR/InstrTypes.h" #include "llvm/Support/DataTypes.h" namespace llvm { @@ -59,15 +60,27 @@ /// assert out if the two APInt's are not the same bit width. ConstantRange(APIntMoveTy Lower, APIntMoveTy Upper); - /// Produce the smallest range that contains all values that - /// might satisfy the comparison specified by Pred when compared to any value - /// contained within Other. - /// - /// Solves for range X in 'for all x in X, there exists a y in Y such that - /// icmp op x, y is true'. Every value that might make the comparison true - /// is included in the resulting range. - static ConstantRange makeICmpRegion(unsigned Pred, - const ConstantRange &Other); + /// 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 + /// 'union over all y in Other . { x : icmp op x y is true }'. If the exact + /// answer is not representable as a ConstantRange, the return value will be a + /// proper superset of the above. + /// + /// Example: Pred = ult and Other = i8 [2, 5) returns Result = [0, 4) + static ConstantRange makeAllowedICmpRegion(CmpInst::Predicate Pred, + const ConstantRange &Other); + + /// Produce the largest range such that all values in the returned range + /// satisfy the given predicate with all values contained within Other. + /// Formally, this returns a subset of + /// 'intersection over all y in Other . { x : icmp op x y is true }'. If the + /// exact answer is not representable as a ConstantRange, the return value + /// will be a proper subset of the above. + /// + /// Example: Pred = ult and Other = i8 [2, 5) returns [0, 2) + static ConstantRange makeSatisfyingICmpRegion(CmpInst::Predicate Pred, + const ConstantRange &Other); /// Return the lower value for this range. /// Index: llvm/trunk/lib/Analysis/LazyValueInfo.cpp =================================================================== --- llvm/trunk/lib/Analysis/LazyValueInfo.cpp +++ llvm/trunk/lib/Analysis/LazyValueInfo.cpp @@ -854,10 +854,10 @@ ConstantInt *CI = dyn_cast(ICI->getOperand(1)); if (CI && (ICI->getOperand(0) == Val || NegOffset)) { - // Calculate the range of values that would satisfy the comparison. + // Calculate the range of values that are allowed by the comparison ConstantRange CmpRange(CI->getValue()); ConstantRange TrueValues = - ConstantRange::makeICmpRegion(ICI->getPredicate(), CmpRange); + ConstantRange::makeAllowedICmpRegion(ICI->getPredicate(), CmpRange); if (NegOffset) // Apply the offset from above. TrueValues = TrueValues.subtract(NegOffset->getValue()); Index: llvm/trunk/lib/IR/ConstantRange.cpp =================================================================== --- llvm/trunk/lib/IR/ConstantRange.cpp +++ llvm/trunk/lib/IR/ConstantRange.cpp @@ -49,14 +49,15 @@ "Lower == Upper, but they aren't min or max value!"); } -ConstantRange ConstantRange::makeICmpRegion(unsigned Pred, - const ConstantRange &CR) { +ConstantRange ConstantRange::makeAllowedICmpRegion(CmpInst::Predicate Pred, + const ConstantRange &CR) { if (CR.isEmptySet()) return CR; uint32_t W = CR.getBitWidth(); switch (Pred) { - default: llvm_unreachable("Invalid ICmp predicate to makeICmpRegion()"); + default: + llvm_unreachable("Invalid ICmp predicate to makeAllowedICmpRegion()"); case CmpInst::ICMP_EQ: return CR; case CmpInst::ICMP_NE: @@ -114,6 +115,16 @@ } } +ConstantRange ConstantRange::makeSatisfyingICmpRegion(CmpInst::Predicate Pred, + const ConstantRange &CR) { + // Follows from De-Morgan's laws: + // + // ~(~A union ~B) == A intersect B. + // + return makeAllowedICmpRegion(CmpInst::getInversePredicate(Pred), CR) + .inverse(); +} + /// isFullSet - Return true if this set contains all of the elements possible /// for this data-type bool ConstantRange::isFullSet() const { Index: llvm/trunk/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp =================================================================== --- llvm/trunk/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp +++ llvm/trunk/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp @@ -979,9 +979,9 @@ // Make a constant range that's the intersection of the two icmp ranges. // If the intersection is empty, we know that the result is false. ConstantRange LHSRange = - ConstantRange::makeICmpRegion(LHSCC, LHSCst->getValue()); + ConstantRange::makeAllowedICmpRegion(LHSCC, LHSCst->getValue()); ConstantRange RHSRange = - ConstantRange::makeICmpRegion(RHSCC, RHSCst->getValue()); + ConstantRange::makeAllowedICmpRegion(RHSCC, RHSCst->getValue()); if (LHSRange.intersectWith(RHSRange).isEmptySet()) return ConstantInt::get(CmpInst::makeCmpResultType(LHS->getType()), 0); Index: llvm/trunk/lib/Transforms/Utils/SimplifyCFG.cpp =================================================================== --- llvm/trunk/lib/Transforms/Utils/SimplifyCFG.cpp +++ llvm/trunk/lib/Transforms/Utils/SimplifyCFG.cpp @@ -421,8 +421,8 @@ } // If we have "x ult 3", for example, then we can add 0,1,2 to the set. - ConstantRange Span = ConstantRange::makeICmpRegion(ICI->getPredicate(), - C->getValue()); + ConstantRange Span = ConstantRange::makeAllowedICmpRegion( + ICI->getPredicate(), C->getValue()); // Shift the range if the compare is fed by an add. This is the range // compare idiom as emitted by instcombine. Index: llvm/trunk/unittests/IR/ConstantRangeTest.cpp =================================================================== --- llvm/trunk/unittests/IR/ConstantRangeTest.cpp +++ llvm/trunk/unittests/IR/ConstantRangeTest.cpp @@ -509,11 +509,63 @@ EXPECT_EQ(Wrap.lshr(Wrap), Full); } -TEST(ConstantRange, MakeICmpRegion) { +TEST(ConstantRange, MakeAllowedICmpRegion) { // PR8250 ConstantRange SMax = ConstantRange(APInt::getSignedMaxValue(32)); - EXPECT_TRUE(ConstantRange::makeICmpRegion(ICmpInst::ICMP_SGT, - SMax).isEmptySet()); + EXPECT_TRUE(ConstantRange::makeAllowedICmpRegion(ICmpInst::ICMP_SGT, SMax) + .isEmptySet()); +} + +TEST(ConstantRange, MakeSatisfyingICmpRegion) { + ConstantRange LowHalf(APInt(8, 0), APInt(8, 128)); + ConstantRange HighHalf(APInt(8, 128), APInt(8, 0)); + ConstantRange EmptySet(8, /* isFullSet = */ false); + + EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_NE, LowHalf), + HighHalf); + + EXPECT_EQ( + ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_NE, HighHalf), + LowHalf); + + EXPECT_TRUE(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_EQ, + HighHalf).isEmptySet()); + + ConstantRange UnsignedSample(APInt(8, 5), APInt(8, 200)); + + EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_ULT, + UnsignedSample), + ConstantRange(APInt(8, 0), APInt(8, 5))); + + EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_ULE, + UnsignedSample), + ConstantRange(APInt(8, 0), APInt(8, 6))); + + EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_UGT, + UnsignedSample), + ConstantRange(APInt(8, 200), APInt(8, 0))); + + EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_UGE, + UnsignedSample), + ConstantRange(APInt(8, 199), APInt(8, 0))); + + ConstantRange SignedSample(APInt(8, -5), APInt(8, 5)); + + EXPECT_EQ( + ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SLT, SignedSample), + ConstantRange(APInt(8, -128), APInt(8, -5))); + + EXPECT_EQ( + ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SLE, SignedSample), + ConstantRange(APInt(8, -128), APInt(8, -4))); + + EXPECT_EQ( + ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SGT, SignedSample), + ConstantRange(APInt(8, 5), APInt(8, -128))); + + EXPECT_EQ( + ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SGE, SignedSample), + ConstantRange(APInt(8, 4), APInt(8, -128))); } } // anonymous namespace