utils/TableGen/DAGISelMatcherEmitter.cpp

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