Revert 69952. Causes testsuite failures on linux x86-64.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69967 91177308-0d34-0410-b5e6-96231b3b80d8

5 files changed, 447 insertions, 353 deletions

diff --git a/lib/CodeGen/SelectionDAG/DAGCombiner.cpp b/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
index 40807d8..72b3e36 100644
--- a/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
+++ b/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
@@ -5098,21 +5098,7 @@ 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();
 }
 
@@ -5174,8 +5160,9 @@ SDValue DAGCombiner::visitEXTRACT_VECTOR_ELT(SDNode *N) {
       // to examine the mask.
       if (BCNumEltsChanged)
         return SDValue();
-      int Idx = cast<ShuffleVectorSDNode>(InVec)->getMask()[Elt];
-      int NumElems = InVec.getValueType().getVectorNumElements();
+      unsigned Idx = cast<ConstantSDNode>(InVec.getOperand(2).
+                                          getOperand(Elt))->getZExtValue();
+      unsigned NumElems = InVec.getOperand(2).getNumOperands();
       InVec = (Idx < NumElems) ? InVec.getOperand(0) : InVec.getOperand(1);
       if (InVec.getOpcode() == ISD::BIT_CONVERT)
         InVec = InVec.getOperand(0);
@@ -5222,6 +5209,7 @@ 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
@@ -5264,36 +5252,56 @@ SDValue DAGCombiner::visitBUILD_VECTOR(SDNode *N) {
   }
 
   // If everything is good, we can make a shuffle operation.
+  MVT IndexVT = MVT::i32;
   if (VecIn1.getNode()) {
-    SmallVector<int, 8> Mask;
+    SmallVector<SDValue, 8> BuildVecIndices;
     for (unsigned i = 0; i != NumInScalars; ++i) {
       if (N->getOperand(i).getOpcode() == ISD::UNDEF) {
-        Mask.push_back(-1);
+        BuildVecIndices.push_back(DAG.getUNDEF(IndexVT));
         continue;
       }
 
-      // If extracting from the first vector, just use the index directly.
       SDValue Extract = N->getOperand(i);
+
+      // If extracting from the first vector, just use the index directly.
       SDValue ExtVal = Extract.getOperand(1);
       if (Extract.getOperand(0) == VecIn1) {
-        Mask.push_back(cast<ConstantSDNode>(ExtVal)->getZExtValue());
+        if (ExtVal.getValueType() == IndexVT)
+          BuildVecIndices.push_back(ExtVal);
+        else {
+          unsigned Idx = cast<ConstantSDNode>(ExtVal)->getZExtValue();
+          BuildVecIndices.push_back(DAG.getConstant(Idx, IndexVT));
+        }
         continue;
       }
 
       // Otherwise, use InIdx + VecSize
       unsigned Idx = cast<ConstantSDNode>(ExtVal)->getZExtValue();
-      Mask.push_back(Idx+NumInScalars);
+      BuildVecIndices.push_back(DAG.getConstant(Idx+NumInScalars, IndexVT));
     }
 
     // Add count and size info.
-    if (!TLI.isTypeLegal(VT) && LegalTypes)
+    MVT BuildVecVT = MVT::getVectorVT(IndexVT, NumElts);
+    if (!TLI.isTypeLegal(BuildVecVT) && LegalTypes)
       return SDValue();
 
     // Return the new VECTOR_SHUFFLE node.
-    SDValue Ops[2];
+    SDValue Ops[5];
     Ops[0] = VecIn1;
-    Ops[1] = VecIn2.getNode() ? VecIn2 : DAG.getUNDEF(VT);
-    return DAG.getVectorShuffle(VT, N->getDebugLoc(), Ops[0], Ops[1], &Mask[0]);
+    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);
   }
 
   return SDValue();
