Change the 'global modification' APIs in SelectionDAG to take a new

DAGUpdateListener object pointer instead of just returning a vector 
of deleted nodes.  This makes the interfaces more efficient (no more
allocating a vector [at least a malloc], filling it in, then walking
it) and more clean.  This also allows the client to be notified of
nodes that are *changed* but not deleted.


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

2 files changed, 209 insertions, 162 deletions

diff --git a/lib/CodeGen/SelectionDAG/DAGCombiner.cpp b/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
index 4508d3a..0823e0a 100644
--- a/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
+++ b/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
@@ -81,13 +81,6 @@ namespace {
         AddToWorkList(*UI);
     }
 
-    /// removeFromWorkList - remove all instances of N from the worklist.
-    ///
-    void removeFromWorkList(SDNode *N) {
-      WorkList.erase(std::remove(WorkList.begin(), WorkList.end(), N),
-                     WorkList.end());
-    }
-    
     /// visit - call the node-specific routine that knows how to fold each
     /// particular type of node.
     SDOperand visit(SDNode *N);
@@ -100,35 +93,16 @@ namespace {
       WorkList.push_back(N);
     }
 
-    SDOperand CombineTo(SDNode *N, const SDOperand *To, unsigned NumTo,
-                        bool AddTo = true) {
-      assert(N->getNumValues() == NumTo && "Broken CombineTo call!");
-      ++NodesCombined;
-      DOUT << "\nReplacing.1 "; DEBUG(N->dump(&DAG));
-      DOUT << "\nWith: "; DEBUG(To[0].Val->dump(&DAG));
-      DOUT << " and " << NumTo-1 << " other values\n";
-      std::vector<SDNode*> NowDead;
-      DAG.ReplaceAllUsesWith(N, To, &NowDead);
-      
-      if (AddTo) {
-        // Push the new nodes and any users onto the worklist
-        for (unsigned i = 0, e = NumTo; i != e; ++i) {
-          AddToWorkList(To[i].Val);
-          AddUsersToWorkList(To[i].Val);
-        }
-      }
-      
-      // Nodes can be reintroduced into the worklist.  Make sure we do not
-      // process a node that has been replaced.
-      removeFromWorkList(N);
-      for (unsigned i = 0, e = NowDead.size(); i != e; ++i)
-        removeFromWorkList(NowDead[i]);
-      
-      // Finally, since the node is now dead, remove it from the graph.
-      DAG.DeleteNode(N);
-      return SDOperand(N, 0);
+    /// removeFromWorkList - remove all instances of N from the worklist.
+    ///
+    void removeFromWorkList(SDNode *N) {
+      WorkList.erase(std::remove(WorkList.begin(), WorkList.end(), N),
+                     WorkList.end());
     }
     
+    SDOperand CombineTo(SDNode *N, const SDOperand *To, unsigned NumTo,
+                        bool AddTo = true);
+    
     SDOperand CombineTo(SDNode *N, SDOperand Res, bool AddTo = true) {
       return CombineTo(N, &Res, 1, AddTo);
     }
@@ -144,50 +118,7 @@ namespace {
     /// SimplifyDemandedBits - Check the specified integer node value to see if
     /// it can be simplified or if things it uses can be simplified by bit
     /// propagation.  If so, return true.
-    bool SimplifyDemandedBits(SDOperand Op, uint64_t Demanded = ~0ULL) {
-      TargetLowering::TargetLoweringOpt TLO(DAG, AfterLegalize);
-      uint64_t KnownZero, KnownOne;
-      Demanded &= MVT::getIntVTBitMask(Op.getValueType());
-      if (!TLI.SimplifyDemandedBits(Op, Demanded, KnownZero, KnownOne, TLO))
-        return false;
-
-      // Revisit the node.
-      AddToWorkList(Op.Val);
-      
-      // Replace the old value with the new one.
-      ++NodesCombined;
-      DOUT << "\nReplacing.2 "; DEBUG(TLO.Old.Val->dump(&DAG));
-      DOUT << "\nWith: "; DEBUG(TLO.New.Val->dump(&DAG));
-      DOUT << '\n';
-
-      std::vector<SDNode*> NowDead;
-      DAG.ReplaceAllUsesOfValueWith(TLO.Old, TLO.New, &NowDead);
-      
-      // Push the new node and any (possibly new) users onto the worklist.
-      AddToWorkList(TLO.New.Val);
-      AddUsersToWorkList(TLO.New.Val);
-      
-      // Nodes can end up on the worklist more than once.  Make sure we do
-      // not process a node that has been replaced.
-      for (unsigned i = 0, e = NowDead.size(); i != e; ++i)
-        removeFromWorkList(NowDead[i]);
-      
-      // 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 (TLO.Old.Val->use_empty()) {
-        removeFromWorkList(TLO.Old.Val);
-        
-        // If the operands of this node are only used by the node, they will now
-        // be dead.  Make sure to visit them first to delete dead nodes early.
-        for (unsigned i = 0, e = TLO.Old.Val->getNumOperands(); i != e; ++i)
-          if (TLO.Old.Val->getOperand(i).Val->hasOneUse())
-            AddToWorkList(TLO.Old.Val->getOperand(i).Val);
-        
-        DAG.DeleteNode(TLO.Old.Val);
-      }
-      return true;
-    }
+    bool SimplifyDemandedBits(SDOperand Op, uint64_t Demanded = ~0ULL);
 
     bool CombineToPreIndexedLoadStore(SDNode *N);
     bool CombineToPostIndexedLoadStore(SDNode *N);
@@ -322,6 +253,27 @@ public:
   };
 }
 
