X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FSelectionDAGNodes.h;h=35993d986aa6711cd7cd12beab2fd91847bec634;hb=ea61c358720aa6c7a159d51658b34276316aa841;hp=b721adac1574fc76477d72c1728a2c8a12a88ae7;hpb=7ece380440238ad0630a225b85a09a2dbed1165a;p=oota-llvm.git diff --git a/include/llvm/CodeGen/SelectionDAGNodes.h b/include/llvm/CodeGen/SelectionDAGNodes.h index b721adac157..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,7 +51,7 @@ 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, @@ -74,6 +74,9 @@ namespace ISD { // 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, @@ -89,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, @@ -101,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 @@ -126,13 +141,12 @@ namespace ISD { SINT_TO_FP, UINT_TO_FP, - // SIGN_EXTEND_INREG/ZERO_EXTEND_INREG - These operators atomically performs - // a SHL/(SRA|SHL) pair to (sign|zero) 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 - 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, - ZERO_EXTEND_INREG, // FP_TO_[US]INT - Convert a floating point value to a signed or unsigned // integer. @@ -153,6 +167,10 @@ namespace ISD { // FP_EXTEND - Extend a smaller FP type into a larger FP type. FP_EXTEND, + // 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, @@ -167,7 +185,7 @@ namespace ISD { // 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 + // 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. @@ -187,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, @@ -197,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. @@ -215,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 @@ -223,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, @@ -257,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. @@ -266,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) @@ -361,6 +388,7 @@ 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; @@ -389,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 @@ -410,6 +448,10 @@ 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(); } @@ -455,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); @@ -479,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() { @@ -519,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); } @@ -551,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; } @@ -707,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: @@ -745,12 +806,11 @@ public: static bool classof(const MVTSDNode *) { return true; } static bool classof(const SDNode *N) { - return + return N->getOpcode() == ISD::SIGN_EXTEND_INREG || - N->getOpcode() == ISD::ZERO_EXTEND_INREG || N->getOpcode() == ISD::FP_ROUND_INREG || N->getOpcode() == ISD::EXTLOAD || - N->getOpcode() == ISD::SEXTLOAD || + N->getOpcode() == ISD::SEXTLOAD || N->getOpcode() == ISD::ZEXTLOAD || N->getOpcode() == ISD::TRUNCSTORE; } @@ -759,7 +819,7 @@ public: 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 { @@ -772,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); } @@ -799,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); } };