include/llvm/CodeGen/SelectionDAGNodes.h

   1 //===-- llvm/CodeGen/SelectionDAGNodes.h - SelectionDAG Nodes ---*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file declares the SDNode class and derived classes, which are used to
  11 // represent the nodes and operations present in a SelectionDAG.  These nodes
  12 // and operations are machine code level operations, with some similarities to
  13 // the GCC RTL representation.
  14 //
  15 // Clients should include the SelectionDAG.h file instead of this file directly.
  16 //
  17 //===----------------------------------------------------------------------===//
  18
  19 #ifndef LLVM_CODEGEN_SELECTIONDAGNODES_H
  20 #define LLVM_CODEGEN_SELECTIONDAGNODES_H
  21
  22 #include "llvm/CodeGen/ValueTypes.h"
  23 #include "llvm/Value.h"
  24 #include "llvm/ADT/GraphTraits.h"
  25 #include "llvm/ADT/iterator"
  26 #include "llvm/Support/DataTypes.h"
  27 #include <cassert>
  28 #include <vector>
  29
  30 namespace llvm {
  31
  32 class SelectionDAG;
  33 class GlobalValue;
  34 class MachineBasicBlock;
  35 class SDNode;
  36 template <typename T> struct simplify_type;
  37 template <typename T> struct ilist_traits;
  38 template<typename NodeTy, typename Traits> class iplist;
  39 template<typename NodeTy> class ilist_iterator;
  40
  41 /// ISD namespace - This namespace contains an enum which represents all of the
  42 /// SelectionDAG node types and value types.
  43 ///
  44 namespace ISD {
  45   //===--------------------------------------------------------------------===//
  46   /// ISD::NodeType enum - This enum defines all of the operators valid in a
  47   /// SelectionDAG.
  48   ///
  49   enum NodeType {
  50     // EntryToken - This is the marker used to indicate the start of the region.
  51     EntryToken,
  52
  53     // Token factor - This node takes multiple tokens as input and produces a
  54     // single token result.  This is used to represent the fact that the operand
  55     // operators are independent of each other.
  56     TokenFactor,
  57
  58     // AssertSext, AssertZext - These nodes record if a register contains a
  59     // value that has already been zero or sign extended from a narrower type.
  60     // These nodes take two operands.  The first is the node that has already
  61     // been extended, and the second is a value type node indicating the width
  62     // of the extension
  63     AssertSext, AssertZext,
  64
  65     // Various leaf nodes.
  66     STRING, BasicBlock, VALUETYPE, CONDCODE, Register,
  67     Constant, ConstantFP,
  68     GlobalAddress, FrameIndex, ConstantPool, ExternalSymbol,
  69
  70     // TargetConstant* - Like Constant*, but the DAG does not do any folding or
  71     // simplification of the constant.
  72     TargetConstant,
  73     TargetConstantFP,
  74
  75     // TargetGlobalAddress - Like GlobalAddress, but the DAG does no folding or
  76     // anything else with this node, and this is valid in the target-specific
  77     // dag, turning into a GlobalAddress operand.
  78     TargetGlobalAddress,
  79     TargetFrameIndex,
  80     TargetConstantPool,
  81     TargetExternalSymbol,
  82
  83     /// RESULT = INTRINSIC_WO_CHAIN(INTRINSICID, arg1, arg2, ...)
  84     /// This node represents a target intrinsic function with no side effects.
  85     /// The first operand is the ID number of the intrinsic from the
  86     /// llvm::Intrinsic namespace.  The operands to the intrinsic follow.  The
  87     /// node has returns the result of the intrinsic.
  88     INTRINSIC_WO_CHAIN,
  89
  90     /// RESULT,OUTCHAIN = INTRINSIC_W_CHAIN(INCHAIN, INTRINSICID, arg1, ...)
  91     /// This node represents a target intrinsic function with side effects that
  92     /// returns a result.  The first operand is a chain pointer.  The second is
  93     /// the ID number of the intrinsic from the llvm::Intrinsic namespace.  The
  94     /// operands to the intrinsic follow.  The node has two results, the result
  95     /// of the intrinsic and an output chain.
  96     INTRINSIC_W_CHAIN,
  97
  98     /// OUTCHAIN = INTRINSIC_VOID(INCHAIN, INTRINSICID, arg1, arg2, ...)
  99     /// This node represents a target intrinsic function with side effects that
 100     /// does not return a result.  The first operand is a chain pointer.  The
 101     /// second is the ID number of the intrinsic from the llvm::Intrinsic
 102     /// namespace.  The operands to the intrinsic follow.
 103     INTRINSIC_VOID,
 104
 105     // CopyToReg - This node has three operands: a chain, a register number to
 106     // set to this value, and a value.
 107     CopyToReg,
 108
 109     // CopyFromReg - This node indicates that the input value is a virtual or
 110     // physical register that is defined outside of the scope of this
 111     // SelectionDAG.  The register is available from the RegSDNode object.
 112     CopyFromReg,
 113
 114     // UNDEF - An undefined node
 115     UNDEF,
 116
 117     // EXTRACT_ELEMENT - This is used to get the first or second (determined by
 118     // a Constant, which is required to be operand #1), element of the aggregate
 119     // value specified as operand #0.  This is only for use before legalization,
 120     // for values that will be broken into multiple registers.
 121     EXTRACT_ELEMENT,
 122
 123     // BUILD_PAIR - This is the opposite of EXTRACT_ELEMENT in some ways.  Given
 124     // two values of the same integer value type, this produces a value twice as
 125     // big.  Like EXTRACT_ELEMENT, this can only be used before legalization.
 126     BUILD_PAIR,
 127
 128     // MERGE_VALUES - This node takes multiple discrete operands and returns
 129     // them all as its individual results.  This nodes has exactly the same
 130     // number of inputs and outputs, and is only valid before legalization.
 131     // This node is useful for some pieces of the code generator that want to
 132     // think about a single node with multiple results, not multiple nodes.
 133     MERGE_VALUES,
 134
 135     // Simple integer binary arithmetic operators.
 136     ADD, SUB, MUL, SDIV, UDIV, SREM, UREM,
 137
 138     // Carry-setting nodes for multiple precision addition and subtraction.
 139     // These nodes take two operands of the same value type, and produce two
 140     // results.  The first result is the normal add or sub result, the second
 141     // result is the carry flag result.
 142     ADDC, SUBC,
 143
 144     // Carry-using nodes for multiple precision addition and subtraction.  These
 145     // nodes take three operands: The first two are the normal lhs and rhs to
 146     // the add or sub, and the third is the input carry flag.  These nodes
 147     // produce two results; the normal result of the add or sub, and the output
 148     // carry flag.  These nodes both read and write a carry flag to allow them
 149     // to them to be chained together for add and sub of arbitrarily large
 150     // values.
 151     ADDE, SUBE,
 152
 153     // Simple binary floating point operators.
 154     FADD, FSUB, FMUL, FDIV, FREM,
 155
 156     // FCOPYSIGN(X, Y) - Return the value of X with the sign of Y.  NOTE: This
 157     // DAG node does not require that X and Y have the same type, just that they
 158     // are both floating point.  X and the result must have the same type.
 159     // FCOPYSIGN(f32, f64) is allowed.
 160     FCOPYSIGN,
 161
 162     /// VBUILD_VECTOR(ELT1, ELT2, ELT3, ELT4,...,  COUNT,TYPE) - Return a vector
 163     /// with the specified, possibly variable, elements.  The number of elements
 164     /// is required to be a power of two.
 165     VBUILD_VECTOR,
 166
 167     /// BUILD_VECTOR(ELT1, ELT2, ELT3, ELT4,...) - Return a vector
 168     /// with the specified, possibly variable, elements.  The number of elements
 169     /// is required to be a power of two.
 170     BUILD_VECTOR,
 171
 172     /// VINSERT_VECTOR_ELT(VECTOR, VAL, IDX,  COUNT,TYPE) - Given a vector
 173     /// VECTOR, an element ELEMENT, and a (potentially variable) index IDX,
 174     /// return an vector with the specified element of VECTOR replaced with VAL.
 175     /// COUNT and TYPE specify the type of vector, as is standard for V* nodes.
 176     VINSERT_VECTOR_ELT,
 177
 178     /// INSERT_VECTOR_ELT(VECTOR, VAL, IDX) - Returns VECTOR (a legal packed
 179     /// type) with the element at IDX replaced with VAL.
 180     INSERT_VECTOR_ELT,
 181
 182     /// VEXTRACT_VECTOR_ELT(VECTOR, IDX) - Returns a single element from VECTOR
 183     /// (an MVT::Vector value) identified by the (potentially variable) element
 184     /// number IDX.
 185     VEXTRACT_VECTOR_ELT,
 186
 187     /// EXTRACT_VECTOR_ELT(VECTOR, IDX) - Returns a single element from VECTOR
 188     /// (a legal packed type vector) identified by the (potentially variable)
 189     /// element number IDX.
 190     EXTRACT_VECTOR_ELT,
 191
 192     /// VVECTOR_SHUFFLE(VEC1, VEC2, SHUFFLEVEC, COUNT,TYPE) - Returns a vector,
 193     /// of the same type as VEC1/VEC2.  SHUFFLEVEC is a VBUILD_VECTOR of
 194     /// constant int values that indicate which value each result element will
 195     /// get.  The elements of VEC1/VEC2 are enumerated in order.  This is quite
 196     /// similar to the Altivec 'vperm' instruction, except that the indices must
 197     /// be constants and are in terms of the element size of VEC1/VEC2, not in
 198     /// terms of bytes.
 199     VVECTOR_SHUFFLE,
 200
 201     /// VECTOR_SHUFFLE(VEC1, VEC2, SHUFFLEVEC) - Returns a vector, of the same
 202     /// type as VEC1/VEC2.  SHUFFLEVEC is a BUILD_VECTOR of constant int values
 203     /// (regardless of whether its datatype is legal or not) that indicate
 204     /// which value each result element will get.  The elements of VEC1/VEC2 are
 205     /// enumerated in order.  This is quite similar to the Altivec 'vperm'
 206     /// instruction, except that the indices must be constants and are in terms
 207     /// of the element size of VEC1/VEC2, not in terms of bytes.
 208     VECTOR_SHUFFLE,
 209
 210     /// X = VBIT_CONVERT(Y)  and X = VBIT_CONVERT(Y, COUNT,TYPE) - This node
 211     /// represents a conversion from or to an ISD::Vector type.
 212     ///
 213     /// This is lowered to a BIT_CONVERT of the appropriate input/output types.
 214     /// The input and output are required to have the same size and at least one
 215     /// is required to be a vector (if neither is a vector, just use
 216     /// BIT_CONVERT).
 217     ///
 218     /// If the result is a vector, this takes three operands (like any other
 219     /// vector producer) which indicate the size and type of the vector result.
 220     /// Otherwise it takes one input.
 221     VBIT_CONVERT,
 222
 223     /// BINOP(LHS, RHS,  COUNT,TYPE)
 224     /// Simple abstract vector operators.  Unlike the integer and floating point
 225     /// binary operators, these nodes also take two additional operands:
 226     /// a constant element count, and a value type node indicating the type of
 227     /// the elements.  The order is count, type, op0, op1.  All vector opcodes,
 228     /// including VLOAD and VConstant must currently have count and type as
 229     /// their last two operands.
 230     VADD, VSUB, VMUL, VSDIV, VUDIV,
 231     VAND, VOR, VXOR,
 232
 233     /// SCALAR_TO_VECTOR(VAL) - This represents the operation of loading a
 234     /// scalar value into the low element of the resultant vector type.  The top
 235     /// elements of the vector are undefined.
 236     SCALAR_TO_VECTOR,
 237
 238     // MULHU/MULHS - Multiply high - Multiply two integers of type iN, producing
 239     // an unsigned/signed value of type i[2*n], then return the top part.
 240     MULHU, MULHS,
 241
 242     // Bitwise operators - logical and, logical or, logical xor, shift left,
 243     // shift right algebraic (shift in sign bits), shift right logical (shift in
 244     // zeroes), rotate left, rotate right, and byteswap.
 245     AND, OR, XOR, SHL, SRA, SRL, ROTL, ROTR, BSWAP,
 246
 247     // Counting operators
 248     CTTZ, CTLZ, CTPOP,
 249
 250     // Select(COND, TRUEVAL, FALSEVAL)
 251     SELECT,
 252
 253     // Select with condition operator - This selects between a true value and
 254     // a false value (ops #2 and #3) based on the boolean result of comparing
 255     // the lhs and rhs (ops #0 and #1) of a conditional expression with the
 256     // condition code in op #4, a CondCodeSDNode.
 257     SELECT_CC,
 258
 259     // SetCC operator - This evaluates to a boolean (i1) true value if the
 260     // condition is true.  The operands to this are the left and right operands
 261     // to compare (ops #0, and #1) and the condition code to compare them with
 262     // (op #2) as a CondCodeSDNode.
 263     SETCC,
 264
 265     // SHL_PARTS/SRA_PARTS/SRL_PARTS - These operators are used for expanded
 266     // integer shift operations, just like ADD/SUB_PARTS.  The operation
 267     // ordering is:
 268     //       [Lo,Hi] = op [LoLHS,HiLHS], Amt
 269     SHL_PARTS, SRA_PARTS, SRL_PARTS,
 270
 271     // Conversion operators.  These are all single input single output
 272     // operations.  For all of these, the result type must be strictly
 273     // wider or narrower (depending on the operation) than the source
 274     // type.
 275
 276     // SIGN_EXTEND - Used for integer types, replicating the sign bit
 277     // into new bits.
 278     SIGN_EXTEND,
 279
 280     // ZERO_EXTEND - Used for integer types, zeroing the new bits.
 281     ZERO_EXTEND,
 282
 283     // ANY_EXTEND - Used for integer types.  The high bits are undefined.
 284     ANY_EXTEND,
 285
 286     // TRUNCATE - Completely drop the high bits.
 287     TRUNCATE,
 288
 289     // [SU]INT_TO_FP - These operators convert integers (whose interpreted sign
 290     // depends on the first letter) to floating point.
 291     SINT_TO_FP,
 292     UINT_TO_FP,
 293
 294     // SIGN_EXTEND_INREG - This operator atomically performs a SHL/SRA pair to
 295     // sign extend a small value in a large integer register (e.g. sign
 296     // extending the low 8 bits of a 32-bit register to fill the top 24 bits
 297     // with the 7th bit).  The size of the smaller type is indicated by the 1th
 298     // operand, a ValueType node.
 299     SIGN_EXTEND_INREG,
 300
 301     // FP_TO_[US]INT - Convert a floating point value to a signed or unsigned
 302     // integer.
 303     FP_TO_SINT,
 304     FP_TO_UINT,
 305
 306     // FP_ROUND - Perform a rounding operation from the current
 307     // precision down to the specified precision (currently always 64->32).
 308     FP_ROUND,
 309
 310     // FP_ROUND_INREG - This operator takes a floating point register, and
 311     // rounds it to a floating point value.  It then promotes it and returns it
 312     // in a register of the same size.  This operation effectively just discards
 313     // excess precision.  The type to round down to is specified by the 1th
 314     // operation, a VTSDNode (currently always 64->32->64).
 315     FP_ROUND_INREG,
 316
 317     // FP_EXTEND - Extend a smaller FP type into a larger FP type.
 318     FP_EXTEND,
 319
 320     // BIT_CONVERT - Theis operator converts between integer and FP values, as
 321     // if one was stored to memory as integer and the other was loaded from the
 322     // same address (or equivalently for vector format conversions, etc).  The
 323     // source and result are required to have the same bit size (e.g.
 324     // f32 <-> i32).  This can also be used for int-to-int or fp-to-fp
 325     // conversions, but that is a noop, deleted by getNode().
 326     BIT_CONVERT,
 327
 328     // FNEG, FABS, FSQRT, FSIN, FCOS - Perform unary floating point negation,
 329     // absolute value, square root, sine and cosine operations.
 330     FNEG, FABS, FSQRT, FSIN, FCOS,
 331
 332     // Other operators.  LOAD and STORE have token chains as their first
 333     // operand, then the same operands as an LLVM load/store instruction, then a
 334     // SRCVALUE node that provides alias analysis information.
 335     LOAD, STORE,
 336
 337     // Abstract vector version of LOAD.  VLOAD has a constant element count as
 338     // the first operand, followed by a value type node indicating the type of
 339     // the elements, a token chain, a pointer operand, and a SRCVALUE node.
 340     VLOAD,
 341
 342     // EXTLOAD, SEXTLOAD, ZEXTLOAD - These three operators all load a value from
 343     // memory and extend them to a larger value (e.g. load a byte into a word
 344     // register).  All three of these have four operands, a token chain, a
 345     // pointer to load from, a SRCVALUE for alias analysis, and a VALUETYPE node
 346     // indicating the type to load.
 347     //
 348     // SEXTLOAD loads the integer operand and sign extends it to a larger
 349     //          integer result type.
 350     // ZEXTLOAD loads the integer operand and zero extends it to a larger
 351     //          integer result type.
 352     // EXTLOAD  is used for three things: floating point extending loads,
 353     //          integer extending loads [the top bits are undefined], and vector
 354     //          extending loads [load into low elt].
 355     EXTLOAD, SEXTLOAD, ZEXTLOAD,
 356
 357     // TRUNCSTORE - This operators truncates (for integer) or rounds (for FP) a
 358     // value and stores it to memory in one operation.  This can be used for
 359     // either integer or floating point operands.  The first four operands of
 360     // this are the same as a standard store.  The fifth is the ValueType to
 361     // store it as (which will be smaller than the source value).
 362     TRUNCSTORE,
 363
 364     // DYNAMIC_STACKALLOC - Allocate some number of bytes on the stack aligned
 365     // to a specified boundary.  The first operand is the token chain, the
 366     // second is the number of bytes to allocate, and the third is the alignment
 367     // boundary.  The size is guaranteed to be a multiple of the stack
 368     // alignment, and the alignment is guaranteed to be bigger than the stack
 369     // alignment (if required) or 0 to get standard stack alignment.
 370     DYNAMIC_STACKALLOC,
 371
 372     // Control flow instructions.  These all have token chains.
 373
 374     // BR - Unconditional branch.  The first operand is the chain
 375     // operand, the second is the MBB to branch to.
 376     BR,
 377
 378     // BRCOND - Conditional branch.  The first operand is the chain,
 379     // the second is the condition, the third is the block to branch
 380     // to if the condition is true.
 381     BRCOND,
 382
 383     // BR_CC - Conditional branch.  The behavior is like that of SELECT_CC, in
 384     // that the condition is represented as condition code, and two nodes to
 385     // compare, rather than as a combined SetCC node.  The operands in order are
 386     // chain, cc, lhs, rhs, block to branch to if condition is true.
 387     BR_CC,
 388
 389     // RET - Return from function.  The first operand is the chain,
 390     // and any subsequent operands are the return values for the
 391     // function.  This operation can have variable number of operands.
 392     RET,
 393
 394     // INLINEASM - Represents an inline asm block.  This node always has two
 395     // return values: a chain and a flag result.  The inputs are as follows:
 396     //   Operand #0   : Input chain.
 397     //   Operand #1   : a ExternalSymbolSDNode with a pointer to the asm string.
 398     //   Operand #2n+2: A RegisterNode.
 399     //   Operand #2n+3: A TargetConstant, indicating if the reg is a use/def
 400     //   Operand #last: Optional, an incoming flag.
 401     INLINEASM,
 402
 403     // STACKSAVE - STACKSAVE has one operand, an input chain.  It produces a
 404     // value, the same type as the pointer type for the system, and an output
 405     // chain.
 406     STACKSAVE,
 407
 408     // STACKRESTORE has two operands, an input chain and a pointer to restore to
 409     // it returns an output chain.
 410     STACKRESTORE,
 411
 412     // MEMSET/MEMCPY/MEMMOVE - The first operand is the chain, and the rest
 413     // correspond to the operands of the LLVM intrinsic functions.  The only
 414     // result is a token chain.  The alignment argument is guaranteed to be a
 415     // Constant node.
 416     MEMSET,
 417     MEMMOVE,
 418     MEMCPY,
 419
 420     // CALLSEQ_START/CALLSEQ_END - These operators mark the beginning and end of
 421     // a call sequence, and carry arbitrary information that target might want
 422     // to know.  The first operand is a chain, the rest are specified by the
 423     // target and not touched by the DAG optimizers.
 424     CALLSEQ_START,  // Beginning of a call sequence
 425     CALLSEQ_END,    // End of a call sequence
 426
 427     // VAARG - VAARG has three operands: an input chain, a pointer, and a
 428     // SRCVALUE.  It returns a pair of values: the vaarg value and a new chain.
 429     VAARG,
 430
 431     // VACOPY - VACOPY has five operands: an input chain, a destination pointer,
 432     // a source pointer, a SRCVALUE for the destination, and a SRCVALUE for the
 433     // source.
 434     VACOPY,
 435
 436     // VAEND, VASTART - VAEND and VASTART have three operands: an input chain, a
 437     // pointer, and a SRCVALUE.
 438     VAEND, VASTART,
 439
 440     // SRCVALUE - This corresponds to a Value*, and is used to associate memory
 441     // locations with their value.  This allows one use alias analysis
 442     // information in the backend.
 443     SRCVALUE,
 444
 445     // PCMARKER - This corresponds to the pcmarker intrinsic.
 446     PCMARKER,
 447
 448     // READCYCLECOUNTER - This corresponds to the readcyclecounter intrinsic.
 449     // The only operand is a chain and a value and a chain are produced.  The
 450     // value is the contents of the architecture specific cycle counter like
 451     // register (or other high accuracy low latency clock source)
 452     READCYCLECOUNTER,
 453
 454     // HANDLENODE node - Used as a handle for various purposes.
 455     HANDLENODE,
 456
 457     // LOCATION - This node is used to represent a source location for debug
 458     // info.  It takes token chain as input, then a line number, then a column
 459     // number, then a filename, then a working dir.  It produces a token chain
 460     // as output.
 461     LOCATION,
 462
 463     // DEBUG_LOC - This node is used to represent source line information
 464     // embedded in the code.  It takes a token chain as input, then a line
 465     // number, then a column then a file id (provided by MachineDebugInfo.) It
 466     // produces a token chain as output.
 467     DEBUG_LOC,
 468
 469     // DEBUG_LABEL - This node is used to mark a location in the code where a
 470     // label should be generated for use by the debug information.  It takes a
 471     // token chain as input and then a unique id (provided by MachineDebugInfo.)
 472     // It produces a token chain as output.
 473     DEBUG_LABEL,
 474
 475     // BUILTIN_OP_END - This must be the last enum value in this list.
 476     BUILTIN_OP_END
 477   };
 478
 479   /// Node predicates
 480
 481   /// isBuildVectorAllOnes - Return true if the specified node is a
 482   /// BUILD_VECTOR where all of the elements are ~0 or undef.
 483   bool isBuildVectorAllOnes(const SDNode *N);
 484
 485   /// isBuildVectorAllZeros - Return true if the specified node is a
 486   /// BUILD_VECTOR where all of the elements are 0 or undef.
 487   bool isBuildVectorAllZeros(const SDNode *N);
 488
 489   //===--------------------------------------------------------------------===//
 490   /// ISD::CondCode enum - These are ordered carefully to make the bitfields
 491   /// below work out, when considering SETFALSE (something that never exists
 492   /// dynamically) as 0.  "U" -> Unsigned (for integer operands) or Unordered
 493   /// (for floating point), "L" -> Less than, "G" -> Greater than, "E" -> Equal
 494   /// to.  If the "N" column is 1, the result of the comparison is undefined if
 495   /// the input is a NAN.
 496   ///
 497   /// All of these (except for the 'always folded ops') should be handled for
 498   /// floating point.  For integer, only the SETEQ,SETNE,SETLT,SETLE,SETGT,
 499   /// SETGE,SETULT,SETULE,SETUGT, and SETUGE opcodes are used.
 500   ///
 501   /// Note that these are laid out in a specific order to allow bit-twiddling
 502   /// to transform conditions.
 503   enum CondCode {
 504     // Opcode          N U L G E       Intuitive operation
 505     SETFALSE,      //    0 0 0 0       Always false (always folded)
 506     SETOEQ,        //    0 0 0 1       True if ordered and equal
 507     SETOGT,        //    0 0 1 0       True if ordered and greater than
 508     SETOGE,        //    0 0 1 1       True if ordered and greater than or equal
 509     SETOLT,        //    0 1 0 0       True if ordered and less than
 510     SETOLE,        //    0 1 0 1       True if ordered and less than or equal
 511     SETONE,        //    0 1 1 0       True if ordered and operands are unequal
 512     SETO,          //    0 1 1 1       True if ordered (no nans)
 513     SETUO,         //    1 0 0 0       True if unordered: isnan(X) | isnan(Y)
 514     SETUEQ,        //    1 0 0 1       True if unordered or equal
 515     SETUGT,        //    1 0 1 0       True if unordered or greater than
 516     SETUGE,        //    1 0 1 1       True if unordered, greater than, or equal
 517     SETULT,        //    1 1 0 0       True if unordered or less than
 518     SETULE,        //    1 1 0 1       True if unordered, less than, or equal
 519     SETUNE,        //    1 1 1 0       True if unordered or not equal
 520     SETTRUE,       //    1 1 1 1       Always true (always folded)
 521     // Don't care operations: undefined if the input is a nan.
 522     SETFALSE2,     //  1 X 0 0 0       Always false (always folded)
 523     SETEQ,         //  1 X 0 0 1       True if equal
 524     SETGT,         //  1 X 0 1 0       True if greater than
 525     SETGE,         //  1 X 0 1 1       True if greater than or equal
 526     SETLT,         //  1 X 1 0 0       True if less than
 527     SETLE,         //  1 X 1 0 1       True if less than or equal
 528     SETNE,         //  1 X 1 1 0       True if not equal
 529     SETTRUE2,      //  1 X 1 1 1       Always true (always folded)
 530
 531     SETCC_INVALID       // Marker value.
 532   };
 533
 534   /// isSignedIntSetCC - Return true if this is a setcc instruction that
 535   /// performs a signed comparison when used with integer operands.
 536   inline bool isSignedIntSetCC(CondCode Code) {
 537     return Code == SETGT || Code == SETGE || Code == SETLT || Code == SETLE;
 538   }
 539
 540   /// isUnsignedIntSetCC - Return true if this is a setcc instruction that
 541   /// performs an unsigned comparison when used with integer operands.
 542   inline bool isUnsignedIntSetCC(CondCode Code) {
 543     return Code == SETUGT || Code == SETUGE || Code == SETULT || Code == SETULE;
 544   }
 545
 546   /// isTrueWhenEqual - Return true if the specified condition returns true if
 547   /// the two operands to the condition are equal.  Note that if one of the two
 548   /// operands is a NaN, this value is meaningless.
 549   inline bool isTrueWhenEqual(CondCode Cond) {
 550     return ((int)Cond & 1) != 0;
 551   }
 552
 553   /// getUnorderedFlavor - This function returns 0 if the condition is always
 554   /// false if an operand is a NaN, 1 if the condition is always true if the
 555   /// operand is a NaN, and 2 if the condition is undefined if the operand is a
 556   /// NaN.
 557   inline unsigned getUnorderedFlavor(CondCode Cond) {
 558     return ((int)Cond >> 3) & 3;
 559   }
 560
 561   /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
 562   /// 'op' is a valid SetCC operation.
 563   CondCode getSetCCInverse(CondCode Operation, bool isInteger);
 564
 565   /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
 566   /// when given the operation for (X op Y).
 567   CondCode getSetCCSwappedOperands(CondCode Operation);
 568
 569   /// getSetCCOrOperation - Return the result of a logical OR between different
 570   /// comparisons of identical values: ((X op1 Y) | (X op2 Y)).  This
 571   /// function returns SETCC_INVALID if it is not possible to represent the
 572   /// resultant comparison.
 573   CondCode getSetCCOrOperation(CondCode Op1, CondCode Op2, bool isInteger);
 574
 575   /// getSetCCAndOperation - Return the result of a logical AND between
 576   /// different comparisons of identical values: ((X op1 Y) & (X op2 Y)).  This
 577   /// function returns SETCC_INVALID if it is not possible to represent the
 578   /// resultant comparison.
 579   CondCode getSetCCAndOperation(CondCode Op1, CondCode Op2, bool isInteger);
 580 }  // end llvm::ISD namespace
 581
 582
 583 //===----------------------------------------------------------------------===//
 584 /// SDOperand - Unlike LLVM values, Selection DAG nodes may return multiple
 585 /// values as the result of a computation.  Many nodes return multiple values,
 586 /// from loads (which define a token and a return value) to ADDC (which returns
 587 /// a result and a carry value), to calls (which may return an arbitrary number
 588 /// of values).
 589 ///
 590 /// As such, each use of a SelectionDAG computation must indicate the node that
 591 /// computes it as well as which return value to use from that node.  This pair
 592 /// of information is represented with the SDOperand value type.
 593 ///
 594 class SDOperand {
 595 public:
 596   SDNode *Val;        // The node defining the value we are using.
 597   unsigned ResNo;     // Which return value of the node we are using.
 598
 599   SDOperand() : Val(0) {}
 600   SDOperand(SDNode *val, unsigned resno) : Val(val), ResNo(resno) {}
 601
 602   bool operator==(const SDOperand &O) const {
 603     return Val == O.Val && ResNo == O.ResNo;
 604   }
 605   bool operator!=(const SDOperand &O) const {
 606     return !operator==(O);
 607   }
 608   bool operator<(const SDOperand &O) const {
 609     return Val < O.Val || (Val == O.Val && ResNo < O.ResNo);
 610   }
 611
 612   SDOperand getValue(unsigned R) const {
 613     return SDOperand(Val, R);
 614   }
 615
 616   // isOperand - Return true if this node is an operand of N.
 617   bool isOperand(SDNode *N) const;
 618
 619   /// getValueType - Return the ValueType of the referenced return value.
 620   ///
 621   inline MVT::ValueType getValueType() const;
 622
 623   // Forwarding methods - These forward to the corresponding methods in SDNode.
 624   inline unsigned getOpcode() const;
 625   inline unsigned getNodeDepth() const;
 626   inline unsigned getNumOperands() const;
 627   inline const SDOperand &getOperand(unsigned i) const;
 628   inline bool isTargetOpcode() const;
 629   inline unsigned getTargetOpcode() const;
 630
 631   /// hasOneUse - Return true if there is exactly one operation using this
 632   /// result value of the defining operator.
 633   inline bool hasOneUse() const;
 634 };
 635
 636
 637 /// simplify_type specializations - Allow casting operators to work directly on
 638 /// SDOperands as if they were SDNode*'s.
 639 template<> struct simplify_type<SDOperand> {
 640   typedef SDNode* SimpleType;
 641   static SimpleType getSimplifiedValue(const SDOperand &Val) {
 642     return static_cast<SimpleType>(Val.Val);
 643   }
 644 };
 645 template<> struct simplify_type<const SDOperand> {
 646   typedef SDNode* SimpleType;
 647   static SimpleType getSimplifiedValue(const SDOperand &Val) {
 648     return static_cast<SimpleType>(Val.Val);
 649   }
 650 };
 651
 652
 653 /// SDNode - Represents one node in the SelectionDAG.
 654 ///
 655 class SDNode {
 656   /// NodeType - The operation that this node performs.
 657   ///
 658   unsigned short NodeType;
 659
 660   /// NodeDepth - Node depth is defined as MAX(Node depth of children)+1.  This
 661   /// means that leaves have a depth of 1, things that use only leaves have a
 662   /// depth of 2, etc.
 663   unsigned short NodeDepth;
 664
 665   /// OperandList - The values that are used by this operation.
 666   ///
 667   SDOperand *OperandList;
 668
 669   /// ValueList - The types of the values this node defines.  SDNode's may
 670   /// define multiple values simultaneously.
 671   MVT::ValueType *ValueList;
 672
 673   /// NumOperands/NumValues - The number of entries in the Operand/Value list.
 674   unsigned short NumOperands, NumValues;
 675
 676   /// Prev/Next pointers - These pointers form the linked list of of the
 677   /// AllNodes list in the current DAG.
 678   SDNode *Prev, *Next;
 679   friend struct ilist_traits<SDNode>;
 680
 681   /// Uses - These are all of the SDNode's that use a value produced by this
 682   /// node.
 683   std::vector<SDNode*> Uses;
 684 public:
 685   virtual ~SDNode() {
 686     assert(NumOperands == 0 && "Operand list not cleared before deletion");
 687   }
 688
 689   //===--------------------------------------------------------------------===//
 690   //  Accessors
 691   //
 692   unsigned getOpcode()  const { return NodeType; }
 693   bool isTargetOpcode() const { return NodeType >= ISD::BUILTIN_OP_END; }
 694   unsigned getTargetOpcode() const {
 695     assert(isTargetOpcode() && "Not a target opcode!");
 696     return NodeType - ISD::BUILTIN_OP_END;
 697   }
 698
 699   size_t use_size() const { return Uses.size(); }
 700   bool use_empty() const { return Uses.empty(); }
 701   bool hasOneUse() const { return Uses.size() == 1; }
 702
 703   /// getNodeDepth - Return the distance from this node to the leaves in the
 704   /// graph.  The leaves have a depth of 1.
 705   unsigned getNodeDepth() const { return NodeDepth; }
 706
 707   typedef std::vector<SDNode*>::const_iterator use_iterator;
 708   use_iterator use_begin() const { return Uses.begin(); }
 709   use_iterator use_end() const { return Uses.end(); }
 710
 711   /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
 712   /// indicated value.  This method ignores uses of other values defined by this
 713   /// operation.
 714   bool hasNUsesOfValue(unsigned NUses, unsigned Value) const;
 715
 716   // isOnlyUse - Return true if this node is the only use of N.
 717   bool isOnlyUse(SDNode *N) const;
 718
 719   // isOperand - Return true if this node is an operand of N.
 720   bool isOperand(SDNode *N) const;
 721
 722   /// getNumOperands - Return the number of values used by this operation.
 723   ///
 724   unsigned getNumOperands() const { return NumOperands; }
 725
 726   const SDOperand &getOperand(unsigned Num) const {
 727     assert(Num < NumOperands && "Invalid child # of SDNode!");
 728     return OperandList[Num];
 729   }
 730   typedef const SDOperand* op_iterator;
 731   op_iterator op_begin() const { return OperandList; }
 732   op_iterator op_end() const { return OperandList+NumOperands; }
 733
 734
 735   /// getNumValues - Return the number of values defined/returned by this
 736   /// operator.
 737   ///
 738   unsigned getNumValues() const { return NumValues; }
 739
 740   /// getValueType - Return the type of a specified result.
 741   ///
 742   MVT::ValueType getValueType(unsigned ResNo) const {
 743     assert(ResNo < NumValues && "Illegal result number!");
 744     return ValueList[ResNo];
 745   }
 746
 747   typedef const MVT::ValueType* value_iterator;
 748   value_iterator value_begin() const { return ValueList; }
 749   value_iterator value_end() const { return ValueList+NumValues; }
 750
 751   /// getOperationName - Return the opcode of this operation for printing.
 752   ///
 753   const char* getOperationName(const SelectionDAG *G = 0) const;
 754   void dump() const;
 755   void dump(const SelectionDAG *G) const;
 756
 757   static bool classof(const SDNode *) { return true; }
 758
 759 protected:
 760   friend class SelectionDAG;
 761
 762   /// getValueTypeList - Return a pointer to the specified value type.
 763   ///
 764   static MVT::ValueType *getValueTypeList(MVT::ValueType VT);
 765
 766   SDNode(unsigned NT, MVT::ValueType VT) : NodeType(NT), NodeDepth(1) {
 767     OperandList = 0; NumOperands = 0;
 768     ValueList = getValueTypeList(VT);
 769     NumValues = 1;
 770     Prev = 0; Next = 0;
 771   }
 772   SDNode(unsigned NT, SDOperand Op)
 773     : NodeType(NT), NodeDepth(Op.Val->getNodeDepth()+1) {
 774     OperandList = new SDOperand[1];
 775     OperandList[0] = Op;
 776     NumOperands = 1;
 777     Op.Val->Uses.push_back(this);
 778     ValueList = 0;
 779     NumValues = 0;
 780     Prev = 0; Next = 0;
 781   }
 782   SDNode(unsigned NT, SDOperand N1, SDOperand N2)
 783     : NodeType(NT) {
 784     if (N1.Val->getNodeDepth() > N2.Val->getNodeDepth())
 785       NodeDepth = N1.Val->getNodeDepth()+1;
 786     else
 787       NodeDepth = N2.Val->getNodeDepth()+1;
 788     OperandList = new SDOperand[2];
 789     OperandList[0] = N1;
 790     OperandList[1] = N2;
 791     NumOperands = 2;
 792     N1.Val->Uses.push_back(this); N2.Val->Uses.push_back(this);
 793     ValueList = 0;
 794     NumValues = 0;
 795     Prev = 0; Next = 0;
 796   }
 797   SDNode(unsigned NT, SDOperand N1, SDOperand N2, SDOperand N3)
 798     : NodeType(NT) {
 799     unsigned ND = N1.Val->getNodeDepth();
 800     if (ND < N2.Val->getNodeDepth())
 801       ND = N2.Val->getNodeDepth();
 802     if (ND < N3.Val->getNodeDepth())
 803       ND = N3.Val->getNodeDepth();
 804     NodeDepth = ND+1;
 805
 806     OperandList = new SDOperand[3];
 807     OperandList[0] = N1;
 808     OperandList[1] = N2;
 809     OperandList[2] = N3;
 810     NumOperands = 3;
 811
 812     N1.Val->Uses.push_back(this); N2.Val->Uses.push_back(this);
 813     N3.Val->Uses.push_back(this);
 814     ValueList = 0;
 815     NumValues = 0;
 816     Prev = 0; Next = 0;
 817   }
 818   SDNode(unsigned NT, SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4)
 819     : NodeType(NT) {
 820     unsigned ND = N1.Val->getNodeDepth();
 821     if (ND < N2.Val->getNodeDepth())
 822       ND = N2.Val->getNodeDepth();
 823     if (ND < N3.Val->getNodeDepth())
 824       ND = N3.Val->getNodeDepth();
 825     if (ND < N4.Val->getNodeDepth())
 826       ND = N4.Val->getNodeDepth();
 827     NodeDepth = ND+1;
 828
 829     OperandList = new SDOperand[4];
 830     OperandList[0] = N1;
 831     OperandList[1] = N2;
 832     OperandList[2] = N3;
 833     OperandList[3] = N4;
 834     NumOperands = 4;
 835
 836     N1.Val->Uses.push_back(this); N2.Val->Uses.push_back(this);
 837     N3.Val->Uses.push_back(this); N4.Val->Uses.push_back(this);
 838     ValueList = 0;
 839     NumValues = 0;
 840     Prev = 0; Next = 0;
 841   }
 842   SDNode(unsigned Opc, const std::vector<SDOperand> &Nodes) : NodeType(Opc) {
 843     NumOperands = Nodes.size();
 844     OperandList = new SDOperand[NumOperands];
 845
 846     unsigned ND = 0;
 847     for (unsigned i = 0, e = Nodes.size(); i != e; ++i) {
 848       OperandList[i] = Nodes[i];
 849       SDNode *N = OperandList[i].Val;
 850       N->Uses.push_back(this);
 851       if (ND < N->getNodeDepth()) ND = N->getNodeDepth();
 852     }
 853     NodeDepth = ND+1;
 854     ValueList = 0;
 855     NumValues = 0;
 856     Prev = 0; Next = 0;
 857   }
 858
 859   /// MorphNodeTo - This clears the return value and operands list, and sets the
 860   /// opcode of the node to the specified value.  This should only be used by
 861   /// the SelectionDAG class.
 862   void MorphNodeTo(unsigned Opc) {
 863     NodeType = Opc;
 864     ValueList = 0;
 865     NumValues = 0;
 866
 867     // Clear the operands list, updating used nodes to remove this from their
 868     // use list.
 869     for (op_iterator I = op_begin(), E = op_end(); I != E; ++I)
 870       I->Val->removeUser(this);
 871     delete [] OperandList;
 872     OperandList = 0;
 873     NumOperands = 0;
 874   }
 875
 876   void setValueTypes(MVT::ValueType VT) {
 877     assert(NumValues == 0 && "Should not have values yet!");
 878     ValueList = getValueTypeList(VT);
 879     NumValues = 1;
 880   }
 881   void setValueTypes(MVT::ValueType *List, unsigned NumVal) {
 882     assert(NumValues == 0 && "Should not have values yet!");
 883     ValueList = List;
 884     NumValues = NumVal;
 885   }
 886
 887   void setOperands(SDOperand Op0) {
 888     assert(NumOperands == 0 && "Should not have operands yet!");
 889     OperandList = new SDOperand[1];
 890     OperandList[0] = Op0;
 891     NumOperands = 1;
 892     Op0.Val->Uses.push_back(this);
 893   }
 894   void setOperands(SDOperand Op0, SDOperand Op1) {
 895     assert(NumOperands == 0 && "Should not have operands yet!");
 896     OperandList = new SDOperand[2];
 897     OperandList[0] = Op0;
 898     OperandList[1] = Op1;
 899     NumOperands = 2;
 900     Op0.Val->Uses.push_back(this); Op1.Val->Uses.push_back(this);
 901   }
 902   void setOperands(SDOperand Op0, SDOperand Op1, SDOperand Op2) {
 903     assert(NumOperands == 0 && "Should not have operands yet!");
 904     OperandList = new SDOperand[3];
 905     OperandList[0] = Op0;
 906     OperandList[1] = Op1;
 907     OperandList[2] = Op2;
 908     NumOperands = 3;
 909     Op0.Val->Uses.push_back(this); Op1.Val->Uses.push_back(this);
 910     Op2.Val->Uses.push_back(this);
 911   }
 912   void setOperands(SDOperand Op0, SDOperand Op1, SDOperand Op2, SDOperand Op3) {
 913     assert(NumOperands == 0 && "Should not have operands yet!");
 914     OperandList = new SDOperand[4];
 915     OperandList[0] = Op0;
 916     OperandList[1] = Op1;
 917     OperandList[2] = Op2;
 918     OperandList[3] = Op3;
 919     NumOperands = 4;
 920     Op0.Val->Uses.push_back(this); Op1.Val->Uses.push_back(this);
 921     Op2.Val->Uses.push_back(this); Op3.Val->Uses.push_back(this);
 922   }
 923   void setOperands(SDOperand Op0, SDOperand Op1, SDOperand Op2, SDOperand Op3,
 924                    SDOperand Op4) {
 925     assert(NumOperands == 0 && "Should not have operands yet!");
 926     OperandList = new SDOperand[5];
 927     OperandList[0] = Op0;
 928     OperandList[1] = Op1;
 929     OperandList[2] = Op2;
 930     OperandList[3] = Op3;
 931     OperandList[4] = Op4;
 932     NumOperands = 5;
 933     Op0.Val->Uses.push_back(this); Op1.Val->Uses.push_back(this);
 934     Op2.Val->Uses.push_back(this); Op3.Val->Uses.push_back(this);
 935     Op4.Val->Uses.push_back(this);
 936   }
 937   void setOperands(SDOperand Op0, SDOperand Op1, SDOperand Op2, SDOperand Op3,
 938                    SDOperand Op4, SDOperand Op5) {
 939     assert(NumOperands == 0 && "Should not have operands yet!");
 940     OperandList = new SDOperand[6];
 941     OperandList[0] = Op0;
 942     OperandList[1] = Op1;
 943     OperandList[2] = Op2;
 944     OperandList[3] = Op3;
 945     OperandList[4] = Op4;
 946     OperandList[5] = Op5;
 947     NumOperands = 6;
 948     Op0.Val->Uses.push_back(this); Op1.Val->Uses.push_back(this);
 949     Op2.Val->Uses.push_back(this); Op3.Val->Uses.push_back(this);
 950     Op4.Val->Uses.push_back(this); Op5.Val->Uses.push_back(this);
 951   }
 952   void setOperands(SDOperand Op0, SDOperand Op1, SDOperand Op2, SDOperand Op3,
 953                    SDOperand Op4, SDOperand Op5, SDOperand Op6) {
 954     assert(NumOperands == 0 && "Should not have operands yet!");
 955     OperandList = new SDOperand[7];
 956     OperandList[0] = Op0;
 957     OperandList[1] = Op1;
 958     OperandList[2] = Op2;
 959     OperandList[3] = Op3;
 960     OperandList[4] = Op4;
 961     OperandList[5] = Op5;
 962     OperandList[6] = Op6;
 963     NumOperands = 7;
 964     Op0.Val->Uses.push_back(this); Op1.Val->Uses.push_back(this);
 965     Op2.Val->Uses.push_back(this); Op3.Val->Uses.push_back(this);
 966     Op4.Val->Uses.push_back(this); Op5.Val->Uses.push_back(this);
 967     Op6.Val->Uses.push_back(this);
 968   }
 969   void setOperands(SDOperand Op0, SDOperand Op1, SDOperand Op2, SDOperand Op3,
 970                    SDOperand Op4, SDOperand Op5, SDOperand Op6, SDOperand Op7) {
 971     assert(NumOperands == 0 && "Should not have operands yet!");
 972     OperandList = new SDOperand[8];
 973     OperandList[0] = Op0;
 974     OperandList[1] = Op1;
 975     OperandList[2] = Op2;
 976     OperandList[3] = Op3;
 977     OperandList[4] = Op4;
 978     OperandList[5] = Op5;
 979     OperandList[6] = Op6;
 980     OperandList[7] = Op7;
 981     NumOperands = 8;
 982     Op0.Val->Uses.push_back(this); Op1.Val->Uses.push_back(this);
 983     Op2.Val->Uses.push_back(this); Op3.Val->Uses.push_back(this);
 984     Op4.Val->Uses.push_back(this); Op5.Val->Uses.push_back(this);
 985     Op6.Val->Uses.push_back(this); Op7.Val->Uses.push_back(this);
 986   }
 987
 988   void addUser(SDNode *User) {
 989     Uses.push_back(User);
 990   }
 991   void removeUser(SDNode *User) {
 992     // Remove this user from the operand's use list.
 993     for (unsigned i = Uses.size(); ; --i) {
 994       assert(i != 0 && "Didn't find user!");
 995       if (Uses[i-1] == User) {
 996         Uses[i-1] = Uses.back();
 997         Uses.pop_back();
 998         return;
 999       }
1000     }
1001   }
1002 };
1003
1004
1005 // Define inline functions from the SDOperand class.
1006
1007 inline unsigned SDOperand::getOpcode() const {
1008   return Val->getOpcode();
1009 }
1010 inline unsigned SDOperand::getNodeDepth() const {
1011   return Val->getNodeDepth();
1012 }
1013 inline MVT::ValueType SDOperand::getValueType() const {
1014   return Val->getValueType(ResNo);
1015 }
1016 inline unsigned SDOperand::getNumOperands() const {
1017   return Val->getNumOperands();
1018 }
1019 inline const SDOperand &SDOperand::getOperand(unsigned i) const {
1020   return Val->getOperand(i);
1021 }
1022 inline bool SDOperand::isTargetOpcode() const {
1023   return Val->isTargetOpcode();
1024 }
1025 inline unsigned SDOperand::getTargetOpcode() const {
1026   return Val->getTargetOpcode();
1027 }
1028 inline bool SDOperand::hasOneUse() const {
1029   return Val->hasNUsesOfValue(1, ResNo);
1030 }
1031
1032 /// HandleSDNode - This class is used to form a handle around another node that
1033 /// is persistant and is updated across invocations of replaceAllUsesWith on its
1034 /// operand.  This node should be directly created by end-users and not added to
1035 /// the AllNodes list.
1036 class HandleSDNode : public SDNode {
1037 public:
1038   HandleSDNode(SDOperand X) : SDNode(ISD::HANDLENODE, X) {}
1039   ~HandleSDNode() {
1040     MorphNodeTo(ISD::HANDLENODE);  // Drops operand uses.
1041   }
1042
1043   SDOperand getValue() const { return getOperand(0); }
1044 };
1045
1046 class StringSDNode : public SDNode {
1047   std::string Value;
1048 protected:
1049   friend class SelectionDAG;
1050   StringSDNode(const std::string &val)
1051     : SDNode(ISD::STRING, MVT::Other), Value(val) {
1052   }
1053 public:
1054   const std::string &getValue() const { return Value; }
1055   static bool classof(const StringSDNode *) { return true; }
1056   static bool classof(const SDNode *N) {
1057     return N->getOpcode() == ISD::STRING;
1058   }
1059 };
1060
1061 class ConstantSDNode : public SDNode {
1062   uint64_t Value;
1063 protected:
1064   friend class SelectionDAG;
1065   ConstantSDNode(bool isTarget, uint64_t val, MVT::ValueType VT)
1066     : SDNode(isTarget ? ISD::TargetConstant : ISD::Constant, VT), Value(val) {
1067   }
1068 public:
1069
1070   uint64_t getValue() const { return Value; }
1071
1072   int64_t getSignExtended() const {
1073     unsigned Bits = MVT::getSizeInBits(getValueType(0));
1074     return ((int64_t)Value << (64-Bits)) >> (64-Bits);
1075   }
1076
1077   bool isNullValue() const { return Value == 0; }
1078   bool isAllOnesValue() const {
1079     return Value == MVT::getIntVTBitMask(getValueType(0));
1080   }
1081
1082   static bool classof(const ConstantSDNode *) { return true; }
1083   static bool classof(const SDNode *N) {
1084     return N->getOpcode() == ISD::Constant ||
1085            N->getOpcode() == ISD::TargetConstant;
1086   }
1087 };
1088
1089 class ConstantFPSDNode : public SDNode {
1090   double Value;
1091 protected:
1092   friend class SelectionDAG;
1093   ConstantFPSDNode(bool isTarget, double val, MVT::ValueType VT)
1094     : SDNode(isTarget ? ISD::TargetConstantFP : ISD::ConstantFP, VT),
1095       Value(val) {
1096   }
1097 public:
1098
1099   double getValue() const { return Value; }
1100
1101   /// isExactlyValue - We don't rely on operator== working on double values, as
1102   /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
1103   /// As such, this method can be used to do an exact bit-for-bit comparison of
1104   /// two floating point values.
1105   bool isExactlyValue(double V) const;
1106
1107   static bool classof(const ConstantFPSDNode *) { return true; }
1108   static bool classof(const SDNode *N) {
1109     return N->getOpcode() == ISD::ConstantFP ||
1110            N->getOpcode() == ISD::TargetConstantFP;
1111   }
1112 };
1113
1114 class GlobalAddressSDNode : public SDNode {
1115   GlobalValue *TheGlobal;
1116   int Offset;
1117 protected:
1118   friend class SelectionDAG;
1119   GlobalAddressSDNode(bool isTarget, const GlobalValue *GA, MVT::ValueType VT,
1120                       int o=0)
1121     : SDNode(isTarget ? ISD::TargetGlobalAddress : ISD::GlobalAddress, VT),
1122       Offset(o) {
1123     TheGlobal = const_cast<GlobalValue*>(GA);
1124   }
1125 public:
1126
1127   GlobalValue *getGlobal() const { return TheGlobal; }
1128   int getOffset() const { return Offset; }
1129
1130   static bool classof(const GlobalAddressSDNode *) { return true; }
1131   static bool classof(const SDNode *N) {
1132     return N->getOpcode() == ISD::GlobalAddress ||
1133            N->getOpcode() == ISD::TargetGlobalAddress;
1134   }
1135 };
1136
1137
1138 class FrameIndexSDNode : public SDNode {
1139   int FI;
1140 protected:
1141   friend class SelectionDAG;
1142   FrameIndexSDNode(int fi, MVT::ValueType VT, bool isTarg)
1143     : SDNode(isTarg ? ISD::TargetFrameIndex : ISD::FrameIndex, VT), FI(fi) {}
1144 public:
1145
1146   int getIndex() const { return FI; }
1147
1148   static bool classof(const FrameIndexSDNode *) { return true; }
1149   static bool classof(const SDNode *N) {
1150     return N->getOpcode() == ISD::FrameIndex ||
1151            N->getOpcode() == ISD::TargetFrameIndex;
1152   }
1153 };
1154
1155 class ConstantPoolSDNode : public SDNode {
1156   Constant *C;
1157   int Offset;
1158   unsigned Alignment;
1159 protected:
1160   friend class SelectionDAG;
1161   ConstantPoolSDNode(bool isTarget, Constant *c, MVT::ValueType VT,
1162                      int o=0)
1163     : SDNode(isTarget ? ISD::TargetConstantPool : ISD::ConstantPool, VT),
1164       C(c), Offset(o), Alignment(0) {}
1165   ConstantPoolSDNode(bool isTarget, Constant *c, MVT::ValueType VT, int o,
1166                      unsigned Align)
1167     : SDNode(isTarget ? ISD::TargetConstantPool : ISD::ConstantPool, VT),
1168       C(c), Offset(o), Alignment(Align) {}
1169 public:
1170
1171   Constant *get() const { return C; }
1172   int getOffset() const { return Offset; }
1173
1174   // Return the alignment of this constant pool object, which is either 0 (for
1175   // default alignment) or log2 of the desired value.
1176   unsigned getAlignment() const { return Alignment; }
1177
1178   static bool classof(const ConstantPoolSDNode *) { return true; }
1179   static bool classof(const SDNode *N) {
1180     return N->getOpcode() == ISD::ConstantPool ||
1181            N->getOpcode() == ISD::TargetConstantPool;
1182   }
1183 };
1184
1185 class BasicBlockSDNode : public SDNode {
1186   MachineBasicBlock *MBB;
1187 protected:
1188   friend class SelectionDAG;
1189   BasicBlockSDNode(MachineBasicBlock *mbb)
1190     : SDNode(ISD::BasicBlock, MVT::Other), MBB(mbb) {}
1191 public:
1192
1193   MachineBasicBlock *getBasicBlock() const { return MBB; }
1194
1195   static bool classof(const BasicBlockSDNode *) { return true; }
1196   static bool classof(const SDNode *N) {
1197     return N->getOpcode() == ISD::BasicBlock;
1198   }
1199 };
1200
1201 class SrcValueSDNode : public SDNode {
1202   const Value *V;
1203   int offset;
1204 protected:
1205   friend class SelectionDAG;
1206   SrcValueSDNode(const Value* v, int o)
1207     : SDNode(ISD::SRCVALUE, MVT::Other), V(v), offset(o) {}
1208
1209 public:
1210   const Value *getValue() const { return V; }
1211   int getOffset() const { return offset; }
1212
1213   static bool classof(const SrcValueSDNode *) { return true; }
1214   static bool classof(const SDNode *N) {
1215     return N->getOpcode() == ISD::SRCVALUE;
1216   }
1217 };
1218
1219
1220 class RegisterSDNode : public SDNode {
1221   unsigned Reg;
1222 protected:
1223   friend class SelectionDAG;
1224   RegisterSDNode(unsigned reg, MVT::ValueType VT)
1225     : SDNode(ISD::Register, VT), Reg(reg) {}
1226 public:
1227
1228   unsigned getReg() const { return Reg; }
1229
1230   static bool classof(const RegisterSDNode *) { return true; }
1231   static bool classof(const SDNode *N) {
1232     return N->getOpcode() == ISD::Register;
1233   }
1234 };
1235
1236 class ExternalSymbolSDNode : public SDNode {
1237   const char *Symbol;
1238 protected:
1239   friend class SelectionDAG;
1240   ExternalSymbolSDNode(bool isTarget, const char *Sym, MVT::ValueType VT)
1241     : SDNode(isTarget ? ISD::TargetExternalSymbol : ISD::ExternalSymbol, VT),
1242       Symbol(Sym) {
1243     }
1244 public:
1245
1246   const char *getSymbol() const { return Symbol; }
1247
1248   static bool classof(const ExternalSymbolSDNode *) { return true; }
1249   static bool classof(const SDNode *N) {
1250     return N->getOpcode() == ISD::ExternalSymbol ||
1251            N->getOpcode() == ISD::TargetExternalSymbol;
1252   }
1253 };
1254
1255 class CondCodeSDNode : public SDNode {
1256   ISD::CondCode Condition;
1257 protected:
1258   friend class SelectionDAG;
1259   CondCodeSDNode(ISD::CondCode Cond)
1260     : SDNode(ISD::CONDCODE, MVT::Other), Condition(Cond) {
1261   }
1262 public:
1263
1264   ISD::CondCode get() const { return Condition; }
1265
1266   static bool classof(const CondCodeSDNode *) { return true; }
1267   static bool classof(const SDNode *N) {
1268     return N->getOpcode() == ISD::CONDCODE;
1269   }
1270 };
1271
1272 /// VTSDNode - This class is used to represent MVT::ValueType's, which are used
1273 /// to parameterize some operations.
1274 class VTSDNode : public SDNode {
1275   MVT::ValueType ValueType;
1276 protected:
1277   friend class SelectionDAG;
1278   VTSDNode(MVT::ValueType VT)
1279     : SDNode(ISD::VALUETYPE, MVT::Other), ValueType(VT) {}
1280 public:
1281
1282   MVT::ValueType getVT() const { return ValueType; }
1283
1284   static bool classof(const VTSDNode *) { return true; }
1285   static bool classof(const SDNode *N) {
1286     return N->getOpcode() == ISD::VALUETYPE;
1287   }
1288 };
1289
1290
1291 class SDNodeIterator : public forward_iterator<SDNode, ptrdiff_t> {
1292   SDNode *Node;
1293   unsigned Operand;
1294
1295   SDNodeIterator(SDNode *N, unsigned Op) : Node(N), Operand(Op) {}
1296 public:
1297   bool operator==(const SDNodeIterator& x) const {
1298     return Operand == x.Operand;
1299   }
1300   bool operator!=(const SDNodeIterator& x) const { return !operator==(x); }
1301
1302   const SDNodeIterator &operator=(const SDNodeIterator &I) {
1303     assert(I.Node == Node && "Cannot assign iterators to two different nodes!");
1304     Operand = I.Operand;
1305     return *this;
1306   }
1307
1308   pointer operator*() const {
1309     return Node->getOperand(Operand).Val;
1310   }
1311   pointer operator->() const { return operator*(); }
1312
1313   SDNodeIterator& operator++() {                // Preincrement
1314     ++Operand;
1315     return *this;
1316   }
1317   SDNodeIterator operator++(int) { // Postincrement
1318     SDNodeIterator tmp = *this; ++*this; return tmp;
1319   }
1320
1321   static SDNodeIterator begin(SDNode *N) { return SDNodeIterator(N, 0); }
1322   static SDNodeIterator end  (SDNode *N) {
1323     return SDNodeIterator(N, N->getNumOperands());
1324   }
1325
1326   unsigned getOperand() const { return Operand; }
1327   const SDNode *getNode() const { return Node; }
1328 };
1329
1330 template <> struct GraphTraits<SDNode*> {
1331   typedef SDNode NodeType;
1332   typedef SDNodeIterator ChildIteratorType;
1333   static inline NodeType *getEntryNode(SDNode *N) { return N; }
1334   static inline ChildIteratorType child_begin(NodeType *N) {
1335     return SDNodeIterator::begin(N);
1336   }
1337   static inline ChildIteratorType child_end(NodeType *N) {
1338     return SDNodeIterator::end(N);
1339   }
1340 };
1341
1342 template<>
1343 struct ilist_traits<SDNode> {
1344   static SDNode *getPrev(const SDNode *N) { return N->Prev; }
1345   static SDNode *getNext(const SDNode *N) { return N->Next; }
1346
1347   static void setPrev(SDNode *N, SDNode *Prev) { N->Prev = Prev; }
1348   static void setNext(SDNode *N, SDNode *Next) { N->Next = Next; }
1349
1350   static SDNode *createSentinel() {
1351     return new SDNode(ISD::EntryToken, MVT::Other);
1352   }
1353   static void destroySentinel(SDNode *N) { delete N; }
1354   //static SDNode *createNode(const SDNode &V) { return new SDNode(V); }
1355
1356
1357   void addNodeToList(SDNode *NTy) {}
1358   void removeNodeFromList(SDNode *NTy) {}
1359   void transferNodesFromList(iplist<SDNode, ilist_traits> &L2,
1360                              const ilist_iterator<SDNode> &X,
1361                              const ilist_iterator<SDNode> &Y) {}
1362 };
1363
1364 } // end llvm namespace
1365
1366 #endif