@@ -5313,10 +5321,8 @@ SDValue DAGCombiner::visitCONCAT_VECTORS(SDNode *N) {
 }
 
 SDValue DAGCombiner::visitVECTOR_SHUFFLE(SDNode *N) {
-  return SDValue();
-  
-  MVT VT = N->getValueType(0);
-  unsigned NumElts = VT.getVectorNumElements();
+  SDValue ShufMask = N->getOperand(2);
+  unsigned NumElts = ShufMask.getNumOperands();
 
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
@@ -5324,13 +5330,60 @@ SDValue DAGCombiner::visitVECTOR_SHUFFLE(SDNode *N) {
   assert(N0.getValueType().getVectorNumElements() == NumElts &&
         "Vector shuffle must be normalized in DAG");
 
-  // FIXME: implement canonicalizations from DAG.getVectorShuffle()
+  // 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);
 
   // If it is a splat, check if the argument vector is a build_vector with
   // all scalar elements the same.
-  if (cast<ShuffleVectorSDNode>(N)->isSplat()) {
+  if (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
@@ -5344,7 +5397,6 @@ 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;
@@ -5369,6 +5421,38 @@ 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();
 }
 
@@ -5377,42 +5461,52 @@ 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) {
-      SmallVector<int, 8> Indices;
-      unsigned NumElts = RHS.getNumOperands();
+      std::vector<SDValue> IdxOps;
+      unsigned NumOps = RHS.getNumOperands();
+      unsigned NumElts = NumOps;
       for (unsigned i = 0; i != NumElts; ++i) {
         SDValue Elt = RHS.getOperand(i);
         if (!isa<ConstantSDNode>(Elt))
           return SDValue();
         else if (cast<ConstantSDNode>(Elt)->isAllOnesValue())
-          Indices.push_back(i);
+          IdxOps.push_back(DAG.getIntPtrConstant(i));
         else if (cast<ConstantSDNode>(Elt)->isNullValue())
-          Indices.push_back(NumElts);
+          IdxOps.push_back(DAG.getIntPtrConstant(NumElts));
         else
           return SDValue();
       }
 
       // Let's see if the target supports this vector_shuffle.
-      MVT RVT = RHS.getValueType();
-      if (!TLI.isVectorClearMaskLegal(&Indices[0], RVT))
+      if (!TLI.isVectorClearMaskLegal(IdxOps, TLI.getPointerTy(), DAG))
         return SDValue();
 
       // Return the new VECTOR_SHUFFLE node.
-      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);
+      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;
     }
   }
 
diff --git a/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp b/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
index fed2b02..5ea1ce3 100644
--- a/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
@@ -267,10 +267,16 @@ private:
                             bool isVolatile, SDValue ValOp,
                             unsigned StWidth, DebugLoc dl);
 
-  /// 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, 
-                         const int *Mask) const;
+  /// 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;
 
   bool LegalizeAllNodesNotLeadingTo(SDNode *N, SDNode *Dest,
                                     SmallPtrSet<SDNode*, 32> &NodesLeadingTo);
@@ -313,35 +319,50 @@ private:
 };
 }
 
-/// 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, 
-                                             const 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);
-  
-  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);
+/// 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());
     }
+    VT = NVT;
+    break;
   }
-  assert((int)NewMask.size() == NumDestElts && "Non-integer NumEltsGrowth?");
-  assert(TLI.isShuffleMaskLegal(&Mask[0], NVT) && "Shuffle not legal?");
-  return DAG.getVectorShuffle(NVT, dl, N1, N2, &NewMask[0]);
+  }
+  return TLI.isShuffleMaskLegal(Mask, VT) ? Mask.getNode() : 0;
 }
 
 SelectionDAGLegalize::SelectionDAGLegalize(SelectionDAG &dag,
@@ -1631,15 +1652,25 @@ 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<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]);
+          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);
           Result = LegalizeOp(Result);
           break;
         }
@@ -1677,14 +1708,13 @@ SDValue SelectionDAGLegalize::LegalizeOp(SDValue Op) {
   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);
