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