utils/TableGen/AsmMatcherEmitter.cpp

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