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