X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FSelectionDAGNodes.h;h=35993d986aa6711cd7cd12beab2fd91847bec634;hb=ea61c358720aa6c7a159d51658b34276316aa841;hp=e21cdb389906b04af6675b944bb43c3170435b1a;hpb=bb66a9f960ca3068feed9ce1fb84bf8fa6214618;p=oota-llvm.git diff --git a/include/llvm/CodeGen/SelectionDAGNodes.h b/include/llvm/CodeGen/SelectionDAGNodes.h index e21cdb38990..35993d986aa 100644 --- a/include/llvm/CodeGen/SelectionDAGNodes.h +++ b/include/llvm/CodeGen/SelectionDAGNodes.h @@ -1,12 +1,12 @@ //===-- llvm/CodeGen/SelectionDAGNodes.h - SelectionDAG Nodes ---*- C++ -*-===// -// +// // 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 declares the SDNode class and derived classes, which are used to // represent the nodes and operations present in a SelectionDAG. These nodes // and operations are machine code level operations, with some similarities to @@ -20,7 +20,10 @@ #define LLVM_CODEGEN_SELECTIONDAGNODES_H #include "llvm/CodeGen/ValueTypes.h" -#include "llvm/support/DataTypes.h" +#include "llvm/ADT/GraphTraits.h" +#include "llvm/ADT/GraphTraits.h" +#include "llvm/ADT/iterator" +#include "llvm/Support/DataTypes.h" #include #include @@ -41,22 +44,39 @@ namespace ISD { /// SelectionDAG. /// enum NodeType { - // Leaf nodes - EntryToken, Constant, ConstantFP, GlobalAddress, FrameIndex, ConstantPool, + // EntryToken - This is the marker used to indicate the start of the region. + EntryToken, + + // Token factor - This node is takes multiple tokens as input and produces a + // single token result. This is used to represent the fact that the operand + // operators are independent of each other. + TokenFactor, + + // Various leaf nodes. + Constant, ConstantFP, GlobalAddress, FrameIndex, ConstantPool, BasicBlock, ExternalSymbol, // CopyToReg - This node has chain and child nodes, and an associated // register number. The instruction selector must guarantee that the value - // of the value node is available in the virtual register stored in the - // CopyRegSDNode object. + // of the value node is available in the register stored in the RegSDNode + // object. 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 virtual register is available from the - // CopyRegSDNode object. + // SelectionDAG. The register is available from the RegSDNode object. CopyFromReg, + // ImplicitDef - This node indicates that the specified register is + // implicitly defined by some operation (e.g. its a live-in argument). This + // register is indicated in the RegSDNode object. The only operand to this + // is the token chain coming in, the only result is the token chain going + // out. + ImplicitDef, + + // 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, @@ -72,6 +92,10 @@ namespace ISD { // Simple binary arithmetic operators. ADD, SUB, MUL, SDIV, UDIV, SREM, UREM, + // 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. + MULHU, MULHS, + // Bitwise operators. AND, OR, XOR, SHL, SRA, SRL, @@ -84,10 +108,18 @@ namespace ISD { // state. SETCC, - // addc - Three input, two output operator: (X, Y, C) -> (X+Y+C, - // Cout). X,Y are integer inputs of agreeing size, C is a one bit - // value, and two values are produced: the sum and a carry out. - ADDC, SUBB, + // ADD_PARTS/SUB_PARTS - These operators take two logical operands which are + // broken into a multiple pieces each, and return the resulting pieces of + // doing an atomic add/sub operation. This is used to handle add/sub of + // expanded types. The operation ordering is: + // [Lo,Hi] = op [LoLHS,HiLHS], [LoRHS,HiRHS] + ADD_PARTS, SUB_PARTS, + + // SHL_PARTS/SRA_PARTS/SRL_PARTS - These operators are used for expanded + // integer shift operations, just like ADD/SUB_PARTS. The operation + // ordering is: + // [Lo,Hi] = op [LoLHS,HiLHS], Amt + SHL_PARTS, SRA_PARTS, SRL_PARTS, // Conversion operators. These are all single input single output // operations. For all of these, the result type must be strictly @@ -104,16 +136,68 @@ namespace ISD { // TRUNCATE - Completely drop the high bits. TRUNCATE, + // [SU]INT_TO_FP - These operators convert integers (whose interpreted sign + // depends on the first letter) to floating point. + SINT_TO_FP, + UINT_TO_FP, + + // SIGN_EXTEND_INREG - This operator atomically performs a SHL/SRA pair to + // sign extend a small value in a large integer register (e.g. sign + // extending the low 8 bits of a 32-bit register to fill the top 24 bits + // with the 7th bit). The size of the smaller type is indicated by the + // ExtraValueType in the MVTSDNode for the operator. + SIGN_EXTEND_INREG, + + // 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. + // precision down to the specified precision (currently always 64->32). 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 + // ExtraValueType in the MVTSDNode (currently always 64->32->64). + FP_ROUND_INREG, + // FP_EXTEND - Extend a smaller FP type into a larger FP type. FP_EXTEND, - // Other operators. LOAD and STORE have token chains. + // FNEG, FABS - Perform unary floating point negation and absolute value + // operations. + FNEG, FABS, + + // Other operators. LOAD and STORE have token chains as their first + // operand, then the same operands as an LLVM load/store instruction. LOAD, STORE, + // EXTLOAD, SEXTLOAD, ZEXTLOAD - These three operators are instances of the + // MVTSDNode. All of these 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 two operands, a chain and a pointer to load from. The extra value + // type is the source type being loaded. + // + // 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, and the stored type + // represented as the 'extra' value type in the MVTSDNode representing the + // operator. This node has the same three operands as a standard store. + TRUNCSTORE, + // 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 @@ -121,7 +205,7 @@ namespace ISD { DYNAMIC_STACKALLOC, // Control flow instructions. These all have token chains. - + // BR - Unconditional branch. The first operand is the chain // operand, the second is the MBB to branch to. BR, @@ -131,6 +215,13 @@ namespace ISD { // 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, + // 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. @@ -141,7 +232,15 @@ namespace ISD { // call). Arguments have already been lowered to explicit DAGs according to // the calling convention in effect here. CALL, - + + // 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, + // ADJCALLSTACKDOWN/ADJCALLSTACKUP - These operators mark the beginning and // end of a call sequence and indicate how much the stack pointer needs to // be adjusted for that particular call. The first operand is a chain, the @@ -149,6 +248,8 @@ namespace ISD { ADJCALLSTACKDOWN, // Beginning of a call sequence ADJCALLSTACKUP, // End of a call sequence + // PCMARKER - This corresponds to the pcmarker intrinsic. + PCMARKER, // BUILTIN_OP_END - This must be the last enum value in this list. BUILTIN_OP_END, @@ -183,7 +284,7 @@ namespace ISD { SETUGT, // 1 0 1 0 True if unordered or greater than SETUGE, // 1 0 1 1 True if unordered, greater than, or equal SETULT, // 1 1 0 0 True if unordered or less than - SETULE, // 1 1 0 1 True if unordered, less than, or equal + SETULE, // 1 1 0 1 True if unordered, less than, or equal SETUNE, // 1 1 1 0 True if unordered or not equal SETTRUE, // 1 1 1 1 Always true (always folded) // Don't care operations: undefined if the input is a nan. @@ -192,7 +293,7 @@ namespace ISD { SETGT, // 1 X 0 1 0 True if greater than SETGE, // 1 X 0 1 1 True if greater than or equal SETLT, // 1 X 1 0 0 True if less than - SETLE, // 1 X 1 0 1 True if less than or equal + SETLE, // 1 X 1 0 1 True if less than or equal SETNE, // 1 X 1 1 0 True if not equal SETTRUE2, // 1 X 1 1 1 Always true (always folded) @@ -259,7 +360,8 @@ namespace ISD { /// computes it as well as which return value to use from that node. This pair /// of information is represented with the SDOperand value type. /// -struct SDOperand { +class SDOperand { +public: SDNode *Val; // The node defining the value we are using. unsigned ResNo; // Which return value of the node we are using. @@ -286,8 +388,13 @@ struct SDOperand { // 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; + + /// hasOneUse - Return true if there is exactly one operation using this + /// result value of the defining operator. + inline bool hasOneUse() const; }; @@ -310,7 +417,17 @@ template<> struct simplify_type { /// SDNode - Represents one node in the SelectionDAG. /// class SDNode { - unsigned NodeType; + /// NodeType - The operation that this node performs. + /// + unsigned short NodeType; + + /// 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; + + /// Operands - The values that are used by this operation. + /// std::vector Operands; /// Values - The types of the values this node defines. SDNode's may define @@ -331,6 +448,19 @@ public: bool use_empty() const { return Uses.empty(); } bool hasOneUse() const { return Uses.size() == 1; } + /// 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; } + + 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); + /// getNumOperands - Return the number of values used by this operation. /// unsigned getNumOperands() const { return Operands.size(); } @@ -357,6 +487,9 @@ public: return Values[ResNo]; } + /// getOperationName - Return the opcode of this operation for printing. + /// + const char* getOperationName() const; void dump() const; static bool classof(const SDNode *) { return true; } @@ -364,23 +497,33 @@ public: protected: friend class SelectionDAG; - SDNode(unsigned NT, MVT::ValueType VT) : NodeType(NT) { + SDNode(unsigned NT, MVT::ValueType VT) : NodeType(NT), NodeDepth(1) { Values.reserve(1); Values.push_back(VT); } - SDNode(unsigned NT, SDOperand Op) - : NodeType(NT) { + : NodeType(NT), NodeDepth(Op.Val->getNodeDepth()+1) { Operands.reserve(1); Operands.push_back(Op); Op.Val->Uses.push_back(this); } 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; Operands.reserve(2); Operands.push_back(N1); Operands.push_back(N2); N1.Val->Uses.push_back(this); N2.Val->Uses.push_back(this); } 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; + Operands.reserve(3); Operands.push_back(N1); Operands.push_back(N2); Operands.push_back(N3); N1.Val->Uses.push_back(this); N2.Val->Uses.push_back(this); @@ -388,8 +531,13 @@ protected: } SDNode(unsigned NT, std::vector &Nodes) : NodeType(NT) { Operands.swap(Nodes); - for (unsigned i = 0, e = Nodes.size(); i != e; ++i) - Nodes[i].Val->Uses.push_back(this); + unsigned ND = 0; + for (unsigned i = 0, e = Operands.size(); i != e; ++i) { + Operands[i].Val->Uses.push_back(this); + if (ND < Operands[i].Val->getNodeDepth()) + ND = Operands[i].Val->getNodeDepth(); + } + NodeDepth = ND+1; } virtual ~SDNode() { @@ -409,6 +557,17 @@ protected: void setValueTypes(std::vector &VTs) { std::swap(Values, VTs); } + + 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.erase(Uses.begin()+i-1); + break; + } + } + } }; @@ -417,6 +576,9 @@ protected: inline unsigned SDOperand::getOpcode() const { return Val->getOpcode(); } +inline unsigned SDOperand::getNodeDepth() const { + return Val->getNodeDepth(); +} inline MVT::ValueType SDOperand::getValueType() const { return Val->getValueType(ResNo); } @@ -426,7 +588,9 @@ inline unsigned SDOperand::getNumOperands() const { inline const SDOperand &SDOperand::getOperand(unsigned i) const { return Val->getOperand(i); } - +inline bool SDOperand::hasOneUse() const { + return Val->hasNUsesOfValue(1, ResNo); +} class ConstantSDNode : public SDNode { @@ -442,12 +606,14 @@ public: int64_t getSignExtended() const { unsigned Bits = MVT::getSizeInBits(getValueType(0)); - return ((int64_t)Value << 64-Bits) >> 64-Bits; + return ((int64_t)Value << (64-Bits)) >> (64-Bits); } bool isNullValue() const { return Value == 0; } bool isAllOnesValue() const { - return Value == (1ULL << MVT::getSizeInBits(getValueType(0)))-1; + int NumBits = MVT::getSizeInBits(getValueType(0)); + if (NumBits == 64) return Value+1 == 0; + return Value == (1ULL << NumBits)-1; } static bool classof(const ConstantSDNode *) { return true; } @@ -498,7 +664,6 @@ protected: GlobalAddressSDNode(const GlobalValue *GA, MVT::ValueType VT) : SDNode(ISD::GlobalAddress, VT) { TheGlobal = const_cast(GA); - } public: @@ -560,25 +725,24 @@ public: }; -class CopyRegSDNode : public SDNode { +class RegSDNode : public SDNode { unsigned Reg; protected: friend class SelectionDAG; - CopyRegSDNode(SDOperand Chain, SDOperand Src, unsigned reg) - : SDNode(ISD::CopyToReg, Chain, Src), Reg(reg) { - setValueTypes(MVT::Other); // Just a token chain. - } - CopyRegSDNode(unsigned reg, MVT::ValueType VT) - : SDNode(ISD::CopyFromReg, VT), Reg(reg) { + RegSDNode(unsigned Opc, SDOperand Chain, SDOperand Src, unsigned reg) + : SDNode(Opc, Chain, Src), Reg(reg) { } + RegSDNode(unsigned Opc, SDOperand Chain, unsigned reg) + : SDNode(Opc, Chain), Reg(reg) {} public: unsigned getReg() const { return Reg; } - static bool classof(const CopyRegSDNode *) { return true; } + static bool classof(const RegSDNode *) { return true; } static bool classof(const SDNode *N) { return N->getOpcode() == ISD::CopyToReg || - N->getOpcode() == ISD::CopyFromReg; + N->getOpcode() == ISD::CopyFromReg || + N->getOpcode() == ISD::ImplicitDef; } }; @@ -605,7 +769,6 @@ protected: friend class SelectionDAG; SetCCSDNode(ISD::CondCode Cond, SDOperand LHS, SDOperand RHS) : SDNode(ISD::SETCC, LHS, RHS), Condition(Cond) { - setValueTypes(MVT::i1); } public: @@ -617,6 +780,96 @@ public: } }; +/// MVTSDNode - This class is used for operators that require an extra +/// value-type to be kept with the node. +class MVTSDNode : public SDNode { + MVT::ValueType ExtraValueType; +protected: + friend class SelectionDAG; + MVTSDNode(unsigned Opc, MVT::ValueType VT1, SDOperand Op0, MVT::ValueType EVT) + : SDNode(Opc, Op0), ExtraValueType(EVT) { + setValueTypes(VT1); + } + MVTSDNode(unsigned Opc, MVT::ValueType VT1, MVT::ValueType VT2, + SDOperand Op0, SDOperand Op1, MVT::ValueType EVT) + : SDNode(Opc, Op0, Op1), ExtraValueType(EVT) { + setValueTypes(VT1, VT2); + } + MVTSDNode(unsigned Opc, MVT::ValueType VT, + SDOperand Op0, SDOperand Op1, SDOperand Op2, MVT::ValueType EVT) + : SDNode(Opc, Op0, Op1, Op2), ExtraValueType(EVT) { + setValueTypes(VT); + } +public: + + MVT::ValueType getExtraValueType() const { return ExtraValueType; } + + static bool classof(const MVTSDNode *) { return true; } + static bool classof(const SDNode *N) { + return + N->getOpcode() == ISD::SIGN_EXTEND_INREG || + N->getOpcode() == ISD::FP_ROUND_INREG || + N->getOpcode() == ISD::EXTLOAD || + N->getOpcode() == ISD::SEXTLOAD || + N->getOpcode() == ISD::ZEXTLOAD || + N->getOpcode() == ISD::TRUNCSTORE; + } +}; + +class SDNodeIterator : public forward_iterator { + SDNode *Node; + unsigned Operand; + + SDNodeIterator(SDNode *N, unsigned Op) : Node(N), Operand(Op) {} +public: + bool operator==(const SDNodeIterator& x) const { + return Operand == x.Operand; + } + bool operator!=(const SDNodeIterator& x) const { return !operator==(x); } + + const SDNodeIterator &operator=(const SDNodeIterator &I) { + assert(I.Node == Node && "Cannot assign iterators to two different nodes!"); + Operand = I.Operand; + return *this; + } + + pointer operator*() const { + return Node->getOperand(Operand).Val; + } + pointer operator->() const { return operator*(); } + + SDNodeIterator& operator++() { // Preincrement + ++Operand; + return *this; + } + SDNodeIterator operator++(int) { // Postincrement + SDNodeIterator tmp = *this; ++*this; return tmp; + } + + static SDNodeIterator begin(SDNode *N) { return SDNodeIterator(N, 0); } + static SDNodeIterator end (SDNode *N) { + return SDNodeIterator(N, N->getNumOperands()); + } + + unsigned getOperand() const { return Operand; } + const SDNode *getNode() const { return Node; } +}; + +template <> struct GraphTraits { + typedef SDNode NodeType; + typedef SDNodeIterator ChildIteratorType; + static inline NodeType *getEntryNode(SDNode *N) { return N; } + static inline ChildIteratorType child_begin(NodeType *N) { + return SDNodeIterator::begin(N); + } + static inline ChildIteratorType child_end(NodeType *N) { + return SDNodeIterator::end(N); + } +}; + + + + } // end llvm namespace #endif