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 "CodeGenInstruction.h"
11 #include "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::make_tuple(Ty.isScalable(),
412 Ty.getElementCount().getKnownMinValue()) <
413 std::make_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::make_tuple(Ty.isScalable(),
420 Ty.getSizeInBits().getKnownMinValue()) <
421 std::make_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 optimizeRules<GroupMatcher>(Matchers, MatcherStorage).swap(Matchers);
549 optimizeRules<SwitchMatcher>(Matchers, MatcherStorage).swap(Matchers);
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::make_tuple(L->getKind(), L->getInsnVarID(), L->getOpIdx()) <
724 std::make_tuple(R->getKind(), R->getInsnVarID(), R->getOpIdx());
725 });
726 }
727
hasFirstCondition() const728 bool RuleMatcher::hasFirstCondition() const {
729 if (insnmatchers_empty())
730 return false;
731 InstructionMatcher &Matcher = insnmatchers_front();
732 if (!Matcher.predicates_empty())
733 return true;
734 for (auto &OM : Matcher.operands())
735 for (auto &OP : OM->predicates())
736 if (!isa<InstructionOperandMatcher>(OP))
737 return true;
738 return false;
739 }
740
getFirstCondition() const741 const PredicateMatcher &RuleMatcher::getFirstCondition() const {
742 assert(!insnmatchers_empty() &&
743 "Trying to get a condition from an empty RuleMatcher");
744
745 InstructionMatcher &Matcher = insnmatchers_front();
746 if (!Matcher.predicates_empty())
747 return **Matcher.predicates_begin();
748 // If there is no more predicate on the instruction itself, look at its
749 // operands.
750 for (auto &OM : Matcher.operands())
751 for (auto &OP : OM->predicates())
752 if (!isa<InstructionOperandMatcher>(OP))
753 return *OP;
754
755 llvm_unreachable("Trying to get a condition from an InstructionMatcher with "
756 "no conditions");
757 }
758
popFirstCondition()759 std::unique_ptr<PredicateMatcher> RuleMatcher::popFirstCondition() {
760 assert(!insnmatchers_empty() &&
761 "Trying to pop a condition from an empty RuleMatcher");
762
763 InstructionMatcher &Matcher = insnmatchers_front();
764 if (!Matcher.predicates_empty())
765 return Matcher.predicates_pop_front();
766 // If there is no more predicate on the instruction itself, look at its
767 // operands.
768 for (auto &OM : Matcher.operands())
769 for (auto &OP : OM->predicates())
770 if (!isa<InstructionOperandMatcher>(OP)) {
771 std::unique_ptr<PredicateMatcher> Result = std::move(OP);
772 OM->eraseNullPredicates();
773 return Result;
774 }
775
776 llvm_unreachable("Trying to pop a condition from an InstructionMatcher with "
777 "no conditions");
778 }
779
updateGISelFlag(GISelFlags CurFlags,const Record * R,StringRef FlagName,GISelFlags FlagBit)780 GISelFlags RuleMatcher::updateGISelFlag(GISelFlags CurFlags, const Record *R,
781 StringRef FlagName,
782 GISelFlags FlagBit) {
783 // If the value of a flag is unset, ignore it.
784 // If it's set, it always takes precedence over the existing value so
785 // clear/set the corresponding bit.
786 bool Unset = false;
787 bool Value = R->getValueAsBitOrUnset("GIIgnoreCopies", Unset);
788 if (!Unset)
789 return Value ? (CurFlags | FlagBit) : (CurFlags & ~FlagBit);
790 return CurFlags;
791 }
792
setGISelFlags(const Record * R)793 SaveAndRestore<GISelFlags> RuleMatcher::setGISelFlags(const Record *R) {
794 if (!R || !R->isSubClassOf("GISelFlags"))
795 return {Flags, Flags};
796
797 assert((R->isSubClassOf("PatFrags") || R->isSubClassOf("Pattern")) &&
798 "GISelFlags is only expected on Pattern/PatFrags!");
799
800 GISelFlags NewFlags =
801 updateGISelFlag(Flags, R, "GIIgnoreCopies", GISF_IgnoreCopies);
802 return {Flags, NewFlags};
803 }
804
defineComplexSubOperand(StringRef SymbolicName,Record * ComplexPattern,unsigned RendererID,unsigned SubOperandID,StringRef ParentSymbolicName)805 Error RuleMatcher::defineComplexSubOperand(StringRef SymbolicName,
806 Record *ComplexPattern,
807 unsigned RendererID,
808 unsigned SubOperandID,
809 StringRef ParentSymbolicName) {
810 std::string ParentName(ParentSymbolicName);
811 if (ComplexSubOperands.count(SymbolicName)) {
812 const std::string &RecordedParentName =
813 ComplexSubOperandsParentName[SymbolicName];
814 if (RecordedParentName != ParentName)
815 return failUnsupported("Error: Complex suboperand " + SymbolicName +
816 " referenced by different operands: " +
817 RecordedParentName + " and " + ParentName + ".");
818 // Complex suboperand referenced more than once from same the operand is
819 // used to generate 'same operand check'. Emitting of
820 // GIR_ComplexSubOperandRenderer for them is already handled.
821 return Error::success();
822 }
823
824 ComplexSubOperands[SymbolicName] =
825 std::make_tuple(ComplexPattern, RendererID, SubOperandID);
826 ComplexSubOperandsParentName[SymbolicName] = ParentName;
827
828 return Error::success();
829 }
830
addInstructionMatcher(StringRef SymbolicName)831 InstructionMatcher &RuleMatcher::addInstructionMatcher(StringRef SymbolicName) {
832 Matchers.emplace_back(new InstructionMatcher(*this, SymbolicName));
833 MutatableInsns.insert(Matchers.back().get());
834 return *Matchers.back();
835 }
836
addRequiredSimplePredicate(StringRef PredName)837 void RuleMatcher::addRequiredSimplePredicate(StringRef PredName) {
838 RequiredSimplePredicates.push_back(PredName.str());
839 }
840
getRequiredSimplePredicates()841 const std::vector<std::string> &RuleMatcher::getRequiredSimplePredicates() {
842 return RequiredSimplePredicates;
843 }
844
addRequiredFeature(Record * Feature)845 void RuleMatcher::addRequiredFeature(Record *Feature) {
846 RequiredFeatures.push_back(Feature);
847 }
848
getRequiredFeatures() const849 const std::vector<Record *> &RuleMatcher::getRequiredFeatures() const {
850 return RequiredFeatures;
851 }
852
implicitlyDefineInsnVar(InstructionMatcher & Matcher)853 unsigned RuleMatcher::implicitlyDefineInsnVar(InstructionMatcher &Matcher) {
854 unsigned NewInsnVarID = NextInsnVarID++;
855 InsnVariableIDs[&Matcher] = NewInsnVarID;
856 return NewInsnVarID;
857 }
858
getInsnVarID(InstructionMatcher & InsnMatcher) const859 unsigned RuleMatcher::getInsnVarID(InstructionMatcher &InsnMatcher) const {
860 const auto &I = InsnVariableIDs.find(&InsnMatcher);
861 if (I != InsnVariableIDs.end())
862 return I->second;
863 llvm_unreachable("Matched Insn was not captured in a local variable");
864 }
865
defineOperand(StringRef SymbolicName,OperandMatcher & OM)866 void RuleMatcher::defineOperand(StringRef SymbolicName, OperandMatcher &OM) {
867 if (!DefinedOperands.contains(SymbolicName)) {
868 DefinedOperands[SymbolicName] = &OM;
869 return;
870 }
871
872 // If the operand is already defined, then we must ensure both references in
873 // the matcher have the exact same node.
874 RuleMatcher &RM = OM.getInstructionMatcher().getRuleMatcher();
875 OM.addPredicate<SameOperandMatcher>(
876 OM.getSymbolicName(), getOperandMatcher(OM.getSymbolicName()).getOpIdx(),
877 RM.getGISelFlags());
878 }
879
definePhysRegOperand(Record * Reg,OperandMatcher & OM)880 void RuleMatcher::definePhysRegOperand(Record *Reg, OperandMatcher &OM) {
881 if (!PhysRegOperands.contains(Reg)) {
882 PhysRegOperands[Reg] = &OM;
883 return;
884 }
885 }
886
887 InstructionMatcher &
getInstructionMatcher(StringRef SymbolicName) const888 RuleMatcher::getInstructionMatcher(StringRef SymbolicName) const {
889 for (const auto &I : InsnVariableIDs)
890 if (I.first->getSymbolicName() == SymbolicName)
891 return *I.first;
892 llvm_unreachable(
893 ("Failed to lookup instruction " + SymbolicName).str().c_str());
894 }
895
getPhysRegOperandMatcher(Record * Reg) const896 const OperandMatcher &RuleMatcher::getPhysRegOperandMatcher(Record *Reg) const {
897 const auto &I = PhysRegOperands.find(Reg);
898
899 if (I == PhysRegOperands.end()) {
900 PrintFatalError(SrcLoc, "Register " + Reg->getName() +
901 " was not declared in matcher");
902 }
903
904 return *I->second;
905 }
906
getOperandMatcher(StringRef Name)907 OperandMatcher &RuleMatcher::getOperandMatcher(StringRef Name) {
908 const auto &I = DefinedOperands.find(Name);
909
910 if (I == DefinedOperands.end())
911 PrintFatalError(SrcLoc, "Operand " + Name + " was not declared in matcher");
912
913 return *I->second;
914 }
915
getOperandMatcher(StringRef Name) const916 const OperandMatcher &RuleMatcher::getOperandMatcher(StringRef Name) const {
917 const auto &I = DefinedOperands.find(Name);
918
919 if (I == DefinedOperands.end())
920 PrintFatalError(SrcLoc, "Operand " + Name + " was not declared in matcher");
921
922 return *I->second;
923 }
924
emit(MatchTable & Table)925 void RuleMatcher::emit(MatchTable &Table) {
926 if (Matchers.empty())
927 llvm_unreachable("Unexpected empty matcher!");
928
929 // The representation supports rules that require multiple roots such as:
930 // %ptr(p0) = ...
931 // %elt0(s32) = G_LOAD %ptr
932 // %1(p0) = G_ADD %ptr, 4
933 // %elt1(s32) = G_LOAD p0 %1
934 // which could be usefully folded into:
935 // %ptr(p0) = ...
936 // %elt0(s32), %elt1(s32) = TGT_LOAD_PAIR %ptr
937 // on some targets but we don't need to make use of that yet.
938 assert(Matchers.size() == 1 && "Cannot handle multi-root matchers yet");
939
940 unsigned LabelID = Table.allocateLabelID();
941 Table << MatchTable::Opcode("GIM_Try", +1)
942 << MatchTable::Comment("On fail goto")
943 << MatchTable::JumpTarget(LabelID)
944 << MatchTable::Comment(("Rule ID " + Twine(RuleID) + " //").str())
945 << MatchTable::LineBreak;
946
947 if (!RequiredFeatures.empty() || HwModeIdx >= 0) {
948 Table << MatchTable::Opcode("GIM_CheckFeatures")
949 << MatchTable::NamedValue(
950 2, getNameForFeatureBitset(RequiredFeatures, HwModeIdx))
951 << MatchTable::LineBreak;
952 }
953
954 if (!RequiredSimplePredicates.empty()) {
955 for (const auto &Pred : RequiredSimplePredicates) {
956 Table << MatchTable::Opcode("GIM_CheckSimplePredicate")
957 << MatchTable::NamedValue(2, Pred) << MatchTable::LineBreak;
958 }
959 }
960
961 Matchers.front()->emitPredicateOpcodes(Table, *this);
962
963 // Check if it's safe to replace registers.
964 for (const auto &MA : Actions)
965 MA->emitAdditionalPredicates(Table, *this);
966
967 // We must also check if it's safe to fold the matched instructions.
968 if (InsnVariableIDs.size() >= 2) {
969 // Invert the map to create stable ordering (by var names)
970 SmallVector<unsigned, 2> InsnIDs;
971 for (const auto &Pair : InsnVariableIDs) {
972 // Skip the root node since it isn't moving anywhere. Everything else is
973 // sinking to meet it.
974 if (Pair.first == Matchers.front().get())
975 continue;
976
977 InsnIDs.push_back(Pair.second);
978 }
979 llvm::sort(InsnIDs);
980
981 for (const auto &InsnID : InsnIDs) {
982 // Reject the difficult cases until we have a more accurate check.
983 Table << MatchTable::Opcode("GIM_CheckIsSafeToFold")
984 << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
985 << MatchTable::LineBreak;
986
987 // FIXME: Emit checks to determine it's _actually_ safe to fold and/or
988 // account for unsafe cases.
989 //
990 // Example:
991 // MI1--> %0 = ...
992 // %1 = ... %0
993 // MI0--> %2 = ... %0
994 // It's not safe to erase MI1. We currently handle this by not
995 // erasing %0 (even when it's dead).
996 //
997 // Example:
998 // MI1--> %0 = load volatile @a
999 // %1 = load volatile @a
1000 // MI0--> %2 = ... %0
1001 // It's not safe to sink %0's def past %1. We currently handle
1002 // this by rejecting all loads.
1003 //
1004 // Example:
1005 // MI1--> %0 = load @a
1006 // %1 = store @a
1007 // MI0--> %2 = ... %0
1008 // It's not safe to sink %0's def past %1. We currently handle
1009 // this by rejecting all loads.
1010 //
1011 // Example:
1012 // G_CONDBR %cond, @BB1
1013 // BB0:
1014 // MI1--> %0 = load @a
1015 // G_BR @BB1
1016 // BB1:
1017 // MI0--> %2 = ... %0
1018 // It's not always safe to sink %0 across control flow. In this
1019 // case it may introduce a memory fault. We currentl handle
1020 // this by rejecting all loads.
1021 }
1022 }
1023
1024 for (const auto &PM : EpilogueMatchers)
1025 PM->emitPredicateOpcodes(Table, *this);
1026
1027 for (const auto &MA : Actions)
1028 MA->emitActionOpcodes(Table, *this);
1029
1030 assert((Table.isWithCoverage() ? !Table.isCombiner() : true) &&
1031 "Combiner tables don't support coverage!");
1032 if (Table.isWithCoverage())
1033 Table << MatchTable::Opcode("GIR_Coverage")
1034 << MatchTable::IntValue(4, RuleID) << MatchTable::LineBreak;
1035 else if (!Table.isCombiner())
1036 Table << MatchTable::Comment(("GIR_Coverage, " + Twine(RuleID) + ",").str())
1037 << MatchTable::LineBreak;
1038
1039 Table << MatchTable::Opcode("GIR_Done", -1) << MatchTable::LineBreak
1040 << MatchTable::Label(LabelID);
1041 ++NumPatternEmitted;
1042 }
1043
isHigherPriorityThan(const RuleMatcher & B) const1044 bool RuleMatcher::isHigherPriorityThan(const RuleMatcher &B) const {
1045 // Rules involving more match roots have higher priority.
1046 if (Matchers.size() > B.Matchers.size())
1047 return true;
1048 if (Matchers.size() < B.Matchers.size())
1049 return false;
1050
1051 for (auto Matcher : zip(Matchers, B.Matchers)) {
1052 if (std::get<0>(Matcher)->isHigherPriorityThan(*std::get<1>(Matcher)))
1053 return true;
1054 if (std::get<1>(Matcher)->isHigherPriorityThan(*std::get<0>(Matcher)))
1055 return false;
1056 }
1057
1058 return false;
1059 }
1060
countRendererFns() const1061 unsigned RuleMatcher::countRendererFns() const {
1062 return std::accumulate(
1063 Matchers.begin(), Matchers.end(), 0,
1064 [](unsigned A, const std::unique_ptr<InstructionMatcher> &Matcher) {
1065 return A + Matcher->countRendererFns();
1066 });
1067 }
1068
1069 //===- PredicateMatcher ---------------------------------------------------===//
1070
~PredicateMatcher()1071 PredicateMatcher::~PredicateMatcher() {}
1072
1073 //===- OperandPredicateMatcher --------------------------------------------===//
1074
~OperandPredicateMatcher()1075 OperandPredicateMatcher::~OperandPredicateMatcher() {}
1076
isHigherPriorityThan(const OperandPredicateMatcher & B) const1077 bool OperandPredicateMatcher::isHigherPriorityThan(
1078 const OperandPredicateMatcher &B) const {
1079 // Generally speaking, an instruction is more important than an Int or a
1080 // LiteralInt because it can cover more nodes but theres an exception to
1081 // this. G_CONSTANT's are less important than either of those two because they
1082 // are more permissive.
1083
1084 const InstructionOperandMatcher *AOM =
1085 dyn_cast<InstructionOperandMatcher>(this);
1086 const InstructionOperandMatcher *BOM =
1087 dyn_cast<InstructionOperandMatcher>(&B);
1088 bool AIsConstantInsn = AOM && AOM->getInsnMatcher().isConstantInstruction();
1089 bool BIsConstantInsn = BOM && BOM->getInsnMatcher().isConstantInstruction();
1090
1091 if (AOM && BOM) {
1092 // The relative priorities between a G_CONSTANT and any other instruction
1093 // don't actually matter but this code is needed to ensure a strict weak
1094 // ordering. This is particularly important on Windows where the rules will
1095 // be incorrectly sorted without it.
1096 if (AIsConstantInsn != BIsConstantInsn)
1097 return AIsConstantInsn < BIsConstantInsn;
1098 return false;
1099 }
1100
1101 if (AOM && AIsConstantInsn && (B.Kind == OPM_Int || B.Kind == OPM_LiteralInt))
1102 return false;
1103 if (BOM && BIsConstantInsn && (Kind == OPM_Int || Kind == OPM_LiteralInt))
1104 return true;
1105
1106 return Kind < B.Kind;
1107 }
1108
1109 //===- SameOperandMatcher -------------------------------------------------===//
1110
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1111 void SameOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
1112 RuleMatcher &Rule) const {
1113 const OperandMatcher &OtherOM = Rule.getOperandMatcher(MatchingName);
1114 unsigned OtherInsnVarID = Rule.getInsnVarID(OtherOM.getInstructionMatcher());
1115 assert(OtherInsnVarID == OtherOM.getInstructionMatcher().getInsnVarID());
1116 const bool IgnoreCopies = Flags & GISF_IgnoreCopies;
1117 Table << MatchTable::Opcode(IgnoreCopies
1118 ? "GIM_CheckIsSameOperandIgnoreCopies"
1119 : "GIM_CheckIsSameOperand")
1120 << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
1121 << MatchTable::Comment("OpIdx") << MatchTable::ULEB128Value(OpIdx)
1122 << MatchTable::Comment("OtherMI")
1123 << MatchTable::ULEB128Value(OtherInsnVarID)
1124 << MatchTable::Comment("OtherOpIdx")
1125 << MatchTable::ULEB128Value(OtherOM.getOpIdx())
1126 << MatchTable::LineBreak;
1127 }
1128
1129 //===- LLTOperandMatcher --------------------------------------------------===//
1130
1131 std::map<LLTCodeGen, unsigned> LLTOperandMatcher::TypeIDValues;
1132
getValue() const1133 MatchTableRecord LLTOperandMatcher::getValue() const {
1134 const auto VI = TypeIDValues.find(Ty);
1135 if (VI == TypeIDValues.end())
1136 return MatchTable::NamedValue(1, getTy().getCxxEnumValue());
1137 return MatchTable::NamedValue(1, getTy().getCxxEnumValue(), VI->second);
1138 }
1139
hasValue() const1140 bool LLTOperandMatcher::hasValue() const {
1141 if (TypeIDValues.size() != KnownTypes.size())
1142 initTypeIDValuesMap();
1143 return TypeIDValues.count(Ty);
1144 }
1145
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1146 void LLTOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
1147 RuleMatcher &Rule) const {
1148 Table << MatchTable::Opcode("GIM_CheckType") << MatchTable::Comment("MI")
1149 << MatchTable::ULEB128Value(InsnVarID) << MatchTable::Comment("Op")
1150 << MatchTable::ULEB128Value(OpIdx) << MatchTable::Comment("Type")
1151 << getValue() << MatchTable::LineBreak;
1152 }
1153
1154 //===- PointerToAnyOperandMatcher -----------------------------------------===//
1155
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1156 void PointerToAnyOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
1157 RuleMatcher &Rule) const {
1158 Table << MatchTable::Opcode("GIM_CheckPointerToAny")
1159 << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
1160 << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx)
1161 << MatchTable::Comment("SizeInBits")
1162 << MatchTable::ULEB128Value(SizeInBits) << MatchTable::LineBreak;
1163 }
1164
1165 //===- RecordNamedOperandMatcher ------------------------------------------===//
1166
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1167 void RecordNamedOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
1168 RuleMatcher &Rule) const {
1169 Table << MatchTable::Opcode("GIM_RecordNamedOperand")
1170 << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
1171 << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx)
1172 << MatchTable::Comment("StoreIdx") << MatchTable::ULEB128Value(StoreIdx)
1173 << MatchTable::Comment("Name : " + Name) << MatchTable::LineBreak;
1174 }
1175
1176 //===- RecordRegisterType ------------------------------------------===//
1177
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1178 void RecordRegisterType::emitPredicateOpcodes(MatchTable &Table,
1179 RuleMatcher &Rule) const {
1180 assert(Idx < 0 && "Temp types always have negative indexes!");
1181 Table << MatchTable::Opcode("GIM_RecordRegType") << MatchTable::Comment("MI")
1182 << MatchTable::ULEB128Value(InsnVarID) << MatchTable::Comment("Op")
1183 << MatchTable::ULEB128Value(OpIdx) << MatchTable::Comment("TempTypeIdx")
1184 << MatchTable::IntValue(1, Idx) << MatchTable::LineBreak;
1185 }
1186
1187 //===- ComplexPatternOperandMatcher ---------------------------------------===//
1188
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1189 void ComplexPatternOperandMatcher::emitPredicateOpcodes(
1190 MatchTable &Table, RuleMatcher &Rule) const {
1191 unsigned ID = getAllocatedTemporariesBaseID();
1192 Table << MatchTable::Opcode("GIM_CheckComplexPattern")
1193 << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
1194 << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx)
1195 << MatchTable::Comment("Renderer") << MatchTable::IntValue(2, ID)
1196 << MatchTable::NamedValue(2, ("GICP_" + TheDef.getName()).str())
1197 << MatchTable::LineBreak;
1198 }
1199
getAllocatedTemporariesBaseID() const1200 unsigned ComplexPatternOperandMatcher::getAllocatedTemporariesBaseID() const {
1201 return Operand.getAllocatedTemporariesBaseID();
1202 }
1203
1204 //===- RegisterBankOperandMatcher -----------------------------------------===//
1205
isIdentical(const PredicateMatcher & B) const1206 bool RegisterBankOperandMatcher::isIdentical(const PredicateMatcher &B) const {
1207 return OperandPredicateMatcher::isIdentical(B) &&
1208 RC.getDef() == cast<RegisterBankOperandMatcher>(&B)->RC.getDef();
1209 }
1210
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1211 void RegisterBankOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
1212 RuleMatcher &Rule) const {
1213 Table << MatchTable::Opcode("GIM_CheckRegBankForClass")
1214 << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
1215 << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx)
1216 << MatchTable::Comment("RC")
1217 << MatchTable::NamedValue(2, RC.getQualifiedIdName())
1218 << MatchTable::LineBreak;
1219 }
1220
1221 //===- MBBOperandMatcher --------------------------------------------------===//
1222
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1223 void MBBOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
1224 RuleMatcher &Rule) const {
1225 Table << MatchTable::Opcode("GIM_CheckIsMBB") << MatchTable::Comment("MI")
1226 << MatchTable::ULEB128Value(InsnVarID) << MatchTable::Comment("Op")
1227 << MatchTable::ULEB128Value(OpIdx) << MatchTable::LineBreak;
1228 }
1229
1230 //===- ImmOperandMatcher --------------------------------------------------===//
1231
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1232 void ImmOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
1233 RuleMatcher &Rule) const {
1234 Table << MatchTable::Opcode("GIM_CheckIsImm") << MatchTable::Comment("MI")
1235 << MatchTable::ULEB128Value(InsnVarID) << MatchTable::Comment("Op")
1236 << MatchTable::ULEB128Value(OpIdx) << MatchTable::LineBreak;
1237 }
1238
1239 //===- ConstantIntOperandMatcher ------------------------------------------===//
1240
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1241 void ConstantIntOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
1242 RuleMatcher &Rule) const {
1243 const bool IsInt8 = isInt<8>(Value);
1244 Table << MatchTable::Opcode(IsInt8 ? "GIM_CheckConstantInt8"
1245 : "GIM_CheckConstantInt")
1246 << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
1247 << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx)
1248 << MatchTable::IntValue(IsInt8 ? 1 : 8, Value) << MatchTable::LineBreak;
1249 }
1250
1251 //===- LiteralIntOperandMatcher -------------------------------------------===//
1252
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1253 void LiteralIntOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
1254 RuleMatcher &Rule) const {
1255 Table << MatchTable::Opcode("GIM_CheckLiteralInt")
1256 << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
1257 << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx)
1258 << MatchTable::IntValue(8, Value) << MatchTable::LineBreak;
1259 }
1260
1261 //===- CmpPredicateOperandMatcher -----------------------------------------===//
1262
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1263 void CmpPredicateOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
1264 RuleMatcher &Rule) const {
1265 Table << MatchTable::Opcode("GIM_CheckCmpPredicate")
1266 << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
1267 << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx)
1268 << MatchTable::Comment("Predicate")
1269 << MatchTable::NamedValue(2, "CmpInst", PredName)
1270 << MatchTable::LineBreak;
1271 }
1272
1273 //===- IntrinsicIDOperandMatcher ------------------------------------------===//
1274
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1275 void IntrinsicIDOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
1276 RuleMatcher &Rule) const {
1277 Table << MatchTable::Opcode("GIM_CheckIntrinsicID")
1278 << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
1279 << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx)
1280 << MatchTable::NamedValue(2, "Intrinsic::" + II->EnumName)
1281 << MatchTable::LineBreak;
1282 }
1283
1284 //===- OperandImmPredicateMatcher -----------------------------------------===//
1285
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1286 void OperandImmPredicateMatcher::emitPredicateOpcodes(MatchTable &Table,
1287 RuleMatcher &Rule) const {
1288 Table << MatchTable::Opcode("GIM_CheckImmOperandPredicate")
1289 << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
1290 << MatchTable::Comment("MO") << MatchTable::ULEB128Value(OpIdx)
1291 << MatchTable::Comment("Predicate")
1292 << MatchTable::NamedValue(2, getEnumNameForPredicate(Predicate))
1293 << MatchTable::LineBreak;
1294 }
1295
1296 //===- OperandMatcher -----------------------------------------------------===//
1297
getOperandExpr(unsigned InsnVarID) const1298 std::string OperandMatcher::getOperandExpr(unsigned InsnVarID) const {
1299 return "State.MIs[" + llvm::to_string(InsnVarID) + "]->getOperand(" +
1300 llvm::to_string(OpIdx) + ")";
1301 }
1302
getInsnVarID() const1303 unsigned OperandMatcher::getInsnVarID() const { return Insn.getInsnVarID(); }
1304
getTempTypeIdx(RuleMatcher & Rule)1305 TempTypeIdx OperandMatcher::getTempTypeIdx(RuleMatcher &Rule) {
1306 if (TTIdx >= 0) {
1307 // Temp type index not assigned yet, so assign one and add the necessary
1308 // predicate.
1309 TTIdx = Rule.getNextTempTypeIdx();
1310 assert(TTIdx < 0);
1311 addPredicate<RecordRegisterType>(TTIdx);
1312 return TTIdx;
1313 }
1314 return TTIdx;
1315 }
1316
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule)1317 void OperandMatcher::emitPredicateOpcodes(MatchTable &Table,
1318 RuleMatcher &Rule) {
1319 if (!Optimized) {
1320 std::string Comment;
1321 raw_string_ostream CommentOS(Comment);
1322 CommentOS << "MIs[" << getInsnVarID() << "] ";
1323 if (SymbolicName.empty())
1324 CommentOS << "Operand " << OpIdx;
1325 else
1326 CommentOS << SymbolicName;
1327 Table << MatchTable::Comment(Comment) << MatchTable::LineBreak;
1328 }
1329
1330 emitPredicateListOpcodes(Table, Rule);
1331 }
1332
isHigherPriorityThan(OperandMatcher & B)1333 bool OperandMatcher::isHigherPriorityThan(OperandMatcher &B) {
1334 // Operand matchers involving more predicates have higher priority.
1335 if (predicates_size() > B.predicates_size())
1336 return true;
1337 if (predicates_size() < B.predicates_size())
1338 return false;
1339
1340 // This assumes that predicates are added in a consistent order.
1341 for (auto &&Predicate : zip(predicates(), B.predicates())) {
1342 if (std::get<0>(Predicate)->isHigherPriorityThan(*std::get<1>(Predicate)))
1343 return true;
1344 if (std::get<1>(Predicate)->isHigherPriorityThan(*std::get<0>(Predicate)))
1345 return false;
1346 }
1347
1348 return false;
1349 }
1350
countRendererFns()1351 unsigned OperandMatcher::countRendererFns() {
1352 return std::accumulate(
1353 predicates().begin(), predicates().end(), 0,
1354 [](unsigned A,
1355 const std::unique_ptr<OperandPredicateMatcher> &Predicate) {
1356 return A + Predicate->countRendererFns();
1357 });
1358 }
1359
addTypeCheckPredicate(const TypeSetByHwMode & VTy,bool OperandIsAPointer)1360 Error OperandMatcher::addTypeCheckPredicate(const TypeSetByHwMode &VTy,
1361 bool OperandIsAPointer) {
1362 if (!VTy.isMachineValueType())
1363 return failUnsupported("unsupported typeset");
1364
1365 if (VTy.getMachineValueType() == MVT::iPTR && OperandIsAPointer) {
1366 addPredicate<PointerToAnyOperandMatcher>(0);
1367 return Error::success();
1368 }
1369
1370 auto OpTyOrNone = MVTToLLT(VTy.getMachineValueType().SimpleTy);
1371 if (!OpTyOrNone)
1372 return failUnsupported("unsupported type");
1373
1374 if (OperandIsAPointer)
1375 addPredicate<PointerToAnyOperandMatcher>(OpTyOrNone->get().getSizeInBits());
1376 else if (VTy.isPointer())
1377 addPredicate<LLTOperandMatcher>(
1378 LLT::pointer(VTy.getPtrAddrSpace(), OpTyOrNone->get().getSizeInBits()));
1379 else
1380 addPredicate<LLTOperandMatcher>(*OpTyOrNone);
1381 return Error::success();
1382 }
1383
1384 //===- InstructionOpcodeMatcher -------------------------------------------===//
1385
1386 DenseMap<const CodeGenInstruction *, unsigned>
1387 InstructionOpcodeMatcher::OpcodeValues;
1388
1389 MatchTableRecord
getInstValue(const CodeGenInstruction * I) const1390 InstructionOpcodeMatcher::getInstValue(const CodeGenInstruction *I) const {
1391 const auto VI = OpcodeValues.find(I);
1392 if (VI != OpcodeValues.end())
1393 return MatchTable::NamedValue(2, I->Namespace, I->TheDef->getName(),
1394 VI->second);
1395 return MatchTable::NamedValue(2, I->Namespace, I->TheDef->getName());
1396 }
1397
initOpcodeValuesMap(const CodeGenTarget & Target)1398 void InstructionOpcodeMatcher::initOpcodeValuesMap(
1399 const CodeGenTarget &Target) {
1400 OpcodeValues.clear();
1401
1402 unsigned OpcodeValue = 0;
1403 for (const CodeGenInstruction *I : Target.getInstructionsByEnumValue())
1404 OpcodeValues[I] = OpcodeValue++;
1405 }
1406
getValue() const1407 MatchTableRecord InstructionOpcodeMatcher::getValue() const {
1408 assert(Insts.size() == 1);
1409
1410 const CodeGenInstruction *I = Insts[0];
1411 const auto VI = OpcodeValues.find(I);
1412 if (VI != OpcodeValues.end())
1413 return MatchTable::NamedValue(2, I->Namespace, I->TheDef->getName(),
1414 VI->second);
1415 return MatchTable::NamedValue(2, I->Namespace, I->TheDef->getName());
1416 }
1417
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1418 void InstructionOpcodeMatcher::emitPredicateOpcodes(MatchTable &Table,
1419 RuleMatcher &Rule) const {
1420 StringRef CheckType =
1421 Insts.size() == 1 ? "GIM_CheckOpcode" : "GIM_CheckOpcodeIsEither";
1422 Table << MatchTable::Opcode(CheckType) << MatchTable::Comment("MI")
1423 << MatchTable::ULEB128Value(InsnVarID);
1424
1425 for (const CodeGenInstruction *I : Insts)
1426 Table << getInstValue(I);
1427 Table << MatchTable::LineBreak;
1428 }
1429
isHigherPriorityThan(const InstructionPredicateMatcher & B) const1430 bool InstructionOpcodeMatcher::isHigherPriorityThan(
1431 const InstructionPredicateMatcher &B) const {
1432 if (InstructionPredicateMatcher::isHigherPriorityThan(B))
1433 return true;
1434 if (B.InstructionPredicateMatcher::isHigherPriorityThan(*this))
1435 return false;
1436
1437 // Prioritize opcodes for cosmetic reasons in the generated source. Although
1438 // this is cosmetic at the moment, we may want to drive a similar ordering
1439 // using instruction frequency information to improve compile time.
1440 if (const InstructionOpcodeMatcher *BO =
1441 dyn_cast<InstructionOpcodeMatcher>(&B))
1442 return Insts[0]->TheDef->getName() < BO->Insts[0]->TheDef->getName();
1443
1444 return false;
1445 }
1446
isConstantInstruction() const1447 bool InstructionOpcodeMatcher::isConstantInstruction() const {
1448 return Insts.size() == 1 && Insts[0]->TheDef->getName() == "G_CONSTANT";
1449 }
1450
getOpcode() const1451 StringRef InstructionOpcodeMatcher::getOpcode() const {
1452 return Insts[0]->TheDef->getName();
1453 }
1454
isVariadicNumOperands() const1455 bool InstructionOpcodeMatcher::isVariadicNumOperands() const {
1456 // If one is variadic, they all should be.
1457 return Insts[0]->Operands.isVariadic;
1458 }
1459
getOperandType(unsigned OpIdx) const1460 StringRef InstructionOpcodeMatcher::getOperandType(unsigned OpIdx) const {
1461 // Types expected to be uniform for all alternatives.
1462 return Insts[0]->Operands[OpIdx].OperandType;
1463 }
1464
1465 //===- InstructionNumOperandsMatcher --------------------------------------===//
1466
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1467 void InstructionNumOperandsMatcher::emitPredicateOpcodes(
1468 MatchTable &Table, RuleMatcher &Rule) const {
1469 Table << MatchTable::Opcode("GIM_CheckNumOperands")
1470 << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
1471 << MatchTable::Comment("Expected")
1472 << MatchTable::ULEB128Value(NumOperands) << MatchTable::LineBreak;
1473 }
1474
1475 //===- InstructionImmPredicateMatcher -------------------------------------===//
1476
isIdentical(const PredicateMatcher & B) const1477 bool InstructionImmPredicateMatcher::isIdentical(
1478 const PredicateMatcher &B) const {
1479 return InstructionPredicateMatcher::isIdentical(B) &&
1480 Predicate.getOrigPatFragRecord() ==
1481 cast<InstructionImmPredicateMatcher>(&B)
1482 ->Predicate.getOrigPatFragRecord();
1483 }
1484
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1485 void InstructionImmPredicateMatcher::emitPredicateOpcodes(
1486 MatchTable &Table, RuleMatcher &Rule) const {
1487 Table << MatchTable::Opcode(getMatchOpcodeForImmPredicate(Predicate))
1488 << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
1489 << MatchTable::Comment("Predicate")
1490 << MatchTable::NamedValue(2, getEnumNameForPredicate(Predicate))
1491 << MatchTable::LineBreak;
1492 }
1493
1494 //===- AtomicOrderingMMOPredicateMatcher ----------------------------------===//
1495
isIdentical(const PredicateMatcher & B) const1496 bool AtomicOrderingMMOPredicateMatcher::isIdentical(
1497 const PredicateMatcher &B) const {
1498 if (!InstructionPredicateMatcher::isIdentical(B))
1499 return false;
1500 const auto &R = *cast<AtomicOrderingMMOPredicateMatcher>(&B);
1501 return Order == R.Order && Comparator == R.Comparator;
1502 }
1503
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1504 void AtomicOrderingMMOPredicateMatcher::emitPredicateOpcodes(
1505 MatchTable &Table, RuleMatcher &Rule) const {
1506 StringRef Opcode = "GIM_CheckAtomicOrdering";
1507
1508 if (Comparator == AO_OrStronger)
1509 Opcode = "GIM_CheckAtomicOrderingOrStrongerThan";
1510 if (Comparator == AO_WeakerThan)
1511 Opcode = "GIM_CheckAtomicOrderingWeakerThan";
1512
1513 Table << MatchTable::Opcode(Opcode) << MatchTable::Comment("MI")
1514 << MatchTable::ULEB128Value(InsnVarID) << MatchTable::Comment("Order")
1515 << MatchTable::NamedValue(1,
1516 ("(uint8_t)AtomicOrdering::" + Order).str())
1517 << MatchTable::LineBreak;
1518 }
1519
1520 //===- MemorySizePredicateMatcher -----------------------------------------===//
1521
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1522 void MemorySizePredicateMatcher::emitPredicateOpcodes(MatchTable &Table,
1523 RuleMatcher &Rule) const {
1524 Table << MatchTable::Opcode("GIM_CheckMemorySizeEqualTo")
1525 << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
1526 << MatchTable::Comment("MMO") << MatchTable::ULEB128Value(MMOIdx)
1527 << MatchTable::Comment("Size") << MatchTable::IntValue(4, Size)
1528 << MatchTable::LineBreak;
1529 }
1530
1531 //===- MemoryAddressSpacePredicateMatcher ---------------------------------===//
1532
isIdentical(const PredicateMatcher & B) const1533 bool MemoryAddressSpacePredicateMatcher::isIdentical(
1534 const PredicateMatcher &B) const {
1535 if (!InstructionPredicateMatcher::isIdentical(B))
1536 return false;
1537 auto *Other = cast<MemoryAddressSpacePredicateMatcher>(&B);
1538 return MMOIdx == Other->MMOIdx && AddrSpaces == Other->AddrSpaces;
1539 }
1540
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1541 void MemoryAddressSpacePredicateMatcher::emitPredicateOpcodes(
1542 MatchTable &Table, RuleMatcher &Rule) const {
1543 Table << MatchTable::Opcode("GIM_CheckMemoryAddressSpace")
1544 << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
1545 << MatchTable::Comment("MMO")
1546 << MatchTable::ULEB128Value(MMOIdx)
1547 // Encode number of address spaces to expect.
1548 << MatchTable::Comment("NumAddrSpace")
1549 << MatchTable::ULEB128Value(AddrSpaces.size());
1550 for (unsigned AS : AddrSpaces)
1551 Table << MatchTable::Comment("AddrSpace") << MatchTable::ULEB128Value(AS);
1552
1553 Table << MatchTable::LineBreak;
1554 }
1555
1556 //===- MemoryAlignmentPredicateMatcher ------------------------------------===//
1557
isIdentical(const PredicateMatcher & B) const1558 bool MemoryAlignmentPredicateMatcher::isIdentical(
1559 const PredicateMatcher &B) const {
1560 if (!InstructionPredicateMatcher::isIdentical(B))
1561 return false;
1562 auto *Other = cast<MemoryAlignmentPredicateMatcher>(&B);
1563 return MMOIdx == Other->MMOIdx && MinAlign == Other->MinAlign;
1564 }
1565
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1566 void MemoryAlignmentPredicateMatcher::emitPredicateOpcodes(
1567 MatchTable &Table, RuleMatcher &Rule) const {
1568 Table << MatchTable::Opcode("GIM_CheckMemoryAlignment")
1569 << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
1570 << MatchTable::Comment("MMO") << MatchTable::ULEB128Value(MMOIdx)
1571 << MatchTable::Comment("MinAlign") << MatchTable::ULEB128Value(MinAlign)
1572 << MatchTable::LineBreak;
1573 }
1574
1575 //===- MemoryVsLLTSizePredicateMatcher ------------------------------------===//
1576
isIdentical(const PredicateMatcher & B) const1577 bool MemoryVsLLTSizePredicateMatcher::isIdentical(
1578 const PredicateMatcher &B) const {
1579 return InstructionPredicateMatcher::isIdentical(B) &&
1580 MMOIdx == cast<MemoryVsLLTSizePredicateMatcher>(&B)->MMOIdx &&
1581 Relation == cast<MemoryVsLLTSizePredicateMatcher>(&B)->Relation &&
1582 OpIdx == cast<MemoryVsLLTSizePredicateMatcher>(&B)->OpIdx;
1583 }
1584
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1585 void MemoryVsLLTSizePredicateMatcher::emitPredicateOpcodes(
1586 MatchTable &Table, RuleMatcher &Rule) const {
1587 Table << MatchTable::Opcode(
1588 Relation == EqualTo ? "GIM_CheckMemorySizeEqualToLLT"
1589 : Relation == GreaterThan ? "GIM_CheckMemorySizeGreaterThanLLT"
1590 : "GIM_CheckMemorySizeLessThanLLT")
1591 << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
1592 << MatchTable::Comment("MMO") << MatchTable::ULEB128Value(MMOIdx)
1593 << MatchTable::Comment("OpIdx") << MatchTable::ULEB128Value(OpIdx)
1594 << MatchTable::LineBreak;
1595 }
1596
1597 //===- VectorSplatImmPredicateMatcher -------------------------------------===//
1598
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1599 void VectorSplatImmPredicateMatcher::emitPredicateOpcodes(
1600 MatchTable &Table, RuleMatcher &Rule) const {
1601 if (Kind == AllOnes)
1602 Table << MatchTable::Opcode("GIM_CheckIsBuildVectorAllOnes");
1603 else
1604 Table << MatchTable::Opcode("GIM_CheckIsBuildVectorAllZeros");
1605
1606 Table << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID);
1607 Table << MatchTable::LineBreak;
1608 }
1609
1610 //===- GenericInstructionPredicateMatcher ---------------------------------===//
1611
GenericInstructionPredicateMatcher(unsigned InsnVarID,TreePredicateFn Predicate)1612 GenericInstructionPredicateMatcher::GenericInstructionPredicateMatcher(
1613 unsigned InsnVarID, TreePredicateFn Predicate)
1614 : GenericInstructionPredicateMatcher(InsnVarID,
1615 getEnumNameForPredicate(Predicate)) {}
1616
isIdentical(const PredicateMatcher & B) const1617 bool GenericInstructionPredicateMatcher::isIdentical(
1618 const PredicateMatcher &B) const {
1619 return InstructionPredicateMatcher::isIdentical(B) &&
1620 EnumVal ==
1621 static_cast<const GenericInstructionPredicateMatcher &>(B).EnumVal;
1622 }
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1623 void GenericInstructionPredicateMatcher::emitPredicateOpcodes(
1624 MatchTable &Table, RuleMatcher &Rule) const {
1625 Table << MatchTable::Opcode("GIM_CheckCxxInsnPredicate")
1626 << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
1627 << MatchTable::Comment("FnId") << MatchTable::NamedValue(2, EnumVal)
1628 << MatchTable::LineBreak;
1629 }
1630
1631 //===- MIFlagsInstructionPredicateMatcher ---------------------------------===//
1632
isIdentical(const PredicateMatcher & B) const1633 bool MIFlagsInstructionPredicateMatcher::isIdentical(
1634 const PredicateMatcher &B) const {
1635 if (!InstructionPredicateMatcher::isIdentical(B))
1636 return false;
1637 const auto &Other =
1638 static_cast<const MIFlagsInstructionPredicateMatcher &>(B);
1639 return Flags == Other.Flags && CheckNot == Other.CheckNot;
1640 }
1641
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule) const1642 void MIFlagsInstructionPredicateMatcher::emitPredicateOpcodes(
1643 MatchTable &Table, RuleMatcher &Rule) const {
1644 Table << MatchTable::Opcode(CheckNot ? "GIM_MIFlagsNot" : "GIM_MIFlags")
1645 << MatchTable::Comment("MI") << MatchTable::ULEB128Value(InsnVarID)
1646 << MatchTable::NamedValue(4, join(Flags, " | "))
1647 << MatchTable::LineBreak;
1648 }
1649
1650 //===- InstructionMatcher -------------------------------------------------===//
1651
1652 OperandMatcher &
addOperand(unsigned OpIdx,const std::string & SymbolicName,unsigned AllocatedTemporariesBaseID)1653 InstructionMatcher::addOperand(unsigned OpIdx, const std::string &SymbolicName,
1654 unsigned AllocatedTemporariesBaseID) {
1655 Operands.emplace_back(new OperandMatcher(*this, OpIdx, SymbolicName,
1656 AllocatedTemporariesBaseID));
1657 if (!SymbolicName.empty())
1658 Rule.defineOperand(SymbolicName, *Operands.back());
1659
1660 return *Operands.back();
1661 }
1662
getOperand(unsigned OpIdx)1663 OperandMatcher &InstructionMatcher::getOperand(unsigned OpIdx) {
1664 auto I = llvm::find_if(Operands,
1665 [&OpIdx](const std::unique_ptr<OperandMatcher> &X) {
1666 return X->getOpIdx() == OpIdx;
1667 });
1668 if (I != Operands.end())
1669 return **I;
1670 llvm_unreachable("Failed to lookup operand");
1671 }
1672
addPhysRegInput(Record * Reg,unsigned OpIdx,unsigned TempOpIdx)1673 OperandMatcher &InstructionMatcher::addPhysRegInput(Record *Reg, unsigned OpIdx,
1674 unsigned TempOpIdx) {
1675 assert(SymbolicName.empty());
1676 OperandMatcher *OM = new OperandMatcher(*this, OpIdx, "", TempOpIdx);
1677 Operands.emplace_back(OM);
1678 Rule.definePhysRegOperand(Reg, *OM);
1679 PhysRegInputs.emplace_back(Reg, OpIdx);
1680 return *OM;
1681 }
1682
emitPredicateOpcodes(MatchTable & Table,RuleMatcher & Rule)1683 void InstructionMatcher::emitPredicateOpcodes(MatchTable &Table,
1684 RuleMatcher &Rule) {
1685 if (NumOperandsCheck)
1686 InstructionNumOperandsMatcher(InsnVarID, getNumOperands())
1687 .emitPredicateOpcodes(Table, Rule);
1688
1689 // First emit all instruction level predicates need to be verified before we
1690 // can verify operands.
1691 emitFilteredPredicateListOpcodes(
1692 [](const PredicateMatcher &P) { return !P.dependsOnOperands(); }, Table,
1693 Rule);
1694
1695 // Emit all operand constraints.
1696 for (const auto &Operand : Operands)
1697 Operand->emitPredicateOpcodes(Table, Rule);
1698
1699 // All of the tablegen defined predicates should now be matched. Now emit
1700 // any custom predicates that rely on all generated checks.
1701 emitFilteredPredicateListOpcodes(
1702 [](const PredicateMatcher &P) { return P.dependsOnOperands(); }, Table,
1703 Rule);
1704 }
1705
isHigherPriorityThan(InstructionMatcher & B)1706 bool InstructionMatcher::isHigherPriorityThan(InstructionMatcher &B) {
1707 // Instruction matchers involving more operands have higher priority.
1708 if (Operands.size() > B.Operands.size())
1709 return true;
1710 if (Operands.size() < B.Operands.size())
1711 return false;
1712
1713 for (auto &&P : zip(predicates(), B.predicates())) {
1714 auto L = static_cast<InstructionPredicateMatcher *>(std::get<0>(P).get());
1715 auto R = static_cast<InstructionPredicateMatcher *>(std::get<1>(P).get());
1716 if (L->isHigherPriorityThan(*R))
1717 return true;
1718 if (R->isHigherPriorityThan(*L))
1719 return false;
1720 }
1721
1722 for (auto Operand : zip(Operands, B.Operands)) {
1723 if (std::get<0>(Operand)->isHigherPriorityThan(*std::get<1>(Operand)))
1724 return true;
1725 if (std::get<1>(Operand)->isHigherPriorityThan(*std::get<0>(Operand)))
1726 return false;
1727 }
1728
1729 return false;
1730 }
1731
countRendererFns()1732 unsigned InstructionMatcher::countRendererFns() {
1733 return std::accumulate(
1734 predicates().begin(), predicates().end(), 0,
1735 [](unsigned A,
1736 const std::unique_ptr<PredicateMatcher> &Predicate) {
1737 return A + Predicate->countRendererFns();
1738 }) +
1739 std::accumulate(
1740 Operands.begin(), Operands.end(), 0,
1741 [](unsigned A, const std::unique_ptr<OperandMatcher> &Operand) {
1742 return A + Operand->countRendererFns();
1743 });
1744 }
1745
optimize()1746 void InstructionMatcher::optimize() {
1747 SmallVector<std::unique_ptr<PredicateMatcher>, 8> Stash;
1748 const auto &OpcMatcher = getOpcodeMatcher();
1749
1750 Stash.push_back(predicates_pop_front());
1751 if (Stash.back().get() == &OpcMatcher) {
1752 if (NumOperandsCheck && OpcMatcher.isVariadicNumOperands() &&
1753 getNumOperands() != 0)
1754 Stash.emplace_back(
1755 new InstructionNumOperandsMatcher(InsnVarID, getNumOperands()));
1756 NumOperandsCheck = false;
1757
1758 for (auto &OM : Operands)
1759 for (auto &OP : OM->predicates())
1760 if (isa<IntrinsicIDOperandMatcher>(OP)) {
1761 Stash.push_back(std::move(OP));
1762 OM->eraseNullPredicates();
1763 break;
1764 }
1765 }
1766
1767 if (InsnVarID > 0) {
1768 assert(!Operands.empty() && "Nested instruction is expected to def a vreg");
1769 for (auto &OP : Operands[0]->predicates())
1770 OP.reset();
1771 Operands[0]->eraseNullPredicates();
1772 }
1773 for (auto &OM : Operands) {
1774 for (auto &OP : OM->predicates())
1775 if (isa<LLTOperandMatcher>(OP))
1776 Stash.push_back(std::move(OP));
1777 OM->eraseNullPredicates();
1778 }
1779 while (!Stash.empty())
1780 prependPredicate(Stash.pop_back_val());
1781 }
1782
1783 //===- InstructionOperandMatcher ------------------------------------------===//
1784
emitCaptureOpcodes(MatchTable & Table,RuleMatcher & Rule) const1785 void InstructionOperandMatcher::emitCaptureOpcodes(MatchTable &Table,
1786 RuleMatcher &Rule) const {
1787 const unsigned NewInsnVarID = InsnMatcher->getInsnVarID();
1788 const bool IgnoreCopies = Flags & GISF_IgnoreCopies;
1789 Table << MatchTable::Opcode(IgnoreCopies ? "GIM_RecordInsnIgnoreCopies"
1790 : "GIM_RecordInsn")
1791 << MatchTable::Comment("DefineMI")
1792 << MatchTable::ULEB128Value(NewInsnVarID) << MatchTable::Comment("MI")
1793 << MatchTable::ULEB128Value(getInsnVarID())
1794 << MatchTable::Comment("OpIdx") << MatchTable::ULEB128Value(getOpIdx())
1795 << MatchTable::Comment("MIs[" + llvm::to_string(NewInsnVarID) + "]")
1796 << MatchTable::LineBreak;
1797 }
1798
isHigherPriorityThan(const OperandPredicateMatcher & B) const1799 bool InstructionOperandMatcher::isHigherPriorityThan(
1800 const OperandPredicateMatcher &B) const {
1801 if (OperandPredicateMatcher::isHigherPriorityThan(B))
1802 return true;
1803 if (B.OperandPredicateMatcher::isHigherPriorityThan(*this))
1804 return false;
1805
1806 if (const InstructionOperandMatcher *BP =
1807 dyn_cast<InstructionOperandMatcher>(&B))
1808 if (InsnMatcher->isHigherPriorityThan(*BP->InsnMatcher))
1809 return true;
1810 return false;
1811 }
1812
1813 //===- OperandRenderer ----------------------------------------------------===//
1814
~OperandRenderer()1815 OperandRenderer::~OperandRenderer() {}
1816
1817 //===- CopyRenderer -------------------------------------------------------===//
1818
emitRenderOpcodes(MatchTable & Table,RuleMatcher & Rule) const1819 void CopyRenderer::emitRenderOpcodes(MatchTable &Table,
1820 RuleMatcher &Rule) const {
1821 const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName);
1822 unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
1823 Table << MatchTable::Opcode("GIR_Copy") << MatchTable::Comment("NewInsnID")
1824 << MatchTable::ULEB128Value(NewInsnID)
1825 << MatchTable::Comment("OldInsnID")
1826 << MatchTable::ULEB128Value(OldInsnVarID)
1827 << MatchTable::Comment("OpIdx")
1828 << MatchTable::ULEB128Value(Operand.getOpIdx())
1829 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
1830 }
1831
1832 //===- CopyPhysRegRenderer ------------------------------------------------===//
1833
emitRenderOpcodes(MatchTable & Table,RuleMatcher & Rule) const1834 void CopyPhysRegRenderer::emitRenderOpcodes(MatchTable &Table,
1835 RuleMatcher &Rule) const {
1836 const OperandMatcher &Operand = Rule.getPhysRegOperandMatcher(PhysReg);
1837 unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
1838 Table << MatchTable::Opcode("GIR_Copy") << MatchTable::Comment("NewInsnID")
1839 << MatchTable::ULEB128Value(NewInsnID)
1840 << MatchTable::Comment("OldInsnID")
1841 << MatchTable::ULEB128Value(OldInsnVarID)
1842 << MatchTable::Comment("OpIdx")
1843 << MatchTable::ULEB128Value(Operand.getOpIdx())
1844 << MatchTable::Comment(PhysReg->getName()) << MatchTable::LineBreak;
1845 }
1846
1847 //===- CopyOrAddZeroRegRenderer -------------------------------------------===//
1848
emitRenderOpcodes(MatchTable & Table,RuleMatcher & Rule) const1849 void CopyOrAddZeroRegRenderer::emitRenderOpcodes(MatchTable &Table,
1850 RuleMatcher &Rule) const {
1851 const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName);
1852 unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
1853 Table << MatchTable::Opcode("GIR_CopyOrAddZeroReg")
1854 << MatchTable::Comment("NewInsnID")
1855 << MatchTable::ULEB128Value(NewInsnID)
1856 << MatchTable::Comment("OldInsnID")
1857 << MatchTable::ULEB128Value(OldInsnVarID)
1858 << MatchTable::Comment("OpIdx")
1859 << MatchTable::ULEB128Value(Operand.getOpIdx())
1860 << MatchTable::NamedValue(
1861 2,
1862 (ZeroRegisterDef->getValue("Namespace")
1863 ? ZeroRegisterDef->getValueAsString("Namespace")
1864 : ""),
1865 ZeroRegisterDef->getName())
1866 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
1867 }
1868
1869 //===- CopyConstantAsImmRenderer ------------------------------------------===//
1870
emitRenderOpcodes(MatchTable & Table,RuleMatcher & Rule) const1871 void CopyConstantAsImmRenderer::emitRenderOpcodes(MatchTable &Table,
1872 RuleMatcher &Rule) const {
1873 InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
1874 unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
1875 Table << MatchTable::Opcode(Signed ? "GIR_CopyConstantAsSImm"
1876 : "GIR_CopyConstantAsUImm")
1877 << MatchTable::Comment("NewInsnID")
1878 << MatchTable::ULEB128Value(NewInsnID)
1879 << MatchTable::Comment("OldInsnID")
1880 << MatchTable::ULEB128Value(OldInsnVarID)
1881 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
1882 }
1883
1884 //===- CopyFConstantAsFPImmRenderer ---------------------------------------===//
1885
emitRenderOpcodes(MatchTable & Table,RuleMatcher & Rule) const1886 void CopyFConstantAsFPImmRenderer::emitRenderOpcodes(MatchTable &Table,
1887 RuleMatcher &Rule) const {
1888 InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
1889 unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
1890 Table << MatchTable::Opcode("GIR_CopyFConstantAsFPImm")
1891 << MatchTable::Comment("NewInsnID")
1892 << MatchTable::ULEB128Value(NewInsnID)
1893 << MatchTable::Comment("OldInsnID")
1894 << MatchTable::ULEB128Value(OldInsnVarID)
1895 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
1896 }
1897
1898 //===- CopySubRegRenderer -------------------------------------------------===//
1899
emitRenderOpcodes(MatchTable & Table,RuleMatcher & Rule) const1900 void CopySubRegRenderer::emitRenderOpcodes(MatchTable &Table,
1901 RuleMatcher &Rule) const {
1902 const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName);
1903 unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
1904 Table << MatchTable::Opcode("GIR_CopySubReg")
1905 << MatchTable::Comment("NewInsnID")
1906 << MatchTable::ULEB128Value(NewInsnID)
1907 << MatchTable::Comment("OldInsnID")
1908 << MatchTable::ULEB128Value(OldInsnVarID)
1909 << MatchTable::Comment("OpIdx")
1910 << MatchTable::ULEB128Value(Operand.getOpIdx())
1911 << MatchTable::Comment("SubRegIdx")
1912 << MatchTable::IntValue(2, SubReg->EnumValue)
1913 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
1914 }
1915
1916 //===- AddRegisterRenderer ------------------------------------------------===//
1917
emitRenderOpcodes(MatchTable & Table,RuleMatcher & Rule) const1918 void AddRegisterRenderer::emitRenderOpcodes(MatchTable &Table,
1919 RuleMatcher &Rule) const {
1920 Table << MatchTable::Opcode("GIR_AddRegister")
1921 << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID);
1922 if (RegisterDef->getName() != "zero_reg") {
1923 Table << MatchTable::NamedValue(
1924 2,
1925 (RegisterDef->getValue("Namespace")
1926 ? RegisterDef->getValueAsString("Namespace")
1927 : ""),
1928 RegisterDef->getName());
1929 } else {
1930 Table << MatchTable::NamedValue(2, Target.getRegNamespace(), "NoRegister");
1931 }
1932 Table << MatchTable::Comment("AddRegisterRegFlags");
1933
1934 // TODO: This is encoded as a 64-bit element, but only 16 or 32-bits are
1935 // really needed for a physical register reference. We can pack the
1936 // register and flags in a single field.
1937 if (IsDef)
1938 Table << MatchTable::NamedValue(2, "RegState::Define");
1939 else
1940 Table << MatchTable::IntValue(2, 0);
1941 Table << MatchTable::LineBreak;
1942 }
1943
1944 //===- TempRegRenderer ----------------------------------------------------===//
1945
emitRenderOpcodes(MatchTable & Table,RuleMatcher & Rule) const1946 void TempRegRenderer::emitRenderOpcodes(MatchTable &Table,
1947 RuleMatcher &Rule) const {
1948 const bool NeedsFlags = (SubRegIdx || IsDef);
1949 if (SubRegIdx) {
1950 assert(!IsDef);
1951 Table << MatchTable::Opcode("GIR_AddTempSubRegister");
1952 } else
1953 Table << MatchTable::Opcode(NeedsFlags ? "GIR_AddTempRegister"
1954 : "GIR_AddSimpleTempRegister");
1955
1956 Table << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
1957 << MatchTable::Comment("TempRegID")
1958 << MatchTable::ULEB128Value(TempRegID);
1959
1960 if (!NeedsFlags) {
1961 Table << MatchTable::LineBreak;
1962 return;
1963 }
1964
1965 Table << MatchTable::Comment("TempRegFlags");
1966 if (IsDef) {
1967 SmallString<32> RegFlags;
1968 RegFlags += "RegState::Define";
1969 if (IsDead)
1970 RegFlags += "|RegState::Dead";
1971 Table << MatchTable::NamedValue(2, RegFlags);
1972 } else
1973 Table << MatchTable::IntValue(2, 0);
1974
1975 if (SubRegIdx)
1976 Table << MatchTable::NamedValue(2, SubRegIdx->getQualifiedName());
1977 Table << MatchTable::LineBreak;
1978 }
1979
1980 //===- ImmRenderer --------------------------------------------------------===//
1981
emitAddImm(MatchTable & Table,RuleMatcher & RM,unsigned InsnID,int64_t Imm,StringRef ImmName)1982 void ImmRenderer::emitAddImm(MatchTable &Table, RuleMatcher &RM,
1983 unsigned InsnID, int64_t Imm, StringRef ImmName) {
1984 const bool IsInt8 = isInt<8>(Imm);
1985
1986 Table << MatchTable::Opcode(IsInt8 ? "GIR_AddImm8" : "GIR_AddImm")
1987 << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
1988 << MatchTable::Comment(ImmName)
1989 << MatchTable::IntValue(IsInt8 ? 1 : 8, Imm) << MatchTable::LineBreak;
1990 }
1991
emitRenderOpcodes(MatchTable & Table,RuleMatcher & Rule) const1992 void ImmRenderer::emitRenderOpcodes(MatchTable &Table,
1993 RuleMatcher &Rule) const {
1994 if (CImmLLT) {
1995 assert(Table.isCombiner() &&
1996 "ConstantInt immediate are only for combiners!");
1997 Table << MatchTable::Opcode("GIR_AddCImm") << MatchTable::Comment("InsnID")
1998 << MatchTable::ULEB128Value(InsnID) << MatchTable::Comment("Type")
1999 << *CImmLLT << MatchTable::Comment("Imm")
2000 << MatchTable::IntValue(8, Imm) << MatchTable::LineBreak;
2001 } else
2002 emitAddImm(Table, Rule, InsnID, Imm);
2003 }
2004
2005 //===- SubRegIndexRenderer ------------------------------------------------===//
2006
emitRenderOpcodes(MatchTable & Table,RuleMatcher & Rule) const2007 void SubRegIndexRenderer::emitRenderOpcodes(MatchTable &Table,
2008 RuleMatcher &Rule) const {
2009 ImmRenderer::emitAddImm(Table, Rule, InsnID, SubRegIdx->EnumValue,
2010 "SubRegIndex");
2011 }
2012
2013 //===- RenderComplexPatternOperand ----------------------------------------===//
2014
emitRenderOpcodes(MatchTable & Table,RuleMatcher & Rule) const2015 void RenderComplexPatternOperand::emitRenderOpcodes(MatchTable &Table,
2016 RuleMatcher &Rule) const {
2017 Table << MatchTable::Opcode(
2018 SubOperand ? (SubReg ? "GIR_ComplexSubOperandSubRegRenderer"
2019 : "GIR_ComplexSubOperandRenderer")
2020 : "GIR_ComplexRenderer")
2021 << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
2022 << MatchTable::Comment("RendererID")
2023 << MatchTable::IntValue(2, RendererID);
2024 if (SubOperand)
2025 Table << MatchTable::Comment("SubOperand")
2026 << MatchTable::ULEB128Value(*SubOperand);
2027 if (SubReg)
2028 Table << MatchTable::Comment("SubRegIdx")
2029 << MatchTable::IntValue(2, SubReg->EnumValue);
2030 Table << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2031 }
2032
2033 //===- CustomRenderer -----------------------------------------------------===//
2034
emitRenderOpcodes(MatchTable & Table,RuleMatcher & Rule) const2035 void CustomRenderer::emitRenderOpcodes(MatchTable &Table,
2036 RuleMatcher &Rule) const {
2037 InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
2038 unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
2039 Table << MatchTable::Opcode("GIR_CustomRenderer")
2040 << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
2041 << MatchTable::Comment("OldInsnID")
2042 << MatchTable::ULEB128Value(OldInsnVarID)
2043 << MatchTable::Comment("Renderer")
2044 << MatchTable::NamedValue(
2045 2, "GICR_" + Renderer.getValueAsString("RendererFn").str())
2046 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2047 }
2048
2049 //===- CustomOperandRenderer ----------------------------------------------===//
2050
emitRenderOpcodes(MatchTable & Table,RuleMatcher & Rule) const2051 void CustomOperandRenderer::emitRenderOpcodes(MatchTable &Table,
2052 RuleMatcher &Rule) const {
2053 const OperandMatcher &OpdMatcher = Rule.getOperandMatcher(SymbolicName);
2054 Table << MatchTable::Opcode("GIR_CustomOperandRenderer")
2055 << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
2056 << MatchTable::Comment("OldInsnID")
2057 << MatchTable::ULEB128Value(OpdMatcher.getInsnVarID())
2058 << MatchTable::Comment("OpIdx")
2059 << MatchTable::ULEB128Value(OpdMatcher.getOpIdx())
2060 << MatchTable::Comment("OperandRenderer")
2061 << MatchTable::NamedValue(
2062 2, "GICR_" + Renderer.getValueAsString("RendererFn").str())
2063 << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
2064 }
2065
2066 //===- CustomCXXAction ----------------------------------------------------===//
2067
emitActionOpcodes(MatchTable & Table,RuleMatcher & Rule) const2068 void CustomCXXAction::emitActionOpcodes(MatchTable &Table,
2069 RuleMatcher &Rule) const {
2070 Table << MatchTable::Opcode("GIR_CustomAction")
2071 << MatchTable::NamedValue(2, FnEnumName) << MatchTable::LineBreak;
2072 }
2073
2074 //===- BuildMIAction ------------------------------------------------------===//
2075
canMutate(RuleMatcher & Rule,const InstructionMatcher * Insn) const2076 bool BuildMIAction::canMutate(RuleMatcher &Rule,
2077 const InstructionMatcher *Insn) const {
2078 if (!Insn)
2079 return false;
2080
2081 if (OperandRenderers.size() != Insn->getNumOperands())
2082 return false;
2083
2084 for (const auto &Renderer : enumerate(OperandRenderers)) {
2085 if (const auto *Copy = dyn_cast<CopyRenderer>(&*Renderer.value())) {
2086 const OperandMatcher &OM =
2087 Rule.getOperandMatcher(Copy->getSymbolicName());
2088 if (Insn != &OM.getInstructionMatcher() ||
2089 OM.getOpIdx() != Renderer.index())
2090 return false;
2091 } else
2092 return false;
2093 }
2094
2095 return true;
2096 }
2097
chooseInsnToMutate(RuleMatcher & Rule)2098 void BuildMIAction::chooseInsnToMutate(RuleMatcher &Rule) {
2099 for (auto *MutateCandidate : Rule.mutatable_insns()) {
2100 if (canMutate(Rule, MutateCandidate)) {
2101 // Take the first one we're offered that we're able to mutate.
2102 Rule.reserveInsnMatcherForMutation(MutateCandidate);
2103 Matched = MutateCandidate;
2104 return;
2105 }
2106 }
2107 }
2108
emitActionOpcodes(MatchTable & Table,RuleMatcher & Rule) const2109 void BuildMIAction::emitActionOpcodes(MatchTable &Table,
2110 RuleMatcher &Rule) const {
2111 const auto AddMIFlags = [&]() {
2112 for (const InstructionMatcher *IM : CopiedFlags) {
2113 Table << MatchTable::Opcode("GIR_CopyMIFlags")
2114 << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
2115 << MatchTable::Comment("OldInsnID")
2116 << MatchTable::ULEB128Value(IM->getInsnVarID())
2117 << MatchTable::LineBreak;
2118 }
2119
2120 if (!SetFlags.empty()) {
2121 Table << MatchTable::Opcode("GIR_SetMIFlags")
2122 << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
2123 << MatchTable::NamedValue(4, join(SetFlags, " | "))
2124 << MatchTable::LineBreak;
2125 }
2126
2127 if (!UnsetFlags.empty()) {
2128 Table << MatchTable::Opcode("GIR_UnsetMIFlags")
2129 << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
2130 << MatchTable::NamedValue(4, join(UnsetFlags, " | "))
2131 << MatchTable::LineBreak;
2132 }
2133 };
2134
2135 if (Matched) {
2136 assert(canMutate(Rule, Matched) &&
2137 "Arranged to mutate an insn that isn't mutatable");
2138
2139 unsigned RecycleInsnID = Rule.getInsnVarID(*Matched);
2140 Table << MatchTable::Opcode("GIR_MutateOpcode")
2141 << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
2142 << MatchTable::Comment("RecycleInsnID")
2143 << MatchTable::ULEB128Value(RecycleInsnID)
2144 << MatchTable::Comment("Opcode")
2145 << MatchTable::NamedValue(2, I->Namespace, I->TheDef->getName())
2146 << MatchTable::LineBreak;
2147
2148 if (!I->ImplicitDefs.empty() || !I->ImplicitUses.empty()) {
2149 for (auto *Def : I->ImplicitDefs) {
2150 auto Namespace = Def->getValue("Namespace")
2151 ? Def->getValueAsString("Namespace")
2152 : "";
2153 const bool IsDead = DeadImplicitDefs.contains(Def);
2154 Table << MatchTable::Opcode("GIR_AddImplicitDef")
2155 << MatchTable::Comment("InsnID")
2156 << MatchTable::ULEB128Value(InsnID)
2157 << MatchTable::NamedValue(2, Namespace, Def->getName())
2158 << (IsDead ? MatchTable::NamedValue(2, "RegState", "Dead")
2159 : MatchTable::IntValue(2, 0))
2160 << MatchTable::LineBreak;
2161 }
2162 for (auto *Use : I->ImplicitUses) {
2163 auto Namespace = Use->getValue("Namespace")
2164 ? Use->getValueAsString("Namespace")
2165 : "";
2166 Table << MatchTable::Opcode("GIR_AddImplicitUse")
2167 << MatchTable::Comment("InsnID")
2168 << MatchTable::ULEB128Value(InsnID)
2169 << MatchTable::NamedValue(2, Namespace, Use->getName())
2170 << MatchTable::LineBreak;
2171 }
2172 }
2173
2174 AddMIFlags();
2175
2176 // Mark the mutated instruction as erased.
2177 Rule.tryEraseInsnID(RecycleInsnID);
2178 return;
2179 }
2180
2181 // TODO: Simple permutation looks like it could be almost as common as
2182 // mutation due to commutative operations.
2183
2184 Table << MatchTable::Opcode("GIR_BuildMI") << MatchTable::Comment("InsnID")
2185 << MatchTable::ULEB128Value(InsnID) << MatchTable::Comment("Opcode")
2186 << MatchTable::NamedValue(2, I->Namespace, I->TheDef->getName())
2187 << MatchTable::LineBreak;
2188 for (const auto &Renderer : OperandRenderers)
2189 Renderer->emitRenderOpcodes(Table, Rule);
2190
2191 for (auto [OpIdx, Def] : enumerate(I->ImplicitDefs)) {
2192 auto Namespace =
2193 Def->getValue("Namespace") ? Def->getValueAsString("Namespace") : "";
2194 if (DeadImplicitDefs.contains(Def)) {
2195 Table
2196 << MatchTable::Opcode("GIR_SetImplicitDefDead")
2197 << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
2198 << MatchTable::Comment(
2199 ("OpIdx for " + Namespace + "::" + Def->getName() + "").str())
2200 << MatchTable::ULEB128Value(OpIdx) << MatchTable::LineBreak;
2201 }
2202 }
2203
2204 if (I->mayLoad || I->mayStore) {
2205 // Emit the ID's for all the instructions that are matched by this rule.
2206 // TODO: Limit this to matched instructions that mayLoad/mayStore or have
2207 // some other means of having a memoperand. Also limit this to
2208 // emitted instructions that expect to have a memoperand too. For
2209 // example, (G_SEXT (G_LOAD x)) that results in separate load and
2210 // sign-extend instructions shouldn't put the memoperand on the
2211 // sign-extend since it has no effect there.
2212
2213 std::vector<unsigned> MergeInsnIDs;
2214 for (const auto &IDMatcherPair : Rule.defined_insn_vars())
2215 MergeInsnIDs.push_back(IDMatcherPair.second);
2216 llvm::sort(MergeInsnIDs);
2217
2218 Table << MatchTable::Opcode("GIR_MergeMemOperands")
2219 << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
2220 << MatchTable::Comment("NumInsns")
2221 << MatchTable::IntValue(1, MergeInsnIDs.size())
2222 << MatchTable::Comment("MergeInsnID's");
2223 for (const auto &MergeInsnID : MergeInsnIDs)
2224 Table << MatchTable::ULEB128Value(MergeInsnID);
2225 Table << MatchTable::LineBreak;
2226 }
2227
2228 AddMIFlags();
2229 }
2230
2231 //===- BuildConstantAction ------------------------------------------------===//
2232
emitActionOpcodes(MatchTable & Table,RuleMatcher & Rule) const2233 void BuildConstantAction::emitActionOpcodes(MatchTable &Table,
2234 RuleMatcher &Rule) const {
2235 Table << MatchTable::Opcode("GIR_BuildConstant")
2236 << MatchTable::Comment("TempRegID")
2237 << MatchTable::ULEB128Value(TempRegID) << MatchTable::Comment("Val")
2238 << MatchTable::IntValue(8, Val) << MatchTable::LineBreak;
2239 }
2240
2241 //===- EraseInstAction ----------------------------------------------------===//
2242
emitActionOpcodes(MatchTable & Table,RuleMatcher & Rule,unsigned InsnID)2243 void EraseInstAction::emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule,
2244 unsigned InsnID) {
2245 // Avoid erasing the same inst twice.
2246 if (!Rule.tryEraseInsnID(InsnID))
2247 return;
2248
2249 Table << MatchTable::Opcode("GIR_EraseFromParent")
2250 << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
2251 << MatchTable::LineBreak;
2252 }
2253
emitActionOpcodes(MatchTable & Table,RuleMatcher & Rule) const2254 void EraseInstAction::emitActionOpcodes(MatchTable &Table,
2255 RuleMatcher &Rule) const {
2256 emitActionOpcodes(Table, Rule, InsnID);
2257 }
2258
2259 //===- ReplaceRegAction ---------------------------------------------------===//
2260
emitAdditionalPredicates(MatchTable & Table,RuleMatcher & Rule) const2261 void ReplaceRegAction::emitAdditionalPredicates(MatchTable &Table,
2262 RuleMatcher &Rule) const {
2263 if (TempRegID != (unsigned)-1)
2264 return;
2265
2266 Table << MatchTable::Opcode("GIM_CheckCanReplaceReg")
2267 << MatchTable::Comment("OldInsnID")
2268 << MatchTable::ULEB128Value(OldInsnID)
2269 << MatchTable::Comment("OldOpIdx") << MatchTable::ULEB128Value(OldOpIdx)
2270 << MatchTable::Comment("NewInsnId")
2271 << MatchTable::ULEB128Value(NewInsnId)
2272 << MatchTable::Comment("NewOpIdx") << MatchTable::ULEB128Value(NewOpIdx)
2273 << MatchTable::LineBreak;
2274 }
2275
emitActionOpcodes(MatchTable & Table,RuleMatcher & Rule) const2276 void ReplaceRegAction::emitActionOpcodes(MatchTable &Table,
2277 RuleMatcher &Rule) const {
2278 if (TempRegID != (unsigned)-1) {
2279 Table << MatchTable::Opcode("GIR_ReplaceRegWithTempReg")
2280 << MatchTable::Comment("OldInsnID")
2281 << MatchTable::ULEB128Value(OldInsnID)
2282 << MatchTable::Comment("OldOpIdx")
2283 << MatchTable::ULEB128Value(OldOpIdx)
2284 << MatchTable::Comment("TempRegID")
2285 << MatchTable::ULEB128Value(TempRegID) << MatchTable::LineBreak;
2286 } else {
2287 Table << MatchTable::Opcode("GIR_ReplaceReg")
2288 << MatchTable::Comment("OldInsnID")
2289 << MatchTable::ULEB128Value(OldInsnID)
2290 << MatchTable::Comment("OldOpIdx")
2291 << MatchTable::ULEB128Value(OldOpIdx)
2292 << MatchTable::Comment("NewInsnId")
2293 << MatchTable::ULEB128Value(NewInsnId)
2294 << MatchTable::Comment("NewOpIdx")
2295 << MatchTable::ULEB128Value(NewOpIdx) << MatchTable::LineBreak;
2296 }
2297 }
2298
2299 //===- ConstrainOperandToRegClassAction -----------------------------------===//
2300
emitActionOpcodes(MatchTable & Table,RuleMatcher & Rule) const2301 void ConstrainOperandToRegClassAction::emitActionOpcodes(
2302 MatchTable &Table, RuleMatcher &Rule) const {
2303 Table << MatchTable::Opcode("GIR_ConstrainOperandRC")
2304 << MatchTable::Comment("InsnID") << MatchTable::ULEB128Value(InsnID)
2305 << MatchTable::Comment("Op") << MatchTable::ULEB128Value(OpIdx)
2306 << MatchTable::NamedValue(2, RC.getQualifiedIdName())
2307 << MatchTable::LineBreak;
2308 }
2309
2310 //===- MakeTempRegisterAction ---------------------------------------------===//
2311
emitActionOpcodes(MatchTable & Table,RuleMatcher & Rule) const2312 void MakeTempRegisterAction::emitActionOpcodes(MatchTable &Table,
2313 RuleMatcher &Rule) const {
2314 Table << MatchTable::Opcode("GIR_MakeTempReg")
2315 << MatchTable::Comment("TempRegID")
2316 << MatchTable::ULEB128Value(TempRegID) << MatchTable::Comment("TypeID")
2317 << Ty << MatchTable::LineBreak;
2318 }
2319
2320 } // namespace gi
2321 } // namespace llvm
2322