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

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