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