[AsmParser] Mnemonic Spell Corrector

[SjoerdMeijer]

Summary

This implements a spell corrector to suggest another mnemonic when an invalid one is specified, for example:

$ echo "adXd r1,r2,#3" | llvm-mc -triple arm
<stdin>:1:1: error: invalid instruction, did you mean: add, qadd?
adXd r1,r2,#3
^

It is target agnostic, but as a first step I have added it only to the ARM backend.

[rengolin]

Hi Sjoerd,

I think this is a nice addition, and if we can trim all the duplication/public issues, the extra computation makes no difference, since this is going to run only when the compiler is on its way out.

The things I'd change from this, you probably already know, but just for completeness sake: :)

• Add the check functions to a cpp file, probably an already existing one that handles asm errors
• Keep things private, and if needed, maybe even duplicate the info (computation is not a problem here)
• Show what change you'd need to do to the original table (maybe a new column?), so we can see what would be the cost
• As you said, some tests would be nice

The only thing I worry here is that instructions rarely behave like text. So the Levenshtein distance may work for "addx -> add" but I'm expecting a lot of bad proposals, maybe enough to make the whole exercise worse than not having it.

This could be really nice if expanded to understand the operands, for example, and restrict to a subset (say, only opcodes that can use quad-regs), or something. In that case, the number of false positives would be lower and the quality of the proposals much better. But obviously, this wouldn't fit this patch.

So, if we have a plan to really make this target agnostic, but maybe with some target-hooks for the special filters, then I think it's a good idea. If the plan is to just use the Levenshtein distance, then it may be too much hassle.

Makes sense?

cheers,
--renato

[SjoerdMeijer]

Hi Renato,

Makes perfect sense, and thanks for looking into this. I will first start with making and adding tests to see if the suggestions are accurate. I've obviously tried it on a number of cases and the suggestions were spot on, but perhaps I've missed something. The outcome of this exercise will then show whether this is all worth it or not.

Cheers,
Sjoerd.

[SjoerdMeijer]

I am now reusing the already existing tablegen'ed MnemonicTable; so no need to introduce another one. That's the reason I've moved the algorithm to the tablegen'ed files, because that's where definitions/datastructures live.

Algorithmically I have made a few tweaks:

• it now returns a list of candidates/suggestions (rather than arbitrarily just the first one)
• to avoid giving useless suggestions, I have restricted to only consider candidates that are 2 edits away.

The added regression test should give a good impression what to expect from this patch and the given suggestions.

[sdardis]

This looks quite useful. One suggestion I have after playing around with this patch is to restrict the suggestions based on the available feature bits as that narrows the list of possibilities quite nicely.

[SjoerdMeijer]

Thanks! I've added the check for the available feature bits.
Also fixed the regression test that had some wrong tags.

[SjoerdMeijer]

Added a test case and a fix for checking supported architecture features.

[sdardis]

Nits inlined. Also you should update the summary.

Thanks,
Simon

test/MC/ARM/invalid-instructions.s

3

Add one line comment explaining that this is testing the mnemonic spell checker.

46

resuling -> resulting

utils/TableGen/AsmMatcherEmitter.cpp

2718

Add a string documenting this assertion such as "Empty string for assembly mnemoic!"

2765

"Edit distance.." -> "Candidates with an edit distance.."

[SjoerdMeijer]

Thanks Simon! I've addressed your comments. Also, I renamed the regression test to invalid-instructions-spellcheck.s just to be even more explicit about the purpose of the test.

[sdardis]

Sorry for missing this earlier, but the <Target>Operand class holds the mnemonic as a StringRef, and the matcher table ->getMnemonic() also returns a StringRef. Happily enough that class already has a edit_distance function: http://llvm.org/docs/doxygen/html/classllvm_1_1StringRef.html#a532f28c842d3728dc8f7e3c40949b33f

Thoughts on using that instead? It would avoid unnecessary std::string construction.

Thanks,
Simon

[SjoerdMeijer]

Oh wow, nice find! Completely missed that too. I am adding this, and that will simplify things a lot!

[SjoerdMeijer]

Now using StringRef and its edit_distance function.

[sdardis]

LGTM. We should see if @rengolin has any further comments.

utils/TableGen/AsmMatcherEmitter.cpp

2726

Space after the '//'.

2732

Space after the if.

[SjoerdMeijer]

Hi @rengolin, Simon had some great suggestions: using the architecture features to narrow down the number of candidates, and the use of the existing stringref edit distance function, which makes this now a fairly straightforward patch. Is it okay to commit this (with the last nits fixed)? Cheers.

[rengolin]

Hi Sjoerd,

Sorry for the delay. Yes, this looks simple enough and quite useful. LGTM.

Thanks!
--renato

lib/Target/ARM/AsmParser/ARMAsmParser.cpp

