LLVM API Documentation

SelectionDAGNodes.h

Go to the documentation of this file.
00001 //===-- llvm/CodeGen/SelectionDAGNodes.h - SelectionDAG Nodes ---*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file declares the SDNode class and derived classes, which are used to
00011 // represent the nodes and operations present in a SelectionDAG.  These nodes
00012 // and operations are machine code level operations, with some similarities to
00013 // the GCC RTL representation.
00014 //
00015 // Clients should include the SelectionDAG.h file instead of this file directly.
00016 //
00017 //===----------------------------------------------------------------------===//
00018 
00019 #ifndef LLVM_CODEGEN_SELECTIONDAGNODES_H
00020 #define LLVM_CODEGEN_SELECTIONDAGNODES_H
00021 
00022 #include "llvm/CodeGen/ValueTypes.h"
00023 #include "llvm/Value.h"
00024 #include "llvm/ADT/GraphTraits.h"
00025 #include "llvm/ADT/iterator"
00026 #include "llvm/Support/DataTypes.h"
00027 #include <cassert>
00028 #include <vector>
00029 
00030 namespace llvm {
00031 
00032 class SelectionDAG;
00033 class GlobalValue;
00034 class MachineBasicBlock;
00035 class SDNode;
00036 template <typename T> struct simplify_type;
00037 template <typename T> struct ilist_traits;
00038 template<typename NodeTy, typename Traits> class iplist;
00039 template<typename NodeTy> class ilist_iterator;
00040 
00041 /// ISD namespace - This namespace contains an enum which represents all of the
00042 /// SelectionDAG node types and value types.
00043 ///
00044 namespace ISD {
00045   //===--------------------------------------------------------------------===//
00046   /// ISD::NodeType enum - This enum defines all of the operators valid in a
00047   /// SelectionDAG.
00048   ///
00049   enum NodeType {
00050     // EntryToken - This is the marker used to indicate the start of the region.
00051     EntryToken,
00052 
00053     // Token factor - This node takes multiple tokens as input and produces a
00054     // single token result.  This is used to represent the fact that the operand
00055     // operators are independent of each other.
00056     TokenFactor,
00057     
00058     // AssertSext, AssertZext - These nodes record if a register contains a 
00059     // value that has already been zero or sign extended from a narrower type.  
00060     // These nodes take two operands.  The first is the node that has already 
00061     // been extended, and the second is a value type node indicating the width
00062     // of the extension
00063     AssertSext, AssertZext,
00064 
00065     // Various leaf nodes.
00066     STRING, BasicBlock, VALUETYPE, CONDCODE, Register,
00067     Constant, ConstantFP,
00068     GlobalAddress, FrameIndex, ConstantPool, ExternalSymbol,
00069 
00070     // TargetConstant* - Like Constant*, but the DAG does not do any folding or
00071     // simplification of the constant.
00072     TargetConstant,
00073     TargetConstantFP,
00074     
00075     // TargetGlobalAddress - Like GlobalAddress, but the DAG does no folding or
00076     // anything else with this node, and this is valid in the target-specific
00077     // dag, turning into a GlobalAddress operand.
00078     TargetGlobalAddress,
00079     TargetFrameIndex,
00080     TargetConstantPool,
00081     TargetExternalSymbol,
00082     
00083     /// RESULT = INTRINSIC_WO_CHAIN(INTRINSICID, arg1, arg2, ...)
00084     /// This node represents a target intrinsic function with no side effects.
00085     /// The first operand is the ID number of the intrinsic from the
00086     /// llvm::Intrinsic namespace.  The operands to the intrinsic follow.  The
00087     /// node has returns the result of the intrinsic.
00088     INTRINSIC_WO_CHAIN,
00089     
00090     /// RESULT,OUTCHAIN = INTRINSIC_W_CHAIN(INCHAIN, INTRINSICID, arg1, ...)
00091     /// This node represents a target intrinsic function with side effects that
00092     /// returns a result.  The first operand is a chain pointer.  The second is
00093     /// the ID number of the intrinsic from the llvm::Intrinsic namespace.  The
00094     /// operands to the intrinsic follow.  The node has two results, the result
00095     /// of the intrinsic and an output chain.
00096     INTRINSIC_W_CHAIN,
00097 
00098     /// OUTCHAIN = INTRINSIC_VOID(INCHAIN, INTRINSICID, arg1, arg2, ...)
00099     /// This node represents a target intrinsic function with side effects that
00100     /// does not return a result.  The first operand is a chain pointer.  The
00101     /// second is the ID number of the intrinsic from the llvm::Intrinsic
00102     /// namespace.  The operands to the intrinsic follow.
00103     INTRINSIC_VOID,
00104     
00105     // CopyToReg - This node has three operands: a chain, a register number to
00106     // set to this value, and a value.  
00107     CopyToReg,
00108 
00109     // CopyFromReg - This node indicates that the input value is a virtual or
00110     // physical register that is defined outside of the scope of this
00111     // SelectionDAG.  The register is available from the RegSDNode object.
00112     CopyFromReg,
00113 
00114     // UNDEF - An undefined node
00115     UNDEF,
00116     
00117     /// FORMAL_ARGUMENTS(CC#, ISVARARG) - This node represents the formal
00118     /// arguments for a function.  CC# is a Constant value indicating the
00119     /// calling convention of the function, and ISVARARG is a flag that
00120     /// indicates whether the function is varargs or not.  This node has one
00121     /// result value for each incoming argument, and is typically custom
00122     /// legalized.
00123     FORMAL_ARGUMENTS,
00124 
00125     // EXTRACT_ELEMENT - This is used to get the first or second (determined by
00126     // a Constant, which is required to be operand #1), element of the aggregate
00127     // value specified as operand #0.  This is only for use before legalization,
00128     // for values that will be broken into multiple registers.
00129     EXTRACT_ELEMENT,
00130 
00131     // BUILD_PAIR - This is the opposite of EXTRACT_ELEMENT in some ways.  Given
00132     // two values of the same integer value type, this produces a value twice as
00133     // big.  Like EXTRACT_ELEMENT, this can only be used before legalization.
00134     BUILD_PAIR,
00135     
00136     // MERGE_VALUES - This node takes multiple discrete operands and returns
00137     // them all as its individual results.  This nodes has exactly the same
00138     // number of inputs and outputs, and is only valid before legalization.
00139     // This node is useful for some pieces of the code generator that want to
00140     // think about a single node with multiple results, not multiple nodes.
00141     MERGE_VALUES,
00142 
00143     // Simple integer binary arithmetic operators.
00144     ADD, SUB, MUL, SDIV, UDIV, SREM, UREM,
00145     
00146     // Carry-setting nodes for multiple precision addition and subtraction.
00147     // These nodes take two operands of the same value type, and produce two
00148     // results.  The first result is the normal add or sub result, the second
00149     // result is the carry flag result.
00150     ADDC, SUBC,
00151     
00152     // Carry-using nodes for multiple precision addition and subtraction.  These
00153     // nodes take three operands: The first two are the normal lhs and rhs to
00154     // the add or sub, and the third is the input carry flag.  These nodes
00155     // produce two results; the normal result of the add or sub, and the output
00156     // carry flag.  These nodes both read and write a carry flag to allow them
00157     // to them to be chained together for add and sub of arbitrarily large
00158     // values.
00159     ADDE, SUBE,
00160     
00161     // Simple binary floating point operators.
00162     FADD, FSUB, FMUL, FDIV, FREM,
00163 
00164     // FCOPYSIGN(X, Y) - Return the value of X with the sign of Y.  NOTE: This
00165     // DAG node does not require that X and Y have the same type, just that they
00166     // are both floating point.  X and the result must have the same type.
00167     // FCOPYSIGN(f32, f64) is allowed.
00168     FCOPYSIGN,
00169 
00170     /// VBUILD_VECTOR(ELT1, ELT2, ELT3, ELT4,...,  COUNT,TYPE) - Return a vector
00171     /// with the specified, possibly variable, elements.  The number of elements
00172     /// is required to be a power of two.
00173     VBUILD_VECTOR,
00174 
00175     /// BUILD_VECTOR(ELT1, ELT2, ELT3, ELT4,...) - Return a vector
00176     /// with the specified, possibly variable, elements.  The number of elements
00177     /// is required to be a power of two.
00178     BUILD_VECTOR,
00179     
00180     /// VINSERT_VECTOR_ELT(VECTOR, VAL, IDX,  COUNT,TYPE) - Given a vector
00181     /// VECTOR, an element ELEMENT, and a (potentially variable) index IDX,
00182     /// return an vector with the specified element of VECTOR replaced with VAL.
00183     /// COUNT and TYPE specify the type of vector, as is standard for V* nodes.
00184     VINSERT_VECTOR_ELT,
00185     
00186     /// INSERT_VECTOR_ELT(VECTOR, VAL, IDX) - Returns VECTOR (a legal packed
00187     /// type) with the element at IDX replaced with VAL.
00188     INSERT_VECTOR_ELT,
00189 
00190     /// VEXTRACT_VECTOR_ELT(VECTOR, IDX) - Returns a single element from VECTOR
00191     /// (an MVT::Vector value) identified by the (potentially variable) element
00192     /// number IDX.
00193     VEXTRACT_VECTOR_ELT,
00194     
00195     /// EXTRACT_VECTOR_ELT(VECTOR, IDX) - Returns a single element from VECTOR
00196     /// (a legal packed type vector) identified by the (potentially variable)
00197     /// element number IDX.
00198     EXTRACT_VECTOR_ELT,
00199     
00200     /// VVECTOR_SHUFFLE(VEC1, VEC2, SHUFFLEVEC, COUNT,TYPE) - Returns a vector,
00201     /// of the same type as VEC1/VEC2.  SHUFFLEVEC is a VBUILD_VECTOR of
00202     /// constant int values that indicate which value each result element will
00203     /// get.  The elements of VEC1/VEC2 are enumerated in order.  This is quite
00204     /// similar to the Altivec 'vperm' instruction, except that the indices must
00205     /// be constants and are in terms of the element size of VEC1/VEC2, not in
00206     /// terms of bytes.
00207     VVECTOR_SHUFFLE,
00208 
00209     /// VECTOR_SHUFFLE(VEC1, VEC2, SHUFFLEVEC) - Returns a vector, of the same
00210     /// type as VEC1/VEC2.  SHUFFLEVEC is a BUILD_VECTOR of constant int values
00211     /// (regardless of whether its datatype is legal or not) that indicate
00212     /// which value each result element will get.  The elements of VEC1/VEC2 are
00213     /// enumerated in order.  This is quite similar to the Altivec 'vperm'
00214     /// instruction, except that the indices must be constants and are in terms
00215     /// of the element size of VEC1/VEC2, not in terms of bytes.
00216     VECTOR_SHUFFLE,
00217     
00218     /// X = VBIT_CONVERT(Y)  and X = VBIT_CONVERT(Y, COUNT,TYPE) - This node
00219     /// represents a conversion from or to an ISD::Vector type.
00220     ///
00221     /// This is lowered to a BIT_CONVERT of the appropriate input/output types.
00222     /// The input and output are required to have the same size and at least one
00223     /// is required to be a vector (if neither is a vector, just use
00224     /// BIT_CONVERT).
00225     ///
00226     /// If the result is a vector, this takes three operands (like any other
00227     /// vector producer) which indicate the size and type of the vector result.
00228     /// Otherwise it takes one input.
00229     VBIT_CONVERT,
00230     
00231     /// BINOP(LHS, RHS,  COUNT,TYPE)
00232     /// Simple abstract vector operators.  Unlike the integer and floating point
00233     /// binary operators, these nodes also take two additional operands:
00234     /// a constant element count, and a value type node indicating the type of
00235     /// the elements.  The order is count, type, op0, op1.  All vector opcodes,
00236     /// including VLOAD and VConstant must currently have count and type as
00237     /// their last two operands.
00238     VADD, VSUB, VMUL, VSDIV, VUDIV,
00239     VAND, VOR, VXOR,
00240     
00241     /// VSELECT(COND,LHS,RHS,  COUNT,TYPE) - Select for MVT::Vector values.
00242     /// COND is a boolean value.  This node return LHS if COND is true, RHS if
00243     /// COND is false.
00244     VSELECT,
00245     
00246     /// SCALAR_TO_VECTOR(VAL) - This represents the operation of loading a
00247     /// scalar value into the low element of the resultant vector type.  The top
00248     /// elements of the vector are undefined.
00249     SCALAR_TO_VECTOR,
00250     
00251     // MULHU/MULHS - Multiply high - Multiply two integers of type iN, producing
00252     // an unsigned/signed value of type i[2*n], then return the top part.
00253     MULHU, MULHS,
00254 
00255     // Bitwise operators - logical and, logical or, logical xor, shift left,
00256     // shift right algebraic (shift in sign bits), shift right logical (shift in
00257     // zeroes), rotate left, rotate right, and byteswap.
00258     AND, OR, XOR, SHL, SRA, SRL, ROTL, ROTR, BSWAP,
00259 
00260     // Counting operators
00261     CTTZ, CTLZ, CTPOP,
00262 
00263     // Select(COND, TRUEVAL, FALSEVAL)
00264     SELECT, 
00265     
00266     // Select with condition operator - This selects between a true value and 
00267     // a false value (ops #2 and #3) based on the boolean result of comparing
00268     // the lhs and rhs (ops #0 and #1) of a conditional expression with the 
00269     // condition code in op #4, a CondCodeSDNode.
00270     SELECT_CC,
00271 
00272     // SetCC operator - This evaluates to a boolean (i1) true value if the
00273     // condition is true.  The operands to this are the left and right operands
00274     // to compare (ops #0, and #1) and the condition code to compare them with
00275     // (op #2) as a CondCodeSDNode.
00276     SETCC,
00277 
00278     // SHL_PARTS/SRA_PARTS/SRL_PARTS - These operators are used for expanded
00279     // integer shift operations, just like ADD/SUB_PARTS.  The operation
00280     // ordering is:
00281     //       [Lo,Hi] = op [LoLHS,HiLHS], Amt
00282     SHL_PARTS, SRA_PARTS, SRL_PARTS,
00283 
00284     // Conversion operators.  These are all single input single output
00285     // operations.  For all of these, the result type must be strictly
00286     // wider or narrower (depending on the operation) than the source
00287     // type.
00288 
00289     // SIGN_EXTEND - Used for integer types, replicating the sign bit
00290     // into new bits.
00291     SIGN_EXTEND,
00292 
00293     // ZERO_EXTEND - Used for integer types, zeroing the new bits.
00294     ZERO_EXTEND,
00295 
00296     // ANY_EXTEND - Used for integer types.  The high bits are undefined.
00297     ANY_EXTEND,
00298     
00299     // TRUNCATE - Completely drop the high bits.
00300     TRUNCATE,
00301 
00302     // [SU]INT_TO_FP - These operators convert integers (whose interpreted sign
00303     // depends on the first letter) to floating point.
00304     SINT_TO_FP,
00305     UINT_TO_FP,
00306 
00307     // SIGN_EXTEND_INREG - This operator atomically performs a SHL/SRA pair to
00308     // sign extend a small value in a large integer register (e.g. sign
00309     // extending the low 8 bits of a 32-bit register to fill the top 24 bits
00310     // with the 7th bit).  The size of the smaller type is indicated by the 1th
00311     // operand, a ValueType node.
00312     SIGN_EXTEND_INREG,
00313 
00314     // FP_TO_[US]INT - Convert a floating point value to a signed or unsigned
00315     // integer.
00316     FP_TO_SINT,
00317     FP_TO_UINT,
00318 
00319     // FP_ROUND - Perform a rounding operation from the current
00320     // precision down to the specified precision (currently always 64->32).
00321     FP_ROUND,
00322 
00323     // FP_ROUND_INREG - This operator takes a floating point register, and
00324     // rounds it to a floating point value.  It then promotes it and returns it
00325     // in a register of the same size.  This operation effectively just discards
00326     // excess precision.  The type to round down to is specified by the 1th
00327     // operation, a VTSDNode (currently always 64->32->64).
00328     FP_ROUND_INREG,
00329 
00330     // FP_EXTEND - Extend a smaller FP type into a larger FP type.
00331     FP_EXTEND,
00332 
00333     // BIT_CONVERT - Theis operator converts between integer and FP values, as
00334     // if one was stored to memory as integer and the other was loaded from the
00335     // same address (or equivalently for vector format conversions, etc).  The 
00336     // source and result are required to have the same bit size (e.g. 
00337     // f32 <-> i32).  This can also be used for int-to-int or fp-to-fp 
00338     // conversions, but that is a noop, deleted by getNode().
00339     BIT_CONVERT,
00340     
00341     // FNEG, FABS, FSQRT, FSIN, FCOS - Perform unary floating point negation,
00342     // absolute value, square root, sine and cosine operations.
00343     FNEG, FABS, FSQRT, FSIN, FCOS,
00344     
00345     // Other operators.  LOAD and STORE have token chains as their first
00346     // operand, then the same operands as an LLVM load/store instruction, then a
00347     // SRCVALUE node that provides alias analysis information.
00348     LOAD, STORE,
00349     
00350     // Abstract vector version of LOAD.  VLOAD has a constant element count as
00351     // the first operand, followed by a value type node indicating the type of
00352     // the elements, a token chain, a pointer operand, and a SRCVALUE node.
00353     VLOAD,
00354 
00355     // EXTLOAD, SEXTLOAD, ZEXTLOAD - These three operators all load a value from
00356     // memory and extend them to a larger value (e.g. load a byte into a word
00357     // register).  All three of these have four operands, a token chain, a
00358     // pointer to load from, a SRCVALUE for alias analysis, and a VALUETYPE node
00359     // indicating the type to load.
00360     //
00361     // SEXTLOAD loads the integer operand and sign extends it to a larger
00362     //          integer result type.
00363     // ZEXTLOAD loads the integer operand and zero extends it to a larger
00364     //          integer result type.
00365     // EXTLOAD  is used for three things: floating point extending loads, 
00366     //          integer extending loads [the top bits are undefined], and vector
00367     //          extending loads [load into low elt].
00368     EXTLOAD, SEXTLOAD, ZEXTLOAD,
00369 
00370     // TRUNCSTORE - This operators truncates (for integer) or rounds (for FP) a
00371     // value and stores it to memory in one operation.  This can be used for
00372     // either integer or floating point operands.  The first four operands of
00373     // this are the same as a standard store.  The fifth is the ValueType to
00374     // store it as (which will be smaller than the source value).
00375     TRUNCSTORE,
00376 
00377     // DYNAMIC_STACKALLOC - Allocate some number of bytes on the stack aligned
00378     // to a specified boundary.  The first operand is the token chain, the
00379     // second is the number of bytes to allocate, and the third is the alignment
00380     // boundary.  The size is guaranteed to be a multiple of the stack 
00381     // alignment, and the alignment is guaranteed to be bigger than the stack 
00382     // alignment (if required) or 0 to get standard stack alignment.
00383     DYNAMIC_STACKALLOC,
00384 
00385     // Control flow instructions.  These all have token chains.
00386 
00387     // BR - Unconditional branch.  The first operand is the chain
00388     // operand, the second is the MBB to branch to.
00389     BR,
00390 
00391     // BRCOND - Conditional branch.  The first operand is the chain,
00392     // the second is the condition, the third is the block to branch
00393     // to if the condition is true.
00394     BRCOND,
00395 
00396     // BR_CC - Conditional branch.  The behavior is like that of SELECT_CC, in
00397     // that the condition is represented as condition code, and two nodes to
00398     // compare, rather than as a combined SetCC node.  The operands in order are
00399     // chain, cc, lhs, rhs, block to branch to if condition is true.
00400     BR_CC,
00401     
00402     // RET - Return from function.  The first operand is the chain,
00403     // and any subsequent operands are the return values for the
00404     // function.  This operation can have variable number of operands.
00405     RET,
00406 
00407     // INLINEASM - Represents an inline asm block.  This node always has two
00408     // return values: a chain and a flag result.  The inputs are as follows:
00409     //   Operand #0   : Input chain.
00410     //   Operand #1   : a ExternalSymbolSDNode with a pointer to the asm string.
00411     //   Operand #2n+2: A RegisterNode.
00412     //   Operand #2n+3: A TargetConstant, indicating if the reg is a use/def
00413     //   Operand #last: Optional, an incoming flag.
00414     INLINEASM,
00415 
00416     // STACKSAVE - STACKSAVE has one operand, an input chain.  It produces a
00417     // value, the same type as the pointer type for the system, and an output
00418     // chain.
00419     STACKSAVE,
00420     
00421     // STACKRESTORE has two operands, an input chain and a pointer to restore to
00422     // it returns an output chain.
00423     STACKRESTORE,
00424     
00425     // MEMSET/MEMCPY/MEMMOVE - The first operand is the chain, and the rest
00426     // correspond to the operands of the LLVM intrinsic functions.  The only
00427     // result is a token chain.  The alignment argument is guaranteed to be a
00428     // Constant node.
00429     MEMSET,
00430     MEMMOVE,
00431     MEMCPY,
00432 
00433     // CALLSEQ_START/CALLSEQ_END - These operators mark the beginning and end of
00434     // a call sequence, and carry arbitrary information that target might want
00435     // to know.  The first operand is a chain, the rest are specified by the
00436     // target and not touched by the DAG optimizers.
00437     CALLSEQ_START,  // Beginning of a call sequence
00438     CALLSEQ_END,    // End of a call sequence
00439     
00440     // VAARG - VAARG has three operands: an input chain, a pointer, and a 
00441     // SRCVALUE.  It returns a pair of values: the vaarg value and a new chain.
00442     VAARG,
00443     
00444     // VACOPY - VACOPY has five operands: an input chain, a destination pointer,
00445     // a source pointer, a SRCVALUE for the destination, and a SRCVALUE for the
00446     // source.
00447     VACOPY,
00448     
00449     // VAEND, VASTART - VAEND and VASTART have three operands: an input chain, a
00450     // pointer, and a SRCVALUE.
00451     VAEND, VASTART,
00452 
00453     // SRCVALUE - This corresponds to a Value*, and is used to associate memory
00454     // locations with their value.  This allows one use alias analysis
00455     // information in the backend.
00456     SRCVALUE,
00457 
00458     // PCMARKER - This corresponds to the pcmarker intrinsic.
00459     PCMARKER,
00460 
00461     // READCYCLECOUNTER - This corresponds to the readcyclecounter intrinsic.
00462     // The only operand is a chain and a value and a chain are produced.  The
00463     // value is the contents of the architecture specific cycle counter like 
00464     // register (or other high accuracy low latency clock source)
00465     READCYCLECOUNTER,
00466 
00467     // HANDLENODE node - Used as a handle for various purposes.
00468     HANDLENODE,
00469 
00470     // LOCATION - This node is used to represent a source location for debug
00471     // info.  It takes token chain as input, then a line number, then a column
00472     // number, then a filename, then a working dir.  It produces a token chain
00473     // as output.
00474     LOCATION,
00475     
00476     // DEBUG_LOC - This node is used to represent source line information
00477     // embedded in the code.  It takes a token chain as input, then a line
00478     // number, then a column then a file id (provided by MachineDebugInfo.) It
00479     // produces a token chain as output.
00480     DEBUG_LOC,
00481     
00482     // DEBUG_LABEL - This node is used to mark a location in the code where a
00483     // label should be generated for use by the debug information.  It takes a
00484     // token chain as input and then a unique id (provided by MachineDebugInfo.)
00485     // It produces a token chain as output.
00486     DEBUG_LABEL,
00487     
00488     // BUILTIN_OP_END - This must be the last enum value in this list.
00489     BUILTIN_OP_END
00490   };
00491 
00492   /// Node predicates
00493 
00494   /// isBuildVectorAllOnes - Return true if the specified node is a
00495   /// BUILD_VECTOR where all of the elements are ~0 or undef.
00496   bool isBuildVectorAllOnes(const SDNode *N);
00497 
00498   /// isBuildVectorAllZeros - Return true if the specified node is a
00499   /// BUILD_VECTOR where all of the elements are 0 or undef.
00500   bool isBuildVectorAllZeros(const SDNode *N);
00501   
00502   //===--------------------------------------------------------------------===//
00503   /// ISD::CondCode enum - These are ordered carefully to make the bitfields
00504   /// below work out, when considering SETFALSE (something that never exists
00505   /// dynamically) as 0.  "U" -> Unsigned (for integer operands) or Unordered
00506   /// (for floating point), "L" -> Less than, "G" -> Greater than, "E" -> Equal
00507   /// to.  If the "N" column is 1, the result of the comparison is undefined if
00508   /// the input is a NAN.
00509   ///
00510   /// All of these (except for the 'always folded ops') should be handled for
00511   /// floating point.  For integer, only the SETEQ,SETNE,SETLT,SETLE,SETGT,
00512   /// SETGE,SETULT,SETULE,SETUGT, and SETUGE opcodes are used.
00513   ///
00514   /// Note that these are laid out in a specific order to allow bit-twiddling
00515   /// to transform conditions.
00516   enum CondCode {
00517     // Opcode          N U L G E       Intuitive operation
00518     SETFALSE,      //    0 0 0 0       Always false (always folded)
00519     SETOEQ,        //    0 0 0 1       True if ordered and equal
00520     SETOGT,        //    0 0 1 0       True if ordered and greater than
00521     SETOGE,        //    0 0 1 1       True if ordered and greater than or equal
00522     SETOLT,        //    0 1 0 0       True if ordered and less than
00523     SETOLE,        //    0 1 0 1       True if ordered and less than or equal
00524     SETONE,        //    0 1 1 0       True if ordered and operands are unequal
00525     SETO,          //    0 1 1 1       True if ordered (no nans)
00526     SETUO,         //    1 0 0 0       True if unordered: isnan(X) | isnan(Y)
00527     SETUEQ,        //    1 0 0 1       True if unordered or equal
00528     SETUGT,        //    1 0 1 0       True if unordered or greater than
00529     SETUGE,        //    1 0 1 1       True if unordered, greater than, or equal
00530     SETULT,        //    1 1 0 0       True if unordered or less than
00531     SETULE,        //    1 1 0 1       True if unordered, less than, or equal
00532     SETUNE,        //    1 1 1 0       True if unordered or not equal
00533     SETTRUE,       //    1 1 1 1       Always true (always folded)
00534     // Don't care operations: undefined if the input is a nan.
00535     SETFALSE2,     //  1 X 0 0 0       Always false (always folded)
00536     SETEQ,         //  1 X 0 0 1       True if equal
00537     SETGT,         //  1 X 0 1 0       True if greater than
00538     SETGE,         //  1 X 0 1 1       True if greater than or equal
00539     SETLT,         //  1 X 1 0 0       True if less than
00540     SETLE,         //  1 X 1 0 1       True if less than or equal
00541     SETNE,         //  1 X 1 1 0       True if not equal
00542     SETTRUE2,      //  1 X 1 1 1       Always true (always folded)
00543 
00544     SETCC_INVALID       // Marker value.
00545   };
00546 
00547   /// isSignedIntSetCC - Return true if this is a setcc instruction that
00548   /// performs a signed comparison when used with integer operands.
00549   inline bool isSignedIntSetCC(CondCode Code) {
00550     return Code == SETGT || Code == SETGE || Code == SETLT || Code == SETLE;
00551   }
00552 
00553   /// isUnsignedIntSetCC - Return true if this is a setcc instruction that
00554   /// performs an unsigned comparison when used with integer operands.
00555   inline bool isUnsignedIntSetCC(CondCode Code) {
00556     return Code == SETUGT || Code == SETUGE || Code == SETULT || Code == SETULE;
00557   }
00558 
00559   /// isTrueWhenEqual - Return true if the specified condition returns true if
00560   /// the two operands to the condition are equal.  Note that if one of the two
00561   /// operands is a NaN, this value is meaningless.
00562   inline bool isTrueWhenEqual(CondCode Cond) {
00563     return ((int)Cond & 1) != 0;
00564   }
00565 
00566   /// getUnorderedFlavor - This function returns 0 if the condition is always
00567   /// false if an operand is a NaN, 1 if the condition is always true if the
00568   /// operand is a NaN, and 2 if the condition is undefined if the operand is a
00569   /// NaN.
00570   inline unsigned getUnorderedFlavor(CondCode Cond) {
00571     return ((int)Cond >> 3) & 3;
00572   }
00573 
00574   /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
00575   /// 'op' is a valid SetCC operation.
00576   CondCode getSetCCInverse(CondCode Operation, bool isInteger);
00577 
00578   /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
00579   /// when given the operation for (X op Y).
00580   CondCode getSetCCSwappedOperands(CondCode Operation);
00581 
00582   /// getSetCCOrOperation - Return the result of a logical OR between different
00583   /// comparisons of identical values: ((X op1 Y) | (X op2 Y)).  This
00584   /// function returns SETCC_INVALID if it is not possible to represent the
00585   /// resultant comparison.
00586   CondCode getSetCCOrOperation(CondCode Op1, CondCode Op2, bool isInteger);
00587 
00588   /// getSetCCAndOperation - Return the result of a logical AND between
00589   /// different comparisons of identical values: ((X op1 Y) & (X op2 Y)).  This
00590   /// function returns SETCC_INVALID if it is not possible to represent the
00591   /// resultant comparison.
00592   CondCode getSetCCAndOperation(CondCode Op1, CondCode Op2, bool isInteger);
00593 }  // end llvm::ISD namespace
00594 
00595 
00596 //===----------------------------------------------------------------------===//
00597 /// SDOperand - Unlike LLVM values, Selection DAG nodes may return multiple
00598 /// values as the result of a computation.  Many nodes return multiple values,
00599 /// from loads (which define a token and a return value) to ADDC (which returns
00600 /// a result and a carry value), to calls (which may return an arbitrary number
00601 /// of values).
00602 ///
00603 /// As such, each use of a SelectionDAG computation must indicate the node that
00604 /// computes it as well as which return value to use from that node.  This pair
00605 /// of information is represented with the SDOperand value type.
00606 ///
00607 class SDOperand {
00608 public:
00609   SDNode *Val;        // The node defining the value we are using.
00610   unsigned ResNo;     // Which return value of the node we are using.
00611 
00612   SDOperand() : Val(0), ResNo(0) {}
00613   SDOperand(SDNode *val, unsigned resno) : Val(val), ResNo(resno) {}
00614 
00615   bool operator==(const SDOperand &O) const {
00616     return Val == O.Val && ResNo == O.ResNo;
00617   }
00618   bool operator!=(const SDOperand &O) const {
00619     return !operator==(O);
00620   }
00621   bool operator<(const SDOperand &O) const {
00622     return Val < O.Val || (Val == O.Val && ResNo < O.ResNo);
00623   }
00624 
00625   SDOperand getValue(unsigned R) const {
00626     return SDOperand(Val, R);
00627   }
00628 
00629   // isOperand - Return true if this node is an operand of N.
00630   bool isOperand(SDNode *N) const;
00631 
00632   /// getValueType - Return the ValueType of the referenced return value.
00633   ///
00634   inline MVT::ValueType getValueType() const;
00635 
00636   // Forwarding methods - These forward to the corresponding methods in SDNode.
00637   inline unsigned getOpcode() const;
00638   inline unsigned getNodeDepth() const;
00639   inline unsigned getNumOperands() const;
00640   inline const SDOperand &getOperand(unsigned i) const;
00641   inline bool isTargetOpcode() const;
00642   inline unsigned getTargetOpcode() const;
00643 
00644   /// hasOneUse - Return true if there is exactly one operation using this
00645   /// result value of the defining operator.
00646   inline bool hasOneUse() const;
00647 };
00648 
00649 
00650 /// simplify_type specializations - Allow casting operators to work directly on
00651 /// SDOperands as if they were SDNode*'s.
00652 template<> struct simplify_type<SDOperand> {
00653   typedef SDNode* SimpleType;
00654   static SimpleType getSimplifiedValue(const SDOperand &Val) {
00655     return static_cast<SimpleType>(Val.Val);
00656   }
00657 };
00658 template<> struct simplify_type<const SDOperand> {
00659   typedef SDNode* SimpleType;
00660   static SimpleType getSimplifiedValue(const SDOperand &Val) {
00661     return static_cast<SimpleType>(Val.Val);
00662   }
00663 };
00664 
00665 
00666 /// SDNode - Represents one node in the SelectionDAG.
00667 ///
00668 class SDNode {
00669   /// NodeType - The operation that this node performs.
00670   ///
00671   unsigned short NodeType;
00672 
00673   /// NodeDepth - Node depth is defined as MAX(Node depth of children)+1.  This
00674   /// means that leaves have a depth of 1, things that use only leaves have a
00675   /// depth of 2, etc.
00676   unsigned short NodeDepth;
00677 
00678   /// OperandList - The values that are used by this operation.
00679   ///
00680   SDOperand *OperandList;
00681   
00682   /// ValueList - The types of the values this node defines.  SDNode's may
00683   /// define multiple values simultaneously.
00684   MVT::ValueType *ValueList;
00685 
00686   /// NumOperands/NumValues - The number of entries in the Operand/Value list.
00687   unsigned short NumOperands, NumValues;
00688   
00689   /// Prev/Next pointers - These pointers form the linked list of of the
00690   /// AllNodes list in the current DAG.
00691   SDNode *Prev, *Next;
00692   friend struct ilist_traits<SDNode>;
00693 
00694   /// Uses - These are all of the SDNode's that use a value produced by this
00695   /// node.
00696   std::vector<SDNode*> Uses;
00697 public:
00698   virtual ~SDNode() {
00699     assert(NumOperands == 0 && "Operand list not cleared before deletion");
00700   }
00701   
00702   //===--------------------------------------------------------------------===//
00703   //  Accessors
00704   //
00705   unsigned getOpcode()  const { return NodeType; }
00706   bool isTargetOpcode() const { return NodeType >= ISD::BUILTIN_OP_END; }
00707   unsigned getTargetOpcode() const {
00708     assert(isTargetOpcode() && "Not a target opcode!");
00709     return NodeType - ISD::BUILTIN_OP_END;
00710   }
00711 
00712   size_t use_size() const { return Uses.size(); }
00713   bool use_empty() const { return Uses.empty(); }
00714   bool hasOneUse() const { return Uses.size() == 1; }
00715 
00716   /// getNodeDepth - Return the distance from this node to the leaves in the
00717   /// graph.  The leaves have a depth of 1.
00718   unsigned getNodeDepth() const { return NodeDepth; }
00719 
00720   typedef std::vector<SDNode*>::const_iterator use_iterator;
00721   use_iterator use_begin() const { return Uses.begin(); }
00722   use_iterator use_end() const { return Uses.end(); }
00723 
00724   /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
00725   /// indicated value.  This method ignores uses of other values defined by this
00726   /// operation.
00727   bool hasNUsesOfValue(unsigned NUses, unsigned Value) const;
00728 
00729   // isOnlyUse - Return true if this node is the only use of N.
00730   bool isOnlyUse(SDNode *N) const;
00731 
00732   // isOperand - Return true if this node is an operand of N.
00733   bool isOperand(SDNode *N) const;
00734 
00735   /// getNumOperands - Return the number of values used by this operation.
00736   ///
00737   unsigned getNumOperands() const { return NumOperands; }
00738 
00739   const SDOperand &getOperand(unsigned Num) const {
00740     assert(Num < NumOperands && "Invalid child # of SDNode!");
00741     return OperandList[Num];
00742   }
00743   typedef const SDOperand* op_iterator;
00744   op_iterator op_begin() const { return OperandList; }
00745   op_iterator op_end() const { return OperandList+NumOperands; }
00746 
00747 
00748   /// getNumValues - Return the number of values defined/returned by this
00749   /// operator.
00750   ///
00751   unsigned getNumValues() const { return NumValues; }
00752 
00753   /// getValueType - Return the type of a specified result.
00754   ///
00755   MVT::ValueType getValueType(unsigned ResNo) const {
00756     assert(ResNo < NumValues && "Illegal result number!");
00757     return ValueList[ResNo];
00758   }
00759 
00760   typedef const MVT::ValueType* value_iterator;
00761   value_iterator value_begin() const { return ValueList; }
00762   value_iterator value_end() const { return ValueList+NumValues; }
00763 
00764   /// getOperationName - Return the opcode of this operation for printing.
00765   ///
00766   const char* getOperationName(const SelectionDAG *G = 0) const;
00767   void dump() const;
00768   void dump(const SelectionDAG *G) const;
00769 
00770   static bool classof(const SDNode *) { return true; }
00771 
00772 protected:
00773   friend class SelectionDAG;
00774   
00775   /// getValueTypeList - Return a pointer to the specified value type.
00776   ///
00777   static MVT::ValueType *getValueTypeList(MVT::ValueType VT);
00778 
00779   SDNode(unsigned NT, MVT::ValueType VT) : NodeType(NT), NodeDepth(1) {
00780     OperandList = 0; NumOperands = 0;
00781     ValueList = getValueTypeList(VT);
00782     NumValues = 1;
00783     Prev = 0; Next = 0;
00784   }
00785   SDNode(unsigned NT, SDOperand Op)
00786     : NodeType(NT), NodeDepth(Op.Val->getNodeDepth()+1) {
00787     OperandList = new SDOperand[1];
00788     OperandList[0] = Op;
00789     NumOperands = 1;
00790     Op.Val->Uses.push_back(this);
00791     ValueList = 0;
00792     NumValues = 0;
00793     Prev = 0; Next = 0;
00794   }
00795   SDNode(unsigned NT, SDOperand N1, SDOperand N2)
00796     : NodeType(NT) {
00797     if (N1.Val->getNodeDepth() > N2.Val->getNodeDepth())
00798       NodeDepth = N1.Val->getNodeDepth()+1;
00799     else
00800       NodeDepth = N2.Val->getNodeDepth()+1;
00801     OperandList = new SDOperand[2];
00802     OperandList[0] = N1;
00803     OperandList[1] = N2;
00804     NumOperands = 2;
00805     N1.Val->Uses.push_back(this); N2.Val->Uses.push_back(this);
00806     ValueList = 0;
00807     NumValues = 0;
00808     Prev = 0; Next = 0;
00809   }
00810   SDNode(unsigned NT, SDOperand N1, SDOperand N2, SDOperand N3)
00811     : NodeType(NT) {
00812     unsigned ND = N1.Val->getNodeDepth();
00813     if (ND < N2.Val->getNodeDepth())
00814       ND = N2.Val->getNodeDepth();
00815     if (ND < N3.Val->getNodeDepth())
00816       ND = N3.Val->getNodeDepth();
00817     NodeDepth = ND+1;
00818 
00819     OperandList = new SDOperand[3];
00820     OperandList[0] = N1;
00821     OperandList[1] = N2;
00822     OperandList[2] = N3;
00823     NumOperands = 3;
00824     
00825     N1.Val->Uses.push_back(this); N2.Val->Uses.push_back(this);
00826     N3.Val->Uses.push_back(this);
00827     ValueList = 0;
00828     NumValues = 0;
00829     Prev = 0; Next = 0;
00830   }
00831   SDNode(unsigned NT, SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4)
00832     : NodeType(NT) {
00833     unsigned ND = N1.Val->getNodeDepth();
00834     if (ND < N2.Val->getNodeDepth())
00835       ND = N2.Val->getNodeDepth();
00836     if (ND < N3.Val->getNodeDepth())
00837       ND = N3.Val->getNodeDepth();
00838     if (ND < N4.Val->getNodeDepth())
00839       ND = N4.Val->getNodeDepth();
00840     NodeDepth = ND+1;
00841 
00842     OperandList = new SDOperand[4];
00843     OperandList[0] = N1;
00844     OperandList[1] = N2;
00845     OperandList[2] = N3;
00846     OperandList[3] = N4;
00847     NumOperands = 4;
00848     
00849     N1.Val->Uses.push_back(this); N2.Val->Uses.push_back(this);
00850     N3.Val->Uses.push_back(this); N4.Val->Uses.push_back(this);
00851     ValueList = 0;
00852     NumValues = 0;
00853     Prev = 0; Next = 0;
00854   }
00855   SDNode(unsigned Opc, const std::vector<SDOperand> &Nodes) : NodeType(Opc) {
00856     NumOperands = Nodes.size();
00857     OperandList = new SDOperand[NumOperands];
00858     
00859     unsigned ND = 0;
00860     for (unsigned i = 0, e = Nodes.size(); i != e; ++i) {
00861       OperandList[i] = Nodes[i];
00862       SDNode *N = OperandList[i].Val;
00863       N->Uses.push_back(this);
00864       if (ND < N->getNodeDepth()) ND = N->getNodeDepth();
00865     }
00866     NodeDepth = ND+1;
00867     ValueList = 0;
00868     NumValues = 0;
00869     Prev = 0; Next = 0;
00870   }
00871 
00872   /// MorphNodeTo - This clears the return value and operands list, and sets the
00873   /// opcode of the node to the specified value.  This should only be used by
00874   /// the SelectionDAG class.
00875   void MorphNodeTo(unsigned Opc) {
00876     NodeType = Opc;
00877     ValueList = 0;
00878     NumValues = 0;
00879     
00880     // Clear the operands list, updating used nodes to remove this from their
00881     // use list.
00882     for (op_iterator I = op_begin(), E = op_end(); I != E; ++I)
00883       I->Val->removeUser(this);
00884     delete [] OperandList;
00885     OperandList = 0;
00886     NumOperands = 0;
00887   }
00888   
00889   void setValueTypes(MVT::ValueType VT) {
00890     assert(NumValues == 0 && "Should not have values yet!");
00891     ValueList = getValueTypeList(VT);
00892     NumValues = 1;
00893   }
00894   void setValueTypes(MVT::ValueType *List, unsigned NumVal) {
00895     assert(NumValues == 0 && "Should not have values yet!");
00896     ValueList = List;
00897     NumValues = NumVal;
00898   }
00899   
00900   void setOperands(SDOperand Op0) {
00901     assert(NumOperands == 0 && "Should not have operands yet!");
00902     OperandList = new SDOperand[1];
00903     OperandList[0] = Op0;
00904     NumOperands = 1;
00905     Op0.Val->Uses.push_back(this);
00906   }
00907   void setOperands(SDOperand Op0, SDOperand Op1) {
00908     assert(NumOperands == 0 && "Should not have operands yet!");
00909     OperandList = new SDOperand[2];
00910     OperandList[0] = Op0;
00911     OperandList[1] = Op1;
00912     NumOperands = 2;
00913     Op0.Val->Uses.push_back(this); Op1.Val->Uses.push_back(this);
00914   }
00915   void setOperands(SDOperand Op0, SDOperand Op1, SDOperand Op2) {
00916     assert(NumOperands == 0 && "Should not have operands yet!");
00917     OperandList = new SDOperand[3];
00918     OperandList[0] = Op0;
00919     OperandList[1] = Op1;
00920     OperandList[2] = Op2;
00921     NumOperands = 3;
00922     Op0.Val->Uses.push_back(this); Op1.Val->Uses.push_back(this);
00923     Op2.Val->Uses.push_back(this);
00924   }
00925   void setOperands(SDOperand Op0, SDOperand Op1, SDOperand Op2, SDOperand Op3) {
00926     assert(NumOperands == 0 && "Should not have operands yet!");
00927     OperandList = new SDOperand[4];
00928     OperandList[0] = Op0;
00929     OperandList[1] = Op1;
00930     OperandList[2] = Op2;
00931     OperandList[3] = Op3;
00932     NumOperands = 4;
00933     Op0.Val->Uses.push_back(this); Op1.Val->Uses.push_back(this);
00934     Op2.Val->Uses.push_back(this); Op3.Val->Uses.push_back(this);
00935   }
00936   void setOperands(SDOperand Op0, SDOperand Op1, SDOperand Op2, SDOperand Op3,
00937                    SDOperand Op4) {
00938     assert(NumOperands == 0 && "Should not have operands yet!");
00939     OperandList = new SDOperand[5];
00940     OperandList[0] = Op0;
00941     OperandList[1] = Op1;
00942     OperandList[2] = Op2;
00943     OperandList[3] = Op3;
00944     OperandList[4] = Op4;
00945     NumOperands = 5;
00946     Op0.Val->Uses.push_back(this); Op1.Val->Uses.push_back(this);
00947     Op2.Val->Uses.push_back(this); Op3.Val->Uses.push_back(this);
00948     Op4.Val->Uses.push_back(this);
00949   }
00950   void setOperands(SDOperand Op0, SDOperand Op1, SDOperand Op2, SDOperand Op3,
00951                    SDOperand Op4, SDOperand Op5) {
00952     assert(NumOperands == 0 && "Should not have operands yet!");
00953     OperandList = new SDOperand[6];
00954     OperandList[0] = Op0;
00955     OperandList[1] = Op1;
00956     OperandList[2] = Op2;
00957     OperandList[3] = Op3;
00958     OperandList[4] = Op4;
00959     OperandList[5] = Op5;
00960     NumOperands = 6;
00961     Op0.Val->Uses.push_back(this); Op1.Val->Uses.push_back(this);
00962     Op2.Val->Uses.push_back(this); Op3.Val->Uses.push_back(this);
00963     Op4.Val->Uses.push_back(this); Op5.Val->Uses.push_back(this);
00964   }
00965   void setOperands(SDOperand Op0, SDOperand Op1, SDOperand Op2, SDOperand Op3,
00966                    SDOperand Op4, SDOperand Op5, SDOperand Op6) {
00967     assert(NumOperands == 0 && "Should not have operands yet!");
00968     OperandList = new SDOperand[7];
00969     OperandList[0] = Op0;
00970     OperandList[1] = Op1;
00971     OperandList[2] = Op2;
00972     OperandList[3] = Op3;
00973     OperandList[4] = Op4;
00974     OperandList[5] = Op5;
00975     OperandList[6] = Op6;
00976     NumOperands = 7;
00977     Op0.Val->Uses.push_back(this); Op1.Val->Uses.push_back(this);
00978     Op2.Val->Uses.push_back(this); Op3.Val->Uses.push_back(this);
00979     Op4.Val->Uses.push_back(this); Op5.Val->Uses.push_back(this);
00980     Op6.Val->Uses.push_back(this);
00981   }
00982   void setOperands(SDOperand Op0, SDOperand Op1, SDOperand Op2, SDOperand Op3,
00983                    SDOperand Op4, SDOperand Op5, SDOperand Op6, SDOperand Op7) {
00984     assert(NumOperands == 0 && "Should not have operands yet!");
00985     OperandList = new SDOperand[8];
00986     OperandList[0] = Op0;
00987     OperandList[1] = Op1;
00988     OperandList[2] = Op2;
00989     OperandList[3] = Op3;
00990     OperandList[4] = Op4;
00991     OperandList[5] = Op5;
00992     OperandList[6] = Op6;
00993     OperandList[7] = Op7;
00994     NumOperands = 8;
00995     Op0.Val->Uses.push_back(this); Op1.Val->Uses.push_back(this);
00996     Op2.Val->Uses.push_back(this); Op3.Val->Uses.push_back(this);
00997     Op4.Val->Uses.push_back(this); Op5.Val->Uses.push_back(this);
00998     Op6.Val->Uses.push_back(this); Op7.Val->Uses.push_back(this);
00999   }
01000 
01001   void addUser(SDNode *User) {
01002     Uses.push_back(User);
01003   }
01004   void removeUser(SDNode *User) {
01005     // Remove this user from the operand's use list.
01006     for (unsigned i = Uses.size(); ; --i) {
01007       assert(i != 0 && "Didn't find user!");
01008       if (Uses[i-1] == User) {
01009         Uses[i-1] = Uses.back();
01010         Uses.pop_back();
01011         return;
01012       }
01013     }
01014   }
01015 };
01016 
01017 
01018 // Define inline functions from the SDOperand class.
01019 
01020 inline unsigned SDOperand::getOpcode() const {
01021   return Val->getOpcode();
01022 }
01023 inline unsigned SDOperand::getNodeDepth() const {
01024   return Val->getNodeDepth();
01025 }
01026 inline MVT::ValueType SDOperand::getValueType() const {
01027   return Val->getValueType(ResNo);
01028 }
01029 inline unsigned SDOperand::getNumOperands() const {
01030   return Val->getNumOperands();
01031 }
01032 inline const SDOperand &SDOperand::getOperand(unsigned i) const {
01033   return Val->getOperand(i);
01034 }
01035 inline bool SDOperand::isTargetOpcode() const {
01036   return Val->isTargetOpcode();
01037 }
01038 inline unsigned SDOperand::getTargetOpcode() const {
01039   return Val->getTargetOpcode();
01040 }
01041 inline bool SDOperand::hasOneUse() const {
01042   return Val->hasNUsesOfValue(1, ResNo);
01043 }
01044 
01045 /// HandleSDNode - This class is used to form a handle around another node that
01046 /// is persistant and is updated across invocations of replaceAllUsesWith on its
01047 /// operand.  This node should be directly created by end-users and not added to
01048 /// the AllNodes list.
01049 class HandleSDNode : public SDNode {
01050 public:
01051   HandleSDNode(SDOperand X) : SDNode(ISD::HANDLENODE, X) {}
01052   ~HandleSDNode() {
01053     MorphNodeTo(ISD::HANDLENODE);  // Drops operand uses.
01054   }
01055   
01056   SDOperand getValue() const { return getOperand(0); }
01057 };
01058 
01059 class StringSDNode : public SDNode {
01060   std::string Value;
01061 protected:
01062   friend class SelectionDAG;
01063   StringSDNode(const std::string &val)
01064     : SDNode(ISD::STRING, MVT::Other), Value(val) {
01065   }
01066 public:
01067   const std::string &getValue() const { return Value; }
01068   static bool classof(const StringSDNode *) { return true; }
01069   static bool classof(const SDNode *N) {
01070     return N->getOpcode() == ISD::STRING;
01071   }
01072 };  
01073 
01074 class ConstantSDNode : public SDNode {
01075   uint64_t Value;
01076 protected:
01077   friend class SelectionDAG;
01078   ConstantSDNode(bool isTarget, uint64_t val, MVT::ValueType VT)
01079     : SDNode(isTarget ? ISD::TargetConstant : ISD::Constant, VT), Value(val) {
01080   }
01081 public:
01082 
01083   uint64_t getValue() const { return Value; }
01084 
01085   int64_t getSignExtended() const {
01086     unsigned Bits = MVT::getSizeInBits(getValueType(0));
01087     return ((int64_t)Value << (64-Bits)) >> (64-Bits);
01088   }
01089 
01090   bool isNullValue() const { return Value == 0; }
01091   bool isAllOnesValue() const {
01092     return Value == MVT::getIntVTBitMask(getValueType(0));
01093   }
01094 
01095   static bool classof(const ConstantSDNode *) { return true; }
01096   static bool classof(const SDNode *N) {
01097     return N->getOpcode() == ISD::Constant ||
01098            N->getOpcode() == ISD::TargetConstant;
01099   }
01100 };
01101 
01102 class ConstantFPSDNode : public SDNode {
01103   double Value;
01104 protected:
01105   friend class SelectionDAG;
01106   ConstantFPSDNode(bool isTarget, double val, MVT::ValueType VT)
01107     : SDNode(isTarget ? ISD::TargetConstantFP : ISD::ConstantFP, VT), 
01108       Value(val) {
01109   }
01110 public:
01111 
01112   double getValue() const { return Value; }
01113 
01114   /// isExactlyValue - We don't rely on operator== working on double values, as
01115   /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
01116   /// As such, this method can be used to do an exact bit-for-bit comparison of
01117   /// two floating point values.
01118   bool isExactlyValue(double V) const;
01119 
01120   static bool classof(const ConstantFPSDNode *) { return true; }
01121   static bool classof(const SDNode *N) {
01122     return N->getOpcode() == ISD::ConstantFP || 
01123            N->getOpcode() == ISD::TargetConstantFP;
01124   }
01125 };
01126 
01127 class GlobalAddressSDNode : public SDNode {
01128   GlobalValue *TheGlobal;
01129   int Offset;
01130 protected:
01131   friend class SelectionDAG;
01132   GlobalAddressSDNode(bool isTarget, const GlobalValue *GA, MVT::ValueType VT,
01133                       int o=0)
01134     : SDNode(isTarget ? ISD::TargetGlobalAddress : ISD::GlobalAddress, VT),
01135       Offset(o) {
01136     TheGlobal = const_cast<GlobalValue*>(GA);
01137   }
01138 public:
01139 
01140   GlobalValue *getGlobal() const { return TheGlobal; }
01141   int getOffset() const { return Offset; }
01142 
01143   static bool classof(const GlobalAddressSDNode *) { return true; }
01144   static bool classof(const SDNode *N) {
01145     return N->getOpcode() == ISD::GlobalAddress ||
01146            N->getOpcode() == ISD::TargetGlobalAddress;
01147   }
01148 };
01149 
01150 
01151 class FrameIndexSDNode : public SDNode {
01152   int FI;
01153 protected:
01154   friend class SelectionDAG;
01155   FrameIndexSDNode(int fi, MVT::ValueType VT, bool isTarg)
01156     : SDNode(isTarg ? ISD::TargetFrameIndex : ISD::FrameIndex, VT), FI(fi) {}
01157 public:
01158 
01159   int getIndex() const { return FI; }
01160 
01161   static bool classof(const FrameIndexSDNode *) { return true; }
01162   static bool classof(const SDNode *N) {
01163     return N->getOpcode() == ISD::FrameIndex ||
01164            N->getOpcode() == ISD::TargetFrameIndex;
01165   }
01166 };
01167 
01168 class ConstantPoolSDNode : public SDNode {
01169   Constant *C;
01170   int Offset;
01171   unsigned Alignment;
01172 protected:
01173   friend class SelectionDAG;
01174   ConstantPoolSDNode(bool isTarget, Constant *c, MVT::ValueType VT,
01175                      int o=0)
01176     : SDNode(isTarget ? ISD::TargetConstantPool : ISD::ConstantPool, VT),
01177       C(c), Offset(o), Alignment(0) {}
01178   ConstantPoolSDNode(bool isTarget, Constant *c, MVT::ValueType VT, int o,
01179                      unsigned Align)
01180     : SDNode(isTarget ? ISD::TargetConstantPool : ISD::ConstantPool, VT),
01181       C(c), Offset(o), Alignment(Align) {}
01182 public:
01183 
01184   Constant *get() const { return C; }
01185   int getOffset() const { return Offset; }
01186   
01187   // Return the alignment of this constant pool object, which is either 0 (for
01188   // default alignment) or log2 of the desired value.
01189   unsigned getAlignment() const { return Alignment; }
01190 
01191   static bool classof(const ConstantPoolSDNode *) { return true; }
01192   static bool classof(const SDNode *N) {
01193     return N->getOpcode() == ISD::ConstantPool ||
01194            N->getOpcode() == ISD::TargetConstantPool;
01195   }
01196 };
01197 
01198 class BasicBlockSDNode : public SDNode {
01199   MachineBasicBlock *MBB;
01200 protected:
01201   friend class SelectionDAG;
01202   BasicBlockSDNode(MachineBasicBlock *mbb)
01203     : SDNode(ISD::BasicBlock, MVT::Other), MBB(mbb) {}
01204 public:
01205 
01206   MachineBasicBlock *getBasicBlock() const { return MBB; }
01207 
01208   static bool classof(const BasicBlockSDNode *) { return true; }
01209   static bool classof(const SDNode *N) {
01210     return N->getOpcode() == ISD::BasicBlock;
01211   }
01212 };
01213 
01214 class SrcValueSDNode : public SDNode {
01215   const Value *V;
01216   int offset;
01217 protected:
01218   friend class SelectionDAG;
01219   SrcValueSDNode(const Value* v, int o)
01220     : SDNode(ISD::SRCVALUE, MVT::Other), V(v), offset(o) {}
01221 
01222 public:
01223   const Value *getValue() const { return V; }
01224   int getOffset() const { return offset; }
01225 
01226   static bool classof(const SrcValueSDNode *) { return true; }
01227   static bool classof(const SDNode *N) {
01228     return N->getOpcode() == ISD::SRCVALUE;
01229   }
01230 };
01231 
01232 
01233 class RegisterSDNode : public SDNode {
01234   unsigned Reg;
01235 protected:
01236   friend class SelectionDAG;
01237   RegisterSDNode(unsigned reg, MVT::ValueType VT)
01238     : SDNode(ISD::Register, VT), Reg(reg) {}
01239 public:
01240 
01241   unsigned getReg() const { return Reg; }
01242 
01243   static bool classof(const RegisterSDNode *) { return true; }
01244   static bool classof(const SDNode *N) {
01245     return N->getOpcode() == ISD::Register;
01246   }
01247 };
01248 
01249 class ExternalSymbolSDNode : public SDNode {
01250   const char *Symbol;
01251 protected:
01252   friend class SelectionDAG;
01253   ExternalSymbolSDNode(bool isTarget, const char *Sym, MVT::ValueType VT)
01254     : SDNode(isTarget ? ISD::TargetExternalSymbol : ISD::ExternalSymbol, VT),
01255       Symbol(Sym) {
01256     }
01257 public:
01258 
01259   const char *getSymbol() const { return Symbol; }
01260 
01261   static bool classof(const ExternalSymbolSDNode *) { return true; }
01262   static bool classof(const SDNode *N) {
01263     return N->getOpcode() == ISD::ExternalSymbol ||
01264            N->getOpcode() == ISD::TargetExternalSymbol;
01265   }
01266 };
01267 
01268 class CondCodeSDNode : public SDNode {
01269   ISD::CondCode Condition;
01270 protected:
01271   friend class SelectionDAG;
01272   CondCodeSDNode(ISD::CondCode Cond)
01273     : SDNode(ISD::CONDCODE, MVT::Other), Condition(Cond) {
01274   }
01275 public:
01276 
01277   ISD::CondCode get() const { return Condition; }
01278 
01279   static bool classof(const CondCodeSDNode *) { return true; }
01280   static bool classof(const SDNode *N) {
01281     return N->getOpcode() == ISD::CONDCODE;
01282   }
01283 };
01284 
01285 /// VTSDNode - This class is used to represent MVT::ValueType's, which are used
01286 /// to parameterize some operations.
01287 class VTSDNode : public SDNode {
01288   MVT::ValueType ValueType;
01289 protected:
01290   friend class SelectionDAG;
01291   VTSDNode(MVT::ValueType VT)
01292     : SDNode(ISD::VALUETYPE, MVT::Other), ValueType(VT) {}
01293 public:
01294 
01295   MVT::ValueType getVT() const { return ValueType; }
01296 
01297   static bool classof(const VTSDNode *) { return true; }
01298   static bool classof(const SDNode *N) {
01299     return N->getOpcode() == ISD::VALUETYPE;
01300   }
01301 };
01302 
01303 
01304 class SDNodeIterator : public forward_iterator<SDNode, ptrdiff_t> {
01305   SDNode *Node;
01306   unsigned Operand;
01307 
01308   SDNodeIterator(SDNode *N, unsigned Op) : Node(N), Operand(Op) {}
01309 public:
01310   bool operator==(const SDNodeIterator& x) const {
01311     return Operand == x.Operand;
01312   }
01313   bool operator!=(const SDNodeIterator& x) const { return !operator==(x); }
01314 
01315   const SDNodeIterator &operator=(const SDNodeIterator &I) {
01316     assert(I.Node == Node && "Cannot assign iterators to two different nodes!");
01317     Operand = I.Operand;
01318     return *this;
01319   }
01320 
01321   pointer operator*() const {
01322     return Node->getOperand(Operand).Val;
01323   }
01324   pointer operator->() const { return operator*(); }
01325 
01326   SDNodeIterator& operator++() {                // Preincrement
01327     ++Operand;
01328     return *this;
01329   }
01330   SDNodeIterator operator++(int) { // Postincrement
01331     SDNodeIterator tmp = *this; ++*this; return tmp;
01332   }
01333 
01334   static SDNodeIterator begin(SDNode *N) { return SDNodeIterator(N, 0); }
01335   static SDNodeIterator end  (SDNode *N) {
01336     return SDNodeIterator(N, N->getNumOperands());
01337   }
01338 
01339   unsigned getOperand() const { return Operand; }
01340   const SDNode *getNode() const { return Node; }
01341 };
01342 
01343 template <> struct GraphTraits<SDNode*> {
01344   typedef SDNode NodeType;
01345   typedef SDNodeIterator ChildIteratorType;
01346   static inline NodeType *getEntryNode(SDNode *N) { return N; }
01347   static inline ChildIteratorType child_begin(NodeType *N) {
01348     return SDNodeIterator::begin(N);
01349   }
01350   static inline ChildIteratorType child_end(NodeType *N) {
01351     return SDNodeIterator::end(N);
01352   }
01353 };
01354 
01355 template<>
01356 struct ilist_traits<SDNode> {
01357   static SDNode *getPrev(const SDNode *N) { return N->Prev; }
01358   static SDNode *getNext(const SDNode *N) { return N->Next; }
01359   
01360   static void setPrev(SDNode *N, SDNode *Prev) { N->Prev = Prev; }
01361   static void setNext(SDNode *N, SDNode *Next) { N->Next = Next; }
01362   
01363   static SDNode *createSentinel() {
01364     return new SDNode(ISD::EntryToken, MVT::Other);
01365   }
01366   static void destroySentinel(SDNode *N) { delete N; }
01367   //static SDNode *createNode(const SDNode &V) { return new SDNode(V); }
01368   
01369   
01370   void addNodeToList(SDNode *NTy) {}
01371   void removeNodeFromList(SDNode *NTy) {}
01372   void transferNodesFromList(iplist<SDNode, ilist_traits> &L2,
01373                              const ilist_iterator<SDNode> &X,
01374                              const ilist_iterator<SDNode> &Y) {}
01375 };
01376 
01377 } // end llvm namespace
01378 
01379 #endif