Eliminate some malloc traffic by allocating vectors on the stack. Change some
[oota-llvm.git] / include / llvm / CodeGen / SelectionDAGNodes.h
index 0b850e617b16830155d665b29bed5cbcd08fcbca..fe6975b19f23bc521f960425a0597a57f9bbf1be 100644 (file)
@@ -47,6 +47,10 @@ namespace ISD {
   /// SelectionDAG.
   ///
   enum NodeType {
+    // DELETED_NODE - This is an illegal flag value that is used to catch
+    // errors.  This opcode is not a legal opcode for any node.
+    DELETED_NODE,
+    
     // EntryToken - This is the marker used to indicate the start of the region.
     EntryToken,
 
@@ -63,28 +67,46 @@ namespace ISD {
     AssertSext, AssertZext,
 
     // Various leaf nodes.
-    Constant, ConstantFP, STRING,
-    GlobalAddress, FrameIndex, ConstantPool,
-    BasicBlock, ExternalSymbol, VALUETYPE, CONDCODE, Register,
-    
-    // ConstantVec works like Constant or ConstantFP, except that it is not a
-    // leaf node.  All operands are either Constant or ConstantFP nodes.
-    ConstantVec,
-    
+    STRING, BasicBlock, VALUETYPE, CONDCODE, Register,
+    Constant, ConstantFP,
+    GlobalAddress, FrameIndex, JumpTable, ConstantPool, ExternalSymbol,
+
     // TargetConstant* - Like Constant*, but the DAG does not do any folding or
     // simplification of the constant.
     TargetConstant,
     TargetConstantFP,
-    TargetConstantVec, 
     
     // TargetGlobalAddress - Like GlobalAddress, but the DAG does no folding or
     // anything else with this node, and this is valid in the target-specific
     // dag, turning into a GlobalAddress operand.
     TargetGlobalAddress,
     TargetFrameIndex,
+    TargetJumpTable,
     TargetConstantPool,
     TargetExternalSymbol,
-
+    
+    /// RESULT = INTRINSIC_WO_CHAIN(INTRINSICID, arg1, arg2, ...)
+    /// This node represents a target intrinsic function with no side effects.
+    /// The first operand is the ID number of the intrinsic from the
+    /// llvm::Intrinsic namespace.  The operands to the intrinsic follow.  The
+    /// node has returns the result of the intrinsic.
+    INTRINSIC_WO_CHAIN,
+    
+    /// RESULT,OUTCHAIN = INTRINSIC_W_CHAIN(INCHAIN, INTRINSICID, arg1, ...)
+    /// This node represents a target intrinsic function with side effects that
+    /// returns a result.  The first operand is a chain pointer.  The second is
+    /// the ID number of the intrinsic from the llvm::Intrinsic namespace.  The
+    /// operands to the intrinsic follow.  The node has two results, the result
+    /// of the intrinsic and an output chain.
+    INTRINSIC_W_CHAIN,
+
+    /// OUTCHAIN = INTRINSIC_VOID(INCHAIN, INTRINSICID, arg1, arg2, ...)
+    /// This node represents a target intrinsic function with side effects that
+    /// does not return a result.  The first operand is a chain pointer.  The
+    /// second is the ID number of the intrinsic from the llvm::Intrinsic
+    /// namespace.  The operands to the intrinsic follow.
+    INTRINSIC_VOID,
+    
     // CopyToReg - This node has three operands: a chain, a register number to
     // set to this value, and a value.  
     CopyToReg,
@@ -96,6 +118,22 @@ namespace ISD {
 
     // UNDEF - An undefined node
     UNDEF,
+    
+    /// FORMAL_ARGUMENTS(CHAIN, CC#, ISVARARG) - This node represents the formal
+    /// arguments for a function.  CC# is a Constant value indicating the
+    /// calling convention of the function, and ISVARARG is a flag that
+    /// indicates whether the function is varargs or not.  This node has one
+    /// result value for each incoming argument, plus one for the output chain.
+    /// It must be custom legalized.
+    /// 
+    FORMAL_ARGUMENTS,
+    
+    /// RV1, RV2...RVn, CHAIN = CALL(CHAIN, CC#, ISVARARG, ISTAILCALL, CALLEE,
+    ///                              ARG0, SIGN0, ARG1, SIGN1, ... ARGn, SIGNn)
+    /// This node represents a fully general function call, before the legalizer
+    /// runs.  This has one result value for each argument / signness pair, plus
+    /// a chain result. It must be custom legalized.
+    CALL,
 
     // EXTRACT_ELEMENT - This is used to get the first or second (determined by
     // a Constant, which is required to be operand #1), element of the aggregate
@@ -118,17 +156,111 @@ namespace ISD {
     // Simple integer binary arithmetic operators.
     ADD, SUB, MUL, SDIV, UDIV, SREM, UREM,
     
+    // Carry-setting nodes for multiple precision addition and subtraction.
+    // These nodes take two operands of the same value type, and produce two
+    // results.  The first result is the normal add or sub result, the second
+    // result is the carry flag result.
+    ADDC, SUBC,
+    
+    // Carry-using nodes for multiple precision addition and subtraction.  These
+    // nodes take three operands: The first two are the normal lhs and rhs to
+    // the add or sub, and the third is the input carry flag.  These nodes
+    // produce two results; the normal result of the add or sub, and the output
+    // carry flag.  These nodes both read and write a carry flag to allow them
+    // to them to be chained together for add and sub of arbitrarily large
+    // values.
+    ADDE, SUBE,
+    
     // Simple binary floating point operators.
     FADD, FSUB, FMUL, FDIV, FREM,
-    
-    // Simple abstract vector operators.  Unlike the integer and floating point
-    // binary operators, these nodes also take two additional operands:
-    // a constant element count, and a value type node indicating the type of
-    // the elements.  The order is op0, op1, count, type.  All vector opcodes,
-    // including VLOAD, must currently have count and type as their 3rd and 4th
-    // arguments.
-    VADD, VSUB, VMUL,
 
+    // FCOPYSIGN(X, Y) - Return the value of X with the sign of Y.  NOTE: This
+    // DAG node does not require that X and Y have the same type, just that they
+    // are both floating point.  X and the result must have the same type.
+    // FCOPYSIGN(f32, f64) is allowed.
+    FCOPYSIGN,
+
+    /// VBUILD_VECTOR(ELT1, ELT2, ELT3, ELT4,...,  COUNT,TYPE) - Return a vector
+    /// with the specified, possibly variable, elements.  The number of elements
+    /// is required to be a power of two.
+    VBUILD_VECTOR,
+
+    /// BUILD_VECTOR(ELT1, ELT2, ELT3, ELT4,...) - Return a vector
+    /// with the specified, possibly variable, elements.  The number of elements
+    /// is required to be a power of two.
+    BUILD_VECTOR,
+    
+    /// VINSERT_VECTOR_ELT(VECTOR, VAL, IDX,  COUNT,TYPE) - Given a vector
+    /// VECTOR, an element ELEMENT, and a (potentially variable) index IDX,
+    /// return an vector with the specified element of VECTOR replaced with VAL.
+    /// COUNT and TYPE specify the type of vector, as is standard for V* nodes.
+    VINSERT_VECTOR_ELT,
+    
+    /// INSERT_VECTOR_ELT(VECTOR, VAL, IDX) - Returns VECTOR (a legal packed
+    /// type) with the element at IDX replaced with VAL.
+    INSERT_VECTOR_ELT,
+
+    /// VEXTRACT_VECTOR_ELT(VECTOR, IDX) - Returns a single element from VECTOR
+    /// (an MVT::Vector value) identified by the (potentially variable) element
+    /// number IDX.
+    VEXTRACT_VECTOR_ELT,
+    
+    /// EXTRACT_VECTOR_ELT(VECTOR, IDX) - Returns a single element from VECTOR
+    /// (a legal packed type vector) identified by the (potentially variable)
+    /// element number IDX.
+    EXTRACT_VECTOR_ELT,
+    
+    /// VVECTOR_SHUFFLE(VEC1, VEC2, SHUFFLEVEC, COUNT,TYPE) - Returns a vector,
+    /// of the same type as VEC1/VEC2.  SHUFFLEVEC is a VBUILD_VECTOR of
+    /// constant int values that indicate which value each result element will
+    /// get.  The elements of VEC1/VEC2 are enumerated in order.  This is quite
+    /// similar to the Altivec 'vperm' instruction, except that the indices must
+    /// be constants and are in terms of the element size of VEC1/VEC2, not in
+    /// terms of bytes.
+    VVECTOR_SHUFFLE,
+
+    /// VECTOR_SHUFFLE(VEC1, VEC2, SHUFFLEVEC) - Returns a vector, of the same
+    /// type as VEC1/VEC2.  SHUFFLEVEC is a BUILD_VECTOR of constant int values
+    /// (regardless of whether its datatype is legal or not) that indicate
+    /// which value each result element will get.  The elements of VEC1/VEC2 are
+    /// enumerated in order.  This is quite similar to the Altivec 'vperm'
+    /// instruction, except that the indices must be constants and are in terms
+    /// of the element size of VEC1/VEC2, not in terms of bytes.
+    VECTOR_SHUFFLE,
+    
+    /// X = VBIT_CONVERT(Y)  and X = VBIT_CONVERT(Y, COUNT,TYPE) - This node
+    /// represents a conversion from or to an ISD::Vector type.
+    ///
+    /// This is lowered to a BIT_CONVERT of the appropriate input/output types.
+    /// The input and output are required to have the same size and at least one
+    /// is required to be a vector (if neither is a vector, just use
+    /// BIT_CONVERT).
+    ///
+    /// If the result is a vector, this takes three operands (like any other
+    /// vector producer) which indicate the size and type of the vector result.
+    /// Otherwise it takes one input.
+    VBIT_CONVERT,
+    
+    /// BINOP(LHS, RHS,  COUNT,TYPE)
+    /// Simple abstract vector operators.  Unlike the integer and floating point
+    /// binary operators, these nodes also take two additional operands:
+    /// a constant element count, and a value type node indicating the type of
+    /// the elements.  The order is count, type, op0, op1.  All vector opcodes,
+    /// including VLOAD and VConstant must currently have count and type as
+    /// their last two operands.
+    VADD, VSUB, VMUL, VSDIV, VUDIV,
+    VAND, VOR, VXOR,
+    
+    /// VSELECT(COND,LHS,RHS,  COUNT,TYPE) - Select for MVT::Vector values.
+    /// COND is a boolean value.  This node return LHS if COND is true, RHS if
+    /// COND is false.
+    VSELECT,
+    
+    /// SCALAR_TO_VECTOR(VAL) - This represents the operation of loading a
+    /// scalar value into the low element of the resultant vector type.  The top
+    /// elements of the vector are undefined.
+    SCALAR_TO_VECTOR,
+    
     // MULHU/MULHS - Multiply high - Multiply two integers of type iN, producing
     // an unsigned/signed value of type i[2*n], then return the top part.
     MULHU, MULHS,
@@ -141,7 +273,7 @@ namespace ISD {
     // Counting operators
     CTTZ, CTLZ, CTPOP,
 
-    // Select
+    // Select(COND, TRUEVAL, FALSEVAL)
     SELECT, 
     
     // Select with condition operator - This selects between a true value and 
@@ -156,13 +288,6 @@ namespace ISD {
     // (op #2) as a CondCodeSDNode.
     SETCC,
 
-    // ADD_PARTS/SUB_PARTS - These operators take two logical operands which are
-    // broken into a multiple pieces each, and return the resulting pieces of
-    // doing an atomic add/sub operation.  This is used to handle add/sub of
-    // expanded types.  The operation ordering is:
-    //       [Lo,Hi] = op [LoLHS,HiLHS], [LoRHS,HiRHS]
-    ADD_PARTS, SUB_PARTS,
-
     // SHL_PARTS/SRA_PARTS/SRL_PARTS - These operators are used for expanded
     // integer shift operations, just like ADD/SUB_PARTS.  The operation
     // ordering is:
@@ -229,15 +354,15 @@ namespace ISD {
     // FNEG, FABS, FSQRT, FSIN, FCOS - Perform unary floating point negation,
     // absolute value, square root, sine and cosine operations.
     FNEG, FABS, FSQRT, FSIN, FCOS,
-
+    
     // Other operators.  LOAD and STORE have token chains as their first
     // operand, then the same operands as an LLVM load/store instruction, then a
     // SRCVALUE node that provides alias analysis information.
     LOAD, STORE,
     
-    // Abstract vector version of LOAD.  VLOAD has a token chain as the first
-    // operand, followed by a pointer operand, a constant element count, a value
-    // type node indicating the type of the elements, and a SRCVALUE node.
+    // Abstract vector version of LOAD.  VLOAD has a constant element count as
+    // the first operand, followed by a value type node indicating the type of
+    // the elements, a token chain, a pointer operand, and a SRCVALUE node.
     VLOAD,
 
     // EXTLOAD, SEXTLOAD, ZEXTLOAD - These three operators all load a value from
@@ -250,10 +375,9 @@ namespace ISD {
     //          integer result type.
     // ZEXTLOAD loads the integer operand and zero extends it to a larger
     //          integer result type.
-    // EXTLOAD  is used for two things: floating point extending loads, and
-    //          integer extending loads where it doesn't matter what the high
-    //          bits are set to.  The code generator is allowed to codegen this
-    //          into whichever operation is more efficient.
+    // EXTLOAD  is used for three things: floating point extending loads, 
+    //          integer extending loads [the top bits are undefined], and vector
+    //          extending loads [load into low elt].
     EXTLOAD, SEXTLOAD, ZEXTLOAD,
 
     // TRUNCSTORE - This operators truncates (for integer) or rounds (for FP) a
@@ -277,33 +401,26 @@ namespace ISD {
     // operand, the second is the MBB to branch to.
     BR,
 
+    // BRIND - Indirect branch.  The first operand is the chain, the second
+    // is the value to branch to, which must be of the same type as the target's
+    // pointer type.
+    BRIND,
+    
     // BRCOND - Conditional branch.  The first operand is the chain,
     // the second is the condition, the third is the block to branch
     // to if the condition is true.
     BRCOND,
 
-    // BRCONDTWOWAY - Two-way conditional branch.  The first operand is the
-    // chain, the second is the condition, the third is the block to branch to
-    // if true, and the forth is the block to branch to if false.  Targets
-    // usually do not implement this, preferring to have legalize demote the
-    // operation to BRCOND/BR pairs when necessary.
-    BRCONDTWOWAY,
-
     // BR_CC - Conditional branch.  The behavior is like that of SELECT_CC, in
     // that the condition is represented as condition code, and two nodes to
     // compare, rather than as a combined SetCC node.  The operands in order are
     // chain, cc, lhs, rhs, block to branch to if condition is true.
     BR_CC,
     
-    // BRTWOWAY_CC - Two-way conditional branch.  The operands in order are
-    // chain, cc, lhs, rhs, block to branch to if condition is true, block to
-    // branch to if condition is false.  Targets usually do not implement this,
-    // preferring to have legalize demote the operation to BRCOND/BR pairs.
-    BRTWOWAY_CC,
-    
     // RET - Return from function.  The first operand is the chain,
-    // and any subsequent operands are the return values for the
-    // function.  This operation can have variable number of operands.
+    // and any subsequent operands are pairs of return value and return value
+    // signness for the function.  This operation can have variable number of
+    // operands.
     RET,
 
     // INLINEASM - Represents an inline asm block.  This node always has two
@@ -366,12 +483,6 @@ namespace ISD {
     // register (or other high accuracy low latency clock source)
     READCYCLECOUNTER,
 
-    // READPORT, WRITEPORT, READIO, WRITEIO - These correspond to the LLVM
-    // intrinsics of the same name.  The first operand is a token chain, the
-    // other operands match the intrinsic.  These produce a token chain in
-    // addition to a value (if any).
-    READPORT, WRITEPORT, READIO, WRITEIO,
-    
     // HANDLENODE node - Used as a handle for various purposes.
     HANDLENODE,
 
@@ -394,9 +505,19 @@ namespace ISD {
     DEBUG_LABEL,
     
     // BUILTIN_OP_END - This must be the last enum value in this list.
-    BUILTIN_OP_END,
+    BUILTIN_OP_END
   };
 
+  /// Node predicates
+
+  /// isBuildVectorAllOnes - Return true if the specified node is a
+  /// BUILD_VECTOR where all of the elements are ~0 or undef.
+  bool isBuildVectorAllOnes(const SDNode *N);
+
+  /// isBuildVectorAllZeros - Return true if the specified node is a
+  /// BUILD_VECTOR where all of the elements are 0 or undef.
+  bool isBuildVectorAllZeros(const SDNode *N);
+  
   //===--------------------------------------------------------------------===//
   /// ISD::CondCode enum - These are ordered carefully to make the bitfields
   /// below work out, when considering SETFALSE (something that never exists
@@ -439,7 +560,7 @@ namespace ISD {
     SETNE,         //  1 X 1 1 0       True if not equal
     SETTRUE2,      //  1 X 1 1 1       Always true (always folded)
 
-    SETCC_INVALID,      // Marker value.
+    SETCC_INVALID       // Marker value.
   };
 
   /// isSignedIntSetCC - Return true if this is a setcc instruction that
@@ -507,7 +628,7 @@ public:
   SDNode *Val;        // The node defining the value we are using.
   unsigned ResNo;     // Which return value of the node we are using.
 
-  SDOperand() : Val(0) {}
+  SDOperand() : Val(0), ResNo(0) {}
   SDOperand(SDNode *val, unsigned resno) : Val(val), ResNo(resno) {}
 
   bool operator==(const SDOperand &O) const {
@@ -524,13 +645,15 @@ public:
     return SDOperand(Val, R);
   }
 
+  // isOperand - Return true if this node is an operand of N.
+  bool isOperand(SDNode *N) const;
+
   /// getValueType - Return the ValueType of the referenced return value.
   ///
   inline MVT::ValueType getValueType() const;
 
   // Forwarding methods - These forward to the corresponding methods in SDNode.
   inline unsigned getOpcode() const;
-  inline unsigned getNodeDepth() const;
   inline unsigned getNumOperands() const;
   inline const SDOperand &getOperand(unsigned i) const;
   inline bool isTargetOpcode() const;
@@ -565,10 +688,8 @@ class SDNode {
   ///
   unsigned short NodeType;
 
-  /// NodeDepth - Node depth is defined as MAX(Node depth of children)+1.  This
-  /// means that leaves have a depth of 1, things that use only leaves have a
-  /// depth of 2, etc.
-  unsigned short NodeDepth;
+  /// NodeId - Unique id per SDNode in the DAG.
+  int NodeId;
 
   /// OperandList - The values that are used by this operation.
   ///
@@ -586,12 +707,19 @@ 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.
   std::vector<SDNode*> Uses;
+  
+  // Out-of-line virtual method to give class a home.
+  virtual void ANCHOR();
 public:
   virtual ~SDNode() {
     assert(NumOperands == 0 && "Operand list not cleared before deletion");
+    NodeType = ISD::DELETED_NODE;
   }
   
   //===--------------------------------------------------------------------===//
@@ -608,9 +736,9 @@ public:
   bool use_empty() const { return Uses.empty(); }
   bool hasOneUse() const { return Uses.size() == 1; }
 
-  /// getNodeDepth - Return the distance from this node to the leaves in the
-  /// graph.  The leaves have a depth of 1.
-  unsigned getNodeDepth() const { return NodeDepth; }
+  /// getNodeId - Return the unique node id.
+  ///
+  int getNodeId() const { return NodeId; }
 
   typedef std::vector<SDNode*>::const_iterator use_iterator;
   use_iterator use_begin() const { return Uses.begin(); }
@@ -619,7 +747,13 @@ public:
   /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
   /// indicated value.  This method ignores uses of other values defined by this
   /// operation.
-  bool hasNUsesOfValue(unsigned NUses, unsigned Value);
+  bool hasNUsesOfValue(unsigned NUses, unsigned Value) const;
+
+  // isOnlyUse - Return true if this node is the only use of N.
+  bool isOnlyUse(SDNode *N) const;
+
+  // isOperand - Return true if this node is an operand of N.
+  bool isOperand(SDNode *N) const;
 
   /// getNumOperands - Return the number of values used by this operation.
   ///
@@ -658,6 +792,11 @@ 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; }
+  
 protected:
   friend class SelectionDAG;
   
@@ -665,14 +804,15 @@ protected:
   ///
   static MVT::ValueType *getValueTypeList(MVT::ValueType VT);
 
-  SDNode(unsigned NT, MVT::ValueType VT) : NodeType(NT), NodeDepth(1) {
+  SDNode(unsigned NT, MVT::ValueType VT) : NodeType(NT), NodeId(-1) {
     OperandList = 0; NumOperands = 0;
     ValueList = getValueTypeList(VT);
     NumValues = 1;
     Prev = 0; Next = 0;
+    NextInBucket = 0;
   }
   SDNode(unsigned NT, SDOperand Op)
-    : NodeType(NT), NodeDepth(Op.Val->getNodeDepth()+1) {
+    : NodeType(NT), NodeId(-1) {
     OperandList = new SDOperand[1];
     OperandList[0] = Op;
     NumOperands = 1;
@@ -680,13 +820,10 @@ protected:
     ValueList = 0;
     NumValues = 0;
     Prev = 0; Next = 0;
+    NextInBucket = 0;
   }
   SDNode(unsigned NT, SDOperand N1, SDOperand N2)
-    : NodeType(NT) {
-    if (N1.Val->getNodeDepth() > N2.Val->getNodeDepth())
-      NodeDepth = N1.Val->getNodeDepth()+1;
-    else
-      NodeDepth = N2.Val->getNodeDepth()+1;
+    : NodeType(NT), NodeId(-1) {
     OperandList = new SDOperand[2];
     OperandList[0] = N1;
     OperandList[1] = N2;
@@ -695,16 +832,10 @@ protected:
     ValueList = 0;
     NumValues = 0;
     Prev = 0; Next = 0;
+    NextInBucket = 0;
   }
   SDNode(unsigned NT, SDOperand N1, SDOperand N2, SDOperand N3)
-    : NodeType(NT) {
-    unsigned ND = N1.Val->getNodeDepth();
-    if (ND < N2.Val->getNodeDepth())
-      ND = N2.Val->getNodeDepth();
-    if (ND < N3.Val->getNodeDepth())
-      ND = N3.Val->getNodeDepth();
-    NodeDepth = ND+1;
-
+    : NodeType(NT), NodeId(-1) {
     OperandList = new SDOperand[3];
     OperandList[0] = N1;
     OperandList[1] = N2;
@@ -716,18 +847,10 @@ protected:
     ValueList = 0;
     NumValues = 0;
     Prev = 0; Next = 0;
+    NextInBucket = 0;
   }
   SDNode(unsigned NT, SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4)
-    : NodeType(NT) {
-    unsigned ND = N1.Val->getNodeDepth();
-    if (ND < N2.Val->getNodeDepth())
-      ND = N2.Val->getNodeDepth();
-    if (ND < N3.Val->getNodeDepth())
-      ND = N3.Val->getNodeDepth();
-    if (ND < N4.Val->getNodeDepth())
-      ND = N4.Val->getNodeDepth();
-    NodeDepth = ND+1;
-
+    : NodeType(NT), NodeId(-1) {
     OperandList = new SDOperand[4];
     OperandList[0] = N1;
     OperandList[1] = N2;
@@ -740,22 +863,22 @@ protected:
     ValueList = 0;
     NumValues = 0;
     Prev = 0; Next = 0;
+    NextInBucket = 0;
   }
-  SDNode(unsigned Opc, const std::vector<SDOperand> &Nodes) : NodeType(Opc) {
-    NumOperands = Nodes.size();
+  SDNode(unsigned Opc, const SDOperand *Ops, unsigned NumOps)
+    : NodeType(Opc), NodeId(-1) {
+    NumOperands = NumOps;
     OperandList = new SDOperand[NumOperands];
     
-    unsigned ND = 0;
-    for (unsigned i = 0, e = Nodes.size(); i != e; ++i) {
-      OperandList[i] = Nodes[i];
+    for (unsigned i = 0, e = NumOps; i != e; ++i) {
+      OperandList[i] = Ops[i];
       SDNode *N = OperandList[i].Val;
       N->Uses.push_back(this);
-      if (ND < N->getNodeDepth()) ND = N->getNodeDepth();
     }
-    NodeDepth = ND+1;
     ValueList = 0;
     NumValues = 0;
     Prev = 0; Next = 0;
+    NextInBucket = 0;
   }
 
   /// MorphNodeTo - This clears the return value and operands list, and sets the
@@ -775,11 +898,6 @@ protected:
     NumOperands = 0;
   }
   
-  void setValueTypes(MVT::ValueType VT) {
-    assert(NumValues == 0 && "Should not have values yet!");
-    ValueList = getValueTypeList(VT);
-    NumValues = 1;
-  }
   void setValueTypes(MVT::ValueType *List, unsigned NumVal) {
     assert(NumValues == 0 && "Should not have values yet!");
     ValueList = List;
@@ -901,6 +1019,10 @@ protected:
       }
     }
   }
+
+  void setNodeId(int Id) {
+    NodeId = Id;
+  }
 };
 
 
@@ -909,9 +1031,6 @@ protected:
 inline unsigned SDOperand::getOpcode() const {
   return Val->getOpcode();
 }
-inline unsigned SDOperand::getNodeDepth() const {
-  return Val->getNodeDepth();
-}
 inline MVT::ValueType SDOperand::getValueType() const {
   return Val->getValueType(ResNo);
 }
@@ -978,9 +1097,7 @@ public:
 
   bool isNullValue() const { return Value == 0; }
   bool isAllOnesValue() const {
-    int NumBits = MVT::getSizeInBits(getValueType(0));
-    if (NumBits == 64) return Value+1 == 0;
-    return Value == (1ULL << NumBits)-1;
+    return Value == MVT::getIntVTBitMask(getValueType(0));
   }
 
   static bool classof(const ConstantSDNode *) { return true; }
@@ -1017,19 +1134,19 @@ public:
 
 class GlobalAddressSDNode : public SDNode {
   GlobalValue *TheGlobal;
-  int offset;
+  int Offset;
 protected:
   friend class SelectionDAG;
   GlobalAddressSDNode(bool isTarget, const GlobalValue *GA, MVT::ValueType VT,
                       int o=0)
-    : SDNode(isTarget ? ISD::TargetGlobalAddress : ISD::GlobalAddress, VT) {
+    : SDNode(isTarget ? ISD::TargetGlobalAddress : ISD::GlobalAddress, VT),
+      Offset(o) {
     TheGlobal = const_cast<GlobalValue*>(GA);
-    offset = o;
   }
 public:
 
   GlobalValue *getGlobal() const { return TheGlobal; }
-  int getOffset() const { return offset; }
+  int getOffset() const { return Offset; }
 
   static bool classof(const GlobalAddressSDNode *) { return true; }
   static bool classof(const SDNode *N) {
@@ -1056,21 +1173,45 @@ public:
   }
 };
 
+class JumpTableSDNode : public SDNode {
+  int JTI;
+protected:
+  friend class SelectionDAG;
+  JumpTableSDNode(int jti, MVT::ValueType VT, bool isTarg)
+    : SDNode(isTarg ? ISD::TargetJumpTable : ISD::JumpTable, VT), 
+    JTI(jti) {}
+public:
+    
+    int getIndex() const { return JTI; }
+  
+  static bool classof(const JumpTableSDNode *) { return true; }
+  static bool classof(const SDNode *N) {
+    return N->getOpcode() == ISD::JumpTable ||
+           N->getOpcode() == ISD::TargetJumpTable;
+  }
+};
+
 class ConstantPoolSDNode : public SDNode {
   Constant *C;
+  int Offset;
   unsigned Alignment;
 protected:
   friend class SelectionDAG;
-  ConstantPoolSDNode(Constant *c, MVT::ValueType VT, bool isTarget)
+  ConstantPoolSDNode(bool isTarget, Constant *c, MVT::ValueType VT,
+                     int o=0)
     : SDNode(isTarget ? ISD::TargetConstantPool : ISD::ConstantPool, VT),
-    C(c), Alignment(0) {}
-  ConstantPoolSDNode(Constant *c, MVT::ValueType VT, unsigned Align,
-                     bool isTarget)
+      C(c), Offset(o), Alignment(0) {}
+  ConstantPoolSDNode(bool isTarget, Constant *c, MVT::ValueType VT, int o,
+                     unsigned Align)
     : SDNode(isTarget ? ISD::TargetConstantPool : ISD::ConstantPool, VT),
-    C(c), Alignment(Align) {}
+      C(c), Offset(o), Alignment(Align) {}
 public:
 
   Constant *get() const { return C; }
+  int getOffset() const { return Offset; }
+  
+  // Return the alignment of this constant pool object, which is either 0 (for
+  // default alignment) or log2 of the desired value.
   unsigned getAlignment() const { return Alignment; }
 
   static bool classof(const ConstantPoolSDNode *) { return true; }