Fixed a bug during widening where we would avoid legalizing a node. When we

replace an OpA with a widened OpB, it is possible to get new uses of OpA due to CSE
when recursively updating nodes.  Since OpA has been processed, the new uses are
not examined again.  The patch checks if this occurred and it it did, updates the
new uses of OpA to use OpB.

llvm-svn: 105453

3 files changed, 72 insertions, 47 deletions

diff --git a/llvm/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp b/llvm/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp
index 17f131b21e4..4fea77e9acb 100644
--- a/llvm/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp
@@ -684,40 +684,45 @@ void DAGTypeLegalizer::ReplaceValueWith(SDValue From, SDValue To) {
   // can potentially cause recursive merging.
   SmallSetVector<SDNode*, 16> NodesToAnalyze;
   NodeUpdateListener NUL(*this, NodesToAnalyze);
-  DAG.ReplaceAllUsesOfValueWith(From, To, &NUL);
-
-  // The old node may still be present in a map like ExpandedIntegers or
-  // PromotedIntegers.  Inform maps about the replacement.
-  ReplacedValues[From] = To;
-
-  // Process the list of nodes that need to be reanalyzed.
-  while (!NodesToAnalyze.empty()) {
-    SDNode *N = NodesToAnalyze.back();
-    NodesToAnalyze.pop_back();
-    if (N->getNodeId() != DAGTypeLegalizer::NewNode)
-      // The node was analyzed while reanalyzing an earlier node - it is safe to
-      // skip.  Note that this is not a morphing node - otherwise it would still
-      // be marked NewNode.
-      continue;
+  do {
+    DAG.ReplaceAllUsesOfValueWith(From, To, &NUL);
+
+    // The old node may still be present in a map like ExpandedIntegers or
+    // PromotedIntegers.  Inform maps about the replacement.
+    ReplacedValues[From] = To;
+
+    // Process the list of nodes that need to be reanalyzed.
+    while (!NodesToAnalyze.empty()) {
+      SDNode *N = NodesToAnalyze.back();
+      NodesToAnalyze.pop_back();
+      if (N->getNodeId() != DAGTypeLegalizer::NewNode)
+        // The node was analyzed while reanalyzing an earlier node - it is safe
+        // to skip.  Note that this is not a morphing node - otherwise it would
+        // still be marked NewNode.
+        continue;
 
-    // Analyze the node's operands and recalculate the node ID.
-    SDNode *M = AnalyzeNewNode(N);
-    if (M != N) {
-      // The node morphed into a different node.  Make everyone use the new node
-      // instead.
-      assert(M->getNodeId() != NewNode && "Analysis resulted in NewNode!");
-      assert(N->getNumValues() == M->getNumValues() &&
-             "Node morphing changed the number of results!");
-      for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) {
-        SDValue OldVal(N, i);
-        SDValue NewVal(M, i);
-        if (M->getNodeId() == Processed)
-          RemapValue(NewVal);
-        DAG.ReplaceAllUsesOfValueWith(OldVal, NewVal, &NUL);
+      // Analyze the node's operands and recalculate the node ID.
+      SDNode *M = AnalyzeNewNode(N);
+      if (M != N) {
+        // The node morphed into a different node.  Make everyone use the new
+        // node instead.
+        assert(M->getNodeId() != NewNode && "Analysis resulted in NewNode!");
+        assert(N->getNumValues() == M->getNumValues() &&
+               "Node morphing changed the number of results!");
+        for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) {
+          SDValue OldVal(N, i);
+          SDValue NewVal(M, i);
+          if (M->getNodeId() == Processed)
+            RemapValue(NewVal);
+          DAG.ReplaceAllUsesOfValueWith(OldVal, NewVal, &NUL);
+        }
+        // The original node continues to exist in the DAG, marked NewNode.
       }
-      // The original node continues to exist in the DAG, marked NewNode.
     }
-  }
+    // When recursively update nodes with new nodes, it is possible to have
+    // new uses of From due to CSE. If this happens, replace the new uses of
+    // From with To.
+  } while (!From.use_empty());
 }
 
 void DAGTypeLegalizer::SetPromotedInteger(SDValue Op, SDValue Result) {
diff --git a/llvm/test/CodeGen/X86/widen_shuffle-1.ll b/llvm/test/CodeGen/X86/widen_shuffle-1.ll
index 47dba4b4a04..25dde57c767 100644
--- a/llvm/test/CodeGen/X86/widen_shuffle-1.ll
+++ b/llvm/test/CodeGen/X86/widen_shuffle-1.ll
@@ -1,13 +1,46 @@
 ; RUN: llc < %s -march=x86 -mattr=+sse42 -disable-mmx | FileCheck %s
-; CHECK: insertps
-; CHECK: extractps
 
 ; widening shuffle v3float and then a add
-
 define void @shuf(<3 x float>* %dst.addr, <3 x float> %src1,<3 x float> %src2) nounwind {
 entry:
+; CHECK: insertps
+; CHECK: extractps
 	%x = shufflevector <3 x float> %src1, <3 x float> %src2, <3 x i32> < i32 0, i32 1, i32 2>
 	%val = fadd <3 x float> %x, %src2
 	store <3 x float> %val, <3 x float>* %dst.addr
 	ret void
 }
+
+
+; widening shuffle v3float with a different mask and then a add
+define void @shuf2(<3 x float>* %dst.addr, <3 x float> %src1,<3 x float> %src2) nounwind {
+entry:
+; CHECK: insertps
+; CHECK: extractps
+	%x = shufflevector <3 x float> %src1, <3 x float> %src2, <3 x i32> < i32 0, i32 4, i32 2>
+	%val = fadd <3 x float> %x, %src2
+	store <3 x float> %val, <3 x float>* %dst.addr
+	ret void
+}
+
+; Example of when widening a v3float operation causes the DAG to replace a node
+; with the operation that we are currently widening, i.e. when replacing
+; opA with opB, the DAG will produce new operations with opA.
+define void @shuf3(<4 x float> %tmp10, <4 x float> %vecinit15, <4 x float>* %dst) {
+entry:
+; CHECK: pshufd
+  %shuffle.i.i.i12 = shufflevector <4 x float> %tmp10, <4 x float> %vecinit15, <4 x i32> <i32 0, i32 1, i32 4, i32 5>
+  %tmp25.i.i = shufflevector <4 x float> %shuffle.i.i.i12, <4 x float> undef, <3 x i32> <i32 0, i32 1, i32 2> 
+  %tmp1.i.i = shufflevector <3 x float> %tmp25.i.i, <3 x float> zeroinitializer, <4 x i32> <i32 0, i32 1, i32 2, i32 3>
+  %tmp3.i13 = shufflevector <4 x float> %tmp1.i.i, <4 x float> undef, <3 x i32> <i32 0, i32 1, i32 2> ; <<3 x float>>
+  %tmp6.i14 = shufflevector <3 x float> %tmp3.i13, <3 x float> zeroinitializer, <4 x i32> <i32 0, i32 1, i32 2, i32 3>
+  %tmp97.i = shufflevector <4 x float> %tmp6.i14, <4 x float> undef, <3 x i32> <i32 0, i32 1, i32 2>
+  %tmp2.i18 = shufflevector <3 x float> %tmp97.i, <3 x float> undef, <4 x i32> <i32 0, i32 1, i32 2, i32 2>
+  %t5 = bitcast <4 x float> %tmp2.i18 to <4 x i32>
+  %shr.i.i19 = lshr <4 x i32> %t5, <i32 19, i32 19, i32 19, i32 19>
+  %and.i.i20 = and <4 x i32> %shr.i.i19, <i32 4080, i32 4080, i32 4080, i32 4080> 
+  %shuffle.i.i.i21 = shufflevector <4 x float> %tmp2.i18, <4 x float> undef, <4 x i32> <i32 2, i32 3, i32 2, i32 3>
+  store <4 x float> %shuffle.i.i.i21, <4 x float>* %dst
+  ret void
+}
+
diff --git a/llvm/test/CodeGen/X86/widen_shuffle-2.ll b/llvm/test/CodeGen/X86/widen_shuffle-2.ll
deleted file mode 100644
index 9374a028631..00000000000
--- a/llvm/test/CodeGen/X86/widen_shuffle-2.ll
+++ /dev/null
@@ -1,13 +0,0 @@
-; RUN: llc < %s -march=x86 -mattr=+sse42 -disable-mmx | FileCheck %s
-; CHECK: insertps
-; CHECK: extractps
-
-; widening shuffle v3float and then a add
-
-define void @shuf(<3 x float>* %dst.addr, <3 x float> %src1,<3 x float> %src2) nounwind {
-entry:
-	%x = shufflevector <3 x float> %src1, <3 x float> %src2, <3 x i32> < i32 0, i32 4, i32 2>
-	%val = fadd <3 x float> %x, %src2
-	store <3 x float> %val, <3 x float>* %dst.addr
-	ret void
-}