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 (const auto &SetBitsIt : ActiveTraits.set_bits()) {
83       TraitProperty Property = TraitProperty(SetBitsIt);
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(std::is_sorted(C0.begin(), C0.end()) &&
95          std::is_sorted(C1.begin(), C1.end()) && "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 (const auto &SetBitsIt : VMI0.RequiredTraits.set_bits())
131     if (!VMI1.RequiredTraits.test(SetBitsIt))
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) {
141 
142   for (const auto &SetBitsIt : VMI.RequiredTraits.set_bits()) {
143     TraitProperty Property = TraitProperty(SetBitsIt);
144 
145     bool IsActiveTrait = Ctx.ActiveTraits.test(unsigned(Property));
146     if (!IsActiveTrait) {
147       LLVM_DEBUG(dbgs() << "[" << DEBUG_TYPE << "] Property "
148                         << getOpenMPContextTraitPropertyName(Property)
149                         << " was not in the OpenMP context.\n");
150       return false;
151     }
152   }
153 
154   // We could use isSubset here but we also want to record the match locations.
155   unsigned ConstructIdx = 0, NoConstructTraits = Ctx.ConstructTraits.size();
156   for (TraitProperty Property : VMI.ConstructTraits) {
157     assert(getOpenMPContextTraitSetForProperty(Property) ==
158                TraitSet::construct &&
159            "Variant context is ill-formed!");
160 
161     // Verify the nesting.
162     bool FoundInOrder = false;
163     while (!FoundInOrder && ConstructIdx != NoConstructTraits)
164       FoundInOrder = (Ctx.ConstructTraits[ConstructIdx++] == Property);
165     if (ConstructMatches)
166       ConstructMatches->push_back(ConstructIdx - 1);
167 
168     if (!FoundInOrder) {
169       LLVM_DEBUG(dbgs() << "[" << DEBUG_TYPE << "] Construct property "
170                         << getOpenMPContextTraitPropertyName(Property)
171                         << " was not nested properly.\n");
172       return false;
173     }
174 
175     // TODO: Verify SIMD
176   }
177 
178   assert(isSubset<TraitProperty>(VMI.ConstructTraits, Ctx.ConstructTraits) &&
179          "Broken invariant!");
180   return true;
181 }
182 
183 bool llvm::omp::isVariantApplicableInContext(const VariantMatchInfo &VMI,
184                                              const OMPContext &Ctx) {
185   return isVariantApplicableInContextHelper(VMI, Ctx, nullptr);
186 }
187 
188 static APInt getVariantMatchScore(const VariantMatchInfo &VMI,
189                                   const OMPContext &Ctx,
190                                   SmallVectorImpl<unsigned> &ConstructMatches) {
191   APInt Score(64, 1);
192 
193   unsigned NoConstructTraits = VMI.ConstructTraits.size();
194   for (const auto &SetBitsIt : VMI.RequiredTraits.set_bits()) {
195     TraitProperty Property = TraitProperty(SetBitsIt);
196     // If there is a user score attached, use it.
197     if (VMI.ScoreMap.count(Property)) {
198       const APInt &UserScore = VMI.ScoreMap.lookup(Property);
199       assert(UserScore.uge(0) && "Expect non-negative user scores!");
200       Score += UserScore.getZExtValue();
201       continue;
202     }
203 
204     switch (getOpenMPContextTraitSetForProperty(Property)) {
205     case TraitSet::construct:
206       // We handle the construct traits later via the VMI.ConstructTraits
207       // container.
208       continue;
209     case TraitSet::implementation:
210       // No effect on the score (implementation defined).
211       continue;
212     case TraitSet::user:
213       // No effect on the score.
214       continue;
215     case TraitSet::device:
216       // Handled separately below.
217       break;
218     case TraitSet::invalid:
219       llvm_unreachable("Unknown trait set is not to be used!");
220     }
221 
222     // device={kind(any)} is "as if" no kind selector was specified.
223     if (Property == TraitProperty::device_kind_any)
224       continue;
225 
226     switch (getOpenMPContextTraitSelectorForProperty(Property)) {
227     case TraitSelector::device_kind:
228       Score += (1ULL << (NoConstructTraits + 0));
229       continue;
230     case TraitSelector::device_arch:
231       Score += (1ULL << (NoConstructTraits + 1));
232       continue;
233     case TraitSelector::device_isa:
234       Score += (1ULL << (NoConstructTraits + 2));
235       continue;
236     default:
237       continue;
238     }
239   }
240 
241   unsigned ConstructIdx = 0;
242   assert(NoConstructTraits == ConstructMatches.size() &&
243          "Mismatch in the construct traits!");
244   for (TraitProperty Property : VMI.ConstructTraits) {
245     assert(getOpenMPContextTraitSetForProperty(Property) ==
246                TraitSet::construct &&
247            "Ill-formed variant match info!");
248     (void)Property;
249     // ConstructMatches is the position p - 1 and we need 2^(p-1).
250     Score += (1ULL << ConstructMatches[ConstructIdx++]);
251   }
252 
253   LLVM_DEBUG(dbgs() << "[" << DEBUG_TYPE << "] Variant has a score of " << Score
254                     << "\n");
255   return Score;
256 }
257 
258 int llvm::omp::getBestVariantMatchForContext(
259     const SmallVectorImpl<VariantMatchInfo> &VMIs, const OMPContext &Ctx) {
260 
261   APInt BestScore(64, 0);
262   int BestVMIIdx = -1;
263   const VariantMatchInfo *BestVMI = nullptr;
264 
265   for (unsigned u = 0, e = VMIs.size(); u < e; ++u) {
266     const VariantMatchInfo &VMI = VMIs[u];
267 
268     SmallVector<unsigned, 8> ConstructMatches;
269     // If the variant is not applicable its not the best.
270     if (!isVariantApplicableInContextHelper(VMI, Ctx, &ConstructMatches))
271       continue;
272     // Check if its clearly not the best.
273     APInt Score = getVariantMatchScore(VMI, Ctx, ConstructMatches);
274     if (Score.ult(BestScore))
275       continue;
276     // Equal score need subset checks.
277     if (Score.eq(BestScore)) {
278       // Strict subset are never best.
279       if (isStrictSubset(VMI, *BestVMI))
280         continue;
281       // Same score and the current best is no strict subset so we keep it.
282       if (!isStrictSubset(*BestVMI, VMI))
283         continue;
284     }
285     // New best found.
286     BestVMI = &VMI;
287     BestVMIIdx = u;
288     BestScore = Score;
289   }
290 
291   return BestVMIIdx;
292 }
293 
294 TraitSet llvm::omp::getOpenMPContextTraitSetKind(StringRef S) {
295   return StringSwitch<TraitSet>(S)
296 #define OMP_TRAIT_SET(Enum, Str) .Case(Str, TraitSet::Enum)
297 #include "llvm/Frontend/OpenMP/OMPKinds.def"
298       .Default(TraitSet::invalid);
299 }
300 
301 TraitSet
302 llvm::omp::getOpenMPContextTraitSetForSelector(TraitSelector Selector) {
303   switch (Selector) {
304 #define OMP_TRAIT_SELECTOR(Enum, TraitSetEnum, Str, ReqProp)                   \
305   case TraitSelector::Enum:                                                    \
306     return TraitSet::TraitSetEnum;
307 #include "llvm/Frontend/OpenMP/OMPKinds.def"
308   }
309   llvm_unreachable("Unknown trait selector!");
310 }
311 TraitSet
312 llvm::omp::getOpenMPContextTraitSetForProperty(TraitProperty Property) {
313   switch (Property) {
314 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
315   case TraitProperty::Enum:                                                    \
316     return TraitSet::TraitSetEnum;
317 #include "llvm/Frontend/OpenMP/OMPKinds.def"
318   }
319   llvm_unreachable("Unknown trait set!");
320 }
321 StringRef llvm::omp::getOpenMPContextTraitSetName(TraitSet Kind) {
322   switch (Kind) {
323 #define OMP_TRAIT_SET(Enum, Str)                                               \
324   case TraitSet::Enum:                                                         \
325     return Str;
326 #include "llvm/Frontend/OpenMP/OMPKinds.def"
327   }
328   llvm_unreachable("Unknown trait set!");
329 }
330 
331 TraitSelector llvm::omp::getOpenMPContextTraitSelectorKind(StringRef S) {
332   return StringSwitch<TraitSelector>(S)
333 #define OMP_TRAIT_SELECTOR(Enum, TraitSetEnum, Str, ReqProp)                   \
334   .Case(Str, TraitSelector::Enum)
335 #include "llvm/Frontend/OpenMP/OMPKinds.def"
336       .Default(TraitSelector::invalid);
337 }
338 TraitSelector
339 llvm::omp::getOpenMPContextTraitSelectorForProperty(TraitProperty Property) {
340   switch (Property) {
341 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
342   case TraitProperty::Enum:                                                    \
343     return TraitSelector::TraitSelectorEnum;
344 #include "llvm/Frontend/OpenMP/OMPKinds.def"
345   }
346   llvm_unreachable("Unknown trait set!");
347 }
348 StringRef llvm::omp::getOpenMPContextTraitSelectorName(TraitSelector Kind) {
349   switch (Kind) {
350 #define OMP_TRAIT_SELECTOR(Enum, TraitSetEnum, Str, ReqProp)                   \
351   case TraitSelector::Enum:                                                    \
352     return Str;
353 #include "llvm/Frontend/OpenMP/OMPKinds.def"
354   }
355   llvm_unreachable("Unknown trait selector!");
356 }
357 
358 TraitProperty llvm::omp::getOpenMPContextTraitPropertyKind(TraitSet Set,
359                                                            StringRef S) {
360 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
361   if (Set == TraitSet::TraitSetEnum && Str == S)                               \
362     return TraitProperty::Enum;
363 #include "llvm/Frontend/OpenMP/OMPKinds.def"
364   return TraitProperty::invalid;
365 }
366 TraitProperty
367 llvm::omp::getOpenMPContextTraitPropertyForSelector(TraitSelector Selector) {
368   return StringSwitch<TraitProperty>(
369              getOpenMPContextTraitSelectorName(Selector))
370 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
371   .Case(Str, Selector == TraitSelector::TraitSelectorEnum                      \
372                  ? TraitProperty::Enum                                         \
373                  : TraitProperty::invalid)
374 #include "llvm/Frontend/OpenMP/OMPKinds.def"
375       .Default(TraitProperty::invalid);
376 }
377 StringRef llvm::omp::getOpenMPContextTraitPropertyName(TraitProperty Kind) {
378   switch (Kind) {
379 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
380   case TraitProperty::Enum:                                                    \
381     return Str;
382 #include "llvm/Frontend/OpenMP/OMPKinds.def"
383   }
384   llvm_unreachable("Unknown trait property!");
385 }
386 StringRef llvm::omp::getOpenMPContextTraitPropertyFullName(TraitProperty Kind) {
387   switch (Kind) {
388 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
389   case TraitProperty::Enum:                                                    \
390     return "(" #TraitSetEnum "," #TraitSelectorEnum "," Str ")";
391 #include "llvm/Frontend/OpenMP/OMPKinds.def"
392   }
393   llvm_unreachable("Unknown trait property!");
394 }
395 
396 bool llvm::omp::isValidTraitSelectorForTraitSet(TraitSelector Selector,
397                                                 TraitSet Set,
398                                                 bool &AllowsTraitScore,
399                                                 bool &RequiresProperty) {
400   AllowsTraitScore = Set != TraitSet::construct && Set != TraitSet::device;
401   switch (Selector) {
402 #define OMP_TRAIT_SELECTOR(Enum, TraitSetEnum, Str, ReqProp)                   \
403   case TraitSelector::Enum:                                                    \
404     RequiresProperty = ReqProp;                                                \
405     return Set == TraitSet::TraitSetEnum;
406 #include "llvm/Frontend/OpenMP/OMPKinds.def"
407   }
408   llvm_unreachable("Unknown trait selector!");
409 }
410 
411 bool llvm::omp::isValidTraitPropertyForTraitSetAndSelector(
412     TraitProperty Property, TraitSelector Selector, TraitSet Set) {
413   switch (Property) {
414 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
415   case TraitProperty::Enum:                                                    \
416     return Set == TraitSet::TraitSetEnum &&                                    \
417            Selector == TraitSelector::TraitSelectorEnum;
418 #include "llvm/Frontend/OpenMP/OMPKinds.def"
419   }
420   llvm_unreachable("Unknown trait property!");
421 }
422 
423 std::string llvm::omp::listOpenMPContextTraitSets() {
424   std::string S;
425 #define OMP_TRAIT_SET(Enum, Str)                                               \
426   if (StringRef(Str) != "invalid")                                             \
427     S.append("'").append(Str).append("'").append(" ");
428 #include "llvm/Frontend/OpenMP/OMPKinds.def"
429   S.pop_back();
430   return S;
431 }
432 
433 std::string llvm::omp::listOpenMPContextTraitSelectors(TraitSet Set) {
434   std::string S;
435 #define OMP_TRAIT_SELECTOR(Enum, TraitSetEnum, Str, ReqProp)                   \
436   if (TraitSet::TraitSetEnum == Set && StringRef(Str) != "Invalid")            \
437     S.append("'").append(Str).append("'").append(" ");
438 #include "llvm/Frontend/OpenMP/OMPKinds.def"
439   S.pop_back();
440   return S;
441 }
442 
443 std::string
444 llvm::omp::listOpenMPContextTraitProperties(TraitSet Set,
445                                             TraitSelector Selector) {
446   std::string S;
447 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
448   if (TraitSet::TraitSetEnum == Set &&                                         \
449       TraitSelector::TraitSelectorEnum == Selector &&                          \
450       StringRef(Str) != "invalid")                                             \
451     S.append("'").append(Str).append("'").append(" ");
452 #include "llvm/Frontend/OpenMP/OMPKinds.def"
453   if (S.empty())
454     return "<none>";
455   S.pop_back();
456   return S;
457 }
458