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