[VectorUtils] API for VFShape, update VFInfo.

[fpetrogalli]

Summary

Summary:
This patch introduces an API to build and modify vector shapes.

The validity of a VFShape can be checked with the
`hasValidParameterList` method, which is also run in an assertion each
time a VFShape is modified.

The field VFISAKind has been moved to VFInfo under the assumption that
different ISAs can map to the same VFShape (as it can be in the case
of vector extensions with the same registers size, for example AVX and
AVX2).

Reviewers: sdesmalen, jdoerfert, simoll, hsaito

Subscribers: hiraditya, llvm-commits

Tags: #llvm

Differential Revision: https://reviews.llvm.org/D70513

[fpetrogalli]

llvm/unittests/Analysis/VectorUtilsTest.cpp

315

This should be /*Parameters*/, not /*HasGlobalPredicate*/. Same for all uses below.

[fpetrogalli]

Fully implement and test the API.

This patch is ready to be reviewed.

Thanks,

Francesco

[fpetrogalli]

In this patch I have achieved better unit tests granularity by moving
the EXPECT_* macros from the test fixture class into the actual
test, so that in case of failure the log message points at the right
line in the code (otherwise it always points at the EXPECT_* in the
method used to run the check in the class definition of the test
fixture).

[fpetrogalli]

In this last update I have:

1. Removed an assertion in updateParameter that was checking a condition for VFParamKind::GlobalPredicate already checked in hasValidParameterList.

2. Renamed a method in the test for better readability of the code (from isValidParameterList to validParams).

Thanks,

Francesco

[fpetrogalli]

In this update I have removed empty statements in the tests. (facepalm)

Thanks,

Francesco

[fpetrogalli]

Update (and rename) the get method to use ElementCount instead of VF
and IsScalable separately.

[fpetrogalli]

llvm/include/llvm/Analysis/VectorUtils.h

83–85

Notice that I am not using ElementCount here to realize VF and IsScalable because it would delete the default constructors associated to VFShape and VFInfo.

[fpetrogalli]

Gentle ping!

[jdoerfert]

Looks fine from my perspective. Anyone else has input on this?

[fpetrogalli]

Allow GlobalPredicate parameters in any position of the signature.

[sdesmalen]

llvm/include/llvm/Analysis/VectorUtils.h

91

nit: can you add a newline between the previous and next method?

llvm/lib/Analysis/VectorUtils.cpp

1189

should this be an assert?

1191

nit: can you add a newline above?

1192

nit: Nothign -> Nothing

1222

Can you add a function here that calculates this, per supported VFABI?

llvm/unittests/Analysis/VectorUtilsTest.cpp

311

nit: this could do with some newlines.

[fpetrogalli]

Address review comments from @sdesmalen.

llvm/lib/Analysis/VectorUtils.cpp

1189

I have updated also the tests replacing EXPECT_FALSE with EXPECT_DEATH, to make sure the assert is not removed.

1222

Marking this as done as the most recent version of the patch doesn't have any concept for VFABI for GlobalPredicate, as the global predicate is allowed to be anywhere in the signature, as long as it is unique.

[sdesmalen]

Thanks for the fixes @fpetrogalli, LGTM!

