From f9d95c8835bc4f9072c33e1f9ebaa581a4d3268d Mon Sep 17 00:00:00 2001
From: Chris Lattner <sabre@nondot.org>
Date: Sun, 9 Mar 2008 00:29:42 +0000
Subject: [PATCH] Fix two problems in
 SelectionDAGLegalize::ExpandBUILD_VECTOR's handling of BUILD_VECTORS that
 only have two unique elements:

1. The previous code was nondeterminstic, because it walked a map in
   SDOperand order, which isn't determinstic.
2. The previous code didn't handle the case when one element was undef
   very well.  Now we ensure that the generated shuffle mask has the
   undef vector on the RHS (instead of potentially being on the LHS)
   and that any elements that refer to it are themselves undef.  This
   allows us to compile CodeGen/X86/vec_set-9.ll into:

_test3:
	movd	%rdi, %xmm0
	punpcklqdq	%xmm0, %xmm0
	ret

instead of:

_test3:
	movd	%rdi, %xmm1
	#IMPLICIT_DEF %xmm0
	punpcklqdq	%xmm1, %xmm0
	ret

... saving a register.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@48060 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/CodeGen/SelectionDAG/LegalizeDAG.cpp | 59 +++++++++++++++---------
 1 file changed, 38 insertions(+), 21 deletions(-)

diff --git a/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp b/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
index 8e59b53d1cb..4993e468d28 100644
--- a/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
@@ -4938,6 +4938,9 @@ SDOperand SelectionDAGLegalize::ExpandBUILD_VECTOR(SDNode *Node) {
   unsigned NumElems = Node->getNumOperands();
   bool isOnlyLowElement = true;
   SDOperand SplatValue = Node->getOperand(0);
+  
+  // FIXME: it would be far nicer to change this into map<SDOperand,uint64_t>
+  // and use a bitmask instead of a list of elements.
   std::map<SDOperand, std::vector<unsigned> > Values;
   Values[SplatValue].push_back(0);
   bool isConstant = true;
@@ -5018,36 +5021,50 @@ SDOperand SelectionDAGLegalize::ExpandBUILD_VECTOR(SDNode *Node) {
   // If there are only two unique elements, we may be able to turn this into a
   // vector shuffle.
   if (Values.size() == 2) {
+    // Get the two values in deterministic order.
+    SDOperand Val1 = Node->getOperand(1);
+    SDOperand Val2;
+    std::map<SDOperand, std::vector<unsigned> >::iterator MI = Values.begin();
+    if (MI->first != Val1)
+      Val2 = MI->first;
+    else
+      Val2 = (++MI)->first;
+    
+    // If Val1 is an undef, make sure end ends up as Val2, to ensure that our 
+    // vector shuffle has the undef vector on the RHS.
+    if (Val1.getOpcode() == ISD::UNDEF)
+      std::swap(Val1, Val2);
+    
     // Build the shuffle constant vector: e.g. <0, 4, 0, 4>
-    MVT::ValueType MaskVT = 
-      MVT::getIntVectorWithNumElements(NumElems);
+    MVT::ValueType MaskVT = MVT::getIntVectorWithNumElements(NumElems);
+    MVT::ValueType MaskEltVT = MVT::getVectorElementType(MaskVT);
     std::vector<SDOperand> MaskVec(NumElems);
-    unsigned i = 0;
-    for (std::map<SDOperand,std::vector<unsigned> >::iterator I=Values.begin(),
-           E = Values.end(); I != E; ++I) {
-      for (std::vector<unsigned>::iterator II = I->second.begin(),
-             EE = I->second.end(); II != EE; ++II)
-        MaskVec[*II] = DAG.getConstant(i, MVT::getVectorElementType(MaskVT));
-      i += 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)
+      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)
+        MaskVec[Val2Elts[i]] = DAG.getConstant(NumElems, MaskEltVT);
+      else
+        MaskVec[Val2Elts[i]] = DAG.getNode(ISD::UNDEF, MaskEltVT);
+    
     SDOperand ShuffleMask = DAG.getNode(ISD::BUILD_VECTOR, MaskVT,
                                         &MaskVec[0], MaskVec.size());
 
-    // If the target supports VECTOR_SHUFFLE and this shuffle mask, use it.
+    // If the target supports SCALAR_TO_VECTOR and this shuffle mask, use it.
     if (TLI.isOperationLegal(ISD::SCALAR_TO_VECTOR, Node->getValueType(0)) &&
         isShuffleLegal(Node->getValueType(0), ShuffleMask)) {
-      SmallVector<SDOperand, 8> Ops;
-      for(std::map<SDOperand,std::vector<unsigned> >::iterator I=Values.begin(),
-            E = Values.end(); I != E; ++I) {
-        SDOperand Op = DAG.getNode(ISD::SCALAR_TO_VECTOR, Node->getValueType(0),
-                                   I->first);
-        Ops.push_back(Op);
-      }
-      Ops.push_back(ShuffleMask);
+      Val1 = DAG.getNode(ISD::SCALAR_TO_VECTOR, Node->getValueType(0), Val1);
+      Val2 = DAG.getNode(ISD::SCALAR_TO_VECTOR, Node->getValueType(0), Val2);
+      SDOperand Ops[] = { Val1, Val2, ShuffleMask };
 
       // Return shuffle(LoValVec, HiValVec, <0,1,0,1>)
-      return DAG.getNode(ISD::VECTOR_SHUFFLE, Node->getValueType(0), 
-                         &Ops[0], Ops.size());
+      return DAG.getNode(ISD::VECTOR_SHUFFLE, Node->getValueType(0), Ops, 3);
     }
   }
   
-- 
2.34.1