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