Switch over from SelectionNodeCSEMap to FoldingSet.

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

6 files changed, 224 insertions, 548 deletions

diff --git a/include/llvm/CodeGen/MachineConstantPool.h b/include/llvm/CodeGen/MachineConstantPool.h
index 1878b52..17ddcf1 100644
--- a/include/llvm/CodeGen/MachineConstantPool.h
+++ b/include/llvm/CodeGen/MachineConstantPool.h
@@ -15,7 +15,8 @@
 #ifndef LLVM_CODEGEN_MACHINECONSTANTPOOL_H
 #define LLVM_CODEGEN_MACHINECONSTANTPOOL_H
 
-#include "llvm/CodeGen/SelectionDAGCSEMap.h"
+#include "llvm/ADT/FoldingSet.h"
+#include "llvm/CodeGen/SelectionDAGNodes.h"
 #include <vector>
 #include <iosfwd>
 
@@ -43,7 +44,7 @@ public:
   virtual int getExistingMachineCPValue(MachineConstantPool *CP,
                                         unsigned Alignment) = 0;
 
-  virtual void AddSelectionDAGCSEId(SelectionDAGCSEMap::NodeID *Id) = 0;
+  virtual void AddSelectionDAGCSEId(FoldingSetNodeID &ID) = 0;
 
   /// print - Implement operator<<...
   ///
diff --git a/include/llvm/CodeGen/SelectionDAG.h b/include/llvm/CodeGen/SelectionDAG.h
index 6e343bd..58f869d 100644
--- a/include/llvm/CodeGen/SelectionDAG.h
+++ b/include/llvm/CodeGen/SelectionDAG.h
@@ -15,8 +15,9 @@
 #ifndef LLVM_CODEGEN_SELECTIONDAG_H
 #define LLVM_CODEGEN_SELECTIONDAG_H
 
-#include "llvm/CodeGen/SelectionDAGCSEMap.h"
+#include "llvm/ADT/FoldingSet.h"
 #include "llvm/ADT/ilist"
+#include "llvm/CodeGen/SelectionDAGNodes.h"
 
 #include <list>
 #include <vector>
