[OpenMP][Part 1] Reusable OpenMP context/traits handling

[jdoerfert]

Summary

This is the first of multiple parts to make OpenMP context/trait
handling reusable and generic. This patch was originally part of D71830
but with the unit tests it can be tested independently.

This patch implements an almost complete handling of OpenMP
contexts/traits such that we can reuse most of the logic in Flang
through the OMPContext.{h,cpp} in llvm/Frontend/OpenMP.

All but construct SIMD specifiers, e.g., inbranch, and the device ISA
selector are define in llvm/lib/Frontend/OpenMP/OMPKinds.def. From
these definitions we generate the enum classes TraitSet,
TraitSelector, and TraitProperty as well as conversion and helper
functions in llvm/lib/Frontend/OpenMP/OMPContext.{h,cpp}.

The OpenMP context is now an explicit object (see struct OMPContext).
This is in anticipation of construct traits that need to be tracked. The
OpenMP context, as well as the VariantMatchInfo, are basically made up
of a set of active or respectively required traits, e.g., 'host', and an
ordered container of constructs which allows duplication. Matching and
scoring is kept as generic as possible to allow easy extension in the
future.

[merge_guards_bot]

Unit tests: pass. 60972 tests passed, 0 failed and 726 were skipped.

clang-tidy: fail. Please fix clang-tidy findings.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

[jdoerfert]

@JonChesterfield Ping.

[JonChesterfield]

Mostly minor comments. You've got a lot of mileage out of x macros. I really like the unit tests generated from the same .def as the source.

I think there's a bug in isSubset where you're comparing iterators but should be comparing values, not sure why the tests miss that though. Marking as request changes / what I've missed for that line.

Thanks!

llvm/include/llvm/ADT/SetOperations.h

72

I wonder if a size comparison and early return would be profitable here.

llvm/include/llvm/Frontend/OpenMP/OMPKinds.def

274

clang-format

llvm/lib/Frontend/OpenMP/OMPContext.cpp

88

Probably warrants a comment that it checks for C0 is a subset of C1. Not sure there's a strong convention on argument order here.

Also a comment that it requires the arrays to have been sorted, assuming an assertion is too expensive

96

This looks strange - missing dereferences?

115

srict -> strict

225

Missmatch => mismatch

[jdoerfert]

Addressed review comments

[merge_guards_bot]

Unit tests: fail. 62360 tests passed, 1 failed and 839 were skipped.

failed: libc++.std/containers/sequences/array/array_creation/to_array.fail.cpp

clang-tidy: fail. clang-tidy found 0 errors and 6 warnings. 0 of them are added as review comments below (why?).

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

[JonChesterfield]

Nice use of expensive_checks.

[rnk]

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

119

I'd suggest that you think about different data structures here. I noticed that this instantiation of SmallSet, which wraps std::set, takes ~20ms, and happens in every file that includes OMPContext.h.

Can you use a BitVector or std::bitset instead?

[jdoerfert]

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

119

TBH, I don't understand why this takes any time at all as it is just a type. Do you mean having std::set in the type is already slow?

I still run test but what do you think of D76170 ?

[rnk]

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

119

Basically, yes, all the time is spent instantiating std::set<>::insert. This is a set of enumerators, though, which are densely packed integers with some known fixed maximum, so a bit vector seems like a more natural representation.

llvm/include/llvm/ADT/SetOperations.h

 ///
 template <class S1Ty, class S2Ty>
 void set_subtract(S1Ty &S1, const S2Ty &S2) {
   for (typename S2Ty::const_iterator SI = S2.begin(), SE = S2.end();
        SI != SE; ++SI)
     S1.erase(*SI);
 }
 
+/// set_is_subset(A, B) - Return true iff A in B
+///
+template <class S1Ty, class S2Ty>
+bool set_is_subset(const S1Ty &S1, const S2Ty &S2) {
+  if (S1.size() > S2.size())
+    return false;
+  for (auto &It : S1)
+    if (!S2.count(It))
+      return false;
+  return true;
+}
+
+/// set_is_strict_subset(A, B) - Return true iff A in B and and A != B
+///
+template <class S1Ty, class S2Ty>
+bool set_is_strict_subset(const S1Ty &S1, const S2Ty &S2) {
+  if (S1.size() >= S2.size())
+    return false;
+  return set_is_subset(S1, S2);
+}
+
 } // End llvm namespace
 
 #endif

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