+
+namespace {
+/// WorkListRemover - This class is a DAGUpdateListener that removes any deleted
+/// nodes from the worklist.
+class VISIBILITY_HIDDEN WorkListRemover : 
+  public SelectionDAG::DAGUpdateListener {
+  DAGCombiner &DC;
+public:
+  WorkListRemover(DAGCombiner &dc) : DC(dc) {}
+  
+  virtual void NodeDeleted(SDNode *N) {
+    printf("remove from WL: %p\n", (void*)N);
+    DC.removeFromWorkList(N);
+  }
+  
+  virtual void NodeUpdated(SDNode *N) {
+    // Ignore updates.
+  }
+};
+}
+
 //===----------------------------------------------------------------------===//
 //  TargetLowering::DAGCombinerInfo implementation
 //===----------------------------------------------------------------------===//
@@ -543,6 +495,78 @@ SDOperand DAGCombiner::ReassociateOps(unsigned Opc, SDOperand N0, SDOperand N1){
   return SDOperand();
 }
 
+SDOperand DAGCombiner::CombineTo(SDNode *N, const SDOperand *To, unsigned NumTo,
+                                 bool AddTo) {
+  assert(N->getNumValues() == NumTo && "Broken CombineTo call!");
+  ++NodesCombined;
+  DOUT << "\nReplacing.1 "; DEBUG(N->dump(&DAG));
+  DOUT << "\nWith: "; DEBUG(To[0].Val->dump(&DAG));
+  DOUT << " and " << NumTo-1 << " other values\n";
+  WorkListRemover DeadNodes(*this);
+  DAG.ReplaceAllUsesWith(N, To, &DeadNodes);
+  
+  if (AddTo) {
+    // Push the new nodes and any users onto the worklist
+    for (unsigned i = 0, e = NumTo; i != e; ++i) {
+      AddToWorkList(To[i].Val);
+      AddUsersToWorkList(To[i].Val);
+    }
+  }
+  
+  // 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);
+  return SDOperand(N, 0);
+}
+
+/// SimplifyDemandedBits - Check the specified integer node value to see if
+/// it can be simplified or if things it uses can be simplified by bit
+/// propagation.  If so, return true.
+bool DAGCombiner::SimplifyDemandedBits(SDOperand Op, uint64_t Demanded) {
+  TargetLowering::TargetLoweringOpt TLO(DAG, AfterLegalize);
+  uint64_t KnownZero, KnownOne;
+  Demanded &= MVT::getIntVTBitMask(Op.getValueType());
+  if (!TLI.SimplifyDemandedBits(Op, Demanded, KnownZero, KnownOne, TLO))
+    return false;
+  
+  // Revisit the node.
+  AddToWorkList(Op.Val);
+  
+  // Replace the old value with the new one.
+  ++NodesCombined;
+  DOUT << "\nReplacing.2 "; DEBUG(TLO.Old.Val->dump(&DAG));
+  DOUT << "\nWith: "; DEBUG(TLO.New.Val->dump(&DAG));
+  DOUT << '\n';
+  
+  // Replace all uses.  If any nodes become isomorphic to other nodes and 
+  // are deleted, make sure to remove them from our worklist.
+  WorkListRemover DeadNodes(*this);
+  DAG.ReplaceAllUsesOfValueWith(TLO.Old, TLO.New, &DeadNodes);
+  
+  // Push the new node and any (possibly new) users onto the worklist.
+  AddToWorkList(TLO.New.Val);
+  AddUsersToWorkList(TLO.New.Val);
+  
+  // 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 (TLO.Old.Val->use_empty()) {
+    removeFromWorkList(TLO.Old.Val);
+    
+    // If the operands of this node are only used by the node, they will now
+    // be dead.  Make sure to visit them first to delete dead nodes early.
+    for (unsigned i = 0, e = TLO.Old.Val->getNumOperands(); i != e; ++i)
+      if (TLO.Old.Val->getOperand(i).Val->hasOneUse())
+        AddToWorkList(TLO.Old.Val->getOperand(i).Val);
+    
+    DAG.DeleteNode(TLO.Old.Val);
+  }
+  return true;
+}
+
 //===----------------------------------------------------------------------===//
 //  Main DAG Combiner implementation
 //===----------------------------------------------------------------------===//
