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 TraitSet
290 llvm::omp::getOpenMPContextTraitSetForProperty(TraitProperty Property) {
291   switch (Property) {
292 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
293   case TraitProperty::Enum:                                                    \
294     return TraitSet::TraitSetEnum;
295 #include "llvm/Frontend/OpenMP/OMPKinds.def"
296   }
297   llvm_unreachable("Unknown trait set!");
298 }
299 StringRef llvm::omp::getOpenMPContextTraitSetName(TraitSet Kind) {
300   switch (Kind) {
301 #define OMP_TRAIT_SET(Enum, Str)                                               \
302   case TraitSet::Enum:                                                         \
303     return Str;
304 #include "llvm/Frontend/OpenMP/OMPKinds.def"
305   }
306   llvm_unreachable("Unknown trait set!");
307 }
308 
309 TraitSelector llvm::omp::getOpenMPContextTraitSelectorKind(StringRef S) {
310   return StringSwitch<TraitSelector>(S)
311 #define OMP_TRAIT_SELECTOR(Enum, TraitSetEnum, Str, ReqProp)                   \
312   .Case(Str, TraitSelector::Enum)
313 #include "llvm/Frontend/OpenMP/OMPKinds.def"
314       .Default(TraitSelector::invalid);
315 }
316 TraitSelector
317 llvm::omp::getOpenMPContextTraitSelectorForProperty(TraitProperty Property) {
318   switch (Property) {
319 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
320   case TraitProperty::Enum:                                                    \
321     return TraitSelector::TraitSelectorEnum;
322 #include "llvm/Frontend/OpenMP/OMPKinds.def"
323   }
324   llvm_unreachable("Unknown trait set!");
325 }
326 StringRef llvm::omp::getOpenMPContextTraitSelectorName(TraitSelector Kind) {
327   switch (Kind) {
328 #define OMP_TRAIT_SELECTOR(Enum, TraitSetEnum, Str, ReqProp)                   \
329   case TraitSelector::Enum:                                                    \
330     return Str;
331 #include "llvm/Frontend/OpenMP/OMPKinds.def"
332   }
333   llvm_unreachable("Unknown trait selector!");
334 }
335 
336 TraitProperty llvm::omp::getOpenMPContextTraitPropertyKind(
337     TraitSet Set, TraitSelector Selector, StringRef S) {
338 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
339   if (Set == TraitSet::TraitSetEnum &&                                         \
340       Selector == TraitSelector::TraitSelectorEnum && Str == S)                \
341     return TraitProperty::Enum;
342 #include "llvm/Frontend/OpenMP/OMPKinds.def"
343   return TraitProperty::invalid;
344 }
345 TraitProperty
346 llvm::omp::getOpenMPContextTraitPropertyForSelector(TraitSelector Selector) {
347   return StringSwitch<TraitProperty>(
348              getOpenMPContextTraitSelectorName(Selector))
349 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
350   .Case(Str, Selector == TraitSelector::TraitSelectorEnum                      \
351                  ? TraitProperty::Enum                                         \
352                  : TraitProperty::invalid)
353 #include "llvm/Frontend/OpenMP/OMPKinds.def"
354       .Default(TraitProperty::invalid);
355 }
356 StringRef llvm::omp::getOpenMPContextTraitPropertyName(TraitProperty Kind) {
357   switch (Kind) {
358 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
359   case TraitProperty::Enum:                                                    \
360     return Str;
361 #include "llvm/Frontend/OpenMP/OMPKinds.def"
362   }
363   llvm_unreachable("Unknown trait property!");
364 }
365 StringRef llvm::omp::getOpenMPContextTraitPropertyFullName(TraitProperty Kind) {
366   switch (Kind) {
367 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
368   case TraitProperty::Enum:                                                    \
369     return "(" #TraitSetEnum "," #TraitSelectorEnum "," Str ")";
370 #include "llvm/Frontend/OpenMP/OMPKinds.def"
371   }
372   llvm_unreachable("Unknown trait property!");
373 }
374 
375 bool llvm::omp::isValidTraitSelectorForTraitSet(TraitSelector Selector,
376                                                 TraitSet Set,
377                                                 bool &AllowsTraitScore,
378                                                 bool &RequiresProperty) {
379   AllowsTraitScore = Set != TraitSet::construct && Set != TraitSet::device;
380   switch (Selector) {
381 #define OMP_TRAIT_SELECTOR(Enum, TraitSetEnum, Str, ReqProp)                   \
382   case TraitSelector::Enum:                                                    \
383     RequiresProperty = ReqProp;                                                \
384     return Set == TraitSet::TraitSetEnum;
385 #include "llvm/Frontend/OpenMP/OMPKinds.def"
386   }
387   llvm_unreachable("Unknown trait selector!");
388 }
389 
390 bool llvm::omp::isValidTraitPropertyForTraitSetAndSelector(
391     TraitProperty Property, TraitSelector Selector, TraitSet Set) {
392   switch (Property) {
393 #define OMP_TRAIT_PROPERTY(Enum, TraitSetEnum, TraitSelectorEnum, Str)         \
394   case TraitProperty::Enum:                                                    \
395     return Set == TraitSet::TraitSetEnum &&                                    \
396            Selector == TraitSelector::TraitSelectorEnum;
397 #include "llvm/Frontend/OpenMP/OMPKinds.def"
398   }
399   llvm_unreachable("Unknown trait property!");
400 }
401