utils/TableGen/DAGISelMatcherEmitter.cpp

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