Backing out 48222 temporarily.

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

1 files changed, 57 insertions, 222 deletions

diff --git a/include/llvm/CodeGen/SelectionDAGNodes.h b/include/llvm/CodeGen/SelectionDAGNodes.h
index 2ebabe51d9..3b718b605a 100644
--- a/include/llvm/CodeGen/SelectionDAGNodes.h
+++ b/include/llvm/CodeGen/SelectionDAGNodes.h
@@ -779,7 +779,7 @@ namespace ISD {
 
 
 //===----------------------------------------------------------------------===//
-/// SDOperandImpl - Unlike LLVM values, Selection DAG nodes may return multiple
+/// SDOperand - Unlike LLVM values, Selection DAG nodes may return multiple
 /// values as the result of a computation.  Many nodes return multiple values,
 /// from loads (which define a token and a return value) to ADDC (which returns
 /// a result and a carry value), to calls (which may return an arbitrary number
@@ -787,28 +787,28 @@ namespace ISD {
 ///
 /// As such, each use of a SelectionDAG computation must indicate the node that
 /// computes it as well as which return value to use from that node.  This pair
-/// of information is represented with the SDOperandImpl value type.
+/// of information is represented with the SDOperand value type.
 ///
-class SDOperandImpl {
+class SDOperand {
 public:
   SDNode *Val;        // The node defining the value we are using.
   unsigned ResNo;     // Which return value of the node we are using.
 
-  SDOperandImpl() : Val(0), ResNo(0) {}
-  SDOperandImpl(SDNode *val, unsigned resno) : Val(val), ResNo(resno) {}
+  SDOperand() : Val(0), ResNo(0) {}
+  SDOperand(SDNode *val, unsigned resno) : Val(val), ResNo(resno) {}
 
-  bool operator==(const SDOperandImpl &O) const {
+  bool operator==(const SDOperand &O) const {
     return Val == O.Val && ResNo == O.ResNo;
   }
-  bool operator!=(const SDOperandImpl &O) const {
+  bool operator!=(const SDOperand &O) const {
     return !operator==(O);
   }
-  bool operator<(const SDOperandImpl &O) const {
+  bool operator<(const SDOperand &O) const {
     return Val < O.Val || (Val == O.Val && ResNo < O.ResNo);
   }
 
-  SDOperandImpl getValue(unsigned R) const {
-    return SDOperandImpl(Val, R);
+  SDOperand getValue(unsigned R) const {
+    return SDOperand(Val, R);
   }
 
   // isOperandOf - Return true if this node is an operand of N.
@@ -827,7 +827,7 @@ public:
   // Forwarding methods - These forward to the corresponding methods in SDNode.
   inline unsigned getOpcode() const;
   inline unsigned getNumOperands() const;
-  inline const SDOperandImpl &getOperand(unsigned i) const;
+  inline const SDOperand &getOperand(unsigned i) const;
   inline uint64_t getConstantOperandVal(unsigned i) const;
   inline bool isTargetOpcode() const;
   inline unsigned getTargetOpcode() const;
@@ -838,8 +838,7 @@ public:
   /// side-effecting instructions.  In practice, this looks through token
   /// factors and non-volatile loads.  In order to remain efficient, this only
   /// looks a couple of nodes in, it does not do an exhaustive search.
-  bool reachesChainWithoutSideEffects(SDOperandImpl Dest, 
-                                      unsigned Depth = 2) const;
+  bool reachesChainWithoutSideEffects(SDOperand Dest, unsigned Depth = 2) const;
   
   /// hasOneUse - Return true if there is exactly one operation using this
   /// result value of the defining operator.
@@ -851,18 +850,14 @@ public:
 };
 
 
-template<> struct DenseMapInfo<SDOperandImpl> {
-  static inline SDOperandImpl getEmptyKey() { 
-    return SDOperandImpl((SDNode*)-1, -1U); 
-  }
-  static inline SDOperandImpl getTombstoneKey() { 
-    return SDOperandImpl((SDNode*)-1, 0);
-  }
-  static unsigned getHashValue(const SDOperandImpl &Val) {
+template<> struct DenseMapInfo<SDOperand> {
+  static inline SDOperand getEmptyKey() { return SDOperand((SDNode*)-1, -1U); }
+  static inline SDOperand getTombstoneKey() { return SDOperand((SDNode*)-1, 0);}
+  static unsigned getHashValue(const SDOperand &Val) {
     return ((unsigned)((uintptr_t)Val.Val >> 4) ^
             (unsigned)((uintptr_t)Val.Val >> 9)) + Val.ResNo;
   }
-  static bool isEqual(const SDOperandImpl &LHS, const SDOperandImpl &RHS) {
+  static bool isEqual(const SDOperand &LHS, const SDOperand &RHS) {
     return LHS == RHS;
   }
   static bool isPod() { return true; }
@@ -870,88 +865,6 @@ template<> struct DenseMapInfo<SDOperandImpl> {
 
 /// simplify_type specializations - Allow casting operators to work directly on
 /// SDOperands as if they were SDNode*'s.
-template<> struct simplify_type<SDOperandImpl> {
-  typedef SDNode* SimpleType;
-  static SimpleType getSimplifiedValue(const SDOperandImpl &Val) {
-    return static_cast<SimpleType>(Val.Val);
-  }
-};
-template<> struct simplify_type<const SDOperandImpl> {
-  typedef SDNode* SimpleType;
-  static SimpleType getSimplifiedValue(const SDOperandImpl &Val) {
-    return static_cast<SimpleType>(Val.Val);
-  }
-};
-
-/// SDOperand - Represents a use of the SDNode referred by
-/// the SDOperandImpl.
-class SDOperand: public SDOperandImpl {
-  /// parent - Parent node of this operand.
-  SDNode    *parent;
-  /// Prev, next - Pointers to the uses list of the SDNode referred by 
-  /// this operand.
-  SDOperand **Prev, *Next;
-public:
-  friend class SDNode;
-  SDOperand(): SDOperandImpl(), parent(NULL), Prev(NULL), Next(NULL) {}
-
-  SDOperand(SDNode *val, unsigned resno) : 
-    SDOperandImpl(val,resno), parent(NULL), Prev(NULL), Next(NULL) {}
-
-  SDOperand(const SDOperandImpl& Op): SDOperandImpl(Op),parent(NULL),
-      Prev(NULL), Next(NULL)  {
-  }
-
-  SDOperand& operator= (SDOperandImpl& Op) {
-      *(SDOperandImpl*)this = Op;
-      Next = NULL;
-      Prev = NULL;
-      return *this;
-  }
-
-  SDOperand& operator= (const SDOperandImpl& Op) {
-      *(SDOperandImpl*)this = Op;
-      Next = NULL;
-      Prev = NULL;
-      return *this;
-  }
-
-  SDOperand& operator= (SDOperand& Op) {
-      *(SDOperandImpl*)this = Op;
-      Next = NULL;
-      Prev = NULL;
-      return *this;
-  }
-
-  SDOperand& operator= (const SDOperand& Op) {
-      *(SDOperandImpl*)this = Op;
-      Next = NULL;
-      Prev = NULL;
-      return *this;
-  }
-
-  SDOperand * getNext() { return Next; }
-
-  SDNode *getUser() { return parent; }
-  void setUser(SDNode *p) { parent = p; }
-
-protected:
-  void addToList(SDOperand **List) {
-    Next = *List;
-    if (Next) Next->Prev = &Next;
-    Prev = List;
-    *List = this;
-  }
-
-  void removeFromList() {
-    *Prev = Next;
-    if (Next) Next->Prev = Prev;
-  }
-};
-
-
-/// simplify_type specializations - Allow casting operators to work directly on
-/// SDOperands as if they were SDNode*'s.
 template<> struct simplify_type<SDOperand> {
   typedef SDNode* SimpleType;
   static SimpleType getSimplifiedValue(const SDOperand &Val) {
@@ -969,7 +882,6 @@ template<> struct simplify_type<const SDOperand> {
 /// SDNode - Represents one node in the SelectionDAG.
 ///
 class SDNode : public FoldingSetNode {
-private:
   /// NodeType - The operation that this node performs.
   ///
   unsigned short NodeType;
@@ -997,15 +909,10 @@ private:
   SDNode *Prev, *Next;
   friend struct ilist_traits<SDNode>;
 
-  /// UsesSize - The size of the uses list.
-  unsigned UsesSize;
-
-  /// Uses - List of uses for this SDNode.
-  SDOperand *Uses;
-
-  /// addUse - add SDOperand to the list of uses.
-  void addUse(SDOperand &U) { U.addToList(&Uses); }
-
+  /// Uses - These are all of the SDNode's that use a value produced by this
+  /// node.
+  SmallVector<SDNode*,3> Uses;
+  
   // Out-of-line virtual method to give class a home.
   virtual void ANCHOR();
 public:
@@ -1024,9 +931,9 @@ public:
     return NodeType - ISD::BUILTIN_OP_END;
   }
 
-  size_t use_size() const { return UsesSize; }
-  bool use_empty() const { return Uses == NULL; }
-  bool hasOneUse() const { return use_size() == 1; }
+  size_t use_size() const { return Uses.size(); }
+  bool use_empty() const { return Uses.empty(); }
+  bool hasOneUse() const { return Uses.size() == 1; }
 
   /// getNodeId - Return the unique node id.
   ///
@@ -1035,75 +942,9 @@ public:
   /// setNodeId - Set unique node id.
   void setNodeId(int Id) { NodeId = Id; }
 
-  /// use_iterator - This class provides iterator support for SDOperand
-  /// operands that use a specific SDNode. 
-  class use_iterator
-    : public forward_iterator<SDOperand, ptrdiff_t> {
-    SDOperand *Op;
-    explicit use_iterator(SDOperand *op) : Op(op) {
-    }
-    friend class SDNode;
-  public:
-    typedef forward_iterator<SDOperand, ptrdiff_t>::reference reference;
-    typedef forward_iterator<SDOperand, ptrdiff_t>::pointer pointer;
-
-    use_iterator(const use_iterator &I) : Op(I.Op) {}
-    use_iterator() : Op(0) {}
-
-    bool operator==(const use_iterator &x) const {
-      return Op == x.Op;
-    }
-    bool operator!=(const use_iterator &x) const {
-      return !operator==(x);
-    }
- 
-    /// atEnd - return true if this iterator is at the end of uses list.
-    bool atEnd() const { return Op == 0; }
-
-    // Iterator traversal: forward iteration only.
-    use_iterator &operator++() {          // Preincrement
-      assert(Op && "Cannot increment end iterator!");
-      Op = Op->getNext();
-      return *this;
-    }
-
-    use_iterator operator++(int) {        // Postincrement
-      use_iterator tmp = *this; ++*this; return tmp;
-    }
-
-
-    /// getOperandNum - Retrive a number of a current operand.
-    unsigned getOperandNum() const {
-      assert(Op && "Cannot dereference end iterator!");
-      return (Op - Op->getUser()->OperandList);
-    }
-
-    /// Retrieve a reference to the current operand.
-    SDOperand &operator*() const {
-      assert(Op && "Cannot dereference end iterator!");
-      return *Op;
-    }
-
-    /// Retrieve a pointer to the current operand.
-    SDOperand *operator->() const {
-      assert(Op && "Cannot dereference end iterator!");
-      return Op;
-    }
-  };
-
-  /// use_begin/use_end - Provide iteration support to walk over all uses
-  /// of an SDNode.
-
-  use_iterator use_begin(SDNode *node) const {
-    return use_iterator(node->Uses);
-  }
-
-  use_iterator use_begin() const {
-    return use_iterator(Uses);
-  }
-
-  static use_iterator use_end() { return use_iterator(0); }
-
+  typedef SmallVector<SDNode*,3>::const_iterator use_iterator;
+  use_iterator use_begin() const { return Uses.begin(); }
+  use_iterator use_end() const { return Uses.end(); }
 
   /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
   /// indicated value.  This method ignores uses of other values defined by this
@@ -1141,7 +982,7 @@ public:
     return OperandList[Num];
   }
 
-  typedef SDOperand* op_iterator;
+  typedef const SDOperand* op_iterator;
   op_iterator op_begin() const { return OperandList; }
   op_iterator op_end() const { return OperandList+NumOperands; }
 
@@ -1198,28 +1039,25 @@ protected:
   }
 
   SDNode(unsigned Opc, SDVTList VTs, const SDOperand *Ops, unsigned NumOps)
-    : NodeType(Opc), NodeId(-1), UsesSize(0), Uses(NULL) {
+    : NodeType(Opc), NodeId(-1) {
     OperandsNeedDelete = true;
     NumOperands = NumOps;
     OperandList = NumOps ? new SDOperand[NumOperands] : 0;
     
     for (unsigned i = 0; i != NumOps; ++i) {
       OperandList[i] = Ops[i];
-      OperandList[i].setUser(this);
-      Ops[i].Val->addUse(OperandList[i]);
-      ++Ops[i].Val->UsesSize;
+      Ops[i].Val->Uses.push_back(this);
     }
     
     ValueList = VTs.VTs;
     NumValues = VTs.NumVTs;
     Prev = 0; Next = 0;
   }
-
-  SDNode(unsigned Opc, SDVTList VTs)
-    : NodeType(Opc), NodeId(-1), UsesSize(0), Uses(NULL) {
+  SDNode(unsigned Opc, SDVTList VTs) : NodeType(Opc), NodeId(-1) {
     OperandsNeedDelete = false;  // Operands set with InitOperands.
     NumOperands = 0;
     OperandList = 0;
+    
     ValueList = VTs.VTs;
     NumValues = VTs.NumVTs;
     Prev = 0; Next = 0;
@@ -1232,14 +1070,9 @@ protected:
     assert(OperandList == 0 && "Operands already set!");
     NumOperands = NumOps;
     OperandList = Ops;
-    UsesSize = 0;
-    Uses = NULL;
     
-    for (unsigned i = 0; i != NumOps; ++i) {
-      OperandList[i].setUser(this);
-      Ops[i].Val->addUse(OperandList[i]);
-      ++Ops[i].Val->UsesSize;
-    }
+    for (unsigned i = 0; i != NumOps; ++i)
+      Ops[i].Val->Uses.push_back(this);
   }
   
   /// MorphNodeTo - This frees the operands of the current node, resets the
@@ -1248,48 +1081,50 @@ protected:
   void MorphNodeTo(unsigned Opc, SDVTList L,
                    const SDOperand *Ops, unsigned NumOps);
   
-  void addUser(unsigned i, SDNode *User) {
-    assert(User->OperandList[i].getUser() && "Node without parent");
-    addUse(User->OperandList[i]);
-    ++UsesSize;
-  }
-
-  void removeUser(unsigned i, SDNode *User) {
-    assert(User->OperandList[i].getUser() && "Node without parent");
-    SDOperand &Op = User->OperandList[i];
-    Op.removeFromList();
-    --UsesSize;
+  void addUser(SDNode *User) {
+    Uses.push_back(User);
+  }
+  void removeUser(SDNode *User) {
+    // Remove this user from the operand's use list.
+    for (unsigned i = Uses.size(); ; --i) {
+      assert(i != 0 && "Didn't find user!");
+      if (Uses[i-1] == User) {
+        Uses[i-1] = Uses.back();
+        Uses.pop_back();
+        return;
+      }
+    }
   }
 };
 
 
-// Define inline functions from the SDOperandImpl class.
+// Define inline functions from the SDOperand class.
 
-inline unsigned SDOperandImpl::getOpcode() const {
+inline unsigned SDOperand::getOpcode() const {
   return Val->getOpcode();
 }
-inline MVT::ValueType SDOperandImpl::getValueType() const {
+inline MVT::ValueType SDOperand::getValueType() const {
   return Val->getValueType(ResNo);
 }
-inline unsigned SDOperandImpl::getNumOperands() const {
+inline unsigned SDOperand::getNumOperands() const {
   return Val->getNumOperands();
 }
-inline const SDOperandImpl &SDOperandImpl::getOperand(unsigned i) const {
+inline const SDOperand &SDOperand::getOperand(unsigned i) const {
   return Val->getOperand(i);
 }
-inline uint64_t SDOperandImpl::getConstantOperandVal(unsigned i) const {
+inline uint64_t SDOperand::getConstantOperandVal(unsigned i) const {
   return Val->getConstantOperandVal(i);
 }
-inline bool SDOperandImpl::isTargetOpcode() const {
+inline bool SDOperand::isTargetOpcode() const {
   return Val->isTargetOpcode();
 }
-inline unsigned SDOperandImpl::getTargetOpcode() const {
+inline unsigned SDOperand::getTargetOpcode() const {
   return Val->getTargetOpcode();
 }
-inline bool SDOperandImpl::hasOneUse() const {
+inline bool SDOperand::hasOneUse() const {
   return Val->hasNUsesOfValue(1, ResNo);
 }
-inline bool SDOperandImpl::use_empty() const {
+inline bool SDOperand::use_empty() const {
   return !Val->hasAnyUseOfValue(ResNo);
 }