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