diff options
author | Nate Begeman <natebegeman@mac.com> | 2009-04-27 18:41:29 +0000 |
---|---|---|
committer | Nate Begeman <natebegeman@mac.com> | 2009-04-27 18:41:29 +0000 |
commit | 9008ca6b6b4f638cfafccb593cbc5b1d3f5ab877 (patch) | |
tree | 0b13ccb79eb37ff6bb74f3be7234826602c7aff1 /lib/CodeGen/SelectionDAG | |
parent | c167cac8f0f0227de08422563844bcb889a4f3dd (diff) | |
download | external_llvm-9008ca6b6b4f638cfafccb593cbc5b1d3f5ab877.zip external_llvm-9008ca6b6b4f638cfafccb593cbc5b1d3f5ab877.tar.gz external_llvm-9008ca6b6b4f638cfafccb593cbc5b1d3f5ab877.tar.bz2 |
2nd attempt, fixing SSE4.1 issues and implementing feedback from duncan.
PR2957
ISD::VECTOR_SHUFFLE now stores an array of integers representing the shuffle
mask internal to the node, rather than taking a BUILD_VECTOR of ConstantSDNodes
as the shuffle mask. A value of -1 represents UNDEF.
In addition to eliminating the creation of illegal BUILD_VECTORS just to
represent shuffle masks, we are better about canonicalizing the shuffle mask,
resulting in substantially better code for some classes of shuffles.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70225 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/CodeGen/SelectionDAG')
-rw-r--r-- | lib/CodeGen/SelectionDAG/DAGCombiner.cpp | 192 | ||||
-rw-r--r-- | lib/CodeGen/SelectionDAG/LegalizeDAG.cpp | 223 | ||||
-rw-r--r-- | lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp | 90 | ||||
-rw-r--r-- | lib/CodeGen/SelectionDAG/SelectionDAG.cpp | 154 | ||||
-rw-r--r-- | lib/CodeGen/SelectionDAG/SelectionDAGBuild.cpp | 153 |
5 files changed, 363 insertions, 449 deletions
diff --git a/lib/CodeGen/SelectionDAG/DAGCombiner.cpp b/lib/CodeGen/SelectionDAG/DAGCombiner.cpp index bd4b10e..bd724af 100644 --- a/lib/CodeGen/SelectionDAG/DAGCombiner.cpp +++ b/lib/CodeGen/SelectionDAG/DAGCombiner.cpp @@ -5102,7 +5102,21 @@ SDValue DAGCombiner::visitINSERT_VECTOR_ELT(SDNode *N) { return DAG.getNode(ISD::BUILD_VECTOR, N->getDebugLoc(), InVec.getValueType(), &Ops[0], Ops.size()); } + // If the invec is an UNDEF and if EltNo is a constant, create a new + // BUILD_VECTOR with undef elements and the inserted element. + if (!LegalOperations && InVec.getOpcode() == ISD::UNDEF && + isa<ConstantSDNode>(EltNo)) { + MVT VT = InVec.getValueType(); + MVT EVT = VT.getVectorElementType(); + unsigned NElts = VT.getVectorNumElements(); + SmallVector<SDValue, 8> Ops(NElts, DAG.getUNDEF(EVT)); + unsigned Elt = cast<ConstantSDNode>(EltNo)->getZExtValue(); + if (Elt < Ops.size()) + Ops[Elt] = InVal; + return DAG.getNode(ISD::BUILD_VECTOR, N->getDebugLoc(), + InVec.getValueType(), &Ops[0], Ops.size()); + } return SDValue(); } @@ -5164,9 +5178,8 @@ SDValue DAGCombiner::visitEXTRACT_VECTOR_ELT(SDNode *N) { // to examine the mask. if (BCNumEltsChanged) return SDValue(); - unsigned Idx = cast<ConstantSDNode>(InVec.getOperand(2). - getOperand(Elt))->getZExtValue(); - unsigned NumElems = InVec.getOperand(2).getNumOperands(); + int Idx = cast<ShuffleVectorSDNode>(InVec)->getMaskElt(Elt); + int NumElems = InVec.getValueType().getVectorNumElements(); InVec = (Idx < NumElems) ? InVec.getOperand(0) : InVec.getOperand(1); if (InVec.getOpcode() == ISD::BIT_CONVERT) InVec = InVec.getOperand(0); @@ -5213,7 +5226,6 @@ SDValue DAGCombiner::visitEXTRACT_VECTOR_ELT(SDNode *N) { SDValue DAGCombiner::visitBUILD_VECTOR(SDNode *N) { unsigned NumInScalars = N->getNumOperands(); MVT VT = N->getValueType(0); - unsigned NumElts = VT.getVectorNumElements(); MVT EltType = VT.getVectorElementType(); // Check to see if this is a BUILD_VECTOR of a bunch of EXTRACT_VECTOR_ELT @@ -5256,56 +5268,36 @@ SDValue DAGCombiner::visitBUILD_VECTOR(SDNode *N) { } // If everything is good, we can make a shuffle operation. - MVT IndexVT = MVT::i32; if (VecIn1.getNode()) { - SmallVector<SDValue, 8> BuildVecIndices; + SmallVector<int, 8> Mask; for (unsigned i = 0; i != NumInScalars; ++i) { if (N->getOperand(i).getOpcode() == ISD::UNDEF) { - BuildVecIndices.push_back(DAG.getUNDEF(IndexVT)); + Mask.push_back(-1); continue; } - SDValue Extract = N->getOperand(i); - // If extracting from the first vector, just use the index directly. + SDValue Extract = N->getOperand(i); SDValue ExtVal = Extract.getOperand(1); if (Extract.getOperand(0) == VecIn1) { - if (ExtVal.getValueType() == IndexVT) - BuildVecIndices.push_back(ExtVal); - else { - unsigned Idx = cast<ConstantSDNode>(ExtVal)->getZExtValue(); - BuildVecIndices.push_back(DAG.getConstant(Idx, IndexVT)); - } + Mask.push_back(cast<ConstantSDNode>(ExtVal)->getZExtValue()); continue; } // Otherwise, use InIdx + VecSize unsigned Idx = cast<ConstantSDNode>(ExtVal)->getZExtValue(); - BuildVecIndices.push_back(DAG.getConstant(Idx+NumInScalars, IndexVT)); + Mask.push_back(Idx+NumInScalars); } // Add count and size info. - MVT BuildVecVT = MVT::getVectorVT(IndexVT, NumElts); - if (!TLI.isTypeLegal(BuildVecVT) && LegalTypes) + if (!TLI.isTypeLegal(VT) && LegalTypes) return SDValue(); // Return the new VECTOR_SHUFFLE node. - SDValue Ops[5]; + SDValue Ops[2]; Ops[0] = VecIn1; - if (VecIn2.getNode()) { - Ops[1] = VecIn2; - } else { - // Use an undef build_vector as input for the second operand. - std::vector<SDValue> UnOps(NumInScalars, - DAG.getUNDEF(EltType)); - Ops[1] = DAG.getNode(ISD::BUILD_VECTOR, N->getDebugLoc(), VT, - &UnOps[0], UnOps.size()); - AddToWorkList(Ops[1].getNode()); - } - - Ops[2] = DAG.getNode(ISD::BUILD_VECTOR, N->getDebugLoc(), BuildVecVT, - &BuildVecIndices[0], BuildVecIndices.size()); - return DAG.getNode(ISD::VECTOR_SHUFFLE, N->getDebugLoc(), VT, Ops, 3); + Ops[1] = VecIn2.getNode() ? VecIn2 : DAG.getUNDEF(VT); + return DAG.getVectorShuffle(VT, N->getDebugLoc(), Ops[0], Ops[1], &Mask[0]); } return SDValue(); @@ -5325,8 +5317,10 @@ SDValue DAGCombiner::visitCONCAT_VECTORS(SDNode *N) { } SDValue DAGCombiner::visitVECTOR_SHUFFLE(SDNode *N) { - SDValue ShufMask = N->getOperand(2); - unsigned NumElts = ShufMask.getNumOperands(); + return SDValue(); + + MVT VT = N->getValueType(0); + unsigned NumElts = VT.getVectorNumElements(); SDValue N0 = N->getOperand(0); SDValue N1 = N->getOperand(1); @@ -5334,60 +5328,13 @@ SDValue DAGCombiner::visitVECTOR_SHUFFLE(SDNode *N) { assert(N0.getValueType().getVectorNumElements() == NumElts && "Vector shuffle must be normalized in DAG"); - // If the shuffle mask is an identity operation on the LHS, return the LHS. - bool isIdentity = true; - for (unsigned i = 0; i != NumElts; ++i) { - if (ShufMask.getOperand(i).getOpcode() != ISD::UNDEF && - cast<ConstantSDNode>(ShufMask.getOperand(i))->getZExtValue() != i) { - isIdentity = false; - break; - } - } - if (isIdentity) return N->getOperand(0); - - // If the shuffle mask is an identity operation on the RHS, return the RHS. - isIdentity = true; - for (unsigned i = 0; i != NumElts; ++i) { - if (ShufMask.getOperand(i).getOpcode() != ISD::UNDEF && - cast<ConstantSDNode>(ShufMask.getOperand(i))->getZExtValue() != - i+NumElts) { - isIdentity = false; - break; - } - } - if (isIdentity) return N->getOperand(1); - - // Check if the shuffle is a unary shuffle, i.e. one of the vectors is not - // needed at all. - bool isUnary = true; - bool isSplat = true; - int VecNum = -1; - unsigned BaseIdx = 0; - for (unsigned i = 0; i != NumElts; ++i) - if (ShufMask.getOperand(i).getOpcode() != ISD::UNDEF) { - unsigned Idx=cast<ConstantSDNode>(ShufMask.getOperand(i))->getZExtValue(); - int V = (Idx < NumElts) ? 0 : 1; - if (VecNum == -1) { - VecNum = V; - BaseIdx = Idx; - } else { - if (BaseIdx != Idx) - isSplat = false; - if (VecNum != V) { - isUnary = false; - break; - } - } - } - - // Normalize unary shuffle so the RHS is undef. - if (isUnary && VecNum == 1) - std::swap(N0, N1); + // FIXME: implement canonicalizations from DAG.getVectorShuffle() // If it is a splat, check if the argument vector is a build_vector with // all scalar elements the same. - if (isSplat) { + if (cast<ShuffleVectorSDNode>(N)->isSplat()) { SDNode *V = N0.getNode(); + // If this is a bit convert that changes the element type of the vector but // not the number of vector elements, look through it. Be careful not to @@ -5401,6 +5348,7 @@ SDValue DAGCombiner::visitVECTOR_SHUFFLE(SDNode *N) { if (V->getOpcode() == ISD::BUILD_VECTOR) { unsigned NumElems = V->getNumOperands(); + unsigned BaseIdx = cast<ShuffleVectorSDNode>(N)->getSplatIndex(); if (NumElems > BaseIdx) { SDValue Base; bool AllSame = true; @@ -5425,38 +5373,6 @@ SDValue DAGCombiner::visitVECTOR_SHUFFLE(SDNode *N) { } } } - - // If it is a unary or the LHS and the RHS are the same node, turn the RHS - // into an undef. - if (isUnary || N0 == N1) { - // Check the SHUFFLE mask, mapping any inputs from the 2nd operand into the - // first operand. - SmallVector<SDValue, 8> MappedOps; - - for (unsigned i = 0; i != NumElts; ++i) { - if (ShufMask.getOperand(i).getOpcode() == ISD::UNDEF || - cast<ConstantSDNode>(ShufMask.getOperand(i))->getZExtValue() < - NumElts) { - MappedOps.push_back(ShufMask.getOperand(i)); - } else { - unsigned NewIdx = - cast<ConstantSDNode>(ShufMask.getOperand(i))->getZExtValue() - - NumElts; - MappedOps.push_back(DAG.getConstant(NewIdx, - ShufMask.getOperand(i).getValueType())); - } - } - - ShufMask = DAG.getNode(ISD::BUILD_VECTOR, N->getDebugLoc(), - ShufMask.getValueType(), - &MappedOps[0], MappedOps.size()); - AddToWorkList(ShufMask.getNode()); - return DAG.getNode(ISD::VECTOR_SHUFFLE, N->getDebugLoc(), - N->getValueType(0), N0, - DAG.getUNDEF(N->getValueType(0)), - ShufMask); - } - return SDValue(); } @@ -5465,52 +5381,42 @@ SDValue DAGCombiner::visitVECTOR_SHUFFLE(SDNode *N) { /// e.g. AND V, <0xffffffff, 0, 0xffffffff, 0>. ==> /// vector_shuffle V, Zero, <0, 4, 2, 4> SDValue DAGCombiner::XformToShuffleWithZero(SDNode *N) { + MVT VT = N->getValueType(0); + DebugLoc dl = N->getDebugLoc(); SDValue LHS = N->getOperand(0); SDValue RHS = N->getOperand(1); if (N->getOpcode() == ISD::AND) { if (RHS.getOpcode() == ISD::BIT_CONVERT) RHS = RHS.getOperand(0); if (RHS.getOpcode() == ISD::BUILD_VECTOR) { - std::vector<SDValue> IdxOps; - unsigned NumOps = RHS.getNumOperands(); - unsigned NumElts = NumOps; + SmallVector<int, 8> Indices; + unsigned NumElts = RHS.getNumOperands(); for (unsigned i = 0; i != NumElts; ++i) { SDValue Elt = RHS.getOperand(i); if (!isa<ConstantSDNode>(Elt)) return SDValue(); else if (cast<ConstantSDNode>(Elt)->isAllOnesValue()) - IdxOps.push_back(DAG.getIntPtrConstant(i)); + Indices.push_back(i); else if (cast<ConstantSDNode>(Elt)->isNullValue()) - IdxOps.push_back(DAG.getIntPtrConstant(NumElts)); + Indices.push_back(NumElts); else return SDValue(); } // Let's see if the target supports this vector_shuffle. - if (!TLI.isVectorClearMaskLegal(IdxOps, TLI.getPointerTy(), DAG)) + MVT RVT = RHS.getValueType(); + if (!TLI.isVectorClearMaskLegal(Indices, RVT)) return SDValue(); // Return the new VECTOR_SHUFFLE node. - MVT EVT = RHS.getValueType().getVectorElementType(); - MVT VT = MVT::getVectorVT(EVT, NumElts); - MVT MaskVT = MVT::getVectorVT(TLI.getPointerTy(), NumElts); - std::vector<SDValue> Ops; - LHS = DAG.getNode(ISD::BIT_CONVERT, LHS.getDebugLoc(), VT, LHS); - Ops.push_back(LHS); - AddToWorkList(LHS.getNode()); - std::vector<SDValue> ZeroOps(NumElts, DAG.getConstant(0, EVT)); - Ops.push_back(DAG.getNode(ISD::BUILD_VECTOR, N->getDebugLoc(), - VT, &ZeroOps[0], ZeroOps.size())); - Ops.push_back(DAG.getNode(ISD::BUILD_VECTOR, N->getDebugLoc(), - MaskVT, &IdxOps[0], IdxOps.size())); - SDValue Result = DAG.getNode(ISD::VECTOR_SHUFFLE, N->getDebugLoc(), - VT, &Ops[0], Ops.size()); - - if (VT != N->getValueType(0)) - Result = DAG.getNode(ISD::BIT_CONVERT, N->getDebugLoc(), - N->getValueType(0), Result); - - return Result; + MVT EVT = RVT.getVectorElementType(); + SmallVector<SDValue,8> ZeroOps(RVT.getVectorNumElements(), + DAG.getConstant(0, EVT)); + SDValue Zero = DAG.getNode(ISD::BUILD_VECTOR, N->getDebugLoc(), + RVT, &ZeroOps[0], ZeroOps.size()); + LHS = DAG.getNode(ISD::BIT_CONVERT, dl, RVT, LHS); + SDValue Shuf = DAG.getVectorShuffle(RVT, dl, LHS, Zero, &Indices[0]); + return DAG.getNode(ISD::BIT_CONVERT, dl, VT, Shuf); } } diff --git a/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp b/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp index 5ea1ce3..be7a794 100644 --- a/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp +++ b/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp @@ -267,16 +267,10 @@ private: bool isVolatile, SDValue ValOp, unsigned StWidth, DebugLoc dl); - /// isShuffleLegal - Return non-null if a vector shuffle is legal with the - /// specified mask and type. Targets can specify exactly which masks they - /// support and the code generator is tasked with not creating illegal masks. - /// - /// Note that this will also return true for shuffles that are promoted to a - /// different type. - /// - /// If this is a legal shuffle, this method returns the (possibly promoted) - /// build_vector Mask. If it's not a legal shuffle, it returns null. - SDNode *isShuffleLegal(MVT VT, SDValue Mask) const; + /// promoteShuffle - Promote a shuffle mask of a vector VT to perform the + /// same shuffle on a vector of NVT. Must not create an illegal shuffle mask. + SDValue promoteShuffle(MVT NVT, MVT VT, DebugLoc dl, SDValue N1, SDValue N2, + SmallVectorImpl<int> &Mask) const; bool LegalizeAllNodesNotLeadingTo(SDNode *N, SDNode *Dest, SmallPtrSet<SDNode*, 32> &NodesLeadingTo); @@ -319,50 +313,35 @@ private: }; } -/// isVectorShuffleLegal - Return true if a vector shuffle is legal with the -/// specified mask and type. Targets can specify exactly which masks they -/// support and the code generator is tasked with not creating illegal masks. -/// -/// Note that this will also return true for shuffles that are promoted to a -/// different type. -SDNode *SelectionDAGLegalize::isShuffleLegal(MVT VT, SDValue Mask) const { - switch (TLI.getOperationAction(ISD::VECTOR_SHUFFLE, VT)) { - default: return 0; - case TargetLowering::Legal: - case TargetLowering::Custom: - break; - case TargetLowering::Promote: { - // If this is promoted to a different type, convert the shuffle mask and - // ask if it is legal in the promoted type! - MVT NVT = TLI.getTypeToPromoteTo(ISD::VECTOR_SHUFFLE, VT); - MVT EltVT = NVT.getVectorElementType(); - - // If we changed # elements, change the shuffle mask. - unsigned NumEltsGrowth = - NVT.getVectorNumElements() / VT.getVectorNumElements(); - assert(NumEltsGrowth && "Cannot promote to vector type with fewer elts!"); - if (NumEltsGrowth > 1) { - // Renumber the elements. - SmallVector<SDValue, 8> Ops; - for (unsigned i = 0, e = Mask.getNumOperands(); i != e; ++i) { - SDValue InOp = Mask.getOperand(i); - for (unsigned j = 0; j != NumEltsGrowth; ++j) { - if (InOp.getOpcode() == ISD::UNDEF) - Ops.push_back(DAG.getUNDEF(EltVT)); - else { - unsigned InEltNo = cast<ConstantSDNode>(InOp)->getZExtValue(); - Ops.push_back(DAG.getConstant(InEltNo*NumEltsGrowth+j, EltVT)); - } - } - } - Mask = DAG.getNode(ISD::BUILD_VECTOR, Mask.getDebugLoc(), - NVT, &Ops[0], Ops.size()); +/// promoteShuffle - Promote a shuffle mask of a vector VT to perform the +/// same shuffle on a vector of NVT. Must not create an illegal shuffle mask. +/// e.g. <v4i32> <0, 1, 0, 1> -> v8i16 <0, 1, 2, 3, 0, 1, 2, 3> +SDValue SelectionDAGLegalize::promoteShuffle(MVT NVT, MVT VT, DebugLoc dl, + SDValue N1, SDValue N2, + SmallVectorImpl<int> &Mask) const { + MVT EltVT = NVT.getVectorElementType(); + int NumMaskElts = VT.getVectorNumElements(); + int NumDestElts = NVT.getVectorNumElements(); + unsigned NumEltsGrowth = NumDestElts / NumMaskElts; + + assert(NumEltsGrowth && "Cannot promote to vector type with fewer elts!"); + + if (NumEltsGrowth == 1) + return DAG.getVectorShuffle(NVT, dl, N1, N2, &Mask[0]); + + SmallVector<int, 8> NewMask; + for (int i = 0; i != NumMaskElts; ++i) { + int Idx = Mask[i]; + for (unsigned j = 0; j != NumEltsGrowth; ++j) { + if (Idx < 0) + NewMask.push_back(-1); + else + NewMask.push_back(Idx * NumEltsGrowth + j); } - VT = NVT; - break; - } } - return TLI.isShuffleMaskLegal(Mask, VT) ? Mask.getNode() : 0; + assert((int)NewMask.size() == NumDestElts && "Non-integer NumEltsGrowth?"); + assert(TLI.isShuffleMaskLegal(NewMask, NVT) && "Shuffle not legal?"); + return DAG.getVectorShuffle(NVT, dl, N1, N2, &NewMask[0]); } SelectionDAGLegalize::SelectionDAGLegalize(SelectionDAG &dag, @@ -1652,25 +1631,15 @@ SDValue SelectionDAGLegalize::LegalizeOp(SDValue Op) { Tmp1.getValueType(), Tmp2); unsigned NumElts = Tmp1.getValueType().getVectorNumElements(); - MVT ShufMaskVT = - MVT::getIntVectorWithNumElements(NumElts); - MVT ShufMaskEltVT = ShufMaskVT.getVectorElementType(); - // We generate a shuffle of InVec and ScVec, so the shuffle mask // should be 0,1,2,3,4,5... with the appropriate element replaced with // elt 0 of the RHS. - SmallVector<SDValue, 8> ShufOps; - for (unsigned i = 0; i != NumElts; ++i) { - if (i != InsertPos->getZExtValue()) - ShufOps.push_back(DAG.getConstant(i, ShufMaskEltVT)); - else - ShufOps.push_back(DAG.getConstant(NumElts, ShufMaskEltVT)); - } - SDValue ShufMask = DAG.getNode(ISD::BUILD_VECTOR, dl, ShufMaskVT, - &ShufOps[0], ShufOps.size()); - - Result = DAG.getNode(ISD::VECTOR_SHUFFLE, dl, Tmp1.getValueType(), - Tmp1, ScVec, ShufMask); + SmallVector<int, 8> ShufOps; + for (unsigned i = 0; i != NumElts; ++i) + ShufOps.push_back(i != InsertPos->getZExtValue() ? i : NumElts); + + Result = DAG.getVectorShuffle(Tmp1.getValueType(), dl, Tmp1, ScVec, + &ShufOps[0]); Result = LegalizeOp(Result); break; } @@ -1705,16 +1674,21 @@ SDValue SelectionDAGLegalize::LegalizeOp(SDValue Op) { break; } break; - case ISD::VECTOR_SHUFFLE: + case ISD::VECTOR_SHUFFLE: { Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the input vectors, Tmp2 = LegalizeOp(Node->getOperand(1)); // but not the shuffle mask. - Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Node->getOperand(2)); + Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2); + MVT VT = Result.getValueType(); + + // Copy the Mask to a local SmallVector for use wi + SmallVector<int, 8> Mask; + cast<ShuffleVectorSDNode>(Result)->getMask(Mask); // Allow targets to custom lower the SHUFFLEs they support. - switch (TLI.getOperationAction(ISD::VECTOR_SHUFFLE, Result.getValueType())){ + switch (TLI.getOperationAction(ISD::VECTOR_SHUFFLE, VT)) { default: assert(0 && "Unknown operation action!"); case TargetLowering::Legal: - assert(isShuffleLegal(Result.getValueType(), Node->getOperand(2)) && + assert(TLI.isShuffleMaskLegal(Mask, VT) && "vector shuffle should not be created if not legal!"); break; case TargetLowering::Custom: @@ -1725,26 +1699,21 @@ SDValue SelectionDAGLegalize::LegalizeOp(SDValue Op) { } // FALLTHROUGH case TargetLowering::Expand: { - MVT VT = Node->getValueType(0); MVT EltVT = VT.getVectorElementType(); - MVT PtrVT = TLI.getPointerTy(); - SDValue Mask = Node->getOperand(2); - unsigned NumElems = Mask.getNumOperands(); + int NumElems = VT.getVectorNumElements(); SmallVector<SDValue, 8> Ops; - for (unsigned i = 0; i != NumElems; ++i) { - SDValue Arg = Mask.getOperand(i); - if (Arg.getOpcode() == ISD::UNDEF) { + for (int i = 0; i != NumElems; ++i) { + if (Mask[i] < 0) { Ops.push_back(DAG.getUNDEF(EltVT)); - } else { - assert(isa<ConstantSDNode>(Arg) && "Invalid VECTOR_SHUFFLE mask!"); - unsigned Idx = cast<ConstantSDNode>(Arg)->getZExtValue(); - if (Idx < NumElems) - Ops.push_back(DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, EltVT, Tmp1, - DAG.getConstant(Idx, PtrVT))); - else - Ops.push_back(DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, EltVT, Tmp2, - DAG.getConstant(Idx - NumElems, PtrVT))); + continue; } + int Idx = Mask[i]; + if (Idx < NumElems) + Ops.push_back(DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, EltVT, Tmp1, + DAG.getIntPtrConstant(Idx))); + else + Ops.push_back(DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, EltVT, Tmp2, + DAG.getIntPtrConstant(Idx - NumElems))); } Result = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, &Ops[0], Ops.size()); break; @@ -1759,15 +1728,13 @@ SDValue SelectionDAGLegalize::LegalizeOp(SDValue Op) { Tmp2 = DAG.getNode(ISD::BIT_CONVERT, dl, NVT, Tmp2); // Convert the shuffle mask to the right # elements. - Tmp3 = SDValue(isShuffleLegal(OVT, Node->getOperand(2)), 0); - assert(Tmp3.getNode() && "Shuffle not legal?"); - Result = DAG.getNode(ISD::VECTOR_SHUFFLE, dl, NVT, Tmp1, Tmp2, Tmp3); + Result = promoteShuffle(NVT, OVT, dl, Tmp1, Tmp2, Mask); Result = DAG.getNode(ISD::BIT_CONVERT, dl, OVT, Result); break; } } break; - + } case ISD::EXTRACT_VECTOR_ELT: Tmp1 = Node->getOperand(0); Tmp2 = LegalizeOp(Node->getOperand(1)); @@ -5490,6 +5457,7 @@ SDValue SelectionDAGLegalize::ExpandBUILD_VECTOR(SDNode *Node) { // FIXME: it would be far nicer to change this into map<SDValue,uint64_t> // and use a bitmask instead of a list of elements. + // FIXME: this doesn't treat <0, u, 0, u> for example, as a splat. std::map<SDValue, std::vector<unsigned> > Values; Values[SplatValue].push_back(0); bool isConstant = true; @@ -5546,21 +5514,17 @@ SDValue SelectionDAGLegalize::ExpandBUILD_VECTOR(SDNode *Node) { if (SplatValue.getNode()) { // Splat of one value? // Build the shuffle constant vector: <0, 0, 0, 0> - MVT MaskVT = MVT::getIntVectorWithNumElements(NumElems); - SDValue Zero = DAG.getConstant(0, MaskVT.getVectorElementType()); - std::vector<SDValue> ZeroVec(NumElems, Zero); - SDValue SplatMask = DAG.getNode(ISD::BUILD_VECTOR, dl, MaskVT, - &ZeroVec[0], ZeroVec.size()); + SmallVector<int, 8> ZeroVec(NumElems, 0); // If the target supports VECTOR_SHUFFLE and this shuffle mask, use it. - if (isShuffleLegal(VT, SplatMask)) { + if (TLI.isShuffleMaskLegal(ZeroVec, Node->getValueType(0))) { // Get the splatted value into the low element of a vector register. SDValue LowValVec = DAG.getNode(ISD::SCALAR_TO_VECTOR, dl, VT, SplatValue); // Return shuffle(LowValVec, undef, <0,0,0,0>) - return DAG.getNode(ISD::VECTOR_SHUFFLE, dl, VT, LowValVec, - DAG.getUNDEF(VT), SplatMask); + return DAG.getVectorShuffle(VT, dl, LowValVec, DAG.getUNDEF(VT), + &ZeroVec[0]); } } @@ -5582,35 +5546,25 @@ SDValue SelectionDAGLegalize::ExpandBUILD_VECTOR(SDNode *Node) { std::swap(Val1, Val2); // Build the shuffle constant vector: e.g. <0, 4, 0, 4> - MVT MaskVT = MVT::getIntVectorWithNumElements(NumElems); - MVT MaskEltVT = MaskVT.getVectorElementType(); - std::vector<SDValue> MaskVec(NumElems); + SmallVector<int, 8> ShuffleMask(NumElems, -1); // Set elements of the shuffle mask for Val1. std::vector<unsigned> &Val1Elts = Values[Val1]; for (unsigned i = 0, e = Val1Elts.size(); i != e; ++i) - MaskVec[Val1Elts[i]] = DAG.getConstant(0, MaskEltVT); + ShuffleMask[Val1Elts[i]] = 0; // Set elements of the shuffle mask for Val2. std::vector<unsigned> &Val2Elts = Values[Val2]; for (unsigned i = 0, e = Val2Elts.size(); i != e; ++i) if (Val2.getOpcode() != ISD::UNDEF) - MaskVec[Val2Elts[i]] = DAG.getConstant(NumElems, MaskEltVT); - else - MaskVec[Val2Elts[i]] = DAG.getUNDEF(MaskEltVT); - - SDValue ShuffleMask = DAG.getNode(ISD::BUILD_VECTOR, dl, MaskVT, - &MaskVec[0], MaskVec.size()); + ShuffleMask[Val2Elts[i]] = NumElems; // If the target supports SCALAR_TO_VECTOR and this shuffle mask, use it. if (TLI.isOperationLegalOrCustom(ISD::SCALAR_TO_VECTOR, VT) && - isShuffleLegal(VT, ShuffleMask)) { + TLI.isShuffleMaskLegal(ShuffleMask, VT)) { Val1 = DAG.getNode(ISD::SCALAR_TO_VECTOR, dl, VT, Val1); Val2 = DAG.getNode(ISD::SCALAR_TO_VECTOR, dl, VT, Val2); - SDValue Ops[] = { Val1, Val2, ShuffleMask }; - - // Return shuffle(LoValVec, HiValVec, <0,1,0,1>) - return DAG.getNode(ISD::VECTOR_SHUFFLE, dl, VT, Ops, 3); + return DAG.getVectorShuffle(VT, dl, Val1, Val2, &ShuffleMask[0]); } } @@ -8066,36 +8020,19 @@ SDValue SelectionDAGLegalize::WidenVectorOp(SDValue Op, MVT WidenVT) { case ISD::VECTOR_SHUFFLE: { SDValue Tmp1 = WidenVectorOp(Node->getOperand(0), WidenVT); SDValue Tmp2 = WidenVectorOp(Node->getOperand(1), WidenVT); - // VECTOR_SHUFFLE 3rd operand must be a constant build vector that is - // used as permutation array. We build the vector here instead of widening - // because we don't want to legalize and have it turned to something else. - SDValue PermOp = Node->getOperand(2); - SDValueVector NewOps; - MVT PVT = PermOp.getValueType().getVectorElementType(); + ShuffleVectorSDNode *SVOp = cast<ShuffleVectorSDNode>(Node); + SmallVector<int, 8> NewMask; for (unsigned i = 0; i < NumElts; ++i) { - if (PermOp.getOperand(i).getOpcode() == ISD::UNDEF) { - NewOps.push_back(PermOp.getOperand(i)); - } else { - unsigned Idx = - cast<ConstantSDNode>(PermOp.getOperand(i))->getZExtValue(); - if (Idx < NumElts) { - NewOps.push_back(PermOp.getOperand(i)); - } - else { - NewOps.push_back(DAG.getConstant(Idx + NewNumElts - NumElts, - PermOp.getOperand(i).getValueType())); - } - } - } - for (unsigned i = NumElts; i < NewNumElts; ++i) { - NewOps.push_back(DAG.getUNDEF(PVT)); + int Idx = SVOp->getMaskElt(i); + if (Idx < (int)NumElts) + NewMask.push_back(Idx); + else + NewMask.push_back(Idx + NewNumElts - NumElts); } - - SDValue Tmp3 = DAG.getNode(ISD::BUILD_VECTOR, dl, - MVT::getVectorVT(PVT, NewOps.size()), - &NewOps[0], NewOps.size()); - - Result = DAG.getNode(ISD::VECTOR_SHUFFLE, dl, WidenVT, Tmp1, Tmp2, Tmp3); + for (unsigned i = NumElts; i < NewNumElts; ++i) + NewMask.push_back(-1); + + Result = DAG.getVectorShuffle(WidenVT, dl, Tmp1, Tmp2, &NewMask[0]); break; } case ISD::LOAD: { diff --git a/lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp b/lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp index eec328f..fac4d99 100644 --- a/lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp +++ b/lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp @@ -761,6 +761,7 @@ void DAGTypeLegalizer::SplitVecRes_VECTOR_SHUFFLE(SDNode *N, SDValue &Lo, SDValue &Hi) { // The low and high parts of the original input give four input vectors. SDValue Inputs[4]; + ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N); DebugLoc dl = N->getDebugLoc(); GetSplitVector(N->getOperand(0), Inputs[0], Inputs[1]); GetSplitVector(N->getOperand(1), Inputs[2], Inputs[3]); @@ -772,10 +773,7 @@ void DAGTypeLegalizer::SplitVecRes_VECTOR_SHUFFLE(SDNode *N, SDValue &Lo, // If Lo or Hi uses elements from at most two of the four input vectors, then // express it as a vector shuffle of those two inputs. Otherwise extract the // input elements by hand and construct the Lo/Hi output using a BUILD_VECTOR. - SDValue Mask = N->getOperand(2); - MVT IdxVT = Mask.getValueType().getVectorElementType(); - SmallVector<SDValue, 16> Ops; - Ops.reserve(NewElts); + SmallVector<int, 16> Ops; for (unsigned High = 0; High < 2; ++High) { SDValue &Output = High ? Hi : Lo; @@ -787,18 +785,15 @@ void DAGTypeLegalizer::SplitVecRes_VECTOR_SHUFFLE(SDNode *N, SDValue &Lo, unsigned FirstMaskIdx = High * NewElts; bool useBuildVector = false; for (unsigned MaskOffset = 0; MaskOffset < NewElts; ++MaskOffset) { - SDValue Arg = Mask.getOperand(FirstMaskIdx + MaskOffset); - // The mask element. This indexes into the input. - unsigned Idx = Arg.getOpcode() == ISD::UNDEF ? - -1U : cast<ConstantSDNode>(Arg)->getZExtValue(); + int Idx = SVN->getMaskElt(FirstMaskIdx + MaskOffset); // The input vector this mask element indexes into. - unsigned Input = Idx / NewElts; + unsigned Input = (unsigned)Idx / NewElts; if (Input >= array_lengthof(Inputs)) { // The mask element does not index into any input vector. - Ops.push_back(DAG.getUNDEF(IdxVT)); + Ops.push_back(-1); continue; } @@ -826,27 +821,24 @@ void DAGTypeLegalizer::SplitVecRes_VECTOR_SHUFFLE(SDNode *N, SDValue &Lo, } // Add the mask index for the new shuffle vector. - Ops.push_back(DAG.getConstant(Idx + OpNo * NewElts, IdxVT)); + Ops.push_back(Idx + OpNo * NewElts); } if (useBuildVector) { MVT EltVT = NewVT.getVectorElementType(); - Ops.clear(); + SmallVector<SDValue, 16> SVOps; // Extract the input elements by hand. for (unsigned MaskOffset = 0; MaskOffset < NewElts; ++MaskOffset) { - SDValue Arg = Mask.getOperand(FirstMaskIdx + MaskOffset); - // The mask element. This indexes into the input. - unsigned Idx = Arg.getOpcode() == ISD::UNDEF ? - -1U : cast<ConstantSDNode>(Arg)->getZExtValue(); + int Idx = SVN->getMaskElt(FirstMaskIdx + MaskOffset); // The input vector this mask element indexes into. - unsigned Input = Idx / NewElts; + unsigned Input = (unsigned)Idx / NewElts; if (Input >= array_lengthof(Inputs)) { // The mask element is "undef" or indexes off the end of the input. - Ops.push_back(DAG.getUNDEF(EltVT)); + SVOps.push_back(DAG.getUNDEF(EltVT)); continue; } @@ -854,25 +846,22 @@ void DAGTypeLegalizer::SplitVecRes_VECTOR_SHUFFLE(SDNode *N, SDValue &Lo, Idx -= Input * NewElts; // Extract the vector element by hand. - Ops.push_back(DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, EltVT, - Inputs[Input], DAG.getIntPtrConstant(Idx))); + SVOps.push_back(DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, EltVT, + Inputs[Input], DAG.getIntPtrConstant(Idx))); } // Construct the Lo/Hi output using a BUILD_VECTOR. - Output = DAG.getNode(ISD::BUILD_VECTOR, dl, NewVT, &Ops[0], Ops.size()); + Output = DAG.getNode(ISD::BUILD_VECTOR,dl,NewVT, &SVOps[0], SVOps.size()); } else if (InputUsed[0] == -1U) { // No input vectors were used! The result is undefined. Output = DAG.getUNDEF(NewVT); } else { - // At least one input vector was used. Create a new shuffle vector. - SDValue NewMask = DAG.getNode(ISD::BUILD_VECTOR, dl, - MVT::getVectorVT(IdxVT, Ops.size()), - &Ops[0], Ops.size()); SDValue Op0 = Inputs[InputUsed[0]]; // If only one input was used, use an undefined vector for the other. SDValue Op1 = InputUsed[1] == -1U ? DAG.getUNDEF(NewVT) : Inputs[InputUsed[1]]; - Output = DAG.getNode(ISD::VECTOR_SHUFFLE, dl, NewVT, Op0, Op1, NewMask); + // At least one input vector was used. Create a new shuffle vector. + Output = DAG.getVectorShuffle(NewVT, dl, Op0, Op1, &Ops[0]); } Ops.clear(); @@ -1473,18 +1462,15 @@ SDValue DAGTypeLegalizer::WidenVecRes_CONCAT_VECTORS(SDNode *N) { if (NumOperands == 2) { // Replace concat of two operands with a shuffle. - MVT PtrVT = TLI.getPointerTy(); - SmallVector<SDValue, 16> MaskOps(WidenNumElts); + SmallVector<int, 16> MaskOps(WidenNumElts); for (unsigned i=0; i < WidenNumElts/2; ++i) { - MaskOps[i] = DAG.getConstant(i, PtrVT); - MaskOps[i+WidenNumElts/2] = DAG.getConstant(i+WidenNumElts, PtrVT); + MaskOps[i] = i; + MaskOps[i+WidenNumElts/2] = i+WidenNumElts; } - SDValue Mask = DAG.getNode(ISD::BUILD_VECTOR, dl, - MVT::getVectorVT(PtrVT, WidenNumElts), - &MaskOps[0], WidenNumElts); - return DAG.getNode(ISD::VECTOR_SHUFFLE, dl, WidenVT, - GetWidenedVector(N->getOperand(0)), - GetWidenedVector(N->getOperand(1)), Mask); + return DAG.getVectorShuffle(WidenVT, dl, + GetWidenedVector(N->getOperand(0)), + GetWidenedVector(N->getOperand(1)), + &MaskOps[0]); } } } @@ -1761,8 +1747,9 @@ SDValue DAGTypeLegalizer::WidenVecRes_UNDEF(SDNode *N) { } SDValue DAGTypeLegalizer::WidenVecRes_VECTOR_SHUFFLE(SDNode *N) { + ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N); MVT VT = N->getValueType(0); - unsigned NumElts = VT.getVectorNumElements(); + int NumElts = VT.getVectorNumElements(); DebugLoc dl = N->getDebugLoc(); MVT WidenVT = TLI.getTypeToTransformTo(VT); @@ -1772,28 +1759,17 @@ SDValue DAGTypeLegalizer::WidenVecRes_VECTOR_SHUFFLE(SDNode *N) { SDValue InOp2 = GetWidenedVector(N->getOperand(1)); // Adjust mask based on new input vector length. - SDValue Mask = N->getOperand(2); - SmallVector<SDValue, 16> MaskOps(WidenNumElts); - MVT IdxVT = Mask.getValueType().getVectorElementType(); - for (unsigned i = 0; i < NumElts; ++i) { - SDValue Arg = Mask.getOperand(i); - if (Arg.getOpcode() == ISD::UNDEF) - MaskOps[i] = Arg; - else { - unsigned Idx = cast<ConstantSDNode>(Arg)->getZExtValue(); - if (Idx < NumElts) - MaskOps[i] = Arg; - else - MaskOps[i] = DAG.getConstant(Idx - NumElts + WidenNumElts, IdxVT); - } + SmallVector<int, 16> NewMask; + for (int i = 0; i < NumElts; ++i) { + int Idx = SVN->getMaskElt(i); + if (Idx < NumElts) + NewMask.push_back(Idx); + else + NewMask.push_back(Idx - NumElts + WidenNumElts); } for (unsigned i = NumElts; i < WidenNumElts; ++i) - MaskOps[i] = DAG.getUNDEF(IdxVT); - SDValue NewMask = DAG.getNode(ISD::BUILD_VECTOR, dl, - MVT::getVectorVT(IdxVT, WidenNumElts), - &MaskOps[0], WidenNumElts); - - return DAG.getNode(ISD::VECTOR_SHUFFLE, dl, WidenVT, InOp1, InOp2, NewMask); + NewMask.push_back(-1); + return DAG.getVectorShuffle(WidenVT, dl, InOp1, InOp2, &NewMask[0]); } SDValue DAGTypeLegalizer::WidenVecRes_VSETCC(SDNode *N) { diff --git a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp index 954b842..7c9a001 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp @@ -456,6 +456,13 @@ static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) { ID.AddInteger(AT->getRawSubclassData()); break; } + case ISD::VECTOR_SHUFFLE: { + const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N); + for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements(); + i != e; ++i) + ID.AddInteger(SVN->getMaskElt(i)); + break; + } } // end switch (N->getOpcode()) } @@ -765,9 +772,9 @@ void SelectionDAG::VerifyNode(SDNode *N) { MVT EltVT = N->getValueType(0).getVectorElementType(); for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) assert((I->getValueType() == EltVT || - (EltVT.isInteger() && I->getValueType().isInteger() && - EltVT.bitsLE(I->getValueType()))) && - "Wrong operand type!"); + (EltVT.isInteger() && I->getValueType().isInteger() && + EltVT.bitsLE(I->getValueType()))) && + "Wrong operand type!"); break; } } @@ -1126,6 +1133,110 @@ SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) { return SDValue(CondCodeNodes[Cond], 0); } +static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) { + std::swap(N1, N2); + int NElts = M.size(); + for (int i = 0; i != NElts; ++i) { + if (M[i] >= NElts) + M[i] -= NElts; + else if (M[i] >= 0) + M[i] += NElts; + } +} + +SDValue SelectionDAG::getVectorShuffle(MVT VT, DebugLoc dl, SDValue N1, + SDValue N2, const int *Mask) { + assert(N1.getValueType() == N2.getValueType() && "Invalid VECTOR_SHUFFLE"); + assert(VT.isVector() && N1.getValueType().isVector() && + "Vector Shuffle VTs must be a vectors"); + assert(VT.getVectorElementType() == N1.getValueType().getVectorElementType() + && "Vector Shuffle VTs must have same element type"); + + // Canonicalize shuffle undef, undef -> undef + if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF) + return N1; + + // Validate that all indices in Mask are within the range of the elements + // input to the shuffle. + int NElts = VT.getVectorNumElements(); + SmallVector<int, 8> MaskVec; + for (int i = 0; i != NElts; ++i) { + if (Mask[i] >= (NElts * 2)) { + assert(0 && "Index out of range"); + return SDValue(); + } + MaskVec.push_back(Mask[i]); + } + + // Canonicalize shuffle v, v -> v, undef + if (N1 == N2) { + N2 = getUNDEF(VT); + for (int i = 0; i != NElts; ++i) + if (MaskVec[i] >= NElts) MaskVec[i] -= NElts; + } + + // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask. + if (N1.getOpcode() == ISD::UNDEF) + commuteShuffle(N1, N2, MaskVec); + + // Canonicalize all index into lhs, -> shuffle lhs, undef + // Canonicalize all index into rhs, -> shuffle rhs, undef + bool AllLHS = true, AllRHS = true; + bool N2Undef = N2.getOpcode() == ISD::UNDEF; + for (int i = 0; i != NElts; ++i) { + if (MaskVec[i] >= NElts) { + if (N2Undef) + MaskVec[i] = -1; + else + AllLHS = false; + } else if (MaskVec[i] >= 0) { + AllRHS = false; + } + } + if (AllLHS && AllRHS) + return getUNDEF(VT); + if (AllLHS) + N2 = getUNDEF(VT); + if (AllRHS) { + N1 = getUNDEF(VT); + commuteShuffle(N1, N2, MaskVec); + } + + // If Identity shuffle, or all shuffle in to undef, return that node. + bool AllUndef = true; + bool Identity = true; + for (int i = 0; i < NElts; ++i) { + if (MaskVec[i] >= 0 && MaskVec[i] != i) Identity = false; + if (MaskVec[i] >= 0) AllUndef = false; + } + if (Identity) + return N1; + if (AllUndef) + return getUNDEF(VT); + + FoldingSetNodeID ID; + SDValue Ops[2] = { N1, N2 }; + AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops, 2); + for (int i = 0; i != NElts; ++i) + ID.AddInteger(MaskVec[i]); + + void* IP = 0; + if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) + return SDValue(E, 0); + + // Allocate the mask array for the node out of the BumpPtrAllocator, since + // SDNode doesn't have access to it. This memory will be "leaked" when + // the node is deallocated, but recovered when the NodeAllocator is released. + int *MaskAlloc = OperandAllocator.Allocate<int>(NElts); + memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int)); + + ShuffleVectorSDNode *N = NodeAllocator.Allocate<ShuffleVectorSDNode>(); + new (N) ShuffleVectorSDNode(VT, dl, N1, N2, MaskAlloc); + CSEMap.InsertNode(N, IP); + AllNodes.push_back(N); + return SDValue(N, 0); +} + SDValue SelectionDAG::getConvertRndSat(MVT VT, DebugLoc dl, SDValue Val, SDValue DTy, SDValue STy, SDValue Rnd, SDValue Sat, @@ -2087,19 +2198,18 @@ bool SelectionDAG::isVerifiedDebugInfoDesc(SDValue Op) const { SDValue SelectionDAG::getShuffleScalarElt(const SDNode *N, unsigned i) { MVT VT = N->getValueType(0); DebugLoc dl = N->getDebugLoc(); - SDValue PermMask = N->getOperand(2); - SDValue Idx = PermMask.getOperand(i); - if (Idx.getOpcode() == ISD::UNDEF) + const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N); + int Index = SVN->getMaskElt(i); + if (Index < 0) return getUNDEF(VT.getVectorElementType()); - unsigned Index = cast<ConstantSDNode>(Idx)->getZExtValue(); - unsigned NumElems = PermMask.getNumOperands(); + int NumElems = VT.getVectorNumElements(); SDValue V = (Index < NumElems) ? N->getOperand(0) : N->getOperand(1); Index %= NumElems; if (V.getOpcode() == ISD::BIT_CONVERT) { V = V.getOperand(0); MVT VVT = V.getValueType(); - if (!VVT.isVector() || VVT.getVectorNumElements() != NumElems) + if (!VVT.isVector() || VVT.getVectorNumElements() != (unsigned)NumElems) return SDValue(); } if (V.getOpcode() == ISD::SCALAR_TO_VECTOR) @@ -2794,12 +2904,7 @@ SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, MVT VT, } break; case ISD::VECTOR_SHUFFLE: - assert(N1.getValueType() == N2.getValueType() && - N1.getValueType().isVector() && - VT.isVector() && N3.getValueType().isVector() && - N3.getOpcode() == ISD::BUILD_VECTOR && - VT.getVectorNumElements() == N3.getNumOperands() && - "Illegal VECTOR_SHUFFLE node!"); + assert(0 && "should use getVectorShuffle constructor!"); break; case ISD::BIT_CONVERT: // Fold bit_convert nodes from a type to themselves. @@ -5323,14 +5428,15 @@ void SDNode::print_types(raw_ostream &OS, const SelectionDAG *G) const { void SDNode::print_details(raw_ostream &OS, const SelectionDAG *G) const { if (!isTargetOpcode() && getOpcode() == ISD::VECTOR_SHUFFLE) { - SDNode *Mask = getOperand(2).getNode(); + const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(this); OS << "<"; - for (unsigned i = 0, e = Mask->getNumOperands(); i != e; ++i) { + for (unsigned i = 0, e = ValueList[0].getVectorNumElements(); i != e; ++i) { + int Idx = SVN->getMaskElt(i); if (i) OS << ","; - if (Mask->getOperand(i).getOpcode() == ISD::UNDEF) + if (Idx < 0) OS << "u"; else - OS << cast<ConstantSDNode>(Mask->getOperand(i))->getZExtValue(); + OS << Idx; } OS << ">"; } @@ -5611,3 +5717,13 @@ bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue, SplatBitSize = sz; return true; } + +bool ShuffleVectorSDNode::isSplatMask(const int *Mask, MVT VT) { + int Idx = -1; + for (unsigned i = 0, e = VT.getVectorNumElements(); i != e; ++i) { + if (Idx < 0) Idx = Mask[i]; + if (Mask[i] >= 0 && Mask[i] != Idx) + return false; + } + return true; +} diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGBuild.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGBuild.cpp index 3e6da24..aac4b65 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAGBuild.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAGBuild.cpp @@ -870,8 +870,7 @@ SDValue SelectionDAGLowering::getValue(const Value *V) { if (ConstantFP *CFP = dyn_cast<ConstantFP>(C)) return N = DAG.getConstantFP(*CFP, VT); - if (isa<UndefValue>(C) && !isa<VectorType>(V->getType()) && - !V->getType()->isAggregateType()) + if (isa<UndefValue>(C) && !V->getType()->isAggregateType()) return N = DAG.getUNDEF(VT); if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) { @@ -925,14 +924,11 @@ SDValue SelectionDAGLowering::getValue(const Value *V) { for (unsigned i = 0; i != NumElements; ++i) Ops.push_back(getValue(CP->getOperand(i))); } else { - assert((isa<ConstantAggregateZero>(C) || isa<UndefValue>(C)) && - "Unknown vector constant!"); + assert(isa<ConstantAggregateZero>(C) && "Unknown vector constant!"); MVT EltVT = TLI.getValueType(VecTy->getElementType()); SDValue Op; - if (isa<UndefValue>(C)) - Op = DAG.getUNDEF(EltVT); - else if (EltVT.isFloatingPoint()) + if (EltVT.isFloatingPoint()) Op = DAG.getConstantFP(0, EltVT); else Op = DAG.getConstant(0, EltVT); @@ -2435,37 +2431,42 @@ void SelectionDAGLowering::visitExtractElement(User &I) { // Utility for visitShuffleVector - Returns true if the mask is mask starting // from SIndx and increasing to the element length (undefs are allowed). -static bool SequentialMask(SDValue Mask, unsigned SIndx) { - unsigned MaskNumElts = Mask.getNumOperands(); - for (unsigned i = 0; i != MaskNumElts; ++i) { - if (Mask.getOperand(i).getOpcode() != ISD::UNDEF) { - unsigned Idx = cast<ConstantSDNode>(Mask.getOperand(i))->getZExtValue(); - if (Idx != i + SIndx) - return false; - } - } +static bool SequentialMask(SmallVectorImpl<int> &Mask, int SIndx) { + int MaskNumElts = Mask.size(); + for (int i = 0; i != MaskNumElts; ++i) + if ((Mask[i] >= 0) && (Mask[i] != i + SIndx)) + return false; return true; } void SelectionDAGLowering::visitShuffleVector(User &I) { + SmallVector<int, 8> Mask; SDValue Src1 = getValue(I.getOperand(0)); SDValue Src2 = getValue(I.getOperand(1)); - SDValue Mask = getValue(I.getOperand(2)); + // Convert the ConstantVector mask operand into an array of ints, with -1 + // representing undef values. + SmallVector<Constant*, 8> MaskElts; + cast<Constant>(I.getOperand(2))->getVectorElements(MaskElts); + int MaskNumElts = MaskElts.size(); + for (int i = 0; i != MaskNumElts; ++i) { + if (isa<UndefValue>(MaskElts[i])) + Mask.push_back(-1); + else + Mask.push_back(cast<ConstantInt>(MaskElts[i])->getSExtValue()); + } + MVT VT = TLI.getValueType(I.getType()); MVT SrcVT = Src1.getValueType(); - int MaskNumElts = Mask.getNumOperands(); int SrcNumElts = SrcVT.getVectorNumElements(); if (SrcNumElts == MaskNumElts) { - setValue(&I, DAG.getNode(ISD::VECTOR_SHUFFLE, getCurDebugLoc(), - VT, Src1, Src2, Mask)); + setValue(&I, DAG.getVectorShuffle(VT, getCurDebugLoc(), Src1, Src2, + &Mask[0])); return; } // Normalize the shuffle vector since mask and vector length don't match. - MVT MaskEltVT = Mask.getValueType().getVectorElementType(); - if (SrcNumElts < MaskNumElts && MaskNumElts % SrcNumElts == 0) { // Mask is longer than the source vectors and is a multiple of the source // vectors. We can use concatenate vector to make the mask and vectors @@ -2479,44 +2480,33 @@ void SelectionDAGLowering::visitShuffleVector(User &I) { // Pad both vectors with undefs to make them the same length as the mask. unsigned NumConcat = MaskNumElts / SrcNumElts; + bool Src1U = Src1.getOpcode() == ISD::UNDEF; + bool Src2U = Src2.getOpcode() == ISD::UNDEF; SDValue UndefVal = DAG.getUNDEF(SrcVT); - SDValue* MOps1 = new SDValue[NumConcat]; - SDValue* MOps2 = new SDValue[NumConcat]; + SmallVector<SDValue, 8> MOps1(NumConcat, UndefVal); + SmallVector<SDValue, 8> MOps2(NumConcat, UndefVal); MOps1[0] = Src1; MOps2[0] = Src2; - for (unsigned i = 1; i != NumConcat; ++i) { - MOps1[i] = UndefVal; - MOps2[i] = UndefVal; - } - Src1 = DAG.getNode(ISD::CONCAT_VECTORS, getCurDebugLoc(), - VT, MOps1, NumConcat); - Src2 = DAG.getNode(ISD::CONCAT_VECTORS, getCurDebugLoc(), - VT, MOps2, NumConcat); - - delete [] MOps1; - delete [] MOps2; + + Src1 = Src1U ? DAG.getUNDEF(VT) : DAG.getNode(ISD::CONCAT_VECTORS, + getCurDebugLoc(), VT, + &MOps1[0], NumConcat); + Src2 = Src2U ? DAG.getUNDEF(VT) : DAG.getNode(ISD::CONCAT_VECTORS, + getCurDebugLoc(), VT, + &MOps2[0], NumConcat); // Readjust mask for new input vector length. - SmallVector<SDValue, 8> MappedOps; + SmallVector<int, 8> MappedOps; for (int i = 0; i != MaskNumElts; ++i) { - if (Mask.getOperand(i).getOpcode() == ISD::UNDEF) { - MappedOps.push_back(Mask.getOperand(i)); - } else { - int Idx = cast<ConstantSDNode>(Mask.getOperand(i))->getZExtValue(); - if (Idx < SrcNumElts) - MappedOps.push_back(DAG.getConstant(Idx, MaskEltVT)); - else - MappedOps.push_back(DAG.getConstant(Idx + MaskNumElts - SrcNumElts, - MaskEltVT)); - } + int Idx = Mask[i]; + if (Idx < SrcNumElts) + MappedOps.push_back(Idx); + else + MappedOps.push_back(Idx + MaskNumElts - SrcNumElts); } - Mask = DAG.getNode(ISD::BUILD_VECTOR, getCurDebugLoc(), - Mask.getValueType(), - &MappedOps[0], MappedOps.size()); - - setValue(&I, DAG.getNode(ISD::VECTOR_SHUFFLE, getCurDebugLoc(), - VT, Src1, Src2, Mask)); + setValue(&I, DAG.getVectorShuffle(VT, getCurDebugLoc(), Src1, Src2, + &MappedOps[0])); return; } @@ -2541,20 +2531,19 @@ void SelectionDAGLowering::visitShuffleVector(User &I) { int MaxRange[2] = {-1, -1}; for (int i = 0; i != MaskNumElts; ++i) { - SDValue Arg = Mask.getOperand(i); - if (Arg.getOpcode() != ISD::UNDEF) { - assert(isa<ConstantSDNode>(Arg) && "Invalid VECTOR_SHUFFLE mask!"); - int Idx = cast<ConstantSDNode>(Arg)->getZExtValue(); - int Input = 0; - if (Idx >= SrcNumElts) { - Input = 1; - Idx -= SrcNumElts; - } - if (Idx > MaxRange[Input]) - MaxRange[Input] = Idx; - if (Idx < MinRange[Input]) - MinRange[Input] = Idx; + int Idx = Mask[i]; + int Input = 0; + if (Idx < 0) + continue; + + if (Idx >= SrcNumElts) { + Input = 1; + Idx -= SrcNumElts; } + if (Idx > MaxRange[Input]) + MaxRange[Input] = Idx; + if (Idx < MinRange[Input]) + MinRange[Input] = Idx; } // Check if the access is smaller than the vector size and can we find @@ -2596,26 +2585,18 @@ void SelectionDAGLowering::visitShuffleVector(User &I) { } } // Calculate new mask. - SmallVector<SDValue, 8> MappedOps; + SmallVector<int, 8> MappedOps; for (int i = 0; i != MaskNumElts; ++i) { - SDValue Arg = Mask.getOperand(i); - if (Arg.getOpcode() == ISD::UNDEF) { - MappedOps.push_back(Arg); - } else { - int Idx = cast<ConstantSDNode>(Arg)->getZExtValue(); - if (Idx < SrcNumElts) - MappedOps.push_back(DAG.getConstant(Idx - StartIdx[0], MaskEltVT)); - else { - Idx = Idx - SrcNumElts - StartIdx[1] + MaskNumElts; - MappedOps.push_back(DAG.getConstant(Idx, MaskEltVT)); - } - } + int Idx = Mask[i]; + if (Idx < 0) + MappedOps.push_back(Idx); + else if (Idx < SrcNumElts) + MappedOps.push_back(Idx - StartIdx[0]); + else + MappedOps.push_back(Idx - SrcNumElts - StartIdx[1] + MaskNumElts); } - Mask = DAG.getNode(ISD::BUILD_VECTOR, getCurDebugLoc(), - Mask.getValueType(), - &MappedOps[0], MappedOps.size()); - setValue(&I, DAG.getNode(ISD::VECTOR_SHUFFLE, getCurDebugLoc(), - VT, Src1, Src2, Mask)); + setValue(&I, DAG.getVectorShuffle(VT, getCurDebugLoc(), Src1, Src2, + &MappedOps[0])); return; } } @@ -2627,12 +2608,10 @@ void SelectionDAGLowering::visitShuffleVector(User &I) { MVT PtrVT = TLI.getPointerTy(); SmallVector<SDValue,8> Ops; for (int i = 0; i != MaskNumElts; ++i) { - SDValue Arg = Mask.getOperand(i); - if (Arg.getOpcode() == ISD::UNDEF) { + if (Mask[i] < 0) { Ops.push_back(DAG.getUNDEF(EltVT)); } else { - assert(isa<ConstantSDNode>(Arg) && "Invalid VECTOR_SHUFFLE mask!"); - int Idx = cast<ConstantSDNode>(Arg)->getZExtValue(); + int Idx = Mask[i]; if (Idx < SrcNumElts) Ops.push_back(DAG.getNode(ISD::EXTRACT_VECTOR_ELT, getCurDebugLoc(), EltVT, Src1, DAG.getConstant(Idx, PtrVT))); |