[RISCV] Sort the extensions in SupportedExtensions and SupportedExperimentalExtensions.

[craig.topper]

Summary

As the extension list continues to grow it probably makes sense
to use a binary search rather than linear search. Sorting the strings
will make this possible.

This also avoids any question about where to add new strings in
the tables.

[asb]

LGTM.

[jrtc27]

Can we have an expensive check that the table is sorted?

[craig.topper]

In D153170#4441462, @jrtc27 wrote:

Can we have an expensive check that the table is sorted?

Yeah. I was going to do it when I made use of the sorted property, but it makes more sense to be in this patch. I'll probably do it for asserts builds for a better chance of people catching the error before it goes to the build bots.

[craig.topper]

Verify the table is sorted. This uses the same pattern we use to check sorted tables in other places like X86InstrFMA3Info.cpp.

[asb]

OK, if this patch is going to verify the table is sorted then SupportedExtensions and SupportedExperimentalExtensions probably deserve a comment to explicitly note they must be kept in sort order. Otherwise, still LGTM.

clang/test/Driver/riscv-march-mcpu-mtune.c

 // MTUNE-E76-MCPU-E31: "-tune-cpu" "sifive-e76"
 
 // -mcpu and -march are given, so pipeline model take from -mcpu since -mtune is
 // not given, and arch ext. take from -march.
 // RUN: %clang --target=riscv32 -### -c %s -mcpu=sifive-e31 -march=rv32ic 2>&1 \
 // RUN:     | FileCheck -check-prefix=MCPU-E31-MARCH-RV32I %s
 // MCPU-E31-MARCH-RV32I: "-target-cpu" "sifive-e31"
 // MCPU-E31-MARCH-RV32I: "-target-feature" "+c"
-// MCPU-E31-MARCH-RV32I: "-target-feature" "-m"
 // MCPU-E31-MARCH-RV32I: "-target-feature" "-a"
 // MCPU-E31-MARCH-RV32I: "-target-feature" "-f"
+// MCPU-E31-MARCH-RV32I: "-target-feature" "-m"
 
 // -mcpu, -march and -mtune are given, so pipeline model take from -mtune
 // and arch ext. take from -march, -mcpu is unused.
 // RUN: %clang --target=riscv32 -### -c %s -mcpu=sifive-e31 -mtune=sifive-e76 -march=rv32ic 2>&1 \
 // RUN:     | FileCheck -check-prefix=MCPU-E31-MTUNE-E76-MARCH-RV32I %s
 // MCPU-E31-MTUNE-E76-MARCH-RV32I: "-target-cpu" "sifive-e31"
 // MCPU-E31-MTUNE-E76-MARCH-RV32I: "-target-feature" "+c"
-// MCPU-E31-MTUNE-E76-MARCH-RV32I: "-target-feature" "-m"
 // MCPU-E31-MTUNE-E76-MARCH-RV32I: "-target-feature" "-a"
 // MCPU-E31-MTUNE-E76-MARCH-RV32I: "-target-feature" "-f"
+// MCPU-E31-MTUNE-E76-MARCH-RV32I: "-target-feature" "-m"
 // MCPU-E31-MTUNE-E76-MARCH-RV32I: "-tune-cpu" "sifive-e76"

llvm/lib/Support/RISCVISAInfo.cpp

 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Errc.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/raw_ostream.h"
 
 #include <array>
+#include <atomic>
 #include <optional>
 #include <string>
 #include <vector>
 
 using namespace llvm;
 
 namespace {
 /// Represents the major and version number components of a RISC-V extension
 struct RISCVExtensionVersion {
   unsigned Major;
   unsigned Minor;
 };
 
 struct RISCVSupportedExtension {
   const char *Name;
   /// Supported version.
   RISCVExtensionVersion Version;
+
+  bool operator<(const RISCVSupportedExtension &RHS) const {
+    return StringRef(Name) < StringRef(RHS.Name);
+  }
 };
 
 } // end anonymous namespace
 
 static constexpr StringLiteral AllStdExts = "mafdqlcbkjtpvnh";
 
 static const char *RISCVGImplications[] = {
   "i", "m", "a", "f", "d", "zicsr", "zifencei"
 };
 
