llvm-project

1
//===- AsmMatcherEmitter.cpp - Generate an assembly matcher ---------------===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
//
9
// This tablegen backend emits a target specifier matcher for converting parsed
10
// assembly operands in the MCInst structures. It also emits a matcher for
11
// custom operand parsing.
12
//
13
// Converting assembly operands into MCInst structures
14
// ---------------------------------------------------
15
//
16
// The input to the target specific matcher is a list of literal tokens and
17
// operands. The target specific parser should generally eliminate any syntax
18
// which is not relevant for matching; for example, comma tokens should have
19
// already been consumed and eliminated by the parser. Most instructions will
20
// end up with a single literal token (the instruction name) and some number of
21
// operands.
22
//
23
// Some example inputs, for X86:
24
//   'addl' (immediate ...) (register ...)
25
//   'add' (immediate ...) (memory ...)
26
//   'call' '*' %epc
27
//
28
// The assembly matcher is responsible for converting this input into a precise
29
// machine instruction (i.e., an instruction with a well defined encoding). This
30
// mapping has several properties which complicate matching:
31
//
32
//  - It may be ambiguous; many architectures can legally encode particular
33
//    variants of an instruction in different ways (for example, using a smaller
34
//    encoding for small immediates). Such ambiguities should never be
35
//    arbitrarily resolved by the assembler, the assembler is always responsible
36
//    for choosing the "best" available instruction.
37
//
38
//  - It may depend on the subtarget or the assembler context. Instructions
39
//    which are invalid for the current mode, but otherwise unambiguous (e.g.,
40
//    an SSE instruction in a file being assembled for i486) should be accepted
41
//    and rejected by the assembler front end. However, if the proper encoding
42
//    for an instruction is dependent on the assembler context then the matcher
43
//    is responsible for selecting the correct machine instruction for the
44
//    current mode.
45
//
46
// The core matching algorithm attempts to exploit the regularity in most
47
// instruction sets to quickly determine the set of possibly matching
48
// instructions, and the simplify the generated code. Additionally, this helps
49
// to ensure that the ambiguities are intentionally resolved by the user.
50
//
51
// The matching is divided into two distinct phases:
52
//
53
//   1. Classification: Each operand is mapped to the unique set which (a)
54
//      contains it, and (b) is the largest such subset for which a single
55
//      instruction could match all members.
56
//
57
//      For register classes, we can generate these subgroups automatically. For
58
//      arbitrary operands, we expect the user to define the classes and their
59
//      relations to one another (for example, 8-bit signed immediates as a
60
//      subset of 32-bit immediates).
61
//
62
//      By partitioning the operands in this way, we guarantee that for any
63
//      tuple of classes, any single instruction must match either all or none
64
//      of the sets of operands which could classify to that tuple.
65
//
66
//      In addition, the subset relation amongst classes induces a partial order
67
//      on such tuples, which we use to resolve ambiguities.
68
//
69
//   2. The input can now be treated as a tuple of classes (static tokens are
70
//      simple singleton sets). Each such tuple should generally map to a single
71
//      instruction (we currently ignore cases where this isn't true, whee!!!),
72
//      which we can emit a simple matcher for.
73
//
74
// Custom Operand Parsing
75
// ----------------------
76
//
77
//  Some targets need a custom way to parse operands, some specific instructions
78
//  can contain arguments that can represent processor flags and other kinds of
79
//  identifiers that need to be mapped to specific values in the final encoded
80
//  instructions. The target specific custom operand parsing works in the
81
//  following way:
82
//
83
//   1. A operand match table is built, each entry contains a mnemonic, an
84
//      operand class, a mask for all operand positions for that same
85
//      class/mnemonic and target features to be checked while trying to match.
86
//
87
//   2. The operand matcher will try every possible entry with the same
88
//      mnemonic and will check if the target feature for this mnemonic also
89
//      matches. After that, if the operand to be matched has its index
90
//      present in the mask, a successful match occurs. Otherwise, fallback
91
//      to the regular operand parsing.
92
//
93
//   3. For a match success, each operand class that has a 'ParserMethod'
94
//      becomes part of a switch from where the custom method is called.
95
//
96
//===----------------------------------------------------------------------===//
97

98
#include "Common/CodeGenInstAlias.h"
99
#include "Common/CodeGenInstruction.h"
100
#include "Common/CodeGenRegisters.h"
101
#include "Common/CodeGenTarget.h"
102
#include "Common/SubtargetFeatureInfo.h"
103
#include "Common/Types.h"
104
#include "llvm/ADT/CachedHashString.h"
105
#include "llvm/ADT/PointerUnion.h"
106
#include "llvm/ADT/STLExtras.h"
107
#include "llvm/ADT/SmallPtrSet.h"
108
#include "llvm/ADT/SmallVector.h"
109
#include "llvm/ADT/StringExtras.h"
110
#include "llvm/Support/CommandLine.h"
111
#include "llvm/Support/Debug.h"
112
#include "llvm/Support/ErrorHandling.h"
113
#include "llvm/TableGen/Error.h"
114
#include "llvm/TableGen/Record.h"
115
#include "llvm/TableGen/StringMatcher.h"
116
#include "llvm/TableGen/StringToOffsetTable.h"
117
#include "llvm/TableGen/TableGenBackend.h"
118
#include <cassert>
119
#include <cctype>
120
#include <forward_list>
121
#include <map>
122
#include <set>
123

124
using namespace llvm;
125

126
#define DEBUG_TYPE "asm-matcher-emitter"
127

128
cl::OptionCategory AsmMatcherEmitterCat("Options for -gen-asm-matcher");
129

130
static cl::opt<std::string>
131
    MatchPrefix("match-prefix", cl::init(""),
132
                cl::desc("Only match instructions with the given prefix"),
133
                cl::cat(AsmMatcherEmitterCat));
134

135
namespace {
136
class AsmMatcherInfo;
137

138
// Register sets are used as keys in some second-order sets TableGen creates
139
// when generating its data structures. This means that the order of two
140
// RegisterSets can be seen in the outputted AsmMatcher tables occasionally, and
141
// can even affect compiler output (at least seen in diagnostics produced when
142
// all matches fail). So we use a type that sorts them consistently.
143
typedef std::set<Record *, LessRecordByID> RegisterSet;
144

145
class AsmMatcherEmitter {
146
  RecordKeeper &Records;
147

148
public:
149
  AsmMatcherEmitter(RecordKeeper &R) : Records(R) {}
150

151
  void run(raw_ostream &o);
152
};
153

154
/// ClassInfo - Helper class for storing the information about a particular
155
/// class of operands which can be matched.
156
struct ClassInfo {
157
  enum ClassInfoKind {
158
    /// Invalid kind, for use as a sentinel value.
159
    Invalid = 0,
160

161
    /// The class for a particular token.
162
    Token,
163

164
    /// The (first) register class, subsequent register classes are
165
    /// RegisterClass0+1, and so on.
166
    RegisterClass0,
167

168
    /// The (first) user defined class, subsequent user defined classes are
169
    /// UserClass0+1, and so on.
170
    UserClass0 = 1 << 16
171
  };
172

173
  /// Kind - The class kind, which is either a predefined kind, or (UserClass0 +
174
  /// N) for the Nth user defined class.
175
  unsigned Kind;
176

177
  /// SuperClasses - The super classes of this class. Note that for simplicities
178
  /// sake user operands only record their immediate super class, while register
179
  /// operands include all superclasses.
180
  std::vector<ClassInfo *> SuperClasses;
181

182
  /// Name - The full class name, suitable for use in an enum.
183
  std::string Name;
184

185
  /// ClassName - The unadorned generic name for this class (e.g., Token).
186
  std::string ClassName;
187

188
  /// ValueName - The name of the value this class represents; for a token this
189
  /// is the literal token string, for an operand it is the TableGen class (or
190
  /// empty if this is a derived class).
191
  std::string ValueName;
192

193
  /// PredicateMethod - The name of the operand method to test whether the
194
  /// operand matches this class; this is not valid for Token or register kinds.
195
  std::string PredicateMethod;
196

197
  /// RenderMethod - The name of the operand method to add this operand to an
198
  /// MCInst; this is not valid for Token or register kinds.
199
  std::string RenderMethod;
200

201
  /// ParserMethod - The name of the operand method to do a target specific
202
  /// parsing on the operand.
203
  std::string ParserMethod;
204

205
  /// For register classes: the records for all the registers in this class.
206
  RegisterSet Registers;
207

208
  /// For custom match classes: the diagnostic kind for when the predicate
209
  /// fails.
210
  std::string DiagnosticType;
211

212
  /// For custom match classes: the diagnostic string for when the predicate
213
  /// fails.
214
  std::string DiagnosticString;
215

216
  /// Is this operand optional and not always required.
217
  bool IsOptional;
218

219
  /// DefaultMethod - The name of the method that returns the default operand
220
  /// for optional operand
221
  std::string DefaultMethod;
222

223
public:
224
  /// isRegisterClass() - Check if this is a register class.
225
  bool isRegisterClass() const {
226
    return Kind >= RegisterClass0 && Kind < UserClass0;
227
  }
228

229
  /// isUserClass() - Check if this is a user defined class.
230
  bool isUserClass() const { return Kind >= UserClass0; }
231

232
  /// isRelatedTo - Check whether this class is "related" to \p RHS. Classes
233
  /// are related if they are in the same class hierarchy.
234
  bool isRelatedTo(const ClassInfo &RHS) const {
235
    // Tokens are only related to tokens.
236
    if (Kind == Token || RHS.Kind == Token)
237
      return Kind == Token && RHS.Kind == Token;
238

239
    // Registers classes are only related to registers classes, and only if
240
    // their intersection is non-empty.
241
    if (isRegisterClass() || RHS.isRegisterClass()) {
242
      if (!isRegisterClass() || !RHS.isRegisterClass())
243
        return false;
244

245
      std::vector<Record *> Tmp;
246
      std::set_intersection(Registers.begin(), Registers.end(),
247
                            RHS.Registers.begin(), RHS.Registers.end(),
248
                            std::back_inserter(Tmp), LessRecordByID());
249

250
      return !Tmp.empty();
251
    }
252

253
    // Otherwise we have two users operands; they are related if they are in the
254
    // same class hierarchy.
255
    //
256
    // FIXME: This is an oversimplification, they should only be related if they
257
    // intersect, however we don't have that information.
258
    assert(isUserClass() && RHS.isUserClass() && "Unexpected class!");
259
    const ClassInfo *Root = this;
260
    while (!Root->SuperClasses.empty())
261
      Root = Root->SuperClasses.front();
262

263
    const ClassInfo *RHSRoot = &RHS;
264
    while (!RHSRoot->SuperClasses.empty())
265
      RHSRoot = RHSRoot->SuperClasses.front();
266

267
    return Root == RHSRoot;
268
  }
269

270
  /// isSubsetOf - Test whether this class is a subset of \p RHS.
271
  bool isSubsetOf(const ClassInfo &RHS) const {
272
    // This is a subset of RHS if it is the same class...
273
    if (this == &RHS)
274
      return true;
275

276
    // ... or if any of its super classes are a subset of RHS.
277
    SmallVector<const ClassInfo *, 16> Worklist(SuperClasses.begin(),
278
                                                SuperClasses.end());
279
    SmallPtrSet<const ClassInfo *, 16> Visited;
280
    while (!Worklist.empty()) {
281
      auto *CI = Worklist.pop_back_val();
282
      if (CI == &RHS)
283
        return true;
284
      for (auto *Super : CI->SuperClasses)
285
        if (Visited.insert(Super).second)
286
          Worklist.push_back(Super);
287
    }
288

289
    return false;
290
  }
291

292
  int getTreeDepth() const {
293
    int Depth = 0;
294
    const ClassInfo *Root = this;
295
    while (!Root->SuperClasses.empty()) {
296
      Depth++;
297
      Root = Root->SuperClasses.front();
298
    }
299
    return Depth;
300
  }
301

302
  const ClassInfo *findRoot() const {
303
    const ClassInfo *Root = this;
304
    while (!Root->SuperClasses.empty())
305
      Root = Root->SuperClasses.front();
306
    return Root;
307
  }
308

309
  /// Compare two classes. This does not produce a total ordering, but does
310
  /// guarantee that subclasses are sorted before their parents, and that the
311
  /// ordering is transitive.
312
  bool operator<(const ClassInfo &RHS) const {
313
    if (this == &RHS)
314
      return false;
315

316
    // First, enforce the ordering between the three different types of class.
317
    // Tokens sort before registers, which sort before user classes.
318
    if (Kind == Token) {
319
      if (RHS.Kind != Token)
320
        return true;
321
      assert(RHS.Kind == Token);
322
    } else if (isRegisterClass()) {
323
      if (RHS.Kind == Token)
324
        return false;
325
      else if (RHS.isUserClass())
326
        return true;
327
      assert(RHS.isRegisterClass());
328
    } else if (isUserClass()) {
329
      if (!RHS.isUserClass())
330
        return false;
331
      assert(RHS.isUserClass());
332
    } else {
333
      llvm_unreachable("Unknown ClassInfoKind");
334
    }
335

336
    if (Kind == Token || isUserClass()) {
337
      // Related tokens and user classes get sorted by depth in the inheritence
338
      // tree (so that subclasses are before their parents).
339
      if (isRelatedTo(RHS)) {
340
        if (getTreeDepth() > RHS.getTreeDepth())
341
          return true;
342
        if (getTreeDepth() < RHS.getTreeDepth())
343
          return false;
344
      } else {
345
        // Unrelated tokens and user classes are ordered by the name of their
346
        // root nodes, so that there is a consistent ordering between
347
        // unconnected trees.
348
        return findRoot()->ValueName < RHS.findRoot()->ValueName;
349
      }
350
    } else if (isRegisterClass()) {
351
      // For register sets, sort by number of registers. This guarantees that
352
      // a set will always sort before all of it's strict supersets.
353
      if (Registers.size() != RHS.Registers.size())
354
        return Registers.size() < RHS.Registers.size();
355
    } else {
356
      llvm_unreachable("Unknown ClassInfoKind");
357
    }
358

359
    // FIXME: We should be able to just return false here, as we only need a
360
    // partial order (we use stable sorts, so this is deterministic) and the
361
    // name of a class shouldn't be significant. However, some of the backends
362
    // accidentally rely on this behaviour, so it will have to stay like this
363
    // until they are fixed.
364
    return ValueName < RHS.ValueName;
365
  }
366
};
367

368
class AsmVariantInfo {
369
public:
370
  StringRef RegisterPrefix;
371
  StringRef TokenizingCharacters;
372
  StringRef SeparatorCharacters;
373
  StringRef BreakCharacters;
374
  StringRef Name;
375
  int AsmVariantNo;
376
};
377

378
bool getPreferSmallerInstructions(CodeGenTarget const &Target) {
379
  return Target.getAsmParser()->getValueAsBit("PreferSmallerInstructions");
380
}
381

382
/// MatchableInfo - Helper class for storing the necessary information for an
383
/// instruction or alias which is capable of being matched.
384
struct MatchableInfo {
385
  struct AsmOperand {
386
    /// Token - This is the token that the operand came from.
387
    StringRef Token;
388

389
    /// The unique class instance this operand should match.
390
    ClassInfo *Class;
391

392
    /// The operand name this is, if anything.
393
    StringRef SrcOpName;
394

395
    /// The operand name this is, before renaming for tied operands.
396
    StringRef OrigSrcOpName;
397

398
    /// The suboperand index within SrcOpName, or -1 for the entire operand.
399
    int SubOpIdx;
400

401
    /// Whether the token is "isolated", i.e., it is preceded and followed
402
    /// by separators.
403
    bool IsIsolatedToken;
404

405
    /// Register record if this token is singleton register.
406
    Record *SingletonReg;
407

408
    explicit AsmOperand(bool IsIsolatedToken, StringRef T)
409
        : Token(T), Class(nullptr), SubOpIdx(-1),
410
          IsIsolatedToken(IsIsolatedToken), SingletonReg(nullptr) {}
411
  };
412

413
  /// ResOperand - This represents a single operand in the result instruction
414
  /// generated by the match.  In cases (like addressing modes) where a single
415
  /// assembler operand expands to multiple MCOperands, this represents the
416
  /// single assembler operand, not the MCOperand.
417
  struct ResOperand {
418
    enum {
419
      /// RenderAsmOperand - This represents an operand result that is
420
      /// generated by calling the render method on the assembly operand.  The
421
      /// corresponding AsmOperand is specified by AsmOperandNum.
422
      RenderAsmOperand,
423

424
      /// TiedOperand - This represents a result operand that is a duplicate of
425
      /// a previous result operand.
426
      TiedOperand,
427

428
      /// ImmOperand - This represents an immediate value that is dumped into
429
      /// the operand.
430
      ImmOperand,
431

432
      /// RegOperand - This represents a fixed register that is dumped in.
433
      RegOperand
434
    } Kind;
435

436
    /// Tuple containing the index of the (earlier) result operand that should
437
    /// be copied from, as well as the indices of the corresponding (parsed)
438
    /// operands in the asm string.
439
    struct TiedOperandsTuple {
440
      unsigned ResOpnd;
441
      unsigned SrcOpnd1Idx;
442
      unsigned SrcOpnd2Idx;
443
    };
444

445
    union {
446
      /// This is the operand # in the AsmOperands list that this should be
447
      /// copied from.
448
      unsigned AsmOperandNum;
449

450
      /// Description of tied operands.
451
      TiedOperandsTuple TiedOperands;
452

453
      /// ImmVal - This is the immediate value added to the instruction.
454
      int64_t ImmVal;
455

456
      /// Register - This is the register record.
457
      Record *Register;
458
    };
459

460
    /// MINumOperands - The number of MCInst operands populated by this
461
    /// operand.
462
    unsigned MINumOperands;
463

464
    static ResOperand getRenderedOp(unsigned AsmOpNum, unsigned NumOperands) {
465
      ResOperand X;
466
      X.Kind = RenderAsmOperand;
467
      X.AsmOperandNum = AsmOpNum;
468
      X.MINumOperands = NumOperands;
469
      return X;
470
    }
471

472
    static ResOperand getTiedOp(unsigned TiedOperandNum, unsigned SrcOperand1,
473
                                unsigned SrcOperand2) {
474
      ResOperand X;
475
      X.Kind = TiedOperand;
476
      X.TiedOperands = {TiedOperandNum, SrcOperand1, SrcOperand2};
477
      X.MINumOperands = 1;
478
      return X;
479
    }
480

481
    static ResOperand getImmOp(int64_t Val) {
482
      ResOperand X;
483
      X.Kind = ImmOperand;
484
      X.ImmVal = Val;
485
      X.MINumOperands = 1;
486
      return X;
487
    }
488

489
    static ResOperand getRegOp(Record *Reg) {
490
      ResOperand X;
491
      X.Kind = RegOperand;
492
      X.Register = Reg;
493
      X.MINumOperands = 1;
494
      return X;
495
    }
496
  };
497

498
  /// AsmVariantID - Target's assembly syntax variant no.
499
  int AsmVariantID;
500

501
  /// AsmString - The assembly string for this instruction (with variants
502
  /// removed), e.g. "movsx $src, $dst".
503
  std::string AsmString;
504

505
  /// TheDef - This is the definition of the instruction or InstAlias that this
506
  /// matchable came from.
507
  Record *const TheDef;
508

509
  // ResInstSize - The size of the resulting instruction for this matchable.
510
  unsigned ResInstSize;
511

512
  /// DefRec - This is the definition that it came from.
513
  PointerUnion<const CodeGenInstruction *, const CodeGenInstAlias *> DefRec;
514

515
  const CodeGenInstruction *getResultInst() const {
516
    if (isa<const CodeGenInstruction *>(DefRec))
517
      return cast<const CodeGenInstruction *>(DefRec);
518
    return cast<const CodeGenInstAlias *>(DefRec)->ResultInst;
519
  }
520

521
  /// ResOperands - This is the operand list that should be built for the result
522
  /// MCInst.
523
  SmallVector<ResOperand, 8> ResOperands;
524

525
  /// Mnemonic - This is the first token of the matched instruction, its
526
  /// mnemonic.
527
  StringRef Mnemonic;
528

529
  /// AsmOperands - The textual operands that this instruction matches,
530
  /// annotated with a class and where in the OperandList they were defined.
531
  /// This directly corresponds to the tokenized AsmString after the mnemonic is
532
  /// removed.
533
  SmallVector<AsmOperand, 8> AsmOperands;
534

535
  /// Predicates - The required subtarget features to match this instruction.
536
  SmallVector<const SubtargetFeatureInfo *, 4> RequiredFeatures;
537

538
  /// ConversionFnKind - The enum value which is passed to the generated
539
  /// convertToMCInst to convert parsed operands into an MCInst for this
540
  /// function.
541
  std::string ConversionFnKind;
542

543
  /// If this instruction is deprecated in some form.
544
  bool HasDeprecation = false;
545

546
  /// If this is an alias, this is use to determine whether or not to using
547
  /// the conversion function defined by the instruction's AsmMatchConverter
548
  /// or to use the function generated by the alias.
549
  bool UseInstAsmMatchConverter;
550

551
  MatchableInfo(const CodeGenInstruction &CGI)
552
      : AsmVariantID(0), AsmString(CGI.AsmString), TheDef(CGI.TheDef),
553
        ResInstSize(TheDef->getValueAsInt("Size")), DefRec(&CGI),
554
        UseInstAsmMatchConverter(true) {}
555

556
  MatchableInfo(std::unique_ptr<const CodeGenInstAlias> Alias)
557
      : AsmVariantID(0), AsmString(Alias->AsmString), TheDef(Alias->TheDef),
558
        ResInstSize(Alias->ResultInst->TheDef->getValueAsInt("Size")),
559
        DefRec(Alias.release()), UseInstAsmMatchConverter(TheDef->getValueAsBit(
560
                                     "UseInstAsmMatchConverter")) {}
561

562
  // Could remove this and the dtor if PointerUnion supported unique_ptr
563
  // elements with a dynamic failure/assertion (like the one below) in the case
564
  // where it was copied while being in an owning state.
565
  MatchableInfo(const MatchableInfo &RHS)
566
      : AsmVariantID(RHS.AsmVariantID), AsmString(RHS.AsmString),
567
        TheDef(RHS.TheDef), ResInstSize(RHS.ResInstSize), DefRec(RHS.DefRec),
568
        ResOperands(RHS.ResOperands), Mnemonic(RHS.Mnemonic),
569
        AsmOperands(RHS.AsmOperands), RequiredFeatures(RHS.RequiredFeatures),
570
        ConversionFnKind(RHS.ConversionFnKind),
571
        HasDeprecation(RHS.HasDeprecation),
572
        UseInstAsmMatchConverter(RHS.UseInstAsmMatchConverter) {
573
    assert(!isa<const CodeGenInstAlias *>(DefRec));
574
  }
575

576
  ~MatchableInfo() {
577
    delete dyn_cast_if_present<const CodeGenInstAlias *>(DefRec);
578
  }
579

580
  // Two-operand aliases clone from the main matchable, but mark the second
581
  // operand as a tied operand of the first for purposes of the assembler.
582
  void formTwoOperandAlias(StringRef Constraint);
583

584
  void initialize(const AsmMatcherInfo &Info,
585
                  SmallPtrSetImpl<Record *> &SingletonRegisters,
586
                  AsmVariantInfo const &Variant, bool HasMnemonicFirst);
587

588
  /// validate - Return true if this matchable is a valid thing to match against
589
  /// and perform a bunch of validity checking.
590
  bool validate(StringRef CommentDelimiter, bool IsAlias) const;
591

592
  /// findAsmOperand - Find the AsmOperand with the specified name and
593
  /// suboperand index.
594
  int findAsmOperand(StringRef N, int SubOpIdx) const {
595
    auto I = find_if(AsmOperands, [&](const AsmOperand &Op) {
596
      return Op.SrcOpName == N && Op.SubOpIdx == SubOpIdx;
597
    });
598
    return (I != AsmOperands.end()) ? I - AsmOperands.begin() : -1;
599
  }
600

601
  /// findAsmOperandNamed - Find the first AsmOperand with the specified name.
602
  /// This does not check the suboperand index.
603
  int findAsmOperandNamed(StringRef N, int LastIdx = -1) const {
604
    auto I =
605
        llvm::find_if(llvm::drop_begin(AsmOperands, LastIdx + 1),
606
                      [&](const AsmOperand &Op) { return Op.SrcOpName == N; });
607
    return (I != AsmOperands.end()) ? I - AsmOperands.begin() : -1;
608
  }
609

610
  int findAsmOperandOriginallyNamed(StringRef N) const {
611
    auto I = find_if(AsmOperands, [&](const AsmOperand &Op) {
612
      return Op.OrigSrcOpName == N;
613
    });
614
    return (I != AsmOperands.end()) ? I - AsmOperands.begin() : -1;
615
  }
616

617
  void buildInstructionResultOperands();
618
  void buildAliasResultOperands(bool AliasConstraintsAreChecked);
619

620
  /// shouldBeMatchedBefore - Compare two matchables for ordering.
621
  bool shouldBeMatchedBefore(const MatchableInfo &RHS,
622
                             bool PreferSmallerInstructions) const {
623
    // The primary comparator is the instruction mnemonic.
624
    if (int Cmp = Mnemonic.compare_insensitive(RHS.Mnemonic))
625
      return Cmp == -1;
626

627
    // (Optionally) Order by the resultant instuctions size.
628
    // eg. for ARM thumb instructions smaller encodings should be preferred.
629
    if (PreferSmallerInstructions && ResInstSize != RHS.ResInstSize)
630
      return ResInstSize < RHS.ResInstSize;
631

632
    if (AsmOperands.size() != RHS.AsmOperands.size())
633
      return AsmOperands.size() < RHS.AsmOperands.size();
634

635
    // Compare lexicographically by operand. The matcher validates that other
636
    // orderings wouldn't be ambiguous using \see couldMatchAmbiguouslyWith().
637
    for (unsigned i = 0, e = AsmOperands.size(); i != e; ++i) {
638
      if (*AsmOperands[i].Class < *RHS.AsmOperands[i].Class)
639
        return true;
640
      if (*RHS.AsmOperands[i].Class < *AsmOperands[i].Class)
641
        return false;
642
    }
643

644
    // For X86 AVX/AVX512 instructions, we prefer vex encoding because the
645
    // vex encoding size is smaller. Since X86InstrSSE.td is included ahead
646
    // of X86InstrAVX512.td, the AVX instruction ID is less than AVX512 ID.
647
    // We use the ID to sort AVX instruction before AVX512 instruction in
648
    // matching table. As well as InstAlias.
649
    if (getResultInst()->TheDef->isSubClassOf("Instruction") &&
650
        getResultInst()->TheDef->getValueAsBit("HasPositionOrder") &&
651
        RHS.getResultInst()->TheDef->isSubClassOf("Instruction") &&
652
        RHS.getResultInst()->TheDef->getValueAsBit("HasPositionOrder"))
653
      return getResultInst()->TheDef->getID() <
654
             RHS.getResultInst()->TheDef->getID();
655

656
    // Give matches that require more features higher precedence. This is useful
657
    // because we cannot define AssemblerPredicates with the negation of
658
    // processor features. For example, ARM v6 "nop" may be either a HINT or
659
    // MOV. With v6, we want to match HINT. The assembler has no way to
660
    // predicate MOV under "NoV6", but HINT will always match first because it
661
    // requires V6 while MOV does not.
662
    if (RequiredFeatures.size() != RHS.RequiredFeatures.size())
663
      return RequiredFeatures.size() > RHS.RequiredFeatures.size();
664

665
    return false;
666
  }
667

668
  /// couldMatchAmbiguouslyWith - Check whether this matchable could
669
  /// ambiguously match the same set of operands as \p RHS (without being a
670
  /// strictly superior match).
671
  bool couldMatchAmbiguouslyWith(const MatchableInfo &RHS,
672
                                 bool PreferSmallerInstructions) const {
673
    // The primary comparator is the instruction mnemonic.
674
    if (Mnemonic != RHS.Mnemonic)
675
      return false;
676

677
    // Different variants can't conflict.
678
    if (AsmVariantID != RHS.AsmVariantID)
679
      return false;
680

681
    // The size of instruction is unambiguous.
682
    if (PreferSmallerInstructions && ResInstSize != RHS.ResInstSize)
683
      return false;
684

685
    // The number of operands is unambiguous.
686
    if (AsmOperands.size() != RHS.AsmOperands.size())
687
      return false;
688

689
    // Otherwise, make sure the ordering of the two instructions is unambiguous
690
    // by checking that either (a) a token or operand kind discriminates them,
691
    // or (b) the ordering among equivalent kinds is consistent.
692

693
    // Tokens and operand kinds are unambiguous (assuming a correct target
694
    // specific parser).
695
    for (unsigned i = 0, e = AsmOperands.size(); i != e; ++i)
696
      if (AsmOperands[i].Class->Kind != RHS.AsmOperands[i].Class->Kind ||
697
          AsmOperands[i].Class->Kind == ClassInfo::Token)
698
        if (*AsmOperands[i].Class < *RHS.AsmOperands[i].Class ||
699
            *RHS.AsmOperands[i].Class < *AsmOperands[i].Class)
700
          return false;
701

702
    // Otherwise, this operand could commute if all operands are equivalent, or
703
    // there is a pair of operands that compare less than and a pair that
704
    // compare greater than.
705
    bool HasLT = false, HasGT = false;
706
    for (unsigned i = 0, e = AsmOperands.size(); i != e; ++i) {
707
      if (*AsmOperands[i].Class < *RHS.AsmOperands[i].Class)
708
        HasLT = true;
709
      if (*RHS.AsmOperands[i].Class < *AsmOperands[i].Class)
710
        HasGT = true;
711
    }
712

713
    return HasLT == HasGT;
714
  }
715

716
  void dump() const;
717

718
private:
719
  void tokenizeAsmString(AsmMatcherInfo const &Info,
720
                         AsmVariantInfo const &Variant);
721
  void addAsmOperand(StringRef Token, bool IsIsolatedToken = false);
722
};
723

724
struct OperandMatchEntry {
725
  unsigned OperandMask;
726
  const MatchableInfo *MI;
727
  ClassInfo *CI;
728

729
  static OperandMatchEntry create(const MatchableInfo *mi, ClassInfo *ci,
730
                                  unsigned opMask) {
731
    OperandMatchEntry X;
732
    X.OperandMask = opMask;
733
    X.CI = ci;
734
    X.MI = mi;
735
    return X;
736
  }
737
};
738

739
class AsmMatcherInfo {
740
public:
741
  /// Tracked Records
742
  RecordKeeper &Records;
743

744
  /// The tablegen AsmParser record.
745
  Record *AsmParser;
746

747
  /// Target - The target information.
748
  CodeGenTarget &Target;
749

750
  /// The classes which are needed for matching.
751
  std::forward_list<ClassInfo> Classes;
752

753
  /// The information on the matchables to match.
754
  std::vector<std::unique_ptr<MatchableInfo>> Matchables;
755

756
  /// Info for custom matching operands by user defined methods.
757
  std::vector<OperandMatchEntry> OperandMatchInfo;
758

759
  /// Map of Register records to their class information.
760
  typedef std::map<Record *, ClassInfo *, LessRecordByID> RegisterClassesTy;
761
  RegisterClassesTy RegisterClasses;
762

763
  /// Map of Predicate records to their subtarget information.
764
  std::map<Record *, SubtargetFeatureInfo, LessRecordByID> SubtargetFeatures;
765

766
  /// Map of AsmOperandClass records to their class information.
767
  std::map<Record *, ClassInfo *> AsmOperandClasses;
768

769
  /// Map of RegisterClass records to their class information.
770
  std::map<Record *, ClassInfo *> RegisterClassClasses;
771

772
private:
773
  /// Map of token to class information which has already been constructed.
774
  std::map<std::string, ClassInfo *> TokenClasses;
775

776
private:
777
  /// getTokenClass - Lookup or create the class for the given token.
778
  ClassInfo *getTokenClass(StringRef Token);
779

780
  /// getOperandClass - Lookup or create the class for the given operand.
781
  ClassInfo *getOperandClass(const CGIOperandList::OperandInfo &OI,
782
                             int SubOpIdx);
783
  ClassInfo *getOperandClass(Record *Rec, int SubOpIdx);
784

785
  /// buildRegisterClasses - Build the ClassInfo* instances for register
786
  /// classes.
787
  void buildRegisterClasses(SmallPtrSetImpl<Record *> &SingletonRegisters);
788

789
  /// buildOperandClasses - Build the ClassInfo* instances for user defined
790
  /// operand classes.
791
  void buildOperandClasses();
792

793
  void buildInstructionOperandReference(MatchableInfo *II, StringRef OpName,
794
                                        unsigned AsmOpIdx);
795
  void buildAliasOperandReference(MatchableInfo *II, StringRef OpName,
796
                                  MatchableInfo::AsmOperand &Op);
797

798
public:
799
  AsmMatcherInfo(Record *AsmParser, CodeGenTarget &Target,
800
                 RecordKeeper &Records);
801

802
  /// Construct the various tables used during matching.
803
  void buildInfo();
804

805
  /// buildOperandMatchInfo - Build the necessary information to handle user
806
  /// defined operand parsing methods.
807
  void buildOperandMatchInfo();
808

809
  /// getSubtargetFeature - Lookup or create the subtarget feature info for the
810
  /// given operand.
811
  const SubtargetFeatureInfo *getSubtargetFeature(Record *Def) const {
812
    assert(Def->isSubClassOf("Predicate") && "Invalid predicate type!");
813
    const auto &I = SubtargetFeatures.find(Def);
814
    return I == SubtargetFeatures.end() ? nullptr : &I->second;
815
  }
816

817
  RecordKeeper &getRecords() const { return Records; }
818

819
  bool hasOptionalOperands() const {
820
    return any_of(Classes,
821
                  [](const ClassInfo &Class) { return Class.IsOptional; });
822
  }
823
};
824

825
} // end anonymous namespace
826

