[SLP] Fix for a bug in jumbled memory access vectorization introduced in r293386

[• ashahid]

Summary

The bug is due to absence of in order uses of scalars which needs to be available for VectorizeTree() API. This API uses it for proper mask computation to be used in "shufflevector" IR.

The fix is to compute the mask for out of order memory accesses while building the vectorizable tree instead of actual vectorization of vectorizable tree.

[mkuper]

This is getting a bit hairy, I think - we have too many valuelists flying around.

How about something like this:
When we sort the vectors, we can also use the sort to generate the corresponding shuffle mask (instead of recomputing it in O(|VL|^2) time in line 2623 - 2634), by sorting pairs of <Value, Index>.
We can then keep an optional shuffle mask instead of the NeedToShuffle bit as part of the tree node, and use it to get the correctly ordered list of scalars back from VectorizableTree[0].Scalars when we need to.

What do you think? My gut feeling is that keeping the mask around is worth it just to avoid the N^2 loop in 2623, and the fix to the bug falls out of it.

[• ashahid]

In D30159#681835, @mkuper wrote:

This is getting a bit hairy, I think - we have too many valuelists flying around.

How about something like this:
When we sort the vectors, we can also use the sort to generate the corresponding shuffle mask (instead of recomputing it in O(|VL|^2) time in line 2623 - 2634), by sorting pairs of <Value, Index>.

The basic idea to keep the mask computation at the current place was because we wanted to compute the mask, (N^2 loop), only if vectorization is found to be beneficial.

OTOH if we do mask computation while sorting memory accesses, the utility of SortMemAccesses API may be reduced, however this is not a bigger problem and can be
worked around by keeping a bit to decide whether to compute the mask or not.

We can then keep an optional shuffle mask instead of the NeedToShuffle bit as part of the tree node, and use it to get the correctly ordered list of scalars back from VectorizableTree[0].Scalars when we need to.

What do you think? My gut feeling is that keeping the mask around is worth it just to avoid the N^2 loop in 2623, and the fix to the bug falls out of it.

Although I am not an expert, I think keeping another ValueList for unordered scalars is a not a bad design. However I am open to other views.

Regards,
Shahid

[mkuper]

In D30159#681901, @ashahid wrote:

In D30159#681835, @mkuper wrote:

This is getting a bit hairy, I think - we have too many valuelists flying around.

How about something like this:
When we sort the vectors, we can also use the sort to generate the corresponding shuffle mask (instead of recomputing it in O(|VL|^2) time in line 2623 - 2634), by sorting pairs of <Value, Index>.

The basic idea to keep the mask computation at the current place was because we wanted to compute the mask, (N^2 loop), only if vectorization is found to be beneficial.

Yes, but we can avoid the O(N^2) computation altogether, right? I mean, doing that doesn't add any cost to the sort. Or am I missing something?

OTOH if we do mask computation while sorting memory accesses, the utility of SortMemAccesses API may be reduced, however this is not a bigger problem and can be
worked around by keeping a bit to decide whether to compute the mask or not.

Don't we sort before we know whether we're going to need the mask?

We can then keep an optional shuffle mask instead of the NeedToShuffle bit as part of the tree node, and use it to get the correctly ordered list of scalars back from VectorizableTree[0].Scalars when we need to.

What do you think? My gut feeling is that keeping the mask around is worth it just to avoid the N^2 loop in 2623, and the fix to the bug falls out of it.

Although I am not an expert, I think keeping another ValueList for unordered scalars is a not a bad design. However I am open to other views.

It seems odd to have both the sorted and the unsorted list. The other thing that bothers me is that we have some invariants which don't seem to be well-defined. Is the guarantee that "Scalars" is ordered to have the "best" order to allow vectorization, while InOrdScalars is ordered according to the original IR order? Also, preserving "program order" is kind of meaningless. The fact we care about order at all is just an artifact of the way we build the tree. What we really care about is mapping each scalar leaf to the vector lane it eventually ends up in, which is precisely the shuffle mask.

Anyway, I'm also open to other opinions, if more people care about this.
What I'm really trying to do here is to make the code make a bit more sense - right now, it makes almost zero sense to me. (This isn't the fault of your patch, I'm talking about the general state of the SLP vectorizer).

[• ashahid]

In D30159#681919, @mkuper wrote:

In D30159#681901, @ashahid wrote:

In D30159#681835, @mkuper wrote:

This is getting a bit hairy, I think - we have too many valuelists flying around.

How about something like this:
When we sort the vectors, we can also use the sort to generate the corresponding shuffle mask (instead of recomputing it in O(|VL|^2) time in line 2623 - 2634), by sorting pairs of <Value, Index>.

The basic idea to keep the mask computation at the current place was because we wanted to compute the mask, (N^2 loop), only if vectorization is found to be beneficial.

Yes, but we can avoid the O(N^2) computation altogether, right? I mean, doing that doesn't add any cost to the sort. Or am I missing something?

OTOH if we do mask computation while sorting memory accesses, the utility of SortMemAccesses API may be reduced, however this is not a bigger problem and can be
worked around by keeping a bit to decide whether to compute the mask or not.

Don't we sort before we know whether we're going to need the mask?

We can then keep an optional shuffle mask instead of the NeedToShuffle bit as part of the tree node, and use it to get the correctly ordered list of scalars back from VectorizableTree[0].Scalars when we need to.

What do you think? My gut feeling is that keeping the mask around is worth it just to avoid the N^2 loop in 2623, and the fix to the bug falls out of it.

Although I am not an expert, I think keeping another ValueList for unordered scalars is a not a bad design. However I am open to other views.

It seems odd to have both the sorted and the unsorted list. The other thing that bothers me is that we have some invariants which don't seem to be well-defined. Is the guarantee that "Scalars" is ordered to have the "best" order to allow vectorization, while InOrdScalars is ordered according to the original IR order? Also, preserving "program order" is kind of meaningless. The fact we care about order at all is just an artifact of the way we build the tree. What we really care about is mapping each scalar leaf to the vector lane it eventually ends up in, which is precisely the shuffle mask.

Anyway, I'm also open to other opinions, if more people care about this.
What I'm really trying to do here is to make the code make a bit more sense - right now, it makes almost zero sense to me. (This isn't the fault of your patch, I'm talking about the general state of the SLP vectorizer).

Thanks Michael, my bad, I completely missed that we can avoid O(N^2) mask computation altogether. Moreover, we don't need to have extra VL and NeedToShuffle.
I will update the patch accordingly.

[• ashahid]

Updated the patch to incorporate the review comments.

[mkuper]

lib/Analysis/LoopAccessAnalysis.cpp

1062 ↗

