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