Home | History | Annotate | Download | only in TableGen 
      1 //===- DAGISelMatcherEmitter.cpp - Matcher Emitter ------------------------===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 //
     10 // This file contains code to generate C++ code for a matcher.
     11 //
     12 //===----------------------------------------------------------------------===//
     13 
     14 #include "DAGISelMatcher.h"
     15 #include "CodeGenDAGPatterns.h"
     16 #include "llvm/ADT/DenseMap.h"
     17 #include "llvm/ADT/SmallString.h"
     18 #include "llvm/ADT/StringMap.h"
     19 #include "llvm/Support/CommandLine.h"
     20 #include "llvm/Support/FormattedStream.h"
     21 #include "llvm/TableGen/Record.h"
     22 using namespace llvm;
     23 
     24 enum {
     25   CommentIndent = 30
     26 };
     27 
     28 // To reduce generated source code size.
     29 static cl::opt<bool>
     30 OmitComments("omit-comments", cl::desc("Do not generate comments"),
     31              cl::init(false));
     32 
     33 namespace {
     34 class MatcherTableEmitter {
     35   const CodeGenDAGPatterns &CGP;
     36 
     37   DenseMap<TreePattern *, unsigned> NodePredicateMap;
     38   std::vector<TreePredicateFn> NodePredicates;
     39 
     40   StringMap<unsigned> PatternPredicateMap;
     41   std::vector<std::string> PatternPredicates;
     42 
     43   DenseMap<const ComplexPattern*, unsigned> ComplexPatternMap;
     44   std::vector<const ComplexPattern*> ComplexPatterns;
     45 
     46 
     47   DenseMap<Record*, unsigned> NodeXFormMap;
     48   std::vector<Record*> NodeXForms;
     49 
     50 public:
     51   MatcherTableEmitter(const CodeGenDAGPatterns &cgp)
     52     : CGP(cgp) {}
     53 
     54   unsigned EmitMatcherList(const Matcher *N, unsigned Indent,
     55                            unsigned StartIdx, formatted_raw_ostream &OS);
     56 
     57   void EmitPredicateFunctions(formatted_raw_ostream &OS);
     58 
     59   void EmitHistogram(const Matcher *N, formatted_raw_ostream &OS);
     60 private:
     61   unsigned EmitMatcher(const Matcher *N, unsigned Indent, unsigned CurrentIdx,
     62                        formatted_raw_ostream &OS);
     63 
     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 
    102 static unsigned GetVBRSize(unsigned Val) {
    103   if (Val <= 127) return 1;
    104 
    105   unsigned NumBytes = 0;
    106   while (Val >= 128) {
    107     Val >>= 7;
    108     ++NumBytes;
    109   }
    110   return NumBytes+1;
    111 }
    112 
    113 /// EmitVBRValue - Emit the specified value as a VBR, returning the number of
    114 /// bytes emitted.
    115 static uint64_t EmitVBRValue(uint64_t Val, raw_ostream &OS) {
    116   if (Val <= 127) {
    117     OS << Val << ", ";
    118     return 1;
    119   }
    120 
    121   uint64_t InVal = Val;
    122   unsigned NumBytes = 0;
    123   while (Val >= 128) {
    124     OS << (Val&127) << "|128,";
    125     Val >>= 7;
    126     ++NumBytes;
    127   }
    128   OS << Val;
    129   if (!OmitComments)
    130     OS << "/*" << InVal << "*/";
    131   OS << ", ";
    132   return NumBytes+1;
    133 }
    134 
    135 /// EmitMatcher - Emit bytes for the specified matcher and return
    136 /// the number of bytes emitted.
    137 unsigned MatcherTableEmitter::
    138 EmitMatcher(const Matcher *N, unsigned Indent, unsigned CurrentIdx,
    139             formatted_raw_ostream &OS) {
    140   OS.PadToColumn(Indent*2);
    141 
    142   switch (N->getKind()) {
    143   case Matcher::Scope: {
    144     const ScopeMatcher *SM = cast<ScopeMatcher>(N);
    145     assert(SM->getNext() == 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.
    580 unsigned MatcherTableEmitter::
    581 EmitMatcherList(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 
    598 void 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 
    710 static 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 
    732 void 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 
    787 void 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