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     OS << "OPC_EmitCopyToReg, "
 675        << cast<EmitCopyToRegMatcher>(N)->getSrcSlot() << ", "
 676        << getQualifiedName(cast<EmitCopyToRegMatcher>(N)->getDestPhysReg())
 677        << ",\n";
 678     return 3;
 679   case Matcher::EmitNodeXForm: {
 680     const EmitNodeXFormMatcher *XF = cast<EmitNodeXFormMatcher>(N);
 681     OS << "OPC_EmitNodeXForm, " << getNodeXFormID(XF->getNodeXForm()) << ", "
 682        << XF->getSlot() << ',';
 683     if (!OmitComments)
 684       OS << " // "<<XF->getNodeXForm()->getName();
 685     OS <<'\n';
 686     return 3;
 687   }
 688
 689   case Matcher::EmitNode:
 690   case Matcher::MorphNodeTo: {
 691     auto NumCoveredBytes = 0;
 692     if (InstrumentCoverage) {
 693       if (const MorphNodeToMatcher *SNT = dyn_cast<MorphNodeToMatcher>(N)) {
 694         NumCoveredBytes = 3;
 695         OS << "OPC_Coverage, ";
 696         std::string src =
 697             GetPatFromTreePatternNode(SNT->getPattern().getSrcPattern());
 698         std::string dst =
 699             GetPatFromTreePatternNode(SNT->getPattern().getDstPattern());
 700         Record *PatRecord = SNT->getPattern().getSrcRecord();
 701         std::string include_src = getIncludePath(PatRecord);
 702         unsigned Offset =
 703             getPatternIdxFromTable(src + " -> " + dst, std::move(include_src));
 704         OS << "TARGET_VAL(" << Offset << "),\n";
 705         OS.indent(FullIndexWidth + Indent * 2);
 706       }
 707     }
 708     const EmitNodeMatcherCommon *EN = cast<EmitNodeMatcherCommon>(N);
 709     OS << (isa<EmitNodeMatcher>(EN) ? "OPC_EmitNode" : "OPC_MorphNodeTo");
 710     bool CompressVTs = EN->getNumVTs() < 3;
 711     if (CompressVTs)
 712       OS << EN->getNumVTs();
 713
 714     OS << ", TARGET_VAL(" << EN->getOpcodeName() << "), 0";
 715
 716     if (EN->hasChain())   OS << "|OPFL_Chain";
 717     if (EN->hasInFlag())  OS << "|OPFL_GlueInput";
 718     if (EN->hasOutFlag()) OS << "|OPFL_GlueOutput";
 719     if (EN->hasMemRefs()) OS << "|OPFL_MemRefs";
 720     if (EN->getNumFixedArityOperands() != -1)
 721       OS << "|OPFL_Variadic" << EN->getNumFixedArityOperands();
 722     OS << ",\n";
 723
 724     OS.indent(FullIndexWidth + Indent*2+4);
 725     if (!CompressVTs) {
 726       OS << EN->getNumVTs();
 727       if (!OmitComments)
 728         OS << "/*#VTs*/";
 729       OS << ", ";
 730     }
 731     for (unsigned i = 0, e = EN->getNumVTs(); i != e; ++i)
 732       OS << getEnumName(EN->getVT(i)) << ", ";
 733
 734     OS << EN->getNumOperands();
 735     if (!OmitComments)
 736       OS << "/*#Ops*/";
 737     OS << ", ";
 738     unsigned NumOperandBytes = 0;
 739     for (unsigned i = 0, e = EN->getNumOperands(); i != e; ++i)
 740       NumOperandBytes += EmitVBRValue(EN->getOperand(i), OS);
 741
 742     if (!OmitComments) {
 743       // Print the result #'s for EmitNode.
 744       if (const EmitNodeMatcher *E = dyn_cast<EmitNodeMatcher>(EN)) {
 745         if (unsigned NumResults = EN->getNumVTs()) {
 746           OS << " // Results =";
 747           unsigned First = E->getFirstResultSlot();
 748           for (unsigned i = 0; i != NumResults; ++i)
 749             OS << " #" << First+i;
 750         }
 751       }
 752       OS << '\n';
 753
 754       if (const MorphNodeToMatcher *SNT = dyn_cast<MorphNodeToMatcher>(N)) {
 755         OS.indent(FullIndexWidth + Indent*2) << "// Src: "
 756           << *SNT->getPattern().getSrcPattern() << " - Complexity = "
 757           << SNT->getPattern().getPatternComplexity(CGP) << '\n';
 758         OS.indent(FullIndexWidth + Indent*2) << "// Dst: "
 759           << *SNT->getPattern().getDstPattern() << '\n';
 760       }
 761     } else
 762       OS << '\n';
 763
 764     return 5 + !CompressVTs + EN->getNumVTs() + NumOperandBytes +
 765            NumCoveredBytes;
 766   }
 767   case Matcher::CompleteMatch: {
 768     const CompleteMatchMatcher *CM = cast<CompleteMatchMatcher>(N);
 769     auto NumCoveredBytes = 0;
 770     if (InstrumentCoverage) {
 771       NumCoveredBytes = 3;
 772       OS << "OPC_Coverage, ";
 773       std::string src =
 774           GetPatFromTreePatternNode(CM->getPattern().getSrcPattern());
 775       std::string dst =
 776           GetPatFromTreePatternNode(CM->getPattern().getDstPattern());
 777       Record *PatRecord = CM->getPattern().getSrcRecord();
 778       std::string include_src = getIncludePath(PatRecord);
 779       unsigned Offset =
 780           getPatternIdxFromTable(src + " -> " + dst, std::move(include_src));
 781       OS << "TARGET_VAL(" << Offset << "),\n";
 782       OS.indent(FullIndexWidth + Indent * 2);
 783     }
 784     OS << "OPC_CompleteMatch, " << CM->getNumResults() << ", ";
 785     unsigned NumResultBytes = 0;
 786     for (unsigned i = 0, e = CM->getNumResults(); i != e; ++i)
 787       NumResultBytes += EmitVBRValue(CM->getResult(i), OS);
 788     OS << '\n';
 789     if (!OmitComments) {
 790       OS.indent(FullIndexWidth + Indent*2) << " // Src: "
 791         << *CM->getPattern().getSrcPattern() << " - Complexity = "
 792         << CM->getPattern().getPatternComplexity(CGP) << '\n';
 793       OS.indent(FullIndexWidth + Indent*2) << " // Dst: "
 794         << *CM->getPattern().getDstPattern();
 795     }
 796     OS << '\n';
 797     return 2 + NumResultBytes + NumCoveredBytes;
 798   }
 799   }
 800   llvm_unreachable("Unreachable");
 801 }
 802
 803 /// EmitMatcherList - Emit the bytes for the specified matcher subtree.
 804 unsigned MatcherTableEmitter::
 805 EmitMatcherList(const Matcher *N, unsigned Indent, unsigned CurrentIdx,
 806                 raw_ostream &OS) {
 807   unsigned Size = 0;
 808   while (N) {
 809     if (!OmitComments)
 810       OS << "/*" << format_decimal(CurrentIdx, IndexWidth) << "*/";
 811     unsigned MatcherSize = EmitMatcher(N, Indent, CurrentIdx, OS);
 812     Size += MatcherSize;
 813     CurrentIdx += MatcherSize;
 814
 815     // If there are other nodes in this list, iterate to them, otherwise we're
 816     // done.
 817     N = N->getNext();
 818   }
 819   return Size;
 820 }
 821
 822 void MatcherTableEmitter::EmitNodePredicatesFunction(
 823     const std::vector<TreePredicateFn> &Preds, StringRef Decl,
 824     raw_ostream &OS) {
 825   if (Preds.empty())
 826     return;
 827
 828   BeginEmitFunction(OS, "bool", Decl, true/*AddOverride*/);
 829   OS << "{\n";
 830   OS << "  switch (PredNo) {\n";
 831   OS << "  default: llvm_unreachable(\"Invalid predicate in table?\");\n";
 832   for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
 833     // Emit the predicate code corresponding to this pattern.
 834     TreePredicateFn PredFn = Preds[i];
 835
 836     assert(!PredFn.isAlwaysTrue() && "No code in this predicate");
 837     OS << "  case " << i << ": { \n";
 838     for (auto *SimilarPred :
 839           NodePredicatesByCodeToRun[PredFn.getCodeToRunOnSDNode()])
 840       OS << "    // " << TreePredicateFn(SimilarPred).getFnName() <<'\n';
 841
 842     OS << PredFn.getCodeToRunOnSDNode() << "\n  }\n";
 843   }
 844   OS << "  }\n";
 845   OS << "}\n";
 846   EndEmitFunction(OS);
 847 }
 848
 849 void MatcherTableEmitter::EmitPredicateFunctions(raw_ostream &OS) {
 850   // Emit pattern predicates.
 851   if (!PatternPredicates.empty()) {
 852     BeginEmitFunction(OS, "bool",
 853           "CheckPatternPredicate(unsigned PredNo) const", true/*AddOverride*/);
 854     OS << "{\n";
 855     OS << "  switch (PredNo) {\n";
 856     OS << "  default: llvm_unreachable(\"Invalid predicate in table?\");\n";
 857     for (unsigned i = 0, e = PatternPredicates.size(); i != e; ++i)
 858       OS << "  case " << i << ": return "  << PatternPredicates[i] << ";\n";
 859     OS << "  }\n";
 860     OS << "}\n";
 861     EndEmitFunction(OS);
 862   }
 863
 864   // Emit Node predicates.
 865   EmitNodePredicatesFunction(
 866       NodePredicates, "CheckNodePredicate(SDNode *Node, unsigned PredNo) const",
 867       OS);
 868   EmitNodePredicatesFunction(
 869       NodePredicatesWithOperands,
 870       "CheckNodePredicateWithOperands(SDNode *Node, unsigned PredNo, "
 871       "const SmallVectorImpl<SDValue> &Operands) const",
 872       OS);
 873
 874   // Emit CompletePattern matchers.
 875   // FIXME: This should be const.
 876   if (!ComplexPatterns.empty()) {
 877     BeginEmitFunction(OS, "bool",
 878           "CheckComplexPattern(SDNode *Root, SDNode *Parent,\n"
 879           "      SDValue N, unsigned PatternNo,\n"
 880           "      SmallVectorImpl<std::pair<SDValue, SDNode*>> &Result)",
 881           true/*AddOverride*/);
 882     OS << "{\n";
 883     OS << "  unsigned NextRes = Result.size();\n";
 884     OS << "  switch (PatternNo) {\n";
 885     OS << "  default: llvm_unreachable(\"Invalid pattern # in table?\");\n";
 886     for (unsigned i = 0, e = ComplexPatterns.size(); i != e; ++i) {
 887       const ComplexPattern &P = *ComplexPatterns[i];
 888       unsigned NumOps = P.getNumOperands();
 889
 890       if (P.hasProperty(SDNPHasChain))
 891         ++NumOps;  // Get the chained node too.
 892
 893       OS << "  case " << i << ":\n";
 894       if (InstrumentCoverage)
 895         OS << "  {\n";
 896       OS << "    Result.resize(NextRes+" << NumOps << ");\n";
 897       if (InstrumentCoverage)
 898         OS << "    bool Succeeded = " << P.getSelectFunc();
 899       else
 900         OS << "  return " << P.getSelectFunc();
 901
 902       OS << "(";
 903       // If the complex pattern wants the root of the match, pass it in as the
 904       // first argument.
 905       if (P.hasProperty(SDNPWantRoot))
 906         OS << "Root, ";
 907
 908       // If the complex pattern wants the parent of the operand being matched,
 909       // pass it in as the next argument.
 910       if (P.hasProperty(SDNPWantParent))
 911         OS << "Parent, ";
 912
 913       OS << "N";
 914       for (unsigned i = 0; i != NumOps; ++i)
 915         OS << ", Result[NextRes+" << i << "].first";
 916       OS << ");\n";
 917       if (InstrumentCoverage) {
 918         OS << "    if (Succeeded)\n";
 919         OS << "       dbgs() << \"\\nCOMPLEX_PATTERN: " << P.getSelectFunc()
 920            << "\\n\" ;\n";
 921         OS << "    return Succeeded;\n";
 922         OS << "    }\n";
 923       }
 924     }
 925     OS << "  }\n";
 926     OS << "}\n";
 927     EndEmitFunction(OS);
 928   }
 929
 930
 931   // Emit SDNodeXForm handlers.
 932   // FIXME: This should be const.
 933   if (!NodeXForms.empty()) {
 934     BeginEmitFunction(OS, "SDValue",
 935           "RunSDNodeXForm(SDValue V, unsigned XFormNo)", true/*AddOverride*/);
 936     OS << "{\n";
 937     OS << "  switch (XFormNo) {\n";
 938     OS << "  default: llvm_unreachable(\"Invalid xform # in table?\");\n";
 939
 940     // FIXME: The node xform could take SDValue's instead of SDNode*'s.
 941     for (unsigned i = 0, e = NodeXForms.size(); i != e; ++i) {
 942       const CodeGenDAGPatterns::NodeXForm &Entry =
 943         CGP.getSDNodeTransform(NodeXForms[i]);
 944
 945       Record *SDNode = Entry.first;
 946       const std::string &Code = Entry.second;
 947
 948       OS << "  case " << i << ": {  ";
 949       if (!OmitComments)
 950         OS << "// " << NodeXForms[i]->getName();
 951       OS << '\n';
 952
 953       std::string ClassName = CGP.getSDNodeInfo(SDNode).getSDClassName();
 954       if (ClassName == "SDNode")
 955         OS << "    SDNode *N = V.getNode();\n";
 956       else
 957         OS << "    " << ClassName << " *N = cast<" << ClassName
 958            << ">(V.getNode());\n";
 959       OS << Code << "\n  }\n";
 960     }
 961     OS << "  }\n";
 962     OS << "}\n";
 963     EndEmitFunction(OS);
 964   }
 965 }
 966
 967 static void BuildHistogram(const Matcher *M, std::vector<unsigned> &OpcodeFreq){
 968   for (; M != nullptr; M = M->getNext()) {
 969     // Count this node.
 970     if (unsigned(M->getKind()) >= OpcodeFreq.size())
 971       OpcodeFreq.resize(M->getKind()+1);
 972     OpcodeFreq[M->getKind()]++;
 973
 974     // Handle recursive nodes.
 975     if (const ScopeMatcher *SM = dyn_cast<ScopeMatcher>(M)) {
 976       for (unsigned i = 0, e = SM->getNumChildren(); i != e; ++i)
 977         BuildHistogram(SM->getChild(i), OpcodeFreq);
 978     } else if (const SwitchOpcodeMatcher *SOM =
 979                  dyn_cast<SwitchOpcodeMatcher>(M)) {
 980       for (unsigned i = 0, e = SOM->getNumCases(); i != e; ++i)
 981         BuildHistogram(SOM->getCaseMatcher(i), OpcodeFreq);
 982     } else if (const SwitchTypeMatcher *STM = dyn_cast<SwitchTypeMatcher>(M)) {
 983       for (unsigned i = 0, e = STM->getNumCases(); i != e; ++i)
 984         BuildHistogram(STM->getCaseMatcher(i), OpcodeFreq);
 985     }
 986   }
 987 }
 988
 989 static StringRef getOpcodeString(Matcher::KindTy Kind) {
 990   switch (Kind) {
 991   case Matcher::Scope: return "OPC_Scope"; break;
 992   case Matcher::RecordNode: return "OPC_RecordNode"; break;
 993   case Matcher::RecordChild: return "OPC_RecordChild"; break;
 994   case Matcher::RecordMemRef: return "OPC_RecordMemRef"; break;
 995   case Matcher::CaptureGlueInput: return "OPC_CaptureGlueInput"; break;
 996   case Matcher::MoveChild: return "OPC_MoveChild"; break;
 997   case Matcher::MoveParent: return "OPC_MoveParent"; break;
 998   case Matcher::CheckSame: return "OPC_CheckSame"; break;
 999   case Matcher::CheckChildSame: return "OPC_CheckChildSame"; break;
1000   case Matcher::CheckPatternPredicate:
1001     return "OPC_CheckPatternPredicate"; break;
1002   case Matcher::CheckPredicate: return "OPC_CheckPredicate"; break;
1003   case Matcher::CheckOpcode: return "OPC_CheckOpcode"; break;
1004   case Matcher::SwitchOpcode: return "OPC_SwitchOpcode"; break;
1005   case Matcher::CheckType: return "OPC_CheckType"; break;
1006   case Matcher::SwitchType: return "OPC_SwitchType"; break;
1007   case Matcher::CheckChildType: return "OPC_CheckChildType"; break;
1008   case Matcher::CheckInteger: return "OPC_CheckInteger"; break;
1009   case Matcher::CheckChildInteger: return "OPC_CheckChildInteger"; break;
1010   case Matcher::CheckCondCode: return "OPC_CheckCondCode"; break;
1011   case Matcher::CheckChild2CondCode: return "OPC_CheckChild2CondCode"; break;
1012   case Matcher::CheckValueType: return "OPC_CheckValueType"; break;
1013   case Matcher::CheckComplexPat: return "OPC_CheckComplexPat"; break;
1014   case Matcher::CheckAndImm: return "OPC_CheckAndImm"; break;
1015   case Matcher::CheckOrImm: return "OPC_CheckOrImm"; break;
1016   case Matcher::CheckFoldableChainNode:
1017     return "OPC_CheckFoldableChainNode"; break;
1018   case Matcher::CheckImmAllOnesV: return "OPC_CheckImmAllOnesV"; break;
1019   case Matcher::CheckImmAllZerosV: return "OPC_CheckImmAllZerosV"; break;
1020   case Matcher::EmitInteger: return "OPC_EmitInteger"; break;
1021   case Matcher::EmitStringInteger: return "OPC_EmitStringInteger"; break;
1022   case Matcher::EmitRegister: return "OPC_EmitRegister"; break;
1023   case Matcher::EmitConvertToTarget: return "OPC_EmitConvertToTarget"; break;
1024   case Matcher::EmitMergeInputChains: return "OPC_EmitMergeInputChains"; break;
1025   case Matcher::EmitCopyToReg: return "OPC_EmitCopyToReg"; break;
1026   case Matcher::EmitNode: return "OPC_EmitNode"; break;
1027   case Matcher::MorphNodeTo: return "OPC_MorphNodeTo"; break;
1028   case Matcher::EmitNodeXForm: return "OPC_EmitNodeXForm"; break;
1029   case Matcher::CompleteMatch: return "OPC_CompleteMatch"; break;
1030   }
1031
1032   llvm_unreachable("Unhandled opcode?");
1033 }
1034
1035 void MatcherTableEmitter::EmitHistogram(const Matcher *M,
1036                                         raw_ostream &OS) {
1037   if (OmitComments)
1038     return;
1039
1040   std::vector<unsigned> OpcodeFreq;
1041   BuildHistogram(M, OpcodeFreq);
1042
1043   OS << "  // Opcode Histogram:\n";
1044   for (unsigned i = 0, e = OpcodeFreq.size(); i != e; ++i) {
1045     OS << "  // #"
1046        << left_justify(getOpcodeString((Matcher::KindTy)i), HistOpcWidth)
1047        << " = " << OpcodeFreq[i] << '\n';
1048   }
1049   OS << '\n';
1050 }
1051
1052
1053 void llvm::EmitMatcherTable(const Matcher *TheMatcher,
1054                             const CodeGenDAGPatterns &CGP,
1055                             raw_ostream &OS) {
1056   OS << "#if defined(GET_DAGISEL_DECL) && defined(GET_DAGISEL_BODY)\n";
1057   OS << "#error GET_DAGISEL_DECL and GET_DAGISEL_BODY cannot be both defined, ";
1058   OS << "undef both for inline definitions\n";
1059   OS << "#endif\n\n";
1060
1061   // Emit a check for omitted class name.
1062   OS << "#ifdef GET_DAGISEL_BODY\n";
1063   OS << "#define LOCAL_DAGISEL_STRINGIZE(X) LOCAL_DAGISEL_STRINGIZE_(X)\n";
1064   OS << "#define LOCAL_DAGISEL_STRINGIZE_(X) #X\n";
1065   OS << "static_assert(sizeof(LOCAL_DAGISEL_STRINGIZE(GET_DAGISEL_BODY)) > 1,"
1066         "\n";
1067   OS << "   \"GET_DAGISEL_BODY is empty: it should be defined with the class "
1068         "name\");\n";
1069   OS << "#undef LOCAL_DAGISEL_STRINGIZE_\n";
1070   OS << "#undef LOCAL_DAGISEL_STRINGIZE\n";
1071   OS << "#endif\n\n";
1072
1073   OS << "#if !defined(GET_DAGISEL_DECL) && !defined(GET_DAGISEL_BODY)\n";
1074   OS << "#define DAGISEL_INLINE 1\n";
1075   OS << "#else\n";
1076   OS << "#define DAGISEL_INLINE 0\n";
1077   OS << "#endif\n\n";
1078
1079   OS << "#if !DAGISEL_INLINE\n";
1080   OS << "#define DAGISEL_CLASS_COLONCOLON GET_DAGISEL_BODY ::\n";
1081   OS << "#else\n";
1082   OS << "#define DAGISEL_CLASS_COLONCOLON\n";
1083   OS << "#endif\n\n";
1084
1085   BeginEmitFunction(OS, "void", "SelectCode(SDNode *N)", false/*AddOverride*/);
1086   MatcherTableEmitter MatcherEmitter(CGP);
1087
1088   OS << "{\n";
1089   OS << "  // Some target values are emitted as 2 bytes, TARGET_VAL handles\n";
1090   OS << "  // this.\n";
1091   OS << "  #define TARGET_VAL(X) X & 255, unsigned(X) >> 8\n";
1092   OS << "  static const unsigned char MatcherTable[] = {\n";
1093   unsigned TotalSize = MatcherEmitter.EmitMatcherList(TheMatcher, 1, 0, OS);
1094   OS << "    0\n  }; // Total Array size is " << (TotalSize+1) << " bytes\n\n";
1095
1096   MatcherEmitter.EmitHistogram(TheMatcher, OS);
1097
1098   OS << "  #undef TARGET_VAL\n";
1099   OS << "  SelectCodeCommon(N, MatcherTable,sizeof(MatcherTable));\n";
1100   OS << "}\n";
1101   EndEmitFunction(OS);
1102
1103   // Next up, emit the function for node and pattern predicates:
1104   MatcherEmitter.EmitPredicateFunctions(OS);
1105
1106   if (InstrumentCoverage)
1107     MatcherEmitter.EmitPatternMatchTable(OS);
1108
1109   // Clean up the preprocessor macros.
1110   OS << "\n";
1111   OS << "#ifdef DAGISEL_INLINE\n";
1112   OS << "#undef DAGISEL_INLINE\n";
1113   OS << "#endif\n";
1114   OS << "#ifdef DAGISEL_CLASS_COLONCOLON\n";
1115   OS << "#undef DAGISEL_CLASS_COLONCOLON\n";
1116   OS << "#endif\n";
1117   OS << "#ifdef GET_DAGISEL_DECL\n";
1118   OS << "#undef GET_DAGISEL_DECL\n";
1119   OS << "#endif\n";
1120   OS << "#ifdef GET_DAGISEL_BODY\n";
1121   OS << "#undef GET_DAGISEL_BODY\n";
1122   OS << "#endif\n";
1123 }