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