contrib/llvm/include/llvm/CodeGen/SelectionDAGNodes.h

   1 //===- llvm/CodeGen/SelectionDAGNodes.h - SelectionDAG Nodes ----*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file declares the SDNode class and derived classes, which are used to
  11 // represent the nodes and operations present in a SelectionDAG.  These nodes
  12 // and operations are machine code level operations, with some similarities to
  13 // the GCC RTL representation.
  14 //
  15 // Clients should include the SelectionDAG.h file instead of this file directly.
  16 //
  17 //===----------------------------------------------------------------------===//
  18
  19 #ifndef LLVM_CODEGEN_SELECTIONDAGNODES_H
  20 #define LLVM_CODEGEN_SELECTIONDAGNODES_H
  21
  22 #include "llvm/ADT/APFloat.h"
  23 #include "llvm/ADT/ArrayRef.h"
  24 #include "llvm/ADT/BitVector.h"
  25 #include "llvm/ADT/FoldingSet.h"
  26 #include "llvm/ADT/GraphTraits.h"
  27 #include "llvm/ADT/SmallPtrSet.h"
  28 #include "llvm/ADT/SmallVector.h"
  29 #include "llvm/ADT/ilist_node.h"
  30 #include "llvm/ADT/iterator.h"
  31 #include "llvm/ADT/iterator_range.h"
  32 #include "llvm/CodeGen/ISDOpcodes.h"
  33 #include "llvm/CodeGen/MachineMemOperand.h"
  34 #include "llvm/CodeGen/ValueTypes.h"
  35 #include "llvm/IR/Constants.h"
  36 #include "llvm/IR/DebugLoc.h"
  37 #include "llvm/IR/Instruction.h"
  38 #include "llvm/IR/Instructions.h"
  39 #include "llvm/IR/Metadata.h"
  40 #include "llvm/IR/Operator.h"
  41 #include "llvm/Support/AlignOf.h"
  42 #include "llvm/Support/AtomicOrdering.h"
  43 #include "llvm/Support/Casting.h"
  44 #include "llvm/Support/ErrorHandling.h"
  45 #include "llvm/Support/MachineValueType.h"
  46 #include <algorithm>
  47 #include <cassert>
  48 #include <climits>
  49 #include <cstddef>
  50 #include <cstdint>
  51 #include <cstring>
  52 #include <iterator>
  53 #include <string>
  54 #include <tuple>
  55
  56 namespace llvm {
  57
  58 class APInt;
  59 class Constant;
  60 template <typename T> struct DenseMapInfo;
  61 class GlobalValue;
  62 class MachineBasicBlock;
  63 class MachineConstantPoolValue;
  64 class MCSymbol;
  65 class raw_ostream;
  66 class SDNode;
  67 class SelectionDAG;
  68 class Type;
  69 class Value;
  70
  71 void checkForCycles(const SDNode *N, const SelectionDAG *DAG = nullptr,
  72                     bool force = false);
  73
  74 /// This represents a list of ValueType's that has been intern'd by
  75 /// a SelectionDAG.  Instances of this simple value class are returned by
  76 /// SelectionDAG::getVTList(...).
  77 ///
  78 struct SDVTList {
  79   const EVT *VTs;
  80   unsigned int NumVTs;
  81 };
  82
  83 namespace ISD {
  84
  85   /// Node predicates
  86
  87   /// If N is a BUILD_VECTOR node whose elements are all the same constant or
  88   /// undefined, return true and return the constant value in \p SplatValue.
  89   bool isConstantSplatVector(const SDNode *N, APInt &SplatValue);
  90
  91   /// Return true if the specified node is a BUILD_VECTOR where all of the
  92   /// elements are ~0 or undef.
  93   bool isBuildVectorAllOnes(const SDNode *N);
  94
  95   /// Return true if the specified node is a BUILD_VECTOR where all of the
  96   /// elements are 0 or undef.
  97   bool isBuildVectorAllZeros(const SDNode *N);
  98
  99   /// Return true if the specified node is a BUILD_VECTOR node of all
 100   /// ConstantSDNode or undef.
 101   bool isBuildVectorOfConstantSDNodes(const SDNode *N);
 102
 103   /// Return true if the specified node is a BUILD_VECTOR node of all
 104   /// ConstantFPSDNode or undef.
 105   bool isBuildVectorOfConstantFPSDNodes(const SDNode *N);
 106
 107   /// Return true if the node has at least one operand and all operands of the
 108   /// specified node are ISD::UNDEF.
 109   bool allOperandsUndef(const SDNode *N);
 110
 111 } // end namespace ISD
 112
 113 //===----------------------------------------------------------------------===//
 114 /// Unlike LLVM values, Selection DAG nodes may return multiple
 115 /// values as the result of a computation.  Many nodes return multiple values,
 116 /// from loads (which define a token and a return value) to ADDC (which returns
 117 /// a result and a carry value), to calls (which may return an arbitrary number
 118 /// of values).
 119 ///
 120 /// As such, each use of a SelectionDAG computation must indicate the node that
 121 /// computes it as well as which return value to use from that node.  This pair
 122 /// of information is represented with the SDValue value type.
 123 ///
 124 class SDValue {
 125   friend struct DenseMapInfo<SDValue>;
 126
 127   SDNode *Node = nullptr; // The node defining the value we are using.
 128   unsigned ResNo = 0;     // Which return value of the node we are using.
 129
 130 public:
 131   SDValue() = default;
 132   SDValue(SDNode *node, unsigned resno);
 133
 134   /// get the index which selects a specific result in the SDNode
 135   unsigned getResNo() const { return ResNo; }
 136
 137   /// get the SDNode which holds the desired result
 138   SDNode *getNode() const { return Node; }
 139
 140   /// set the SDNode
 141   void setNode(SDNode *N) { Node = N; }
 142
 143   inline SDNode *operator->() const { return Node; }
 144
 145   bool operator==(const SDValue &O) const {
 146     return Node == O.Node && ResNo == O.ResNo;
 147   }
 148   bool operator!=(const SDValue &O) const {
 149     return !operator==(O);
 150   }
 151   bool operator<(const SDValue &O) const {
 152     return std::tie(Node, ResNo) < std::tie(O.Node, O.ResNo);
 153   }
 154   explicit operator bool() const {
 155     return Node != nullptr;
 156   }
 157
 158   SDValue getValue(unsigned R) const {
 159     return SDValue(Node, R);
 160   }
 161
 162   /// Return true if this node is an operand of N.
 163   bool isOperandOf(const SDNode *N) const;
 164
 165   /// Return the ValueType of the referenced return value.
 166   inline EVT getValueType() const;
 167
 168   /// Return the simple ValueType of the referenced return value.
 169   MVT getSimpleValueType() const {
 170     return getValueType().getSimpleVT();
 171   }
 172
 173   /// Returns the size of the value in bits.
 174   unsigned getValueSizeInBits() const {
 175     return getValueType().getSizeInBits();
 176   }
 177
 178   unsigned getScalarValueSizeInBits() const {
 179     return getValueType().getScalarType().getSizeInBits();
 180   }
 181
 182   // Forwarding methods - These forward to the corresponding methods in SDNode.
 183   inline unsigned getOpcode() const;
 184   inline unsigned getNumOperands() const;
 185   inline const SDValue &getOperand(unsigned i) const;
 186   inline uint64_t getConstantOperandVal(unsigned i) const;
 187   inline bool isTargetMemoryOpcode() const;
 188   inline bool isTargetOpcode() const;
 189   inline bool isMachineOpcode() const;
 190   inline bool isUndef() const;
 191   inline unsigned getMachineOpcode() const;
 192   inline const DebugLoc &getDebugLoc() const;
 193   inline void dump() const;
 194   inline void dump(const SelectionDAG *G) const;
 195   inline void dumpr() const;
 196   inline void dumpr(const SelectionDAG *G) const;
 197
 198   /// Return true if this operand (which must be a chain) reaches the
 199   /// specified operand without crossing any side-effecting instructions.
 200   /// In practice, this looks through token factors and non-volatile loads.
 201   /// In order to remain efficient, this only
 202   /// looks a couple of nodes in, it does not do an exhaustive search.
 203   bool reachesChainWithoutSideEffects(SDValue Dest,
 204                                       unsigned Depth = 2) const;
 205
 206   /// Return true if there are no nodes using value ResNo of Node.
 207   inline bool use_empty() const;
 208
 209   /// Return true if there is exactly one node using value ResNo of Node.
 210   inline bool hasOneUse() const;
 211 };
 212
 213 template<> struct DenseMapInfo<SDValue> {
 214   static inline SDValue getEmptyKey() {
 215     SDValue V;
 216     V.ResNo = -1U;
 217     return V;
 218   }
 219
 220   static inline SDValue getTombstoneKey() {
 221     SDValue V;
 222     V.ResNo = -2U;
 223     return V;
 224   }
 225
 226   static unsigned getHashValue(const SDValue &Val) {
 227     return ((unsigned)((uintptr_t)Val.getNode() >> 4) ^
 228             (unsigned)((uintptr_t)Val.getNode() >> 9)) + Val.getResNo();
 229   }
 230
 231   static bool isEqual(const SDValue &LHS, const SDValue &RHS) {
 232     return LHS == RHS;
 233   }
 234 };
 235 template <> struct isPodLike<SDValue> { static const bool value = true; };
 236
 237 /// Allow casting operators to work directly on
 238 /// SDValues as if they were SDNode*'s.
 239 template<> struct simplify_type<SDValue> {
 240   using SimpleType = SDNode *;
 241
 242   static SimpleType getSimplifiedValue(SDValue &Val) {
 243     return Val.getNode();
 244   }
 245 };
 246 template<> struct simplify_type<const SDValue> {
 247   using SimpleType = /*const*/ SDNode *;
 248
 249   static SimpleType getSimplifiedValue(const SDValue &Val) {
 250     return Val.getNode();
 251   }
 252 };
 253
 254 /// Represents a use of a SDNode. This class holds an SDValue,
 255 /// which records the SDNode being used and the result number, a
 256 /// pointer to the SDNode using the value, and Next and Prev pointers,
 257 /// which link together all the uses of an SDNode.
 258 ///
 259 class SDUse {
 260   /// Val - The value being used.
 261   SDValue Val;
 262   /// User - The user of this value.
 263   SDNode *User = nullptr;
 264   /// Prev, Next - Pointers to the uses list of the SDNode referred by
 265   /// this operand.
 266   SDUse **Prev = nullptr;
 267   SDUse *Next = nullptr;
 268
 269 public:
 270   SDUse() = default;
 271   SDUse(const SDUse &U) = delete;
 272   SDUse &operator=(const SDUse &) = delete;
 273
 274   /// Normally SDUse will just implicitly convert to an SDValue that it holds.
 275   operator const SDValue&() const { return Val; }
 276
 277   /// If implicit conversion to SDValue doesn't work, the get() method returns
 278   /// the SDValue.
 279   const SDValue &get() const { return Val; }
 280
 281   /// This returns the SDNode that contains this Use.
 282   SDNode *getUser() { return User; }
 283
 284   /// Get the next SDUse in the use list.
 285   SDUse *getNext() const { return Next; }
 286
 287   /// Convenience function for get().getNode().
 288   SDNode *getNode() const { return Val.getNode(); }
 289   /// Convenience function for get().getResNo().
 290   unsigned getResNo() const { return Val.getResNo(); }
 291   /// Convenience function for get().getValueType().
 292   EVT getValueType() const { return Val.getValueType(); }
 293
 294   /// Convenience function for get().operator==
 295   bool operator==(const SDValue &V) const {
 296     return Val == V;
 297   }
 298
 299   /// Convenience function for get().operator!=
 300   bool operator!=(const SDValue &V) const {
 301     return Val != V;
 302   }
 303
 304   /// Convenience function for get().operator<
 305   bool operator<(const SDValue &V) const {
 306     return Val < V;
 307   }
 308
 309 private:
 310   friend class SelectionDAG;
 311   friend class SDNode;
 312   // TODO: unfriend HandleSDNode once we fix its operand handling.
 313   friend class HandleSDNode;
 314
 315   void setUser(SDNode *p) { User = p; }
 316
 317   /// Remove this use from its existing use list, assign it the
 318   /// given value, and add it to the new value's node's use list.
 319   inline void set(const SDValue &V);
 320   /// Like set, but only supports initializing a newly-allocated
 321   /// SDUse with a non-null value.
 322   inline void setInitial(const SDValue &V);
 323   /// Like set, but only sets the Node portion of the value,
 324   /// leaving the ResNo portion unmodified.
 325   inline void setNode(SDNode *N);
 326
 327   void addToList(SDUse **List) {
 328     Next = *List;
 329     if (Next) Next->Prev = &Next;
 330     Prev = List;
 331     *List = this;
 332   }
 333
 334   void removeFromList() {
 335     *Prev = Next;
 336     if (Next) Next->Prev = Prev;
 337   }
 338 };
 339
 340 /// simplify_type specializations - Allow casting operators to work directly on
 341 /// SDValues as if they were SDNode*'s.
 342 template<> struct simplify_type<SDUse> {
 343   using SimpleType = SDNode *;
 344
 345   static SimpleType getSimplifiedValue(SDUse &Val) {
 346     return Val.getNode();
 347   }
 348 };
 349
 350 /// These are IR-level optimization flags that may be propagated to SDNodes.
 351 /// TODO: This data structure should be shared by the IR optimizer and the
 352 /// the backend.
 353 struct SDNodeFlags {
 354 private:
 355   // This bit is used to determine if the flags are in a defined state.
 356   // Flag bits can only be masked out during intersection if the masking flags
 357   // are defined.
 358   bool AnyDefined : 1;
 359
 360   bool NoUnsignedWrap : 1;
 361   bool NoSignedWrap : 1;
 362   bool Exact : 1;
 363   bool NoNaNs : 1;
 364   bool NoInfs : 1;
 365   bool NoSignedZeros : 1;
 366   bool AllowReciprocal : 1;
 367   bool VectorReduction : 1;
 368   bool AllowContract : 1;
 369   bool ApproximateFuncs : 1;
 370   bool AllowReassociation : 1;
 371
 372 public:
 373   /// Default constructor turns off all optimization flags.
 374   SDNodeFlags()
 375       : AnyDefined(false), NoUnsignedWrap(false), NoSignedWrap(false),
 376         Exact(false), NoNaNs(false), NoInfs(false),
 377         NoSignedZeros(false), AllowReciprocal(false), VectorReduction(false),
 378         AllowContract(false), ApproximateFuncs(false),
 379         AllowReassociation(false) {}
 380
 381   /// Propagate the fast-math-flags from an IR FPMathOperator.
 382   void copyFMF(const FPMathOperator &FPMO) {
 383     setNoNaNs(FPMO.hasNoNaNs());
 384     setNoInfs(FPMO.hasNoInfs());
 385     setNoSignedZeros(FPMO.hasNoSignedZeros());
 386     setAllowReciprocal(FPMO.hasAllowReciprocal());
 387     setAllowContract(FPMO.hasAllowContract());
 388     setApproximateFuncs(FPMO.hasApproxFunc());
 389     setAllowReassociation(FPMO.hasAllowReassoc());
 390   }
 391
 392   /// Sets the state of the flags to the defined state.
 393   void setDefined() { AnyDefined = true; }
 394   /// Returns true if the flags are in a defined state.
 395   bool isDefined() const { return AnyDefined; }
 396
 397   // These are mutators for each flag.
 398   void setNoUnsignedWrap(bool b) {
 399     setDefined();
 400     NoUnsignedWrap = b;
 401   }
 402   void setNoSignedWrap(bool b) {
 403     setDefined();
 404     NoSignedWrap = b;
 405   }
 406   void setExact(bool b) {
 407     setDefined();
 408     Exact = b;
 409   }
 410   void setNoNaNs(bool b) {
 411     setDefined();
 412     NoNaNs = b;
 413   }
 414   void setNoInfs(bool b) {
 415     setDefined();
 416     NoInfs = b;
 417   }
 418   void setNoSignedZeros(bool b) {
 419     setDefined();
 420     NoSignedZeros = b;
 421   }
 422   void setAllowReciprocal(bool b) {
 423     setDefined();
 424     AllowReciprocal = b;
 425   }
 426   void setVectorReduction(bool b) {
 427     setDefined();
 428     VectorReduction = b;
 429   }
 430   void setAllowContract(bool b) {
 431     setDefined();
 432     AllowContract = b;
 433   }
 434   void setApproximateFuncs(bool b) {
 435     setDefined();
 436     ApproximateFuncs = b;
 437   }
 438   void setAllowReassociation(bool b) {
 439     setDefined();
 440     AllowReassociation = b;
 441   }
 442
 443   // These are accessors for each flag.
 444   bool hasNoUnsignedWrap() const { return NoUnsignedWrap; }
 445   bool hasNoSignedWrap() const { return NoSignedWrap; }
 446   bool hasExact() const { return Exact; }
 447   bool hasNoNaNs() const { return NoNaNs; }
 448   bool hasNoInfs() const { return NoInfs; }
 449   bool hasNoSignedZeros() const { return NoSignedZeros; }
 450   bool hasAllowReciprocal() const { return AllowReciprocal; }
 451   bool hasVectorReduction() const { return VectorReduction; }
 452   bool hasAllowContract() const { return AllowContract; }
 453   bool hasApproximateFuncs() const { return ApproximateFuncs; }
 454   bool hasAllowReassociation() const { return AllowReassociation; }
 455
 456   bool isFast() const {
 457     return NoSignedZeros && AllowReciprocal && NoNaNs && NoInfs &&
 458            AllowContract && ApproximateFuncs && AllowReassociation;
 459   }
 460
 461   /// Clear any flags in this flag set that aren't also set in Flags.
 462   /// If the given Flags are undefined then don't do anything.
 463   void intersectWith(const SDNodeFlags Flags) {
 464     if (!Flags.isDefined())
 465       return;
 466     NoUnsignedWrap &= Flags.NoUnsignedWrap;
 467     NoSignedWrap &= Flags.NoSignedWrap;
 468     Exact &= Flags.Exact;
 469     NoNaNs &= Flags.NoNaNs;
 470     NoInfs &= Flags.NoInfs;
 471     NoSignedZeros &= Flags.NoSignedZeros;
 472     AllowReciprocal &= Flags.AllowReciprocal;
 473     VectorReduction &= Flags.VectorReduction;
 474     AllowContract &= Flags.AllowContract;
 475     ApproximateFuncs &= Flags.ApproximateFuncs;
 476     AllowReassociation &= Flags.AllowReassociation;
 477   }
 478 };
 479
 480 /// Represents one node in the SelectionDAG.
 481 ///
 482 class SDNode : public FoldingSetNode, public ilist_node<SDNode> {
 483 private:
 484   /// The operation that this node performs.
 485   int16_t NodeType;
 486
 487 protected:
 488   // We define a set of mini-helper classes to help us interpret the bits in our
 489   // SubclassData.  These are designed to fit within a uint16_t so they pack
 490   // with NodeType.
 491
 492   class SDNodeBitfields {
 493     friend class SDNode;
 494     friend class MemIntrinsicSDNode;
 495     friend class MemSDNode;
 496     friend class SelectionDAG;
 497
 498     uint16_t HasDebugValue : 1;
 499     uint16_t IsMemIntrinsic : 1;
 500     uint16_t IsDivergent : 1;
 501   };
 502   enum { NumSDNodeBits = 3 };
 503
 504   class ConstantSDNodeBitfields {
 505     friend class ConstantSDNode;
 506
 507     uint16_t : NumSDNodeBits;
 508
 509     uint16_t IsOpaque : 1;
 510   };
 511
 512   class MemSDNodeBitfields {
 513     friend class MemSDNode;
 514     friend class MemIntrinsicSDNode;
 515     friend class AtomicSDNode;
 516
 517     uint16_t : NumSDNodeBits;
 518
 519     uint16_t IsVolatile : 1;
 520     uint16_t IsNonTemporal : 1;
 521     uint16_t IsDereferenceable : 1;
 522     uint16_t IsInvariant : 1;
 523   };
 524   enum { NumMemSDNodeBits = NumSDNodeBits + 4 };
 525
 526   class LSBaseSDNodeBitfields {
 527     friend class LSBaseSDNode;
 528
 529     uint16_t : NumMemSDNodeBits;
 530
 531     uint16_t AddressingMode : 3; // enum ISD::MemIndexedMode
 532   };
 533   enum { NumLSBaseSDNodeBits = NumMemSDNodeBits + 3 };
 534
 535   class LoadSDNodeBitfields {
 536     friend class LoadSDNode;
 537     friend class MaskedLoadSDNode;
 538
 539     uint16_t : NumLSBaseSDNodeBits;
 540
 541     uint16_t ExtTy : 2; // enum ISD::LoadExtType
 542     uint16_t IsExpanding : 1;
 543   };
 544
 545   class StoreSDNodeBitfields {
 546     friend class StoreSDNode;
 547     friend class MaskedStoreSDNode;
 548
 549     uint16_t : NumLSBaseSDNodeBits;
 550
 551     uint16_t IsTruncating : 1;
 552     uint16_t IsCompressing : 1;
 553   };
 554
 555   union {
 556     char RawSDNodeBits[sizeof(uint16_t)];
 557     SDNodeBitfields SDNodeBits;
 558     ConstantSDNodeBitfields ConstantSDNodeBits;
 559     MemSDNodeBitfields MemSDNodeBits;
 560     LSBaseSDNodeBitfields LSBaseSDNodeBits;
 561     LoadSDNodeBitfields LoadSDNodeBits;
 562     StoreSDNodeBitfields StoreSDNodeBits;
 563   };
 564
 565   // RawSDNodeBits must cover the entirety of the union.  This means that all of
 566   // the union's members must have size <= RawSDNodeBits.  We write the RHS as
 567   // "2" instead of sizeof(RawSDNodeBits) because MSVC can't handle the latter.
 568   static_assert(sizeof(SDNodeBitfields) <= 2, "field too wide");
 569   static_assert(sizeof(ConstantSDNodeBitfields) <= 2, "field too wide");
 570   static_assert(sizeof(MemSDNodeBitfields) <= 2, "field too wide");
 571   static_assert(sizeof(LSBaseSDNodeBitfields) <= 2, "field too wide");
 572   static_assert(sizeof(LoadSDNodeBitfields) <= 2, "field too wide");
 573   static_assert(sizeof(StoreSDNodeBitfields) <= 2, "field too wide");
 574
 575 private:
 576   friend class SelectionDAG;
 577   // TODO: unfriend HandleSDNode once we fix its operand handling.
 578   friend class HandleSDNode;
 579
 580   /// Unique id per SDNode in the DAG.
 581   int NodeId = -1;
 582
 583   /// The values that are used by this operation.
 584   SDUse *OperandList = nullptr;
 585
 586   /// The types of the values this node defines.  SDNode's may
 587   /// define multiple values simultaneously.
 588   const EVT *ValueList;
 589
 590   /// List of uses for this SDNode.
 591   SDUse *UseList = nullptr;
 592
 593   /// The number of entries in the Operand/Value list.
 594   unsigned short NumOperands = 0;
 595   unsigned short NumValues;
 596
 597   // The ordering of the SDNodes. It roughly corresponds to the ordering of the
 598   // original LLVM instructions.
 599   // This is used for turning off scheduling, because we'll forgo
 600   // the normal scheduling algorithms and output the instructions according to
 601   // this ordering.
 602   unsigned IROrder;
 603
 604   /// Source line information.
 605   DebugLoc debugLoc;
 606
 607   /// Return a pointer to the specified value type.
 608   static const EVT *getValueTypeList(EVT VT);
 609
 610   SDNodeFlags Flags;
 611
 612 public:
 613   /// Unique and persistent id per SDNode in the DAG.
 614   /// Used for debug printing.
 615   uint16_t PersistentId;
 616
 617   //===--------------------------------------------------------------------===//
 618   //  Accessors
 619   //
 620
 621   /// Return the SelectionDAG opcode value for this node. For
 622   /// pre-isel nodes (those for which isMachineOpcode returns false), these
 623   /// are the opcode values in the ISD and <target>ISD namespaces. For
 624   /// post-isel opcodes, see getMachineOpcode.
 625   unsigned getOpcode()  const { return (unsigned short)NodeType; }
 626
 627   /// Test if this node has a target-specific opcode (in the
 628   /// \<target\>ISD namespace).
 629   bool isTargetOpcode() const { return NodeType >= ISD::BUILTIN_OP_END; }
 630
 631   /// Test if this node has a target-specific
 632   /// memory-referencing opcode (in the \<target\>ISD namespace and
 633   /// greater than FIRST_TARGET_MEMORY_OPCODE).
 634   bool isTargetMemoryOpcode() const {
 635     return NodeType >= ISD::FIRST_TARGET_MEMORY_OPCODE;
 636   }
 637
 638   /// Return true if the type of the node type undefined.
 639   bool isUndef() const { return NodeType == ISD::UNDEF; }
 640
 641   /// Test if this node is a memory intrinsic (with valid pointer information).
 642   /// INTRINSIC_W_CHAIN and INTRINSIC_VOID nodes are sometimes created for
 643   /// non-memory intrinsics (with chains) that are not really instances of
 644   /// MemSDNode. For such nodes, we need some extra state to determine the
 645   /// proper classof relationship.
 646   bool isMemIntrinsic() const {
 647     return (NodeType == ISD::INTRINSIC_W_CHAIN ||
 648             NodeType == ISD::INTRINSIC_VOID) &&
 649            SDNodeBits.IsMemIntrinsic;
 650   }
 651
 652   /// Test if this node is a strict floating point pseudo-op.
 653   bool isStrictFPOpcode() {
 654     switch (NodeType) {
 655       default:
 656         return false;
 657       case ISD::STRICT_FADD:
 658       case ISD::STRICT_FSUB:
 659       case ISD::STRICT_FMUL:
 660       case ISD::STRICT_FDIV:
 661       case ISD::STRICT_FREM:
 662       case ISD::STRICT_FMA:
 663       case ISD::STRICT_FSQRT:
 664       case ISD::STRICT_FPOW:
 665       case ISD::STRICT_FPOWI:
 666       case ISD::STRICT_FSIN:
 667       case ISD::STRICT_FCOS:
 668       case ISD::STRICT_FEXP:
 669       case ISD::STRICT_FEXP2:
 670       case ISD::STRICT_FLOG:
 671       case ISD::STRICT_FLOG10:
 672       case ISD::STRICT_FLOG2:
 673       case ISD::STRICT_FRINT:
 674       case ISD::STRICT_FNEARBYINT:
 675       case ISD::STRICT_FMAXNUM:
 676       case ISD::STRICT_FMINNUM:
 677       case ISD::STRICT_FCEIL:
 678       case ISD::STRICT_FFLOOR:
 679       case ISD::STRICT_FROUND:
 680       case ISD::STRICT_FTRUNC:
 681         return true;
 682     }
 683   }
 684
 685   /// Test if this node has a post-isel opcode, directly
 686   /// corresponding to a MachineInstr opcode.
 687   bool isMachineOpcode() const { return NodeType < 0; }
 688
 689   /// This may only be called if isMachineOpcode returns
 690   /// true. It returns the MachineInstr opcode value that the node's opcode
 691   /// corresponds to.
 692   unsigned getMachineOpcode() const {
 693     assert(isMachineOpcode() && "Not a MachineInstr opcode!");
 694     return ~NodeType;
 695   }
 696
 697   bool getHasDebugValue() const { return SDNodeBits.HasDebugValue; }
 698   void setHasDebugValue(bool b) { SDNodeBits.HasDebugValue = b; }
 699
 700   bool isDivergent() const { return SDNodeBits.IsDivergent; }
 701
 702   /// Return true if there are no uses of this node.
 703   bool use_empty() const { return UseList == nullptr; }
 704
 705   /// Return true if there is exactly one use of this node.
 706   bool hasOneUse() const {
 707     return !use_empty() && std::next(use_begin()) == use_end();
 708   }
 709
 710   /// Return the number of uses of this node. This method takes
 711   /// time proportional to the number of uses.
 712   size_t use_size() const { return std::distance(use_begin(), use_end()); }
 713
 714   /// Return the unique node id.
 715   int getNodeId() const { return NodeId; }
 716
 717   /// Set unique node id.
 718   void setNodeId(int Id) { NodeId = Id; }
 719
 720   /// Return the node ordering.
 721   unsigned getIROrder() const { return IROrder; }
 722
 723   /// Set the node ordering.
 724   void setIROrder(unsigned Order) { IROrder = Order; }
 725
 726   /// Return the source location info.
 727   const DebugLoc &getDebugLoc() const { return debugLoc; }
 728
 729   /// Set source location info.  Try to avoid this, putting
 730   /// it in the constructor is preferable.
 731   void setDebugLoc(DebugLoc dl) { debugLoc = std::move(dl); }
 732
 733   /// This class provides iterator support for SDUse
 734   /// operands that use a specific SDNode.
 735   class use_iterator
 736     : public std::iterator<std::forward_iterator_tag, SDUse, ptrdiff_t> {
 737     friend class SDNode;
 738
 739     SDUse *Op = nullptr;
 740
 741     explicit use_iterator(SDUse *op) : Op(op) {}
 742
 743   public:
 744     using reference = std::iterator<std::forward_iterator_tag,
 745                                     SDUse, ptrdiff_t>::reference;
 746     using pointer = std::iterator<std::forward_iterator_tag,
 747                                   SDUse, ptrdiff_t>::pointer;
 748
 749     use_iterator() = default;
 750     use_iterator(const use_iterator &I) : Op(I.Op) {}
 751
 752     bool operator==(const use_iterator &x) const {
 753       return Op == x.Op;
 754     }
 755     bool operator!=(const use_iterator &x) const {
 756       return !operator==(x);
 757     }
 758
 759     /// Return true if this iterator is at the end of uses list.
 760     bool atEnd() const { return Op == nullptr; }
 761
 762     // Iterator traversal: forward iteration only.
 763     use_iterator &operator++() {          // Preincrement
 764       assert(Op && "Cannot increment end iterator!");
 765       Op = Op->getNext();
 766       return *this;
 767     }
 768
 769     use_iterator operator++(int) {        // Postincrement
 770       use_iterator tmp = *this; ++*this; return tmp;
 771     }
 772
 773     /// Retrieve a pointer to the current user node.
 774     SDNode *operator*() const {
 775       assert(Op && "Cannot dereference end iterator!");
 776       return Op->getUser();
 777     }
 778
 779     SDNode *operator->() const { return operator*(); }
 780
 781     SDUse &getUse() const { return *Op; }
 782
 783     /// Retrieve the operand # of this use in its user.
 784     unsigned getOperandNo() const {
 785       assert(Op && "Cannot dereference end iterator!");
 786       return (unsigned)(Op - Op->getUser()->OperandList);
 787     }
 788   };
 789
 790   /// Provide iteration support to walk over all uses of an SDNode.
 791   use_iterator use_begin() const {
 792     return use_iterator(UseList);
 793   }
 794
 795   static use_iterator use_end() { return use_iterator(nullptr); }
 796
 797   inline iterator_range<use_iterator> uses() {
 798     return make_range(use_begin(), use_end());
 799   }
 800   inline iterator_range<use_iterator> uses() const {
 801     return make_range(use_begin(), use_end());
 802   }
 803
 804   /// Return true if there are exactly NUSES uses of the indicated value.
 805   /// This method ignores uses of other values defined by this operation.
 806   bool hasNUsesOfValue(unsigned NUses, unsigned Value) const;
 807
 808   /// Return true if there are any use of the indicated value.
 809   /// This method ignores uses of other values defined by this operation.
 810   bool hasAnyUseOfValue(unsigned Value) const;
 811
 812   /// Return true if this node is the only use of N.
 813   bool isOnlyUserOf(const SDNode *N) const;
 814
 815   /// Return true if this node is an operand of N.
 816   bool isOperandOf(const SDNode *N) const;
 817
 818   /// Return true if this node is a predecessor of N.
 819   /// NOTE: Implemented on top of hasPredecessor and every bit as
 820   /// expensive. Use carefully.
 821   bool isPredecessorOf(const SDNode *N) const {
 822     return N->hasPredecessor(this);
 823   }
 824
 825   /// Return true if N is a predecessor of this node.
 826   /// N is either an operand of this node, or can be reached by recursively
 827   /// traversing up the operands.
 828   /// NOTE: This is an expensive method. Use it carefully.
 829   bool hasPredecessor(const SDNode *N) const;
 830
 831   /// Returns true if N is a predecessor of any node in Worklist. This
 832   /// helper keeps Visited and Worklist sets externally to allow unions
 833   /// searches to be performed in parallel, caching of results across
 834   /// queries and incremental addition to Worklist. Stops early if N is
 835   /// found but will resume. Remember to clear Visited and Worklists
 836   /// if DAG changes. MaxSteps gives a maximum number of nodes to visit before
 837   /// giving up. The TopologicalPrune flag signals that positive NodeIds are
 838   /// topologically ordered (Operands have strictly smaller node id) and search
 839   /// can be pruned leveraging this.
 840   static bool hasPredecessorHelper(const SDNode *N,
 841                                    SmallPtrSetImpl<const SDNode *> &Visited,
 842                                    SmallVectorImpl<const SDNode *> &Worklist,
 843                                    unsigned int MaxSteps = 0,
 844                                    bool TopologicalPrune = false) {
 845     SmallVector<const SDNode *, 8> DeferredNodes;
 846     if (Visited.count(N))
 847       return true;
 848
 849     // Node Id's are assigned in three places: As a topological
 850     // ordering (> 0), during legalization (results in values set to
 851     // 0), new nodes (set to -1). If N has a topolgical id then we
 852     // know that all nodes with ids smaller than it cannot be
 853     // successors and we need not check them. Filter out all node
 854     // that can't be matches. We add them to the worklist before exit
 855     // in case of multiple calls. Note that during selection the topological id
 856     // may be violated if a node's predecessor is selected before it. We mark
 857     // this at selection negating the id of unselected successors and
 858     // restricting topological pruning to positive ids.
 859
 860     int NId = N->getNodeId();
 861     // If we Invalidated the Id, reconstruct original NId.
 862     if (NId < -1)
 863       NId = -(NId + 1);
 864
 865     bool Found = false;
 866     while (!Worklist.empty()) {
 867       const SDNode *M = Worklist.pop_back_val();
 868       int MId = M->getNodeId();
 869       if (TopologicalPrune && M->getOpcode() != ISD::TokenFactor && (NId > 0) &&
 870           (MId > 0) && (MId < NId)) {
 871         DeferredNodes.push_back(M);
 872         continue;
 873       }
 874       for (const SDValue &OpV : M->op_values()) {
 875         SDNode *Op = OpV.getNode();
 876         if (Visited.insert(Op).second)
 877           Worklist.push_back(Op);
 878         if (Op == N)
 879           Found = true;
 880       }
 881       if (Found)
 882         break;
 883       if (MaxSteps != 0 && Visited.size() >= MaxSteps)
 884         break;
 885     }
 886     // Push deferred nodes back on worklist.
 887     Worklist.append(DeferredNodes.begin(), DeferredNodes.end());
 888     // If we bailed early, conservatively return found.
 889     if (MaxSteps != 0 && Visited.size() >= MaxSteps)
 890       return true;
 891     return Found;
 892   }
 893
 894   /// Return true if all the users of N are contained in Nodes.
 895   /// NOTE: Requires at least one match, but doesn't require them all.
 896   static bool areOnlyUsersOf(ArrayRef<const SDNode *> Nodes, const SDNode *N);
 897
 898   /// Return the number of values used by this operation.
 899   unsigned getNumOperands() const { return NumOperands; }
 900
 901   /// Helper method returns the integer value of a ConstantSDNode operand.
 902   inline uint64_t getConstantOperandVal(unsigned Num) const;
 903
 904   const SDValue &getOperand(unsigned Num) const {
 905     assert(Num < NumOperands && "Invalid child # of SDNode!");
 906     return OperandList[Num];
 907   }
 908
 909   using op_iterator = SDUse *;
 910
 911   op_iterator op_begin() const { return OperandList; }
 912   op_iterator op_end() const { return OperandList+NumOperands; }
 913   ArrayRef<SDUse> ops() const { return makeArrayRef(op_begin(), op_end()); }
 914
 915   /// Iterator for directly iterating over the operand SDValue's.
 916   struct value_op_iterator
 917       : iterator_adaptor_base<value_op_iterator, op_iterator,
 918                               std::random_access_iterator_tag, SDValue,
 919                               ptrdiff_t, value_op_iterator *,
 920                               value_op_iterator *> {
 921     explicit value_op_iterator(SDUse *U = nullptr)
 922       : iterator_adaptor_base(U) {}
 923
 924     const SDValue &operator*() const { return I->get(); }
 925   };
 926
 927   iterator_range<value_op_iterator> op_values() const {
 928     return make_range(value_op_iterator(op_begin()),
 929                       value_op_iterator(op_end()));
 930   }
 931
 932   SDVTList getVTList() const {
 933     SDVTList X = { ValueList, NumValues };
 934     return X;
 935   }
 936
 937   /// If this node has a glue operand, return the node
 938   /// to which the glue operand points. Otherwise return NULL.
 939   SDNode *getGluedNode() const {
 940     if (getNumOperands() != 0 &&
 941         getOperand(getNumOperands()-1).getValueType() == MVT::Glue)
 942       return getOperand(getNumOperands()-1).getNode();
 943     return nullptr;
 944   }
 945
 946   /// If this node has a glue value with a user, return
 947   /// the user (there is at most one). Otherwise return NULL.
 948   SDNode *getGluedUser() const {
 949     for (use_iterator UI = use_begin(), UE = use_end(); UI != UE; ++UI)
 950       if (UI.getUse().get().getValueType() == MVT::Glue)
 951         return *UI;
 952     return nullptr;
 953   }
 954
 955   const SDNodeFlags getFlags() const { return Flags; }
 956   void setFlags(SDNodeFlags NewFlags) { Flags = NewFlags; }
 957   bool isFast() { return Flags.isFast(); }
 958
 959   /// Clear any flags in this node that aren't also set in Flags.
 960   /// If Flags is not in a defined state then this has no effect.
 961   void intersectFlagsWith(const SDNodeFlags Flags);
 962
 963   /// Return the number of values defined/returned by this operator.
 964   unsigned getNumValues() const { return NumValues; }
 965
 966   /// Return the type of a specified result.
 967   EVT getValueType(unsigned ResNo) const {
 968     assert(ResNo < NumValues && "Illegal result number!");
 969     return ValueList[ResNo];
 970   }
 971
 972   /// Return the type of a specified result as a simple type.
 973   MVT getSimpleValueType(unsigned ResNo) const {
 974     return getValueType(ResNo).getSimpleVT();
 975   }
 976
 977   /// Returns MVT::getSizeInBits(getValueType(ResNo)).
 978   unsigned getValueSizeInBits(unsigned ResNo) const {
 979     return getValueType(ResNo).getSizeInBits();
 980   }
 981
 982   using value_iterator = const EVT *;
 983
 984   value_iterator value_begin() const { return ValueList; }
 985   value_iterator value_end() const { return ValueList+NumValues; }
 986
 987   /// Return the opcode of this operation for printing.
 988   std::string getOperationName(const SelectionDAG *G = nullptr) const;
 989   static const char* getIndexedModeName(ISD::MemIndexedMode AM);
 990   void print_types(raw_ostream &OS, const SelectionDAG *G) const;
 991   void print_details(raw_ostream &OS, const SelectionDAG *G) const;
 992   void print(raw_ostream &OS, const SelectionDAG *G = nullptr) const;
 993   void printr(raw_ostream &OS, const SelectionDAG *G = nullptr) const;
 994
 995   /// Print a SelectionDAG node and all children down to
 996   /// the leaves.  The given SelectionDAG allows target-specific nodes
 997   /// to be printed in human-readable form.  Unlike printr, this will
 998   /// print the whole DAG, including children that appear multiple
 999   /// times.
1000   ///
1001   void printrFull(raw_ostream &O, const SelectionDAG *G = nullptr) const;
1002
1003   /// Print a SelectionDAG node and children up to
1004   /// depth "depth."  The given SelectionDAG allows target-specific
1005   /// nodes to be printed in human-readable form.  Unlike printr, this
1006   /// will print children that appear multiple times wherever they are
1007   /// used.
1008   ///
1009   void printrWithDepth(raw_ostream &O, const SelectionDAG *G = nullptr,
1010                        unsigned depth = 100) const;
1011
1012   /// Dump this node, for debugging.
1013   void dump() const;
1014
1015   /// Dump (recursively) this node and its use-def subgraph.
1016   void dumpr() const;
1017
1018   /// Dump this node, for debugging.
1019   /// The given SelectionDAG allows target-specific nodes to be printed
1020   /// in human-readable form.
1021   void dump(const SelectionDAG *G) const;
1022
1023   /// Dump (recursively) this node and its use-def subgraph.
1024   /// The given SelectionDAG allows target-specific nodes to be printed
1025   /// in human-readable form.
1026   void dumpr(const SelectionDAG *G) const;
1027
1028   /// printrFull to dbgs().  The given SelectionDAG allows
1029   /// target-specific nodes to be printed in human-readable form.
1030   /// Unlike dumpr, this will print the whole DAG, including children
1031   /// that appear multiple times.
1032   void dumprFull(const SelectionDAG *G = nullptr) const;
1033
1034   /// printrWithDepth to dbgs().  The given
1035   /// SelectionDAG allows target-specific nodes to be printed in
1036   /// human-readable form.  Unlike dumpr, this will print children
1037   /// that appear multiple times wherever they are used.
1038   ///
1039   void dumprWithDepth(const SelectionDAG *G = nullptr,
1040                       unsigned depth = 100) const;
1041
1042   /// Gather unique data for the node.
1043   void Profile(FoldingSetNodeID &ID) const;
1044
1045   /// This method should only be used by the SDUse class.
1046   void addUse(SDUse &U) { U.addToList(&UseList); }
1047
1048 protected:
1049   static SDVTList getSDVTList(EVT VT) {
1050     SDVTList Ret = { getValueTypeList(VT), 1 };
1051     return Ret;
1052   }
1053
1054   /// Create an SDNode.
1055   ///
1056   /// SDNodes are created without any operands, and never own the operand
1057   /// storage. To add operands, see SelectionDAG::createOperands.
1058   SDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs)
1059       : NodeType(Opc), ValueList(VTs.VTs), NumValues(VTs.NumVTs),
1060         IROrder(Order), debugLoc(std::move(dl)) {
1061     memset(&RawSDNodeBits, 0, sizeof(RawSDNodeBits));
1062     assert(debugLoc.hasTrivialDestructor() && "Expected trivial destructor");
1063     assert(NumValues == VTs.NumVTs &&
1064            "NumValues wasn't wide enough for its operands!");
1065   }
1066
1067   /// Release the operands and set this node to have zero operands.
1068   void DropOperands();
1069 };
1070
1071 /// Wrapper class for IR location info (IR ordering and DebugLoc) to be passed
1072 /// into SDNode creation functions.
1073 /// When an SDNode is created from the DAGBuilder, the DebugLoc is extracted
1074 /// from the original Instruction, and IROrder is the ordinal position of
1075 /// the instruction.
1076 /// When an SDNode is created after the DAG is being built, both DebugLoc and
1077 /// the IROrder are propagated from the original SDNode.
1078 /// So SDLoc class provides two constructors besides the default one, one to
1079 /// be used by the DAGBuilder, the other to be used by others.
1080 class SDLoc {
1081 private:
1082   DebugLoc DL;
1083   int IROrder = 0;
1084
1085 public:
1086   SDLoc() = default;
1087   SDLoc(const SDNode *N) : DL(N->getDebugLoc()), IROrder(N->getIROrder()) {}
1088   SDLoc(const SDValue V) : SDLoc(V.getNode()) {}
1089   SDLoc(const Instruction *I, int Order) : IROrder(Order) {
1090     assert(Order >= 0 && "bad IROrder");
1091     if (I)
1092       DL = I->getDebugLoc();
1093   }
1094
1095   unsigned getIROrder() const { return IROrder; }
1096   const DebugLoc &getDebugLoc() const { return DL; }
1097 };
1098
1099 // Define inline functions from the SDValue class.
1100
1101 inline SDValue::SDValue(SDNode *node, unsigned resno)
1102     : Node(node), ResNo(resno) {
1103   // Explicitly check for !ResNo to avoid use-after-free, because there are
1104   // callers that use SDValue(N, 0) with a deleted N to indicate successful
1105   // combines.
1106   assert((!Node || !ResNo || ResNo < Node->getNumValues()) &&
1107          "Invalid result number for the given node!");
1108   assert(ResNo < -2U && "Cannot use result numbers reserved for DenseMaps.");
1109 }
1110
1111 inline unsigned SDValue::getOpcode() const {
1112   return Node->getOpcode();
1113 }
1114
1115 inline EVT SDValue::getValueType() const {
1116   return Node->getValueType(ResNo);
1117 }
1118
1119 inline unsigned SDValue::getNumOperands() const {
1120   return Node->getNumOperands();
1121 }
1122
1123 inline const SDValue &SDValue::getOperand(unsigned i) const {
1124   return Node->getOperand(i);
1125 }
1126
1127 inline uint64_t SDValue::getConstantOperandVal(unsigned i) const {
1128   return Node->getConstantOperandVal(i);
1129 }
1130
1131 inline bool SDValue::isTargetOpcode() const {
1132   return Node->isTargetOpcode();
1133 }
1134
1135 inline bool SDValue::isTargetMemoryOpcode() const {
1136   return Node->isTargetMemoryOpcode();
1137 }
1138
1139 inline bool SDValue::isMachineOpcode() const {
1140   return Node->isMachineOpcode();
1141 }
1142
1143 inline unsigned SDValue::getMachineOpcode() const {
1144   return Node->getMachineOpcode();
1145 }
1146
1147 inline bool SDValue::isUndef() const {
1148   return Node->isUndef();
1149 }
1150
1151 inline bool SDValue::use_empty() const {
1152   return !Node->hasAnyUseOfValue(ResNo);
1153 }
1154
1155 inline bool SDValue::hasOneUse() const {
1156   return Node->hasNUsesOfValue(1, ResNo);
1157 }
1158
1159 inline const DebugLoc &SDValue::getDebugLoc() const {
1160   return Node->getDebugLoc();
1161 }
1162
1163 inline void SDValue::dump() const {
1164   return Node->dump();
1165 }
1166
1167 inline void SDValue::dump(const SelectionDAG *G) const {
1168   return Node->dump(G);
1169 }
1170
1171 inline void SDValue::dumpr() const {
1172   return Node->dumpr();
1173 }
1174
1175 inline void SDValue::dumpr(const SelectionDAG *G) const {
1176   return Node->dumpr(G);
1177 }
1178
1179 // Define inline functions from the SDUse class.
1180
1181 inline void SDUse::set(const SDValue &V) {
1182   if (Val.getNode()) removeFromList();
1183   Val = V;
1184   if (V.getNode()) V.getNode()->addUse(*this);
1185 }
1186
1187 inline void SDUse::setInitial(const SDValue &V) {
1188   Val = V;
1189   V.getNode()->addUse(*this);
1190 }
1191
1192 inline void SDUse::setNode(SDNode *N) {
1193   if (Val.getNode()) removeFromList();
1194   Val.setNode(N);
1195   if (N) N->addUse(*this);
1196 }
1197
1198 /// This class is used to form a handle around another node that
1199 /// is persistent and is updated across invocations of replaceAllUsesWith on its
1200 /// operand.  This node should be directly created by end-users and not added to
1201 /// the AllNodes list.
1202 class HandleSDNode : public SDNode {
1203   SDUse Op;
1204
1205 public:
1206   explicit HandleSDNode(SDValue X)
1207     : SDNode(ISD::HANDLENODE, 0, DebugLoc(), getSDVTList(MVT::Other)) {
1208     // HandleSDNodes are never inserted into the DAG, so they won't be
1209     // auto-numbered. Use ID 65535 as a sentinel.
1210     PersistentId = 0xffff;
1211
1212     // Manually set up the operand list. This node type is special in that it's
1213     // always stack allocated and SelectionDAG does not manage its operands.
1214     // TODO: This should either (a) not be in the SDNode hierarchy, or (b) not
1215     // be so special.
1216     Op.setUser(this);
1217     Op.setInitial(X);
1218     NumOperands = 1;
1219     OperandList = &Op;
1220   }
1221   ~HandleSDNode();
1222
1223   const SDValue &getValue() const { return Op; }
1224 };
1225
1226 class AddrSpaceCastSDNode : public SDNode {
1227 private:
1228   unsigned SrcAddrSpace;
1229   unsigned DestAddrSpace;
1230
1231 public:
1232   AddrSpaceCastSDNode(unsigned Order, const DebugLoc &dl, EVT VT,
1233                       unsigned SrcAS, unsigned DestAS);
1234
1235   unsigned getSrcAddressSpace() const { return SrcAddrSpace; }
1236   unsigned getDestAddressSpace() const { return DestAddrSpace; }
1237
1238   static bool classof(const SDNode *N) {
1239     return N->getOpcode() == ISD::ADDRSPACECAST;
1240   }
1241 };
1242
1243 /// This is an abstract virtual class for memory operations.
1244 class MemSDNode : public SDNode {
1245 private:
1246   // VT of in-memory value.
1247   EVT MemoryVT;
1248
1249 protected:
1250   /// Memory reference information.
1251   MachineMemOperand *MMO;
1252
1253 public:
1254   MemSDNode(unsigned Opc, unsigned Order, const DebugLoc &dl, SDVTList VTs,
1255             EVT memvt, MachineMemOperand *MMO);
1256
1257   bool readMem() const { return MMO->isLoad(); }
1258   bool writeMem() const { return MMO->isStore(); }
1259
1260   /// Returns alignment and volatility of the memory access
1261   unsigned getOriginalAlignment() const {
1262     return MMO->getBaseAlignment();
1263   }
1264   unsigned getAlignment() const {
1265     return MMO->getAlignment();
1266   }
1267
1268   /// Return the SubclassData value, without HasDebugValue. This contains an
1269   /// encoding of the volatile flag, as well as bits used by subclasses. This
1270   /// function should only be used to compute a FoldingSetNodeID value.
1271   /// The HasDebugValue bit is masked out because CSE map needs to match
1272   /// nodes with debug info with nodes without debug info. Same is about
1273   /// isDivergent bit.
1274   unsigned getRawSubclassData() const {
1275     uint16_t Data;
1276     union {
1277       char RawSDNodeBits[sizeof(uint16_t)];
1278       SDNodeBitfields SDNodeBits;
1279     };
1280     memcpy(&RawSDNodeBits, &this->RawSDNodeBits, sizeof(this->RawSDNodeBits));
1281     SDNodeBits.HasDebugValue = 0;
1282     SDNodeBits.IsDivergent = false;
1283     memcpy(&Data, &RawSDNodeBits, sizeof(RawSDNodeBits));
1284     return Data;
1285   }
1286
1287   bool isVolatile() const { return MemSDNodeBits.IsVolatile; }
1288   bool isNonTemporal() const { return MemSDNodeBits.IsNonTemporal; }
1289   bool isDereferenceable() const { return MemSDNodeBits.IsDereferenceable; }
1290   bool isInvariant() const { return MemSDNodeBits.IsInvariant; }
1291
1292   // Returns the offset from the location of the access.
1293   int64_t getSrcValueOffset() const { return MMO->getOffset(); }
1294
1295   /// Returns the AA info that describes the dereference.
1296   AAMDNodes getAAInfo() const { return MMO->getAAInfo(); }
1297
1298   /// Returns the Ranges that describes the dereference.
1299   const MDNode *getRanges() const { return MMO->getRanges(); }
1300
1301   /// Returns the synchronization scope ID for this memory operation.
1302   SyncScope::ID getSyncScopeID() const { return MMO->getSyncScopeID(); }
1303
1304   /// Return the atomic ordering requirements for this memory operation. For
1305   /// cmpxchg atomic operations, return the atomic ordering requirements when
1306   /// store occurs.
1307   AtomicOrdering getOrdering() const { return MMO->getOrdering(); }
1308
1309   /// Return the type of the in-memory value.
1310   EVT getMemoryVT() const { return MemoryVT; }
1311
1312   /// Return a MachineMemOperand object describing the memory
1313   /// reference performed by operation.
1314   MachineMemOperand *getMemOperand() const { return MMO; }
1315
1316   const MachinePointerInfo &getPointerInfo() const {
1317     return MMO->getPointerInfo();
1318   }
1319
1320   /// Return the address space for the associated pointer
1321   unsigned getAddressSpace() const {
1322     return getPointerInfo().getAddrSpace();
1323   }
1324
1325   /// Update this MemSDNode's MachineMemOperand information
1326   /// to reflect the alignment of NewMMO, if it has a greater alignment.
1327   /// This must only be used when the new alignment applies to all users of
1328   /// this MachineMemOperand.
1329   void refineAlignment(const MachineMemOperand *NewMMO) {
1330     MMO->refineAlignment(NewMMO);
1331   }
1332
1333   const SDValue &getChain() const { return getOperand(0); }
1334   const SDValue &getBasePtr() const {
1335     return getOperand(getOpcode() == ISD::STORE ? 2 : 1);
1336   }
1337
1338   // Methods to support isa and dyn_cast
1339   static bool classof(const SDNode *N) {
1340     // For some targets, we lower some target intrinsics to a MemIntrinsicNode
1341     // with either an intrinsic or a target opcode.
1342     return N->getOpcode() == ISD::LOAD                ||
1343            N->getOpcode() == ISD::STORE               ||
1344            N->getOpcode() == ISD::PREFETCH            ||
1345            N->getOpcode() == ISD::ATOMIC_CMP_SWAP     ||
1346            N->getOpcode() == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS ||
1347            N->getOpcode() == ISD::ATOMIC_SWAP         ||
1348            N->getOpcode() == ISD::ATOMIC_LOAD_ADD     ||
1349            N->getOpcode() == ISD::ATOMIC_LOAD_SUB     ||
1350            N->getOpcode() == ISD::ATOMIC_LOAD_AND     ||
1351            N->getOpcode() == ISD::ATOMIC_LOAD_CLR     ||
1352            N->getOpcode() == ISD::ATOMIC_LOAD_OR      ||
1353            N->getOpcode() == ISD::ATOMIC_LOAD_XOR     ||
1354            N->getOpcode() == ISD::ATOMIC_LOAD_NAND    ||
1355            N->getOpcode() == ISD::ATOMIC_LOAD_MIN     ||
1356            N->getOpcode() == ISD::ATOMIC_LOAD_MAX     ||
1357            N->getOpcode() == ISD::ATOMIC_LOAD_UMIN    ||
1358            N->getOpcode() == ISD::ATOMIC_LOAD_UMAX    ||
1359            N->getOpcode() == ISD::ATOMIC_LOAD         ||
1360            N->getOpcode() == ISD::ATOMIC_STORE        ||
1361            N->getOpcode() == ISD::MLOAD               ||
1362            N->getOpcode() == ISD::MSTORE              ||
1363            N->getOpcode() == ISD::MGATHER             ||
1364            N->getOpcode() == ISD::MSCATTER            ||
1365            N->isMemIntrinsic()                        ||
1366            N->isTargetMemoryOpcode();
1367   }
1368 };
1369
1370 /// This is an SDNode representing atomic operations.
1371 class AtomicSDNode : public MemSDNode {
1372 public:
1373   AtomicSDNode(unsigned Opc, unsigned Order, const DebugLoc &dl, SDVTList VTL,
1374                EVT MemVT, MachineMemOperand *MMO)
1375       : MemSDNode(Opc, Order, dl, VTL, MemVT, MMO) {}
1376
1377   const SDValue &getBasePtr() const { return getOperand(1); }
1378   const SDValue &getVal() const { return getOperand(2); }
1379
1380   /// Returns true if this SDNode represents cmpxchg atomic operation, false
1381   /// otherwise.
1382   bool isCompareAndSwap() const {
1383     unsigned Op = getOpcode();
1384     return Op == ISD::ATOMIC_CMP_SWAP ||
1385            Op == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS;
1386   }
1387
1388   /// For cmpxchg atomic operations, return the atomic ordering requirements
1389   /// when store does not occur.
1390   AtomicOrdering getFailureOrdering() const {
1391     assert(isCompareAndSwap() && "Must be cmpxchg operation");
1392     return MMO->getFailureOrdering();
1393   }
1394
1395   // Methods to support isa and dyn_cast
1396   static bool classof(const SDNode *N) {
1397     return N->getOpcode() == ISD::ATOMIC_CMP_SWAP     ||
1398            N->getOpcode() == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS ||
1399            N->getOpcode() == ISD::ATOMIC_SWAP         ||
1400            N->getOpcode() == ISD::ATOMIC_LOAD_ADD     ||
1401            N->getOpcode() == ISD::ATOMIC_LOAD_SUB     ||
1402            N->getOpcode() == ISD::ATOMIC_LOAD_AND     ||
1403            N->getOpcode() == ISD::ATOMIC_LOAD_CLR     ||
1404            N->getOpcode() == ISD::ATOMIC_LOAD_OR      ||
1405            N->getOpcode() == ISD::ATOMIC_LOAD_XOR     ||
1406            N->getOpcode() == ISD::ATOMIC_LOAD_NAND    ||
1407            N->getOpcode() == ISD::ATOMIC_LOAD_MIN     ||
1408            N->getOpcode() == ISD::ATOMIC_LOAD_MAX     ||
1409            N->getOpcode() == ISD::ATOMIC_LOAD_UMIN    ||
1410            N->getOpcode() == ISD::ATOMIC_LOAD_UMAX    ||
1411            N->getOpcode() == ISD::ATOMIC_LOAD         ||
1412            N->getOpcode() == ISD::ATOMIC_STORE;
1413   }
1414 };
1415
1416 /// This SDNode is used for target intrinsics that touch
1417 /// memory and need an associated MachineMemOperand. Its opcode may be
1418 /// INTRINSIC_VOID, INTRINSIC_W_CHAIN, PREFETCH, or a target-specific opcode
1419 /// with a value not less than FIRST_TARGET_MEMORY_OPCODE.
1420 class MemIntrinsicSDNode : public MemSDNode {
1421 public:
1422   MemIntrinsicSDNode(unsigned Opc, unsigned Order, const DebugLoc &dl,
1423                      SDVTList VTs, EVT MemoryVT, MachineMemOperand *MMO)
1424       : MemSDNode(Opc, Order, dl, VTs, MemoryVT, MMO) {
1425     SDNodeBits.IsMemIntrinsic = true;
1426   }
1427
1428   // Methods to support isa and dyn_cast
1429   static bool classof(const SDNode *N) {
1430     // We lower some target intrinsics to their target opcode
1431     // early a node with a target opcode can be of this class
1432     return N->isMemIntrinsic()             ||
1433            N->getOpcode() == ISD::PREFETCH ||
1434            N->isTargetMemoryOpcode();
1435   }
1436 };
1437
1438 /// This SDNode is used to implement the code generator
1439 /// support for the llvm IR shufflevector instruction.  It combines elements
1440 /// from two input vectors into a new input vector, with the selection and
1441 /// ordering of elements determined by an array of integers, referred to as
1442 /// the shuffle mask.  For input vectors of width N, mask indices of 0..N-1
1443 /// refer to elements from the LHS input, and indices from N to 2N-1 the RHS.
1444 /// An index of -1 is treated as undef, such that the code generator may put
1445 /// any value in the corresponding element of the result.
1446 class ShuffleVectorSDNode : public SDNode {
1447   // The memory for Mask is owned by the SelectionDAG's OperandAllocator, and
1448   // is freed when the SelectionDAG object is destroyed.
1449   const int *Mask;
1450
1451 protected:
1452   friend class SelectionDAG;
1453
1454   ShuffleVectorSDNode(EVT VT, unsigned Order, const DebugLoc &dl, const int *M)
1455       : SDNode(ISD::VECTOR_SHUFFLE, Order, dl, getSDVTList(VT)), Mask(M) {}
1456
1457 public:
1458   ArrayRef<int> getMask() const {
1459     EVT VT = getValueType(0);
1460     return makeArrayRef(Mask, VT.getVectorNumElements());
1461   }
1462
1463   int getMaskElt(unsigned Idx) const {
1464     assert(Idx < getValueType(0).getVectorNumElements() && "Idx out of range!");
1465     return Mask[Idx];
1466   }
1467
1468   bool isSplat() const { return isSplatMask(Mask, getValueType(0)); }
1469
1470   int  getSplatIndex() const {
1471     assert(isSplat() && "Cannot get splat index for non-splat!");
1472     EVT VT = getValueType(0);
1473     for (unsigned i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
1474       if (Mask[i] >= 0)
1475         return Mask[i];
1476     }
1477     llvm_unreachable("Splat with all undef indices?");
1478   }
1479
1480   static bool isSplatMask(const int *Mask, EVT VT);
1481
1482   /// Change values in a shuffle permute mask assuming
1483   /// the two vector operands have swapped position.
1484   static void commuteMask(MutableArrayRef<int> Mask) {
1485     unsigned NumElems = Mask.size();
1486     for (unsigned i = 0; i != NumElems; ++i) {
1487       int idx = Mask[i];
1488       if (idx < 0)
1489         continue;
1490       else if (idx < (int)NumElems)
1491         Mask[i] = idx + NumElems;
1492       else
1493         Mask[i] = idx - NumElems;
1494     }
1495   }
1496
1497   static bool classof(const SDNode *N) {
1498     return N->getOpcode() == ISD::VECTOR_SHUFFLE;
1499   }
1500 };
1501
1502 class ConstantSDNode : public SDNode {
1503   friend class SelectionDAG;
1504
1505   const ConstantInt *Value;
1506
1507   ConstantSDNode(bool isTarget, bool isOpaque, const ConstantInt *val, EVT VT)
1508       : SDNode(isTarget ? ISD::TargetConstant : ISD::Constant, 0, DebugLoc(),
1509                getSDVTList(VT)),
1510         Value(val) {
1511     ConstantSDNodeBits.IsOpaque = isOpaque;
1512   }
1513
1514 public:
1515   const ConstantInt *getConstantIntValue() const { return Value; }
1516   const APInt &getAPIntValue() const { return Value->getValue(); }
1517   uint64_t getZExtValue() const { return Value->getZExtValue(); }
1518   int64_t getSExtValue() const { return Value->getSExtValue(); }
1519   uint64_t getLimitedValue(uint64_t Limit = UINT64_MAX) {
1520     return Value->getLimitedValue(Limit);
1521   }
1522
1523   bool isOne() const { return Value->isOne(); }
1524   bool isNullValue() const { return Value->isZero(); }
1525   bool isAllOnesValue() const { return Value->isMinusOne(); }
1526
1527   bool isOpaque() const { return ConstantSDNodeBits.IsOpaque; }
1528
1529   static bool classof(const SDNode *N) {
1530     return N->getOpcode() == ISD::Constant ||
1531            N->getOpcode() == ISD::TargetConstant;
1532   }
1533 };
1534
1535 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
1536   return cast<ConstantSDNode>(getOperand(Num))->getZExtValue();
1537 }
1538
1539 class ConstantFPSDNode : public SDNode {
1540   friend class SelectionDAG;
1541
1542   const ConstantFP *Value;
1543
1544   ConstantFPSDNode(bool isTarget, const ConstantFP *val, EVT VT)
1545       : SDNode(isTarget ? ISD::TargetConstantFP : ISD::ConstantFP, 0,
1546                DebugLoc(), getSDVTList(VT)),
1547         Value(val) {}
1548
1549 public:
1550   const APFloat& getValueAPF() const { return Value->getValueAPF(); }
1551   const ConstantFP *getConstantFPValue() const { return Value; }
1552
1553   /// Return true if the value is positive or negative zero.
1554   bool isZero() const { return Value->isZero(); }
1555
1556   /// Return true if the value is a NaN.
1557   bool isNaN() const { return Value->isNaN(); }
1558
1559   /// Return true if the value is an infinity
1560   bool isInfinity() const { return Value->isInfinity(); }
1561
1562   /// Return true if the value is negative.
1563   bool isNegative() const { return Value->isNegative(); }
1564
1565   /// We don't rely on operator== working on double values, as
1566   /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
1567   /// As such, this method can be used to do an exact bit-for-bit comparison of
1568   /// two floating point values.
1569
1570   /// We leave the version with the double argument here because it's just so
1571   /// convenient to write "2.0" and the like.  Without this function we'd
1572   /// have to duplicate its logic everywhere it's called.
1573   bool isExactlyValue(double V) const {
1574     return Value->getValueAPF().isExactlyValue(V);
1575   }
1576   bool isExactlyValue(const APFloat& V) const;
1577
1578   static bool isValueValidForType(EVT VT, const APFloat& Val);
1579
1580   static bool classof(const SDNode *N) {
1581     return N->getOpcode() == ISD::ConstantFP ||
1582            N->getOpcode() == ISD::TargetConstantFP;
1583   }
1584 };
1585
1586 /// Returns true if \p V is a constant integer zero.
1587 bool isNullConstant(SDValue V);
1588
1589 /// Returns true if \p V is an FP constant with a value of positive zero.
1590 bool isNullFPConstant(SDValue V);
1591
1592 /// Returns true if \p V is an integer constant with all bits set.
1593 bool isAllOnesConstant(SDValue V);
1594
1595 /// Returns true if \p V is a constant integer one.
1596 bool isOneConstant(SDValue V);
1597
1598 /// Return the non-bitcasted source operand of \p V if it exists.
1599 /// If \p V is not a bitcasted value, it is returned as-is.
1600 SDValue peekThroughBitcasts(SDValue V);
1601
1602 /// Return the non-bitcasted and one-use source operand of \p V if it exists.
1603 /// If \p V is not a bitcasted one-use value, it is returned as-is.
1604 SDValue peekThroughOneUseBitcasts(SDValue V);
1605
1606 /// Returns true if \p V is a bitwise not operation. Assumes that an all ones
1607 /// constant is canonicalized to be operand 1.
1608 bool isBitwiseNot(SDValue V);
1609
1610 /// Returns the SDNode if it is a constant splat BuildVector or constant int.
1611 ConstantSDNode *isConstOrConstSplat(SDValue N, bool AllowUndefs = false);
1612
1613 /// Returns the SDNode if it is a constant splat BuildVector or constant float.
1614 ConstantFPSDNode *isConstOrConstSplatFP(SDValue N, bool AllowUndefs = false);
1615
1616 /// Return true if the value is a constant 0 integer or a splatted vector of
1617 /// a constant 0 integer (with no undefs).
1618 /// Build vector implicit truncation is not an issue for null values.
1619 bool isNullOrNullSplat(SDValue V);
1620
1621 /// Return true if the value is a constant 1 integer or a splatted vector of a
1622 /// constant 1 integer (with no undefs).
1623 /// Does not permit build vector implicit truncation.
1624 bool isOneOrOneSplat(SDValue V);
1625
1626 /// Return true if the value is a constant -1 integer or a splatted vector of a
1627 /// constant -1 integer (with no undefs).
1628 /// Does not permit build vector implicit truncation.
1629 bool isAllOnesOrAllOnesSplat(SDValue V);
1630
1631 class GlobalAddressSDNode : public SDNode {
1632   friend class SelectionDAG;
1633
1634   const GlobalValue *TheGlobal;
1635   int64_t Offset;
1636   unsigned char TargetFlags;
1637
1638   GlobalAddressSDNode(unsigned Opc, unsigned Order, const DebugLoc &DL,
1639                       const GlobalValue *GA, EVT VT, int64_t o,
1640                       unsigned char TF);
1641
1642 public:
1643   const GlobalValue *getGlobal() const { return TheGlobal; }
1644   int64_t getOffset() const { return Offset; }
1645   unsigned char getTargetFlags() const { return TargetFlags; }
1646   // Return the address space this GlobalAddress belongs to.
1647   unsigned getAddressSpace() const;
1648
1649   static bool classof(const SDNode *N) {
1650     return N->getOpcode() == ISD::GlobalAddress ||
1651            N->getOpcode() == ISD::TargetGlobalAddress ||
1652            N->getOpcode() == ISD::GlobalTLSAddress ||
1653            N->getOpcode() == ISD::TargetGlobalTLSAddress;
1654   }
1655 };
1656
1657 class FrameIndexSDNode : public SDNode {
1658   friend class SelectionDAG;
1659
1660   int FI;
1661
1662   FrameIndexSDNode(int fi, EVT VT, bool isTarg)
1663     : SDNode(isTarg ? ISD::TargetFrameIndex : ISD::FrameIndex,
1664       0, DebugLoc(), getSDVTList(VT)), FI(fi) {
1665   }
1666
1667 public:
1668   int getIndex() const { return FI; }
1669
1670   static bool classof(const SDNode *N) {
1671     return N->getOpcode() == ISD::FrameIndex ||
1672            N->getOpcode() == ISD::TargetFrameIndex;
1673   }
1674 };
1675
1676 class JumpTableSDNode : public SDNode {
1677   friend class SelectionDAG;
1678
1679   int JTI;
1680   unsigned char TargetFlags;
1681
1682   JumpTableSDNode(int jti, EVT VT, bool isTarg, unsigned char TF)
1683     : SDNode(isTarg ? ISD::TargetJumpTable : ISD::JumpTable,
1684       0, DebugLoc(), getSDVTList(VT)), JTI(jti), TargetFlags(TF) {
1685   }
1686
1687 public:
1688   int getIndex() const { return JTI; }
1689   unsigned char getTargetFlags() const { return TargetFlags; }
1690
1691   static bool classof(const SDNode *N) {
1692     return N->getOpcode() == ISD::JumpTable ||
1693            N->getOpcode() == ISD::TargetJumpTable;
1694   }
1695 };
1696
1697 class ConstantPoolSDNode : public SDNode {
1698   friend class SelectionDAG;
1699
1700   union {
1701     const Constant *ConstVal;
1702     MachineConstantPoolValue *MachineCPVal;
1703   } Val;
1704   int Offset;  // It's a MachineConstantPoolValue if top bit is set.
1705   unsigned Alignment;  // Minimum alignment requirement of CP (not log2 value).
1706   unsigned char TargetFlags;
1707
1708   ConstantPoolSDNode(bool isTarget, const Constant *c, EVT VT, int o,
1709                      unsigned Align, unsigned char TF)
1710     : SDNode(isTarget ? ISD::TargetConstantPool : ISD::ConstantPool, 0,
1711              DebugLoc(), getSDVTList(VT)), Offset(o), Alignment(Align),
1712              TargetFlags(TF) {
1713     assert(Offset >= 0 && "Offset is too large");
1714     Val.ConstVal = c;
1715   }
1716
1717   ConstantPoolSDNode(bool isTarget, MachineConstantPoolValue *v,
1718                      EVT VT, int o, unsigned Align, unsigned char TF)
1719     : SDNode(isTarget ? ISD::TargetConstantPool : ISD::ConstantPool, 0,
1720              DebugLoc(), getSDVTList(VT)), Offset(o), Alignment(Align),
1721              TargetFlags(TF) {
1722     assert(Offset >= 0 && "Offset is too large");
1723     Val.MachineCPVal = v;
1724     Offset |= 1 << (sizeof(unsigned)*CHAR_BIT-1);
1725   }
1726
1727 public:
1728   bool isMachineConstantPoolEntry() const {
1729     return Offset < 0;
1730   }
1731
1732   const Constant *getConstVal() const {
1733     assert(!isMachineConstantPoolEntry() && "Wrong constantpool type");
1734     return Val.ConstVal;
1735   }
1736
1737   MachineConstantPoolValue *getMachineCPVal() const {
1738     assert(isMachineConstantPoolEntry() && "Wrong constantpool type");
1739     return Val.MachineCPVal;
1740   }
1741
1742   int getOffset() const {
1743     return Offset & ~(1 << (sizeof(unsigned)*CHAR_BIT-1));
1744   }
1745
1746   // Return the alignment of this constant pool object, which is either 0 (for
1747   // default alignment) or the desired value.
1748   unsigned getAlignment() const { return Alignment; }
1749   unsigned char getTargetFlags() const { return TargetFlags; }
1750
1751   Type *getType() const;
1752
1753   static bool classof(const SDNode *N) {
1754     return N->getOpcode() == ISD::ConstantPool ||
1755            N->getOpcode() == ISD::TargetConstantPool;
1756   }
1757 };
1758
1759 /// Completely target-dependent object reference.
1760 class TargetIndexSDNode : public SDNode {
1761   friend class SelectionDAG;
1762
1763   unsigned char TargetFlags;
1764   int Index;
1765   int64_t Offset;
1766
1767 public:
1768   TargetIndexSDNode(int Idx, EVT VT, int64_t Ofs, unsigned char TF)
1769     : SDNode(ISD::TargetIndex, 0, DebugLoc(), getSDVTList(VT)),
1770       TargetFlags(TF), Index(Idx), Offset(Ofs) {}
1771
1772   unsigned char getTargetFlags() const { return TargetFlags; }
1773   int getIndex() const { return Index; }
1774   int64_t getOffset() const { return Offset; }
1775
1776   static bool classof(const SDNode *N) {
1777     return N->getOpcode() == ISD::TargetIndex;
1778   }
1779 };
1780
1781 class BasicBlockSDNode : public SDNode {
1782   friend class SelectionDAG;
1783
1784   MachineBasicBlock *MBB;
1785
1786   /// Debug info is meaningful and potentially useful here, but we create
1787   /// blocks out of order when they're jumped to, which makes it a bit
1788   /// harder.  Let's see if we need it first.
1789   explicit BasicBlockSDNode(MachineBasicBlock *mbb)
1790     : SDNode(ISD::BasicBlock, 0, DebugLoc(), getSDVTList(MVT::Other)), MBB(mbb)
1791   {}
1792
1793 public:
1794   MachineBasicBlock *getBasicBlock() const { return MBB; }
1795
1796   static bool classof(const SDNode *N) {
1797     return N->getOpcode() == ISD::BasicBlock;
1798   }
1799 };
1800
1801 /// A "pseudo-class" with methods for operating on BUILD_VECTORs.
1802 class BuildVectorSDNode : public SDNode {
1803 public:
1804   // These are constructed as SDNodes and then cast to BuildVectorSDNodes.
1805   explicit BuildVectorSDNode() = delete;
1806
1807   /// Check if this is a constant splat, and if so, find the
1808   /// smallest element size that splats the vector.  If MinSplatBits is
1809   /// nonzero, the element size must be at least that large.  Note that the
1810   /// splat element may be the entire vector (i.e., a one element vector).
1811   /// Returns the splat element value in SplatValue.  Any undefined bits in
1812   /// that value are zero, and the corresponding bits in the SplatUndef mask
1813   /// are set.  The SplatBitSize value is set to the splat element size in
1814   /// bits.  HasAnyUndefs is set to true if any bits in the vector are
1815   /// undefined.  isBigEndian describes the endianness of the target.
1816   bool isConstantSplat(APInt &SplatValue, APInt &SplatUndef,
1817                        unsigned &SplatBitSize, bool &HasAnyUndefs,
1818                        unsigned MinSplatBits = 0,
1819                        bool isBigEndian = false) const;
1820
1821   /// Returns the splatted value or a null value if this is not a splat.
1822   ///
1823   /// If passed a non-null UndefElements bitvector, it will resize it to match
1824   /// the vector width and set the bits where elements are undef.
1825   SDValue getSplatValue(BitVector *UndefElements = nullptr) const;
1826
1827   /// Returns the splatted constant or null if this is not a constant
1828   /// splat.
1829   ///
1830   /// If passed a non-null UndefElements bitvector, it will resize it to match
1831   /// the vector width and set the bits where elements are undef.
1832   ConstantSDNode *
1833   getConstantSplatNode(BitVector *UndefElements = nullptr) const;
1834
1835   /// Returns the splatted constant FP or null if this is not a constant
1836   /// FP splat.
1837   ///
1838   /// If passed a non-null UndefElements bitvector, it will resize it to match
1839   /// the vector width and set the bits where elements are undef.
1840   ConstantFPSDNode *
1841   getConstantFPSplatNode(BitVector *UndefElements = nullptr) const;
1842
1843   /// If this is a constant FP splat and the splatted constant FP is an
1844   /// exact power or 2, return the log base 2 integer value.  Otherwise,
1845   /// return -1.
1846   ///
1847   /// The BitWidth specifies the necessary bit precision.
1848   int32_t getConstantFPSplatPow2ToLog2Int(BitVector *UndefElements,
1849                                           uint32_t BitWidth) const;
1850
1851   bool isConstant() const;
1852
1853   static bool classof(const SDNode *N) {
1854     return N->getOpcode() == ISD::BUILD_VECTOR;
1855   }
1856 };
1857
1858 /// An SDNode that holds an arbitrary LLVM IR Value. This is
1859 /// used when the SelectionDAG needs to make a simple reference to something
1860 /// in the LLVM IR representation.
1861 ///
1862 class SrcValueSDNode : public SDNode {
1863   friend class SelectionDAG;
1864
1865   const Value *V;
1866
1867   /// Create a SrcValue for a general value.
1868   explicit SrcValueSDNode(const Value *v)
1869     : SDNode(ISD::SRCVALUE, 0, DebugLoc(), getSDVTList(MVT::Other)), V(v) {}
1870
1871 public:
1872   /// Return the contained Value.
1873   const Value *getValue() const { return V; }
1874
1875   static bool classof(const SDNode *N) {
1876     return N->getOpcode() == ISD::SRCVALUE;
1877   }
1878 };
1879
1880 class MDNodeSDNode : public SDNode {
1881   friend class SelectionDAG;
1882
1883   const MDNode *MD;
1884
1885   explicit MDNodeSDNode(const MDNode *md)
1886   : SDNode(ISD::MDNODE_SDNODE, 0, DebugLoc(), getSDVTList(MVT::Other)), MD(md)
1887   {}
1888
1889 public:
1890   const MDNode *getMD() const { return MD; }
1891
1892   static bool classof(const SDNode *N) {
1893     return N->getOpcode() == ISD::MDNODE_SDNODE;
1894   }
1895 };
1896
1897 class RegisterSDNode : public SDNode {
1898   friend class SelectionDAG;
1899
1900   unsigned Reg;
1901
1902   RegisterSDNode(unsigned reg, EVT VT)
1903     : SDNode(ISD::Register, 0, DebugLoc(), getSDVTList(VT)), Reg(reg) {}
1904
1905 public:
1906   unsigned getReg() const { return Reg; }
1907
1908   static bool classof(const SDNode *N) {
1909     return N->getOpcode() == ISD::Register;
1910   }
1911 };
1912
1913 class RegisterMaskSDNode : public SDNode {
1914   friend class SelectionDAG;
1915
1916   // The memory for RegMask is not owned by the node.
1917   const uint32_t *RegMask;
1918
1919   RegisterMaskSDNode(const uint32_t *mask)
1920     : SDNode(ISD::RegisterMask, 0, DebugLoc(), getSDVTList(MVT::Untyped)),
1921       RegMask(mask) {}
1922
1923 public:
1924   const uint32_t *getRegMask() const { return RegMask; }
1925
1926   static bool classof(const SDNode *N) {
1927     return N->getOpcode() == ISD::RegisterMask;
1928   }
1929 };
1930
1931 class BlockAddressSDNode : public SDNode {
1932   friend class SelectionDAG;
1933
1934   const BlockAddress *BA;
1935   int64_t Offset;
1936   unsigned char TargetFlags;
1937
1938   BlockAddressSDNode(unsigned NodeTy, EVT VT, const BlockAddress *ba,
1939                      int64_t o, unsigned char Flags)
1940     : SDNode(NodeTy, 0, DebugLoc(), getSDVTList(VT)),
1941              BA(ba), Offset(o), TargetFlags(Flags) {}
1942
1943 public:
1944   const BlockAddress *getBlockAddress() const { return BA; }
1945   int64_t getOffset() const { return Offset; }
1946   unsigned char getTargetFlags() const { return TargetFlags; }
1947
1948   static bool classof(const SDNode *N) {
1949     return N->getOpcode() == ISD::BlockAddress ||
1950            N->getOpcode() == ISD::TargetBlockAddress;
1951   }
1952 };
1953
1954 class LabelSDNode : public SDNode {
1955   friend class SelectionDAG;
1956
1957   MCSymbol *Label;
1958
1959   LabelSDNode(unsigned Order, const DebugLoc &dl, MCSymbol *L)
1960       : SDNode(ISD::EH_LABEL, Order, dl, getSDVTList(MVT::Other)), Label(L) {}
1961
1962 public:
1963   MCSymbol *getLabel() const { return Label; }
1964
1965   static bool classof(const SDNode *N) {
1966     return N->getOpcode() == ISD::EH_LABEL ||
1967            N->getOpcode() == ISD::ANNOTATION_LABEL;
1968   }
1969 };
1970
1971 class ExternalSymbolSDNode : public SDNode {
1972   friend class SelectionDAG;
1973
1974   const char *Symbol;
1975   unsigned char TargetFlags;
1976
1977   ExternalSymbolSDNode(bool isTarget, const char *Sym, unsigned char TF, EVT VT)
1978     : SDNode(isTarget ? ISD::TargetExternalSymbol : ISD::ExternalSymbol,
1979              0, DebugLoc(), getSDVTList(VT)), Symbol(Sym), TargetFlags(TF) {}
1980
1981 public:
1982   const char *getSymbol() const { return Symbol; }
1983   unsigned char getTargetFlags() const { return TargetFlags; }
1984
1985   static bool classof(const SDNode *N) {
1986     return N->getOpcode() == ISD::ExternalSymbol ||
1987            N->getOpcode() == ISD::TargetExternalSymbol;
1988   }
1989 };
1990
1991 class MCSymbolSDNode : public SDNode {
1992   friend class SelectionDAG;
1993
1994   MCSymbol *Symbol;
1995
1996   MCSymbolSDNode(MCSymbol *Symbol, EVT VT)
1997       : SDNode(ISD::MCSymbol, 0, DebugLoc(), getSDVTList(VT)), Symbol(Symbol) {}
1998
1999 public:
2000   MCSymbol *getMCSymbol() const { return Symbol; }
2001
2002   static bool classof(const SDNode *N) {
2003     return N->getOpcode() == ISD::MCSymbol;
2004   }
2005 };
2006
2007 class CondCodeSDNode : public SDNode {
2008   friend class SelectionDAG;
2009
2010   ISD::CondCode Condition;
2011
2012   explicit CondCodeSDNode(ISD::CondCode Cond)
2013     : SDNode(ISD::CONDCODE, 0, DebugLoc(), getSDVTList(MVT::Other)),
2014       Condition(Cond) {}
2015
2016 public:
2017   ISD::CondCode get() const { return Condition; }
2018
2019   static bool classof(const SDNode *N) {
2020     return N->getOpcode() == ISD::CONDCODE;
2021   }
2022 };
2023
2024 /// This class is used to represent EVT's, which are used
2025 /// to parameterize some operations.
2026 class VTSDNode : public SDNode {
2027   friend class SelectionDAG;
2028
2029   EVT ValueType;
2030
2031   explicit VTSDNode(EVT VT)
2032     : SDNode(ISD::VALUETYPE, 0, DebugLoc(), getSDVTList(MVT::Other)),
2033       ValueType(VT) {}
2034
2035 public:
2036   EVT getVT() const { return ValueType; }
2037
2038   static bool classof(const SDNode *N) {
2039     return N->getOpcode() == ISD::VALUETYPE;
2040   }
2041 };
2042
2043 /// Base class for LoadSDNode and StoreSDNode
2044 class LSBaseSDNode : public MemSDNode {
2045 public:
2046   LSBaseSDNode(ISD::NodeType NodeTy, unsigned Order, const DebugLoc &dl,
2047                SDVTList VTs, ISD::MemIndexedMode AM, EVT MemVT,
2048                MachineMemOperand *MMO)
2049       : MemSDNode(NodeTy, Order, dl, VTs, MemVT, MMO) {
2050     LSBaseSDNodeBits.AddressingMode = AM;
2051     assert(getAddressingMode() == AM && "Value truncated");
2052   }
2053
2054   const SDValue &getOffset() const {
2055     return getOperand(getOpcode() == ISD::LOAD ? 2 : 3);
2056   }
2057
2058   /// Return the addressing mode for this load or store:
2059   /// unindexed, pre-inc, pre-dec, post-inc, or post-dec.
2060   ISD::MemIndexedMode getAddressingMode() const {
2061     return static_cast<ISD::MemIndexedMode>(LSBaseSDNodeBits.AddressingMode);
2062   }
2063
2064   /// Return true if this is a pre/post inc/dec load/store.
2065   bool isIndexed() const { return getAddressingMode() != ISD::UNINDEXED; }
2066
2067   /// Return true if this is NOT a pre/post inc/dec load/store.
2068   bool isUnindexed() const { return getAddressingMode() == ISD::UNINDEXED; }
2069
2070   static bool classof(const SDNode *N) {
2071     return N->getOpcode() == ISD::LOAD ||
2072            N->getOpcode() == ISD::STORE;
2073   }
2074 };
2075
2076 /// This class is used to represent ISD::LOAD nodes.
2077 class LoadSDNode : public LSBaseSDNode {
2078   friend class SelectionDAG;
2079
2080   LoadSDNode(unsigned Order, const DebugLoc &dl, SDVTList VTs,
2081              ISD::MemIndexedMode AM, ISD::LoadExtType ETy, EVT MemVT,
2082              MachineMemOperand *MMO)
2083       : LSBaseSDNode(ISD::LOAD, Order, dl, VTs, AM, MemVT, MMO) {
2084     LoadSDNodeBits.ExtTy = ETy;
2085     assert(readMem() && "Load MachineMemOperand is not a load!");
2086     assert(!writeMem() && "Load MachineMemOperand is a store!");
2087   }
2088
2089 public:
2090   /// Return whether this is a plain node,
2091   /// or one of the varieties of value-extending loads.
2092   ISD::LoadExtType getExtensionType() const {
2093     return static_cast<ISD::LoadExtType>(LoadSDNodeBits.ExtTy);
2094   }
2095
2096   const SDValue &getBasePtr() const { return getOperand(1); }
2097   const SDValue &getOffset() const { return getOperand(2); }
2098
2099   static bool classof(const SDNode *N) {
2100     return N->getOpcode() == ISD::LOAD;
2101   }
2102 };
2103
2104 /// This class is used to represent ISD::STORE nodes.
2105 class StoreSDNode : public LSBaseSDNode {
2106   friend class SelectionDAG;
2107
2108   StoreSDNode(unsigned Order, const DebugLoc &dl, SDVTList VTs,
2109               ISD::MemIndexedMode AM, bool isTrunc, EVT MemVT,
2110               MachineMemOperand *MMO)
2111       : LSBaseSDNode(ISD::STORE, Order, dl, VTs, AM, MemVT, MMO) {
2112     StoreSDNodeBits.IsTruncating = isTrunc;
2113     assert(!readMem() && "Store MachineMemOperand is a load!");
2114     assert(writeMem() && "Store MachineMemOperand is not a store!");
2115   }
2116
2117 public:
2118   /// Return true if the op does a truncation before store.
2119   /// For integers this is the same as doing a TRUNCATE and storing the result.
2120   /// For floats, it is the same as doing an FP_ROUND and storing the result.
2121   bool isTruncatingStore() const { return StoreSDNodeBits.IsTruncating; }
2122   void setTruncatingStore(bool Truncating) {
2123     StoreSDNodeBits.IsTruncating = Truncating;
2124   }
2125
2126   const SDValue &getValue() const { return getOperand(1); }
2127   const SDValue &getBasePtr() const { return getOperand(2); }
2128   const SDValue &getOffset() const { return getOperand(3); }
2129
2130   static bool classof(const SDNode *N) {
2131     return N->getOpcode() == ISD::STORE;
2132   }
2133 };
2134
2135 /// This base class is used to represent MLOAD and MSTORE nodes
2136 class MaskedLoadStoreSDNode : public MemSDNode {
2137 public:
2138   friend class SelectionDAG;
2139
2140   MaskedLoadStoreSDNode(ISD::NodeType NodeTy, unsigned Order,
2141                         const DebugLoc &dl, SDVTList VTs, EVT MemVT,
2142                         MachineMemOperand *MMO)
2143       : MemSDNode(NodeTy, Order, dl, VTs, MemVT, MMO) {}
2144
2145   // MaskedLoadSDNode (Chain, ptr, mask, passthru)
2146   // MaskedStoreSDNode (Chain, data, ptr, mask)
2147   // Mask is a vector of i1 elements
2148   const SDValue &getBasePtr() const {
2149     return getOperand(getOpcode() == ISD::MLOAD ? 1 : 2);
2150   }
2151   const SDValue &getMask() const {
2152     return getOperand(getOpcode() == ISD::MLOAD ? 2 : 3);
2153   }
2154
2155   static bool classof(const SDNode *N) {
2156     return N->getOpcode() == ISD::MLOAD ||
2157            N->getOpcode() == ISD::MSTORE;
2158   }
2159 };
2160
2161 /// This class is used to represent an MLOAD node
2162 class MaskedLoadSDNode : public MaskedLoadStoreSDNode {
2163 public:
2164   friend class SelectionDAG;
2165
2166   MaskedLoadSDNode(unsigned Order, const DebugLoc &dl, SDVTList VTs,
2167                    ISD::LoadExtType ETy, bool IsExpanding, EVT MemVT,
2168                    MachineMemOperand *MMO)
2169       : MaskedLoadStoreSDNode(ISD::MLOAD, Order, dl, VTs, MemVT, MMO) {
2170     LoadSDNodeBits.ExtTy = ETy;
2171     LoadSDNodeBits.IsExpanding = IsExpanding;
2172   }
2173
2174   ISD::LoadExtType getExtensionType() const {
2175     return static_cast<ISD::LoadExtType>(LoadSDNodeBits.ExtTy);
2176   }
2177
2178   const SDValue &getBasePtr() const { return getOperand(1); }
2179   const SDValue &getMask() const    { return getOperand(2); }
2180   const SDValue &getPassThru() const { return getOperand(3); }
2181
2182   static bool classof(const SDNode *N) {
2183     return N->getOpcode() == ISD::MLOAD;
2184   }
2185
2186   bool isExpandingLoad() const { return LoadSDNodeBits.IsExpanding; }
2187 };
2188
2189 /// This class is used to represent an MSTORE node
2190 class MaskedStoreSDNode : public MaskedLoadStoreSDNode {
2191 public:
2192   friend class SelectionDAG;
2193
2194   MaskedStoreSDNode(unsigned Order, const DebugLoc &dl, SDVTList VTs,
2195                     bool isTrunc, bool isCompressing, EVT MemVT,
2196                     MachineMemOperand *MMO)
2197       : MaskedLoadStoreSDNode(ISD::MSTORE, Order, dl, VTs, MemVT, MMO) {
2198     StoreSDNodeBits.IsTruncating = isTrunc;
2199     StoreSDNodeBits.IsCompressing = isCompressing;
2200   }
2201
2202   /// Return true if the op does a truncation before store.
2203   /// For integers this is the same as doing a TRUNCATE and storing the result.
2204   /// For floats, it is the same as doing an FP_ROUND and storing the result.
2205   bool isTruncatingStore() const { return StoreSDNodeBits.IsTruncating; }
2206
2207   /// Returns true if the op does a compression to the vector before storing.
2208   /// The node contiguously stores the active elements (integers or floats)
2209   /// in src (those with their respective bit set in writemask k) to unaligned
2210   /// memory at base_addr.
2211   bool isCompressingStore() const { return StoreSDNodeBits.IsCompressing; }
2212
2213   const SDValue &getValue() const   { return getOperand(1); }
2214   const SDValue &getBasePtr() const { return getOperand(2); }
2215   const SDValue &getMask() const    { return getOperand(3); }
2216
2217   static bool classof(const SDNode *N) {
2218     return N->getOpcode() == ISD::MSTORE;
2219   }
2220 };
2221
2222 /// This is a base class used to represent
2223 /// MGATHER and MSCATTER nodes
2224 ///
2225 class MaskedGatherScatterSDNode : public MemSDNode {
2226 public:
2227   friend class SelectionDAG;
2228
2229   MaskedGatherScatterSDNode(ISD::NodeType NodeTy, unsigned Order,
2230                             const DebugLoc &dl, SDVTList VTs, EVT MemVT,
2231                             MachineMemOperand *MMO)
2232       : MemSDNode(NodeTy, Order, dl, VTs, MemVT, MMO) {}
2233
2234   // In the both nodes address is Op1, mask is Op2:
2235   // MaskedGatherSDNode  (Chain, passthru, mask, base, index, scale)
2236   // MaskedScatterSDNode (Chain, value, mask, base, index, scale)
2237   // Mask is a vector of i1 elements
2238   const SDValue &getBasePtr() const { return getOperand(3); }
2239   const SDValue &getIndex()   const { return getOperand(4); }
2240   const SDValue &getMask()    const { return getOperand(2); }
2241   const SDValue &getScale()   const { return getOperand(5); }
2242
2243   static bool classof(const SDNode *N) {
2244     return N->getOpcode() == ISD::MGATHER ||
2245            N->getOpcode() == ISD::MSCATTER;
2246   }
2247 };
2248
2249 /// This class is used to represent an MGATHER node
2250 ///
2251 class MaskedGatherSDNode : public MaskedGatherScatterSDNode {
2252 public:
2253   friend class SelectionDAG;
2254
2255   MaskedGatherSDNode(unsigned Order, const DebugLoc &dl, SDVTList VTs,
2256                      EVT MemVT, MachineMemOperand *MMO)
2257       : MaskedGatherScatterSDNode(ISD::MGATHER, Order, dl, VTs, MemVT, MMO) {}
2258
2259   const SDValue &getPassThru() const { return getOperand(1); }
2260
2261   static bool classof(const SDNode *N) {
2262     return N->getOpcode() == ISD::MGATHER;
2263   }
2264 };
2265
2266 /// This class is used to represent an MSCATTER node
2267 ///
2268 class MaskedScatterSDNode : public MaskedGatherScatterSDNode {
2269 public:
2270   friend class SelectionDAG;
2271
2272   MaskedScatterSDNode(unsigned Order, const DebugLoc &dl, SDVTList VTs,
2273                       EVT MemVT, MachineMemOperand *MMO)
2274       : MaskedGatherScatterSDNode(ISD::MSCATTER, Order, dl, VTs, MemVT, MMO) {}
2275
2276   const SDValue &getValue() const { return getOperand(1); }
2277
2278   static bool classof(const SDNode *N) {
2279     return N->getOpcode() == ISD::MSCATTER;
2280   }
2281 };
2282
2283 /// An SDNode that represents everything that will be needed
2284 /// to construct a MachineInstr. These nodes are created during the
2285 /// instruction selection proper phase.
2286 ///
2287 /// Note that the only supported way to set the `memoperands` is by calling the
2288 /// `SelectionDAG::setNodeMemRefs` function as the memory management happens
2289 /// inside the DAG rather than in the node.
2290 class MachineSDNode : public SDNode {
2291 private:
2292   friend class SelectionDAG;
2293
2294   MachineSDNode(unsigned Opc, unsigned Order, const DebugLoc &DL, SDVTList VTs)
2295       : SDNode(Opc, Order, DL, VTs) {}
2296
2297   // We use a pointer union between a single `MachineMemOperand` pointer and
2298   // a pointer to an array of `MachineMemOperand` pointers. This is null when
2299   // the number of these is zero, the single pointer variant used when the
2300   // number is one, and the array is used for larger numbers.
2301   //
2302   // The array is allocated via the `SelectionDAG`'s allocator and so will
2303   // always live until the DAG is cleaned up and doesn't require ownership here.
2304   //
2305   // We can't use something simpler like `TinyPtrVector` here because `SDNode`
2306   // subclasses aren't managed in a conforming C++ manner. See the comments on
2307   // `SelectionDAG::MorphNodeTo` which details what all goes on, but the
2308   // constraint here is that these don't manage memory with their constructor or
2309   // destructor and can be initialized to a good state even if they start off
2310   // uninitialized.
2311   PointerUnion<MachineMemOperand *, MachineMemOperand **> MemRefs = {};
2312
2313   // Note that this could be folded into the above `MemRefs` member if doing so
2314   // is advantageous at some point. We don't need to store this in most cases.
2315   // However, at the moment this doesn't appear to make the allocation any
2316   // smaller and makes the code somewhat simpler to read.
2317   int NumMemRefs = 0;
2318
2319 public:
2320   using mmo_iterator = ArrayRef<MachineMemOperand *>::const_iterator;
2321
2322   ArrayRef<MachineMemOperand *> memoperands() const {
2323     // Special case the common cases.
2324     if (NumMemRefs == 0)
2325       return {};
2326     if (NumMemRefs == 1)
2327       return makeArrayRef(MemRefs.getAddrOfPtr1(), 1);
2328
2329     // Otherwise we have an actual array.
2330     return makeArrayRef(MemRefs.get<MachineMemOperand **>(), NumMemRefs);
2331   }
2332   mmo_iterator memoperands_begin() const { return memoperands().begin(); }
2333   mmo_iterator memoperands_end() const { return memoperands().end(); }
2334   bool memoperands_empty() const { return memoperands().empty(); }
2335
2336   /// Clear out the memory reference descriptor list.
2337   void clearMemRefs() {
2338     MemRefs = nullptr;
2339     NumMemRefs = 0;
2340   }
2341
2342   static bool classof(const SDNode *N) {
2343     return N->isMachineOpcode();
2344   }
2345 };
2346
2347 class SDNodeIterator : public std::iterator<std::forward_iterator_tag,
2348                                             SDNode, ptrdiff_t> {
2349   const SDNode *Node;
2350   unsigned Operand;
2351
2352   SDNodeIterator(const SDNode *N, unsigned Op) : Node(N), Operand(Op) {}
2353
2354 public:
2355   bool operator==(const SDNodeIterator& x) const {
2356     return Operand == x.Operand;
2357   }
2358   bool operator!=(const SDNodeIterator& x) const { return !operator==(x); }
2359
2360   pointer operator*() const {
2361     return Node->getOperand(Operand).getNode();
2362   }
2363   pointer operator->() const { return operator*(); }
2364
2365   SDNodeIterator& operator++() {                // Preincrement
2366     ++Operand;
2367     return *this;
2368   }
2369   SDNodeIterator operator++(int) { // Postincrement
2370     SDNodeIterator tmp = *this; ++*this; return tmp;
2371   }
2372   size_t operator-(SDNodeIterator Other) const {
2373     assert(Node == Other.Node &&
2374            "Cannot compare iterators of two different nodes!");
2375     return Operand - Other.Operand;
2376   }
2377
2378   static SDNodeIterator begin(const SDNode *N) { return SDNodeIterator(N, 0); }
2379   static SDNodeIterator end  (const SDNode *N) {
2380     return SDNodeIterator(N, N->getNumOperands());
2381   }
2382
2383   unsigned getOperand() const { return Operand; }
2384   const SDNode *getNode() const { return Node; }
2385 };
2386
2387 template <> struct GraphTraits<SDNode*> {
2388   using NodeRef = SDNode *;
2389   using ChildIteratorType = SDNodeIterator;
2390
2391   static NodeRef getEntryNode(SDNode *N) { return N; }
2392
2393   static ChildIteratorType child_begin(NodeRef N) {
2394     return SDNodeIterator::begin(N);
2395   }
2396
2397   static ChildIteratorType child_end(NodeRef N) {
2398     return SDNodeIterator::end(N);
2399   }
2400 };
2401
2402 /// A representation of the largest SDNode, for use in sizeof().
2403 ///
2404 /// This needs to be a union because the largest node differs on 32 bit systems
2405 /// with 4 and 8 byte pointer alignment, respectively.
2406 using LargestSDNode = AlignedCharArrayUnion<AtomicSDNode, TargetIndexSDNode,
2407                                             BlockAddressSDNode,
2408                                             GlobalAddressSDNode>;
2409
2410 /// The SDNode class with the greatest alignment requirement.
2411 using MostAlignedSDNode = GlobalAddressSDNode;
2412
2413 namespace ISD {
2414
2415   /// Returns true if the specified node is a non-extending and unindexed load.
2416   inline bool isNormalLoad(const SDNode *N) {
2417     const LoadSDNode *Ld = dyn_cast<LoadSDNode>(N);
2418     return Ld && Ld->getExtensionType() == ISD::NON_EXTLOAD &&
2419       Ld->getAddressingMode() == ISD::UNINDEXED;
2420   }
2421
2422   /// Returns true if the specified node is a non-extending load.
2423   inline bool isNON_EXTLoad(const SDNode *N) {
2424     return isa<LoadSDNode>(N) &&
2425       cast<LoadSDNode>(N)->getExtensionType() == ISD::NON_EXTLOAD;
2426   }
2427
2428   /// Returns true if the specified node is a EXTLOAD.
2429   inline bool isEXTLoad(const SDNode *N) {
2430     return isa<LoadSDNode>(N) &&
2431       cast<LoadSDNode>(N)->getExtensionType() == ISD::EXTLOAD;
2432   }
2433
2434   /// Returns true if the specified node is a SEXTLOAD.
2435   inline bool isSEXTLoad(const SDNode *N) {
2436     return isa<LoadSDNode>(N) &&
2437       cast<LoadSDNode>(N)->getExtensionType() == ISD::SEXTLOAD;
2438   }
2439
2440   /// Returns true if the specified node is a ZEXTLOAD.
2441   inline bool isZEXTLoad(const SDNode *N) {
2442     return isa<LoadSDNode>(N) &&
2443       cast<LoadSDNode>(N)->getExtensionType() == ISD::ZEXTLOAD;
2444   }
2445
2446   /// Returns true if the specified node is an unindexed load.
2447   inline bool isUNINDEXEDLoad(const SDNode *N) {
2448     return isa<LoadSDNode>(N) &&
2449       cast<LoadSDNode>(N)->getAddressingMode() == ISD::UNINDEXED;
2450   }
2451
2452   /// Returns true if the specified node is a non-truncating
2453   /// and unindexed store.
2454   inline bool isNormalStore(const SDNode *N) {
2455     const StoreSDNode *St = dyn_cast<StoreSDNode>(N);
2456     return St && !St->isTruncatingStore() &&
2457       St->getAddressingMode() == ISD::UNINDEXED;
2458   }
2459
2460   /// Returns true if the specified node is a non-truncating store.
2461   inline bool isNON_TRUNCStore(const SDNode *N) {
2462     return isa<StoreSDNode>(N) && !cast<StoreSDNode>(N)->isTruncatingStore();
2463   }
2464
2465   /// Returns true if the specified node is a truncating store.
2466   inline bool isTRUNCStore(const SDNode *N) {
2467     return isa<StoreSDNode>(N) && cast<StoreSDNode>(N)->isTruncatingStore();
2468   }
2469
2470   /// Returns true if the specified node is an unindexed store.
2471   inline bool isUNINDEXEDStore(const SDNode *N) {
2472     return isa<StoreSDNode>(N) &&
2473       cast<StoreSDNode>(N)->getAddressingMode() == ISD::UNINDEXED;
2474   }
2475
2476   /// Return true if the node is a math/logic binary operator. This corresponds
2477   /// to the IR function of the same name.
2478   inline bool isBinaryOp(const SDNode *N) {
2479     auto Op = N->getOpcode();
2480     return (Op == ISD::ADD || Op == ISD::SUB || Op == ISD::MUL ||
2481             Op == ISD::AND || Op == ISD::OR || Op == ISD::XOR ||
2482             Op == ISD::SHL || Op == ISD::SRL || Op == ISD::SRA ||
2483             Op == ISD::SDIV || Op == ISD::UDIV || Op == ISD::SREM ||
2484             Op == ISD::UREM || Op == ISD::FADD || Op == ISD::FSUB ||
2485             Op == ISD::FMUL || Op == ISD::FDIV || Op == ISD::FREM);
2486   }
2487
2488   /// Attempt to match a unary predicate against a scalar/splat constant or
2489   /// every element of a constant BUILD_VECTOR.
2490   /// If AllowUndef is true, then UNDEF elements will pass nullptr to Match.
2491   bool matchUnaryPredicate(SDValue Op,
2492                            std::function<bool(ConstantSDNode *)> Match,
2493                            bool AllowUndefs = false);
2494
2495   /// Attempt to match a binary predicate against a pair of scalar/splat
2496   /// constants or every element of a pair of constant BUILD_VECTORs.
2497   /// If AllowUndef is true, then UNDEF elements will pass nullptr to Match.
2498   bool matchBinaryPredicate(
2499       SDValue LHS, SDValue RHS,
2500       std::function<bool(ConstantSDNode *, ConstantSDNode *)> Match,
2501       bool AllowUndefs = false);
2502 } // end namespace ISD
2503
2504 } // end namespace llvm
2505
2506 #endif // LLVM_CODEGEN_SELECTIONDAGNODES_H