827
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
828
LLVM_DUMP_METHOD void MatchableInfo::dump() const {
829
  errs() << TheDef->getName() << " -- "
830
         << "flattened:\"" << AsmString << "\"\n";
831

832
  errs() << "  variant: " << AsmVariantID << "\n";
833

834
  for (unsigned i = 0, e = AsmOperands.size(); i != e; ++i) {
835
    const AsmOperand &Op = AsmOperands[i];
836
    errs() << "  op[" << i << "] = " << Op.Class->ClassName << " - ";
837
    errs() << '\"' << Op.Token << "\"\n";
838
  }
839
}
840
#endif
841

842
static std::pair<StringRef, StringRef>
843
parseTwoOperandConstraint(StringRef S, ArrayRef<SMLoc> Loc) {
844
  // Split via the '='.
845
  std::pair<StringRef, StringRef> Ops = S.split('=');
846
  if (Ops.second == "")
847
    PrintFatalError(Loc, "missing '=' in two-operand alias constraint");
848
  // Trim whitespace and the leading '$' on the operand names.
849
  size_t start = Ops.first.find_first_of('$');
850
  if (start == std::string::npos)
851
    PrintFatalError(Loc, "expected '$' prefix on asm operand name");
852
  Ops.first = Ops.first.slice(start + 1, std::string::npos);
853
  size_t end = Ops.first.find_last_of(" \t");
854
  Ops.first = Ops.first.slice(0, end);
855
  // Now the second operand.
856
  start = Ops.second.find_first_of('$');
857
  if (start == std::string::npos)
858
    PrintFatalError(Loc, "expected '$' prefix on asm operand name");
859
  Ops.second = Ops.second.slice(start + 1, std::string::npos);
860
  end = Ops.second.find_last_of(" \t");
861
  Ops.first = Ops.first.slice(0, end);
862
  return Ops;
863
}
864

865
void MatchableInfo::formTwoOperandAlias(StringRef Constraint) {
866
  // Figure out which operands are aliased and mark them as tied.
867
  std::pair<StringRef, StringRef> Ops =
868
      parseTwoOperandConstraint(Constraint, TheDef->getLoc());
869

870
  // Find the AsmOperands that refer to the operands we're aliasing.
871
  int SrcAsmOperand = findAsmOperandNamed(Ops.first);
872
  int DstAsmOperand = findAsmOperandNamed(Ops.second);
873
  if (SrcAsmOperand == -1)
874
    PrintFatalError(TheDef->getLoc(),
875
                    "unknown source two-operand alias operand '" + Ops.first +
876
                        "'.");
877
  if (DstAsmOperand == -1)
878
    PrintFatalError(TheDef->getLoc(),
879
                    "unknown destination two-operand alias operand '" +
880
                        Ops.second + "'.");
881

882
  // Find the ResOperand that refers to the operand we're aliasing away
883
  // and update it to refer to the combined operand instead.
884
  for (ResOperand &Op : ResOperands) {
885
    if (Op.Kind == ResOperand::RenderAsmOperand &&
886
        Op.AsmOperandNum == (unsigned)SrcAsmOperand) {
887
      Op.AsmOperandNum = DstAsmOperand;
888
      break;
889
    }
890
  }
891
  // Remove the AsmOperand for the alias operand.
892
  AsmOperands.erase(AsmOperands.begin() + SrcAsmOperand);
893
  // Adjust the ResOperand references to any AsmOperands that followed
894
  // the one we just deleted.
895
  for (ResOperand &Op : ResOperands) {
896
    switch (Op.Kind) {
897
    default:
898
      // Nothing to do for operands that don't reference AsmOperands.
899
      break;
900
    case ResOperand::RenderAsmOperand:
901
      if (Op.AsmOperandNum > (unsigned)SrcAsmOperand)
902
        --Op.AsmOperandNum;
903
      break;
904
    }
905
  }
906
}
907

908
/// extractSingletonRegisterForAsmOperand - Extract singleton register,
909
/// if present, from specified token.
910
static void extractSingletonRegisterForAsmOperand(MatchableInfo::AsmOperand &Op,
911
                                                  const AsmMatcherInfo &Info,
912
                                                  StringRef RegisterPrefix) {
913
  StringRef Tok = Op.Token;
914

915
  // If this token is not an isolated token, i.e., it isn't separated from
916
  // other tokens (e.g. with whitespace), don't interpret it as a register name.
917
  if (!Op.IsIsolatedToken)
918
    return;
919

920
  if (RegisterPrefix.empty()) {
921
    std::string LoweredTok = Tok.lower();
922
    if (const CodeGenRegister *Reg = Info.Target.getRegisterByName(LoweredTok))
923
      Op.SingletonReg = Reg->TheDef;
924
    return;
925
  }
926

927
  if (!Tok.starts_with(RegisterPrefix))
928
    return;
929

930
  StringRef RegName = Tok.substr(RegisterPrefix.size());
931
  if (const CodeGenRegister *Reg = Info.Target.getRegisterByName(RegName))
932
    Op.SingletonReg = Reg->TheDef;
933

934
  // If there is no register prefix (i.e. "%" in "%eax"), then this may
935
  // be some random non-register token, just ignore it.
936
}
937

938
void MatchableInfo::initialize(const AsmMatcherInfo &Info,
939
                               SmallPtrSetImpl<Record *> &SingletonRegisters,
940
                               AsmVariantInfo const &Variant,
941
                               bool HasMnemonicFirst) {
942
  AsmVariantID = Variant.AsmVariantNo;
943
  AsmString = CodeGenInstruction::FlattenAsmStringVariants(
944
      AsmString, Variant.AsmVariantNo);
945

946
  tokenizeAsmString(Info, Variant);
947

948
  // The first token of the instruction is the mnemonic, which must be a
949
  // simple string, not a $foo variable or a singleton register.
950
  if (AsmOperands.empty())
951
    PrintFatalError(TheDef->getLoc(),
952
                    "Instruction '" + TheDef->getName() + "' has no tokens");
953

954
  assert(!AsmOperands[0].Token.empty());
955
  if (HasMnemonicFirst) {
956
    Mnemonic = AsmOperands[0].Token;
957
    if (Mnemonic[0] == '$')
958
      PrintFatalError(TheDef->getLoc(),
959
                      "Invalid instruction mnemonic '" + Mnemonic + "'!");
960

961
    // Remove the first operand, it is tracked in the mnemonic field.
962
    AsmOperands.erase(AsmOperands.begin());
963
  } else if (AsmOperands[0].Token[0] != '$')
964
    Mnemonic = AsmOperands[0].Token;
965

966
  // Compute the require features.
967
  for (Record *Predicate : TheDef->getValueAsListOfDefs("Predicates"))
968
    if (const SubtargetFeatureInfo *Feature =
969
            Info.getSubtargetFeature(Predicate))
970
      RequiredFeatures.push_back(Feature);
971

972
  // Collect singleton registers, if used.
973
  for (MatchableInfo::AsmOperand &Op : AsmOperands) {
974
    extractSingletonRegisterForAsmOperand(Op, Info, Variant.RegisterPrefix);
975
    if (Record *Reg = Op.SingletonReg)
976
      SingletonRegisters.insert(Reg);
977
  }
978

979
  const RecordVal *DepMask = TheDef->getValue("DeprecatedFeatureMask");
980
  if (!DepMask)
981
    DepMask = TheDef->getValue("ComplexDeprecationPredicate");
982

983
  HasDeprecation =
984
      DepMask ? !DepMask->getValue()->getAsUnquotedString().empty() : false;
985
}
986

987
/// Append an AsmOperand for the given substring of AsmString.
988
void MatchableInfo::addAsmOperand(StringRef Token, bool IsIsolatedToken) {
989
  AsmOperands.push_back(AsmOperand(IsIsolatedToken, Token));
990
}
991

992
/// tokenizeAsmString - Tokenize a simplified assembly string.
993
void MatchableInfo::tokenizeAsmString(const AsmMatcherInfo &Info,
994
                                      AsmVariantInfo const &Variant) {
995
  StringRef String = AsmString;
996
  size_t Prev = 0;
997
  bool InTok = false;
998
  bool IsIsolatedToken = true;
999
  for (size_t i = 0, e = String.size(); i != e; ++i) {
1000
    char Char = String[i];
1001
    if (Variant.BreakCharacters.contains(Char)) {
1002
      if (InTok) {
1003
        addAsmOperand(String.slice(Prev, i), false);
1004
        Prev = i;
1005
        IsIsolatedToken = false;
1006
      }
1007
      InTok = true;
1008
      continue;
1009
    }
1010
    if (Variant.TokenizingCharacters.contains(Char)) {
1011
      if (InTok) {
1012
        addAsmOperand(String.slice(Prev, i), IsIsolatedToken);
1013
        InTok = false;
1014
        IsIsolatedToken = false;
1015
      }
1016
      addAsmOperand(String.slice(i, i + 1), IsIsolatedToken);
1017
      Prev = i + 1;
1018
      IsIsolatedToken = true;
1019
      continue;
1020
    }
1021
    if (Variant.SeparatorCharacters.contains(Char)) {
1022
      if (InTok) {
1023
        addAsmOperand(String.slice(Prev, i), IsIsolatedToken);
1024
        InTok = false;
1025
      }
1026
      Prev = i + 1;
1027
      IsIsolatedToken = true;
1028
      continue;
1029
    }
1030

1031
    switch (Char) {
1032
    case '\\':
1033
      if (InTok) {
1034
        addAsmOperand(String.slice(Prev, i), false);
1035
        InTok = false;
1036
        IsIsolatedToken = false;
1037
      }
1038
      ++i;
1039
      assert(i != String.size() && "Invalid quoted character");
1040
      addAsmOperand(String.slice(i, i + 1), IsIsolatedToken);
1041
      Prev = i + 1;
1042
      IsIsolatedToken = false;
1043
      break;
1044

1045
    case '$': {
1046
      if (InTok) {
1047
        addAsmOperand(String.slice(Prev, i), IsIsolatedToken);
1048
        InTok = false;
1049
        IsIsolatedToken = false;
1050
      }
1051

1052
      // If this isn't "${", start new identifier looking like "$xxx"
1053
      if (i + 1 == String.size() || String[i + 1] != '{') {
1054
        Prev = i;
1055
        break;
1056
      }
1057

1058
      size_t EndPos = String.find('}', i);
1059
      assert(EndPos != StringRef::npos &&
1060
             "Missing brace in operand reference!");
1061
      addAsmOperand(String.slice(i, EndPos + 1), IsIsolatedToken);
1062
      Prev = EndPos + 1;
1063
      i = EndPos;
1064
      IsIsolatedToken = false;
1065
      break;
1066
    }
1067

1068
    default:
1069
      InTok = true;
1070
      break;
1071
    }
1072
  }
1073
  if (InTok && Prev != String.size())
1074
    addAsmOperand(String.substr(Prev), IsIsolatedToken);
1075
}
1076

1077
bool MatchableInfo::validate(StringRef CommentDelimiter, bool IsAlias) const {
1078
  // Reject matchables with no .s string.
1079
  if (AsmString.empty())
1080
    PrintFatalError(TheDef->getLoc(), "instruction with empty asm string");
1081

1082
  // Reject any matchables with a newline in them, they should be marked
1083
  // isCodeGenOnly if they are pseudo instructions.
1084
  if (AsmString.find('\n') != std::string::npos)
1085
    PrintFatalError(TheDef->getLoc(),
1086
                    "multiline instruction is not valid for the asmparser, "
1087
                    "mark it isCodeGenOnly");
1088

1089
  // Remove comments from the asm string.  We know that the asmstring only
1090
  // has one line.
1091
  if (!CommentDelimiter.empty() &&
1092
      StringRef(AsmString).contains(CommentDelimiter))
1093
    PrintFatalError(TheDef->getLoc(),
1094
                    "asmstring for instruction has comment character in it, "
1095
                    "mark it isCodeGenOnly");
1096

1097
  // Reject matchables with operand modifiers, these aren't something we can
1098
  // handle, the target should be refactored to use operands instead of
1099
  // modifiers.
1100
  //
1101
  // Also, check for instructions which reference the operand multiple times,
1102
  // if they don't define a custom AsmMatcher: this implies a constraint that
1103
  // the built-in matching code would not honor.
1104
  std::set<std::string> OperandNames;
1105
  for (const AsmOperand &Op : AsmOperands) {
1106
    StringRef Tok = Op.Token;
1107
    if (Tok[0] == '$' && Tok.contains(':'))
1108
      PrintFatalError(
1109
          TheDef->getLoc(),
1110
          "matchable with operand modifier '" + Tok +
1111
              "' not supported by asm matcher.  Mark isCodeGenOnly!");
1112
    // Verify that any operand is only mentioned once.
1113
    // We reject aliases and ignore instructions for now.
1114
    if (!IsAlias && TheDef->getValueAsString("AsmMatchConverter").empty() &&
1115
        Tok[0] == '$' && !OperandNames.insert(std::string(Tok)).second) {
1116
      LLVM_DEBUG({
1117
        errs() << "warning: '" << TheDef->getName() << "': "
1118
               << "ignoring instruction with tied operand '" << Tok << "'\n";
1119
      });
1120
      return false;
1121
    }
1122
  }
1123

1124
  return true;
1125
}
1126

1127
static std::string getEnumNameForToken(StringRef Str) {
1128
  std::string Res;
1129

1130
  for (char C : Str) {
1131
    switch (C) {
1132
    case '*':
1133
      Res += "_STAR_";
1134
      break;
1135
    case '%':
1136
      Res += "_PCT_";
1137
      break;
1138
    case ':':
1139
      Res += "_COLON_";
1140
      break;
1141
    case '!':
1142
      Res += "_EXCLAIM_";
1143
      break;
1144
    case '.':
1145
      Res += "_DOT_";
1146
      break;
1147
    case '<':
1148
      Res += "_LT_";
1149
      break;
1150
    case '>':
1151
      Res += "_GT_";
1152
      break;
1153
    case '-':
1154
      Res += "_MINUS_";
1155
      break;
1156
    case '#':
1157
      Res += "_HASH_";
1158
      break;
1159
    default:
1160
      if (isAlnum(C))
1161
        Res += C;
1162
      else
1163
        Res += "_" + utostr((unsigned)C) + "_";
1164
    }
1165
  }
1166

1167
  return Res;
1168
}
1169

1170
ClassInfo *AsmMatcherInfo::getTokenClass(StringRef Token) {
1171
  ClassInfo *&Entry = TokenClasses[std::string(Token)];
1172

1173
  if (!Entry) {
1174
    Classes.emplace_front();
1175
    Entry = &Classes.front();
1176
    Entry->Kind = ClassInfo::Token;
1177
    Entry->ClassName = "Token";
1178
    Entry->Name = "MCK_" + getEnumNameForToken(Token);
1179
    Entry->ValueName = std::string(Token);
1180
    Entry->PredicateMethod = "<invalid>";
1181
    Entry->RenderMethod = "<invalid>";
1182
    Entry->ParserMethod = "";
1183
    Entry->DiagnosticType = "";
1184
    Entry->IsOptional = false;
1185
    Entry->DefaultMethod = "<invalid>";
1186
  }
1187

1188
  return Entry;
1189
}
1190

1191
ClassInfo *
1192
AsmMatcherInfo::getOperandClass(const CGIOperandList::OperandInfo &OI,
1193
                                int SubOpIdx) {
1194
  Record *Rec = OI.Rec;
1195
  if (SubOpIdx != -1)
1196
    Rec = cast<DefInit>(OI.MIOperandInfo->getArg(SubOpIdx))->getDef();
1197
  return getOperandClass(Rec, SubOpIdx);
1198
}
1199

