AsmMatcherEmitter.cpp revision 606e8ad796f72824f5509e2657c44eca025d4baf
1//===- AsmMatcherEmitter.cpp - Generate an assembly matcher ---------------===// 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 tablegen backend emits a target specifier matcher for converting parsed 11// assembly operands in the MCInst structures. 12// 13// The input to the target specific matcher is a list of literal tokens and 14// operands. The target specific parser should generally eliminate any syntax 15// which is not relevant for matching; for example, comma tokens should have 16// already been consumed and eliminated by the parser. Most instructions will 17// end up with a single literal token (the instruction name) and some number of 18// operands. 19// 20// Some example inputs, for X86: 21// 'addl' (immediate ...) (register ...) 22// 'add' (immediate ...) (memory ...) 23// 'call' '*' %epc 24// 25// The assembly matcher is responsible for converting this input into a precise 26// machine instruction (i.e., an instruction with a well defined encoding). This 27// mapping has several properties which complicate matching: 28// 29// - It may be ambiguous; many architectures can legally encode particular 30// variants of an instruction in different ways (for example, using a smaller 31// encoding for small immediates). Such ambiguities should never be 32// arbitrarily resolved by the assembler, the assembler is always responsible 33// for choosing the "best" available instruction. 34// 35// - It may depend on the subtarget or the assembler context. Instructions 36// which are invalid for the current mode, but otherwise unambiguous (e.g., 37// an SSE instruction in a file being assembled for i486) should be accepted 38// and rejected by the assembler front end. However, if the proper encoding 39// for an instruction is dependent on the assembler context then the matcher 40// is responsible for selecting the correct machine instruction for the 41// current mode. 42// 43// The core matching algorithm attempts to exploit the regularity in most 44// instruction sets to quickly determine the set of possibly matching 45// instructions, and the simplify the generated code. Additionally, this helps 46// to ensure that the ambiguities are intentionally resolved by the user. 47// 48// The matching is divided into two distinct phases: 49// 50// 1. Classification: Each operand is mapped to the unique set which (a) 51// contains it, and (b) is the largest such subset for which a single 52// instruction could match all members. 53// 54// For register classes, we can generate these subgroups automatically. For 55// arbitrary operands, we expect the user to define the classes and their 56// relations to one another (for example, 8-bit signed immediates as a 57// subset of 32-bit immediates). 58// 59// By partitioning the operands in this way, we guarantee that for any 60// tuple of classes, any single instruction must match either all or none 61// of the sets of operands which could classify to that tuple. 62// 63// In addition, the subset relation amongst classes induces a partial order 64// on such tuples, which we use to resolve ambiguities. 65// 66// FIXME: What do we do if a crazy case shows up where this is the wrong 67// resolution? 68// 69// 2. The input can now be treated as a tuple of classes (static tokens are 70// simple singleton sets). Each such tuple should generally map to a single 71// instruction (we currently ignore cases where this isn't true, whee!!!), 72// which we can emit a simple matcher for. 73// 74//===----------------------------------------------------------------------===// 75 76#include "AsmMatcherEmitter.h" 77#include "CodeGenTarget.h" 78#include "Record.h" 79#include "llvm/ADT/OwningPtr.h" 80#include "llvm/ADT/SmallVector.h" 81#include "llvm/ADT/STLExtras.h" 82#include "llvm/ADT/StringExtras.h" 83#include "llvm/Support/CommandLine.h" 84#include "llvm/Support/Debug.h" 85#include <list> 86#include <map> 87#include <set> 88using namespace llvm; 89 90namespace { 91static cl::opt<std::string> 92MatchPrefix("match-prefix", cl::init(""), 93 cl::desc("Only match instructions with the given prefix")); 94} 95 96/// FlattenVariants - Flatten an .td file assembly string by selecting the 97/// variant at index \arg N. 98static std::string FlattenVariants(const std::string &AsmString, 99 unsigned N) { 100 StringRef Cur = AsmString; 101 std::string Res = ""; 102 103 for (;;) { 104 // Find the start of the next variant string. 105 size_t VariantsStart = 0; 106 for (size_t e = Cur.size(); VariantsStart != e; ++VariantsStart) 107 if (Cur[VariantsStart] == '{' && 108 (VariantsStart == 0 || (Cur[VariantsStart-1] != '$' && 109 Cur[VariantsStart-1] != '\\'))) 110 break; 111 112 // Add the prefix to the result. 113 Res += Cur.slice(0, VariantsStart); 114 if (VariantsStart == Cur.size()) 115 break; 116 117 ++VariantsStart; // Skip the '{'. 118 119 // Scan to the end of the variants string. 120 size_t VariantsEnd = VariantsStart; 121 unsigned NestedBraces = 1; 122 for (size_t e = Cur.size(); VariantsEnd != e; ++VariantsEnd) { 123 if (Cur[VariantsEnd] == '}' && Cur[VariantsEnd-1] != '\\') { 124 if (--NestedBraces == 0) 125 break; 126 } else if (Cur[VariantsEnd] == '{') 127 ++NestedBraces; 128 } 129 130 // Select the Nth variant (or empty). 131 StringRef Selection = Cur.slice(VariantsStart, VariantsEnd); 132 for (unsigned i = 0; i != N; ++i) 133 Selection = Selection.split('|').second; 134 Res += Selection.split('|').first; 135 136 assert(VariantsEnd != Cur.size() && 137 "Unterminated variants in assembly string!"); 138 Cur = Cur.substr(VariantsEnd + 1); 139 } 140 141 return Res; 142} 143 144/// TokenizeAsmString - Tokenize a simplified assembly string. 145static void TokenizeAsmString(const StringRef &AsmString, 146 SmallVectorImpl<StringRef> &Tokens) { 147 unsigned Prev = 0; 148 bool InTok = true; 149 for (unsigned i = 0, e = AsmString.size(); i != e; ++i) { 150 switch (AsmString[i]) { 151 case '[': 152 case ']': 153 case '*': 154 case '!': 155 case ' ': 156 case '\t': 157 case ',': 158 if (InTok) { 159 Tokens.push_back(AsmString.slice(Prev, i)); 160 InTok = false; 161 } 162 if (!isspace(AsmString[i]) && AsmString[i] != ',') 163 Tokens.push_back(AsmString.substr(i, 1)); 164 Prev = i + 1; 165 break; 166 167 case '\\': 168 if (InTok) { 169 Tokens.push_back(AsmString.slice(Prev, i)); 170 InTok = false; 171 } 172 ++i; 173 assert(i != AsmString.size() && "Invalid quoted character"); 174 Tokens.push_back(AsmString.substr(i, 1)); 175 Prev = i + 1; 176 break; 177 178 case '$': { 179 // If this isn't "${", treat like a normal token. 180 if (i + 1 == AsmString.size() || AsmString[i + 1] != '{') { 181 if (InTok) { 182 Tokens.push_back(AsmString.slice(Prev, i)); 183 InTok = false; 184 } 185 Prev = i; 186 break; 187 } 188 189 if (InTok) { 190 Tokens.push_back(AsmString.slice(Prev, i)); 191 InTok = false; 192 } 193 194 StringRef::iterator End = 195 std::find(AsmString.begin() + i, AsmString.end(), '}'); 196 assert(End != AsmString.end() && "Missing brace in operand reference!"); 197 size_t EndPos = End - AsmString.begin(); 198 Tokens.push_back(AsmString.slice(i, EndPos+1)); 199 Prev = EndPos + 1; 200 i = EndPos; 201 break; 202 } 203 204 default: 205 InTok = true; 206 } 207 } 208 if (InTok && Prev != AsmString.size()) 209 Tokens.push_back(AsmString.substr(Prev)); 210} 211 212static bool IsAssemblerInstruction(const StringRef &Name, 213 const CodeGenInstruction &CGI, 214 const SmallVectorImpl<StringRef> &Tokens) { 215 // Ignore psuedo ops. 216 // 217 // FIXME: This is a hack. 218 if (const RecordVal *Form = CGI.TheDef->getValue("Form")) 219 if (Form->getValue()->getAsString() == "Pseudo") 220 return false; 221 222 // Ignore "PHI" node. 223 // 224 // FIXME: This is also a hack. 225 if (Name == "PHI") 226 return false; 227 228 // Ignore instructions with no .s string. 229 // 230 // FIXME: What are these? 231 if (CGI.AsmString.empty()) 232 return false; 233 234 // FIXME: Hack; ignore any instructions with a newline in them. 235 if (std::find(CGI.AsmString.begin(), 236 CGI.AsmString.end(), '\n') != CGI.AsmString.end()) 237 return false; 238 239 // Ignore instructions with attributes, these are always fake instructions for 240 // simplifying codegen. 241 // 242 // FIXME: Is this true? 243 // 244 // Also, we ignore instructions which reference the operand multiple times; 245 // this implies a constraint we would not currently honor. These are 246 // currently always fake instructions for simplifying codegen. 247 // 248 // FIXME: Encode this assumption in the .td, so we can error out here. 249 std::set<std::string> OperandNames; 250 for (unsigned i = 1, e = Tokens.size(); i < e; ++i) { 251 if (Tokens[i][0] == '$' && 252 std::find(Tokens[i].begin(), 253 Tokens[i].end(), ':') != Tokens[i].end()) { 254 DEBUG({ 255 errs() << "warning: '" << Name << "': " 256 << "ignoring instruction; operand with attribute '" 257 << Tokens[i] << "', \n"; 258 }); 259 return false; 260 } 261 262 if (Tokens[i][0] == '$' && !OperandNames.insert(Tokens[i]).second) { 263 DEBUG({ 264 errs() << "warning: '" << Name << "': " 265 << "ignoring instruction; tied operand '" 266 << Tokens[i] << "', \n"; 267 }); 268 return false; 269 } 270 } 271 272 return true; 273} 274 275namespace { 276 277/// ClassInfo - Helper class for storing the information about a particular 278/// class of operands which can be matched. 279struct ClassInfo { 280 enum ClassInfoKind { 281 Token, ///< The class for a particular token. 282 Register, ///< A register class. 283 UserClass0 ///< The (first) user defined class, subsequent user defined 284 /// classes are UserClass0+1, and so on. 285 }; 286 287 /// Kind - The class kind, which is either a predefined kind, or (UserClass0 + 288 /// N) for the Nth user defined class. 289 unsigned Kind; 290 291 /// Name - The class name, suitable for use as an enum. 292 std::string Name; 293 294 /// ValueName - The name of the value this class represents; for a token this 295 /// is the literal token string, for an operand it is the TableGen class (or 296 /// empty if this is a derived class). 297 std::string ValueName; 298 299 /// PredicateMethod - The name of the operand method to test whether the 300 /// operand matches this class; this is not valid for Token kinds. 301 std::string PredicateMethod; 302 303 /// RenderMethod - The name of the operand method to add this operand to an 304 /// MCInst; this is not valid for Token kinds. 305 std::string RenderMethod; 306 307 /// operator< - Compare two classes. 308 bool operator<(const ClassInfo &RHS) const { 309 // Incompatible kinds are comparable. 310 if (Kind != RHS.Kind) 311 return Kind < RHS.Kind; 312 313 switch (Kind) { 314 case Token: 315 // Tokens are always comparable. 316 // 317 // FIXME: Compare by enum value. 318 return ValueName < RHS.ValueName; 319 320 case Register: 321 // FIXME: Compare by subset relation. 322 return false; 323 324 default: 325 // FIXME: Allow user defined relation. 326 return false; 327 } 328 } 329}; 330 331/// InstructionInfo - Helper class for storing the necessary information for an 332/// instruction which is capable of being matched. 333struct InstructionInfo { 334 struct Operand { 335 /// The unique class instance this operand should match. 336 ClassInfo *Class; 337 338 /// The original operand this corresponds to, if any. 339 const CodeGenInstruction::OperandInfo *OperandInfo; 340 }; 341 342 /// InstrName - The target name for this instruction. 343 std::string InstrName; 344 345 /// Instr - The instruction this matches. 346 const CodeGenInstruction *Instr; 347 348 /// AsmString - The assembly string for this instruction (with variants 349 /// removed). 350 std::string AsmString; 351 352 /// Tokens - The tokenized assembly pattern that this instruction matches. 353 SmallVector<StringRef, 4> Tokens; 354 355 /// Operands - The operands that this instruction matches. 356 SmallVector<Operand, 4> Operands; 357 358 /// ConversionFnKind - The enum value which is passed to the generated 359 /// ConvertToMCInst to convert parsed operands into an MCInst for this 360 /// function. 361 std::string ConversionFnKind; 362 363 /// operator< - Compare two instructions. 364 bool operator<(const InstructionInfo &RHS) const { 365 // Order first by the number of operands (which is unambiguous). 366 if (Operands.size() != RHS.Operands.size()) 367 return Operands.size() < RHS.Operands.size(); 368 369 // Otherwise, order by lexicographic comparison of tokens and operand kinds 370 // (these can never be ambiguous). 371 for (unsigned i = 0, e = Operands.size(); i != e; ++i) 372 if (Operands[i].Class->Kind != RHS.Operands[i].Class->Kind || 373 Operands[i].Class->Kind == ClassInfo::Token) 374 if (*Operands[i].Class < *RHS.Operands[i].Class) 375 return true; 376 377 // Finally, order by the component wise comparison of operand classes. We 378 // don't want to rely on the lexigraphic ordering of elements, so we define 379 // only define the ordering when it is unambiguous. That is, when some pair 380 // compares less than and no pair compares greater than. 381 382 // Check that no pair compares greater than. 383 for (unsigned i = 0, e = Operands.size(); i != e; ++i) 384 if (*RHS.Operands[i].Class < *Operands[i].Class) 385 return false; 386 387 // Otherwise, return true if some pair compares less than. 388 for (unsigned i = 0, e = Operands.size(); i != e; ++i) 389 if (*Operands[i].Class < *RHS.Operands[i].Class) 390 return true; 391 392 return false; 393 } 394 395public: 396 void dump(); 397}; 398 399class AsmMatcherInfo { 400public: 401 /// The classes which are needed for matching. 402 std::vector<ClassInfo*> Classes; 403 404 /// The information on the instruction to match. 405 std::vector<InstructionInfo*> Instructions; 406 407private: 408 /// Map of token to class information which has already been constructed. 409 std::map<std::string, ClassInfo*> TokenClasses; 410 411 /// Map of operand name to class information which has already been 412 /// constructed. 413 std::map<std::string, ClassInfo*> OperandClasses; 414 415private: 416 /// getTokenClass - Lookup or create the class for the given token. 417 ClassInfo *getTokenClass(const StringRef &Token); 418 419 /// getOperandClass - Lookup or create the class for the given operand. 420 ClassInfo *getOperandClass(const StringRef &Token, 421 const CodeGenInstruction::OperandInfo &OI); 422 423public: 424 /// BuildInfo - Construct the various tables used during matching. 425 void BuildInfo(CodeGenTarget &Target); 426}; 427 428} 429 430void InstructionInfo::dump() { 431 errs() << InstrName << " -- " << "flattened:\"" << AsmString << '\"' 432 << ", tokens:["; 433 for (unsigned i = 0, e = Tokens.size(); i != e; ++i) { 434 errs() << Tokens[i]; 435 if (i + 1 != e) 436 errs() << ", "; 437 } 438 errs() << "]\n"; 439 440 for (unsigned i = 0, e = Operands.size(); i != e; ++i) { 441 Operand &Op = Operands[i]; 442 errs() << " op[" << i << "] = "; 443 if (Op.Class->Kind == ClassInfo::Token) { 444 errs() << '\"' << Tokens[i] << "\"\n"; 445 continue; 446 } 447 448 const CodeGenInstruction::OperandInfo &OI = *Op.OperandInfo; 449 errs() << OI.Name << " " << OI.Rec->getName() 450 << " (" << OI.MIOperandNo << ", " << OI.MINumOperands << ")\n"; 451 } 452} 453 454static std::string getEnumNameForToken(const StringRef &Str) { 455 std::string Res; 456 457 for (StringRef::iterator it = Str.begin(), ie = Str.end(); it != ie; ++it) { 458 switch (*it) { 459 case '*': Res += "_STAR_"; break; 460 case '%': Res += "_PCT_"; break; 461 case ':': Res += "_COLON_"; break; 462 463 default: 464 if (isalnum(*it)) { 465 Res += *it; 466 } else { 467 Res += "_" + utostr((unsigned) *it) + "_"; 468 } 469 } 470 } 471 472 return Res; 473} 474 475ClassInfo *AsmMatcherInfo::getTokenClass(const StringRef &Token) { 476 ClassInfo *&Entry = TokenClasses[Token]; 477 478 if (!Entry) { 479 Entry = new ClassInfo(); 480 Entry->Kind = ClassInfo::Token; 481 Entry->Name = "MCK_" + getEnumNameForToken(Token); 482 Entry->ValueName = Token; 483 Entry->PredicateMethod = "<invalid>"; 484 Entry->RenderMethod = "<invalid>"; 485 Classes.push_back(Entry); 486 } 487 488 return Entry; 489} 490 491ClassInfo * 492AsmMatcherInfo::getOperandClass(const StringRef &Token, 493 const CodeGenInstruction::OperandInfo &OI) { 494 std::string ClassName; 495 if (OI.Rec->isSubClassOf("RegisterClass")) { 496 ClassName = "Reg"; 497 } else if (OI.Rec->isSubClassOf("Operand")) { 498 // FIXME: This should not be hard coded. 499 const RecordVal *RV = OI.Rec->getValue("Type"); 500 501 // FIXME: Yet another total hack. 502 if (RV->getValue()->getAsString() == "iPTR" || 503 OI.Rec->getName() == "i8mem_NOREX" || 504 OI.Rec->getName() == "lea32mem" || 505 OI.Rec->getName() == "lea64mem" || 506 OI.Rec->getName() == "i128mem" || 507 OI.Rec->getName() == "sdmem" || 508 OI.Rec->getName() == "ssmem" || 509 OI.Rec->getName() == "lea64_32mem") { 510 ClassName = "Mem"; 511 } else { 512 ClassName = "Imm"; 513 } 514 } 515 516 ClassInfo *&Entry = OperandClasses[ClassName]; 517 518 if (!Entry) { 519 Entry = new ClassInfo(); 520 // FIXME: Hack. 521 if (ClassName == "Reg") { 522 Entry->Kind = ClassInfo::Register; 523 } else { 524 if (ClassName == "Mem") 525 Entry->Kind = ClassInfo::UserClass0; 526 else 527 Entry->Kind = ClassInfo::UserClass0 + 1; 528 } 529 Entry->Name = "MCK_" + ClassName; 530 Entry->ValueName = OI.Rec->getName(); 531 Entry->PredicateMethod = "is" + ClassName; 532 Entry->RenderMethod = "add" + ClassName + "Operands"; 533 Classes.push_back(Entry); 534 } 535 536 return Entry; 537} 538 539void AsmMatcherInfo::BuildInfo(CodeGenTarget &Target) { 540 for (std::map<std::string, CodeGenInstruction>::const_iterator 541 it = Target.getInstructions().begin(), 542 ie = Target.getInstructions().end(); 543 it != ie; ++it) { 544 const CodeGenInstruction &CGI = it->second; 545 546 if (!StringRef(it->first).startswith(MatchPrefix)) 547 continue; 548 549 OwningPtr<InstructionInfo> II(new InstructionInfo); 550 551 II->InstrName = it->first; 552 II->Instr = &it->second; 553 II->AsmString = FlattenVariants(CGI.AsmString, 0); 554 555 TokenizeAsmString(II->AsmString, II->Tokens); 556 557 // Ignore instructions which shouldn't be matched. 558 if (!IsAssemblerInstruction(it->first, CGI, II->Tokens)) 559 continue; 560 561 for (unsigned i = 0, e = II->Tokens.size(); i != e; ++i) { 562 StringRef Token = II->Tokens[i]; 563 564 // Check for simple tokens. 565 if (Token[0] != '$') { 566 InstructionInfo::Operand Op; 567 Op.Class = getTokenClass(Token); 568 Op.OperandInfo = 0; 569 II->Operands.push_back(Op); 570 continue; 571 } 572 573 // Otherwise this is an operand reference. 574 StringRef OperandName; 575 if (Token[1] == '{') 576 OperandName = Token.substr(2, Token.size() - 3); 577 else 578 OperandName = Token.substr(1); 579 580 // Map this token to an operand. FIXME: Move elsewhere. 581 unsigned Idx; 582 try { 583 Idx = CGI.getOperandNamed(OperandName); 584 } catch(...) { 585 errs() << "error: unable to find operand: '" << OperandName << "'!\n"; 586 break; 587 } 588 589 const CodeGenInstruction::OperandInfo &OI = CGI.OperandList[Idx]; 590 InstructionInfo::Operand Op; 591 Op.Class = getOperandClass(Token, OI); 592 Op.OperandInfo = &OI; 593 II->Operands.push_back(Op); 594 } 595 596 // If we broke out, ignore the instruction. 597 if (II->Operands.size() != II->Tokens.size()) 598 continue; 599 600 Instructions.push_back(II.take()); 601 } 602} 603 604static void EmitConvertToMCInst(CodeGenTarget &Target, 605 std::vector<InstructionInfo*> &Infos, 606 raw_ostream &OS) { 607 // Write the convert function to a separate stream, so we can drop it after 608 // the enum. 609 std::string ConvertFnBody; 610 raw_string_ostream CvtOS(ConvertFnBody); 611 612 // Function we have already generated. 613 std::set<std::string> GeneratedFns; 614 615 // Start the unified conversion function. 616 617 CvtOS << "static bool ConvertToMCInst(ConversionKind Kind, MCInst &Inst, " 618 << "unsigned Opcode,\n" 619 << " SmallVectorImpl<" 620 << Target.getName() << "Operand> &Operands) {\n"; 621 CvtOS << " Inst.setOpcode(Opcode);\n"; 622 CvtOS << " switch (Kind) {\n"; 623 CvtOS << " default:\n"; 624 625 // Start the enum, which we will generate inline. 626 627 OS << "// Unified function for converting operants to MCInst instances.\n\n"; 628 OS << "enum ConversionKind {\n"; 629 630 for (std::vector<InstructionInfo*>::const_iterator it = Infos.begin(), 631 ie = Infos.end(); it != ie; ++it) { 632 InstructionInfo &II = **it; 633 634 // Order the (class) operands by the order to convert them into an MCInst. 635 SmallVector<std::pair<unsigned, unsigned>, 4> MIOperandList; 636 for (unsigned i = 0, e = II.Operands.size(); i != e; ++i) { 637 InstructionInfo::Operand &Op = II.Operands[i]; 638 if (Op.OperandInfo) 639 MIOperandList.push_back(std::make_pair(Op.OperandInfo->MIOperandNo, i)); 640 } 641 std::sort(MIOperandList.begin(), MIOperandList.end()); 642 643 // Compute the total number of operands. 644 unsigned NumMIOperands = 0; 645 for (unsigned i = 0, e = II.Instr->OperandList.size(); i != e; ++i) { 646 const CodeGenInstruction::OperandInfo &OI = II.Instr->OperandList[i]; 647 NumMIOperands = std::max(NumMIOperands, 648 OI.MIOperandNo + OI.MINumOperands); 649 } 650 651 // Build the conversion function signature. 652 std::string Signature = "Convert"; 653 unsigned CurIndex = 0; 654 for (unsigned i = 0, e = MIOperandList.size(); i != e; ++i) { 655 InstructionInfo::Operand &Op = II.Operands[MIOperandList[i].second]; 656 assert(CurIndex <= Op.OperandInfo->MIOperandNo && 657 "Duplicate match for instruction operand!"); 658 659 Signature += "_"; 660 661 // Skip operands which weren't matched by anything, this occurs when the 662 // .td file encodes "implicit" operands as explicit ones. 663 // 664 // FIXME: This should be removed from the MCInst structure. 665 for (; CurIndex != Op.OperandInfo->MIOperandNo; ++CurIndex) 666 Signature += "Imp"; 667 668 Signature += Op.Class->Name; 669 Signature += utostr(Op.OperandInfo->MINumOperands); 670 Signature += "_" + utostr(MIOperandList[i].second); 671 672 CurIndex += Op.OperandInfo->MINumOperands; 673 } 674 675 // Add any trailing implicit operands. 676 for (; CurIndex != NumMIOperands; ++CurIndex) 677 Signature += "Imp"; 678 679 II.ConversionFnKind = Signature; 680 681 // Check if we have already generated this signature. 682 if (!GeneratedFns.insert(Signature).second) 683 continue; 684 685 // If not, emit it now. 686 687 // Add to the enum list. 688 OS << " " << Signature << ",\n"; 689 690 // And to the convert function. 691 CvtOS << " case " << Signature << ":\n"; 692 CurIndex = 0; 693 for (unsigned i = 0, e = MIOperandList.size(); i != e; ++i) { 694 InstructionInfo::Operand &Op = II.Operands[MIOperandList[i].second]; 695 696 // Add the implicit operands. 697 for (; CurIndex != Op.OperandInfo->MIOperandNo; ++CurIndex) 698 CvtOS << " Inst.addOperand(MCOperand::CreateReg(0));\n"; 699 700 CvtOS << " Operands[" << MIOperandList[i].second 701 << "]." << Op.Class->RenderMethod 702 << "(Inst, " << Op.OperandInfo->MINumOperands << ");\n"; 703 CurIndex += Op.OperandInfo->MINumOperands; 704 } 705 706 // And add trailing implicit operands. 707 for (; CurIndex != NumMIOperands; ++CurIndex) 708 CvtOS << " Inst.addOperand(MCOperand::CreateReg(0));\n"; 709 CvtOS << " break;\n"; 710 } 711 712 // Finish the convert function. 713 714 CvtOS << " }\n"; 715 CvtOS << " return false;\n"; 716 CvtOS << "}\n\n"; 717 718 // Finish the enum, and drop the convert function after it. 719 720 OS << " NumConversionVariants\n"; 721 OS << "};\n\n"; 722 723 OS << CvtOS.str(); 724} 725 726/// EmitMatchClassEnumeration - Emit the enumeration for match class kinds. 727static void EmitMatchClassEnumeration(CodeGenTarget &Target, 728 std::vector<ClassInfo*> &Infos, 729 raw_ostream &OS) { 730 OS << "namespace {\n\n"; 731 732 OS << "/// MatchClassKind - The kinds of classes which participate in\n" 733 << "/// instruction matching.\n"; 734 OS << "enum MatchClassKind {\n"; 735 OS << " InvalidMatchClass = 0,\n"; 736 for (std::vector<ClassInfo*>::iterator it = Infos.begin(), 737 ie = Infos.end(); it != ie; ++it) { 738 ClassInfo &CI = **it; 739 OS << " " << CI.Name << ", // "; 740 if (CI.Kind == ClassInfo::Token) { 741 OS << "'" << CI.ValueName << "'\n"; 742 } else if (CI.Kind == ClassInfo::Register) { 743 if (!CI.ValueName.empty()) 744 OS << "register class '" << CI.ValueName << "'\n"; 745 else 746 OS << "derived register class\n"; 747 } else { 748 OS << "user defined class '" << CI.ValueName << "'\n"; 749 } 750 } 751 OS << " NumMatchClassKinds\n"; 752 OS << "};\n\n"; 753 754 OS << "}\n\n"; 755} 756 757/// EmitClassifyOperand - Emit the function to classify an operand. 758static void EmitClassifyOperand(CodeGenTarget &Target, 759 std::vector<ClassInfo*> &Infos, 760 raw_ostream &OS) { 761 OS << "static MatchClassKind ClassifyOperand(" 762 << Target.getName() << "Operand &Operand) {\n"; 763 OS << " if (Operand.isToken())\n"; 764 OS << " return MatchTokenString(Operand.getToken());\n\n"; 765 for (std::vector<ClassInfo*>::iterator it = Infos.begin(), 766 ie = Infos.end(); it != ie; ++it) { 767 ClassInfo &CI = **it; 768 769 if (CI.Kind != ClassInfo::Token) { 770 OS << " if (Operand." << CI.PredicateMethod << "())\n"; 771 OS << " return " << CI.Name << ";\n\n"; 772 } 773 } 774 OS << " return InvalidMatchClass;\n"; 775 OS << "}\n\n"; 776} 777 778typedef std::pair<std::string, std::string> StringPair; 779 780/// FindFirstNonCommonLetter - Find the first character in the keys of the 781/// string pairs that is not shared across the whole set of strings. All 782/// strings are assumed to have the same length. 783static unsigned 784FindFirstNonCommonLetter(const std::vector<const StringPair*> &Matches) { 785 assert(!Matches.empty()); 786 for (unsigned i = 0, e = Matches[0]->first.size(); i != e; ++i) { 787 // Check to see if letter i is the same across the set. 788 char Letter = Matches[0]->first[i]; 789 790 for (unsigned str = 0, e = Matches.size(); str != e; ++str) 791 if (Matches[str]->first[i] != Letter) 792 return i; 793 } 794 795 return Matches[0]->first.size(); 796} 797 798/// EmitStringMatcherForChar - Given a set of strings that are known to be the 799/// same length and whose characters leading up to CharNo are the same, emit 800/// code to verify that CharNo and later are the same. 801/// 802/// \return - True if control can leave the emitted code fragment. 803static bool EmitStringMatcherForChar(const std::string &StrVariableName, 804 const std::vector<const StringPair*> &Matches, 805 unsigned CharNo, unsigned IndentCount, 806 raw_ostream &OS) { 807 assert(!Matches.empty() && "Must have at least one string to match!"); 808 std::string Indent(IndentCount*2+4, ' '); 809 810 // If we have verified that the entire string matches, we're done: output the 811 // matching code. 812 if (CharNo == Matches[0]->first.size()) { 813 assert(Matches.size() == 1 && "Had duplicate keys to match on"); 814 815 // FIXME: If Matches[0].first has embeded \n, this will be bad. 816 OS << Indent << Matches[0]->second << "\t // \"" << Matches[0]->first 817 << "\"\n"; 818 return false; 819 } 820 821 // Bucket the matches by the character we are comparing. 822 std::map<char, std::vector<const StringPair*> > MatchesByLetter; 823 824 for (unsigned i = 0, e = Matches.size(); i != e; ++i) 825 MatchesByLetter[Matches[i]->first[CharNo]].push_back(Matches[i]); 826 827 828 // If we have exactly one bucket to match, see how many characters are common 829 // across the whole set and match all of them at once. 830 if (MatchesByLetter.size() == 1) { 831 unsigned FirstNonCommonLetter = FindFirstNonCommonLetter(Matches); 832 unsigned NumChars = FirstNonCommonLetter-CharNo; 833 834 // Emit code to break out if the prefix doesn't match. 835 if (NumChars == 1) { 836 // Do the comparison with if (Str[1] != 'f') 837 // FIXME: Need to escape general characters. 838 OS << Indent << "if (" << StrVariableName << "[" << CharNo << "] != '" 839 << Matches[0]->first[CharNo] << "')\n"; 840 OS << Indent << " break;\n"; 841 } else { 842 // Do the comparison with if (Str.substr(1,3) != "foo"). 843 // FIXME: Need to escape general strings. 844 OS << Indent << "if (" << StrVariableName << ".substr(" << CharNo << "," 845 << NumChars << ") != \""; 846 OS << Matches[0]->first.substr(CharNo, NumChars) << "\")\n"; 847 OS << Indent << " break;\n"; 848 } 849 850 return EmitStringMatcherForChar(StrVariableName, Matches, 851 FirstNonCommonLetter, IndentCount, OS); 852 } 853 854 // Otherwise, we have multiple possible things, emit a switch on the 855 // character. 856 OS << Indent << "switch (" << StrVariableName << "[" << CharNo << "]) {\n"; 857 OS << Indent << "default: break;\n"; 858 859 for (std::map<char, std::vector<const StringPair*> >::iterator LI = 860 MatchesByLetter.begin(), E = MatchesByLetter.end(); LI != E; ++LI) { 861 // TODO: escape hard stuff (like \n) if we ever care about it. 862 OS << Indent << "case '" << LI->first << "':\t // " 863 << LI->second.size() << " strings to match.\n"; 864 if (EmitStringMatcherForChar(StrVariableName, LI->second, CharNo+1, 865 IndentCount+1, OS)) 866 OS << Indent << " break;\n"; 867 } 868 869 OS << Indent << "}\n"; 870 return true; 871} 872 873 874/// EmitStringMatcher - Given a list of strings and code to execute when they 875/// match, output a simple switch tree to classify the input string. 876/// 877/// If a match is found, the code in Vals[i].second is executed; control must 878/// not exit this code fragment. If nothing matches, execution falls through. 879/// 880/// \param StrVariableName - The name of the variable to test. 881static void EmitStringMatcher(const std::string &StrVariableName, 882 const std::vector<StringPair> &Matches, 883 raw_ostream &OS) { 884 // First level categorization: group strings by length. 885 std::map<unsigned, std::vector<const StringPair*> > MatchesByLength; 886 887 for (unsigned i = 0, e = Matches.size(); i != e; ++i) 888 MatchesByLength[Matches[i].first.size()].push_back(&Matches[i]); 889 890 // Output a switch statement on length and categorize the elements within each 891 // bin. 892 OS << " switch (" << StrVariableName << ".size()) {\n"; 893 OS << " default: break;\n"; 894 895 for (std::map<unsigned, std::vector<const StringPair*> >::iterator LI = 896 MatchesByLength.begin(), E = MatchesByLength.end(); LI != E; ++LI) { 897 OS << " case " << LI->first << ":\t // " << LI->second.size() 898 << " strings to match.\n"; 899 if (EmitStringMatcherForChar(StrVariableName, LI->second, 0, 0, OS)) 900 OS << " break;\n"; 901 } 902 903 OS << " }\n"; 904} 905 906 907/// EmitMatchTokenString - Emit the function to match a token string to the 908/// appropriate match class value. 909static void EmitMatchTokenString(CodeGenTarget &Target, 910 std::vector<ClassInfo*> &Infos, 911 raw_ostream &OS) { 912 // Construct the match list. 913 std::vector<StringPair> Matches; 914 for (std::vector<ClassInfo*>::iterator it = Infos.begin(), 915 ie = Infos.end(); it != ie; ++it) { 916 ClassInfo &CI = **it; 917 918 if (CI.Kind == ClassInfo::Token) 919 Matches.push_back(StringPair(CI.ValueName, "return " + CI.Name + ";")); 920 } 921 922 OS << "static MatchClassKind MatchTokenString(const StringRef &Name) {\n"; 923 924 EmitStringMatcher("Name", Matches, OS); 925 926 OS << " return InvalidMatchClass;\n"; 927 OS << "}\n\n"; 928} 929 930/// EmitMatchRegisterName - Emit the function to match a string to the target 931/// specific register enum. 932static void EmitMatchRegisterName(CodeGenTarget &Target, Record *AsmParser, 933 raw_ostream &OS) { 934 // Construct the match list. 935 std::vector<StringPair> Matches; 936 for (unsigned i = 0, e = Target.getRegisters().size(); i != e; ++i) { 937 const CodeGenRegister &Reg = Target.getRegisters()[i]; 938 if (Reg.TheDef->getValueAsString("AsmName").empty()) 939 continue; 940 941 Matches.push_back(StringPair(Reg.TheDef->getValueAsString("AsmName"), 942 "return " + utostr(i + 1) + ";")); 943 } 944 945 OS << "unsigned " << Target.getName() 946 << AsmParser->getValueAsString("AsmParserClassName") 947 << "::MatchRegisterName(const StringRef &Name) {\n"; 948 949 EmitStringMatcher("Name", Matches, OS); 950 951 OS << " return 0;\n"; 952 OS << "}\n\n"; 953} 954 955void AsmMatcherEmitter::run(raw_ostream &OS) { 956 CodeGenTarget Target; 957 Record *AsmParser = Target.getAsmParser(); 958 std::string ClassName = AsmParser->getValueAsString("AsmParserClassName"); 959 960 EmitSourceFileHeader("Assembly Matcher Source Fragment", OS); 961 962 // Emit the function to match a register name to number. 963 EmitMatchRegisterName(Target, AsmParser, OS); 964 965 // Compute the information on the instructions to match. 966 AsmMatcherInfo Info; 967 Info.BuildInfo(Target); 968 969 // Sort the instruction table using the partial order on classes. 970 std::sort(Info.Instructions.begin(), Info.Instructions.end(), 971 less_ptr<InstructionInfo>()); 972 973 DEBUG_WITH_TYPE("instruction_info", { 974 for (std::vector<InstructionInfo*>::iterator 975 it = Info.Instructions.begin(), ie = Info.Instructions.end(); 976 it != ie; ++it) 977 (*it)->dump(); 978 }); 979 980 // Check for ambiguous instructions. 981 unsigned NumAmbiguous = 0; 982 for (std::vector<InstructionInfo*>::const_iterator it = 983 Info.Instructions.begin(), ie = Info.Instructions.end() - 1; 984 it != ie;) { 985 InstructionInfo &II = **it; 986 ++it; 987 988 InstructionInfo &Next = **it; 989 990 if (!(II < Next)){ 991 DEBUG_WITH_TYPE("ambiguous_instrs", { 992 errs() << "warning: ambiguous instruction match:\n"; 993 II.dump(); 994 errs() << "\nis incomparable with:\n"; 995 Next.dump(); 996 errs() << "\n\n"; 997 }); 998 ++NumAmbiguous; 999 } 1000 } 1001 if (NumAmbiguous) 1002 DEBUG_WITH_TYPE("ambiguous_instrs", { 1003 errs() << "warning: " << NumAmbiguous 1004 << " ambiguous instructions!\n"; 1005 }); 1006 1007 // Generate the unified function to convert operands into an MCInst. 1008 EmitConvertToMCInst(Target, Info.Instructions, OS); 1009 1010 // Emit the enumeration for classes which participate in matching. 1011 EmitMatchClassEnumeration(Target, Info.Classes, OS); 1012 1013 // Emit the routine to match token strings to their match class. 1014 EmitMatchTokenString(Target, Info.Classes, OS); 1015 1016 // Emit the routine to classify an operand. 1017 EmitClassifyOperand(Target, Info.Classes, OS); 1018 1019 // Finally, build the match function. 1020 1021 size_t MaxNumOperands = 0; 1022 for (std::vector<InstructionInfo*>::const_iterator it = 1023 Info.Instructions.begin(), ie = Info.Instructions.end(); 1024 it != ie; ++it) 1025 MaxNumOperands = std::max(MaxNumOperands, (*it)->Operands.size()); 1026 1027 OS << "bool " << Target.getName() << ClassName 1028 << "::MatchInstruction(" 1029 << "SmallVectorImpl<" << Target.getName() << "Operand> &Operands, " 1030 << "MCInst &Inst) {\n"; 1031 1032 // Emit the static match table; unused classes get initalized to 0 which is 1033 // guaranteed to be InvalidMatchClass. 1034 // 1035 // FIXME: We can reduce the size of this table very easily. First, we change 1036 // it so that store the kinds in separate bit-fields for each index, which 1037 // only needs to be the max width used for classes at that index (we also need 1038 // to reject based on this during classification). If we then make sure to 1039 // order the match kinds appropriately (putting mnemonics last), then we 1040 // should only end up using a few bits for each class, especially the ones 1041 // following the mnemonic. 1042 OS << " static const struct MatchEntry {\n"; 1043 OS << " unsigned Opcode;\n"; 1044 OS << " ConversionKind ConvertFn;\n"; 1045 OS << " MatchClassKind Classes[" << MaxNumOperands << "];\n"; 1046 OS << " } MatchTable[" << Info.Instructions.size() << "] = {\n"; 1047 1048 for (std::vector<InstructionInfo*>::const_iterator it = 1049 Info.Instructions.begin(), ie = Info.Instructions.end(); 1050 it != ie; ++it) { 1051 InstructionInfo &II = **it; 1052 1053 OS << " { " << Target.getName() << "::" << II.InstrName 1054 << ", " << II.ConversionFnKind << ", { "; 1055 for (unsigned i = 0, e = II.Operands.size(); i != e; ++i) { 1056 InstructionInfo::Operand &Op = II.Operands[i]; 1057 1058 if (i) OS << ", "; 1059 OS << Op.Class->Name; 1060 } 1061 OS << " } },\n"; 1062 } 1063 1064 OS << " };\n\n"; 1065 1066 // Emit code to compute the class list for this operand vector. 1067 OS << " // Eliminate obvious mismatches.\n"; 1068 OS << " if (Operands.size() > " << MaxNumOperands << ")\n"; 1069 OS << " return true;\n\n"; 1070 1071 OS << " // Compute the class list for this operand vector.\n"; 1072 OS << " MatchClassKind Classes[" << MaxNumOperands << "];\n"; 1073 OS << " for (unsigned i = 0, e = Operands.size(); i != e; ++i) {\n"; 1074 OS << " Classes[i] = ClassifyOperand(Operands[i]);\n\n"; 1075 1076 OS << " // Check for invalid operands before matching.\n"; 1077 OS << " if (Classes[i] == InvalidMatchClass)\n"; 1078 OS << " return true;\n"; 1079 OS << " }\n\n"; 1080 1081 OS << " // Mark unused classes.\n"; 1082 OS << " for (unsigned i = Operands.size(), e = " << MaxNumOperands << "; " 1083 << "i != e; ++i)\n"; 1084 OS << " Classes[i] = InvalidMatchClass;\n\n"; 1085 1086 // Emit code to search the table. 1087 OS << " // Search the table.\n"; 1088 OS << " for (const MatchEntry *it = MatchTable, " 1089 << "*ie = MatchTable + " << Info.Instructions.size() 1090 << "; it != ie; ++it) {\n"; 1091 for (unsigned i = 0; i != MaxNumOperands; ++i) { 1092 OS << " if (Classes[" << i << "] != it->Classes[" << i << "])\n"; 1093 OS << " continue;\n"; 1094 } 1095 OS << "\n"; 1096 OS << " return ConvertToMCInst(it->ConvertFn, Inst, " 1097 << "it->Opcode, Operands);\n"; 1098 OS << " }\n\n"; 1099 1100 OS << " return true;\n"; 1101 OS << "}\n\n"; 1102} 1103