Switch the allnodes list from a vector of pointers to an ilist of nodes.This eliminates the vector, allows constant time removal of a node froma graph, and makes iteration over the all nodes list stable when adding

nodes to the graph.


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

4 files changed, 37 insertions, 46 deletions

diff --git a/lib/CodeGen/SelectionDAG/DAGCombiner.cpp b/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
index 2eca87c730..ca137431a0 100644
--- a/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
+++ b/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
@@ -514,7 +514,9 @@ void DAGCombiner::Run(bool RunningAfterLegalize) {
   AfterLegalize = RunningAfterLegalize;
 
   // Add all the dag nodes to the worklist.
-  WorkList.insert(WorkList.end(), DAG.allnodes_begin(), DAG.allnodes_end());
+  for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(),
+       E = DAG.allnodes_end(); I != E; ++I)
+    WorkList.push_back(I);
   
   // Create a dummy node (which is not added to allnodes), that adds a reference
   // to the root node, preventing it from being deleted, and tracking any
diff --git a/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp b/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
index 874bfafab1..56ab18c773 100644
--- a/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
@@ -394,7 +394,6 @@ static void ComputeTopDownOrdering(SDNode *N, std::vector<SDNode*> &Order,
   
   // Now that we have N in, add anything that uses it if all of their operands
   // are now done.
-  
   for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); UI != E;++UI)
     ComputeTopDownOrdering(*UI, Order, Visited);
 }
