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