diff --git a/llvm/lib/Support/X86TargetParser.cpp b/llvm/lib/Support/X86TargetParser.cpp
--- a/llvm/lib/Support/X86TargetParser.cpp
+++ b/llvm/lib/Support/X86TargetParser.cpp
@@ -114,6 +114,12 @@
   FeatureBitset ImpliedFeatures;
 };
 
+struct FlatFeatureDependency {
+  StringLiteral Name;
+  FeatureBitset ImpliedEnabledFeatures;
+  FeatureBitset ImpliedDisabledFeatures;
+};
+
 } // end anonymous namespace
 
 #define X86_FEATURE(ENUM, STRING)                                              \
@@ -536,6 +542,48 @@
 #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,
@@ -554,54 +602,24 @@
       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)