+//===- OpenMP/OMPContext.h ----- OpenMP context helper functions  - C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+/// \file
+///
+/// This file provides helper functions and classes to deal with OpenMP
+/// 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/SetVector.h"
+#include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/Triple.h"
+#include "llvm/Frontend/OpenMP/OMPConstants.h"
+
+namespace llvm {
+namespace omp {
+
+/// OpenMP Context related IDs and helpers
+///
+///{
+
+/// IDs for all OpenMP context selector trait sets (construct/device/...).
+enum class TraitSet {
+#define OMP_TRAIT_SET(Enum, ...) Enum,
+#include "llvm/Frontend/OpenMP/OMPKinds.def"
+};
+
+/// IDs for all OpenMP context selector trait (device={kind/isa...}/...).
+enum class TraitSelector {
+#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"
+};
+
+/// Parse \p Str and return the trait set it matches or TraitSet::invalid.
+TraitSet getOpenMPContextTraitSetKind(StringRef Str);
+
+/// Return the trait set for which \p Property is a property.
+TraitSet getOpenMPContextTraitSetForProperty(TraitProperty Property);
+
+/// Return a textual representation of the trait set \p Kind.
+StringRef getOpenMPContextTraitSetName(TraitSet Kind);
+
+/// Parse \p Str and return the trait set it matches or
+/// TraitSelector::invalid.
+TraitSelector getOpenMPContextTraitSelectorKind(StringRef Str);
+
+/// Return the trait selector for which \p Property is a property.
+TraitSelector getOpenMPContextTraitSelectorForProperty(TraitProperty Property);
+
+/// Return a textual representation of the trait selector \p Kind.
+StringRef getOpenMPContextTraitSelectorName(TraitSelector Kind);
+
+/// Parse \p Str and return the trait set it matches or
+/// TraitProperty::invalid.
+TraitProperty getOpenMPContextTraitPropertyKind(TraitSet Set,
+                                                TraitSelector Selector,
+                                                StringRef Str);
+
+/// Return the trait property for a singleton selector \p Selector.
+TraitProperty getOpenMPContextTraitPropertyForSelector(TraitSelector Selector);
+
+/// Return a textual representation of the trait property \p Kind.
+StringRef getOpenMPContextTraitPropertyName(TraitProperty Kind);
+
+/// Return a textual representation of the trait property \p Kind with selector
+/// and set name included.
+StringRef getOpenMPContextTraitPropertyFullName(TraitProperty Kind);
+///}
+
+/// Return true if \p Selector can be nested in \p Set. Also sets
+/// \p AllowsTraitScore and \p RequiresProperty to true/false if the user can
+/// specify a score for properties in \p Selector and if the \p Selector
+/// requires at least one property.
+bool isValidTraitSelectorForTraitSet(TraitSelector Selector, TraitSet Set,
+                                     bool &AllowsTraitScore,
+                                     bool &RequiresProperty);
+
+/// Return true if \p Property can be nested in \p Selector and \p Set.
+bool isValidTraitPropertyForTraitSetAndSelector(TraitProperty Property,
+                                                TraitSelector Selector,
+                                                TraitSet Set);
+
+/// Variant match information describes the required traits and how they are
+/// scored (via the ScoresMap). In addition, the required consturct nesting is
+/// decribed as well.
+struct VariantMatchInfo {
+  /// Add the trait \p Property to the required trait set. If \p Score is not
+  /// null, it recorded as well. If \p Property is in the `construct` set it
+  /// is recorded in-order in the ConstructTraits as well.
+  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);
+    if (Set == TraitSet::construct)
+      ConstructTraits.push_back(Property);
+  }
+
+  SmallSet<TraitProperty, 8> RequiredTraits;
+  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);
+
+/// Return the index (into \p VMIs) of the variant with the highest score
+/// from the ones applicble in \p Ctx. See llvm::isVariantApplicableInContext.
+int getBestVariantMatchForContext(const SmallVectorImpl<VariantMatchInfo> &VMIs,
+                                  const OMPContext &Ctx);
+
+} // namespace omp
+
+template <> struct DenseMapInfo<omp::TraitProperty> {
+  static inline omp::TraitProperty getEmptyKey() {
+    return omp::TraitProperty(-1);
+  }
+  static inline omp::TraitProperty getTombstoneKey() {
+    return omp::TraitProperty(-2);
+  }
+  static unsigned getHashValue(omp::TraitProperty val) {
+    return std::hash<unsigned>{}(unsigned(val));
+  }
+  static bool isEqual(omp::TraitProperty LHS, omp::TraitProperty RHS) {
+    return LHS == RHS;
+  }
+};
+
+} // end namespace llvm
+#endif // LLVM_OPENMP_CONTEXT_H

