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