LLVM  11.0.0git
VFABIDemangling.cpp
Go to the documentation of this file.
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"
12 
13 using namespace llvm;
14 
15 namespace {
16 /// Utilities for the Vector Function ABI name parser.
17 
18 /// Return types for the parser functions.
19 enum 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.
27 ParseRet 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)
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.
52 ParseRet 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 ///
71 ParseRet 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".
104 ParseRet 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.
128 ParseRet 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".
167 ParseRet 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.
192 ParseRet 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.
225 ParseRet 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.
260 ParseRet 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.
280 bool verifyAllVectorsHaveSameWidth(FunctionType *Signature) {
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(
294  llvm::make_range(VecTys.begin() + 1, VecTys.end()),
295  [&EC](VectorType *VTy) { return (EC == VTy->getElementCount()); });
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.
303 ElementCount 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(/*Min=*/1, /*Scalable=*/false);
314 }
315 } // namespace
316 
317 // Format of the ABI name:
318 // _ZGV<isa><mask><vlen><parameters>_<scalarname>[(<redirection>)]
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.Min;
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 
462  const VFParamKind ParamKind = StringSwitch<VFParamKind>(Token)
463  .Case("v", VFParamKind::Vector)
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 }
LLVM_NODISCARD StringRef take_front(size_t N=1) const
Return a StringRef equal to &#39;this&#39; but with only the first N elements remaining.
Definition: StringRef.h:621
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
static bool IsMasked(Instruction *I)
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:67
LLVM_NODISCARD bool startswith(StringRef Prefix) const
Check if this string starts with the given Prefix.
Definition: StringRef.h:289
auto count_if(R &&Range, UnaryPredicate P)
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
Definition: STLExtras.h:1574
bool consume_front(StringRef Prefix)
Returns true if this StringRef has the given prefix and removes that prefix.
Definition: StringRef.h:683
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1491
Contains the information about the kind of vectorization available.
Definition: VectorUtils.h:82
F(f)
LLVM_NODISCARD StringRef ltrim(char Char) const
Return string with consecutive Char characters starting from the the left removed.
Definition: StringRef.h:823
static constexpr char const * _LLVM_
LLVM Internal VFABI ISA token for vector functions.
Definition: VectorUtils.h:139
Holds the VFShape for a specific scalar to vector function mapping.
Definition: VectorUtils.h:124
unsigned Min
Definition: TypeSize.h:30
StringSwitch & Case(StringLiteral S, T Value)
Definition: StringSwitch.h:67
LLVM_NODISCARD StringRef drop_front(size_t N=1) const
Return a StringRef equal to &#39;this&#39; but with the first N elements dropped.
Definition: StringRef.h:654
LLVM_NODISCARD R Default(T Value)
Definition: StringSwitch.h:181
LLVM_NODISCARD bool empty() const
empty - Check if the string is empty.
Definition: StringRef.h:156
std::enable_if_t< std::numeric_limits< T >::is_signed, bool > consumeInteger(unsigned Radix, T &Result)
Parse the current string as an integer of the specified radix.
Definition: StringRef.h:545
LLVM_NODISCARD StringRef take_while(function_ref< bool(char)> F) const
Return the longest prefix of &#39;this&#39; such that every character in the prefix satisfies the given predi...
Definition: StringRef.h:640
Class to represent function types.
Definition: DerivedTypes.h:108
VFISAKind
Describes the type of Instruction Set Architecture.
Definition: VectorUtils.h:44
A switch()-like statement whose cases are string literals.
Definition: StringSwitch.h:42
ElementCount getElementCount() const
Return an ElementCount instance to represent the (possibly scalable) number of elements in the vector...
Definition: DerivedTypes.h:657
Encapsulates information needed to describe a parameter.
Definition: VectorUtils.h:62
ArrayRef< Type * > params() const
Definition: DerivedTypes.h:135
constexpr bool isPowerOf2_64(uint64_t Value)
Return true if the argument is a power of two > 0 (64 bit edition.)
Definition: MathExtras.h:497
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:883
Type * getReturnType() const
Definition: DerivedTypes.h:129
Function * getFunction(StringRef Name) const
Look up the specified function in the module symbol table.
Definition: Module.cpp:174
FunctionType * getFunctionType() const
Returns the FunctionType for me.
Definition: Function.h:165
Base class of all SIMD vector types.
Definition: DerivedTypes.h:390
VFParamKind
Describes the type of Parameters.
Definition: VectorUtils.h:25
ParseRet
Utilities for the Vector Function ABI name parser.
bool consume_back(StringRef Suffix)
Returns true if this StringRef has the given suffix and removes that suffix.
Definition: StringRef.h:693
VFParamKind getVFParamKindFromString(const StringRef Token)
Retrieve the VFParamKind from a string token.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Lightweight error class with error context and mandatory checking.
Definition: Error.h:157
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:57
Optional< VFInfo > tryDemangleForVFABI(StringRef MangledName, const Module &M)
Function to construct a VFInfo out of a mangled names in the following format: