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