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