@@ -603,14 +627,14 @@ void DAGCombiner::Run(bool RunningAfterLegalize) {
     DOUT << "\nReplacing.3 "; DEBUG(N->dump(&DAG));
     DOUT << "\nWith: "; DEBUG(RV.Val->dump(&DAG));
     DOUT << '\n';
-    std::vector<SDNode*> NowDead;
+    WorkListRemover DeadNodes(*this);
     if (N->getNumValues() == RV.Val->getNumValues())
-      DAG.ReplaceAllUsesWith(N, RV.Val, &NowDead);
+      DAG.ReplaceAllUsesWith(N, RV.Val, &DeadNodes);
     else {
       assert(N->getValueType(0) == RV.getValueType() &&
              N->getNumValues() == 1 && "Type mismatch");
       SDOperand OpV = RV;
-      DAG.ReplaceAllUsesWith(N, &OpV, &NowDead);
+      DAG.ReplaceAllUsesWith(N, &OpV, &DeadNodes);
     }
       
     // Push the new node and any users onto the worklist
@@ -626,8 +650,6 @@ void DAGCombiner::Run(bool RunningAfterLegalize) {
     // Nodes can be reintroduced into the worklist.  Make sure we do not
     // process a node that has been replaced.
     removeFromWorkList(N);
-    for (unsigned i = 0, e = NowDead.size(); i != e; ++i)
-      removeFromWorkList(NowDead[i]);
     
     // Finally, since the node is now dead, remove it from the graph.
     DAG.DeleteNode(N);
@@ -3084,7 +3106,9 @@ SDOperand DAGCombiner::ReduceLoadWidth(SDNode *N) {
                        LN0->isVolatile(), NewAlign);
     AddToWorkList(N);
     if (CombineSRL) {
-      DAG.ReplaceAllUsesOfValueWith(N0.getValue(1), Load.getValue(1));
+      WorkListRemover DeadNodes(*this);
+      DAG.ReplaceAllUsesOfValueWith(N0.getValue(1), Load.getValue(1),
+                                    &DeadNodes);
       CombineTo(N->getOperand(0).Val, Load);
     } else
       CombineTo(N0.Val, Load, Load.getValue(1));
@@ -3990,30 +4014,24 @@ bool DAGCombiner::CombineToPreIndexedLoadStore(SDNode *N) {
   DOUT << "\nReplacing.4 "; DEBUG(N->dump(&DAG));
   DOUT << "\nWith: "; DEBUG(Result.Val->dump(&DAG));
   DOUT << '\n';
-  std::vector<SDNode*> NowDead;
+  WorkListRemover DeadNodes(*this);
   if (isLoad) {
     DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 0), Result.getValue(0),
-                                  &NowDead);
+                                  &DeadNodes);
     DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 1), Result.getValue(2),
