[SLPVectorizer] Don't ignore scalar extraction instructions of aggregate value

[Carrot]

Summary

For code like

struct S {

void* p;
void* q;

};

static S kS0;

S getS() {

return kS0;

}

LLVM generate following instructions for ppc

lxvx 0, 0, 3
mfvsrld 3, 0
mfvsrd 4, 0

Ideal result should be just

ld 3, 0(4)
ld 4, 8(4)

The problem is in SLPVectorizer, the vector build instructions (insertvalue for aggregate type) is passed to BoUpSLP.buildTree, it is treated as UserIgnoreList, so later in cost estimation, the cost of these instructions are not counted.
For aggregate value, later usage are more likely to be done in integer registers, either used as individual scalars or used as a whole for function call or return value. So for vectorization of aggregate value, the scalar extraction instructions are required in cost estimation.

[hfinkel]

The current code generation is also odd on x86 (for the same reason). Returning the aggregate forces the values to be placed in specific GPRs. That makes the vectorization not worthwhile. Can you please also add this test into the X86 directory (running for x86, obviously) as well?

There might be cases where this is not the right thing to do, but nothing comes to mind at the moment. LGTM.

lib/Transforms/Vectorize/SLPVectorizer.cpp

5715

I'd say "scalar registers" instead of "integer registers" (they might, for example, be floating-point registers).

[Carrot]

Will check in this patch with a new test case for x86.

include/llvm/Transforms/Vectorize/SLPVectorizer.h

private:
   ///       every time we run into a memory barrier.
   void collectSeedInstructions(BasicBlock *BB);
 
   /// \brief Try to vectorize a chain that starts at two arithmetic instrs.
   bool tryToVectorizePair(Value *A, Value *B, slpvectorizer::BoUpSLP &R);
 
   /// \brief Try to vectorize a list of operands.
   /// \@param BuildVector A list of users to ignore for the purpose of
-  ///                     scheduling and that don't need extracting.
+  ///                     scheduling and cost estimation when NeedExtraction
+  ///                     is false.
   /// \returns true if a value was vectorized.
   bool tryToVectorizeList(ArrayRef<Value *> VL, slpvectorizer::BoUpSLP &R,
                           ArrayRef<Value *> BuildVector = None,
-                          bool AllowReorder = false);
+                          bool AllowReorder = false,
+                          bool NeedExtraction = false);
 
   /// \brief Try to vectorize a chain that may start at the operands of \p I.
   bool tryToVectorize(Instruction *I, slpvectorizer::BoUpSLP &R);
 
   /// \brief Vectorize the store instructions collected in Stores.
   bool vectorizeStoreChains(slpvectorizer::BoUpSLP &R);
 
   /// \brief Vectorize the index computations of the getelementptr instructions

lib/Transforms/Vectorize/SLPVectorizer.cpp