llvm/include/llvm/Analysis/VectorUtils.h

 
 /// Contains the information about the kind of vectorization
 /// available.
 ///
 /// This object in independent on the paradigm used to
 /// represent vector functions. in particular, it is not attached to
 /// any target-specific ABI.
 struct VFShape {
   unsigned VF;     // Vectorization factor.
   bool IsScalable; // True if the function is a scalable function.
-  VFISAKind ISA;   // Instruction Set Architecture.
   SmallVector<VFParameter, 8> Parameters; // List of parameter informations.
   // Comparison operator.
   bool operator==(const VFShape &Other) const {
-    return std::tie(VF, IsScalable, ISA, Parameters) ==
-           std::tie(Other.VF, Other.IsScalable, Other.ISA, Other.Parameters);
+    return std::tie(VF, IsScalable, Parameters) ==
+           std::tie(Other.VF, Other.IsScalable, Other.Parameters);
+  }
+  /// Update the parameter in position P.ParamPos to P.
+  void updateParam(VFParameter P) {
+    assert(P.ParamPos < Parameters.size() && "Invalid parameter position.");
+    Parameters[P.ParamPos] = P;
+    assert(hasValidParameterList() && "Invalid parameter list");
+  }
+  // Retrieve the basic vectorization shape of the function, where all
+  // parameters are mapped to VFParamKind::Vector with \p EC
+  // lanes. Specifies whether the function has a Global Predicate
+  // argument via \p HasGlobalPred.
+  static VFShape get(const CallInst &CI, ElementCount EC, bool HasGlobalPred) {
+    SmallVector<VFParameter, 8> Parameters;
+    for (unsigned I = 0; I < CI.arg_size(); ++I)
+      Parameters.push_back(VFParameter({I, VFParamKind::Vector}));
+    if (HasGlobalPred)
+      Parameters.push_back(
+          VFParameter({CI.arg_size(), VFParamKind::GlobalPredicate}));
+
+    return {EC.Min, EC.Scalable, Parameters};
   }
+  /// Sanity check on the Parameters in the VFShape.
+  bool hasValidParameterList() const;
 };
 
 /// Holds the VFShape for a specific scalar to vector function mapping.
 struct VFInfo {
   VFShape Shape;        // Classification of the vector function.
   StringRef ScalarName; // Scalar Function Name.
   StringRef VectorName; // Vector Function Name associated to this VFInfo.
+  VFISAKind ISA;        // Instruction Set Architecture.
 
   // Comparison operator.
   bool operator==(const VFInfo &Other) const {
-    return std::tie(Shape, ScalarName, VectorName) ==
-           std::tie(Shape, Other.ScalarName, Other.VectorName);
+    return std::tie(Shape, ScalarName, VectorName, ISA) ==
+           std::tie(Shape, Other.ScalarName, Other.VectorName, Other.ISA);
   }
 };
 
 namespace VFABI {
 /// LLVM Internal VFABI ISA token for vector functions.
 static constexpr char const *_LLVM_ = "_LLVM_";
 
 /// Function to contruct a VFInfo out of a mangled names in the

llvm/lib/Analysis/VFABIDemangling.cpp

const auto NGlobalPreds = std::count_if(
       Parameters.begin(), Parameters.end(), [](const VFParameter PK) {
         return PK.ParamKind == VFParamKind::GlobalPredicate;
       });
   assert(NGlobalPreds < 2 && "Cannot have more than one global predicate.");
   if (NGlobalPreds)
     assert(Parameters.back().ParamKind == VFParamKind::GlobalPredicate &&
            "The global predicate must be the last parameter");
 
-  const VFShape Shape({VF, IsScalable, ISA, Parameters});
-  return VFInfo({Shape, ScalarName, VectorName});
+  const VFShape Shape({VF, IsScalable, Parameters});
+  return VFInfo({Shape, ScalarName, VectorName, ISA});
 }
 
 VFParamKind VFABI::getVFParamKindFromString(const StringRef Token) {
   const VFParamKind ParamKind = StringSwitch<VFParamKind>(Token)
                                     .Case("v", VFParamKind::Vector)
                                     .Case("l", VFParamKind::OMP_Linear)
                                     .Case("R", VFParamKind::OMP_LinearRef)
                                     .Case("L", VFParamKind::OMP_LinearVal)

llvm/lib/Analysis/VectorUtils.cpp

#ifndef NDEBUG
     Optional<VFInfo> Info = VFABI::tryDemangleForVFABI(S);
     assert(Info.hasValue() && "Invalid name for a VFABI variant.");
     assert(CI.getModule()->getFunction(Info.getValue().VectorName) &&
            "Vector function is missing.");
 #endif
     VariantMappings.push_back(S);
   }
 }
