1//===- VFABIDemangling.cpp - Vector Function ABI demangling utilities. ---===//
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/ADT/SmallSet.h"
10#include "llvm/ADT/SmallString.h"
11#include "llvm/Analysis/VectorUtils.h"
12
13using namespace llvm;
14
15namespace {
16/// Utilities for the Vector Function ABI name parser.
17
18/// Return types for the parser functions.
19enum class ParseRet {
20  OK,   // Found.
21  None, // Not found.
22  Error // Syntax error.
23};
24
25/// Extracts the `<isa>` information from the mangled string, and
26/// sets the `ISA` accordingly.
27ParseRet tryParseISA(StringRef &MangledName, VFISAKind &ISA) {
28  if (MangledName.empty())
29    return ParseRet::Error;
30
31  if (MangledName.startswith(VFABI::_LLVM_)) {
32    MangledName = MangledName.drop_front(strlen(VFABI::_LLVM_));
33    ISA = VFISAKind::LLVM;
34  } else {
35    ISA = StringSwitch<VFISAKind>(MangledName.take_front(1))
36              .Case("n", VFISAKind::AdvancedSIMD)
37              .Case("s", VFISAKind::SVE)
38              .Case("b", VFISAKind::SSE)
39              .Case("c", VFISAKind::AVX)
40              .Case("d", VFISAKind::AVX2)
41              .Case("e", VFISAKind::AVX512)
42              .Default(VFISAKind::Unknown);
43    MangledName = MangledName.drop_front(1);
44  }
45
46  return ParseRet::OK;
47}
48
49/// Extracts the `<mask>` information from the mangled string, and
50/// sets `IsMasked` accordingly. The input string `MangledName` is
51/// left unmodified.
52ParseRet tryParseMask(StringRef &MangledName, bool &IsMasked) {
53  if (MangledName.consume_front("M")) {
54    IsMasked = true;
55    return ParseRet::OK;
56  }
57
58  if (MangledName.consume_front("N")) {
59    IsMasked = false;
60    return ParseRet::OK;
61  }
62
63  return ParseRet::Error;
64}
65
66/// Extract the `<vlen>` information from the mangled string, and
67/// sets `VF` accordingly. A `<vlen> == "x"` token is interpreted as a scalable
68/// vector length. On success, the `<vlen>` token is removed from
69/// the input string `ParseString`.
70///
71ParseRet tryParseVLEN(StringRef &ParseString, unsigned &VF, bool &IsScalable) {
72  if (ParseString.consume_front("x")) {
73    // Set VF to 0, to be later adjusted to a value grater than zero
74    // by looking at the signature of the vector function with
75    // `getECFromSignature`.
76    VF = 0;
77    IsScalable = true;
78    return ParseRet::OK;
79  }
80
81  if (ParseString.consumeInteger(10, VF))
82    return ParseRet::Error;
83
84  // The token `0` is invalid for VLEN.
85  if (VF == 0)
86    return ParseRet::Error;
87
88  IsScalable = false;
89  return ParseRet::OK;
90}
91
92/// The function looks for the following strings at the beginning of
93/// the input string `ParseString`:
94///
95///  <token> <number>
96///
97/// On success, it removes the parsed parameter from `ParseString`,
98/// sets `PKind` to the correspondent enum value, sets `Pos` to
99/// <number>, and return success.  On a syntax error, it return a
100/// parsing error. If nothing is parsed, it returns None.
101///
102/// The function expects <token> to be one of "ls", "Rs", "Us" or
103/// "Ls".
104ParseRet tryParseLinearTokenWithRuntimeStep(StringRef &ParseString,
105                                            VFParamKind &PKind, int &Pos,
106                                            const StringRef Token) {
107  if (ParseString.consume_front(Token)) {
108    PKind = VFABI::getVFParamKindFromString(Token);
109    if (ParseString.consumeInteger(10, Pos))
110      return ParseRet::Error;
111    return ParseRet::OK;
112  }
113
114  return ParseRet::None;
115}
116
117/// The function looks for the following stringt at the beginning of
118/// the input string `ParseString`:
119///
120///  <token> <number>
121///
122/// <token> is one of "ls", "Rs", "Us" or "Ls".
123///
124/// On success, it removes the parsed parameter from `ParseString`,
125/// sets `PKind` to the correspondent enum value, sets `StepOrPos` to
126/// <number>, and return success.  On a syntax error, it return a
127/// parsing error. If nothing is parsed, it returns None.
128ParseRet tryParseLinearWithRuntimeStep(StringRef &ParseString,
129                                       VFParamKind &PKind, int &StepOrPos) {
130  ParseRet Ret;
131
132  // "ls" <RuntimeStepPos>
133  Ret = tryParseLinearTokenWithRuntimeStep(ParseString, PKind, StepOrPos, "ls");
134  if (Ret != ParseRet::None)
135    return Ret;
136
137  // "Rs" <RuntimeStepPos>
138  Ret = tryParseLinearTokenWithRuntimeStep(ParseString, PKind, StepOrPos, "Rs");
139  if (Ret != ParseRet::None)
140    return Ret;
141
142  // "Ls" <RuntimeStepPos>
143  Ret = tryParseLinearTokenWithRuntimeStep(ParseString, PKind, StepOrPos, "Ls");
144  if (Ret != ParseRet::None)
145    return Ret;
146
147  // "Us" <RuntimeStepPos>
148  Ret = tryParseLinearTokenWithRuntimeStep(ParseString, PKind, StepOrPos, "Us");
149  if (Ret != ParseRet::None)
150    return Ret;
151
152  return ParseRet::None;
153}
154
155/// The function looks for the following strings at the beginning of
156/// the input string `ParseString`:
157///
158///  <token> {"n"} <number>
159///
160/// On success, it removes the parsed parameter from `ParseString`,
161/// sets `PKind` to the correspondent enum value, sets `LinearStep` to
162/// <number>, and return success.  On a syntax error, it return a
163/// parsing error. If nothing is parsed, it returns None.
164///
165/// The function expects <token> to be one of "l", "R", "U" or
166/// "L".
167ParseRet tryParseCompileTimeLinearToken(StringRef &ParseString,
168                                        VFParamKind &PKind, int &LinearStep,
169                                        const StringRef Token) {
170  if (ParseString.consume_front(Token)) {
171    PKind = VFABI::getVFParamKindFromString(Token);
172    const bool Negate = ParseString.consume_front("n");
173    if (ParseString.consumeInteger(10, LinearStep))
174      LinearStep = 1;
175    if (Negate)
176      LinearStep *= -1;
177    return ParseRet::OK;
178  }
179
180  return ParseRet::None;
181}
182
183/// The function looks for the following strings at the beginning of
184/// the input string `ParseString`:
185///
186/// ["l" | "R" | "U" | "L"] {"n"} <number>
187///
188/// On success, it removes the parsed parameter from `ParseString`,
189/// sets `PKind` to the correspondent enum value, sets `LinearStep` to
190/// <number>, and return success.  On a syntax error, it return a
191/// parsing error. If nothing is parsed, it returns None.
192ParseRet tryParseLinearWithCompileTimeStep(StringRef &ParseString,
193                                           VFParamKind &PKind, int &StepOrPos) {
194  // "l" {"n"} <CompileTimeStep>
195  if (tryParseCompileTimeLinearToken(ParseString, PKind, StepOrPos, "l") ==
196      ParseRet::OK)
197    return ParseRet::OK;
198
199  // "R" {"n"} <CompileTimeStep>
200  if (tryParseCompileTimeLinearToken(ParseString, PKind, StepOrPos, "R") ==
201      ParseRet::OK)
202    return ParseRet::OK;
203
204  // "L" {"n"} <CompileTimeStep>
205  if (tryParseCompileTimeLinearToken(ParseString, PKind, StepOrPos, "L") ==
206      ParseRet::OK)
207    return ParseRet::OK;
208
209  // "U" {"n"} <CompileTimeStep>
210  if (tryParseCompileTimeLinearToken(ParseString, PKind, StepOrPos, "U") ==
211      ParseRet::OK)
212    return ParseRet::OK;
213
214  return ParseRet::None;
215}
216
217/// Looks into the <parameters> part of the mangled name in search
218/// for valid paramaters at the beginning of the string
219/// `ParseString`.
220///
221/// On success, it removes the parsed parameter from `ParseString`,
222/// sets `PKind` to the correspondent enum value, sets `StepOrPos`
223/// accordingly, and return success.  On a syntax error, it return a
224/// parsing error. If nothing is parsed, it returns None.
225ParseRet tryParseParameter(StringRef &ParseString, VFParamKind &PKind,
226                           int &StepOrPos) {
227  if (ParseString.consume_front("v")) {
228    PKind = VFParamKind::Vector;
229    StepOrPos = 0;
230    return ParseRet::OK;
231  }
232
233  if (ParseString.consume_front("u")) {
234    PKind = VFParamKind::OMP_Uniform;
235    StepOrPos = 0;
236    return ParseRet::OK;
237  }
238
239  const ParseRet HasLinearRuntime =
240      tryParseLinearWithRuntimeStep(ParseString, PKind, StepOrPos);
241  if (HasLinearRuntime != ParseRet::None)
242    return HasLinearRuntime;
243
244  const ParseRet HasLinearCompileTime =
245      tryParseLinearWithCompileTimeStep(ParseString, PKind, StepOrPos);
246  if (HasLinearCompileTime != ParseRet::None)
247    return HasLinearCompileTime;
248
249  return ParseRet::None;
250}
251
252/// Looks into the <parameters> part of the mangled name in search
253/// of a valid 'aligned' clause. The function should be invoked
254/// after parsing a parameter via `tryParseParameter`.
255///
256/// On success, it removes the parsed parameter from `ParseString`,
257/// sets `PKind` to the correspondent enum value, sets `StepOrPos`
258/// accordingly, and return success.  On a syntax error, it return a
259/// parsing error. If nothing is parsed, it returns None.
260ParseRet tryParseAlign(StringRef &ParseString, Align &Alignment) {
261  uint64_t Val;
262  //    "a" <number>
263  if (ParseString.consume_front("a")) {
264    if (ParseString.consumeInteger(10, Val))
265      return ParseRet::Error;
266
267    if (!isPowerOf2_64(Val))
268      return ParseRet::Error;
269
270    Alignment = Align(Val);
271
272    return ParseRet::OK;
273  }
274
275  return ParseRet::None;
276}
277#ifndef NDEBUG
278// Verify the assumtion that all vectors in the signature of a vector
279// function have the same number of elements.
280bool verifyAllVectorsHaveSameWidth(FunctionType *Signature) {
281  SmallVector<VectorType *, 2> VecTys;
282  if (auto *RetTy = dyn_cast<VectorType>(Signature->getReturnType()))
283    VecTys.push_back(RetTy);
284  for (auto *Ty : Signature->params())
285    if (auto *VTy = dyn_cast<VectorType>(Ty))
286      VecTys.push_back(VTy);
287
288  if (VecTys.size() <= 1)
289    return true;
290
291  assert(VecTys.size() > 1 && "Invalid number of elements.");
292  const ElementCount EC = VecTys[0]->getElementCount();
293  return llvm::all_of(llvm::drop_begin(VecTys), [&EC](VectorType *VTy) {
294    return (EC == VTy->getElementCount());
295  });
296}
297
298#endif // NDEBUG
299
300// Extract the VectorizationFactor from a given function signature,
301// under the assumtion that all vectors have the same number of
302// elements, i.e. same ElementCount.Min.
303ElementCount getECFromSignature(FunctionType *Signature) {
304  assert(verifyAllVectorsHaveSameWidth(Signature) &&
305         "Invalid vector signature.");
306
307  if (auto *RetTy = dyn_cast<VectorType>(Signature->getReturnType()))
308    return RetTy->getElementCount();
309  for (auto *Ty : Signature->params())
310    if (auto *VTy = dyn_cast<VectorType>(Ty))
311      return VTy->getElementCount();
312
313  return ElementCount::getFixed(/*Min=*/1);
314}
315} // namespace
316
317// Format of the ABI name:
318// _ZGV<isa><mask><vlen><parameters>_<scalarname>[(<redirection>)]
319Optional<VFInfo> VFABI::tryDemangleForVFABI(StringRef MangledName,
320                                            const Module &M) {
321  const StringRef OriginalName = MangledName;
322  // Assume there is no custom name <redirection>, and therefore the
323  // vector name consists of
324  // _ZGV<isa><mask><vlen><parameters>_<scalarname>.
325  StringRef VectorName = MangledName;
326
327  // Parse the fixed size part of the manled name
328  if (!MangledName.consume_front("_ZGV"))
329    return None;
330
331  // Extract ISA. An unknow ISA is also supported, so we accept all
332  // values.
333  VFISAKind ISA;
334  if (tryParseISA(MangledName, ISA) != ParseRet::OK)
335    return None;
336
337  // Extract <mask>.
338  bool IsMasked;
339  if (tryParseMask(MangledName, IsMasked) != ParseRet::OK)
340    return None;
341
342  // Parse the variable size, starting from <vlen>.
343  unsigned VF;
344  bool IsScalable;
345  if (tryParseVLEN(MangledName, VF, IsScalable) != ParseRet::OK)
346    return None;
347
348  // Parse the <parameters>.
349  ParseRet ParamFound;
350  SmallVector<VFParameter, 8> Parameters;
351  do {
352    const unsigned ParameterPos = Parameters.size();
353    VFParamKind PKind;
354    int StepOrPos;
355    ParamFound = tryParseParameter(MangledName, PKind, StepOrPos);
356
357    // Bail off if there is a parsing error in the parsing of the parameter.
358    if (ParamFound == ParseRet::Error)
359      return None;
360
361    if (ParamFound == ParseRet::OK) {
362      Align Alignment;
363      // Look for the alignment token "a <number>".
364      const ParseRet AlignFound = tryParseAlign(MangledName, Alignment);
365      // Bail off if there is a syntax error in the align token.
366      if (AlignFound == ParseRet::Error)
367        return None;
368
369      // Add the parameter.
370      Parameters.push_back({ParameterPos, PKind, StepOrPos, Alignment});
371    }
372  } while (ParamFound == ParseRet::OK);
373
374  // A valid MangledName must have at least one valid entry in the
375  // <parameters>.
376  if (Parameters.empty())
377    return None;
378
379  // Check for the <scalarname> and the optional <redirection>, which
380  // are separated from the prefix with "_"
381  if (!MangledName.consume_front("_"))
382    return None;
383
384  // The rest of the string must be in the format:
385  // <scalarname>[(<redirection>)]
386  const StringRef ScalarName =
387      MangledName.take_while([](char In) { return In != '('; });
388
389  if (ScalarName.empty())
390    return None;
391
392  // Reduce MangledName to [(<redirection>)].
393  MangledName = MangledName.ltrim(ScalarName);
394  // Find the optional custom name redirection.
395  if (MangledName.consume_front("(")) {
396    if (!MangledName.consume_back(")"))
397      return None;
398    // Update the vector variant with the one specified by the user.
399    VectorName = MangledName;
400    // If the vector name is missing, bail out.
401    if (VectorName.empty())
402      return None;
403  }
404
405  // LLVM internal mapping via the TargetLibraryInfo (TLI) must be
406  // redirected to an existing name.
407  if (ISA == VFISAKind::LLVM && VectorName == OriginalName)
408    return None;
409
410  // When <mask> is "M", we need to add a parameter that is used as
411  // global predicate for the function.
412  if (IsMasked) {
413    const unsigned Pos = Parameters.size();
414    Parameters.push_back({Pos, VFParamKind::GlobalPredicate});
415  }
416
417  // Asserts for parameters of type `VFParamKind::GlobalPredicate`, as
418  // prescribed by the Vector Function ABI specifications supported by
419  // this parser:
420  // 1. Uniqueness.
421  // 2. Must be the last in the parameter list.
422  const auto NGlobalPreds = std::count_if(
423      Parameters.begin(), Parameters.end(), [](const VFParameter PK) {
424        return PK.ParamKind == VFParamKind::GlobalPredicate;
425      });
426  assert(NGlobalPreds < 2 && "Cannot have more than one global predicate.");
427  if (NGlobalPreds)
428    assert(Parameters.back().ParamKind == VFParamKind::GlobalPredicate &&
429           "The global predicate must be the last parameter");
430
431  // Adjust the VF for scalable signatures. The EC.Min is not encoded
432  // in the name of the function, but it is encoded in the IR
433  // signature of the function. We need to extract this information
434  // because it is needed by the loop vectorizer, which reasons in
435  // terms of VectorizationFactor or ElementCount. In particular, we
436  // need to make sure that the VF field of the VFShape class is never
437  // set to 0.
438  if (IsScalable) {
439    const Function *F = M.getFunction(VectorName);
440    // The declaration of the function must be present in the module
441    // to be able to retrieve its signature.
442    if (!F)
443      return None;
444    const ElementCount EC = getECFromSignature(F->getFunctionType());
445    VF = EC.getKnownMinValue();
446  }
447
448  // Sanity checks.
449  // 1. We don't accept a zero lanes vectorization factor.
450  // 2. We don't accept the demangling if the vector function is not
451  // present in the module.
452  if (VF == 0)
453    return None;
454  if (!M.getFunction(VectorName))
455    return None;
456
457  const VFShape Shape({VF, IsScalable, Parameters});
458  return VFInfo({Shape, std::string(ScalarName), std::string(VectorName), ISA});
459}
460
461VFParamKind VFABI::getVFParamKindFromString(const StringRef Token) {
462  const VFParamKind ParamKind = StringSwitch<VFParamKind>(Token)
463                                    .Case("v", VFParamKind::Vector)
464                                    .Case("l", VFParamKind::OMP_Linear)
465                                    .Case("R", VFParamKind::OMP_LinearRef)
466                                    .Case("L", VFParamKind::OMP_LinearVal)
467                                    .Case("U", VFParamKind::OMP_LinearUVal)
468                                    .Case("ls", VFParamKind::OMP_LinearPos)
469                                    .Case("Ls", VFParamKind::OMP_LinearValPos)
470                                    .Case("Rs", VFParamKind::OMP_LinearRefPos)
471                                    .Case("Us", VFParamKind::OMP_LinearUValPos)
472                                    .Case("u", VFParamKind::OMP_Uniform)
473                                    .Default(VFParamKind::Unknown);
474
475  if (ParamKind != VFParamKind::Unknown)
476    return ParamKind;
477
478  // This function should never be invoked with an invalid input.
479  llvm_unreachable("This fuction should be invoken only on parameters"
480                   " that have a textual representation in the mangled name"
481                   " of the Vector Function ABI");
482}
483