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