llvm/include/llvm/Frontend/OpenMP/OMPKinds.def

 
 ///}
 
 /// Proc bind kinds
 ///
 ///{
 
 #ifndef OMP_PROC_BIND_KIND
 #define OMP_PROC_BIND_KIND(Enum, Str, Value)
 #endif
 
 #define __OMP_PROC_BIND_KIND(Name, Value)                                      \
   OMP_PROC_BIND_KIND(OMP_PROC_BIND_##Name, #Name, Value)
 
 __OMP_PROC_BIND_KIND(master, 2)
 __OMP_PROC_BIND_KIND(close, 3)
 __OMP_PROC_BIND_KIND(spread, 4)
 __OMP_PROC_BIND_KIND(default, 6)
 __OMP_PROC_BIND_KIND(unknown, 7)
 
 #undef __OMP_PROC_BIND_KIND
 #undef OMP_PROC_BIND_KIND
 
 ///}
+
+/// OpenMP context related definitions:
+///  - trait set selector
+///  - trait selector
+///  - trait property
+///
+///{
+
+#ifndef OMP_TRAIT_SET
+#define OMP_TRAIT_SET(Enum, Str)
+#endif
+#ifndef OMP_TRAIT_SELECTOR
+#define OMP_TRAIT_SELECTOR(Enum, TraitSetEnum, Str, RequiresProperty)
+#endif
+#ifndef OMP_TRAIT_PROPERTY
+#define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)
+#endif
+
+#define __OMP_TRAIT_SET(Name) OMP_TRAIT_SET(Name, #Name)
+#define __OMP_TRAIT_SELECTOR(TraitSet, Name, RequiresProperty)                 \
+  OMP_TRAIT_SELECTOR(TraitSet##_##Name, TraitSet, #Name, RequiresProperty)
+#define __OMP_TRAIT_SELECTOR_AND_PROPERTY(TraitSet, Name)                      \
+  OMP_TRAIT_SELECTOR(TraitSet##_##Name, TraitSet, #Name, false)                \
+  OMP_TRAIT_PROPERTY(TraitSet##_##Name##_##Name, TraitSet, TraitSet##_##Name,  \
+                     #Name)
+#define __OMP_TRAIT_PROPERTY(TraitSet, TraitSelector, Name)                    \
+  OMP_TRAIT_PROPERTY(TraitSet##_##TraitSelector##_##Name, TraitSet,            \
+                     TraitSet##_##TraitSelector, #Name)
+
+// "invalid" must go first.
+OMP_TRAIT_SET(invalid, "invalid")
+OMP_TRAIT_SELECTOR(invalid, invalid, "invalid", false)
+OMP_TRAIT_PROPERTY(invalid, invalid, invalid, "invalid")
+
+__OMP_TRAIT_SET(construct)
+__OMP_TRAIT_SELECTOR_AND_PROPERTY(construct, target)
+__OMP_TRAIT_SELECTOR_AND_PROPERTY(construct, teams)
+__OMP_TRAIT_SELECTOR_AND_PROPERTY(construct, parallel)
+__OMP_TRAIT_SELECTOR_AND_PROPERTY(construct, for)
+__OMP_TRAIT_SELECTOR_AND_PROPERTY(construct, simd)
+
+__OMP_TRAIT_SET(device)
+
+__OMP_TRAIT_SELECTOR(device, kind, true)
+
+__OMP_TRAIT_PROPERTY(device, kind, host)
+__OMP_TRAIT_PROPERTY(device, kind, nohost)
+__OMP_TRAIT_PROPERTY(device, kind, cpu)
+__OMP_TRAIT_PROPERTY(device, kind, gpu)
+__OMP_TRAIT_PROPERTY(device, kind, fpga)
+__OMP_TRAIT_PROPERTY(device, kind, any)
+
+__OMP_TRAIT_SELECTOR(device, isa, true)
+
+// TODO: What do we want for ISA?
+
+__OMP_TRAIT_SELECTOR(device, arch, true)
+
+__OMP_TRAIT_PROPERTY(device, arch, arm)
+__OMP_TRAIT_PROPERTY(device, arch, armeb)
+__OMP_TRAIT_PROPERTY(device, arch, aarch64)
+__OMP_TRAIT_PROPERTY(device, arch, aarch64_be)
+__OMP_TRAIT_PROPERTY(device, arch, aarch64_32)
+__OMP_TRAIT_PROPERTY(device, arch, ppc)
+__OMP_TRAIT_PROPERTY(device, arch, ppc64)
+__OMP_TRAIT_PROPERTY(device, arch, ppc64le)
+__OMP_TRAIT_PROPERTY(device, arch, x86)
+__OMP_TRAIT_PROPERTY(device, arch, x86_64)
+__OMP_TRAIT_PROPERTY(device, arch, amdgcn)
+__OMP_TRAIT_PROPERTY(device, arch, nvptx)
+__OMP_TRAIT_PROPERTY(device, arch, nvptx64)
+
+__OMP_TRAIT_SET(implementation)
+
+__OMP_TRAIT_SELECTOR(implementation, vendor, true)
+
+__OMP_TRAIT_PROPERTY(implementation, vendor, amd)
+__OMP_TRAIT_PROPERTY(implementation, vendor, arm)
+__OMP_TRAIT_PROPERTY(implementation, vendor, bsc)
+__OMP_TRAIT_PROPERTY(implementation, vendor, cray)
+__OMP_TRAIT_PROPERTY(implementation, vendor, fujitsu)
+__OMP_TRAIT_PROPERTY(implementation, vendor, gnu)
+__OMP_TRAIT_PROPERTY(implementation, vendor, ibm)
+__OMP_TRAIT_PROPERTY(implementation, vendor, intel)
+__OMP_TRAIT_PROPERTY(implementation, vendor, llvm)
+__OMP_TRAIT_PROPERTY(implementation, vendor, pgi)
+__OMP_TRAIT_PROPERTY(implementation, vendor, ti)
+__OMP_TRAIT_PROPERTY(implementation, vendor, unknown)
+
+__OMP_TRAIT_SELECTOR(implementation, extension, true)
+
+__OMP_TRAIT_SET(user)
+
+__OMP_TRAIT_SELECTOR(user, condition, true)
+
+__OMP_TRAIT_PROPERTY(user, condition, true)
+__OMP_TRAIT_PROPERTY(user, condition, false)
+__OMP_TRAIT_PROPERTY(user, condition, unknown)
+
+#undef OMP_TRAIT_SET
+#undef __OMP_TRAIT_SET
+///}
+
+/// Traits for the requires directive
+///
+/// These will (potentially) become trait selectors for the OpenMP context if
+/// the OMP_REQUIRES_TRAIT macro is not defined.
+///
+///{
+
+#ifdef OMP_REQUIRES_TRAIT
+#define __OMP_REQUIRES_TRAIT(Name)                                             \
+  OMP_REQUIRES_TRAIT(OMP_REQUIRES_TRAIT_##Name, #Name)
+#else
+#define __OMP_REQUIRES_TRAIT(Name)                                             \
+  __OMP_TRAIT_SELECTOR_AND_PROPERTY(implementation, Name)
+#endif
+
+__OMP_REQUIRES_TRAIT(unified_address)
+__OMP_REQUIRES_TRAIT(unified_shared_memory)
+__OMP_REQUIRES_TRAIT(reverse_offload)
+__OMP_REQUIRES_TRAIT(dynamic_allocators)
+__OMP_REQUIRES_TRAIT(atomic_default_mem_order)
+
+#undef __OMP_TRAIT_SELECTOR_AND_PROPERTY
+#undef OMP_TRAIT_SELECTOR
+#undef __OMP_TRAIT_SELECTOR
+#undef OMP_TRAIT_PROPERTY
+#undef __OMP_TRAIT_PROPERTY
+#undef __OMP_REQUIRES_TRAIT
+#undef OMP_REQUIRES_TRAIT
+///}

llvm/lib/Frontend/OpenMP/CMakeLists.txt

 add_llvm_component_library(LLVMFrontendOpenMP
   OMPConstants.cpp
+  OMPContext.cpp
   OMPIRBuilder.cpp
 
   ADDITIONAL_HEADER_DIRS
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/Frontend
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/Frontend/OpenMP/OMP
 
   DEPENDS
   intrinsics_gen
   )

llvm/lib/Frontend/OpenMP/OMPContext.cpp

+//===- OMPContext.cpp ------ Collection of helpers for OpenMP contexts ----===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+/// \file
+///
+/// This file implements helper functions and classes to deal with OpenMP
+/// contexts as used by `[begin/end] declare variant` and `metadirective`.
+///
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Frontend/OpenMP/OMPContext.h"
+#include "llvm/ADT/SetOperations.h"
+#include "llvm/ADT/StringSwitch.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+
+#define DEBUG_TYPE "openmp-ir-builder"
+
+using namespace llvm;
+using namespace omp;
+
+OMPContext::OMPContext(bool IsDeviceCompilation, Triple TargetTriple) {
+  // Add the appropriate device kind trait based on the triple and the
+  // IsDeviceCompilation flag.
+  ActiveTraits.insert(IsDeviceCompilation ? TraitProperty::device_kind_nohost
+                                          : TraitProperty::device_kind_host);
+  switch (TargetTriple.getArch()) {
+  case Triple::arm:
+  case Triple::armeb:
+  case Triple::aarch64:
+  case Triple::aarch64_be:
+  case Triple::aarch64_32:
+  case Triple::mips:
+  case Triple::mipsel:
+  case Triple::mips64:
+  case Triple::mips64el:
+  case Triple::ppc:
+  case Triple::ppc64:
+  case Triple::ppc64le:
+  case Triple::x86:
+  case Triple::x86_64:
+    ActiveTraits.insert(TraitProperty::device_kind_cpu);
+    break;
+  case Triple::amdgcn:
+  case Triple::nvptx:
+  case Triple::nvptx64:
+    ActiveTraits.insert(TraitProperty::device_kind_gpu);
+    break;
+  default:
+    break;
+  }
+
+  // Add the appropriate device architecture trait based on the triple.
+#define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
+  if (TraitSelector::TraitSelectorEnum == TraitSelector::device_arch)          \
+    if (TargetTriple.getArch() == TargetTriple.getArchTypeForLLVMName(Str))    \
+      ActiveTraits.insert(TraitProperty::Enum);
+#include "llvm/Frontend/OpenMP/OMPKinds.def"
+
+  // TODO: What exactly do we want to see as device ISA trait?
+  //       The discussion on the list did not seem to have come to an agreed
+  //       upon solution.
+
+  // LLVM is the "OpenMP vendor" but we could also interpret vendor as the
+  // target vendor.
+  ActiveTraits.insert(TraitProperty::implementation_vendor_llvm);
+
+  // The user condition true is accepted but not false.
+  ActiveTraits.insert(TraitProperty::user_condition_true);
+
+  // This is for sure some device.
+  ActiveTraits.insert(TraitProperty::device_kind_any);
+
+  LLVM_DEBUG({
+    dbgs() << "[" << DEBUG_TYPE
+           << "] New OpenMP context with the following properties:\n";
+    for (auto &Property : ActiveTraits)
+      dbgs() << "\t " << getOpenMPContextTraitPropertyFullName(Property)
+             << "\n";
+  });
+}
+
+/// Return true if \p C0 is a subset of \p C1. Note that both arrays are
+/// expected to be sorted.
+template <typename T> static bool isSubset(ArrayRef<T> C0, ArrayRef<T> C1) {
+#ifdef EXPENSIVE_CHECKS
+  assert(std::is_sorted(C0.begin(), C0.end()) &&
+         std::is_sorted(C1.begin(), C1.end()) && "Expected sorted arrays!");
+#endif
+  if (C0.size() > C1.size())
+    return false;
+  auto It0 = C0.begin(), End0 = C0.end();
+  auto It1 = C1.begin(), End1 = C1.end();
+  while (It0 != End0) {
+    if (It1 == End1)
+      return false;
+    if (*It0 == *It1) {
+      ++It0;
+      ++It1;
+      continue;
+    }
+    ++It0;
+  }
+  return true;
+}
+
+/// Return true if \p C0 is a strict subset of \p C1. Note that both arrays are
+/// expected to be sorted.
+template <typename T>
+static bool isStrictSubset(ArrayRef<T> C0, ArrayRef<T> C1) {
+  if (C0.size() >= C1.size())
+    return false;
+  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);
+}
+
+static int isVariantApplicableInContextHelper(
+    const VariantMatchInfo &VMI, const OMPContext &Ctx,
+    SmallVectorImpl<unsigned> *ConstructMatches) {
+
+  for (TraitProperty Property : VMI.RequiredTraits) {
+
+    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;
+    }
+  }
+
+  // We could use isSubset here but we also want to record the match locations.
+  unsigned ConstructIdx = 0, NoConstructTraits = Ctx.ConstructTraits.size();
+  for (TraitProperty Property : VMI.ConstructTraits) {
+    assert(getOpenMPContextTraitSetForProperty(Property) ==
+               TraitSet::construct &&
+           "Variant context is ill-formed!");
+
+    // Verify the nesting.
+    bool FoundInOrder = false;
+    while (!FoundInOrder && ConstructIdx != NoConstructTraits)
+      FoundInOrder = (Ctx.ConstructTraits[ConstructIdx++] == Property);
+    if (ConstructMatches)
+      ConstructMatches->push_back(ConstructIdx - 1);
+
+    if (!FoundInOrder) {
+      LLVM_DEBUG(dbgs() << "[" << DEBUG_TYPE << "] Construct property "
+                        << getOpenMPContextTraitPropertyName(Property)
+                        << " was not nested properly.\n");
+      return false;
+    }
+
+    // TODO: Verify SIMD
+  }
+
+  assert(isSubset<TraitProperty>(VMI.ConstructTraits, Ctx.ConstructTraits) &&
+         "Broken invariant!");
+  return true;
+}
+
+bool llvm::omp::isVariantApplicableInContext(const VariantMatchInfo &VMI,
+                                             const OMPContext &Ctx) {
+  return isVariantApplicableInContextHelper(VMI, Ctx, nullptr);
+}
+
+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) {
+    // 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;
+    }
+
+    switch (getOpenMPContextTraitSetForProperty(Property)) {
+    case TraitSet::construct:
+      // We handle the construct traits later via the VMI.ConstructTraits
+      // container.
+      continue;
+    case TraitSet::implementation:
+      // No effect on the score (implementation defined).
+      continue;
+    case TraitSet::user:
+      // No effect on the score.
+      continue;
+    case TraitSet::device:
+      // Handled separately below.
+      break;
+    case TraitSet::invalid:
+      llvm_unreachable("Unknown trait set is not to be used!");
+    }
+
+    // device={kind(any)} is "as if" no kind selector was specified.
+    if (Property == TraitProperty::device_kind_any)
+      continue;
+
+    switch (getOpenMPContextTraitSelectorForProperty(Property)) {
+    case TraitSelector::device_kind:
+      Score += (1 << (NoConstructTraits + 0));
+      continue;
+    case TraitSelector::device_arch:
+      Score += (1 << (NoConstructTraits + 1));
+      continue;
+    case TraitSelector::device_isa:
+      Score += (1 << (NoConstructTraits + 2));
+      continue;
+    default:
+      continue;
+    }
+  }
+
+  unsigned ConstructIdx = 0;
+  assert(NoConstructTraits == ConstructMatches.size() &&
+         "Mismatch in the construct traits!");
+  for (TraitProperty Property : VMI.ConstructTraits) {
+    assert(getOpenMPContextTraitSetForProperty(Property) ==
+               TraitSet::construct &&
+           "Ill-formed variant match info!");
+    // ConstructMatches is the position p - 1 and we need 2^(p-1).
+    Score += (1 << ConstructMatches[ConstructIdx++]);
+  }
+
+  LLVM_DEBUG(dbgs() << "[" << DEBUG_TYPE << "] Variant has a score of " << Score
+                    << "\n");
+  return Score;
+};
+
+int llvm::omp::getBestVariantMatchForContext(
+    const SmallVectorImpl<VariantMatchInfo> &VMIs, const OMPContext &Ctx) {
+
+  APInt BestScore(64, 0);
+  int BestVMIIdx = -1;
+  const VariantMatchInfo *BestVMI = nullptr;
+
+  for (unsigned u = 0, e = VMIs.size(); u < e; ++u) {
+    const VariantMatchInfo &VMI = VMIs[u];
+
+    SmallVector<unsigned, 8> ConstructMatches;
+    // If the variant is not applicable its not the best.
+    if (!isVariantApplicableInContextHelper(VMI, Ctx, &ConstructMatches))
+      continue;
+    // Check if its clearly not the best.
+    APInt Score = getVariantMatchScore(VMI, Ctx, ConstructMatches);
+    if (Score.ult(BestScore))
+      continue;
+    // Equal score need subset checks.
+    if (Score.eq(BestScore)) {
+      // Strict subset are never best.
+      if (isStrictSubset(VMI, *BestVMI))
+        continue;
+      // Same score and the current best is no strict subset so we keep it.
+      if (!isStrictSubset(*BestVMI, VMI))
+        continue;
+    }
+    // New best found.
+    BestVMI = &VMI;
+    BestVMIIdx = u;
+    BestScore = Score;
+  }
+
+  return BestVMIIdx;
+}
+
+TraitSet llvm::omp::getOpenMPContextTraitSetKind(StringRef S) {
+  return StringSwitch<TraitSet>(S)
+#define OMP_TRAIT_SET(Enum, Str) .Case(Str, TraitSet::Enum)
+#include "llvm/Frontend/OpenMP/OMPKinds.def"
+      .Default(TraitSet::invalid);
+}
+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"
+  }
+}
+StringRef llvm::omp::getOpenMPContextTraitSetName(TraitSet Kind) {
+  switch (Kind) {
+#define OMP_TRAIT_SET(Enum, Str)                                               \
+  case TraitSet::Enum:                                                         \
+    return Str;
+#include "llvm/Frontend/OpenMP/OMPKinds.def"
+  }
+  llvm_unreachable("Unknown trait set!");
+}
+
+TraitSelector llvm::omp::getOpenMPContextTraitSelectorKind(StringRef S) {
+  return StringSwitch<TraitSelector>(S)
+#define OMP_TRAIT_SELECTOR(Enum, TraitSetEnum, Str, ReqProp)                   \
+  .Case(Str, TraitSelector::Enum)
+#include "llvm/Frontend/OpenMP/OMPKinds.def"
+      .Default(TraitSelector::invalid);
+}
+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"
+  }
+}
+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"
+  }
+  llvm_unreachable("Unknown trait selector!");
+}
+
+TraitProperty llvm::omp::getOpenMPContextTraitPropertyKind(
+    TraitSet Set, TraitSelector Selector, StringRef S) {
+#define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
+  if (Set == TraitSet::TraitSetEnum &&                                         \
+      Selector == TraitSelector::TraitSelectorEnum && Str == S)                \
+    return TraitProperty::Enum;
+#include "llvm/Frontend/OpenMP/OMPKinds.def"
+  return TraitProperty::invalid;
+}
+TraitProperty
+llvm::omp::getOpenMPContextTraitPropertyForSelector(TraitSelector Selector) {
+  return StringSwitch<TraitProperty>(
+             getOpenMPContextTraitSelectorName(Selector))
+#define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
+  .Case(Str, Selector == TraitSelector::TraitSelectorEnum                      \
+                 ? TraitProperty::Enum                                         \
+                 : TraitProperty::invalid)
+#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"
+  }
+  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"
+  }
+  llvm_unreachable("Unknown trait property!");
+}
+
+bool llvm::omp::isValidTraitSelectorForTraitSet(TraitSelector Selector,
+                                                TraitSet Set,
+                                                bool &AllowsTraitScore,
+                                                bool &RequiresProperty) {
+  AllowsTraitScore = Set != TraitSet::construct && Set != TraitSet::device;
+  switch (Selector) {
+#define OMP_TRAIT_SELECTOR(Enum, TraitSetEnum, Str, ReqProp)                   \
+  case TraitSelector::Enum:                                                    \
+    RequiresProperty = ReqProp;                                                \
+    return Set == TraitSet::TraitSetEnum;
+#include "llvm/Frontend/OpenMP/OMPKinds.def"
+  }
+  llvm_unreachable("Unknown trait selector!");
+}
+
+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"
+  }
+  llvm_unreachable("Unknown trait property!");
+}

