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 from
a 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@24262 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 52 insertions, 14 deletions

diff --git a/include/llvm/CodeGen/SelectionDAG.h b/include/llvm/CodeGen/SelectionDAG.h
index 81d3d06692..fc8746c116 100644
--- a/include/llvm/CodeGen/SelectionDAG.h
+++ b/include/llvm/CodeGen/SelectionDAG.h
@@ -16,6 +16,8 @@
 #define LLVM_CODEGEN_SELECTIONDAG_H
 
 #include "llvm/CodeGen/SelectionDAGNodes.h"
+#include "llvm/ADT/ilist"
+
 #include <map>
 #include <list>
 #include <string> // FIXME remove eventually, turning map into const char* map.
@@ -43,8 +45,8 @@ class SelectionDAG {
   // Root - The root of the entire DAG.  EntryNode - The starting token.
   SDOperand Root, EntryNode;
 
-  // AllNodes - All of the nodes in the DAG
-  std::vector<SDNode*> AllNodes;
+  // AllNodes - A linked list of nodes in the current DAG.
+  ilist<SDNode> AllNodes;
 
   // ValueNodes - track SrcValue nodes
   std::map<std::pair<const Value*, int>, SDNode*> ValueNodes;
@@ -64,11 +66,13 @@ public:
   void viewGraph();
 
 
-  typedef std::vector<SDNode*>::const_iterator allnodes_iterator;
-  allnodes_iterator allnodes_begin() const { return AllNodes.begin(); }
-  allnodes_iterator allnodes_end() const { return AllNodes.end(); }
-  unsigned allnodes_size() const { return AllNodes.size(); }
-
+  typedef ilist<SDNode>::const_iterator allnodes_const_iterator;
+  allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); }
+  allnodes_const_iterator allnodes_end() const { return AllNodes.end(); }
+  typedef ilist<SDNode>::iterator allnodes_iterator;
+  allnodes_iterator allnodes_begin() { return AllNodes.begin(); }
+  allnodes_iterator allnodes_end() { return AllNodes.end(); }
+  
   /// getRoot - Return the root tag of the SelectionDAG.
   ///
   const SDOperand &getRoot() const { return Root; }
@@ -413,6 +417,6 @@ template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> {
   }
 };
 
-}
+}  // end namespace llvm
 
 #endif
diff --git a/include/llvm/CodeGen/SelectionDAGNodes.h b/include/llvm/CodeGen/SelectionDAGNodes.h
index 2cbca1728e..8088293352 100644
--- a/include/llvm/CodeGen/SelectionDAGNodes.h
+++ b/include/llvm/CodeGen/SelectionDAGNodes.h
@@ -22,7 +22,6 @@
 #include "llvm/CodeGen/ValueTypes.h"
 #include "llvm/Value.h"
 #include "llvm/ADT/GraphTraits.h"
-#include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/iterator"
 #include "llvm/Support/DataTypes.h"
 #include <cassert>
@@ -35,6 +34,9 @@ class GlobalValue;
 class MachineBasicBlock;
 class SDNode;
 template <typename T> struct simplify_type;
+template <typename T> struct ilist_traits;
+template<typename NodeTy, typename Traits> class iplist;
+template<typename NodeTy> class ilist_iterator;
 
 /// ISD namespace - This namespace contains an enum which represents all of the
 /// SelectionDAG node types and value types.
@@ -501,12 +503,20 @@ class SDNode {
 
   /// NumOperands/NumValues - The number of entries in the Operand/Value list.
   unsigned short NumOperands, NumValues;
+  
+  /// Prev/Next pointers - These pointers form the linked list of of the
+  /// AllNodes list in the current DAG.
+  SDNode *Prev, *Next;
+  friend struct ilist_traits<SDNode>;
 
   /// Uses - These are all of the SDNode's that use a value produced by this
   /// node.
   std::vector<SDNode*> Uses;
 public:
-
+  virtual ~SDNode() {
+    assert(NumOperands == 0 && "Operand list not cleared before deletion");
+  }
+  
   //===--------------------------------------------------------------------===//
   //  Accessors
   //
@@ -586,6 +596,7 @@ protected:
     OperandList = 0; NumOperands = 0;
     ValueList = getValueTypeList(VT);
     NumValues = 1;
+    Prev = 0; Next = 0;
   }
   SDNode(unsigned NT, SDOperand Op)
     : NodeType(NT), NodeDepth(Op.Val->getNodeDepth()+1) {
@@ -595,6 +606,7 @@ protected:
     Op.Val->Uses.push_back(this);
     ValueList = 0;
     NumValues = 0;
+    Prev = 0; Next = 0;
   }
   SDNode(unsigned NT, SDOperand N1, SDOperand N2)
     : NodeType(NT) {
@@ -609,6 +621,7 @@ protected:
     N1.Val->Uses.push_back(this); N2.Val->Uses.push_back(this);
     ValueList = 0;
     NumValues = 0;
+    Prev = 0; Next = 0;
   }
   SDNode(unsigned NT, SDOperand N1, SDOperand N2, SDOperand N3)
     : NodeType(NT) {
@@ -629,6 +642,7 @@ protected:
     N3.Val->Uses.push_back(this);
     ValueList = 0;
     NumValues = 0;
+    Prev = 0; Next = 0;
   }
   SDNode(unsigned NT, SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4)
     : NodeType(NT) {
@@ -652,6 +666,7 @@ protected:
     N3.Val->Uses.push_back(this); N4.Val->Uses.push_back(this);
     ValueList = 0;
     NumValues = 0;
+    Prev = 0; Next = 0;
   }
   SDNode(unsigned Opc, const std::vector<SDOperand> &Nodes) : NodeType(Opc) {
     NumOperands = Nodes.size();
@@ -667,10 +682,7 @@ protected:
     NodeDepth = ND+1;
     ValueList = 0;
     NumValues = 0;
-  }
-
-  virtual ~SDNode() {
-    assert(NumOperands == 0 && "Operand list not cleared before deletion");
+    Prev = 0; Next = 0;
   }
 
   /// MorphNodeTo - This clears the return value and operands list, and sets the
@@ -1075,6 +1087,28 @@ template <> struct GraphTraits<SDNode*> {
   }
 };
 
+template<>
+struct ilist_traits<SDNode> {
+  static SDNode *getPrev(const SDNode *N) { return N->Prev; }
+  static SDNode *getNext(const SDNode *N) { return N->Next; }
+  
+  static void setPrev(SDNode *N, SDNode *Prev) { N->Prev = Prev; }
+  static void setNext(SDNode *N, SDNode *Next) { N->Next = Next; }
+  
+  static SDNode *createSentinel() {
+    return new SDNode(ISD::EntryToken, MVT::Other);
+  }
+  static void destroySentinel(SDNode *N) { delete N; }
+  //static SDNode *createNode(const SDNode &V) { return new SDNode(V); }
+  
+  
+  void addNodeToList(SDNode *NTy) {}
+  void removeNodeFromList(SDNode *NTy) {}
+  void transferNodesFromList(iplist<SDNode, ilist_traits> &L2,
+                             const ilist_iterator<SDNode> &X,
+                             const ilist_iterator<SDNode> &Y) {}
+};
+
 } // end llvm namespace
 
 #endif