include/llvm/CodeGen/SelectionDAGNodes.h

   1 //===-- llvm/CodeGen/SelectionDAGNodes.h - SelectionDAG Nodes ---*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // 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/Constants.h"
  24 #include "llvm/ADT/FoldingSet.h"
  25 #include "llvm/ADT/GraphTraits.h"
  26 #include "llvm/ADT/iterator.h"
  27 #include "llvm/ADT/ilist_node.h"
  28 #include "llvm/ADT/STLExtras.h"
  29 #include "llvm/CodeGen/ValueTypes.h"
  30 #include "llvm/CodeGen/MachineMemOperand.h"
  31 #include "llvm/Support/Allocator.h"
  32 #include "llvm/Support/RecyclingAllocator.h"
  33 #include "llvm/Support/DataTypes.h"
  34 #include <cassert>
  35
  36 namespace llvm {
  37
  38 class SelectionDAG;
  39 class GlobalValue;
  40 class MachineBasicBlock;
  41 class MachineConstantPoolValue;
  42 class SDNode;
  43 class CompileUnitDesc;
  44 template <typename T> struct DenseMapInfo;
  45 template <typename T> struct simplify_type;
  46 template <typename T> struct ilist_traits;
  47
  48 /// SDVTList - This represents a list of ValueType's that has been intern'd by
  49 /// a SelectionDAG.  Instances of this simple value class are returned by
  50 /// SelectionDAG::getVTList(...).
  51 ///
  52 struct SDVTList {
  53   const MVT *VTs;
  54   unsigned short NumVTs;
  55 };
  56
  57 /// ISD namespace - This namespace contains an enum which represents all of the
  58 /// SelectionDAG node types and value types.
  59 ///
  60 /// If you add new elements here you should increase OpActionsCapacity in
  61 /// TargetLowering.h by the number of new elements.
  62 namespace ISD {
  63
  64   //===--------------------------------------------------------------------===//
  65   /// ISD::NodeType enum - This enum defines all of the operators valid in a
  66   /// SelectionDAG.
  67   ///
  68   enum NodeType {
  69     // DELETED_NODE - This is an illegal flag value that is used to catch
  70     // errors.  This opcode is not a legal opcode for any node.
  71     DELETED_NODE,
  72
  73     // EntryToken - This is the marker used to indicate the start of the region.
  74     EntryToken,
  75
  76     // TokenFactor - This node takes multiple tokens as input and produces a
  77     // single token result.  This is used to represent the fact that the operand
  78     // operators are independent of each other.
  79     TokenFactor,
  80
  81     // AssertSext, AssertZext - These nodes record if a register contains a
  82     // value that has already been zero or sign extended from a narrower type.
  83     // These nodes take two operands.  The first is the node that has already
  84     // been extended, and the second is a value type node indicating the width
  85     // of the extension
  86     AssertSext, AssertZext,
  87
  88     // Various leaf nodes.
  89     BasicBlock, VALUETYPE, ARG_FLAGS, CONDCODE, Register,
  90     Constant, ConstantFP,
  91     GlobalAddress, GlobalTLSAddress, FrameIndex,
  92     JumpTable, ConstantPool, ExternalSymbol,
  93
  94     // The address of the GOT
  95     GLOBAL_OFFSET_TABLE,
  96
  97     // FRAMEADDR, RETURNADDR - These nodes represent llvm.frameaddress and
  98     // llvm.returnaddress on the DAG.  These nodes take one operand, the index
  99     // of the frame or return address to return.  An index of zero corresponds
 100     // to the current function's frame or return address, an index of one to the
 101     // parent's frame or return address, and so on.
 102     FRAMEADDR, RETURNADDR,
 103
 104     // FRAME_TO_ARGS_OFFSET - This node represents offset from frame pointer to
 105     // first (possible) on-stack argument. This is needed for correct stack
 106     // adjustment during unwind.
 107     FRAME_TO_ARGS_OFFSET,
 108
 109     // RESULT, OUTCHAIN = EXCEPTIONADDR(INCHAIN) - This node represents the
 110     // address of the exception block on entry to an landing pad block.
 111     EXCEPTIONADDR,
 112
 113     // RESULT, OUTCHAIN = EHSELECTION(INCHAIN, EXCEPTION) - This node represents
 114     // the selection index of the exception thrown.
 115     EHSELECTION,
 116
 117     // OUTCHAIN = EH_RETURN(INCHAIN, OFFSET, HANDLER) - This node represents
 118     // 'eh_return' gcc dwarf builtin, which is used to return from
 119     // exception. The general meaning is: adjust stack by OFFSET and pass
 120     // execution to HANDLER. Many platform-related details also :)
 121     EH_RETURN,
 122
 123     // TargetConstant* - Like Constant*, but the DAG does not do any folding or
 124     // simplification of the constant.
 125     TargetConstant,
 126     TargetConstantFP,
 127
 128     // TargetGlobalAddress - Like GlobalAddress, but the DAG does no folding or
 129     // anything else with this node, and this is valid in the target-specific
 130     // dag, turning into a GlobalAddress operand.
 131     TargetGlobalAddress,
 132     TargetGlobalTLSAddress,
 133     TargetFrameIndex,
 134     TargetJumpTable,
 135     TargetConstantPool,
 136     TargetExternalSymbol,
 137
 138     /// RESULT = INTRINSIC_WO_CHAIN(INTRINSICID, arg1, arg2, ...)
 139     /// This node represents a target intrinsic function with no side effects.
 140     /// The first operand is the ID number of the intrinsic from the
 141     /// llvm::Intrinsic namespace.  The operands to the intrinsic follow.  The
 142     /// node has returns the result of the intrinsic.
 143     INTRINSIC_WO_CHAIN,
 144
 145     /// RESULT,OUTCHAIN = INTRINSIC_W_CHAIN(INCHAIN, INTRINSICID, arg1, ...)
 146     /// This node represents a target intrinsic function with side effects that
 147     /// returns a result.  The first operand is a chain pointer.  The second is
 148     /// the ID number of the intrinsic from the llvm::Intrinsic namespace.  The
 149     /// operands to the intrinsic follow.  The node has two results, the result
 150     /// of the intrinsic and an output chain.
 151     INTRINSIC_W_CHAIN,
 152
 153     /// OUTCHAIN = INTRINSIC_VOID(INCHAIN, INTRINSICID, arg1, arg2, ...)
 154     /// This node represents a target intrinsic function with side effects that
 155     /// does not return a result.  The first operand is a chain pointer.  The
 156     /// second is the ID number of the intrinsic from the llvm::Intrinsic
 157     /// namespace.  The operands to the intrinsic follow.
 158     INTRINSIC_VOID,
 159
 160     // CopyToReg - This node has three operands: a chain, a register number to
 161     // set to this value, and a value.
 162     CopyToReg,
 163
 164     // CopyFromReg - This node indicates that the input value is a virtual or
 165     // physical register that is defined outside of the scope of this
 166     // SelectionDAG.  The register is available from the RegisterSDNode object.
 167     CopyFromReg,
 168
 169     // UNDEF - An undefined node
 170     UNDEF,
 171
 172     /// FORMAL_ARGUMENTS(CHAIN, CC#, ISVARARG, FLAG0, ..., FLAGn) - This node
 173     /// represents the formal arguments for a function.  CC# is a Constant value
 174     /// indicating the calling convention of the function, and ISVARARG is a
 175     /// flag that indicates whether the function is varargs or not. This node
 176     /// has one result value for each incoming argument, plus one for the output
 177     /// chain. It must be custom legalized. See description of CALL node for
 178     /// FLAG argument contents explanation.
 179     ///
 180     FORMAL_ARGUMENTS,
 181
 182     /// RV1, RV2...RVn, CHAIN = CALL(CHAIN, CALLEE,
 183     ///                              ARG0, FLAG0, ARG1, FLAG1, ... ARGn, FLAGn)
 184     /// This node represents a fully general function call, before the legalizer
 185     /// runs.  This has one result value for each argument / flag pair, plus
 186     /// a chain result. It must be custom legalized. Flag argument indicates
 187     /// misc. argument attributes. Currently:
 188     /// Bit 0 - signness
 189     /// Bit 1 - 'inreg' attribute
 190     /// Bit 2 - 'sret' attribute
 191     /// Bit 4 - 'byval' attribute
 192     /// Bit 5 - 'nest' attribute
 193     /// Bit 6-9 - alignment of byval structures
 194     /// Bit 10-26 - size of byval structures
 195     /// Bits 31:27 - argument ABI alignment in the first argument piece and
 196     /// alignment '1' in other argument pieces.
 197     ///
 198     /// CALL nodes use the CallSDNode subclass of SDNode, which
 199     /// additionally carries information about the calling convention,
 200     /// whether the call is varargs, and if it's marked as a tail call.
 201     ///
 202     CALL,
 203
 204     // EXTRACT_ELEMENT - This is used to get the lower or upper (determined by
 205     // a Constant, which is required to be operand #1) half of the integer or
 206     // float value specified as operand #0.  This is only for use before
 207     // legalization, for values that will be broken into multiple registers.
 208     EXTRACT_ELEMENT,
 209
 210     // BUILD_PAIR - This is the opposite of EXTRACT_ELEMENT in some ways.  Given
 211     // two values of the same integer value type, this produces a value twice as
 212     // big.  Like EXTRACT_ELEMENT, this can only be used before legalization.
 213     BUILD_PAIR,
 214
 215     // MERGE_VALUES - This node takes multiple discrete operands and returns
 216     // them all as its individual results.  This nodes has exactly the same
 217     // number of inputs and outputs, and is only valid before legalization.
 218     // This node is useful for some pieces of the code generator that want to
 219     // think about a single node with multiple results, not multiple nodes.
 220     MERGE_VALUES,
 221
 222     // Simple integer binary arithmetic operators.
 223     ADD, SUB, MUL, SDIV, UDIV, SREM, UREM,
 224
 225     // SMUL_LOHI/UMUL_LOHI - Multiply two integers of type iN, producing
 226     // a signed/unsigned value of type i[2*N], and return the full value as
 227     // two results, each of type iN.
 228     SMUL_LOHI, UMUL_LOHI,
 229
 230     // SDIVREM/UDIVREM - Divide two integers and produce both a quotient and
 231     // remainder result.
 232     SDIVREM, UDIVREM,
 233
 234     // CARRY_FALSE - This node is used when folding other nodes,
 235     // like ADDC/SUBC, which indicate the carry result is always false.
 236     CARRY_FALSE,
 237
 238     // Carry-setting nodes for multiple precision addition and subtraction.
 239     // These nodes take two operands of the same value type, and produce two
 240     // results.  The first result is the normal add or sub result, the second
 241     // result is the carry flag result.
 242     ADDC, SUBC,
 243
 244     // Carry-using nodes for multiple precision addition and subtraction.  These
 245     // nodes take three operands: The first two are the normal lhs and rhs to
 246     // the add or sub, and the third is the input carry flag.  These nodes
 247     // produce two results; the normal result of the add or sub, and the output
 248     // carry flag.  These nodes both read and write a carry flag to allow them
 249     // to them to be chained together for add and sub of arbitrarily large
 250     // values.
 251     ADDE, SUBE,
 252
 253     // Simple binary floating point operators.
 254     FADD, FSUB, FMUL, FDIV, FREM,
 255
 256     // FCOPYSIGN(X, Y) - Return the value of X with the sign of Y.  NOTE: This
 257     // DAG node does not require that X and Y have the same type, just that they
 258     // are both floating point.  X and the result must have the same type.
 259     // FCOPYSIGN(f32, f64) is allowed.
 260     FCOPYSIGN,
 261
 262     // INT = FGETSIGN(FP) - Return the sign bit of the specified floating point
 263     // value as an integer 0/1 value.
 264     FGETSIGN,
 265
 266     /// BUILD_VECTOR(ELT0, ELT1, ELT2, ELT3,...) - Return a vector
 267     /// with the specified, possibly variable, elements.  The number of elements
 268     /// is required to be a power of two.
 269     BUILD_VECTOR,
 270
 271     /// INSERT_VECTOR_ELT(VECTOR, VAL, IDX) - Returns VECTOR with the element
 272     /// at IDX replaced with VAL.  If the type of VAL is larger than the vector
 273     /// element type then VAL is truncated before replacement.
 274     INSERT_VECTOR_ELT,
 275
 276     /// EXTRACT_VECTOR_ELT(VECTOR, IDX) - Returns a single element from VECTOR
 277     /// identified by the (potentially variable) element number IDX.
 278     EXTRACT_VECTOR_ELT,
 279
 280     /// CONCAT_VECTORS(VECTOR0, VECTOR1, ...) - Given a number of values of
 281     /// vector type with the same length and element type, this produces a
 282     /// concatenated vector result value, with length equal to the sum of the
 283     /// lengths of the input vectors.
 284     CONCAT_VECTORS,
 285
 286     /// EXTRACT_SUBVECTOR(VECTOR, IDX) - Returns a subvector from VECTOR (an
 287     /// vector value) starting with the (potentially variable) element number
 288     /// IDX, which must be a multiple of the result vector length.
 289     EXTRACT_SUBVECTOR,
 290
 291     /// VECTOR_SHUFFLE(VEC1, VEC2, SHUFFLEVEC) - Returns a vector, of the same
 292     /// type as VEC1/VEC2.  SHUFFLEVEC is a BUILD_VECTOR of constant int values
 293     /// (maybe of an illegal datatype) or undef that indicate which value each
 294     /// result element will get.  The elements of VEC1/VEC2 are enumerated in
 295     /// order.  This is quite similar to the Altivec 'vperm' instruction, except
 296     /// that the indices must be constants and are in terms of the element size
 297     /// of VEC1/VEC2, not in terms of bytes.
 298     VECTOR_SHUFFLE,
 299
 300     /// SCALAR_TO_VECTOR(VAL) - This represents the operation of loading a
 301     /// scalar value into element 0 of the resultant vector type.  The top
 302     /// elements 1 to N-1 of the N-element vector are undefined.
 303     SCALAR_TO_VECTOR,
 304
 305     // EXTRACT_SUBREG - This node is used to extract a sub-register value.
 306     // This node takes a superreg and a constant sub-register index as operands.
 307     // Note sub-register indices must be increasing. That is, if the
 308     // sub-register index of a 8-bit sub-register is N, then the index for a
 309     // 16-bit sub-register must be at least N+1.
 310     EXTRACT_SUBREG,
 311
 312     // INSERT_SUBREG - This node is used to insert a sub-register value.
 313     // This node takes a superreg, a subreg value, and a constant sub-register
 314     // index as operands.
 315     INSERT_SUBREG,
 316
 317     // MULHU/MULHS - Multiply high - Multiply two integers of type iN, producing
 318     // an unsigned/signed value of type i[2*N], then return the top part.
 319     MULHU, MULHS,
 320
 321     // Bitwise operators - logical and, logical or, logical xor, shift left,
 322     // shift right algebraic (shift in sign bits), shift right logical (shift in
 323     // zeroes), rotate left, rotate right, and byteswap.
 324     AND, OR, XOR, SHL, SRA, SRL, ROTL, ROTR, BSWAP,
 325
 326     // Counting operators
 327     CTTZ, CTLZ, CTPOP,
 328
 329     // Select(COND, TRUEVAL, FALSEVAL).  If the type of the boolean COND is not
 330     // i1 then the high bits must conform to getSetCCResultContents.
 331     SELECT,
 332
 333     // Select with condition operator - This selects between a true value and
 334     // a false value (ops #2 and #3) based on the boolean result of comparing
 335     // the lhs and rhs (ops #0 and #1) of a conditional expression with the
 336     // condition code in op #4, a CondCodeSDNode.
 337     SELECT_CC,
 338
 339     // SetCC operator - This evaluates to a true value iff the condition is
 340     // true.  If the result value type is not i1 then the high bits conform
 341     // to getSetCCResultContents.  The operands to this are the left and right
 342     // operands to compare (ops #0, and #1) and the condition code to compare
 343     // them with (op #2) as a CondCodeSDNode.
 344     SETCC,
 345
 346     // Vector SetCC operator - This evaluates to a vector of integer elements
 347     // with the high bit in each element set to true if the comparison is true
 348     // and false if the comparison is false.  All other bits in each element
 349     // are undefined.  The operands to this are the left and right operands
 350     // to compare (ops #0, and #1) and the condition code to compare them with
 351     // (op #2) as a CondCodeSDNode.
 352     VSETCC,
 353
 354     // SHL_PARTS/SRA_PARTS/SRL_PARTS - These operators are used for expanded
 355     // integer shift operations, just like ADD/SUB_PARTS.  The operation
 356     // ordering is:
 357     //       [Lo,Hi] = op [LoLHS,HiLHS], Amt
 358     SHL_PARTS, SRA_PARTS, SRL_PARTS,
 359
 360     // Conversion operators.  These are all single input single output
 361     // operations.  For all of these, the result type must be strictly
 362     // wider or narrower (depending on the operation) than the source
 363     // type.
 364
 365     // SIGN_EXTEND - Used for integer types, replicating the sign bit
 366     // into new bits.
 367     SIGN_EXTEND,
 368
 369     // ZERO_EXTEND - Used for integer types, zeroing the new bits.
 370     ZERO_EXTEND,
 371
 372     // ANY_EXTEND - Used for integer types.  The high bits are undefined.
 373     ANY_EXTEND,
 374
 375     // TRUNCATE - Completely drop the high bits.
 376     TRUNCATE,
 377
 378     // [SU]INT_TO_FP - These operators convert integers (whose interpreted sign
 379     // depends on the first letter) to floating point.
 380     SINT_TO_FP,
 381     UINT_TO_FP,
 382
 383     // SIGN_EXTEND_INREG - This operator atomically performs a SHL/SRA pair to
 384     // sign extend a small value in a large integer register (e.g. sign
 385     // extending the low 8 bits of a 32-bit register to fill the top 24 bits
 386     // with the 7th bit).  The size of the smaller type is indicated by the 1th
 387     // operand, a ValueType node.
 388     SIGN_EXTEND_INREG,
 389
 390     /// FP_TO_[US]INT - Convert a floating point value to a signed or unsigned
 391     /// integer.
 392     FP_TO_SINT,
 393     FP_TO_UINT,
 394
 395     /// X = FP_ROUND(Y, TRUNC) - Rounding 'Y' from a larger floating point type
 396     /// down to the precision of the destination VT.  TRUNC is a flag, which is
 397     /// always an integer that is zero or one.  If TRUNC is 0, this is a
 398     /// normal rounding, if it is 1, this FP_ROUND is known to not change the
 399     /// value of Y.
 400     ///
 401     /// The TRUNC = 1 case is used in cases where we know that the value will
 402     /// not be modified by the node, because Y is not using any of the extra
 403     /// precision of source type.  This allows certain transformations like
 404     /// FP_EXTEND(FP_ROUND(X,1)) -> X which are not safe for
 405     /// FP_EXTEND(FP_ROUND(X,0)) because the extra bits aren't removed.
 406     FP_ROUND,
 407
 408     // FLT_ROUNDS_ - Returns current rounding mode:
 409     // -1 Undefined
 410     //  0 Round to 0
 411     //  1 Round to nearest
 412     //  2 Round to +inf
 413     //  3 Round to -inf
 414     FLT_ROUNDS_,
 415
 416     /// X = FP_ROUND_INREG(Y, VT) - This operator takes an FP register, and
 417     /// rounds it to a floating point value.  It then promotes it and returns it
 418     /// in a register of the same size.  This operation effectively just
 419     /// discards excess precision.  The type to round down to is specified by
 420     /// the VT operand, a VTSDNode.
 421     FP_ROUND_INREG,
 422
 423     /// X = FP_EXTEND(Y) - Extend a smaller FP type into a larger FP type.
 424     FP_EXTEND,
 425
 426     // BIT_CONVERT - Theis operator converts between integer and FP values, as
 427     // if one was stored to memory as integer and the other was loaded from the
 428     // same address (or equivalently for vector format conversions, etc).  The
 429     // source and result are required to have the same bit size (e.g.
 430     // f32 <-> i32).  This can also be used for int-to-int or fp-to-fp
 431     // conversions, but that is a noop, deleted by getNode().
 432     BIT_CONVERT,
 433
 434     // CONVERT_RNDSAT - This operator is used to support various conversions
 435     // between various types (float, signed, unsigned and vectors of those
 436     // types) with rounding and saturation. NOTE: Avoid using this operator as
 437     // most target don't support it and the operator might be removed in the
 438     // future. It takes the following arguments:
 439     //   0) value
 440     //   1) dest type (type to convert to)
 441     //   2) src type (type to convert from)
 442     //   3) rounding imm
 443     //   4) saturation imm
 444     //   5) ISD::CvtCode indicating the type of conversion to do
 445     CONVERT_RNDSAT,
 446
 447     // FNEG, FABS, FSQRT, FSIN, FCOS, FPOWI, FPOW,
 448     // FLOG, FLOG2, FLOG10, FEXP, FEXP2,
 449     // FCEIL, FTRUNC, FRINT, FNEARBYINT, FFLOOR - Perform various unary floating
 450     // point operations. These are inspired by libm.
 451     FNEG, FABS, FSQRT, FSIN, FCOS, FPOWI, FPOW,
 452     FLOG, FLOG2, FLOG10, FEXP, FEXP2,
 453     FCEIL, FTRUNC, FRINT, FNEARBYINT, FFLOOR,
 454
 455     // LOAD and STORE have token chains as their first operand, then the same
 456     // operands as an LLVM load/store instruction, then an offset node that
 457     // is added / subtracted from the base pointer to form the address (for
 458     // indexed memory ops).
 459     LOAD, STORE,
 460
 461     // DYNAMIC_STACKALLOC - Allocate some number of bytes on the stack aligned
 462     // to a specified boundary.  This node always has two return values: a new
 463     // stack pointer value and a chain. The first operand is the token chain,
 464     // the second is the number of bytes to allocate, and the third is the
 465     // alignment boundary.  The size is guaranteed to be a multiple of the stack
 466     // alignment, and the alignment is guaranteed to be bigger than the stack
 467     // alignment (if required) or 0 to get standard stack alignment.
 468     DYNAMIC_STACKALLOC,
 469
 470     // Control flow instructions.  These all have token chains.
 471
 472     // BR - Unconditional branch.  The first operand is the chain
 473     // operand, the second is the MBB to branch to.
 474     BR,
 475
 476     // BRIND - Indirect branch.  The first operand is the chain, the second
 477     // is the value to branch to, which must be of the same type as the target's
 478     // pointer type.
 479     BRIND,
 480
 481     // BR_JT - Jumptable branch. The first operand is the chain, the second
 482     // is the jumptable index, the last one is the jumptable entry index.
 483     BR_JT,
 484
 485     // BRCOND - Conditional branch.  The first operand is the chain, the
 486     // second is the condition, the third is the block to branch to if the
 487     // condition is true.  If the type of the condition is not i1, then the
 488     // high bits must conform to getSetCCResultContents.
 489     BRCOND,
 490
 491     // BR_CC - Conditional branch.  The behavior is like that of SELECT_CC, in
 492     // that the condition is represented as condition code, and two nodes to
 493     // compare, rather than as a combined SetCC node.  The operands in order are
 494     // chain, cc, lhs, rhs, block to branch to if condition is true.
 495     BR_CC,
 496
 497     // RET - Return from function.  The first operand is the chain,
 498     // and any subsequent operands are pairs of return value and return value
 499     // attributes (see CALL for description of attributes) for the function.
 500     // This operation can have variable number of operands.
 501     RET,
 502
 503     // INLINEASM - Represents an inline asm block.  This node always has two
 504     // return values: a chain and a flag result.  The inputs are as follows:
 505     //   Operand #0   : Input chain.
 506     //   Operand #1   : a ExternalSymbolSDNode with a pointer to the asm string.
 507     //   Operand #2n+2: A RegisterNode.
 508     //   Operand #2n+3: A TargetConstant, indicating if the reg is a use/def
 509     //   Operand #last: Optional, an incoming flag.
 510     INLINEASM,
 511
 512     // DBG_LABEL, EH_LABEL - Represents a label in mid basic block used to track
 513     // locations needed for debug and exception handling tables.  These nodes
 514     // take a chain as input and return a chain.
 515     DBG_LABEL,
 516     EH_LABEL,
 517
 518     // DECLARE - Represents a llvm.dbg.declare intrinsic. It's used to track
 519     // local variable declarations for debugging information. First operand is
 520     // a chain, while the next two operands are first two arguments (address
 521     // and variable) of a llvm.dbg.declare instruction.
 522     DECLARE,
 523
 524     // STACKSAVE - STACKSAVE has one operand, an input chain.  It produces a
 525     // value, the same type as the pointer type for the system, and an output
 526     // chain.
 527     STACKSAVE,
 528
 529     // STACKRESTORE has two operands, an input chain and a pointer to restore to
 530     // it returns an output chain.
 531     STACKRESTORE,
 532
 533     // CALLSEQ_START/CALLSEQ_END - These operators mark the beginning and end of
 534     // a call sequence, and carry arbitrary information that target might want
 535     // to know.  The first operand is a chain, the rest are specified by the
 536     // target and not touched by the DAG optimizers.
 537     // CALLSEQ_START..CALLSEQ_END pairs may not be nested.
 538     CALLSEQ_START,  // Beginning of a call sequence
 539     CALLSEQ_END,    // End of a call sequence
 540
 541     // VAARG - VAARG has three operands: an input chain, a pointer, and a
 542     // SRCVALUE.  It returns a pair of values: the vaarg value and a new chain.
 543     VAARG,
 544
 545     // VACOPY - VACOPY has five operands: an input chain, a destination pointer,
 546     // a source pointer, a SRCVALUE for the destination, and a SRCVALUE for the
 547     // source.
 548     VACOPY,
 549
 550     // VAEND, VASTART - VAEND and VASTART have three operands: an input chain, a
 551     // pointer, and a SRCVALUE.
 552     VAEND, VASTART,
 553
 554     // SRCVALUE - This is a node type that holds a Value* that is used to
 555     // make reference to a value in the LLVM IR.
 556     SRCVALUE,
 557
 558     // MEMOPERAND - This is a node that contains a MachineMemOperand which
 559     // records information about a memory reference. This is used to make
 560     // AliasAnalysis queries from the backend.
 561     MEMOPERAND,
 562
 563     // PCMARKER - This corresponds to the pcmarker intrinsic.
 564     PCMARKER,
 565
 566     // READCYCLECOUNTER - This corresponds to the readcyclecounter intrinsic.
 567     // The only operand is a chain and a value and a chain are produced.  The
 568     // value is the contents of the architecture specific cycle counter like
 569     // register (or other high accuracy low latency clock source)
 570     READCYCLECOUNTER,
 571
 572     // HANDLENODE node - Used as a handle for various purposes.
 573     HANDLENODE,
 574
 575     // DBG_STOPPOINT - This node is used to represent a source location for
 576     // debug info.  It takes token chain as input, and carries a line number,
 577     // column number, and a pointer to a CompileUnitDesc object identifying
 578     // the containing compilation unit.  It produces a token chain as output.
 579     DBG_STOPPOINT,
 580
 581     // DEBUG_LOC - This node is used to represent source line information
 582     // embedded in the code.  It takes a token chain as input, then a line
 583     // number, then a column then a file id (provided by MachineModuleInfo.) It
 584     // produces a token chain as output.
 585     DEBUG_LOC,
 586
 587     // TRAMPOLINE - This corresponds to the init_trampoline intrinsic.
 588     // It takes as input a token chain, the pointer to the trampoline,
 589     // the pointer to the nested function, the pointer to pass for the
 590     // 'nest' parameter, a SRCVALUE for the trampoline and another for
 591     // the nested function (allowing targets to access the original
 592     // Function*).  It produces the result of the intrinsic and a token
 593     // chain as output.
 594     TRAMPOLINE,
 595
 596     // TRAP - Trapping instruction
 597     TRAP,
 598
 599     // PREFETCH - This corresponds to a prefetch intrinsic. It takes chains are
 600     // their first operand. The other operands are the address to prefetch,
 601     // read / write specifier, and locality specifier.
 602     PREFETCH,
 603
 604     // OUTCHAIN = MEMBARRIER(INCHAIN, load-load, load-store, store-load,
 605     //                       store-store, device)
 606     // This corresponds to the memory.barrier intrinsic.
 607     // it takes an input chain, 4 operands to specify the type of barrier, an
 608     // operand specifying if the barrier applies to device and uncached memory
 609     // and produces an output chain.
 610     MEMBARRIER,
 611
 612     // Val, OUTCHAIN = ATOMIC_CMP_SWAP(INCHAIN, ptr, cmp, swap)
 613     // this corresponds to the atomic.lcs intrinsic.
 614     // cmp is compared to *ptr, and if equal, swap is stored in *ptr.
 615     // the return is always the original value in *ptr
 616     ATOMIC_CMP_SWAP_8,
 617     ATOMIC_CMP_SWAP_16,
 618     ATOMIC_CMP_SWAP_32,
 619     ATOMIC_CMP_SWAP_64,
 620
 621     // Val, OUTCHAIN = ATOMIC_SWAP(INCHAIN, ptr, amt)
 622     // this corresponds to the atomic.swap intrinsic.
 623     // amt is stored to *ptr atomically.
 624     // the return is always the original value in *ptr
 625     ATOMIC_SWAP_8,
 626     ATOMIC_SWAP_16,
 627     ATOMIC_SWAP_32,
 628     ATOMIC_SWAP_64,
 629
 630     // Val, OUTCHAIN = ATOMIC_L[OpName]S(INCHAIN, ptr, amt)
 631     // this corresponds to the atomic.[OpName] intrinsic.
 632     // op(*ptr, amt) is stored to *ptr atomically.
 633     // the return is always the original value in *ptr
 634     ATOMIC_LOAD_ADD_8,
 635     ATOMIC_LOAD_SUB_8,
 636     ATOMIC_LOAD_AND_8,
 637     ATOMIC_LOAD_OR_8,
 638     ATOMIC_LOAD_XOR_8,
 639     ATOMIC_LOAD_NAND_8,
 640     ATOMIC_LOAD_MIN_8,
 641     ATOMIC_LOAD_MAX_8,
 642     ATOMIC_LOAD_UMIN_8,
 643     ATOMIC_LOAD_UMAX_8,
 644     ATOMIC_LOAD_ADD_16,
 645     ATOMIC_LOAD_SUB_16,
 646     ATOMIC_LOAD_AND_16,
 647     ATOMIC_LOAD_OR_16,
 648     ATOMIC_LOAD_XOR_16,
 649     ATOMIC_LOAD_NAND_16,
 650     ATOMIC_LOAD_MIN_16,
 651     ATOMIC_LOAD_MAX_16,
 652     ATOMIC_LOAD_UMIN_16,
 653     ATOMIC_LOAD_UMAX_16,
 654     ATOMIC_LOAD_ADD_32,
 655     ATOMIC_LOAD_SUB_32,
 656     ATOMIC_LOAD_AND_32,
 657     ATOMIC_LOAD_OR_32,
 658     ATOMIC_LOAD_XOR_32,
 659     ATOMIC_LOAD_NAND_32,
 660     ATOMIC_LOAD_MIN_32,
 661     ATOMIC_LOAD_MAX_32,
 662     ATOMIC_LOAD_UMIN_32,
 663     ATOMIC_LOAD_UMAX_32,
 664     ATOMIC_LOAD_ADD_64,
 665     ATOMIC_LOAD_SUB_64,
 666     ATOMIC_LOAD_AND_64,
 667     ATOMIC_LOAD_OR_64,
 668     ATOMIC_LOAD_XOR_64,
 669     ATOMIC_LOAD_NAND_64,
 670     ATOMIC_LOAD_MIN_64,
 671     ATOMIC_LOAD_MAX_64,
 672     ATOMIC_LOAD_UMIN_64,
 673     ATOMIC_LOAD_UMAX_64,
 674
 675     // BUILTIN_OP_END - This must be the last enum value in this list.
 676     BUILTIN_OP_END
 677   };
 678
 679   /// Node predicates
 680
 681   /// isBuildVectorAllOnes - Return true if the specified node is a
 682   /// BUILD_VECTOR where all of the elements are ~0 or undef.
 683   bool isBuildVectorAllOnes(const SDNode *N);
 684
 685   /// isBuildVectorAllZeros - Return true if the specified node is a
 686   /// BUILD_VECTOR where all of the elements are 0 or undef.
 687   bool isBuildVectorAllZeros(const SDNode *N);
 688
 689   /// isScalarToVector - Return true if the specified node is a
 690   /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
 691   /// element is not an undef.
 692   bool isScalarToVector(const SDNode *N);
 693
 694   /// isDebugLabel - Return true if the specified node represents a debug
 695   /// label (i.e. ISD::DBG_LABEL or TargetInstrInfo::DBG_LABEL node).
 696   bool isDebugLabel(const SDNode *N);
 697
 698   //===--------------------------------------------------------------------===//
 699   /// MemIndexedMode enum - This enum defines the load / store indexed
 700   /// addressing modes.
 701   ///
 702   /// UNINDEXED    "Normal" load / store. The effective address is already
 703   ///              computed and is available in the base pointer. The offset
 704   ///              operand is always undefined. In addition to producing a
 705   ///              chain, an unindexed load produces one value (result of the
 706   ///              load); an unindexed store does not produce a value.
 707   ///
 708   /// PRE_INC      Similar to the unindexed mode where the effective address is
 709   /// PRE_DEC      the value of the base pointer add / subtract the offset.
 710   ///              It considers the computation as being folded into the load /
 711   ///              store operation (i.e. the load / store does the address
 712   ///              computation as well as performing the memory transaction).
 713   ///              The base operand is always undefined. In addition to
 714   ///              producing a chain, pre-indexed load produces two values
 715   ///              (result of the load and the result of the address
 716   ///              computation); a pre-indexed store produces one value (result
 717   ///              of the address computation).
 718   ///
 719   /// POST_INC     The effective address is the value of the base pointer. The
 720   /// POST_DEC     value of the offset operand is then added to / subtracted
 721   ///              from the base after memory transaction. In addition to
 722   ///              producing a chain, post-indexed load produces two values
 723   ///              (the result of the load and the result of the base +/- offset
 724   ///              computation); a post-indexed store produces one value (the
 725   ///              the result of the base +/- offset computation).
 726   ///
 727   enum MemIndexedMode {
 728     UNINDEXED = 0,
 729     PRE_INC,
 730     PRE_DEC,
 731     POST_INC,
 732     POST_DEC,
 733     LAST_INDEXED_MODE
 734   };
 735
 736   //===--------------------------------------------------------------------===//
 737   /// LoadExtType enum - This enum defines the three variants of LOADEXT
 738   /// (load with extension).
 739   ///
 740   /// SEXTLOAD loads the integer operand and sign extends it to a larger
 741   ///          integer result type.
 742   /// ZEXTLOAD loads the integer operand and zero extends it to a larger
 743   ///          integer result type.
 744   /// EXTLOAD  is used for three things: floating point extending loads,
 745   ///          integer extending loads [the top bits are undefined], and vector
 746   ///          extending loads [load into low elt].
 747   ///
 748   enum LoadExtType {
 749     NON_EXTLOAD = 0,
 750     EXTLOAD,
 751     SEXTLOAD,
 752     ZEXTLOAD,
 753     LAST_LOADEXT_TYPE
 754   };
 755
 756   //===--------------------------------------------------------------------===//
 757   /// ISD::CondCode enum - These are ordered carefully to make the bitfields
 758   /// below work out, when considering SETFALSE (something that never exists
 759   /// dynamically) as 0.  "U" -> Unsigned (for integer operands) or Unordered
 760   /// (for floating point), "L" -> Less than, "G" -> Greater than, "E" -> Equal
 761   /// to.  If the "N" column is 1, the result of the comparison is undefined if
 762   /// the input is a NAN.
 763   ///
 764   /// All of these (except for the 'always folded ops') should be handled for
 765   /// floating point.  For integer, only the SETEQ,SETNE,SETLT,SETLE,SETGT,
 766   /// SETGE,SETULT,SETULE,SETUGT, and SETUGE opcodes are used.
 767   ///
 768   /// Note that these are laid out in a specific order to allow bit-twiddling
 769   /// to transform conditions.
 770   enum CondCode {
 771     // Opcode          N U L G E       Intuitive operation
 772     SETFALSE,      //    0 0 0 0       Always false (always folded)
 773     SETOEQ,        //    0 0 0 1       True if ordered and equal
 774     SETOGT,        //    0 0 1 0       True if ordered and greater than
 775     SETOGE,        //    0 0 1 1       True if ordered and greater than or equal
 776     SETOLT,        //    0 1 0 0       True if ordered and less than
 777     SETOLE,        //    0 1 0 1       True if ordered and less than or equal
 778     SETONE,        //    0 1 1 0       True if ordered and operands are unequal
 779     SETO,          //    0 1 1 1       True if ordered (no nans)
 780     SETUO,         //    1 0 0 0       True if unordered: isnan(X) | isnan(Y)
 781     SETUEQ,        //    1 0 0 1       True if unordered or equal
 782     SETUGT,        //    1 0 1 0       True if unordered or greater than
 783     SETUGE,        //    1 0 1 1       True if unordered, greater than, or equal
 784     SETULT,        //    1 1 0 0       True if unordered or less than
 785     SETULE,        //    1 1 0 1       True if unordered, less than, or equal
 786     SETUNE,        //    1 1 1 0       True if unordered or not equal
 787     SETTRUE,       //    1 1 1 1       Always true (always folded)
 788     // Don't care operations: undefined if the input is a nan.
 789     SETFALSE2,     //  1 X 0 0 0       Always false (always folded)
 790     SETEQ,         //  1 X 0 0 1       True if equal
 791     SETGT,         //  1 X 0 1 0       True if greater than
 792     SETGE,         //  1 X 0 1 1       True if greater than or equal
 793     SETLT,         //  1 X 1 0 0       True if less than
 794     SETLE,         //  1 X 1 0 1       True if less than or equal
 795     SETNE,         //  1 X 1 1 0       True if not equal
 796     SETTRUE2,      //  1 X 1 1 1       Always true (always folded)
 797
 798     SETCC_INVALID       // Marker value.
 799   };
 800
 801   /// isSignedIntSetCC - Return true if this is a setcc instruction that
 802   /// performs a signed comparison when used with integer operands.
 803   inline bool isSignedIntSetCC(CondCode Code) {
 804     return Code == SETGT || Code == SETGE || Code == SETLT || Code == SETLE;
 805   }
 806
 807   /// isUnsignedIntSetCC - Return true if this is a setcc instruction that
 808   /// performs an unsigned comparison when used with integer operands.
 809   inline bool isUnsignedIntSetCC(CondCode Code) {
 810     return Code == SETUGT || Code == SETUGE || Code == SETULT || Code == SETULE;
 811   }
 812
 813   /// isTrueWhenEqual - Return true if the specified condition returns true if
 814   /// the two operands to the condition are equal.  Note that if one of the two
 815   /// operands is a NaN, this value is meaningless.
 816   inline bool isTrueWhenEqual(CondCode Cond) {
 817     return ((int)Cond & 1) != 0;
 818   }
 819
 820   /// getUnorderedFlavor - This function returns 0 if the condition is always
 821   /// false if an operand is a NaN, 1 if the condition is always true if the
 822   /// operand is a NaN, and 2 if the condition is undefined if the operand is a
 823   /// NaN.
 824   inline unsigned getUnorderedFlavor(CondCode Cond) {
 825     return ((int)Cond >> 3) & 3;
 826   }
 827
 828   /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
 829   /// 'op' is a valid SetCC operation.
 830   CondCode getSetCCInverse(CondCode Operation, bool isInteger);
 831
 832   /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
 833   /// when given the operation for (X op Y).
 834   CondCode getSetCCSwappedOperands(CondCode Operation);
 835
 836   /// getSetCCOrOperation - Return the result of a logical OR between different
 837   /// comparisons of identical values: ((X op1 Y) | (X op2 Y)).  This
 838   /// function returns SETCC_INVALID if it is not possible to represent the
 839   /// resultant comparison.
 840   CondCode getSetCCOrOperation(CondCode Op1, CondCode Op2, bool isInteger);
 841
 842   /// getSetCCAndOperation - Return the result of a logical AND between
 843   /// different comparisons of identical values: ((X op1 Y) & (X op2 Y)).  This
 844   /// function returns SETCC_INVALID if it is not possible to represent the
 845   /// resultant comparison.
 846   CondCode getSetCCAndOperation(CondCode Op1, CondCode Op2, bool isInteger);
 847
 848   //===--------------------------------------------------------------------===//
 849   /// CvtCode enum - This enum defines the various converts CONVERT_RNDSAT
 850   /// supports.
 851   enum CvtCode {
 852     CVT_FF,     // Float from Float
 853     CVT_FS,     // Float from Signed
 854     CVT_FU,     // Float from Unsigned
 855     CVT_SF,     // Signed from Float
 856     CVT_UF,     // Unsigned from Float
 857     CVT_SS,     // Signed from Signed
 858     CVT_SU,     // Signed from Unsigned
 859     CVT_US,     // Unsigned from Signed
 860     CVT_UU,     // Unsigned from Unsigned
 861     CVT_INVALID // Marker - Invalid opcode
 862   };
 863 }  // end llvm::ISD namespace
 864
 865
 866 //===----------------------------------------------------------------------===//
 867 /// SDValue - Unlike LLVM values, Selection DAG nodes may return multiple
 868 /// values as the result of a computation.  Many nodes return multiple values,
 869 /// from loads (which define a token and a return value) to ADDC (which returns
 870 /// a result and a carry value), to calls (which may return an arbitrary number
 871 /// of values).
 872 ///
 873 /// As such, each use of a SelectionDAG computation must indicate the node that
 874 /// computes it as well as which return value to use from that node.  This pair
 875 /// of information is represented with the SDValue value type.
 876 ///
 877 class SDValue {
 878   SDNode *Node;       // The node defining the value we are using.
 879   unsigned ResNo;     // Which return value of the node we are using.
 880 public:
 881   SDValue() : Node(0), ResNo(0) {}
 882   SDValue(SDNode *node, unsigned resno) : Node(node), ResNo(resno) {}
 883
 884   /// get the index which selects a specific result in the SDNode
 885   unsigned getResNo() const { return ResNo; }
 886
 887   /// get the SDNode which holds the desired result
 888   SDNode *getNode() const { return Node; }
 889
 890   /// set the SDNode
 891   void setNode(SDNode *N) { Node = N; }
 892
 893   bool operator==(const SDValue &O) const {
 894     return Node == O.Node && ResNo == O.ResNo;
 895   }
 896   bool operator!=(const SDValue &O) const {
 897     return !operator==(O);
 898   }
 899   bool operator<(const SDValue &O) const {
 900     return Node < O.Node || (Node == O.Node && ResNo < O.ResNo);
 901   }
 902
 903   SDValue getValue(unsigned R) const {
 904     return SDValue(Node, R);
 905   }
 906
 907   // isOperandOf - Return true if this node is an operand of N.
 908   bool isOperandOf(SDNode *N) const;
 909
 910   /// getValueType - Return the ValueType of the referenced return value.
 911   ///
 912   inline MVT getValueType() const;
 913
 914   /// getValueSizeInBits - Returns the size of the value in bits.
 915   ///
 916   unsigned getValueSizeInBits() const {
 917     return getValueType().getSizeInBits();
 918   }
 919
 920   // Forwarding methods - These forward to the corresponding methods in SDNode.
 921   inline unsigned getOpcode() const;
 922   inline unsigned getNumOperands() const;
 923   inline const SDValue &getOperand(unsigned i) const;
 924   inline uint64_t getConstantOperandVal(unsigned i) const;
 925   inline bool isTargetOpcode() const;
 926   inline bool isMachineOpcode() const;
 927   inline unsigned getMachineOpcode() const;
 928
 929
 930   /// reachesChainWithoutSideEffects - Return true if this operand (which must
 931   /// be a chain) reaches the specified operand without crossing any
 932   /// side-effecting instructions.  In practice, this looks through token
 933   /// factors and non-volatile loads.  In order to remain efficient, this only
 934   /// looks a couple of nodes in, it does not do an exhaustive search.
 935   bool reachesChainWithoutSideEffects(SDValue Dest,
 936                                       unsigned Depth = 2) const;
 937
 938   /// use_empty - Return true if there are no nodes using value ResNo
 939   /// of Node.
 940   ///
 941   inline bool use_empty() const;
 942
 943   /// hasOneUse - Return true if there is exactly one node using value
 944   /// ResNo of Node.
 945   ///
 946   inline bool hasOneUse() const;
 947 };
 948
 949
 950 template<> struct DenseMapInfo<SDValue> {
 951   static inline SDValue getEmptyKey() {
 952     return SDValue((SDNode*)-1, -1U);
 953   }
 954   static inline SDValue getTombstoneKey() {
 955     return SDValue((SDNode*)-1, 0);
 956   }
 957   static unsigned getHashValue(const SDValue &Val) {
 958     return ((unsigned)((uintptr_t)Val.getNode() >> 4) ^
 959             (unsigned)((uintptr_t)Val.getNode() >> 9)) + Val.getResNo();
 960   }
 961   static bool isEqual(const SDValue &LHS, const SDValue &RHS) {
 962     return LHS == RHS;
 963   }
 964   static bool isPod() { return true; }
 965 };
 966
 967 /// simplify_type specializations - Allow casting operators to work directly on
 968 /// SDValues as if they were SDNode*'s.
 969 template<> struct simplify_type<SDValue> {
 970   typedef SDNode* SimpleType;
 971   static SimpleType getSimplifiedValue(const SDValue &Val) {
 972     return static_cast<SimpleType>(Val.getNode());
 973   }
 974 };
 975 template<> struct simplify_type<const SDValue> {
 976   typedef SDNode* SimpleType;
 977   static SimpleType getSimplifiedValue(const SDValue &Val) {
 978     return static_cast<SimpleType>(Val.getNode());
 979   }
 980 };
 981
 982 /// SDUse - Represents a use of the SDNode referred by
 983 /// the SDValue.
 984 class SDUse {
 985   SDValue Operand;
 986   /// User - Parent node of this operand.
 987   SDNode    *User;
 988   /// Prev, next - Pointers to the uses list of the SDNode referred by
 989   /// this operand.
 990   SDUse **Prev, *Next;
 991 public:
 992   friend class SDNode;
 993   SDUse(): Operand(), User(NULL), Prev(NULL), Next(NULL) {}
 994
 995   SDUse(SDNode *val, unsigned resno) :
 996     Operand(val,resno), User(NULL), Prev(NULL), Next(NULL) {}
 997
 998   SDUse& operator= (const SDValue& Op) {
 999       Operand = Op;
1000       Next = NULL;
1001       Prev = NULL;
1002       return *this;
1003   }
1004
1005   SDUse& operator= (const SDUse& Op) {
1006       Operand = Op;
1007       Next = NULL;
1008       Prev = NULL;
1009       return *this;
1010   }
1011
1012   SDUse *getNext() { return Next; }
1013
1014   SDNode *getUser() { return User; }
1015
1016   void setUser(SDNode *p) { User = p; }
1017
1018   operator SDValue() const { return Operand; }
1019
1020   const SDValue& getSDValue() const { return Operand; }
1021
1022   SDValue &getSDValue() { return Operand; }
1023   SDNode *getVal() { return Operand.getNode(); }
1024   SDNode *getVal() const { return Operand.getNode(); } // FIXME: const correct?
1025
1026   bool operator==(const SDValue &O) const {
1027     return Operand == O;
1028   }
1029
1030   bool operator!=(const SDValue &O) const {
1031     return !(Operand == O);
1032   }
1033
1034   bool operator<(const SDValue &O) const {
1035     return Operand < O;
1036   }
1037
1038 protected:
1039   void addToList(SDUse **List) {
1040     Next = *List;
1041     if (Next) Next->Prev = &Next;
1042     Prev = List;
1043     *List = this;
1044   }
1045
1046   void removeFromList() {
1047     *Prev = Next;
1048     if (Next) Next->Prev = Prev;
1049   }
1050 };
1051
1052
1053 /// simplify_type specializations - Allow casting operators to work directly on
1054 /// SDValues as if they were SDNode*'s.
1055 template<> struct simplify_type<SDUse> {
1056   typedef SDNode* SimpleType;
1057   static SimpleType getSimplifiedValue(const SDUse &Val) {
1058     return static_cast<SimpleType>(Val.getVal());
1059   }
1060 };
1061 template<> struct simplify_type<const SDUse> {
1062   typedef SDNode* SimpleType;
1063   static SimpleType getSimplifiedValue(const SDUse &Val) {
1064     return static_cast<SimpleType>(Val.getVal());
1065   }
1066 };
1067
1068
1069 /// SDOperandPtr - A helper SDValue pointer class, that can handle
1070 /// arrays of SDUse and arrays of SDValue objects. This is required
1071 /// in many places inside the SelectionDAG.
1072 ///
1073 class SDOperandPtr {
1074   const SDValue *ptr; // The pointer to the SDValue object
1075   int object_size;      // The size of the object containg the SDValue
1076 public:
1077   SDOperandPtr() : ptr(0), object_size(0) {}
1078
1079   SDOperandPtr(SDUse * use_ptr) {
1080     ptr = &use_ptr->getSDValue();
1081     object_size = (int)sizeof(SDUse);
1082   }
1083
1084   SDOperandPtr(const SDValue * op_ptr) {
1085     ptr = op_ptr;
1086     object_size = (int)sizeof(SDValue);
1087   }
1088
1089   const SDValue operator *() { return *ptr; }
1090   const SDValue *operator ->() { return ptr; }
1091   SDOperandPtr operator ++ () {
1092     ptr = (SDValue*)((char *)ptr + object_size);
1093     return *this;
1094   }
1095
1096   SDOperandPtr operator ++ (int) {
1097     SDOperandPtr tmp = *this;
1098     ptr = (SDValue*)((char *)ptr + object_size);
1099     return tmp;
1100   }
1101
1102   SDValue operator[] (int idx) const {
1103     return *(SDValue*)((char*) ptr + object_size * idx);
1104   }
1105 };
1106
1107 /// SDNode - Represents one node in the SelectionDAG.
1108 ///
1109 class SDNode : public FoldingSetNode, public ilist_node<SDNode> {
1110 private:
1111   /// NodeType - The operation that this node performs.
1112   ///
1113   short NodeType;
1114
1115   /// OperandsNeedDelete - This is true if OperandList was new[]'d.  If true,
1116   /// then they will be delete[]'d when the node is destroyed.
1117   unsigned short OperandsNeedDelete : 1;
1118
1119 protected:
1120   /// SubclassData - This member is defined by this class, but is not used for
1121   /// anything.  Subclasses can use it to hold whatever state they find useful.
1122   /// This field is initialized to zero by the ctor.
1123   unsigned short SubclassData : 15;
1124
1125 private:
1126   /// NodeId - Unique id per SDNode in the DAG.
1127   int NodeId;
1128
1129   /// OperandList - The values that are used by this operation.
1130   ///
1131   SDUse *OperandList;
1132
1133   /// ValueList - The types of the values this node defines.  SDNode's may
1134   /// define multiple values simultaneously.
1135   const MVT *ValueList;
1136
1137   /// NumOperands/NumValues - The number of entries in the Operand/Value list.
1138   unsigned short NumOperands, NumValues;
1139
1140   /// Uses - List of uses for this SDNode.
1141   SDUse *Uses;
1142
1143   /// addUse - add SDUse to the list of uses.
1144   void addUse(SDUse &U) { U.addToList(&Uses); }
1145
1146   // Out-of-line virtual method to give class a home.
1147   virtual void ANCHOR();
1148 public:
1149   virtual ~SDNode() {
1150     assert(NumOperands == 0 && "Operand list not cleared before deletion");
1151     NodeType = ISD::DELETED_NODE;
1152   }
1153
1154   //===--------------------------------------------------------------------===//
1155   //  Accessors
1156   //
1157
1158   /// getOpcode - Return the SelectionDAG opcode value for this node. For
1159   /// pre-isel nodes (those for which isMachineOpcode returns false), these
1160   /// are the opcode values in the ISD and <target>ISD namespaces. For
1161   /// post-isel opcodes, see getMachineOpcode.
1162   unsigned getOpcode()  const { return (unsigned short)NodeType; }
1163
1164   /// isTargetOpcode - Test if this node has a target-specific opcode (in the
1165   /// <target>ISD namespace).
1166   bool isTargetOpcode() const { return NodeType >= ISD::BUILTIN_OP_END; }
1167
1168   /// isMachineOpcode - Test if this node has a post-isel opcode, directly
1169   /// corresponding to a MachineInstr opcode.
1170   bool isMachineOpcode() const { return NodeType < 0; }
1171
1172   /// getMachineOpcode - This may only be called if isMachineOpcode returns
1173   /// true. It returns the MachineInstr opcode value that the node's opcode
1174   /// corresponds to.
1175   unsigned getMachineOpcode() const {
1176     assert(isMachineOpcode() && "Not a MachineInstr opcode!");
1177     return ~NodeType;
1178   }
1179
1180   /// use_empty - Return true if there are no uses of this node.
1181   ///
1182   bool use_empty() const { return Uses == NULL; }
1183
1184   /// hasOneUse - Return true if there is exactly one use of this node.
1185   ///
1186   bool hasOneUse() const {
1187     return !use_empty() && next(use_begin()) == use_end();
1188   }
1189
1190   /// use_size - Return the number of uses of this node. This method takes
1191   /// time proportional to the number of uses.
1192   ///
1193   size_t use_size() const { return std::distance(use_begin(), use_end()); }
1194
1195   /// getNodeId - Return the unique node id.
1196   ///
1197   int getNodeId() const { return NodeId; }
1198
1199   /// setNodeId - Set unique node id.
1200   void setNodeId(int Id) { NodeId = Id; }
1201
1202   /// use_iterator - This class provides iterator support for SDUse
1203   /// operands that use a specific SDNode.
1204   class use_iterator
1205     : public forward_iterator<SDUse, ptrdiff_t> {
1206     SDUse *Op;
1207     explicit use_iterator(SDUse *op) : Op(op) {
1208     }
1209     friend class SDNode;
1210   public:
1211     typedef forward_iterator<SDUse, ptrdiff_t>::reference reference;
1212     typedef forward_iterator<SDUse, ptrdiff_t>::pointer pointer;
1213
1214     use_iterator(const use_iterator &I) : Op(I.Op) {}
1215     use_iterator() : Op(0) {}
1216
1217     bool operator==(const use_iterator &x) const {
1218       return Op == x.Op;
1219     }
1220     bool operator!=(const use_iterator &x) const {
1221       return !operator==(x);
1222     }
1223
1224     /// atEnd - return true if this iterator is at the end of uses list.
1225     bool atEnd() const { return Op == 0; }
1226
1227     // Iterator traversal: forward iteration only.
1228     use_iterator &operator++() {          // Preincrement
1229       assert(Op && "Cannot increment end iterator!");
1230       Op = Op->getNext();
1231       return *this;
1232     }
1233
1234     use_iterator operator++(int) {        // Postincrement
1235       use_iterator tmp = *this; ++*this; return tmp;
1236     }
1237
1238     /// Retrieve a pointer to the current user node.
1239     SDNode *operator*() const {
1240       assert(Op && "Cannot dereference end iterator!");
1241       return Op->getUser();
1242     }
1243
1244     SDNode *operator->() const { return operator*(); }
1245
1246     SDUse &getUse() const { return *Op; }
1247
1248     /// getOperandNo - Retrive the operand # of this use in its user.
1249     ///
1250     unsigned getOperandNo() const {
1251       assert(Op && "Cannot dereference end iterator!");
1252       return (unsigned)(Op - Op->getUser()->OperandList);
1253     }
1254   };
1255
1256   /// use_begin/use_end - Provide iteration support to walk over all uses
1257   /// of an SDNode.
1258
1259   use_iterator use_begin() const {
1260     return use_iterator(Uses);
1261   }
1262
1263   static use_iterator use_end() { return use_iterator(0); }
1264
1265
1266   /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
1267   /// indicated value.  This method ignores uses of other values defined by this
1268   /// operation.
1269   bool hasNUsesOfValue(unsigned NUses, unsigned Value) const;
1270
1271   /// hasAnyUseOfValue - Return true if there are any use of the indicated
1272   /// value. This method ignores uses of other values defined by this operation.
1273   bool hasAnyUseOfValue(unsigned Value) const;
1274
1275   /// isOnlyUserOf - Return true if this node is the only use of N.
1276   ///
1277   bool isOnlyUserOf(SDNode *N) const;
1278
1279   /// isOperandOf - Return true if this node is an operand of N.
1280   ///
1281   bool isOperandOf(SDNode *N) const;
1282
1283   /// isPredecessorOf - Return true if this node is a predecessor of N. This
1284   /// node is either an operand of N or it can be reached by recursively
1285   /// traversing up the operands.
1286   /// NOTE: this is an expensive method. Use it carefully.
1287   bool isPredecessorOf(SDNode *N) const;
1288
1289   /// getNumOperands - Return the number of values used by this operation.
1290   ///
1291   unsigned getNumOperands() const { return NumOperands; }
1292
1293   /// getConstantOperandVal - Helper method returns the integer value of a
1294   /// ConstantSDNode operand.
1295   uint64_t getConstantOperandVal(unsigned Num) const;
1296
1297   const SDValue &getOperand(unsigned Num) const {
1298     assert(Num < NumOperands && "Invalid child # of SDNode!");
1299     return OperandList[Num].getSDValue();
1300   }
1301
1302   typedef SDUse* op_iterator;
1303   op_iterator op_begin() const { return OperandList; }
1304   op_iterator op_end() const { return OperandList+NumOperands; }
1305
1306
1307   SDVTList getVTList() const {
1308     SDVTList X = { ValueList, NumValues };
1309     return X;
1310   };
1311
1312   /// getFlaggedNode - If this node has a flag operand, return the node
1313   /// to which the flag operand points. Otherwise return NULL.
1314   SDNode *getFlaggedNode() const {
1315     if (getNumOperands() != 0 &&
1316         getOperand(getNumOperands()-1).getValueType() == MVT::Flag)
1317       return getOperand(getNumOperands()-1).getNode();
1318     return 0;
1319   }
1320
1321   /// getNumValues - Return the number of values defined/returned by this
1322   /// operator.
1323   ///
1324   unsigned getNumValues() const { return NumValues; }
1325
1326   /// getValueType - Return the type of a specified result.
1327   ///
1328   MVT getValueType(unsigned ResNo) const {
1329     assert(ResNo < NumValues && "Illegal result number!");
1330     return ValueList[ResNo];
1331   }
1332
1333   /// getValueSizeInBits - Returns MVT::getSizeInBits(getValueType(ResNo)).
1334   ///
1335   unsigned getValueSizeInBits(unsigned ResNo) const {
1336     return getValueType(ResNo).getSizeInBits();
1337   }
1338
1339   typedef const MVT* value_iterator;
1340   value_iterator value_begin() const { return ValueList; }
1341   value_iterator value_end() const { return ValueList+NumValues; }
1342
1343   /// getOperationName - Return the opcode of this operation for printing.
1344   ///
1345   std::string getOperationName(const SelectionDAG *G = 0) const;
1346   static const char* getIndexedModeName(ISD::MemIndexedMode AM);
1347   void print(raw_ostream &OS, const SelectionDAG *G = 0) const;
1348   void dump() const;
1349   void dump(const SelectionDAG *G) const;
1350
1351   static bool classof(const SDNode *) { return true; }
1352
1353   /// Profile - Gather unique data for the node.
1354   ///
1355   void Profile(FoldingSetNodeID &ID) const;
1356
1357 protected:
1358   friend class SelectionDAG;
1359   friend struct ilist_traits<SDNode>;
1360
1361   /// getValueTypeList - Return a pointer to the specified value type.
1362   ///
1363   static const MVT *getValueTypeList(MVT VT);
1364   static SDVTList getSDVTList(MVT VT) {
1365     SDVTList Ret = { getValueTypeList(VT), 1 };
1366     return Ret;
1367   }
1368
1369   SDNode(unsigned Opc, SDVTList VTs, const SDValue *Ops, unsigned NumOps)
1370     : NodeType(Opc), OperandsNeedDelete(true), SubclassData(0),
1371       NodeId(-1), Uses(NULL) {
1372     NumOperands = NumOps;
1373     OperandList = NumOps ? new SDUse[NumOperands] : 0;
1374
1375     for (unsigned i = 0; i != NumOps; ++i) {
1376       OperandList[i] = Ops[i];
1377       OperandList[i].setUser(this);
1378       Ops[i].getNode()->addUse(OperandList[i]);
1379     }
1380
1381     ValueList = VTs.VTs;
1382     NumValues = VTs.NumVTs;
1383   }
1384
1385   SDNode(unsigned Opc, SDVTList VTs, const SDUse *Ops, unsigned NumOps)
1386     : NodeType(Opc), OperandsNeedDelete(true), SubclassData(0),
1387       NodeId(-1), Uses(NULL) {
1388     OperandsNeedDelete = true;
1389     NumOperands = NumOps;
1390     OperandList = NumOps ? new SDUse[NumOperands] : 0;
1391
1392     for (unsigned i = 0; i != NumOps; ++i) {
1393       OperandList[i] = Ops[i];
1394       OperandList[i].setUser(this);
1395       Ops[i].getVal()->addUse(OperandList[i]);
1396     }
1397
1398     ValueList = VTs.VTs;
1399     NumValues = VTs.NumVTs;
1400   }
1401
1402   /// This constructor adds no operands itself; operands can be
1403   /// set later with InitOperands.
1404   SDNode(unsigned Opc, SDVTList VTs)
1405     : NodeType(Opc), OperandsNeedDelete(false), SubclassData(0),
1406       NodeId(-1), Uses(NULL) {
1407     NumOperands = 0;
1408     OperandList = 0;
1409     ValueList = VTs.VTs;
1410     NumValues = VTs.NumVTs;
1411   }
1412
1413   /// InitOperands - Initialize the operands list of this node with the
1414   /// specified values, which are part of the node (thus they don't need to be
1415   /// copied in or allocated).
1416   void InitOperands(SDUse *Ops, unsigned NumOps) {
1417     assert(OperandList == 0 && "Operands already set!");
1418     NumOperands = NumOps;
1419     OperandList = Ops;
1420     Uses = NULL;
1421
1422     for (unsigned i = 0; i != NumOps; ++i) {
1423       OperandList[i].setUser(this);
1424       Ops[i].getVal()->addUse(OperandList[i]);
1425     }
1426   }
1427
1428   /// DropOperands - Release the operands and set this node to have
1429   /// zero operands.
1430   void DropOperands();
1431
1432   void addUser(unsigned i, SDNode *User) {
1433     assert(User->OperandList[i].getUser() && "Node without parent");
1434     addUse(User->OperandList[i]);
1435   }
1436
1437   void removeUser(unsigned i, SDNode *User) {
1438     assert(User->OperandList[i].getUser() && "Node without parent");
1439     SDUse &Op = User->OperandList[i];
1440     Op.removeFromList();
1441   }
1442 };
1443
1444
1445 // Define inline functions from the SDValue class.
1446
1447 inline unsigned SDValue::getOpcode() const {
1448   return Node->getOpcode();
1449 }
1450 inline MVT SDValue::getValueType() const {
1451   return Node->getValueType(ResNo);
1452 }
1453 inline unsigned SDValue::getNumOperands() const {
1454   return Node->getNumOperands();
1455 }
1456 inline const SDValue &SDValue::getOperand(unsigned i) const {
1457   return Node->getOperand(i);
1458 }
1459 inline uint64_t SDValue::getConstantOperandVal(unsigned i) const {
1460   return Node->getConstantOperandVal(i);
1461 }
1462 inline bool SDValue::isTargetOpcode() const {
1463   return Node->isTargetOpcode();
1464 }
1465 inline bool SDValue::isMachineOpcode() const {
1466   return Node->isMachineOpcode();
1467 }
1468 inline unsigned SDValue::getMachineOpcode() const {
1469   return Node->getMachineOpcode();
1470 }
1471 inline bool SDValue::use_empty() const {
1472   return !Node->hasAnyUseOfValue(ResNo);
1473 }
1474 inline bool SDValue::hasOneUse() const {
1475   return Node->hasNUsesOfValue(1, ResNo);
1476 }
1477
1478 /// UnarySDNode - This class is used for single-operand SDNodes.  This is solely
1479 /// to allow co-allocation of node operands with the node itself.
1480 class UnarySDNode : public SDNode {
1481   virtual void ANCHOR();  // Out-of-line virtual method to give class a home.
1482   SDUse Op;
1483 public:
1484   UnarySDNode(unsigned Opc, SDVTList VTs, SDValue X)
1485     : SDNode(Opc, VTs) {
1486     Op = X;
1487     InitOperands(&Op, 1);
1488   }
1489 };
1490
1491 /// BinarySDNode - This class is used for two-operand SDNodes.  This is solely
1492 /// to allow co-allocation of node operands with the node itself.
1493 class BinarySDNode : public SDNode {
1494   virtual void ANCHOR();  // Out-of-line virtual method to give class a home.
1495   SDUse Ops[2];
1496 public:
1497   BinarySDNode(unsigned Opc, SDVTList VTs, SDValue X, SDValue Y)
1498     : SDNode(Opc, VTs) {
1499     Ops[0] = X;
1500     Ops[1] = Y;
1501     InitOperands(Ops, 2);
1502   }
1503 };
1504
1505 /// TernarySDNode - This class is used for three-operand SDNodes. This is solely
1506 /// to allow co-allocation of node operands with the node itself.
1507 class TernarySDNode : public SDNode {
1508   virtual void ANCHOR();  // Out-of-line virtual method to give class a home.
1509   SDUse Ops[3];
1510 public:
1511   TernarySDNode(unsigned Opc, SDVTList VTs, SDValue X, SDValue Y,
1512                 SDValue Z)
1513     : SDNode(Opc, VTs) {
1514     Ops[0] = X;
1515     Ops[1] = Y;
1516     Ops[2] = Z;
1517     InitOperands(Ops, 3);
1518   }
1519 };
1520
1521
1522 /// HandleSDNode - This class is used to form a handle around another node that
1523 /// is persistant and is updated across invocations of replaceAllUsesWith on its
1524 /// operand.  This node should be directly created by end-users and not added to
1525 /// the AllNodes list.
1526 class HandleSDNode : public SDNode {
1527   virtual void ANCHOR();  // Out-of-line virtual method to give class a home.
1528   SDUse Op;
1529 public:
1530   // FIXME: Remove the "noinline" attribute once <rdar://problem/5852746> is
1531   // fixed.
1532 #ifdef __GNUC__
1533   explicit __attribute__((__noinline__)) HandleSDNode(SDValue X)
1534 #else
1535   explicit HandleSDNode(SDValue X)
1536 #endif
1537     : SDNode(ISD::HANDLENODE, getSDVTList(MVT::Other)) {
1538     Op = X;
1539     InitOperands(&Op, 1);
1540   }
1541   ~HandleSDNode();
1542   const SDValue &getValue() const { return Op.getSDValue(); }
1543 };
1544
1545 /// Abstact virtual class for operations for memory operations
1546 class MemSDNode : public SDNode {
1547   virtual void ANCHOR();  // Out-of-line virtual method to give class a home.
1548
1549 private:
1550   // MemoryVT - VT of in-memory value.
1551   MVT MemoryVT;
1552
1553   //! SrcValue - Memory location for alias analysis.
1554   const Value *SrcValue;
1555
1556   //! SVOffset - Memory location offset. Note that base is defined in MemSDNode
1557   int SVOffset;
1558
1559   /// Flags - the low bit indicates whether this is a volatile reference;
1560   /// the remainder is a log2 encoding of the alignment in bytes.
1561   unsigned Flags;
1562
1563 public:
1564   MemSDNode(unsigned Opc, SDVTList VTs, MVT MemoryVT,
1565             const Value *srcValue, int SVOff,
1566             unsigned alignment, bool isvolatile);
1567
1568   MemSDNode(unsigned Opc, SDVTList VTs, const SDValue *Ops, unsigned NumOps,
1569             MVT MemoryVT, const Value *srcValue, int SVOff,
1570             unsigned alignment, bool isvolatile);
1571
1572   /// Returns alignment and volatility of the memory access
1573   unsigned getAlignment() const { return (1u << (Flags >> 1)) >> 1; }
1574   bool isVolatile() const { return Flags & 1; }
1575
1576   /// Returns the SrcValue and offset that describes the location of the access
1577   const Value *getSrcValue() const { return SrcValue; }
1578   int getSrcValueOffset() const { return SVOffset; }
1579
1580   /// getMemoryVT - Return the type of the in-memory value.
1581   MVT getMemoryVT() const { return MemoryVT; }
1582
1583   /// getMemOperand - Return a MachineMemOperand object describing the memory
1584   /// reference performed by operation.
1585   MachineMemOperand getMemOperand() const;
1586
1587   const SDValue &getChain() const { return getOperand(0); }
1588   const SDValue &getBasePtr() const {
1589     return getOperand(getOpcode() == ISD::STORE ? 2 : 1);
1590   }
1591
1592   /// getRawFlags - Represent the flags as a bunch of bits.
1593   ///
1594   unsigned getRawFlags() const { return Flags; }
1595
1596   // Methods to support isa and dyn_cast
1597   static bool classof(const MemSDNode *) { return true; }
1598   static bool classof(const SDNode *N) {
1599     // For some targets, we lower some target intrinsics to a MemIntrinsicNode
1600     // with either an intrinsic or a target opcode.
1601     return N->getOpcode() == ISD::LOAD                ||
1602            N->getOpcode() == ISD::STORE               ||
1603            N->getOpcode() == ISD::ATOMIC_CMP_SWAP_8   ||
1604            N->getOpcode() == ISD::ATOMIC_SWAP_8       ||
1605            N->getOpcode() == ISD::ATOMIC_LOAD_ADD_8   ||
1606            N->getOpcode() == ISD::ATOMIC_LOAD_SUB_8   ||
1607            N->getOpcode() == ISD::ATOMIC_LOAD_AND_8   ||
1608            N->getOpcode() == ISD::ATOMIC_LOAD_OR_8    ||
1609            N->getOpcode() == ISD::ATOMIC_LOAD_XOR_8   ||
1610            N->getOpcode() == ISD::ATOMIC_LOAD_NAND_8  ||
1611            N->getOpcode() == ISD::ATOMIC_LOAD_MIN_8   ||
1612            N->getOpcode() == ISD::ATOMIC_LOAD_MAX_8   ||
1613            N->getOpcode() == ISD::ATOMIC_LOAD_UMIN_8  ||
1614            N->getOpcode() == ISD::ATOMIC_LOAD_UMAX_8  ||
1615
1616            N->getOpcode() == ISD::ATOMIC_CMP_SWAP_16  ||
1617            N->getOpcode() == ISD::ATOMIC_SWAP_16      ||
1618            N->getOpcode() == ISD::ATOMIC_LOAD_ADD_16  ||
1619            N->getOpcode() == ISD::ATOMIC_LOAD_SUB_16  ||
1620            N->getOpcode() == ISD::ATOMIC_LOAD_AND_16  ||
1621            N->getOpcode() == ISD::ATOMIC_LOAD_OR_16   ||
1622            N->getOpcode() == ISD::ATOMIC_LOAD_XOR_16  ||
1623            N->getOpcode() == ISD::ATOMIC_LOAD_NAND_16 ||
1624            N->getOpcode() == ISD::ATOMIC_LOAD_MIN_16  ||
1625            N->getOpcode() == ISD::ATOMIC_LOAD_MAX_16  ||
1626            N->getOpcode() == ISD::ATOMIC_LOAD_UMIN_16 ||
1627            N->getOpcode() == ISD::ATOMIC_LOAD_UMAX_16 ||
1628
1629            N->getOpcode() == ISD::ATOMIC_CMP_SWAP_32  ||
1630            N->getOpcode() == ISD::ATOMIC_SWAP_32      ||
1631            N->getOpcode() == ISD::ATOMIC_LOAD_ADD_32  ||
1632            N->getOpcode() == ISD::ATOMIC_LOAD_SUB_32  ||
1633            N->getOpcode() == ISD::ATOMIC_LOAD_AND_32  ||
1634            N->getOpcode() == ISD::ATOMIC_LOAD_OR_32   ||
1635            N->getOpcode() == ISD::ATOMIC_LOAD_XOR_32  ||
1636            N->getOpcode() == ISD::ATOMIC_LOAD_NAND_32 ||
1637            N->getOpcode() == ISD::ATOMIC_LOAD_MIN_32  ||
1638            N->getOpcode() == ISD::ATOMIC_LOAD_MAX_32  ||
1639            N->getOpcode() == ISD::ATOMIC_LOAD_UMIN_32 ||
1640            N->getOpcode() == ISD::ATOMIC_LOAD_UMAX_32 ||
1641
1642            N->getOpcode() == ISD::ATOMIC_CMP_SWAP_64  ||
1643            N->getOpcode() == ISD::ATOMIC_SWAP_64      ||
1644            N->getOpcode() == ISD::ATOMIC_LOAD_ADD_64  ||
1645            N->getOpcode() == ISD::ATOMIC_LOAD_SUB_64  ||
1646            N->getOpcode() == ISD::ATOMIC_LOAD_AND_64  ||
1647            N->getOpcode() == ISD::ATOMIC_LOAD_OR_64   ||
1648            N->getOpcode() == ISD::ATOMIC_LOAD_XOR_64  ||
1649            N->getOpcode() == ISD::ATOMIC_LOAD_NAND_64 ||
1650            N->getOpcode() == ISD::ATOMIC_LOAD_MIN_64  ||
1651            N->getOpcode() == ISD::ATOMIC_LOAD_MAX_64  ||
1652            N->getOpcode() == ISD::ATOMIC_LOAD_UMIN_64 ||
1653            N->getOpcode() == ISD::ATOMIC_LOAD_UMAX_64 ||
1654
1655            N->getOpcode() == ISD::INTRINSIC_W_CHAIN   ||
1656            N->getOpcode() == ISD::INTRINSIC_VOID      ||
1657            N->isTargetOpcode();
1658   }
1659 };
1660
1661 /// AtomicSDNode - A SDNode reprenting atomic operations.
1662 ///
1663 class AtomicSDNode : public MemSDNode {
1664   virtual void ANCHOR();  // Out-of-line virtual method to give class a home.
1665   SDUse Ops[4];
1666
1667  public:
1668   // Opc:   opcode for atomic
1669   // VTL:    value type list
1670   // Chain:  memory chain for operaand
1671   // Ptr:    address to update as a SDValue
1672   // Cmp:    compare value
1673   // Swp:    swap value
1674   // SrcVal: address to update as a Value (used for MemOperand)
1675   // Align:  alignment of memory
1676   AtomicSDNode(unsigned Opc, SDVTList VTL, SDValue Chain, SDValue Ptr,
1677                SDValue Cmp, SDValue Swp, const Value* SrcVal,
1678                unsigned Align=0)
1679     : MemSDNode(Opc, VTL, Cmp.getValueType(), SrcVal, /*SVOffset=*/0,
1680                 Align, /*isVolatile=*/true) {
1681     Ops[0] = Chain;
1682     Ops[1] = Ptr;
1683     Ops[2] = Cmp;
1684     Ops[3] = Swp;
1685     InitOperands(Ops, 4);
1686   }
1687   AtomicSDNode(unsigned Opc, SDVTList VTL, SDValue Chain, SDValue Ptr,
1688                SDValue Val, const Value* SrcVal, unsigned Align=0)
1689     : MemSDNode(Opc, VTL, Val.getValueType(), SrcVal, /*SVOffset=*/0,
1690                 Align, /*isVolatile=*/true) {
1691     Ops[0] = Chain;
1692     Ops[1] = Ptr;
1693     Ops[2] = Val;
1694     InitOperands(Ops, 3);
1695   }
1696
1697   const SDValue &getBasePtr() const { return getOperand(1); }
1698   const SDValue &getVal() const { return getOperand(2); }
1699
1700   bool isCompareAndSwap() const {
1701     unsigned Op = getOpcode();
1702     return Op == ISD::ATOMIC_CMP_SWAP_8 ||
1703            Op == ISD::ATOMIC_CMP_SWAP_16 ||
1704            Op == ISD::ATOMIC_CMP_SWAP_32 ||
1705            Op == ISD::ATOMIC_CMP_SWAP_64;
1706   }
1707
1708   // Methods to support isa and dyn_cast
1709   static bool classof(const AtomicSDNode *) { return true; }
1710   static bool classof(const SDNode *N) {
1711     return N->getOpcode() == ISD::ATOMIC_CMP_SWAP_8   ||
1712            N->getOpcode() == ISD::ATOMIC_SWAP_8       ||
1713            N->getOpcode() == ISD::ATOMIC_LOAD_ADD_8   ||
1714            N->getOpcode() == ISD::ATOMIC_LOAD_SUB_8   ||
1715            N->getOpcode() == ISD::ATOMIC_LOAD_AND_8   ||
1716            N->getOpcode() == ISD::ATOMIC_LOAD_OR_8    ||
1717            N->getOpcode() == ISD::ATOMIC_LOAD_XOR_8   ||
1718            N->getOpcode() == ISD::ATOMIC_LOAD_NAND_8  ||
1719            N->getOpcode() == ISD::ATOMIC_LOAD_MIN_8   ||
1720            N->getOpcode() == ISD::ATOMIC_LOAD_MAX_8   ||
1721            N->getOpcode() == ISD::ATOMIC_LOAD_UMIN_8  ||
1722            N->getOpcode() == ISD::ATOMIC_LOAD_UMAX_8  ||
1723            N->getOpcode() == ISD::ATOMIC_CMP_SWAP_16  ||
1724            N->getOpcode() == ISD::ATOMIC_SWAP_16      ||
1725            N->getOpcode() == ISD::ATOMIC_LOAD_ADD_16  ||
1726            N->getOpcode() == ISD::ATOMIC_LOAD_SUB_16  ||
1727            N->getOpcode() == ISD::ATOMIC_LOAD_AND_16  ||
1728            N->getOpcode() == ISD::ATOMIC_LOAD_OR_16   ||
1729            N->getOpcode() == ISD::ATOMIC_LOAD_XOR_16  ||
1730            N->getOpcode() == ISD::ATOMIC_LOAD_NAND_16 ||
1731            N->getOpcode() == ISD::ATOMIC_LOAD_MIN_16  ||
1732            N->getOpcode() == ISD::ATOMIC_LOAD_MAX_16  ||
1733            N->getOpcode() == ISD::ATOMIC_LOAD_UMIN_16 ||
1734            N->getOpcode() == ISD::ATOMIC_LOAD_UMAX_16 ||
1735            N->getOpcode() == ISD::ATOMIC_CMP_SWAP_32  ||
1736            N->getOpcode() == ISD::ATOMIC_SWAP_32      ||
1737            N->getOpcode() == ISD::ATOMIC_LOAD_ADD_32  ||
1738            N->getOpcode() == ISD::ATOMIC_LOAD_SUB_32  ||
1739            N->getOpcode() == ISD::ATOMIC_LOAD_AND_32  ||
1740            N->getOpcode() == ISD::ATOMIC_LOAD_OR_32   ||
1741            N->getOpcode() == ISD::ATOMIC_LOAD_XOR_32  ||
1742            N->getOpcode() == ISD::ATOMIC_LOAD_NAND_32 ||
1743            N->getOpcode() == ISD::ATOMIC_LOAD_MIN_32  ||
1744            N->getOpcode() == ISD::ATOMIC_LOAD_MAX_32  ||
1745            N->getOpcode() == ISD::ATOMIC_LOAD_UMIN_32 ||
1746            N->getOpcode() == ISD::ATOMIC_LOAD_UMAX_32 ||
1747            N->getOpcode() == ISD::ATOMIC_CMP_SWAP_64  ||
1748            N->getOpcode() == ISD::ATOMIC_SWAP_64      ||
1749            N->getOpcode() == ISD::ATOMIC_LOAD_ADD_64  ||
1750            N->getOpcode() == ISD::ATOMIC_LOAD_SUB_64  ||
1751            N->getOpcode() == ISD::ATOMIC_LOAD_AND_64  ||
1752            N->getOpcode() == ISD::ATOMIC_LOAD_OR_64   ||
1753            N->getOpcode() == ISD::ATOMIC_LOAD_XOR_64  ||
1754            N->getOpcode() == ISD::ATOMIC_LOAD_NAND_64 ||
1755            N->getOpcode() == ISD::ATOMIC_LOAD_MIN_64  ||
1756            N->getOpcode() == ISD::ATOMIC_LOAD_MAX_64  ||
1757            N->getOpcode() == ISD::ATOMIC_LOAD_UMIN_64 ||
1758            N->getOpcode() == ISD::ATOMIC_LOAD_UMAX_64;
1759   }
1760 };
1761
1762 /// MemIntrinsicSDNode - This SDNode is used for target intrinsic that touches
1763 /// memory and need an associated memory operand.
1764 ///
1765 class MemIntrinsicSDNode : public MemSDNode {
1766   virtual void ANCHOR();  // Out-of-line virtual method to give class a home.
1767   bool ReadMem;  // Intrinsic reads memory
1768   bool WriteMem; // Intrinsic writes memory
1769   public:
1770   MemIntrinsicSDNode(unsigned Opc, SDVTList VTs,
1771                      const SDValue *Ops, unsigned NumOps,
1772                      MVT MemoryVT, const Value *srcValue, int SVO,
1773                      unsigned Align, bool Vol, bool ReadMem, bool WriteMem)
1774     : MemSDNode(Opc, VTs, Ops, NumOps, MemoryVT, srcValue, SVO, Align, Vol),
1775       ReadMem(ReadMem), WriteMem(WriteMem) {
1776   }
1777
1778   bool readMem() const { return ReadMem; }
1779   bool writeMem() const { return WriteMem; }
1780
1781   // Methods to support isa and dyn_cast
1782   static bool classof(const MemIntrinsicSDNode *) { return true; }
1783   static bool classof(const SDNode *N) {
1784     // We lower some target intrinsics to their target opcode
1785     // early a node with a target opcode can be of this class
1786     return N->getOpcode() == ISD::INTRINSIC_W_CHAIN ||
1787            N->getOpcode() == ISD::INTRINSIC_VOID ||
1788            N->isTargetOpcode();
1789   }
1790 };
1791
1792 class ConstantSDNode : public SDNode {
1793   const ConstantInt *Value;
1794   virtual void ANCHOR();  // Out-of-line virtual method to give class a home.
1795 protected:
1796   friend class SelectionDAG;
1797   ConstantSDNode(bool isTarget, const ConstantInt *val, MVT VT)
1798     : SDNode(isTarget ? ISD::TargetConstant : ISD::Constant, getSDVTList(VT)),
1799       Value(val) {
1800   }
1801 public:
1802
1803   const ConstantInt *getConstantIntValue() const { return Value; }
1804   const APInt &getAPIntValue() const { return Value->getValue(); }
1805   uint64_t getZExtValue() const { return Value->getZExtValue(); }
1806   int64_t getSExtValue() const { return Value->getSExtValue(); }
1807
1808   bool isNullValue() const { return Value->isNullValue(); }
1809   bool isAllOnesValue() const { return Value->isAllOnesValue(); }
1810
1811   static bool classof(const ConstantSDNode *) { return true; }
1812   static bool classof(const SDNode *N) {
1813     return N->getOpcode() == ISD::Constant ||
1814            N->getOpcode() == ISD::TargetConstant;
1815   }
1816 };
1817
1818 class ConstantFPSDNode : public SDNode {
1819   const ConstantFP *Value;
1820   virtual void ANCHOR();  // Out-of-line virtual method to give class a home.
1821 protected:
1822   friend class SelectionDAG;
1823   ConstantFPSDNode(bool isTarget, const ConstantFP *val, MVT VT)
1824     : SDNode(isTarget ? ISD::TargetConstantFP : ISD::ConstantFP,
1825              getSDVTList(VT)), Value(val) {
1826   }
1827 public:
1828
1829   const APFloat& getValueAPF() const { return Value->getValueAPF(); }
1830   const ConstantFP *getConstantFPValue() const { return Value; }
1831
1832   /// isExactlyValue - We don't rely on operator== working on double values, as
1833   /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
1834   /// As such, this method can be used to do an exact bit-for-bit comparison of
1835   /// two floating point values.
1836
1837   /// We leave the version with the double argument here because it's just so
1838   /// convenient to write "2.0" and the like.  Without this function we'd
1839   /// have to duplicate its logic everywhere it's called.
1840   bool isExactlyValue(double V) const {
1841     bool ignored;
1842     // convert is not supported on this type
1843     if (&Value->getValueAPF().getSemantics() == &APFloat::PPCDoubleDouble)
1844       return false;
1845     APFloat Tmp(V);
1846     Tmp.convert(Value->getValueAPF().getSemantics(),
1847                 APFloat::rmNearestTiesToEven, &ignored);
1848     return isExactlyValue(Tmp);
1849   }
1850   bool isExactlyValue(const APFloat& V) const;
1851
1852   bool isValueValidForType(MVT VT, const APFloat& Val);
1853
1854   static bool classof(const ConstantFPSDNode *) { return true; }
1855   static bool classof(const SDNode *N) {
1856     return N->getOpcode() == ISD::ConstantFP ||
1857            N->getOpcode() == ISD::TargetConstantFP;
1858   }
1859 };
1860
1861 class GlobalAddressSDNode : public SDNode {
1862   GlobalValue *TheGlobal;
1863   int64_t Offset;
1864   virtual void ANCHOR();  // Out-of-line virtual method to give class a home.
1865 protected:
1866   friend class SelectionDAG;
1867   GlobalAddressSDNode(bool isTarget, const GlobalValue *GA, MVT VT,
1868                       int64_t o = 0);
1869 public:
1870
1871   GlobalValue *getGlobal() const { return TheGlobal; }
1872   int64_t getOffset() const { return Offset; }
1873
1874   static bool classof(const GlobalAddressSDNode *) { return true; }
1875   static bool classof(const SDNode *N) {
1876     return N->getOpcode() == ISD::GlobalAddress ||
1877            N->getOpcode() == ISD::TargetGlobalAddress ||
1878            N->getOpcode() == ISD::GlobalTLSAddress ||
1879            N->getOpcode() == ISD::TargetGlobalTLSAddress;
1880   }
1881 };
1882
1883 class FrameIndexSDNode : public SDNode {
1884   int FI;
1885   virtual void ANCHOR();  // Out-of-line virtual method to give class a home.
1886 protected:
1887   friend class SelectionDAG;
1888   FrameIndexSDNode(int fi, MVT VT, bool isTarg)
1889     : SDNode(isTarg ? ISD::TargetFrameIndex : ISD::FrameIndex, getSDVTList(VT)),
1890       FI(fi) {
1891   }
1892 public:
1893
1894   int getIndex() const { return FI; }
1895
1896   static bool classof(const FrameIndexSDNode *) { return true; }
1897   static bool classof(const SDNode *N) {
1898     return N->getOpcode() == ISD::FrameIndex ||
1899            N->getOpcode() == ISD::TargetFrameIndex;
1900   }
1901 };
1902
1903 class JumpTableSDNode : public SDNode {
1904   int JTI;
1905   virtual void ANCHOR();  // Out-of-line virtual method to give class a home.
1906 protected:
1907   friend class SelectionDAG;
1908   JumpTableSDNode(int jti, MVT VT, bool isTarg)
1909     : SDNode(isTarg ? ISD::TargetJumpTable : ISD::JumpTable, getSDVTList(VT)),
1910       JTI(jti) {
1911   }
1912 public:
1913
1914   int getIndex() const { return JTI; }
1915
1916   static bool classof(const JumpTableSDNode *) { return true; }
1917   static bool classof(const SDNode *N) {
1918     return N->getOpcode() == ISD::JumpTable ||
1919            N->getOpcode() == ISD::TargetJumpTable;
1920   }
1921 };
1922
1923 class ConstantPoolSDNode : public SDNode {
1924   union {
1925     Constant *ConstVal;
1926     MachineConstantPoolValue *MachineCPVal;
1927   } Val;
1928   int Offset;  // It's a MachineConstantPoolValue if top bit is set.
1929   unsigned Alignment;
1930   virtual void ANCHOR();  // Out-of-line virtual method to give class a home.
1931 protected:
1932   friend class SelectionDAG;
1933   ConstantPoolSDNode(bool isTarget, Constant *c, MVT VT, int o=0)
1934     : SDNode(isTarget ? ISD::TargetConstantPool : ISD::ConstantPool,
1935              getSDVTList(VT)), Offset(o), Alignment(0) {
1936     assert((int)Offset >= 0 && "Offset is too large");
1937     Val.ConstVal = c;
1938   }
1939   ConstantPoolSDNode(bool isTarget, Constant *c, MVT VT, int o, unsigned Align)
1940     : SDNode(isTarget ? ISD::TargetConstantPool : ISD::ConstantPool,
1941              getSDVTList(VT)), Offset(o), Alignment(Align) {
1942     assert((int)Offset >= 0 && "Offset is too large");
1943     Val.ConstVal = c;
1944   }
1945   ConstantPoolSDNode(bool isTarget, MachineConstantPoolValue *v,
1946                      MVT VT, int o=0)
1947     : SDNode(isTarget ? ISD::TargetConstantPool : ISD::ConstantPool,
1948              getSDVTList(VT)), Offset(o), Alignment(0) {
1949     assert((int)Offset >= 0 && "Offset is too large");
1950     Val.MachineCPVal = v;
1951     Offset |= 1 << (sizeof(unsigned)*8-1);
1952   }
1953   ConstantPoolSDNode(bool isTarget, MachineConstantPoolValue *v,
1954                      MVT VT, int o, unsigned Align)
1955     : SDNode(isTarget ? ISD::TargetConstantPool : ISD::ConstantPool,
1956              getSDVTList(VT)), Offset(o), Alignment(Align) {
1957     assert((int)Offset >= 0 && "Offset is too large");
1958     Val.MachineCPVal = v;
1959     Offset |= 1 << (sizeof(unsigned)*8-1);
1960   }
1961 public:
1962
1963   bool isMachineConstantPoolEntry() const {
1964     return (int)Offset < 0;
1965   }
1966
1967   Constant *getConstVal() const {
1968     assert(!isMachineConstantPoolEntry() && "Wrong constantpool type");
1969     return Val.ConstVal;
1970   }
1971
1972   MachineConstantPoolValue *getMachineCPVal() const {
1973     assert(isMachineConstantPoolEntry() && "Wrong constantpool type");
1974     return Val.MachineCPVal;
1975   }
1976
1977   int getOffset() const {
1978     return Offset & ~(1 << (sizeof(unsigned)*8-1));
1979   }
1980
1981   // Return the alignment of this constant pool object, which is either 0 (for
1982   // default alignment) or log2 of the desired value.
1983   unsigned getAlignment() const { return Alignment; }
1984
1985   const Type *getType() const;
1986
1987   static bool classof(const ConstantPoolSDNode *) { return true; }
1988   static bool classof(const SDNode *N) {
1989     return N->getOpcode() == ISD::ConstantPool ||
1990            N->getOpcode() == ISD::TargetConstantPool;
1991   }
1992 };
1993
1994 class BasicBlockSDNode : public SDNode {
1995   MachineBasicBlock *MBB;
1996   virtual void ANCHOR();  // Out-of-line virtual method to give class a home.
1997 protected:
1998   friend class SelectionDAG;
1999   explicit BasicBlockSDNode(MachineBasicBlock *mbb)
2000     : SDNode(ISD::BasicBlock, getSDVTList(MVT::Other)), MBB(mbb) {
2001   }
2002 public:
2003
2004   MachineBasicBlock *getBasicBlock() const { return MBB; }
2005
2006   static bool classof(const BasicBlockSDNode *) { return true; }
2007   static bool classof(const SDNode *N) {
2008     return N->getOpcode() == ISD::BasicBlock;
2009   }
2010 };
2011
2012 /// SrcValueSDNode - An SDNode that holds an arbitrary LLVM IR Value. This is
2013 /// used when the SelectionDAG needs to make a simple reference to something
2014 /// in the LLVM IR representation.
2015 ///
2016 /// Note that this is not used for carrying alias information; that is done
2017 /// with MemOperandSDNode, which includes a Value which is required to be a
2018 /// pointer, and several other fields specific to memory references.
2019 ///
2020 class SrcValueSDNode : public SDNode {
2021   const Value *V;
2022   virtual void ANCHOR();  // Out-of-line virtual method to give class a home.
2023 protected:
2024   friend class SelectionDAG;
2025   /// Create a SrcValue for a general value.
2026   explicit SrcValueSDNode(const Value *v)
2027     : SDNode(ISD::SRCVALUE, getSDVTList(MVT::Other)), V(v) {}
2028
2029 public:
2030   /// getValue - return the contained Value.
2031   const Value *getValue() const { return V; }
2032
2033   static bool classof(const SrcValueSDNode *) { return true; }
2034   static bool classof(const SDNode *N) {
2035     return N->getOpcode() == ISD::SRCVALUE;
2036   }
2037 };
2038
2039
2040 /// MemOperandSDNode - An SDNode that holds a MachineMemOperand. This is
2041 /// used to represent a reference to memory after ISD::LOAD
2042 /// and ISD::STORE have been lowered.
2043 ///
2044 class MemOperandSDNode : public SDNode {
2045   virtual void ANCHOR();  // Out-of-line virtual method to give class a home.
2046 protected:
2047   friend class SelectionDAG;
2048   /// Create a MachineMemOperand node
2049   explicit MemOperandSDNode(const MachineMemOperand &mo)
2050     : SDNode(ISD::MEMOPERAND, getSDVTList(MVT::Other)), MO(mo) {}
2051
2052 public:
2053   /// MO - The contained MachineMemOperand.
2054   const MachineMemOperand MO;
2055
2056   static bool classof(const MemOperandSDNode *) { return true; }
2057   static bool classof(const SDNode *N) {
2058     return N->getOpcode() == ISD::MEMOPERAND;
2059   }
2060 };
2061
2062
2063 class RegisterSDNode : public SDNode {
2064   unsigned Reg;
2065   virtual void ANCHOR();  // Out-of-line virtual method to give class a home.
2066 protected:
2067   friend class SelectionDAG;
2068   RegisterSDNode(unsigned reg, MVT VT)
2069     : SDNode(ISD::Register, getSDVTList(VT)), Reg(reg) {
2070   }
2071 public:
2072
2073   unsigned getReg() const { return Reg; }
2074
2075   static bool classof(const RegisterSDNode *) { return true; }
2076   static bool classof(const SDNode *N) {
2077     return N->getOpcode() == ISD::Register;
2078   }
2079 };
2080
2081 class DbgStopPointSDNode : public SDNode {
2082   SDUse Chain;
2083   unsigned Line;
2084   unsigned Column;
2085   const CompileUnitDesc *CU;
2086   virtual void ANCHOR();  // Out-of-line virtual method to give class a home.
2087 protected:
2088   friend class SelectionDAG;
2089   DbgStopPointSDNode(SDValue ch, unsigned l, unsigned c,
2090                      const CompileUnitDesc *cu)
2091     : SDNode(ISD::DBG_STOPPOINT, getSDVTList(MVT::Other)),
2092       Line(l), Column(c), CU(cu) {
2093     Chain = ch;
2094     InitOperands(&Chain, 1);
2095   }
2096 public:
2097   unsigned getLine() const { return Line; }
2098   unsigned getColumn() const { return Column; }
2099   const CompileUnitDesc *getCompileUnit() const { return CU; }
2100
2101   static bool classof(const DbgStopPointSDNode *) { return true; }
2102   static bool classof(const SDNode *N) {
2103     return N->getOpcode() == ISD::DBG_STOPPOINT;
2104   }
2105 };
2106
2107 class LabelSDNode : public SDNode {
2108   SDUse Chain;
2109   unsigned LabelID;
2110   virtual void ANCHOR();  // Out-of-line virtual method to give class a home.
2111 protected:
2112   friend class SelectionDAG;
2113   LabelSDNode(unsigned NodeTy, SDValue ch, unsigned id)
2114     : SDNode(NodeTy, getSDVTList(MVT::Other)), LabelID(id) {
2115     Chain = ch;
2116     InitOperands(&Chain, 1);
2117   }
2118 public:
2119   unsigned getLabelID() const { return LabelID; }
2120
2121   static bool classof(const LabelSDNode *) { return true; }
2122   static bool classof(const SDNode *N) {
2123     return N->getOpcode() == ISD::DBG_LABEL ||
2124            N->getOpcode() == ISD::EH_LABEL;
2125   }
2126 };
2127
2128 class ExternalSymbolSDNode : public SDNode {
2129   const char *Symbol;
2130   virtual void ANCHOR();  // Out-of-line virtual method to give class a home.
2131 protected:
2132   friend class SelectionDAG;
2133   ExternalSymbolSDNode(bool isTarget, const char *Sym, MVT VT)
2134     : SDNode(isTarget ? ISD::TargetExternalSymbol : ISD::ExternalSymbol,
2135              getSDVTList(VT)), Symbol(Sym) {
2136   }
2137 public:
2138
2139   const char *getSymbol() const { return Symbol; }
2140
2141   static bool classof(const ExternalSymbolSDNode *) { return true; }
2142   static bool classof(const SDNode *N) {
2143     return N->getOpcode() == ISD::ExternalSymbol ||
2144            N->getOpcode() == ISD::TargetExternalSymbol;
2145   }
2146 };
2147
2148 class CondCodeSDNode : public SDNode {
2149   ISD::CondCode Condition;
2150   virtual void ANCHOR();  // Out-of-line virtual method to give class a home.
2151 protected:
2152   friend class SelectionDAG;
2153   explicit CondCodeSDNode(ISD::CondCode Cond)
2154     : SDNode(ISD::CONDCODE, getSDVTList(MVT::Other)), Condition(Cond) {
2155   }
2156 public:
2157
2158   ISD::CondCode get() const { return Condition; }
2159
2160   static bool classof(const CondCodeSDNode *) { return true; }
2161   static bool classof(const SDNode *N) {
2162     return N->getOpcode() == ISD::CONDCODE;
2163   }
2164 };
2165
2166 /// CvtRndSatSDNode - NOTE: avoid using this node as this may disappear in the
2167 /// future and most targets don't support it.
2168 class CvtRndSatSDNode : public SDNode {
2169   ISD::CvtCode CvtCode;
2170   virtual void ANCHOR();  // Out-of-line virtual method to give class a home.
2171 protected:
2172   friend class SelectionDAG;
2173   explicit CvtRndSatSDNode(MVT VT, const SDValue *Ops, unsigned NumOps,
2174                            ISD::CvtCode Code)
2175     : SDNode(ISD::CONVERT_RNDSAT, getSDVTList(VT), Ops, NumOps), CvtCode(Code) {
2176     assert(NumOps == 5 && "wrong number of operations");
2177   }
2178 public:
2179   ISD::CvtCode getCvtCode() const { return CvtCode; }
2180
2181   static bool classof(const CvtRndSatSDNode *) { return true; }
2182   static bool classof(const SDNode *N) {
2183     return N->getOpcode() == ISD::CONVERT_RNDSAT;
2184   }
2185 };
2186
2187 namespace ISD {
2188   struct ArgFlagsTy {
2189   private:
2190     static const uint64_t NoFlagSet      = 0ULL;
2191     static const uint64_t ZExt           = 1ULL<<0;  ///< Zero extended
2192     static const uint64_t ZExtOffs       = 0;
2193     static const uint64_t SExt           = 1ULL<<1;  ///< Sign extended
2194     static const uint64_t SExtOffs       = 1;
2195     static const uint64_t InReg          = 1ULL<<2;  ///< Passed in register
2196     static const uint64_t InRegOffs      = 2;
2197     static const uint64_t SRet           = 1ULL<<3;  ///< Hidden struct-ret ptr
2198     static const uint64_t SRetOffs       = 3;
2199     static const uint64_t ByVal          = 1ULL<<4;  ///< Struct passed by value
2200     static const uint64_t ByValOffs      = 4;
2201     static const uint64_t Nest           = 1ULL<<5;  ///< Nested fn static chain
2202     static const uint64_t NestOffs       = 5;
2203     static const uint64_t ByValAlign     = 0xFULL << 6; //< Struct alignment
2204     static const uint64_t ByValAlignOffs = 6;
2205     static const uint64_t Split          = 1ULL << 10;
2206     static const uint64_t SplitOffs      = 10;
2207     static const uint64_t OrigAlign      = 0x1FULL<<27;
2208     static const uint64_t OrigAlignOffs  = 27;
2209     static const uint64_t ByValSize      = 0xffffffffULL << 32; //< Struct size
2210     static const uint64_t ByValSizeOffs  = 32;
2211
2212     static const uint64_t One            = 1ULL; //< 1 of this type, for shifts
2213
2214     uint64_t Flags;
2215   public:
2216     ArgFlagsTy() : Flags(0) { }
2217
2218     bool isZExt()   const { return Flags & ZExt; }
2219     void setZExt()  { Flags |= One << ZExtOffs; }
2220
2221     bool isSExt()   const { return Flags & SExt; }
2222     void setSExt()  { Flags |= One << SExtOffs; }
2223
2224     bool isInReg()  const { return Flags & InReg; }
2225     void setInReg() { Flags |= One << InRegOffs; }
2226
2227     bool isSRet()   const { return Flags & SRet; }
2228     void setSRet()  { Flags |= One << SRetOffs; }
2229
2230     bool isByVal()  const { return Flags & ByVal; }
2231     void setByVal() { Flags |= One << ByValOffs; }
2232
2233     bool isNest()   const { return Flags & Nest; }
2234     void setNest()  { Flags |= One << NestOffs; }
2235
2236     unsigned getByValAlign() const {
2237       return (unsigned)
2238         ((One << ((Flags & ByValAlign) >> ByValAlignOffs)) / 2);
2239     }
2240     void setByValAlign(unsigned A) {
2241       Flags = (Flags & ~ByValAlign) |
2242         (uint64_t(Log2_32(A) + 1) << ByValAlignOffs);
2243     }
2244
2245     bool isSplit()   const { return Flags & Split; }
2246     void setSplit()  { Flags |= One << SplitOffs; }
2247
2248     unsigned getOrigAlign() const {
2249       return (unsigned)
2250         ((One << ((Flags & OrigAlign) >> OrigAlignOffs)) / 2);
2251     }
2252     void setOrigAlign(unsigned A) {
2253       Flags = (Flags & ~OrigAlign) |
2254         (uint64_t(Log2_32(A) + 1) << OrigAlignOffs);
2255     }
2256
2257     unsigned getByValSize() const {
2258       return (unsigned)((Flags & ByValSize) >> ByValSizeOffs);
2259     }
2260     void setByValSize(unsigned S) {
2261       Flags = (Flags & ~ByValSize) | (uint64_t(S) << ByValSizeOffs);
2262     }
2263
2264     /// getArgFlagsString - Returns the flags as a string, eg: "zext align:4".
2265     std::string getArgFlagsString();
2266
2267     /// getRawBits - Represent the flags as a bunch of bits.
2268     uint64_t getRawBits() const { return Flags; }
2269   };
2270 }
2271
2272 /// ARG_FLAGSSDNode - Leaf node holding parameter flags.
2273 class ARG_FLAGSSDNode : public SDNode {
2274   ISD::ArgFlagsTy TheFlags;
2275   virtual void ANCHOR();  // Out-of-line virtual method to give class a home.
2276 protected:
2277   friend class SelectionDAG;
2278   explicit ARG_FLAGSSDNode(ISD::ArgFlagsTy Flags)
2279     : SDNode(ISD::ARG_FLAGS, getSDVTList(MVT::Other)), TheFlags(Flags) {
2280   }
2281 public:
2282   ISD::ArgFlagsTy getArgFlags() const { return TheFlags; }
2283
2284   static bool classof(const ARG_FLAGSSDNode *) { return true; }
2285   static bool classof(const SDNode *N) {
2286     return N->getOpcode() == ISD::ARG_FLAGS;
2287   }
2288 };
2289
2290 /// CallSDNode - Node for calls -- ISD::CALL.
2291 class CallSDNode : public SDNode {
2292   unsigned CallingConv;
2293   bool IsVarArg;
2294   bool IsTailCall;
2295   // We might eventually want a full-blown Attributes for the result; that
2296   // will expand the size of the representation.  At the moment we only
2297   // need Inreg.
2298   bool Inreg;
2299   virtual void ANCHOR();  // Out-of-line virtual method to give class a home.
2300 protected:
2301   friend class SelectionDAG;
2302   CallSDNode(unsigned cc, bool isvararg, bool istailcall, bool isinreg,
2303              SDVTList VTs, const SDValue *Operands, unsigned numOperands)
2304     : SDNode(ISD::CALL, VTs, Operands, numOperands),
2305       CallingConv(cc), IsVarArg(isvararg), IsTailCall(istailcall),
2306       Inreg(isinreg) {}
2307 public:
2308   unsigned getCallingConv() const { return CallingConv; }
2309   unsigned isVarArg() const { return IsVarArg; }
2310   unsigned isTailCall() const { return IsTailCall; }
2311   unsigned isInreg() const { return Inreg; }
2312
2313   /// Set this call to not be marked as a tail call. Normally setter
2314   /// methods in SDNodes are unsafe because it breaks the CSE map,
2315   /// but we don't include the tail call flag for calls so it's ok
2316   /// in this case.
2317   void setNotTailCall() { IsTailCall = false; }
2318
2319   SDValue getChain() const { return getOperand(0); }
2320   SDValue getCallee() const { return getOperand(1); }
2321
2322   unsigned getNumArgs() const { return (getNumOperands() - 2) / 2; }
2323   SDValue getArg(unsigned i) const { return getOperand(2+2*i); }
2324   SDValue getArgFlagsVal(unsigned i) const {
2325     return getOperand(3+2*i);
2326   }
2327   ISD::ArgFlagsTy getArgFlags(unsigned i) const {
2328     return cast<ARG_FLAGSSDNode>(getArgFlagsVal(i).getNode())->getArgFlags();
2329   }
2330
2331   unsigned getNumRetVals() const { return getNumValues() - 1; }
2332   MVT getRetValType(unsigned i) const { return getValueType(i); }
2333
2334   static bool classof(const CallSDNode *) { return true; }
2335   static bool classof(const SDNode *N) {
2336     return N->getOpcode() == ISD::CALL;
2337   }
2338 };
2339
2340 /// VTSDNode - This class is used to represent MVT's, which are used
2341 /// to parameterize some operations.
2342 class VTSDNode : public SDNode {
2343   MVT ValueType;
2344   virtual void ANCHOR();  // Out-of-line virtual method to give class a home.
2345 protected:
2346   friend class SelectionDAG;
2347   explicit VTSDNode(MVT VT)
2348     : SDNode(ISD::VALUETYPE, getSDVTList(MVT::Other)), ValueType(VT) {
2349   }
2350 public:
2351
2352   MVT getVT() const { return ValueType; }
2353
2354   static bool classof(const VTSDNode *) { return true; }
2355   static bool classof(const SDNode *N) {
2356     return N->getOpcode() == ISD::VALUETYPE;
2357   }
2358 };
2359
2360 /// LSBaseSDNode - Base class for LoadSDNode and StoreSDNode
2361 ///
2362 class LSBaseSDNode : public MemSDNode {
2363 protected:
2364   //! Operand array for load and store
2365   /*!
2366     \note Moving this array to the base class captures more
2367     common functionality shared between LoadSDNode and
2368     StoreSDNode
2369    */
2370   SDUse Ops[4];
2371 public:
2372   LSBaseSDNode(ISD::NodeType NodeTy, SDValue *Operands, unsigned numOperands,
2373                SDVTList VTs, ISD::MemIndexedMode AM, MVT VT,
2374                const Value *SV, int SVO, unsigned Align, bool Vol)
2375     : MemSDNode(NodeTy, VTs, VT, SV, SVO, Align, Vol) {
2376     SubclassData = AM;
2377     for (unsigned i = 0; i != numOperands; ++i)
2378       Ops[i] = Operands[i];
2379     InitOperands(Ops, numOperands);
2380     assert(Align != 0 && "Loads and stores should have non-zero aligment");
2381     assert((getOffset().getOpcode() == ISD::UNDEF || isIndexed()) &&
2382            "Only indexed loads and stores have a non-undef offset operand");
2383   }
2384
2385   const SDValue &getOffset() const {
2386     return getOperand(getOpcode() == ISD::LOAD ? 2 : 3);
2387   }
2388
2389   /// getAddressingMode - Return the addressing mode for this load or store:
2390   /// unindexed, pre-inc, pre-dec, post-inc, or post-dec.
2391   ISD::MemIndexedMode getAddressingMode() const {
2392     return ISD::MemIndexedMode(SubclassData & 7);
2393   }
2394
2395   /// isIndexed - Return true if this is a pre/post inc/dec load/store.
2396   bool isIndexed() const { return getAddressingMode() != ISD::UNINDEXED; }
2397
2398   /// isUnindexed - Return true if this is NOT a pre/post inc/dec load/store.
2399   bool isUnindexed() const { return getAddressingMode() == ISD::UNINDEXED; }
2400
2401   static bool classof(const LSBaseSDNode *) { return true; }
2402   static bool classof(const SDNode *N) {
2403     return N->getOpcode() == ISD::LOAD ||
2404            N->getOpcode() == ISD::STORE;
2405   }
2406 };
2407
2408 /// LoadSDNode - This class is used to represent ISD::LOAD nodes.
2409 ///
2410 class LoadSDNode : public LSBaseSDNode {
2411   virtual void ANCHOR();  // Out-of-line virtual method to give class a home.
2412 protected:
2413   friend class SelectionDAG;
2414   LoadSDNode(SDValue *ChainPtrOff, SDVTList VTs,
2415              ISD::MemIndexedMode AM, ISD::LoadExtType ETy, MVT LVT,
2416              const Value *SV, int O=0, unsigned Align=0, bool Vol=false)
2417     : LSBaseSDNode(ISD::LOAD, ChainPtrOff, 3,
2418                    VTs, AM, LVT, SV, O, Align, Vol) {
2419     SubclassData |= (unsigned short)ETy << 3;
2420   }
2421 public:
2422
2423   /// getExtensionType - Return whether this is a plain node,
2424   /// or one of the varieties of value-extending loads.
2425   ISD::LoadExtType getExtensionType() const {
2426     return ISD::LoadExtType((SubclassData >> 3) & 3);
2427   }
2428
2429   const SDValue &getBasePtr() const { return getOperand(1); }
2430   const SDValue &getOffset() const { return getOperand(2); }
2431
2432   static bool classof(const LoadSDNode *) { return true; }
2433   static bool classof(const SDNode *N) {
2434     return N->getOpcode() == ISD::LOAD;
2435   }
2436 };
2437
2438 /// StoreSDNode - This class is used to represent ISD::STORE nodes.
2439 ///
2440 class StoreSDNode : public LSBaseSDNode {
2441   virtual void ANCHOR();  // Out-of-line virtual method to give class a home.
2442 protected:
2443   friend class SelectionDAG;
2444   StoreSDNode(SDValue *ChainValuePtrOff, SDVTList VTs,
2445               ISD::MemIndexedMode AM, bool isTrunc, MVT SVT,
2446               const Value *SV, int O=0, unsigned Align=0, bool Vol=false)
2447     : LSBaseSDNode(ISD::STORE, ChainValuePtrOff, 4,
2448                    VTs, AM, SVT, SV, O, Align, Vol) {
2449     SubclassData |= (unsigned short)isTrunc << 3;
2450   }
2451 public:
2452
2453   /// isTruncatingStore - Return true if the op does a truncation before store.
2454   /// For integers this is the same as doing a TRUNCATE and storing the result.
2455   /// For floats, it is the same as doing an FP_ROUND and storing the result.
2456   bool isTruncatingStore() const { return (SubclassData >> 3) & 1; }
2457
2458   const SDValue &getValue() const { return getOperand(1); }
2459   const SDValue &getBasePtr() const { return getOperand(2); }
2460   const SDValue &getOffset() const { return getOperand(3); }
2461
2462   static bool classof(const StoreSDNode *) { return true; }
2463   static bool classof(const SDNode *N) {
2464     return N->getOpcode() == ISD::STORE;
2465   }
2466 };
2467
2468
2469 class SDNodeIterator : public forward_iterator<SDNode, ptrdiff_t> {
2470   SDNode *Node;
2471   unsigned Operand;
2472
2473   SDNodeIterator(SDNode *N, unsigned Op) : Node(N), Operand(Op) {}
2474 public:
2475   bool operator==(const SDNodeIterator& x) const {
2476     return Operand == x.Operand;
2477   }
2478   bool operator!=(const SDNodeIterator& x) const { return !operator==(x); }
2479
2480   const SDNodeIterator &operator=(const SDNodeIterator &I) {
2481     assert(I.Node == Node && "Cannot assign iterators to two different nodes!");
2482     Operand = I.Operand;
2483     return *this;
2484   }
2485
2486   pointer operator*() const {
2487     return Node->getOperand(Operand).getNode();
2488   }
2489   pointer operator->() const { return operator*(); }
2490
2491   SDNodeIterator& operator++() {                // Preincrement
2492     ++Operand;
2493     return *this;
2494   }
2495   SDNodeIterator operator++(int) { // Postincrement
2496     SDNodeIterator tmp = *this; ++*this; return tmp;
2497   }
2498
2499   static SDNodeIterator begin(SDNode *N) { return SDNodeIterator(N, 0); }
2500   static SDNodeIterator end  (SDNode *N) {
2501     return SDNodeIterator(N, N->getNumOperands());
2502   }
2503
2504   unsigned getOperand() const { return Operand; }
2505   const SDNode *getNode() const { return Node; }
2506 };
2507
2508 template <> struct GraphTraits<SDNode*> {
2509   typedef SDNode NodeType;
2510   typedef SDNodeIterator ChildIteratorType;
2511   static inline NodeType *getEntryNode(SDNode *N) { return N; }
2512   static inline ChildIteratorType child_begin(NodeType *N) {
2513     return SDNodeIterator::begin(N);
2514   }
2515   static inline ChildIteratorType child_end(NodeType *N) {
2516     return SDNodeIterator::end(N);
2517   }
2518 };
2519
2520 /// LargestSDNode - The largest SDNode class.
2521 ///
2522 typedef LoadSDNode LargestSDNode;
2523
2524 /// MostAlignedSDNode - The SDNode class with the greatest alignment
2525 /// requirement.
2526 ///
2527 typedef ARG_FLAGSSDNode MostAlignedSDNode;
2528
2529 namespace ISD {
2530   /// isNormalLoad - Returns true if the specified node is a non-extending
2531   /// and unindexed load.
2532   inline bool isNormalLoad(const SDNode *N) {
2533     const LoadSDNode *Ld = dyn_cast<LoadSDNode>(N);
2534     return Ld && Ld->getExtensionType() == ISD::NON_EXTLOAD &&
2535       Ld->getAddressingMode() == ISD::UNINDEXED;
2536   }
2537
2538   /// isNON_EXTLoad - Returns true if the specified node is a non-extending
2539   /// load.
2540   inline bool isNON_EXTLoad(const SDNode *N) {
2541     return isa<LoadSDNode>(N) &&
2542       cast<LoadSDNode>(N)->getExtensionType() == ISD::NON_EXTLOAD;
2543   }
2544
2545   /// isEXTLoad - Returns true if the specified node is a EXTLOAD.
2546   ///
2547   inline bool isEXTLoad(const SDNode *N) {
2548     return isa<LoadSDNode>(N) &&
2549       cast<LoadSDNode>(N)->getExtensionType() == ISD::EXTLOAD;
2550   }
2551
2552   /// isSEXTLoad - Returns true if the specified node is a SEXTLOAD.
2553   ///
2554   inline bool isSEXTLoad(const SDNode *N) {
2555     return isa<LoadSDNode>(N) &&
2556       cast<LoadSDNode>(N)->getExtensionType() == ISD::SEXTLOAD;
2557   }
2558
2559   /// isZEXTLoad - Returns true if the specified node is a ZEXTLOAD.
2560   ///
2561   inline bool isZEXTLoad(const SDNode *N) {
2562     return isa<LoadSDNode>(N) &&
2563       cast<LoadSDNode>(N)->getExtensionType() == ISD::ZEXTLOAD;
2564   }
2565
2566   /// isUNINDEXEDLoad - Returns true if the specified node is an unindexed load.
2567   ///
2568   inline bool isUNINDEXEDLoad(const SDNode *N) {
2569     return isa<LoadSDNode>(N) &&
2570       cast<LoadSDNode>(N)->getAddressingMode() == ISD::UNINDEXED;
2571   }
2572
2573   /// isNormalStore - Returns true if the specified node is a non-truncating
2574   /// and unindexed store.
2575   inline bool isNormalStore(const SDNode *N) {
2576     const StoreSDNode *St = dyn_cast<StoreSDNode>(N);
2577     return St && !St->isTruncatingStore() &&
2578       St->getAddressingMode() == ISD::UNINDEXED;
2579   }
2580
2581   /// isNON_TRUNCStore - Returns true if the specified node is a non-truncating
2582   /// store.
2583   inline bool isNON_TRUNCStore(const SDNode *N) {
2584     return isa<StoreSDNode>(N) && !cast<StoreSDNode>(N)->isTruncatingStore();
2585   }
2586
2587   /// isTRUNCStore - Returns true if the specified node is a truncating
2588   /// store.
2589   inline bool isTRUNCStore(const SDNode *N) {
2590     return isa<StoreSDNode>(N) && cast<StoreSDNode>(N)->isTruncatingStore();
2591   }
2592
2593   /// isUNINDEXEDStore - Returns true if the specified node is an
2594   /// unindexed store.
2595   inline bool isUNINDEXEDStore(const SDNode *N) {
2596     return isa<StoreSDNode>(N) &&
2597       cast<StoreSDNode>(N)->getAddressingMode() == ISD::UNINDEXED;
2598   }
2599 }
2600
2601
2602 } // end llvm namespace
2603
2604 #endif