unsigned ARMAsmParser::MatchInstruction(OperandVector &Operands, MCInst &Inst,
   discardImplicitITBlock();
 
   // If none of these succeed, return the error we got when trying to match
   // outside any IT blocks.
   EmitInITBlock = false;
   return PlainMatchResult;
 }
 
+std::string ARMMnemonicSpellCheck(std::string S, uint64_t FBS);
+
 static const char *getSubtargetFeatureName(uint64_t Val);
 bool ARMAsmParser::MatchAndEmitInstruction(SMLoc IDLoc, unsigned &Opcode,
                                            OperandVector &Operands,
                                            MCStreamer &Out, uint64_t &ErrorInfo,
                                            bool MatchingInlineAsm) {
   MCInst Inst;
   unsigned MatchResult;
   bool PendConditionalInstruction = false;
if (ErrorInfo != ~0ULL) {
         return Error(IDLoc, "too few operands for instruction");
 
       ErrorLoc = ((ARMOperand &)*Operands[ErrorInfo]).getStartLoc();
       if (ErrorLoc == SMLoc()) ErrorLoc = IDLoc;
     }
 
     return Error(ErrorLoc, "invalid operand for instruction");
   }
-  case Match_MnemonicFail:
-    return Error(IDLoc, "invalid instruction",
+  case Match_MnemonicFail: {
+    uint64_t FBS = ComputeAvailableFeatures(getSTI().getFeatureBits());
+    std::string Suggestion = ARMMnemonicSpellCheck(
+      std::string(((ARMOperand &)*Operands[0]).getToken()), FBS);
+    return Error(IDLoc, "invalid instruction" + Suggestion,
                  ((ARMOperand &)*Operands[0]).getLocRange());
+  }
   case Match_RequiresNotITBlock:
     return Error(IDLoc, "flag setting instruction only valid outside IT block");
   case Match_RequiresITBlock:
     return Error(IDLoc, "instruction only valid inside IT block");
   case Match_RequiresV6:
     return Error(IDLoc, "instruction variant requires ARMv6 or later");
   case Match_RequiresThumb2:
     return Error(IDLoc, "instruction variant requires Thumb2");

test/MC/ARM/invalid-instructions.s

+@ RUN: not llvm-mc -triple=arm -show-encoding < %s 2>&1 | FileCheck %s
+@ RUN: not llvm-mc -triple=thumb -show-encoding < %s 2>&1 | FileCheck %s --check-prefix=CHECK-THUMB
+
+@ First check what happens when an instruction is omitted:
+
+  r1, r2, r3
+
+@ CHECK:      error: unexpected token in operand
+@ CHECK-NEXT: r1, r2, r3
+@ CHECK-NEXT:   ^
+
+@ We don't want to see a suggestion here; the edit distance is too large to
+@ give sensible suggestions:
+
+  aaaaaaaaaaaaaaa r1, r2, r3
+
+@ CHECK:      error: invalid instruction
+@ CHECK-NEXT: aaaaaaaaaaaaaaa r1, r2, r3
+@ CHECK-NEXT: ^
+
+@ Check that we get one suggestion: 'adXd' is 1 edit away, an insertion,
+@ from an alternative 'add':
+
+  adXd r1, r2, r3
+
+@ CHECK:      error: invalid instruction, did you mean: add?
+@ CHECK-NEXT: adXd r1, r2, r3
+@ CHECK-NEXT: ^
+
+@ Check edit distance 1, a deletion:
+
+  ad r1, r2, r3
+
+@ CHECK:      error: invalid instruction, did you mean: adc, add, adr, and?
+@ CHECK-NEXT: ad r1, r2, r3
+@ CHECK-NEXT: ^
+
+@ Let's check another one that is 1 edit away, an subsitution:
+
+  ldrea r1, r2, r3
+
+@ CHECK:      error: invalid instruction, did you mean: ldrex?
+@ CHECK-NEXT: ldrea r1, r2, r3
+@ CHECK-NEXT: ^
+
+@ Check an instruction that is 2 edits away, resuling in a number of suggestions:
+
+  ldre r1, r2, r3
+
+@ CHECK:      error: invalid instruction, did you mean: ldr, ldrb, ldrd, ldrex, ldrh, ldrt?
+@ CHECK-NEXT: ldre r1, r2, r3
+@ CHECK-NEXT: ^
+
+@ Here it is checked that we don't suggest instructions that are not supported.
+@ For example, in Thumb mode we don't want to see suggestions 'faddd' of 'qadd'
+@ because they are not supported.
+
+  fadd r1, r2, r3
+
+@ CHECK-THUMB: error: invalid instruction, did you mean: add?
+@ CHECK-THUMB: fadd r1, r2, r3
+@ CHECK-THUMB: ^
+
+@ CHECK:      error: invalid instruction, did you mean: add, qadd?
+@ CHECK-NEXT: fadd r1, r2, r3
+@ CHECK-NEXT: ^

utils/TableGen/AsmMatcherEmitter.cpp

static void emitCustomOperandParsing(raw_ostream &OS, CodeGenTarget &Target,
   OS << "      return Result;\n";
   OS << "  }\n\n";
 
   OS << "  // Okay, we had no match.\n";
   OS << "  return MatchOperand_NoMatch;\n";
   OS << "}\n\n";
 }
 
+static void emitMnemonicSpellChecker(raw_ostream &OS, CodeGenTarget &Target,
+                                     unsigned VariantCount) {
+  OS << "// Simple implementation of Levenshtein Distance calculation.\n";
+  OS << "static unsigned EditDistance(std::string S, std::string T) {\n";
+  OS << "  assert(S.size() && T.size());\n";
+  OS << "  const unsigned N = S.size() + 1;\n";
+  OS << "  const unsigned M = T.size() + 1;\n";
+  OS << "  std::vector<std::vector<unsigned> >Mat(M, std::vector<unsigned>(N));\n";
+  OS << "\n";
+  OS << "  for (unsigned i = 0; i<M; i++)\n";
+  OS << "    Mat[i][0] = i;\n";
+  OS << "  for (unsigned i = 0; i<N; i++)\n";
+  OS << "    Mat[0][i] = i;\n";
+  OS << "\n";
+  OS << "  auto Min = [] (unsigned N, unsigned M) { return N < M ? N : M; };\n";
+  OS << "  for (unsigned i = 1; i<N; i++) {\n";
+  OS << "    for (unsigned j = 1; j<M; j++) {\n";
+  OS << "      const unsigned Cost = S[i-1] == T[j-1] ? 0 : 1;\n";
+  OS << "      Mat[j][i] = Min(Mat[j-1][i] + 1, Min(Mat[j][i-1] + 1, Mat[j-1][i-1] + Cost));\n";
+  OS << "    }\n";
+  OS << "  }\n";
+  OS << "  return Mat[M-1][N-1];\n";
+  OS << "}\n";
+  OS << "\n";
+  OS << "std::string " << Target.getName() << "MnemonicSpellCheck(std::string S, uint64_t FBS) {\n";
+  if (!VariantCount)
+    OS <<  "  return \"\";";
+  else {
+    OS << "  unsigned MinDist = ~0;\n";
+    OS << "  std::vector<std::string> Candidates;\n";
+    OS << "  std::string Prev = \"\";\n";
+    OS << "  auto End = std::end(MatchTable0);\n";
+    OS << "\n";
+    OS << "  for (auto I = std::begin(MatchTable0); I < End; I++) {\n";
+    OS << "    if ((FBS & I->RequiredFeatures) != I->RequiredFeatures)\n";
+    OS << "      continue;\n";
+    OS << "    std::string T(I->getMnemonic().str());\n";
+    OS << "    // Avoid recomputing the edit distance for the same string.\n";
+    OS << "    if(T == Prev)\n";
+    OS << "      continue;\n";
+    OS << "\n";
+    OS << "    Prev = T;\n";
+    OS << "    unsigned Dist = EditDistance(S, T);\n";
+    OS << "    if (Dist < MinDist) {\n";
+    OS << "      Candidates.clear();\n";
+    OS << "      Candidates.push_back(T);\n";
+    OS << "      MinDist = Dist;\n";
+    OS << "    } else if (Dist == MinDist)\n";
+    OS << "      Candidates.push_back(T);\n";
+    OS << "  }\n";
+    OS << "\n";
+    OS << "  // Edit distance bigger than 2 are probably not useful suggestions.\n";
+    OS << "  if (MinDist > 2 || Candidates.empty())\n";
+    OS << "    return \"\";\n";
+    OS << "\n";
+    OS << "  std::string Res = \", did you mean: \";\n";
+    OS << "  unsigned i = 0;\n";
+    OS << "  for( ; i < Candidates.size() - 1; i++)\n";
+    OS << "    Res += Candidates[i] + \", \";\n";
+    OS << "  return Res + Candidates[i] + \"?\";\n";
+  }
+  OS << "}\n";
+  OS << "\n";
+}
+
+
 void AsmMatcherEmitter::run(raw_ostream &OS) {
   CodeGenTarget Target(Records);
   Record *AsmParser = Target.getAsmParser();
   StringRef ClassName = AsmParser->getValueAsString("AsmParserClassName");
 
   // Compute the information on the instructions to match.
   AsmMatcherInfo Info(AsmParser, Target, Records);
   Info.buildInfo();
for (const auto &MI : Info.Matchables) {
         OS << Op.Class->Name;
       }
       OS << " }, },\n";
     }
 
     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 << "  // Eliminate obvious mismatches.\n";
   OS << "  if (Operands.size() > "