diff --git a/include/llvm/CodeGen/SelectionDAG.h b/include/llvm/CodeGen/SelectionDAG.h
index c1a01ea..2550d64 100644
--- a/include/llvm/CodeGen/SelectionDAG.h
+++ b/include/llvm/CodeGen/SelectionDAG.h
@@ -139,11 +139,6 @@
   /// SelectionDAG.
   void RemoveDeadNodes();
 
-  /// RemoveDeadNode - Remove the specified node from the system. If any of its
-  /// operands then becomes dead, remove them as well. The vector Deleted is
-  /// populated with nodes that are deleted.
-  void RemoveDeadNode(SDNode *N, std::vector<SDNode*> &Deleted);
-  
   /// DeleteNode - Remove the specified node from the system.  This node must
   /// have no referrers.
   void DeleteNode(SDNode *N);
@@ -464,28 +459,41 @@
   SDNode *getTargetNode(unsigned Opcode, std::vector<MVT::ValueType> &ResultTys,
                         const SDOperand *Ops, unsigned NumOps);
   
+  /// DAGUpdateListener - Clients of various APIs that cause global effects on
+  /// the DAG can optionally implement this interface.  This allows the clients
+  /// to handle the various sorts of updates that happen.
+  class DAGUpdateListener {
+  public:
+    virtual ~DAGUpdateListener();
+    virtual void NodeDeleted(SDNode *N) = 0;
+    virtual void NodeUpdated(SDNode *N) = 0;
+  };
+  
+  /// RemoveDeadNode - Remove the specified node from the system. If any of its
+  /// operands then becomes dead, remove them as well. Inform UpdateListener
+  /// for each node deleted.
+  void RemoveDeadNode(SDNode *N, DAGUpdateListener *UpdateListener = 0);
+  
   /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
   /// This can cause recursive merging of nodes in the DAG.  Use the first
   /// version if 'From' is known to have a single result, use the second
   /// if you have two nodes with identical results, use the third otherwise.
   ///
-  /// These methods all take an optional vector, which (if not null) is 
-  /// populated with any nodes that are deleted from the SelectionDAG, due to
-  /// new equivalences that are discovered.
+  /// These methods all take an optional UpdateListener, which (if not null) is 
+  /// informed about nodes that are deleted and modified due to recursive
+  /// changes in the dag.
   ///
   void ReplaceAllUsesWith(SDOperand From, SDOperand Op,
-                          std::vector<SDNode*> *Deleted = 0);
+                          DAGUpdateListener *UpdateListener = 0);
   void ReplaceAllUsesWith(SDNode *From, SDNode *To,
-                          std::vector<SDNode*> *Deleted = 0);
+                          DAGUpdateListener *UpdateListener = 0);
   void ReplaceAllUsesWith(SDNode *From, const SDOperand *To,
-                          std::vector<SDNode*> *Deleted = 0);
+                          DAGUpdateListener *UpdateListener = 0);
 
   /// 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, but it is required for
-  /// this method.
+  /// uses of other values produced by From.Val alone.
   void ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To,
-                                 std::vector<SDNode*> *Deleted = 0);
+                                 DAGUpdateListener *UpdateListener = 0);
 
   /// AssignNodeIds - Assign a unique node id for each node in the DAG based on
   /// their allnodes order. It returns the maximum id.
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 @@
         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 @@
       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 @@
     /// 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 @@
   };
 }
 
+
+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 @@
   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 @@
     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 @@
     // 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 @@
                        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 @@
   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 @@
         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 @@
         // 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 @@
       // 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 @@
   return Res;
 }
 
+SelectionDAG::DAGUpdateListener::~DAGUpdateListener() {}
+
 //===----------------------------------------------------------------------===//
 //                              ConstantFPSDNode Class
 //===----------------------------------------------------------------------===//
@@ -455,7 +457,7 @@
   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 @@
     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 @@
     N->NumOperands = 0;
     
     // Finally, remove N itself.
-    Deleted.push_back(N);
     AllNodes.erase(N);
   }
 }
@@ -3170,13 +3174,14 @@
                  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 @@
     // 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 @@
 /// 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 @@
     // 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 @@
 /// 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 @@
     // 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 @@
     // 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 @@
     // 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();
   }
 }
 
diff --git a/utils/TableGen/DAGISelEmitter.cpp b/utils/TableGen/DAGISelEmitter.cpp
index 493330a..f1829a7 100644
--- a/utils/TableGen/DAGISelEmitter.cpp
+++ b/utils/TableGen/DAGISelEmitter.cpp
@@ -1952,16 +1952,13 @@
      << "// *** instruction selector class.  These functions are really "
      << "methods.\n\n";
   
-  OS << "#include \"llvm/Support/Compiler.h\"\n";
-
   OS << "// Instruction selector priority queue:\n"
      << "std::vector<SDNode*> ISelQueue;\n";
   OS << "/// Keep track of nodes which have already been added to queue.\n"
      << "unsigned char *ISelQueued;\n";
   OS << "/// Keep track of nodes which have already been selected.\n"
      << "unsigned char *ISelSelected;\n";