@@ -409,19 +408,20 @@ void SelectionDAGLegalize::LegalizeDAG() {
   // node is only legalized after all of its operands are legalized.
   std::map<SDNode*, unsigned> Visited;
   std::vector<SDNode*> Order;
-  Order.reserve(DAG.allnodes_end()-DAG.allnodes_begin());
   
   // Compute ordering from all of the leaves in the graphs, those (like the
   // entry node) that have no operands.
   for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(),
        E = DAG.allnodes_end(); I != E; ++I) {
-    if ((*I)->getNumOperands() == 0) {
-      Visited[*I] = 0 - 1U;
-      ComputeTopDownOrdering(*I, Order, Visited);
+    if (I->getNumOperands() == 0) {
+      Visited[I] = 0 - 1U;
+      ComputeTopDownOrdering(I, Order, Visited);
     }
   }
   
-  assert(Order.size() == Visited.size() && Order.size() == DAG.allnodes_size()&&
+  assert(Order.size() == Visited.size() &&
+         Order.size() == 
+            (unsigned)std::distance(DAG.allnodes_begin(), DAG.allnodes_end()) &&
          "Error: DAG is cyclic!");
   Visited.clear();
   
diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp
index 9abaeefcea..e6f33761e1 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp
@@ -837,21 +837,18 @@ void SimpleSched::FakeGroupDominators() {
 void SimpleSched::PrepareNodeInfo() {
   // Allocate node information
   Info = new NodeInfo[NodeCount];
-  // Get base of all nodes table
-  SelectionDAG::allnodes_iterator AllNodes = DAG.allnodes_begin();
-  
-  // For each node being scheduled
-  for (unsigned i = 0, N = NodeCount; i < N; i++) {
-    // Get next node from DAG all nodes table
-    SDNode *Node = AllNodes[i];
+
+  unsigned i = 0;
+  for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(),
+       E = DAG.allnodes_end(); I != E; ++I, ++i) {
     // Fast reference to node schedule info
     NodeInfo* NI = &Info[i];
     // Set up map
-    Map[Node] = NI;
+    Map[I] = NI;
     // Set node
-    NI->Node = Node;
+    NI->Node = I;
     // Set pending visit count
-    NI->setPending(Node->use_size());    
+    NI->setPending(I->use_size());
   }
 }
 
@@ -1235,7 +1232,7 @@ void SimpleSched::EmitNode(NodeInfo *NI) {
 ///
 void SimpleSched::Schedule() {
   // Number the nodes
-  NodeCount = DAG.allnodes_size();
+  NodeCount = std::distance(DAG.allnodes_begin(), DAG.allnodes_end());
   // Test to see if scheduling should occur
   bool ShouldSchedule = NodeCount > 3 && ScheduleStyle != noScheduling;
   // Set up minimum info for scheduling
diff --git a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
index 0c7473d0a4..3c0baf0563 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
@@ -179,24 +179,20 @@ void SelectionDAG::RemoveDeadNodes(SDNode *N) {
     MadeChange = true;
   }
 
-  for (unsigned i = 0, e = AllNodes.size(); i != e; ++i) {
-    // Try to delete this node.
-    SDNode *N = AllNodes[i];
-    if (N->use_empty() && N->getOpcode() != 65535) {
-      DestroyDeadNode(N);
+  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 (unsigned i = 0, e = AllNodes.size(); i != e; ++i)
-      if (AllNodes[i]->use_empty()) {
-        delete AllNodes[i];
-        AllNodes[i] = AllNodes.back();
-        AllNodes.pop_back();
-        --i; --e;
-      }
+    for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ) {
+      SDNode *N = I++;
+      if (N->use_empty())
+        AllNodes.erase(N);
+    }
   }
   
   // If the root changed (e.g. it was a dead load, update the root).
@@ -244,15 +240,7 @@ void SelectionDAG::DeleteNode(SDNode *N) {
 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
 
   // Remove it from the AllNodes list.
-  for (std::vector<SDNode*>::iterator I = AllNodes.begin(); ; ++I) {
-    assert(I != AllNodes.end() && "Node not in AllNodes list??");
-    if (*I == N) {
-      // Erase from the vector, which is not ordered.
-      std::swap(*I, AllNodes.back());
-      AllNodes.pop_back();
-      break;
-    }
-  }
+  AllNodes.remove(N);
     
   // Drop all of the operands and decrement used nodes use counts.
   for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I)
@@ -431,12 +419,12 @@ SDNode *SelectionDAG::AddNonLeafNodeToCSEMaps(SDNode *N) {
 
 
 SelectionDAG::~SelectionDAG() {
-  for (unsigned i = 0, e = AllNodes.size(); i != e; ++i) {
-    SDNode *N = AllNodes[i];
+  while (!AllNodes.empty()) {
+    SDNode *N = AllNodes.begin();
     delete [] N->OperandList;
     N->OperandList = 0;
     N->NumOperands = 0;
-    delete N;
+    AllNodes.pop_front();
   }
 }
 
@@ -1217,7 +1205,7 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
   case 3: return getNode(Opcode, VT, Ops[0], Ops[1], Ops[2]);
   default: break;
   }
-
+  
   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(Ops[1].Val);
   switch (Opcode) {
   default: break;
@@ -1838,7 +1826,7 @@ void SDNode::dump(const SelectionDAG *G) const {
   }
 }
 
-static void DumpNodes(SDNode *N, unsigned indent, const SelectionDAG *G) {
+static void DumpNodes(const SDNode *N, unsigned indent, const SelectionDAG *G) {
   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
     if (N->getOperand(i).Val->hasOneUse())
       DumpNodes(N->getOperand(i).Val, indent+2, G);
@@ -1853,7 +1841,11 @@ static void DumpNodes(SDNode *N, unsigned indent, const SelectionDAG *G) {
 
 void SelectionDAG::dump() const {
   std::cerr << "SelectionDAG has " << AllNodes.size() << " nodes:";
-  std::vector<SDNode*> Nodes(AllNodes);
+  std::vector<const SDNode*> Nodes;
+  for (allnodes_const_iterator I = allnodes_begin(), E = allnodes_end();
+       I != E; ++I)
+    Nodes.push_back(I);
+  
   std::sort(Nodes.begin(), Nodes.end());
 
   for (unsigned i = 0, e = Nodes.size(); i != e; ++i) {