@@ -31,6 +32,7 @@ namespace llvm {
   class MachineDebugInfo;
   class MachineFunction;
   class MachineConstantPoolValue;
+  class SDOperand;
 
 /// SelectionDAG class - This is used to represent a portion of an LLVM function
 /// in a low-level Data Dependence DAG representation suitable for instruction
@@ -56,7 +58,7 @@ class SelectionDAG {
 
   /// CSEMap - This structure is used to memoize nodes, automatically performing
   /// CSE with existing nodes with a duplicate is requested.
-  SelectionDAGCSEMap CSEMap;
+  FoldingSet<SDNode> CSEMap;
 
 public:
   SelectionDAG(TargetLowering &tli, MachineFunction &mf, MachineDebugInfo *di)
diff --git a/include/llvm/CodeGen/SelectionDAGCSEMap.h b/include/llvm/CodeGen/SelectionDAGCSEMap.h
deleted file mode 100644
index 067cf1f..0000000
--- a/include/llvm/CodeGen/SelectionDAGCSEMap.h
+++ /dev/null
@@ -1,129 +0,0 @@
-//===-- llvm/CodeGen/SelectionDAGCSEMap.h - CSE Map for SD ------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file was developed by Chris Lattner and is distributed under
-// the University of Illinois Open Source License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This file declares the SelectionDAG class, and transitively defines the
-// SDNode class and subclasses.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_CODEGEN_SELECTIONDAGCSEMAP_H
-#define LLVM_CODEGEN_SELECTIONDAGCSEMAP_H
-
-#include "llvm/ADT/SmallVector.h"
-#include "llvm/CodeGen/SelectionDAGNodes.h"
-
-namespace llvm {
-  class SDNode;
-  class SDOperand;
-  struct SDVTList;
-  
-  /// SelectionDAGCSEMap - This class is used for two purposes:
-  ///   1. Given information (e.g. opcode and operand info) about a node we want
-  ///      to create, look up the unique instance of the node in the map.  If
-  ///      the node already exists, return it, otherwise return the bucket it
-  ///      should be inserted into.
-  ///   2. Given a node that has already been created, remove it from the CSE
-  ///      map.
-  /// 
-  /// This class is implemented as a chained hash table, where the "buckets" are
-  /// actually the SDNodes themselves (the next pointer is in the SDNode).
-  ///
-  class SelectionDAGCSEMap {
-    void **Buckets;
-    unsigned NumBuckets;  // Always a power of 2.
-    unsigned NumNodes;
-  public:
-    class NodeID;
-    SelectionDAGCSEMap();
-    ~SelectionDAGCSEMap();
-    
-    /// RemoveNode - Remove a node from the CSE map, returning true if one was
-    /// removed or false if the node was not in the CSE map.
-    bool RemoveNode(SDNode *N);
-    
-    /// GetOrInsertSimpleNode - If there is an existing simple SDNode exactly
-    /// equal to the specified node, return it.  Otherwise, insert 'N' and it
-    /// instead.  This only works on *simple* SDNodes, not ConstantSDNode or any
-    /// other classes derived from SDNode.
-    SDNode *GetOrInsertNode(SDNode *N);
-    
-    /// FindNodeOrInsertPos - Look up the node specified by ID.  If it exists,
-    /// return it.  If not, return the insertion token that will make insertion
-    /// faster.
-    SDNode *FindNodeOrInsertPos(const NodeID &ID, void *&InsertPos);
-    
-    /// InsertNode - Insert the specified node into the CSE Map, knowing that it
-    /// is not already in the map.  InsertPos must be obtained from 
-    /// FindNodeOrInsertPos.
-    void InsertNode(SDNode *N, void *InsertPos);
-    
-    class NodeID {
-      /// Use a SmallVector to avoid a heap allocation in the common case.
-      ///
-      SmallVector<unsigned, 32> Bits;
-    public:
-      NodeID() {}
-      NodeID(SDNode *N);
-      NodeID(unsigned short ID, SDVTList VTList);
-      NodeID(unsigned short ID, SDVTList VTList, SDOperand Op);
-      NodeID(unsigned short ID, SDVTList VTList, 
-             SDOperand Op1, SDOperand Op2);
-      NodeID(unsigned short ID, SDVTList VTList, 
-             SDOperand Op1, SDOperand Op2, SDOperand Op3);
-      NodeID(unsigned short ID, SDVTList VTList, 
-             const SDOperand *OpList, unsigned N);
-      
-      void SetOpcode(unsigned short ID) {
-        Bits.push_back(ID);
-      }
-      
-      /// getOpcode - Return the opcode that has been set for this NodeID.
-      ///
-      unsigned getOpcode() const {
-        return Bits[0];
-      }
-
-      void SetValueTypes(SDVTList VTList);
-      void SetOperands() {}
-      void SetOperands(SDOperand Op) { AddOperand(Op); }
-      void SetOperands(SDOperand Op1, SDOperand Op2) {
-        AddOperand(Op1); AddOperand(Op2);
-      }
-      void SetOperands(SDOperand Op1, SDOperand Op2, SDOperand Op3) {
-        AddOperand(Op1); AddOperand(Op2); AddOperand(Op3);
-      }
-      void SetOperands(const SDOperand *Ops, unsigned NumOps);
-      void AddOperand(SDOperand Op);
-      void AddPointer(const void *Ptr);
-      void AddInteger(signed I) {
-        Bits.push_back(I);
-      }
-      void AddInteger(unsigned I) {
-        Bits.push_back(I);
-      }
-      void AddInteger(uint64_t I) {
-        Bits.push_back(unsigned(I));
-        Bits.push_back(unsigned(I >> 32));
-      }
-      
-      unsigned ComputeHash() const;
-      
-      bool operator==(const NodeID &RHS) const;
-    };
-    
-  private:
-    SDNode *GetNextPtr(void *NextInBucketPtr);
-    SDNode *GetNextPtr(void *NextInBucketPtr, void **Buckets, unsigned NumBuck);
-    void **GetBucketPtr(void *NextInBucketPtr);
-    void **GetBucketFor(const NodeID &ID) const;
-    void GrowHashTable();
-  };
-}  // end namespace llvm
-
-#endif
diff --git a/include/llvm/CodeGen/SelectionDAGNodes.h b/include/llvm/CodeGen/SelectionDAGNodes.h
index 18afa69..5dfb280 100644
--- a/include/llvm/CodeGen/SelectionDAGNodes.h
+++ b/include/llvm/CodeGen/SelectionDAGNodes.h
@@ -20,6 +20,7 @@
 #define LLVM_CODEGEN_SELECTIONDAGNODES_H
 
 #include "llvm/Value.h"
+#include "llvm/ADT/FoldingSet.h"
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/iterator"
 #include "llvm/ADT/SmallVector.h"
@@ -742,7 +743,7 @@ template<> struct simplify_type<const SDOperand> {
 
 /// SDNode - Represents one node in the SelectionDAG.
 ///
-class SDNode {
+class SDNode : public FoldingSetNode {
   /// NodeType - The operation that this node performs.
   ///
   unsigned short NodeType;
@@ -766,9 +767,6 @@ class SDNode {
   SDNode *Prev, *Next;
   friend struct ilist_traits<SDNode>;
 
-  /// NextInBucket - This is used by the SelectionDAGCSEMap.
-  void *NextInBucket;
-  
   /// Uses - These are all of the SDNode's that use a value produced by this
   /// node.
   SmallVector<SDNode*,3> Uses;
@@ -778,7 +776,6 @@ class SDNode {
 public:
   virtual ~SDNode() {
     assert(NumOperands == 0 && "Operand list not cleared before deletion");
-    assert(NextInBucket == 0 && "Still in CSEMap?");
     NodeType = ISD::DELETED_NODE;
   }
   
@@ -863,11 +860,10 @@ public:
 
   static bool classof(const SDNode *) { return true; }
 
-  
-  /// NextInBucket accessors, these are private to SelectionDAGCSEMap.
-  void *getNextInBucket() const { return NextInBucket; }
-  void SetNextInBucket(void *N) { NextInBucket = N; }
-  
+  /// Profile - Gather unique data for the node.
+  ///
+  void Profile(FoldingSetNodeID &ID);
+
 protected:
   friend class SelectionDAG;
   
@@ -880,7 +876,6 @@ protected:
     ValueList = getValueTypeList(VT);
     NumValues = 1;
     Prev = 0; Next = 0;
-    NextInBucket = 0;
   }
   SDNode(unsigned NT, SDOperand Op)
     : NodeType(NT), NodeId(-1) {
@@ -891,7 +886,6 @@ protected:
     ValueList = 0;
     NumValues = 0;
     Prev = 0; Next = 0;
-    NextInBucket = 0;
   }
   SDNode(unsigned NT, SDOperand N1, SDOperand N2)
     : NodeType(NT), NodeId(-1) {
@@ -903,7 +897,6 @@ protected:
     ValueList = 0;
     NumValues = 0;
     Prev = 0; Next = 0;
-    NextInBucket = 0;
   }
   SDNode(unsigned NT, SDOperand N1, SDOperand N2, SDOperand N3)
     : NodeType(NT), NodeId(-1) {
@@ -918,7 +911,6 @@ protected:
     ValueList = 0;
     NumValues = 0;
     Prev = 0; Next = 0;
-    NextInBucket = 0;
   }
   SDNode(unsigned NT, SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4)
     : NodeType(NT), NodeId(-1) {
@@ -934,7 +926,6 @@ protected:
     ValueList = 0;
     NumValues = 0;
     Prev = 0; Next = 0;
-    NextInBucket = 0;
   }
   SDNode(unsigned Opc, const SDOperand *Ops, unsigned NumOps)
     : NodeType(Opc), NodeId(-1) {
@@ -949,7 +940,6 @@ protected:
     ValueList = 0;
     NumValues = 0;
     Prev = 0; Next = 0;
-    NextInBucket = 0;
   }
 
   /// MorphNodeTo - This clears the return value and operands list, and sets the
diff --git a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
index 3bd6768..3511b79 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
@@ -252,6 +252,144 @@ const TargetMachine &SelectionDAG::getTarget() const {
 }
 
 //===----------------------------------------------------------------------===//
+//                           SDNode Profile Support
+//===----------------------------------------------------------------------===//
+
+/// getNodeIDOpcode - Return the opcode that has been set for this NodeID.
+///
+static unsigned getNodeIDOpcode(FoldingSetNodeID &ID)  {
+  return ID.getRawData(0);
+}
+static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC)  {
+  ID.AddInteger(OpC);
+}
+
+/// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
+/// solely with their pointer.
+void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
+  ID.AddPointer(VTList.VTs);  
+}
+
+
+static void AddNodeIDOperand(FoldingSetNodeID &ID, SDOperand Op) {
+  ID.AddPointer(Op.Val);
+  ID.AddInteger(Op.ResNo);
+}
+
+static void AddNodeIDOperands(FoldingSetNodeID &ID) {
+}
+void AddNodeIDOperands(FoldingSetNodeID &ID, SDOperand Op) {
+  AddNodeIDOperand(ID, Op);
+}
+static void AddNodeIDOperands(FoldingSetNodeID &ID,
+                             SDOperand Op1, SDOperand Op2) {
+  AddNodeIDOperand(ID, Op1);
+  AddNodeIDOperand(ID, Op2);
+}
+static void AddNodeIDOperands(FoldingSetNodeID &ID,
+                              SDOperand Op1, SDOperand Op2, SDOperand Op3) {
+  AddNodeIDOperand(ID, Op1);
+  AddNodeIDOperand(ID, Op2);
+  AddNodeIDOperand(ID, Op3);
+}
+static void AddNodeIDOperands(FoldingSetNodeID &ID,
+                              const SDOperand *Ops, unsigned NumOps) {
+  for (; NumOps; --NumOps, ++Ops)
+    AddNodeIDOperand(ID, *Ops);
+}
+
+static void AddNodeIDNode(FoldingSetNodeID &ID,
+                          unsigned short OpC, SDVTList VTList) {
+  AddNodeIDOpcode(ID, OpC);
+  AddNodeIDValueTypes(ID, VTList);
+  AddNodeIDOperands(ID);
+}
+static void AddNodeIDNode(FoldingSetNodeID &ID,
+                          unsigned short OpC, SDVTList VTList,
+                          SDOperand Op) {
+  AddNodeIDOpcode(ID, OpC);
+  AddNodeIDValueTypes(ID, VTList);
+  AddNodeIDOperands(ID, Op);
+}
+static void AddNodeIDNode(FoldingSetNodeID &ID,
+                          unsigned short OpC, SDVTList VTList, 
+                          SDOperand Op1, SDOperand Op2) {
+  AddNodeIDOpcode(ID, OpC);
+  AddNodeIDValueTypes(ID, VTList);
+  AddNodeIDOperands(ID, Op1, Op2);
+}
+static void AddNodeIDNode(FoldingSetNodeID &ID,
+                          unsigned short OpC, SDVTList VTList, 
+                          SDOperand Op1, SDOperand Op2, SDOperand Op3) {
+  AddNodeIDOpcode(ID, OpC);
+  AddNodeIDValueTypes(ID, VTList);
+  AddNodeIDOperands(ID, Op1, Op2);
+}
+static void AddNodeIDNode(FoldingSetNodeID &ID,
+                          unsigned short OpC, SDVTList VTList, 
+                          const SDOperand *OpList, unsigned N) {
+  AddNodeIDOpcode(ID, OpC);
+  AddNodeIDValueTypes(ID, VTList);
+  AddNodeIDOperands(ID, OpList, N);
+}
+
+static void AddNodeIDNode(FoldingSetNodeID &ID, SDNode *N) {
+  AddNodeIDOpcode(ID, N->getOpcode());
+  // Add the return value info.
+  AddNodeIDValueTypes(ID, N->getVTList());
+  // Add the operand info.
+  AddNodeIDOperands(ID, N->op_begin(), N->getNumOperands());
+
+  // Handle SDNode leafs with special info.
+  if (N->getNumOperands() == 0) {
+    switch (N->getOpcode()) {
+    default: break;  // Normal nodes don't need extra info.
+    case ISD::TargetConstant:
+    case ISD::Constant:
+      ID.AddInteger(cast<ConstantSDNode>(N)->getValue());
+      break;
+    case ISD::TargetConstantFP:
+    case ISD::ConstantFP:
+      ID.AddDouble(cast<ConstantFPSDNode>(N)->getValue());
+      break;
+    case ISD::TargetGlobalAddress:
+    case ISD::GlobalAddress:
+      ID.AddPointer(cast<GlobalAddressSDNode>(N)->getGlobal());
+      ID.AddInteger(cast<GlobalAddressSDNode>(N)->getOffset());
+      break;
+    case ISD::BasicBlock:
+      ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
+      break;
+    case ISD::Register:
+      ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
+      break;
+    case ISD::SRCVALUE:
+      ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
+      ID.AddInteger(cast<SrcValueSDNode>(N)->getOffset());
+      break;
+    case ISD::FrameIndex:
+    case ISD::TargetFrameIndex:
+      ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
+      break;
+    case ISD::JumpTable:
+    case ISD::TargetJumpTable:
+      ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
+      break;
+    case ISD::ConstantPool:
+    case ISD::TargetConstantPool:
+      ID.AddInteger(cast<ConstantPoolSDNode>(N)->getAlignment());
+      ID.AddInteger(cast<ConstantPoolSDNode>(N)->getOffset());
+      if (cast<ConstantPoolSDNode>(N)->isMachineConstantPoolEntry())
+        cast<ConstantPoolSDNode>(N)->getMachineCPVal()->
+          AddSelectionDAGCSEId(ID);
+      else
+        ID.AddPointer(cast<ConstantPoolSDNode>(N)->getConstVal());
+      break;
+    }
+  }
+}
+
+//===----------------------------------------------------------------------===//
 //                              SelectionDAG Class
 //===----------------------------------------------------------------------===//
 
@@ -439,10 +577,8 @@ SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDOperand Op,
     if (N->getValueType(i) == MVT::Flag)
       return 0;   // Never CSE anything that produces a flag.
   
-  SelectionDAGCSEMap::NodeID ID;
-  ID.SetOpcode(N->getOpcode());
-  ID.SetValueTypes(N->getVTList());
-  ID.SetOperands(Op);
+  FoldingSetNodeID ID;
+  AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Op);
   return CSEMap.FindNodeOrInsertPos(ID, InsertPos);
 }
 
@@ -461,10 +597,8 @@ SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
     if (N->getValueType(i) == MVT::Flag)
       return 0;   // Never CSE anything that produces a flag.
                                               
-  SelectionDAGCSEMap::NodeID ID;
-  ID.SetOpcode(N->getOpcode());
-  ID.SetValueTypes(N->getVTList());
-  ID.SetOperands(Op1, Op2);
+  FoldingSetNodeID ID;
+  AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Op1, Op2);
   return CSEMap.FindNodeOrInsertPos(ID, InsertPos);
 }
 
