SVFS implementation according to RFC: Interface user provided vector functions with the vectorizer.

[aranisumedh]

Summary

[http://lists.llvm.org/pipermail/llvm-dev/2019-June/133484.html]

[jdoerfert]

Some high level coding comments.

Documentation needed in various places.

Why std::vector and not llvm::SmallVector for example?

llvm/include/llvm/Analysis/SearchVectorFunctionSystem.h

35

I'd like some "class comment" and also comments on the members. It is not clear to everyone (incl. me) what distinguishes for example LinearValPos and LinearUValPos and why we need that.

48

automatically private.

54

I don't think this is a good idea.

62

) : ParamPos(ParamPos), LinearStepOrPos(0)

Why take a string just to convert it? Shouldn't we expose the conversion as a static member and expect a enum here. That way users can use the conversion if they need to but if they know the enums they want there is no need to go through the string first.

112

One could generate them with a macro if one wanted to:

#declare LOOKUP_FN(NAME) \
   bool is ##NAME () { \
            return ParamKind == ParameterKind::OMP_ ## NAME; \
   }

LOOKUP_FN(Uniform)
...
#undef LOOKUP_FN(NAME)

137

The default case is missing. llvm_unreachable I assume.

150

Make it a struct or do not expose all members.

153

) : M(M) {}

157

No need for the typedef. Again, please add comments to the class and members.

163

(Honest question) Can't we use something like = default or is that a C++ feature we are not allowed to use yet?

llvm/lib/Analysis/SearchVectorFunctionSystem.cpp

20

MangledName.startswith("_ZGV") ?

36

You could add an "ISA_UNKNOWN" case as a default here and assert on that one. Would probably make it slightly easier to maintain. But this is fine as well.

[aranisumedh]

Added code to expose the functionality as an Analysis Pass. Integrated changes as suggested in prior code review.

[aranisumedh]

llvm/include/llvm/Analysis/SearchVectorFunctionSystem.h

54

I forgot to remove the comment. This is incorrect comment.

This constructor is not used for testing.

62

I preferred to use a string as demangling does String parsing. Hence, I thought it would be easier to call a class constructor with the StringRef as it's argument.

137

I don't think StringSwitch Default Case handles llvm_unreachable

163

It is a C++ 20 feature. Hence, I think I cannot use it for now. https://en.cppreference.com/w/cpp/keyword/default

[jdoerfert]

Second round, we make progress :)

Style:
We usually prefer C++-style comments // if possible. They are placed in front of variables (not for enums). And you should use doxygen style comments whenever it'll get picked up, so in front of any declaration (class, member, ...). (see also the style stuff here: https://llvm.org/docs/CodingStandards.html)

Test:
It looks like the tests are all positive, e.g., good input results in good return. Could you add some to make sure invalid input is detected _and_ reported as such?

llvm/include/llvm/Analysis/SearchVectorFunctionSystem.h

92

Why not LOOKUP_PARAMETER(Vector)?

I don't think you want ; at the end.

Cleanup:
#undef LOOKUP_PARAMETER

111

What is the default here? What happens for bad inputs?

121

Doxygen class comment.

122

I found a single use of this exposed member and that use can be replaced by something like:
Call->getModule()
If there is no reason to have this member, get rid of it and all the init stuff.

162

These doxygen documentations do not match the methods.

197

These methods lack doxygen documentation.

217

It seems the new pass manager interface is missing.

llvm/lib/Analysis/SearchVectorFunctionSystem.cpp

278

for (Instruction &I : instructions(F))

[aranisumedh]

llvm/include/llvm/Analysis/SearchVectorFunctionSystem.h

111

Should I add an assert before the StringSwitch?

Or add OMP_Unknown to handle such cases?

217

Could you share pointers to how to add a new pass using the new pass manager interface?

[jdoerfert]

llvm/include/llvm/Analysis/SearchVectorFunctionSystem.h

111

I would prefere the OMP_Unknown case but I am probably fine with any error checking solution. I mainly want to avoid silent errors.

217

Take a look at other patches that do it, e.g., D64185

[aranisumedh]

llvm/include/llvm/Analysis/SearchVectorFunctionSystem.h

92

Vector is a generic case and not just restricted to OMP. Hence, for the macro to work, there is a prefix OMP_ attached to the rest of the scenarios and not Vector.

122

I did make this change but however, as I'm building the CallInst programmatically in the test case, this leads to a segmentation fault.

However, in the patch that is to follow(hooking to the loopVectorizer), Call->getModule() works perfectly.

Do you have any suggestions as so as to get the getVectorizedFunction test working as specified in SearchVectorFunctionTest.cpp

Also, do I use AssertionSuccess() and AssertionFailure() for testing bad inputs?

[aranisumedh]

Thank you for valuable inputs. Sorry for the delay in getting back to you.