+    Result = DAG.UpdateNodeOperands(Result, Tmp1, Tmp2, Node->getOperand(2));
 
     // Allow targets to custom lower the SHUFFLEs they support.
     switch (TLI.getOperationAction(ISD::VECTOR_SHUFFLE, Result.getValueType())){
     default: assert(0 && "Unknown operation action!");
     case TargetLowering::Legal:
-      assert(TLI.isShuffleMaskLegal(cast<ShuffleVectorSDNode>(Node)->getMask(),
-                                    Result.getValueType()) &&
+      assert(isShuffleLegal(Result.getValueType(), Node->getOperand(2)) &&
              "vector shuffle should not be created if not legal!");
       break;
     case TargetLowering::Custom:
@@ -1698,21 +1728,23 @@ SDValue SelectionDAGLegalize::LegalizeOp(SDValue Op) {
       MVT VT = Node->getValueType(0);
       MVT EltVT = VT.getVectorElementType();
       MVT PtrVT = TLI.getPointerTy();
-      const int *Mask = cast<ShuffleVectorSDNode>(Node)->getMask();
-      int NumElems = VT.getVectorNumElements();
+      SDValue Mask = Node->getOperand(2);
+      unsigned NumElems = Mask.getNumOperands();
       SmallVector<SDValue, 8> Ops;
-      for (int i = 0; i != NumElems; ++i) {
-        if (Mask[i] < 0) {
+      for (unsigned i = 0; i != NumElems; ++i) {
+        SDValue Arg = Mask.getOperand(i);
+        if (Arg.getOpcode() == ISD::UNDEF) {
           Ops.push_back(DAG.getUNDEF(EltVT));
-          continue;
+        } 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)));
         }
-        int Idx = Mask[i];
-        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)));
       }
       Result = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, &Ops[0], Ops.size());
       break;
@@ -1727,8 +1759,9 @@ SDValue SelectionDAGLegalize::LegalizeOp(SDValue Op) {
       Tmp2 = DAG.getNode(ISD::BIT_CONVERT, dl, NVT, Tmp2);
 
       // Convert the shuffle mask to the right # elements.
-      Result = promoteShuffle(NVT, OVT, dl, Tmp1, Tmp2,
-                              cast<ShuffleVectorSDNode>(Node)->getMask());
+      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 = DAG.getNode(ISD::BIT_CONVERT, dl, OVT, Result);
       break;
     }
@@ -5457,7 +5490,6 @@ 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;
@@ -5514,17 +5546,21 @@ SDValue SelectionDAGLegalize::ExpandBUILD_VECTOR(SDNode *Node) {
 
   if (SplatValue.getNode()) {   // Splat of one value?
     // Build the shuffle constant vector: <0, 0, 0, 0>
-    SmallVector<int, 8> ZeroVec(NumElems, 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());
 
     // If the target supports VECTOR_SHUFFLE and this shuffle mask, use it.
-    if (TLI.isShuffleMaskLegal(&ZeroVec[0], Node->getValueType(0))) {
+    if (isShuffleLegal(VT, SplatMask)) {
       // 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.getVectorShuffle(VT, dl, LowValVec, DAG.getUNDEF(VT),
-                                  &ZeroVec[0]);
+      return DAG.getNode(ISD::VECTOR_SHUFFLE, dl, VT, LowValVec,
+                         DAG.getUNDEF(VT), SplatMask);
     }
   }
 
@@ -5546,25 +5582,35 @@ SDValue SelectionDAGLegalize::ExpandBUILD_VECTOR(SDNode *Node) {
       std::swap(Val1, Val2);
 
     // Build the shuffle constant vector: e.g. <0, 4, 0, 4>
-    SmallVector<int, 8> ShuffleMask(NumElems, -1);
+    MVT MaskVT = MVT::getIntVectorWithNumElements(NumElems);
+    MVT MaskEltVT = MaskVT.getVectorElementType();
+    std::vector<SDValue> MaskVec(NumElems);
 
     // Set elements of the shuffle mask for Val1.
     std::vector<unsigned> &Val1Elts = Values[Val1];
     for (unsigned i = 0, e = Val1Elts.size(); i != e; ++i)
-      ShuffleMask[Val1Elts[i]] = 0;
+      MaskVec[Val1Elts[i]] = DAG.getConstant(0, MaskEltVT);
 
     // 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)
-        ShuffleMask[Val2Elts[i]] = NumElems;
+        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());
 
     // If the target supports SCALAR_TO_VECTOR and this shuffle mask, use it.
     if (TLI.isOperationLegalOrCustom(ISD::SCALAR_TO_VECTOR, VT) &&
-        TLI.isShuffleMaskLegal(&ShuffleMask[0], VT)) {
+        isShuffleLegal(VT, ShuffleMask)) {
       Val1 = DAG.getNode(ISD::SCALAR_TO_VECTOR, dl, VT, Val1);
       Val2 = DAG.getNode(ISD::SCALAR_TO_VECTOR, dl, VT, Val2);
-      return DAG.getVectorShuffle(VT, dl, Val1, Val2, &ShuffleMask[0]);
+      SDValue Ops[] = { Val1, Val2, ShuffleMask };
+
+      // Return shuffle(LoValVec, HiValVec, <0,1,0,1>)
+      return DAG.getNode(ISD::VECTOR_SHUFFLE, dl, VT, Ops, 3);
     }
   }
 
