2 files changed, 39 insertions, 16 deletions

diff --git a/lib/CodeGen/SelectionDAG/DAGCombiner.cpp b/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
index 67a419aac9..0d90fc0748 100644
--- a/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
+++ b/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
@@ -522,12 +522,17 @@ SDValue DAGCombiner::CombineTo(SDNode *N, const SDValue *To, unsigned NumTo,
     }
   }
   
-  // Nodes can be reintroduced into the worklist.  Make sure we do not
-  // process a node that has been replaced.
-  removeFromWorkList(N);
+  // Finally, if the node is now dead, remove it from the graph.  The node
+  // may not be dead if the replacement process recursively simplified to
+  // something else needing this node.
+  if (N->use_empty()) {
+    // Nodes can be reintroduced into the worklist.  Make sure we do not
+    // process a node that has been replaced.
+    removeFromWorkList(N);
   
-  // Finally, since the node is now dead, remove it from the graph.
-  DAG.DeleteNode(N);
+    // Finally, since the node is now dead, remove it from the graph.
+    DAG.DeleteNode(N);
+  }
   return SDValue(N, 0);
 }
 
@@ -658,12 +663,17 @@ void DAGCombiner::Run(CombineLevel AtLevel) {
     for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
       AddToWorkList(N->getOperand(i).getNode());
       
-    // Nodes can be reintroduced into the worklist.  Make sure we do not
-    // process a node that has been replaced.
-    removeFromWorkList(N);
+    // Finally, if the node is now dead, remove it from the graph.  The node
+    // may not be dead if the replacement process recursively simplified to
+    // something else needing this node.
+    if (N->use_empty()) {
+      // Nodes can be reintroduced into the worklist.  Make sure we do not
+      // process a node that has been replaced.
+      removeFromWorkList(N);
     
-    // Finally, since the node is now dead, remove it from the graph.
-    DAG.DeleteNode(N);
+      // Finally, since the node is now dead, remove it from the graph.
+      DAG.DeleteNode(N);
+    }
   }
   
   // If the root changed (e.g. it was a dead load, update the root).
diff --git a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
index b83d537e37..d8124e6d7c 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
@@ -4388,9 +4388,16 @@ void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To,
          "Cannot replace with this method!");
   assert(From != To.getNode() && "Cannot replace uses of with self");
 
-  while (!From->use_empty()) {
-    SDNode::use_iterator UI = From->use_begin();
+  // Iterate over all the existing uses of From. This specifically avoids
+  // visiting any new uses of From that arrise while the replacement is
+  // happening, because any such uses would be the result of CSE: If an
+  // existing node looks like From after one of its operands is replaced
+  // by To, we don't want to replace of all its users with To too.
+  // See PR3018 for more info.
+  SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
+  while (UI != UE) {
     SDNode *U = *UI;
+    do ++UI; while (UI != UE && *UI == U);
 
     // This node is about to morph, remove its old self from the CSE maps.
     RemoveNodeFromCSEMaps(U);
@@ -4437,9 +4444,12 @@ void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To,
   if (From == To)
     return;
 
-  while (!From->use_empty()) {
-    SDNode::use_iterator UI = From->use_begin();
+  // Iterate over just the existing users of From. See the comments in
+  // the ReplaceAllUsesWith above.
+  SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
+  while (UI != UE) {
     SDNode *U = *UI;
+    do ++UI; while (UI != UE && *UI == U);
 
     // This node is about to morph, remove its old self from the CSE maps.
     RemoveNodeFromCSEMaps(U);
@@ -4480,9 +4490,12 @@ void SelectionDAG::ReplaceAllUsesWith(SDNode *From,
   if (From->getNumValues() == 1)  // Handle the simple case efficiently.
     return ReplaceAllUsesWith(SDValue(From, 0), To[0], UpdateListener);
 
-  while (!From->use_empty()) {
-    SDNode::use_iterator UI = From->use_begin();
+  // Iterate over just the existing users of From. See the comments in
+  // the ReplaceAllUsesWith above.
+  SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
+  while (UI != UE) {
     SDNode *U = *UI;
+    do ++UI; while (UI != UE && *UI == U);
 
     // This node is about to morph, remove its old self from the CSE maps.
     RemoveNodeFromCSEMaps(U);