[SLP]Merge reorder and reuse shuffles.

[ABataev]

Summary

It is possible to merge reuse and reorder shuffles and reduce the total
cost of the ivectorization tree/number of final instructions.

[anton-afanasyev]

The same work will be done by instcombine, so we can just zero redundant cost here to gain the same effect globally. But it makes sense to make shuffle merging at the vectorization stage as well, of course.

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

3510

3513

Here += looks confusing, we can just set DeadCost = ..., since DeadCost == 0.

4348

This doesn't change anything but it looks preferable for IsFinalized to be true after finalization even for empty Mask.

4634

Why do we ignore ReuseShuffleIndices here?

[RKSimon]

llvm/test/Transforms/SLPVectorizer/AArch64/PR38339.ll

12

These align changes look like they should already be there - regenerate the base test file and then rebase?

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

3510

I don't get it. What do you want to see here?

3513

No, DeadCost is not 0, it is ReuseShuffleCost

4634

Because stores do not have uses, so this is actually just a dead code.

[ABataev]

Updated and rebased

[anton-afanasyev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

3510

I suggest to join code below (starting from if (!NeedToShuffleReuses && !E->ReorderIndices.empty())) to this if-block:

if (NeedToShuffleReuses) {
  ...
  DeadCost = ReuseShuffleCost;
} else if (!E->ReorderIndices.empty()) {
  DeadCost = TTI->getShuffleCost(TargetTransformInfo::SK_PermuteSingleSrc, VecTy);
}

3513

If NeedToShuffleReuses == false then ReuseShuffleCost == 0, so DeadCost == 0.

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

3510

Ok, I see

[ABataev]

Address comments

[anton-afanasyev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

3513

So, you still can set DeadCost = ... instead of +=. It's simpler and points that we can get starting cost either from shuffle reuse, or from reorder indices, not both.

[ABataev]

Replaced += with just =

[anton-afanasyev]

Looks good to me, just one style remark: we have newlines between function members for all classes throughout this module, so I'd prefer to see the same for ShuffleInstructionBuilder class.

[rupprecht]

I think I'm seeing a miscompile as a result of the patch. The issue is not the transformation itself, but a dependent instruction is reading the wrong value.

Before this patch, we have this:

  %171 = load <2 x i32>, <2 x i32>* %114, align 8
  %reorder_shuffle = shufflevector <2 x i32> %171, <2 x i32> undef, <2 x i32> <i32 1, i32 0>
  %shuffle = shufflevector <2 x i32> %reorder_shuffle, <2 x i32> undef, <4 x i32> <i32 0, i32 1, i32 0, i32 1>
...
  %186 = add nsw <2 x i32> %reorder_shuffle, <i32 -1, i32 -1>

After this patch the same snippet looks like:

  %171 = load <2 x i32>, <2 x i32>* %114, align 8
  %shuffle = shufflevector <2 x i32> %171, <2 x i32> undef, <4 x i32> <i32 1, i32 0, i32 1, i32 0>
...
  %186 = add nsw <2 x i32> %171, <i32 -1, i32 -1>

IIUC, if we suppose %171 loads the values (a, b), then:

• In the original version, %reorder_shuffle is (b, a), so %186 is (b - 1, a - 1)
• In the modified version, %186 reads directly from %171, so the result is (a - 1, b - 1), which is swapped

Do you know what the issue might be? I'm trying to reduce the test case so I can share more details.

[ABataev]

In D92668#2473257, @rupprecht wrote:

I think I'm seeing a miscompile as a result of the patch. The issue is not the transformation itself, but a dependent instruction is reading the wrong value.

Before this patch, we have this:

  %171 = load <2 x i32>, <2 x i32>* %114, align 8
  %reorder_shuffle = shufflevector <2 x i32> %171, <2 x i32> undef, <2 x i32> <i32 1, i32 0>
  %shuffle = shufflevector <2 x i32> %reorder_shuffle, <2 x i32> undef, <4 x i32> <i32 0, i32 1, i32 0, i32 1>
...
  %186 = add nsw <2 x i32> %reorder_shuffle, <i32 -1, i32 -1>

After this patch the same snippet looks like:

  %171 = load <2 x i32>, <2 x i32>* %114, align 8
  %shuffle = shufflevector <2 x i32> %171, <2 x i32> undef, <4 x i32> <i32 1, i32 0, i32 1, i32 0>
...
  %186 = add nsw <2 x i32> %171, <i32 -1, i32 -1>

IIUC, if we suppose %171 loads the values (a, b), then:

• In the original version, %reorder_shuffle is (b, a), so %186 is (b - 1, a - 1)
• In the modified version, %186 reads directly from %171, so the result is (a - 1, b - 1), which is swapped

Do you know what the issue might be? I'm trying to reduce the test case so I can share more details.

Hi, thanks for report, looks like you're right. I'll fix it.

[rupprecht]

Finally got a reasonably sized reduction. It's probably so long because I'm just using clang to build, and if it gets smaller than clang optimizes too much of it away; if I used opt to control the passes I could probably get it smaller. Anyway, hope this is good enough to demonstrate the issue:

; ModuleID = './repro.ll'
source_filename = "repro.ll"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

%struct.widget = type { %struct.baz }
%struct.baz = type { i32 (...)**, i32, i32, i32, i32, i8* }
%struct.snork = type { i8, i8, i8, i8, i8, i8, i8, i8, i8, i8, i8*, %struct.spam*, i8*, i8* }
%struct.spam = type { i8, i8, i8, i32, i32, i32, i32 }
%struct.zot = type { i8 }
%struct.wombat = type { i8 }

define void @wombat(%struct.widget* %arg) local_unnamed_addr align 32 personality i8* undef {
bb:
  %tmp = alloca float, align 4
  %tmp1 = alloca float, align 4
  %tmp2 = alloca float, align 4
  %tmp3 = alloca float, align 4
  %tmp4 = alloca %struct.snork, align 8
  %tmp7 = getelementptr inbounds %struct.widget, %struct.widget* %arg, i64 0, i32 0, i32 2
  %tmp8 = getelementptr inbounds %struct.widget, %struct.widget* %arg, i64 0, i32 0, i32 1
  %tmp9 = getelementptr inbounds %struct.snork, %struct.snork* %tmp4, i64 0, i32 11
  invoke void bitcast (void ()* @quux to void (%struct.snork*, %struct.zot*)*)(%struct.snork* %tmp4, %struct.zot* null)
          to label %bb11 unwind label %bb47

bb11:                                             ; preds = %bb
  %tmp12 = load i32, i32* %tmp7, align 4
  %tmp13 = load i32, i32* %tmp8, align 8
  invoke void bitcast (void ()* @wobble to void (%struct.wombat*, float*, float*, float*, float*)*)(%struct.wombat* undef, float* %tmp, float* %tmp1, float* %tmp2, float* %tmp3)
          to label %bb14 unwind label %bb47

bb14:                                             ; preds = %bb11
  %tmp15 = load float, float* %tmp, align 4
  %tmp16 = load float, float* %tmp1, align 4
  %tmp17 = load float, float* %tmp2, align 4
  %tmp18 = load float, float* %tmp3, align 4
  %tmp20 = load %struct.spam*, %struct.spam** %tmp9, align 8
  %tmp21 = add nsw i32 %tmp12, -1
  %tmp22 = fptosi float %tmp15 to i32
  %tmp23 = icmp slt i32 %tmp22, 0
  %tmp24 = icmp sgt i32 %tmp12, %tmp22
  %tmp25 = select i1 %tmp24, i32 %tmp22, i32 %tmp21
  %tmp26 = select i1 %tmp23, i32 0, i32 %tmp25
  %tmp27 = getelementptr inbounds %struct.spam, %struct.spam* %tmp20, i64 0, i32 3
  store i32 %tmp26, i32* %tmp27, align 8
  %tmp28 = add nsw i32 %tmp13, -1
  %tmp29 = fptosi float %tmp16 to i32
  %tmp30 = icmp slt i32 %tmp29, 0
  %tmp31 = icmp sgt i32 %tmp13, %tmp29
  %tmp32 = select i1 %tmp31, i32 %tmp29, i32 %tmp28
  %tmp33 = select i1 %tmp30, i32 0, i32 %tmp32
  %tmp34 = getelementptr inbounds %struct.spam, %struct.spam* %tmp20, i64 0, i32 4
  store i32 %tmp33, i32* %tmp34, align 4
  %tmp35 = fptosi float %tmp17 to i32
  %tmp36 = icmp slt i32 %tmp35, 0
  %tmp37 = icmp sgt i32 %tmp12, %tmp35
  %tmp38 = select i1 %tmp37, i32 %tmp35, i32 %tmp21
  %tmp39 = select i1 %tmp36, i32 0, i32 %tmp38
  %tmp40 = getelementptr inbounds %struct.spam, %struct.spam* %tmp20, i64 0, i32 5
  store i32 %tmp39, i32* %tmp40, align 8
  %tmp41 = fptosi float %tmp18 to i32
  %tmp42 = icmp slt i32 %tmp41, 0
  %tmp43 = icmp sgt i32 %tmp13, %tmp41
  %tmp44 = select i1 %tmp43, i32 %tmp41, i32 %tmp28
  %tmp45 = select i1 %tmp42, i32 0, i32 %tmp44
  %tmp46 = getelementptr inbounds %struct.spam, %struct.spam* %tmp20, i64 0, i32 6
  store i32 %tmp45, i32* %tmp46, align 4
  ret void

bb47:                                             ; preds = %bb11, %bb10
  %tmp48 = landingpad { i8*, i32 }
          cleanup
  ret void
}

declare void @quux() unnamed_addr

declare void @wobble() local_unnamed_addr

Building with clang -c repro.ll -O3 -o optimized.ll -fno-discard-value-names -S -emit-llvm, before this patch we had:

  %1 = load <2 x i32>, <2 x i32>* %0, align 8
  %reorder_shuffle = shufflevector <2 x i32> %1, <2 x i32> undef, <2 x i32> <i32 1, i32 0>
...
  %shuffle = shufflevector <2 x i32> %reorder_shuffle, <2 x i32> undef, <4 x i32> <i32 0, i32 1, i32 0, i32 1>
...
  %2 = add nsw <2 x i32> %reorder_shuffle, <i32 -1, i32 -1>

And after, we have:

  %1 = load <2 x i32>, <2 x i32>* %0, align 8
...
  %shuffle = shufflevector <2 x i32> %1, <2 x i32> undef, <4 x i32> <i32 1, i32 0, i32 1, i32 0>
...
  %2 = add nsw <2 x i32> %1, <i32 -1, i32 -1>

As with the previous snippet, the dependency on %reorder_shuffle gets lost.

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

case Instruction::ExtractElement: {
                 cast<ExtractElementInst>(V)->getIndexOperand());
             Idx = IO->getZExtValue();
           } else {
             --Idx;
           }
           ReuseShuffleCost +=
               TTI->getVectorInstrCost(Instruction::ExtractElement, VecTy, Idx);
         }
       }
       int DeadCost = ReuseShuffleCost;
