[Assembler] Report multiple near misses for invalid instructions

[olista01]

Summary

The current table-generated assembly instruction matcher returns a
64-bit error code when matching fails. Since multiple instruction
encodings with the same mnemonic can fail for different reasons, it uses
some heuristics to decide which message is important.

This heuristic does not work well for targets that have many encodings
with the same mnemonic but different operands, or which have different
versions of instructions controlled by subtarget features, as it is hard
to know which encoding the user was intending to use.

Instead of trying to improve the heuristic in the table-generated
matcher, this patch changes it to report a list of near-miss encodings.
This list contains an entry for each encoding with the correct mnemonic,
but with exactly one thing preventing it from being valid. This thing
could be a single invalid operand, a missing target feature or a failed
target-specific validation function.

The target-specific assembly parser can then report an error message
giving multiple options for instruction variants that the user may have
been trying to use. For example, I am working on a patch to use this for
ARM, which can give this error for an invalid instruction for ARMv6-M:

<stdin>:8:3: error: invalid instruction, multiple near-miss encodings found
  adds r0, r1, #0x8
  ^
<stdin>:8:3: note: for one encoding: instruction requires: thumb2
  adds r0, r1, #0x8
  ^
<stdin>:8:16: note: for one encoding: expected an integer in range [0, 7]
  adds r0, r1, #0x8
               ^
<stdin>:8:16: note: for one encoding: expected a register in range [r0, r7]
  adds r0, r1, #0x8
               ^

This also allows the target-specific assembly parser to apply its own
heuristics to suppress some errors. For example, the error "instruction
requires: arm-mode" is never going to be useful when targeting an
M-profile architecture (which does not have ARM mode).

This patch just adds the target-independent mechanism for doing this,
all targets still use the old mechanism. I've added a bit in the
AsmParser tablegen class to allow targets to switch to this new
mechanism. To use this, the target-specific assembly parser will have to
be modified for the change in signature of MatchInstructionImpl, and to
report errors based on the list of near-misses.

[echristo]

In general looks ok, can you share the next step patch to make sure that no only is this fine, but is also the direction we want to go?

Thanks!

-eric

ps. silly nit inline.

include/llvm/MC/MCParser/MCTargetAsmParser.h

94

Random nit: no comma necessary.

[olista01]

Sorry it's taken me so long to get back to this, I've now posted the patch the ARM-specific usage of this at D31530.

[olista01]

Ping.

[olista01]

Ping.

[rengolin]

@echristo, any comments on this?

[echristo]

Catching up on code review. This is one of the next things on my list.

[olista01]

Ping

[echristo]

Hi Oliver!

I'm sorry for the delay, that said I'd also like to see a lot more commenting through here along with how we expect this API/data structures to work. It's hard to review this because I'm not sure how it's going to be used ultimately.

I don't see any noticeable problems, but I'd really like to see how this is going to be used (and have that commented in the source) before putting this in.

Thanks!

-eric

[olista01]

Expanded comments on the NearMissInfo struct.

If you want an example of how this will be used in practice, D31530 uses it in the ARM assembly parser.

[rengolin]

Hi Oliver,

D31530 is looking great (which depends on this one), but I'd like to get Eric's final approval for this one.

@echristo, what kind of additional comments are you expecting to see in the code? Did you have a look at D31530 (a concrete implementation of this logic)?

cheers,
--renato

[olista01]

Ping.

[olista01]

Ping.

I have a number of patches already approved which depend on this (using it in the ARM asm parser), and a few more that I'm working on, so it would be good to get this committed soon.

[echristo]

Sorry for the delay, go ahead.

include/llvm/MC/MCParser/MCTargetAsmParser.h

 };
 
 enum OperandMatchResultTy {
   MatchOperand_Success,  // operand matched successfully
   MatchOperand_NoMatch,  // operand did not match
   MatchOperand_ParseFail // operand matched but had errors
 };
 
