X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FSelectionDAGNodes.h;h=77d607a2cb6d0d02a8fa5d64b42551ae4aaf5e02;hb=cdb73882335834d40ffc7343d55ca89d49417585;hp=7e3b1688ac46ce4c51ebea44a210122d8638634b;hpb=1ab7d859cf5c490612799d7e132c0b1c39f8f497;p=oota-llvm.git diff --git a/include/llvm/CodeGen/SelectionDAGNodes.h b/include/llvm/CodeGen/SelectionDAGNodes.h index 7e3b1688ac4..1c3a50de147 100644 --- a/include/llvm/CodeGen/SelectionDAGNodes.h +++ b/include/llvm/CodeGen/SelectionDAGNodes.h @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -19,34 +19,53 @@ #ifndef LLVM_CODEGEN_SELECTIONDAGNODES_H #define LLVM_CODEGEN_SELECTIONDAGNODES_H -#include "llvm/CodeGen/ValueTypes.h" #include "llvm/Value.h" +#include "llvm/ADT/FoldingSet.h" #include "llvm/ADT/GraphTraits.h" -#include "llvm/ADT/iterator" +#include "llvm/ADT/iterator.h" +#include "llvm/ADT/APFloat.h" +#include "llvm/ADT/APInt.h" +#include "llvm/CodeGen/ValueTypes.h" +#include "llvm/CodeGen/MachineMemOperand.h" #include "llvm/Support/DataTypes.h" #include -#include namespace llvm { class SelectionDAG; class GlobalValue; class MachineBasicBlock; +class MachineConstantPoolValue; class SDNode; +template struct DenseMapInfo; template struct simplify_type; template struct ilist_traits; template class iplist; template class ilist_iterator; +/// SDVTList - This represents a list of ValueType's that has been intern'd by +/// a SelectionDAG. Instances of this simple value class are returned by +/// SelectionDAG::getVTList(...). +/// +struct SDVTList { + const MVT *VTs; + unsigned short NumVTs; +}; + /// ISD namespace - This namespace contains an enum which represents all of the /// SelectionDAG node types and value types. /// namespace ISD { + //===--------------------------------------------------------------------===// /// ISD::NodeType enum - This enum defines all of the operators valid in a /// SelectionDAG. /// enum NodeType { + // DELETED_NODE - This is an illegal flag value that is used to catch + // errors. This opcode is not a legal opcode for any node. + DELETED_NODE, + // EntryToken - This is the marker used to indicate the start of the region. EntryToken, @@ -63,49 +82,120 @@ namespace ISD { AssertSext, AssertZext, // Various leaf nodes. - STRING, BasicBlock, VALUETYPE, CONDCODE, Register, + STRING, BasicBlock, VALUETYPE, ARG_FLAGS, CONDCODE, Register, Constant, ConstantFP, - GlobalAddress, FrameIndex, ConstantPool, ExternalSymbol, + GlobalAddress, GlobalTLSAddress, FrameIndex, + JumpTable, ConstantPool, ExternalSymbol, - // ConstantVec works like Constant or ConstantFP, except that it is not a - // leaf node. All operands are either Constant or ConstantFP nodes. - ConstantVec, + // The address of the GOT + GLOBAL_OFFSET_TABLE, + + // FRAMEADDR, RETURNADDR - These nodes represent llvm.frameaddress and + // llvm.returnaddress on the DAG. These nodes take one operand, the index + // of the frame or return address to return. An index of zero corresponds + // to the current function's frame or return address, an index of one to the + // parent's frame or return address, and so on. + FRAMEADDR, RETURNADDR, + + // FRAME_TO_ARGS_OFFSET - This node represents offset from frame pointer to + // first (possible) on-stack argument. This is needed for correct stack + // adjustment during unwind. + FRAME_TO_ARGS_OFFSET, + + // RESULT, OUTCHAIN = EXCEPTIONADDR(INCHAIN) - This node represents the + // address of the exception block on entry to an landing pad block. + EXCEPTIONADDR, + // RESULT, OUTCHAIN = EHSELECTION(INCHAIN, EXCEPTION) - This node represents + // the selection index of the exception thrown. + EHSELECTION, + + // OUTCHAIN = EH_RETURN(INCHAIN, OFFSET, HANDLER) - This node represents + // 'eh_return' gcc dwarf builtin, which is used to return from + // exception. The general meaning is: adjust stack by OFFSET and pass + // execution to HANDLER. Many platform-related details also :) + EH_RETURN, + // TargetConstant* - Like Constant*, but the DAG does not do any folding or // simplification of the constant. TargetConstant, TargetConstantFP, - TargetConstantVec, // TargetGlobalAddress - Like GlobalAddress, but the DAG does no folding or // anything else with this node, and this is valid in the target-specific // dag, turning into a GlobalAddress operand. TargetGlobalAddress, + TargetGlobalTLSAddress, TargetFrameIndex, + TargetJumpTable, TargetConstantPool, TargetExternalSymbol, - - // Abstract version of ConstantVec with abstract Vector type. The first node - // is a constant element count, the second is a value type indicating the - // type of the elements. - VConstant, - + + /// RESULT = INTRINSIC_WO_CHAIN(INTRINSICID, arg1, arg2, ...) + /// This node represents a target intrinsic function with no side effects. + /// The first operand is the ID number of the intrinsic from the + /// llvm::Intrinsic namespace. The operands to the intrinsic follow. The + /// node has returns the result of the intrinsic. + INTRINSIC_WO_CHAIN, + + /// RESULT,OUTCHAIN = INTRINSIC_W_CHAIN(INCHAIN, INTRINSICID, arg1, ...) + /// This node represents a target intrinsic function with side effects that + /// returns a result. The first operand is a chain pointer. The second is + /// the ID number of the intrinsic from the llvm::Intrinsic namespace. The + /// operands to the intrinsic follow. The node has two results, the result + /// of the intrinsic and an output chain. + INTRINSIC_W_CHAIN, + + /// OUTCHAIN = INTRINSIC_VOID(INCHAIN, INTRINSICID, arg1, arg2, ...) + /// This node represents a target intrinsic function with side effects that + /// does not return a result. The first operand is a chain pointer. The + /// second is the ID number of the intrinsic from the llvm::Intrinsic + /// namespace. The operands to the intrinsic follow. + INTRINSIC_VOID, + // CopyToReg - This node has three operands: a chain, a register number to // set to this value, and a value. CopyToReg, // CopyFromReg - This node indicates that the input value is a virtual or // physical register that is defined outside of the scope of this - // SelectionDAG. The register is available from the RegSDNode object. + // SelectionDAG. The register is available from the RegisterSDNode object. CopyFromReg, // UNDEF - An undefined node UNDEF, - - // EXTRACT_ELEMENT - This is used to get the first or second (determined by - // a Constant, which is required to be operand #1), element of the aggregate - // value specified as operand #0. This is only for use before legalization, - // for values that will be broken into multiple registers. + + /// FORMAL_ARGUMENTS(CHAIN, CC#, ISVARARG, FLAG0, ..., FLAGn) - This node + /// represents the formal arguments for a function. CC# is a Constant value + /// indicating the calling convention of the function, and ISVARARG is a + /// flag that indicates whether the function is varargs or not. This node + /// has one result value for each incoming argument, plus one for the output + /// chain. It must be custom legalized. See description of CALL node for + /// FLAG argument contents explanation. + /// + FORMAL_ARGUMENTS, + + /// RV1, RV2...RVn, CHAIN = CALL(CHAIN, CC#, ISVARARG, ISTAILCALL, CALLEE, + /// ARG0, FLAG0, ARG1, FLAG1, ... ARGn, FLAGn) + /// This node represents a fully general function call, before the legalizer + /// runs. This has one result value for each argument / flag pair, plus + /// a chain result. It must be custom legalized. Flag argument indicates + /// misc. argument attributes. Currently: + /// Bit 0 - signness + /// Bit 1 - 'inreg' attribute + /// Bit 2 - 'sret' attribute + /// Bit 4 - 'byval' attribute + /// Bit 5 - 'nest' attribute + /// Bit 6-9 - alignment of byval structures + /// Bit 10-26 - size of byval structures + /// Bits 31:27 - argument ABI alignment in the first argument piece and + /// alignment '1' in other argument pieces. + CALL, + + // EXTRACT_ELEMENT - This is used to get the lower or upper (determined by + // a Constant, which is required to be operand #1) half of the integer value + // specified as operand #0. This is only for use before legalization, for + // values that will be broken into multiple registers. EXTRACT_ELEMENT, // BUILD_PAIR - This is the opposite of EXTRACT_ELEMENT in some ways. Given @@ -122,6 +212,19 @@ namespace ISD { // Simple integer binary arithmetic operators. ADD, SUB, MUL, SDIV, UDIV, SREM, UREM, + + // SMUL_LOHI/UMUL_LOHI - Multiply two integers of type iN, producing + // a signed/unsigned value of type i[2*N], and return the full value as + // two results, each of type iN. + SMUL_LOHI, UMUL_LOHI, + + // SDIVREM/UDIVREM - Divide two integers and produce both a quotient and + // remainder result. + SDIVREM, UDIVREM, + + // CARRY_FALSE - This node is used when folding other nodes, + // like ADDC/SUBC, which indicate the carry result is always false. + CARRY_FALSE, // Carry-setting nodes for multiple precision addition and subtraction. // These nodes take two operands of the same value type, and produce two @@ -140,17 +243,70 @@ namespace ISD { // Simple binary floating point operators. FADD, FSUB, FMUL, FDIV, FREM, - - // Simple abstract vector operators. Unlike the integer and floating point - // binary operators, these nodes also take two additional operands: - // a constant element count, and a value type node indicating the type of - // the elements. The order is count, type, op0, op1. All vector opcodes, - // including VLOAD and VConstant must currently have count and type as - // their 1st and 2nd arguments. - VADD, VSUB, VMUL, + // FCOPYSIGN(X, Y) - Return the value of X with the sign of Y. NOTE: This + // DAG node does not require that X and Y have the same type, just that they + // are both floating point. X and the result must have the same type. + // FCOPYSIGN(f32, f64) is allowed. + FCOPYSIGN, + + // INT = FGETSIGN(FP) - Return the sign bit of the specified floating point + // value as an integer 0/1 value. + FGETSIGN, + + /// BUILD_VECTOR(ELT0, ELT1, ELT2, ELT3,...) - Return a vector + /// with the specified, possibly variable, elements. The number of elements + /// is required to be a power of two. + BUILD_VECTOR, + + /// INSERT_VECTOR_ELT(VECTOR, VAL, IDX) - Returns VECTOR with the element + /// at IDX replaced with VAL. If the type of VAL is larger than the vector + /// element type then VAL is truncated before replacement. + INSERT_VECTOR_ELT, + + /// EXTRACT_VECTOR_ELT(VECTOR, IDX) - Returns a single element from VECTOR + /// identified by the (potentially variable) element number IDX. + EXTRACT_VECTOR_ELT, + + /// CONCAT_VECTORS(VECTOR0, VECTOR1, ...) - Given a number of values of + /// vector type with the same length and element type, this produces a + /// concatenated vector result value, with length equal to the sum of the + /// lengths of the input vectors. + CONCAT_VECTORS, + + /// EXTRACT_SUBVECTOR(VECTOR, IDX) - Returns a subvector from VECTOR (an + /// vector value) starting with the (potentially variable) element number + /// IDX, which must be a multiple of the result vector length. + EXTRACT_SUBVECTOR, + + /// VECTOR_SHUFFLE(VEC1, VEC2, SHUFFLEVEC) - Returns a vector, of the same + /// type as VEC1/VEC2. SHUFFLEVEC is a BUILD_VECTOR of constant int values + /// (maybe of an illegal datatype) or undef that indicate which value each + /// result element will get. The elements of VEC1/VEC2 are enumerated in + /// order. This is quite similar to the Altivec 'vperm' instruction, except + /// that the indices must be constants and are in terms of the element size + /// of VEC1/VEC2, not in terms of bytes. + VECTOR_SHUFFLE, + + /// SCALAR_TO_VECTOR(VAL) - This represents the operation of loading a + /// scalar value into element 0 of the resultant vector type. The top + /// elements 1 to N-1 of the N-element vector are undefined. + SCALAR_TO_VECTOR, + + // EXTRACT_SUBREG - This node is used to extract a sub-register value. + // This node takes a superreg and a constant sub-register index as operands. + // Note sub-register indices must be increasing. That is, if the + // sub-register index of a 8-bit sub-register is N, then the index for a + // 16-bit sub-register must be at least N+1. + EXTRACT_SUBREG, + + // INSERT_SUBREG - This node is used to insert a sub-register value. + // This node takes a superreg, a subreg value, and a constant sub-register + // index as operands. + INSERT_SUBREG, + // MULHU/MULHS - Multiply high - Multiply two integers of type iN, producing - // an unsigned/signed value of type i[2*n], then return the top part. + // an unsigned/signed value of type i[2*N], then return the top part. MULHU, MULHS, // Bitwise operators - logical and, logical or, logical xor, shift left, @@ -161,7 +317,7 @@ namespace ISD { // Counting operators CTTZ, CTLZ, CTPOP, - // Select + // Select(COND, TRUEVAL, FALSEVAL) SELECT, // Select with condition operator - This selects between a true value and @@ -176,6 +332,14 @@ namespace ISD { // (op #2) as a CondCodeSDNode. SETCC, + // Vector SetCC operator - This evaluates to a vector of integer elements + // with the high bit in each element set to true if the comparison is true + // and false if the comparison is false. All other bits in each element + // are undefined. The operands to this are the left and right operands + // to compare (ops #0, and #1) and the condition code to compare them with + // (op #2) as a CondCodeSDNode. + VSETCC, + // SHL_PARTS/SRA_PARTS/SRL_PARTS - These operators are used for expanded // integer shift operations, just like ADD/SUB_PARTS. The operation // ordering is: @@ -212,23 +376,40 @@ namespace ISD { // operand, a ValueType node. SIGN_EXTEND_INREG, - // FP_TO_[US]INT - Convert a floating point value to a signed or unsigned - // integer. + /// FP_TO_[US]INT - Convert a floating point value to a signed or unsigned + /// integer. FP_TO_SINT, FP_TO_UINT, - // FP_ROUND - Perform a rounding operation from the current - // precision down to the specified precision (currently always 64->32). + /// X = FP_ROUND(Y, TRUNC) - Rounding 'Y' from a larger floating point type + /// down to the precision of the destination VT. TRUNC is a flag, which is + /// always an integer that is zero or one. If TRUNC is 0, this is a + /// normal rounding, if it is 1, this FP_ROUND is known to not change the + /// value of Y. + /// + /// The TRUNC = 1 case is used in cases where we know that the value will + /// not be modified by the node, because Y is not using any of the extra + /// precision of source type. This allows certain transformations like + /// FP_EXTEND(FP_ROUND(X,1)) -> X which are not safe for + /// FP_EXTEND(FP_ROUND(X,0)) because the extra bits aren't removed. FP_ROUND, - - // FP_ROUND_INREG - This operator takes a floating point register, and - // rounds it to a floating point value. It then promotes it and returns it - // in a register of the same size. This operation effectively just discards - // excess precision. The type to round down to is specified by the 1th - // operation, a VTSDNode (currently always 64->32->64). + + // FLT_ROUNDS_ - Returns current rounding mode: + // -1 Undefined + // 0 Round to 0 + // 1 Round to nearest + // 2 Round to +inf + // 3 Round to -inf + FLT_ROUNDS_, + + /// X = FP_ROUND_INREG(Y, VT) - This operator takes an FP register, and + /// rounds it to a floating point value. It then promotes it and returns it + /// in a register of the same size. This operation effectively just + /// discards excess precision. The type to round down to is specified by + /// the VT operand, a VTSDNode. FP_ROUND_INREG, - // FP_EXTEND - Extend a smaller FP type into a larger FP type. + /// X = FP_EXTEND(Y) - Extend a smaller FP type into a larger FP type. FP_EXTEND, // BIT_CONVERT - Theis operator converts between integer and FP values, as @@ -239,48 +420,23 @@ namespace ISD { // conversions, but that is a noop, deleted by getNode(). BIT_CONVERT, - // FNEG, FABS, FSQRT, FSIN, FCOS - Perform unary floating point negation, - // absolute value, square root, sine and cosine operations. - FNEG, FABS, FSQRT, FSIN, FCOS, - - // Other operators. LOAD and STORE have token chains as their first - // operand, then the same operands as an LLVM load/store instruction, then a - // SRCVALUE node that provides alias analysis information. - LOAD, STORE, + // FNEG, FABS, FSQRT, FSIN, FCOS, FPOWI, FPOW - Perform unary floating point + // negation, absolute value, square root, sine and cosine, powi, and pow + // operations. + FNEG, FABS, FSQRT, FSIN, FCOS, FPOWI, FPOW, - // Abstract vector version of LOAD. VLOAD has a constant element count as - // the first operand, followed by a value type node indicating the type of - // the elements, a token chain, a pointer operand, and a SRCVALUE node. - VLOAD, - - // EXTLOAD, SEXTLOAD, ZEXTLOAD - These three operators all load a value from - // memory and extend them to a larger value (e.g. load a byte into a word - // register). All three of these have four operands, a token chain, a - // pointer to load from, a SRCVALUE for alias analysis, and a VALUETYPE node - // indicating the type to load. - // - // SEXTLOAD loads the integer operand and sign extends it to a larger - // integer result type. - // ZEXTLOAD loads the integer operand and zero extends it to a larger - // integer result type. - // EXTLOAD is used for two things: floating point extending loads, and - // integer extending loads where it doesn't matter what the high - // bits are set to. The code generator is allowed to codegen this - // into whichever operation is more efficient. - EXTLOAD, SEXTLOAD, ZEXTLOAD, - - // TRUNCSTORE - This operators truncates (for integer) or rounds (for FP) a - // value and stores it to memory in one operation. This can be used for - // either integer or floating point operands. The first four operands of - // this are the same as a standard store. The fifth is the ValueType to - // store it as (which will be smaller than the source value). - TRUNCSTORE, + // LOAD and STORE have token chains as their first operand, then the same + // operands as an LLVM load/store instruction, then an offset node that + // is added / subtracted from the base pointer to form the address (for + // indexed memory ops). + LOAD, STORE, // DYNAMIC_STACKALLOC - Allocate some number of bytes on the stack aligned - // to a specified boundary. The first operand is the token chain, the - // second is the number of bytes to allocate, and the third is the alignment - // boundary. The size is guaranteed to be a multiple of the stack - // alignment, and the alignment is guaranteed to be bigger than the stack + // to a specified boundary. This node always has two return values: a new + // stack pointer value and a chain. The first operand is the token chain, + // the second is the number of bytes to allocate, and the third is the + // alignment boundary. The size is guaranteed to be a multiple of the stack + // alignment, and the alignment is guaranteed to be bigger than the stack // alignment (if required) or 0 to get standard stack alignment. DYNAMIC_STACKALLOC, @@ -290,33 +446,30 @@ namespace ISD { // operand, the second is the MBB to branch to. BR, + // BRIND - Indirect branch. The first operand is the chain, the second + // is the value to branch to, which must be of the same type as the target's + // pointer type. + BRIND, + + // BR_JT - Jumptable branch. The first operand is the chain, the second + // is the jumptable index, the last one is the jumptable entry index. + BR_JT, + // BRCOND - Conditional branch. The first operand is the chain, // the second is the condition, the third is the block to branch // to if the condition is true. BRCOND, - // BRCONDTWOWAY - Two-way conditional branch. The first operand is the - // chain, the second is the condition, the third is the block to branch to - // if true, and the forth is the block to branch to if false. Targets - // usually do not implement this, preferring to have legalize demote the - // operation to BRCOND/BR pairs when necessary. - BRCONDTWOWAY, - // BR_CC - Conditional branch. The behavior is like that of SELECT_CC, in // that the condition is represented as condition code, and two nodes to // compare, rather than as a combined SetCC node. The operands in order are // chain, cc, lhs, rhs, block to branch to if condition is true. BR_CC, - // BRTWOWAY_CC - Two-way conditional branch. The operands in order are - // chain, cc, lhs, rhs, block to branch to if condition is true, block to - // branch to if condition is false. Targets usually do not implement this, - // preferring to have legalize demote the operation to BRCOND/BR pairs. - BRTWOWAY_CC, - // RET - Return from function. The first operand is the chain, - // and any subsequent operands are the return values for the - // function. This operation can have variable number of operands. + // and any subsequent operands are pairs of return value and return value + // signness for the function. This operation can have variable number of + // operands. RET, // INLINEASM - Represents an inline asm block. This node always has two @@ -327,7 +480,22 @@ namespace ISD { // Operand #2n+3: A TargetConstant, indicating if the reg is a use/def // Operand #last: Optional, an incoming flag. INLINEASM, - + + // LABEL - Represents a label in mid basic block used to track + // locations needed for debug and exception handling tables. This node + // returns a chain. + // Operand #0 : input chain. + // Operand #1 : module unique number use to identify the label. + // Operand #2 : 0 indicates a debug label (e.g. stoppoint), 1 indicates + // a EH label, 2 indicates unknown label type. + LABEL, + + // DECLARE - Represents a llvm.dbg.declare intrinsic. It's used to track + // local variable declarations for debugging information. First operand is + // a chain, while the next two operands are first two arguments (address + // and variable) of a llvm.dbg.declare instruction. + DECLARE, + // STACKSAVE - STACKSAVE has one operand, an input chain. It produces a // value, the same type as the pointer type for the system, and an output // chain. @@ -337,18 +505,11 @@ namespace ISD { // it returns an output chain. STACKRESTORE, - // MEMSET/MEMCPY/MEMMOVE - The first operand is the chain, and the rest - // correspond to the operands of the LLVM intrinsic functions. The only - // result is a token chain. The alignment argument is guaranteed to be a - // Constant node. - MEMSET, - MEMMOVE, - MEMCPY, - // CALLSEQ_START/CALLSEQ_END - These operators mark the beginning and end of // a call sequence, and carry arbitrary information that target might want // to know. The first operand is a chain, the rest are specified by the // target and not touched by the DAG optimizers. + // CALLSEQ_START..CALLSEQ_END pairs may not be nested. CALLSEQ_START, // Beginning of a call sequence CALLSEQ_END, // End of a call sequence @@ -365,11 +526,15 @@ namespace ISD { // pointer, and a SRCVALUE. VAEND, VASTART, - // SRCVALUE - This corresponds to a Value*, and is used to associate memory - // locations with their value. This allows one use alias analysis - // information in the backend. + // SRCVALUE - This is a node type that holds a Value* that is used to + // make reference to a value in the LLVM IR. SRCVALUE, + // MEMOPERAND - This is a node that contains a MachineMemOperand which + // records information about a memory reference. This is used to make + // AliasAnalysis queries from the backend. + MEMOPERAND, + // PCMARKER - This corresponds to the pcmarker intrinsic. PCMARKER, @@ -379,12 +544,6 @@ namespace ISD { // register (or other high accuracy low latency clock source) READCYCLECOUNTER, - // READPORT, WRITEPORT, READIO, WRITEIO - These correspond to the LLVM - // intrinsics of the same name. The first operand is a token chain, the - // other operands match the intrinsic. These produce a token chain in - // addition to a value (if any). - READPORT, WRITEPORT, READIO, WRITEIO, - // HANDLENODE node - Used as a handle for various purposes. HANDLENODE, @@ -396,20 +555,154 @@ namespace ISD { // DEBUG_LOC - This node is used to represent source line information // embedded in the code. It takes a token chain as input, then a line - // number, then a column then a file id (provided by MachineDebugInfo.) It + // number, then a column then a file id (provided by MachineModuleInfo.) It // produces a token chain as output. DEBUG_LOC, + + // TRAMPOLINE - This corresponds to the init_trampoline intrinsic. + // It takes as input a token chain, the pointer to the trampoline, + // the pointer to the nested function, the pointer to pass for the + // 'nest' parameter, a SRCVALUE for the trampoline and another for + // the nested function (allowing targets to access the original + // Function*). It produces the result of the intrinsic and a token + // chain as output. + TRAMPOLINE, + + // TRAP - Trapping instruction + TRAP, + + // PREFETCH - This corresponds to a prefetch intrinsic. It takes chains are + // their first operand. The other operands are the address to prefetch, + // read / write specifier, and locality specifier. + PREFETCH, + + // OUTCHAIN = MEMBARRIER(INCHAIN, load-load, load-store, store-load, + // store-store, device) + // This corresponds to the memory.barrier intrinsic. + // it takes an input chain, 4 operands to specify the type of barrier, an + // operand specifying if the barrier applies to device and uncached memory + // and produces an output chain. + MEMBARRIER, + + // Val, OUTCHAIN = ATOMIC_LCS(INCHAIN, ptr, cmp, swap) + // this corresponds to the atomic.lcs intrinsic. + // cmp is compared to *ptr, and if equal, swap is stored in *ptr. + // the return is always the original value in *ptr + ATOMIC_LCS, + + // Val, OUTCHAIN = ATOMIC_LAS(INCHAIN, ptr, amt) + // this corresponds to the atomic.las intrinsic. + // *ptr + amt is stored to *ptr atomically. + // the return is always the original value in *ptr + ATOMIC_LAS, + + // Val, OUTCHAIN = ATOMIC_SWAP(INCHAIN, ptr, amt) + // this corresponds to the atomic.swap intrinsic. + // amt is stored to *ptr atomically. + // the return is always the original value in *ptr + ATOMIC_SWAP, + + // Val, OUTCHAIN = ATOMIC_LSS(INCHAIN, ptr, amt) + // this corresponds to the atomic.lss intrinsic. + // *ptr - amt is stored to *ptr atomically. + // the return is always the original value in *ptr + ATOMIC_LSS, - // DEBUG_LABEL - This node is used to mark a location in the code where a - // label should be generated for use by the debug information. It takes a - // token chain as input and then a unique id (provided by MachineDebugInfo.) - // It produces a token chain as output. - DEBUG_LABEL, + // Val, OUTCHAIN = ATOMIC_L[OpName]S(INCHAIN, ptr, amt) + // this corresponds to the atomic.[OpName] intrinsic. + // op(*ptr, amt) is stored to *ptr atomically. + // the return is always the original value in *ptr + ATOMIC_LOAD_AND, + ATOMIC_LOAD_OR, + ATOMIC_LOAD_XOR, + ATOMIC_LOAD_NAND, + ATOMIC_LOAD_MIN, + ATOMIC_LOAD_MAX, + ATOMIC_LOAD_UMIN, + ATOMIC_LOAD_UMAX, // BUILTIN_OP_END - This must be the last enum value in this list. BUILTIN_OP_END }; + /// Node predicates + + /// isBuildVectorAllOnes - Return true if the specified node is a + /// BUILD_VECTOR where all of the elements are ~0 or undef. + bool isBuildVectorAllOnes(const SDNode *N); + + /// isBuildVectorAllZeros - Return true if the specified node is a + /// BUILD_VECTOR where all of the elements are 0 or undef. + bool isBuildVectorAllZeros(const SDNode *N); + + /// isScalarToVector - Return true if the specified node is a + /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low + /// element is not an undef. + bool isScalarToVector(const SDNode *N); + + /// isDebugLabel - Return true if the specified node represents a debug + /// label (i.e. ISD::LABEL or TargetInstrInfo::LABEL node and third operand + /// is 0). + bool isDebugLabel(const SDNode *N); + + //===--------------------------------------------------------------------===// + /// MemIndexedMode enum - This enum defines the load / store indexed + /// addressing modes. + /// + /// UNINDEXED "Normal" load / store. The effective address is already + /// computed and is available in the base pointer. The offset + /// operand is always undefined. In addition to producing a + /// chain, an unindexed load produces one value (result of the + /// load); an unindexed store does not produce a value. + /// + /// PRE_INC Similar to the unindexed mode where the effective address is + /// PRE_DEC the value of the base pointer add / subtract the offset. + /// It considers the computation as being folded into the load / + /// store operation (i.e. the load / store does the address + /// computation as well as performing the memory transaction). + /// The base operand is always undefined. In addition to + /// producing a chain, pre-indexed load produces two values + /// (result of the load and the result of the address + /// computation); a pre-indexed store produces one value (result + /// of the address computation). + /// + /// POST_INC The effective address is the value of the base pointer. The + /// POST_DEC value of the offset operand is then added to / subtracted + /// from the base after memory transaction. In addition to + /// producing a chain, post-indexed load produces two values + /// (the result of the load and the result of the base +/- offset + /// computation); a post-indexed store produces one value (the + /// the result of the base +/- offset computation). + /// + enum MemIndexedMode { + UNINDEXED = 0, + PRE_INC, + PRE_DEC, + POST_INC, + POST_DEC, + LAST_INDEXED_MODE + }; + + //===--------------------------------------------------------------------===// + /// LoadExtType enum - This enum defines the three variants of LOADEXT + /// (load with extension). + /// + /// SEXTLOAD loads the integer operand and sign extends it to a larger + /// integer result type. + /// ZEXTLOAD loads the integer operand and zero extends it to a larger + /// integer result type. + /// EXTLOAD is used for three things: floating point extending loads, + /// integer extending loads [the top bits are undefined], and vector + /// extending loads [load into low elt]. + /// + enum LoadExtType { + NON_EXTLOAD = 0, + EXTLOAD, + SEXTLOAD, + ZEXTLOAD, + LAST_LOADX_TYPE + }; + //===--------------------------------------------------------------------===// /// ISD::CondCode enum - These are ordered carefully to make the bitfields /// below work out, when considering SETFALSE (something that never exists @@ -520,7 +813,7 @@ public: SDNode *Val; // The node defining the value we are using. unsigned ResNo; // Which return value of the node we are using. - SDOperand() : Val(0) {} + SDOperand() : Val(0), ResNo(0) {} SDOperand(SDNode *val, unsigned resno) : Val(val), ResNo(resno) {} bool operator==(const SDOperand &O) const { @@ -537,24 +830,63 @@ public: return SDOperand(Val, R); } + // isOperandOf - Return true if this node is an operand of N. + bool isOperandOf(SDNode *N) const; + /// getValueType - Return the ValueType of the referenced return value. /// - inline MVT::ValueType getValueType() const; + inline MVT getValueType() const; + + /// getValueSizeInBits - Returns the size of the value in bits. + /// + unsigned getValueSizeInBits() const { + return getValueType().getSizeInBits(); + } // Forwarding methods - These forward to the corresponding methods in SDNode. inline unsigned getOpcode() const; - inline unsigned getNodeDepth() const; inline unsigned getNumOperands() const; inline const SDOperand &getOperand(unsigned i) const; + inline uint64_t getConstantOperandVal(unsigned i) const; inline bool isTargetOpcode() const; inline unsigned getTargetOpcode() const; + + /// reachesChainWithoutSideEffects - Return true if this operand (which must + /// be a chain) reaches the specified operand without crossing any + /// side-effecting instructions. In practice, this looks through token + /// factors and non-volatile loads. In order to remain efficient, this only + /// looks a couple of nodes in, it does not do an exhaustive search. + bool reachesChainWithoutSideEffects(SDOperand Dest, + unsigned Depth = 2) const; + /// hasOneUse - Return true if there is exactly one operation using this /// result value of the defining operator. inline bool hasOneUse() const; + + /// use_empty - Return true if there are no operations using this + /// result value of the defining operator. + inline bool use_empty() const; }; +template<> struct DenseMapInfo { + static inline SDOperand getEmptyKey() { + return SDOperand((SDNode*)-1, -1U); + } + static inline SDOperand getTombstoneKey() { + return SDOperand((SDNode*)-1, 0); + } + static unsigned getHashValue(const SDOperand &Val) { + return ((unsigned)((uintptr_t)Val.Val >> 4) ^ + (unsigned)((uintptr_t)Val.Val >> 9)) + Val.ResNo; + } + static bool isEqual(const SDOperand &LHS, const SDOperand &RHS) { + return LHS == RHS; + } + static bool isPod() { return true; } +}; + /// simplify_type specializations - Allow casting operators to work directly on /// SDOperands as if they were SDNode*'s. template<> struct simplify_type { @@ -570,41 +902,175 @@ template<> struct simplify_type { } }; +/// SDUse - Represents a use of the SDNode referred by +/// the SDOperand. +class SDUse { + SDOperand Operand; + /// User - Parent node of this operand. + SDNode *User; + /// Prev, next - Pointers to the uses list of the SDNode referred by + /// this operand. + SDUse **Prev, *Next; +public: + friend class SDNode; + SDUse(): Operand(), User(NULL), Prev(NULL), Next(NULL) {} + + SDUse(SDNode *val, unsigned resno) : + Operand(val,resno), User(NULL), Prev(NULL), Next(NULL) {} + + SDUse& operator= (const SDOperand& Op) { + Operand = Op; + Next = NULL; + Prev = NULL; + return *this; + } + + SDUse& operator= (const SDUse& Op) { + Operand = Op; + Next = NULL; + Prev = NULL; + return *this; + } + + SDUse * getNext() { return Next; } + + SDNode *getUser() { return User; } + + void setUser(SDNode *p) { User = p; } + + operator SDOperand() const { return Operand; } + + const SDOperand& getSDOperand() const { return Operand; } + + SDNode* &getVal () { return Operand.Val; } + + bool operator==(const SDOperand &O) const { + return Operand == O; + } + + bool operator!=(const SDOperand &O) const { + return !(Operand == O); + } + + bool operator<(const SDOperand &O) const { + return Operand < O; + } + +protected: + void addToList(SDUse **List) { + Next = *List; + if (Next) Next->Prev = &Next; + Prev = List; + *List = this; + } + + void removeFromList() { + *Prev = Next; + if (Next) Next->Prev = Prev; + } +}; + + +/// simplify_type specializations - Allow casting operators to work directly on +/// SDOperands as if they were SDNode*'s. +template<> struct simplify_type { + typedef SDNode* SimpleType; + static SimpleType getSimplifiedValue(const SDUse &Val) { + return static_cast(Val.getSDOperand().Val); + } +}; +template<> struct simplify_type { + typedef SDNode* SimpleType; + static SimpleType getSimplifiedValue(const SDUse &Val) { + return static_cast(Val.getSDOperand().Val); + } +}; + + +/// SDOperandPtr - A helper SDOperand pointer class, that can handle +/// arrays of SDUse and arrays of SDOperand objects. This is required +/// in many places inside the SelectionDAG. +/// +class SDOperandPtr { + const SDOperand *ptr; // The pointer to the SDOperand object + int object_size; // The size of the object containg the SDOperand +public: + SDOperandPtr() : ptr(0), object_size(0) {} + + SDOperandPtr(SDUse * use_ptr) { + ptr = &use_ptr->getSDOperand(); + object_size = (int)sizeof(SDUse); + } + + SDOperandPtr(const SDOperand * op_ptr) { + ptr = op_ptr; + object_size = (int)sizeof(SDOperand); + } + + const SDOperand operator *() { return *ptr; } + const SDOperand *operator ->() { return ptr; } + SDOperandPtr operator ++ () { + ptr = (SDOperand*)((char *)ptr + object_size); + return *this; + } + + SDOperandPtr operator ++ (int) { + SDOperandPtr tmp = *this; + ptr = (SDOperand*)((char *)ptr + object_size); + return tmp; + } + + SDOperand operator[] (int idx) const { + return *(SDOperand*)((char*) ptr + object_size * idx); + } +}; /// SDNode - Represents one node in the SelectionDAG. /// -class SDNode { +class SDNode : public FoldingSetNode { +private: /// NodeType - The operation that this node performs. /// unsigned short NodeType; + + /// OperandsNeedDelete - This is true if OperandList was new[]'d. If true, + /// then they will be delete[]'d when the node is destroyed. + bool OperandsNeedDelete : 1; - /// NodeDepth - Node depth is defined as MAX(Node depth of children)+1. This - /// means that leaves have a depth of 1, things that use only leaves have a - /// depth of 2, etc. - unsigned short NodeDepth; + /// NodeId - Unique id per SDNode in the DAG. + int NodeId; /// OperandList - The values that are used by this operation. /// - SDOperand *OperandList; + SDUse *OperandList; /// ValueList - The types of the values this node defines. SDNode's may /// define multiple values simultaneously. - MVT::ValueType *ValueList; + const MVT *ValueList; /// NumOperands/NumValues - The number of entries in the Operand/Value list. unsigned short NumOperands, NumValues; + /// UsesSize - The size of the uses list. + unsigned UsesSize; + + /// Uses - List of uses for this SDNode. + SDUse *Uses; + /// Prev/Next pointers - These pointers form the linked list of of the /// AllNodes list in the current DAG. SDNode *Prev, *Next; friend struct ilist_traits; - /// Uses - These are all of the SDNode's that use a value produced by this - /// node. - std::vector Uses; + /// addUse - add SDUse to the list of uses. + void addUse(SDUse &U) { U.addToList(&Uses); } + + // Out-of-line virtual method to give class a home. + virtual void ANCHOR(); public: virtual ~SDNode() { assert(NumOperands == 0 && "Operand list not cleared before deletion"); + NodeType = ISD::DELETED_NODE; } //===--------------------------------------------------------------------===// @@ -617,39 +1083,133 @@ public: return NodeType - ISD::BUILTIN_OP_END; } - size_t use_size() const { return Uses.size(); } - bool use_empty() const { return Uses.empty(); } - bool hasOneUse() const { return Uses.size() == 1; } + size_t use_size() const { return UsesSize; } + bool use_empty() const { return Uses == NULL; } + bool hasOneUse() const { return use_size() == 1; } + + /// getNodeId - Return the unique node id. + /// + int getNodeId() const { return NodeId; } + + /// setNodeId - Set unique node id. + void setNodeId(int Id) { NodeId = Id; } + + /// use_iterator - This class provides iterator support for SDUse + /// operands that use a specific SDNode. + class use_iterator + : public forward_iterator { + SDUse *Op; + explicit use_iterator(SDUse *op) : Op(op) { + } + friend class SDNode; + public: + typedef forward_iterator::reference reference; + typedef forward_iterator::pointer pointer; + + use_iterator(const use_iterator &I) : Op(I.Op) {} + use_iterator() : Op(0) {} + + bool operator==(const use_iterator &x) const { + return Op == x.Op; + } + bool operator!=(const use_iterator &x) const { + return !operator==(x); + } + + /// atEnd - return true if this iterator is at the end of uses list. + bool atEnd() const { return Op == 0; } + + // Iterator traversal: forward iteration only. + use_iterator &operator++() { // Preincrement + assert(Op && "Cannot increment end iterator!"); + Op = Op->getNext(); + return *this; + } + + use_iterator operator++(int) { // Postincrement + use_iterator tmp = *this; ++*this; return tmp; + } + + + /// getOperandNum - Retrive a number of a current operand. + unsigned getOperandNum() const { + assert(Op && "Cannot dereference end iterator!"); + return (unsigned)(Op - Op->getUser()->OperandList); + } + + /// Retrieve a reference to the current operand. + SDUse &operator*() const { + assert(Op && "Cannot dereference end iterator!"); + return *Op; + } + + /// Retrieve a pointer to the current operand. + SDUse *operator->() const { + assert(Op && "Cannot dereference end iterator!"); + return Op; + } + }; + + /// use_begin/use_end - Provide iteration support to walk over all uses + /// of an SDNode. + + use_iterator use_begin(SDNode *node) const { + return use_iterator(node->Uses); + } + + use_iterator use_begin() const { + return use_iterator(Uses); + } - /// getNodeDepth - Return the distance from this node to the leaves in the - /// graph. The leaves have a depth of 1. - unsigned getNodeDepth() const { return NodeDepth; } + static use_iterator use_end() { return use_iterator(0); } - typedef std::vector::const_iterator use_iterator; - use_iterator use_begin() const { return Uses.begin(); } - use_iterator use_end() const { return Uses.end(); } /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the /// indicated value. This method ignores uses of other values defined by this /// operation. bool hasNUsesOfValue(unsigned NUses, unsigned Value) const; - // isOnlyUse - Return true if this node is the only use of N. - bool isOnlyUse(SDNode *N) const; + /// hasAnyUseOfValue - Return true if there are any use of the indicated + /// value. This method ignores uses of other values defined by this operation. + bool hasAnyUseOfValue(unsigned Value) const; + + /// isOnlyUseOf - Return true if this node is the only use of N. + /// + bool isOnlyUseOf(SDNode *N) const; + + /// isOperandOf - Return true if this node is an operand of N. + /// + bool isOperandOf(SDNode *N) const; + + /// isPredecessorOf - Return true if this node is a predecessor of N. This + /// node is either an operand of N or it can be reached by recursively + /// traversing up the operands. + /// NOTE: this is an expensive method. Use it carefully. + bool isPredecessorOf(SDNode *N) const; /// getNumOperands - Return the number of values used by this operation. /// unsigned getNumOperands() const { return NumOperands; } + /// getConstantOperandVal - Helper method returns the integer value of a + /// ConstantSDNode operand. + uint64_t getConstantOperandVal(unsigned Num) const; + const SDOperand &getOperand(unsigned Num) const { assert(Num < NumOperands && "Invalid child # of SDNode!"); - return OperandList[Num]; + return OperandList[Num].getSDOperand(); } - typedef const SDOperand* op_iterator; + + typedef SDUse* op_iterator; op_iterator op_begin() const { return OperandList; } op_iterator op_end() const { return OperandList+NumOperands; } + SDVTList getVTList() const { + SDVTList X = { ValueList, NumValues }; + return X; + }; + /// getNumValues - Return the number of values defined/returned by this /// operator. /// @@ -657,265 +1217,125 @@ public: /// getValueType - Return the type of a specified result. /// - MVT::ValueType getValueType(unsigned ResNo) const { + MVT getValueType(unsigned ResNo) const { assert(ResNo < NumValues && "Illegal result number!"); return ValueList[ResNo]; } - typedef const MVT::ValueType* value_iterator; + /// getValueSizeInBits - Returns MVT::getSizeInBits(getValueType(ResNo)). + /// + unsigned getValueSizeInBits(unsigned ResNo) const { + return getValueType(ResNo).getSizeInBits(); + } + + typedef const MVT* value_iterator; value_iterator value_begin() const { return ValueList; } value_iterator value_end() const { return ValueList+NumValues; } /// getOperationName - Return the opcode of this operation for printing. /// - const char* getOperationName(const SelectionDAG *G = 0) const; + std::string getOperationName(const SelectionDAG *G = 0) const; + static const char* getIndexedModeName(ISD::MemIndexedMode AM); void dump() const; void dump(const SelectionDAG *G) const; static bool classof(const SDNode *) { return true; } + /// Profile - Gather unique data for the node. + /// + void Profile(FoldingSetNodeID &ID); + protected: friend class SelectionDAG; /// getValueTypeList - Return a pointer to the specified value type. /// - static MVT::ValueType *getValueTypeList(MVT::ValueType VT); - - SDNode(unsigned NT, MVT::ValueType VT) : NodeType(NT), NodeDepth(1) { - OperandList = 0; NumOperands = 0; - ValueList = getValueTypeList(VT); - NumValues = 1; - Prev = 0; Next = 0; + static const MVT *getValueTypeList(MVT VT); + static SDVTList getSDVTList(MVT VT) { + SDVTList Ret = { getValueTypeList(VT), 1 }; + return Ret; } - SDNode(unsigned NT, SDOperand Op) - : NodeType(NT), NodeDepth(Op.Val->getNodeDepth()+1) { - OperandList = new SDOperand[1]; - OperandList[0] = Op; - NumOperands = 1; - Op.Val->Uses.push_back(this); - ValueList = 0; - NumValues = 0; - Prev = 0; Next = 0; - } - SDNode(unsigned NT, SDOperand N1, SDOperand N2) - : NodeType(NT) { - if (N1.Val->getNodeDepth() > N2.Val->getNodeDepth()) - NodeDepth = N1.Val->getNodeDepth()+1; - else - NodeDepth = N2.Val->getNodeDepth()+1; - OperandList = new SDOperand[2]; - OperandList[0] = N1; - OperandList[1] = N2; - NumOperands = 2; - N1.Val->Uses.push_back(this); N2.Val->Uses.push_back(this); - ValueList = 0; - NumValues = 0; - Prev = 0; Next = 0; - } - SDNode(unsigned NT, SDOperand N1, SDOperand N2, SDOperand N3) - : NodeType(NT) { - unsigned ND = N1.Val->getNodeDepth(); - if (ND < N2.Val->getNodeDepth()) - ND = N2.Val->getNodeDepth(); - if (ND < N3.Val->getNodeDepth()) - ND = N3.Val->getNodeDepth(); - NodeDepth = ND+1; - - OperandList = new SDOperand[3]; - OperandList[0] = N1; - OperandList[1] = N2; - OperandList[2] = N3; - NumOperands = 3; + + SDNode(unsigned Opc, SDVTList VTs, const SDOperand *Ops, unsigned NumOps) + : NodeType(Opc), NodeId(-1), UsesSize(0), Uses(NULL) { + OperandsNeedDelete = true; + NumOperands = NumOps; + OperandList = NumOps ? new SDUse[NumOperands] : 0; - N1.Val->Uses.push_back(this); N2.Val->Uses.push_back(this); - N3.Val->Uses.push_back(this); - ValueList = 0; - NumValues = 0; - Prev = 0; Next = 0; - } - SDNode(unsigned NT, SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4) - : NodeType(NT) { - unsigned ND = N1.Val->getNodeDepth(); - if (ND < N2.Val->getNodeDepth()) - ND = N2.Val->getNodeDepth(); - if (ND < N3.Val->getNodeDepth()) - ND = N3.Val->getNodeDepth(); - if (ND < N4.Val->getNodeDepth()) - ND = N4.Val->getNodeDepth(); - NodeDepth = ND+1; - - OperandList = new SDOperand[4]; - OperandList[0] = N1; - OperandList[1] = N2; - OperandList[2] = N3; - OperandList[3] = N4; - NumOperands = 4; + for (unsigned i = 0; i != NumOps; ++i) { + OperandList[i] = Ops[i]; + OperandList[i].setUser(this); + Ops[i].Val->addUse(OperandList[i]); + ++Ops[i].Val->UsesSize; + } - N1.Val->Uses.push_back(this); N2.Val->Uses.push_back(this); - N3.Val->Uses.push_back(this); N4.Val->Uses.push_back(this); - ValueList = 0; - NumValues = 0; + ValueList = VTs.VTs; + NumValues = VTs.NumVTs; Prev = 0; Next = 0; } - SDNode(unsigned Opc, const std::vector &Nodes) : NodeType(Opc) { - NumOperands = Nodes.size(); - OperandList = new SDOperand[NumOperands]; + + SDNode(unsigned Opc, SDVTList VTs, SDOperandPtr Ops, unsigned NumOps) + : NodeType(Opc), NodeId(-1), UsesSize(0), Uses(NULL) { + OperandsNeedDelete = true; + NumOperands = NumOps; + OperandList = NumOps ? new SDUse[NumOperands] : 0; - unsigned ND = 0; - for (unsigned i = 0, e = Nodes.size(); i != e; ++i) { - OperandList[i] = Nodes[i]; - SDNode *N = OperandList[i].Val; - N->Uses.push_back(this); - if (ND < N->getNodeDepth()) ND = N->getNodeDepth(); + for (unsigned i = 0; i != NumOps; ++i) { + OperandList[i] = Ops[i]; + OperandList[i].setUser(this); + Ops[i].Val->addUse(OperandList[i]); + ++Ops[i].Val->UsesSize; } - NodeDepth = ND+1; - ValueList = 0; - NumValues = 0; + + ValueList = VTs.VTs; + NumValues = VTs.NumVTs; Prev = 0; Next = 0; } - /// MorphNodeTo - This clears the return value and operands list, and sets the - /// opcode of the node to the specified value. This should only be used by - /// the SelectionDAG class. - void MorphNodeTo(unsigned Opc) { - NodeType = Opc; - ValueList = 0; - NumValues = 0; - - // Clear the operands list, updating used nodes to remove this from their - // use list. - for (op_iterator I = op_begin(), E = op_end(); I != E; ++I) - I->Val->removeUser(this); - delete [] OperandList; - OperandList = 0; + SDNode(unsigned Opc, SDVTList VTs) + : NodeType(Opc), NodeId(-1), UsesSize(0), Uses(NULL) { + OperandsNeedDelete = false; // Operands set with InitOperands. NumOperands = 0; + OperandList = 0; + ValueList = VTs.VTs; + NumValues = VTs.NumVTs; + Prev = 0; Next = 0; } - void setValueTypes(MVT::ValueType VT) { - assert(NumValues == 0 && "Should not have values yet!"); - ValueList = getValueTypeList(VT); - NumValues = 1; - } - void setValueTypes(MVT::ValueType *List, unsigned NumVal) { - assert(NumValues == 0 && "Should not have values yet!"); - ValueList = List; - NumValues = NumVal; + /// InitOperands - Initialize the operands list of this node with the + /// specified values, which are part of the node (thus they don't need to be + /// copied in or allocated). + void InitOperands(SDUse *Ops, unsigned NumOps) { + assert(OperandList == 0 && "Operands already set!"); + NumOperands = NumOps; + OperandList = Ops; + UsesSize = 0; + Uses = NULL; + + for (unsigned i = 0; i != NumOps; ++i) { + OperandList[i].setUser(this); + Ops[i].getVal()->addUse(OperandList[i]); + ++Ops[i].getVal()->UsesSize; + } } - void setOperands(SDOperand Op0) { - assert(NumOperands == 0 && "Should not have operands yet!"); - OperandList = new SDOperand[1]; - OperandList[0] = Op0; - NumOperands = 1; - Op0.Val->Uses.push_back(this); - } - void setOperands(SDOperand Op0, SDOperand Op1) { - assert(NumOperands == 0 && "Should not have operands yet!"); - OperandList = new SDOperand[2]; - OperandList[0] = Op0; - OperandList[1] = Op1; - NumOperands = 2; - Op0.Val->Uses.push_back(this); Op1.Val->Uses.push_back(this); - } - void setOperands(SDOperand Op0, SDOperand Op1, SDOperand Op2) { - assert(NumOperands == 0 && "Should not have operands yet!"); - OperandList = new SDOperand[3]; - OperandList[0] = Op0; - OperandList[1] = Op1; - OperandList[2] = Op2; - NumOperands = 3; - Op0.Val->Uses.push_back(this); Op1.Val->Uses.push_back(this); - Op2.Val->Uses.push_back(this); - } - void setOperands(SDOperand Op0, SDOperand Op1, SDOperand Op2, SDOperand Op3) { - assert(NumOperands == 0 && "Should not have operands yet!"); - OperandList = new SDOperand[4]; - OperandList[0] = Op0; - OperandList[1] = Op1; - OperandList[2] = Op2; - OperandList[3] = Op3; - NumOperands = 4; - Op0.Val->Uses.push_back(this); Op1.Val->Uses.push_back(this); - Op2.Val->Uses.push_back(this); Op3.Val->Uses.push_back(this); - } - void setOperands(SDOperand Op0, SDOperand Op1, SDOperand Op2, SDOperand Op3, - SDOperand Op4) { - assert(NumOperands == 0 && "Should not have operands yet!"); - OperandList = new SDOperand[5]; - OperandList[0] = Op0; - OperandList[1] = Op1; - OperandList[2] = Op2; - OperandList[3] = Op3; - OperandList[4] = Op4; - NumOperands = 5; - Op0.Val->Uses.push_back(this); Op1.Val->Uses.push_back(this); - Op2.Val->Uses.push_back(this); Op3.Val->Uses.push_back(this); - Op4.Val->Uses.push_back(this); - } - void setOperands(SDOperand Op0, SDOperand Op1, SDOperand Op2, SDOperand Op3, - SDOperand Op4, SDOperand Op5) { - assert(NumOperands == 0 && "Should not have operands yet!"); - OperandList = new SDOperand[6]; - OperandList[0] = Op0; - OperandList[1] = Op1; - OperandList[2] = Op2; - OperandList[3] = Op3; - OperandList[4] = Op4; - OperandList[5] = Op5; - NumOperands = 6; - Op0.Val->Uses.push_back(this); Op1.Val->Uses.push_back(this); - Op2.Val->Uses.push_back(this); Op3.Val->Uses.push_back(this); - Op4.Val->Uses.push_back(this); Op5.Val->Uses.push_back(this); - } - void setOperands(SDOperand Op0, SDOperand Op1, SDOperand Op2, SDOperand Op3, - SDOperand Op4, SDOperand Op5, SDOperand Op6) { - assert(NumOperands == 0 && "Should not have operands yet!"); - OperandList = new SDOperand[7]; - OperandList[0] = Op0; - OperandList[1] = Op1; - OperandList[2] = Op2; - OperandList[3] = Op3; - OperandList[4] = Op4; - OperandList[5] = Op5; - OperandList[6] = Op6; - NumOperands = 7; - Op0.Val->Uses.push_back(this); Op1.Val->Uses.push_back(this); - Op2.Val->Uses.push_back(this); Op3.Val->Uses.push_back(this); - Op4.Val->Uses.push_back(this); Op5.Val->Uses.push_back(this); - Op6.Val->Uses.push_back(this); - } - void setOperands(SDOperand Op0, SDOperand Op1, SDOperand Op2, SDOperand Op3, - SDOperand Op4, SDOperand Op5, SDOperand Op6, SDOperand Op7) { - assert(NumOperands == 0 && "Should not have operands yet!"); - OperandList = new SDOperand[8]; - OperandList[0] = Op0; - OperandList[1] = Op1; - OperandList[2] = Op2; - OperandList[3] = Op3; - OperandList[4] = Op4; - OperandList[5] = Op5; - OperandList[6] = Op6; - OperandList[7] = Op7; - NumOperands = 8; - Op0.Val->Uses.push_back(this); Op1.Val->Uses.push_back(this); - Op2.Val->Uses.push_back(this); Op3.Val->Uses.push_back(this); - Op4.Val->Uses.push_back(this); Op5.Val->Uses.push_back(this); - Op6.Val->Uses.push_back(this); Op7.Val->Uses.push_back(this); - } - - void addUser(SDNode *User) { - Uses.push_back(User); - } - void removeUser(SDNode *User) { - // Remove this user from the operand's use list. - for (unsigned i = Uses.size(); ; --i) { - assert(i != 0 && "Didn't find user!"); - if (Uses[i-1] == User) { - Uses[i-1] = Uses.back(); - Uses.pop_back(); - return; - } - } + /// MorphNodeTo - This frees the operands of the current node, resets the + /// opcode, types, and operands to the specified value. This should only be + /// used by the SelectionDAG class. + void MorphNodeTo(unsigned Opc, SDVTList L, + SDOperandPtr Ops, unsigned NumOps); + + void addUser(unsigned i, SDNode *User) { + assert(User->OperandList[i].getUser() && "Node without parent"); + addUse(User->OperandList[i]); + ++UsesSize; + } + + void removeUser(unsigned i, SDNode *User) { + assert(User->OperandList[i].getUser() && "Node without parent"); + SDUse &Op = User->OperandList[i]; + Op.removeFromList(); + --UsesSize; } }; @@ -925,10 +1345,7 @@ protected: inline unsigned SDOperand::getOpcode() const { return Val->getOpcode(); } -inline unsigned SDOperand::getNodeDepth() const { - return Val->getNodeDepth(); -} -inline MVT::ValueType SDOperand::getValueType() const { +inline MVT SDOperand::getValueType() const { return Val->getValueType(ResNo); } inline unsigned SDOperand::getNumOperands() const { @@ -937,6 +1354,9 @@ inline unsigned SDOperand::getNumOperands() const { inline const SDOperand &SDOperand::getOperand(unsigned i) const { return Val->getOperand(i); } +inline uint64_t SDOperand::getConstantOperandVal(unsigned i) const { + return Val->getConstantOperandVal(i); +} inline bool SDOperand::isTargetOpcode() const { return Val->isTargetOpcode(); } @@ -946,27 +1366,112 @@ inline unsigned SDOperand::getTargetOpcode() const { inline bool SDOperand::hasOneUse() const { return Val->hasNUsesOfValue(1, ResNo); } +inline bool SDOperand::use_empty() const { + return !Val->hasAnyUseOfValue(ResNo); +} + +/// UnarySDNode - This class is used for single-operand SDNodes. This is solely +/// to allow co-allocation of node operands with the node itself. +class UnarySDNode : public SDNode { + virtual void ANCHOR(); // Out-of-line virtual method to give class a home. + SDUse Op; +public: + UnarySDNode(unsigned Opc, SDVTList VTs, SDOperand X) + : SDNode(Opc, VTs) { + Op = X; + InitOperands(&Op, 1); + } +}; + +/// BinarySDNode - This class is used for two-operand SDNodes. This is solely +/// to allow co-allocation of node operands with the node itself. +class BinarySDNode : public SDNode { + virtual void ANCHOR(); // Out-of-line virtual method to give class a home. + SDUse Ops[2]; +public: + BinarySDNode(unsigned Opc, SDVTList VTs, SDOperand X, SDOperand Y) + : SDNode(Opc, VTs) { + Ops[0] = X; + Ops[1] = Y; + InitOperands(Ops, 2); + } +}; + +/// TernarySDNode - This class is used for three-operand SDNodes. This is solely +/// to allow co-allocation of node operands with the node itself. +class TernarySDNode : public SDNode { + virtual void ANCHOR(); // Out-of-line virtual method to give class a home. + SDUse Ops[3]; +public: + TernarySDNode(unsigned Opc, SDVTList VTs, SDOperand X, SDOperand Y, + SDOperand Z) + : SDNode(Opc, VTs) { + Ops[0] = X; + Ops[1] = Y; + Ops[2] = Z; + InitOperands(Ops, 3); + } +}; + /// HandleSDNode - This class is used to form a handle around another node that /// is persistant and is updated across invocations of replaceAllUsesWith on its /// operand. This node should be directly created by end-users and not added to /// the AllNodes list. class HandleSDNode : public SDNode { + virtual void ANCHOR(); // Out-of-line virtual method to give class a home. + SDUse Op; public: - HandleSDNode(SDOperand X) : SDNode(ISD::HANDLENODE, X) {} - ~HandleSDNode() { - MorphNodeTo(ISD::HANDLENODE); // Drops operand uses. + // FIXME: Remove the "noinline" attribute once is + // fixed. +#ifdef __GNUC__ + explicit __attribute__((__noinline__)) HandleSDNode(SDOperand X) +#else + explicit HandleSDNode(SDOperand X) +#endif + : SDNode(ISD::HANDLENODE, getSDVTList(MVT::Other)) { + Op = X; + InitOperands(&Op, 1); } - - SDOperand getValue() const { return getOperand(0); } + ~HandleSDNode(); + SDUse getValue() const { return Op; } +}; + +class AtomicSDNode : public SDNode { + virtual void ANCHOR(); // Out-of-line virtual method to give class a home. + SDUse Ops[4]; + MVT OrigVT; +public: + AtomicSDNode(unsigned Opc, SDVTList VTL, SDOperand Chain, SDOperand Ptr, + SDOperand Cmp, SDOperand Swp, MVT VT) + : SDNode(Opc, VTL) { + Ops[0] = Chain; + Ops[1] = Ptr; + Ops[2] = Swp; + Ops[3] = Cmp; + InitOperands(Ops, 4); + OrigVT=VT; + } + AtomicSDNode(unsigned Opc, SDVTList VTL, SDOperand Chain, SDOperand Ptr, + SDOperand Val, MVT VT) + : SDNode(Opc, VTL) { + Ops[0] = Chain; + Ops[1] = Ptr; + Ops[2] = Val; + InitOperands(Ops, 3); + OrigVT=VT; + } + MVT getVT() const { return OrigVT; } + bool isCompareAndSwap() const { return getOpcode() == ISD::ATOMIC_LCS; } }; class StringSDNode : public SDNode { std::string Value; + virtual void ANCHOR(); // Out-of-line virtual method to give class a home. protected: friend class SelectionDAG; - StringSDNode(const std::string &val) - : SDNode(ISD::STRING, MVT::Other), Value(val) { + explicit StringSDNode(const std::string &val) + : SDNode(ISD::STRING, getSDVTList(MVT::Other)), Value(val) { } public: const std::string &getValue() const { return Value; } @@ -977,26 +1482,27 @@ public: }; class ConstantSDNode : public SDNode { - uint64_t Value; + APInt Value; + virtual void ANCHOR(); // Out-of-line virtual method to give class a home. protected: friend class SelectionDAG; - ConstantSDNode(bool isTarget, uint64_t val, MVT::ValueType VT) - : SDNode(isTarget ? ISD::TargetConstant : ISD::Constant, VT), Value(val) { + ConstantSDNode(bool isTarget, const APInt &val, MVT VT) + : SDNode(isTarget ? ISD::TargetConstant : ISD::Constant, getSDVTList(VT)), + Value(val) { } public: - uint64_t getValue() const { return Value; } + const APInt &getAPIntValue() const { return Value; } + uint64_t getValue() const { return Value.getZExtValue(); } int64_t getSignExtended() const { - unsigned Bits = MVT::getSizeInBits(getValueType(0)); - return ((int64_t)Value << (64-Bits)) >> (64-Bits); + unsigned Bits = getValueType(0).getSizeInBits(); + return ((int64_t)Value.getZExtValue() << (64-Bits)) >> (64-Bits); } bool isNullValue() const { return Value == 0; } bool isAllOnesValue() const { - int NumBits = MVT::getSizeInBits(getValueType(0)); - if (NumBits == 64) return Value+1 == 0; - return Value == (1ULL << NumBits)-1; + return Value == getValueType(0).getIntegerVTBitMask(); } static bool classof(const ConstantSDNode *) { return true; } @@ -1007,22 +1513,37 @@ public: }; class ConstantFPSDNode : public SDNode { - double Value; + APFloat Value; + virtual void ANCHOR(); // Out-of-line virtual method to give class a home. protected: friend class SelectionDAG; - ConstantFPSDNode(bool isTarget, double val, MVT::ValueType VT) - : SDNode(isTarget ? ISD::TargetConstantFP : ISD::ConstantFP, VT), - Value(val) { + ConstantFPSDNode(bool isTarget, const APFloat& val, MVT VT) + : SDNode(isTarget ? ISD::TargetConstantFP : ISD::ConstantFP, + getSDVTList(VT)), Value(val) { } public: - double getValue() const { return Value; } + const APFloat& getValueAPF() const { return Value; } /// isExactlyValue - We don't rely on operator== working on double values, as /// it returns true for things that are clearly not equal, like -0.0 and 0.0. /// As such, this method can be used to do an exact bit-for-bit comparison of /// two floating point values. - bool isExactlyValue(double V) const; + + /// We leave the version with the double argument here because it's just so + /// convenient to write "2.0" and the like. Without this function we'd + /// have to duplicate its logic everywhere it's called. + bool isExactlyValue(double V) const { + // convert is not supported on this type + if (&Value.getSemantics() == &APFloat::PPCDoubleDouble) + return false; + APFloat Tmp(V); + Tmp.convert(Value.getSemantics(), APFloat::rmNearestTiesToEven); + return isExactlyValue(Tmp); + } + bool isExactlyValue(const APFloat& V) const; + + bool isValueValidForType(MVT VT, const APFloat& Val); static bool classof(const ConstantFPSDNode *) { return true; } static bool classof(const SDNode *N) { @@ -1034,14 +1555,10 @@ public: class GlobalAddressSDNode : public SDNode { GlobalValue *TheGlobal; int Offset; + virtual void ANCHOR(); // Out-of-line virtual method to give class a home. protected: friend class SelectionDAG; - GlobalAddressSDNode(bool isTarget, const GlobalValue *GA, MVT::ValueType VT, - int o=0) - : SDNode(isTarget ? ISD::TargetGlobalAddress : ISD::GlobalAddress, VT), - Offset(o) { - TheGlobal = const_cast(GA); - } + GlobalAddressSDNode(bool isTarget, const GlobalValue *GA, MVT VT, int o = 0); public: GlobalValue *getGlobal() const { return TheGlobal; } @@ -1050,17 +1567,21 @@ public: static bool classof(const GlobalAddressSDNode *) { return true; } static bool classof(const SDNode *N) { return N->getOpcode() == ISD::GlobalAddress || - N->getOpcode() == ISD::TargetGlobalAddress; + N->getOpcode() == ISD::TargetGlobalAddress || + N->getOpcode() == ISD::GlobalTLSAddress || + N->getOpcode() == ISD::TargetGlobalTLSAddress; } }; - class FrameIndexSDNode : public SDNode { int FI; + virtual void ANCHOR(); // Out-of-line virtual method to give class a home. protected: friend class SelectionDAG; - FrameIndexSDNode(int fi, MVT::ValueType VT, bool isTarg) - : SDNode(isTarg ? ISD::TargetFrameIndex : ISD::FrameIndex, VT), FI(fi) {} + FrameIndexSDNode(int fi, MVT VT, bool isTarg) + : SDNode(isTarg ? ISD::TargetFrameIndex : ISD::FrameIndex, getSDVTList(VT)), + FI(fi) { + } public: int getIndex() const { return FI; } @@ -1072,29 +1593,90 @@ public: } }; +class JumpTableSDNode : public SDNode { + int JTI; + virtual void ANCHOR(); // Out-of-line virtual method to give class a home. +protected: + friend class SelectionDAG; + JumpTableSDNode(int jti, MVT VT, bool isTarg) + : SDNode(isTarg ? ISD::TargetJumpTable : ISD::JumpTable, getSDVTList(VT)), + JTI(jti) { + } +public: + + int getIndex() const { return JTI; } + + static bool classof(const JumpTableSDNode *) { return true; } + static bool classof(const SDNode *N) { + return N->getOpcode() == ISD::JumpTable || + N->getOpcode() == ISD::TargetJumpTable; + } +}; + class ConstantPoolSDNode : public SDNode { - Constant *C; - int Offset; + union { + Constant *ConstVal; + MachineConstantPoolValue *MachineCPVal; + } Val; + int Offset; // It's a MachineConstantPoolValue if top bit is set. unsigned Alignment; + virtual void ANCHOR(); // Out-of-line virtual method to give class a home. protected: friend class SelectionDAG; - ConstantPoolSDNode(bool isTarget, Constant *c, MVT::ValueType VT, - int o=0) - : SDNode(isTarget ? ISD::TargetConstantPool : ISD::ConstantPool, VT), - C(c), Offset(o), Alignment(0) {} - ConstantPoolSDNode(bool isTarget, Constant *c, MVT::ValueType VT, int o, - unsigned Align) - : SDNode(isTarget ? ISD::TargetConstantPool : ISD::ConstantPool, VT), - C(c), Offset(o), Alignment(Align) {} + ConstantPoolSDNode(bool isTarget, Constant *c, MVT VT, int o=0) + : SDNode(isTarget ? ISD::TargetConstantPool : ISD::ConstantPool, + getSDVTList(VT)), Offset(o), Alignment(0) { + assert((int)Offset >= 0 && "Offset is too large"); + Val.ConstVal = c; + } + ConstantPoolSDNode(bool isTarget, Constant *c, MVT VT, int o, unsigned Align) + : SDNode(isTarget ? ISD::TargetConstantPool : ISD::ConstantPool, + getSDVTList(VT)), Offset(o), Alignment(Align) { + assert((int)Offset >= 0 && "Offset is too large"); + Val.ConstVal = c; + } + ConstantPoolSDNode(bool isTarget, MachineConstantPoolValue *v, + MVT VT, int o=0) + : SDNode(isTarget ? ISD::TargetConstantPool : ISD::ConstantPool, + getSDVTList(VT)), Offset(o), Alignment(0) { + assert((int)Offset >= 0 && "Offset is too large"); + Val.MachineCPVal = v; + Offset |= 1 << (sizeof(unsigned)*8-1); + } + ConstantPoolSDNode(bool isTarget, MachineConstantPoolValue *v, + MVT VT, int o, unsigned Align) + : SDNode(isTarget ? ISD::TargetConstantPool : ISD::ConstantPool, + getSDVTList(VT)), Offset(o), Alignment(Align) { + assert((int)Offset >= 0 && "Offset is too large"); + Val.MachineCPVal = v; + Offset |= 1 << (sizeof(unsigned)*8-1); + } public: - Constant *get() const { return C; } - int getOffset() const { return Offset; } + bool isMachineConstantPoolEntry() const { + return (int)Offset < 0; + } + + Constant *getConstVal() const { + assert(!isMachineConstantPoolEntry() && "Wrong constantpool type"); + return Val.ConstVal; + } + + MachineConstantPoolValue *getMachineCPVal() const { + assert(isMachineConstantPoolEntry() && "Wrong constantpool type"); + return Val.MachineCPVal; + } + + int getOffset() const { + return Offset & ~(1 << (sizeof(unsigned)*8-1)); + } // Return the alignment of this constant pool object, which is either 0 (for // default alignment) or log2 of the desired value. unsigned getAlignment() const { return Alignment; } + const Type *getType() const; + static bool classof(const ConstantPoolSDNode *) { return true; } static bool classof(const SDNode *N) { return N->getOpcode() == ISD::ConstantPool || @@ -1104,10 +1686,12 @@ public: class BasicBlockSDNode : public SDNode { MachineBasicBlock *MBB; + virtual void ANCHOR(); // Out-of-line virtual method to give class a home. protected: friend class SelectionDAG; - BasicBlockSDNode(MachineBasicBlock *mbb) - : SDNode(ISD::BasicBlock, MVT::Other), MBB(mbb) {} + explicit BasicBlockSDNode(MachineBasicBlock *mbb) + : SDNode(ISD::BasicBlock, getSDVTList(MVT::Other)), MBB(mbb) { + } public: MachineBasicBlock *getBasicBlock() const { return MBB; } @@ -1118,17 +1702,26 @@ public: } }; +/// SrcValueSDNode - An SDNode that holds an arbitrary LLVM IR Value. This is +/// used when the SelectionDAG needs to make a simple reference to something +/// in the LLVM IR representation. +/// +/// Note that this is not used for carrying alias information; that is done +/// with MemOperandSDNode, which includes a Value which is required to be a +/// pointer, and several other fields specific to memory references. +/// class SrcValueSDNode : public SDNode { const Value *V; - int offset; + virtual void ANCHOR(); // Out-of-line virtual method to give class a home. protected: friend class SelectionDAG; - SrcValueSDNode(const Value* v, int o) - : SDNode(ISD::SRCVALUE, MVT::Other), V(v), offset(o) {} + /// Create a SrcValue for a general value. + explicit SrcValueSDNode(const Value *v) + : SDNode(ISD::SRCVALUE, getSDVTList(MVT::Other)), V(v) {} public: + /// getValue - return the contained Value. const Value *getValue() const { return V; } - int getOffset() const { return offset; } static bool classof(const SrcValueSDNode *) { return true; } static bool classof(const SDNode *N) { @@ -1137,12 +1730,37 @@ public: }; +/// MemOperandSDNode - An SDNode that holds a MachineMemOperand. This is +/// used to represent a reference to memory after ISD::LOAD +/// and ISD::STORE have been lowered. +/// +class MemOperandSDNode : public SDNode { + virtual void ANCHOR(); // Out-of-line virtual method to give class a home. +protected: + friend class SelectionDAG; + /// Create a MachineMemOperand node + explicit MemOperandSDNode(const MachineMemOperand &mo) + : SDNode(ISD::MEMOPERAND, getSDVTList(MVT::Other)), MO(mo) {} + +public: + /// MO - The contained MachineMemOperand. + const MachineMemOperand MO; + + static bool classof(const MemOperandSDNode *) { return true; } + static bool classof(const SDNode *N) { + return N->getOpcode() == ISD::MEMOPERAND; + } +}; + + class RegisterSDNode : public SDNode { unsigned Reg; + virtual void ANCHOR(); // Out-of-line virtual method to give class a home. protected: friend class SelectionDAG; - RegisterSDNode(unsigned reg, MVT::ValueType VT) - : SDNode(ISD::Register, VT), Reg(reg) {} + RegisterSDNode(unsigned reg, MVT VT) + : SDNode(ISD::Register, getSDVTList(VT)), Reg(reg) { + } public: unsigned getReg() const { return Reg; } @@ -1155,12 +1773,13 @@ public: class ExternalSymbolSDNode : public SDNode { const char *Symbol; + virtual void ANCHOR(); // Out-of-line virtual method to give class a home. protected: friend class SelectionDAG; - ExternalSymbolSDNode(bool isTarget, const char *Sym, MVT::ValueType VT) - : SDNode(isTarget ? ISD::TargetExternalSymbol : ISD::ExternalSymbol, VT), - Symbol(Sym) { - } + ExternalSymbolSDNode(bool isTarget, const char *Sym, MVT VT) + : SDNode(isTarget ? ISD::TargetExternalSymbol : ISD::ExternalSymbol, + getSDVTList(VT)), Symbol(Sym) { + } public: const char *getSymbol() const { return Symbol; } @@ -1174,10 +1793,11 @@ public: class CondCodeSDNode : public SDNode { ISD::CondCode Condition; + virtual void ANCHOR(); // Out-of-line virtual method to give class a home. protected: friend class SelectionDAG; - CondCodeSDNode(ISD::CondCode Cond) - : SDNode(ISD::CONDCODE, MVT::Other), Condition(Cond) { + explicit CondCodeSDNode(ISD::CondCode Cond) + : SDNode(ISD::CONDCODE, getSDVTList(MVT::Other)), Condition(Cond) { } public: @@ -1189,17 +1809,122 @@ public: } }; -/// VTSDNode - This class is used to represent MVT::ValueType's, which are used +namespace ISD { + struct ArgFlagsTy { + private: + static const uint64_t NoFlagSet = 0ULL; + static const uint64_t ZExt = 1ULL<<0; ///< Zero extended + static const uint64_t ZExtOffs = 0; + static const uint64_t SExt = 1ULL<<1; ///< Sign extended + static const uint64_t SExtOffs = 1; + static const uint64_t InReg = 1ULL<<2; ///< Passed in register + static const uint64_t InRegOffs = 2; + static const uint64_t SRet = 1ULL<<3; ///< Hidden struct-ret ptr + static const uint64_t SRetOffs = 3; + static const uint64_t ByVal = 1ULL<<4; ///< Struct passed by value + static const uint64_t ByValOffs = 4; + static const uint64_t Nest = 1ULL<<5; ///< Nested fn static chain + static const uint64_t NestOffs = 5; + static const uint64_t ByValAlign = 0xFULL << 6; //< Struct alignment + static const uint64_t ByValAlignOffs = 6; + static const uint64_t Split = 1ULL << 10; + static const uint64_t SplitOffs = 10; + static const uint64_t OrigAlign = 0x1FULL<<27; + static const uint64_t OrigAlignOffs = 27; + static const uint64_t ByValSize = 0xffffffffULL << 32; //< Struct size + static const uint64_t ByValSizeOffs = 32; + + static const uint64_t One = 1ULL; //< 1 of this type, for shifts + + uint64_t Flags; + public: + ArgFlagsTy() : Flags(0) { } + + bool isZExt() const { return Flags & ZExt; } + void setZExt() { Flags |= One << ZExtOffs; } + + bool isSExt() const { return Flags & SExt; } + void setSExt() { Flags |= One << SExtOffs; } + + bool isInReg() const { return Flags & InReg; } + void setInReg() { Flags |= One << InRegOffs; } + + bool isSRet() const { return Flags & SRet; } + void setSRet() { Flags |= One << SRetOffs; } + + bool isByVal() const { return Flags & ByVal; } + void setByVal() { Flags |= One << ByValOffs; } + + bool isNest() const { return Flags & Nest; } + void setNest() { Flags |= One << NestOffs; } + + unsigned getByValAlign() const { + return (unsigned) + ((One << ((Flags & ByValAlign) >> ByValAlignOffs)) / 2); + } + void setByValAlign(unsigned A) { + Flags = (Flags & ~ByValAlign) | + (uint64_t(Log2_32(A) + 1) << ByValAlignOffs); + } + + bool isSplit() const { return Flags & Split; } + void setSplit() { Flags |= One << SplitOffs; } + + unsigned getOrigAlign() const { + return (unsigned) + ((One << ((Flags & OrigAlign) >> OrigAlignOffs)) / 2); + } + void setOrigAlign(unsigned A) { + Flags = (Flags & ~OrigAlign) | + (uint64_t(Log2_32(A) + 1) << OrigAlignOffs); + } + + unsigned getByValSize() const { + return (unsigned)((Flags & ByValSize) >> ByValSizeOffs); + } + void setByValSize(unsigned S) { + Flags = (Flags & ~ByValSize) | (uint64_t(S) << ByValSizeOffs); + } + + /// getArgFlagsString - Returns the flags as a string, eg: "zext align:4". + std::string getArgFlagsString(); + + /// getRawBits - Represent the flags as a bunch of bits. + uint64_t getRawBits() const { return Flags; } + }; +} + +/// ARG_FLAGSSDNode - Leaf node holding parameter flags. +class ARG_FLAGSSDNode : public SDNode { + ISD::ArgFlagsTy TheFlags; + virtual void ANCHOR(); // Out-of-line virtual method to give class a home. +protected: + friend class SelectionDAG; + explicit ARG_FLAGSSDNode(ISD::ArgFlagsTy Flags) + : SDNode(ISD::ARG_FLAGS, getSDVTList(MVT::Other)), TheFlags(Flags) { + } +public: + ISD::ArgFlagsTy getArgFlags() const { return TheFlags; } + + static bool classof(const ARG_FLAGSSDNode *) { return true; } + static bool classof(const SDNode *N) { + return N->getOpcode() == ISD::ARG_FLAGS; + } +}; + +/// VTSDNode - This class is used to represent MVT's, which are used /// to parameterize some operations. class VTSDNode : public SDNode { - MVT::ValueType ValueType; + MVT ValueType; + virtual void ANCHOR(); // Out-of-line virtual method to give class a home. protected: friend class SelectionDAG; - VTSDNode(MVT::ValueType VT) - : SDNode(ISD::VALUETYPE, MVT::Other), ValueType(VT) {} + explicit VTSDNode(MVT VT) + : SDNode(ISD::VALUETYPE, getSDVTList(MVT::Other)), ValueType(VT) { + } public: - MVT::ValueType getVT() const { return ValueType; } + MVT getVT() const { return ValueType; } static bool classof(const VTSDNode *) { return true; } static bool classof(const SDNode *N) { @@ -1207,6 +1932,139 @@ public: } }; +/// LSBaseSDNode - Base class for LoadSDNode and StoreSDNode +/// +class LSBaseSDNode : public SDNode { +private: + // AddrMode - unindexed, pre-indexed, post-indexed. + ISD::MemIndexedMode AddrMode; + + // MemoryVT - VT of in-memory value. + MVT MemoryVT; + + //! SrcValue - Memory location for alias analysis. + const Value *SrcValue; + + //! SVOffset - Memory location offset. + int SVOffset; + + //! Alignment - Alignment of memory location in bytes. + unsigned Alignment; + + //! IsVolatile - True if the store is volatile. + bool IsVolatile; +protected: + //! Operand array for load and store + /*! + \note Moving this array to the base class captures more + common functionality shared between LoadSDNode and + StoreSDNode + */ + SDUse Ops[4]; +public: + LSBaseSDNode(ISD::NodeType NodeTy, SDOperand *Operands, unsigned numOperands, + SDVTList VTs, ISD::MemIndexedMode AM, MVT VT, + const Value *SV, int SVO, unsigned Align, bool Vol) + : SDNode(NodeTy, VTs), + AddrMode(AM), MemoryVT(VT), + SrcValue(SV), SVOffset(SVO), Alignment(Align), IsVolatile(Vol) { + for (unsigned i = 0; i != numOperands; ++i) + Ops[i] = Operands[i]; + InitOperands(Ops, numOperands); + assert(Align != 0 && "Loads and stores should have non-zero aligment"); + assert((getOffset().getOpcode() == ISD::UNDEF || isIndexed()) && + "Only indexed loads and stores have a non-undef offset operand"); + } + + const SDOperand &getChain() const { return getOperand(0); } + const SDOperand &getBasePtr() const { + return getOperand(getOpcode() == ISD::LOAD ? 1 : 2); + } + const SDOperand &getOffset() const { + return getOperand(getOpcode() == ISD::LOAD ? 2 : 3); + } + + const Value *getSrcValue() const { return SrcValue; } + int getSrcValueOffset() const { return SVOffset; } + unsigned getAlignment() const { return Alignment; } + MVT getMemoryVT() const { return MemoryVT; } + bool isVolatile() const { return IsVolatile; } + + ISD::MemIndexedMode getAddressingMode() const { return AddrMode; } + + /// isIndexed - Return true if this is a pre/post inc/dec load/store. + bool isIndexed() const { return AddrMode != ISD::UNINDEXED; } + + /// isUnindexed - Return true if this is NOT a pre/post inc/dec load/store. + bool isUnindexed() const { return AddrMode == ISD::UNINDEXED; } + + /// getMemOperand - Return a MachineMemOperand object describing the memory + /// reference performed by this load or store. + MachineMemOperand getMemOperand() const; + + static bool classof(const LSBaseSDNode *) { return true; } + static bool classof(const SDNode *N) { + return N->getOpcode() == ISD::LOAD || + N->getOpcode() == ISD::STORE; + } +}; + +/// LoadSDNode - This class is used to represent ISD::LOAD nodes. +/// +class LoadSDNode : public LSBaseSDNode { + virtual void ANCHOR(); // Out-of-line virtual method to give class a home. + + // ExtType - non-ext, anyext, sext, zext. + ISD::LoadExtType ExtType; + +protected: + friend class SelectionDAG; + LoadSDNode(SDOperand *ChainPtrOff, SDVTList VTs, + ISD::MemIndexedMode AM, ISD::LoadExtType ETy, MVT LVT, + const Value *SV, int O=0, unsigned Align=0, bool Vol=false) + : LSBaseSDNode(ISD::LOAD, ChainPtrOff, 3, + VTs, AM, LVT, SV, O, Align, Vol), + ExtType(ETy) {} +public: + + ISD::LoadExtType getExtensionType() const { return ExtType; } + const SDOperand &getBasePtr() const { return getOperand(1); } + const SDOperand &getOffset() const { return getOperand(2); } + + static bool classof(const LoadSDNode *) { return true; } + static bool classof(const SDNode *N) { + return N->getOpcode() == ISD::LOAD; + } +}; + +/// StoreSDNode - This class is used to represent ISD::STORE nodes. +/// +class StoreSDNode : public LSBaseSDNode { + virtual void ANCHOR(); // Out-of-line virtual method to give class a home. + + // IsTruncStore - True if the op does a truncation before store. + bool IsTruncStore; +protected: + friend class SelectionDAG; + StoreSDNode(SDOperand *ChainValuePtrOff, SDVTList VTs, + ISD::MemIndexedMode AM, bool isTrunc, MVT SVT, + const Value *SV, int O=0, unsigned Align=0, bool Vol=false) + : LSBaseSDNode(ISD::STORE, ChainValuePtrOff, 4, + VTs, AM, SVT, SV, O, Align, Vol), + IsTruncStore(isTrunc) {} +public: + + bool isTruncatingStore() const { return IsTruncStore; } + const SDOperand &getValue() const { return getOperand(1); } + const SDOperand &getBasePtr() const { return getOperand(2); } + const SDOperand &getOffset() const { return getOperand(3); } + + static bool classof(const StoreSDNode *) { return true; } + static bool classof(const SDNode *N) { + return N->getOpcode() == ISD::STORE; + } +}; + class SDNodeIterator : public forward_iterator { SDNode *Node; @@ -1268,19 +2126,92 @@ struct ilist_traits { static void setNext(SDNode *N, SDNode *Next) { N->Next = Next; } static SDNode *createSentinel() { - return new SDNode(ISD::EntryToken, MVT::Other); + return new SDNode(ISD::EntryToken, SDNode::getSDVTList(MVT::Other)); } static void destroySentinel(SDNode *N) { delete N; } //static SDNode *createNode(const SDNode &V) { return new SDNode(V); } - void addNodeToList(SDNode *NTy) {} - void removeNodeFromList(SDNode *NTy) {} - void transferNodesFromList(iplist &L2, - const ilist_iterator &X, - const ilist_iterator &Y) {} + void addNodeToList(SDNode *) {} + void removeNodeFromList(SDNode *) {} + void transferNodesFromList(iplist &, + const ilist_iterator &, + const ilist_iterator &) {} }; +namespace ISD { + /// isNormalLoad - Returns true if the specified node is a non-extending + /// and unindexed load. + inline bool isNormalLoad(const SDNode *N) { + const LoadSDNode *Ld = dyn_cast(N); + return Ld && Ld->getExtensionType() == ISD::NON_EXTLOAD && + Ld->getAddressingMode() == ISD::UNINDEXED; + } + + /// isNON_EXTLoad - Returns true if the specified node is a non-extending + /// load. + inline bool isNON_EXTLoad(const SDNode *N) { + return isa(N) && + cast(N)->getExtensionType() == ISD::NON_EXTLOAD; + } + + /// isEXTLoad - Returns true if the specified node is a EXTLOAD. + /// + inline bool isEXTLoad(const SDNode *N) { + return isa(N) && + cast(N)->getExtensionType() == ISD::EXTLOAD; + } + + /// isSEXTLoad - Returns true if the specified node is a SEXTLOAD. + /// + inline bool isSEXTLoad(const SDNode *N) { + return isa(N) && + cast(N)->getExtensionType() == ISD::SEXTLOAD; + } + + /// isZEXTLoad - Returns true if the specified node is a ZEXTLOAD. + /// + inline bool isZEXTLoad(const SDNode *N) { + return isa(N) && + cast(N)->getExtensionType() == ISD::ZEXTLOAD; + } + + /// isUNINDEXEDLoad - Returns true if the specified node is an unindexed load. + /// + inline bool isUNINDEXEDLoad(const SDNode *N) { + return isa(N) && + cast(N)->getAddressingMode() == ISD::UNINDEXED; + } + + /// isNormalStore - Returns true if the specified node is a non-truncating + /// and unindexed store. + inline bool isNormalStore(const SDNode *N) { + const StoreSDNode *St = dyn_cast(N); + return St && !St->isTruncatingStore() && + St->getAddressingMode() == ISD::UNINDEXED; + } + + /// isNON_TRUNCStore - Returns true if the specified node is a non-truncating + /// store. + inline bool isNON_TRUNCStore(const SDNode *N) { + return isa(N) && !cast(N)->isTruncatingStore(); + } + + /// isTRUNCStore - Returns true if the specified node is a truncating + /// store. + inline bool isTRUNCStore(const SDNode *N) { + return isa(N) && cast(N)->isTruncatingStore(); + } + + /// isUNINDEXEDStore - Returns true if the specified node is an + /// unindexed store. + inline bool isUNINDEXEDStore(const SDNode *N) { + return isa(N) && + cast(N)->getAddressingMode() == ISD::UNINDEXED; + } +} + + } // end llvm namespace #endif