1	//===- GlobalISelCombinerMatchTableEmitter.cpp - --------------------------===//
2	//
3	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4	// See https://llvm.org/LICENSE.txt for license information.
5	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6	//
7	//===----------------------------------------------------------------------===//
8	//
9	/// \file Generate a combiner implementation for GlobalISel from a declarative
10	/// syntax using GlobalISelMatchTable.
11	///
12	/// Usually, TableGen backends use "assert is an error" as a means to report
13	/// invalid input. They try to diagnose common case but don't try very hard and
14	/// crashes can be common. This backend aims to behave closer to how a language
15	/// compiler frontend would behave: we try extra hard to diagnose invalid inputs
16	/// early, and any crash should be considered a bug (= a feature or diagnostic
17	/// is missing).
18	///
19	/// While this can make the backend a bit more complex than it needs to be, it
20	/// pays off because MIR patterns can get complicated. Giving useful error
21	/// messages to combine writers can help boost their productivity.
22	///
23	/// As with anything, a good balance has to be found. We also don't want to
24	/// write hundreds of lines of code to detect edge cases. In practice, crashing
25	/// very occasionally, or giving poor errors in some rare instances, is fine.
26	///
27	//===----------------------------------------------------------------------===//
28
29	#include "Basic/CodeGenIntrinsics.h"
30	#include "Common/CodeGenInstruction.h"
31	#include "Common/CodeGenTarget.h"
32	#include "Common/GlobalISel/CXXPredicates.h"
33	#include "Common/GlobalISel/CodeExpander.h"
34	#include "Common/GlobalISel/CodeExpansions.h"
35	#include "Common/GlobalISel/CombinerUtils.h"
36	#include "Common/GlobalISel/GlobalISelMatchTable.h"
37	#include "Common/GlobalISel/GlobalISelMatchTableExecutorEmitter.h"
38	#include "Common/GlobalISel/MatchDataInfo.h"
39	#include "Common/GlobalISel/PatternParser.h"
40	#include "Common/GlobalISel/Patterns.h"
41	#include "Common/SubtargetFeatureInfo.h"
42	#include "llvm/ADT/APInt.h"
43	#include "llvm/ADT/EquivalenceClasses.h"
44	#include "llvm/ADT/Hashing.h"
45	#include "llvm/ADT/MapVector.h"
46	#include "llvm/ADT/SetVector.h"
47	#include "llvm/ADT/Statistic.h"
48	#include "llvm/ADT/StringSet.h"
49	#include "llvm/Support/CommandLine.h"
50	#include "llvm/Support/Debug.h"
51	#include "llvm/Support/PrettyStackTrace.h"
52	#include "llvm/Support/ScopedPrinter.h"
53	#include "llvm/TableGen/Error.h"
54	#include "llvm/TableGen/Record.h"
55	#include "llvm/TableGen/StringMatcher.h"
56	#include "llvm/TableGen/TableGenBackend.h"
57	#include <cstdint>
58
59	using namespace llvm;
60	using namespace llvm::gi;
61
62	#define DEBUG_TYPE "gicombiner-emitter"
63
64	namespace {
65	cl::OptionCategory
66	GICombinerEmitterCat("Options for -gen-global-isel-combiner");
67	cl::opt<bool> StopAfterParse(
68	"gicombiner-stop-after-parse",
69	cl::desc("Stop processing after parsing rules and dump state"),
70	cl::cat(GICombinerEmitterCat));
71	cl::list<std::string>
72	SelectedCombiners("combiners", cl::desc("Emit the specified combiners"),
73	cl::cat(GICombinerEmitterCat), cl::CommaSeparated);
74	cl::opt<bool> DebugCXXPreds(
75	"gicombiner-debug-cxxpreds",
76	cl::desc("Add Contextual/Debug comments to all C++ predicates"),
77	cl::cat(GICombinerEmitterCat));
78	cl::opt<bool> DebugTypeInfer("gicombiner-debug-typeinfer",
79	cl::desc("Print type inference debug logs"),
80	cl::cat(GICombinerEmitterCat));
81
82	constexpr StringLiteral CXXApplyPrefix = "GICXXCustomAction_CombineApply";
83	constexpr StringLiteral CXXPredPrefix = "GICXXPred_MI_Predicate_";
84
85	//===- CodeExpansions Helpers --------------------------------------------===//
86
87	void declareInstExpansion(CodeExpansions &CE, const InstructionMatcher &IM,
88	StringRef Name) {
89	CE.declare(Name, Expansion: "State.MIs[" + to_string(Value: IM.getInsnVarID()) + "]");
90	}
91
92	void declareInstExpansion(CodeExpansions &CE, const BuildMIAction &A,
93	StringRef Name) {
94	// Note: we use redeclare here because this may overwrite a matcher inst
95	// expansion.
96	CE.redeclare(Name, Expansion: "OutMIs[" + to_string(Value: A.getInsnID()) + "]");
97	}
98
99	void declareOperandExpansion(CodeExpansions &CE, const OperandMatcher &OM,
100	StringRef Name) {
101	CE.declare(Name, Expansion: "State.MIs[" + to_string(Value: OM.getInsnVarID()) +
102	"]->getOperand(" + to_string(Value: OM.getOpIdx()) + ")");
103	}
104
105	void declareTempRegExpansion(CodeExpansions &CE, unsigned TempRegID,
106	StringRef Name) {
107	CE.declare(Name, Expansion: "State.TempRegisters[" + to_string(Value: TempRegID) + "]");
108	}
109
110	//===- Misc. Helpers -----------------------------------------------------===//
111
112	template <typename Container> auto keys(Container &&C) {
113	return map_range(C, [](auto &Entry) -> auto & { return Entry.first; });
114	}
115
116	template <typename Container> auto values(Container &&C) {
117	return map_range(C, [](auto &Entry) -> auto & { return Entry.second; });
118	}
119
120	std::string getIsEnabledPredicateEnumName(unsigned CombinerRuleID) {
121	return "GICXXPred_Simple_IsRule" + to_string(Value: CombinerRuleID) + "Enabled";
122	}
123
124	//===- MatchTable Helpers ------------------------------------------------===//
125
126	LLTCodeGen getLLTCodeGen(const PatternType &PT) {
127	return *MVTToLLT(SVT: getValueType(Rec: PT.getLLTRecord()));
128	}
129
130	LLTCodeGenOrTempType getLLTCodeGenOrTempType(const PatternType &PT,
131	RuleMatcher &RM) {
132	assert(!PT.isNone());
133
134	if (PT.isLLT())
135	return getLLTCodeGen(PT);
136
137	assert(PT.isTypeOf());
138	auto &OM = RM.getOperandMatcher(Name: PT.getTypeOfOpName());
139	return OM.getTempTypeIdx(Rule&: RM);
140	}
141
142	//===- PrettyStackTrace Helpers ------------------------------------------===//
143
144	class PrettyStackTraceParse : public PrettyStackTraceEntry {
145	const Record &Def;
146
147	public:
148	PrettyStackTraceParse(const Record &Def) : Def(Def) {}
149
150	void print(raw_ostream &OS) const override {
151	if (Def.isSubClassOf(Name: "GICombineRule"))
152	OS << "Parsing GICombineRule '" << Def.getName() << "'";
153	else if (Def.isSubClassOf(Name: PatFrag::ClassName))
154	OS << "Parsing " << PatFrag::ClassName << " '" << Def.getName() << "'";
155	else
156	OS << "Parsing '" << Def.getName() << "'";
157	OS << '\n';
158	}
159	};
160
161	class PrettyStackTraceEmit : public PrettyStackTraceEntry {
162	const Record &Def;
163	const Pattern *Pat = nullptr;
164
165	public:
166	PrettyStackTraceEmit(const Record &Def, const Pattern *Pat = nullptr)
167	: Def(Def), Pat(Pat) {}
168
169	void print(raw_ostream &OS) const override {
170	if (Def.isSubClassOf(Name: "GICombineRule"))
171	OS << "Emitting GICombineRule '" << Def.getName() << "'";
172	else if (Def.isSubClassOf(Name: PatFrag::ClassName))
173	OS << "Emitting " << PatFrag::ClassName << " '" << Def.getName() << "'";
174	else
175	OS << "Emitting '" << Def.getName() << "'";
176
177	if (Pat)
178	OS << " [" << Pat->getKindName() << " '" << Pat->getName() << "']";
179	OS << '\n';
180	}
181	};
182
183	//===- CombineRuleOperandTypeChecker --------------------------------------===//
184
185	/// This is a wrapper around OperandTypeChecker specialized for Combiner Rules.
186	/// On top of doing the same things as OperandTypeChecker, this also attempts to
187	/// infer as many types as possible for temporary register defs & immediates in
188	/// apply patterns.
189	///
190	/// The inference is trivial and leverages the MCOI OperandTypes encoded in
191	/// CodeGenInstructions to infer types across patterns in a CombineRule. It's
192	/// thus very limited and only supports CodeGenInstructions (but that's the main
193	/// use case so it's fine).
194	///
195	/// We only try to infer untyped operands in apply patterns when they're temp
196	/// reg defs, or immediates. Inference always outputs a `TypeOf<$x>` where $x is
197	/// a named operand from a match pattern.
198	class CombineRuleOperandTypeChecker : private OperandTypeChecker {
199	public:
200	CombineRuleOperandTypeChecker(const Record &RuleDef,
201	const OperandTable &MatchOpTable)
202	: OperandTypeChecker(RuleDef.getLoc()), RuleDef(RuleDef),
203	MatchOpTable(MatchOpTable) {}
204
205	/// Records and checks a 'match' pattern.
206	bool processMatchPattern(InstructionPattern &P);
207
208	/// Records and checks an 'apply' pattern.
209	bool processApplyPattern(InstructionPattern &P);
210
211	/// Propagates types, then perform type inference and do a second round of
212	/// propagation in the apply patterns only if any types were inferred.
213	void propagateAndInferTypes();
214
215	private:
216	/// TypeEquivalenceClasses are groups of operands of an instruction that share
217	/// a common type.
218	///
219	/// e.g. [[a, b], [c, d]] means a and b have the same type, and c and
220	/// d have the same type too. b/c and a/d don't have to have the same type,
221	/// though.
222	using TypeEquivalenceClasses = EquivalenceClasses<StringRef>;
223
224	/// \returns true for `OPERAND_GENERIC_` 0 through 5.
225	/// These are the MCOI types that can be registers. The other MCOI types are
226	/// either immediates, or fancier operands used only post-ISel, so we don't
227	/// care about them for combiners.
228	static bool canMCOIOperandTypeBeARegister(StringRef MCOIType) {
229	// Assume OPERAND_GENERIC_0 through 5 can be registers. The other MCOI
230	// OperandTypes are either never used in gMIR, or not relevant (e.g.
231	// OPERAND_GENERIC_IMM, which is definitely never a register).
232	return MCOIType.drop_back(N: 1).ends_with(Suffix: "OPERAND_GENERIC_");
233	}
234
235	/// Finds the "MCOI::"" operand types for each operand of \p CGP.
236	///
237	/// This is a bit trickier than it looks because we need to handle variadic
238	/// in/outs.
239	///
240	/// e.g. for
241	/// (G_BUILD_VECTOR $vec, $x, $y) ->
242	/// [MCOI::OPERAND_GENERIC_0, MCOI::OPERAND_GENERIC_1,
243	/// MCOI::OPERAND_GENERIC_1]
244	///
245	/// For unknown types (which can happen in variadics where varargs types are
246	/// inconsistent), a unique name is given, e.g. "unknown_type_0".
247	static std::vector<std::string>
248	getMCOIOperandTypes(const CodeGenInstructionPattern &CGP);
249
250	/// Adds the TypeEquivalenceClasses for \p P in \p OutTECs.
251	void getInstEqClasses(const InstructionPattern &P,
252	TypeEquivalenceClasses &OutTECs) const;
253
254	/// Calls `getInstEqClasses` on all patterns of the rule to produce the whole
255	/// rule's TypeEquivalenceClasses.
256	TypeEquivalenceClasses getRuleEqClasses() const;
257
258	/// Tries to infer the type of the \p ImmOpIdx -th operand of \p IP using \p
259	/// TECs.
260	///
261	/// This is achieved by trying to find a named operand in \p IP that shares
262	/// the same type as \p ImmOpIdx, and using \ref inferNamedOperandType on that
263	/// operand instead.
264	///
265	/// \returns the inferred type or an empty PatternType if inference didn't
266	/// succeed.
267	PatternType inferImmediateType(const InstructionPattern &IP,
268	unsigned ImmOpIdx,
269	const TypeEquivalenceClasses &TECs) const;
270
271	/// Looks inside \p TECs to infer \p OpName's type.
272	///
273	/// \returns the inferred type or an empty PatternType if inference didn't
274	/// succeed.
275	PatternType inferNamedOperandType(const InstructionPattern &IP,
276	StringRef OpName,
277	const TypeEquivalenceClasses &TECs,
278	bool AllowSelf = false) const;
279
280	const Record &RuleDef;
281	SmallVector<InstructionPattern *, 8> MatchPats;
282	SmallVector<InstructionPattern *, 8> ApplyPats;
283
284	const OperandTable &MatchOpTable;
285	};
286
287	bool CombineRuleOperandTypeChecker::processMatchPattern(InstructionPattern &P) {
288	MatchPats.push_back(Elt: &P);
289	return check(P, /*CheckTypeOf*/ VerifyTypeOfOperand: [](const auto &) {
290	// GITypeOf in 'match' is currently always rejected by the
291	// CombineRuleBuilder after inference is done.
292	return true;
293	});
294	}
295
296	bool CombineRuleOperandTypeChecker::processApplyPattern(InstructionPattern &P) {
297	ApplyPats.push_back(Elt: &P);
298	return check(P, /*CheckTypeOf*/ VerifyTypeOfOperand: [&](const PatternType &Ty) {
299	// GITypeOf<"$x"> can only be used if "$x" is a matched operand.
300	const auto OpName = Ty.getTypeOfOpName();
301	if (MatchOpTable.lookup(OpName).Found)
302	return true;
303
304	PrintError(ErrorLoc: RuleDef.getLoc(), Msg: "'" + OpName + "' ('" + Ty.str() +
305	"') does not refer to a matched operand!");
306	return false;
307	});
308	}
309
310	void CombineRuleOperandTypeChecker::propagateAndInferTypes() {
311	/// First step here is to propagate types using the OperandTypeChecker. That
312	/// way we ensure all uses of a given register have consistent types.
313	propagateTypes();
314
315	/// Build the TypeEquivalenceClasses for the whole rule.
316	const TypeEquivalenceClasses TECs = getRuleEqClasses();
317
318	/// Look at the apply patterns and find operands that need to be
319	/// inferred. We then try to find an equivalence class that they're a part of
320	/// and select the best operand to use for the `GITypeOf` type. We prioritize
321	/// defs of matched instructions because those are guaranteed to be registers.
322	bool InferredAny = false;
323	for (auto *Pat : ApplyPats) {
324	for (unsigned K = 0; K < Pat->operands_size(); ++K) {
325	auto &Op = Pat->getOperand(K);
326
327	// We only want to take a look at untyped defs or immediates.
328	if ((!Op.isDef() && !Op.hasImmValue()) || Op.getType())
329	continue;
330
331	// Infer defs & named immediates.
332	if (Op.isDef() || Op.isNamedImmediate()) {
333	// Check it's not a redefinition of a matched operand.
334	// In such cases, inference is not necessary because we just copy
335	// operands and don't create temporary registers.
336	if (MatchOpTable.lookup(OpName: Op.getOperandName()).Found)
337	continue;
338
339	// Inference is needed here, so try to do it.
340	if (PatternType Ty =
341	inferNamedOperandType(IP: *Pat, OpName: Op.getOperandName(), TECs)) {
342	if (DebugTypeInfer)
343	errs() << "INFER: " << Op.describe() << " -> " << Ty.str() << '\n';
344	Op.setType(Ty);
345	InferredAny = true;
346	}
347
348	continue;
349	}
350
351	// Infer immediates
352	if (Op.hasImmValue()) {
353	if (PatternType Ty = inferImmediateType(IP: *Pat, ImmOpIdx: K, TECs)) {
354	if (DebugTypeInfer)
355	errs() << "INFER: " << Op.describe() << " -> " << Ty.str() << '\n';
356	Op.setType(Ty);
357	InferredAny = true;
358	}
359	continue;
360	}
361	}
362	}
363
364	// If we've inferred any types, we want to propagate them across the apply
365	// patterns. Type inference only adds GITypeOf types that point to Matched
366	// operands, so we definitely don't want to propagate types into the match
367	// patterns as well, otherwise bad things happen.
368	if (InferredAny) {
369	OperandTypeChecker OTC(RuleDef.getLoc());
370	for (auto *Pat : ApplyPats) {
371	if (!OTC.check(P&: *Pat, VerifyTypeOfOperand: [&](const auto &) { return true; }))
372	PrintFatalError(ErrorLoc: RuleDef.getLoc(),
373	Msg: "OperandTypeChecker unexpectedly failed on '" +
374	Pat->getName() + "' during Type Inference");
375	}
376	OTC.propagateTypes();
377
378	if (DebugTypeInfer) {
379	errs() << "Apply patterns for rule " << RuleDef.getName()
380	<< " after inference:\n";
381	for (auto *Pat : ApplyPats) {
382	errs() << " ";
383	Pat->print(OS&: errs(), /*PrintName*/ true);
384	errs() << '\n';
385	}
386	errs() << '\n';
387	}
388	}
389	}
390
391	PatternType CombineRuleOperandTypeChecker::inferImmediateType(
392	const InstructionPattern &IP, unsigned ImmOpIdx,
393	const TypeEquivalenceClasses &TECs) const {
394	// We can only infer CGPs (except intrinsics).
395	const auto *CGP = dyn_cast<CodeGenInstructionPattern>(Val: &IP);
396	if (!CGP || CGP->isIntrinsic())
397	return {};
398
399	// For CGPs, we try to infer immediates by trying to infer another named
400	// operand that shares its type.
401	//
402	// e.g.
403	// Pattern: G_BUILD_VECTOR $x, $y, 0
404	// MCOIs: [MCOI::OPERAND_GENERIC_0, MCOI::OPERAND_GENERIC_1,
405	// MCOI::OPERAND_GENERIC_1]
406	// $y has the same type as 0, so we can infer $y and get the type 0 should
407	// have.
408
409	// We infer immediates by looking for a named operand that shares the same
410	// MCOI type.
411	const auto MCOITypes = getMCOIOperandTypes(CGP: *CGP);
412	StringRef ImmOpTy = MCOITypes[ImmOpIdx];
413
414	for (const auto &[Idx, Ty] : enumerate(First: MCOITypes)) {
415	if (Idx != ImmOpIdx && Ty == ImmOpTy) {
416	const auto &Op = IP.getOperand(K: Idx);
417	if (!Op.isNamedOperand())
418	continue;
419
420	// Named operand with the same name, try to infer that.
421	if (PatternType InferTy = inferNamedOperandType(IP, OpName: Op.getOperandName(),
422	TECs, /*AllowSelf=*/true))
423	return InferTy;
424	}
425	}
426
427	return {};
428	}
429
430	PatternType CombineRuleOperandTypeChecker::inferNamedOperandType(
431	const InstructionPattern &IP, StringRef OpName,
432	const TypeEquivalenceClasses &TECs, bool AllowSelf) const {
433	// This is the simplest possible case, we just need to find a TEC that
434	// contains OpName. Look at all operands in equivalence class and try to
435	// find a suitable one. If `AllowSelf` is true, the operand itself is also
436	// considered suitable.
437
438	// Check for a def of a matched pattern. This is guaranteed to always
439	// be a register so we can blindly use that.
440	StringRef GoodOpName;
441	for (auto It = TECs.findLeader(V: OpName); It != TECs.member_end(); ++It) {
442	if (!AllowSelf && *It == OpName)
443	continue;
444
445	const auto LookupRes = MatchOpTable.lookup(OpName: *It);
446	if (LookupRes.Def) // Favor defs
447	return PatternType::getTypeOf(OpName: *It);
448
449	// Otherwise just save this in case we don't find any def.
450	if (GoodOpName.empty() && LookupRes.Found)
451	GoodOpName = *It;
452	}
453
454	if (!GoodOpName.empty())
455	return PatternType::getTypeOf(OpName: GoodOpName);
456
457	// No good operand found, give up.
458	return {};
459	}
460
461	std::vector<std::string> CombineRuleOperandTypeChecker::getMCOIOperandTypes(
462	const CodeGenInstructionPattern &CGP) {
463	// FIXME?: Should we cache this? We call it twice when inferring immediates.
464
465	static unsigned UnknownTypeIdx = 0;
466
467	std::vector<std::string> OpTypes;
468	auto &CGI = CGP.getInst();
469	Record *VarArgsTy = CGI.TheDef->isSubClassOf(Name: "GenericInstruction")
470	? CGI.TheDef->getValueAsOptionalDef(FieldName: "variadicOpsType")
471	: nullptr;
472	std::string VarArgsTyName =
473	VarArgsTy ? ("MCOI::" + VarArgsTy->getValueAsString(FieldName: "OperandType")).str()
474	: ("unknown_type_" + Twine(UnknownTypeIdx++)).str();
475
476	// First, handle defs.
477	for (unsigned K = 0; K < CGI.Operands.NumDefs; ++K)
478	OpTypes.push_back(x: CGI.Operands[K].OperandType);
479
480	// Then, handle variadic defs if there are any.
481	if (CGP.hasVariadicDefs()) {
482	for (unsigned K = CGI.Operands.NumDefs; K < CGP.getNumInstDefs(); ++K)
483	OpTypes.push_back(x: VarArgsTyName);
484	}
485
486	// If we had variadic defs, the op idx in the pattern won't match the op idx
487	// in the CGI anymore.
488	int CGIOpOffset = int(CGI.Operands.NumDefs) - CGP.getNumInstDefs();
489	assert(CGP.hasVariadicDefs() ? (CGIOpOffset <= 0) : (CGIOpOffset == 0));
490
491	// Handle all remaining use operands, including variadic ones.
492	for (unsigned K = CGP.getNumInstDefs(); K < CGP.getNumInstOperands(); ++K) {
493	unsigned CGIOpIdx = K + CGIOpOffset;
494	if (CGIOpIdx >= CGI.Operands.size()) {
495	assert(CGP.isVariadic());
496	OpTypes.push_back(x: VarArgsTyName);
497	} else {
498	OpTypes.push_back(x: CGI.Operands[CGIOpIdx].OperandType);
499	}
500	}
501
502	assert(OpTypes.size() == CGP.operands_size());
503	return OpTypes;
504	}
505
506	void CombineRuleOperandTypeChecker::getInstEqClasses(
507	const InstructionPattern &P, TypeEquivalenceClasses &OutTECs) const {
508	// Determine the TypeEquivalenceClasses by:
509	// - Getting the MCOI Operand Types.
510	// - Creating a Map of MCOI Type -> [Operand Indexes]
511	// - Iterating over the map, filtering types we don't like, and just adding
512	// the array of Operand Indexes to \p OutTECs.
513
514	// We can only do this on CodeGenInstructions that aren't intrinsics. Other
515	// InstructionPatterns have no type inference information associated with
516	// them.
517	// TODO: We could try to extract some info from CodeGenIntrinsic to
518	// guide inference.
519
520	// TODO: Could we add some inference information to builtins at least? e.g.
521	// ReplaceReg should always replace with a reg of the same type, for instance.
522	// Though, those patterns are often used alone so it might not be worth the
523	// trouble to infer their types.
524	auto *CGP = dyn_cast<CodeGenInstructionPattern>(Val: &P);
525	if (!CGP || CGP->isIntrinsic())
526	return;
527
528	const auto MCOITypes = getMCOIOperandTypes(CGP: *CGP);
529	assert(MCOITypes.size() == P.operands_size());
530
531	DenseMap<StringRef, std::vector<unsigned>> TyToOpIdx;
532	for (const auto &[Idx, Ty] : enumerate(First: MCOITypes))
533	TyToOpIdx[Ty].push_back(x: Idx);
534
535	if (DebugTypeInfer)
536	errs() << "\tGroups for " << P.getName() << ":\t";
537
538	for (const auto &[Ty, Idxs] : TyToOpIdx) {
539	if (!canMCOIOperandTypeBeARegister(MCOIType: Ty))
540	continue;
541
542	if (DebugTypeInfer)
543	errs() << '[';
544	StringRef Sep = "";
545
546	// We only collect named operands.
547	StringRef Leader;
548	for (unsigned Idx : Idxs) {
549	const auto &Op = P.getOperand(K: Idx);
550	if (!Op.isNamedOperand())
551	continue;
552
553	const auto OpName = Op.getOperandName();
554	if (DebugTypeInfer) {
555	errs() << Sep << OpName;
556	Sep = ", ";
557	}
558
559	if (Leader.empty())
560	OutTECs.insert(Data: (Leader = OpName));
561	else
562	OutTECs.unionSets(V1: Leader, V2: OpName);
563	}
564
565	if (DebugTypeInfer)
566	errs() << "] ";
567	}
568
569	if (DebugTypeInfer)
570	errs() << '\n';
571	}
572
573	CombineRuleOperandTypeChecker::TypeEquivalenceClasses
574	CombineRuleOperandTypeChecker::getRuleEqClasses() const {
575	StringMap<unsigned> OpNameToEqClassIdx;
576	TypeEquivalenceClasses TECs;
577
578	if (DebugTypeInfer)
579	errs() << "Rule Operand Type Equivalence Classes for " << RuleDef.getName()
580	<< ":\n";
581
582	for (const auto *Pat : MatchPats)
583	getInstEqClasses(P: *Pat, OutTECs&: TECs);
584	for (const auto *Pat : ApplyPats)
585	getInstEqClasses(P: *Pat, OutTECs&: TECs);
586
587	if (DebugTypeInfer) {
588	errs() << "Final Type Equivalence Classes: ";
589	for (auto ClassIt = TECs.begin(); ClassIt != TECs.end(); ++ClassIt) {
590	// only print non-empty classes.
591	if (auto MembIt = TECs.member_begin(I: ClassIt);
592	MembIt != TECs.member_end()) {
593	errs() << '[';
594	StringRef Sep = "";
595	for (; MembIt != TECs.member_end(); ++MembIt) {
596	errs() << Sep << *MembIt;
597	Sep = ", ";
598	}
599	errs() << "] ";
600	}
601	}
602	errs() << '\n';
603	}
604
605	return TECs;
606	}
607
608	//===- CombineRuleBuilder -------------------------------------------------===//
609
610	/// Parses combine rule and builds a small intermediate representation to tie
611	/// patterns together and emit RuleMatchers to match them. This may emit more
612	/// than one RuleMatcher, e.g. for `wip_match_opcode`.
613	///
614	/// Memory management for `Pattern` objects is done through `std::unique_ptr`.
615	/// In most cases, there are two stages to a pattern's lifetime:
616	/// - Creation in a `parse` function
617	/// - The unique_ptr is stored in a variable, and may be destroyed if the
618	/// pattern is found to be semantically invalid.
619	/// - Ownership transfer into a `PatternMap`
620	/// - Once a pattern is moved into either the map of Match or Apply
621	/// patterns, it is known to be valid and it never moves back.
622	class CombineRuleBuilder {
623	public:
624	using PatternMap = MapVector<StringRef, std::unique_ptr<Pattern>>;
625	using PatternAlternatives = DenseMap<const Pattern *, unsigned>;
626
627	CombineRuleBuilder(const CodeGenTarget &CGT,
628	SubtargetFeatureInfoMap &SubtargetFeatures,
629	Record &RuleDef, unsigned ID,
630	std::vector<RuleMatcher> &OutRMs)
631	: Parser(CGT, RuleDef.getLoc()), CGT(CGT),
632	SubtargetFeatures(SubtargetFeatures), RuleDef(RuleDef), RuleID(ID),
633	OutRMs(OutRMs) {}
634
635	/// Parses all fields in the RuleDef record.
636	bool parseAll();
637
638	/// Emits all RuleMatchers into the vector of RuleMatchers passed in the
639	/// constructor.
640	bool emitRuleMatchers();
641
642	void print(raw_ostream &OS) const;
643	void dump() const { print(OS&: dbgs()); }
644
645	/// Debug-only verification of invariants.
646	#ifndef NDEBUG
647	void verify() const;
648	#endif
649
650	private:
651	const CodeGenInstruction &getGConstant() const {
652	return CGT.getInstruction(InstRec: RuleDef.getRecords().getDef(Name: "G_CONSTANT"));
653	}
654
655	void PrintError(Twine Msg) const { ::PrintError(Rec: &RuleDef, Msg); }
656	void PrintWarning(Twine Msg) const { ::PrintWarning(WarningLoc: RuleDef.getLoc(), Msg); }
657	void PrintNote(Twine Msg) const { ::PrintNote(NoteLoc: RuleDef.getLoc(), Msg); }
658
659	void print(raw_ostream &OS, const PatternAlternatives &Alts) const;
660
661	bool addApplyPattern(std::unique_ptr<Pattern> Pat);
662	bool addMatchPattern(std::unique_ptr<Pattern> Pat);
663
664	/// Adds the expansions from \see MatchDatas to \p CE.
665	void declareAllMatchDatasExpansions(CodeExpansions &CE) const;
666
667	/// Adds a matcher \p P to \p IM, expanding its code using \p CE.
668	/// Note that the predicate is added on the last InstructionMatcher.
669	///
670	/// \p Alts is only used if DebugCXXPreds is enabled.
671	void addCXXPredicate(RuleMatcher &M, const CodeExpansions &CE,
672	const CXXPattern &P, const PatternAlternatives &Alts);
673
674	/// Adds an apply \p P to \p IM, expanding its code using \p CE.
675	void addCXXAction(RuleMatcher &M, const CodeExpansions &CE,
676	const CXXPattern &P);
677
678	bool hasOnlyCXXApplyPatterns() const;
679	bool hasEraseRoot() const;
680
681	// Infer machine operand types and check their consistency.
682	bool typecheckPatterns();
683
684	/// For all PatFragPatterns, add a new entry in PatternAlternatives for each
685	/// PatternList it contains. This is multiplicative, so if we have 2
686	/// PatFrags with 3 alternatives each, we get 2*3 permutations added to
687	/// PermutationsToEmit. The "MaxPermutations" field controls how many
688	/// permutations are allowed before an error is emitted and this function
689	/// returns false. This is a simple safeguard to prevent combination of
690	/// PatFrags from generating enormous amounts of rules.
691	bool buildPermutationsToEmit();
692
693	/// Checks additional semantics of the Patterns.
694	bool checkSemantics();
695
696	/// Creates a new RuleMatcher with some boilerplate
697	/// settings/actions/predicates, and and adds it to \p OutRMs.
698	/// \see addFeaturePredicates too.
699	///
700	/// \param Alts Current set of alternatives, for debug comment.
701	/// \param AdditionalComment Comment string to be added to the
702	/// `DebugCommentAction`.
703	RuleMatcher &addRuleMatcher(const PatternAlternatives &Alts,
704	Twine AdditionalComment = "");
705	bool addFeaturePredicates(RuleMatcher &M);
706
707	bool findRoots();
708	bool buildRuleOperandsTable();
709
710	bool parseDefs(const DagInit &Def);
711
712	bool emitMatchPattern(CodeExpansions &CE, const PatternAlternatives &Alts,
713	const InstructionPattern &IP);
714	bool emitMatchPattern(CodeExpansions &CE, const PatternAlternatives &Alts,
715	const AnyOpcodePattern &AOP);
716
717	bool emitPatFragMatchPattern(CodeExpansions &CE,
718	const PatternAlternatives &Alts, RuleMatcher &RM,
719	InstructionMatcher *IM,
720	const PatFragPattern &PFP,
721	DenseSet<const Pattern *> &SeenPats);
722
723	bool emitApplyPatterns(CodeExpansions &CE, RuleMatcher &M);
724
725	// Recursively visits InstructionPatterns from P to build up the
726	// RuleMatcher actions.
727	bool emitInstructionApplyPattern(CodeExpansions &CE, RuleMatcher &M,
728	const InstructionPattern &P,
729	DenseSet<const Pattern *> &SeenPats,
730	StringMap<unsigned> &OperandToTempRegID);
731
732	bool emitCodeGenInstructionApplyImmOperand(RuleMatcher &M,
733	BuildMIAction &DstMI,
734	const CodeGenInstructionPattern &P,
735	const InstructionOperand &O);
736
737	bool emitBuiltinApplyPattern(CodeExpansions &CE, RuleMatcher &M,
738	const BuiltinPattern &P,
739	StringMap<unsigned> &OperandToTempRegID);
740
741	// Recursively visits CodeGenInstructionPattern from P to build up the
742	// RuleMatcher/InstructionMatcher. May create new InstructionMatchers as
743	// needed.
744	using OperandMapperFnRef =
745	function_ref<InstructionOperand(const InstructionOperand &)>;
746	using OperandDefLookupFn =
747	function_ref<const InstructionPattern *(StringRef)>;
748	bool emitCodeGenInstructionMatchPattern(
749	CodeExpansions &CE, const PatternAlternatives &Alts, RuleMatcher &M,
750	InstructionMatcher &IM, const CodeGenInstructionPattern &P,
751	DenseSet<const Pattern *> &SeenPats, OperandDefLookupFn LookupOperandDef,
752	OperandMapperFnRef OperandMapper = [](const auto &O) { return O; });
753
754	PatternParser Parser;
755	const CodeGenTarget &CGT;
756	SubtargetFeatureInfoMap &SubtargetFeatures;
757	Record &RuleDef;
758	const unsigned RuleID;
759	std::vector<RuleMatcher> &OutRMs;
760
761	// For InstructionMatcher::addOperand
762	unsigned AllocatedTemporariesBaseID = 0;
763
764	/// The root of the pattern.
765	StringRef RootName;
766
767	/// These maps have ownership of the actual Pattern objects.
768	/// They both map a Pattern's name to the Pattern instance.
769	PatternMap MatchPats;
770	PatternMap ApplyPats;
771
772	/// Operand tables to tie match/apply patterns together.
773	OperandTable MatchOpTable;
774	OperandTable ApplyOpTable;
775
776	/// Set by findRoots.
777	Pattern *MatchRoot = nullptr;
778	SmallDenseSet<InstructionPattern *, 2> ApplyRoots;
779
780	SmallVector<MatchDataInfo, 2> MatchDatas;
781	SmallVector<PatternAlternatives, 1> PermutationsToEmit;
782	};
783
784	bool CombineRuleBuilder::parseAll() {
785	auto StackTrace = PrettyStackTraceParse(RuleDef);
786
787	if (!parseDefs(Def: *RuleDef.getValueAsDag(FieldName: "Defs")))
788	return false;
789
790	if (!Parser.parsePatternList(
791	List: *RuleDef.getValueAsDag(FieldName: "Match"),
792	ParseAction: [this](auto Pat) { return addMatchPattern(Pat: std::move(Pat)); }, Operator: "match",
793	AnonPatNamePrefix: (RuleDef.getName() + "_match").str()))
794	return false;
795
796	if (!Parser.parsePatternList(
797	List: *RuleDef.getValueAsDag(FieldName: "Apply"),
798	ParseAction: [this](auto Pat) { return addApplyPattern(Pat: std::move(Pat)); }, Operator: "apply",
799	AnonPatNamePrefix: (RuleDef.getName() + "_apply").str()))
800	return false;
801
802	if (!buildRuleOperandsTable() || !typecheckPatterns() || !findRoots() ||
803	!checkSemantics() || !buildPermutationsToEmit())
804	return false;
805	LLVM_DEBUG(verify());
806	return true;
807	}
808
809	bool CombineRuleBuilder::emitRuleMatchers() {
810	auto StackTrace = PrettyStackTraceEmit(RuleDef);
811
812	assert(MatchRoot);
813	CodeExpansions CE;
814	declareAllMatchDatasExpansions(CE);
815
816	assert(!PermutationsToEmit.empty());
817	for (const auto &Alts : PermutationsToEmit) {
818	switch (MatchRoot->getKind()) {
819	case Pattern::K_AnyOpcode: {
820	if (!emitMatchPattern(CE, Alts, AOP: *cast<AnyOpcodePattern>(Val: MatchRoot)))
821	return false;
822	break;
823	}
824	case Pattern::K_PatFrag:
825	case Pattern::K_Builtin:
826	case Pattern::K_CodeGenInstruction:
827	if (!emitMatchPattern(CE, Alts, IP: *cast<InstructionPattern>(Val: MatchRoot)))
828	return false;
829	break;
830	case Pattern::K_CXX:
831	PrintError(Msg: "C++ code cannot be the root of a rule!");
832	return false;
833	default:
834	llvm_unreachable("unknown pattern kind!");
835	}
836	}
837
838	return true;
839	}
840
841	void CombineRuleBuilder::print(raw_ostream &OS) const {
842	OS << "(CombineRule name:" << RuleDef.getName() << " id:" << RuleID
843	<< " root:" << RootName << '\n';
844
845	if (!MatchDatas.empty()) {
846	OS << " (MatchDatas\n";
847	for (const auto &MD : MatchDatas) {
848	OS << " ";
849	MD.print(OS);
850	OS << '\n';
851	}
852	OS << " )\n";
853	}
854
855	const auto &SeenPFs = Parser.getSeenPatFrags();
856	if (!SeenPFs.empty()) {
857	OS << " (PatFrags\n";
858	for (const auto *PF : Parser.getSeenPatFrags()) {
859	PF->print(OS, /*Indent=*/" ");
860	OS << '\n';
861	}
862	OS << " )\n";
863	}
864
865	const auto DumpPats = [&](StringRef Name, const PatternMap &Pats) {
866	OS << " (" << Name << " ";
867	if (Pats.empty()) {
868	OS << "<empty>)\n";
869	return;
870	}
871
872	OS << '\n';
873	for (const auto &[Name, Pat] : Pats) {
874	OS << " ";
875	if (Pat.get() == MatchRoot)
876	OS << "<match_root>";
877	if (isa<InstructionPattern>(Val: Pat.get()) &&
878	ApplyRoots.contains(V: cast<InstructionPattern>(Val: Pat.get())))
879	OS << "<apply_root>";
880	OS << Name << ":";
881	Pat->print(OS, /*PrintName=*/false);
882	OS << '\n';
883	}
884	OS << " )\n";
885	};
886
887	DumpPats("MatchPats", MatchPats);
888	DumpPats("ApplyPats", ApplyPats);
889
890	MatchOpTable.print(OS, Name: "MatchPats", /*Indent*/ " ");
891	ApplyOpTable.print(OS, Name: "ApplyPats", /*Indent*/ " ");
892
893	if (PermutationsToEmit.size() > 1) {
894	OS << " (PermutationsToEmit\n";
895	for (const auto &Perm : PermutationsToEmit) {
896	OS << " ";
897	print(OS, Alts: Perm);
898	OS << ",\n";
899	}
900	OS << " )\n";
901	}
902
903	OS << ")\n";
904	}
905
906	#ifndef NDEBUG
907	void CombineRuleBuilder::verify() const {
908	const auto VerifyPats = [&](const PatternMap &Pats) {
909	for (const auto &[Name, Pat] : Pats) {
910	if (!Pat)
911	PrintFatalError(Msg: "null pattern in pattern map!");
912
913	if (Name != Pat->getName()) {
914	Pat->dump();
915	PrintFatalError(Msg: "Pattern name mismatch! Map name: " + Name +
916	", Pat name: " + Pat->getName());
917	}
918
919	// Sanity check: the map should point to the same data as the Pattern.
920	// Both strings are allocated in the pool using insertStrRef.
921	if (Name.data() != Pat->getName().data()) {
922	dbgs() << "Map StringRef: '" << Name << "' @ "
923	<< (const void *)Name.data() << '\n';
924	dbgs() << "Pat String: '" << Pat->getName() << "' @ "
925	<< (const void *)Pat->getName().data() << '\n';
926	PrintFatalError(Msg: "StringRef stored in the PatternMap is not referencing "
927	"the same string as its Pattern!");
928	}
929	}
930	};
931
932	VerifyPats(MatchPats);
933	VerifyPats(ApplyPats);
934
935	// Check there are no wip_match_opcode patterns in the "apply" patterns.
936	if (any_of(Range: ApplyPats,
937	P: [&](auto &E) { return isa<AnyOpcodePattern>(E.second.get()); })) {
938	dump();
939	PrintFatalError(
940	Msg: "illegal wip_match_opcode pattern in the 'apply' patterns!");
941	}
942
943	// Check there are no nullptrs in ApplyRoots.
944	if (ApplyRoots.contains(V: nullptr)) {
945	PrintFatalError(
946	Msg: "CombineRuleBuilder's ApplyRoots set contains a null pointer!");
947	}
948	}
949	#endif
950
951	void CombineRuleBuilder::print(raw_ostream &OS,
952	const PatternAlternatives &Alts) const {
953	SmallVector<std::string, 1> Strings(
954	map_range(C: Alts, F: [](const auto &PatAndPerm) {
955	return PatAndPerm.first->getName().str() + "[" +
956	to_string(PatAndPerm.second) + "]";
957	}));
958	// Sort so output is deterministic for tests. Otherwise it's sorted by pointer
959	// values.
960	sort(C&: Strings);
961	OS << "[" << join(R&: Strings, Separator: ", ") << "]";
962	}
963
964	bool CombineRuleBuilder::addApplyPattern(std::unique_ptr<Pattern> Pat) {
965	StringRef Name = Pat->getName();
966	if (ApplyPats.contains(Key: Name)) {
967	PrintError(Msg: "'" + Name + "' apply pattern defined more than once!");
968	return false;
969	}
970
971	if (isa<AnyOpcodePattern>(Val: Pat.get())) {
972	PrintError(Msg: "'" + Name +
973	"': wip_match_opcode is not supported in apply patterns");
974	return false;
975	}
976
977	if (isa<PatFragPattern>(Val: Pat.get())) {
978	PrintError(Msg: "'" + Name + "': using " + PatFrag::ClassName +
979	" is not supported in apply patterns");
980	return false;
981	}
982
983	if (auto *CXXPat = dyn_cast<CXXPattern>(Val: Pat.get()))
984	CXXPat->setIsApply();
985
986	ApplyPats[Name] = std::move(Pat);
987	return true;
988	}
989
990	bool CombineRuleBuilder::addMatchPattern(std::unique_ptr<Pattern> Pat) {
991	StringRef Name = Pat->getName();
992	if (MatchPats.contains(Key: Name)) {
993	PrintError(Msg: "'" + Name + "' match pattern defined more than once!");
994	return false;
995	}
996
997	// For now, none of the builtins can appear in 'match'.
998	if (const auto *BP = dyn_cast<BuiltinPattern>(Val: Pat.get())) {
999	PrintError(Msg: "'" + BP->getInstName() +
1000	"' cannot be used in a 'match' pattern");
1001	return false;
1002	}
1003
1004	MatchPats[Name] = std::move(Pat);
1005	return true;
1006	}
1007
1008	void CombineRuleBuilder::declareAllMatchDatasExpansions(
1009	CodeExpansions &CE) const {
1010	for (const auto &MD : MatchDatas)
1011	CE.declare(Name: MD.getPatternSymbol(), Expansion: MD.getQualifiedVariableName());
1012	}
1013
1014	void CombineRuleBuilder::addCXXPredicate(RuleMatcher &M,
1015	const CodeExpansions &CE,
1016	const CXXPattern &P,
1017	const PatternAlternatives &Alts) {
1018	// FIXME: Hack so C++ code is executed last. May not work for more complex
1019	// patterns.
1020	auto &IM = *std::prev(x: M.insnmatchers().end());
1021	auto Loc = RuleDef.getLoc();
1022	const auto AddComment = [&](raw_ostream &OS) {
1023	OS << "// Pattern Alternatives: ";
1024	print(OS, Alts);
1025	OS << '\n';
1026	};
1027	const auto &ExpandedCode =
1028	DebugCXXPreds ? P.expandCode(CE, Locs: Loc, AddComment) : P.expandCode(CE, Locs: Loc);
1029	IM->addPredicate<GenericInstructionPredicateMatcher>(
1030	args: ExpandedCode.getEnumNameWithPrefix(Prefix: CXXPredPrefix));
1031	}
1032
1033	void CombineRuleBuilder::addCXXAction(RuleMatcher &M, const CodeExpansions &CE,
1034	const CXXPattern &P) {
1035	const auto &ExpandedCode = P.expandCode(CE, Locs: RuleDef.getLoc());
1036	M.addAction<CustomCXXAction>(
1037	args: ExpandedCode.getEnumNameWithPrefix(Prefix: CXXApplyPrefix));
1038	}
1039
1040	bool CombineRuleBuilder::hasOnlyCXXApplyPatterns() const {
1041	return all_of(Range: ApplyPats, P: [&](auto &Entry) {
1042	return isa<CXXPattern>(Entry.second.get());
1043	});
1044	}
1045
1046	bool CombineRuleBuilder::hasEraseRoot() const {
1047	return any_of(Range: ApplyPats, P: [&](auto &Entry) {
1048	if (const auto *BP = dyn_cast<BuiltinPattern>(Entry.second.get()))
1049	return BP->getBuiltinKind() == BI_EraseRoot;
1050	return false;
1051	});
1052	}
1053
1054	bool CombineRuleBuilder::typecheckPatterns() {
1055	CombineRuleOperandTypeChecker OTC(RuleDef, MatchOpTable);
1056
1057	for (auto &Pat : values(C&: MatchPats)) {
1058	if (auto *IP = dyn_cast<InstructionPattern>(Val: Pat.get())) {
1059	if (!OTC.processMatchPattern(P&: *IP))
1060	return false;
1061	}
1062	}
1063
1064	for (auto &Pat : values(C&: ApplyPats)) {
1065	if (auto *IP = dyn_cast<InstructionPattern>(Val: Pat.get())) {
1066	if (!OTC.processApplyPattern(P&: *IP))
1067	return false;
1068	}
1069	}
1070
1071	OTC.propagateAndInferTypes();
1072
1073	// Always check this after in case inference adds some special types to the
1074	// match patterns.
1075	for (auto &Pat : values(C&: MatchPats)) {
1076	if (auto *IP = dyn_cast<InstructionPattern>(Val: Pat.get())) {
1077	if (IP->diagnoseAllSpecialTypes(
1078	Loc: RuleDef.getLoc(), Msg: PatternType::SpecialTyClassName +
1079	" is not supported in 'match' patterns")) {
1080	return false;
1081	}
1082	}
1083	}
1084	return true;
1085	}
1086
1087	bool CombineRuleBuilder::buildPermutationsToEmit() {
1088	PermutationsToEmit.clear();
1089
1090	// Start with one empty set of alternatives.
1091	PermutationsToEmit.emplace_back();
1092	for (const auto &Pat : values(C&: MatchPats)) {
1093	unsigned NumAlts = 0;
1094	// Note: technically, AnyOpcodePattern also needs permutations, but:
1095	// - We only allow a single one of them in the root.
1096	// - They cannot be mixed with any other pattern other than C++ code.
1097	// So we don't really need to take them into account here. We could, but
1098	// that pattern is a hack anyway and the less it's involved, the better.
1099	if (const auto *PFP = dyn_cast<PatFragPattern>(Val: Pat.get()))
1100	NumAlts = PFP->getPatFrag().num_alternatives();
1101	else
1102	continue;
1103
1104	// For each pattern that needs permutations, multiply the current set of
1105	// alternatives.
1106	auto CurPerms = PermutationsToEmit;
1107	PermutationsToEmit.clear();
1108
1109	for (const auto &Perm : CurPerms) {
1110	assert(!Perm.count(Pat.get()) && "Pattern already emitted?");
1111	for (unsigned K = 0; K < NumAlts; ++K) {
1112	PatternAlternatives NewPerm = Perm;
1113	NewPerm[Pat.get()] = K;
1114	PermutationsToEmit.emplace_back(Args: std::move(NewPerm));
1115	}
1116	}
1117	}
1118
1119	if (int64_t MaxPerms = RuleDef.getValueAsInt(FieldName: "MaxPermutations");
1120	MaxPerms > 0) {
1121	if ((int64_t)PermutationsToEmit.size() > MaxPerms) {
1122	PrintError(Msg: "cannot emit rule '" + RuleDef.getName() + "'; " +
1123	Twine(PermutationsToEmit.size()) +
1124	" permutations would be emitted, but the max is " +
1125	Twine(MaxPerms));
1126	return false;
1127	}
1128	}
1129
1130	// Ensure we always have a single empty entry, it simplifies the emission
1131	// logic so it doesn't need to handle the case where there are no perms.
1132	if (PermutationsToEmit.empty()) {
1133	PermutationsToEmit.emplace_back();
1134	return true;
1135	}
1136
1137	return true;
1138	}
1139
1140	bool CombineRuleBuilder::checkSemantics() {
1141	assert(MatchRoot && "Cannot call this before findRoots()");
1142
1143	bool UsesWipMatchOpcode = false;
1144	for (const auto &Match : MatchPats) {
1145	const auto *Pat = Match.second.get();
1146
1147	if (const auto *CXXPat = dyn_cast<CXXPattern>(Val: Pat)) {
1148	if (!CXXPat->getRawCode().contains(Other: "return "))
1149	PrintWarning(Msg: "'match' C++ code does not seem to return!");
1150	continue;
1151	}
1152
1153	// MIFlags in match cannot use the following syntax: (MIFlags $mi)
1154	if (const auto *CGP = dyn_cast<CodeGenInstructionPattern>(Val: Pat)) {
1155	if (auto *FI = CGP->getMIFlagsInfo()) {
1156	if (!FI->copy_flags().empty()) {
1157	PrintError(
1158	Msg: "'match' patterns cannot refer to flags from other instructions");
1159	PrintNote(Msg: "MIFlags in '" + CGP->getName() +
1160	"' refer to: " + join(R: FI->copy_flags(), Separator: ", "));
1161	return false;
1162	}
1163	}
1164	}
1165
1166	const auto *AOP = dyn_cast<AnyOpcodePattern>(Val: Pat);
1167	if (!AOP)
1168	continue;
1169
1170	if (UsesWipMatchOpcode) {
1171	PrintError(Msg: "wip_opcode_match can only be present once");
1172	return false;
1173	}
1174
1175	UsesWipMatchOpcode = true;
1176	}
1177
1178	for (const auto &Apply : ApplyPats) {
1179	assert(Apply.second.get());
1180	const auto *IP = dyn_cast<InstructionPattern>(Val: Apply.second.get());
1181	if (!IP)
1182	continue;
1183
1184	if (UsesWipMatchOpcode) {
1185	PrintError(Msg: "cannot use wip_match_opcode in combination with apply "
1186	"instruction patterns!");
1187	return false;
1188	}
1189
1190	// Check that the insts mentioned in copy_flags exist.
1191	if (const auto *CGP = dyn_cast<CodeGenInstructionPattern>(Val: IP)) {
1192	if (auto *FI = CGP->getMIFlagsInfo()) {
1193	for (auto InstName : FI->copy_flags()) {
1194	auto It = MatchPats.find(Key: InstName);
1195	if (It == MatchPats.end()) {
1196	PrintError(Msg: "unknown instruction '$" + InstName +
1197	"' referenced in MIFlags of '" + CGP->getName() + "'");
1198	return false;
1199	}
1200
1201	if (!isa<CodeGenInstructionPattern>(Val: It->second.get())) {
1202	PrintError(
1203	Msg: "'$" + InstName +
1204	"' does not refer to a CodeGenInstruction in MIFlags of '" +
1205	CGP->getName() + "'");
1206	return false;
1207	}
1208	}
1209	}
1210	}
1211
1212	const auto *BIP = dyn_cast<BuiltinPattern>(Val: IP);
1213	if (!BIP)
1214	continue;
1215	StringRef Name = BIP->getInstName();
1216
1217	// (GIEraseInst) has to be the only apply pattern, or it can not be used at
1218	// all. The root cannot have any defs either.
1219	switch (BIP->getBuiltinKind()) {
1220	case BI_EraseRoot: {
1221	if (ApplyPats.size() > 1) {
1222	PrintError(Msg: Name + " must be the only 'apply' pattern");
1223	return false;
1224	}
1225
1226	const auto *IRoot = dyn_cast<CodeGenInstructionPattern>(Val: MatchRoot);
1227	if (!IRoot) {
1228	PrintError(Msg: Name + " can only be used if the root is a "
1229	"CodeGenInstruction or Intrinsic");
1230	return false;
1231	}
1232
1233	if (IRoot->getNumInstDefs() != 0) {
1234	PrintError(Msg: Name + " can only be used if on roots that do "
1235	"not have any output operand");
1236	PrintNote(Msg: "'" + IRoot->getInstName() + "' has " +
1237	Twine(IRoot->getNumInstDefs()) + " output operands");
1238	return false;
1239	}
1240	break;
1241	}
1242	case BI_ReplaceReg: {
1243	// (GIReplaceReg can only be used on the root instruction)
1244	// TODO: When we allow rewriting non-root instructions, also allow this.
1245	StringRef OldRegName = BIP->getOperand(K: 0).getOperandName();
1246	auto *Def = MatchOpTable.getDef(OpName: OldRegName);
1247	if (!Def) {
1248	PrintError(Msg: Name + " cannot find a matched pattern that defines '" +
1249	OldRegName + "'");
1250	return false;
1251	}
1252	if (MatchOpTable.getDef(OpName: OldRegName) != MatchRoot) {
1253	PrintError(Msg: Name + " cannot replace '" + OldRegName +
1254	"': this builtin can only replace a register defined by the "
1255	"match root");
1256	return false;
1257	}
1258	break;
1259	}
1260	}
1261	}
1262
1263	return true;
1264	}
1265
1266	RuleMatcher &CombineRuleBuilder::addRuleMatcher(const PatternAlternatives &Alts,
1267	Twine AdditionalComment) {
1268	auto &RM = OutRMs.emplace_back(args: RuleDef.getLoc());
1269	addFeaturePredicates(M&: RM);
1270	RM.setPermanentGISelFlags(GISF_IgnoreCopies);
1271	RM.addRequiredSimplePredicate(PredName: getIsEnabledPredicateEnumName(CombinerRuleID: RuleID));
1272
1273	std::string Comment;
1274	raw_string_ostream CommentOS(Comment);
1275	CommentOS << "Combiner Rule #" << RuleID << ": " << RuleDef.getName();
1276	if (!Alts.empty()) {
1277	CommentOS << " @ ";
1278	print(OS&: CommentOS, Alts);
1279	}
1280	if (!AdditionalComment.isTriviallyEmpty())
1281	CommentOS << "; " << AdditionalComment;
1282	RM.addAction<DebugCommentAction>(args&: Comment);
1283	return RM;
1284	}
1285
1286	bool CombineRuleBuilder::addFeaturePredicates(RuleMatcher &M) {
1287	if (!RuleDef.getValue(Name: "Predicates"))
1288	return true;
1289
1290	ListInit *Preds = RuleDef.getValueAsListInit(FieldName: "Predicates");
1291	for (Init *PI : Preds->getValues()) {
1292	DefInit *Pred = dyn_cast<DefInit>(Val: PI);
1293	if (!Pred)
1294	continue;
1295
1296	Record *Def = Pred->getDef();
1297	if (!Def->isSubClassOf(Name: "Predicate")) {
1298	::PrintError(Rec: Def, Msg: "Unknown 'Predicate' Type");
1299	return false;
1300	}
1301
1302	if (Def->getValueAsString(FieldName: "CondString").empty())
1303	continue;
1304
1305	if (SubtargetFeatures.count(x: Def) == 0) {
1306	SubtargetFeatures.emplace(
1307	args&: Def, args: SubtargetFeatureInfo(Def, SubtargetFeatures.size()));
1308	}
1309
1310	M.addRequiredFeature(Feature: Def);
1311	}
1312
1313	return true;
1314	}
1315
1316	bool CombineRuleBuilder::findRoots() {
1317	const auto Finish = [&]() {
1318	assert(MatchRoot);
1319
1320	if (hasOnlyCXXApplyPatterns() || hasEraseRoot())
1321	return true;
1322
1323	auto *IPRoot = dyn_cast<InstructionPattern>(Val: MatchRoot);
1324	if (!IPRoot)
1325	return true;
1326
1327	if (IPRoot->getNumInstDefs() == 0) {
1328	// No defs to work with -> find the root using the pattern name.
1329	auto It = ApplyPats.find(Key: RootName);
1330	if (It == ApplyPats.end()) {
1331	PrintError(Msg: "Cannot find root '" + RootName + "' in apply patterns!");
1332	return false;
1333	}
1334
1335	auto *ApplyRoot = dyn_cast<InstructionPattern>(Val: It->second.get());
1336	if (!ApplyRoot) {
1337	PrintError(Msg: "apply pattern root '" + RootName +
1338	"' must be an instruction pattern");
1339	return false;
1340	}
1341
1342	ApplyRoots.insert(V: ApplyRoot);
1343	return true;
1344	}
1345
1346	// Collect all redefinitions of the MatchRoot's defs and put them in
1347	// ApplyRoots.
1348	const auto DefsNeeded = IPRoot->getApplyDefsNeeded();
1349	for (auto &Op : DefsNeeded) {
1350	assert(Op.isDef() && Op.isNamedOperand());
1351	StringRef Name = Op.getOperandName();
1352
1353	auto *ApplyRedef = ApplyOpTable.getDef(OpName: Name);
1354	if (!ApplyRedef) {
1355	PrintError(Msg: "'" + Name + "' must be redefined in the 'apply' pattern");
1356	return false;
1357	}
1358
1359	ApplyRoots.insert(V: (InstructionPattern *)ApplyRedef);
1360	}
1361
1362	if (auto It = ApplyPats.find(Key: RootName); It != ApplyPats.end()) {
1363	if (find(Range&: ApplyRoots, Val: It->second.get()) == ApplyRoots.end()) {
1364	PrintError(Msg: "apply pattern '" + RootName +
1365	"' is supposed to be a root but it does not redefine any of "
1366	"the defs of the match root");
1367	return false;
1368	}
1369	}
1370
1371	return true;
1372	};
1373
1374	// Look by pattern name, e.g.
1375	// (G_FNEG $x, $y):$root
1376	if (auto MatchPatIt = MatchPats.find(Key: RootName);
1377	MatchPatIt != MatchPats.end()) {
1378	MatchRoot = MatchPatIt->second.get();
1379	return Finish();
1380	}
1381
1382	// Look by def:
1383	// (G_FNEG $root, $y)
1384	auto LookupRes = MatchOpTable.lookup(OpName: RootName);
1385	if (!LookupRes.Found) {
1386	PrintError(Msg: "Cannot find root '" + RootName + "' in match patterns!");
1387	return false;
1388	}
1389
1390	MatchRoot = LookupRes.Def;
1391	if (!MatchRoot) {
1392	PrintError(Msg: "Cannot use live-in operand '" + RootName +
1393	"' as match pattern root!");
1394	return false;
1395	}
1396
1397	return Finish();
1398	}
1399
1400	bool CombineRuleBuilder::buildRuleOperandsTable() {
1401	const auto DiagnoseRedefMatch = [&](StringRef OpName) {
1402	PrintError(Msg: "Operand '" + OpName +
1403	"' is defined multiple times in the 'match' patterns");
1404	};
1405
1406	const auto DiagnoseRedefApply = [&](StringRef OpName) {
1407	PrintError(Msg: "Operand '" + OpName +
1408	"' is defined multiple times in the 'apply' patterns");
1409	};
1410
1411	for (auto &Pat : values(C&: MatchPats)) {
1412	auto *IP = dyn_cast<InstructionPattern>(Val: Pat.get());
1413	if (IP && !MatchOpTable.addPattern(P: IP, DiagnoseRedef: DiagnoseRedefMatch))
1414	return false;
1415	}
1416
1417	for (auto &Pat : values(C&: ApplyPats)) {
1418	auto *IP = dyn_cast<InstructionPattern>(Val: Pat.get());
1419	if (IP && !ApplyOpTable.addPattern(P: IP, DiagnoseRedef: DiagnoseRedefApply))
1420	return false;
1421	}
1422
1423	return true;
1424	}
1425
1426	bool CombineRuleBuilder::parseDefs(const DagInit &Def) {
1427	if (Def.getOperatorAsDef(Loc: RuleDef.getLoc())->getName() != "defs") {
1428	PrintError(Msg: "Expected defs operator");
1429	return false;
1430	}
1431
1432	SmallVector<StringRef> Roots;
1433	for (unsigned I = 0, E = Def.getNumArgs(); I < E; ++I) {
1434	if (isSpecificDef(N: *Def.getArg(Num: I), Def: "root")) {
1435	Roots.emplace_back(Args: Def.getArgNameStr(Num: I));
1436	continue;
1437	}
1438
1439	// Subclasses of GIDefMatchData should declare that this rule needs to pass
1440	// data from the match stage to the apply stage, and ensure that the
1441	// generated matcher has a suitable variable for it to do so.
1442	if (Record *MatchDataRec =
1443	getDefOfSubClass(N: *Def.getArg(Num: I), Cls: "GIDefMatchData")) {
1444	MatchDatas.emplace_back(Args: Def.getArgNameStr(Num: I),
1445	Args: MatchDataRec->getValueAsString(FieldName: "Type"));
1446	continue;
1447	}
1448
1449	// Otherwise emit an appropriate error message.
1450	if (getDefOfSubClass(N: *Def.getArg(Num: I), Cls: "GIDefKind"))
1451	PrintError(Msg: "This GIDefKind not implemented in tablegen");
1452	else if (getDefOfSubClass(N: *Def.getArg(Num: I), Cls: "GIDefKindWithArgs"))
1453	PrintError(Msg: "This GIDefKindWithArgs not implemented in tablegen");
1454	else
1455	PrintError(Msg: "Expected a subclass of GIDefKind or a sub-dag whose "
1456	"operator is of type GIDefKindWithArgs");
1457	return false;
1458	}
1459
1460	if (Roots.size() != 1) {
1461	PrintError(Msg: "Combine rules must have exactly one root");
1462	return false;
1463	}
1464
1465	RootName = Roots.front();
1466
1467	// Assign variables to all MatchDatas.
1468	AssignMatchDataVariables(Infos: MatchDatas);
1469	return true;
1470	}
1471
1472	bool CombineRuleBuilder::emitMatchPattern(CodeExpansions &CE,
1473	const PatternAlternatives &Alts,
1474	const InstructionPattern &IP) {
1475	auto StackTrace = PrettyStackTraceEmit(RuleDef, &IP);
1476
1477	auto &M = addRuleMatcher(Alts);
1478	InstructionMatcher &IM = M.addInstructionMatcher(SymbolicName: IP.getName());
1479	declareInstExpansion(CE, IM, Name: IP.getName());
1480
1481	DenseSet<const Pattern *> SeenPats;
1482
1483	const auto FindOperandDef = [&](StringRef Op) -> InstructionPattern * {
1484	return MatchOpTable.getDef(OpName: Op);
1485	};
1486
1487	if (const auto *CGP = dyn_cast<CodeGenInstructionPattern>(Val: &IP)) {
1488	if (!emitCodeGenInstructionMatchPattern(CE, Alts, M, IM, P: *CGP, SeenPats,
1489	LookupOperandDef: FindOperandDef))
1490	return false;
1491	} else if (const auto *PFP = dyn_cast<PatFragPattern>(Val: &IP)) {
1492	if (!PFP->getPatFrag().canBeMatchRoot()) {
1493	PrintError(Msg: "cannot use '" + PFP->getInstName() + " as match root");
1494	return false;
1495	}
1496
1497	if (!emitPatFragMatchPattern(CE, Alts, RM&: M, IM: &IM, PFP: *PFP, SeenPats))
1498	return false;
1499	} else if (isa<BuiltinPattern>(Val: &IP)) {
1500	llvm_unreachable("No match builtins known!");
1501	} else
1502	llvm_unreachable("Unknown kind of InstructionPattern!");
1503
1504	// Emit remaining patterns
1505	for (auto &Pat : values(C&: MatchPats)) {
1506	if (SeenPats.contains(V: Pat.get()))
1507	continue;
1508
1509	switch (Pat->getKind()) {
1510	case Pattern::K_AnyOpcode:
1511	PrintError(Msg: "wip_match_opcode can not be used with instruction patterns!");
1512	return false;
1513	case Pattern::K_PatFrag: {
1514	if (!emitPatFragMatchPattern(CE, Alts, RM&: M, /*IM*/ nullptr,
1515	PFP: *cast<PatFragPattern>(Val: Pat.get()), SeenPats))
1516	return false;
1517	continue;
1518	}
1519	case Pattern::K_Builtin:
1520	PrintError(Msg: "No known match builtins");
1521	return false;
1522	case Pattern::K_CodeGenInstruction:
1523	cast<InstructionPattern>(Val: Pat.get())->reportUnreachable(Locs: RuleDef.getLoc());
1524	return false;
1525	case Pattern::K_CXX: {
1526	addCXXPredicate(M, CE, P: *cast<CXXPattern>(Val: Pat.get()), Alts);
1527	continue;
1528	}
1529	default:
1530	llvm_unreachable("unknown pattern kind!");
1531	}
1532	}
1533
1534	return emitApplyPatterns(CE, M);
1535	}
1536
1537	bool CombineRuleBuilder::emitMatchPattern(CodeExpansions &CE,
1538	const PatternAlternatives &Alts,
1539	const AnyOpcodePattern &AOP) {
1540	auto StackTrace = PrettyStackTraceEmit(RuleDef, &AOP);
1541
1542	for (const CodeGenInstruction *CGI : AOP.insts()) {
1543	auto &M = addRuleMatcher(Alts, AdditionalComment: "wip_match_opcode '" +
1544	CGI->TheDef->getName() + "'");
1545
1546	InstructionMatcher &IM = M.addInstructionMatcher(SymbolicName: AOP.getName());
1547	declareInstExpansion(CE, IM, Name: AOP.getName());
1548	// declareInstExpansion needs to be identical, otherwise we need to create a
1549	// CodeExpansions object here instead.
1550	assert(IM.getInsnVarID() == 0);
1551
1552	IM.addPredicate<InstructionOpcodeMatcher>(args&: CGI);
1553
1554	// Emit remaining patterns.
1555	for (auto &Pat : values(C&: MatchPats)) {
1556	if (Pat.get() == &AOP)
1557	continue;
1558
1559	switch (Pat->getKind()) {
1560	case Pattern::K_AnyOpcode:
1561	PrintError(Msg: "wip_match_opcode can only be present once!");
1562	return false;
1563	case Pattern::K_PatFrag: {
1564	DenseSet<const Pattern *> SeenPats;
1565	if (!emitPatFragMatchPattern(CE, Alts, RM&: M, /*IM*/ nullptr,
1566	PFP: *cast<PatFragPattern>(Val: Pat.get()),
1567	SeenPats))
1568	return false;
1569	continue;
1570	}
1571	case Pattern::K_Builtin:
1572	PrintError(Msg: "No known match builtins");
1573	return false;
1574	case Pattern::K_CodeGenInstruction:
1575	cast<InstructionPattern>(Val: Pat.get())->reportUnreachable(
1576	Locs: RuleDef.getLoc());
1577	return false;
1578	case Pattern::K_CXX: {
1579	addCXXPredicate(M, CE, P: *cast<CXXPattern>(Val: Pat.get()), Alts);
1580	break;
1581	}
1582	default:
1583	llvm_unreachable("unknown pattern kind!");
1584	}
1585	}
1586
1587	if (!emitApplyPatterns(CE, M))
1588	return false;
1589	}
1590
1591	return true;
1592	}
1593
1594	bool CombineRuleBuilder::emitPatFragMatchPattern(
1595	CodeExpansions &CE, const PatternAlternatives &Alts, RuleMatcher &RM,
1596	InstructionMatcher *IM, const PatFragPattern &PFP,
1597	DenseSet<const Pattern *> &SeenPats) {
1598	auto StackTrace = PrettyStackTraceEmit(RuleDef, &PFP);
1599
1600	if (SeenPats.contains(V: &PFP))
1601	return true;
1602	SeenPats.insert(V: &PFP);
1603
1604	const auto &PF = PFP.getPatFrag();
1605
1606	if (!IM) {
1607	// When we don't have an IM, this means this PatFrag isn't reachable from
1608	// the root. This is only acceptable if it doesn't define anything (e.g. a
1609	// pure C++ PatFrag).
1610	if (PF.num_out_params() != 0) {
1611	PFP.reportUnreachable(Locs: RuleDef.getLoc());
1612	return false;
1613	}
1614	} else {
1615	// When an IM is provided, this is reachable from the root, and we're
1616	// expecting to have output operands.
1617	// TODO: If we want to allow for multiple roots we'll need a map of IMs
1618	// then, and emission becomes a bit more complicated.
1619	assert(PF.num_roots() == 1);
1620	}
1621
1622	CodeExpansions PatFragCEs;
1623	if (!PFP.mapInputCodeExpansions(ParentCEs: CE, PatFragCEs, DiagLoc: RuleDef.getLoc()))
1624	return false;
1625
1626	// List of {ParamName, ArgName}.
1627	// When all patterns have been emitted, find expansions in PatFragCEs named
1628	// ArgName and add their expansion to CE using ParamName as the key.
1629	SmallVector<std::pair<std::string, std::string>, 4> CEsToImport;
1630
1631	// Map parameter names to the actual argument.
1632	const auto OperandMapper =
1633	[&](const InstructionOperand &O) -> InstructionOperand {
1634	if (!O.isNamedOperand())
1635	return O;
1636
1637	StringRef ParamName = O.getOperandName();
1638
1639	// Not sure what to do with those tbh. They should probably never be here.
1640	assert(!O.isNamedImmediate() && "TODO: handle named imms");
1641	unsigned PIdx = PF.getParamIdx(Name: ParamName);
1642
1643	// Map parameters to the argument values.
1644	if (PIdx == (unsigned)-1) {
1645	// This is a temp of the PatFragPattern, prefix the name to avoid
1646	// conflicts.
1647	return O.withNewName(
1648	NewName: insertStrRef(S: (PFP.getName() + "." + ParamName).str()));
1649	}
1650
1651	// The operand will be added to PatFragCEs's code expansions using the
1652	// parameter's name. If it's bound to some operand during emission of the
1653	// patterns, we'll want to add it to CE.
1654	auto ArgOp = PFP.getOperand(K: PIdx);
1655	if (ArgOp.isNamedOperand())
1656	CEsToImport.emplace_back(Args: ArgOp.getOperandName().str(), Args&: ParamName);
1657
1658	if (ArgOp.getType() && O.getType() && ArgOp.getType() != O.getType()) {
1659	StringRef PFName = PF.getName();
1660	PrintWarning(Msg: "impossible type constraints: operand " + Twine(PIdx) +
1661	" of '" + PFP.getName() + "' has type '" +
1662	ArgOp.getType().str() + "', but '" + PFName +
1663	"' constrains it to '" + O.getType().str() + "'");
1664	if (ArgOp.isNamedOperand())
1665	PrintNote(Msg: "operand " + Twine(PIdx) + " of '" + PFP.getName() +
1666	"' is '" + ArgOp.getOperandName() + "'");
1667	if (O.isNamedOperand())
1668	PrintNote(Msg: "argument " + Twine(PIdx) + " of '" + PFName + "' is '" +
1669	ParamName + "'");
1670	}
1671
1672	return ArgOp;
1673	};
1674
1675	// PatFragPatterns are only made of InstructionPatterns or CXXPatterns.
1676	// Emit instructions from the root.
1677	const auto &FragAlt = PF.getAlternative(K: Alts.lookup(Val: &PFP));
1678	const auto &FragAltOT = FragAlt.OpTable;
1679	const auto LookupOperandDef =
1680	[&](StringRef Op) -> const InstructionPattern * {
1681	return FragAltOT.getDef(OpName: Op);
1682	};
1683
1684	DenseSet<const Pattern *> PatFragSeenPats;
1685	for (const auto &[Idx, InOp] : enumerate(First: PF.out_params())) {
1686	if (InOp.Kind != PatFrag::PK_Root)
1687	continue;
1688
1689	StringRef ParamName = InOp.Name;
1690	const auto *Def = FragAltOT.getDef(OpName: ParamName);
1691	assert(Def && "PatFrag::checkSemantics should have emitted an error if "
1692	"an out operand isn't defined!");
1693	assert(isa<CodeGenInstructionPattern>(Def) &&
1694	"Nested PatFrags not supported yet");
1695
1696	if (!emitCodeGenInstructionMatchPattern(
1697	CE&: PatFragCEs, Alts, M&: RM, IM&: *IM, P: *cast<CodeGenInstructionPattern>(Val: Def),
1698	SeenPats&: PatFragSeenPats, LookupOperandDef, OperandMapper))
1699	return false;
1700	}
1701
1702	// Emit leftovers.
1703	for (const auto &Pat : FragAlt.Pats) {
1704	if (PatFragSeenPats.contains(V: Pat.get()))
1705	continue;
1706
1707	if (const auto *CXXPat = dyn_cast<CXXPattern>(Val: Pat.get())) {
1708	addCXXPredicate(M&: RM, CE: PatFragCEs, P: *CXXPat, Alts);
1709	continue;
1710	}
1711
1712	if (const auto *IP = dyn_cast<InstructionPattern>(Val: Pat.get())) {
1713	IP->reportUnreachable(Locs: PF.getLoc());
1714	return false;
1715	}
1716
1717	llvm_unreachable("Unexpected pattern kind in PatFrag");
1718	}
1719
1720	for (const auto &[ParamName, ArgName] : CEsToImport) {
1721	// Note: we're find if ParamName already exists. It just means it's been
1722	// bound before, so we prefer to keep the first binding.
1723	CE.declare(Name: ParamName, Expansion: PatFragCEs.lookup(Variable: ArgName));
1724	}
1725
1726	return true;
1727	}
1728
1729	bool CombineRuleBuilder::emitApplyPatterns(CodeExpansions &CE, RuleMatcher &M) {
1730	if (hasOnlyCXXApplyPatterns()) {
1731	for (auto &Pat : values(C&: ApplyPats))
1732	addCXXAction(M, CE, P: *cast<CXXPattern>(Val: Pat.get()));
1733	return true;
1734	}
1735
1736	DenseSet<const Pattern *> SeenPats;
1737	StringMap<unsigned> OperandToTempRegID;
1738
1739	for (auto *ApplyRoot : ApplyRoots) {
1740	assert(isa<InstructionPattern>(ApplyRoot) &&
1741	"Root can only be a InstructionPattern!");
1742	if (!emitInstructionApplyPattern(CE, M,
1743	P: cast<InstructionPattern>(Val&: *ApplyRoot),
1744	SeenPats, OperandToTempRegID))
1745	return false;
1746	}
1747
1748	for (auto &Pat : values(C&: ApplyPats)) {
1749	if (SeenPats.contains(V: Pat.get()))
1750	continue;
1751
1752	switch (Pat->getKind()) {
1753	case Pattern::K_AnyOpcode:
1754	llvm_unreachable("Unexpected pattern in apply!");
1755	case Pattern::K_PatFrag:
1756	// TODO: We could support pure C++ PatFrags as a temporary thing.
1757	llvm_unreachable("Unexpected pattern in apply!");
1758	case Pattern::K_Builtin:
1759	if (!emitInstructionApplyPattern(CE, M, P: cast<BuiltinPattern>(Val&: *Pat),
1760	SeenPats, OperandToTempRegID))
1761	return false;
1762	break;
1763	case Pattern::K_CodeGenInstruction:
1764	cast<CodeGenInstructionPattern>(Val&: *Pat).reportUnreachable(Locs: RuleDef.getLoc());
1765	return false;
1766	case Pattern::K_CXX: {
1767	addCXXAction(M, CE, P: *cast<CXXPattern>(Val: Pat.get()));
1768	continue;
1769	}
1770	default:
1771	llvm_unreachable("unknown pattern kind!");
1772	}
1773	}
1774
1775	// Erase the root.
1776	unsigned RootInsnID =
1777	M.getInsnVarID(InsnMatcher&: M.getInstructionMatcher(SymbolicName: MatchRoot->getName()));
1778	M.addAction<EraseInstAction>(args&: RootInsnID);
1779
1780	return true;
1781	}
1782
1783	bool CombineRuleBuilder::emitInstructionApplyPattern(
1784	CodeExpansions &CE, RuleMatcher &M, const InstructionPattern &P,
1785	DenseSet<const Pattern *> &SeenPats,
1786	StringMap<unsigned> &OperandToTempRegID) {
1787	auto StackTrace = PrettyStackTraceEmit(RuleDef, &P);
1788
1789	if (SeenPats.contains(V: &P))
1790	return true;
1791
1792	SeenPats.insert(V: &P);
1793
1794	// First, render the uses.
1795	for (auto &Op : P.named_operands()) {
1796	if (Op.isDef())
1797	continue;
1798
1799	StringRef OpName = Op.getOperandName();
1800	if (const auto *DefPat = ApplyOpTable.getDef(OpName)) {
1801	if (!emitInstructionApplyPattern(CE, M, P: *DefPat, SeenPats,
1802	OperandToTempRegID))
1803	return false;
1804	} else {
1805	// If we have no def, check this exists in the MatchRoot.
1806	if (!Op.isNamedImmediate() && !MatchOpTable.lookup(OpName).Found) {
1807	PrintError(Msg: "invalid output operand '" + OpName +
1808	"': operand is not a live-in of the match pattern, and it "
1809	"has no definition");
1810	return false;
1811	}
1812	}
1813	}
1814
1815	if (const auto *BP = dyn_cast<BuiltinPattern>(Val: &P))
1816	return emitBuiltinApplyPattern(CE, M, P: *BP, OperandToTempRegID);
1817
1818	if (isa<PatFragPattern>(Val: &P))
1819	llvm_unreachable("PatFragPatterns is not supported in 'apply'!");
1820
1821	auto &CGIP = cast<CodeGenInstructionPattern>(Val: P);
1822
1823	// Now render this inst.
1824	auto &DstMI =
1825	M.addAction<BuildMIAction>(args: M.allocateOutputInsnID(), args: &CGIP.getInst());
1826
1827	bool HasEmittedIntrinsicID = false;
1828	const auto EmitIntrinsicID = [&]() {
1829	assert(CGIP.isIntrinsic());
1830	DstMI.addRenderer<IntrinsicIDRenderer>(args: CGIP.getIntrinsic());
1831	HasEmittedIntrinsicID = true;
1832	};
1833
1834	for (auto &Op : P.operands()) {
1835	// Emit the intrinsic ID after the last def.
1836	if (CGIP.isIntrinsic() && !Op.isDef() && !HasEmittedIntrinsicID)
1837	EmitIntrinsicID();
1838
1839	if (Op.isNamedImmediate()) {
1840	PrintError(Msg: "invalid output operand '" + Op.getOperandName() +
1841	"': output immediates cannot be named");
1842	PrintNote(Msg: "while emitting pattern '" + P.getName() + "' (" +
1843	P.getInstName() + ")");
1844	return false;
1845	}
1846
1847	if (Op.hasImmValue()) {
1848	if (!emitCodeGenInstructionApplyImmOperand(M, DstMI, P: CGIP, O: Op))
1849	return false;
1850	continue;
1851	}
1852
1853	StringRef OpName = Op.getOperandName();
1854
1855	// Uses of operand.
1856	if (!Op.isDef()) {
1857	if (auto It = OperandToTempRegID.find(Key: OpName);
1858	It != OperandToTempRegID.end()) {
1859	assert(!MatchOpTable.lookup(OpName).Found &&
1860	"Temp reg is also from match pattern?");
1861	DstMI.addRenderer<TempRegRenderer>(args&: It->second);
1862	} else {
1863	// This should be a match live in or a redef of a matched instr.
1864	// If it's a use of a temporary register, then we messed up somewhere -
1865	// the previous condition should have passed.
1866	assert(MatchOpTable.lookup(OpName).Found &&
1867	!ApplyOpTable.getDef(OpName) && "Temp reg not emitted yet!");
1868	DstMI.addRenderer<CopyRenderer>(args&: OpName);
1869	}
1870	continue;
1871	}
1872
1873	// Determine what we're dealing with. Are we replace a matched instruction?
1874	// Creating a new one?
1875	auto OpLookupRes = MatchOpTable.lookup(OpName);
1876	if (OpLookupRes.Found) {
1877	if (OpLookupRes.isLiveIn()) {
1878	// live-in of the match pattern.
1879	PrintError(Msg: "Cannot define live-in operand '" + OpName +
1880	"' in the 'apply' pattern");
1881	return false;
1882	}
1883	assert(OpLookupRes.Def);
1884
1885	// TODO: Handle this. We need to mutate the instr, or delete the old
1886	// one.
1887	// Likewise, we also need to ensure we redef everything, if the
1888	// instr has more than one def, we need to redef all or nothing.
1889	if (OpLookupRes.Def != MatchRoot) {
1890	PrintError(Msg: "redefining an instruction other than the root is not "
1891	"supported (operand '" +
1892	OpName + "')");
1893	return false;
1894	}
1895	// redef of a match
1896	DstMI.addRenderer<CopyRenderer>(args&: OpName);
1897	continue;
1898	}
1899
1900	// Define a new register unique to the apply patterns (AKA a "temp"
1901	// register).
1902	unsigned TempRegID;
1903	if (auto It = OperandToTempRegID.find(Key: OpName);
1904	It != OperandToTempRegID.end()) {
1905	TempRegID = It->second;
1906	} else {
1907	// This is a brand new register.
1908	TempRegID = M.allocateTempRegID();
1909	OperandToTempRegID[OpName] = TempRegID;
1910	const auto Ty = Op.getType();
1911	if (!Ty) {
1912	PrintError(Msg: "def of a new register '" + OpName +
1913	"' in the apply patterns must have a type");
1914	return false;
1915	}
1916
1917	declareTempRegExpansion(CE, TempRegID, Name: OpName);
1918	// Always insert the action at the beginning, otherwise we may end up
1919	// using the temp reg before it's available.
1920	M.insertAction<MakeTempRegisterAction>(
1921	InsertPt: M.actions_begin(), args: getLLTCodeGenOrTempType(PT: Ty, RM&: M), args&: TempRegID);
1922	}
1923
1924	DstMI.addRenderer<TempRegRenderer>(args&: TempRegID, /*IsDef=*/args: true);
1925	}
1926
1927	// Some intrinsics have no in operands, ensure the ID is still emitted in such
1928	// cases.
1929	if (CGIP.isIntrinsic() && !HasEmittedIntrinsicID)
1930	EmitIntrinsicID();
1931
1932	// Render MIFlags
1933	if (const auto *FI = CGIP.getMIFlagsInfo()) {
1934	for (StringRef InstName : FI->copy_flags())
1935	DstMI.addCopiedMIFlags(IM: M.getInstructionMatcher(SymbolicName: InstName));
1936	for (StringRef F : FI->set_flags())
1937	DstMI.addSetMIFlags(Flag: F);
1938	for (StringRef F : FI->unset_flags())
1939	DstMI.addUnsetMIFlags(Flag: F);
1940	}
1941
1942	// Don't allow mutating opcodes for GISel combiners. We want a more precise
1943	// handling of MIFlags so we require them to be explicitly preserved.
1944	//
1945	// TODO: We don't mutate very often, if at all in combiners, but it'd be nice
1946	// to re-enable this. We'd then need to always clear MIFlags when mutating
1947	// opcodes, and never mutate an inst that we copy flags from.
1948	// DstMI.chooseInsnToMutate(M);
1949	declareInstExpansion(CE, A: DstMI, Name: P.getName());
1950
1951	return true;
1952	}
1953
1954	bool CombineRuleBuilder::emitCodeGenInstructionApplyImmOperand(
1955	RuleMatcher &M, BuildMIAction &DstMI, const CodeGenInstructionPattern &P,
1956	const InstructionOperand &O) {
1957	// If we have a type, we implicitly emit a G_CONSTANT, except for G_CONSTANT
1958	// itself where we emit a CImm.
1959	//
1960	// No type means we emit a simple imm.
1961	// G_CONSTANT is a special case and needs a CImm though so this is likely a
1962	// mistake.
1963	const bool isGConstant = P.is(OpcodeName: "G_CONSTANT");
1964	const auto Ty = O.getType();
1965	if (!Ty) {
1966	if (isGConstant) {
1967	PrintError(Msg: "'G_CONSTANT' immediate must be typed!");
1968	PrintNote(Msg: "while emitting pattern '" + P.getName() + "' (" +
1969	P.getInstName() + ")");
1970	return false;
1971	}
1972
1973	DstMI.addRenderer<ImmRenderer>(args: O.getImmValue());
1974	return true;
1975	}
1976
1977	auto ImmTy = getLLTCodeGenOrTempType(PT: Ty, RM&: M);
1978
1979	if (isGConstant) {
1980	DstMI.addRenderer<ImmRenderer>(args: O.getImmValue(), args&: ImmTy);
1981	return true;
1982	}
1983
1984	unsigned TempRegID = M.allocateTempRegID();
1985	// Ensure MakeTempReg & the BuildConstantAction occur at the beginning.
1986	auto InsertIt = M.insertAction<MakeTempRegisterAction>(InsertPt: M.actions_begin(),
1987	args&: ImmTy, args&: TempRegID);
1988	M.insertAction<BuildConstantAction>(InsertPt: ++InsertIt, args&: TempRegID, args: O.getImmValue());
1989	DstMI.addRenderer<TempRegRenderer>(args&: TempRegID);
1990	return true;
1991	}
1992
1993	bool CombineRuleBuilder::emitBuiltinApplyPattern(
1994	CodeExpansions &CE, RuleMatcher &M, const BuiltinPattern &P,
1995	StringMap<unsigned> &OperandToTempRegID) {
1996	const auto Error = [&](Twine Reason) {
1997	PrintError(Msg: "cannot emit '" + P.getInstName() + "' builtin: " + Reason);
1998	return false;
1999	};
2000
2001	switch (P.getBuiltinKind()) {
2002	case BI_EraseRoot: {
2003	// Root is always inst 0.
2004	M.addAction<EraseInstAction>(/*InsnID*/ args: 0);
2005	return true;
2006	}
2007	case BI_ReplaceReg: {
2008	StringRef Old = P.getOperand(K: 0).getOperandName();
2009	StringRef New = P.getOperand(K: 1).getOperandName();
2010
2011	if (!ApplyOpTable.lookup(OpName: New).Found && !MatchOpTable.lookup(OpName: New).Found)
2012	return Error("unknown operand '" + Old + "'");
2013
2014	auto &OldOM = M.getOperandMatcher(Name: Old);
2015	if (auto It = OperandToTempRegID.find(Key: New);
2016	It != OperandToTempRegID.end()) {
2017	// Replace with temp reg.
2018	M.addAction<ReplaceRegAction>(args: OldOM.getInsnVarID(), args: OldOM.getOpIdx(),
2019	args&: It->second);
2020	} else {
2021	// Replace with matched reg.
2022	auto &NewOM = M.getOperandMatcher(Name: New);
2023	M.addAction<ReplaceRegAction>(args: OldOM.getInsnVarID(), args: OldOM.getOpIdx(),
2024	args: NewOM.getInsnVarID(), args: NewOM.getOpIdx());
2025	}
2026	// checkSemantics should have ensured that we can only rewrite the root.
2027	// Ensure we're deleting it.
2028	assert(MatchOpTable.getDef(Old) == MatchRoot);
2029	return true;
2030	}
2031	}
2032
2033	llvm_unreachable("Unknown BuiltinKind!");
2034	}
2035
2036	bool isLiteralImm(const InstructionPattern &P, unsigned OpIdx) {
2037	if (const auto *CGP = dyn_cast<CodeGenInstructionPattern>(Val: &P)) {
2038	StringRef InstName = CGP->getInst().TheDef->getName();
2039	return (InstName == "G_CONSTANT" || InstName == "G_FCONSTANT") &&
2040	OpIdx == 1;
2041	}
2042
2043	llvm_unreachable("TODO");
2044	}
2045
2046	bool CombineRuleBuilder::emitCodeGenInstructionMatchPattern(
2047	CodeExpansions &CE, const PatternAlternatives &Alts, RuleMatcher &M,
2048	InstructionMatcher &IM, const CodeGenInstructionPattern &P,
2049	DenseSet<const Pattern *> &SeenPats, OperandDefLookupFn LookupOperandDef,
2050	OperandMapperFnRef OperandMapper) {
2051	auto StackTrace = PrettyStackTraceEmit(RuleDef, &P);
2052
2053	if (SeenPats.contains(V: &P))
2054	return true;
2055
2056	SeenPats.insert(V: &P);
2057
2058	IM.addPredicate<InstructionOpcodeMatcher>(args: &P.getInst());
2059	declareInstExpansion(CE, IM, Name: P.getName());
2060
2061	// If this is an intrinsic, check the intrinsic ID.
2062	if (P.isIntrinsic()) {
2063	// The IntrinsicID's operand is the first operand after the defs.
2064	OperandMatcher &OM = IM.addOperand(OpIdx: P.getNumInstDefs(), SymbolicName: "$intrinsic_id",
2065	AllocatedTemporariesBaseID: AllocatedTemporariesBaseID++);
2066	OM.addPredicate<IntrinsicIDOperandMatcher>(args: P.getIntrinsic());
2067	}
2068
2069	// Check flags if needed.
2070	if (const auto *FI = P.getMIFlagsInfo()) {
2071	assert(FI->copy_flags().empty());
2072
2073	if (const auto &SetF = FI->set_flags(); !SetF.empty())
2074	IM.addPredicate<MIFlagsInstructionPredicateMatcher>(args: SetF.getArrayRef());
2075	if (const auto &UnsetF = FI->unset_flags(); !UnsetF.empty())
2076	IM.addPredicate<MIFlagsInstructionPredicateMatcher>(args: UnsetF.getArrayRef(),
2077	/*CheckNot=*/args: true);
2078	}
2079
2080	for (auto [Idx, OriginalO] : enumerate(First: P.operands())) {
2081	// Remap the operand. This is used when emitting InstructionPatterns inside
2082	// PatFrags, so it can remap them to the arguments passed to the pattern.
2083	//
2084	// We use the remapped operand to emit immediates, and for the symbolic
2085	// operand names (in IM.addOperand). CodeExpansions and OperandTable lookups
2086	// still use the original name.
2087	//
2088	// The "def" flag on the remapped operand is always ignored.
2089	auto RemappedO = OperandMapper(OriginalO);
2090	assert(RemappedO.isNamedOperand() == OriginalO.isNamedOperand() &&
2091	"Cannot remap an unnamed operand to a named one!");
2092
2093	const auto OpName =
2094	RemappedO.isNamedOperand() ? RemappedO.getOperandName().str() : "";
2095
2096	// For intrinsics, the first use operand is the intrinsic id, so the true
2097	// operand index is shifted by 1.
2098	//
2099	// From now on:
2100	// Idx = index in the pattern operand list.
2101	// RealIdx = expected index in the MachineInstr.
2102	const unsigned RealIdx =
2103	(P.isIntrinsic() && !OriginalO.isDef()) ? (Idx + 1) : Idx;
2104	OperandMatcher &OM =
2105	IM.addOperand(OpIdx: RealIdx, SymbolicName: OpName, AllocatedTemporariesBaseID: AllocatedTemporariesBaseID++);
2106	if (!OpName.empty())
2107	declareOperandExpansion(CE, OM, Name: OriginalO.getOperandName());
2108
2109	// Handle immediates.
2110	if (RemappedO.hasImmValue()) {
2111	if (isLiteralImm(P, OpIdx: Idx))
2112	OM.addPredicate<LiteralIntOperandMatcher>(args: RemappedO.getImmValue());
2113	else
2114	OM.addPredicate<ConstantIntOperandMatcher>(args: RemappedO.getImmValue());
2115	}
2116
2117	// Handle typed operands, but only bother to check if it hasn't been done
2118	// before.
2119	//
2120	// getOperandMatcher will always return the first OM to have been created
2121	// for that Operand. "OM" here is always a new OperandMatcher.
2122	//
2123	// Always emit a check for unnamed operands.
2124	if (OpName.empty() ||
2125	!M.getOperandMatcher(Name: OpName).contains<LLTOperandMatcher>()) {
2126	if (const auto Ty = RemappedO.getType()) {
2127	// TODO: We could support GITypeOf here on the condition that the
2128	// OperandMatcher exists already. Though it's clunky to make this work
2129	// and isn't all that useful so it's just rejected in typecheckPatterns
2130	// at this time.
2131	assert(Ty.isLLT() && "Only LLTs are supported in match patterns!");
2132	OM.addPredicate<LLTOperandMatcher>(args: getLLTCodeGen(PT: Ty));
2133	}
2134	}
2135
2136	// Stop here if the operand is a def, or if it had no name.
2137	if (OriginalO.isDef() || !OriginalO.isNamedOperand())
2138	continue;
2139
2140	const auto *DefPat = LookupOperandDef(OriginalO.getOperandName());
2141	if (!DefPat)
2142	continue;
2143
2144	if (OriginalO.hasImmValue()) {
2145	assert(!OpName.empty());
2146	// This is a named immediate that also has a def, that's not okay.
2147	// e.g.
2148	// (G_SEXT $y, (i32 0))
2149	// (COPY $x, 42:$y)
2150	PrintError(Msg: "'" + OpName +
2151	"' is a named immediate, it cannot be defined by another "
2152	"instruction");
2153	PrintNote(Msg: "'" + OpName + "' is defined by '" + DefPat->getName() + "'");
2154	return false;
2155	}
2156
2157	// From here we know that the operand defines an instruction, and we need to
2158	// emit it.
2159	auto InstOpM =
2160	OM.addPredicate<InstructionOperandMatcher>(args&: M, args: DefPat->getName());
2161	if (!InstOpM) {
2162	// TODO: copy-pasted from GlobalISelEmitter.cpp. Is it still relevant
2163	// here?
2164	PrintError(Msg: "Nested instruction '" + DefPat->getName() +
2165	"' cannot be the same as another operand '" +
2166	OriginalO.getOperandName() + "'");
2167	return false;
2168	}
2169
2170	auto &IM = (*InstOpM)->getInsnMatcher();
2171	if (const auto *CGIDef = dyn_cast<CodeGenInstructionPattern>(Val: DefPat)) {
2172	if (!emitCodeGenInstructionMatchPattern(CE, Alts, M, IM, P: *CGIDef,
2173	SeenPats, LookupOperandDef,
2174	OperandMapper))
2175	return false;
2176	continue;
2177	}
2178
2179	if (const auto *PFPDef = dyn_cast<PatFragPattern>(Val: DefPat)) {
2180	if (!emitPatFragMatchPattern(CE, Alts, RM&: M, IM: &IM, PFP: *PFPDef, SeenPats))
2181	return false;
2182	continue;
2183	}
2184
2185	llvm_unreachable("unknown type of InstructionPattern");
2186	}
2187
2188	return true;
2189	}
2190
2191	//===- GICombinerEmitter --------------------------------------------------===//
2192
2193	/// Main implementation class. This emits the tablegenerated output.
2194	///
2195	/// It collects rules, uses `CombineRuleBuilder` to parse them and accumulate
2196	/// RuleMatchers, then takes all the necessary state/data from the various
2197	/// static storage pools and wires them together to emit the match table &
2198	/// associated function/data structures.
2199	class GICombinerEmitter final : public GlobalISelMatchTableExecutorEmitter {
2200	RecordKeeper &Records;
2201	StringRef Name;
2202	const CodeGenTarget &Target;
2203	Record *Combiner;
2204	unsigned NextRuleID = 0;
2205
2206	// List all combine rules (ID, name) imported.
2207	// Note that the combiner rule ID is different from the RuleMatcher ID. The
2208	// latter is internal to the MatchTable, the former is the canonical ID of the
2209	// combine rule used to disable/enable it.
2210	std::vector<std::pair<unsigned, std::string>> AllCombineRules;
2211
2212	// Keep track of all rules we've seen so far to ensure we don't process
2213	// the same rule twice.
2214	StringSet<> RulesSeen;
2215
2216	MatchTable buildMatchTable(MutableArrayRef<RuleMatcher> Rules);
2217
2218	void emitRuleConfigImpl(raw_ostream &OS);
2219
2220	void emitAdditionalImpl(raw_ostream &OS) override;
2221
2222	void emitMIPredicateFns(raw_ostream &OS) override;
2223	void emitI64ImmPredicateFns(raw_ostream &OS) override;
2224	void emitAPFloatImmPredicateFns(raw_ostream &OS) override;
2225	void emitAPIntImmPredicateFns(raw_ostream &OS) override;
2226	void emitTestSimplePredicate(raw_ostream &OS) override;
2227	void emitRunCustomAction(raw_ostream &OS) override;
2228
2229	void emitAdditionalTemporariesDecl(raw_ostream &OS,
2230	StringRef Indent) override;
2231
2232	const CodeGenTarget &getTarget() const override { return Target; }
2233	StringRef getClassName() const override {
2234	return Combiner->getValueAsString(FieldName: "Classname");
2235	}
2236
2237	StringRef getCombineAllMethodName() const {
2238	return Combiner->getValueAsString(FieldName: "CombineAllMethodName");
2239	}
2240
2241	std::string getRuleConfigClassName() const {
2242	return getClassName().str() + "RuleConfig";
2243	}
2244
2245	void gatherRules(std::vector<RuleMatcher> &Rules,
2246	const std::vector<Record *> &&RulesAndGroups);
2247
2248	public:
2249	explicit GICombinerEmitter(RecordKeeper &RK, const CodeGenTarget &Target,
2250	StringRef Name, Record *Combiner);
2251	~GICombinerEmitter() {}
2252
2253	void run(raw_ostream &OS);
2254	};
2255
2256	void GICombinerEmitter::emitRuleConfigImpl(raw_ostream &OS) {
2257	OS << "struct " << getRuleConfigClassName() << " {\n"
2258	<< " SparseBitVector<> DisabledRules;\n\n"
2259	<< " bool isRuleEnabled(unsigned RuleID) const;\n"
2260	<< " bool parseCommandLineOption();\n"
2261	<< " bool setRuleEnabled(StringRef RuleIdentifier);\n"
2262	<< " bool setRuleDisabled(StringRef RuleIdentifier);\n"
2263	<< "};\n\n";
2264
2265	std::vector<std::pair<std::string, std::string>> Cases;
2266	Cases.reserve(n: AllCombineRules.size());
2267
2268	for (const auto &[ID, Name] : AllCombineRules)
2269	Cases.emplace_back(args: Name, args: "return " + to_string(Value: ID) + ";\n");
2270
2271	OS << "static std::optional<uint64_t> getRuleIdxForIdentifier(StringRef "
2272	"RuleIdentifier) {\n"
2273	<< " uint64_t I;\n"
2274	<< " // getAtInteger(...) returns false on success\n"
2275	<< " bool Parsed = !RuleIdentifier.getAsInteger(0, I);\n"
2276	<< " if (Parsed)\n"
2277	<< " return I;\n\n"
2278	<< "#ifndef NDEBUG\n";
2279	StringMatcher Matcher("RuleIdentifier", Cases, OS);
2280	Matcher.Emit();
2281	OS << "#endif // ifndef NDEBUG\n\n"
2282	<< " return std::nullopt;\n"
2283	<< "}\n";
2284
2285	OS << "static std::optional<std::pair<uint64_t, uint64_t>> "
2286	"getRuleRangeForIdentifier(StringRef RuleIdentifier) {\n"
2287	<< " std::pair<StringRef, StringRef> RangePair = "
2288	"RuleIdentifier.split('-');\n"
2289	<< " if (!RangePair.second.empty()) {\n"
2290	<< " const auto First = "
2291	"getRuleIdxForIdentifier(RangePair.first);\n"
2292	<< " const auto Last = "
2293	"getRuleIdxForIdentifier(RangePair.second);\n"
2294	<< " if (!First || !Last)\n"
2295	<< " return std::nullopt;\n"
2296	<< " if (First >= Last)\n"
2297	<< " report_fatal_error(\"Beginning of range should be before "
2298	"end of range\");\n"
2299	<< " return {{*First, *Last + 1}};\n"
2300	<< " }\n"
2301	<< " if (RangePair.first == \"*\") {\n"
2302	<< " return {{0, " << AllCombineRules.size() << "}};\n"
2303	<< " }\n"
2304	<< " const auto I = getRuleIdxForIdentifier(RangePair.first);\n"
2305	<< " if (!I)\n"
2306	<< " return std::nullopt;\n"
2307	<< " return {{*I, *I + 1}};\n"
2308	<< "}\n\n";
2309
2310	for (bool Enabled : {true, false}) {
2311	OS << "bool " << getRuleConfigClassName() << "::setRule"
2312	<< (Enabled ? "Enabled" : "Disabled") << "(StringRef RuleIdentifier) {\n"
2313	<< " auto MaybeRange = getRuleRangeForIdentifier(RuleIdentifier);\n"
2314	<< " if (!MaybeRange)\n"
2315	<< " return false;\n"
2316	<< " for (auto I = MaybeRange->first; I < MaybeRange->second; ++I)\n"
2317	<< " DisabledRules." << (Enabled ? "reset" : "set") << "(I);\n"
2318	<< " return true;\n"
2319	<< "}\n\n";
2320	}
2321
2322	OS << "static std::vector<std::string> " << Name << "Option;\n"
2323	<< "static cl::list<std::string> " << Name << "DisableOption(\n"
2324	<< " \"" << Name.lower() << "-disable-rule\",\n"
2325	<< " cl::desc(\"Disable one or more combiner rules temporarily in "
2326	<< "the " << Name << " pass\"),\n"
2327	<< " cl::CommaSeparated,\n"
2328	<< " cl::Hidden,\n"
2329	<< " cl::cat(GICombinerOptionCategory),\n"
2330	<< " cl::callback([](const std::string &Str) {\n"
2331	<< " " << Name << "Option.push_back(Str);\n"
2332	<< " }));\n"
2333	<< "static cl::list<std::string> " << Name << "OnlyEnableOption(\n"
2334	<< " \"" << Name.lower() << "-only-enable-rule\",\n"
2335	<< " cl::desc(\"Disable all rules in the " << Name
2336	<< " pass then re-enable the specified ones\"),\n"
2337	<< " cl::Hidden,\n"
2338	<< " cl::cat(GICombinerOptionCategory),\n"
2339	<< " cl::callback([](const std::string &CommaSeparatedArg) {\n"
2340	<< " StringRef Str = CommaSeparatedArg;\n"
2341	<< " " << Name << "Option.push_back(\"*\");\n"
2342	<< " do {\n"
2343	<< " auto X = Str.split(\",\");\n"
2344	<< " " << Name << "Option.push_back((\"!\" + X.first).str());\n"
2345	<< " Str = X.second;\n"
2346	<< " } while (!Str.empty());\n"
2347	<< " }));\n"
2348	<< "\n\n"
2349	<< "bool " << getRuleConfigClassName()
2350	<< "::isRuleEnabled(unsigned RuleID) const {\n"
2351	<< " return !DisabledRules.test(RuleID);\n"
2352	<< "}\n"
2353	<< "bool " << getRuleConfigClassName() << "::parseCommandLineOption() {\n"
2354	<< " for (StringRef Identifier : " << Name << "Option) {\n"
2355	<< " bool Enabled = Identifier.consume_front(\"!\");\n"
2356	<< " if (Enabled && !setRuleEnabled(Identifier))\n"
2357	<< " return false;\n"
2358	<< " if (!Enabled && !setRuleDisabled(Identifier))\n"
2359	<< " return false;\n"
2360	<< " }\n"
2361	<< " return true;\n"
2362	<< "}\n\n";
2363	}
2364
2365	void GICombinerEmitter::emitAdditionalImpl(raw_ostream &OS) {
2366	OS << "bool " << getClassName() << "::" << getCombineAllMethodName()
2367	<< "(MachineInstr &I) const {\n"
2368	<< " const TargetSubtargetInfo &ST = MF.getSubtarget();\n"
2369	<< " const PredicateBitset AvailableFeatures = "
2370	"getAvailableFeatures();\n"
2371	<< " B.setInstrAndDebugLoc(I);\n"
2372	<< " State.MIs.clear();\n"
2373	<< " State.MIs.push_back(&I);\n"
2374	<< " " << MatchDataInfo::StructName << " = "
2375	<< MatchDataInfo::StructTypeName << "();\n\n"
2376	<< " if (executeMatchTable(*this, State, ExecInfo, B"
2377	<< ", getMatchTable(), *ST.getInstrInfo(), MRI, "
2378	"*MRI.getTargetRegisterInfo(), *ST.getRegBankInfo(), AvailableFeatures"
2379	<< ", /*CoverageInfo*/ nullptr)) {\n"
2380	<< " return true;\n"
2381	<< " }\n\n"
2382	<< " return false;\n"
2383	<< "}\n\n";
2384	}
2385
2386	void GICombinerEmitter::emitMIPredicateFns(raw_ostream &OS) {
2387	auto MatchCode = CXXPredicateCode::getAllMatchCode();
2388	emitMIPredicateFnsImpl<const CXXPredicateCode *>(
2389	OS, AdditionalDecls: "", Predicates: ArrayRef<const CXXPredicateCode *>(MatchCode),
2390	GetPredEnumName: [](const CXXPredicateCode *C) -> StringRef { return C->BaseEnumName; },
2391	GetPredCode: [](const CXXPredicateCode *C) -> StringRef { return C->Code; });
2392	}
2393
2394	void GICombinerEmitter::emitI64ImmPredicateFns(raw_ostream &OS) {
2395	// Unused, but still needs to be called.
2396	emitImmPredicateFnsImpl<unsigned>(
2397	OS, TypeIdentifier: "I64", ArgType: "int64_t", Predicates: {}, GetPredEnumName: [](unsigned) { return ""; },
2398	GetPredCode: [](unsigned) { return ""; });
2399	}
2400
2401	void GICombinerEmitter::emitAPFloatImmPredicateFns(raw_ostream &OS) {
2402	// Unused, but still needs to be called.
2403	emitImmPredicateFnsImpl<unsigned>(
2404	OS, TypeIdentifier: "APFloat", ArgType: "const APFloat &", Predicates: {}, GetPredEnumName: [](unsigned) { return ""; },
2405	GetPredCode: [](unsigned) { return ""; });
2406	}
2407
2408	void GICombinerEmitter::emitAPIntImmPredicateFns(raw_ostream &OS) {
2409	// Unused, but still needs to be called.
2410	emitImmPredicateFnsImpl<unsigned>(
2411	OS, TypeIdentifier: "APInt", ArgType: "const APInt &", Predicates: {}, GetPredEnumName: [](unsigned) { return ""; },
2412	GetPredCode: [](unsigned) { return ""; });
2413	}
2414
2415	void GICombinerEmitter::emitTestSimplePredicate(raw_ostream &OS) {
2416	if (!AllCombineRules.empty()) {
2417	OS << "enum {\n";
2418	std::string EnumeratorSeparator = " = GICXXPred_Invalid + 1,\n";
2419	// To avoid emitting a switch, we expect that all those rules are in order.
2420	// That way we can just get the RuleID from the enum by subtracting
2421	// (GICXXPred_Invalid + 1).
2422	unsigned ExpectedID = 0;
2423	(void)ExpectedID;
2424	for (const auto &ID : keys(C&: AllCombineRules)) {
2425	assert(ExpectedID++ == ID && "combine rules are not ordered!");
2426	OS << " " << getIsEnabledPredicateEnumName(CombinerRuleID: ID) << EnumeratorSeparator;
2427	EnumeratorSeparator = ",\n";
2428	}
2429	OS << "};\n\n";
2430	}
2431
2432	OS << "bool " << getClassName()
2433	<< "::testSimplePredicate(unsigned Predicate) const {\n"
2434	<< " return RuleConfig.isRuleEnabled(Predicate - "
2435	"GICXXPred_Invalid - "
2436	"1);\n"
2437	<< "}\n";
2438	}
2439
2440	void GICombinerEmitter::emitRunCustomAction(raw_ostream &OS) {
2441	const auto ApplyCode = CXXPredicateCode::getAllApplyCode();
2442
2443	if (!ApplyCode.empty()) {
2444	OS << "enum {\n";
2445	std::string EnumeratorSeparator = " = GICXXCustomAction_Invalid + 1,\n";
2446	for (const auto &Apply : ApplyCode) {
2447	OS << " " << Apply->getEnumNameWithPrefix(Prefix: CXXApplyPrefix)
2448	<< EnumeratorSeparator;
2449	EnumeratorSeparator = ",\n";
2450	}
2451	OS << "};\n";
2452	}
2453
2454	OS << "void " << getClassName()
2455	<< "::runCustomAction(unsigned ApplyID, const MatcherState &State, "
2456	"NewMIVector &OutMIs) const "
2457	"{\n";
2458	if (!ApplyCode.empty()) {
2459	OS << " switch(ApplyID) {\n";
2460	for (const auto &Apply : ApplyCode) {
2461	OS << " case " << Apply->getEnumNameWithPrefix(Prefix: CXXApplyPrefix) << ":{\n"
2462	<< " Helper.getBuilder().setInstrAndDebugLoc(*State.MIs[0]);\n"
2463	<< " " << join(R: split(Str: Apply->Code, Separator: '\n'), Separator: "\n ") << '\n'
2464	<< " return;\n";
2465	OS << " }\n";
2466	}
2467	OS << "}\n";
2468	}
2469	OS << " llvm_unreachable(\"Unknown Apply Action\");\n"
2470	<< "}\n";
2471	}
2472
2473	void GICombinerEmitter::emitAdditionalTemporariesDecl(raw_ostream &OS,
2474	StringRef Indent) {
2475	OS << Indent << "struct " << MatchDataInfo::StructTypeName << " {\n";
2476	for (const auto &[Type, VarNames] : AllMatchDataVars) {
2477	assert(!VarNames.empty() && "Cannot have no vars for this type!");
2478	OS << Indent << " " << Type << " " << join(R: VarNames, Separator: ", ") << ";\n";
2479	}
2480	OS << Indent << "};\n"
2481	<< Indent << "mutable " << MatchDataInfo::StructTypeName << " "
2482	<< MatchDataInfo::StructName << ";\n\n";
2483	}
2484
2485	GICombinerEmitter::GICombinerEmitter(RecordKeeper &RK,
2486	const CodeGenTarget &Target,
2487	StringRef Name, Record *Combiner)
2488	: Records(RK), Name(Name), Target(Target), Combiner(Combiner) {}
2489
2490	MatchTable
2491	GICombinerEmitter::buildMatchTable(MutableArrayRef<RuleMatcher> Rules) {
2492	std::vector<Matcher *> InputRules;
2493	for (Matcher &Rule : Rules)
2494	InputRules.push_back(x: &Rule);
2495
2496	unsigned CurrentOrdering = 0;
2497	StringMap<unsigned> OpcodeOrder;
2498	for (RuleMatcher &Rule : Rules) {
2499	const StringRef Opcode = Rule.getOpcode();
2500	assert(!Opcode.empty() && "Didn't expect an undefined opcode");
2501	if (OpcodeOrder.count(Key: Opcode) == 0)
2502	OpcodeOrder[Opcode] = CurrentOrdering++;
2503	}
2504
2505	llvm::stable_sort(Range&: InputRules, C: [&OpcodeOrder](const Matcher *A,
2506	const Matcher *B) {
2507	auto *L = static_cast<const RuleMatcher *>(A);
2508	auto *R = static_cast<const RuleMatcher *>(B);
2509	return std::make_tuple(args&: OpcodeOrder[L->getOpcode()], args: L->getNumOperands()) <
2510	std::make_tuple(args&: OpcodeOrder[R->getOpcode()], args: R->getNumOperands());
2511	});
2512
2513	for (Matcher *Rule : InputRules)
2514	Rule->optimize();
2515
2516	std::vector<std::unique_ptr<Matcher>> MatcherStorage;
2517	std::vector<Matcher *> OptRules =
2518	optimizeRules<GroupMatcher>(Rules: InputRules, MatcherStorage);
2519
2520	for (Matcher *Rule : OptRules)
2521	Rule->optimize();
2522
2523	OptRules = optimizeRules<SwitchMatcher>(Rules: OptRules, MatcherStorage);
2524
2525	return MatchTable::buildTable(Rules: OptRules, /*WithCoverage*/ false,
2526	/*IsCombiner*/ true);
2527	}
2528
2529	/// Recurse into GICombineGroup's and flatten the ruleset into a simple list.
2530	void GICombinerEmitter::gatherRules(
2531	std::vector<RuleMatcher> &ActiveRules,
2532	const std::vector<Record *> &&RulesAndGroups) {
2533	for (Record *Rec : RulesAndGroups) {
2534	if (!Rec->isValueUnset(FieldName: "Rules")) {
2535	gatherRules(ActiveRules, RulesAndGroups: Rec->getValueAsListOfDefs(FieldName: "Rules"));
2536	continue;
2537	}
2538
2539	StringRef RuleName = Rec->getName();
2540	if (!RulesSeen.insert(key: RuleName).second) {
2541	PrintWarning(WarningLoc: Rec->getLoc(),
2542	Msg: "skipping rule '" + Rec->getName() +
2543	"' because it has already been processed");
2544	continue;
2545	}
2546
2547	AllCombineRules.emplace_back(args&: NextRuleID, args: Rec->getName().str());
2548	CombineRuleBuilder CRB(Target, SubtargetFeatures, *Rec, NextRuleID++,
2549	ActiveRules);
2550
2551	if (!CRB.parseAll()) {
2552	assert(ErrorsPrinted && "Parsing failed without errors!");
2553	continue;
2554	}
2555
2556	if (StopAfterParse) {
2557	CRB.print(OS&: outs());
2558	continue;
2559	}
2560
2561	if (!CRB.emitRuleMatchers()) {
2562	assert(ErrorsPrinted && "Emission failed without errors!");
2563	continue;
2564	}
2565	}
2566	}
2567
2568	void GICombinerEmitter::run(raw_ostream &OS) {
2569	InstructionOpcodeMatcher::initOpcodeValuesMap(Target);
2570	LLTOperandMatcher::initTypeIDValuesMap();
2571
2572	Records.startTimer(Name: "Gather rules");
2573	std::vector<RuleMatcher> Rules;
2574	gatherRules(ActiveRules&: Rules, RulesAndGroups: Combiner->getValueAsListOfDefs(FieldName: "Rules"));
2575	if (ErrorsPrinted)
2576	PrintFatalError(ErrorLoc: Combiner->getLoc(), Msg: "Failed to parse one or more rules");
2577
2578	if (StopAfterParse)
2579	return;
2580
2581	Records.startTimer(Name: "Creating Match Table");
2582	unsigned MaxTemporaries = 0;
2583	for (const auto &Rule : Rules)
2584	MaxTemporaries = std::max(a: MaxTemporaries, b: Rule.countRendererFns());
2585
2586	llvm::stable_sort(Range&: Rules, C: [&](const RuleMatcher &A, const RuleMatcher &B) {
2587	if (A.isHigherPriorityThan(B)) {
2588	assert(!B.isHigherPriorityThan(A) && "Cannot be more important "
2589	"and less important at "
2590	"the same time");
2591	return true;
2592	}
2593	return false;
2594	});
2595
2596	const MatchTable Table = buildMatchTable(Rules);
2597
2598	Records.startTimer(Name: "Emit combiner");
2599
2600	emitSourceFileHeader(Desc: getClassName().str() + " Combiner Match Table", OS);
2601
2602	// Unused
2603	std::vector<StringRef> CustomRendererFns;
2604	// Unused
2605	std::vector<Record *> ComplexPredicates;
2606
2607	SmallVector<LLTCodeGen, 16> TypeObjects;
2608	append_range(C&: TypeObjects, R&: KnownTypes);
2609	llvm::sort(C&: TypeObjects);
2610
2611	// Hack: Avoid empty declarator.
2612	if (TypeObjects.empty())
2613	TypeObjects.push_back(Elt: LLT::scalar(SizeInBits: 1));
2614
2615	// GET_GICOMBINER_DEPS, which pulls in extra dependencies.
2616	OS << "#ifdef GET_GICOMBINER_DEPS\n"
2617	<< "#include \"llvm/ADT/SparseBitVector.h\"\n"
2618	<< "namespace llvm {\n"
2619	<< "extern cl::OptionCategory GICombinerOptionCategory;\n"
2620	<< "} // end namespace llvm\n"
2621	<< "#endif // ifdef GET_GICOMBINER_DEPS\n\n";
2622
2623	// GET_GICOMBINER_TYPES, which needs to be included before the declaration of
2624	// the class.
2625	OS << "#ifdef GET_GICOMBINER_TYPES\n";
2626	emitRuleConfigImpl(OS);
2627	OS << "#endif // ifdef GET_GICOMBINER_TYPES\n\n";
2628	emitPredicateBitset(OS, IfDefName: "GET_GICOMBINER_TYPES");
2629
2630	// GET_GICOMBINER_CLASS_MEMBERS, which need to be included inside the class.
2631	emitPredicatesDecl(OS, IfDefName: "GET_GICOMBINER_CLASS_MEMBERS");
2632	emitTemporariesDecl(OS, IfDefName: "GET_GICOMBINER_CLASS_MEMBERS");
2633
2634	// GET_GICOMBINER_IMPL, which needs to be included outside the class.
2635	emitExecutorImpl(OS, Table, TypeObjects, Rules, ComplexOperandMatchers: ComplexPredicates,
2636	CustomOperandRenderers: CustomRendererFns, IfDefName: "GET_GICOMBINER_IMPL");
2637
2638	// GET_GICOMBINER_CONSTRUCTOR_INITS, which are in the constructor's
2639	// initializer list.
2640	emitPredicatesInit(OS, IfDefName: "GET_GICOMBINER_CONSTRUCTOR_INITS");
2641	emitTemporariesInit(OS, MaxTemporaries, IfDefName: "GET_GICOMBINER_CONSTRUCTOR_INITS");
2642	}
2643
2644	} // end anonymous namespace
2645
2646	//===----------------------------------------------------------------------===//
2647
2648	static void EmitGICombiner(RecordKeeper &RK, raw_ostream &OS) {
2649	EnablePrettyStackTrace();
2650	CodeGenTarget Target(RK);
2651
2652	if (SelectedCombiners.empty())
2653	PrintFatalError(Msg: "No combiners selected with -combiners");
2654	for (const auto &Combiner : SelectedCombiners) {
2655	Record *CombinerDef = RK.getDef(Name: Combiner);
2656	if (!CombinerDef)
2657	PrintFatalError(Msg: "Could not find " + Combiner);
2658	GICombinerEmitter(RK, Target, Combiner, CombinerDef).run(OS);
2659	}
2660	}
2661
2662	static TableGen::Emitter::Opt X("gen-global-isel-combiner", EmitGICombiner,
2663	"Generate GlobalISel Combiner");
2664