+// When matching of an assembly instruction fails, there may be multiple
+// encodings that are close to being a match. It's often ambiguous which one
+// the programmer intended to use, so we want to report an error which mentions
+// each of these "near-miss" encodings. This struct contains information about
+// one such encoding, and why it did not match the parsed instruction.
+class NearMissInfo {
+public:
+  enum NearMissKind {
+    NoNearMiss,
+    NearMissOperand,
+    NearMissFeature,
+    NearMissPredicate,
+    NearMissTooFewOperands,
+  };
+
+  // The encoding is valid for the parsed assembly string. This is only used
+  // internally to the table-generated assembly matcher.
+  static NearMissInfo getSuccess() { return NearMissInfo(); }
+
+  // The instruction encoding is not valid because it requires some target
+  // features that are not currently enabled. MissingFeatures has a bit set for
+  // each feature that the encoding needs but which is not enabled.
+  static NearMissInfo getMissedFeature(uint64_t MissingFeatures) {
+    NearMissInfo Result;
+    Result.Kind = NearMissFeature;
+    Result.Features = MissingFeatures;
+    return Result;
+  }
+
+  // The instruction encoding is not valid because the target-specific
+  // predicate function returned an error code. FailureCode is the
+  // target-specific error code returned by the predicate.
+  static NearMissInfo getMissedPredicate(unsigned FailureCode) {
+    NearMissInfo Result;
+    Result.Kind = NearMissPredicate;
+    Result.PredicateError = FailureCode;
+    return Result;
+  }
+
+  // The instruction encoding is not valid because one (and only one) parsed
+  // operand is not of the correct type. OperandError is the error code
+  // relating to the operand class expected by the encoding. OperandClass is
+  // the type of the expected operand. Opcode is the opcode of the encoding.
+  // OperandIndex is the index into the parsed operand list.
+  static NearMissInfo getMissedOperand(unsigned OperandError,
+                                       unsigned OperandClass, unsigned Opcode,
+                                       unsigned OperandIndex) {
+    NearMissInfo Result;
+    Result.Kind = NearMissOperand;
+    Result.MissedOperand.Error = OperandError;
+    Result.MissedOperand.Class = OperandClass;
+    Result.MissedOperand.Opcode = Opcode;
+    Result.MissedOperand.Index = OperandIndex;
+    return Result;
+  }
+
+  // The instruction encoding is not valid because it expects more operands
+  // than were parsed. OperandClass is the class of the expected operand that
+  // was not provided. Opcode is the instruction encoding.
+  static NearMissInfo getTooFewOperands(unsigned OperandClass,
+                                        unsigned Opcode) {
+    NearMissInfo Result;
+    Result.Kind = NearMissTooFewOperands;
+    Result.TooFewOperands.Class = OperandClass;
+    Result.TooFewOperands.Opcode = Opcode;
+    return Result;
+  }
+
+  operator bool() const { return Kind != NoNearMiss; }
+
+  NearMissKind getKind() const { return Kind; }
+
+  // Feature flags required by the instruction, that the current target does
+  // not have.
+  uint64_t getFeatures() const {
+    assert(Kind == NearMissFeature);
+    return Features;
+  }
+  // Error code returned by the target predicate when validating this
+  // instruction encoding.
+  unsigned getPredicateError() const {
+    assert(Kind == NearMissPredicate);
+    return PredicateError;
+  }
+  // MatchClassKind of the operand that we expected to see.
+  unsigned getOperandClass() const {
+    assert(Kind == NearMissOperand || Kind == NearMissTooFewOperands);
+    return MissedOperand.Class;
+  }
+  // Opcode of the encoding we were trying to match.
+  unsigned getOpcode() const {
+    assert(Kind == NearMissOperand || Kind == NearMissTooFewOperands);
+    return MissedOperand.Opcode;
+  }
+  // Error code returned when validating the operand.
+  unsigned getOperandError() const {
+    assert(Kind == NearMissOperand);
+    return MissedOperand.Error;
+  }
+  // Index of the actual operand we were trying to match in the list of parsed
+  // operands.
+  unsigned getOperandIndex() const {
+    assert(Kind == NearMissOperand);
+    return MissedOperand.Index;
+  }
+
+private:
+  NearMissKind Kind;
+
+  // These two structs share a common prefix, so we can safely rely on the fact
+  // that they overlap in the union.
+  struct MissedOpInfo {
+    unsigned Class;
+    unsigned Opcode;
+    unsigned Error;
+    unsigned Index;
+  };
+
+  struct TooFewOperandsInfo {
+    unsigned Class;
+    unsigned Opcode;
+  };
+
+  union {
+    uint64_t Features;
+    unsigned PredicateError;
+    MissedOpInfo MissedOperand;
+    TooFewOperandsInfo TooFewOperands;
+  };
+
+  NearMissInfo() : Kind(NoNearMiss) {}
+};
+
 /// MCTargetAsmParser - Generic interface to target specific assembly parsers.
 class MCTargetAsmParser : public MCAsmParserExtension {
 public:
   enum MatchResultTy {
     Match_InvalidOperand,
     Match_MissingFeature,
     Match_MnemonicFail,
     Match_Success,
+    Match_NearMisses,
     FIRST_TARGET_MATCH_RESULT_TY
   };
 
 protected: // Can only create subclasses.
   MCTargetAsmParser(MCTargetOptions const &, const MCSubtargetInfo &STI);
 
   /// Create a copy of STI and return a non-const reference to it.
   MCSubtargetInfo &copySTI();

include/llvm/Target/Target.td

class AsmParser {
   // This generates a function which can be used to lookup registers from
   // their aliases. This function will fail when called on targets where
   // several registers share the same alias (i.e. not a 1:1 mapping).
   bit ShouldEmitMatchRegisterAltName = 0;
 
   // HasMnemonicFirst - Set to false if target instructions don't always
   // start with a mnemonic as the first token.
   bit HasMnemonicFirst = 1;
+
+  // ReportMultipleNearMisses -
+  // When 0, the assembly matcher reports an error for one encoding or operand
+  // that did not match the parsed instruction.
+  // When 1, the assmebly matcher returns a list of encodings that were close
+  // to matching the parsed instruction, so to allow more detailed error
+  // messages.
+  bit ReportMultipleNearMisses = 0;
 }
 def DefaultAsmParser : AsmParser;
 
 //===----------------------------------------------------------------------===//
 // AsmParserVariant - Subtargets can have multiple different assembly parsers
 // (e.g. AT&T vs Intel syntax on X86 for example). This class can be
 // implemented by targets to describe such variants.
 //

utils/TableGen/AsmMatcherEmitter.cpp

if (NumAmbiguous)
              << " ambiguous matchables!\n";
   });
 
   // Compute the information on the custom operand parsing.
   Info.buildOperandMatchInfo();
 
   bool HasMnemonicFirst = AsmParser->getValueAsBit("HasMnemonicFirst");
   bool HasOptionalOperands = Info.hasOptionalOperands();
