[SLP] Fix order of `insertelement`/`insertvalue` seed operands

[anton-afanasyev]

Summary

This patch takes the indices operands of insertelement/insertvalue
into account while generation of seed elements for findBuildAggregate().
This function has kept the original order of inserts before.
Also this patch optimizes findBuildAggregate() preventing it from
redundant temporary vector allocations and its multiple reversing.

Fixes llvm.org/pr44067

[xbolva00]

Add test?

[anton-afanasyev]

In D83779#2150568, @xbolva00 wrote:

Add test?

Sure, thanks!

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

7078

Why need a parameter here? Why always return 2?

7087–7088

Just return 0;, no need for else

7089–7099

No need for else.

7094

Use actual type and i->I

[ABataev]

In D83779#2150568, @xbolva00 wrote:

Add test?

I assume this is actually NFC, it just tries to optimize the function findBuildAggregate.

[anton-afanasyev]

Update tests

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

7078

Fixed, it was temporary dummy.

7087–7088

Fixed, thanks.

7094

Fixed, thanks.

[anton-afanasyev]

In D83779#2153039, @ABataev wrote:

In D83779#2150568, @xbolva00 wrote:

Add test?

I assume this is actually NFC, it just tries to optimize the function findBuildAggregate.

No, actually it's not NFC (though instcombine has done the same work previously).

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

7084

No need for else here, just unconditional block, since then part is terminated with return

7118

No need for else here

7120

Remove else here

7124

.empty()

7131

Enclose in braces

7322

Very strange check, why we need it? Why did you change the previous one?

7337

Same question here

llvm/test/Transforms/SLPVectorizer/AArch64/gather-root.ll

206–209 ↗

