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