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