Optimize OptTable::findNearest implementation and usage

[serge-sans-paille]

Summary

When used to find an exact match, some extra context can be used to
totally cut some computations.

This saves 1% of the instruction count when pre processing sqlite3.c
through

valgrind --tool=callgrind ./bin/clang -E sqlite3.c -o/dev/null

[nikic]

clang/lib/Driver/Driver.cpp

2475

I think this changes MinimumLength from the default of 4 to 0?

llvm/include/llvm/Option/OptTable.h

179

Shouldn't this be MaximumDistance?

llvm/lib/Option/OptTable.cpp

285

Should probably be ssize_t rather than signed?

[serge-sans-paille]

Thanks @nikic for the review. Remarks taken into account.

[nikic]

LGTM

[nikic]

FYI I just noticed some i686 failures that look something like this:

/builddir/build/BUILD/llvm-16.0.0.src/redhat-linux-build/unittests/Option/./OptionTests --gtest_filter=OptTableTest/0.FindNearest
--
/builddir/build/BUILD/llvm-16.0.0.src/unittests/Option/OptionParsingTest.cpp:314: Failure
Expected equality of these values:
  1U
    Which is: 1
  T.findNearest("-blorb", Nearest)
    Which is: 4294967295
/builddir/build/BUILD/llvm-16.0.0.src/unittests/Option/OptionParsingTest.cpp:315: Failure
Expected equality of these values:
  Nearest
    Which is: ""
  "-blorp"

Plausibly caused by this change -- I'm thinking that MaximumDistance is initialized to UINT_MAX - 1, but then we cast that to a signed integer and compare that, so it wraps to a large negative number.

[serge-sans-paille]

Plausibly caused by this change -- I'm thinking that MaximumDistance is initialized to UINT_MAX - 1, but then we cast that to a signed integer and compare that, so it wraps to a large negative number.

@nikic : I thought I fixed that with e8a163dc03e6913360beb305620104ba129c081c ... is it included in your build?

clang/lib/Driver/Driver.cpp

InputArgList Driver::ParseArgStrings(ArrayRef<const char *> ArgStrings,
   }
 
   for (const Arg *A : Args.filtered(options::OPT_UNKNOWN)) {
     unsigned DiagID;
     auto ArgString = A->getAsString(Args);
     std::string Nearest;
     if (getOpts().findNearest(ArgString, Nearest, IncludedFlagsBitmask,
                               ExcludedFlagsBitmask) > 1) {
-      if (getOpts().findNearest(ArgString, Nearest, options::CC1Option) == 0 &&
-          !IsCLMode()) {
+      if (!IsCLMode() &&
+          getOpts().findExact(ArgString, Nearest, options::CC1Option)) {
         DiagID = diag::err_drv_unknown_argument_with_suggestion;
         Diags.Report(DiagID) << ArgString << "-Xclang " + Nearest;
       } else {
         DiagID = IsCLMode() ? diag::warn_drv_unknown_argument_clang_cl
                             : diag::err_drv_unknown_argument;
         Diags.Report(DiagID) << ArgString;
       }
     } else {
       DiagID = IsCLMode()
                    ? diag::warn_drv_unknown_argument_clang_cl_with_suggestion
                    : diag::err_drv_unknown_argument_with_suggestion;
       Diags.Report(DiagID) << ArgString << Nearest;
     }
     ContainsError |= Diags.getDiagnosticLevel(DiagID, SourceLocation()) >
                      DiagnosticsEngine::Warning;
   }
 
   for (const Arg *A : Args.filtered(options::OPT_o)) {
     if (ArgStrings[A->getIndex()] == A->getSpelling())
       continue;
 
     // Warn on joined arguments that are similar to a long argument.
     std::string ArgString = ArgStrings[A->getIndex()];
     std::string Nearest;
-    if (getOpts().findNearest("-" + ArgString, Nearest, IncludedFlagsBitmask,
-                              ExcludedFlagsBitmask) == 0)
+    if (getOpts().findExact("-" + ArgString, Nearest, IncludedFlagsBitmask,
+                            ExcludedFlagsBitmask))
       Diags.Report(diag::warn_drv_potentially_misspelled_joined_argument)
           << A->getAsString(Args) << Nearest;
   }
 
   return Args;
 }
 
 // Determine which compilation mode we are in. We look for options which
