[SLP] Enhance SLPVectorizer to vectorize vector aggregate

[anton-afanasyev]

Summary

Vector aggregate is homogeneous aggregate of vectors like { <2 x float>, <2 x float> }.
This patch allows findBuildAggregate() to consider vector aggregates as
well as scalar ones. For instance, { <2 x float>, <2 x float> } maps to <4 x float>.

Fixes vector part of llvm.org/PR42022

[anton-afanasyev]

Oops, missed regression test, I'm to add it.

[anton-afanasyev]

Add test

[anton-afanasyev]

Update summary

[RKSimon]

llvm/test/Transforms/SLPVectorizer/X86/pr42022.ll

4

Regenerate with update_test_checks.py ?

[anton-afanasyev]

llvm/test/Transforms/SLPVectorizer/X86/pr42022.ll

4

Should it really be autogenerated? I don't like test autogeneration for excessiveness and false positives while testing. Here we just checking vector <4 x float> is generated. Is autogeneration really standard for tests now?

[dtemirbulatov]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

6769

Maybe here we could try other sizes here, for example, 8?

[anton-afanasyev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

6769

Are you talking about number 4 in SmallVector<Value*, 4>? It is just default size preallocated for vector, it could be potentially resized by push_back() below. But I believe it won't for most cases.

[anton-afanasyev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

6769

*default capacity

[dtemirbulatov]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

6769

yes, correct

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2879–2880

Why do we have this check?

2879–2880

Also, would be good to have a test for this if we don't have it yet.

6762

Not formatted

6772–6774

Just BuildVectorOpds.append(TmpBuildVectorOpds.rbegin(), TmpBuildVectorOpds.rend());

llvm/test/Transforms/SLPVectorizer/X86/pr42022.ll

4

It is common practice to use auto checks and demonstrate the difference then.

[RKSimon]

llvm/test/Transforms/SLPVectorizer/X86/pr42022.ll

4

update_test_checks.py helps us identify any hidden regressions

also you can probably remove the dso_local and local_unnamed_addr #0 tags

[anton-afanasyev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2879–2880

Hmm, you're right, I'm just to delete this check. I haven't faced any issue concerning scalability, but decided to check it just in case ({ <vscale x 2 x float>, <vscale x 2 x float> } is not isomorphic to <4 x float>?). But I see no similar check across SLPVectorizer.cpp, so I'm to delete this check.

6762

Thanks, fixed with clang-format.

6772–6774

Sure, thanks!

llvm/test/Transforms/SLPVectorizer/X86/pr42022.ll

4

Ok, thank, I'm to fix it.

[anton-afanasyev]

Update

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2879–2880

My question was different. I just wanted some explanation what's the problem with the scalable vectors? If the check is required we must have it. Also, still, would be good to have a test for this situation.

[anton-afanasyev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2879–2880

I wasn't familiar with vscale property, but learned it now. That check was actually unnecessary: { <vscale x N x Ty>, <vscale x N x Ty> } maps to <vscale x 2N x Ty>, so we can deal with this scalability set to true.

[RKSimon]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2879–2880

Probably worth adding at least some test coverage for this - in aarch64 maybe?

[anton-afanasyev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2879–2880

Actually vscale property cannot be set to true for such cases.
The structure like { <vscale x 2 x float> } is forbidden, I've got error: invalid element type for struct trying to opt this.

2879–2880

What do you mean by test coverage here? I can copy the same pr42022.ll to llvm/test/Transforms/SLPVectorizer/AArch64, but the only difference will be -mtriple= option.
If you are talking about original issue (pointed here https://llvm.org/pr42022), for aarch64 the vectorization is done for "Bad" case and is failed for two "Good" case (https://godbolt.org/z/5JEGSm), but the root cause is different ABI of aarch64 compared to x86-64. This patch doesn't change this and doesn't concern this.

[RKSimon]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2879–2880

I was referring to adding vscale tests - but if they can't occur then that's fine.

[vporpo]

I think we cannot handle several similar cases with aggregates inside aggregates (e.g., [2 x {float, float}], {{float, float}, {float, float}}). Perhaps we could address some of these cases too with this patch? Please see the tests below:

; RUN: opt -slp-vectorizer -S -mtriple=x86_64-unknown-linux-gnu < %s | FileCheck %s                                                                                                                                                                                       

%StructTy = type { float, float}

define [2 x %StructTy] @ArrayOfStruct(float *%Ptr) {
  %GEP0 = getelementptr inbounds float, float* %Ptr, i64 0
  %L0 = load float, float * %GEP0
  %GEP1 = getelementptr inbounds float, float* %Ptr, i64 1
  %L1 = load float, float * %GEP1
  %GEP2 = getelementptr inbounds float, float* %Ptr, i64 2
  %L2 = load float, float * %GEP2
  %GEP3 = getelementptr inbounds float, float* %Ptr, i64 3
  %L3 = load float, float * %GEP3

  %Fadd0 = fadd fast float %L0, 1.1e+01
  %Fadd1 = fadd fast float %L1, 1.2e+01
  %Fadd2 = fadd fast float %L2, 1.3e+01
  %Fadd3 = fadd fast float %L3, 1.4e+01

  %StructIn0 = insertvalue %StructTy undef, float %Fadd0, 0
  %StructIn1 = insertvalue %StructTy %StructIn0, float %Fadd1, 1

  %StructIn2 = insertvalue %StructTy undef, float %Fadd2, 0
  %StructIn3 = insertvalue %StructTy %StructIn2, float %Fadd3, 1

  %Ret0 = insertvalue [2 x %StructTy] undef, %StructTy %StructIn1, 0
  %Ret1 = insertvalue [2 x %StructTy] %Ret0, %StructTy %StructIn3, 1
  ret [2 x %StructTy] %Ret1
}

define {%StructTy, %StructTy} @StructOfStruct(float *%Ptr) {
  %GEP0 = getelementptr inbounds float, float* %Ptr, i64 0
  %L0 = load float, float * %GEP0
  %GEP1 = getelementptr inbounds float, float* %Ptr, i64 1
  %L1 = load float, float * %GEP1
  %GEP2 = getelementptr inbounds float, float* %Ptr, i64 2
  %L2 = load float, float * %GEP2
  %GEP3 = getelementptr inbounds float, float* %Ptr, i64 3
  %L3 = load float, float * %GEP3

  %Fadd0 = fadd fast float %L0, 1.1e+01
  %Fadd1 = fadd fast float %L1, 1.2e+01
  %Fadd2 = fadd fast float %L2, 1.3e+01
  %Fadd3 = fadd fast float %L3, 1.4e+01

  %StructIn0 = insertvalue %StructTy undef, float %Fadd0, 0
  %StructIn1 = insertvalue %StructTy %StructIn0, float %Fadd1, 1

  %StructIn2 = insertvalue %StructTy undef, float %Fadd2, 0
  %StructIn3 = insertvalue %StructTy %StructIn2, float %Fadd3, 1

  %Ret0 = insertvalue {%StructTy, %StructTy} undef, %StructTy %StructIn1, 0
  %Ret1 = insertvalue {%StructTy, %StructTy} %Ret0, %StructTy %StructIn3, 1
  ret {%StructTy, %StructTy} %Ret1
}

[anton-afanasyev]

In D70068#1746753, @vporpo wrote:

I think we cannot handle several similar cases with aggregates inside aggregates (e.g., [2 x {float, float}], {{float, float}, {float, float}}). Perhaps we could address some of these cases too with this patch? Please see the tests below:
...

Good point! I've checked your case {{float, float}, {float, float}} with modified patch and it has been successfully vectorized. But this has required several hacks.
So may be a separate patch is better? One needs modify canMapToVector() and findBuildAggregate() to be recursive, merge findBuildVector() and findBuildAggregate() -- I can send it to review as a following patch, while fixing next, Matrix22 part of https://llvm.org/pr42022 issue.

[vporpo]

Well, ideally we should be able to handle any combination and nesting of scalars, vectors and aggregates in a unified way.
For example:

{float, <2 x float>, float},
{float, float, <2 x float>},
{{float, float}, <4 x float>, <2 x float>},
{{float}, {float}, [2 x float]}, 
{{{float, float}, float}, float}

etc.
This would require some redesign of the code, which is why I think it makes sense to have a single patch for all of them.

But yes, feel free to split them into separate patches.

But could you also add some more tests to show which of these cases this patch is taking care of. For example, I think {<2 x float>, <2 x float>, <4 x float>} or {<2 x float>, float, float} will not work. Here are some examples:

; RUN: opt -slp-vectorizer -S -mtriple=x86_64-unknown-linux-gnu < %s | FileCheck %s  

define { <2 x float>, float, float } @StructOfVectorAndScalars(float *%Ptr) {
  %GEP0 = getelementptr inbounds float, float* %Ptr, i64 0
  %L0 = load float, float * %GEP0
  %GEP1 = getelementptr inbounds float, float* %Ptr, i64 1
  %L1 = load float, float * %GEP1
  %GEP2 = getelementptr inbounds float, float* %Ptr, i64 2
  %L2 = load float, float * %GEP2
  %GEP3 = getelementptr inbounds float, float* %Ptr, i64 3
  %L3 = load float, float * %GEP3

  %VecIn0 = insertelement <2 x float> undef, float %L0, i64 0
  %VecIn1 = insertelement <2 x float> %VecIn0, float %L1, i64 1

  %Ret0 = insertvalue {<2 x float>, float, float} undef, <2 x float> %VecIn1, 0
  %Ret1 = insertvalue {<2 x float>, float, float} %Ret0, float %L2, 1
  %Ret2 = insertvalue {<2 x float>, float, float} %Ret1, float %L3, 1
  ret {<2 x float>, float, float} %Ret1
}

define { <2 x float>, <2 x float>, <4 x float> } @StructOfVectors(float *%Ptr) {
  %GEP0 = getelementptr inbounds float, float* %Ptr, i64 0
  %L0 = load float, float * %GEP0
  %GEP1 = getelementptr inbounds float, float* %Ptr, i64 1
  %L1 = load float, float * %GEP1
  %GEP2 = getelementptr inbounds float, float* %Ptr, i64 2
  %L2 = load float, float * %GEP2
  %GEP3 = getelementptr inbounds float, float* %Ptr, i64 3
  %L3 = load float, float * %GEP3

  %GEP4 = getelementptr inbounds float, float* %Ptr, i64 4
  %L4 = load float, float * %GEP4
  %GEP5 = getelementptr inbounds float, float* %Ptr, i64 5
  %L5 = load float, float * %GEP5
  %GEP6 = getelementptr inbounds float, float* %Ptr, i64 6
  %L6 = load float, float * %GEP6
  %GEP7 = getelementptr inbounds float, float* %Ptr, i64 7
  %L7 = load float, float * %GEP7

  %VecIn0 = insertelement <2 x float> undef, float %L0, i64 0
  %VecIn1 = insertelement <2 x float> %VecIn0, float %L1, i64 1

  %VecIn2 = insertelement <2 x float> undef, float %L2, i64 0
  %VecIn3 = insertelement <2 x float> %VecIn2, float %L3, i64 1

  %VecIn4 = insertelement <4 x float> undef, float %L4, i64 0
  %VecIn5 = insertelement <4 x float> %VecIn4, float %L5, i64 1
  %VecIn6 = insertelement <4 x float> %VecIn5, float %L6, i64 2
  %VecIn7 = insertelement <4 x float> %VecIn6, float %L7, i64 3

  %Ret0 = insertvalue {<2 x float>, <2 x float>, <4 x float>} undef, <2 x float> %VecIn1, 0
  %Ret1 = insertvalue {<2 x float>, <2 x float>, <4 x float>} %Ret0, <2 x float> %VecIn3, 1
  %Ret2 = insertvalue {<2 x float>, <2 x float>, <4 x float>} %Ret1, <4 x float> %VecIn7, 2
  ret {<2 x float>, <2 x float>, <4 x float>} %Ret2
}

llvm/test/Transforms/SLPVectorizer/X86/pr42022.ll

2

Could you replace this test with the smallest test that exposes the issue?
I think something like this should do the job:

; RUN: opt -slp-vectorizer -S -mtriple=x86_64-unknown-linux-gnu < %s | FileCheck %s

; Checks that vector insertvalues into the struct become SLP seeds.
define { <2 x float>, <2 x float> } @StructOfVectors(float *%Ptr) {
  %GEP0 = getelementptr inbounds float, float* %Ptr, i64 0
  %L0 = load float, float * %GEP0
  %GEP1 = getelementptr inbounds float, float* %Ptr, i64 1
  %L1 = load float, float * %GEP1
  %GEP2 = getelementptr inbounds float, float* %Ptr, i64 2
  %L2 = load float, float * %GEP2
  %GEP3 = getelementptr inbounds float, float* %Ptr, i64 3
  %L3 = load float, float * %GEP3

  %VecIn0 = insertelement <2 x float> undef, float %L0, i64 0
  %VecIn1 = insertelement <2 x float> %VecIn0, float %L1, i64 1

  %VecIn2 = insertelement <2 x float> undef, float %L2, i64 0
  %VecIn3 = insertelement <2 x float> %VecIn2, float %L3, i64 1

  %Ret0 = insertvalue {<2 x float>, <2 x float>} undef, <2 x float> %VecIn1, 0
  %Ret1 = insertvalue {<2 x float>, <2 x float>} %Ret0, <2 x float> %VecIn3, 1
  ret {<2 x float>, <2 x float>} %Ret1
}

[anton-afanasyev]

llvm/test/Transforms/SLPVectorizer/X86/pr42022.ll

2

Thanks, I've replaced this with your test!

[anton-afanasyev]

Update test with shorter one

[anton-afanasyev]

In D70068#1748108, @vporpo wrote:

Well, ideally we should be able to handle any combination and nesting of scalars, vectors and aggregates in a unified way.
For example:

{float, <2 x float>, float},
{float, float, <2 x float>},
{{float, float}, <4 x float>, <2 x float>},
{{float}, {float}, [2 x float]}, 
{{{float, float}, float}, float}

etc.
This would require some redesign of the code, which is why I think it makes sense to have a single patch for all of them.

But yes, feel free to split them into separate patches.

Actually I'm not sure vectorizer should support vectorization of _any_ combinations. For instance, does add operation make sense for structure like {float, float, <2 x float>} in real life (dictated by frontend output, mostly from )? I would focus on _homogeneous_ aggregate -- aggregate of equal type elements, including any nesting depth like {{{float, float}, {float, float}},{{float, float}, {float, float}}}.

[anton-afanasyev]

In D70068#1748108, @vporpo wrote:

...
But could you also add some more tests to show which of these cases this patch is taking care of. For example, I think {<2 x float>, <2 x float>, <4 x float>} or {<2 x float>, float, float} will not work. Here are some examples:
...

Yes, thanks, I'm to add two tests for homogeneous and non-homogeneous cases.

[anton-afanasyev]

Added several tests

[anton-afanasyev]

Added test for {{{i16,i16},{i16,i16}},{{i16,i16},{i16,i16}}}.
I'm to process this and other previously added test cases by the following commit.

[anton-afanasyev]

Is it ok to lgtm for now?

[RKSimon]

Please can you pre-commit the tests with current codegen and then rebase to show the diff?

[anton-afanasyev]

Updated test diff against precommitted tests

[anton-afanasyev]

In D70068#1755110, @RKSimon wrote:

Please can you pre-commit the tests with current codegen and then rebase to show the diff?

Ok, done

[anton-afanasyev]

Updated

[anton-afanasyev]

Here is further enhencement considering different combinations of aggregates: https://reviews.llvm.org/D70587

[RKSimon]

LGTM - thanks

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

public:
   }
 
   // \returns minimum vector register size as set by cl::opt.
   unsigned getMinVecRegSize() const {
     return MinVecRegSize;
   }
 
   /// Check if ArrayType or StructType is isomorphic to some VectorType.
+  /// Accepts homogeneous aggregate of vectors like
+  /// { <2 x float>, <2 x float> }
   ///
   /// \returns number of elements in vector if isomorphism exists, 0 otherwise.
   unsigned canMapToVector(Type *T, const DataLayout &DL) const;
 
   /// \returns True if the VectorizableTree is both tiny and not fully
   /// vectorizable. We do not vectorize such trees.
   bool isTreeTinyAndNotFullyVectorizable() const;
 
unsigned BoUpSLP::canMapToVector(Type *T, const DataLayout &DL) const {
   auto *ST = dyn_cast<StructType>(T);
   if (ST) {
     N = ST->getNumElements();
     EltTy = *ST->element_begin();
   } else {
     N = cast<ArrayType>(T)->getNumElements();
     EltTy = cast<ArrayType>(T)->getElementType();
   }
+
+  if (auto *VT = dyn_cast<VectorType>(EltTy)) {
+    if (VT->isScalable())
+      return 0;
+    EltTy = VT->getElementType();
+    N *= VT->getNumElements();
+  }
+
   if (!isValidElementType(EltTy))
     return 0;
   uint64_t VTSize = DL.getTypeStoreSizeInBits(VectorType::get(EltTy, N));
   if (VTSize < MinVecRegSize || VTSize > MaxVecRegSize || VTSize != DL.getTypeStoreSizeInBits(T))
     return 0;
   if (ST) {
     // Check that struct is homogeneous.
     for (const auto *Ty : ST->elements())
-      if (Ty != EltTy)
+      if (Ty != *ST->element_begin())
         return 0;
   }
   return N;
 }
 
 bool BoUpSLP::canReuseExtract(ArrayRef<Value *> VL, Value *OpValue,
                               SmallVectorImpl<unsigned> &CurrentOrder) const {
   Instruction *E0 = cast<Instruction>(OpValue);
do {
     if (!LastInsertElem || !LastInsertElem->hasOneUse())
       return false;
   } while (true);
   std::reverse(BuildVectorOpds.begin(), BuildVectorOpds.end());
   return true;
 }
 
 /// Like findBuildVector, but looks for construction of aggregate.
+/// Accepts homegeneous aggregate of vectors like { <2 x float>, <2 x float> }.
 ///
 /// \return true if it matches.
 static bool findBuildAggregate(InsertValueInst *IV,
-                               SmallVectorImpl<Value *> &BuildVectorOpds) {
+                             TargetTransformInfo *TTI,
+                             SmallVectorImpl<Value *> &BuildVectorOpds,
+                             int &UserCost) {
+  UserCost = 0;
   do {
+    if (auto *IE = dyn_cast<InsertElementInst>(IV->getInsertedValueOperand())) {
+      int TmpUserCost;
+      SmallVector<Value *, 4> TmpBuildVectorOpds;
+      if (!findBuildVector(IE, TTI, TmpBuildVectorOpds, TmpUserCost))
+        return false;
+      for (auto OpdIt = TmpBuildVectorOpds.rbegin();
+           OpdIt != TmpBuildVectorOpds.rend(); OpdIt++)
+        BuildVectorOpds.push_back(*OpdIt);
+      UserCost += TmpUserCost;
+    } else {
       BuildVectorOpds.push_back(IV->getInsertedValueOperand());
+    }
     Value *V = IV->getAggregateOperand();
     if (isa<UndefValue>(V))
       break;
     IV = dyn_cast<InsertValueInst>(V);
     if (!IV || !IV->hasOneUse())
       return false;
   } while (true);
   std::reverse(BuildVectorOpds.begin(), BuildVectorOpds.end());
auto &&ExtraVectorization = [this](Instruction *I, BoUpSLP &R) -> bool {
     return tryToVectorize(I, R);
   };
   return tryToVectorizeHorReductionOrInstOperands(P, I, BB, R, TTI,
                                                   ExtraVectorization);
 }
 
 bool SLPVectorizerPass::vectorizeInsertValueInst(InsertValueInst *IVI,
                                                  BasicBlock *BB, BoUpSLP &R) {
+  int UserCost = 0;
   const DataLayout &DL = BB->getModule()->getDataLayout();
   if (!R.canMapToVector(IVI->getType(), DL))
     return false;
 
   SmallVector<Value *, 16> BuildVectorOpds;
-  if (!findBuildAggregate(IVI, BuildVectorOpds))
+  if (!findBuildAggregate(IVI, TTI, BuildVectorOpds, UserCost))
     return false;
 
   LLVM_DEBUG(dbgs() << "SLP: array mappable to vector: " << *IVI << "\n");
   // Aggregate value is unlikely to be processed in vector register, we need to
   // extract scalars into scalar registers, so NeedExtraction is set true.
-  return tryToVectorizeList(BuildVectorOpds, R);
+  return tryToVectorizeList(BuildVectorOpds, R, UserCost);
 }
 
 bool SLPVectorizerPass::vectorizeInsertElementInst(InsertElementInst *IEI,
                                                    BasicBlock *BB, BoUpSLP &R) {
   int UserCost;
   SmallVector<Value *, 16> BuildVectorOpds;
   if (!findBuildVector(IEI, TTI, BuildVectorOpds, UserCost) ||
       (llvm::all_of(BuildVectorOpds,

llvm/test/Transforms/SLPVectorizer/X86/pr42022.ll

+; RUN: opt -slp-vectorizer -S -mtriple=x86_64-unknown-linux-gnu < %s | FileCheck %s
+; CHECK: fadd <4 x float>
+
+%struct.Vector4 = type { float, float, float, float }
+
+; Function Attrs: norecurse nounwind readonly uwtable
+define dso_local { <2 x float>, <2 x float> } @_Z6AddBadRK7Vector4S1_(%struct.Vector4* nocapture readonly dereferenceable(16) %0, %struct.Vector4* nocapture readonly dereferenceable(16) %1) local_unnamed_addr #0 {
+  %3 = getelementptr inbounds %struct.Vector4, %struct.Vector4* %0, i64 0, i32 0
+  %4 = load float, float* %3, align 4
+  %5 = getelementptr inbounds %struct.Vector4, %struct.Vector4* %1, i64 0, i32 0
+  %6 = load float, float* %5, align 4
+  %7 = fadd float %4, %6
+  %8 = insertelement <2 x float> undef, float %7, i32 0
+  %9 = getelementptr inbounds %struct.Vector4, %struct.Vector4* %0, i64 0, i32 1
+  %10 = load float, float* %9, align 4
+  %11 = getelementptr inbounds %struct.Vector4, %struct.Vector4* %1, i64 0, i32 1
+  %12 = load float, float* %11, align 4
+  %13 = fadd float %10, %12
+  %14 = insertelement <2 x float> %8, float %13, i32 1
+  %15 = getelementptr inbounds %struct.Vector4, %struct.Vector4* %0, i64 0, i32 2
+  %16 = load float, float* %15, align 4
+  %17 = getelementptr inbounds %struct.Vector4, %struct.Vector4* %1, i64 0, i32 2
+  %18 = load float, float* %17, align 4
+  %19 = fadd float %16, %18
+  %20 = insertelement <2 x float> undef, float %19, i32 0
+  %21 = getelementptr inbounds %struct.Vector4, %struct.Vector4* %0, i64 0, i32 3
+  %22 = load float, float* %21, align 4
+  %23 = getelementptr inbounds %struct.Vector4, %struct.Vector4* %1, i64 0, i32 3
+  %24 = load float, float* %23, align 4
+  %25 = fadd float %22, %24
+  %26 = insertelement <2 x float> %20, float %25, i32 1
+  %27 = insertvalue { <2 x float>, <2 x float> } undef, <2 x float> %14, 0
+  %28 = insertvalue { <2 x float>, <2 x float> } %27, <2 x float> %26, 1
+  ret { <2 x float>, <2 x float> } %28
+}