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