1 //===- OMPContext.cpp ------ Collection of helpers for OpenMP contexts ----===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 /// \file
9 ///
10 /// This file implements helper functions and classes to deal with OpenMP
11 /// contexts as used by `[begin/end] declare variant` and `metadirective`.
12 ///
13 //===----------------------------------------------------------------------===//
14 
15 #include "llvm/Frontend/OpenMP/OMPContext.h"
16 #include "llvm/ADT/SetOperations.h"
17 #include "llvm/ADT/StringRef.h"
18 #include "llvm/ADT/StringSwitch.h"
19 #include "llvm/ADT/Triple.h"
20 #include "llvm/Support/Debug.h"
21 #include "llvm/Support/raw_ostream.h"
22 
23 #define DEBUG_TYPE "openmp-ir-builder"
24 
25 using namespace llvm;
26 using namespace omp;
27 
28 OMPContext::OMPContext(bool IsDeviceCompilation, Triple TargetTriple) {
29   // Add the appropriate device kind trait based on the triple and the
30   // IsDeviceCompilation flag.
31   ActiveTraits.set(unsigned(IsDeviceCompilation
32                                 ? TraitProperty::device_kind_nohost
33                                 : TraitProperty::device_kind_host));
34   switch (TargetTriple.getArch()) {
35   case Triple::arm:
36   case Triple::armeb:
37   case Triple::aarch64:
38   case Triple::aarch64_be:
39   case Triple::aarch64_32:
40   case Triple::mips:
41   case Triple::mipsel:
42   case Triple::mips64:
43   case Triple::mips64el:
44   case Triple::ppc:
45   case Triple::ppcle:
46   case Triple::ppc64:
47   case Triple::ppc64le:
48   case Triple::x86:
49   case Triple::x86_64:
50     ActiveTraits.set(unsigned(TraitProperty::device_kind_cpu));
51     break;
52   case Triple::amdgcn:
53   case Triple::nvptx:
54   case Triple::nvptx64:
55     ActiveTraits.set(unsigned(TraitProperty::device_kind_gpu));
56     break;
57   default:
58     break;
59   }
60 
61   // Add the appropriate device architecture trait based on the triple.
62 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
63   if (TraitSelector::TraitSelectorEnum == TraitSelector::device_arch) {        \
64     if (TargetTriple.getArch() == TargetTriple.getArchTypeForLLVMName(Str))    \
65       ActiveTraits.set(unsigned(TraitProperty::Enum));                         \
66     if (StringRef(Str) == StringRef("x86_64") &&                               \
67         TargetTriple.getArch() == Triple::x86_64)                              \
68       ActiveTraits.set(unsigned(TraitProperty::Enum));                         \
69   }
70 #include "llvm/Frontend/OpenMP/OMPKinds.def"
71 
72   // TODO: What exactly do we want to see as device ISA trait?
73   //       The discussion on the list did not seem to have come to an agreed
74   //       upon solution.
75 
76   // LLVM is the "OpenMP vendor" but we could also interpret vendor as the
77   // target vendor.
78   ActiveTraits.set(unsigned(TraitProperty::implementation_vendor_llvm));
79 
80   // The user condition true is accepted but not false.
81   ActiveTraits.set(unsigned(TraitProperty::user_condition_true));
82 
83   // This is for sure some device.
84   ActiveTraits.set(unsigned(TraitProperty::device_kind_any));
85 
86   LLVM_DEBUG({
87     dbgs() << "[" << DEBUG_TYPE
88            << "] New OpenMP context with the following properties:\n";
89     for (unsigned Bit : ActiveTraits.set_bits()) {
90       TraitProperty Property = TraitProperty(Bit);
91       dbgs() << "\t " << getOpenMPContextTraitPropertyFullName(Property)
92              << "\n";
93     }
94   });
95 }
96 
97 /// Return true if \p C0 is a subset of \p C1. Note that both arrays are
98 /// expected to be sorted.
99 template <typename T> static bool isSubset(ArrayRef<T> C0, ArrayRef<T> C1) {
100 #ifdef EXPENSIVE_CHECKS
101   assert(llvm::is_sorted(C0) && llvm::is_sorted(C1) &&
102          "Expected sorted arrays!");
103 #endif
104   if (C0.size() > C1.size())
105     return false;
106   auto It0 = C0.begin(), End0 = C0.end();
107   auto It1 = C1.begin(), End1 = C1.end();
108   while (It0 != End0) {
109     if (It1 == End1)
110       return false;
111     if (*It0 == *It1) {
112       ++It0;
113       ++It1;
114       continue;
115     }
116     ++It0;
117   }
118   return true;
119 }
120 
121 /// Return true if \p C0 is a strict subset of \p C1. Note that both arrays are
122 /// expected to be sorted.
123 template <typename T>
124 static bool isStrictSubset(ArrayRef<T> C0, ArrayRef<T> C1) {
125   if (C0.size() >= C1.size())
126     return false;
127   return isSubset<T>(C0, C1);
128 }
129 
130 static bool isStrictSubset(const VariantMatchInfo &VMI0,
131                            const VariantMatchInfo &VMI1) {
132   // If all required traits are a strict subset and the ordered vectors storing
133   // the construct traits, we say it is a strict subset. Note that the latter
134   // relation is not required to be strict.
135   if (VMI0.RequiredTraits.count() >= VMI1.RequiredTraits.count())
136     return false;
137   for (unsigned Bit : VMI0.RequiredTraits.set_bits())
138     if (!VMI1.RequiredTraits.test(Bit))
139       return false;
140   if (!isSubset<TraitProperty>(VMI0.ConstructTraits, VMI1.ConstructTraits))
141     return false;
142   return true;
143 }
144 
145 static int isVariantApplicableInContextHelper(
146     const VariantMatchInfo &VMI, const OMPContext &Ctx,
147     SmallVectorImpl<unsigned> *ConstructMatches, bool DeviceSetOnly) {
148 
149   // The match kind determines if we need to match all traits, any of the
150   // traits, or none of the traits for it to be an applicable context.
151   enum MatchKind { MK_ALL, MK_ANY, MK_NONE };
152 
153   MatchKind MK = MK_ALL;
154   // Determine the match kind the user wants, "all" is the default and provided
155   // to the user only for completeness.
156   if (VMI.RequiredTraits.test(
157           unsigned(TraitProperty::implementation_extension_match_any)))
158     MK = MK_ANY;
159   if (VMI.RequiredTraits.test(
160           unsigned(TraitProperty::implementation_extension_match_none)))
161     MK = MK_NONE;
162 
163   // Helper to deal with a single property that was (not) found in the OpenMP
164   // context based on the match kind selected by the user via
165   // `implementation={extensions(match_[all,any,none])}'
166   auto HandleTrait = [MK](TraitProperty Property,
167                           bool WasFound) -> Optional<bool> /* Result */ {
168     // For kind "any" a single match is enough but we ignore non-matched
169     // properties.
170     if (MK == MK_ANY) {
171       if (WasFound)
172         return true;
173       return None;
174     }
175 
176     // In "all" or "none" mode we accept a matching or non-matching property
177     // respectively and move on. We are not done yet!
178     if ((WasFound && MK == MK_ALL) || (!WasFound && MK == MK_NONE))
179       return None;
180 
181     // We missed a property, provide some debug output and indicate failure.
182     LLVM_DEBUG({
183       if (MK == MK_ALL)
184         dbgs() << "[" << DEBUG_TYPE << "] Property "
185                << getOpenMPContextTraitPropertyName(Property, "")
186                << " was not in the OpenMP context but match kind is all.\n";
187       if (MK == MK_NONE)
188         dbgs() << "[" << DEBUG_TYPE << "] Property "
189                << getOpenMPContextTraitPropertyName(Property, "")
190                << " was in the OpenMP context but match kind is none.\n";
191     });
192     return false;
193   };
194 
195   for (unsigned Bit : VMI.RequiredTraits.set_bits()) {
196     TraitProperty Property = TraitProperty(Bit);
197     if (DeviceSetOnly &&
198         getOpenMPContextTraitSetForProperty(Property) != TraitSet::device)
199       continue;
200 
201     // So far all extensions are handled elsewhere, we skip them here as they
202     // are not part of the OpenMP context.
203     if (getOpenMPContextTraitSelectorForProperty(Property) ==
204         TraitSelector::implementation_extension)
205       continue;
206 
207     bool IsActiveTrait = Ctx.ActiveTraits.test(unsigned(Property));
208 
209     // We overwrite the isa trait as it is actually up to the OMPContext hook to
210     // check the raw string(s).
211     if (Property == TraitProperty::device_isa___ANY)
212       IsActiveTrait = llvm::all_of(VMI.ISATraits, [&](StringRef RawString) {
213         return Ctx.matchesISATrait(RawString);
214       });
215 
216     Optional<bool> Result = HandleTrait(Property, IsActiveTrait);
217     if (Result.hasValue())
218       return Result.getValue();
219   }
220 
221   if (!DeviceSetOnly) {
222     // We could use isSubset here but we also want to record the match
223     // locations.
224     unsigned ConstructIdx = 0, NoConstructTraits = Ctx.ConstructTraits.size();
225     for (TraitProperty Property : VMI.ConstructTraits) {
226       assert(getOpenMPContextTraitSetForProperty(Property) ==
227                  TraitSet::construct &&
228              "Variant context is ill-formed!");
229 
230       // Verify the nesting.
231       bool FoundInOrder = false;
232       while (!FoundInOrder && ConstructIdx != NoConstructTraits)
233         FoundInOrder = (Ctx.ConstructTraits[ConstructIdx++] == Property);
234       if (ConstructMatches)
235         ConstructMatches->push_back(ConstructIdx - 1);
236 
237       Optional<bool> Result = HandleTrait(Property, FoundInOrder);
238       if (Result.hasValue())
239         return Result.getValue();
240 
241       if (!FoundInOrder) {
242         LLVM_DEBUG(dbgs() << "[" << DEBUG_TYPE << "] Construct property "
243                           << getOpenMPContextTraitPropertyName(Property, "")
244                           << " was not nested properly.\n");
245         return false;
246       }
247 
248       // TODO: Verify SIMD
249     }
250 
251     assert(isSubset<TraitProperty>(VMI.ConstructTraits, Ctx.ConstructTraits) &&
252            "Broken invariant!");
253   }
254 
255   if (MK == MK_ANY) {
256     LLVM_DEBUG(dbgs() << "[" << DEBUG_TYPE
257                       << "] None of the properties was in the OpenMP context "
258                          "but match kind is any.\n");
259     return false;
260   }
261 
262   return true;
263 }
264 
265 bool llvm::omp::isVariantApplicableInContext(const VariantMatchInfo &VMI,
266                                              const OMPContext &Ctx,
267                                              bool DeviceSetOnly) {
268   return isVariantApplicableInContextHelper(
269       VMI, Ctx, /* ConstructMatches */ nullptr, DeviceSetOnly);
270 }
271 
272 static APInt getVariantMatchScore(const VariantMatchInfo &VMI,
273                                   const OMPContext &Ctx,
274                                   SmallVectorImpl<unsigned> &ConstructMatches) {
275   APInt Score(64, 1);
276 
277   unsigned NoConstructTraits = VMI.ConstructTraits.size();
278   for (unsigned Bit : VMI.RequiredTraits.set_bits()) {
279     TraitProperty Property = TraitProperty(Bit);
280     // If there is a user score attached, use it.
281     if (VMI.ScoreMap.count(Property)) {
282       const APInt &UserScore = VMI.ScoreMap.lookup(Property);
283       assert(UserScore.uge(0) && "Expect non-negative user scores!");
284       Score += UserScore.getZExtValue();
285       continue;
286     }
287 
288     switch (getOpenMPContextTraitSetForProperty(Property)) {
289     case TraitSet::construct:
290       // We handle the construct traits later via the VMI.ConstructTraits
291       // container.
292       continue;
293     case TraitSet::implementation:
294       // No effect on the score (implementation defined).
295       continue;
296     case TraitSet::user:
297       // No effect on the score.
298       continue;
299     case TraitSet::device:
300       // Handled separately below.
301       break;
302     case TraitSet::invalid:
303       llvm_unreachable("Unknown trait set is not to be used!");
304     }
305 
306     // device={kind(any)} is "as if" no kind selector was specified.
307     if (Property == TraitProperty::device_kind_any)
308       continue;
309 
310     switch (getOpenMPContextTraitSelectorForProperty(Property)) {
311     case TraitSelector::device_kind:
312       Score += (1ULL << (NoConstructTraits + 0));
313       continue;
314     case TraitSelector::device_arch:
315       Score += (1ULL << (NoConstructTraits + 1));
316       continue;
317     case TraitSelector::device_isa:
318       Score += (1ULL << (NoConstructTraits + 2));
319       continue;
320     default:
321       continue;
322     }
323   }
324 
325   unsigned ConstructIdx = 0;
326   assert(NoConstructTraits == ConstructMatches.size() &&
327          "Mismatch in the construct traits!");
328   for (TraitProperty Property : VMI.ConstructTraits) {
329     assert(getOpenMPContextTraitSetForProperty(Property) ==
330                TraitSet::construct &&
331            "Ill-formed variant match info!");
332     (void)Property;
333     // ConstructMatches is the position p - 1 and we need 2^(p-1).
334     Score += (1ULL << ConstructMatches[ConstructIdx++]);
335   }
336 
337   LLVM_DEBUG(dbgs() << "[" << DEBUG_TYPE << "] Variant has a score of " << Score
338                     << "\n");
339   return Score;
340 }
341 
342 int llvm::omp::getBestVariantMatchForContext(
343     const SmallVectorImpl<VariantMatchInfo> &VMIs, const OMPContext &Ctx) {
344 
345   APInt BestScore(64, 0);
346   int BestVMIIdx = -1;
347   const VariantMatchInfo *BestVMI = nullptr;
348 
349   for (unsigned u = 0, e = VMIs.size(); u < e; ++u) {
350     const VariantMatchInfo &VMI = VMIs[u];
351 
352     SmallVector<unsigned, 8> ConstructMatches;
353     // If the variant is not applicable its not the best.
354     if (!isVariantApplicableInContextHelper(VMI, Ctx, &ConstructMatches,
355                                             /* DeviceSetOnly */ false))
356       continue;
357     // Check if its clearly not the best.
358     APInt Score = getVariantMatchScore(VMI, Ctx, ConstructMatches);
359     if (Score.ult(BestScore))
360       continue;
361     // Equal score need subset checks.
362     if (Score.eq(BestScore)) {
363       // Strict subset are never best.
364       if (isStrictSubset(VMI, *BestVMI))
365         continue;
366       // Same score and the current best is no strict subset so we keep it.
367       if (!isStrictSubset(*BestVMI, VMI))
368         continue;
369     }
370     // New best found.
371     BestVMI = &VMI;
372     BestVMIIdx = u;
373     BestScore = Score;
374   }
375 
376   return BestVMIIdx;
377 }
378 
379 TraitSet llvm::omp::getOpenMPContextTraitSetKind(StringRef S) {
380   return StringSwitch<TraitSet>(S)
381 #define OMP_TRAIT_SET(Enum, Str) .Case(Str, TraitSet::Enum)
382 #include "llvm/Frontend/OpenMP/OMPKinds.def"
383       .Default(TraitSet::invalid);
384 }
385 
386 TraitSet
387 llvm::omp::getOpenMPContextTraitSetForSelector(TraitSelector Selector) {
388   switch (Selector) {
389 #define OMP_TRAIT_SELECTOR(Enum, TraitSetEnum, Str, ReqProp)                   \
390   case TraitSelector::Enum:                                                    \
391     return TraitSet::TraitSetEnum;
392 #include "llvm/Frontend/OpenMP/OMPKinds.def"
393   }
394   llvm_unreachable("Unknown trait selector!");
395 }
396 TraitSet
397 llvm::omp::getOpenMPContextTraitSetForProperty(TraitProperty Property) {
398   switch (Property) {
399 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
400   case TraitProperty::Enum:                                                    \
401     return TraitSet::TraitSetEnum;
402 #include "llvm/Frontend/OpenMP/OMPKinds.def"
403   }
404   llvm_unreachable("Unknown trait set!");
405 }
406 StringRef llvm::omp::getOpenMPContextTraitSetName(TraitSet Kind) {
407   switch (Kind) {
408 #define OMP_TRAIT_SET(Enum, Str)                                               \
409   case TraitSet::Enum:                                                         \
410     return Str;
411 #include "llvm/Frontend/OpenMP/OMPKinds.def"
412   }
413   llvm_unreachable("Unknown trait set!");
414 }
415 
416 TraitSelector llvm::omp::getOpenMPContextTraitSelectorKind(StringRef S) {
417   return StringSwitch<TraitSelector>(S)
418 #define OMP_TRAIT_SELECTOR(Enum, TraitSetEnum, Str, ReqProp)                   \
419   .Case(Str, TraitSelector::Enum)
420 #include "llvm/Frontend/OpenMP/OMPKinds.def"
421       .Default(TraitSelector::invalid);
422 }
423 TraitSelector
424 llvm::omp::getOpenMPContextTraitSelectorForProperty(TraitProperty Property) {
425   switch (Property) {
426 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
427   case TraitProperty::Enum:                                                    \
428     return TraitSelector::TraitSelectorEnum;
429 #include "llvm/Frontend/OpenMP/OMPKinds.def"
430   }
431   llvm_unreachable("Unknown trait set!");
432 }
433 StringRef llvm::omp::getOpenMPContextTraitSelectorName(TraitSelector Kind) {
434   switch (Kind) {
435 #define OMP_TRAIT_SELECTOR(Enum, TraitSetEnum, Str, ReqProp)                   \
436   case TraitSelector::Enum:                                                    \
437     return Str;
438 #include "llvm/Frontend/OpenMP/OMPKinds.def"
439   }
440   llvm_unreachable("Unknown trait selector!");
441 }
442 
443 TraitProperty llvm::omp::getOpenMPContextTraitPropertyKind(
444     TraitSet Set, TraitSelector Selector, StringRef S) {
445   // Special handling for `device={isa(...)}` as we accept anything here. It is
446   // up to the target to decide if the feature is available.
447   if (Set == TraitSet::device && Selector == TraitSelector::device_isa)
448     return TraitProperty::device_isa___ANY;
449 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
450   if (Set == TraitSet::TraitSetEnum && Str == S)                               \
451     return TraitProperty::Enum;
452 #include "llvm/Frontend/OpenMP/OMPKinds.def"
453   return TraitProperty::invalid;
454 }
455 TraitProperty
456 llvm::omp::getOpenMPContextTraitPropertyForSelector(TraitSelector Selector) {
457   return StringSwitch<TraitProperty>(
458              getOpenMPContextTraitSelectorName(Selector))
459 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
460   .Case(Str, Selector == TraitSelector::TraitSelectorEnum                      \
461                  ? TraitProperty::Enum                                         \
462                  : TraitProperty::invalid)
463 #include "llvm/Frontend/OpenMP/OMPKinds.def"
464       .Default(TraitProperty::invalid);
465 }
466 StringRef llvm::omp::getOpenMPContextTraitPropertyName(TraitProperty Kind,
467                                                        StringRef RawString) {
468   if (Kind == TraitProperty::device_isa___ANY)
469     return RawString;
470   switch (Kind) {
471 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
472   case TraitProperty::Enum:                                                    \
473     return Str;
474 #include "llvm/Frontend/OpenMP/OMPKinds.def"
475   }
476   llvm_unreachable("Unknown trait property!");
477 }
478 StringRef llvm::omp::getOpenMPContextTraitPropertyFullName(TraitProperty Kind) {
479   switch (Kind) {
480 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
481   case TraitProperty::Enum:                                                    \
482     return "(" #TraitSetEnum "," #TraitSelectorEnum "," Str ")";
483 #include "llvm/Frontend/OpenMP/OMPKinds.def"
484   }
485   llvm_unreachable("Unknown trait property!");
486 }
487 
488 bool llvm::omp::isValidTraitSelectorForTraitSet(TraitSelector Selector,
489                                                 TraitSet Set,
490                                                 bool &AllowsTraitScore,
491                                                 bool &RequiresProperty) {
492   AllowsTraitScore = Set != TraitSet::construct && Set != TraitSet::device;
493   switch (Selector) {
494 #define OMP_TRAIT_SELECTOR(Enum, TraitSetEnum, Str, ReqProp)                   \
495   case TraitSelector::Enum:                                                    \
496     RequiresProperty = ReqProp;                                                \
497     return Set == TraitSet::TraitSetEnum;
498 #include "llvm/Frontend/OpenMP/OMPKinds.def"
499   }
500   llvm_unreachable("Unknown trait selector!");
501 }
502 
503 bool llvm::omp::isValidTraitPropertyForTraitSetAndSelector(
504     TraitProperty Property, TraitSelector Selector, TraitSet Set) {
505   switch (Property) {
506 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
507   case TraitProperty::Enum:                                                    \
508     return Set == TraitSet::TraitSetEnum &&                                    \
509            Selector == TraitSelector::TraitSelectorEnum;
510 #include "llvm/Frontend/OpenMP/OMPKinds.def"
511   }
512   llvm_unreachable("Unknown trait property!");
513 }
514 
515 std::string llvm::omp::listOpenMPContextTraitSets() {
516   std::string S;
517 #define OMP_TRAIT_SET(Enum, Str)                                               \
518   if (StringRef(Str) != "invalid")                                             \
519     S.append("'").append(Str).append("'").append(" ");
520 #include "llvm/Frontend/OpenMP/OMPKinds.def"
521   S.pop_back();
522   return S;
523 }
524 
525 std::string llvm::omp::listOpenMPContextTraitSelectors(TraitSet Set) {
526   std::string S;
527 #define OMP_TRAIT_SELECTOR(Enum, TraitSetEnum, Str, ReqProp)                   \
528   if (TraitSet::TraitSetEnum == Set && StringRef(Str) != "Invalid")            \
529     S.append("'").append(Str).append("'").append(" ");
530 #include "llvm/Frontend/OpenMP/OMPKinds.def"
531   S.pop_back();
532   return S;
533 }
534 
535 std::string
536 llvm::omp::listOpenMPContextTraitProperties(TraitSet Set,
537                                             TraitSelector Selector) {
538   std::string S;
539 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
540   if (TraitSet::TraitSetEnum == Set &&                                         \
541       TraitSelector::TraitSelectorEnum == Selector &&                          \
542       StringRef(Str) != "invalid")                                             \
543     S.append("'").append(Str).append("'").append(" ");
544 #include "llvm/Frontend/OpenMP/OMPKinds.def"
545   if (S.empty())
546     return "<none>";
547   S.pop_back();
548   return S;
549 }
550