AsmMatcherEmitter.cpp revision 5e8f2a65ca2044815039129610876dfc4de3ebfa
18cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd//===- AsmMatcherEmitter.cpp - Generate an assembly matcher ---------------===// 28cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// 38cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// The LLVM Compiler Infrastructure 48cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// 58cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// This file is distributed under the University of Illinois Open Source 68cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// License. See LICENSE.TXT for details. 78cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// 88cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd//===----------------------------------------------------------------------===// 98cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// 108cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// This tablegen backend emits a target specifier matcher for converting parsed 118cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// assembly operands in the MCInst structures. 128cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// 138cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// The input to the target specific matcher is a list of literal tokens and 148cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// operands. The target specific parser should generally eliminate any syntax 158cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// which is not relevant for matching; for example, comma tokens should have 168cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// already been consumed and eliminated by the parser. Most instructions will 178cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// end up with a single literal token (the instruction name) and some number of 188cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// operands. 198cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// 208cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// Some example inputs, for X86: 218cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// 'addl' (immediate ...) (register ...) 228cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// 'add' (immediate ...) (memory ...) 238cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// 'call' '*' %epc 248cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// 258cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// The assembly matcher is responsible for converting this input into a precise 268cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// machine instruction (i.e., an instruction with a well defined encoding). This 278cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// mapping has several properties which complicate matching: 288cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// 298cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// - It may be ambiguous; many architectures can legally encode particular 308cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// variants of an instruction in different ways (for example, using a smaller 318cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// encoding for small immediates). Such ambiguities should never be 328cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// arbitrarily resolved by the assembler, the assembler is always responsible 338cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// for choosing the "best" available instruction. 348cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// 358cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// - It may depend on the subtarget or the assembler context. Instructions 368cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// which are invalid for the current mode, but otherwise unambiguous (e.g., 378cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// an SSE instruction in a file being assembled for i486) should be accepted 388cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// and rejected by the assembler front end. However, if the proper encoding 398cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// for an instruction is dependent on the assembler context then the matcher 408cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// is responsible for selecting the correct machine instruction for the 418cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// current mode. 428cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// 438cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// The core matching algorithm attempts to exploit the regularity in most 448cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// instruction sets to quickly determine the set of possibly matching 458cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// instructions, and the simplify the generated code. Additionally, this helps 468cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// to ensure that the ambiguities are intentionally resolved by the user. 478cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd// 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// 2. The input can now be treated as a tuple of classes (static tokens are 67// simple singleton sets). Each such tuple should generally map to a single 68// instruction (we currently ignore cases where this isn't true, whee!!!), 69// which we can emit a simple matcher for. 70// 71//===----------------------------------------------------------------------===// 72 73#include "AsmMatcherEmitter.h" 74#include "CodeGenTarget.h" 75#include "Record.h" 76#include "StringMatcher.h" 77#include "llvm/ADT/OwningPtr.h" 78#include "llvm/ADT/PointerUnion.h" 79#include "llvm/ADT/SmallPtrSet.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 <map> 86#include <set> 87using namespace llvm; 88 89static cl::opt<std::string> 90MatchPrefix("match-prefix", cl::init(""), 91 cl::desc("Only match instructions with the given prefix")); 92 93 94namespace { 95 class AsmMatcherInfo; 96struct SubtargetFeatureInfo; 97 98/// ClassInfo - Helper class for storing the information about a particular 99/// class of operands which can be matched. 100struct ClassInfo { 101 enum ClassInfoKind { 102 /// Invalid kind, for use as a sentinel value. 103 Invalid = 0, 104 105 /// The class for a particular token. 106 Token, 107 108 /// The (first) register class, subsequent register classes are 109 /// RegisterClass0+1, and so on. 110 RegisterClass0, 111 112 /// The (first) user defined class, subsequent user defined classes are 113 /// UserClass0+1, and so on. 114 UserClass0 = 1<<16 115 }; 116 117 /// Kind - The class kind, which is either a predefined kind, or (UserClass0 + 118 /// N) for the Nth user defined class. 119 unsigned Kind; 120 121 /// SuperClasses - The super classes of this class. Note that for simplicities 122 /// sake user operands only record their immediate super class, while register 123 /// operands include all superclasses. 124 std::vector<ClassInfo*> SuperClasses; 125 126 /// Name - The full class name, suitable for use in an enum. 127 std::string Name; 128 129 /// ClassName - The unadorned generic name for this class (e.g., Token). 130 std::string ClassName; 131 132 /// ValueName - The name of the value this class represents; for a token this 133 /// is the literal token string, for an operand it is the TableGen class (or 134 /// empty if this is a derived class). 135 std::string ValueName; 136 137 /// PredicateMethod - The name of the operand method to test whether the 138 /// operand matches this class; this is not valid for Token or register kinds. 139 std::string PredicateMethod; 140 141 /// RenderMethod - The name of the operand method to add this operand to an 142 /// MCInst; this is not valid for Token or register kinds. 143 std::string RenderMethod; 144 145 /// For register classes, the records for all the registers in this class. 146 std::set<Record*> Registers; 147 148public: 149 /// isRegisterClass() - Check if this is a register class. 150 bool isRegisterClass() const { 151 return Kind >= RegisterClass0 && Kind < UserClass0; 152 } 153 154 /// isUserClass() - Check if this is a user defined class. 155 bool isUserClass() const { 156 return Kind >= UserClass0; 157 } 158 159 /// isRelatedTo - Check whether this class is "related" to \arg RHS. Classes 160 /// are related if they are in the same class hierarchy. 161 bool isRelatedTo(const ClassInfo &RHS) const { 162 // Tokens are only related to tokens. 163 if (Kind == Token || RHS.Kind == Token) 164 return Kind == Token && RHS.Kind == Token; 165 166 // Registers classes are only related to registers classes, and only if 167 // their intersection is non-empty. 168 if (isRegisterClass() || RHS.isRegisterClass()) { 169 if (!isRegisterClass() || !RHS.isRegisterClass()) 170 return false; 171 172 std::set<Record*> Tmp; 173 std::insert_iterator< std::set<Record*> > II(Tmp, Tmp.begin()); 174 std::set_intersection(Registers.begin(), Registers.end(), 175 RHS.Registers.begin(), RHS.Registers.end(), 176 II); 177 178 return !Tmp.empty(); 179 } 180 181 // Otherwise we have two users operands; they are related if they are in the 182 // same class hierarchy. 183 // 184 // FIXME: This is an oversimplification, they should only be related if they 185 // intersect, however we don't have that information. 186 assert(isUserClass() && RHS.isUserClass() && "Unexpected class!"); 187 const ClassInfo *Root = this; 188 while (!Root->SuperClasses.empty()) 189 Root = Root->SuperClasses.front(); 190 191 const ClassInfo *RHSRoot = &RHS; 192 while (!RHSRoot->SuperClasses.empty()) 193 RHSRoot = RHSRoot->SuperClasses.front(); 194 195 return Root == RHSRoot; 196 } 197 198 /// isSubsetOf - Test whether this class is a subset of \arg RHS; 199 bool isSubsetOf(const ClassInfo &RHS) const { 200 // This is a subset of RHS if it is the same class... 201 if (this == &RHS) 202 return true; 203 204 // ... or if any of its super classes are a subset of RHS. 205 for (std::vector<ClassInfo*>::const_iterator it = SuperClasses.begin(), 206 ie = SuperClasses.end(); it != ie; ++it) 207 if ((*it)->isSubsetOf(RHS)) 208 return true; 209 210 return false; 211 } 212 213 /// operator< - Compare two classes. 214 bool operator<(const ClassInfo &RHS) const { 215 if (this == &RHS) 216 return false; 217 218 // Unrelated classes can be ordered by kind. 219 if (!isRelatedTo(RHS)) 220 return Kind < RHS.Kind; 221 222 switch (Kind) { 223 case Invalid: 224 assert(0 && "Invalid kind!"); 225 case Token: 226 // Tokens are comparable by value. 227 // 228 // FIXME: Compare by enum value. 229 return ValueName < RHS.ValueName; 230 231 default: 232 // This class preceeds the RHS if it is a proper subset of the RHS. 233 if (isSubsetOf(RHS)) 234 return true; 235 if (RHS.isSubsetOf(*this)) 236 return false; 237 238 // Otherwise, order by name to ensure we have a total ordering. 239 return ValueName < RHS.ValueName; 240 } 241 } 242}; 243 244/// MatchableInfo - Helper class for storing the necessary information for an 245/// instruction or alias which is capable of being matched. 246struct MatchableInfo { 247 struct AsmOperand { 248 /// Token - This is the token that the operand came from. 249 StringRef Token; 250 251 /// The unique class instance this operand should match. 252 ClassInfo *Class; 253 254 /// The operand name this is, if anything. 255 StringRef SrcOpName; 256 257 explicit AsmOperand(StringRef T) : Token(T), Class(0) {} 258 }; 259 260 /// ResOperand - This represents a single operand in the result instruction 261 /// generated by the match. In cases (like addressing modes) where a single 262 /// assembler operand expands to multiple MCOperands, this represents the 263 /// single assembler operand, not the MCOperand. 264 struct ResOperand { 265 enum { 266 /// RenderAsmOperand - This represents an operand result that is 267 /// generated by calling the render method on the assembly operand. The 268 /// corresponding AsmOperand is specified by AsmOperandNum. 269 RenderAsmOperand, 270 271 /// TiedOperand - This represents a result operand that is a duplicate of 272 /// a previous result operand. 273 TiedOperand, 274 275 /// ImmOperand - This represents an immediate value that is dumped into 276 /// the operand. 277 ImmOperand, 278 279 /// RegOperand - This represents a fixed register that is dumped in. 280 RegOperand 281 } Kind; 282 283 union { 284 /// This is the operand # in the AsmOperands list that this should be 285 /// copied from. 286 unsigned AsmOperandNum; 287 288 /// TiedOperandNum - This is the (earlier) result operand that should be 289 /// copied from. 290 unsigned TiedOperandNum; 291 292 /// ImmVal - This is the immediate value added to the instruction. 293 int64_t ImmVal; 294 295 /// Register - This is the register record. 296 Record *Register; 297 }; 298 299 /// OpInfo - This is the information about the instruction operand that is 300 /// being populated. 301 const CGIOperandList::OperandInfo *OpInfo; 302 303 static ResOperand getRenderedOp(unsigned AsmOpNum, 304 const CGIOperandList::OperandInfo *Op) { 305 ResOperand X; 306 X.Kind = RenderAsmOperand; 307 X.AsmOperandNum = AsmOpNum; 308 X.OpInfo = Op; 309 return X; 310 } 311 312 static ResOperand getTiedOp(unsigned TiedOperandNum, 313 const CGIOperandList::OperandInfo *Op) { 314 ResOperand X; 315 X.Kind = TiedOperand; 316 X.TiedOperandNum = TiedOperandNum; 317 X.OpInfo = Op; 318 return X; 319 } 320 321 static ResOperand getImmOp(int64_t Val, 322 const CGIOperandList::OperandInfo *Op) { 323 ResOperand X; 324 X.Kind = ImmOperand; 325 X.ImmVal = Val; 326 X.OpInfo = Op; 327 return X; 328 } 329 330 static ResOperand getRegOp(Record *Reg, 331 const CGIOperandList::OperandInfo *Op) { 332 ResOperand X; 333 X.Kind = RegOperand; 334 X.Register = Reg; 335 X.OpInfo = Op; 336 return X; 337 } 338 339 }; 340 341 /// TheDef - This is the definition of the instruction or InstAlias that this 342 /// matchable came from. 343 Record *const TheDef; 344 345 /// DefRec - This is the definition that it came from. 346 PointerUnion<const CodeGenInstruction*, const CodeGenInstAlias*> DefRec; 347 348 const CodeGenInstruction *getResultInst() const { 349 if (DefRec.is<const CodeGenInstruction*>()) 350 return DefRec.get<const CodeGenInstruction*>(); 351 return DefRec.get<const CodeGenInstAlias*>()->ResultInst; 352 } 353 354 /// ResOperands - This is the operand list that should be built for the result 355 /// MCInst. 356 std::vector<ResOperand> ResOperands; 357 358 /// AsmString - The assembly string for this instruction (with variants 359 /// removed), e.g. "movsx $src, $dst". 360 std::string AsmString; 361 362 /// Mnemonic - This is the first token of the matched instruction, its 363 /// mnemonic. 364 StringRef Mnemonic; 365 366 /// AsmOperands - The textual operands that this instruction matches, 367 /// annotated with a class and where in the OperandList they were defined. 368 /// This directly corresponds to the tokenized AsmString after the mnemonic is 369 /// removed. 370 SmallVector<AsmOperand, 4> AsmOperands; 371 372 /// Predicates - The required subtarget features to match this instruction. 373 SmallVector<SubtargetFeatureInfo*, 4> RequiredFeatures; 374 375 /// ConversionFnKind - The enum value which is passed to the generated 376 /// ConvertToMCInst to convert parsed operands into an MCInst for this 377 /// function. 378 std::string ConversionFnKind; 379 380 MatchableInfo(const CodeGenInstruction &CGI) 381 : TheDef(CGI.TheDef), DefRec(&CGI), AsmString(CGI.AsmString) { 382 } 383 384 MatchableInfo(const CodeGenInstAlias *Alias) 385 : TheDef(Alias->TheDef), DefRec(Alias), AsmString(Alias->AsmString) { 386 } 387 388 void Initialize(const AsmMatcherInfo &Info, 389 SmallPtrSet<Record*, 16> &SingletonRegisters); 390 391 /// Validate - Return true if this matchable is a valid thing to match against 392 /// and perform a bunch of validity checking. 393 bool Validate(StringRef CommentDelimiter, bool Hack) const; 394 395 /// getSingletonRegisterForAsmOperand - If the specified token is a singleton 396 /// register, return the Record for it, otherwise return null. 397 Record *getSingletonRegisterForAsmOperand(unsigned i, 398 const AsmMatcherInfo &Info) const; 399 400 int FindAsmOperandNamed(StringRef N) const { 401 for (unsigned i = 0, e = AsmOperands.size(); i != e; ++i) 402 if (N == AsmOperands[i].SrcOpName) 403 return i; 404 return -1; 405 } 406 407 void BuildInstructionResultOperands(); 408 void BuildAliasResultOperands(); 409 410 /// operator< - Compare two matchables. 411 bool operator<(const MatchableInfo &RHS) const { 412 // The primary comparator is the instruction mnemonic. 413 if (Mnemonic != RHS.Mnemonic) 414 return Mnemonic < RHS.Mnemonic; 415 416 if (AsmOperands.size() != RHS.AsmOperands.size()) 417 return AsmOperands.size() < RHS.AsmOperands.size(); 418 419 // Compare lexicographically by operand. The matcher validates that other 420 // orderings wouldn't be ambiguous using \see CouldMatchAmiguouslyWith(). 421 for (unsigned i = 0, e = AsmOperands.size(); i != e; ++i) { 422 if (*AsmOperands[i].Class < *RHS.AsmOperands[i].Class) 423 return true; 424 if (*RHS.AsmOperands[i].Class < *AsmOperands[i].Class) 425 return false; 426 } 427 428 return false; 429 } 430 431 /// CouldMatchAmiguouslyWith - Check whether this matchable could 432 /// ambiguously match the same set of operands as \arg RHS (without being a 433 /// strictly superior match). 434 bool CouldMatchAmiguouslyWith(const MatchableInfo &RHS) { 435 // The primary comparator is the instruction mnemonic. 436 if (Mnemonic != RHS.Mnemonic) 437 return false; 438 439 // The number of operands is unambiguous. 440 if (AsmOperands.size() != RHS.AsmOperands.size()) 441 return false; 442 443 // Otherwise, make sure the ordering of the two instructions is unambiguous 444 // by checking that either (a) a token or operand kind discriminates them, 445 // or (b) the ordering among equivalent kinds is consistent. 446 447 // Tokens and operand kinds are unambiguous (assuming a correct target 448 // specific parser). 449 for (unsigned i = 0, e = AsmOperands.size(); i != e; ++i) 450 if (AsmOperands[i].Class->Kind != RHS.AsmOperands[i].Class->Kind || 451 AsmOperands[i].Class->Kind == ClassInfo::Token) 452 if (*AsmOperands[i].Class < *RHS.AsmOperands[i].Class || 453 *RHS.AsmOperands[i].Class < *AsmOperands[i].Class) 454 return false; 455 456 // Otherwise, this operand could commute if all operands are equivalent, or 457 // there is a pair of operands that compare less than and a pair that 458 // compare greater than. 459 bool HasLT = false, HasGT = false; 460 for (unsigned i = 0, e = AsmOperands.size(); i != e; ++i) { 461 if (*AsmOperands[i].Class < *RHS.AsmOperands[i].Class) 462 HasLT = true; 463 if (*RHS.AsmOperands[i].Class < *AsmOperands[i].Class) 464 HasGT = true; 465 } 466 467 return !(HasLT ^ HasGT); 468 } 469 470 void dump(); 471 472private: 473 void TokenizeAsmString(const AsmMatcherInfo &Info); 474}; 475 476/// SubtargetFeatureInfo - Helper class for storing information on a subtarget 477/// feature which participates in instruction matching. 478struct SubtargetFeatureInfo { 479 /// \brief The predicate record for this feature. 480 Record *TheDef; 481 482 /// \brief An unique index assigned to represent this feature. 483 unsigned Index; 484 485 SubtargetFeatureInfo(Record *D, unsigned Idx) : TheDef(D), Index(Idx) {} 486 487 /// \brief The name of the enumerated constant identifying this feature. 488 std::string getEnumName() const { 489 return "Feature_" + TheDef->getName(); 490 } 491}; 492 493class AsmMatcherInfo { 494public: 495 /// Tracked Records 496 RecordKeeper &Records; 497 498 /// The tablegen AsmParser record. 499 Record *AsmParser; 500 501 /// Target - The target information. 502 CodeGenTarget &Target; 503 504 /// The AsmParser "RegisterPrefix" value. 505 std::string RegisterPrefix; 506 507 /// The classes which are needed for matching. 508 std::vector<ClassInfo*> Classes; 509 510 /// The information on the matchables to match. 511 std::vector<MatchableInfo*> Matchables; 512 513 /// Map of Register records to their class information. 514 std::map<Record*, ClassInfo*> RegisterClasses; 515 516 /// Map of Predicate records to their subtarget information. 517 std::map<Record*, SubtargetFeatureInfo*> SubtargetFeatures; 518 519private: 520 /// Map of token to class information which has already been constructed. 521 std::map<std::string, ClassInfo*> TokenClasses; 522 523 /// Map of RegisterClass records to their class information. 524 std::map<Record*, ClassInfo*> RegisterClassClasses; 525 526 /// Map of AsmOperandClass records to their class information. 527 std::map<Record*, ClassInfo*> AsmOperandClasses; 528 529private: 530 /// getTokenClass - Lookup or create the class for the given token. 531 ClassInfo *getTokenClass(StringRef Token); 532 533 /// getOperandClass - Lookup or create the class for the given operand. 534 ClassInfo *getOperandClass(const CGIOperandList::OperandInfo &OI); 535 536 /// BuildRegisterClasses - Build the ClassInfo* instances for register 537 /// classes. 538 void BuildRegisterClasses(SmallPtrSet<Record*, 16> &SingletonRegisters); 539 540 /// BuildOperandClasses - Build the ClassInfo* instances for user defined 541 /// operand classes. 542 void BuildOperandClasses(); 543 544 void BuildInstructionOperandReference(MatchableInfo *II, 545 StringRef OpName, 546 MatchableInfo::AsmOperand &Op); 547 void BuildAliasOperandReference(MatchableInfo *II, 548 StringRef OpName, 549 MatchableInfo::AsmOperand &Op); 550 551public: 552 AsmMatcherInfo(Record *AsmParser, 553 CodeGenTarget &Target, 554 RecordKeeper &Records); 555 556 /// BuildInfo - Construct the various tables used during matching. 557 void BuildInfo(); 558 559 /// getSubtargetFeature - Lookup or create the subtarget feature info for the 560 /// given operand. 561 SubtargetFeatureInfo *getSubtargetFeature(Record *Def) const { 562 assert(Def->isSubClassOf("Predicate") && "Invalid predicate type!"); 563 std::map<Record*, SubtargetFeatureInfo*>::const_iterator I = 564 SubtargetFeatures.find(Def); 565 return I == SubtargetFeatures.end() ? 0 : I->second; 566 } 567 568 RecordKeeper &getRecords() const { 569 return Records; 570 } 571}; 572 573} 574 575void MatchableInfo::dump() { 576 errs() << TheDef->getName() << " -- " << "flattened:\"" << AsmString <<"\"\n"; 577 578 for (unsigned i = 0, e = AsmOperands.size(); i != e; ++i) { 579 AsmOperand &Op = AsmOperands[i]; 580 errs() << " op[" << i << "] = " << Op.Class->ClassName << " - "; 581 errs() << '\"' << Op.Token << "\"\n"; 582 } 583} 584 585void MatchableInfo::Initialize(const AsmMatcherInfo &Info, 586 SmallPtrSet<Record*, 16> &SingletonRegisters) { 587 // TODO: Eventually support asmparser for Variant != 0. 588 AsmString = CodeGenInstruction::FlattenAsmStringVariants(AsmString, 0); 589 590 TokenizeAsmString(Info); 591 592 // Compute the require features. 593 std::vector<Record*> Predicates =TheDef->getValueAsListOfDefs("Predicates"); 594 for (unsigned i = 0, e = Predicates.size(); i != e; ++i) 595 if (SubtargetFeatureInfo *Feature = 596 Info.getSubtargetFeature(Predicates[i])) 597 RequiredFeatures.push_back(Feature); 598 599 // Collect singleton registers, if used. 600 for (unsigned i = 0, e = AsmOperands.size(); i != e; ++i) { 601 if (Record *Reg = getSingletonRegisterForAsmOperand(i, Info)) 602 SingletonRegisters.insert(Reg); 603 } 604} 605 606/// TokenizeAsmString - Tokenize a simplified assembly string. 607void MatchableInfo::TokenizeAsmString(const AsmMatcherInfo &Info) { 608 StringRef String = AsmString; 609 unsigned Prev = 0; 610 bool InTok = true; 611 for (unsigned i = 0, e = String.size(); i != e; ++i) { 612 switch (String[i]) { 613 case '[': 614 case ']': 615 case '*': 616 case '!': 617 case ' ': 618 case '\t': 619 case ',': 620 if (InTok) { 621 AsmOperands.push_back(AsmOperand(String.slice(Prev, i))); 622 InTok = false; 623 } 624 if (!isspace(String[i]) && String[i] != ',') 625 AsmOperands.push_back(AsmOperand(String.substr(i, 1))); 626 Prev = i + 1; 627 break; 628 629 case '\\': 630 if (InTok) { 631 AsmOperands.push_back(AsmOperand(String.slice(Prev, i))); 632 InTok = false; 633 } 634 ++i; 635 assert(i != String.size() && "Invalid quoted character"); 636 AsmOperands.push_back(AsmOperand(String.substr(i, 1))); 637 Prev = i + 1; 638 break; 639 640 case '$': { 641 if (InTok) { 642 AsmOperands.push_back(AsmOperand(String.slice(Prev, i))); 643 InTok = false; 644 } 645 646 // If this isn't "${", treat like a normal token. 647 if (i + 1 == String.size() || String[i + 1] != '{') { 648 Prev = i; 649 break; 650 } 651 652 StringRef::iterator End = std::find(String.begin() + i, String.end(),'}'); 653 assert(End != String.end() && "Missing brace in operand reference!"); 654 size_t EndPos = End - String.begin(); 655 AsmOperands.push_back(AsmOperand(String.slice(i, EndPos+1))); 656 Prev = EndPos + 1; 657 i = EndPos; 658 break; 659 } 660 661 case '.': 662 if (InTok) 663 AsmOperands.push_back(AsmOperand(String.slice(Prev, i))); 664 Prev = i; 665 InTok = true; 666 break; 667 668 default: 669 InTok = true; 670 } 671 } 672 if (InTok && Prev != String.size()) 673 AsmOperands.push_back(AsmOperand(String.substr(Prev))); 674 675 // The first token of the instruction is the mnemonic, which must be a 676 // simple string, not a $foo variable or a singleton register. 677 assert(!AsmOperands.empty() && "Instruction has no tokens?"); 678 Mnemonic = AsmOperands[0].Token; 679 if (Mnemonic[0] == '$' || getSingletonRegisterForAsmOperand(0, Info)) 680 throw TGError(TheDef->getLoc(), 681 "Invalid instruction mnemonic '" + Mnemonic.str() + "'!"); 682 683 // Remove the first operand, it is tracked in the mnemonic field. 684 AsmOperands.erase(AsmOperands.begin()); 685} 686 687 688 689bool MatchableInfo::Validate(StringRef CommentDelimiter, bool Hack) const { 690 // Reject matchables with no .s string. 691 if (AsmString.empty()) 692 throw TGError(TheDef->getLoc(), "instruction with empty asm string"); 693 694 // Reject any matchables with a newline in them, they should be marked 695 // isCodeGenOnly if they are pseudo instructions. 696 if (AsmString.find('\n') != std::string::npos) 697 throw TGError(TheDef->getLoc(), 698 "multiline instruction is not valid for the asmparser, " 699 "mark it isCodeGenOnly"); 700 701 // Remove comments from the asm string. We know that the asmstring only 702 // has one line. 703 if (!CommentDelimiter.empty() && 704 StringRef(AsmString).find(CommentDelimiter) != StringRef::npos) 705 throw TGError(TheDef->getLoc(), 706 "asmstring for instruction has comment character in it, " 707 "mark it isCodeGenOnly"); 708 709 // Reject matchables with operand modifiers, these aren't something we can 710 /// handle, the target should be refactored to use operands instead of 711 /// modifiers. 712 // 713 // Also, check for instructions which reference the operand multiple times; 714 // this implies a constraint we would not honor. 715 std::set<std::string> OperandNames; 716 for (unsigned i = 0, e = AsmOperands.size(); i != e; ++i) { 717 StringRef Tok = AsmOperands[i].Token; 718 if (Tok[0] == '$' && Tok.find(':') != StringRef::npos) 719 throw TGError(TheDef->getLoc(), 720 "matchable with operand modifier '" + Tok.str() + 721 "' not supported by asm matcher. Mark isCodeGenOnly!"); 722 723 // Verify that any operand is only mentioned once. 724 // We reject aliases and ignore instructions for now. 725 if (Tok[0] == '$' && !OperandNames.insert(Tok).second) { 726 if (!Hack) 727 throw TGError(TheDef->getLoc(), 728 "ERROR: matchable with tied operand '" + Tok.str() + 729 "' can never be matched!"); 730 // FIXME: Should reject these. The ARM backend hits this with $lane in a 731 // bunch of instructions. It is unclear what the right answer is. 732 DEBUG({ 733 errs() << "warning: '" << TheDef->getName() << "': " 734 << "ignoring instruction with tied operand '" 735 << Tok.str() << "'\n"; 736 }); 737 return false; 738 } 739 } 740 741 return true; 742} 743 744 745/// getSingletonRegisterForAsmOperand - If the specified token is a singleton 746/// register, return the register name, otherwise return a null StringRef. 747Record *MatchableInfo:: 748getSingletonRegisterForAsmOperand(unsigned i, const AsmMatcherInfo &Info) const{ 749 StringRef Tok = AsmOperands[i].Token; 750 if (!Tok.startswith(Info.RegisterPrefix)) 751 return 0; 752 753 StringRef RegName = Tok.substr(Info.RegisterPrefix.size()); 754 if (const CodeGenRegister *Reg = Info.Target.getRegisterByName(RegName)) 755 return Reg->TheDef; 756 757 // If there is no register prefix (i.e. "%" in "%eax"), then this may 758 // be some random non-register token, just ignore it. 759 if (Info.RegisterPrefix.empty()) 760 return 0; 761 762 // Otherwise, we have something invalid prefixed with the register prefix, 763 // such as %foo. 764 std::string Err = "unable to find register for '" + RegName.str() + 765 "' (which matches register prefix)"; 766 throw TGError(TheDef->getLoc(), Err); 767} 768 769 770static std::string getEnumNameForToken(StringRef Str) { 771 std::string Res; 772 773 for (StringRef::iterator it = Str.begin(), ie = Str.end(); it != ie; ++it) { 774 switch (*it) { 775 case '*': Res += "_STAR_"; break; 776 case '%': Res += "_PCT_"; break; 777 case ':': Res += "_COLON_"; break; 778 case '!': Res += "_EXCLAIM_"; break; 779 default: 780 if (isalnum(*it)) 781 Res += *it; 782 else 783 Res += "_" + utostr((unsigned) *it) + "_"; 784 } 785 } 786 787 return Res; 788} 789 790ClassInfo *AsmMatcherInfo::getTokenClass(StringRef Token) { 791 ClassInfo *&Entry = TokenClasses[Token]; 792 793 if (!Entry) { 794 Entry = new ClassInfo(); 795 Entry->Kind = ClassInfo::Token; 796 Entry->ClassName = "Token"; 797 Entry->Name = "MCK_" + getEnumNameForToken(Token); 798 Entry->ValueName = Token; 799 Entry->PredicateMethod = "<invalid>"; 800 Entry->RenderMethod = "<invalid>"; 801 Classes.push_back(Entry); 802 } 803 804 return Entry; 805} 806 807ClassInfo * 808AsmMatcherInfo::getOperandClass(const CGIOperandList::OperandInfo &OI) { 809 if (OI.Rec->isSubClassOf("RegisterClass")) { 810 if (ClassInfo *CI = RegisterClassClasses[OI.Rec]) 811 return CI; 812 throw TGError(OI.Rec->getLoc(), "register class has no class info!"); 813 } 814 815 assert(OI.Rec->isSubClassOf("Operand") && "Unexpected operand!"); 816 Record *MatchClass = OI.Rec->getValueAsDef("ParserMatchClass"); 817 if (ClassInfo *CI = AsmOperandClasses[MatchClass]) 818 return CI; 819 820 throw TGError(OI.Rec->getLoc(), "operand has no match class!"); 821} 822 823void AsmMatcherInfo:: 824BuildRegisterClasses(SmallPtrSet<Record*, 16> &SingletonRegisters) { 825 const std::vector<CodeGenRegister> &Registers = Target.getRegisters(); 826 const std::vector<CodeGenRegisterClass> &RegClassList = 827 Target.getRegisterClasses(); 828 829 // The register sets used for matching. 830 std::set< std::set<Record*> > RegisterSets; 831 832 // Gather the defined sets. 833 for (std::vector<CodeGenRegisterClass>::const_iterator it = 834 RegClassList.begin(), ie = RegClassList.end(); it != ie; ++it) 835 RegisterSets.insert(std::set<Record*>(it->Elements.begin(), 836 it->Elements.end())); 837 838 // Add any required singleton sets. 839 for (SmallPtrSet<Record*, 16>::iterator it = SingletonRegisters.begin(), 840 ie = SingletonRegisters.end(); it != ie; ++it) { 841 Record *Rec = *it; 842 RegisterSets.insert(std::set<Record*>(&Rec, &Rec + 1)); 843 } 844 845 // Introduce derived sets where necessary (when a register does not determine 846 // a unique register set class), and build the mapping of registers to the set 847 // they should classify to. 848 std::map<Record*, std::set<Record*> > RegisterMap; 849 for (std::vector<CodeGenRegister>::const_iterator it = Registers.begin(), 850 ie = Registers.end(); it != ie; ++it) { 851 const CodeGenRegister &CGR = *it; 852 // Compute the intersection of all sets containing this register. 853 std::set<Record*> ContainingSet; 854 855 for (std::set< std::set<Record*> >::iterator it = RegisterSets.begin(), 856 ie = RegisterSets.end(); it != ie; ++it) { 857 if (!it->count(CGR.TheDef)) 858 continue; 859 860 if (ContainingSet.empty()) { 861 ContainingSet = *it; 862 continue; 863 } 864 865 std::set<Record*> Tmp; 866 std::swap(Tmp, ContainingSet); 867 std::insert_iterator< std::set<Record*> > II(ContainingSet, 868 ContainingSet.begin()); 869 std::set_intersection(Tmp.begin(), Tmp.end(), it->begin(), it->end(), II); 870 } 871 872 if (!ContainingSet.empty()) { 873 RegisterSets.insert(ContainingSet); 874 RegisterMap.insert(std::make_pair(CGR.TheDef, ContainingSet)); 875 } 876 } 877 878 // Construct the register classes. 879 std::map<std::set<Record*>, ClassInfo*> RegisterSetClasses; 880 unsigned Index = 0; 881 for (std::set< std::set<Record*> >::iterator it = RegisterSets.begin(), 882 ie = RegisterSets.end(); it != ie; ++it, ++Index) { 883 ClassInfo *CI = new ClassInfo(); 884 CI->Kind = ClassInfo::RegisterClass0 + Index; 885 CI->ClassName = "Reg" + utostr(Index); 886 CI->Name = "MCK_Reg" + utostr(Index); 887 CI->ValueName = ""; 888 CI->PredicateMethod = ""; // unused 889 CI->RenderMethod = "addRegOperands"; 890 CI->Registers = *it; 891 Classes.push_back(CI); 892 RegisterSetClasses.insert(std::make_pair(*it, CI)); 893 } 894 895 // Find the superclasses; we could compute only the subgroup lattice edges, 896 // but there isn't really a point. 897 for (std::set< std::set<Record*> >::iterator it = RegisterSets.begin(), 898 ie = RegisterSets.end(); it != ie; ++it) { 899 ClassInfo *CI = RegisterSetClasses[*it]; 900 for (std::set< std::set<Record*> >::iterator it2 = RegisterSets.begin(), 901 ie2 = RegisterSets.end(); it2 != ie2; ++it2) 902 if (*it != *it2 && 903 std::includes(it2->begin(), it2->end(), it->begin(), it->end())) 904 CI->SuperClasses.push_back(RegisterSetClasses[*it2]); 905 } 906 907 // Name the register classes which correspond to a user defined RegisterClass. 908 for (std::vector<CodeGenRegisterClass>::const_iterator 909 it = RegClassList.begin(), ie = RegClassList.end(); it != ie; ++it) { 910 ClassInfo *CI = RegisterSetClasses[std::set<Record*>(it->Elements.begin(), 911 it->Elements.end())]; 912 if (CI->ValueName.empty()) { 913 CI->ClassName = it->getName(); 914 CI->Name = "MCK_" + it->getName(); 915 CI->ValueName = it->getName(); 916 } else 917 CI->ValueName = CI->ValueName + "," + it->getName(); 918 919 RegisterClassClasses.insert(std::make_pair(it->TheDef, CI)); 920 } 921 922 // Populate the map for individual registers. 923 for (std::map<Record*, std::set<Record*> >::iterator it = RegisterMap.begin(), 924 ie = RegisterMap.end(); it != ie; ++it) 925 RegisterClasses[it->first] = RegisterSetClasses[it->second]; 926 927 // Name the register classes which correspond to singleton registers. 928 for (SmallPtrSet<Record*, 16>::iterator it = SingletonRegisters.begin(), 929 ie = SingletonRegisters.end(); it != ie; ++it) { 930 Record *Rec = *it; 931 ClassInfo *CI = RegisterClasses[Rec]; 932 assert(CI && "Missing singleton register class info!"); 933 934 if (CI->ValueName.empty()) { 935 CI->ClassName = Rec->getName(); 936 CI->Name = "MCK_" + Rec->getName(); 937 CI->ValueName = Rec->getName(); 938 } else 939 CI->ValueName = CI->ValueName + "," + Rec->getName(); 940 } 941} 942 943void AsmMatcherInfo::BuildOperandClasses() { 944 std::vector<Record*> AsmOperands = 945 Records.getAllDerivedDefinitions("AsmOperandClass"); 946 947 // Pre-populate AsmOperandClasses map. 948 for (std::vector<Record*>::iterator it = AsmOperands.begin(), 949 ie = AsmOperands.end(); it != ie; ++it) 950 AsmOperandClasses[*it] = new ClassInfo(); 951 952 unsigned Index = 0; 953 for (std::vector<Record*>::iterator it = AsmOperands.begin(), 954 ie = AsmOperands.end(); it != ie; ++it, ++Index) { 955 ClassInfo *CI = AsmOperandClasses[*it]; 956 CI->Kind = ClassInfo::UserClass0 + Index; 957 958 ListInit *Supers = (*it)->getValueAsListInit("SuperClasses"); 959 for (unsigned i = 0, e = Supers->getSize(); i != e; ++i) { 960 DefInit *DI = dynamic_cast<DefInit*>(Supers->getElement(i)); 961 if (!DI) { 962 PrintError((*it)->getLoc(), "Invalid super class reference!"); 963 continue; 964 } 965 966 ClassInfo *SC = AsmOperandClasses[DI->getDef()]; 967 if (!SC) 968 PrintError((*it)->getLoc(), "Invalid super class reference!"); 969 else 970 CI->SuperClasses.push_back(SC); 971 } 972 CI->ClassName = (*it)->getValueAsString("Name"); 973 CI->Name = "MCK_" + CI->ClassName; 974 CI->ValueName = (*it)->getName(); 975 976 // Get or construct the predicate method name. 977 Init *PMName = (*it)->getValueInit("PredicateMethod"); 978 if (StringInit *SI = dynamic_cast<StringInit*>(PMName)) { 979 CI->PredicateMethod = SI->getValue(); 980 } else { 981 assert(dynamic_cast<UnsetInit*>(PMName) && 982 "Unexpected PredicateMethod field!"); 983 CI->PredicateMethod = "is" + CI->ClassName; 984 } 985 986 // Get or construct the render method name. 987 Init *RMName = (*it)->getValueInit("RenderMethod"); 988 if (StringInit *SI = dynamic_cast<StringInit*>(RMName)) { 989 CI->RenderMethod = SI->getValue(); 990 } else { 991 assert(dynamic_cast<UnsetInit*>(RMName) && 992 "Unexpected RenderMethod field!"); 993 CI->RenderMethod = "add" + CI->ClassName + "Operands"; 994 } 995 996 AsmOperandClasses[*it] = CI; 997 Classes.push_back(CI); 998 } 999} 1000 1001AsmMatcherInfo::AsmMatcherInfo(Record *asmParser, 1002 CodeGenTarget &target, 1003 RecordKeeper &records) 1004 : Records(records), AsmParser(asmParser), Target(target), 1005 RegisterPrefix(AsmParser->getValueAsString("RegisterPrefix")) { 1006} 1007 1008 1009void AsmMatcherInfo::BuildInfo() { 1010 // Build information about all of the AssemblerPredicates. 1011 std::vector<Record*> AllPredicates = 1012 Records.getAllDerivedDefinitions("Predicate"); 1013 for (unsigned i = 0, e = AllPredicates.size(); i != e; ++i) { 1014 Record *Pred = AllPredicates[i]; 1015 // Ignore predicates that are not intended for the assembler. 1016 if (!Pred->getValueAsBit("AssemblerMatcherPredicate")) 1017 continue; 1018 1019 if (Pred->getName().empty()) 1020 throw TGError(Pred->getLoc(), "Predicate has no name!"); 1021 1022 unsigned FeatureNo = SubtargetFeatures.size(); 1023 SubtargetFeatures[Pred] = new SubtargetFeatureInfo(Pred, FeatureNo); 1024 assert(FeatureNo < 32 && "Too many subtarget features!"); 1025 } 1026 1027 StringRef CommentDelimiter = AsmParser->getValueAsString("CommentDelimiter"); 1028 1029 // Parse the instructions; we need to do this first so that we can gather the 1030 // singleton register classes. 1031 SmallPtrSet<Record*, 16> SingletonRegisters; 1032 for (CodeGenTarget::inst_iterator I = Target.inst_begin(), 1033 E = Target.inst_end(); I != E; ++I) { 1034 const CodeGenInstruction &CGI = **I; 1035 1036 // If the tblgen -match-prefix option is specified (for tblgen hackers), 1037 // filter the set of instructions we consider. 1038 if (!StringRef(CGI.TheDef->getName()).startswith(MatchPrefix)) 1039 continue; 1040 1041 // Ignore "codegen only" instructions. 1042 if (CGI.TheDef->getValueAsBit("isCodeGenOnly")) 1043 continue; 1044 1045 // Validate the operand list to ensure we can handle this instruction. 1046 for (unsigned i = 0, e = CGI.Operands.size(); i != e; ++i) { 1047 const CGIOperandList::OperandInfo &OI = CGI.Operands[i]; 1048 1049 // Validate tied operands. 1050 if (OI.getTiedRegister() != -1) { 1051 // If we have a tied operand that consists of multiple MCOperands, reject 1052 // it. We reject aliases and ignore instructions for now. 1053 if (OI.MINumOperands != 1) { 1054 // FIXME: Should reject these. The ARM backend hits this with $lane 1055 // in a bunch of instructions. It is unclear what the right answer is. 1056 DEBUG({ 1057 errs() << "warning: '" << CGI.TheDef->getName() << "': " 1058 << "ignoring instruction with multi-operand tied operand '" 1059 << OI.Name << "'\n"; 1060 }); 1061 continue; 1062 } 1063 } 1064 } 1065 1066 OwningPtr<MatchableInfo> II(new MatchableInfo(CGI)); 1067 1068 II->Initialize(*this, SingletonRegisters); 1069 1070 // Ignore instructions which shouldn't be matched and diagnose invalid 1071 // instruction definitions with an error. 1072 if (!II->Validate(CommentDelimiter, true)) 1073 continue; 1074 1075 // Ignore "Int_*" and "*_Int" instructions, which are internal aliases. 1076 // 1077 // FIXME: This is a total hack. 1078 if (StringRef(II->TheDef->getName()).startswith("Int_") || 1079 StringRef(II->TheDef->getName()).endswith("_Int")) 1080 continue; 1081 1082 Matchables.push_back(II.take()); 1083 } 1084 1085 // Parse all of the InstAlias definitions and stick them in the list of 1086 // matchables. 1087 std::vector<Record*> AllInstAliases = 1088 Records.getAllDerivedDefinitions("InstAlias"); 1089 for (unsigned i = 0, e = AllInstAliases.size(); i != e; ++i) { 1090 CodeGenInstAlias *Alias = new CodeGenInstAlias(AllInstAliases[i], Target); 1091 1092 OwningPtr<MatchableInfo> II(new MatchableInfo(Alias)); 1093 1094 II->Initialize(*this, SingletonRegisters); 1095 1096 // Validate the alias definitions. 1097 II->Validate(CommentDelimiter, false); 1098 1099 Matchables.push_back(II.take()); 1100 } 1101 1102 // Build info for the register classes. 1103 BuildRegisterClasses(SingletonRegisters); 1104 1105 // Build info for the user defined assembly operand classes. 1106 BuildOperandClasses(); 1107 1108 // Build the information about matchables, now that we have fully formed 1109 // classes. 1110 for (std::vector<MatchableInfo*>::iterator it = Matchables.begin(), 1111 ie = Matchables.end(); it != ie; ++it) { 1112 MatchableInfo *II = *it; 1113 1114 // Parse the tokens after the mnemonic. 1115 for (unsigned i = 0, e = II->AsmOperands.size(); i != e; ++i) { 1116 MatchableInfo::AsmOperand &Op = II->AsmOperands[i]; 1117 StringRef Token = Op.Token; 1118 1119 // Check for singleton registers. 1120 if (Record *RegRecord = II->getSingletonRegisterForAsmOperand(i, *this)) { 1121 Op.Class = RegisterClasses[RegRecord]; 1122 assert(Op.Class && Op.Class->Registers.size() == 1 && 1123 "Unexpected class for singleton register"); 1124 continue; 1125 } 1126 1127 // Check for simple tokens. 1128 if (Token[0] != '$') { 1129 Op.Class = getTokenClass(Token); 1130 continue; 1131 } 1132 1133 if (Token.size() > 1 && isdigit(Token[1])) { 1134 Op.Class = getTokenClass(Token); 1135 continue; 1136 } 1137 1138 // Otherwise this is an operand reference. 1139 StringRef OperandName; 1140 if (Token[1] == '{') 1141 OperandName = Token.substr(2, Token.size() - 3); 1142 else 1143 OperandName = Token.substr(1); 1144 1145 if (II->DefRec.is<const CodeGenInstruction*>()) 1146 BuildInstructionOperandReference(II, OperandName, Op); 1147 else 1148 BuildAliasOperandReference(II, OperandName, Op); 1149 } 1150 1151 if (II->DefRec.is<const CodeGenInstruction*>()) 1152 II->BuildInstructionResultOperands(); 1153 else 1154 II->BuildAliasResultOperands(); 1155 } 1156 1157 // Reorder classes so that classes preceed super classes. 1158 std::sort(Classes.begin(), Classes.end(), less_ptr<ClassInfo>()); 1159} 1160 1161/// BuildInstructionOperandReference - The specified operand is a reference to a 1162/// named operand such as $src. Resolve the Class and OperandInfo pointers. 1163void AsmMatcherInfo:: 1164BuildInstructionOperandReference(MatchableInfo *II, 1165 StringRef OperandName, 1166 MatchableInfo::AsmOperand &Op) { 1167 const CodeGenInstruction &CGI = *II->DefRec.get<const CodeGenInstruction*>(); 1168 const CGIOperandList &Operands = CGI.Operands; 1169 1170 // Map this token to an operand. 1171 unsigned Idx; 1172 if (!Operands.hasOperandNamed(OperandName, Idx)) 1173 throw TGError(II->TheDef->getLoc(), "error: unable to find operand: '" + 1174 OperandName.str() + "'"); 1175 1176 // Set up the operand class. 1177 Op.Class = getOperandClass(Operands[Idx]); 1178 1179 // If the named operand is tied, canonicalize it to the untied operand. 1180 // For example, something like: 1181 // (outs GPR:$dst), (ins GPR:$src) 1182 // with an asmstring of 1183 // "inc $src" 1184 // we want to canonicalize to: 1185 // "inc $dst" 1186 // so that we know how to provide the $dst operand when filling in the result. 1187 int OITied = Operands[Idx].getTiedRegister(); 1188 if (OITied != -1) { 1189 // The tied operand index is an MIOperand index, find the operand that 1190 // contains it. 1191 for (unsigned i = 0, e = Operands.size(); i != e; ++i) { 1192 if (Operands[i].MIOperandNo == unsigned(OITied)) { 1193 OperandName = Operands[i].Name; 1194 break; 1195 } 1196 } 1197 } 1198 1199 Op.SrcOpName = OperandName; 1200} 1201 1202/// BuildAliasOperandReference - When parsing an operand reference out of the 1203/// matching string (e.g. "movsx $src, $dst"), determine what the class of the 1204/// operand reference is by looking it up in the result pattern definition. 1205void AsmMatcherInfo::BuildAliasOperandReference(MatchableInfo *II, 1206 StringRef OperandName, 1207 MatchableInfo::AsmOperand &Op) { 1208 const CodeGenInstAlias &CGA = *II->DefRec.get<const CodeGenInstAlias*>(); 1209 1210 // Set up the operand class. 1211 for (unsigned i = 0, e = CGA.ResultOperands.size(); i != e; ++i) 1212 if (CGA.ResultOperands[i].isRecord() && 1213 CGA.ResultOperands[i].getName() == OperandName) { 1214 // It's safe to go with the first one we find, because CodeGenInstAlias 1215 // validates that all operands with the same name have the same record. 1216 unsigned ResultIdx = CGA.ResultInstOperandIndex[i]; 1217 Op.Class = getOperandClass(CGA.ResultInst->Operands[ResultIdx]); 1218 Op.SrcOpName = OperandName; 1219 return; 1220 } 1221 1222 throw TGError(II->TheDef->getLoc(), "error: unable to find operand: '" + 1223 OperandName.str() + "'"); 1224} 1225 1226void MatchableInfo::BuildInstructionResultOperands() { 1227 const CodeGenInstruction *ResultInst = getResultInst(); 1228 1229 // Loop over all operands of the result instruction, determining how to 1230 // populate them. 1231 for (unsigned i = 0, e = ResultInst->Operands.size(); i != e; ++i) { 1232 const CGIOperandList::OperandInfo &OpInfo = ResultInst->Operands[i]; 1233 1234 // If this is a tied operand, just copy from the previously handled operand. 1235 int TiedOp = OpInfo.getTiedRegister(); 1236 if (TiedOp != -1) { 1237 ResOperands.push_back(ResOperand::getTiedOp(TiedOp, &OpInfo)); 1238 continue; 1239 } 1240 1241 // Find out what operand from the asmparser that this MCInst operand comes 1242 // from. 1243 int SrcOperand = FindAsmOperandNamed(OpInfo.Name); 1244 1245 if (!OpInfo.Name.empty() && SrcOperand != -1) { 1246 ResOperands.push_back(ResOperand::getRenderedOp(SrcOperand, &OpInfo)); 1247 continue; 1248 } 1249 1250 throw TGError(TheDef->getLoc(), "Instruction '" + 1251 TheDef->getName() + "' has operand '" + OpInfo.Name + 1252 "' that doesn't appear in asm string!"); 1253 } 1254} 1255 1256void MatchableInfo::BuildAliasResultOperands() { 1257 const CodeGenInstAlias &CGA = *DefRec.get<const CodeGenInstAlias*>(); 1258 const CodeGenInstruction *ResultInst = getResultInst(); 1259 1260 // Loop over all operands of the result instruction, determining how to 1261 // populate them. 1262 unsigned AliasOpNo = 0; 1263 for (unsigned i = 0, e = ResultInst->Operands.size(); i != e; ++i) { 1264 const CGIOperandList::OperandInfo &OpInfo = ResultInst->Operands[i]; 1265 1266 // If this is a tied operand, just copy from the previously handled operand. 1267 int TiedOp = OpInfo.getTiedRegister(); 1268 if (TiedOp != -1) { 1269 ResOperands.push_back(ResOperand::getTiedOp(TiedOp, &OpInfo)); 1270 continue; 1271 } 1272 1273 // Find out what operand from the asmparser that this MCInst operand comes 1274 // from. 1275 switch (CGA.ResultOperands[AliasOpNo].Kind) { 1276 case CodeGenInstAlias::ResultOperand::K_Record: { 1277 StringRef Name = CGA.ResultOperands[AliasOpNo++].getName(); 1278 int SrcOperand = FindAsmOperandNamed(Name); 1279 if (SrcOperand != -1) { 1280 ResOperands.push_back(ResOperand::getRenderedOp(SrcOperand, &OpInfo)); 1281 continue; 1282 } 1283 1284 throw TGError(TheDef->getLoc(), "Instruction '" + 1285 TheDef->getName() + "' has operand '" + OpInfo.Name + 1286 "' that doesn't appear in asm string!"); 1287 } 1288 case CodeGenInstAlias::ResultOperand::K_Imm: { 1289 int64_t ImmVal = CGA.ResultOperands[AliasOpNo++].getImm(); 1290 ResOperands.push_back(ResOperand::getImmOp(ImmVal, &OpInfo)); 1291 continue; 1292 } 1293 1294 case CodeGenInstAlias::ResultOperand::K_Reg: { 1295 Record *Reg = CGA.ResultOperands[AliasOpNo++].getRegister(); 1296 ResOperands.push_back(ResOperand::getRegOp(Reg, &OpInfo)); 1297 continue; 1298 } 1299 } 1300 } 1301} 1302 1303static void EmitConvertToMCInst(CodeGenTarget &Target, 1304 std::vector<MatchableInfo*> &Infos, 1305 raw_ostream &OS) { 1306 // Write the convert function to a separate stream, so we can drop it after 1307 // the enum. 1308 std::string ConvertFnBody; 1309 raw_string_ostream CvtOS(ConvertFnBody); 1310 1311 // Function we have already generated. 1312 std::set<std::string> GeneratedFns; 1313 1314 // Start the unified conversion function. 1315 CvtOS << "static void ConvertToMCInst(ConversionKind Kind, MCInst &Inst, " 1316 << "unsigned Opcode,\n" 1317 << " const SmallVectorImpl<MCParsedAsmOperand*" 1318 << "> &Operands) {\n"; 1319 CvtOS << " Inst.setOpcode(Opcode);\n"; 1320 CvtOS << " switch (Kind) {\n"; 1321 CvtOS << " default:\n"; 1322 1323 // Start the enum, which we will generate inline. 1324 1325 OS << "// Unified function for converting operands to MCInst instances.\n\n"; 1326 OS << "enum ConversionKind {\n"; 1327 1328 // TargetOperandClass - This is the target's operand class, like X86Operand. 1329 std::string TargetOperandClass = Target.getName() + "Operand"; 1330 1331 for (std::vector<MatchableInfo*>::const_iterator it = Infos.begin(), 1332 ie = Infos.end(); it != ie; ++it) { 1333 MatchableInfo &II = **it; 1334 1335 // Build the conversion function signature. 1336 std::string Signature = "Convert"; 1337 std::string CaseBody; 1338 raw_string_ostream CaseOS(CaseBody); 1339 1340 // Compute the convert enum and the case body. 1341 for (unsigned i = 0, e = II.ResOperands.size(); i != e; ++i) { 1342 const MatchableInfo::ResOperand &OpInfo = II.ResOperands[i]; 1343 1344 // Generate code to populate each result operand. 1345 switch (OpInfo.Kind) { 1346 case MatchableInfo::ResOperand::RenderAsmOperand: { 1347 // This comes from something we parsed. 1348 MatchableInfo::AsmOperand &Op = II.AsmOperands[OpInfo.AsmOperandNum]; 1349 1350 // Registers are always converted the same, don't duplicate the 1351 // conversion function based on them. 1352 Signature += "__"; 1353 if (Op.Class->isRegisterClass()) 1354 Signature += "Reg"; 1355 else 1356 Signature += Op.Class->ClassName; 1357 Signature += utostr(OpInfo.OpInfo->MINumOperands); 1358 Signature += "_" + itostr(OpInfo.AsmOperandNum); 1359 1360 CaseOS << " ((" << TargetOperandClass << "*)Operands[" 1361 << (OpInfo.AsmOperandNum+1) << "])->" << Op.Class->RenderMethod 1362 << "(Inst, " << OpInfo.OpInfo->MINumOperands << ");\n"; 1363 break; 1364 } 1365 1366 case MatchableInfo::ResOperand::TiedOperand: { 1367 // If this operand is tied to a previous one, just copy the MCInst 1368 // operand from the earlier one.We can only tie single MCOperand values. 1369 //assert(OpInfo.OpInfo->MINumOperands == 1 && "Not a singular MCOperand"); 1370 unsigned TiedOp = OpInfo.TiedOperandNum; 1371 assert(i > TiedOp && "Tied operand preceeds its target!"); 1372 CaseOS << " Inst.addOperand(Inst.getOperand(" << TiedOp << "));\n"; 1373 Signature += "__Tie" + utostr(TiedOp); 1374 break; 1375 } 1376 case MatchableInfo::ResOperand::ImmOperand: { 1377 int64_t Val = OpInfo.ImmVal; 1378 CaseOS << " Inst.addOperand(MCOperand::CreateImm(" << Val << "));\n"; 1379 Signature += "__imm" + itostr(Val); 1380 break; 1381 } 1382 case MatchableInfo::ResOperand::RegOperand: { 1383 if (OpInfo.Register == 0) { 1384 CaseOS << " Inst.addOperand(MCOperand::CreateReg(0));\n"; 1385 Signature += "__reg0"; 1386 } else { 1387 std::string N = getQualifiedName(OpInfo.Register); 1388 CaseOS << " Inst.addOperand(MCOperand::CreateReg(" << N << "));\n"; 1389 Signature += "__reg" + OpInfo.Register->getName(); 1390 } 1391 } 1392 } 1393 } 1394 1395 II.ConversionFnKind = Signature; 1396 1397 // Check if we have already generated this signature. 1398 if (!GeneratedFns.insert(Signature).second) 1399 continue; 1400 1401 // If not, emit it now. Add to the enum list. 1402 OS << " " << Signature << ",\n"; 1403 1404 CvtOS << " case " << Signature << ":\n"; 1405 CvtOS << CaseOS.str(); 1406 CvtOS << " return;\n"; 1407 } 1408 1409 // Finish the convert function. 1410 1411 CvtOS << " }\n"; 1412 CvtOS << "}\n\n"; 1413 1414 // Finish the enum, and drop the convert function after it. 1415 1416 OS << " NumConversionVariants\n"; 1417 OS << "};\n\n"; 1418 1419 OS << CvtOS.str(); 1420} 1421 1422/// EmitMatchClassEnumeration - Emit the enumeration for match class kinds. 1423static void EmitMatchClassEnumeration(CodeGenTarget &Target, 1424 std::vector<ClassInfo*> &Infos, 1425 raw_ostream &OS) { 1426 OS << "namespace {\n\n"; 1427 1428 OS << "/// MatchClassKind - The kinds of classes which participate in\n" 1429 << "/// instruction matching.\n"; 1430 OS << "enum MatchClassKind {\n"; 1431 OS << " InvalidMatchClass = 0,\n"; 1432 for (std::vector<ClassInfo*>::iterator it = Infos.begin(), 1433 ie = Infos.end(); it != ie; ++it) { 1434 ClassInfo &CI = **it; 1435 OS << " " << CI.Name << ", // "; 1436 if (CI.Kind == ClassInfo::Token) { 1437 OS << "'" << CI.ValueName << "'\n"; 1438 } else if (CI.isRegisterClass()) { 1439 if (!CI.ValueName.empty()) 1440 OS << "register class '" << CI.ValueName << "'\n"; 1441 else 1442 OS << "derived register class\n"; 1443 } else { 1444 OS << "user defined class '" << CI.ValueName << "'\n"; 1445 } 1446 } 1447 OS << " NumMatchClassKinds\n"; 1448 OS << "};\n\n"; 1449 1450 OS << "}\n\n"; 1451} 1452 1453/// EmitClassifyOperand - Emit the function to classify an operand. 1454static void EmitClassifyOperand(AsmMatcherInfo &Info, 1455 raw_ostream &OS) { 1456 OS << "static MatchClassKind ClassifyOperand(MCParsedAsmOperand *GOp) {\n" 1457 << " " << Info.Target.getName() << "Operand &Operand = *(" 1458 << Info.Target.getName() << "Operand*)GOp;\n"; 1459 1460 // Classify tokens. 1461 OS << " if (Operand.isToken())\n"; 1462 OS << " return MatchTokenString(Operand.getToken());\n\n"; 1463 1464 // Classify registers. 1465 // 1466 // FIXME: Don't hardcode isReg, getReg. 1467 OS << " if (Operand.isReg()) {\n"; 1468 OS << " switch (Operand.getReg()) {\n"; 1469 OS << " default: return InvalidMatchClass;\n"; 1470 for (std::map<Record*, ClassInfo*>::iterator 1471 it = Info.RegisterClasses.begin(), ie = Info.RegisterClasses.end(); 1472 it != ie; ++it) 1473 OS << " case " << Info.Target.getName() << "::" 1474 << it->first->getName() << ": return " << it->second->Name << ";\n"; 1475 OS << " }\n"; 1476 OS << " }\n\n"; 1477 1478 // Classify user defined operands. To do so, we need to perform a topological 1479 // sort of the superclass relationship graph so that we always match the 1480 // narrowest type first. 1481 1482 // Collect the incoming edge counts for each class. 1483 std::map<ClassInfo*, unsigned> IncomingEdges; 1484 for (std::vector<ClassInfo*>::iterator it = Info.Classes.begin(), 1485 ie = Info.Classes.end(); it != ie; ++it) { 1486 ClassInfo &CI = **it; 1487 1488 if (!CI.isUserClass()) 1489 continue; 1490 1491 for (std::vector<ClassInfo*>::iterator SI = CI.SuperClasses.begin(), 1492 SE = CI.SuperClasses.end(); SI != SE; ++SI) 1493 ++IncomingEdges[*SI]; 1494 } 1495 1496 // Initialize a worklist of classes with no incoming edges. 1497 std::vector<ClassInfo*> LeafClasses; 1498 for (std::vector<ClassInfo*>::iterator it = Info.Classes.begin(), 1499 ie = Info.Classes.end(); it != ie; ++it) { 1500 if (!IncomingEdges[*it]) 1501 LeafClasses.push_back(*it); 1502 } 1503 1504 // Iteratively pop the list, process that class, and update the incoming 1505 // edge counts for its super classes. When a superclass reaches zero 1506 // incoming edges, push it onto the worklist for processing. 1507 while (!LeafClasses.empty()) { 1508 ClassInfo &CI = *LeafClasses.back(); 1509 LeafClasses.pop_back(); 1510 1511 if (!CI.isUserClass()) 1512 continue; 1513 1514 OS << " // '" << CI.ClassName << "' class"; 1515 if (!CI.SuperClasses.empty()) { 1516 OS << ", subclass of "; 1517 for (unsigned i = 0, e = CI.SuperClasses.size(); i != e; ++i) { 1518 if (i) OS << ", "; 1519 OS << "'" << CI.SuperClasses[i]->ClassName << "'"; 1520 assert(CI < *CI.SuperClasses[i] && "Invalid class relation!"); 1521 1522 --IncomingEdges[CI.SuperClasses[i]]; 1523 if (!IncomingEdges[CI.SuperClasses[i]]) 1524 LeafClasses.push_back(CI.SuperClasses[i]); 1525 } 1526 } 1527 OS << "\n"; 1528 1529 OS << " if (Operand." << CI.PredicateMethod << "()) {\n"; 1530 1531 // Validate subclass relationships. 1532 if (!CI.SuperClasses.empty()) { 1533 for (unsigned i = 0, e = CI.SuperClasses.size(); i != e; ++i) 1534 OS << " assert(Operand." << CI.SuperClasses[i]->PredicateMethod 1535 << "() && \"Invalid class relationship!\");\n"; 1536 } 1537 1538 OS << " return " << CI.Name << ";\n"; 1539 OS << " }\n\n"; 1540 } 1541 1542 OS << " return InvalidMatchClass;\n"; 1543 OS << "}\n\n"; 1544} 1545 1546/// EmitIsSubclass - Emit the subclass predicate function. 1547static void EmitIsSubclass(CodeGenTarget &Target, 1548 std::vector<ClassInfo*> &Infos, 1549 raw_ostream &OS) { 1550 OS << "/// IsSubclass - Compute whether \\arg A is a subclass of \\arg B.\n"; 1551 OS << "static bool IsSubclass(MatchClassKind A, MatchClassKind B) {\n"; 1552 OS << " if (A == B)\n"; 1553 OS << " return true;\n\n"; 1554 1555 OS << " switch (A) {\n"; 1556 OS << " default:\n"; 1557 OS << " return false;\n"; 1558 for (std::vector<ClassInfo*>::iterator it = Infos.begin(), 1559 ie = Infos.end(); it != ie; ++it) { 1560 ClassInfo &A = **it; 1561 1562 if (A.Kind != ClassInfo::Token) { 1563 std::vector<StringRef> SuperClasses; 1564 for (std::vector<ClassInfo*>::iterator it = Infos.begin(), 1565 ie = Infos.end(); it != ie; ++it) { 1566 ClassInfo &B = **it; 1567 1568 if (&A != &B && A.isSubsetOf(B)) 1569 SuperClasses.push_back(B.Name); 1570 } 1571 1572 if (SuperClasses.empty()) 1573 continue; 1574 1575 OS << "\n case " << A.Name << ":\n"; 1576 1577 if (SuperClasses.size() == 1) { 1578 OS << " return B == " << SuperClasses.back() << ";\n"; 1579 continue; 1580 } 1581 1582 OS << " switch (B) {\n"; 1583 OS << " default: return false;\n"; 1584 for (unsigned i = 0, e = SuperClasses.size(); i != e; ++i) 1585 OS << " case " << SuperClasses[i] << ": return true;\n"; 1586 OS << " }\n"; 1587 } 1588 } 1589 OS << " }\n"; 1590 OS << "}\n\n"; 1591} 1592 1593 1594 1595/// EmitMatchTokenString - Emit the function to match a token string to the 1596/// appropriate match class value. 1597static void EmitMatchTokenString(CodeGenTarget &Target, 1598 std::vector<ClassInfo*> &Infos, 1599 raw_ostream &OS) { 1600 // Construct the match list. 1601 std::vector<StringMatcher::StringPair> Matches; 1602 for (std::vector<ClassInfo*>::iterator it = Infos.begin(), 1603 ie = Infos.end(); it != ie; ++it) { 1604 ClassInfo &CI = **it; 1605 1606 if (CI.Kind == ClassInfo::Token) 1607 Matches.push_back(StringMatcher::StringPair(CI.ValueName, 1608 "return " + CI.Name + ";")); 1609 } 1610 1611 OS << "static MatchClassKind MatchTokenString(StringRef Name) {\n"; 1612 1613 StringMatcher("Name", Matches, OS).Emit(); 1614 1615 OS << " return InvalidMatchClass;\n"; 1616 OS << "}\n\n"; 1617} 1618 1619/// EmitMatchRegisterName - Emit the function to match a string to the target 1620/// specific register enum. 1621static void EmitMatchRegisterName(CodeGenTarget &Target, Record *AsmParser, 1622 raw_ostream &OS) { 1623 // Construct the match list. 1624 std::vector<StringMatcher::StringPair> Matches; 1625 for (unsigned i = 0, e = Target.getRegisters().size(); i != e; ++i) { 1626 const CodeGenRegister &Reg = Target.getRegisters()[i]; 1627 if (Reg.TheDef->getValueAsString("AsmName").empty()) 1628 continue; 1629 1630 Matches.push_back(StringMatcher::StringPair( 1631 Reg.TheDef->getValueAsString("AsmName"), 1632 "return " + utostr(i + 1) + ";")); 1633 } 1634 1635 OS << "static unsigned MatchRegisterName(StringRef Name) {\n"; 1636 1637 StringMatcher("Name", Matches, OS).Emit(); 1638 1639 OS << " return 0;\n"; 1640 OS << "}\n\n"; 1641} 1642 1643/// EmitSubtargetFeatureFlagEnumeration - Emit the subtarget feature flag 1644/// definitions. 1645static void EmitSubtargetFeatureFlagEnumeration(AsmMatcherInfo &Info, 1646 raw_ostream &OS) { 1647 OS << "// Flags for subtarget features that participate in " 1648 << "instruction matching.\n"; 1649 OS << "enum SubtargetFeatureFlag {\n"; 1650 for (std::map<Record*, SubtargetFeatureInfo*>::const_iterator 1651 it = Info.SubtargetFeatures.begin(), 1652 ie = Info.SubtargetFeatures.end(); it != ie; ++it) { 1653 SubtargetFeatureInfo &SFI = *it->second; 1654 OS << " " << SFI.getEnumName() << " = (1 << " << SFI.Index << "),\n"; 1655 } 1656 OS << " Feature_None = 0\n"; 1657 OS << "};\n\n"; 1658} 1659 1660/// EmitComputeAvailableFeatures - Emit the function to compute the list of 1661/// available features given a subtarget. 1662static void EmitComputeAvailableFeatures(AsmMatcherInfo &Info, 1663 raw_ostream &OS) { 1664 std::string ClassName = 1665 Info.AsmParser->getValueAsString("AsmParserClassName"); 1666 1667 OS << "unsigned " << Info.Target.getName() << ClassName << "::\n" 1668 << "ComputeAvailableFeatures(const " << Info.Target.getName() 1669 << "Subtarget *Subtarget) const {\n"; 1670 OS << " unsigned Features = 0;\n"; 1671 for (std::map<Record*, SubtargetFeatureInfo*>::const_iterator 1672 it = Info.SubtargetFeatures.begin(), 1673 ie = Info.SubtargetFeatures.end(); it != ie; ++it) { 1674 SubtargetFeatureInfo &SFI = *it->second; 1675 OS << " if (" << SFI.TheDef->getValueAsString("CondString") 1676 << ")\n"; 1677 OS << " Features |= " << SFI.getEnumName() << ";\n"; 1678 } 1679 OS << " return Features;\n"; 1680 OS << "}\n\n"; 1681} 1682 1683static std::string GetAliasRequiredFeatures(Record *R, 1684 const AsmMatcherInfo &Info) { 1685 std::vector<Record*> ReqFeatures = R->getValueAsListOfDefs("Predicates"); 1686 std::string Result; 1687 unsigned NumFeatures = 0; 1688 for (unsigned i = 0, e = ReqFeatures.size(); i != e; ++i) { 1689 SubtargetFeatureInfo *F = Info.getSubtargetFeature(ReqFeatures[i]); 1690 1691 if (F == 0) 1692 throw TGError(R->getLoc(), "Predicate '" + ReqFeatures[i]->getName() + 1693 "' is not marked as an AssemblerPredicate!"); 1694 1695 if (NumFeatures) 1696 Result += '|'; 1697 1698 Result += F->getEnumName(); 1699 ++NumFeatures; 1700 } 1701 1702 if (NumFeatures > 1) 1703 Result = '(' + Result + ')'; 1704 return Result; 1705} 1706 1707/// EmitMnemonicAliases - If the target has any MnemonicAlias<> definitions, 1708/// emit a function for them and return true, otherwise return false. 1709static bool EmitMnemonicAliases(raw_ostream &OS, const AsmMatcherInfo &Info) { 1710 std::vector<Record*> Aliases = 1711 Info.getRecords().getAllDerivedDefinitions("MnemonicAlias"); 1712 if (Aliases.empty()) return false; 1713 1714 OS << "static void ApplyMnemonicAliases(StringRef &Mnemonic, " 1715 "unsigned Features) {\n"; 1716 1717 // Keep track of all the aliases from a mnemonic. Use an std::map so that the 1718 // iteration order of the map is stable. 1719 std::map<std::string, std::vector<Record*> > AliasesFromMnemonic; 1720 1721 for (unsigned i = 0, e = Aliases.size(); i != e; ++i) { 1722 Record *R = Aliases[i]; 1723 AliasesFromMnemonic[R->getValueAsString("FromMnemonic")].push_back(R); 1724 } 1725 1726 // Process each alias a "from" mnemonic at a time, building the code executed 1727 // by the string remapper. 1728 std::vector<StringMatcher::StringPair> Cases; 1729 for (std::map<std::string, std::vector<Record*> >::iterator 1730 I = AliasesFromMnemonic.begin(), E = AliasesFromMnemonic.end(); 1731 I != E; ++I) { 1732 const std::vector<Record*> &ToVec = I->second; 1733 1734 // Loop through each alias and emit code that handles each case. If there 1735 // are two instructions without predicates, emit an error. If there is one, 1736 // emit it last. 1737 std::string MatchCode; 1738 int AliasWithNoPredicate = -1; 1739 1740 for (unsigned i = 0, e = ToVec.size(); i != e; ++i) { 1741 Record *R = ToVec[i]; 1742 std::string FeatureMask = GetAliasRequiredFeatures(R, Info); 1743 1744 // If this unconditionally matches, remember it for later and diagnose 1745 // duplicates. 1746 if (FeatureMask.empty()) { 1747 if (AliasWithNoPredicate != -1) { 1748 // We can't have two aliases from the same mnemonic with no predicate. 1749 PrintError(ToVec[AliasWithNoPredicate]->getLoc(), 1750 "two MnemonicAliases with the same 'from' mnemonic!"); 1751 throw TGError(R->getLoc(), "this is the other MnemonicAlias."); 1752 } 1753 1754 AliasWithNoPredicate = i; 1755 continue; 1756 } 1757 1758 if (!MatchCode.empty()) 1759 MatchCode += "else "; 1760 MatchCode += "if ((Features & " + FeatureMask + ") == "+FeatureMask+")\n"; 1761 MatchCode += " Mnemonic = \"" +R->getValueAsString("ToMnemonic")+"\";\n"; 1762 } 1763 1764 if (AliasWithNoPredicate != -1) { 1765 Record *R = ToVec[AliasWithNoPredicate]; 1766 if (!MatchCode.empty()) 1767 MatchCode += "else\n "; 1768 MatchCode += "Mnemonic = \"" + R->getValueAsString("ToMnemonic")+"\";\n"; 1769 } 1770 1771 MatchCode += "return;"; 1772 1773 Cases.push_back(std::make_pair(I->first, MatchCode)); 1774 } 1775 1776 1777 StringMatcher("Mnemonic", Cases, OS).Emit(); 1778 OS << "}\n\n"; 1779 1780 return true; 1781} 1782 1783void AsmMatcherEmitter::run(raw_ostream &OS) { 1784 CodeGenTarget Target(Records); 1785 Record *AsmParser = Target.getAsmParser(); 1786 std::string ClassName = AsmParser->getValueAsString("AsmParserClassName"); 1787 1788 // Compute the information on the instructions to match. 1789 AsmMatcherInfo Info(AsmParser, Target, Records); 1790 Info.BuildInfo(); 1791 1792 // Sort the instruction table using the partial order on classes. We use 1793 // stable_sort to ensure that ambiguous instructions are still 1794 // deterministically ordered. 1795 std::stable_sort(Info.Matchables.begin(), Info.Matchables.end(), 1796 less_ptr<MatchableInfo>()); 1797 1798 DEBUG_WITH_TYPE("instruction_info", { 1799 for (std::vector<MatchableInfo*>::iterator 1800 it = Info.Matchables.begin(), ie = Info.Matchables.end(); 1801 it != ie; ++it) 1802 (*it)->dump(); 1803 }); 1804 1805 // Check for ambiguous matchables. 1806 DEBUG_WITH_TYPE("ambiguous_instrs", { 1807 unsigned NumAmbiguous = 0; 1808 for (unsigned i = 0, e = Info.Matchables.size(); i != e; ++i) { 1809 for (unsigned j = i + 1; j != e; ++j) { 1810 MatchableInfo &A = *Info.Matchables[i]; 1811 MatchableInfo &B = *Info.Matchables[j]; 1812 1813 if (A.CouldMatchAmiguouslyWith(B)) { 1814 errs() << "warning: ambiguous matchables:\n"; 1815 A.dump(); 1816 errs() << "\nis incomparable with:\n"; 1817 B.dump(); 1818 errs() << "\n\n"; 1819 ++NumAmbiguous; 1820 } 1821 } 1822 } 1823 if (NumAmbiguous) 1824 errs() << "warning: " << NumAmbiguous 1825 << " ambiguous matchables!\n"; 1826 }); 1827 1828 // Write the output. 1829 1830 EmitSourceFileHeader("Assembly Matcher Source Fragment", OS); 1831 1832 // Information for the class declaration. 1833 OS << "\n#ifdef GET_ASSEMBLER_HEADER\n"; 1834 OS << "#undef GET_ASSEMBLER_HEADER\n"; 1835 OS << " // This should be included into the middle of the declaration of \n"; 1836 OS << " // your subclasses implementation of TargetAsmParser.\n"; 1837 OS << " unsigned ComputeAvailableFeatures(const " << 1838 Target.getName() << "Subtarget *Subtarget) const;\n"; 1839 OS << " enum MatchResultTy {\n"; 1840 OS << " Match_Success, Match_MnemonicFail, Match_InvalidOperand,\n"; 1841 OS << " Match_MissingFeature\n"; 1842 OS << " };\n"; 1843 OS << " MatchResultTy MatchInstructionImpl(\n"; 1844 OS << " const SmallVectorImpl<MCParsedAsmOperand*> &Operands,\n"; 1845 OS << " MCInst &Inst, unsigned &ErrorInfo);\n\n"; 1846 OS << "#endif // GET_ASSEMBLER_HEADER_INFO\n\n"; 1847 1848 OS << "\n#ifdef GET_REGISTER_MATCHER\n"; 1849 OS << "#undef GET_REGISTER_MATCHER\n\n"; 1850 1851 // Emit the subtarget feature enumeration. 1852 EmitSubtargetFeatureFlagEnumeration(Info, OS); 1853 1854 // Emit the function to match a register name to number. 1855 EmitMatchRegisterName(Target, AsmParser, OS); 1856 1857 OS << "#endif // GET_REGISTER_MATCHER\n\n"; 1858 1859 1860 OS << "\n#ifdef GET_MATCHER_IMPLEMENTATION\n"; 1861 OS << "#undef GET_MATCHER_IMPLEMENTATION\n\n"; 1862 1863 // Generate the function that remaps for mnemonic aliases. 1864 bool HasMnemonicAliases = EmitMnemonicAliases(OS, Info); 1865 1866 // Generate the unified function to convert operands into an MCInst. 1867 EmitConvertToMCInst(Target, Info.Matchables, OS); 1868 1869 // Emit the enumeration for classes which participate in matching. 1870 EmitMatchClassEnumeration(Target, Info.Classes, OS); 1871 1872 // Emit the routine to match token strings to their match class. 1873 EmitMatchTokenString(Target, Info.Classes, OS); 1874 1875 // Emit the routine to classify an operand. 1876 EmitClassifyOperand(Info, OS); 1877 1878 // Emit the subclass predicate routine. 1879 EmitIsSubclass(Target, Info.Classes, OS); 1880 1881 // Emit the available features compute function. 1882 EmitComputeAvailableFeatures(Info, OS); 1883 1884 1885 size_t MaxNumOperands = 0; 1886 for (std::vector<MatchableInfo*>::const_iterator it = 1887 Info.Matchables.begin(), ie = Info.Matchables.end(); 1888 it != ie; ++it) 1889 MaxNumOperands = std::max(MaxNumOperands, (*it)->AsmOperands.size()); 1890 1891 1892 // Emit the static match table; unused classes get initalized to 0 which is 1893 // guaranteed to be InvalidMatchClass. 1894 // 1895 // FIXME: We can reduce the size of this table very easily. First, we change 1896 // it so that store the kinds in separate bit-fields for each index, which 1897 // only needs to be the max width used for classes at that index (we also need 1898 // to reject based on this during classification). If we then make sure to 1899 // order the match kinds appropriately (putting mnemonics last), then we 1900 // should only end up using a few bits for each class, especially the ones 1901 // following the mnemonic. 1902 OS << "namespace {\n"; 1903 OS << " struct MatchEntry {\n"; 1904 OS << " unsigned Opcode;\n"; 1905 OS << " const char *Mnemonic;\n"; 1906 OS << " ConversionKind ConvertFn;\n"; 1907 OS << " MatchClassKind Classes[" << MaxNumOperands << "];\n"; 1908 OS << " unsigned RequiredFeatures;\n"; 1909 OS << " };\n\n"; 1910 1911 OS << "// Predicate for searching for an opcode.\n"; 1912 OS << " struct LessOpcode {\n"; 1913 OS << " bool operator()(const MatchEntry &LHS, StringRef RHS) {\n"; 1914 OS << " return StringRef(LHS.Mnemonic) < RHS;\n"; 1915 OS << " }\n"; 1916 OS << " bool operator()(StringRef LHS, const MatchEntry &RHS) {\n"; 1917 OS << " return LHS < StringRef(RHS.Mnemonic);\n"; 1918 OS << " }\n"; 1919 OS << " bool operator()(const MatchEntry &LHS, const MatchEntry &RHS) {\n"; 1920 OS << " return StringRef(LHS.Mnemonic) < StringRef(RHS.Mnemonic);\n"; 1921 OS << " }\n"; 1922 OS << " };\n"; 1923 1924 OS << "} // end anonymous namespace.\n\n"; 1925 1926 OS << "static const MatchEntry MatchTable[" 1927 << Info.Matchables.size() << "] = {\n"; 1928 1929 for (std::vector<MatchableInfo*>::const_iterator it = 1930 Info.Matchables.begin(), ie = Info.Matchables.end(); 1931 it != ie; ++it) { 1932 MatchableInfo &II = **it; 1933 1934 1935 OS << " { " << Target.getName() << "::" 1936 << II.getResultInst()->TheDef->getName() << ", \"" << II.Mnemonic << "\"" 1937 << ", " << II.ConversionFnKind << ", { "; 1938 for (unsigned i = 0, e = II.AsmOperands.size(); i != e; ++i) { 1939 MatchableInfo::AsmOperand &Op = II.AsmOperands[i]; 1940 1941 if (i) OS << ", "; 1942 OS << Op.Class->Name; 1943 } 1944 OS << " }, "; 1945 1946 // Write the required features mask. 1947 if (!II.RequiredFeatures.empty()) { 1948 for (unsigned i = 0, e = II.RequiredFeatures.size(); i != e; ++i) { 1949 if (i) OS << "|"; 1950 OS << II.RequiredFeatures[i]->getEnumName(); 1951 } 1952 } else 1953 OS << "0"; 1954 1955 OS << "},\n"; 1956 } 1957 1958 OS << "};\n\n"; 1959 1960 // Finally, build the match function. 1961 OS << Target.getName() << ClassName << "::MatchResultTy " 1962 << Target.getName() << ClassName << "::\n" 1963 << "MatchInstructionImpl(const SmallVectorImpl<MCParsedAsmOperand*>" 1964 << " &Operands,\n"; 1965 OS << " MCInst &Inst, unsigned &ErrorInfo) {\n"; 1966 1967 // Emit code to get the available features. 1968 OS << " // Get the current feature set.\n"; 1969 OS << " unsigned AvailableFeatures = getAvailableFeatures();\n\n"; 1970 1971 OS << " // Get the instruction mnemonic, which is the first token.\n"; 1972 OS << " StringRef Mnemonic = ((" << Target.getName() 1973 << "Operand*)Operands[0])->getToken();\n\n"; 1974 1975 if (HasMnemonicAliases) { 1976 OS << " // Process all MnemonicAliases to remap the mnemonic.\n"; 1977 OS << " ApplyMnemonicAliases(Mnemonic, AvailableFeatures);\n\n"; 1978 } 1979 1980 // Emit code to compute the class list for this operand vector. 1981 OS << " // Eliminate obvious mismatches.\n"; 1982 OS << " if (Operands.size() > " << (MaxNumOperands+1) << ") {\n"; 1983 OS << " ErrorInfo = " << (MaxNumOperands+1) << ";\n"; 1984 OS << " return Match_InvalidOperand;\n"; 1985 OS << " }\n\n"; 1986 1987 OS << " // Compute the class list for this operand vector.\n"; 1988 OS << " MatchClassKind Classes[" << MaxNumOperands << "];\n"; 1989 OS << " for (unsigned i = 1, e = Operands.size(); i != e; ++i) {\n"; 1990 OS << " Classes[i-1] = ClassifyOperand(Operands[i]);\n\n"; 1991 1992 OS << " // Check for invalid operands before matching.\n"; 1993 OS << " if (Classes[i-1] == InvalidMatchClass) {\n"; 1994 OS << " ErrorInfo = i;\n"; 1995 OS << " return Match_InvalidOperand;\n"; 1996 OS << " }\n"; 1997 OS << " }\n\n"; 1998 1999 OS << " // Mark unused classes.\n"; 2000 OS << " for (unsigned i = Operands.size()-1, e = " << MaxNumOperands << "; " 2001 << "i != e; ++i)\n"; 2002 OS << " Classes[i] = InvalidMatchClass;\n\n"; 2003 2004 OS << " // Some state to try to produce better error messages.\n"; 2005 OS << " bool HadMatchOtherThanFeatures = false;\n\n"; 2006 OS << " // Set ErrorInfo to the operand that mismatches if it is \n"; 2007 OS << " // wrong for all instances of the instruction.\n"; 2008 OS << " ErrorInfo = ~0U;\n"; 2009 2010 // Emit code to search the table. 2011 OS << " // Search the table.\n"; 2012 OS << " std::pair<const MatchEntry*, const MatchEntry*> MnemonicRange =\n"; 2013 OS << " std::equal_range(MatchTable, MatchTable+" 2014 << Info.Matchables.size() << ", Mnemonic, LessOpcode());\n\n"; 2015 2016 OS << " // Return a more specific error code if no mnemonics match.\n"; 2017 OS << " if (MnemonicRange.first == MnemonicRange.second)\n"; 2018 OS << " return Match_MnemonicFail;\n\n"; 2019 2020 OS << " for (const MatchEntry *it = MnemonicRange.first, " 2021 << "*ie = MnemonicRange.second;\n"; 2022 OS << " it != ie; ++it) {\n"; 2023 2024 OS << " // equal_range guarantees that instruction mnemonic matches.\n"; 2025 OS << " assert(Mnemonic == it->Mnemonic);\n"; 2026 2027 // Emit check that the subclasses match. 2028 OS << " bool OperandsValid = true;\n"; 2029 OS << " for (unsigned i = 0; i != " << MaxNumOperands << "; ++i) {\n"; 2030 OS << " if (IsSubclass(Classes[i], it->Classes[i]))\n"; 2031 OS << " continue;\n"; 2032 OS << " // If this operand is broken for all of the instances of this\n"; 2033 OS << " // mnemonic, keep track of it so we can report loc info.\n"; 2034 OS << " if (it == MnemonicRange.first || ErrorInfo == i+1)\n"; 2035 OS << " ErrorInfo = i+1;\n"; 2036 OS << " else\n"; 2037 OS << " ErrorInfo = ~0U;"; 2038 OS << " // Otherwise, just reject this instance of the mnemonic.\n"; 2039 OS << " OperandsValid = false;\n"; 2040 OS << " break;\n"; 2041 OS << " }\n\n"; 2042 2043 OS << " if (!OperandsValid) continue;\n"; 2044 2045 // Emit check that the required features are available. 2046 OS << " if ((AvailableFeatures & it->RequiredFeatures) " 2047 << "!= it->RequiredFeatures) {\n"; 2048 OS << " HadMatchOtherThanFeatures = true;\n"; 2049 OS << " continue;\n"; 2050 OS << " }\n"; 2051 2052 OS << "\n"; 2053 OS << " ConvertToMCInst(it->ConvertFn, Inst, it->Opcode, Operands);\n"; 2054 2055 // Call the post-processing function, if used. 2056 std::string InsnCleanupFn = 2057 AsmParser->getValueAsString("AsmParserInstCleanup"); 2058 if (!InsnCleanupFn.empty()) 2059 OS << " " << InsnCleanupFn << "(Inst);\n"; 2060 2061 OS << " return Match_Success;\n"; 2062 OS << " }\n\n"; 2063 2064 OS << " // Okay, we had no match. Try to return a useful error code.\n"; 2065 OS << " if (HadMatchOtherThanFeatures) return Match_MissingFeature;\n"; 2066 OS << " return Match_InvalidOperand;\n"; 2067 OS << "}\n\n"; 2068 2069 OS << "#endif // GET_MATCHER_IMPLEMENTATION\n\n"; 2070} 2071