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 a matcher.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "DAGISelMatcher.h"
  15 #include "CodeGenDAGPatterns.h"
  16 #include "Record.h"
  17 #include "llvm/ADT/DenseMap.h"
  18 #include "llvm/ADT/SmallString.h"
  19 #include "llvm/ADT/StringMap.h"
  20 #include "llvm/Support/FormattedStream.h"
  21 using namespace llvm;
  22
  23 enum {
  24   CommentIndent = 30
  25 };
  26
  27 /// ClassifyInt - Classify an integer by size, return '1','2','4','8' if this
  28 /// fits in 1, 2, 4, or 8 sign extended bytes.
  29 static char ClassifyInt(int64_t Val) {
  30   if (Val == int8_t(Val))  return '1';
  31   if (Val == int16_t(Val)) return '2';
  32   if (Val == int32_t(Val)) return '4';
  33   return '8';
  34 }
  35
  36 /// EmitInt - Emit the specified integer, returning the number of bytes emitted.
  37 static unsigned EmitInt(int64_t Val, formatted_raw_ostream &OS) {
  38   unsigned BytesEmitted = 1;
  39   OS << (int)(unsigned char)Val << ", ";
  40   if (Val == int8_t(Val)) {
  41     OS << '\n';
  42     return BytesEmitted;
  43   }
  44
  45   OS << (int)(unsigned char)(Val >> 8) << ", ";
  46   ++BytesEmitted;
  47
  48   if (Val != int16_t(Val)) {
  49     OS << (int)(unsigned char)(Val >> 16) << ", "
  50        << (int)(unsigned char)(Val >> 24) << ", ";
  51     BytesEmitted += 2;
  52
  53     if (Val != int32_t(Val)) {
  54       OS << (int)(unsigned char)(Val >> 32) << ", "
  55          << (int)(unsigned char)(Val >> 40) << ", "
  56          << (int)(unsigned char)(Val >> 48) << ", "
  57          << (int)(unsigned char)(Val >> 56) << ", ";
  58       BytesEmitted += 4;
  59     }
  60   }
  61
  62   OS.PadToColumn(CommentIndent) << "// " << Val << " aka 0x";
  63   OS.write_hex(Val) << '\n';
  64   return BytesEmitted;
  65 }
  66
  67 namespace {
  68 class MatcherTableEmitter {
  69   StringMap<unsigned> NodePredicateMap, PatternPredicateMap;
  70   std::vector<std::string> NodePredicates, PatternPredicates;
  71
  72   DenseMap<const ComplexPattern*, unsigned> ComplexPatternMap;
  73   std::vector<const ComplexPattern*> ComplexPatterns;
  74
  75
  76   DenseMap<Record*, unsigned> NodeXFormMap;
  77   std::vector<const Record*> NodeXForms;
  78
  79   // Per opcode frequence count.
  80   std::vector<unsigned> Histogram;
  81 public:
  82   MatcherTableEmitter() {}
  83
  84   unsigned EmitMatcherList(const Matcher *N, unsigned Indent,
  85                            unsigned StartIdx, formatted_raw_ostream &OS);
  86
  87   void EmitPredicateFunctions(formatted_raw_ostream &OS);
  88
  89   void EmitHistogram(formatted_raw_ostream &OS);
  90 private:
  91   unsigned EmitMatcher(const Matcher *N, unsigned Indent, unsigned CurrentIdx,
  92                        formatted_raw_ostream &OS);
  93
  94   unsigned getNodePredicate(StringRef PredName) {
  95     unsigned &Entry = NodePredicateMap[PredName];
  96     if (Entry == 0) {
  97       NodePredicates.push_back(PredName.str());
  98       Entry = NodePredicates.size();
  99     }
 100     return Entry-1;
 101   }
 102   unsigned getPatternPredicate(StringRef PredName) {
 103     unsigned &Entry = PatternPredicateMap[PredName];
 104     if (Entry == 0) {
 105       PatternPredicates.push_back(PredName.str());
 106       Entry = PatternPredicates.size();
 107     }
 108     return Entry-1;
 109   }
 110
 111   unsigned getComplexPat(const ComplexPattern &P) {
 112     unsigned &Entry = ComplexPatternMap[&P];
 113     if (Entry == 0) {
 114       ComplexPatterns.push_back(&P);
 115       Entry = ComplexPatterns.size();
 116     }
 117     return Entry-1;
 118   }
 119
 120   unsigned getNodeXFormID(Record *Rec) {
 121     unsigned &Entry = NodeXFormMap[Rec];
 122     if (Entry == 0) {
 123       NodeXForms.push_back(Rec);
 124       Entry = NodeXForms.size();
 125     }
 126     return Entry-1;
 127   }
 128
 129 };
 130 } // end anonymous namespace.
 131
 132 static unsigned GetVBRSize(unsigned Val) {
 133   if (Val <= 127) return 1;
 134
 135   unsigned NumBytes = 0;
 136   while (Val >= 128) {
 137     Val >>= 7;
 138     ++NumBytes;
 139   }
 140   return NumBytes+1;
 141 }
 142
 143 /// EmitVBRValue - Emit the specified value as a VBR, returning the number of
 144 /// bytes emitted.
 145 static unsigned EmitVBRValue(unsigned Val, raw_ostream &OS) {
 146   if (Val <= 127) {
 147     OS << Val << ", ";
 148     return 1;
 149   }
 150
 151   unsigned InVal = Val;
 152   unsigned NumBytes = 0;
 153   while (Val >= 128) {
 154     OS << (Val&127) << "|128,";
 155     Val >>= 7;
 156     ++NumBytes;
 157   }
 158   OS << Val << "/*" << InVal << "*/, ";
 159   return NumBytes+1;
 160 }
 161
 162 /// EmitMatcherOpcodes - Emit bytes for the specified matcher and return
 163 /// the number of bytes emitted.
 164 unsigned MatcherTableEmitter::
 165 EmitMatcher(const Matcher *N, unsigned Indent, unsigned CurrentIdx,
 166             formatted_raw_ostream &OS) {
 167   OS.PadToColumn(Indent*2);
 168
 169   switch (N->getKind()) {
 170   case Matcher::Scope: {
 171     const ScopeMatcher *SM = cast<ScopeMatcher>(N);
 172     assert(SM->getNext() == 0 && "Shouldn't have next after scope");
 173
 174     unsigned StartIdx = CurrentIdx;
 175
 176     // Emit all of the children.
 177     for (unsigned i = 0, e = SM->getNumChildren(); i != e; ++i) {
 178       if (i == 0) {
 179         OS << "OPC_Scope, ";
 180         ++CurrentIdx;
 181       } else {
 182         OS << "/*" << CurrentIdx << "*/";
 183         OS.PadToColumn(Indent*2) << "/*Scope*/ ";
 184       }
 185
 186       // We need to encode the child and the offset of the failure code before
 187       // emitting either of them.  Handle this by buffering the output into a
 188       // string while we get the size.  Unfortunately, the offset of the
 189       // children depends on the VBR size of the child, so for large children we
 190       // have to iterate a bit.
 191       SmallString<128> TmpBuf;
 192       unsigned ChildSize = 0;
 193       unsigned VBRSize = 0;
 194       do {
 195         VBRSize = GetVBRSize(ChildSize);
 196
 197         TmpBuf.clear();
 198         raw_svector_ostream OS(TmpBuf);
 199         formatted_raw_ostream FOS(OS);
 200         ChildSize = EmitMatcherList(cast<ScopeMatcher>(N)->getChild(i),
 201                                    Indent+1, CurrentIdx+VBRSize, FOS);
 202       } while (GetVBRSize(ChildSize) != VBRSize);
 203
 204       assert(ChildSize != 0 && "Should not have a zero-sized child!");
 205
 206       CurrentIdx += EmitVBRValue(ChildSize, OS);
 207       OS << "/*->" << CurrentIdx+ChildSize << "*/";
 208
 209       if (i == 0)
 210         OS.PadToColumn(CommentIndent) << "// " << SM->getNumChildren()
 211           << " children in Scope";
 212
 213       OS << '\n' << TmpBuf.str();
 214       CurrentIdx += ChildSize;
 215     }
 216
 217     // Emit a zero as a sentinel indicating end of 'Scope'.
 218     OS << "/*" << CurrentIdx << "*/";
 219     OS.PadToColumn(Indent*2) << "0, /*End of Scope*/\n";
 220     return CurrentIdx - StartIdx + 1;
 221   }
 222
 223   case Matcher::RecordNode:
 224     OS << "OPC_RecordNode,";
 225     OS.PadToColumn(CommentIndent) << "// "
 226        << cast<RecordMatcher>(N)->getWhatFor() << '\n';
 227     return 1;
 228
 229   case Matcher::RecordChild:
 230     OS << "OPC_RecordChild" << cast<RecordChildMatcher>(N)->getChildNo()
 231        << ',';
 232     OS.PadToColumn(CommentIndent) << "// "
 233       << cast<RecordChildMatcher>(N)->getWhatFor() << '\n';
 234     return 1;
 235
 236   case Matcher::RecordMemRef:
 237     OS << "OPC_RecordMemRef,\n";
 238     return 1;
 239
 240   case Matcher::CaptureFlagInput:
 241     OS << "OPC_CaptureFlagInput,\n";
 242     return 1;
 243
 244   case Matcher::MoveChild:
 245     OS << "OPC_MoveChild, " << cast<MoveChildMatcher>(N)->getChildNo() << ",\n";
 246     return 2;
 247
 248   case Matcher::MoveParent:
 249     OS << "OPC_MoveParent,\n";
 250     return 1;
 251
 252   case Matcher::CheckSame:
 253     OS << "OPC_CheckSame, "
 254        << cast<CheckSameMatcher>(N)->getMatchNumber() << ",\n";
 255     return 2;
 256
 257   case Matcher::CheckPatternPredicate: {
 258     StringRef Pred = cast<CheckPatternPredicateMatcher>(N)->getPredicate();
 259     OS << "OPC_CheckPatternPredicate, " << getPatternPredicate(Pred) << ',';
 260     OS.PadToColumn(CommentIndent) << "// " << Pred << '\n';
 261     return 2;
 262   }
 263   case Matcher::CheckPredicate: {
 264     StringRef Pred = cast<CheckPredicateMatcher>(N)->getPredicateName();
 265     OS << "OPC_CheckPredicate, " << getNodePredicate(Pred) << ',';
 266     OS.PadToColumn(CommentIndent) << "// " << Pred << '\n';
 267     return 2;
 268   }
 269
 270   case Matcher::CheckOpcode:
 271     OS << "OPC_CheckOpcode, "
 272        << cast<CheckOpcodeMatcher>(N)->getOpcode().getEnumName() << ",\n";
 273     return 2;
 274
 275   case Matcher::CheckMultiOpcode: {
 276     const CheckMultiOpcodeMatcher *CMO = cast<CheckMultiOpcodeMatcher>(N);
 277     OS << "OPC_CheckMultiOpcode, " << CMO->getNumOpcodes() << ", ";
 278     for (unsigned i = 0, e = CMO->getNumOpcodes(); i != e; ++i)
 279       OS << CMO->getOpcode(i).getEnumName() << ", ";
 280     OS << '\n';
 281     return 2 + CMO->getNumOpcodes();
 282   }
 283
 284   case Matcher::CheckType:
 285     OS << "OPC_CheckType, "
 286        << getEnumName(cast<CheckTypeMatcher>(N)->getType()) << ",\n";
 287     return 2;
 288   case Matcher::CheckChildType:
 289     OS << "OPC_CheckChild"
 290        << cast<CheckChildTypeMatcher>(N)->getChildNo() << "Type, "
 291        << getEnumName(cast<CheckChildTypeMatcher>(N)->getType()) << ",\n";
 292     return 2;
 293
 294   case Matcher::CheckInteger: {
 295     int64_t Val = cast<CheckIntegerMatcher>(N)->getValue();
 296     OS << "OPC_CheckInteger" << ClassifyInt(Val) << ", ";
 297     return EmitInt(Val, OS)+1;
 298   }
 299   case Matcher::CheckCondCode:
 300     OS << "OPC_CheckCondCode, ISD::"
 301        << cast<CheckCondCodeMatcher>(N)->getCondCodeName() << ",\n";
 302     return 2;
 303
 304   case Matcher::CheckValueType:
 305     OS << "OPC_CheckValueType, MVT::"
 306        << cast<CheckValueTypeMatcher>(N)->getTypeName() << ",\n";
 307     return 2;
 308
 309   case Matcher::CheckComplexPat: {
 310     const ComplexPattern &Pattern =
 311       cast<CheckComplexPatMatcher>(N)->getPattern();
 312     OS << "OPC_CheckComplexPat, " << getComplexPat(Pattern) << ',';
 313     OS.PadToColumn(CommentIndent) << "// " << Pattern.getSelectFunc();
 314     OS << ": " << Pattern.getNumOperands() << " operands";
 315     if (Pattern.hasProperty(SDNPHasChain))
 316       OS << " + chain result and input";
 317     OS << '\n';
 318     return 2;
 319   }
 320
 321   case Matcher::CheckAndImm: {
 322     int64_t Val = cast<CheckAndImmMatcher>(N)->getValue();
 323     OS << "OPC_CheckAndImm" << ClassifyInt(Val) << ", ";
 324     return EmitInt(Val, OS)+1;
 325   }
 326
 327   case Matcher::CheckOrImm: {
 328     int64_t Val = cast<CheckOrImmMatcher>(N)->getValue();
 329     OS << "OPC_CheckOrImm" << ClassifyInt(Val) << ", ";
 330     return EmitInt(Val, OS)+1;
 331   }
 332   case Matcher::CheckFoldableChainNode:
 333     OS << "OPC_CheckFoldableChainNode,\n";
 334     return 1;
 335   case Matcher::CheckChainCompatible:
 336     OS << "OPC_CheckChainCompatible, "
 337        << cast<CheckChainCompatibleMatcher>(N)->getPreviousOp() << ",\n";
 338     return 2;
 339
 340   case Matcher::EmitInteger: {
 341     int64_t Val = cast<EmitIntegerMatcher>(N)->getValue();
 342     OS << "OPC_EmitInteger" << ClassifyInt(Val) << ", "
 343        << getEnumName(cast<EmitIntegerMatcher>(N)->getVT()) << ", ";
 344     return EmitInt(Val, OS)+2;
 345   }
 346   case Matcher::EmitStringInteger: {
 347     const std::string &Val = cast<EmitStringIntegerMatcher>(N)->getValue();
 348     // These should always fit into one byte.
 349     OS << "OPC_EmitInteger1, "
 350       << getEnumName(cast<EmitStringIntegerMatcher>(N)->getVT()) << ", "
 351       << Val << ",\n";
 352     return 3;
 353   }
 354
 355   case Matcher::EmitRegister:
 356     OS << "OPC_EmitRegister, "
 357        << getEnumName(cast<EmitRegisterMatcher>(N)->getVT()) << ", ";
 358     if (Record *R = cast<EmitRegisterMatcher>(N)->getReg())
 359       OS << getQualifiedName(R) << ",\n";
 360     else
 361       OS << "0 /*zero_reg*/,\n";
 362     return 3;
 363
 364   case Matcher::EmitConvertToTarget:
 365     OS << "OPC_EmitConvertToTarget, "
 366        << cast<EmitConvertToTargetMatcher>(N)->getSlot() << ",\n";
 367     return 2;
 368
 369   case Matcher::EmitMergeInputChains: {
 370     const EmitMergeInputChainsMatcher *MN =
 371       cast<EmitMergeInputChainsMatcher>(N);
 372     OS << "OPC_EmitMergeInputChains, " << MN->getNumNodes() << ", ";
 373     for (unsigned i = 0, e = MN->getNumNodes(); i != e; ++i)
 374       OS << MN->getNode(i) << ", ";
 375     OS << '\n';
 376     return 2+MN->getNumNodes();
 377   }
 378   case Matcher::EmitCopyToReg:
 379     OS << "OPC_EmitCopyToReg, "
 380        << cast<EmitCopyToRegMatcher>(N)->getSrcSlot() << ", "
 381        << getQualifiedName(cast<EmitCopyToRegMatcher>(N)->getDestPhysReg())
 382        << ",\n";
 383     return 3;
 384   case Matcher::EmitNodeXForm: {
 385     const EmitNodeXFormMatcher *XF = cast<EmitNodeXFormMatcher>(N);
 386     OS << "OPC_EmitNodeXForm, " << getNodeXFormID(XF->getNodeXForm()) << ", "
 387        << XF->getSlot() << ',';
 388     OS.PadToColumn(CommentIndent) << "// "<<XF->getNodeXForm()->getName()<<'\n';
 389     return 3;
 390   }
 391
 392   case Matcher::EmitNode:
 393   case Matcher::MorphNodeTo: {
 394     const EmitNodeMatcherCommon *EN = cast<EmitNodeMatcherCommon>(N);
 395     OS << (isa<EmitNodeMatcher>(EN) ? "OPC_EmitNode" : "OPC_MorphNodeTo");
 396     OS << ", TARGET_OPCODE(" << EN->getOpcodeName() << "), 0";
 397
 398     if (EN->hasChain())   OS << "|OPFL_Chain";
 399     if (EN->hasInFlag())  OS << "|OPFL_FlagInput";
 400     if (EN->hasOutFlag()) OS << "|OPFL_FlagOutput";
 401     if (EN->hasMemRefs()) OS << "|OPFL_MemRefs";
 402     if (EN->getNumFixedArityOperands() != -1)
 403       OS << "|OPFL_Variadic" << EN->getNumFixedArityOperands();
 404     OS << ",\n";
 405
 406     OS.PadToColumn(Indent*2+4) << EN->getNumVTs() << "/*#VTs*/, ";
 407     for (unsigned i = 0, e = EN->getNumVTs(); i != e; ++i)
 408       OS << getEnumName(EN->getVT(i)) << ", ";
 409
 410     OS << EN->getNumOperands() << "/*#Ops*/, ";
 411     unsigned NumOperandBytes = 0;
 412     for (unsigned i = 0, e = EN->getNumOperands(); i != e; ++i) {
 413       // We emit the operand numbers in VBR encoded format, in case the number
 414       // is too large to represent with a byte.
 415       NumOperandBytes += EmitVBRValue(EN->getOperand(i), OS);
 416     }
 417
 418     // Print the result #'s for EmitNode.
 419     if (const EmitNodeMatcher *E = dyn_cast<EmitNodeMatcher>(EN)) {
 420       if (unsigned NumResults = EN->getNumNonChainFlagVTs()) {
 421         OS.PadToColumn(CommentIndent) << "// Results = ";
 422         unsigned First = E->getFirstResultSlot();
 423         for (unsigned i = 0; i != NumResults; ++i)
 424           OS << "#" << First+i << " ";
 425       }
 426     }
 427     OS << '\n';
 428
 429     if (const MorphNodeToMatcher *SNT = dyn_cast<MorphNodeToMatcher>(N)) {
 430       OS.PadToColumn(Indent*2) << "// Src: "
 431       << *SNT->getPattern().getSrcPattern() << '\n';
 432       OS.PadToColumn(Indent*2) << "// Dst: "
 433       << *SNT->getPattern().getDstPattern() << '\n';
 434
 435     }
 436
 437     return 6+EN->getNumVTs()+NumOperandBytes;
 438   }
 439   case Matcher::MarkFlagResults: {
 440     const MarkFlagResultsMatcher *CFR = cast<MarkFlagResultsMatcher>(N);
 441     OS << "OPC_MarkFlagResults, " << CFR->getNumNodes() << ", ";
 442     unsigned NumOperandBytes = 0;
 443     for (unsigned i = 0, e = CFR->getNumNodes(); i != e; ++i)
 444       NumOperandBytes += EmitVBRValue(CFR->getNode(i), OS);
 445     OS << '\n';
 446     return 2+NumOperandBytes;
 447   }
 448   case Matcher::CompleteMatch: {
 449     const CompleteMatchMatcher *CM = cast<CompleteMatchMatcher>(N);
 450     OS << "OPC_CompleteMatch, " << CM->getNumResults() << ", ";
 451     unsigned NumResultBytes = 0;
 452     for (unsigned i = 0, e = CM->getNumResults(); i != e; ++i)
 453       NumResultBytes += EmitVBRValue(CM->getResult(i), OS);
 454     OS << '\n';
 455     OS.PadToColumn(Indent*2) << "// Src: "
 456       << *CM->getPattern().getSrcPattern() << '\n';
 457     OS.PadToColumn(Indent*2) << "// Dst: "
 458       << *CM->getPattern().getDstPattern() << '\n';
 459     return 2 + NumResultBytes;
 460   }
 461   }
 462   assert(0 && "Unreachable");
 463   return 0;
 464 }
 465
 466 /// EmitMatcherList - Emit the bytes for the specified matcher subtree.
 467 unsigned MatcherTableEmitter::
 468 EmitMatcherList(const Matcher *N, unsigned Indent, unsigned CurrentIdx,
 469                 formatted_raw_ostream &OS) {
 470   unsigned Size = 0;
 471   while (N) {
 472     if (unsigned(N->getKind()) >= Histogram.size())
 473       Histogram.resize(N->getKind()+1);
 474     Histogram[N->getKind()]++;
 475
 476     OS << "/*" << CurrentIdx << "*/";
 477     unsigned MatcherSize = EmitMatcher(N, Indent, CurrentIdx, OS);
 478     Size += MatcherSize;
 479     CurrentIdx += MatcherSize;
 480
 481     // If there are other nodes in this list, iterate to them, otherwise we're
 482     // done.
 483     N = N->getNext();
 484   }
 485   return Size;
 486 }
 487
 488 void MatcherTableEmitter::EmitPredicateFunctions(formatted_raw_ostream &OS) {
 489   // FIXME: Don't build off the DAGISelEmitter's predicates, emit them directly
 490   // here into the case stmts.
 491
 492   // Emit pattern predicates.
 493   OS << "bool CheckPatternPredicate(unsigned PredNo) const {\n";
 494   OS << "  switch (PredNo) {\n";
 495   OS << "  default: assert(0 && \"Invalid predicate in table?\");\n";
 496   for (unsigned i = 0, e = PatternPredicates.size(); i != e; ++i)
 497     OS << "  case " << i << ": return "  << PatternPredicates[i] << ";\n";
 498   OS << "  }\n";
 499   OS << "}\n\n";
 500
 501   // Emit Node predicates.
 502   OS << "bool CheckNodePredicate(SDNode *N, unsigned PredNo) const {\n";
 503   OS << "  switch (PredNo) {\n";
 504   OS << "  default: assert(0 && \"Invalid predicate in table?\");\n";
 505   for (unsigned i = 0, e = NodePredicates.size(); i != e; ++i)
 506     OS << "  case " << i << ": return "  << NodePredicates[i] << "(N);\n";
 507   OS << "  }\n";
 508   OS << "}\n\n";
 509
 510   // Emit CompletePattern matchers.
 511   // FIXME: This should be const.
 512   OS << "bool CheckComplexPattern(SDNode *Root, SDValue N,\n";
 513   OS << "      unsigned PatternNo, SmallVectorImpl<SDValue> &Result) {\n";
 514   OS << "  switch (PatternNo) {\n";
 515   OS << "  default: assert(0 && \"Invalid pattern # in table?\");\n";
 516   for (unsigned i = 0, e = ComplexPatterns.size(); i != e; ++i) {
 517     const ComplexPattern &P = *ComplexPatterns[i];
 518     unsigned NumOps = P.getNumOperands();
 519
 520     if (P.hasProperty(SDNPHasChain))
 521       ++NumOps;  // Get the chained node too.
 522
 523     OS << "  case " << i << ":\n";
 524     OS << "    Result.resize(Result.size()+" << NumOps << ");\n";
 525     OS << "    return "  << P.getSelectFunc();
 526
 527     // FIXME: Temporary hack until old isel dies.
 528     if (P.hasProperty(SDNPHasChain))
 529       OS << "XXX";
 530
 531     OS << "(Root, N";
 532     for (unsigned i = 0; i != NumOps; ++i)
 533       OS << ", Result[Result.size()-" << (NumOps-i) << ']';
 534     OS << ");\n";
 535   }
 536   OS << "  }\n";
 537   OS << "}\n\n";
 538
 539   // Emit SDNodeXForm handlers.
 540   // FIXME: This should be const.
 541   OS << "SDValue RunSDNodeXForm(SDValue V, unsigned XFormNo) {\n";
 542   OS << "  switch (XFormNo) {\n";
 543   OS << "  default: assert(0 && \"Invalid xform # in table?\");\n";
 544
 545   // FIXME: The node xform could take SDValue's instead of SDNode*'s.
 546   for (unsigned i = 0, e = NodeXForms.size(); i != e; ++i)
 547     OS << "  case " << i << ": return Transform_" << NodeXForms[i]->getName()
 548        << "(V.getNode());\n";
 549   OS << "  }\n";
 550   OS << "}\n\n";
 551 }
 552
 553 void MatcherTableEmitter::EmitHistogram(formatted_raw_ostream &OS) {
 554   OS << "  // Opcode Histogram:\n";
 555   for (unsigned i = 0, e = Histogram.size(); i != e; ++i) {
 556     OS << "  // #";
 557     switch ((Matcher::KindTy)i) {
 558     case Matcher::Scope: OS << "OPC_Scope"; break;
 559     case Matcher::RecordNode: OS << "OPC_RecordNode"; break;
 560     case Matcher::RecordChild: OS << "OPC_RecordChild"; break;
 561     case Matcher::RecordMemRef: OS << "OPC_RecordMemRef"; break;
 562     case Matcher::CaptureFlagInput: OS << "OPC_CaptureFlagInput"; break;
 563     case Matcher::MoveChild: OS << "OPC_MoveChild"; break;
 564     case Matcher::MoveParent: OS << "OPC_MoveParent"; break;
 565     case Matcher::CheckSame: OS << "OPC_CheckSame"; break;
 566     case Matcher::CheckPatternPredicate:
 567       OS << "OPC_CheckPatternPredicate"; break;
 568     case Matcher::CheckPredicate: OS << "OPC_CheckPredicate"; break;
 569     case Matcher::CheckOpcode: OS << "OPC_CheckOpcode"; break;
 570     case Matcher::CheckMultiOpcode: OS << "OPC_CheckMultiOpcode"; break;
 571     case Matcher::CheckType: OS << "OPC_CheckType"; break;
 572     case Matcher::CheckChildType: OS << "OPC_CheckChildType"; break;
 573     case Matcher::CheckInteger: OS << "OPC_CheckInteger"; break;
 574     case Matcher::CheckCondCode: OS << "OPC_CheckCondCode"; break;
 575     case Matcher::CheckValueType: OS << "OPC_CheckValueType"; break;
 576     case Matcher::CheckComplexPat: OS << "OPC_CheckComplexPat"; break;
 577     case Matcher::CheckAndImm: OS << "OPC_CheckAndImm"; break;
 578     case Matcher::CheckOrImm: OS << "OPC_CheckOrImm"; break;
 579     case Matcher::CheckFoldableChainNode:
 580       OS << "OPC_CheckFoldableChainNode"; break;
 581     case Matcher::CheckChainCompatible: OS << "OPC_CheckChainCompatible"; break;
 582     case Matcher::EmitInteger: OS << "OPC_EmitInteger"; break;
 583     case Matcher::EmitStringInteger: OS << "OPC_EmitStringInteger"; break;
 584     case Matcher::EmitRegister: OS << "OPC_EmitRegister"; break;
 585     case Matcher::EmitConvertToTarget: OS << "OPC_EmitConvertToTarget"; break;
 586     case Matcher::EmitMergeInputChains: OS << "OPC_EmitMergeInputChains"; break;
 587     case Matcher::EmitCopyToReg: OS << "OPC_EmitCopyToReg"; break;
 588     case Matcher::EmitNode: OS << "OPC_EmitNode"; break;
 589     case Matcher::MorphNodeTo: OS << "OPC_MorphNodeTo"; break;
 590     case Matcher::EmitNodeXForm: OS << "OPC_EmitNodeXForm"; break;
 591     case Matcher::MarkFlagResults: OS << "OPC_MarkFlagResults"; break;
 592     case Matcher::CompleteMatch: OS << "OPC_CompleteMatch"; break;
 593     }
 594
 595     OS.PadToColumn(40) << " = " << Histogram[i] << '\n';
 596   }
 597   OS << '\n';
 598 }
 599
 600
 601 void llvm::EmitMatcherTable(const Matcher *TheMatcher, raw_ostream &O) {
 602   formatted_raw_ostream OS(O);
 603
 604   OS << "// The main instruction selector code.\n";
 605   OS << "SDNode *SelectCode(SDNode *N) {\n";
 606
 607   MatcherTableEmitter MatcherEmitter;
 608
 609   OS << "  // Opcodes are emitted as 2 bytes, TARGET_OPCODE handles this.\n";
 610   OS << "  #define TARGET_OPCODE(X) X & 255, unsigned(X) >> 8\n";
 611   OS << "  static const unsigned char MatcherTable[] = {\n";
 612   unsigned TotalSize = MatcherEmitter.EmitMatcherList(TheMatcher, 5, 0, OS);
 613   OS << "    0\n  }; // Total Array size is " << (TotalSize+1) << " bytes\n\n";
 614
 615   MatcherEmitter.EmitHistogram(OS);
 616
 617   OS << "  #undef TARGET_OPCODE\n";
 618   OS << "  return SelectCodeCommon(N, MatcherTable,sizeof(MatcherTable));\n}\n";
 619   OS << "\n";
 620
 621   // Next up, emit the function for node and pattern predicates:
 622   MatcherEmitter.EmitPredicateFunctions(OS);
 623 }