-                                  &NowDead);
+                                  &DeadNodes);
   } else {
     DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 0), Result.getValue(1),
-                                  &NowDead);
+                                  &DeadNodes);
   }
 
-  // Nodes can end up on the worklist more than once.  Make sure we do
-  // not process a node that has been replaced.
-  for (unsigned i = 0, e = NowDead.size(); i != e; ++i)
-    removeFromWorkList(NowDead[i]);
   // Finally, since the node is now dead, remove it from the graph.
   DAG.DeleteNode(N);
 
   // Replace the uses of Ptr with uses of the updated base value.
   DAG.ReplaceAllUsesOfValueWith(Ptr, Result.getValue(isLoad ? 1 : 0),
-                                &NowDead);
+                                &DeadNodes);
   removeFromWorkList(Ptr.Val);
-  for (unsigned i = 0, e = NowDead.size(); i != e; ++i)
-    removeFromWorkList(NowDead[i]);
   DAG.DeleteNode(Ptr.Val);
 
   return true;
@@ -4121,33 +4139,26 @@ bool DAGCombiner::CombineToPostIndexedLoadStore(SDNode *N) {
         DOUT << "\nReplacing.5 "; DEBUG(N->dump(&DAG));
         DOUT << "\nWith: "; DEBUG(Result.Val->dump(&DAG));
         DOUT << '\n';
-        std::vector<SDNode*> NowDead;
+        WorkListRemover DeadNodes(*this);
         if (isLoad) {
           DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 0), Result.getValue(0),
-                                        &NowDead);
+                                        &DeadNodes);
           DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 1), Result.getValue(2),
-                                        &NowDead);
+                                        &DeadNodes);
         } else {
           DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 0), Result.getValue(1),
-                                        &NowDead);
+                                        &DeadNodes);
         }
 
-        // Nodes can end up on the worklist more than once.  Make sure we do
-        // not process a node that has been replaced.
-        for (unsigned i = 0, e = NowDead.size(); i != e; ++i)
-          removeFromWorkList(NowDead[i]);
         // Finally, since the node is now dead, remove it from the graph.
         DAG.DeleteNode(N);
 
         // Replace the uses of Use with uses of the updated base value.
         DAG.ReplaceAllUsesOfValueWith(SDOperand(Op, 0),
                                       Result.getValue(isLoad ? 1 : 0),
-                                      &NowDead);
+                                      &DeadNodes);
         removeFromWorkList(Op);
-        for (unsigned i = 0, e = NowDead.size(); i != e; ++i)
-          removeFromWorkList(NowDead[i]);
         DAG.DeleteNode(Op);
-
         return true;
       }
     }
@@ -4228,13 +4239,11 @@ SDOperand DAGCombiner::visitLOAD(SDNode *N) {
         // v3         = add v2, c
         // Now we replace use of chain2 with chain1.  This makes the second load
         // isomorphic to the one we are deleting, and thus makes this load live.
-        std::vector<SDNode*> NowDead;
         DOUT << "\nReplacing.6 "; DEBUG(N->dump(&DAG));
         DOUT << "\nWith chain: "; DEBUG(Chain.Val->dump(&DAG));
         DOUT << "\n";
-        DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 1), Chain, &NowDead);
-        for (unsigned i = 0, e = NowDead.size(); i != e; ++i)
-          removeFromWorkList(NowDead[i]);
+        WorkListRemover DeadNodes(*this);
+        DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 1), Chain, &DeadNodes);
         if (N->use_empty()) {
           removeFromWorkList(N);
           DAG.DeleteNode(N);
@@ -4245,19 +4254,17 @@ SDOperand DAGCombiner::visitLOAD(SDNode *N) {
       // Indexed loads.
       assert(N->getValueType(2) == MVT::Other && "Malformed indexed loads?");
       if (N->hasNUsesOfValue(0, 0) && N->hasNUsesOfValue(0, 1)) {
-        std::vector<SDNode*> NowDead;
         SDOperand Undef = DAG.getNode(ISD::UNDEF, N->getValueType(0));
         DOUT << "\nReplacing.6 "; DEBUG(N->dump(&DAG));
         DOUT << "\nWith: "; DEBUG(Undef.Val->dump(&DAG));
         DOUT << " and 2 other values\n";
-        DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 0), Undef, &NowDead);
+        WorkListRemover DeadNodes(*this);
+        DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 0), Undef, &DeadNodes);
         DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 1),
                                     DAG.getNode(ISD::UNDEF, N->getValueType(1)),