+// NOTE: This table should be sorted alphabetically by extension name.
 static const RISCVSupportedExtension SupportedExtensions[] = {
-    {"i", RISCVExtensionVersion{2, 1}},
-    {"e", RISCVExtensionVersion{2, 0}},
-    {"m", RISCVExtensionVersion{2, 0}},
     {"a", RISCVExtensionVersion{2, 1}},
-    {"f", RISCVExtensionVersion{2, 2}},
-    {"d", RISCVExtensionVersion{2, 2}},
     {"c", RISCVExtensionVersion{2, 0}},
-
+    {"d", RISCVExtensionVersion{2, 2}},
+    {"e", RISCVExtensionVersion{2, 0}},
+    {"f", RISCVExtensionVersion{2, 2}},
     {"h", RISCVExtensionVersion{1, 0}},
+    {"i", RISCVExtensionVersion{2, 1}},
+    {"m", RISCVExtensionVersion{2, 0}},
 
-    {"zihintpause", RISCVExtensionVersion{2, 0}},
+    {"svinval", RISCVExtensionVersion{1, 0}},
+    {"svnapot", RISCVExtensionVersion{1, 0}},
+    {"svpbmt", RISCVExtensionVersion{1, 0}},
+
+    {"v", RISCVExtensionVersion{1, 0}},
+
+    // vendor-defined ('X') extensions
+    {"xsfvcp", RISCVExtensionVersion{1, 0}},
+    {"xtheadba", RISCVExtensionVersion{1, 0}},
+    {"xtheadbb", RISCVExtensionVersion{1, 0}},
+    {"xtheadbs", RISCVExtensionVersion{1, 0}},
+    {"xtheadcmo", RISCVExtensionVersion{1, 0}},
+    {"xtheadcondmov", RISCVExtensionVersion{1, 0}},
+    {"xtheadfmemidx", RISCVExtensionVersion{1, 0}},
+    {"xtheadmac", RISCVExtensionVersion{1, 0}},
+    {"xtheadmemidx", RISCVExtensionVersion{1, 0}},
+    {"xtheadmempair", RISCVExtensionVersion{1, 0}},
+    {"xtheadsync", RISCVExtensionVersion{1, 0}},
+    {"xtheadvdot", RISCVExtensionVersion{1, 0}},
+    {"xventanacondops", RISCVExtensionVersion{1, 0}},
+
+    {"zawrs", RISCVExtensionVersion{1, 0}},
+
+    {"zba", RISCVExtensionVersion{1, 0}},
+    {"zbb", RISCVExtensionVersion{1, 0}},
+    {"zbc", RISCVExtensionVersion{1, 0}},
+    {"zbkb", RISCVExtensionVersion{1, 0}},
+    {"zbkc", RISCVExtensionVersion{1, 0}},
+    {"zbkx", RISCVExtensionVersion{1, 0}},
+    {"zbs", RISCVExtensionVersion{1, 0}},
 
     {"zca", RISCVExtensionVersion{1, 0}},
     {"zcb", RISCVExtensionVersion{1, 0}},
     {"zcd", RISCVExtensionVersion{1, 0}},
     {"zcf", RISCVExtensionVersion{1, 0}},
     {"zcmp", RISCVExtensionVersion{1, 0}},
     {"zcmt", RISCVExtensionVersion{1, 0}},
 
-    {"zfhmin", RISCVExtensionVersion{1, 0}},
-    {"zfh", RISCVExtensionVersion{1, 0}},
+    {"zdinx", RISCVExtensionVersion{1, 0}},
 
+    {"zfh", RISCVExtensionVersion{1, 0}},
+    {"zfhmin", RISCVExtensionVersion{1, 0}},
     {"zfinx", RISCVExtensionVersion{1, 0}},
-    {"zdinx", RISCVExtensionVersion{1, 0}},
-    {"zhinxmin", RISCVExtensionVersion{1, 0}},
+
     {"zhinx", RISCVExtensionVersion{1, 0}},
+    {"zhinxmin", RISCVExtensionVersion{1, 0}},
 
-    {"zba", RISCVExtensionVersion{1, 0}},
-    {"zbb", RISCVExtensionVersion{1, 0}},
-    {"zbc", RISCVExtensionVersion{1, 0}},
-    {"zbs", RISCVExtensionVersion{1, 0}},
+    {"zicbom", RISCVExtensionVersion{1, 0}},
+    {"zicbop", RISCVExtensionVersion{1, 0}},
+    {"zicboz", RISCVExtensionVersion{1, 0}},
+    {"zicntr", RISCVExtensionVersion{1, 0}},
+    {"zicsr", RISCVExtensionVersion{2, 0}},
+    {"zifencei", RISCVExtensionVersion{2, 0}},
+    {"zihintpause", RISCVExtensionVersion{2, 0}},
+    {"zihpm", RISCVExtensionVersion{1, 0}},
 
-    {"zbkb", RISCVExtensionVersion{1, 0}},
-    {"zbkc", RISCVExtensionVersion{1, 0}},
-    {"zbkx", RISCVExtensionVersion{1, 0}},
+    {"zk", RISCVExtensionVersion{1, 0}},
+    {"zkn", RISCVExtensionVersion{1, 0}},
     {"zknd", RISCVExtensionVersion{1, 0}},
     {"zkne", RISCVExtensionVersion{1, 0}},
     {"zknh", RISCVExtensionVersion{1, 0}},
-    {"zksed", RISCVExtensionVersion{1, 0}},
-    {"zksh", RISCVExtensionVersion{1, 0}},
     {"zkr", RISCVExtensionVersion{1, 0}},
-    {"zkn", RISCVExtensionVersion{1, 0}},
     {"zks", RISCVExtensionVersion{1, 0}},
+    {"zksed", RISCVExtensionVersion{1, 0}},
+    {"zksh", RISCVExtensionVersion{1, 0}},
     {"zkt", RISCVExtensionVersion{1, 0}},
-    {"zk", RISCVExtensionVersion{1, 0}},
 
     {"zmmul", RISCVExtensionVersion{1, 0}},
 
-    {"v", RISCVExtensionVersion{1, 0}},
-    {"zvl32b", RISCVExtensionVersion{1, 0}},
-    {"zvl64b", RISCVExtensionVersion{1, 0}},
-    {"zvl128b", RISCVExtensionVersion{1, 0}},
-    {"zvl256b", RISCVExtensionVersion{1, 0}},
-    {"zvl512b", RISCVExtensionVersion{1, 0}},
+    {"zve32f", RISCVExtensionVersion{1, 0}},
+    {"zve32x", RISCVExtensionVersion{1, 0}},
+    {"zve64d", RISCVExtensionVersion{1, 0}},
+    {"zve64f", RISCVExtensionVersion{1, 0}},
+    {"zve64x", RISCVExtensionVersion{1, 0}},
     {"zvl1024b", RISCVExtensionVersion{1, 0}},
-    {"zvl2048b", RISCVExtensionVersion{1, 0}},
-    {"zvl4096b", RISCVExtensionVersion{1, 0}},
-    {"zvl8192b", RISCVExtensionVersion{1, 0}},
+    {"zvl128b", RISCVExtensionVersion{1, 0}},
     {"zvl16384b", RISCVExtensionVersion{1, 0}},
+    {"zvl2048b", RISCVExtensionVersion{1, 0}},
+    {"zvl256b", RISCVExtensionVersion{1, 0}},
     {"zvl32768b", RISCVExtensionVersion{1, 0}},
+    {"zvl32b", RISCVExtensionVersion{1, 0}},
+    {"zvl4096b", RISCVExtensionVersion{1, 0}},
+    {"zvl512b", RISCVExtensionVersion{1, 0}},
+    {"zvl64b", RISCVExtensionVersion{1, 0}},
     {"zvl65536b", RISCVExtensionVersion{1, 0}},
-    {"zve32x", RISCVExtensionVersion{1, 0}},
-    {"zve32f", RISCVExtensionVersion{1, 0}},
-    {"zve64x", RISCVExtensionVersion{1, 0}},
-    {"zve64f", RISCVExtensionVersion{1, 0}},
-    {"zve64d", RISCVExtensionVersion{1, 0}},
-
-    {"zicbom", RISCVExtensionVersion{1, 0}},
-    {"zicboz", RISCVExtensionVersion{1, 0}},
-    {"zicbop", RISCVExtensionVersion{1, 0}},
-    {"zicntr", RISCVExtensionVersion{1, 0}},
-    {"zicsr", RISCVExtensionVersion{2, 0}},
-    {"zifencei", RISCVExtensionVersion{2, 0}},
-    {"zihpm", RISCVExtensionVersion{1, 0}},
-
-    {"zawrs", RISCVExtensionVersion{1, 0}},
-
-    {"svnapot", RISCVExtensionVersion{1, 0}},
-    {"svpbmt", RISCVExtensionVersion{1, 0}},
-    {"svinval", RISCVExtensionVersion{1, 0}},
-
-    // vendor-defined ('X') extensions
-    {"xsfvcp", RISCVExtensionVersion{1, 0}},
-    {"xtheadba", RISCVExtensionVersion{1, 0}},
-    {"xtheadbb", RISCVExtensionVersion{1, 0}},
-    {"xtheadbs", RISCVExtensionVersion{1, 0}},
-    {"xtheadcmo", RISCVExtensionVersion{1, 0}},
-    {"xtheadcondmov", RISCVExtensionVersion{1, 0}},
-    {"xtheadfmemidx", RISCVExtensionVersion{1, 0}},
-    {"xtheadmac", RISCVExtensionVersion{1, 0}},
-    {"xtheadmemidx", RISCVExtensionVersion{1, 0}},
-    {"xtheadmempair", RISCVExtensionVersion{1, 0}},
-    {"xtheadsync", RISCVExtensionVersion{1, 0}},
-    {"xtheadvdot", RISCVExtensionVersion{1, 0}},
-    {"xventanacondops", RISCVExtensionVersion{1, 0}},
+    {"zvl8192b", RISCVExtensionVersion{1, 0}},
 };
 
