1	//===- llvm/CodeGen/SelectionDAG.h - InstSelection DAG ----------*- 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 SelectionDAG class, and transitively defines the
10	// SDNode class and subclasses.
11	//
12	//===----------------------------------------------------------------------===//
13
14	#ifndef LLVM_CODEGEN_SELECTIONDAG_H
15	#define LLVM_CODEGEN_SELECTIONDAG_H
16
17	#include "llvm/ADT/APFloat.h"
18	#include "llvm/ADT/APInt.h"
19	#include "llvm/ADT/ArrayRef.h"
20	#include "llvm/ADT/DenseMap.h"
21	#include "llvm/ADT/DenseSet.h"
22	#include "llvm/ADT/FoldingSet.h"
23	#include "llvm/ADT/SmallVector.h"
24	#include "llvm/ADT/StringMap.h"
25	#include "llvm/ADT/ilist.h"
26	#include "llvm/ADT/iterator.h"
27	#include "llvm/ADT/iterator_range.h"
28	#include "llvm/CodeGen/DAGCombine.h"
29	#include "llvm/CodeGen/ISDOpcodes.h"
30	#include "llvm/CodeGen/MachineFunction.h"
31	#include "llvm/CodeGen/MachineMemOperand.h"
32	#include "llvm/CodeGen/SelectionDAGNodes.h"
33	#include "llvm/CodeGen/ValueTypes.h"
34	#include "llvm/CodeGenTypes/MachineValueType.h"
35	#include "llvm/IR/DebugLoc.h"
36	#include "llvm/IR/Metadata.h"
37	#include "llvm/Support/Allocator.h"
38	#include "llvm/Support/ArrayRecycler.h"
39	#include "llvm/Support/CodeGen.h"
40	#include "llvm/Support/ErrorHandling.h"
41	#include "llvm/Support/RecyclingAllocator.h"
42	#include <cassert>
43	#include <cstdint>
44	#include <functional>
45	#include <map>
46	#include <string>
47	#include <tuple>
48	#include <utility>
49	#include <vector>
50
51	namespace llvm {
52
53	class DIExpression;
54	class DILabel;
55	class DIVariable;
56	class Function;
57	class Pass;
58	class Type;
59	template <class GraphType> struct GraphTraits;
60	template <typename T, unsigned int N> class SmallSetVector;
61	template <typename T, typename Enable> struct FoldingSetTrait;
62	class AAResults;
63	class BlockAddress;
64	class BlockFrequencyInfo;
65	class Constant;
66	class ConstantFP;
67	class ConstantInt;
68	class DataLayout;
69	struct fltSemantics;
70	class FunctionLoweringInfo;
71	class FunctionVarLocs;
72	class GlobalValue;
73	struct KnownBits;
74	class LLVMContext;
75	class MachineBasicBlock;
76	class MachineConstantPoolValue;
77	class MCSymbol;
78	class OptimizationRemarkEmitter;
79	class ProfileSummaryInfo;
80	class SDDbgValue;
81	class SDDbgOperand;
82	class SDDbgLabel;
83	class SelectionDAG;
84	class SelectionDAGTargetInfo;
85	class TargetLibraryInfo;
86	class TargetLowering;
87	class TargetMachine;
88	class TargetSubtargetInfo;
89	class Value;
90
91	template <typename T> class GenericSSAContext;
92	using SSAContext = GenericSSAContext<Function>;
93	template <typename T> class GenericUniformityInfo;
94	using UniformityInfo = GenericUniformityInfo<SSAContext>;
95
96	class SDVTListNode : public FoldingSetNode {
97	friend struct FoldingSetTrait<SDVTListNode>;
98
99	/// A reference to an Interned FoldingSetNodeID for this node.
100	/// The Allocator in SelectionDAG holds the data.
101	/// SDVTList contains all types which are frequently accessed in SelectionDAG.
102	/// The size of this list is not expected to be big so it won't introduce
103	/// a memory penalty.
104	FoldingSetNodeIDRef FastID;
105	const EVT *VTs;
106	unsigned int NumVTs;
107	/// The hash value for SDVTList is fixed, so cache it to avoid
108	/// hash calculation.
109	unsigned HashValue;
110
111	public:
112	SDVTListNode(const FoldingSetNodeIDRef ID, const EVT *VT, unsigned int Num) :
113	FastID(ID), VTs(VT), NumVTs(Num) {
114	HashValue = ID.ComputeHash();
115	}
116
117	SDVTList getSDVTList() {
118	SDVTList result = {.VTs: VTs, .NumVTs: NumVTs};
119	return result;
120	}
121	};
122
123	/// Specialize FoldingSetTrait for SDVTListNode
124	/// to avoid computing temp FoldingSetNodeID and hash value.
125	template<> struct FoldingSetTrait<SDVTListNode> : DefaultFoldingSetTrait<SDVTListNode> {
126	static void Profile(const SDVTListNode &X, FoldingSetNodeID& ID) {
127	ID = X.FastID;
128	}
129
130	static bool Equals(const SDVTListNode &X, const FoldingSetNodeID &ID,
131	unsigned IDHash, FoldingSetNodeID &TempID) {
132	if (X.HashValue != IDHash)
133	return false;
134	return ID == X.FastID;
135	}
136
137	static unsigned ComputeHash(const SDVTListNode &X, FoldingSetNodeID &TempID) {
138	return X.HashValue;
139	}
140	};
141
142	template <> struct ilist_alloc_traits<SDNode> {
143	static void deleteNode(SDNode *) {
144	llvm_unreachable("ilist_traits<SDNode> shouldn't see a deleteNode call!");
145	}
146	};
147
148	/// Keeps track of dbg_value information through SDISel. We do
149	/// not build SDNodes for these so as not to perturb the generated code;
150	/// instead the info is kept off to the side in this structure. Each SDNode may
151	/// have one or more associated dbg_value entries. This information is kept in
152	/// DbgValMap.
153	/// Byval parameters are handled separately because they don't use alloca's,
154	/// which busts the normal mechanism. There is good reason for handling all
155	/// parameters separately: they may not have code generated for them, they
156	/// should always go at the beginning of the function regardless of other code
157	/// motion, and debug info for them is potentially useful even if the parameter
158	/// is unused. Right now only byval parameters are handled separately.
159	class SDDbgInfo {
160	BumpPtrAllocator Alloc;
161	SmallVector<SDDbgValue*, 32> DbgValues;
162	SmallVector<SDDbgValue*, 32> ByvalParmDbgValues;
163	SmallVector<SDDbgLabel*, 4> DbgLabels;
164	using DbgValMapType = DenseMap<const SDNode *, SmallVector<SDDbgValue *, 2>>;
165	DbgValMapType DbgValMap;
166
167	public:
168	SDDbgInfo() = default;
169	SDDbgInfo(const SDDbgInfo &) = delete;
170	SDDbgInfo &operator=(const SDDbgInfo &) = delete;
171
172	void add(SDDbgValue *V, bool isParameter);
173
174	void add(SDDbgLabel *L) { DbgLabels.push_back(Elt: L); }
175
176	/// Invalidate all DbgValues attached to the node and remove
177	/// it from the Node-to-DbgValues map.
178	void erase(const SDNode *Node);
179
180	void clear() {
181	DbgValMap.clear();
182	DbgValues.clear();
183	ByvalParmDbgValues.clear();
184	DbgLabels.clear();
185	Alloc.Reset();
186	}
187
188	BumpPtrAllocator &getAlloc() { return Alloc; }
189
190	bool empty() const {
191	return DbgValues.empty() && ByvalParmDbgValues.empty() && DbgLabels.empty();
192	}
193
194	ArrayRef<SDDbgValue*> getSDDbgValues(const SDNode *Node) const {
195	auto I = DbgValMap.find(Val: Node);
196	if (I != DbgValMap.end())
197	return I->second;
198	return ArrayRef<SDDbgValue*>();
199	}
200
201	using DbgIterator = SmallVectorImpl<SDDbgValue*>::iterator;
202	using DbgLabelIterator = SmallVectorImpl<SDDbgLabel*>::iterator;
203
204	DbgIterator DbgBegin() { return DbgValues.begin(); }
205	DbgIterator DbgEnd() { return DbgValues.end(); }
206	DbgIterator ByvalParmDbgBegin() { return ByvalParmDbgValues.begin(); }
207	DbgIterator ByvalParmDbgEnd() { return ByvalParmDbgValues.end(); }
208	DbgLabelIterator DbgLabelBegin() { return DbgLabels.begin(); }
209	DbgLabelIterator DbgLabelEnd() { return DbgLabels.end(); }
210	};
211
212	void checkForCycles(const SelectionDAG *DAG, bool force = false);
213
214	/// This is used to represent a portion of an LLVM function in a low-level
215	/// Data Dependence DAG representation suitable for instruction selection.
216	/// This DAG is constructed as the first step of instruction selection in order
217	/// to allow implementation of machine specific optimizations
218	/// and code simplifications.
219	///
220	/// The representation used by the SelectionDAG is a target-independent
221	/// representation, which has some similarities to the GCC RTL representation,
222	/// but is significantly more simple, powerful, and is a graph form instead of a
223	/// linear form.
224	///
225	class SelectionDAG {
226	const TargetMachine &TM;
227	const SelectionDAGTargetInfo *TSI = nullptr;
228	const TargetLowering *TLI = nullptr;
229	const TargetLibraryInfo *LibInfo = nullptr;
230	const FunctionVarLocs *FnVarLocs = nullptr;
231	MachineFunction *MF;
232	Pass *SDAGISelPass = nullptr;
233	LLVMContext *Context;
234	CodeGenOptLevel OptLevel;
235
236	UniformityInfo *UA = nullptr;
237	FunctionLoweringInfo * FLI = nullptr;
238
239	/// The function-level optimization remark emitter. Used to emit remarks
240	/// whenever manipulating the DAG.
241	OptimizationRemarkEmitter *ORE;
242
243	ProfileSummaryInfo *PSI = nullptr;
244	BlockFrequencyInfo *BFI = nullptr;
245
246	/// List of non-single value types.
247	FoldingSet<SDVTListNode> VTListMap;
248
249	/// Pool allocation for misc. objects that are created once per SelectionDAG.
250	BumpPtrAllocator Allocator;
251
252	/// The starting token.
253	SDNode EntryNode;
254
255	/// The root of the entire DAG.
256	SDValue Root;
257
258	/// A linked list of nodes in the current DAG.
259	ilist<SDNode> AllNodes;
260
261	/// The AllocatorType for allocating SDNodes. We use
262	/// pool allocation with recycling.
263	using NodeAllocatorType = RecyclingAllocator<BumpPtrAllocator, SDNode,
264	sizeof(LargestSDNode),
265	alignof(MostAlignedSDNode)>;
266
267	/// Pool allocation for nodes.
268	NodeAllocatorType NodeAllocator;
269
270	/// This structure is used to memoize nodes, automatically performing
271	/// CSE with existing nodes when a duplicate is requested.
272	FoldingSet<SDNode> CSEMap;
273
274	/// Pool allocation for machine-opcode SDNode operands.
275	BumpPtrAllocator OperandAllocator;
276	ArrayRecycler<SDUse> OperandRecycler;
277
278	/// Tracks dbg_value and dbg_label information through SDISel.
279	SDDbgInfo *DbgInfo;
280
281	using CallSiteInfo = MachineFunction::CallSiteInfo;
282	using CallSiteInfoImpl = MachineFunction::CallSiteInfoImpl;
283
284	struct NodeExtraInfo {
285	CallSiteInfo CSInfo;
286	MDNode *HeapAllocSite = nullptr;
287	MDNode *PCSections = nullptr;
288	bool NoMerge = false;
289	};
290	/// Out-of-line extra information for SDNodes.
291	DenseMap<const SDNode *, NodeExtraInfo> SDEI;
292
293	/// PersistentId counter to be used when inserting the next
294	/// SDNode to this SelectionDAG. We do not place that under
295	/// `#if LLVM_ENABLE_ABI_BREAKING_CHECKS` intentionally because
296	/// it adds unneeded complexity without noticeable
297	/// benefits (see discussion with @thakis in D120714).
298	uint16_t NextPersistentId = 0;
299
300	public:
301	/// Clients of various APIs that cause global effects on
302	/// the DAG can optionally implement this interface. This allows the clients
303	/// to handle the various sorts of updates that happen.
304	///
305	/// A DAGUpdateListener automatically registers itself with DAG when it is
306	/// constructed, and removes itself when destroyed in RAII fashion.
307	struct DAGUpdateListener {
308	DAGUpdateListener *const Next;
309	SelectionDAG &DAG;
310
311	explicit DAGUpdateListener(SelectionDAG &D)
312	: Next(D.UpdateListeners), DAG(D) {
313	DAG.UpdateListeners = this;
314	}
315
316	virtual ~DAGUpdateListener() {
317	assert(DAG.UpdateListeners == this &&
318	"DAGUpdateListeners must be destroyed in LIFO order");
319	DAG.UpdateListeners = Next;
320	}
321
322	/// The node N that was deleted and, if E is not null, an
323	/// equivalent node E that replaced it.
324	virtual void NodeDeleted(SDNode *N, SDNode *E);
325
326	/// The node N that was updated.
327	virtual void NodeUpdated(SDNode *N);
328
329	/// The node N that was inserted.
330	virtual void NodeInserted(SDNode *N);
331	};
332
333	struct DAGNodeDeletedListener : public DAGUpdateListener {
334	std::function<void(SDNode *, SDNode *)> Callback;
335
336	DAGNodeDeletedListener(SelectionDAG &DAG,
337	std::function<void(SDNode *, SDNode *)> Callback)
338	: DAGUpdateListener(DAG), Callback(std::move(Callback)) {}
339
340	void NodeDeleted(SDNode *N, SDNode *E) override { Callback(N, E); }
341
342	private:
343	virtual void anchor();
344	};
345
346	struct DAGNodeInsertedListener : public DAGUpdateListener {
347	std::function<void(SDNode *)> Callback;
348
349	DAGNodeInsertedListener(SelectionDAG &DAG,
350	std::function<void(SDNode *)> Callback)
351	: DAGUpdateListener(DAG), Callback(std::move(Callback)) {}
352
353	void NodeInserted(SDNode *N) override { Callback(N); }
354
355	private:
356	virtual void anchor();
357	};
358
359	/// Help to insert SDNodeFlags automatically in transforming. Use
360	/// RAII to save and resume flags in current scope.
361	class FlagInserter {
362	SelectionDAG &DAG;
363	SDNodeFlags Flags;
364	FlagInserter *LastInserter;
365
366	public:
367	FlagInserter(SelectionDAG &SDAG, SDNodeFlags Flags)
368	: DAG(SDAG), Flags(Flags),
369	LastInserter(SDAG.getFlagInserter()) {
370	SDAG.setFlagInserter(this);
371	}
372	FlagInserter(SelectionDAG &SDAG, SDNode *N)
373	: FlagInserter(SDAG, N->getFlags()) {}
374
375	FlagInserter(const FlagInserter &) = delete;
376	FlagInserter &operator=(const FlagInserter &) = delete;
377	~FlagInserter() { DAG.setFlagInserter(LastInserter); }
378
379	SDNodeFlags getFlags() const { return Flags; }
380	};
381
382	/// When true, additional steps are taken to
383	/// ensure that getConstant() and similar functions return DAG nodes that
384	/// have legal types. This is important after type legalization since
385	/// any illegally typed nodes generated after this point will not experience
386	/// type legalization.
387	bool NewNodesMustHaveLegalTypes = false;
388
389	private:
390	/// DAGUpdateListener is a friend so it can manipulate the listener stack.
391	friend struct DAGUpdateListener;
392
393	/// Linked list of registered DAGUpdateListener instances.
394	/// This stack is maintained by DAGUpdateListener RAII.
395	DAGUpdateListener *UpdateListeners = nullptr;
396
397	/// Implementation of setSubgraphColor.
398	/// Return whether we had to truncate the search.
399	bool setSubgraphColorHelper(SDNode *N, const char *Color,
400	DenseSet<SDNode *> &visited,
401	int level, bool &printed);
402
403	template <typename SDNodeT, typename... ArgTypes>
404	SDNodeT *newSDNode(ArgTypes &&... Args) {
405	return new (NodeAllocator.template Allocate<SDNodeT>())
406	SDNodeT(std::forward<ArgTypes>(Args)...);
407	}
408
409	/// Build a synthetic SDNodeT with the given args and extract its subclass
410	/// data as an integer (e.g. for use in a folding set).
411	///
412	/// The args to this function are the same as the args to SDNodeT's
413	/// constructor, except the second arg (assumed to be a const DebugLoc&) is
414	/// omitted.
415	template <typename SDNodeT, typename... ArgTypes>
416	static uint16_t getSyntheticNodeSubclassData(unsigned IROrder,
417	ArgTypes &&... Args) {
418	// The compiler can reduce this expression to a constant iff we pass an
419	// empty DebugLoc. Thankfully, the debug location doesn't have any bearing
420	// on the subclass data.
421	return SDNodeT(IROrder, DebugLoc(), std::forward<ArgTypes>(Args)...)
422	.getRawSubclassData();
423	}
424
425	template <typename SDNodeTy>
426	static uint16_t getSyntheticNodeSubclassData(unsigned Opc, unsigned Order,
427	SDVTList VTs, EVT MemoryVT,
428	MachineMemOperand *MMO) {
429	return SDNodeTy(Opc, Order, DebugLoc(), VTs, MemoryVT, MMO)
430	.getRawSubclassData();
431	}
432
433	void createOperands(SDNode *Node, ArrayRef<SDValue> Vals);
434
435	void removeOperands(SDNode *Node) {
436	if (!Node->OperandList)
437	return;
438	OperandRecycler.deallocate(
439	Cap: ArrayRecycler<SDUse>::Capacity::get(N: Node->NumOperands),
440	Ptr: Node->OperandList);
441	Node->NumOperands = 0;
442	Node->OperandList = nullptr;
443	}
444	void CreateTopologicalOrder(std::vector<SDNode*>& Order);
445
446	public:
447	// Maximum depth for recursive analysis such as computeKnownBits, etc.
448	static constexpr unsigned MaxRecursionDepth = 6;
449
450	explicit SelectionDAG(const TargetMachine &TM, CodeGenOptLevel);
451	SelectionDAG(const SelectionDAG &) = delete;
452	SelectionDAG &operator=(const SelectionDAG &) = delete;
453	~SelectionDAG();
454
455	/// Prepare this SelectionDAG to process code in the given MachineFunction.
456	void init(MachineFunction &NewMF, OptimizationRemarkEmitter &NewORE,
457	Pass *PassPtr, const TargetLibraryInfo *LibraryInfo,
458	UniformityInfo *UA, ProfileSummaryInfo *PSIin,
459	BlockFrequencyInfo *BFIin, FunctionVarLocs const *FnVarLocs);
460
461	void setFunctionLoweringInfo(FunctionLoweringInfo * FuncInfo) {
462	FLI = FuncInfo;
463	}
464
465	/// Clear state and free memory necessary to make this
466	/// SelectionDAG ready to process a new block.
467	void clear();
468
469	MachineFunction &getMachineFunction() const { return *MF; }
470	const Pass *getPass() const { return SDAGISelPass; }
471
472	const DataLayout &getDataLayout() const { return MF->getDataLayout(); }
473	const TargetMachine &getTarget() const { return TM; }
474	const TargetSubtargetInfo &getSubtarget() const { return MF->getSubtarget(); }
475	template <typename STC> const STC &getSubtarget() const {
476	return MF->getSubtarget<STC>();
477	}
478	const TargetLowering &getTargetLoweringInfo() const { return *TLI; }
479	const TargetLibraryInfo &getLibInfo() const { return *LibInfo; }
480	const SelectionDAGTargetInfo &getSelectionDAGInfo() const { return *TSI; }
481	const UniformityInfo *getUniformityInfo() const { return UA; }
482	/// Returns the result of the AssignmentTrackingAnalysis pass if it's
483	/// available, otherwise return nullptr.
484	const FunctionVarLocs *getFunctionVarLocs() const { return FnVarLocs; }
485	LLVMContext *getContext() const { return Context; }
486	OptimizationRemarkEmitter &getORE() const { return *ORE; }
487	ProfileSummaryInfo *getPSI() const { return PSI; }
488	BlockFrequencyInfo *getBFI() const { return BFI; }
489
490	FlagInserter *getFlagInserter() { return Inserter; }
491	void setFlagInserter(FlagInserter *FI) { Inserter = FI; }
492
493	/// Just dump dot graph to a user-provided path and title.
494	/// This doesn't open the dot viewer program and
495	/// helps visualization when outside debugging session.
496	/// FileName expects absolute path. If provided
497	/// without any path separators then the file
498	/// will be created in the current directory.
499	/// Error will be emitted if the path is insane.
500	#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
501	LLVM_DUMP_METHOD void dumpDotGraph(const Twine &FileName, const Twine &Title);
502	#endif
503
504	/// Pop up a GraphViz/gv window with the DAG rendered using 'dot'.
505	void viewGraph(const std::string &Title);
506	void viewGraph();
507
508	#if LLVM_ENABLE_ABI_BREAKING_CHECKS
509	std::map<const SDNode *, std::string> NodeGraphAttrs;
510	#endif
511
512	/// Clear all previously defined node graph attributes.
513	/// Intended to be used from a debugging tool (eg. gdb).
514	void clearGraphAttrs();
515
516	/// Set graph attributes for a node. (eg. "color=red".)
517	void setGraphAttrs(const SDNode *N, const char *Attrs);
518
519	/// Get graph attributes for a node. (eg. "color=red".)
520	/// Used from getNodeAttributes.
521	std::string getGraphAttrs(const SDNode *N) const;
522
523	/// Convenience for setting node color attribute.
524	void setGraphColor(const SDNode *N, const char *Color);
525
526	/// Convenience for setting subgraph color attribute.
527	void setSubgraphColor(SDNode *N, const char *Color);
528
529	using allnodes_const_iterator = ilist<SDNode>::const_iterator;
530
531	allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); }
532	allnodes_const_iterator allnodes_end() const { return AllNodes.end(); }
533
534	using allnodes_iterator = ilist<SDNode>::iterator;
535
536	allnodes_iterator allnodes_begin() { return AllNodes.begin(); }
537	allnodes_iterator allnodes_end() { return AllNodes.end(); }
538
539	ilist<SDNode>::size_type allnodes_size() const {
540	return AllNodes.size();
541	}
542
543	iterator_range<allnodes_iterator> allnodes() {
544	return make_range(x: allnodes_begin(), y: allnodes_end());
545	}
546	iterator_range<allnodes_const_iterator> allnodes() const {
547	return make_range(x: allnodes_begin(), y: allnodes_end());
548	}
549
550	/// Return the root tag of the SelectionDAG.
551	const SDValue &getRoot() const { return Root; }
552
553	/// Return the token chain corresponding to the entry of the function.
554	SDValue getEntryNode() const {
555	return SDValue(const_cast<SDNode *>(&EntryNode), 0);
556	}
557
558	/// Set the current root tag of the SelectionDAG.
559	///
560	const SDValue &setRoot(SDValue N) {
561	assert((!N.getNode() || N.getValueType() == MVT::Other) &&
562	"DAG root value is not a chain!");
563	if (N.getNode())
564	checkForCycles(N: N.getNode(), DAG: this);
565	Root = N;
566	if (N.getNode())
567	checkForCycles(DAG: this);
568	return Root;
569	}
570
571	#ifndef NDEBUG
572	void VerifyDAGDivergence();
573	#endif
574
575	/// This iterates over the nodes in the SelectionDAG, folding
576	/// certain types of nodes together, or eliminating superfluous nodes. The
577	/// Level argument controls whether Combine is allowed to produce nodes and
578	/// types that are illegal on the target.
579	void Combine(CombineLevel Level, AAResults *AA, CodeGenOptLevel OptLevel);
580
581	/// This transforms the SelectionDAG into a SelectionDAG that
582	/// only uses types natively supported by the target.
583	/// Returns "true" if it made any changes.
584	///
585	/// Note that this is an involved process that may invalidate pointers into
586	/// the graph.
587	bool LegalizeTypes();
588
589	/// This transforms the SelectionDAG into a SelectionDAG that is
590	/// compatible with the target instruction selector, as indicated by the
591	/// TargetLowering object.
592	///
593	/// Note that this is an involved process that may invalidate pointers into
594	/// the graph.
595	void Legalize();
596
597	/// Transforms a SelectionDAG node and any operands to it into a node
598	/// that is compatible with the target instruction selector, as indicated by
599	/// the TargetLowering object.
600	///
601	/// \returns true if \c N is a valid, legal node after calling this.
602	///
603	/// This essentially runs a single recursive walk of the \c Legalize process
604	/// over the given node (and its operands). This can be used to incrementally
605	/// legalize the DAG. All of the nodes which are directly replaced,
606	/// potentially including N, are added to the output parameter \c
607	/// UpdatedNodes so that the delta to the DAG can be understood by the
608	/// caller.
609	///
610	/// When this returns false, N has been legalized in a way that make the
611	/// pointer passed in no longer valid. It may have even been deleted from the
612	/// DAG, and so it shouldn't be used further. When this returns true, the
613	/// N passed in is a legal node, and can be immediately processed as such.
614	/// This may still have done some work on the DAG, and will still populate
615	/// UpdatedNodes with any new nodes replacing those originally in the DAG.
616	bool LegalizeOp(SDNode *N, SmallSetVector<SDNode *, 16> &UpdatedNodes);
617
618	/// This transforms the SelectionDAG into a SelectionDAG
619	/// that only uses vector math operations supported by the target. This is
620	/// necessary as a separate step from Legalize because unrolling a vector
621	/// operation can introduce illegal types, which requires running
622	/// LegalizeTypes again.
623	///
624	/// This returns true if it made any changes; in that case, LegalizeTypes
625	/// is called again before Legalize.
626	///
627	/// Note that this is an involved process that may invalidate pointers into
628	/// the graph.
629	bool LegalizeVectors();
630
631	/// This method deletes all unreachable nodes in the SelectionDAG.
632	void RemoveDeadNodes();
633
634	/// Remove the specified node from the system. This node must
635	/// have no referrers.
636	void DeleteNode(SDNode *N);
637
638	/// Return an SDVTList that represents the list of values specified.
639	SDVTList getVTList(EVT VT);
640	SDVTList getVTList(EVT VT1, EVT VT2);
641	SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3);
642	SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4);
643	SDVTList getVTList(ArrayRef<EVT> VTs);
644
645	//===--------------------------------------------------------------------===//
646	// Node creation methods.
647
648	/// Create a ConstantSDNode wrapping a constant value.
649	/// If VT is a vector type, the constant is splatted into a BUILD_VECTOR.
650	///
651	/// If only legal types can be produced, this does the necessary
652	/// transformations (e.g., if the vector element type is illegal).
653	/// @{
654	SDValue getConstant(uint64_t Val, const SDLoc &DL, EVT VT,
655	bool isTarget = false, bool isOpaque = false);
656	SDValue getConstant(const APInt &Val, const SDLoc &DL, EVT VT,
657	bool isTarget = false, bool isOpaque = false);
658
659	SDValue getAllOnesConstant(const SDLoc &DL, EVT VT, bool IsTarget = false,
660	bool IsOpaque = false) {
661	return getConstant(Val: APInt::getAllOnes(numBits: VT.getScalarSizeInBits()), DL, VT,
662	isTarget: IsTarget, isOpaque: IsOpaque);
663	}
664
665	SDValue getConstant(const ConstantInt &Val, const SDLoc &DL, EVT VT,
666	bool isTarget = false, bool isOpaque = false);
667	SDValue getIntPtrConstant(uint64_t Val, const SDLoc &DL,
668	bool isTarget = false);
669	SDValue getShiftAmountConstant(uint64_t Val, EVT VT, const SDLoc &DL,
670	bool LegalTypes = true);
671	SDValue getShiftAmountConstant(const APInt &Val, EVT VT, const SDLoc &DL,
672	bool LegalTypes = true);
673	SDValue getVectorIdxConstant(uint64_t Val, const SDLoc &DL,
674	bool isTarget = false);
675
676	SDValue getTargetConstant(uint64_t Val, const SDLoc &DL, EVT VT,
677	bool isOpaque = false) {
678	return getConstant(Val, DL, VT, isTarget: true, isOpaque);
679	}
680	SDValue getTargetConstant(const APInt &Val, const SDLoc &DL, EVT VT,
681	bool isOpaque = false) {
682	return getConstant(Val, DL, VT, isTarget: true, isOpaque);
683	}
684	SDValue getTargetConstant(const ConstantInt &Val, const SDLoc &DL, EVT VT,
685	bool isOpaque = false) {
686	return getConstant(Val, DL, VT, isTarget: true, isOpaque);
687	}
688
689	/// Create a true or false constant of type \p VT using the target's
690	/// BooleanContent for type \p OpVT.
691	SDValue getBoolConstant(bool V, const SDLoc &DL, EVT VT, EVT OpVT);
692	/// @}
693
694	/// Create a ConstantFPSDNode wrapping a constant value.
695	/// If VT is a vector type, the constant is splatted into a BUILD_VECTOR.
696	///
697	/// If only legal types can be produced, this does the necessary
698	/// transformations (e.g., if the vector element type is illegal).
699	/// The forms that take a double should only be used for simple constants
700	/// that can be exactly represented in VT. No checks are made.
701	/// @{
702	SDValue getConstantFP(double Val, const SDLoc &DL, EVT VT,
703	bool isTarget = false);
704	SDValue getConstantFP(const APFloat &Val, const SDLoc &DL, EVT VT,
705	bool isTarget = false);
706	SDValue getConstantFP(const ConstantFP &V, const SDLoc &DL, EVT VT,
707	bool isTarget = false);
708	SDValue getTargetConstantFP(double Val, const SDLoc &DL, EVT VT) {
709	return getConstantFP(Val, DL, VT, isTarget: true);
710	}
711	SDValue getTargetConstantFP(const APFloat &Val, const SDLoc &DL, EVT VT) {
712	return getConstantFP(Val, DL, VT, isTarget: true);
713	}
714	SDValue getTargetConstantFP(const ConstantFP &Val, const SDLoc &DL, EVT VT) {
715	return getConstantFP(V: Val, DL, VT, isTarget: true);
716	}
717	/// @}
718
719	SDValue getGlobalAddress(const GlobalValue *GV, const SDLoc &DL, EVT VT,
720	int64_t offset = 0, bool isTargetGA = false,
721	unsigned TargetFlags = 0);
722	SDValue getTargetGlobalAddress(const GlobalValue *GV, const SDLoc &DL, EVT VT,
723	int64_t offset = 0, unsigned TargetFlags = 0) {
724	return getGlobalAddress(GV, DL, VT, offset, isTargetGA: true, TargetFlags);
725	}
726	SDValue getFrameIndex(int FI, EVT VT, bool isTarget = false);
727	SDValue getTargetFrameIndex(int FI, EVT VT) {
728	return getFrameIndex(FI, VT, isTarget: true);
729	}
730	SDValue getJumpTable(int JTI, EVT VT, bool isTarget = false,
731	unsigned TargetFlags = 0);
732	SDValue getTargetJumpTable(int JTI, EVT VT, unsigned TargetFlags = 0) {
733	return getJumpTable(JTI, VT, isTarget: true, TargetFlags);
734	}
735	SDValue getJumpTableDebugInfo(int JTI, SDValue Chain, const SDLoc &DL);
736	SDValue getConstantPool(const Constant *C, EVT VT,
737	MaybeAlign Align = std::nullopt, int Offs = 0,
738	bool isT = false, unsigned TargetFlags = 0);
739	SDValue getTargetConstantPool(const Constant *C, EVT VT,
740	MaybeAlign Align = std::nullopt, int Offset = 0,
741	unsigned TargetFlags = 0) {
742	return getConstantPool(C, VT, Align, Offs: Offset, isT: true, TargetFlags);
743	}
744	SDValue getConstantPool(MachineConstantPoolValue *C, EVT VT,
745	MaybeAlign Align = std::nullopt, int Offs = 0,
746	bool isT = false, unsigned TargetFlags = 0);
747	SDValue getTargetConstantPool(MachineConstantPoolValue *C, EVT VT,
748	MaybeAlign Align = std::nullopt, int Offset = 0,
749	unsigned TargetFlags = 0) {
750	return getConstantPool(C, VT, Align, Offs: Offset, isT: true, TargetFlags);
751	}
752	// When generating a branch to a BB, we don't in general know enough
753	// to provide debug info for the BB at that time, so keep this one around.
754	SDValue getBasicBlock(MachineBasicBlock *MBB);
755	SDValue getExternalSymbol(const char *Sym, EVT VT);
756	SDValue getTargetExternalSymbol(const char *Sym, EVT VT,
757	unsigned TargetFlags = 0);
758	SDValue getMCSymbol(MCSymbol *Sym, EVT VT);
759
760	SDValue getValueType(EVT);
761	SDValue getRegister(unsigned Reg, EVT VT);
762	SDValue getRegisterMask(const uint32_t *RegMask);
763	SDValue getEHLabel(const SDLoc &dl, SDValue Root, MCSymbol *Label);
764	SDValue getLabelNode(unsigned Opcode, const SDLoc &dl, SDValue Root,
765	MCSymbol *Label);
766	SDValue getBlockAddress(const BlockAddress *BA, EVT VT, int64_t Offset = 0,
767	bool isTarget = false, unsigned TargetFlags = 0);
768	SDValue getTargetBlockAddress(const BlockAddress *BA, EVT VT,
769	int64_t Offset = 0, unsigned TargetFlags = 0) {
770	return getBlockAddress(BA, VT, Offset, isTarget: true, TargetFlags);
771	}
772
773	SDValue getCopyToReg(SDValue Chain, const SDLoc &dl, unsigned Reg,
774	SDValue N) {
775	return getNode(ISD::CopyToReg, dl, MVT::Other, Chain,
776	getRegister(Reg, N.getValueType()), N);
777	}
778
779	// This version of the getCopyToReg method takes an extra operand, which
780	// indicates that there is potentially an incoming glue value (if Glue is not
781	// null) and that there should be a glue result.
782	SDValue getCopyToReg(SDValue Chain, const SDLoc &dl, unsigned Reg, SDValue N,
783	SDValue Glue) {
784	SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
785	SDValue Ops[] = { Chain, getRegister(Reg, VT: N.getValueType()), N, Glue };
786	return getNode(Opcode: ISD::CopyToReg, DL: dl, VTList: VTs,
787	Ops: ArrayRef(Ops, Glue.getNode() ? 4 : 3));
788	}
789
790	// Similar to last getCopyToReg() except parameter Reg is a SDValue
791	SDValue getCopyToReg(SDValue Chain, const SDLoc &dl, SDValue Reg, SDValue N,
792	SDValue Glue) {
793	SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
794	SDValue Ops[] = { Chain, Reg, N, Glue };
795	return getNode(Opcode: ISD::CopyToReg, DL: dl, VTList: VTs,
796	Ops: ArrayRef(Ops, Glue.getNode() ? 4 : 3));
797	}
798
799	SDValue getCopyFromReg(SDValue Chain, const SDLoc &dl, unsigned Reg, EVT VT) {
800	SDVTList VTs = getVTList(VT, MVT::Other);
801	SDValue Ops[] = { Chain, getRegister(Reg, VT) };
802	return getNode(Opcode: ISD::CopyFromReg, DL: dl, VTList: VTs, Ops);
803	}
804
805	// This version of the getCopyFromReg method takes an extra operand, which
806	// indicates that there is potentially an incoming glue value (if Glue is not
807	// null) and that there should be a glue result.
808	SDValue getCopyFromReg(SDValue Chain, const SDLoc &dl, unsigned Reg, EVT VT,
809	SDValue Glue) {
810	SDVTList VTs = getVTList(VT, MVT::Other, MVT::Glue);
811	SDValue Ops[] = { Chain, getRegister(Reg, VT), Glue };
812	return getNode(Opcode: ISD::CopyFromReg, DL: dl, VTList: VTs,
813	Ops: ArrayRef(Ops, Glue.getNode() ? 3 : 2));
814	}
815
816	SDValue getCondCode(ISD::CondCode Cond);
817
818	/// Return an ISD::VECTOR_SHUFFLE node. The number of elements in VT,
819	/// which must be a vector type, must match the number of mask elements
820	/// NumElts. An integer mask element equal to -1 is treated as undefined.
821	SDValue getVectorShuffle(EVT VT, const SDLoc &dl, SDValue N1, SDValue N2,
822	ArrayRef<int> Mask);
823
824	/// Return an ISD::BUILD_VECTOR node. The number of elements in VT,
825	/// which must be a vector type, must match the number of operands in Ops.
826	/// The operands must have the same type as (or, for integers, a type wider
827	/// than) VT's element type.
828	SDValue getBuildVector(EVT VT, const SDLoc &DL, ArrayRef<SDValue> Ops) {
829	// VerifySDNode (via InsertNode) checks BUILD_VECTOR later.
830	return getNode(Opcode: ISD::BUILD_VECTOR, DL, VT, Ops);
831	}
832
833	/// Return an ISD::BUILD_VECTOR node. The number of elements in VT,
834	/// which must be a vector type, must match the number of operands in Ops.
835	/// The operands must have the same type as (or, for integers, a type wider
836	/// than) VT's element type.
837	SDValue getBuildVector(EVT VT, const SDLoc &DL, ArrayRef<SDUse> Ops) {
838	// VerifySDNode (via InsertNode) checks BUILD_VECTOR later.
839	return getNode(Opcode: ISD::BUILD_VECTOR, DL, VT, Ops);
840	}
841
842	/// Return a splat ISD::BUILD_VECTOR node, consisting of Op splatted to all
843	/// elements. VT must be a vector type. Op's type must be the same as (or,
844	/// for integers, a type wider than) VT's element type.
845	SDValue getSplatBuildVector(EVT VT, const SDLoc &DL, SDValue Op) {
846	// VerifySDNode (via InsertNode) checks BUILD_VECTOR later.
847	if (Op.getOpcode() == ISD::UNDEF) {
848	assert((VT.getVectorElementType() == Op.getValueType() ||
849	(VT.isInteger() &&
850	VT.getVectorElementType().bitsLE(Op.getValueType()))) &&
851	"A splatted value must have a width equal or (for integers) "
852	"greater than the vector element type!");
853	return getNode(Opcode: ISD::UNDEF, DL: SDLoc(), VT);
854	}
855
856	SmallVector<SDValue, 16> Ops(VT.getVectorNumElements(), Op);
857	return getNode(Opcode: ISD::BUILD_VECTOR, DL, VT, Ops);
858	}
859
860	// Return a splat ISD::SPLAT_VECTOR node, consisting of Op splatted to all
861	// elements.
862	SDValue getSplatVector(EVT VT, const SDLoc &DL, SDValue Op) {
863	if (Op.getOpcode() == ISD::UNDEF) {
864	assert((VT.getVectorElementType() == Op.getValueType() ||
865	(VT.isInteger() &&
866	VT.getVectorElementType().bitsLE(Op.getValueType()))) &&
867	"A splatted value must have a width equal or (for integers) "
868	"greater than the vector element type!");
869	return getNode(Opcode: ISD::UNDEF, DL: SDLoc(), VT);
870	}
871	return getNode(Opcode: ISD::SPLAT_VECTOR, DL, VT, Operand: Op);
872	}
873
874	/// Returns a node representing a splat of one value into all lanes
875	/// of the provided vector type. This is a utility which returns
876	/// either a BUILD_VECTOR or SPLAT_VECTOR depending on the
877	/// scalability of the desired vector type.
878	SDValue getSplat(EVT VT, const SDLoc &DL, SDValue Op) {
879	assert(VT.isVector() && "Can't splat to non-vector type");
880	return VT.isScalableVector() ?
881	getSplatVector(VT, DL, Op) : getSplatBuildVector(VT, DL, Op);
882	}
883
884	/// Returns a vector of type ResVT whose elements contain the linear sequence
885	/// <0, Step, Step * 2, Step * 3, ...>
886	SDValue getStepVector(const SDLoc &DL, EVT ResVT, APInt StepVal);
887
888	/// Returns a vector of type ResVT whose elements contain the linear sequence
889	/// <0, 1, 2, 3, ...>
890	SDValue getStepVector(const SDLoc &DL, EVT ResVT);
891
892	/// Returns an ISD::VECTOR_SHUFFLE node semantically equivalent to
893	/// the shuffle node in input but with swapped operands.
894	///
895	/// Example: shuffle A, B, <0,5,2,7> -> shuffle B, A, <4,1,6,3>
896	SDValue getCommutedVectorShuffle(const ShuffleVectorSDNode &SV);
897
898	/// Convert Op, which must be of float type, to the
899	/// float type VT, by either extending or rounding (by truncation).
900	SDValue getFPExtendOrRound(SDValue Op, const SDLoc &DL, EVT VT);
901
902	/// Convert Op, which must be a STRICT operation of float type, to the
903	/// float type VT, by either extending or rounding (by truncation).
904	std::pair<SDValue, SDValue>
905	getStrictFPExtendOrRound(SDValue Op, SDValue Chain, const SDLoc &DL, EVT VT);
906
907	/// Convert *_EXTEND_VECTOR_INREG to *_EXTEND opcode.
908	static unsigned getOpcode_EXTEND(unsigned Opcode) {
909	switch (Opcode) {
910	case ISD::ANY_EXTEND:
911	case ISD::ANY_EXTEND_VECTOR_INREG:
912	return ISD::ANY_EXTEND;
913	case ISD::ZERO_EXTEND:
914	case ISD::ZERO_EXTEND_VECTOR_INREG:
915	return ISD::ZERO_EXTEND;
916	case ISD::SIGN_EXTEND:
917	case ISD::SIGN_EXTEND_VECTOR_INREG:
918	return ISD::SIGN_EXTEND;
919	}
920	llvm_unreachable("Unknown opcode");
921	}
922
923	/// Convert *_EXTEND to *_EXTEND_VECTOR_INREG opcode.
924	static unsigned getOpcode_EXTEND_VECTOR_INREG(unsigned Opcode) {
925	switch (Opcode) {
926	case ISD::ANY_EXTEND:
927	case ISD::ANY_EXTEND_VECTOR_INREG:
928	return ISD::ANY_EXTEND_VECTOR_INREG;
929	case ISD::ZERO_EXTEND:
930	case ISD::ZERO_EXTEND_VECTOR_INREG:
931	return ISD::ZERO_EXTEND_VECTOR_INREG;
932	case ISD::SIGN_EXTEND:
933	case ISD::SIGN_EXTEND_VECTOR_INREG:
934	return ISD::SIGN_EXTEND_VECTOR_INREG;
935	}
936	llvm_unreachable("Unknown opcode");
937	}
938
939	/// Convert Op, which must be of integer type, to the
940	/// integer type VT, by either any-extending or truncating it.
941	SDValue getAnyExtOrTrunc(SDValue Op, const SDLoc &DL, EVT VT);
942
943	/// Convert Op, which must be of integer type, to the
944	/// integer type VT, by either sign-extending or truncating it.
945	SDValue getSExtOrTrunc(SDValue Op, const SDLoc &DL, EVT VT);
946
947	/// Convert Op, which must be of integer type, to the
948	/// integer type VT, by either zero-extending or truncating it.
949	SDValue getZExtOrTrunc(SDValue Op, const SDLoc &DL, EVT VT);
950
951	/// Convert Op, which must be of integer type, to the
952	/// integer type VT, by either any/sign/zero-extending (depending on IsAny /
953	/// IsSigned) or truncating it.
954	SDValue getExtOrTrunc(SDValue Op, const SDLoc &DL,
955	EVT VT, unsigned Opcode) {
956	switch(Opcode) {
957	case ISD::ANY_EXTEND:
958	return getAnyExtOrTrunc(Op, DL, VT);
959	case ISD::ZERO_EXTEND:
960	return getZExtOrTrunc(Op, DL, VT);
961	case ISD::SIGN_EXTEND:
962	return getSExtOrTrunc(Op, DL, VT);
963	}
964	llvm_unreachable("Unsupported opcode");
965	}
966
967	/// Convert Op, which must be of integer type, to the
968	/// integer type VT, by either sign/zero-extending (depending on IsSigned) or
969	/// truncating it.
970	SDValue getExtOrTrunc(bool IsSigned, SDValue Op, const SDLoc &DL, EVT VT) {
971	return IsSigned ? getSExtOrTrunc(Op, DL, VT) : getZExtOrTrunc(Op, DL, VT);
972	}
973
974	/// Convert Op, which must be of integer type, to the
975	/// integer type VT, by first bitcasting (from potential vector) to
976	/// corresponding scalar type then either any-extending or truncating it.
977	SDValue getBitcastedAnyExtOrTrunc(SDValue Op, const SDLoc &DL, EVT VT);
978
979	/// Convert Op, which must be of integer type, to the
980	/// integer type VT, by first bitcasting (from potential vector) to
981	/// corresponding scalar type then either sign-extending or truncating it.
982	SDValue getBitcastedSExtOrTrunc(SDValue Op, const SDLoc &DL, EVT VT);
983
984	/// Convert Op, which must be of integer type, to the
985	/// integer type VT, by first bitcasting (from potential vector) to
986	/// corresponding scalar type then either zero-extending or truncating it.
987	SDValue getBitcastedZExtOrTrunc(SDValue Op, const SDLoc &DL, EVT VT);
988
989	/// Return the expression required to zero extend the Op
990	/// value assuming it was the smaller SrcTy value.
991	SDValue getZeroExtendInReg(SDValue Op, const SDLoc &DL, EVT VT);
992
993	/// Convert Op, which must be of integer type, to the integer type VT, by
994	/// either truncating it or performing either zero or sign extension as
995	/// appropriate extension for the pointer's semantics.
996	SDValue getPtrExtOrTrunc(SDValue Op, const SDLoc &DL, EVT VT);
997
998	/// Return the expression required to extend the Op as a pointer value
999	/// assuming it was the smaller SrcTy value. This may be either a zero extend
1000	/// or a sign extend.
1001	SDValue getPtrExtendInReg(SDValue Op, const SDLoc &DL, EVT VT);
1002
1003	/// Convert Op, which must be of integer type, to the integer type VT,
1004	/// by using an extension appropriate for the target's
1005	/// BooleanContent for type OpVT or truncating it.
1006	SDValue getBoolExtOrTrunc(SDValue Op, const SDLoc &SL, EVT VT, EVT OpVT);
1007
1008	/// Create negative operation as (SUB 0, Val).
1009	SDValue getNegative(SDValue Val, const SDLoc &DL, EVT VT);
1010
1011	/// Create a bitwise NOT operation as (XOR Val, -1).
1012	SDValue getNOT(const SDLoc &DL, SDValue Val, EVT VT);
1013
1014	/// Create a logical NOT operation as (XOR Val, BooleanOne).
1015	SDValue getLogicalNOT(const SDLoc &DL, SDValue Val, EVT VT);
1016
1017	/// Create a vector-predicated logical NOT operation as (VP_XOR Val,
1018	/// BooleanOne, Mask, EVL).
1019	SDValue getVPLogicalNOT(const SDLoc &DL, SDValue Val, SDValue Mask,
1020	SDValue EVL, EVT VT);
1021
1022	/// Convert a vector-predicated Op, which must be an integer vector, to the
1023	/// vector-type VT, by performing either vector-predicated zext or truncating
1024	/// it. The Op will be returned as-is if Op and VT are vectors containing
1025	/// integer with same width.
1026	SDValue getVPZExtOrTrunc(const SDLoc &DL, EVT VT, SDValue Op, SDValue Mask,
1027	SDValue EVL);
1028
1029	/// Convert a vector-predicated Op, which must be of integer type, to the
1030	/// vector-type integer type VT, by either truncating it or performing either
1031	/// vector-predicated zero or sign extension as appropriate extension for the
1032	/// pointer's semantics. This function just redirects to getVPZExtOrTrunc
1033	/// right now.
1034	SDValue getVPPtrExtOrTrunc(const SDLoc &DL, EVT VT, SDValue Op, SDValue Mask,
1035	SDValue EVL);
1036
1037	/// Returns sum of the base pointer and offset.
1038	/// Unlike getObjectPtrOffset this does not set NoUnsignedWrap by default.
1039	SDValue getMemBasePlusOffset(SDValue Base, TypeSize Offset, const SDLoc &DL,
1040	const SDNodeFlags Flags = SDNodeFlags());
1041	SDValue getMemBasePlusOffset(SDValue Base, SDValue Offset, const SDLoc &DL,
1042	const SDNodeFlags Flags = SDNodeFlags());
1043
1044	/// Create an add instruction with appropriate flags when used for
1045	/// addressing some offset of an object. i.e. if a load is split into multiple
1046	/// components, create an add nuw from the base pointer to the offset.
1047	SDValue getObjectPtrOffset(const SDLoc &SL, SDValue Ptr, TypeSize Offset) {
1048	SDNodeFlags Flags;
1049	Flags.setNoUnsignedWrap(true);
1050	return getMemBasePlusOffset(Base: Ptr, Offset, DL: SL, Flags);
1051	}
1052
1053	SDValue getObjectPtrOffset(const SDLoc &SL, SDValue Ptr, SDValue Offset) {
1054	// The object itself can't wrap around the address space, so it shouldn't be
1055	// possible for the adds of the offsets to the split parts to overflow.
1056	SDNodeFlags Flags;
1057	Flags.setNoUnsignedWrap(true);
1058	return getMemBasePlusOffset(Base: Ptr, Offset, DL: SL, Flags);
1059	}
1060
1061	/// Return a new CALLSEQ_START node, that starts new call frame, in which
1062	/// InSize bytes are set up inside CALLSEQ_START..CALLSEQ_END sequence and
1063	/// OutSize specifies part of the frame set up prior to the sequence.
1064	SDValue getCALLSEQ_START(SDValue Chain, uint64_t InSize, uint64_t OutSize,
1065	const SDLoc &DL) {
1066	SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
1067	SDValue Ops[] = { Chain,
1068	getIntPtrConstant(Val: InSize, DL, isTarget: true),
1069	getIntPtrConstant(Val: OutSize, DL, isTarget: true) };
1070	return getNode(Opcode: ISD::CALLSEQ_START, DL, VTList: VTs, Ops);
1071	}
1072
1073	/// Return a new CALLSEQ_END node, which always must have a
1074	/// glue result (to ensure it's not CSE'd).
1075	/// CALLSEQ_END does not have a useful SDLoc.
1076	SDValue getCALLSEQ_END(SDValue Chain, SDValue Op1, SDValue Op2,
1077	SDValue InGlue, const SDLoc &DL) {
1078	SDVTList NodeTys = getVTList(MVT::Other, MVT::Glue);
1079	SmallVector<SDValue, 4> Ops;
1080	Ops.push_back(Elt: Chain);
1081	Ops.push_back(Elt: Op1);
1082	Ops.push_back(Elt: Op2);
1083	if (InGlue.getNode())
1084	Ops.push_back(Elt: InGlue);
1085	return getNode(Opcode: ISD::CALLSEQ_END, DL, VTList: NodeTys, Ops);
1086	}
1087
1088	SDValue getCALLSEQ_END(SDValue Chain, uint64_t Size1, uint64_t Size2,
1089	SDValue Glue, const SDLoc &DL) {
1090	return getCALLSEQ_END(
1091	Chain, Op1: getIntPtrConstant(Val: Size1, DL, /*isTarget=*/isTarget: true),
1092	Op2: getIntPtrConstant(Val: Size2, DL, /*isTarget=*/isTarget: true), InGlue: Glue, DL);
1093	}
1094
1095	/// Return true if the result of this operation is always undefined.
1096	bool isUndef(unsigned Opcode, ArrayRef<SDValue> Ops);
1097
1098	/// Return an UNDEF node. UNDEF does not have a useful SDLoc.
1099	SDValue getUNDEF(EVT VT) {
1100	return getNode(Opcode: ISD::UNDEF, DL: SDLoc(), VT);
1101	}
1102
1103	/// Return a node that represents the runtime scaling 'MulImm * RuntimeVL'.
1104	SDValue getVScale(const SDLoc &DL, EVT VT, APInt MulImm,
1105	bool ConstantFold = true);
1106
1107	SDValue getElementCount(const SDLoc &DL, EVT VT, ElementCount EC,
1108	bool ConstantFold = true);
1109
1110	/// Return a GLOBAL_OFFSET_TABLE node. This does not have a useful SDLoc.
1111	SDValue getGLOBAL_OFFSET_TABLE(EVT VT) {
1112	return getNode(Opcode: ISD::GLOBAL_OFFSET_TABLE, DL: SDLoc(), VT);
1113	}
1114
1115	/// Gets or creates the specified node.
1116	///
1117	SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT,
1118	ArrayRef<SDUse> Ops);
1119	SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT,
1120	ArrayRef<SDValue> Ops, const SDNodeFlags Flags);
1121	SDValue getNode(unsigned Opcode, const SDLoc &DL, ArrayRef<EVT> ResultTys,
1122	ArrayRef<SDValue> Ops);
1123	SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList,
1124	ArrayRef<SDValue> Ops, const SDNodeFlags Flags);
1125
1126	// Use flags from current flag inserter.
1127	SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT,
1128	ArrayRef<SDValue> Ops);
1129	SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList,
1130	ArrayRef<SDValue> Ops);
1131	SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue Operand);
1132	SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1,
1133	SDValue N2);
1134	SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1,
1135	SDValue N2, SDValue N3);
1136
1137	// Specialize based on number of operands.
1138	SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT);
1139	SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue Operand,
1140	const SDNodeFlags Flags);
1141	SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1,
1142	SDValue N2, const SDNodeFlags Flags);
1143	SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1,
1144	SDValue N2, SDValue N3, const SDNodeFlags Flags);
1145	SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1,
1146	SDValue N2, SDValue N3, SDValue N4);
1147	SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1,
1148	SDValue N2, SDValue N3, SDValue N4, SDValue N5);
1149
1150	// Specialize again based on number of operands for nodes with a VTList
1151	// rather than a single VT.
1152	SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList);
1153	SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList, SDValue N);
1154	SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList, SDValue N1,
1155	SDValue N2);
1156	SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList, SDValue N1,
1157	SDValue N2, SDValue N3);
1158	SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList, SDValue N1,
1159	SDValue N2, SDValue N3, SDValue N4);
1160	SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList, SDValue N1,
1161	SDValue N2, SDValue N3, SDValue N4, SDValue N5);
1162
1163	/// Compute a TokenFactor to force all the incoming stack arguments to be
1164	/// loaded from the stack. This is used in tail call lowering to protect
1165	/// stack arguments from being clobbered.
1166	SDValue getStackArgumentTokenFactor(SDValue Chain);
1167
1168	SDValue getMemcpy(SDValue Chain, const SDLoc &dl, SDValue Dst, SDValue Src,
1169	SDValue Size, Align Alignment, bool isVol,
1170	bool AlwaysInline, bool isTailCall,
1171	MachinePointerInfo DstPtrInfo,
1172	MachinePointerInfo SrcPtrInfo,
1173	const AAMDNodes &AAInfo = AAMDNodes(),
1174	AAResults *AA = nullptr);
1175
1176	SDValue getMemmove(SDValue Chain, const SDLoc &dl, SDValue Dst, SDValue Src,
1177	SDValue Size, Align Alignment, bool isVol, bool isTailCall,
1178	MachinePointerInfo DstPtrInfo,
1179	MachinePointerInfo SrcPtrInfo,
1180	const AAMDNodes &AAInfo = AAMDNodes(),
1181	AAResults *AA = nullptr);
1182
1183	SDValue getMemset(SDValue Chain, const SDLoc &dl, SDValue Dst, SDValue Src,
1184	SDValue Size, Align Alignment, bool isVol,
1185	bool AlwaysInline, bool isTailCall,
1186	MachinePointerInfo DstPtrInfo,
1187	const AAMDNodes &AAInfo = AAMDNodes());
1188
1189	SDValue getAtomicMemcpy(SDValue Chain, const SDLoc &dl, SDValue Dst,
1190	SDValue Src, SDValue Size, Type *SizeTy,
1191	unsigned ElemSz, bool isTailCall,
1192	MachinePointerInfo DstPtrInfo,
1193	MachinePointerInfo SrcPtrInfo);
1194
1195	SDValue getAtomicMemmove(SDValue Chain, const SDLoc &dl, SDValue Dst,
1196	SDValue Src, SDValue Size, Type *SizeTy,
1197	unsigned ElemSz, bool isTailCall,
1198	MachinePointerInfo DstPtrInfo,
1199	MachinePointerInfo SrcPtrInfo);
1200
1201	SDValue getAtomicMemset(SDValue Chain, const SDLoc &dl, SDValue Dst,
1202	SDValue Value, SDValue Size, Type *SizeTy,
1203	unsigned ElemSz, bool isTailCall,
1204	MachinePointerInfo DstPtrInfo);
1205
1206	/// Helper function to make it easier to build SetCC's if you just have an
1207	/// ISD::CondCode instead of an SDValue.
1208	SDValue getSetCC(const SDLoc &DL, EVT VT, SDValue LHS, SDValue RHS,
1209	ISD::CondCode Cond, SDValue Chain = SDValue(),
1210	bool IsSignaling = false) {
1211	assert(LHS.getValueType().isVector() == RHS.getValueType().isVector() &&
1212	"Vector/scalar operand type mismatch for setcc");
1213	assert(LHS.getValueType().isVector() == VT.isVector() &&
1214	"Vector/scalar result type mismatch for setcc");
1215	assert(Cond != ISD::SETCC_INVALID &&
1216	"Cannot create a setCC of an invalid node.");
1217	if (Chain)
1218	return getNode(IsSignaling ? ISD::STRICT_FSETCCS : ISD::STRICT_FSETCC, DL,
1219	{VT, MVT::Other}, {Chain, LHS, RHS, getCondCode(Cond)});
1220	return getNode(Opcode: ISD::SETCC, DL, VT, N1: LHS, N2: RHS, N3: getCondCode(Cond));
1221	}
1222
1223	/// Helper function to make it easier to build VP_SETCCs if you just have an
1224	/// ISD::CondCode instead of an SDValue.
1225	SDValue getSetCCVP(const SDLoc &DL, EVT VT, SDValue LHS, SDValue RHS,
1226	ISD::CondCode Cond, SDValue Mask, SDValue EVL) {
1227	assert(LHS.getValueType().isVector() && RHS.getValueType().isVector() &&
1228	"Cannot compare scalars");
1229	assert(Cond != ISD::SETCC_INVALID &&
1230	"Cannot create a setCC of an invalid node.");
1231	return getNode(Opcode: ISD::VP_SETCC, DL, VT, N1: LHS, N2: RHS, N3: getCondCode(Cond), N4: Mask,
1232	N5: EVL);
1233	}
1234
1235	/// Helper function to make it easier to build Select's if you just have
1236	/// operands and don't want to check for vector.
1237	SDValue getSelect(const SDLoc &DL, EVT VT, SDValue Cond, SDValue LHS,
1238	SDValue RHS) {
1239	assert(LHS.getValueType() == VT && RHS.getValueType() == VT &&
1240	"Cannot use select on differing types");
1241	auto Opcode = Cond.getValueType().isVector() ? ISD::VSELECT : ISD::SELECT;
1242	return getNode(Opcode, DL, VT, N1: Cond, N2: LHS, N3: RHS);
1243	}
1244
1245	/// Helper function to make it easier to build SelectCC's if you just have an
1246	/// ISD::CondCode instead of an SDValue.
1247	SDValue getSelectCC(const SDLoc &DL, SDValue LHS, SDValue RHS, SDValue True,
1248	SDValue False, ISD::CondCode Cond) {
1249	return getNode(Opcode: ISD::SELECT_CC, DL, VT: True.getValueType(), N1: LHS, N2: RHS, N3: True,
1250	N4: False, N5: getCondCode(Cond));
1251	}
1252
1253	/// Try to simplify a select/vselect into 1 of its operands or a constant.
1254	SDValue simplifySelect(SDValue Cond, SDValue TVal, SDValue FVal);
1255
1256	/// Try to simplify a shift into 1 of its operands or a constant.
1257	SDValue simplifyShift(SDValue X, SDValue Y);
1258
1259	/// Try to simplify a floating-point binary operation into 1 of its operands
1260	/// or a constant.
1261	SDValue simplifyFPBinop(unsigned Opcode, SDValue X, SDValue Y,
1262	SDNodeFlags Flags);
1263
1264	/// VAArg produces a result and token chain, and takes a pointer
1265	/// and a source value as input.
1266	SDValue getVAArg(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr,
1267	SDValue SV, unsigned Align);
1268
1269	/// Gets a node for an atomic cmpxchg op. There are two
1270	/// valid Opcodes. ISD::ATOMIC_CMO_SWAP produces the value loaded and a
1271	/// chain result. ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS produces the value loaded,
1272	/// a success flag (initially i1), and a chain.
1273	SDValue getAtomicCmpSwap(unsigned Opcode, const SDLoc &dl, EVT MemVT,
1274	SDVTList VTs, SDValue Chain, SDValue Ptr,
1275	SDValue Cmp, SDValue Swp, MachineMemOperand *MMO);
1276
1277	/// Gets a node for an atomic op, produces result (if relevant)
1278	/// and chain and takes 2 operands.
1279	SDValue getAtomic(unsigned Opcode, const SDLoc &dl, EVT MemVT, SDValue Chain,
1280	SDValue Ptr, SDValue Val, MachineMemOperand *MMO);
1281
1282	/// Gets a node for an atomic op, produces result and chain and
1283	/// takes 1 operand.
1284	SDValue getAtomic(unsigned Opcode, const SDLoc &dl, EVT MemVT, EVT VT,
1285	SDValue Chain, SDValue Ptr, MachineMemOperand *MMO);
1286
1287	/// Gets a node for an atomic op, produces result and chain and takes N
1288	/// operands.
1289	SDValue getAtomic(unsigned Opcode, const SDLoc &dl, EVT MemVT,
1290	SDVTList VTList, ArrayRef<SDValue> Ops,
1291	MachineMemOperand *MMO);
1292
1293	/// Creates a MemIntrinsicNode that may produce a
1294	/// result and takes a list of operands. Opcode may be INTRINSIC_VOID,
1295	/// INTRINSIC_W_CHAIN, or a target-specific opcode with a value not
1296	/// less than FIRST_TARGET_MEMORY_OPCODE.
1297	SDValue getMemIntrinsicNode(
1298	unsigned Opcode, const SDLoc &dl, SDVTList VTList, ArrayRef<SDValue> Ops,
1299	EVT MemVT, MachinePointerInfo PtrInfo, Align Alignment,
1300	MachineMemOperand::Flags Flags = MachineMemOperand::MOLoad |
1301	MachineMemOperand::MOStore,
1302	uint64_t Size = 0, const AAMDNodes &AAInfo = AAMDNodes());
1303
1304	inline SDValue getMemIntrinsicNode(
1305	unsigned Opcode, const SDLoc &dl, SDVTList VTList, ArrayRef<SDValue> Ops,
1306	EVT MemVT, MachinePointerInfo PtrInfo,
1307	MaybeAlign Alignment = std::nullopt,
1308	MachineMemOperand::Flags Flags = MachineMemOperand::MOLoad |
1309	MachineMemOperand::MOStore,
1310	uint64_t Size = 0, const AAMDNodes &AAInfo = AAMDNodes()) {
1311	// Ensure that codegen never sees alignment 0
1312	return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, PtrInfo,
1313	Alignment: Alignment.value_or(u: getEVTAlign(MemoryVT: MemVT)), Flags,
1314	Size, AAInfo);
1315	}
1316
1317	SDValue getMemIntrinsicNode(unsigned Opcode, const SDLoc &dl, SDVTList VTList,
1318	ArrayRef<SDValue> Ops, EVT MemVT,
1319	MachineMemOperand *MMO);
1320
1321	/// Creates a LifetimeSDNode that starts (`IsStart==true`) or ends
1322	/// (`IsStart==false`) the lifetime of the portion of `FrameIndex` between
1323	/// offsets `Offset` and `Offset + Size`.
1324	SDValue getLifetimeNode(bool IsStart, const SDLoc &dl, SDValue Chain,
1325	int FrameIndex, int64_t Size, int64_t Offset = -1);
1326
1327	/// Creates a PseudoProbeSDNode with function GUID `Guid` and
1328	/// the index of the block `Index` it is probing, as well as the attributes
1329	/// `attr` of the probe.
1330	SDValue getPseudoProbeNode(const SDLoc &Dl, SDValue Chain, uint64_t Guid,
1331	uint64_t Index, uint32_t Attr);
1332
1333	/// Create a MERGE_VALUES node from the given operands.
1334	SDValue getMergeValues(ArrayRef<SDValue> Ops, const SDLoc &dl);
1335
1336	/// Loads are not normal binary operators: their result type is not
1337	/// determined by their operands, and they produce a value AND a token chain.
1338	///
1339	/// This function will set the MOLoad flag on MMOFlags, but you can set it if
1340	/// you want. The MOStore flag must not be set.
1341	SDValue getLoad(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr,
1342	MachinePointerInfo PtrInfo,
1343	MaybeAlign Alignment = MaybeAlign(),
1344	MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
1345	const AAMDNodes &AAInfo = AAMDNodes(),
1346	const MDNode *Ranges = nullptr);
1347	SDValue getLoad(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr,
1348	MachineMemOperand *MMO);
1349	SDValue
1350	getExtLoad(ISD::LoadExtType ExtType, const SDLoc &dl, EVT VT, SDValue Chain,
1351	SDValue Ptr, MachinePointerInfo PtrInfo, EVT MemVT,
1352	MaybeAlign Alignment = MaybeAlign(),
1353	MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
1354	const AAMDNodes &AAInfo = AAMDNodes());
1355	SDValue getExtLoad(ISD::LoadExtType ExtType, const SDLoc &dl, EVT VT,
1356	SDValue Chain, SDValue Ptr, EVT MemVT,
1357	MachineMemOperand *MMO);
1358	SDValue getIndexedLoad(SDValue OrigLoad, const SDLoc &dl, SDValue Base,
1359	SDValue Offset, ISD::MemIndexedMode AM);
1360	SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, EVT VT,
1361	const SDLoc &dl, SDValue Chain, SDValue Ptr, SDValue Offset,
1362	MachinePointerInfo PtrInfo, EVT MemVT, Align Alignment,
1363	MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
1364	const AAMDNodes &AAInfo = AAMDNodes(),
1365	const MDNode *Ranges = nullptr);
1366	inline SDValue getLoad(
1367	ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, EVT VT, const SDLoc &dl,
1368	SDValue Chain, SDValue Ptr, SDValue Offset, MachinePointerInfo PtrInfo,
1369	EVT MemVT, MaybeAlign Alignment = MaybeAlign(),
1370	MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
1371	const AAMDNodes &AAInfo = AAMDNodes(), const MDNode *Ranges = nullptr) {
1372	// Ensures that codegen never sees a None Alignment.
1373	return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, PtrInfo, MemVT,
1374	Alignment: Alignment.value_or(u: getEVTAlign(MemoryVT: MemVT)), MMOFlags, AAInfo,
1375	Ranges);
1376	}
1377	SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, EVT VT,
1378	const SDLoc &dl, SDValue Chain, SDValue Ptr, SDValue Offset,
1379	EVT MemVT, MachineMemOperand *MMO);
1380
1381	/// Helper function to build ISD::STORE nodes.
1382	///
1383	/// This function will set the MOStore flag on MMOFlags, but you can set it if
1384	/// you want. The MOLoad and MOInvariant flags must not be set.
1385
1386	SDValue
1387	getStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr,
1388	MachinePointerInfo PtrInfo, Align Alignment,
1389	MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
1390	const AAMDNodes &AAInfo = AAMDNodes());
1391	inline SDValue
1392	getStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr,
1393	MachinePointerInfo PtrInfo, MaybeAlign Alignment = MaybeAlign(),
1394	MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
1395	const AAMDNodes &AAInfo = AAMDNodes()) {
1396	return getStore(Chain, dl, Val, Ptr, PtrInfo,
1397	Alignment: Alignment.value_or(u: getEVTAlign(MemoryVT: Val.getValueType())),
1398	MMOFlags, AAInfo);
1399	}
1400	SDValue getStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr,
1401	MachineMemOperand *MMO);
1402	SDValue
1403	getTruncStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr,
1404	MachinePointerInfo PtrInfo, EVT SVT, Align Alignment,
1405	MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
1406	const AAMDNodes &AAInfo = AAMDNodes());
1407	inline SDValue
1408	getTruncStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr,
1409	MachinePointerInfo PtrInfo, EVT SVT,
1410	MaybeAlign Alignment = MaybeAlign(),
1411	MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
1412	const AAMDNodes &AAInfo = AAMDNodes()) {
1413	return getTruncStore(Chain, dl, Val, Ptr, PtrInfo, SVT,
1414	Alignment: Alignment.value_or(u: getEVTAlign(MemoryVT: SVT)), MMOFlags,
1415	AAInfo);
1416	}
1417	SDValue getTruncStore(SDValue Chain, const SDLoc &dl, SDValue Val,
1418	SDValue Ptr, EVT SVT, MachineMemOperand *MMO);
1419	SDValue getIndexedStore(SDValue OrigStore, const SDLoc &dl, SDValue Base,
1420	SDValue Offset, ISD::MemIndexedMode AM);
1421
1422	SDValue getLoadVP(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, EVT VT,
1423	const SDLoc &dl, SDValue Chain, SDValue Ptr, SDValue Offset,
1424	SDValue Mask, SDValue EVL, MachinePointerInfo PtrInfo,
1425	EVT MemVT, Align Alignment,
1426	MachineMemOperand::Flags MMOFlags, const AAMDNodes &AAInfo,
1427	const MDNode *Ranges = nullptr, bool IsExpanding = false);
1428	inline SDValue
1429	getLoadVP(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, EVT VT,
1430	const SDLoc &dl, SDValue Chain, SDValue Ptr, SDValue Offset,
1431	SDValue Mask, SDValue EVL, MachinePointerInfo PtrInfo, EVT MemVT,
1432	MaybeAlign Alignment = MaybeAlign(),
1433	MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
1434	const AAMDNodes &AAInfo = AAMDNodes(),
1435	const MDNode *Ranges = nullptr, bool IsExpanding = false) {
1436	// Ensures that codegen never sees a None Alignment.
1437	return getLoadVP(AM, ExtType, VT, dl, Chain, Ptr, Offset, Mask, EVL,
1438	PtrInfo, MemVT, Alignment: Alignment.value_or(u: getEVTAlign(MemoryVT: MemVT)),
1439	MMOFlags, AAInfo, Ranges, IsExpanding);
1440	}
1441	SDValue getLoadVP(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, EVT VT,
1442	const SDLoc &dl, SDValue Chain, SDValue Ptr, SDValue Offset,
1443	SDValue Mask, SDValue EVL, EVT MemVT,
1444	MachineMemOperand *MMO, bool IsExpanding = false);
1445	SDValue getLoadVP(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr,
1446	SDValue Mask, SDValue EVL, MachinePointerInfo PtrInfo,
1447	MaybeAlign Alignment, MachineMemOperand::Flags MMOFlags,
1448	const AAMDNodes &AAInfo, const MDNode *Ranges = nullptr,
1449	bool IsExpanding = false);
1450	SDValue getLoadVP(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr,
1451	SDValue Mask, SDValue EVL, MachineMemOperand *MMO,
1452	bool IsExpanding = false);
1453	SDValue getExtLoadVP(ISD::LoadExtType ExtType, const SDLoc &dl, EVT VT,
1454	SDValue Chain, SDValue Ptr, SDValue Mask, SDValue EVL,
1455	MachinePointerInfo PtrInfo, EVT MemVT,
1456	MaybeAlign Alignment, MachineMemOperand::Flags MMOFlags,
1457	const AAMDNodes &AAInfo, bool IsExpanding = false);
1458	SDValue getExtLoadVP(ISD::LoadExtType ExtType, const SDLoc &dl, EVT VT,
1459	SDValue Chain, SDValue Ptr, SDValue Mask, SDValue EVL,
1460	EVT MemVT, MachineMemOperand *MMO,
1461	bool IsExpanding = false);
1462	SDValue getIndexedLoadVP(SDValue OrigLoad, const SDLoc &dl, SDValue Base,
1463	SDValue Offset, ISD::MemIndexedMode AM);
1464	SDValue getStoreVP(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr,
1465	SDValue Offset, SDValue Mask, SDValue EVL, EVT MemVT,
1466	MachineMemOperand *MMO, ISD::MemIndexedMode AM,
1467	bool IsTruncating = false, bool IsCompressing = false);
1468	SDValue getTruncStoreVP(SDValue Chain, const SDLoc &dl, SDValue Val,
1469	SDValue Ptr, SDValue Mask, SDValue EVL,
1470	MachinePointerInfo PtrInfo, EVT SVT, Align Alignment,
1471	MachineMemOperand::Flags MMOFlags,
1472	const AAMDNodes &AAInfo, bool IsCompressing = false);
1473	SDValue getTruncStoreVP(SDValue Chain, const SDLoc &dl, SDValue Val,
1474	SDValue Ptr, SDValue Mask, SDValue EVL, EVT SVT,
1475	MachineMemOperand *MMO, bool IsCompressing = false);
1476	SDValue getIndexedStoreVP(SDValue OrigStore, const SDLoc &dl, SDValue Base,
1477	SDValue Offset, ISD::MemIndexedMode AM);
1478
1479	SDValue getStridedLoadVP(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
1480	EVT VT, const SDLoc &DL, SDValue Chain, SDValue Ptr,
1481	SDValue Offset, SDValue Stride, SDValue Mask,
1482	SDValue EVL, MachinePointerInfo PtrInfo, EVT MemVT,
1483	Align Alignment, MachineMemOperand::Flags MMOFlags,
1484	const AAMDNodes &AAInfo,
1485	const MDNode *Ranges = nullptr,
1486	bool IsExpanding = false);
1487	inline SDValue getStridedLoadVP(
1488	ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, EVT VT, const SDLoc &DL,
1489	SDValue Chain, SDValue Ptr, SDValue Offset, SDValue Stride, SDValue Mask,
1490	SDValue EVL, MachinePointerInfo PtrInfo, EVT MemVT,
1491	MaybeAlign Alignment = MaybeAlign(),
1492	MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
1493	const AAMDNodes &AAInfo = AAMDNodes(), const MDNode *Ranges = nullptr,
1494	bool IsExpanding = false) {
1495	// Ensures that codegen never sees a None Alignment.
1496	return getStridedLoadVP(AM, ExtType, VT, DL, Chain, Ptr, Offset, Stride,
1497	Mask, EVL, PtrInfo, MemVT,
1498	Alignment: Alignment.value_or(u: getEVTAlign(MemoryVT: MemVT)), MMOFlags,
1499	AAInfo, Ranges, IsExpanding);
1500	}
1501	SDValue getStridedLoadVP(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
1502	EVT VT, const SDLoc &DL, SDValue Chain, SDValue Ptr,
1503	SDValue Offset, SDValue Stride, SDValue Mask,
1504	SDValue EVL, EVT MemVT, MachineMemOperand *MMO,
1505	bool IsExpanding = false);
1506	SDValue getStridedLoadVP(EVT VT, const SDLoc &DL, SDValue Chain, SDValue Ptr,
1507	SDValue Stride, SDValue Mask, SDValue EVL,
1508	MachinePointerInfo PtrInfo, MaybeAlign Alignment,
1509	MachineMemOperand::Flags MMOFlags,
1510	const AAMDNodes &AAInfo,
1511	const MDNode *Ranges = nullptr,
1512	bool IsExpanding = false);
1513	SDValue getStridedLoadVP(EVT VT, const SDLoc &DL, SDValue Chain, SDValue Ptr,
1514	SDValue Stride, SDValue Mask, SDValue EVL,
1515	MachineMemOperand *MMO, bool IsExpanding = false);
1516	SDValue
1517	getExtStridedLoadVP(ISD::LoadExtType ExtType, const SDLoc &DL, EVT VT,
1518	SDValue Chain, SDValue Ptr, SDValue Stride, SDValue Mask,
1519	SDValue EVL, MachinePointerInfo PtrInfo, EVT MemVT,
1520	MaybeAlign Alignment, MachineMemOperand::Flags MMOFlags,
1521	const AAMDNodes &AAInfo, bool IsExpanding = false);
1522	SDValue getExtStridedLoadVP(ISD::LoadExtType ExtType, const SDLoc &DL, EVT VT,
1523	SDValue Chain, SDValue Ptr, SDValue Stride,
1524	SDValue Mask, SDValue EVL, EVT MemVT,
1525	MachineMemOperand *MMO, bool IsExpanding = false);
1526	SDValue getIndexedStridedLoadVP(SDValue OrigLoad, const SDLoc &DL,
1527	SDValue Base, SDValue Offset,
1528	ISD::MemIndexedMode AM);
1529	SDValue getStridedStoreVP(SDValue Chain, const SDLoc &DL, SDValue Val,
1530	SDValue Ptr, SDValue Offset, SDValue Stride,
1531	SDValue Mask, SDValue EVL, EVT MemVT,
1532	MachineMemOperand *MMO, ISD::MemIndexedMode AM,
1533	bool IsTruncating = false,
1534	bool IsCompressing = false);
1535	SDValue getTruncStridedStoreVP(SDValue Chain, const SDLoc &DL, SDValue Val,
1536	SDValue Ptr, SDValue Stride, SDValue Mask,
1537	SDValue EVL, MachinePointerInfo PtrInfo,
1538	EVT SVT, Align Alignment,
1539	MachineMemOperand::Flags MMOFlags,
1540	const AAMDNodes &AAInfo,
1541	bool IsCompressing = false);
1542	SDValue getTruncStridedStoreVP(SDValue Chain, const SDLoc &DL, SDValue Val,
1543	SDValue Ptr, SDValue Stride, SDValue Mask,
1544	SDValue EVL, EVT SVT, MachineMemOperand *MMO,
1545	bool IsCompressing = false);
1546	SDValue getIndexedStridedStoreVP(SDValue OrigStore, const SDLoc &DL,
1547	SDValue Base, SDValue Offset,
1548	ISD::MemIndexedMode AM);
1549
1550	SDValue getGatherVP(SDVTList VTs, EVT VT, const SDLoc &dl,
1551	ArrayRef<SDValue> Ops, MachineMemOperand *MMO,
1552	ISD::MemIndexType IndexType);
1553	SDValue getScatterVP(SDVTList VTs, EVT VT, const SDLoc &dl,
1554	ArrayRef<SDValue> Ops, MachineMemOperand *MMO,
1555	ISD::MemIndexType IndexType);
1556
1557	SDValue getMaskedLoad(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Base,
1558	SDValue Offset, SDValue Mask, SDValue Src0, EVT MemVT,
1559	MachineMemOperand *MMO, ISD::MemIndexedMode AM,
1560	ISD::LoadExtType, bool IsExpanding = false);
1561	SDValue getIndexedMaskedLoad(SDValue OrigLoad, const SDLoc &dl, SDValue Base,
1562	SDValue Offset, ISD::MemIndexedMode AM);
1563	SDValue getMaskedStore(SDValue Chain, const SDLoc &dl, SDValue Val,
1564	SDValue Base, SDValue Offset, SDValue Mask, EVT MemVT,
1565	MachineMemOperand *MMO, ISD::MemIndexedMode AM,
1566	bool IsTruncating = false, bool IsCompressing = false);
1567	SDValue getIndexedMaskedStore(SDValue OrigStore, const SDLoc &dl,
1568	SDValue Base, SDValue Offset,
1569	ISD::MemIndexedMode AM);
1570	SDValue getMaskedGather(SDVTList VTs, EVT MemVT, const SDLoc &dl,
1571	ArrayRef<SDValue> Ops, MachineMemOperand *MMO,
1572	ISD::MemIndexType IndexType, ISD::LoadExtType ExtTy);
1573	SDValue getMaskedScatter(SDVTList VTs, EVT MemVT, const SDLoc &dl,
1574	ArrayRef<SDValue> Ops, MachineMemOperand *MMO,
1575	ISD::MemIndexType IndexType,
1576	bool IsTruncating = false);
1577
1578	SDValue getGetFPEnv(SDValue Chain, const SDLoc &dl, SDValue Ptr, EVT MemVT,
1579	MachineMemOperand *MMO);
1580	SDValue getSetFPEnv(SDValue Chain, const SDLoc &dl, SDValue Ptr, EVT MemVT,
1581	MachineMemOperand *MMO);
1582
1583	/// Construct a node to track a Value* through the backend.
1584	SDValue getSrcValue(const Value *v);
1585
1586	/// Return an MDNodeSDNode which holds an MDNode.
1587	SDValue getMDNode(const MDNode *MD);
1588
1589	/// Return a bitcast using the SDLoc of the value operand, and casting to the
1590	/// provided type. Use getNode to set a custom SDLoc.
1591	SDValue getBitcast(EVT VT, SDValue V);
1592
1593	/// Return an AddrSpaceCastSDNode.
1594	SDValue getAddrSpaceCast(const SDLoc &dl, EVT VT, SDValue Ptr, unsigned SrcAS,
1595	unsigned DestAS);
1596
1597	/// Return a freeze using the SDLoc of the value operand.
1598	SDValue getFreeze(SDValue V);
1599
1600	/// Return an AssertAlignSDNode.
1601	SDValue getAssertAlign(const SDLoc &DL, SDValue V, Align A);
1602
1603	/// Swap N1 and N2 if Opcode is a commutative binary opcode
1604	/// and the canonical form expects the opposite order.
1605	void canonicalizeCommutativeBinop(unsigned Opcode, SDValue &N1,
1606	SDValue &N2) const;
1607
1608	/// Return the specified value casted to
1609	/// the target's desired shift amount type.
1610	SDValue getShiftAmountOperand(EVT LHSTy, SDValue Op);
1611
1612	/// Expand the specified \c ISD::VAARG node as the Legalize pass would.
1613	SDValue expandVAArg(SDNode *Node);
1614
1615	/// Expand the specified \c ISD::VACOPY node as the Legalize pass would.
1616	SDValue expandVACopy(SDNode *Node);
1617
1618	/// Return a GlobalAddress of the function from the current module with
1619	/// name matching the given ExternalSymbol. Additionally can provide the
1620	/// matched function.
1621	/// Panic if the function doesn't exist.
1622	SDValue getSymbolFunctionGlobalAddress(SDValue Op,
1623	Function **TargetFunction = nullptr);
1624
1625	/// *Mutate* the specified node in-place to have the
1626	/// specified operands. If the resultant node already exists in the DAG,
1627	/// this does not modify the specified node, instead it returns the node that
1628	/// already exists. If the resultant node does not exist in the DAG, the
1629	/// input node is returned. As a degenerate case, if you specify the same
1630	/// input operands as the node already has, the input node is returned.
1631	SDNode *UpdateNodeOperands(SDNode *N, SDValue Op);
1632	SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2);
1633	SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
1634	SDValue Op3);
1635	SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
1636	SDValue Op3, SDValue Op4);
1637	SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
1638	SDValue Op3, SDValue Op4, SDValue Op5);
1639	SDNode *UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops);
1640
1641	/// Creates a new TokenFactor containing \p Vals. If \p Vals contains 64k
1642	/// values or more, move values into new TokenFactors in 64k-1 blocks, until
1643	/// the final TokenFactor has less than 64k operands.
1644	SDValue getTokenFactor(const SDLoc &DL, SmallVectorImpl<SDValue> &Vals);
1645
1646	/// *Mutate* the specified machine node's memory references to the provided
1647	/// list.
1648	void setNodeMemRefs(MachineSDNode *N,
1649	ArrayRef<MachineMemOperand *> NewMemRefs);
1650
1651	// Calculate divergence of node \p N based on its operands.
1652	bool calculateDivergence(SDNode *N);
1653
1654	// Propagates the change in divergence to users
1655	void updateDivergence(SDNode * N);
1656
1657	/// These are used for target selectors to *mutate* the
1658	/// specified node to have the specified return type, Target opcode, and
1659	/// operands. Note that target opcodes are stored as
1660	/// ~TargetOpcode in the node opcode field. The resultant node is returned.
1661	SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT);
1662	SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT, SDValue Op1);
1663	SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT,
1664	SDValue Op1, SDValue Op2);
1665	SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT,
1666	SDValue Op1, SDValue Op2, SDValue Op3);
1667	SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT,
1668	ArrayRef<SDValue> Ops);
1669	SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1, EVT VT2);
1670	SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1,
1671	EVT VT2, ArrayRef<SDValue> Ops);
1672	SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1,
1673	EVT VT2, EVT VT3, ArrayRef<SDValue> Ops);
1674	SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1,
1675	EVT VT2, SDValue Op1, SDValue Op2);
1676	SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, SDVTList VTs,
1677	ArrayRef<SDValue> Ops);
1678
1679	/// This *mutates* the specified node to have the specified
1680	/// return type, opcode, and operands.
1681	SDNode *MorphNodeTo(SDNode *N, unsigned Opc, SDVTList VTs,
1682	ArrayRef<SDValue> Ops);
1683
1684	/// Mutate the specified strict FP node to its non-strict equivalent,
1685	/// unlinking the node from its chain and dropping the metadata arguments.
1686	/// The node must be a strict FP node.
1687	SDNode *mutateStrictFPToFP(SDNode *Node);
1688
1689	/// These are used for target selectors to create a new node
1690	/// with specified return type(s), MachineInstr opcode, and operands.
1691	///
1692	/// Note that getMachineNode returns the resultant node. If there is already
1693	/// a node of the specified opcode and operands, it returns that node instead
1694	/// of the current one.
1695	MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT);
1696	MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT,
1697	SDValue Op1);
1698	MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT,
1699	SDValue Op1, SDValue Op2);
1700	MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT,
1701	SDValue Op1, SDValue Op2, SDValue Op3);
1702	MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT,
1703	ArrayRef<SDValue> Ops);
1704	MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1,
1705	EVT VT2, SDValue Op1, SDValue Op2);
1706	MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1,
1707	EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3);
1708	MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1,
1709	EVT VT2, ArrayRef<SDValue> Ops);
1710	MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1,
1711	EVT VT2, EVT VT3, SDValue Op1, SDValue Op2);
1712	MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1,
1713	EVT VT2, EVT VT3, SDValue Op1, SDValue Op2,
1714	SDValue Op3);
1715	MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1,
1716	EVT VT2, EVT VT3, ArrayRef<SDValue> Ops);
1717	MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl,
1718	ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops);
1719	MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, SDVTList VTs,
1720	ArrayRef<SDValue> Ops);
1721
1722	/// A convenience function for creating TargetInstrInfo::EXTRACT_SUBREG nodes.
1723	SDValue getTargetExtractSubreg(int SRIdx, const SDLoc &DL, EVT VT,
1724	SDValue Operand);
1725
1726	/// A convenience function for creating TargetInstrInfo::INSERT_SUBREG nodes.
1727	SDValue getTargetInsertSubreg(int SRIdx, const SDLoc &DL, EVT VT,
1728	SDValue Operand, SDValue Subreg);
1729
1730	/// Get the specified node if it's already available, or else return NULL.
1731	SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTList,
1732	ArrayRef<SDValue> Ops, const SDNodeFlags Flags);
1733	SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTList,
1734	ArrayRef<SDValue> Ops);
1735
1736	/// Check if a node exists without modifying its flags.
1737	bool doesNodeExist(unsigned Opcode, SDVTList VTList, ArrayRef<SDValue> Ops);
1738
1739	/// Creates a SDDbgValue node.
1740	SDDbgValue *getDbgValue(DIVariable *Var, DIExpression *Expr, SDNode *N,
1741	unsigned R, bool IsIndirect, const DebugLoc &DL,
1742	unsigned O);
1743
1744	/// Creates a constant SDDbgValue node.
1745	SDDbgValue *getConstantDbgValue(DIVariable *Var, DIExpression *Expr,
1746	const Value *C, const DebugLoc &DL,
1747	unsigned O);
1748
1749	/// Creates a FrameIndex SDDbgValue node.
1750	SDDbgValue *getFrameIndexDbgValue(DIVariable *Var, DIExpression *Expr,
1751	unsigned FI, bool IsIndirect,
1752	const DebugLoc &DL, unsigned O);
1753
1754	/// Creates a FrameIndex SDDbgValue node.
1755	SDDbgValue *getFrameIndexDbgValue(DIVariable *Var, DIExpression *Expr,
1756	unsigned FI,
1757	ArrayRef<SDNode *> Dependencies,
1758	bool IsIndirect, const DebugLoc &DL,
1759	unsigned O);
1760
1761	/// Creates a VReg SDDbgValue node.
1762	SDDbgValue *getVRegDbgValue(DIVariable *Var, DIExpression *Expr,
1763	unsigned VReg, bool IsIndirect,
1764	const DebugLoc &DL, unsigned O);
1765
1766	/// Creates a SDDbgValue node from a list of locations.
1767	SDDbgValue *getDbgValueList(DIVariable *Var, DIExpression *Expr,
1768	ArrayRef<SDDbgOperand> Locs,
1769	ArrayRef<SDNode *> Dependencies, bool IsIndirect,
1770	const DebugLoc &DL, unsigned O, bool IsVariadic);
1771
1772	/// Creates a SDDbgLabel node.
1773	SDDbgLabel *getDbgLabel(DILabel *Label, const DebugLoc &DL, unsigned O);
1774
1775	/// Transfer debug values from one node to another, while optionally
1776	/// generating fragment expressions for split-up values. If \p InvalidateDbg
1777	/// is set, debug values are invalidated after they are transferred.
1778	void transferDbgValues(SDValue From, SDValue To, unsigned OffsetInBits = 0,
1779	unsigned SizeInBits = 0, bool InvalidateDbg = true);
1780
1781	/// Remove the specified node from the system. If any of its
1782	/// operands then becomes dead, remove them as well. Inform UpdateListener
1783	/// for each node deleted.
1784	void RemoveDeadNode(SDNode *N);
1785
1786	/// This method deletes the unreachable nodes in the
1787	/// given list, and any nodes that become unreachable as a result.
1788	void RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes);
1789
1790	/// Modify anything using 'From' to use 'To' instead.
1791	/// This can cause recursive merging of nodes in the DAG. Use the first
1792	/// version if 'From' is known to have a single result, use the second
1793	/// if you have two nodes with identical results (or if 'To' has a superset
1794	/// of the results of 'From'), use the third otherwise.
1795	///
1796	/// These methods all take an optional UpdateListener, which (if not null) is
1797	/// informed about nodes that are deleted and modified due to recursive
1798	/// changes in the dag.
1799	///
1800	/// These functions only replace all existing uses. It's possible that as
1801	/// these replacements are being performed, CSE may cause the From node
1802	/// to be given new uses. These new uses of From are left in place, and
1803	/// not automatically transferred to To.
1804	///
1805	void ReplaceAllUsesWith(SDValue From, SDValue To);
1806	void ReplaceAllUsesWith(SDNode *From, SDNode *To);
1807	void ReplaceAllUsesWith(SDNode *From, const SDValue *To);
1808
1809	/// Replace any uses of From with To, leaving
1810	/// uses of other values produced by From.getNode() alone.
1811	void ReplaceAllUsesOfValueWith(SDValue From, SDValue To);
1812
1813	/// Like ReplaceAllUsesOfValueWith, but for multiple values at once.
1814	/// This correctly handles the case where
1815	/// there is an overlap between the From values and the To values.
1816	void ReplaceAllUsesOfValuesWith(const SDValue *From, const SDValue *To,
1817	unsigned Num);
1818
1819	/// If an existing load has uses of its chain, create a token factor node with
1820	/// that chain and the new memory node's chain and update users of the old
1821	/// chain to the token factor. This ensures that the new memory node will have
1822	/// the same relative memory dependency position as the old load. Returns the
1823	/// new merged load chain.
1824	SDValue makeEquivalentMemoryOrdering(SDValue OldChain, SDValue NewMemOpChain);
1825
1826	/// If an existing load has uses of its chain, create a token factor node with
1827	/// that chain and the new memory node's chain and update users of the old
1828	/// chain to the token factor. This ensures that the new memory node will have
1829	/// the same relative memory dependency position as the old load. Returns the
1830	/// new merged load chain.
1831	SDValue makeEquivalentMemoryOrdering(LoadSDNode *OldLoad, SDValue NewMemOp);
1832
1833	/// Topological-sort the AllNodes list and a
1834	/// assign a unique node id for each node in the DAG based on their
1835	/// topological order. Returns the number of nodes.
1836	unsigned AssignTopologicalOrder();
1837
1838	/// Move node N in the AllNodes list to be immediately
1839	/// before the given iterator Position. This may be used to update the
1840	/// topological ordering when the list of nodes is modified.
1841	void RepositionNode(allnodes_iterator Position, SDNode *N) {
1842	AllNodes.insert(where: Position, New: AllNodes.remove(IT: N));
1843	}
1844
1845	/// Returns an APFloat semantics tag appropriate for the given type. If VT is
1846	/// a vector type, the element semantics are returned.
1847	static const fltSemantics &EVTToAPFloatSemantics(EVT VT) {
1848	switch (VT.getScalarType().getSimpleVT().SimpleTy) {
1849	default: llvm_unreachable("Unknown FP format");
1850	case MVT::f16: return APFloat::IEEEhalf();
1851	case MVT::bf16: return APFloat::BFloat();
1852	case MVT::f32: return APFloat::IEEEsingle();
1853	case MVT::f64: return APFloat::IEEEdouble();
1854	case MVT::f80: return APFloat::x87DoubleExtended();
1855	case MVT::f128: return APFloat::IEEEquad();
1856	case MVT::ppcf128: return APFloat::PPCDoubleDouble();
1857	}
1858	}
1859
1860	/// Add a dbg_value SDNode. If SD is non-null that means the
1861	/// value is produced by SD.
1862	void AddDbgValue(SDDbgValue *DB, bool isParameter);
1863
1864	/// Add a dbg_label SDNode.
1865	void AddDbgLabel(SDDbgLabel *DB);
1866
1867	/// Get the debug values which reference the given SDNode.
1868	ArrayRef<SDDbgValue*> GetDbgValues(const SDNode* SD) const {
1869	return DbgInfo->getSDDbgValues(Node: SD);
1870	}
1871
1872	public:
1873	/// Return true if there are any SDDbgValue nodes associated
1874	/// with this SelectionDAG.
1875	bool hasDebugValues() const { return !DbgInfo->empty(); }
1876
1877	SDDbgInfo::DbgIterator DbgBegin() const { return DbgInfo->DbgBegin(); }
1878	SDDbgInfo::DbgIterator DbgEnd() const { return DbgInfo->DbgEnd(); }
1879
1880	SDDbgInfo::DbgIterator ByvalParmDbgBegin() const {
1881	return DbgInfo->ByvalParmDbgBegin();
1882	}
1883	SDDbgInfo::DbgIterator ByvalParmDbgEnd() const {
1884	return DbgInfo->ByvalParmDbgEnd();
1885	}
1886
1887	SDDbgInfo::DbgLabelIterator DbgLabelBegin() const {
1888	return DbgInfo->DbgLabelBegin();
1889	}
1890	SDDbgInfo::DbgLabelIterator DbgLabelEnd() const {
1891	return DbgInfo->DbgLabelEnd();
1892	}
1893
1894	/// To be invoked on an SDNode that is slated to be erased. This
1895	/// function mirrors \c llvm::salvageDebugInfo.
1896	void salvageDebugInfo(SDNode &N);
1897
1898	void dump() const;
1899
1900	/// In most cases this function returns the ABI alignment for a given type,
1901	/// except for illegal vector types where the alignment exceeds that of the
1902	/// stack. In such cases we attempt to break the vector down to a legal type
1903	/// and return the ABI alignment for that instead.
1904	Align getReducedAlign(EVT VT, bool UseABI);
1905
1906	/// Create a stack temporary based on the size in bytes and the alignment
1907	SDValue CreateStackTemporary(TypeSize Bytes, Align Alignment);
1908
1909	/// Create a stack temporary, suitable for holding the specified value type.
1910	/// If minAlign is specified, the slot size will have at least that alignment.
1911	SDValue CreateStackTemporary(EVT VT, unsigned minAlign = 1);
1912
1913	/// Create a stack temporary suitable for holding either of the specified
1914	/// value types.
1915	SDValue CreateStackTemporary(EVT VT1, EVT VT2);
1916
1917	SDValue FoldSymbolOffset(unsigned Opcode, EVT VT,
1918	const GlobalAddressSDNode *GA,
1919	const SDNode *N2);
1920
1921	SDValue FoldConstantArithmetic(unsigned Opcode, const SDLoc &DL, EVT VT,
1922	ArrayRef<SDValue> Ops);
1923
1924	/// Fold floating-point operations when all operands are constants and/or
1925	/// undefined.
1926	SDValue foldConstantFPMath(unsigned Opcode, const SDLoc &DL, EVT VT,
1927	ArrayRef<SDValue> Ops);
1928
1929	/// Constant fold a setcc to true or false.
1930	SDValue FoldSetCC(EVT VT, SDValue N1, SDValue N2, ISD::CondCode Cond,
1931	const SDLoc &dl);
1932
1933	/// Return true if the sign bit of Op is known to be zero.
1934	/// We use this predicate to simplify operations downstream.
1935	bool SignBitIsZero(SDValue Op, unsigned Depth = 0) const;
1936
1937	/// Return true if 'Op & Mask' is known to be zero. We
1938	/// use this predicate to simplify operations downstream. Op and Mask are
1939	/// known to be the same type.
1940	bool MaskedValueIsZero(SDValue Op, const APInt &Mask,
1941	unsigned Depth = 0) const;
1942
1943	/// Return true if 'Op & Mask' is known to be zero in DemandedElts. We
1944	/// use this predicate to simplify operations downstream. Op and Mask are
1945	/// known to be the same type.
1946	bool MaskedValueIsZero(SDValue Op, const APInt &Mask,
1947	const APInt &DemandedElts, unsigned Depth = 0) const;
1948
1949	/// Return true if 'Op' is known to be zero in DemandedElts. We
1950	/// use this predicate to simplify operations downstream.
1951	bool MaskedVectorIsZero(SDValue Op, const APInt &DemandedElts,
1952	unsigned Depth = 0) const;
1953
1954	/// Return true if '(Op & Mask) == Mask'.
1955	/// Op and Mask are known to be the same type.
1956	bool MaskedValueIsAllOnes(SDValue Op, const APInt &Mask,
1957	unsigned Depth = 0) const;
1958
1959	/// For each demanded element of a vector, see if it is known to be zero.
1960	APInt computeVectorKnownZeroElements(SDValue Op, const APInt &DemandedElts,
1961	unsigned Depth = 0) const;
1962
1963	/// Determine which bits of Op are known to be either zero or one and return
1964	/// them in Known. For vectors, the known bits are those that are shared by
1965	/// every vector element.
1966	/// Targets can implement the computeKnownBitsForTargetNode method in the
1967	/// TargetLowering class to allow target nodes to be understood.
1968	KnownBits computeKnownBits(SDValue Op, unsigned Depth = 0) const;
1969
1970	/// Determine which bits of Op are known to be either zero or one and return
1971	/// them in Known. The DemandedElts argument allows us to only collect the
1972	/// known bits that are shared by the requested vector elements.
1973	/// Targets can implement the computeKnownBitsForTargetNode method in the
1974	/// TargetLowering class to allow target nodes to be understood.
1975	KnownBits computeKnownBits(SDValue Op, const APInt &DemandedElts,
1976	unsigned Depth = 0) const;
1977
1978	/// Used to represent the possible overflow behavior of an operation.
1979	/// Never: the operation cannot overflow.
1980	/// Always: the operation will always overflow.
1981	/// Sometime: the operation may or may not overflow.
1982	enum OverflowKind {
1983	OFK_Never,
1984	OFK_Sometime,
1985	OFK_Always,
1986	};
1987
1988	/// Determine if the result of the signed addition of 2 nodes can overflow.
1989	OverflowKind computeOverflowForSignedAdd(SDValue N0, SDValue N1) const;
1990
1991	/// Determine if the result of the unsigned addition of 2 nodes can overflow.
1992	OverflowKind computeOverflowForUnsignedAdd(SDValue N0, SDValue N1) const;
1993
1994	/// Determine if the result of the addition of 2 nodes can overflow.
1995	OverflowKind computeOverflowForAdd(bool IsSigned, SDValue N0,
1996	SDValue N1) const {
1997	return IsSigned ? computeOverflowForSignedAdd(N0, N1)
1998	: computeOverflowForUnsignedAdd(N0, N1);
1999	}
2000
2001	/// Determine if the result of the addition of 2 nodes can never overflow.
2002	bool willNotOverflowAdd(bool IsSigned, SDValue N0, SDValue N1) const {
2003	return computeOverflowForAdd(IsSigned, N0, N1) == OFK_Never;
2004	}
2005
2006	/// Determine if the result of the signed sub of 2 nodes can overflow.
2007	OverflowKind computeOverflowForSignedSub(SDValue N0, SDValue N1) const;
2008
2009	/// Determine if the result of the unsigned sub of 2 nodes can overflow.
2010	OverflowKind computeOverflowForUnsignedSub(SDValue N0, SDValue N1) const;
2011
2012	/// Determine if the result of the sub of 2 nodes can overflow.
2013	OverflowKind computeOverflowForSub(bool IsSigned, SDValue N0,
2014	SDValue N1) const {
2015	return IsSigned ? computeOverflowForSignedSub(N0, N1)
2016	: computeOverflowForUnsignedSub(N0, N1);
2017	}
2018
2019	/// Determine if the result of the sub of 2 nodes can never overflow.
2020	bool willNotOverflowSub(bool IsSigned, SDValue N0, SDValue N1) const {
2021	return computeOverflowForSub(IsSigned, N0, N1) == OFK_Never;
2022	}
2023
2024	/// Determine if the result of the signed mul of 2 nodes can overflow.
2025	OverflowKind computeOverflowForSignedMul(SDValue N0, SDValue N1) const;
2026
2027	/// Determine if the result of the unsigned mul of 2 nodes can overflow.
2028	OverflowKind computeOverflowForUnsignedMul(SDValue N0, SDValue N1) const;
2029
2030	/// Determine if the result of the mul of 2 nodes can overflow.
2031	OverflowKind computeOverflowForMul(bool IsSigned, SDValue N0,
2032	SDValue N1) const {
2033	return IsSigned ? computeOverflowForSignedMul(N0, N1)
2034	: computeOverflowForUnsignedMul(N0, N1);
2035	}
2036
2037	/// Determine if the result of the mul of 2 nodes can never overflow.
2038	bool willNotOverflowMul(bool IsSigned, SDValue N0, SDValue N1) const {
2039	return computeOverflowForMul(IsSigned, N0, N1) == OFK_Never;
2040	}
2041
2042	/// Test if the given value is known to have exactly one bit set. This differs
2043	/// from computeKnownBits in that it doesn't necessarily determine which bit
2044	/// is set.
2045	bool isKnownToBeAPowerOfTwo(SDValue Val, unsigned Depth = 0) const;
2046
2047	/// Return the number of times the sign bit of the register is replicated into
2048	/// the other bits. We know that at least 1 bit is always equal to the sign
2049	/// bit (itself), but other cases can give us information. For example,
2050	/// immediately after an "SRA X, 2", we know that the top 3 bits are all equal
2051	/// to each other, so we return 3. Targets can implement the
2052	/// ComputeNumSignBitsForTarget method in the TargetLowering class to allow
2053	/// target nodes to be understood.
2054	unsigned ComputeNumSignBits(SDValue Op, unsigned Depth = 0) const;
2055
2056	/// Return the number of times the sign bit of the register is replicated into
2057	/// the other bits. We know that at least 1 bit is always equal to the sign
2058	/// bit (itself), but other cases can give us information. For example,
2059	/// immediately after an "SRA X, 2", we know that the top 3 bits are all equal
2060	/// to each other, so we return 3. The DemandedElts argument allows
2061	/// us to only collect the minimum sign bits of the requested vector elements.
2062	/// Targets can implement the ComputeNumSignBitsForTarget method in the
2063	/// TargetLowering class to allow target nodes to be understood.
2064	unsigned ComputeNumSignBits(SDValue Op, const APInt &DemandedElts,
2065	unsigned Depth = 0) const;
2066
2067	/// Get the upper bound on bit size for this Value \p Op as a signed integer.
2068	/// i.e. x == sext(trunc(x to MaxSignedBits) to bitwidth(x)).
2069	/// Similar to the APInt::getSignificantBits function.
2070	/// Helper wrapper to ComputeNumSignBits.
2071	unsigned ComputeMaxSignificantBits(SDValue Op, unsigned Depth = 0) const;
2072
2073	/// Get the upper bound on bit size for this Value \p Op as a signed integer.
2074	/// i.e. x == sext(trunc(x to MaxSignedBits) to bitwidth(x)).
2075	/// Similar to the APInt::getSignificantBits function.
2076	/// Helper wrapper to ComputeNumSignBits.
2077	unsigned ComputeMaxSignificantBits(SDValue Op, const APInt &DemandedElts,
2078	unsigned Depth = 0) const;
2079
2080	/// Return true if this function can prove that \p Op is never poison
2081	/// and, if \p PoisonOnly is false, does not have undef bits.
2082	bool isGuaranteedNotToBeUndefOrPoison(SDValue Op, bool PoisonOnly = false,
2083	unsigned Depth = 0) const;
2084
2085	/// Return true if this function can prove that \p Op is never poison
2086	/// and, if \p PoisonOnly is false, does not have undef bits. The DemandedElts
2087	/// argument limits the check to the requested vector elements.
2088	bool isGuaranteedNotToBeUndefOrPoison(SDValue Op, const APInt &DemandedElts,
2089	bool PoisonOnly = false,
2090	unsigned Depth = 0) const;
2091
2092	/// Return true if this function can prove that \p Op is never poison.
2093	bool isGuaranteedNotToBePoison(SDValue Op, unsigned Depth = 0) const {
2094	return isGuaranteedNotToBeUndefOrPoison(Op, /*PoisonOnly*/ PoisonOnly: true, Depth);
2095	}
2096
2097	/// Return true if this function can prove that \p Op is never poison. The
2098	/// DemandedElts argument limits the check to the requested vector elements.
2099	bool isGuaranteedNotToBePoison(SDValue Op, const APInt &DemandedElts,
2100	unsigned Depth = 0) const {
2101	return isGuaranteedNotToBeUndefOrPoison(Op, DemandedElts,
2102	/*PoisonOnly*/ PoisonOnly: true, Depth);
2103	}
2104
2105	/// Return true if Op can create undef or poison from non-undef & non-poison
2106	/// operands. The DemandedElts argument limits the check to the requested
2107	/// vector elements.
2108	///
2109	/// \p ConsiderFlags controls whether poison producing flags on the
2110	/// instruction are considered. This can be used to see if the instruction
2111	/// could still introduce undef or poison even without poison generating flags
2112	/// which might be on the instruction. (i.e. could the result of
2113	/// Op->dropPoisonGeneratingFlags() still create poison or undef)
2114	bool canCreateUndefOrPoison(SDValue Op, const APInt &DemandedElts,
2115	bool PoisonOnly = false,
2116	bool ConsiderFlags = true,
2117	unsigned Depth = 0) const;
2118
2119	/// Return true if Op can create undef or poison from non-undef & non-poison
2120	/// operands.
2121	///
2122	/// \p ConsiderFlags controls whether poison producing flags on the
2123	/// instruction are considered. This can be used to see if the instruction
2124	/// could still introduce undef or poison even without poison generating flags
2125	/// which might be on the instruction. (i.e. could the result of
2126	/// Op->dropPoisonGeneratingFlags() still create poison or undef)
2127	bool canCreateUndefOrPoison(SDValue Op, bool PoisonOnly = false,
2128	bool ConsiderFlags = true,
2129	unsigned Depth = 0) const;
2130
2131	/// Return true if the specified operand is an ISD::OR or ISD::XOR node
2132	/// that can be treated as an ISD::ADD node.
2133	/// or(x,y) == add(x,y) iff haveNoCommonBitsSet(x,y)
2134	/// xor(x,y) == add(x,y) iff isMinSignedConstant(y)
2135	bool isADDLike(SDValue Op) const;
2136
2137	/// Return true if the specified operand is an ISD::ADD with a ConstantSDNode
2138	/// on the right-hand side, or if it is an ISD::OR with a ConstantSDNode that
2139	/// is guaranteed to have the same semantics as an ADD. This handles the
2140	/// equivalence:
2141	/// X|Cst == X+Cst iff X&Cst = 0.
2142	bool isBaseWithConstantOffset(SDValue Op) const;
2143
2144	/// Test whether the given SDValue (or all elements of it, if it is a
2145	/// vector) is known to never be NaN. If \p SNaN is true, returns if \p Op is
2146	/// known to never be a signaling NaN (it may still be a qNaN).
2147	bool isKnownNeverNaN(SDValue Op, bool SNaN = false, unsigned Depth = 0) const;
2148
2149	/// \returns true if \p Op is known to never be a signaling NaN.
2150	bool isKnownNeverSNaN(SDValue Op, unsigned Depth = 0) const {
2151	return isKnownNeverNaN(Op, SNaN: true, Depth);
2152	}
2153
2154	/// Test whether the given floating point SDValue is known to never be
2155	/// positive or negative zero.
2156	bool isKnownNeverZeroFloat(SDValue Op) const;
2157
2158	/// Test whether the given SDValue is known to contain non-zero value(s).
2159	bool isKnownNeverZero(SDValue Op, unsigned Depth = 0) const;
2160
2161	/// Test whether two SDValues are known to compare equal. This
2162	/// is true if they are the same value, or if one is negative zero and the
2163	/// other positive zero.
2164	bool isEqualTo(SDValue A, SDValue B) const;
2165
2166	/// Return true if A and B have no common bits set. As an example, this can
2167	/// allow an 'add' to be transformed into an 'or'.
2168	bool haveNoCommonBitsSet(SDValue A, SDValue B) const;
2169
2170	/// Test whether \p V has a splatted value for all the demanded elements.
2171	///
2172	/// On success \p UndefElts will indicate the elements that have UNDEF
2173	/// values instead of the splat value, this is only guaranteed to be correct
2174	/// for \p DemandedElts.
2175	///
2176	/// NOTE: The function will return true for a demanded splat of UNDEF values.
2177	bool isSplatValue(SDValue V, const APInt &DemandedElts, APInt &UndefElts,
2178	unsigned Depth = 0) const;
2179
2180	/// Test whether \p V has a splatted value.
2181	bool isSplatValue(SDValue V, bool AllowUndefs = false) const;
2182
2183	/// If V is a splatted value, return the source vector and its splat index.
2184	SDValue getSplatSourceVector(SDValue V, int &SplatIndex);
2185
2186	/// If V is a splat vector, return its scalar source operand by extracting
2187	/// that element from the source vector. If LegalTypes is true, this method
2188	/// may only return a legally-typed splat value. If it cannot legalize the
2189	/// splatted value it will return SDValue().
2190	SDValue getSplatValue(SDValue V, bool LegalTypes = false);
2191
2192	/// If a SHL/SRA/SRL node \p V has a constant or splat constant shift amount
2193	/// that is less than the element bit-width of the shift node, return it.
2194	const APInt *getValidShiftAmountConstant(SDValue V,
2195	const APInt &DemandedElts) const;
2196
2197	/// If a SHL/SRA/SRL node \p V has constant shift amounts that are all less
2198	/// than the element bit-width of the shift node, return the minimum value.
2199	const APInt *
2200	getValidMinimumShiftAmountConstant(SDValue V,
2201	const APInt &DemandedElts) const;
2202
2203	/// If a SHL/SRA/SRL node \p V has constant shift amounts that are all less
2204	/// than the element bit-width of the shift node, return the maximum value.
2205	const APInt *
2206	getValidMaximumShiftAmountConstant(SDValue V,
2207	const APInt &DemandedElts) const;
2208
2209	/// Match a binop + shuffle pyramid that represents a horizontal reduction
2210	/// over the elements of a vector starting from the EXTRACT_VECTOR_ELT node /p
2211	/// Extract. The reduction must use one of the opcodes listed in /p
2212	/// CandidateBinOps and on success /p BinOp will contain the matching opcode.
2213	/// Returns the vector that is being reduced on, or SDValue() if a reduction
2214	/// was not matched. If \p AllowPartials is set then in the case of a
2215	/// reduction pattern that only matches the first few stages, the extracted
2216	/// subvector of the start of the reduction is returned.
2217	SDValue matchBinOpReduction(SDNode *Extract, ISD::NodeType &BinOp,
2218	ArrayRef<ISD::NodeType> CandidateBinOps,
2219	bool AllowPartials = false);
2220
2221	/// Utility function used by legalize and lowering to
2222	/// "unroll" a vector operation by splitting out the scalars and operating
2223	/// on each element individually. If the ResNE is 0, fully unroll the vector
2224	/// op. If ResNE is less than the width of the vector op, unroll up to ResNE.
2225	/// If the ResNE is greater than the width of the vector op, unroll the
2226	/// vector op and fill the end of the resulting vector with UNDEFS.
2227	SDValue UnrollVectorOp(SDNode *N, unsigned ResNE = 0);
2228
2229	/// Like UnrollVectorOp(), but for the [US](ADD|SUB|MUL)O family of opcodes.
2230	/// This is a separate function because those opcodes have two results.
2231	std::pair<SDValue, SDValue> UnrollVectorOverflowOp(SDNode *N,
2232	unsigned ResNE = 0);
2233
2234	/// Return true if loads are next to each other and can be
2235	/// merged. Check that both are nonvolatile and if LD is loading
2236	/// 'Bytes' bytes from a location that is 'Dist' units away from the
2237	/// location that the 'Base' load is loading from.
2238	bool areNonVolatileConsecutiveLoads(LoadSDNode *LD, LoadSDNode *Base,
2239	unsigned Bytes, int Dist) const;
2240
2241	/// Infer alignment of a load / store address. Return std::nullopt if it
2242	/// cannot be inferred.
2243	MaybeAlign InferPtrAlign(SDValue Ptr) const;
2244
2245	/// Split the scalar node with EXTRACT_ELEMENT using the provided VTs and
2246	/// return the low/high part.
2247	std::pair<SDValue, SDValue> SplitScalar(const SDValue &N, const SDLoc &DL,
2248	const EVT &LoVT, const EVT &HiVT);
2249
2250	/// Compute the VTs needed for the low/hi parts of a type
2251	/// which is split (or expanded) into two not necessarily identical pieces.
2252	std::pair<EVT, EVT> GetSplitDestVTs(const EVT &VT) const;
2253
2254	/// Compute the VTs needed for the low/hi parts of a type, dependent on an
2255	/// enveloping VT that has been split into two identical pieces. Sets the
2256	/// HisIsEmpty flag when hi type has zero storage size.
2257	std::pair<EVT, EVT> GetDependentSplitDestVTs(const EVT &VT, const EVT &EnvVT,
2258	bool *HiIsEmpty) const;
2259
2260	/// Split the vector with EXTRACT_SUBVECTOR using the provided
2261	/// VTs and return the low/high part.
2262	std::pair<SDValue, SDValue> SplitVector(const SDValue &N, const SDLoc &DL,
2263	const EVT &LoVT, const EVT &HiVT);
2264
2265	/// Split the vector with EXTRACT_SUBVECTOR and return the low/high part.
2266	std::pair<SDValue, SDValue> SplitVector(const SDValue &N, const SDLoc &DL) {
2267	EVT LoVT, HiVT;
2268	std::tie(args&: LoVT, args&: HiVT) = GetSplitDestVTs(VT: N.getValueType());
2269	return SplitVector(N, DL, LoVT, HiVT);
2270	}
2271
2272	/// Split the explicit vector length parameter of a VP operation.
2273	std::pair<SDValue, SDValue> SplitEVL(SDValue N, EVT VecVT, const SDLoc &DL);
2274
2275	/// Split the node's operand with EXTRACT_SUBVECTOR and
2276	/// return the low/high part.
2277	std::pair<SDValue, SDValue> SplitVectorOperand(const SDNode *N, unsigned OpNo)
2278	{
2279	return SplitVector(N: N->getOperand(Num: OpNo), DL: SDLoc(N));
2280	}
2281
2282	/// Widen the vector up to the next power of two using INSERT_SUBVECTOR.
2283	SDValue WidenVector(const SDValue &N, const SDLoc &DL);
2284
2285	/// Append the extracted elements from Start to Count out of the vector Op in
2286	/// Args. If Count is 0, all of the elements will be extracted. The extracted
2287	/// elements will have type EVT if it is provided, and otherwise their type
2288	/// will be Op's element type.
2289	void ExtractVectorElements(SDValue Op, SmallVectorImpl<SDValue> &Args,
2290	unsigned Start = 0, unsigned Count = 0,
2291	EVT EltVT = EVT());
2292
2293	/// Compute the default alignment value for the given type.
2294	Align getEVTAlign(EVT MemoryVT) const;
2295
2296	/// Test whether the given value is a constant int or similar node.
2297	SDNode *isConstantIntBuildVectorOrConstantInt(SDValue N) const;
2298
2299	/// Test whether the given value is a constant FP or similar node.
2300	SDNode *isConstantFPBuildVectorOrConstantFP(SDValue N) const ;
2301
2302	/// \returns true if \p N is any kind of constant or build_vector of
2303	/// constants, int or float. If a vector, it may not necessarily be a splat.
2304	inline bool isConstantValueOfAnyType(SDValue N) const {
2305	return isConstantIntBuildVectorOrConstantInt(N) ||
2306	isConstantFPBuildVectorOrConstantFP(N);
2307	}
2308
2309	/// Set CallSiteInfo to be associated with Node.
2310	void addCallSiteInfo(const SDNode *Node, CallSiteInfoImpl &&CallInfo) {
2311	SDEI[Node].CSInfo = std::move(CallInfo);
2312	}
2313	/// Return CallSiteInfo associated with Node, or a default if none exists.
2314	CallSiteInfo getCallSiteInfo(const SDNode *Node) {
2315	auto I = SDEI.find(Val: Node);
2316	return I != SDEI.end() ? std::move(I->second).CSInfo : CallSiteInfo();
2317	}
2318	/// Set HeapAllocSite to be associated with Node.
2319	void addHeapAllocSite(const SDNode *Node, MDNode *MD) {
2320	SDEI[Node].HeapAllocSite = MD;
2321	}
2322	/// Return HeapAllocSite associated with Node, or nullptr if none exists.
2323	MDNode *getHeapAllocSite(const SDNode *Node) const {
2324	auto I = SDEI.find(Val: Node);
2325	return I != SDEI.end() ? I->second.HeapAllocSite : nullptr;
2326	}
2327	/// Set PCSections to be associated with Node.
2328	void addPCSections(const SDNode *Node, MDNode *MD) {
2329	SDEI[Node].PCSections = MD;
2330	}
2331	/// Return PCSections associated with Node, or nullptr if none exists.
2332	MDNode *getPCSections(const SDNode *Node) const {
2333	auto It = SDEI.find(Val: Node);
2334	return It != SDEI.end() ? It->second.PCSections : nullptr;
2335	}
2336	/// Set NoMergeSiteInfo to be associated with Node if NoMerge is true.
2337	void addNoMergeSiteInfo(const SDNode *Node, bool NoMerge) {
2338	if (NoMerge)
2339	SDEI[Node].NoMerge = NoMerge;
2340	}
2341	/// Return NoMerge info associated with Node.
2342	bool getNoMergeSiteInfo(const SDNode *Node) const {
2343	auto I = SDEI.find(Val: Node);
2344	return I != SDEI.end() ? I->second.NoMerge : false;
2345	}
2346
2347	/// Copy extra info associated with one node to another.
2348	void copyExtraInfo(SDNode *From, SDNode *To);
2349
2350	/// Return the current function's default denormal handling kind for the given
2351	/// floating point type.
2352	DenormalMode getDenormalMode(EVT VT) const {
2353	return MF->getDenormalMode(FPType: EVTToAPFloatSemantics(VT));
2354	}
2355
2356	bool shouldOptForSize() const;
2357
2358	/// Get the (commutative) neutral element for the given opcode, if it exists.
2359	SDValue getNeutralElement(unsigned Opcode, const SDLoc &DL, EVT VT,
2360	SDNodeFlags Flags);
2361
2362	/// Some opcodes may create immediate undefined behavior when used with some
2363	/// values (integer division-by-zero for example). Therefore, these operations
2364	/// are not generally safe to move around or change.
2365	bool isSafeToSpeculativelyExecute(unsigned Opcode) const {
2366	switch (Opcode) {
2367	case ISD::SDIV:
2368	case ISD::SREM:
2369	case ISD::SDIVREM:
2370	case ISD::UDIV:
2371	case ISD::UREM:
2372	case ISD::UDIVREM:
2373	return false;
2374	default:
2375	return true;
2376	}
2377	}
2378
2379	/// Check if the provided node is save to speculatively executed given its
2380	/// current arguments. So, while `udiv` the opcode is not safe to
2381	/// speculatively execute, a given `udiv` node may be if the denominator is
2382	/// known nonzero.
2383	bool isSafeToSpeculativelyExecuteNode(const SDNode *N) const {
2384	switch (N->getOpcode()) {
2385	case ISD::UDIV:
2386	return isKnownNeverZero(Op: N->getOperand(Num: 1));
2387	default:
2388	return isSafeToSpeculativelyExecute(Opcode: N->getOpcode());
2389	}
2390	}
2391
2392	SDValue makeStateFunctionCall(unsigned LibFunc, SDValue Ptr, SDValue InChain,
2393	const SDLoc &DLoc);
2394
2395	private:
2396	void InsertNode(SDNode *N);
2397	bool RemoveNodeFromCSEMaps(SDNode *N);
2398	void AddModifiedNodeToCSEMaps(SDNode *N);
2399	SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op, void *&InsertPos);
2400	SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op1, SDValue Op2,
2401	void *&InsertPos);
2402	SDNode *FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
2403	void *&InsertPos);
2404	SDNode *UpdateSDLocOnMergeSDNode(SDNode *N, const SDLoc &loc);
2405
2406	void DeleteNodeNotInCSEMaps(SDNode *N);
2407	void DeallocateNode(SDNode *N);
2408
2409	void allnodes_clear();
2410
2411	/// Look up the node specified by ID in CSEMap. If it exists, return it. If
2412	/// not, return the insertion token that will make insertion faster. This
2413	/// overload is for nodes other than Constant or ConstantFP, use the other one
2414	/// for those.
2415	SDNode *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos);
2416
2417	/// Look up the node specified by ID in CSEMap. If it exists, return it. If
2418	/// not, return the insertion token that will make insertion faster. Performs
2419	/// additional processing for constant nodes.
2420	SDNode *FindNodeOrInsertPos(const FoldingSetNodeID &ID, const SDLoc &DL,
2421	void *&InsertPos);
2422
2423	/// Maps to auto-CSE operations.
2424	std::vector<CondCodeSDNode*> CondCodeNodes;
2425
2426	std::vector<SDNode*> ValueTypeNodes;
2427	std::map<EVT, SDNode*, EVT::compareRawBits> ExtendedValueTypeNodes;
2428	StringMap<SDNode*> ExternalSymbols;
2429
2430	std::map<std::pair<std::string, unsigned>, SDNode *> TargetExternalSymbols;
2431	DenseMap<MCSymbol *, SDNode *> MCSymbols;
2432
2433	FlagInserter *Inserter = nullptr;
2434	};
2435
2436	template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> {
2437	using nodes_iterator = pointer_iterator<SelectionDAG::allnodes_iterator>;
2438
2439	static nodes_iterator nodes_begin(SelectionDAG *G) {
2440	return nodes_iterator(G->allnodes_begin());
2441	}
2442
2443	static nodes_iterator nodes_end(SelectionDAG *G) {
2444	return nodes_iterator(G->allnodes_end());
2445	}
2446	};
2447
2448	} // end namespace llvm
2449
2450	#endif // LLVM_CODEGEN_SELECTIONDAG_H
2451