+  bool ReportMultipleNearMisses =
+      AsmParser->getValueAsBit("ReportMultipleNearMisses");
 
   // Write the output.
 
   // Information for the class declaration.
   OS << "\n#ifdef GET_ASSEMBLER_HEADER\n";
   OS << "#undef GET_ASSEMBLER_HEADER\n";
   OS << "  // This should be included into the middle of the declaration of\n";
   OS << "  // your subclasses implementation of MCTargetAsmParser.\n";
   OS << "  uint64_t ComputeAvailableFeatures(const FeatureBitset& FB) const;\n";
   if (HasOptionalOperands) {
     OS << "  void convertToMCInst(unsigned Kind, MCInst &Inst, "
        << "unsigned Opcode,\n"
        << "                       const OperandVector &Operands,\n"
        << "                       const SmallBitVector &OptionalOperandsMask);\n";
   } else {
     OS << "  void convertToMCInst(unsigned Kind, MCInst &Inst, "
        << "unsigned Opcode,\n"
        << "                       const OperandVector &Operands);\n";
   }
   OS << "  void convertToMapAndConstraints(unsigned Kind,\n                ";
   OS << "           const OperandVector &Operands) override;\n";
   OS << "  unsigned MatchInstructionImpl(const OperandVector &Operands,\n"
