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