LLVM API Documentation

SelectionDAGNodes.h
Go to the documentation of this file.
00001 //===-- llvm/CodeGen/SelectionDAGNodes.h - SelectionDAG Nodes ---*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file declares the SDNode class and derived classes, which are used to
00011 // represent the nodes and operations present in a SelectionDAG.  These nodes
00012 // and operations are machine code level operations, with some similarities to
00013 // the GCC RTL representation.
00014 //
00015 // Clients should include the SelectionDAG.h file instead of this file directly.
00016 //
00017 //===----------------------------------------------------------------------===//
00018 
00019 #ifndef LLVM_CODEGEN_SELECTIONDAGNODES_H
00020 #define LLVM_CODEGEN_SELECTIONDAGNODES_H
00021 
00022 #include "llvm/ADT/iterator_range.h"
00023 #include "llvm/ADT/BitVector.h"
00024 #include "llvm/ADT/FoldingSet.h"
00025 #include "llvm/ADT/GraphTraits.h"
00026 #include "llvm/ADT/STLExtras.h"
00027 #include "llvm/ADT/SmallPtrSet.h"
00028 #include "llvm/ADT/SmallVector.h"
00029 #include "llvm/ADT/ilist_node.h"
00030 #include "llvm/CodeGen/ISDOpcodes.h"
00031 #include "llvm/CodeGen/MachineMemOperand.h"
00032 #include "llvm/CodeGen/ValueTypes.h"
00033 #include "llvm/IR/Constants.h"
00034 #include "llvm/IR/DebugLoc.h"
00035 #include "llvm/IR/Instructions.h"
00036 #include "llvm/Support/DataTypes.h"
00037 #include "llvm/Support/MathExtras.h"
00038 #include <cassert>
00039 
00040 namespace llvm {
00041 
00042 class SelectionDAG;
00043 class GlobalValue;
00044 class MachineBasicBlock;
00045 class MachineConstantPoolValue;
00046 class SDNode;
00047 class Value;
00048 class MCSymbol;
00049 template <typename T> struct DenseMapInfo;
00050 template <typename T> struct simplify_type;
00051 template <typename T> struct ilist_traits;
00052 
00053 /// isBinOpWithFlags - Returns true if the opcode is a binary operation
00054 /// with flags.
00055 static bool isBinOpWithFlags(unsigned Opcode) {
00056   switch (Opcode) {
00057   case ISD::SDIV:
00058   case ISD::UDIV:
00059   case ISD::SRA:
00060   case ISD::SRL:
00061   case ISD::MUL:
00062   case ISD::ADD:
00063   case ISD::SUB:
00064   case ISD::SHL:
00065     return true;
00066   default:
00067     return false;
00068   }
00069 }
00070 
00071 void checkForCycles(const SDNode *N, const SelectionDAG *DAG = nullptr,
00072                     bool force = false);
00073 
00074 /// SDVTList - This represents a list of ValueType's that has been intern'd by
00075 /// a SelectionDAG.  Instances of this simple value class are returned by
00076 /// SelectionDAG::getVTList(...).
00077 ///
00078 struct SDVTList {
00079   const EVT *VTs;
00080   unsigned int NumVTs;
00081 };
00082 
00083 namespace ISD {
00084   /// Node predicates
00085 
00086   /// isBuildVectorAllOnes - Return true if the specified node is a
00087   /// BUILD_VECTOR where all of the elements are ~0 or undef.
00088   bool isBuildVectorAllOnes(const SDNode *N);
00089 
00090   /// isBuildVectorAllZeros - Return true if the specified node is a
00091   /// BUILD_VECTOR where all of the elements are 0 or undef.
00092   bool isBuildVectorAllZeros(const SDNode *N);
00093 
00094   /// \brief Return true if the specified node is a BUILD_VECTOR node of
00095   /// all ConstantSDNode or undef.
00096   bool isBuildVectorOfConstantSDNodes(const SDNode *N);
00097 
00098   /// isScalarToVector - Return true if the specified node is a
00099   /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
00100   /// element is not an undef.
00101   bool isScalarToVector(const SDNode *N);
00102 
00103   /// allOperandsUndef - Return true if the node has at least one operand
00104   /// and all operands of the specified node are ISD::UNDEF.
00105   bool allOperandsUndef(const SDNode *N);
00106 }  // end llvm:ISD namespace
00107 
00108 //===----------------------------------------------------------------------===//
00109 /// SDValue - Unlike LLVM values, Selection DAG nodes may return multiple
00110 /// values as the result of a computation.  Many nodes return multiple values,
00111 /// from loads (which define a token and a return value) to ADDC (which returns
00112 /// a result and a carry value), to calls (which may return an arbitrary number
00113 /// of values).
00114 ///
00115 /// As such, each use of a SelectionDAG computation must indicate the node that
00116 /// computes it as well as which return value to use from that node.  This pair
00117 /// of information is represented with the SDValue value type.
00118 ///
00119 class SDValue {
00120   friend struct DenseMapInfo<SDValue>;
00121 
00122   SDNode *Node;       // The node defining the value we are using.
00123   unsigned ResNo;     // Which return value of the node we are using.
00124 public:
00125   SDValue() : Node(nullptr), ResNo(0) {}
00126   SDValue(SDNode *node, unsigned resno);
00127 
00128   /// get the index which selects a specific result in the SDNode
00129   unsigned getResNo() const { return ResNo; }
00130 
00131   /// get the SDNode which holds the desired result
00132   SDNode *getNode() const { return Node; }
00133 
00134   /// set the SDNode
00135   void setNode(SDNode *N) { Node = N; }
00136 
00137   inline SDNode *operator->() const { return Node; }
00138 
00139   bool operator==(const SDValue &O) const {
00140     return Node == O.Node && ResNo == O.ResNo;
00141   }
00142   bool operator!=(const SDValue &O) const {
00143     return !operator==(O);
00144   }
00145   bool operator<(const SDValue &O) const {
00146     return std::tie(Node, ResNo) < std::tie(O.Node, O.ResNo);
00147   }
00148   LLVM_EXPLICIT operator bool() const {
00149     return Node != nullptr;
00150   }
00151 
00152   SDValue getValue(unsigned R) const {
00153     return SDValue(Node, R);
00154   }
00155 
00156   // isOperandOf - Return true if this node is an operand of N.
00157   bool isOperandOf(SDNode *N) const;
00158 
00159   /// getValueType - Return the ValueType of the referenced return value.
00160   ///
00161   inline EVT getValueType() const;
00162 
00163   /// Return the simple ValueType of the referenced return value.
00164   MVT getSimpleValueType() const {
00165     return getValueType().getSimpleVT();
00166   }
00167 
00168   /// getValueSizeInBits - Returns the size of the value in bits.
00169   ///
00170   unsigned getValueSizeInBits() const {
00171     return getValueType().getSizeInBits();
00172   }
00173 
00174   unsigned getScalarValueSizeInBits() const {
00175     return getValueType().getScalarType().getSizeInBits();
00176   }
00177 
00178   // Forwarding methods - These forward to the corresponding methods in SDNode.
00179   inline unsigned getOpcode() const;
00180   inline unsigned getNumOperands() const;
00181   inline const SDValue &getOperand(unsigned i) const;
00182   inline uint64_t getConstantOperandVal(unsigned i) const;
00183   inline bool isTargetMemoryOpcode() const;
00184   inline bool isTargetOpcode() const;
00185   inline bool isMachineOpcode() const;
00186   inline unsigned getMachineOpcode() const;
00187   inline const DebugLoc getDebugLoc() const;
00188   inline void dump() const;
00189   inline void dumpr() const;
00190 
00191   /// reachesChainWithoutSideEffects - Return true if this operand (which must
00192   /// be a chain) reaches the specified operand without crossing any
00193   /// side-effecting instructions.  In practice, this looks through token
00194   /// factors and non-volatile loads.  In order to remain efficient, this only
00195   /// looks a couple of nodes in, it does not do an exhaustive search.
00196   bool reachesChainWithoutSideEffects(SDValue Dest,
00197                                       unsigned Depth = 2) const;
00198 
00199   /// use_empty - Return true if there are no nodes using value ResNo
00200   /// of Node.
00201   ///
00202   inline bool use_empty() const;
00203 
00204   /// hasOneUse - Return true if there is exactly one node using value
00205   /// ResNo of Node.
00206   ///
00207   inline bool hasOneUse() const;
00208 };
00209 
00210 
00211 template<> struct DenseMapInfo<SDValue> {
00212   static inline SDValue getEmptyKey() {
00213     SDValue V;
00214     V.ResNo = -1U;
00215     return V;
00216   }
00217   static inline SDValue getTombstoneKey() {
00218     SDValue V;
00219     V.ResNo = -2U;
00220     return V;
00221   }
00222   static unsigned getHashValue(const SDValue &Val) {
00223     return ((unsigned)((uintptr_t)Val.getNode() >> 4) ^
00224             (unsigned)((uintptr_t)Val.getNode() >> 9)) + Val.getResNo();
00225   }
00226   static bool isEqual(const SDValue &LHS, const SDValue &RHS) {
00227     return LHS == RHS;
00228   }
00229 };
00230 template <> struct isPodLike<SDValue> { static const bool value = true; };
00231 
00232 
00233 /// simplify_type specializations - Allow casting operators to work directly on
00234 /// SDValues as if they were SDNode*'s.
00235 template<> struct simplify_type<SDValue> {
00236   typedef SDNode* SimpleType;
00237   static SimpleType getSimplifiedValue(SDValue &Val) {
00238     return Val.getNode();
00239   }
00240 };
00241 template<> struct simplify_type<const SDValue> {
00242   typedef /*const*/ SDNode* SimpleType;
00243   static SimpleType getSimplifiedValue(const SDValue &Val) {
00244     return Val.getNode();
00245   }
00246 };
00247 
00248 /// SDUse - Represents a use of a SDNode. This class holds an SDValue,
00249 /// which records the SDNode being used and the result number, a
00250 /// pointer to the SDNode using the value, and Next and Prev pointers,
00251 /// which link together all the uses of an SDNode.
00252 ///
00253 class SDUse {
00254   /// Val - The value being used.
00255   SDValue Val;
00256   /// User - The user of this value.
00257   SDNode *User;
00258   /// Prev, Next - Pointers to the uses list of the SDNode referred by
00259   /// this operand.
00260   SDUse **Prev, *Next;
00261 
00262   SDUse(const SDUse &U) LLVM_DELETED_FUNCTION;
00263   void operator=(const SDUse &U) LLVM_DELETED_FUNCTION;
00264 
00265 public:
00266   SDUse() : Val(), User(nullptr), Prev(nullptr), Next(nullptr) {}
00267 
00268   /// Normally SDUse will just implicitly convert to an SDValue that it holds.
00269   operator const SDValue&() const { return Val; }
00270 
00271   /// If implicit conversion to SDValue doesn't work, the get() method returns
00272   /// the SDValue.
00273   const SDValue &get() const { return Val; }
00274 
00275   /// getUser - This returns the SDNode that contains this Use.
00276   SDNode *getUser() { return User; }
00277 
00278   /// getNext - Get the next SDUse in the use list.
00279   SDUse *getNext() const { return Next; }
00280 
00281   /// getNode - Convenience function for get().getNode().
00282   SDNode *getNode() const { return Val.getNode(); }
00283   /// getResNo - Convenience function for get().getResNo().
00284   unsigned getResNo() const { return Val.getResNo(); }
00285   /// getValueType - Convenience function for get().getValueType().
00286   EVT getValueType() const { return Val.getValueType(); }
00287 
00288   /// operator== - Convenience function for get().operator==
00289   bool operator==(const SDValue &V) const {
00290     return Val == V;
00291   }
00292 
00293   /// operator!= - Convenience function for get().operator!=
00294   bool operator!=(const SDValue &V) const {
00295     return Val != V;
00296   }
00297 
00298   /// operator< - Convenience function for get().operator<
00299   bool operator<(const SDValue &V) const {
00300     return Val < V;
00301   }
00302 
00303 private:
00304   friend class SelectionDAG;
00305   friend class SDNode;
00306 
00307   void setUser(SDNode *p) { User = p; }
00308 
00309   /// set - Remove this use from its existing use list, assign it the
00310   /// given value, and add it to the new value's node's use list.
00311   inline void set(const SDValue &V);
00312   /// setInitial - like set, but only supports initializing a newly-allocated
00313   /// SDUse with a non-null value.
00314   inline void setInitial(const SDValue &V);
00315   /// setNode - like set, but only sets the Node portion of the value,
00316   /// leaving the ResNo portion unmodified.
00317   inline void setNode(SDNode *N);
00318 
00319   void addToList(SDUse **List) {
00320     Next = *List;
00321     if (Next) Next->Prev = &Next;
00322     Prev = List;
00323     *List = this;
00324   }
00325 
00326   void removeFromList() {
00327     *Prev = Next;
00328     if (Next) Next->Prev = Prev;
00329   }
00330 };
00331 
00332 /// simplify_type specializations - Allow casting operators to work directly on
00333 /// SDValues as if they were SDNode*'s.
00334 template<> struct simplify_type<SDUse> {
00335   typedef SDNode* SimpleType;
00336   static SimpleType getSimplifiedValue(SDUse &Val) {
00337     return Val.getNode();
00338   }
00339 };
00340 
00341 
00342 /// SDNode - Represents one node in the SelectionDAG.
00343 ///
00344 class SDNode : public FoldingSetNode, public ilist_node<SDNode> {
00345 private:
00346   /// NodeType - The operation that this node performs.
00347   ///
00348   int16_t NodeType;
00349 
00350   /// OperandsNeedDelete - This is true if OperandList was new[]'d.  If true,
00351   /// then they will be delete[]'d when the node is destroyed.
00352   uint16_t OperandsNeedDelete : 1;
00353 
00354   /// HasDebugValue - This tracks whether this node has one or more dbg_value
00355   /// nodes corresponding to it.
00356   uint16_t HasDebugValue : 1;
00357 
00358 protected:
00359   /// SubclassData - This member is defined by this class, but is not used for
00360   /// anything.  Subclasses can use it to hold whatever state they find useful.
00361   /// This field is initialized to zero by the ctor.
00362   uint16_t SubclassData : 14;
00363 
00364 private:
00365   /// NodeId - Unique id per SDNode in the DAG.
00366   int NodeId;
00367 
00368   /// OperandList - The values that are used by this operation.
00369   ///
00370   SDUse *OperandList;
00371 
00372   /// ValueList - The types of the values this node defines.  SDNode's may
00373   /// define multiple values simultaneously.
00374   const EVT *ValueList;
00375 
00376   /// UseList - List of uses for this SDNode.
00377   SDUse *UseList;
00378 
00379   /// NumOperands/NumValues - The number of entries in the Operand/Value list.
00380   unsigned short NumOperands, NumValues;
00381 
00382   /// debugLoc - source line information.
00383   DebugLoc debugLoc;
00384 
00385   // The ordering of the SDNodes. It roughly corresponds to the ordering of the
00386   // original LLVM instructions.
00387   // This is used for turning off scheduling, because we'll forgo
00388   // the normal scheduling algorithms and output the instructions according to
00389   // this ordering.
00390   unsigned IROrder;
00391 
00392   /// getValueTypeList - Return a pointer to the specified value type.
00393   static const EVT *getValueTypeList(EVT VT);
00394 
00395   friend class SelectionDAG;
00396   friend struct ilist_traits<SDNode>;
00397 
00398 public:
00399   //===--------------------------------------------------------------------===//
00400   //  Accessors
00401   //
00402 
00403   /// getOpcode - Return the SelectionDAG opcode value for this node. For
00404   /// pre-isel nodes (those for which isMachineOpcode returns false), these
00405   /// are the opcode values in the ISD and <target>ISD namespaces. For
00406   /// post-isel opcodes, see getMachineOpcode.
00407   unsigned getOpcode()  const { return (unsigned short)NodeType; }
00408 
00409   /// isTargetOpcode - Test if this node has a target-specific opcode (in the
00410   /// <target>ISD namespace).
00411   bool isTargetOpcode() const { return NodeType >= ISD::BUILTIN_OP_END; }
00412 
00413   /// isTargetMemoryOpcode - Test if this node has a target-specific
00414   /// memory-referencing opcode (in the <target>ISD namespace and
00415   /// greater than FIRST_TARGET_MEMORY_OPCODE).
00416   bool isTargetMemoryOpcode() const {
00417     return NodeType >= ISD::FIRST_TARGET_MEMORY_OPCODE;
00418   }
00419 
00420   /// isMachineOpcode - Test if this node has a post-isel opcode, directly
00421   /// corresponding to a MachineInstr opcode.
00422   bool isMachineOpcode() const { return NodeType < 0; }
00423 
00424   /// getMachineOpcode - This may only be called if isMachineOpcode returns
00425   /// true. It returns the MachineInstr opcode value that the node's opcode
00426   /// corresponds to.
00427   unsigned getMachineOpcode() const {
00428     assert(isMachineOpcode() && "Not a MachineInstr opcode!");
00429     return ~NodeType;
00430   }
00431 
00432   /// getHasDebugValue - get this bit.
00433   bool getHasDebugValue() const { return HasDebugValue; }
00434 
00435   /// setHasDebugValue - set this bit.
00436   void setHasDebugValue(bool b) { HasDebugValue = b; }
00437 
00438   /// use_empty - Return true if there are no uses of this node.
00439   ///
00440   bool use_empty() const { return UseList == nullptr; }
00441 
00442   /// hasOneUse - Return true if there is exactly one use of this node.
00443   ///
00444   bool hasOneUse() const {
00445     return !use_empty() && std::next(use_begin()) == use_end();
00446   }
00447 
00448   /// use_size - Return the number of uses of this node. This method takes
00449   /// time proportional to the number of uses.
00450   ///
00451   size_t use_size() const { return std::distance(use_begin(), use_end()); }
00452 
00453   /// getNodeId - Return the unique node id.
00454   ///
00455   int getNodeId() const { return NodeId; }
00456 
00457   /// setNodeId - Set unique node id.
00458   void setNodeId(int Id) { NodeId = Id; }
00459 
00460   /// getIROrder - Return the node ordering.
00461   ///
00462   unsigned getIROrder() const { return IROrder; }
00463 
00464   /// setIROrder - Set the node ordering.
00465   ///
00466   void setIROrder(unsigned Order) { IROrder = Order; }
00467 
00468   /// getDebugLoc - Return the source location info.
00469   const DebugLoc getDebugLoc() const { return debugLoc; }
00470 
00471   /// setDebugLoc - Set source location info.  Try to avoid this, putting
00472   /// it in the constructor is preferable.
00473   void setDebugLoc(const DebugLoc dl) { debugLoc = dl; }
00474 
00475   /// use_iterator - This class provides iterator support for SDUse
00476   /// operands that use a specific SDNode.
00477   class use_iterator
00478     : public std::iterator<std::forward_iterator_tag, SDUse, ptrdiff_t> {
00479     SDUse *Op;
00480     explicit use_iterator(SDUse *op) : Op(op) {
00481     }
00482     friend class SDNode;
00483   public:
00484     typedef std::iterator<std::forward_iterator_tag,
00485                           SDUse, ptrdiff_t>::reference reference;
00486     typedef std::iterator<std::forward_iterator_tag,
00487                           SDUse, ptrdiff_t>::pointer pointer;
00488 
00489     use_iterator(const use_iterator &I) : Op(I.Op) {}
00490     use_iterator() : Op(nullptr) {}
00491 
00492     bool operator==(const use_iterator &x) const {
00493       return Op == x.Op;
00494     }
00495     bool operator!=(const use_iterator &x) const {
00496       return !operator==(x);
00497     }
00498 
00499     /// atEnd - return true if this iterator is at the end of uses list.
00500     bool atEnd() const { return Op == nullptr; }
00501 
00502     // Iterator traversal: forward iteration only.
00503     use_iterator &operator++() {          // Preincrement
00504       assert(Op && "Cannot increment end iterator!");
00505       Op = Op->getNext();
00506       return *this;
00507     }
00508 
00509     use_iterator operator++(int) {        // Postincrement
00510       use_iterator tmp = *this; ++*this; return tmp;
00511     }
00512 
00513     /// Retrieve a pointer to the current user node.
00514     SDNode *operator*() const {
00515       assert(Op && "Cannot dereference end iterator!");
00516       return Op->getUser();
00517     }
00518 
00519     SDNode *operator->() const { return operator*(); }
00520 
00521     SDUse &getUse() const { return *Op; }
00522 
00523     /// getOperandNo - Retrieve the operand # of this use in its user.
00524     ///
00525     unsigned getOperandNo() const {
00526       assert(Op && "Cannot dereference end iterator!");
00527       return (unsigned)(Op - Op->getUser()->OperandList);
00528     }
00529   };
00530 
00531   /// use_begin/use_end - Provide iteration support to walk over all uses
00532   /// of an SDNode.
00533 
00534   use_iterator use_begin() const {
00535     return use_iterator(UseList);
00536   }
00537 
00538   static use_iterator use_end() { return use_iterator(nullptr); }
00539 
00540   inline iterator_range<use_iterator> uses() {
00541     return iterator_range<use_iterator>(use_begin(), use_end());
00542   }
00543   inline iterator_range<use_iterator> uses() const {
00544     return iterator_range<use_iterator>(use_begin(), use_end());
00545   }
00546 
00547   /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
00548   /// indicated value.  This method ignores uses of other values defined by this
00549   /// operation.
00550   bool hasNUsesOfValue(unsigned NUses, unsigned Value) const;
00551 
00552   /// hasAnyUseOfValue - Return true if there are any use of the indicated
00553   /// value. This method ignores uses of other values defined by this operation.
00554   bool hasAnyUseOfValue(unsigned Value) const;
00555 
00556   /// isOnlyUserOf - Return true if this node is the only use of N.
00557   ///
00558   bool isOnlyUserOf(SDNode *N) const;
00559 
00560   /// isOperandOf - Return true if this node is an operand of N.
00561   ///
00562   bool isOperandOf(SDNode *N) const;
00563 
00564   /// isPredecessorOf - Return true if this node is a predecessor of N.
00565   /// NOTE: Implemented on top of hasPredecessor and every bit as
00566   /// expensive. Use carefully.
00567   bool isPredecessorOf(const SDNode *N) const {
00568     return N->hasPredecessor(this);
00569   }
00570 
00571   /// hasPredecessor - Return true if N is a predecessor of this node.
00572   /// N is either an operand of this node, or can be reached by recursively
00573   /// traversing up the operands.
00574   /// NOTE: This is an expensive method. Use it carefully.
00575   bool hasPredecessor(const SDNode *N) const;
00576 
00577   /// hasPredecesorHelper - Return true if N is a predecessor of this node.
00578   /// N is either an operand of this node, or can be reached by recursively
00579   /// traversing up the operands.
00580   /// In this helper the Visited and worklist sets are held externally to
00581   /// cache predecessors over multiple invocations. If you want to test for
00582   /// multiple predecessors this method is preferable to multiple calls to
00583   /// hasPredecessor. Be sure to clear Visited and Worklist if the DAG
00584   /// changes.
00585   /// NOTE: This is still very expensive. Use carefully.
00586   bool hasPredecessorHelper(const SDNode *N,
00587                             SmallPtrSet<const SDNode *, 32> &Visited,
00588                             SmallVectorImpl<const SDNode *> &Worklist) const;
00589 
00590   /// getNumOperands - Return the number of values used by this operation.
00591   ///
00592   unsigned getNumOperands() const { return NumOperands; }
00593 
00594   /// getConstantOperandVal - Helper method returns the integer value of a
00595   /// ConstantSDNode operand.
00596   uint64_t getConstantOperandVal(unsigned Num) const;
00597 
00598   const SDValue &getOperand(unsigned Num) const {
00599     assert(Num < NumOperands && "Invalid child # of SDNode!");
00600     return OperandList[Num];
00601   }
00602 
00603   typedef SDUse* op_iterator;
00604   op_iterator op_begin() const { return OperandList; }
00605   op_iterator op_end() const { return OperandList+NumOperands; }
00606   ArrayRef<SDUse> ops() const { return makeArrayRef(op_begin(), op_end()); }
00607 
00608   SDVTList getVTList() const {
00609     SDVTList X = { ValueList, NumValues };
00610     return X;
00611   }
00612 
00613   /// getGluedNode - If this node has a glue operand, return the node
00614   /// to which the glue operand points. Otherwise return NULL.
00615   SDNode *getGluedNode() const {
00616     if (getNumOperands() != 0 &&
00617       getOperand(getNumOperands()-1).getValueType() == MVT::Glue)
00618       return getOperand(getNumOperands()-1).getNode();
00619     return nullptr;
00620   }
00621 
00622   // If this is a pseudo op, like copyfromreg, look to see if there is a
00623   // real target node glued to it.  If so, return the target node.
00624   const SDNode *getGluedMachineNode() const {
00625     const SDNode *FoundNode = this;
00626 
00627     // Climb up glue edges until a machine-opcode node is found, or the
00628     // end of the chain is reached.
00629     while (!FoundNode->isMachineOpcode()) {
00630       const SDNode *N = FoundNode->getGluedNode();
00631       if (!N) break;
00632       FoundNode = N;
00633     }
00634 
00635     return FoundNode;
00636   }
00637 
00638   /// getGluedUser - If this node has a glue value with a user, return
00639   /// the user (there is at most one). Otherwise return NULL.
00640   SDNode *getGluedUser() const {
00641     for (use_iterator UI = use_begin(), UE = use_end(); UI != UE; ++UI)
00642       if (UI.getUse().get().getValueType() == MVT::Glue)
00643         return *UI;
00644     return nullptr;
00645   }
00646 
00647   /// getNumValues - Return the number of values defined/returned by this
00648   /// operator.
00649   ///
00650   unsigned getNumValues() const { return NumValues; }
00651 
00652   /// getValueType - Return the type of a specified result.
00653   ///
00654   EVT getValueType(unsigned ResNo) const {
00655     assert(ResNo < NumValues && "Illegal result number!");
00656     return ValueList[ResNo];
00657   }
00658 
00659   /// Return the type of a specified result as a simple type.
00660   ///
00661   MVT getSimpleValueType(unsigned ResNo) const {
00662     return getValueType(ResNo).getSimpleVT();
00663   }
00664 
00665   /// getValueSizeInBits - Returns MVT::getSizeInBits(getValueType(ResNo)).
00666   ///
00667   unsigned getValueSizeInBits(unsigned ResNo) const {
00668     return getValueType(ResNo).getSizeInBits();
00669   }
00670 
00671   typedef const EVT* value_iterator;
00672   value_iterator value_begin() const { return ValueList; }
00673   value_iterator value_end() const { return ValueList+NumValues; }
00674 
00675   /// getOperationName - Return the opcode of this operation for printing.
00676   ///
00677   std::string getOperationName(const SelectionDAG *G = nullptr) const;
00678   static const char* getIndexedModeName(ISD::MemIndexedMode AM);
00679   void print_types(raw_ostream &OS, const SelectionDAG *G) const;
00680   void print_details(raw_ostream &OS, const SelectionDAG *G) const;
00681   void print(raw_ostream &OS, const SelectionDAG *G = nullptr) const;
00682   void printr(raw_ostream &OS, const SelectionDAG *G = nullptr) const;
00683 
00684   /// printrFull - Print a SelectionDAG node and all children down to
00685   /// the leaves.  The given SelectionDAG allows target-specific nodes
00686   /// to be printed in human-readable form.  Unlike printr, this will
00687   /// print the whole DAG, including children that appear multiple
00688   /// times.
00689   ///
00690   void printrFull(raw_ostream &O, const SelectionDAG *G = nullptr) const;
00691 
00692   /// printrWithDepth - Print a SelectionDAG node and children up to
00693   /// depth "depth."  The given SelectionDAG allows target-specific
00694   /// nodes to be printed in human-readable form.  Unlike printr, this
00695   /// will print children that appear multiple times wherever they are
00696   /// used.
00697   ///
00698   void printrWithDepth(raw_ostream &O, const SelectionDAG *G = nullptr,
00699                        unsigned depth = 100) const;
00700 
00701 
00702   /// dump - Dump this node, for debugging.
00703   void dump() const;
00704 
00705   /// dumpr - Dump (recursively) this node and its use-def subgraph.
00706   void dumpr() const;
00707 
00708   /// dump - Dump this node, for debugging.
00709   /// The given SelectionDAG allows target-specific nodes to be printed
00710   /// in human-readable form.
00711   void dump(const SelectionDAG *G) const;
00712 
00713   /// dumpr - Dump (recursively) this node and its use-def subgraph.
00714   /// The given SelectionDAG allows target-specific nodes to be printed
00715   /// in human-readable form.
00716   void dumpr(const SelectionDAG *G) const;
00717 
00718   /// dumprFull - printrFull to dbgs().  The given SelectionDAG allows
00719   /// target-specific nodes to be printed in human-readable form.
00720   /// Unlike dumpr, this will print the whole DAG, including children
00721   /// that appear multiple times.
00722   ///
00723   void dumprFull(const SelectionDAG *G = nullptr) const;
00724 
00725   /// dumprWithDepth - printrWithDepth to dbgs().  The given
00726   /// SelectionDAG allows target-specific nodes to be printed in
00727   /// human-readable form.  Unlike dumpr, this will print children
00728   /// that appear multiple times wherever they are used.
00729   ///
00730   void dumprWithDepth(const SelectionDAG *G = nullptr,
00731                       unsigned depth = 100) const;
00732 
00733   /// Profile - Gather unique data for the node.
00734   ///
00735   void Profile(FoldingSetNodeID &ID) const;
00736 
00737   /// addUse - This method should only be used by the SDUse class.
00738   ///
00739   void addUse(SDUse &U) { U.addToList(&UseList); }
00740 
00741 protected:
00742   static SDVTList getSDVTList(EVT VT) {
00743     SDVTList Ret = { getValueTypeList(VT), 1 };
00744     return Ret;
00745   }
00746 
00747   SDNode(unsigned Opc, unsigned Order, const DebugLoc dl, SDVTList VTs,
00748          ArrayRef<SDValue> Ops)
00749     : NodeType(Opc), OperandsNeedDelete(true), HasDebugValue(false),
00750       SubclassData(0), NodeId(-1),
00751       OperandList(Ops.size() ? new SDUse[Ops.size()] : nullptr),
00752       ValueList(VTs.VTs), UseList(nullptr),
00753       NumOperands(Ops.size()), NumValues(VTs.NumVTs),
00754       debugLoc(dl), IROrder(Order) {
00755     for (unsigned i = 0; i != Ops.size(); ++i) {
00756       OperandList[i].setUser(this);
00757       OperandList[i].setInitial(Ops[i]);
00758     }
00759     checkForCycles(this);
00760   }
00761 
00762   /// This constructor adds no operands itself; operands can be
00763   /// set later with InitOperands.
00764   SDNode(unsigned Opc, unsigned Order, const DebugLoc dl, SDVTList VTs)
00765     : NodeType(Opc), OperandsNeedDelete(false), HasDebugValue(false),
00766       SubclassData(0), NodeId(-1), OperandList(nullptr), ValueList(VTs.VTs),
00767       UseList(nullptr), NumOperands(0), NumValues(VTs.NumVTs), debugLoc(dl),
00768       IROrder(Order) {}
00769 
00770   /// InitOperands - Initialize the operands list of this with 1 operand.
00771   void InitOperands(SDUse *Ops, const SDValue &Op0) {
00772     Ops[0].setUser(this);
00773     Ops[0].setInitial(Op0);
00774     NumOperands = 1;
00775     OperandList = Ops;
00776     checkForCycles(this);
00777   }
00778 
00779   /// InitOperands - Initialize the operands list of this with 2 operands.
00780   void InitOperands(SDUse *Ops, const SDValue &Op0, const SDValue &Op1) {
00781     Ops[0].setUser(this);
00782     Ops[0].setInitial(Op0);
00783     Ops[1].setUser(this);
00784     Ops[1].setInitial(Op1);
00785     NumOperands = 2;
00786     OperandList = Ops;
00787     checkForCycles(this);
00788   }
00789 
00790   /// InitOperands - Initialize the operands list of this with 3 operands.
00791   void InitOperands(SDUse *Ops, const SDValue &Op0, const SDValue &Op1,
00792                     const SDValue &Op2) {
00793     Ops[0].setUser(this);
00794     Ops[0].setInitial(Op0);
00795     Ops[1].setUser(this);
00796     Ops[1].setInitial(Op1);
00797     Ops[2].setUser(this);
00798     Ops[2].setInitial(Op2);
00799     NumOperands = 3;
00800     OperandList = Ops;
00801     checkForCycles(this);
00802   }
00803 
00804   /// InitOperands - Initialize the operands list of this with 4 operands.
00805   void InitOperands(SDUse *Ops, const SDValue &Op0, const SDValue &Op1,
00806                     const SDValue &Op2, const SDValue &Op3) {
00807     Ops[0].setUser(this);
00808     Ops[0].setInitial(Op0);
00809     Ops[1].setUser(this);
00810     Ops[1].setInitial(Op1);
00811     Ops[2].setUser(this);
00812     Ops[2].setInitial(Op2);
00813     Ops[3].setUser(this);
00814     Ops[3].setInitial(Op3);
00815     NumOperands = 4;
00816     OperandList = Ops;
00817     checkForCycles(this);
00818   }
00819 
00820   /// InitOperands - Initialize the operands list of this with N operands.
00821   void InitOperands(SDUse *Ops, const SDValue *Vals, unsigned N) {
00822     for (unsigned i = 0; i != N; ++i) {
00823       Ops[i].setUser(this);
00824       Ops[i].setInitial(Vals[i]);
00825     }
00826     NumOperands = N;
00827     OperandList = Ops;
00828     checkForCycles(this);
00829   }
00830 
00831   /// DropOperands - Release the operands and set this node to have
00832   /// zero operands.
00833   void DropOperands();
00834 };
00835 
00836 /// Wrapper class for IR location info (IR ordering and DebugLoc) to be passed
00837 /// into SDNode creation functions.
00838 /// When an SDNode is created from the DAGBuilder, the DebugLoc is extracted
00839 /// from the original Instruction, and IROrder is the ordinal position of
00840 /// the instruction.
00841 /// When an SDNode is created after the DAG is being built, both DebugLoc and
00842 /// the IROrder are propagated from the original SDNode.
00843 /// So SDLoc class provides two constructors besides the default one, one to
00844 /// be used by the DAGBuilder, the other to be used by others.
00845 class SDLoc {
00846 private:
00847   // Ptr could be used for either Instruction* or SDNode*. It is used for
00848   // Instruction* if IROrder is not -1.
00849   const void *Ptr;
00850   int IROrder;
00851 
00852 public:
00853   SDLoc() : Ptr(nullptr), IROrder(0) {}
00854   SDLoc(const SDNode *N) : Ptr(N), IROrder(-1) {
00855     assert(N && "null SDNode");
00856   }
00857   SDLoc(const SDValue V) : Ptr(V.getNode()), IROrder(-1) {
00858     assert(Ptr && "null SDNode");
00859   }
00860   SDLoc(const Instruction *I, int Order) : Ptr(I), IROrder(Order) {
00861     assert(Order >= 0 && "bad IROrder");
00862   }
00863   unsigned getIROrder() {
00864     if (IROrder >= 0 || Ptr == nullptr) {
00865       return (unsigned)IROrder;
00866     }
00867     const SDNode *N = (const SDNode*)(Ptr);
00868     return N->getIROrder();
00869   }
00870   DebugLoc getDebugLoc() {
00871     if (!Ptr) {
00872       return DebugLoc();
00873     }
00874     if (IROrder >= 0) {
00875       const Instruction *I = (const Instruction*)(Ptr);
00876       return I->getDebugLoc();
00877     }
00878     const SDNode *N = (const SDNode*)(Ptr);
00879     return N->getDebugLoc();
00880   }
00881 };
00882 
00883 
00884 // Define inline functions from the SDValue class.
00885 
00886 inline SDValue::SDValue(SDNode *node, unsigned resno)
00887     : Node(node), ResNo(resno) {
00888   assert((!Node || ResNo < Node->getNumValues()) &&
00889          "Invalid result number for the given node!");
00890   assert(ResNo < -2U && "Cannot use result numbers reserved for DenseMaps.");
00891 }
00892 
00893 inline unsigned SDValue::getOpcode() const {
00894   return Node->getOpcode();
00895 }
00896 inline EVT SDValue::getValueType() const {
00897   return Node->getValueType(ResNo);
00898 }
00899 inline unsigned SDValue::getNumOperands() const {
00900   return Node->getNumOperands();
00901 }
00902 inline const SDValue &SDValue::getOperand(unsigned i) const {
00903   return Node->getOperand(i);
00904 }
00905 inline uint64_t SDValue::getConstantOperandVal(unsigned i) const {
00906   return Node->getConstantOperandVal(i);
00907 }
00908 inline bool SDValue::isTargetOpcode() const {
00909   return Node->isTargetOpcode();
00910 }
00911 inline bool SDValue::isTargetMemoryOpcode() const {
00912   return Node->isTargetMemoryOpcode();
00913 }
00914 inline bool SDValue::isMachineOpcode() const {
00915   return Node->isMachineOpcode();
00916 }
00917 inline unsigned SDValue::getMachineOpcode() const {
00918   return Node->getMachineOpcode();
00919 }
00920 inline bool SDValue::use_empty() const {
00921   return !Node->hasAnyUseOfValue(ResNo);
00922 }
00923 inline bool SDValue::hasOneUse() const {
00924   return Node->hasNUsesOfValue(1, ResNo);
00925 }
00926 inline const DebugLoc SDValue::getDebugLoc() const {
00927   return Node->getDebugLoc();
00928 }
00929 inline void SDValue::dump() const {
00930   return Node->dump();
00931 }
00932 inline void SDValue::dumpr() const {
00933   return Node->dumpr();
00934 }
00935 // Define inline functions from the SDUse class.
00936 
00937 inline void SDUse::set(const SDValue &V) {
00938   if (Val.getNode()) removeFromList();
00939   Val = V;
00940   if (V.getNode()) V.getNode()->addUse(*this);
00941 }
00942 
00943 inline void SDUse::setInitial(const SDValue &V) {
00944   Val = V;
00945   V.getNode()->addUse(*this);
00946 }
00947 
00948 inline void SDUse::setNode(SDNode *N) {
00949   if (Val.getNode()) removeFromList();
00950   Val.setNode(N);
00951   if (N) N->addUse(*this);
00952 }
00953 
00954 /// UnarySDNode - This class is used for single-operand SDNodes.  This is solely
00955 /// to allow co-allocation of node operands with the node itself.
00956 class UnarySDNode : public SDNode {
00957   SDUse Op;
00958 public:
00959   UnarySDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
00960               SDValue X)
00961     : SDNode(Opc, Order, dl, VTs) {
00962     InitOperands(&Op, X);
00963   }
00964 };
00965 
00966 /// BinarySDNode - This class is used for two-operand SDNodes.  This is solely
00967 /// to allow co-allocation of node operands with the node itself.
00968 class BinarySDNode : public SDNode {
00969   SDUse Ops[2];
00970 public:
00971   BinarySDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
00972                SDValue X, SDValue Y)
00973     : SDNode(Opc, Order, dl, VTs) {
00974     InitOperands(Ops, X, Y);
00975   }
00976 };
00977 
00978 /// BinaryWithFlagsSDNode - This class is an extension of BinarySDNode
00979 /// used from those opcodes that have associated extra flags.
00980 class BinaryWithFlagsSDNode : public BinarySDNode {
00981   enum { NUW = (1 << 0), NSW = (1 << 1), EXACT = (1 << 2) };
00982 
00983 public:
00984   BinaryWithFlagsSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
00985                         SDValue X, SDValue Y)
00986       : BinarySDNode(Opc, Order, dl, VTs, X, Y) {}
00987   /// getRawSubclassData - Return the SubclassData value, which contains an
00988   /// encoding of the flags.
00989   /// This function should be used to add subclass data to the NodeID value.
00990   unsigned getRawSubclassData() const { return SubclassData; }
00991   void setHasNoUnsignedWrap(bool b) {
00992     SubclassData = (SubclassData & ~NUW) | (b ? NUW : 0);
00993   }
00994   void setHasNoSignedWrap(bool b) {
00995     SubclassData = (SubclassData & ~NSW) | (b ? NSW : 0);
00996   }
00997   void setIsExact(bool b) {
00998     SubclassData = (SubclassData & ~EXACT) | (b ? EXACT : 0);
00999   }
01000   bool hasNoUnsignedWrap() const { return SubclassData & NUW; }
01001   bool hasNoSignedWrap() const { return SubclassData & NSW; }
01002   bool isExact() const { return SubclassData & EXACT; }
01003   static bool classof(const SDNode *N) {
01004     return isBinOpWithFlags(N->getOpcode());
01005   }
01006 };
01007 
01008 /// TernarySDNode - This class is used for three-operand SDNodes. This is solely
01009 /// to allow co-allocation of node operands with the node itself.
01010 class TernarySDNode : public SDNode {
01011   SDUse Ops[3];
01012 public:
01013   TernarySDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
01014                 SDValue X, SDValue Y, SDValue Z)
01015     : SDNode(Opc, Order, dl, VTs) {
01016     InitOperands(Ops, X, Y, Z);
01017   }
01018 };
01019 
01020 
01021 /// HandleSDNode - This class is used to form a handle around another node that
01022 /// is persistent and is updated across invocations of replaceAllUsesWith on its
01023 /// operand.  This node should be directly created by end-users and not added to
01024 /// the AllNodes list.
01025 class HandleSDNode : public SDNode {
01026   SDUse Op;
01027 public:
01028   explicit HandleSDNode(SDValue X)
01029     : SDNode(ISD::HANDLENODE, 0, DebugLoc(), getSDVTList(MVT::Other)) {
01030     InitOperands(&Op, X);
01031   }
01032   ~HandleSDNode();
01033   const SDValue &getValue() const { return Op; }
01034 };
01035 
01036 class AddrSpaceCastSDNode : public UnarySDNode {
01037 private:
01038   unsigned SrcAddrSpace;
01039   unsigned DestAddrSpace;
01040 
01041 public:
01042   AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT, SDValue X,
01043                       unsigned SrcAS, unsigned DestAS);
01044 
01045   unsigned getSrcAddressSpace() const { return SrcAddrSpace; }
01046   unsigned getDestAddressSpace() const { return DestAddrSpace; }
01047 
01048   static bool classof(const SDNode *N) {
01049     return N->getOpcode() == ISD::ADDRSPACECAST;
01050   }
01051 };
01052 
01053 /// Abstact virtual class for operations for memory operations
01054 class MemSDNode : public SDNode {
01055 private:
01056   // MemoryVT - VT of in-memory value.
01057   EVT MemoryVT;
01058 
01059 protected:
01060   /// MMO - Memory reference information.
01061   MachineMemOperand *MMO;
01062 
01063 public:
01064   MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
01065             EVT MemoryVT, MachineMemOperand *MMO);
01066 
01067   MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
01068             ArrayRef<SDValue> Ops, EVT MemoryVT, MachineMemOperand *MMO);
01069 
01070   bool readMem() const { return MMO->isLoad(); }
01071   bool writeMem() const { return MMO->isStore(); }
01072 
01073   /// Returns alignment and volatility of the memory access
01074   unsigned getOriginalAlignment() const {
01075     return MMO->getBaseAlignment();
01076   }
01077   unsigned getAlignment() const {
01078     return MMO->getAlignment();
01079   }
01080 
01081   /// getRawSubclassData - Return the SubclassData value, which contains an
01082   /// encoding of the volatile flag, as well as bits used by subclasses. This
01083   /// function should only be used to compute a FoldingSetNodeID value.
01084   unsigned getRawSubclassData() const {
01085     return SubclassData;
01086   }
01087 
01088   // We access subclass data here so that we can check consistency
01089   // with MachineMemOperand information.
01090   bool isVolatile() const { return (SubclassData >> 5) & 1; }
01091   bool isNonTemporal() const { return (SubclassData >> 6) & 1; }
01092   bool isInvariant() const { return (SubclassData >> 7) & 1; }
01093 
01094   AtomicOrdering getOrdering() const {
01095     return AtomicOrdering((SubclassData >> 8) & 15);
01096   }
01097   SynchronizationScope getSynchScope() const {
01098     return SynchronizationScope((SubclassData >> 12) & 1);
01099   }
01100 
01101   // Returns the offset from the location of the access.
01102   int64_t getSrcValueOffset() const { return MMO->getOffset(); }
01103 
01104   /// Returns the AA info that describes the dereference.
01105   AAMDNodes getAAInfo() const { return MMO->getAAInfo(); }
01106 
01107   /// Returns the Ranges that describes the dereference.
01108   const MDNode *getRanges() const { return MMO->getRanges(); }
01109 
01110   /// getMemoryVT - Return the type of the in-memory value.
01111   EVT getMemoryVT() const { return MemoryVT; }
01112 
01113   /// getMemOperand - Return a MachineMemOperand object describing the memory
01114   /// reference performed by operation.
01115   MachineMemOperand *getMemOperand() const { return MMO; }
01116 
01117   const MachinePointerInfo &getPointerInfo() const {
01118     return MMO->getPointerInfo();
01119   }
01120 
01121   /// getAddressSpace - Return the address space for the associated pointer
01122   unsigned getAddressSpace() const {
01123     return getPointerInfo().getAddrSpace();
01124   }
01125 
01126   /// refineAlignment - Update this MemSDNode's MachineMemOperand information
01127   /// to reflect the alignment of NewMMO, if it has a greater alignment.
01128   /// This must only be used when the new alignment applies to all users of
01129   /// this MachineMemOperand.
01130   void refineAlignment(const MachineMemOperand *NewMMO) {
01131     MMO->refineAlignment(NewMMO);
01132   }
01133 
01134   const SDValue &getChain() const { return getOperand(0); }
01135   const SDValue &getBasePtr() const {
01136     return getOperand(getOpcode() == ISD::STORE ? 2 : 1);
01137   }
01138 
01139   // Methods to support isa and dyn_cast
01140   static bool classof(const SDNode *N) {
01141     // For some targets, we lower some target intrinsics to a MemIntrinsicNode
01142     // with either an intrinsic or a target opcode.
01143     return N->getOpcode() == ISD::LOAD                ||
01144            N->getOpcode() == ISD::STORE               ||
01145            N->getOpcode() == ISD::PREFETCH            ||
01146            N->getOpcode() == ISD::ATOMIC_CMP_SWAP     ||
01147            N->getOpcode() == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS ||
01148            N->getOpcode() == ISD::ATOMIC_SWAP         ||
01149            N->getOpcode() == ISD::ATOMIC_LOAD_ADD     ||
01150            N->getOpcode() == ISD::ATOMIC_LOAD_SUB     ||
01151            N->getOpcode() == ISD::ATOMIC_LOAD_AND     ||
01152            N->getOpcode() == ISD::ATOMIC_LOAD_OR      ||
01153            N->getOpcode() == ISD::ATOMIC_LOAD_XOR     ||
01154            N->getOpcode() == ISD::ATOMIC_LOAD_NAND    ||
01155            N->getOpcode() == ISD::ATOMIC_LOAD_MIN     ||
01156            N->getOpcode() == ISD::ATOMIC_LOAD_MAX     ||
01157            N->getOpcode() == ISD::ATOMIC_LOAD_UMIN    ||
01158            N->getOpcode() == ISD::ATOMIC_LOAD_UMAX    ||
01159            N->getOpcode() == ISD::ATOMIC_LOAD         ||
01160            N->getOpcode() == ISD::ATOMIC_STORE        ||
01161            N->isTargetMemoryOpcode();
01162   }
01163 };
01164 
01165 /// AtomicSDNode - A SDNode reprenting atomic operations.
01166 ///
01167 class AtomicSDNode : public MemSDNode {
01168   SDUse Ops[4];
01169 
01170   /// For cmpxchg instructions, the ordering requirements when a store does not
01171   /// occur.
01172   AtomicOrdering FailureOrdering;
01173 
01174   void InitAtomic(AtomicOrdering SuccessOrdering,
01175                   AtomicOrdering FailureOrdering,
01176                   SynchronizationScope SynchScope) {
01177     // This must match encodeMemSDNodeFlags() in SelectionDAG.cpp.
01178     assert((SuccessOrdering & 15) == SuccessOrdering &&
01179            "Ordering may not require more than 4 bits!");
01180     assert((FailureOrdering & 15) == FailureOrdering &&
01181            "Ordering may not require more than 4 bits!");
01182     assert((SynchScope & 1) == SynchScope &&
01183            "SynchScope may not require more than 1 bit!");
01184     SubclassData |= SuccessOrdering << 8;
01185     SubclassData |= SynchScope << 12;
01186     this->FailureOrdering = FailureOrdering;
01187     assert(getSuccessOrdering() == SuccessOrdering &&
01188            "Ordering encoding error!");
01189     assert(getFailureOrdering() == FailureOrdering &&
01190            "Ordering encoding error!");
01191     assert(getSynchScope() == SynchScope && "Synch-scope encoding error!");
01192   }
01193 
01194 public:
01195   // Opc:   opcode for atomic
01196   // VTL:    value type list
01197   // Chain:  memory chain for operaand
01198   // Ptr:    address to update as a SDValue
01199   // Cmp:    compare value
01200   // Swp:    swap value
01201   // SrcVal: address to update as a Value (used for MemOperand)
01202   // Align:  alignment of memory
01203   AtomicSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTL,
01204                EVT MemVT, SDValue Chain, SDValue Ptr, SDValue Cmp, SDValue Swp,
01205                MachineMemOperand *MMO, AtomicOrdering Ordering,
01206                SynchronizationScope SynchScope)
01207       : MemSDNode(Opc, Order, dl, VTL, MemVT, MMO) {
01208     InitAtomic(Ordering, Ordering, SynchScope);
01209     InitOperands(Ops, Chain, Ptr, Cmp, Swp);
01210   }
01211   AtomicSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTL,
01212                EVT MemVT,
01213                SDValue Chain, SDValue Ptr,
01214                SDValue Val, MachineMemOperand *MMO,
01215                AtomicOrdering Ordering, SynchronizationScope SynchScope)
01216     : MemSDNode(Opc, Order, dl, VTL, MemVT, MMO) {
01217     InitAtomic(Ordering, Ordering, SynchScope);
01218     InitOperands(Ops, Chain, Ptr, Val);
01219   }
01220   AtomicSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTL,
01221                EVT MemVT,
01222                SDValue Chain, SDValue Ptr,
01223                MachineMemOperand *MMO,
01224                AtomicOrdering Ordering, SynchronizationScope SynchScope)
01225     : MemSDNode(Opc, Order, dl, VTL, MemVT, MMO) {
01226     InitAtomic(Ordering, Ordering, SynchScope);
01227     InitOperands(Ops, Chain, Ptr);
01228   }
01229   AtomicSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTL, EVT MemVT,
01230                const SDValue* AllOps, SDUse *DynOps, unsigned NumOps,
01231                MachineMemOperand *MMO,
01232                AtomicOrdering SuccessOrdering, AtomicOrdering FailureOrdering,
01233                SynchronizationScope SynchScope)
01234     : MemSDNode(Opc, Order, dl, VTL, MemVT, MMO) {
01235     InitAtomic(SuccessOrdering, FailureOrdering, SynchScope);
01236     assert((DynOps || NumOps <= array_lengthof(Ops)) &&
01237            "Too many ops for internal storage!");
01238     InitOperands(DynOps ? DynOps : Ops, AllOps, NumOps);
01239   }
01240 
01241   const SDValue &getBasePtr() const { return getOperand(1); }
01242   const SDValue &getVal() const { return getOperand(2); }
01243 
01244   AtomicOrdering getSuccessOrdering() const {
01245     return getOrdering();
01246   }
01247 
01248   // Not quite enough room in SubclassData for everything, so failure gets its
01249   // own field.
01250   AtomicOrdering getFailureOrdering() const {
01251     return FailureOrdering;
01252   }
01253 
01254   bool isCompareAndSwap() const {
01255     unsigned Op = getOpcode();
01256     return Op == ISD::ATOMIC_CMP_SWAP || Op == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS;
01257   }
01258 
01259   // Methods to support isa and dyn_cast
01260   static bool classof(const SDNode *N) {
01261     return N->getOpcode() == ISD::ATOMIC_CMP_SWAP     ||
01262            N->getOpcode() == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS ||
01263            N->getOpcode() == ISD::ATOMIC_SWAP         ||
01264            N->getOpcode() == ISD::ATOMIC_LOAD_ADD     ||
01265            N->getOpcode() == ISD::ATOMIC_LOAD_SUB     ||
01266            N->getOpcode() == ISD::ATOMIC_LOAD_AND     ||
01267            N->getOpcode() == ISD::ATOMIC_LOAD_OR      ||
01268            N->getOpcode() == ISD::ATOMIC_LOAD_XOR     ||
01269            N->getOpcode() == ISD::ATOMIC_LOAD_NAND    ||
01270            N->getOpcode() == ISD::ATOMIC_LOAD_MIN     ||
01271            N->getOpcode() == ISD::ATOMIC_LOAD_MAX     ||
01272            N->getOpcode() == ISD::ATOMIC_LOAD_UMIN    ||
01273            N->getOpcode() == ISD::ATOMIC_LOAD_UMAX    ||
01274            N->getOpcode() == ISD::ATOMIC_LOAD         ||
01275            N->getOpcode() == ISD::ATOMIC_STORE;
01276   }
01277 };
01278 
01279 /// MemIntrinsicSDNode - This SDNode is used for target intrinsics that touch
01280 /// memory and need an associated MachineMemOperand. Its opcode may be
01281 /// INTRINSIC_VOID, INTRINSIC_W_CHAIN, PREFETCH, or a target-specific opcode
01282 /// with a value not less than FIRST_TARGET_MEMORY_OPCODE.
01283 class MemIntrinsicSDNode : public MemSDNode {
01284 public:
01285   MemIntrinsicSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
01286                      ArrayRef<SDValue> Ops, EVT MemoryVT,
01287                      MachineMemOperand *MMO)
01288     : MemSDNode(Opc, Order, dl, VTs, Ops, MemoryVT, MMO) {
01289   }
01290 
01291   // Methods to support isa and dyn_cast
01292   static bool classof(const SDNode *N) {
01293     // We lower some target intrinsics to their target opcode
01294     // early a node with a target opcode can be of this class
01295     return N->getOpcode() == ISD::INTRINSIC_W_CHAIN ||
01296            N->getOpcode() == ISD::INTRINSIC_VOID ||
01297            N->getOpcode() == ISD::PREFETCH ||
01298            N->isTargetMemoryOpcode();
01299   }
01300 };
01301 
01302 /// ShuffleVectorSDNode - This SDNode is used to implement the code generator
01303 /// support for the llvm IR shufflevector instruction.  It combines elements
01304 /// from two input vectors into a new input vector, with the selection and
01305 /// ordering of elements determined by an array of integers, referred to as
01306 /// the shuffle mask.  For input vectors of width N, mask indices of 0..N-1
01307 /// refer to elements from the LHS input, and indices from N to 2N-1 the RHS.
01308 /// An index of -1 is treated as undef, such that the code generator may put
01309 /// any value in the corresponding element of the result.
01310 class ShuffleVectorSDNode : public SDNode {
01311   SDUse Ops[2];
01312 
01313   // The memory for Mask is owned by the SelectionDAG's OperandAllocator, and
01314   // is freed when the SelectionDAG object is destroyed.
01315   const int *Mask;
01316 protected:
01317   friend class SelectionDAG;
01318   ShuffleVectorSDNode(EVT VT, unsigned Order, DebugLoc dl, SDValue N1,
01319                       SDValue N2, const int *M)
01320     : SDNode(ISD::VECTOR_SHUFFLE, Order, dl, getSDVTList(VT)), Mask(M) {
01321     InitOperands(Ops, N1, N2);
01322   }
01323 public:
01324 
01325   ArrayRef<int> getMask() const {
01326     EVT VT = getValueType(0);
01327     return makeArrayRef(Mask, VT.getVectorNumElements());
01328   }
01329   int getMaskElt(unsigned Idx) const {
01330     assert(Idx < getValueType(0).getVectorNumElements() && "Idx out of range!");
01331     return Mask[Idx];
01332   }
01333 
01334   bool isSplat() const { return isSplatMask(Mask, getValueType(0)); }
01335   int  getSplatIndex() const {
01336     assert(isSplat() && "Cannot get splat index for non-splat!");
01337     EVT VT = getValueType(0);
01338     for (unsigned i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
01339       if (Mask[i] >= 0)
01340         return Mask[i];
01341     }
01342     llvm_unreachable("Splat with all undef indices?");
01343   }
01344   static bool isSplatMask(const int *Mask, EVT VT);
01345 
01346   static bool classof(const SDNode *N) {
01347     return N->getOpcode() == ISD::VECTOR_SHUFFLE;
01348   }
01349 };
01350 
01351 class ConstantSDNode : public SDNode {
01352   const ConstantInt *Value;
01353   friend class SelectionDAG;
01354   ConstantSDNode(bool isTarget, bool isOpaque, const ConstantInt *val, EVT VT)
01355     : SDNode(isTarget ? ISD::TargetConstant : ISD::Constant,
01356              0, DebugLoc(), getSDVTList(VT)), Value(val) {
01357     SubclassData |= (uint16_t)isOpaque;
01358   }
01359 public:
01360 
01361   const ConstantInt *getConstantIntValue() const { return Value; }
01362   const APInt &getAPIntValue() const { return Value->getValue(); }
01363   uint64_t getZExtValue() const { return Value->getZExtValue(); }
01364   int64_t getSExtValue() const { return Value->getSExtValue(); }
01365 
01366   bool isOne() const { return Value->isOne(); }
01367   bool isNullValue() const { return Value->isNullValue(); }
01368   bool isAllOnesValue() const { return Value->isAllOnesValue(); }
01369 
01370   bool isOpaque() const { return SubclassData & 1; }
01371 
01372   static bool classof(const SDNode *N) {
01373     return N->getOpcode() == ISD::Constant ||
01374            N->getOpcode() == ISD::TargetConstant;
01375   }
01376 };
01377 
01378 class ConstantFPSDNode : public SDNode {
01379   const ConstantFP *Value;
01380   friend class SelectionDAG;
01381   ConstantFPSDNode(bool isTarget, const ConstantFP *val, EVT VT)
01382     : SDNode(isTarget ? ISD::TargetConstantFP : ISD::ConstantFP,
01383              0, DebugLoc(), getSDVTList(VT)), Value(val) {
01384   }
01385 public:
01386 
01387   const APFloat& getValueAPF() const { return Value->getValueAPF(); }
01388   const ConstantFP *getConstantFPValue() const { return Value; }
01389 
01390   /// isZero - Return true if the value is positive or negative zero.
01391   bool isZero() const { return Value->isZero(); }
01392 
01393   /// isNaN - Return true if the value is a NaN.
01394   bool isNaN() const { return Value->isNaN(); }
01395 
01396   /// isExactlyValue - We don't rely on operator== working on double values, as
01397   /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
01398   /// As such, this method can be used to do an exact bit-for-bit comparison of
01399   /// two floating point values.
01400 
01401   /// We leave the version with the double argument here because it's just so
01402   /// convenient to write "2.0" and the like.  Without this function we'd
01403   /// have to duplicate its logic everywhere it's called.
01404   bool isExactlyValue(double V) const {
01405     bool ignored;
01406     APFloat Tmp(V);
01407     Tmp.convert(Value->getValueAPF().getSemantics(),
01408                 APFloat::rmNearestTiesToEven, &ignored);
01409     return isExactlyValue(Tmp);
01410   }
01411   bool isExactlyValue(const APFloat& V) const;
01412 
01413   static bool isValueValidForType(EVT VT, const APFloat& Val);
01414 
01415   static bool classof(const SDNode *N) {
01416     return N->getOpcode() == ISD::ConstantFP ||
01417            N->getOpcode() == ISD::TargetConstantFP;
01418   }
01419 };
01420 
01421 class GlobalAddressSDNode : public SDNode {
01422   const GlobalValue *TheGlobal;
01423   int64_t Offset;
01424   unsigned char TargetFlags;
01425   friend class SelectionDAG;
01426   GlobalAddressSDNode(unsigned Opc, unsigned Order, DebugLoc DL,
01427                       const GlobalValue *GA, EVT VT, int64_t o,
01428                       unsigned char TargetFlags);
01429 public:
01430 
01431   const GlobalValue *getGlobal() const { return TheGlobal; }
01432   int64_t getOffset() const { return Offset; }
01433   unsigned char getTargetFlags() const { return TargetFlags; }
01434   // Return the address space this GlobalAddress belongs to.
01435   unsigned getAddressSpace() const;
01436 
01437   static bool classof(const SDNode *N) {
01438     return N->getOpcode() == ISD::GlobalAddress ||
01439            N->getOpcode() == ISD::TargetGlobalAddress ||
01440            N->getOpcode() == ISD::GlobalTLSAddress ||
01441            N->getOpcode() == ISD::TargetGlobalTLSAddress;
01442   }
01443 };
01444 
01445 class FrameIndexSDNode : public SDNode {
01446   int FI;
01447   friend class SelectionDAG;
01448   FrameIndexSDNode(int fi, EVT VT, bool isTarg)
01449     : SDNode(isTarg ? ISD::TargetFrameIndex : ISD::FrameIndex,
01450       0, DebugLoc(), getSDVTList(VT)), FI(fi) {
01451   }
01452 public:
01453 
01454   int getIndex() const { return FI; }
01455 
01456   static bool classof(const SDNode *N) {
01457     return N->getOpcode() == ISD::FrameIndex ||
01458            N->getOpcode() == ISD::TargetFrameIndex;
01459   }
01460 };
01461 
01462 class JumpTableSDNode : public SDNode {
01463   int JTI;
01464   unsigned char TargetFlags;
01465   friend class SelectionDAG;
01466   JumpTableSDNode(int jti, EVT VT, bool isTarg, unsigned char TF)
01467     : SDNode(isTarg ? ISD::TargetJumpTable : ISD::JumpTable,
01468       0, DebugLoc(), getSDVTList(VT)), JTI(jti), TargetFlags(TF) {
01469   }
01470 public:
01471 
01472   int getIndex() const { return JTI; }
01473   unsigned char getTargetFlags() const { return TargetFlags; }
01474 
01475   static bool classof(const SDNode *N) {
01476     return N->getOpcode() == ISD::JumpTable ||
01477            N->getOpcode() == ISD::TargetJumpTable;
01478   }
01479 };
01480 
01481 class ConstantPoolSDNode : public SDNode {
01482   union {
01483     const Constant *ConstVal;
01484     MachineConstantPoolValue *MachineCPVal;
01485   } Val;
01486   int Offset;  // It's a MachineConstantPoolValue if top bit is set.
01487   unsigned Alignment;  // Minimum alignment requirement of CP (not log2 value).
01488   unsigned char TargetFlags;
01489   friend class SelectionDAG;
01490   ConstantPoolSDNode(bool isTarget, const Constant *c, EVT VT, int o,
01491                      unsigned Align, unsigned char TF)
01492     : SDNode(isTarget ? ISD::TargetConstantPool : ISD::ConstantPool, 0,
01493              DebugLoc(), getSDVTList(VT)), Offset(o), Alignment(Align),
01494              TargetFlags(TF) {
01495     assert(Offset >= 0 && "Offset is too large");
01496     Val.ConstVal = c;
01497   }
01498   ConstantPoolSDNode(bool isTarget, MachineConstantPoolValue *v,
01499                      EVT VT, int o, unsigned Align, unsigned char TF)
01500     : SDNode(isTarget ? ISD::TargetConstantPool : ISD::ConstantPool, 0,
01501              DebugLoc(), getSDVTList(VT)), Offset(o), Alignment(Align),
01502              TargetFlags(TF) {
01503     assert(Offset >= 0 && "Offset is too large");
01504     Val.MachineCPVal = v;
01505     Offset |= 1 << (sizeof(unsigned)*CHAR_BIT-1);
01506   }
01507 public:
01508 
01509   bool isMachineConstantPoolEntry() const {
01510     return Offset < 0;
01511   }
01512 
01513   const Constant *getConstVal() const {
01514     assert(!isMachineConstantPoolEntry() && "Wrong constantpool type");
01515     return Val.ConstVal;
01516   }
01517 
01518   MachineConstantPoolValue *getMachineCPVal() const {
01519     assert(isMachineConstantPoolEntry() && "Wrong constantpool type");
01520     return Val.MachineCPVal;
01521   }
01522 
01523   int getOffset() const {
01524     return Offset & ~(1 << (sizeof(unsigned)*CHAR_BIT-1));
01525   }
01526 
01527   // Return the alignment of this constant pool object, which is either 0 (for
01528   // default alignment) or the desired value.
01529   unsigned getAlignment() const { return Alignment; }
01530   unsigned char getTargetFlags() const { return TargetFlags; }
01531 
01532   Type *getType() const;
01533 
01534   static bool classof(const SDNode *N) {
01535     return N->getOpcode() == ISD::ConstantPool ||
01536            N->getOpcode() == ISD::TargetConstantPool;
01537   }
01538 };
01539 
01540 /// Completely target-dependent object reference.
01541 class TargetIndexSDNode : public SDNode {
01542   unsigned char TargetFlags;
01543   int Index;
01544   int64_t Offset;
01545   friend class SelectionDAG;
01546 public:
01547 
01548   TargetIndexSDNode(int Idx, EVT VT, int64_t Ofs, unsigned char TF)
01549     : SDNode(ISD::TargetIndex, 0, DebugLoc(), getSDVTList(VT)),
01550       TargetFlags(TF), Index(Idx), Offset(Ofs) {}
01551 public:
01552 
01553   unsigned char getTargetFlags() const { return TargetFlags; }
01554   int getIndex() const { return Index; }
01555   int64_t getOffset() const { return Offset; }
01556 
01557   static bool classof(const SDNode *N) {
01558     return N->getOpcode() == ISD::TargetIndex;
01559   }
01560 };
01561 
01562 class BasicBlockSDNode : public SDNode {
01563   MachineBasicBlock *MBB;
01564   friend class SelectionDAG;
01565   /// Debug info is meaningful and potentially useful here, but we create
01566   /// blocks out of order when they're jumped to, which makes it a bit
01567   /// harder.  Let's see if we need it first.
01568   explicit BasicBlockSDNode(MachineBasicBlock *mbb)
01569     : SDNode(ISD::BasicBlock, 0, DebugLoc(), getSDVTList(MVT::Other)), MBB(mbb)
01570   {}
01571 public:
01572 
01573   MachineBasicBlock *getBasicBlock() const { return MBB; }
01574 
01575   static bool classof(const SDNode *N) {
01576     return N->getOpcode() == ISD::BasicBlock;
01577   }
01578 };
01579 
01580 /// BuildVectorSDNode - A "pseudo-class" with methods for operating on
01581 /// BUILD_VECTORs.
01582 class BuildVectorSDNode : public SDNode {
01583   // These are constructed as SDNodes and then cast to BuildVectorSDNodes.
01584   explicit BuildVectorSDNode() LLVM_DELETED_FUNCTION;
01585 public:
01586   /// isConstantSplat - Check if this is a constant splat, and if so, find the
01587   /// smallest element size that splats the vector.  If MinSplatBits is
01588   /// nonzero, the element size must be at least that large.  Note that the
01589   /// splat element may be the entire vector (i.e., a one element vector).
01590   /// Returns the splat element value in SplatValue.  Any undefined bits in
01591   /// that value are zero, and the corresponding bits in the SplatUndef mask
01592   /// are set.  The SplatBitSize value is set to the splat element size in
01593   /// bits.  HasAnyUndefs is set to true if any bits in the vector are
01594   /// undefined.  isBigEndian describes the endianness of the target.
01595   bool isConstantSplat(APInt &SplatValue, APInt &SplatUndef,
01596                        unsigned &SplatBitSize, bool &HasAnyUndefs,
01597                        unsigned MinSplatBits = 0,
01598                        bool isBigEndian = false) const;
01599 
01600   /// \brief Returns the splatted value or a null value if this is not a splat.
01601   ///
01602   /// If passed a non-null UndefElements bitvector, it will resize it to match
01603   /// the vector width and set the bits where elements are undef.
01604   SDValue getSplatValue(BitVector *UndefElements = nullptr) const;
01605 
01606   /// \brief Returns the splatted constant or null if this is not a constant
01607   /// splat.
01608   ///
01609   /// If passed a non-null UndefElements bitvector, it will resize it to match
01610   /// the vector width and set the bits where elements are undef.
01611   ConstantSDNode *
01612   getConstantSplatNode(BitVector *UndefElements = nullptr) const;
01613 
01614   /// \brief Returns the splatted constant FP or null if this is not a constant
01615   /// FP splat.
01616   ///
01617   /// If passed a non-null UndefElements bitvector, it will resize it to match
01618   /// the vector width and set the bits where elements are undef.
01619   ConstantFPSDNode *
01620   getConstantFPSplatNode(BitVector *UndefElements = nullptr) const;
01621 
01622   bool isConstant() const;
01623 
01624   static inline bool classof(const SDNode *N) {
01625     return N->getOpcode() == ISD::BUILD_VECTOR;
01626   }
01627 };
01628 
01629 /// SrcValueSDNode - An SDNode that holds an arbitrary LLVM IR Value. This is
01630 /// used when the SelectionDAG needs to make a simple reference to something
01631 /// in the LLVM IR representation.
01632 ///
01633 class SrcValueSDNode : public SDNode {
01634   const Value *V;
01635   friend class SelectionDAG;
01636   /// Create a SrcValue for a general value.
01637   explicit SrcValueSDNode(const Value *v)
01638     : SDNode(ISD::SRCVALUE, 0, DebugLoc(), getSDVTList(MVT::Other)), V(v) {}
01639 
01640 public:
01641   /// getValue - return the contained Value.
01642   const Value *getValue() const { return V; }
01643 
01644   static bool classof(const SDNode *N) {
01645     return N->getOpcode() == ISD::SRCVALUE;
01646   }
01647 };
01648 
01649 class MDNodeSDNode : public SDNode {
01650   const MDNode *MD;
01651   friend class SelectionDAG;
01652   explicit MDNodeSDNode(const MDNode *md)
01653   : SDNode(ISD::MDNODE_SDNODE, 0, DebugLoc(), getSDVTList(MVT::Other)), MD(md)
01654   {}
01655 public:
01656 
01657   const MDNode *getMD() const { return MD; }
01658 
01659   static bool classof(const SDNode *N) {
01660     return N->getOpcode() == ISD::MDNODE_SDNODE;
01661   }
01662 };
01663 
01664 class RegisterSDNode : public SDNode {
01665   unsigned Reg;
01666   friend class SelectionDAG;
01667   RegisterSDNode(unsigned reg, EVT VT)
01668     : SDNode(ISD::Register, 0, DebugLoc(), getSDVTList(VT)), Reg(reg) {
01669   }
01670 public:
01671 
01672   unsigned getReg() const { return Reg; }
01673 
01674   static bool classof(const SDNode *N) {
01675     return N->getOpcode() == ISD::Register;
01676   }
01677 };
01678 
01679 class RegisterMaskSDNode : public SDNode {
01680   // The memory for RegMask is not owned by the node.
01681   const uint32_t *RegMask;
01682   friend class SelectionDAG;
01683   RegisterMaskSDNode(const uint32_t *mask)
01684     : SDNode(ISD::RegisterMask, 0, DebugLoc(), getSDVTList(MVT::Untyped)),
01685       RegMask(mask) {}
01686 public:
01687 
01688   const uint32_t *getRegMask() const { return RegMask; }
01689 
01690   static bool classof(const SDNode *N) {
01691     return N->getOpcode() == ISD::RegisterMask;
01692   }
01693 };
01694 
01695 class BlockAddressSDNode : public SDNode {
01696   const BlockAddress *BA;
01697   int64_t Offset;
01698   unsigned char TargetFlags;
01699   friend class SelectionDAG;
01700   BlockAddressSDNode(unsigned NodeTy, EVT VT, const BlockAddress *ba,
01701                      int64_t o, unsigned char Flags)
01702     : SDNode(NodeTy, 0, DebugLoc(), getSDVTList(VT)),
01703              BA(ba), Offset(o), TargetFlags(Flags) {
01704   }
01705 public:
01706   const BlockAddress *getBlockAddress() const { return BA; }
01707   int64_t getOffset() const { return Offset; }
01708   unsigned char getTargetFlags() const { return TargetFlags; }
01709 
01710   static bool classof(const SDNode *N) {
01711     return N->getOpcode() == ISD::BlockAddress ||
01712            N->getOpcode() == ISD::TargetBlockAddress;
01713   }
01714 };
01715 
01716 class EHLabelSDNode : public SDNode {
01717   SDUse Chain;
01718   MCSymbol *Label;
01719   friend class SelectionDAG;
01720   EHLabelSDNode(unsigned Order, DebugLoc dl, SDValue ch, MCSymbol *L)
01721     : SDNode(ISD::EH_LABEL, Order, dl, getSDVTList(MVT::Other)), Label(L) {
01722     InitOperands(&Chain, ch);
01723   }
01724 public:
01725   MCSymbol *getLabel() const { return Label; }
01726 
01727   static bool classof(const SDNode *N) {
01728     return N->getOpcode() == ISD::EH_LABEL;
01729   }
01730 };
01731 
01732 class ExternalSymbolSDNode : public SDNode {
01733   const char *Symbol;
01734   unsigned char TargetFlags;
01735 
01736   friend class SelectionDAG;
01737   ExternalSymbolSDNode(bool isTarget, const char *Sym, unsigned char TF, EVT VT)
01738     : SDNode(isTarget ? ISD::TargetExternalSymbol : ISD::ExternalSymbol,
01739              0, DebugLoc(), getSDVTList(VT)), Symbol(Sym), TargetFlags(TF) {
01740   }
01741 public:
01742 
01743   const char *getSymbol() const { return Symbol; }
01744   unsigned char getTargetFlags() const { return TargetFlags; }
01745 
01746   static bool classof(const SDNode *N) {
01747     return N->getOpcode() == ISD::ExternalSymbol ||
01748            N->getOpcode() == ISD::TargetExternalSymbol;
01749   }
01750 };
01751 
01752 class CondCodeSDNode : public SDNode {
01753   ISD::CondCode Condition;
01754   friend class SelectionDAG;
01755   explicit CondCodeSDNode(ISD::CondCode Cond)
01756     : SDNode(ISD::CONDCODE, 0, DebugLoc(), getSDVTList(MVT::Other)),
01757       Condition(Cond) {
01758   }
01759 public:
01760 
01761   ISD::CondCode get() const { return Condition; }
01762 
01763   static bool classof(const SDNode *N) {
01764     return N->getOpcode() == ISD::CONDCODE;
01765   }
01766 };
01767 
01768 /// CvtRndSatSDNode - NOTE: avoid using this node as this may disappear in the
01769 /// future and most targets don't support it.
01770 class CvtRndSatSDNode : public SDNode {
01771   ISD::CvtCode CvtCode;
01772   friend class SelectionDAG;
01773   explicit CvtRndSatSDNode(EVT VT, unsigned Order, DebugLoc dl,
01774                            ArrayRef<SDValue> Ops, ISD::CvtCode Code)
01775     : SDNode(ISD::CONVERT_RNDSAT, Order, dl, getSDVTList(VT), Ops),
01776       CvtCode(Code) {
01777     assert(Ops.size() == 5 && "wrong number of operations");
01778   }
01779 public:
01780   ISD::CvtCode getCvtCode() const { return CvtCode; }
01781 
01782   static bool classof(const SDNode *N) {
01783     return N->getOpcode() == ISD::CONVERT_RNDSAT;
01784   }
01785 };
01786 
01787 /// VTSDNode - This class is used to represent EVT's, which are used
01788 /// to parameterize some operations.
01789 class VTSDNode : public SDNode {
01790   EVT ValueType;
01791   friend class SelectionDAG;
01792   explicit VTSDNode(EVT VT)
01793     : SDNode(ISD::VALUETYPE, 0, DebugLoc(), getSDVTList(MVT::Other)),
01794       ValueType(VT) {
01795   }
01796 public:
01797 
01798   EVT getVT() const { return ValueType; }
01799 
01800   static bool classof(const SDNode *N) {
01801     return N->getOpcode() == ISD::VALUETYPE;
01802   }
01803 };
01804 
01805 /// LSBaseSDNode - Base class for LoadSDNode and StoreSDNode
01806 ///
01807 class LSBaseSDNode : public MemSDNode {
01808   //! Operand array for load and store
01809   /*!
01810     \note Moving this array to the base class captures more
01811     common functionality shared between LoadSDNode and
01812     StoreSDNode
01813    */
01814   SDUse Ops[4];
01815 public:
01816   LSBaseSDNode(ISD::NodeType NodeTy, unsigned Order, DebugLoc dl,
01817                SDValue *Operands, unsigned numOperands,
01818                SDVTList VTs, ISD::MemIndexedMode AM, EVT MemVT,
01819                MachineMemOperand *MMO)
01820     : MemSDNode(NodeTy, Order, dl, VTs, MemVT, MMO) {
01821     SubclassData |= AM << 2;
01822     assert(getAddressingMode() == AM && "MemIndexedMode encoding error!");
01823     InitOperands(Ops, Operands, numOperands);
01824     assert((getOffset().getOpcode() == ISD::UNDEF || isIndexed()) &&
01825            "Only indexed loads and stores have a non-undef offset operand");
01826   }
01827 
01828   const SDValue &getOffset() const {
01829     return getOperand(getOpcode() == ISD::LOAD ? 2 : 3);
01830   }
01831 
01832   /// getAddressingMode - Return the addressing mode for this load or store:
01833   /// unindexed, pre-inc, pre-dec, post-inc, or post-dec.
01834   ISD::MemIndexedMode getAddressingMode() const {
01835     return ISD::MemIndexedMode((SubclassData >> 2) & 7);
01836   }
01837 
01838   /// isIndexed - Return true if this is a pre/post inc/dec load/store.
01839   bool isIndexed() const { return getAddressingMode() != ISD::UNINDEXED; }
01840 
01841   /// isUnindexed - Return true if this is NOT a pre/post inc/dec load/store.
01842   bool isUnindexed() const { return getAddressingMode() == ISD::UNINDEXED; }
01843 
01844   static bool classof(const SDNode *N) {
01845     return N->getOpcode() == ISD::LOAD ||
01846            N->getOpcode() == ISD::STORE;
01847   }
01848 };
01849 
01850 /// LoadSDNode - This class is used to represent ISD::LOAD nodes.
01851 ///
01852 class LoadSDNode : public LSBaseSDNode {
01853   friend class SelectionDAG;
01854   LoadSDNode(SDValue *ChainPtrOff, unsigned Order, DebugLoc dl, SDVTList VTs,
01855              ISD::MemIndexedMode AM, ISD::LoadExtType ETy, EVT MemVT,
01856              MachineMemOperand *MMO)
01857     : LSBaseSDNode(ISD::LOAD, Order, dl, ChainPtrOff, 3, VTs, AM, MemVT, MMO) {
01858     SubclassData |= (unsigned short)ETy;
01859     assert(getExtensionType() == ETy && "LoadExtType encoding error!");
01860     assert(readMem() && "Load MachineMemOperand is not a load!");
01861     assert(!writeMem() && "Load MachineMemOperand is a store!");
01862   }
01863 public:
01864 
01865   /// getExtensionType - Return whether this is a plain node,
01866   /// or one of the varieties of value-extending loads.
01867   ISD::LoadExtType getExtensionType() const {
01868     return ISD::LoadExtType(SubclassData & 3);
01869   }
01870 
01871   const SDValue &getBasePtr() const { return getOperand(1); }
01872   const SDValue &getOffset() const { return getOperand(2); }
01873 
01874   static bool classof(const SDNode *N) {
01875     return N->getOpcode() == ISD::LOAD;
01876   }
01877 };
01878 
01879 /// StoreSDNode - This class is used to represent ISD::STORE nodes.
01880 ///
01881 class StoreSDNode : public LSBaseSDNode {
01882   friend class SelectionDAG;
01883   StoreSDNode(SDValue *ChainValuePtrOff, unsigned Order, DebugLoc dl,
01884               SDVTList VTs, ISD::MemIndexedMode AM, bool isTrunc, EVT MemVT,
01885               MachineMemOperand *MMO)
01886     : LSBaseSDNode(ISD::STORE, Order, dl, ChainValuePtrOff, 4,
01887                    VTs, AM, MemVT, MMO) {
01888     SubclassData |= (unsigned short)isTrunc;
01889     assert(isTruncatingStore() == isTrunc && "isTrunc encoding error!");
01890     assert(!readMem() && "Store MachineMemOperand is a load!");
01891     assert(writeMem() && "Store MachineMemOperand is not a store!");
01892   }
01893 public:
01894 
01895   /// isTruncatingStore - Return true if the op does a truncation before store.
01896   /// For integers this is the same as doing a TRUNCATE and storing the result.
01897   /// For floats, it is the same as doing an FP_ROUND and storing the result.
01898   bool isTruncatingStore() const { return SubclassData & 1; }
01899 
01900   const SDValue &getValue() const { return getOperand(1); }
01901   const SDValue &getBasePtr() const { return getOperand(2); }
01902   const SDValue &getOffset() const { return getOperand(3); }
01903 
01904   static bool classof(const SDNode *N) {
01905     return N->getOpcode() == ISD::STORE;
01906   }
01907 };
01908 
01909 /// MachineSDNode - An SDNode that represents everything that will be needed
01910 /// to construct a MachineInstr. These nodes are created during the
01911 /// instruction selection proper phase.
01912 ///
01913 class MachineSDNode : public SDNode {
01914 public:
01915   typedef MachineMemOperand **mmo_iterator;
01916 
01917 private:
01918   friend class SelectionDAG;
01919   MachineSDNode(unsigned Opc, unsigned Order, const DebugLoc DL, SDVTList VTs)
01920     : SDNode(Opc, Order, DL, VTs), MemRefs(nullptr), MemRefsEnd(nullptr) {}
01921 
01922   /// LocalOperands - Operands for this instruction, if they fit here. If
01923   /// they don't, this field is unused.
01924   SDUse LocalOperands[4];
01925 
01926   /// MemRefs - Memory reference descriptions for this instruction.
01927   mmo_iterator MemRefs;
01928   mmo_iterator MemRefsEnd;
01929 
01930 public:
01931   mmo_iterator memoperands_begin() const { return MemRefs; }
01932   mmo_iterator memoperands_end() const { return MemRefsEnd; }
01933   bool memoperands_empty() const { return MemRefsEnd == MemRefs; }
01934 
01935   /// setMemRefs - Assign this MachineSDNodes's memory reference descriptor
01936   /// list. This does not transfer ownership.
01937   void setMemRefs(mmo_iterator NewMemRefs, mmo_iterator NewMemRefsEnd) {
01938     for (mmo_iterator MMI = NewMemRefs, MME = NewMemRefsEnd; MMI != MME; ++MMI)
01939       assert(*MMI && "Null mem ref detected!");
01940     MemRefs = NewMemRefs;
01941     MemRefsEnd = NewMemRefsEnd;
01942   }
01943 
01944   static bool classof(const SDNode *N) {
01945     return N->isMachineOpcode();
01946   }
01947 };
01948 
01949 class SDNodeIterator : public std::iterator<std::forward_iterator_tag,
01950                                             SDNode, ptrdiff_t> {
01951   const SDNode *Node;
01952   unsigned Operand;
01953 
01954   SDNodeIterator(const SDNode *N, unsigned Op) : Node(N), Operand(Op) {}
01955 public:
01956   bool operator==(const SDNodeIterator& x) const {
01957     return Operand == x.Operand;
01958   }
01959   bool operator!=(const SDNodeIterator& x) const { return !operator==(x); }
01960 
01961   const SDNodeIterator &operator=(const SDNodeIterator &I) {
01962     assert(I.Node == Node && "Cannot assign iterators to two different nodes!");
01963     Operand = I.Operand;
01964     return *this;
01965   }
01966 
01967   pointer operator*() const {
01968     return Node->getOperand(Operand).getNode();
01969   }
01970   pointer operator->() const { return operator*(); }
01971 
01972   SDNodeIterator& operator++() {                // Preincrement
01973     ++Operand;
01974     return *this;
01975   }
01976   SDNodeIterator operator++(int) { // Postincrement
01977     SDNodeIterator tmp = *this; ++*this; return tmp;
01978   }
01979   size_t operator-(SDNodeIterator Other) const {
01980     assert(Node == Other.Node &&
01981            "Cannot compare iterators of two different nodes!");
01982     return Operand - Other.Operand;
01983   }
01984 
01985   static SDNodeIterator begin(const SDNode *N) { return SDNodeIterator(N, 0); }
01986   static SDNodeIterator end  (const SDNode *N) {
01987     return SDNodeIterator(N, N->getNumOperands());
01988   }
01989 
01990   unsigned getOperand() const { return Operand; }
01991   const SDNode *getNode() const { return Node; }
01992 };
01993 
01994 template <> struct GraphTraits<SDNode*> {
01995   typedef SDNode NodeType;
01996   typedef SDNodeIterator ChildIteratorType;
01997   static inline NodeType *getEntryNode(SDNode *N) { return N; }
01998   static inline ChildIteratorType child_begin(NodeType *N) {
01999     return SDNodeIterator::begin(N);
02000   }
02001   static inline ChildIteratorType child_end(NodeType *N) {
02002     return SDNodeIterator::end(N);
02003   }
02004 };
02005 
02006 /// LargestSDNode - The largest SDNode class.
02007 ///
02008 typedef AtomicSDNode LargestSDNode;
02009 
02010 /// MostAlignedSDNode - The SDNode class with the greatest alignment
02011 /// requirement.
02012 ///
02013 typedef GlobalAddressSDNode MostAlignedSDNode;
02014 
02015 namespace ISD {
02016   /// isNormalLoad - Returns true if the specified node is a non-extending
02017   /// and unindexed load.
02018   inline bool isNormalLoad(const SDNode *N) {
02019     const LoadSDNode *Ld = dyn_cast<LoadSDNode>(N);
02020     return Ld && Ld->getExtensionType() == ISD::NON_EXTLOAD &&
02021       Ld->getAddressingMode() == ISD::UNINDEXED;
02022   }
02023 
02024   /// isNON_EXTLoad - Returns true if the specified node is a non-extending
02025   /// load.
02026   inline bool isNON_EXTLoad(const SDNode *N) {
02027     return isa<LoadSDNode>(N) &&
02028       cast<LoadSDNode>(N)->getExtensionType() == ISD::NON_EXTLOAD;
02029   }
02030 
02031   /// isEXTLoad - Returns true if the specified node is a EXTLOAD.
02032   ///
02033   inline bool isEXTLoad(const SDNode *N) {
02034     return isa<LoadSDNode>(N) &&
02035       cast<LoadSDNode>(N)->getExtensionType() == ISD::EXTLOAD;
02036   }
02037 
02038   /// isSEXTLoad - Returns true if the specified node is a SEXTLOAD.
02039   ///
02040   inline bool isSEXTLoad(const SDNode *N) {
02041     return isa<LoadSDNode>(N) &&
02042       cast<LoadSDNode>(N)->getExtensionType() == ISD::SEXTLOAD;
02043   }
02044 
02045   /// isZEXTLoad - Returns true if the specified node is a ZEXTLOAD.
02046   ///
02047   inline bool isZEXTLoad(const SDNode *N) {
02048     return isa<LoadSDNode>(N) &&
02049       cast<LoadSDNode>(N)->getExtensionType() == ISD::ZEXTLOAD;
02050   }
02051 
02052   /// isUNINDEXEDLoad - Returns true if the specified node is an unindexed load.
02053   ///
02054   inline bool isUNINDEXEDLoad(const SDNode *N) {
02055     return isa<LoadSDNode>(N) &&
02056       cast<LoadSDNode>(N)->getAddressingMode() == ISD::UNINDEXED;
02057   }
02058 
02059   /// isNormalStore - Returns true if the specified node is a non-truncating
02060   /// and unindexed store.
02061   inline bool isNormalStore(const SDNode *N) {
02062     const StoreSDNode *St = dyn_cast<StoreSDNode>(N);
02063     return St && !St->isTruncatingStore() &&
02064       St->getAddressingMode() == ISD::UNINDEXED;
02065   }
02066 
02067   /// isNON_TRUNCStore - Returns true if the specified node is a non-truncating
02068   /// store.
02069   inline bool isNON_TRUNCStore(const SDNode *N) {
02070     return isa<StoreSDNode>(N) && !cast<StoreSDNode>(N)->isTruncatingStore();
02071   }
02072 
02073   /// isTRUNCStore - Returns true if the specified node is a truncating
02074   /// store.
02075   inline bool isTRUNCStore(const SDNode *N) {
02076     return isa<StoreSDNode>(N) && cast<StoreSDNode>(N)->isTruncatingStore();
02077   }
02078 
02079   /// isUNINDEXEDStore - Returns true if the specified node is an
02080   /// unindexed store.
02081   inline bool isUNINDEXEDStore(const SDNode *N) {
02082     return isa<StoreSDNode>(N) &&
02083       cast<StoreSDNode>(N)->getAddressingMode() == ISD::UNINDEXED;
02084   }
02085 }
02086 
02087 } // end llvm namespace
02088 
02089 #endif