LLVM 20.0.0git
ConstructDecompositionT.h
Go to the documentation of this file.
1//===- ConstructDecompositionT.h -- Decomposing compound constructs -------===//
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// Given a compound construct with a set of clauses, generate the list of
9// constituent leaf constructs, each with a list of clauses that apply to it.
10//
11// Note: Clauses that are not originally present, but that are implied by the
12// OpenMP spec are materialized, and are present in the output.
13//
14// Note: Composite constructs will also be broken up into leaf constructs.
15// If composite constructs require processing as a whole, the lists of clauses
16// for each leaf constituent should be merged.
17//===----------------------------------------------------------------------===//
18#ifndef LLVM_FRONTEND_OPENMP_CONSTRUCTDECOMPOSITIONT_H
19#define LLVM_FRONTEND_OPENMP_CONSTRUCTDECOMPOSITIONT_H
20
21#include "llvm/ADT/ArrayRef.h"
22#include "llvm/ADT/STLExtras.h"
27
28#include <iterator>
29#include <list>
30#include <optional>
31#include <tuple>
32#include <type_traits>
33#include <unordered_map>
34#include <unordered_set>
35#include <utility>
36#include <variant>
37
39 static llvm::omp::Directive worksharing[] = {
40 llvm::omp::Directive::OMPD_do, llvm::omp::Directive::OMPD_for,
41 llvm::omp::Directive::OMPD_scope, llvm::omp::Directive::OMPD_sections,
42 llvm::omp::Directive::OMPD_single, llvm::omp::Directive::OMPD_workshare,
43 };
44 return worksharing;
45}
46
48 static llvm::omp::Directive worksharingLoop[] = {
49 llvm::omp::Directive::OMPD_do,
50 llvm::omp::Directive::OMPD_for,
51 };
52 return worksharingLoop;
53}
54
55namespace detail {
56template <typename Container, typename Predicate>
57typename std::remove_reference_t<Container>::iterator
58find_unique(Container &&container, Predicate &&pred) {
59 auto first = std::find_if(container.begin(), container.end(), pred);
60 if (first == container.end())
61 return first;
62 auto second = std::find_if(std::next(first), container.end(), pred);
63 if (second == container.end())
64 return first;
65 return container.end();
66}
67} // namespace detail
68
69namespace tomp {
70
71// ClauseType - Either instance of ClauseT, or a type derived from ClauseT.
72//
73// This is the clause representation in the code using this infrastructure.
74//
75// HelperType - A class that implements two member functions:
76//
77// // Return the base object of the given object, if any.
78// std::optional<Object> getBaseObject(const Object &object) const
79// // Return the iteration variable of the outermost loop associated
80// // with the construct being worked on, if any.
81// std::optional<Object> getLoopIterVar() const
82template <typename ClauseType, typename HelperType>
84 using ClauseTy = ClauseType;
85
86 using TypeTy = typename ClauseTy::TypeTy;
87 using IdTy = typename ClauseTy::IdTy;
88 using ExprTy = typename ClauseTy::ExprTy;
89 using HelperTy = HelperType;
91
92 using ClauseSet = std::unordered_set<const ClauseTy *>;
93
94 ConstructDecompositionT(uint32_t ver, HelperType &helper,
95 llvm::omp::Directive dir,
97 : version(ver), construct(dir), helper(helper) {
98 for (const ClauseTy &clause : clauses)
99 nodes.push_back(&clause);
100
101 bool success = split();
102 if (!success)
103 return;
104
105 // Copy the individual leaf directives with their clauses to the
106 // output list. Copy by value, since we don't own the storage
107 // with the input clauses, and the internal representation uses
108 // clause addresses.
109 for (auto &leaf : leafs) {
110 output.push_back({leaf.id, {}});
111 auto &out = output.back();
112 for (const ClauseTy *c : leaf.clauses)
113 out.clauses.push_back(*c);
114 }
115 }
116
118
119private:
120 bool split();
121
122 struct LeafReprInternal {
123 llvm::omp::Directive id = llvm::omp::Directive::OMPD_unknown;
125 };
126
127 LeafReprInternal *findDirective(llvm::omp::Directive dirId) {
128 auto found = llvm::find_if(
129 leafs, [&](const LeafReprInternal &leaf) { return leaf.id == dirId; });
130 return found != leafs.end() ? &*found : nullptr;
131 }
132
133 ClauseSet *findClausesWith(const ObjectTy &object) {
134 if (auto found = syms.find(object.id()); found != syms.end())
135 return &found->second;
136 return nullptr;
137 }
138
139 template <typename S>
140 ClauseTy *makeClause(llvm::omp::Clause clauseId, S &&specific) {
141 implicit.push_back(typename ClauseTy::BaseT{clauseId, std::move(specific)});
142 return &implicit.back();
143 }
144
145 void addClauseSymsToMap(const ObjectTy &object, const ClauseTy *);
146 void addClauseSymsToMap(const tomp::ObjectListT<IdTy, ExprTy> &objects,
147 const ClauseTy *);
148 void addClauseSymsToMap(const TypeTy &item, const ClauseTy *);
149 void addClauseSymsToMap(const ExprTy &item, const ClauseTy *);
150 void addClauseSymsToMap(const tomp::clause::MapT<TypeTy, IdTy, ExprTy> &item,
151 const ClauseTy *);
152
153 template <typename U>
154 void addClauseSymsToMap(const std::optional<U> &item, const ClauseTy *);
155 template <typename U>
156 void addClauseSymsToMap(const tomp::ListT<U> &item, const ClauseTy *);
157 template <typename... U, size_t... Is>
158 void addClauseSymsToMap(const std::tuple<U...> &item, const ClauseTy *,
159 std::index_sequence<Is...> = {});
160 template <typename U>
161 std::enable_if_t<std::is_enum_v<llvm::remove_cvref_t<U>>, void>
162 addClauseSymsToMap(U &&item, const ClauseTy *);
163
164 template <typename U>
165 std::enable_if_t<llvm::remove_cvref_t<U>::EmptyTrait::value, void>
166 addClauseSymsToMap(U &&item, const ClauseTy *);
167
168 template <typename U>
169 std::enable_if_t<llvm::remove_cvref_t<U>::IncompleteTrait::value, void>
170 addClauseSymsToMap(U &&item, const ClauseTy *);
171
172 template <typename U>
173 std::enable_if_t<llvm::remove_cvref_t<U>::WrapperTrait::value, void>
174 addClauseSymsToMap(U &&item, const ClauseTy *);
175
176 template <typename U>
177 std::enable_if_t<llvm::remove_cvref_t<U>::TupleTrait::value, void>
178 addClauseSymsToMap(U &&item, const ClauseTy *);
179
180 template <typename U>
181 std::enable_if_t<llvm::remove_cvref_t<U>::UnionTrait::value, void>
182 addClauseSymsToMap(U &&item, const ClauseTy *);
183
184 // Apply a clause to the only directive that allows it. If there are no
185 // directives that allow it, or if there is more that one, do not apply
186 // anything and return false, otherwise return true.
187 bool applyToUnique(const ClauseTy *node);
188
189 // Apply a clause to the first directive in given range that allows it.
190 // If such a directive does not exist, return false, otherwise return true.
191 template <typename Iterator>
192 bool applyToFirst(const ClauseTy *node, llvm::iterator_range<Iterator> range);
193
194 // Apply a clause to the innermost directive that allows it. If such a
195 // directive does not exist, return false, otherwise return true.
196 bool applyToInnermost(const ClauseTy *node);
197
198 // Apply a clause to the outermost directive that allows it. If such a
199 // directive does not exist, return false, otherwise return true.
200 bool applyToOutermost(const ClauseTy *node);
201
202 template <typename Predicate>
203 bool applyIf(const ClauseTy *node, Predicate shouldApply);
204
205 bool applyToAll(const ClauseTy *node);
206
207 template <typename Clause>
208 bool applyClause(Clause &&clause, const ClauseTy *node);
209
210 bool applyClause(const tomp::clause::CollapseT<TypeTy, IdTy, ExprTy> &clause,
211 const ClauseTy *);
212 bool applyClause(const tomp::clause::PrivateT<TypeTy, IdTy, ExprTy> &clause,
213 const ClauseTy *);
214 bool
216 const ClauseTy *);
217 bool
218 applyClause(const tomp::clause::LastprivateT<TypeTy, IdTy, ExprTy> &clause,
219 const ClauseTy *);
220 bool applyClause(const tomp::clause::SharedT<TypeTy, IdTy, ExprTy> &clause,
221 const ClauseTy *);
222 bool applyClause(const tomp::clause::DefaultT<TypeTy, IdTy, ExprTy> &clause,
223 const ClauseTy *);
224 bool
225 applyClause(const tomp::clause::ThreadLimitT<TypeTy, IdTy, ExprTy> &clause,
226 const ClauseTy *);
227 bool applyClause(const tomp::clause::OrderT<TypeTy, IdTy, ExprTy> &clause,
228 const ClauseTy *);
229 bool applyClause(const tomp::clause::AllocateT<TypeTy, IdTy, ExprTy> &clause,
230 const ClauseTy *);
231 bool applyClause(const tomp::clause::ReductionT<TypeTy, IdTy, ExprTy> &clause,
232 const ClauseTy *);
233 bool applyClause(const tomp::clause::IfT<TypeTy, IdTy, ExprTy> &clause,
234 const ClauseTy *);
235 bool applyClause(const tomp::clause::LinearT<TypeTy, IdTy, ExprTy> &clause,
236 const ClauseTy *);
237 bool applyClause(const tomp::clause::NowaitT<TypeTy, IdTy, ExprTy> &clause,
238 const ClauseTy *);
239 bool
241 const ClauseTy *);
242
243 uint32_t version;
244 llvm::omp::Directive construct;
245 HelperType &helper;
246 ListT<LeafReprInternal> leafs;
248 std::list<ClauseTy> implicit; // Container for materialized implicit clauses.
249 // Inserting must preserve element addresses.
250 std::unordered_map<IdTy, ClauseSet> syms;
251 std::unordered_set<IdTy> mapBases;
252};
253
254// Deduction guide
255template <typename ClauseType, typename HelperType>
256ConstructDecompositionT(uint32_t, HelperType &, llvm::omp::Directive,
259
260template <typename C, typename H>
261void ConstructDecompositionT<C, H>::addClauseSymsToMap(const ObjectTy &object,
262 const ClauseTy *node) {
263 syms[object.id()].insert(node);
264}
265
266template <typename C, typename H>
267void ConstructDecompositionT<C, H>::addClauseSymsToMap(
268 const tomp::ObjectListT<IdTy, ExprTy> &objects, const ClauseTy *node) {
269 for (auto &object : objects)
270 syms[object.id()].insert(node);
271}
272
273template <typename C, typename H>
274void ConstructDecompositionT<C, H>::addClauseSymsToMap(const TypeTy &item,
275 const ClauseTy *node) {
276 // Nothing to do for types.
277}
278
279template <typename C, typename H>
280void ConstructDecompositionT<C, H>::addClauseSymsToMap(const ExprTy &item,
281 const ClauseTy *node) {
282 // Nothing to do for expressions.
283}
284
285template <typename C, typename H>
286void ConstructDecompositionT<C, H>::addClauseSymsToMap(
288 const ClauseTy *node) {
289 auto &objects = std::get<tomp::ObjectListT<IdTy, ExprTy>>(item.t);
290 addClauseSymsToMap(objects, node);
291 for (auto &object : objects) {
292 if (auto base = helper.getBaseObject(object))
293 mapBases.insert(base->id());
294 }
295}
296
297template <typename C, typename H>
298template <typename U>
299void ConstructDecompositionT<C, H>::addClauseSymsToMap(
300 const std::optional<U> &item, const ClauseTy *node) {
301 if (item)
302 addClauseSymsToMap(*item, node);
303}
304
305template <typename C, typename H>
306template <typename U>
307void ConstructDecompositionT<C, H>::addClauseSymsToMap(
308 const tomp::ListT<U> &item, const ClauseTy *node) {
309 for (auto &s : item)
310 addClauseSymsToMap(s, node);
311}
312
313template <typename C, typename H>
314template <typename... U, size_t... Is>
315void ConstructDecompositionT<C, H>::addClauseSymsToMap(
316 const std::tuple<U...> &item, const ClauseTy *node,
317 std::index_sequence<Is...>) {
318 (void)node; // Silence strange warning from GCC.
319 (addClauseSymsToMap(std::get<Is>(item), node), ...);
320}
321
322template <typename C, typename H>
323template <typename U>
324std::enable_if_t<std::is_enum_v<llvm::remove_cvref_t<U>>, void>
325ConstructDecompositionT<C, H>::addClauseSymsToMap(U &&item,
326 const ClauseTy *node) {
327 // Nothing to do for enums.
328}
329
330template <typename C, typename H>
331template <typename U>
332std::enable_if_t<llvm::remove_cvref_t<U>::EmptyTrait::value, void>
333ConstructDecompositionT<C, H>::addClauseSymsToMap(U &&item,
334 const ClauseTy *node) {
335 // Nothing to do for an empty class.
336}
337
338template <typename C, typename H>
339template <typename U>
340std::enable_if_t<llvm::remove_cvref_t<U>::IncompleteTrait::value, void>
341ConstructDecompositionT<C, H>::addClauseSymsToMap(U &&item,
342 const ClauseTy *node) {
343 // Nothing to do for an incomplete class (they're empty).
344}
345
346template <typename C, typename H>
347template <typename U>
348std::enable_if_t<llvm::remove_cvref_t<U>::WrapperTrait::value, void>
349ConstructDecompositionT<C, H>::addClauseSymsToMap(U &&item,
350 const ClauseTy *node) {
351 addClauseSymsToMap(item.v, node);
352}
353
354template <typename C, typename H>
355template <typename U>
356std::enable_if_t<llvm::remove_cvref_t<U>::TupleTrait::value, void>
357ConstructDecompositionT<C, H>::addClauseSymsToMap(U &&item,
358 const ClauseTy *node) {
359 constexpr size_t tuple_size =
360 std::tuple_size_v<llvm::remove_cvref_t<decltype(item.t)>>;
361 addClauseSymsToMap(item.t, node, std::make_index_sequence<tuple_size>{});
362}
363
364template <typename C, typename H>
365template <typename U>
366std::enable_if_t<llvm::remove_cvref_t<U>::UnionTrait::value, void>
367ConstructDecompositionT<C, H>::addClauseSymsToMap(U &&item,
368 const ClauseTy *node) {
369 std::visit([&](auto &&s) { addClauseSymsToMap(s, node); }, item.u);
370}
371
372// Apply a clause to the only directive that allows it. If there are no
373// directives that allow it, or if there is more that one, do not apply
374// anything and return false, otherwise return true.
375template <typename C, typename H>
376bool ConstructDecompositionT<C, H>::applyToUnique(const ClauseTy *node) {
377 auto unique = detail::find_unique(leafs, [=](const auto &leaf) {
378 return llvm::omp::isAllowedClauseForDirective(leaf.id, node->id, version);
379 });
380
381 if (unique != leafs.end()) {
382 unique->clauses.push_back(node);
383 return true;
384 }
385 return false;
386}
387
388// Apply a clause to the first directive in given range that allows it.
389// If such a directive does not exist, return false, otherwise return true.
390template <typename C, typename H>
391template <typename Iterator>
392bool ConstructDecompositionT<C, H>::applyToFirst(
393 const ClauseTy *node, llvm::iterator_range<Iterator> range) {
394 if (range.empty())
395 return false;
396
397 for (auto &leaf : range) {
398 if (!llvm::omp::isAllowedClauseForDirective(leaf.id, node->id, version))
399 continue;
400 leaf.clauses.push_back(node);
401 return true;
402 }
403 return false;
404}
405
406// Apply a clause to the innermost directive that allows it. If such a
407// directive does not exist, return false, otherwise return true.
408template <typename C, typename H>
409bool ConstructDecompositionT<C, H>::applyToInnermost(const ClauseTy *node) {
410 return applyToFirst(node, llvm::reverse(leafs));
411}
412
413// Apply a clause to the outermost directive that allows it. If such a
414// directive does not exist, return false, otherwise return true.
415template <typename C, typename H>
416bool ConstructDecompositionT<C, H>::applyToOutermost(const ClauseTy *node) {
417 return applyToFirst(node, llvm::iterator_range(leafs));
418}
419
420template <typename C, typename H>
421template <typename Predicate>
422bool ConstructDecompositionT<C, H>::applyIf(const ClauseTy *node,
423 Predicate shouldApply) {
424 bool applied = false;
425 for (auto &leaf : leafs) {
426 if (!llvm::omp::isAllowedClauseForDirective(leaf.id, node->id, version))
427 continue;
428 if (!shouldApply(leaf))
429 continue;
430 leaf.clauses.push_back(node);
431 applied = true;
432 }
433
434 return applied;
435}
436
437template <typename C, typename H>
438bool ConstructDecompositionT<C, H>::applyToAll(const ClauseTy *node) {
439 return applyIf(node, [](auto) { return true; });
440}
441
442template <typename C, typename H>
443template <typename Specific>
445 const ClauseTy *node) {
446 // The default behavior is to find the unique directive to which the
447 // given clause may be applied. If there are no such directives, or
448 // if there are multiple ones, flag an error.
449 // From "OpenMP Application Programming Interface", Version 5.2:
450 // S Some clauses are permitted only on a single leaf construct of the
451 // S combined or composite construct, in which case the effect is as if
452 // S the clause is applied to that specific construct. (p339, 31-33)
453 if (applyToUnique(node))
454 return true;
455
456 return false;
457}
458
459// COLLAPSE
460// [5.2:93:20-21]
461// Directives: distribute, do, for, loop, simd, taskloop
462//
463// [5.2:339:35]
464// (35) The collapse clause is applied once to the combined or composite
465// construct.
466template <typename C, typename H>
469 const ClauseTy *node) {
470 // Apply "collapse" to the innermost directive. If it's not one that
471 // allows it flag an error.
472 if (!leafs.empty()) {
473 auto &last = leafs.back();
474
475 if (llvm::omp::isAllowedClauseForDirective(last.id, node->id, version)) {
476 last.clauses.push_back(node);
477 return true;
478 }
479 }
480
481 return false;
482}
483
484// PRIVATE
485// [5.2:111:5-7]
486// Directives: distribute, do, for, loop, parallel, scope, sections, simd,
487// single, target, task, taskloop, teams
488//
489// [5.2:340:1-2]
490// (1) The effect of the 1 private clause is as if it is applied only to the
491// innermost leaf construct that permits it.
492template <typename C, typename H>
493bool ConstructDecompositionT<C, H>::applyClause(
495 const ClauseTy *node) {
496 return applyToInnermost(node);
497}
498
499// FIRSTPRIVATE
500// [5.2:112:5-7]
501// Directives: distribute, do, for, parallel, scope, sections, single, target,
502// task, taskloop, teams
503//
504// [5.2:340:3-20]
505// (3) The effect of the firstprivate clause is as if it is applied to one or
506// more leaf constructs as follows:
507// (5) To the distribute construct if it is among the constituent constructs;
508// (6) To the teams construct if it is among the constituent constructs and the
509// distribute construct is not;
510// (8) To a worksharing construct that accepts the clause if one is among the
511// constituent constructs;
512// (9) To the taskloop construct if it is among the constituent constructs;
513// (10) To the parallel construct if it is among the constituent constructs and
514// neither a taskloop construct nor a worksharing construct that accepts
515// the clause is among them;
516// (12) To the target construct if it is among the constituent constructs and
517// the same list item neither appears in a lastprivate clause nor is the
518// base variable or base pointer of a list item that appears in a map
519// clause.
520//
521// (15) If the parallel construct is among the constituent constructs and the
522// effect is not as if the firstprivate clause is applied to it by the above
523// rules, then the effect is as if the shared clause with the same list item is
524// applied to the parallel construct.
525// (17) If the teams construct is among the constituent constructs and the
526// effect is not as if the firstprivate clause is applied to it by the above
527// rules, then the effect is as if the shared clause with the same list item is
528// applied to the teams construct.
529template <typename C, typename H>
530bool ConstructDecompositionT<C, H>::applyClause(
532 const ClauseTy *node) {
533 bool applied = false;
534
535 // [5.2:340:3-6]
536 auto dirDistribute = findDirective(llvm::omp::OMPD_distribute);
537 auto dirTeams = findDirective(llvm::omp::OMPD_teams);
538 if (dirDistribute != nullptr) {
539 dirDistribute->clauses.push_back(node);
540 applied = true;
541 // [5.2:340:17]
542 if (dirTeams != nullptr) {
543 auto *shared = makeClause(
544 llvm::omp::Clause::OMPC_shared,
546 dirTeams->clauses.push_back(shared);
547 }
548 } else if (dirTeams != nullptr) {
549 dirTeams->clauses.push_back(node);
550 applied = true;
551 }
552
553 // [5.2:340:8]
554 auto findWorksharing = [&]() {
555 auto worksharing = getWorksharing();
556 for (auto &leaf : leafs) {
557 auto found = llvm::find(worksharing, leaf.id);
558 if (found != std::end(worksharing))
559 return &leaf;
560 }
561 return static_cast<typename decltype(leafs)::value_type *>(nullptr);
562 };
563
564 auto dirWorksharing = findWorksharing();
565 if (dirWorksharing != nullptr) {
566 dirWorksharing->clauses.push_back(node);
567 applied = true;
568 }
569
570 // [5.2:340:9]
571 auto dirTaskloop = findDirective(llvm::omp::OMPD_taskloop);
572 if (dirTaskloop != nullptr) {
573 dirTaskloop->clauses.push_back(node);
574 applied = true;
575 }
576
577 // [5.2:340:10]
578 auto dirParallel = findDirective(llvm::omp::OMPD_parallel);
579 if (dirParallel != nullptr) {
580 if (dirTaskloop == nullptr && dirWorksharing == nullptr) {
581 dirParallel->clauses.push_back(node);
582 applied = true;
583 } else {
584 // [5.2:340:15]
585 auto *shared = makeClause(
586 llvm::omp::Clause::OMPC_shared,
588 dirParallel->clauses.push_back(shared);
589 }
590 }
591
592 // [5.2:340:12]
593 auto inLastprivate = [&](const ObjectTy &object) {
594 if (ClauseSet *set = findClausesWith(object)) {
595 return llvm::find_if(*set, [](const ClauseTy *c) {
596 return c->id == llvm::omp::Clause::OMPC_lastprivate;
597 }) != set->end();
598 }
599 return false;
600 };
601
602 auto dirTarget = findDirective(llvm::omp::OMPD_target);
603 if (dirTarget != nullptr) {
606 clause.v, std::back_inserter(objects), [&](const ObjectTy &object) {
607 return !inLastprivate(object) && !mapBases.count(object.id());
608 });
609 if (!objects.empty()) {
610 auto *firstp = makeClause(
611 llvm::omp::Clause::OMPC_firstprivate,
613 dirTarget->clauses.push_back(firstp);
614 applied = true;
615 }
616 }
617
618 // "task" is not handled by any of the cases above.
619 if (auto dirTask = findDirective(llvm::omp::OMPD_task)) {
620 dirTask->clauses.push_back(node);
621 applied = true;
622 }
623
624 return applied;
625}
626
627// LASTPRIVATE
628// [5.2:115:7-8]
629// Directives: distribute, do, for, loop, sections, simd, taskloop
630//
631// [5.2:340:21-30]
632// (21) The effect of the lastprivate clause is as if it is applied to all leaf
633// constructs that permit the clause.
634// (22) If the parallel construct is among the constituent constructs and the
635// list item is not also specified in the firstprivate clause, then the effect
636// of the lastprivate clause is as if the shared clause with the same list item
637// is applied to the parallel construct.
638// (24) If the teams construct is among the constituent constructs and the list
639// item is not also specified in the firstprivate clause, then the effect of the
640// lastprivate clause is as if the shared clause with the same list item is
641// applied to the teams construct.
642// (27) If the target construct is among the constituent constructs and the list
643// item is not the base variable or base pointer of a list item that appears in
644// a map clause, the effect of the lastprivate clause is as if the same list
645// item appears in a map clause with a map-type of tofrom.
646template <typename C, typename H>
647bool ConstructDecompositionT<C, H>::applyClause(
649 const ClauseTy *node) {
650 bool applied = false;
651
652 // [5.2:340:21]
653 applied = applyToAll(node);
654 if (!applied)
655 return false;
656
657 auto inFirstprivate = [&](const ObjectTy &object) {
658 if (ClauseSet *set = findClausesWith(object)) {
659 return llvm::find_if(*set, [](const ClauseTy *c) {
660 return c->id == llvm::omp::Clause::OMPC_firstprivate;
661 }) != set->end();
662 }
663 return false;
664 };
665
666 auto &objects = std::get<tomp::ObjectListT<IdTy, ExprTy>>(clause.t);
667
668 // Prepare list of objects that could end up in a "shared" clause.
671 objects, std::back_inserter(sharedObjects),
672 [&](const ObjectTy &object) { return !inFirstprivate(object); });
673
674 if (!sharedObjects.empty()) {
675 // [5.2:340:22]
676 if (auto dirParallel = findDirective(llvm::omp::OMPD_parallel)) {
677 auto *shared = makeClause(
678 llvm::omp::Clause::OMPC_shared,
679 tomp::clause::SharedT<TypeTy, IdTy, ExprTy>{/*List=*/sharedObjects});
680 dirParallel->clauses.push_back(shared);
681 applied = true;
682 }
683
684 // [5.2:340:24]
685 if (auto dirTeams = findDirective(llvm::omp::OMPD_teams)) {
686 auto *shared = makeClause(
687 llvm::omp::Clause::OMPC_shared,
688 tomp::clause::SharedT<TypeTy, IdTy, ExprTy>{/*List=*/sharedObjects});
689 dirTeams->clauses.push_back(shared);
690 applied = true;
691 }
692 }
693
694 // [5.2:340:27]
695 if (auto dirTarget = findDirective(llvm::omp::OMPD_target)) {
698 objects, std::back_inserter(tofrom),
699 [&](const ObjectTy &object) { return !mapBases.count(object.id()); });
700
701 if (!tofrom.empty()) {
702 using MapType =
704 auto *map =
705 makeClause(llvm::omp::Clause::OMPC_map,
707 {/*MapType=*/MapType::Tofrom,
708 /*MapTypeModifier=*/std::nullopt,
709 /*Mapper=*/std::nullopt, /*Iterator=*/std::nullopt,
710 /*LocatorList=*/std::move(tofrom)}});
711 dirTarget->clauses.push_back(map);
712 applied = true;
713 }
714 }
715
716 return applied;
717}
718
719// SHARED
720// [5.2:110:5-6]
721// Directives: parallel, task, taskloop, teams
722//
723// [5.2:340:31-32]
724// (31) The effect of the shared, default, thread_limit, or order clause is as
725// if it is applied to all leaf constructs that permit the clause.
726template <typename C, typename H>
727bool ConstructDecompositionT<C, H>::applyClause(
729 const ClauseTy *node) {
730 // [5.2:340:31]
731 return applyToAll(node);
732}
733
734// DEFAULT
735// [5.2:109:5-6]
736// Directives: parallel, task, taskloop, teams
737//
738// [5.2:340:31-32]
739// (31) The effect of the shared, default, thread_limit, or order clause is as
740// if it is applied to all leaf constructs that permit the clause.
741template <typename C, typename H>
742bool ConstructDecompositionT<C, H>::applyClause(
744 const ClauseTy *node) {
745 // [5.2:340:31]
746 return applyToAll(node);
747}
748
749// THREAD_LIMIT
750// [5.2:277:14-15]
751// Directives: target, teams
752//
753// [5.2:340:31-32]
754// (31) The effect of the shared, default, thread_limit, or order clause is as
755// if it is applied to all leaf constructs that permit the clause.
756template <typename C, typename H>
757bool ConstructDecompositionT<C, H>::applyClause(
759 const ClauseTy *node) {
760 // [5.2:340:31]
761 return applyToAll(node);
762}
763
764// ORDER
765// [5.2:234:3-4]
766// Directives: distribute, do, for, loop, simd
767//
768// [5.2:340:31-32]
769// (31) The effect of the shared, default, thread_limit, or order clause is as
770// if it is applied to all leaf constructs that permit the clause.
771template <typename C, typename H>
772bool ConstructDecompositionT<C, H>::applyClause(
774 const ClauseTy *node) {
775 // [5.2:340:31]
776 return applyToAll(node);
777}
778
779// ALLOCATE
780// [5.2:178:7-9]
781// Directives: allocators, distribute, do, for, parallel, scope, sections,
782// single, target, task, taskgroup, taskloop, teams
783//
784// [5.2:340:33-35]
785// (33) The effect of the allocate clause is as if it is applied to all leaf
786// constructs that permit the clause and to which a data-sharing attribute
787// clause that may create a private copy of the same list item is applied.
788template <typename C, typename H>
789bool ConstructDecompositionT<C, H>::applyClause(
791 const ClauseTy *node) {
792 // This one needs to be applied at the end, once we know which clauses are
793 // assigned to which leaf constructs.
794
795 // [5.2:340:33]
796 auto canMakePrivateCopy = [](llvm::omp::Clause id) {
797 switch (id) {
798 // Clauses with "privatization" property:
799 case llvm::omp::Clause::OMPC_firstprivate:
800 case llvm::omp::Clause::OMPC_in_reduction:
801 case llvm::omp::Clause::OMPC_lastprivate:
802 case llvm::omp::Clause::OMPC_linear:
803 case llvm::omp::Clause::OMPC_private:
804 case llvm::omp::Clause::OMPC_reduction:
805 case llvm::omp::Clause::OMPC_task_reduction:
806 return true;
807 default:
808 return false;
809 }
810 };
811
812 bool applied = applyIf(node, [&](const auto &leaf) {
813 return llvm::any_of(leaf.clauses, [&](const ClauseTy *n) {
814 return canMakePrivateCopy(n->id);
815 });
816 });
817
818 return applied;
819}
820
821// REDUCTION
822// [5.2:134:17-18]
823// Directives: do, for, loop, parallel, scope, sections, simd, taskloop, teams
824//
825// [5.2:340:36-37], [5.2:341:1-13]
826// (36) The effect of the reduction clause is as if it is applied to all leaf
827// constructs that permit the clause, except for the following constructs:
828// (1) The parallel construct, when combined with the sections,
829// worksharing-loop, loop, or taskloop construct; and
830// (3) The teams construct, when combined with the loop construct.
831// (4) For the parallel and teams constructs above, the effect of the reduction
832// clause instead is as if each list item or, for any list item that is an array
833// item, its corresponding base array or base pointer appears in a shared clause
834// for the construct.
835// (6) If the task reduction-modifier is specified, the effect is as if it only
836// modifies the behavior of the reduction clause on the innermost leaf construct
837// that accepts the modifier (see Section 5.5.8).
838// (8) If the inscan reduction-modifier is specified, the effect is as if it
839// modifies the behavior of the reduction clause on all constructs of the
840// combined construct to which the clause is applied and that accept the
841// modifier.
842// (10) If a list item in a reduction clause on a combined target construct does
843// not have the same base variable or base pointer as a list item in a map
844// clause on the construct, then the effect is as if the list item in the
845// reduction clause appears as a list item in a map clause with a map-type of
846// tofrom.
847template <typename C, typename H>
848bool ConstructDecompositionT<C, H>::applyClause(
850 const ClauseTy *node) {
852
853 // [5.2:340:36], [5.2:341:1], [5.2:341:3]
854 bool applyToParallel = true, applyToTeams = true;
855
856 auto dirParallel = findDirective(llvm::omp::Directive::OMPD_parallel);
857 if (dirParallel) {
858 auto exclusions = llvm::concat<const llvm::omp::Directive>(
860 llvm::omp::Directive::OMPD_loop,
861 llvm::omp::Directive::OMPD_sections,
862 llvm::omp::Directive::OMPD_taskloop,
863 });
864 auto present = [&](llvm::omp::Directive id) {
865 return findDirective(id) != nullptr;
866 };
867
868 if (llvm::any_of(exclusions, present))
869 applyToParallel = false;
870 }
871
872 auto dirTeams = findDirective(llvm::omp::Directive::OMPD_teams);
873 if (dirTeams) {
874 // The only exclusion is OMPD_loop.
875 if (findDirective(llvm::omp::Directive::OMPD_loop))
876 applyToTeams = false;
877 }
878
879 using ReductionModifier = typename ReductionTy::ReductionModifier;
880 using ReductionIdentifiers = typename ReductionTy::ReductionIdentifiers;
881
882 auto &objects = std::get<tomp::ObjectListT<IdTy, ExprTy>>(clause.t);
883 auto &modifier = std::get<std::optional<ReductionModifier>>(clause.t);
884
885 // Apply the reduction clause first to all directives according to the spec.
886 // If the reduction was applied at least once, proceed with the data sharing
887 // side-effects.
888 bool applied = false;
889
890 // [5.2:341:6], [5.2:341:8]
891 auto isValidModifier = [](llvm::omp::Directive dir, ReductionModifier mod,
892 bool alreadyApplied) {
893 switch (mod) {
894 case ReductionModifier::Inscan:
895 // According to [5.2:135:11-13], "inscan" only applies to
896 // worksharing-loop, worksharing-loop-simd, or "simd" constructs.
897 return dir == llvm::omp::Directive::OMPD_simd ||
899 case ReductionModifier::Task:
900 if (alreadyApplied)
901 return false;
902 // According to [5.2:135:16-18], "task" only applies to "parallel" and
903 // worksharing constructs.
904 return dir == llvm::omp::Directive::OMPD_parallel ||
906 case ReductionModifier::Default:
907 return true;
908 }
909 llvm_unreachable("Unexpected modifier");
910 };
911
912 auto *unmodified = makeClause(
913 llvm::omp::Clause::OMPC_reduction,
914 ReductionTy{
915 {/*ReductionModifier=*/std::nullopt,
916 /*ReductionIdentifiers=*/std::get<ReductionIdentifiers>(clause.t),
917 /*List=*/objects}});
918
919 ReductionModifier effective =
920 modifier.has_value() ? *modifier : ReductionModifier::Default;
921 bool effectiveApplied = false;
922 // Walk over the leaf constructs starting from the innermost, and apply
923 // the clause as required by the spec.
924 for (auto &leaf : llvm::reverse(leafs)) {
925 if (!llvm::omp::isAllowedClauseForDirective(leaf.id, node->id, version))
926 continue;
927 if (!applyToParallel && &leaf == dirParallel)
928 continue;
929 if (!applyToTeams && &leaf == dirTeams)
930 continue;
931 // Some form of the clause will be applied past this point.
932 if (isValidModifier(leaf.id, effective, effectiveApplied)) {
933 // Apply clause with modifier.
934 leaf.clauses.push_back(node);
935 effectiveApplied = true;
936 } else {
937 // Apply clause without modifier.
938 leaf.clauses.push_back(unmodified);
939 }
940 // The modifier must be applied to some construct.
941 applied = effectiveApplied;
942 }
943
944 if (!applied)
945 return false;
946
948 llvm::transform(objects, std::back_inserter(sharedObjects),
949 [&](const ObjectTy &object) {
950 auto maybeBase = helper.getBaseObject(object);
951 return maybeBase ? *maybeBase : object;
952 });
953
954 // [5.2:341:4]
955 if (!sharedObjects.empty()) {
956 if (dirParallel && !applyToParallel) {
957 auto *shared = makeClause(
958 llvm::omp::Clause::OMPC_shared,
959 tomp::clause::SharedT<TypeTy, IdTy, ExprTy>{/*List=*/sharedObjects});
960 dirParallel->clauses.push_back(shared);
961 }
962 if (dirTeams && !applyToTeams) {
963 auto *shared = makeClause(
964 llvm::omp::Clause::OMPC_shared,
965 tomp::clause::SharedT<TypeTy, IdTy, ExprTy>{/*List=*/sharedObjects});
966 dirTeams->clauses.push_back(shared);
967 }
968 }
969
970 // [5.2:341:10]
971 auto dirTarget = findDirective(llvm::omp::Directive::OMPD_target);
972 if (dirTarget && leafs.size() > 1) {
974 llvm::copy_if(objects, std::back_inserter(tofrom),
975 [&](const ObjectTy &object) {
976 if (auto maybeBase = helper.getBaseObject(object))
977 return !mapBases.count(maybeBase->id());
978 return !mapBases.count(object.id()); // XXX is this ok?
979 });
980 if (!tofrom.empty()) {
981 using MapType =
983 auto *map = makeClause(
984 llvm::omp::Clause::OMPC_map,
986 {/*MapType=*/MapType::Tofrom, /*MapTypeModifier=*/std::nullopt,
987 /*Mapper=*/std::nullopt, /*Iterator=*/std::nullopt,
988 /*LocatorList=*/std::move(tofrom)}});
989
990 dirTarget->clauses.push_back(map);
991 applied = true;
992 }
993 }
994
995 return applied;
996}
997
998// IF
999// [5.2:72:7-9]
1000// Directives: cancel, parallel, simd, target, target data, target enter data,
1001// target exit data, target update, task, taskloop
1002//
1003// [5.2:72:15-18]
1004// (15) For combined or composite constructs, the if clause only applies to the
1005// semantics of the construct named in the directive-name-modifier.
1006// (16) For a combined or composite construct, if no directive-name-modifier is
1007// specified then the if clause applies to all constituent constructs to which
1008// an if clause can apply.
1009template <typename C, typename H>
1010bool ConstructDecompositionT<C, H>::applyClause(
1012 const ClauseTy *node) {
1013 using DirectiveNameModifier =
1015 using IfExpression = typename clause::IfT<TypeTy, IdTy, ExprTy>::IfExpression;
1016 auto &modifier = std::get<std::optional<DirectiveNameModifier>>(clause.t);
1017
1018 if (modifier) {
1019 llvm::omp::Directive dirId = *modifier;
1020 auto *unmodified =
1021 makeClause(llvm::omp::Clause::OMPC_if,
1023 {/*DirectiveNameModifier=*/std::nullopt,
1024 /*IfExpression=*/std::get<IfExpression>(clause.t)}});
1025
1026 if (auto *hasDir = findDirective(dirId)) {
1027 hasDir->clauses.push_back(unmodified);
1028 return true;
1029 }
1030 return false;
1031 }
1032
1033 return applyToAll(node);
1034}
1035
1036// LINEAR
1037// [5.2:118:1-2]
1038// Directives: declare simd, do, for, simd
1039//
1040// [5.2:341:15-22]
1041// (15.1) The effect of the linear clause is as if it is applied to the
1042// innermost leaf construct.
1043// (15.2) Additionally, if the list item is not the iteration variable of a simd
1044// or worksharing-loop SIMD construct, the effect on the outer leaf constructs
1045// is as if the list item was specified in firstprivate and lastprivate clauses
1046// on the combined or composite construct, with the rules specified above
1047// applied.
1048// (19) If a list item of the linear clause is the iteration variable of a simd
1049// or worksharing-loop SIMD construct and it is not declared in the construct,
1050// the effect on the outer leaf constructs is as if the list item was specified
1051// in a lastprivate clause on the combined or composite construct with the rules
1052// specified above applied.
1053template <typename C, typename H>
1054bool ConstructDecompositionT<C, H>::applyClause(
1056 const ClauseTy *node) {
1057 // [5.2:341:15.1]
1058 if (!applyToInnermost(node))
1059 return false;
1060
1061 // [5.2:341:15.2], [5.2:341:19]
1062 auto dirSimd = findDirective(llvm::omp::Directive::OMPD_simd);
1063 std::optional<ObjectTy> iterVar = helper.getLoopIterVar();
1064 const auto &objects = std::get<tomp::ObjectListT<IdTy, ExprTy>>(clause.t);
1065
1066 // Lists of objects that will be used to construct "firstprivate" and
1067 // "lastprivate" clauses.
1069
1070 for (const ObjectTy &object : objects) {
1071 last.push_back(object);
1072 if (!dirSimd || !iterVar || object.id() != iterVar->id())
1073 first.push_back(object);
1074 }
1075
1076 if (!first.empty()) {
1077 auto *firstp = makeClause(
1078 llvm::omp::Clause::OMPC_firstprivate,
1080 nodes.push_back(firstp); // Appending to the main clause list.
1081 }
1082 if (!last.empty()) {
1083 auto *lastp =
1084 makeClause(llvm::omp::Clause::OMPC_lastprivate,
1086 {/*LastprivateModifier=*/std::nullopt, /*List=*/last}});
1087 nodes.push_back(lastp); // Appending to the main clause list.
1088 }
1089 return true;
1090}
1091
1092// NOWAIT
1093// [5.2:308:11-13]
1094// Directives: dispatch, do, for, interop, scope, sections, single, target,
1095// target enter data, target exit data, target update, taskwait, workshare
1096//
1097// [5.2:341:23]
1098// (23) The effect of the nowait clause is as if it is applied to the outermost
1099// leaf construct that permits it.
1100template <typename C, typename H>
1101bool ConstructDecompositionT<C, H>::applyClause(
1103 const ClauseTy *node) {
1104 return applyToOutermost(node);
1105}
1106
1107template <typename C, typename H>
1108bool ConstructDecompositionT<C, H>::applyClause(
1110 const ClauseTy *node) {
1111 return applyToAll(node);
1112}
1113
1114template <typename C, typename H> bool ConstructDecompositionT<C, H>::split() {
1115 bool success = true;
1116
1117 for (llvm::omp::Directive leaf :
1119 leafs.push_back(LeafReprInternal{leaf, /*clauses=*/{}});
1120
1121 for (const ClauseTy *node : nodes)
1122 addClauseSymsToMap(*node, node);
1123
1124 // First we need to apply LINEAR, because it can generate additional
1125 // "firstprivate" and "lastprivate" clauses that apply to the combined/
1126 // composite construct.
1127 // Collect them separately, because they may modify the clause list.
1129 for (const ClauseTy *node : nodes) {
1130 if (node->id == llvm::omp::Clause::OMPC_linear)
1131 linears.push_back(node);
1132 }
1133 for (const auto *node : linears) {
1134 success = success &&
1135 applyClause(std::get<tomp::clause::LinearT<TypeTy, IdTy, ExprTy>>(
1136 node->u),
1137 node);
1138 }
1139
1140 // "allocate" clauses need to be applied last since they need to see
1141 // which directives have data-privatizing clauses.
1142 auto skip = [](const ClauseTy *node) {
1143 switch (node->id) {
1144 case llvm::omp::Clause::OMPC_allocate:
1145 case llvm::omp::Clause::OMPC_linear:
1146 return true;
1147 default:
1148 return false;
1149 }
1150 };
1151
1152 // Apply (almost) all clauses.
1153 for (const ClauseTy *node : nodes) {
1154 if (skip(node))
1155 continue;
1156 success =
1157 success &&
1158 std::visit([&](auto &&s) { return applyClause(s, node); }, node->u);
1159 }
1160
1161 // Apply "allocate".
1162 for (const ClauseTy *node : nodes) {
1163 if (node->id != llvm::omp::Clause::OMPC_allocate)
1164 continue;
1165 success =
1166 success &&
1167 std::visit([&](auto &&s) { return applyClause(s, node); }, node->u);
1168 }
1169
1170 return success;
1171}
1172
1173} // namespace tomp
1174
1175#endif // LLVM_FRONTEND_OPENMP_CONSTRUCTDECOMPOSITIONT_H
Unify divergent function exit nodes
static llvm::ArrayRef< llvm::omp::Directive > getWorksharing()
static llvm::ArrayRef< llvm::omp::Directive > getWorksharingLoop()
static bool shouldApply(Function &F, ProfileSummaryInfo &PSI)
hexagon gen pred
static bool skip(DataExtractor &Data, uint64_t &Offset, bool SkippedRanges)
Skip an InlineInfo object in the specified data at the specified offset.
Definition: InlineInfo.cpp:77
SI Form memory clauses
This file contains some templates that are useful if you are working with the STL at all.
This file defines the SmallVector class.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
bool empty() const
Definition: SmallVector.h:94
void push_back(const T &Elt)
Definition: SmallVector.h:426
A range adaptor for a pair of iterators.
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
std::remove_reference_t< Container >::iterator find_unique(Container &&container, Predicate &&pred)
ArrayRef< Directive > getLeafConstructsOrSelf(Directive D)
Definition: OMP.cpp:85
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1742
LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt mod(const DynamicAPInt &LHS, const DynamicAPInt &RHS)
is always non-negative.
Definition: DynamicAPInt.h:380
auto unique(Range &&R, Predicate P)
Definition: STLExtras.h:2013
OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P)
Provide wrappers to std::copy_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1768
OutputIt transform(R &&Range, OutputIt d_first, UnaryFunction F)
Wrapper function around std::transform to apply a function to a range and store the result elsewhere.
Definition: STLExtras.h:1928
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1729
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:419
typename llvm::remove_cvref< T >::type remove_cvref_t
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1749
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1879
LogicalResult success(bool IsSuccess=true)
Utility function to generate a LogicalResult.
Definition: LogicalResult.h:55
Definition: ClauseT.h:133
typename ClauseTy::ExprTy ExprTy
std::unordered_set< const ClauseTy * > ClauseSet
typename ClauseTy::TypeTy TypeTy
tomp::ObjectT< IdTy, ExprTy > ObjectTy
ConstructDecompositionT(uint32_t ver, HelperType &helper, llvm::omp::Directive dir, llvm::ArrayRef< ClauseTy > clauses)
tomp::ListT< DirectiveWithClauses< ClauseType > > output
std::tuple< OPT(DirectiveNameModifier), IfExpression > t
Definition: ClauseT.h:681
type::DirectiveName DirectiveNameModifier
Definition: ClauseT.h:678
std::tuple< OPT(LastprivateModifier), List > t
Definition: ClauseT.h:752
std::tuple< OPT(StepSimpleModifier), OPT(StepComplexModifier), OPT(LinearModifier), List > t
Definition: ClauseT.h:768
std::tuple< OPT(MapType), OPT(MapTypeModifiers), OPT(Mappers), OPT(Iterator), LocatorList > t
Definition: ClauseT.h:793
std::tuple< OPT(ReductionModifier), ReductionIdentifiers, List > t
Definition: ClauseT.h:988