I have mostly used asserts() to capture bad inputs. I have not yet added tests to test for bad input. Google test had documentation using AssertionSuccess() and AssertionFailure(). [https://github.com/google/googletest/blob/master/googletest/docs/advanced.md]. Do I use that or you've something else in mind?

[jdoerfert]

I think someone else should start looking at this.

llvm/include/llvm/Analysis/SearchVectorFunctionSystem.h

122

You lost me here.

137

I guess you can do this: add a default case, if that value is chosen invoke llvm_unreachable.

llvm/unittests/Analysis/SearchVectorFunctionSystemTest.cpp

274

I doubt we want to output anything here.

[aranisumedh]

llvm/include/llvm/Analysis/SearchVectorFunctionSystem.h

122

I have added a new comment that points to the issue better.

137

Will update.

llvm/unittests/Analysis/SearchVectorFunctionSystemTest.cpp

228

I create the CallInst programmatically here. The stack trace tells me the bug is in getVectorizedFunction in SearchVectorFunctionSystem.cpp. When it calls Call->getModule(), a segmentation fault occurs. As I understand, the CallInst is probably not getting inserted in the module.

I was wondering how do I modify the test case so as to suit this functionality?

274

Yes. Forgot to remove the comments. It was for debugging purpose.

[aranisumedh]

Minor changes as suggested in the recent review.

[jdoerfert]

llvm/unittests/Analysis/SearchVectorFunctionSystemTest.cpp

228

CallInst should have a constructor/create method that takes a basic block or instruction. Alternatively, call Call->insertXXX later.

[a.elovikov]

Thanks for working on this! I'm really interested in using this functionality so here are some comments on the main interface header.

llvm/include/llvm/Analysis/SearchVectorFunctionSystem.h

46

How is this different from Vector?

57

That's great, I see how it can be used for non-OMP usage.

62

Is it original (scalar) call position or vector call position? Please make it clear in the comment.

I'm interested in this because my use case might have Mask argument in the vector function variant in the middle of other arguments. Is it possible to handle that with this patch?

67

My preference for this is to make the ctor private and provide public static functions to create different set of required arguments for different kinds. E.g. no LinearStepOrPos of varying/vector parameter. SOmething like this:

private:
  ParamType()

public
  static ParamType vector() { return ParamType{}; }
  static ParamType linear(int LinearStep) { ... }
  static ParamType linearWithNonConstStride(unsigned StepArgPosition) { ... }

Feel free to ignore though.

85

I'm not sure if more broad "isLinear" interface for all the Linear* would be useful. Kind of sad if we won't be able to have it because of this accessors.

95

I would split it into two methods with proper asserts for the correct kind of this param.

97

Do we really need the setter? Why once created param description could change?

121

This is marked as done but I don't see the doxygen comment...

132

Isn't it part of ISA somehow? Why do we need a separate flag that isn't applicable for all the ISAs? Or do I miss something here?

Also, I'm not familiar with is (I assume it's related to SVE) - how does it deal with VF. Do we still need VF here if IsScalable is true?

135

Is it possible to add the information about the return value? Like varying vector/uniform scalar/uniform vector.

172

I'd rather have an interface not referencing the CallInst (e.g. mangled name instead). Why doesn't it have a "bool Masked" parameter?

179

Same as above, I think. E.g. interface without CallInst, bool Mask.

196

I'm not sure why is in VFABI namespace. Mask/NoMask isn't ABI-specific. Same for functions below.

[aranisumedh]

llvm/include/llvm/Analysis/SearchVectorFunctionSystem.h

46

You mean Unknown? It's for error handling.

62

It is the original call position.

85

It just checks if the parameter type is OMP_Linear. It doesn't check for Linear* case

95

According to the VFABI, it'll be either step or pos associated. If we split this into two, we would need more variables.

As per the ABI, if it's ls, Rs, Ls, Us, u, only then would we pos associated with the parameter else it's a step.

97

No. I don't think the parameters can change. I can change the implementation so as to avoid using the setter function.

132

If the VF is set to 'x' and and the ISA is SVE, it is then the IsScalable flag is set to true.

135

Could you elaborate, so as to make sure I get you right?

172

We are trying to search for all the vector function mappings available for a given scalar function by querying the SVFS table. Hence, I think that it is better to pass the CallInst, where we check for records in our table with matching scalar names. It also follows the description in the RFC.

179

You can specify the bool Mask within the VectorFunctionShape that is the second parameter. In the separate patch that is to follow, I'll demonstrate how the loop vectorizer will call and query SVFS to vectorize a CallInst.

196

The parsing of the mangled names is as described in the Vector Function ABI. All these functions take in mangled name and parse the information. Hence, I decided to keep these function within the VFABI namespace.

[sdesmalen]

Thanks @aranisumedh for working on this!

The patch is quite big and I think it would be easier to review if it is split up. My main concern is that this patch conflates the SVFS pass/mechanism and the (demangling for the) AArch64 Vector ABI, which I think need to be split up into separate patches.

If you add a print method to the SVFS pass, you can print the available vector mappings as described in LLVM IR function attributes by running opt -analyze -svfs, which would make it easier to test using FileCheck. If you add that first, you could use the -analyze functionality to test the demangling of the AArch64 Vector ABI with .ll tests.

Not sure if this was already discussed anywhere else, but is there a reason this doesn't live in TargetLibraryInfo? There is already a getVectorizedFunction in that class, so it makes sense to make that method more powerful by having it take a VectorFunctionShape as well as unsigned VF.

llvm/include/llvm/Analysis/SearchVectorFunctionSystem.h

46

It is more explicit to rename it to Invalid in that case.

82

Can you just expand these functions instead of using a pragma? Given the simplicity of the definition there is little benefit to using a macro here, and having them expanded would make it easier to search for in the codebase.

101

is this not specific to the AArch64 Vector ABI?

129

VectorFunctionShape could benefit from having a constructor, if only to ensure that a VectorFunctionShape is valid and can be used as operand in operator==.

154

Do we want to expose RecordTable?

180

This method asks for a vectorized function that *exactly*matches the specifications in VectorFunctionShape info. You may want to think about a mechanism in VectorFunctionShape where you can distinguish "required" and "optional" features. For example, if this function is asked for to return an unpredicated vector function, but it only has a predicated vector function, we'd still prefer to get the predicated vector function and construct an "all true" predicate, rather than having to fall back on scalar instructions.

llvm/lib/Analysis/SearchVectorFunctionSystem.cpp

267

I think you should either support 1 mapping, or support multiple mappings with a clear mechanism to prioritise which mapping takes priority. This function seems to prioritise based on whether or not a function-name is mangled which makes little sense to me.

[aranisumedh]

As suggested earlier by Sander, I'll be splitting this patch into two patches for easier review.

[aranisumedh]

llvm/include/llvm/Analysis/SearchVectorFunctionSystem.h

97

The current implementation allows me to handle corner cases better. This setter function is used to set the LinearStepOrPos for the first time.

101

No. IIRC, this is in agreement with other vendors too.

