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/STLExtras.h"
13#include "llvm/ADT/SmallVector.h"
14#include "llvm/ADT/StringRef.h"
15#include "llvm/ADT/StringSwitch.h"
16#include "llvm/Support/ErrorHandling.h"
17
18#include <algorithm>
19#include <iterator>
20#include <type_traits>
21
22using namespace llvm;
23using namespace llvm::omp;
24
25#define GEN_DIRECTIVES_IMPL
26#include "llvm/Frontend/OpenMP/OMP.inc"
27
28static iterator_range<ArrayRef<Directive>::iterator>
29getFirstCompositeRange(iterator_range<ArrayRef<Directive>::iterator> Leafs) {
30 // OpenMP Spec 5.2: [17.3, 8-9]
31 // If directive-name-A and directive-name-B both correspond to loop-
32 // associated constructs then directive-name is a composite construct
33 // otherwise directive-name is a combined construct.
34 //
35 // In the list of leaf constructs, find the first loop-associated construct,
36 // this is the beginning of the returned range. Then, starting from the
37 // immediately following leaf construct, find the first sequence of adjacent
38 // loop-associated constructs. The last of those is the last one of the
39 // range, that is, the end of the range is one past that element.
40 // If such a sequence of adjacent loop-associated directives does not exist,
41 // return an empty range.
42 //
43 // The end of the returned range (including empty range) is intended to be
44 // a point from which the search for the next range could resume.
45 //
46 // Consequently, this function can't return a range with a single leaf
47 // construct in it.
48
49 auto firstLoopAssociated =
50 [](iterator_range<ArrayRef<Directive>::iterator> List) {
51 for (auto It = List.begin(), End = List.end(); It != End; ++It) {
52 if (getDirectiveAssociation(Dir: *It) == Association::Loop)
53 return It;
54 }
55 return List.end();
56 };
57
58 auto Empty = llvm::make_range(x: Leafs.end(), y: Leafs.end());
59
60 auto Begin = firstLoopAssociated(Leafs);
61 if (Begin == Leafs.end())
62 return Empty;
63
64 auto End =
65 firstLoopAssociated(llvm::make_range(x: std::next(x: Begin), y: Leafs.end()));
66 if (End == Leafs.end())
67 return Empty;
68
69 for (; End != Leafs.end(); ++End) {
70 if (getDirectiveAssociation(Dir: *End) != Association::Loop)
71 break;
72 }
73 return llvm::make_range(x: Begin, y: End);
74}
75
76namespace llvm::omp {
77ArrayRef<Directive> getLeafConstructs(Directive D) {
78 auto Idx = static_cast<std::size_t>(D);
79 if (Idx >= Directive_enumSize)
80 return std::nullopt;
81 const auto *Row = LeafConstructTable[LeafConstructTableOrdering[Idx]];
82 return ArrayRef(&Row[2], static_cast<int>(Row[1]));
83}
84
85ArrayRef<Directive> getLeafConstructsOrSelf(Directive D) {
86 if (auto Leafs = getLeafConstructs(D); !Leafs.empty())
87 return Leafs;
88 auto Idx = static_cast<size_t>(D);
89 assert(Idx < Directive_enumSize && "Invalid directive");
90 const auto *Row = LeafConstructTable[LeafConstructTableOrdering[Idx]];
91 // The first entry in the row is the directive itself.
92 return ArrayRef(&Row[0], &Row[0] + 1);
93}
94
95ArrayRef<Directive>
96getLeafOrCompositeConstructs(Directive D, SmallVectorImpl<Directive> &Output) {
97 using ArrayTy = ArrayRef<Directive>;
98 using IteratorTy = ArrayTy::iterator;
99 ArrayRef<Directive> Leafs = getLeafConstructsOrSelf(D);
100
101 IteratorTy Iter = Leafs.begin();
102 do {
103 auto Range = getFirstCompositeRange(Leafs: llvm::make_range(x: Iter, y: Leafs.end()));
104 // All directives before the range are leaf constructs.
105 for (; Iter != Range.begin(); ++Iter)
106 Output.push_back(Elt: *Iter);
107 if (!Range.empty()) {
108 Directive Comp =
109 getCompoundConstruct(Parts: ArrayTy(Range.begin(), Range.end()));
110 assert(Comp != OMPD_unknown);
111 Output.push_back(Elt: Comp);
112 Iter = Range.end();
113 // As of now, a composite construct must contain all constituent leaf
114 // constructs from some point until the end of all constituent leaf
115 // constructs.
116 assert(Iter == Leafs.end() && "Malformed directive");
117 }
118 } while (Iter != Leafs.end());
119
120 return Output;
121}
122
123Directive getCompoundConstruct(ArrayRef<Directive> Parts) {
124 if (Parts.empty())
125 return OMPD_unknown;
126
127 // Parts don't have to be leafs, so expand them into leafs first.
128 // Store the expanded leafs in the same format as rows in the leaf
129 // table (generated by tablegen).
130 SmallVector<Directive> RawLeafs(2);
131 for (Directive P : Parts) {
132 ArrayRef<Directive> Ls = getLeafConstructs(D: P);
133 if (!Ls.empty())
134 RawLeafs.append(in_start: Ls.begin(), in_end: Ls.end());
135 else
136 RawLeafs.push_back(Elt: P);
137 }
138
139 // RawLeafs will be used as key in the binary search. The search doesn't
140 // guarantee that the exact same entry will be found (since RawLeafs may
141 // not correspond to any compound directive). Because of that, we will
142 // need to compare the search result with the given set of leafs.
143 // Also, if there is only one leaf in the list, it corresponds to itself,
144 // no search is necessary.
145 auto GivenLeafs{ArrayRef<Directive>(RawLeafs).drop_front(N: 2)};
146 if (GivenLeafs.size() == 1)
147 return GivenLeafs.front();
148 RawLeafs[1] = static_cast<Directive>(GivenLeafs.size());
149
150 auto Iter = std::lower_bound(
151 first: LeafConstructTable, last: LeafConstructTableEndDirective,
152 val: static_cast<std::decay_t<decltype(*LeafConstructTable)>>(RawLeafs.data()),
153 comp: [](const llvm::omp::Directive *RowA, const llvm::omp::Directive *RowB) {
154 const auto *BeginA = &RowA[2];
155 const auto *EndA = BeginA + static_cast<int>(RowA[1]);
156 const auto *BeginB = &RowB[2];
157 const auto *EndB = BeginB + static_cast<int>(RowB[1]);
158 if (BeginA == EndA && BeginB == EndB)
159 return static_cast<int>(RowA[0]) < static_cast<int>(RowB[0]);
160 return std::lexicographical_compare(BeginA, EndA, BeginB, EndB);
161 });
162
163 if (Iter == std::end(arr: LeafConstructTable))
164 return OMPD_unknown;
165
166 // Verify that we got a match.
167 Directive Found = (*Iter)[0];
168 ArrayRef<Directive> FoundLeafs = getLeafConstructs(D: Found);
169 if (FoundLeafs == GivenLeafs)
170 return Found;
171 return OMPD_unknown;
172}
173
174bool isLeafConstruct(Directive D) { return getLeafConstructs(D).empty(); }
175
176bool isCompositeConstruct(Directive D) {
177 ArrayRef<Directive> Leafs = getLeafConstructsOrSelf(D);
178 if (Leafs.size() <= 1)
179 return false;
180 auto Range = getFirstCompositeRange(Leafs);
181 return Range.begin() == Leafs.begin() && Range.end() == Leafs.end();
182}
183
184bool isCombinedConstruct(Directive D) {
185 // OpenMP Spec 5.2: [17.3, 9-10]
186 // Otherwise directive-name is a combined construct.
187 return !getLeafConstructs(D).empty() && !isCompositeConstruct(D);
188}
189} // namespace llvm::omp
190