[Review Request] Numbering SDNode to discard SmallPtrSet in selection DAG

[shawfly]

Summary

In selection DAG, SmallPtrSet is widely used to indicate the existence of SDNode in a set when traversing the DAG. This consumes 3~5% of total compilation time. SmallPtrSet is a good data structure, but it is not suitable here; by numbering the SDNode, it can be done in O(1) to indicate whether a SDNode is visited or not.

Each SDNode belongs to a Selection DAG, in this patch, SDNode is numbered according to its belonged Selection DAG. This patch could improve llc performance by 2.5-3% for SpecCPU2006.

[bkramer]

Some high level comments:

• SmallPtrSet is usually O(1) but falls back to linear search when it's small. SmallPtrSet<64> is way too large, have you benchmarked with the small capacity lowered to 8 or 16? This of course adds malloc overhead in more cases but we might get away with it.

If the above fails:

• I really don't see the point of FlagVector. Why not just use a SmallVector (or SmallBitVector as we're only storing bools) and resize appropriately when it's used. In any case, the class does not belong in SmallVector.h.

[shawfly]

Thanks for your review.

1. SmallBitVector can meet what FlagVector can after some minor changes, but for the convenience of review, I don't want to change it since it is a common container which is used by most people, I will change to use SmallBitVector instead of FlagVector.

2. SmallBitVector is usually O(1), but the overhead to construct this set is hot, the insert_impl is very hot.

[cid:image001.png@01CE7F3B.A70406A0]

• {F9266, layout=link}

[mehdi_amini]

include/llvm/CodeGen/SelectionDAGNodes.h

964

Minor comment if you update this revision: variable should start with an uppercase: s/ownerDAG/OwnerDAG/

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

900

Why 1? I would have expected 0 here?

lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp

549

No need for else here after continue.

