[SLP]Better detection of perfect/shuffles matches for gather nodes.

[ABataev]

Summary

Implemented better scheme for perfect/shuffled matches of the gather
nodes which allows to fix the performance regressions introduced by
earlier patches. Starting detecting matches for broadcast nodes and
extractelement gathering.

[ABataev]

llvm/test/Transforms/SLPVectorizer/X86/blending-shuffle-inseltpoison.ll

25–66

Regression is caused by the incorrect cost model. It returns cost 12 for mul <4 x i8> and it is compensated by the fact that we calculate the cost of gather of extractelement instructions twice (its cost is -3). After this patch we correctly calculate the cost for the gather node only once (-3 for the first gather and 0 for the second one, perfect diamond match). llvm-mca returns the cost of code is 2 or 4 (for normalized mul <16 x i8> it is 4, for the original code it is 2). Need to tweak the cost model.

[echristo]

Given the iterations here I think that it needs a lot of inline documentation for cost model of what you're doing and what it's expecting here.

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

3717

This needs to be documented as to what you're doing and what it means in the code.

3741

Same :)

4550

Please document this :)

[ABataev]

Address comments

[RKSimon]

llvm/test/Transforms/SLPVectorizer/X86/blending-shuffle-inseltpoison.ll

25–66

I'll handle this regression - I'm reviewing the cost tables against llvm-mca reports at the moment.

[RKSimon]

Please can you rebase? The vXi8 MUL costs should be better now

[ABataev]

Rebase

[ABataev]

llvm/test/Transforms/SLPVectorizer/X86/blending-shuffle.ll

113–154

Regressions caused by the incorrect cost of mul <2 x i8>. Per mca tool the cost is 2, cost model reports 3.

[RKSimon]

llvm/test/Transforms/SLPVectorizer/X86/blending-shuffle.ll

113–154

Are we counting the costs of the v4i8 mul twice here?

[ABataev]

llvm/test/Transforms/SLPVectorizer/X86/blending-shuffle.ll

113–154

Yes, but the cost of mul of v2i8. It is extended to mul v4i8 by the instcombine.

[ABataev]

Rebase

[RKSimon]

llvm/test/Transforms/SLPVectorizer/X86/blending-shuffle.ll

113–154

The cost is trickier than that as the costs tables aren't usually cpu specific- the worst case for v2i8 multiply is at least 4, so that's what the cost table reports - incidently, this test is for bdver2 (cost = 3.5),

But tbh, I wouldn't worry too much about this scalarization.

[ABataev]

Rebase

[RKSimon]

LGTM

[nikic]

FYI there seems to be some (but not very large) compile-time impact on ClamAV: https://llvm-compile-time-tracker.com/compare.php?from=e60f147324b64f7740de58e6b936cdc0e26daadd&to=36911971a58d1ba8b15e97790ac816eaadb0603e&stat=instructions

The file with the largest impact is libclamav_htmlnorm.c with 3.4% regression in NewPM-O3 (and 5.6% in NewPM-ReleaseLTO-g). Might be worth taking a look.

[ABataev]

In D102920#2791168, @nikic wrote:

FYI there seems to be some (but not very large) compile-time impact on ClamAV: https://llvm-compile-time-tracker.com/compare.php?from=e60f147324b64f7740de58e6b936cdc0e26daadd&to=36911971a58d1ba8b15e97790ac816eaadb0603e&stat=instructions

The file with the largest impact is libclamav_htmlnorm.c with 3.4% regression in NewPM-O3 (and 5.6% in NewPM-ReleaseLTO-g). Might be worth taking a look.

I'll check if it can be improved, thanks!

[ABataev]

In D102920#2791168, @nikic wrote:

FYI there seems to be some (but not very large) compile-time impact on ClamAV: https://llvm-compile-time-tracker.com/compare.php?from=e60f147324b64f7740de58e6b936cdc0e26daadd&to=36911971a58d1ba8b15e97790ac816eaadb0603e&stat=instructions

The file with the largest impact is libclamav_htmlnorm.c with 3.4% regression in NewPM-O3 (and 5.6% in NewPM-ReleaseLTO-g). Might be worth taking a look.

Checked it, caused by the different order of the checks for gathered scalars introduced in this patch. Unfortunately, we cannot change the order back, it was incorrect and produced incorrect cost in some cases. Had to implement a special check to fix this bug, it affects compile time in some cases.

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Vectorize/SLPVectorizer.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SetOperations.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallBitVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/iterator.h"
 #include "llvm/ADT/iterator_range.h"
