1//===- OMP.cpp ------ Collection of helpers for OpenMP --------------------===//
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
9#include "llvm/Frontend/OpenMP/OMP.h"
10
11#include "llvm/ADT/ArrayRef.h"
12#include "llvm/ADT/Sequence.h"
13#include "llvm/ADT/SmallSet.h"
14#include "llvm/ADT/SmallVector.h"
15#include "llvm/ADT/StringRef.h"
16#include "llvm/Demangle/Demangle.h"
17#include "llvm/Frontend/OpenMP/OMPIRBuilder.h"
18#include "llvm/Support/ErrorHandling.h"
19
20#include <algorithm>
21#include <cstdio>
22#include <iterator>
23#include <string>
24#include <type_traits>
25
26using namespace llvm;
27using namespace llvm::omp;
28
29#define GEN_DIRECTIVES_IMPL
30#include "llvm/Frontend/OpenMP/OMP.inc"
31
32static iterator_range<ArrayRef<Directive>::iterator>
33getFirstCompositeRange(iterator_range<ArrayRef<Directive>::iterator> Leafs) {
34 // OpenMP Spec 5.2: [17.3, 8-9]
35 // If directive-name-A and directive-name-B both correspond to loop-
36 // associated constructs then directive-name is a composite construct
37 // otherwise directive-name is a combined construct.
38 //
39 // In the list of leaf constructs, find the first loop-associated construct,
40 // this is the beginning of the returned range. Then, starting from the
41 // immediately following leaf construct, find the first sequence of adjacent
42 // loop-associated constructs. The last of those is the last one of the
43 // range, that is, the end of the range is one past that element.
44 // If such a sequence of adjacent loop-associated directives does not exist,
45 // return an empty range.
46 //
47 // The end of the returned range (including empty range) is intended to be
48 // a point from which the search for the next range could resume.
49 //
50 // Consequently, this function can't return a range with a single leaf
51 // construct in it.
52
53 auto firstLoopAssociated =
54 [](iterator_range<ArrayRef<Directive>::iterator> List) {
55 for (auto It = List.begin(), End = List.end(); It != End; ++It) {
56 if (getDirectiveAssociation(Dir: *It) == Association::LoopNest)
57 return It;
58 }
59 return List.end();
60 };
61
62 auto Empty = llvm::make_range(x: Leafs.end(), y: Leafs.end());
63
64 auto Begin = firstLoopAssociated(Leafs);
65 if (Begin == Leafs.end())
66 return Empty;
67
68 auto End =
69 firstLoopAssociated(llvm::make_range(x: std::next(x: Begin), y: Leafs.end()));
70 if (End == Leafs.end())
71 return Empty;
72
73 for (; End != Leafs.end(); ++End) {
74 if (getDirectiveAssociation(Dir: *End) != Association::LoopNest)
75 break;
76 }
77 return llvm::make_range(x: Begin, y: End);
78}
79
80static void
81collectPrivatizingConstructs(llvm::SmallSet<Directive, 16> &Constructs,
82 unsigned Version) {
83 llvm::SmallSet<Clause, 16> Privatizing;
84 for (auto C :
85 llvm::enum_seq_inclusive<Clause>(Begin: Clause::First_, End: Clause::Last_)) {
86 if (isPrivatizingClause(C))
87 Privatizing.insert(V: C);
88 }
89
90 for (auto D : llvm::enum_seq_inclusive<Directive>(Begin: Directive::First_,
91 End: Directive::Last_)) {
92 bool AllowsPrivatizing = llvm::any_of(Range&: Privatizing, P: [&](Clause C) {
93 return isAllowedClauseForDirective(D, C, Version);
94 });
95 if (AllowsPrivatizing)
96 Constructs.insert(V: D);
97 }
98}
99
100namespace llvm::omp {
101ArrayRef<Directive> getLeafConstructs(Directive D) {
102 auto Idx = static_cast<std::size_t>(D);
103 if (Idx >= Directive_enumSize)
104 return {};
105 const auto *Row = LeafConstructTable[LeafConstructTableOrdering[Idx]];
106 return ArrayRef(&Row[2], static_cast<int>(Row[1]));
107}
108
109ArrayRef<Directive> getLeafConstructsOrSelf(Directive D) {
110 if (auto Leafs = getLeafConstructs(D); !Leafs.empty())
111 return Leafs;
112 auto Idx = static_cast<size_t>(D);
113 assert(Idx < Directive_enumSize && "Invalid directive");
114 const auto *Row = LeafConstructTable[LeafConstructTableOrdering[Idx]];
115 // The first entry in the row is the directive itself.
116 return ArrayRef(&Row[0], &Row[0] + 1);
117}
118
119ArrayRef<Directive>
120getLeafOrCompositeConstructs(Directive D, SmallVectorImpl<Directive> &Output) {
121 using ArrayTy = ArrayRef<Directive>;
122 using IteratorTy = ArrayTy::iterator;
123 ArrayRef<Directive> Leafs = getLeafConstructsOrSelf(D);
124
125 IteratorTy Iter = Leafs.begin();
126 do {
127 auto Range = getFirstCompositeRange(Leafs: llvm::make_range(x: Iter, y: Leafs.end()));
128 // All directives before the range are leaf constructs.
129 for (; Iter != Range.begin(); ++Iter)
130 Output.push_back(Elt: *Iter);
131 if (!Range.empty()) {
132 Directive Comp =
133 getCompoundConstruct(Parts: ArrayTy(Range.begin(), Range.end()));
134 assert(Comp != OMPD_unknown);
135 Output.push_back(Elt: Comp);
136 Iter = Range.end();
137 // As of now, a composite construct must contain all constituent leaf
138 // constructs from some point until the end of all constituent leaf
139 // constructs.
140 assert(Iter == Leafs.end() && "Malformed directive");
141 }
142 } while (Iter != Leafs.end());
143
144 return Output;
145}
146
147Directive getCompoundConstruct(ArrayRef<Directive> Parts) {
148 if (Parts.empty())
149 return OMPD_unknown;
150
151 // Parts don't have to be leafs, so expand them into leafs first.
152 // Store the expanded leafs in the same format as rows in the leaf
153 // table (generated by tablegen).
154 SmallVector<Directive> RawLeafs(2);
155 for (Directive P : Parts) {
156 ArrayRef<Directive> Ls = getLeafConstructs(D: P);
157 if (!Ls.empty())
158 RawLeafs.append(in_start: Ls.begin(), in_end: Ls.end());
159 else
160 RawLeafs.push_back(Elt: P);
161 }
162
163 // RawLeafs will be used as key in the binary search. The search doesn't
164 // guarantee that the exact same entry will be found (since RawLeafs may
165 // not correspond to any compound directive). Because of that, we will
166 // need to compare the search result with the given set of leafs.
167 // Also, if there is only one leaf in the list, it corresponds to itself,
168 // no search is necessary.
169 auto GivenLeafs{ArrayRef<Directive>(RawLeafs).drop_front(N: 2)};
170 if (GivenLeafs.size() == 1)
171 return GivenLeafs.front();
172 RawLeafs[1] = static_cast<Directive>(GivenLeafs.size());
173
174 auto Iter = std::lower_bound(
175 first: LeafConstructTable, last: LeafConstructTableEndDirective,
176 val: static_cast<std::decay_t<decltype(*LeafConstructTable)>>(RawLeafs.data()),
177 comp: [](const llvm::omp::Directive *RowA, const llvm::omp::Directive *RowB) {
178 const auto *BeginA = &RowA[2];
179 const auto *EndA = BeginA + static_cast<int>(RowA[1]);
180 const auto *BeginB = &RowB[2];
181 const auto *EndB = BeginB + static_cast<int>(RowB[1]);
182 if (BeginA == EndA && BeginB == EndB)
183 return static_cast<int>(RowA[0]) < static_cast<int>(RowB[0]);
184 return std::lexicographical_compare(first1: BeginA, last1: EndA, first2: BeginB, last2: EndB);
185 });
186
187 if (Iter == std::end(arr: LeafConstructTable))
188 return OMPD_unknown;
189
190 // Verify that we got a match.
191 Directive Found = (*Iter)[0];
192 ArrayRef<Directive> FoundLeafs = getLeafConstructs(D: Found);
193 if (FoundLeafs == GivenLeafs)
194 return Found;
195 return OMPD_unknown;
196}
197
198bool isLeafConstruct(Directive D) { return getLeafConstructs(D).empty(); }
199
200bool isCompositeConstruct(Directive D) {
201 ArrayRef<Directive> Leafs = getLeafConstructsOrSelf(D);
202 if (Leafs.size() <= 1)
203 return false;
204 auto Range = getFirstCompositeRange(Leafs);
205 return Range.begin() == Leafs.begin() && Range.end() == Leafs.end();
206}
207
208bool isCombinedConstruct(Directive D) {
209 // OpenMP Spec 5.2: [17.3, 9-10]
210 // Otherwise directive-name is a combined construct.
211 return !getLeafConstructs(D).empty() && !isCompositeConstruct(D);
212}
213
214ArrayRef<unsigned> getOpenMPVersions() {
215 static unsigned Versions[]{31, 40, 45, 50, 51, 52, 60, 61};
216 return Versions;
217}
218
219bool isPrivatizingConstruct(Directive D, unsigned Version) {
220 static llvm::SmallSet<Directive, 16> Privatizing;
221 [[maybe_unused]] static bool Init =
222 (collectPrivatizingConstructs(Constructs&: Privatizing, Version), true);
223
224 // As of OpenMP 6.0, privatizing constructs (with the test being if they
225 // allow a privatizing clause) are: dispatch, distribute, do, for, loop,
226 // parallel, scope, sections, simd, single, target, target_data, task,
227 // taskgroup, taskloop, and teams.
228 return llvm::is_contained(Range&: Privatizing, Element: D);
229}
230
231std::string prettifyFunctionName(StringRef FunctionName) {
232 // Internalized functions have the right name, but simply a suffix.
233 if (FunctionName.ends_with(Suffix: ".internalized"))
234 return FunctionName.drop_back(N: sizeof("internalized")).str() +
235 " (internalized)";
236 unsigned LineNo = 0;
237 auto ParentName = deconstructOpenMPKernelName(KernelName: FunctionName, LineNo);
238 if (LineNo == 0)
239 return FunctionName.str();
240 return ("omp target in " + ParentName + " @ " + std::to_string(val: LineNo) +
241 " (" + FunctionName + ")")
242 .str();
243}
244
245std::string deconstructOpenMPKernelName(StringRef KernelName,
246 unsigned &LineNo) {
247
248 // Only handle functions with an OpenMP kernel prefix for now. Naming scheme:
249 // __omp_offloading_<hex_hash1>_<hex_hash2>_<name>_l<line>_[<count>_]<suffix>
250 if (!KernelName.starts_with(Prefix: TargetRegionEntryInfo::KernelNamePrefix))
251 return "";
252
253 auto PrettyName = KernelName.drop_front(
254 N: sizeof(TargetRegionEntryInfo::KernelNamePrefix) - /*'\0'*/ 1);
255 for (int I = 0; I < 3; ++I) {
256 PrettyName = PrettyName.drop_while(F: [](char c) { return c != '_'; });
257 PrettyName = PrettyName.drop_front();
258 }
259
260 // Look for the last '_l<line>'.
261 size_t LineIdx = PrettyName.rfind(Str: "_l");
262 if (LineIdx == StringRef::npos)
263 return "";
264 if (PrettyName.drop_front(N: LineIdx + 2).consumeInteger(Radix: 10, Result&: LineNo))
265 return "";
266 return demangle(MangledName: PrettyName.take_front(N: LineIdx));
267}
268} // namespace llvm::omp
269