(On Diff #278479)

A regression?

[ABataev]

llvm/test/Transforms/SLPVectorizer/X86/alternate-cast.ll

293–296 ↗

(On Diff #278479)

Regression?

llvm/test/Transforms/SLPVectorizer/X86/insert-element-build-vector.ll

129–134 ↗

(On Diff #278479)

Regression?

[anton-afanasyev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

7084

Thanks, fixed

7118

Fixed

7120

Removed

7124

Changed

7131

Enclosed

7322

The way the findBuildAggregate() works has changed: it outputs vector of Values, ordered by inserts indices, so it possible this vector contains gaps. But I've changed findBuildAggregate() again, splitting it to recursive and non-recursive parts, and making this check inside the latter one.

llvm/test/Transforms/SLPVectorizer/AArch64/gather-root.ll

206–209 ↗

(On Diff #278479)

Fixed by allowing to findBuildAggregate() support of partial vector filling.

llvm/test/Transforms/SLPVectorizer/X86/alternate-cast.ll

293–296 ↗

(On Diff #278479)

Fixed

llvm/test/Transforms/SLPVectorizer/X86/insert-element-build-vector.ll

129–134 ↗

(On Diff #278479)

Yes, that's regression, but that's pay for the optimization by reducing shufflevectors at the more common cases.

[anton-afanasyev]

Update. Splitted findBuildAggregate() to recursive and non-recursive parts.

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

7083

returns true for the function, that shall return unsigned

7091

Type *

7115

Just cast

7132

What about VectorType here if it is allowed in the previous function?

7152

cast<Instruction>

7155–7158

No need for else here

7162–7165

Better to transform it a condition of the loop and return false after the end of the loop

7163–7171

Just llvm::erase_value(<container>, nullptr)

7174–7175

Tabs

7318

Why you don't need this?

[anton-afanasyev]

Addressed @ABataev's comments.

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

7083

Thanks, I've forgotten to change return type.

7091

Fixed

7115

Fixed

7132

No need to do this: insertvalue's indices can never point to vector elements, only to structure and array ones. Function getAggregateSize() doesn's use InsertValueInst::indices() and computes aggregate size by getNumElements() multiplication, whereas getOperandIndex() just returns insertvalue's operand offset. The vector can be addressed by insertvalue only as final atomic element of structure. Function findBuildAggregate_rec() processes this element separately using OperandIndex as base offset.

7152

Fixed

7155–7158

No, this else matters here: it embraces the block which is executed only if InsertedOperand is not insert. There is the second nested if inside the first one.

7162–7165

Transformed.

7163–7171

Thanks, changed. Used llvm::erase_if(<container>, <predicate>), didn't found llvm::erase_value().

7174–7175

Hmm, that's actually spaces, not tabs.

7318

This is checked inside findBuildAggregate() itself now.

[anton-afanasyev]

Updated

[anton-afanasyev]

Ping. Rebase.

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

7078

Maybe better to return Optional<unsigned> here rather than return bool and have AggregateSize return param/

7110–7111

Same, Optional<unsigned>

[anton-afanasyev]

Addressed comments

[anton-afanasyev]

Fixed

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

7078

Sounds good, fixed

7110–7111

Ok, done

[RKSimon]

A couple of minor style comments - trivial scope reductions

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

7081

if (auto *IE = dyn_cast<InsertElementInst>(InsertInst))

7085

unsigned AggregateSize = 1;

7112

if (auto *IE = dyn_cast<InsertElementInst>(InsertInst))

[anton-afanasyev]

Addressed

[anton-afanasyev]

Fixed

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

7081

Sure, fixed.

7085

Fixed.

7112

Fixed.

[RKSimon]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

7080

VectorType::getNumElements() will be going away soon - you need to replace this with cast<FixedVectorType>(IE->getType())->getNumElements()

7095

dyn_cast<FixedVectorType>

7111

cast<FixedVectorType>(IE->getType())

[anton-afanasyev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

7080

Replaced

7095

Fixed

7111

Fixed

[anton-afanasyev]

Addressed comments

[RKSimon]

Thanks, no more comments from me - the reverse_hadd_v4f32 fix will be very useful to x86 backend hadd formation!

@ABataev any more comments?

[ABataev]

llvm/test/Transforms/SLPVectorizer/X86/alternate-int.ll

428–431 ↗

(On Diff #283613)

This change also does not look like caused by the patch

llvm/test/Transforms/SLPVectorizer/X86/load-merge.ll

59 ↗

(On Diff #283613)

Drop this change or commit it separately as NFC.

[RKSimon]

llvm/test/Transforms/SLPVectorizer/X86/alternate-int.ll

428–431 ↗

(On Diff #283613)

Should be fixed in rG3b93464dcf2f4bcaa4a8fe3d888fee027aa2100b

[anton-afanasyev]

llvm/test/Transforms/SLPVectorizer/X86/alternate-int.ll

428–431 ↗

(On Diff #283613)

Thanks, dropped this change.

llvm/test/Transforms/SLPVectorizer/X86/load-merge.ll

59 ↗

(On Diff #283613)

Dropped.

[anton-afanasyev]

Addressed comments

[ABataev]

LG

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

 //===- SLPVectorizer.cpp - A bottom up SLP Vectorizer ---------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
 // This pass implements the Bottom Up SLP vectorizer. It detects consecutive
Value *emitReduction(Value *VectorizedValue, IRBuilder<> &Builder,
 
     // The result is in the first element of the vector.
     return Builder.CreateExtractElement(TmpVec, Builder.getInt32(0));
   }
 };
 
 } // end anonymous namespace
 
+static unsigned int getAggregateSize(Instruction *InsertInst) {
+  return 2;
+}
+
+static unsigned int getOperandIndex(Instruction *InsertInst) {
+  auto *IE = dyn_cast<InsertElementInst>(InsertInst);
+  if (IE) {
+    if (auto *CI = dyn_cast<ConstantInt>(IE->getOperand(2)))
+      return CI->getZExtValue();
+    else
+      return 0;
+  } else {
+    auto *IV = cast<InsertValueInst>(InsertInst);
+    Type *AggregateType = cast<StructType>(InsertInst->getType());
+    unsigned int OperandIndex = 0;
+    Type *CurrentType = IV->getType();
+    for (auto i : IV->indices()) {
+      AggregateType->getElementType(i);
+      OperandIndex += i;
+    }
+    return OperandIndex;
+  }
+}
+
 /// Recognize construction of vectors like
 ///  %ra = insertelement <4 x float> undef, float %s0, i32 0
 ///  %rb = insertelement <4 x float> %ra, float %s1, i32 1
 ///  %rc = insertelement <4 x float> %rb, float %s2, i32 2
 ///  %rd = insertelement <4 x float> %rc, float %s3, i32 3
 ///  starting from the last insertelement or insertvalue instruction.
 ///
-/// Also recognize aggregates like {<2 x float>, <2 x float>},
+/// Also recognize homogeneous aggregates like {<2 x float>, <2 x float>},
 /// {{float, float}, {float, float}}, [2 x {float, float}] and so on.
 /// See llvm/test/Transforms/SLPVectorizer/X86/pr42022.ll for examples.
 ///
 /// Assume LastInsertInst is of InsertElementInst or InsertValueInst type.
 ///
 /// \return true if it matches.
-static bool findBuildAggregate(Value *LastInsertInst, TargetTransformInfo *TTI,
+static bool findBuildAggregate(Instruction *LastInsertInst,
+                               TargetTransformInfo *TTI,
                                SmallVectorImpl<Value *> &BuildVectorOpds,
                                SmallVectorImpl<Value *> &InsertElts) {
   assert((isa<InsertElementInst>(LastInsertInst) ||
           isa<InsertValueInst>(LastInsertInst)) &&
          "Expected insertelement or insertvalue instruction!");
-  do {
-    Value *InsertedOperand;
-    auto *IE = dyn_cast<InsertElementInst>(LastInsertInst);
-    if (IE) {
-      InsertedOperand = IE->getOperand(1);
-      LastInsertInst = IE->getOperand(0);
-    } else {
-      auto *IV = cast<InsertValueInst>(LastInsertInst);
-      InsertedOperand = IV->getInsertedValueOperand();
-      LastInsertInst = IV->getAggregateOperand();
-    }
+  unsigned int aggregateSize = getAggregateSize(LastInsertInst);
+  // TODO: "!= 0" to prevent aggregate size computing?
+  if (BuildVectorOpds.size() != aggregateSize) {
+    BuildVectorOpds.resize(aggregateSize);
+    InsertElts.resize(aggregateSize);
+
+  do {
+    Value *InsertedOperand = LastInsertInst->getOperand(1);
+    unsigned int OperandIndex = getOperandIndex(LastInsertInst);
     if (isa<InsertElementInst>(InsertedOperand) ||
         isa<InsertValueInst>(InsertedOperand)) {
-      SmallVector<Value *, 8> TmpBuildVectorOpds;
-      SmallVector<Value *, 8> TmpInsertElts;
-      if (!findBuildAggregate(InsertedOperand, TTI, TmpBuildVectorOpds,
-                              TmpInsertElts))
-        return false;
-      BuildVectorOpds.append(TmpBuildVectorOpds.rbegin(),
-                             TmpBuildVectorOpds.rend());
-      InsertElts.append(TmpInsertElts.rbegin(), TmpInsertElts.rend());
+      if (!findBuildAggregate(dyn_cast<Instruction>(InsertedOperand), TTI,
+                              BuildVectorOpds, InsertElts))
+        return false;
     } else {
-      BuildVectorOpds.push_back(InsertedOperand);
-      InsertElts.push_back(IE);
+      BuildVectorOpds[OperandIndex] = InsertedOperand;
+      InsertElts[OperandIndex] = LastInsertInst;
     }
-    if (isa<UndefValue>(LastInsertInst))
+    if (isa<UndefValue>(LastInsertInst->getOperand(0)))
       break;
+    LastInsertInst = dyn_cast<Instruction>(LastInsertInst->getOperand(0));
     if ((!isa<InsertValueInst>(LastInsertInst) &&
          !isa<InsertElementInst>(LastInsertInst)) ||
         !LastInsertInst->hasOneUse())
       return false;
   } while (true);
-  std::reverse(BuildVectorOpds.begin(), BuildVectorOpds.end());
-  std::reverse(InsertElts.begin(), InsertElts.end());
   return true;
 }
 
 static bool PhiTypeSorterFunc(Value *V, Value *V2) {
   return V->getType() < V2->getType();
 }
 
 /// Try and get a reduction value from a phi node.
 ///
 /// Given a phi node \p P in a block \p ParentBB, consider possible reductions
 /// if they come from either \p ParentBB or a containing loop latch.
 ///
 /// \returns A candidate reduction value if possible, or \code nullptr \endcode
 /// if not possible.
 static Value *getReductionValue(const DominatorTree *DT, PHINode *P,
                                 BasicBlock *ParentBB, LoopInfo *LI) {
   // There are situations where the reduction value is not dominated by the
   // reduction phi. Vectorizing such cases has been reported to cause
   // miscompiles. See PR25787.
   auto DominatedReduxValue = [&](Value *R) {
     return isa<Instruction>(R) &&
            DT->dominates(P->getParent(), cast<Instruction>(R)->getParent());
   };
 
   Value *Rdx = nullptr;
 
   // Return the incoming value if it comes from the same BB as the phi node.
   if (P->getIncomingBlock(0) == ParentBB) {
     Rdx = P->getIncomingValue(0);
   } else if (P->getIncomingBlock(1) == ParentBB) {
     Rdx = P->getIncomingValue(1);
   }
 
   if (Rdx && DominatedReduxValue(Rdx))
bool SLPVectorizerPass::vectorizeInsertValueInst(InsertValueInst *IVI,
   const DataLayout &DL = BB->getModule()->getDataLayout();
   if (!R.canMapToVector(IVI->getType(), DL))
     return false;
 
   SmallVector<Value *, 16> BuildVectorOpds;
   SmallVector<Value *, 16> BuildVectorInsts;
   if (!findBuildAggregate(IVI, TTI, BuildVectorOpds, BuildVectorInsts) ||
       BuildVectorOpds.size() < 2)
     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, /*AllowReorder=*/false,
                             BuildVectorInsts);
 }
 
 bool SLPVectorizerPass::vectorizeInsertElementInst(InsertElementInst *IEI,
                                                    BasicBlock *BB, BoUpSLP &R) {
   SmallVector<Value *, 16> BuildVectorInsts;
   SmallVector<Value *, 16> BuildVectorOpds;
   if (!findBuildAggregate(IEI, TTI, BuildVectorOpds, BuildVectorInsts) ||
       BuildVectorOpds.size() < 2 ||
       (llvm::all_of(BuildVectorOpds,
                     [](Value *V) { return isa<ExtractElementInst>(V); }) &&
        isShuffle(BuildVectorOpds)))
     return false;
 
   // Vectorize starting with the build vector operands ignoring the BuildVector
   // instructions for the purpose of scheduling and user extraction.
   return tryToVectorizeList(BuildVectorOpds, R, /*AllowReorder=*/false,
                             BuildVectorInsts);