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"
22using namespace llvm;
23
24enum {
25  CommentIndent = 30
26};
27
28// To reduce generated source code size.
29static cl::opt<bool>
30OmitComments("omit-comments", cl::desc("Do not generate comments"),
31             cl::init(false));
32
33namespace {
34class 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
50public:
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);
60private:
61  unsigned EmitMatcher(const Matcher *N, unsigned Indent, unsigned CurrentIdx,
62                       formatted_raw_ostream &OS);
63
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
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  }
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
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
102static 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.
115static 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.
137unsigned MatcherTableEmitter::
138EmitMatcher(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.
597unsigned MatcherTableEmitter::
598EmitMatcherList(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
615void 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
727static 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
749void 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
806void 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