1//===- GlobalISelMatchTable.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#include "GlobalISelMatchTable.h"
10#include "Common/CodeGenInstruction.h"
11#include "Common/CodeGenRegisters.h"
12#include "llvm/ADT/Statistic.h"
13#include "llvm/Support/Debug.h"
14#include "llvm/Support/LEB128.h"
15#include "llvm/Support/ScopedPrinter.h"
16#include "llvm/Support/raw_ostream.h"
17#include "llvm/TableGen/Error.h"
18
19#define DEBUG_TYPE "gi-match-table"
20
21STATISTIC(NumPatternEmitted, "Number of patterns emitted");
22
23using namespace llvm;
24using namespace gi;
25
26// FIXME: Use createStringError instead.
27static Error failUnsupported(const Twine &Reason) {
28 return make_error<StringError>(Args: Reason, Args: inconvertibleErrorCode());
29}
30
31/// Get the name of the enum value used to number the predicate function.
32static std::string getEnumNameForPredicate(const TreePredicateFn &Predicate) {
33 if (Predicate.hasGISelPredicateCode())
34 return "GICXXPred_MI_" + Predicate.getFnName();
35 if (Predicate.hasGISelLeafPredicateCode())
36 return "GICXXPred_MO_" + Predicate.getFnName();
37 return "GICXXPred_" + Predicate.getImmTypeIdentifier().str() + "_" +
38 Predicate.getFnName();
39}
40
41static std::string
42getMatchOpcodeForImmPredicate(const TreePredicateFn &Predicate) {
43 return "GIM_Check" + Predicate.getImmTypeIdentifier().str() + "ImmPredicate";
44}
45
46// GIMT_Encode2/4/8
47constexpr StringLiteral EncodeMacroName = "GIMT_Encode";
48
49//===- Helpers ------------------------------------------------------------===//
50
51void llvm::gi::emitEncodingMacrosDef(raw_ostream &OS) {
52 OS << "#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__\n"
53 << "#define " << EncodeMacroName << "2(Val)"
54 << " uint8_t(Val), uint8_t((Val) >> 8)\n"
55 << "#define " << EncodeMacroName << "4(Val)"
56 << " uint8_t(Val), uint8_t((Val) >> 8), "
57 "uint8_t((Val) >> 16), uint8_t((Val) >> 24)\n"
58 << "#define " << EncodeMacroName << "8(Val)"
59 << " uint8_t(Val), uint8_t((Val) >> 8), "
60 "uint8_t((Val) >> 16), uint8_t((Val) >> 24), "
61 "uint8_t(uint64_t(Val) >> 32), uint8_t(uint64_t(Val) >> 40), "
62 "uint8_t(uint64_t(Val) >> 48), uint8_t(uint64_t(Val) >> 56)\n"
63 << "#else\n"
64 << "#define " << EncodeMacroName << "2(Val)"
65 << " uint8_t((Val) >> 8), uint8_t(Val)\n"
66 << "#define " << EncodeMacroName << "4(Val)"
67 << " uint8_t((Val) >> 24), uint8_t((Val) >> 16), "
68 "uint8_t((Val) >> 8), uint8_t(Val)\n"
69 << "#define " << EncodeMacroName << "8(Val)"
70 << " uint8_t(uint64_t(Val) >> 56), uint8_t(uint64_t(Val) >> 48), "
71 "uint8_t(uint64_t(Val) >> 40), uint8_t(uint64_t(Val) >> 32), "
72 "uint8_t((Val) >> 24), uint8_t((Val) >> 16), "
73 "uint8_t((Val) >> 8), uint8_t(Val)\n"
74 << "#endif\n";
75}
76
77void llvm::gi::emitEncodingMacrosUndef(raw_ostream &OS) {
78 OS << "#undef " << EncodeMacroName << "2\n"
79 << "#undef " << EncodeMacroName << "4\n"
80 << "#undef " << EncodeMacroName << "8\n";
81}
82
83std::string
84llvm::gi::getNameForFeatureBitset(ArrayRef<const Record *> FeatureBitset,
85 int HwModeIdx) {
86 std::string Name = "GIFBS";
87 for (const Record *Feature : FeatureBitset)
88 Name += ("_" + Feature->getName()).str();
89 if (HwModeIdx >= 0)
90 Name += ("_HwMode" + std::to_string(val: HwModeIdx));
91 return Name;
92}
93
94template <class GroupT>
95std::vector<Matcher *>
96llvm::gi::optimizeRules(ArrayRef<Matcher *> Rules,
97 std::vector<std::unique_ptr<Matcher>> &MatcherStorage) {
98
99 std::vector<Matcher *> OptRules;
100 std::unique_ptr<GroupT> CurrentGroup = std::make_unique<GroupT>();
101 assert(CurrentGroup->empty() && "Newly created group isn't empty!");
102 unsigned NumGroups = 0;
103
104 auto ProcessCurrentGroup = [&]() {
105 if (CurrentGroup->empty())
106 // An empty group is good to be reused:
107 return;
108
109 // If the group isn't large enough to provide any benefit, move all the
110 // added rules out of it and make sure to re-create the group to properly
111 // re-initialize it:
112 if (CurrentGroup->size() < 2)
113 append_range(OptRules, CurrentGroup->matchers());
114 else {
115 CurrentGroup->finalize();
116 OptRules.push_back(CurrentGroup.get());
117 MatcherStorage.emplace_back(std::move(CurrentGroup));
118 ++NumGroups;
119 }
120 CurrentGroup = std::make_unique<GroupT>();
121 };
122 for (Matcher *Rule : Rules) {
123 // Greedily add as many matchers as possible to the current group:
124 if (CurrentGroup->addMatcher(*Rule))
125 continue;
126
127 ProcessCurrentGroup();
128 assert(CurrentGroup->empty() && "A group wasn't properly re-initialized");
129
130 // Try to add the pending matcher to a newly created empty group:
131 if (!CurrentGroup->addMatcher(*Rule))
132 // If we couldn't add the matcher to an empty group, that group type
133 // doesn't support that kind of matchers at all, so just skip it:
134 OptRules.push_back(x: Rule);
135 }
136 ProcessCurrentGroup();
137
138 LLVM_DEBUG(dbgs() << "NumGroups: " << NumGroups << "\n");
139 (void)NumGroups;
140 assert(CurrentGroup->empty() && "The last group wasn't properly processed");
141 return OptRules;
142}
143
144template std::vector<Matcher *> llvm::gi::optimizeRules<GroupMatcher>(
145 ArrayRef<Matcher *> Rules,
146 std::vector<std::unique_ptr<Matcher>> &MatcherStorage);
147
148template std::vector<Matcher *> llvm::gi::optimizeRules<SwitchMatcher>(
149 ArrayRef<Matcher *> Rules,
150 std::vector<std::unique_ptr<Matcher>> &MatcherStorage);
151
152static std::string getEncodedEmitStr(StringRef NamedValue, unsigned NumBytes) {
153 if (NumBytes == 2 || NumBytes == 4 || NumBytes == 8)
154 return (EncodeMacroName + Twine(NumBytes) + "(" + NamedValue + ")").str();
155 llvm_unreachable("Unsupported number of bytes!");
156}
157
158template <class Range> static bool matchersRecordOperand(Range &&R) {
159 return any_of(R, [](const auto &I) { return I->recordsOperand(); });
160}
161
162//===- Global Data --------------------------------------------------------===//
163
164std::set<LLTCodeGen> llvm::gi::KnownTypes;
165
166//===- MatchTableRecord ---------------------------------------------------===//
167
168void MatchTableRecord::emit(raw_ostream &OS, bool LineBreakIsNextAfterThis,
169 const MatchTable &Table) const {
170 bool UseLineComment =
171 LineBreakIsNextAfterThis || (Flags & MTRF_LineBreakFollows);
172 if (Flags & (MTRF_JumpTarget | MTRF_CommaFollows))
173 UseLineComment = false;
174
175 if (Flags & MTRF_Comment)
176 OS << (UseLineComment ? "// " : "/*");
177
178 if (NumElements > 1 && !(Flags & (MTRF_PreEncoded | MTRF_Comment)))
179 OS << getEncodedEmitStr(NamedValue: EmitStr, NumBytes: NumElements);
180 else
181 OS << EmitStr;
182
183 if (Flags & MTRF_Label)
184 OS << ": @" << Table.getLabelIndex(LabelID);
185
186 if ((Flags & MTRF_Comment) && !UseLineComment)
187 OS << "*/";
188
189 if (Flags & MTRF_JumpTarget) {
190 if (Flags & MTRF_Comment)
191 OS << " ";
192 // TODO: Could encode this AOT to speed up build of generated file
193 OS << getEncodedEmitStr(NamedValue: llvm::to_string(Value: Table.getLabelIndex(LabelID)),
194 NumBytes: NumElements);
195 }
196
197 if (Flags & MTRF_CommaFollows) {
198 OS << ",";
199 if (!LineBreakIsNextAfterThis && !(Flags & MTRF_LineBreakFollows))
200 OS << " ";
201 }
202
203 if (Flags & MTRF_LineBreakFollows)
204 OS << "\n";
205}
206
207//===- MatchTable ---------------------------------------------------------===//
208
209MatchTableRecord MatchTable::LineBreak = {
210 std::nullopt, "" /* Emit String */, 0 /* Elements */,
211 MatchTableRecord::MTRF_LineBreakFollows};
212
213MatchTableRecord MatchTable::Comment(StringRef Comment) {
214 return MatchTableRecord(std::nullopt, Comment, 0,
215 MatchTableRecord::MTRF_Comment);
216}
217
218MatchTableRecord MatchTable::Opcode(StringRef Opcode, int IndentAdjust) {
219 unsigned ExtraFlags = 0;
220 if (IndentAdjust > 0)
221 ExtraFlags |= MatchTableRecord::MTRF_Indent;
222 if (IndentAdjust < 0)
223 ExtraFlags |= MatchTableRecord::MTRF_Outdent;
224
225 return MatchTableRecord(std::nullopt, Opcode, 1,
226 MatchTableRecord::MTRF_CommaFollows | ExtraFlags);
227}
228
229MatchTableRecord MatchTable::NamedValue(unsigned NumBytes,
230 StringRef NamedValue) {
231 return MatchTableRecord(std::nullopt, NamedValue, NumBytes,
232 MatchTableRecord::MTRF_CommaFollows);
233}
234
235MatchTableRecord MatchTable::NamedValue(unsigned NumBytes, StringRef Namespace,
236 StringRef NamedValue) {
237 return MatchTableRecord(std::nullopt, (Namespace + "::" + NamedValue).str(),
238 NumBytes, MatchTableRecord::MTRF_CommaFollows);
239}
240
241MatchTableRecord MatchTable::IntValue(unsigned NumBytes, int64_t IntValue) {
242 assert(isUIntN(NumBytes * 8, IntValue) || isIntN(NumBytes * 8, IntValue));
243 uint64_t UIntValue = IntValue;
244 if (NumBytes < 8)
245 UIntValue &= (UINT64_C(1) << NumBytes * 8) - 1;
246 std::string Str = llvm::to_string(Value: UIntValue);
247 if (UIntValue > INT64_MAX)
248 Str += 'u';
249 // TODO: Could optimize this directly to save the compiler some work when
250 // building the file
251 return MatchTableRecord(std::nullopt, Str, NumBytes,
252 MatchTableRecord::MTRF_CommaFollows);
253}
254
255MatchTableRecord MatchTable::ULEB128Value(uint64_t IntValue) {
256 uint8_t Buffer[10];
257 unsigned Len = encodeULEB128(Value: IntValue, p: Buffer);
258
259 // Simple case (most common)
260 if (Len == 1) {
261 return MatchTableRecord(std::nullopt, llvm::to_string(Value: (unsigned)Buffer[0]),
262 1, MatchTableRecord::MTRF_CommaFollows);
263 }
264
265 // Print it as, e.g. /* -123456 (*/, 0xC0, 0xBB, 0x78 /*)*/
266 std::string Str;
267 raw_string_ostream OS(Str);
268 OS << "/* " << llvm::to_string(Value: IntValue) << "(*/";
269 for (unsigned K = 0; K < Len; ++K) {
270 if (K)
271 OS << ", ";
272 OS << "0x" << llvm::toHex(Input: {Buffer[K]});
273 }
274 OS << "/*)*/";
275 return MatchTableRecord(std::nullopt, Str, Len,
276 MatchTableRecord::MTRF_CommaFollows |
277 MatchTableRecord::MTRF_PreEncoded);
278}
279
280MatchTableRecord MatchTable::Label(unsigned LabelID) {
281 return MatchTableRecord(LabelID, "Label " + llvm::to_string(Value: LabelID), 0,
282 MatchTableRecord::MTRF_Label |
283 MatchTableRecord::MTRF_Comment |
284 MatchTableRecord::MTRF_LineBreakFollows);
285}
286
287MatchTableRecord MatchTable::JumpTarget(unsigned LabelID) {
288 return MatchTableRecord(LabelID, "Label " + llvm::to_string(Value: LabelID), 4,
289 MatchTableRecord::MTRF_JumpTarget |
290 MatchTableRecord::MTRF_Comment |
291 MatchTableRecord::MTRF_CommaFollows);
292}
293
294void MatchTable::emitUse(raw_ostream &OS) const { OS << "MatchTable" << ID; }
295
296void MatchTable::emitDeclaration(raw_ostream &OS) const {
297 static constexpr unsigned BaseIndent = 4;
298 unsigned Indentation = 0;
299 OS << " constexpr static uint8_t MatchTable" << ID << "[] = {";
300 LineBreak.emit(OS, LineBreakIsNextAfterThis: true, Table: *this);
301
302 // We want to display the table index of each line in a consistent
303 // manner. It has to appear as a column on the left side of the table.
304 // To determine how wide the column needs to be, check how many characters
305 // we need to fit the largest possible index in the current table.
306 const unsigned NumColsForIdx = llvm::to_string(Value: CurrentSize).size();
307
308 unsigned CurIndex = 0;
309 const auto BeginLine = [&]() {
310 OS.indent(NumSpaces: BaseIndent);
311 std::string IdxStr = llvm::to_string(Value: CurIndex);
312 // Pad the string with spaces to keep the size of the prefix consistent.
313 OS << " /* ";
314 OS.indent(NumSpaces: NumColsForIdx - IdxStr.size()) << IdxStr << " */ ";
315 OS.indent(NumSpaces: Indentation);
316 };
317
318 BeginLine();
319 for (auto I = Contents.begin(), E = Contents.end(); I != E; ++I) {
320 bool LineBreakIsNext = false;
321 const auto &NextI = std::next(x: I);
322
323 if (NextI != E) {
324 if (NextI->EmitStr == "" &&
325 NextI->Flags == MatchTableRecord::MTRF_LineBreakFollows)
326 LineBreakIsNext = true;
327 }
328
329 if (I->Flags & MatchTableRecord::MTRF_Indent)
330 Indentation += 2;
331
332 I->emit(OS, LineBreakIsNextAfterThis: LineBreakIsNext, Table: *this);
333 if (I->Flags & MatchTableRecord::MTRF_LineBreakFollows)
334 BeginLine();
335
336 if (I->Flags & MatchTableRecord::MTRF_Outdent)
337 Indentation -= 2;
338
339 CurIndex += I->size();
340 }
341 assert(CurIndex == CurrentSize);
342 OS << "}; // Size: " << CurrentSize << " bytes\n";
343}
344
345MatchTable MatchTable::buildTable(ArrayRef<Matcher *> Rules, bool WithCoverage,
346 bool IsCombiner) {
347 MatchTable Table(WithCoverage, IsCombiner);
348 for (Matcher *Rule : Rules)
349 Rule->emit(Table);
350
351 return Table << MatchTable::Opcode(Opcode: "GIM_Reject") << MatchTable::LineBreak;
352}
353
354//===- LLTCodeGen ---------------------------------------------------------===//
355
356std::string LLTCodeGen::getCxxEnumValue() const {
357 std::string Str;
358 raw_string_ostream OS(Str);
359
360 emitCxxEnumValue(OS);
361 return Str;
362}
363
364void LLTCodeGen::emitCxxEnumValue(raw_ostream &OS) const {
365 if (Ty.isScalar()) {
366 OS << "GILLT_s" << Ty.getSizeInBits();
367 return;
368 }
369 if (Ty.isVector()) {
370 OS << (Ty.isScalable() ? "GILLT_nxv" : "GILLT_v")
371 << Ty.getElementCount().getKnownMinValue() << "s"
372 << Ty.getScalarSizeInBits();
373 return;
374 }
375 if (Ty.isPointer()) {
376 OS << "GILLT_p" << Ty.getAddressSpace();
377 if (Ty.getSizeInBits() > 0)
378 OS << "s" << Ty.getSizeInBits();
379 return;
380 }
381 llvm_unreachable("Unhandled LLT");
382}
383
384void LLTCodeGen::emitCxxConstructorCall(raw_ostream &OS) const {
385 if (Ty.isScalar()) {
386 OS << "LLT::scalar(" << Ty.getSizeInBits() << ")";
387 return;
388 }
389 if (Ty.isVector()) {
390 OS << "LLT::vector("
391 << (Ty.isScalable() ? "ElementCount::getScalable("
392 : "ElementCount::getFixed(")
393 << Ty.getElementCount().getKnownMinValue() << "), "
394 << Ty.getScalarSizeInBits() << ")";
395 return;
396 }
397 if (Ty.isPointer() && Ty.getSizeInBits() > 0) {
398 OS << "LLT::pointer(" << Ty.getAddressSpace() << ", " << Ty.getSizeInBits()
399 << ")";
400 return;
401 }
402 llvm_unreachable("Unhandled LLT");
403}
404
405/// This ordering is used for std::unique() and llvm::sort(). There's no
406/// particular logic behind the order but either A < B or B < A must be
407/// true if A != B.
408bool LLTCodeGen::operator<(const LLTCodeGen &Other) const {
409 if (Ty.isValid() != Other.Ty.isValid())
410 return Ty.isValid() < Other.Ty.isValid();
411 if (!Ty.isValid())
412 return false;
413
414 if (Ty.isVector() != Other.Ty.isVector())
415 return Ty.isVector() < Other.Ty.isVector();
416 if (Ty.isScalar() != Other.Ty.isScalar())
417 return Ty.isScalar() < Other.Ty.isScalar();
418 if (Ty.isPointer() != Other.Ty.isPointer())
419 return Ty.isPointer() < Other.Ty.isPointer();
420
421 if (Ty.isPointer() && Ty.getAddressSpace() != Other.Ty.getAddressSpace())
422 return Ty.getAddressSpace() < Other.Ty.getAddressSpace();
423
424 if (Ty.isVector() && Ty.getElementCount() != Other.Ty.getElementCount())
425 return std::tuple(Ty.isScalable(),
426 Ty.getElementCount().getKnownMinValue()) <
427 std::tuple(Other.Ty.isScalable(),
428 Other.Ty.getElementCount().getKnownMinValue());
429
430 assert((!Ty.isVector() || Ty.isScalable() == Other.Ty.isScalable()) &&
431 "Unexpected mismatch of scalable property");
432 return Ty.isVector()
433 ? std::tuple(Ty.isScalable(),
434 Ty.getSizeInBits().getKnownMinValue()) <
435 std::tuple(Other.Ty.isScalable(),
436 Other.Ty.getSizeInBits().getKnownMinValue())
437 : Ty.getSizeInBits().getFixedValue() <
438 Other.Ty.getSizeInBits().getFixedValue();
439}
440
441//===- LLTCodeGen Helpers -------------------------------------------------===//
442
443std::optional<LLTCodeGen> llvm::gi::MVTToLLT(MVT VT) {
444 if (VT.isVector() && !VT.getVectorElementCount().isScalar())
445 return LLTCodeGen(
446 LLT::vector(EC: VT.getVectorElementCount(), ScalarSizeInBits: VT.getScalarSizeInBits()));
447
448 if (VT.isInteger() || VT.isFloatingPoint())
449 return LLTCodeGen(LLT::scalar(SizeInBits: VT.getSizeInBits()));
450
451 return std::nullopt;
452}
453
454//===- Matcher ------------------------------------------------------------===//
455
456void Matcher::optimize() {}
457
458Matcher::~Matcher() = default;
459
460//===- GroupMatcher -------------------------------------------------------===//
461
462bool GroupMatcher::recordsOperand() const {
463 return matchersRecordOperand(R: Conditions) || matchersRecordOperand(R: Matchers);
464}
465
466bool GroupMatcher::candidateConditionMatches(
467 const PredicateMatcher &Predicate) const {
468
469 if (empty()) {
470 // Sharing predicates for nested instructions is not supported yet as we
471 // currently don't hoist the GIM_RecordInsn's properly, therefore we can
472 // only work on the original root instruction (InsnVarID == 0):
473 if (Predicate.getInsnVarID() != 0)
474 return false;
475 // ... otherwise an empty group can handle any predicate with no specific
476 // requirements:
477 return true;
478 }
479
480 const Matcher &Representative = **Matchers.begin();
481 const auto &RepresentativeCondition = Representative.getFirstCondition();
482 // ... if not empty, the group can only accomodate matchers with the exact
483 // same first condition:
484 return Predicate.isIdentical(B: RepresentativeCondition);
485}
486
487std::unique_ptr<PredicateMatcher> GroupMatcher::popFirstCondition() {
488 assert(!Conditions.empty() &&
489 "Trying to pop a condition from a condition-less group");
490 std::unique_ptr<PredicateMatcher> P = std::move(Conditions.front());
491 Conditions.erase(CI: Conditions.begin());
492 return P;
493}
494
495/// Check if the Condition, which is a predicate of M, cannot be hoisted outside
496/// of (i.e., checked before) M.
497static bool cannotHoistCondition(const PredicateMatcher &Condition,
498 const Matcher &M) {
499 // The condition can't be hoisted if it is a C++ predicate that refers to
500 // operands and the operands are registered within the matcher.
501 return Condition.dependsOnOperands() && M.recordsOperand();
502}
503
504bool GroupMatcher::addMatcher(Matcher &Candidate) {
505 if (!Candidate.hasFirstCondition())
506 return false;
507
508 // Only add candidates that have a matching first condition that can be
509 // hoisted into the GroupMatcher.
510 const PredicateMatcher &Predicate = Candidate.getFirstCondition();
511 if (!candidateConditionMatches(Predicate) ||
512 cannotHoistCondition(Condition: Predicate, M: Candidate))
513 return false;
514
515 Matchers.push_back(x: &Candidate);
516 return true;
517}
518
519void GroupMatcher::finalize() {
520 assert(Conditions.empty() && "Already finalized?");
521 if (empty())
522 return;
523
524 Matcher &FirstRule = **Matchers.begin();
525 for (;;) {
526 // All the checks are expected to succeed during the first iteration:
527 for (const auto &Rule : Matchers)
528 if (!Rule->hasFirstCondition())
529 return;
530 // Hoist the first condition if it is identical in all matchers in the group
531 // and it can be hoisted in every matcher.
532 const auto &FirstCondition = FirstRule.getFirstCondition();
533 if (cannotHoistCondition(Condition: FirstCondition, M: FirstRule))
534 return;
535 for (unsigned I = 1, E = Matchers.size(); I < E; ++I) {
536 const auto &OtherFirstCondition = Matchers[I]->getFirstCondition();
537 if (!OtherFirstCondition.isIdentical(B: FirstCondition) ||
538 cannotHoistCondition(Condition: OtherFirstCondition, M: *Matchers[I]))
539 return;
540 }
541
542 Conditions.push_back(Elt: FirstRule.popFirstCondition());
543 for (unsigned I = 1, E = Matchers.size(); I < E; ++I)
544 Matchers[I]->popFirstCondition();
545 }
546}
547
548void GroupMatcher::emit(MatchTable &Table) {
549 unsigned LabelID = ~0U;
550 if (!Conditions.empty()) {
551 LabelID = Table.allocateLabelID();
552 Table << MatchTable::Opcode(Opcode: "GIM_Try", IndentAdjust: +1)
553 << MatchTable::Comment(Comment: "On fail goto")
554 << MatchTable::JumpTarget(LabelID) << MatchTable::LineBreak;
555 }
556 for (auto &Condition : Conditions)
557 Condition->emitPredicateOpcodes(
558 Table, Rule&: *static_cast<RuleMatcher *>(*Matchers.begin()));
559
560 for (const auto &M : Matchers)
561 M->emit(Table);
562
563 // Exit the group
564 if (!Conditions.empty())
565 Table << MatchTable::Opcode(Opcode: "GIM_Reject", IndentAdjust: -1) << MatchTable::LineBreak
566 << MatchTable::Label(LabelID);
567}
568
569void GroupMatcher::optimize() {
570 // Make sure we only sort by a specific predicate within a range of rules that
571 // all have that predicate checked against a specific value (not a wildcard):
572 auto F = Matchers.begin();
573 auto T = F;
574 auto E = Matchers.end();
575 while (T != E) {
576 while (T != E) {
577 auto *R = static_cast<RuleMatcher *>(*T);
578 if (!R->getFirstConditionAsRootType().get().isValid())
579 break;
580 ++T;
581 }
582 std::stable_sort(first: F, last: T, comp: [](Matcher *A, Matcher *B) {
583 auto *L = static_cast<RuleMatcher *>(A);
584 auto *R = static_cast<RuleMatcher *>(B);
585 return L->getFirstConditionAsRootType() <
586 R->getFirstConditionAsRootType();
587 });
588 if (T != E)
589 F = ++T;
590 }
591 Matchers = optimizeRules<GroupMatcher>(Rules: Matchers, MatcherStorage);
592 Matchers = optimizeRules<SwitchMatcher>(Rules: Matchers, MatcherStorage);
593}
594
595//===- SwitchMatcher ------------------------------------------------------===//
596
597bool SwitchMatcher::recordsOperand() const {
598 assert(!isa_and_present<RecordNamedOperandMatcher>(Condition.get()) &&
599 "Switch conditions should not record named operands");
600 return matchersRecordOperand(R: Matchers);
601}
602
603bool SwitchMatcher::isSupportedPredicateType(const PredicateMatcher &P) {
604 return isa<InstructionOpcodeMatcher>(Val: P) || isa<LLTOperandMatcher>(Val: P);
605}
606
607bool SwitchMatcher::candidateConditionMatches(
608 const PredicateMatcher &Predicate) const {
609
610 if (empty()) {
611 // Sharing predicates for nested instructions is not supported yet as we
612 // currently don't hoist the GIM_RecordInsn's properly, therefore we can
613 // only work on the original root instruction (InsnVarID == 0):
614 if (Predicate.getInsnVarID() != 0)
615 return false;
616 // ... while an attempt to add even a root matcher to an empty SwitchMatcher
617 // could fail as not all the types of conditions are supported:
618 if (!isSupportedPredicateType(P: Predicate))
619 return false;
620 // ... or the condition might not have a proper implementation of
621 // getValue() / isIdenticalDownToValue() yet:
622 if (!Predicate.hasValue())
623 return false;
624 // ... otherwise an empty Switch can accomodate the condition with no
625 // further requirements:
626 return true;
627 }
628
629 const Matcher &CaseRepresentative = **Matchers.begin();
630 const auto &RepresentativeCondition = CaseRepresentative.getFirstCondition();
631 // Switch-cases must share the same kind of condition and path to the value it
632 // checks:
633 if (!Predicate.isIdenticalDownToValue(B: RepresentativeCondition))
634 return false;
635
636 const auto Value = Predicate.getValue();
637 // ... but be unique with respect to the actual value they check:
638 return Values.count(x: Value) == 0;
639}
640
641bool SwitchMatcher::addMatcher(Matcher &Candidate) {
642 if (!Candidate.hasFirstCondition())
643 return false;
644
645 const PredicateMatcher &Predicate = Candidate.getFirstCondition();
646 if (!candidateConditionMatches(Predicate))
647 return false;
648 const auto Value = Predicate.getValue();
649 Values.insert(x: Value);
650
651 Matchers.push_back(x: &Candidate);
652 return true;
653}
654
655void SwitchMatcher::finalize() {
656 assert(Condition == nullptr && "Already finalized");
657 assert(Values.size() == Matchers.size() && "Broken SwitchMatcher");
658 if (empty())
659 return;
660
661 llvm::stable_sort(Range&: Matchers, C: [](const Matcher *L, const Matcher *R) {
662 return L->getFirstCondition().getValue() <
663 R->getFirstCondition().getValue();
664 });
665 Condition = Matchers[0]->popFirstCondition();
666 for (unsigned I = 1, E = Values.size(); I < E; ++I)
667 Matchers[I]->popFirstCondition();
668}
669
670void SwitchMatcher::emitPredicateSpecificOpcodes(const PredicateMatcher &P,
671 MatchTable &Table) {
672 assert(isSupportedPredicateType(P) && "Predicate type is not supported");
673
674 if (const auto *Condition = dyn_cast<InstructionOpcodeMatcher>(Val: &P)) {
675 Table << MatchTable::Opcode(Opcode: "GIM_SwitchOpcode") << MatchTable::Comment(Comment: "MI")
676 << MatchTable::ULEB128Value(IntValue: Condition->getInsnVarID());
677 return;
678 }
679 if (const auto *Condition = dyn_cast<LLTOperandMatcher>(Val: &P)) {
680 Table << MatchTable::Opcode(Opcode: "GIM_SwitchType") << MatchTable::Comment(Comment: "MI")
681 << MatchTable::ULEB128Value(IntValue: Condition->getInsnVarID())
682 << MatchTable::Comment(Comment: "Op")
683 << MatchTable::ULEB128Value(IntValue: Condition->getOpIdx());
684 return;
685 }
686
687 llvm_unreachable("emitPredicateSpecificOpcodes is broken: can not handle a "
688 "predicate type that is claimed to be supported");
689}
690
691void SwitchMatcher::emit(MatchTable &Table) {
692 assert(Values.size() == Matchers.size() && "Broken SwitchMatcher");
693 if (empty())
694 return;
695 assert(Condition != nullptr &&
696 "Broken SwitchMatcher, hasn't been finalized?");
697
698 std::vector<unsigned> LabelIDs(Values.size());
699 std::generate(first: LabelIDs.begin(), last: LabelIDs.end(),
700 gen: [&Table]() { return Table.allocateLabelID(); });
701 const unsigned Default = Table.allocateLabelID();
702
703 const int64_t LowerBound = Values.begin()->RawValue;
704 const int64_t UpperBound = Values.rbegin()->RawValue + 1;
705
706 emitPredicateSpecificOpcodes(P: *Condition, Table);
707
708 Table << MatchTable::Comment(Comment: "[") << MatchTable::IntValue(NumBytes: 2, IntValue: LowerBound)
709 << MatchTable::IntValue(NumBytes: 2, IntValue: UpperBound) << MatchTable::Comment(Comment: ")")
710 << MatchTable::Comment(Comment: "default:") << MatchTable::JumpTarget(LabelID: Default);
711
712 int64_t J = LowerBound;
713 auto VI = Values.begin();
714 for (unsigned I = 0, E = Values.size(); I < E; ++I) {
715 auto V = *VI++;
716 while (J++ < V.RawValue)
717 Table << MatchTable::IntValue(NumBytes: 4, IntValue: 0);
718 V.Record.turnIntoComment();
719 Table << MatchTable::LineBreak << V.Record
720 << MatchTable::JumpTarget(LabelID: LabelIDs[I]);
721 }
722 Table << MatchTable::LineBreak;
723
724 for (unsigned I = 0, E = Values.size(); I < E; ++I) {
725 Table << MatchTable::Label(LabelID: LabelIDs[I]);
726 Matchers[I]->emit(Table);
727 Table << MatchTable::Opcode(Opcode: "GIM_Reject") << MatchTable::LineBreak;
728 }
729 Table << MatchTable::Label(LabelID: Default);
730}
731
732//===- RuleMatcher --------------------------------------------------------===//
733
734RuleMatcher::RuleMatcher(ArrayRef<SMLoc> SrcLoc)
735 : SrcLoc(SrcLoc), RuleID(NextRuleID++) {}
736
737uint64_t RuleMatcher::NextRuleID = 0;
738
739StringRef RuleMatcher::getOpcode() const {
740 return Matchers.front()->getOpcode();
741}
742
743bool RuleMatcher::recordsOperand() const {
744 return matchersRecordOperand(R: Matchers);
745}
746
747LLTCodeGen RuleMatcher::getFirstConditionAsRootType() {
748 InstructionMatcher &InsnMatcher = *Matchers.front();
749 if (!InsnMatcher.predicates_empty())
750 if (const auto *TM =
751 dyn_cast<LLTOperandMatcher>(Val: &**InsnMatcher.predicates_begin()))
752 if (TM->getInsnVarID() == 0 && TM->getOpIdx() == 0)
753 return TM->getTy();
754 return {};
755}
756
757void RuleMatcher::optimize() {
758 for (auto &Item : InsnVariableIDs) {
759 InstructionMatcher &InsnMatcher = *Item.first;
760 for (auto &OM : InsnMatcher.operands()) {
761 // Complex Patterns are usually expensive and they relatively rarely fail
762 // on their own: more often we end up throwing away all the work done by a
763 // matching part of a complex pattern because some other part of the
764 // enclosing pattern didn't match. All of this makes it beneficial to
765 // delay complex patterns until the very end of the rule matching,
766 // especially for targets having lots of complex patterns.
767 for (auto &OP : OM->predicates())
768 if (isa<ComplexPatternOperandMatcher>(Val: OP))
769 EpilogueMatchers.emplace_back(args: std::move(OP));
770 OM->eraseNullPredicates();
771 }
772 InsnMatcher.optimize();
773 }
774 llvm::sort(C&: EpilogueMatchers, Comp: [](const std::unique_ptr<PredicateMatcher> &L,
775 const std::unique_ptr<PredicateMatcher> &R) {
776 return std::tuple(L->getKind(), L->getInsnVarID(), L->getOpIdx()) <
777 std::tuple(R->getKind(), R->getInsnVarID(), R->getOpIdx());
778 });
779
780 // Deduplicate EraseInst actions, and if an EraseInst erases the root, place
781 // it at the end to favor generation of GIR_EraseRootFromParent_Done
782 DenseSet<unsigned> AlreadySeenEraseInsts;
783 auto EraseRootIt = Actions.end();
784 auto It = Actions.begin();
785 while (It != Actions.end()) {
786 if (const auto *EI = dyn_cast<EraseInstAction>(Val: It->get())) {
787 unsigned InstID = EI->getInsnID();
788 if (!AlreadySeenEraseInsts.insert(V: InstID).second) {
789 It = Actions.erase(position: It);
790 continue;
791 }
792
793 if (InstID == 0)
794 EraseRootIt = It;
795 }
796
797 ++It;
798 }
799
800 if (EraseRootIt != Actions.end())
801 Actions.splice(position: Actions.end(), x&: Actions, i: EraseRootIt);
802}
803
804bool RuleMatcher::hasFirstCondition() const {
805 if (insnmatchers_empty())
806 return false;
807 InstructionMatcher &Matcher = insnmatchers_front();
808 if (!Matcher.predicates_empty())
809 return true;
810 for (auto &OM : Matcher.operands())
811 for (auto &OP : OM->predicates())
812 if (!isa<InstructionOperandMatcher>(Val: OP))
813 return true;
814 return false;
815}
816
817const PredicateMatcher &RuleMatcher::getFirstCondition() const {
818 assert(!insnmatchers_empty() &&
819 "Trying to get a condition from an empty RuleMatcher");
820
821 InstructionMatcher &Matcher = insnmatchers_front();
822 if (!Matcher.predicates_empty())
823 return **Matcher.predicates_begin();
824 // If there is no more predicate on the instruction itself, look at its
825 // operands.
826 for (auto &OM : Matcher.operands())
827 for (auto &OP : OM->predicates())
828 if (!isa<InstructionOperandMatcher>(Val: OP))
829 return *OP;
830
831 llvm_unreachable("Trying to get a condition from an InstructionMatcher with "
832 "no conditions");
833}
834
835std::unique_ptr<PredicateMatcher> RuleMatcher::popFirstCondition() {
836 assert(!insnmatchers_empty() &&
837 "Trying to pop a condition from an empty RuleMatcher");
838
839 InstructionMatcher &Matcher = insnmatchers_front();
840 if (!Matcher.predicates_empty())
841 return Matcher.predicates_pop_front();
842 // If there is no more predicate on the instruction itself, look at its
843 // operands.
844 for (auto &OM : Matcher.operands())
845 for (auto &OP : OM->predicates())
846 if (!isa<InstructionOperandMatcher>(Val: OP)) {
847 std::unique_ptr<PredicateMatcher> Result = std::move(OP);
848 OM->eraseNullPredicates();
849 return Result;
850 }
851
852 llvm_unreachable("Trying to pop a condition from an InstructionMatcher with "
853 "no conditions");
854}
855
856GISelFlags RuleMatcher::updateGISelFlag(GISelFlags CurFlags, const Record *R,
857 StringRef FlagName,
858 GISelFlags FlagBit) {
859 // If the value of a flag is unset, ignore it.
860 // If it's set, it always takes precedence over the existing value so
861 // clear/set the corresponding bit.
862 bool Unset = false;
863 bool Value = R->getValueAsBitOrUnset(FieldName: "GIIgnoreCopies", Unset);
864 if (!Unset)
865 return Value ? (CurFlags | FlagBit) : (CurFlags & ~FlagBit);
866 return CurFlags;
867}
868
869SaveAndRestore<GISelFlags> RuleMatcher::setGISelFlags(const Record *R) {
870 if (!R || !R->isSubClassOf(Name: "GISelFlags"))
871 return {Flags, Flags};
872
873 assert((R->isSubClassOf("PatFrags") || R->isSubClassOf("Pattern")) &&
874 "GISelFlags is only expected on Pattern/PatFrags!");
875
876 GISelFlags NewFlags =
877 updateGISelFlag(CurFlags: Flags, R, FlagName: "GIIgnoreCopies", FlagBit: GISF_IgnoreCopies);
878 return {Flags, NewFlags};
879}
880
881Error RuleMatcher::defineComplexSubOperand(StringRef SymbolicName,
882 const Record *ComplexPattern,
883 unsigned RendererID,
884 unsigned SubOperandID,
885 StringRef ParentSymbolicName) {
886 std::string ParentName(ParentSymbolicName);
887 auto [It, Inserted] = ComplexSubOperands.try_emplace(
888 Key: SymbolicName, Args&: ComplexPattern, Args&: RendererID, Args&: SubOperandID);
889 if (!Inserted) {
890 const std::string &RecordedParentName =
891 ComplexSubOperandsParentName[SymbolicName];
892 if (RecordedParentName != ParentName)
893 return failUnsupported(Reason: "Error: Complex suboperand " + SymbolicName +
894 " referenced by different operands: " +
895 RecordedParentName + " and " + ParentName + ".");
896 // Complex suboperand referenced more than once from same the operand is
897 // used to generate 'same operand check'. Emitting of
898 // GIR_ComplexSubOperandRenderer for them is already handled.
899 return Error::success();
900 }
901
902 ComplexSubOperandsParentName[SymbolicName] = std::move(ParentName);
903
904 return Error::success();
905}
906
907InstructionMatcher &RuleMatcher::addInstructionMatcher(StringRef SymbolicName) {
908 Matchers.emplace_back(args: new InstructionMatcher(*this, SymbolicName));
909 MutatableInsns.insert(Ptr: Matchers.back().get());
910 return *Matchers.back();
911}
912
913void RuleMatcher::addRequiredSimplePredicate(StringRef PredName) {
914 RequiredSimplePredicates.push_back(x: PredName.str());
915}
916
917const std::vector<std::string> &RuleMatcher::getRequiredSimplePredicates() {
918 return RequiredSimplePredicates;
919}
920
921unsigned RuleMatcher::implicitlyDefineInsnVar(InstructionMatcher &Matcher) {
922 unsigned NewInsnVarID = NextInsnVarID++;
923 InsnVariableIDs[&Matcher] = NewInsnVarID;
924 return NewInsnVarID;
925}
926
927unsigned RuleMatcher::getInsnVarID(InstructionMatcher &InsnMatcher) const {
928 const auto &I = InsnVariableIDs.find(x: &InsnMatcher);
929 if (I != InsnVariableIDs.end())
930 return I->second;
931 llvm_unreachable("Matched Insn was not captured in a local variable");
932}
933
934void RuleMatcher::defineOperand(StringRef SymbolicName, OperandMatcher &OM) {
935 if (DefinedOperands.try_emplace(Key: SymbolicName, Args: &OM).second)
936 return;
937
938 // If the operand is already defined, then we must ensure both references in
939 // the matcher have the exact same node.
940 RuleMatcher &RM = OM.getInstructionMatcher().getRuleMatcher();
941 OM.addPredicate<SameOperandMatcher>(
942 args: OM.getSymbolicName(), args: getOperandMatcher(Name: OM.getSymbolicName()).getOpIdx(),
943 args: RM.getGISelFlags());
944}
945
946void RuleMatcher::definePhysRegOperand(const Record *Reg, OperandMatcher &OM) {
947 PhysRegOperands.try_emplace(Key: Reg, Args: &OM);
948}
949
950InstructionMatcher &
951RuleMatcher::getInstructionMatcher(StringRef SymbolicName) const {
952 for (const auto &I : InsnVariableIDs)
953 if (I.first->getSymbolicName() == SymbolicName)
954 return *I.first;
955 llvm_unreachable(
956 ("Failed to lookup instruction " + SymbolicName).str().c_str());
957}
958
959const OperandMatcher &
960RuleMatcher::getPhysRegOperandMatcher(const Record *Reg) const {
961 const auto &I = PhysRegOperands.find(Key: Reg);
962
963 if (I == PhysRegOperands.end()) {
964 PrintFatalError(ErrorLoc: SrcLoc, Msg: "Register " + Reg->getName() +
965 " was not declared in matcher");
966 }
967
968 return *I->second;
969}
970
971OperandMatcher &RuleMatcher::getOperandMatcher(StringRef Name) {
972 const auto &I = DefinedOperands.find(Key: Name);
973
974 if (I == DefinedOperands.end())
975 PrintFatalError(ErrorLoc: SrcLoc, Msg: "Operand " + Name + " was not declared in matcher");
976
977 return *I->second;
978}
979
980const OperandMatcher &RuleMatcher::getOperandMatcher(StringRef Name) const {
981 const auto &I = DefinedOperands.find(Key: Name);
982
983 if (I == DefinedOperands.end())
984 PrintFatalError(ErrorLoc: SrcLoc, Msg: "Operand " + Name + " was not declared in matcher");
985
986 return *I->second;
987}
988
989void RuleMatcher::emit(MatchTable &Table) {
990 if (Matchers.empty())
991 llvm_unreachable("Unexpected empty matcher!");
992
993 // The representation supports rules that require multiple roots such as:
994 // %ptr(p0) = ...
995 // %elt0(s32) = G_LOAD %ptr
996 // %1(p0) = G_ADD %ptr, 4
997 // %elt1(s32) = G_LOAD p0 %1
998 // which could be usefully folded into:
999 // %ptr(p0) = ...
1000 // %elt0(s32), %elt1(s32) = TGT_LOAD_PAIR %ptr
1001 // on some targets but we don't need to make use of that yet.
1002 assert(Matchers.size() == 1 && "Cannot handle multi-root matchers yet");
1003
1004 unsigned LabelID = Table.allocateLabelID();
1005 Table << MatchTable::Opcode(Opcode: "GIM_Try", IndentAdjust: +1)
1006 << MatchTable::Comment(Comment: "On fail goto")
1007 << MatchTable::JumpTarget(LabelID)
1008 << MatchTable::Comment(Comment: ("Rule ID " + Twine(RuleID) + " //").str())
1009 << MatchTable::LineBreak;
1010
1011 if (!RequiredFeatures.empty() || HwModeIdx >= 0) {
1012 Table << MatchTable::Opcode(Opcode: "GIM_CheckFeatures")
1013 << MatchTable::NamedValue(
1014 NumBytes: 2, NamedValue: getNameForFeatureBitset(FeatureBitset: RequiredFeatures, HwModeIdx))
1015 << MatchTable::LineBreak;
1016 }
1017
1018 if (!RequiredSimplePredicates.empty()) {
1019 for (const auto &Pred : RequiredSimplePredicates) {
1020 Table << MatchTable::Opcode(Opcode: "GIM_CheckSimplePredicate")
1021 << MatchTable::NamedValue(NumBytes: 2, NamedValue: Pred) << MatchTable::LineBreak;
1022 }
1023 }
1024
1025 Matchers.front()->emitPredicateOpcodes(Table, Rule&: *this);
1026
1027 // Check if it's safe to replace registers.
1028 for (const auto &MA : Actions)
1029 MA->emitAdditionalPredicates(Table, Rule&: *this);
1030
1031 // We must also check if it's safe to fold the matched instructions.
1032 if (InsnVariableIDs.size() >= 2) {
1033
1034 // FIXME: Emit checks to determine it's _actually_ safe to fold and/or
1035 // account for unsafe cases.
1036 //
1037 // Example:
1038 // MI1--> %0 = ...
1039 // %1 = ... %0
1040 // MI0--> %2 = ... %0
1041 // It's not safe to erase MI1. We currently handle this by not
1042 // erasing %0 (even when it's dead).
1043 //
1044 // Example:
1045 // MI1--> %0 = load volatile @a
1046 // %1 = load volatile @a
1047 // MI0--> %2 = ... %0
1048 // It's not safe to sink %0's def past %1. We currently handle
1049 // this by rejecting all loads.
1050 //
1051 // Example:
1052 // MI1--> %0 = load @a
1053 // %1 = store @a
1054 // MI0--> %2 = ... %0
1055 // It's not safe to sink %0's def past %1. We currently handle
1056 // this by rejecting all loads.
1057 //
1058 // Example:
1059 // G_CONDBR %cond, @BB1
1060 // BB0:
1061 // MI1--> %0 = load @a
1062 // G_BR @BB1
1063 // BB1:
1064 // MI0--> %2 = ... %0
1065 // It's not always safe to sink %0 across control flow. In this
1066 // case it may introduce a memory fault. We currentl handle
1067 // this by rejecting all loads.
1068
1069 Table << MatchTable::Opcode(Opcode: "GIM_CheckIsSafeToFold")
1070 << MatchTable::Comment(Comment: "NumInsns")
1071 << MatchTable::IntValue(NumBytes: 1, IntValue: InsnVariableIDs.size() - 1)
1072 << MatchTable::LineBreak;
1073 }
1074
1075 for (const auto &PM : EpilogueMatchers)
1076 PM->emitPredicateOpcodes(Table, Rule&: *this);
1077
1078 if (!CustomCXXAction.empty()) {
1079 /// Handle combiners relying on custom C++ code instead of actions.
1080 assert(Table.isCombiner() && "CustomCXXAction is only for combiners!");
1081 // We cannot have actions other than debug comments.
1082 assert(none_of(Actions, [](auto &A) {
1083 return A->getKind() != MatchAction::AK_DebugComment;
1084 }));
1085 for (const auto &MA : Actions)
1086 MA->emitActionOpcodes(Table, Rule&: *this);
1087 Table << MatchTable::Opcode(Opcode: "GIR_DoneWithCustomAction", IndentAdjust: -1)
1088 << MatchTable::Comment(Comment: "Fn")
1089 << MatchTable::NamedValue(NumBytes: 2, NamedValue: CustomCXXAction)
1090 << MatchTable::LineBreak;
1091 } else {
1092 // Emit all actions except the last one, then emit coverage and emit the
1093 // final action.
1094 //
1095 // This is because some actions, such as GIR_EraseRootFromParent_Done, also
1096 // double as a GIR_Done and terminate execution of the rule.
1097 if (!Actions.empty()) {
1098 for (const auto &MA : drop_end(RangeOrContainer&: Actions))
1099 MA->emitActionOpcodes(Table, Rule&: *this);
1100 }
1101
1102 assert((Table.isWithCoverage() ? !Table.isCombiner() : true) &&
1103 "Combiner tables don't support coverage!");
1104 if (Table.isWithCoverage())
1105 Table << MatchTable::Opcode(Opcode: "GIR_Coverage")
1106 << MatchTable::IntValue(NumBytes: 4, IntValue: RuleID) << MatchTable::LineBreak;
1107 else if (!Table.isCombiner())
1108 Table << MatchTable::Comment(
1109 Comment: ("GIR_Coverage, " + Twine(RuleID) + ",").str())
1110 << MatchTable::LineBreak;
1111
1112 if (Actions.empty() ||
1113 !Actions.back()->emitActionOpcodesAndDone(Table, Rule&: *this)) {
1114 Table << MatchTable::Opcode(Opcode: "GIR_Done", IndentAdjust: -1) << MatchTable::LineBreak;
1115 }
1116 }
1117
1118 Table << MatchTable::Label(LabelID);
1119 ++NumPatternEmitted;
1120}
1121
1122bool RuleMatcher::isHigherPriorityThan(const RuleMatcher &B) const {
1123 // Rules involving more match roots have higher priority.
1124 if (Matchers.size() > B.Matchers.size())
1125 return true;
1126 if (Matchers.size() < B.Matchers.size())
1127 return false;
1128
1129 for (auto Matcher : zip(t: Matchers, u: B.Matchers)) {
1130 if (std::get<0>(t&: Matcher)->isHigherPriorityThan(B&: *std::get<1>(t&: Matcher)))
1131 return true;
1132 if (std::get<1>(t&: Matcher)->isHigherPriorityThan(B&: *std::get<0>(t&: Matcher)))
1133 return false;
1134 }
1135
1136 return false;
1137}
1138
1139unsigned RuleMatcher::countRendererFns() const {
1140 return std::accumulate(
1141 first: Matchers.begin(), last: Matchers.end(), init: 0,
1142 binary_op: [](unsigned A, const std::unique_ptr<InstructionMatcher> &Matcher) {
1143 return A + Matcher->countRendererFns();
1144 });
1145}
1146
1147void RuleMatcher::insnmatchers_pop_front() { Matchers.erase(position: Matchers.begin()); }
1148
1149//===- PredicateMatcher ---------------------------------------------------===//
1150
1151PredicateMatcher::~PredicateMatcher() = default;
1152
1153//===- OperandPredicateMatcher --------------------------------------------===//
1154
1155OperandPredicateMatcher::~OperandPredicateMatcher() = default;
1156
1157bool OperandPredicateMatcher::isHigherPriorityThan(
1158 const OperandPredicateMatcher &B) const {
1159 // Generally speaking, an instruction is more important than an Int or a
1160 // LiteralInt because it can cover more nodes but there's an exception to
1161 // this. G_CONSTANT's are less important than either of those two because they
1162 // are more permissive.
1163
1164 const auto *AOM = dyn_cast<InstructionOperandMatcher>(Val: this);
1165 const auto *BOM = dyn_cast<InstructionOperandMatcher>(Val: &B);
1166 bool AIsConstantInsn = AOM && AOM->getInsnMatcher().isConstantInstruction();
1167 bool BIsConstantInsn = BOM && BOM->getInsnMatcher().isConstantInstruction();
1168
1169 // The relative priorities between a G_CONSTANT and any other instruction
1170 // don't actually matter but this code is needed to ensure a strict weak
1171 // ordering. This is particularly important on Windows where the rules will
1172 // be incorrectly sorted without it.
1173 if (AOM && BOM)
1174 return !AIsConstantInsn && BIsConstantInsn;
1175
1176 if (AIsConstantInsn && (B.Kind == OPM_Int || B.Kind == OPM_LiteralInt))
1177 return false;
1178 if (BIsConstantInsn && (Kind == OPM_Int || Kind == OPM_LiteralInt))
1179 return true;
1180
1181 return Kind < B.Kind;
1182}
1183
1184//===- SameOperandMatcher -------------------------------------------------===//
1185
1186void SameOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
1187 RuleMatcher &Rule) const {
1188 const OperandMatcher &OtherOM = Rule.getOperandMatcher(Name: MatchingName);
1189 unsigned OtherInsnVarID = Rule.getInsnVarID(InsnMatcher&: OtherOM.getInstructionMatcher());
1190 assert(OtherInsnVarID == OtherOM.getInstructionMatcher().getInsnVarID());
1191 const bool IgnoreCopies = Flags & GISF_IgnoreCopies;
1192 Table << MatchTable::Opcode(Opcode: IgnoreCopies
1193 ? "GIM_CheckIsSameOperandIgnoreCopies"
1194 : "GIM_CheckIsSameOperand")
1195 << MatchTable::Comment(Comment: "MI") << MatchTable::ULEB128Value(IntValue: InsnVarID)
1196 << MatchTable::Comment(Comment: "OpIdx") << MatchTable::ULEB128Value(IntValue: OpIdx)
1197 << MatchTable::Comment(Comment: "OtherMI")
1198 << MatchTable::ULEB128Value(IntValue: OtherInsnVarID)
1199 << MatchTable::Comment(Comment: "OtherOpIdx")
1200 << MatchTable::ULEB128Value(IntValue: OtherOM.getOpIdx())
1201 << MatchTable::LineBreak;
1202}
1203
1204//===- LLTOperandMatcher --------------------------------------------------===//
1205
1206std::map<LLTCodeGen, unsigned> LLTOperandMatcher::TypeIDValues;
1207
1208RecordAndValue LLTOperandMatcher::getValue() const {
1209 const auto VI = TypeIDValues.find(x: Ty);
1210 if (VI == TypeIDValues.end())
1211 return MatchTable::NamedValue(NumBytes: 1, NamedValue: getTy().getCxxEnumValue());
1212 return {MatchTable::NamedValue(NumBytes: 1, NamedValue: getTy().getCxxEnumValue()), VI->second};
1213}
1214
1215bool LLTOperandMatcher::hasValue() const {
1216 if (TypeIDValues.size() != KnownTypes.size())
1217 initTypeIDValuesMap();
1218 return TypeIDValues.count(x: Ty);
1219}
1220
1221void LLTOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
1222 RuleMatcher &Rule) const {
1223 if (InsnVarID == 0) {
1224 Table << MatchTable::Opcode(Opcode: "GIM_RootCheckType");
1225 } else {
1226 Table << MatchTable::Opcode(Opcode: "GIM_CheckType") << MatchTable::Comment(Comment: "MI")
1227 << MatchTable::ULEB128Value(IntValue: InsnVarID);
1228 }
1229 Table << MatchTable::Comment(Comment: "Op") << MatchTable::ULEB128Value(IntValue: OpIdx)
1230 << MatchTable::Comment(Comment: "Type") << getValue().Record
1231 << MatchTable::LineBreak;
1232}
1233
1234//===- PointerToAnyOperandMatcher -----------------------------------------===//
1235
1236void PointerToAnyOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
1237 RuleMatcher &Rule) const {
1238 Table << MatchTable::Opcode(Opcode: "GIM_CheckPointerToAny")
1239 << MatchTable::Comment(Comment: "MI") << MatchTable::ULEB128Value(IntValue: InsnVarID)
1240 << MatchTable::Comment(Comment: "Op") << MatchTable::ULEB128Value(IntValue: OpIdx)
1241 << MatchTable::Comment(Comment: "SizeInBits")
1242 << MatchTable::ULEB128Value(IntValue: SizeInBits) << MatchTable::LineBreak;
1243}
1244
1245//===- RecordNamedOperandMatcher ------------------------------------------===//
1246
1247void RecordNamedOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
1248 RuleMatcher &Rule) const {
1249 Table << MatchTable::Opcode(Opcode: "GIM_RecordNamedOperand")
1250 << MatchTable::Comment(Comment: "MI") << MatchTable::ULEB128Value(IntValue: InsnVarID)
1251 << MatchTable::Comment(Comment: "Op") << MatchTable::ULEB128Value(IntValue: OpIdx)
1252 << MatchTable::Comment(Comment: "StoreIdx") << MatchTable::ULEB128Value(IntValue: StoreIdx)
1253 << MatchTable::Comment(Comment: "Name : " + Name) << MatchTable::LineBreak;
1254}
1255
1256//===- RecordRegisterType ------------------------------------------===//
1257
1258void RecordRegisterType::emitPredicateOpcodes(MatchTable &Table,
1259 RuleMatcher &Rule) const {
1260 assert(Idx < 0 && "Temp types always have negative indexes!");
1261 Table << MatchTable::Opcode(Opcode: "GIM_RecordRegType") << MatchTable::Comment(Comment: "MI")
1262 << MatchTable::ULEB128Value(IntValue: InsnVarID) << MatchTable::Comment(Comment: "Op")
1263 << MatchTable::ULEB128Value(IntValue: OpIdx) << MatchTable::Comment(Comment: "TempTypeIdx")
1264 << MatchTable::IntValue(NumBytes: 1, IntValue: Idx) << MatchTable::LineBreak;
1265}
1266
1267//===- ComplexPatternOperandMatcher ---------------------------------------===//
1268
1269void ComplexPatternOperandMatcher::emitPredicateOpcodes(
1270 MatchTable &Table, RuleMatcher &Rule) const {
1271 unsigned ID = getAllocatedTemporariesBaseID();
1272 Table << MatchTable::Opcode(Opcode: "GIM_CheckComplexPattern")
1273 << MatchTable::Comment(Comment: "MI") << MatchTable::ULEB128Value(IntValue: InsnVarID)
1274 << MatchTable::Comment(Comment: "Op") << MatchTable::ULEB128Value(IntValue: OpIdx)
1275 << MatchTable::Comment(Comment: "Renderer") << MatchTable::IntValue(NumBytes: 2, IntValue: ID)
1276 << MatchTable::NamedValue(NumBytes: 2, NamedValue: ("GICP_" + TheDef.getName()).str())
1277 << MatchTable::LineBreak;
1278}
1279
1280unsigned ComplexPatternOperandMatcher::getAllocatedTemporariesBaseID() const {
1281 return Operand.getAllocatedTemporariesBaseID();
1282}
1283
1284//===- RegisterBankOperandMatcher -----------------------------------------===//
1285
1286bool RegisterBankOperandMatcher::isIdentical(const PredicateMatcher &B) const {
1287 return OperandPredicateMatcher::isIdentical(B) &&
1288 RC.getDef() == cast<RegisterBankOperandMatcher>(Val: &B)->RC.getDef();
1289}
1290
1291void RegisterBankOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
1292 RuleMatcher &Rule) const {
1293 if (InsnVarID == 0) {
1294 Table << MatchTable::Opcode(Opcode: "GIM_RootCheckRegBankForClass");
1295 } else {
1296 Table << MatchTable::Opcode(Opcode: "GIM_CheckRegBankForClass")
1297 << MatchTable::Comment(Comment: "MI") << MatchTable::ULEB128Value(IntValue: InsnVarID);
1298 }
1299
1300 Table << MatchTable::Comment(Comment: "Op") << MatchTable::ULEB128Value(IntValue: OpIdx)
1301 << MatchTable::Comment(Comment: "RC")
1302 << MatchTable::NamedValue(NumBytes: 2, NamedValue: RC.getQualifiedIdName())
1303 << MatchTable::LineBreak;
1304}
1305
1306//===- MBBOperandMatcher --------------------------------------------------===//
1307
1308void MBBOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
1309 RuleMatcher &Rule) const {
1310 Table << MatchTable::Opcode(Opcode: "GIM_CheckIsMBB") << MatchTable::Comment(Comment: "MI")
1311 << MatchTable::ULEB128Value(IntValue: InsnVarID) << MatchTable::Comment(Comment: "Op")
1312 << MatchTable::ULEB128Value(IntValue: OpIdx) << MatchTable::LineBreak;
1313}
1314
1315//===- ImmOperandMatcher --------------------------------------------------===//
1316
1317void ImmOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
1318 RuleMatcher &Rule) const {
1319 Table << MatchTable::Opcode(Opcode: "GIM_CheckIsImm") << MatchTable::Comment(Comment: "MI")
1320 << MatchTable::ULEB128Value(IntValue: InsnVarID) << MatchTable::Comment(Comment: "Op")
1321 << MatchTable::ULEB128Value(IntValue: OpIdx) << MatchTable::LineBreak;
1322}
1323
1324//===- ConstantIntOperandMatcher ------------------------------------------===//
1325
1326void ConstantIntOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
1327 RuleMatcher &Rule) const {
1328 const bool IsInt8 = isInt<8>(x: Value);
1329 Table << MatchTable::Opcode(Opcode: IsInt8 ? "GIM_CheckConstantInt8"
1330 : "GIM_CheckConstantInt")
1331 << MatchTable::Comment(Comment: "MI") << MatchTable::ULEB128Value(IntValue: InsnVarID)
1332 << MatchTable::Comment(Comment: "Op") << MatchTable::ULEB128Value(IntValue: OpIdx)
1333 << MatchTable::IntValue(NumBytes: IsInt8 ? 1 : 8, IntValue: Value) << MatchTable::LineBreak;
1334}
1335
1336//===- LiteralIntOperandMatcher -------------------------------------------===//
1337
1338void LiteralIntOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
1339 RuleMatcher &Rule) const {
1340 Table << MatchTable::Opcode(Opcode: "GIM_CheckLiteralInt")
1341 << MatchTable::Comment(Comment: "MI") << MatchTable::ULEB128Value(IntValue: InsnVarID)
1342 << MatchTable::Comment(Comment: "Op") << MatchTable::ULEB128Value(IntValue: OpIdx)
1343 << MatchTable::IntValue(NumBytes: 8, IntValue: Value) << MatchTable::LineBreak;
1344}
1345
1346//===- CmpPredicateOperandMatcher -----------------------------------------===//
1347
1348void CmpPredicateOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
1349 RuleMatcher &Rule) const {
1350 Table << MatchTable::Opcode(Opcode: "GIM_CheckCmpPredicate")
1351 << MatchTable::Comment(Comment: "MI") << MatchTable::ULEB128Value(IntValue: InsnVarID)
1352 << MatchTable::Comment(Comment: "Op") << MatchTable::ULEB128Value(IntValue: OpIdx)
1353 << MatchTable::Comment(Comment: "Predicate")
1354 << MatchTable::NamedValue(NumBytes: 2, Namespace: "CmpInst", NamedValue: PredName)
1355 << MatchTable::LineBreak;
1356}
1357
1358//===- IntrinsicIDOperandMatcher ------------------------------------------===//
1359
1360void IntrinsicIDOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
1361 RuleMatcher &Rule) const {
1362 Table << MatchTable::Opcode(Opcode: "GIM_CheckIntrinsicID")
1363 << MatchTable::Comment(Comment: "MI") << MatchTable::ULEB128Value(IntValue: InsnVarID)
1364 << MatchTable::Comment(Comment: "Op") << MatchTable::ULEB128Value(IntValue: OpIdx)
1365 << MatchTable::NamedValue(NumBytes: 2, NamedValue: "Intrinsic::" + II->EnumName.str())
1366 << MatchTable::LineBreak;
1367}
1368
1369//===- OperandImmPredicateMatcher -----------------------------------------===//
1370
1371void OperandImmPredicateMatcher::emitPredicateOpcodes(MatchTable &Table,
1372 RuleMatcher &Rule) const {
1373 Table << MatchTable::Opcode(Opcode: "GIM_CheckImmOperandPredicate")
1374 << MatchTable::Comment(Comment: "MI") << MatchTable::ULEB128Value(IntValue: InsnVarID)
1375 << MatchTable::Comment(Comment: "MO") << MatchTable::ULEB128Value(IntValue: OpIdx)
1376 << MatchTable::Comment(Comment: "Predicate")
1377 << MatchTable::NamedValue(NumBytes: 2, NamedValue: getEnumNameForPredicate(Predicate))
1378 << MatchTable::LineBreak;
1379}
1380
1381//===- OperandLeafPredicateMatcher
1382//-----------------------------------------===//
1383
1384void OperandLeafPredicateMatcher::emitPredicateOpcodes(
1385 MatchTable &Table, RuleMatcher &Rule) const {
1386 Table << MatchTable::Opcode(Opcode: "GIM_CheckLeafOperandPredicate")
1387 << MatchTable::Comment(Comment: "MI") << MatchTable::ULEB128Value(IntValue: InsnVarID)
1388 << MatchTable::Comment(Comment: "MO") << MatchTable::ULEB128Value(IntValue: OpIdx)
1389 << MatchTable::Comment(Comment: "Predicate")
1390 << MatchTable::NamedValue(NumBytes: 2, NamedValue: getEnumNameForPredicate(Predicate))
1391 << MatchTable::LineBreak;
1392}
1393
1394//===- OperandMatcher -----------------------------------------------------===//
1395
1396std::string OperandMatcher::getOperandExpr(unsigned InsnVarID) const {
1397 return "State.MIs[" + llvm::to_string(Value: InsnVarID) + "]->getOperand(" +
1398 llvm::to_string(Value: OpIdx) + ")";
1399}
1400
1401unsigned OperandMatcher::getInsnVarID() const { return Insn.getInsnVarID(); }
1402
1403TempTypeIdx OperandMatcher::getTempTypeIdx(RuleMatcher &Rule) {
1404 assert(!IsVariadic && "Cannot use this on variadic operands!");
1405 if (TTIdx >= 0) {
1406 // Temp type index not assigned yet, so assign one and add the necessary
1407 // predicate.
1408 TTIdx = Rule.getNextTempTypeIdx();
1409 assert(TTIdx < 0);
1410 addPredicate<RecordRegisterType>(args&: TTIdx);
1411 return TTIdx;
1412 }
1413 return TTIdx;
1414}
1415
1416bool OperandMatcher::recordsOperand() const {
1417 return matchersRecordOperand(R: Predicates);
1418}
1419
1420void OperandMatcher::emitPredicateOpcodes(MatchTable &Table,
1421 RuleMatcher &Rule) {
1422 if (!Optimized) {
1423 std::string Comment;
1424 raw_string_ostream CommentOS(Comment);
1425 CommentOS << "MIs[" << getInsnVarID() << "] ";
1426 if (SymbolicName.empty())
1427 CommentOS << "Operand " << OpIdx;
1428 else
1429 CommentOS << SymbolicName;
1430 Table << MatchTable::Comment(Comment) << MatchTable::LineBreak;
1431 }
1432
1433 emitPredicateListOpcodes(Table, args&: Rule);
1434}
1435
1436bool OperandMatcher::isHigherPriorityThan(OperandMatcher &B) {
1437 // Operand matchers involving more predicates have higher priority.
1438 if (predicates_size() > B.predicates_size())
1439 return true;
1440 if (predicates_size() < B.predicates_size())
1441 return false;
1442
1443 // This assumes that predicates are added in a consistent order.
1444 for (auto &&Predicate : zip(t: predicates(), u: B.predicates())) {
1445 if (std::get<0>(t&: Predicate)->isHigherPriorityThan(B: *std::get<1>(t&: Predicate)))
1446 return true;
1447 if (std::get<1>(t&: Predicate)->isHigherPriorityThan(B: *std::get<0>(t&: Predicate)))
1448 return false;
1449 }
1450
1451 return false;
1452}
1453
1454unsigned OperandMatcher::countRendererFns() {
1455 return std::accumulate(
1456 first: predicates().begin(), last: predicates().end(), init: 0,
1457 binary_op: [](unsigned A,
1458 const std::unique_ptr<OperandPredicateMatcher> &Predicate) {
1459 return A + Predicate->countRendererFns();
1460 });
1461}
1462
1463Error OperandMatcher::addTypeCheckPredicate(const TypeSetByHwMode &VTy,
1464 bool OperandIsAPointer) {
1465 if (!VTy.isMachineValueType())
1466 return failUnsupported(Reason: "unsupported typeset");
1467
1468 if ((VTy.getMachineValueType() == MVT::iPTR ||
1469 VTy.getMachineValueType() == MVT::cPTR) &&
1470 OperandIsAPointer) {
1471 addPredicate<PointerToAnyOperandMatcher>(args: 0);
1472 return Error::success();
1473 }
1474
1475 auto OpTyOrNone = MVTToLLT(VT: VTy.getMachineValueType().SimpleTy);
1476 if (!OpTyOrNone)
1477 return failUnsupported(Reason: "unsupported type");
1478
1479 if (OperandIsAPointer)
1480 addPredicate<PointerToAnyOperandMatcher>(args: OpTyOrNone->get().getSizeInBits());
1481 else if (VTy.isPointer())
1482 addPredicate<LLTOperandMatcher>(
1483 args: LLT::pointer(AddressSpace: VTy.getPtrAddrSpace(), SizeInBits: OpTyOrNone->get().getSizeInBits()));
1484 else
1485 addPredicate<LLTOperandMatcher>(args&: *OpTyOrNone);
1486 return Error::success();
1487}
1488
1489//===- InstructionOpcodeMatcher -------------------------------------------===//
1490
1491DenseMap<const CodeGenInstruction *, unsigned>
1492 InstructionOpcodeMatcher::OpcodeValues;
1493
1494RecordAndValue
1495InstructionOpcodeMatcher::getInstValue(const CodeGenInstruction *I) const {
1496 const auto VI = OpcodeValues.find(Val: I);
1497 if (VI != OpcodeValues.end())
1498 return {MatchTable::NamedValue(NumBytes: 2, Namespace: I->Namespace, NamedValue: I->getName()), VI->second};
1499 return MatchTable::NamedValue(NumBytes: 2, Namespace: I->Namespace, NamedValue: I->getName());
1500}
1501
1502void InstructionOpcodeMatcher::initOpcodeValuesMap(
1503 const CodeGenTarget &Target) {
1504 OpcodeValues.clear();
1505
1506 for (const CodeGenInstruction *I : Target.getInstructions())
1507 OpcodeValues[I] = Target.getInstrIntValue(R: I->TheDef);
1508}
1509
1510RecordAndValue InstructionOpcodeMatcher::getValue() const {
1511 assert(Insts.size() == 1);
1512
1513 const CodeGenInstruction *I = Insts[0];
1514 const auto VI = OpcodeValues.find(Val: I);
1515 if (VI != OpcodeValues.end())
1516 return {MatchTable::NamedValue(NumBytes: 2, Namespace: I->Namespace, NamedValue: I->getName()), VI->second};
1517 return MatchTable::NamedValue(NumBytes: 2, Namespace: I->Namespace, NamedValue: I->getName());
1518}
1519
1520void InstructionOpcodeMatcher::emitPredicateOpcodes(MatchTable &Table,
1521 RuleMatcher &Rule) const {
1522 StringRef CheckType =
1523 Insts.size() == 1 ? "GIM_CheckOpcode" : "GIM_CheckOpcodeIsEither";
1524 Table << MatchTable::Opcode(Opcode: CheckType) << MatchTable::Comment(Comment: "MI")
1525 << MatchTable::ULEB128Value(IntValue: InsnVarID);
1526
1527 for (const CodeGenInstruction *I : Insts)
1528 Table << getInstValue(I).Record;
1529 Table << MatchTable::LineBreak;
1530}
1531
1532bool InstructionOpcodeMatcher::isHigherPriorityThan(
1533 const InstructionPredicateMatcher &B) const {
1534 if (InstructionPredicateMatcher::isHigherPriorityThan(B))
1535 return true;
1536 if (B.InstructionPredicateMatcher::isHigherPriorityThan(B: *this))
1537 return false;
1538
1539 // Prioritize opcodes for cosmetic reasons in the generated source. Although
1540 // this is cosmetic at the moment, we may want to drive a similar ordering
1541 // using instruction frequency information to improve compile time.
1542 if (const InstructionOpcodeMatcher *BO =
1543 dyn_cast<InstructionOpcodeMatcher>(Val: &B))
1544 return Insts[0]->getName() < BO->Insts[0]->getName();
1545
1546 return false;
1547}
1548
1549bool InstructionOpcodeMatcher::isConstantInstruction() const {
1550 return Insts.size() == 1 && Insts[0]->getName() == "G_CONSTANT";
1551}
1552
1553StringRef InstructionOpcodeMatcher::getOpcode() const {
1554 return Insts[0]->getName();
1555}
1556
1557bool InstructionOpcodeMatcher::isVariadicNumOperands() const {
1558 // If one is variadic, they all should be.
1559 return Insts[0]->Operands.isVariadic;
1560}
1561
1562StringRef InstructionOpcodeMatcher::getOperandType(unsigned OpIdx) const {
1563 // Types expected to be uniform for all alternatives.
1564 return Insts[0]->Operands[OpIdx].OperandType;
1565}
1566
1567//===- InstructionNumOperandsMatcher --------------------------------------===//
1568
1569void InstructionNumOperandsMatcher::emitPredicateOpcodes(
1570 MatchTable &Table, RuleMatcher &Rule) const {
1571 StringRef Opc;
1572 switch (CK) {
1573 case CheckKind::Eq:
1574 Opc = "GIM_CheckNumOperands";
1575 break;
1576 case CheckKind::GE:
1577 Opc = "GIM_CheckNumOperandsGE";
1578 break;
1579 case CheckKind::LE:
1580 Opc = "GIM_CheckNumOperandsLE";
1581 break;
1582 }
1583 Table << MatchTable::Opcode(Opcode: Opc) << MatchTable::Comment(Comment: "MI")
1584 << MatchTable::ULEB128Value(IntValue: InsnVarID)
1585 << MatchTable::Comment(Comment: "Expected")
1586 << MatchTable::ULEB128Value(IntValue: NumOperands) << MatchTable::LineBreak;
1587}
1588
1589//===- InstructionImmPredicateMatcher -------------------------------------===//
1590
1591bool InstructionImmPredicateMatcher::isIdentical(
1592 const PredicateMatcher &B) const {
1593 return InstructionPredicateMatcher::isIdentical(B) &&
1594 Predicate.getOrigPatFragRecord() ==
1595 cast<InstructionImmPredicateMatcher>(Val: &B)
1596 ->Predicate.getOrigPatFragRecord();
1597}
1598
1599void InstructionImmPredicateMatcher::emitPredicateOpcodes(
1600 MatchTable &Table, RuleMatcher &Rule) const {
1601 Table << MatchTable::Opcode(Opcode: getMatchOpcodeForImmPredicate(Predicate))
1602 << MatchTable::Comment(Comment: "MI") << MatchTable::ULEB128Value(IntValue: InsnVarID)
1603 << MatchTable::Comment(Comment: "Predicate")
1604 << MatchTable::NamedValue(NumBytes: 2, NamedValue: getEnumNameForPredicate(Predicate))
1605 << MatchTable::LineBreak;
1606}
1607
1608//===- AtomicOrderingMMOPredicateMatcher ----------------------------------===//
1609
1610bool AtomicOrderingMMOPredicateMatcher::isIdentical(
1611 const PredicateMatcher &B) const {
1612 if (!InstructionPredicateMatcher::isIdentical(B))
1613 return false;
1614 const auto &R = *cast<AtomicOrderingMMOPredicateMatcher>(Val: &B);
1615 return Order == R.Order && Comparator == R.Comparator;
1616}
1617
1618void AtomicOrderingMMOPredicateMatcher::emitPredicateOpcodes(
1619 MatchTable &Table, RuleMatcher &Rule) const {
1620 StringRef Opcode = "GIM_CheckAtomicOrdering";
1621
1622 if (Comparator == AO_OrStronger)
1623 Opcode = "GIM_CheckAtomicOrderingOrStrongerThan";
1624 if (Comparator == AO_WeakerThan)
1625 Opcode = "GIM_CheckAtomicOrderingWeakerThan";
1626
1627 Table << MatchTable::Opcode(Opcode) << MatchTable::Comment(Comment: "MI")
1628 << MatchTable::ULEB128Value(IntValue: InsnVarID) << MatchTable::Comment(Comment: "Order")
1629 << MatchTable::NamedValue(NumBytes: 1,
1630 NamedValue: ("(uint8_t)AtomicOrdering::" + Order).str())
1631 << MatchTable::LineBreak;
1632}
1633
1634//===- MemorySizePredicateMatcher -----------------------------------------===//
1635
1636void MemorySizePredicateMatcher::emitPredicateOpcodes(MatchTable &Table,
1637 RuleMatcher &Rule) const {
1638 Table << MatchTable::Opcode(Opcode: "GIM_CheckMemorySizeEqualTo")
1639 << MatchTable::Comment(Comment: "MI") << MatchTable::ULEB128Value(IntValue: InsnVarID)
1640 << MatchTable::Comment(Comment: "MMO") << MatchTable::ULEB128Value(IntValue: MMOIdx)
1641 << MatchTable::Comment(Comment: "Size") << MatchTable::IntValue(NumBytes: 4, IntValue: Size)
1642 << MatchTable::LineBreak;
1643}
1644
1645//===- MemoryAddressSpacePredicateMatcher ---------------------------------===//
1646
1647bool MemoryAddressSpacePredicateMatcher::isIdentical(
1648 const PredicateMatcher &B) const {
1649 if (!InstructionPredicateMatcher::isIdentical(B))
1650 return false;
1651 auto *Other = cast<MemoryAddressSpacePredicateMatcher>(Val: &B);
1652 return MMOIdx == Other->MMOIdx && AddrSpaces == Other->AddrSpaces;
1653}
1654
1655void MemoryAddressSpacePredicateMatcher::emitPredicateOpcodes(
1656 MatchTable &Table, RuleMatcher &Rule) const {
1657 assert(AddrSpaces.size() < 256);
1658 Table << MatchTable::Opcode(Opcode: "GIM_CheckMemoryAddressSpace")
1659 << MatchTable::Comment(Comment: "MI") << MatchTable::ULEB128Value(IntValue: InsnVarID)
1660 << MatchTable::Comment(Comment: "MMO")
1661 << MatchTable::ULEB128Value(IntValue: MMOIdx)
1662 // Encode number of address spaces to expect.
1663 << MatchTable::Comment(Comment: "NumAddrSpace")
1664 << MatchTable::IntValue(NumBytes: 1, IntValue: AddrSpaces.size());
1665 for (unsigned AS : AddrSpaces)
1666 Table << MatchTable::Comment(Comment: "AddrSpace") << MatchTable::ULEB128Value(IntValue: AS);
1667
1668 Table << MatchTable::LineBreak;
1669}
1670
1671//===- MemoryAlignmentPredicateMatcher ------------------------------------===//
1672
1673bool MemoryAlignmentPredicateMatcher::isIdentical(
1674 const PredicateMatcher &B) const {
1675 if (!InstructionPredicateMatcher::isIdentical(B))
1676 return false;
1677 auto *Other = cast<MemoryAlignmentPredicateMatcher>(Val: &B);
1678 return MMOIdx == Other->MMOIdx && MinAlign == Other->MinAlign;
1679}
1680
1681void MemoryAlignmentPredicateMatcher::emitPredicateOpcodes(
1682 MatchTable &Table, RuleMatcher &Rule) const {
1683 // TODO: we could support more, just need to emit the right opcode or switch
1684 // to log alignment.
1685 assert(MinAlign < 256);
1686 Table << MatchTable::Opcode(Opcode: "GIM_CheckMemoryAlignment")
1687 << MatchTable::Comment(Comment: "MI") << MatchTable::ULEB128Value(IntValue: InsnVarID)
1688 << MatchTable::Comment(Comment: "MMO") << MatchTable::ULEB128Value(IntValue: MMOIdx)
1689 << MatchTable::Comment(Comment: "MinAlign") << MatchTable::IntValue(NumBytes: 1, IntValue: MinAlign)
1690 << MatchTable::LineBreak;
1691}
1692
1693//===- MemoryVsLLTSizePredicateMatcher ------------------------------------===//
1694
1695bool MemoryVsLLTSizePredicateMatcher::isIdentical(
1696 const PredicateMatcher &B) const {
1697 return InstructionPredicateMatcher::isIdentical(B) &&
1698 MMOIdx == cast<MemoryVsLLTSizePredicateMatcher>(Val: &B)->MMOIdx &&
1699 Relation == cast<MemoryVsLLTSizePredicateMatcher>(Val: &B)->Relation &&
1700 OpIdx == cast<MemoryVsLLTSizePredicateMatcher>(Val: &B)->OpIdx;
1701}
1702
1703void MemoryVsLLTSizePredicateMatcher::emitPredicateOpcodes(
1704 MatchTable &Table, RuleMatcher &Rule) const {
1705 Table << MatchTable::Opcode(
1706 Opcode: Relation == EqualTo ? "GIM_CheckMemorySizeEqualToLLT"
1707 : Relation == GreaterThan ? "GIM_CheckMemorySizeGreaterThanLLT"
1708 : "GIM_CheckMemorySizeLessThanLLT")
1709 << MatchTable::Comment(Comment: "MI") << MatchTable::ULEB128Value(IntValue: InsnVarID)
1710 << MatchTable::Comment(Comment: "MMO") << MatchTable::ULEB128Value(IntValue: MMOIdx)
1711 << MatchTable::Comment(Comment: "OpIdx") << MatchTable::ULEB128Value(IntValue: OpIdx)
1712 << MatchTable::LineBreak;
1713}
1714
1715//===- VectorSplatImmPredicateMatcher -------------------------------------===//
1716
1717void VectorSplatImmPredicateMatcher::emitPredicateOpcodes(
1718 MatchTable &Table, RuleMatcher &Rule) const {
1719 if (Kind == AllOnes)
1720 Table << MatchTable::Opcode(Opcode: "GIM_CheckIsBuildVectorAllOnes");
1721 else
1722 Table << MatchTable::Opcode(Opcode: "GIM_CheckIsBuildVectorAllZeros");
1723
1724 Table << MatchTable::Comment(Comment: "MI") << MatchTable::ULEB128Value(IntValue: InsnVarID);
1725 Table << MatchTable::LineBreak;
1726}
1727
1728//===- GenericInstructionPredicateMatcher ---------------------------------===//
1729
1730GenericInstructionPredicateMatcher::GenericInstructionPredicateMatcher(
1731 unsigned InsnVarID, TreePredicateFn Predicate)
1732 : GenericInstructionPredicateMatcher(InsnVarID,
1733 getEnumNameForPredicate(Predicate)) {}
1734
1735bool GenericInstructionPredicateMatcher::isIdentical(
1736 const PredicateMatcher &B) const {
1737 return InstructionPredicateMatcher::isIdentical(B) &&
1738 EnumVal ==
1739 static_cast<const GenericInstructionPredicateMatcher &>(B).EnumVal;
1740}
1741void GenericInstructionPredicateMatcher::emitPredicateOpcodes(
1742 MatchTable &Table, RuleMatcher &Rule) const {
1743 Table << MatchTable::Opcode(Opcode: "GIM_CheckCxxInsnPredicate")
1744 << MatchTable::Comment(Comment: "MI") << MatchTable::ULEB128Value(IntValue: InsnVarID)
1745 << MatchTable::Comment(Comment: "FnId") << MatchTable::NamedValue(NumBytes: 2, NamedValue: EnumVal)
1746 << MatchTable::LineBreak;
1747}
1748
1749//===- MIFlagsInstructionPredicateMatcher ---------------------------------===//
1750
1751bool MIFlagsInstructionPredicateMatcher::isIdentical(
1752 const PredicateMatcher &B) const {
1753 if (!InstructionPredicateMatcher::isIdentical(B))
1754 return false;
1755 const auto &Other =
1756 static_cast<const MIFlagsInstructionPredicateMatcher &>(B);
1757 return Flags == Other.Flags && CheckNot == Other.CheckNot;
1758}
1759
1760void MIFlagsInstructionPredicateMatcher::emitPredicateOpcodes(
1761 MatchTable &Table, RuleMatcher &Rule) const {
1762 Table << MatchTable::Opcode(Opcode: CheckNot ? "GIM_MIFlagsNot" : "GIM_MIFlags")
1763 << MatchTable::Comment(Comment: "MI") << MatchTable::ULEB128Value(IntValue: InsnVarID)
1764 << MatchTable::NamedValue(NumBytes: 4, NamedValue: join(R: Flags, Separator: " | "))
1765 << MatchTable::LineBreak;
1766}
1767
1768//===- InstructionMatcher -------------------------------------------------===//
1769
1770OperandMatcher &
1771InstructionMatcher::addOperand(unsigned OpIdx, const std::string &SymbolicName,
1772 unsigned AllocatedTemporariesBaseID,
1773 bool IsVariadic) {
1774 assert((Operands.empty() || !Operands.back()->isVariadic()) &&
1775 "Cannot add more operands after a variadic operand");
1776 Operands.emplace_back(args: new OperandMatcher(
1777 *this, OpIdx, SymbolicName, AllocatedTemporariesBaseID, IsVariadic));
1778 if (!SymbolicName.empty())
1779 Rule.defineOperand(SymbolicName, OM&: *Operands.back());
1780 return *Operands.back();
1781}
1782
1783OperandMatcher &InstructionMatcher::getOperand(unsigned OpIdx) {
1784 auto I = llvm::find_if(Range&: Operands,
1785 P: [&OpIdx](const std::unique_ptr<OperandMatcher> &X) {
1786 return X->getOpIdx() == OpIdx;
1787 });
1788 if (I != Operands.end())
1789 return **I;
1790 llvm_unreachable("Failed to lookup operand");
1791}
1792
1793OperandMatcher &InstructionMatcher::addPhysRegInput(const Record *Reg,
1794 unsigned OpIdx,
1795 unsigned TempOpIdx) {
1796 assert(SymbolicName.empty());
1797 OperandMatcher *OM = new OperandMatcher(*this, OpIdx, "", TempOpIdx);
1798 Operands.emplace_back(args&: OM);
1799 Rule.definePhysRegOperand(Reg, OM&: *OM);
1800 return *OM;
1801}
1802
1803bool InstructionMatcher::recordsOperand() const {
1804 return matchersRecordOperand(R: Predicates) || matchersRecordOperand(R: operands());
1805}
1806
1807void InstructionMatcher::emitPredicateOpcodes(MatchTable &Table,
1808 RuleMatcher &Rule) {
1809 if (canAddNumOperandsCheck()) {
1810 InstructionNumOperandsMatcher(InsnVarID, getNumOperandMatchers())
1811 .emitPredicateOpcodes(Table, Rule);
1812 }
1813
1814 // First emit all instruction level predicates need to be verified before we
1815 // can verify operands.
1816 emitFilteredPredicateListOpcodes(
1817 ShouldEmitPredicate: [](const PredicateMatcher &P) { return !P.dependsOnOperands(); }, Table,
1818 args&: Rule);
1819
1820 // Emit all operand constraints.
1821 for (const auto &Operand : Operands)
1822 Operand->emitPredicateOpcodes(Table, Rule);
1823
1824 // All of the tablegen defined predicates should now be matched. Now emit
1825 // any custom predicates that rely on all generated checks.
1826 emitFilteredPredicateListOpcodes(
1827 ShouldEmitPredicate: [](const PredicateMatcher &P) { return P.dependsOnOperands(); }, Table,
1828 args&: Rule);
1829}
1830
1831bool InstructionMatcher::isHigherPriorityThan(InstructionMatcher &B) {
1832 // Instruction matchers involving more operands have higher priority.
1833 if (Operands.size() > B.Operands.size())
1834 return true;
1835 if (Operands.size() < B.Operands.size())
1836 return false;
1837
1838 for (auto &&P : zip(t: predicates(), u: B.predicates())) {
1839 auto L = static_cast<InstructionPredicateMatcher *>(std::get<0>(t&: P).get());
1840 auto R = static_cast<InstructionPredicateMatcher *>(std::get<1>(t&: P).get());
1841 if (L->isHigherPriorityThan(B: *R))
1842 return true;
1843 if (R->isHigherPriorityThan(B: *L))
1844 return false;
1845 }
1846
1847 for (auto Operand : zip(t&: Operands, u&: B.Operands)) {
1848 if (std::get<0>(t&: Operand)->isHigherPriorityThan(B&: *std::get<1>(t&: Operand)))
1849 return true;
1850 if (std::get<1>(t&: Operand)->isHigherPriorityThan(B&: *std::get<0>(t&: Operand)))
1851 return false;
1852 }
1853
1854 return false;
1855}
1856
1857unsigned InstructionMatcher::countRendererFns() {
1858 return std::accumulate(
1859 first: predicates().begin(), last: predicates().end(), init: 0,
1860 binary_op: [](unsigned A,
1861 const std::unique_ptr<PredicateMatcher> &Predicate) {
1862 return A + Predicate->countRendererFns();
1863 }) +
1864 std::accumulate(
1865 first: Operands.begin(), last: Operands.end(), init: 0,
1866 binary_op: [](unsigned A, const std::unique_ptr<OperandMatcher> &Operand) {
1867 return A + Operand->countRendererFns();
1868 });
1869}
1870
1871void InstructionMatcher::optimize() {
1872 SmallVector<std::unique_ptr<PredicateMatcher>, 8> Stash;
1873 const auto &OpcMatcher = getOpcodeMatcher();
1874
1875 Stash.push_back(Elt: predicates_pop_front());
1876 if (Stash.back().get() == &OpcMatcher) {
1877 // FIXME: Is this even needed still? Why the isVariadicNumOperands check?
1878 if (canAddNumOperandsCheck() && OpcMatcher.isVariadicNumOperands() &&
1879 getNumOperandMatchers() != 0) {
1880 Stash.emplace_back(Args: new InstructionNumOperandsMatcher(
1881 InsnVarID, getNumOperandMatchers()));
1882 }
1883 AllowNumOpsCheck = false;
1884
1885 for (auto &OM : Operands)
1886 for (auto &OP : OM->predicates())
1887 if (isa<IntrinsicIDOperandMatcher>(Val: OP)) {
1888 Stash.push_back(Elt: std::move(OP));
1889 OM->eraseNullPredicates();
1890 break;
1891 }
1892 }
1893
1894 if (InsnVarID > 0) {
1895 assert(!Operands.empty() && "Nested instruction is expected to def a vreg");
1896 for (auto &OP : Operands[0]->predicates())
1897 OP.reset();
1898 Operands[0]->eraseNullPredicates();
1899 }
1900 for (auto &OM : Operands) {
1901 for (auto &OP : OM->predicates())
1902 if (isa<LLTOperandMatcher>(Val: OP))
1903 Stash.push_back(Elt: std::move(OP));
1904 OM->eraseNullPredicates();
1905 }
1906 while (!Stash.empty())
1907 prependPredicate(Predicate: Stash.pop_back_val());
1908}
1909
1910//===- InstructionOperandMatcher ------------------------------------------===//
1911
1912void InstructionOperandMatcher::emitCaptureOpcodes(MatchTable &Table,
1913 RuleMatcher &Rule) const {
1914 const unsigned NewInsnVarID = InsnMatcher->getInsnVarID();
1915 const bool IgnoreCopies = Flags & GISF_IgnoreCopies;
1916 Table << MatchTable::Opcode(Opcode: IgnoreCopies ? "GIM_RecordInsnIgnoreCopies"
1917 : "GIM_RecordInsn")
1918 << MatchTable::Comment(Comment: "DefineMI")
1919 << MatchTable::ULEB128Value(IntValue: NewInsnVarID) << MatchTable::Comment(Comment: "MI")
1920 << MatchTable::ULEB128Value(IntValue: getInsnVarID())
1921 << MatchTable::Comment(Comment: "OpIdx") << MatchTable::ULEB128Value(IntValue: getOpIdx())
1922 << MatchTable::Comment(Comment: "MIs[" + llvm::to_string(Value: NewInsnVarID) + "]")
1923 << MatchTable::LineBreak;
1924}
1925
1926bool InstructionOperandMatcher::isHigherPriorityThan(
1927 const OperandPredicateMatcher &B) const {
1928 if (OperandPredicateMatcher::isHigherPriorityThan(B))
1929 return true;
1930 if (B.OperandPredicateMatcher::isHigherPriorityThan(B: *this))
1931 return false;
1932
1933 if (const InstructionOperandMatcher *BP =
1934 dyn_cast<InstructionOperandMatcher>(Val: &B))
1935 if (InsnMatcher->isHigherPriorityThan(B&: *BP->InsnMatcher))
1936 return true;
1937 return false;
1938}
1939
1940//===- OperandRenderer ----------------------------------------------------===//
1941
1942OperandRenderer::~OperandRenderer() = default;
1943
1944//===- CopyRenderer -------------------------------------------------------===//
1945
1946void CopyRenderer::emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule,
1947 unsigned NewInsnID, unsigned OldInsnID,
1948 unsigned OpIdx, StringRef Name,
1949 bool ForVariadic) {
1950 if (!ForVariadic && NewInsnID == 0 && OldInsnID == 0) {
1951 Table << MatchTable::Opcode(Opcode: "GIR_RootToRootCopy");
1952 } else {
1953 Table << MatchTable::Opcode(Opcode: ForVariadic ? "GIR_CopyRemaining" : "GIR_Copy")
1954 << MatchTable::Comment(Comment: "NewInsnID")
1955 << MatchTable::ULEB128Value(IntValue: NewInsnID)
1956 << MatchTable::Comment(Comment: "OldInsnID")
1957 << MatchTable::ULEB128Value(IntValue: OldInsnID);
1958 }
1959
1960 Table << MatchTable::Comment(Comment: "OpIdx") << MatchTable::ULEB128Value(IntValue: OpIdx)
1961 << MatchTable::Comment(Comment: Name) << MatchTable::LineBreak;
1962}
1963
1964void CopyRenderer::emitRenderOpcodes(MatchTable &Table,
1965 RuleMatcher &Rule) const {
1966 const OperandMatcher &Operand = Rule.getOperandMatcher(Name: SymbolicName);
1967 unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher&: Operand.getInstructionMatcher());
1968
1969 emitRenderOpcodes(Table, Rule, NewInsnID, OldInsnID: OldInsnVarID, OpIdx: Operand.getOpIdx(),
1970 Name: SymbolicName, ForVariadic: Operand.isVariadic());
1971}
1972
1973//===- CopyPhysRegRenderer ------------------------------------------------===//
1974
1975void CopyPhysRegRenderer::emitRenderOpcodes(MatchTable &Table,
1976 RuleMatcher &Rule) const {
1977 const OperandMatcher &Operand = Rule.getPhysRegOperandMatcher(Reg: PhysReg);
1978 unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher&: Operand.getInstructionMatcher());
1979 CopyRenderer::emitRenderOpcodes(Table, Rule, NewInsnID, OldInsnID: OldInsnVarID,
1980 OpIdx: Operand.getOpIdx(), Name: PhysReg->getName());
1981}
1982
1983//===- CopyOrAddZeroRegRenderer -------------------------------------------===//
1984
1985void CopyOrAddZeroRegRenderer::emitRenderOpcodes(MatchTable &Table,
1986 RuleMatcher &Rule) const {
1987 const OperandMatcher &Operand = Rule.getOperandMatcher(Name: SymbolicName);
1988 unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher&: Operand.getInstructionMatcher());
1989 Table << MatchTable::Opcode(Opcode: "GIR_CopyOrAddZeroReg")
1990 << MatchTable::Comment(Comment: "NewInsnID")
1991 << MatchTable::ULEB128Value(IntValue: NewInsnID)
1992 << MatchTable::Comment(Comment: "OldInsnID")
1993 << MatchTable::ULEB128Value(IntValue: OldInsnVarID)
1994 << MatchTable::Comment(Comment: "OpIdx")
1995 << MatchTable::ULEB128Value(IntValue: Operand.getOpIdx())
1996 << MatchTable::NamedValue(
1997 NumBytes: 2,
1998 Namespace: (ZeroRegisterDef->getValue(Name: "Namespace")
1999 ? ZeroRegisterDef->getValueAsString(FieldName: "Namespace")
2000 : ""),
2001 NamedValue: ZeroRegisterDef->getName())
2002 << MatchTable::Comment(Comment: SymbolicName) << MatchTable::LineBreak;
2003}
2004
2005//===- CopyConstantAsImmRenderer ------------------------------------------===//
2006
2007void CopyConstantAsImmRenderer::emitRenderOpcodes(MatchTable &Table,
2008 RuleMatcher &Rule) const {
2009 InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
2010 unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
2011 Table << MatchTable::Opcode(Opcode: Signed ? "GIR_CopyConstantAsSImm"
2012 : "GIR_CopyConstantAsUImm")
2013 << MatchTable::Comment(Comment: "NewInsnID")
2014 << MatchTable::ULEB128Value(IntValue: NewInsnID)
2015 << MatchTable::Comment(Comment: "OldInsnID")
2016 << MatchTable::ULEB128Value(IntValue: OldInsnVarID)
2017 << MatchTable::Comment(Comment: SymbolicName) << MatchTable::LineBreak;
2018}
2019
2020//===- CopyFConstantAsFPImmRenderer ---------------------------------------===//
2021
2022void CopyFConstantAsFPImmRenderer::emitRenderOpcodes(MatchTable &Table,
2023 RuleMatcher &Rule) const {
2024 InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
2025 unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
2026 Table << MatchTable::Opcode(Opcode: "GIR_CopyFConstantAsFPImm")
2027 << MatchTable::Comment(Comment: "NewInsnID")
2028 << MatchTable::ULEB128Value(IntValue: NewInsnID)
2029 << MatchTable::Comment(Comment: "OldInsnID")
2030 << MatchTable::ULEB128Value(IntValue: OldInsnVarID)
2031 << MatchTable::Comment(Comment: SymbolicName) << MatchTable::LineBreak;
2032}
2033
2034//===- CopySubRegRenderer -------------------------------------------------===//
2035
2036void CopySubRegRenderer::emitRenderOpcodes(MatchTable &Table,
2037 RuleMatcher &Rule) const {
2038 const OperandMatcher &Operand = Rule.getOperandMatcher(Name: SymbolicName);
2039 unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher&: Operand.getInstructionMatcher());
2040 Table << MatchTable::Opcode(Opcode: "GIR_CopySubReg")
2041 << MatchTable::Comment(Comment: "NewInsnID")
2042 << MatchTable::ULEB128Value(IntValue: NewInsnID)
2043 << MatchTable::Comment(Comment: "OldInsnID")
2044 << MatchTable::ULEB128Value(IntValue: OldInsnVarID)
2045 << MatchTable::Comment(Comment: "OpIdx")
2046 << MatchTable::ULEB128Value(IntValue: Operand.getOpIdx())
2047 << MatchTable::Comment(Comment: "SubRegIdx")
2048 << MatchTable::IntValue(NumBytes: 2, IntValue: SubReg->EnumValue)
2049 << MatchTable::Comment(Comment: SymbolicName) << MatchTable::LineBreak;
2050}
2051
2052//===- AddRegisterRenderer ------------------------------------------------===//
2053
2054void AddRegisterRenderer::emitRenderOpcodes(MatchTable &Table,
2055 RuleMatcher &Rule) const {
2056 Table << MatchTable::Opcode(Opcode: "GIR_AddRegister")
2057 << MatchTable::Comment(Comment: "InsnID") << MatchTable::ULEB128Value(IntValue: InsnID);
2058 if (RegisterDef->getName() != "zero_reg") {
2059 Table << MatchTable::NamedValue(
2060 NumBytes: 2,
2061 Namespace: (RegisterDef->getValue(Name: "Namespace")
2062 ? RegisterDef->getValueAsString(FieldName: "Namespace")
2063 : ""),
2064 NamedValue: RegisterDef->getName());
2065 } else {
2066 Table << MatchTable::NamedValue(NumBytes: 2, Namespace: Target.getRegNamespace(), NamedValue: "NoRegister");
2067 }
2068 Table << MatchTable::Comment(Comment: "AddRegisterRegFlags");
2069
2070 // TODO: This is encoded as a 64-bit element, but only 16 or 32-bits are
2071 // really needed for a physical register reference. We can pack the
2072 // register and flags in a single field.
2073 if (IsDef) {
2074 Table << MatchTable::NamedValue(
2075 NumBytes: 2, NamedValue: IsDead ? "static_cast<uint16_t>(RegState::Define|RegState::Dead)"
2076 : "static_cast<uint16_t>(RegState::Define)");
2077 } else {
2078 assert(!IsDead && "A use cannot be dead");
2079 Table << MatchTable::IntValue(NumBytes: 2, IntValue: 0);
2080 }
2081 Table << MatchTable::LineBreak;
2082}
2083
2084//===- TempRegRenderer ----------------------------------------------------===//
2085
2086void TempRegRenderer::emitRenderOpcodes(MatchTable &Table,
2087 RuleMatcher &Rule) const {
2088 const bool NeedsFlags = (SubRegIdx || IsDef);
2089 if (SubRegIdx) {
2090 assert(!IsDef);
2091 Table << MatchTable::Opcode(Opcode: "GIR_AddTempSubRegister");
2092 } else {
2093 Table << MatchTable::Opcode(Opcode: NeedsFlags ? "GIR_AddTempRegister"
2094 : "GIR_AddSimpleTempRegister");
2095 }
2096
2097 Table << MatchTable::Comment(Comment: "InsnID") << MatchTable::ULEB128Value(IntValue: InsnID)
2098 << MatchTable::Comment(Comment: "TempRegID")
2099 << MatchTable::ULEB128Value(IntValue: TempRegID);
2100
2101 if (!NeedsFlags) {
2102 Table << MatchTable::LineBreak;
2103 return;
2104 }
2105
2106 Table << MatchTable::Comment(Comment: "TempRegFlags");
2107 if (IsDef) {
2108 SmallString<32> RegFlags;
2109 RegFlags += "static_cast<uint16_t>(RegState::Define";
2110 if (IsDead)
2111 RegFlags += "|RegState::Dead";
2112 RegFlags += ")";
2113 Table << MatchTable::NamedValue(NumBytes: 2, NamedValue: RegFlags);
2114 } else {
2115 Table << MatchTable::IntValue(NumBytes: 2, IntValue: 0);
2116 }
2117
2118 if (SubRegIdx)
2119 Table << MatchTable::NamedValue(NumBytes: 2, NamedValue: SubRegIdx->getQualifiedName());
2120 Table << MatchTable::LineBreak;
2121}
2122
2123//===- ImmRenderer --------------------------------------------------------===//
2124
2125void ImmRenderer::emitAddImm(MatchTable &Table, RuleMatcher &RM,
2126 unsigned InsnID, int64_t Imm, StringRef ImmName) {
2127 const bool IsInt8 = isInt<8>(x: Imm);
2128
2129 Table << MatchTable::Opcode(Opcode: IsInt8 ? "GIR_AddImm8" : "GIR_AddImm")
2130 << MatchTable::Comment(Comment: "InsnID") << MatchTable::ULEB128Value(IntValue: InsnID)
2131 << MatchTable::Comment(Comment: ImmName)
2132 << MatchTable::IntValue(NumBytes: IsInt8 ? 1 : 8, IntValue: Imm) << MatchTable::LineBreak;
2133}
2134
2135void ImmRenderer::emitRenderOpcodes(MatchTable &Table,
2136 RuleMatcher &Rule) const {
2137 if (CImmLLT) {
2138 assert(Table.isCombiner() &&
2139 "ConstantInt immediate are only for combiners!");
2140 Table << MatchTable::Opcode(Opcode: "GIR_AddCImm") << MatchTable::Comment(Comment: "InsnID")
2141 << MatchTable::ULEB128Value(IntValue: InsnID) << MatchTable::Comment(Comment: "Type")
2142 << *CImmLLT << MatchTable::Comment(Comment: "Imm")
2143 << MatchTable::IntValue(NumBytes: 8, IntValue: Imm) << MatchTable::LineBreak;
2144 } else {
2145 emitAddImm(Table, RM&: Rule, InsnID, Imm);
2146 }
2147}
2148
2149//===- SubRegIndexRenderer ------------------------------------------------===//
2150
2151void SubRegIndexRenderer::emitRenderOpcodes(MatchTable &Table,
2152 RuleMatcher &Rule) const {
2153 ImmRenderer::emitAddImm(Table, RM&: Rule, InsnID, Imm: SubRegIdx->EnumValue,
2154 ImmName: "SubRegIndex");
2155}
2156
2157//===- RenderComplexPatternOperand ----------------------------------------===//
2158
2159void RenderComplexPatternOperand::emitRenderOpcodes(MatchTable &Table,
2160 RuleMatcher &Rule) const {
2161 Table << MatchTable::Opcode(
2162 Opcode: SubOperand ? (SubReg ? "GIR_ComplexSubOperandSubRegRenderer"
2163 : "GIR_ComplexSubOperandRenderer")
2164 : "GIR_ComplexRenderer")
2165 << MatchTable::Comment(Comment: "InsnID") << MatchTable::ULEB128Value(IntValue: InsnID)
2166 << MatchTable::Comment(Comment: "RendererID")
2167 << MatchTable::IntValue(NumBytes: 2, IntValue: RendererID);
2168 if (SubOperand)
2169 Table << MatchTable::Comment(Comment: "SubOperand")
2170 << MatchTable::ULEB128Value(IntValue: *SubOperand);
2171 if (SubReg)
2172 Table << MatchTable::Comment(Comment: "SubRegIdx")
2173 << MatchTable::IntValue(NumBytes: 2, IntValue: SubReg->EnumValue);
2174 Table << MatchTable::Comment(Comment: SymbolicName) << MatchTable::LineBreak;
2175}
2176
2177//===- IntrinsicIDRenderer ------------------------------------------------===//
2178
2179void IntrinsicIDRenderer::emitRenderOpcodes(MatchTable &Table,
2180 RuleMatcher &Rule) const {
2181 Table << MatchTable::Opcode(Opcode: "GIR_AddIntrinsicID") << MatchTable::Comment(Comment: "MI")
2182 << MatchTable::ULEB128Value(IntValue: InsnID)
2183 << MatchTable::NamedValue(NumBytes: 2, NamedValue: "Intrinsic::" + II->EnumName.str())
2184 << MatchTable::LineBreak;
2185}
2186
2187//===- CustomRenderer -----------------------------------------------------===//
2188
2189void CustomRenderer::emitRenderOpcodes(MatchTable &Table,
2190 RuleMatcher &Rule) const {
2191 InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
2192 unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
2193 Table << MatchTable::Opcode(Opcode: "GIR_CustomRenderer")
2194 << MatchTable::Comment(Comment: "InsnID") << MatchTable::ULEB128Value(IntValue: InsnID)
2195 << MatchTable::Comment(Comment: "OldInsnID")
2196 << MatchTable::ULEB128Value(IntValue: OldInsnVarID)
2197 << MatchTable::Comment(Comment: "Renderer")
2198 << MatchTable::NamedValue(
2199 NumBytes: 2, NamedValue: "GICR_" + Renderer.getValueAsString(FieldName: "RendererFn").str())
2200 << MatchTable::Comment(Comment: SymbolicName) << MatchTable::LineBreak;
2201}
2202
2203//===- CustomOperandRenderer ----------------------------------------------===//
2204
2205void CustomOperandRenderer::emitRenderOpcodes(MatchTable &Table,
2206 RuleMatcher &Rule) const {
2207 const OperandMatcher &OpdMatcher = Rule.getOperandMatcher(Name: SymbolicName);
2208 Table << MatchTable::Opcode(Opcode: "GIR_CustomOperandRenderer")
2209 << MatchTable::Comment(Comment: "InsnID") << MatchTable::ULEB128Value(IntValue: InsnID)
2210 << MatchTable::Comment(Comment: "OldInsnID")
2211 << MatchTable::ULEB128Value(IntValue: OpdMatcher.getInsnVarID())
2212 << MatchTable::Comment(Comment: "OpIdx")
2213 << MatchTable::ULEB128Value(IntValue: OpdMatcher.getOpIdx())
2214 << MatchTable::Comment(Comment: "OperandRenderer")
2215 << MatchTable::NamedValue(
2216 NumBytes: 2, NamedValue: "GICR_" + Renderer.getValueAsString(FieldName: "RendererFn").str())
2217 << MatchTable::Comment(Comment: SymbolicName) << MatchTable::LineBreak;
2218}
2219
2220//===- BuildMIAction ------------------------------------------------------===//
2221
2222bool BuildMIAction::canMutate(RuleMatcher &Rule,
2223 const InstructionMatcher *Insn) const {
2224 if (!Insn || Insn->hasVariadicMatcher())
2225 return false;
2226
2227 if (OperandRenderers.size() != Insn->getNumOperandMatchers())
2228 return false;
2229
2230 for (const auto &Renderer : enumerate(First: OperandRenderers)) {
2231 if (const auto *Copy = dyn_cast<CopyRenderer>(Val: &*Renderer.value())) {
2232 const OperandMatcher &OM =
2233 Rule.getOperandMatcher(Name: Copy->getSymbolicName());
2234 if (Insn != &OM.getInstructionMatcher() ||
2235 OM.getOpIdx() != Renderer.index())
2236 return false;
2237 } else {
2238 return false;
2239 }
2240 }
2241
2242 return true;
2243}
2244
2245void BuildMIAction::chooseInsnToMutate(RuleMatcher &Rule) {
2246 for (auto *MutateCandidate : Rule.mutatable_insns()) {
2247 if (canMutate(Rule, Insn: MutateCandidate)) {
2248 // Take the first one we're offered that we're able to mutate.
2249 Rule.reserveInsnMatcherForMutation(InsnMatcher: MutateCandidate);
2250 Matched = MutateCandidate;
2251 return;
2252 }
2253 }
2254}
2255
2256void BuildMIAction::emitActionOpcodes(MatchTable &Table,
2257 RuleMatcher &Rule) const {
2258 const auto AddMIFlags = [&]() {
2259 for (const InstructionMatcher *IM : CopiedFlags) {
2260 Table << MatchTable::Opcode(Opcode: "GIR_CopyMIFlags")
2261 << MatchTable::Comment(Comment: "InsnID") << MatchTable::ULEB128Value(IntValue: InsnID)
2262 << MatchTable::Comment(Comment: "OldInsnID")
2263 << MatchTable::ULEB128Value(IntValue: IM->getInsnVarID())
2264 << MatchTable::LineBreak;
2265 }
2266
2267 if (!SetFlags.empty()) {
2268 Table << MatchTable::Opcode(Opcode: "GIR_SetMIFlags")
2269 << MatchTable::Comment(Comment: "InsnID") << MatchTable::ULEB128Value(IntValue: InsnID)
2270 << MatchTable::NamedValue(NumBytes: 4, NamedValue: join(R: SetFlags, Separator: " | "))
2271 << MatchTable::LineBreak;
2272 }
2273
2274 if (!UnsetFlags.empty()) {
2275 Table << MatchTable::Opcode(Opcode: "GIR_UnsetMIFlags")
2276 << MatchTable::Comment(Comment: "InsnID") << MatchTable::ULEB128Value(IntValue: InsnID)
2277 << MatchTable::NamedValue(NumBytes: 4, NamedValue: join(R: UnsetFlags, Separator: " | "))
2278 << MatchTable::LineBreak;
2279 }
2280 };
2281
2282 if (Matched) {
2283 assert(canMutate(Rule, Matched) &&
2284 "Arranged to mutate an insn that isn't mutatable");
2285
2286 unsigned RecycleInsnID = Rule.getInsnVarID(InsnMatcher&: *Matched);
2287 Table << MatchTable::Opcode(Opcode: "GIR_MutateOpcode")
2288 << MatchTable::Comment(Comment: "InsnID") << MatchTable::ULEB128Value(IntValue: InsnID)
2289 << MatchTable::Comment(Comment: "RecycleInsnID")
2290 << MatchTable::ULEB128Value(IntValue: RecycleInsnID)
2291 << MatchTable::Comment(Comment: "Opcode")
2292 << MatchTable::NamedValue(NumBytes: 2, Namespace: I->Namespace, NamedValue: I->getName())
2293 << MatchTable::LineBreak;
2294
2295 if (!I->ImplicitDefs.empty() || !I->ImplicitUses.empty()) {
2296 for (auto *Def : I->ImplicitDefs) {
2297 auto Namespace = Def->getValue(Name: "Namespace")
2298 ? Def->getValueAsString(FieldName: "Namespace")
2299 : "";
2300 const bool IsDead = DeadImplicitDefs.contains(Ptr: Def);
2301 Table << MatchTable::Opcode(Opcode: "GIR_AddImplicitDef")
2302 << MatchTable::Comment(Comment: "InsnID")
2303 << MatchTable::ULEB128Value(IntValue: InsnID)
2304 << MatchTable::NamedValue(NumBytes: 2, Namespace, NamedValue: Def->getName())
2305 << (IsDead ? MatchTable::NamedValue(
2306 NumBytes: 2, NamedValue: "static_cast<unsigned>(RegState::Dead)")
2307 : MatchTable::IntValue(NumBytes: 2, IntValue: 0))
2308 << MatchTable::LineBreak;
2309 }
2310 for (auto *Use : I->ImplicitUses) {
2311 auto Namespace = Use->getValue(Name: "Namespace")
2312 ? Use->getValueAsString(FieldName: "Namespace")
2313 : "";
2314 Table << MatchTable::Opcode(Opcode: "GIR_AddImplicitUse")
2315 << MatchTable::Comment(Comment: "InsnID")
2316 << MatchTable::ULEB128Value(IntValue: InsnID)
2317 << MatchTable::NamedValue(NumBytes: 2, Namespace, NamedValue: Use->getName())
2318 << MatchTable::LineBreak;
2319 }
2320 }
2321
2322 AddMIFlags();
2323
2324 // Mark the mutated instruction as erased.
2325 Rule.tryEraseInsnID(ID: RecycleInsnID);
2326 return;
2327 }
2328
2329 // TODO: Simple permutation looks like it could be almost as common as
2330 // mutation due to commutative operations.
2331
2332 if (InsnID == 0) {
2333 Table << MatchTable::Opcode(Opcode: "GIR_BuildRootMI");
2334 } else {
2335 Table << MatchTable::Opcode(Opcode: "GIR_BuildMI") << MatchTable::Comment(Comment: "InsnID")
2336 << MatchTable::ULEB128Value(IntValue: InsnID);
2337 }
2338
2339 Table << MatchTable::Comment(Comment: "Opcode")
2340 << MatchTable::NamedValue(NumBytes: 2, Namespace: I->Namespace, NamedValue: I->getName())
2341 << MatchTable::LineBreak;
2342
2343 for (const auto &Renderer : OperandRenderers)
2344 Renderer->emitRenderOpcodes(Table, Rule);
2345
2346 for (auto [OpIdx, Def] : enumerate(First: I->ImplicitDefs)) {
2347 auto Namespace =
2348 Def->getValue(Name: "Namespace") ? Def->getValueAsString(FieldName: "Namespace") : "";
2349 if (DeadImplicitDefs.contains(Ptr: Def)) {
2350 Table
2351 << MatchTable::Opcode(Opcode: "GIR_SetImplicitDefDead")
2352 << MatchTable::Comment(Comment: "InsnID") << MatchTable::ULEB128Value(IntValue: InsnID)
2353 << MatchTable::Comment(
2354 Comment: ("OpIdx for " + Namespace + "::" + Def->getName() + "").str())
2355 << MatchTable::ULEB128Value(IntValue: OpIdx) << MatchTable::LineBreak;
2356 }
2357 }
2358
2359 if (I->mayLoad || I->mayStore) {
2360 // Emit the ID's for all the instructions that are matched by this rule.
2361 // TODO: Limit this to matched instructions that mayLoad/mayStore or have
2362 // some other means of having a memoperand. Also limit this to
2363 // emitted instructions that expect to have a memoperand too. For
2364 // example, (G_SEXT (G_LOAD x)) that results in separate load and
2365 // sign-extend instructions shouldn't put the memoperand on the
2366 // sign-extend since it has no effect there.
2367
2368 std::vector<unsigned> MergeInsnIDs;
2369 for (const auto &IDMatcherPair : Rule.defined_insn_vars())
2370 MergeInsnIDs.push_back(x: IDMatcherPair.second);
2371 llvm::sort(C&: MergeInsnIDs);
2372
2373 Table << MatchTable::Opcode(Opcode: "GIR_MergeMemOperands")
2374 << MatchTable::Comment(Comment: "InsnID") << MatchTable::ULEB128Value(IntValue: InsnID)
2375 << MatchTable::Comment(Comment: "NumInsns")
2376 << MatchTable::IntValue(NumBytes: 1, IntValue: MergeInsnIDs.size())
2377 << MatchTable::Comment(Comment: "MergeInsnID's");
2378 for (const auto &MergeInsnID : MergeInsnIDs)
2379 Table << MatchTable::ULEB128Value(IntValue: MergeInsnID);
2380 Table << MatchTable::LineBreak;
2381 }
2382
2383 AddMIFlags();
2384}
2385
2386//===- BuildConstantAction ------------------------------------------------===//
2387
2388void BuildConstantAction::emitActionOpcodes(MatchTable &Table,
2389 RuleMatcher &Rule) const {
2390 Table << MatchTable::Opcode(Opcode: "GIR_BuildConstant")
2391 << MatchTable::Comment(Comment: "TempRegID")
2392 << MatchTable::ULEB128Value(IntValue: TempRegID) << MatchTable::Comment(Comment: "Val")
2393 << MatchTable::IntValue(NumBytes: 8, IntValue: Val) << MatchTable::LineBreak;
2394}
2395
2396//===- EraseInstAction ----------------------------------------------------===//
2397
2398void EraseInstAction::emitActionOpcodes(MatchTable &Table,
2399 RuleMatcher &Rule) const {
2400 // Avoid erasing the same inst twice.
2401 if (!Rule.tryEraseInsnID(ID: InsnID))
2402 return;
2403
2404 Table << MatchTable::Opcode(Opcode: "GIR_EraseFromParent")
2405 << MatchTable::Comment(Comment: "InsnID") << MatchTable::ULEB128Value(IntValue: InsnID)
2406 << MatchTable::LineBreak;
2407}
2408
2409bool EraseInstAction::emitActionOpcodesAndDone(MatchTable &Table,
2410 RuleMatcher &Rule) const {
2411 if (InsnID != 0) {
2412 emitActionOpcodes(Table, Rule);
2413 return false;
2414 }
2415
2416 if (!Rule.tryEraseInsnID(ID: 0))
2417 return false;
2418
2419 Table << MatchTable::Opcode(Opcode: "GIR_EraseRootFromParent_Done", IndentAdjust: -1)
2420 << MatchTable::LineBreak;
2421 return true;
2422}
2423
2424//===- ReplaceRegAction ---------------------------------------------------===//
2425
2426void ReplaceRegAction::emitAdditionalPredicates(MatchTable &Table,
2427 RuleMatcher &Rule) const {
2428 if (TempRegID != (unsigned)-1)
2429 return;
2430
2431 Table << MatchTable::Opcode(Opcode: "GIM_CheckCanReplaceReg")
2432 << MatchTable::Comment(Comment: "OldInsnID")
2433 << MatchTable::ULEB128Value(IntValue: OldInsnID)
2434 << MatchTable::Comment(Comment: "OldOpIdx") << MatchTable::ULEB128Value(IntValue: OldOpIdx)
2435 << MatchTable::Comment(Comment: "NewInsnId")
2436 << MatchTable::ULEB128Value(IntValue: NewInsnId)
2437 << MatchTable::Comment(Comment: "NewOpIdx") << MatchTable::ULEB128Value(IntValue: NewOpIdx)
2438 << MatchTable::LineBreak;
2439}
2440
2441void ReplaceRegAction::emitActionOpcodes(MatchTable &Table,
2442 RuleMatcher &Rule) const {
2443 if (TempRegID != (unsigned)-1) {
2444 Table << MatchTable::Opcode(Opcode: "GIR_ReplaceRegWithTempReg")
2445 << MatchTable::Comment(Comment: "OldInsnID")
2446 << MatchTable::ULEB128Value(IntValue: OldInsnID)
2447 << MatchTable::Comment(Comment: "OldOpIdx")
2448 << MatchTable::ULEB128Value(IntValue: OldOpIdx)
2449 << MatchTable::Comment(Comment: "TempRegID")
2450 << MatchTable::ULEB128Value(IntValue: TempRegID) << MatchTable::LineBreak;
2451 } else {
2452 Table << MatchTable::Opcode(Opcode: "GIR_ReplaceReg")
2453 << MatchTable::Comment(Comment: "OldInsnID")
2454 << MatchTable::ULEB128Value(IntValue: OldInsnID)
2455 << MatchTable::Comment(Comment: "OldOpIdx")
2456 << MatchTable::ULEB128Value(IntValue: OldOpIdx)
2457 << MatchTable::Comment(Comment: "NewInsnId")
2458 << MatchTable::ULEB128Value(IntValue: NewInsnId)
2459 << MatchTable::Comment(Comment: "NewOpIdx")
2460 << MatchTable::ULEB128Value(IntValue: NewOpIdx) << MatchTable::LineBreak;
2461 }
2462}
2463
2464//===- ConstrainOperandToRegClassAction -----------------------------------===//
2465
2466void ConstrainOperandToRegClassAction::emitActionOpcodes(
2467 MatchTable &Table, RuleMatcher &Rule) const {
2468 Table << MatchTable::Opcode(Opcode: "GIR_ConstrainOperandRC")
2469 << MatchTable::Comment(Comment: "InsnID") << MatchTable::ULEB128Value(IntValue: InsnID)
2470 << MatchTable::Comment(Comment: "Op") << MatchTable::ULEB128Value(IntValue: OpIdx)
2471 << MatchTable::NamedValue(NumBytes: 2, NamedValue: RC.getQualifiedIdName())
2472 << MatchTable::LineBreak;
2473}
2474
2475//===- MakeTempRegisterAction ---------------------------------------------===//
2476
2477void MakeTempRegisterAction::emitActionOpcodes(MatchTable &Table,
2478 RuleMatcher &Rule) const {
2479 Table << MatchTable::Opcode(Opcode: "GIR_MakeTempReg")
2480 << MatchTable::Comment(Comment: "TempRegID")
2481 << MatchTable::ULEB128Value(IntValue: TempRegID) << MatchTable::Comment(Comment: "TypeID")
2482 << Ty << MatchTable::LineBreak;
2483}
2484