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