+// NOTE: This table should be sorted alphabetically by extension name.
 static const RISCVSupportedExtension SupportedExperimentalExtensions[] = {
     {"smaia", RISCVExtensionVersion{1, 0}},
     {"ssaia", RISCVExtensionVersion{1, 0}},
 
-    {"zihintntl", RISCVExtensionVersion{0, 2}},
-
     {"zfa", RISCVExtensionVersion{0, 2}},
     {"zfbfmin", RISCVExtensionVersion{0, 6}},
+
     {"zicond", RISCVExtensionVersion{1, 0}},
+
+    {"zihintntl", RISCVExtensionVersion{0, 2}},
+
+    {"ztso", RISCVExtensionVersion{0, 1}},
+
+    {"zvbb", RISCVExtensionVersion{0, 9}},
+    {"zvbc", RISCVExtensionVersion{0, 9}},
+
     {"zvfbfmin", RISCVExtensionVersion{0, 6}},
     {"zvfbfwma", RISCVExtensionVersion{0, 6}},
     {"zvfh", RISCVExtensionVersion{0, 1}},
-    {"ztso", RISCVExtensionVersion{0, 1}},
 
     // vector crypto
-    {"zvbb", RISCVExtensionVersion{0, 9}},
-    {"zvbc", RISCVExtensionVersion{0, 9}},
     {"zvkg", RISCVExtensionVersion{0, 9}},
     {"zvkn", RISCVExtensionVersion{0, 9}},
     {"zvknc", RISCVExtensionVersion{0, 9}},
     {"zvkned", RISCVExtensionVersion{0, 9}},
     {"zvkng", RISCVExtensionVersion{0, 9}},
     {"zvknha", RISCVExtensionVersion{0, 9}},
     {"zvknhb", RISCVExtensionVersion{0, 9}},
     {"zvks", RISCVExtensionVersion{0, 9}},
     {"zvksc", RISCVExtensionVersion{0, 9}},
     {"zvksed", RISCVExtensionVersion{0, 9}},
     {"zvksg", RISCVExtensionVersion{0, 9}},
     {"zvksh", RISCVExtensionVersion{0, 9}},
     {"zvkt", RISCVExtensionVersion{0, 9}},
 };
 
