Index: llvm/trunk/include/llvm/IR/ConstantRange.h =================================================================== --- llvm/trunk/include/llvm/IR/ConstantRange.h +++ llvm/trunk/include/llvm/IR/ConstantRange.h @@ -365,6 +365,13 @@ ConstantRange udiv(const ConstantRange &Other) const; /// Return a new range representing the possible values resulting + /// from a signed division of a value in this range and a value in + /// \p Other. Division by zero and division of SignedMin by -1 are considered + /// undefined behavior, in line with IR, and do not contribute towards the + /// result. + ConstantRange sdiv(const ConstantRange &Other) const; + + /// Return a new range representing the possible values resulting /// from an unsigned remainder operation of a value in this range and a /// value in \p Other. ConstantRange urem(const ConstantRange &Other) const; Index: llvm/trunk/lib/IR/ConstantRange.cpp =================================================================== --- llvm/trunk/lib/IR/ConstantRange.cpp +++ llvm/trunk/lib/IR/ConstantRange.cpp @@ -765,6 +765,8 @@ return multiply(Other); case Instruction::UDiv: return udiv(Other); + case Instruction::SDiv: + return sdiv(Other); case Instruction::URem: return urem(Other); case Instruction::SRem: @@ -962,6 +964,91 @@ return getNonEmpty(std::move(Lower), std::move(Upper)); } +ConstantRange ConstantRange::sdiv(const ConstantRange &RHS) const { + // We split up the LHS and RHS into positive and negative components + // and then also compute the positive and negative components of the result + // separately by combining division results with the appropriate signs. + APInt Zero = APInt::getNullValue(getBitWidth()); + APInt SignedMin = APInt::getSignedMinValue(getBitWidth()); + ConstantRange PosFilter(APInt(getBitWidth(), 1), SignedMin); + ConstantRange NegFilter(SignedMin, Zero); + ConstantRange PosL = intersectWith(PosFilter); + ConstantRange NegL = intersectWith(NegFilter); + ConstantRange PosR = RHS.intersectWith(PosFilter); + ConstantRange NegR = RHS.intersectWith(NegFilter); + + ConstantRange PosRes = getEmpty(); + if (!PosL.isEmptySet() && !PosR.isEmptySet()) + // pos / pos = pos. + PosRes = ConstantRange(PosL.Lower.sdiv(PosR.Upper - 1), + (PosL.Upper - 1).sdiv(PosR.Lower) + 1); + + if (!NegL.isEmptySet() && !NegR.isEmptySet()) { + // neg / neg = pos. + // + // We need to deal with one tricky case here: SignedMin / -1 is UB on the + // IR level, so we'll want to exclude this case when calculating bounds. + // (For APInts the operation is well-defined and yields SignedMin.) We + // handle this by dropping either SignedMin from the LHS or -1 from the RHS. + APInt Lo = (NegL.Upper - 1).sdiv(NegR.Lower); + if (NegL.Lower.isMinSignedValue() && NegR.Upper.isNullValue()) { + // Remove -1 from the LHS. Skip if it's the only element, as this would + // leave us with an empty set. + if (!NegR.Lower.isAllOnesValue()) { + APInt AdjNegRUpper; + if (RHS.Lower.isAllOnesValue()) + // Negative part of [-1, X] without -1 is [SignedMin, X]. + AdjNegRUpper = RHS.Upper; + else + // [X, -1] without -1 is [X, -2]. + AdjNegRUpper = NegR.Upper - 1; + + PosRes = PosRes.unionWith( + ConstantRange(Lo, NegL.Lower.sdiv(AdjNegRUpper - 1) + 1)); + } + + // Remove SignedMin from the RHS. Skip if it's the only element, as this + // would leave us with an empty set. + if (NegL.Upper != SignedMin + 1) { + APInt AdjNegLLower; + if (Upper == SignedMin + 1) + // Negative part of [X, SignedMin] without SignedMin is [X, -1]. + AdjNegLLower = Lower; + else + // [SignedMin, X] without SignedMin is [SignedMin + 1, X]. + AdjNegLLower = NegL.Lower + 1; + + PosRes = PosRes.unionWith( + ConstantRange(std::move(Lo), + AdjNegLLower.sdiv(NegR.Upper - 1) + 1)); + } + } else { + PosRes = PosRes.unionWith( + ConstantRange(std::move(Lo), NegL.Lower.sdiv(NegR.Upper - 1) + 1)); + } + } + + ConstantRange NegRes = getEmpty(); + if (!PosL.isEmptySet() && !NegR.isEmptySet()) + // pos / neg = neg. + NegRes = ConstantRange((PosL.Upper - 1).sdiv(NegR.Upper - 1), + PosL.Lower.sdiv(NegR.Lower) + 1); + + if (!NegL.isEmptySet() && !PosR.isEmptySet()) + // neg / pos = neg. + NegRes = NegRes.unionWith( + ConstantRange(NegL.Lower.sdiv(PosR.Lower), + (NegL.Upper - 1).sdiv(PosR.Upper - 1) + 1)); + + // Prefer a non-wrapping signed range here. + ConstantRange Res = NegRes.unionWith(PosRes, PreferredRangeType::Signed); + + // Preserve the zero that we dropped when splitting the LHS by sign. + if (contains(Zero) && (!PosR.isEmptySet() || !NegR.isEmptySet())) + Res = Res.unionWith(ConstantRange(Zero)); + return Res; +} + ConstantRange ConstantRange::urem(const ConstantRange &RHS) const { if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isNullValue()) return getEmpty(); Index: llvm/trunk/unittests/IR/ConstantRangeTest.cpp =================================================================== --- llvm/trunk/unittests/IR/ConstantRangeTest.cpp +++ llvm/trunk/unittests/IR/ConstantRangeTest.cpp @@ -6,6 +6,7 @@ // //===----------------------------------------------------------------------===// +#include "llvm/ADT/BitVector.h" #include "llvm/IR/ConstantRange.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/Operator.h" @@ -844,6 +845,63 @@ ConstantRange(APInt(16, 0), APInt(16, 99))); } +TEST_F(ConstantRangeTest, SDiv) { + unsigned Bits = 4; + EnumerateTwoConstantRanges(Bits, [&](const ConstantRange &CR1, + const ConstantRange &CR2) { + // Collect possible results in a bit vector. We store the signed value plus + // a bias to make it unsigned. + int Bias = 1 << (Bits - 1); + BitVector Results(1 << Bits); + ForeachNumInConstantRange(CR1, [&](const APInt &N1) { + ForeachNumInConstantRange(CR2, [&](const APInt &N2) { + // Division by zero is UB. + if (N2 == 0) + return; + + // SignedMin / -1 is UB. + if (N1.isMinSignedValue() && N2.isAllOnesValue()) + return; + + APInt N = N1.sdiv(N2); + Results.set(N.getSExtValue() + Bias); + }); + }); + + ConstantRange CR = CR1.sdiv(CR2); + if (Results.none()) { + EXPECT_TRUE(CR.isEmptySet()); + return; + } + + // If there is a non-full signed envelope, that should be the result. + APInt SMin(Bits, Results.find_first() - Bias); + APInt SMax(Bits, Results.find_last() - Bias); + ConstantRange Envelope = ConstantRange::getNonEmpty(SMin, SMax + 1); + if (!Envelope.isFullSet()) { + EXPECT_EQ(Envelope, CR); + return; + } + + // If the signed envelope is a full set, try to find a smaller sign wrapped + // set that is separated in negative and positive components (or one which + // can also additionally contain zero). + int LastNeg = Results.find_last_in(0, Bias) - Bias; + int LastPos = Results.find_next(Bias) - Bias; + if (Results[Bias]) { + if (LastNeg == -1) + ++LastNeg; + else if (LastPos == 1) + --LastPos; + } + + APInt WMax(Bits, LastNeg); + APInt WMin(Bits, LastPos); + ConstantRange Wrapped = ConstantRange::getNonEmpty(WMin, WMax + 1); + EXPECT_EQ(Wrapped, CR); + }); +} + TEST_F(ConstantRangeTest, URem) { EXPECT_EQ(Full.urem(Empty), Empty); EXPECT_EQ(Empty.urem(Full), Empty);