@@ -484,9 +618,9 @@ SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
     if (N->getValueType(i) == MVT::Flag)
       return 0;   // Never CSE anything that produces a flag.
   
-  SelectionDAGCSEMap::NodeID ID;
-  ID.SetOpcode(N->getOpcode());
-  ID.SetValueTypes(N->getVTList());
+  FoldingSetNodeID ID;
+  AddNodeIDNode(ID, N->getOpcode(), N->getVTList());
+  
   if (const LoadSDNode *LD = dyn_cast<LoadSDNode>(N)) {
     ID.AddInteger(LD->getAddressingMode());
     ID.AddInteger(LD->getExtensionType());
@@ -504,7 +638,8 @@ SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
     ID.AddInteger(ST->getAlignment());
     ID.AddInteger(ST->isVolatile());
   }
-  ID.SetOperands(Ops, NumOps);
+  
+  AddNodeIDOperands(ID, Ops, NumOps);
   return CSEMap.FindNodeOrInsertPos(ID, InsertPos);
 }
 
@@ -544,7 +679,8 @@ SDOperand SelectionDAG::getConstant(uint64_t Val, MVT::ValueType VT, bool isT) {
   Val &= MVT::getIntVTBitMask(VT);
 
   unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
-  SelectionDAGCSEMap::NodeID ID(Opc, getVTList(VT));
+  FoldingSetNodeID ID;
+  AddNodeIDNode(ID, Opc, getVTList(VT));
   ID.AddInteger(Val);
   void *IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
@@ -566,8 +702,9 @@ SDOperand SelectionDAG::getConstantFP(double Val, MVT::ValueType VT,
   // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
   // we don't have issues with SNANs.
   unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
-  SelectionDAGCSEMap::NodeID ID(Opc, getVTList(VT));
-  ID.AddInteger(DoubleToBits(Val));
+  FoldingSetNodeID ID;
+  AddNodeIDNode(ID, Opc, getVTList(VT));
+  ID.AddDouble(Val);
   void *IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDOperand(E, 0);
@@ -581,7 +718,8 @@ SDOperand SelectionDAG::getGlobalAddress(const GlobalValue *GV,
                                          MVT::ValueType VT, int Offset,
                                          bool isTargetGA) {
   unsigned Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
-  SelectionDAGCSEMap::NodeID ID(Opc, getVTList(VT));
+  FoldingSetNodeID ID;
+  AddNodeIDNode(ID, Opc, getVTList(VT));
   ID.AddPointer(GV);
   ID.AddInteger(Offset);
   void *IP = 0;
@@ -596,7 +734,8 @@ SDOperand SelectionDAG::getGlobalAddress(const GlobalValue *GV,
 SDOperand SelectionDAG::getFrameIndex(int FI, MVT::ValueType VT,
                                       bool isTarget) {
   unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
-  SelectionDAGCSEMap::NodeID ID(Opc, getVTList(VT));
+  FoldingSetNodeID ID;
+  AddNodeIDNode(ID, Opc, getVTList(VT));
   ID.AddInteger(FI);
   void *IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
@@ -609,7 +748,8 @@ SDOperand SelectionDAG::getFrameIndex(int FI, MVT::ValueType VT,
 
 SDOperand SelectionDAG::getJumpTable(int JTI, MVT::ValueType VT, bool isTarget){
   unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
-  SelectionDAGCSEMap::NodeID ID(Opc, getVTList(VT));
+  FoldingSetNodeID ID;
+  AddNodeIDNode(ID, Opc, getVTList(VT));
   ID.AddInteger(JTI);
   void *IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
@@ -624,7 +764,8 @@ SDOperand SelectionDAG::getConstantPool(Constant *C, MVT::ValueType VT,
                                         unsigned Alignment, int Offset,
                                         bool isTarget) {
   unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
-  SelectionDAGCSEMap::NodeID ID(Opc, getVTList(VT));
+  FoldingSetNodeID ID;
+  AddNodeIDNode(ID, Opc, getVTList(VT));
   ID.AddInteger(Alignment);
   ID.AddInteger(Offset);
   ID.AddPointer(C);
@@ -643,10 +784,11 @@ SDOperand SelectionDAG::getConstantPool(MachineConstantPoolValue *C,
                                         unsigned Alignment, int Offset,
                                         bool isTarget) {
   unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
-  SelectionDAGCSEMap::NodeID ID(Opc, getVTList(VT));
+  FoldingSetNodeID ID;
+  AddNodeIDNode(ID, Opc, getVTList(VT));
   ID.AddInteger(Alignment);
   ID.AddInteger(Offset);
-  C->AddSelectionDAGCSEId(&ID);
+  C->AddSelectionDAGCSEId(ID);
   void *IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDOperand(E, 0);
@@ -658,7 +800,8 @@ SDOperand SelectionDAG::getConstantPool(MachineConstantPoolValue *C,
 
 
 SDOperand SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
-  SelectionDAGCSEMap::NodeID ID(ISD::BasicBlock, getVTList(MVT::Other));
+  FoldingSetNodeID ID;
+  AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other));
   ID.AddPointer(MBB);
   void *IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
@@ -709,7 +852,8 @@ SDOperand SelectionDAG::getCondCode(ISD::CondCode Cond) {
 }
 
 SDOperand SelectionDAG::getRegister(unsigned RegNo, MVT::ValueType VT) {
-  SelectionDAGCSEMap::NodeID ID(ISD::Register, getVTList(VT));
+  FoldingSetNodeID ID;
+  AddNodeIDNode(ID, ISD::Register, getVTList(VT));
   ID.AddInteger(RegNo);
   void *IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
@@ -724,7 +868,8 @@ SDOperand SelectionDAG::getSrcValue(const Value *V, int Offset) {
   assert((!V || isa<PointerType>(V->getType())) &&
          "SrcValue is not a pointer?");
 
-  SelectionDAGCSEMap::NodeID ID(ISD::SRCVALUE, getVTList(MVT::Other));
+  FoldingSetNodeID ID;
+  AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other));
   ID.AddPointer(V);
   ID.AddInteger(Offset);
   void *IP = 0;
@@ -812,7 +957,8 @@ SDOperand SelectionDAG::FoldSetCC(MVT::ValueType VT, SDOperand N1,
 /// getNode - Gets or creates the specified node.
 ///
 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT) {
-  SelectionDAGCSEMap::NodeID ID(Opcode, getVTList(VT));
+  FoldingSetNodeID ID;
+  AddNodeIDNode(ID, Opcode, getVTList(VT));
   void *IP = 0;
   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDOperand(E, 0);
@@ -991,7 +1137,8 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
   SDNode *N;
   SDVTList VTs = getVTList(VT);
   if (VT != MVT::Flag) { // Don't CSE flag producing nodes
-    SelectionDAGCSEMap::NodeID ID(Opcode, VTs, Operand);
+    FoldingSetNodeID ID;
+    AddNodeIDNode(ID, Opcode, VTs, Operand);
     void *IP = 0;
     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
       return SDOperand(E, 0);
@@ -1291,7 +1438,8 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
   SDNode *N;
   SDVTList VTs = getVTList(VT);
   if (VT != MVT::Flag) {
-    SelectionDAGCSEMap::NodeID ID(Opcode, VTs, N1, N2);
+    FoldingSetNodeID ID;
+    AddNodeIDNode(ID, Opcode, VTs, N1, N2);
     void *IP = 0;
     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
       return SDOperand(E, 0);
@@ -1349,7 +1497,8 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
   SDNode *N;
   SDVTList VTs = getVTList(VT);
   if (VT != MVT::Flag) {
-    SelectionDAGCSEMap::NodeID ID(Opcode, VTs, N1, N2, N3);
+    FoldingSetNodeID ID;
+    AddNodeIDNode(ID, Opcode, VTs, N1, N2, N3);
     void *IP = 0;
     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
       return SDOperand(E, 0);
@@ -1386,7 +1535,8 @@ SDOperand SelectionDAG::getLoad(MVT::ValueType VT,
   unsigned Alignment = 1;
   SDVTList VTs = getVTList(VT, MVT::Other);
   SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType());
-  SelectionDAGCSEMap::NodeID ID(ISD::LOAD, VTs, Chain, Ptr, Undef);
+  FoldingSetNodeID ID;
+  AddNodeIDNode(ID, ISD::LOAD, VTs, Chain, Ptr, Undef);
   ID.AddInteger(ISD::UNINDEXED);
   ID.AddInteger(ISD::NON_EXTLOAD);
   ID.AddInteger(VT);
@@ -1428,7 +1578,8 @@ SDOperand SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, MVT::ValueType VT,
   unsigned Alignment = 1;
   SDVTList VTs = getVTList(VT, MVT::Other);
   SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType());
-  SelectionDAGCSEMap::NodeID ID(ISD::LOAD, VTs, Chain, Ptr, Undef);
+  FoldingSetNodeID ID;
+  AddNodeIDNode(ID, ISD::LOAD, VTs, Chain, Ptr, Undef);
   ID.AddInteger(ISD::UNINDEXED);
   ID.AddInteger(ExtType);
   ID.AddInteger(EVT);
@@ -1454,7 +1605,8 @@ SDOperand SelectionDAG::getIndexedLoad(SDOperand OrigLoad, SDOperand Base,
          "Load is already a indexed load!");
   MVT::ValueType VT = OrigLoad.getValueType();
   SDVTList VTs = getVTList(VT, Base.getValueType(), MVT::Other);
-  SelectionDAGCSEMap::NodeID ID(ISD::LOAD, VTs, LD->getChain(), Base, Offset);
+  FoldingSetNodeID ID;
+  AddNodeIDNode(ID, ISD::LOAD, VTs, LD->getChain(), Base, Offset);
   ID.AddInteger(AM);
   ID.AddInteger(LD->getExtensionType());
   ID.AddInteger(LD->getLoadedVT());
@@ -1493,7 +1645,8 @@ SDOperand SelectionDAG::getStore(SDOperand Chain, SDOperand Value,
   SDVTList VTs = getVTList(MVT::Other);
   SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType());
   SDOperand Ops[] = { Chain, Value, Ptr, Undef };
-  SelectionDAGCSEMap::NodeID ID(ISD::STORE, VTs, Ops, 4);
+  FoldingSetNodeID ID;
+  AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
   ID.AddInteger(ISD::UNINDEXED);
   ID.AddInteger(false);
   ID.AddInteger(VT);
@@ -1528,7 +1681,8 @@ SDOperand SelectionDAG::getTruncStore(SDOperand Chain, SDOperand Value,
   SDVTList VTs = getVTList(MVT::Other);
   SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType());
   SDOperand Ops[] = { Chain, Value, Ptr, Undef };
-  SelectionDAGCSEMap::NodeID ID(ISD::STORE, VTs, Ops, 4);
+  FoldingSetNodeID ID;
+  AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
   ID.AddInteger(ISD::UNINDEXED);
   ID.AddInteger(isTrunc);
   ID.AddInteger(SVT);
@@ -1588,7 +1742,8 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
   SDNode *N;
   SDVTList VTs = getVTList(VT);
   if (VT != MVT::Flag) {
-    SelectionDAGCSEMap::NodeID ID(Opcode, VTs, Ops, NumOps);
+    FoldingSetNodeID ID;
+    AddNodeIDNode(ID, Opcode, VTs, Ops, NumOps);
     void *IP = 0;
     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
       return SDOperand(E, 0);
@@ -1649,10 +1804,8 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList,
   // Memoize the node unless it returns a flag.
   SDNode *N;
   if (VTList.VTs[VTList.NumVTs-1] != MVT::Flag) {
-    SelectionDAGCSEMap::NodeID ID;
-    ID.SetOpcode(Opcode);
-    ID.SetValueTypes(VTList);
-    ID.SetOperands(&Ops[0], NumOps);
+    FoldingSetNodeID ID;
+    AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
     void *IP = 0;
     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
       return SDOperand(E, 0);
@@ -1872,7 +2025,8 @@ UpdateNodeOperands(SDOperand InN, SDOperand *Ops, unsigned NumOps) {
 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
                                    MVT::ValueType VT) {
   SDVTList VTs = getVTList(VT);
-  SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs);
+  FoldingSetNodeID ID;
+  AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs);
   void *IP = 0;
   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
     return ON;
@@ -1890,7 +2044,8 @@ SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
                                    MVT::ValueType VT, SDOperand Op1) {
   // If an identical node already exists, use it.
   SDVTList VTs = getVTList(VT);
-  SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs, Op1);
+  FoldingSetNodeID ID;
+  AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Op1);
   void *IP = 0;
   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
     return ON;
@@ -1908,7 +2063,8 @@ SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
                                    SDOperand Op2) {
   // If an identical node already exists, use it.
   SDVTList VTs = getVTList(VT);
-  SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs, Op1, Op2);
+  FoldingSetNodeID ID;
+  AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs,  Op1, Op2);
   void *IP = 0;
   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
     return ON;
@@ -1927,8 +2083,8 @@ SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
                                    SDOperand Op2, SDOperand Op3) {
   // If an identical node already exists, use it.
   SDVTList VTs = getVTList(VT);
-  SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs,
-                                Op1, Op2, Op3);
+  FoldingSetNodeID ID;
+  AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs,  Op1, Op2, Op3);
   void *IP = 0;
   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
     return ON;
@@ -1947,9 +2103,8 @@ SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
                                    unsigned NumOps) {
   // If an identical node already exists, use it.
   SDVTList VTs = getVTList(VT);
-  SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs);
-  for (unsigned i = 0; i != NumOps; ++i)
-    ID.AddOperand(Ops[i]);
+  FoldingSetNodeID ID;
+  AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, NumOps);
   void *IP = 0;
   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
     return ON;
@@ -1967,7 +2122,8 @@ SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
                                    MVT::ValueType VT1, MVT::ValueType VT2,
                                    SDOperand Op1, SDOperand Op2) {
   SDVTList VTs = getVTList(VT1, VT2);
-  SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs, Op1, Op2);
+  FoldingSetNodeID ID;
+  AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Op1, Op2);
   void *IP = 0;
   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
     return ON;
@@ -1987,8 +2143,8 @@ SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
                                    SDOperand Op3) {
   // If an identical node already exists, use it.
   SDVTList VTs = getVTList(VT1, VT2);
-  SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs,
-                                Op1, Op2, Op3);
+  FoldingSetNodeID ID;
+  AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Op1, Op2, Op3);
   void *IP = 0;
   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
     return ON;