for (const auto &Data : ExtractVectorsTys) {
         Cost += TTIRef.getShuffleCost(TargetTransformInfo::SK_InsertSubvector,
                                       VecTy, None, 0, EEVTy);
       }
     }
   };
   if (E->State == TreeEntry::NeedToGather) {
     if (allConstant(VL))
       return 0;
-    if (isSplat(VL)) {
-      return ReuseShuffleCost +
-             TTI->getShuffleCost(TargetTransformInfo::SK_Broadcast, VecTy, None,
-                                 0);
-    }
-    if (E->getOpcode() == Instruction::ExtractElement &&
-        allSameType(VL) && allSameBlock(VL)) {
-      SmallVector<int> Mask;
-      Optional<TargetTransformInfo::ShuffleKind> ShuffleKind =
-          isShuffle(VL, Mask);
-      if (ShuffleKind.hasValue()) {
-        InstructionCost Cost =
-            computeExtractCost(VL, VecTy, *ShuffleKind, Mask, *TTI);
-        AdjustExtractsCost(Cost, /*IsGather=*/true);
-        return ReuseShuffleCost + Cost;
-      }
-    }
-    InstructionCost GatherCost = 0;
     SmallVector<int> Mask;
     SmallVector<const TreeEntry *> Entries;
     Optional<TargetTransformInfo::ShuffleKind> Shuffle =
         isGatherShuffledEntry(E, Mask, Entries);
     if (Shuffle.hasValue()) {
+      InstructionCost GatherCost = 0;
       if (ShuffleVectorInst::isIdentityMask(Mask)) {
+        // Perfect match in the graph, will reuse the previously vectorized
+        // node. Cost is 0.
         LLVM_DEBUG(
             dbgs()
             << "SLP: perfect diamond match for gather bundle that starts with "
             << *VL.front() << ".\n");
       } else {
         LLVM_DEBUG(dbgs() << "SLP: shuffled " << Entries.size()
                           << " entries for bundle that starts with "
                           << *VL.front() << ".\n");
+        // Detected that instead of gather we can emit a shuffle of single/two
+        // previously vectorized nodes. Add the cost of the permutation rather
+        // than gather.
         GatherCost = TTI->getShuffleCost(*Shuffle, VecTy, Mask);
       }
-    } else {
-      GatherCost = getGatherCost(VL);
-    }
       return ReuseShuffleCost + GatherCost;
     }
