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" 23using namespace llvm; 24 25enum { 26 CommentIndent = 30 27}; 28 29// To reduce generated source code size. 30static cl::opt<bool> 31OmitComments("omit-comments", cl::desc("Do not generate comments"), 32 cl::init(false)); 33 34namespace { 35class 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 55public: 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); 65private: 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 120static 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. 133static 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. 155unsigned MatcherTableEmitter:: 156EmitMatcher(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. 620unsigned MatcherTableEmitter:: 621EmitMatcherList(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 638void 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 746static 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 768void 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 824void 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} 851