diff --git a/llvm/include/llvm/Frontend/OpenMP/OMPContext.h b/llvm/include/llvm/Frontend/OpenMP/OMPContext.h
--- a/llvm/include/llvm/Frontend/OpenMP/OMPContext.h
+++ b/llvm/include/llvm/Frontend/OpenMP/OMPContext.h
@@ -16,6 +16,7 @@
 #define LLVM_OPENMP_CONTEXT_H
 
 #include "llvm/ADT/APSInt.h"
+#include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/Triple.h"
@@ -44,6 +45,7 @@
 enum class TraitProperty {
 #define OMP_TRAIT_PROPERTY(Enum, ...) Enum,
 #include "llvm/Frontend/OpenMP/OMPKinds.def"
+NUM_PROPERTIES
 };
 
 /// Parse \p Str and return the trait set it matches or TraitSet::invalid.
@@ -122,12 +124,12 @@
   void addTrait(TraitSet Set, TraitProperty Property, APInt *Score = nullptr) {
     if (Score)
       ScoreMap[Property] = *Score;
-    RequiredTraits.insert(Property);
+    RequiredTraits.set(unsigned(Property));
     if (Set == TraitSet::construct)
       ConstructTraits.push_back(Property);
   }
 
-  SmallSet<TraitProperty, 8> RequiredTraits;
+  BitVector RequiredTraits = BitVector(unsigned(TraitProperty::NUM_PROPERTIES));
   SmallVector<TraitProperty, 8> ConstructTraits;
   SmallDenseMap<TraitProperty, APInt> ScoreMap;
 };
diff --git a/llvm/lib/Frontend/OpenMP/OMPContext.cpp b/llvm/lib/Frontend/OpenMP/OMPContext.cpp
--- a/llvm/lib/Frontend/OpenMP/OMPContext.cpp
+++ b/llvm/lib/Frontend/OpenMP/OMPContext.cpp
@@ -122,15 +122,22 @@
   // If all required traits are a strict subset and the ordered vectors storing
   // the construct traits, we say it is a strict subset. Note that the latter
   // relation is not required to be strict.
-  return set_is_strict_subset(VMI0.RequiredTraits, VMI1.RequiredTraits) &&
-         isSubset<TraitProperty>(VMI0.ConstructTraits, VMI1.ConstructTraits);
+  if (VMI0.RequiredTraits.count() >= VMI1.RequiredTraits.count())
+    return false;
+  for (const auto &SetBitsIt : VMI0.RequiredTraits.set_bits())
+    if (!VMI1.RequiredTraits.test(SetBitsIt))
+        return false;
+  if (!isSubset<TraitProperty>(VMI0.ConstructTraits, VMI1.ConstructTraits))
+    return false;
+  return true;
 }
 
 static int isVariantApplicableInContextHelper(
     const VariantMatchInfo &VMI, const OMPContext &Ctx,
     SmallVectorImpl<unsigned> *ConstructMatches) {
 
-  for (TraitProperty Property : VMI.RequiredTraits) {
+  for (const auto &SetBitsIt : VMI.RequiredTraits.set_bits()) {
+    TraitProperty Property = TraitProperty(SetBitsIt);
 
     bool IsActiveTrait = Ctx.ActiveTraits.count(Property);
     if (!IsActiveTrait) {
@@ -181,7 +188,8 @@
   APInt Score(64, 1);
 
   unsigned NoConstructTraits = VMI.ConstructTraits.size();
-  for (TraitProperty Property : VMI.RequiredTraits) {
+  for (const auto &SetBitsIt : VMI.RequiredTraits.set_bits()) {
+    TraitProperty Property = TraitProperty(SetBitsIt);
     // If there is a user score attached, use it.
     if (VMI.ScoreMap.count(Property)) {
       const APInt &UserScore = VMI.ScoreMap.lookup(Property);
@@ -304,6 +312,8 @@
   case TraitProperty::Enum:                                                    \
     return TraitSet::TraitSetEnum;
 #include "llvm/Frontend/OpenMP/OMPKinds.def"
+  case TraitProperty::NUM_PROPERTIES:
+    break;
   }
   llvm_unreachable("Unknown trait set!");
 }
@@ -331,6 +341,8 @@
   case TraitProperty::Enum:                                                    \
     return TraitSelector::TraitSelectorEnum;
 #include "llvm/Frontend/OpenMP/OMPKinds.def"
+  case TraitProperty::NUM_PROPERTIES:
+    break;
   }
   llvm_unreachable("Unknown trait set!");
 }
@@ -369,6 +381,8 @@
   case TraitProperty::Enum:                                                    \
     return Str;
 #include "llvm/Frontend/OpenMP/OMPKinds.def"
+  case TraitProperty::NUM_PROPERTIES:
+    break;
   }
   llvm_unreachable("Unknown trait property!");
 }
@@ -378,6 +392,8 @@
   case TraitProperty::Enum:                                                    \
     return "(" #TraitSetEnum "," #TraitSelectorEnum "," Str ")";
 #include "llvm/Frontend/OpenMP/OMPKinds.def"
+  case TraitProperty::NUM_PROPERTIES:
+    break;
   }
   llvm_unreachable("Unknown trait property!");
 }
@@ -405,6 +421,8 @@
     return Set == TraitSet::TraitSetEnum &&                                    \
            Selector == TraitSelector::TraitSelectorEnum;
 #include "llvm/Frontend/OpenMP/OMPKinds.def"
+  case TraitProperty::NUM_PROPERTIES:
+    break;
   }
   llvm_unreachable("Unknown trait property!");
 }