@@ -8020,19 +8066,36 @@ 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);
-    const int *Mask = cast<ShuffleVectorSDNode>(Node)->getMask();
-    SmallVector<int, 8> NewMask;
+    // 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();
     for (unsigned i = 0; i < NumElts; ++i) {
-      int Idx = Mask[i];
-      if (Idx < (int)NumElts)
-        NewMask.push_back(Idx);
-      else
-        NewMask.push_back(Idx + NewNumElts - NumElts);
+      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)
-      NewMask.push_back(-1);
-    
-    Result = DAG.getVectorShuffle(WidenVT, dl, Tmp1, Tmp2, &NewMask[0]);
+    for (unsigned i = NumElts; i < NewNumElts; ++i) {
+      NewOps.push_back(DAG.getUNDEF(PVT));
+    }
+
+    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);
     break;
   }
   case ISD::LOAD: {
diff --git a/lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp b/lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp
index 116f300..eec328f 100644
--- a/lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp
+++ b/lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp
@@ -772,8 +772,10 @@ 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.
-  const int *Mask = cast<ShuffleVectorSDNode>(N)->getMask();
-  SmallVector<int, 16> Ops;
+  SDValue Mask = N->getOperand(2);
+  MVT IdxVT = Mask.getValueType().getVectorElementType();
+  SmallVector<SDValue, 16> Ops;
+  Ops.reserve(NewElts);
   for (unsigned High = 0; High < 2; ++High) {
     SDValue &Output = High ? Hi : Lo;
 
@@ -785,15 +787,18 @@ 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.
-      int Idx = Mask[FirstMaskIdx + MaskOffset];
+      unsigned Idx = Arg.getOpcode() == ISD::UNDEF ?
+        -1U : cast<ConstantSDNode>(Arg)->getZExtValue();
 
       // The input vector this mask element indexes into.
-      unsigned Input = (unsigned)Idx / NewElts;
+      unsigned Input = Idx / NewElts;
 
       if (Input >= array_lengthof(Inputs)) {
         // The mask element does not index into any input vector.
-        Ops.push_back(-1);
+        Ops.push_back(DAG.getUNDEF(IdxVT));
         continue;
       }
 
@@ -821,24 +826,27 @@ void DAGTypeLegalizer::SplitVecRes_VECTOR_SHUFFLE(SDNode *N, SDValue &Lo,
       }
 
       // Add the mask index for the new shuffle vector.
-      Ops.push_back(Idx + OpNo * NewElts);
+      Ops.push_back(DAG.getConstant(Idx + OpNo * NewElts, IdxVT));
     }
 
     if (useBuildVector) {
       MVT EltVT = NewVT.getVectorElementType();
-      SmallVector<SDValue, 16> SVOps;
+      Ops.clear();
 
       // 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.
-        int Idx = Mask[FirstMaskIdx + MaskOffset];
+        unsigned Idx = Arg.getOpcode() == ISD::UNDEF ?
+          -1U : cast<ConstantSDNode>(Arg)->getZExtValue();
 
         // The input vector this mask element indexes into.
-        unsigned Input = (unsigned)Idx / NewElts;
+        unsigned Input = Idx / NewElts;
 
         if (Input >= array_lengthof(Inputs)) {
           // The mask element is "undef" or indexes off the end of the input.
-          SVOps.push_back(DAG.getUNDEF(EltVT));
+          Ops.push_back(DAG.getUNDEF(EltVT));
           continue;
         }
 
@@ -846,22 +854,25 @@ void DAGTypeLegalizer::SplitVecRes_VECTOR_SHUFFLE(SDNode *N, SDValue &Lo,
         Idx -= Input * NewElts;
 
         // Extract the vector element by hand.
-        SVOps.push_back(DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, EltVT,
-                                    Inputs[Input], DAG.getIntPtrConstant(Idx)));
+        Ops.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, &SVOps[0], SVOps.size());
+      Output = DAG.getNode(ISD::BUILD_VECTOR, dl, NewVT, &Ops[0], Ops.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]];
-      // At least one input vector was used.  Create a new shuffle vector.
-      Output =  DAG.getVectorShuffle(NewVT, dl, Op0, Op1, &Ops[0]);
+      Output = DAG.getNode(ISD::VECTOR_SHUFFLE, dl, NewVT, Op0, Op1, NewMask);
     }
 
     Ops.clear();
