From 6729b6de1f5b753251b4f31fd6349912d07d34ef Mon Sep 17 00:00:00 2001 From: Simon Pilgrim Date: Thu, 5 Nov 2020 14:55:42 +0000 Subject: [PATCH] [KnownBits] Move ValueTracking SREM KnownBits handling to KnownBits::srem. NFCI. Move the ValueTracking implementation to KnownBits, the SelectionDAG version is more limited so I'm intending to replace that as a separate commit. --- llvm/include/llvm/Support/KnownBits.h | 3 +++ llvm/lib/Analysis/ValueTracking.cpp | 36 ++++---------------------------- llvm/lib/Support/KnownBits.cpp | 30 ++++++++++++++++++++++++++ llvm/unittests/Support/KnownBitsTest.cpp | 9 ++++++++ 4 files changed, 46 insertions(+), 32 deletions(-) diff --git a/llvm/include/llvm/Support/KnownBits.h b/llvm/include/llvm/Support/KnownBits.h index 2ef4a8f..de1c0cd 100644 --- a/llvm/include/llvm/Support/KnownBits.h +++ b/llvm/include/llvm/Support/KnownBits.h @@ -264,6 +264,9 @@ public: /// Compute known bits for urem(LHS, RHS). static KnownBits urem(const KnownBits &LHS, const KnownBits &RHS); + /// Compute known bits for srem(LHS, RHS). + static KnownBits srem(const KnownBits &LHS, const KnownBits &RHS); + /// Compute known bits for umax(LHS, RHS). static KnownBits umax(const KnownBits &LHS, const KnownBits &RHS); diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp index 632a5ea..44cf4f8 100644 --- a/llvm/lib/Analysis/ValueTracking.cpp +++ b/llvm/lib/Analysis/ValueTracking.cpp @@ -1294,39 +1294,11 @@ static void computeKnownBitsFromOperator(const Operator *I, break; } case Instruction::SRem: - if (ConstantInt *Rem = dyn_cast(I->getOperand(1))) { - APInt RA = Rem->getValue().abs(); - if (RA.isPowerOf2()) { - APInt LowBits = RA - 1; - computeKnownBits(I->getOperand(0), Known2, Depth + 1, Q); - - // The low bits of the first operand are unchanged by the srem. - Known.Zero = Known2.Zero & LowBits; - Known.One = Known2.One & LowBits; - - // If the first operand is non-negative or has all low bits zero, then - // the upper bits are all zero. - if (Known2.isNonNegative() || LowBits.isSubsetOf(Known2.Zero)) - Known.Zero |= ~LowBits; - - // If the first operand is negative and not all low bits are zero, then - // the upper bits are all one. - if (Known2.isNegative() && LowBits.intersects(Known2.One)) - Known.One |= ~LowBits; - - assert((Known.Zero & Known.One) == 0 && "Bits known to be one AND zero?"); - break; - } - } - - // The sign bit is the LHS's sign bit, except when the result of the - // remainder is zero. - computeKnownBits(I->getOperand(0), Known2, Depth + 1, Q); - // If it's known zero, our sign bit is also zero. - if (Known2.isNonNegative()) - Known.makeNonNegative(); - + computeKnownBits(I->getOperand(0), Known, Depth + 1, Q); + computeKnownBits(I->getOperand(1), Known2, Depth + 1, Q); + Known = KnownBits::srem(Known, Known2); break; + case Instruction::URem: computeKnownBits(I->getOperand(0), Known, Depth + 1, Q); computeKnownBits(I->getOperand(1), Known2, Depth + 1, Q); diff --git a/llvm/lib/Support/KnownBits.cpp b/llvm/lib/Support/KnownBits.cpp index 3a50938..7ca949b 100644 --- a/llvm/lib/Support/KnownBits.cpp +++ b/llvm/lib/Support/KnownBits.cpp @@ -345,6 +345,36 @@ KnownBits KnownBits::urem(const KnownBits &LHS, const KnownBits &RHS) { return Known; } +KnownBits KnownBits::srem(const KnownBits &LHS, const KnownBits &RHS) { + unsigned BitWidth = LHS.getBitWidth(); + assert(!LHS.hasConflict() && !RHS.hasConflict()); + KnownBits Known(BitWidth); + + if (RHS.isConstant() && RHS.getConstant().isPowerOf2()) { + // The low bits of the first operand are unchanged by the srem. + APInt LowBits = RHS.getConstant() - 1; + Known.Zero = LHS.Zero & LowBits; + Known.One = LHS.One & LowBits; + + // If the first operand is non-negative or has all low bits zero, then + // the upper bits are all zero. + if (LHS.isNonNegative() || LowBits.isSubsetOf(LHS.Zero)) + Known.Zero |= ~LowBits; + + // If the first operand is negative and not all low bits are zero, then + // the upper bits are all one. + if (LHS.isNegative() && LowBits.intersects(LHS.One)) + Known.One |= ~LowBits; + return Known; + } + + // The sign bit is the LHS's sign bit, except when the result of the + // remainder is zero. If it's known zero, our sign bit is also zero. + if (LHS.isNonNegative()) + Known.makeNonNegative(); + return Known; +} + KnownBits &KnownBits::operator&=(const KnownBits &RHS) { // Result bit is 0 if either operand bit is 0. Zero |= RHS.Zero; diff --git a/llvm/unittests/Support/KnownBitsTest.cpp b/llvm/unittests/Support/KnownBitsTest.cpp index 60e61b5..709a3fc 100644 --- a/llvm/unittests/Support/KnownBitsTest.cpp +++ b/llvm/unittests/Support/KnownBitsTest.cpp @@ -115,6 +115,7 @@ TEST(KnownBitsTest, BinaryExhaustive) { KnownBits KnownMul(KnownAnd); KnownBits KnownUDiv(KnownAnd); KnownBits KnownURem(KnownAnd); + KnownBits KnownSRem(KnownAnd); KnownBits KnownShl(KnownAnd); KnownBits KnownLShr(KnownAnd); KnownBits KnownAShr(KnownAnd); @@ -163,6 +164,10 @@ TEST(KnownBitsTest, BinaryExhaustive) { Res = N1.urem(N2); KnownURem.One &= Res; KnownURem.Zero &= ~Res; + + Res = N1.srem(N2); + KnownSRem.One &= Res; + KnownSRem.Zero &= ~Res; } if (N2.ult(1ULL << N1.getBitWidth())) { @@ -227,6 +232,10 @@ TEST(KnownBitsTest, BinaryExhaustive) { EXPECT_TRUE(ComputedURem.Zero.isSubsetOf(KnownURem.Zero)); EXPECT_TRUE(ComputedURem.One.isSubsetOf(KnownURem.One)); + KnownBits ComputedSRem = KnownBits::srem(Known1, Known2); + EXPECT_TRUE(ComputedSRem.Zero.isSubsetOf(KnownSRem.Zero)); + EXPECT_TRUE(ComputedSRem.One.isSubsetOf(KnownSRem.One)); + KnownBits ComputedShl = KnownBits::shl(Known1, Known2); EXPECT_TRUE(ComputedShl.Zero.isSubsetOf(KnownShl.Zero)); EXPECT_TRUE(ComputedShl.One.isSubsetOf(KnownShl.One)); -- 2.7.4