-                                      &NowDead);
-        DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 2), Chain, &NowDead);
+                                      &DeadNodes);
+        DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 2), Chain, &DeadNodes);
         removeFromWorkList(N);
-        for (unsigned i = 0, e = NowDead.size(); i != e; ++i)
-          removeFromWorkList(NowDead[i]);
         DAG.DeleteNode(N);
         return SDOperand(N, 0);   // Return N so it doesn't get rechecked!
       }
diff --git a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
index 9e4d724..eeec961 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
@@ -43,6 +43,8 @@ static SDVTList makeVTList(const MVT::ValueType *VTs, unsigned NumVTs) {
   return Res;
 }
 
+SelectionDAG::DAGUpdateListener::~DAGUpdateListener() {}
+
 //===----------------------------------------------------------------------===//
 //                              ConstantFPSDNode Class
 //===----------------------------------------------------------------------===//
@@ -455,7 +457,7 @@ void SelectionDAG::RemoveDeadNodes() {
   setRoot(Dummy.getValue());
 }
 
-void SelectionDAG::RemoveDeadNode(SDNode *N, std::vector<SDNode*> &Deleted) {
+void SelectionDAG::RemoveDeadNode(SDNode *N, DAGUpdateListener *UpdateListener){
   SmallVector<SDNode*, 16> DeadNodes;
   DeadNodes.push_back(N);
 
@@ -465,6 +467,9 @@ void SelectionDAG::RemoveDeadNode(SDNode *N, std::vector<SDNode*> &Deleted) {
     SDNode *N = DeadNodes.back();
     DeadNodes.pop_back();
     
+    if (UpdateListener)
+      UpdateListener->NodeDeleted(N);
+    
     // Take the node out of the appropriate CSE map.
     RemoveNodeFromCSEMaps(N);
 
@@ -484,7 +489,6 @@ void SelectionDAG::RemoveDeadNode(SDNode *N, std::vector<SDNode*> &Deleted) {
     N->NumOperands = 0;
     
     // Finally, remove N itself.
-    Deleted.push_back(N);
     AllNodes.erase(N);
   }
 }
@@ -3170,13 +3174,14 @@ SDNode *SelectionDAG::getTargetNode(unsigned Opcode,
                  Ops, NumOps).Val;
 }
 
+
 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
 /// This can cause recursive merging of nodes in the DAG.
 ///
 /// This version assumes From has a single result value.
 ///
 void SelectionDAG::ReplaceAllUsesWith(SDOperand FromN, SDOperand To,
-                                      std::vector<SDNode*> *Deleted) {
+                                      DAGUpdateListener *UpdateListener) {
   SDNode *From = FromN.Val;
   // FIXME: This works around a dag isel emitter bug.
   if (From->getNumValues() == 1 && FromN.ResNo != 0)
@@ -3204,10 +3209,16 @@ void SelectionDAG::ReplaceAllUsesWith(SDOperand FromN, SDOperand To,
     // Now that we have modified U, add it back to the CSE maps.  If it already
     // exists there, recursively merge the results together.
     if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) {
-      ReplaceAllUsesWith(U, Existing, Deleted);
-      // U is now dead.
-      if (Deleted) Deleted->push_back(U);
+      ReplaceAllUsesWith(U, Existing, UpdateListener);
+      // U is now dead.  Inform the listener if it exists and delete it.
+      if (UpdateListener) 
+        UpdateListener->NodeDeleted(U);
       DeleteNodeNotInCSEMaps(U);
+    } else {
+      // If the node doesn't already exist, we updated it.  Inform a listener if
+      // it exists.
+      if (UpdateListener) 
+        UpdateListener->NodeUpdated(U);
     }
   }
 }
