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 // GIHasOneUse is a match-only predicate and cannot appear in 'apply'.
1041 if (const auto *BP = dyn_cast<BuiltinPattern>(Val: Pat.get())) {
1042 if (BP->getBuiltinKind() == BI_HasOneUse) {
1043 PrintError(Msg: "'" + BP->getInstName() +
1044 "' cannot be used in a 'apply' pattern");
1045 return false;
1046 }
1047 }
1048
1049 if (auto *CXXPat = dyn_cast<CXXPattern>(Val: Pat.get()))
1050 CXXPat->setIsApply();
1051
1052 ApplyPats[Name] = std::move(Pat);
1053 return true;
1054}
1055
1056bool CombineRuleBuilder::addMatchPattern(std::unique_ptr<Pattern> Pat) {
1057 StringRef Name = Pat->getName();
1058 if (MatchPats.contains(Key: Name)) {
1059 PrintError(Msg: "'" + Name + "' match pattern defined more than once!");
1060 return false;
1061 }
1062
1063 // Most builtins cannot appear in 'match', except GIHasOneUse.
1064 if (const auto *BP = dyn_cast<BuiltinPattern>(Val: Pat.get())) {
1065 if (BP->getBuiltinKind() != BI_HasOneUse) {
1066 PrintError(Msg: "'" + BP->getInstName() +
1067 "' cannot be used in a 'match' pattern");
1068 return false;
1069 }
1070 }
1071
1072 MatchPats[Name] = std::move(Pat);
1073 return true;
1074}
1075
1076void CombineRuleBuilder::declareAllMatchDatasExpansions(
1077 CodeExpansions &CE) const {
1078 for (const auto &MD : MatchDatas)
1079 CE.declare(Name: MD.Symbol, Expansion: MD.getVarName());
1080}
1081
1082void CombineRuleBuilder::addCXXPredicate(RuleMatcher &M,
1083 const CodeExpansions &CE,
1084 const CXXPattern &P,
1085 const PatternAlternatives &Alts) {
1086 auto Loc = RuleDef.getLoc();
1087 const auto AddComment = [&](raw_ostream &OS) {
1088 OS << "// Pattern Alternatives: ";
1089 print(OS, Alts);
1090 OS << '\n';
1091 };
1092 const auto &ExpandedCode =
1093 DebugCXXPreds ? P.expandCode(CE, Locs: Loc, AddComment) : P.expandCode(CE, Locs: Loc);
1094 // FIXME?: This isn't too clean, the pred does not belong to that instruction.
1095 // It works because GenericInstructionPredicateMatcher will never be hoisted.
1096 // Ideally the RuleMatcher should have a separate container for this type of
1097 // situation (perhaps we can reuse EpilogueMatcher), but it's not a big deal
1098 // right now.
1099 InstructionMatcher &IM = M.roots_front();
1100 IM.addPredicate<GenericInstructionPredicateMatcher>(
1101 args: ExpandedCode.getEnumNameWithPrefix(Prefix: CXXPredPrefix));
1102}
1103
1104bool CombineRuleBuilder::hasOnlyCXXApplyPatterns() const {
1105 return all_of(Range: ApplyPats, P: [&](auto &Entry) {
1106 return isa<CXXPattern>(Entry.second.get());
1107 });
1108}
1109
1110bool CombineRuleBuilder::hasEraseRoot() const {
1111 return any_of(Range: ApplyPats, P: [&](auto &Entry) {
1112 if (const auto *BP = dyn_cast<BuiltinPattern>(Entry.second.get()))
1113 return BP->getBuiltinKind() == BI_EraseRoot;
1114 return false;
1115 });
1116}
1117
1118bool CombineRuleBuilder::typecheckPatterns() {
1119 CombineRuleOperandTypeChecker OTC(RuleDef, MatchOpTable);
1120
1121 for (auto &Pat : values(C&: MatchPats)) {
1122 if (auto *IP = dyn_cast<InstructionPattern>(Val: Pat.get())) {
1123 if (!OTC.processMatchPattern(P&: *IP))
1124 return false;
1125 }
1126 }
1127
1128 for (auto &Pat : values(C&: ApplyPats)) {
1129 if (auto *IP = dyn_cast<InstructionPattern>(Val: Pat.get())) {
1130 if (!OTC.processApplyPattern(P&: *IP))
1131 return false;
1132 }
1133 }
1134
1135 OTC.propagateAndInferTypes();
1136
1137 // Always check this after in case inference adds some special types to the
1138 // match patterns.
1139 for (auto &Pat : values(C&: MatchPats)) {
1140 if (auto *IP = dyn_cast<InstructionPattern>(Val: Pat.get())) {
1141 bool HasDiag = false;
1142 for (const auto &[Idx, Op] : enumerate(First&: IP->operands())) {
1143 if (Op.getType().isTypeOf()) {
1144 PrintError(Msg: PatternType::TypeOfClassName +
1145 " is not supported in 'match' patterns");
1146 PrintNote(Msg: "operand " + Twine(Idx) + " of '" + IP->getName() +
1147 "' has type '" + Op.getType().str() + "'");
1148 HasDiag = true;
1149 }
1150 }
1151 if (HasDiag)
1152 return false;
1153 }
1154 }
1155 return true;
1156}
1157
1158bool CombineRuleBuilder::buildPermutationsToEmit() {
1159 PermutationsToEmit.clear();
1160
1161 // Start with one empty set of alternatives.
1162 PermutationsToEmit.emplace_back();
1163 for (const auto &Pat : values(C&: MatchPats)) {
1164 unsigned NumAlts = 0;
1165 // Note: technically, AnyOpcodePattern also needs permutations, but:
1166 // - We only allow a single one of them in the root.
1167 // - They cannot be mixed with any other pattern other than C++ code.
1168 // So we don't really need to take them into account here. We could, but
1169 // that pattern is a hack anyway and the less it's involved, the better.
1170 if (const auto *PFP = dyn_cast<PatFragPattern>(Val: Pat.get()))
1171 NumAlts = PFP->getPatFrag().num_alternatives();
1172 else
1173 continue;
1174
1175 // For each pattern that needs permutations, multiply the current set of
1176 // alternatives.
1177 auto CurPerms = PermutationsToEmit;
1178 PermutationsToEmit.clear();
1179
1180 for (const auto &Perm : CurPerms) {
1181 assert(!Perm.contains(Pat.get()) && "Pattern already emitted?");
1182 for (unsigned K = 0; K < NumAlts; ++K) {
1183 PatternAlternatives NewPerm = Perm;
1184 NewPerm[Pat.get()] = K;
1185 PermutationsToEmit.emplace_back(Args: std::move(NewPerm));
1186 }
1187 }
1188 }
1189
1190 if (int64_t MaxPerms = RuleDef.getValueAsInt(FieldName: "MaxPermutations");
1191 MaxPerms > 0) {
1192 if ((int64_t)PermutationsToEmit.size() > MaxPerms) {
1193 PrintError(Msg: "cannot emit rule '" + RuleDef.getName() + "'; " +
1194 Twine(PermutationsToEmit.size()) +
1195 " permutations would be emitted, but the max is " +
1196 Twine(MaxPerms));
1197 return false;
1198 }
1199 }
1200
1201 // Ensure we always have a single empty entry, it simplifies the emission
1202 // logic so it doesn't need to handle the case where there are no perms.
1203 if (PermutationsToEmit.empty()) {
1204 PermutationsToEmit.emplace_back();
1205 return true;
1206 }
1207
1208 return true;
1209}
1210
1211bool CombineRuleBuilder::checkSemantics() {
1212 assert(MatchRoot && "Cannot call this before findRoots()");
1213
1214 const auto CheckVariadicOperands = [&](const InstructionPattern &IP,
1215 bool IsMatch) {
1216 bool HasVariadic = false;
1217 for (auto &Op : IP.operands()) {
1218 if (!Op.getType().isVariadicPack())
1219 continue;
1220
1221 HasVariadic = true;
1222
1223 if (IsMatch && &Op != &IP.operands_back()) {
1224 PrintError(Msg: "'" + IP.getInstName() +
1225 "': " + PatternType::VariadicClassName +
1226 " can only be used on the last operand");
1227 return false;
1228 }
1229
1230 if (Op.isDef()) {
1231 PrintError(Msg: "'" + IP.getInstName() + "': " +
1232 PatternType::VariadicClassName + " cannot be used on defs");
1233 return false;
1234 }
1235 }
1236
1237 if (HasVariadic && !IP.isVariadic()) {
1238 PrintError(Msg: "cannot use a " + PatternType::VariadicClassName +
1239 " operand on non-variadic instruction '" + IP.getInstName() +
1240 "'");
1241 return false;
1242 }
1243
1244 return true;
1245 };
1246
1247 bool UsesWipMatchOpcode = false;
1248 for (const auto &Match : MatchPats) {
1249 const auto *Pat = Match.second.get();
1250
1251 if (const auto *CXXPat = dyn_cast<CXXPattern>(Val: Pat)) {
1252 if (!CXXPat->getRawCode().contains(Other: "return "))
1253 PrintWarning(Msg: "'match' C++ code does not seem to return!");
1254 continue;
1255 }
1256
1257 if (const auto IP = dyn_cast<InstructionPattern>(Val: Pat)) {
1258 if (!CheckVariadicOperands(*IP, /*IsMatch=*/true))
1259 return false;
1260
1261 // MIFlags in match cannot use the following syntax: (MIFlags $mi)
1262 if (const auto *CGP = dyn_cast<CodeGenInstructionPattern>(Val: Pat)) {
1263 if (auto *FI = CGP->getMIFlagsInfo()) {
1264 if (!FI->copy_flags().empty()) {
1265 PrintError(Msg: "'match' patterns cannot refer to flags from other "
1266 "instructions");
1267 PrintNote(Msg: "MIFlags in '" + CGP->getName() +
1268 "' refer to: " + join(R: FI->copy_flags(), Separator: ", "));
1269 return false;
1270 }
1271 }
1272 }
1273 continue;
1274 }
1275
1276 const auto *AOP = dyn_cast<AnyOpcodePattern>(Val: Pat);
1277 if (!AOP)
1278 continue;
1279
1280 if (UsesWipMatchOpcode) {
1281 PrintError(Msg: "wip_opcode_match can only be present once");
1282 return false;
1283 }
1284
1285 UsesWipMatchOpcode = true;
1286 }
1287
1288 std::optional<bool> IsUsingCXXPatterns;
1289 for (const auto &Apply : ApplyPats) {
1290 Pattern *Pat = Apply.second.get();
1291 if (IsUsingCXXPatterns) {
1292 if (*IsUsingCXXPatterns != isa<CXXPattern>(Val: Pat)) {
1293 PrintError(Msg: "'apply' patterns cannot mix C++ code with other types of "
1294 "patterns");
1295 return false;
1296 }
1297 } else {
1298 IsUsingCXXPatterns = isa<CXXPattern>(Val: Pat);
1299 }
1300
1301 assert(Pat);
1302 const auto *IP = dyn_cast<InstructionPattern>(Val: Pat);
1303 if (!IP)
1304 continue;
1305
1306 if (!CheckVariadicOperands(*IP, /*IsMatch=*/false))
1307 return false;
1308
1309 if (UsesWipMatchOpcode) {
1310 PrintError(Msg: "cannot use wip_match_opcode in combination with apply "
1311 "instruction patterns!");
1312 return false;
1313 }
1314
1315 // Check that the insts mentioned in copy_flags exist.
1316 if (const auto *CGP = dyn_cast<CodeGenInstructionPattern>(Val: IP)) {
1317 if (auto *FI = CGP->getMIFlagsInfo()) {
1318 for (auto InstName : FI->copy_flags()) {
1319 auto It = MatchPats.find(Key: InstName);
1320 if (It == MatchPats.end()) {
1321 PrintError(Msg: "unknown instruction '$" + InstName +
1322 "' referenced in MIFlags of '" + CGP->getName() + "'");
1323 return false;
1324 }
1325
1326 if (!isa<CodeGenInstructionPattern>(Val: It->second.get())) {
1327 PrintError(
1328 Msg: "'$" + InstName +
1329 "' does not refer to a CodeGenInstruction in MIFlags of '" +
1330 CGP->getName() + "'");
1331 return false;
1332 }
1333 }
1334 }
1335 }
1336
1337 const auto *BIP = dyn_cast<BuiltinPattern>(Val: IP);
1338 if (!BIP)
1339 continue;
1340 StringRef Name = BIP->getInstName();
1341
1342 // (GIEraseInst) has to be the only apply pattern, or it can not be used at
1343 // all. The root cannot have any defs either.
1344 switch (BIP->getBuiltinKind()) {
1345 case BI_EraseRoot: {
1346 if (ApplyPats.size() > 1) {
1347 PrintError(Msg: Name + " must be the only 'apply' pattern");
1348 return false;
1349 }
1350
1351 const auto *IRoot = dyn_cast<CodeGenInstructionPattern>(Val: MatchRoot);
1352 if (!IRoot) {
1353 PrintError(Msg: Name + " can only be used if the root is a "
1354 "CodeGenInstruction or Intrinsic");
1355 return false;
1356 }
1357
1358 if (IRoot->getNumInstDefs() != 0) {
1359 PrintError(Msg: Name + " can only be used if on roots that do "
1360 "not have any output operand");
1361 PrintNote(Msg: "'" + IRoot->getInstName() + "' has " +
1362 Twine(IRoot->getNumInstDefs()) + " output operands");
1363 return false;
1364 }
1365 break;
1366 }
1367 case BI_ReplaceReg: {
1368 // (GIReplaceReg can only be used on the root instruction)
1369 // TODO: When we allow rewriting non-root instructions, also allow this.
1370 StringRef OldRegName = BIP->getOperand(K: 0).getOperandName();
1371 auto *Def = MatchOpTable.getDef(OpName: OldRegName);
1372 if (!Def) {
1373 PrintError(Msg: Name + " cannot find a matched pattern that defines '" +
1374 OldRegName + "'");
1375 return false;
1376 }
1377 if (MatchOpTable.getDef(OpName: OldRegName) != MatchRoot) {
1378 PrintError(Msg: Name + " cannot replace '" + OldRegName +
1379 "': this builtin can only replace a register defined by the "
1380 "match root");
1381 return false;
1382 }
1383 break;
1384 }
1385 case BI_HasOneUse:
1386 // GIHasOneUse is a match-only predicate, not valid in apply patterns.
1387 break;
1388 }
1389 }
1390
1391 // TODO: Diagnose uses of MatchDatas if the Rule doesn't have C++ on both the
1392 // match and apply. It's useless in such cases.
1393 if (!hasOnlyCXXApplyPatterns() && !MatchDatas.empty()) {
1394 PrintError(Msg: MatchDataClassName +
1395 " can only be used if 'apply' in entirely written in C++");
1396 return false;
1397 }
1398
1399 return true;
1400}
1401
1402RuleMatcher &CombineRuleBuilder::addRuleMatcher(const PatternAlternatives &Alts,
1403 Twine AdditionalComment) {
1404 // C++ predicates in the combiner are much more flexible and do not depend on
1405 // RecordNamedOperandMatcher. The drawback of this is that we need to assume
1406 // any operand can be used by any C++ predicate, limiting optimizations in
1407 // some cases.
1408 auto &RM =
1409 OutRMs.emplace_back(args: RuleDef.getLoc(), /*UsesRecordOperands=*/args: false);
1410 addFeaturePredicates(M&: RM);
1411 RM.setPermanentGISelFlags(GISF_IgnoreCopies);
1412 RM.addRequiredSimplePredicate(PredName: getIsEnabledPredicateEnumName(CombinerRuleID: RuleID));
1413
1414 std::string Comment;
1415 raw_string_ostream CommentOS(Comment);
1416 CommentOS << "Combiner Rule #" << RuleID << ": " << RuleDef.getName();
1417 if (!Alts.empty()) {
1418 CommentOS << " @ ";
1419 print(OS&: CommentOS, Alts);
1420 }
1421 if (!AdditionalComment.isTriviallyEmpty())
1422 CommentOS << "; " << AdditionalComment;
1423 RM.addAction<DebugCommentAction>(args&: Comment);
1424 return RM;
1425}
1426
1427bool CombineRuleBuilder::addFeaturePredicates(RuleMatcher &M) {
1428 if (!RuleDef.getValue(Name: "Predicates"))
1429 return true;
1430
1431 const ListInit *Preds = RuleDef.getValueAsListInit(FieldName: "Predicates");
1432 for (const Init *PI : Preds->getElements()) {
1433 const DefInit *Pred = dyn_cast<DefInit>(Val: PI);
1434 if (!Pred)
1435 continue;
1436
1437 const Record *Def = Pred->getDef();
1438 if (!Def->isSubClassOf(Name: "Predicate")) {
1439 ::PrintError(Rec: Def, Msg: "Unknown 'Predicate' Type");
1440 return false;
1441 }
1442
1443 if (Def->getValueAsString(FieldName: "CondString").empty())
1444 continue;
1445
1446 if (SubtargetFeatures.count(x: Def) == 0) {
1447 SubtargetFeatures.emplace(
1448 args&: Def, args: SubtargetFeatureInfo(Def, SubtargetFeatures.size()));
1449 }
1450
1451 M.addRequiredFeature(Feature: Def);
1452 }
1453
1454 return true;
1455}
1456
1457bool CombineRuleBuilder::findRoots() {
1458 const auto Finish = [&]() {
1459 assert(MatchRoot);
1460
1461 if (hasOnlyCXXApplyPatterns() || hasEraseRoot())
1462 return true;
1463
1464 auto *IPRoot = dyn_cast<InstructionPattern>(Val: MatchRoot);
1465 if (!IPRoot)
1466 return true;
1467
1468 if (IPRoot->getNumInstDefs() == 0) {
1469 // No defs to work with -> find the root using the pattern name.
1470 auto It = ApplyPats.find(Key: RootName);
1471 if (It == ApplyPats.end()) {
1472 PrintError(Msg: "Cannot find root '" + RootName + "' in apply patterns!");
1473 return false;
1474 }
1475
1476 auto *ApplyRoot = dyn_cast<InstructionPattern>(Val: It->second.get());
1477 if (!ApplyRoot) {
1478 PrintError(Msg: "apply pattern root '" + RootName +
1479 "' must be an instruction pattern");
1480 return false;
1481 }
1482
1483 ApplyRoots.insert(V: ApplyRoot);
1484 return true;
1485 }
1486
1487 // Collect all redefinitions of the MatchRoot's defs and put them in
1488 // ApplyRoots.
1489 const auto DefsNeeded = IPRoot->getApplyDefsNeeded();
1490 for (auto &Op : DefsNeeded) {
1491 assert(Op.isDef() && Op.isNamedOperand());
1492 StringRef Name = Op.getOperandName();
1493
1494 auto *ApplyRedef = ApplyOpTable.getDef(OpName: Name);
1495 if (!ApplyRedef) {
1496 PrintError(Msg: "'" + Name + "' must be redefined in the 'apply' pattern");
1497 return false;
1498 }
1499
1500 ApplyRoots.insert(V: (InstructionPattern *)ApplyRedef);
1501 }
1502
1503 if (auto It = ApplyPats.find(Key: RootName); It != ApplyPats.end()) {
1504 if (find(Range&: ApplyRoots, Val: It->second.get()) == ApplyRoots.end()) {
1505 PrintError(Msg: "apply pattern '" + RootName +
1506 "' is supposed to be a root but it does not redefine any of "
1507 "the defs of the match root");
1508 return false;
1509 }
1510 }
1511
1512 return true;
1513 };
1514
1515 // Look by pattern name, e.g.
1516 // (G_FNEG $x, $y):$root
1517 if (auto MatchPatIt = MatchPats.find(Key: RootName);
1518 MatchPatIt != MatchPats.end()) {
1519 MatchRoot = MatchPatIt->second.get();
1520 return Finish();
1521 }
1522
1523 // Look by def:
1524 // (G_FNEG $root, $y)
1525 auto LookupRes = MatchOpTable.lookup(OpName: RootName);
1526 if (!LookupRes.Found) {
1527 PrintError(Msg: "Cannot find root '" + RootName + "' in match patterns!");
1528 return false;
1529 }
1530
1531 MatchRoot = LookupRes.Def;
1532 if (!MatchRoot) {
1533 PrintError(Msg: "Cannot use live-in operand '" + RootName +
1534 "' as match pattern root!");
1535 return false;
1536 }
1537
1538 return Finish();
1539}
1540
1541bool CombineRuleBuilder::buildRuleOperandsTable() {
1542 const auto DiagnoseRedefMatch = [&](StringRef OpName) {
1543 PrintError(Msg: "Operand '" + OpName +
1544 "' is defined multiple times in the 'match' patterns");
1545 };
1546
1547 const auto DiagnoseRedefApply = [&](StringRef OpName) {
1548 PrintError(Msg: "Operand '" + OpName +
1549 "' is defined multiple times in the 'apply' patterns");
1550 };
1551
1552 for (auto &Pat : values(C&: MatchPats)) {
1553 auto *IP = dyn_cast<InstructionPattern>(Val: Pat.get());
1554 if (IP && !MatchOpTable.addPattern(P: IP, DiagnoseRedef: DiagnoseRedefMatch))
1555 return false;
1556 }
1557
1558 for (auto &Pat : values(C&: ApplyPats)) {
1559 auto *IP = dyn_cast<InstructionPattern>(Val: Pat.get());
1560 if (IP && !ApplyOpTable.addPattern(P: IP, DiagnoseRedef: DiagnoseRedefApply))
1561 return false;
1562 }
1563
1564 return true;
1565}
1566
1567bool CombineRuleBuilder::parseDefs(const DagInit &Def) {
1568 if (Def.getOperatorAsDef(Loc: RuleDef.getLoc())->getName() != "defs") {
1569 PrintError(Msg: "Expected defs operator");
1570 return false;
1571 }
1572
1573 SmallVector<StringRef> Roots;
1574 for (unsigned I = 0, E = Def.getNumArgs(); I < E; ++I) {
1575 if (isSpecificDef(N: *Def.getArg(Num: I), Def: "root")) {
1576 Roots.emplace_back(Args: Def.getArgNameStr(Num: I));
1577 continue;
1578 }
1579
1580 // Subclasses of GIDefMatchData should declare that this rule needs to pass
1581 // data from the match stage to the apply stage, and ensure that the
1582 // generated matcher has a suitable variable for it to do so.
1583 if (const Record *MatchDataRec =
1584 getDefOfSubClass(N: *Def.getArg(Num: I), Cls: MatchDataClassName)) {
1585 MatchDatas.emplace_back(Args: Def.getArgNameStr(Num: I),
1586 Args: MatchDataRec->getValueAsString(FieldName: "Type"));
1587 continue;
1588 }
1589
1590 // Otherwise emit an appropriate error message.
1591 if (getDefOfSubClass(N: *Def.getArg(Num: I), Cls: "GIDefKind"))
1592 PrintError(Msg: "This GIDefKind not implemented in tablegen");
1593 else if (getDefOfSubClass(N: *Def.getArg(Num: I), Cls: "GIDefKindWithArgs"))
1594 PrintError(Msg: "This GIDefKindWithArgs not implemented in tablegen");
1595 else
1596 PrintError(Msg: "Expected a subclass of GIDefKind or a sub-dag whose "
1597 "operator is of type GIDefKindWithArgs");
1598 return false;
1599 }
1600
1601 if (Roots.size() != 1) {
1602 PrintError(Msg: "Combine rules must have exactly one root");
1603 return false;
1604 }
1605
1606 RootName = Roots.front();
1607 return true;
1608}
1609
1610bool CombineRuleBuilder::emitMatchPattern(CodeExpansions &CE,
1611 const PatternAlternatives &Alts,
1612 const InstructionPattern &IP) {
1613 auto StackTrace = PrettyStackTraceEmit(RuleDef, &IP);
1614
1615 auto &M = addRuleMatcher(Alts);
1616 InstructionMatcher &IM = M.addInstructionMatcher(SymbolicName: IP.getName());
1617 declareInstExpansion(CE, IM, Name: IP.getName());
1618
1619 DenseSet<const Pattern *> SeenPats;
1620
1621 const auto FindOperandDef = [&](StringRef Op) -> InstructionPattern * {
1622 return MatchOpTable.getDef(OpName: Op);
1623 };
1624
1625 if (const auto *CGP = dyn_cast<CodeGenInstructionPattern>(Val: &IP)) {
1626 if (!emitCodeGenInstructionMatchPattern(CE, Alts, M, IM, P: *CGP, SeenPats,
1627 LookupOperandDef: FindOperandDef))
1628 return false;
1629 } else if (const auto *PFP = dyn_cast<PatFragPattern>(Val: &IP)) {
1630 if (!PFP->getPatFrag().canBeMatchRoot()) {
1631 PrintError(Msg: "cannot use '" + PFP->getInstName() + " as match root");
1632 return false;
1633 }
1634
1635 if (!emitPatFragMatchPattern(CE, Alts, RM&: M, IM: &IM, PFP: *PFP, SeenPats))
1636 return false;
1637 } else if (const auto *BP = dyn_cast<BuiltinPattern>(Val: &IP)) {
1638 if (BP->getBuiltinKind() == BI_HasOneUse) {
1639 IM.addPredicate<OneUsePredicateMatcher>();
1640 } else {
1641 llvm_unreachable("No match builtins known!");
1642 }
1643 } else {
1644 llvm_unreachable("Unknown kind of InstructionPattern!");
1645 }
1646
1647 // Emit remaining patterns
1648 const bool IsUsingCustomCXXAction = hasOnlyCXXApplyPatterns();
1649 SmallVector<CXXPattern *, 2> CXXMatchers;
1650 for (auto &Pat : values(C&: MatchPats)) {
1651 if (SeenPats.contains(V: Pat.get()))
1652 continue;
1653
1654 switch (Pat->getKind()) {
1655 case Pattern::K_AnyOpcode:
1656 PrintError(Msg: "wip_match_opcode can not be used with instruction patterns!");
1657 return false;
1658 case Pattern::K_PatFrag: {
1659 if (!emitPatFragMatchPattern(CE, Alts, RM&: M, /*IM*/ nullptr,
1660 PFP: *cast<PatFragPattern>(Val: Pat.get()), SeenPats))
1661 return false;
1662 continue;
1663 }
1664 case Pattern::K_Builtin: {
1665 const auto *BP = cast<BuiltinPattern>(Val: Pat.get());
1666 if (BP->getBuiltinKind() == BI_HasOneUse) {
1667 assert(BP->getNumInstOperands() == 1 && "GIHasOneUse takes 1 operand");
1668 StringRef OpName = BP->getOperand(K: 0).getOperandName();
1669 const auto *DefPat = MatchOpTable.getDef(OpName);
1670 if (!DefPat) {
1671 PrintError(Msg: "GIHasOneUse: operand '" + OpName + "' not defined");
1672 return false;
1673 }
1674 auto &InsnMatcher = M.getInstructionMatcher(SymbolicName: DefPat->getName());
1675 InsnMatcher.addPredicate<OneUsePredicateMatcher>();
1676 continue;
1677 }
1678 PrintError(Msg: "No known match builtins");
1679 return false;
1680 }
1681 case Pattern::K_CodeGenInstruction:
1682 cast<InstructionPattern>(Val: Pat.get())->reportUnreachable(Locs: RuleDef.getLoc());
1683 return false;
1684 case Pattern::K_CXX: {
1685 // Delay emission for top-level C++ matchers (which can use MatchDatas).
1686 if (IsUsingCustomCXXAction)
1687 CXXMatchers.push_back(Elt: cast<CXXPattern>(Val: Pat.get()));
1688 else
1689 addCXXPredicate(M, CE, P: *cast<CXXPattern>(Val: Pat.get()), Alts);
1690 continue;
1691 }
1692 default:
1693 llvm_unreachable("unknown pattern kind!");
1694 }
1695 }
1696
1697 return IsUsingCustomCXXAction ? emitCXXMatchApply(CE, M, Matchers: CXXMatchers)
1698 : emitApplyPatterns(CE, M);
1699}
1700
1701bool CombineRuleBuilder::emitMatchPattern(CodeExpansions &CE,
1702 const PatternAlternatives &Alts,
1703 const AnyOpcodePattern &AOP) {
1704 auto StackTrace = PrettyStackTraceEmit(RuleDef, &AOP);
1705
1706 const bool IsUsingCustomCXXAction = hasOnlyCXXApplyPatterns();
1707 for (const CodeGenInstruction *CGI : AOP.insts()) {
1708 auto &M = addRuleMatcher(Alts, AdditionalComment: "wip_match_opcode '" + CGI->getName() + "'");
1709
1710 InstructionMatcher &IM = M.addInstructionMatcher(SymbolicName: AOP.getName());
1711 declareInstExpansion(CE, IM, Name: AOP.getName());
1712 // declareInstExpansion needs to be identical, otherwise we need to create a
1713 // CodeExpansions object here instead.
1714 assert(IM.getInsnVarID() == 0);
1715
1716 IM.addPredicate<InstructionOpcodeMatcher>(args&: CGI);
1717
1718 // Emit remaining patterns.
1719 SmallVector<CXXPattern *, 2> CXXMatchers;
1720 for (auto &Pat : values(C&: MatchPats)) {
1721 if (Pat.get() == &AOP)
1722 continue;
1723
1724 switch (Pat->getKind()) {
1725 case Pattern::K_AnyOpcode:
1726 PrintError(Msg: "wip_match_opcode can only be present once!");
1727 return false;
1728 case Pattern::K_PatFrag: {
1729 DenseSet<const Pattern *> SeenPats;
1730 if (!emitPatFragMatchPattern(CE, Alts, RM&: M, /*IM*/ nullptr,
1731 PFP: *cast<PatFragPattern>(Val: Pat.get()),
1732 SeenPats))
1733 return false;
1734 continue;
1735 }
1736 case Pattern::K_CodeGenInstruction:
1737 cast<InstructionPattern>(Val: Pat.get())->reportUnreachable(
1738 Locs: RuleDef.getLoc());
1739 return false;
1740 case Pattern::K_CXX: {
1741 // Delay emission for top-level C++ matchers (which can use MatchDatas).
1742 if (IsUsingCustomCXXAction)
1743 CXXMatchers.push_back(Elt: cast<CXXPattern>(Val: Pat.get()));
1744 else
1745 addCXXPredicate(M, CE, P: *cast<CXXPattern>(Val: Pat.get()), Alts);
1746 break;
1747 }
1748 default:
1749 llvm_unreachable("unknown pattern kind!");
1750 }
1751 }
1752
1753 const bool Res = IsUsingCustomCXXAction
1754 ? emitCXXMatchApply(CE, M, Matchers: CXXMatchers)
1755 : emitApplyPatterns(CE, M);
1756 if (!Res)
1757 return false;
1758 }
1759
1760 return true;
1761}
1762
1763bool CombineRuleBuilder::emitPatFragMatchPattern(
1764 CodeExpansions &CE, const PatternAlternatives &Alts, RuleMatcher &RM,
1765 InstructionMatcher *IM, const PatFragPattern &PFP,
1766 DenseSet<const Pattern *> &SeenPats) {
1767 auto StackTrace = PrettyStackTraceEmit(RuleDef, &PFP);
1768
1769 if (!SeenPats.insert(V: &PFP).second)
1770 return true;
1771
1772 const auto &PF = PFP.getPatFrag();
1773
1774 if (!IM) {
1775 // When we don't have an IM, this means this PatFrag isn't reachable from
1776 // the root. This is only acceptable if it doesn't define anything (e.g. a
1777 // pure C++ PatFrag).
1778 if (PF.num_out_params() != 0) {
1779 PFP.reportUnreachable(Locs: RuleDef.getLoc());
1780 return false;
1781 }
1782 } else {
1783 // When an IM is provided, this is reachable from the root, and we're
1784 // expecting to have output operands.
1785 // TODO: If we want to allow for multiple roots we'll need a map of IMs
1786 // then, and emission becomes a bit more complicated.
1787 assert(PF.num_roots() == 1);
1788 }
1789
1790 CodeExpansions PatFragCEs;
1791 if (!PFP.mapInputCodeExpansions(ParentCEs: CE, PatFragCEs, DiagLoc: RuleDef.getLoc()))
1792 return false;
1793
1794 // List of {ParamName, ArgName}.
1795 // When all patterns have been emitted, find expansions in PatFragCEs named
1796 // ArgName and add their expansion to CE using ParamName as the key.
1797 SmallVector<std::pair<std::string, std::string>, 4> CEsToImport;
1798
1799 // Map parameter names to the actual argument.
1800 const auto OperandMapper =
1801 [&](const InstructionOperand &O) -> InstructionOperand {
1802 if (!O.isNamedOperand())
1803 return O;
1804
1805 StringRef ParamName = O.getOperandName();
1806
1807 // Not sure what to do with those tbh. They should probably never be here.
1808 assert(!O.isNamedImmediate() && "TODO: handle named imms");
1809 unsigned PIdx = PF.getParamIdx(Name: ParamName);
1810
1811 // Map parameters to the argument values.
1812 if (PIdx == (unsigned)-1) {
1813 // This is a temp of the PatFragPattern, prefix the name to avoid
1814 // conflicts.
1815 return O.withNewName(
1816 NewName: insertStrRef(S: (PFP.getName() + "." + ParamName).str()));
1817 }
1818
1819 // The operand will be added to PatFragCEs's code expansions using the
1820 // parameter's name. If it's bound to some operand during emission of the
1821 // patterns, we'll want to add it to CE.
1822 auto ArgOp = PFP.getOperand(K: PIdx);
1823 if (ArgOp.isNamedOperand())
1824 CEsToImport.emplace_back(Args: ArgOp.getOperandName().str(), Args&: ParamName);
1825
1826 if (ArgOp.getType() && O.getType() && ArgOp.getType() != O.getType()) {
1827 StringRef PFName = PF.getName();
1828 PrintWarning(Msg: "impossible type constraints: operand " + Twine(PIdx) +
1829 " of '" + PFP.getName() + "' has type '" +
1830 ArgOp.getType().str() + "', but '" + PFName +
1831 "' constrains it to '" + O.getType().str() + "'");
1832 if (ArgOp.isNamedOperand())
1833 PrintNote(Msg: "operand " + Twine(PIdx) + " of '" + PFP.getName() +
1834 "' is '" + ArgOp.getOperandName() + "'");
1835 if (O.isNamedOperand())
1836 PrintNote(Msg: "argument " + Twine(PIdx) + " of '" + PFName + "' is '" +
1837 ParamName + "'");
1838 }
1839
1840 return ArgOp;
1841 };
1842
1843 // PatFragPatterns are only made of InstructionPatterns or CXXPatterns.
1844 // Emit instructions from the root.
1845 const auto &FragAlt = PF.getAlternative(K: Alts.lookup(Val: &PFP));
1846 const auto &FragAltOT = FragAlt.OpTable;
1847 const auto LookupOperandDef =
1848 [&](StringRef Op) -> const InstructionPattern * {
1849 return FragAltOT.getDef(OpName: Op);
1850 };
1851
1852 DenseSet<const Pattern *> PatFragSeenPats;
1853 for (const auto &[Idx, InOp] : enumerate(First: PF.out_params())) {
1854 if (InOp.Kind != PatFrag::PK_Root)
1855 continue;
1856
1857 StringRef ParamName = InOp.Name;
1858 const auto *Def = FragAltOT.getDef(OpName: ParamName);
1859 assert(Def && "PatFrag::checkSemantics should have emitted an error if "
1860 "an out operand isn't defined!");
1861 assert(isa<CodeGenInstructionPattern>(Def) &&
1862 "Nested PatFrags not supported yet");
1863
1864 if (!emitCodeGenInstructionMatchPattern(
1865 CE&: PatFragCEs, Alts, M&: RM, IM&: *IM, P: *cast<CodeGenInstructionPattern>(Val: Def),
1866 SeenPats&: PatFragSeenPats, LookupOperandDef, OperandMapper))
1867 return false;
1868 }
1869
1870 // Emit leftovers.
1871 for (const auto &Pat : FragAlt.Pats) {
1872 if (PatFragSeenPats.contains(V: Pat.get()))
1873 continue;
1874
1875 if (const auto *CXXPat = dyn_cast<CXXPattern>(Val: Pat.get())) {
1876 addCXXPredicate(M&: RM, CE: PatFragCEs, P: *CXXPat, Alts);
1877 continue;
1878 }
1879
1880 if (const auto *IP = dyn_cast<InstructionPattern>(Val: Pat.get())) {
1881 IP->reportUnreachable(Locs: PF.getLoc());
1882 return false;
1883 }
1884
1885 llvm_unreachable("Unexpected pattern kind in PatFrag");
1886 }
1887
1888 for (const auto &[ParamName, ArgName] : CEsToImport) {
1889 // Note: we're find if ParamName already exists. It just means it's been
1890 // bound before, so we prefer to keep the first binding.
1891 CE.declare(Name: ParamName, Expansion: PatFragCEs.lookup(Variable: ArgName));
1892 }
1893
1894 return true;
1895}
1896
1897bool CombineRuleBuilder::emitApplyPatterns(CodeExpansions &CE, RuleMatcher &M) {
1898 assert(MatchDatas.empty());
1899
1900 DenseSet<const Pattern *> SeenPats;
1901 StringMap<unsigned> OperandToTempRegID;
1902
1903 for (auto *ApplyRoot : ApplyRoots) {
1904 assert(isa<InstructionPattern>(ApplyRoot) &&
1905 "Root can only be a InstructionPattern!");
1906 if (!emitInstructionApplyPattern(CE, M,
1907 P: cast<InstructionPattern>(Val&: *ApplyRoot),
1908 SeenPats, OperandToTempRegID))
1909 return false;
1910 }
1911
1912 for (auto &Pat : values(C&: ApplyPats)) {
1913 if (SeenPats.contains(V: Pat.get()))
1914 continue;
1915
1916 switch (Pat->getKind()) {
1917 case Pattern::K_AnyOpcode:
1918 llvm_unreachable("Unexpected pattern in apply!");
1919 case Pattern::K_PatFrag:
1920 // TODO: We could support pure C++ PatFrags as a temporary thing.
1921 llvm_unreachable("Unexpected pattern in apply!");
1922 case Pattern::K_Builtin:
1923 if (!emitInstructionApplyPattern(CE, M, P: cast<BuiltinPattern>(Val&: *Pat),
1924 SeenPats, OperandToTempRegID))
1925 return false;
1926 break;
1927 case Pattern::K_CodeGenInstruction:
1928 cast<CodeGenInstructionPattern>(Val&: *Pat).reportUnreachable(Locs: RuleDef.getLoc());
1929 return false;
1930 case Pattern::K_CXX: {
1931 llvm_unreachable(
1932 "CXX Pattern Emission should have been handled earlier!");
1933 }
1934 default:
1935 llvm_unreachable("unknown pattern kind!");
1936 }
1937 }
1938
1939 // Erase the root.
1940 unsigned RootInsnID =
1941 M.getInstructionMatcher(SymbolicName: MatchRoot->getName()).getInsnVarID();
1942 if (M.tryEraseInsnID(ID: RootInsnID))
1943 M.addAction<EraseInstAction>(args&: RootInsnID);
1944
1945 return true;
1946}
1947
1948bool CombineRuleBuilder::emitCXXMatchApply(CodeExpansions &CE, RuleMatcher &M,
1949 ArrayRef<CXXPattern *> Matchers) {
1950 assert(hasOnlyCXXApplyPatterns());
1951 declareAllMatchDatasExpansions(CE);
1952
1953 std::string CodeStr;
1954 raw_string_ostream OS(CodeStr);
1955
1956 for (auto &MD : MatchDatas)
1957 OS << MD.Type << " " << MD.getVarName() << ";\n";
1958
1959 if (!Matchers.empty()) {
1960 OS << "// Match Patterns\n";
1961 for (auto *M : Matchers) {
1962 OS << "if(![&](){";
1963 CodeExpander Expander(M->getRawCode(), CE, RuleDef.getLoc(),
1964 /*ShowExpansions=*/false);
1965 Expander.emit(OS);
1966 OS << "}()) {\n"
1967 << " return false;\n}\n";
1968 }
1969 }
1970
1971 OS << "// Apply Patterns\n";
1972 ListSeparator LS("\n");
1973 for (auto &Pat : ApplyPats) {
1974 auto *CXXPat = cast<CXXPattern>(Val: Pat.second.get());
1975 CodeExpander Expander(CXXPat->getRawCode(), CE, RuleDef.getLoc(),
1976 /*ShowExpansions=*/false);
1977 OS << LS;
1978 Expander.emit(OS);
1979 }
1980
1981 const auto &Code = CXXPredicateCode::getCustomActionCode(Code: CodeStr);
1982 M.setCustomCXXAction(Code.getEnumNameWithPrefix(Prefix: CXXCustomActionPrefix));
1983 return true;
1984}
1985
1986bool CombineRuleBuilder::emitInstructionApplyPattern(
1987 CodeExpansions &CE, RuleMatcher &M, const InstructionPattern &P,
1988 DenseSet<const Pattern *> &SeenPats,
1989 StringMap<unsigned> &OperandToTempRegID) {
1990 auto StackTrace = PrettyStackTraceEmit(RuleDef, &P);
1991
1992 if (!SeenPats.insert(V: &P).second)
1993 return true;
1994
1995 // First, render the uses.
1996 for (auto &Op : P.named_operands()) {
1997 if (Op.isDef())
1998 continue;
1999
2000 StringRef OpName = Op.getOperandName();
2001 if (const auto *DefPat = ApplyOpTable.getDef(OpName)) {
2002 if (!emitInstructionApplyPattern(CE, M, P: *DefPat, SeenPats,
2003 OperandToTempRegID))
2004 return false;
2005 } else {
2006 // If we have no def, check this exists in the MatchRoot.
2007 if (!Op.isNamedImmediate() && !MatchOpTable.lookup(OpName).Found) {
2008 PrintError(Msg: "invalid output operand '" + OpName +
2009 "': operand is not a live-in of the match pattern, and it "
2010 "has no definition");
2011 return false;
2012 }
2013 }
2014 }
2015
2016 if (const auto *BP = dyn_cast<BuiltinPattern>(Val: &P))
2017 return emitBuiltinApplyPattern(CE, M, P: *BP, OperandToTempRegID);
2018
2019 if (isa<PatFragPattern>(Val: &P))
2020 llvm_unreachable("PatFragPatterns is not supported in 'apply'!");
2021
2022 auto &CGIP = cast<CodeGenInstructionPattern>(Val: P);
2023
2024 // Now render this inst.
2025 auto &DstMI =
2026 M.addAction<BuildMIAction>(args: M.allocateOutputInsnID(), args&: M, args: &CGIP.getInst());
2027
2028 bool HasEmittedIntrinsicID = false;
2029 const auto EmitIntrinsicID = [&]() {
2030 assert(CGIP.isIntrinsic());
2031 DstMI.addRenderer<IntrinsicIDRenderer>(args: CGIP.getIntrinsic());
2032 HasEmittedIntrinsicID = true;
2033 };
2034
2035 for (auto &Op : P.operands()) {
2036 // Emit the intrinsic ID after the last def.
2037 if (CGIP.isIntrinsic() && !Op.isDef() && !HasEmittedIntrinsicID)
2038 EmitIntrinsicID();
2039
2040 if (Op.isNamedImmediate()) {
2041 PrintError(Msg: "invalid output operand '" + Op.getOperandName() +
2042 "': output immediates cannot be named");
2043 PrintNote(Msg: "while emitting pattern '" + P.getName() + "' (" +
2044 P.getInstName() + ")");
2045 return false;
2046 }
2047
2048 if (Op.hasImmValue()) {
2049 if (!emitCodeGenInstructionApplyImmOperand(M, DstMI, P: CGIP, O: Op))
2050 return false;
2051 continue;
2052 }
2053
2054 StringRef OpName = Op.getOperandName();
2055
2056 // Uses of operand.
2057 if (!Op.isDef()) {
2058 if (auto It = OperandToTempRegID.find(Key: OpName);
2059 It != OperandToTempRegID.end()) {
2060 assert(!MatchOpTable.lookup(OpName).Found &&
2061 "Temp reg is also from match pattern?");
2062 DstMI.addRenderer<TempRegRenderer>(args&: It->second);
2063 } else {
2064 // This should be a match live in or a redef of a matched instr.
2065 // If it's a use of a temporary register, then we messed up somewhere -
2066 // the previous condition should have passed.
2067 assert(MatchOpTable.lookup(OpName).Found &&
2068 !ApplyOpTable.getDef(OpName) && "Temp reg not emitted yet!");
2069 DstMI.addRenderer<CopyRenderer>(args&: M, args&: OpName);
2070 }
2071 continue;
2072 }
2073
2074 // Determine what we're dealing with. Are we replacing a matched
2075 // instruction? Creating a new one?
2076 auto OpLookupRes = MatchOpTable.lookup(OpName);
2077 if (OpLookupRes.Found) {
2078 if (OpLookupRes.isLiveIn()) {
2079 // live-in of the match pattern.
2080 PrintError(Msg: "Cannot define live-in operand '" + OpName +
2081 "' in the 'apply' pattern");
2082 return false;
2083 }
2084 assert(OpLookupRes.Def);
2085
2086 // TODO: Handle this. We need to mutate the instr, or delete the old
2087 // one.
2088 // Likewise, we also need to ensure we redef everything, if the
2089 // instr has more than one def, we need to redef all or nothing.
2090 if (OpLookupRes.Def != MatchRoot) {
2091 PrintError(Msg: "redefining an instruction other than the root is not "
2092 "supported (operand '" +
2093 OpName + "')");
2094 return false;
2095 }
2096 // redef of a match
2097 DstMI.addRenderer<CopyRenderer>(args&: M, args&: OpName);
2098 continue;
2099 }
2100
2101 // Define a new register unique to the apply patterns (AKA a "temp"
2102 // register).
2103 unsigned TempRegID;
2104 if (auto It = OperandToTempRegID.find(Key: OpName);
2105 It != OperandToTempRegID.end()) {
2106 TempRegID = It->second;
2107 } else {
2108 // This is a brand new register.
2109 TempRegID = M.allocateTempRegID();
2110 OperandToTempRegID[OpName] = TempRegID;
2111 const auto Ty = Op.getType();
2112 if (!Ty) {
2113 PrintError(Msg: "def of a new register '" + OpName +
2114 "' in the apply patterns must have a type");
2115 return false;
2116 }
2117
2118 declareTempRegExpansion(CE, TempRegID, Name: OpName);
2119 // Always insert the action at the beginning, otherwise we may end up
2120 // using the temp reg before it's available.
2121 auto Result = getLLTCodeGenOrTempType(PT: Ty, RM&: M);
2122 if (!Result)
2123 return false;
2124 M.insertAction<MakeTempRegisterAction>(InsertPt: M.actions_begin(), args&: *Result,
2125 args&: TempRegID);
2126 }
2127
2128 DstMI.addRenderer<TempRegRenderer>(args&: TempRegID, /*IsDef=*/args: true);
2129 }
2130
2131 // Some intrinsics have no in operands, ensure the ID is still emitted in such
2132 // cases.
2133 if (CGIP.isIntrinsic() && !HasEmittedIntrinsicID)
2134 EmitIntrinsicID();
2135
2136 // Render MIFlags
2137 if (const auto *FI = CGIP.getMIFlagsInfo()) {
2138 for (StringRef InstName : FI->copy_flags())
2139 DstMI.addCopiedMIFlags(IM: M.getInstructionMatcher(SymbolicName: InstName));
2140 for (StringRef F : FI->set_flags())
2141 DstMI.addSetMIFlags(Flag: F);
2142 for (StringRef F : FI->unset_flags())
2143 DstMI.addUnsetMIFlags(Flag: F);
2144 }
2145
2146 // Don't allow mutating opcodes for GISel combiners. We want a more precise
2147 // handling of MIFlags so we require them to be explicitly preserved.
2148 //
2149 // TODO: We don't mutate very often, if at all in combiners, but it'd be nice
2150 // to re-enable this. We'd then need to always clear MIFlags when mutating
2151 // opcodes, and never mutate an inst that we copy flags from.
2152 // DstMI.chooseInsnToMutate(M);
2153 declareInstExpansion(CE, A: DstMI, Name: P.getName());
2154
2155 return true;
2156}
2157
2158bool CombineRuleBuilder::emitCodeGenInstructionApplyImmOperand(
2159 RuleMatcher &M, BuildMIAction &DstMI, const CodeGenInstructionPattern &P,
2160 const InstructionOperand &O) {
2161 // If we have a type, we implicitly emit a G_CONSTANT, except for G_CONSTANT
2162 // itself (which needs a CImm) and G_FCONSTANT (which needs an FP immediate).
2163 // The pattern grammar has no fp literals, so a G_FCONSTANT immediate is an
2164 // IEEE bit pattern of the immediate's type (0 is +0.0 for every FP width).
2165 //
2166 // No type means we emit a simple imm.
2167 // G_CONSTANT/G_FCONSTANT are special cases and need a typed immediate
2168 // though so this is likely a mistake.
2169 const bool isGConstant = P.is(OpcodeName: "G_CONSTANT");
2170 const bool isGFConstant = P.is(OpcodeName: "G_FCONSTANT");
2171 const auto Ty = O.getType();
2172 if (!Ty) {
2173 if (isGConstant) {
2174 PrintError(Msg: "'G_CONSTANT' immediate must be typed!");
2175 PrintNote(Msg: "while emitting pattern '" + P.getName() + "' (" +
2176 P.getInstName() + ")");
2177 return false;
2178 }
2179
2180 if (isGFConstant) {
2181 PrintError(Msg: "'G_FCONSTANT' immediate must be typed!");
2182 PrintNote(Msg: "while emitting pattern '" + P.getName() + "' (" +
2183 P.getInstName() + ")");
2184 return false;
2185 }
2186
2187 DstMI.addRenderer<ImmRenderer>(args: O.getImmValue());
2188 return true;
2189 }
2190
2191 auto ImmTy = getLLTCodeGenOrTempType(PT: Ty, RM&: M);
2192 if (!ImmTy)
2193 return false;
2194
2195 if (isGConstant) {
2196 DstMI.addRenderer<ImmRenderer>(args: O.getImmValue(), args&: *ImmTy);
2197 return true;
2198 }
2199
2200 if (isGFConstant) {
2201 DstMI.addRenderer<ImmRenderer>(args: O.getImmValue(), args&: *ImmTy, /*IsFP=*/args: true);
2202 return true;
2203 }
2204
2205 unsigned TempRegID = M.allocateTempRegID();
2206 // Ensure MakeTempReg & the BuildConstantAction occur at the beginning.
2207 auto InsertIt = M.insertAction<MakeTempRegisterAction>(InsertPt: M.actions_begin(),
2208 args&: *ImmTy, args&: TempRegID);
2209 M.insertAction<BuildConstantAction>(InsertPt: ++InsertIt, args&: TempRegID, args: O.getImmValue());
2210 DstMI.addRenderer<TempRegRenderer>(args&: TempRegID);
2211 return true;
2212}
2213
2214bool CombineRuleBuilder::emitBuiltinApplyPattern(
2215 CodeExpansions &CE, RuleMatcher &M, const BuiltinPattern &P,
2216 StringMap<unsigned> &OperandToTempRegID) {
2217 const auto Error = [&](Twine Reason) {
2218 PrintError(Msg: "cannot emit '" + P.getInstName() + "' builtin: " + Reason);
2219 return false;
2220 };
2221
2222 switch (P.getBuiltinKind()) {
2223 case BI_EraseRoot: {
2224 // Root is always inst 0.
2225 if (M.tryEraseInsnID(ID: 0))
2226 M.addAction<EraseInstAction>(/*InsnID*/ args: 0);
2227 return true;
2228 }
2229 case BI_HasOneUse:
2230 llvm_unreachable("GIHasOneUse cannot be used in apply patterns!");
2231
2232 case BI_ReplaceReg: {
2233 StringRef Old = P.getOperand(K: 0).getOperandName();
2234 StringRef New = P.getOperand(K: 1).getOperandName();
2235
2236 if (!ApplyOpTable.lookup(OpName: New).Found && !MatchOpTable.lookup(OpName: New).Found)
2237 return Error("unknown operand '" + Old + "'");
2238
2239 auto &OldOM = M.getOperandMatcher(Name: Old);
2240 if (auto It = OperandToTempRegID.find(Key: New);
2241 It != OperandToTempRegID.end()) {
2242 // Replace with temp reg.
2243 M.addAction<ReplaceRegAction>(args: OldOM.getInsnVarID(), args: OldOM.getOpIdx(),
2244 args&: It->second);
2245 } else {
2246 // Replace with matched reg.
2247 auto &NewOM = M.getOperandMatcher(Name: New);
2248 M.addAction<ReplaceRegAction>(args: OldOM.getInsnVarID(), args: OldOM.getOpIdx(),
2249 args: NewOM.getInsnVarID(), args: NewOM.getOpIdx());
2250 }
2251 // checkSemantics should have ensured that we can only rewrite the root.
2252 // Ensure we're deleting it.
2253 assert(MatchOpTable.getDef(Old) == MatchRoot);
2254 return true;
2255 }
2256 }
2257
2258 llvm_unreachable("Unknown BuiltinKind!");
2259}
2260
2261bool isLiteralImm(const InstructionPattern &P, unsigned OpIdx) {
2262 if (const auto *CGP = dyn_cast<CodeGenInstructionPattern>(Val: &P)) {
2263 StringRef InstName = CGP->getInst().getName();
2264 return (InstName == "G_CONSTANT" || InstName == "G_FCONSTANT") &&
2265 OpIdx == 1;
2266 }
2267
2268 llvm_unreachable("TODO");
2269}
2270
2271bool CombineRuleBuilder::emitCodeGenInstructionMatchPattern(
2272 CodeExpansions &CE, const PatternAlternatives &Alts, RuleMatcher &M,
2273 InstructionMatcher &IM, const CodeGenInstructionPattern &P,
2274 DenseSet<const Pattern *> &SeenPats, OperandDefLookupFn LookupOperandDef,
2275 OperandMapperFnRef OperandMapper) {
2276 auto StackTrace = PrettyStackTraceEmit(RuleDef, &P);
2277
2278 if (!SeenPats.insert(V: &P).second)
2279 return true;
2280
2281 IM.addPredicate<InstructionOpcodeMatcher>(args: &P.getInst());
2282 declareInstExpansion(CE, IM, Name: P.getName());
2283
2284 // If this is an intrinsic, check the intrinsic ID.
2285 if (P.isIntrinsic()) {
2286 // The IntrinsicID's operand is the first operand after the defs.
2287 OperandMatcher &OM = IM.addOperand(OpIdx: P.getNumInstDefs(), SymbolicName: "$intrinsic_id",
2288 AllocatedTemporariesBaseID: AllocatedTemporariesBaseID++);
2289 OM.addPredicate<IntrinsicIDOperandMatcher>(args: P.getIntrinsic());
2290 }
2291
2292 // Check flags if needed.
2293 if (const auto *FI = P.getMIFlagsInfo()) {
2294 assert(FI->copy_flags().empty());
2295
2296 if (const auto &SetF = FI->set_flags(); !SetF.empty())
2297 IM.addPredicate<MIFlagsInstructionPredicateMatcher>(args: SetF.getArrayRef());
2298 if (const auto &UnsetF = FI->unset_flags(); !UnsetF.empty())
2299 IM.addPredicate<MIFlagsInstructionPredicateMatcher>(args: UnsetF.getArrayRef(),
2300 /*CheckNot=*/args: true);
2301 }
2302
2303 for (auto [Idx, OriginalO] : enumerate(First: P.operands())) {
2304 // Remap the operand. This is used when emitting InstructionPatterns inside
2305 // PatFrags, so it can remap them to the arguments passed to the pattern.
2306 //
2307 // We use the remapped operand to emit immediates, and for the symbolic
2308 // operand names (in IM.addOperand). CodeExpansions and OperandTable lookups
2309 // still use the original name.
2310 //
2311 // The "def" flag on the remapped operand is always ignored.
2312 auto RemappedO = OperandMapper(OriginalO);
2313 assert(RemappedO.isNamedOperand() == OriginalO.isNamedOperand() &&
2314 "Cannot remap an unnamed operand to a named one!");
2315
2316 const auto Ty = RemappedO.getType();
2317
2318 const auto OpName =
2319 RemappedO.isNamedOperand() ? RemappedO.getOperandName().str() : "";
2320
2321 // For intrinsics, the first use operand is the intrinsic id, so the true
2322 // operand index is shifted by 1.
2323 //
2324 // From now on:
2325 // Idx = index in the pattern operand list.
2326 // RealIdx = expected index in the MachineInstr.
2327 const unsigned RealIdx =
2328 (P.isIntrinsic() && !OriginalO.isDef()) ? (Idx + 1) : Idx;
2329
2330 if (Ty.isVariadicPack() && M.hasOperand(SymbolicName: OpName)) {
2331 // TODO: We could add some CheckIsSameOperand opcode variant that checks
2332 // all operands. We could also just emit a C++ code snippet lazily to do
2333 // the check since it's probably fairly rare that we need to do it.
2334 //
2335 // I'm just not sure it's worth the effort at this stage.
2336 PrintError(Msg: "each instance of a " + PatternType::VariadicClassName +
2337 " operand must have a unique name within the match patterns");
2338 PrintNote(Msg: "'" + OpName + "' is used multiple times");
2339 return false;
2340 }
2341
2342 OperandMatcher &OM =
2343 IM.addOperand(OpIdx: RealIdx, SymbolicName: OpName, AllocatedTemporariesBaseID: AllocatedTemporariesBaseID++,
2344 /*IsVariadic=*/Ty.isVariadicPack());
2345 if (!OpName.empty())
2346 declareOperandExpansion(CE, OM, Name: OriginalO.getOperandName());
2347
2348 if (Ty.isVariadicPack()) {
2349 // In the presence of variadics, the InstructionMatcher won't insert a
2350 // InstructionNumOperandsMatcher implicitly, so we have to emit our own.
2351 assert((Idx + 1) == P.operands_size() &&
2352 "VariadicPack isn't last operand!");
2353 auto VPTI = Ty.getVariadicPackTypeInfo();
2354 assert(VPTI.Min > 0 && (VPTI.Max == 0 || VPTI.Max > VPTI.Min));
2355 IM.addPredicate<InstructionNumOperandsMatcher>(
2356 args: RealIdx + VPTI.Min, args: InstructionNumOperandsMatcher::CheckKind::GE);
2357 if (VPTI.Max) {
2358 IM.addPredicate<InstructionNumOperandsMatcher>(
2359 args: RealIdx + VPTI.Max, args: InstructionNumOperandsMatcher::CheckKind::LE);
2360 }
2361 break;
2362 }
2363
2364 // Handle immediates.
2365 if (RemappedO.hasImmValue()) {
2366 if (isLiteralImm(P, OpIdx: Idx))
2367 OM.addPredicate<LiteralIntOperandMatcher>(args: RemappedO.getImmValue());
2368 else
2369 OM.addPredicate<ConstantIntOperandMatcher>(args: RemappedO.getImmValue());
2370 }
2371
2372 // Handle typed operands, but only bother to check if it hasn't been done
2373 // before.
2374 //
2375 // getOperandMatcher will always return the first OM to have been created
2376 // for that Operand. "OM" here is always a new OperandMatcher.
2377 //
2378 // Always emit a check for unnamed operands.
2379 if (Ty && (OpName.empty() ||
2380 !M.getOperandMatcher(Name: OpName).contains<LLTOperandMatcher>())) {
2381 // TODO: We could support GITypeOf here on the condition that the
2382 // OperandMatcher exists already. Though it's clunky to make this work
2383 // and isn't all that useful so it's just rejected in typecheckPatterns
2384 // at this time.
2385 assert(Ty.isLLT());
2386 OM.addPredicate<LLTOperandMatcher>(args: getLLTCodeGen(PT: Ty));
2387 }
2388
2389 // Stop here if the operand is a def, or if it had no name.
2390 if (OriginalO.isDef() || !OriginalO.isNamedOperand())
2391 continue;
2392
2393 const auto *DefPat = LookupOperandDef(OriginalO.getOperandName());
2394 if (!DefPat)
2395 continue;
2396
2397 if (OriginalO.hasImmValue()) {
2398 assert(!OpName.empty());
2399 // This is a named immediate that also has a def, that's not okay.
2400 // e.g.
2401 // (G_SEXT $y, (i32 0))
2402 // (COPY $x, 42:$y)
2403 PrintError(Msg: "'" + OpName +
2404 "' is a named immediate, it cannot be defined by another "
2405 "instruction");
2406 PrintNote(Msg: "'" + OpName + "' is defined by '" + DefPat->getName() + "'");
2407 return false;
2408 }
2409
2410 // From here we know that the operand defines an instruction, and we need to
2411 // emit it.
2412 auto InstOpM =
2413 OM.addPredicate<InstructionOperandMatcher>(args&: M, args: DefPat->getName());
2414 if (!InstOpM) {
2415 // TODO: copy-pasted from GlobalISelEmitter.cpp. Is it still relevant
2416 // here?
2417 PrintError(Msg: "Nested instruction '" + DefPat->getName() +
2418 "' cannot be the same as another operand '" +
2419 OriginalO.getOperandName() + "'");
2420 return false;
2421 }
2422
2423 auto &IM = (*InstOpM)->getInsnMatcher();
2424 if (const auto *CGIDef = dyn_cast<CodeGenInstructionPattern>(Val: DefPat)) {
2425 if (!emitCodeGenInstructionMatchPattern(CE, Alts, M, IM, P: *CGIDef,
2426 SeenPats, LookupOperandDef,
2427 OperandMapper))
2428 return false;
2429 continue;
2430 }
2431
2432 if (const auto *PFPDef = dyn_cast<PatFragPattern>(Val: DefPat)) {
2433 if (!emitPatFragMatchPattern(CE, Alts, RM&: M, IM: &IM, PFP: *PFPDef, SeenPats))
2434 return false;
2435 continue;
2436 }
2437
2438 llvm_unreachable("unknown type of InstructionPattern");
2439 }
2440
2441 return true;
2442}
2443
2444//===- GICombinerEmitter --------------------------------------------------===//
2445
2446/// Main implementation class. This emits the tablegenerated output.
2447///
2448/// It collects rules, uses `CombineRuleBuilder` to parse them and accumulate
2449/// RuleMatchers, then takes all the necessary state/data from the various
2450/// static storage pools and wires them together to emit the match table &
2451/// associated function/data structures.
2452class GICombinerEmitter final : public GlobalISelMatchTableExecutorEmitter {
2453 const RecordKeeper &Records;
2454 StringRef Name;
2455 const CodeGenTarget &Target;
2456 const Record *Combiner;
2457 unsigned NextRuleID = 0;
2458
2459 // List all combine rules (ID, name) imported.
2460 // Note that the combiner rule ID is different from the RuleMatcher ID. The
2461 // latter is internal to the MatchTable, the former is the canonical ID of the
2462 // combine rule used to disable/enable it.
2463 std::vector<std::pair<unsigned, std::string>> AllCombineRules;
2464
2465 // Opcodes handled by the generated matcher.
2466 SmallSetVector<const CodeGenInstruction *, 32> MatchOpcodes;
2467
2468 // Keep track of all rules we've seen so far to ensure we don't process
2469 // the same rule twice.
2470 StringSet<> RulesSeen;
2471
2472 MatchTable buildMatchTable(MutableArrayRef<RuleMatcher> Rules);
2473
2474 void emitRuleConfigImpl(raw_ostream &OS);
2475 void collectMatchOpcodes(ArrayRef<RuleMatcher> Rules);
2476 void emitCanMatchOpcodeFn(raw_ostream &OS, StringRef FnName) const;
2477
2478 void emitAdditionalImpl(raw_ostream &OS) override;
2479
2480 void emitMIPredicateFns(raw_ostream &OS) override;
2481 void emitLeafPredicateFns(raw_ostream &OS) override;
2482 void emitI64ImmPredicateFns(raw_ostream &OS) override;
2483 void emitAPFloatImmPredicateFns(raw_ostream &OS) override;
2484 void emitAPIntImmPredicateFns(raw_ostream &OS) override;
2485 void emitTestSimplePredicate(raw_ostream &OS) override;
2486 void emitRunCustomAction(raw_ostream &OS) override;
2487
2488 const CodeGenTarget &getTarget() const override { return Target; }
2489 StringRef getClassName() const override {
2490 return Combiner->getValueAsString(FieldName: "Classname");
2491 }
2492
2493 StringRef getCombineAllMethodName() const {
2494 return Combiner->getValueAsString(FieldName: "CombineAllMethodName");
2495 }
2496
2497 std::string getRuleConfigClassName() const {
2498 return getClassName().str() + "RuleConfig";
2499 }
2500
2501 void gatherRules(std::vector<RuleMatcher> &Rules,
2502 ArrayRef<const Record *> RulesAndGroups);
2503
2504public:
2505 explicit GICombinerEmitter(const RecordKeeper &RK,
2506 const CodeGenTarget &Target, StringRef Name,
2507 const Record *Combiner);
2508 ~GICombinerEmitter() override = default;
2509
2510 void run(raw_ostream &OS);
2511};
2512
2513void GICombinerEmitter::emitRuleConfigImpl(raw_ostream &OS) {
2514 IfDefGuardEmitter If(OS, "GET_GICOMBINER_TYPES");
2515 OS << "struct " << getRuleConfigClassName() << " {\n"
2516 << " SparseBitVector<> DisabledRules;\n\n"
2517 << " bool isRuleEnabled(unsigned RuleID) const;\n"
2518 << " bool parseCommandLineOption();\n"
2519 << " bool setRuleEnabled(StringRef RuleIdentifier);\n"
2520 << " bool setRuleDisabled(StringRef RuleIdentifier);\n"
2521 << "};\n\n";
2522
2523 std::vector<std::pair<std::string, std::string>> Cases;
2524 Cases.reserve(n: AllCombineRules.size());
2525
2526 for (const auto &[ID, Name] : AllCombineRules)
2527 Cases.emplace_back(args: Name, args: "return " + to_string(Value: ID) + ";\n");
2528
2529 OS << "static std::optional<uint64_t> getRuleIdxForIdentifier(StringRef "
2530 "RuleIdentifier) {\n"
2531 << " uint64_t I;\n"
2532 << " // getAtInteger(...) returns false on success\n"
2533 << " bool Parsed = !RuleIdentifier.getAsInteger(0, I);\n"
2534 << " if (Parsed)\n"
2535 << " return I;\n\n"
2536 << "#ifndef NDEBUG\n";
2537 StringMatcher Matcher("RuleIdentifier", Cases, OS);
2538 Matcher.Emit();
2539 OS << "#endif // ifndef NDEBUG\n\n"
2540 << " return std::nullopt;\n"
2541 << "}\n";
2542
2543 OS << "static std::optional<std::pair<uint64_t, uint64_t>> "
2544 "getRuleRangeForIdentifier(StringRef RuleIdentifier) {\n"
2545 << " std::pair<StringRef, StringRef> RangePair = "
2546 "RuleIdentifier.split('-');\n"
2547 << " if (!RangePair.second.empty()) {\n"
2548 << " const auto First = "
2549 "getRuleIdxForIdentifier(RangePair.first);\n"
2550 << " const auto Last = "
2551 "getRuleIdxForIdentifier(RangePair.second);\n"
2552 << " if (!First || !Last)\n"
2553 << " return std::nullopt;\n"
2554 << " if (First >= Last)\n"
2555 << " report_fatal_error(\"Beginning of range should be before "
2556 "end of range\");\n"
2557 << " return {{*First, *Last + 1}};\n"
2558 << " }\n"
2559 << " if (RangePair.first == \"*\") {\n"
2560 << " return {{0, " << AllCombineRules.size() << "}};\n"
2561 << " }\n"
2562 << " const auto I = getRuleIdxForIdentifier(RangePair.first);\n"
2563 << " if (!I)\n"
2564 << " return std::nullopt;\n"
2565 << " return {{*I, *I + 1}};\n"
2566 << "}\n\n";
2567
2568 for (bool Enabled : {true, false}) {
2569 OS << "bool " << getRuleConfigClassName() << "::setRule"
2570 << (Enabled ? "Enabled" : "Disabled") << "(StringRef RuleIdentifier) {\n"
2571 << " auto MaybeRange = getRuleRangeForIdentifier(RuleIdentifier);\n"
2572 << " if (!MaybeRange)\n"
2573 << " return false;\n"
2574 << " for (auto I = MaybeRange->first; I < MaybeRange->second; ++I)\n"
2575 << " DisabledRules." << (Enabled ? "reset" : "set") << "(I);\n"
2576 << " return true;\n"
2577 << "}\n\n";
2578 }
2579
2580 OS << "static std::vector<std::string> " << Name << "Option;\n"
2581 << "static cl::list<std::string> " << Name << "DisableOption(\n"
2582 << " \"" << Name.lower() << "-disable-rule\",\n"
2583 << " cl::desc(\"Disable one or more combiner rules temporarily in "
2584 << "the " << Name << " pass\"),\n"
2585 << " cl::CommaSeparated,\n"
2586 << " cl::Hidden,\n"
2587 << " cl::cat(GICombinerOptionCategory),\n"
2588 << " cl::callback([](const std::string &Str) {\n"
2589 << " " << Name << "Option.push_back(Str);\n"
2590 << " }));\n"
2591 << "static cl::list<std::string> " << Name << "OnlyEnableOption(\n"
2592 << " \"" << Name.lower() << "-only-enable-rule\",\n"
2593 << " cl::desc(\"Disable all rules in the " << Name
2594 << " pass then re-enable the specified ones\"),\n"
2595 << " cl::Hidden,\n"
2596 << " cl::cat(GICombinerOptionCategory),\n"
2597 << " cl::callback([](const std::string &CommaSeparatedArg) {\n"
2598 << " StringRef Str = CommaSeparatedArg;\n"
2599 << " " << Name << "Option.push_back(\"*\");\n"
2600 << " do {\n"
2601 << " auto X = Str.split(\",\");\n"
2602 << " " << Name << "Option.push_back((\"!\" + X.first).str());\n"
2603 << " Str = X.second;\n"
2604 << " } while (!Str.empty());\n"
2605 << " }));\n"
2606 << "\n\n"
2607 << "bool " << getRuleConfigClassName()
2608 << "::isRuleEnabled(unsigned RuleID) const {\n"
2609 << " return !DisabledRules.test(RuleID);\n"
2610 << "}\n"
2611 << "bool " << getRuleConfigClassName() << "::parseCommandLineOption() {\n"
2612 << " for (StringRef Identifier : " << Name << "Option) {\n"
2613 << " bool Enabled = Identifier.consume_front(\"!\");\n"
2614 << " if (Enabled && !setRuleEnabled(Identifier))\n"
2615 << " return false;\n"
2616 << " if (!Enabled && !setRuleDisabled(Identifier))\n"
2617 << " return false;\n"
2618 << " }\n"
2619 << " return true;\n"
2620 << "}\n\n";
2621}
2622
2623void GICombinerEmitter::collectMatchOpcodes(ArrayRef<RuleMatcher> Rules) {
2624 for (const RuleMatcher &Rule : Rules) {
2625 for (const CodeGenInstruction *I :
2626 Rule.roots_front().getOpcodeMatcher().getAlternativeOpcodes())
2627 MatchOpcodes.insert(X: I);
2628 }
2629}
2630
2631void GICombinerEmitter::emitCanMatchOpcodeFn(raw_ostream &OS,
2632 StringRef FnName) const {
2633 OS << "bool " << FnName << "(unsigned Opc) const {\n";
2634 if (MatchOpcodes.empty()) {
2635 OS << " (void)Opc;\n"
2636 << " return false;\n"
2637 << "}\n\n";
2638 return;
2639 }
2640
2641 OS << " switch (Opc) {\n";
2642 for (const CodeGenInstruction *I : MatchOpcodes)
2643 OS << " case " << I->Namespace << "::" << I->getName() << ":\n";
2644 OS << " return true;\n"
2645 << " default:\n"
2646 << " return false;\n"
2647 << " }\n"
2648 << "}\n\n";
2649}
2650
2651void GICombinerEmitter::emitAdditionalImpl(raw_ostream &OS) {
2652 std::string CanMatchOpcodeFnName =
2653 (getClassName() + "::canMatchOpcode").str();
2654 emitCanMatchOpcodeFn(OS, FnName: CanMatchOpcodeFnName);
2655 // Combines may build new instructions that do not preserve the
2656 // poison-generating flags from the original root instruction.
2657 OS << "uint32_t " << getClassName() << "::getRootFlagsToDrop() const {\n"
2658 << " return MachineInstr::getPoisonGeneratingFlags();\n"
2659 << "}\n\n";
2660 OS << "bool " << getClassName() << "::" << getCombineAllMethodName()
2661 << "(MachineInstr &I) const {\n"
2662 << " const PredicateBitset AvailableFeatures = "
2663 "getAvailableFeatures();\n"
2664 << " State.MIs.clear();\n"
2665 << " State.MIs.push_back(&I);\n"
2666 << " if (executeMatchTable(*this, State, ExecInfo, B"
2667 << ", getMatchTable(), Helper.getTII(), MRI, Helper.getTRI(), "
2668 "Helper.getRBI(), AvailableFeatures"
2669 << ", /*CoverageInfo*/ nullptr)) {\n"
2670 << " return true;\n"
2671 << " }\n\n"
2672 << " return false;\n"
2673 << "}\n\n";
2674}
2675
2676void GICombinerEmitter::emitMIPredicateFns(raw_ostream &OS) {
2677 auto MatchCode = CXXPredicateCode::getAllMatchCode();
2678 emitMIPredicateFnsImpl<const CXXPredicateCode *>(
2679 OS, AdditionalDecls: "", Predicates: ArrayRef<const CXXPredicateCode *>(MatchCode),
2680 GetPredEnumName: [](const CXXPredicateCode *C) -> StringRef { return C->BaseEnumName; },
2681 GetPredCode: [](const CXXPredicateCode *C) -> StringRef { return C->Code; });
2682}
2683
2684void GICombinerEmitter::emitLeafPredicateFns(raw_ostream &OS) {
2685 // Unused, but still needs to be called.
2686 emitLeafPredicateFnsImpl<unsigned>(
2687 OS, AdditionalDecls: "", Predicates: {}, GetPredEnumName: [](unsigned) { return ""; }, GetPredCode: [](unsigned) { return ""; });
2688}
2689
2690void GICombinerEmitter::emitI64ImmPredicateFns(raw_ostream &OS) {
2691 // Unused, but still needs to be called.
2692 emitImmPredicateFnsImpl<unsigned>(
2693 OS, TypeIdentifier: "I64", ArgType: "int64_t", Predicates: {}, GetPredEnumName: [](unsigned) { return ""; },
2694 GetPredCode: [](unsigned) { return ""; });
2695}
2696
2697void GICombinerEmitter::emitAPFloatImmPredicateFns(raw_ostream &OS) {
2698 // Unused, but still needs to be called.
2699 emitImmPredicateFnsImpl<unsigned>(
2700 OS, TypeIdentifier: "APFloat", ArgType: "const APFloat &", Predicates: {}, GetPredEnumName: [](unsigned) { return ""; },
2701 GetPredCode: [](unsigned) { return ""; });
2702}
2703
2704void GICombinerEmitter::emitAPIntImmPredicateFns(raw_ostream &OS) {
2705 // Unused, but still needs to be called.
2706 emitImmPredicateFnsImpl<unsigned>(
2707 OS, TypeIdentifier: "APInt", ArgType: "const APInt &", Predicates: {}, GetPredEnumName: [](unsigned) { return ""; },
2708 GetPredCode: [](unsigned) { return ""; });
2709}
2710
2711void GICombinerEmitter::emitTestSimplePredicate(raw_ostream &OS) {
2712 if (!AllCombineRules.empty()) {
2713 OS << "enum {\n";
2714 std::string EnumeratorSeparator = " = GICXXPred_Invalid + 1,\n";
2715 // To avoid emitting a switch, we expect that all those rules are in order.
2716 // That way we can just get the RuleID from the enum by subtracting
2717 // (GICXXPred_Invalid + 1).
2718 [[maybe_unused]] unsigned ExpectedID = 0;
2719 for (const auto &ID : keys(C&: AllCombineRules)) {
2720 assert(ExpectedID == ID && "combine rules are not ordered!");
2721 ++ExpectedID;
2722 OS << " " << getIsEnabledPredicateEnumName(CombinerRuleID: ID) << EnumeratorSeparator;
2723 EnumeratorSeparator = ",\n";
2724 }
2725 OS << "};\n\n";
2726 }
2727
2728 OS << "bool " << getClassName()
2729 << "::testSimplePredicate(unsigned Predicate) const {\n"
2730 << " return RuleConfig.isRuleEnabled(Predicate - "
2731 "GICXXPred_Invalid - "
2732 "1);\n"
2733 << "}\n";
2734}
2735
2736void GICombinerEmitter::emitRunCustomAction(raw_ostream &OS) {
2737 const auto CustomActionsCode = CXXPredicateCode::getAllCustomActionsCode();
2738
2739 if (!CustomActionsCode.empty()) {
2740 OS << "enum {\n";
2741 std::string EnumeratorSeparator = " = GICXXCustomAction_Invalid + 1,\n";
2742 for (const auto &CA : CustomActionsCode) {
2743 OS << " " << CA->getEnumNameWithPrefix(Prefix: CXXCustomActionPrefix)
2744 << EnumeratorSeparator;
2745 EnumeratorSeparator = ",\n";
2746 }
2747 OS << "};\n";
2748 }
2749
2750 OS << "bool " << getClassName()
2751 << "::runCustomAction(unsigned ApplyID, const MatcherState &State, "
2752 "NewMIVector &OutMIs) const "
2753 "{\n Helper.getBuilder().setInstrAndDebugLoc(*State.MIs[0]);\n";
2754 if (!CustomActionsCode.empty()) {
2755 OS << " switch(ApplyID) {\n";
2756 for (const auto &CA : CustomActionsCode) {
2757 OS << " case " << CA->getEnumNameWithPrefix(Prefix: CXXCustomActionPrefix)
2758 << ":{\n"
2759 << " " << join(R: split(Str: CA->Code, Separator: '\n'), Separator: "\n ") << '\n'
2760 << " return true;\n";
2761 OS << " }\n";
2762 }
2763 OS << " }\n";
2764 }
2765 OS << " llvm_unreachable(\"Unknown Apply Action\");\n"
2766 << "}\n";
2767}
2768
2769GICombinerEmitter::GICombinerEmitter(const RecordKeeper &RK,
2770 const CodeGenTarget &Target,
2771 StringRef Name, const Record *Combiner)
2772 : Records(RK), Name(Name), Target(Target), Combiner(Combiner) {}
2773
2774MatchTable
2775GICombinerEmitter::buildMatchTable(MutableArrayRef<RuleMatcher> Rules) {
2776 std::vector<std::unique_ptr<Matcher>> MatcherStorage;
2777 std::vector<Matcher *> OptRules = optimizeRuleset(Rules, MatcherStorage);
2778 return ::buildMatchTable(Rules: OptRules, /*WithCoverage*/ false,
2779 /*IsCombiner*/ true);
2780}
2781
2782/// Recurse into GICombineGroup's and flatten the ruleset into a simple list.
2783void GICombinerEmitter::gatherRules(std::vector<RuleMatcher> &ActiveRules,
2784 ArrayRef<const Record *> RulesAndGroups) {
2785 for (const Record *Rec : RulesAndGroups) {
2786 if (!Rec->isValueUnset(FieldName: "Rules")) {
2787 gatherRules(ActiveRules, RulesAndGroups: Rec->getValueAsListOfDefs(FieldName: "Rules"));
2788 continue;
2789 }
2790
2791 StringRef RuleName = Rec->getName();
2792 if (!RulesSeen.insert(key: RuleName).second) {
2793 PrintWarning(WarningLoc: Rec->getLoc(),
2794 Msg: "skipping rule '" + Rec->getName() +
2795 "' because it has already been processed");
2796 continue;
2797 }
2798
2799 AllCombineRules.emplace_back(args&: NextRuleID, args: Rec->getName().str());
2800 CombineRuleBuilder CRB(Target, SubtargetFeatures, *Rec, NextRuleID++,
2801 ActiveRules);
2802
2803 if (!CRB.parseAll()) {
2804 assert(ErrorsPrinted && "Parsing failed without errors!");
2805 continue;
2806 }
2807
2808 if (StopAfterParse) {
2809 CRB.print(OS&: outs());
2810 continue;
2811 }
2812
2813 if (!CRB.emitRuleMatchers()) {
2814 assert(ErrorsPrinted && "Emission failed without errors!");
2815 continue;
2816 }
2817 }
2818}
2819
2820void GICombinerEmitter::run(raw_ostream &OS) {
2821 InstructionOpcodeMatcher::initOpcodeValuesMap(Target);
2822 LLTOperandMatcher::initTypeIDValuesMap();
2823
2824 TGTimer &Timer = Records.getTimer();
2825 Timer.startTimer(Name: "Gather rules");
2826 std::vector<RuleMatcher> Rules;
2827 gatherRules(ActiveRules&: Rules, RulesAndGroups: Combiner->getValueAsListOfDefs(FieldName: "Rules"));
2828 if (ErrorsPrinted)
2829 PrintFatalError(ErrorLoc: Combiner->getLoc(), Msg: "Failed to parse one or more rules");
2830
2831 if (StopAfterParse)
2832 return;
2833
2834 Timer.startTimer(Name: "Creating Match Table");
2835 unsigned MaxTemporaries = 0;
2836 for (const auto &Rule : Rules)
2837 MaxTemporaries = std::max(a: MaxTemporaries, b: Rule.countRendererFns());
2838
2839 llvm::stable_sort(Range&: Rules, C: [&](const RuleMatcher &A, const RuleMatcher &B) {
2840 if (A.isHigherPriorityThan(B)) {
2841 assert(!B.isHigherPriorityThan(A) && "Cannot be more important "
2842 "and less important at "
2843 "the same time");
2844 return true;
2845 }
2846 return false;
2847 });
2848
2849 collectMatchOpcodes(Rules);
2850 const MatchTable Table = buildMatchTable(Rules);
2851
2852 Timer.startTimer(Name: "Emit combiner");
2853
2854 emitSourceFileHeader(Desc: getClassName().str() + " Combiner Match Table", OS);
2855
2856 SmallVector<LLTCodeGen, 16> TypeObjects;
2857 append_range(C&: TypeObjects, R&: KnownTypes);
2858 llvm::sort(C&: TypeObjects);
2859
2860 // Hack: Avoid empty declarator.
2861 if (TypeObjects.empty())
2862 TypeObjects.push_back(Elt: LLT::scalar(SizeInBits: 1));
2863
2864 // GET_GICOMBINER_DEPS, which pulls in extra dependencies.
2865 {
2866 IfDefGuardEmitter If(OS, "GET_GICOMBINER_DEPS");
2867 OS << "#include \"llvm/ADT/SparseBitVector.h\"\n";
2868 NamespaceEmitter LlvmNS(OS, "llvm");
2869 OS << "extern cl::OptionCategory GICombinerOptionCategory;\n";
2870 }
2871
2872 // GET_GICOMBINER_TYPES, which needs to be included before the declaration of
2873 // the class.
2874 emitRuleConfigImpl(OS);
2875 emitPredicateBitset(OS, IfDefName: "GET_GICOMBINER_TYPES");
2876
2877 // GET_GICOMBINER_CLASS_MEMBERS, which need to be included inside the class.
2878 {
2879 IfDefGuardEmitter If(OS, "GET_GICOMBINER_CLASS_MEMBERS");
2880 OS << " bool canMatchOpcode(unsigned Opc) const override;\n"
2881 << " uint32_t getRootFlagsToDrop() const override;\n";
2882 }
2883 emitPredicatesDecl(OS, IfDefName: "GET_GICOMBINER_CLASS_MEMBERS");
2884 emitTemporariesDecl(OS, IfDefName: "GET_GICOMBINER_CLASS_MEMBERS");
2885
2886 // GET_GICOMBINER_IMPL, which needs to be included outside the class.
2887 emitExecutorImpl(OS, Table, TypeObjects, Rules, ComplexOperandMatchers: {}, CustomOperandRenderers: {},
2888 IfDefName: "GET_GICOMBINER_IMPL");
2889
2890 // GET_GICOMBINER_CONSTRUCTOR_INITS, which are in the constructor's
2891 // initializer list.
2892 emitPredicatesInit(OS, IfDefName: "GET_GICOMBINER_CONSTRUCTOR_INITS");
2893 emitTemporariesInit(OS, MaxTemporaries, IfDefName: "GET_GICOMBINER_CONSTRUCTOR_INITS");
2894}
2895
2896//===----------------------------------------------------------------------===//
2897
2898static void EmitGICombiner(const RecordKeeper &RK, raw_ostream &OS) {
2899 EnablePrettyStackTrace();
2900 const CodeGenTarget Target(RK);
2901
2902 if (SelectedCombiners.empty())
2903 PrintFatalError(Msg: "No combiners selected with -combiners");
2904 for (const auto &Combiner : SelectedCombiners) {
2905 const Record *CombinerDef = RK.getDef(Name: Combiner);
2906 if (!CombinerDef)
2907 PrintFatalError(Msg: "Could not find " + Combiner);
2908 GICombinerEmitter(RK, Target, Combiner, CombinerDef).run(OS);
2909 }
2910}
2911
2912static TableGen::Emitter::Opt X("gen-global-isel-combiner", EmitGICombiner,
2913 "Generate GlobalISel Combiner");
2914