[OptTable] Precompute OptTable prefixes union table through tablegen

This avoid rediscovering this table when reading each options, providing
a sensible 2% speedup when processing and empty file, and a measurable
speedup on typical workloads, see:

This is optional, the legacy, on-the-fly, approach can still be used
through the GenericOptTable class, while the new one is used through
PrecomputedOptTable.

https://llvm-compile-time-tracker.com/compare.php?from=4da6cb3202817ee2897d6b690e4af950459caea4&to=19a492b704e8f5c1dea120b9c0d3859bd78796be&stat=instructions:u

Differential Revision: https://reviews.llvm.org/D140800

24 files changed, 227 insertions, 121 deletions

diff --git a/llvm/include/llvm/Option/OptTable.h b/llvm/include/llvm/Option/OptTable.h
index 4933116..25d86c0 100644
--- a/llvm/include/llvm/Option/OptTable.h
+++ b/llvm/include/llvm/Option/OptTable.h
@@ -12,7 +12,6 @@
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringRef.h"
-#include "llvm/ADT/StringSet.h"
 #include "llvm/Option/OptSpecifier.h"
 #include "llvm/Support/StringSaver.h"
 #include <cassert>
@@ -68,14 +67,17 @@ private:
   unsigned InputOptionID = 0;
   unsigned UnknownOptionID = 0;
 
+protected:
   /// The index of the first option which can be parsed (i.e., is not a
   /// special option like 'input' or 'unknown', and is not an option group).
   unsigned FirstSearchableIndex = 0;
 
+  /// The union of the first element of all option prefixes.
+  SmallString<8> PrefixChars;
+
   /// The union of all option prefixes. If an argument does not begin with
   /// one of these, it is an input.
-  StringSet<> PrefixesUnion;
-  SmallString<8> PrefixChars;
+  virtual ArrayRef<StringLiteral> getPrefixesUnion() const = 0;
 
 private:
   const Info &getInfo(OptSpecifier Opt) const {
@@ -88,10 +90,15 @@ private:
                                           unsigned &Index) const;
 
 protected:
+  /// Initialize OptTable using Tablegen'ed OptionInfos. Child class must
+  /// manually call \c buildPrefixChars once they are fully constructed.
   OptTable(ArrayRef<Info> OptionInfos, bool IgnoreCase = false);
 
+  /// Build (or rebuild) the PrefixChars member.
+  void buildPrefixChars();
+
 public:
-  ~OptTable();
+  virtual ~OptTable();
 
   /// Return the total number of option classes.
   unsigned getNumOptions() const { return OptionInfos.size(); }
@@ -246,6 +253,32 @@ public:
                  bool ShowHidden = false, bool ShowAllAliases = false) const;
 };
 
+/// Specialization of OptTable
+class GenericOptTable : public OptTable {
+  SmallVector<StringLiteral> PrefixesUnionBuffer;
+
+protected:
+  GenericOptTable(ArrayRef<Info> OptionInfos, bool IgnoreCase = false);
+  ArrayRef<StringLiteral> getPrefixesUnion() const final {
+    return PrefixesUnionBuffer;
+  }
+};
+
+class PrecomputedOptTable : public OptTable {
+  ArrayRef<StringLiteral> PrefixesUnion;
+
+protected:
+  PrecomputedOptTable(ArrayRef<Info> OptionInfos,
+                      ArrayRef<StringLiteral> PrefixesTable,
+                      bool IgnoreCase = false)
+      : OptTable(OptionInfos, IgnoreCase), PrefixesUnion(PrefixesTable) {
+    buildPrefixChars();
+  }
+  ArrayRef<StringLiteral> getPrefixesUnion() const final {
+    return PrefixesUnion;
+  }
+};
+
 } // end namespace opt
 
 } // end namespace llvm
diff --git a/llvm/lib/ExecutionEngine/JITLink/COFFDirectiveParser.cpp b/llvm/lib/ExecutionEngine/JITLink/COFFDirectiveParser.cpp
index 70c5a2c..30c1579 100644
--- a/llvm/lib/ExecutionEngine/JITLink/COFFDirectiveParser.cpp
+++ b/llvm/lib/ExecutionEngine/JITLink/COFFDirectiveParser.cpp
@@ -27,6 +27,14 @@ using namespace jitlink;
 #include "COFFOptions.inc"
 #undef PREFIX
 
+static constexpr const StringLiteral PrefixTable_init[] =
+#define PREFIX_UNION(VALUES) VALUES
+#include "COFFOptions.inc"
+#undef PREFIX_UNION
+    ;
+static constexpr const ArrayRef<StringLiteral>
+    PrefixTable(PrefixTable_init, std::size(PrefixTable_init) - 1);
+
 // Create table mapping all options defined in COFFOptions.td
 static constexpr opt::OptTable::Info infoTable[] = {
 #define OPTION(X1, X2, ID, KIND, GROUP, ALIAS, X7, X8, X9, X10, X11, X12)      \
@@ -46,9 +54,9 @@ static constexpr opt::OptTable::Info infoTable[] = {
 #undef OPTION
 };
 
-class COFFOptTable : public opt::OptTable {
+class COFFOptTable : public opt::PrecomputedOptTable {
 public:
-  COFFOptTable() : OptTable(infoTable, true) {}
+  COFFOptTable() : PrecomputedOptTable(infoTable, PrefixTable, true) {}
 };
 
 static COFFOptTable optTable;
diff --git a/llvm/lib/Option/OptTable.cpp b/llvm/lib/Option/OptTable.cpp
index 49d56c0..dea9fc0 100644
--- a/llvm/lib/Option/OptTable.cpp
+++ b/llvm/lib/Option/OptTable.cpp
@@ -9,7 +9,6 @@
 #include "llvm/Option/OptTable.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringRef.h"
-#include "llvm/ADT/StringSet.h"
 #include "llvm/Option/Arg.h"
 #include "llvm/Option/ArgList.h"
 #include "llvm/Option/OptSpecifier.h"
@@ -23,6 +22,7 @@
 #include <cctype>
 #include <cstring>
 #include <map>
+#include <set>
 #include <string>
 #include <utility>
 #include <vector>
@@ -125,16 +125,13 @@ OptTable::OptTable(ArrayRef<Info> OptionInfos, bool IgnoreCase)
     }
   }
 #endif
