1
2	//===- GlobalISelEmitter.cpp - Generate an instruction selector -----------===//
3	//
4	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5	// See https://llvm.org/LICENSE.txt for license information.
6	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7	//
8	//===----------------------------------------------------------------------===//
9	//
10	/// \file
11	/// This tablegen backend emits code for use by the GlobalISel instruction
12	/// selector. See include/llvm/Target/GlobalISel/Target.td.
13	///
14	/// This file analyzes the patterns recognized by the SelectionDAGISel tablegen
15	/// backend, filters out the ones that are unsupported, maps
16	/// SelectionDAG-specific constructs to their GlobalISel counterpart
17	/// (when applicable: MVT to LLT; SDNode to generic Instruction).
18	///
19	/// Not all patterns are supported: pass the tablegen invocation
20	/// "-warn-on-skipped-patterns" to emit a warning when a pattern is skipped,
21	/// as well as why.
22	///
23	/// The generated file defines a single method:
24	/// bool <Target>InstructionSelector::selectImpl(MachineInstr &I) const;
25	/// intended to be used in InstructionSelector::select as the first-step
26	/// selector for the patterns that don't require complex C++.
27	///
28	/// FIXME: We'll probably want to eventually define a base
29	/// "TargetGenInstructionSelector" class.
30	///
31	//===----------------------------------------------------------------------===//
32
33	#include "Basic/CodeGenIntrinsics.h"
34	#include "Common/CodeGenDAGPatterns.h"
35	#include "Common/CodeGenInstruction.h"
36	#include "Common/CodeGenRegisters.h"
37	#include "Common/CodeGenTarget.h"
38	#include "Common/GlobalISel/GlobalISelMatchTable.h"
39	#include "Common/GlobalISel/GlobalISelMatchTableExecutorEmitter.h"
40	#include "Common/InfoByHwMode.h"
41	#include "Common/SubtargetFeatureInfo.h"
42	#include "llvm/ADT/Statistic.h"
43	#include "llvm/CodeGenTypes/LowLevelType.h"
44	#include "llvm/CodeGenTypes/MachineValueType.h"
45	#include "llvm/Support/CodeGenCoverage.h"
46	#include "llvm/Support/CommandLine.h"
47	#include "llvm/Support/Error.h"
48	#include "llvm/Support/SaveAndRestore.h"
49	#include "llvm/Support/ScopedPrinter.h"
50	#include "llvm/TableGen/Error.h"
51	#include "llvm/TableGen/Record.h"
52	#include "llvm/TableGen/TableGenBackend.h"
53	#include <numeric>
54	#include <string>
55
56	using namespace llvm;
57	using namespace llvm::gi;
58
59	using action_iterator = RuleMatcher::action_iterator;
60
61	#define DEBUG_TYPE "gisel-emitter"
62
63	STATISTIC(NumPatternTotal, "Total number of patterns");
64	STATISTIC(NumPatternImported, "Number of patterns imported from SelectionDAG");
65	STATISTIC(NumPatternImportsSkipped, "Number of SelectionDAG imports skipped");
66	STATISTIC(NumPatternsTested,
67	"Number of patterns executed according to coverage information");
68
69	cl::OptionCategory GlobalISelEmitterCat("Options for -gen-global-isel");
70
71	static cl::opt<bool> WarnOnSkippedPatterns(
72	"warn-on-skipped-patterns",
73	cl::desc("Explain why a pattern was skipped for inclusion "
74	"in the GlobalISel selector"),
75	cl::init(Val: false), cl::cat(GlobalISelEmitterCat));
76
77	static cl::opt<bool> GenerateCoverage(
78	"instrument-gisel-coverage",
79	cl::desc("Generate coverage instrumentation for GlobalISel"),
80	cl::init(Val: false), cl::cat(GlobalISelEmitterCat));
81
82	static cl::opt<std::string> UseCoverageFile(
83	"gisel-coverage-file", cl::init(Val: ""),
84	cl::desc("Specify file to retrieve coverage information from"),
85	cl::cat(GlobalISelEmitterCat));
86
87	static cl::opt<bool> OptimizeMatchTable(
88	"optimize-match-table",
89	cl::desc("Generate an optimized version of the match table"),
90	cl::init(Val: true), cl::cat(GlobalISelEmitterCat));
91
92	namespace {
93
94	static std::string explainPredicates(const TreePatternNode &N) {
95	std::string Explanation;
96	StringRef Separator = "";
97	for (const TreePredicateCall &Call : N.getPredicateCalls()) {
98	const TreePredicateFn &P = Call.Fn;
99	Explanation +=
100	(Separator + P.getOrigPatFragRecord()->getRecord()->getName()).str();
101	Separator = ", ";
102
103	if (P.isAlwaysTrue())
104	Explanation += " always-true";
105	if (P.isImmediatePattern())
106	Explanation += " immediate";
107
108	if (P.isUnindexed())
109	Explanation += " unindexed";
110
111	if (P.isNonExtLoad())
112	Explanation += " non-extload";
113	if (P.isAnyExtLoad())
114	Explanation += " extload";
115	if (P.isSignExtLoad())
116	Explanation += " sextload";
117	if (P.isZeroExtLoad())
118	Explanation += " zextload";
119
120	if (P.isNonTruncStore())
121	Explanation += " non-truncstore";
122	if (P.isTruncStore())
123	Explanation += " truncstore";
124
125	if (Record *VT = P.getMemoryVT())
126	Explanation += (" MemVT=" + VT->getName()).str();
127	if (Record *VT = P.getScalarMemoryVT())
128	Explanation += (" ScalarVT(MemVT)=" + VT->getName()).str();
129
130	if (ListInit *AddrSpaces = P.getAddressSpaces()) {
131	raw_string_ostream OS(Explanation);
132	OS << " AddressSpaces=[";
133
134	StringRef AddrSpaceSeparator;
135	for (Init *Val : AddrSpaces->getValues()) {
136	IntInit *IntVal = dyn_cast<IntInit>(Val);
137	if (!IntVal)
138	continue;
139
140	OS << AddrSpaceSeparator << IntVal->getValue();
141	AddrSpaceSeparator = ", ";
142	}
143
144	OS << ']';
145	}
146
147	int64_t MinAlign = P.getMinAlignment();
148	if (MinAlign > 0)
149	Explanation += " MinAlign=" + utostr(X: MinAlign);
150
151	if (P.isAtomicOrderingMonotonic())
152	Explanation += " monotonic";
153	if (P.isAtomicOrderingAcquire())
154	Explanation += " acquire";
155	if (P.isAtomicOrderingRelease())
156	Explanation += " release";
157	if (P.isAtomicOrderingAcquireRelease())
158	Explanation += " acq_rel";
159	if (P.isAtomicOrderingSequentiallyConsistent())
160	Explanation += " seq_cst";
161	if (P.isAtomicOrderingAcquireOrStronger())
162	Explanation += " >=acquire";
163	if (P.isAtomicOrderingWeakerThanAcquire())
164	Explanation += " <acquire";
165	if (P.isAtomicOrderingReleaseOrStronger())
166	Explanation += " >=release";
167	if (P.isAtomicOrderingWeakerThanRelease())
168	Explanation += " <release";
169	}
170	return Explanation;
171	}
172
173	std::string explainOperator(Record *Operator) {
174	if (Operator->isSubClassOf(Name: "SDNode"))
175	return (" (" + Operator->getValueAsString(FieldName: "Opcode") + ")").str();
176
177	if (Operator->isSubClassOf(Name: "Intrinsic"))
178	return (" (Operator is an Intrinsic, " + Operator->getName() + ")").str();
179
180	if (Operator->isSubClassOf(Name: "ComplexPattern"))
181	return (" (Operator is an unmapped ComplexPattern, " + Operator->getName() +
182	")")
183	.str();
184
185	if (Operator->isSubClassOf(Name: "SDNodeXForm"))
186	return (" (Operator is an unmapped SDNodeXForm, " + Operator->getName() +
187	")")
188	.str();
189
190	return (" (Operator " + Operator->getName() + " not understood)").str();
191	}
192
193	/// Helper function to let the emitter report skip reason error messages.
194	static Error failedImport(const Twine &Reason) {
195	return make_error<StringError>(Args: Reason, Args: inconvertibleErrorCode());
196	}
197
198	static Error isTrivialOperatorNode(const TreePatternNode &N) {
199	std::string Explanation;
200	std::string Separator;
201
202	bool HasUnsupportedPredicate = false;
203	for (const TreePredicateCall &Call : N.getPredicateCalls()) {
204	const TreePredicateFn &Predicate = Call.Fn;
205
206	if (Predicate.isAlwaysTrue())
207	continue;
208
209	if (Predicate.isImmediatePattern())
210	continue;
211
212	if (Predicate.hasNoUse())
213	continue;
214
215	if (Predicate.isNonExtLoad() || Predicate.isAnyExtLoad() ||
216	Predicate.isSignExtLoad() || Predicate.isZeroExtLoad())
217	continue;
218
219	if (Predicate.isNonTruncStore() || Predicate.isTruncStore())
220	continue;
221
222	if (Predicate.isLoad() && Predicate.getMemoryVT())
223	continue;
224
225	if (Predicate.isLoad() || Predicate.isStore()) {
226	if (Predicate.isUnindexed())
227	continue;
228	}
229
230	if (Predicate.isLoad() || Predicate.isStore() || Predicate.isAtomic()) {
231	const ListInit *AddrSpaces = Predicate.getAddressSpaces();
232	if (AddrSpaces && !AddrSpaces->empty())
233	continue;
234
235	if (Predicate.getMinAlignment() > 0)
236	continue;
237	}
238
239	if (Predicate.isAtomic() && Predicate.getMemoryVT())
240	continue;
241
242	if (Predicate.isAtomic() &&
243	(Predicate.isAtomicOrderingMonotonic() ||
244	Predicate.isAtomicOrderingAcquire() ||
245	Predicate.isAtomicOrderingRelease() ||
246	Predicate.isAtomicOrderingAcquireRelease() ||
247	Predicate.isAtomicOrderingSequentiallyConsistent() ||
248	Predicate.isAtomicOrderingAcquireOrStronger() ||
249	Predicate.isAtomicOrderingWeakerThanAcquire() ||
250	Predicate.isAtomicOrderingReleaseOrStronger() ||
251	Predicate.isAtomicOrderingWeakerThanRelease()))
252	continue;
253
254	if (Predicate.hasGISelPredicateCode())
255	continue;
256
257	HasUnsupportedPredicate = true;
258	Explanation = Separator + "Has a predicate (" + explainPredicates(N) + ")";
259	Separator = ", ";
260	Explanation += (Separator + "first-failing:" +
261	Predicate.getOrigPatFragRecord()->getRecord()->getName())
262	.str();
263	break;
264	}
265
266	if (!HasUnsupportedPredicate)
267	return Error::success();
268
269	return failedImport(Reason: Explanation);
270	}
271
272	static Record *getInitValueAsRegClass(Init *V) {
273	if (DefInit *VDefInit = dyn_cast<DefInit>(Val: V)) {
274	if (VDefInit->getDef()->isSubClassOf(Name: "RegisterOperand"))
275	return VDefInit->getDef()->getValueAsDef(FieldName: "RegClass");
276	if (VDefInit->getDef()->isSubClassOf(Name: "RegisterClass"))
277	return VDefInit->getDef();
278	}
279	return nullptr;
280	}
281
282	static std::string getScopedName(unsigned Scope, const std::string &Name) {
283	return ("pred:" + Twine(Scope) + ":" + Name).str();
284	}
285
286	static std::string getMangledRootDefName(StringRef DefOperandName) {
287	return ("DstI[" + DefOperandName + "]").str();
288	}
289
290	//===- GlobalISelEmitter class --------------------------------------------===//
291
292	static Expected<LLTCodeGen> getInstResultType(const TreePatternNode &Dst,
293	const CodeGenTarget &Target) {
294	// While we allow more than one output (both implicit and explicit defs)
295	// below, we only expect one explicit def here.
296	assert(Dst.getOperator()->isSubClassOf("Instruction"));
297	CodeGenInstruction &InstInfo = Target.getInstruction(InstRec: Dst.getOperator());
298	if (!InstInfo.Operands.NumDefs)
299	return failedImport(Reason: "Dst pattern child needs a def");
300
301	ArrayRef<TypeSetByHwMode> ChildTypes = Dst.getExtTypes();
302	if (ChildTypes.size() < 1)
303	return failedImport(Reason: "Dst pattern child has no result");
304
305	// If there are multiple results, just take the first one (this is how
306	// SelectionDAG does it).
307	std::optional<LLTCodeGen> MaybeOpTy;
308	if (ChildTypes.front().isMachineValueType()) {
309	MaybeOpTy = MVTToLLT(SVT: ChildTypes.front().getMachineValueType().SimpleTy);
310	}
311
312	if (!MaybeOpTy)
313	return failedImport(Reason: "Dst operand has an unsupported type");
314	return *MaybeOpTy;
315	}
316
317	class GlobalISelEmitter final : public GlobalISelMatchTableExecutorEmitter {
318	public:
319	explicit GlobalISelEmitter(RecordKeeper &RK);
320
321	void emitAdditionalImpl(raw_ostream &OS) override;
322
323	void emitMIPredicateFns(raw_ostream &OS) override;
324	void emitI64ImmPredicateFns(raw_ostream &OS) override;
325	void emitAPFloatImmPredicateFns(raw_ostream &OS) override;
326	void emitAPIntImmPredicateFns(raw_ostream &OS) override;
327	void emitTestSimplePredicate(raw_ostream &OS) override;
328	void emitRunCustomAction(raw_ostream &OS) override;
329
330	void postProcessRule(RuleMatcher &M);
331
332	const CodeGenTarget &getTarget() const override { return Target; }
333	StringRef getClassName() const override { return ClassName; }
334
335	void run(raw_ostream &OS);
336
337	private:
338	std::string ClassName;
339
340	const RecordKeeper &RK;
341	const CodeGenDAGPatterns CGP;
342	const CodeGenTarget &Target;
343	CodeGenRegBank &CGRegs;
344
345	std::vector<Record *> AllPatFrags;
346
347	/// Keep track of the equivalence between SDNodes and Instruction by mapping
348	/// SDNodes to the GINodeEquiv mapping. We need to map to the GINodeEquiv to
349	/// check for attributes on the relation such as CheckMMOIsNonAtomic.
350	/// This is defined using 'GINodeEquiv' in the target description.
351	DenseMap<Record *, Record *> NodeEquivs;
352
353	/// Keep track of the equivalence between ComplexPattern's and
354	/// GIComplexOperandMatcher. Map entries are specified by subclassing
355	/// GIComplexPatternEquiv.
356	DenseMap<const Record *, const Record *> ComplexPatternEquivs;
357
358	/// Keep track of the equivalence between SDNodeXForm's and
359	/// GICustomOperandRenderer. Map entries are specified by subclassing
360	/// GISDNodeXFormEquiv.
361	DenseMap<const Record *, const Record *> SDNodeXFormEquivs;
362
363	/// Keep track of Scores of PatternsToMatch similar to how the DAG does.
364	/// This adds compatibility for RuleMatchers to use this for ordering rules.
365	DenseMap<uint64_t, int> RuleMatcherScores;
366
367	// Rule coverage information.
368	std::optional<CodeGenCoverage> RuleCoverage;
369
370	/// Variables used to help with collecting of named operands for predicates
371	/// with 'let PredicateCodeUsesOperands = 1'. WaitingForNamedOperands is set
372	/// to the number of named operands that predicate expects. Store locations in
373	/// StoreIdxForName correspond to the order in which operand names appear in
374	/// predicate's argument list.
375	/// When we visit named operand and WaitingForNamedOperands is not zero, add
376	/// matcher that will record operand and decrease counter.
377	unsigned WaitingForNamedOperands = 0;
378	StringMap<unsigned> StoreIdxForName;
379
380	void gatherOpcodeValues();
381	void gatherTypeIDValues();
382	void gatherNodeEquivs();
383
384	Record *findNodeEquiv(Record *N) const;
385	const CodeGenInstruction *getEquivNode(Record &Equiv,
386	const TreePatternNode &N) const;
387
388	Error importRulePredicates(RuleMatcher &M, ArrayRef<Record *> Predicates);
389	Expected<InstructionMatcher &>
390	createAndImportSelDAGMatcher(RuleMatcher &Rule,
391	InstructionMatcher &InsnMatcher,
392	const TreePatternNode &Src, unsigned &TempOpIdx);
393	Error importComplexPatternOperandMatcher(OperandMatcher &OM, Record *R,
394	unsigned &TempOpIdx) const;
395	Error importChildMatcher(RuleMatcher &Rule, InstructionMatcher &InsnMatcher,
396	const TreePatternNode &SrcChild,
397	bool OperandIsAPointer, bool OperandIsImmArg,
398	unsigned OpIdx, unsigned &TempOpIdx);
399
400	Expected<BuildMIAction &> createAndImportInstructionRenderer(
401	RuleMatcher &M, InstructionMatcher &InsnMatcher,
402	const TreePatternNode &Src, const TreePatternNode &Dst);
403	Expected<action_iterator> createAndImportSubInstructionRenderer(
404	action_iterator InsertPt, RuleMatcher &M, const TreePatternNode &Dst,
405	const TreePatternNode &Src, unsigned TempReg);
406	Expected<action_iterator>
407	createInstructionRenderer(action_iterator InsertPt, RuleMatcher &M,
408	const TreePatternNode &Dst);
409
410	Expected<action_iterator>
411	importExplicitDefRenderers(action_iterator InsertPt, RuleMatcher &M,
412	BuildMIAction &DstMIBuilder,
413	const TreePatternNode &Src,
414	const TreePatternNode &Dst, unsigned Start = 0);
415
416	Expected<action_iterator> importExplicitUseRenderers(
417	action_iterator InsertPt, RuleMatcher &M, BuildMIAction &DstMIBuilder,
418	const llvm::TreePatternNode &Dst, const TreePatternNode &Src);
419	Expected<action_iterator> importExplicitUseRenderer(
420	action_iterator InsertPt, RuleMatcher &Rule, BuildMIAction &DstMIBuilder,
421	const TreePatternNode &DstChild, const TreePatternNode &Src);
422	Error importDefaultOperandRenderers(action_iterator InsertPt, RuleMatcher &M,
423	BuildMIAction &DstMIBuilder,
424	const DAGDefaultOperand &DefaultOp) const;
425	Error
426	importImplicitDefRenderers(BuildMIAction &DstMIBuilder,
427	const std::vector<Record *> &ImplicitDefs) const;
428
429	/// Analyze pattern \p P, returning a matcher for it if possible.
430	/// Otherwise, return an Error explaining why we don't support it.
431	Expected<RuleMatcher> runOnPattern(const PatternToMatch &P);
432
433	void declareSubtargetFeature(Record *Predicate);
434
435	unsigned declareHwModeCheck(StringRef HwModeFeatures);
436
437	MatchTable buildMatchTable(MutableArrayRef<RuleMatcher> Rules, bool Optimize,
438	bool WithCoverage);
439
440	/// Infer a CodeGenRegisterClass for the type of \p SuperRegNode. The returned
441	/// CodeGenRegisterClass will support the CodeGenRegisterClass of
442	/// \p SubRegNode, and the subregister index defined by \p SubRegIdxNode.
443	/// If no register class is found, return std::nullopt.
444	std::optional<const CodeGenRegisterClass *>
445	inferSuperRegisterClassForNode(const TypeSetByHwMode &Ty,
446	const TreePatternNode &SuperRegNode,
447	const TreePatternNode &SubRegIdxNode);
448	std::optional<CodeGenSubRegIndex *>
449	inferSubRegIndexForNode(const TreePatternNode &SubRegIdxNode);
450
451	/// Infer a CodeGenRegisterClass which suppoorts \p Ty and \p SubRegIdxNode.
452	/// Return std::nullopt if no such class exists.
453	std::optional<const CodeGenRegisterClass *>
454	inferSuperRegisterClass(const TypeSetByHwMode &Ty,
455	const TreePatternNode &SubRegIdxNode);
456
457	/// Return the CodeGenRegisterClass associated with \p Leaf if it has one.
458	std::optional<const CodeGenRegisterClass *>
459	getRegClassFromLeaf(const TreePatternNode &Leaf);
460
461	/// Return a CodeGenRegisterClass for \p N if one can be found. Return
462	/// std::nullopt otherwise.
463	std::optional<const CodeGenRegisterClass *>
464	inferRegClassFromPattern(const TreePatternNode &N);
465
466	/// Return the size of the MemoryVT in this predicate, if possible.
467	std::optional<unsigned>
468	getMemSizeBitsFromPredicate(const TreePredicateFn &Predicate);
469
470	// Add builtin predicates.
471	Expected<InstructionMatcher &>
472	addBuiltinPredicates(const Record *SrcGIEquivOrNull,
473	const TreePredicateFn &Predicate,
474	InstructionMatcher &InsnMatcher, bool &HasAddedMatcher);
475	};
476
477	StringRef getPatFragPredicateEnumName(Record *R) { return R->getName(); }
478
479	void GlobalISelEmitter::gatherOpcodeValues() {
480	InstructionOpcodeMatcher::initOpcodeValuesMap(Target);
481	}
482
483	void GlobalISelEmitter::gatherTypeIDValues() {
484	LLTOperandMatcher::initTypeIDValuesMap();
485	}
486
487	void GlobalISelEmitter::gatherNodeEquivs() {
488	assert(NodeEquivs.empty());
489	for (Record *Equiv : RK.getAllDerivedDefinitions(ClassName: "GINodeEquiv"))
490	NodeEquivs[Equiv->getValueAsDef(FieldName: "Node")] = Equiv;
491
492	assert(ComplexPatternEquivs.empty());
493	for (Record *Equiv : RK.getAllDerivedDefinitions(ClassName: "GIComplexPatternEquiv")) {
494	Record *SelDAGEquiv = Equiv->getValueAsDef(FieldName: "SelDAGEquivalent");
495	if (!SelDAGEquiv)
496	continue;
497	ComplexPatternEquivs[SelDAGEquiv] = Equiv;
498	}
499
500	assert(SDNodeXFormEquivs.empty());
501	for (Record *Equiv : RK.getAllDerivedDefinitions(ClassName: "GISDNodeXFormEquiv")) {
502	Record *SelDAGEquiv = Equiv->getValueAsDef(FieldName: "SelDAGEquivalent");
503	if (!SelDAGEquiv)
504	continue;
505	SDNodeXFormEquivs[SelDAGEquiv] = Equiv;
506	}
507	}
508
509	Record *GlobalISelEmitter::findNodeEquiv(Record *N) const {
510	return NodeEquivs.lookup(Val: N);
511	}
512
513	const CodeGenInstruction *
514	GlobalISelEmitter::getEquivNode(Record &Equiv, const TreePatternNode &N) const {
515	if (N.getNumChildren() >= 1) {
516	// setcc operation maps to two different G_* instructions based on the type.
517	if (!Equiv.isValueUnset(FieldName: "IfFloatingPoint") &&
518	MVT(N.getChild(N: 0).getSimpleType(ResNo: 0)).isFloatingPoint())
519	return &Target.getInstruction(InstRec: Equiv.getValueAsDef(FieldName: "IfFloatingPoint"));
520	}
521
522	if (!Equiv.isValueUnset(FieldName: "IfConvergent") &&
523	N.getIntrinsicInfo(CDP: CGP)->isConvergent)
524	return &Target.getInstruction(InstRec: Equiv.getValueAsDef(FieldName: "IfConvergent"));
525
526	for (const TreePredicateCall &Call : N.getPredicateCalls()) {
527	const TreePredicateFn &Predicate = Call.Fn;
528	if (!Equiv.isValueUnset(FieldName: "IfSignExtend") &&
529	(Predicate.isLoad() || Predicate.isAtomic()) &&
530	Predicate.isSignExtLoad())
531	return &Target.getInstruction(InstRec: Equiv.getValueAsDef(FieldName: "IfSignExtend"));
532	if (!Equiv.isValueUnset(FieldName: "IfZeroExtend") &&
533	(Predicate.isLoad() || Predicate.isAtomic()) &&
534	Predicate.isZeroExtLoad())
535	return &Target.getInstruction(InstRec: Equiv.getValueAsDef(FieldName: "IfZeroExtend"));
536	}
537
538	return &Target.getInstruction(InstRec: Equiv.getValueAsDef(FieldName: "I"));
539	}
540
541	GlobalISelEmitter::GlobalISelEmitter(RecordKeeper &RK)
542	: GlobalISelMatchTableExecutorEmitter(), RK(RK), CGP(RK),
543	Target(CGP.getTargetInfo()), CGRegs(Target.getRegBank()) {
544	ClassName = Target.getName().str() + "InstructionSelector";
545	}
546
547	//===- Emitter ------------------------------------------------------------===//
548
549	Error GlobalISelEmitter::importRulePredicates(RuleMatcher &M,
550	ArrayRef<Record *> Predicates) {
551	for (Record *Pred : Predicates) {
552	if (Pred->getValueAsString(FieldName: "CondString").empty())
553	continue;
554	declareSubtargetFeature(Predicate: Pred);
555	M.addRequiredFeature(Feature: Pred);
556	}
557
558	return Error::success();
559	}
560
561	std::optional<unsigned> GlobalISelEmitter::getMemSizeBitsFromPredicate(
562	const TreePredicateFn &Predicate) {
563	std::optional<LLTCodeGen> MemTyOrNone =
564	MVTToLLT(SVT: getValueType(Rec: Predicate.getMemoryVT()));
565
566	if (!MemTyOrNone)
567	return std::nullopt;
568
569	// Align so unusual types like i1 don't get rounded down.
570	return llvm::alignTo(
571	Value: static_cast<unsigned>(MemTyOrNone->get().getSizeInBits()), Align: 8);
572	}
573
574	Expected<InstructionMatcher &> GlobalISelEmitter::addBuiltinPredicates(
575	const Record *SrcGIEquivOrNull, const TreePredicateFn &Predicate,
576	InstructionMatcher &InsnMatcher, bool &HasAddedMatcher) {
577	if (Predicate.isLoad() || Predicate.isStore() || Predicate.isAtomic()) {
578	if (const ListInit *AddrSpaces = Predicate.getAddressSpaces()) {
579	SmallVector<unsigned, 4> ParsedAddrSpaces;
580
581	for (Init *Val : AddrSpaces->getValues()) {
582	IntInit *IntVal = dyn_cast<IntInit>(Val);
583	if (!IntVal)
584	return failedImport(Reason: "Address space is not an integer");
585	ParsedAddrSpaces.push_back(Elt: IntVal->getValue());
586	}
587
588	if (!ParsedAddrSpaces.empty()) {
589	InsnMatcher.addPredicate<MemoryAddressSpacePredicateMatcher>(
590	args: 0, args&: ParsedAddrSpaces);
591	return InsnMatcher;
592	}
593	}
594
595	int64_t MinAlign = Predicate.getMinAlignment();
596	if (MinAlign > 0) {
597	InsnMatcher.addPredicate<MemoryAlignmentPredicateMatcher>(args: 0, args&: MinAlign);
598	return InsnMatcher;
599	}
600	}
601
602	// G_LOAD is used for both non-extending and any-extending loads.
603	if (Predicate.isLoad() && Predicate.isNonExtLoad()) {
604	InsnMatcher.addPredicate<MemoryVsLLTSizePredicateMatcher>(
605	args: 0, args: MemoryVsLLTSizePredicateMatcher::EqualTo, args: 0);
606	return InsnMatcher;
607	}
608	if (Predicate.isLoad() && Predicate.isAnyExtLoad()) {
609	InsnMatcher.addPredicate<MemoryVsLLTSizePredicateMatcher>(
610	args: 0, args: MemoryVsLLTSizePredicateMatcher::LessThan, args: 0);
611	return InsnMatcher;
612	}
613
614	if (Predicate.isStore()) {
615	if (Predicate.isTruncStore()) {
616	if (Predicate.getMemoryVT() != nullptr) {
617	// FIXME: If MemoryVT is set, we end up with 2 checks for the MMO size.
618	auto MemSizeInBits = getMemSizeBitsFromPredicate(Predicate);
619	if (!MemSizeInBits)
620	return failedImport(Reason: "MemVT could not be converted to LLT");
621
622	InsnMatcher.addPredicate<MemorySizePredicateMatcher>(args: 0, args: *MemSizeInBits /
623	8);
624	} else {
625	InsnMatcher.addPredicate<MemoryVsLLTSizePredicateMatcher>(
626	args: 0, args: MemoryVsLLTSizePredicateMatcher::LessThan, args: 0);
627	}
628	return InsnMatcher;
629	}
630	if (Predicate.isNonTruncStore()) {
631	// We need to check the sizes match here otherwise we could incorrectly
632	// match truncating stores with non-truncating ones.
633	InsnMatcher.addPredicate<MemoryVsLLTSizePredicateMatcher>(
634	args: 0, args: MemoryVsLLTSizePredicateMatcher::EqualTo, args: 0);
635	}
636	}
637
638	assert(SrcGIEquivOrNull != nullptr && "Invalid SrcGIEquivOrNull value");
639	// No check required. We already did it by swapping the opcode.
640	if (!SrcGIEquivOrNull->isValueUnset(FieldName: "IfSignExtend") &&
641	Predicate.isSignExtLoad())
642	return InsnMatcher;
643
644	// No check required. We already did it by swapping the opcode.
645	if (!SrcGIEquivOrNull->isValueUnset(FieldName: "IfZeroExtend") &&
646	Predicate.isZeroExtLoad())
647	return InsnMatcher;
648
649	// No check required. G_STORE by itself is a non-extending store.
650	if (Predicate.isNonTruncStore())
651	return InsnMatcher;
652
653	if (Predicate.isLoad() || Predicate.isStore() || Predicate.isAtomic()) {
654	if (Predicate.getMemoryVT() != nullptr) {
655	auto MemSizeInBits = getMemSizeBitsFromPredicate(Predicate);
656	if (!MemSizeInBits)
657	return failedImport(Reason: "MemVT could not be converted to LLT");
658
659	InsnMatcher.addPredicate<MemorySizePredicateMatcher>(args: 0,
660	args: *MemSizeInBits / 8);
661	return InsnMatcher;
662	}
663	}
664
665	if (Predicate.isLoad() || Predicate.isStore()) {
666	// No check required. A G_LOAD/G_STORE is an unindexed load.
667	if (Predicate.isUnindexed())
668	return InsnMatcher;
669	}
670
671	if (Predicate.isAtomic()) {
672	if (Predicate.isAtomicOrderingMonotonic()) {
673	InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(args: "Monotonic");
674	return InsnMatcher;
675	}
676	if (Predicate.isAtomicOrderingAcquire()) {
677	InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(args: "Acquire");
678	return InsnMatcher;
679	}
680	if (Predicate.isAtomicOrderingRelease()) {
681	InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(args: "Release");
682	return InsnMatcher;
683	}
684	if (Predicate.isAtomicOrderingAcquireRelease()) {
685	InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
686	args: "AcquireRelease");
687	return InsnMatcher;
688	}
689	if (Predicate.isAtomicOrderingSequentiallyConsistent()) {
690	InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
691	args: "SequentiallyConsistent");
692	return InsnMatcher;
693	}
694	}
695
696	if (Predicate.isAtomicOrderingAcquireOrStronger()) {
697	InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
698	args: "Acquire", args: AtomicOrderingMMOPredicateMatcher::AO_OrStronger);
699	return InsnMatcher;
700	}
701	if (Predicate.isAtomicOrderingWeakerThanAcquire()) {
702	InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
703	args: "Acquire", args: AtomicOrderingMMOPredicateMatcher::AO_WeakerThan);
704	return InsnMatcher;
705	}
706
707	if (Predicate.isAtomicOrderingReleaseOrStronger()) {
708	InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
709	args: "Release", args: AtomicOrderingMMOPredicateMatcher::AO_OrStronger);
710	return InsnMatcher;
711	}
712	if (Predicate.isAtomicOrderingWeakerThanRelease()) {
713	InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
714	args: "Release", args: AtomicOrderingMMOPredicateMatcher::AO_WeakerThan);
715	return InsnMatcher;
716	}
717	HasAddedMatcher = false;
718	return InsnMatcher;
719	}
720
721	Expected<InstructionMatcher &> GlobalISelEmitter::createAndImportSelDAGMatcher(
722	RuleMatcher &Rule, InstructionMatcher &InsnMatcher,
723	const TreePatternNode &Src, unsigned &TempOpIdx) {
724	const auto SavedFlags = Rule.setGISelFlags(Src.getGISelFlagsRecord());
725
726	Record *SrcGIEquivOrNull = nullptr;
727	const CodeGenInstruction *SrcGIOrNull = nullptr;
728
729	// Start with the defined operands (i.e., the results of the root operator).
730	if (Src.isLeaf()) {
731	Init *SrcInit = Src.getLeafValue();
732	if (isa<IntInit>(Val: SrcInit)) {
733	InsnMatcher.addPredicate<InstructionOpcodeMatcher>(
734	args: &Target.getInstruction(InstRec: RK.getDef(Name: "G_CONSTANT")));
735	} else
736	return failedImport(
737	Reason: "Unable to deduce gMIR opcode to handle Src (which is a leaf)");
738	} else {
739	SrcGIEquivOrNull = findNodeEquiv(N: Src.getOperator());
740	if (!SrcGIEquivOrNull)
741	return failedImport(Reason: "Pattern operator lacks an equivalent Instruction" +
742	explainOperator(Operator: Src.getOperator()));
743	SrcGIOrNull = getEquivNode(Equiv&: *SrcGIEquivOrNull, N: Src);
744
745	// The operators look good: match the opcode
746	InsnMatcher.addPredicate<InstructionOpcodeMatcher>(args&: SrcGIOrNull);
747	}
748
749	unsigned OpIdx = 0;
750	for (const TypeSetByHwMode &VTy : Src.getExtTypes()) {
751	// Results don't have a name unless they are the root node. The caller will
752	// set the name if appropriate.
753	const bool OperandIsAPointer =
754	SrcGIOrNull && SrcGIOrNull->isOutOperandAPointer(i: OpIdx);
755	OperandMatcher &OM = InsnMatcher.addOperand(OpIdx: OpIdx++, SymbolicName: "", AllocatedTemporariesBaseID: TempOpIdx);
756	if (auto Error = OM.addTypeCheckPredicate(VTy, OperandIsAPointer))
757	return failedImport(Reason: toString(E: std::move(Error)) +
758	" for result of Src pattern operator");
759	}
760
761	for (const TreePredicateCall &Call : Src.getPredicateCalls()) {
762	const TreePredicateFn &Predicate = Call.Fn;
763	bool HasAddedBuiltinMatcher = true;
764	if (Predicate.isAlwaysTrue())
765	continue;
766
767	if (Predicate.isImmediatePattern()) {
768	InsnMatcher.addPredicate<InstructionImmPredicateMatcher>(args: Predicate);
769	continue;
770	}
771
772	auto InsnMatcherOrError = addBuiltinPredicates(
773	SrcGIEquivOrNull, Predicate, InsnMatcher, HasAddedMatcher&: HasAddedBuiltinMatcher);
774	if (auto Error = InsnMatcherOrError.takeError())
775	return std::move(Error);
776
777	// FIXME: This should be part of addBuiltinPredicates(). If we add this at
778	// the start of addBuiltinPredicates() without returning, then there might
779	// be cases where we hit the last return before which the
780	// HasAddedBuiltinMatcher will be set to false. The predicate could be
781	// missed if we add it in the middle or at the end due to return statements
782	// after the addPredicate<>() calls.
783	if (Predicate.hasNoUse()) {
784	InsnMatcher.addPredicate<NoUsePredicateMatcher>();
785	HasAddedBuiltinMatcher = true;
786	}
787
788	if (Predicate.hasGISelPredicateCode()) {
789	if (Predicate.usesOperands()) {
790	assert(WaitingForNamedOperands == 0 &&
791	"previous predicate didn't find all operands or "
792	"nested predicate that uses operands");
793	TreePattern *TP = Predicate.getOrigPatFragRecord();
794	WaitingForNamedOperands = TP->getNumArgs();
795	for (unsigned i = 0; i < WaitingForNamedOperands; ++i)
796	StoreIdxForName[getScopedName(Scope: Call.Scope, Name: TP->getArgName(i))] = i;
797	}
798	InsnMatcher.addPredicate<GenericInstructionPredicateMatcher>(args: Predicate);
799	continue;
800	}
801	if (!HasAddedBuiltinMatcher) {
802	return failedImport(Reason: "Src pattern child has predicate (" +
803	explainPredicates(N: Src) + ")");
804	}
805	}
806
807	if (SrcGIEquivOrNull &&
808	SrcGIEquivOrNull->getValueAsBit(FieldName: "CheckMMOIsNonAtomic"))
809	InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(args: "NotAtomic");
810	else if (SrcGIEquivOrNull &&
811	SrcGIEquivOrNull->getValueAsBit(FieldName: "CheckMMOIsAtomic")) {
812	InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
813	args: "Unordered", args: AtomicOrderingMMOPredicateMatcher::AO_OrStronger);
814	}
815
816	if (Src.isLeaf()) {
817	Init *SrcInit = Src.getLeafValue();
818	if (IntInit *SrcIntInit = dyn_cast<IntInit>(Val: SrcInit)) {
819	OperandMatcher &OM =
820	InsnMatcher.addOperand(OpIdx: OpIdx++, SymbolicName: Src.getName(), AllocatedTemporariesBaseID: TempOpIdx);
821	OM.addPredicate<LiteralIntOperandMatcher>(args: SrcIntInit->getValue());
822	} else
823	return failedImport(
824	Reason: "Unable to deduce gMIR opcode to handle Src (which is a leaf)");
825	} else {
826	assert(SrcGIOrNull &&
827	"Expected to have already found an equivalent Instruction");
828	if (SrcGIOrNull->TheDef->getName() == "G_CONSTANT" ||
829	SrcGIOrNull->TheDef->getName() == "G_FCONSTANT") {
830	// imm/fpimm still have operands but we don't need to do anything with it
831	// here since we don't support ImmLeaf predicates yet. However, we still
832	// need to note the hidden operand to get GIM_CheckNumOperands correct.
833	InsnMatcher.addOperand(OpIdx: OpIdx++, SymbolicName: "", AllocatedTemporariesBaseID: TempOpIdx);
834	return InsnMatcher;
835	}
836
837	// Special case because the operand order is changed from setcc. The
838	// predicate operand needs to be swapped from the last operand to the first
839	// source.
840
841	unsigned NumChildren = Src.getNumChildren();
842	bool IsFCmp = SrcGIOrNull->TheDef->getName() == "G_FCMP";
843
844	if (IsFCmp || SrcGIOrNull->TheDef->getName() == "G_ICMP") {
845	const TreePatternNode &SrcChild = Src.getChild(N: NumChildren - 1);
846	if (SrcChild.isLeaf()) {
847	DefInit *DI = dyn_cast<DefInit>(Val: SrcChild.getLeafValue());
848	Record *CCDef = DI ? DI->getDef() : nullptr;
849	if (!CCDef || !CCDef->isSubClassOf(Name: "CondCode"))
850	return failedImport(Reason: "Unable to handle CondCode");
851
852	OperandMatcher &OM =
853	InsnMatcher.addOperand(OpIdx: OpIdx++, SymbolicName: SrcChild.getName(), AllocatedTemporariesBaseID: TempOpIdx);
854	StringRef PredType = IsFCmp ? CCDef->getValueAsString(FieldName: "FCmpPredicate")
855	: CCDef->getValueAsString(FieldName: "ICmpPredicate");
856
857	if (!PredType.empty()) {
858	OM.addPredicate<CmpPredicateOperandMatcher>(args: std::string(PredType));
859	// Process the other 2 operands normally.
860	--NumChildren;
861	}
862	}
863	}
864
865	// Match the used operands (i.e. the children of the operator).
866	bool IsIntrinsic =
867	SrcGIOrNull->TheDef->getName() == "G_INTRINSIC" ||
868	SrcGIOrNull->TheDef->getName() == "G_INTRINSIC_W_SIDE_EFFECTS" ||
869	SrcGIOrNull->TheDef->getName() == "G_INTRINSIC_CONVERGENT" ||
870	SrcGIOrNull->TheDef->getName() ==
871	"G_INTRINSIC_CONVERGENT_W_SIDE_EFFECTS";
872	const CodeGenIntrinsic *II = Src.getIntrinsicInfo(CDP: CGP);
873	if (IsIntrinsic && !II)
874	return failedImport(Reason: "Expected IntInit containing intrinsic ID)");
875
876	for (unsigned i = 0; i != NumChildren; ++i) {
877	const TreePatternNode &SrcChild = Src.getChild(N: i);
878
879	// We need to determine the meaning of a literal integer based on the
880	// context. If this is a field required to be an immediate (such as an
881	// immarg intrinsic argument), the required predicates are different than
882	// a constant which may be materialized in a register. If we have an
883	// argument that is required to be an immediate, we should not emit an LLT
884	// type check, and should not be looking for a G_CONSTANT defined
885	// register.
886	bool OperandIsImmArg = SrcGIOrNull->isInOperandImmArg(i);
887
888	// SelectionDAG allows pointers to be represented with iN since it doesn't
889	// distinguish between pointers and integers but they are different types
890	// in GlobalISel. Coerce integers to pointers to address space 0 if the
891	// context indicates a pointer.
892	//
893	bool OperandIsAPointer = SrcGIOrNull->isInOperandAPointer(i);
894
895	if (IsIntrinsic) {
896	// For G_INTRINSIC/G_INTRINSIC_W_SIDE_EFFECTS, the operand immediately
897	// following the defs is an intrinsic ID.
898	if (i == 0) {
899	OperandMatcher &OM =
900	InsnMatcher.addOperand(OpIdx: OpIdx++, SymbolicName: SrcChild.getName(), AllocatedTemporariesBaseID: TempOpIdx);
901	OM.addPredicate<IntrinsicIDOperandMatcher>(args&: II);
902	continue;
903	}
904
905	// We have to check intrinsics for llvm_anyptr_ty and immarg parameters.
906	//
907	// Note that we have to look at the i-1th parameter, because we don't
908	// have the intrinsic ID in the intrinsic's parameter list.
909	OperandIsAPointer |= II->isParamAPointer(ParamIdx: i - 1);
910	OperandIsImmArg |= II->isParamImmArg(ParamIdx: i - 1);
911	}
912
913	if (auto Error =
914	importChildMatcher(Rule, InsnMatcher, SrcChild, OperandIsAPointer,
915	OperandIsImmArg, OpIdx: OpIdx++, TempOpIdx))
916	return std::move(Error);
917	}
918	}
919
920	return InsnMatcher;
921	}
922
923	Error GlobalISelEmitter::importComplexPatternOperandMatcher(
924	OperandMatcher &OM, Record *R, unsigned &TempOpIdx) const {
925	const auto &ComplexPattern = ComplexPatternEquivs.find(Val: R);
926	if (ComplexPattern == ComplexPatternEquivs.end())
927	return failedImport(Reason: "SelectionDAG ComplexPattern (" + R->getName() +
928	") not mapped to GlobalISel");
929
930	OM.addPredicate<ComplexPatternOperandMatcher>(args&: OM, args: *ComplexPattern->second);
931	TempOpIdx++;
932	return Error::success();
933	}
934
935	// Get the name to use for a pattern operand. For an anonymous physical register
936	// input, this should use the register name.
937	static StringRef getSrcChildName(const TreePatternNode &SrcChild,
938	Record *&PhysReg) {
939	StringRef SrcChildName = SrcChild.getName();
940	if (SrcChildName.empty() && SrcChild.isLeaf()) {
941	if (auto *ChildDefInit = dyn_cast<DefInit>(Val: SrcChild.getLeafValue())) {
942	auto *ChildRec = ChildDefInit->getDef();
943	if (ChildRec->isSubClassOf(Name: "Register")) {
944	SrcChildName = ChildRec->getName();
945	PhysReg = ChildRec;
946	}
947	}
948	}
949
950	return SrcChildName;
951	}
952
953	Error GlobalISelEmitter::importChildMatcher(
954	RuleMatcher &Rule, InstructionMatcher &InsnMatcher,
955	const TreePatternNode &SrcChild, bool OperandIsAPointer,
956	bool OperandIsImmArg, unsigned OpIdx, unsigned &TempOpIdx) {
957
958	Record *PhysReg = nullptr;
959	std::string SrcChildName = std::string(getSrcChildName(SrcChild, PhysReg));
960	if (!SrcChild.isLeaf() &&
961	SrcChild.getOperator()->isSubClassOf(Name: "ComplexPattern")) {
962	// The "name" of a non-leaf complex pattern (MY_PAT $op1, $op2) is
963	// "MY_PAT:op1:op2" and the ones with same "name" represent same operand.
964	std::string PatternName = std::string(SrcChild.getOperator()->getName());
965	for (unsigned i = 0; i < SrcChild.getNumChildren(); ++i) {
966	PatternName += ":";
967	PatternName += SrcChild.getChild(N: i).getName();
968	}
969	SrcChildName = PatternName;
970	}
971
972	OperandMatcher &OM =
973	PhysReg ? InsnMatcher.addPhysRegInput(Reg: PhysReg, OpIdx, TempOpIdx)
974	: InsnMatcher.addOperand(OpIdx, SymbolicName: SrcChildName, AllocatedTemporariesBaseID: TempOpIdx);
975	if (OM.isSameAsAnotherOperand())
976	return Error::success();
977
978	ArrayRef<TypeSetByHwMode> ChildTypes = SrcChild.getExtTypes();
979	if (ChildTypes.size() != 1)
980	return failedImport(Reason: "Src pattern child has multiple results");
981
982	// Check MBB's before the type check since they are not a known type.
983	if (!SrcChild.isLeaf()) {
984	if (SrcChild.getOperator()->isSubClassOf(Name: "SDNode")) {
985	auto &ChildSDNI = CGP.getSDNodeInfo(R: SrcChild.getOperator());
986	if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
987	OM.addPredicate<MBBOperandMatcher>();
988	return Error::success();
989	}
990	if (SrcChild.getOperator()->getName() == "timm") {
991	OM.addPredicate<ImmOperandMatcher>();
992
993	// Add predicates, if any
994	for (const TreePredicateCall &Call : SrcChild.getPredicateCalls()) {
995	const TreePredicateFn &Predicate = Call.Fn;
996
997	// Only handle immediate patterns for now
998	if (Predicate.isImmediatePattern()) {
999	OM.addPredicate<OperandImmPredicateMatcher>(args: Predicate);
1000	}
1001	}
1002
1003	return Error::success();
1004	}
1005	}
1006	}
1007
1008	// Immediate arguments have no meaningful type to check as they don't have
1009	// registers.
1010	if (!OperandIsImmArg) {
1011	if (auto Error =
1012	OM.addTypeCheckPredicate(VTy: ChildTypes.front(), OperandIsAPointer))
1013	return failedImport(Reason: toString(E: std::move(Error)) + " for Src operand (" +
1014	to_string(Value: SrcChild) + ")");
1015	}
1016
1017	// Try look up SrcChild for a (named) predicate operand if there is any.
1018	if (WaitingForNamedOperands) {
1019	auto &ScopedNames = SrcChild.getNamesAsPredicateArg();
1020	if (!ScopedNames.empty()) {
1021	auto PA = ScopedNames.begin();
1022	std::string Name = getScopedName(Scope: PA->getScope(), Name: PA->getIdentifier());
1023	OM.addPredicate<RecordNamedOperandMatcher>(args&: StoreIdxForName[Name], args&: Name);
1024	--WaitingForNamedOperands;
1025	}
1026	}
1027
1028	// Check for nested instructions.
1029	if (!SrcChild.isLeaf()) {
1030	if (SrcChild.getOperator()->isSubClassOf(Name: "ComplexPattern")) {
1031	// When a ComplexPattern is used as an operator, it should do the same
1032	// thing as when used as a leaf. However, the children of the operator
1033	// name the sub-operands that make up the complex operand and we must
1034	// prepare to reference them in the renderer too.
1035	unsigned RendererID = TempOpIdx;
1036	if (auto Error = importComplexPatternOperandMatcher(
1037	OM, R: SrcChild.getOperator(), TempOpIdx))
1038	return Error;
1039
1040	for (unsigned i = 0, e = SrcChild.getNumChildren(); i != e; ++i) {
1041	auto &SubOperand = SrcChild.getChild(N: i);
1042	if (!SubOperand.getName().empty()) {
1043	if (auto Error = Rule.defineComplexSubOperand(
1044	SymbolicName: SubOperand.getName(), ComplexPattern: SrcChild.getOperator(), RendererID, SubOperandID: i,
1045	ParentSymbolicName: SrcChildName))
1046	return Error;
1047	}
1048	}
1049
1050	return Error::success();
1051	}
1052
1053	auto MaybeInsnOperand = OM.addPredicate<InstructionOperandMatcher>(
1054	args&: InsnMatcher.getRuleMatcher(), args: SrcChild.getName());
1055	if (!MaybeInsnOperand) {
1056	// This isn't strictly true. If the user were to provide exactly the same
1057	// matchers as the original operand then we could allow it. However, it's
1058	// simpler to not permit the redundant specification.
1059	return failedImport(
1060	Reason: "Nested instruction cannot be the same as another operand");
1061	}
1062
1063	// Map the node to a gMIR instruction.
1064	InstructionOperandMatcher &InsnOperand = **MaybeInsnOperand;
1065	auto InsnMatcherOrError = createAndImportSelDAGMatcher(
1066	Rule, InsnMatcher&: InsnOperand.getInsnMatcher(), Src: SrcChild, TempOpIdx);
1067	if (auto Error = InsnMatcherOrError.takeError())
1068	return Error;
1069
1070	return Error::success();
1071	}
1072
1073	if (SrcChild.hasAnyPredicate())
1074	return failedImport(Reason: "Src pattern child has unsupported predicate");
1075
1076	// Check for constant immediates.
1077	if (auto *ChildInt = dyn_cast<IntInit>(Val: SrcChild.getLeafValue())) {
1078	if (OperandIsImmArg) {
1079	// Checks for argument directly in operand list
1080	OM.addPredicate<LiteralIntOperandMatcher>(args: ChildInt->getValue());
1081	} else {
1082	// Checks for materialized constant
1083	OM.addPredicate<ConstantIntOperandMatcher>(args: ChildInt->getValue());
1084	}
1085	return Error::success();
1086	}
1087
1088	// Check for def's like register classes or ComplexPattern's.
1089	if (auto *ChildDefInit = dyn_cast<DefInit>(Val: SrcChild.getLeafValue())) {
1090	auto *ChildRec = ChildDefInit->getDef();
1091
1092	// Check for register classes.
1093	if (ChildRec->isSubClassOf(Name: "RegisterClass") ||
1094	ChildRec->isSubClassOf(Name: "RegisterOperand")) {
1095	OM.addPredicate<RegisterBankOperandMatcher>(
1096	args: Target.getRegisterClass(R: getInitValueAsRegClass(V: ChildDefInit)));
1097	return Error::success();
1098	}
1099
1100	if (ChildRec->isSubClassOf(Name: "Register")) {
1101	// This just be emitted as a copy to the specific register.
1102	ValueTypeByHwMode VT = ChildTypes.front().getValueTypeByHwMode();
1103	const CodeGenRegisterClass *RC =
1104	CGRegs.getMinimalPhysRegClass(RegRecord: ChildRec, VT: &VT);
1105	if (!RC) {
1106	return failedImport(
1107	Reason: "Could not determine physical register class of pattern source");
1108	}
1109
1110	OM.addPredicate<RegisterBankOperandMatcher>(args: *RC);
1111	return Error::success();
1112	}
1113
1114	// Check for ValueType.
1115	if (ChildRec->isSubClassOf(Name: "ValueType")) {
1116	// We already added a type check as standard practice so this doesn't need
1117	// to do anything.
1118	return Error::success();
1119	}
1120
1121	// Check for ComplexPattern's.
1122	if (ChildRec->isSubClassOf(Name: "ComplexPattern"))
1123	return importComplexPatternOperandMatcher(OM, R: ChildRec, TempOpIdx);
1124
1125	if (ChildRec->isSubClassOf(Name: "ImmLeaf")) {
1126	return failedImport(
1127	Reason: "Src pattern child def is an unsupported tablegen class (ImmLeaf)");
1128	}
1129
1130	// Place holder for SRCVALUE nodes. Nothing to do here.
1131	if (ChildRec->getName() == "srcvalue")
1132	return Error::success();
1133
1134	const bool ImmAllOnesV = ChildRec->getName() == "immAllOnesV";
1135	if (ImmAllOnesV || ChildRec->getName() == "immAllZerosV") {
1136	auto MaybeInsnOperand = OM.addPredicate<InstructionOperandMatcher>(
1137	args&: InsnMatcher.getRuleMatcher(), args: SrcChild.getName(), args: false);
1138	InstructionOperandMatcher &InsnOperand = **MaybeInsnOperand;
1139
1140	ValueTypeByHwMode VTy = ChildTypes.front().getValueTypeByHwMode();
1141
1142	const CodeGenInstruction &BuildVector =
1143	Target.getInstruction(InstRec: RK.getDef(Name: "G_BUILD_VECTOR"));
1144	const CodeGenInstruction &BuildVectorTrunc =
1145	Target.getInstruction(InstRec: RK.getDef(Name: "G_BUILD_VECTOR_TRUNC"));
1146
1147	// Treat G_BUILD_VECTOR as the canonical opcode, and G_BUILD_VECTOR_TRUNC
1148	// as an alternative.
1149	InsnOperand.getInsnMatcher().addPredicate<InstructionOpcodeMatcher>(
1150	args: ArrayRef({&BuildVector, &BuildVectorTrunc}));
1151
1152	// TODO: Handle both G_BUILD_VECTOR and G_BUILD_VECTOR_TRUNC We could
1153	// theoretically not emit any opcode check, but getOpcodeMatcher currently
1154	// has to succeed.
1155	OperandMatcher &OM =
1156	InsnOperand.getInsnMatcher().addOperand(OpIdx: 0, SymbolicName: "", AllocatedTemporariesBaseID: TempOpIdx);
1157	if (auto Error =
1158	OM.addTypeCheckPredicate(VTy, OperandIsAPointer: false /* OperandIsAPointer */))
1159	return failedImport(Reason: toString(E: std::move(Error)) +
1160	" for result of Src pattern operator");
1161
1162	InsnOperand.getInsnMatcher().addPredicate<VectorSplatImmPredicateMatcher>(
1163	args: ImmAllOnesV ? VectorSplatImmPredicateMatcher::AllOnes
1164	: VectorSplatImmPredicateMatcher::AllZeros);
1165	return Error::success();
1166	}
1167
1168	return failedImport(
1169	Reason: "Src pattern child def is an unsupported tablegen class");
1170	}
1171
1172	return failedImport(Reason: "Src pattern child is an unsupported kind");
1173	}
1174
1175	Expected<action_iterator> GlobalISelEmitter::importExplicitUseRenderer(
1176	action_iterator InsertPt, RuleMatcher &Rule, BuildMIAction &DstMIBuilder,
1177	const TreePatternNode &DstChild, const TreePatternNode &Src) {
1178
1179	const auto &SubOperand = Rule.getComplexSubOperand(SymbolicName: DstChild.getName());
1180	if (SubOperand) {
1181	DstMIBuilder.addRenderer<RenderComplexPatternOperand>(
1182	args&: *std::get<0>(t: *SubOperand), args: DstChild.getName(), args: std::get<1>(t: *SubOperand),
1183	args: std::get<2>(t: *SubOperand));
1184	return InsertPt;
1185	}
1186
1187	if (!DstChild.isLeaf()) {
1188	if (DstChild.getOperator()->isSubClassOf(Name: "SDNodeXForm")) {
1189	auto &Child = DstChild.getChild(N: 0);
1190	auto I = SDNodeXFormEquivs.find(Val: DstChild.getOperator());
1191	if (I != SDNodeXFormEquivs.end()) {
1192	Record *XFormOpc = DstChild.getOperator()->getValueAsDef(FieldName: "Opcode");
1193	if (XFormOpc->getName() == "timm") {
1194	// If this is a TargetConstant, there won't be a corresponding
1195	// instruction to transform. Instead, this will refer directly to an
1196	// operand in an instruction's operand list.
1197	DstMIBuilder.addRenderer<CustomOperandRenderer>(args: *I->second,
1198	args: Child.getName());
1199	} else {
1200	DstMIBuilder.addRenderer<CustomRenderer>(args: *I->second, args: Child.getName());
1201	}
1202
1203	return InsertPt;
1204	}
1205	return failedImport(Reason: "SDNodeXForm " + Child.getName() +
1206	" has no custom renderer");
1207	}
1208
1209	// We accept 'bb' here. It's an operator because BasicBlockSDNode isn't
1210	// inline, but in MI it's just another operand.
1211	if (DstChild.getOperator()->isSubClassOf(Name: "SDNode")) {
1212	auto &ChildSDNI = CGP.getSDNodeInfo(R: DstChild.getOperator());
1213	if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
1214	DstMIBuilder.addRenderer<CopyRenderer>(args: DstChild.getName());
1215	return InsertPt;
1216	}
1217	}
1218
1219	// Similarly, imm is an operator in TreePatternNode's view but must be
1220	// rendered as operands.
1221	// FIXME: The target should be able to choose sign-extended when appropriate
1222	// (e.g. on Mips).
1223	if (DstChild.getOperator()->getName() == "timm") {
1224	DstMIBuilder.addRenderer<CopyRenderer>(args: DstChild.getName());
1225	return InsertPt;
1226	} else if (DstChild.getOperator()->getName() == "imm") {
1227	DstMIBuilder.addRenderer<CopyConstantAsImmRenderer>(args: DstChild.getName());
1228	return InsertPt;
1229	} else if (DstChild.getOperator()->getName() == "fpimm") {
1230	DstMIBuilder.addRenderer<CopyFConstantAsFPImmRenderer>(
1231	args: DstChild.getName());
1232	return InsertPt;
1233	}
1234
1235	if (DstChild.getOperator()->isSubClassOf(Name: "Instruction")) {
1236	auto OpTy = getInstResultType(Dst: DstChild, Target);
1237	if (!OpTy)
1238	return OpTy.takeError();
1239
1240	unsigned TempRegID = Rule.allocateTempRegID();
1241	InsertPt =
1242	Rule.insertAction<MakeTempRegisterAction>(InsertPt, args&: *OpTy, args&: TempRegID);
1243	DstMIBuilder.addRenderer<TempRegRenderer>(args&: TempRegID);
1244
1245	auto InsertPtOrError = createAndImportSubInstructionRenderer(
1246	InsertPt: ++InsertPt, M&: Rule, Dst: DstChild, Src, TempReg: TempRegID);
1247	if (auto Error = InsertPtOrError.takeError())
1248	return std::move(Error);
1249	return InsertPtOrError.get();
1250	}
1251
1252	return failedImport(Reason: "Dst pattern child isn't a leaf node or an MBB" +
1253	llvm::to_string(Value: DstChild));
1254	}
1255
1256	// It could be a specific immediate in which case we should just check for
1257	// that immediate.
1258	if (const IntInit *ChildIntInit =
1259	dyn_cast<IntInit>(Val: DstChild.getLeafValue())) {
1260	DstMIBuilder.addRenderer<ImmRenderer>(args: ChildIntInit->getValue());
1261	return InsertPt;
1262	}
1263
1264	// Otherwise, we're looking for a bog-standard RegisterClass operand.
1265	if (auto *ChildDefInit = dyn_cast<DefInit>(Val: DstChild.getLeafValue())) {
1266	auto *ChildRec = ChildDefInit->getDef();
1267
1268	ArrayRef<TypeSetByHwMode> ChildTypes = DstChild.getExtTypes();
1269	if (ChildTypes.size() != 1)
1270	return failedImport(Reason: "Dst pattern child has multiple results");
1271
1272	std::optional<LLTCodeGen> OpTyOrNone;
1273	if (ChildTypes.front().isMachineValueType())
1274	OpTyOrNone = MVTToLLT(SVT: ChildTypes.front().getMachineValueType().SimpleTy);
1275	if (!OpTyOrNone)
1276	return failedImport(Reason: "Dst operand has an unsupported type");
1277
1278	if (ChildRec->isSubClassOf(Name: "Register")) {
1279	DstMIBuilder.addRenderer<AddRegisterRenderer>(args: Target, args&: ChildRec);
1280	return InsertPt;
1281	}
1282
1283	if (ChildRec->isSubClassOf(Name: "RegisterClass") ||
1284	ChildRec->isSubClassOf(Name: "RegisterOperand") ||
1285	ChildRec->isSubClassOf(Name: "ValueType")) {
1286	if (ChildRec->isSubClassOf(Name: "RegisterOperand") &&
1287	!ChildRec->isValueUnset(FieldName: "GIZeroRegister")) {
1288	DstMIBuilder.addRenderer<CopyOrAddZeroRegRenderer>(
1289	args: DstChild.getName(), args: ChildRec->getValueAsDef(FieldName: "GIZeroRegister"));
1290	return InsertPt;
1291	}
1292
1293	DstMIBuilder.addRenderer<CopyRenderer>(args: DstChild.getName());
1294	return InsertPt;
1295	}
1296
1297	if (ChildRec->isSubClassOf(Name: "SubRegIndex")) {
1298	CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(ChildRec);
1299	DstMIBuilder.addRenderer<ImmRenderer>(args: SubIdx->EnumValue);
1300	return InsertPt;
1301	}
1302
1303	if (ChildRec->isSubClassOf(Name: "ComplexPattern")) {
1304	const auto &ComplexPattern = ComplexPatternEquivs.find(Val: ChildRec);
1305	if (ComplexPattern == ComplexPatternEquivs.end())
1306	return failedImport(
1307	Reason: "SelectionDAG ComplexPattern not mapped to GlobalISel");
1308
1309	const OperandMatcher &OM = Rule.getOperandMatcher(Name: DstChild.getName());
1310	DstMIBuilder.addRenderer<RenderComplexPatternOperand>(
1311	args: *ComplexPattern->second, args: DstChild.getName(),
1312	args: OM.getAllocatedTemporariesBaseID());
1313	return InsertPt;
1314	}
1315
1316	return failedImport(
1317	Reason: "Dst pattern child def is an unsupported tablegen class");
1318	}
1319
1320	// Handle the case where the MVT/register class is omitted in the dest pattern
1321	// but MVT exists in the source pattern.
1322	if (isa<UnsetInit>(Val: DstChild.getLeafValue())) {
1323	for (unsigned NumOp = 0; NumOp < Src.getNumChildren(); NumOp++)
1324	if (Src.getChild(N: NumOp).getName() == DstChild.getName()) {
1325	DstMIBuilder.addRenderer<CopyRenderer>(args: Src.getChild(N: NumOp).getName());
1326	return InsertPt;
1327	}
1328	}
1329	return failedImport(Reason: "Dst pattern child is an unsupported kind");
1330	}
1331
1332	Expected<BuildMIAction &> GlobalISelEmitter::createAndImportInstructionRenderer(
1333	RuleMatcher &M, InstructionMatcher &InsnMatcher, const TreePatternNode &Src,
1334	const TreePatternNode &Dst) {
1335	auto InsertPtOrError = createInstructionRenderer(InsertPt: M.actions_end(), M, Dst);
1336	if (auto Error = InsertPtOrError.takeError())
1337	return std::move(Error);
1338
1339	action_iterator InsertPt = InsertPtOrError.get();
1340	BuildMIAction &DstMIBuilder = *static_cast<BuildMIAction *>(InsertPt->get());
1341
1342	for (auto PhysInput : InsnMatcher.getPhysRegInputs()) {
1343	InsertPt = M.insertAction<BuildMIAction>(
1344	InsertPt, args: M.allocateOutputInsnID(),
1345	args: &Target.getInstruction(InstRec: RK.getDef(Name: "COPY")));
1346	BuildMIAction &CopyToPhysRegMIBuilder =
1347	*static_cast<BuildMIAction *>(InsertPt->get());
1348	CopyToPhysRegMIBuilder.addRenderer<AddRegisterRenderer>(
1349	args: Target, args&: PhysInput.first, args: true);
1350	CopyToPhysRegMIBuilder.addRenderer<CopyPhysRegRenderer>(args&: PhysInput.first);
1351	}
1352
1353	if (auto Error =
1354	importExplicitDefRenderers(InsertPt, M, DstMIBuilder, Src, Dst)
1355	.takeError())
1356	return std::move(Error);
1357
1358	if (auto Error =
1359	importExplicitUseRenderers(InsertPt, M, DstMIBuilder, Dst, Src)
1360	.takeError())
1361	return std::move(Error);
1362
1363	return DstMIBuilder;
1364	}
1365
1366	Expected<action_iterator>
1367	GlobalISelEmitter::createAndImportSubInstructionRenderer(
1368	const action_iterator InsertPt, RuleMatcher &M, const TreePatternNode &Dst,
1369	const TreePatternNode &Src, unsigned TempRegID) {
1370	auto InsertPtOrError = createInstructionRenderer(InsertPt, M, Dst);
1371
1372	// TODO: Assert there's exactly one result.
1373
1374	if (auto Error = InsertPtOrError.takeError())
1375	return std::move(Error);
1376
1377	BuildMIAction &DstMIBuilder =
1378	*static_cast<BuildMIAction *>(InsertPtOrError.get()->get());
1379
1380	// Assign the result to TempReg.
1381	DstMIBuilder.addRenderer<TempRegRenderer>(args&: TempRegID, args: true);
1382
1383	// Handle additional (ignored) results.
1384	if (DstMIBuilder.getCGI()->Operands.NumDefs > 1) {
1385	InsertPtOrError = importExplicitDefRenderers(
1386	InsertPt: std::prev(x: *InsertPtOrError), M, DstMIBuilder, Src, Dst, /*Start=*/1);
1387	if (auto Error = InsertPtOrError.takeError())
1388	return std::move(Error);
1389	}
1390
1391	InsertPtOrError = importExplicitUseRenderers(InsertPt: InsertPtOrError.get(), M,
1392	DstMIBuilder, Dst, Src);
1393	if (auto Error = InsertPtOrError.takeError())
1394	return std::move(Error);
1395
1396	// We need to make sure that when we import an INSERT_SUBREG as a
1397	// subinstruction that it ends up being constrained to the correct super
1398	// register and subregister classes.
1399	auto OpName = Target.getInstruction(InstRec: Dst.getOperator()).TheDef->getName();
1400	if (OpName == "INSERT_SUBREG") {
1401	auto SubClass = inferRegClassFromPattern(N: Dst.getChild(N: 1));
1402	if (!SubClass)
1403	return failedImport(
1404	Reason: "Cannot infer register class from INSERT_SUBREG operand #1");
1405	std::optional<const CodeGenRegisterClass *> SuperClass =
1406	inferSuperRegisterClassForNode(Ty: Dst.getExtType(ResNo: 0), SuperRegNode: Dst.getChild(N: 0),
1407	SubRegIdxNode: Dst.getChild(N: 2));
1408	if (!SuperClass)
1409	return failedImport(
1410	Reason: "Cannot infer register class for INSERT_SUBREG operand #0");
1411	// The destination and the super register source of an INSERT_SUBREG must
1412	// be the same register class.
1413	M.insertAction<ConstrainOperandToRegClassAction>(
1414	InsertPt, args: DstMIBuilder.getInsnID(), args: 0, args: **SuperClass);
1415	M.insertAction<ConstrainOperandToRegClassAction>(
1416	InsertPt, args: DstMIBuilder.getInsnID(), args: 1, args: **SuperClass);
1417	M.insertAction<ConstrainOperandToRegClassAction>(
1418	InsertPt, args: DstMIBuilder.getInsnID(), args: 2, args: **SubClass);
1419	return InsertPtOrError.get();
1420	}
1421
1422	if (OpName == "EXTRACT_SUBREG") {
1423	// EXTRACT_SUBREG selects into a subregister COPY but unlike most
1424	// instructions, the result register class is controlled by the
1425	// subregisters of the operand. As a result, we must constrain the result
1426	// class rather than check that it's already the right one.
1427	auto SuperClass = inferRegClassFromPattern(N: Dst.getChild(N: 0));
1428	if (!SuperClass)
1429	return failedImport(
1430	Reason: "Cannot infer register class from EXTRACT_SUBREG operand #0");
1431
1432	auto SubIdx = inferSubRegIndexForNode(SubRegIdxNode: Dst.getChild(N: 1));
1433	if (!SubIdx)
1434	return failedImport(Reason: "EXTRACT_SUBREG child #1 is not a subreg index");
1435
1436	const auto SrcRCDstRCPair =
1437	(*SuperClass)->getMatchingSubClassWithSubRegs(RegBank&: CGRegs, SubIdx: *SubIdx);
1438	assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass");
1439	M.insertAction<ConstrainOperandToRegClassAction>(
1440	InsertPt, args: DstMIBuilder.getInsnID(), args: 0, args&: *SrcRCDstRCPair->second);
1441	M.insertAction<ConstrainOperandToRegClassAction>(
1442	InsertPt, args: DstMIBuilder.getInsnID(), args: 1, args&: *SrcRCDstRCPair->first);
1443
1444	// We're done with this pattern! It's eligible for GISel emission; return
1445	// it.
1446	return InsertPtOrError.get();
1447	}
1448
1449	// Similar to INSERT_SUBREG, we also have to handle SUBREG_TO_REG as a
1450	// subinstruction.
1451	if (OpName == "SUBREG_TO_REG") {
1452	auto SubClass = inferRegClassFromPattern(N: Dst.getChild(N: 1));
1453	if (!SubClass)
1454	return failedImport(
1455	Reason: "Cannot infer register class from SUBREG_TO_REG child #1");
1456	auto SuperClass =
1457	inferSuperRegisterClass(Ty: Dst.getExtType(ResNo: 0), SubRegIdxNode: Dst.getChild(N: 2));
1458	if (!SuperClass)
1459	return failedImport(
1460	Reason: "Cannot infer register class for SUBREG_TO_REG operand #0");
1461	M.insertAction<ConstrainOperandToRegClassAction>(
1462	InsertPt, args: DstMIBuilder.getInsnID(), args: 0, args: **SuperClass);
1463	M.insertAction<ConstrainOperandToRegClassAction>(
1464	InsertPt, args: DstMIBuilder.getInsnID(), args: 2, args: **SubClass);
1465	return InsertPtOrError.get();
1466	}
1467
1468	if (OpName == "REG_SEQUENCE") {
1469	auto SuperClass = inferRegClassFromPattern(N: Dst.getChild(N: 0));
1470	M.insertAction<ConstrainOperandToRegClassAction>(
1471	InsertPt, args: DstMIBuilder.getInsnID(), args: 0, args: **SuperClass);
1472
1473	unsigned Num = Dst.getNumChildren();
1474	for (unsigned I = 1; I != Num; I += 2) {
1475	const TreePatternNode &SubRegChild = Dst.getChild(N: I + 1);
1476
1477	auto SubIdx = inferSubRegIndexForNode(SubRegIdxNode: SubRegChild);
1478	if (!SubIdx)
1479	return failedImport(Reason: "REG_SEQUENCE child is not a subreg index");
1480
1481	const auto SrcRCDstRCPair =
1482	(*SuperClass)->getMatchingSubClassWithSubRegs(RegBank&: CGRegs, SubIdx: *SubIdx);
1483	assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass");
1484	M.insertAction<ConstrainOperandToRegClassAction>(
1485	InsertPt, args: DstMIBuilder.getInsnID(), args&: I, args&: *SrcRCDstRCPair->second);
1486	}
1487
1488	return InsertPtOrError.get();
1489	}
1490
1491	M.insertAction<ConstrainOperandsToDefinitionAction>(InsertPt,
1492	args: DstMIBuilder.getInsnID());
1493	return InsertPtOrError.get();
1494	}
1495
1496	Expected<action_iterator> GlobalISelEmitter::createInstructionRenderer(
1497	action_iterator InsertPt, RuleMatcher &M, const TreePatternNode &Dst) {
1498	Record *DstOp = Dst.getOperator();
1499	if (!DstOp->isSubClassOf(Name: "Instruction")) {
1500	if (DstOp->isSubClassOf(Name: "ValueType"))
1501	return failedImport(
1502	Reason: "Pattern operator isn't an instruction (it's a ValueType)");
1503	return failedImport(Reason: "Pattern operator isn't an instruction");
1504	}
1505	CodeGenInstruction *DstI = &Target.getInstruction(InstRec: DstOp);
1506
1507	// COPY_TO_REGCLASS is just a copy with a ConstrainOperandToRegClassAction
1508	// attached. Similarly for EXTRACT_SUBREG except that's a subregister copy.
1509	StringRef Name = DstI->TheDef->getName();
1510	if (Name == "COPY_TO_REGCLASS" || Name == "EXTRACT_SUBREG")
1511	DstI = &Target.getInstruction(InstRec: RK.getDef(Name: "COPY"));
1512
1513	return M.insertAction<BuildMIAction>(InsertPt, args: M.allocateOutputInsnID(),
1514	args&: DstI);
1515	}
1516
1517	Expected<action_iterator> GlobalISelEmitter::importExplicitDefRenderers(
1518	action_iterator InsertPt, RuleMatcher &M, BuildMIAction &DstMIBuilder,
1519	const TreePatternNode &Src, const TreePatternNode &Dst, unsigned Start) {
1520	const CodeGenInstruction *DstI = DstMIBuilder.getCGI();
1521	const unsigned SrcNumDefs = Src.getExtTypes().size();
1522	const unsigned DstNumDefs = DstI->Operands.NumDefs;
1523	if (DstNumDefs == 0)
1524	return InsertPt;
1525
1526	for (unsigned I = Start; I < SrcNumDefs; ++I) {
1527	std::string OpName = getMangledRootDefName(DefOperandName: DstI->Operands[I].Name);
1528	// CopyRenderer saves a StringRef, so cannot pass OpName itself -
1529	// let's use a string with an appropriate lifetime.
1530	StringRef PermanentRef = M.getOperandMatcher(Name: OpName).getSymbolicName();
1531	DstMIBuilder.addRenderer<CopyRenderer>(args&: PermanentRef);
1532	}
1533
1534	// Some instructions have multiple defs, but are missing a type entry
1535	// (e.g. s_cc_out operands).
1536	if (Dst.getExtTypes().size() < DstNumDefs)
1537	return failedImport(Reason: "unhandled discarded def");
1538
1539	for (unsigned I = SrcNumDefs; I < DstNumDefs; ++I) {
1540	const TypeSetByHwMode &ExtTy = Dst.getExtType(ResNo: I);
1541	if (!ExtTy.isMachineValueType())
1542	return failedImport(Reason: "unsupported typeset");
1543
1544	auto OpTy = MVTToLLT(SVT: ExtTy.getMachineValueType().SimpleTy);
1545	if (!OpTy)
1546	return failedImport(Reason: "unsupported type");
1547
1548	unsigned TempRegID = M.allocateTempRegID();
1549	InsertPt =
1550	M.insertAction<MakeTempRegisterAction>(InsertPt, args&: *OpTy, args&: TempRegID);
1551	DstMIBuilder.addRenderer<TempRegRenderer>(args&: TempRegID, args: true, args: nullptr, args: true);
1552	}
1553
1554	return InsertPt;
1555	}
1556
1557	Expected<action_iterator> GlobalISelEmitter::importExplicitUseRenderers(
1558	action_iterator InsertPt, RuleMatcher &M, BuildMIAction &DstMIBuilder,
1559	const llvm::TreePatternNode &Dst, const llvm::TreePatternNode &Src) {
1560	const CodeGenInstruction *DstI = DstMIBuilder.getCGI();
1561	CodeGenInstruction *OrigDstI = &Target.getInstruction(InstRec: Dst.getOperator());
1562
1563	StringRef Name = OrigDstI->TheDef->getName();
1564	unsigned ExpectedDstINumUses = Dst.getNumChildren();
1565
1566	// EXTRACT_SUBREG needs to use a subregister COPY.
1567	if (Name == "EXTRACT_SUBREG") {
1568	if (!Dst.getChild(N: 1).isLeaf())
1569	return failedImport(Reason: "EXTRACT_SUBREG child #1 is not a leaf");
1570	DefInit *SubRegInit = dyn_cast<DefInit>(Val: Dst.getChild(N: 1).getLeafValue());
1571	if (!SubRegInit)
1572	return failedImport(Reason: "EXTRACT_SUBREG child #1 is not a subreg index");
1573
1574	CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(SubRegInit->getDef());
1575	const TreePatternNode &ValChild = Dst.getChild(N: 0);
1576	if (!ValChild.isLeaf()) {
1577	// We really have to handle the source instruction, and then insert a
1578	// copy from the subregister.
1579	auto ExtractSrcTy = getInstResultType(Dst: ValChild, Target);
1580	if (!ExtractSrcTy)
1581	return ExtractSrcTy.takeError();
1582
1583	unsigned TempRegID = M.allocateTempRegID();
1584	InsertPt = M.insertAction<MakeTempRegisterAction>(InsertPt, args&: *ExtractSrcTy,
1585	args&: TempRegID);
1586
1587	auto InsertPtOrError = createAndImportSubInstructionRenderer(
1588	InsertPt: ++InsertPt, M, Dst: ValChild, Src, TempRegID);
1589	if (auto Error = InsertPtOrError.takeError())
1590	return std::move(Error);
1591
1592	DstMIBuilder.addRenderer<TempRegRenderer>(args&: TempRegID, args: false, args&: SubIdx);
1593	return InsertPt;
1594	}
1595
1596	// If this is a source operand, this is just a subregister copy.
1597	Record *RCDef = getInitValueAsRegClass(V: ValChild.getLeafValue());
1598	if (!RCDef)
1599	return failedImport(Reason: "EXTRACT_SUBREG child #0 could not "
1600	"be coerced to a register class");
1601
1602	CodeGenRegisterClass *RC = CGRegs.getRegClass(RCDef);
1603
1604	const auto SrcRCDstRCPair =
1605	RC->getMatchingSubClassWithSubRegs(RegBank&: CGRegs, SubIdx);
1606	if (SrcRCDstRCPair) {
1607	assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass");
1608	if (SrcRCDstRCPair->first != RC)
1609	return failedImport(Reason: "EXTRACT_SUBREG requires an additional COPY");
1610	}
1611
1612	StringRef RegOperandName = Dst.getChild(N: 0).getName();
1613	if (const auto &SubOperand = M.getComplexSubOperand(SymbolicName: RegOperandName)) {
1614	DstMIBuilder.addRenderer<RenderComplexPatternOperand>(
1615	args&: *std::get<0>(t: *SubOperand), args&: RegOperandName, args: std::get<1>(t: *SubOperand),
1616	args: std::get<2>(t: *SubOperand), args&: SubIdx);
1617	return InsertPt;
1618	}
1619
1620	DstMIBuilder.addRenderer<CopySubRegRenderer>(args&: RegOperandName, args&: SubIdx);
1621	return InsertPt;
1622	}
1623
1624	if (Name == "REG_SEQUENCE") {
1625	if (!Dst.getChild(N: 0).isLeaf())
1626	return failedImport(Reason: "REG_SEQUENCE child #0 is not a leaf");
1627
1628	Record *RCDef = getInitValueAsRegClass(V: Dst.getChild(N: 0).getLeafValue());
1629	if (!RCDef)
1630	return failedImport(Reason: "REG_SEQUENCE child #0 could not "
1631	"be coerced to a register class");
1632
1633	if ((ExpectedDstINumUses - 1) % 2 != 0)
1634	return failedImport(Reason: "Malformed REG_SEQUENCE");
1635
1636	for (unsigned I = 1; I != ExpectedDstINumUses; I += 2) {
1637	const TreePatternNode &ValChild = Dst.getChild(N: I);
1638	const TreePatternNode &SubRegChild = Dst.getChild(N: I + 1);
1639
1640	if (DefInit *SubRegInit = dyn_cast<DefInit>(Val: SubRegChild.getLeafValue())) {
1641	CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(SubRegInit->getDef());
1642
1643	auto InsertPtOrError =
1644	importExplicitUseRenderer(InsertPt, Rule&: M, DstMIBuilder, DstChild: ValChild, Src);
1645	if (auto Error = InsertPtOrError.takeError())
1646	return std::move(Error);
1647	InsertPt = InsertPtOrError.get();
1648	DstMIBuilder.addRenderer<SubRegIndexRenderer>(args&: SubIdx);
1649	}
1650	}
1651
1652	return InsertPt;
1653	}
1654
1655	// Render the explicit uses.
1656	unsigned DstINumUses = OrigDstI->Operands.size() - OrigDstI->Operands.NumDefs;
1657	if (Name == "COPY_TO_REGCLASS") {
1658	DstINumUses--; // Ignore the class constraint.
1659	ExpectedDstINumUses--;
1660	}
1661
1662	// NumResults - This is the number of results produced by the instruction in
1663	// the "outs" list.
1664	unsigned NumResults = OrigDstI->Operands.NumDefs;
1665
1666	// Number of operands we know the output instruction must have. If it is
1667	// variadic, we could have more operands.
1668	unsigned NumFixedOperands = DstI->Operands.size();
1669
1670	// Loop over all of the fixed operands of the instruction pattern, emitting
1671	// code to fill them all in. The node 'N' usually has number children equal to
1672	// the number of input operands of the instruction. However, in cases where
1673	// there are predicate operands for an instruction, we need to fill in the
1674	// 'execute always' values. Match up the node operands to the instruction
1675	// operands to do this.
1676	unsigned Child = 0;
1677
1678	// Similarly to the code in TreePatternNode::ApplyTypeConstraints, count the
1679	// number of operands at the end of the list which have default values.
1680	// Those can come from the pattern if it provides enough arguments, or be
1681	// filled in with the default if the pattern hasn't provided them. But any
1682	// operand with a default value _before_ the last mandatory one will be
1683	// filled in with their defaults unconditionally.
1684	unsigned NonOverridableOperands = NumFixedOperands;
1685	while (NonOverridableOperands > NumResults &&
1686	CGP.operandHasDefault(Op: DstI->Operands[NonOverridableOperands - 1].Rec))
1687	--NonOverridableOperands;
1688
1689	unsigned NumDefaultOps = 0;
1690	for (unsigned I = 0; I != DstINumUses; ++I) {
1691	unsigned InstOpNo = DstI->Operands.NumDefs + I;
1692
1693	// Determine what to emit for this operand.
1694	Record *OperandNode = DstI->Operands[InstOpNo].Rec;
1695
1696	// If the operand has default values, introduce them now.
1697	if (CGP.operandHasDefault(Op: OperandNode) &&
1698	(InstOpNo < NonOverridableOperands || Child >= Dst.getNumChildren())) {
1699	// This is a predicate or optional def operand which the pattern has not
1700	// overridden, or which we aren't letting it override; emit the 'default
1701	// ops' operands.
1702
1703	Record *OperandNode = DstI->Operands[InstOpNo].Rec;
1704	if (auto Error = importDefaultOperandRenderers(
1705	InsertPt, M, DstMIBuilder, DefaultOp: CGP.getDefaultOperand(R: OperandNode)))
1706	return std::move(Error);
1707
1708	++NumDefaultOps;
1709	continue;
1710	}
1711
1712	auto InsertPtOrError = importExplicitUseRenderer(InsertPt, Rule&: M, DstMIBuilder,
1713	DstChild: Dst.getChild(N: Child), Src);
1714	if (auto Error = InsertPtOrError.takeError())
1715	return std::move(Error);
1716	InsertPt = InsertPtOrError.get();
1717	++Child;
1718	}
1719
1720	if (NumDefaultOps + ExpectedDstINumUses != DstINumUses)
1721	return failedImport(Reason: "Expected " + llvm::to_string(Value: DstINumUses) +
1722	" used operands but found " +
1723	llvm::to_string(Value: ExpectedDstINumUses) +
1724	" explicit ones and " + llvm::to_string(Value: NumDefaultOps) +
1725	" default ones");
1726
1727	return InsertPt;
1728	}
1729
1730	Error GlobalISelEmitter::importDefaultOperandRenderers(
1731	action_iterator InsertPt, RuleMatcher &M, BuildMIAction &DstMIBuilder,
1732	const DAGDefaultOperand &DefaultOp) const {
1733	for (const auto &Op : DefaultOp.DefaultOps) {
1734	const auto &N = *Op;
1735	if (!N.isLeaf())
1736	return failedImport(Reason: "Could not add default op");
1737
1738	const auto *DefaultOp = N.getLeafValue();
1739
1740	if (const DefInit *DefaultDefOp = dyn_cast<DefInit>(Val: DefaultOp)) {
1741	std::optional<LLTCodeGen> OpTyOrNone = MVTToLLT(SVT: N.getSimpleType(ResNo: 0));
1742	auto Def = DefaultDefOp->getDef();
1743	if (Def->getName() == "undef_tied_input") {
1744	unsigned TempRegID = M.allocateTempRegID();
1745	M.insertAction<MakeTempRegisterAction>(InsertPt, args&: *OpTyOrNone,
1746	args&: TempRegID);
1747	InsertPt = M.insertAction<BuildMIAction>(
1748	InsertPt, args: M.allocateOutputInsnID(),
1749	args: &Target.getInstruction(InstRec: RK.getDef(Name: "IMPLICIT_DEF")));
1750	BuildMIAction &IDMIBuilder =
1751	*static_cast<BuildMIAction *>(InsertPt->get());
1752	IDMIBuilder.addRenderer<TempRegRenderer>(args&: TempRegID);
1753	DstMIBuilder.addRenderer<TempRegRenderer>(args&: TempRegID);
1754	} else {
1755	DstMIBuilder.addRenderer<AddRegisterRenderer>(args: Target, args&: Def);
1756	}
1757	continue;
1758	}
1759
1760	if (const IntInit *DefaultIntOp = dyn_cast<IntInit>(Val: DefaultOp)) {
1761	DstMIBuilder.addRenderer<ImmRenderer>(args: DefaultIntOp->getValue());
1762	continue;
1763	}
1764
1765	return failedImport(Reason: "Could not add default op");
1766	}
1767
1768	return Error::success();
1769	}
1770
1771	Error GlobalISelEmitter::importImplicitDefRenderers(
1772	BuildMIAction &DstMIBuilder,
1773	const std::vector<Record *> &ImplicitDefs) const {
1774	if (!ImplicitDefs.empty())
1775	return failedImport(Reason: "Pattern defines a physical register");
1776	return Error::success();
1777	}
1778
1779	std::optional<const CodeGenRegisterClass *>
1780	GlobalISelEmitter::getRegClassFromLeaf(const TreePatternNode &Leaf) {
1781	assert(Leaf.isLeaf() && "Expected leaf?");
1782	Record *RCRec = getInitValueAsRegClass(V: Leaf.getLeafValue());
1783	if (!RCRec)
1784	return std::nullopt;
1785	CodeGenRegisterClass *RC = CGRegs.getRegClass(RCRec);
1786	if (!RC)
1787	return std::nullopt;
1788	return RC;
1789	}
1790
1791	std::optional<const CodeGenRegisterClass *>
1792	GlobalISelEmitter::inferRegClassFromPattern(const TreePatternNode &N) {
1793	if (N.isLeaf())
1794	return getRegClassFromLeaf(Leaf: N);
1795
1796	// We don't have a leaf node, so we have to try and infer something. Check
1797	// that we have an instruction that we can infer something from.
1798
1799	// Only handle things that produce at least one value (if multiple values,
1800	// just take the first one).
1801	if (N.getNumTypes() < 1)
1802	return std::nullopt;
1803	Record *OpRec = N.getOperator();
1804
1805	// We only want instructions.
1806	if (!OpRec->isSubClassOf(Name: "Instruction"))
1807	return std::nullopt;
1808
1809	// Don't want to try and infer things when there could potentially be more
1810	// than one candidate register class.
1811	auto &Inst = Target.getInstruction(InstRec: OpRec);
1812
1813	// Handle any special-case instructions which we can safely infer register
1814	// classes from.
1815	StringRef InstName = Inst.TheDef->getName();
1816	bool IsRegSequence = InstName == "REG_SEQUENCE";
1817	if (IsRegSequence || InstName == "COPY_TO_REGCLASS") {
1818	// If we have a COPY_TO_REGCLASS, then we need to handle it specially. It
1819	// has the desired register class as the first child.
1820	const TreePatternNode &RCChild = N.getChild(N: IsRegSequence ? 0 : 1);
1821	if (!RCChild.isLeaf())
1822	return std::nullopt;
1823	return getRegClassFromLeaf(Leaf: RCChild);
1824	}
1825	if (InstName == "INSERT_SUBREG") {
1826	const TreePatternNode &Child0 = N.getChild(N: 0);
1827	assert(Child0.getNumTypes() == 1 && "Unexpected number of types!");
1828	const TypeSetByHwMode &VTy = Child0.getExtType(ResNo: 0);
1829	return inferSuperRegisterClassForNode(Ty: VTy, SuperRegNode: Child0, SubRegIdxNode: N.getChild(N: 2));
1830	}
1831	if (InstName == "EXTRACT_SUBREG") {
1832	assert(N.getNumTypes() == 1 && "Unexpected number of types!");
1833	const TypeSetByHwMode &VTy = N.getExtType(ResNo: 0);
1834	return inferSuperRegisterClass(Ty: VTy, SubRegIdxNode: N.getChild(N: 1));
1835	}
1836
1837	// Handle destination record types that we can safely infer a register class
1838	// from.
1839	const auto &DstIOperand = Inst.Operands[0];
1840	Record *DstIOpRec = DstIOperand.Rec;
1841	if (DstIOpRec->isSubClassOf(Name: "RegisterOperand")) {
1842	DstIOpRec = DstIOpRec->getValueAsDef(FieldName: "RegClass");
1843	const CodeGenRegisterClass &RC = Target.getRegisterClass(R: DstIOpRec);
1844	return &RC;
1845	}
1846
1847	if (DstIOpRec->isSubClassOf(Name: "RegisterClass")) {
1848	const CodeGenRegisterClass &RC = Target.getRegisterClass(R: DstIOpRec);
1849	return &RC;
1850	}
1851
1852	return std::nullopt;
1853	}
1854
1855	std::optional<const CodeGenRegisterClass *>
1856	GlobalISelEmitter::inferSuperRegisterClass(
1857	const TypeSetByHwMode &Ty, const TreePatternNode &SubRegIdxNode) {
1858	// We need a ValueTypeByHwMode for getSuperRegForSubReg.
1859	if (!Ty.isValueTypeByHwMode(AllowEmpty: false))
1860	return std::nullopt;
1861	if (!SubRegIdxNode.isLeaf())
1862	return std::nullopt;
1863	DefInit *SubRegInit = dyn_cast<DefInit>(Val: SubRegIdxNode.getLeafValue());
1864	if (!SubRegInit)
1865	return std::nullopt;
1866	CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(SubRegInit->getDef());
1867
1868	// Use the information we found above to find a minimal register class which
1869	// supports the subregister and type we want.
1870	auto RC =
1871	Target.getSuperRegForSubReg(Ty: Ty.getValueTypeByHwMode(), RegBank&: CGRegs, SubIdx,
1872	/* MustBeAllocatable */ true);
1873	if (!RC)
1874	return std::nullopt;
1875	return *RC;
1876	}
1877
1878	std::optional<const CodeGenRegisterClass *>
1879	GlobalISelEmitter::inferSuperRegisterClassForNode(
1880	const TypeSetByHwMode &Ty, const TreePatternNode &SuperRegNode,
1881	const TreePatternNode &SubRegIdxNode) {
1882	// Check if we already have a defined register class for the super register
1883	// node. If we do, then we should preserve that rather than inferring anything
1884	// from the subregister index node. We can assume that whoever wrote the
1885	// pattern in the first place made sure that the super register and
1886	// subregister are compatible.
1887	if (std::optional<const CodeGenRegisterClass *> SuperRegisterClass =
1888	inferRegClassFromPattern(N: SuperRegNode))
1889	return *SuperRegisterClass;
1890	return inferSuperRegisterClass(Ty, SubRegIdxNode);
1891	}
1892
1893	std::optional<CodeGenSubRegIndex *> GlobalISelEmitter::inferSubRegIndexForNode(
1894	const TreePatternNode &SubRegIdxNode) {
1895	if (!SubRegIdxNode.isLeaf())
1896	return std::nullopt;
1897
1898	DefInit *SubRegInit = dyn_cast<DefInit>(Val: SubRegIdxNode.getLeafValue());
1899	if (!SubRegInit)
1900	return std::nullopt;
1901	return CGRegs.getSubRegIdx(SubRegInit->getDef());
1902	}
1903
1904	Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) {
1905	// Keep track of the matchers and actions to emit.
1906	int Score = P.getPatternComplexity(CGP);
1907	RuleMatcher M(P.getSrcRecord()->getLoc());
1908	RuleMatcherScores[M.getRuleID()] = Score;
1909	M.addAction<DebugCommentAction>(args: llvm::to_string(Value: P.getSrcPattern()) +
1910	" => " +
1911	llvm::to_string(Value: P.getDstPattern()));
1912
1913	SmallVector<Record *, 4> Predicates;
1914	P.getPredicateRecords(PredicateRecs&: Predicates);
1915	if (auto Error = importRulePredicates(M, Predicates))
1916	return std::move(Error);
1917
1918	if (!P.getHwModeFeatures().empty())
1919	M.addHwModeIdx(Idx: declareHwModeCheck(HwModeFeatures: P.getHwModeFeatures()));
1920
1921	// Next, analyze the pattern operators.
1922	TreePatternNode &Src = P.getSrcPattern();
1923	TreePatternNode &Dst = P.getDstPattern();
1924
1925	// If the root of either pattern isn't a simple operator, ignore it.
1926	if (auto Err = isTrivialOperatorNode(N: Dst))
1927	return failedImport(Reason: "Dst pattern root isn't a trivial operator (" +
1928	toString(E: std::move(Err)) + ")");
1929	if (auto Err = isTrivialOperatorNode(N: Src))
1930	return failedImport(Reason: "Src pattern root isn't a trivial operator (" +
1931	toString(E: std::move(Err)) + ")");
1932
1933	// The different predicates and matchers created during
1934	// addInstructionMatcher use the RuleMatcher M to set up their
1935	// instruction ID (InsnVarID) that are going to be used when
1936	// M is going to be emitted.
1937	// However, the code doing the emission still relies on the IDs
1938	// returned during that process by the RuleMatcher when issuing
1939	// the recordInsn opcodes.
1940	// Because of that:
1941	// 1. The order in which we created the predicates
1942	// and such must be the same as the order in which we emit them,
1943	// and
1944	// 2. We need to reset the generation of the IDs in M somewhere between
1945	// addInstructionMatcher and emit
1946	//
1947	// FIXME: Long term, we don't want to have to rely on this implicit
1948	// naming being the same. One possible solution would be to have
1949	// explicit operator for operation capture and reference those.
1950	// The plus side is that it would expose opportunities to share
1951	// the capture accross rules. The downside is that it would
1952	// introduce a dependency between predicates (captures must happen
1953	// before their first use.)
1954	InstructionMatcher &InsnMatcherTemp = M.addInstructionMatcher(SymbolicName: Src.getName());
1955	unsigned TempOpIdx = 0;
1956
1957	const auto SavedFlags = M.setGISelFlags(P.getSrcRecord());
1958
1959	auto InsnMatcherOrError =
1960	createAndImportSelDAGMatcher(Rule&: M, InsnMatcher&: InsnMatcherTemp, Src, TempOpIdx);
1961	if (auto Error = InsnMatcherOrError.takeError())
1962	return std::move(Error);
1963	InstructionMatcher &InsnMatcher = InsnMatcherOrError.get();
1964
1965	if (Dst.isLeaf()) {
1966	Record *RCDef = getInitValueAsRegClass(V: Dst.getLeafValue());
1967	if (RCDef) {
1968	const CodeGenRegisterClass &RC = Target.getRegisterClass(R: RCDef);
1969
1970	// We need to replace the def and all its uses with the specified
1971	// operand. However, we must also insert COPY's wherever needed.
1972	// For now, emit a copy and let the register allocator clean up.
1973	auto &DstI = Target.getInstruction(InstRec: RK.getDef(Name: "COPY"));
1974	const auto &DstIOperand = DstI.Operands[0];
1975
1976	OperandMatcher &OM0 = InsnMatcher.getOperand(OpIdx: 0);
1977	OM0.setSymbolicName(DstIOperand.Name);
1978	M.defineOperand(SymbolicName: OM0.getSymbolicName(), OM&: OM0);
1979	OM0.addPredicate<RegisterBankOperandMatcher>(args: RC);
1980
1981	auto &DstMIBuilder =
1982	M.addAction<BuildMIAction>(args: M.allocateOutputInsnID(), args: &DstI);
1983	DstMIBuilder.addRenderer<CopyRenderer>(args: DstIOperand.Name);
1984	DstMIBuilder.addRenderer<CopyRenderer>(args: Dst.getName());
1985	M.addAction<ConstrainOperandToRegClassAction>(args: 0, args: 0, args: RC);
1986
1987	// Erase the root.
1988	unsigned RootInsnID = M.getInsnVarID(InsnMatcher);
1989	M.addAction<EraseInstAction>(args&: RootInsnID);
1990
1991	// We're done with this pattern! It's eligible for GISel emission; return
1992	// it.
1993	++NumPatternImported;
1994	return std::move(M);
1995	}
1996
1997	return failedImport(Reason: "Dst pattern root isn't a known leaf");
1998	}
1999
2000	// Start with the defined operands (i.e., the results of the root operator).
2001	Record *DstOp = Dst.getOperator();
2002	if (!DstOp->isSubClassOf(Name: "Instruction"))
2003	return failedImport(Reason: "Pattern operator isn't an instruction");
2004
2005	auto &DstI = Target.getInstruction(InstRec: DstOp);
2006	StringRef DstIName = DstI.TheDef->getName();
2007
2008	unsigned DstNumDefs = DstI.Operands.NumDefs,
2009	SrcNumDefs = Src.getExtTypes().size();
2010	if (DstNumDefs < SrcNumDefs) {
2011	if (DstNumDefs != 0)
2012	return failedImport(Reason: "Src pattern result has more defs than dst MI (" +
2013	to_string(Value: SrcNumDefs) + " def(s) vs " +
2014	to_string(Value: DstNumDefs) + " def(s))");
2015
2016	bool FoundNoUsePred = false;
2017	for (const auto &Pred : InsnMatcher.predicates()) {
2018	if ((FoundNoUsePred = isa<NoUsePredicateMatcher>(Val: Pred.get())))
2019	break;
2020	}
2021	if (!FoundNoUsePred)
2022	return failedImport(Reason: "Src pattern result has " + to_string(Value: SrcNumDefs) +
2023	" def(s) without the HasNoUse predicate set to true "
2024	"but Dst MI has no def");
2025	}
2026
2027	// The root of the match also has constraints on the register bank so that it
2028	// matches the result instruction.
2029	unsigned OpIdx = 0;
2030	unsigned N = std::min(a: DstNumDefs, b: SrcNumDefs);
2031	for (unsigned I = 0; I < N; ++I) {
2032	const TypeSetByHwMode &VTy = Src.getExtType(ResNo: I);
2033
2034	const auto &DstIOperand = DstI.Operands[OpIdx];
2035	PointerUnion<Record *, const CodeGenRegisterClass *> MatchedRC =
2036	DstIOperand.Rec;
2037	if (DstIName == "COPY_TO_REGCLASS") {
2038	MatchedRC = getInitValueAsRegClass(V: Dst.getChild(N: 1).getLeafValue());
2039
2040	if (MatchedRC.isNull())
2041	return failedImport(
2042	Reason: "COPY_TO_REGCLASS operand #1 isn't a register class");
2043	} else if (DstIName == "REG_SEQUENCE") {
2044	MatchedRC = getInitValueAsRegClass(V: Dst.getChild(N: 0).getLeafValue());
2045	if (MatchedRC.isNull())
2046	return failedImport(Reason: "REG_SEQUENCE operand #0 isn't a register class");
2047	} else if (DstIName == "EXTRACT_SUBREG") {
2048	auto InferredClass = inferRegClassFromPattern(N: Dst.getChild(N: 0));
2049	if (!InferredClass)
2050	return failedImport(
2051	Reason: "Could not infer class for EXTRACT_SUBREG operand #0");
2052
2053	// We can assume that a subregister is in the same bank as it's super
2054	// register.
2055	MatchedRC = (*InferredClass)->getDef();
2056	} else if (DstIName == "INSERT_SUBREG") {
2057	auto MaybeSuperClass =
2058	inferSuperRegisterClassForNode(Ty: VTy, SuperRegNode: Dst.getChild(N: 0), SubRegIdxNode: Dst.getChild(N: 2));
2059	if (!MaybeSuperClass)
2060	return failedImport(
2061	Reason: "Cannot infer register class for INSERT_SUBREG operand #0");
2062	// Move to the next pattern here, because the register class we found
2063	// doesn't necessarily have a record associated with it. So, we can't
2064	// set DstIOpRec using this.
2065	MatchedRC = *MaybeSuperClass;
2066	} else if (DstIName == "SUBREG_TO_REG") {
2067	auto MaybeRegClass = inferSuperRegisterClass(Ty: VTy, SubRegIdxNode: Dst.getChild(N: 2));
2068	if (!MaybeRegClass)
2069	return failedImport(
2070	Reason: "Cannot infer register class for SUBREG_TO_REG operand #0");
2071	MatchedRC = *MaybeRegClass;
2072	} else if (MatchedRC.get<Record *>()->isSubClassOf(Name: "RegisterOperand"))
2073	MatchedRC = MatchedRC.get<Record *>()->getValueAsDef(FieldName: "RegClass");
2074	else if (!MatchedRC.get<Record *>()->isSubClassOf(Name: "RegisterClass"))
2075	return failedImport(Reason: "Dst MI def isn't a register class" + to_string(Value: Dst));
2076
2077	OperandMatcher &OM = InsnMatcher.getOperand(OpIdx);
2078	// The operand names declared in the DstI instruction are unrelated to
2079	// those used in pattern's source and destination DAGs, so mangle the
2080	// former to prevent implicitly adding unexpected
2081	// GIM_CheckIsSameOperand predicates by the defineOperand method.
2082	OM.setSymbolicName(getMangledRootDefName(DefOperandName: DstIOperand.Name));
2083	M.defineOperand(SymbolicName: OM.getSymbolicName(), OM);
2084	if (MatchedRC.is<Record *>())
2085	MatchedRC = &Target.getRegisterClass(R: MatchedRC.get<Record *>());
2086	OM.addPredicate<RegisterBankOperandMatcher>(
2087	args: *MatchedRC.get<const CodeGenRegisterClass *>());
2088	++OpIdx;
2089	}
2090
2091	auto DstMIBuilderOrError =
2092	createAndImportInstructionRenderer(M, InsnMatcher, Src, Dst);
2093	if (auto Error = DstMIBuilderOrError.takeError())
2094	return std::move(Error);
2095	BuildMIAction &DstMIBuilder = DstMIBuilderOrError.get();
2096
2097	// Render the implicit defs.
2098	// These are only added to the root of the result.
2099	if (auto Error = importImplicitDefRenderers(DstMIBuilder, ImplicitDefs: P.getDstRegs()))
2100	return std::move(Error);
2101
2102	DstMIBuilder.chooseInsnToMutate(Rule&: M);
2103
2104	// Constrain the registers to classes. This is normally derived from the
2105	// emitted instruction but a few instructions require special handling.
2106	if (DstIName == "COPY_TO_REGCLASS") {
2107	// COPY_TO_REGCLASS does not provide operand constraints itself but the
2108	// result is constrained to the class given by the second child.
2109	Record *DstIOpRec = getInitValueAsRegClass(V: Dst.getChild(N: 1).getLeafValue());
2110
2111	if (DstIOpRec == nullptr)
2112	return failedImport(Reason: "COPY_TO_REGCLASS operand #1 isn't a register class");
2113
2114	M.addAction<ConstrainOperandToRegClassAction>(
2115	args: 0, args: 0, args: Target.getRegisterClass(R: DstIOpRec));
2116	} else if (DstIName == "EXTRACT_SUBREG") {
2117	auto SuperClass = inferRegClassFromPattern(N: Dst.getChild(N: 0));
2118	if (!SuperClass)
2119	return failedImport(
2120	Reason: "Cannot infer register class from EXTRACT_SUBREG operand #0");
2121
2122	auto SubIdx = inferSubRegIndexForNode(SubRegIdxNode: Dst.getChild(N: 1));
2123	if (!SubIdx)
2124	return failedImport(Reason: "EXTRACT_SUBREG child #1 is not a subreg index");
2125
2126	// It would be nice to leave this constraint implicit but we're required
2127	// to pick a register class so constrain the result to a register class
2128	// that can hold the correct MVT.
2129	//
2130	// FIXME: This may introduce an extra copy if the chosen class doesn't
2131	// actually contain the subregisters.
2132	assert(Src.getExtTypes().size() == 1 &&
2133	"Expected Src of EXTRACT_SUBREG to have one result type");
2134
2135	const auto SrcRCDstRCPair =
2136	(*SuperClass)->getMatchingSubClassWithSubRegs(RegBank&: CGRegs, SubIdx: *SubIdx);
2137	if (!SrcRCDstRCPair) {
2138	return failedImport(Reason: "subreg index is incompatible "
2139	"with inferred reg class");
2140	}
2141
2142	assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass");
2143	M.addAction<ConstrainOperandToRegClassAction>(args: 0, args: 0,
2144	args&: *SrcRCDstRCPair->second);
2145	M.addAction<ConstrainOperandToRegClassAction>(args: 0, args: 1, args&: *SrcRCDstRCPair->first);
2146	} else if (DstIName == "INSERT_SUBREG") {
2147	assert(Src.getExtTypes().size() == 1 &&
2148	"Expected Src of INSERT_SUBREG to have one result type");
2149	// We need to constrain the destination, a super regsister source, and a
2150	// subregister source.
2151	auto SubClass = inferRegClassFromPattern(N: Dst.getChild(N: 1));
2152	if (!SubClass)
2153	return failedImport(
2154	Reason: "Cannot infer register class from INSERT_SUBREG operand #1");
2155	auto SuperClass = inferSuperRegisterClassForNode(
2156	Ty: Src.getExtType(ResNo: 0), SuperRegNode: Dst.getChild(N: 0), SubRegIdxNode: Dst.getChild(N: 2));
2157	if (!SuperClass)
2158	return failedImport(
2159	Reason: "Cannot infer register class for INSERT_SUBREG operand #0");
2160	M.addAction<ConstrainOperandToRegClassAction>(args: 0, args: 0, args: **SuperClass);
2161	M.addAction<ConstrainOperandToRegClassAction>(args: 0, args: 1, args: **SuperClass);
2162	M.addAction<ConstrainOperandToRegClassAction>(args: 0, args: 2, args: **SubClass);
2163	} else if (DstIName == "SUBREG_TO_REG") {
2164	// We need to constrain the destination and subregister source.
2165	assert(Src.getExtTypes().size() == 1 &&
2166	"Expected Src of SUBREG_TO_REG to have one result type");
2167
2168	// Attempt to infer the subregister source from the first child. If it has
2169	// an explicitly given register class, we'll use that. Otherwise, we will
2170	// fail.
2171	auto SubClass = inferRegClassFromPattern(N: Dst.getChild(N: 1));
2172	if (!SubClass)
2173	return failedImport(
2174	Reason: "Cannot infer register class from SUBREG_TO_REG child #1");
2175	// We don't have a child to look at that might have a super register node.
2176	auto SuperClass =
2177	inferSuperRegisterClass(Ty: Src.getExtType(ResNo: 0), SubRegIdxNode: Dst.getChild(N: 2));
2178	if (!SuperClass)
2179	return failedImport(
2180	Reason: "Cannot infer register class for SUBREG_TO_REG operand #0");
2181	M.addAction<ConstrainOperandToRegClassAction>(args: 0, args: 0, args: **SuperClass);
2182	M.addAction<ConstrainOperandToRegClassAction>(args: 0, args: 2, args: **SubClass);
2183	} else if (DstIName == "REG_SEQUENCE") {
2184	auto SuperClass = inferRegClassFromPattern(N: Dst.getChild(N: 0));
2185
2186	M.addAction<ConstrainOperandToRegClassAction>(args: 0, args: 0, args: **SuperClass);
2187
2188	unsigned Num = Dst.getNumChildren();
2189	for (unsigned I = 1; I != Num; I += 2) {
2190	TreePatternNode &SubRegChild = Dst.getChild(N: I + 1);
2191
2192	auto SubIdx = inferSubRegIndexForNode(SubRegIdxNode: SubRegChild);
2193	if (!SubIdx)
2194	return failedImport(Reason: "REG_SEQUENCE child is not a subreg index");
2195
2196	const auto SrcRCDstRCPair =
2197	(*SuperClass)->getMatchingSubClassWithSubRegs(RegBank&: CGRegs, SubIdx: *SubIdx);
2198
2199	M.addAction<ConstrainOperandToRegClassAction>(args: 0, args&: I,
2200	args&: *SrcRCDstRCPair->second);
2201	}
2202	} else {
2203	M.addAction<ConstrainOperandsToDefinitionAction>(args: 0);
2204	}
2205
2206	// Erase the root.
2207	unsigned RootInsnID = M.getInsnVarID(InsnMatcher);
2208	M.addAction<EraseInstAction>(args&: RootInsnID);
2209
2210	// We're done with this pattern! It's eligible for GISel emission; return it.
2211	++NumPatternImported;
2212	return std::move(M);
2213	}
2214
2215	MatchTable
2216	GlobalISelEmitter::buildMatchTable(MutableArrayRef<RuleMatcher> Rules,
2217	bool Optimize, bool WithCoverage) {
2218	std::vector<Matcher *> InputRules;
2219	for (Matcher &Rule : Rules)
2220	InputRules.push_back(x: &Rule);
2221
2222	if (!Optimize)
2223	return MatchTable::buildTable(Rules: InputRules, WithCoverage);
2224
2225	unsigned CurrentOrdering = 0;
2226	StringMap<unsigned> OpcodeOrder;
2227	for (RuleMatcher &Rule : Rules) {
2228	const StringRef Opcode = Rule.getOpcode();
2229	assert(!Opcode.empty() && "Didn't expect an undefined opcode");
2230	if (OpcodeOrder.count(Key: Opcode) == 0)
2231	OpcodeOrder[Opcode] = CurrentOrdering++;
2232	}
2233
2234	llvm::stable_sort(Range&: InputRules, C: [&OpcodeOrder](const Matcher *A,
2235	const Matcher *B) {
2236	auto *L = static_cast<const RuleMatcher *>(A);
2237	auto *R = static_cast<const RuleMatcher *>(B);
2238	return std::tuple(OpcodeOrder[L->getOpcode()], L->getNumOperands()) <
2239	std::tuple(OpcodeOrder[R->getOpcode()], R->getNumOperands());
2240	});
2241
2242	for (Matcher *Rule : InputRules)
2243	Rule->optimize();
2244
2245	std::vector<std::unique_ptr<Matcher>> MatcherStorage;
2246	std::vector<Matcher *> OptRules =
2247	optimizeRules<GroupMatcher>(Rules: InputRules, MatcherStorage);
2248
2249	for (Matcher *Rule : OptRules)
2250	Rule->optimize();
2251
2252	OptRules = optimizeRules<SwitchMatcher>(Rules: OptRules, MatcherStorage);
2253
2254	return MatchTable::buildTable(Rules: OptRules, WithCoverage);
2255	}
2256
2257	void GlobalISelEmitter::emitAdditionalImpl(raw_ostream &OS) {
2258	OS << "bool " << getClassName()
2259	<< "::selectImpl(MachineInstr &I, CodeGenCoverage "
2260	"&CoverageInfo) const {\n"
2261	<< " const PredicateBitset AvailableFeatures = "
2262	"getAvailableFeatures();\n"
2263	<< " MachineIRBuilder B(I);\n"
2264	<< " State.MIs.clear();\n"
2265	<< " State.MIs.push_back(&I);\n\n"
2266	<< " if (executeMatchTable(*this, State, ExecInfo, B"
2267	<< ", getMatchTable(), TII, MF->getRegInfo(), TRI, RBI, AvailableFeatures"
2268	<< ", &CoverageInfo)) {\n"
2269	<< " return true;\n"
2270	<< " }\n\n"
2271	<< " return false;\n"
2272	<< "}\n\n";
2273	}
2274
2275	void GlobalISelEmitter::emitMIPredicateFns(raw_ostream &OS) {
2276	std::vector<Record *> MatchedRecords;
2277	std::copy_if(first: AllPatFrags.begin(), last: AllPatFrags.end(),
2278	result: std::back_inserter(x&: MatchedRecords), pred: [&](Record *R) {
2279	return !R->getValueAsString(FieldName: "GISelPredicateCode").empty();
2280	});
2281	emitMIPredicateFnsImpl<Record *>(
2282	OS,
2283	AdditionalDecls: " const MachineFunction &MF = *MI.getParent()->getParent();\n"
2284	" const MachineRegisterInfo &MRI = MF.getRegInfo();\n"
2285	" const auto &Operands = State.RecordedOperands;\n"
2286	" (void)Operands;\n"
2287	" (void)MRI;",
2288	Predicates: ArrayRef<Record *>(MatchedRecords), GetPredEnumName: &getPatFragPredicateEnumName,
2289	GetPredCode: [&](Record *R) { return R->getValueAsString(FieldName: "GISelPredicateCode"); },
2290	Comment: "PatFrag predicates.");
2291	}
2292
2293	void GlobalISelEmitter::emitI64ImmPredicateFns(raw_ostream &OS) {
2294	std::vector<Record *> MatchedRecords;
2295	std::copy_if(first: AllPatFrags.begin(), last: AllPatFrags.end(),
2296	result: std::back_inserter(x&: MatchedRecords), pred: [&](Record *R) {
2297	bool Unset;
2298	return !R->getValueAsString(FieldName: "ImmediateCode").empty() &&
2299	!R->getValueAsBitOrUnset(FieldName: "IsAPFloat", Unset) &&
2300	!R->getValueAsBit(FieldName: "IsAPInt");
2301	});
2302	emitImmPredicateFnsImpl<Record *>(
2303	OS, TypeIdentifier: "I64", ArgType: "int64_t", Predicates: ArrayRef<Record *>(MatchedRecords),
2304	GetPredEnumName: &getPatFragPredicateEnumName,
2305	GetPredCode: [&](Record *R) { return R->getValueAsString(FieldName: "ImmediateCode"); },
2306	Comment: "PatFrag predicates.");
2307	}
2308
2309	void GlobalISelEmitter::emitAPFloatImmPredicateFns(raw_ostream &OS) {
2310	std::vector<Record *> MatchedRecords;
2311	std::copy_if(first: AllPatFrags.begin(), last: AllPatFrags.end(),
2312	result: std::back_inserter(x&: MatchedRecords), pred: [&](Record *R) {
2313	bool Unset;
2314	return !R->getValueAsString(FieldName: "ImmediateCode").empty() &&
2315	R->getValueAsBitOrUnset(FieldName: "IsAPFloat", Unset);
2316	});
2317	emitImmPredicateFnsImpl<Record *>(
2318	OS, TypeIdentifier: "APFloat", ArgType: "const APFloat &", Predicates: ArrayRef<Record *>(MatchedRecords),
2319	GetPredEnumName: &getPatFragPredicateEnumName,
2320	GetPredCode: [&](Record *R) { return R->getValueAsString(FieldName: "ImmediateCode"); },
2321	Comment: "PatFrag predicates.");
2322	}
2323
2324	void GlobalISelEmitter::emitAPIntImmPredicateFns(raw_ostream &OS) {
2325	std::vector<Record *> MatchedRecords;
2326	std::copy_if(first: AllPatFrags.begin(), last: AllPatFrags.end(),
2327	result: std::back_inserter(x&: MatchedRecords), pred: [&](Record *R) {
2328	return !R->getValueAsString(FieldName: "ImmediateCode").empty() &&
2329	R->getValueAsBit(FieldName: "IsAPInt");
2330	});
2331	emitImmPredicateFnsImpl<Record *>(
2332	OS, TypeIdentifier: "APInt", ArgType: "const APInt &", Predicates: ArrayRef<Record *>(MatchedRecords),
2333	GetPredEnumName: &getPatFragPredicateEnumName,
2334	GetPredCode: [&](Record *R) { return R->getValueAsString(FieldName: "ImmediateCode"); },
2335	Comment: "PatFrag predicates.");
2336	}
2337
2338	void GlobalISelEmitter::emitTestSimplePredicate(raw_ostream &OS) {
2339	OS << "bool " << getClassName() << "::testSimplePredicate(unsigned) const {\n"
2340	<< " llvm_unreachable(\"" + getClassName() +
2341	" does not support simple predicates!\");\n"
2342	<< " return false;\n"
2343	<< "}\n";
2344	}
2345
2346	void GlobalISelEmitter::emitRunCustomAction(raw_ostream &OS) {
2347	OS << "void " << getClassName()
2348	<< "::runCustomAction(unsigned, const MatcherState&, NewMIVector &) const "
2349	"{\n"
2350	<< " llvm_unreachable(\"" + getClassName() +
2351	" does not support custom C++ actions!\");\n"
2352	<< "}\n";
2353	}
2354
2355	void GlobalISelEmitter::postProcessRule(RuleMatcher &M) {
2356	SmallPtrSet<Record *, 16> UsedRegs;
2357
2358	// TODO: deal with subregs?
2359	for (auto &A : M.actions()) {
2360	auto *MI = dyn_cast<BuildMIAction>(Val: A.get());
2361	if (!MI)
2362	continue;
2363
2364	for (auto *Use : MI->getCGI()->ImplicitUses)
2365	UsedRegs.insert(Ptr: Use);
2366	}
2367
2368	for (auto &A : M.actions()) {
2369	auto *MI = dyn_cast<BuildMIAction>(Val: A.get());
2370	if (!MI)
2371	continue;
2372
2373	for (auto *Def : MI->getCGI()->ImplicitDefs) {
2374	if (!UsedRegs.contains(Ptr: Def))
2375	MI->setDeadImplicitDef(Def);
2376	}
2377	}
2378	}
2379
2380	void GlobalISelEmitter::run(raw_ostream &OS) {
2381	if (!UseCoverageFile.empty()) {
2382	RuleCoverage = CodeGenCoverage();
2383	auto RuleCoverageBufOrErr = MemoryBuffer::getFile(Filename: UseCoverageFile);
2384	if (!RuleCoverageBufOrErr) {
2385	PrintWarning(WarningLoc: SMLoc(), Msg: "Missing rule coverage data");
2386	RuleCoverage = std::nullopt;
2387	} else {
2388	if (!RuleCoverage->parse(Buffer&: *RuleCoverageBufOrErr.get(), BackendName: Target.getName())) {
2389	PrintWarning(WarningLoc: SMLoc(), Msg: "Ignoring invalid or missing rule coverage data");
2390	RuleCoverage = std::nullopt;
2391	}
2392	}
2393	}
2394
2395	// Track the run-time opcode values
2396	gatherOpcodeValues();
2397	// Track the run-time LLT ID values
2398	gatherTypeIDValues();
2399
2400	// Track the GINodeEquiv definitions.
2401	gatherNodeEquivs();
2402
2403	AllPatFrags = RK.getAllDerivedDefinitions(ClassName: "PatFrags");
2404
2405	emitSourceFileHeader(
2406	Desc: ("Global Instruction Selector for the " + Target.getName() + " target")
2407	.str(),
2408	OS);
2409	std::vector<RuleMatcher> Rules;
2410	// Look through the SelectionDAG patterns we found, possibly emitting some.
2411	for (const PatternToMatch &Pat : CGP.ptms()) {
2412	++NumPatternTotal;
2413
2414	auto MatcherOrErr = runOnPattern(P: Pat);
2415
2416	// The pattern analysis can fail, indicating an unsupported pattern.
2417	// Report that if we've been asked to do so.
2418	if (auto Err = MatcherOrErr.takeError()) {
2419	if (WarnOnSkippedPatterns) {
2420	PrintWarning(WarningLoc: Pat.getSrcRecord()->getLoc(),
2421	Msg: "Skipped pattern: " + toString(E: std::move(Err)));
2422	} else {
2423	consumeError(Err: std::move(Err));
2424	}
2425	++NumPatternImportsSkipped;
2426	continue;
2427	}
2428
2429	if (RuleCoverage) {
2430	if (RuleCoverage->isCovered(RuleID: MatcherOrErr->getRuleID()))
2431	++NumPatternsTested;
2432	else
2433	PrintWarning(WarningLoc: Pat.getSrcRecord()->getLoc(),
2434	Msg: "Pattern is not covered by a test");
2435	}
2436	Rules.push_back(x: std::move(MatcherOrErr.get()));
2437	postProcessRule(M&: Rules.back());
2438	}
2439
2440	// Comparison function to order records by name.
2441	auto orderByName = [](const Record *A, const Record *B) {
2442	return A->getName() < B->getName();
2443	};
2444
2445	std::vector<Record *> ComplexPredicates =
2446	RK.getAllDerivedDefinitions(ClassName: "GIComplexOperandMatcher");
2447	llvm::sort(C&: ComplexPredicates, Comp: orderByName);
2448
2449	std::vector<StringRef> CustomRendererFns;
2450	transform(Range: RK.getAllDerivedDefinitions(ClassName: "GICustomOperandRenderer"),
2451	d_first: std::back_inserter(x&: CustomRendererFns), F: [](const auto &Record) {
2452	return Record->getValueAsString("RendererFn");
2453	});
2454	// Sort and remove duplicates to get a list of unique renderer functions, in
2455	// case some were mentioned more than once.
2456	llvm::sort(C&: CustomRendererFns);
2457	CustomRendererFns.erase(
2458	first: std::unique(first: CustomRendererFns.begin(), last: CustomRendererFns.end()),
2459	last: CustomRendererFns.end());
2460
2461	// Create a table containing the LLT objects needed by the matcher and an enum
2462	// for the matcher to reference them with.
2463	std::vector<LLTCodeGen> TypeObjects;
2464	append_range(C&: TypeObjects, R&: KnownTypes);
2465	llvm::sort(C&: TypeObjects);
2466
2467	// Sort rules.
2468	llvm::stable_sort(Range&: Rules, C: [&](const RuleMatcher &A, const RuleMatcher &B) {
2469	int ScoreA = RuleMatcherScores[A.getRuleID()];
2470	int ScoreB = RuleMatcherScores[B.getRuleID()];
2471	if (ScoreA > ScoreB)
2472	return true;
2473	if (ScoreB > ScoreA)
2474	return false;
2475	if (A.isHigherPriorityThan(B)) {
2476	assert(!B.isHigherPriorityThan(A) && "Cannot be more important "
2477	"and less important at "
2478	"the same time");
2479	return true;
2480	}
2481	return false;
2482	});
2483
2484	unsigned MaxTemporaries = 0;
2485	for (const auto &Rule : Rules)
2486	MaxTemporaries = std::max(a: MaxTemporaries, b: Rule.countRendererFns());
2487
2488	// Build match table
2489	const MatchTable Table =
2490	buildMatchTable(Rules, Optimize: OptimizeMatchTable, WithCoverage: GenerateCoverage);
2491
2492	emitPredicateBitset(OS, IfDefName: "GET_GLOBALISEL_PREDICATE_BITSET");
2493	emitTemporariesDecl(OS, IfDefName: "GET_GLOBALISEL_TEMPORARIES_DECL");
2494	emitTemporariesInit(OS, MaxTemporaries, IfDefName: "GET_GLOBALISEL_TEMPORARIES_INIT");
2495	emitExecutorImpl(OS, Table, TypeObjects, Rules, ComplexOperandMatchers: ComplexPredicates,
2496	CustomOperandRenderers: CustomRendererFns, IfDefName: "GET_GLOBALISEL_IMPL");
2497	emitPredicatesDecl(OS, IfDefName: "GET_GLOBALISEL_PREDICATES_DECL");
2498	emitPredicatesInit(OS, IfDefName: "GET_GLOBALISEL_PREDICATES_INIT");
2499	}
2500
2501	void GlobalISelEmitter::declareSubtargetFeature(Record *Predicate) {
2502	SubtargetFeatures.try_emplace(k: Predicate, args&: Predicate, args: SubtargetFeatures.size());
2503	}
2504
2505	unsigned GlobalISelEmitter::declareHwModeCheck(StringRef HwModeFeatures) {
2506	return HwModes.emplace(args: HwModeFeatures.str(), args: HwModes.size()).first->second;
2507	}
2508
2509	} // end anonymous namespace
2510
2511	//===----------------------------------------------------------------------===//
2512
2513	static TableGen::Emitter::OptClass<GlobalISelEmitter>
2514	X("gen-global-isel", "Generate GlobalISel selector");
2515