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