[OpenMP][NFC] Reduce instantiation time with different data structure

[jdoerfert]

Summary

See rational here: https://reviews.llvm.org/D71847#1922648

[jdoerfert]

Tests pass fine, @rnk, let me know if this solves the issue you saw.

[rnk]

Thanks, yes, this is what I had in mind.

llvm/include/llvm/Frontend/OpenMP/OMPContext.h

48

LLVM doesn't use the all uppercase naming style for enums, I'd use something like Count, Num, or Max.

One technique you could use to avoid the sentinel enum is to make an alias for the last enum, as is done for builtin types here:
https://github.com/llvm/llvm-project/blob/master/clang/include/clang/AST/Type.h#L2514
Then you won't have to handle NUM_PROPERTIES below, and you would use TraitProperty::Max + 1 for the BitVector.

152

This is the same instantiation, so we don't get any savings unless the same technique is applied here. I started by trying to change this type, but it was challenging, so I raised the issue to see if you'd be OK with it.

llvm/lib/Frontend/OpenMP/OMPContext.cpp

129

Worth fixing this formatting nit

[jdoerfert]

Addressed comments

[rnk]

lgtm, as long as you are OK with the casts as the code author.

llvm/lib/Frontend/OpenMP/OMPContext.cpp

127–129

I expected BitVector to expose an API to do this without iterating the bits individually, but I can't find one. test seems close, but not quite right. Oh well.

llvm/include/llvm/Frontend/OpenMP/OMPContext.h

 /// contexts as used by `[begin/end] declare variant` and `metadirective`.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_OPENMP_CONTEXT_H
 #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"
 #include "llvm/Frontend/OpenMP/OMPConstants.h"
 
 namespace llvm {
 namespace omp {
 

 #define OMP_TRAIT_SELECTOR(Enum, ...) Enum,
 #include "llvm/Frontend/OpenMP/OMPKinds.def"
 };
 
 /// IDs for all OpenMP context trait properties (host/gpu/bsc/llvm/...)
 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.
 TraitSet getOpenMPContextTraitSetKind(StringRef Str);
 
 /// Return the trait set for which \p Selector is a selector.
 TraitSet getOpenMPContextTraitSetForSelector(TraitSelector Selector);
 
void addTrait(TraitProperty Property, APInt *Score = nullptr) {
     addTrait(getOpenMPContextTraitSetForProperty(Property), Property, Score);
   }
   /// Add the trait \p Property which is in set \p Set to the required trait
   /// set. If \p Score is not null, it recorded as well. If \p Set is the
   /// `construct` set it is recorded in-order in the ConstructTraits as well.
   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;
 };
 
 /// The context for a source location is made up of active property traits,
 /// e.g., device={kind(host)}, and constructs traits which describe the nesting
 /// in OpenMP constructs at the location.
 struct OMPContext {
   OMPContext(bool IsDeviceCompilation, Triple TargetTriple);
 
   void addTrait(TraitProperty Property) {
     addTrait(getOpenMPContextTraitSetForProperty(Property), Property);
   }
   void addTrait(TraitSet Set, TraitProperty Property) {
     ActiveTraits.insert(Property);
     if (Set == TraitSet::construct)
       ConstructTraits.push_back(Property);
   }
 
   SmallSet<TraitProperty, 8> ActiveTraits;
   SmallVector<TraitProperty, 8> ConstructTraits;
 };
 
 /// Return true if \p VMI is applicable in \p Ctx, that is, all traits required
 /// by \p VMI are available in the OpenMP context \p Ctx.
 bool isVariantApplicableInContext(const VariantMatchInfo &VMI,
                                   const OMPContext &Ctx);
 

llvm/lib/Frontend/OpenMP/OMPContext.cpp