+    if (isSplat(VL)) {
+      // Found the broadcasting of the single scalar, calculate the cost as the
+      // broadcast.
+      return ReuseShuffleCost +
+             TTI->getShuffleCost(TargetTransformInfo::SK_Broadcast, VecTy, None,
+                                 0);
+    }
+    if (E->getOpcode() == Instruction::ExtractElement && allSameType(VL) &&
+        allSameBlock(VL)) {
+      // Check that gather of extractelements can be represented as just a
+      // shuffle of a single/two vectors the scalars are extracted from.
+      SmallVector<int> Mask;
+      Optional<TargetTransformInfo::ShuffleKind> ShuffleKind =
+          isShuffle(VL, Mask);
+      if (ShuffleKind.hasValue()) {
+        // Found the bunch of extractelement instructions that must be gathered
+        // into a vector and can be represented as a permutation elements in a
+        // single input vector or of 2 input vectors.
+        InstructionCost Cost =
+            computeExtractCost(VL, VecTy, *ShuffleKind, Mask, *TTI);
+        AdjustExtractsCost(Cost, /*IsGather=*/true);
+        return ReuseShuffleCost + Cost;
+      }
+    }
+    return ReuseShuffleCost + getGatherCost(VL);
+  }
   assert((E->State == TreeEntry::Vectorize ||
           E->State == TreeEntry::ScatterVectorize) &&
          "Unhandled state");
   assert(E->getOpcode() && allSameType(VL) && allSameBlock(VL) && "Invalid VL");
   Instruction *VL0 = E->getMainOp();
   unsigned ShuffleOrOp =
       E->isAltShuffle() ? (unsigned)Instruction::ShuffleVector : E->getOpcode();
   switch (ShuffleOrOp) {
if (EU.User && isa<InsertElementInst>(EU.User)) {
           continue;
         Value *VU = EU.User;
         auto *It = find_if(FirstUsers, [VU](Value *V) {
           // Checks if 2 insertelements are from the same buildvector.
           if (VU->getType() != V->getType())
             return false;
           auto *IE1 = cast<InsertElementInst>(VU);
           auto *IE2 = cast<InsertElementInst>(V);
+          // Go though of insertelement instructions trying to find either VU as
+          // the original vector for IE2 or V as the original vector for IE1.
           do {
             if (IE1 == VU || IE2 == V)
               return true;
             if (IE1)
               IE1 = dyn_cast<InsertElementInst>(IE1->getOperand(0));
             if (IE2)
               IE2 = dyn_cast<InsertElementInst>(IE2->getOperand(0));
           } while (IE1 || IE2);

 #endif
 
   return Cost;
 }
 
 Optional<TargetTransformInfo::ShuffleKind>
 BoUpSLP::isGatherShuffledEntry(const TreeEntry *TE, SmallVectorImpl<int> &Mask,
                                SmallVectorImpl<const TreeEntry *> &Entries) {
+  // TODO: currently checking only for Scalars in the tree entry, need to count
+  // reused elements too for better cost estimation.
   Mask.assign(TE->Scalars.size(), UndefMaskElem);
   Entries.clear();
-  DenseMap<Value *, const TreeEntry *> UsedValuesEntry;
+  // Build a lists of values to tree entries.
+  DenseMap<Value *, SmallPtrSet<const TreeEntry *, 4>> ValueToTEs;
+  for (const std::unique_ptr<TreeEntry> &EntryPtr : VectorizableTree) {
+    if (EntryPtr.get() == TE)
+      break;
+    if (EntryPtr->State != TreeEntry::NeedToGather)
+      continue;
+    for (Value *V : EntryPtr->Scalars)
+      ValueToTEs.try_emplace(V).first->getSecond().insert(EntryPtr.get());
+  }
+  // Find all tree entries used by the gathered values. If no common entries
+  // found - not a shuffle.
+  // Here we build a set of tree nodes for each gathered value and trying to
+  // find the intersection between these sets. If we have at least one common
+  // tree node for each gathered value - we have just a permutation of the
+  // single vector. If we have 2 different sets, we're in situation where we
+  // have a permutation of 2 input vectors.
+  SmallVector<SmallPtrSet<const TreeEntry *, 4>> UsedTEs;
+  DenseMap<Value *, int> UsedValuesEntry;
+  for (Value *V : TE->Scalars) {
+    if (isa<UndefValue>(V))
+      continue;
+    // Build a list of tree entries where V is used.
+    SmallPtrSet<const TreeEntry *, 4> VToTEs;
+    auto It = ValueToTEs.find(V);
+    if (It != ValueToTEs.end())
+      VToTEs = It->second;
+    if (const TreeEntry *VTE = getTreeEntry(V))
+      VToTEs.insert(VTE);
+    if (VToTEs.empty())
+      return None;
+    if (UsedTEs.empty()) {
+      // The first iteration, just insert the list of nodes to vector.
+      UsedTEs.push_back(VToTEs);
+    } else {
+      // Need to check if there are any previously used tree nodes which use V.
+      // If there are no such nodes, consider that we have another one input
+      // vector.
+      SmallPtrSet<const TreeEntry *, 4> SavedVToTEs(VToTEs);
+      unsigned Idx = 0;
+      for (SmallPtrSet<const TreeEntry *, 4> &Set : UsedTEs) {
+        // Do we have a non-empty intersection of previously listed tree entries
+        // and tree entries using current V?
+        set_intersect(VToTEs, Set);
+        if (!VToTEs.empty()) {
+          // Yes, write the new subset and continue analysis for the next
+          // scalar.
+          Set.swap(VToTEs);
+          break;
+        }
+        VToTEs = SavedVToTEs;
+        ++Idx;
+      }
+      // No non-empty intersection found - need to add a second set of possible
+      // source vectors.
+      if (Idx == UsedTEs.size()) {
+        // If the number of input vectors is greater than 2 - not a permutation,
+        // fallback to the regular gather.
+        if (UsedTEs.size() == 2)
+          return None;
+        UsedTEs.push_back(SavedVToTEs);
+        Idx = UsedTEs.size() - 1;
+      }
+      UsedValuesEntry.try_emplace(V, Idx);
+    }
+  }
+
   unsigned VF = 0;
+  if (UsedTEs.size() == 1) {
+    // Try to find the perfect match in another gather node at first.
+    auto It = find_if(UsedTEs.front(), [TE](const TreeEntry *EntryPtr) {
+      return EntryPtr->isSame(TE->Scalars);
+    });
+    if (It != UsedTEs.front().end()) {
+      Entries.push_back(*It);
+      std::iota(Mask.begin(), Mask.end(), 0);
+      return TargetTransformInfo::SK_PermuteSingleSrc;
+    }
+    // No perfect match, just shuffle, so choose the first tree node.
+    Entries.push_back(*UsedTEs.front().begin());
+  } else {
+    // Try to find nodes with the same vector factor.
+    assert(UsedTEs.size() == 2 && "Expected at max 2 permuted entries.");
     // FIXME: Shall be replaced by GetVF function once non-power-2 patch is
     // landed.
     auto &&GetVF = [](const TreeEntry *TE) {
       if (!TE->ReuseShuffleIndices.empty())
         return TE->ReuseShuffleIndices.size();
       return TE->Scalars.size();
     };
+    DenseMap<int, const TreeEntry *> VFToTE;
+    for (const TreeEntry *TE : UsedTEs.front())
+      VFToTE.try_emplace(GetVF(TE), TE);
+    for (const TreeEntry *TE : UsedTEs.back()) {
+      auto It = VFToTE.find(GetVF(TE));
+      if (It != VFToTE.end()) {
+        VF = It->first;
+        Entries.push_back(It->second);
+        Entries.push_back(TE);
+        break;
+      }
+    }
+    // No 2 source vectors with the same vector factor - give up and do regular
+    // gather.
+    if (Entries.empty())
+      return None;
+  }
+
+  // Build a shuffle mask for better cost estimation and vector emission.
   for (int I = 0, E = TE->Scalars.size(); I < E; ++I) {
     Value *V = TE->Scalars[I];
     if (isa<UndefValue>(V))
       continue;
-    const TreeEntry *VTE = UsedValuesEntry.lookup(V);
-    if (!VTE) {
-      if (Entries.size() == 2)
-        return None;
-      VTE = getTreeEntry(V);
-      if (!VTE || find_if(
-                      VectorizableTree,
-                      [VTE, TE](const std::unique_ptr<TreeEntry> &EntryPtr) {
-                        return EntryPtr.get() == VTE || EntryPtr.get() == TE;
-                      })->get() == TE) {
-        // Check if it is used in one of the gathered entries.
-        const auto *It =
-            find_if(VectorizableTree,
-                    [V, TE](const std::unique_ptr<TreeEntry> &EntryPtr) {
-                      return EntryPtr.get() == TE ||
-                             (EntryPtr->State == TreeEntry::NeedToGather &&
-                              is_contained(EntryPtr->Scalars, V));
-                    });
-        // The vector factor of shuffled entries must be the same.
-        if (It->get() == TE)
-          return None;
-        VTE = It->get();
-      }
-      Entries.push_back(VTE);
-      if (Entries.size() == 1) {
-        VF = GetVF(VTE);
-      } else if (VF != GetVF(VTE)) {
-        assert(Entries.size() == 2 && "Expected shuffle of 1 or 2 entries.");
-        assert(VF > 0 && "Expected non-zero vector factor.");
-        return None;
-      }
-      for (Value *SV : VTE->Scalars)
-        UsedValuesEntry.try_emplace(SV, VTE);
-    }
+    unsigned Idx = UsedValuesEntry.lookup(V);
+    const TreeEntry *VTE = Entries[Idx];
     int FoundLane = findLaneForValue(VTE->Scalars, VTE->ReuseShuffleIndices, V);
-    Mask[I] = (Entries.front() == VTE ? 0 : VF) + FoundLane;
+    Mask[I] = Idx * VF + FoundLane;
     // Extra check required by isSingleSourceMaskImpl function (called by
     // ShuffleVectorInst::isSingleSourceMask).
     if (Mask[I] >= 2 * E)
       return None;
   }
   switch (Entries.size()) {
   case 1:
     return TargetTransformInfo::SK_PermuteSingleSrc;

llvm/test/Transforms/SLPVectorizer/X86/blending-shuffle-inseltpoison.ll

;
   %y1y1 = mul i8 %y1, %y1
   %ins1 = insertelement <2 x i8> poison, i8 %x0x0, i32 0
   %ins2 = insertelement <2 x i8> %ins1, i8 %y1y1, i32 1
   ret <2 x i8> %ins2
 }
 
 define <4 x i8> @h(<4 x i8> %x, <4 x i8> %y) {
 ; CHECK-LABEL: @h(
-; CHECK-NEXT:    [[TMP1:%.*]] = shufflevector <4 x i8> [[X:%.*]], <4 x i8> [[Y:%.*]], <4 x i32> <i32 0, i32 3, i32 5, i32 6>
-; CHECK-NEXT:    [[TMP2:%.*]] = mul <4 x i8> [[TMP1]], [[TMP1]]
-; CHECK-NEXT:    ret <4 x i8> [[TMP2]]
+; CHECK-NEXT:    [[X0:%.*]] = extractelement <4 x i8> [[X:%.*]], i32 0
+; CHECK-NEXT:    [[X3:%.*]] = extractelement <4 x i8> [[X]], i32 3
+; CHECK-NEXT:    [[Y1:%.*]] = extractelement <4 x i8> [[Y:%.*]], i32 1
+; CHECK-NEXT:    [[Y2:%.*]] = extractelement <4 x i8> [[Y]], i32 2
+; CHECK-NEXT:    [[X0X0:%.*]] = mul i8 [[X0]], [[X0]]
+; CHECK-NEXT:    [[X3X3:%.*]] = mul i8 [[X3]], [[X3]]
+; CHECK-NEXT:    [[Y1Y1:%.*]] = mul i8 [[Y1]], [[Y1]]
+; CHECK-NEXT:    [[Y2Y2:%.*]] = mul i8 [[Y2]], [[Y2]]
+; CHECK-NEXT:    [[INS1:%.*]] = insertelement <4 x i8> poison, i8 [[X0X0]], i32 0
+; CHECK-NEXT:    [[INS2:%.*]] = insertelement <4 x i8> [[INS1]], i8 [[X3X3]], i32 1
+; CHECK-NEXT:    [[INS3:%.*]] = insertelement <4 x i8> [[INS2]], i8 [[Y1Y1]], i32 2
+; CHECK-NEXT:    [[INS4:%.*]] = insertelement <4 x i8> [[INS3]], i8 [[Y2Y2]], i32 3
+; CHECK-NEXT:    ret <4 x i8> [[INS4]]
 ;
   %x0 = extractelement <4 x i8> %x, i32 0
   %x3 = extractelement <4 x i8> %x, i32 3
   %y1 = extractelement <4 x i8> %y, i32 1
   %y2 = extractelement <4 x i8> %y, i32 2
   %x0x0 = mul i8 %x0, %x0
   %x3x3 = mul i8 %x3, %x3
   %y1y1 = mul i8 %y1, %y1
   %y2y2 = mul i8 %y2, %y2
   %ins1 = insertelement <4 x i8> poison, i8 %x0x0, i32 0
   %ins2 = insertelement <4 x i8> %ins1, i8 %x3x3, i32 1
   %ins3 = insertelement <4 x i8> %ins2, i8 %y1y1, i32 2
   %ins4 = insertelement <4 x i8> %ins3, i8 %y2y2, i32 3
   ret <4 x i8> %ins4
 }
 
 define <4 x i8> @h_undef(<4 x i8> %x, <4 x i8> %y) {
 ; CHECK-LABEL: @h_undef(
-; CHECK-NEXT:    [[TMP1:%.*]] = shufflevector <4 x i8> [[X:%.*]], <4 x i8> [[Y:%.*]], <4 x i32> <i32 undef, i32 3, i32 5, i32 6>
-; CHECK-NEXT:    [[TMP2:%.*]] = mul <4 x i8> [[TMP1]], [[TMP1]]
-; CHECK-NEXT:    ret <4 x i8> [[TMP2]]
+; CHECK-NEXT:    [[X3:%.*]] = extractelement <4 x i8> [[X:%.*]], i32 3
+; CHECK-NEXT:    [[Y1:%.*]] = extractelement <4 x i8> [[Y:%.*]], i32 1
+; CHECK-NEXT:    [[Y2:%.*]] = extractelement <4 x i8> [[Y]], i32 2
+; CHECK-NEXT:    [[X3X3:%.*]] = mul i8 [[X3]], [[X3]]
+; CHECK-NEXT:    [[Y1Y1:%.*]] = mul i8 [[Y1]], [[Y1]]
+; CHECK-NEXT:    [[Y2Y2:%.*]] = mul i8 [[Y2]], [[Y2]]
+; CHECK-NEXT:    [[INS2:%.*]] = insertelement <4 x i8> <i8 undef, i8 poison, i8 poison, i8 poison>, i8 [[X3X3]], i32 1
+; CHECK-NEXT:    [[INS3:%.*]] = insertelement <4 x i8> [[INS2]], i8 [[Y1Y1]], i32 2
+; CHECK-NEXT:    [[INS4:%.*]] = insertelement <4 x i8> [[INS3]], i8 [[Y2Y2]], i32 3
+; CHECK-NEXT:    ret <4 x i8> [[INS4]]
 ;
   %x0 = extractelement <4 x i8> undef, i32 0
   %x3 = extractelement <4 x i8> %x, i32 3
   %y1 = extractelement <4 x i8> %y, i32 1
   %y2 = extractelement <4 x i8> %y, i32 2
   %x0x0 = mul i8 %x0, %x0
   %x3x3 = mul i8 %x3, %x3
   %y1y1 = mul i8 %y1, %y1
   %y2y2 = mul i8 %y2, %y2

llvm/test/Transforms/SLPVectorizer/X86/blending-shuffle.ll

;
   %y1y1 = mul i8 %y1, %y1
   %ins1 = insertelement <2 x i8> undef, i8 %x0x0, i32 0
   %ins2 = insertelement <2 x i8> %ins1, i8 %y1y1, i32 1
   ret <2 x i8> %ins2
 }
 
 define <4 x i8> @h(<4 x i8> %x, <4 x i8> %y) {
 ; CHECK-LABEL: @h(
-; CHECK-NEXT:    [[TMP1:%.*]] = shufflevector <4 x i8> [[X:%.*]], <4 x i8> [[Y:%.*]], <4 x i32> <i32 0, i32 3, i32 5, i32 6>
-; CHECK-NEXT:    [[TMP2:%.*]] = mul <4 x i8> [[TMP1]], [[TMP1]]
-; CHECK-NEXT:    ret <4 x i8> [[TMP2]]
+; CHECK-NEXT:    [[X0:%.*]] = extractelement <4 x i8> [[X:%.*]], i32 0
+; CHECK-NEXT:    [[X3:%.*]] = extractelement <4 x i8> [[X]], i32 3
+; CHECK-NEXT:    [[Y1:%.*]] = extractelement <4 x i8> [[Y:%.*]], i32 1
+; CHECK-NEXT:    [[Y2:%.*]] = extractelement <4 x i8> [[Y]], i32 2
+; CHECK-NEXT:    [[X0X0:%.*]] = mul i8 [[X0]], [[X0]]
+; CHECK-NEXT:    [[X3X3:%.*]] = mul i8 [[X3]], [[X3]]
+; CHECK-NEXT:    [[Y1Y1:%.*]] = mul i8 [[Y1]], [[Y1]]
+; CHECK-NEXT:    [[Y2Y2:%.*]] = mul i8 [[Y2]], [[Y2]]
+; CHECK-NEXT:    [[INS1:%.*]] = insertelement <4 x i8> undef, i8 [[X0X0]], i32 0
+; CHECK-NEXT:    [[INS2:%.*]] = insertelement <4 x i8> [[INS1]], i8 [[X3X3]], i32 1
+; CHECK-NEXT:    [[INS3:%.*]] = insertelement <4 x i8> [[INS2]], i8 [[Y1Y1]], i32 2
+; CHECK-NEXT:    [[INS4:%.*]] = insertelement <4 x i8> [[INS3]], i8 [[Y2Y2]], i32 3
+; CHECK-NEXT:    ret <4 x i8> [[INS4]]
 ;
   %x0 = extractelement <4 x i8> %x, i32 0
   %x3 = extractelement <4 x i8> %x, i32 3
   %y1 = extractelement <4 x i8> %y, i32 1
   %y2 = extractelement <4 x i8> %y, i32 2
   %x0x0 = mul i8 %x0, %x0
   %x3x3 = mul i8 %x3, %x3
   %y1y1 = mul i8 %y1, %y1
   %y2y2 = mul i8 %y2, %y2
   %ins1 = insertelement <4 x i8> undef, i8 %x0x0, i32 0
   %ins2 = insertelement <4 x i8> %ins1, i8 %x3x3, i32 1
   %ins3 = insertelement <4 x i8> %ins2, i8 %y1y1, i32 2
   %ins4 = insertelement <4 x i8> %ins3, i8 %y2y2, i32 3
   ret <4 x i8> %ins4
 }
 
 define <4 x i8> @h_undef(<4 x i8> %x, <4 x i8> %y) {
 ; CHECK-LABEL: @h_undef(
-; CHECK-NEXT:    [[TMP1:%.*]] = shufflevector <4 x i8> [[X:%.*]], <4 x i8> [[Y:%.*]], <4 x i32> <i32 undef, i32 3, i32 5, i32 6>
-; CHECK-NEXT:    [[TMP2:%.*]] = mul <4 x i8> [[TMP1]], [[TMP1]]
-; CHECK-NEXT:    ret <4 x i8> [[TMP2]]
+; CHECK-NEXT:    [[X3:%.*]] = extractelement <4 x i8> [[X:%.*]], i32 3
+; CHECK-NEXT:    [[Y1:%.*]] = extractelement <4 x i8> [[Y:%.*]], i32 1
+; CHECK-NEXT:    [[Y2:%.*]] = extractelement <4 x i8> [[Y]], i32 2
+; CHECK-NEXT:    [[X3X3:%.*]] = mul i8 [[X3]], [[X3]]
+; CHECK-NEXT:    [[Y1Y1:%.*]] = mul i8 [[Y1]], [[Y1]]
+; CHECK-NEXT:    [[Y2Y2:%.*]] = mul i8 [[Y2]], [[Y2]]
+; CHECK-NEXT:    [[INS2:%.*]] = insertelement <4 x i8> undef, i8 [[X3X3]], i32 1
+; CHECK-NEXT:    [[INS3:%.*]] = insertelement <4 x i8> [[INS2]], i8 [[Y1Y1]], i32 2
+; CHECK-NEXT:    [[INS4:%.*]] = insertelement <4 x i8> [[INS3]], i8 [[Y2Y2]], i32 3
+; CHECK-NEXT:    ret <4 x i8> [[INS4]]
 ;
   %x0 = extractelement <4 x i8> undef, i32 0
   %x3 = extractelement <4 x i8> %x, i32 3
   %y1 = extractelement <4 x i8> %y, i32 1
   %y2 = extractelement <4 x i8> %y, i32 2
   %x0x0 = mul i8 %x0, %x0
   %x3x3 = mul i8 %x3, %x3
   %y1y1 = mul i8 %y1, %y1
;
   %1 = add i8 %x0x0, %x3x3
   %2 = add i8 %y1y1, %y2y2
   %3 = add i8 %1, %2
   ret i8 %3
 }
 
 define i8 @j(<4 x i8> %x, <4 x i8> %y) {
 ; CHECK-LABEL: @j(
 ; CHECK-NEXT:    [[X0:%.*]] = extractelement <4 x i8> [[X:%.*]], i32 0
 ; CHECK-NEXT:    [[X3:%.*]] = extractelement <4 x i8> [[X]], i32 3
 ; CHECK-NEXT:    [[Y1:%.*]] = extractelement <4 x i8> [[Y:%.*]], i32 1
 ; CHECK-NEXT:    [[Y2:%.*]] = extractelement <4 x i8> [[Y]], i32 2
 ; CHECK-NEXT:    [[X0X0:%.*]] = mul i8 [[X0]], [[X0]]
 ; CHECK-NEXT:    [[X3X3:%.*]] = mul i8 [[X3]], [[X3]]
 ; CHECK-NEXT:    [[Y1Y1:%.*]] = mul i8 [[Y1]], [[Y1]]
 ; CHECK-NEXT:    [[Y2Y2:%.*]] = mul i8 [[Y2]], [[Y2]]
 ; CHECK-NEXT:    [[TMP1:%.*]] = add i8 [[X0X0]], [[X3X3]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = add i8 [[Y1Y1]], [[Y2Y2]]
 ; CHECK-NEXT:    [[TMP3:%.*]] = sdiv i8 [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret i8 [[TMP3]]
 ;
   %x0 = extractelement <4 x i8> %x, i32 0
   %x3 = extractelement <4 x i8> %x, i32 3
   %y1 = extractelement <4 x i8> %y, i32 1
   %y2 = extractelement <4 x i8> %y, i32 2
   %x0x0 = mul i8 %x0, %x0
   %x3x3 = mul i8 %x3, %x3
   %y1y1 = mul i8 %y1, %y1
   %y2y2 = mul i8 %y2, %y2
   %1 = add i8 %x0x0, %x3x3
   %2 = add i8 %y1y1, %y2y2
   %3 = sdiv i8 %1, %2
   ret i8 %3
 }
 
 define i8 @k(<4 x i8> %x) {
 ; CHECK-LABEL: @k(
 ; CHECK-NEXT:    [[X0:%.*]] = extractelement <4 x i8> [[X:%.*]], i32 0
 ; CHECK-NEXT:    [[X3:%.*]] = extractelement <4 x i8> [[X]], i32 3
 ; CHECK-NEXT:    [[X1:%.*]] = extractelement <4 x i8> [[X]], i32 1
 ; CHECK-NEXT:    [[X2:%.*]] = extractelement <4 x i8> [[X]], i32 2
 ; CHECK-NEXT:    [[X0X0:%.*]] = mul i8 [[X0]], [[X0]]
 ; CHECK-NEXT:    [[X3X3:%.*]] = mul i8 [[X3]], [[X3]]
 ; CHECK-NEXT:    [[X1X1:%.*]] = mul i8 [[X1]], [[X1]]
 ; CHECK-NEXT:    [[X2X2:%.*]] = mul i8 [[X2]], [[X2]]
 ; CHECK-NEXT:    [[TMP1:%.*]] = add i8 [[X0X0]], [[X3X3]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = add i8 [[X1X1]], [[X2X2]]
 ; CHECK-NEXT:    [[TMP3:%.*]] = sdiv i8 [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret i8 [[TMP3]]
 ;
   %x0 = extractelement <4 x i8> %x, i32 0
   %x3 = extractelement <4 x i8> %x, i32 3
   %x1 = extractelement <4 x i8> %x, i32 1
   %x2 = extractelement <4 x i8> %x, i32 2
   %x0x0 = mul i8 %x0, %x0
   %x3x3 = mul i8 %x3, %x3
   %x1x1 = mul i8 %x1, %x1
   %x2x2 = mul i8 %x2, %x2

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -slp-vectorizer -S -mtriple=x86_64-unknown-linux -slp-threshold=-1 | FileCheck %s
 
 define i32 @diamond_broadcast(i32* noalias nocapture %B, i32* noalias nocapture %A) {
 ; CHECK-LABEL: @diamond_broadcast(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[LD:%.*]] = load i32, i32* [[A:%.*]], align 4
-; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[LD]], [[LD]]
-; CHECK-NEXT:    store i32 [[MUL]], i32* [[B:%.*]], align 4
-; CHECK-NEXT:    [[MUL8:%.*]] = mul i32 [[LD]], [[LD]]
-; CHECK-NEXT:    [[ARRAYIDX9:%.*]] = getelementptr inbounds i32, i32* [[B]], i64 1
-; CHECK-NEXT:    store i32 [[MUL8]], i32* [[ARRAYIDX9]], align 4
-; CHECK-NEXT:    [[MUL14:%.*]] = mul i32 [[LD]], [[LD]]
+; CHECK-NEXT:    [[ARRAYIDX9:%.*]] = getelementptr inbounds i32, i32* [[B:%.*]], i64 1
 ; CHECK-NEXT:    [[ARRAYIDX15:%.*]] = getelementptr inbounds i32, i32* [[B]], i64 2
-; CHECK-NEXT:    store i32 [[MUL14]], i32* [[ARRAYIDX15]], align 4
-; CHECK-NEXT:    [[MUL20:%.*]] = mul i32 [[LD]], [[LD]]
+; CHECK-NEXT:    [[TMP0:%.*]] = insertelement <4 x i32> poison, i32 [[LD]], i32 0
+; CHECK-NEXT:    [[TMP1:%.*]] = insertelement <4 x i32> [[TMP0]], i32 [[LD]], i32 1
+; CHECK-NEXT:    [[TMP2:%.*]] = insertelement <4 x i32> [[TMP1]], i32 [[LD]], i32 2
+; CHECK-NEXT:    [[TMP3:%.*]] = insertelement <4 x i32> [[TMP2]], i32 [[LD]], i32 3
+; CHECK-NEXT:    [[TMP4:%.*]] = mul <4 x i32> [[TMP3]], [[TMP3]]
 ; CHECK-NEXT:    [[ARRAYIDX21:%.*]] = getelementptr inbounds i32, i32* [[B]], i64 3
-; CHECK-NEXT:    store i32 [[MUL20]], i32* [[ARRAYIDX21]], align 4
+; CHECK-NEXT:    [[TMP5:%.*]] = bitcast i32* [[B]] to <4 x i32>*
+; CHECK-NEXT:    store <4 x i32> [[TMP4]], <4 x i32>* [[TMP5]], align 4
 ; CHECK-NEXT:    ret i32 0
 ;
 entry:
   %ld = load i32, i32* %A, align 4
   %mul = mul i32 %ld, %ld
   store i32 %mul, i32* %B, align 4
   %mul8 = mul i32 %ld, %ld
   %arrayidx9 = getelementptr inbounds i32, i32* %B, i64 1