X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FSelectionDAGNodes.h;h=35993d986aa6711cd7cd12beab2fd91847bec634;hb=ea61c358720aa6c7a159d51658b34276316aa841;hp=2957a51401c45483e29d42f19d1703e01bdf5b59;hpb=8a496fcffdcba757412fc5cc6c772260ccfde000;p=oota-llvm.git diff --git a/include/llvm/CodeGen/SelectionDAGNodes.h b/include/llvm/CodeGen/SelectionDAGNodes.h index 2957a51401c..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 @@ -51,23 +51,32 @@ namespace ISD { // 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 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 register number 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, @@ -83,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, @@ -95,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 @@ -120,21 +141,63 @@ namespace ISD { 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 @@ -142,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, @@ -152,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. @@ -170,7 +240,7 @@ namespace ISD { 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 @@ -178,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, @@ -212,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. @@ -221,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) @@ -316,8 +388,13 @@ public: // 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; }; @@ -340,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 @@ -361,6 +448,14 @@ 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. @@ -402,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); @@ -426,8 +531,13 @@ protected: } SDNode(unsigned NT, std::vector &Nodes) : NodeType(NT) { Operands.swap(Nodes); - for (unsigned i = 0, e = Operands.size(); i != e; ++i) + 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() { @@ -466,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); } @@ -475,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 { @@ -496,7 +611,9 @@ public: 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; } @@ -608,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; } }; @@ -653,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: @@ -665,11 +780,46 @@ 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 { @@ -682,18 +832,18 @@ public: 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; + SDNodeIterator tmp = *this; ++*this; return tmp; } static SDNodeIterator begin(SDNode *N) { return SDNodeIterator(N, 0); } @@ -709,10 +859,10 @@ template <> struct GraphTraits { typedef SDNode NodeType; typedef SDNodeIterator ChildIteratorType; static inline NodeType *getEntryNode(SDNode *N) { return N; } - static inline ChildIteratorType child_begin(NodeType *N) { + static inline ChildIteratorType child_begin(NodeType *N) { return SDNodeIterator::begin(N); } - static inline ChildIteratorType child_end(NodeType *N) { + static inline ChildIteratorType child_end(NodeType *N) { return SDNodeIterator::end(N); } };