1 //===- DAGISelMatcherEmitter.cpp - Matcher Emitter ------------------------===//
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
7 //===----------------------------------------------------------------------===//
9 // This file contains code to generate C++ code for a matcher.
11 //===----------------------------------------------------------------------===//
13 #include "CodeGenDAGPatterns.h"
14 #include "DAGISelMatcher.h"
15 #include "llvm/ADT/DenseMap.h"
16 #include "llvm/ADT/StringMap.h"
17 #include "llvm/ADT/MapVector.h"
18 #include "llvm/ADT/SmallString.h"
19 #include "llvm/ADT/StringMap.h"
20 #include "llvm/ADT/TinyPtrVector.h"
21 #include "llvm/Support/CommandLine.h"
22 #include "llvm/Support/Format.h"
23 #include "llvm/Support/SourceMgr.h"
24 #include "llvm/TableGen/Error.h"
25 #include "llvm/TableGen/Record.h"
30 FullIndexWidth
= IndexWidth
+ 4,
34 cl::OptionCategory
DAGISelCat("Options for -gen-dag-isel");
36 // To reduce generated source code size.
37 static cl::opt
<bool> OmitComments("omit-comments",
38 cl::desc("Do not generate comments"),
39 cl::init(false), cl::cat(DAGISelCat
));
41 static cl::opt
<bool> InstrumentCoverage(
42 "instrument-coverage",
43 cl::desc("Generates tables to help identify patterns matched"),
44 cl::init(false), cl::cat(DAGISelCat
));
47 class MatcherTableEmitter
{
48 const CodeGenDAGPatterns
&CGP
;
50 DenseMap
<TreePattern
*, unsigned> NodePredicateMap
;
51 std::vector
<TreePredicateFn
> NodePredicates
;
52 std::vector
<TreePredicateFn
> NodePredicatesWithOperands
;
54 // We de-duplicate the predicates by code string, and use this map to track
55 // all the patterns with "identical" predicates.
56 StringMap
<TinyPtrVector
<TreePattern
*>> NodePredicatesByCodeToRun
;
58 StringMap
<unsigned> PatternPredicateMap
;
59 std::vector
<std::string
> PatternPredicates
;
61 DenseMap
<const ComplexPattern
*, unsigned> ComplexPatternMap
;
62 std::vector
<const ComplexPattern
*> ComplexPatterns
;
65 DenseMap
<Record
*, unsigned> NodeXFormMap
;
66 std::vector
<Record
*> NodeXForms
;
68 std::vector
<std::string
> VecIncludeStrings
;
69 MapVector
<std::string
, unsigned, StringMap
<unsigned> > VecPatterns
;
71 unsigned getPatternIdxFromTable(std::string
&&P
, std::string
&&include_loc
) {
72 const auto It
= VecPatterns
.find(P
);
73 if (It
== VecPatterns
.end()) {
74 VecPatterns
.insert(make_pair(std::move(P
), VecPatterns
.size()));
75 VecIncludeStrings
.push_back(std::move(include_loc
));
76 return VecIncludeStrings
.size() - 1;
82 MatcherTableEmitter(const CodeGenDAGPatterns
&cgp
)
85 unsigned EmitMatcherList(const Matcher
*N
, unsigned Indent
,
86 unsigned StartIdx
, raw_ostream
&OS
);
88 void EmitPredicateFunctions(raw_ostream
&OS
);
90 void EmitHistogram(const Matcher
*N
, raw_ostream
&OS
);
92 void EmitPatternMatchTable(raw_ostream
&OS
);
95 void EmitNodePredicatesFunction(const std::vector
<TreePredicateFn
> &Preds
,
96 StringRef Decl
, raw_ostream
&OS
);
98 unsigned EmitMatcher(const Matcher
*N
, unsigned Indent
, unsigned CurrentIdx
,
101 unsigned getNodePredicate(TreePredicateFn Pred
) {
102 TreePattern
*TP
= Pred
.getOrigPatFragRecord();
103 unsigned &Entry
= NodePredicateMap
[TP
];
105 TinyPtrVector
<TreePattern
*> &SameCodePreds
=
106 NodePredicatesByCodeToRun
[Pred
.getCodeToRunOnSDNode()];
107 if (SameCodePreds
.empty()) {
108 // We've never seen a predicate with the same code: allocate an entry.
109 if (Pred
.usesOperands()) {
110 NodePredicatesWithOperands
.push_back(Pred
);
111 Entry
= NodePredicatesWithOperands
.size();
113 NodePredicates
.push_back(Pred
);
114 Entry
= NodePredicates
.size();
117 // We did see an identical predicate: re-use it.
118 Entry
= NodePredicateMap
[SameCodePreds
.front()];
120 assert(TreePredicateFn(SameCodePreds
.front()).usesOperands() ==
121 Pred
.usesOperands() &&
122 "PatFrags with some code must have same usesOperands setting");
124 // In both cases, we've never seen this particular predicate before, so
125 // mark it in the list of predicates sharing the same code.
126 SameCodePreds
.push_back(TP
);
131 unsigned getPatternPredicate(StringRef PredName
) {
132 unsigned &Entry
= PatternPredicateMap
[PredName
];
134 PatternPredicates
.push_back(PredName
.str());
135 Entry
= PatternPredicates
.size();
139 unsigned getComplexPat(const ComplexPattern
&P
) {
140 unsigned &Entry
= ComplexPatternMap
[&P
];
142 ComplexPatterns
.push_back(&P
);
143 Entry
= ComplexPatterns
.size();
148 unsigned getNodeXFormID(Record
*Rec
) {
149 unsigned &Entry
= NodeXFormMap
[Rec
];
151 NodeXForms
.push_back(Rec
);
152 Entry
= NodeXForms
.size();
158 } // end anonymous namespace.
160 static std::string
GetPatFromTreePatternNode(const TreePatternNode
*N
) {
162 raw_string_ostream
Stream(str
);
168 static unsigned GetVBRSize(unsigned Val
) {
169 if (Val
<= 127) return 1;
171 unsigned NumBytes
= 0;
179 /// EmitVBRValue - Emit the specified value as a VBR, returning the number of
181 static uint64_t EmitVBRValue(uint64_t Val
, raw_ostream
&OS
) {
187 uint64_t InVal
= Val
;
188 unsigned NumBytes
= 0;
190 OS
<< (Val
&127) << "|128,";
196 OS
<< "/*" << InVal
<< "*/";
201 // This is expensive and slow.
202 static std::string
getIncludePath(const Record
*R
) {
204 raw_string_ostream
Stream(str
);
205 auto Locs
= R
->getLoc();
207 if (Locs
.size() > 1) {
208 // Get where the pattern prototype was instantiated
210 } else if (Locs
.size() == 1) {
213 unsigned CurBuf
= SrcMgr
.FindBufferContainingLoc(L
);
214 assert(CurBuf
&& "Invalid or unspecified location!");
216 Stream
<< SrcMgr
.getBufferInfo(CurBuf
).Buffer
->getBufferIdentifier() << ":"
217 << SrcMgr
.FindLineNumber(L
, CurBuf
);
222 static void BeginEmitFunction(raw_ostream
&OS
, StringRef RetType
,
223 StringRef Decl
, bool AddOverride
) {
224 OS
<< "#ifdef GET_DAGISEL_DECL\n";
225 OS
<< RetType
<< ' ' << Decl
;
230 "#if defined(GET_DAGISEL_BODY) || DAGISEL_INLINE\n";
231 OS
<< RetType
<< " DAGISEL_CLASS_COLONCOLON " << Decl
<< "\n";
233 OS
<< "#if DAGISEL_INLINE\n"
239 static void EndEmitFunction(raw_ostream
&OS
) {
240 OS
<< "#endif // GET_DAGISEL_BODY\n\n";
243 void MatcherTableEmitter::EmitPatternMatchTable(raw_ostream
&OS
) {
245 assert(isUInt
<16>(VecPatterns
.size()) &&
246 "Using only 16 bits to encode offset into Pattern Table");
247 assert(VecPatterns
.size() == VecIncludeStrings
.size() &&
248 "The sizes of Pattern and include vectors should be the same");
250 BeginEmitFunction(OS
, "StringRef", "getPatternForIndex(unsigned Index)",
251 true/*AddOverride*/);
253 OS
<< "static const char * PATTERN_MATCH_TABLE[] = {\n";
255 for (const auto &It
: VecPatterns
) {
256 OS
<< "\"" << It
.first
<< "\",\n";
260 OS
<< "\nreturn StringRef(PATTERN_MATCH_TABLE[Index]);";
264 BeginEmitFunction(OS
, "StringRef", "getIncludePathForIndex(unsigned Index)",
265 true/*AddOverride*/);
267 OS
<< "static const char * INCLUDE_PATH_TABLE[] = {\n";
269 for (const auto &It
: VecIncludeStrings
) {
270 OS
<< "\"" << It
<< "\",\n";
274 OS
<< "\nreturn StringRef(INCLUDE_PATH_TABLE[Index]);";
279 /// EmitMatcher - Emit bytes for the specified matcher and return
280 /// the number of bytes emitted.
281 unsigned MatcherTableEmitter::
282 EmitMatcher(const Matcher
*N
, unsigned Indent
, unsigned CurrentIdx
,
286 switch (N
->getKind()) {
287 case Matcher::Scope
: {
288 const ScopeMatcher
*SM
= cast
<ScopeMatcher
>(N
);
289 assert(SM
->getNext() == nullptr && "Shouldn't have next after scope");
291 unsigned StartIdx
= CurrentIdx
;
293 // Emit all of the children.
294 for (unsigned i
= 0, e
= SM
->getNumChildren(); i
!= e
; ++i
) {
300 OS
<< "/*" << format_decimal(CurrentIdx
, IndexWidth
) << "*/";
301 OS
.indent(Indent
*2) << "/*Scope*/ ";
306 // We need to encode the child and the offset of the failure code before
307 // emitting either of them. Handle this by buffering the output into a
308 // string while we get the size. Unfortunately, the offset of the
309 // children depends on the VBR size of the child, so for large children we
310 // have to iterate a bit.
311 SmallString
<128> TmpBuf
;
312 unsigned ChildSize
= 0;
313 unsigned VBRSize
= 0;
315 VBRSize
= GetVBRSize(ChildSize
);
318 raw_svector_ostream
OS(TmpBuf
);
319 ChildSize
= EmitMatcherList(SM
->getChild(i
), Indent
+1,
320 CurrentIdx
+VBRSize
, OS
);
321 } while (GetVBRSize(ChildSize
) != VBRSize
);
323 assert(ChildSize
!= 0 && "Should not have a zero-sized child!");
325 CurrentIdx
+= EmitVBRValue(ChildSize
, OS
);
327 OS
<< "/*->" << CurrentIdx
+ChildSize
<< "*/";
330 OS
<< " // " << SM
->getNumChildren() << " children in Scope";
333 OS
<< '\n' << TmpBuf
;
334 CurrentIdx
+= ChildSize
;
337 // Emit a zero as a sentinel indicating end of 'Scope'.
339 OS
<< "/*" << format_decimal(CurrentIdx
, IndexWidth
) << "*/";
340 OS
.indent(Indent
*2) << "0, ";
342 OS
<< "/*End of Scope*/";
344 return CurrentIdx
- StartIdx
+ 1;
347 case Matcher::RecordNode
:
348 OS
<< "OPC_RecordNode,";
351 << cast
<RecordMatcher
>(N
)->getResultNo() << " = "
352 << cast
<RecordMatcher
>(N
)->getWhatFor();
356 case Matcher::RecordChild
:
357 OS
<< "OPC_RecordChild" << cast
<RecordChildMatcher
>(N
)->getChildNo()
361 << cast
<RecordChildMatcher
>(N
)->getResultNo() << " = "
362 << cast
<RecordChildMatcher
>(N
)->getWhatFor();
366 case Matcher::RecordMemRef
:
367 OS
<< "OPC_RecordMemRef,\n";
370 case Matcher::CaptureGlueInput
:
371 OS
<< "OPC_CaptureGlueInput,\n";
374 case Matcher::MoveChild
: {
375 const auto *MCM
= cast
<MoveChildMatcher
>(N
);
377 OS
<< "OPC_MoveChild";
378 // Handle the specialized forms.
379 if (MCM
->getChildNo() >= 8)
381 OS
<< MCM
->getChildNo() << ",\n";
382 return (MCM
->getChildNo() >= 8) ? 2 : 1;
385 case Matcher::MoveParent
:
386 OS
<< "OPC_MoveParent,\n";
389 case Matcher::CheckSame
:
390 OS
<< "OPC_CheckSame, "
391 << cast
<CheckSameMatcher
>(N
)->getMatchNumber() << ",\n";
394 case Matcher::CheckChildSame
:
395 OS
<< "OPC_CheckChild"
396 << cast
<CheckChildSameMatcher
>(N
)->getChildNo() << "Same, "
397 << cast
<CheckChildSameMatcher
>(N
)->getMatchNumber() << ",\n";
400 case Matcher::CheckPatternPredicate
: {
401 StringRef Pred
=cast
<CheckPatternPredicateMatcher
>(N
)->getPredicate();
402 OS
<< "OPC_CheckPatternPredicate, " << getPatternPredicate(Pred
) << ',';
404 OS
<< " // " << Pred
;
408 case Matcher::CheckPredicate
: {
409 TreePredicateFn Pred
= cast
<CheckPredicateMatcher
>(N
)->getPredicate();
410 unsigned OperandBytes
= 0;
412 if (Pred
.usesOperands()) {
413 unsigned NumOps
= cast
<CheckPredicateMatcher
>(N
)->getNumOperands();
414 OS
<< "OPC_CheckPredicateWithOperands, " << NumOps
<< "/*#Ops*/, ";
415 for (unsigned i
= 0; i
< NumOps
; ++i
)
416 OS
<< cast
<CheckPredicateMatcher
>(N
)->getOperandNo(i
) << ", ";
417 OperandBytes
= 1 + NumOps
;
419 OS
<< "OPC_CheckPredicate, ";
422 OS
<< getNodePredicate(Pred
) << ',';
424 OS
<< " // " << Pred
.getFnName();
426 return 2 + OperandBytes
;
429 case Matcher::CheckOpcode
:
430 OS
<< "OPC_CheckOpcode, TARGET_VAL("
431 << cast
<CheckOpcodeMatcher
>(N
)->getOpcode().getEnumName() << "),\n";
434 case Matcher::SwitchOpcode
:
435 case Matcher::SwitchType
: {
436 unsigned StartIdx
= CurrentIdx
;
439 if (const SwitchOpcodeMatcher
*SOM
= dyn_cast
<SwitchOpcodeMatcher
>(N
)) {
440 OS
<< "OPC_SwitchOpcode ";
441 NumCases
= SOM
->getNumCases();
443 OS
<< "OPC_SwitchType ";
444 NumCases
= cast
<SwitchTypeMatcher
>(N
)->getNumCases();
448 OS
<< "/*" << NumCases
<< " cases */";
452 // For each case we emit the size, then the opcode, then the matcher.
453 for (unsigned i
= 0, e
= NumCases
; i
!= e
; ++i
) {
454 const Matcher
*Child
;
456 if (const SwitchOpcodeMatcher
*SOM
= dyn_cast
<SwitchOpcodeMatcher
>(N
)) {
457 Child
= SOM
->getCaseMatcher(i
);
458 IdxSize
= 2; // size of opcode in table is 2 bytes.
460 Child
= cast
<SwitchTypeMatcher
>(N
)->getCaseMatcher(i
);
461 IdxSize
= 1; // size of type in table is 1 byte.
464 // We need to encode the opcode and the offset of the case code before
465 // emitting the case code. Handle this by buffering the output into a
466 // string while we get the size. Unfortunately, the offset of the
467 // children depends on the VBR size of the child, so for large children we
468 // have to iterate a bit.
469 SmallString
<128> TmpBuf
;
470 unsigned ChildSize
= 0;
471 unsigned VBRSize
= 0;
473 VBRSize
= GetVBRSize(ChildSize
);
476 raw_svector_ostream
OS(TmpBuf
);
477 ChildSize
= EmitMatcherList(Child
, Indent
+1, CurrentIdx
+VBRSize
+IdxSize
,
479 } while (GetVBRSize(ChildSize
) != VBRSize
);
481 assert(ChildSize
!= 0 && "Should not have a zero-sized child!");
485 OS
<< "/*" << format_decimal(CurrentIdx
, IndexWidth
) << "*/";
488 OS
<< (isa
<SwitchOpcodeMatcher
>(N
) ?
489 "/*SwitchOpcode*/ " : "/*SwitchType*/ ");
493 CurrentIdx
+= EmitVBRValue(ChildSize
, OS
);
495 if (const SwitchOpcodeMatcher
*SOM
= dyn_cast
<SwitchOpcodeMatcher
>(N
))
496 OS
<< "TARGET_VAL(" << SOM
->getCaseOpcode(i
).getEnumName() << "),";
498 OS
<< getEnumName(cast
<SwitchTypeMatcher
>(N
)->getCaseType(i
)) << ',';
500 CurrentIdx
+= IdxSize
;
503 OS
<< "// ->" << CurrentIdx
+ChildSize
;
506 CurrentIdx
+= ChildSize
;
509 // Emit the final zero to terminate the switch.
511 OS
<< "/*" << format_decimal(CurrentIdx
, IndexWidth
) << "*/";
512 OS
.indent(Indent
*2) << "0,";
514 OS
<< (isa
<SwitchOpcodeMatcher
>(N
) ?
515 " // EndSwitchOpcode" : " // EndSwitchType");
519 return CurrentIdx
-StartIdx
;
522 case Matcher::CheckType
:
523 if (cast
<CheckTypeMatcher
>(N
)->getResNo() == 0) {
524 OS
<< "OPC_CheckType, "
525 << getEnumName(cast
<CheckTypeMatcher
>(N
)->getType()) << ",\n";
528 OS
<< "OPC_CheckTypeRes, " << cast
<CheckTypeMatcher
>(N
)->getResNo()
529 << ", " << getEnumName(cast
<CheckTypeMatcher
>(N
)->getType()) << ",\n";
532 case Matcher::CheckChildType
:
533 OS
<< "OPC_CheckChild"
534 << cast
<CheckChildTypeMatcher
>(N
)->getChildNo() << "Type, "
535 << getEnumName(cast
<CheckChildTypeMatcher
>(N
)->getType()) << ",\n";
538 case Matcher::CheckInteger
: {
539 OS
<< "OPC_CheckInteger, ";
540 unsigned Bytes
=1+EmitVBRValue(cast
<CheckIntegerMatcher
>(N
)->getValue(), OS
);
544 case Matcher::CheckChildInteger
: {
545 OS
<< "OPC_CheckChild" << cast
<CheckChildIntegerMatcher
>(N
)->getChildNo()
547 unsigned Bytes
=1+EmitVBRValue(cast
<CheckChildIntegerMatcher
>(N
)->getValue(),
552 case Matcher::CheckCondCode
:
553 OS
<< "OPC_CheckCondCode, ISD::"
554 << cast
<CheckCondCodeMatcher
>(N
)->getCondCodeName() << ",\n";
557 case Matcher::CheckChild2CondCode
:
558 OS
<< "OPC_CheckChild2CondCode, ISD::"
559 << cast
<CheckChild2CondCodeMatcher
>(N
)->getCondCodeName() << ",\n";
562 case Matcher::CheckValueType
:
563 OS
<< "OPC_CheckValueType, MVT::"
564 << cast
<CheckValueTypeMatcher
>(N
)->getTypeName() << ",\n";
567 case Matcher::CheckComplexPat
: {
568 const CheckComplexPatMatcher
*CCPM
= cast
<CheckComplexPatMatcher
>(N
);
569 const ComplexPattern
&Pattern
= CCPM
->getPattern();
570 OS
<< "OPC_CheckComplexPat, /*CP*/" << getComplexPat(Pattern
) << ", /*#*/"
571 << CCPM
->getMatchNumber() << ',';
574 OS
<< " // " << Pattern
.getSelectFunc();
575 OS
<< ":$" << CCPM
->getName();
576 for (unsigned i
= 0, e
= Pattern
.getNumOperands(); i
!= e
; ++i
)
577 OS
<< " #" << CCPM
->getFirstResult()+i
;
579 if (Pattern
.hasProperty(SDNPHasChain
))
580 OS
<< " + chain result";
586 case Matcher::CheckAndImm
: {
587 OS
<< "OPC_CheckAndImm, ";
588 unsigned Bytes
=1+EmitVBRValue(cast
<CheckAndImmMatcher
>(N
)->getValue(), OS
);
593 case Matcher::CheckOrImm
: {
594 OS
<< "OPC_CheckOrImm, ";
595 unsigned Bytes
= 1+EmitVBRValue(cast
<CheckOrImmMatcher
>(N
)->getValue(), OS
);
600 case Matcher::CheckFoldableChainNode
:
601 OS
<< "OPC_CheckFoldableChainNode,\n";
604 case Matcher::CheckImmAllOnesV
:
605 OS
<< "OPC_CheckImmAllOnesV,\n";
608 case Matcher::CheckImmAllZerosV
:
609 OS
<< "OPC_CheckImmAllZerosV,\n";
612 case Matcher::EmitInteger
: {
613 int64_t Val
= cast
<EmitIntegerMatcher
>(N
)->getValue();
614 OS
<< "OPC_EmitInteger, "
615 << getEnumName(cast
<EmitIntegerMatcher
>(N
)->getVT()) << ", ";
616 unsigned Bytes
= 2+EmitVBRValue(Val
, OS
);
620 case Matcher::EmitStringInteger
: {
621 const std::string
&Val
= cast
<EmitStringIntegerMatcher
>(N
)->getValue();
622 // These should always fit into one byte.
623 OS
<< "OPC_EmitInteger, "
624 << getEnumName(cast
<EmitStringIntegerMatcher
>(N
)->getVT()) << ", "
629 case Matcher::EmitRegister
: {
630 const EmitRegisterMatcher
*Matcher
= cast
<EmitRegisterMatcher
>(N
);
631 const CodeGenRegister
*Reg
= Matcher
->getReg();
632 // If the enum value of the register is larger than one byte can handle,
633 // use EmitRegister2.
634 if (Reg
&& Reg
->EnumValue
> 255) {
635 OS
<< "OPC_EmitRegister2, " << getEnumName(Matcher
->getVT()) << ", ";
636 OS
<< "TARGET_VAL(" << getQualifiedName(Reg
->TheDef
) << "),\n";
639 OS
<< "OPC_EmitRegister, " << getEnumName(Matcher
->getVT()) << ", ";
641 OS
<< getQualifiedName(Reg
->TheDef
) << ",\n";
645 OS
<< "/*zero_reg*/";
652 case Matcher::EmitConvertToTarget
:
653 OS
<< "OPC_EmitConvertToTarget, "
654 << cast
<EmitConvertToTargetMatcher
>(N
)->getSlot() << ",\n";
657 case Matcher::EmitMergeInputChains
: {
658 const EmitMergeInputChainsMatcher
*MN
=
659 cast
<EmitMergeInputChainsMatcher
>(N
);
661 // Handle the specialized forms OPC_EmitMergeInputChains1_0, 1_1, and 1_2.
662 if (MN
->getNumNodes() == 1 && MN
->getNode(0) < 3) {
663 OS
<< "OPC_EmitMergeInputChains1_" << MN
->getNode(0) << ",\n";
667 OS
<< "OPC_EmitMergeInputChains, " << MN
->getNumNodes() << ", ";
668 for (unsigned i
= 0, e
= MN
->getNumNodes(); i
!= e
; ++i
)
669 OS
<< MN
->getNode(i
) << ", ";
671 return 2+MN
->getNumNodes();
673 case Matcher::EmitCopyToReg
: {
674 const auto *C2RMatcher
= cast
<EmitCopyToRegMatcher
>(N
);
676 const CodeGenRegister
*Reg
= C2RMatcher
->getDestPhysReg();
677 if (Reg
->EnumValue
> 255) {
678 assert(isUInt
<16>(Reg
->EnumValue
) && "not handled");
679 OS
<< "OPC_EmitCopyToReg2, " << C2RMatcher
->getSrcSlot() << ", "
680 << "TARGET_VAL(" << getQualifiedName(Reg
->TheDef
) << "),\n";
683 OS
<< "OPC_EmitCopyToReg, " << C2RMatcher
->getSrcSlot() << ", "
684 << getQualifiedName(Reg
->TheDef
) << ",\n";
689 case Matcher::EmitNodeXForm
: {
690 const EmitNodeXFormMatcher
*XF
= cast
<EmitNodeXFormMatcher
>(N
);
691 OS
<< "OPC_EmitNodeXForm, " << getNodeXFormID(XF
->getNodeXForm()) << ", "
692 << XF
->getSlot() << ',';
694 OS
<< " // "<<XF
->getNodeXForm()->getName();
699 case Matcher::EmitNode
:
700 case Matcher::MorphNodeTo
: {
701 auto NumCoveredBytes
= 0;
702 if (InstrumentCoverage
) {
703 if (const MorphNodeToMatcher
*SNT
= dyn_cast
<MorphNodeToMatcher
>(N
)) {
705 OS
<< "OPC_Coverage, ";
707 GetPatFromTreePatternNode(SNT
->getPattern().getSrcPattern());
709 GetPatFromTreePatternNode(SNT
->getPattern().getDstPattern());
710 Record
*PatRecord
= SNT
->getPattern().getSrcRecord();
711 std::string include_src
= getIncludePath(PatRecord
);
713 getPatternIdxFromTable(src
+ " -> " + dst
, std::move(include_src
));
714 OS
<< "TARGET_VAL(" << Offset
<< "),\n";
715 OS
.indent(FullIndexWidth
+ Indent
* 2);
718 const EmitNodeMatcherCommon
*EN
= cast
<EmitNodeMatcherCommon
>(N
);
719 OS
<< (isa
<EmitNodeMatcher
>(EN
) ? "OPC_EmitNode" : "OPC_MorphNodeTo");
720 bool CompressVTs
= EN
->getNumVTs() < 3;
722 OS
<< EN
->getNumVTs();
724 OS
<< ", TARGET_VAL(" << EN
->getOpcodeName() << "), 0";
726 if (EN
->hasChain()) OS
<< "|OPFL_Chain";
727 if (EN
->hasInFlag()) OS
<< "|OPFL_GlueInput";
728 if (EN
->hasOutFlag()) OS
<< "|OPFL_GlueOutput";
729 if (EN
->hasMemRefs()) OS
<< "|OPFL_MemRefs";
730 if (EN
->getNumFixedArityOperands() != -1)
731 OS
<< "|OPFL_Variadic" << EN
->getNumFixedArityOperands();
734 OS
.indent(FullIndexWidth
+ Indent
*2+4);
736 OS
<< EN
->getNumVTs();
741 for (unsigned i
= 0, e
= EN
->getNumVTs(); i
!= e
; ++i
)
742 OS
<< getEnumName(EN
->getVT(i
)) << ", ";
744 OS
<< EN
->getNumOperands();
748 unsigned NumOperandBytes
= 0;
749 for (unsigned i
= 0, e
= EN
->getNumOperands(); i
!= e
; ++i
)
750 NumOperandBytes
+= EmitVBRValue(EN
->getOperand(i
), OS
);
753 // Print the result #'s for EmitNode.
754 if (const EmitNodeMatcher
*E
= dyn_cast
<EmitNodeMatcher
>(EN
)) {
755 if (unsigned NumResults
= EN
->getNumVTs()) {
756 OS
<< " // Results =";
757 unsigned First
= E
->getFirstResultSlot();
758 for (unsigned i
= 0; i
!= NumResults
; ++i
)
759 OS
<< " #" << First
+i
;
764 if (const MorphNodeToMatcher
*SNT
= dyn_cast
<MorphNodeToMatcher
>(N
)) {
765 OS
.indent(FullIndexWidth
+ Indent
*2) << "// Src: "
766 << *SNT
->getPattern().getSrcPattern() << " - Complexity = "
767 << SNT
->getPattern().getPatternComplexity(CGP
) << '\n';
768 OS
.indent(FullIndexWidth
+ Indent
*2) << "// Dst: "
769 << *SNT
->getPattern().getDstPattern() << '\n';
774 return 5 + !CompressVTs
+ EN
->getNumVTs() + NumOperandBytes
+
777 case Matcher::CompleteMatch
: {
778 const CompleteMatchMatcher
*CM
= cast
<CompleteMatchMatcher
>(N
);
779 auto NumCoveredBytes
= 0;
780 if (InstrumentCoverage
) {
782 OS
<< "OPC_Coverage, ";
784 GetPatFromTreePatternNode(CM
->getPattern().getSrcPattern());
786 GetPatFromTreePatternNode(CM
->getPattern().getDstPattern());
787 Record
*PatRecord
= CM
->getPattern().getSrcRecord();
788 std::string include_src
= getIncludePath(PatRecord
);
790 getPatternIdxFromTable(src
+ " -> " + dst
, std::move(include_src
));
791 OS
<< "TARGET_VAL(" << Offset
<< "),\n";
792 OS
.indent(FullIndexWidth
+ Indent
* 2);
794 OS
<< "OPC_CompleteMatch, " << CM
->getNumResults() << ", ";
795 unsigned NumResultBytes
= 0;
796 for (unsigned i
= 0, e
= CM
->getNumResults(); i
!= e
; ++i
)
797 NumResultBytes
+= EmitVBRValue(CM
->getResult(i
), OS
);
800 OS
.indent(FullIndexWidth
+ Indent
*2) << " // Src: "
801 << *CM
->getPattern().getSrcPattern() << " - Complexity = "
802 << CM
->getPattern().getPatternComplexity(CGP
) << '\n';
803 OS
.indent(FullIndexWidth
+ Indent
*2) << " // Dst: "
804 << *CM
->getPattern().getDstPattern();
807 return 2 + NumResultBytes
+ NumCoveredBytes
;
810 llvm_unreachable("Unreachable");
813 /// EmitMatcherList - Emit the bytes for the specified matcher subtree.
814 unsigned MatcherTableEmitter::
815 EmitMatcherList(const Matcher
*N
, unsigned Indent
, unsigned CurrentIdx
,
820 OS
<< "/*" << format_decimal(CurrentIdx
, IndexWidth
) << "*/";
821 unsigned MatcherSize
= EmitMatcher(N
, Indent
, CurrentIdx
, OS
);
823 CurrentIdx
+= MatcherSize
;
825 // If there are other nodes in this list, iterate to them, otherwise we're
832 void MatcherTableEmitter::EmitNodePredicatesFunction(
833 const std::vector
<TreePredicateFn
> &Preds
, StringRef Decl
,
838 BeginEmitFunction(OS
, "bool", Decl
, true/*AddOverride*/);
840 OS
<< " switch (PredNo) {\n";
841 OS
<< " default: llvm_unreachable(\"Invalid predicate in table?\");\n";
842 for (unsigned i
= 0, e
= Preds
.size(); i
!= e
; ++i
) {
843 // Emit the predicate code corresponding to this pattern.
844 TreePredicateFn PredFn
= Preds
[i
];
846 assert(!PredFn
.isAlwaysTrue() && "No code in this predicate");
847 OS
<< " case " << i
<< ": { \n";
848 for (auto *SimilarPred
:
849 NodePredicatesByCodeToRun
[PredFn
.getCodeToRunOnSDNode()])
850 OS
<< " // " << TreePredicateFn(SimilarPred
).getFnName() <<'\n';
852 OS
<< PredFn
.getCodeToRunOnSDNode() << "\n }\n";
859 void MatcherTableEmitter::EmitPredicateFunctions(raw_ostream
&OS
) {
860 // Emit pattern predicates.
861 if (!PatternPredicates
.empty()) {
862 BeginEmitFunction(OS
, "bool",
863 "CheckPatternPredicate(unsigned PredNo) const", true/*AddOverride*/);
865 OS
<< " switch (PredNo) {\n";
866 OS
<< " default: llvm_unreachable(\"Invalid predicate in table?\");\n";
867 for (unsigned i
= 0, e
= PatternPredicates
.size(); i
!= e
; ++i
)
868 OS
<< " case " << i
<< ": return " << PatternPredicates
[i
] << ";\n";
874 // Emit Node predicates.
875 EmitNodePredicatesFunction(
876 NodePredicates
, "CheckNodePredicate(SDNode *Node, unsigned PredNo) const",
878 EmitNodePredicatesFunction(
879 NodePredicatesWithOperands
,
880 "CheckNodePredicateWithOperands(SDNode *Node, unsigned PredNo, "
881 "const SmallVectorImpl<SDValue> &Operands) const",
884 // Emit CompletePattern matchers.
885 // FIXME: This should be const.
886 if (!ComplexPatterns
.empty()) {
887 BeginEmitFunction(OS
, "bool",
888 "CheckComplexPattern(SDNode *Root, SDNode *Parent,\n"
889 " SDValue N, unsigned PatternNo,\n"
890 " SmallVectorImpl<std::pair<SDValue, SDNode*>> &Result)",
891 true/*AddOverride*/);
893 OS
<< " unsigned NextRes = Result.size();\n";
894 OS
<< " switch (PatternNo) {\n";
895 OS
<< " default: llvm_unreachable(\"Invalid pattern # in table?\");\n";
896 for (unsigned i
= 0, e
= ComplexPatterns
.size(); i
!= e
; ++i
) {
897 const ComplexPattern
&P
= *ComplexPatterns
[i
];
898 unsigned NumOps
= P
.getNumOperands();
900 if (P
.hasProperty(SDNPHasChain
))
901 ++NumOps
; // Get the chained node too.
903 OS
<< " case " << i
<< ":\n";
904 if (InstrumentCoverage
)
906 OS
<< " Result.resize(NextRes+" << NumOps
<< ");\n";
907 if (InstrumentCoverage
)
908 OS
<< " bool Succeeded = " << P
.getSelectFunc();
910 OS
<< " return " << P
.getSelectFunc();
913 // If the complex pattern wants the root of the match, pass it in as the
915 if (P
.hasProperty(SDNPWantRoot
))
918 // If the complex pattern wants the parent of the operand being matched,
919 // pass it in as the next argument.
920 if (P
.hasProperty(SDNPWantParent
))
924 for (unsigned i
= 0; i
!= NumOps
; ++i
)
925 OS
<< ", Result[NextRes+" << i
<< "].first";
927 if (InstrumentCoverage
) {
928 OS
<< " if (Succeeded)\n";
929 OS
<< " dbgs() << \"\\nCOMPLEX_PATTERN: " << P
.getSelectFunc()
931 OS
<< " return Succeeded;\n";
941 // Emit SDNodeXForm handlers.
942 // FIXME: This should be const.
943 if (!NodeXForms
.empty()) {
944 BeginEmitFunction(OS
, "SDValue",
945 "RunSDNodeXForm(SDValue V, unsigned XFormNo)", true/*AddOverride*/);
947 OS
<< " switch (XFormNo) {\n";
948 OS
<< " default: llvm_unreachable(\"Invalid xform # in table?\");\n";
950 // FIXME: The node xform could take SDValue's instead of SDNode*'s.
951 for (unsigned i
= 0, e
= NodeXForms
.size(); i
!= e
; ++i
) {
952 const CodeGenDAGPatterns::NodeXForm
&Entry
=
953 CGP
.getSDNodeTransform(NodeXForms
[i
]);
955 Record
*SDNode
= Entry
.first
;
956 const std::string
&Code
= Entry
.second
;
958 OS
<< " case " << i
<< ": { ";
960 OS
<< "// " << NodeXForms
[i
]->getName();
963 std::string ClassName
= CGP
.getSDNodeInfo(SDNode
).getSDClassName();
964 if (ClassName
== "SDNode")
965 OS
<< " SDNode *N = V.getNode();\n";
967 OS
<< " " << ClassName
<< " *N = cast<" << ClassName
968 << ">(V.getNode());\n";
969 OS
<< Code
<< "\n }\n";
977 static void BuildHistogram(const Matcher
*M
, std::vector
<unsigned> &OpcodeFreq
){
978 for (; M
!= nullptr; M
= M
->getNext()) {
980 if (unsigned(M
->getKind()) >= OpcodeFreq
.size())
981 OpcodeFreq
.resize(M
->getKind()+1);
982 OpcodeFreq
[M
->getKind()]++;
984 // Handle recursive nodes.
985 if (const ScopeMatcher
*SM
= dyn_cast
<ScopeMatcher
>(M
)) {
986 for (unsigned i
= 0, e
= SM
->getNumChildren(); i
!= e
; ++i
)
987 BuildHistogram(SM
->getChild(i
), OpcodeFreq
);
988 } else if (const SwitchOpcodeMatcher
*SOM
=
989 dyn_cast
<SwitchOpcodeMatcher
>(M
)) {
990 for (unsigned i
= 0, e
= SOM
->getNumCases(); i
!= e
; ++i
)
991 BuildHistogram(SOM
->getCaseMatcher(i
), OpcodeFreq
);
992 } else if (const SwitchTypeMatcher
*STM
= dyn_cast
<SwitchTypeMatcher
>(M
)) {
993 for (unsigned i
= 0, e
= STM
->getNumCases(); i
!= e
; ++i
)
994 BuildHistogram(STM
->getCaseMatcher(i
), OpcodeFreq
);
999 static StringRef
getOpcodeString(Matcher::KindTy Kind
) {
1001 case Matcher::Scope
: return "OPC_Scope"; break;
1002 case Matcher::RecordNode
: return "OPC_RecordNode"; break;
1003 case Matcher::RecordChild
: return "OPC_RecordChild"; break;
1004 case Matcher::RecordMemRef
: return "OPC_RecordMemRef"; break;
1005 case Matcher::CaptureGlueInput
: return "OPC_CaptureGlueInput"; break;
1006 case Matcher::MoveChild
: return "OPC_MoveChild"; break;
1007 case Matcher::MoveParent
: return "OPC_MoveParent"; break;
1008 case Matcher::CheckSame
: return "OPC_CheckSame"; break;
1009 case Matcher::CheckChildSame
: return "OPC_CheckChildSame"; break;
1010 case Matcher::CheckPatternPredicate
:
1011 return "OPC_CheckPatternPredicate"; break;
1012 case Matcher::CheckPredicate
: return "OPC_CheckPredicate"; break;
1013 case Matcher::CheckOpcode
: return "OPC_CheckOpcode"; break;
1014 case Matcher::SwitchOpcode
: return "OPC_SwitchOpcode"; break;
1015 case Matcher::CheckType
: return "OPC_CheckType"; break;
1016 case Matcher::SwitchType
: return "OPC_SwitchType"; break;
1017 case Matcher::CheckChildType
: return "OPC_CheckChildType"; break;
1018 case Matcher::CheckInteger
: return "OPC_CheckInteger"; break;
1019 case Matcher::CheckChildInteger
: return "OPC_CheckChildInteger"; break;
1020 case Matcher::CheckCondCode
: return "OPC_CheckCondCode"; break;
1021 case Matcher::CheckChild2CondCode
: return "OPC_CheckChild2CondCode"; break;
1022 case Matcher::CheckValueType
: return "OPC_CheckValueType"; break;
1023 case Matcher::CheckComplexPat
: return "OPC_CheckComplexPat"; break;
1024 case Matcher::CheckAndImm
: return "OPC_CheckAndImm"; break;
1025 case Matcher::CheckOrImm
: return "OPC_CheckOrImm"; break;
1026 case Matcher::CheckFoldableChainNode
:
1027 return "OPC_CheckFoldableChainNode"; break;
1028 case Matcher::CheckImmAllOnesV
: return "OPC_CheckImmAllOnesV"; break;
1029 case Matcher::CheckImmAllZerosV
: return "OPC_CheckImmAllZerosV"; break;
1030 case Matcher::EmitInteger
: return "OPC_EmitInteger"; break;
1031 case Matcher::EmitStringInteger
: return "OPC_EmitStringInteger"; break;
1032 case Matcher::EmitRegister
: return "OPC_EmitRegister"; break;
1033 case Matcher::EmitConvertToTarget
: return "OPC_EmitConvertToTarget"; break;
1034 case Matcher::EmitMergeInputChains
: return "OPC_EmitMergeInputChains"; break;
1035 case Matcher::EmitCopyToReg
: return "OPC_EmitCopyToReg"; break;
1036 case Matcher::EmitNode
: return "OPC_EmitNode"; break;
1037 case Matcher::MorphNodeTo
: return "OPC_MorphNodeTo"; break;
1038 case Matcher::EmitNodeXForm
: return "OPC_EmitNodeXForm"; break;
1039 case Matcher::CompleteMatch
: return "OPC_CompleteMatch"; break;
1042 llvm_unreachable("Unhandled opcode?");
1045 void MatcherTableEmitter::EmitHistogram(const Matcher
*M
,
1050 std::vector
<unsigned> OpcodeFreq
;
1051 BuildHistogram(M
, OpcodeFreq
);
1053 OS
<< " // Opcode Histogram:\n";
1054 for (unsigned i
= 0, e
= OpcodeFreq
.size(); i
!= e
; ++i
) {
1056 << left_justify(getOpcodeString((Matcher::KindTy
)i
), HistOpcWidth
)
1057 << " = " << OpcodeFreq
[i
] << '\n';
1063 void llvm::EmitMatcherTable(const Matcher
*TheMatcher
,
1064 const CodeGenDAGPatterns
&CGP
,
1066 OS
<< "#if defined(GET_DAGISEL_DECL) && defined(GET_DAGISEL_BODY)\n";
1067 OS
<< "#error GET_DAGISEL_DECL and GET_DAGISEL_BODY cannot be both defined, ";
1068 OS
<< "undef both for inline definitions\n";
1071 // Emit a check for omitted class name.
1072 OS
<< "#ifdef GET_DAGISEL_BODY\n";
1073 OS
<< "#define LOCAL_DAGISEL_STRINGIZE(X) LOCAL_DAGISEL_STRINGIZE_(X)\n";
1074 OS
<< "#define LOCAL_DAGISEL_STRINGIZE_(X) #X\n";
1075 OS
<< "static_assert(sizeof(LOCAL_DAGISEL_STRINGIZE(GET_DAGISEL_BODY)) > 1,"
1077 OS
<< " \"GET_DAGISEL_BODY is empty: it should be defined with the class "
1079 OS
<< "#undef LOCAL_DAGISEL_STRINGIZE_\n";
1080 OS
<< "#undef LOCAL_DAGISEL_STRINGIZE\n";
1083 OS
<< "#if !defined(GET_DAGISEL_DECL) && !defined(GET_DAGISEL_BODY)\n";
1084 OS
<< "#define DAGISEL_INLINE 1\n";
1086 OS
<< "#define DAGISEL_INLINE 0\n";
1089 OS
<< "#if !DAGISEL_INLINE\n";
1090 OS
<< "#define DAGISEL_CLASS_COLONCOLON GET_DAGISEL_BODY ::\n";
1092 OS
<< "#define DAGISEL_CLASS_COLONCOLON\n";
1095 BeginEmitFunction(OS
, "void", "SelectCode(SDNode *N)", false/*AddOverride*/);
1096 MatcherTableEmitter
MatcherEmitter(CGP
);
1099 OS
<< " // Some target values are emitted as 2 bytes, TARGET_VAL handles\n";
1100 OS
<< " // this.\n";
1101 OS
<< " #define TARGET_VAL(X) X & 255, unsigned(X) >> 8\n";
1102 OS
<< " static const unsigned char MatcherTable[] = {\n";
1103 unsigned TotalSize
= MatcherEmitter
.EmitMatcherList(TheMatcher
, 1, 0, OS
);
1104 OS
<< " 0\n }; // Total Array size is " << (TotalSize
+1) << " bytes\n\n";
1106 MatcherEmitter
.EmitHistogram(TheMatcher
, OS
);
1108 OS
<< " #undef TARGET_VAL\n";
1109 OS
<< " SelectCodeCommon(N, MatcherTable,sizeof(MatcherTable));\n";
1111 EndEmitFunction(OS
);
1113 // Next up, emit the function for node and pattern predicates:
1114 MatcherEmitter
.EmitPredicateFunctions(OS
);
1116 if (InstrumentCoverage
)
1117 MatcherEmitter
.EmitPatternMatchTable(OS
);
1119 // Clean up the preprocessor macros.
1121 OS
<< "#ifdef DAGISEL_INLINE\n";
1122 OS
<< "#undef DAGISEL_INLINE\n";
1124 OS
<< "#ifdef DAGISEL_CLASS_COLONCOLON\n";
1125 OS
<< "#undef DAGISEL_CLASS_COLONCOLON\n";
1127 OS
<< "#ifdef GET_DAGISEL_DECL\n";
1128 OS
<< "#undef GET_DAGISEL_DECL\n";
1130 OS
<< "#ifdef GET_DAGISEL_BODY\n";
1131 OS
<< "#undef GET_DAGISEL_BODY\n";