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