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
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();
}
}