(On Diff #89610)

The API seems a bit odd - having to pass a SmallVector when you know you don't want it to be filled doesn't look right.
I'd prefer something like passing in a pointer, and filling the vector in if it's not null (or passing in an Optional<> reference to a similar effect.)

1098 ↗

(On Diff #89610)

I was thinking along the lines of directly sorting an array of tuples <Offset, Value*, Index> - and then you can pull the mask out of it.
But the that may turn out uglier than what you have here. Your call.

1111 ↗

(On Diff #89610)

Redundant braces.

lib/Transforms/Vectorize/SLPVectorizer.cpp

2627 ↗

(On Diff #89610)

This seems unrelated.
Should it have been here before as well?

[• ashahid]

lib/Analysis/LoopAccessAnalysis.cpp

1062 ↗

(On Diff #89610)

Ok

1098 ↗

(On Diff #89610)

With tuple, I think we still need 2 std::sort() call. I am opting for the simpler than uglier.

lib/Transforms/Vectorize/SLPVectorizer.cpp

2627 ↗

(On Diff #89610)

Earlier this path was not tested properly but thanks to this bug we found.

As in this particular case the vectorized value is being used from the tree entry data instead of the return value, if we don't update E->VectorizedValue "shufflvector" IR will not be used, rather vectorized load IR will be used which is not the intention.

[• ashahid]

Updated the path to incorporate review comments.

[mkuper]

LGTM, with some style comments inline.

lib/Analysis/LoopAccessAnalysis.cpp

1097 ↗

(On Diff #89974)

IIRC, you can do something like "SmallVector<unsigned, 4> UseOrder(VL.size())", and then "UseOrder[i] = i".
This is slightly shorter, and maybe a bit prettier, but feel free to leave as is if you prefer it.

1115 ↗

(On Diff #89974)

I think I would group everything that has to do with Mask together - something like:

if (Mask) {
  Mask->reserve(VL.size());
  for (unsigned i = 0; i < VL.size(); i++)
    Mask->emplace_back(i);
  std::sort(Mask->begin(), Mask->end(),
                [&UseOrder](unsigned Left, unsigned Right) {
                return UseOrder[Left] < UseOrder[Right];
              });  
}

Instead of having three "if(Mask)"-s.
Sure, you get another for loop, but I think it's cleaner this way.

1098 ↗

(On Diff #89610)

Ok. I think we can do with 1, but I'm still not sure it's an improvement, so we can keep this as is.

lib/Transforms/Vectorize/SLPVectorizer.cpp

2627 ↗

(On Diff #89610)

Right, that's more or less what I thought.

[• ashahid]

lib/Transforms/Vectorize/SLPVectorizer.cpp

2627 ↗

(On Diff #89610)

Oh I missed one thing, I think you added a test jumbled-same.ll for a recent fix. I think this test needs to be updated now to account for the use of shuffled value of the loaded vector in "extractelement"?

[mkuper]

lib/Transforms/Vectorize/SLPVectorizer.cpp

2627 ↗

(On Diff #89610)

Argh, yes, I didn't notice the shuffle is used in the icmp, but not in the extract.
Go ahead and update it. Thanks!

[• ashahid]

Updated the patch to do a proper lane computation for external uses.

[mkuper]

lib/Transforms/Vectorize/SLPVectorizer.cpp

2861 ↗

(On Diff #90429)

This is the only change in the patch w.r.t the previous version, right?

2864 ↗

(On Diff #90429)

Isn't this condition equivalent to E->ShuffleMask[i] == ExternalUse.Lane? I think that's a bit clearer, maybe.
(I'm not really certain it's clearer, but I'd like to make sure I understand what's going on here)

Regardless, please add a comment describing what this whole thing does.

test/Transforms/SLPVectorizer/X86/jumbled-same.ll

16 ↗

(On Diff #90429)

Ok, now this makes sense. :-)

[• ashahid]

lib/Transforms/Vectorize/SLPVectorizer.cpp

2861 ↗

(On Diff #90429)

Yes

2864 ↗

(On Diff #90429)

Yes, this condition is equivalent to E->ShuffleMask[i] == ExternalUse.Lane and it does look clearer. Oh, sure I will add the comment.

llvm/trunk/include/llvm/Analysis/LoopAccessAnalysis.h

 /// run-time assumptions.
 int64_t getPtrStride(PredicatedScalarEvolution &PSE, Value *Ptr, const Loop *Lp,
                      const ValueToValueMap &StridesMap = ValueToValueMap(),
                      bool Assume = false, bool ShouldCheckWrap = true);
 
 /// \brief Try to sort an array of loads / stores.
 ///
 /// An array of loads / stores can only be sorted if all pointer operands
-/// refer to the same object, and the differences between these pointers 
+/// refer to the same object, and the differences between these pointers
 /// are known to be constant. If that is the case, this returns true, and the
 /// sorted array is returned in \p Sorted. Otherwise, this returns false, and
 /// \p Sorted is invalid.
+//  If \p Mask is not null, it also returns the \p Mask which is the shuffle
+//  mask for actual memory access order.
 bool sortMemAccesses(ArrayRef<Value *> VL, const DataLayout &DL,
-                     ScalarEvolution &SE, SmallVectorImpl<Value *> &Sorted);
+                     ScalarEvolution &SE, SmallVectorImpl<Value *> &Sorted,
+                     SmallVectorImpl<unsigned> *Mask = nullptr);
 
 /// \brief Returns true if the memory operations \p A and \p B are consecutive.
 /// This is a simple API that does not depend on the analysis pass. 
 bool isConsecutiveAccess(Value *A, Value *B, const DataLayout &DL,
                          ScalarEvolution &SE, bool CheckType = true);
 
 /// \brief This analysis provides dependence information for the memory accesses
 /// of a loop.

llvm/trunk/lib/Analysis/LoopAccessAnalysis.cpp

if (LoadInst *L = dyn_cast<LoadInst>(I))
     return L->getPointerAddressSpace();
   if (StoreInst *S = dyn_cast<StoreInst>(I))
     return S->getPointerAddressSpace();
   return -1;
 }
 
 bool llvm::sortMemAccesses(ArrayRef<Value *> VL, const DataLayout &DL,
                            ScalarEvolution &SE,
-                           SmallVectorImpl<Value *> &Sorted) {
+                           SmallVectorImpl<Value *> &Sorted,
+                           SmallVectorImpl<unsigned> *Mask) {
   SmallVector<std::pair<int64_t, Value *>, 4> OffValPairs;
   OffValPairs.reserve(VL.size());
   Sorted.reserve(VL.size());
 
   // Walk over the pointers, and map each of them to an offset relative to
   // first pointer in the array.
   Value *Ptr0 = getPointerOperand(VL[0]);
   const SCEV *Scev0 = SE.getSCEV(Ptr0);
   Value *Obj0 = GetUnderlyingObject(Ptr0, DL);
-
   for (auto *Val : VL) {
     // The only kind of access we care about here is load.
     if (!isa<LoadInst>(Val))
       return false;
 
     Value *Ptr = getPointerOperand(Val);
     assert(Ptr && "Expected value to have a pointer operand.");
 
for (auto *Val : VL) {
     // may just not be smart enough to figure out they do. Regardless,
     // there's nothing we can do.
     if (!Diff)
       return false;
 
     OffValPairs.emplace_back(Diff->getAPInt().getSExtValue(), Val);
   }
 
-  std::sort(OffValPairs.begin(), OffValPairs.end(),
-            [](const std::pair<int64_t, Value *> &Left,
-               const std::pair<int64_t, Value *> &Right) {
-              return Left.first < Right.first;
+  SmallVector<unsigned, 4> UseOrder(VL.size());
+  for (unsigned i = 0; i < VL.size(); i++) {
+    UseOrder[i] = i;
+  }
+
+  // Sort the memory accesses and keep the order of their uses in UseOrder.
+  std::sort(UseOrder.begin(), UseOrder.end(),
+            [&OffValPairs](unsigned Left, unsigned Right) {
+              return OffValPairs[Left].first < OffValPairs[Right].first;
             });
 
-  for (auto &it : OffValPairs)
-    Sorted.push_back(it.second);
+  for (unsigned i = 0; i < VL.size(); i++)
+    Sorted.emplace_back(OffValPairs[UseOrder[i]].second);
+
+  // Sort UseOrder to compute the Mask.
+  if (Mask) {
+    Mask->reserve(VL.size());
+    for (unsigned i = 0; i < VL.size(); i++)
+      Mask->emplace_back(i);
+    std::sort(Mask->begin(), Mask->end(),
+              [&UseOrder](unsigned Left, unsigned Right) {
+                return UseOrder[Left] < UseOrder[Right];
+              });
+  }
 
   return true;
 }
 
 /// Returns true if the memory operations \p A and \p B are consecutive.
 bool llvm::isConsecutiveAccess(Value *A, Value *B, const DataLayout &DL,
                                ScalarEvolution &SE, bool CheckType) {
   Value *PtrA = getPointerOperand(A);

llvm/trunk/lib/Transforms/Vectorize/SLPVectorizer.cpp

private:
 
   /// This is the recursive part of buildTree.
   void buildTree_rec(ArrayRef<Value *> Roots, unsigned Depth);
 
   /// \returns True if the ExtractElement/ExtractValue instructions in VL can
   /// be vectorized to use the original vector (or aggregate "bitcast" to a vector).
   bool canReuseExtract(ArrayRef<Value *> VL, unsigned Opcode) const;
 
-  /// Vectorize a single entry in the tree. VL icontains all isomorphic scalars
-  /// in order of its usage in a user program, for example ADD1, ADD2 and so on
-  /// or LOAD1 , LOAD2 etc.
-  Value *vectorizeTree(ArrayRef<Value *> VL, TreeEntry *E);
+  /// Vectorize a single entry in the tree.
+  Value *vectorizeTree(TreeEntry *E);
 
   /// Vectorize a single entry in the tree, starting in \p VL.
   Value *vectorizeTree(ArrayRef<Value *> VL);
 
   /// \returns the pointer to the vectorized value if \p VL is already
   /// vectorized, or NULL. They may happen in cycles.
   Value *alreadyVectorized(ArrayRef<Value *> VL) const;
 
void reorderAltShuffleOperands(ArrayRef<Value *> VL,
                                  SmallVectorImpl<Value *> &Left,
                                  SmallVectorImpl<Value *> &Right);
   /// \reorder commutative operands to get better probability of
   /// generating vectorized code.
   void reorderInputsAccordingToOpcode(ArrayRef<Value *> VL,
                                       SmallVectorImpl<Value *> &Left,
                                       SmallVectorImpl<Value *> &Right);
   struct TreeEntry {
-    TreeEntry() : Scalars(), VectorizedValue(nullptr),
-    NeedToGather(0), NeedToShuffle(0) {}
+    TreeEntry()
+        : Scalars(), VectorizedValue(nullptr), NeedToGather(0), ShuffleMask() {}
 
     /// \returns true if the scalars in VL are equal to this entry.
     bool isSame(ArrayRef<Value *> VL) const {
       assert(VL.size() == Scalars.size() && "Invalid size");
       return std::equal(VL.begin(), VL.end(), Scalars.begin());
     }
 
     /// \returns true if the scalars in VL are found in this tree entry.
struct TreeEntry {
     ValueList Scalars;
 
     /// The Scalars are vectorized into this value. It is initialized to Null.
     Value *VectorizedValue;
 
     /// Do we need to gather this sequence ?
     bool NeedToGather;
 
-    /// Do we need to shuffle the load ?
-    bool NeedToShuffle;
+    /// Records optional suffle mask for jumbled memory accesses in this.
+    SmallVector<unsigned, 8> ShuffleMask;
+
   };
 
   /// Create a new VectorizableTree entry.
   TreeEntry *newTreeEntry(ArrayRef<Value *> VL, bool Vectorized,
-                          bool NeedToShuffle) {
+                          ArrayRef<unsigned> ShuffleMask = None) {
     VectorizableTree.emplace_back();
     int idx = VectorizableTree.size() - 1;
     TreeEntry *Last = &VectorizableTree[idx];
     Last->Scalars.insert(Last->Scalars.begin(), VL.begin(), VL.end());
     Last->NeedToGather = !Vectorized;
-    Last->NeedToShuffle = NeedToShuffle;
+    if (!ShuffleMask.empty())
+      Last->ShuffleMask.insert(Last->ShuffleMask.begin(), ShuffleMask.begin(),
+                               ShuffleMask.end());
+
     if (Vectorized) {
       for (int i = 0, e = VL.size(); i != e; ++i) {
         assert(!ScalarToTreeEntry.count(VL[i]) && "Scalar already in tree!");
         ScalarToTreeEntry[VL[i]] = idx;
       }
     } else {
       MustGather.insert(VL.begin(), VL.end());
     }

 
 
 void BoUpSLP::buildTree_rec(ArrayRef<Value *> VL, unsigned Depth) {
   bool isAltShuffle = false;
   assert((allConstant(VL) || allSameType(VL)) && "Invalid types!");
 
   if (Depth == RecursionMaxDepth) {
     DEBUG(dbgs() << "SLP: Gathering due to max recursion depth.\n");
-    newTreeEntry(VL, false, false);
+    newTreeEntry(VL, false);
     return;
   }
 
   // Don't handle vectors.
   if (VL[0]->getType()->isVectorTy()) {
     DEBUG(dbgs() << "SLP: Gathering due to vector type.\n");
-    newTreeEntry(VL, false, false);
+    newTreeEntry(VL, false);
     return;
   }
 
   if (StoreInst *SI = dyn_cast<StoreInst>(VL[0]))
     if (SI->getValueOperand()->getType()->isVectorTy()) {
       DEBUG(dbgs() << "SLP: Gathering due to store vector type.\n");
-      newTreeEntry(VL, false, false);
+      newTreeEntry(VL, false);
       return;
     }
   unsigned Opcode = getSameOpcode(VL);
 
   // Check that this shuffle vector refers to the alternate
   // sequence of opcodes.
   if (Opcode == Instruction::ShuffleVector) {
     Instruction *I0 = dyn_cast<Instruction>(VL[0]);
     unsigned Op = I0->getOpcode();
     if (Op != Instruction::ShuffleVector)
       isAltShuffle = true;
   }
 
   // If all of the operands are identical or constant we have a simple solution.
   if (allConstant(VL) || isSplat(VL) || !allSameBlock(VL) || !Opcode) {
     DEBUG(dbgs() << "SLP: Gathering due to C,S,B,O. \n");
-    newTreeEntry(VL, false, false);
+    newTreeEntry(VL, false);
     return;
   }
 
   // We now know that this is a vector of instructions of the same type from
   // the same block.
 
   // Don't vectorize ephemeral values.
   for (unsigned i = 0, e = VL.size(); i != e; ++i) {
     if (EphValues.count(VL[i])) {
       DEBUG(dbgs() << "SLP: The instruction (" << *VL[i] <<
             ") is ephemeral.\n");
-      newTreeEntry(VL, false, false);
+      newTreeEntry(VL, false);
       return;
     }
   }
 
   // Check if this is a duplicate of another entry.
   if (ScalarToTreeEntry.count(VL[0])) {
     int Idx = ScalarToTreeEntry[VL[0]];
     TreeEntry *E = &VectorizableTree[Idx];
     for (unsigned i = 0, e = VL.size(); i != e; ++i) {
       DEBUG(dbgs() << "SLP: \tChecking bundle: " << *VL[i] << ".\n");
       if (E->Scalars[i] != VL[i]) {
         DEBUG(dbgs() << "SLP: Gathering due to partial overlap.\n");
-        newTreeEntry(VL, false, false);
+        newTreeEntry(VL, false);
         return;
       }
     }
     DEBUG(dbgs() << "SLP: Perfect diamond merge at " << *VL[0] << ".\n");
     return;
   }
 
   // Check that none of the instructions in the bundle are already in the tree.
   for (unsigned i = 0, e = VL.size(); i != e; ++i) {
     if (ScalarToTreeEntry.count(VL[i])) {
       DEBUG(dbgs() << "SLP: The instruction (" << *VL[i] <<
             ") is already in tree.\n");
-      newTreeEntry(VL, false, false);
+      newTreeEntry(VL, false);
       return;
     }
   }
 
   // If any of the scalars is marked as a value that needs to stay scalar then
   // we need to gather the scalars.
   for (unsigned i = 0, e = VL.size(); i != e; ++i) {
     if (MustGather.count(VL[i])) {
       DEBUG(dbgs() << "SLP: Gathering due to gathered scalar.\n");
-      newTreeEntry(VL, false, false);
+      newTreeEntry(VL, false);
       return;
     }
   }
 
   // Check that all of the users of the scalars that we want to vectorize are
   // schedulable.
   Instruction *VL0 = cast<Instruction>(VL[0]);
   BasicBlock *BB = cast<Instruction>(VL0)->getParent();
 
   if (!DT->isReachableFromEntry(BB)) {
     // Don't go into unreachable blocks. They may contain instructions with
     // dependency cycles which confuse the final scheduling.
     DEBUG(dbgs() << "SLP: bundle in unreachable block.\n");
-    newTreeEntry(VL, false, false);
+    newTreeEntry(VL, false);
     return;
   }
 
   // Check that every instructions appears once in this bundle.
   for (unsigned i = 0, e = VL.size(); i < e; ++i)
     for (unsigned j = i+1; j < e; ++j)
       if (VL[i] == VL[j]) {
         DEBUG(dbgs() << "SLP: Scalar used twice in bundle.\n");
-        newTreeEntry(VL, false, false);
+        newTreeEntry(VL, false);
         return;
       }
 
   auto &BSRef = BlocksSchedules[BB];
   if (!BSRef) {
     BSRef = llvm::make_unique<BlockScheduling>(BB);
   }
   BlockScheduling &BS = *BSRef.get();
 
   if (!BS.tryScheduleBundle(VL, this)) {
     DEBUG(dbgs() << "SLP: We are not able to schedule this bundle!\n");
     assert((!BS.getScheduleData(VL[0]) ||
             !BS.getScheduleData(VL[0])->isPartOfBundle()) &&
            "tryScheduleBundle should cancelScheduling on failure");
-    newTreeEntry(VL, false, false);
+    newTreeEntry(VL, false);
     return;
   }
   DEBUG(dbgs() << "SLP: We are able to schedule this bundle.\n");
 
   switch (Opcode) {
     case Instruction::PHI: {
       PHINode *PH = dyn_cast<PHINode>(VL0);
 
       // Check for terminator values (e.g. invoke).
       for (unsigned j = 0; j < VL.size(); ++j)
         for (unsigned i = 0, e = PH->getNumIncomingValues(); i < e; ++i) {
           TerminatorInst *Term = dyn_cast<TerminatorInst>(
               cast<PHINode>(VL[j])->getIncomingValueForBlock(PH->getIncomingBlock(i)));
           if (Term) {
             DEBUG(dbgs() << "SLP: Need to swizzle PHINodes (TerminatorInst use).\n");
             BS.cancelScheduling(VL);
-            newTreeEntry(VL, false, false);
+            newTreeEntry(VL, false);
             return;
           }
         }
 
-      newTreeEntry(VL, true, false);
+      newTreeEntry(VL, true);
       DEBUG(dbgs() << "SLP: added a vector of PHINodes.\n");
 
       for (unsigned i = 0, e = PH->getNumIncomingValues(); i < e; ++i) {
         ValueList Operands;
         // Prepare the operand vector.
         for (Value *j : VL)
           Operands.push_back(cast<PHINode>(j)->getIncomingValueForBlock(
               PH->getIncomingBlock(i)));
 
         buildTree_rec(Operands, Depth + 1);
       }
       return;
     }
     case Instruction::ExtractValue:
     case Instruction::ExtractElement: {
       bool Reuse = canReuseExtract(VL, Opcode);
       if (Reuse) {
         DEBUG(dbgs() << "SLP: Reusing extract sequence.\n");
       } else {
         BS.cancelScheduling(VL);
       }
-      newTreeEntry(VL, Reuse, false);
+      newTreeEntry(VL, Reuse);
       return;
     }
     case Instruction::Load: {
       // Check that a vectorized load would load the same memory as a scalar
       // load.
       // For example we don't want vectorize loads that are smaller than 8 bit.
       // Even though we have a packed struct {<i2, i2, i2, i2>} LLVM treats
       // loading/storing it as an i8 struct. If we vectorize loads/stores from
       // such a struct we read/write packed bits disagreeing with the
       // unvectorized version.
       Type *ScalarTy = VL[0]->getType();
 
       if (DL->getTypeSizeInBits(ScalarTy) !=
           DL->getTypeAllocSizeInBits(ScalarTy)) {
         BS.cancelScheduling(VL);
-        newTreeEntry(VL, false, false);
+        newTreeEntry(VL, false);
         DEBUG(dbgs() << "SLP: Gathering loads of non-packed type.\n");
         return;
       }
 
       // Make sure all loads in the bundle are simple - we can't vectorize
       // atomic or volatile loads.
       for (unsigned i = 0, e = VL.size() - 1; i < e; ++i) {
         LoadInst *L = cast<LoadInst>(VL[i]);
         if (!L->isSimple()) {
           BS.cancelScheduling(VL);
-          newTreeEntry(VL, false, false);
+          newTreeEntry(VL, false);
           DEBUG(dbgs() << "SLP: Gathering non-simple loads.\n");
           return;
         }
       }
 
       // Check if the loads are consecutive, reversed, or neither.
       bool Consecutive = true;
       bool ReverseConsecutive = true;
       for (unsigned i = 0, e = VL.size() - 1; i < e; ++i) {
         if (!isConsecutiveAccess(VL[i], VL[i + 1], *DL, *SE)) {
           Consecutive = false;
           break;
         } else {
           ReverseConsecutive = false;
         }
       }
 
       if (Consecutive) {
         ++NumLoadsWantToKeepOrder;
-        newTreeEntry(VL, true, false);
+        newTreeEntry(VL, true);
         DEBUG(dbgs() << "SLP: added a vector of loads.\n");
         return;
       }
 
       // If none of the load pairs were consecutive when checked in order,
       // check the reverse order.
       if (ReverseConsecutive)
         for (unsigned i = VL.size() - 1; i > 0; --i)
           if (!isConsecutiveAccess(VL[i], VL[i - 1], *DL, *SE)) {
             ReverseConsecutive = false;
             break;
           }
 
       if (VL.size() > 2 && !ReverseConsecutive) {
         bool ShuffledLoads = true;
         SmallVector<Value *, 8> Sorted;
-        if (sortMemAccesses(VL, *DL, *SE, Sorted)) {
+        SmallVector<unsigned, 4> Mask;
+        if (sortMemAccesses(VL, *DL, *SE, Sorted, &Mask)) {
           auto NewVL = makeArrayRef(Sorted.begin(), Sorted.end());
           for (unsigned i = 0, e = NewVL.size() - 1; i < e; ++i) {
             if (!isConsecutiveAccess(NewVL[i], NewVL[i + 1], *DL, *SE)) {
               ShuffledLoads = false;
               break;
             }
           }
           if (ShuffledLoads) {
-            newTreeEntry(NewVL, true, true);
+            newTreeEntry(NewVL, true, makeArrayRef(Mask.begin(), Mask.end()));
             return;
           }
         }
       }
 
       BS.cancelScheduling(VL);
-      newTreeEntry(VL, false, false);
+      newTreeEntry(VL, false);
 
       if (ReverseConsecutive) {
         ++NumLoadsWantToChangeOrder;
         DEBUG(dbgs() << "SLP: Gathering reversed loads.\n");
       } else {
         DEBUG(dbgs() << "SLP: Gathering non-consecutive loads.\n");
       }
       return;
switch (Opcode) {
     case Instruction::Trunc:
     case Instruction::FPTrunc:
     case Instruction::BitCast: {
       Type *SrcTy = VL0->getOperand(0)->getType();
       for (Value *Val : VL) {
         Type *Ty = cast<Instruction>(Val)->getOperand(0)->getType();
         if (Ty != SrcTy || !isValidElementType(Ty)) {
           BS.cancelScheduling(VL);
-          newTreeEntry(VL, false, false);
+          newTreeEntry(VL, false);
           DEBUG(dbgs() << "SLP: Gathering casts with different src types.\n");
           return;
         }
       }
-      newTreeEntry(VL, true, false);
+      newTreeEntry(VL, true);
       DEBUG(dbgs() << "SLP: added a vector of casts.\n");
 
       for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) {
         ValueList Operands;
         // Prepare the operand vector.
         for (Value *j : VL)
           Operands.push_back(cast<Instruction>(j)->getOperand(i));
 
         buildTree_rec(Operands, Depth+1);
       }
       return;
     }
     case Instruction::ICmp:
     case Instruction::FCmp: {
       // Check that all of the compares have the same predicate.
       CmpInst::Predicate P0 = cast<CmpInst>(VL0)->getPredicate();
       Type *ComparedTy = cast<Instruction>(VL[0])->getOperand(0)->getType();
       for (unsigned i = 1, e = VL.size(); i < e; ++i) {
         CmpInst *Cmp = cast<CmpInst>(VL[i]);
         if (Cmp->getPredicate() != P0 ||
             Cmp->getOperand(0)->getType() != ComparedTy) {
           BS.cancelScheduling(VL);
-          newTreeEntry(VL, false, false);
+          newTreeEntry(VL, false);
           DEBUG(dbgs() << "SLP: Gathering cmp with different predicate.\n");
           return;
         }
       }
 
-      newTreeEntry(VL, true, false);
+      newTreeEntry(VL, true);
       DEBUG(dbgs() << "SLP: added a vector of compares.\n");
 
       for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) {
         ValueList Operands;
         // Prepare the operand vector.
         for (Value *j : VL)
           Operands.push_back(cast<Instruction>(j)->getOperand(i));
 
switch (Opcode) {
     case Instruction::SRem:
     case Instruction::FRem:
     case Instruction::Shl:
     case Instruction::LShr:
     case Instruction::AShr:
     case Instruction::And:
     case Instruction::Or:
     case Instruction::Xor: {
-      newTreeEntry(VL, true, false);
+      newTreeEntry(VL, true);
       DEBUG(dbgs() << "SLP: added a vector of bin op.\n");
 
       // Sort operands of the instructions so that each side is more likely to
       // have the same opcode.
       if (isa<BinaryOperator>(VL0) && VL0->isCommutative()) {
         ValueList Left, Right;
         reorderInputsAccordingToOpcode(VL, Left, Right);
         buildTree_rec(Left, Depth + 1);
case Instruction::Xor: {
       return;
     }
     case Instruction::GetElementPtr: {
       // We don't combine GEPs with complicated (nested) indexing.
       for (Value *Val : VL) {
         if (cast<Instruction>(Val)->getNumOperands() != 2) {
           DEBUG(dbgs() << "SLP: not-vectorizable GEP (nested indexes).\n");
           BS.cancelScheduling(VL);
-          newTreeEntry(VL, false, false);
+          newTreeEntry(VL, false);
           return;
         }
       }
 
       // We can't combine several GEPs into one vector if they operate on
       // different types.
       Type *Ty0 = cast<Instruction>(VL0)->getOperand(0)->getType();
       for (Value *Val : VL) {
         Type *CurTy = cast<Instruction>(Val)->getOperand(0)->getType();
         if (Ty0 != CurTy) {
           DEBUG(dbgs() << "SLP: not-vectorizable GEP (different types).\n");
           BS.cancelScheduling(VL);
-          newTreeEntry(VL, false, false);
+          newTreeEntry(VL, false);
           return;
         }
       }
 
       // We don't combine GEPs with non-constant indexes.
       for (Value *Val : VL) {
         auto Op = cast<Instruction>(Val)->getOperand(1);
         if (!isa<ConstantInt>(Op)) {
           DEBUG(
               dbgs() << "SLP: not-vectorizable GEP (non-constant indexes).\n");
           BS.cancelScheduling(VL);
-          newTreeEntry(VL, false, false);
+          newTreeEntry(VL, false);
           return;
         }
       }
 
-      newTreeEntry(VL, true, false);
+      newTreeEntry(VL, true);
       DEBUG(dbgs() << "SLP: added a vector of GEPs.\n");
       for (unsigned i = 0, e = 2; i < e; ++i) {
         ValueList Operands;
         // Prepare the operand vector.
         for (Value *j : VL)
           Operands.push_back(cast<Instruction>(j)->getOperand(i));
 
         buildTree_rec(Operands, Depth + 1);
       }
       return;
     }
     case Instruction::Store: {
       // Check if the stores are consecutive or of we need to swizzle them.
       for (unsigned i = 0, e = VL.size() - 1; i < e; ++i)
         if (!isConsecutiveAccess(VL[i], VL[i + 1], *DL, *SE)) {
           BS.cancelScheduling(VL);
-          newTreeEntry(VL, false, false);
+          newTreeEntry(VL, false);
           DEBUG(dbgs() << "SLP: Non-consecutive store.\n");
           return;
         }
 
-      newTreeEntry(VL, true, false);
+      newTreeEntry(VL, true);
       DEBUG(dbgs() << "SLP: added a vector of stores.\n");
 
       ValueList Operands;
       for (Value *j : VL)
         Operands.push_back(cast<Instruction>(j)->getOperand(0));
 
       buildTree_rec(Operands, Depth + 1);
       return;
     }
     case Instruction::Call: {
       // Check if the calls are all to the same vectorizable intrinsic.
       CallInst *CI = cast<CallInst>(VL[0]);
       // Check if this is an Intrinsic call or something that can be
       // represented by an intrinsic call
       Intrinsic::ID ID = getVectorIntrinsicIDForCall(CI, TLI);
       if (!isTriviallyVectorizable(ID)) {
         BS.cancelScheduling(VL);
-        newTreeEntry(VL, false, false);
+        newTreeEntry(VL, false);
         DEBUG(dbgs() << "SLP: Non-vectorizable call.\n");
         return;
       }
       Function *Int = CI->getCalledFunction();
       Value *A1I = nullptr;
       if (hasVectorInstrinsicScalarOpd(ID, 1))
         A1I = CI->getArgOperand(1);
       for (unsigned i = 1, e = VL.size(); i != e; ++i) {
         CallInst *CI2 = dyn_cast<CallInst>(VL[i]);
         if (!CI2 || CI2->getCalledFunction() != Int ||
             getVectorIntrinsicIDForCall(CI2, TLI) != ID ||
             !CI->hasIdenticalOperandBundleSchema(*CI2)) {
           BS.cancelScheduling(VL);
-          newTreeEntry(VL, false, false);
+          newTreeEntry(VL, false);
           DEBUG(dbgs() << "SLP: mismatched calls:" << *CI << "!=" << *VL[i]
                        << "\n");
           return;
         }
         // ctlz,cttz and powi are special intrinsics whose second argument
         // should be same in order for them to be vectorized.
         if (hasVectorInstrinsicScalarOpd(ID, 1)) {
           Value *A1J = CI2->getArgOperand(1);
           if (A1I != A1J) {
             BS.cancelScheduling(VL);
-            newTreeEntry(VL, false, false);
+            newTreeEntry(VL, false);
             DEBUG(dbgs() << "SLP: mismatched arguments in call:" << *CI
                          << " argument "<< A1I<<"!=" << A1J
                          << "\n");
             return;
           }
         }
         // Verify that the bundle operands are identical between the two calls.
         if (CI->hasOperandBundles() &&
             !std::equal(CI->op_begin() + CI->getBundleOperandsStartIndex(),
                         CI->op_begin() + CI->getBundleOperandsEndIndex(),
                         CI2->op_begin() + CI2->getBundleOperandsStartIndex())) {
           BS.cancelScheduling(VL);
-          newTreeEntry(VL, false, false);
+          newTreeEntry(VL, false);
           DEBUG(dbgs() << "SLP: mismatched bundle operands in calls:" << *CI << "!="
                        << *VL[i] << '\n');
           return;
         }
       }
 
-      newTreeEntry(VL, true, false);
+      newTreeEntry(VL, true);
       for (unsigned i = 0, e = CI->getNumArgOperands(); i != e; ++i) {
         ValueList Operands;
         // Prepare the operand vector.
         for (Value *j : VL) {
           CallInst *CI2 = dyn_cast<CallInst>(j);
           Operands.push_back(CI2->getArgOperand(i));
         }
         buildTree_rec(Operands, Depth + 1);
       }
       return;
     }
     case Instruction::ShuffleVector: {
       // If this is not an alternate sequence of opcode like add-sub
       // then do not vectorize this instruction.
       if (!isAltShuffle) {
         BS.cancelScheduling(VL);
-        newTreeEntry(VL, false, false);
+        newTreeEntry(VL, false);
         DEBUG(dbgs() << "SLP: ShuffleVector are not vectorized.\n");
         return;
       }
-      newTreeEntry(VL, true, false);
+      newTreeEntry(VL, true);
       DEBUG(dbgs() << "SLP: added a ShuffleVector op.\n");
 
       // Reorder operands if reordering would enable vectorization.
       if (isa<BinaryOperator>(VL0)) {
         ValueList Left, Right;
         reorderAltShuffleOperands(VL, Left, Right);
         buildTree_rec(Left, Depth + 1);
         buildTree_rec(Right, Depth + 1);
         return;
       }
 
       for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) {
         ValueList Operands;
         // Prepare the operand vector.
         for (Value *j : VL)
           Operands.push_back(cast<Instruction>(j)->getOperand(i));
 
         buildTree_rec(Operands, Depth + 1);
       }
       return;
     }
     default:
       BS.cancelScheduling(VL);
-      newTreeEntry(VL, false, false);
+      newTreeEntry(VL, false);
       DEBUG(dbgs() << "SLP: Gathering unknown instruction.\n");
       return;
   }
 }
 
 unsigned BoUpSLP::canMapToVector(Type *T, const DataLayout &DL) const {
   unsigned N;
   Type *EltTy;
switch (Opcode) {
     }
     case Instruction::Load: {
       // Cost of wide load - cost of scalar loads.
       unsigned alignment = dyn_cast<LoadInst>(VL0)->getAlignment();
       int ScalarLdCost = VecTy->getNumElements() *
             TTI->getMemoryOpCost(Instruction::Load, ScalarTy, alignment, 0);
       int VecLdCost = TTI->getMemoryOpCost(Instruction::Load,
                                            VecTy, alignment, 0);
-      if (E->NeedToShuffle) {
+      if (!E->ShuffleMask.empty()) {
         VecLdCost += TTI->getShuffleCost(
             TargetTransformInfo::SK_PermuteSingleSrc, VecTy, 0);
       }
       return VecLdCost - ScalarLdCost;
     }
     case Instruction::Store: {
       // We know that we can merge the stores. Calculate the cost.
       unsigned alignment = dyn_cast<StoreInst>(VL0)->getAlignment();
Value *BoUpSLP::alreadyVectorized(ArrayRef<Value *> VL) const {
   }
   return nullptr;
 }
 
 Value *BoUpSLP::vectorizeTree(ArrayRef<Value *> VL) {
   if (ScalarToTreeEntry.count(VL[0])) {
     int Idx = ScalarToTreeEntry[VL[0]];
     TreeEntry *E = &VectorizableTree[Idx];
-    if (E->isSame(VL) || (E->NeedToShuffle && E->isFoundJumbled(VL, *DL, *SE)))
-      return vectorizeTree(VL, E);
+    if (E->isSame(VL) ||
+        (!E->ShuffleMask.empty() && E->isFoundJumbled(VL, *DL, *SE)))
+      return vectorizeTree(E);
   }
 
   Type *ScalarTy = VL[0]->getType();
   if (StoreInst *SI = dyn_cast<StoreInst>(VL[0]))
     ScalarTy = SI->getValueOperand()->getType();
   VectorType *VecTy = VectorType::get(ScalarTy, VL.size());
 
   return Gather(VL, VecTy);
 }
 
-Value *BoUpSLP::vectorizeTree(ArrayRef<Value *> VL, TreeEntry *E) {
+Value *BoUpSLP::vectorizeTree(TreeEntry *E) {
   IRBuilder<>::InsertPointGuard Guard(Builder);
 
-  if (E->VectorizedValue && !E->NeedToShuffle) {
+  if (E->VectorizedValue && E->ShuffleMask.empty()) {
     DEBUG(dbgs() << "SLP: Diamond merged for " << *E->Scalars[0] << ".\n");
     return E->VectorizedValue;
   }
 
   Instruction *VL0 = cast<Instruction>(E->Scalars[0]);
   Type *ScalarTy = VL0->getType();
   if (StoreInst *SI = dyn_cast<StoreInst>(VL0))
     ScalarTy = SI->getValueOperand()->getType();
case Instruction::Load: {
       }
       LI->setAlignment(Alignment);
       E->VectorizedValue = LI;
       ++NumVectorInstructions;
       propagateMetadata(LI, E->Scalars);
 
       // As program order of scalar loads are jumbled, the vectorized 'load'
       // must be followed by a 'shuffle' with the required jumbled mask.
-      if (!VL.empty() && (E->NeedToShuffle)) {
-        assert(VL.size() == E->Scalars.size() &&
-               "Equal number of scalars expected");
+      if (!E->ShuffleMask.empty()) {
         SmallVector<Constant *, 8> Mask;
-        for (Value *Val : VL) {
-          if (ScalarToTreeEntry.count(Val)) {
-            int Idx = ScalarToTreeEntry[Val];
-            TreeEntry *E = &VectorizableTree[Idx];
-            for (unsigned Lane = 0, LE = VL.size(); Lane != LE; ++Lane) {
-              if (E->Scalars[Lane] == Val) {
-                Mask.push_back(Builder.getInt32(Lane));
-                break;
-              }
-            }
-          }
+        for (unsigned Lane = 0, LE = E->ShuffleMask.size(); Lane != LE;
+             ++Lane) {
+          Mask.push_back(Builder.getInt32(E->ShuffleMask[Lane]));
         }
-
         // Generate shuffle for jumbled memory access
         Value *Undef = UndefValue::get(VecTy);
         Value *Shuf = Builder.CreateShuffleVector((Value *)LI, Undef,
                                                   ConstantVector::get(Mask));
+        E->VectorizedValue = Shuf;
+        ++NumVectorInstructions;
         return Shuf;
       }
 
       return LI;
     }
     case Instruction::Store: {
       StoreInst *SI = cast<StoreInst>(VL0);
       unsigned Alignment = SI->getAlignment();

 BoUpSLP::vectorizeTree(ExtraValueToDebugLocsMap &ExternallyUsedValues) {
 
   // All blocks must be scheduled before any instructions are inserted.
   for (auto &BSIter : BlocksSchedules) {
     scheduleBlock(BSIter.second.get());
   }
 
   Builder.SetInsertPoint(&F->getEntryBlock().front());
-  auto *VectorRoot = vectorizeTree(ArrayRef<Value *>(), &VectorizableTree[0]);
+  auto *VectorRoot = vectorizeTree(&VectorizableTree[0]);
 
   // If the vectorized tree can be rewritten in a smaller type, we truncate the
   // vectorized root. InstCombine will then rewrite the entire expression. We
   // sign extend the extracted values below.
   auto *ScalarRoot = VectorizableTree[0].Scalars[0];
   if (MinBWs.count(ScalarRoot)) {
     if (auto *I = dyn_cast<Instruction>(VectorRoot))
       Builder.SetInsertPoint(&*++BasicBlock::iterator(I));
for (const auto &ExternalUse : ExternalUses) {
     assert(ScalarToTreeEntry.count(Scalar) && "Invalid scalar");
 
     int Idx = ScalarToTreeEntry[Scalar];
     TreeEntry *E = &VectorizableTree[Idx];
     assert(!E->NeedToGather && "Extracting from a gather list");
 
     Value *Vec = E->VectorizedValue;
     assert(Vec && "Can't find vectorizable value");
-
-    Value *Lane = Builder.getInt32(ExternalUse.Lane);
+    unsigned i = 0;
+    Value *Lane;
+    // In case vectorizable scalars use are not in-order, scalars would have
+    // been shuffled.Recompute the proper Lane of ExternalUse.
+    if (!E->ShuffleMask.empty()) {
+      SmallVector<unsigned, 4> Val(E->ShuffleMask.size());
+      for (; i < E->ShuffleMask.size(); i++) {
+        if (E->ShuffleMask[i] == (unsigned)ExternalUse.Lane)
+          break;
+      }
+      Lane = Builder.getInt32(i);
+    } else {
+      Lane = Builder.getInt32(ExternalUse.Lane);
+    }
     // If User == nullptr, the Scalar is used as extra arg. Generate
     // ExtractElement instruction and update the record for this scalar in
     // ExternallyUsedValues.
     if (!User) {
       assert(ExternallyUsedValues.count(Scalar) &&
              "Scalar with nullptr as an external user must be registered in "
              "ExternallyUsedValues map");
       if (auto *VecI = dyn_cast<Instruction>(Vec)) {

llvm/trunk/test/Transforms/SLPVectorizer/X86/jumbled-load-bug.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -S -slp-vectorizer | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define <4 x i32> @zot() #0 {
+; CHECK-LABEL: @zot(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    [[P0:%.*]] = getelementptr inbounds [4 x i8], [4 x i8]* undef, i64 undef, i64 0
+; CHECK-NEXT:    [[P1:%.*]] = getelementptr inbounds [4 x i8], [4 x i8]* undef, i64 undef, i64 1
+; CHECK-NEXT:    [[P2:%.*]] = getelementptr inbounds [4 x i8], [4 x i8]* undef, i64 undef, i64 2
+; CHECK-NEXT:    [[P3:%.*]] = getelementptr inbounds [4 x i8], [4 x i8]* undef, i64 undef, i64 3
+; CHECK-NEXT:    [[TMP0:%.*]] = bitcast i8* [[P0]] to <4 x i8>*
+; CHECK-NEXT:    [[TMP1:%.*]] = load <4 x i8>, <4 x i8>* [[TMP0]], align 1
+; CHECK-NEXT:    [[TMP2:%.*]] = shufflevector <4 x i8> [[TMP1]], <4 x i8> undef, <4 x i32> <i32 1, i32 0, i32 2, i32 3>
+; CHECK-NEXT:    [[TMP3:%.*]] = extractelement <4 x i8> [[TMP2]], i32 0
+; CHECK-NEXT:    [[I0:%.*]] = insertelement <4 x i8> undef, i8 [[TMP3]], i32 0
+; CHECK-NEXT:    [[TMP4:%.*]] = extractelement <4 x i8> [[TMP2]], i32 1
+; CHECK-NEXT:    [[I1:%.*]] = insertelement <4 x i8> [[I0]], i8 [[TMP4]], i32 1
+; CHECK-NEXT:    [[TMP5:%.*]] = extractelement <4 x i8> [[TMP2]], i32 2
+; CHECK-NEXT:    [[I2:%.*]] = insertelement <4 x i8> [[I1]], i8 [[TMP5]], i32 2
+; CHECK-NEXT:    [[TMP6:%.*]] = extractelement <4 x i8> [[TMP2]], i32 3
+; CHECK-NEXT:    [[I3:%.*]] = insertelement <4 x i8> [[I2]], i8 [[TMP6]], i32 3
+; CHECK-NEXT:    [[RET:%.*]] = zext <4 x i8> [[I3]] to <4 x i32>
+; CHECK-NEXT:    ret <4 x i32> [[RET]]
+;
+bb:
+  %p0 = getelementptr inbounds [4 x i8], [4 x i8]* undef, i64 undef, i64 0
+  %p1 = getelementptr inbounds [4 x i8], [4 x i8]* undef, i64 undef, i64 1
+  %p2 = getelementptr inbounds [4 x i8], [4 x i8]* undef, i64 undef, i64 2
+  %p3 = getelementptr inbounds [4 x i8], [4 x i8]* undef, i64 undef, i64 3
+  %v3 = load i8, i8* %p3, align 1
+  %v2 = load i8, i8* %p2, align 1
+  %v0 = load i8, i8* %p0, align 1
+  %v1 = load i8, i8* %p1, align 1
+  %i0 = insertelement <4 x i8> undef, i8 %v1, i32 0
+  %i1 = insertelement <4 x i8> %i0, i8 %v0, i32 1
+  %i2 = insertelement <4 x i8> %i1, i8 %v2, i32 2
+  %i3 = insertelement <4 x i8> %i2, i8 %v3, i32 3
+  %ret = zext <4 x i8> %i3 to <4 x i32>
+  ret <4 x i32> %ret
+}

llvm/trunk/test/Transforms/SLPVectorizer/X86/jumbled-same.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -slp-vectorizer -S -mtriple=x86_64-unknown-linux -mattr=+sse4.2 | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 @a = common local_unnamed_addr global [4 x i32] zeroinitializer, align 4
 @b = common local_unnamed_addr global [4 x i32] zeroinitializer, align 4
 
 define i32 @fn1() {
 ; CHECK-LABEL: @fn1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = load <4 x i32>, <4 x i32>* bitcast ([4 x i32]* @b to <4 x i32>*), align 4
 ; CHECK-NEXT:    [[TMP1:%.*]] = shufflevector <4 x i32> [[TMP0]], <4 x i32> undef, <4 x i32> <i32 1, i32 2, i32 3, i32 0>
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp sgt <4 x i32> [[TMP1]], zeroinitializer
-; CHECK-NEXT:    [[TMP3:%.*]] = extractelement <4 x i32> [[TMP0]], i32 1
+; CHECK-NEXT:    [[TMP3:%.*]] = extractelement <4 x i32> [[TMP1]], i32 0
 ; CHECK-NEXT:    [[TMP4:%.*]] = insertelement <4 x i32> undef, i32 [[TMP3]], i32 0
 ; CHECK-NEXT:    [[TMP5:%.*]] = insertelement <4 x i32> [[TMP4]], i32 ptrtoint (i32 ()* @fn1 to i32), i32 1
 ; CHECK-NEXT:    [[TMP6:%.*]] = insertelement <4 x i32> [[TMP5]], i32 ptrtoint (i32 ()* @fn1 to i32), i32 2
 ; CHECK-NEXT:    [[TMP7:%.*]] = insertelement <4 x i32> [[TMP6]], i32 8, i32 3
 ; CHECK-NEXT:    [[TMP8:%.*]] = select <4 x i1> [[TMP2]], <4 x i32> [[TMP7]], <4 x i32> <i32 6, i32 0, i32 0, i32 0>
 ; CHECK-NEXT:    store <4 x i32> [[TMP8]], <4 x i32>* bitcast ([4 x i32]* @a to <4 x i32>*), align 4
 ; CHECK-NEXT:    ret i32 0
 ;