@@ -1462,15 +1473,18 @@ SDValue DAGTypeLegalizer::WidenVecRes_CONCAT_VECTORS(SDNode *N) {
 
       if (NumOperands == 2) {
         // Replace concat of two operands with a shuffle.
-        SmallVector<int, 16> MaskOps(WidenNumElts);
+        MVT PtrVT = TLI.getPointerTy();
+        SmallVector<SDValue, 16> MaskOps(WidenNumElts);
         for (unsigned i=0; i < WidenNumElts/2; ++i) {
-          MaskOps[i] = i;
-          MaskOps[i+WidenNumElts/2] = i+WidenNumElts;
+          MaskOps[i] = DAG.getConstant(i, PtrVT);
+          MaskOps[i+WidenNumElts/2] = DAG.getConstant(i+WidenNumElts, PtrVT);
         }
-        return DAG.getVectorShuffle(WidenVT, dl, 
-                                    GetWidenedVector(N->getOperand(0)),
-                                    GetWidenedVector(N->getOperand(1)),
-                                    &MaskOps[0]);
+        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);
       }
     }
   }
@@ -1748,7 +1762,7 @@ SDValue DAGTypeLegalizer::WidenVecRes_UNDEF(SDNode *N) {
 
 SDValue DAGTypeLegalizer::WidenVecRes_VECTOR_SHUFFLE(SDNode *N) {
   MVT VT = N->getValueType(0);
-  int NumElts = VT.getVectorNumElements();
+  unsigned NumElts = VT.getVectorNumElements();
   DebugLoc dl = N->getDebugLoc();
 
   MVT WidenVT = TLI.getTypeToTransformTo(VT);
@@ -1758,17 +1772,28 @@ SDValue DAGTypeLegalizer::WidenVecRes_VECTOR_SHUFFLE(SDNode *N) {
   SDValue InOp2 = GetWidenedVector(N->getOperand(1));
 
   // Adjust mask based on new input vector length.
-  const int *Mask = cast<ShuffleVectorSDNode>(N)->getMask();
-  SmallVector<int, 16> NewMask;
-  for (int i = 0; i < NumElts; ++i) {
-    if (Mask[i] < NumElts)
-      NewMask.push_back(Mask[i]);
-    else
-      NewMask.push_back(Mask[i] - NumElts + WidenNumElts);
+  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);
+    }
   }
   for (unsigned i = NumElts; i < WidenNumElts; ++i)
-    NewMask.push_back(-1);
-  return DAG.getVectorShuffle(WidenVT, dl, InOp1, InOp2, &NewMask[0]);
+    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);
 }
 
 SDValue DAGTypeLegalizer::WidenVecRes_VSETCC(SDNode *N) {
diff --git a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
index 11d12eb..edd985e 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
@@ -456,13 +456,6 @@ static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
     ID.AddInteger(AT->getRawSubclassData());
     break;
   }
