summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/SelectionDAG
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/CodeGen/SelectionDAG')
-rw-r--r--llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp124
1 files changed, 111 insertions, 13 deletions
diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
index c2c7bb07ca8..cb375830b17 100644
--- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
@@ -2007,9 +2007,26 @@ static const APInt *getValidShiftAmountConstant(SDValue V) {
}
/// Determine which bits of Op are known to be either zero or one and return
-/// them in the KnownZero/KnownOne bitsets.
+/// them in the KnownZero/KnownOne bitsets. For vectors, the known bits are
+/// those that are shared by every vector element.
void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
APInt &KnownOne, unsigned Depth) const {
+ EVT VT = Op.getValueType();
+ APInt DemandedElts = VT.isVector()
+ ? APInt::getAllOnesValue(VT.getVectorNumElements())
+ : APInt(1, 1);
+ computeKnownBits(Op, KnownZero, KnownOne, DemandedElts, Depth);
+}
+
+/// Determine which bits of Op are known to be either zero or one and return
+/// them in the KnownZero/KnownOne bitsets. The DemandedElts argument allows
+/// us to only collect the known bits that are shared by the requested vector
+/// elements.
+/// TODO: We only support DemandedElts on a few opcodes so far, the remainder
+/// should be added when they become necessary.
+void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
+ APInt &KnownOne, const APInt &DemandedElts,
+ unsigned Depth) const {
unsigned BitWidth = Op.getScalarValueSizeInBits();
KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
@@ -2017,6 +2034,10 @@ void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
return; // Limit search depth.
APInt KnownZero2, KnownOne2;
+ unsigned NumElts = DemandedElts.getBitWidth();
+
+ if (DemandedElts == APInt(NumElts, 0))
+ return; // No demanded elts, better to assume we don't know anything.
switch (Op.getOpcode()) {
case ISD::Constant:
@@ -2025,9 +2046,15 @@ void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
KnownZero = ~KnownOne;
break;
case ISD::BUILD_VECTOR:
- // Collect the known bits that are shared by every vector element.
+ // Collect the known bits that are shared by every demanded vector element.
+ assert(NumElts == Op.getValueType().getVectorNumElements() &&
+ "Unexpected vector size");
KnownZero = KnownOne = APInt::getAllOnesValue(BitWidth);
- for (SDValue SrcOp : Op->ops()) {
+ for (unsigned i = 0, e = Op.getNumOperands(); i != e; ++i) {
+ if (!DemandedElts[i])
+ continue;
+
+ SDValue SrcOp = Op.getOperand(i);
computeKnownBits(SrcOp, KnownZero2, KnownOne2, Depth + 1);
// BUILD_VECTOR can implicitly truncate sources, we must handle this.
@@ -2038,16 +2065,72 @@ void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
KnownZero2 = KnownZero2.trunc(BitWidth);
}
- // Known bits are the values that are shared by every element.
- // TODO: support per-element known bits.
+ // Known bits are the values that are shared by every demanded element.
+ KnownOne &= KnownOne2;
+ KnownZero &= KnownZero2;
+ }
+ break;
+ case ISD::VECTOR_SHUFFLE: {
+ // Collect the known bits that are shared by every vector element referenced
+ // by the shuffle.
+ APInt DemandedLHS(NumElts, 0), DemandedRHS(NumElts, 0);
+ KnownZero = KnownOne = APInt::getAllOnesValue(BitWidth);
+ const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(Op);
+ assert(NumElts == SVN->getMask().size() && "Unexpected vector size");
+ for (unsigned i = 0; i != NumElts; ++i) {
+ int M = SVN->getMaskElt(i);
+ if (M < 0) {
+ // For UNDEF elements, we don't know anything about the common state of
+ // the shuffle result.
+ // FIXME: Is this too pessimistic?
+ KnownZero = KnownOne = APInt(BitWidth, 0);
+ break;
+ }
+ if (!DemandedElts[i])
+ continue;
+
+ if ((unsigned)M < NumElts)
+ DemandedLHS.setBit((unsigned)M % NumElts);
+ else
+ DemandedRHS.setBit((unsigned)M % NumElts);
+ }
+ // Known bits are the values that are shared by every demanded element.
+ if (DemandedLHS != APInt(NumElts, 0)) {
+ SDValue LHS = Op.getOperand(0);
+ computeKnownBits(LHS, KnownZero2, KnownOne2, DemandedLHS, Depth + 1);
KnownOne &= KnownOne2;
KnownZero &= KnownZero2;
}
+ if (DemandedRHS != APInt(NumElts, 0)) {
+ SDValue RHS = Op.getOperand(1);
+ computeKnownBits(RHS, KnownZero2, KnownOne2, DemandedRHS, Depth + 1);
+ KnownOne &= KnownOne2;
+ KnownZero &= KnownZero2;
+ }
+ break;
+ }
+ case ISD::EXTRACT_SUBVECTOR: {
+ // If we know the element index, just demand that subvector elements,
+ // otherwise demand them all.
+ SDValue Src = Op.getOperand(0);
+ ConstantSDNode *SubIdx = dyn_cast<ConstantSDNode>(Op.getOperand(1));
+ unsigned NumSrcElts = Src.getValueType().getVectorNumElements();
+ if (SubIdx && SubIdx->getAPIntValue().ule(NumSrcElts - NumElts)) {
+ // Offset the demanded elts by the subvector index.
+ uint64_t Idx = SubIdx->getZExtValue();
+ APInt DemandedSrc = DemandedElts.zext(NumSrcElts).shl(Idx);
+ computeKnownBits(Src, KnownZero, KnownOne, DemandedSrc, Depth + 1);
+ } else {
+ computeKnownBits(Src, KnownZero, KnownOne, Depth + 1);
+ }
break;
+ }
case ISD::AND:
// If either the LHS or the RHS are Zero, the result is zero.
- computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
- computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
+ computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, DemandedElts,
+ Depth + 1);
+ computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, DemandedElts,
+ Depth + 1);
// Output known-1 bits are only known if set in both the LHS & RHS.
KnownOne &= KnownOne2;
@@ -2206,7 +2289,8 @@ void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
if (NewBits.getBoolValue())
InputDemandedBits |= InSignBit;
- computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
+ computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, DemandedElts,
+ Depth + 1);
KnownOne &= InputDemandedBits;
KnownZero &= InputDemandedBits;
@@ -2253,7 +2337,8 @@ void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
KnownZero = KnownZero.trunc(InBits);
KnownOne = KnownOne.trunc(InBits);
- computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
+ computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, DemandedElts,
+ Depth + 1);
KnownZero = KnownZero.zext(BitWidth);
KnownOne = KnownOne.zext(BitWidth);
KnownZero |= NewBits;
@@ -2266,7 +2351,8 @@ void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
KnownZero = KnownZero.trunc(InBits);
KnownOne = KnownOne.trunc(InBits);
- computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
+ computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, DemandedElts,
+ Depth + 1);
// Note if the sign bit is known to be zero or one.
bool SignBitKnownZero = KnownZero.isNegative();
@@ -2439,16 +2525,28 @@ void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
// At the moment we keep this simple and skip tracking the specific
// element. This way we get the lowest common denominator for all elements
// of the vector.
- // TODO: get information for given vector element
+ SDValue InVec = Op.getOperand(0);
+ SDValue EltNo = Op.getOperand(1);
+ EVT VecVT = InVec.getValueType();
const unsigned BitWidth = Op.getValueSizeInBits();
- const unsigned EltBitWidth = Op.getOperand(0).getScalarValueSizeInBits();
+ const unsigned EltBitWidth = VecVT.getScalarSizeInBits();
+ const unsigned NumSrcElts = VecVT.getVectorNumElements();
// If BitWidth > EltBitWidth the value is anyext:ed. So we do not know
// anything about the extended bits.
if (BitWidth > EltBitWidth) {
KnownZero = KnownZero.trunc(EltBitWidth);
KnownOne = KnownOne.trunc(EltBitWidth);
}
- computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
+ ConstantSDNode *ConstEltNo = dyn_cast<ConstantSDNode>(EltNo);
+ if (ConstEltNo && ConstEltNo->getAPIntValue().ult(NumSrcElts)) {
+ // If we know the element index, just demand that vector element.
+ unsigned Idx = ConstEltNo->getZExtValue();
+ APInt DemandedElt = APInt::getOneBitSet(NumSrcElts, Idx);
+ computeKnownBits(InVec, KnownZero, KnownOne, DemandedElt, Depth + 1);
+ } else {
+ // Unknown element index, so ignore DemandedElts and demand them all.
+ computeKnownBits(InVec, KnownZero, KnownOne, Depth + 1);
+ }
if (BitWidth > EltBitWidth) {
KnownZero = KnownZero.zext(BitWidth);
KnownOne = KnownOne.zext(BitWidth);
OpenPOWER on IntegriCloud