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