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