static bool isStrictSubset(ArrayRef<T> C0, ArrayRef<T> C1) {
   return isSubset<T>(C0, C1);
 }
 
 static bool isStrictSubset(const VariantMatchInfo &VMI0,
                            const VariantMatchInfo &VMI1) {
   // 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) {
       LLVM_DEBUG(dbgs() << "[" << DEBUG_TYPE << "] Property "
                         << getOpenMPContextTraitPropertyName(Property)
                         << " was not in the OpenMP context.\n");
       return false;
     }

 }
 
 static APInt getVariantMatchScore(const VariantMatchInfo &VMI,
                                   const OMPContext &Ctx,
                                   SmallVectorImpl<unsigned> &ConstructMatches) {
   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);
       assert(UserScore.uge(0) && "Expect non-negative user scores!");
       Score += UserScore.getZExtValue();
       continue;
     }
 

 }
 TraitSet
 llvm::omp::getOpenMPContextTraitSetForProperty(TraitProperty Property) {
   switch (Property) {
 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
   case TraitProperty::Enum:                                                    \
     return TraitSet::TraitSetEnum;
 #include "llvm/Frontend/OpenMP/OMPKinds.def"
+  case TraitProperty::NUM_PROPERTIES:
+    break;
   }
   llvm_unreachable("Unknown trait set!");
 }
 StringRef llvm::omp::getOpenMPContextTraitSetName(TraitSet Kind) {
   switch (Kind) {
 #define OMP_TRAIT_SET(Enum, Str)                                               \
   case TraitSet::Enum:                                                         \
     return Str;

 }
 TraitSelector
 llvm::omp::getOpenMPContextTraitSelectorForProperty(TraitProperty Property) {
   switch (Property) {
 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
   case TraitProperty::Enum:                                                    \
     return TraitSelector::TraitSelectorEnum;
 #include "llvm/Frontend/OpenMP/OMPKinds.def"
+  case TraitProperty::NUM_PROPERTIES:
+    break;
   }
   llvm_unreachable("Unknown trait set!");
 }
 StringRef llvm::omp::getOpenMPContextTraitSelectorName(TraitSelector Kind) {
   switch (Kind) {
 #define OMP_TRAIT_SELECTOR(Enum, TraitSetEnum, Str, ReqProp)                   \
   case TraitSelector::Enum:                                                    \
     return Str;
#include "llvm/Frontend/OpenMP/OMPKinds.def"
       .Default(TraitProperty::invalid);
 }
 StringRef llvm::omp::getOpenMPContextTraitPropertyName(TraitProperty Kind) {
   switch (Kind) {
 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
   case TraitProperty::Enum:                                                    \
     return Str;
 #include "llvm/Frontend/OpenMP/OMPKinds.def"
+  case TraitProperty::NUM_PROPERTIES:
+    break;
   }
   llvm_unreachable("Unknown trait property!");
 }
 StringRef llvm::omp::getOpenMPContextTraitPropertyFullName(TraitProperty Kind) {
   switch (Kind) {
 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
   case TraitProperty::Enum:                                                    \
     return "(" #TraitSetEnum "," #TraitSelectorEnum "," Str ")";
 #include "llvm/Frontend/OpenMP/OMPKinds.def"
+  case TraitProperty::NUM_PROPERTIES:
+    break;
   }
   llvm_unreachable("Unknown trait property!");
 }
 
 bool llvm::omp::isValidTraitSelectorForTraitSet(TraitSelector Selector,
                                                 TraitSet Set,
                                                 bool &AllowsTraitScore,
                                                 bool &RequiresProperty) {

 bool llvm::omp::isValidTraitPropertyForTraitSetAndSelector(
     TraitProperty Property, TraitSelector Selector, TraitSet Set) {
   switch (Property) {
 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
   case TraitProperty::Enum:                                                    \
     return Set == TraitSet::TraitSetEnum &&                                    \
            Selector == TraitSelector::TraitSelectorEnum;
 #include "llvm/Frontend/OpenMP/OMPKinds.def"
+  case TraitProperty::NUM_PROPERTIES:
+    break;
   }
   llvm_unreachable("Unknown trait property!");
 }
 
 std::string llvm::omp::listOpenMPContextTraitSets() {
   std::string S;
 #define OMP_TRAIT_SET(Enum, Str)                                               \
   if (StringRef(Str) != "invalid")                                             \