include/llvm/CodeGen/SelectionDAGNodes.h

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