+
+bool VFShape::hasValidParameterList() const {
+  for (unsigned Pos = 0, NumParams = Parameters.size(); Pos < NumParams;
+       ++Pos) {
+    if (Parameters[Pos].ParamPos != Pos)
+      return false;
+    switch (Parameters[Pos].ParamKind) {
+    default: // Nothign to check.
+      break;
+    case VFParamKind::OMP_Linear:
+    case VFParamKind::OMP_LinearRef:
+    case VFParamKind::OMP_LinearVal:
+    case VFParamKind::OMP_LinearUVal:
+      // Compile time linear steps must be non-zero.
+      if (Parameters[Pos].LinearStepOrPos == 0)
+        return false;
+      break;
+    case VFParamKind::OMP_LinearPos:
+    case VFParamKind::OMP_LinearRefPos:
+    case VFParamKind::OMP_LinearValPos:
+    case VFParamKind::OMP_LinearUValPos:
+      // The runtime linear step must be referring to some other
+      // parameters in the signature.
+      if (Parameters[Pos].LinearStepOrPos >= int(NumParams))
+        return false;
+      // The linear step parameter must be marked as uniform.
+      if (Parameters[Parameters[Pos].LinearStepOrPos].ParamKind !=
+          VFParamKind::OMP_Uniform)
+        return false;
+      // The linear step parameter can't point at itself.
+      if (Parameters[Pos].LinearStepOrPos == int(Pos))
+        return false;
+      break;
+    case VFParamKind::GlobalPredicate:
+      // The global predicate must be the unique. Can be placed anywhere in the
+      // signature.
+      for (unsigned NextPos = Pos + 1; NextPos < NumParams; ++NextPos)
+        if (Parameters[NextPos].ParamKind == VFParamKind::GlobalPredicate)
+          return false;
+      break;
+    }
+  }
+  return true;
+}

llvm/unittests/Analysis/VectorFunctionABITest.cpp

private:
   // Parser output.
   VFInfo Info;
   // Reset the parser output references.
   void reset() { Info = VFInfo(); }
 
 protected:
   // Referencies to the parser output field.
   unsigned &VF = Info.Shape.VF;
