LLVM 19.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
240 uint32_t version;
241 llvm::omp::Directive construct;
242 HelperType &helper;
243 ListT<LeafReprInternal> leafs;
245 std::list<ClauseTy> implicit; // Container for materialized implicit clauses.
246 // Inserting must preserve element addresses.
247 std::unordered_map<IdTy, ClauseSet> syms;
248 std::unordered_set<IdTy> mapBases;
249};
250
251// Deduction guide
252template <typename ClauseType, typename HelperType>
253ConstructDecompositionT(uint32_t, HelperType &, llvm::omp::Directive,
256
257template <typename C, typename H>
258void ConstructDecompositionT<C, H>::addClauseSymsToMap(const ObjectTy &object,
259 const ClauseTy *node) {
260 syms[object.id()].insert(node);
261}
262
263template <typename C, typename H>
264void ConstructDecompositionT<C, H>::addClauseSymsToMap(
265 const tomp::ObjectListT<IdTy, ExprTy> &objects, const ClauseTy *node) {
266 for (auto &object : objects)
267 syms[object.id()].insert(node);
268}
269
270template <typename C, typename H>
271void ConstructDecompositionT<C, H>::addClauseSymsToMap(const TypeTy &item,
272 const ClauseTy *node) {
273 // Nothing to do for types.
274}
275
276template <typename C, typename H>
277void ConstructDecompositionT<C, H>::addClauseSymsToMap(const ExprTy &item,
278 const ClauseTy *node) {
279 // Nothing to do for expressions.
280}
281
282template <typename C, typename H>
283void ConstructDecompositionT<C, H>::addClauseSymsToMap(
285 const ClauseTy *node) {
286 auto &objects = std::get<tomp::ObjectListT<IdTy, ExprTy>>(item.t);
287 addClauseSymsToMap(objects, node);
288 for (auto &object : objects) {
289 if (auto base = helper.getBaseObject(object))
290 mapBases.insert(base->id());
291 }
292}
293
294template <typename C, typename H>
295template <typename U>
296void ConstructDecompositionT<C, H>::addClauseSymsToMap(
297 const std::optional<U> &item, const ClauseTy *node) {
298 if (item)
299 addClauseSymsToMap(*item, node);
300}
301
302template <typename C, typename H>
303template <typename U>
304void ConstructDecompositionT<C, H>::addClauseSymsToMap(
305 const tomp::ListT<U> &item, const ClauseTy *node) {
306 for (auto &s : item)
307 addClauseSymsToMap(s, node);
308}
309
310template <typename C, typename H>
311template <typename... U, size_t... Is>
312void ConstructDecompositionT<C, H>::addClauseSymsToMap(
313 const std::tuple<U...> &item, const ClauseTy *node,
314 std::index_sequence<Is...>) {
315 (void)node; // Silence strange warning from GCC.
316 (addClauseSymsToMap(std::get<Is>(item), node), ...);
317}
318
319template <typename C, typename H>
320template <typename U>
321std::enable_if_t<std::is_enum_v<llvm::remove_cvref_t<U>>, void>
322ConstructDecompositionT<C, H>::addClauseSymsToMap(U &&item,
323 const ClauseTy *node) {
324 // Nothing to do for enums.
325}
326
327template <typename C, typename H>
328template <typename U>
329std::enable_if_t<llvm::remove_cvref_t<U>::EmptyTrait::value, void>
330ConstructDecompositionT<C, H>::addClauseSymsToMap(U &&item,
331 const ClauseTy *node) {
332 // Nothing to do for an empty class.
333}
334
335template <typename C, typename H>
336template <typename U>
337std::enable_if_t<llvm::remove_cvref_t<U>::IncompleteTrait::value, void>
338ConstructDecompositionT<C, H>::addClauseSymsToMap(U &&item,
339 const ClauseTy *node) {
340 // Nothing to do for an incomplete class (they're empty).
341}
342
343template <typename C, typename H>
344template <typename U>
345std::enable_if_t<llvm::remove_cvref_t<U>::WrapperTrait::value, void>
346ConstructDecompositionT<C, H>::addClauseSymsToMap(U &&item,
347 const ClauseTy *node) {
348 addClauseSymsToMap(item.v, node);
349}
350
351template <typename C, typename H>
352template <typename U>
353std::enable_if_t<llvm::remove_cvref_t<U>::TupleTrait::value, void>
354ConstructDecompositionT<C, H>::addClauseSymsToMap(U &&item,
355 const ClauseTy *node) {
356 constexpr size_t tuple_size =
357 std::tuple_size_v<llvm::remove_cvref_t<decltype(item.t)>>;
358 addClauseSymsToMap(item.t, node, std::make_index_sequence<tuple_size>{});
359}
360
361template <typename C, typename H>
362template <typename U>
363std::enable_if_t<llvm::remove_cvref_t<U>::UnionTrait::value, void>
364ConstructDecompositionT<C, H>::addClauseSymsToMap(U &&item,
365 const ClauseTy *node) {
366 std::visit([&](auto &&s) { addClauseSymsToMap(s, node); }, item.u);
367}
368
369// Apply a clause to the only directive that allows it. If there are no
370// directives that allow it, or if there is more that one, do not apply
371// anything and return false, otherwise return true.
372template <typename C, typename H>
373bool ConstructDecompositionT<C, H>::applyToUnique(const ClauseTy *node) {
374 auto unique = detail::find_unique(leafs, [=](const auto &leaf) {
375 return llvm::omp::isAllowedClauseForDirective(leaf.id, node->id, version);
376 });
377
378 if (unique != leafs.end()) {
379 unique->clauses.push_back(node);
380 return true;
381 }
382 return false;
383}
384
385// Apply a clause to the first directive in given range that allows it.
386// If such a directive does not exist, return false, otherwise return true.
387template <typename C, typename H>
388template <typename Iterator>
389bool ConstructDecompositionT<C, H>::applyToFirst(
390 const ClauseTy *node, llvm::iterator_range<Iterator> range) {
391 if (range.empty())
392 return false;
393
394 for (auto &leaf : range) {
395 if (!llvm::omp::isAllowedClauseForDirective(leaf.id, node->id, version))
396 continue;
397 leaf.clauses.push_back(node);
398 return true;
399 }
400 return false;
401}
402
403// Apply a clause to the innermost directive that allows it. If such a
404// directive does not exist, return false, otherwise return true.
405template <typename C, typename H>
406bool ConstructDecompositionT<C, H>::applyToInnermost(const ClauseTy *node) {
407 return applyToFirst(node, llvm::reverse(leafs));
408}
409
410// Apply a clause to the outermost directive that allows it. If such a
411// directive does not exist, return false, otherwise return true.
412template <typename C, typename H>
413bool ConstructDecompositionT<C, H>::applyToOutermost(const ClauseTy *node) {
414 return applyToFirst(node, llvm::iterator_range(leafs));
415}
416
417template <typename C, typename H>
418template <typename Predicate>
419bool ConstructDecompositionT<C, H>::applyIf(const ClauseTy *node,
420 Predicate shouldApply) {
421 bool applied = false;
422 for (auto &leaf : leafs) {
423 if (!llvm::omp::isAllowedClauseForDirective(leaf.id, node->id, version))
424 continue;
425 if (!shouldApply(leaf))
426 continue;
427 leaf.clauses.push_back(node);
428 applied = true;
429 }
430
431 return applied;
432}
433
434template <typename C, typename H>
435bool ConstructDecompositionT<C, H>::applyToAll(const ClauseTy *node) {
436 return applyIf(node, [](auto) { return true; });
437}
438
439template <typename C, typename H>
440template <typename Specific>
442 const ClauseTy *node) {
443 // The default behavior is to find the unique directive to which the
444 // given clause may be applied. If there are no such directives, or
445 // if there are multiple ones, flag an error.
446 // From "OpenMP Application Programming Interface", Version 5.2:
447 // S Some clauses are permitted only on a single leaf construct of the
448 // S combined or composite construct, in which case the effect is as if
449 // S the clause is applied to that specific construct. (p339, 31-33)
450 if (applyToUnique(node))
451 return true;
452
453 return false;
454}
455
456// COLLAPSE
457// [5.2:93:20-21]
458// Directives: distribute, do, for, loop, simd, taskloop
459//
460// [5.2:339:35]
461// (35) The collapse clause is applied once to the combined or composite
462// construct.
463template <typename C, typename H>
466 const ClauseTy *node) {
467 // Apply "collapse" to the innermost directive. If it's not one that
468 // allows it flag an error.
469 if (!leafs.empty()) {
470 auto &last = leafs.back();
471
472 if (llvm::omp::isAllowedClauseForDirective(last.id, node->id, version)) {
473 last.clauses.push_back(node);
474 return true;
475 }
476 }
477
478 return false;
479}
480
481// PRIVATE
482// [5.2:111:5-7]
483// Directives: distribute, do, for, loop, parallel, scope, sections, simd,
484// single, target, task, taskloop, teams
485//
486// [5.2:340:1-2]
487// (1) The effect of the 1 private clause is as if it is applied only to the
488// innermost leaf construct that permits it.
489template <typename C, typename H>
490bool ConstructDecompositionT<C, H>::applyClause(
492 const ClauseTy *node) {
493 return applyToInnermost(node);
494}
495
496// FIRSTPRIVATE
497// [5.2:112:5-7]
498// Directives: distribute, do, for, parallel, scope, sections, single, target,
499// task, taskloop, teams
500//
501// [5.2:340:3-20]
502// (3) The effect of the firstprivate clause is as if it is applied to one or
503// more leaf constructs as follows:
504// (5) To the distribute construct if it is among the constituent constructs;
505// (6) To the teams construct if it is among the constituent constructs and the
506// distribute construct is not;
507// (8) To a worksharing construct that accepts the clause if one is among the
508// constituent constructs;
509// (9) To the taskloop construct if it is among the constituent constructs;
510// (10) To the parallel construct if it is among the constituent constructs and
511// neither a taskloop construct nor a worksharing construct that accepts
512// the clause is among them;
513// (12) To the target construct if it is among the constituent constructs and
514// the same list item neither appears in a lastprivate clause nor is the
515// base variable or base pointer of a list item that appears in a map
516// clause.
517//
518// (15) If the parallel construct is among the constituent constructs and the
519// effect is not as if the firstprivate clause is applied to it by the above
520// rules, then the effect is as if the shared clause with the same list item is
521// applied to the parallel construct.
522// (17) If the teams construct is among the constituent constructs and the
523// effect is not as if the firstprivate clause is applied to it by the above
524// rules, then the effect is as if the shared clause with the same list item is
525// applied to the teams construct.
526template <typename C, typename H>
527bool ConstructDecompositionT<C, H>::applyClause(
529 const ClauseTy *node) {
530 bool applied = false;
531
532 // [5.2:340:3-6]
533 auto dirDistribute = findDirective(llvm::omp::OMPD_distribute);
534 auto dirTeams = findDirective(llvm::omp::OMPD_teams);
535 if (dirDistribute != nullptr) {
536 dirDistribute->clauses.push_back(node);
537 applied = true;
538 // [5.2:340:17]
539 if (dirTeams != nullptr) {
540 auto *shared = makeClause(
541 llvm::omp::Clause::OMPC_shared,
543 dirTeams->clauses.push_back(shared);
544 }
545 } else if (dirTeams != nullptr) {
546 dirTeams->clauses.push_back(node);
547 applied = true;
548 }
549
550 // [5.2:340:8]
551 auto findWorksharing = [&]() {
552 auto worksharing = getWorksharing();
553 for (auto &leaf : leafs) {
554 auto found = llvm::find(worksharing, leaf.id);
555 if (found != std::end(worksharing))
556 return &leaf;
557 }
558 return static_cast<typename decltype(leafs)::value_type *>(nullptr);
559 };
560
561 auto dirWorksharing = findWorksharing();
562 if (dirWorksharing != nullptr) {
563 dirWorksharing->clauses.push_back(node);
564 applied = true;
565 }
566
567 // [5.2:340:9]
568 auto dirTaskloop = findDirective(llvm::omp::OMPD_taskloop);
569 if (dirTaskloop != nullptr) {
570 dirTaskloop->clauses.push_back(node);
571 applied = true;
572 }
573
574 // [5.2:340:10]
575 auto dirParallel = findDirective(llvm::omp::OMPD_parallel);
576 if (dirParallel != nullptr) {
577 if (dirTaskloop == nullptr && dirWorksharing == nullptr) {
578 dirParallel->clauses.push_back(node);
579 applied = true;
580 } else {
581 // [5.2:340:15]
582 auto *shared = makeClause(
583 llvm::omp::Clause::OMPC_shared,
585 dirParallel->clauses.push_back(shared);
586 }
587 }
588
589 // [5.2:340:12]
590 auto inLastprivate = [&](const ObjectTy &object) {
591 if (ClauseSet *set = findClausesWith(object)) {
592 return llvm::find_if(*set, [](const ClauseTy *c) {
593 return c->id == llvm::omp::Clause::OMPC_lastprivate;
594 }) != set->end();
595 }
596 return false;
597 };
598
599 auto dirTarget = findDirective(llvm::omp::OMPD_target);
600 if (dirTarget != nullptr) {
603 clause.v, std::back_inserter(objects), [&](const ObjectTy &object) {
604 return !inLastprivate(object) && !mapBases.count(object.id());
605 });
606 if (!objects.empty()) {
607 auto *firstp = makeClause(
608 llvm::omp::Clause::OMPC_firstprivate,
610 dirTarget->clauses.push_back(firstp);
611 applied = true;
612 }
613 }
614
615 // "task" is not handled by any of the cases above.
616 if (auto dirTask = findDirective(llvm::omp::OMPD_task)) {
617 dirTask->clauses.push_back(node);
618 applied = true;
619 }
620
621 return applied;
622}
623
624// LASTPRIVATE
625// [5.2:115:7-8]
626// Directives: distribute, do, for, loop, sections, simd, taskloop
627//
628// [5.2:340:21-30]
629// (21) The effect of the lastprivate clause is as if it is applied to all leaf
630// constructs that permit the clause.
631// (22) If the parallel construct is among the constituent constructs and the
632// list item is not also specified in the firstprivate clause, then the effect
633// of the lastprivate clause is as if the shared clause with the same list item
634// is applied to the parallel construct.
635// (24) If the teams construct is among the constituent constructs and the list
636// item is not also specified in the firstprivate clause, then the effect of the
637// lastprivate clause is as if the shared clause with the same list item is
638// applied to the teams construct.
639// (27) If the target construct is among the constituent constructs and the list
640// item is not the base variable or base pointer of a list item that appears in
641// a map clause, the effect of the lastprivate clause is as if the same list
642// item appears in a map clause with a map-type of tofrom.
643template <typename C, typename H>
644bool ConstructDecompositionT<C, H>::applyClause(
646 const ClauseTy *node) {
647 bool applied = false;
648
649 // [5.2:340:21]
650 applied = applyToAll(node);
651 if (!applied)
652 return false;
653
654 auto inFirstprivate = [&](const ObjectTy &object) {
655 if (ClauseSet *set = findClausesWith(object)) {
656 return llvm::find_if(*set, [](const ClauseTy *c) {
657 return c->id == llvm::omp::Clause::OMPC_firstprivate;
658 }) != set->end();
659 }
660 return false;
661 };
662
663 auto &objects = std::get<tomp::ObjectListT<IdTy, ExprTy>>(clause.t);
664
665 // Prepare list of objects that could end up in a "shared" clause.
668 objects, std::back_inserter(sharedObjects),
669 [&](const ObjectTy &object) { return !inFirstprivate(object); });
670
671 if (!sharedObjects.empty()) {
672 // [5.2:340:22]
673 if (auto dirParallel = findDirective(llvm::omp::OMPD_parallel)) {
674 auto *shared = makeClause(
675 llvm::omp::Clause::OMPC_shared,
676 tomp::clause::SharedT<TypeTy, IdTy, ExprTy>{/*List=*/sharedObjects});
677 dirParallel->clauses.push_back(shared);
678 applied = true;
679 }
680
681 // [5.2:340:24]
682 if (auto dirTeams = findDirective(llvm::omp::OMPD_teams)) {
683 auto *shared = makeClause(
684 llvm::omp::Clause::OMPC_shared,
685 tomp::clause::SharedT<TypeTy, IdTy, ExprTy>{/*List=*/sharedObjects});
686 dirTeams->clauses.push_back(shared);
687 applied = true;
688 }
689 }
690
691 // [5.2:340:27]
692 if (auto dirTarget = findDirective(llvm::omp::OMPD_target)) {
695 objects, std::back_inserter(tofrom),
696 [&](const ObjectTy &object) { return !mapBases.count(object.id()); });
697
698 if (!tofrom.empty()) {
699 using MapType =
701 auto *map =
702 makeClause(llvm::omp::Clause::OMPC_map,
704 {/*MapType=*/MapType::Tofrom,
705 /*MapTypeModifier=*/std::nullopt,
706 /*Mapper=*/std::nullopt, /*Iterator=*/std::nullopt,
707 /*LocatorList=*/std::move(tofrom)}});
708 dirTarget->clauses.push_back(map);
709 applied = true;
710 }
711 }
712
713 return applied;
714}
715
716// SHARED
717// [5.2:110:5-6]
718// Directives: parallel, task, taskloop, teams
719//
720// [5.2:340:31-32]
721// (31) The effect of the shared, default, thread_limit, or order clause is as
722// if it is applied to all leaf constructs that permit the clause.
723template <typename C, typename H>
724bool ConstructDecompositionT<C, H>::applyClause(
726 const ClauseTy *node) {
727 // [5.2:340:31]
728 return applyToAll(node);
729}
730
731// DEFAULT
732// [5.2:109:5-6]
733// Directives: parallel, task, taskloop, teams
734//
735// [5.2:340:31-32]
736// (31) The effect of the shared, default, thread_limit, or order clause is as
737// if it is applied to all leaf constructs that permit the clause.
738template <typename C, typename H>
739bool ConstructDecompositionT<C, H>::applyClause(
741 const ClauseTy *node) {
742 // [5.2:340:31]
743 return applyToAll(node);
744}
745
746// THREAD_LIMIT
747// [5.2:277:14-15]
748// Directives: target, teams
749//
750// [5.2:340:31-32]
751// (31) The effect of the shared, default, thread_limit, or order clause is as
752// if it is applied to all leaf constructs that permit the clause.
753template <typename C, typename H>
754bool ConstructDecompositionT<C, H>::applyClause(
756 const ClauseTy *node) {
757 // [5.2:340:31]
758 return applyToAll(node);
759}
760
761// ORDER
762// [5.2:234:3-4]
763// Directives: distribute, do, for, loop, simd
764//
765// [5.2:340:31-32]
766// (31) The effect of the shared, default, thread_limit, or order clause is as
767// if it is applied to all leaf constructs that permit the clause.
768template <typename C, typename H>
769bool ConstructDecompositionT<C, H>::applyClause(
771 const ClauseTy *node) {
772 // [5.2:340:31]
773 return applyToAll(node);
774}
775
776// ALLOCATE
777// [5.2:178:7-9]
778// Directives: allocators, distribute, do, for, parallel, scope, sections,
779// single, target, task, taskgroup, taskloop, teams
780//
781// [5.2:340:33-35]
782// (33) The effect of the allocate clause is as if it is applied to all leaf
783// constructs that permit the clause and to which a data-sharing attribute
784// clause that may create a private copy of the same list item is applied.
785template <typename C, typename H>
786bool ConstructDecompositionT<C, H>::applyClause(
788 const ClauseTy *node) {
789 // This one needs to be applied at the end, once we know which clauses are
790 // assigned to which leaf constructs.
791
792 // [5.2:340:33]
793 auto canMakePrivateCopy = [](llvm::omp::Clause id) {
794 switch (id) {
795 // Clauses with "privatization" property:
796 case llvm::omp::Clause::OMPC_firstprivate:
797 case llvm::omp::Clause::OMPC_in_reduction:
798 case llvm::omp::Clause::OMPC_lastprivate:
799 case llvm::omp::Clause::OMPC_linear:
800 case llvm::omp::Clause::OMPC_private:
801 case llvm::omp::Clause::OMPC_reduction:
802 case llvm::omp::Clause::OMPC_task_reduction:
803 return true;
804 default:
805 return false;
806 }
807 };
808
809 bool applied = applyIf(node, [&](const auto &leaf) {
810 return llvm::any_of(leaf.clauses, [&](const ClauseTy *n) {
811 return canMakePrivateCopy(n->id);
812 });
813 });
814
815 return applied;
816}
817
818// REDUCTION
819// [5.2:134:17-18]
820// Directives: do, for, loop, parallel, scope, sections, simd, taskloop, teams
821//
822// [5.2:340:36-37], [5.2:341:1-13]
823// (36) The effect of the reduction clause is as if it is applied to all leaf
824// constructs that permit the clause, except for the following constructs:
825// (1) The parallel construct, when combined with the sections,
826// worksharing-loop, loop, or taskloop construct; and
827// (3) The teams construct, when combined with the loop construct.
828// (4) For the parallel and teams constructs above, the effect of the reduction
829// clause instead is as if each list item or, for any list item that is an array
830// item, its corresponding base array or base pointer appears in a shared clause
831// for the construct.
832// (6) If the task reduction-modifier is specified, the effect is as if it only
833// modifies the behavior of the reduction clause on the innermost leaf construct
834// that accepts the modifier (see Section 5.5.8).
835// (8) If the inscan reduction-modifier is specified, the effect is as if it
836// modifies the behavior of the reduction clause on all constructs of the
837// combined construct to which the clause is applied and that accept the
838// modifier.
839// (10) If a list item in a reduction clause on a combined target construct does
840// not have the same base variable or base pointer as a list item in a map
841// clause on the construct, then the effect is as if the list item in the
842// reduction clause appears as a list item in a map clause with a map-type of
843// tofrom.
844template <typename C, typename H>
845bool ConstructDecompositionT<C, H>::applyClause(
847 const ClauseTy *node) {
849
850 // [5.2:340:36], [5.2:341:1], [5.2:341:3]
851 bool applyToParallel = true, applyToTeams = true;
852
853 auto dirParallel = findDirective(llvm::omp::Directive::OMPD_parallel);
854 if (dirParallel) {
855 auto exclusions = llvm::concat<const llvm::omp::Directive>(
857 llvm::omp::Directive::OMPD_loop,
858 llvm::omp::Directive::OMPD_sections,
859 llvm::omp::Directive::OMPD_taskloop,
860 });
861 auto present = [&](llvm::omp::Directive id) {
862 return findDirective(id) != nullptr;
863 };
864
865 if (llvm::any_of(exclusions, present))
866 applyToParallel = false;
867 }
868
869 auto dirTeams = findDirective(llvm::omp::Directive::OMPD_teams);
870 if (dirTeams) {
871 // The only exclusion is OMPD_loop.
872 if (findDirective(llvm::omp::Directive::OMPD_loop))
873 applyToTeams = false;
874 }
875
876 using ReductionModifier = typename ReductionTy::ReductionModifier;
877 using ReductionIdentifiers = typename ReductionTy::ReductionIdentifiers;
878
879 auto &objects = std::get<tomp::ObjectListT<IdTy, ExprTy>>(clause.t);
880 auto &modifier = std::get<std::optional<ReductionModifier>>(clause.t);
881
882 // Apply the reduction clause first to all directives according to the spec.
883 // If the reduction was applied at least once, proceed with the data sharing
884 // side-effects.
885 bool applied = false;
886
887 // [5.2:341:6], [5.2:341:8]
888 auto isValidModifier = [](llvm::omp::Directive dir, ReductionModifier mod,
889 bool alreadyApplied) {
890 switch (mod) {
891 case ReductionModifier::Inscan:
892 // According to [5.2:135:11-13], "inscan" only applies to
893 // worksharing-loop, worksharing-loop-simd, or "simd" constructs.
894 return dir == llvm::omp::Directive::OMPD_simd ||
896 case ReductionModifier::Task:
897 if (alreadyApplied)
898 return false;
899 // According to [5.2:135:16-18], "task" only applies to "parallel" and
900 // worksharing constructs.
901 return dir == llvm::omp::Directive::OMPD_parallel ||
903 case ReductionModifier::Default:
904 return true;
905 }
906 llvm_unreachable("Unexpected modifier");
907 };
908
909 auto *unmodified = makeClause(
910 llvm::omp::Clause::OMPC_reduction,
911 ReductionTy{
912 {/*ReductionModifier=*/std::nullopt,
913 /*ReductionIdentifiers=*/std::get<ReductionIdentifiers>(clause.t),
914 /*List=*/objects}});
915
916 ReductionModifier effective =
917 modifier.has_value() ? *modifier : ReductionModifier::Default;
918 bool effectiveApplied = false;
919 // Walk over the leaf constructs starting from the innermost, and apply
920 // the clause as required by the spec.
921 for (auto &leaf : llvm::reverse(leafs)) {
922 if (!llvm::omp::isAllowedClauseForDirective(leaf.id, node->id, version))
923 continue;
924 if (!applyToParallel && &leaf == dirParallel)
925 continue;
926 if (!applyToTeams && &leaf == dirTeams)
927 continue;
928 // Some form of the clause will be applied past this point.
929 if (isValidModifier(leaf.id, effective, effectiveApplied)) {
930 // Apply clause with modifier.
931 leaf.clauses.push_back(node);
932 effectiveApplied = true;
933 } else {
934 // Apply clause without modifier.
935 leaf.clauses.push_back(unmodified);
936 }
937 // The modifier must be applied to some construct.
938 applied = effectiveApplied;
939 }
940
941 if (!applied)
942 return false;
943
945 llvm::transform(objects, std::back_inserter(sharedObjects),
946 [&](const ObjectTy &object) {
947 auto maybeBase = helper.getBaseObject(object);
948 return maybeBase ? *maybeBase : object;
949 });
950
951 // [5.2:341:4]
952 if (!sharedObjects.empty()) {
953 if (dirParallel && !applyToParallel) {
954 auto *shared = makeClause(
955 llvm::omp::Clause::OMPC_shared,
956 tomp::clause::SharedT<TypeTy, IdTy, ExprTy>{/*List=*/sharedObjects});
957 dirParallel->clauses.push_back(shared);
958 }
959 if (dirTeams && !applyToTeams) {
960 auto *shared = makeClause(
961 llvm::omp::Clause::OMPC_shared,
962 tomp::clause::SharedT<TypeTy, IdTy, ExprTy>{/*List=*/sharedObjects});
963 dirTeams->clauses.push_back(shared);
964 }
965 }
966
967 // [5.2:341:10]
968 auto dirTarget = findDirective(llvm::omp::Directive::OMPD_target);
969 if (dirTarget && leafs.size() > 1) {
971 llvm::copy_if(objects, std::back_inserter(tofrom),
972 [&](const ObjectTy &object) {
973 if (auto maybeBase = helper.getBaseObject(object))
974 return !mapBases.count(maybeBase->id());
975 return !mapBases.count(object.id()); // XXX is this ok?
976 });
977 if (!tofrom.empty()) {
978 using MapType =
980 auto *map = makeClause(
981 llvm::omp::Clause::OMPC_map,
983 {/*MapType=*/MapType::Tofrom, /*MapTypeModifier=*/std::nullopt,
984 /*Mapper=*/std::nullopt, /*Iterator=*/std::nullopt,
985 /*LocatorList=*/std::move(tofrom)}});
986
987 dirTarget->clauses.push_back(map);
988 applied = true;
989 }
990 }
991
992 return applied;
993}
994
995// IF
996// [5.2:72:7-9]
997// Directives: cancel, parallel, simd, target, target data, target enter data,
998// target exit data, target update, task, taskloop
999//
1000// [5.2:72:15-18]
1001// (15) For combined or composite constructs, the if clause only applies to the
1002// semantics of the construct named in the directive-name-modifier.
1003// (16) For a combined or composite construct, if no directive-name-modifier is
1004// specified then the if clause applies to all constituent constructs to which
1005// an if clause can apply.
1006template <typename C, typename H>
1007bool ConstructDecompositionT<C, H>::applyClause(
1009 const ClauseTy *node) {
1010 using DirectiveNameModifier =
1012 using IfExpression = typename clause::IfT<TypeTy, IdTy, ExprTy>::IfExpression;
1013 auto &modifier = std::get<std::optional<DirectiveNameModifier>>(clause.t);
1014
1015 if (modifier) {
1016 llvm::omp::Directive dirId = *modifier;
1017 auto *unmodified =
1018 makeClause(llvm::omp::Clause::OMPC_if,
1020 {/*DirectiveNameModifier=*/std::nullopt,
1021 /*IfExpression=*/std::get<IfExpression>(clause.t)}});
1022
1023 if (auto *hasDir = findDirective(dirId)) {
1024 hasDir->clauses.push_back(unmodified);
1025 return true;
1026 }
1027 return false;
1028 }
1029
1030 return applyToAll(node);
1031}
1032
1033// LINEAR
1034// [5.2:118:1-2]
1035// Directives: declare simd, do, for, simd
1036//
1037// [5.2:341:15-22]
1038// (15.1) The effect of the linear clause is as if it is applied to the
1039// innermost leaf construct.
1040// (15.2) Additionally, if the list item is not the iteration variable of a simd
1041// or worksharing-loop SIMD construct, the effect on the outer leaf constructs
1042// is as if the list item was specified in firstprivate and lastprivate clauses
1043// on the combined or composite construct, with the rules specified above
1044// applied.
1045// (19) If a list item of the linear clause is the iteration variable of a simd
1046// or worksharing-loop SIMD construct and it is not declared in the construct,
1047// the effect on the outer leaf constructs is as if the list item was specified
1048// in a lastprivate clause on the combined or composite construct with the rules
1049// specified above applied.
1050template <typename C, typename H>
1051bool ConstructDecompositionT<C, H>::applyClause(
1053 const ClauseTy *node) {
1054 // [5.2:341:15.1]
1055 if (!applyToInnermost(node))
1056 return false;
1057
1058 // [5.2:341:15.2], [5.2:341:19]
1059 auto dirSimd = findDirective(llvm::omp::Directive::OMPD_simd);
1060 std::optional<ObjectTy> iterVar = helper.getLoopIterVar();
1061 const auto &objects = std::get<tomp::ObjectListT<IdTy, ExprTy>>(clause.t);
1062
1063 // Lists of objects that will be used to construct "firstprivate" and
1064 // "lastprivate" clauses.
1066
1067 for (const ObjectTy &object : objects) {
1068 last.push_back(object);
1069 if (!dirSimd || !iterVar || object.id() != iterVar->id())
1070 first.push_back(object);
1071 }
1072
1073 if (!first.empty()) {
1074 auto *firstp = makeClause(
1075 llvm::omp::Clause::OMPC_firstprivate,
1077 nodes.push_back(firstp); // Appending to the main clause list.
1078 }
1079 if (!last.empty()) {
1080 auto *lastp =
1081 makeClause(llvm::omp::Clause::OMPC_lastprivate,
1083 {/*LastprivateModifier=*/std::nullopt, /*List=*/last}});
1084 nodes.push_back(lastp); // Appending to the main clause list.
1085 }
1086 return true;
1087}
1088
1089// NOWAIT
1090// [5.2:308:11-13]
1091// Directives: dispatch, do, for, interop, scope, sections, single, target,
1092// target enter data, target exit data, target update, taskwait, workshare
1093//
1094// [5.2:341:23]
1095// (23) The effect of the nowait clause is as if it is applied to the outermost
1096// leaf construct that permits it.
1097template <typename C, typename H>
1098bool ConstructDecompositionT<C, H>::applyClause(
1100 const ClauseTy *node) {
1101 return applyToOutermost(node);
1102}
1103
1104template <typename C, typename H> bool ConstructDecompositionT<C, H>::split() {
1105 bool success = true;
1106
1107 for (llvm::omp::Directive leaf :
1109 leafs.push_back(LeafReprInternal{leaf, /*clauses=*/{}});
1110
1111 for (const ClauseTy *node : nodes)
1112 addClauseSymsToMap(*node, node);
1113
1114 // First we need to apply LINEAR, because it can generate additional
1115 // "firstprivate" and "lastprivate" clauses that apply to the combined/
1116 // composite construct.
1117 // Collect them separately, because they may modify the clause list.
1119 for (const ClauseTy *node : nodes) {
1120 if (node->id == llvm::omp::Clause::OMPC_linear)
1121 linears.push_back(node);
1122 }
1123 for (const auto *node : linears) {
1124 success = success &&
1125 applyClause(std::get<tomp::clause::LinearT<TypeTy, IdTy, ExprTy>>(
1126 node->u),
1127 node);
1128 }
1129
1130 // "allocate" clauses need to be applied last since they need to see
1131 // which directives have data-privatizing clauses.
1132 auto skip = [](const ClauseTy *node) {
1133 switch (node->id) {
1134 case llvm::omp::Clause::OMPC_allocate:
1135 case llvm::omp::Clause::OMPC_linear:
1136 return true;
1137 default:
1138 return false;
1139 }
1140 };
1141
1142 // Apply (almost) all clauses.
1143 for (const ClauseTy *node : nodes) {
1144 if (skip(node))
1145 continue;
1146 success =
1147 success &&
1148 std::visit([&](auto &&s) { return applyClause(s, node); }, node->u);
1149 }
1150
1151 // Apply "allocate".
1152 for (const ClauseTy *node : nodes) {
1153 if (node->id != llvm::omp::Clause::OMPC_allocate)
1154 continue;
1155 success =
1156 success &&
1157 std::visit([&](auto &&s) { return applyClause(s, node); }, node->u);
1158 }
1159
1160 return success;
1161}
1162
1163} // namespace tomp
1164
1165#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:375
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
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