• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===- DAGISelMatcherEmitter.cpp - Matcher Emitter ------------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file contains code to generate C++ code for a matcher.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "DAGISelMatcher.h"
15 #include "CodeGenDAGPatterns.h"
16 #include "llvm/ADT/DenseMap.h"
17 #include "llvm/ADT/SmallString.h"
18 #include "llvm/ADT/StringMap.h"
19 #include "llvm/Support/CommandLine.h"
20 #include "llvm/Support/FormattedStream.h"
21 #include "llvm/TableGen/Record.h"
22 using namespace llvm;
23 
24 enum {
25   CommentIndent = 30
26 };
27 
28 // To reduce generated source code size.
29 static cl::opt<bool>
30 OmitComments("omit-comments", cl::desc("Do not generate comments"),
31              cl::init(false));
32 
33 namespace {
34 class MatcherTableEmitter {
35   const CodeGenDAGPatterns &CGP;
36 
37   DenseMap<TreePattern *, unsigned> NodePredicateMap;
38   std::vector<TreePredicateFn> NodePredicates;
39 
40   StringMap<unsigned> PatternPredicateMap;
41   std::vector<std::string> PatternPredicates;
42 
43   DenseMap<const ComplexPattern*, unsigned> ComplexPatternMap;
44   std::vector<const ComplexPattern*> ComplexPatterns;
45 
46 
47   DenseMap<Record*, unsigned> NodeXFormMap;
48   std::vector<Record*> NodeXForms;
49 
50 public:
MatcherTableEmitter(const CodeGenDAGPatterns & cgp)51   MatcherTableEmitter(const CodeGenDAGPatterns &cgp)
52     : CGP(cgp) {}
53 
54   unsigned EmitMatcherList(const Matcher *N, unsigned Indent,
55                            unsigned StartIdx, formatted_raw_ostream &OS);
56 
57   void EmitPredicateFunctions(formatted_raw_ostream &OS);
58 
59   void EmitHistogram(const Matcher *N, formatted_raw_ostream &OS);
60 private:
61   unsigned EmitMatcher(const Matcher *N, unsigned Indent, unsigned CurrentIdx,
62                        formatted_raw_ostream &OS);
63 
getNodePredicate(TreePredicateFn Pred)64   unsigned getNodePredicate(TreePredicateFn Pred) {
65     unsigned &Entry = NodePredicateMap[Pred.getOrigPatFragRecord()];
66     if (Entry == 0) {
67       NodePredicates.push_back(Pred);
68       Entry = NodePredicates.size();
69     }
70     return Entry-1;
71   }
72 
getPatternPredicate(StringRef PredName)73   unsigned getPatternPredicate(StringRef PredName) {
74     unsigned &Entry = PatternPredicateMap[PredName];
75     if (Entry == 0) {
76       PatternPredicates.push_back(PredName.str());
77       Entry = PatternPredicates.size();
78     }
79     return Entry-1;
80   }
getComplexPat(const ComplexPattern & P)81   unsigned getComplexPat(const ComplexPattern &P) {
82     unsigned &Entry = ComplexPatternMap[&P];
83     if (Entry == 0) {
84       ComplexPatterns.push_back(&P);
85       Entry = ComplexPatterns.size();
86     }
87     return Entry-1;
88   }
89 
getNodeXFormID(Record * Rec)90   unsigned getNodeXFormID(Record *Rec) {
91     unsigned &Entry = NodeXFormMap[Rec];
92     if (Entry == 0) {
93       NodeXForms.push_back(Rec);
94       Entry = NodeXForms.size();
95     }
96     return Entry-1;
97   }
98 
99 };
100 } // end anonymous namespace.
101 
GetVBRSize(unsigned Val)102 static unsigned GetVBRSize(unsigned Val) {
103   if (Val <= 127) return 1;
104 
105   unsigned NumBytes = 0;
106   while (Val >= 128) {
107     Val >>= 7;
108     ++NumBytes;
109   }
110   return NumBytes+1;
111 }
112 
113 /// EmitVBRValue - Emit the specified value as a VBR, returning the number of
114 /// bytes emitted.
EmitVBRValue(uint64_t Val,raw_ostream & OS)115 static uint64_t EmitVBRValue(uint64_t Val, raw_ostream &OS) {
116   if (Val <= 127) {
117     OS << Val << ", ";
118     return 1;
119   }
120 
121   uint64_t InVal = Val;
122   unsigned NumBytes = 0;
123   while (Val >= 128) {
124     OS << (Val&127) << "|128,";
125     Val >>= 7;
126     ++NumBytes;
127   }
128   OS << Val;
129   if (!OmitComments)
130     OS << "/*" << InVal << "*/";
131   OS << ", ";
132   return NumBytes+1;
133 }
134 
135 /// EmitMatcher - Emit bytes for the specified matcher and return
136 /// the number of bytes emitted.
137 unsigned MatcherTableEmitter::
EmitMatcher(const Matcher * N,unsigned Indent,unsigned CurrentIdx,formatted_raw_ostream & OS)138 EmitMatcher(const Matcher *N, unsigned Indent, unsigned CurrentIdx,
139             formatted_raw_ostream &OS) {
140   OS.PadToColumn(Indent*2);
141 
142   switch (N->getKind()) {
143   case Matcher::Scope: {
144     const ScopeMatcher *SM = cast<ScopeMatcher>(N);
145     assert(SM->getNext() == nullptr && "Shouldn't have next after scope");
146 
147     unsigned StartIdx = CurrentIdx;
148 
149     // Emit all of the children.
150     for (unsigned i = 0, e = SM->getNumChildren(); i != e; ++i) {
151       if (i == 0) {
152         OS << "OPC_Scope, ";
153         ++CurrentIdx;
154       } else  {
155         if (!OmitComments) {
156           OS << "/*" << CurrentIdx << "*/";
157           OS.PadToColumn(Indent*2) << "/*Scope*/ ";
158         } else
159           OS.PadToColumn(Indent*2);
160       }
161 
162       // We need to encode the child and the offset of the failure code before
163       // emitting either of them.  Handle this by buffering the output into a
164       // string while we get the size.  Unfortunately, the offset of the
165       // children depends on the VBR size of the child, so for large children we
166       // have to iterate a bit.
167       SmallString<128> TmpBuf;
168       unsigned ChildSize = 0;
169       unsigned VBRSize = 0;
170       do {
171         VBRSize = GetVBRSize(ChildSize);
172 
173         TmpBuf.clear();
174         raw_svector_ostream OS(TmpBuf);
175         formatted_raw_ostream FOS(OS);
176         ChildSize = EmitMatcherList(SM->getChild(i), Indent+1,
177                                     CurrentIdx+VBRSize, FOS);
178       } while (GetVBRSize(ChildSize) != VBRSize);
179 
180       assert(ChildSize != 0 && "Should not have a zero-sized child!");
181 
182       CurrentIdx += EmitVBRValue(ChildSize, OS);
183       if (!OmitComments) {
184         OS << "/*->" << CurrentIdx+ChildSize << "*/";
185 
186         if (i == 0)
187           OS.PadToColumn(CommentIndent) << "// " << SM->getNumChildren()
188             << " children in Scope";
189       }
190 
191       OS << '\n' << TmpBuf.str();
192       CurrentIdx += ChildSize;
193     }
194 
195     // Emit a zero as a sentinel indicating end of 'Scope'.
196     if (!OmitComments)
197       OS << "/*" << CurrentIdx << "*/";
198     OS.PadToColumn(Indent*2) << "0, ";
199     if (!OmitComments)
200       OS << "/*End of Scope*/";
201     OS << '\n';
202     return CurrentIdx - StartIdx + 1;
203   }
204 
205   case Matcher::RecordNode:
206     OS << "OPC_RecordNode,";
207     if (!OmitComments)
208       OS.PadToColumn(CommentIndent) << "// #"
209         << cast<RecordMatcher>(N)->getResultNo() << " = "
210         << cast<RecordMatcher>(N)->getWhatFor();
211     OS << '\n';
212     return 1;
213 
214   case Matcher::RecordChild:
215     OS << "OPC_RecordChild" << cast<RecordChildMatcher>(N)->getChildNo()
216        << ',';
217     if (!OmitComments)
218       OS.PadToColumn(CommentIndent) << "// #"
219         << cast<RecordChildMatcher>(N)->getResultNo() << " = "
220         << cast<RecordChildMatcher>(N)->getWhatFor();
221     OS << '\n';
222     return 1;
223 
224   case Matcher::RecordMemRef:
225     OS << "OPC_RecordMemRef,\n";
226     return 1;
227 
228   case Matcher::CaptureGlueInput:
229     OS << "OPC_CaptureGlueInput,\n";
230     return 1;
231 
232   case Matcher::MoveChild:
233     OS << "OPC_MoveChild, " << cast<MoveChildMatcher>(N)->getChildNo() << ",\n";
234     return 2;
235 
236   case Matcher::MoveParent:
237     OS << "OPC_MoveParent,\n";
238     return 1;
239 
240   case Matcher::CheckSame:
241     OS << "OPC_CheckSame, "
242        << cast<CheckSameMatcher>(N)->getMatchNumber() << ",\n";
243     return 2;
244 
245   case Matcher::CheckChildSame:
246     OS << "OPC_CheckChild"
247        << cast<CheckChildSameMatcher>(N)->getChildNo() << "Same, "
248        << cast<CheckChildSameMatcher>(N)->getMatchNumber() << ",\n";
249     return 2;
250 
251   case Matcher::CheckPatternPredicate: {
252     StringRef Pred =cast<CheckPatternPredicateMatcher>(N)->getPredicate();
253     OS << "OPC_CheckPatternPredicate, " << getPatternPredicate(Pred) << ',';
254     if (!OmitComments)
255       OS.PadToColumn(CommentIndent) << "// " << Pred;
256     OS << '\n';
257     return 2;
258   }
259   case Matcher::CheckPredicate: {
260     TreePredicateFn Pred = cast<CheckPredicateMatcher>(N)->getPredicate();
261     OS << "OPC_CheckPredicate, " << getNodePredicate(Pred) << ',';
262     if (!OmitComments)
263       OS.PadToColumn(CommentIndent) << "// " << Pred.getFnName();
264     OS << '\n';
265     return 2;
266   }
267 
268   case Matcher::CheckOpcode:
269     OS << "OPC_CheckOpcode, TARGET_VAL("
270        << cast<CheckOpcodeMatcher>(N)->getOpcode().getEnumName() << "),\n";
271     return 3;
272 
273   case Matcher::SwitchOpcode:
274   case Matcher::SwitchType: {
275     unsigned StartIdx = CurrentIdx;
276 
277     unsigned NumCases;
278     if (const SwitchOpcodeMatcher *SOM = dyn_cast<SwitchOpcodeMatcher>(N)) {
279       OS << "OPC_SwitchOpcode ";
280       NumCases = SOM->getNumCases();
281     } else {
282       OS << "OPC_SwitchType ";
283       NumCases = cast<SwitchTypeMatcher>(N)->getNumCases();
284     }
285 
286     if (!OmitComments)
287       OS << "/*" << NumCases << " cases */";
288     OS << ", ";
289     ++CurrentIdx;
290 
291     // For each case we emit the size, then the opcode, then the matcher.
292     for (unsigned i = 0, e = NumCases; i != e; ++i) {
293       const Matcher *Child;
294       unsigned IdxSize;
295       if (const SwitchOpcodeMatcher *SOM = dyn_cast<SwitchOpcodeMatcher>(N)) {
296         Child = SOM->getCaseMatcher(i);
297         IdxSize = 2;  // size of opcode in table is 2 bytes.
298       } else {
299         Child = cast<SwitchTypeMatcher>(N)->getCaseMatcher(i);
300         IdxSize = 1;  // size of type in table is 1 byte.
301       }
302 
303       // We need to encode the opcode and the offset of the case code before
304       // emitting the case code.  Handle this by buffering the output into a
305       // string while we get the size.  Unfortunately, the offset of the
306       // children depends on the VBR size of the child, so for large children we
307       // have to iterate a bit.
308       SmallString<128> TmpBuf;
309       unsigned ChildSize = 0;
310       unsigned VBRSize = 0;
311       do {
312         VBRSize = GetVBRSize(ChildSize);
313 
314         TmpBuf.clear();
315         raw_svector_ostream OS(TmpBuf);
316         formatted_raw_ostream FOS(OS);
317         ChildSize = EmitMatcherList(Child, Indent+1, CurrentIdx+VBRSize+IdxSize,
318                                     FOS);
319       } while (GetVBRSize(ChildSize) != VBRSize);
320 
321       assert(ChildSize != 0 && "Should not have a zero-sized child!");
322 
323       if (i != 0) {
324         if (!OmitComments)
325           OS << "/*" << CurrentIdx << "*/";
326         OS.PadToColumn(Indent*2);
327         if (!OmitComments)
328           OS << (isa<SwitchOpcodeMatcher>(N) ?
329                      "/*SwitchOpcode*/ " : "/*SwitchType*/ ");
330       }
331 
332       // Emit the VBR.
333       CurrentIdx += EmitVBRValue(ChildSize, OS);
334 
335       if (const SwitchOpcodeMatcher *SOM = dyn_cast<SwitchOpcodeMatcher>(N))
336         OS << "TARGET_VAL(" << SOM->getCaseOpcode(i).getEnumName() << "),";
337       else
338         OS << getEnumName(cast<SwitchTypeMatcher>(N)->getCaseType(i)) << ',';
339 
340       CurrentIdx += IdxSize;
341 
342       if (!OmitComments)
343         OS << "// ->" << CurrentIdx+ChildSize;
344       OS << '\n';
345       OS << TmpBuf.str();
346       CurrentIdx += ChildSize;
347     }
348 
349     // Emit the final zero to terminate the switch.
350     if (!OmitComments)
351       OS << "/*" << CurrentIdx << "*/";
352     OS.PadToColumn(Indent*2) << "0, ";
353     if (!OmitComments)
354       OS << (isa<SwitchOpcodeMatcher>(N) ?
355              "// EndSwitchOpcode" : "// EndSwitchType");
356 
357     OS << '\n';
358     ++CurrentIdx;
359     return CurrentIdx-StartIdx;
360   }
361 
362  case Matcher::CheckType:
363     assert(cast<CheckTypeMatcher>(N)->getResNo() == 0 &&
364            "FIXME: Add support for CheckType of resno != 0");
365     OS << "OPC_CheckType, "
366        << getEnumName(cast<CheckTypeMatcher>(N)->getType()) << ",\n";
367     return 2;
368 
369   case Matcher::CheckChildType:
370     OS << "OPC_CheckChild"
371        << cast<CheckChildTypeMatcher>(N)->getChildNo() << "Type, "
372        << getEnumName(cast<CheckChildTypeMatcher>(N)->getType()) << ",\n";
373     return 2;
374 
375   case Matcher::CheckInteger: {
376     OS << "OPC_CheckInteger, ";
377     unsigned Bytes=1+EmitVBRValue(cast<CheckIntegerMatcher>(N)->getValue(), OS);
378     OS << '\n';
379     return Bytes;
380   }
381   case Matcher::CheckChildInteger: {
382     OS << "OPC_CheckChild" << cast<CheckChildIntegerMatcher>(N)->getChildNo()
383        << "Integer, ";
384     unsigned Bytes=1+EmitVBRValue(cast<CheckChildIntegerMatcher>(N)->getValue(),
385                                   OS);
386     OS << '\n';
387     return Bytes;
388   }
389   case Matcher::CheckCondCode:
390     OS << "OPC_CheckCondCode, ISD::"
391        << cast<CheckCondCodeMatcher>(N)->getCondCodeName() << ",\n";
392     return 2;
393 
394   case Matcher::CheckValueType:
395     OS << "OPC_CheckValueType, MVT::"
396        << cast<CheckValueTypeMatcher>(N)->getTypeName() << ",\n";
397     return 2;
398 
399   case Matcher::CheckComplexPat: {
400     const CheckComplexPatMatcher *CCPM = cast<CheckComplexPatMatcher>(N);
401     const ComplexPattern &Pattern = CCPM->getPattern();
402     OS << "OPC_CheckComplexPat, /*CP*/" << getComplexPat(Pattern) << ", /*#*/"
403        << CCPM->getMatchNumber() << ',';
404 
405     if (!OmitComments) {
406       OS.PadToColumn(CommentIndent) << "// " << Pattern.getSelectFunc();
407       OS << ":$" << CCPM->getName();
408       for (unsigned i = 0, e = Pattern.getNumOperands(); i != e; ++i)
409         OS << " #" << CCPM->getFirstResult()+i;
410 
411       if (Pattern.hasProperty(SDNPHasChain))
412         OS << " + chain result";
413     }
414     OS << '\n';
415     return 3;
416   }
417 
418   case Matcher::CheckAndImm: {
419     OS << "OPC_CheckAndImm, ";
420     unsigned Bytes=1+EmitVBRValue(cast<CheckAndImmMatcher>(N)->getValue(), OS);
421     OS << '\n';
422     return Bytes;
423   }
424 
425   case Matcher::CheckOrImm: {
426     OS << "OPC_CheckOrImm, ";
427     unsigned Bytes = 1+EmitVBRValue(cast<CheckOrImmMatcher>(N)->getValue(), OS);
428     OS << '\n';
429     return Bytes;
430   }
431 
432   case Matcher::CheckFoldableChainNode:
433     OS << "OPC_CheckFoldableChainNode,\n";
434     return 1;
435 
436   case Matcher::EmitInteger: {
437     int64_t Val = cast<EmitIntegerMatcher>(N)->getValue();
438     OS << "OPC_EmitInteger, "
439        << getEnumName(cast<EmitIntegerMatcher>(N)->getVT()) << ", ";
440     unsigned Bytes = 2+EmitVBRValue(Val, OS);
441     OS << '\n';
442     return Bytes;
443   }
444   case Matcher::EmitStringInteger: {
445     const std::string &Val = cast<EmitStringIntegerMatcher>(N)->getValue();
446     // These should always fit into one byte.
447     OS << "OPC_EmitInteger, "
448       << getEnumName(cast<EmitStringIntegerMatcher>(N)->getVT()) << ", "
449       << Val << ",\n";
450     return 3;
451   }
452 
453   case Matcher::EmitRegister: {
454     const EmitRegisterMatcher *Matcher = cast<EmitRegisterMatcher>(N);
455     const CodeGenRegister *Reg = Matcher->getReg();
456     // If the enum value of the register is larger than one byte can handle,
457     // use EmitRegister2.
458     if (Reg && Reg->EnumValue > 255) {
459       OS << "OPC_EmitRegister2, " << getEnumName(Matcher->getVT()) << ", ";
460       OS << "TARGET_VAL(" << getQualifiedName(Reg->TheDef) << "),\n";
461       return 4;
462     } else {
463       OS << "OPC_EmitRegister, " << getEnumName(Matcher->getVT()) << ", ";
464       if (Reg) {
465         OS << getQualifiedName(Reg->TheDef) << ",\n";
466       } else {
467         OS << "0 ";
468         if (!OmitComments)
469           OS << "/*zero_reg*/";
470         OS << ",\n";
471       }
472       return 3;
473     }
474   }
475 
476   case Matcher::EmitConvertToTarget:
477     OS << "OPC_EmitConvertToTarget, "
478        << cast<EmitConvertToTargetMatcher>(N)->getSlot() << ",\n";
479     return 2;
480 
481   case Matcher::EmitMergeInputChains: {
482     const EmitMergeInputChainsMatcher *MN =
483       cast<EmitMergeInputChainsMatcher>(N);
484 
485     // Handle the specialized forms OPC_EmitMergeInputChains1_0 and 1_1.
486     if (MN->getNumNodes() == 1 && MN->getNode(0) < 2) {
487       OS << "OPC_EmitMergeInputChains1_" << MN->getNode(0) << ",\n";
488       return 1;
489     }
490 
491     OS << "OPC_EmitMergeInputChains, " << MN->getNumNodes() << ", ";
492     for (unsigned i = 0, e = MN->getNumNodes(); i != e; ++i)
493       OS << MN->getNode(i) << ", ";
494     OS << '\n';
495     return 2+MN->getNumNodes();
496   }
497   case Matcher::EmitCopyToReg:
498     OS << "OPC_EmitCopyToReg, "
499        << cast<EmitCopyToRegMatcher>(N)->getSrcSlot() << ", "
500        << getQualifiedName(cast<EmitCopyToRegMatcher>(N)->getDestPhysReg())
501        << ",\n";
502     return 3;
503   case Matcher::EmitNodeXForm: {
504     const EmitNodeXFormMatcher *XF = cast<EmitNodeXFormMatcher>(N);
505     OS << "OPC_EmitNodeXForm, " << getNodeXFormID(XF->getNodeXForm()) << ", "
506        << XF->getSlot() << ',';
507     if (!OmitComments)
508       OS.PadToColumn(CommentIndent) << "// "<<XF->getNodeXForm()->getName();
509     OS <<'\n';
510     return 3;
511   }
512 
513   case Matcher::EmitNode:
514   case Matcher::MorphNodeTo: {
515     const EmitNodeMatcherCommon *EN = cast<EmitNodeMatcherCommon>(N);
516     OS << (isa<EmitNodeMatcher>(EN) ? "OPC_EmitNode" : "OPC_MorphNodeTo");
517     OS << ", TARGET_VAL(" << EN->getOpcodeName() << "), 0";
518 
519     if (EN->hasChain())   OS << "|OPFL_Chain";
520     if (EN->hasInFlag())  OS << "|OPFL_GlueInput";
521     if (EN->hasOutFlag()) OS << "|OPFL_GlueOutput";
522     if (EN->hasMemRefs()) OS << "|OPFL_MemRefs";
523     if (EN->getNumFixedArityOperands() != -1)
524       OS << "|OPFL_Variadic" << EN->getNumFixedArityOperands();
525     OS << ",\n";
526 
527     OS.PadToColumn(Indent*2+4) << EN->getNumVTs();
528     if (!OmitComments)
529       OS << "/*#VTs*/";
530     OS << ", ";
531     for (unsigned i = 0, e = EN->getNumVTs(); i != e; ++i)
532       OS << getEnumName(EN->getVT(i)) << ", ";
533 
534     OS << EN->getNumOperands();
535     if (!OmitComments)
536       OS << "/*#Ops*/";
537     OS << ", ";
538     unsigned NumOperandBytes = 0;
539     for (unsigned i = 0, e = EN->getNumOperands(); i != e; ++i)
540       NumOperandBytes += EmitVBRValue(EN->getOperand(i), OS);
541 
542     if (!OmitComments) {
543       // Print the result #'s for EmitNode.
544       if (const EmitNodeMatcher *E = dyn_cast<EmitNodeMatcher>(EN)) {
545         if (unsigned NumResults = EN->getNumVTs()) {
546           OS.PadToColumn(CommentIndent) << "// Results =";
547           unsigned First = E->getFirstResultSlot();
548           for (unsigned i = 0; i != NumResults; ++i)
549             OS << " #" << First+i;
550         }
551       }
552       OS << '\n';
553 
554       if (const MorphNodeToMatcher *SNT = dyn_cast<MorphNodeToMatcher>(N)) {
555         OS.PadToColumn(Indent*2) << "// Src: "
556           << *SNT->getPattern().getSrcPattern() << " - Complexity = "
557           << SNT->getPattern().getPatternComplexity(CGP) << '\n';
558         OS.PadToColumn(Indent*2) << "// Dst: "
559           << *SNT->getPattern().getDstPattern() << '\n';
560       }
561     } else
562       OS << '\n';
563 
564     return 6+EN->getNumVTs()+NumOperandBytes;
565   }
566   case Matcher::MarkGlueResults: {
567     const MarkGlueResultsMatcher *CFR = cast<MarkGlueResultsMatcher>(N);
568     OS << "OPC_MarkGlueResults, " << CFR->getNumNodes() << ", ";
569     unsigned NumOperandBytes = 0;
570     for (unsigned i = 0, e = CFR->getNumNodes(); i != e; ++i)
571       NumOperandBytes += EmitVBRValue(CFR->getNode(i), OS);
572     OS << '\n';
573     return 2+NumOperandBytes;
574   }
575   case Matcher::CompleteMatch: {
576     const CompleteMatchMatcher *CM = cast<CompleteMatchMatcher>(N);
577     OS << "OPC_CompleteMatch, " << CM->getNumResults() << ", ";
578     unsigned NumResultBytes = 0;
579     for (unsigned i = 0, e = CM->getNumResults(); i != e; ++i)
580       NumResultBytes += EmitVBRValue(CM->getResult(i), OS);
581     OS << '\n';
582     if (!OmitComments) {
583       OS.PadToColumn(Indent*2) << "// Src: "
584         << *CM->getPattern().getSrcPattern() << " - Complexity = "
585         << CM->getPattern().getPatternComplexity(CGP) << '\n';
586       OS.PadToColumn(Indent*2) << "// Dst: "
587         << *CM->getPattern().getDstPattern();
588     }
589     OS << '\n';
590     return 2 + NumResultBytes;
591   }
592   }
593   llvm_unreachable("Unreachable");
594 }
595 
596 /// EmitMatcherList - Emit the bytes for the specified matcher subtree.
597 unsigned MatcherTableEmitter::
EmitMatcherList(const Matcher * N,unsigned Indent,unsigned CurrentIdx,formatted_raw_ostream & OS)598 EmitMatcherList(const Matcher *N, unsigned Indent, unsigned CurrentIdx,
599                 formatted_raw_ostream &OS) {
600   unsigned Size = 0;
601   while (N) {
602     if (!OmitComments)
603       OS << "/*" << CurrentIdx << "*/";
604     unsigned MatcherSize = EmitMatcher(N, Indent, CurrentIdx, OS);
605     Size += MatcherSize;
606     CurrentIdx += MatcherSize;
607 
608     // If there are other nodes in this list, iterate to them, otherwise we're
609     // done.
610     N = N->getNext();
611   }
612   return Size;
613 }
614 
EmitPredicateFunctions(formatted_raw_ostream & OS)615 void MatcherTableEmitter::EmitPredicateFunctions(formatted_raw_ostream &OS) {
616   // Emit pattern predicates.
617   if (!PatternPredicates.empty()) {
618     OS << "bool CheckPatternPredicate(unsigned PredNo) const override {\n";
619     OS << "  switch (PredNo) {\n";
620     OS << "  default: llvm_unreachable(\"Invalid predicate in table?\");\n";
621     for (unsigned i = 0, e = PatternPredicates.size(); i != e; ++i)
622       OS << "  case " << i << ": return "  << PatternPredicates[i] << ";\n";
623     OS << "  }\n";
624     OS << "}\n\n";
625   }
626 
627   // Emit Node predicates.
628   // FIXME: Annoyingly, these are stored by name, which we never even emit. Yay?
629   StringMap<TreePattern*> PFsByName;
630 
631   for (CodeGenDAGPatterns::pf_iterator I = CGP.pf_begin(), E = CGP.pf_end();
632        I != E; ++I)
633     PFsByName[I->first->getName()] = I->second;
634 
635   if (!NodePredicates.empty()) {
636     OS << "bool CheckNodePredicate(SDNode *Node,\n";
637     OS << "                        unsigned PredNo) const override {\n";
638     OS << "  switch (PredNo) {\n";
639     OS << "  default: llvm_unreachable(\"Invalid predicate in table?\");\n";
640     for (unsigned i = 0, e = NodePredicates.size(); i != e; ++i) {
641       // Emit the predicate code corresponding to this pattern.
642       TreePredicateFn PredFn = NodePredicates[i];
643 
644       assert(!PredFn.isAlwaysTrue() && "No code in this predicate");
645       OS << "  case " << i << ": { // " << NodePredicates[i].getFnName() <<'\n';
646 
647       OS << PredFn.getCodeToRunOnSDNode() << "\n  }\n";
648     }
649     OS << "  }\n";
650     OS << "}\n\n";
651   }
652 
653   // Emit CompletePattern matchers.
654   // FIXME: This should be const.
655   if (!ComplexPatterns.empty()) {
656     OS << "bool CheckComplexPattern(SDNode *Root, SDNode *Parent,\n";
657     OS << "                         SDValue N, unsigned PatternNo,\n";
658     OS << "         SmallVectorImpl<std::pair<SDValue, SDNode*> > &Result) override {\n";
659     OS << "  unsigned NextRes = Result.size();\n";
660     OS << "  switch (PatternNo) {\n";
661     OS << "  default: llvm_unreachable(\"Invalid pattern # in table?\");\n";
662     for (unsigned i = 0, e = ComplexPatterns.size(); i != e; ++i) {
663       const ComplexPattern &P = *ComplexPatterns[i];
664       unsigned NumOps = P.getNumOperands();
665 
666       if (P.hasProperty(SDNPHasChain))
667         ++NumOps;  // Get the chained node too.
668 
669       OS << "  case " << i << ":\n";
670       OS << "    Result.resize(NextRes+" << NumOps << ");\n";
671       OS << "    return "  << P.getSelectFunc();
672 
673       OS << "(";
674       // If the complex pattern wants the root of the match, pass it in as the
675       // first argument.
676       if (P.hasProperty(SDNPWantRoot))
677         OS << "Root, ";
678 
679       // If the complex pattern wants the parent of the operand being matched,
680       // pass it in as the next argument.
681       if (P.hasProperty(SDNPWantParent))
682         OS << "Parent, ";
683 
684       OS << "N";
685       for (unsigned i = 0; i != NumOps; ++i)
686         OS << ", Result[NextRes+" << i << "].first";
687       OS << ");\n";
688     }
689     OS << "  }\n";
690     OS << "}\n\n";
691   }
692 
693 
694   // Emit SDNodeXForm handlers.
695   // FIXME: This should be const.
696   if (!NodeXForms.empty()) {
697     OS << "SDValue RunSDNodeXForm(SDValue V, unsigned XFormNo) override {\n";
698     OS << "  switch (XFormNo) {\n";
699     OS << "  default: llvm_unreachable(\"Invalid xform # in table?\");\n";
700 
701     // FIXME: The node xform could take SDValue's instead of SDNode*'s.
702     for (unsigned i = 0, e = NodeXForms.size(); i != e; ++i) {
703       const CodeGenDAGPatterns::NodeXForm &Entry =
704         CGP.getSDNodeTransform(NodeXForms[i]);
705 
706       Record *SDNode = Entry.first;
707       const std::string &Code = Entry.second;
708 
709       OS << "  case " << i << ": {  ";
710       if (!OmitComments)
711         OS << "// " << NodeXForms[i]->getName();
712       OS << '\n';
713 
714       std::string ClassName = CGP.getSDNodeInfo(SDNode).getSDClassName();
715       if (ClassName == "SDNode")
716         OS << "    SDNode *N = V.getNode();\n";
717       else
718         OS << "    " << ClassName << " *N = cast<" << ClassName
719            << ">(V.getNode());\n";
720       OS << Code << "\n  }\n";
721     }
722     OS << "  }\n";
723     OS << "}\n\n";
724   }
725 }
726 
BuildHistogram(const Matcher * M,std::vector<unsigned> & OpcodeFreq)727 static void BuildHistogram(const Matcher *M, std::vector<unsigned> &OpcodeFreq){
728   for (; M != nullptr; M = M->getNext()) {
729     // Count this node.
730     if (unsigned(M->getKind()) >= OpcodeFreq.size())
731       OpcodeFreq.resize(M->getKind()+1);
732     OpcodeFreq[M->getKind()]++;
733 
734     // Handle recursive nodes.
735     if (const ScopeMatcher *SM = dyn_cast<ScopeMatcher>(M)) {
736       for (unsigned i = 0, e = SM->getNumChildren(); i != e; ++i)
737         BuildHistogram(SM->getChild(i), OpcodeFreq);
738     } else if (const SwitchOpcodeMatcher *SOM =
739                  dyn_cast<SwitchOpcodeMatcher>(M)) {
740       for (unsigned i = 0, e = SOM->getNumCases(); i != e; ++i)
741         BuildHistogram(SOM->getCaseMatcher(i), OpcodeFreq);
742     } else if (const SwitchTypeMatcher *STM = dyn_cast<SwitchTypeMatcher>(M)) {
743       for (unsigned i = 0, e = STM->getNumCases(); i != e; ++i)
744         BuildHistogram(STM->getCaseMatcher(i), OpcodeFreq);
745     }
746   }
747 }
748 
EmitHistogram(const Matcher * M,formatted_raw_ostream & OS)749 void MatcherTableEmitter::EmitHistogram(const Matcher *M,
750                                         formatted_raw_ostream &OS) {
751   if (OmitComments)
752     return;
753 
754   std::vector<unsigned> OpcodeFreq;
755   BuildHistogram(M, OpcodeFreq);
756 
757   OS << "  // Opcode Histogram:\n";
758   for (unsigned i = 0, e = OpcodeFreq.size(); i != e; ++i) {
759     OS << "  // #";
760     switch ((Matcher::KindTy)i) {
761     case Matcher::Scope: OS << "OPC_Scope"; break;
762     case Matcher::RecordNode: OS << "OPC_RecordNode"; break;
763     case Matcher::RecordChild: OS << "OPC_RecordChild"; break;
764     case Matcher::RecordMemRef: OS << "OPC_RecordMemRef"; break;
765     case Matcher::CaptureGlueInput: OS << "OPC_CaptureGlueInput"; break;
766     case Matcher::MoveChild: OS << "OPC_MoveChild"; break;
767     case Matcher::MoveParent: OS << "OPC_MoveParent"; break;
768     case Matcher::CheckSame: OS << "OPC_CheckSame"; break;
769     case Matcher::CheckChildSame: OS << "OPC_CheckChildSame"; break;
770     case Matcher::CheckPatternPredicate:
771       OS << "OPC_CheckPatternPredicate"; break;
772     case Matcher::CheckPredicate: OS << "OPC_CheckPredicate"; break;
773     case Matcher::CheckOpcode: OS << "OPC_CheckOpcode"; break;
774     case Matcher::SwitchOpcode: OS << "OPC_SwitchOpcode"; break;
775     case Matcher::CheckType: OS << "OPC_CheckType"; break;
776     case Matcher::SwitchType: OS << "OPC_SwitchType"; break;
777     case Matcher::CheckChildType: OS << "OPC_CheckChildType"; break;
778     case Matcher::CheckInteger: OS << "OPC_CheckInteger"; break;
779     case Matcher::CheckChildInteger: OS << "OPC_CheckChildInteger"; break;
780     case Matcher::CheckCondCode: OS << "OPC_CheckCondCode"; break;
781     case Matcher::CheckValueType: OS << "OPC_CheckValueType"; break;
782     case Matcher::CheckComplexPat: OS << "OPC_CheckComplexPat"; break;
783     case Matcher::CheckAndImm: OS << "OPC_CheckAndImm"; break;
784     case Matcher::CheckOrImm: OS << "OPC_CheckOrImm"; break;
785     case Matcher::CheckFoldableChainNode:
786       OS << "OPC_CheckFoldableChainNode"; break;
787     case Matcher::EmitInteger: OS << "OPC_EmitInteger"; break;
788     case Matcher::EmitStringInteger: OS << "OPC_EmitStringInteger"; break;
789     case Matcher::EmitRegister: OS << "OPC_EmitRegister"; break;
790     case Matcher::EmitConvertToTarget: OS << "OPC_EmitConvertToTarget"; break;
791     case Matcher::EmitMergeInputChains: OS << "OPC_EmitMergeInputChains"; break;
792     case Matcher::EmitCopyToReg: OS << "OPC_EmitCopyToReg"; break;
793     case Matcher::EmitNode: OS << "OPC_EmitNode"; break;
794     case Matcher::MorphNodeTo: OS << "OPC_MorphNodeTo"; break;
795     case Matcher::EmitNodeXForm: OS << "OPC_EmitNodeXForm"; break;
796     case Matcher::MarkGlueResults: OS << "OPC_MarkGlueResults"; break;
797     case Matcher::CompleteMatch: OS << "OPC_CompleteMatch"; break;
798     }
799 
800     OS.PadToColumn(40) << " = " << OpcodeFreq[i] << '\n';
801   }
802   OS << '\n';
803 }
804 
805 
EmitMatcherTable(const Matcher * TheMatcher,const CodeGenDAGPatterns & CGP,raw_ostream & O)806 void llvm::EmitMatcherTable(const Matcher *TheMatcher,
807                             const CodeGenDAGPatterns &CGP,
808                             raw_ostream &O) {
809   formatted_raw_ostream OS(O);
810 
811   OS << "// The main instruction selector code.\n";
812   OS << "SDNode *SelectCode(SDNode *N) {\n";
813 
814   MatcherTableEmitter MatcherEmitter(CGP);
815 
816   OS << "  // Some target values are emitted as 2 bytes, TARGET_VAL handles\n";
817   OS << "  // this.\n";
818   OS << "  #define TARGET_VAL(X) X & 255, unsigned(X) >> 8\n";
819   OS << "  static const unsigned char MatcherTable[] = {\n";
820   unsigned TotalSize = MatcherEmitter.EmitMatcherList(TheMatcher, 6, 0, OS);
821   OS << "    0\n  }; // Total Array size is " << (TotalSize+1) << " bytes\n\n";
822 
823   MatcherEmitter.EmitHistogram(TheMatcher, OS);
824 
825   OS << "  #undef TARGET_VAL\n";
826   OS << "  return SelectCodeCommon(N, MatcherTable,sizeof(MatcherTable));\n}\n";
827   OS << '\n';
828 
829   // Next up, emit the function for node and pattern predicates:
830   MatcherEmitter.EmitPredicateFunctions(OS);
831 }
832