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 55namespace llvm { 56 57class APInt; 58class Constant; 59template <typename T> struct DenseMapInfo; 60class GlobalValue; 61class MachineBasicBlock; 62class MachineConstantPoolValue; 63class MCSymbol; 64class raw_ostream; 65class SDNode; 66class SelectionDAG; 67class Type; 68class Value; 69 70void 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/// 77struct SDVTList { 78 const EVT *VTs; 79 unsigned int NumVTs; 80}; 81 82namespace 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/// 123class 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 129public: 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; 193 inline void dumpr() 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 210template<> 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}; 232template <> 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. 236template<> struct simplify_type<SDValue> { 237 using SimpleType = SDNode *; 238 239 static SimpleType getSimplifiedValue(SDValue &Val) { 240 return Val.getNode(); 241 } 242}; 243template<> 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/// 256class 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 266public: 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 306private: 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. 339template<> 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. 350struct SDNodeFlags { 351private: 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 368public: 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/// 455class SDNode : public FoldingSetNode, public ilist_node<SDNode> { 456private: 457 /// The operation that this node performs. 458 int16_t NodeType; 459 460protected: 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 546private: 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 583public: 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 977protected: 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. 1009class SDLoc { 1010private: 1011 DebugLoc DL; 1012 int IROrder = 0; 1013 1014public: 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 1030inline 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 1040inline unsigned SDValue::getOpcode() const { 1041 return Node->getOpcode(); 1042} 1043 1044inline EVT SDValue::getValueType() const { 1045 return Node->getValueType(ResNo); 1046} 1047 1048inline unsigned SDValue::getNumOperands() const { 1049 return Node->getNumOperands(); 1050} 1051 1052inline const SDValue &SDValue::getOperand(unsigned i) const { 1053 return Node->getOperand(i); 1054} 1055 1056inline uint64_t SDValue::getConstantOperandVal(unsigned i) const { 1057 return Node->getConstantOperandVal(i); 1058} 1059 1060inline bool SDValue::isTargetOpcode() const { 1061 return Node->isTargetOpcode(); 1062} 1063 1064inline bool SDValue::isTargetMemoryOpcode() const { 1065 return Node->isTargetMemoryOpcode(); 1066} 1067 1068inline bool SDValue::isMachineOpcode() const { 1069 return Node->isMachineOpcode(); 1070} 1071 1072inline unsigned SDValue::getMachineOpcode() const { 1073 return Node->getMachineOpcode(); 1074} 1075 1076inline bool SDValue::isUndef() const { 1077 return Node->isUndef(); 1078} 1079 1080inline bool SDValue::use_empty() const { 1081 return !Node->hasAnyUseOfValue(ResNo); 1082} 1083 1084inline bool SDValue::hasOneUse() const { 1085 return Node->hasNUsesOfValue(1, ResNo); 1086} 1087 1088inline const DebugLoc &SDValue::getDebugLoc() const { 1089 return Node->getDebugLoc(); 1090} 1091 1092inline void SDValue::dump() const { 1093 return Node->dump(); 1094} 1095 1096inline void SDValue::dumpr() const { 1097 return Node->dumpr(); 1098} 1099 1100// Define inline functions from the SDUse class. 1101 1102inline void SDUse::set(const SDValue &V) { 1103 if (Val.getNode()) removeFromList(); 1104 Val = V; 1105 if (V.getNode()) V.getNode()->addUse(*this); 1106} 1107 1108inline void SDUse::setInitial(const SDValue &V) { 1109 Val = V; 1110 V.getNode()->addUse(*this); 1111} 1112 1113inline 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. 1123class HandleSDNode : public SDNode { 1124 SDUse Op; 1125 1126public: 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 1147class AddrSpaceCastSDNode : public SDNode { 1148private: 1149 unsigned SrcAddrSpace; 1150 unsigned DestAddrSpace; 1151 1152public: 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. 1165class MemSDNode : public SDNode { 1166private: 1167 // VT of in-memory value. 1168 EVT MemoryVT; 1169 1170protected: 1171 /// Memory reference information. 1172 MachineMemOperand *MMO; 1173 1174public: 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. 1289class AtomicSDNode : public MemSDNode { 1290public: 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. 1337class MemIntrinsicSDNode : public MemSDNode { 1338public: 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. 1363class 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 1368protected: 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 1374public: 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 1419class 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 1432public: 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 1453uint64_t SDNode::getConstantOperandVal(unsigned Num) const { 1454 return cast<ConstantSDNode>(getOperand(Num))->getZExtValue(); 1455} 1456 1457class 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 1468public: 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. 1506bool isNullConstant(SDValue V); 1507 1508/// Returns true if \p V is an FP constant with a value of positive zero. 1509bool isNullFPConstant(SDValue V); 1510 1511/// Returns true if \p V is an integer constant with all bits set. 1512bool isAllOnesConstant(SDValue V); 1513 1514/// Returns true if \p V is a constant integer one. 1515bool 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. 1519bool isBitwiseNot(SDValue V); 1520 1521/// Returns the SDNode if it is a constant splat BuildVector or constant int. 1522ConstantSDNode *isConstOrConstSplat(SDValue V); 1523 1524/// Returns the SDNode if it is a constant splat BuildVector or constant float. 1525ConstantFPSDNode *isConstOrConstSplatFP(SDValue V); 1526 1527class 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 1538public: 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 1553class 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 1563public: 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 1572class 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 1583public: 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 1593class 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 1623public: 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. 1656class TargetIndexSDNode : public SDNode { 1657 friend class SelectionDAG; 1658 1659 unsigned char TargetFlags; 1660 int Index; 1661 int64_t Offset; 1662 1663public: 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 1677class 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 1689public: 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. 1698class BuildVectorSDNode : public SDNode { 1699public: 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/// 1758class 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 1767public: 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 1776class 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 1785public: 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 1793class 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 1801public: 1802 unsigned getReg() const { return Reg; } 1803 1804 static bool classof(const SDNode *N) { 1805 return N->getOpcode() == ISD::Register; 1806 } 1807}; 1808 1809class 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 1819public: 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 1827class 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 1839public: 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 1850class 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 1858public: 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 1867class 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 1877public: 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 1887class 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 1895public: 1896 MCSymbol *getMCSymbol() const { return Symbol; } 1897 1898 static bool classof(const SDNode *N) { 1899 return N->getOpcode() == ISD::MCSymbol; 1900 } 1901}; 1902 1903class 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 1912public: 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. 1922class 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 1931public: 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 1940class LSBaseSDNode : public MemSDNode { 1941public: 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. 1973class 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 1985public: 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. 2001class 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 2013public: 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 2019 const SDValue &getValue() const { return getOperand(1); } 2020 const SDValue &getBasePtr() const { return getOperand(2); } 2021 const SDValue &getOffset() const { return getOperand(3); } 2022 2023 static bool classof(const SDNode *N) { 2024 return N->getOpcode() == ISD::STORE; 2025 } 2026}; 2027 2028/// This base class is used to represent MLOAD and MSTORE nodes 2029class MaskedLoadStoreSDNode : public MemSDNode { 2030public: 2031 friend class SelectionDAG; 2032 2033 MaskedLoadStoreSDNode(ISD::NodeType NodeTy, unsigned Order, 2034 const DebugLoc &dl, SDVTList VTs, EVT MemVT, 2035 MachineMemOperand *MMO) 2036 : MemSDNode(NodeTy, Order, dl, VTs, MemVT, MMO) {} 2037 2038 // In the both nodes address is Op1, mask is Op2: 2039 // MaskedLoadSDNode (Chain, ptr, mask, src0), src0 is a passthru value 2040 // MaskedStoreSDNode (Chain, ptr, mask, data) 2041 // Mask is a vector of i1 elements 2042 const SDValue &getBasePtr() const { return getOperand(1); } 2043 const SDValue &getMask() const { return getOperand(2); } 2044 2045 static bool classof(const SDNode *N) { 2046 return N->getOpcode() == ISD::MLOAD || 2047 N->getOpcode() == ISD::MSTORE; 2048 } 2049}; 2050 2051/// This class is used to represent an MLOAD node 2052class MaskedLoadSDNode : public MaskedLoadStoreSDNode { 2053public: 2054 friend class SelectionDAG; 2055 2056 MaskedLoadSDNode(unsigned Order, const DebugLoc &dl, SDVTList VTs, 2057 ISD::LoadExtType ETy, bool IsExpanding, EVT MemVT, 2058 MachineMemOperand *MMO) 2059 : MaskedLoadStoreSDNode(ISD::MLOAD, Order, dl, VTs, MemVT, MMO) { 2060 LoadSDNodeBits.ExtTy = ETy; 2061 LoadSDNodeBits.IsExpanding = IsExpanding; 2062 } 2063 2064 ISD::LoadExtType getExtensionType() const { 2065 return static_cast<ISD::LoadExtType>(LoadSDNodeBits.ExtTy); 2066 } 2067 2068 const SDValue &getSrc0() const { return getOperand(3); } 2069 static bool classof(const SDNode *N) { 2070 return N->getOpcode() == ISD::MLOAD; 2071 } 2072 2073 bool isExpandingLoad() const { return LoadSDNodeBits.IsExpanding; } 2074}; 2075 2076/// This class is used to represent an MSTORE node 2077class MaskedStoreSDNode : public MaskedLoadStoreSDNode { 2078public: 2079 friend class SelectionDAG; 2080 2081 MaskedStoreSDNode(unsigned Order, const DebugLoc &dl, SDVTList VTs, 2082 bool isTrunc, bool isCompressing, EVT MemVT, 2083 MachineMemOperand *MMO) 2084 : MaskedLoadStoreSDNode(ISD::MSTORE, Order, dl, VTs, MemVT, MMO) { 2085 StoreSDNodeBits.IsTruncating = isTrunc; 2086 StoreSDNodeBits.IsCompressing = isCompressing; 2087 } 2088 2089 /// Return true if the op does a truncation before store. 2090 /// For integers this is the same as doing a TRUNCATE and storing the result. 2091 /// For floats, it is the same as doing an FP_ROUND and storing the result. 2092 bool isTruncatingStore() const { return StoreSDNodeBits.IsTruncating; } 2093 2094 /// Returns true if the op does a compression to the vector before storing. 2095 /// The node contiguously stores the active elements (integers or floats) 2096 /// in src (those with their respective bit set in writemask k) to unaligned 2097 /// memory at base_addr. 2098 bool isCompressingStore() const { return StoreSDNodeBits.IsCompressing; } 2099 2100 const SDValue &getValue() const { return getOperand(3); } 2101 2102 static bool classof(const SDNode *N) { 2103 return N->getOpcode() == ISD::MSTORE; 2104 } 2105}; 2106 2107/// This is a base class used to represent 2108/// MGATHER and MSCATTER nodes 2109/// 2110class MaskedGatherScatterSDNode : public MemSDNode { 2111public: 2112 friend class SelectionDAG; 2113 2114 MaskedGatherScatterSDNode(unsigned NodeTy, unsigned Order, 2115 const DebugLoc &dl, SDVTList VTs, EVT MemVT, 2116 MachineMemOperand *MMO) 2117 : MemSDNode(NodeTy, Order, dl, VTs, MemVT, MMO) {} 2118 2119 // In the both nodes address is Op1, mask is Op2: 2120 // MaskedGatherSDNode (Chain, src0, mask, base, index), src0 is a passthru value 2121 // MaskedScatterSDNode (Chain, value, mask, base, index) 2122 // Mask is a vector of i1 elements 2123 const SDValue &getBasePtr() const { return getOperand(3); } 2124 const SDValue &getIndex() const { return getOperand(4); } 2125 const SDValue &getMask() const { return getOperand(2); } 2126 const SDValue &getValue() const { return getOperand(1); } 2127 2128 static bool classof(const SDNode *N) { 2129 return N->getOpcode() == ISD::MGATHER || 2130 N->getOpcode() == ISD::MSCATTER; 2131 } 2132}; 2133 2134/// This class is used to represent an MGATHER node 2135/// 2136class MaskedGatherSDNode : public MaskedGatherScatterSDNode { 2137public: 2138 friend class SelectionDAG; 2139 2140 MaskedGatherSDNode(unsigned Order, const DebugLoc &dl, SDVTList VTs, 2141 EVT MemVT, MachineMemOperand *MMO) 2142 : MaskedGatherScatterSDNode(ISD::MGATHER, Order, dl, VTs, MemVT, MMO) {} 2143 2144 static bool classof(const SDNode *N) { 2145 return N->getOpcode() == ISD::MGATHER; 2146 } 2147}; 2148 2149/// This class is used to represent an MSCATTER node 2150/// 2151class MaskedScatterSDNode : public MaskedGatherScatterSDNode { 2152public: 2153 friend class SelectionDAG; 2154 2155 MaskedScatterSDNode(unsigned Order, const DebugLoc &dl, SDVTList VTs, 2156 EVT MemVT, MachineMemOperand *MMO) 2157 : MaskedGatherScatterSDNode(ISD::MSCATTER, Order, dl, VTs, MemVT, MMO) {} 2158 2159 static bool classof(const SDNode *N) { 2160 return N->getOpcode() == ISD::MSCATTER; 2161 } 2162}; 2163 2164/// An SDNode that represents everything that will be needed 2165/// to construct a MachineInstr. These nodes are created during the 2166/// instruction selection proper phase. 2167class MachineSDNode : public SDNode { 2168public: 2169 using mmo_iterator = MachineMemOperand **; 2170 2171private: 2172 friend class SelectionDAG; 2173 2174 MachineSDNode(unsigned Opc, unsigned Order, const DebugLoc &DL, SDVTList VTs) 2175 : SDNode(Opc, Order, DL, VTs) {} 2176 2177 /// Memory reference descriptions for this instruction. 2178 mmo_iterator MemRefs = nullptr; 2179 mmo_iterator MemRefsEnd = nullptr; 2180 2181public: 2182 mmo_iterator memoperands_begin() const { return MemRefs; } 2183 mmo_iterator memoperands_end() const { return MemRefsEnd; } 2184 bool memoperands_empty() const { return MemRefsEnd == MemRefs; } 2185 2186 /// Assign this MachineSDNodes's memory reference descriptor 2187 /// list. This does not transfer ownership. 2188 void setMemRefs(mmo_iterator NewMemRefs, mmo_iterator NewMemRefsEnd) { 2189 for (mmo_iterator MMI = NewMemRefs, MME = NewMemRefsEnd; MMI != MME; ++MMI) 2190 assert(*MMI && "Null mem ref detected!"); 2191 MemRefs = NewMemRefs; 2192 MemRefsEnd = NewMemRefsEnd; 2193 } 2194 2195 static bool classof(const SDNode *N) { 2196 return N->isMachineOpcode(); 2197 } 2198}; 2199 2200class SDNodeIterator : public std::iterator<std::forward_iterator_tag, 2201 SDNode, ptrdiff_t> { 2202 const SDNode *Node; 2203 unsigned Operand; 2204 2205 SDNodeIterator(const SDNode *N, unsigned Op) : Node(N), Operand(Op) {} 2206 2207public: 2208 bool operator==(const SDNodeIterator& x) const { 2209 return Operand == x.Operand; 2210 } 2211 bool operator!=(const SDNodeIterator& x) const { return !operator==(x); } 2212 2213 pointer operator*() const { 2214 return Node->getOperand(Operand).getNode(); 2215 } 2216 pointer operator->() const { return operator*(); } 2217 2218 SDNodeIterator& operator++() { // Preincrement 2219 ++Operand; 2220 return *this; 2221 } 2222 SDNodeIterator operator++(int) { // Postincrement 2223 SDNodeIterator tmp = *this; ++*this; return tmp; 2224 } 2225 size_t operator-(SDNodeIterator Other) const { 2226 assert(Node == Other.Node && 2227 "Cannot compare iterators of two different nodes!"); 2228 return Operand - Other.Operand; 2229 } 2230 2231 static SDNodeIterator begin(const SDNode *N) { return SDNodeIterator(N, 0); } 2232 static SDNodeIterator end (const SDNode *N) { 2233 return SDNodeIterator(N, N->getNumOperands()); 2234 } 2235 2236 unsigned getOperand() const { return Operand; } 2237 const SDNode *getNode() const { return Node; } 2238}; 2239 2240template <> struct GraphTraits<SDNode*> { 2241 using NodeRef = SDNode *; 2242 using ChildIteratorType = SDNodeIterator; 2243 2244 static NodeRef getEntryNode(SDNode *N) { return N; } 2245 2246 static ChildIteratorType child_begin(NodeRef N) { 2247 return SDNodeIterator::begin(N); 2248 } 2249 2250 static ChildIteratorType child_end(NodeRef N) { 2251 return SDNodeIterator::end(N); 2252 } 2253}; 2254 2255/// A representation of the largest SDNode, for use in sizeof(). 2256/// 2257/// This needs to be a union because the largest node differs on 32 bit systems 2258/// with 4 and 8 byte pointer alignment, respectively. 2259using LargestSDNode = AlignedCharArrayUnion<AtomicSDNode, TargetIndexSDNode, 2260 BlockAddressSDNode, 2261 GlobalAddressSDNode>; 2262 2263/// The SDNode class with the greatest alignment requirement. 2264using MostAlignedSDNode = GlobalAddressSDNode; 2265 2266namespace ISD { 2267 2268 /// Returns true if the specified node is a non-extending and unindexed load. 2269 inline bool isNormalLoad(const SDNode *N) { 2270 const LoadSDNode *Ld = dyn_cast<LoadSDNode>(N); 2271 return Ld && Ld->getExtensionType() == ISD::NON_EXTLOAD && 2272 Ld->getAddressingMode() == ISD::UNINDEXED; 2273 } 2274 2275 /// Returns true if the specified node is a non-extending load. 2276 inline bool isNON_EXTLoad(const SDNode *N) { 2277 return isa<LoadSDNode>(N) && 2278 cast<LoadSDNode>(N)->getExtensionType() == ISD::NON_EXTLOAD; 2279 } 2280 2281 /// Returns true if the specified node is a EXTLOAD. 2282 inline bool isEXTLoad(const SDNode *N) { 2283 return isa<LoadSDNode>(N) && 2284 cast<LoadSDNode>(N)->getExtensionType() == ISD::EXTLOAD; 2285 } 2286 2287 /// Returns true if the specified node is a SEXTLOAD. 2288 inline bool isSEXTLoad(const SDNode *N) { 2289 return isa<LoadSDNode>(N) && 2290 cast<LoadSDNode>(N)->getExtensionType() == ISD::SEXTLOAD; 2291 } 2292 2293 /// Returns true if the specified node is a ZEXTLOAD. 2294 inline bool isZEXTLoad(const SDNode *N) { 2295 return isa<LoadSDNode>(N) && 2296 cast<LoadSDNode>(N)->getExtensionType() == ISD::ZEXTLOAD; 2297 } 2298 2299 /// Returns true if the specified node is an unindexed load. 2300 inline bool isUNINDEXEDLoad(const SDNode *N) { 2301 return isa<LoadSDNode>(N) && 2302 cast<LoadSDNode>(N)->getAddressingMode() == ISD::UNINDEXED; 2303 } 2304 2305 /// Returns true if the specified node is a non-truncating 2306 /// and unindexed store. 2307 inline bool isNormalStore(const SDNode *N) { 2308 const StoreSDNode *St = dyn_cast<StoreSDNode>(N); 2309 return St && !St->isTruncatingStore() && 2310 St->getAddressingMode() == ISD::UNINDEXED; 2311 } 2312 2313 /// Returns true if the specified node is a non-truncating store. 2314 inline bool isNON_TRUNCStore(const SDNode *N) { 2315 return isa<StoreSDNode>(N) && !cast<StoreSDNode>(N)->isTruncatingStore(); 2316 } 2317 2318 /// Returns true if the specified node is a truncating store. 2319 inline bool isTRUNCStore(const SDNode *N) { 2320 return isa<StoreSDNode>(N) && cast<StoreSDNode>(N)->isTruncatingStore(); 2321 } 2322 2323 /// Returns true if the specified node is an unindexed store. 2324 inline bool isUNINDEXEDStore(const SDNode *N) { 2325 return isa<StoreSDNode>(N) && 2326 cast<StoreSDNode>(N)->getAddressingMode() == ISD::UNINDEXED; 2327 } 2328 2329} // end namespace ISD 2330 2331} // end namespace llvm 2332 2333#endif // LLVM_CODEGEN_SELECTIONDAGNODES_H 2334