blob: c1556ff3c74d72c2e9731dd6281a32697b03e161 [file] [log] [blame]
//===- OMP.cpp ------ Collection of helpers for OpenMP --------------------===//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
#include "llvm/Frontend/OpenMP/OMP.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/ADT/StringSwitch.h"
#include "llvm/Support/ErrorHandling.h"
#include <algorithm>
#include <iterator>
#include <type_traits>
using namespace llvm;
using namespace llvm::omp;
#include "llvm/Frontend/OpenMP/"
static iterator_range<ArrayRef<Directive>::iterator>
getFirstCompositeRange(iterator_range<ArrayRef<Directive>::iterator> Leafs) {
// OpenMP Spec 5.2: [17.3, 8-9]
// If directive-name-A and directive-name-B both correspond to loop-
// associated constructs then directive-name is a composite construct
// otherwise directive-name is a combined construct.
// In the list of leaf constructs, find the first loop-associated construct,
// this is the beginning of the returned range. Then, starting from the
// immediately following leaf construct, find the first sequence of adjacent
// loop-associated constructs. The last of those is the last one of the
// range, that is, the end of the range is one past that element.
// If such a sequence of adjacent loop-associated directives does not exist,
// return an empty range.
// The end of the returned range (including empty range) is intended to be
// a point from which the search for the next range could resume.
// Consequently, this function can't return a range with a single leaf
// construct in it.
auto firstLoopAssociated =
[](iterator_range<ArrayRef<Directive>::iterator> List) {
for (auto It = List.begin(), End = List.end(); It != End; ++It) {
if (getDirectiveAssociation(*It) == Association::Loop)
return It;
return List.end();
auto Empty = llvm::make_range(Leafs.end(), Leafs.end());
auto Begin = firstLoopAssociated(Leafs);
if (Begin == Leafs.end())
return Empty;
auto End =
firstLoopAssociated(llvm::make_range(std::next(Begin), Leafs.end()));
if (End == Leafs.end())
return Empty;
for (; End != Leafs.end(); ++End) {
if (getDirectiveAssociation(*End) != Association::Loop)
return llvm::make_range(Begin, End);
namespace llvm::omp {
ArrayRef<Directive> getLeafConstructs(Directive D) {
auto Idx = static_cast<std::size_t>(D);
if (Idx >= Directive_enumSize)
return std::nullopt;
const auto *Row = LeafConstructTable[LeafConstructTableOrdering[Idx]];
return ArrayRef(&Row[2], static_cast<int>(Row[1]));
ArrayRef<Directive> getLeafConstructsOrSelf(Directive D) {
if (auto Leafs = getLeafConstructs(D); !Leafs.empty())
return Leafs;
auto Idx = static_cast<size_t>(D);
assert(Idx < Directive_enumSize && "Invalid directive");
const auto *Row = LeafConstructTable[LeafConstructTableOrdering[Idx]];
// The first entry in the row is the directive itself.
return ArrayRef(&Row[0], &Row[0] + 1);
getLeafOrCompositeConstructs(Directive D, SmallVectorImpl<Directive> &Output) {
using ArrayTy = ArrayRef<Directive>;
using IteratorTy = ArrayTy::iterator;
ArrayRef<Directive> Leafs = getLeafConstructsOrSelf(D);
IteratorTy Iter = Leafs.begin();
do {
auto Range = getFirstCompositeRange(llvm::make_range(Iter, Leafs.end()));
// All directives before the range are leaf constructs.
for (; Iter != Range.begin(); ++Iter)
if (!Range.empty()) {
Directive Comp =
getCompoundConstruct(ArrayTy(Range.begin(), Range.end()));
assert(Comp != OMPD_unknown);
Iter = Range.end();
// As of now, a composite construct must contain all constituent leaf
// constructs from some point until the end of all constituent leaf
// constructs.
assert(Iter == Leafs.end() && "Malformed directive");
} while (Iter != Leafs.end());
return Output;
Directive getCompoundConstruct(ArrayRef<Directive> Parts) {
if (Parts.empty())
return OMPD_unknown;
// Parts don't have to be leafs, so expand them into leafs first.
// Store the expanded leafs in the same format as rows in the leaf
// table (generated by tablegen).
SmallVector<Directive> RawLeafs(2);
for (Directive P : Parts) {
ArrayRef<Directive> Ls = getLeafConstructs(P);
if (!Ls.empty())
RawLeafs.append(Ls.begin(), Ls.end());
// RawLeafs will be used as key in the binary search. The search doesn't
// guarantee that the exact same entry will be found (since RawLeafs may
// not correspond to any compound directive). Because of that, we will
// need to compare the search result with the given set of leafs.
// Also, if there is only one leaf in the list, it corresponds to itself,
// no search is necessary.
auto GivenLeafs{ArrayRef<Directive>(RawLeafs).drop_front(2)};
if (GivenLeafs.size() == 1)
return GivenLeafs.front();
RawLeafs[1] = static_cast<Directive>(GivenLeafs.size());
auto Iter = std::lower_bound(
LeafConstructTable, LeafConstructTableEndDirective,
[](const llvm::omp::Directive *RowA, const llvm::omp::Directive *RowB) {
const auto *BeginA = &RowA[2];
const auto *EndA = BeginA + static_cast<int>(RowA[1]);
const auto *BeginB = &RowB[2];
const auto *EndB = BeginB + static_cast<int>(RowB[1]);
if (BeginA == EndA && BeginB == EndB)
return static_cast<int>(RowA[0]) < static_cast<int>(RowB[0]);
return std::lexicographical_compare(BeginA, EndA, BeginB, EndB);
if (Iter == std::end(LeafConstructTable))
return OMPD_unknown;
// Verify that we got a match.
Directive Found = (*Iter)[0];
ArrayRef<Directive> FoundLeafs = getLeafConstructs(Found);
if (FoundLeafs == GivenLeafs)
return Found;
return OMPD_unknown;
bool isLeafConstruct(Directive D) { return getLeafConstructs(D).empty(); }
bool isCompositeConstruct(Directive D) {
ArrayRef<Directive> Leafs = getLeafConstructsOrSelf(D);
if (Leafs.size() <= 1)
return false;
auto Range = getFirstCompositeRange(Leafs);
return Range.begin() == Leafs.begin() && Range.end() == Leafs.end();
bool isCombinedConstruct(Directive D) {
// OpenMP Spec 5.2: [17.3, 9-10]
// Otherwise directive-name is a combined construct.
return !getLeafConstructs(D).empty() && !isCompositeConstruct(D);
} // namespace llvm::omp