1200
ClassInfo *AsmMatcherInfo::getOperandClass(Record *Rec, int SubOpIdx) {
1201
  if (Rec->isSubClassOf("RegisterOperand")) {
1202
    // RegisterOperand may have an associated ParserMatchClass. If it does,
1203
    // use it, else just fall back to the underlying register class.
1204
    const RecordVal *R = Rec->getValue("ParserMatchClass");
1205
    if (!R || !R->getValue())
1206
      PrintFatalError(Rec->getLoc(),
1207
                      "Record `" + Rec->getName() +
1208
                          "' does not have a ParserMatchClass!\n");
1209

1210
    if (DefInit *DI = dyn_cast<DefInit>(R->getValue())) {
1211
      Record *MatchClass = DI->getDef();
1212
      if (ClassInfo *CI = AsmOperandClasses[MatchClass])
1213
        return CI;
1214
    }
1215

1216
    // No custom match class. Just use the register class.
1217
    Record *ClassRec = Rec->getValueAsDef("RegClass");
1218
    if (!ClassRec)
1219
      PrintFatalError(Rec->getLoc(),
1220
                      "RegisterOperand `" + Rec->getName() +
1221
                          "' has no associated register class!\n");
1222
    if (ClassInfo *CI = RegisterClassClasses[ClassRec])
1223
      return CI;
1224
    PrintFatalError(Rec->getLoc(), "register class has no class info!");
1225
  }
1226

1227
  if (Rec->isSubClassOf("RegisterClass")) {
1228
    if (ClassInfo *CI = RegisterClassClasses[Rec])
1229
      return CI;
1230
    PrintFatalError(Rec->getLoc(), "register class has no class info!");
1231
  }
1232

1233
  if (!Rec->isSubClassOf("Operand"))
1234
    PrintFatalError(Rec->getLoc(),
1235
                    "Operand `" + Rec->getName() +
1236
                        "' does not derive from class Operand!\n");
1237
  Record *MatchClass = Rec->getValueAsDef("ParserMatchClass");
1238
  if (ClassInfo *CI = AsmOperandClasses[MatchClass])
1239
    return CI;
1240

1241
  PrintFatalError(Rec->getLoc(), "operand has no match class!");
1242
}
1243

1244
struct LessRegisterSet {
1245
  bool operator()(const RegisterSet &LHS, const RegisterSet &RHS) const {
1246
    // std::set<T> defines its own compariso "operator<", but it
1247
    // performs a lexicographical comparison by T's innate comparison
1248
    // for some reason. We don't want non-deterministic pointer
1249
    // comparisons so use this instead.
1250
    return std::lexicographical_compare(LHS.begin(), LHS.end(), RHS.begin(),
1251
                                        RHS.end(), LessRecordByID());
1252
  }
1253
};
1254

1255
void AsmMatcherInfo::buildRegisterClasses(
1256
    SmallPtrSetImpl<Record *> &SingletonRegisters) {
1257
  const auto &Registers = Target.getRegBank().getRegisters();
1258
  auto &RegClassList = Target.getRegBank().getRegClasses();
1259

1260
  typedef std::set<RegisterSet, LessRegisterSet> RegisterSetSet;
1261

1262
  // The register sets used for matching.
1263
  RegisterSetSet RegisterSets;
1264

1265
  // Gather the defined sets.
1266
  for (const CodeGenRegisterClass &RC : RegClassList)
1267
    RegisterSets.insert(
1268
        RegisterSet(RC.getOrder().begin(), RC.getOrder().end()));
1269

1270
  // Add any required singleton sets.
1271
  for (Record *Rec : SingletonRegisters) {
1272
    RegisterSets.insert(RegisterSet(&Rec, &Rec + 1));
1273
  }
1274

1275
  // Introduce derived sets where necessary (when a register does not determine
1276
  // a unique register set class), and build the mapping of registers to the set
1277
  // they should classify to.
1278
  std::map<Record *, RegisterSet> RegisterMap;
1279
  for (const CodeGenRegister &CGR : Registers) {
1280
    // Compute the intersection of all sets containing this register.
1281
    RegisterSet ContainingSet;
1282

1283
    for (const RegisterSet &RS : RegisterSets) {
1284
      if (!RS.count(CGR.TheDef))
1285
        continue;
1286

1287
      if (ContainingSet.empty()) {
1288
        ContainingSet = RS;
1289
        continue;
1290
      }
1291

1292
      RegisterSet Tmp;
1293
      std::set_intersection(ContainingSet.begin(), ContainingSet.end(),
1294
                            RS.begin(), RS.end(),
1295
                            std::inserter(Tmp, Tmp.begin()), LessRecordByID());
1296
      ContainingSet = std::move(Tmp);
1297
    }
1298

1299
    if (!ContainingSet.empty()) {
1300
      RegisterSets.insert(ContainingSet);
1301
      RegisterMap.insert(std::pair(CGR.TheDef, ContainingSet));
1302
    }
1303
  }
1304

1305
  // Construct the register classes.
1306
  std::map<RegisterSet, ClassInfo *, LessRegisterSet> RegisterSetClasses;
1307
  unsigned Index = 0;
1308
  for (const RegisterSet &RS : RegisterSets) {
1309
    Classes.emplace_front();
1310
    ClassInfo *CI = &Classes.front();
1311
    CI->Kind = ClassInfo::RegisterClass0 + Index;
1312
    CI->ClassName = "Reg" + utostr(Index);
1313
    CI->Name = "MCK_Reg" + utostr(Index);
1314
    CI->ValueName = "";
1315
    CI->PredicateMethod = ""; // unused
1316
    CI->RenderMethod = "addRegOperands";
1317
    CI->Registers = RS;
1318
    // FIXME: diagnostic type.
1319
    CI->DiagnosticType = "";
1320
    CI->IsOptional = false;
1321
    CI->DefaultMethod = ""; // unused
1322
    RegisterSetClasses.insert(std::pair(RS, CI));
1323
    ++Index;
1324
  }
1325

1326
  // Find the superclasses; we could compute only the subgroup lattice edges,
1327
  // but there isn't really a point.
1328
  for (const RegisterSet &RS : RegisterSets) {
1329
    ClassInfo *CI = RegisterSetClasses[RS];
1330
    for (const RegisterSet &RS2 : RegisterSets)
1331
      if (RS != RS2 && std::includes(RS2.begin(), RS2.end(), RS.begin(),
1332
                                     RS.end(), LessRecordByID()))
1333
        CI->SuperClasses.push_back(RegisterSetClasses[RS2]);
1334
  }
1335

1336
  // Name the register classes which correspond to a user defined RegisterClass.
1337
  for (const CodeGenRegisterClass &RC : RegClassList) {
1338
    // Def will be NULL for non-user defined register classes.
1339
    Record *Def = RC.getDef();
1340
    if (!Def)
1341
      continue;
1342
    ClassInfo *CI = RegisterSetClasses[RegisterSet(RC.getOrder().begin(),
1343
                                                   RC.getOrder().end())];
1344
    if (CI->ValueName.empty()) {
1345
      CI->ClassName = RC.getName();
1346
      CI->Name = "MCK_" + RC.getName();
1347
      CI->ValueName = RC.getName();
1348
    } else
1349
      CI->ValueName = CI->ValueName + "," + RC.getName();
1350

1351
    Init *DiagnosticType = Def->getValueInit("DiagnosticType");
1352
    if (StringInit *SI = dyn_cast<StringInit>(DiagnosticType))
1353
      CI->DiagnosticType = std::string(SI->getValue());
1354

1355
    Init *DiagnosticString = Def->getValueInit("DiagnosticString");
1356
    if (StringInit *SI = dyn_cast<StringInit>(DiagnosticString))
1357
      CI->DiagnosticString = std::string(SI->getValue());
1358

1359
    // If we have a diagnostic string but the diagnostic type is not specified
1360
    // explicitly, create an anonymous diagnostic type.
1361
    if (!CI->DiagnosticString.empty() && CI->DiagnosticType.empty())
1362
      CI->DiagnosticType = RC.getName();
1363

1364
    RegisterClassClasses.insert(std::pair(Def, CI));
1365
  }
1366

1367
  // Populate the map for individual registers.
1368
  for (auto &It : RegisterMap)
1369
    RegisterClasses[It.first] = RegisterSetClasses[It.second];
1370

1371
  // Name the register classes which correspond to singleton registers.
1372
  for (Record *Rec : SingletonRegisters) {
1373
    ClassInfo *CI = RegisterClasses[Rec];
1374
    assert(CI && "Missing singleton register class info!");
1375

1376
    if (CI->ValueName.empty()) {
1377
      CI->ClassName = std::string(Rec->getName());
1378
      CI->Name = "MCK_" + Rec->getName().str();
1379
      CI->ValueName = std::string(Rec->getName());
1380
    } else
1381
      CI->ValueName = CI->ValueName + "," + Rec->getName().str();
1382
  }
1383
}
1384

1385
void AsmMatcherInfo::buildOperandClasses() {
1386
  std::vector<Record *> AsmOperands =
1387
      Records.getAllDerivedDefinitions("AsmOperandClass");
1388

1389
  // Pre-populate AsmOperandClasses map.
1390
  for (Record *Rec : AsmOperands) {
1391
    Classes.emplace_front();
1392
    AsmOperandClasses[Rec] = &Classes.front();
1393
  }
1394

1395
  unsigned Index = 0;
1396
  for (Record *Rec : AsmOperands) {
1397
    ClassInfo *CI = AsmOperandClasses[Rec];
1398
    CI->Kind = ClassInfo::UserClass0 + Index;
1399

1400
    ListInit *Supers = Rec->getValueAsListInit("SuperClasses");
1401
    for (Init *I : Supers->getValues()) {
1402
      DefInit *DI = dyn_cast<DefInit>(I);
1403
      if (!DI) {
1404
        PrintError(Rec->getLoc(), "Invalid super class reference!");
1405
        continue;
1406
      }
1407

1408
      ClassInfo *SC = AsmOperandClasses[DI->getDef()];
1409
      if (!SC)
1410
        PrintError(Rec->getLoc(), "Invalid super class reference!");
1411
      else
1412
        CI->SuperClasses.push_back(SC);
1413
    }
1414
    CI->ClassName = std::string(Rec->getValueAsString("Name"));
1415
    CI->Name = "MCK_" + CI->ClassName;
1416
    CI->ValueName = std::string(Rec->getName());
1417

1418
    // Get or construct the predicate method name.
1419
    Init *PMName = Rec->getValueInit("PredicateMethod");
1420
    if (StringInit *SI = dyn_cast<StringInit>(PMName)) {
1421
      CI->PredicateMethod = std::string(SI->getValue());
1422
    } else {
1423
      assert(isa<UnsetInit>(PMName) && "Unexpected PredicateMethod field!");
1424
      CI->PredicateMethod = "is" + CI->ClassName;
1425
    }
1426

1427
    // Get or construct the render method name.
1428
    Init *RMName = Rec->getValueInit("RenderMethod");
1429
    if (StringInit *SI = dyn_cast<StringInit>(RMName)) {
1430
      CI->RenderMethod = std::string(SI->getValue());
1431
    } else {
1432
      assert(isa<UnsetInit>(RMName) && "Unexpected RenderMethod field!");
1433
      CI->RenderMethod = "add" + CI->ClassName + "Operands";
1434
    }
1435

1436
    // Get the parse method name or leave it as empty.
1437
    Init *PRMName = Rec->getValueInit("ParserMethod");
1438
    if (StringInit *SI = dyn_cast<StringInit>(PRMName))
1439
      CI->ParserMethod = std::string(SI->getValue());
1440

1441
    // Get the diagnostic type and string or leave them as empty.
1442
    Init *DiagnosticType = Rec->getValueInit("DiagnosticType");
1443
    if (StringInit *SI = dyn_cast<StringInit>(DiagnosticType))
1444
      CI->DiagnosticType = std::string(SI->getValue());
1445
    Init *DiagnosticString = Rec->getValueInit("DiagnosticString");
1446
    if (StringInit *SI = dyn_cast<StringInit>(DiagnosticString))
1447
      CI->DiagnosticString = std::string(SI->getValue());
1448
    // If we have a DiagnosticString, we need a DiagnosticType for use within
1449
    // the matcher.
1450
    if (!CI->DiagnosticString.empty() && CI->DiagnosticType.empty())
1451
      CI->DiagnosticType = CI->ClassName;
1452

1453
    Init *IsOptional = Rec->getValueInit("IsOptional");
1454
    if (BitInit *BI = dyn_cast<BitInit>(IsOptional))
1455
      CI->IsOptional = BI->getValue();
1456

1457
    // Get or construct the default method name.
1458
    Init *DMName = Rec->getValueInit("DefaultMethod");
1459
    if (StringInit *SI = dyn_cast<StringInit>(DMName)) {
1460
      CI->DefaultMethod = std::string(SI->getValue());
1461
    } else {
1462
      assert(isa<UnsetInit>(DMName) && "Unexpected DefaultMethod field!");
1463
      CI->DefaultMethod = "default" + CI->ClassName + "Operands";
1464
    }
1465

1466
    ++Index;
1467
  }
1468
}
1469

1470
AsmMatcherInfo::AsmMatcherInfo(Record *asmParser, CodeGenTarget &target,
1471
                               RecordKeeper &records)
1472
    : Records(records), AsmParser(asmParser), Target(target) {}
1473

1474
/// buildOperandMatchInfo - Build the necessary information to handle user
1475
/// defined operand parsing methods.
1476
void AsmMatcherInfo::buildOperandMatchInfo() {
1477

1478
  /// Map containing a mask with all operands indices that can be found for
1479
  /// that class inside a instruction.
1480
  typedef std::map<ClassInfo *, unsigned, deref<std::less<>>> OpClassMaskTy;
1481
  OpClassMaskTy OpClassMask;
1482

1483
  bool CallCustomParserForAllOperands =
1484
      AsmParser->getValueAsBit("CallCustomParserForAllOperands");
1485
  for (const auto &MI : Matchables) {
1486
    OpClassMask.clear();
1487

1488
    // Keep track of all operands of this instructions which belong to the
1489
    // same class.
1490
    unsigned NumOptionalOps = 0;
1491
    for (unsigned i = 0, e = MI->AsmOperands.size(); i != e; ++i) {
1492
      const MatchableInfo::AsmOperand &Op = MI->AsmOperands[i];
1493
      if (CallCustomParserForAllOperands || !Op.Class->ParserMethod.empty()) {
1494
        unsigned &OperandMask = OpClassMask[Op.Class];
1495
        OperandMask |= maskTrailingOnes<unsigned>(NumOptionalOps + 1)
1496
                       << (i - NumOptionalOps);
1497
      }
1498
      if (Op.Class->IsOptional)
1499
        ++NumOptionalOps;
1500
    }
1501

1502
    // Generate operand match info for each mnemonic/operand class pair.
1503
    for (const auto &OCM : OpClassMask) {
1504
      unsigned OpMask = OCM.second;
1505
      ClassInfo *CI = OCM.first;
1506
      OperandMatchInfo.push_back(
1507
          OperandMatchEntry::create(MI.get(), CI, OpMask));
1508
    }
1509
  }
1510
}
1511

1512
void AsmMatcherInfo::buildInfo() {
1513
  // Build information about all of the AssemblerPredicates.
1514
  const std::vector<std::pair<Record *, SubtargetFeatureInfo>>
1515
      &SubtargetFeaturePairs = SubtargetFeatureInfo::getAll(Records);
1516
  SubtargetFeatures.insert(SubtargetFeaturePairs.begin(),
1517
                           SubtargetFeaturePairs.end());
1518
#ifndef NDEBUG
1519
  for (const auto &Pair : SubtargetFeatures)
1520
    LLVM_DEBUG(Pair.second.dump());
1521
#endif // NDEBUG
1522

1523
  bool HasMnemonicFirst = AsmParser->getValueAsBit("HasMnemonicFirst");
1524
  bool ReportMultipleNearMisses =
1525
      AsmParser->getValueAsBit("ReportMultipleNearMisses");
1526

1527
  // Parse the instructions; we need to do this first so that we can gather the
1528
  // singleton register classes.
1529
  SmallPtrSet<Record *, 16> SingletonRegisters;
1530
  unsigned VariantCount = Target.getAsmParserVariantCount();
1531
  for (unsigned VC = 0; VC != VariantCount; ++VC) {
1532
    Record *AsmVariant = Target.getAsmParserVariant(VC);
1533
    StringRef CommentDelimiter =
1534
        AsmVariant->getValueAsString("CommentDelimiter");
1535
    AsmVariantInfo Variant;
1536
    Variant.RegisterPrefix = AsmVariant->getValueAsString("RegisterPrefix");
1537
    Variant.TokenizingCharacters =
1538
        AsmVariant->getValueAsString("TokenizingCharacters");
1539
    Variant.SeparatorCharacters =
1540
        AsmVariant->getValueAsString("SeparatorCharacters");
1541
    Variant.BreakCharacters = AsmVariant->getValueAsString("BreakCharacters");
1542
    Variant.Name = AsmVariant->getValueAsString("Name");
1543
    Variant.AsmVariantNo = AsmVariant->getValueAsInt("Variant");
1544

1545
    for (const CodeGenInstruction *CGI : Target.getInstructionsByEnumValue()) {
1546

1547
      // If the tblgen -match-prefix option is specified (for tblgen hackers),
1548
      // filter the set of instructions we consider.
1549
      if (!StringRef(CGI->TheDef->getName()).starts_with(MatchPrefix))
1550
        continue;
1551

1552
      // Ignore "codegen only" instructions.
1553
      if (CGI->TheDef->getValueAsBit("isCodeGenOnly"))
1554
        continue;
1555

1556
      // Ignore instructions for different instructions
1557
      StringRef V = CGI->TheDef->getValueAsString("AsmVariantName");
1558
      if (!V.empty() && V != Variant.Name)
1559
        continue;
1560

1561
      auto II = std::make_unique<MatchableInfo>(*CGI);
1562

1563
      II->initialize(*this, SingletonRegisters, Variant, HasMnemonicFirst);
1564

1565
      // Ignore instructions which shouldn't be matched and diagnose invalid
1566
      // instruction definitions with an error.
1567
      if (!II->validate(CommentDelimiter, false))
1568
        continue;
1569

1570
      Matchables.push_back(std::move(II));
1571
    }
1572

1573
    // Parse all of the InstAlias definitions and stick them in the list of
1574
    // matchables.
1575
    std::vector<Record *> AllInstAliases =
1576
        Records.getAllDerivedDefinitions("InstAlias");
1577
    for (Record *InstAlias : AllInstAliases) {
1578
      auto Alias = std::make_unique<CodeGenInstAlias>(InstAlias, Target);
1579

1580
      // If the tblgen -match-prefix option is specified (for tblgen hackers),
1581
      // filter the set of instruction aliases we consider, based on the target
1582
      // instruction.
1583
      if (!StringRef(Alias->ResultInst->TheDef->getName())
1584
               .starts_with(MatchPrefix))
1585
        continue;
1586

1587
      StringRef V = Alias->TheDef->getValueAsString("AsmVariantName");
1588
      if (!V.empty() && V != Variant.Name)
1589
        continue;
1590

1591
      auto II = std::make_unique<MatchableInfo>(std::move(Alias));
1592

1593
      II->initialize(*this, SingletonRegisters, Variant, HasMnemonicFirst);
1594

1595
      // Validate the alias definitions.
1596
      II->validate(CommentDelimiter, true);
1597

1598
      Matchables.push_back(std::move(II));
1599
    }
1600
  }
1601

1602
  // Build info for the register classes.
1603
  buildRegisterClasses(SingletonRegisters);
1604

1605
  // Build info for the user defined assembly operand classes.
1606
  buildOperandClasses();
1607

1608
  // Build the information about matchables, now that we have fully formed
1609
  // classes.
1610
  std::vector<std::unique_ptr<MatchableInfo>> NewMatchables;
1611
  for (auto &II : Matchables) {
1612
    // Parse the tokens after the mnemonic.
1613
    // Note: buildInstructionOperandReference may insert new AsmOperands, so
1614
    // don't precompute the loop bound.
1615
    for (unsigned i = 0; i != II->AsmOperands.size(); ++i) {
1616
      MatchableInfo::AsmOperand &Op = II->AsmOperands[i];
1617
      StringRef Token = Op.Token;
1618

1619
      // Check for singleton registers.
1620
      if (Record *RegRecord = Op.SingletonReg) {
1621
        Op.Class = RegisterClasses[RegRecord];
1622
        assert(Op.Class && Op.Class->Registers.size() == 1 &&
1623
               "Unexpected class for singleton register");
1624
        continue;
1625
      }
1626

1627
      // Check for simple tokens.
1628
      if (Token[0] != '$') {
1629
        Op.Class = getTokenClass(Token);
1630
        continue;
1631
      }
1632

1633
      if (Token.size() > 1 && isdigit(Token[1])) {
1634
        Op.Class = getTokenClass(Token);
1635
        continue;
1636
      }
1637

1638
      // Otherwise this is an operand reference.
1639
      StringRef OperandName;
1640
      if (Token[1] == '{')
1641
        OperandName = Token.substr(2, Token.size() - 3);
1642
      else
1643
        OperandName = Token.substr(1);
1644

1645
      if (isa<const CodeGenInstruction *>(II->DefRec))
1646
        buildInstructionOperandReference(II.get(), OperandName, i);
1647
      else
1648
        buildAliasOperandReference(II.get(), OperandName, Op);
1649
    }
1650

1651
    if (isa<const CodeGenInstruction *>(II->DefRec)) {
1652
      II->buildInstructionResultOperands();
1653
      // If the instruction has a two-operand alias, build up the
1654
      // matchable here. We'll add them in bulk at the end to avoid
1655
      // confusing this loop.
1656
      StringRef Constraint =
1657
          II->TheDef->getValueAsString("TwoOperandAliasConstraint");
1658
      if (Constraint != "") {
1659
        // Start by making a copy of the original matchable.
1660
        auto AliasII = std::make_unique<MatchableInfo>(*II);
1661

1662
        // Adjust it to be a two-operand alias.
1663
        AliasII->formTwoOperandAlias(Constraint);
1664

1665
        // Add the alias to the matchables list.
1666
        NewMatchables.push_back(std::move(AliasII));
1667
      }
1668
    } else
1669
      // FIXME: The tied operands checking is not yet integrated with the
1670
      // framework for reporting multiple near misses. To prevent invalid
1671
      // formats from being matched with an alias if a tied-operands check
1672
      // would otherwise have disallowed it, we just disallow such constructs
1673
      // in TableGen completely.
1674
      II->buildAliasResultOperands(!ReportMultipleNearMisses);
1675
  }
1676
  if (!NewMatchables.empty())
1677
    Matchables.insert(Matchables.end(),
1678
                      std::make_move_iterator(NewMatchables.begin()),
1679
                      std::make_move_iterator(NewMatchables.end()));
1680

1681
  // Process token alias definitions and set up the associated superclass
1682
  // information.
1683
  std::vector<Record *> AllTokenAliases =
1684
      Records.getAllDerivedDefinitions("TokenAlias");
1685
  for (Record *Rec : AllTokenAliases) {
1686
    ClassInfo *FromClass = getTokenClass(Rec->getValueAsString("FromToken"));
1687
    ClassInfo *ToClass = getTokenClass(Rec->getValueAsString("ToToken"));
1688
    if (FromClass == ToClass)
1689
      PrintFatalError(Rec->getLoc(),
1690
                      "error: Destination value identical to source value.");
1691
    FromClass->SuperClasses.push_back(ToClass);
1692
  }
1693

1694
  // Reorder classes so that classes precede super classes.
1695
  Classes.sort();
1696

1697
#ifdef EXPENSIVE_CHECKS
1698
  // Verify that the table is sorted and operator < works transitively.
1699
  for (auto I = Classes.begin(), E = Classes.end(); I != E; ++I) {
1700
    for (auto J = I; J != E; ++J) {
1701
      assert(!(*J < *I));
1702
      assert(I == J || !J->isSubsetOf(*I));
1703
    }
1704
  }
1705
#endif
1706
}
1707

