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