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/TableGen/Record.h"
17#include "llvm/ADT/DenseMap.h"
18#include "llvm/ADT/SmallString.h"
19#include "llvm/ADT/StringMap.h"
20#include "llvm/Support/CommandLine.h"
21#include "llvm/Support/FormattedStream.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/// EmitMatcherOpcodes - 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() == 0 && "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::CheckPatternPredicate: {
246    StringRef Pred =cast<CheckPatternPredicateMatcher>(N)->getPredicate();
247    OS << "OPC_CheckPatternPredicate, " << getPatternPredicate(Pred) << ',';
248    if (!OmitComments)
249      OS.PadToColumn(CommentIndent) << "// " << Pred;
250    OS << '\n';
251    return 2;
252  }
253  case Matcher::CheckPredicate: {
254    TreePredicateFn Pred = cast<CheckPredicateMatcher>(N)->getPredicate();
255    OS << "OPC_CheckPredicate, " << getNodePredicate(Pred) << ',';
256    if (!OmitComments)
257      OS.PadToColumn(CommentIndent) << "// " << Pred.getFnName();
258    OS << '\n';
259    return 2;
260  }
261
262  case Matcher::CheckOpcode:
263    OS << "OPC_CheckOpcode, TARGET_VAL("
264       << cast<CheckOpcodeMatcher>(N)->getOpcode().getEnumName() << "),\n";
265    return 3;
266
267  case Matcher::SwitchOpcode:
268  case Matcher::SwitchType: {
269    unsigned StartIdx = CurrentIdx;
270
271    unsigned NumCases;
272    if (const SwitchOpcodeMatcher *SOM = dyn_cast<SwitchOpcodeMatcher>(N)) {
273      OS << "OPC_SwitchOpcode ";
274      NumCases = SOM->getNumCases();
275    } else {
276      OS << "OPC_SwitchType ";
277      NumCases = cast<SwitchTypeMatcher>(N)->getNumCases();
278    }
279
280    if (!OmitComments)
281      OS << "/*" << NumCases << " cases */";
282    OS << ", ";
283    ++CurrentIdx;
284
285    // For each case we emit the size, then the opcode, then the matcher.
286    for (unsigned i = 0, e = NumCases; i != e; ++i) {
287      const Matcher *Child;
288      unsigned IdxSize;
289      if (const SwitchOpcodeMatcher *SOM = dyn_cast<SwitchOpcodeMatcher>(N)) {
290        Child = SOM->getCaseMatcher(i);
291        IdxSize = 2;  // size of opcode in table is 2 bytes.
292      } else {
293        Child = cast<SwitchTypeMatcher>(N)->getCaseMatcher(i);
294        IdxSize = 1;  // size of type in table is 1 byte.
295      }
296
297      // We need to encode the opcode and the offset of the case code before
298      // emitting the case code.  Handle this by buffering the output into a
299      // string while we get the size.  Unfortunately, the offset of the
300      // children depends on the VBR size of the child, so for large children we
301      // have to iterate a bit.
302      SmallString<128> TmpBuf;
303      unsigned ChildSize = 0;
304      unsigned VBRSize = 0;
305      do {
306        VBRSize = GetVBRSize(ChildSize);
307
308        TmpBuf.clear();
309        raw_svector_ostream OS(TmpBuf);
310        formatted_raw_ostream FOS(OS);
311        ChildSize = EmitMatcherList(Child, Indent+1, CurrentIdx+VBRSize+IdxSize,
312                                    FOS);
313      } while (GetVBRSize(ChildSize) != VBRSize);
314
315      assert(ChildSize != 0 && "Should not have a zero-sized child!");
316
317      if (i != 0) {
318        OS.PadToColumn(Indent*2);
319        if (!OmitComments)
320        OS << (isa<SwitchOpcodeMatcher>(N) ?
321                   "/*SwitchOpcode*/ " : "/*SwitchType*/ ");
322      }
323
324      // Emit the VBR.
325      CurrentIdx += EmitVBRValue(ChildSize, OS);
326
327      OS << ' ';
328      if (const SwitchOpcodeMatcher *SOM = dyn_cast<SwitchOpcodeMatcher>(N))
329        OS << "TARGET_VAL(" << SOM->getCaseOpcode(i).getEnumName() << "),";
330      else
331        OS << getEnumName(cast<SwitchTypeMatcher>(N)->getCaseType(i)) << ',';
332
333      CurrentIdx += IdxSize;
334
335      if (!OmitComments)
336        OS << "// ->" << CurrentIdx+ChildSize;
337      OS << '\n';
338      OS << TmpBuf.str();
339      CurrentIdx += ChildSize;
340    }
341
342    // Emit the final zero to terminate the switch.
343    OS.PadToColumn(Indent*2) << "0, ";
344    if (!OmitComments)
345      OS << (isa<SwitchOpcodeMatcher>(N) ?
346             "// EndSwitchOpcode" : "// EndSwitchType");
347
348    OS << '\n';
349    ++CurrentIdx;
350    return CurrentIdx-StartIdx;
351  }
352
353 case Matcher::CheckType:
354    assert(cast<CheckTypeMatcher>(N)->getResNo() == 0 &&
355           "FIXME: Add support for CheckType of resno != 0");
356    OS << "OPC_CheckType, "
357       << getEnumName(cast<CheckTypeMatcher>(N)->getType()) << ",\n";
358    return 2;
359
360  case Matcher::CheckChildType:
361    OS << "OPC_CheckChild"
362       << cast<CheckChildTypeMatcher>(N)->getChildNo() << "Type, "
363       << getEnumName(cast<CheckChildTypeMatcher>(N)->getType()) << ",\n";
364    return 2;
365
366  case Matcher::CheckInteger: {
367    OS << "OPC_CheckInteger, ";
368    unsigned Bytes=1+EmitVBRValue(cast<CheckIntegerMatcher>(N)->getValue(), OS);
369    OS << '\n';
370    return Bytes;
371  }
372  case Matcher::CheckCondCode:
373    OS << "OPC_CheckCondCode, ISD::"
374       << cast<CheckCondCodeMatcher>(N)->getCondCodeName() << ",\n";
375    return 2;
376
377  case Matcher::CheckValueType:
378    OS << "OPC_CheckValueType, MVT::"
379       << cast<CheckValueTypeMatcher>(N)->getTypeName() << ",\n";
380    return 2;
381
382  case Matcher::CheckComplexPat: {
383    const CheckComplexPatMatcher *CCPM = cast<CheckComplexPatMatcher>(N);
384    const ComplexPattern &Pattern = CCPM->getPattern();
385    OS << "OPC_CheckComplexPat, /*CP*/" << getComplexPat(Pattern) << ", /*#*/"
386       << CCPM->getMatchNumber() << ',';
387
388    if (!OmitComments) {
389      OS.PadToColumn(CommentIndent) << "// " << Pattern.getSelectFunc();
390      OS << ":$" << CCPM->getName();
391      for (unsigned i = 0, e = Pattern.getNumOperands(); i != e; ++i)
392        OS << " #" << CCPM->getFirstResult()+i;
393
394      if (Pattern.hasProperty(SDNPHasChain))
395        OS << " + chain result";
396    }
397    OS << '\n';
398    return 3;
399  }
400
401  case Matcher::CheckAndImm: {
402    OS << "OPC_CheckAndImm, ";
403    unsigned Bytes=1+EmitVBRValue(cast<CheckAndImmMatcher>(N)->getValue(), OS);
404    OS << '\n';
405    return Bytes;
406  }
407
408  case Matcher::CheckOrImm: {
409    OS << "OPC_CheckOrImm, ";
410    unsigned Bytes = 1+EmitVBRValue(cast<CheckOrImmMatcher>(N)->getValue(), OS);
411    OS << '\n';
412    return Bytes;
413  }
414
415  case Matcher::CheckFoldableChainNode:
416    OS << "OPC_CheckFoldableChainNode,\n";
417    return 1;
418
419  case Matcher::EmitInteger: {
420    int64_t Val = cast<EmitIntegerMatcher>(N)->getValue();
421    OS << "OPC_EmitInteger, "
422       << getEnumName(cast<EmitIntegerMatcher>(N)->getVT()) << ", ";
423    unsigned Bytes = 2+EmitVBRValue(Val, OS);
424    OS << '\n';
425    return Bytes;
426  }
427  case Matcher::EmitStringInteger: {
428    const std::string &Val = cast<EmitStringIntegerMatcher>(N)->getValue();
429    // These should always fit into one byte.
430    OS << "OPC_EmitInteger, "
431      << getEnumName(cast<EmitStringIntegerMatcher>(N)->getVT()) << ", "
432      << Val << ",\n";
433    return 3;
434  }
435
436  case Matcher::EmitRegister: {
437    const EmitRegisterMatcher *Matcher = cast<EmitRegisterMatcher>(N);
438    const CodeGenRegister *Reg = Matcher->getReg();
439    // If the enum value of the register is larger than one byte can handle,
440    // use EmitRegister2.
441    if (Reg && Reg->EnumValue > 255) {
442      OS << "OPC_EmitRegister2, " << getEnumName(Matcher->getVT()) << ", ";
443      OS << "TARGET_VAL(" << getQualifiedName(Reg->TheDef) << "),\n";
444      return 4;
445    } else {
446      OS << "OPC_EmitRegister, " << getEnumName(Matcher->getVT()) << ", ";
447      if (Reg) {
448        OS << getQualifiedName(Reg->TheDef) << ",\n";
449      } else {
450        OS << "0 ";
451        if (!OmitComments)
452          OS << "/*zero_reg*/";
453        OS << ",\n";
454      }
455      return 3;
456    }
457  }
458
459  case Matcher::EmitConvertToTarget:
460    OS << "OPC_EmitConvertToTarget, "
461       << cast<EmitConvertToTargetMatcher>(N)->getSlot() << ",\n";
462    return 2;
463
464  case Matcher::EmitMergeInputChains: {
465    const EmitMergeInputChainsMatcher *MN =
466      cast<EmitMergeInputChainsMatcher>(N);
467
468    // Handle the specialized forms OPC_EmitMergeInputChains1_0 and 1_1.
469    if (MN->getNumNodes() == 1 && MN->getNode(0) < 2) {
470      OS << "OPC_EmitMergeInputChains1_" << MN->getNode(0) << ",\n";
471      return 1;
472    }
473
474    OS << "OPC_EmitMergeInputChains, " << MN->getNumNodes() << ", ";
475    for (unsigned i = 0, e = MN->getNumNodes(); i != e; ++i)
476      OS << MN->getNode(i) << ", ";
477    OS << '\n';
478    return 2+MN->getNumNodes();
479  }
480  case Matcher::EmitCopyToReg:
481    OS << "OPC_EmitCopyToReg, "
482       << cast<EmitCopyToRegMatcher>(N)->getSrcSlot() << ", "
483       << getQualifiedName(cast<EmitCopyToRegMatcher>(N)->getDestPhysReg())
484       << ",\n";
485    return 3;
486  case Matcher::EmitNodeXForm: {
487    const EmitNodeXFormMatcher *XF = cast<EmitNodeXFormMatcher>(N);
488    OS << "OPC_EmitNodeXForm, " << getNodeXFormID(XF->getNodeXForm()) << ", "
489       << XF->getSlot() << ',';
490    if (!OmitComments)
491      OS.PadToColumn(CommentIndent) << "// "<<XF->getNodeXForm()->getName();
492    OS <<'\n';
493    return 3;
494  }
495
496  case Matcher::EmitNode:
497  case Matcher::MorphNodeTo: {
498    const EmitNodeMatcherCommon *EN = cast<EmitNodeMatcherCommon>(N);
499    OS << (isa<EmitNodeMatcher>(EN) ? "OPC_EmitNode" : "OPC_MorphNodeTo");
500    OS << ", TARGET_VAL(" << EN->getOpcodeName() << "), 0";
501
502    if (EN->hasChain())   OS << "|OPFL_Chain";
503    if (EN->hasInFlag())  OS << "|OPFL_GlueInput";
504    if (EN->hasOutFlag()) OS << "|OPFL_GlueOutput";
505    if (EN->hasMemRefs()) OS << "|OPFL_MemRefs";
506    if (EN->getNumFixedArityOperands() != -1)
507      OS << "|OPFL_Variadic" << EN->getNumFixedArityOperands();
508    OS << ",\n";
509
510    OS.PadToColumn(Indent*2+4) << EN->getNumVTs();
511    if (!OmitComments)
512      OS << "/*#VTs*/";
513    OS << ", ";
514    for (unsigned i = 0, e = EN->getNumVTs(); i != e; ++i)
515      OS << getEnumName(EN->getVT(i)) << ", ";
516
517    OS << EN->getNumOperands();
518    if (!OmitComments)
519      OS << "/*#Ops*/";
520    OS << ", ";
521    unsigned NumOperandBytes = 0;
522    for (unsigned i = 0, e = EN->getNumOperands(); i != e; ++i)
523      NumOperandBytes += EmitVBRValue(EN->getOperand(i), OS);
524
525    if (!OmitComments) {
526      // Print the result #'s for EmitNode.
527      if (const EmitNodeMatcher *E = dyn_cast<EmitNodeMatcher>(EN)) {
528        if (unsigned NumResults = EN->getNumVTs()) {
529          OS.PadToColumn(CommentIndent) << "// Results =";
530          unsigned First = E->getFirstResultSlot();
531          for (unsigned i = 0; i != NumResults; ++i)
532            OS << " #" << First+i;
533        }
534      }
535      OS << '\n';
536
537      if (const MorphNodeToMatcher *SNT = dyn_cast<MorphNodeToMatcher>(N)) {
538        OS.PadToColumn(Indent*2) << "// Src: "
539          << *SNT->getPattern().getSrcPattern() << " - Complexity = "
540          << SNT->getPattern().getPatternComplexity(CGP) << '\n';
541        OS.PadToColumn(Indent*2) << "// Dst: "
542          << *SNT->getPattern().getDstPattern() << '\n';
543      }
544    } else
545      OS << '\n';
546
547    return 6+EN->getNumVTs()+NumOperandBytes;
548  }
549  case Matcher::MarkGlueResults: {
550    const MarkGlueResultsMatcher *CFR = cast<MarkGlueResultsMatcher>(N);
551    OS << "OPC_MarkGlueResults, " << CFR->getNumNodes() << ", ";
552    unsigned NumOperandBytes = 0;
553    for (unsigned i = 0, e = CFR->getNumNodes(); i != e; ++i)
554      NumOperandBytes += EmitVBRValue(CFR->getNode(i), OS);
555    OS << '\n';
556    return 2+NumOperandBytes;
557  }
558  case Matcher::CompleteMatch: {
559    const CompleteMatchMatcher *CM = cast<CompleteMatchMatcher>(N);
560    OS << "OPC_CompleteMatch, " << CM->getNumResults() << ", ";
561    unsigned NumResultBytes = 0;
562    for (unsigned i = 0, e = CM->getNumResults(); i != e; ++i)
563      NumResultBytes += EmitVBRValue(CM->getResult(i), OS);
564    OS << '\n';
565    if (!OmitComments) {
566      OS.PadToColumn(Indent*2) << "// Src: "
567        << *CM->getPattern().getSrcPattern() << " - Complexity = "
568        << CM->getPattern().getPatternComplexity(CGP) << '\n';
569      OS.PadToColumn(Indent*2) << "// Dst: "
570        << *CM->getPattern().getDstPattern();
571    }
572    OS << '\n';
573    return 2 + NumResultBytes;
574  }
575  }
576  llvm_unreachable("Unreachable");
577}
578
579/// EmitMatcherList - Emit the bytes for the specified matcher subtree.
580unsigned MatcherTableEmitter::
581EmitMatcherList(const Matcher *N, unsigned Indent, unsigned CurrentIdx,
582                formatted_raw_ostream &OS) {
583  unsigned Size = 0;
584  while (N) {
585    if (!OmitComments)
586      OS << "/*" << CurrentIdx << "*/";
587    unsigned MatcherSize = EmitMatcher(N, Indent, CurrentIdx, OS);
588    Size += MatcherSize;
589    CurrentIdx += MatcherSize;
590
591    // If there are other nodes in this list, iterate to them, otherwise we're
592    // done.
593    N = N->getNext();
594  }
595  return Size;
596}
597
598void MatcherTableEmitter::EmitPredicateFunctions(formatted_raw_ostream &OS) {
599  // Emit pattern predicates.
600  if (!PatternPredicates.empty()) {
601    OS << "virtual bool CheckPatternPredicate(unsigned PredNo) const {\n";
602    OS << "  switch (PredNo) {\n";
603    OS << "  default: llvm_unreachable(\"Invalid predicate in table?\");\n";
604    for (unsigned i = 0, e = PatternPredicates.size(); i != e; ++i)
605      OS << "  case " << i << ": return "  << PatternPredicates[i] << ";\n";
606    OS << "  }\n";
607    OS << "}\n\n";
608  }
609
610  // Emit Node predicates.
611  // FIXME: Annoyingly, these are stored by name, which we never even emit. Yay?
612  StringMap<TreePattern*> PFsByName;
613
614  for (CodeGenDAGPatterns::pf_iterator I = CGP.pf_begin(), E = CGP.pf_end();
615       I != E; ++I)
616    PFsByName[I->first->getName()] = I->second;
617
618  if (!NodePredicates.empty()) {
619    OS << "virtual bool CheckNodePredicate(SDNode *Node,\n";
620    OS << "                                unsigned PredNo) const {\n";
621    OS << "  switch (PredNo) {\n";
622    OS << "  default: llvm_unreachable(\"Invalid predicate in table?\");\n";
623    for (unsigned i = 0, e = NodePredicates.size(); i != e; ++i) {
624      // Emit the predicate code corresponding to this pattern.
625      TreePredicateFn PredFn = NodePredicates[i];
626
627      assert(!PredFn.isAlwaysTrue() && "No code in this predicate");
628      OS << "  case " << i << ": { // " << NodePredicates[i].getFnName() <<'\n';
629
630      OS << PredFn.getCodeToRunOnSDNode() << "\n  }\n";
631    }
632    OS << "  }\n";
633    OS << "}\n\n";
634  }
635
636  // Emit CompletePattern matchers.
637  // FIXME: This should be const.
638  if (!ComplexPatterns.empty()) {
639    OS << "virtual bool CheckComplexPattern(SDNode *Root, SDNode *Parent,\n";
640    OS << "                                 SDValue N, unsigned PatternNo,\n";
641    OS << "         SmallVectorImpl<std::pair<SDValue, SDNode*> > &Result) {\n";
642    OS << "  unsigned NextRes = Result.size();\n";
643    OS << "  switch (PatternNo) {\n";
644    OS << "  default: llvm_unreachable(\"Invalid pattern # in table?\");\n";
645    for (unsigned i = 0, e = ComplexPatterns.size(); i != e; ++i) {
646      const ComplexPattern &P = *ComplexPatterns[i];
647      unsigned NumOps = P.getNumOperands();
648
649      if (P.hasProperty(SDNPHasChain))
650        ++NumOps;  // Get the chained node too.
651
652      OS << "  case " << i << ":\n";
653      OS << "    Result.resize(NextRes+" << NumOps << ");\n";
654      OS << "    return "  << P.getSelectFunc();
655
656      OS << "(";
657      // If the complex pattern wants the root of the match, pass it in as the
658      // first argument.
659      if (P.hasProperty(SDNPWantRoot))
660        OS << "Root, ";
661
662      // If the complex pattern wants the parent of the operand being matched,
663      // pass it in as the next argument.
664      if (P.hasProperty(SDNPWantParent))
665        OS << "Parent, ";
666
667      OS << "N";
668      for (unsigned i = 0; i != NumOps; ++i)
669        OS << ", Result[NextRes+" << i << "].first";
670      OS << ");\n";
671    }
672    OS << "  }\n";
673    OS << "}\n\n";
674  }
675
676
677  // Emit SDNodeXForm handlers.
678  // FIXME: This should be const.
679  if (!NodeXForms.empty()) {
680    OS << "virtual SDValue RunSDNodeXForm(SDValue V, unsigned XFormNo) {\n";
681    OS << "  switch (XFormNo) {\n";
682    OS << "  default: llvm_unreachable(\"Invalid xform # in table?\");\n";
683
684    // FIXME: The node xform could take SDValue's instead of SDNode*'s.
685    for (unsigned i = 0, e = NodeXForms.size(); i != e; ++i) {
686      const CodeGenDAGPatterns::NodeXForm &Entry =
687        CGP.getSDNodeTransform(NodeXForms[i]);
688
689      Record *SDNode = Entry.first;
690      const std::string &Code = Entry.second;
691
692      OS << "  case " << i << ": {  ";
693      if (!OmitComments)
694        OS << "// " << NodeXForms[i]->getName();
695      OS << '\n';
696
697      std::string ClassName = CGP.getSDNodeInfo(SDNode).getSDClassName();
698      if (ClassName == "SDNode")
699        OS << "    SDNode *N = V.getNode();\n";
700      else
701        OS << "    " << ClassName << " *N = cast<" << ClassName
702           << ">(V.getNode());\n";
703      OS << Code << "\n  }\n";
704    }
705    OS << "  }\n";
706    OS << "}\n\n";
707  }
708}
709
710static void BuildHistogram(const Matcher *M, std::vector<unsigned> &OpcodeFreq){
711  for (; M != 0; M = M->getNext()) {
712    // Count this node.
713    if (unsigned(M->getKind()) >= OpcodeFreq.size())
714      OpcodeFreq.resize(M->getKind()+1);
715    OpcodeFreq[M->getKind()]++;
716
717    // Handle recursive nodes.
718    if (const ScopeMatcher *SM = dyn_cast<ScopeMatcher>(M)) {
719      for (unsigned i = 0, e = SM->getNumChildren(); i != e; ++i)
720        BuildHistogram(SM->getChild(i), OpcodeFreq);
721    } else if (const SwitchOpcodeMatcher *SOM =
722                 dyn_cast<SwitchOpcodeMatcher>(M)) {
723      for (unsigned i = 0, e = SOM->getNumCases(); i != e; ++i)
724        BuildHistogram(SOM->getCaseMatcher(i), OpcodeFreq);
725    } else if (const SwitchTypeMatcher *STM = dyn_cast<SwitchTypeMatcher>(M)) {
726      for (unsigned i = 0, e = STM->getNumCases(); i != e; ++i)
727        BuildHistogram(STM->getCaseMatcher(i), OpcodeFreq);
728    }
729  }
730}
731
732void MatcherTableEmitter::EmitHistogram(const Matcher *M,
733                                        formatted_raw_ostream &OS) {
734  if (OmitComments)
735    return;
736
737  std::vector<unsigned> OpcodeFreq;
738  BuildHistogram(M, OpcodeFreq);
739
740  OS << "  // Opcode Histogram:\n";
741  for (unsigned i = 0, e = OpcodeFreq.size(); i != e; ++i) {
742    OS << "  // #";
743    switch ((Matcher::KindTy)i) {
744    case Matcher::Scope: OS << "OPC_Scope"; break;
745    case Matcher::RecordNode: OS << "OPC_RecordNode"; break;
746    case Matcher::RecordChild: OS << "OPC_RecordChild"; break;
747    case Matcher::RecordMemRef: OS << "OPC_RecordMemRef"; break;
748    case Matcher::CaptureGlueInput: OS << "OPC_CaptureGlueInput"; break;
749    case Matcher::MoveChild: OS << "OPC_MoveChild"; break;
750    case Matcher::MoveParent: OS << "OPC_MoveParent"; break;
751    case Matcher::CheckSame: OS << "OPC_CheckSame"; break;
752    case Matcher::CheckPatternPredicate:
753      OS << "OPC_CheckPatternPredicate"; break;
754    case Matcher::CheckPredicate: OS << "OPC_CheckPredicate"; break;
755    case Matcher::CheckOpcode: OS << "OPC_CheckOpcode"; break;
756    case Matcher::SwitchOpcode: OS << "OPC_SwitchOpcode"; break;
757    case Matcher::CheckType: OS << "OPC_CheckType"; break;
758    case Matcher::SwitchType: OS << "OPC_SwitchType"; break;
759    case Matcher::CheckChildType: OS << "OPC_CheckChildType"; break;
760    case Matcher::CheckInteger: OS << "OPC_CheckInteger"; break;
761    case Matcher::CheckCondCode: OS << "OPC_CheckCondCode"; break;
762    case Matcher::CheckValueType: OS << "OPC_CheckValueType"; break;
763    case Matcher::CheckComplexPat: OS << "OPC_CheckComplexPat"; break;
764    case Matcher::CheckAndImm: OS << "OPC_CheckAndImm"; break;
765    case Matcher::CheckOrImm: OS << "OPC_CheckOrImm"; break;
766    case Matcher::CheckFoldableChainNode:
767      OS << "OPC_CheckFoldableChainNode"; break;
768    case Matcher::EmitInteger: OS << "OPC_EmitInteger"; break;
769    case Matcher::EmitStringInteger: OS << "OPC_EmitStringInteger"; break;
770    case Matcher::EmitRegister: OS << "OPC_EmitRegister"; break;
771    case Matcher::EmitConvertToTarget: OS << "OPC_EmitConvertToTarget"; break;
772    case Matcher::EmitMergeInputChains: OS << "OPC_EmitMergeInputChains"; break;
773    case Matcher::EmitCopyToReg: OS << "OPC_EmitCopyToReg"; break;
774    case Matcher::EmitNode: OS << "OPC_EmitNode"; break;
775    case Matcher::MorphNodeTo: OS << "OPC_MorphNodeTo"; break;
776    case Matcher::EmitNodeXForm: OS << "OPC_EmitNodeXForm"; break;
777    case Matcher::MarkGlueResults: OS << "OPC_MarkGlueResults"; break;
778    case Matcher::CompleteMatch: OS << "OPC_CompleteMatch"; break;
779    }
780
781    OS.PadToColumn(40) << " = " << OpcodeFreq[i] << '\n';
782  }
783  OS << '\n';
784}
785
786
787void llvm::EmitMatcherTable(const Matcher *TheMatcher,
788                            const CodeGenDAGPatterns &CGP,
789                            raw_ostream &O) {
790  formatted_raw_ostream OS(O);
791
792  OS << "// The main instruction selector code.\n";
793  OS << "SDNode *SelectCode(SDNode *N) {\n";
794
795  MatcherTableEmitter MatcherEmitter(CGP);
796
797  OS << "  // Some target values are emitted as 2 bytes, TARGET_VAL handles\n";
798  OS << "  // this.\n";
799  OS << "  #define TARGET_VAL(X) X & 255, unsigned(X) >> 8\n";
800  OS << "  static const unsigned char MatcherTable[] = {\n";
801  unsigned TotalSize = MatcherEmitter.EmitMatcherList(TheMatcher, 5, 0, OS);
802  OS << "    0\n  }; // Total Array size is " << (TotalSize+1) << " bytes\n\n";
803
804  MatcherEmitter.EmitHistogram(TheMatcher, OS);
805
806  OS << "  #undef TARGET_VAL\n";
807  OS << "  return SelectCodeCommon(N, MatcherTable,sizeof(MatcherTable));\n}\n";
808  OS << '\n';
809
810  // Next up, emit the function for node and pattern predicates:
811  MatcherEmitter.EmitPredicateFunctions(OS);
812}
813