1708
/// buildInstructionOperandReference - The specified operand is a reference to a
1709
/// named operand such as $src.  Resolve the Class and OperandInfo pointers.
1710
void AsmMatcherInfo::buildInstructionOperandReference(MatchableInfo *II,
1711
                                                      StringRef OperandName,
1712
                                                      unsigned AsmOpIdx) {
1713
  const CodeGenInstruction &CGI = *cast<const CodeGenInstruction *>(II->DefRec);
1714
  const CGIOperandList &Operands = CGI.Operands;
1715
  MatchableInfo::AsmOperand *Op = &II->AsmOperands[AsmOpIdx];
1716

1717
  // Map this token to an operand.
1718
  unsigned Idx;
1719
  if (!Operands.hasOperandNamed(OperandName, Idx))
1720
    PrintFatalError(II->TheDef->getLoc(),
1721
                    "error: unable to find operand: '" + OperandName + "'");
1722

1723
  // If the instruction operand has multiple suboperands, but the parser
1724
  // match class for the asm operand is still the default "ImmAsmOperand",
1725
  // then handle each suboperand separately.
1726
  if (Op->SubOpIdx == -1 && Operands[Idx].MINumOperands > 1) {
1727
    Record *Rec = Operands[Idx].Rec;
1728
    assert(Rec->isSubClassOf("Operand") && "Unexpected operand!");
1729
    Record *MatchClass = Rec->getValueAsDef("ParserMatchClass");
1730
    if (MatchClass && MatchClass->getValueAsString("Name") == "Imm") {
1731
      // Insert remaining suboperands after AsmOpIdx in II->AsmOperands.
1732
      StringRef Token = Op->Token; // save this in case Op gets moved
1733
      for (unsigned SI = 1, SE = Operands[Idx].MINumOperands; SI != SE; ++SI) {
1734
        MatchableInfo::AsmOperand NewAsmOp(/*IsIsolatedToken=*/true, Token);
1735
        NewAsmOp.SubOpIdx = SI;
1736
        II->AsmOperands.insert(II->AsmOperands.begin() + AsmOpIdx + SI,
1737
                               NewAsmOp);
1738
      }
1739
      // Replace Op with first suboperand.
1740
      Op = &II->AsmOperands[AsmOpIdx]; // update the pointer in case it moved
1741
      Op->SubOpIdx = 0;
1742
    }
1743
  }
1744

1745
  // Set up the operand class.
1746
  Op->Class = getOperandClass(Operands[Idx], Op->SubOpIdx);
1747
  Op->OrigSrcOpName = OperandName;
1748

1749
  // If the named operand is tied, canonicalize it to the untied operand.
1750
  // For example, something like:
1751
  //   (outs GPR:$dst), (ins GPR:$src)
1752
  // with an asmstring of
1753
  //   "inc $src"
1754
  // we want to canonicalize to:
1755
  //   "inc $dst"
1756
  // so that we know how to provide the $dst operand when filling in the result.
1757
  int OITied = -1;
1758
  if (Operands[Idx].MINumOperands == 1)
1759
    OITied = Operands[Idx].getTiedRegister();
1760
  if (OITied != -1) {
1761
    // The tied operand index is an MIOperand index, find the operand that
1762
    // contains it.
1763
    std::pair<unsigned, unsigned> Idx = Operands.getSubOperandNumber(OITied);
1764
    OperandName = Operands[Idx.first].Name;
1765
    Op->SubOpIdx = Idx.second;
1766
  }
1767

1768
  Op->SrcOpName = OperandName;
1769
}
1770

1771
/// buildAliasOperandReference - When parsing an operand reference out of the
1772
/// matching string (e.g. "movsx $src, $dst"), determine what the class of the
1773
/// operand reference is by looking it up in the result pattern definition.
1774
void AsmMatcherInfo::buildAliasOperandReference(MatchableInfo *II,
1775
                                                StringRef OperandName,
1776
                                                MatchableInfo::AsmOperand &Op) {
1777
  const CodeGenInstAlias &CGA = *cast<const CodeGenInstAlias *>(II->DefRec);
1778

1779
  // Set up the operand class.
1780
  for (unsigned i = 0, e = CGA.ResultOperands.size(); i != e; ++i)
1781
    if (CGA.ResultOperands[i].isRecord() &&
1782
        CGA.ResultOperands[i].getName() == OperandName) {
1783
      // It's safe to go with the first one we find, because CodeGenInstAlias
1784
      // validates that all operands with the same name have the same record.
1785
      Op.SubOpIdx = CGA.ResultInstOperandIndex[i].second;
1786
      // Use the match class from the Alias definition, not the
1787
      // destination instruction, as we may have an immediate that's
1788
      // being munged by the match class.
1789
      Op.Class =
1790
          getOperandClass(CGA.ResultOperands[i].getRecord(), Op.SubOpIdx);
1791
      Op.SrcOpName = OperandName;
1792
      Op.OrigSrcOpName = OperandName;
1793
      return;
1794
    }
1795

1796
  PrintFatalError(II->TheDef->getLoc(),
1797
                  "error: unable to find operand: '" + OperandName + "'");
1798
}
1799

1800
void MatchableInfo::buildInstructionResultOperands() {
1801
  const CodeGenInstruction *ResultInst = getResultInst();
1802

1803
  // Loop over all operands of the result instruction, determining how to
1804
  // populate them.
1805
  for (const CGIOperandList::OperandInfo &OpInfo : ResultInst->Operands) {
1806
    // If this is a tied operand, just copy from the previously handled operand.
1807
    int TiedOp = -1;
1808
    if (OpInfo.MINumOperands == 1)
1809
      TiedOp = OpInfo.getTiedRegister();
1810
    if (TiedOp != -1) {
1811
      int TiedSrcOperand = findAsmOperandOriginallyNamed(OpInfo.Name);
1812
      if (TiedSrcOperand != -1 &&
1813
          ResOperands[TiedOp].Kind == ResOperand::RenderAsmOperand)
1814
        ResOperands.push_back(ResOperand::getTiedOp(
1815
            TiedOp, ResOperands[TiedOp].AsmOperandNum, TiedSrcOperand));
1816
      else
1817
        ResOperands.push_back(ResOperand::getTiedOp(TiedOp, 0, 0));
1818
      continue;
1819
    }
1820

1821
    int SrcOperand = findAsmOperandNamed(OpInfo.Name);
1822
    if (OpInfo.Name.empty() || SrcOperand == -1) {
1823
      // This may happen for operands that are tied to a suboperand of a
1824
      // complex operand.  Simply use a dummy value here; nobody should
1825
      // use this operand slot.
1826
      // FIXME: The long term goal is for the MCOperand list to not contain
1827
      // tied operands at all.
1828
      ResOperands.push_back(ResOperand::getImmOp(0));
1829
      continue;
1830
    }
1831

1832
    // Check if the one AsmOperand populates the entire operand.
1833
    unsigned NumOperands = OpInfo.MINumOperands;
1834
    if (AsmOperands[SrcOperand].SubOpIdx == -1) {
1835
      ResOperands.push_back(ResOperand::getRenderedOp(SrcOperand, NumOperands));
1836
      continue;
1837
    }
1838

1839
    // Add a separate ResOperand for each suboperand.
1840
    for (unsigned AI = 0; AI < NumOperands; ++AI) {
1841
      assert(AsmOperands[SrcOperand + AI].SubOpIdx == (int)AI &&
1842
             AsmOperands[SrcOperand + AI].SrcOpName == OpInfo.Name &&
1843
             "unexpected AsmOperands for suboperands");
1844
      ResOperands.push_back(ResOperand::getRenderedOp(SrcOperand + AI, 1));
1845
    }
1846
  }
1847
}
1848

1849
void MatchableInfo::buildAliasResultOperands(bool AliasConstraintsAreChecked) {
1850
  const CodeGenInstAlias &CGA = *cast<const CodeGenInstAlias *>(DefRec);
1851
  const CodeGenInstruction *ResultInst = getResultInst();
1852

1853
  // Map of:  $reg -> #lastref
1854
  //   where $reg is the name of the operand in the asm string
1855
  //   where #lastref is the last processed index where $reg was referenced in
1856
  //   the asm string.
1857
  SmallDenseMap<StringRef, int> OperandRefs;
1858

1859
  // Loop over all operands of the result instruction, determining how to
1860
  // populate them.
1861
  unsigned AliasOpNo = 0;
1862
  unsigned LastOpNo = CGA.ResultInstOperandIndex.size();
1863
  for (unsigned i = 0, e = ResultInst->Operands.size(); i != e; ++i) {
1864
    const CGIOperandList::OperandInfo *OpInfo = &ResultInst->Operands[i];
1865

1866
    // If this is a tied operand, just copy from the previously handled operand.
1867
    int TiedOp = -1;
1868
    if (OpInfo->MINumOperands == 1)
1869
      TiedOp = OpInfo->getTiedRegister();
1870
    if (TiedOp != -1) {
1871
      unsigned SrcOp1 = 0;
1872
      unsigned SrcOp2 = 0;
1873

1874
      // If an operand has been specified twice in the asm string,
1875
      // add the two source operand's indices to the TiedOp so that
1876
      // at runtime the 'tied' constraint is checked.
1877
      if (ResOperands[TiedOp].Kind == ResOperand::RenderAsmOperand) {
1878
        SrcOp1 = ResOperands[TiedOp].AsmOperandNum;
1879

1880
        // Find the next operand (similarly named operand) in the string.
1881
        StringRef Name = AsmOperands[SrcOp1].SrcOpName;
1882
        auto Insert = OperandRefs.try_emplace(Name, SrcOp1);
1883
        SrcOp2 = findAsmOperandNamed(Name, Insert.first->second);
1884

1885
        // Not updating the record in OperandRefs will cause TableGen
1886
        // to fail with an error at the end of this function.
1887
        if (AliasConstraintsAreChecked)
1888
          Insert.first->second = SrcOp2;
1889

1890
        // In case it only has one reference in the asm string,
1891
        // it doesn't need to be checked for tied constraints.
1892
        SrcOp2 = (SrcOp2 == (unsigned)-1) ? SrcOp1 : SrcOp2;
1893
      }
1894

1895
      // If the alias operand is of a different operand class, we only want
1896
      // to benefit from the tied-operands check and just match the operand
1897
      // as a normal, but not copy the original (TiedOp) to the result
1898
      // instruction. We do this by passing -1 as the tied operand to copy.
1899
      if (ResultInst->Operands[i].Rec->getName() !=
1900
          ResultInst->Operands[TiedOp].Rec->getName()) {
1901
        SrcOp1 = ResOperands[TiedOp].AsmOperandNum;
1902
        int SubIdx = CGA.ResultInstOperandIndex[AliasOpNo].second;
1903
        StringRef Name = CGA.ResultOperands[AliasOpNo].getName();
1904
        SrcOp2 = findAsmOperand(Name, SubIdx);
1905
        ResOperands.push_back(
1906
            ResOperand::getTiedOp((unsigned)-1, SrcOp1, SrcOp2));
1907
      } else {
1908
        ResOperands.push_back(ResOperand::getTiedOp(TiedOp, SrcOp1, SrcOp2));
1909
        continue;
1910
      }
1911
    }
1912

1913
    // Handle all the suboperands for this operand.
1914
    const std::string &OpName = OpInfo->Name;
1915
    for (; AliasOpNo < LastOpNo &&
1916
           CGA.ResultInstOperandIndex[AliasOpNo].first == i;
1917
         ++AliasOpNo) {
1918
      int SubIdx = CGA.ResultInstOperandIndex[AliasOpNo].second;
1919

1920
      // Find out what operand from the asmparser that this MCInst operand
1921
      // comes from.
1922
      switch (CGA.ResultOperands[AliasOpNo].Kind) {
1923
      case CodeGenInstAlias::ResultOperand::K_Record: {
1924
        StringRef Name = CGA.ResultOperands[AliasOpNo].getName();
1925
        int SrcOperand = findAsmOperand(Name, SubIdx);
1926
        if (SrcOperand == -1)
1927
          PrintFatalError(TheDef->getLoc(),
1928
                          "Instruction '" + TheDef->getName() +
1929
                              "' has operand '" + OpName +
1930
                              "' that doesn't appear in asm string!");
1931

1932
        // Add it to the operand references. If it is added a second time, the
1933
        // record won't be updated and it will fail later on.
1934
        OperandRefs.try_emplace(Name, SrcOperand);
1935

1936
        unsigned NumOperands = (SubIdx == -1 ? OpInfo->MINumOperands : 1);
1937
        ResOperands.push_back(
1938
            ResOperand::getRenderedOp(SrcOperand, NumOperands));
1939
        break;
1940
      }
1941
      case CodeGenInstAlias::ResultOperand::K_Imm: {
1942
        int64_t ImmVal = CGA.ResultOperands[AliasOpNo].getImm();
1943
        ResOperands.push_back(ResOperand::getImmOp(ImmVal));
1944
        break;
1945
      }
1946
      case CodeGenInstAlias::ResultOperand::K_Reg: {
1947
        Record *Reg = CGA.ResultOperands[AliasOpNo].getRegister();
1948
        ResOperands.push_back(ResOperand::getRegOp(Reg));
1949
        break;
1950
      }
1951
      }
1952
    }
1953
  }
1954

1955
  // Check that operands are not repeated more times than is supported.
1956
  for (auto &T : OperandRefs) {
1957
    if (T.second != -1 && findAsmOperandNamed(T.first, T.second) != -1)
1958
      PrintFatalError(TheDef->getLoc(),
1959
                      "Operand '" + T.first + "' can never be matched");
1960
  }
1961
}
1962

1963
static unsigned
1964
getConverterOperandID(const std::string &Name,
1965
                      SmallSetVector<CachedHashString, 16> &Table,
1966
                      bool &IsNew) {
1967
  IsNew = Table.insert(CachedHashString(Name));
1968

1969
  unsigned ID = IsNew ? Table.size() - 1 : find(Table, Name) - Table.begin();
1970

1971
  assert(ID < Table.size());
1972

1973
  return ID;
1974
}
1975

1976
static unsigned
1977
emitConvertFuncs(CodeGenTarget &Target, StringRef ClassName,
1978
                 std::vector<std::unique_ptr<MatchableInfo>> &Infos,
1979
                 bool HasMnemonicFirst, bool HasOptionalOperands,
1980
                 raw_ostream &OS) {
1981
  SmallSetVector<CachedHashString, 16> OperandConversionKinds;
1982
  SmallSetVector<CachedHashString, 16> InstructionConversionKinds;
1983
  std::vector<std::vector<uint8_t>> ConversionTable;
1984
  size_t MaxRowLength = 2; // minimum is custom converter plus terminator.
1985

1986
  // TargetOperandClass - This is the target's operand class, like X86Operand.
1987
  std::string TargetOperandClass = Target.getName().str() + "Operand";
1988

1989
  // Write the convert function to a separate stream, so we can drop it after
1990
  // the enum. We'll build up the conversion handlers for the individual
1991
  // operand types opportunistically as we encounter them.
1992
  std::string ConvertFnBody;
1993
  raw_string_ostream CvtOS(ConvertFnBody);
1994
  // Start the unified conversion function.
1995
  if (HasOptionalOperands) {
1996
    CvtOS << "void " << Target.getName() << ClassName << "::\n"
1997
          << "convertToMCInst(unsigned Kind, MCInst &Inst, "
1998
          << "unsigned Opcode,\n"
1999
          << "                const OperandVector &Operands,\n"
2000
          << "                const SmallBitVector &OptionalOperandsMask,\n"
2001
          << "                ArrayRef<unsigned> DefaultsOffset) {\n";
2002
  } else {
2003
    CvtOS << "void " << Target.getName() << ClassName << "::\n"
2004
          << "convertToMCInst(unsigned Kind, MCInst &Inst, "
2005
          << "unsigned Opcode,\n"
2006
          << "                const OperandVector &Operands) {\n";
2007
  }
2008
  CvtOS << "  assert(Kind < CVT_NUM_SIGNATURES && \"Invalid signature!\");\n";
2009
  CvtOS << "  const uint8_t *Converter = ConversionTable[Kind];\n";
2010
  CvtOS << "  Inst.setOpcode(Opcode);\n";
2011
  CvtOS << "  for (const uint8_t *p = Converter; *p; p += 2) {\n";
2012
  if (HasOptionalOperands) {
2013
    // When optional operands are involved, formal and actual operand indices
2014
    // may differ. Map the former to the latter by subtracting the number of
2015
    // absent optional operands.
2016
    // FIXME: This is not an operand index in the CVT_Tied case
2017
    CvtOS << "    unsigned OpIdx = *(p + 1) - DefaultsOffset[*(p + 1)];\n";
2018
  } else {
2019
    CvtOS << "    unsigned OpIdx = *(p + 1);\n";
2020
  }
2021
  CvtOS << "    switch (*p) {\n";
2022
  CvtOS << "    default: llvm_unreachable(\"invalid conversion entry!\");\n";
2023
  CvtOS << "    case CVT_Reg:\n";
2024
  CvtOS << "      static_cast<" << TargetOperandClass
2025
        << " &>(*Operands[OpIdx]).addRegOperands(Inst, 1);\n";
2026
  CvtOS << "      break;\n";
2027
  CvtOS << "    case CVT_Tied: {\n";
2028
  CvtOS << "      assert(*(p + 1) < (size_t)(std::end(TiedAsmOperandTable) -\n";
2029
  CvtOS
2030
      << "                              std::begin(TiedAsmOperandTable)) &&\n";
2031
  CvtOS << "             \"Tied operand not found\");\n";
2032
  CvtOS << "      unsigned TiedResOpnd = TiedAsmOperandTable[*(p + 1)][0];\n";
2033
  CvtOS << "      if (TiedResOpnd != (uint8_t)-1)\n";
2034
  CvtOS << "        Inst.addOperand(Inst.getOperand(TiedResOpnd));\n";
2035
  CvtOS << "      break;\n";
2036
  CvtOS << "    }\n";
2037

2038
  std::string OperandFnBody;
2039
  raw_string_ostream OpOS(OperandFnBody);
2040
  // Start the operand number lookup function.
2041
  OpOS << "void " << Target.getName() << ClassName << "::\n"
2042
       << "convertToMapAndConstraints(unsigned Kind,\n";
2043
  OpOS.indent(27);
2044
  OpOS << "const OperandVector &Operands) {\n"
2045
       << "  assert(Kind < CVT_NUM_SIGNATURES && \"Invalid signature!\");\n"
2046
       << "  unsigned NumMCOperands = 0;\n"
2047
       << "  const uint8_t *Converter = ConversionTable[Kind];\n"
2048
       << "  for (const uint8_t *p = Converter; *p; p += 2) {\n"
2049
       << "    switch (*p) {\n"
2050
       << "    default: llvm_unreachable(\"invalid conversion entry!\");\n"
2051
       << "    case CVT_Reg:\n"
2052
       << "      Operands[*(p + 1)]->setMCOperandNum(NumMCOperands);\n"
2053
       << "      Operands[*(p + 1)]->setConstraint(\"r\");\n"
2054
       << "      ++NumMCOperands;\n"
2055
       << "      break;\n"
2056
       << "    case CVT_Tied:\n"
2057
       << "      ++NumMCOperands;\n"
2058
       << "      break;\n";
2059

2060
  // Pre-populate the operand conversion kinds with the standard always
2061
  // available entries.
2062
  OperandConversionKinds.insert(CachedHashString("CVT_Done"));
2063
  OperandConversionKinds.insert(CachedHashString("CVT_Reg"));
2064
  OperandConversionKinds.insert(CachedHashString("CVT_Tied"));
2065
  enum { CVT_Done, CVT_Reg, CVT_Tied };
2066

2067
  // Map of e.g. <0, 2, 3> -> "Tie_0_2_3" enum label.
2068
  std::map<std::tuple<uint8_t, uint8_t, uint8_t>, std::string>
2069
      TiedOperandsEnumMap;
2070

2071
  for (auto &II : Infos) {
2072
    // Check if we have a custom match function.
2073
    StringRef AsmMatchConverter =
2074
        II->getResultInst()->TheDef->getValueAsString("AsmMatchConverter");
2075
    if (!AsmMatchConverter.empty() && II->UseInstAsmMatchConverter) {
2076
      std::string Signature = ("ConvertCustom_" + AsmMatchConverter).str();
2077
      II->ConversionFnKind = Signature;
2078

2079
      // Check if we have already generated this signature.
2080
      if (!InstructionConversionKinds.insert(CachedHashString(Signature)))
2081
        continue;
2082

2083
      // Remember this converter for the kind enum.
2084
      unsigned KindID = OperandConversionKinds.size();
2085
      OperandConversionKinds.insert(
2086
          CachedHashString("CVT_" + getEnumNameForToken(AsmMatchConverter)));
2087

2088
      // Add the converter row for this instruction.
2089
      ConversionTable.emplace_back();
2090
      ConversionTable.back().push_back(KindID);
2091
      ConversionTable.back().push_back(CVT_Done);
2092

2093
      // Add the handler to the conversion driver function.
2094
      CvtOS << "    case CVT_" << getEnumNameForToken(AsmMatchConverter)
2095
            << ":\n"
2096
            << "      " << AsmMatchConverter << "(Inst, Operands);\n"
2097
            << "      break;\n";
2098

2099
      // FIXME: Handle the operand number lookup for custom match functions.
2100
      continue;
2101
    }
2102

2103
    // Build the conversion function signature.
2104
    std::string Signature = "Convert";
2105

2106
    std::vector<uint8_t> ConversionRow;
2107

2108
    // Compute the convert enum and the case body.
2109
    MaxRowLength = std::max(MaxRowLength, II->ResOperands.size() * 2 + 1);
2110

2111
    for (unsigned i = 0, e = II->ResOperands.size(); i != e; ++i) {
2112
      const MatchableInfo::ResOperand &OpInfo = II->ResOperands[i];
2113

2114
      // Generate code to populate each result operand.
2115
      switch (OpInfo.Kind) {
2116
      case MatchableInfo::ResOperand::RenderAsmOperand: {
2117
        // This comes from something we parsed.
2118
        const MatchableInfo::AsmOperand &Op =
2119
            II->AsmOperands[OpInfo.AsmOperandNum];
2120

2121
        // Registers are always converted the same, don't duplicate the
2122
        // conversion function based on them.
2123
        Signature += "__";
2124
        std::string Class;
2125
        Class = Op.Class->isRegisterClass() ? "Reg" : Op.Class->ClassName;
2126
        Signature += Class;
2127
        Signature += utostr(OpInfo.MINumOperands);
2128
        Signature += "_" + itostr(OpInfo.AsmOperandNum);
2129

2130
        // Add the conversion kind, if necessary, and get the associated ID
2131
        // the index of its entry in the vector).
2132
        std::string Name =
2133
            "CVT_" +
2134
            (Op.Class->isRegisterClass() ? "Reg" : Op.Class->RenderMethod);
2135
        if (Op.Class->IsOptional) {
2136
          // For optional operands we must also care about DefaultMethod
2137
          assert(HasOptionalOperands);
2138
          Name += "_" + Op.Class->DefaultMethod;
2139
        }
2140
        Name = getEnumNameForToken(Name);
2141

2142
        bool IsNewConverter = false;
2143
        unsigned ID =
2144
            getConverterOperandID(Name, OperandConversionKinds, IsNewConverter);
2145

2146
        // Add the operand entry to the instruction kind conversion row.
2147
        ConversionRow.push_back(ID);
2148
        ConversionRow.push_back(OpInfo.AsmOperandNum + HasMnemonicFirst);
2149

2150
        if (!IsNewConverter)
2151
          break;
2152

2153
        // This is a new operand kind. Add a handler for it to the
2154
        // converter driver.
2155
        CvtOS << "    case " << Name << ":\n";
2156
        if (Op.Class->IsOptional) {
2157
          // If optional operand is not present in actual instruction then we
2158
          // should call its DefaultMethod before RenderMethod
2159
          assert(HasOptionalOperands);
2160
          CvtOS << "      if (OptionalOperandsMask[*(p + 1) - 1]) {\n"
2161
                << "        " << Op.Class->DefaultMethod << "()"
2162
                << "->" << Op.Class->RenderMethod << "(Inst, "
2163
                << OpInfo.MINumOperands << ");\n"
2164
                << "      } else {\n"
2165
                << "        static_cast<" << TargetOperandClass
2166
                << " &>(*Operands[OpIdx])." << Op.Class->RenderMethod
2167
                << "(Inst, " << OpInfo.MINumOperands << ");\n"
2168
                << "      }\n";
2169
        } else {
2170
          CvtOS << "      static_cast<" << TargetOperandClass
2171
                << " &>(*Operands[OpIdx])." << Op.Class->RenderMethod
2172
                << "(Inst, " << OpInfo.MINumOperands << ");\n";
2173
        }
2174
        CvtOS << "      break;\n";
2175

2176
        // Add a handler for the operand number lookup.
2177
        OpOS << "    case " << Name << ":\n"
2178
             << "      Operands[*(p + 1)]->setMCOperandNum(NumMCOperands);\n";
2179

2180
        if (Op.Class->isRegisterClass())
2181
          OpOS << "      Operands[*(p + 1)]->setConstraint(\"r\");\n";
2182
        else
2183
          OpOS << "      Operands[*(p + 1)]->setConstraint(\"m\");\n";
2184
        OpOS << "      NumMCOperands += " << OpInfo.MINumOperands << ";\n"
2185
             << "      break;\n";
2186
        break;
2187
      }
2188
      case MatchableInfo::ResOperand::TiedOperand: {
2189
        // If this operand is tied to a previous one, just copy the MCInst
2190
        // operand from the earlier one.We can only tie single MCOperand values.
2191
        assert(OpInfo.MINumOperands == 1 && "Not a singular MCOperand");
2192
        uint8_t TiedOp = OpInfo.TiedOperands.ResOpnd;
2193
        uint8_t SrcOp1 = OpInfo.TiedOperands.SrcOpnd1Idx + HasMnemonicFirst;
2194
        uint8_t SrcOp2 = OpInfo.TiedOperands.SrcOpnd2Idx + HasMnemonicFirst;
2195
        assert((i > TiedOp || TiedOp == (uint8_t)-1) &&
2196
               "Tied operand precedes its target!");
2197
        auto TiedTupleName = std::string("Tie") + utostr(TiedOp) + '_' +
2198
                             utostr(SrcOp1) + '_' + utostr(SrcOp2);
2199
        Signature += "__" + TiedTupleName;
2200
        ConversionRow.push_back(CVT_Tied);
2201
        ConversionRow.push_back(TiedOp);
2202
        ConversionRow.push_back(SrcOp1);
2203
        ConversionRow.push_back(SrcOp2);
2204

2205
        // Also create an 'enum' for this combination of tied operands.
2206
        auto Key = std::tuple(TiedOp, SrcOp1, SrcOp2);
2207
        TiedOperandsEnumMap.emplace(Key, TiedTupleName);
2208
        break;
2209
      }
2210
      case MatchableInfo::ResOperand::ImmOperand: {
2211
        int64_t Val = OpInfo.ImmVal;
2212
        std::string Ty = "imm_" + itostr(Val);
2213
        Ty = getEnumNameForToken(Ty);
2214
        Signature += "__" + Ty;
2215

2216
        std::string Name = "CVT_" + Ty;
2217
        bool IsNewConverter = false;
2218
        unsigned ID =
2219
            getConverterOperandID(Name, OperandConversionKinds, IsNewConverter);
2220
        // Add the operand entry to the instruction kind conversion row.
2221
        ConversionRow.push_back(ID);
2222
        ConversionRow.push_back(0);
2223

2224
        if (!IsNewConverter)
2225
          break;
2226

2227
        CvtOS << "    case " << Name << ":\n"
2228
              << "      Inst.addOperand(MCOperand::createImm(" << Val << "));\n"
2229
              << "      break;\n";
2230

2231
        OpOS << "    case " << Name << ":\n"
2232
             << "      Operands[*(p + 1)]->setMCOperandNum(NumMCOperands);\n"
2233
             << "      Operands[*(p + 1)]->setConstraint(\"\");\n"
2234
             << "      ++NumMCOperands;\n"
2235
             << "      break;\n";
2236
        break;
2237
      }
2238
      case MatchableInfo::ResOperand::RegOperand: {
2239
        std::string Reg, Name;
2240
        if (!OpInfo.Register) {
2241
          Name = "reg0";
2242
          Reg = "0";
2243
        } else {
2244
          Reg = getQualifiedName(OpInfo.Register);
2245
          Name = "reg" + OpInfo.Register->getName().str();
2246
        }
2247
        Signature += "__" + Name;
2248
        Name = "CVT_" + Name;
2249
        bool IsNewConverter = false;
2250
        unsigned ID =
2251
            getConverterOperandID(Name, OperandConversionKinds, IsNewConverter);
2252
        // Add the operand entry to the instruction kind conversion row.
2253
        ConversionRow.push_back(ID);
2254
        ConversionRow.push_back(0);
2255

2256
        if (!IsNewConverter)
2257
          break;
2258
        CvtOS << "    case " << Name << ":\n"
2259
              << "      Inst.addOperand(MCOperand::createReg(" << Reg << "));\n"
2260
              << "      break;\n";
2261

2262
        OpOS << "    case " << Name << ":\n"
2263
             << "      Operands[*(p + 1)]->setMCOperandNum(NumMCOperands);\n"
2264
             << "      Operands[*(p + 1)]->setConstraint(\"m\");\n"
2265
             << "      ++NumMCOperands;\n"
2266
             << "      break;\n";
2267
      }
2268
      }
2269
    }
2270

2271
    // If there were no operands, add to the signature to that effect
2272
    if (Signature == "Convert")
2273
      Signature += "_NoOperands";
2274

2275
    II->ConversionFnKind = Signature;
2276

2277
    // Save the signature. If we already have it, don't add a new row
2278
    // to the table.
2279
    if (!InstructionConversionKinds.insert(CachedHashString(Signature)))
2280
      continue;
2281

2282
    // Add the row to the table.
2283
    ConversionTable.push_back(std::move(ConversionRow));
2284
  }
2285

2286
  // Finish up the converter driver function.
2287
  CvtOS << "    }\n  }\n}\n\n";
2288

2289
  // Finish up the operand number lookup function.
2290
  OpOS << "    }\n  }\n}\n\n";
2291

2292
  // Output a static table for tied operands.
2293
  if (TiedOperandsEnumMap.size()) {
2294
    // The number of tied operand combinations will be small in practice,
2295
    // but just add the assert to be sure.
2296
    assert(TiedOperandsEnumMap.size() <= 254 &&
2297
           "Too many tied-operand combinations to reference with "
2298
           "an 8bit offset from the conversion table, where index "
2299
           "'255' is reserved as operand not to be copied.");
2300

2301
    OS << "enum {\n";
2302
    for (auto &KV : TiedOperandsEnumMap) {
2303
      OS << "  " << KV.second << ",\n";
2304
    }
2305
    OS << "};\n\n";
2306

2307
    OS << "static const uint8_t TiedAsmOperandTable[][3] = {\n";
2308
    for (auto &KV : TiedOperandsEnumMap) {
2309
      OS << "  /* " << KV.second << " */ { " << utostr(std::get<0>(KV.first))
2310
         << ", " << utostr(std::get<1>(KV.first)) << ", "
2311
         << utostr(std::get<2>(KV.first)) << " },\n";
2312
    }
2313
    OS << "};\n\n";
2314
  } else
2315
    OS << "static const uint8_t TiedAsmOperandTable[][3] = "
2316
          "{ /* empty  */ {0, 0, 0} };\n\n";
2317

2318
  OS << "namespace {\n";
2319

2320
  // Output the operand conversion kind enum.
2321
  OS << "enum OperatorConversionKind {\n";
2322
  for (const auto &Converter : OperandConversionKinds)
2323
    OS << "  " << Converter << ",\n";
2324
  OS << "  CVT_NUM_CONVERTERS\n";
2325
  OS << "};\n\n";
2326

2327
  // Output the instruction conversion kind enum.
2328
  OS << "enum InstructionConversionKind {\n";
2329
  for (const auto &Signature : InstructionConversionKinds)
2330
    OS << "  " << Signature << ",\n";
2331
  OS << "  CVT_NUM_SIGNATURES\n";
2332
  OS << "};\n\n";
2333

2334
  OS << "} // end anonymous namespace\n\n";
2335

2336
  // Output the conversion table.
2337
  OS << "static const uint8_t ConversionTable[CVT_NUM_SIGNATURES]["
2338
     << MaxRowLength << "] = {\n";
2339

2340
  for (unsigned Row = 0, ERow = ConversionTable.size(); Row != ERow; ++Row) {
2341
    assert(ConversionTable[Row].size() % 2 == 0 && "bad conversion row!");
2342
    OS << "  // " << InstructionConversionKinds[Row] << "\n";
2343
    OS << "  { ";
2344
    for (unsigned i = 0, e = ConversionTable[Row].size(); i != e; i += 2) {
2345
      OS << OperandConversionKinds[ConversionTable[Row][i]] << ", ";
2346
      if (OperandConversionKinds[ConversionTable[Row][i]] !=
2347
          CachedHashString("CVT_Tied")) {
2348
        OS << (unsigned)(ConversionTable[Row][i + 1]) << ", ";
2349
        continue;
2350
      }
2351

2352
      // For a tied operand, emit a reference to the TiedAsmOperandTable
2353
      // that contains the operand to copy, and the parsed operands to
2354
      // check for their tied constraints.
2355
      auto Key = std::tuple((uint8_t)ConversionTable[Row][i + 1],
2356
                            (uint8_t)ConversionTable[Row][i + 2],
2357
                            (uint8_t)ConversionTable[Row][i + 3]);
2358
      auto TiedOpndEnum = TiedOperandsEnumMap.find(Key);
2359
      assert(TiedOpndEnum != TiedOperandsEnumMap.end() &&
2360
             "No record for tied operand pair");
2361
      OS << TiedOpndEnum->second << ", ";
2362
      i += 2;
2363
    }
2364
    OS << "CVT_Done },\n";
2365
  }
2366

2367
  OS << "};\n\n";
2368

2369
  // Spit out the conversion driver function.
2370
  OS << ConvertFnBody;
2371

2372
  // Spit out the operand number lookup function.
2373
  OS << OperandFnBody;
2374

2375
  return ConversionTable.size();
2376
}
2377

