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