include/llvm/ADT/SmallVector.h

 
 namespace llvm {
 
+/// FlagVector is a class to contain simple type element, such as bool, int, etc.
+/// [] operation is safe for any > 0 index since it will expand according to the index
+/// it is mainly used to indicate the existence of one element in a set.
+template <typename T, unsigned SmallSize>
+class FlagVector {
+public:
+  // Default ctor - Initialize to empty.
+  explicit FlagVector() {
+    BeginX = SmallStorage;
+    Size = 0;
+    Capacity = SmallSize;
+    memset(BeginX, 0, sizeof(T) * Capacity);
+  }
+private:
+  T SmallStorage[SmallSize];
+  T *BeginX;
+  size_t Size, Capacity;
+
+public:
+  ~FlagVector() {
+    if (BeginX != SmallStorage) {
+      free(BeginX);
+    }
+  }
+
+  size_t size() const { return Size; }
+
+  void push_back(T val) {
+    assert(Size < Capacity);
+    this->operator[](Size++) = val;
+  }
+
+  void reserve(unsigned N) {
+    if (Capacity < N) {
+      this->grow(N);
+    }
+  }
+
+  T& operator[](unsigned idx) {
+    if (idx >= Capacity) {
+      grow(idx + 1);
+    } 
+    if (idx >= Size) {
+      Size = idx + 1;
+    }
+    return BeginX[idx];
+  }
+
+  const T& operator[](unsigned idx) const {
+    if (idx >= Capacity) {
+      grow(idx + 1);
+    }
+    if (idx >= Size) {
+      Size = idx + 1;
+    }
+    return BeginX[idx];
+  }
+
+private:
+  void grow(size_t NewSize) {
+    if (NewSize <= Capacity) {
+      return;
+    }
+    while (Capacity <= NewSize) {
+      Capacity = Capacity << 1;
+    }
+
+    T *NewElts = static_cast<T*>(malloc(Capacity * sizeof(T)));
+    memcpy(NewElts, BeginX, Size * sizeof(T));
+    memset(NewElts + Size, 0, (Capacity - Size) * sizeof(T));
+    if (BeginX != SmallStorage) {
+      free(BeginX);
+    }
+    BeginX = NewElts;
+  }
+
+  void reset() {
+    memset(BeginX, 0, sizeof(T) * Size);
+  }
+
+  void resize(unsigned N) {
+    if (N < Size) {
+      Size = N;
+      memset(BeginX + Size, 0, sizeof(T) * (Capacity - Size));
+    } else if (Capacity < N) {
+      this->grow(N);
+    }
+  }
+};
+
 /// SmallVectorBase - This is all the non-templated stuff common to all
 /// SmallVectors.
 class SmallVectorBase {

include/llvm/CodeGen/SelectionDAG.h

 /// but is significantly more simple, powerful, and is a graph form instead of a
 /// linear form.
 ///
-class SelectionDAG {
+class SelectionDAG : public SDContext {
   const TargetMachine &TM;
   const TargetSelectionDAGInfo &TSI;
   const TargetTransformInfo *TTI;

include/llvm/CodeGen/SelectionDAGNodes.h

 
 void checkForCycles(const SDNode *N);
 
+/// SDContext provide the interface to number the SDNode in a selection DAG
+class SDContext {
+protected:
+  /// SDNode counter in a DAG, to facilitating the numbering of SDNode.
+  int SDNodeCount;
+  SDContext() : SDNodeCount(0) {}
+public:
+  int SDNodeNumber() { return SDNodeCount++; }
+};
+
 /// SDVTList - This represents a list of ValueType's that has been intern'd by
 /// a SelectionDAG.  Instances of this simple value class are returned by
 /// SelectionDAG::getVTList(...).

   friend struct ilist_traits<SDNode>;
 
 public:
+  // The unique number for a SDNode in a selection DAG
+  // SDNode is numbered from 0 incrementally in one DAG
+  int SeqPos;
   //===--------------------------------------------------------------------===//
   //  Accessors
   //

     return Ret;
   }
 
-  SDNode(unsigned Opc, unsigned Order, const DebugLoc dl, SDVTList VTs,
+  SDNode(SDContext *ownerDAG, unsigned Opc, unsigned Order, const DebugLoc dl, SDVTList VTs,
          const SDValue *Ops, unsigned NumOps)
     : NodeType(Opc), OperandsNeedDelete(true), HasDebugValue(false),
       SubclassData(0), NodeId(-1),

       ValueList(VTs.VTs), UseList(NULL),
       NumOperands(NumOps), NumValues(VTs.NumVTs),
       debugLoc(dl), IROrder(Order) {
+    assert(ownerDAG && "SDNode is created with a null ownerDAG!");
+    SeqPos = ownerDAG->SDNodeNumber();
     for (unsigned i = 0; i != NumOps; ++i) {
       OperandList[i].setUser(this);
       OperandList[i].setInitial(Ops[i]);

 
   /// This constructor adds no operands itself; operands can be
   /// set later with InitOperands.
-  SDNode(unsigned Opc, unsigned Order, const DebugLoc dl, SDVTList VTs)
+  SDNode(SDContext *ownerDAG, unsigned Opc, unsigned Order, const DebugLoc dl, SDVTList VTs)
     : NodeType(Opc), OperandsNeedDelete(false), HasDebugValue(false),
       SubclassData(0), NodeId(-1), OperandList(0),
       ValueList(VTs.VTs), UseList(NULL), NumOperands(0), NumValues(VTs.NumVTs),
-      debugLoc(dl), IROrder(Order) {}
+      debugLoc(dl), IROrder(Order) {
+    assert(ownerDAG && "SDNode is created with a null ownerDAG!");
+    SeqPos = ownerDAG->SDNodeNumber();
+  }
 
   /// InitOperands - Initialize the operands list of this with 1 operand.
   void InitOperands(SDUse *Ops, const SDValue &Op0) {

 class UnarySDNode : public SDNode {
   SDUse Op;
 public:
-  UnarySDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs, SDValue X)
-    : SDNode(Opc, Order, dl, VTs) {
+  UnarySDNode(SDContext *ownerDAG, unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs, SDValue X)
+    : SDNode(ownerDAG, Opc, Order, dl, VTs) {
     InitOperands(&Op, X);
   }
 };

 class BinarySDNode : public SDNode {
   SDUse Ops[2];
 public:
-  BinarySDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs, SDValue X, SDValue Y)
-    : SDNode(Opc, Order, dl, VTs) {
+  BinarySDNode(SDContext *ownerDAG, unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs, SDValue X, SDValue Y)
+    : SDNode(ownerDAG, Opc, Order, dl, VTs) {
     InitOperands(Ops, X, Y);
   }
 };

 class TernarySDNode : public SDNode {
   SDUse Ops[3];
 public:
-  TernarySDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
+  TernarySDNode(SDContext *ownerDAG, unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
                 SDValue X, SDValue Y, SDValue Z)
-    : SDNode(Opc, Order, dl, VTs) {
+    : SDNode(ownerDAG, Opc, Order, dl, VTs) {
     InitOperands(Ops, X, Y, Z);
   }
 };

 #if __GNUC__==4 && __GNUC_MINOR__==2 && defined(__APPLE__) && !defined(__llvm__)
   explicit __attribute__((__noinline__)) HandleSDNode(SDValue X)
 #else
-  explicit HandleSDNode(SDValue X)
+  explicit HandleSDNode(SDContext *ownerDAG, SDValue X)
 #endif
-    : SDNode(ISD::HANDLENODE, 0, DebugLoc(), getSDVTList(MVT::Other)) {
+    : SDNode(ownerDAG, ISD::HANDLENODE, 0, DebugLoc(), getSDVTList(MVT::Other)) {
     InitOperands(&Op, X);
   }
   ~HandleSDNode();

   MachineMemOperand *MMO;
 
 public:
-  MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
+  MemSDNode(SDContext *ownerDAG, unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
             EVT MemoryVT, MachineMemOperand *MMO);
 
-  MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs, const SDValue *Ops,
+  MemSDNode(SDContext *ownerDAG, unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs, const SDValue *Ops,
             unsigned NumOps, EVT MemoryVT, MachineMemOperand *MMO);
 
   bool readMem() const { return MMO->isLoad(); }

   // Swp:    swap value
   // SrcVal: address to update as a Value (used for MemOperand)
   // Align:  alignment of memory
-  AtomicSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTL, EVT MemVT,
+  AtomicSDNode(SDContext *ownerDAG, unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTL, EVT MemVT,
                SDValue Chain, SDValue Ptr,
                SDValue Cmp, SDValue Swp, MachineMemOperand *MMO,
                AtomicOrdering Ordering, SynchronizationScope SynchScope)
-    : MemSDNode(Opc, Order, dl, VTL, MemVT, MMO) {
+    : MemSDNode(ownerDAG, Opc, Order, dl, VTL, MemVT, MMO) {
     InitAtomic(Ordering, SynchScope);
     InitOperands(Ops, Chain, Ptr, Cmp, Swp);
   }
-  AtomicSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTL, EVT MemVT,
+  AtomicSDNode(SDContext *ownerDAG, unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTL, EVT MemVT,
                SDValue Chain, SDValue Ptr,
                SDValue Val, MachineMemOperand *MMO,
                AtomicOrdering Ordering, SynchronizationScope SynchScope)
-    : MemSDNode(Opc, Order, dl, VTL, MemVT, MMO) {
+    : MemSDNode(ownerDAG, Opc, Order, dl, VTL, MemVT, MMO) {
     InitAtomic(Ordering, SynchScope);
     InitOperands(Ops, Chain, Ptr, Val);
   }
-  AtomicSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTL, EVT MemVT,
+  AtomicSDNode(SDContext *ownerDAG, unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTL, EVT MemVT,
                SDValue Chain, SDValue Ptr,
                MachineMemOperand *MMO,
                AtomicOrdering Ordering, SynchronizationScope SynchScope)
-    : MemSDNode(Opc, Order, dl, VTL, MemVT, MMO) {
+    : MemSDNode(ownerDAG, Opc, Order, dl, VTL, MemVT, MMO) {
     InitAtomic(Ordering, SynchScope);
     InitOperands(Ops, Chain, Ptr);
   }

 /// with a value not less than FIRST_TARGET_MEMORY_OPCODE.
 class MemIntrinsicSDNode : public MemSDNode {
 public:
-  MemIntrinsicSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
+  MemIntrinsicSDNode(SDContext *ownerDAG, unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
                      const SDValue *Ops, unsigned NumOps,
                      EVT MemoryVT, MachineMemOperand *MMO)
-    : MemSDNode(Opc, Order, dl, VTs, Ops, NumOps, MemoryVT, MMO) {
+    : MemSDNode(ownerDAG, Opc, Order, dl, VTs, Ops, NumOps, MemoryVT, MMO) {
   }
 
   // Methods to support isa and dyn_cast

   const int *Mask;
 protected:
   friend class SelectionDAG;
-  ShuffleVectorSDNode(EVT VT, unsigned Order, DebugLoc dl, SDValue N1, SDValue N2, const int *M)
-    : SDNode(ISD::VECTOR_SHUFFLE, Order, dl, getSDVTList(VT)), Mask(M) {
+  ShuffleVectorSDNode(SDContext *ownerDAG, EVT VT, unsigned Order, DebugLoc dl, SDValue N1, SDValue N2, const int *M)
+    : SDNode(ownerDAG, ISD::VECTOR_SHUFFLE, Order, dl, getSDVTList(VT)), Mask(M) {
     InitOperands(Ops, N1, N2);
   }
 public:

 class ConstantSDNode : public SDNode {
   const ConstantInt *Value;
   friend class SelectionDAG;
-  ConstantSDNode(bool isTarget, const ConstantInt *val, EVT VT)
-    : SDNode(isTarget ? ISD::TargetConstant : ISD::Constant,
+  ConstantSDNode(SDContext *ownerDAG, bool isTarget, const ConstantInt *val, EVT VT)
+    : SDNode(ownerDAG, isTarget ? ISD::TargetConstant : ISD::Constant,
              0, DebugLoc(), getSDVTList(VT)), Value(val) {
   }
 public:

 class ConstantFPSDNode : public SDNode {
   const ConstantFP *Value;
   friend class SelectionDAG;
-  ConstantFPSDNode(bool isTarget, const ConstantFP *val, EVT VT)
-    : SDNode(isTarget ? ISD::TargetConstantFP : ISD::ConstantFP,
+  ConstantFPSDNode(SDContext *ownerDAG, bool isTarget, const ConstantFP *val, EVT VT)
+    : SDNode(ownerDAG, isTarget ? ISD::TargetConstantFP : ISD::ConstantFP,
              0, DebugLoc(), getSDVTList(VT)), Value(val) {
   }
 public:

   int64_t Offset;
   unsigned char TargetFlags;
   friend class SelectionDAG;
-  GlobalAddressSDNode(unsigned Opc, unsigned Order, DebugLoc DL, const GlobalValue *GA, EVT VT,
+  GlobalAddressSDNode(SDContext *ownerDAG, unsigned Opc, unsigned Order, DebugLoc DL, const GlobalValue *GA, EVT VT,
                       int64_t o, unsigned char TargetFlags);
 public:
 

 class FrameIndexSDNode : public SDNode {
   int FI;
   friend class SelectionDAG;
-  FrameIndexSDNode(int fi, EVT VT, bool isTarg)
-    : SDNode(isTarg ? ISD::TargetFrameIndex : ISD::FrameIndex,
+  FrameIndexSDNode(SDContext *ownerDAG, int fi, EVT VT, bool isTarg)
+    : SDNode(ownerDAG, isTarg ? ISD::TargetFrameIndex : ISD::FrameIndex,
       0, DebugLoc(), getSDVTList(VT)), FI(fi) {
   }
 public:

   int JTI;
   unsigned char TargetFlags;
   friend class SelectionDAG;
-  JumpTableSDNode(int jti, EVT VT, bool isTarg, unsigned char TF)
-    : SDNode(isTarg ? ISD::TargetJumpTable : ISD::JumpTable,
+  JumpTableSDNode(SDContext *ownerDAG, int jti, EVT VT, bool isTarg, unsigned char TF)
+    : SDNode(ownerDAG, isTarg ? ISD::TargetJumpTable : ISD::JumpTable,
       0, DebugLoc(), getSDVTList(VT)), JTI(jti), TargetFlags(TF) {
   }
 public:

   unsigned Alignment;  // Minimum alignment requirement of CP (not log2 value).
   unsigned char TargetFlags;
   friend class SelectionDAG;
-  ConstantPoolSDNode(bool isTarget, const Constant *c, EVT VT, int o,
+  ConstantPoolSDNode(SDContext *ownerDAG, bool isTarget, const Constant *c, EVT VT, int o,
                      unsigned Align, unsigned char TF)
-    : SDNode(isTarget ? ISD::TargetConstantPool : ISD::ConstantPool, 0, DebugLoc(),
+    : SDNode(ownerDAG, isTarget ? ISD::TargetConstantPool : ISD::ConstantPool, 0, DebugLoc(),
              getSDVTList(VT)), Offset(o), Alignment(Align), TargetFlags(TF) {
     assert(Offset >= 0 && "Offset is too large");
     Val.ConstVal = c;
   }
-  ConstantPoolSDNode(bool isTarget, MachineConstantPoolValue *v,
+  ConstantPoolSDNode(SDContext *ownerDAG, bool isTarget, MachineConstantPoolValue *v,
                      EVT VT, int o, unsigned Align, unsigned char TF)
-    : SDNode(isTarget ? ISD::TargetConstantPool : ISD::ConstantPool, 0, DebugLoc(),
+    : SDNode(ownerDAG, isTarget ? ISD::TargetConstantPool : ISD::ConstantPool, 0, DebugLoc(),
              getSDVTList(VT)), Offset(o), Alignment(Align), TargetFlags(TF) {
     assert(Offset >= 0 && "Offset is too large");
     Val.MachineCPVal = v;

   friend class SelectionDAG;
 public:
 
-  TargetIndexSDNode(int Idx, EVT VT, int64_t Ofs, unsigned char TF)
-    : SDNode(ISD::TargetIndex, 0, DebugLoc(), getSDVTList(VT)),
+  TargetIndexSDNode(SDContext *ownerDAG, int Idx, EVT VT, int64_t Ofs, unsigned char TF)
+    : SDNode(ownerDAG, ISD::TargetIndex, 0, DebugLoc(), getSDVTList(VT)),
       TargetFlags(TF), Index(Idx), Offset(Ofs) {}
 public:
 

   /// Debug info is meaningful and potentially useful here, but we create
   /// blocks out of order when they're jumped to, which makes it a bit
   /// harder.  Let's see if we need it first.
-  explicit BasicBlockSDNode(MachineBasicBlock *mbb)
-    : SDNode(ISD::BasicBlock, 0, DebugLoc(), getSDVTList(MVT::Other)), MBB(mbb) {
+  explicit BasicBlockSDNode(SDContext *ownerDAG, MachineBasicBlock *mbb)
+    : SDNode(ownerDAG, ISD::BasicBlock, 0, DebugLoc(), getSDVTList(MVT::Other)), MBB(mbb) {
   }
 public:
 

   const Value *V;
   friend class SelectionDAG;
   /// Create a SrcValue for a general value.
-  explicit SrcValueSDNode(const Value *v)
-    : SDNode(ISD::SRCVALUE, 0, DebugLoc(), getSDVTList(MVT::Other)), V(v) {}
+  explicit SrcValueSDNode(SDContext *ownerDAG, const Value *v)
+    : SDNode(ownerDAG, ISD::SRCVALUE, 0, DebugLoc(), getSDVTList(MVT::Other)), V(v) {}
 
 public:
   /// getValue - return the contained Value.

 class MDNodeSDNode : public SDNode {
   const MDNode *MD;
   friend class SelectionDAG;
-  explicit MDNodeSDNode(const MDNode *md)
-  : SDNode(ISD::MDNODE_SDNODE, 0, DebugLoc(), getSDVTList(MVT::Other)), MD(md) {}
+  explicit MDNodeSDNode(SDContext *ownerDAG, const MDNode *md)
+  : SDNode(ownerDAG, ISD::MDNODE_SDNODE, 0, DebugLoc(), getSDVTList(MVT::Other)), MD(md) {}
 public:
   
   const MDNode *getMD() const { return MD; }

 class RegisterSDNode : public SDNode {
   unsigned Reg;
   friend class SelectionDAG;
-  RegisterSDNode(unsigned reg, EVT VT)
-    : SDNode(ISD::Register, 0, DebugLoc(), getSDVTList(VT)), Reg(reg) {
+  RegisterSDNode(SDContext *ownerDAG, unsigned reg, EVT VT)
+    : SDNode(ownerDAG, ISD::Register, 0, DebugLoc(), getSDVTList(VT)), Reg(reg) {
   }
 public:
 

   // The memory for RegMask is not owned by the node.
   const uint32_t *RegMask;
   friend class SelectionDAG;
-  RegisterMaskSDNode(const uint32_t *mask)
-    : SDNode(ISD::RegisterMask, 0, DebugLoc(), getSDVTList(MVT::Untyped)),
+  RegisterMaskSDNode(SDContext *ownerDAG, const uint32_t *mask)
+    : SDNode(ownerDAG, ISD::RegisterMask, 0, DebugLoc(), getSDVTList(MVT::Untyped)),
       RegMask(mask) {}
 public:
 

   int64_t Offset;
   unsigned char TargetFlags;
   friend class SelectionDAG;
-  BlockAddressSDNode(unsigned NodeTy, EVT VT, const BlockAddress *ba,
+  BlockAddressSDNode(SDContext *ownerDAG, unsigned NodeTy, EVT VT, const BlockAddress *ba,
                      int64_t o, unsigned char Flags)
-    : SDNode(NodeTy, 0, DebugLoc(), getSDVTList(VT)),
+    : SDNode(ownerDAG, NodeTy, 0, DebugLoc(), getSDVTList(VT)),
              BA(ba), Offset(o), TargetFlags(Flags) {
   }
 public:

   SDUse Chain;
   MCSymbol *Label;
   friend class SelectionDAG;
-  EHLabelSDNode(unsigned Order, DebugLoc dl, SDValue ch, MCSymbol *L)
-    : SDNode(ISD::EH_LABEL, Order, dl, getSDVTList(MVT::Other)), Label(L) {
+  EHLabelSDNode(SDContext *ownerDAG, unsigned Order, DebugLoc dl, SDValue ch, MCSymbol *L)
+    : SDNode(ownerDAG, ISD::EH_LABEL, Order, dl, getSDVTList(MVT::Other)), Label(L) {
     InitOperands(&Chain, ch);
   }
 public:

   unsigned char TargetFlags;
   
   friend class SelectionDAG;
-  ExternalSymbolSDNode(bool isTarget, const char *Sym, unsigned char TF, EVT VT)
-    : SDNode(isTarget ? ISD::TargetExternalSymbol : ISD::ExternalSymbol,
+  ExternalSymbolSDNode(SDContext *ownerDAG, bool isTarget, const char *Sym, unsigned char TF, EVT VT)
+    : SDNode(ownerDAG, isTarget ? ISD::TargetExternalSymbol : ISD::ExternalSymbol,
              0, DebugLoc(), getSDVTList(VT)), Symbol(Sym), TargetFlags(TF) {
   }
 public:

 class CondCodeSDNode : public SDNode {
   ISD::CondCode Condition;
   friend class SelectionDAG;
-  explicit CondCodeSDNode(ISD::CondCode Cond)
-    : SDNode(ISD::CONDCODE, 0, DebugLoc(), getSDVTList(MVT::Other)),
+  explicit CondCodeSDNode(SDContext *ownerDAG, ISD::CondCode Cond)
+    : SDNode(ownerDAG, ISD::CONDCODE, 0, DebugLoc(), getSDVTList(MVT::Other)),
       Condition(Cond) {
   }
 public:

 class CvtRndSatSDNode : public SDNode {
   ISD::CvtCode CvtCode;
   friend class SelectionDAG;
-  explicit CvtRndSatSDNode(EVT VT, unsigned Order, DebugLoc dl, const SDValue *Ops,
+  explicit CvtRndSatSDNode(SDContext *ownerDAG, EVT VT, unsigned Order, DebugLoc dl, const SDValue *Ops,
                            unsigned NumOps, ISD::CvtCode Code)
-    : SDNode(ISD::CONVERT_RNDSAT, Order, dl, getSDVTList(VT), Ops, NumOps),
+    : SDNode(ownerDAG, ISD::CONVERT_RNDSAT, Order, dl, getSDVTList(VT), Ops, NumOps),
       CvtCode(Code) {
     assert(NumOps == 5 && "wrong number of operations");
   }

 class VTSDNode : public SDNode {
   EVT ValueType;
   friend class SelectionDAG;
-  explicit VTSDNode(EVT VT)
-    : SDNode(ISD::VALUETYPE, 0, DebugLoc(), getSDVTList(MVT::Other)),
+  explicit VTSDNode(SDContext *ownerDAG, EVT VT)
+    : SDNode(ownerDAG, ISD::VALUETYPE, 0, DebugLoc(), getSDVTList(MVT::Other)),
       ValueType(VT) {
   }
 public:

    */
   SDUse Ops[4];
 public:
-  LSBaseSDNode(ISD::NodeType NodeTy, unsigned Order, DebugLoc dl, SDValue *Operands,
+  LSBaseSDNode(SDContext *ownerDAG, ISD::NodeType NodeTy, unsigned Order, DebugLoc dl, SDValue *Operands,
                unsigned numOperands, SDVTList VTs, ISD::MemIndexedMode AM,
                EVT MemVT, MachineMemOperand *MMO)
-    : MemSDNode(NodeTy, Order, dl, VTs, MemVT, MMO) {
+    : MemSDNode(ownerDAG, NodeTy, Order, dl, VTs, MemVT, MMO) {
     SubclassData |= AM << 2;
     assert(getAddressingMode() == AM && "MemIndexedMode encoding error!");
     InitOperands(Ops, Operands, numOperands);

 ///
 class LoadSDNode : public LSBaseSDNode {
   friend class SelectionDAG;
-  LoadSDNode(SDValue *ChainPtrOff, unsigned Order, DebugLoc dl, SDVTList VTs,
+  LoadSDNode(SDContext *ownerDAG, SDValue *ChainPtrOff, unsigned Order, DebugLoc dl, SDVTList VTs,
              ISD::MemIndexedMode AM, ISD::LoadExtType ETy, EVT MemVT,
              MachineMemOperand *MMO)
-    : LSBaseSDNode(ISD::LOAD, Order, dl, ChainPtrOff, 3, VTs, AM, MemVT, MMO) {
+    : LSBaseSDNode(ownerDAG, ISD::LOAD, Order, dl, ChainPtrOff, 3, VTs, AM, MemVT, MMO) {
     SubclassData |= (unsigned short)ETy;
     assert(getExtensionType() == ETy && "LoadExtType encoding error!");
     assert(readMem() && "Load MachineMemOperand is not a load!");

 ///
 class StoreSDNode : public LSBaseSDNode {
   friend class SelectionDAG;
-  StoreSDNode(SDValue *ChainValuePtrOff, unsigned Order, DebugLoc dl,
+  StoreSDNode(SDContext *ownerDAG, SDValue *ChainValuePtrOff, unsigned Order, DebugLoc dl,
               SDVTList VTs, ISD::MemIndexedMode AM, bool isTrunc, EVT MemVT,
               MachineMemOperand *MMO)
-    : LSBaseSDNode(ISD::STORE, Order, dl, ChainValuePtrOff, 4,
+    : LSBaseSDNode(ownerDAG, ISD::STORE, Order, dl, ChainValuePtrOff, 4,
                    VTs, AM, MemVT, MMO) {
     SubclassData |= (unsigned short)isTrunc;
     assert(isTruncatingStore() == isTrunc && "isTrunc encoding error!");

 
 private:
   friend class SelectionDAG;
-  MachineSDNode(unsigned Opc, unsigned Order, const DebugLoc DL, SDVTList VTs)
-    : SDNode(Opc, Order, DL, VTs), MemRefs(0), MemRefsEnd(0) {}
+  MachineSDNode(SDContext *ownerDAG, unsigned Opc, unsigned Order, const DebugLoc DL, SDVTList VTs)
+    : SDNode(ownerDAG, Opc, Order, DL, VTs), MemRefs(0), MemRefsEnd(0) {}
 
   /// LocalOperands - Operands for this instruction, if they fit here. If
   /// they don't, this field is unused.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

     // contain duplicate or removed nodes. When choosing a node to
     // visit, we pop off the order stack until we find an item that is
     // also in the contents set. All operations are O(log N).
-    SmallPtrSet<SDNode*, 64> WorkListContents;
-    SmallVector<SDNode*, 64> WorkListOrder;
+    // Each DAG node has a UID, use a flag vector to indicate whether it is visited
+    FlagVector<bool, 128> WorkListFlag;
+    SmallVector<SDNode*, 128> WorkListOrder;
 
     // AA - Used for DAG load/store alias analysis.
     AliasAnalysis &AA;

     /// AddToWorkList - Add to the work list making sure its instance is at the
     /// back (next to be processed.)
     void AddToWorkList(SDNode *N) {
-      WorkListContents.insert(N);
+      WorkListFlag[N->SeqPos] = true;
       WorkListOrder.push_back(N);
     }
 

     /// removeFromWorkList - remove all instances of N from the worklist.
     ///
     void removeFromWorkList(SDNode *N) {
-      WorkListContents.erase(N);
+      WorkListFlag[N->SeqPos] = false;
     }
 
     SDValue CombineTo(SDNode *N, const SDValue *To, unsigned NumTo,

   LegalOperations = Level >= AfterLegalizeVectorOps;
   LegalTypes = Level >= AfterLegalizeTypes;
 
+  WorkListOrder.reserve(DAG.allnodes_size());
+  WorkListFlag.reserve(DAG.allnodes_size());
+
   // Add all the dag nodes to the worklist.
   for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(),
        E = DAG.allnodes_end(); I != E; ++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
   // changes of the root.
-  HandleSDNode Dummy(DAG.getRoot());
+  HandleSDNode Dummy(&DAG, DAG.getRoot());
 
   // The root of the dag may dangle to deleted nodes until the dag combiner is
   // done.  Set it to null to avoid confusion.

 
   // while the worklist isn't empty, find a node and
   // try and combine it.
-  while (!WorkListContents.empty()) {
+  while (!WorkListOrder.empty()) {
     SDNode *N;
     // The WorkListOrder holds the SDNodes in order, but it may contain duplicates.
     // In order to avoid a linear scan, we use a set (O(log N)) to hold what the
     // worklist *should* contain, and check the node we want to visit is should
     // actually be visited.
-    do {
-      N = WorkListOrder.pop_back_val();
-    } while (!WorkListContents.erase(N));
+    N = WorkListOrder.pop_back_val();
+    if (!WorkListFlag[N->SeqPos]) {
+      continue;
+    }
+    WorkListFlag[N->SeqPos] = false;
 
     // If N has no uses, it is dead.  Make sure to revisit all N's operands once
     // N is deleted from the DAG, since they too may now be dead or may have a

 
   SmallVector<SDNode *, 8> TFs;     // List of token factors to visit.
   SmallVector<SDValue, 8> Ops;    // Ops for replacing token factor.
-  SmallPtrSet<SDNode*, 16> SeenOps;
+  FlagVector<bool, 128> SeenOps;
   bool Changed = false;             // If we should replace this token factor.
 
   // Start out with this token factor.

 
       default:
         // Only add if it isn't already in the list.
-        if (SeenOps.insert(Op.getNode()))
+        if (!SeenOps[Op.getNode()->SeqPos]) {
+          SeenOps[Op.getNode()->SeqPos] = true;
           Ops.push_back(Op);
-        else
+        } else {
           Changed = true;
+        }
         break;
       }
     }

lib/CodeGen/SelectionDAG/LegalizeDAG.cpp

   SelectionDAG::allnodes_iterator LegalizePosition;
 
   /// LegalizedNodes - The set of nodes which have already been legalized.
-  SmallPtrSet<SDNode *, 16> LegalizedNodes;
+  FlagVector<bool, 128> LegalizedNodes; 
+  // Each DAG node has a UID, use a flag vector to indicate whether it is legalized
 
   EVT getSetCCResultType(EVT VT) const {
     return TLI.getSetCCResultType(*DAG.getContext(), VT);

   void PromoteNode(SDNode *Node);
 
   void ForgetNode(SDNode *N) {
-    LegalizedNodes.erase(N);
+    LegalizedNodes[N->SeqPos] = false;
     if (LegalizePosition == SelectionDAG::allnodes_iterator(N))
       ++LegalizePosition;
   }

       --LegalizePosition;
 
       SDNode *N = LegalizePosition;
-      if (LegalizedNodes.insert(N)) {
+      if (!LegalizedNodes[N->SeqPos]) {
+        LegalizedNodes[N->SeqPos] = true;
         AnyLegalized = true;
         LegalizeOp(N);
       }

         SDValue SAO =
           DAG.getShiftAmountOperand(Node->getOperand(0).getValueType(),
                                     Node->getOperand(1));
-        HandleSDNode Handle(SAO);
+        HandleSDNode Handle(&DAG, SAO);
         LegalizeOp(SAO.getNode());
         NewNode = DAG.UpdateNodeOperands(Node, Node->getOperand(0),
                                          Handle.getValue());

         SDValue SAO =
           DAG.getShiftAmountOperand(Node->getOperand(0).getValueType(),
                                     Node->getOperand(2));
-        HandleSDNode Handle(SAO);
+        HandleSDNode Handle(&DAG, SAO);
         LegalizeOp(SAO.getNode());
         NewNode = DAG.UpdateNodeOperands(Node, Node->getOperand(0),
                                          Node->getOperand(1),

                                   DAG.getEntryNode(), CPIdx,
                                   MachinePointerInfo::getConstantPool(),
                                   MVT::f32, false, false, Alignment);
-    HandleSDNode Handle(Load);
+    HandleSDNode Handle(&DAG, Load);
     LegalizeOp(Load.getNode());
     FudgeInReg = Handle.getValue();
   }

lib/CodeGen/SelectionDAG/LegalizeTypes.cpp

   // 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
   // changes of the root.
-  HandleSDNode Dummy(DAG.getRoot());
+  HandleSDNode Dummy(&DAG, DAG.getRoot());
   Dummy.setNodeId(Unanalyzed);
 
   // The root of the dag may dangle to deleted nodes until the type legalizer is

lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp

 
   // Look for other loads of the same chain. Find loads that are loading from
   // the same base pointer and different offsets.
-  SmallPtrSet<SDNode*, 16> Visited;
+  FlagVector<bool, 64> Visited;
+  // Each DAG node has a UID, use a flag vector to indicate whether it is visited
   SmallVector<int64_t, 4> Offsets;
   DenseMap<long long, SDNode*> O2SMap;  // Map from offset to SDNode.
   bool Cluster = false;

   for (SDNode::use_iterator I = Chain->use_begin(), E = Chain->use_end();
        I != E; ++I) {
     SDNode *User = *I;
-    if (User == Node || !Visited.insert(User))
+    if (User == Node)
       continue;
+    if (Visited[User->SeqPos]) {
+      continue;
+    }
+    Visited[User->SeqPos] = true;
     int64_t Offset1, Offset2;
     if (!TII->areLoadsFromSameBasePtr(Base, User, Offset1, Offset2) ||
         Offset1 == Offset2)

 
   // Add all nodes in depth first order.
   SmallVector<SDNode*, 64> Worklist;
-  SmallPtrSet<SDNode*, 64> Visited;
+  // Each DAG node has a UID, use a flag vector to indicate whether it is visited
+  FlagVector<bool, 64> WorkListFlag;
   Worklist.push_back(DAG->getRoot().getNode());
-  Visited.insert(DAG->getRoot().getNode());
+  WorkListFlag[DAG->getRoot().getNode()->SeqPos] = true;
 
   SmallVector<SUnit*, 8> CallSUnits;
   while (!Worklist.empty()) {

     SDNode *NI = Worklist.pop_back_val();
 
     // Add all operands to the worklist unless they've already been added.
-    for (unsigned i = 0, e = NI->getNumOperands(); i != e; ++i)
-      if (Visited.insert(NI->getOperand(i).getNode()))
+    for (unsigned i = 0, e = NI->getNumOperands(); i != e; ++i) {
+      if (!WorkListFlag[NI->getOperand(i).getNode()->SeqPos]) {
         Worklist.push_back(NI->getOperand(i).getNode());
+        WorkListFlag[NI->getOperand(i).getNode()->SeqPos] = true;
+      }
+    }
 
     if (isPassiveNode(NI))  // Leaf node, e.g. a TargetImmediate.
       continue;

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

 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());
+  HandleSDNode Dummy(this, getRoot());
 
   SmallVector<SDNode*, 128> DeadNodes;
 

   // Create a dummy node that adds a reference to the root node, preventing
   // it from being deleted.  (This matters if the root is an operand of the
   // dead node.)
-  HandleSDNode Dummy(getRoot());
+  HandleSDNode Dummy(this, getRoot());
 
   RemoveDeadNodes(DeadNodes);
 }

 // EntryNode could meaningfully have debug info if we can find it...
 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
   : TM(tm), TSI(*tm.getSelectionDAGInfo()), TTI(0), OptLevel(OL),
-    EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
+    EntryNode(this, ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
     Root(getEntryNode()), UpdateListeners(0) {
   AllNodes.push_back(&EntryNode);
   DbgInfo = new SDDbgInfo();

 }
 
 SelectionDAG::~SelectionDAG() {
+  SDNodeCount = 0;
   assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
   allnodes_clear();
   delete DbgInfo;

 }
 
 void SelectionDAG::clear() {
+  SDNodeCount = 1;
   allnodes_clear();
   OperandAllocator.Reset();
   CSEMap.clear();

       return SDValue(N, 0);
 
   if (!N) {
-    N = new (NodeAllocator) ConstantSDNode(isT, Elt, EltVT);
+    N = new (NodeAllocator) ConstantSDNode(this, isT, Elt, EltVT);
     CSEMap.InsertNode(N, IP);
     AllNodes.push_back(N);
   }

       return SDValue(N, 0);
 
   if (!N) {
-    N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, EltVT);
+    N = new (NodeAllocator) ConstantFPSDNode(this, isTarget, &V, EltVT);
     CSEMap.InsertNode(N, IP);
     AllNodes.push_back(N);
   }

   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDValue(E, 0);
 
-  SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
+  SDNode *N = new (NodeAllocator) GlobalAddressSDNode(this, Opc, DL.getIROrder(),
                                                       DL.getDebugLoc(), GV, VT,
                                                       Offset, TargetFlags);
   CSEMap.InsertNode(N, IP);

   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDValue(E, 0);
 
-  SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
+  SDNode *N = new (NodeAllocator) FrameIndexSDNode(this, FI, VT, isTarget);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);
   return SDValue(N, 0);

   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDValue(E, 0);
 
-  SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
+  SDNode *N = new (NodeAllocator) JumpTableSDNode(this, JTI, VT, isTarget,
                                                   TargetFlags);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);

   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDValue(E, 0);
 
-  SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
+  SDNode *N = new (NodeAllocator) ConstantPoolSDNode(this, isTarget, C, VT, Offset,
                                                      Alignment, TargetFlags);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);

   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDValue(E, 0);
 
-  SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
+  SDNode *N = new (NodeAllocator) ConstantPoolSDNode(this, isTarget, C, VT, Offset,
                                                      Alignment, TargetFlags);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);

   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDValue(E, 0);
 
-  SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
+  SDNode *N = new (NodeAllocator) TargetIndexSDNode(this, Index, VT, Offset,
                                                     TargetFlags);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);

   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDValue(E, 0);
 
-  SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
+  SDNode *N = new (NodeAllocator) BasicBlockSDNode(this, MBB);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);
   return SDValue(N, 0);

     ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
 
   if (N) return SDValue(N, 0);
-  N = new (NodeAllocator) VTSDNode(VT);
+  N = new (NodeAllocator) VTSDNode(this, VT);
   AllNodes.push_back(N);
   return SDValue(N, 0);
 }

 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
   SDNode *&N = ExternalSymbols[Sym];
   if (N) return SDValue(N, 0);
-  N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
+  N = new (NodeAllocator) ExternalSymbolSDNode(this, false, Sym, 0, VT);
   AllNodes.push_back(N);
   return SDValue(N, 0);
 }

     TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
                                                                TargetFlags)];
   if (N) return SDValue(N, 0);
-  N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
+  N = new (NodeAllocator) ExternalSymbolSDNode(this, true, Sym, TargetFlags, VT);
   AllNodes.push_back(N);
   return SDValue(N, 0);
 }

     CondCodeNodes.resize(Cond+1);
 
   if (CondCodeNodes[Cond] == 0) {
-    CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
+    CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(this, Cond);
     CondCodeNodes[Cond] = N;
     AllNodes.push_back(N);
   }

   memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
 
   ShuffleVectorSDNode *N =
-    new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(), dl.getDebugLoc(), N1, N2, MaskAlloc);
+    new (NodeAllocator) ShuffleVectorSDNode(this, VT, dl.getIROrder(), dl.getDebugLoc(), N1, N2, MaskAlloc);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);
   return SDValue(N, 0);

   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDValue(E, 0);
 
-  CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(), dl.getDebugLoc(), Ops, 5,
+  CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(this, VT, dl.getIROrder(), dl.getDebugLoc(), Ops, 5,
                                                            Code);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);

   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDValue(E, 0);
 
-  SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
+  SDNode *N = new (NodeAllocator) RegisterSDNode(this, RegNo, VT);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);
   return SDValue(N, 0);

   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDValue(E, 0);
 
-  SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
+  SDNode *N = new (NodeAllocator) RegisterMaskSDNode(this, RegMask);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);
   return SDValue(N, 0);

   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDValue(E, 0);
 
-  SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(), dl.getDebugLoc(), Root, Label);
+  SDNode *N = new (NodeAllocator) EHLabelSDNode(this, dl.getIROrder(), dl.getDebugLoc(), Root, Label);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);
   return SDValue(N, 0);

   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDValue(E, 0);
 
-  SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
+  SDNode *N = new (NodeAllocator) BlockAddressSDNode(this, Opc, VT, BA, Offset,
                                                      TargetFlags);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);

   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDValue(E, 0);
 
-  SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
+  SDNode *N = new (NodeAllocator) SrcValueSDNode(this, V);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);
   return SDValue(N, 0);

   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDValue(E, 0);
 
-  SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
+  SDNode *N = new (NodeAllocator) MDNodeSDNode(this, MD);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);
   return SDValue(N, 0);

   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDValue(E, 0);
 
-  SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), getVTList(VT));
+  SDNode *N = new (NodeAllocator) SDNode(this, Opcode, DL.getIROrder(), DL.getDebugLoc(), getVTList(VT));
   CSEMap.InsertNode(N, IP);
 
   AllNodes.push_back(N);

     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
       return SDValue(E, 0);
 
-    N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, Operand);
+    N = new (NodeAllocator) UnarySDNode(this, Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, Operand);
     CSEMap.InsertNode(N, IP);
   } else {
-    N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, Operand);
+    N = new (NodeAllocator) UnarySDNode(this, Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, Operand);
   }
 
   AllNodes.push_back(N);

     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
       return SDValue(E, 0);
 
-    N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
+    N = new (NodeAllocator) BinarySDNode(this, Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
     CSEMap.InsertNode(N, IP);
   } else {
-    N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
+    N = new (NodeAllocator) BinarySDNode(this, Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
   }
 
   AllNodes.push_back(N);

     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
       return SDValue(E, 0);
 
-    N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2, N3);
+    N = new (NodeAllocator) TernarySDNode(this, Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2, N3);
     CSEMap.InsertNode(N, IP);
   } else {
-    N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2, N3);
+    N = new (NodeAllocator) TernarySDNode(this, Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2, N3);
   }
 
   AllNodes.push_back(N);

     cast<AtomicSDNode>(E)->refineAlignment(MMO);
     return SDValue(E, 0);
   }
-  SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(), dl.getDebugLoc(), VTs, MemVT, Chain,
+  SDNode *N = new (NodeAllocator) AtomicSDNode(this, Opcode, dl.getIROrder(), dl.getDebugLoc(), VTs, MemVT, Chain,
                                                Ptr, Cmp, Swp, MMO, Ordering,
                                                SynchScope);
   CSEMap.InsertNode(N, IP);

     cast<AtomicSDNode>(E)->refineAlignment(MMO);
     return SDValue(E, 0);
   }
-  SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(), dl.getDebugLoc(), VTs, MemVT, Chain,
+  SDNode *N = new (NodeAllocator) AtomicSDNode(this, Opcode, dl.getIROrder(), dl.getDebugLoc(), VTs, MemVT, Chain,
                                                Ptr, Val, MMO,
                                                Ordering, SynchScope);
   CSEMap.InsertNode(N, IP);

     cast<AtomicSDNode>(E)->refineAlignment(MMO);
     return SDValue(E, 0);
   }
-  SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(), dl.getDebugLoc(), VTs, MemVT, Chain,
+  SDNode *N = new (NodeAllocator) AtomicSDNode(this, Opcode, dl.getIROrder(), dl.getDebugLoc(), VTs, MemVT, Chain,
                                                Ptr, MMO, Ordering, SynchScope);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);

       return SDValue(E, 0);
     }
 
-    N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(), dl.getDebugLoc(), VTList, Ops, NumOps,
+    N = new (NodeAllocator) MemIntrinsicSDNode(this, Opcode, dl.getIROrder(), dl.getDebugLoc(), VTList, Ops, NumOps,
                                                MemVT, MMO);
     CSEMap.InsertNode(N, IP);
   } else {
-    N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(), dl.getDebugLoc(), VTList, Ops, NumOps,
+    N = new (NodeAllocator) MemIntrinsicSDNode(this, Opcode, dl.getIROrder(), dl.getDebugLoc(), VTList, Ops, NumOps,
                                                MemVT, MMO);
   }
   AllNodes.push_back(N);

     cast<LoadSDNode>(E)->refineAlignment(MMO);
     return SDValue(E, 0);
   }
-  SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(), dl.getDebugLoc(), VTs, AM, ExtType,
+  SDNode *N = new (NodeAllocator) LoadSDNode(this, Ops, dl.getIROrder(), dl.getDebugLoc(), VTs, AM, ExtType,
                                              MemVT, MMO);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);

     cast<StoreSDNode>(E)->refineAlignment(MMO);
     return SDValue(E, 0);
   }
-  SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(), dl.getDebugLoc(), VTs, ISD::UNINDEXED,
+  SDNode *N = new (NodeAllocator) StoreSDNode(this, Ops, dl.getIROrder(), dl.getDebugLoc(), VTs, ISD::UNINDEXED,
                                               false, VT, MMO);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);

     cast<StoreSDNode>(E)->refineAlignment(MMO);
     return SDValue(E, 0);
   }
-  SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(), dl.getDebugLoc(), VTs, ISD::UNINDEXED,
+  SDNode *N = new (NodeAllocator) StoreSDNode(this, Ops, dl.getIROrder(), dl.getDebugLoc(), VTs, ISD::UNINDEXED,
                                               true, SVT, MMO);
   CSEMap.InsertNode(N, IP);
   AllNodes.push_back(N);

   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
     return SDValue(E, 0);
 
-  SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(), dl.getDebugLoc(), VTs, AM,
+  SDNode *N = new (NodeAllocator) StoreSDNode(this, Ops, dl.getIROrder(), dl.getDebugLoc(), VTs, AM,
                                               ST->isTruncatingStore(),
                                               ST->getMemoryVT(),
                                               ST->getMemOperand());

     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
       return SDValue(E, 0);
 
-    N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, Ops, NumOps);
+    N = new (NodeAllocator) SDNode(this, Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, Ops, NumOps);
     CSEMap.InsertNode(N, IP);
   } else {
-    N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, Ops, NumOps);
+    N = new (NodeAllocator) SDNode(this, Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, Ops, NumOps);
   }
 
   AllNodes.push_back(N);

       return SDValue(E, 0);
 
     if (NumOps == 1) {
-      N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTList, Ops[0]);
+      N = new (NodeAllocator) UnarySDNode(this, Opcode, DL.getIROrder(), DL.getDebugLoc(), VTList, Ops[0]);
     } else if (NumOps == 2) {
-      N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTList, Ops[0], Ops[1]);
+      N = new (NodeAllocator) BinarySDNode(this, Opcode, DL.getIROrder(), DL.getDebugLoc(), VTList, Ops[0], Ops[1]);
     } else if (NumOps == 3) {
-      N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTList, Ops[0], Ops[1],
+      N = new (NodeAllocator) TernarySDNode(this, Opcode, DL.getIROrder(), DL.getDebugLoc(), VTList, Ops[0], Ops[1],
                                             Ops[2]);
     } else {
-      N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTList, Ops, NumOps);
+      N = new (NodeAllocator) SDNode(this, Opcode, DL.getIROrder(), DL.getDebugLoc(), VTList, Ops, NumOps);
     }
     CSEMap.InsertNode(N, IP);
   } else {
     if (NumOps == 1) {
-      N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTList, Ops[0]);
+      N = new (NodeAllocator) UnarySDNode(this, Opcode, DL.getIROrder(), DL.getDebugLoc(), VTList, Ops[0]);
     } else if (NumOps == 2) {
-      N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTList, Ops[0], Ops[1]);
+      N = new (NodeAllocator) BinarySDNode(this, Opcode, DL.getIROrder(), DL.getDebugLoc(), VTList, Ops[0], Ops[1]);
     } else if (NumOps == 3) {
-      N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTList, Ops[0], Ops[1],
+      N = new (NodeAllocator) TernarySDNode(this, Opcode, DL.getIROrder(), DL.getDebugLoc(), VTList, Ops[0], Ops[1],
                                             Ops[2]);
     } else {
-      N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTList, Ops, NumOps);
+      N = new (NodeAllocator) SDNode(this, Opcode, DL.getIROrder(), DL.getDebugLoc(), VTList, Ops, NumOps);
     }
   }
   AllNodes.push_back(N);

   }
 
   // Allocate a new MachineSDNode.
-  N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs);
+  N = new (NodeAllocator) MachineSDNode(this, ~Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs);
 
   // Initialize the operands list.
   if (NumOps > array_lengthof(N->LocalOperands))

   DropOperands();
 }
 
-GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
+GlobalAddressSDNode::GlobalAddressSDNode(SDContext *ownerDAG, unsigned Opc, unsigned Order,
                                          DebugLoc DL, const GlobalValue *GA,
                                          EVT VT, int64_t o, unsigned char TF)
-  : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
+  : SDNode(ownerDAG, Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
   TheGlobal = GA;
 }
 
-MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
+MemSDNode::MemSDNode(SDContext *ownerDAG, unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
                      EVT memvt, MachineMemOperand *mmo)
- : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
+ : SDNode(ownerDAG, Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
   SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
                                       MMO->isNonTemporal(), MMO->isInvariant());
   assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");

   assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
 }
 
-MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
+MemSDNode::MemSDNode(SDContext *ownerDAG, unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
                      const SDValue *Ops, unsigned NumOps, EVT memvt,
                      MachineMemOperand *mmo)
-   : SDNode(Opc, Order, dl, VTs, Ops, NumOps),
+   : SDNode(ownerDAG, Opc, Order, dl, VTs, Ops, NumOps),
      MemoryVT(memvt), MMO(mmo) {
   SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
                                       MMO->isNonTemporal(), MMO->isInvariant());

lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp

 }
 
 void SelectionDAGISel::ComputeLiveOutVRegInfo() {
-  SmallPtrSet<SDNode*, 128> VisitedNodes;
+  /// Each DAG node has a UID, use a flag vector to indicate whether it is visited
+  FlagVector<bool, 256> VisitedNodes;
   SmallVector<SDNode*, 128> Worklist;
 
   Worklist.push_back(CurDAG->getRoot().getNode());

     SDNode *N = Worklist.pop_back_val();
 
     // If we've already seen this node, ignore it.
-    if (!VisitedNodes.insert(N))
+    if (VisitedNodes[N->SeqPos]) {
       continue;
-
+    } else {
+      VisitedNodes[N->SeqPos] = true;
+    }
     // Otherwise, add all chain operands to the worklist.
     for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
       if (N->getOperand(i).getValueType() == MVT::Other)

     // 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 changes of the root.
-    HandleSDNode Dummy(CurDAG->getRoot());
+    HandleSDNode Dummy(CurDAG, CurDAG->getRoot());
     SelectionDAG::allnodes_iterator ISelPosition (CurDAG->getRoot().getNode());
     ++ISelPosition;
 

lib/Target/X86/X86ISelDAGToDAG.cpp

 
     // Add an artificial use to this node so that we can keep track of
     // it if it gets CSE'd with a different node.
-    HandleSDNode Handle(N);
+    HandleSDNode Handle(CurDAG, N);
 
     // Test if the LHS of the sub can be folded.
     X86ISelAddressMode Backup = AM;

   case ISD::ADD: {
     // Add an artificial use to this node so that we can keep track of
     // it if it gets CSE'd with a different node.
-    HandleSDNode Handle(N);
+    HandleSDNode Handle(CurDAG, N);
 
     X86ISelAddressMode Backup = AM;
     if (!MatchAddressRecursively(N.getOperand(0), AM, Depth+1) &&