2378
/// emitMatchClassEnumeration - Emit the enumeration for match class kinds.
2379
static void emitMatchClassEnumeration(CodeGenTarget &Target,
2380
                                      std::forward_list<ClassInfo> &Infos,
2381
                                      raw_ostream &OS) {
2382
  OS << "namespace {\n\n";
2383

2384
  OS << "/// MatchClassKind - The kinds of classes which participate in\n"
2385
     << "/// instruction matching.\n";
2386
  OS << "enum MatchClassKind {\n";
2387
  OS << "  InvalidMatchClass = 0,\n";
2388
  OS << "  OptionalMatchClass = 1,\n";
2389
  ClassInfo::ClassInfoKind LastKind = ClassInfo::Token;
2390
  StringRef LastName = "OptionalMatchClass";
2391
  for (const auto &CI : Infos) {
2392
    if (LastKind == ClassInfo::Token && CI.Kind != ClassInfo::Token) {
2393
      OS << "  MCK_LAST_TOKEN = " << LastName << ",\n";
2394
    } else if (LastKind < ClassInfo::UserClass0 &&
2395
               CI.Kind >= ClassInfo::UserClass0) {
2396
      OS << "  MCK_LAST_REGISTER = " << LastName << ",\n";
2397
    }
2398
    LastKind = (ClassInfo::ClassInfoKind)CI.Kind;
2399
    LastName = CI.Name;
2400

2401
    OS << "  " << CI.Name << ", // ";
2402
    if (CI.Kind == ClassInfo::Token) {
2403
      OS << "'" << CI.ValueName << "'\n";
2404
    } else if (CI.isRegisterClass()) {
2405
      if (!CI.ValueName.empty())
2406
        OS << "register class '" << CI.ValueName << "'\n";
2407
      else
2408
        OS << "derived register class\n";
2409
    } else {
2410
      OS << "user defined class '" << CI.ValueName << "'\n";
2411
    }
2412
  }
2413
  OS << "  NumMatchClassKinds\n";
2414
  OS << "};\n\n";
2415

2416
  OS << "} // end anonymous namespace\n\n";
2417
}
2418

2419
/// emitMatchClassDiagStrings - Emit a function to get the diagnostic text to be
2420
/// used when an assembly operand does not match the expected operand class.
2421
static void emitOperandMatchErrorDiagStrings(AsmMatcherInfo &Info,
2422
                                             raw_ostream &OS) {
2423
  // If the target does not use DiagnosticString for any operands, don't emit
2424
  // an unused function.
2425
  if (llvm::all_of(Info.Classes, [](const ClassInfo &CI) {
2426
        return CI.DiagnosticString.empty();
2427
      }))
2428
    return;
2429

2430
  OS << "static const char *getMatchKindDiag(" << Info.Target.getName()
2431
     << "AsmParser::" << Info.Target.getName()
2432
     << "MatchResultTy MatchResult) {\n";
2433
  OS << "  switch (MatchResult) {\n";
2434

2435
  for (const auto &CI : Info.Classes) {
2436
    if (!CI.DiagnosticString.empty()) {
2437
      assert(!CI.DiagnosticType.empty() &&
2438
             "DiagnosticString set without DiagnosticType");
2439
      OS << "  case " << Info.Target.getName() << "AsmParser::Match_"
2440
         << CI.DiagnosticType << ":\n";
2441
      OS << "    return \"" << CI.DiagnosticString << "\";\n";
2442
    }
2443
  }
2444

2445
  OS << "  default:\n";
2446
  OS << "    return nullptr;\n";
2447

2448
  OS << "  }\n";
2449
  OS << "}\n\n";
2450
}
2451

2452
static void emitRegisterMatchErrorFunc(AsmMatcherInfo &Info, raw_ostream &OS) {
2453
  OS << "static unsigned getDiagKindFromRegisterClass(MatchClassKind "
2454
        "RegisterClass) {\n";
2455
  if (none_of(Info.Classes, [](const ClassInfo &CI) {
2456
        return CI.isRegisterClass() && !CI.DiagnosticType.empty();
2457
      })) {
2458
    OS << "  return MCTargetAsmParser::Match_InvalidOperand;\n";
2459
  } else {
2460
    OS << "  switch (RegisterClass) {\n";
2461
    for (const auto &CI : Info.Classes) {
2462
      if (CI.isRegisterClass() && !CI.DiagnosticType.empty()) {
2463
        OS << "  case " << CI.Name << ":\n";
2464
        OS << "    return " << Info.Target.getName() << "AsmParser::Match_"
2465
           << CI.DiagnosticType << ";\n";
2466
      }
2467
    }
2468

2469
    OS << "  default:\n";
2470
    OS << "    return MCTargetAsmParser::Match_InvalidOperand;\n";
2471

2472
    OS << "  }\n";
2473
  }
2474
  OS << "}\n\n";
2475
}
2476

2477
/// emitValidateOperandClass - Emit the function to validate an operand class.
2478
static void emitValidateOperandClass(AsmMatcherInfo &Info, raw_ostream &OS) {
2479
  OS << "static unsigned validateOperandClass(MCParsedAsmOperand &GOp, "
2480
     << "MatchClassKind Kind) {\n";
2481
  OS << "  " << Info.Target.getName() << "Operand &Operand = ("
2482
     << Info.Target.getName() << "Operand &)GOp;\n";
2483

2484
  // The InvalidMatchClass is not to match any operand.
2485
  OS << "  if (Kind == InvalidMatchClass)\n";
2486
  OS << "    return MCTargetAsmParser::Match_InvalidOperand;\n\n";
2487

2488
  // Check for Token operands first.
2489
  // FIXME: Use a more specific diagnostic type.
2490
  OS << "  if (Operand.isToken() && Kind <= MCK_LAST_TOKEN)\n";
2491
  OS << "    return isSubclass(matchTokenString(Operand.getToken()), Kind) ?\n"
2492
     << "             MCTargetAsmParser::Match_Success :\n"
2493
     << "             MCTargetAsmParser::Match_InvalidOperand;\n\n";
2494

2495
  // Check the user classes. We don't care what order since we're only
2496
  // actually matching against one of them.
2497
  OS << "  switch (Kind) {\n"
2498
        "  default: break;\n";
2499
  for (const auto &CI : Info.Classes) {
2500
    if (!CI.isUserClass())
2501
      continue;
2502

2503
    OS << "  // '" << CI.ClassName << "' class\n";
2504
    OS << "  case " << CI.Name << ": {\n";
2505
    OS << "    DiagnosticPredicate DP(Operand." << CI.PredicateMethod
2506
       << "());\n";
2507
    OS << "    if (DP.isMatch())\n";
2508
    OS << "      return MCTargetAsmParser::Match_Success;\n";
2509
    if (!CI.DiagnosticType.empty()) {
2510
      OS << "    if (DP.isNearMatch())\n";
2511
      OS << "      return " << Info.Target.getName() << "AsmParser::Match_"
2512
         << CI.DiagnosticType << ";\n";
2513
      OS << "    break;\n";
2514
    } else
2515
      OS << "    break;\n";
2516
    OS << "    }\n";
2517
  }
2518
  OS << "  } // end switch (Kind)\n\n";
2519

2520
  // Check for register operands, including sub-classes.
2521
  OS << "  if (Operand.isReg()) {\n";
2522
  OS << "    MatchClassKind OpKind;\n";
2523
  OS << "    switch (Operand.getReg().id()) {\n";
2524
  OS << "    default: OpKind = InvalidMatchClass; break;\n";
2525
  for (const auto &RC : Info.RegisterClasses)
2526
    OS << "    case " << RC.first->getValueAsString("Namespace")
2527
       << "::" << RC.first->getName() << ": OpKind = " << RC.second->Name
2528
       << "; break;\n";
2529
  OS << "    }\n";
2530
  OS << "    return isSubclass(OpKind, Kind) ? "
2531
     << "(unsigned)MCTargetAsmParser::Match_Success :\n                     "
2532
     << "                 getDiagKindFromRegisterClass(Kind);\n  }\n\n";
2533

2534
  // Expected operand is a register, but actual is not.
2535
  OS << "  if (Kind > MCK_LAST_TOKEN && Kind <= MCK_LAST_REGISTER)\n";
2536
  OS << "    return getDiagKindFromRegisterClass(Kind);\n\n";
2537

2538
  // Generic fallthrough match failure case for operands that don't have
2539
  // specialized diagnostic types.
2540
  OS << "  return MCTargetAsmParser::Match_InvalidOperand;\n";
2541
  OS << "}\n\n";
2542
}
2543

2544
/// emitIsSubclass - Emit the subclass predicate function.
2545
static void emitIsSubclass(CodeGenTarget &Target,
2546
                           std::forward_list<ClassInfo> &Infos,
2547
                           raw_ostream &OS) {
2548
  OS << "/// isSubclass - Compute whether \\p A is a subclass of \\p B.\n";
2549
  OS << "static bool isSubclass(MatchClassKind A, MatchClassKind B) {\n";
2550
  OS << "  if (A == B)\n";
2551
  OS << "    return true;\n\n";
2552

2553
  bool EmittedSwitch = false;
2554
  for (const auto &A : Infos) {
2555
    std::vector<StringRef> SuperClasses;
2556
    if (A.IsOptional)
2557
      SuperClasses.push_back("OptionalMatchClass");
2558
    for (const auto &B : Infos) {
2559
      if (&A != &B && A.isSubsetOf(B))
2560
        SuperClasses.push_back(B.Name);
2561
    }
2562

2563
    if (SuperClasses.empty())
2564
      continue;
2565

2566
    // If this is the first SuperClass, emit the switch header.
2567
    if (!EmittedSwitch) {
2568
      OS << "  switch (A) {\n";
2569
      OS << "  default:\n";
2570
      OS << "    return false;\n";
2571
      EmittedSwitch = true;
2572
    }
2573

2574
    OS << "\n  case " << A.Name << ":\n";
2575

2576
    if (SuperClasses.size() == 1) {
2577
      OS << "    return B == " << SuperClasses.back() << ";\n";
2578
      continue;
2579
    }
2580

2581
    if (!SuperClasses.empty()) {
2582
      OS << "    switch (B) {\n";
2583
      OS << "    default: return false;\n";
2584
      for (StringRef SC : SuperClasses)
2585
        OS << "    case " << SC << ": return true;\n";
2586
      OS << "    }\n";
2587
    } else {
2588
      // No case statement to emit
2589
      OS << "    return false;\n";
2590
    }
2591
  }
2592

2593
  // If there were case statements emitted into the string stream write the
2594
  // default.
2595
  if (EmittedSwitch)
2596
    OS << "  }\n";
2597
  else
2598
    OS << "  return false;\n";
2599

2600
  OS << "}\n\n";
2601
}
2602

2603
/// emitMatchTokenString - Emit the function to match a token string to the
2604
/// appropriate match class value.
2605
static void emitMatchTokenString(CodeGenTarget &Target,
2606
                                 std::forward_list<ClassInfo> &Infos,
2607
                                 raw_ostream &OS) {
2608
  // Construct the match list.
2609
  std::vector<StringMatcher::StringPair> Matches;
2610
  for (const auto &CI : Infos) {
2611
    if (CI.Kind == ClassInfo::Token)
2612
      Matches.emplace_back(CI.ValueName, "return " + CI.Name + ";");
2613
  }
2614

2615
  OS << "static MatchClassKind matchTokenString(StringRef Name) {\n";
2616

2617
  StringMatcher("Name", Matches, OS).Emit();
2618

2619
  OS << "  return InvalidMatchClass;\n";
2620
  OS << "}\n\n";
2621
}
2622

2623
/// emitMatchRegisterName - Emit the function to match a string to the target
2624
/// specific register enum.
2625
static void emitMatchRegisterName(CodeGenTarget &Target, Record *AsmParser,
2626
                                  raw_ostream &OS) {
2627
  // Construct the match list.
2628
  std::vector<StringMatcher::StringPair> Matches;
2629
  const auto &Regs = Target.getRegBank().getRegisters();
2630
  std::string Namespace =
2631
      Regs.front().TheDef->getValueAsString("Namespace").str();
2632
  for (const CodeGenRegister &Reg : Regs) {
2633
    StringRef AsmName = Reg.TheDef->getValueAsString("AsmName");
2634
    if (AsmName.empty())
2635
      continue;
2636

2637
    Matches.emplace_back(AsmName.str(), "return " + Namespace +
2638
                                            "::" + Reg.getName().str() + ';');
2639
  }
2640

2641
  OS << "static MCRegister MatchRegisterName(StringRef Name) {\n";
2642

2643
  bool IgnoreDuplicates =
2644
      AsmParser->getValueAsBit("AllowDuplicateRegisterNames");
2645
  StringMatcher("Name", Matches, OS).Emit(0, IgnoreDuplicates);
2646

2647
  OS << "  return " << Namespace << "::NoRegister;\n";
2648
  OS << "}\n\n";
2649
}
2650

2651
/// Emit the function to match a string to the target
2652
/// specific register enum.
2653
static void emitMatchRegisterAltName(CodeGenTarget &Target, Record *AsmParser,
2654
                                     raw_ostream &OS) {
2655
  // Construct the match list.
2656
  std::vector<StringMatcher::StringPair> Matches;
2657
  const auto &Regs = Target.getRegBank().getRegisters();
2658
  std::string Namespace =
2659
      Regs.front().TheDef->getValueAsString("Namespace").str();
2660
  for (const CodeGenRegister &Reg : Regs) {
2661

2662
    auto AltNames = Reg.TheDef->getValueAsListOfStrings("AltNames");
2663

2664
    for (auto AltName : AltNames) {
2665
      AltName = StringRef(AltName).trim();
2666

2667
      // don't handle empty alternative names
2668
      if (AltName.empty())
2669
        continue;
2670

2671
      Matches.emplace_back(AltName.str(), "return " + Namespace +
2672
                                              "::" + Reg.getName().str() + ';');
2673
    }
2674
  }
2675

2676
  OS << "static MCRegister MatchRegisterAltName(StringRef Name) {\n";
2677

2678
  bool IgnoreDuplicates =
2679
      AsmParser->getValueAsBit("AllowDuplicateRegisterNames");
2680
  StringMatcher("Name", Matches, OS).Emit(0, IgnoreDuplicates);
2681

2682
  OS << "  return " << Namespace << "::NoRegister;\n";
2683
  OS << "}\n\n";
2684
}
2685

2686
/// emitOperandDiagnosticTypes - Emit the operand matching diagnostic types.
2687
static void emitOperandDiagnosticTypes(AsmMatcherInfo &Info, raw_ostream &OS) {
2688
  // Get the set of diagnostic types from all of the operand classes.
2689
  std::set<StringRef> Types;
2690
  for (const auto &OpClassEntry : Info.AsmOperandClasses) {
2691
    if (!OpClassEntry.second->DiagnosticType.empty())
2692
      Types.insert(OpClassEntry.second->DiagnosticType);
2693
  }
2694
  for (const auto &OpClassEntry : Info.RegisterClassClasses) {
2695
    if (!OpClassEntry.second->DiagnosticType.empty())
2696
      Types.insert(OpClassEntry.second->DiagnosticType);
2697
  }
2698

2699
  if (Types.empty())
2700
    return;
2701

2702
  // Now emit the enum entries.
2703
  for (StringRef Type : Types)
2704
    OS << "  Match_" << Type << ",\n";
2705
  OS << "  END_OPERAND_DIAGNOSTIC_TYPES\n";
2706
}
2707

2708
/// emitGetSubtargetFeatureName - Emit the helper function to get the
2709
/// user-level name for a subtarget feature.
2710
static void emitGetSubtargetFeatureName(AsmMatcherInfo &Info, raw_ostream &OS) {
2711
  OS << "// User-level names for subtarget features that participate in\n"
2712
     << "// instruction matching.\n"
2713
     << "static const char *getSubtargetFeatureName(uint64_t Val) {\n";
2714
  if (!Info.SubtargetFeatures.empty()) {
2715
    OS << "  switch(Val) {\n";
2716
    for (const auto &SF : Info.SubtargetFeatures) {
2717
      const SubtargetFeatureInfo &SFI = SF.second;
2718
      // FIXME: Totally just a placeholder name to get the algorithm working.
2719
      OS << "  case " << SFI.getEnumBitName() << ": return \""
2720
         << SFI.TheDef->getValueAsString("PredicateName") << "\";\n";
2721
    }
2722
    OS << "  default: return \"(unknown)\";\n";
2723
    OS << "  }\n";
2724
  } else {
2725
    // Nothing to emit, so skip the switch
2726
    OS << "  return \"(unknown)\";\n";
2727
  }
2728
  OS << "}\n\n";
2729
}
2730