-  VFISAKind &ISA = Info.Shape.ISA;
+  VFISAKind &ISA = Info.ISA;
   SmallVector<VFParameter, 8> &Parameters = Info.Shape.Parameters;
   StringRef &ScalarName = Info.ScalarName;
   StringRef &VectorName = Info.VectorName;
   bool &IsScalable = Info.Shape.IsScalable;
   // Invoke the parser.
   bool invokeParser(const StringRef MangledName) {
     reset();
     const auto OptInfo = VFABI::tryDemangleForVFABI(MangledName);

llvm/unittests/Analysis/VectorUtilsTest.cpp

TEST_F(VectorUtilsTest, getSplatValueElt1) {
   parseAssembly(
       "define <2 x i8> @test(i8 %x) {\n"
       "  %ins = insertelement <2 x i8> undef, i8 %x, i32 1\n"
       "  %A = shufflevector <2 x i8> %ins, <2 x i8> undef, <2 x i32> <i32 1, i32 1>\n"
       "  ret <2 x i8> %A\n"
       "}\n");
   EXPECT_EQ(getSplatValue(A), nullptr);
 }
+
+////////////////////////////////////////////////////////////////////////////////
+// VFShape API tests.
+////////////////////////////////////////////////////////////////////////////////
+
+class VFShapeAPITest : public testing::Test {
+protected:
+  void SetUp() override {
+    M = parseAssemblyString(IR, Err, Ctx);
+    // Get the only call instruction in the block, which is the first
+    // instruction.
+    CI = dyn_cast<CallInst>(&*(instructions(M->getFunction("f")).begin()));
+  }
+  const char *IR = "define i32 @f(i32 %a, i64 %b, double %c) {\n"
+                   " %1 = call i32 @g(i32 %a, i64 %b, double %c)\n"
+                   "  ret i32 %1\n"
+                   "}\n"
+                   "declare i32 @g(i32, i64, double)\n";
+  LLVMContext Ctx;
+  SMDiagnostic Err;
+  std::unique_ptr<Module> M;
+  CallInst *CI;
+  // Dummy shape with no parameters, overwritten by buildShape when invoked.
+  VFShape Shape = {/*VF*/ 2, /*IsScalable*/ false, /*Parameters*/ {}};
+  VFShape Expected;
+  SmallVector<VFParameter, 8> &ExpectedParams = Expected.Parameters;
+  void buildShape(unsigned VF, bool IsScalable, bool HasGlobalPred) {
+    Shape = VFShape::get(*CI, {VF, IsScalable}, HasGlobalPred);
+  }
+  bool validParams(ArrayRef<VFParameter> Parameters) {
+    Shape.Parameters =
+        SmallVector<VFParameter, 8>(Parameters.begin(), Parameters.end());
+    return Shape.hasValidParameterList();
+  }
+};
+
+TEST_F(VFShapeAPITest, API_buildVFShape) {
+  buildShape(/*VF*/ 2, /*IsScalable*/ false, /*HasGlobalPred*/ false);
+  Expected = {/*VF*/ 2, /*IsScalable*/ false, /*Parameters*/ {
+                  {0, VFParamKind::Vector},
+                  {1, VFParamKind::Vector},
+                  {2, VFParamKind::Vector},
+              }};
+  EXPECT_EQ(Shape, Expected);
+
+  buildShape(/*VF*/ 4, /*IsScalable*/ false, /*HasGlobalPred*/ true);
+  Expected = {/*VF*/ 4, /*IsScalable*/ false, /*Parameters*/ {
+                  {0, VFParamKind::Vector},
+                  {1, VFParamKind::Vector},
+                  {2, VFParamKind::Vector},
+                  {3, VFParamKind::GlobalPredicate},
+              }};
+  EXPECT_EQ(Shape, Expected);
+
+  buildShape(/*VF*/ 16, /*IsScalable*/ true, /*HasGlobalPred*/ false);
+  Expected = {/*VF*/ 16, /*IsScalable*/ true, /*Parameters*/ {
+                  {0, VFParamKind::Vector},
+                  {1, VFParamKind::Vector},
+                  {2, VFParamKind::Vector},
+              }};
+  EXPECT_EQ(Shape, Expected);
+}
+
+TEST_F(VFShapeAPITest, API_updateVFShape) {
+
+  buildShape(/*VF*/ 2, /*IsScalable*/ false, /*HasGlobalPred*/ false);
+  Shape.updateParam({0 /*Pos*/, VFParamKind::OMP_Linear, 1, Align(4)});
+  Expected = {/*VF*/ 2, /*IsScalable*/ false, /*Parameters*/ {
+                  {0, VFParamKind::OMP_Linear, 1, Align(4)},
+                  {1, VFParamKind::Vector},
+                  {2, VFParamKind::Vector},
+              }};
+  EXPECT_EQ(Shape, Expected);
+
+  // From this point on, we update only the parameters of the VFShape,
+  // so we update only the reference of the expected Parameters.
+  Shape.updateParam({1 /*Pos*/, VFParamKind::OMP_Uniform});
+  ExpectedParams = {
+      {0, VFParamKind::OMP_Linear, 1, Align(4)},
+      {1, VFParamKind::OMP_Uniform},
+      {2, VFParamKind::Vector},
+  };
+  EXPECT_EQ(Shape, Expected);
+
+  Shape.updateParam({2 /*Pos*/, VFParamKind::OMP_LinearRefPos, 1});
+  ExpectedParams = {
+      {0, VFParamKind::OMP_Linear, 1, Align(4)},
+      {1, VFParamKind::OMP_Uniform},
+      {2, VFParamKind::OMP_LinearRefPos, 1},
+  };
+  EXPECT_EQ(Shape, Expected);
+}
+
+TEST_F(VFShapeAPITest, API_updateVFShape_GlobalPredicate) {
+
+  buildShape(/*VF*/ 2, /*IsScalable*/ true, /*HasGlobalPred*/ true);
+  Shape.updateParam({1 /*Pos*/, VFParamKind::OMP_Uniform});
+  Expected = {/*VF*/ 2, /*IsScalable*/ true,
+              /*Parameters*/ {{0, VFParamKind::Vector},
+                              {1, VFParamKind::OMP_Uniform},
+                              {2, VFParamKind::Vector},
+                              {3, VFParamKind::GlobalPredicate}}};
+  EXPECT_EQ(Shape, Expected);
+}
+
+TEST_F(VFShapeAPITest, Parameters_Valid) {
+  // ParamPos in order.
+  EXPECT_TRUE(validParams({{0, VFParamKind::Vector}}));
+  EXPECT_TRUE(
+      validParams({{0, VFParamKind::Vector}, {1, VFParamKind::Vector}}));
+  EXPECT_TRUE(validParams({{0, VFParamKind::Vector},
+                           {1, VFParamKind::Vector},
+                           {2, VFParamKind::Vector}}));
+
+  // GlocalPredicate is unique.
+  EXPECT_TRUE(validParams({{0, VFParamKind::Vector},
+                           {1, VFParamKind::Vector},
+                           {2, VFParamKind::Vector},
+                           {3, VFParamKind::GlobalPredicate}}));
+
+  EXPECT_TRUE(validParams({{0, VFParamKind::Vector},
+                           {1, VFParamKind::GlobalPredicate},
+                           {2, VFParamKind::Vector}}));
+}
+
+TEST_F(VFShapeAPITest, Parameters_ValidOpenMPLinear) {
+// Valid linear constant step (>0).
+#define __BUILD_PARAMETERS(Kind, Val)                                          \
+  {                                                                            \
+    { 0, Kind, Val }                                                           \
+  }
+  EXPECT_TRUE(validParams(__BUILD_PARAMETERS(VFParamKind::OMP_Linear, 1)));
+  EXPECT_TRUE(validParams(__BUILD_PARAMETERS(VFParamKind::OMP_LinearRef, 2)));
+  EXPECT_TRUE(validParams(__BUILD_PARAMETERS(VFParamKind::OMP_LinearVal, 4)));
+  EXPECT_TRUE(validParams(__BUILD_PARAMETERS(VFParamKind::OMP_LinearUVal, 33)));
+#undef __BUILD_PARAMETERS
+
+// Valid linear runtime step (the step parameter is marked uniform).
+#define __BUILD_PARAMETERS(Kind)                                               \
+  {                                                                            \
+    {0, VFParamKind::OMP_Uniform}, {1, VFParamKind::Vector}, { 2, Kind, 0 }    \
+  }
+  EXPECT_TRUE(validParams(__BUILD_PARAMETERS(VFParamKind::OMP_LinearPos)));
+  EXPECT_TRUE(validParams(__BUILD_PARAMETERS(VFParamKind::OMP_LinearRefPos)));
+  EXPECT_TRUE(validParams(__BUILD_PARAMETERS(VFParamKind::OMP_LinearValPos)));
+  EXPECT_TRUE(validParams(__BUILD_PARAMETERS(VFParamKind::OMP_LinearUValPos)));
+#undef __BUILD_PARAMETERS
+}
+
+TEST_F(VFShapeAPITest, Parameters_Invalid) {
+  // Wrong order.
+  EXPECT_FALSE(validParams({{1, VFParamKind::Vector}}));
+  EXPECT_FALSE(
+      validParams({{1, VFParamKind::Vector}, {0, VFParamKind::Vector}}));
+
+  // GlobalPredicate is not unique
+  EXPECT_FALSE(validParams({{0, VFParamKind::Vector},
+                            {1, VFParamKind::GlobalPredicate},
+                            {2, VFParamKind::GlobalPredicate}}));
+  EXPECT_FALSE(validParams({{0, VFParamKind::GlobalPredicate},
+                            {1, VFParamKind::Vector},
+                            {2, VFParamKind::GlobalPredicate}}));
+}
+
+TEST_F(VFShapeAPITest, Parameters_InvalidOpenMPLinear) {
+// Compile time linear steps must be non-zero (compile time invariant).
+#define __BUILD_PARAMETERS(Kind)                                               \
+  {                                                                            \
+    { 0, Kind, 0 }                                                             \
+  }
+  EXPECT_FALSE(validParams(__BUILD_PARAMETERS(VFParamKind::OMP_Linear)));
+  EXPECT_FALSE(validParams(__BUILD_PARAMETERS(VFParamKind::OMP_LinearRef)));
+  EXPECT_FALSE(validParams(__BUILD_PARAMETERS(VFParamKind::OMP_LinearVal)));
+  EXPECT_FALSE(validParams(__BUILD_PARAMETERS(VFParamKind::OMP_LinearUVal)));
+#undef __BUILD_PARAMETERS
+
+// The step of a runtime linear parameter must be marked
+// as uniform (runtime invariant).
+#define __BUILD_PARAMETERS(Kind)                                               \
+  {                                                                            \
+    {0, VFParamKind::OMP_Uniform}, {1, VFParamKind::Vector}, { 2, Kind, 1 }    \
+  }
+  EXPECT_FALSE(validParams(__BUILD_PARAMETERS(VFParamKind::OMP_LinearPos)));
+  EXPECT_FALSE(validParams(__BUILD_PARAMETERS(VFParamKind::OMP_LinearRefPos)));
+  EXPECT_FALSE(validParams(__BUILD_PARAMETERS(VFParamKind::OMP_LinearValPos)));
+  EXPECT_FALSE(validParams(__BUILD_PARAMETERS(VFParamKind::OMP_LinearUValPos)));
+#undef __BUILD_PARAMETERS
+
+// The linear step parameter can't point at itself.
+#define __BUILD_PARAMETERS(Kind)                                               \
+  {                                                                            \
+    {0, VFParamKind::Vector}, {1, VFParamKind::Vector}, { 2, Kind, 2 }         \
+  }
+  EXPECT_FALSE(validParams(__BUILD_PARAMETERS(VFParamKind::OMP_LinearPos)));
+  EXPECT_FALSE(validParams(__BUILD_PARAMETERS(VFParamKind::OMP_LinearRefPos)));
+  EXPECT_FALSE(validParams(__BUILD_PARAMETERS(VFParamKind::OMP_LinearValPos)));
+  EXPECT_FALSE(validParams(__BUILD_PARAMETERS(VFParamKind::OMP_LinearUValPos)));
+#undef __BUILD_PARAMETERS
+
+// Linear parameter (runtime) is out of range.
+#define __BUILD_PARAMETERS(Kind)                                               \
+  {                                                                            \
+    {0, VFParamKind::Vector}, {1, VFParamKind::Vector}, { 2, Kind, 3 }         \
+  }
+  EXPECT_FALSE(validParams(__BUILD_PARAMETERS(VFParamKind::OMP_LinearPos)));
+  EXPECT_FALSE(validParams(__BUILD_PARAMETERS(VFParamKind::OMP_LinearRefPos)));
+  EXPECT_FALSE(validParams(__BUILD_PARAMETERS(VFParamKind::OMP_LinearValPos)));
+  EXPECT_FALSE(validParams(__BUILD_PARAMETERS(VFParamKind::OMP_LinearUValPos)));
+#undef __BUILD_PARAMETERS
+}