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

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)));