if (TypoCorrect) {
     // the option `/diagnostics:caret` than a reference to a file in the root
     // directory.
     unsigned IncludedFlagsBitmask;
     unsigned ExcludedFlagsBitmask;
     std::tie(IncludedFlagsBitmask, ExcludedFlagsBitmask) =
         getIncludeExcludeOptionFlagMasks(IsCLMode());
     std::string Nearest;
     if (getOpts().findNearest(Value, Nearest, IncludedFlagsBitmask,
                               ExcludedFlagsBitmask) <= 1) {
       Diag(clang::diag::err_drv_no_such_file_with_suggestion)
           << Value << Nearest;
       return false;
     }
   }
 
   // In CL mode, don't error on apparently non-existent linker inputs, because
   // they can be influenced by linker flags the clang driver might not

llvm/include/llvm/Option/OptTable.h

public:
   /// OptTable.
   /// \param [in] FlagsToInclude - Only find options with any of these flags.
   /// Zero is the default, which includes all flags.
   /// \param [in] FlagsToExclude - Don't find options with this flag. Zero
   /// is the default, and means exclude nothing.
   /// \param [in] MinimumLength - Don't find options shorter than this length.
   /// For example, a minimum length of 3 prevents "-x" from being considered
   /// near to "-S".
+  /// \param [in] MaximumDistance - Don't find options whose distance is greater
+  /// than this value.
   ///
   /// \return The edit distance of the nearest string found.
   unsigned findNearest(StringRef Option, std::string &NearestString,
                        unsigned FlagsToInclude = 0, unsigned FlagsToExclude = 0,
-                       unsigned MinimumLength = 4) const;
+                       unsigned MinimumLength = 4,
+                       unsigned MaximumDistance = UINT_MAX - 1) const;
+
+  bool findExact(StringRef Option, std::string &ExactString,
+                 unsigned FlagsToInclude = 0,
+                 unsigned FlagsToExclude = 0) const {
+    return findNearest(Option, ExactString, FlagsToInclude, FlagsToExclude, 4,
+                       0) == 0;
+  }
 
   /// Parse a single argument; returning the new argument and
   /// updating Index.
   ///
   /// \param [in,out] Index - The current parsing position in the argument
   /// string list; on return this will be the index of the next argument
   /// string to parse.
   /// \param [in] FlagsToInclude - Only parse options with any of these flags.

llvm/lib/Option/OptTable.cpp

for (auto Prefix : In.Prefixes) {
         Ret.push_back(S);
     }
   }
   return Ret;
 }
 
 unsigned OptTable::findNearest(StringRef Option, std::string &NearestString,
                                unsigned FlagsToInclude, unsigned FlagsToExclude,
-                               unsigned MinimumLength) const {
+                               unsigned MinimumLength,
+                               unsigned MaximumDistance) const {
   assert(!Option.empty());
 
   // Consider each [option prefix + option name] pair as a candidate, finding
   // the closest match.
-  unsigned BestDistance = UINT_MAX;
+  unsigned BestDistance = MaximumDistance + 1;
   SmallString<16> Candidate;
   SmallString<16> NormalizedName;
 
   for (const Info &CandidateInfo :
        ArrayRef<Info>(OptionInfos).drop_front(FirstSearchableIndex)) {
     StringRef CandidateName = CandidateInfo.Name;
 
     // We can eliminate some option prefix/name pairs as candidates right away:
if (CandidateHasDelimiter) {
         NormalizedName += Last;
     } else
       NormalizedName = Option;
 
     // Consider each possible prefix for each candidate to find the most
     // appropriate one. For example, if a user asks for "--helm", suggest
     // "--help" over "-help".
     for (auto CandidatePrefix : CandidateInfo.Prefixes) {
+      // If Candidate and NormalizedName have more than 'BestDistance'
+      // characters of difference, no need to compute the edit distance, it's
+      // going to be greater than BestDistance. Don't bother computing Candidate
+      // at all.
+      if (std::abs((ssize_t)(CandidatePrefix.size() + CandidateName.size()) -
+                   (ssize_t)NormalizedName.size()) > (ssize_t)BestDistance) {
+        continue;
+      }
       Candidate = CandidatePrefix;
       Candidate += CandidateName;
       unsigned Distance = StringRef(Candidate).edit_distance(
           NormalizedName, /*AllowReplacements=*/true,
           /*MaxEditDistance=*/BestDistance);
       if (RHS.empty() && CandidateHasDelimiter) {
         // The Candidate ends with a = or : delimiter, but the option passed in
         // didn't contain the delimiter (or doesn't have anything after it).