llvm/lib/Analysis/VFABIDemangling.cpp

   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
  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)
  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.
  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) {
 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.
 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::getFixed(/*Min=*/1);
 314 }
 315 } // namespace
 316
 317 // Format of the ABI name:
 318 // _ZGV<isa><mask><vlen><parameters>_<scalarname>[(<redirection>)]
 319 Optional<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({ElementCount::get(VF, IsScalable), Parameters});
 458   return VFInfo({Shape, std::string(ScalarName), std::string(VectorName), ISA});
 459 }
 460
 461 VFParamKind 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 }