[VFDatabase] Scalar functions are vector functions with VF =1

[masoud.ataei]

Summary

Proposing to return scalar function when VF==1.

I am adding trivial mapping scalar --> scalar when VF==1 to
prevent false positive for "isVectorizable" query. Also modified
"getVectorizedFunction" to return scalar function when VF==1.
This patch is supported by LIT and unit tests.

[fhahn]

It would be great if you could explain *why* it needs to set this, ideally with a test case. The existing code either does not use NeedToScalarize or initializes it with false. Technically we don't need to scalarize with VF==1, its already the scalar loop.

[masoud.ataei]

In D78054#1979031, @fhahn wrote:

It would be great if you could explain *why* it needs to set this, ideally with a test case. The existing code either does not use NeedToScalarize or initializes it with false. Technically we don't need to scalarize with VF==1, its already the scalar loop.

I have a large test case that when we have VF=1, it will go to else part of this if statement from InnerLoopVectorizer::widenCallInstruction function

    if (UseVectorIntrinsic) {
      // Use vector version of the intrinsic.
      Type *TysForDecl[] = {CI->getType()};
      if (VF > 1)
        TysForDecl[0] = VectorType::get(CI->getType()->getScalarType(), VF);
      VectorF = Intrinsic::getDeclaration(M, ID, TysForDecl);
    } else {
      // Use vector version of the function call.
      const VFShape Shape =
          VFShape::get(*CI, {VF, false} /*EC*/, false /*HasGlobalPred*/);
#ifndef NDEBUG
        const SmallVector<VFInfo, 8> Infos = VFDatabase::getMappings(*CI);
        assert(std::find_if(Infos.begin(), Infos.end(),
                            [&Shape](const VFInfo &Info) {
                              return Info.Shape == Shape;
                            }) != Infos.end() &&
               "Vector function shape is missing from the database.");
#endif
        VectorF = VFDatabase(*CI).getVectorizedFunction(Shape);
    }

and it will create a Shape with VF=1 then the assertion is triggered. But I think we shouldn't be there when we are not vectorizing. Returning true for NeedToScalarize prevent us from that.
I will see if I can reproduce the same issue with an small test case.

[fhahn]

In D78054#1981255, @masoud.ataei wrote:

In D78054#1979031, @fhahn wrote:

It would be great if you could explain *why* it needs to set this, ideally with a test case. The existing code either does not use NeedToScalarize or initializes it with false. Technically we don't need to scalarize with VF==1, its already the scalar loop.

I have a large test case that when we have VF=1, it will go to else part of this if statement from InnerLoopVectorizer::widenCallInstruction function

    if (UseVectorIntrinsic) {
      // Use vector version of the intrinsic.
      Type *TysForDecl[] = {CI->getType()};
      if (VF > 1)
        TysForDecl[0] = VectorType::get(CI->getType()->getScalarType(), VF);
      VectorF = Intrinsic::getDeclaration(M, ID, TysForDecl);
    } else {
      // Use vector version of the function call.
      const VFShape Shape =
          VFShape::get(*CI, {VF, false} /*EC*/, false /*HasGlobalPred*/);
#ifndef NDEBUG
        const SmallVector<VFInfo, 8> Infos = VFDatabase::getMappings(*CI);
        assert(std::find_if(Infos.begin(), Infos.end(),
                            [&Shape](const VFInfo &Info) {
                              return Info.Shape == Shape;
                            }) != Infos.end() &&
               "Vector function shape is missing from the database.");
#endif
        VectorF = VFDatabase(*CI).getVectorizedFunction(Shape);
    }

and it will create a Shape with VF=1 then the assertion is triggered. But I think we shouldn't be there when we are not vectorizing. Returning true for NeedToScalarize prevent us from that.
I will see if I can reproduce the same issue with an small test case.

getting a reduced test case would be great. Bugpoint might be helpful with reducing a large IR file. The fix might be just changing the default of NeedToScalarize from true to false when initializing it a few lines above.

