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