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.insert(IsDeviceCompilation ? TraitProperty::device_kind_nohost
30                                           : TraitProperty::device_kind_host);
31   switch (TargetTriple.getArch()) {
32   case Triple::arm:
33   case Triple::armeb:
34   case Triple::aarch64:
35   case Triple::aarch64_be:
36   case Triple::aarch64_32:
37   case Triple::mips:
38   case Triple::mipsel:
39   case Triple::mips64:
40   case Triple::mips64el:
41   case Triple::ppc:
42   case Triple::ppc64:
43   case Triple::ppc64le:
44   case Triple::x86:
45   case Triple::x86_64:
46     ActiveTraits.insert(TraitProperty::device_kind_cpu);
47     break;
48   case Triple::amdgcn:
49   case Triple::nvptx:
50   case Triple::nvptx64:
51     ActiveTraits.insert(TraitProperty::device_kind_gpu);
52     break;
53   default:
54     break;
55   }
56 
57   // Add the appropriate device architecture trait based on the triple.
58 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
59   if (TraitSelector::TraitSelectorEnum == TraitSelector::device_arch)          \
60     if (TargetTriple.getArch() == TargetTriple.getArchTypeForLLVMName(Str))    \
61       ActiveTraits.insert(TraitProperty::Enum);
62 #include "llvm/Frontend/OpenMP/OMPKinds.def"
63 
64   // TODO: What exactly do we want to see as device ISA trait?
65   //       The discussion on the list did not seem to have come to an agreed
66   //       upon solution.
67 
68   // LLVM is the "OpenMP vendor" but we could also interpret vendor as the
69   // target vendor.
70   ActiveTraits.insert(TraitProperty::implementation_vendor_llvm);
71 
72   // The user condition true is accepted but not false.
73   ActiveTraits.insert(TraitProperty::user_condition_true);
74 
75   // This is for sure some device.
76   ActiveTraits.insert(TraitProperty::device_kind_any);
77 
78   LLVM_DEBUG({
79     dbgs() << "[" << DEBUG_TYPE
80            << "] New OpenMP context with the following properties:\n";
81     for (auto &Property : ActiveTraits)
82       dbgs() << "\t " << getOpenMPContextTraitPropertyFullName(Property)
83              << "\n";
84   });
85 }
86 
87 /// Return true if \p C0 is a subset of \p C1. Note that both arrays are
88 /// expected to be sorted.
89 template <typename T> static bool isSubset(ArrayRef<T> C0, ArrayRef<T> C1) {
90 #ifdef EXPENSIVE_CHECKS
91   assert(std::is_sorted(C0.begin(), C0.end()) &&
92          std::is_sorted(C1.begin(), C1.end()) && "Expected sorted arrays!");
93 #endif
94   if (C0.size() > C1.size())
95     return false;
96   auto It0 = C0.begin(), End0 = C0.end();
97   auto It1 = C1.begin(), End1 = C1.end();
98   while (It0 != End0) {
99     if (It1 == End1)
100       return false;
101     if (*It0 == *It1) {
102       ++It0;
103       ++It1;
104       continue;
105     }
106     ++It0;
107   }
108   return true;
109 }
110 
111 /// Return true if \p C0 is a strict subset of \p C1. Note that both arrays are
112 /// expected to be sorted.
113 template <typename T>
114 static bool isStrictSubset(ArrayRef<T> C0, ArrayRef<T> C1) {
115   if (C0.size() >= C1.size())
116     return false;
117   return isSubset<T>(C0, C1);
118 }
119 
120 static bool isStrictSubset(const VariantMatchInfo &VMI0,
121                            const VariantMatchInfo &VMI1) {
122   // If all required traits are a strict subset and the ordered vectors storing
123   // the construct traits, we say it is a strict subset. Note that the latter
124   // relation is not required to be strict.
125   return set_is_strict_subset(VMI0.RequiredTraits, VMI1.RequiredTraits) &&
126          isSubset<TraitProperty>(VMI0.ConstructTraits, VMI1.ConstructTraits);
127 }
128 
129 static int isVariantApplicableInContextHelper(
130     const VariantMatchInfo &VMI, const OMPContext &Ctx,
131     SmallVectorImpl<unsigned> *ConstructMatches) {
132 
133   for (TraitProperty Property : VMI.RequiredTraits) {
134 
135     bool IsActiveTrait = Ctx.ActiveTraits.count(Property);
136     if (!IsActiveTrait) {
137       LLVM_DEBUG(dbgs() << "[" << DEBUG_TYPE << "] Property "
138                         << getOpenMPContextTraitPropertyName(Property)
139                         << " was not in the OpenMP context.\n");
140       return false;
141     }
142   }
143 
144   // We could use isSubset here but we also want to record the match locations.
145   unsigned ConstructIdx = 0, NoConstructTraits = Ctx.ConstructTraits.size();
146   for (TraitProperty Property : VMI.ConstructTraits) {
147     assert(getOpenMPContextTraitSetForProperty(Property) ==
148                TraitSet::construct &&
149            "Variant context is ill-formed!");
150 
151     // Verify the nesting.
152     bool FoundInOrder = false;
153     while (!FoundInOrder && ConstructIdx != NoConstructTraits)
154       FoundInOrder = (Ctx.ConstructTraits[ConstructIdx++] == Property);
155     if (ConstructMatches)
156       ConstructMatches->push_back(ConstructIdx - 1);
157 
158     if (!FoundInOrder) {
159       LLVM_DEBUG(dbgs() << "[" << DEBUG_TYPE << "] Construct property "
160                         << getOpenMPContextTraitPropertyName(Property)
161                         << " was not nested properly.\n");
162       return false;
163     }
164 
165     // TODO: Verify SIMD
166   }
167 
168   assert(isSubset<TraitProperty>(VMI.ConstructTraits, Ctx.ConstructTraits) &&
169          "Broken invariant!");
170   return true;
171 }
172 
173 bool llvm::omp::isVariantApplicableInContext(const VariantMatchInfo &VMI,
174                                              const OMPContext &Ctx) {
175   return isVariantApplicableInContextHelper(VMI, Ctx, nullptr);
176 }
177 
178 static APInt getVariantMatchScore(const VariantMatchInfo &VMI,
179                                   const OMPContext &Ctx,
180                                   SmallVectorImpl<unsigned> &ConstructMatches) {
181   APInt Score(64, 1);
182 
183   unsigned NoConstructTraits = VMI.ConstructTraits.size();
184   for (TraitProperty Property : VMI.RequiredTraits) {
185     // If there is a user score attached, use it.
186     if (VMI.ScoreMap.count(Property)) {
187       const APInt &UserScore = VMI.ScoreMap.lookup(Property);
188       assert(UserScore.uge(0) && "Expect non-negative user scores!");
189       Score += UserScore.getZExtValue();
190       continue;
191     }
192 
193     switch (getOpenMPContextTraitSetForProperty(Property)) {
194     case TraitSet::construct:
195       // We handle the construct traits later via the VMI.ConstructTraits
196       // container.
197       continue;
198     case TraitSet::implementation:
199       // No effect on the score (implementation defined).
200       continue;
201     case TraitSet::user:
202       // No effect on the score.
203       continue;
204     case TraitSet::device:
205       // Handled separately below.
206       break;
207     case TraitSet::invalid:
208       llvm_unreachable("Unknown trait set is not to be used!");
209     }
210 
211     // device={kind(any)} is "as if" no kind selector was specified.
212     if (Property == TraitProperty::device_kind_any)
213       continue;
214 
215     switch (getOpenMPContextTraitSelectorForProperty(Property)) {
216     case TraitSelector::device_kind:
217       Score += (1ULL << (NoConstructTraits + 0));
218       continue;
219     case TraitSelector::device_arch:
220       Score += (1ULL << (NoConstructTraits + 1));
221       continue;
222     case TraitSelector::device_isa:
223       Score += (1ULL << (NoConstructTraits + 2));
224       continue;
225     default:
226       continue;
227     }
228   }
229 
230   unsigned ConstructIdx = 0;
231   assert(NoConstructTraits == ConstructMatches.size() &&
232          "Mismatch in the construct traits!");
233   for (TraitProperty Property : VMI.ConstructTraits) {
234     assert(getOpenMPContextTraitSetForProperty(Property) ==
235                TraitSet::construct &&
236            "Ill-formed variant match info!");
237     (void)Property;
238     // ConstructMatches is the position p - 1 and we need 2^(p-1).
239     Score += (1ULL << ConstructMatches[ConstructIdx++]);
240   }
241 
242   LLVM_DEBUG(dbgs() << "[" << DEBUG_TYPE << "] Variant has a score of " << Score
243                     << "\n");
244   return Score;
245 }
246 
247 int llvm::omp::getBestVariantMatchForContext(
248     const SmallVectorImpl<VariantMatchInfo> &VMIs, const OMPContext &Ctx) {
249 
250   APInt BestScore(64, 0);
251   int BestVMIIdx = -1;
252   const VariantMatchInfo *BestVMI = nullptr;
253 
254   for (unsigned u = 0, e = VMIs.size(); u < e; ++u) {
255     const VariantMatchInfo &VMI = VMIs[u];
256 
257     SmallVector<unsigned, 8> ConstructMatches;
258     // If the variant is not applicable its not the best.
259     if (!isVariantApplicableInContextHelper(VMI, Ctx, &ConstructMatches))
260       continue;
261     // Check if its clearly not the best.
262     APInt Score = getVariantMatchScore(VMI, Ctx, ConstructMatches);
263     if (Score.ult(BestScore))
264       continue;
265     // Equal score need subset checks.
266     if (Score.eq(BestScore)) {
267       // Strict subset are never best.
268       if (isStrictSubset(VMI, *BestVMI))
269         continue;
270       // Same score and the current best is no strict subset so we keep it.
271       if (!isStrictSubset(*BestVMI, VMI))
272         continue;
273     }
274     // New best found.
275     BestVMI = &VMI;
276     BestVMIIdx = u;
277     BestScore = Score;
278   }
279 
280   return BestVMIIdx;
281 }
282 
283 TraitSet llvm::omp::getOpenMPContextTraitSetKind(StringRef S) {
284   return StringSwitch<TraitSet>(S)
285 #define OMP_TRAIT_SET(Enum, Str) .Case(Str, TraitSet::Enum)
286 #include "llvm/Frontend/OpenMP/OMPKinds.def"
287       .Default(TraitSet::invalid);
288 }
289 
290 TraitSet
291 llvm::omp::getOpenMPContextTraitSetForSelector(TraitSelector Selector) {
292   switch (Selector) {
293 #define OMP_TRAIT_SELECTOR(Enum, TraitSetEnum, Str, ReqProp)                   \
294   case TraitSelector::Enum:                                                    \
295     return TraitSet::TraitSetEnum;
296 #include "llvm/Frontend/OpenMP/OMPKinds.def"
297   }
298   llvm_unreachable("Unknown trait selector!");
299 }
300 TraitSet
301 llvm::omp::getOpenMPContextTraitSetForProperty(TraitProperty Property) {
302   switch (Property) {
303 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
304   case TraitProperty::Enum:                                                    \
305     return TraitSet::TraitSetEnum;
306 #include "llvm/Frontend/OpenMP/OMPKinds.def"
307   }
308   llvm_unreachable("Unknown trait set!");
309 }
310 StringRef llvm::omp::getOpenMPContextTraitSetName(TraitSet Kind) {
311   switch (Kind) {
312 #define OMP_TRAIT_SET(Enum, Str)                                               \
313   case TraitSet::Enum:                                                         \
314     return Str;
315 #include "llvm/Frontend/OpenMP/OMPKinds.def"
316   }
317   llvm_unreachable("Unknown trait set!");
318 }
319 
320 TraitSelector llvm::omp::getOpenMPContextTraitSelectorKind(StringRef S) {
321   return StringSwitch<TraitSelector>(S)
322 #define OMP_TRAIT_SELECTOR(Enum, TraitSetEnum, Str, ReqProp)                   \
323   .Case(Str, TraitSelector::Enum)
324 #include "llvm/Frontend/OpenMP/OMPKinds.def"
325       .Default(TraitSelector::invalid);
326 }
327 TraitSelector
328 llvm::omp::getOpenMPContextTraitSelectorForProperty(TraitProperty Property) {
329   switch (Property) {
330 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
331   case TraitProperty::Enum:                                                    \
332     return TraitSelector::TraitSelectorEnum;
333 #include "llvm/Frontend/OpenMP/OMPKinds.def"
334   }
335   llvm_unreachable("Unknown trait set!");
336 }
337 StringRef llvm::omp::getOpenMPContextTraitSelectorName(TraitSelector Kind) {
338   switch (Kind) {
339 #define OMP_TRAIT_SELECTOR(Enum, TraitSetEnum, Str, ReqProp)                   \
340   case TraitSelector::Enum:                                                    \
341     return Str;
342 #include "llvm/Frontend/OpenMP/OMPKinds.def"
343   }
344   llvm_unreachable("Unknown trait selector!");
345 }
346 
347 TraitProperty llvm::omp::getOpenMPContextTraitPropertyKind(TraitSet Set,
348                                                            StringRef S) {
349 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
350   if (Set == TraitSet::TraitSetEnum && Str == S)                               \
351     return TraitProperty::Enum;
352 #include "llvm/Frontend/OpenMP/OMPKinds.def"
353   return TraitProperty::invalid;
354 }
355 TraitProperty
356 llvm::omp::getOpenMPContextTraitPropertyForSelector(TraitSelector Selector) {
357   return StringSwitch<TraitProperty>(
358              getOpenMPContextTraitSelectorName(Selector))
359 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
360   .Case(Str, Selector == TraitSelector::TraitSelectorEnum                      \
361                  ? TraitProperty::Enum                                         \
362                  : TraitProperty::invalid)
363 #include "llvm/Frontend/OpenMP/OMPKinds.def"
364       .Default(TraitProperty::invalid);
365 }
366 StringRef llvm::omp::getOpenMPContextTraitPropertyName(TraitProperty Kind) {
367   switch (Kind) {
368 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
369   case TraitProperty::Enum:                                                    \
370     return Str;
371 #include "llvm/Frontend/OpenMP/OMPKinds.def"
372   }
373   llvm_unreachable("Unknown trait property!");
374 }
375 StringRef llvm::omp::getOpenMPContextTraitPropertyFullName(TraitProperty Kind) {
376   switch (Kind) {
377 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
378   case TraitProperty::Enum:                                                    \
379     return "(" #TraitSetEnum "," #TraitSelectorEnum "," Str ")";
380 #include "llvm/Frontend/OpenMP/OMPKinds.def"
381   }
382   llvm_unreachable("Unknown trait property!");
383 }
384 
385 bool llvm::omp::isValidTraitSelectorForTraitSet(TraitSelector Selector,
386                                                 TraitSet Set,
387                                                 bool &AllowsTraitScore,
388                                                 bool &RequiresProperty) {
389   AllowsTraitScore = Set != TraitSet::construct && Set != TraitSet::device;
390   switch (Selector) {
391 #define OMP_TRAIT_SELECTOR(Enum, TraitSetEnum, Str, ReqProp)                   \
392   case TraitSelector::Enum:                                                    \
393     RequiresProperty = ReqProp;                                                \
394     return Set == TraitSet::TraitSetEnum;
395 #include "llvm/Frontend/OpenMP/OMPKinds.def"
396   }
397   llvm_unreachable("Unknown trait selector!");
398 }
399 
400 bool llvm::omp::isValidTraitPropertyForTraitSetAndSelector(
401     TraitProperty Property, TraitSelector Selector, TraitSet Set) {
402   switch (Property) {
403 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
404   case TraitProperty::Enum:                                                    \
405     return Set == TraitSet::TraitSetEnum &&                                    \
406            Selector == TraitSelector::TraitSelectorEnum;
407 #include "llvm/Frontend/OpenMP/OMPKinds.def"
408   }
409   llvm_unreachable("Unknown trait property!");
410 }
411 
412 std::string llvm::omp::listOpenMPContextTraitSets() {
413   std::string S;
414 #define OMP_TRAIT_SET(Enum, Str)                                               \
415   if (StringRef(Str) != "invalid")                                             \
416     S.append("'").append(Str).append("'").append(" ");
417 #include "llvm/Frontend/OpenMP/OMPKinds.def"
418   S.pop_back();
419   return S;
420 }
421 
422 std::string llvm::omp::listOpenMPContextTraitSelectors(TraitSet Set) {
423   std::string S;
424 #define OMP_TRAIT_SELECTOR(Enum, TraitSetEnum, Str, ReqProp)                   \
425   if (TraitSet::TraitSetEnum == Set && StringRef(Str) != "Invalid")            \
426     S.append("'").append(Str).append("'").append(" ");
427 #include "llvm/Frontend/OpenMP/OMPKinds.def"
428   S.pop_back();
429   return S;
430 }
431 
432 std::string
433 llvm::omp::listOpenMPContextTraitProperties(TraitSet Set,
434                                             TraitSelector Selector) {
435   std::string S;
436 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
437   if (TraitSet::TraitSetEnum == Set &&                                         \
438       TraitSelector::TraitSelectorEnum == Selector &&                          \
439       StringRef(Str) != "invalid")                                             \
440     S.append("'").append(Str).append("'").append(" ");
441 #include "llvm/Frontend/OpenMP/OMPKinds.def"
442   S.pop_back();
443   return S;
444 }
445