-      if (!E->ReorderIndices.empty()) {
-        // TODO: Merge this shuffle with the ReuseShuffleCost.
+      if (!NeedToShuffleReuses && !E->ReorderIndices.empty())
         DeadCost += TTI->getShuffleCost(
             TargetTransformInfo::SK_PermuteSingleSrc, VecTy);
-      }
       for (unsigned I = 0, E = VL.size(); I < E; ++I) {
         Instruction *EI = cast<Instruction>(VL[I]);
         // If all users are going to be vectorized, instruction can be
         // considered as dead.
         // The same, if have only one user, it will be vectorized for sure.
         if (areAllUsersVectorized(EI)) {
           // Take credit for instruction that will become dead.
           if (EI->hasOneUse()) {
case Instruction::Load: {
         VecLdCost = TTI->getMemoryOpCost(Instruction::Load, VecTy, alignment, 0,
                                          CostKind, VL0);
       } else {
         assert(E->State == TreeEntry::ScatterVectorize && "Unknown EntryState");
         VecLdCost = TTI->getGatherScatterOpCost(
             Instruction::Load, VecTy, cast<LoadInst>(VL0)->getPointerOperand(),
             /*VariableMask=*/false, alignment, CostKind, VL0);
       }
-      if (!E->ReorderIndices.empty()) {
-        // TODO: Merge this shuffle with the ReuseShuffleCost.
+      if (!NeedToShuffleReuses && !E->ReorderIndices.empty())
         VecLdCost += TTI->getShuffleCost(
             TargetTransformInfo::SK_PermuteSingleSrc, VecTy);
-      }
       LLVM_DEBUG(dumpTreeCosts(E, ReuseShuffleCost, VecLdCost, ScalarLdCost));
       return ReuseShuffleCost + VecLdCost - ScalarLdCost;
     }
     case Instruction::Store: {
       // We know that we can merge the stores. Calculate the cost.
       bool IsReorder = !E->ReorderIndices.empty();
       auto *SI =
           cast<StoreInst>(IsReorder ? VL[E->ReorderIndices.front()] : VL0);
       Align Alignment = SI->getAlign();
       int ScalarEltCost =
           TTI->getMemoryOpCost(Instruction::Store, ScalarTy, Alignment, 0,
                                CostKind, VL0);
-      if (NeedToShuffleReuses)
-        ReuseShuffleCost = -(ReuseShuffleNumbers - VL.size()) * ScalarEltCost;
       int ScalarStCost = VecTy->getNumElements() * ScalarEltCost;
       int VecStCost = TTI->getMemoryOpCost(Instruction::Store,
                                            VecTy, Alignment, 0, CostKind, VL0);
-      if (IsReorder) {
-        // TODO: Merge this shuffle with the ReuseShuffleCost.
+      if (IsReorder)
         VecStCost += TTI->getShuffleCost(
             TargetTransformInfo::SK_PermuteSingleSrc, VecTy);
-      }
       LLVM_DEBUG(dumpTreeCosts(E, ReuseShuffleCost, VecStCost, ScalarStCost));
-      return ReuseShuffleCost + VecStCost - ScalarStCost;
+      return VecStCost - ScalarStCost;
     }
     case Instruction::Call: {
       CallInst *CI = cast<CallInst>(VL0);
       Intrinsic::ID ID = getVectorIntrinsicIDForCall(CI, TLI);
 
       // Calculate the cost of the scalar and vector calls.
       IntrinsicCostAttributes CostAttrs(ID, *CI, ElementCount::getFixed(1), 1);
       int ScalarEltCost = TTI->getIntrinsicInstrCost(CostAttrs, CostKind);
if (!ReuseShuffleIndicies.empty()) {
     if (auto *I = dyn_cast<Instruction>(Vec)) {
       GatherSeq.insert(I);
       CSEBlocks.insert(I->getParent());
     }
   }
   return Vec;
 }
 
+namespace {
+/// Merges shuffle masks and emits final shuffle instruction, if required.
+class ShuffleInstructionBuilder {
+  IRBuilderBase &Builder;
+  bool IsFinalized = false;
+  SmallVector<int, 4> Mask;
+
+public:
+  ShuffleInstructionBuilder(IRBuilderBase &Builder) : Builder(Builder) {}
+  /// Adds a mask, inverting it before applying.
+  void addInversedMask(ArrayRef<unsigned> SubMask) {
+    if (SubMask.empty())
+      return;
+    SmallVector<int, 4> NewMask;
+    inversePermutation(SubMask, NewMask);
+    addMask(NewMask);
+  }
+  /// Functions adds masks, merging them into  single one.
+  void addMask(ArrayRef<unsigned> SubMask) {
+    SmallVector<int, 4> NewMask(SubMask.begin(), SubMask.end());
+    addMask(NewMask);
+  }
+  void addMask(ArrayRef<int> SubMask) {
+    if (SubMask.empty())
+      return;
+    if (Mask.empty()) {
+      Mask.append(SubMask.begin(), SubMask.end());
+      return;
+    }
+    SmallVector<int, 4> NewMask(SubMask.size(), SubMask.size());
+    int TermValue = std::min(Mask.size(), SubMask.size());
+    for (int I = 0, E = SubMask.size(); I < E; ++I) {
+      if (SubMask[I] >= TermValue || Mask[SubMask[I]] >= TermValue) {
+        NewMask[I] = E;
+        continue;
+      }
+      NewMask[I] = Mask[SubMask[I]];
+    }
+    Mask.swap(NewMask);
+  }
+  Value *finalize(Value *V) {
+    IsFinalized = true;
+    if (Mask.empty())
+      return V;
+    return Builder.CreateShuffleVector(V, Mask, "shuffle");
+  }
+  ~ShuffleInstructionBuilder() {
+    assert((IsFinalized || Mask.empty()) &&
+           "Must be finalized construction of the shuffles.");
+  }
+};
+} // namespace
+
 Value *BoUpSLP::vectorizeTree(TreeEntry *E) {
   IRBuilder<>::InsertPointGuard Guard(Builder);
 
   if (E->VectorizedValue) {
     LLVM_DEBUG(dbgs() << "SLP: Diamond merged for " << *E->Scalars[0] << ".\n");
     return E->VectorizedValue;
   }
 
+  ShuffleInstructionBuilder ShuffleBuilder(Builder);
   bool NeedToShuffleReuses = !E->ReuseShuffleIndices.empty();
   if (E->State == TreeEntry::NeedToGather) {
     setInsertPointAfterBundle(E);
     Value *Vec = gather(E->Scalars);
     if (NeedToShuffleReuses) {
-      Vec = Builder.CreateShuffleVector(Vec, E->ReuseShuffleIndices, "shuffle");
+      ShuffleBuilder.addMask(E->ReuseShuffleIndices);
+      Vec = ShuffleBuilder.finalize(Vec);
       if (auto *I = dyn_cast<Instruction>(Vec)) {
         GatherSeq.insert(I);
         CSEBlocks.insert(I->getParent());
       }
     }
     E->VectorizedValue = Vec;
     return Vec;
   }
case Instruction::PHI: {
 
       assert(NewPhi->getNumIncomingValues() == PH->getNumIncomingValues() &&
              "Invalid number of incoming values");
       return V;
     }
 
     case Instruction::ExtractElement: {
       Value *V = E->getSingleOperand(0);
-      if (!E->ReorderIndices.empty()) {
-        SmallVector<int, 4> Mask;
-        inversePermutation(E->ReorderIndices, Mask);
-        Builder.SetInsertPoint(VL0);
-        V = Builder.CreateShuffleVector(V, Mask, "reorder_shuffle");
-      }
-      if (NeedToShuffleReuses) {
-        // TODO: Merge this shuffle with the ReorderShuffleMask.
-        if (E->ReorderIndices.empty())
-          Builder.SetInsertPoint(VL0);
-        V = Builder.CreateShuffleVector(V, E->ReuseShuffleIndices, "shuffle");
-      }
+      ShuffleBuilder.addInversedMask(E->ReorderIndices);
+      ShuffleBuilder.addMask(E->ReuseShuffleIndices);
+      V = ShuffleBuilder.finalize(V);
       E->VectorizedValue = V;
       return V;
     }
     case Instruction::ExtractValue: {
       auto *LI = cast<LoadInst>(E->getSingleOperand(0));
       Builder.SetInsertPoint(LI);
       auto *PtrTy = PointerType::get(VecTy, LI->getPointerAddressSpace());
       Value *Ptr = Builder.CreateBitCast(LI->getOperand(0), PtrTy);
       LoadInst *V = Builder.CreateAlignedLoad(VecTy, Ptr, LI->getAlign());
       Value *NewV = propagateMetadata(V, E->Scalars);
-      if (!E->ReorderIndices.empty()) {
-        SmallVector<int, 4> Mask;
-        inversePermutation(E->ReorderIndices, Mask);
-        NewV = Builder.CreateShuffleVector(NewV, Mask, "reorder_shuffle");
-      }
-      if (NeedToShuffleReuses) {
-        // TODO: Merge this shuffle with the ReorderShuffleMask.
-        NewV = Builder.CreateShuffleVector(NewV, E->ReuseShuffleIndices,
-                                           "shuffle");
-      }
+      ShuffleBuilder.addInversedMask(E->ReorderIndices);
+      ShuffleBuilder.addMask(E->ReuseShuffleIndices);
+      NewV = ShuffleBuilder.finalize(NewV);
       E->VectorizedValue = NewV;
       return NewV;
     }
     case Instruction::ZExt:
     case Instruction::SExt:
     case Instruction::FPToUI:
     case Instruction::FPToSI:
     case Instruction::FPExt:
case Instruction::BitCast: {
 
       if (E->VectorizedValue) {
         LLVM_DEBUG(dbgs() << "SLP: Diamond merged for " << *VL0 << ".\n");
         return E->VectorizedValue;
       }
 
       auto *CI = cast<CastInst>(VL0);
       Value *V = Builder.CreateCast(CI->getOpcode(), InVec, VecTy);
-      if (NeedToShuffleReuses)
-        V = Builder.CreateShuffleVector(V, E->ReuseShuffleIndices, "shuffle");
+      ShuffleBuilder.addMask(E->ReuseShuffleIndices);
+      V = ShuffleBuilder.finalize(V);
 
       E->VectorizedValue = V;
       ++NumVectorInstructions;
       return V;
     }
     case Instruction::FCmp:
     case Instruction::ICmp: {
       setInsertPointAfterBundle(E);
 
       Value *L = vectorizeTree(E->getOperand(0));
       Value *R = vectorizeTree(E->getOperand(1));
 
       if (E->VectorizedValue) {
         LLVM_DEBUG(dbgs() << "SLP: Diamond merged for " << *VL0 << ".\n");
         return E->VectorizedValue;
       }
 
       CmpInst::Predicate P0 = cast<CmpInst>(VL0)->getPredicate();
       Value *V = Builder.CreateCmp(P0, L, R);
       propagateIRFlags(V, E->Scalars, VL0);
-      if (NeedToShuffleReuses)
-        V = Builder.CreateShuffleVector(V, E->ReuseShuffleIndices, "shuffle");
+      ShuffleBuilder.addMask(E->ReuseShuffleIndices);
+      V = ShuffleBuilder.finalize(V);
 
       E->VectorizedValue = V;
       ++NumVectorInstructions;
       return V;
     }
     case Instruction::Select: {
       setInsertPointAfterBundle(E);
 
       Value *Cond = vectorizeTree(E->getOperand(0));
       Value *True = vectorizeTree(E->getOperand(1));
       Value *False = vectorizeTree(E->getOperand(2));
 
       if (E->VectorizedValue) {
         LLVM_DEBUG(dbgs() << "SLP: Diamond merged for " << *VL0 << ".\n");
         return E->VectorizedValue;
       }
 
       Value *V = Builder.CreateSelect(Cond, True, False);
-      if (NeedToShuffleReuses)
-        V = Builder.CreateShuffleVector(V, E->ReuseShuffleIndices, "shuffle");
+      ShuffleBuilder.addMask(E->ReuseShuffleIndices);
+      V = ShuffleBuilder.finalize(V);
 
       E->VectorizedValue = V;
       ++NumVectorInstructions;
       return V;
     }
     case Instruction::FNeg: {
       setInsertPointAfterBundle(E);
 
       Value *Op = vectorizeTree(E->getOperand(0));
 
       if (E->VectorizedValue) {
         LLVM_DEBUG(dbgs() << "SLP: Diamond merged for " << *VL0 << ".\n");
         return E->VectorizedValue;
       }
 
       Value *V = Builder.CreateUnOp(
           static_cast<Instruction::UnaryOps>(E->getOpcode()), Op);
       propagateIRFlags(V, E->Scalars, VL0);
       if (auto *I = dyn_cast<Instruction>(V))
         V = propagateMetadata(I, E->Scalars);
 
-      if (NeedToShuffleReuses)
-        V = Builder.CreateShuffleVector(V, E->ReuseShuffleIndices, "shuffle");
+      ShuffleBuilder.addMask(E->ReuseShuffleIndices);
+      V = ShuffleBuilder.finalize(V);
 
       E->VectorizedValue = V;
       ++NumVectorInstructions;
 
       return V;
     }
     case Instruction::Add:
     case Instruction::FAdd:
case Instruction::Xor: {
 
       Value *V = Builder.CreateBinOp(
           static_cast<Instruction::BinaryOps>(E->getOpcode()), LHS,
           RHS);
       propagateIRFlags(V, E->Scalars, VL0);
       if (auto *I = dyn_cast<Instruction>(V))
         V = propagateMetadata(I, E->Scalars);
 
-      if (NeedToShuffleReuses)
-        V = Builder.CreateShuffleVector(V, E->ReuseShuffleIndices, "shuffle");
+      ShuffleBuilder.addMask(E->ReuseShuffleIndices);
+      V = ShuffleBuilder.finalize(V);
 
       E->VectorizedValue = V;
       ++NumVectorInstructions;
 
       return V;
     }
     case Instruction::Load: {
       // Loads are inserted at the head of the tree because we don't want to
case Instruction::Load: {
         Align CommonAlignment = LI->getAlign();
         for (Value *V : E->Scalars)
           CommonAlignment =
               commonAlignment(CommonAlignment, cast<LoadInst>(V)->getAlign());
         NewLI = Builder.CreateMaskedGather(VecPtr, CommonAlignment);
       }
       Value *V = propagateMetadata(NewLI, E->Scalars);
 
-      if (IsReorder) {
-        SmallVector<int, 4> Mask;
-        inversePermutation(E->ReorderIndices, Mask);
-        V = Builder.CreateShuffleVector(V, Mask, "reorder_shuffle");
-      }
-      if (NeedToShuffleReuses) {
-        // TODO: Merge this shuffle with the ReorderShuffleMask.
-        V = Builder.CreateShuffleVector(V, E->ReuseShuffleIndices, "shuffle");
-      }
+      ShuffleBuilder.addInversedMask(E->ReorderIndices);
+      ShuffleBuilder.addMask(E->ReuseShuffleIndices);
+      V = ShuffleBuilder.finalize(V);
       E->VectorizedValue = V;
       ++NumVectorInstructions;
       return V;
     }
     case Instruction::Store: {
       bool IsReorder = !E->ReorderIndices.empty();
       auto *SI = cast<StoreInst>(
           IsReorder ? E->Scalars[E->ReorderIndices.front()] : VL0);
       unsigned AS = SI->getPointerAddressSpace();
 
       setInsertPointAfterBundle(E);
 
       Value *VecValue = vectorizeTree(E->getOperand(0));
-      if (IsReorder) {
-        SmallVector<int, 4> Mask(E->ReorderIndices.begin(),
-                                 E->ReorderIndices.end());
-        VecValue = Builder.CreateShuffleVector(VecValue, Mask, "reorder_shuf");
-      }
+      ShuffleBuilder.addMask(E->ReorderIndices);
+      VecValue = ShuffleBuilder.finalize(VecValue);
+
       Value *ScalarPtr = SI->getPointerOperand();
       Value *VecPtr = Builder.CreateBitCast(
           ScalarPtr, VecValue->getType()->getPointerTo(AS));
       StoreInst *ST = Builder.CreateAlignedStore(VecValue, VecPtr,
                                                  SI->getAlign());
 
       // The pointer operand uses an in-tree scalar, so add the new BitCast to
       // ExternalUses to make sure that an extract will be generated in the
       // future.
       if (getTreeEntry(ScalarPtr))
         ExternalUses.push_back(ExternalUser(ScalarPtr, cast<User>(VecPtr), 0));
 
       Value *V = propagateMetadata(ST, E->Scalars);
-      if (NeedToShuffleReuses)
-        V = Builder.CreateShuffleVector(V, E->ReuseShuffleIndices, "shuffle");
 
       E->VectorizedValue = V;
       ++NumVectorInstructions;
       return V;
     }
     case Instruction::GetElementPtr: {
       setInsertPointAfterBundle(E);
 
case Instruction::GetElementPtr: {
         OpVecs.push_back(OpVec);
       }
 
       Value *V = Builder.CreateGEP(
           cast<GetElementPtrInst>(VL0)->getSourceElementType(), Op0, OpVecs);
       if (Instruction *I = dyn_cast<Instruction>(V))
         V = propagateMetadata(I, E->Scalars);
 
-      if (NeedToShuffleReuses)
-        V = Builder.CreateShuffleVector(V, E->ReuseShuffleIndices, "shuffle");
+      ShuffleBuilder.addMask(E->ReuseShuffleIndices);
+      V = ShuffleBuilder.finalize(V);
 
       E->VectorizedValue = V;
       ++NumVectorInstructions;
 
       return V;
     }
     case Instruction::Call: {
       CallInst *CI = cast<CallInst>(VL0);
case Instruction::Call: {
 
       // The scalar argument uses an in-tree scalar so we add the new vectorized
       // call to ExternalUses list to make sure that an extract will be
       // generated in the future.
       if (ScalarArg && getTreeEntry(ScalarArg))
         ExternalUses.push_back(ExternalUser(ScalarArg, cast<User>(V), 0));
 
       propagateIRFlags(V, E->Scalars, VL0);
-      if (NeedToShuffleReuses)
-        V = Builder.CreateShuffleVector(V, E->ReuseShuffleIndices, "shuffle");
+      ShuffleBuilder.addMask(E->ReuseShuffleIndices);
+      V = ShuffleBuilder.finalize(V);
 
       E->VectorizedValue = V;
       ++NumVectorInstructions;
       return V;
     }
     case Instruction::ShuffleVector: {
       assert(E->isAltShuffle() &&
              ((Instruction::isBinaryOp(E->getOpcode()) &&
case Instruction::ShuffleVector: {
       }
 
       propagateIRFlags(V0, OpScalars);
       propagateIRFlags(V1, AltScalars);
 
       Value *V = Builder.CreateShuffleVector(V0, V1, Mask);
       if (Instruction *I = dyn_cast<Instruction>(V))
         V = propagateMetadata(I, E->Scalars);
-      if (NeedToShuffleReuses)
-        V = Builder.CreateShuffleVector(V, E->ReuseShuffleIndices, "shuffle");
+      ShuffleBuilder.addMask(E->ReuseShuffleIndices);
+      V = ShuffleBuilder.finalize(V);
 
       E->VectorizedValue = V;
       ++NumVectorInstructions;
 
       return V;
     }
     default:
     llvm_unreachable("unknown inst");

llvm/test/Transforms/SLPVectorizer/AArch64/PR38339.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -slp-vectorizer -S -mtriple=aarch64-apple-ios -mcpu=cyclone -o - %s | FileCheck %s
 
 define void @f1(<2 x i16> %x, i16* %a) {
 ; CHECK-LABEL: @f1(
 ; CHECK-NEXT:    [[SHUFFLE:%.*]] = shufflevector <2 x i16> [[X:%.*]], <2 x i16> undef, <4 x i32> <i32 0, i32 1, i32 1, i32 0>
 ; CHECK-NEXT:    [[PTR0:%.*]] = getelementptr inbounds [4 x i16], [4 x i16]* undef, i16 0, i16 0
 ; CHECK-NEXT:    [[PTR1:%.*]] = getelementptr inbounds [4 x i16], [4 x i16]* undef, i16 0, i16 1
 ; CHECK-NEXT:    [[PTR2:%.*]] = getelementptr inbounds [4 x i16], [4 x i16]* undef, i16 0, i16 2
 ; CHECK-NEXT:    [[PTR3:%.*]] = getelementptr inbounds [4 x i16], [4 x i16]* undef, i16 0, i16 3
 ; CHECK-NEXT:    [[TMP1:%.*]] = extractelement <4 x i16> [[SHUFFLE]], i32 0
 ; CHECK-NEXT:    store i16 [[TMP1]], i16* [[A:%.*]], align 2
 ; CHECK-NEXT:    [[TMP2:%.*]] = bitcast i16* [[PTR0]] to <4 x i16>*
 ; CHECK-NEXT:    store <4 x i16> [[SHUFFLE]], <4 x i16>* [[TMP2]], align 2
 ; CHECK-NEXT:    ret void
 ;
   %t2 = extractelement <2 x i16> %x, i32 0
   %t3 = extractelement <2 x i16> %x, i32 1
   %ptr0 = getelementptr inbounds [4 x i16], [4 x i16]* undef, i16 0, i16 0
   %ptr1 = getelementptr inbounds [4 x i16], [4 x i16]* undef, i16 0, i16 1

 
 define void @f3(<2 x i16> %x, i16* %a) {
 ; CHECK-LABEL: @f3(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[CONT:%.*]]
 ; CHECK:       cont:
 ; CHECK-NEXT:    [[XX:%.*]] = phi <2 x i16> [ [[X:%.*]], [[ENTRY:%.*]] ], [ undef, [[CONT]] ]
 ; CHECK-NEXT:    [[AA:%.*]] = phi i16* [ [[A:%.*]], [[ENTRY]] ], [ undef, [[CONT]] ]
-; CHECK-NEXT:    [[REORDER_SHUFFLE:%.*]] = shufflevector <2 x i16> [[XX]], <2 x i16> undef, <2 x i32> <i32 1, i32 0>
-; CHECK-NEXT:    [[SHUFFLE:%.*]] = shufflevector <2 x i16> [[REORDER_SHUFFLE]], <2 x i16> undef, <4 x i32> <i32 0, i32 1, i32 1, i32 0>
+; CHECK-NEXT:    [[SHUFFLE:%.*]] = shufflevector <2 x i16> [[XX]], <2 x i16> undef, <4 x i32> <i32 1, i32 0, i32 0, i32 1>
 ; CHECK-NEXT:    [[PTR0:%.*]] = getelementptr inbounds [4 x i16], [4 x i16]* undef, i16 0, i16 0
 ; CHECK-NEXT:    [[PTR1:%.*]] = getelementptr inbounds [4 x i16], [4 x i16]* undef, i16 0, i16 1
 ; CHECK-NEXT:    [[PTR2:%.*]] = getelementptr inbounds [4 x i16], [4 x i16]* undef, i16 0, i16 2
 ; CHECK-NEXT:    [[PTR3:%.*]] = getelementptr inbounds [4 x i16], [4 x i16]* undef, i16 0, i16 3
 ; CHECK-NEXT:    [[TMP0:%.*]] = extractelement <4 x i16> [[SHUFFLE]], i32 0
 ; CHECK-NEXT:    store i16 [[TMP0]], i16* [[A]], align 2
 ; CHECK-NEXT:    [[TMP1:%.*]] = bitcast i16* [[PTR0]] to <4 x i16>*
 ; CHECK-NEXT:    store <4 x i16> [[SHUFFLE]], <4 x i16>* [[TMP1]], align 2

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

;
   ret void
 }
 
 define void @i64_simplifiedi_reversed(i64* noalias %st, i64* noalias %ld) {
 ; CHECK-LABEL: @i64_simplifiedi_reversed(
 ; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds i64, i64* [[LD:%.*]], i64 1
 ; CHECK-NEXT:    [[TMP1:%.*]] = bitcast i64* [[LD]] to <2 x i64>*
 ; CHECK-NEXT:    [[TMP2:%.*]] = load <2 x i64>, <2 x i64>* [[TMP1]], align 8
-; CHECK-NEXT:    [[TMP3:%.*]] = shufflevector <2 x i64> [[TMP2]], <2 x i64> undef, <2 x i32> <i32 1, i32 0>
-; CHECK-NEXT:    [[SHUFFLE:%.*]] = shufflevector <2 x i64> [[TMP3]], <2 x i64> undef, <4 x i32> <i32 0, i32 1, i32 0, i32 1>
+; CHECK-NEXT:    [[SHUFFLE:%.*]] = shufflevector <2 x i64> [[TMP2]], <2 x i64> undef, <4 x i32> <i32 1, i32 0, i32 1, i32 0>
 ; CHECK-NEXT:    [[ARRAYIDX3:%.*]] = getelementptr inbounds i64, i64* [[ST:%.*]], i64 1
 ; CHECK-NEXT:    [[ARRAYIDX4:%.*]] = getelementptr inbounds i64, i64* [[ST]], i64 2
 ; CHECK-NEXT:    [[ARRAYIDX5:%.*]] = getelementptr inbounds i64, i64* [[ST]], i64 3
-; CHECK-NEXT:    [[TMP4:%.*]] = bitcast i64* [[ST]] to <4 x i64>*
-; CHECK-NEXT:    store <4 x i64> [[SHUFFLE]], <4 x i64>* [[TMP4]], align 8
+; CHECK-NEXT:    [[TMP3:%.*]] = bitcast i64* [[ST]] to <4 x i64>*
+; CHECK-NEXT:    store <4 x i64> [[SHUFFLE]], <4 x i64>* [[TMP3]], align 8
 ; CHECK-NEXT:    ret void
 ;
   %arrayidx1 = getelementptr inbounds i64, i64* %ld, i64 1
 
   %t0 = load i64, i64* %ld, align 8
   %t1 = load i64, i64* %arrayidx1, align 8
 
   %arrayidx3 = getelementptr inbounds i64, i64* %st, i64 1