bool SLPVectorizerPass::tryToVectorizePair(Value *A, Value *B, BoUpSLP &R) {
   if (!A || !B)
     return false;
   Value *VL[] = { A, B };
   return tryToVectorizeList(VL, R, None, true);
 }
 
 bool SLPVectorizerPass::tryToVectorizeList(ArrayRef<Value *> VL, BoUpSLP &R,
                                            ArrayRef<Value *> BuildVector,
-                                           bool AllowReorder) {
+                                           bool AllowReorder,
+                                           bool NeedExtraction) {
   if (VL.size() < 2)
     return false;
 
   DEBUG(dbgs() << "SLP: Trying to vectorize a list of length = " << VL.size()
                << ".\n");
 
   // Check that all of the parts are scalar instructions of the same type.
   Instruction *I0 = dyn_cast<Instruction>(VL[0]);
for (unsigned I = NextInst; I < MaxInst; ++I) {
       // Check that a previous iteration of this loop did not delete the Value.
       if (hasValueBeenRAUWed(VL, TrackValues, I, OpsWidth))
         continue;
 
       DEBUG(dbgs() << "SLP: Analyzing " << OpsWidth << " operations "
                    << "\n");
       ArrayRef<Value *> Ops = VL.slice(I, OpsWidth);
 
+      ArrayRef<Value *> EmptyArray;
       ArrayRef<Value *> BuildVectorSlice;
       if (!BuildVector.empty())
         BuildVectorSlice = BuildVector.slice(I, OpsWidth);
 
-      R.buildTree(Ops, BuildVectorSlice);
+      R.buildTree(Ops, NeedExtraction ? EmptyArray : BuildVectorSlice);
       // TODO: check if we can allow reordering for more cases.
       if (AllowReorder && R.shouldReorder()) {
         // Conceptually, there is nothing actually preventing us from trying to
         // reorder a larger list. In fact, we do exactly this when vectorizing
         // reductions. However, at this point, we only expect to get here when
         // there are exactly two operations.
         assert(Ops.size() == 2);
         assert(BuildVectorSlice.empty());
if (!R.canMapToVector(IVI->getType(), DL))
     return false;
 
   SmallVector<Value *, 16> BuildVector;
   SmallVector<Value *, 16> BuildVectorOpds;
   if (!findBuildAggregate(IVI, BuildVector, BuildVectorOpds))
     return false;
 
   DEBUG(dbgs() << "SLP: array mappable to vector: " << *IVI << "\n");
-  return tryToVectorizeList(BuildVectorOpds, R, BuildVector, false);
+  // 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, BuildVector, false, true);
 }
 
 bool SLPVectorizerPass::vectorizeInsertElementInst(InsertElementInst *IEI,
                                                    BasicBlock *BB, BoUpSLP &R) {
   SmallVector<Value *, 16> BuildVector;
   SmallVector<Value *, 16> BuildVectorOpds;
   if (!findBuildVector(IEI, BuildVector, BuildVectorOpds))
     return false;

test/Transforms/SLPVectorizer/PowerPC/aggregate.ll

+; RUN: opt -S -mtriple=powerpc64-linux-gnu -mcpu=pwr9 -mattr=+vsx -slp-vectorizer < %s | FileCheck %s
+
+%struct.S = type { i8*, i8* }
+
+@kS0 = common global %struct.S zeroinitializer, align 8
+
+define { i64, i64 } @getS() {
+entry:
+  %0 = load i64, i64* bitcast (%struct.S* @kS0 to i64*), align 8
+  %1 = load i64, i64* bitcast (i8** getelementptr inbounds (%struct.S, %struct.S* @kS0, i64 0, i32 1) to i64*), align 8
+  %2 = insertvalue { i64, i64 } undef, i64 %0, 0
+  %3 = insertvalue { i64, i64 } %2, i64 %1, 1
+  ret { i64, i64 } %3
+}
+
+; CHECK: load i64
+; CHECK-NOT: load <2 x i64>
+; CHECK-NOT: extractelement
+

test/Transforms/SLPVectorizer/X86/aggregate.ll

+; RUN: opt -S -mtriple=x86_64-unknown-linux -mcpu=corei7 -slp-vectorizer < %s | FileCheck %s
+
+%struct.S = type { i8*, i8* }
+
+@kS0 = common global %struct.S zeroinitializer, align 8
+
+define { i64, i64 } @getS() {
+entry:
+  %0 = load i64, i64* bitcast (%struct.S* @kS0 to i64*), align 8
+  %1 = load i64, i64* bitcast (i8** getelementptr inbounds (%struct.S, %struct.S* @kS0, i64 0, i32 1) to i64*), align 8
+  %2 = insertvalue { i64, i64 } undef, i64 %0, 0
+  %3 = insertvalue { i64, i64 } %2, i64 %1, 1
+  ret { i64, i64 } %3
+}
+
+; CHECK: load i64
+; CHECK-NOT: load <2 x i64>
+; CHECK-NOT: extractelement
+