@@ -2311,6 +2467,12 @@ unsigned SelectionDAG::AssignTopologicalOrder(std::vector<SDNode*> &TopOrder) {
 void SDNode::ANCHOR() {
 }
 
+/// Profile - Gather unique data for the node.
+///
+void SDNode::Profile(FoldingSetNodeID &ID) {
+  AddNodeIDNode(ID, this);
+}
+
 /// getValueTypeList - Return a pointer to the specified value type.
 ///
 MVT::ValueType *SDNode::getValueTypeList(MVT::ValueType VT) {
diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGCSEMap.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGCSEMap.cpp
deleted file mode 100644
index 498e9ef..0000000
--- a/lib/CodeGen/SelectionDAG/SelectionDAGCSEMap.cpp
+++ /dev/null
@@ -1,350 +0,0 @@
-//===-- SelectionDAGCSEMap.cpp - Implement the SelectionDAG CSE Map -------===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file was developed by Chris Lattner and is distributed under
-// the University of Illinois Open Source License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This implements the SelectionDAGCSEMap class.
-//
-//===----------------------------------------------------------------------===//
-
-#include "llvm/CodeGen/SelectionDAG.h"
-#include "llvm/CodeGen/MachineConstantPool.h"
-#include "llvm/Support/MathExtras.h"
-using namespace llvm;
-
-//===----------------------------------------------------------------------===//
-// SelectionDAGCSEMap::NodeID Implementation
-
-/// SetValueTypes - Value type lists are intern'd so we can represent them
-/// solely with their pointer.
-void SelectionDAGCSEMap::NodeID::SetValueTypes(SDVTList VTList) {
-  AddPointer(VTList.VTs);  
-}
-
-SelectionDAGCSEMap::NodeID::NodeID(SDNode *N) {
-  SetOpcode(N->getOpcode());
-  // Add the return value info.
-  SetValueTypes(N->getVTList());
-  // Add the operand info.
-  SetOperands(N->op_begin(), N->getNumOperands());
-
-  // Handle SDNode leafs with special info.
-  if (N->getNumOperands() == 0) {
-    switch (N->getOpcode()) {
-    default: break;  // Normal nodes don't need extra info.
-    case ISD::TargetConstant:
-    case ISD::Constant:
-      AddInteger(cast<ConstantSDNode>(N)->getValue());
-      break;
-    case ISD::TargetConstantFP:
-    case ISD::ConstantFP:
-      AddInteger(DoubleToBits(cast<ConstantFPSDNode>(N)->getValue()));
-      break;
-    case ISD::TargetGlobalAddress:
-    case ISD::GlobalAddress:
-      AddPointer(cast<GlobalAddressSDNode>(N)->getGlobal());
-      AddInteger(cast<GlobalAddressSDNode>(N)->getOffset());
-      break;
-    case ISD::BasicBlock:
-      AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
-      break;
-    case ISD::Register:
-      AddInteger(cast<RegisterSDNode>(N)->getReg());
-      break;
-    case ISD::SRCVALUE:
-      AddPointer(cast<SrcValueSDNode>(N)->getValue());
-      AddInteger(cast<SrcValueSDNode>(N)->getOffset());
-      break;
-    case ISD::FrameIndex:
-    case ISD::TargetFrameIndex:
-      AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
-      break;
-    case ISD::JumpTable:
-    case ISD::TargetJumpTable:
-      AddInteger(cast<JumpTableSDNode>(N)->getIndex());
-      break;
-    case ISD::ConstantPool:
-    case ISD::TargetConstantPool:
-      AddInteger(cast<ConstantPoolSDNode>(N)->getAlignment());
-      AddInteger(cast<ConstantPoolSDNode>(N)->getOffset());
-      if (cast<ConstantPoolSDNode>(N)->isMachineConstantPoolEntry())
-        cast<ConstantPoolSDNode>(N)->getMachineCPVal()->
-          AddSelectionDAGCSEId(this);
-      else
-        AddPointer(cast<ConstantPoolSDNode>(N)->getConstVal());
-      break;
-    }
-  }
-}
-
-SelectionDAGCSEMap::NodeID::NodeID(unsigned short ID, SDVTList VTList) {
-  SetOpcode(ID);
-  SetValueTypes(VTList);
-  SetOperands();
-}
-SelectionDAGCSEMap::NodeID::NodeID(unsigned short ID, SDVTList VTList,
-                                   SDOperand Op) {
-  SetOpcode(ID);
-  SetValueTypes(VTList);
-  SetOperands(Op);
-}
-SelectionDAGCSEMap::NodeID::NodeID(unsigned short ID, SDVTList VTList, 
-                                   SDOperand Op1, SDOperand Op2) {
-  SetOpcode(ID);
-  SetValueTypes(VTList);
-  SetOperands(Op1, Op2);
-}
-SelectionDAGCSEMap::NodeID::NodeID(unsigned short ID, SDVTList VTList, 
-                                   SDOperand Op1, SDOperand Op2,
-                                   SDOperand Op3) {
-  SetOpcode(ID);
-  SetValueTypes(VTList);
-  SetOperands(Op1, Op2, Op3);
-}
-SelectionDAGCSEMap::NodeID::NodeID(unsigned short ID, SDVTList VTList, 
-                                   const SDOperand *OpList, unsigned N) {
-  SetOpcode(ID);
-  SetValueTypes(VTList);
-  SetOperands(OpList, N);
-}
-
-void SelectionDAGCSEMap::NodeID::AddPointer(const void *Ptr) {
-  // Note: this adds pointers to the hash using sizes and endianness that depend
-  // on the host.  It doesn't matter however, because hashing on pointer values
-  // in inherently unstable.  Nothing in the SelectionDAG should depend on the
-  // ordering of nodes in the CSEMap.
-  intptr_t PtrI = (intptr_t)Ptr;
-  Bits.push_back(unsigned(PtrI));
-  if (sizeof(intptr_t) > sizeof(unsigned))
-    Bits.push_back(unsigned(uint64_t(PtrI) >> 32));
-}
-
-void SelectionDAGCSEMap::NodeID::AddOperand(SDOperand Op) {
-  AddPointer(Op.Val);
-  Bits.push_back(Op.ResNo);
-}
-
-void SelectionDAGCSEMap::NodeID::SetOperands(const SDOperand *Ops, 
-                                             unsigned NumOps) {
-  for (; NumOps; --NumOps, ++Ops)
-    AddOperand(*Ops);
-}
-
-
-/// ComputeHash - Compute a strong hash value for this NodeID, for lookup in
-/// the SelectionDAGCSEMap.
-unsigned SelectionDAGCSEMap::NodeID::ComputeHash() const {
-  // This is adapted from SuperFastHash by Paul Hsieh.
-  unsigned Hash = Bits.size();
-  for (const unsigned *BP = &Bits[0], *E = BP+Bits.size(); BP != E; ++BP) {
-    unsigned Data = *BP;
-    Hash         += Data & 0xFFFF;
-    unsigned Tmp  = ((Data >> 16) << 11) ^ Hash;
-    Hash          = (Hash << 16) ^ Tmp;
-    Hash         += Hash >> 11;
-  }
-  
-  // Force "avalanching" of final 127 bits.
-  Hash ^= Hash << 3;
-  Hash += Hash >> 5;
-  Hash ^= Hash << 4;
-  Hash += Hash >> 17;
-  Hash ^= Hash << 25;
-  Hash += Hash >> 6;
-  return Hash;
-}
-
-bool SelectionDAGCSEMap::NodeID::operator==(const NodeID &RHS) const {
-  if (Bits.size() != RHS.Bits.size()) return false;
-  return memcmp(&Bits[0], &RHS.Bits[0], Bits.size()*sizeof(Bits[0])) == 0;
-}
-
-
-//===----------------------------------------------------------------------===//
-// SelectionDAGCSEMap Implementation
-
-SelectionDAGCSEMap::SelectionDAGCSEMap() : NumNodes(0) {
-  NumBuckets = 64;
-  Buckets = new void*[NumBuckets];
-  memset(Buckets, 0, NumBuckets*sizeof(void*));
-}
-SelectionDAGCSEMap::~SelectionDAGCSEMap() {
-  delete [] Buckets;
-}
-
-/// GetNextPtr - In order to save space, each bucket is a singly-linked-list. In
-/// order to make deletion more efficient, we make the list circular, so we can
-/// delete a node without computing its hash.  The problem with this is that the
-/// start of the hash buckets are not SDNodes.  If NextInBucketPtr is a bucket
-/// pointer, this method returns null: use GetBucketPtr when this happens.
-SDNode *SelectionDAGCSEMap::GetNextPtr(void *NextInBucketPtr) {
-  if (NextInBucketPtr >= Buckets && NextInBucketPtr < Buckets+NumBuckets)
-    return 0;
-  return static_cast<SDNode*>(NextInBucketPtr);
-}
-
-/// GetNextPtr - This is just like the previous GetNextPtr implementation, but
-/// allows a bucket array to be specified.
-SDNode *SelectionDAGCSEMap::GetNextPtr(void *NextInBucketPtr, void **Bucks, 
-                                       unsigned NumBuck) {
-  if (NextInBucketPtr >= Bucks && NextInBucketPtr < Bucks+NumBuck)
-    return 0;
-  return static_cast<SDNode*>(NextInBucketPtr);
-}
-
-void **SelectionDAGCSEMap::GetBucketPtr(void *NextInBucketPtr) {
-  //assert(NextInBucketPtr >= Buckets && NextInBucketPtr < Buckets+NumBuckets &&
-  //       "NextInBucketPtr is not a bucket ptr");
-  return static_cast<void**>(NextInBucketPtr);
-}
-
-/// GetBucketFor - Hash the specified node ID and return the hash bucket for the
-/// specified ID.
-void **SelectionDAGCSEMap::GetBucketFor(const NodeID &ID) const {
-  // NumBuckets is always a power of 2.
-  unsigned BucketNum = ID.ComputeHash() & (NumBuckets-1);
-  return Buckets+BucketNum;
-}
-
-/// GrowHashTable - Double the size of the hash table and rehash everything.
-///
-void SelectionDAGCSEMap::GrowHashTable() {
-  void **OldBuckets = Buckets;
-  unsigned OldNumBuckets = NumBuckets;
-  NumBuckets <<= 1;
-  
-  // Reset the node count to zero: we're going to reinsert everything.
-  NumNodes = 0;
-  
-  // Clear out new buckets.
-  Buckets = new void*[NumBuckets];
-  memset(Buckets, 0, NumBuckets*sizeof(void*));
-
-  // Walk the old buckets, rehashing nodes into their new place.
-  for (unsigned i = 0; i != OldNumBuckets; ++i) {
-    void *Probe = OldBuckets[i];
-    if (!Probe) continue;
-    while (SDNode *NodeInBucket = GetNextPtr(Probe, OldBuckets, OldNumBuckets)){
-      // Figure out the next link, remove NodeInBucket from the old link.
-      Probe = NodeInBucket->getNextInBucket();
-      NodeInBucket->SetNextInBucket(0);
-
-      // Insert the node into the new bucket, after recomputing the hash.
-      InsertNode(NodeInBucket, GetBucketFor(NodeID(NodeInBucket)));
-    }
-  }
-  
-  delete[] OldBuckets;
-}
-
-/// FindNodeOrInsertPos - Look up the node specified by ID.  If it exists,
-/// return it.  If not, return the insertion token that will make insertion
-/// faster.
-SDNode *SelectionDAGCSEMap::FindNodeOrInsertPos(const NodeID &ID,
-                                                void *&InsertPos) {
-  void **Bucket = GetBucketFor(ID);
-  void *Probe = *Bucket;
-  
-  InsertPos = 0;
-  
-  unsigned Opc = ID.getOpcode();
-  while (SDNode *NodeInBucket = GetNextPtr(Probe)) {
-    // If we found a node with the same opcode, it might be a matching node.
-    // Because it is in the same bucket as this one, we know the hash values
-    // match.  Compute the NodeID for the possible match and do a final compare.
-    if (NodeInBucket->getOpcode() == Opc) {
-      NodeID OtherID(NodeInBucket);
-      if (OtherID == ID)
-        return NodeInBucket;
-    }
-
-    Probe = NodeInBucket->getNextInBucket();
-  }
-  
-  // Didn't find the node, return null with the bucket as the InsertPos.
-  InsertPos = Bucket;
-  return 0;
-}
-
-/// InsertNode - Insert the specified node into the CSE Map, knowing that it
-/// is not already in the map.  InsertPos must be obtained from 
-/// FindNodeOrInsertPos.
-void SelectionDAGCSEMap::InsertNode(SDNode *N, void *InsertPos) {
-  ++NumNodes;
-  // Do we need to grow the hashtable?
-  if (NumNodes > NumBuckets*2) {
-    GrowHashTable();
-    InsertPos = GetBucketFor(NodeID(N));
-  }
-  
-  /// The insert position is actually a bucket pointer.
-  void **Bucket = static_cast<void**>(InsertPos);
-  
-  void *Next = *Bucket;
-  
-  // If this is the first insertion into this bucket, its next pointer will be
-  // null.  Pretend as if it pointed to itself.
-  if (Next == 0)
-    Next = Bucket;
-
-  // Set the nodes next pointer, and make the bucket point to the node.
-  N->SetNextInBucket(Next);
-  *Bucket = N;
-}
-
-
-/// RemoveNode - Remove a node from the CSE map, returning true if one was
-/// removed or false if the node was not in the CSE map.
-bool SelectionDAGCSEMap::RemoveNode(SDNode *N) {
-
-  // Because each bucket is a circular list, we don't need to compute N's hash
-  // to remove it.  Chase around the list until we find the node (or bucket)
-  // which points to N.
-  void *Ptr = N->getNextInBucket();
-  if (Ptr == 0) return false;  // Not in CSEMap.
-
-  --NumNodes;
-
-  void *NodeNextPtr = Ptr;
-  N->SetNextInBucket(0);
-  while (1) {
-    if (SDNode *NodeInBucket = GetNextPtr(Ptr)) {
-      // Advance pointer.
-      Ptr = NodeInBucket->getNextInBucket();
-      
-      // We found a node that points to N, change it to point to N's next node,
-      // removing N from the list.
-      if (Ptr == N) {
-        NodeInBucket->SetNextInBucket(NodeNextPtr);
-        return true;
-      }
-    } else {
-      void **Bucket = GetBucketPtr(Ptr);
-      Ptr = *Bucket;
-      
-      // If we found that the bucket points to N, update the bucket to point to
-      // whatever is next.
-      if (Ptr == N) {
-        *Bucket = NodeNextPtr;
-        return true;
-      }
-    }
-  }
-}
-
-/// GetOrInsertSimpleNode - If there is an existing simple SDNode exactly
-/// equal to the specified node, return it.  Otherwise, insert 'N' and it
-/// instead.  This only works on *simple* SDNodes, not ConstantSDNode or any
-/// other classes derived from SDNode.
-SDNode *SelectionDAGCSEMap::GetOrInsertNode(SDNode *N) {
-  SelectionDAGCSEMap::NodeID ID(N);
-  void *IP;
-  if (SDNode *E = FindNodeOrInsertPos(ID, IP))
-    return E;
-  InsertNode(N, IP);
-  return N;
-}