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 22 using namespace llvm; 23 using namespace llvm::omp; 24 25 #define GEN_DIRECTIVES_IMPL 26 #include "llvm/Frontend/OpenMP/OMP.inc" 27 28 static iterator_range<ArrayRef<Directive>::iterator> 29 getFirstCompositeRange(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(*It) == Association::Loop) 53 return It; 54 } 55 return List.end(); 56 }; 57 58 auto Empty = llvm::make_range(Leafs.end(), 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(std::next(Begin), Leafs.end())); 66 if (End == Leafs.end()) 67 return Empty; 68 69 for (; End != Leafs.end(); ++End) { 70 if (getDirectiveAssociation(*End) != Association::Loop) 71 break; 72 } 73 return llvm::make_range(Begin, End); 74 } 75 76 namespace llvm::omp { 77 ArrayRef<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 85 ArrayRef<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 95 ArrayRef<Directive> 96 getLeafOrCompositeConstructs(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(llvm::make_range(Iter, Leafs.end())); 104 // All directives before the range are leaf constructs. 105 for (; Iter != Range.begin(); ++Iter) 106 Output.push_back(*Iter); 107 if (!Range.empty()) { 108 Directive Comp = 109 getCompoundConstruct(ArrayTy(Range.begin(), Range.end())); 110 assert(Comp != OMPD_unknown); 111 Output.push_back(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 123 Directive 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(P); 133 if (!Ls.empty()) 134 RawLeafs.append(Ls.begin(), Ls.end()); 135 else 136 RawLeafs.push_back(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(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 LeafConstructTable, LeafConstructTableEndDirective, 152 static_cast<std::decay_t<decltype(*LeafConstructTable)>>(RawLeafs.data()), 153 [](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(LeafConstructTable)) 164 return OMPD_unknown; 165 166 // Verify that we got a match. 167 Directive Found = (*Iter)[0]; 168 ArrayRef<Directive> FoundLeafs = getLeafConstructs(Found); 169 if (FoundLeafs == GivenLeafs) 170 return Found; 171 return OMPD_unknown; 172 } 173 174 bool isLeafConstruct(Directive D) { return getLeafConstructs(D).empty(); } 175 176 bool 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 184 bool 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