+}
 
-  // Build prefixes.
-  for (unsigned i = FirstSearchableIndex + 1, e = getNumOptions() + 1;
-                i != e; ++i) {
-    const auto &P = getInfo(i).Prefixes;
-    PrefixesUnion.insert(P.begin(), P.end());
-  }
+void OptTable::buildPrefixChars() {
+  assert(PrefixChars.empty() && "rebuilding a non-empty prefix char");
 
   // Build prefix chars.
-  for (const StringRef &Prefix : PrefixesUnion.keys()) {
+  for (const StringLiteral &Prefix : getPrefixesUnion()) {
     for (char C : Prefix)
       if (!is_contained(PrefixChars, C))
         PrefixChars.push_back(C);
@@ -151,10 +148,10 @@ const Option OptTable::getOption(OptSpecifier Opt) const {
   return Option(&getInfo(id), this);
 }
 
-static bool isInput(const StringSet<> &Prefixes, StringRef Arg) {
+static bool isInput(const ArrayRef<StringLiteral> &Prefixes, StringRef Arg) {
   if (Arg == "-")
     return true;
-  for (const StringRef &Prefix : Prefixes.keys())
+  for (const StringRef &Prefix : Prefixes)
     if (Arg.startswith(Prefix))
       return false;
   return true;
@@ -236,6 +233,9 @@ unsigned OptTable::findNearest(StringRef Option, std::string &NearestString,
   // Consider each [option prefix + option name] pair as a candidate, finding
   // the closest match.
   unsigned BestDistance = UINT_MAX;
+  SmallString<16> Candidate;
+  SmallString<16> NormalizedName;
+
   for (const Info &CandidateInfo :
        ArrayRef<Info>(OptionInfos).drop_front(FirstSearchableIndex)) {
     StringRef CandidateName = CandidateInfo.Name;
@@ -243,7 +243,7 @@ unsigned OptTable::findNearest(StringRef Option, std::string &NearestString,
     // We can eliminate some option prefix/name pairs as candidates right away:
     // * Ignore option candidates with empty names, such as "--", or names
     //   that do not meet the minimum length.
-    if (CandidateName.empty() || CandidateName.size() < MinimumLength)
+    if (CandidateName.size() < MinimumLength)
       continue;
 
     // * If FlagsToInclude were specified, ignore options that don't include
@@ -262,26 +262,25 @@ unsigned OptTable::findNearest(StringRef Option, std::string &NearestString,
     // Now check if the candidate ends with a character commonly used when
     // delimiting an option from its value, such as '=' or ':'. If it does,
     // attempt to split the given option based on that delimiter.
-    StringRef LHS, RHS;
     char Last = CandidateName.back();
     bool CandidateHasDelimiter = Last == '=' || Last == ':';
-    std::string NormalizedName = std::string(Option);
+    StringRef RHS;
     if (CandidateHasDelimiter) {
-      std::tie(LHS, RHS) = Option.split(Last);
-      NormalizedName = std::string(LHS);
-      if (Option.find(Last) == LHS.size())
+      std::tie(NormalizedName, RHS) = Option.split(Last);
+      if (Option.find(Last) == NormalizedName.size())
         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) {
-      std::string Candidate = (CandidatePrefix + CandidateName).str();
-      StringRef CandidateRef = Candidate;
-      unsigned Distance =
-          CandidateRef.edit_distance(NormalizedName, /*AllowReplacements=*/true,
-                                     /*MaxEditDistance=*/BestDistance);
+      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).
@@ -310,7 +309,7 @@ std::unique_ptr<Arg> OptTable::parseOneArgGrouped(InputArgList &Args,
   // itself.
   const char *CStr = Args.getArgString(Index);
   StringRef Str(CStr);
-  if (isInput(PrefixesUnion, Str))
+  if (isInput(getPrefixesUnion(), Str))
     return std::make_unique<Arg>(getOption(InputOptionID), Str, Index++, CStr);
 
   const Info *End = OptionInfos.data() + OptionInfos.size();
@@ -375,7 +374,7 @@ std::unique_ptr<Arg> OptTable::ParseOneArg(const ArgList &Args, unsigned &Index,
 
   // Anything that doesn't start with PrefixesUnion is an input, as is '-'
   // itself.
-  if (isInput(PrefixesUnion, Str))
+  if (isInput(getPrefixesUnion(), Str))
     return std::make_unique<Arg>(getOption(InputOptionID), Str, Index++,
                                  Str.data());
 
@@ -653,3 +652,13 @@ void OptTable::printHelp(raw_ostream &OS, const char *Usage, const char *Title,
 
   OS.flush();
 }
+
+GenericOptTable::GenericOptTable(ArrayRef<Info> OptionInfos, bool IgnoreCase)
+    : OptTable(OptionInfos, IgnoreCase) {
+
+  std::set<StringLiteral> TmpPrefixesUnion;
+  for (auto const &Info : OptionInfos.drop_front(FirstSearchableIndex))
+    TmpPrefixesUnion.insert(Info.Prefixes.begin(), Info.Prefixes.end());
+  PrefixesUnionBuffer.append(TmpPrefixesUnion.begin(), TmpPrefixesUnion.end());
+  buildPrefixChars();
+}
diff --git a/llvm/lib/ToolDrivers/llvm-dlltool/DlltoolDriver.cpp b/llvm/lib/ToolDrivers/llvm-dlltool/DlltoolDriver.cpp
index 375c455..7d8bf2b 100644
--- a/llvm/lib/ToolDrivers/llvm-dlltool/DlltoolDriver.cpp
+++ b/llvm/lib/ToolDrivers/llvm-dlltool/DlltoolDriver.cpp
@@ -52,9 +52,9 @@ static constexpr opt::OptTable::Info InfoTable[] = {
 #undef OPTION
 };
 
-class DllOptTable : public llvm::opt::OptTable {
+class DllOptTable : public opt::GenericOptTable {
 public:
-  DllOptTable() : OptTable(InfoTable, false) {}
+  DllOptTable() : opt::GenericOptTable(InfoTable, false) {}
 };
 
 // Opens a file. Path has to be resolved already.
diff --git a/llvm/lib/ToolDrivers/llvm-lib/LibDriver.cpp b/llvm/lib/ToolDrivers/llvm-lib/LibDriver.cpp
index b0046e0..ade753a 100644
--- a/llvm/lib/ToolDrivers/llvm-lib/LibDriver.cpp
+++ b/llvm/lib/ToolDrivers/llvm-lib/LibDriver.cpp
@@ -56,11 +56,10 @@ static constexpr opt::OptTable::Info InfoTable[] = {
 #undef OPTION
 };
 
-class LibOptTable : public opt::OptTable {
+class LibOptTable : public opt::GenericOptTable {
 public:
-  LibOptTable() : OptTable(InfoTable, true) {}
+  LibOptTable() : opt::GenericOptTable(InfoTable, true) {}
 };
-
 }
 
 static std::string getDefaultOutputPath(const NewArchiveMember &FirstMember) {
diff --git a/llvm/tools/dsymutil/dsymutil.cpp b/llvm/tools/dsymutil/dsymutil.cpp
index b492ecb..75876a8 100644
--- a/llvm/tools/dsymutil/dsymutil.cpp
+++ b/llvm/tools/dsymutil/dsymutil.cpp
@@ -82,9 +82,9 @@ static constexpr opt::OptTable::Info InfoTable[] = {
 #undef OPTION
 };
 
-class DsymutilOptTable : public opt::OptTable {
+class DsymutilOptTable : public opt::GenericOptTable {
 public:
-  DsymutilOptTable() : OptTable(InfoTable) {}
+  DsymutilOptTable() : opt::GenericOptTable(InfoTable) {}
 };
 } // namespace
 
diff --git a/llvm/tools/llvm-cvtres/llvm-cvtres.cpp b/llvm/tools/llvm-cvtres/llvm-cvtres.cpp
index 2e32d14..9040237 100644
--- a/llvm/tools/llvm-cvtres/llvm-cvtres.cpp
+++ b/llvm/tools/llvm-cvtres/llvm-cvtres.cpp
@@ -63,9 +63,9 @@ static constexpr opt::OptTable::Info InfoTable[] = {
 #undef OPTION
 };
 
-class CvtResOptTable : public opt::OptTable {
+class CvtResOptTable : public opt::GenericOptTable {
 public:
-  CvtResOptTable() : OptTable(InfoTable, true) {}
+  CvtResOptTable() : opt::GenericOptTable(InfoTable, true) {}
 };
 }
 
diff --git a/llvm/tools/llvm-cxxfilt/llvm-cxxfilt.cpp b/llvm/tools/llvm-cxxfilt/llvm-cxxfilt.cpp
index c26049e..06f0a25 100644
--- a/llvm/tools/llvm-cxxfilt/llvm-cxxfilt.cpp
+++ b/llvm/tools/llvm-cxxfilt/llvm-cxxfilt.cpp
@@ -51,9 +51,11 @@ static constexpr opt::OptTable::Info InfoTable[] = {
 #undef OPTION
 };
 
-class CxxfiltOptTable : public opt::OptTable {
+class CxxfiltOptTable : public opt::GenericOptTable {
 public:
-  CxxfiltOptTable() : OptTable(InfoTable) { setGroupedShortOptions(true); }
+  CxxfiltOptTable() : opt::GenericOptTable(InfoTable) {
+    setGroupedShortOptions(true);
+  }
 };
 } // namespace
 
diff --git a/llvm/tools/llvm-dwarfutil/llvm-dwarfutil.cpp b/llvm/tools/llvm-dwarfutil/llvm-dwarfutil.cpp
index ed7e9f4..0e87c13 100644
--- a/llvm/tools/llvm-dwarfutil/llvm-dwarfutil.cpp
+++ b/llvm/tools/llvm-dwarfutil/llvm-dwarfutil.cpp
@@ -59,9 +59,9 @@ static constexpr opt::OptTable::Info InfoTable[] = {
 #undef OPTION
 };
 
-class DwarfutilOptTable : public opt::OptTable {
+class DwarfutilOptTable : public opt::GenericOptTable {
 public:
-  DwarfutilOptTable() : OptTable(InfoTable) {}
+  DwarfutilOptTable() : opt::GenericOptTable(InfoTable) {}
 };
 } // namespace
 
diff --git a/llvm/tools/llvm-ifs/llvm-ifs.cpp b/llvm/tools/llvm-ifs/llvm-ifs.cpp
index 0c85a1f..0ca9dfd 100644
--- a/llvm/tools/llvm-ifs/llvm-ifs.cpp
+++ b/llvm/tools/llvm-ifs/llvm-ifs.cpp
@@ -79,9 +79,11 @@ static constexpr opt::OptTable::Info InfoTable[] = {
 #undef OPTION
 };
 
-class IFSOptTable : public opt::OptTable {
+class IFSOptTable : public opt::GenericOptTable {
 public:
-  IFSOptTable() : OptTable(InfoTable) { setGroupedShortOptions(true); }
+  IFSOptTable() : opt::GenericOptTable(InfoTable) {
+    setGroupedShortOptions(true);
+  }
 };
 
 struct DriverConfig {
diff --git a/llvm/tools/llvm-lipo/llvm-lipo.cpp b/llvm/tools/llvm-lipo/llvm-lipo.cpp
index c161ef9..074a526 100644
--- a/llvm/tools/llvm-lipo/llvm-lipo.cpp
+++ b/llvm/tools/llvm-lipo/llvm-lipo.cpp
@@ -93,9 +93,9 @@ static constexpr opt::OptTable::Info LipoInfoTable[] = {
 };
 } // namespace lipo
 
-class LipoOptTable : public opt::OptTable {
+class LipoOptTable : public opt::GenericOptTable {
 public:
-  LipoOptTable() : OptTable(lipo::LipoInfoTable) {}
+  LipoOptTable() : opt::GenericOptTable(lipo::LipoInfoTable) {}
 };
 
 enum class LipoAction {
diff --git a/llvm/tools/llvm-ml/llvm-ml.cpp b/llvm/tools/llvm-ml/llvm-ml.cpp
index 2a81c9c..0af4854 100644
--- a/llvm/tools/llvm-ml/llvm-ml.cpp
+++ b/llvm/tools/llvm-ml/llvm-ml.cpp
@@ -79,9 +79,9 @@ static constexpr opt::OptTable::Info InfoTable[] = {
 #undef OPTION
 };
 
-class MLOptTable : public opt::OptTable {
+class MLOptTable : public opt::GenericOptTable {
 public:
-  MLOptTable() : OptTable(InfoTable, /*IgnoreCase=*/false) {}
+  MLOptTable() : opt::GenericOptTable(InfoTable, /*IgnoreCase=*/false) {}
 };
 } // namespace
 
diff --git a/llvm/tools/llvm-mt/llvm-mt.cpp b/llvm/tools/llvm-mt/llvm-mt.cpp
index 9b01c43..d460fd6 100644
--- a/llvm/tools/llvm-mt/llvm-mt.cpp
+++ b/llvm/tools/llvm-mt/llvm-mt.cpp
@@ -60,9 +60,9 @@ static constexpr opt::OptTable::Info InfoTable[] = {
 #undef OPTION
 };
 
-class CvtResOptTable : public opt::OptTable {
+class CvtResOptTable : public opt::GenericOptTable {
 public:
-  CvtResOptTable() : OptTable(InfoTable, true) {}
+  CvtResOptTable() : opt::GenericOptTable(InfoTable, true) {}
 };
 } // namespace
 
diff --git a/llvm/tools/llvm-nm/llvm-nm.cpp b/llvm/tools/llvm-nm/llvm-nm.cpp
index 649cee0c..55319d0e 100644
--- a/llvm/tools/llvm-nm/llvm-nm.cpp
+++ b/llvm/tools/llvm-nm/llvm-nm.cpp
@@ -83,9 +83,11 @@ static constexpr opt::OptTable::Info InfoTable[] = {
 #undef OPTION
 };
 
-class NmOptTable : public opt::OptTable {
+class NmOptTable : public opt::GenericOptTable {
 public:
-  NmOptTable() : OptTable(InfoTable) { setGroupedShortOptions(true); }
+  NmOptTable() : opt::GenericOptTable(InfoTable) {
+    setGroupedShortOptions(true);
+  }
 };
 
 enum OutputFormatTy { bsd, sysv, posix, darwin, just_symbols };
diff --git a/llvm/tools/llvm-objcopy/ObjcopyOptions.cpp b/llvm/tools/llvm-objcopy/ObjcopyOptions.cpp
index 3a970e2..577b837 100644
--- a/llvm/tools/llvm-objcopy/ObjcopyOptions.cpp
+++ b/llvm/tools/llvm-objcopy/ObjcopyOptions.cpp
@@ -56,9 +56,9 @@ static constexpr opt::OptTable::Info ObjcopyInfoTable[] = {
 };
 } // namespace objcopy_opt
 
-class ObjcopyOptTable : public opt::OptTable {
+class ObjcopyOptTable : public opt::GenericOptTable {
 public:
-  ObjcopyOptTable() : OptTable(objcopy_opt::ObjcopyInfoTable) {
+  ObjcopyOptTable() : opt::GenericOptTable(objcopy_opt::ObjcopyInfoTable) {
     setGroupedShortOptions(true);
   }
 };
@@ -101,10 +101,10 @@ static constexpr opt::OptTable::Info InstallNameToolInfoTable[] = {
 };
 } // namespace install_name_tool
 
-class InstallNameToolOptTable : public opt::OptTable {
+class InstallNameToolOptTable : public opt::GenericOptTable {
 public:
   InstallNameToolOptTable()
-      : OptTable(install_name_tool::InstallNameToolInfoTable) {}
+      : GenericOptTable(install_name_tool::InstallNameToolInfoTable) {}
 };
 
 enum BitcodeStripID {
@@ -145,9 +145,10 @@ static constexpr opt::OptTable::Info BitcodeStripInfoTable[] = {
 };
 } // namespace bitcode_strip
 
-class BitcodeStripOptTable : public opt::OptTable {
+class BitcodeStripOptTable : public opt::GenericOptTable {
 public:
-  BitcodeStripOptTable() : OptTable(bitcode_strip::BitcodeStripInfoTable) {}
+  BitcodeStripOptTable()
+      : opt::GenericOptTable(bitcode_strip::BitcodeStripInfoTable) {}
 };
 
 enum StripID {
@@ -179,9 +180,9 @@ static constexpr opt::OptTable::Info StripInfoTable[] = {
 };
 } // namespace strip
 
-class StripOptTable : public opt::OptTable {
+class StripOptTable : public opt::GenericOptTable {
 public:
-  StripOptTable() : OptTable(strip::StripInfoTable) {
+  StripOptTable() : GenericOptTable(strip::StripInfoTable) {
     setGroupedShortOptions(true);
   }
 };
diff --git a/llvm/tools/llvm-objdump/llvm-objdump.cpp b/llvm/tools/llvm-objdump/llvm-objdump.cpp
index bf8487b..4e78e26 100644
--- a/llvm/tools/llvm-objdump/llvm-objdump.cpp
+++ b/llvm/tools/llvm-objdump/llvm-objdump.cpp
@@ -97,18 +97,19 @@ using namespace llvm::opt;
 
 namespace {
 
-class CommonOptTable : public opt::OptTable {
+class CommonOptTable : public opt::GenericOptTable {
 public:
   CommonOptTable(ArrayRef<Info> OptionInfos, const char *Usage,
                  const char *Description)
-      : OptTable(OptionInfos), Usage(Usage), Description(Description) {
+      : opt::GenericOptTable(OptionInfos), Usage(Usage),
+        Description(Description) {
     setGroupedShortOptions(true);
   }
 
   void printHelp(StringRef Argv0, bool ShowHidden = false) const {
     Argv0 = sys::path::filename(Argv0);
-    opt::OptTable::printHelp(outs(), (Argv0 + Usage).str().c_str(), Description,
-                             ShowHidden, ShowHidden);
+    opt::GenericOptTable::printHelp(outs(), (Argv0 + Usage).str().c_str(),
+                                    Description, ShowHidden, ShowHidden);
     // TODO Replace this with OptTable API once it adds extrahelp support.
     outs() << "\nPass @FILE as argument to read options from FILE.\n";
   }
diff --git a/llvm/tools/llvm-rc/llvm-rc.cpp b/llvm/tools/llvm-rc/llvm-rc.cpp
index 6f7cc09..8e525bd 100644
--- a/llvm/tools/llvm-rc/llvm-rc.cpp
+++ b/llvm/tools/llvm-rc/llvm-rc.cpp
@@ -76,9 +76,9 @@ static constexpr opt::OptTable::Info InfoTable[] = {
 };
 } // namespace rc_opt
 
-class RcOptTable : public opt::OptTable {
+class RcOptTable : public opt::GenericOptTable {
 public:
-  RcOptTable() : OptTable(rc_opt::InfoTable, /* IgnoreCase = */ true) {}
+  RcOptTable() : GenericOptTable(rc_opt::InfoTable, /* IgnoreCase = */ true) {}
 };
 
 enum Windres_ID {
@@ -110,10 +110,10 @@ static constexpr opt::OptTable::Info InfoTable[] = {
 };
 } // namespace windres_opt
 
-class WindresOptTable : public opt::OptTable {
+class WindresOptTable : public opt::GenericOptTable {
 public:
   WindresOptTable()
-      : OptTable(windres_opt::InfoTable, /* IgnoreCase = */ false) {}
+      : GenericOptTable(windres_opt::InfoTable, /* IgnoreCase = */ false) {}
 };
 
 static ExitOnError ExitOnErr;
diff --git a/llvm/tools/llvm-readobj/llvm-readobj.cpp b/llvm/tools/llvm-readobj/llvm-readobj.cpp
index 89f6a89..a11de35 100644
--- a/llvm/tools/llvm-readobj/llvm-readobj.cpp
+++ b/llvm/tools/llvm-readobj/llvm-readobj.cpp
@@ -80,9 +80,11 @@ static constexpr opt::OptTable::Info InfoTable[] = {
 #undef OPTION
 };
 
-class ReadobjOptTable : public opt::OptTable {
+class ReadobjOptTable : public opt::GenericOptTable {
 public:
-  ReadobjOptTable() : OptTable(InfoTable) { setGroupedShortOptions(true); }
+  ReadobjOptTable() : opt::GenericOptTable(InfoTable) {
+    setGroupedShortOptions(true);
+  }
 };
 
 enum OutputFormatTy { bsd, sysv, posix, darwin, just_symbols };
diff --git a/llvm/tools/llvm-size/llvm-size.cpp b/llvm/tools/llvm-size/llvm-size.cpp
index 07fdab4..32dbf3d 100644
--- a/llvm/tools/llvm-size/llvm-size.cpp
+++ b/llvm/tools/llvm-size/llvm-size.cpp
@@ -66,9 +66,9 @@ static constexpr opt::OptTable::Info InfoTable[] = {
 #undef OPTION
 };
 
-class SizeOptTable : public opt::OptTable {
+class SizeOptTable : public opt::GenericOptTable {
 public:
-  SizeOptTable() : OptTable(InfoTable) { setGroupedShortOptions(true); }
+  SizeOptTable() : GenericOptTable(InfoTable) { setGroupedShortOptions(true); }
 };
 
 enum OutputFormatTy { berkeley, sysv, darwin };
diff --git a/llvm/tools/llvm-strings/llvm-strings.cpp b/llvm/tools/llvm-strings/llvm-strings.cpp
index 69a3b12..f6d08a1 100644
--- a/llvm/tools/llvm-strings/llvm-strings.cpp
+++ b/llvm/tools/llvm-strings/llvm-strings.cpp
@@ -58,9 +58,11 @@ static constexpr opt::OptTable::Info InfoTable[] = {
 #undef OPTION
 };
 
-class StringsOptTable : public opt::OptTable {
+class StringsOptTable : public opt::GenericOptTable {
 public:
-  StringsOptTable() : OptTable(InfoTable) { setGroupedShortOptions(true); }
+  StringsOptTable() : GenericOptTable(InfoTable) {
+    setGroupedShortOptions(true);
+  }
 };
 } // namespace
 
diff --git a/llvm/tools/llvm-symbolizer/llvm-symbolizer.cpp b/llvm/tools/llvm-symbolizer/llvm-symbolizer.cpp
index f38870c..1b86134 100644
--- a/llvm/tools/llvm-symbolizer/llvm-symbolizer.cpp
+++ b/llvm/tools/llvm-symbolizer/llvm-symbolizer.cpp
@@ -75,9 +75,9 @@ static constexpr opt::OptTable::Info InfoTable[] = {
 #undef OPTION
 };
 
-class SymbolizerOptTable : public opt::OptTable {
+class SymbolizerOptTable : public opt::GenericOptTable {
 public:
-  SymbolizerOptTable() : OptTable(InfoTable) {
+  SymbolizerOptTable() : GenericOptTable(InfoTable) {
     setGroupedShortOptions(true);
   }
 };
diff --git a/llvm/tools/llvm-tli-checker/llvm-tli-checker.cpp b/llvm/tools/llvm-tli-checker/llvm-tli-checker.cpp
index 1ac7189..179c42b 100644
--- a/llvm/tools/llvm-tli-checker/llvm-tli-checker.cpp
+++ b/llvm/tools/llvm-tli-checker/llvm-tli-checker.cpp
@@ -54,9 +54,9 @@ static constexpr opt::OptTable::Info InfoTable[] = {
 #undef OPTION
 };
 
-class TLICheckerOptTable : public opt::OptTable {
+class TLICheckerOptTable : public opt::GenericOptTable {
 public:
-  TLICheckerOptTable() : OptTable(InfoTable) {}
+  TLICheckerOptTable() : GenericOptTable(InfoTable) {}
 };
 } // end anonymous namespace
 
diff --git a/llvm/unittests/Option/OptionParsingTest.cpp b/llvm/unittests/Option/OptionParsingTest.cpp
index 19f68c0..9d1b46a 100644
--- a/llvm/unittests/Option/OptionParsingTest.cpp
+++ b/llvm/unittests/Option/OptionParsingTest.cpp
@@ -32,6 +32,14 @@ enum ID {
 #include "Opts.inc"
 #undef PREFIX
 
+static constexpr const StringLiteral PrefixTable_init[] =
+#define PREFIX_UNION(VALUES) VALUES
+#include "Opts.inc"
+#undef PREFIX_UNION
+    ;
+static constexpr const ArrayRef<StringLiteral>
+    PrefixTable(PrefixTable_init, std::size(PrefixTable_init) - 1);
+
 enum OptionFlags {
   OptFlag1 = (1 << 4),
   OptFlag2 = (1 << 5),
@@ -48,10 +56,16 @@ static constexpr OptTable::Info InfoTable[] = {
 };
 
 namespace {
-class TestOptTable : public OptTable {
+class TestOptTable : public GenericOptTable {
 public:
   TestOptTable(bool IgnoreCase = false)
-    : OptTable(InfoTable, IgnoreCase) {}
+      : GenericOptTable(InfoTable, IgnoreCase) {}
+};
+
+class TestPrecomputedOptTable : public PrecomputedOptTable {
+public:
+  TestPrecomputedOptTable(bool IgnoreCase = false)
+      : PrecomputedOptTable(InfoTable, PrefixTable, IgnoreCase) {}
 };
 }
 
@@ -67,8 +81,20 @@ const char *Args[] = {
   "-Gchuu", "2"
   };
 
-TEST(Option, OptionParsing) {
-  TestOptTable T;
+// Test fixture
+template <typename T> class OptTableTest : public ::testing::Test {};
+
+template <typename T> class DISABLED_OptTableTest : public ::testing::Test {};
+
+// Test both precomputed and computed OptTables with the same suite of tests.
+using OptTableTestTypes =
+    ::testing::Types<TestOptTable, TestPrecomputedOptTable>;
+
+TYPED_TEST_SUITE(OptTableTest, OptTableTestTypes, );
+TYPED_TEST_SUITE(DISABLED_OptTableTest, OptTableTestTypes, );
+
+TYPED_TEST(OptTableTest, OptionParsing) {
+  TypeParam T;
   unsigned MAI, MAC;
   InputArgList AL = T.ParseArgs(Args, MAI, MAC);
 
@@ -114,8 +140,8 @@ TEST(Option, OptionParsing) {
   EXPECT_EQ("desu", StringRef(ASL[1]));
 }
 
-TEST(Option, ParseWithFlagExclusions) {
-  TestOptTable T;
+TYPED_TEST(OptTableTest, ParseWithFlagExclusions) {
+  TypeParam T;
   unsigned MAI, MAC;
 
   // Exclude flag3 to avoid parsing as OPT_SLASH_C.
@@ -142,8 +168,8 @@ TEST(Option, ParseWithFlagExclusions) {
   EXPECT_EQ("bar", AL.getLastArgValue(OPT_C));
 }
 
-TEST(Option, ParseAliasInGroup) {
-  TestOptTable T;
+TYPED_TEST(OptTableTest, ParseAliasInGroup) {
+  TypeParam T;
   unsigned MAI, MAC;
 
   const char *MyArgs[] = { "-I" };
@@ -151,8 +177,8 @@ TEST(Option, ParseAliasInGroup) {
   EXPECT_TRUE(AL.hasArg(OPT_H));
 }
 
-TEST(Option, AliasArgs) {
-  TestOptTable T;
+TYPED_TEST(OptTableTest, AliasArgs) {
+  TypeParam T;
   unsigned MAI, MAC;
 
   const char *MyArgs[] = { "-J", "-Joo" };
@@ -162,8 +188,8 @@ TEST(Option, AliasArgs) {
   EXPECT_EQ("bar", AL.getAllArgValues(OPT_B)[1]);
 }
 
-TEST(Option, IgnoreCase) {
-  TestOptTable T(true);
+TYPED_TEST(OptTableTest, IgnoreCase) {
+  TypeParam T(true);
   unsigned MAI, MAC;
 
   const char *MyArgs[] = { "-a", "-joo" };
@@ -172,8 +198,8 @@ TEST(Option, IgnoreCase) {
   EXPECT_TRUE(AL.hasArg(OPT_B));
 }
 
-TEST(Option, DoNotIgnoreCase) {
-  TestOptTable T;
+TYPED_TEST(OptTableTest, DoNotIgnoreCase) {
+  TypeParam T;
   unsigned MAI, MAC;
 
   const char *MyArgs[] = { "-a", "-joo" };
@@ -182,8 +208,8 @@ TEST(Option, DoNotIgnoreCase) {
   EXPECT_FALSE(AL.hasArg(OPT_B));
 }
 
-TEST(Option, SlurpEmpty) {
-  TestOptTable T;
+TYPED_TEST(OptTableTest, SlurpEmpty) {
+  TypeParam T;
   unsigned MAI, MAC;
 
   const char *MyArgs[] = { "-A", "-slurp" };
@@ -193,8 +219,8 @@ TEST(Option, SlurpEmpty) {
   EXPECT_EQ(0U, AL.getAllArgValues(OPT_Slurp).size());
 }
 
-TEST(Option, Slurp) {
-  TestOptTable T;
+TYPED_TEST(OptTableTest, Slurp) {
+  TypeParam T;
   unsigned MAI, MAC;
 
   const char *MyArgs[] = { "-A", "-slurp", "-B", "--", "foo" };
@@ -209,8 +235,8 @@ TEST(Option, Slurp) {
   EXPECT_EQ("foo", AL.getAllArgValues(OPT_Slurp)[2]);
 }
 
-TEST(Option, SlurpJoinedEmpty) {
-  TestOptTable T;
+TYPED_TEST(OptTableTest, SlurpJoinedEmpty) {
+  TypeParam T;
   unsigned MAI, MAC;
 
   const char *MyArgs[] = { "-A", "-slurpjoined" };
@@ -220,8 +246,8 @@ TEST(Option, SlurpJoinedEmpty) {
   EXPECT_EQ(AL.getAllArgValues(OPT_SlurpJoined).size(), 0U);
 }
 
-TEST(Option, SlurpJoinedOneJoined) {
-  TestOptTable T;
+TYPED_TEST(OptTableTest, SlurpJoinedOneJoined) {
+  TypeParam T;
   unsigned MAI, MAC;
 
   const char *MyArgs[] = { "-A", "-slurpjoinedfoo" };
@@ -232,8 +258,8 @@ TEST(Option, SlurpJoinedOneJoined) {
   EXPECT_EQ(AL.getAllArgValues(OPT_SlurpJoined)[0], "foo");
 }
 
-TEST(Option, SlurpJoinedAndSeparate) {
-  TestOptTable T;
+TYPED_TEST(OptTableTest, SlurpJoinedAndSeparate) {
+  TypeParam T;
   unsigned MAI, MAC;
 
   const char *MyArgs[] = { "-A", "-slurpjoinedfoo", "bar", "baz" };
@@ -246,8 +272,8 @@ TEST(Option, SlurpJoinedAndSeparate) {
   EXPECT_EQ("baz", AL.getAllArgValues(OPT_SlurpJoined)[2]);
 }
 
-TEST(Option, SlurpJoinedButSeparate) {
-  TestOptTable T;
+TYPED_TEST(OptTableTest, SlurpJoinedButSeparate) {
+  TypeParam T;
   unsigned MAI, MAC;
 
   const char *MyArgs[] = { "-A", "-slurpjoined", "foo", "bar", "baz" };
@@ -260,8 +286,8 @@ TEST(Option, SlurpJoinedButSeparate) {
   EXPECT_EQ("baz", AL.getAllArgValues(OPT_SlurpJoined)[2]);
 }
 
-TEST(Option, FlagAliasToJoined) {
-  TestOptTable T;
+TYPED_TEST(OptTableTest, FlagAliasToJoined) {
+  TypeParam T;
   unsigned MAI, MAC;
 
   // Check that a flag alias provides an empty argument to a joined option.
@@ -273,8 +299,8 @@ TEST(Option, FlagAliasToJoined) {
   EXPECT_EQ("", AL.getAllArgValues(OPT_B)[0]);
 }
 
-TEST(Option, FindNearest) {
-  TestOptTable T;
+TYPED_TEST(OptTableTest, FindNearest) {
+  TypeParam T;
   std::string Nearest;
 
   // Options that are too short should not be considered
@@ -324,8 +350,8 @@ TEST(Option, FindNearest) {
   EXPECT_EQ(Nearest, "-doopf1");
 }
 
-TEST(DISABLED_Option, FindNearestFIXME) {
-  TestOptTable T;
+TYPED_TEST(DISABLED_OptTableTest, FindNearestFIXME) {
+  TypeParam T;
   std::string Nearest;
 
   // FIXME: Options with joined values should not have those values considered
@@ -333,11 +359,10 @@ TEST(DISABLED_Option, FindNearestFIXME) {
   // succeed.
   EXPECT_EQ(1U, T.findNearest("--erbghFoo", Nearest));
   EXPECT_EQ(Nearest, "--ermghFoo");
-
 }
 
-TEST(Option, ParseGroupedShortOptions) {
-  TestOptTable T;
+TYPED_TEST(OptTableTest, ParseGroupedShortOptions) {
+  TypeParam T;
   T.setGroupedShortOptions(true);
   unsigned MAI, MAC;
 
@@ -366,8 +391,8 @@ TEST(Option, ParseGroupedShortOptions) {
   EXPECT_TRUE(AL3.hasArg(OPT_Blorp));
 }
 
-TEST(Option, UnknownOptions) {
-  TestOptTable T;
+TYPED_TEST(OptTableTest, UnknownOptions) {
+  TypeParam T;
   unsigned MAI, MAC;
   const char *Args[] = {"-u", "--long", "0"};
   for (int I = 0; I < 2; ++I) {
@@ -380,8 +405,8 @@ TEST(Option, UnknownOptions) {
   }
 }
 
-TEST(Option, FlagsWithoutValues) {
-  TestOptTable T;
+TYPED_TEST(OptTableTest, FlagsWithoutValues) {
+  TypeParam T;
   T.setGroupedShortOptions(true);
   unsigned MAI, MAC;
   const char *Args[] = {"-A=1", "-A="};
@@ -392,8 +417,8 @@ TEST(Option, FlagsWithoutValues) {
   EXPECT_EQ("-A=", Unknown[1]);
 }
 
-TEST(Option, UnknownGroupedShortOptions) {
-  TestOptTable T;
+TYPED_TEST(OptTableTest, UnknownGroupedShortOptions) {
+  TypeParam T;
   T.setGroupedShortOptions(true);
   unsigned MAI, MAC;
   const char *Args[] = {"-AuzK", "-AuzK"};
diff --git a/llvm/utils/TableGen/OptParserEmitter.cpp b/llvm/utils/TableGen/OptParserEmitter.cpp
index b897843..d363191 100644
--- a/llvm/utils/TableGen/OptParserEmitter.cpp
+++ b/llvm/utils/TableGen/OptParserEmitter.cpp
@@ -237,8 +237,14 @@ void EmitOptParser(RecordKeeper &Records, raw_ostream &OS) {
       CurPrefix = NewPrefix;
   }
 
-  // Dump prefixes.
+  DenseSet<StringRef> PrefixesUnionSet;
+  for (const auto &Prefix : Prefixes)
+    PrefixesUnionSet.insert(Prefix.first.begin(), Prefix.first.end());
+  SmallVector<StringRef> PrefixesUnion(PrefixesUnionSet.begin(),
+                                       PrefixesUnionSet.end());
+  array_pod_sort(PrefixesUnion.begin(), PrefixesUnion.end());
 
+  // Dump prefixes.
   OS << "/////////\n";
   OS << "// Prefixes\n\n";
   OS << "#ifdef PREFIX\n";
@@ -259,6 +265,20 @@ void EmitOptParser(RecordKeeper &Records, raw_ostream &OS) {
   OS << "#undef COMMA\n";
   OS << "#endif // PREFIX\n\n";
 
+  // Dump prefix unions.
+  OS << "/////////\n";
+  OS << "// Prefix Union\n\n";
+  OS << "#ifdef PREFIX_UNION\n";
+  OS << "#define COMMA ,\n";
+  OS << "PREFIX_UNION({\n";
+  for (const auto &Prefix : PrefixesUnion) {
+    OS << "llvm::StringLiteral(\"" << Prefix << "\") COMMA ";
+  }
+  OS << "llvm::StringLiteral(\"\")})\n";
+  OS << "#undef COMMA\n";
+  OS << "#endif // PREFIX_UNION\n\n";
+
+  // Dump groups.
   OS << "/////////\n";
   OS << "// ValuesCode\n\n";
   OS << "#ifdef OPTTABLE_VALUES_CODE\n";