121

That is because it was a part of the last diff. Hence, the lines get moved. The getter and setters are pretty straightforward. Do I still add a doxygen comment for the same?

154

Making it private.

[aranisumedh]

llvm/lib/Analysis/SearchVectorFunctionSystem.cpp

267

The priority is given on the basis that there exists a redirection to a custom user-defined function. This scenario arises from the different uses of declare simd and declare variant.

And the implementation follows that we save the VectorName as the mangledName if there is no redirection. Hence we prioritize declare variant over declare simd

llvm/include/llvm/Analysis/SearchVectorFunctionSystem.h

+//===- SearchVectorFunctionSystem.h - Search Vector Function System -------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+/// \file
+/// This is the interface used for user provided vector functions with the
+/// vectorizer.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/StringRef.h"
+#include "llvm/IR/DerivedTypes.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/ADT/StringSwitch.h"
+#include "llvm/IR/Module.h"
+
+namespace llvm {
+
+enum class ParameterKind 
+{
+    Vector,
+    OMP_Linear,
+    OMP_LinearRef,
+    OMP_LinearVal,
+    OMP_LinearUVal,
+    OMP_LinearPos,
+    OMP_LinearValPos,
+    OMP_LinearRefPos,
+    OMP_LinearUValPos,
+    OMP_Uniform
+};
+
+enum class ISAKind
+{
+  ISA_AdvancedSIMD,
+  ISA_SVE,
+  ISA_SSE,
+  ISA_AVX,
+  ISA_AVX2,
+  ISA_AVX512
+};
+  
+class ParamType {
+    private:
+        unsigned ParamPos;
+        ParameterKind ParamKind;
+        int LinearStepOrPos;
+    
+    public:
+        // Constructor - Used for testing
+        ParamType(unsigned ParamPos, StringRef ParamKind, int LinearStepOrPos) {
+            this->ParamPos = ParamPos;
+            setParameterKind(ParamKind);
+            this->LinearStepOrPos = LinearStepOrPos;
+        }
+
+        // Constructor for ParameterKind with no step. Eg- ParameterKind::Vector
+        ParamType(unsigned ParamPos, StringRef ParamKind) {
+            this->ParamPos = ParamPos;
+            setParameterKind(ParamKind);
+            LinearStepOrPos = 0;
+        }
+
+        bool operator==(const ParamType &other) const {
+                return (ParamPos == other.ParamPos
+                && ParamKind == other.ParamKind
+                && LinearStepOrPos == other.LinearStepOrPos);
+        }
+
+        bool isVector() {
+            return ParamKind == ParameterKind::Vector;            
+        }
+
+        bool isLinear() {
+            return ParamKind == ParameterKind::OMP_Linear;            
+        }
+
+        bool isLinearVal() {
+            return ParamKind == ParameterKind::OMP_LinearVal;
+        }
+
+        bool isLinearRef() {
+            return ParamKind == ParameterKind::OMP_LinearRef;
+        }
+
+        bool isLinearUVal() {
+            return ParamKind == ParameterKind::OMP_LinearUVal;
+        }
+
+        bool isLinearPos() {
+            return ParamKind == ParameterKind::OMP_LinearPos;
+        }
+
+        bool isLinearValPos() {
+            return ParamKind == ParameterKind::OMP_LinearValPos;
+        }
+
+        bool isLinearRefPos() {
+            return ParamKind == ParameterKind::OMP_LinearRefPos;
+        }
+
+        bool isLinearUValPos() {
+            return ParamKind == ParameterKind::OMP_LinearUValPos;
+        }
+
+        bool isUniform() {
+            return ParamKind == ParameterKind::OMP_Uniform;
+        }
+
+        int getLinearStepOrPos(){
+            return LinearStepOrPos;
+        }
+
+        void setLinearStepOrPos(int s) {
+            LinearStepOrPos = s;
+        }
+
+        ParameterKind getParameterKind() {
+            return ParamKind;
+        }
+
+        void setParameterKind(StringRef kind) {
+            ParamKind = StringSwitch<ParameterKind>(kind)
+                .Case("v",  ParameterKind::Vector)
+                .Case("l",  ParameterKind::OMP_Linear)
+                .Case("R",  ParameterKind::OMP_LinearRef)
+                .Case("L",  ParameterKind::OMP_LinearVal)
+                .Case("U",  ParameterKind::OMP_LinearUVal)
+                .Case("ls", ParameterKind::OMP_LinearPos)
+                .Case("Ls", ParameterKind::OMP_LinearValPos)
+                .Case("Rs", ParameterKind::OMP_LinearRefPos)
+                .Case("Us", ParameterKind::OMP_LinearUValPos)
+                .Case("u",  ParameterKind::OMP_Uniform);
+        }
+
+        unsigned getParamPos() {
+            return ParamPos;
+        }
+
+        void setParamPos(unsigned Position) {
+            ParamPos = Position;
+        }
+};
+
+class SVFS{
+    public:
+        Module *M;
+
+        SVFS(Module *M) {
+            this->M = M;
+        }
+
+        typedef struct VectorFunctionShape {
+            unsigned VF; // Vectorization factor 
+            bool IsMasked;
+            bool IsScalable;
+            ISAKind ISA;
+            std::vector<ParamType> Parameters;
+            bool operator==(const VectorFunctionShape &other) const {
+                return (VF == other.VF
+                && IsMasked == other.IsMasked
+                && IsScalable == other.IsScalable
+                && ISA == other.ISA
+                && Parameters == other.Parameters);
+            }
+        } VectorFunctionShape;
+
+        typedef struct VectorRecord {
+            VectorFunctionShape VFS;
+            StringRef ScalarName;
+            StringRef VectorName;
+        } VectorRecord;
+
+        std::vector<VectorRecord> RecordTable;
+
+        /// Creates a table for quick lookup of available vector functions.
+        ///
+        /// \param MangledName - Comma separated strings of the available vector
+        /// functions in their mangled format
+        /// \param ScalarFTy - Scalar function signature required to generate 
+        /// the vector function signature
+        void createTableLookupRecord(CallInst *Call);
+
+        /// Does name demangling
+        /// \param MangledName - Mangled name for demangling
+        /// \param Result filled with a populated vector record after name 
+        /// demangling
+        void demangleName(StringRef MangledName, SVFS::VectorRecord &Record);
+
+        std::vector<VectorFunctionShape> isFunctionVectorizable(
+                                                        CallInst *Call) const;
+
+        Function* getVectorizedFunction(llvm::CallInst *Call,
+                                            VectorFunctionShape Info) const;
+
+};
+
+namespace VFABI {
+    bool getABISignature(StringRef MangledName); 
+    ISAKind getISA(StringRef MangledName);
+    bool getIsMasked(StringRef MangledName);
+    unsigned getVF(StringRef MangledName);
+    void getParameters(StringRef MangledName, SVFS::VectorRecord &NewRecord);
+    StringRef getScalarName(StringRef MangledName);
+    StringRef getVectorName(StringRef MangledName);
+    void parseParamList(StringRef ParameterList,
+                            std::vector<ParamType> &Parameters);
+    bool getIsScalable(StringRef MangledName);
+}
+}
 No newline at end of file