[masoud.ataei]

I am adding a test to my proposed change.

[masoud.ataei]

Assert is required for this test.

[fpetrogalli]

HI @masoud.ataei ,

thank you for working on this.

Regarding the following:

it will create a Shape with VF=1 then the assertion is triggered. But I think we shouldn't be there when we are not vectorizing. Returning true for NeedToScalarize prevent us from that.

I think that setting NeedToScalarize = true when VF == 1 is a bit misleading, because nothing has been vectorized.

Instead, why not modify the VFDatabase queries and return the scalar function when looking for a VFShape that has VF == 1? The assertion you are seeing being raised is there to report the lack of vector functions of the shape the vectorizer is expecting... I see as a perfectly legal operation to return the original scalar function if the vectorizer is vectorizing with a VFShape of VF == 1.

Let me know if this doesn't make sense to you, I might have missed something!

Kind regards,

Francesco

[fpetrogalli]

Hi @masoud.ataei,

this is the right approach but I think it needs some refinement. Thank you for your patience!

1. May I ask you to upload patches with the full context of the changes (helps to see the code around your changes, so that the reviewers doesn't have to look at the sources in a separate windows or editor. https://releases.llvm.org/10.0.0/docs/Phabricator.html#requesting-a-review-via-the-web-interface explains how to add the context)
2. Please add a couple of unit tests in llvm-project/llvm/unittests/Analysis/VectorUtilsTest.cpp to test VFShape::getTrivialMapping.
3. It would be great if you could add tests for VFDabase in the same unit tests file to test the behavior that returns the scalar function when the trivial mapping is passed to getVectorizedFunction.

Let me know if you have any question.

Francesco

llvm/include/llvm/Analysis/VectorUtils.h

99

I think it is worth describing this method making sure it is clear it realizes the VFShape of the original scalar function with VF =1, something like this.

Retrieve the VFShape that can be used to map a (scalar) function to itself, with VF = 1.

100

Typo: Triival -> Trivial

Nit: maybe instead of Trivial we could call this method getScalarShape? This name will make it pretty clear what the method is doing.

247–254

I'd rather not change the signature of this function, but instead make const CallInst &CI a field of VFDatabase initiated by the constructor.

The reason for this is that it seems off to me to invoke VFDatabase(CI).getVectorizedFunction(Shape, CI), where CI has to be specified twice.

Also, I might be wrong, but I don't see how this patch is fixing your problem. You are using VFShape::getTriivalMapping(CI) while looping on ScalarToVectorMappings, which seems to me doesn't have at all the trivial mapping in it because you haven't modified the list of mappins.

What I think you should do here is check the input shape to be the trivial mapping before ever looping on ScalarToVectorMappinngs, and exit returning CI->getCalledFunction():

Function *getVectorizedFunction(const VFShape &Shape) {
  if (Shape = VFShape::getTriivalMapping(CI))
    return CI->getCalledFunction();

  for (const auto &Info : ScalarToVectorMappings)
    // .... original code
}

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

4395

This assertion is here to make sure that VFDatabase succeeds in finding the vector function it's been queried on. It does so by looking in the mapping because it assumes that the mappings are listing all the possible vector shapes.

Now that we have decided to add a mapping (the trivial one) that is not handled by the mappings retrieved with VFDatabase::getMappings (and we have to do so otherwise the query "is function vectorizable" will always evaluate to true), I think we have to check that VFDatabase has succeeded in finding the vector version it has been looking for. Thismeans that we need to assert that VFDatabase(*CI).getVectorizedFunction(Shape) !=nullptr.

I would keep the code verbose here, instead of relying on the assert(VectorF && "Can't create vector function."); at line 4400, so that we can differentiate the reason for the failure in the scope where the VFDatabase is used.

FWIW, I think that the assertion here is not raised anymore by your test not because you are returning the scalar function of the VFInfo that have the trivial mappings (which I think is never being run), but because the || VF == 1 is evaluating to true in the case you are testing.

[masoud.ataei]

Addressing comments and adding unit tests.

[masoud.ataei]

Reviews addressed.

[fpetrogalli]

Hi @masoud.ataei - almost there!

I have added a couple of comments that you need to address, inlined in the patch.

I also have two minor requests:

1. update the commit message title mentioning the VFDatabase, something like [VFDatabase] Scalar functions are vector functions with VF =1.
2. There is nothing about scalarization in this patch, so I guess you can rename the ll test to something like vectorizeVFone.ll?

Thank you (again) for your patience!

Kind regards,

Francesco

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

4401

Sorry - I didn't mean to remove this assert. We need to check that sure we don't end up with a null pointer when generating VectorF in line 4384. I like the idea of having assert specifically for the two cases (intrinsics and VFDatabase), as it helps debugging, so instead of restoring this assert, please add another assert on line 4385 (after VectorF = Intrinsic::getDeclaration(M, ID, TysForDecl); that says something along the lines of "Can't retrieve vector intrinsic.".

llvm/test/Transforms/LoopVectorize/scalarizeVFOne.ll

8 ↗

(On Diff #259978)

I wouldn't check the assert being raised. In term of testing for this patch I am happy with the unittest you have written. For the sake of protecting the high level test that made you run into this problem, I suggest you modifying the checks of this test to make sure the loop is vectorized with VF = 1 (I guess you just need to make sure no vector instructions are generated...)

llvm/unittests/Analysis/VectorUtilsTest.cpp

546

May I ask why not just EXPECT_EQ(VFDatabase(*CI).getVectorizedFunction(scalarShape), ...? I am missing the reason why you had to use new here.

[masoud.ataei]

Thanks Francesco for the reviews.
The reviews are addressed.

[fpetrogalli]

In D78054#2005917, @masoud.ataei wrote:

Thanks Francesco for the reviews.
The reviews are addressed.

Thank you! A couple more of comments, mostly nits, plus one substantial comment for the ll test, as I am not sure you are testing the right thing for this patch as it is right now (apologies if that was induced by my previous review).

Kind regards,

Francesco

llvm/include/llvm/Analysis/VectorUtils.h

102

Please name the constant parameters:

return VFShape::get(CI, /*EC*/{1, false}, /*HasGlobalPredicate*/false);

195

Docs:

/// The CallInst instance being queried for scalar to vector mappings.
const CallInst &CI;

llvm/test/Transforms/LoopVectorize/vectorizeVFone.ll

9

Are you sure you are checking the right thing here? If vectorization happens with VF = 2, you wouldn't be catching this because the VFDatabase would be redirecting the VF=2 call to __atand2_massv, as specified by the VFABI attribute below. If my understanding is correct, whaat you want to test here is that the compiler doesn't crash, and that it does not emit vector code. I think that should be tested by:

; CHECK-LABEL: getScalarFunc
; CHECK-NOT: <{{[0-9]+}} x double>

[masoud.ataei]

llvm/test/Transforms/LoopVectorize/vectorizeVFone.ll

9

I checked the force vectorize with vectorization factor=2, and I get this line:

%10 = call fast <2 x double> @__atand2_massv(<2 x double> %9)

So this will be caught by that check. About __atand2_massv function, regular expression {{.*}}atan{{.*}} will trigger it.

The reason that I cannot simply check for <{{[0-9]+}} x double> is this: There is

declare <2 x double> @__atand2_massv(<2 x double>) #1

declaration in IR when you want to do vectorization. So CHECK-NOT: <{{[0-9]+}} x double> will always return true.

[fpetrogalli]

llvm/test/Transforms/LoopVectorize/vectorizeVFone.ll

9

Thank you for explaining! I missed the fact that the check was valid also for the massv version of atan2. Might be worth adding a comment right before the check, saying that such check is supposed to catch also the massv version of the function.

[masoud.ataei]

Reviews are addressed.
Thanks Francesco,

[masoud.ataei]

Sorry, I was missing your suggestion of commenting above check on the test file.
Done.

[fpetrogalli]

One last thing!

llvm/unittests/Analysis/VectorUtilsTest.cpp

549–554

Same here as for the first EXPECT_EQ, I think you don't want to use operator new.

You could actually extract the VFDatabase(CI) in a variable, right before using it in any of the checks.

[masoud.ataei]

Oh, sorry I missed these part in my last update.
Thanks Francesco,

[fpetrogalli]

LGTM!

Thank you for working on this @masoud.ataei!

Francesco

[jsji]

llvm/test/Transforms/LoopVectorize/vectorizeVFone.ll

3

This might have problem -- what if the target powerpc64le is not buid?
I think we either need a REQUIRE or remove this triple , or move it to a target specific test dir.

[masoud.ataei]

llvm/test/Transforms/LoopVectorize/vectorizeVFone.ll

3

You are right. This triple is not needed.
This is already committed. I will create a new differential to propose to remove this triple.

llvm/include/llvm/Analysis/VectorUtils.h

struct VFShape {
 
   /// 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 VFShape that can be used to map a (scalar) function to itself,
+  // with VF = 1.
+  static VFShape getScalarShape(const CallInst &CI) {
+    return VFShape::get(CI, /*EC*/ {1, false}, /*HasGlobalPredicate*/ false);
+  }
+
   // 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}));

 
 /// The Vector Function Database.
 ///
 /// Helper class used to find the vector functions associated to a
 /// scalar CallInst.
 class VFDatabase {
   /// The Module of the CallInst CI.
   const Module *M;
+  /// The CallInst instance being queried for scalar to vector mappings.
+  const CallInst &CI;
   /// List of vector functions descritors associated to the call
   /// instruction.
   const SmallVector<VFInfo, 8> ScalarToVectorMappings;
 
   /// Retreive the scalar-to-vector mappings associated to the rule of
   /// a vector Function ABI.
   static void getVFABIMappings(const CallInst &CI,
                                SmallVectorImpl<VFInfo> &Mappings) {
static SmallVector<VFInfo, 8> getMappings(const CallInst &CI) {
 
     // Other non-VFABI variants should be retrieved here.
 
     return Ret;
   }
 
   /// Constructor, requires a CallInst instance.
   VFDatabase(CallInst &CI)
-      : M(CI.getModule()), ScalarToVectorMappings(VFDatabase::getMappings(CI)) {
-  }
+      : M(CI.getModule()), CI(CI),
+        ScalarToVectorMappings(VFDatabase::getMappings(CI)) {}
   /// \defgroup VFDatabase query interface.
   ///
   /// @{
   /// Retrieve the Function with VFShape \p Shape.
   Function *getVectorizedFunction(const VFShape &Shape) const {
+    if (Shape == VFShape::getScalarShape(CI))
+      return CI.getCalledFunction();
+
     for (const auto &Info : ScalarToVectorMappings)
       if (Info.Shape == Shape)
         return M->getFunction(Info.VectorName);
 
     return nullptr;
   }
   /// @}
 };
 

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

for (unsigned Part = 0; Part < UF; ++Part) {
 
     Function *VectorF;
     if (UseVectorIntrinsic) {
       // Use vector version of the intrinsic.
       Type *TysForDecl[] = {CI->getType()};
       if (VF > 1)
         TysForDecl[0] = VectorType::get(CI->getType()->getScalarType(), VF);
       VectorF = Intrinsic::getDeclaration(M, ID, TysForDecl);
+      assert(VectorF && "Can't retrieve vector intrinsic.");
     } else {
       // Use vector version of the function call.
       const VFShape Shape =
           VFShape::get(*CI, {VF, false} /*EC*/, false /*HasGlobalPred*/);
 #ifndef NDEBUG
-        const SmallVector<VFInfo, 8> Infos = VFDatabase::getMappings(*CI);
-        assert(std::find_if(Infos.begin(), Infos.end(),
-                            [&Shape](const VFInfo &Info) {
-                              return Info.Shape == Shape;
-                            }) != Infos.end() &&
-               "Vector function shape is missing from the database.");
+      assert(VFDatabase(*CI).getVectorizedFunction(Shape) != nullptr &&
+             "Can't create vector function.");
 #endif
         VectorF = VFDatabase(*CI).getVectorizedFunction(Shape);
     }
-      assert(VectorF && "Can't create vector function.");
-
       SmallVector<OperandBundleDef, 1> OpBundles;
       CI->getOperandBundlesAsDefs(OpBundles);
       CallInst *V = Builder.CreateCall(VectorF, Args, OpBundles);
 
       if (isa<FPMathOperator>(V))
         V->copyFastMathFlags(CI);
 
       VectorLoopValueMap.setVectorValue(&I, Part, V);

llvm/test/Transforms/LoopVectorize/vectorizeVFone.ll

+; RUN: opt < %s -passes=loop-vectorize -S 2>&1 | FileCheck %s
+
+target triple = "powerpc64le-unknown-linux-gnu"
+%type = type { [3 x double] }
+
+define void @getScalarFunc(double* %A, double* %C, %type* %B) #0 {
+; CHECK-LABEL: getScalarFunc
+; This check will catch also the massv version of the function.
+; CHECK-NOT: call fast <{{[0-9]+}} x double> @{{.*}}atan{{.*}}(<{{[0-9]+}} x double> %{{[0-9]+}})
+entry:
+  br label %for.body
+
+for.body: 
+  %i = phi i64 [ %inc, %for.body ], [ 0, %entry ]
+  %dummyload2 = load double, double* %A, align 8
+  %arrayidx.i24 = getelementptr inbounds %type, %type* %B, i64 %i, i32 0, i32 0
+  %_15 = load double, double* %arrayidx.i24, align 8
+  %call10 = tail call fast double @atan(double %_15) #1
+  %inc = add i64 %i, 1
+  %cmp = icmp ugt i64 1000, %inc
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end: 
+  ret void
+}
+
+declare double @atan(double) local_unnamed_addr
+declare <2 x double> @__atand2_massv(<2 x double>) #1
+attributes #0 = { "target-cpu"="pwr9" }
+attributes #1 = { nounwind readnone "vector-function-abi-variant"="_ZGV_LLVM_N2v_atan(__atand2_massv)" }

llvm/unittests/Analysis/VectorUtilsTest.cpp

TEST_F(VFShapeAPITest, API_buildVFShape) {
   Expected = {/*VF*/ 16, /*IsScalable*/ true, /*Parameters*/ {
                   {0, VFParamKind::Vector},
                   {1, VFParamKind::Vector},
                   {2, VFParamKind::Vector},
               }};
   EXPECT_EQ(Shape, Expected);
 }
 
+TEST_F(VFShapeAPITest, API_getScalarShape) {
+  buildShape(/*VF*/ 1, /*IsScalable*/ false, /*HasGlobalPred*/ false);
+  EXPECT_EQ(VFShape::getScalarShape(*CI), Shape);
+}
+
+TEST_F(VFShapeAPITest, API_getVectorizedFunction) {
+  VFShape ScalarShape = VFShape::getScalarShape(*CI);
+  EXPECT_EQ(VFDatabase(*CI).getVectorizedFunction(ScalarShape),
+            M->getFunction("g"));
+
+  buildShape(/*VF*/ 1, /*IsScalable*/ true, /*HasGlobalPred*/ false);
+  EXPECT_EQ(VFDatabase(*CI).getVectorizedFunction(Shape), nullptr);
+  buildShape(/*VF*/ 1, /*IsScalable*/ false, /*HasGlobalPred*/ true);
+  EXPECT_EQ(VFDatabase(*CI).getVectorizedFunction(Shape), nullptr);
+  buildShape(/*VF*/ 1, /*IsScalable*/ true, /*HasGlobalPred*/ true);
+  EXPECT_EQ(VFDatabase(*CI).getVectorizedFunction(Shape), nullptr);
+}
+
 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},