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