llvm/unittests/Frontend/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Analysis
   Core
   FrontendOpenMP
   Support
   Passes
   TransformUtils
   )
 
 add_llvm_unittest(LLVMFrontendTests
+  OpenMPContextTest.cpp
   OpenMPIRBuilderTest.cpp
   )
 
 target_link_libraries(LLVMFrontendTests PRIVATE LLVMTestingSupport)

llvm/unittests/Frontend/OpenMPContextTest.cpp

+//===- unittest/IR/OpenMPContextTest.cpp - OpenMP Context handling tests --===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Frontend/OpenMP/OMPConstants.h"
+#include "llvm/Frontend/OpenMP/OMPContext.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+using namespace omp;
+
+namespace {
+
+class OpenMPContextTest : public testing::Test {
+protected:
+  void SetUp() override {}
+
+  void TearDown() override {}
+};
+
+TEST_F(OpenMPContextTest, RoundTripAndAssociation) {
+#define OMP_TRAIT_SET(Enum, Str)                                               \
+  EXPECT_EQ(TraitSet::Enum,                                                    \
+            getOpenMPContextTraitSetKind(                                      \
+                getOpenMPContextTraitSetName(TraitSet::Enum)));                \
+  EXPECT_EQ(Str,                                                               \
+            getOpenMPContextTraitSetName(getOpenMPContextTraitSetKind(Str)));
+#define OMP_TRAIT_SELECTOR(Enum, TraitSetEnum, Str, RequiresProperty)          \
+  EXPECT_EQ(TraitSelector::Enum,                                               \
+            getOpenMPContextTraitSelectorKind(                                 \
+                getOpenMPContextTraitSelectorName(TraitSelector::Enum)));      \
+  EXPECT_EQ(Str, getOpenMPContextTraitSelectorName(                            \
+                     getOpenMPContextTraitSelectorKind(Str)));
+#define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
+  EXPECT_EQ(TraitProperty::Enum,                                               \
+            getOpenMPContextTraitPropertyKind(                                 \
+                TraitSet::TraitSetEnum, TraitSelector::TraitSelectorEnum,      \
+                getOpenMPContextTraitPropertyName(TraitProperty::Enum)));      \
+  EXPECT_EQ(                                                                   \
+      Str,                                                                     \
+      getOpenMPContextTraitPropertyName(getOpenMPContextTraitPropertyKind(     \
+          TraitSet::TraitSetEnum, TraitSelector::TraitSelectorEnum, Str)));    \
+  EXPECT_EQ(TraitSet::TraitSetEnum,                                            \
+            getOpenMPContextTraitSetForProperty(TraitProperty::Enum));         \
+  EXPECT_EQ(TraitSelector::TraitSelectorEnum,                                  \
+            getOpenMPContextTraitSelectorForProperty(TraitProperty::Enum));
+#include "llvm/Frontend/OpenMP/OMPKinds.def"
+}
+
+TEST_F(OpenMPContextTest, ValidNesting) {
+  bool AllowsTraitScore, ReqProperty;
+#define OMP_TRAIT_SELECTOR(Enum, TraitSetEnum, Str, RequiresProperty)          \
+  EXPECT_TRUE(isValidTraitSelectorForTraitSet(TraitSelector::Enum,             \
+                                              TraitSet::TraitSetEnum,          \
+                                              AllowsTraitScore, ReqProperty)); \
+  EXPECT_EQ(RequiresProperty, ReqProperty);
+#define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
+  EXPECT_TRUE(isValidTraitPropertyForTraitSetAndSelector(                      \
+      TraitProperty::Enum, TraitSelector::TraitSelectorEnum,                   \
+      TraitSet::TraitSetEnum));
+#include "llvm/Frontend/OpenMP/OMPKinds.def"
+}
+
+TEST_F(OpenMPContextTest, ApplicabilityNonConstruct) {
+  OMPContext HostLinux(false, Triple("x86_64-unknown-linux"));
+  OMPContext DeviceLinux(true, Triple("x86_64-unknown-linux"));
+  OMPContext HostNVPTX(false, Triple("nvptx64-nvidia-cuda"));
+  OMPContext DeviceNVPTX(true, Triple("nvptx64-nvidia-cuda"));
+
+  VariantMatchInfo Empty;
+  EXPECT_TRUE(isVariantApplicableInContext(Empty, HostLinux));
+  EXPECT_TRUE(isVariantApplicableInContext(Empty, DeviceLinux));
+  EXPECT_TRUE(isVariantApplicableInContext(Empty, HostNVPTX));
+  EXPECT_TRUE(isVariantApplicableInContext(Empty, DeviceNVPTX));
+
+  VariantMatchInfo UserCondFalse;
+  UserCondFalse.addTrait(TraitProperty::user_condition_false);
+  EXPECT_FALSE(isVariantApplicableInContext(UserCondFalse, HostLinux));
+  EXPECT_FALSE(isVariantApplicableInContext(UserCondFalse, DeviceLinux));
+  EXPECT_FALSE(isVariantApplicableInContext(UserCondFalse, HostNVPTX));
+  EXPECT_FALSE(isVariantApplicableInContext(UserCondFalse, DeviceNVPTX));
+
+  VariantMatchInfo DeviceArchArm;
+  DeviceArchArm.addTrait(TraitProperty::device_arch_arm);
+  EXPECT_FALSE(isVariantApplicableInContext(DeviceArchArm, HostLinux));
+  EXPECT_FALSE(isVariantApplicableInContext(DeviceArchArm, DeviceLinux));
+  EXPECT_FALSE(isVariantApplicableInContext(DeviceArchArm, HostNVPTX));
+  EXPECT_FALSE(isVariantApplicableInContext(DeviceArchArm, DeviceNVPTX));
+
+  VariantMatchInfo LLVMHostUserCondTrue;
+  LLVMHostUserCondTrue.addTrait(TraitProperty::implementation_vendor_llvm);
+  LLVMHostUserCondTrue.addTrait(TraitProperty::device_kind_host);
+  LLVMHostUserCondTrue.addTrait(TraitProperty::device_kind_any);
+  LLVMHostUserCondTrue.addTrait(TraitProperty::user_condition_true);
+  EXPECT_TRUE(isVariantApplicableInContext(LLVMHostUserCondTrue, HostLinux));
+  EXPECT_FALSE(isVariantApplicableInContext(LLVMHostUserCondTrue, DeviceLinux));
+  EXPECT_TRUE(isVariantApplicableInContext(LLVMHostUserCondTrue, HostNVPTX));
+  EXPECT_FALSE(isVariantApplicableInContext(LLVMHostUserCondTrue, DeviceNVPTX));
+
+  VariantMatchInfo LLVMHostUserCondTrueCPU = LLVMHostUserCondTrue;
+  LLVMHostUserCondTrueCPU.addTrait(TraitProperty::device_kind_cpu);
+  EXPECT_TRUE(isVariantApplicableInContext(LLVMHostUserCondTrueCPU, HostLinux));
+  EXPECT_FALSE(
+      isVariantApplicableInContext(LLVMHostUserCondTrueCPU, DeviceLinux));
+  EXPECT_FALSE(
+      isVariantApplicableInContext(LLVMHostUserCondTrueCPU, HostNVPTX));
+  EXPECT_FALSE(
+      isVariantApplicableInContext(LLVMHostUserCondTrueCPU, DeviceNVPTX));
+
+  VariantMatchInfo GPU;
+  GPU.addTrait(TraitProperty::device_kind_gpu);
+  EXPECT_FALSE(isVariantApplicableInContext(GPU, HostLinux));
+  EXPECT_FALSE(isVariantApplicableInContext(GPU, DeviceLinux));
+  EXPECT_TRUE(isVariantApplicableInContext(GPU, HostNVPTX));
+  EXPECT_TRUE(isVariantApplicableInContext(GPU, DeviceNVPTX));
+
+  VariantMatchInfo NoHost;
+  NoHost.addTrait(TraitProperty::device_kind_nohost);
+  EXPECT_FALSE(isVariantApplicableInContext(NoHost, HostLinux));
+  EXPECT_TRUE(isVariantApplicableInContext(NoHost, DeviceLinux));
+  EXPECT_FALSE(isVariantApplicableInContext(NoHost, HostNVPTX));
+  EXPECT_TRUE(isVariantApplicableInContext(NoHost, DeviceNVPTX));
+}
+
+TEST_F(OpenMPContextTest, ApplicabilityAllTraits) {
+  OMPContext HostLinuxParallelParallel(false, Triple("x86_64-unknown-linux"));
+  HostLinuxParallelParallel.addTrait(
+      TraitProperty::construct_parallel_parallel);
+  HostLinuxParallelParallel.addTrait(
+      TraitProperty::construct_parallel_parallel);
+  OMPContext DeviceLinuxTargetParallel(true, Triple("x86_64-unknown-linux"));
+  DeviceLinuxTargetParallel.addTrait(TraitProperty::construct_target_target);
+  DeviceLinuxTargetParallel.addTrait(
+      TraitProperty::construct_parallel_parallel);
+  OMPContext HostNVPTXFor(false, Triple("nvptx64-nvidia-cuda"));
+  HostNVPTXFor.addTrait(TraitProperty::construct_for_for);
+  OMPContext DeviceNVPTXTargetTeamsParallel(true,
+                                            Triple("nvptx64-nvidia-cuda"));
+  DeviceNVPTXTargetTeamsParallel.addTrait(
+      TraitProperty::construct_target_target);
+  DeviceNVPTXTargetTeamsParallel.addTrait(TraitProperty::construct_teams_teams);
+  DeviceNVPTXTargetTeamsParallel.addTrait(
+      TraitProperty::construct_parallel_parallel);
+
+  { // non-construct variants
+    VariantMatchInfo Empty;
+    EXPECT_TRUE(isVariantApplicableInContext(Empty, HostLinuxParallelParallel));
+    EXPECT_TRUE(isVariantApplicableInContext(Empty, DeviceLinuxTargetParallel));
+    EXPECT_TRUE(isVariantApplicableInContext(Empty, HostNVPTXFor));
+    EXPECT_TRUE(
+        isVariantApplicableInContext(Empty, DeviceNVPTXTargetTeamsParallel));
+
+    VariantMatchInfo UserCondFalse;
+    UserCondFalse.addTrait(TraitProperty::user_condition_false);
+    EXPECT_FALSE(
+        isVariantApplicableInContext(UserCondFalse, HostLinuxParallelParallel));
+    EXPECT_FALSE(
+        isVariantApplicableInContext(UserCondFalse, DeviceLinuxTargetParallel));
+    EXPECT_FALSE(isVariantApplicableInContext(UserCondFalse, HostNVPTXFor));
+    EXPECT_FALSE(isVariantApplicableInContext(UserCondFalse,
+                                              DeviceNVPTXTargetTeamsParallel));
+
+    VariantMatchInfo DeviceArchArm;
+    DeviceArchArm.addTrait(TraitProperty::device_arch_arm);
+    EXPECT_FALSE(
+        isVariantApplicableInContext(DeviceArchArm, HostLinuxParallelParallel));
+    EXPECT_FALSE(
+        isVariantApplicableInContext(DeviceArchArm, DeviceLinuxTargetParallel));
+    EXPECT_FALSE(isVariantApplicableInContext(DeviceArchArm, HostNVPTXFor));
+    EXPECT_FALSE(isVariantApplicableInContext(DeviceArchArm,
+                                              DeviceNVPTXTargetTeamsParallel));
+
+    APInt Score(32, 1000);
+    VariantMatchInfo LLVMHostUserCondTrue;
+    LLVMHostUserCondTrue.addTrait(TraitProperty::implementation_vendor_llvm);
+    LLVMHostUserCondTrue.addTrait(TraitProperty::device_kind_host);
+    LLVMHostUserCondTrue.addTrait(TraitProperty::device_kind_any);
+    LLVMHostUserCondTrue.addTrait(TraitProperty::user_condition_true, &Score);
+    EXPECT_TRUE(isVariantApplicableInContext(LLVMHostUserCondTrue,
+                                             HostLinuxParallelParallel));
+    EXPECT_FALSE(isVariantApplicableInContext(LLVMHostUserCondTrue,
+                                              DeviceLinuxTargetParallel));
+    EXPECT_TRUE(
+        isVariantApplicableInContext(LLVMHostUserCondTrue, HostNVPTXFor));
+    EXPECT_FALSE(isVariantApplicableInContext(LLVMHostUserCondTrue,
+                                              DeviceNVPTXTargetTeamsParallel));
+
+    VariantMatchInfo LLVMHostUserCondTrueCPU = LLVMHostUserCondTrue;
+    LLVMHostUserCondTrueCPU.addTrait(TraitProperty::device_kind_cpu);
+    EXPECT_TRUE(isVariantApplicableInContext(LLVMHostUserCondTrueCPU,
+                                             HostLinuxParallelParallel));
+    EXPECT_FALSE(isVariantApplicableInContext(LLVMHostUserCondTrueCPU,
+                                              DeviceLinuxTargetParallel));
+    EXPECT_FALSE(
+        isVariantApplicableInContext(LLVMHostUserCondTrueCPU, HostNVPTXFor));
+    EXPECT_FALSE(isVariantApplicableInContext(LLVMHostUserCondTrueCPU,
+                                              DeviceNVPTXTargetTeamsParallel));
+
+    VariantMatchInfo GPU;
+    GPU.addTrait(TraitProperty::device_kind_gpu);
+    EXPECT_FALSE(isVariantApplicableInContext(GPU, HostLinuxParallelParallel));
+    EXPECT_FALSE(isVariantApplicableInContext(GPU, DeviceLinuxTargetParallel));
+    EXPECT_TRUE(isVariantApplicableInContext(GPU, HostNVPTXFor));
+    EXPECT_TRUE(
+        isVariantApplicableInContext(GPU, DeviceNVPTXTargetTeamsParallel));
+
+    VariantMatchInfo NoHost;
+    NoHost.addTrait(TraitProperty::device_kind_nohost);
+    EXPECT_FALSE(
+        isVariantApplicableInContext(NoHost, HostLinuxParallelParallel));
+    EXPECT_TRUE(
+        isVariantApplicableInContext(NoHost, DeviceLinuxTargetParallel));
+    EXPECT_FALSE(isVariantApplicableInContext(NoHost, HostNVPTXFor));
+    EXPECT_TRUE(
+        isVariantApplicableInContext(NoHost, DeviceNVPTXTargetTeamsParallel));
+  }
+  { // variants with all sets
+    VariantMatchInfo DeviceArchArmParallel;
+    DeviceArchArmParallel.addTrait(TraitProperty::construct_parallel_parallel);
+    DeviceArchArmParallel.addTrait(TraitProperty::device_arch_arm);
+    EXPECT_FALSE(isVariantApplicableInContext(DeviceArchArmParallel,
+                                              HostLinuxParallelParallel));
+    EXPECT_FALSE(isVariantApplicableInContext(DeviceArchArmParallel,
+                                              DeviceLinuxTargetParallel));
+    EXPECT_FALSE(
+        isVariantApplicableInContext(DeviceArchArmParallel, HostNVPTXFor));
+    EXPECT_FALSE(isVariantApplicableInContext(DeviceArchArmParallel,
+                                              DeviceNVPTXTargetTeamsParallel));
+
+    VariantMatchInfo LLVMHostUserCondTrueParallel;
+    LLVMHostUserCondTrueParallel.addTrait(
+        TraitProperty::implementation_vendor_llvm);
+    LLVMHostUserCondTrueParallel.addTrait(TraitProperty::device_kind_host);
+    LLVMHostUserCondTrueParallel.addTrait(TraitProperty::device_kind_any);
+    LLVMHostUserCondTrueParallel.addTrait(TraitProperty::user_condition_true);
+    LLVMHostUserCondTrueParallel.addTrait(
+        TraitProperty::construct_parallel_parallel);
+    EXPECT_TRUE(isVariantApplicableInContext(LLVMHostUserCondTrueParallel,
+                                             HostLinuxParallelParallel));
+    EXPECT_FALSE(isVariantApplicableInContext(LLVMHostUserCondTrueParallel,
+                                              DeviceLinuxTargetParallel));
+    EXPECT_FALSE(isVariantApplicableInContext(LLVMHostUserCondTrueParallel,
+                                              HostNVPTXFor));
+    EXPECT_FALSE(isVariantApplicableInContext(LLVMHostUserCondTrueParallel,
+                                              DeviceNVPTXTargetTeamsParallel));
+
+    VariantMatchInfo LLVMHostUserCondTrueParallelParallel =
+        LLVMHostUserCondTrueParallel;
+    LLVMHostUserCondTrueParallelParallel.addTrait(
+        TraitProperty::construct_parallel_parallel);
+    EXPECT_TRUE(isVariantApplicableInContext(
+        LLVMHostUserCondTrueParallelParallel, HostLinuxParallelParallel));
+    EXPECT_FALSE(isVariantApplicableInContext(
+        LLVMHostUserCondTrueParallelParallel, DeviceLinuxTargetParallel));
+    EXPECT_FALSE(isVariantApplicableInContext(
+        LLVMHostUserCondTrueParallelParallel, HostNVPTXFor));
+    EXPECT_FALSE(isVariantApplicableInContext(
+        LLVMHostUserCondTrueParallelParallel, DeviceNVPTXTargetTeamsParallel));
+
+    VariantMatchInfo LLVMHostUserCondTrueParallelParallelParallel =
+        LLVMHostUserCondTrueParallelParallel;
+    LLVMHostUserCondTrueParallelParallelParallel.addTrait(
+        TraitProperty::construct_parallel_parallel);
+    EXPECT_FALSE(isVariantApplicableInContext(
+        LLVMHostUserCondTrueParallelParallelParallel,
+        HostLinuxParallelParallel));
+    EXPECT_FALSE(isVariantApplicableInContext(
+        LLVMHostUserCondTrueParallelParallelParallel,
+        DeviceLinuxTargetParallel));
+    EXPECT_FALSE(isVariantApplicableInContext(
+        LLVMHostUserCondTrueParallelParallelParallel, HostNVPTXFor));
+    EXPECT_FALSE(isVariantApplicableInContext(
+        LLVMHostUserCondTrueParallelParallelParallel,
+        DeviceNVPTXTargetTeamsParallel));
+
+    VariantMatchInfo GPUTargetTeams;
+    GPUTargetTeams.addTrait(TraitProperty::construct_target_target);
+    GPUTargetTeams.addTrait(TraitProperty::construct_teams_teams);
+    GPUTargetTeams.addTrait(TraitProperty::device_kind_gpu);
+    EXPECT_FALSE(isVariantApplicableInContext(GPUTargetTeams,
+                                              HostLinuxParallelParallel));
+    EXPECT_FALSE(isVariantApplicableInContext(GPUTargetTeams,
+                                              DeviceLinuxTargetParallel));
+    EXPECT_FALSE(isVariantApplicableInContext(GPUTargetTeams, HostNVPTXFor));
+    EXPECT_TRUE(isVariantApplicableInContext(GPUTargetTeams,
+                                             DeviceNVPTXTargetTeamsParallel));
+
+    VariantMatchInfo GPUTargetParallel;
+    GPUTargetParallel.addTrait(TraitProperty::construct_target_target);
+    GPUTargetParallel.addTrait(TraitProperty::construct_parallel_parallel);
+    GPUTargetParallel.addTrait(TraitProperty::device_kind_gpu);
+    EXPECT_FALSE(isVariantApplicableInContext(GPUTargetParallel,
+                                              HostLinuxParallelParallel));
+    EXPECT_FALSE(isVariantApplicableInContext(GPUTargetParallel,
+                                              DeviceLinuxTargetParallel));
+    EXPECT_FALSE(isVariantApplicableInContext(GPUTargetParallel, HostNVPTXFor));
+    EXPECT_TRUE(isVariantApplicableInContext(GPUTargetParallel,
+                                             DeviceNVPTXTargetTeamsParallel));
+  }
+}
+
+TEST_F(OpenMPContextTest, ScoringSimple) {
+  // TODO: Add scoring tests (via getBestVariantMatchForContext).
+}
+
+} // namespace