-  OS << "/// Dummy parameter to ReplaceAllUsesOfValueWith().\n"
-     << "std::vector<SDNode*> ISelKilled;\n\n";
+
 
   OS << "/// IsChainCompatible - Returns true if Chain is Op or Chain does\n";
   OS << "/// not reach Op.\n";
@@ -2009,37 +2006,52 @@
   OS << "  }\n";
   OS << "}\n\n";
 
-  OS << "inline void RemoveKilled() {\n";
-OS << "  unsigned NumKilled = ISelKilled.size();\n";
-  OS << "  if (NumKilled) {\n";
-  OS << "    for (unsigned i = 0; i != NumKilled; ++i) {\n";
-  OS << "      SDNode *Temp = ISelKilled[i];\n";
-  OS << "      ISelQueue.erase(std::remove(ISelQueue.begin(), ISelQueue.end(), "
-     << "Temp), ISelQueue.end());\n";
-  OS << "    };\n";
- OS << "    std::make_heap(ISelQueue.begin(), ISelQueue.end(), isel_sort());\n";
-  OS << "    ISelKilled.clear();\n";
-  OS << "  }\n";
+  
+  OS << "class VISIBILITY_HIDDEN ISelQueueUpdater :\n";
+  OS << "  public SelectionDAG::DAGUpdateListener {\n";
+  OS << "    std::vector<SDNode*> &ISelQueue;\n";
+  OS << "    bool HadDelete;\n";
+  OS << "  public:\n";
+  OS << "    ISelQueueUpdater(std::vector<SDNode*> &isq)\n";
+  OS << "      : ISelQueue(isq), HadDelete(false) {}\n";
+  OS << "    \n";
+  OS << "    bool hadDelete() const { return HadDelete; }\n";
+  OS << "    \n";
+  OS << "    virtual void NodeDeleted(SDNode *N) {\n";
+  OS << "      ISelQueue.erase(std::remove(ISelQueue.begin(), ISelQueue.end(),";
+  OS << " N),\n                      ISelQueue.end());\n";
+  OS << "      HadDelete = true;\n";
+  OS << "    }\n";
+  OS << "    \n";
+  OS << "    // Ignore updates.\n";
+  OS << "    virtual void NodeUpdated(SDNode *N) {}\n";
+  OS << "  };\n";
+  
+  OS << "inline void UpdateQueue(const ISelQueueUpdater &ISQU) {\n";
+  OS << "  if (ISQU.hadDelete())\n";
+  OS << "    std::make_heap(ISelQueue.begin(), ISelQueue.end(),isel_sort());\n";
   OS << "}\n\n";
 
   OS << "void ReplaceUses(SDOperand F, SDOperand T) DISABLE_INLINE {\n";
-  OS << "  CurDAG->ReplaceAllUsesOfValueWith(F, T, &ISelKilled);\n";
+  OS << "  ISelQueueUpdater ISQU(ISelQueue);\n";
+  OS << "  CurDAG->ReplaceAllUsesOfValueWith(F, T, &ISQU);\n";
   OS << "  setSelected(F.Val->getNodeId());\n";
-  OS << "  RemoveKilled();\n";
+  OS << "  UpdateQueue(ISQU);\n";
   OS << "}\n";
   OS << "void ReplaceUses(SDNode *F, SDNode *T) DISABLE_INLINE {\n";
   OS << "  unsigned FNumVals = F->getNumValues();\n";
   OS << "  unsigned TNumVals = T->getNumValues();\n";
+  OS << "  ISelQueueUpdater ISQU(ISelQueue);\n";
   OS << "  if (FNumVals != TNumVals) {\n";
   OS << "    for (unsigned i = 0, e = std::min(FNumVals, TNumVals); "
      << "i < e; ++i)\n";
   OS << "      CurDAG->ReplaceAllUsesOfValueWith(SDOperand(F, i), "
-     << "SDOperand(T, i), &ISelKilled);\n";
+     << "SDOperand(T, i), &ISQU);\n";
   OS << "  } else {\n";
-  OS << "    CurDAG->ReplaceAllUsesWith(F, T, &ISelKilled);\n";
+  OS << "    CurDAG->ReplaceAllUsesWith(F, T, &ISQU);\n";
   OS << "  }\n";
   OS << "  setSelected(F->getNodeId());\n";
-  OS << "  RemoveKilled();\n";
+  OS << "  UpdateQueue(ISQU);\n";
   OS << "}\n\n";
 
   OS << "// SelectRoot - Top level entry to DAG isel.\n";
@@ -2066,8 +2078,9 @@
   OS << "        if (ResNode)\n";
   OS << "          ReplaceUses(Node, ResNode);\n";
   OS << "        if (Node->use_empty()) { // Don't delete EntryToken, etc.\n";
-  OS << "          CurDAG->RemoveDeadNode(Node, ISelKilled);\n";
-  OS << "          RemoveKilled();\n";
+  OS << "          ISelQueueUpdater ISQU(ISelQueue);\n";
+  OS << "          CurDAG->RemoveDeadNode(Node, &ISQU);\n";
+  OS << "          UpdateQueue(ISQU);\n";
   OS << "        }\n";
   OS << "      }\n";
   OS << "    }\n";