2731
static std::string GetAliasRequiredFeatures(Record *R,
2732
                                            const AsmMatcherInfo &Info) {
2733
  std::vector<Record *> ReqFeatures = R->getValueAsListOfDefs("Predicates");
2734
  std::string Result;
2735

2736
  if (ReqFeatures.empty())
2737
    return Result;
2738

2739
  for (unsigned i = 0, e = ReqFeatures.size(); i != e; ++i) {
2740
    const SubtargetFeatureInfo *F = Info.getSubtargetFeature(ReqFeatures[i]);
2741

2742
    if (!F)
2743
      PrintFatalError(R->getLoc(),
2744
                      "Predicate '" + ReqFeatures[i]->getName() +
2745
                          "' is not marked as an AssemblerPredicate!");
2746

2747
    if (i)
2748
      Result += " && ";
2749

2750
    Result += "Features.test(" + F->getEnumBitName() + ')';
2751
  }
2752

2753
  return Result;
2754
}
2755

2756
static void
2757
emitMnemonicAliasVariant(raw_ostream &OS, const AsmMatcherInfo &Info,
2758
                         std::vector<Record *> &Aliases, unsigned Indent = 0,
2759
                         StringRef AsmParserVariantName = StringRef()) {
2760
  // Keep track of all the aliases from a mnemonic.  Use an std::map so that the
2761
  // iteration order of the map is stable.
2762
  std::map<std::string, std::vector<Record *>> AliasesFromMnemonic;
2763

2764
  for (Record *R : Aliases) {
2765
    // FIXME: Allow AssemblerVariantName to be a comma separated list.
2766
    StringRef AsmVariantName = R->getValueAsString("AsmVariantName");
2767
    if (AsmVariantName != AsmParserVariantName)
2768
      continue;
2769
    AliasesFromMnemonic[R->getValueAsString("FromMnemonic").lower()].push_back(
2770
        R);
2771
  }
2772
  if (AliasesFromMnemonic.empty())
2773
    return;
2774

2775
  // Process each alias a "from" mnemonic at a time, building the code executed
2776
  // by the string remapper.
2777
  std::vector<StringMatcher::StringPair> Cases;
2778
  for (const auto &AliasEntry : AliasesFromMnemonic) {
2779
    const std::vector<Record *> &ToVec = AliasEntry.second;
2780

2781
    // Loop through each alias and emit code that handles each case.  If there
2782
    // are two instructions without predicates, emit an error.  If there is one,
2783
    // emit it last.
2784
    std::string MatchCode;
2785
    int AliasWithNoPredicate = -1;
2786

2787
    for (unsigned i = 0, e = ToVec.size(); i != e; ++i) {
2788
      Record *R = ToVec[i];
2789
      std::string FeatureMask = GetAliasRequiredFeatures(R, Info);
2790

2791
      // If this unconditionally matches, remember it for later and diagnose
2792
      // duplicates.
2793
      if (FeatureMask.empty()) {
2794
        if (AliasWithNoPredicate != -1 &&
2795
            R->getValueAsString("ToMnemonic") !=
2796
                ToVec[AliasWithNoPredicate]->getValueAsString("ToMnemonic")) {
2797
          // We can't have two different aliases from the same mnemonic with no
2798
          // predicate.
2799
          PrintError(
2800
              ToVec[AliasWithNoPredicate]->getLoc(),
2801
              "two different MnemonicAliases with the same 'from' mnemonic!");
2802
          PrintFatalError(R->getLoc(), "this is the other MnemonicAlias.");
2803
        }
2804

2805
        AliasWithNoPredicate = i;
2806
        continue;
2807
      }
2808
      if (R->getValueAsString("ToMnemonic") == AliasEntry.first)
2809
        PrintFatalError(R->getLoc(), "MnemonicAlias to the same string");
2810

2811
      if (!MatchCode.empty())
2812
        MatchCode += "else ";
2813
      MatchCode += "if (" + FeatureMask + ")\n";
2814
      MatchCode += "  Mnemonic = \"";
2815
      MatchCode += R->getValueAsString("ToMnemonic").lower();
2816
      MatchCode += "\";\n";
2817
    }
2818

2819
    if (AliasWithNoPredicate != -1) {
2820
      Record *R = ToVec[AliasWithNoPredicate];
2821
      if (!MatchCode.empty())
2822
        MatchCode += "else\n  ";
2823
      MatchCode += "Mnemonic = \"";
2824
      MatchCode += R->getValueAsString("ToMnemonic").lower();
2825
      MatchCode += "\";\n";
2826
    }
2827

2828
    MatchCode += "return;";
2829

2830
    Cases.push_back(std::pair(AliasEntry.first, MatchCode));
2831
  }
2832
  StringMatcher("Mnemonic", Cases, OS).Emit(Indent);
2833
}
2834

2835
/// emitMnemonicAliases - If the target has any MnemonicAlias<> definitions,
2836
/// emit a function for them and return true, otherwise return false.
2837
static bool emitMnemonicAliases(raw_ostream &OS, const AsmMatcherInfo &Info,
2838
                                CodeGenTarget &Target) {
2839
  // Ignore aliases when match-prefix is set.
2840
  if (!MatchPrefix.empty())
2841
    return false;
2842

2843
  std::vector<Record *> Aliases =
2844
      Info.getRecords().getAllDerivedDefinitions("MnemonicAlias");
2845
  if (Aliases.empty())
2846
    return false;
2847

2848
  OS << "static void applyMnemonicAliases(StringRef &Mnemonic, "
2849
        "const FeatureBitset &Features, unsigned VariantID) {\n";
2850
  OS << "  switch (VariantID) {\n";
2851
  unsigned VariantCount = Target.getAsmParserVariantCount();
2852
  for (unsigned VC = 0; VC != VariantCount; ++VC) {
2853
    Record *AsmVariant = Target.getAsmParserVariant(VC);
2854
    int AsmParserVariantNo = AsmVariant->getValueAsInt("Variant");
2855
    StringRef AsmParserVariantName = AsmVariant->getValueAsString("Name");
2856
    OS << "  case " << AsmParserVariantNo << ":\n";
2857
    emitMnemonicAliasVariant(OS, Info, Aliases, /*Indent=*/2,
2858
                             AsmParserVariantName);
2859
    OS << "    break;\n";
2860
  }
2861
  OS << "  }\n";
2862

2863
  // Emit aliases that apply to all variants.
2864
  emitMnemonicAliasVariant(OS, Info, Aliases);
2865

2866
  OS << "}\n\n";
2867

2868
  return true;
2869
}
2870

2871
static void
2872
emitCustomOperandParsing(raw_ostream &OS, CodeGenTarget &Target,
2873
                         const AsmMatcherInfo &Info, StringRef ClassName,
2874
                         StringToOffsetTable &StringTable,
2875
                         unsigned MaxMnemonicIndex, unsigned MaxFeaturesIndex,
2876
                         bool HasMnemonicFirst, const Record &AsmParser) {
2877
  unsigned MaxMask = 0;
2878
  for (const OperandMatchEntry &OMI : Info.OperandMatchInfo) {
2879
    MaxMask |= OMI.OperandMask;
2880
  }
2881

2882
  // Emit the static custom operand parsing table;
2883
  OS << "namespace {\n";
2884
  OS << "  struct OperandMatchEntry {\n";
2885
  OS << "    " << getMinimalTypeForRange(MaxMnemonicIndex) << " Mnemonic;\n";
2886
  OS << "    " << getMinimalTypeForRange(MaxMask) << " OperandMask;\n";
2887
  OS << "    "
2888
     << getMinimalTypeForRange(
2889
            std::distance(Info.Classes.begin(), Info.Classes.end()) +
2890
            2 /* Include 'InvalidMatchClass' and 'OptionalMatchClass' */)
2891
     << " Class;\n";
2892
  OS << "    " << getMinimalTypeForRange(MaxFeaturesIndex)
2893
     << " RequiredFeaturesIdx;\n\n";
2894
  OS << "    StringRef getMnemonic() const {\n";
2895
  OS << "      return StringRef(MnemonicTable + Mnemonic + 1,\n";
2896
  OS << "                       MnemonicTable[Mnemonic]);\n";
2897
  OS << "    }\n";
2898
  OS << "  };\n\n";
2899

2900
  OS << "  // Predicate for searching for an opcode.\n";
2901
  OS << "  struct LessOpcodeOperand {\n";
2902
  OS << "    bool operator()(const OperandMatchEntry &LHS, StringRef RHS) {\n";
2903
  OS << "      return LHS.getMnemonic()  < RHS;\n";
2904
  OS << "    }\n";
2905
  OS << "    bool operator()(StringRef LHS, const OperandMatchEntry &RHS) {\n";
2906
  OS << "      return LHS < RHS.getMnemonic();\n";
2907
  OS << "    }\n";
2908
  OS << "    bool operator()(const OperandMatchEntry &LHS,";
2909
  OS << " const OperandMatchEntry &RHS) {\n";
2910
  OS << "      return LHS.getMnemonic() < RHS.getMnemonic();\n";
2911
  OS << "    }\n";
2912
  OS << "  };\n";
2913

2914
  OS << "} // end anonymous namespace\n\n";
2915

2916
  OS << "static const OperandMatchEntry OperandMatchTable["
2917
     << Info.OperandMatchInfo.size() << "] = {\n";
2918

2919
  OS << "  /* Operand List Mnemonic, Mask, Operand Class, Features */\n";
2920
  for (const OperandMatchEntry &OMI : Info.OperandMatchInfo) {
2921
    const MatchableInfo &II = *OMI.MI;
2922

2923
    OS << "  { ";
2924

2925
    // Store a pascal-style length byte in the mnemonic.
2926
    std::string LenMnemonic = char(II.Mnemonic.size()) + II.Mnemonic.lower();
2927
    OS << StringTable.GetOrAddStringOffset(LenMnemonic, false) << " /* "
2928
       << II.Mnemonic << " */, ";
2929

2930
    OS << OMI.OperandMask;
2931
    OS << " /* ";
2932
    ListSeparator LS;
2933
    for (int i = 0, e = 31; i != e; ++i)
2934
      if (OMI.OperandMask & (1 << i))
2935
        OS << LS << i;
2936
    OS << " */, ";
2937

2938
    OS << OMI.CI->Name;
2939

2940
    // Write the required features mask.
2941
    OS << ", AMFBS";
2942
    if (II.RequiredFeatures.empty())
2943
      OS << "_None";
2944
    else
2945
      for (unsigned i = 0, e = II.RequiredFeatures.size(); i != e; ++i)
2946
        OS << '_' << II.RequiredFeatures[i]->TheDef->getName();
2947

2948
    OS << " },\n";
2949
  }
2950
  OS << "};\n\n";
2951

2952
  // Emit the operand class switch to call the correct custom parser for
2953
  // the found operand class.
2954
  OS << "ParseStatus " << Target.getName() << ClassName << "::\n"
2955
     << "tryCustomParseOperand(OperandVector"
2956
     << " &Operands,\n                      unsigned MCK) {\n\n"
2957
     << "  switch(MCK) {\n";
2958

2959
  for (const auto &CI : Info.Classes) {
2960
    if (CI.ParserMethod.empty())
2961
      continue;
2962
    OS << "  case " << CI.Name << ":\n"
2963
       << "    return " << CI.ParserMethod << "(Operands);\n";
2964
  }
2965

2966
  OS << "  default:\n";
2967
  OS << "    return ParseStatus::NoMatch;\n";
2968
  OS << "  }\n";
2969
  OS << "  return ParseStatus::NoMatch;\n";
2970
  OS << "}\n\n";
2971

2972
  // Emit the static custom operand parser. This code is very similar with
2973
  // the other matcher. Also use MatchResultTy here just in case we go for
2974
  // a better error handling.
2975
  OS << "ParseStatus " << Target.getName() << ClassName << "::\n"
2976
     << "MatchOperandParserImpl(OperandVector"
2977
     << " &Operands,\n                       StringRef Mnemonic,\n"
2978
     << "                       bool ParseForAllFeatures) {\n";
2979

2980
  // Emit code to get the available features.
2981
  OS << "  // Get the current feature set.\n";
2982
  OS << "  const FeatureBitset &AvailableFeatures = "
2983
        "getAvailableFeatures();\n\n";
2984

2985
  OS << "  // Get the next operand index.\n";
2986
  OS << "  unsigned NextOpNum = Operands.size()"
2987
     << (HasMnemonicFirst ? " - 1" : "") << ";\n";
2988

2989
  // Emit code to search the table.
2990
  OS << "  // Search the table.\n";
2991
  if (HasMnemonicFirst) {
2992
    OS << "  auto MnemonicRange =\n";
2993
    OS << "    std::equal_range(std::begin(OperandMatchTable), "
2994
          "std::end(OperandMatchTable),\n";
2995
    OS << "                     Mnemonic, LessOpcodeOperand());\n\n";
2996
  } else {
2997
    OS << "  auto MnemonicRange = std::pair(std::begin(OperandMatchTable),"
2998
          " std::end(OperandMatchTable));\n";
2999
    OS << "  if (!Mnemonic.empty())\n";
3000
    OS << "    MnemonicRange =\n";
3001
    OS << "      std::equal_range(std::begin(OperandMatchTable), "
3002
          "std::end(OperandMatchTable),\n";
3003
    OS << "                       Mnemonic, LessOpcodeOperand());\n\n";
3004
  }
3005

3006
  OS << "  if (MnemonicRange.first == MnemonicRange.second)\n";
3007
  OS << "    return ParseStatus::NoMatch;\n\n";
3008

3009
  OS << "  for (const OperandMatchEntry *it = MnemonicRange.first,\n"
3010
     << "       *ie = MnemonicRange.second; it != ie; ++it) {\n";
3011

3012
  OS << "    // equal_range guarantees that instruction mnemonic matches.\n";
3013
  OS << "    assert(Mnemonic == it->getMnemonic());\n\n";
3014

3015
  // Emit check that the required features are available.
3016
  OS << "    // check if the available features match\n";
3017
  OS << "    const FeatureBitset &RequiredFeatures = "
3018
        "FeatureBitsets[it->RequiredFeaturesIdx];\n";
3019
  OS << "    if (!ParseForAllFeatures && (AvailableFeatures & "
3020
        "RequiredFeatures) != RequiredFeatures)\n";
3021
  OS << "      continue;\n\n";
3022

3023
  // Emit check to ensure the operand number matches.
3024
  OS << "    // check if the operand in question has a custom parser.\n";
3025
  OS << "    if (!(it->OperandMask & (1 << NextOpNum)))\n";
3026
  OS << "      continue;\n\n";
3027

3028
  // Emit call to the custom parser method
3029
  StringRef ParserName = AsmParser.getValueAsString("OperandParserMethod");
3030
  if (ParserName.empty())
3031
    ParserName = "tryCustomParseOperand";
3032
  OS << "    // call custom parse method to handle the operand\n";
3033
  OS << "    ParseStatus Result = " << ParserName << "(Operands, it->Class);\n";
3034
  OS << "    if (!Result.isNoMatch())\n";
3035
  OS << "      return Result;\n";
3036
  OS << "  }\n\n";
3037

3038
  OS << "  // Okay, we had no match.\n";
3039
  OS << "  return ParseStatus::NoMatch;\n";
3040
  OS << "}\n\n";
3041
}
3042

3043
static void emitAsmTiedOperandConstraints(CodeGenTarget &Target,
3044
                                          AsmMatcherInfo &Info, raw_ostream &OS,
3045
                                          bool HasOptionalOperands) {
3046
  std::string AsmParserName =
3047
      std::string(Info.AsmParser->getValueAsString("AsmParserClassName"));
3048
  OS << "static bool ";
3049
  OS << "checkAsmTiedOperandConstraints(const " << Target.getName()
3050
     << AsmParserName << "&AsmParser,\n";
3051
  OS << "                               unsigned Kind, const OperandVector "
3052
        "&Operands,\n";
3053
  if (HasOptionalOperands)
3054
    OS << "                               ArrayRef<unsigned> DefaultsOffset,\n";
3055
  OS << "                               uint64_t &ErrorInfo) {\n";
3056
  OS << "  assert(Kind < CVT_NUM_SIGNATURES && \"Invalid signature!\");\n";
3057
  OS << "  const uint8_t *Converter = ConversionTable[Kind];\n";
3058
  OS << "  for (const uint8_t *p = Converter; *p; p += 2) {\n";
3059
  OS << "    switch (*p) {\n";
3060
  OS << "    case CVT_Tied: {\n";
3061
  OS << "      unsigned OpIdx = *(p + 1);\n";
3062
  OS << "      assert(OpIdx < (size_t)(std::end(TiedAsmOperandTable) -\n";
3063
  OS << "                              std::begin(TiedAsmOperandTable)) &&\n";
3064
  OS << "             \"Tied operand not found\");\n";
3065
  OS << "      unsigned OpndNum1 = TiedAsmOperandTable[OpIdx][1];\n";
3066
  OS << "      unsigned OpndNum2 = TiedAsmOperandTable[OpIdx][2];\n";
3067
  if (HasOptionalOperands) {
3068
    // When optional operands are involved, formal and actual operand indices
3069
    // may differ. Map the former to the latter by subtracting the number of
3070
    // absent optional operands.
3071
    OS << "      OpndNum1 = OpndNum1 - DefaultsOffset[OpndNum1];\n";
3072
    OS << "      OpndNum2 = OpndNum2 - DefaultsOffset[OpndNum2];\n";
3073
  }
3074
  OS << "      if (OpndNum1 != OpndNum2) {\n";
3075
  OS << "        auto &SrcOp1 = Operands[OpndNum1];\n";
3076
  OS << "        auto &SrcOp2 = Operands[OpndNum2];\n";
3077
  OS << "        if (!AsmParser.areEqualRegs(*SrcOp1, *SrcOp2)) {\n";
3078
  OS << "          ErrorInfo = OpndNum2;\n";
3079
  OS << "          return false;\n";
3080
  OS << "        }\n";
3081
  OS << "      }\n";
3082
  OS << "      break;\n";
3083
  OS << "    }\n";
3084
  OS << "    default:\n";
3085
  OS << "      break;\n";
3086
  OS << "    }\n";
3087
  OS << "  }\n";
3088
  OS << "  return true;\n";
3089
  OS << "}\n\n";
3090
}
3091

3092
static void emitMnemonicSpellChecker(raw_ostream &OS, CodeGenTarget &Target,
3093
                                     unsigned VariantCount) {
3094
  OS << "static std::string " << Target.getName()
3095
     << "MnemonicSpellCheck(StringRef S, const FeatureBitset &FBS,"
3096
     << " unsigned VariantID) {\n";
3097
  if (!VariantCount)
3098
    OS << "  return \"\";";
3099
  else {
3100
    OS << "  const unsigned MaxEditDist = 2;\n";
3101
    OS << "  std::vector<StringRef> Candidates;\n";
3102
    OS << "  StringRef Prev = \"\";\n\n";
3103

3104
    OS << "  // Find the appropriate table for this asm variant.\n";
3105
    OS << "  const MatchEntry *Start, *End;\n";
3106
    OS << "  switch (VariantID) {\n";
3107
    OS << "  default: llvm_unreachable(\"invalid variant!\");\n";
3108
    for (unsigned VC = 0; VC != VariantCount; ++VC) {
3109
      Record *AsmVariant = Target.getAsmParserVariant(VC);
3110
      int AsmVariantNo = AsmVariant->getValueAsInt("Variant");
3111
      OS << "  case " << AsmVariantNo << ": Start = std::begin(MatchTable" << VC
3112
         << "); End = std::end(MatchTable" << VC << "); break;\n";
3113
    }
3114
    OS << "  }\n\n";
3115
    OS << "  for (auto I = Start; I < End; I++) {\n";
3116
    OS << "    // Ignore unsupported instructions.\n";
3117
    OS << "    const FeatureBitset &RequiredFeatures = "
3118
          "FeatureBitsets[I->RequiredFeaturesIdx];\n";
3119
    OS << "    if ((FBS & RequiredFeatures) != RequiredFeatures)\n";
3120
    OS << "      continue;\n";
3121
    OS << "\n";
3122
    OS << "    StringRef T = I->getMnemonic();\n";
3123
    OS << "    // Avoid recomputing the edit distance for the same string.\n";
3124
    OS << "    if (T == Prev)\n";
3125
    OS << "      continue;\n";
3126
    OS << "\n";
3127
    OS << "    Prev = T;\n";
3128
    OS << "    unsigned Dist = S.edit_distance(T, false, MaxEditDist);\n";
3129
    OS << "    if (Dist <= MaxEditDist)\n";
3130
    OS << "      Candidates.push_back(T);\n";
3131
    OS << "  }\n";
3132
    OS << "\n";
3133
    OS << "  if (Candidates.empty())\n";
3134
    OS << "    return \"\";\n";
3135
    OS << "\n";
3136
    OS << "  std::string Res = \", did you mean: \";\n";
3137
    OS << "  unsigned i = 0;\n";
3138
    OS << "  for (; i < Candidates.size() - 1; i++)\n";
3139
    OS << "    Res += Candidates[i].str() + \", \";\n";
3140
    OS << "  return Res + Candidates[i].str() + \"?\";\n";
3141
  }
3142
  OS << "}\n";
3143
  OS << "\n";
3144
}
3145

3146
static void emitMnemonicChecker(raw_ostream &OS, CodeGenTarget &Target,
3147
                                unsigned VariantCount, bool HasMnemonicFirst,
3148
                                bool HasMnemonicAliases) {
3149
  OS << "static bool " << Target.getName()
3150
     << "CheckMnemonic(StringRef Mnemonic,\n";
3151
  OS << "                                "
3152
     << "const FeatureBitset &AvailableFeatures,\n";
3153
  OS << "                                "
3154
     << "unsigned VariantID) {\n";
3155

3156
  if (!VariantCount) {
3157
    OS << "  return false;\n";
3158
  } else {
3159
    if (HasMnemonicAliases) {
3160
      OS << "  // Process all MnemonicAliases to remap the mnemonic.\n";
3161
      OS << "  applyMnemonicAliases(Mnemonic, AvailableFeatures, VariantID);";
3162
      OS << "\n\n";
3163
    }
3164
    OS << "  // Find the appropriate table for this asm variant.\n";
3165
    OS << "  const MatchEntry *Start, *End;\n";
3166
    OS << "  switch (VariantID) {\n";
3167
    OS << "  default: llvm_unreachable(\"invalid variant!\");\n";
3168
    for (unsigned VC = 0; VC != VariantCount; ++VC) {
3169
      Record *AsmVariant = Target.getAsmParserVariant(VC);
3170
      int AsmVariantNo = AsmVariant->getValueAsInt("Variant");
3171
      OS << "  case " << AsmVariantNo << ": Start = std::begin(MatchTable" << VC
3172
         << "); End = std::end(MatchTable" << VC << "); break;\n";
3173
    }
3174
    OS << "  }\n\n";
3175

3176
    OS << "  // Search the table.\n";
3177
    if (HasMnemonicFirst) {
3178
      OS << "  auto MnemonicRange = "
3179
            "std::equal_range(Start, End, Mnemonic, LessOpcode());\n\n";
3180
    } else {
3181
      OS << "  auto MnemonicRange = std::pair(Start, End);\n";
3182
      OS << "  unsigned SIndex = Mnemonic.empty() ? 0 : 1;\n";
3183
      OS << "  if (!Mnemonic.empty())\n";
3184
      OS << "    MnemonicRange = "
3185
         << "std::equal_range(Start, End, Mnemonic.lower(), LessOpcode());\n\n";
3186
    }
3187

3188
    OS << "  if (MnemonicRange.first == MnemonicRange.second)\n";
3189
    OS << "    return false;\n\n";
3190

3191
    OS << "  for (const MatchEntry *it = MnemonicRange.first, "
3192
       << "*ie = MnemonicRange.second;\n";
3193
    OS << "       it != ie; ++it) {\n";
3194
    OS << "    const FeatureBitset &RequiredFeatures =\n";
3195
    OS << "      FeatureBitsets[it->RequiredFeaturesIdx];\n";
3196
    OS << "    if ((AvailableFeatures & RequiredFeatures) == ";
3197
    OS << "RequiredFeatures)\n";
3198
    OS << "      return true;\n";
3199
    OS << "  }\n";
3200
    OS << "  return false;\n";
3201
  }
3202
  OS << "}\n";
3203
  OS << "\n";
3204
}
3205

3206
// Emit a function mapping match classes to strings, for debugging.
3207
static void emitMatchClassKindNames(std::forward_list<ClassInfo> &Infos,
3208
                                    raw_ostream &OS) {
3209
  OS << "#ifndef NDEBUG\n";
3210
  OS << "const char *getMatchClassName(MatchClassKind Kind) {\n";
3211
  OS << "  switch (Kind) {\n";
3212

3213
  OS << "  case InvalidMatchClass: return \"InvalidMatchClass\";\n";
3214
  OS << "  case OptionalMatchClass: return \"OptionalMatchClass\";\n";
3215
  for (const auto &CI : Infos) {
3216
    OS << "  case " << CI.Name << ": return \"" << CI.Name << "\";\n";
3217
  }
3218
  OS << "  case NumMatchClassKinds: return \"NumMatchClassKinds\";\n";
3219

3220
  OS << "  }\n";
3221
  OS << "  llvm_unreachable(\"unhandled MatchClassKind!\");\n";
3222
  OS << "}\n\n";
3223
  OS << "#endif // NDEBUG\n";
3224
}
3225

3226
static std::string
3227
getNameForFeatureBitset(const std::vector<Record *> &FeatureBitset) {
3228
  std::string Name = "AMFBS";
3229
  for (const auto &Feature : FeatureBitset)
3230
    Name += ("_" + Feature->getName()).str();
3231
  return Name;
3232
}
3233

