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