llvm/lib/Frontend/OpenMP/OMP.cpp

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