llvm/lib/Analysis/CMakeLists.txt

add_llvm_library(LLVMAnalysis
   PtrUseVisitor.cpp
   RegionInfo.cpp
   RegionPass.cpp
   RegionPrinter.cpp
   ScalarEvolution.cpp
   ScalarEvolutionAliasAnalysis.cpp
   ScalarEvolutionExpander.cpp
   ScalarEvolutionNormalization.cpp
+  SearchVectorFunctionSystem.cpp
   StackSafetyAnalysis.cpp
   SyncDependenceAnalysis.cpp
   SyntheticCountsUtils.cpp
   TargetLibraryInfo.cpp
   TargetTransformInfo.cpp
   Trace.cpp
   TypeBasedAliasAnalysis.cpp
   TypeMetadataUtils.cpp

llvm/lib/Analysis/SearchVectorFunctionSystem.cpp

+//===- SearchVectorFunctionSystem.cpp - Search Vector Function System -----===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/SearchVectorFunctionSystem.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/IR/Function.h"
+#include "llvm/Support/Compiler.h"
+
+namespace llvm{
+
+bool VFABI::getABISignature(StringRef MangledName) {
+    // Capture the ABI Signature value
+    StringRef ABISignature;
+    ABISignature = MangledName.substr(0,4);
+    return ABISignature.equals("_ZGV");
+}
+
+ISAKind VFABI::getISA(StringRef MangledName) {
+    // Capture the ISA value
+    StringRef ISAValue = MangledName.substr(4, 1);
+    assert(ISAValue.equals("n") || ISAValue.equals("s")
+            || ISAValue.equals("b") || ISAValue.equals("c")
+            || ISAValue.equals("d") || ISAValue.equals("e")
+            && "Unknown ISA Specified");
+    ISAKind ISA = StringSwitch<ISAKind>(ISAValue)
+      .Case("n", ISAKind::ISA_AdvancedSIMD)
+      .Case("s", ISAKind::ISA_SVE)
+      .Case("b", ISAKind::ISA_SSE)
+      .Case("c", ISAKind::ISA_AVX)
+      .Case("d", ISAKind::ISA_AVX2)
+      .Case("e", ISAKind::ISA_AVX512);
+  return ISA;
+}
+
+bool VFABI::getIsMasked(StringRef MangledName) {
+    // Capture the MASK value
+    StringRef Mask;
+    Mask = MangledName.substr(5,1);
+    if (VFABI::getISA(MangledName) == ISAKind::ISA_SVE)
+        return true;
+    assert(Mask.equals("N") || Mask.equals("M") && "Invalid masking option");
+    return Mask.equals("N") ? false : true;
+
+}
+
+unsigned VFABI::getVF(StringRef MangledName) {
+    // Capture the VF
+    // VectorLength can be any positive integer
+    unsigned VF;
+    std::size_t Pos;
+
+    Pos = MangledName.find_first_of("vlRLUu", 6);
+    if (!MangledName.substr(6, Pos - 6).compare("x")){
+        assert(VFABI::getISA(MangledName) == ISAKind::ISA_SVE
+                && "Incompatible ISA");
+        return 0;
+    }
+    MangledName.substr(6, Pos - 6).consumeInteger(10, VF);
+    return VF;
+}
+
+bool VFABI::getIsScalable(StringRef MangledName) {
+    // Capture if it is Scalable or Not
+    bool IsSVE = VFABI::getISA(MangledName) == ISAKind::ISA_SVE;
+    bool IsVFZero = VFABI::getVF(MangledName) == 0;
+    return IsSVE && IsVFZero;
+}
+
+void VFABI::getParameters (StringRef MangledName,
+                            SVFS::VectorRecord &NewRecord) {
+    // Capture the parameters
+    StringRef ParamList;
+    std::size_t Pos;
+    std::size_t NewPos;
+
+    Pos = MangledName.find_first_of("vlRLUu", 6);
+    NewPos = MangledName.find("_", Pos);
+    ParamList = MangledName.substr(Pos, NewPos - Pos);
+    VFABI::parseParamList(ParamList, NewRecord.VFS.Parameters);
+}
+
+StringRef VFABI::getScalarName(StringRef MangledName) {
+    // Get Scalar function name
+    StringRef ScalarFunctionName;
+    std::size_t Pos;
+    std::size_t NewPos;
+
+    Pos = MangledName.find("_", 6) + 1;
+    NewPos = MangledName.find("(", Pos);
+    // Handles Case: custom vector function name not provided
+    if (NewPos == StringRef::npos)
+        NewPos = MangledName.str().length();
+    ScalarFunctionName = MangledName.substr(Pos, NewPos - Pos);
+
+    return ScalarFunctionName;
+}
+
+StringRef VFABI::getVectorName(StringRef MangledName) {
+    // Get vector Function Name
+    StringRef VectorFunctionName;
+    std::size_t Pos;
+    std::size_t NewPos;
+
+    Pos = MangledName.find("(", 6);
+    if (Pos == StringRef::npos)
+        return MangledName;
+    Pos ++;
+    NewPos = MangledName.find(")", Pos);
+    VectorFunctionName = MangledName.substr(Pos, NewPos - Pos);
+
+    return VectorFunctionName;
+}
+
+void VFABI::parseParamList(StringRef ParamList,
+                            std::vector<ParamType> &Params){
+    std::size_t Pos; // Pos to iterate ParamList
+    std::size_t NewPos;
+
+    unsigned ParamPos = 0; // param Pos
+    int LinearStepOrPos;
+
+    Pos = 0;
+    StringRef ParamKind;
+
+    // Parse the param list and store it to newRecord.VFS.Parameters
+    // NewPos - Pos = length of param string
+    // length of param string = ParamList.str().length()
+    // TODO: Handle negative numbers for LinearStepOrPos.
+    // Eg=linear(val(ParamPos):-3)=`Ln3`
+    while ((NewPos = ParamList.find_first_of("vlRLUu", Pos+1)) <
+                                                (ParamList.str().length())) {
+        ParamKind = ParamList.substr(Pos, 1);
+        if (ParamList.substr(Pos+1, 1).equals("s")) {
+            ParamKind = ParamList.substr(Pos, 2);
+            Pos++;
+        }
+        // +1 to read the LinearStepOrPos value after the param kind
+        Pos++;
+        if (NewPos > Pos) {
+            ParamList.substr(Pos, NewPos - (Pos)).consumeInteger(10,
+                                                            LinearStepOrPos);
+            Params.push_back(ParamType(ParamPos, ParamKind, LinearStepOrPos));
+        }
+        else
+        {
+            ParamType Parameter(ParamPos, ParamKind);
+            assert(Parameter.isLinear() || Parameter.isLinearRef()
+                    || Parameter.isLinearVal() || Parameter.isVector()
+                    || Parameter.isUniform()|| Parameter.isLinearUVal()
+                    && "Step Not Specified for given ParameterKind");
+            // Default LinearStepOrPos value if not specified in ABI signature
+            if (Parameter.isLinear() || Parameter.isLinearRef()
+                || Parameter.isLinearVal() || Parameter.isLinearUVal()) {
+                Parameter.setLinearStepOrPos(1);
+            }
+            Params.push_back(Parameter);
+        }
+        ParamPos++;
+        Pos = NewPos;
+    }
+
+    // Last param value || only param
+    // NewPos is the end of StringRef ParamList
+    ParamKind = ParamList.substr(Pos, 1);
+
+    // +1 to read the LinearStepOrPos value after the param kind
+    if ((ParamList.str().length()) > Pos + 1) {
+        StringRef StrLinearStepOrPos = ParamList.substr(Pos+1,
+                                        (ParamList.str().length()) - (Pos + 1));
+        StrLinearStepOrPos.consumeInteger(10, LinearStepOrPos);
+        Params.push_back(ParamType(ParamPos, ParamKind, LinearStepOrPos));
+    }
+    else {
+        ParamType Parameter(ParamPos, ParamKind);
+        // Default LinearStepOrPos value if not specified in ABI signature
+        if (Parameter.isLinear() || Parameter.isLinearRef()
+            || Parameter.isLinearVal()) {
+            Parameter.setLinearStepOrPos(1);
+        }
+        Params.push_back(Parameter);
+    }
+}
+
+void SVFS::demangleName(StringRef MangledName, SVFS::VectorRecord &NewRecord) {
+    // String Parsing - Populate newRecord
+    // Vector Function ABI for AArch64 (Sec 3.5)
+
+    if (!VFABI::getABISignature(MangledName))
+        return;
+    NewRecord.VFS.ISA = VFABI::getISA(MangledName);
+    NewRecord.VFS.IsMasked = VFABI::getIsMasked(MangledName);
+    NewRecord.VFS.VF = VFABI::getVF(MangledName);
+    NewRecord.VFS.IsScalable = VFABI::getIsScalable(MangledName);
+    VFABI::getParameters(MangledName, NewRecord);
+    NewRecord.ScalarName = VFABI::getScalarName(MangledName);
+    NewRecord.VectorName = VFABI::getVectorName(MangledName);
+
+}
+
+void SVFS::createTableLookupRecord(CallInst *Call) {
+    Function *ScalarFunc = Call->getCalledFunction();
+    StringRef MangledName = ScalarFunc->getFnAttribute(
+                            "vector-function-abi-variant").getValueAsString();
+
+    SmallVector<StringRef, 4> VectorStrings;
+
+    MangledName.split(VectorStrings, ",");
+
+    for (auto VectorString : VectorStrings) {
+        // Populate a new entry to be recorded
+        SVFS::VectorRecord NewRecord;
+        SVFS::demangleName(VectorString.trim(), NewRecord);
+        // Populate the table
+        SVFS::RecordTable.push_back(NewRecord);
+    }
+}
+
+std::vector<SVFS::VectorFunctionShape> SVFS::isFunctionVectorizable(
+                                                        CallInst *Call) const {
+    std::vector<SVFS::VectorFunctionShape> AvailableVFS;
+    // Iterate through all records.
+    for (auto Record: SVFS::RecordTable) {
+        if (Record.ScalarName == Call->getCalledFunction()->getName()) {
+            AvailableVFS.push_back(Record.VFS);
+        }
+    }
+    return AvailableVFS;
+}
+
+Function* SVFS::getVectorizedFunction(CallInst *Call,
+                                        SVFS::VectorFunctionShape Info) const {
+    std::vector<VectorRecord> Records;
+    // Iterate through all records
+    for (auto Record : SVFS::RecordTable) {
+        if (Record.ScalarName == Call->getCalledFunction()->getName()
+                && Record.VFS == Info) {
+            Records.push_back(Record);
+        }
+    }
+    StringRef FuncName = Records[0].VectorName;
+    // Atmost 2 functions that have the same VectorFunctionShape.
+    assert(Records.size() <= 2 && "Invalid Table Entries");
+    if (Records.size() == 2) {
+        bool IsMangled = VFABI::getABISignature(Records[0].VectorName);
+        // Checks to ensure only one entry has a custom name
+        if (IsMangled)
+            assert(VFABI::getABISignature(Records[1].VectorName) == false
+            && "Invalid Table Entries");
+        else
+            assert(VFABI::getABISignature(Records[1].VectorName) == true
+            && "Invalid Table Entries");
+        FuncName = IsMangled?Records[1].VectorName:Records[0].VectorName;
+    }
+
+    return SVFS::M->getFunction(FuncName);
+}
+
+}
 No newline at end of file

llvm/unittests/Analysis/CMakeLists.txt

add_llvm_unittest(AnalysisTests
   LoopInfoTest.cpp
   MemoryBuiltinsTest.cpp
   MemorySSATest.cpp
   OrderedBasicBlockTest.cpp
   OrderedInstructionsTest.cpp
   PhiValuesTest.cpp
   ProfileSummaryInfoTest.cpp
   ScalarEvolutionTest.cpp
+  SearchVectorFunctionSystemTest.cpp
   SparsePropagation.cpp
   TargetLibraryInfoTest.cpp
   TBAATest.cpp
   UnrollAnalyzerTest.cpp
   ValueLatticeTest.cpp
   ValueTrackingTest.cpp
   )

llvm/unittests/Analysis/SearchVectorFunctionSystemTest.cpp

+//===------- SearchVectorFunctionSystemTest.cpp - SVFS Unittests  ---------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/SearchVectorFunctionSystem.h"
+#include "llvm/AsmParser/Parser.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/Support/SourceMgr.h"
+#include "llvm/Support/raw_ostream.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+class SearchVectorFunctionSystemTest : public testing::Test {
+protected:
+    SearchVectorFunctionSystemTest() : M(new Module("MyModule", Ctx)) {
+        FArgTypes.push_back(Type::getInt32Ty(Ctx));
+        FArgTypes.push_back(Type::getInt32Ty(Ctx));
+        FunctionType *FTy =
+            FunctionType::get(Type::getInt32Ty(Ctx), FArgTypes, false);
+        F = Function::Create(FTy, Function::ExternalLinkage, "sin", M.get());
+    }
+
+    LLVMContext Ctx;
+    std::unique_ptr<Module> M;
+    SmallVector<Type *, 2> FArgTypes;
+    Function *F;
+};
+
+TEST_F(SearchVectorFunctionSystemTest, TableCreation) {
+    SVFS S(M.get());
+
+    // Tests the complete functionality of table creation
+    Value *Args[] = {ConstantInt::get(Type::getInt32Ty(Ctx), 20),
+                    ConstantInt::get(Type::getInt32Ty(Ctx), 20)};
+    std::unique_ptr<CallInst> Caller(CallInst::Create(F, Args));
+    CallInst *Call = Caller.get();
+    F->addFnAttr("vector-function-abi-variant", "_ZGVnN2vv_sin(another_vector),"
+                                    "_ZGVnN8l8v_sin(sinVector),_ZGVnN4vl_sin");
+
+    S.createTableLookupRecord(Call);
+    
+    // Checks for "_ZGVnN2vv_sin(another_vector)"
+    EXPECT_EQ(S.RecordTable[0].VFS.VF, (unsigned) 2);
+    EXPECT_FALSE(S.RecordTable[0].VFS.IsMasked);
+    EXPECT_EQ(S.RecordTable[0].VFS.ISA, ISAKind::ISA_AdvancedSIMD);
+
+    EXPECT_TRUE(S.RecordTable[0].VFS.Parameters[0].isVector());
+    EXPECT_EQ(S.RecordTable[0].VFS.Parameters[0].getParamPos(), (unsigned) 0);
+
+    EXPECT_TRUE(S.RecordTable[0].VFS.Parameters[1].isVector());
+    EXPECT_EQ(S.RecordTable[0].VFS.Parameters[1].getParamPos(), (unsigned) 1);
+
+    EXPECT_EQ(S.RecordTable[0].ScalarName, "sin");
+    EXPECT_EQ(S.RecordTable[0].VectorName, "another_vector");
+
+    // Checks for "_ZGVnN8l8v_sin(sinVector)"
+    EXPECT_EQ(S.RecordTable[1].VFS.VF, (unsigned) 8);
+    EXPECT_FALSE(S.RecordTable[1].VFS.IsMasked);
+    EXPECT_EQ(S.RecordTable[1].VFS.ISA, ISAKind::ISA_AdvancedSIMD);
+
+    EXPECT_TRUE(S.RecordTable[1].VFS.Parameters[0].isLinear());
+    EXPECT_EQ(S.RecordTable[1].VFS.Parameters[0].getParamPos(), (unsigned) 0);
+    EXPECT_EQ(S.RecordTable[1].VFS.Parameters[0].getLinearStepOrPos(), 8);
+
+    EXPECT_TRUE(S.RecordTable[1].VFS.Parameters[1].isVector());
+    EXPECT_EQ(S.RecordTable[1].VFS.Parameters[1].getParamPos(), (unsigned) 1);
+
+    EXPECT_EQ(S.RecordTable[1].ScalarName, "sin");
+    EXPECT_EQ(S.RecordTable[1].VectorName, "sinVector");
+
+    // Checks for "_ZGVnN4vl_sin"
+    EXPECT_EQ(S.RecordTable[2].VFS.VF, (unsigned) 4);
+    EXPECT_FALSE(S.RecordTable[2].VFS.IsMasked);
+    EXPECT_EQ(S.RecordTable[2].VFS.ISA, ISAKind::ISA_AdvancedSIMD);
+
+    EXPECT_TRUE(S.RecordTable[2].VFS.Parameters[0].isVector());
+    EXPECT_EQ(S.RecordTable[2].VFS.Parameters[0].getParamPos(), (unsigned) 0);
+
+    EXPECT_TRUE(S.RecordTable[2].VFS.Parameters[1].isLinear());
+    EXPECT_EQ(S.RecordTable[2].VFS.Parameters[1].getParamPos(), (unsigned) 1);
+    EXPECT_EQ(S.RecordTable[2].VFS.Parameters[1].getLinearStepOrPos(), 1);
+
+    EXPECT_EQ(S.RecordTable[2].ScalarName, "sin");
+    EXPECT_EQ(S.RecordTable[2].VectorName, "_ZGVnN4vl_sin");
+
+}
+
+TEST_F(SearchVectorFunctionSystemTest, NameDemangling) {
+    SVFS S(M.get());
+
+    SVFS::VectorRecord Output;
+
+    S.demangleName("_ZGVnN2vl_sin", Output);
+
+    EXPECT_EQ(Output.VFS.VF, (unsigned) 2);
+    EXPECT_FALSE(Output.VFS.IsMasked);
+    EXPECT_EQ(Output.VFS.ISA, ISAKind::ISA_AdvancedSIMD);
+
+    // Does call parseParamList()
+    EXPECT_TRUE(Output.VFS.Parameters[0].isVector());
+    EXPECT_EQ(Output.VFS.Parameters[0].getParamPos(), (unsigned) 0);
+
+    EXPECT_EQ(Output.VFS.Parameters[1].getLinearStepOrPos(), 1);
+    EXPECT_TRUE(Output.VFS.Parameters[1].isLinear());
+    EXPECT_EQ(Output.VFS.Parameters[1].getParamPos(), (unsigned) 1);
+
+    EXPECT_EQ(Output.ScalarName, "sin") ;
+    EXPECT_EQ(Output.VectorName, "_ZGVnN2vl_sin");
+
+}
+
+TEST_F(SearchVectorFunctionSystemTest, ParamListParsing) {
+    SVFS S(M.get());
+    
+    std::vector<ParamType> Output;
+
+    VFABI::parseParamList("vl16Ls32R3l", Output);
+
+    EXPECT_EQ(Output[0].getParamPos(), (unsigned) 0);
+    EXPECT_TRUE(Output[0].isVector());
+
+    EXPECT_EQ(Output[1].getParamPos(), (unsigned) 1);
+    EXPECT_TRUE(Output[1].isLinear());
+    EXPECT_EQ(Output[1].getLinearStepOrPos(), 16);
+
+    EXPECT_EQ(Output[2].getParamPos(), (unsigned) 2);
+    EXPECT_TRUE(Output[2].isLinearValPos());
+    EXPECT_EQ(Output[2].getLinearStepOrPos(), 32);
+
+    EXPECT_EQ(Output[3].getParamPos(), (unsigned) 3);
+    EXPECT_TRUE(Output[3].isLinearRef());
+    EXPECT_EQ(Output[3].getLinearStepOrPos(), 3);
+
+    EXPECT_EQ(Output[4].getParamPos(), (unsigned) 4);
+    EXPECT_TRUE(Output[4].isLinear());
+    EXPECT_EQ(Output[4].getLinearStepOrPos(), 1);
+
+}
+
+TEST_F(SearchVectorFunctionSystemTest, VFABITest) {
+    SVFS S(M.get());
+
+    // Getting ISA Kind
+    EXPECT_EQ(VFABI::getISA("_ZGVnN2_sin"), ISAKind::ISA_AdvancedSIMD);
+    EXPECT_EQ(VFABI::getISA("_ZGVsN2_sin"), ISAKind::ISA_SVE);
+    EXPECT_EQ(VFABI::getISA("_ZGVbN2_sin"), ISAKind::ISA_SSE);
+    EXPECT_EQ(VFABI::getISA("_ZGVcN2_sin"), ISAKind::ISA_AVX);
+    EXPECT_EQ(VFABI::getISA("_ZGVdN2_sin"), ISAKind::ISA_AVX2);
+    EXPECT_EQ(VFABI::getISA("_ZGVeN2_sin"), ISAKind::ISA_AVX512);
+
+    // Getting Mask Value
+    EXPECT_TRUE(VFABI::getIsMasked("_ZGVnM2v_sin"));
+    EXPECT_FALSE(VFABI::getIsMasked("_ZGVnN2v_sin"));
+    EXPECT_TRUE(VFABI::getIsMasked("_ZGVsN2v_sin"));
+    EXPECT_TRUE(VFABI::getIsMasked("_ZGVsM2v_sin"));
+
+    // Getting Scalable Value
+    EXPECT_TRUE(VFABI::getIsScalable("_ZGVsMxv_sin"));
+    EXPECT_FALSE(VFABI::getIsScalable("_ZGVsM2v_sin"));
+
+    // Getting VF
+    EXPECT_EQ(VFABI::getVF("_ZGVnM2v_sin"), (unsigned) 2);
+    EXPECT_EQ(VFABI::getVF("_ZGVnM22v_sin"), (unsigned) 22);
+    EXPECT_EQ(VFABI::getVF("_ZGVsMxv_sin"), (unsigned) 0);
+
+    // Getting Scalar Name
+    EXPECT_EQ(VFABI::getScalarName("_ZGVnM2v_sin"), "sin");
+    EXPECT_EQ(VFABI::getScalarName("_ZGVnM2v_sin(UserFunc)"), "sin");
+    EXPECT_EQ(VFABI::getScalarName("_ZGVnM2v___sin_sin_sin"), "__sin_sin_sin");
+
+    // Getting Vector Name
+    EXPECT_EQ(VFABI::getVectorName("_ZGVnM2v_sin"), "_ZGVnM2v_sin");
+    EXPECT_EQ(VFABI::getVectorName("_ZGVnM2v_sin(UserFunc)"), "UserFunc");
+
+}
+
+TEST_F(SearchVectorFunctionSystemTest, isFunctionVectorizable) {
+    SVFS S(M.get());
+
+    Value *Args[] = {ConstantInt::get(Type::getInt32Ty(Ctx), 20),
+                    ConstantInt::get(Type::getInt32Ty(Ctx), 20)};
+    std::unique_ptr<CallInst> Caller(CallInst::Create(F, Args));
+    CallInst *Call = Caller.get();
+
+    F->addFnAttr("vector-function-abi-variant", 
+                    "_ZGVnN2vv_cos(another_vector), _ZGVnN2vv_sin,"
+                    " _ZGVnN4vl_sin(sinVector),_ZGVnN4vl_sin");
+
+    S.createTableLookupRecord(Call);
+    std::vector<SVFS::VectorFunctionShape> AvailableVFS;
+    AvailableVFS = S.isFunctionVectorizable(Call);
+
+    EXPECT_EQ(AvailableVFS.size(), (unsigned) 3);
+    EXPECT_EQ(AvailableVFS[0], S.RecordTable[1].VFS);
+    EXPECT_EQ(AvailableVFS[1], S.RecordTable[2].VFS);
+    EXPECT_EQ(AvailableVFS[2], S.RecordTable[3].VFS);
+
+    const ParamType Param1((unsigned) 0, "v");
+    const ParamType Param2((unsigned) 1, "v");
+    const ParamType Param3((unsigned) 1, "l", 1);
+
+    // Corresponding VFS for _ZGVnN2vv
+    std::vector<ParamType> ParamList1{{Param1, Param2}};
+    SVFS::VectorFunctionShape ExpectedVFS1{(unsigned) 2 /* VF */,
+                            false /* IsMasked */, 
+                            false /* IsScalable */,
+                            ISAKind::ISA_AdvancedSIMD,
+                            ParamList1};
+
+    // Corresponding VFS for _ZGVnN4vl_sin
+    std::vector<ParamType> ParamList2{{Param1, Param3}};
+    SVFS::VectorFunctionShape ExpectedVFS2{(unsigned) 4 /* VF */,
+                            false /* IsMasked */, 
+                            false /* IsScalable */,
+                            ISAKind::ISA_AdvancedSIMD,
+                            ParamList2};
+
+    EXPECT_EQ(AvailableVFS[0], ExpectedVFS1);
+    EXPECT_EQ(AvailableVFS[1], ExpectedVFS2);
+    EXPECT_EQ(AvailableVFS[2], ExpectedVFS2);
+
+}
+
+TEST_F(SearchVectorFunctionSystemTest, getVectorizedFunction) {
+    SVFS S(M.get());
+
+    Value *Args[] = {ConstantInt::get(Type::getInt32Ty(Ctx), 20),
+                    ConstantInt::get(Type::getInt32Ty(Ctx), 20)};
+    std::unique_ptr<CallInst> Caller(CallInst::Create(F, Args));
+    CallInst *Call = Caller.get();
+
+    F->addFnAttr("vector-function-abi-variant", 
+                    "_ZGVnN2vv_cos(another_vector),_ZGVnN2vv_sin,"
+                    "_ZGVnN4vl_sin(sinVector), _ZGVnN4vl_sin,"
+                    " _ZGVnN16ll_sin");
+
+    const ParamType Param1((unsigned) 0, "v");
+    const ParamType Param2((unsigned) 0, "l", 1);
+    const ParamType Param3((unsigned) 1, "l", 1);
+
+    // Corresponding VFS for _ZGVnN4vl_sin
+    std::vector<ParamType> ParamList1{{Param1, Param3}};
+    SVFS::VectorFunctionShape VFS1{(unsigned) 4 /* VF */,
+                            false /* IsMasked */, 
+                            false /* IsScalable */,
+                            ISAKind::ISA_AdvancedSIMD,
+                            ParamList1};
+
+    Type* Tys0[] = {VectorType::get(FArgTypes[0], 4), 
+                        FArgTypes[1]};
+    FunctionType* VectorFTy0 = 
+                FunctionType::get(VectorType::get(Type::getInt32Ty(Ctx), 4),
+                                       Tys0, false);
+    Function* VectorFunc0 = Function::Create(VectorFTy0,
+                                                Function::ExternalLinkage,
+                                                "sinVector", M.get());
+
+    S.createTableLookupRecord(Call);
+    // Checking for "_ZGVnN4vl_sin"
+    Function *ResFunc0 = S.getVectorizedFunction(Call, VFS1);
+    // As the given VFS has two possible options,
+    // we return the one with custom name
+    EXPECT_EQ(ResFunc0, VectorFunc0);
+
+    // Corresponding VFS for _ZGVnN16ll_sin
+    std::vector<ParamType> ParamList2{{Param2, Param3}};
+    SVFS::VectorFunctionShape VFS2{(unsigned) 16 /* VF */,
+                            false /* IsMasked */, 
+                            false /* IsScalable */,
+                            ISAKind::ISA_AdvancedSIMD,
+                            ParamList2};
+
+    FunctionType *VectorFTy1 = 
+                FunctionType::get(VectorType::get(Type::getInt32Ty(Ctx), 16),
+                                       FArgTypes, false);
+    Function *VectorFunc1 = Function::Create(VectorFTy1, 
+                                                Function::ExternalLinkage,
+                                                "_ZGVnN16ll_sin", M.get());
+
+    // Checking for "_ZGVnN16ll_sin"
+    Function *ResFunc1 = S.getVectorizedFunction(Call, VFS2);
+    // Only one record exists for the given VFS
+    EXPECT_EQ(ResFunc1, VectorFunc1);
+
+}
 No newline at end of file