3234
void AsmMatcherEmitter::run(raw_ostream &OS) {
3235
  CodeGenTarget Target(Records);
3236
  Record *AsmParser = Target.getAsmParser();
3237
  StringRef ClassName = AsmParser->getValueAsString("AsmParserClassName");
3238

3239
  emitSourceFileHeader("Assembly Matcher Source Fragment", OS, Records);
3240

3241
  // Compute the information on the instructions to match.
3242
  AsmMatcherInfo Info(AsmParser, Target, Records);
3243
  Info.buildInfo();
3244

3245
  bool PreferSmallerInstructions = getPreferSmallerInstructions(Target);
3246
  // Sort the instruction table using the partial order on classes. We use
3247
  // stable_sort to ensure that ambiguous instructions are still
3248
  // deterministically ordered.
3249
  llvm::stable_sort(
3250
      Info.Matchables,
3251
      [PreferSmallerInstructions](const std::unique_ptr<MatchableInfo> &A,
3252
                                  const std::unique_ptr<MatchableInfo> &B) {
3253
        return A->shouldBeMatchedBefore(*B, PreferSmallerInstructions);
3254
      });
3255

3256
#ifdef EXPENSIVE_CHECKS
3257
  // Verify that the table is sorted and operator < works transitively.
3258
  for (auto I = Info.Matchables.begin(), E = Info.Matchables.end(); I != E;
3259
       ++I) {
3260
    for (auto J = I; J != E; ++J) {
3261
      assert(!(*J)->shouldBeMatchedBefore(**I, PreferSmallerInstructions));
3262
    }
3263
  }
3264
#endif
3265

3266
  DEBUG_WITH_TYPE("instruction_info", {
3267
    for (const auto &MI : Info.Matchables)
3268
      MI->dump();
3269
  });
3270

3271
  // Check for ambiguous matchables.
3272
  DEBUG_WITH_TYPE("ambiguous_instrs", {
3273
    unsigned NumAmbiguous = 0;
3274
    for (auto I = Info.Matchables.begin(), E = Info.Matchables.end(); I != E;
3275
         ++I) {
3276
      for (auto J = std::next(I); J != E; ++J) {
3277
        const MatchableInfo &A = **I;
3278
        const MatchableInfo &B = **J;
3279

3280
        if (A.couldMatchAmbiguouslyWith(B, PreferSmallerInstructions)) {
3281
          errs() << "warning: ambiguous matchables:\n";
3282
          A.dump();
3283
          errs() << "\nis incomparable with:\n";
3284
          B.dump();
3285
          errs() << "\n\n";
3286
          ++NumAmbiguous;
3287
        }
3288
      }
3289
    }
3290
    if (NumAmbiguous)
3291
      errs() << "warning: " << NumAmbiguous << " ambiguous matchables!\n";
3292
  });
3293

3294
  // Compute the information on the custom operand parsing.
3295
  Info.buildOperandMatchInfo();
3296

3297
  bool HasMnemonicFirst = AsmParser->getValueAsBit("HasMnemonicFirst");
3298
  bool HasOptionalOperands = Info.hasOptionalOperands();
3299
  bool ReportMultipleNearMisses =
3300
      AsmParser->getValueAsBit("ReportMultipleNearMisses");
3301

3302
  // Write the output.
3303

3304
  // Information for the class declaration.
3305
  OS << "\n#ifdef GET_ASSEMBLER_HEADER\n";
3306
  OS << "#undef GET_ASSEMBLER_HEADER\n";
3307
  OS << "  // This should be included into the middle of the declaration of\n";
3308
  OS << "  // your subclasses implementation of MCTargetAsmParser.\n";
3309
  OS << "  FeatureBitset ComputeAvailableFeatures(const FeatureBitset &FB) "
3310
        "const;\n";
3311
  if (HasOptionalOperands) {
3312
    OS << "  void convertToMCInst(unsigned Kind, MCInst &Inst, "
3313
       << "unsigned Opcode,\n"
3314
       << "                       const OperandVector &Operands,\n"
3315
       << "                       const SmallBitVector "
3316
          "&OptionalOperandsMask,\n"
3317
       << "                       ArrayRef<unsigned> DefaultsOffset);\n";
3318
  } else {
3319
    OS << "  void convertToMCInst(unsigned Kind, MCInst &Inst, "
3320
       << "unsigned Opcode,\n"
3321
       << "                       const OperandVector &Operands);\n";
3322
  }
3323
  OS << "  void convertToMapAndConstraints(unsigned Kind,\n                ";
3324
  OS << "           const OperandVector &Operands) override;\n";
3325
  OS << "  unsigned MatchInstructionImpl(const OperandVector &Operands,\n"
3326
     << "                                MCInst &Inst,\n";
3327
  if (ReportMultipleNearMisses)
3328
    OS << "                                SmallVectorImpl<NearMissInfo> "
3329
          "*NearMisses,\n";
3330
  else
3331
    OS << "                                uint64_t &ErrorInfo,\n"
3332
       << "                                FeatureBitset &MissingFeatures,\n";
3333
  OS << "                                bool matchingInlineAsm,\n"
3334
     << "                                unsigned VariantID = 0);\n";
3335
  if (!ReportMultipleNearMisses)
3336
    OS << "  unsigned MatchInstructionImpl(const OperandVector &Operands,\n"
3337
       << "                                MCInst &Inst,\n"
3338
       << "                                uint64_t &ErrorInfo,\n"
3339
       << "                                bool matchingInlineAsm,\n"
3340
       << "                                unsigned VariantID = 0) {\n"
3341
       << "    FeatureBitset MissingFeatures;\n"
3342
       << "    return MatchInstructionImpl(Operands, Inst, ErrorInfo, "
3343
          "MissingFeatures,\n"
3344
       << "                                matchingInlineAsm, VariantID);\n"
3345
       << "  }\n\n";
3346

3347
  if (!Info.OperandMatchInfo.empty()) {
3348
    OS << "  ParseStatus MatchOperandParserImpl(\n";
3349
    OS << "    OperandVector &Operands,\n";
3350
    OS << "    StringRef Mnemonic,\n";
3351
    OS << "    bool ParseForAllFeatures = false);\n";
3352

3353
    OS << "  ParseStatus tryCustomParseOperand(\n";
3354
    OS << "    OperandVector &Operands,\n";
3355
    OS << "    unsigned MCK);\n\n";
3356
  }
3357

3358
  OS << "#endif // GET_ASSEMBLER_HEADER\n\n";
3359

3360
  // Emit the operand match diagnostic enum names.
3361
  OS << "\n#ifdef GET_OPERAND_DIAGNOSTIC_TYPES\n";
3362
  OS << "#undef GET_OPERAND_DIAGNOSTIC_TYPES\n\n";
3363
  emitOperandDiagnosticTypes(Info, OS);
3364
  OS << "#endif // GET_OPERAND_DIAGNOSTIC_TYPES\n\n";
3365

3366
  OS << "\n#ifdef GET_REGISTER_MATCHER\n";
3367
  OS << "#undef GET_REGISTER_MATCHER\n\n";
3368

3369
  // Emit the subtarget feature enumeration.
3370
  SubtargetFeatureInfo::emitSubtargetFeatureBitEnumeration(
3371
      Info.SubtargetFeatures, OS);
3372

3373
  // Emit the function to match a register name to number.
3374
  // This should be omitted for Mips target
3375
  if (AsmParser->getValueAsBit("ShouldEmitMatchRegisterName"))
3376
    emitMatchRegisterName(Target, AsmParser, OS);
3377

3378
  if (AsmParser->getValueAsBit("ShouldEmitMatchRegisterAltName"))
3379
    emitMatchRegisterAltName(Target, AsmParser, OS);
3380

3381
  OS << "#endif // GET_REGISTER_MATCHER\n\n";
3382

3383
  OS << "\n#ifdef GET_SUBTARGET_FEATURE_NAME\n";
3384
  OS << "#undef GET_SUBTARGET_FEATURE_NAME\n\n";
3385

3386
  // Generate the helper function to get the names for subtarget features.
3387
  emitGetSubtargetFeatureName(Info, OS);
3388

3389
  OS << "#endif // GET_SUBTARGET_FEATURE_NAME\n\n";
3390

3391
  OS << "\n#ifdef GET_MATCHER_IMPLEMENTATION\n";
3392
  OS << "#undef GET_MATCHER_IMPLEMENTATION\n\n";
3393

3394
  // Generate the function that remaps for mnemonic aliases.
3395
  bool HasMnemonicAliases = emitMnemonicAliases(OS, Info, Target);
3396

3397
  // Generate the convertToMCInst function to convert operands into an MCInst.
3398
  // Also, generate the convertToMapAndConstraints function for MS-style inline
3399
  // assembly.  The latter doesn't actually generate a MCInst.
3400
  unsigned NumConverters =
3401
      emitConvertFuncs(Target, ClassName, Info.Matchables, HasMnemonicFirst,
3402
                       HasOptionalOperands, OS);
3403

3404
  // Emit the enumeration for classes which participate in matching.
3405
  emitMatchClassEnumeration(Target, Info.Classes, OS);
3406

3407
  // Emit a function to get the user-visible string to describe an operand
3408
  // match failure in diagnostics.
3409
  emitOperandMatchErrorDiagStrings(Info, OS);
3410

3411
  // Emit a function to map register classes to operand match failure codes.
3412
  emitRegisterMatchErrorFunc(Info, OS);
3413

3414
  // Emit the routine to match token strings to their match class.
3415
  emitMatchTokenString(Target, Info.Classes, OS);
3416

3417
  // Emit the subclass predicate routine.
3418
  emitIsSubclass(Target, Info.Classes, OS);
3419

3420
  // Emit the routine to validate an operand against a match class.
3421
  emitValidateOperandClass(Info, OS);
3422

3423
  emitMatchClassKindNames(Info.Classes, OS);
3424

3425
  // Emit the available features compute function.
3426
  SubtargetFeatureInfo::emitComputeAssemblerAvailableFeatures(
3427
      Info.Target.getName(), ClassName, "ComputeAvailableFeatures",
3428
      Info.SubtargetFeatures, OS);
3429

3430
  if (!ReportMultipleNearMisses)
3431
    emitAsmTiedOperandConstraints(Target, Info, OS, HasOptionalOperands);
3432

3433
  StringToOffsetTable StringTable;
3434

3435
  size_t MaxNumOperands = 0;
3436
  unsigned MaxMnemonicIndex = 0;
3437
  bool HasDeprecation = false;
3438
  for (const auto &MI : Info.Matchables) {
3439
    MaxNumOperands = std::max(MaxNumOperands, MI->AsmOperands.size());
3440
    HasDeprecation |= MI->HasDeprecation;
3441

3442
    // Store a pascal-style length byte in the mnemonic.
3443
    std::string LenMnemonic = char(MI->Mnemonic.size()) + MI->Mnemonic.lower();
3444
    MaxMnemonicIndex = std::max(
3445
        MaxMnemonicIndex, StringTable.GetOrAddStringOffset(LenMnemonic, false));
3446
  }
3447

3448
  OS << "static const char MnemonicTable[] =\n";
3449
  StringTable.EmitString(OS);
3450
  OS << ";\n\n";
3451

3452
  std::vector<std::vector<Record *>> FeatureBitsets;
3453
  for (const auto &MI : Info.Matchables) {
3454
    if (MI->RequiredFeatures.empty())
3455
      continue;
3456
    FeatureBitsets.emplace_back();
3457
    for (unsigned I = 0, E = MI->RequiredFeatures.size(); I != E; ++I)
3458
      FeatureBitsets.back().push_back(MI->RequiredFeatures[I]->TheDef);
3459
  }
3460

3461
  llvm::sort(FeatureBitsets, [&](const std::vector<Record *> &A,
3462
                                 const std::vector<Record *> &B) {
3463
    if (A.size() < B.size())
3464
      return true;
3465
    if (A.size() > B.size())
3466
      return false;
3467
    for (auto Pair : zip(A, B)) {
3468
      if (std::get<0>(Pair)->getName() < std::get<1>(Pair)->getName())
3469
        return true;
3470
      if (std::get<0>(Pair)->getName() > std::get<1>(Pair)->getName())
3471
        return false;
3472
    }
3473
    return false;
3474
  });
3475
  FeatureBitsets.erase(llvm::unique(FeatureBitsets), FeatureBitsets.end());
3476
  OS << "// Feature bitsets.\n"
3477
     << "enum : " << getMinimalTypeForRange(FeatureBitsets.size()) << " {\n"
3478
     << "  AMFBS_None,\n";
3479
  for (const auto &FeatureBitset : FeatureBitsets) {
3480
    if (FeatureBitset.empty())
3481
      continue;
3482
    OS << "  " << getNameForFeatureBitset(FeatureBitset) << ",\n";
3483
  }
3484
  OS << "};\n\n"
3485
     << "static constexpr FeatureBitset FeatureBitsets[] = {\n"
3486
     << "  {}, // AMFBS_None\n";
3487
  for (const auto &FeatureBitset : FeatureBitsets) {
3488
    if (FeatureBitset.empty())
3489
      continue;
3490
    OS << "  {";
3491
    for (const auto &Feature : FeatureBitset) {
3492
      const auto &I = Info.SubtargetFeatures.find(Feature);
3493
      assert(I != Info.SubtargetFeatures.end() && "Didn't import predicate?");
3494
      OS << I->second.getEnumBitName() << ", ";
3495
    }
3496
    OS << "},\n";
3497
  }
3498
  OS << "};\n\n";
3499

3500
  // Emit the static match table; unused classes get initialized to 0 which is
3501
  // guaranteed to be InvalidMatchClass.
3502
  //
3503
  // FIXME: We can reduce the size of this table very easily. First, we change
3504
  // it so that store the kinds in separate bit-fields for each index, which
3505
  // only needs to be the max width used for classes at that index (we also need
3506
  // to reject based on this during classification). If we then make sure to
3507
  // order the match kinds appropriately (putting mnemonics last), then we
3508
  // should only end up using a few bits for each class, especially the ones
3509
  // following the mnemonic.
3510
  OS << "namespace {\n";
3511
  OS << "  struct MatchEntry {\n";
3512
  OS << "    " << getMinimalTypeForRange(MaxMnemonicIndex) << " Mnemonic;\n";
3513
  OS << "    uint16_t Opcode;\n";
3514
  OS << "    " << getMinimalTypeForRange(NumConverters) << " ConvertFn;\n";
3515
  OS << "    " << getMinimalTypeForRange(FeatureBitsets.size())
3516
     << " RequiredFeaturesIdx;\n";
3517
  OS << "    "
3518
     << getMinimalTypeForRange(
3519
            std::distance(Info.Classes.begin(), Info.Classes.end()) +
3520
            2 /* Include 'InvalidMatchClass' and 'OptionalMatchClass' */)
3521
     << " Classes[" << MaxNumOperands << "];\n";
3522
  OS << "    StringRef getMnemonic() const {\n";
3523
  OS << "      return StringRef(MnemonicTable + Mnemonic + 1,\n";
3524
  OS << "                       MnemonicTable[Mnemonic]);\n";
3525
  OS << "    }\n";
3526
  OS << "  };\n\n";
3527

3528
  OS << "  // Predicate for searching for an opcode.\n";
3529
  OS << "  struct LessOpcode {\n";
3530
  OS << "    bool operator()(const MatchEntry &LHS, StringRef RHS) {\n";
3531
  OS << "      return LHS.getMnemonic() < RHS;\n";
3532
  OS << "    }\n";
3533
  OS << "    bool operator()(StringRef LHS, const MatchEntry &RHS) {\n";
3534
  OS << "      return LHS < RHS.getMnemonic();\n";
3535
  OS << "    }\n";
3536
  OS << "    bool operator()(const MatchEntry &LHS, const MatchEntry &RHS) {\n";
3537
  OS << "      return LHS.getMnemonic() < RHS.getMnemonic();\n";
3538
  OS << "    }\n";
3539
  OS << "  };\n";
3540

3541
  OS << "} // end anonymous namespace\n\n";
3542

3543
  unsigned VariantCount = Target.getAsmParserVariantCount();
3544
  for (unsigned VC = 0; VC != VariantCount; ++VC) {
3545
    Record *AsmVariant = Target.getAsmParserVariant(VC);
3546
    int AsmVariantNo = AsmVariant->getValueAsInt("Variant");
3547

3548
    OS << "static const MatchEntry MatchTable" << VC << "[] = {\n";
3549

3550
    for (const auto &MI : Info.Matchables) {
3551
      if (MI->AsmVariantID != AsmVariantNo)
3552
        continue;
3553

3554
      // Store a pascal-style length byte in the mnemonic.
3555
      std::string LenMnemonic =
3556
          char(MI->Mnemonic.size()) + MI->Mnemonic.lower();
3557
      OS << "  { " << StringTable.GetOrAddStringOffset(LenMnemonic, false)
3558
         << " /* " << MI->Mnemonic << " */, " << Target.getInstNamespace()
3559
         << "::" << MI->getResultInst()->TheDef->getName() << ", "
3560
         << MI->ConversionFnKind << ", ";
3561

3562
      // Write the required features mask.
3563
      OS << "AMFBS";
3564
      if (MI->RequiredFeatures.empty())
3565
        OS << "_None";
3566
      else
3567
        for (unsigned i = 0, e = MI->RequiredFeatures.size(); i != e; ++i)
3568
          OS << '_' << MI->RequiredFeatures[i]->TheDef->getName();
3569

3570
      OS << ", { ";
3571
      ListSeparator LS;
3572
      for (const MatchableInfo::AsmOperand &Op : MI->AsmOperands)
3573
        OS << LS << Op.Class->Name;
3574
      OS << " }, },\n";
3575
    }
3576

3577
    OS << "};\n\n";
3578
  }
3579

3580
  OS << "#include \"llvm/Support/Debug.h\"\n";
3581
  OS << "#include \"llvm/Support/Format.h\"\n\n";
3582

3583
  // Finally, build the match function.
3584
  OS << "unsigned " << Target.getName() << ClassName << "::\n"
3585
     << "MatchInstructionImpl(const OperandVector &Operands,\n";
3586
  OS << "                     MCInst &Inst,\n";
3587
  if (ReportMultipleNearMisses)
3588
    OS << "                     SmallVectorImpl<NearMissInfo> *NearMisses,\n";
3589
  else
3590
    OS << "                     uint64_t &ErrorInfo,\n"
3591
       << "                     FeatureBitset &MissingFeatures,\n";
3592
  OS << "                     bool matchingInlineAsm, unsigned VariantID) {\n";
3593

3594
  if (!ReportMultipleNearMisses) {
3595
    OS << "  // Eliminate obvious mismatches.\n";
3596
    OS << "  if (Operands.size() > " << (MaxNumOperands + HasMnemonicFirst)
3597
       << ") {\n";
3598
    OS << "    ErrorInfo = " << (MaxNumOperands + HasMnemonicFirst) << ";\n";
3599
    OS << "    return Match_InvalidOperand;\n";
3600
    OS << "  }\n\n";
3601
  }
3602

3603
  // Emit code to get the available features.
3604
  OS << "  // Get the current feature set.\n";
3605
  OS << "  const FeatureBitset &AvailableFeatures = "
3606
        "getAvailableFeatures();\n\n";
3607

3608
  OS << "  // Get the instruction mnemonic, which is the first token.\n";
3609
  if (HasMnemonicFirst) {
3610
    OS << "  StringRef Mnemonic = ((" << Target.getName()
3611
       << "Operand &)*Operands[0]).getToken();\n\n";
3612
  } else {
3613
    OS << "  StringRef Mnemonic;\n";
3614
    OS << "  if (Operands[0]->isToken())\n";
3615
    OS << "    Mnemonic = ((" << Target.getName()
3616
       << "Operand &)*Operands[0]).getToken();\n\n";
3617
  }
3618

3619
  if (HasMnemonicAliases) {
3620
    OS << "  // Process all MnemonicAliases to remap the mnemonic.\n";
3621
    OS << "  applyMnemonicAliases(Mnemonic, AvailableFeatures, VariantID);\n\n";
3622
  }
3623

3624
  // Emit code to compute the class list for this operand vector.
3625
  if (!ReportMultipleNearMisses) {
3626
    OS << "  // Some state to try to produce better error messages.\n";
3627
    OS << "  bool HadMatchOtherThanFeatures = false;\n";
3628
    OS << "  bool HadMatchOtherThanPredicate = false;\n";
3629
    OS << "  unsigned RetCode = Match_InvalidOperand;\n";
3630
    OS << "  MissingFeatures.set();\n";
3631
    OS << "  // Set ErrorInfo to the operand that mismatches if it is\n";
3632
    OS << "  // wrong for all instances of the instruction.\n";
3633
    OS << "  ErrorInfo = ~0ULL;\n";
3634
  }
3635

3636
  if (HasOptionalOperands) {
3637
    OS << "  SmallBitVector OptionalOperandsMask(" << MaxNumOperands << ");\n";
3638
  }
3639

3640
  // Emit code to search the table.
3641
  OS << "  // Find the appropriate table for this asm variant.\n";
3642
  OS << "  const MatchEntry *Start, *End;\n";
3643
  OS << "  switch (VariantID) {\n";
3644
  OS << "  default: llvm_unreachable(\"invalid variant!\");\n";
3645
  for (unsigned VC = 0; VC != VariantCount; ++VC) {
3646
    Record *AsmVariant = Target.getAsmParserVariant(VC);
3647
    int AsmVariantNo = AsmVariant->getValueAsInt("Variant");
3648
    OS << "  case " << AsmVariantNo << ": Start = std::begin(MatchTable" << VC
3649
       << "); End = std::end(MatchTable" << VC << "); break;\n";
3650
  }
3651
  OS << "  }\n";
3652

3653
  OS << "  // Search the table.\n";
3654
  if (HasMnemonicFirst) {
3655
    OS << "  auto MnemonicRange = "
3656
          "std::equal_range(Start, End, Mnemonic, LessOpcode());\n\n";
3657
  } else {
3658
    OS << "  auto MnemonicRange = std::pair(Start, End);\n";
3659
    OS << "  unsigned SIndex = Mnemonic.empty() ? 0 : 1;\n";
3660
    OS << "  if (!Mnemonic.empty())\n";
3661
    OS << "    MnemonicRange = "
3662
          "std::equal_range(Start, End, Mnemonic.lower(), LessOpcode());\n\n";
3663
  }
3664

3665
  OS << "  DEBUG_WITH_TYPE(\"asm-matcher\", dbgs() << \"AsmMatcher: found \" "
3666
        "<<\n"
3667
     << "  std::distance(MnemonicRange.first, MnemonicRange.second) <<\n"
3668
     << "  \" encodings with mnemonic '\" << Mnemonic << \"'\\n\");\n\n";
3669

3670
  OS << "  // Return a more specific error code if no mnemonics match.\n";
3671
  OS << "  if (MnemonicRange.first == MnemonicRange.second)\n";
3672
  OS << "    return Match_MnemonicFail;\n\n";
3673

3674
  OS << "  for (const MatchEntry *it = MnemonicRange.first, "
3675
     << "*ie = MnemonicRange.second;\n";
3676
  OS << "       it != ie; ++it) {\n";
3677
  OS << "    const FeatureBitset &RequiredFeatures = "
3678
        "FeatureBitsets[it->RequiredFeaturesIdx];\n";
3679
  OS << "    bool HasRequiredFeatures =\n";
3680
  OS << "      (AvailableFeatures & RequiredFeatures) == RequiredFeatures;\n";
3681
  OS << "    DEBUG_WITH_TYPE(\"asm-matcher\", dbgs() << \"Trying to match "
3682
        "opcode \"\n";
3683
  OS << "                                          << MII.getName(it->Opcode) "
3684
        "<< \"\\n\");\n";
3685

3686
  if (ReportMultipleNearMisses) {
3687
    OS << "    // Some state to record ways in which this instruction did not "
3688
          "match.\n";
3689
    OS << "    NearMissInfo OperandNearMiss = NearMissInfo::getSuccess();\n";
3690
    OS << "    NearMissInfo FeaturesNearMiss = NearMissInfo::getSuccess();\n";
3691
    OS << "    NearMissInfo EarlyPredicateNearMiss = "
3692
          "NearMissInfo::getSuccess();\n";
3693
    OS << "    NearMissInfo LatePredicateNearMiss = "
3694
          "NearMissInfo::getSuccess();\n";
3695
    OS << "    bool MultipleInvalidOperands = false;\n";
3696
  }
3697

3698
  if (HasMnemonicFirst) {
3699
    OS << "    // equal_range guarantees that instruction mnemonic matches.\n";
3700
    OS << "    assert(Mnemonic == it->getMnemonic());\n";
3701
  }
3702

3703
  // Emit check that the subclasses match.
3704
  if (!ReportMultipleNearMisses)
3705
    OS << "    bool OperandsValid = true;\n";
3706
  if (HasOptionalOperands) {
3707
    OS << "    OptionalOperandsMask.reset(0, " << MaxNumOperands << ");\n";
3708
  }
3709
  OS << "    for (unsigned FormalIdx = " << (HasMnemonicFirst ? "0" : "SIndex")
3710
     << ", ActualIdx = " << (HasMnemonicFirst ? "1" : "SIndex")
3711
     << "; FormalIdx != " << MaxNumOperands << "; ++FormalIdx) {\n";
3712
  OS << "      auto Formal = "
3713
     << "static_cast<MatchClassKind>(it->Classes[FormalIdx]);\n";
3714
  OS << "      DEBUG_WITH_TYPE(\"asm-matcher\",\n";
3715
  OS << "                      dbgs() << \"  Matching formal operand class \" "
3716
        "<< getMatchClassName(Formal)\n";
3717
  OS << "                             << \" against actual operand at index \" "
3718
        "<< ActualIdx);\n";
3719
  OS << "      if (ActualIdx < Operands.size())\n";
3720
  OS << "        DEBUG_WITH_TYPE(\"asm-matcher\", dbgs() << \" (\";\n";
3721
  OS << "                        Operands[ActualIdx]->print(dbgs()); dbgs() << "
3722
        "\"): \");\n";
3723
  OS << "      else\n";
3724
  OS << "        DEBUG_WITH_TYPE(\"asm-matcher\", dbgs() << \": \");\n";
3725
  OS << "      if (ActualIdx >= Operands.size()) {\n";
3726
  OS << "        DEBUG_WITH_TYPE(\"asm-matcher\", dbgs() << \"actual operand "
3727
        "index out of range\\n\");\n";
3728
  if (ReportMultipleNearMisses) {
3729
    OS << "        bool ThisOperandValid = (Formal == "
3730
       << "InvalidMatchClass) || "
3731
          "isSubclass(Formal, OptionalMatchClass);\n";
3732
    OS << "        if (!ThisOperandValid) {\n";
3733
    OS << "          if (!OperandNearMiss) {\n";
3734
    OS << "            // Record info about match failure for later use.\n";
3735
    OS << "            DEBUG_WITH_TYPE(\"asm-matcher\", dbgs() << \"recording "
3736
          "too-few-operands near miss\\n\");\n";
3737
    OS << "            OperandNearMiss =\n";
3738
    OS << "                NearMissInfo::getTooFewOperands(Formal, "
3739
          "it->Opcode);\n";
3740
    OS << "          } else if (OperandNearMiss.getKind() != "
3741
          "NearMissInfo::NearMissTooFewOperands) {\n";
3742
    OS << "            // If more than one operand is invalid, give up on this "
3743
          "match entry.\n";
3744
    OS << "            DEBUG_WITH_TYPE(\n";
3745
    OS << "                \"asm-matcher\",\n";
3746
    OS << "                dbgs() << \"second invalid operand, giving up on "
3747
          "this opcode\\n\");\n";
3748
    OS << "            MultipleInvalidOperands = true;\n";
3749
    OS << "            break;\n";
3750
    OS << "          }\n";
3751
    OS << "        } else {\n";
3752
    OS << "          DEBUG_WITH_TYPE(\"asm-matcher\", dbgs() << \"but formal "
3753
          "operand not required\\n\");\n";
3754
    OS << "          if (isSubclass(Formal, OptionalMatchClass)) {\n";
3755
    OS << "            OptionalOperandsMask.set(FormalIdx);\n";
3756
    OS << "          }\n";
3757
    OS << "        }\n";
3758
    OS << "        continue;\n";
3759
  } else {
3760
    OS << "        if (Formal == InvalidMatchClass) {\n";
3761
    if (HasOptionalOperands) {
3762
      OS << "          OptionalOperandsMask.set(FormalIdx, " << MaxNumOperands
3763
         << ");\n";
3764
    }
3765
    OS << "          break;\n";
3766
    OS << "        }\n";
3767
    OS << "        if (isSubclass(Formal, OptionalMatchClass)) {\n";
3768
    if (HasOptionalOperands) {
3769
      OS << "          OptionalOperandsMask.set(FormalIdx);\n";
3770
    }
3771
    OS << "          continue;\n";
3772
    OS << "        }\n";
3773
    OS << "        OperandsValid = false;\n";
3774
    OS << "        ErrorInfo = ActualIdx;\n";
3775
    OS << "        break;\n";
3776
  }
3777
  OS << "      }\n";
3778
  OS << "      MCParsedAsmOperand &Actual = *Operands[ActualIdx];\n";
3779
  OS << "      unsigned Diag = validateOperandClass(Actual, Formal);\n";
3780
  OS << "      if (Diag == Match_Success) {\n";
3781
  OS << "        DEBUG_WITH_TYPE(\"asm-matcher\",\n";
3782
  OS << "                        dbgs() << \"match success using generic "
3783
        "matcher\\n\");\n";
3784
  OS << "        ++ActualIdx;\n";
3785
  OS << "        continue;\n";
3786
  OS << "      }\n";
3787
  OS << "      // If the generic handler indicates an invalid operand\n";
3788
  OS << "      // failure, check for a special case.\n";
3789
  OS << "      if (Diag != Match_Success) {\n";
3790
  OS << "        unsigned TargetDiag = validateTargetOperandClass(Actual, "
3791
        "Formal);\n";
3792
  OS << "        if (TargetDiag == Match_Success) {\n";
3793
  OS << "          DEBUG_WITH_TYPE(\"asm-matcher\",\n";
3794
  OS << "                          dbgs() << \"match success using target "
3795
        "matcher\\n\");\n";
3796
  OS << "          ++ActualIdx;\n";
3797
  OS << "          continue;\n";
3798
  OS << "        }\n";
3799
  OS << "        // If the target matcher returned a specific error code use\n";
3800
  OS << "        // that, else use the one from the generic matcher.\n";
3801
  OS << "        if (TargetDiag != Match_InvalidOperand && "
3802
        "HasRequiredFeatures)\n";
3803
  OS << "          Diag = TargetDiag;\n";
3804
  OS << "      }\n";
3805
  OS << "      // If current formal operand wasn't matched and it is optional\n"
3806
     << "      // then try to match next formal operand\n";
3807
  OS << "      if (Diag == Match_InvalidOperand "
3808
     << "&& isSubclass(Formal, OptionalMatchClass)) {\n";
3809
  if (HasOptionalOperands) {
3810
    OS << "        OptionalOperandsMask.set(FormalIdx);\n";
3811
  }
3812
  OS << "        DEBUG_WITH_TYPE(\"asm-matcher\", dbgs() << \"ignoring "
3813
        "optional operand\\n\");\n";
3814
  OS << "        continue;\n";
3815
  OS << "      }\n";
3816

3817
  if (ReportMultipleNearMisses) {
3818
    OS << "      if (!OperandNearMiss) {\n";
3819
    OS << "        // If this is the first invalid operand we have seen, "
3820
          "record some\n";
3821
    OS << "        // information about it.\n";
3822
    OS << "        DEBUG_WITH_TYPE(\n";
3823
    OS << "            \"asm-matcher\",\n";
3824
    OS << "            dbgs()\n";
3825
    OS << "                << \"operand match failed, recording near-miss with "
3826
          "diag code \"\n";
3827
    OS << "                << Diag << \"\\n\");\n";
3828
    OS << "        OperandNearMiss =\n";
3829
    OS << "            NearMissInfo::getMissedOperand(Diag, Formal, "
3830
          "it->Opcode, ActualIdx);\n";
3831
    OS << "        ++ActualIdx;\n";
3832
    OS << "      } else {\n";
3833
    OS << "        // If more than one operand is invalid, give up on this "
3834
          "match entry.\n";
3835
    OS << "        DEBUG_WITH_TYPE(\n";
3836
    OS << "            \"asm-matcher\",\n";
3837
    OS << "            dbgs() << \"second operand mismatch, skipping this "
3838
          "opcode\\n\");\n";
3839
    OS << "        MultipleInvalidOperands = true;\n";
3840
    OS << "        break;\n";
3841
    OS << "      }\n";
3842
    OS << "    }\n\n";
3843
  } else {
3844
    OS << "      // If this operand is broken for all of the instances of "
3845
          "this\n";
3846
    OS << "      // mnemonic, keep track of it so we can report loc info.\n";
3847
    OS << "      // If we already had a match that only failed due to a\n";
3848
    OS << "      // target predicate, that diagnostic is preferred.\n";
3849
    OS << "      if (!HadMatchOtherThanPredicate &&\n";
3850
    OS << "          (it == MnemonicRange.first || ErrorInfo <= ActualIdx)) "
3851
          "{\n";
3852
    OS << "        if (HasRequiredFeatures && (ErrorInfo != ActualIdx || Diag "
3853
          "!= Match_InvalidOperand))\n";
3854
    OS << "          RetCode = Diag;\n";
3855
    OS << "        ErrorInfo = ActualIdx;\n";
3856
    OS << "      }\n";
3857
    OS << "      // Otherwise, just reject this instance of the mnemonic.\n";
3858
    OS << "      OperandsValid = false;\n";
3859
    OS << "      break;\n";
3860
    OS << "    }\n\n";
3861
  }
3862

3863
  if (ReportMultipleNearMisses)
3864
    OS << "    if (MultipleInvalidOperands) {\n";
3865
  else
3866
    OS << "    if (!OperandsValid) {\n";
3867
  OS << "      DEBUG_WITH_TYPE(\"asm-matcher\", dbgs() << \"Opcode result: "
3868
        "multiple \"\n";
3869
  OS << "                                               \"operand mismatches, "
3870
        "ignoring \"\n";
3871
  OS << "                                               \"this opcode\\n\");\n";
3872
  OS << "      continue;\n";
3873
  OS << "    }\n";
3874

3875
  // Emit check that the required features are available.
3876
  OS << "    if (!HasRequiredFeatures) {\n";
3877
  if (!ReportMultipleNearMisses)
3878
    OS << "      HadMatchOtherThanFeatures = true;\n";
3879
  OS << "      FeatureBitset NewMissingFeatures = RequiredFeatures & "
3880
        "~AvailableFeatures;\n";
3881
  OS << "      DEBUG_WITH_TYPE(\"asm-matcher\", dbgs() << \"Missing target "
3882
        "features:\";\n";
3883
  OS << "                      for (unsigned I = 0, E = "
3884
        "NewMissingFeatures.size(); I != E; ++I)\n";
3885
  OS << "                        if (NewMissingFeatures[I])\n";
3886
  OS << "                          dbgs() << ' ' << I;\n";
3887
  OS << "                      dbgs() << \"\\n\");\n";
3888
  if (ReportMultipleNearMisses) {
3889
    OS << "      FeaturesNearMiss = "
3890
          "NearMissInfo::getMissedFeature(NewMissingFeatures);\n";
3891
  } else {
3892
    OS << "      if (NewMissingFeatures.count() <=\n"
3893
          "          MissingFeatures.count())\n";
3894
    OS << "        MissingFeatures = NewMissingFeatures;\n";
3895
    OS << "      continue;\n";
3896
  }
3897
  OS << "    }\n";
3898
  OS << "\n";
3899
  OS << "    Inst.clear();\n\n";
3900
  OS << "    Inst.setOpcode(it->Opcode);\n";
3901
  // Verify the instruction with the target-specific match predicate function.
3902
  OS << "    // We have a potential match but have not rendered the operands.\n"
3903
     << "    // Check the target predicate to handle any context sensitive\n"
3904
        "    // constraints.\n"
3905
     << "    // For example, Ties that are referenced multiple times must be\n"
3906
        "    // checked here to ensure the input is the same for each match\n"
3907
        "    // constraints. If we leave it any later the ties will have been\n"
3908
        "    // canonicalized\n"
3909
     << "    unsigned MatchResult;\n"
3910
     << "    if ((MatchResult = checkEarlyTargetMatchPredicate(Inst, "
3911
        "Operands)) != Match_Success) {\n"
3912
     << "      Inst.clear();\n";
3913
  OS << "      DEBUG_WITH_TYPE(\n";
3914
  OS << "          \"asm-matcher\",\n";
3915
  OS << "          dbgs() << \"Early target match predicate failed with diag "
3916
        "code \"\n";
3917
  OS << "                 << MatchResult << \"\\n\");\n";
3918
  if (ReportMultipleNearMisses) {
3919
    OS << "      EarlyPredicateNearMiss = "
3920
          "NearMissInfo::getMissedPredicate(MatchResult);\n";
3921
  } else {
3922
    OS << "      RetCode = MatchResult;\n"
3923
       << "      HadMatchOtherThanPredicate = true;\n"
3924
       << "      continue;\n";
3925
  }
3926
  OS << "    }\n\n";
3927

3928
  if (ReportMultipleNearMisses) {
3929
    OS << "    // If we did not successfully match the operands, then we can't "
3930
          "convert to\n";
3931
    OS << "    // an MCInst, so bail out on this instruction variant now.\n";
3932
    OS << "    if (OperandNearMiss) {\n";
3933
    OS << "      // If the operand mismatch was the only problem, reprrt it as "
3934
          "a near-miss.\n";
3935
    OS << "      if (NearMisses && !FeaturesNearMiss && "
3936
          "!EarlyPredicateNearMiss) {\n";
3937
    OS << "        DEBUG_WITH_TYPE(\n";
3938
    OS << "            \"asm-matcher\",\n";
3939
    OS << "            dbgs()\n";
3940
    OS << "                << \"Opcode result: one mismatched operand, adding "
3941
          "near-miss\\n\");\n";
3942
    OS << "        NearMisses->push_back(OperandNearMiss);\n";
3943
    OS << "      } else {\n";
3944
    OS << "        DEBUG_WITH_TYPE(\"asm-matcher\", dbgs() << \"Opcode result: "
3945
          "multiple \"\n";
3946
    OS << "                                                 \"types of "
3947
          "mismatch, so not \"\n";
3948
    OS << "                                                 \"reporting "
3949
          "near-miss\\n\");\n";
3950
    OS << "      }\n";
3951
    OS << "      continue;\n";
3952
    OS << "    }\n\n";
3953
  }
3954

3955
  // When converting parsed operands to MCInst we need to know whether optional
3956
  // operands were parsed or not so that we can choose the correct converter
3957
  // function. We also need to know this when checking tied operand constraints.
3958
  // DefaultsOffset is an array of deltas between the formal (MCInst) and the
3959
  // actual (parsed operand array) operand indices. When all optional operands
3960
  // are present, all elements of the array are zeros. If some of the optional
3961
  // operands are absent, the array might look like '0, 0, 1, 1, 1, 2, 2, 3',
3962
  // where each increment in value reflects the absence of an optional operand.
3963
  if (HasOptionalOperands) {
3964
    OS << "    unsigned DefaultsOffset[" << (MaxNumOperands + 1)
3965
       << "] = { 0 };\n";
3966
    OS << "    assert(OptionalOperandsMask.size() == " << (MaxNumOperands)
3967
       << ");\n";
3968
    OS << "    for (unsigned i = 0, NumDefaults = 0; i < " << (MaxNumOperands)
3969
       << "; ++i) {\n";
3970
    OS << "      DefaultsOffset[i + 1] = NumDefaults;\n";
3971
    OS << "      NumDefaults += (OptionalOperandsMask[i] ? 1 : 0);\n";
3972
    OS << "    }\n\n";
3973
  }
3974

3975
  OS << "    if (matchingInlineAsm) {\n";
3976
  OS << "      convertToMapAndConstraints(it->ConvertFn, Operands);\n";
3977
  if (!ReportMultipleNearMisses) {
3978
    if (HasOptionalOperands) {
3979
      OS << "      if (!checkAsmTiedOperandConstraints(*this, it->ConvertFn, "
3980
            "Operands,\n";
3981
      OS << "                                          DefaultsOffset, "
3982
            "ErrorInfo))\n";
3983
    } else {
3984
      OS << "      if (!checkAsmTiedOperandConstraints(*this, it->ConvertFn, "
3985
            "Operands,\n";
3986
      OS << "                                          ErrorInfo))\n";
3987
    }
3988
    OS << "        return Match_InvalidTiedOperand;\n";
3989
    OS << "\n";
3990
  }
3991
  OS << "      return Match_Success;\n";
3992
  OS << "    }\n\n";
3993
  OS << "    // We have selected a definite instruction, convert the parsed\n"
3994
     << "    // operands into the appropriate MCInst.\n";
3995
  if (HasOptionalOperands) {
3996
    OS << "    convertToMCInst(it->ConvertFn, Inst, it->Opcode, Operands,\n"
3997
       << "                    OptionalOperandsMask, DefaultsOffset);\n";
3998
  } else {
3999
    OS << "    convertToMCInst(it->ConvertFn, Inst, it->Opcode, Operands);\n";
4000
  }
4001
  OS << "\n";
4002

4003
  // Verify the instruction with the target-specific match predicate function.
4004
  OS << "    // We have a potential match. Check the target predicate to\n"
4005
     << "    // handle any context sensitive constraints.\n"
4006
     << "    if ((MatchResult = checkTargetMatchPredicate(Inst)) !="
4007
     << " Match_Success) {\n"
4008
     << "      DEBUG_WITH_TYPE(\"asm-matcher\",\n"
4009
     << "                      dbgs() << \"Target match predicate failed with "
4010
        "diag code \"\n"
4011
     << "                             << MatchResult << \"\\n\");\n"
4012
     << "      Inst.clear();\n";
4013
  if (ReportMultipleNearMisses) {
4014
    OS << "      LatePredicateNearMiss = "
4015
          "NearMissInfo::getMissedPredicate(MatchResult);\n";
4016
  } else {
4017
    OS << "      RetCode = MatchResult;\n"
4018
       << "      HadMatchOtherThanPredicate = true;\n"
4019
       << "      continue;\n";
4020
  }
4021
  OS << "    }\n\n";
4022

4023
  if (ReportMultipleNearMisses) {
4024
    OS << "    int NumNearMisses = ((int)(bool)OperandNearMiss +\n";
4025
    OS << "                         (int)(bool)FeaturesNearMiss +\n";
4026
    OS << "                         (int)(bool)EarlyPredicateNearMiss +\n";
4027
    OS << "                         (int)(bool)LatePredicateNearMiss);\n";
4028
    OS << "    if (NumNearMisses == 1) {\n";
4029
    OS << "      // We had exactly one type of near-miss, so add that to the "
4030
          "list.\n";
4031
    OS << "      assert(!OperandNearMiss && \"OperandNearMiss was handled "
4032
          "earlier\");\n";
4033
    OS << "      DEBUG_WITH_TYPE(\"asm-matcher\", dbgs() << \"Opcode result: "
4034
          "found one type of \"\n";
4035
    OS << "                                            \"mismatch, so "
4036
          "reporting a \"\n";
4037
    OS << "                                            \"near-miss\\n\");\n";
4038
    OS << "      if (NearMisses && FeaturesNearMiss)\n";
4039
    OS << "        NearMisses->push_back(FeaturesNearMiss);\n";
4040
    OS << "      else if (NearMisses && EarlyPredicateNearMiss)\n";
4041
    OS << "        NearMisses->push_back(EarlyPredicateNearMiss);\n";
4042
    OS << "      else if (NearMisses && LatePredicateNearMiss)\n";
4043
    OS << "        NearMisses->push_back(LatePredicateNearMiss);\n";
4044
    OS << "\n";
4045
    OS << "      continue;\n";
4046
    OS << "    } else if (NumNearMisses > 1) {\n";
4047
    OS << "      // This instruction missed in more than one way, so ignore "
4048
          "it.\n";
4049
    OS << "      DEBUG_WITH_TYPE(\"asm-matcher\", dbgs() << \"Opcode result: "
4050
          "multiple \"\n";
4051
    OS << "                                               \"types of mismatch, "
4052
          "so not \"\n";
4053
    OS << "                                               \"reporting "
4054
          "near-miss\\n\");\n";
4055
    OS << "      continue;\n";
4056
    OS << "    }\n";
4057
  }
4058

4059
  // Call the post-processing function, if used.
4060
  StringRef InsnCleanupFn = AsmParser->getValueAsString("AsmParserInstCleanup");
4061
  if (!InsnCleanupFn.empty())
4062
    OS << "    " << InsnCleanupFn << "(Inst);\n";
4063

4064
  if (HasDeprecation) {
4065
    OS << "    std::string Info;\n";
4066
    OS << "    if "
4067
          "(!getParser().getTargetParser().getTargetOptions()."
4068
          "MCNoDeprecatedWarn &&\n";
4069
    OS << "        MII.getDeprecatedInfo(Inst, getSTI(), Info)) {\n";
4070
    OS << "      SMLoc Loc = ((" << Target.getName()
4071
       << "Operand &)*Operands[0]).getStartLoc();\n";
4072
    OS << "      getParser().Warning(Loc, Info, std::nullopt);\n";
4073
    OS << "    }\n";
4074
  }
4075

4076
  if (!ReportMultipleNearMisses) {
4077
    if (HasOptionalOperands) {
4078
      OS << "    if (!checkAsmTiedOperandConstraints(*this, it->ConvertFn, "
4079
            "Operands,\n";
4080
      OS << "                                         DefaultsOffset, "
4081
            "ErrorInfo))\n";
4082
    } else {
4083
      OS << "    if (!checkAsmTiedOperandConstraints(*this, it->ConvertFn, "
4084
            "Operands,\n";
4085
      OS << "                                         ErrorInfo))\n";
4086
    }
4087
    OS << "      return Match_InvalidTiedOperand;\n";
4088
    OS << "\n";
4089
  }
4090

4091
  OS << "    DEBUG_WITH_TYPE(\n";
4092
  OS << "        \"asm-matcher\",\n";
4093
  OS << "        dbgs() << \"Opcode result: complete match, selecting this "
4094
        "opcode\\n\");\n";
4095
  OS << "    return Match_Success;\n";
4096
  OS << "  }\n\n";
4097

4098
  if (ReportMultipleNearMisses) {
4099
    OS << "  // No instruction variants matched exactly.\n";
4100
    OS << "  return Match_NearMisses;\n";
4101
  } else {
4102
    OS << "  // Okay, we had no match.  Try to return a useful error code.\n";
4103
    OS << "  if (HadMatchOtherThanPredicate || !HadMatchOtherThanFeatures)\n";
4104
    OS << "    return RetCode;\n\n";
4105
    OS << "  ErrorInfo = 0;\n";
4106
    OS << "  return Match_MissingFeature;\n";
4107
  }
4108
  OS << "}\n\n";
4109

4110
  if (!Info.OperandMatchInfo.empty())
4111
    emitCustomOperandParsing(OS, Target, Info, ClassName, StringTable,
4112
                             MaxMnemonicIndex, FeatureBitsets.size(),
4113
                             HasMnemonicFirst, *AsmParser);
4114

4115
  OS << "#endif // GET_MATCHER_IMPLEMENTATION\n\n";
4116

4117
  OS << "\n#ifdef GET_MNEMONIC_SPELL_CHECKER\n";
4118
  OS << "#undef GET_MNEMONIC_SPELL_CHECKER\n\n";
4119

4120
  emitMnemonicSpellChecker(OS, Target, VariantCount);
4121

4122
  OS << "#endif // GET_MNEMONIC_SPELL_CHECKER\n\n";
4123

4124
  OS << "\n#ifdef GET_MNEMONIC_CHECKER\n";
4125
  OS << "#undef GET_MNEMONIC_CHECKER\n\n";
4126

4127
  emitMnemonicChecker(OS, Target, VariantCount, HasMnemonicFirst,
4128
                      HasMnemonicAliases);
4129

4130
  OS << "#endif // GET_MNEMONIC_CHECKER\n\n";
4131
}
4132

4133
static TableGen::Emitter::OptClass<AsmMatcherEmitter>
4134
    X("gen-asm-matcher", "Generate assembly instruction matcher");
4135