1//===- DAGISelMatcherEmitter.cpp - Matcher Emitter ------------------------===//
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// This file contains code to generate C++ code for a matcher.
10//
11//===----------------------------------------------------------------------===//
12
13#include "Basic/SDNodeProperties.h"
14#include "Common/CodeGenDAGPatterns.h"
15#include "Common/CodeGenInstruction.h"
16#include "Common/CodeGenRegisters.h"
17#include "Common/CodeGenTarget.h"
18#include "DAGISelMatcher.h"
19#include "llvm/ADT/DenseMap.h"
20#include "llvm/ADT/MapVector.h"
21#include "llvm/ADT/StringMap.h"
22#include "llvm/ADT/TinyPtrVector.h"
23#include "llvm/Support/CommandLine.h"
24#include "llvm/Support/Format.h"
25#include "llvm/Support/LEB128.h"
26#include "llvm/Support/SourceMgr.h"
27#include "llvm/TableGen/Error.h"
28#include "llvm/TableGen/Record.h"
29
30using namespace llvm;
31
32enum {
33 IndexWidth = 7,
34 FullIndexWidth = IndexWidth + 4,
35 HistOpcWidth = 40,
36};
37
38static cl::OptionCategory DAGISelCat("Options for -gen-dag-isel");
39
40// To reduce generated source code size.
41static cl::opt<bool> OmitComments("omit-comments",
42 cl::desc("Do not generate comments"),
43 cl::init(Val: false), cl::cat(DAGISelCat));
44
45static cl::opt<bool> InstrumentCoverage(
46 "instrument-coverage",
47 cl::desc("Generates tables to help identify patterns matched"),
48 cl::init(Val: false), cl::cat(DAGISelCat));
49
50namespace {
51class MatcherTableEmitter {
52 const CodeGenDAGPatterns &CGP;
53
54 SmallVector<unsigned, Matcher::HighestKind + 1> OpcodeCounts;
55
56 std::vector<TreePattern *> NodePredicates;
57 std::vector<TreePattern *> NodePredicatesWithOperands;
58
59 // We de-duplicate the predicates by code string, and use this map to track
60 // all the patterns with "identical" predicates.
61 MapVector<std::string, TinyPtrVector<TreePattern *>, StringMap<unsigned>>
62 NodePredicatesByCodeToRun;
63
64 std::vector<std::string> PatternPredicates;
65
66 std::vector<const ComplexPattern *> ComplexPatterns;
67
68 DenseMap<const Record *, unsigned> NodeXFormMap;
69 std::vector<const Record *> NodeXForms;
70
71 std::vector<std::string> VecIncludeStrings;
72 MapVector<std::string, unsigned, StringMap<unsigned>> VecPatterns;
73
74 std::map<ValueTypeByHwMode, unsigned> ValueTypeMap;
75
76 unsigned getPatternIdxFromTable(std::string &&P, std::string &&include_loc) {
77 const auto [It, Inserted] =
78 VecPatterns.try_emplace(Key: std::move(P), Args: VecPatterns.size());
79 if (Inserted) {
80 VecIncludeStrings.push_back(x: std::move(include_loc));
81 return VecIncludeStrings.size() - 1;
82 }
83 return It->second;
84 }
85
86public:
87 MatcherTableEmitter(const Matcher *TheMatcher, const CodeGenDAGPatterns &cgp)
88 : CGP(cgp), OpcodeCounts(Matcher::HighestKind + 1, 0) {
89 // Record the usage of ComplexPattern.
90 MapVector<const ComplexPattern *, unsigned> ComplexPatternUsage;
91 // Record the usage of PatternPredicate.
92 MapVector<StringRef, unsigned> PatternPredicateUsage;
93 // Record the usage of Predicate.
94 MapVector<TreePattern *, unsigned> PredicateUsage;
95
96 // Iterate the whole MatcherTable once and do some statistics.
97 std::function<void(const Matcher *)> Statistic = [&](const Matcher *N) {
98 while (N) {
99 if (auto *SM = dyn_cast<ScopeMatcher>(Val: N))
100 for (unsigned I = 0; I < SM->getNumChildren(); I++)
101 Statistic(SM->getChild(i: I));
102 else if (auto *SOM = dyn_cast<SwitchOpcodeMatcher>(Val: N))
103 for (unsigned I = 0; I < SOM->getNumCases(); I++)
104 Statistic(SOM->getCaseMatcher(i: I));
105 else if (auto *STM = dyn_cast<SwitchTypeMatcher>(Val: N))
106 for (unsigned I = 0; I < STM->getNumCases(); I++)
107 Statistic(STM->getCaseMatcher(i: I));
108 else if (auto *CPM = dyn_cast<CheckComplexPatMatcher>(Val: N))
109 ++ComplexPatternUsage[&CPM->getPattern()];
110 else if (auto *CPPM = dyn_cast<CheckPatternPredicateMatcher>(Val: N))
111 ++PatternPredicateUsage[CPPM->getPredicate()];
112 else if (auto *PM = dyn_cast<CheckPredicateMatcher>(Val: N))
113 ++PredicateUsage[PM->getPredicate().getOrigPatFragRecord()];
114 N = N->getNext();
115 }
116 };
117 Statistic(TheMatcher);
118
119 // Sort ComplexPatterns by usage.
120 std::vector<std::pair<const ComplexPattern *, unsigned>> ComplexPatternList(
121 ComplexPatternUsage.begin(), ComplexPatternUsage.end());
122 stable_sort(Range&: ComplexPatternList, C: [](const auto &A, const auto &B) {
123 return A.second > B.second;
124 });
125 for (const auto &ComplexPattern : ComplexPatternList)
126 ComplexPatterns.push_back(x: ComplexPattern.first);
127
128 // Sort PatternPredicates by usage.
129 std::vector<std::pair<std::string, unsigned>> PatternPredicateList(
130 PatternPredicateUsage.begin(), PatternPredicateUsage.end());
131 stable_sort(Range&: PatternPredicateList, C: [](const auto &A, const auto &B) {
132 return A.second > B.second;
133 });
134 for (const auto &PatternPredicate : PatternPredicateList)
135 PatternPredicates.push_back(x: PatternPredicate.first);
136
137 // Sort Predicates by usage.
138 // Merge predicates with same code.
139 for (const auto &Usage : PredicateUsage) {
140 TreePattern *TP = Usage.first;
141 TreePredicateFn Pred(TP);
142 NodePredicatesByCodeToRun[Pred.getCodeToRunOnSDNode()].push_back(NewVal: TP);
143 }
144
145 std::vector<std::pair<TreePattern *, unsigned>> PredicateList;
146 // Sum the usage.
147 for (auto &Predicate : NodePredicatesByCodeToRun) {
148 TinyPtrVector<TreePattern *> &TPs = Predicate.second;
149 stable_sort(Range&: TPs, C: [](const auto *A, const auto *B) {
150 return A->getRecord()->getName() < B->getRecord()->getName();
151 });
152 unsigned Uses = 0;
153 for (TreePattern *TP : TPs)
154 Uses += PredicateUsage[TP];
155
156 // We only add the first predicate here since they are with the same code.
157 PredicateList.emplace_back(args: TPs[0], args&: Uses);
158 }
159
160 stable_sort(Range&: PredicateList, C: [](const auto &A, const auto &B) {
161 return A.second > B.second;
162 });
163 for (const auto &Predicate : PredicateList) {
164 TreePattern *TP = Predicate.first;
165 if (TreePredicateFn(TP).usesOperands())
166 NodePredicatesWithOperands.push_back(x: TP);
167 else
168 NodePredicates.push_back(x: TP);
169 }
170 }
171
172 unsigned EmitMatcherList(const Matcher *N, const unsigned Indent,
173 unsigned StartIdx, raw_ostream &OS);
174
175 unsigned SizeMatcherList(Matcher *N, raw_ostream &OS);
176
177 void EmitPredicateFunctions(raw_ostream &OS);
178
179 void EmitValueTypeFunction(raw_ostream &OS);
180
181 void EmitHistogram(raw_ostream &OS);
182
183 void EmitPatternMatchTable(raw_ostream &OS);
184
185private:
186 void EmitNodePredicatesFunction(const std::vector<TreePattern *> &Preds,
187 StringRef Decl, raw_ostream &OS);
188
189 unsigned SizeMatcher(Matcher *N, raw_ostream &OS);
190
191 unsigned EmitMatcher(const Matcher *N, const unsigned Indent,
192 unsigned CurrentIdx, raw_ostream &OS);
193
194 unsigned getNodePredicate(TreePredicateFn Pred) {
195 // We use the first predicate.
196 TreePattern *PredPat =
197 NodePredicatesByCodeToRun[Pred.getCodeToRunOnSDNode()][0];
198 return Pred.usesOperands()
199 ? llvm::find(Range&: NodePredicatesWithOperands, Val: PredPat) -
200 NodePredicatesWithOperands.begin()
201 : llvm::find(Range&: NodePredicates, Val: PredPat) - NodePredicates.begin();
202 }
203
204 unsigned getPatternPredicate(StringRef PredName) {
205 return llvm::find(Range&: PatternPredicates, Val: PredName) - PatternPredicates.begin();
206 }
207 unsigned getComplexPat(const ComplexPattern &P) {
208 return llvm::find(Range&: ComplexPatterns, Val: &P) - ComplexPatterns.begin();
209 }
210
211 unsigned getNodeXFormID(const Record *Rec) {
212 unsigned &Entry = NodeXFormMap[Rec];
213 if (Entry == 0) {
214 NodeXForms.push_back(x: Rec);
215 Entry = NodeXForms.size();
216 }
217 return Entry - 1;
218 }
219
220 unsigned getValueTypeID(const ValueTypeByHwMode &VT) {
221 unsigned &Entry = ValueTypeMap[VT];
222 if (Entry == 0) {
223 Entry = ValueTypeMap.size();
224 if (Entry > 256)
225 report_fatal_error(
226 reason: "More ValueType by HwMode than fit in a 8-bit index");
227 }
228
229 return Entry - 1;
230 }
231
232 unsigned emitValueTypeByHwMode(const ValueTypeByHwMode &VTBH,
233 raw_ostream &OS);
234};
235} // end anonymous namespace.
236
237static std::string GetPatFromTreePatternNode(const TreePatternNode &N) {
238 std::string str;
239 raw_string_ostream Stream(str);
240 Stream << N;
241 return str;
242}
243
244static unsigned GetVBRSize(unsigned Val) {
245 if (Val <= 127)
246 return 1;
247
248 unsigned NumBytes = 0;
249 while (Val >= 128) {
250 Val >>= 7;
251 ++NumBytes;
252 }
253 return NumBytes + 1;
254}
255
256/// EmitVBRValue - Emit the specified value as a VBR, returning the number of
257/// bytes emitted.
258static unsigned EmitVBRValue(uint64_t Val, raw_ostream &OS) {
259 if (Val <= 127) {
260 OS << Val << ',';
261 return 1;
262 }
263
264 uint64_t InVal = Val;
265 unsigned NumBytes = 0;
266 while (Val >= 128) {
267 OS << (Val & 127) << "|128,";
268 Val >>= 7;
269 ++NumBytes;
270 }
271 OS << Val;
272 if (!OmitComments)
273 OS << "/*" << InVal << "*/";
274 OS << ',';
275 return NumBytes + 1;
276}
277
278/// Emit the specified signed value as a VBR. To improve compression we encode
279/// positive numbers shifted left by 1 and negative numbers negated and shifted
280/// left by 1 with bit 0 set.
281static unsigned EmitSignedVBRValue(int64_t Val, raw_ostream &OS) {
282 uint8_t Buffer[10];
283 unsigned Len = encodeSLEB128(Value: Val, p: Buffer);
284
285 for (unsigned i = 0; i != Len - 1; ++i)
286 OS << static_cast<unsigned>(Buffer[i] & 127) << "|128,";
287
288 OS << static_cast<unsigned>(Buffer[Len - 1]);
289 if ((Len > 1 || Val < 0) && !OmitComments)
290 OS << "/*" << Val << "*/";
291 OS << ',';
292 return Len;
293}
294
295// This is expensive and slow.
296static std::string getIncludePath(const Record *R) {
297 std::string str;
298 raw_string_ostream Stream(str);
299 auto Locs = R->getLoc();
300 SMLoc L;
301 if (Locs.size() > 1) {
302 // Get where the pattern prototype was instantiated
303 L = Locs[1];
304 } else if (Locs.size() == 1) {
305 L = Locs[0];
306 }
307 unsigned CurBuf = SrcMgr.FindBufferContainingLoc(Loc: L);
308 assert(CurBuf && "Invalid or unspecified location!");
309
310 Stream << SrcMgr.getBufferInfo(i: CurBuf).Buffer->getBufferIdentifier() << ":"
311 << SrcMgr.FindLineNumber(Loc: L, BufferID: CurBuf);
312 return str;
313}
314
315/// This function traverses the matcher tree and sizes all the nodes
316/// that are children of the three kinds of nodes that have them.
317unsigned MatcherTableEmitter::SizeMatcherList(Matcher *N, raw_ostream &OS) {
318 unsigned Size = 0;
319 while (N) {
320 Size += SizeMatcher(N, OS);
321 N = N->getNext();
322 }
323 return Size;
324}
325
326/// This function sizes the children of the three kinds of nodes that
327/// have them. It does so by using special cases for those three
328/// nodes, but sharing the code in EmitMatcher() for the other kinds.
329unsigned MatcherTableEmitter::SizeMatcher(Matcher *N, raw_ostream &OS) {
330 unsigned Idx = 0;
331
332 ++OpcodeCounts[N->getKind()];
333 switch (N->getKind()) {
334 // The Scope matcher has its kind, a series of child size + child,
335 // and a trailing zero.
336 case Matcher::Scope: {
337 ScopeMatcher *SM = cast<ScopeMatcher>(Val: N);
338 assert(SM->getNext() == nullptr && "Scope matcher should not have next");
339 unsigned Size = 1; // Count the kind.
340 for (unsigned i = 0, e = SM->getNumChildren(); i != e; ++i) {
341 const unsigned ChildSize = SizeMatcherList(N: SM->getChild(i), OS);
342 assert(ChildSize != 0 && "Matcher cannot have child of size 0");
343 SM->getChild(i)->setSize(ChildSize);
344 Size += GetVBRSize(Val: ChildSize) + ChildSize; // Count VBR and child size.
345 }
346 ++Size; // Count the zero sentinel.
347 return Size;
348 }
349
350 // SwitchOpcode and SwitchType have their kind, a series of child size +
351 // opcode/type + child, and a trailing zero.
352 case Matcher::SwitchOpcode:
353 case Matcher::SwitchType: {
354 unsigned Size = 1; // Count the kind.
355 unsigned NumCases;
356 if (const SwitchOpcodeMatcher *SOM = dyn_cast<SwitchOpcodeMatcher>(Val: N))
357 NumCases = SOM->getNumCases();
358 else
359 NumCases = cast<SwitchTypeMatcher>(Val: N)->getNumCases();
360 for (unsigned i = 0, e = NumCases; i != e; ++i) {
361 Matcher *Child;
362 if (SwitchOpcodeMatcher *SOM = dyn_cast<SwitchOpcodeMatcher>(Val: N)) {
363 Child = SOM->getCaseMatcher(i);
364 Size += 2; // Count the child's opcode.
365 } else {
366 Child = cast<SwitchTypeMatcher>(Val: N)->getCaseMatcher(i);
367 Size += GetVBRSize(Val: cast<SwitchTypeMatcher>(Val: N)
368 ->getCaseType(i)
369 .SimpleTy); // Count the child's type.
370 }
371 const unsigned ChildSize = SizeMatcherList(N: Child, OS);
372 assert(ChildSize != 0 && "Matcher cannot have child of size 0");
373 Child->setSize(ChildSize);
374 Size += GetVBRSize(Val: ChildSize) + ChildSize; // Count VBR and child size.
375 }
376 ++Size; // Count the zero sentinel.
377 return Size;
378 }
379
380 default:
381 // Employ the matcher emitter to size other matchers.
382 return EmitMatcher(N, Indent: 0, CurrentIdx: Idx, OS);
383 }
384 llvm_unreachable("Unreachable");
385}
386
387static void BeginEmitFunction(raw_ostream &OS, StringRef RetType,
388 StringRef Decl, bool AddOverride) {
389 OS << "#ifdef GET_DAGISEL_DECL\n";
390 OS << RetType << ' ' << Decl;
391 if (AddOverride)
392 OS << " override";
393 OS << ";\n"
394 "#endif\n"
395 "#if defined(GET_DAGISEL_BODY) || DAGISEL_INLINE\n";
396 OS << RetType << " DAGISEL_CLASS_COLONCOLON " << Decl << "\n";
397 if (AddOverride) {
398 OS << "#if DAGISEL_INLINE\n"
399 " override\n"
400 "#endif\n";
401 }
402}
403
404static void EndEmitFunction(raw_ostream &OS) {
405 OS << "#endif // GET_DAGISEL_BODY\n\n";
406}
407
408void MatcherTableEmitter::EmitPatternMatchTable(raw_ostream &OS) {
409
410 if (!isUInt<32>(x: VecPatterns.size()))
411 report_fatal_error(reason: "More patterns defined that can fit into 32-bit Pattern "
412 "Table index encoding");
413
414 assert(VecPatterns.size() == VecIncludeStrings.size() &&
415 "The sizes of Pattern and include vectors should be the same");
416
417 BeginEmitFunction(OS, RetType: "StringRef", Decl: "getPatternForIndex(unsigned Index)",
418 AddOverride: true /*AddOverride*/);
419 OS << "{\n";
420 OS << "static const char *PATTERN_MATCH_TABLE[] = {\n";
421
422 for (const auto &It : VecPatterns) {
423 OS << "\"" << It.first << "\",\n";
424 }
425
426 OS << "\n};";
427 OS << "\nreturn StringRef(PATTERN_MATCH_TABLE[Index]);";
428 OS << "\n}\n";
429 EndEmitFunction(OS);
430
431 BeginEmitFunction(OS, RetType: "StringRef", Decl: "getIncludePathForIndex(unsigned Index)",
432 AddOverride: true /*AddOverride*/);
433 OS << "{\n";
434 OS << "static const char *INCLUDE_PATH_TABLE[] = {\n";
435
436 for (const auto &It : VecIncludeStrings) {
437 OS << "\"" << It << "\",\n";
438 }
439
440 OS << "\n};";
441 OS << "\nreturn StringRef(INCLUDE_PATH_TABLE[Index]);";
442 OS << "\n}\n";
443 EndEmitFunction(OS);
444}
445
446static unsigned emitMVT(MVT VT, raw_ostream &OS) {
447 // Print the MVT directly if it doesn't require a VBR.
448 if (VT.SimpleTy <= 127) {
449 OS << getEnumName(T: VT) << ',';
450 return 1;
451 }
452
453 if (!OmitComments)
454 OS << "/*" << getEnumName(T: VT) << "*/";
455 return EmitVBRValue(Val: VT.SimpleTy, OS);
456}
457
458unsigned
459MatcherTableEmitter::emitValueTypeByHwMode(const ValueTypeByHwMode &VTBH,
460 raw_ostream &OS) {
461 if (!OmitComments)
462 OS << "/*" << VTBH << "*/";
463 OS << getValueTypeID(VT: VTBH) << ',';
464 return 1;
465}
466/// EmitMatcher - Emit bytes for the specified matcher and return
467/// the number of bytes emitted.
468unsigned MatcherTableEmitter::EmitMatcher(const Matcher *N,
469 const unsigned Indent,
470 unsigned CurrentIdx,
471 raw_ostream &OS) {
472 OS.indent(NumSpaces: Indent);
473
474 switch (N->getKind()) {
475 case Matcher::Scope: {
476 const ScopeMatcher *SM = cast<ScopeMatcher>(Val: N);
477 unsigned StartIdx = CurrentIdx;
478
479 OS << "OPC_Scope";
480 if (!OmitComments)
481 OS << " /*" << SM->getNumChildren() << " children */";
482 OS << ", ";
483 ++CurrentIdx;
484
485 // Emit all of the children.
486 for (unsigned i = 0, e = SM->getNumChildren(); i != e; ++i) {
487 if (i != 0) {
488 if (!OmitComments) {
489 OS << "/*" << format_decimal(N: CurrentIdx, Width: IndexWidth) << "*/";
490 OS.indent(NumSpaces: Indent) << "/*Scope*/ ";
491 } else {
492 OS.indent(NumSpaces: Indent);
493 }
494 }
495
496 const Matcher *Child = SM->getChild(i);
497 unsigned ChildSize = Child->getSize();
498 CurrentIdx += EmitVBRValue(Val: ChildSize, OS);
499 if (!OmitComments)
500 OS << " // ->" << CurrentIdx + ChildSize;
501 OS << '\n';
502
503 ChildSize = EmitMatcherList(N: Child, Indent: Indent + 1, StartIdx: CurrentIdx, OS);
504 assert(ChildSize == Child->getSize() &&
505 "Emitted child size does not match calculated size");
506 CurrentIdx += ChildSize;
507 }
508
509 // Emit a zero as a sentinel indicating end of 'Scope'.
510 if (!OmitComments)
511 OS << "/*" << format_decimal(N: CurrentIdx, Width: IndexWidth) << "*/";
512 OS.indent(NumSpaces: Indent) << "0,";
513 if (!OmitComments)
514 OS << " // End of Scope";
515 OS << '\n';
516 return CurrentIdx - StartIdx + 1;
517 }
518
519 case Matcher::RecordNode:
520 OS << "OPC_RecordNode,";
521 if (!OmitComments)
522 OS << " // #" << cast<RecordMatcher>(Val: N)->getResultNo() << " = "
523 << cast<RecordMatcher>(Val: N)->getWhatFor();
524 OS << '\n';
525 return 1;
526
527 case Matcher::RecordChild:
528 OS << "OPC_RecordChild" << cast<RecordChildMatcher>(Val: N)->getChildNo() << ',';
529 if (!OmitComments)
530 OS << " // #" << cast<RecordChildMatcher>(Val: N)->getResultNo() << " = "
531 << cast<RecordChildMatcher>(Val: N)->getWhatFor();
532 OS << '\n';
533 return 1;
534
535 case Matcher::RecordMemRef:
536 OS << "OPC_RecordMemRef,\n";
537 return 1;
538
539 case Matcher::CaptureGlueInput:
540 OS << "OPC_CaptureGlueInput,\n";
541 return 1;
542
543 case Matcher::MoveChild: {
544 const auto *MCM = cast<MoveChildMatcher>(Val: N);
545
546 OS << "OPC_MoveChild";
547 // Handle the specialized forms.
548 if (MCM->getChildNo() >= 8)
549 OS << ", ";
550 OS << MCM->getChildNo() << ",\n";
551 return (MCM->getChildNo() >= 8) ? 2 : 1;
552 }
553
554 case Matcher::MoveSibling: {
555 const auto *MSM = cast<MoveSiblingMatcher>(Val: N);
556
557 OS << "OPC_MoveSibling";
558 // Handle the specialized forms.
559 if (MSM->getSiblingNo() >= 8)
560 OS << ", ";
561 OS << MSM->getSiblingNo() << ",\n";
562 return (MSM->getSiblingNo() >= 8) ? 2 : 1;
563 }
564
565 case Matcher::MoveParent:
566 OS << "OPC_MoveParent,\n";
567 return 1;
568
569 case Matcher::CheckSame:
570 OS << "OPC_CheckSame, " << cast<CheckSameMatcher>(Val: N)->getMatchNumber()
571 << ",\n";
572 return 2;
573
574 case Matcher::CheckChildSame:
575 OS << "OPC_CheckChild" << cast<CheckChildSameMatcher>(Val: N)->getChildNo()
576 << "Same, " << cast<CheckChildSameMatcher>(Val: N)->getMatchNumber() << ",\n";
577 return 2;
578
579 case Matcher::CheckPatternPredicate: {
580 StringRef Pred = cast<CheckPatternPredicateMatcher>(Val: N)->getPredicate();
581 unsigned PredNo = getPatternPredicate(PredName: Pred);
582 if (PredNo > 255)
583 OS << "OPC_CheckPatternPredicateTwoByte, TARGET_VAL(" << PredNo << "),";
584 else if (PredNo < 8)
585 OS << "OPC_CheckPatternPredicate" << PredNo << ',';
586 else
587 OS << "OPC_CheckPatternPredicate, " << PredNo << ',';
588 if (!OmitComments)
589 OS << " // " << Pred;
590 OS << '\n';
591 return 2 + (PredNo > 255) - (PredNo < 8);
592 }
593 case Matcher::CheckPredicate: {
594 TreePredicateFn Pred = cast<CheckPredicateMatcher>(Val: N)->getPredicate();
595 unsigned OperandBytes = 0;
596 unsigned PredNo = getNodePredicate(Pred);
597
598 if (Pred.usesOperands()) {
599 unsigned NumOps = cast<CheckPredicateMatcher>(Val: N)->getNumOperands();
600 OS << "OPC_CheckPredicateWithOperands, " << NumOps << "/*#Ops*/, ";
601 for (unsigned i = 0; i < NumOps; ++i)
602 OS << cast<CheckPredicateMatcher>(Val: N)->getOperandNo(i) << ", ";
603 OperandBytes = 1 + NumOps;
604 } else {
605 if (PredNo < 8) {
606 OperandBytes = -1;
607 OS << "OPC_CheckPredicate" << PredNo << ',';
608 } else {
609 OS << "OPC_CheckPredicate, ";
610 }
611 }
612
613 if (PredNo >= 8 || Pred.usesOperands())
614 OS << PredNo << ',';
615 if (!OmitComments)
616 OS << " // " << Pred.getFnName();
617 OS << '\n';
618 return 2 + OperandBytes;
619 }
620
621 case Matcher::CheckOpcode:
622 OS << "OPC_CheckOpcode, TARGET_VAL("
623 << cast<CheckOpcodeMatcher>(Val: N)->getOpcode().getEnumName() << "),\n";
624 return 3;
625
626 case Matcher::SwitchOpcode:
627 case Matcher::SwitchType: {
628 unsigned StartIdx = CurrentIdx;
629
630 unsigned NumCases;
631 if (const SwitchOpcodeMatcher *SOM = dyn_cast<SwitchOpcodeMatcher>(Val: N)) {
632 OS << "OPC_SwitchOpcode ";
633 NumCases = SOM->getNumCases();
634 } else {
635 OS << "OPC_SwitchType ";
636 NumCases = cast<SwitchTypeMatcher>(Val: N)->getNumCases();
637 }
638
639 if (!OmitComments)
640 OS << "/*" << NumCases << " cases */";
641 OS << ", ";
642 ++CurrentIdx;
643
644 // For each case we emit the size, then the opcode, then the matcher.
645 for (unsigned i = 0, e = NumCases; i != e; ++i) {
646 const Matcher *Child;
647 unsigned IdxSize;
648 if (const SwitchOpcodeMatcher *SOM = dyn_cast<SwitchOpcodeMatcher>(Val: N)) {
649 Child = SOM->getCaseMatcher(i);
650 IdxSize = 2; // size of opcode in table is 2 bytes.
651 } else {
652 Child = cast<SwitchTypeMatcher>(Val: N)->getCaseMatcher(i);
653 IdxSize = GetVBRSize(
654 Val: cast<SwitchTypeMatcher>(Val: N)
655 ->getCaseType(i)
656 .SimpleTy); // size of type in table is sizeof(VBR(MVT)) byte.
657 }
658
659 if (i != 0) {
660 if (!OmitComments)
661 OS << "/*" << format_decimal(N: CurrentIdx, Width: IndexWidth) << "*/";
662 OS.indent(NumSpaces: Indent);
663 if (!OmitComments)
664 OS << (isa<SwitchOpcodeMatcher>(Val: N) ? "/*SwitchOpcode*/ "
665 : "/*SwitchType*/ ");
666 }
667
668 unsigned ChildSize = Child->getSize();
669 CurrentIdx += EmitVBRValue(Val: ChildSize, OS) + IdxSize;
670 OS << ' ';
671 if (const SwitchOpcodeMatcher *SOM = dyn_cast<SwitchOpcodeMatcher>(Val: N))
672 OS << "TARGET_VAL(" << SOM->getCaseOpcode(i).getEnumName() << "),";
673 else
674 emitMVT(VT: cast<SwitchTypeMatcher>(Val: N)->getCaseType(i), OS);
675 if (!OmitComments)
676 OS << " // ->" << CurrentIdx + ChildSize;
677 OS << '\n';
678
679 ChildSize = EmitMatcherList(N: Child, Indent: Indent + 1, StartIdx: CurrentIdx, OS);
680 assert(ChildSize == Child->getSize() &&
681 "Emitted child size does not match calculated size");
682 CurrentIdx += ChildSize;
683 }
684
685 // Emit the final zero to terminate the switch.
686 if (!OmitComments)
687 OS << "/*" << format_decimal(N: CurrentIdx, Width: IndexWidth) << "*/";
688 OS.indent(NumSpaces: Indent) << "0,";
689 if (!OmitComments)
690 OS << (isa<SwitchOpcodeMatcher>(Val: N) ? " // EndSwitchOpcode"
691 : " // EndSwitchType");
692
693 OS << '\n';
694 return CurrentIdx - StartIdx + 1;
695 }
696
697 case Matcher::CheckType: {
698 const ValueTypeByHwMode &VTBH = cast<CheckTypeMatcher>(Val: N)->getType();
699 if (VTBH.isSimple()) {
700 MVT VT = VTBH.getSimple();
701 if (cast<CheckTypeMatcher>(Val: N)->getResNo() == 0) {
702 switch (VT.SimpleTy) {
703 case MVT::i32:
704 case MVT::i64:
705 OS << "OPC_CheckTypeI" << MVT(VT).getSizeInBits() << ",\n";
706 return 1;
707 default:
708 OS << "OPC_CheckType, ";
709 unsigned NumBytes = emitMVT(VT, OS);
710 OS << '\n';
711 return NumBytes + 1;
712 }
713 }
714
715 OS << "OPC_CheckTypeRes, " << cast<CheckTypeMatcher>(Val: N)->getResNo()
716 << ", ";
717 unsigned NumBytes =
718 emitMVT(VT: cast<CheckTypeMatcher>(Val: N)->getType().getSimple(), OS);
719 OS << '\n';
720 return NumBytes + 2;
721 }
722
723 unsigned OpSize = 1;
724 if (cast<CheckTypeMatcher>(Val: N)->getResNo() == 0) {
725 OS << "OPC_CheckTypeByHwMode, ";
726 } else {
727 OS << "OPC_CheckTypeResByHwMode, "
728 << cast<CheckTypeMatcher>(Val: N)->getResNo() << ", ";
729 OpSize += 1;
730 }
731 OpSize += emitValueTypeByHwMode(VTBH, OS);
732 OS << '\n';
733 return OpSize;
734 }
735
736 case Matcher::CheckChildType: {
737 const ValueTypeByHwMode &VTBH = cast<CheckChildTypeMatcher>(Val: N)->getType();
738 if (VTBH.isSimple()) {
739 MVT VT = VTBH.getSimple();
740 switch (VT.SimpleTy) {
741 case MVT::i32:
742 case MVT::i64:
743 OS << "OPC_CheckChild" << cast<CheckChildTypeMatcher>(Val: N)->getChildNo()
744 << "TypeI" << MVT(VT).getSizeInBits() << ",\n";
745 return 1;
746 default:
747 OS << "OPC_CheckChild" << cast<CheckChildTypeMatcher>(Val: N)->getChildNo()
748 << "Type, ";
749 unsigned NumBytes = emitMVT(VT, OS);
750 OS << '\n';
751 return NumBytes + 1;
752 }
753 } else {
754 OS << "OPC_CheckChild" << cast<CheckChildTypeMatcher>(Val: N)->getChildNo()
755 << "TypeByHwMode, ";
756 unsigned NumBytes = emitValueTypeByHwMode(VTBH, OS);
757 OS << '\n';
758 return NumBytes + 1;
759 }
760 }
761
762 case Matcher::CheckInteger: {
763 OS << "OPC_CheckInteger, ";
764 unsigned Bytes =
765 1 + EmitSignedVBRValue(Val: cast<CheckIntegerMatcher>(Val: N)->getValue(), OS);
766 OS << '\n';
767 return Bytes;
768 }
769 case Matcher::CheckChildInteger: {
770 OS << "OPC_CheckChild" << cast<CheckChildIntegerMatcher>(Val: N)->getChildNo()
771 << "Integer, ";
772 unsigned Bytes = 1 + EmitSignedVBRValue(
773 Val: cast<CheckChildIntegerMatcher>(Val: N)->getValue(), OS);
774 OS << '\n';
775 return Bytes;
776 }
777 case Matcher::CheckCondCode:
778 OS << "OPC_CheckCondCode, ISD::"
779 << cast<CheckCondCodeMatcher>(Val: N)->getCondCodeName() << ",\n";
780 return 2;
781
782 case Matcher::CheckChild2CondCode:
783 OS << "OPC_CheckChild2CondCode, ISD::"
784 << cast<CheckChild2CondCodeMatcher>(Val: N)->getCondCodeName() << ",\n";
785 return 2;
786
787 case Matcher::CheckValueType: {
788 OS << "OPC_CheckValueType, ";
789 unsigned NumBytes = emitMVT(VT: cast<CheckValueTypeMatcher>(Val: N)->getVT(), OS);
790 OS << "\n";
791 return NumBytes + 1;
792 }
793
794 case Matcher::CheckComplexPat: {
795 const CheckComplexPatMatcher *CCPM = cast<CheckComplexPatMatcher>(Val: N);
796 const ComplexPattern &Pattern = CCPM->getPattern();
797 unsigned PatternNo = getComplexPat(P: Pattern);
798 if (PatternNo < 8)
799 OS << "OPC_CheckComplexPat" << PatternNo << ", /*#*/"
800 << CCPM->getMatchNumber() << ',';
801 else
802 OS << "OPC_CheckComplexPat, /*CP*/" << PatternNo << ", /*#*/"
803 << CCPM->getMatchNumber() << ',';
804
805 if (!OmitComments) {
806 OS << " // " << Pattern.getSelectFunc();
807 OS << ":$" << CCPM->getName();
808 for (unsigned i = 0, e = Pattern.getNumOperands(); i != e; ++i)
809 OS << " #" << CCPM->getFirstResult() + i;
810
811 if (Pattern.hasProperty(Prop: SDNPHasChain))
812 OS << " + chain result";
813 }
814 OS << '\n';
815 return PatternNo < 8 ? 2 : 3;
816 }
817
818 case Matcher::CheckAndImm: {
819 OS << "OPC_CheckAndImm, ";
820 unsigned Bytes =
821 1 + EmitVBRValue(Val: cast<CheckAndImmMatcher>(Val: N)->getValue(), OS);
822 OS << '\n';
823 return Bytes;
824 }
825
826 case Matcher::CheckOrImm: {
827 OS << "OPC_CheckOrImm, ";
828 unsigned Bytes =
829 1 + EmitVBRValue(Val: cast<CheckOrImmMatcher>(Val: N)->getValue(), OS);
830 OS << '\n';
831 return Bytes;
832 }
833
834 case Matcher::CheckFoldableChainNode:
835 OS << "OPC_CheckFoldableChainNode,\n";
836 return 1;
837
838 case Matcher::CheckImmAllOnesV:
839 OS << "OPC_CheckImmAllOnesV,\n";
840 return 1;
841
842 case Matcher::CheckImmAllZerosV:
843 OS << "OPC_CheckImmAllZerosV,\n";
844 return 1;
845
846 case Matcher::EmitInteger: {
847 const auto *IM = cast<EmitIntegerMatcher>(Val: N);
848 int64_t Val = IM->getValue();
849 const std::string &Str = IM->getString();
850 const ValueTypeByHwMode &VTBH = IM->getVT();
851 unsigned TypeBytes = 0;
852 if (VTBH.isSimple()) {
853 MVT VT = VTBH.getSimple();
854 switch (VT.SimpleTy) {
855 case MVT::i8:
856 case MVT::i16:
857 case MVT::i32:
858 case MVT::i64:
859 OS << "OPC_EmitIntegerI" << VT.getSizeInBits() << ", ";
860 break;
861 default:
862 OS << "OPC_EmitInteger, ";
863 TypeBytes = emitMVT(VT, OS);
864 OS << ' ';
865 break;
866 }
867 } else {
868 OS << "OPC_EmitIntegerByHwMode, ";
869 TypeBytes = emitValueTypeByHwMode(VTBH, OS);
870 OS << ' ';
871 }
872 // If the value is 63 or smaller, use the string directly. Otherwise, use
873 // a VBR.
874 unsigned ValBytes = 1;
875 if (!Str.empty() && Val <= 63)
876 OS << Str << ',';
877 else
878 ValBytes = EmitSignedVBRValue(Val, OS);
879 if (!OmitComments) {
880 OS << " // #" << IM->getResultNo() << " = ";
881 if (!Str.empty())
882 OS << Str;
883 else
884 OS << Val;
885 }
886 OS << '\n';
887 return 1 + TypeBytes + ValBytes;
888 }
889
890 case Matcher::EmitRegister: {
891 const EmitRegisterMatcher *Matcher = cast<EmitRegisterMatcher>(Val: N);
892 const CodeGenRegister *Reg = Matcher->getReg();
893 const ValueTypeByHwMode &VTBH = Matcher->getVT();
894 unsigned OpBytes;
895 if (VTBH.isSimple()) {
896 MVT VT = VTBH.getSimple();
897 // If the enum value of the register is larger than one byte can handle,
898 // use EmitRegister2.
899 if (Reg && Reg->EnumValue > 255) {
900 OS << "OPC_EmitRegister2, ";
901 OpBytes = emitMVT(VT, OS);
902 OS << " TARGET_VAL(" << getQualifiedName(R: Reg->TheDef) << "),\n";
903 return OpBytes + 3;
904 }
905 switch (VT.SimpleTy) {
906 case MVT::i32:
907 case MVT::i64:
908 OpBytes = 1;
909 OS << "OPC_EmitRegisterI" << VT.getSizeInBits() << ", ";
910 break;
911 default:
912 OS << "OPC_EmitRegister, ";
913 OpBytes = emitMVT(VT, OS) + 1;
914 OS << ' ';
915 break;
916 }
917 } else {
918 if (Reg && Reg->EnumValue > 255) {
919 OS << "OPC_EmitRegisterByHwMode2, ";
920 OpBytes = emitValueTypeByHwMode(VTBH, OS);
921 OS << " TARGET_VAL(" << getQualifiedName(R: Reg->TheDef) << "),\n";
922 return OpBytes + 3;
923 }
924
925 OS << "OPC_EmitRegisterByHwMode, ";
926 OpBytes = emitValueTypeByHwMode(VTBH, OS) + 1;
927 OS << ' ';
928 }
929 if (Reg)
930 OS << getQualifiedName(R: Reg->TheDef);
931 else
932 OS << "MCRegister::NoRegister";
933
934 OS << ',';
935 if (!OmitComments)
936 OS << " // #" << Matcher->getResultNo();
937 OS << '\n';
938 return OpBytes + 1;
939 }
940
941 case Matcher::EmitConvertToTarget: {
942 const auto *CTTM = cast<EmitConvertToTargetMatcher>(Val: N);
943 unsigned Slot = CTTM->getSlot();
944 OS << "OPC_EmitConvertToTarget";
945 if (Slot >= 8)
946 OS << ", ";
947 OS << Slot << ',';
948 if (!OmitComments)
949 OS << " // #" << CTTM->getResultNo() << " = ConvertToTarget #" << Slot;
950 OS << '\n';
951 return 1 + (Slot >= 8);
952 }
953
954 case Matcher::EmitMergeInputChains: {
955 const EmitMergeInputChainsMatcher *MN =
956 cast<EmitMergeInputChainsMatcher>(Val: N);
957
958 // Handle the specialized forms OPC_EmitMergeInputChains1_0, 1_1, and 1_2.
959 if (MN->getNumNodes() == 1 && MN->getNode(i: 0) < 3) {
960 OS << "OPC_EmitMergeInputChains1_" << MN->getNode(i: 0) << ",\n";
961 return 1;
962 }
963
964 OS << "OPC_EmitMergeInputChains, " << MN->getNumNodes() << ',';
965 for (unsigned i = 0, e = MN->getNumNodes(); i != e; ++i)
966 OS << ' ' << MN->getNode(i) << ",";
967 OS << '\n';
968 return 2 + MN->getNumNodes();
969 }
970 case Matcher::EmitCopyToReg: {
971 const auto *C2RMatcher = cast<EmitCopyToRegMatcher>(Val: N);
972 int Bytes = 3;
973 const CodeGenRegister *Reg = C2RMatcher->getDestPhysReg();
974 unsigned Slot = C2RMatcher->getSrcSlot();
975 if (Reg->EnumValue > 255) {
976 assert(isUInt<16>(Reg->EnumValue) && "not handled");
977 OS << "OPC_EmitCopyToRegTwoByte, " << Slot << ", "
978 << "TARGET_VAL(" << getQualifiedName(R: Reg->TheDef) << "),";
979 ++Bytes;
980 } else {
981 if (Slot < 8) {
982 OS << "OPC_EmitCopyToReg" << Slot << ", "
983 << getQualifiedName(R: Reg->TheDef) << ",";
984 --Bytes;
985 } else {
986 OS << "OPC_EmitCopyToReg, " << Slot << ", "
987 << getQualifiedName(R: Reg->TheDef) << ",";
988 }
989 }
990 if (!OmitComments)
991 OS << " // = #" << Slot;
992
993 OS << '\n';
994 return Bytes;
995 }
996 case Matcher::EmitNodeXForm: {
997 const EmitNodeXFormMatcher *XF = cast<EmitNodeXFormMatcher>(Val: N);
998 OS << "OPC_EmitNodeXForm, " << getNodeXFormID(Rec: XF->getNodeXForm()) << ", "
999 << XF->getSlot() << ',';
1000 if (!OmitComments)
1001 OS << " // #" << XF->getResultNo() << " = "
1002 << XF->getNodeXForm()->getName() << " #" << XF->getSlot();
1003 OS << '\n';
1004 return 3;
1005 }
1006
1007 case Matcher::EmitNode:
1008 case Matcher::MorphNodeTo: {
1009 auto NumCoveredBytes = 0;
1010 if (InstrumentCoverage) {
1011 if (const MorphNodeToMatcher *SNT = dyn_cast<MorphNodeToMatcher>(Val: N)) {
1012 NumCoveredBytes = 3;
1013 OS << "OPC_Coverage, ";
1014 std::string src =
1015 GetPatFromTreePatternNode(N: SNT->getPattern().getSrcPattern());
1016 std::string dst =
1017 GetPatFromTreePatternNode(N: SNT->getPattern().getDstPattern());
1018 const Record *PatRecord = SNT->getPattern().getSrcRecord();
1019 std::string include_src = getIncludePath(R: PatRecord);
1020 unsigned Offset =
1021 getPatternIdxFromTable(P: src + " -> " + dst, include_loc: std::move(include_src));
1022 OS << "COVERAGE_IDX_VAL(" << Offset << "),\n";
1023 OS.indent(NumSpaces: FullIndexWidth + Indent);
1024 }
1025 }
1026 const EmitNodeMatcherCommon *EN = cast<EmitNodeMatcherCommon>(Val: N);
1027 bool SupportsDeactivationSymbol =
1028 EN->getInstruction().TheDef->getValueAsBit(
1029 FieldName: "supportsDeactivationSymbol");
1030 if (SupportsDeactivationSymbol) {
1031 OS << "OPC_CaptureDeactivationSymbol,\n";
1032 OS.indent(NumSpaces: FullIndexWidth + Indent);
1033 }
1034
1035 bool ByHwMode =
1036 llvm::any_of(Range: EN->getVTList(), P: [](const ValueTypeByHwMode &VT) {
1037 return !VT.isSimple();
1038 });
1039
1040 bool IsEmitNode = isa<EmitNodeMatcher>(Val: EN);
1041 OS << (IsEmitNode ? "OPC_EmitNode" : "OPC_MorphNodeTo");
1042 unsigned NumVTs = EN->getNumVTs();
1043 bool CompressVTs = !ByHwMode && EN->getNumVTs() < 3;
1044 bool CompressNodeInfo = false;
1045 if (CompressVTs) {
1046 OS << NumVTs;
1047 // When NumVTs is zero, only consider compressing the chain flag. Any
1048 // zero result node without chain would be deleted and not eligible for
1049 // isel.
1050 if (NumVTs > 0 && !EN->hasChain() && !EN->hasInGlue() &&
1051 !EN->hasOutGlue() && !EN->hasMemRefs() &&
1052 EN->getNumFixedArityOperands() == -1) {
1053 CompressNodeInfo = true;
1054 OS << "None";
1055 } else if (EN->hasChain() && !EN->hasInGlue() && !EN->hasOutGlue() &&
1056 !EN->hasMemRefs() && EN->getNumFixedArityOperands() == -1) {
1057 CompressNodeInfo = true;
1058 OS << "Chain";
1059 } else if (NumVTs > 0 && !IsEmitNode && !EN->hasChain() &&
1060 EN->hasInGlue() && !EN->hasOutGlue() && !EN->hasMemRefs() &&
1061 EN->getNumFixedArityOperands() == -1) {
1062 CompressNodeInfo = true;
1063 OS << "GlueInput";
1064 } else if (NumVTs > 0 && !IsEmitNode && !EN->hasChain() &&
1065 !EN->hasInGlue() && EN->hasOutGlue() && !EN->hasMemRefs() &&
1066 EN->getNumFixedArityOperands() == -1) {
1067 CompressNodeInfo = true;
1068 OS << "GlueOutput";
1069 }
1070 }
1071
1072 if (ByHwMode)
1073 OS << "ByHwMode";
1074
1075 const CodeGenInstruction &CGI = EN->getInstruction();
1076 OS << ", TARGET_VAL(" << CGI.Namespace << "::" << CGI.TheDef->getName()
1077 << ")";
1078
1079 if (!CompressNodeInfo) {
1080 OS << ", 0";
1081 if (EN->hasChain())
1082 OS << "|OPFL_Chain";
1083 if (EN->hasInGlue())
1084 OS << "|OPFL_GlueInput";
1085 if (EN->hasOutGlue())
1086 OS << "|OPFL_GlueOutput";
1087 if (EN->hasMemRefs())
1088 OS << "|OPFL_MemRefs";
1089 if (EN->getNumFixedArityOperands() != -1)
1090 OS << "|OPFL_Variadic" << EN->getNumFixedArityOperands();
1091 }
1092 OS << ",\n";
1093
1094 OS.indent(NumSpaces: FullIndexWidth + Indent + 4);
1095 if (!CompressVTs) {
1096 OS << EN->getNumVTs();
1097 if (!OmitComments)
1098 OS << "/*#VTs*/";
1099 OS << ",";
1100 }
1101 unsigned NumTypeBytes = 0;
1102 if (ByHwMode) {
1103 for (unsigned i = 0, e = EN->getNumVTs(); i != e; ++i) {
1104 OS << ' ';
1105 const ValueTypeByHwMode &VTBH = EN->getVT(i);
1106 NumTypeBytes += emitValueTypeByHwMode(VTBH, OS);
1107 }
1108 } else {
1109 for (unsigned i = 0, e = EN->getNumVTs(); i != e; ++i) {
1110 OS << ' ';
1111 NumTypeBytes += emitMVT(VT: EN->getVT(i).getSimple(), OS);
1112 }
1113 }
1114
1115 OS << ' ' << EN->getNumOperands();
1116 if (!OmitComments)
1117 OS << "/*#Ops*/";
1118 OS << ',';
1119 unsigned NumOperandBytes = 0;
1120 for (unsigned i = 0, e = EN->getNumOperands(); i != e; ++i) {
1121 OS << ' ';
1122 NumOperandBytes += EmitVBRValue(Val: EN->getOperand(i), OS);
1123 }
1124
1125 if (!OmitComments) {
1126 // Print the result #'s for EmitNode.
1127 if (const EmitNodeMatcher *E = dyn_cast<EmitNodeMatcher>(Val: EN)) {
1128 if (unsigned NumResults = EN->getNumVTs()) {
1129 OS << " // Results =";
1130 unsigned First = E->getFirstResultSlot();
1131 for (unsigned i = 0; i != NumResults; ++i)
1132 OS << " #" << First + i;
1133 }
1134 }
1135 OS << '\n';
1136
1137 if (const MorphNodeToMatcher *SNT = dyn_cast<MorphNodeToMatcher>(Val: N)) {
1138 OS.indent(NumSpaces: FullIndexWidth + Indent)
1139 << "// Src: " << SNT->getPattern().getSrcPattern()
1140 << " - Complexity = " << SNT->getPattern().getPatternComplexity(CGP)
1141 << '\n';
1142 OS.indent(NumSpaces: FullIndexWidth + Indent)
1143 << "// Dst: " << SNT->getPattern().getDstPattern() << '\n';
1144 }
1145 } else {
1146 OS << '\n';
1147 }
1148
1149 return 4 + SupportsDeactivationSymbol + !CompressVTs + !CompressNodeInfo +
1150 NumTypeBytes + NumOperandBytes + NumCoveredBytes;
1151 }
1152 case Matcher::CompleteMatch: {
1153 const CompleteMatchMatcher *CM = cast<CompleteMatchMatcher>(Val: N);
1154 auto NumCoveredBytes = 0;
1155 if (InstrumentCoverage) {
1156 NumCoveredBytes = 3;
1157 OS << "OPC_Coverage, ";
1158 std::string src =
1159 GetPatFromTreePatternNode(N: CM->getPattern().getSrcPattern());
1160 std::string dst =
1161 GetPatFromTreePatternNode(N: CM->getPattern().getDstPattern());
1162 const Record *PatRecord = CM->getPattern().getSrcRecord();
1163 std::string include_src = getIncludePath(R: PatRecord);
1164 unsigned Offset =
1165 getPatternIdxFromTable(P: src + " -> " + dst, include_loc: std::move(include_src));
1166 OS << "COVERAGE_IDX_VAL(" << Offset << "),\n";
1167 OS.indent(NumSpaces: FullIndexWidth + Indent);
1168 }
1169 OS << "OPC_CompleteMatch, " << CM->getNumResults() << ",";
1170 unsigned NumResultBytes = 0;
1171 for (unsigned i = 0, e = CM->getNumResults(); i != e; ++i) {
1172 OS << ' ';
1173 NumResultBytes += EmitVBRValue(Val: CM->getResult(R: i), OS);
1174 }
1175 OS << '\n';
1176 if (!OmitComments) {
1177 OS.indent(NumSpaces: FullIndexWidth + Indent)
1178 << " // Src: " << CM->getPattern().getSrcPattern()
1179 << " - Complexity = " << CM->getPattern().getPatternComplexity(CGP)
1180 << '\n';
1181 OS.indent(NumSpaces: FullIndexWidth + Indent)
1182 << " // Dst: " << CM->getPattern().getDstPattern();
1183 }
1184 OS << '\n';
1185 return 2 + NumResultBytes + NumCoveredBytes;
1186 }
1187 }
1188 llvm_unreachable("Unreachable");
1189}
1190
1191/// This function traverses the matcher tree and emits all the nodes.
1192/// The nodes have already been sized.
1193unsigned MatcherTableEmitter::EmitMatcherList(const Matcher *N,
1194 const unsigned Indent,
1195 unsigned CurrentIdx,
1196 raw_ostream &OS) {
1197 unsigned Size = 0;
1198 while (N) {
1199 if (!OmitComments)
1200 OS << "/*" << format_decimal(N: CurrentIdx, Width: IndexWidth) << "*/";
1201 unsigned MatcherSize = EmitMatcher(N, Indent, CurrentIdx, OS);
1202 Size += MatcherSize;
1203 CurrentIdx += MatcherSize;
1204
1205 // If there are other nodes in this list, iterate to them, otherwise we're
1206 // done.
1207 N = N->getNext();
1208 }
1209 return Size;
1210}
1211
1212void MatcherTableEmitter::EmitNodePredicatesFunction(
1213 const std::vector<TreePattern *> &Preds, StringRef Decl, raw_ostream &OS) {
1214 if (Preds.empty())
1215 return;
1216
1217 BeginEmitFunction(OS, RetType: "bool", Decl, AddOverride: true /*AddOverride*/);
1218 OS << "{\n";
1219 OS << " switch (PredNo) {\n";
1220 OS << " default: llvm_unreachable(\"Invalid predicate in table?\");\n";
1221 for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
1222 // Emit the predicate code corresponding to this pattern.
1223 TreePredicateFn PredFn(Preds[i]);
1224 assert(!PredFn.isAlwaysTrue() && "No code in this predicate");
1225 std::string PredFnCodeStr = PredFn.getCodeToRunOnSDNode();
1226
1227 OS << " case " << i << ": {\n";
1228 for (auto *SimilarPred : NodePredicatesByCodeToRun[PredFnCodeStr])
1229 OS << " // " << TreePredicateFn(SimilarPred).getFnName() << '\n';
1230 OS << PredFnCodeStr << "\n }\n";
1231 }
1232 OS << " }\n";
1233 OS << "}\n";
1234 EndEmitFunction(OS);
1235}
1236
1237void MatcherTableEmitter::EmitPredicateFunctions(raw_ostream &OS) {
1238 // Emit pattern predicates.
1239 if (!PatternPredicates.empty()) {
1240 BeginEmitFunction(OS, RetType: "bool",
1241 Decl: "CheckPatternPredicate(unsigned PredNo) const",
1242 AddOverride: true /*AddOverride*/);
1243 OS << "{\n";
1244 OS << " switch (PredNo) {\n";
1245 OS << " default: llvm_unreachable(\"Invalid predicate in table?\");\n";
1246 for (unsigned i = 0, e = PatternPredicates.size(); i != e; ++i)
1247 OS << " case " << i << ": return " << PatternPredicates[i] << ";\n";
1248 OS << " }\n";
1249 OS << "}\n";
1250 EndEmitFunction(OS);
1251 }
1252
1253 // Emit Node predicates.
1254 EmitNodePredicatesFunction(
1255 Preds: NodePredicates, Decl: "CheckNodePredicate(SDValue Op, unsigned PredNo) const",
1256 OS);
1257 EmitNodePredicatesFunction(
1258 Preds: NodePredicatesWithOperands,
1259 Decl: "CheckNodePredicateWithOperands(SDValue Op, unsigned PredNo, "
1260 "ArrayRef<SDValue> Operands) const",
1261 OS);
1262
1263 // Emit CompletePattern matchers.
1264 // FIXME: This should be const.
1265 if (!ComplexPatterns.empty()) {
1266 BeginEmitFunction(
1267 OS, RetType: "bool",
1268 Decl: "CheckComplexPattern(SDNode *Root, SDNode *Parent,\n"
1269 " SDValue N, unsigned PatternNo,\n"
1270 " SmallVectorImpl<std::pair<SDValue, SDNode *>> &Result)",
1271 AddOverride: true /*AddOverride*/);
1272 OS << "{\n";
1273 OS << " unsigned NextRes = Result.size();\n";
1274 OS << " switch (PatternNo) {\n";
1275 OS << " default: llvm_unreachable(\"Invalid pattern # in table?\");\n";
1276 for (unsigned i = 0, e = ComplexPatterns.size(); i != e; ++i) {
1277 const ComplexPattern &P = *ComplexPatterns[i];
1278 unsigned NumOps = P.getNumOperands();
1279
1280 if (P.hasProperty(Prop: SDNPHasChain))
1281 ++NumOps; // Get the chained node too.
1282
1283 OS << " case " << i << ":\n";
1284 if (InstrumentCoverage)
1285 OS << " {\n";
1286 OS << " Result.resize(NextRes+" << NumOps << ");\n";
1287 if (InstrumentCoverage)
1288 OS << " bool Succeeded = " << P.getSelectFunc();
1289 else
1290 OS << " return " << P.getSelectFunc();
1291
1292 OS << "(";
1293 // If the complex pattern wants the root of the match, pass it in as the
1294 // first argument.
1295 if (P.wantsRoot())
1296 OS << "Root, ";
1297
1298 // If the complex pattern wants the parent of the operand being matched,
1299 // pass it in as the next argument.
1300 if (P.wantsParent())
1301 OS << "Parent, ";
1302
1303 OS << "N";
1304 for (unsigned i = 0; i != NumOps; ++i)
1305 OS << ", Result[NextRes+" << i << "].first";
1306 OS << ");\n";
1307 if (InstrumentCoverage) {
1308 OS << " if (Succeeded)\n";
1309 OS << " dbgs() << \"\\nCOMPLEX_PATTERN: " << P.getSelectFunc()
1310 << "\\n\" ;\n";
1311 OS << " return Succeeded;\n";
1312 OS << " }\n";
1313 }
1314 }
1315 OS << " }\n";
1316 OS << "}\n";
1317 EndEmitFunction(OS);
1318 }
1319
1320 // Emit SDNodeXForm handlers.
1321 // FIXME: This should be const.
1322 if (!NodeXForms.empty()) {
1323 BeginEmitFunction(OS, RetType: "SDValue",
1324 Decl: "RunSDNodeXForm(SDValue V, unsigned XFormNo)",
1325 AddOverride: true /*AddOverride*/);
1326 OS << "{\n";
1327 OS << " switch (XFormNo) {\n";
1328 OS << " default: llvm_unreachable(\"Invalid xform # in table?\");\n";
1329
1330 // FIXME: The node xform could take SDValue's instead of SDNode*'s.
1331 for (unsigned i = 0, e = NodeXForms.size(); i != e; ++i) {
1332 const CodeGenDAGPatterns::NodeXForm &Entry =
1333 CGP.getSDNodeTransform(R: NodeXForms[i]);
1334
1335 const Record *SDNode = Entry.first;
1336 const std::string &Code = Entry.second;
1337
1338 OS << " case " << i << ": { ";
1339 if (!OmitComments)
1340 OS << "// " << NodeXForms[i]->getName();
1341 OS << '\n';
1342
1343 std::string ClassName = CGP.getSDNodeInfo(R: SDNode).getSDClassName().str();
1344 if (ClassName == "SDNode")
1345 OS << " SDNode *N = V.getNode();\n";
1346 else
1347 OS << " " << ClassName << " *N = cast<" << ClassName
1348 << ">(V.getNode());\n";
1349 OS << Code << "\n }\n";
1350 }
1351 OS << " }\n";
1352 OS << "}\n";
1353 EndEmitFunction(OS);
1354 }
1355}
1356
1357void MatcherTableEmitter::EmitValueTypeFunction(raw_ostream &OS) {
1358 if (ValueTypeMap.empty())
1359 return;
1360
1361 BeginEmitFunction(OS, RetType: "MVT", Decl: "getValueTypeForHwMode(unsigned Index) const",
1362 /*AddOverride=*/true);
1363 OS << "{\n";
1364
1365 OS << " switch (Index) {\n";
1366 OS << " default: llvm_unreachable(\"Unexpected index\");\n";
1367
1368 for (const auto &[VTs, Idx] : ValueTypeMap) {
1369 OS << " case " << (Idx - 1) << ":\n";
1370 if (VTs.isSimple()) {
1371 OS << " return " << getEnumName(T: VTs.getSimple()) << ";\n";
1372 } else {
1373 OS << " switch (HwMode) {\n";
1374 if (!VTs.hasDefault())
1375 OS << " default:\n return MVT();\n";
1376 for (const auto [Mode, VT] : VTs) {
1377 if (Mode == DefaultMode)
1378 OS << " default:\n";
1379 else
1380 OS << " case " << Mode << ":\n";
1381 OS << " return " << getEnumName(T: VT) << ";\n";
1382 }
1383
1384 OS << " }\n";
1385 OS << " break;\n";
1386 }
1387 }
1388
1389 OS << " }\n";
1390
1391 OS << "}\n";
1392 EndEmitFunction(OS);
1393}
1394
1395static StringRef getOpcodeString(Matcher::KindTy Kind) {
1396 switch (Kind) {
1397 case Matcher::Scope:
1398 return "OPC_Scope";
1399 case Matcher::RecordNode:
1400 return "OPC_RecordNode";
1401 case Matcher::RecordChild:
1402 return "OPC_RecordChild";
1403 case Matcher::RecordMemRef:
1404 return "OPC_RecordMemRef";
1405 case Matcher::CaptureGlueInput:
1406 return "OPC_CaptureGlueInput";
1407 case Matcher::MoveChild:
1408 return "OPC_MoveChild";
1409 case Matcher::MoveSibling:
1410 return "OPC_MoveSibling";
1411 case Matcher::MoveParent:
1412 return "OPC_MoveParent";
1413 case Matcher::CheckSame:
1414 return "OPC_CheckSame";
1415 case Matcher::CheckChildSame:
1416 return "OPC_CheckChildSame";
1417 case Matcher::CheckPatternPredicate:
1418 return "OPC_CheckPatternPredicate";
1419 case Matcher::CheckPredicate:
1420 return "OPC_CheckPredicate";
1421 case Matcher::CheckOpcode:
1422 return "OPC_CheckOpcode";
1423 case Matcher::SwitchOpcode:
1424 return "OPC_SwitchOpcode";
1425 case Matcher::CheckType:
1426 return "OPC_CheckType";
1427 case Matcher::SwitchType:
1428 return "OPC_SwitchType";
1429 case Matcher::CheckChildType:
1430 return "OPC_CheckChildType";
1431 case Matcher::CheckInteger:
1432 return "OPC_CheckInteger";
1433 case Matcher::CheckChildInteger:
1434 return "OPC_CheckChildInteger";
1435 case Matcher::CheckCondCode:
1436 return "OPC_CheckCondCode";
1437 case Matcher::CheckChild2CondCode:
1438 return "OPC_CheckChild2CondCode";
1439 case Matcher::CheckValueType:
1440 return "OPC_CheckValueType";
1441 case Matcher::CheckComplexPat:
1442 return "OPC_CheckComplexPat";
1443 case Matcher::CheckAndImm:
1444 return "OPC_CheckAndImm";
1445 case Matcher::CheckOrImm:
1446 return "OPC_CheckOrImm";
1447 case Matcher::CheckFoldableChainNode:
1448 return "OPC_CheckFoldableChainNode";
1449 case Matcher::CheckImmAllOnesV:
1450 return "OPC_CheckImmAllOnesV";
1451 case Matcher::CheckImmAllZerosV:
1452 return "OPC_CheckImmAllZerosV";
1453 case Matcher::EmitInteger:
1454 return "OPC_EmitInteger";
1455 case Matcher::EmitRegister:
1456 return "OPC_EmitRegister";
1457 case Matcher::EmitConvertToTarget:
1458 return "OPC_EmitConvertToTarget";
1459 case Matcher::EmitMergeInputChains:
1460 return "OPC_EmitMergeInputChains";
1461 case Matcher::EmitCopyToReg:
1462 return "OPC_EmitCopyToReg";
1463 case Matcher::EmitNode:
1464 return "OPC_EmitNode";
1465 case Matcher::MorphNodeTo:
1466 return "OPC_MorphNodeTo";
1467 case Matcher::EmitNodeXForm:
1468 return "OPC_EmitNodeXForm";
1469 case Matcher::CompleteMatch:
1470 return "OPC_CompleteMatch";
1471 }
1472
1473 llvm_unreachable("Unhandled opcode?");
1474}
1475
1476void MatcherTableEmitter::EmitHistogram(raw_ostream &OS) {
1477 if (OmitComments)
1478 return;
1479
1480 OS << " // Opcode Histogram:\n";
1481 for (unsigned i = 0, e = OpcodeCounts.size(); i != e; ++i) {
1482 OS << " // #"
1483 << left_justify(Str: getOpcodeString(Kind: (Matcher::KindTy)i), Width: HistOpcWidth)
1484 << " = " << OpcodeCounts[i] << '\n';
1485 }
1486 OS << '\n';
1487}
1488
1489void llvm::EmitMatcherTable(Matcher *TheMatcher, const CodeGenDAGPatterns &CGP,
1490 raw_ostream &OS) {
1491 OS << "#if defined(GET_DAGISEL_DECL) && defined(GET_DAGISEL_BODY)\n";
1492 OS << "#error GET_DAGISEL_DECL and GET_DAGISEL_BODY cannot be both defined, ";
1493 OS << "undef both for inline definitions\n";
1494 OS << "#endif\n\n";
1495
1496 // Emit a check for omitted class name.
1497 OS << "#ifdef GET_DAGISEL_BODY\n";
1498 OS << "#define LOCAL_DAGISEL_STRINGIZE(X) LOCAL_DAGISEL_STRINGIZE_(X)\n";
1499 OS << "#define LOCAL_DAGISEL_STRINGIZE_(X) #X\n";
1500 OS << "static_assert(sizeof(LOCAL_DAGISEL_STRINGIZE(GET_DAGISEL_BODY)) > 1,"
1501 "\n";
1502 OS << " \"GET_DAGISEL_BODY is empty: it should be defined with the class "
1503 "name\");\n";
1504 OS << "#undef LOCAL_DAGISEL_STRINGIZE_\n";
1505 OS << "#undef LOCAL_DAGISEL_STRINGIZE\n";
1506 OS << "#endif\n\n";
1507
1508 OS << "#if !defined(GET_DAGISEL_DECL) && !defined(GET_DAGISEL_BODY)\n";
1509 OS << "#define DAGISEL_INLINE 1\n";
1510 OS << "#else\n";
1511 OS << "#define DAGISEL_INLINE 0\n";
1512 OS << "#endif\n\n";
1513
1514 OS << "#if !DAGISEL_INLINE\n";
1515 OS << "#define DAGISEL_CLASS_COLONCOLON GET_DAGISEL_BODY ::\n";
1516 OS << "#else\n";
1517 OS << "#define DAGISEL_CLASS_COLONCOLON\n";
1518 OS << "#endif\n\n";
1519
1520 BeginEmitFunction(OS, RetType: "void", Decl: "SelectCode(SDNode *N)", AddOverride: false /*AddOverride*/);
1521 MatcherTableEmitter MatcherEmitter(TheMatcher, CGP);
1522
1523 // First we size all the children of the three kinds of matchers that have
1524 // them. This is done by sharing the code in EmitMatcher(). but we don't
1525 // want to emit anything, so we turn off comments and use a null stream.
1526 bool SaveOmitComments = OmitComments;
1527 OmitComments = true;
1528 raw_null_ostream NullOS;
1529 unsigned TotalSize = MatcherEmitter.SizeMatcherList(N: TheMatcher, OS&: NullOS);
1530 OmitComments = SaveOmitComments;
1531
1532 // Now that the matchers are sized, we can emit the code for them to the
1533 // final stream.
1534 OS << "{\n";
1535 OS << " // Some target values are emitted as 2 bytes, TARGET_VAL handles\n";
1536 OS << " // this. Coverage indexes are emitted as 4 bytes,\n";
1537 OS << " // COVERAGE_IDX_VAL handles this.\n";
1538 OS << " #define TARGET_VAL(X) X & 255, unsigned(X) >> 8\n";
1539 OS << " #define COVERAGE_IDX_VAL(X) X & 255, (unsigned(X) >> 8) & 255, ";
1540 OS << "(unsigned(X) >> 16) & 255, (unsigned(X) >> 24) & 255\n";
1541 OS << " static const uint8_t MatcherTable[] = {\n";
1542 TotalSize = MatcherEmitter.EmitMatcherList(N: TheMatcher, Indent: 1, CurrentIdx: 0, OS);
1543 OS << " }; // Total Array size is " << TotalSize << " bytes\n\n";
1544
1545 MatcherEmitter.EmitHistogram(OS);
1546
1547 OS << " #undef COVERAGE_IDX_VAL\n";
1548 OS << " #undef TARGET_VAL\n";
1549 OS << " SelectCodeCommon(N, MatcherTable, sizeof(MatcherTable));\n";
1550 OS << "}\n";
1551 EndEmitFunction(OS);
1552
1553 // Next up, emit the function for node and pattern predicates:
1554 MatcherEmitter.EmitPredicateFunctions(OS);
1555
1556 MatcherEmitter.EmitValueTypeFunction(OS);
1557
1558 if (InstrumentCoverage)
1559 MatcherEmitter.EmitPatternMatchTable(OS);
1560
1561 // Clean up the preprocessor macros.
1562 OS << "\n";
1563 OS << "#ifdef DAGISEL_INLINE\n";
1564 OS << "#undef DAGISEL_INLINE\n";
1565 OS << "#endif\n";
1566 OS << "#ifdef DAGISEL_CLASS_COLONCOLON\n";
1567 OS << "#undef DAGISEL_CLASS_COLONCOLON\n";
1568 OS << "#endif\n";
1569 OS << "#ifdef GET_DAGISEL_DECL\n";
1570 OS << "#undef GET_DAGISEL_DECL\n";
1571 OS << "#endif\n";
1572 OS << "#ifdef GET_DAGISEL_BODY\n";
1573 OS << "#undef GET_DAGISEL_BODY\n";
1574 OS << "#endif\n";
1575}
1576