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