[X86] Flatten feature dependency tree at compile-time

[Nathan-Huckleberry]

Summary

Using constexpr we can flatten the feature dependency tree at
compile-time so that no computation is required at run-time.

[craig.topper]

llvm/lib/Support/X86TargetParser.cpp

581

Doesn't this violate the no global constructor rule?

[Nathan-Huckleberry]

llvm/lib/Support/X86TargetParser.cpp

581

Oh yikes, yes it does. I tried making the map a function level static variable, but this code is apparently called by multiple threads in some cases so we run into race condition.

Should I switch to a static array and just do a linear search through the array?

[Nathan-Huckleberry]

Change dependency map to constexpr array to avoid global constructor

[Nathan-Huckleberry]

Change dependency map to constexpr array to avoid global constructor

[craig.topper]

Do you have compile time numbers for this after https://reviews.llvm.org/D85807 ?

llvm/lib/Support/X86TargetParser.cpp

583

I've never seen COUNTER before. Is it supported by all the compilers we support. I couldn't find other uses in tree.

[void]

llvm/lib/Support/X86TargetParser.cpp

583

It is. I believe it's a GNU C feature. But it's heavily used in Linux.

llvm/lib/Support/X86TargetParser.cpp

struct ProcInfo {
   FeatureBitset Features;
 };
 
 struct FeatureInfo {
   StringLiteral Name;
   FeatureBitset ImpliedFeatures;
 };
 
+struct FlatFeatureDependency {
+  StringLiteral Name;
+  FeatureBitset ImpliedEnabledFeatures;
+  FeatureBitset ImpliedDisabledFeatures;
+};
+
 } // end anonymous namespace
 
 #define X86_FEATURE(ENUM, STRING)                                              \
   static constexpr FeatureBitset Feature##ENUM = {X86::FEATURE_##ENUM};
 #include "llvm/Support/X86TargetParser.def"
 
 // Pentium with MMX.
 static constexpr FeatureBitset FeaturesPentiumMMX =

 static constexpr FeatureBitset ImpliedFeaturesAMX_BF16 = FeatureAMX_TILE;
 static constexpr FeatureBitset ImpliedFeaturesAMX_INT8 = FeatureAMX_TILE;
 
 static constexpr FeatureInfo FeatureInfos[X86::CPU_FEATURE_MAX] = {
 #define X86_FEATURE(ENUM, STR) {{STR}, ImpliedFeatures##ENUM},
 #include "llvm/Support/X86TargetParser.def"
 };
 
+static constexpr FeatureBitset ImpliedEnabledFeatures(FeatureBitset Implies) {
+  FeatureBitset Bits;
+  Bits |= Implies;
+  for (unsigned i = 0; i != CPU_FEATURE_MAX; ++i) {
+    if (Implies[i])
+      Bits |= ImpliedEnabledFeatures(FeatureInfos[i].ImpliedFeatures);
+  }
+  return Bits;
+}
+
+static constexpr FeatureBitset ImpliedDisabledFeatures(unsigned Value) {
+  FeatureBitset Bits;
+  // Check all features looking for any dependent on this feature. If we find
+  // one, mark it and recursively find any feature that depend on it.
+  for (unsigned i = 0; i != CPU_FEATURE_MAX; ++i) {
+    if (FeatureInfos[i].ImpliedFeatures[Value]) {
+      Bits.set(i);
+      Bits |= ImpliedDisabledFeatures(i);
+    }
+  }
+  return Bits;
+}
+
+// Traverse the dependency tree at compile time so we don't need to recompute at
+// runtime.
+static constexpr FlatFeatureDependency
+FlattenFeatureDependencies(unsigned Index) {
+  auto I = FeatureInfos[Index];
+  FeatureBitset ImpliedEnabled =
+      ImpliedEnabledFeatures(I.ImpliedFeatures) | FeatureBitset().set(Index);
+  FeatureBitset ImpliedDisabled =
+      ImpliedDisabledFeatures(Index) | FeatureBitset().set(Index);
+
+  return {I.Name, ImpliedEnabled, ImpliedDisabled};
+}
+
+static constexpr FlatFeatureDependency
+    FeatureDependencies[X86::CPU_FEATURE_MAX] = {
+#define X86_FEATURE(ENUM, STR) FlattenFeatureDependencies(__COUNTER__),
+#include "llvm/Support/X86TargetParser.def"
+};
+
 void llvm::X86::getFeaturesForCPU(StringRef CPU,
                                   SmallVectorImpl<StringRef> &EnabledFeatures) {
   auto I = llvm::find_if(Processors,
                          [&](const ProcInfo &P) { return P.Name == CPU; });
   assert(I != std::end(Processors) && "Processor not found!");
 
   FeatureBitset Bits = I->Features;
 
   // Remove the 64-bit feature which we only use to validate if a CPU can
   // be used with 64-bit mode.
   Bits &= ~Feature64BIT;
 
   // Add the string version of all set bits.
   for (unsigned i = 0; i != CPU_FEATURE_MAX; ++i)
     if (Bits[i] && !FeatureInfos[i].Name.empty())
       EnabledFeatures.push_back(FeatureInfos[i].Name);
 }
 
