contrib/llvm/utils/TableGen/DAGISelMatcherEmitter.cpp

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