Teach InstCombine's ComputeMaskedBits what SelectionDAG's
ComputeMaskedBits knows about cttz, ctlz, and ctpop. Teach
SelectionDAG's ComputeMaskedBits what InstCombine's knows
about SRem. And teach them both some things about high bits
in Mul, UDiv, URem, and Sub. This allows instcombine and
dagcombine to eliminate sign-extension operations in
several new cases.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@50358 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Transforms/Scalar/InstructionCombining.cpp b/lib/Transforms/Scalar/InstructionCombining.cpp
index 6bf06e7..655ab10 100644
--- a/lib/Transforms/Scalar/InstructionCombining.cpp
+++ b/lib/Transforms/Scalar/InstructionCombining.cpp
@@ -700,15 +700,15 @@
return;
}
+ KnownZero.clear(); KnownOne.clear(); // Start out not knowing anything.
+
if (Depth == 6 || Mask == 0)
return; // Limit search depth.
User *I = dyn_cast<User>(V);
if (!I) return;
- KnownZero.clear(); KnownOne.clear(); // Don't know anything.
APInt KnownZero2(KnownZero), KnownOne2(KnownOne);
-
switch (getOpcode(I)) {
default: break;
case Instruction::And: {
@@ -759,16 +759,42 @@
assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
// If low bits are zero in either operand, output low known-0 bits.
+ // Also compute a conserative estimate for high known-0 bits.
// More trickiness is possible, but this is sufficient for the
// interesting case of alignment computation.
KnownOne.clear();
unsigned TrailZ = KnownZero.countTrailingOnes() +
KnownZero2.countTrailingOnes();
+ unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
+ KnownZero2.countLeadingOnes() +
+ 1, BitWidth) - BitWidth;
+
TrailZ = std::min(TrailZ, BitWidth);
- KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ);
+ LeadZ = std::min(LeadZ, BitWidth);
+ KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
+ APInt::getHighBitsSet(BitWidth, LeadZ);
KnownZero &= Mask;
return;
}
+ case Instruction::UDiv: {
+ // For the purposes of computing leading zeros we can conservatively
+ // treat a udiv as a logical right shift by the power of 2 known to
+ // be greater than the denominator.
+ APInt AllOnes = APInt::getAllOnesValue(BitWidth);
+ ComputeMaskedBits(I->getOperand(0),
+ AllOnes, KnownZero2, KnownOne2, Depth+1);
+ unsigned LeadZ = KnownZero2.countLeadingOnes();
+
+ KnownOne2.clear();
+ KnownZero2.clear();
+ ComputeMaskedBits(I->getOperand(1),
+ AllOnes, KnownZero2, KnownOne2, Depth+1);
+ LeadZ = std::min(BitWidth,
+ LeadZ + BitWidth - KnownOne2.countLeadingZeros());
+
+ KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ) & Mask;
+ return;
+ }
case Instruction::Select:
ComputeMaskedBits(I->getOperand(2), Mask, KnownZero, KnownOne, Depth+1);
ComputeMaskedBits(I->getOperand(1), Mask, KnownZero2, KnownOne2, Depth+1);
@@ -900,38 +926,36 @@
unsigned NLZ = (CLHS->getValue()+1).countLeadingZeros();
// NLZ can't be BitWidth with no sign bit
APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
- ComputeMaskedBits(I->getOperand(1), MaskV, KnownZero, KnownOne, Depth+1);
+ ComputeMaskedBits(I->getOperand(1), MaskV, KnownZero2, KnownOne2,
+ Depth+1);
- // If all of the MaskV bits are known to be zero, then we know the output
- // top bits are zero, because we now know that the output is from [0-C].
- if ((KnownZero & MaskV) == MaskV) {
+ // If all of the MaskV bits are known to be zero, then we know the
+ // output top bits are zero, because we now know that the output is
+ // from [0-C].
+ if ((KnownZero2 & MaskV) == MaskV) {
unsigned NLZ2 = CLHS->getValue().countLeadingZeros();
// Top bits known zero.
KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2) & Mask;
- KnownOne = APInt(BitWidth, 0); // No one bits known.
- } else {
- KnownZero = KnownOne = APInt(BitWidth, 0); // Otherwise, nothing known.
}
- return;
}
}
}
// fall through
case Instruction::Add: {
- // If either the LHS or the RHS are Zero, the result is zero.
- ComputeMaskedBits(I->getOperand(1), Mask, KnownZero, KnownOne, Depth+1);
- ComputeMaskedBits(I->getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1);
- assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
- assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
-
// Output known-0 bits are known if clear or set in both the low clear bits
// common to both LHS & RHS. For example, 8+(X<<3) is known to have the
// low 3 bits clear.
- unsigned KnownZeroOut = std::min(KnownZero.countTrailingOnes(),
- KnownZero2.countTrailingOnes());
-
- KnownZero = APInt::getLowBitsSet(BitWidth, KnownZeroOut);
- KnownOne = APInt(BitWidth, 0);
+ APInt Mask2 = APInt::getLowBitsSet(BitWidth, Mask.countTrailingOnes());
+ ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero2, KnownOne2, Depth+1);
+ assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
+ unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
+
+ ComputeMaskedBits(I->getOperand(1), Mask2, KnownZero2, KnownOne2, Depth+1);
+ assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
+ KnownZeroOut = std::min(KnownZeroOut,
+ KnownZero2.countTrailingOnes());
+
+ KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
return;
}
case Instruction::SRem:
@@ -956,7 +980,7 @@
}
}
break;
- case Instruction::URem:
+ case Instruction::URem: {
if (ConstantInt *Rem = dyn_cast<ConstantInt>(I->getOperand(1))) {
APInt RA = Rem->getValue();
if (RA.isStrictlyPositive() && RA.isPowerOf2()) {
@@ -965,19 +989,24 @@
KnownZero |= ~LowBits & Mask;
ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero, KnownOne,Depth+1);
assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
+ break;
}
- } else {
- // Since the result is less than or equal to RHS, any leading zero bits
- // in RHS must also exist in the result.
- APInt AllOnes = APInt::getAllOnesValue(BitWidth);
- ComputeMaskedBits(I->getOperand(1), AllOnes, KnownZero2, KnownOne2,
- Depth+1);
-
- uint32_t Leaders = KnownZero2.countLeadingOnes();
- KnownZero |= APInt::getHighBitsSet(BitWidth, Leaders) & Mask;
- assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
}
+
+ // Since the result is less than or equal to either operand, any leading
+ // zero bits in either operand must also exist in the result.
+ APInt AllOnes = APInt::getAllOnesValue(BitWidth);
+ ComputeMaskedBits(I->getOperand(0), AllOnes, KnownZero, KnownOne,
+ Depth+1);
+ ComputeMaskedBits(I->getOperand(1), AllOnes, KnownZero2, KnownOne2,
+ Depth+1);
+
+ uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
+ KnownZero2.countLeadingOnes());
+ KnownOne.clear();
+ KnownZero = APInt::getHighBitsSet(BitWidth, Leaders) & Mask;
break;
+ }
case Instruction::Alloca:
case Instruction::Malloc: {
@@ -1088,6 +1117,20 @@
}
break;
}
+ case Instruction::Call:
+ if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
+ switch (II->getIntrinsicID()) {
+ default: break;
+ case Intrinsic::ctpop:
+ case Intrinsic::ctlz:
+ case Intrinsic::cttz: {
+ unsigned LowBits = Log2_32(BitWidth)+1;
+ KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
+ break;
+ }
+ }
+ }
+ break;
}
}
@@ -1232,7 +1275,9 @@
APInt LHSKnownZero(BitWidth, 0), LHSKnownOne(BitWidth, 0);
APInt &RHSKnownZero = KnownZero, &RHSKnownOne = KnownOne;
switch (I->getOpcode()) {
- default: break;
+ default:
+ ComputeMaskedBits(V, DemandedMask, RHSKnownZero, RHSKnownOne, Depth);
+ break;
case Instruction::And:
// If either the LHS or the RHS are Zero, the result is zero.
if (SimplifyDemandedBits(I->getOperand(1), DemandedMask,
@@ -1578,6 +1623,9 @@
LHSKnownZero, LHSKnownOne, Depth+1))
return true;
}
+ // Otherwise just hand the sub off to ComputeMaskedBits to fill in
+ // the known zeros and ones.
+ ComputeMaskedBits(V, DemandedMask, RHSKnownZero, RHSKnownOne, Depth);
break;
case Instruction::Shl:
if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) {
@@ -1695,10 +1743,10 @@
}
}
break;
- case Instruction::URem:
+ case Instruction::URem: {
if (ConstantInt *Rem = dyn_cast<ConstantInt>(I->getOperand(1))) {
APInt RA = Rem->getValue();
- if (RA.isPowerOf2()) {
+ if (RA.isStrictlyPositive() && RA.isPowerOf2()) {
APInt LowBits = (RA - 1) | RA;
APInt Mask2 = LowBits & DemandedMask;
KnownZero |= ~LowBits & DemandedMask;
@@ -1707,19 +1755,26 @@
return true;
assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
+ break;
}
- } else {
- APInt KnownZero2(BitWidth, 0), KnownOne2(BitWidth, 0);
- APInt AllOnes = APInt::getAllOnesValue(BitWidth);
- if (SimplifyDemandedBits(I->getOperand(1), AllOnes,
- KnownZero2, KnownOne2, Depth+1))
- return true;
-
- uint32_t Leaders = KnownZero2.countLeadingOnes();
- KnownZero |= APInt::getHighBitsSet(BitWidth, Leaders) & DemandedMask;
}
+
+ APInt KnownZero2(BitWidth, 0), KnownOne2(BitWidth, 0);
+ APInt AllOnes = APInt::getAllOnesValue(BitWidth);
+ ComputeMaskedBits(I->getOperand(0), AllOnes,
+ KnownZero2, KnownOne2, Depth+1);
+ uint32_t Leaders = KnownZero2.countLeadingOnes();
+ APInt HighZeros = APInt::getHighBitsSet(BitWidth, Leaders);
+ if (SimplifyDemandedBits(I->getOperand(1), ~HighZeros,
+ KnownZero2, KnownOne2, Depth+1))
+ return true;
+
+ Leaders = std::max(Leaders,
+ KnownZero2.countLeadingOnes());
+ KnownZero = APInt::getHighBitsSet(BitWidth, Leaders) & DemandedMask;
break;
}
+ }
// If the client is only demanding bits that we know, return the known
// constant.