-// For each feature that is (transitively) implied by this feature, set it.
-static void getImpliedEnabledFeatures(FeatureBitset &Bits,
-                                      const FeatureBitset &Implies) {
-  // Fast path: Implies is often empty.
-  if (!Implies.any())
-    return;
-  FeatureBitset Prev;
-  Bits |= Implies;
-  do {
-    Prev = Bits;
-    for (unsigned i = CPU_FEATURE_MAX; i;)
-      if (Bits[--i])
-        Bits |= FeatureInfos[i].ImpliedFeatures;
-  } while (Prev != Bits);
-}
-
-/// Create bit vector of features that are implied disabled if the feature
-/// passed in Value is disabled.
-static void getImpliedDisabledFeatures(FeatureBitset &Bits, unsigned Value) {
-  // Check all features looking for any dependent on this feature. If we find
-  // one, mark it and recursively find any feature that depend on it.
-  FeatureBitset Prev;
-  Bits.set(Value);
-  do {
-    Prev = Bits;
-    for (unsigned i = 0; i != CPU_FEATURE_MAX; ++i)
-      if ((FeatureInfos[i].ImpliedFeatures & Bits).any())
-        Bits.set(i);
-  } while (Prev != Bits);
-}
-
 void llvm::X86::updateImpliedFeatures(
     StringRef Feature, bool Enabled,
     StringMap<bool> &Features) {
-  auto I = llvm::find_if(
-      FeatureInfos, [&](const FeatureInfo &FI) { return FI.Name == Feature; });
-  if (I == std::end(FeatureInfos)) {
+
+  FeatureBitset ImpliedBits;
+  auto D =
+      llvm::find_if(FeatureDependencies, [&](const FlatFeatureDependency &FD) {
+        return FD.Name == Feature;
+      });
+  if (D == std::end(FeatureDependencies)) {
     // FIXME: This shouldn't happen, but may not have all features in the table
     // yet.
     return;
   }
-
-  FeatureBitset ImpliedBits;
   if (Enabled)
-    getImpliedEnabledFeatures(ImpliedBits, I->ImpliedFeatures);
+    ImpliedBits = D->ImpliedEnabledFeatures;
   else
-    getImpliedDisabledFeatures(ImpliedBits,
-                               std::distance(std::begin(FeatureInfos), I));
+    ImpliedBits = D->ImpliedDisabledFeatures;
 
   // Update the map entry for all implied features.
   for (unsigned i = 0; i != CPU_FEATURE_MAX; ++i)
     if (ImpliedBits[i] && !FeatureInfos[i].Name.empty())
       Features[FeatureInfos[i].Name] = Enabled;
 }