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