@@ -3219,12 +3230,13 @@ void SelectionDAG::ReplaceAllUsesWith(SDOperand FromN, SDOperand To,
 /// values.
 ///
 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To,
-                                      std::vector<SDNode*> *Deleted) {
+                                      DAGUpdateListener *UpdateListener) {
   assert(From != To && "Cannot replace uses of with self");
   assert(From->getNumValues() == To->getNumValues() &&
          "Cannot use this version of ReplaceAllUsesWith!");
   if (From->getNumValues() == 1)   // If possible, use the faster version.
-    return ReplaceAllUsesWith(SDOperand(From, 0), SDOperand(To, 0), Deleted);
+    return ReplaceAllUsesWith(SDOperand(From, 0), SDOperand(To, 0),
+                              UpdateListener);
   
   while (!From->use_empty()) {
     // Process users until they are all gone.
@@ -3244,10 +3256,16 @@ void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To,
     // Now that we have modified U, add it back to the CSE maps.  If it already
     // exists there, recursively merge the results together.
     if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) {
-      ReplaceAllUsesWith(U, Existing, Deleted);
-      // U is now dead.
-      if (Deleted) Deleted->push_back(U);
+      ReplaceAllUsesWith(U, Existing, UpdateListener);
+      // U is now dead.  Inform the listener if it exists and delete it.
+      if (UpdateListener) 
+        UpdateListener->NodeDeleted(U);
       DeleteNodeNotInCSEMaps(U);
+    } else {
+      // If the node doesn't already exist, we updated it.  Inform a listener if
+      // it exists.
+      if (UpdateListener) 
+        UpdateListener->NodeUpdated(U);
     }
   }
 }
@@ -3259,9 +3277,9 @@ void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To,
 /// number and types of values returned by From.
 void SelectionDAG::ReplaceAllUsesWith(SDNode *From,
                                       const SDOperand *To,
-                                      std::vector<SDNode*> *Deleted) {
+                                      DAGUpdateListener *UpdateListener) {
   if (From->getNumValues() == 1)  // Handle the simple case efficiently.
-    return ReplaceAllUsesWith(SDOperand(From, 0), To[0], Deleted);
+    return ReplaceAllUsesWith(SDOperand(From, 0), To[0], UpdateListener);
 
   while (!From->use_empty()) {
     // Process users until they are all gone.
@@ -3282,35 +3300,67 @@ void SelectionDAG::ReplaceAllUsesWith(SDNode *From,
     // Now that we have modified U, add it back to the CSE maps.  If it already
     // exists there, recursively merge the results together.
     if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) {
-      ReplaceAllUsesWith(U, Existing, Deleted);
-      // U is now dead.
-      if (Deleted) Deleted->push_back(U);
+      ReplaceAllUsesWith(U, Existing, UpdateListener);
+      // U is now dead.  Inform the listener if it exists and delete it.
+      if (UpdateListener) 
+        UpdateListener->NodeDeleted(U);
       DeleteNodeNotInCSEMaps(U);
+    } else {
+      // If the node doesn't already exist, we updated it.  Inform a listener if
+      // it exists.
+      if (UpdateListener) 
+        UpdateListener->NodeUpdated(U);
     }
   }
 }
 
+namespace {
+  /// ChainedSetUpdaterListener - This class is a DAGUpdateListener that removes
+  /// any deleted nodes from the set passed into its constructor and recursively
+  /// notifies another update listener if specified.
+  class ChainedSetUpdaterListener : 
+  public SelectionDAG::DAGUpdateListener {
+    SmallSetVector<SDNode*, 16> &Set;
+    SelectionDAG::DAGUpdateListener *Chain;
+  public:
+    ChainedSetUpdaterListener(SmallSetVector<SDNode*, 16> &set,
+                              SelectionDAG::DAGUpdateListener *chain)
+      : Set(set), Chain(chain) {}
+    
+    virtual void NodeDeleted(SDNode *N) {
+      Set.remove(N);
+      if (Chain) Chain->NodeDeleted(N);
+    }
+    virtual void NodeUpdated(SDNode *N) {
+      if (Chain) Chain->NodeUpdated(N);
+    }
+  };
+}
+
 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
 /// uses of other values produced by From.Val alone.  The Deleted vector is