+static void verifyTables() {
+#ifndef NDEBUG
+  static std::atomic<bool> TableChecked(false);
+  if (!TableChecked.load(std::memory_order_relaxed)) {
+    assert(llvm::is_sorted(SupportedExtensions) &&
+           "Extensions are not sorted by name");
+    assert(llvm::is_sorted(SupportedExperimentalExtensions) &&
+           "Experimental extensions are not sorted by name");
+    TableChecked.store(true, std::memory_order_relaxed);
+  }
+#endif
+}
+
 static bool stripExperimentalPrefix(StringRef &Ext) {
   return Ext.consume_front("experimental-");
 }
 
 // This function finds the last character that doesn't belong to a version
 // (e.g. zba1p0 is extension 'zba' of version '1p0'). So the function will
 // consume [0-9]*p[0-9]* starting from the backward. An extension name will not
 // end with a digit or the letter 'p', so this function will parse correctly.
bool RISCVISAInfo::isSupportedExtensionFeature(StringRef Ext) {
 
   if (IsExperimental)
     return llvm::any_of(SupportedExperimentalExtensions, FindByName(Ext));
   else
     return llvm::any_of(SupportedExtensions, FindByName(Ext));
 }
 
 bool RISCVISAInfo::isSupportedExtension(StringRef Ext) {
+  verifyTables();
   return llvm::any_of(SupportedExtensions, FindByName(Ext)) ||
          llvm::any_of(SupportedExperimentalExtensions, FindByName(Ext));
 }
 
 bool RISCVISAInfo::isSupportedExtension(StringRef Ext, unsigned MajorVersion,
                                         unsigned MinorVersion) {
   auto FindByNameAndVersion = [=](const RISCVSupportedExtension &ExtInfo) {
     return ExtInfo.Name == Ext && (MajorVersion == ExtInfo.Version.Major) &&