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