-     << "                                MCInst &Inst,\n"
-     << "                                uint64_t &ErrorInfo,"
-     << " bool matchingInlineAsm,\n"
+     << "                                MCInst &Inst,\n";
+  if (ReportMultipleNearMisses)
+    OS << "                                SmallVectorImpl<NearMissInfo> *NearMisses,\n";
+  else
+    OS << "                                uint64_t &ErrorInfo,\n";
+  OS << "                                bool matchingInlineAsm,\n"
      << "                                unsigned VariantID = 0);\n";
 
   if (!Info.OperandMatchInfo.empty()) {
     OS << "  OperandMatchResultTy MatchOperandParserImpl(\n";
     OS << "    OperandVector &Operands,\n";
     OS << "    StringRef Mnemonic);\n";
 
     OS << "  OperandMatchResultTy tryCustomParseOperand(\n";
for (unsigned VC = 0; VC != VariantCount; ++VC) {
     OS << "};\n\n";
   }
 
   emitMnemonicSpellChecker(OS, Target, VariantCount);
 
   // Finally, build the match function.
   OS << "unsigned " << Target.getName() << ClassName << "::\n"
      << "MatchInstructionImpl(const OperandVector &Operands,\n";
-  OS << "                     MCInst &Inst, uint64_t &ErrorInfo,\n"
-     << "                     bool matchingInlineAsm, unsigned VariantID) {\n";
+  OS << "                     MCInst &Inst,\n";
+  if (ReportMultipleNearMisses)
+    OS << "                     SmallVectorImpl<NearMissInfo> *NearMisses,\n";
+  else
+    OS << "                     uint64_t &ErrorInfo,\n";
+  OS << "                     bool matchingInlineAsm, unsigned VariantID) {\n";
 
+  if (!ReportMultipleNearMisses) {
     OS << "  // Eliminate obvious mismatches.\n";
     OS << "  if (Operands.size() > "
        << (MaxNumOperands + HasMnemonicFirst) << ") {\n";
     OS << "    ErrorInfo = "
        << (MaxNumOperands + HasMnemonicFirst) << ";\n";
     OS << "    return Match_InvalidOperand;\n";
     OS << "  }\n\n";
+  }
 
   // Emit code to get the available features.
   OS << "  // Get the current feature set.\n";
   OS << "  uint64_t AvailableFeatures = getAvailableFeatures();\n\n";
 
   OS << "  // Get the instruction mnemonic, which is the first token.\n";
   if (HasMnemonicFirst) {
     OS << "  StringRef Mnemonic = ((" << Target.getName()
        << "Operand&)*Operands[0]).getToken();\n\n";
   } else {
     OS << "  StringRef Mnemonic;\n";
     OS << "  if (Operands[0]->isToken())\n";
     OS << "    Mnemonic = ((" << Target.getName()
        << "Operand&)*Operands[0]).getToken();\n\n";
   }
 
   if (HasMnemonicAliases) {
     OS << "  // Process all MnemonicAliases to remap the mnemonic.\n";
     OS << "  applyMnemonicAliases(Mnemonic, AvailableFeatures, VariantID);\n\n";
   }
 
   // Emit code to compute the class list for this operand vector.
+  if (!ReportMultipleNearMisses) {
     OS << "  // Some state to try to produce better error messages.\n";
     OS << "  bool HadMatchOtherThanFeatures = false;\n";
     OS << "  bool HadMatchOtherThanPredicate = false;\n";
     OS << "  unsigned RetCode = Match_InvalidOperand;\n";
     OS << "  uint64_t MissingFeatures = ~0ULL;\n";
-  if (HasOptionalOperands) {
-    OS << "  SmallBitVector OptionalOperandsMask(" << MaxNumOperands << ");\n";
-  }
     OS << "  // Set ErrorInfo to the operand that mismatches if it is\n";
     OS << "  // wrong for all instances of the instruction.\n";
     OS << "  ErrorInfo = ~0ULL;\n";
+  }
+
+  if (HasOptionalOperands) {
+    OS << "  SmallBitVector OptionalOperandsMask(" << MaxNumOperands << ");\n";
+  }
 
   // Emit code to search the table.
   OS << "  // Find the appropriate table for this asm variant.\n";
   OS << "  const MatchEntry *Start, *End;\n";
   OS << "  switch (VariantID) {\n";
   OS << "  default: llvm_unreachable(\"invalid variant!\");\n";
   for (unsigned VC = 0; VC != VariantCount; ++VC) {
     Record *AsmVariant = Target.getAsmParserVariant(VC);
#endif
   OS << "  // Return a more specific error code if no mnemonics match.\n";
   OS << "  if (MnemonicRange.first == MnemonicRange.second)\n";
   OS << "    return Match_MnemonicFail;\n\n";
 
   OS << "  for (const MatchEntry *it = MnemonicRange.first, "
      << "*ie = MnemonicRange.second;\n";
   OS << "       it != ie; ++it) {\n";
 
+  if (ReportMultipleNearMisses) {
+    OS << "    // Some state to record ways in which this instruction did not match.\n";
+    OS << "    NearMissInfo OperandNearMiss = NearMissInfo::getSuccess();\n";
+    OS << "    NearMissInfo FeaturesNearMiss = NearMissInfo::getSuccess();\n";
+    OS << "    NearMissInfo EarlyPredicateNearMiss = NearMissInfo::getSuccess();\n";
+    OS << "    NearMissInfo LatePredicateNearMiss = NearMissInfo::getSuccess();\n";
+    OS << "    bool MultipleInvalidOperands = false;\n";
+  }
+
   if (HasMnemonicFirst) {
     OS << "    // equal_range guarantees that instruction mnemonic matches.\n";
     OS << "    assert(Mnemonic == it->getMnemonic());\n";
   }
 
   // Emit check that the subclasses match.
+  if (!ReportMultipleNearMisses)
     OS << "    bool OperandsValid = true;\n";
   if (HasOptionalOperands) {
     OS << "    OptionalOperandsMask.reset(0, " << MaxNumOperands << ");\n";
   }
   OS << "    for (unsigned FormalIdx = " << (HasMnemonicFirst ? "0" : "SIndex")
      << ", ActualIdx = " << (HasMnemonicFirst ? "1" : "SIndex")
      << "; FormalIdx != " << MaxNumOperands << "; ++FormalIdx) {\n";
   OS << "      auto Formal = "
      << "static_cast<MatchClassKind>(it->Classes[FormalIdx]);\n";
   OS << "      if (ActualIdx >= Operands.size()) {\n";
-  OS << "        OperandsValid = (Formal == " <<"InvalidMatchClass) || "
+  if (ReportMultipleNearMisses) {
+    OS << "        bool ThisOperandValid = (Formal == " <<"InvalidMatchClass) || "
                                    "isSubclass(Formal, OptionalMatchClass);\n";
+    OS << "        if (!ThisOperandValid) {\n";
+    OS << "          if (!OperandNearMiss) {\n";
+    OS << "            // Record info about match failure for later use.\n";
+    OS << "            OperandNearMiss =\n";
+    OS << "                NearMissInfo::getTooFewOperands(Formal, it->Opcode);\n";
+    OS << "          } else {\n";
+    OS << "            // If more than one operand is invalid, give up on this match entry.\n";
+    OS << "            MultipleInvalidOperands = true;\n";
+    OS << "            break;\n";
+    OS << "          }\n";
+    OS << "        }\n";
+    OS << "        continue;\n";
+  } else {
+    OS << "        OperandsValid = (Formal == InvalidMatchClass) || isSubclass(Formal, OptionalMatchClass);\n";
     OS << "        if (!OperandsValid) ErrorInfo = ActualIdx;\n";
     if (HasOptionalOperands) {
       OS << "        OptionalOperandsMask.set(FormalIdx, " << MaxNumOperands
          << ");\n";
     }
     OS << "        break;\n";
+  }
   OS << "      }\n";
   OS << "      MCParsedAsmOperand &Actual = *Operands[ActualIdx];\n";
   OS << "      unsigned Diag = validateOperandClass(Actual, Formal);\n";
   OS << "      if (Diag == Match_Success) {\n";
   OS << "        ++ActualIdx;\n";
   OS << "        continue;\n";
   OS << "      }\n";
   OS << "      // If the generic handler indicates an invalid operand\n";
OS << "      // If current formal operand wasn't matched and it is optional\n"
      << "      // then try to match next formal operand\n";
   OS << "      if (Diag == Match_InvalidOperand "
      << "&& isSubclass(Formal, OptionalMatchClass)) {\n";
   if (HasOptionalOperands) {
     OS << "        OptionalOperandsMask.set(FormalIdx);\n";
   }
   OS << "        continue;\n";
   OS << "      }\n";
+
+  if (ReportMultipleNearMisses) {
+    OS << "      if (!OperandNearMiss) {\n";
+    OS << "        // If this is the first invalid operand we have seen, record some\n";
+    OS << "        // information about it.\n";
+    OS << "        OperandNearMiss =\n";
+    OS << "            NearMissInfo::getMissedOperand(Diag, Formal, it->Opcode, ActualIdx);\n";
+    OS << "        ++ActualIdx;\n";
+    OS << "      } else {\n";
+    OS << "        // If more than one operand is invalid, give up on this match entry.\n";
+    OS << "        MultipleInvalidOperands = true;\n";
+    OS << "        break;\n";
+    OS << "      }\n";
+    OS << "    }\n\n";
+  } else {
     OS << "      // If this operand is broken for all of the instances of this\n";
     OS << "      // mnemonic, keep track of it so we can report loc info.\n";
     OS << "      // If we already had a match that only failed due to a\n";
     OS << "      // target predicate, that diagnostic is preferred.\n";
     OS << "      if (!HadMatchOtherThanPredicate &&\n";
     OS << "          (it == MnemonicRange.first || ErrorInfo <= ActualIdx)) {\n";
     OS << "        ErrorInfo = ActualIdx;\n";
     OS << "        // InvalidOperand is the default. Prefer specificity.\n";
     OS << "        if (Diag != Match_InvalidOperand)\n";
     OS << "          RetCode = Diag;\n";
     OS << "      }\n";
     OS << "      // Otherwise, just reject this instance of the mnemonic.\n";
     OS << "      OperandsValid = false;\n";
     OS << "      break;\n";
     OS << "    }\n\n";
+  }
 
-  OS << "    if (!OperandsValid) continue;\n";
+  if (ReportMultipleNearMisses)
+    OS << "    if (MultipleInvalidOperands) continue;\n\n";
+  else
+    OS << "    if (!OperandsValid) continue;\n\n";
 
   // Emit check that the required features are available.
   OS << "    if ((AvailableFeatures & it->RequiredFeatures) "
      << "!= it->RequiredFeatures) {\n";
+  if (!ReportMultipleNearMisses)
     OS << "      HadMatchOtherThanFeatures = true;\n";
   OS << "      uint64_t NewMissingFeatures = it->RequiredFeatures & "
         "~AvailableFeatures;\n";
+  if (ReportMultipleNearMisses) {
+    OS << "      FeaturesNearMiss = NearMissInfo::getMissedFeature(NewMissingFeatures);\n";
+  } else {
     OS << "      if (countPopulation(NewMissingFeatures) <=\n"
           "          countPopulation(MissingFeatures))\n";
     OS << "        MissingFeatures = NewMissingFeatures;\n";
     OS << "      continue;\n";
+  }
   OS << "    }\n";
   OS << "\n";
   OS << "    Inst.clear();\n\n";
   OS << "    Inst.setOpcode(it->Opcode);\n";
   // Verify the instruction with the target-specific match predicate function.
   OS << "    // We have a potential match but have not rendered the operands.\n"
      << "    // Check the target predicate to handle any context sensitive\n"
         "    // constraints.\n"
      << "    // For example, Ties that are referenced multiple times must be\n"
         "    // checked here to ensure the input is the same for each match\n"
         "    // constraints. If we leave it any later the ties will have been\n"
         "    // canonicalized\n"
      << "    unsigned MatchResult;\n"
      << "    if ((MatchResult = checkEarlyTargetMatchPredicate(Inst, "
         "Operands)) != Match_Success) {\n"
-     << "      Inst.clear();\n"
-     << "      RetCode = MatchResult;\n"
+     << "      Inst.clear();\n";
+  if (ReportMultipleNearMisses) {
+    OS << "      EarlyPredicateNearMiss = NearMissInfo::getMissedPredicate(MatchResult);\n";
+  } else {
+    OS << "      RetCode = MatchResult;\n"
        << "      HadMatchOtherThanPredicate = true;\n"
-     << "      continue;\n"
-     << "    }\n\n";
+       << "      continue;\n";
+  }
+  OS << "    }\n\n";
+
+  if (ReportMultipleNearMisses) {
+    OS << "    // If we did not successfully match the operands, then we can't convert to\n";
+    OS << "    // an MCInst, so bail out on this instruction variant now.\n";
+    OS << "    if (OperandNearMiss) {\n";
+    OS << "      // If the operand mismatch was the only problem, reprrt it as a near-miss.\n";
+    OS << "      if (NearMisses && !FeaturesNearMiss && !EarlyPredicateNearMiss) {\n";
+    OS << "        NearMisses->push_back(OperandNearMiss);\n";
+    OS << "      }\n";
+    OS << "      continue;\n";
+    OS << "    }\n\n";
+  }
+
   OS << "    if (matchingInlineAsm) {\n";
   OS << "      convertToMapAndConstraints(it->ConvertFn, Operands);\n";
   OS << "      return Match_Success;\n";
   OS << "    }\n\n";
   OS << "    // We have selected a definite instruction, convert the parsed\n"
      << "    // operands into the appropriate MCInst.\n";
   if (HasOptionalOperands) {
     OS << "    convertToMCInst(it->ConvertFn, Inst, it->Opcode, Operands,\n"
        << "                    OptionalOperandsMask);\n";
   } else {
     OS << "    convertToMCInst(it->ConvertFn, Inst, it->Opcode, Operands);\n";
   }
   OS << "\n";
 
   // Verify the instruction with the target-specific match predicate function.
   OS << "    // We have a potential match. Check the target predicate to\n"
      << "    // handle any context sensitive constraints.\n"
      << "    if ((MatchResult = checkTargetMatchPredicate(Inst)) !="
      << " Match_Success) {\n"
-     << "      Inst.clear();\n"
-     << "      RetCode = MatchResult;\n"
+     << "      Inst.clear();\n";
+  if (ReportMultipleNearMisses) {
+    OS << "      LatePredicateNearMiss = NearMissInfo::getMissedPredicate(MatchResult);\n";
+  } else {
+    OS << "      RetCode = MatchResult;\n"
        << "      HadMatchOtherThanPredicate = true;\n"
-     << "      continue;\n"
-     << "    }\n\n";
+       << "      continue;\n";
+  }
+  OS << "    }\n\n";
+
+  if (ReportMultipleNearMisses) {
+    OS << "    int NumNearMisses = ((int)(bool)OperandNearMiss +\n";
+    OS << "                         (int)(bool)FeaturesNearMiss +\n";
+    OS << "                         (int)(bool)EarlyPredicateNearMiss +\n";
+    OS << "                         (int)(bool)LatePredicateNearMiss);\n";
+    OS << "    if (NumNearMisses == 1) {\n";
+    OS << "      // We had exactly one type of near-miss, so add that to the list.\n";
+    OS << "      assert(!OperandNearMiss && \"OperandNearMiss was handled earlier\");\n";
+    OS << "      if (NearMisses && FeaturesNearMiss)\n";
+    OS << "        NearMisses->push_back(FeaturesNearMiss);\n";
+    OS << "      else if (NearMisses && EarlyPredicateNearMiss)\n";
+    OS << "        NearMisses->push_back(EarlyPredicateNearMiss);\n";
+    OS << "      else if (NearMisses && LatePredicateNearMiss)\n";
+    OS << "        NearMisses->push_back(LatePredicateNearMiss);\n";
+    OS << "\n";
+    OS << "      continue;\n";
+    OS << "    } else if (NumNearMisses > 1) {\n";
+    OS << "      // This instruction missed in more than one way, so ignore it.\n";
+    OS << "      continue;\n";
+    OS << "    }\n";
+  }
 
   // Call the post-processing function, if used.
   StringRef InsnCleanupFn = AsmParser->getValueAsString("AsmParserInstCleanup");
   if (!InsnCleanupFn.empty())
     OS << "    " << InsnCleanupFn << "(Inst);\n";
 
   if (HasDeprecation) {
     OS << "    std::string Info;\n";
     OS << "    if (!getParser().getTargetParser().\n";
     OS << "        getTargetOptions().MCNoDeprecatedWarn &&\n";
     OS << "        MII.get(Inst.getOpcode()).getDeprecatedInfo(Inst, getSTI(), Info)) {\n";
     OS << "      SMLoc Loc = ((" << Target.getName()
        << "Operand&)*Operands[0]).getStartLoc();\n";
     OS << "      getParser().Warning(Loc, Info, None);\n";
     OS << "    }\n";
   }
 
   OS << "    return Match_Success;\n";
   OS << "  }\n\n";
 
+  if (ReportMultipleNearMisses) {
+    OS << "  // No instruction variants matched exactly.\n";
+    OS << "  return Match_NearMisses;\n";
+  } else {
     OS << "  // Okay, we had no match.  Try to return a useful error code.\n";
     OS << "  if (HadMatchOtherThanPredicate || !HadMatchOtherThanFeatures)\n";
     OS << "    return RetCode;\n\n";
     OS << "  // Missing feature matches return which features were missing\n";
     OS << "  ErrorInfo = MissingFeatures;\n";
     OS << "  return Match_MissingFeature;\n";
+  }
   OS << "}\n\n";
 
   if (!Info.OperandMatchInfo.empty())
     emitCustomOperandParsing(OS, Target, Info, ClassName, StringTable,
                              MaxMnemonicIndex, HasMnemonicFirst);
 
   OS << "#endif // GET_MATCHER_IMPLEMENTATION\n\n";
 }