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