-  case ISD::VECTOR_SHUFFLE: {
-    const int *Mask = cast<ShuffleVectorSDNode>(N)->getMask();
-    for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements(); 
-         i != e; ++i)
-      ID.AddInteger(Mask[i]);
-    break;
-  }
   } // end switch (N->getOpcode())
 }
 
@@ -769,6 +762,12 @@ void SelectionDAG::VerifyNode(SDNode *N) {
     assert(N->getValueType(0).isVector() && "Wrong return type!");
     assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
            "Wrong number of operands!");
+    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!");
     break;
   }
   }
@@ -1127,110 +1126,6 @@ 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 the indices past in in Mask are within the range of 
-  // 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,
@@ -2192,18 +2087,19 @@ bool SelectionDAG::isVerifiedDebugInfoDesc(SDValue Op) const {
 SDValue SelectionDAG::getShuffleScalarElt(const SDNode *N, unsigned i) {
   MVT VT = N->getValueType(0);
   DebugLoc dl = N->getDebugLoc();
-  const int *PermMask = cast<ShuffleVectorSDNode>(N)->getMask();
-  if (PermMask[i] < 0)
+  SDValue PermMask = N->getOperand(2);
+  SDValue Idx = PermMask.getOperand(i);
+  if (Idx.getOpcode() == ISD::UNDEF)
     return getUNDEF(VT.getVectorElementType());
-  int Index = PermMask[i];
-  int NumElems = VT.getVectorNumElements();
+  unsigned Index = cast<ConstantSDNode>(Idx)->getZExtValue();
+  unsigned NumElems = PermMask.getNumOperands();
   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() != (unsigned)NumElems)
+    if (!VVT.isVector() || VVT.getVectorNumElements() != NumElems)
       return SDValue();
   }
   if (V.getOpcode() == ISD::SCALAR_TO_VECTOR)
@@ -2897,7 +2793,12 @@ SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, MVT VT,
     }
     break;
   case ISD::VECTOR_SHUFFLE:
-    assert(0 && "should use getVectorShuffle constructor!");
+    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!");
     break;
   case ISD::BIT_CONVERT:
     // Fold bit_convert nodes from a type to themselves.
@@ -5421,14 +5322,14 @@ 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) {
-    const int *Mask = cast<ShuffleVectorSDNode>(this)->getMask();
+    SDNode *Mask = getOperand(2).getNode();
     OS << "<";
-    for (unsigned i = 0, e = ValueList[0].getVectorNumElements(); i != e; ++i) {
+    for (unsigned i = 0, e = Mask->getNumOperands(); i != e; ++i) {
       if (i) OS << ",";
-      if (Mask[i] < 0)
+      if (Mask->getOperand(i).getOpcode() == ISD::UNDEF)
         OS << "u";
       else
-        OS << Mask[i];
+        OS << cast<ConstantSDNode>(Mask->getOperand(i))->getZExtValue();
     }
     OS << ">";
   }
@@ -5709,13 +5610,3 @@ 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 aac4b65..3e6da24 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAGBuild.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAGBuild.cpp
@@ -870,7 +870,8 @@ SDValue SelectionDAGLowering::getValue(const Value *V) {
     if (ConstantFP *CFP = dyn_cast<ConstantFP>(C))
       return N = DAG.getConstantFP(*CFP, VT);
 
-    if (isa<UndefValue>(C) && !V->getType()->isAggregateType())
+    if (isa<UndefValue>(C) && !isa<VectorType>(V->getType()) &&
+        !V->getType()->isAggregateType())
       return N = DAG.getUNDEF(VT);
 
     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
@@ -924,11 +925,14 @@ 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) && "Unknown vector constant!");
+      assert((isa<ConstantAggregateZero>(C) || isa<UndefValue>(C)) &&
+             "Unknown vector constant!");
       MVT EltVT = TLI.getValueType(VecTy->getElementType());
 
       SDValue Op;