-/// handled the same was as for ReplaceAllUsesWith.
+/// handled the same way as for ReplaceAllUsesWith.
 void SelectionDAG::ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To,
-                                             std::vector<SDNode*> *Deleted) {
+                                             DAGUpdateListener *UpdateListener){
   assert(From != To && "Cannot replace a value with itself");
+  
   // Handle the simple, trivial, case efficiently.
   if (From.Val->getNumValues() == 1) {
-    ReplaceAllUsesWith(From, To, Deleted);
+    ReplaceAllUsesWith(From, To, UpdateListener);
     return;
   }
-  
+
+  if (From.use_empty()) return;
+
   // Get all of the users of From.Val.  We want these in a nice,
   // deterministically ordered and uniqued set, so we use a SmallSetVector.
   SmallSetVector<SDNode*, 16> Users(From.Val->use_begin(), From.Val->use_end());
 
-  std::vector<SDNode*> LocalDeletionVector;
+  // When one of the recursive merges deletes nodes from the graph, we need to
+  // make sure that UpdateListener is notified *and* that the node is removed
+  // from Users if present.  CSUL does this.
+  ChainedSetUpdaterListener CSUL(Users, UpdateListener);
   
-  // Pick a deletion vector to use.  If the user specified one, use theirs,
-  // otherwise use a local one.
-  std::vector<SDNode*> *DeleteVector = Deleted ? Deleted : &LocalDeletionVector;
   while (!Users.empty()) {
     // We know that this user uses some value of From.  If it is the right
     // value, update it.
@@ -3329,7 +3379,7 @@ void SelectionDAG::ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To,
     // from the CSE maps.
     RemoveNodeFromCSEMaps(User);
     
-    // Update all operands that match "From".
+    // Update all operands that match "From" in case there are multiple uses.
     for (; Op != E; ++Op) {
       if (*Op == From) {
         From.Val->removeUser(User);
@@ -3341,31 +3391,21 @@ void SelectionDAG::ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To,
     // Now that we have modified User, add it back to the CSE maps.  If it
     // already exists there, recursively merge the results together.
     SDNode *Existing = AddNonLeafNodeToCSEMaps(User);
-    if (!Existing) continue;  // Continue on to next user.
+    if (!Existing) {
+      if (UpdateListener) UpdateListener->NodeUpdated(User);
+      continue;  // Continue on to next user.
+    }
     
     // If there was already an existing matching node, use ReplaceAllUsesWith
-    // to replace the dead one with the existing one.  However, this can cause
+    // to replace the dead one with the existing one.  This can cause
     // recursive merging of other unrelated nodes down the line.  The merging
-    // can cause deletion of nodes that used the old value.  In this case,
-    // we have to be certain to remove them from the Users set.
-    unsigned NumDeleted = DeleteVector->size();
-    ReplaceAllUsesWith(User, Existing, DeleteVector);
+    // can cause deletion of nodes that used the old value.  To handle this, we
+    // use CSUL to remove them from the Users set.
+    ReplaceAllUsesWith(User, Existing, &CSUL);
     
-    // User is now dead.
-    DeleteVector->push_back(User);
+    // User is now dead.  Notify a listener if present.
+    if (UpdateListener) UpdateListener->NodeDeleted(User);
     DeleteNodeNotInCSEMaps(User);
-    
-    // We have to be careful here, because ReplaceAllUsesWith could have
-    // deleted a user of From, which means there may be dangling pointers
-    // in the "Users" setvector.  Scan over the deleted node pointers and
-    // remove them from the setvector.
-    for (unsigned i = NumDeleted, e = DeleteVector->size(); i != e; ++i)
-      Users.remove((*DeleteVector)[i]);
-
-    // If the user doesn't need the set of deleted elements, don't retain them
-    // to the next loop iteration.
-    if (Deleted == 0)
-      LocalDeletionVector.clear();
   }
 }