Changes in directory llvm/lib/CodeGen/SelectionDAG:
LegalizeDAG.cpp updated: 1.383 -> 1.384
SelectionDAG.cpp updated: 1.316 -> 1.317
---
Log message:
Make SelectionDAG::RemoveDeadNodes iterative instead of recursive, which
also make it simpler.
---
Diffs of the changes: (+33 -51)
LegalizeDAG.cpp | 2 -
SelectionDAG.cpp | 82 +++++++++++++++++++++----------------------------------
2 files changed, 33 insertions(+), 51 deletions(-)
Index: llvm/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp:1.383
llvm/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp:1.384
--- llvm/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp:1.383 Wed Jul 26 18:55:56 2006
+++ llvm/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp Fri Aug 4 12:45:20 2006
@@ -349,7 +349,7 @@
PackedNodes.clear();
// Remove dead nodes now.
- DAG.RemoveDeadNodes(OldRoot.Val);
+ DAG.RemoveDeadNodes();
}
Index: llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
diff -u llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp:1.316
llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp:1.317
--- llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp:1.316 Wed Aug 2
17:00:34 2006
+++ llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp Fri Aug 4 12:45:20 2006
@@ -23,6 +23,7 @@
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/ADT/SetVector.h"
+#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringExtras.h"
#include <iostream>
#include <set>
@@ -263,69 +264,50 @@
//===----------------------------------------------------------------------===//
/// RemoveDeadNodes - This method deletes all unreachable nodes in the
-/// SelectionDAG, including nodes (like loads) that have uses of their token
-/// chain but no other uses and no side effect. If a node is passed in as an
-/// argument, it is used as the seed for node deletion.
-void SelectionDAG::RemoveDeadNodes(SDNode *N) {
+/// SelectionDAG.
+void SelectionDAG::RemoveDeadNodes() {
// Create a dummy node (which is not added to allnodes), that adds a
reference
// to the root node, preventing it from being deleted.
HandleSDNode Dummy(getRoot());
- bool MadeChange = false;
+ SmallVector<SDNode*, 128> DeadNodes;
- // If we have a hint to start from, use it.
- if (N && N->use_empty()) {
- DestroyDeadNode(N);
- MadeChange = true;
- }
-
+ // Add all obviously-dead nodes to the DeadNodes worklist.
for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
- if (I->use_empty() && I->getOpcode() != 65535) {
- // Node is dead, recursively delete newly dead uses.
- DestroyDeadNode(I);
- MadeChange = true;
- }
-
- // Walk the nodes list, removing the nodes we've marked as dead.
- if (MadeChange) {
- for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; )
{
- SDNode *N = I++;
- if (N->use_empty())
- AllNodes.erase(N);
+ if (I->use_empty())
+ DeadNodes.push_back(I);
+
+ // Process the worklist, deleting the nodes and adding their uses to the
+ // worklist.
+ while (!DeadNodes.empty()) {
+ SDNode *N = DeadNodes.back();
+ DeadNodes.pop_back();
+
+ // Take the node out of the appropriate CSE map.
+ RemoveNodeFromCSEMaps(N);
+
+ // Next, brutally remove the operand list. This is safe to do, as there
are
+ // no cycles in the graph.
+ for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
+ SDNode *Operand = I->Val;
+ Operand->removeUser(N);
+
+ // Now that we removed this operand, see if there are no uses of it left.
+ if (Operand->use_empty())
+ DeadNodes.push_back(Operand);
}
+ delete[] N->OperandList;
+ N->OperandList = 0;
+ N->NumOperands = 0;
+
+ // Finally, remove N itself.
+ AllNodes.erase(N);
}
// If the root changed (e.g. it was a dead load, update the root).
setRoot(Dummy.getValue());
}
-/// DestroyDeadNode - We know that N is dead. Nuke it from the CSE maps for
the
-/// graph. If it is the last user of any of its operands, recursively process
-/// them the same way.
-///
-void SelectionDAG::DestroyDeadNode(SDNode *N) {
- // Okay, we really are going to delete this node. First take this out of the
- // appropriate CSE map.
- RemoveNodeFromCSEMaps(N);
-
- // Next, brutally remove the operand list. This is safe to do, as there are
- // no cycles in the graph.
- for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
- SDNode *O = I->Val;
- O->removeUser(N);
-
- // Now that we removed this operand, see if there are no uses of it left.
- if (O->use_empty())
- DestroyDeadNode(O);
- }
- delete[] N->OperandList;
- N->OperandList = 0;
- N->NumOperands = 0;
-
- // Mark the node as dead.
- N->MorphNodeTo(65535);
-}
-
void SelectionDAG::DeleteNode(SDNode *N) {
assert(N->use_empty() && "Cannot delete a node that is not dead!");
_______________________________________________
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
