From e237d56b43ebfbb9847648ff82aa17c3d7607481 Mon Sep 17 00:00:00 2001 From: Simon Pilgrim Date: Thu, 5 Nov 2020 14:29:13 +0000 Subject: [PATCH] [KnownBits] Move ValueTracking/SelectionDAG UREM KnownBits handling to KnownBits::urem. NFCI. Both these have the same implementation - so move them to a single KnownBits copy. GlobalISel will be able to use this as well with minimal effort. --- llvm/include/llvm/Support/KnownBits.h | 3 +++ llvm/lib/Analysis/ValueTracking.cpp | 22 ++-------------------- llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp | 21 +-------------------- llvm/lib/Support/KnownBits.cpp | 21 +++++++++++++++++++++ llvm/unittests/Support/KnownBitsTest.cpp | 9 +++++++++ 5 files changed, 36 insertions(+), 40 deletions(-) diff --git a/llvm/include/llvm/Support/KnownBits.h b/llvm/include/llvm/Support/KnownBits.h index 7ed20e1..2ef4a8f 100644 --- a/llvm/include/llvm/Support/KnownBits.h +++ b/llvm/include/llvm/Support/KnownBits.h @@ -261,6 +261,9 @@ public: /// Compute known bits for udiv(LHS, RHS). static KnownBits udiv(const KnownBits &LHS, const KnownBits &RHS); + /// Compute known bits for urem(LHS, RHS). + static KnownBits urem(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 07113e18..632a5ea 100644 --- a/llvm/lib/Analysis/ValueTracking.cpp +++ b/llvm/lib/Analysis/ValueTracking.cpp @@ -1327,29 +1327,11 @@ static void computeKnownBitsFromOperator(const Operator *I, Known.makeNonNegative(); break; - case Instruction::URem: { - if (ConstantInt *Rem = dyn_cast(I->getOperand(1))) { - const APInt &RA = Rem->getValue(); - if (RA.isPowerOf2()) { - APInt LowBits = (RA - 1); - computeKnownBits(I->getOperand(0), Known, Depth + 1, Q); - Known.Zero |= ~LowBits; - Known.One &= LowBits; - break; - } - } - - // Since the result is less than or equal to either operand, any leading - // zero bits in either operand must also exist in the result. + case Instruction::URem: computeKnownBits(I->getOperand(0), Known, Depth + 1, Q); computeKnownBits(I->getOperand(1), Known2, Depth + 1, Q); - - unsigned Leaders = - std::max(Known.countMinLeadingZeros(), Known2.countMinLeadingZeros()); - Known.resetAll(); - Known.Zero.setHighBits(Leaders); + Known = KnownBits::urem(Known, Known2); break; - } case Instruction::Alloca: Known.Zero.setLowBits(Log2(cast(I)->getAlign())); break; diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp index 6afddb5..782c38d 100644 --- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp +++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp @@ -3274,28 +3274,9 @@ KnownBits SelectionDAG::computeKnownBits(SDValue Op, const APInt &DemandedElts, } break; case ISD::UREM: { - if (ConstantSDNode *Rem = isConstOrConstSplat(Op.getOperand(1))) { - const APInt &RA = Rem->getAPIntValue(); - if (RA.isPowerOf2()) { - APInt LowBits = (RA - 1); - Known2 = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1); - - // The upper bits are all zero, the lower ones are unchanged. - Known.Zero = Known2.Zero | ~LowBits; - Known.One = Known2.One & LowBits; - break; - } - } - - // Since the result is less than or equal to either operand, any leading - // zero bits in either operand must also exist in the result. Known = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1); Known2 = computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1); - - uint32_t Leaders = - std::max(Known.countMinLeadingZeros(), Known2.countMinLeadingZeros()); - Known.resetAll(); - Known.Zero.setHighBits(Leaders); + Known = KnownBits::urem(Known, Known2); break; } case ISD::EXTRACT_ELEMENT: { diff --git a/llvm/lib/Support/KnownBits.cpp b/llvm/lib/Support/KnownBits.cpp index dff34eb..3a50938 100644 --- a/llvm/lib/Support/KnownBits.cpp +++ b/llvm/lib/Support/KnownBits.cpp @@ -324,6 +324,27 @@ KnownBits KnownBits::udiv(const KnownBits &LHS, const KnownBits &RHS) { return Known; } +KnownBits KnownBits::urem(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 upper bits are all zero, the lower ones are unchanged. + APInt LowBits = RHS.getConstant() - 1; + Known.Zero = LHS.Zero | ~LowBits; + Known.One = LHS.One & LowBits; + return Known; + } + + // Since the result is less than or equal to either operand, any leading + // zero bits in either operand must also exist in the result. + uint32_t Leaders = + std::max(LHS.countMinLeadingZeros(), RHS.countMinLeadingZeros()); + Known.Zero.setHighBits(Leaders); + 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 43e5981..60e61b5 100644 --- a/llvm/unittests/Support/KnownBitsTest.cpp +++ b/llvm/unittests/Support/KnownBitsTest.cpp @@ -114,6 +114,7 @@ TEST(KnownBitsTest, BinaryExhaustive) { KnownBits KnownSMin(KnownAnd); KnownBits KnownMul(KnownAnd); KnownBits KnownUDiv(KnownAnd); + KnownBits KnownURem(KnownAnd); KnownBits KnownShl(KnownAnd); KnownBits KnownLShr(KnownAnd); KnownBits KnownAShr(KnownAnd); @@ -158,6 +159,10 @@ TEST(KnownBitsTest, BinaryExhaustive) { Res = N1.udiv(N2); KnownUDiv.One &= Res; KnownUDiv.Zero &= ~Res; + + Res = N1.urem(N2); + KnownURem.One &= Res; + KnownURem.Zero &= ~Res; } if (N2.ult(1ULL << N1.getBitWidth())) { @@ -218,6 +223,10 @@ TEST(KnownBitsTest, BinaryExhaustive) { EXPECT_TRUE(ComputedUDiv.Zero.isSubsetOf(KnownUDiv.Zero)); EXPECT_TRUE(ComputedUDiv.One.isSubsetOf(KnownUDiv.One)); + KnownBits ComputedURem = KnownBits::urem(Known1, Known2); + EXPECT_TRUE(ComputedURem.Zero.isSubsetOf(KnownURem.Zero)); + EXPECT_TRUE(ComputedURem.One.isSubsetOf(KnownURem.One)); + KnownBits ComputedShl = KnownBits::shl(Known1, Known2); EXPECT_TRUE(ComputedShl.Zero.isSubsetOf(KnownShl.Zero)); EXPECT_TRUE(ComputedShl.One.isSubsetOf(KnownShl.One)); -- 2.7.4