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