-      if (EltVT.isFloatingPoint())
+      if (isa<UndefValue>(C))
+        Op = DAG.getUNDEF(EltVT);
+      else if (EltVT.isFloatingPoint())
         Op = DAG.getConstantFP(0, EltVT);
       else
         Op = DAG.getConstant(0, EltVT);
@@ -2431,42 +2435,37 @@ 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(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;
+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;
+    }
+  }
   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.getVectorShuffle(VT, getCurDebugLoc(), Src1, Src2,
-                                      &Mask[0]));
+    setValue(&I, DAG.getNode(ISD::VECTOR_SHUFFLE, getCurDebugLoc(),
+                             VT, Src1, Src2, Mask));
     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
@@ -2480,33 +2479,44 @@ 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);
 
-    SmallVector<SDValue, 8> MOps1(NumConcat, UndefVal);
-    SmallVector<SDValue, 8> MOps2(NumConcat, UndefVal);
+    SDValue* MOps1 = new SDValue[NumConcat];
+    SDValue* MOps2 = new SDValue[NumConcat];
     MOps1[0] = Src1;
     MOps2[0] = Src2;
-    
-    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);
+    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;
 
     // Readjust mask for new input vector length.
-    SmallVector<int, 8> MappedOps;
+    SmallVector<SDValue, 8> MappedOps;
     for (int i = 0; i != MaskNumElts; ++i) {
-      int Idx = Mask[i];
-      if (Idx < SrcNumElts)
-        MappedOps.push_back(Idx);
-      else
-        MappedOps.push_back(Idx + MaskNumElts - SrcNumElts);
+      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));
+      }
     }
-    setValue(&I, DAG.getVectorShuffle(VT, getCurDebugLoc(), Src1, Src2, 
-                                      &MappedOps[0]));
+    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));
     return;
   }
 
@@ -2531,19 +2541,20 @@ void SelectionDAGLowering::visitShuffleVector(User &I) {
     int MaxRange[2] = {-1, -1};
 
     for (int i = 0; i != MaskNumElts; ++i) {
-      int Idx = Mask[i];
-      int Input = 0;
-      if (Idx < 0)
-        continue;
-      
-      if (Idx >= SrcNumElts) {
-        Input = 1;
-        Idx -= SrcNumElts;
+      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;
       }
-      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
@@ -2585,18 +2596,26 @@ void SelectionDAGLowering::visitShuffleVector(User &I) {
         }
       }
       // Calculate new mask.
-      SmallVector<int, 8> MappedOps;
+      SmallVector<SDValue, 8> MappedOps;
       for (int i = 0; i != MaskNumElts; ++i) {
-        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);
+        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));
+          }
+        }
       }
-      setValue(&I, DAG.getVectorShuffle(VT, getCurDebugLoc(), Src1, Src2,
-                                        &MappedOps[0]));
+      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));
       return;
     }
   }
@@ -2608,10 +2627,12 @@ void SelectionDAGLowering::visitShuffleVector(User &I) {
   MVT PtrVT = TLI.getPointerTy();
   SmallVector<SDValue,8> Ops;
   for (int i = 0; i != MaskNumElts; ++i) {
-    if (Mask[i] < 0) {
+    SDValue Arg = Mask.getOperand(i);
+    if (Arg.getOpcode() == ISD::UNDEF) {
       Ops.push_back(DAG.getUNDEF(EltVT));
     } else {
-      int Idx = Mask[i];
+      assert(isa<ConstantSDNode>(Arg) && "Invalid VECTOR_SHUFFLE mask!");
+      int Idx = cast<ConstantSDNode>(Arg)->getZExtValue();
       if (Idx < SrcNumElts)
         Ops.push_back(DAG.getNode(ISD::EXTRACT_VECTOR_ELT, getCurDebugLoc(),
                                   EltVT, Src1, DAG.getConstant(Idx, PtrVT)));