Line data Source code
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 33795321 : SDValue() = default;
132 : SDValue(SDNode *node, unsigned resno);
133 :
134 : /// get the index which selects a specific result in the SDNode
135 0 : unsigned getResNo() const { return ResNo; }
136 :
137 : /// get the SDNode which holds the desired result
138 0 : SDNode *getNode() const { return Node; }
139 :
140 : /// set the SDNode
141 13701717 : void setNode(SDNode *N) { Node = N; }
142 :
143 0 : inline SDNode *operator->() const { return Node; }
144 :
145 0 : bool operator==(const SDValue &O) const {
146 391559025 : return Node == O.Node && ResNo == O.ResNo;
147 : }
148 : bool operator!=(const SDValue &O) const {
149 7856875 : 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 0 : explicit operator bool() const {
155 1613 : return Node != nullptr;
156 : }
157 :
158 0 : SDValue getValue(unsigned R) const {
159 0 : 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 23371769 : return getValueType().getSimpleVT();
171 : }
172 :
173 : /// Returns the size of the value in bits.
174 5922230 : unsigned getValueSizeInBits() const {
175 11844460 : return getValueType().getSizeInBits();
176 : }
177 :
178 48654278 : unsigned getScalarValueSizeInBits() const {
179 145962834 : 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 198626920 : return ((unsigned)((uintptr_t)Val.getNode() >> 4) ^
228 99311525 : (unsigned)((uintptr_t)Val.getNode() >> 9)) + Val.getResNo();
229 : }
230 :
231 : static bool isEqual(const SDValue &LHS, const SDValue &RHS) {
232 205385437 : 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 548206 : 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 42591180 : 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 12967885 : 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 20397236 : operator const SDValue&() const { return Val; }
276 :
277 : /// If implicit conversion to SDValue doesn't work, the get() method returns
278 : /// the SDValue.
279 33094658 : const SDValue &get() const { return Val; }
280 :
281 : /// This returns the SDNode that contains this Use.
282 0 : SDNode *getUser() { return User; }
283 :
284 : /// Get the next SDUse in the use list.
285 0 : SDUse *getNext() const { return Next; }
286 :
287 : /// Convenience function for get().getNode().
288 129587016 : SDNode *getNode() const { return Val.getNode(); }
289 : /// Convenience function for get().getResNo().
290 193693815 : 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 139 : 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 151087112 : 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 169649863 : Next = *List;
329 96700982 : if (Next) Next->Prev = &Next;
330 169649863 : Prev = List;
331 163369995 : *List = this;
332 : }
333 :
334 0 : void removeFromList() {
335 90572405 : *Prev = Next;
336 31529578 : if (Next) Next->Prev = Prev;
337 0 : }
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 105986867 : : 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 22747664 : AllowReassociation(false) {}
380 :
381 : /// Propagate the fast-math-flags from an IR FPMathOperator.
382 157065 : 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 157065 : }
391 :
392 : /// Sets the state of the flags to the defined state.
393 5668923 : void setDefined() { AnyDefined = true; }
394 : /// Returns true if the flags are in a defined state.
395 852880 : bool isDefined() const { return AnyDefined; }
396 :
397 : // These are mutators for each flag.
398 : void setNoUnsignedWrap(bool b) {
399 : setDefined();
400 5491929 : NoUnsignedWrap = b;
401 : }
402 : void setNoSignedWrap(bool b) {
403 : setDefined();
404 391677 : NoSignedWrap = b;
405 : }
406 : void setExact(bool b) {
407 : setDefined();
408 41186 : Exact = b;
409 : }
410 : void setNoNaNs(bool b) {
411 : setDefined();
412 157084 : NoNaNs = b;
413 : }
414 : void setNoInfs(bool b) {
415 : setDefined();
416 157084 : NoInfs = b;
417 : }
418 : void setNoSignedZeros(bool b) {
419 : setDefined();
420 157065 : NoSignedZeros = b;
421 : }
422 : void setAllowReciprocal(bool b) {
423 : setDefined();
424 157065 : AllowReciprocal = b;
425 : }
426 : void setVectorReduction(bool b) {
427 : setDefined();
428 143 : VectorReduction = b;
429 : }
430 : void setAllowContract(bool b) {
431 : setDefined();
432 157065 : AllowContract = b;
433 : }
434 : void setApproximateFuncs(bool b) {
435 : setDefined();
436 157065 : ApproximateFuncs = b;
437 : }
438 : void setAllowReassociation(bool b) {
439 : setDefined();
440 157094 : 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 4018534 : 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 852880 : void intersectWith(const SDNodeFlags Flags) {
464 852880 : if (!Flags.isDefined())
465 : return;
466 131709 : NoUnsignedWrap &= Flags.NoUnsignedWrap;
467 131709 : NoSignedWrap &= Flags.NoSignedWrap;
468 131709 : Exact &= Flags.Exact;
469 131709 : NoNaNs &= Flags.NoNaNs;
470 131709 : NoInfs &= Flags.NoInfs;
471 131709 : NoSignedZeros &= Flags.NoSignedZeros;
472 131709 : AllowReciprocal &= Flags.AllowReciprocal;
473 131709 : VectorReduction &= Flags.VectorReduction;
474 131709 : AllowContract &= Flags.AllowContract;
475 131709 : ApproximateFuncs &= Flags.ApproximateFuncs;
476 131709 : 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 1140900941 : 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 365818 : 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 0 : bool isTargetMemoryOpcode() const {
635 0 : return NodeType >= ISD::FIRST_TARGET_MEMORY_OPCODE;
636 : }
637 :
638 : /// Return true if the type of the node type undefined.
639 1007 : 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 0 : bool isMemIntrinsic() const {
647 1089414 : return (NodeType == ISD::INTRINSIC_W_CHAIN ||
648 1089414 : NodeType == ISD::INTRINSIC_VOID) &&
649 12412 : SDNodeBits.IsMemIntrinsic;
650 : }
651 :
652 : /// Test if this node is a strict floating point pseudo-op.
653 0 : bool isStrictFPOpcode() {
654 29783819 : switch (NodeType) {
655 : default:
656 : return false;
657 0 : 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 0 : return true;
676 : }
677 : }
678 :
679 : /// Test if this node has a post-isel opcode, directly
680 : /// corresponding to a MachineInstr opcode.
681 0 : 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 0 : unsigned getMachineOpcode() const {
687 : assert(isMachineOpcode() && "Not a MachineInstr opcode!");
688 91891032 : return ~NodeType;
689 : }
690 :
691 15571156 : bool getHasDebugValue() const { return SDNodeBits.HasDebugValue; }
692 68449 : void setHasDebugValue(bool b) { SDNodeBits.HasDebugValue = b; }
693 :
694 131798334 : bool isDivergent() const { return SDNodeBits.IsDivergent; }
695 :
696 : /// Return true if there are no uses of this node.
697 0 : 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 24777592 : 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 2022 : size_t use_size() const { return std::distance(use_begin(), use_end()); }
707 :
708 : /// Return the unique node id.
709 0 : int getNodeId() const { return NodeId; }
710 :
711 : /// Set unique node id.
712 462459199 : void setNodeId(int Id) { NodeId = Id; }
713 :
714 : /// Return the node ordering.
715 0 : unsigned getIROrder() const { return IROrder; }
716 :
717 : /// Set the node ordering.
718 114053 : void setIROrder(unsigned Order) { IROrder = Order; }
719 :
720 : /// Return the source location info.
721 17117144 : 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 6192816 : 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 7078165 : use_iterator(const use_iterator &I) : Op(I.Op) {}
745 :
746 0 : bool operator==(const use_iterator &x) const {
747 365799 : return Op == x.Op;
748 : }
749 : bool operator!=(const use_iterator &x) const {
750 41129931 : 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 348606459 : Op = Op->getNext();
760 : return *this;
761 : }
762 :
763 0 : use_iterator operator++(int) { // Postincrement
764 0 : use_iterator tmp = *this; ++*this; return tmp;
765 : }
766 :
767 : /// Retrieve a pointer to the current user node.
768 0 : SDNode *operator*() const {
769 : assert(Op && "Cannot dereference end iterator!");
770 299716614 : return Op->getUser();
771 : }
772 :
773 : SDNode *operator->() const { return operator*(); }
774 :
775 0 : SDUse &getUse() const { return *Op; }
776 :
777 : /// Retrieve the operand # of this use in its user.
778 0 : unsigned getOperandNo() const {
779 : assert(Op && "Cannot dereference end iterator!");
780 1809242 : return (unsigned)(Op - Op->getUser()->OperandList);
781 : }
782 : };
783 :
784 : /// Provide iteration support to walk over all uses of an SDNode.
785 0 : use_iterator use_begin() const {
786 0 : 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 27606683 : return make_range(use_begin(), use_end());
793 : }
794 : inline iterator_range<use_iterator> uses() const {
795 3559 : 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 2086 : 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 551126 : 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 551126 : 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 550558 : int NId = N->getNodeId();
855 : // If we Invalidated the Id, reconstruct original NId.
856 550558 : if (NId < -1)
857 1114 : NId = -(NId + 1);
858 :
859 : bool Found = false;
860 2188611 : while (!Worklist.empty()) {
861 1642995 : const SDNode *M = Worklist.pop_back_val();
862 1642995 : int MId = M->getNodeId();
863 1541830 : if (TopologicalPrune && M->getOpcode() != ISD::TokenFactor && (NId > 0) &&
864 3164023 : (MId > 0) && (MId < NId)) {
865 1326433 : DeferredNodes.push_back(M);
866 1326433 : continue;
867 : }
868 970559 : for (const SDValue &OpV : M->op_values()) {
869 653997 : SDNode *Op = OpV.getNode();
870 653997 : if (Visited.insert(Op).second)
871 538576 : Worklist.push_back(Op);
872 653997 : if (Op == N)
873 : Found = true;
874 : }
875 316562 : if (Found)
876 : break;
877 311620 : if (MaxSteps != 0 && Visited.size() >= MaxSteps)
878 : break;
879 : }
880 : // Push deferred nodes back on worklist.
881 550558 : Worklist.append(DeferredNodes.begin(), DeferredNodes.end());
882 : // If we bailed early, conservatively return found.
883 550558 : if (MaxSteps != 0 && Visited.size() >= MaxSteps)
884 0 : 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 137487441 : 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 0 : const SDValue &getOperand(unsigned Num) const {
899 : assert(Num < NumOperands && "Invalid child # of SDNode!");
900 300943632 : return OperandList[Num];
901 : }
902 :
903 : using op_iterator = SDUse *;
904 :
905 0 : op_iterator op_begin() const { return OperandList; }
906 63909251 : op_iterator op_end() const { return OperandList+NumOperands; }
907 101217187 : 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 0 : 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 166082391 : value_op_iterator(op_end()));
924 : }
925 :
926 0 : SDVTList getVTList() const {
927 242321 : SDVTList X = { ValueList, NumValues };
928 0 : 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 83871322 : if (getNumOperands() != 0 &&
935 165591788 : 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 10104605 : for (use_iterator UI = use_begin(), UE = use_end(); UI != UE; ++UI)
944 6999374 : if (UI.getUse().get().getValueType() == MVT::Glue)
945 : return *UI;
946 : return nullptr;
947 : }
948 :
949 16797990 : const SDNodeFlags getFlags() const { return Flags; }
950 12194959 : 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 152129591 : unsigned getNumValues() const { return NumValues; }
959 :
960 : /// Return the type of a specified result.
961 0 : EVT getValueType(unsigned ResNo) const {
962 : assert(ResNo < NumValues && "Illegal result number!");
963 278101103 : return ValueList[ResNo];
964 : }
965 :
966 : /// Return the type of a specified result as a simple type.
967 : MVT getSimpleValueType(unsigned ResNo) const {
968 43446860 : return getValueType(ResNo).getSimpleVT();
969 : }
970 :
971 : /// Returns MVT::getSizeInBits(getValueType(ResNo)).
972 : unsigned getValueSizeInBits(unsigned ResNo) const {
973 2472105 : return getValueType(ResNo).getSizeInBits();
974 : }
975 :
976 : using value_iterator = const EVT *;
977 :
978 0 : value_iterator value_begin() const { return ValueList; }
979 39724940 : 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 18970900 : void addUse(SDUse &U) { U.addToList(&UseList); }
1041 :
1042 : protected:
1043 : static SDVTList getSDVTList(EVT VT) {
1044 10104751 : 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 76552311 : SDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs)
1053 76552311 : : NodeType(Opc), ValueList(VTs.VTs), NumValues(VTs.NumVTs),
1054 76552311 : IROrder(Order), debugLoc(std::move(dl)) {
1055 76552311 : 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 76552311 : }
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 22517071 : class SDLoc {
1075 : private:
1076 : DebugLoc DL;
1077 : int IROrder = 0;
1078 :
1079 : public:
1080 1005206 : SDLoc() = default;
1081 159382857 : SDLoc(const SDNode *N) : DL(N->getDebugLoc()), IROrder(N->getIROrder()) {}
1082 : SDLoc(const SDValue V) : SDLoc(V.getNode()) {}
1083 18676021 : SDLoc(const Instruction *I, int Order) : IROrder(Order) {
1084 : assert(Order >= 0 && "bad IROrder");
1085 18676021 : if (I)
1086 : DL = I->getDebugLoc();
1087 : }
1088 :
1089 65523399 : unsigned getIROrder() const { return IROrder; }
1090 34797854 : const DebugLoc &getDebugLoc() const { return DL; }
1091 : };
1092 :
1093 : // Define inline functions from the SDValue class.
1094 :
1095 52954097 : inline SDValue::SDValue(SDNode *node, unsigned resno)
1096 74330724 : : 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 0 : inline unsigned SDValue::getOpcode() const {
1106 240398785 : return Node->getOpcode();
1107 : }
1108 :
1109 0 : inline EVT SDValue::getValueType() const {
1110 699488165 : return Node->getValueType(ResNo);
1111 : }
1112 :
1113 0 : inline unsigned SDValue::getNumOperands() const {
1114 147437781 : return Node->getNumOperands();
1115 : }
1116 :
1117 0 : inline const SDValue &SDValue::getOperand(unsigned i) const {
1118 164848939 : return Node->getOperand(i);
1119 : }
1120 :
1121 0 : inline uint64_t SDValue::getConstantOperandVal(unsigned i) const {
1122 0 : 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 0 : inline bool SDValue::isMachineOpcode() const {
1134 54653109 : return Node->isMachineOpcode();
1135 : }
1136 :
1137 0 : inline unsigned SDValue::getMachineOpcode() const {
1138 0 : return Node->getMachineOpcode();
1139 : }
1140 :
1141 0 : inline bool SDValue::isUndef() const {
1142 49961644 : return Node->isUndef();
1143 : }
1144 :
1145 0 : inline bool SDValue::use_empty() const {
1146 708124 : return !Node->hasAnyUseOfValue(ResNo);
1147 : }
1148 :
1149 0 : inline bool SDValue::hasOneUse() const {
1150 19181420 : return Node->hasNUsesOfValue(1, ResNo);
1151 : }
1152 :
1153 0 : inline const DebugLoc &SDValue::getDebugLoc() const {
1154 0 : 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 88049131 : if (Val.getNode()) removeFromList();
1177 78289522 : Val = V;
1178 9759609 : if (V.getNode()) V.getNode()->addUse(*this);
1179 : }
1180 :
1181 : inline void SDUse::setInitial(const SDValue &V) {
1182 157366980 : Val = V;
1183 151087112 : V.getNode()->addUse(*this);
1184 : }
1185 :
1186 : inline void SDUse::setNode(SDNode *N) {
1187 2523274 : if (Val.getNode()) removeFromList();
1188 : Val.setNode(N);
1189 2523274 : 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 12967884 : explicit HandleSDNode(SDValue X)
1201 12967884 : : 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 12967885 : 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 12967885 : NumOperands = 1;
1213 12967885 : OperandList = &Op;
1214 12967885 : }
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 0 : unsigned getSrcAddressSpace() const { return SrcAddrSpace; }
1230 0 : unsigned getDestAddressSpace() const { return DestAddrSpace; }
1231 :
1232 : static bool classof(const SDNode *N) {
1233 0 : 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 0 : bool readMem() const { return MMO->isLoad(); }
1252 2 : bool writeMem() const { return MMO->isStore(); }
1253 :
1254 : /// Returns alignment and volatility of the memory access
1255 0 : unsigned getOriginalAlignment() const {
1256 23848 : return MMO->getBaseAlignment();
1257 : }
1258 0 : unsigned getAlignment() const {
1259 35239981 : 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 17325119 : memcpy(&RawSDNodeBits, &this->RawSDNodeBits, sizeof(this->RawSDNodeBits));
1275 17325119 : SDNodeBits.HasDebugValue = 0;
1276 17325119 : SDNodeBits.IsDivergent = false;
1277 17360 : memcpy(&Data, &RawSDNodeBits, sizeof(RawSDNodeBits));
1278 10486856 : return Data;
1279 : }
1280 :
1281 33575629 : bool isVolatile() const { return MemSDNodeBits.IsVolatile; }
1282 2512082 : bool isNonTemporal() const { return MemSDNodeBits.IsNonTemporal; }
1283 16186 : bool isDereferenceable() const { return MemSDNodeBits.IsDereferenceable; }
1284 35903 : bool isInvariant() const { return MemSDNodeBits.IsInvariant; }
1285 :
1286 : // Returns the offset from the location of the access.
1287 36984 : int64_t getSrcValueOffset() const { return MMO->getOffset(); }
1288 :
1289 : /// Returns the AA info that describes the dereference.
1290 0 : AAMDNodes getAAInfo() const { return MMO->getAAInfo(); }
1291 :
1292 : /// Returns the Ranges that describes the dereference.
1293 5596957 : 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 0 : AtomicOrdering getOrdering() const { return MMO->getOrdering(); }
1302 :
1303 : /// Return the type of the in-memory value.
1304 0 : EVT getMemoryVT() const { return MemoryVT; }
1305 :
1306 : /// Return a MachineMemOperand object describing the memory
1307 : /// reference performed by operation.
1308 0 : MachineMemOperand *getMemOperand() const { return MMO; }
1309 :
1310 0 : const MachinePointerInfo &getPointerInfo() const {
1311 0 : return MMO->getPointerInfo();
1312 : }
1313 :
1314 : /// Return the address space for the associated pointer
1315 : unsigned getAddressSpace() const {
1316 44722806 : 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 0 : void refineAlignment(const MachineMemOperand *NewMMO) {
1324 167741 : MMO->refineAlignment(NewMMO);
1325 0 : }
1326 :
1327 67974330 : const SDValue &getChain() const { return getOperand(0); }
1328 : const SDValue &getBasePtr() const {
1329 24794605 : return getOperand(getOpcode() == ISD::STORE ? 2 : 1);
1330 : }
1331 :
1332 : // Methods to support isa and dyn_cast
1333 15594307 : 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 8477497 : return N->getOpcode() == ISD::LOAD ||
1337 1113226 : N->getOpcode() == ISD::STORE ||
1338 1112689 : N->getOpcode() == ISD::PREFETCH ||
1339 1112247 : N->getOpcode() == ISD::ATOMIC_CMP_SWAP ||
1340 1110899 : N->getOpcode() == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS ||
1341 1107980 : N->getOpcode() == ISD::ATOMIC_SWAP ||
1342 1103955 : N->getOpcode() == ISD::ATOMIC_LOAD_ADD ||
1343 1103165 : N->getOpcode() == ISD::ATOMIC_LOAD_SUB ||
1344 1102604 : N->getOpcode() == ISD::ATOMIC_LOAD_AND ||
1345 1102428 : N->getOpcode() == ISD::ATOMIC_LOAD_CLR ||
1346 1101727 : N->getOpcode() == ISD::ATOMIC_LOAD_OR ||
1347 1101035 : N->getOpcode() == ISD::ATOMIC_LOAD_XOR ||
1348 1100931 : N->getOpcode() == ISD::ATOMIC_LOAD_NAND ||
1349 1100341 : N->getOpcode() == ISD::ATOMIC_LOAD_MIN ||
1350 1099762 : N->getOpcode() == ISD::ATOMIC_LOAD_MAX ||
1351 1099189 : N->getOpcode() == ISD::ATOMIC_LOAD_UMIN ||
1352 1098616 : N->getOpcode() == ISD::ATOMIC_LOAD_UMAX ||
1353 1092101 : N->getOpcode() == ISD::ATOMIC_LOAD ||
1354 1090276 : N->getOpcode() == ISD::ATOMIC_STORE ||
1355 1089769 : N->getOpcode() == ISD::MLOAD ||
1356 1089414 : N->getOpcode() == ISD::MSTORE ||
1357 1089414 : N->getOpcode() == ISD::MGATHER ||
1358 : N->getOpcode() == ISD::MSCATTER ||
1359 16672715 : N->isMemIntrinsic() ||
1360 15594307 : 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 0 : : MemSDNode(Opc, Order, dl, VTL, MemVT, MMO) {}
1370 :
1371 1754 : const SDValue &getBasePtr() const { return getOperand(1); }
1372 40 : 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 578881 : static bool classof(const SDNode *N) {
1391 578848 : return N->getOpcode() == ISD::ATOMIC_CMP_SWAP ||
1392 578848 : N->getOpcode() == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS ||
1393 578678 : N->getOpcode() == ISD::ATOMIC_SWAP ||
1394 578446 : N->getOpcode() == ISD::ATOMIC_LOAD_ADD ||
1395 578252 : N->getOpcode() == ISD::ATOMIC_LOAD_SUB ||
1396 578134 : N->getOpcode() == ISD::ATOMIC_LOAD_AND ||
1397 578134 : N->getOpcode() == ISD::ATOMIC_LOAD_CLR ||
1398 578016 : N->getOpcode() == ISD::ATOMIC_LOAD_OR ||
1399 577898 : N->getOpcode() == ISD::ATOMIC_LOAD_XOR ||
1400 577898 : N->getOpcode() == ISD::ATOMIC_LOAD_NAND ||
1401 577780 : N->getOpcode() == ISD::ATOMIC_LOAD_MIN ||
1402 577660 : N->getOpcode() == ISD::ATOMIC_LOAD_MAX ||
1403 577542 : N->getOpcode() == ISD::ATOMIC_LOAD_UMIN ||
1404 577424 : N->getOpcode() == ISD::ATOMIC_LOAD_UMAX ||
1405 1156171 : N->getOpcode() == ISD::ATOMIC_LOAD ||
1406 578881 : 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 16718 : : MemSDNode(Opc, Order, dl, VTs, MemoryVT, MMO) {
1419 16718 : 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 0 : return N->isMemIntrinsic() ||
1427 0 : 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 107045 : ShuffleVectorSDNode(EVT VT, unsigned Order, const DebugLoc &dl, const int *M)
1449 107813 : : SDNode(ISD::VECTOR_SHUFFLE, Order, dl, getSDVTList(VT)), Mask(M) {}
1450 :
1451 : public:
1452 380579 : ArrayRef<int> getMask() const {
1453 380579 : EVT VT = getValueType(0);
1454 380579 : return makeArrayRef(Mask, VT.getVectorNumElements());
1455 : }
1456 :
1457 0 : int getMaskElt(unsigned Idx) const {
1458 : assert(Idx < getValueType(0).getVectorNumElements() && "Idx out of range!");
1459 2696571 : return Mask[Idx];
1460 : }
1461 :
1462 77841 : bool isSplat() const { return isSplatMask(Mask, getValueType(0)); }
1463 :
1464 17355 : int getSplatIndex() const {
1465 : assert(isSplat() && "Cannot get splat index for non-splat!");
1466 17355 : EVT VT = getValueType(0);
1467 18392 : for (unsigned i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
1468 18392 : if (Mask[i] >= 0)
1469 17355 : return Mask[i];
1470 : }
1471 0 : 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 1228 : unsigned NumElems = Mask.size();
1480 2662298 : for (unsigned i = 0; i != NumElems; ++i) {
1481 2474619 : int idx = Mask[i];
1482 2474619 : if (idx < 0)
1483 : continue;
1484 2140550 : else if (idx < (int)NumElems)
1485 1318234 : Mask[i] = idx + NumElems;
1486 : else
1487 822316 : Mask[i] = idx - NumElems;
1488 : }
1489 : }
1490 :
1491 : static bool classof(const SDNode *N) {
1492 1395945 : 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 8294258 : ConstantSDNode(bool isTarget, bool isOpaque, const ConstantInt *val, EVT VT)
1502 24882774 : : SDNode(isTarget ? ISD::TargetConstant : ISD::Constant, 0, DebugLoc(),
1503 : getSDVTList(VT)),
1504 12399540 : Value(val) {
1505 8294258 : ConstantSDNodeBits.IsOpaque = isOpaque;
1506 8294258 : }
1507 :
1508 : public:
1509 0 : const ConstantInt *getConstantIntValue() const { return Value; }
1510 0 : const APInt &getAPIntValue() const { return Value->getValue(); }
1511 0 : uint64_t getZExtValue() const { return Value->getZExtValue(); }
1512 0 : int64_t getSExtValue() const { return Value->getSExtValue(); }
1513 0 : uint64_t getLimitedValue(uint64_t Limit = UINT64_MAX) {
1514 0 : return Value->getLimitedValue(Limit);
1515 : }
1516 :
1517 0 : bool isOne() const { return Value->isOne(); }
1518 0 : bool isNullValue() const { return Value->isZero(); }
1519 0 : bool isAllOnesValue() const { return Value->isMinusOne(); }
1520 :
1521 31312559 : bool isOpaque() const { return ConstantSDNodeBits.IsOpaque; }
1522 :
1523 : static bool classof(const SDNode *N) {
1524 338856461 : return N->getOpcode() == ISD::Constant ||
1525 : N->getOpcode() == ISD::TargetConstant;
1526 : }
1527 : };
1528 :
1529 : uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
1530 630420 : return cast<ConstantSDNode>(getOperand(Num))->getZExtValue();
1531 : }
1532 :
1533 : class ConstantFPSDNode : public SDNode {
1534 : friend class SelectionDAG;
1535 :
1536 : const ConstantFP *Value;
1537 :
1538 36713 : ConstantFPSDNode(bool isTarget, const ConstantFP *val, EVT VT)
1539 36713 : : SDNode(isTarget ? ISD::TargetConstantFP : ISD::ConstantFP, 0,
1540 73426 : DebugLoc(), getSDVTList(VT)),
1541 72186 : Value(val) {}
1542 :
1543 : public:
1544 0 : const APFloat& getValueAPF() const { return Value->getValueAPF(); }
1545 0 : const ConstantFP *getConstantFPValue() const { return Value; }
1546 :
1547 : /// Return true if the value is positive or negative zero.
1548 0 : bool isZero() const { return Value->isZero(); }
1549 :
1550 : /// Return true if the value is a NaN.
1551 0 : bool isNaN() const { return Value->isNaN(); }
1552 :
1553 : /// Return true if the value is an infinity
1554 0 : bool isInfinity() const { return Value->isInfinity(); }
1555 :
1556 : /// Return true if the value is negative.
1557 0 : 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 0 : bool isExactlyValue(double V) const {
1568 14446 : 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 191178154 : 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 : /// Return the non-bitcasted source operand of \p V if it exists.
1593 : /// If \p V is not a bitcasted value, it is returned as-is.
1594 : SDValue peekThroughBitcasts(SDValue V);
1595 :
1596 : /// Return the non-bitcasted and one-use source operand of \p V if it exists.
1597 : /// If \p V is not a bitcasted one-use value, it is returned as-is.
1598 : SDValue peekThroughOneUseBitcasts(SDValue V);
1599 :
1600 : /// Returns true if \p V is a bitwise not operation. Assumes that an all ones
1601 : /// constant is canonicalized to be operand 1.
1602 : bool isBitwiseNot(SDValue V);
1603 :
1604 : /// Returns the SDNode if it is a constant splat BuildVector or constant int.
1605 : ConstantSDNode *isConstOrConstSplat(SDValue N, bool AllowUndefs = false);
1606 :
1607 : /// Returns the SDNode if it is a constant splat BuildVector or constant float.
1608 : ConstantFPSDNode *isConstOrConstSplatFP(SDValue N, bool AllowUndefs = false);
1609 :
1610 : class GlobalAddressSDNode : public SDNode {
1611 : friend class SelectionDAG;
1612 :
1613 : const GlobalValue *TheGlobal;
1614 : int64_t Offset;
1615 : unsigned char TargetFlags;
1616 :
1617 : GlobalAddressSDNode(unsigned Opc, unsigned Order, const DebugLoc &DL,
1618 : const GlobalValue *GA, EVT VT, int64_t o,
1619 : unsigned char TF);
1620 :
1621 : public:
1622 0 : const GlobalValue *getGlobal() const { return TheGlobal; }
1623 0 : int64_t getOffset() const { return Offset; }
1624 0 : unsigned char getTargetFlags() const { return TargetFlags; }
1625 : // Return the address space this GlobalAddress belongs to.
1626 : unsigned getAddressSpace() const;
1627 :
1628 : static bool classof(const SDNode *N) {
1629 113616372 : return N->getOpcode() == ISD::GlobalAddress ||
1630 106263271 : N->getOpcode() == ISD::TargetGlobalAddress ||
1631 226352535 : N->getOpcode() == ISD::GlobalTLSAddress ||
1632 : N->getOpcode() == ISD::TargetGlobalTLSAddress;
1633 : }
1634 : };
1635 :
1636 : class FrameIndexSDNode : public SDNode {
1637 : friend class SelectionDAG;
1638 :
1639 : int FI;
1640 :
1641 5104461 : FrameIndexSDNode(int fi, EVT VT, bool isTarg)
1642 5104461 : : SDNode(isTarg ? ISD::TargetFrameIndex : ISD::FrameIndex,
1643 7662404 : 0, DebugLoc(), getSDVTList(VT)), FI(fi) {
1644 5104461 : }
1645 :
1646 : public:
1647 0 : int getIndex() const { return FI; }
1648 :
1649 : static bool classof(const SDNode *N) {
1650 80891347 : return N->getOpcode() == ISD::FrameIndex ||
1651 : N->getOpcode() == ISD::TargetFrameIndex;
1652 : }
1653 : };
1654 :
1655 : class JumpTableSDNode : public SDNode {
1656 : friend class SelectionDAG;
1657 :
1658 : int JTI;
1659 : unsigned char TargetFlags;
1660 :
1661 9497 : JumpTableSDNode(int jti, EVT VT, bool isTarg, unsigned char TF)
1662 9497 : : SDNode(isTarg ? ISD::TargetJumpTable : ISD::JumpTable,
1663 12696 : 0, DebugLoc(), getSDVTList(VT)), JTI(jti), TargetFlags(TF) {
1664 9497 : }
1665 :
1666 : public:
1667 0 : int getIndex() const { return JTI; }
1668 0 : unsigned char getTargetFlags() const { return TargetFlags; }
1669 :
1670 : static bool classof(const SDNode *N) {
1671 56931353 : return N->getOpcode() == ISD::JumpTable ||
1672 : N->getOpcode() == ISD::TargetJumpTable;
1673 : }
1674 : };
1675 :
1676 : class ConstantPoolSDNode : public SDNode {
1677 : friend class SelectionDAG;
1678 :
1679 : union {
1680 : const Constant *ConstVal;
1681 : MachineConstantPoolValue *MachineCPVal;
1682 : } Val;
1683 : int Offset; // It's a MachineConstantPoolValue if top bit is set.
1684 : unsigned Alignment; // Minimum alignment requirement of CP (not log2 value).
1685 : unsigned char TargetFlags;
1686 :
1687 94341 : ConstantPoolSDNode(bool isTarget, const Constant *c, EVT VT, int o,
1688 : unsigned Align, unsigned char TF)
1689 94341 : : SDNode(isTarget ? ISD::TargetConstantPool : ISD::ConstantPool, 0,
1690 188682 : DebugLoc(), getSDVTList(VT)), Offset(o), Alignment(Align),
1691 128611 : TargetFlags(TF) {
1692 : assert(Offset >= 0 && "Offset is too large");
1693 94341 : Val.ConstVal = c;
1694 94341 : }
1695 :
1696 265 : ConstantPoolSDNode(bool isTarget, MachineConstantPoolValue *v,
1697 : EVT VT, int o, unsigned Align, unsigned char TF)
1698 265 : : SDNode(isTarget ? ISD::TargetConstantPool : ISD::ConstantPool, 0,
1699 530 : DebugLoc(), getSDVTList(VT)), Offset(o), Alignment(Align),
1700 282 : TargetFlags(TF) {
1701 : assert(Offset >= 0 && "Offset is too large");
1702 265 : Val.MachineCPVal = v;
1703 265 : Offset |= 1 << (sizeof(unsigned)*CHAR_BIT-1);
1704 265 : }
1705 :
1706 : public:
1707 0 : bool isMachineConstantPoolEntry() const {
1708 0 : return Offset < 0;
1709 : }
1710 :
1711 0 : const Constant *getConstVal() const {
1712 : assert(!isMachineConstantPoolEntry() && "Wrong constantpool type");
1713 0 : return Val.ConstVal;
1714 : }
1715 :
1716 0 : MachineConstantPoolValue *getMachineCPVal() const {
1717 : assert(isMachineConstantPoolEntry() && "Wrong constantpool type");
1718 0 : return Val.MachineCPVal;
1719 : }
1720 :
1721 0 : int getOffset() const {
1722 101250 : return Offset & ~(1 << (sizeof(unsigned)*CHAR_BIT-1));
1723 : }
1724 :
1725 : // Return the alignment of this constant pool object, which is either 0 (for
1726 : // default alignment) or the desired value.
1727 0 : unsigned getAlignment() const { return Alignment; }
1728 0 : unsigned char getTargetFlags() const { return TargetFlags; }
1729 :
1730 : Type *getType() const;
1731 :
1732 : static bool classof(const SDNode *N) {
1733 62608667 : return N->getOpcode() == ISD::ConstantPool ||
1734 : N->getOpcode() == ISD::TargetConstantPool;
1735 : }
1736 : };
1737 :
1738 : /// Completely target-dependent object reference.
1739 : class TargetIndexSDNode : public SDNode {
1740 : friend class SelectionDAG;
1741 :
1742 : unsigned char TargetFlags;
1743 : int Index;
1744 : int64_t Offset;
1745 :
1746 : public:
1747 0 : TargetIndexSDNode(int Idx, EVT VT, int64_t Ofs, unsigned char TF)
1748 0 : : SDNode(ISD::TargetIndex, 0, DebugLoc(), getSDVTList(VT)),
1749 0 : TargetFlags(TF), Index(Idx), Offset(Ofs) {}
1750 :
1751 0 : unsigned char getTargetFlags() const { return TargetFlags; }
1752 0 : int getIndex() const { return Index; }
1753 0 : int64_t getOffset() const { return Offset; }
1754 :
1755 : static bool classof(const SDNode *N) {
1756 0 : return N->getOpcode() == ISD::TargetIndex;
1757 : }
1758 : };
1759 :
1760 : class BasicBlockSDNode : public SDNode {
1761 : friend class SelectionDAG;
1762 :
1763 : MachineBasicBlock *MBB;
1764 :
1765 : /// Debug info is meaningful and potentially useful here, but we create
1766 : /// blocks out of order when they're jumped to, which makes it a bit
1767 : /// harder. Let's see if we need it first.
1768 725447 : explicit BasicBlockSDNode(MachineBasicBlock *mbb)
1769 725447 : : SDNode(ISD::BasicBlock, 0, DebugLoc(), getSDVTList(MVT::Other)), MBB(mbb)
1770 725447 : {}
1771 :
1772 : public:
1773 0 : MachineBasicBlock *getBasicBlock() const { return MBB; }
1774 :
1775 : static bool classof(const SDNode *N) {
1776 0 : return N->getOpcode() == ISD::BasicBlock;
1777 : }
1778 : };
1779 :
1780 : /// A "pseudo-class" with methods for operating on BUILD_VECTORs.
1781 : class BuildVectorSDNode : public SDNode {
1782 : public:
1783 : // These are constructed as SDNodes and then cast to BuildVectorSDNodes.
1784 : explicit BuildVectorSDNode() = delete;
1785 :
1786 : /// Check if this is a constant splat, and if so, find the
1787 : /// smallest element size that splats the vector. If MinSplatBits is
1788 : /// nonzero, the element size must be at least that large. Note that the
1789 : /// splat element may be the entire vector (i.e., a one element vector).
1790 : /// Returns the splat element value in SplatValue. Any undefined bits in
1791 : /// that value are zero, and the corresponding bits in the SplatUndef mask
1792 : /// are set. The SplatBitSize value is set to the splat element size in
1793 : /// bits. HasAnyUndefs is set to true if any bits in the vector are
1794 : /// undefined. isBigEndian describes the endianness of the target.
1795 : bool isConstantSplat(APInt &SplatValue, APInt &SplatUndef,
1796 : unsigned &SplatBitSize, bool &HasAnyUndefs,
1797 : unsigned MinSplatBits = 0,
1798 : bool isBigEndian = false) const;
1799 :
1800 : /// Returns the splatted value or a null value if this is not a splat.
1801 : ///
1802 : /// If passed a non-null UndefElements bitvector, it will resize it to match
1803 : /// the vector width and set the bits where elements are undef.
1804 : SDValue getSplatValue(BitVector *UndefElements = nullptr) const;
1805 :
1806 : /// Returns the splatted constant or null if this is not a constant
1807 : /// 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 : ConstantSDNode *
1812 : getConstantSplatNode(BitVector *UndefElements = nullptr) const;
1813 :
1814 : /// Returns the splatted constant FP or null if this is not a constant
1815 : /// FP splat.
1816 : ///
1817 : /// If passed a non-null UndefElements bitvector, it will resize it to match
1818 : /// the vector width and set the bits where elements are undef.
1819 : ConstantFPSDNode *
1820 : getConstantFPSplatNode(BitVector *UndefElements = nullptr) const;
1821 :
1822 : /// If this is a constant FP splat and the splatted constant FP is an
1823 : /// exact power or 2, return the log base 2 integer value. Otherwise,
1824 : /// return -1.
1825 : ///
1826 : /// The BitWidth specifies the necessary bit precision.
1827 : int32_t getConstantFPSplatPow2ToLog2Int(BitVector *UndefElements,
1828 : uint32_t BitWidth) const;
1829 :
1830 : bool isConstant() const;
1831 :
1832 : static bool classof(const SDNode *N) {
1833 26372404 : return N->getOpcode() == ISD::BUILD_VECTOR;
1834 : }
1835 : };
1836 :
1837 : /// An SDNode that holds an arbitrary LLVM IR Value. This is
1838 : /// used when the SelectionDAG needs to make a simple reference to something
1839 : /// in the LLVM IR representation.
1840 : ///
1841 : class SrcValueSDNode : public SDNode {
1842 : friend class SelectionDAG;
1843 :
1844 : const Value *V;
1845 :
1846 : /// Create a SrcValue for a general value.
1847 511 : explicit SrcValueSDNode(const Value *v)
1848 511 : : SDNode(ISD::SRCVALUE, 0, DebugLoc(), getSDVTList(MVT::Other)), V(v) {}
1849 :
1850 : public:
1851 : /// Return the contained Value.
1852 0 : const Value *getValue() const { return V; }
1853 :
1854 : static bool classof(const SDNode *N) {
1855 0 : return N->getOpcode() == ISD::SRCVALUE;
1856 : }
1857 : };
1858 :
1859 : class MDNodeSDNode : public SDNode {
1860 : friend class SelectionDAG;
1861 :
1862 : const MDNode *MD;
1863 :
1864 17390 : explicit MDNodeSDNode(const MDNode *md)
1865 17390 : : SDNode(ISD::MDNODE_SDNODE, 0, DebugLoc(), getSDVTList(MVT::Other)), MD(md)
1866 17390 : {}
1867 :
1868 : public:
1869 0 : const MDNode *getMD() const { return MD; }
1870 :
1871 : static bool classof(const SDNode *N) {
1872 432 : return N->getOpcode() == ISD::MDNODE_SDNODE;
1873 : }
1874 : };
1875 :
1876 : class RegisterSDNode : public SDNode {
1877 : friend class SelectionDAG;
1878 :
1879 : unsigned Reg;
1880 :
1881 6726947 : RegisterSDNode(unsigned reg, EVT VT)
1882 6726947 : : SDNode(ISD::Register, 0, DebugLoc(), getSDVTList(VT)), Reg(reg) {}
1883 :
1884 : public:
1885 0 : unsigned getReg() const { return Reg; }
1886 :
1887 : static bool classof(const SDNode *N) {
1888 10455179 : return N->getOpcode() == ISD::Register;
1889 : }
1890 : };
1891 :
1892 : class RegisterMaskSDNode : public SDNode {
1893 : friend class SelectionDAG;
1894 :
1895 : // The memory for RegMask is not owned by the node.
1896 : const uint32_t *RegMask;
1897 :
1898 591888 : RegisterMaskSDNode(const uint32_t *mask)
1899 1775664 : : SDNode(ISD::RegisterMask, 0, DebugLoc(), getSDVTList(MVT::Untyped)),
1900 591888 : RegMask(mask) {}
1901 :
1902 : public:
1903 0 : const uint32_t *getRegMask() const { return RegMask; }
1904 :
1905 : static bool classof(const SDNode *N) {
1906 12827937 : return N->getOpcode() == ISD::RegisterMask;
1907 : }
1908 : };
1909 :
1910 : class BlockAddressSDNode : public SDNode {
1911 : friend class SelectionDAG;
1912 :
1913 : const BlockAddress *BA;
1914 : int64_t Offset;
1915 : unsigned char TargetFlags;
1916 :
1917 478 : BlockAddressSDNode(unsigned NodeTy, EVT VT, const BlockAddress *ba,
1918 : int64_t o, unsigned char Flags)
1919 1434 : : SDNode(NodeTy, 0, DebugLoc(), getSDVTList(VT)),
1920 478 : BA(ba), Offset(o), TargetFlags(Flags) {}
1921 :
1922 : public:
1923 0 : const BlockAddress *getBlockAddress() const { return BA; }
1924 0 : int64_t getOffset() const { return Offset; }
1925 0 : unsigned char getTargetFlags() const { return TargetFlags; }
1926 :
1927 : static bool classof(const SDNode *N) {
1928 56813083 : return N->getOpcode() == ISD::BlockAddress ||
1929 : N->getOpcode() == ISD::TargetBlockAddress;
1930 : }
1931 : };
1932 :
1933 : class LabelSDNode : public SDNode {
1934 : friend class SelectionDAG;
1935 :
1936 : MCSymbol *Label;
1937 :
1938 993979 : LabelSDNode(unsigned Order, const DebugLoc &dl, MCSymbol *L)
1939 1079424 : : SDNode(ISD::EH_LABEL, Order, dl, getSDVTList(MVT::Other)), Label(L) {}
1940 :
1941 : public:
1942 0 : MCSymbol *getLabel() const { return Label; }
1943 :
1944 : static bool classof(const SDNode *N) {
1945 : return N->getOpcode() == ISD::EH_LABEL ||
1946 : N->getOpcode() == ISD::ANNOTATION_LABEL;
1947 : }
1948 : };
1949 :
1950 : class ExternalSymbolSDNode : public SDNode {
1951 : friend class SelectionDAG;
1952 :
1953 : const char *Symbol;
1954 : unsigned char TargetFlags;
1955 :
1956 35407 : ExternalSymbolSDNode(bool isTarget, const char *Sym, unsigned char TF, EVT VT)
1957 35407 : : SDNode(isTarget ? ISD::TargetExternalSymbol : ISD::ExternalSymbol,
1958 47556 : 0, DebugLoc(), getSDVTList(VT)), Symbol(Sym), TargetFlags(TF) {}
1959 :
1960 : public:
1961 0 : const char *getSymbol() const { return Symbol; }
1962 0 : unsigned char getTargetFlags() const { return TargetFlags; }
1963 :
1964 : static bool classof(const SDNode *N) {
1965 56931209 : return N->getOpcode() == ISD::ExternalSymbol ||
1966 : N->getOpcode() == ISD::TargetExternalSymbol;
1967 : }
1968 : };
1969 :
1970 : class MCSymbolSDNode : public SDNode {
1971 : friend class SelectionDAG;
1972 :
1973 : MCSymbol *Symbol;
1974 :
1975 57 : MCSymbolSDNode(MCSymbol *Symbol, EVT VT)
1976 57 : : SDNode(ISD::MCSymbol, 0, DebugLoc(), getSDVTList(VT)), Symbol(Symbol) {}
1977 :
1978 : public:
1979 0 : MCSymbol *getMCSymbol() const { return Symbol; }
1980 :
1981 : static bool classof(const SDNode *N) {
1982 17 : return N->getOpcode() == ISD::MCSymbol;
1983 : }
1984 : };
1985 :
1986 : class CondCodeSDNode : public SDNode {
1987 : friend class SelectionDAG;
1988 :
1989 : ISD::CondCode Condition;
1990 :
1991 187885 : explicit CondCodeSDNode(ISD::CondCode Cond)
1992 563655 : : SDNode(ISD::CONDCODE, 0, DebugLoc(), getSDVTList(MVT::Other)),
1993 187885 : Condition(Cond) {}
1994 :
1995 : public:
1996 0 : ISD::CondCode get() const { return Condition; }
1997 :
1998 : static bool classof(const SDNode *N) {
1999 : return N->getOpcode() == ISD::CONDCODE;
2000 : }
2001 : };
2002 :
2003 : /// This class is used to represent EVT's, which are used
2004 : /// to parameterize some operations.
2005 : class VTSDNode : public SDNode {
2006 : friend class SelectionDAG;
2007 :
2008 : EVT ValueType;
2009 :
2010 92967 : explicit VTSDNode(EVT VT)
2011 278901 : : SDNode(ISD::VALUETYPE, 0, DebugLoc(), getSDVTList(MVT::Other)),
2012 92967 : ValueType(VT) {}
2013 :
2014 : public:
2015 0 : EVT getVT() const { return ValueType; }
2016 :
2017 : static bool classof(const SDNode *N) {
2018 6 : return N->getOpcode() == ISD::VALUETYPE;
2019 : }
2020 : };
2021 :
2022 : /// Base class for LoadSDNode and StoreSDNode
2023 : class LSBaseSDNode : public MemSDNode {
2024 : public:
2025 : LSBaseSDNode(ISD::NodeType NodeTy, unsigned Order, const DebugLoc &dl,
2026 : SDVTList VTs, ISD::MemIndexedMode AM, EVT MemVT,
2027 : MachineMemOperand *MMO)
2028 13471131 : : MemSDNode(NodeTy, Order, dl, VTs, MemVT, MMO) {
2029 13471131 : LSBaseSDNodeBits.AddressingMode = AM;
2030 : assert(getAddressingMode() == AM && "Value truncated");
2031 : }
2032 :
2033 : const SDValue &getOffset() const {
2034 12381 : return getOperand(getOpcode() == ISD::LOAD ? 2 : 3);
2035 : }
2036 :
2037 : /// Return the addressing mode for this load or store:
2038 : /// unindexed, pre-inc, pre-dec, post-inc, or post-dec.
2039 : ISD::MemIndexedMode getAddressingMode() const {
2040 69301956 : return static_cast<ISD::MemIndexedMode>(LSBaseSDNodeBits.AddressingMode);
2041 : }
2042 :
2043 : /// Return true if this is a pre/post inc/dec load/store.
2044 : bool isIndexed() const { return getAddressingMode() != ISD::UNINDEXED; }
2045 :
2046 : /// Return true if this is NOT a pre/post inc/dec load/store.
2047 : bool isUnindexed() const { return getAddressingMode() == ISD::UNINDEXED; }
2048 :
2049 : static bool classof(const SDNode *N) {
2050 4716 : return N->getOpcode() == ISD::LOAD ||
2051 : N->getOpcode() == ISD::STORE;
2052 : }
2053 : };
2054 :
2055 : /// This class is used to represent ISD::LOAD nodes.
2056 : class LoadSDNode : public LSBaseSDNode {
2057 : friend class SelectionDAG;
2058 :
2059 : LoadSDNode(unsigned Order, const DebugLoc &dl, SDVTList VTs,
2060 : ISD::MemIndexedMode AM, ISD::LoadExtType ETy, EVT MemVT,
2061 : MachineMemOperand *MMO)
2062 6475349 : : LSBaseSDNode(ISD::LOAD, Order, dl, VTs, AM, MemVT, MMO) {
2063 3316856 : LoadSDNodeBits.ExtTy = ETy;
2064 : assert(readMem() && "Load MachineMemOperand is not a load!");
2065 : assert(!writeMem() && "Load MachineMemOperand is a store!");
2066 : }
2067 :
2068 : public:
2069 : /// Return whether this is a plain node,
2070 : /// or one of the varieties of value-extending loads.
2071 : ISD::LoadExtType getExtensionType() const {
2072 28010527 : return static_cast<ISD::LoadExtType>(LoadSDNodeBits.ExtTy);
2073 : }
2074 :
2075 2665473 : const SDValue &getBasePtr() const { return getOperand(1); }
2076 4315 : const SDValue &getOffset() const { return getOperand(2); }
2077 :
2078 : static bool classof(const SDNode *N) {
2079 41744684 : return N->getOpcode() == ISD::LOAD;
2080 : }
2081 : };
2082 :
2083 : /// This class is used to represent ISD::STORE nodes.
2084 : class StoreSDNode : public LSBaseSDNode {
2085 : friend class SelectionDAG;
2086 :
2087 : StoreSDNode(unsigned Order, const DebugLoc &dl, SDVTList VTs,
2088 : ISD::MemIndexedMode AM, bool isTrunc, EVT MemVT,
2089 : MachineMemOperand *MMO)
2090 6995782 : : LSBaseSDNode(ISD::STORE, Order, dl, VTs, AM, MemVT, MMO) {
2091 3502420 : StoreSDNodeBits.IsTruncating = isTrunc;
2092 : assert(!readMem() && "Store MachineMemOperand is a load!");
2093 : assert(writeMem() && "Store MachineMemOperand is not a store!");
2094 : }
2095 :
2096 : public:
2097 : /// Return true if the op does a truncation before store.
2098 : /// For integers this is the same as doing a TRUNCATE and storing the result.
2099 : /// For floats, it is the same as doing an FP_ROUND and storing the result.
2100 34369372 : bool isTruncatingStore() const { return StoreSDNodeBits.IsTruncating; }
2101 : void setTruncatingStore(bool Truncating) {
2102 213 : StoreSDNodeBits.IsTruncating = Truncating;
2103 : }
2104 :
2105 28532726 : const SDValue &getValue() const { return getOperand(1); }
2106 1601577 : const SDValue &getBasePtr() const { return getOperand(2); }
2107 0 : const SDValue &getOffset() const { return getOperand(3); }
2108 :
2109 : static bool classof(const SDNode *N) {
2110 25185435 : return N->getOpcode() == ISD::STORE;
2111 : }
2112 : };
2113 :
2114 : /// This base class is used to represent MLOAD and MSTORE nodes
2115 : class MaskedLoadStoreSDNode : public MemSDNode {
2116 : public:
2117 : friend class SelectionDAG;
2118 :
2119 : MaskedLoadStoreSDNode(ISD::NodeType NodeTy, unsigned Order,
2120 : const DebugLoc &dl, SDVTList VTs, EVT MemVT,
2121 : MachineMemOperand *MMO)
2122 1972 : : MemSDNode(NodeTy, Order, dl, VTs, MemVT, MMO) {}
2123 :
2124 : // MaskedLoadSDNode (Chain, ptr, mask, passthru)
2125 : // MaskedStoreSDNode (Chain, data, ptr, mask)
2126 : // Mask is a vector of i1 elements
2127 : const SDValue &getBasePtr() const {
2128 75 : return getOperand(getOpcode() == ISD::MLOAD ? 1 : 2);
2129 : }
2130 : const SDValue &getMask() const {
2131 1575 : return getOperand(getOpcode() == ISD::MLOAD ? 2 : 3);
2132 : }
2133 :
2134 : static bool classof(const SDNode *N) {
2135 : return N->getOpcode() == ISD::MLOAD ||
2136 : N->getOpcode() == ISD::MSTORE;
2137 : }
2138 : };
2139 :
2140 : /// This class is used to represent an MLOAD node
2141 : class MaskedLoadSDNode : public MaskedLoadStoreSDNode {
2142 : public:
2143 : friend class SelectionDAG;
2144 :
2145 : MaskedLoadSDNode(unsigned Order, const DebugLoc &dl, SDVTList VTs,
2146 : ISD::LoadExtType ETy, bool IsExpanding, EVT MemVT,
2147 : MachineMemOperand *MMO)
2148 1224 : : MaskedLoadStoreSDNode(ISD::MLOAD, Order, dl, VTs, MemVT, MMO) {
2149 1224 : LoadSDNodeBits.ExtTy = ETy;
2150 612 : LoadSDNodeBits.IsExpanding = IsExpanding;
2151 : }
2152 :
2153 : ISD::LoadExtType getExtensionType() const {
2154 2205 : return static_cast<ISD::LoadExtType>(LoadSDNodeBits.ExtTy);
2155 : }
2156 :
2157 24 : const SDValue &getBasePtr() const { return getOperand(1); }
2158 803 : const SDValue &getMask() const { return getOperand(2); }
2159 101 : const SDValue &getPassThru() const { return getOperand(3); }
2160 :
2161 : static bool classof(const SDNode *N) {
2162 569 : return N->getOpcode() == ISD::MLOAD;
2163 : }
2164 :
2165 2836 : bool isExpandingLoad() const { return LoadSDNodeBits.IsExpanding; }
2166 : };
2167 :
2168 : /// This class is used to represent an MSTORE node
2169 : class MaskedStoreSDNode : public MaskedLoadStoreSDNode {
2170 : public:
2171 : friend class SelectionDAG;
2172 :
2173 : MaskedStoreSDNode(unsigned Order, const DebugLoc &dl, SDVTList VTs,
2174 : bool isTrunc, bool isCompressing, EVT MemVT,
2175 : MachineMemOperand *MMO)
2176 748 : : MaskedLoadStoreSDNode(ISD::MSTORE, Order, dl, VTs, MemVT, MMO) {
2177 748 : StoreSDNodeBits.IsTruncating = isTrunc;
2178 374 : StoreSDNodeBits.IsCompressing = isCompressing;
2179 : }
2180 :
2181 : /// Return true if the op does a truncation before store.
2182 : /// For integers this is the same as doing a TRUNCATE and storing the result.
2183 : /// For floats, it is the same as doing an FP_ROUND and storing the result.
2184 575 : bool isTruncatingStore() const { return StoreSDNodeBits.IsTruncating; }
2185 :
2186 : /// Returns true if the op does a compression to the vector before storing.
2187 : /// The node contiguously stores the active elements (integers or floats)
2188 : /// in src (those with their respective bit set in writemask k) to unaligned
2189 : /// memory at base_addr.
2190 571 : bool isCompressingStore() const { return StoreSDNodeBits.IsCompressing; }
2191 :
2192 676 : const SDValue &getValue() const { return getOperand(1); }
2193 14 : const SDValue &getBasePtr() const { return getOperand(2); }
2194 323 : const SDValue &getMask() const { return getOperand(3); }
2195 :
2196 : static bool classof(const SDNode *N) {
2197 313 : return N->getOpcode() == ISD::MSTORE;
2198 : }
2199 : };
2200 :
2201 : /// This is a base class used to represent
2202 : /// MGATHER and MSCATTER nodes
2203 : ///
2204 : class MaskedGatherScatterSDNode : public MemSDNode {
2205 : public:
2206 : friend class SelectionDAG;
2207 :
2208 : MaskedGatherScatterSDNode(ISD::NodeType NodeTy, unsigned Order,
2209 : const DebugLoc &dl, SDVTList VTs, EVT MemVT,
2210 : MachineMemOperand *MMO)
2211 1272 : : MemSDNode(NodeTy, Order, dl, VTs, MemVT, MMO) {}
2212 :
2213 : // In the both nodes address is Op1, mask is Op2:
2214 : // MaskedGatherSDNode (Chain, passthru, mask, base, index, scale)
2215 : // MaskedScatterSDNode (Chain, value, mask, base, index, scale)
2216 : // Mask is a vector of i1 elements
2217 : const SDValue &getBasePtr() const { return getOperand(3); }
2218 76 : const SDValue &getIndex() const { return getOperand(4); }
2219 625 : const SDValue &getMask() const { return getOperand(2); }
2220 178 : const SDValue &getScale() const { return getOperand(5); }
2221 :
2222 : static bool classof(const SDNode *N) {
2223 : return N->getOpcode() == ISD::MGATHER ||
2224 : N->getOpcode() == ISD::MSCATTER;
2225 : }
2226 : };
2227 :
2228 : /// This class is used to represent an MGATHER node
2229 : ///
2230 : class MaskedGatherSDNode : public MaskedGatherScatterSDNode {
2231 : public:
2232 : friend class SelectionDAG;
2233 :
2234 : MaskedGatherSDNode(unsigned Order, const DebugLoc &dl, SDVTList VTs,
2235 : EVT MemVT, MachineMemOperand *MMO)
2236 473 : : MaskedGatherScatterSDNode(ISD::MGATHER, Order, dl, VTs, MemVT, MMO) {}
2237 :
2238 57 : const SDValue &getPassThru() const { return getOperand(1); }
2239 :
2240 : static bool classof(const SDNode *N) {
2241 : return N->getOpcode() == ISD::MGATHER;
2242 : }
2243 : };
2244 :
2245 : /// This class is used to represent an MSCATTER node
2246 : ///
2247 : class MaskedScatterSDNode : public MaskedGatherScatterSDNode {
2248 : public:
2249 : friend class SelectionDAG;
2250 :
2251 : MaskedScatterSDNode(unsigned Order, const DebugLoc &dl, SDVTList VTs,
2252 : EVT MemVT, MachineMemOperand *MMO)
2253 168 : : MaskedGatherScatterSDNode(ISD::MSCATTER, Order, dl, VTs, MemVT, MMO) {}
2254 :
2255 267 : const SDValue &getValue() const { return getOperand(1); }
2256 :
2257 : static bool classof(const SDNode *N) {
2258 : return N->getOpcode() == ISD::MSCATTER;
2259 : }
2260 : };
2261 :
2262 : /// An SDNode that represents everything that will be needed
2263 : /// to construct a MachineInstr. These nodes are created during the
2264 : /// instruction selection proper phase.
2265 : ///
2266 : /// Note that the only supported way to set the `memoperands` is by calling the
2267 : /// `SelectionDAG::setNodeMemRefs` function as the memory management happens
2268 : /// inside the DAG rather than in the node.
2269 : class MachineSDNode : public SDNode {
2270 : private:
2271 : friend class SelectionDAG;
2272 :
2273 564037 : MachineSDNode(unsigned Opc, unsigned Order, const DebugLoc &DL, SDVTList VTs)
2274 778193 : : SDNode(Opc, Order, DL, VTs) {}
2275 :
2276 : // We use a pointer union between a single `MachineMemOperand` pointer and
2277 : // a pointer to an array of `MachineMemOperand` pointers. This is null when
2278 : // the number of these is zero, the single pointer variant used when the
2279 : // number is one, and the array is used for larger numbers.
2280 : //
2281 : // The array is allocated via the `SelectionDAG`'s allocator and so will
2282 : // always live until the DAG is cleaned up and doesn't require ownership here.
2283 : //
2284 : // We can't use something simpler like `TinyPtrVector` here because `SDNode`
2285 : // subclasses aren't managed in a conforming C++ manner. See the comments on
2286 : // `SelectionDAG::MorphNodeTo` which details what all goes on, but the
2287 : // constraint here is that these don't manage memory with their constructor or
2288 : // destructor and can be initialized to a good state even if they start off
2289 : // uninitialized.
2290 : PointerUnion<MachineMemOperand *, MachineMemOperand **> MemRefs = {};
2291 :
2292 : // Note that this could be folded into the above `MemRefs` member if doing so
2293 : // is advantageous at some point. We don't need to store this in most cases.
2294 : // However, at the moment this doesn't appear to make the allocation any
2295 : // smaller and makes the code somewhat simpler to read.
2296 : int NumMemRefs = 0;
2297 :
2298 : public:
2299 : using mmo_iterator = ArrayRef<MachineMemOperand *>::const_iterator;
2300 :
2301 : ArrayRef<MachineMemOperand *> memoperands() const {
2302 : // Special case the common cases.
2303 11795582 : if (NumMemRefs == 0)
2304 : return {};
2305 5281859 : if (NumMemRefs == 1)
2306 : return makeArrayRef(MemRefs.getAddrOfPtr1(), 1);
2307 :
2308 : // Otherwise we have an actual array.
2309 333206 : return makeArrayRef(MemRefs.get<MachineMemOperand **>(), NumMemRefs);
2310 : }
2311 : mmo_iterator memoperands_begin() const { return memoperands().begin(); }
2312 : mmo_iterator memoperands_end() const { return memoperands().end(); }
2313 0 : bool memoperands_empty() const { return memoperands().empty(); }
2314 :
2315 : /// Clear out the memory reference descriptor list.
2316 : void clearMemRefs() {
2317 : MemRefs = nullptr;
2318 11789592 : NumMemRefs = 0;
2319 : }
2320 :
2321 : static bool classof(const SDNode *N) {
2322 13267878 : return N->isMachineOpcode();
2323 : }
2324 : };
2325 :
2326 : class SDNodeIterator : public std::iterator<std::forward_iterator_tag,
2327 : SDNode, ptrdiff_t> {
2328 : const SDNode *Node;
2329 : unsigned Operand;
2330 :
2331 : SDNodeIterator(const SDNode *N, unsigned Op) : Node(N), Operand(Op) {}
2332 :
2333 : public:
2334 0 : bool operator==(const SDNodeIterator& x) const {
2335 0 : return Operand == x.Operand;
2336 : }
2337 : bool operator!=(const SDNodeIterator& x) const { return !operator==(x); }
2338 :
2339 0 : pointer operator*() const {
2340 15586 : return Node->getOperand(Operand).getNode();
2341 : }
2342 : pointer operator->() const { return operator*(); }
2343 :
2344 : SDNodeIterator& operator++() { // Preincrement
2345 15562 : ++Operand;
2346 : return *this;
2347 : }
2348 : SDNodeIterator operator++(int) { // Postincrement
2349 : SDNodeIterator tmp = *this; ++*this; return tmp;
2350 : }
2351 : size_t operator-(SDNodeIterator Other) const {
2352 : assert(Node == Other.Node &&
2353 : "Cannot compare iterators of two different nodes!");
2354 : return Operand - Other.Operand;
2355 : }
2356 :
2357 : static SDNodeIterator begin(const SDNode *N) { return SDNodeIterator(N, 0); }
2358 : static SDNodeIterator end (const SDNode *N) {
2359 8608 : return SDNodeIterator(N, N->getNumOperands());
2360 : }
2361 :
2362 : unsigned getOperand() const { return Operand; }
2363 : const SDNode *getNode() const { return Node; }
2364 : };
2365 :
2366 : template <> struct GraphTraits<SDNode*> {
2367 : using NodeRef = SDNode *;
2368 : using ChildIteratorType = SDNodeIterator;
2369 :
2370 : static NodeRef getEntryNode(SDNode *N) { return N; }
2371 :
2372 : static ChildIteratorType child_begin(NodeRef N) {
2373 : return SDNodeIterator::begin(N);
2374 : }
2375 :
2376 : static ChildIteratorType child_end(NodeRef N) {
2377 : return SDNodeIterator::end(N);
2378 : }
2379 : };
2380 :
2381 : /// A representation of the largest SDNode, for use in sizeof().
2382 : ///
2383 : /// This needs to be a union because the largest node differs on 32 bit systems
2384 : /// with 4 and 8 byte pointer alignment, respectively.
2385 : using LargestSDNode = AlignedCharArrayUnion<AtomicSDNode, TargetIndexSDNode,
2386 : BlockAddressSDNode,
2387 : GlobalAddressSDNode>;
2388 :
2389 : /// The SDNode class with the greatest alignment requirement.
2390 : using MostAlignedSDNode = GlobalAddressSDNode;
2391 :
2392 : namespace ISD {
2393 :
2394 : /// Returns true if the specified node is a non-extending and unindexed load.
2395 : inline bool isNormalLoad(const SDNode *N) {
2396 : const LoadSDNode *Ld = dyn_cast<LoadSDNode>(N);
2397 5169701 : return Ld && Ld->getExtensionType() == ISD::NON_EXTLOAD &&
2398 : Ld->getAddressingMode() == ISD::UNINDEXED;
2399 : }
2400 :
2401 : /// Returns true if the specified node is a non-extending load.
2402 : inline bool isNON_EXTLoad(const SDNode *N) {
2403 290145 : return isa<LoadSDNode>(N) &&
2404 : cast<LoadSDNode>(N)->getExtensionType() == ISD::NON_EXTLOAD;
2405 : }
2406 :
2407 : /// Returns true if the specified node is a EXTLOAD.
2408 : inline bool isEXTLoad(const SDNode *N) {
2409 438253 : return isa<LoadSDNode>(N) &&
2410 : cast<LoadSDNode>(N)->getExtensionType() == ISD::EXTLOAD;
2411 : }
2412 :
2413 : /// Returns true if the specified node is a SEXTLOAD.
2414 : inline bool isSEXTLoad(const SDNode *N) {
2415 285145 : return isa<LoadSDNode>(N) &&
2416 : cast<LoadSDNode>(N)->getExtensionType() == ISD::SEXTLOAD;
2417 : }
2418 :
2419 : /// Returns true if the specified node is a ZEXTLOAD.
2420 : inline bool isZEXTLoad(const SDNode *N) {
2421 5986057 : return isa<LoadSDNode>(N) &&
2422 : cast<LoadSDNode>(N)->getExtensionType() == ISD::ZEXTLOAD;
2423 : }
2424 :
2425 : /// Returns true if the specified node is an unindexed load.
2426 : inline bool isUNINDEXEDLoad(const SDNode *N) {
2427 3450324 : return isa<LoadSDNode>(N) &&
2428 : cast<LoadSDNode>(N)->getAddressingMode() == ISD::UNINDEXED;
2429 : }
2430 :
2431 : /// Returns true if the specified node is a non-truncating
2432 : /// and unindexed store.
2433 : inline bool isNormalStore(const SDNode *N) {
2434 : const StoreSDNode *St = dyn_cast<StoreSDNode>(N);
2435 8071191 : return St && !St->isTruncatingStore() &&
2436 : St->getAddressingMode() == ISD::UNINDEXED;
2437 : }
2438 :
2439 : /// Returns true if the specified node is a non-truncating store.
2440 : inline bool isNON_TRUNCStore(const SDNode *N) {
2441 : return isa<StoreSDNode>(N) && !cast<StoreSDNode>(N)->isTruncatingStore();
2442 : }
2443 :
2444 : /// Returns true if the specified node is a truncating store.
2445 : inline bool isTRUNCStore(const SDNode *N) {
2446 : return isa<StoreSDNode>(N) && cast<StoreSDNode>(N)->isTruncatingStore();
2447 : }
2448 :
2449 : /// Returns true if the specified node is an unindexed store.
2450 : inline bool isUNINDEXEDStore(const SDNode *N) {
2451 : return isa<StoreSDNode>(N) &&
2452 : cast<StoreSDNode>(N)->getAddressingMode() == ISD::UNINDEXED;
2453 : }
2454 :
2455 : /// Return true if the node is a math/logic binary operator. This corresponds
2456 : /// to the IR function of the same name.
2457 : inline bool isBinaryOp(const SDNode *N) {
2458 : auto Op = N->getOpcode();
2459 : return (Op == ISD::ADD || Op == ISD::SUB || Op == ISD::MUL ||
2460 : Op == ISD::AND || Op == ISD::OR || Op == ISD::XOR ||
2461 : Op == ISD::SHL || Op == ISD::SRL || Op == ISD::SRA ||
2462 : Op == ISD::SDIV || Op == ISD::UDIV || Op == ISD::SREM ||
2463 : Op == ISD::UREM || Op == ISD::FADD || Op == ISD::FSUB ||
2464 : Op == ISD::FMUL || Op == ISD::FDIV || Op == ISD::FREM);
2465 : }
2466 :
2467 : /// Attempt to match a unary predicate against a scalar/splat constant or
2468 : /// every element of a constant BUILD_VECTOR.
2469 : bool matchUnaryPredicate(SDValue Op,
2470 : std::function<bool(ConstantSDNode *)> Match);
2471 :
2472 : /// Attempt to match a binary predicate against a pair of scalar/splat
2473 : /// constants or every element of a pair of constant BUILD_VECTORs.
2474 : bool matchBinaryPredicate(
2475 : SDValue LHS, SDValue RHS,
2476 : std::function<bool(ConstantSDNode *, ConstantSDNode *)> Match);
2477 :
2478 : } // end namespace ISD
2479 :
2480 : } // end namespace llvm
2481 :
2482 : #endif // LLVM_CODEGEN_SELECTIONDAGNODES_H
|
