[SLP] Make SLPVectorizer to use `llvm.masked.gather` intrinsic

[anton-afanasyev]

Summary

For the scattered operands of load instructions it makes sense
to use gathering load intrinsic, which can lower to native instruction
for X86/AVX512 and ARM/SVE. This also enables building
vectorization tree with entries containing scattered operands.
The next step is to add scattered store.

Fixes PR47629 and PR47623

[anton-afanasyev]

Updated comments and LaneIndex

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

24

Hmm, investigated this: no, I was wrong, the calculated cost is correct (insertelemetss for gather instr are compesated by insertelements for buildvector). Further investigating this... Looks like codegen issue more.

[RKSimon]

Please can you rebase after rG1eeae4310771d8a6896fe09effe88883998f34e8?

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

24

Hmm - does the X86 TTI handle buildvectors of pointers costs or does it fallback to the generic implementation (which is almost certainly lower)?

[dmgreen]

The MVE gather costs were certainly written with the loop vectorizer in mind. The number of gather/scatter instructions we have is quite limited and it's not always simple to match llvm.gathers to mve gathers. I've not seen any issues from this so far though, other than what was just fixed up in rG30ad7426442e.

[anton-afanasyev]

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

24

Despite of codegen output for Skylake looking complicated I believe it's still more optimized, since the gather is cheaper than four loads from memory, isn't it?

[RKSimon]

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

24

My concern is that -march=avx512 does nothing so you're just getting raw sse2 costs here - hence why I updated the tests at rG1eeae4310771d8a6896fe09effe88883998f34e8

[anton-afanasyev]

Rebased against changed test file

[anton-afanasyev]

Rebased, but optimization eliminated for -mattr=.... Option -mattr=+avx512vl should be set explicitly to activate costs.

[xbolva00]

This comment was removed by xbolva00.

[anton-afanasyev]

I've extended test case again: https://reviews.llvm.org/rGe8d67ef2dc93. Also, @xbolva00 precommited test for PR47263, which is fixed with this patch.

[anton-afanasyev]

Rebased

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

1583

I would think about adding a new EntryState instead of adding a new data member.

3706

Comment for false argument

4549

auto *

4551

auto *

4558

.emplace_back(PO, cast<User>(VecPtr), InsIndex);

4563

Try to merge this code line with the one in line 4539

[anton-afanasyev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

1583

I've thought about it and discussed this with @dtemirbulatov (his throttling patch is extending EntryState as well). I've come that IsScattered is like ReuseShuffleIndices/ReorderIndices (data members) more than an "entry state". Also, the current entry state NeedToGather would add ambiguity in that case.

3706

Ok.

4549

Ok

4551

UndefValue::get() returns UndefValue* type, but we need Value* here.

4558

Ok

4563

Done.

[anton-afanasyev]

Addressed notes

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

1583

It is different thing. ReuseShuffleIndices/ReorderIndices can be used by many different entries while IsScattered member is used only for a single particular kind of node. It increases memory usage because we add an extra field which is just ignored in many cases. Plus, to me, this field just a mark of the new kind of gather.

2851

Why it is vectorized if this is actually kind of gather?

[anton-afanasyev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

1583

Ok, sounds convincing, I can change it. But I don't think this field is "just the new kind of gather". I'm planning to use IsScattered for scattered stores (@llvm.store.scatter intrinsic) at the next step, of course. This is not the gather like NeedToGather entry state.

2851

Actually I think vectorized is more appropriate here than gathered in sense it is used throughout SLPVectorizer module. Since we actually modify several instruction to _one_. I can change it to scatter-vectorized.

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2851

Could you give a bit more explanation why it should be treated as vectorized?

[anton-afanasyev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2851

Ok.
For now, enum EntryState {Vectorize, NeedToGather} has two states: the first is for the bundle that is to be vectorized, the second is to be gathered, but here "gathered" means this bundle will stay untouched after tree vectorization, we need no replace several scalar instructions with one vector instruction. Also we need no handle users of gathered instruction.
For the "scattered" entry we have opposite case: several scalar instructios to be replaced with @llvm.masked.gather.* and @llvm.masked.scatter.* intrinsics and we need to handle its users (at least, for store = @llvm.masked.scatter.* case (the next patch, also using IsScattered field)).
Am I clear?

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2851

Shall we handle the users for loads?

[anton-afanasyev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2851

No, only for stores, of course. Vectorized loads are leaves of vectorized tree, whereas stores are seed points. Scattered stores can also be "vectorized" in the sense of being replaced with the one intrinsic.

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2851

Then for loads it is more just a kind a gather, rather than vectorize. Is it required to mark the scalars as vectorized or just enough to mark as gathered? Do we need all this stuff that is required for the vectorized instructions, like inorder, etc.?

[anton-afanasyev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2851

Yes, we need this stuff: at least, separate cost estimation, scheduling. We treat this as generalization of vectorization -- like load <4 x i32>, @llvm.masked.gather loads to <4 x i32>, for instance.

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2851

Why it cannot be model via gather? We gather the scalar loads here but into a different form. Instead of direct gather we just gather the addresses and then do a load. But this still a kind of gather. Do you need to continue scheduling here? No, you don't, just need to extend Gather function to generate gather of addresses + llvm.masked.gather call.

[anton-afanasyev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2851

It can be model via gather, ok, but only for load case, not for store one. But we already treat ordinary load <4 x i32> as vectorized entry, what is the difference with @llvm.masked.gather <4 x i32>? I see here consistent symmetry:

ordinary load of vector <-> ordinary store of vector
             |                 |
gather of vector <-> scatter of vector

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2851

Because the model is not based on the final outcome. Plus, you missed the real gather of addresses.
Did you think about adding a new gather treeentry for addresses? Looks like you missed the cost for addresses gather.

[anton-afanasyev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2851

Why is model not based on the final outcome? The cost is separate issue -- I can fix this at getEntryCost().

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2851

Because later this code can be transformed into something else, anyway, for example gather can be transformed into a single instruction. The model itself is based on the scalars, how they are transformed into a vector form.
I would suggest just to add 2 tree entries in this case. One for new scatter vectorization form and one for gathering of addresses. It would simplify handling of this in future and won't break the model. Plus, you would not need to add a new cost calculation and rely on the exisiting cost model for the gather of addresses.

[anton-afanasyev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2851

Sounds good, thanks!

[anton-afanasyev]

Added second tree entry for addresses

[ABataev]

In D90445#2380023, @anton-afanasyev wrote:

Added second tree entry for addresses

Yep, this looks much better now. What about adding new vectorization kind for scatter-gather?

[dtemirbulatov]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

1583

Just to avoid any confusion, I think it is to change the name to IsScatterGatherOps?

[anton-afanasyev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

1583

Current IsScatteredOps means that _operands_ of load/store are _scattered_, so need either to gather, or to scatter them. I'm to change name to IsScatterOpds to avoid confusion with Operations.

[anton-afanasyev]

Renamed IsScatteredOps to IsScatteredOpds

[anton-afanasyev]

In D90445#2380322, @ABataev wrote:

In D90445#2380023, @anton-afanasyev wrote:

Added second tree entry for addresses

Yep, this looks much better now. What about adding new vectorization kind for scatter-gather?

What do you mean by "vectorization kind"? Vectorization is differentiated by bundle instructions opcode.

[ABataev]

In D90445#2382105, @anton-afanasyev wrote:

In D90445#2380322, @ABataev wrote:

In D90445#2380023, @anton-afanasyev wrote:

Added second tree entry for addresses

Yep, this looks much better now. What about adding new vectorization kind for scatter-gather?

What do you mean by "vectorization kind"? Vectorization is differentiated by bundle instructions opcode.

I meant, to add a new vectorization kind for this node, something like Scatter or ScatterVectorized. We discussed before, that this new boolean field is going to e unused in many cases and better to introduce a new vectorization id (extend EntryState enum)

[anton-afanasyev]

Use of EntryState

[anton-afanasyev]

I meant, to add a new vectorization kind for this node, something like Scatter or ScatterVectorized. We discussed before, that this new boolean field is going to e unused in many cases and better to introduce a new vectorization id (extend EntryState enum)

Ok, changed. Do you think this is better now?

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2853

Better to modify Bundle parameter in newTreeEntry function, something like Optional<std::pair<EntryState, Bundle>> and pass EntryState directly at function call. You can implement it as a separate NFC patch.

3704

Add assert here for E->State == TreeEntry::ScatterVectorize

4546

Add assert here for E->State == TreeEntry::ScatterVectorize

[anton-afanasyev]

Added asserts

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2853

Ok, I can fix it in a separate patch. But now I doubt that initial memory optimization with IsScatteredOpds elimination was worse than this final EntryState expansion requiring changes for all newTreeEntry() calls.

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2853

Yes, it still will be better. Here you will allocate the value on the stack, which will be cleared after function termination. With an extra data member each TreeEntry will retain it till the end of life of the whole tree.

[anton-afanasyev]

Assert fix

[anton-afanasyev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2853

Ok

[anton-afanasyev]

Fixed asserts again

[anton-afanasyev]

Small fix of debug printer

[dtemirbulatov]

Also, please add ScatterVectorize to TreeEntry.dump()

[anton-afanasyev]

In D90445#2391375, @dtemirbulatov wrote:

Also, please add ScatterVectorize to TreeEntry.dump()

It's already here, line 1704.

[dtemirbulatov]

Looks good, any other objections?

[RKSimon]

LGTM with one minor

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

1555–1558

Minor - please add comment explaining the purpose of each enum

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2853

Looks like you still do not pass the vectorization state as an argument. I thought we agreed to modify Bundle related param to be an Optional of EntryState and Bundle types? Better to create the entry with the correctly set inner state rather than modify them outside of the class. It breaks encapsulation.

[anton-afanasyev]

Add comment

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

1555–1558

Thank you, done!

2853

Sorry, missed this comment. Yes, we agreed to do this, but as a separate NFC patch.

3709

In general, yes, we can end up with reordering, but this could be optimized with preliminary pointers vector shuffling. Though I think it's rather rare case (load-gather plus reordering meeting together), I can prepare separate patch to optimize this after investigation of its impact.

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2853

Yes, thanks. Could you prepare this NFC patch before commiting this patch?

[anton-afanasyev]

Added optional EntryState param to newTreeEntry()

[anton-afanasyev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2853

Hmm, I've decided to get rid of scary make_pair inside all newTreeEntry() callings, leaving most of the code untouched. So, added optional EntryState param to newTreeEntry() function. Minimal changes, so no need for separate patch. Is it good now?

[anton-afanasyev]

Fix tests after "--check-prefixes" change (D90445) and fix one assert

[RKSimon]

LGTM with one minor

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

10

Sorry, I think you need to remove the 'CHECK' from all of these and just use SSE/AVX

[anton-afanasyev]

Fix test, CHECK prefix is unused

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

10

Ok, done

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

1754

It may conflict with State param value and may lead to incorrect undrstanding/decisions in future. That's why I proposed to merge EntryState and Bundle into one Optional<std::pair<>>, though this solution also is not quite optimal.
Maybe better to split this function into 2 overloaded copies, one for gather and one for vectorized state?

[anton-afanasyev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

1754

Would it be better to leave all as it was before and just add setEntryState() method to accurately set ScatterVectorize (or other state in future)?

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

1754

Nah, it is similar to what was before. Better to set the correct state when constructing the state rather than construct it with the incorrect flag and then trying to fix it on-the-fly. It is bad design decision and always a source of bugs.

[anton-afanasyev]

Add overloaded newTreeEntry() for common case

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

1754

Ok, thanks! So I created overloaded copy of newTreeEntry() especially for EntryState given explicitly. Is it good now?

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

1756

I think it will crash if Bundle is None

1762

1. Better to make Optional<std::pair<EntryState, ScheduleData *>>.
2. I would add `assert(!StateAndBundle || StateAndBundle.getValue().first != NeedToGather && "...");

[anton-afanasyev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

1756

Thank you, fixed!

1762

1. I tried to get rid of std::pair again, now looks better, doesn't it?
2. Thanks, added.

[anton-afanasyev]

Fixes and assert

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

1767

What if !Bundle && EntryState != NeedToGather, i.e. trying to vectorize gather entry?

[anton-afanasyev]

Added another assert

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

1767

Thanks, added second assert.

[ABataev]

LG

[fhahn]

It looks like this change may cause a crash when building LNT, e.g. http://lab.llvm.org:8011/#/builders/105/builds/1899/steps/7/logs/stdio

[anton-afanasyev]

In D90445#2399926, @fhahn wrote:

It looks like this change may cause a crash when building LNT, e.g. http://lab.llvm.org:8011/#/builders/105/builds/1899/steps/7/logs/stdio

Thank you, fixing!

[anton-afanasyev]

Fixed

[bkramer]

Saw some random miscompiles after this. Fixed by 4dbe12e86649ba6b5f03a9ba97e84d718727f7a7, can you check if I got it right?

[anton-afanasyev]

In D90445#2402312, @bkramer wrote:

Saw some random miscompiles after this. Fixed by 4dbe12e86649ba6b5f03a9ba97e84d718727f7a7, can you check if I got it right?

Yes, thanks, looks good!

[fhahn]

It appears this is causing a ~2-3% regression on AArch64 for some benchmarks, including CINT2000/256.bzip2. Any ideas? It might be caused by underestimating the cost of gather/scatter on AArch64.

[RKSimon]

In D90445#2411311, @fhahn wrote:

It appears this is causing a ~2-3% regression on AArch64 for some benchmarks, including CINT2000/256.bzip2. Any ideas? It might be caused by underestimating the cost of gather/scatter on AArch64.

Poor target specific costs is likely to be the problem - either for explicit gather intrinsic costs or the scalarization overhead fallback.

[dmgreen]

If isLegalMaskedGather is returning false (as it will do for AArch64 NEON), then should this even be attempting to use gather/scatter? I would have thought that will never do worth it if it is just going to scalarize again?

[RKSimon]

In D90445#2411347, @dmgreen wrote:

If isLegalMaskedGather is returning false (as it will do for AArch64 NEON), then should this even be attempting to use gather/scatter? I would have thought that will never do worth it if it is just going to scalarize again?

SLP should always create gathers with constant masks while isLegalMaskedGather covers the more general variable masks as well - we can always legalize constant mask gathers back to a buildvector or insertelement chain so its often worthwhile using the gather intrinsic to act for that case as well, hence it being important we correctly handle the scalarization overhead fallback.

[anton-afanasyev]

I believe this issue is related to the default cost for getGatherScatterOpCost(). For the arch not having gather/scatter instrs we use TargetTransformInfoImplBase::getGatherScatterOpCost() which returns 1 unconditionally: https://github.com/llvm/llvm-project/blob/release/11.x/llvm/include/llvm/Analysis/TargetTransformInfoImpl.h#L480
I'd fix it by setting something like 1024 for the default cost.

[fhahn]

In D90445#2411663, @anton-afanasyev wrote:

I believe this issue is related to the default cost for getGatherScatterOpCost(). For the arch not having gather/scatter instrs we use TargetTransformInfoImplBase::getGatherScatterOpCost() which returns 1 unconditionally: https://github.com/llvm/llvm-project/blob/release/11.x/llvm/include/llvm/Analysis/TargetTransformInfoImpl.h#L480
I'd fix it by setting something like 1024 for the default cost.

yes, I managed to track it down to that. I pushed some additional tests and D91984 to add a more realistic estimate for the cost when scalarizing.

[vdmitrie]

Current SLP has significant drawback with regard to its cost modeling. And this patch highlights it.
Consider we have four scalar loads of i8 type. With prior approach (vectorization overhead) we had cost for such entry 4 (x86 target).
With this new approach we have two entries instead of one: ScatterVectorize loads + NeedToGather GEPs. And costs for these entries are 6 and 10 respectively, thus cost increased from 4 to 16.
And the problem here is once we put this pattern into the tree it pulls cost up for the entire tree. If we have multiple such patterns over the tree their effect is magnified. These entries finally outweigh possible profit of vectorization for remaining portion of the tree and we end up not vectorizing it at all (even if downstream optimizations could probably change it into optimal code). If SLP could make choice vectorization overhead vs gather intrinsic based in their costs while building vectorizable tree the outcome could be different.

[anton-afanasyev]

In D90445#2411961, @vdmitrie wrote:

Current SLP has significant drawback with regard to its cost modeling. And this patch highlights it.
Consider we have four scalar loads of i8 type. With prior approach (vectorization overhead) we had cost for such entry 4 (x86 target).
With this new approach we have two entries instead of one: ScatterVectorize loads + NeedToGather GEPs. And costs for these entries are 6 and 10 respectively, thus cost increased from 4 to 16.
And the problem here is once we put this pattern into the tree it pulls cost up for the entire tree. If we have multiple such patterns over the tree their effect is magnified. These entries finally outweigh possible profit of vectorization for remaining portion of the tree and we end up not vectorizing it at all (even if downstream optimizations could probably change it into optimal code). If SLP could make choice vectorization overhead vs gather intrinsic based in their costs while building vectorizable tree the outcome could be different.

Good point, thank you! As you said, that is not the problem specific for this patch exclusively. One can fix it by hacky cost comparing at the buildind tree stage, but I do believe the more general solution is preferable. Does this patch https://reviews.llvm.org/D57779 (vectorization throttling) fixes this? After greedy strategy of building the maximum tree we choose the cheapest part of it for vectorization.

[dtemirbulatov]

Good point, thank you! As you said, that is not the problem specific for this patch exclusively. One can fix it by hacky cost comparing at the buildind tree stage, but I do believe the more general solution is preferable. Does this patch https://reviews.llvm.org/D57779 (vectorization throttling) fixes this? After greedy strategy of building the maximum tree we choose the cheapest part of it for vectorization.

No, I think https://reviews.llvm.org/D57779 is about a different thing. Here, we have new functionality which allows us to built the tree with gather-loads otherwise we just ignore it and thus have a different tree. I am not sure how to handle the case if it is accumulating those expensive operations. Maybe guard this new functionality by a flag for now?

[anton-afanasyev]

Talked with @dtemirbulatov privately and reached a consensus that his patch reviews.llvm.org/D57779 fixes the issue defined above by @vdmitrie in general.

[vdmitrie]

It sounds like throttling patch should resolve this issue as cutting out ScatterVectorize entry with high cost will effectively return to previous behavior.

[anton-afanasyev]

In D90445#2416578, @vdmitrie wrote:

It sounds like throttling patch should resolve this issue as cutting out ScatterVectorize entry with high cost will effectively return to previous behavior.

Yes, exactly. The only difference with previous behavior could arise in case of the new tree accumulating other instructions starting from ScatterVectorize and NeedToGather GEPs entries, preventing them from being contained in other parts of tree. But these entries are terminal, with so rare speculative exceptions that I believe it's good euristics for this case as well as for the general SLP drawback you mentioned: build the maximum tree and choose the cheapest subtree.

[fhahn]

It looks like this commit may be causing a mis-compile: https://bugs.llvm.org/show_bug.cgi?id=50015

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

struct TreeEntry {
     }
 
     /// A vector of scalars.
     ValueList Scalars;
 
     /// The Scalars are vectorized into this value. It is initialized to Null.
     Value *VectorizedValue = nullptr;
 
-    /// Do we need to gather this sequence ?
-    enum EntryState { Vectorize, NeedToGather };
+    /// Do we need to gather this sequence or vectorize it
+    /// (either with vector instruction or with scatter/gather
+    /// intrinsics for store/load)?
+    enum EntryState { Vectorize, ScatterVectorize, NeedToGather };
     EntryState State;
 
     /// Does this sequence require some shuffling?
     SmallVector<int, 4> ReuseShuffleIndices;
 
     /// Does this entry require reordering?
     SmallVector<unsigned, 4> ReorderIndices;
 
     /// Points back to the VectorizableTree.
     ///
     /// Only used for Graphviz right now.  Unfortunately GraphTrait::NodeRef has
     /// to be a pointer and needs to be able to initialize the child iterator.
     /// Thus we need a reference back to the container to translate the indices
     /// to entries.
     VecTreeTy &Container;
 
     /// The TreeEntry index containing the user of this entry.  We can actually
     /// have multiple users so the data structure is not truly a tree.
     SmallVector<EdgeInfo, 1> UserTreeIndices;
 
     /// The index of this treeEntry in VectorizableTree.
     int Idx = -1;
 
   private:
     /// The operands of each instruction in each lane Operands[op_index][lane].
     /// Note: This helps avoid the replication of the code that performs the
     /// reordering of operands during buildTree_rec() and vectorizeTree().
     SmallVector<ValueList, 2> Operands;
 
     /// The main/alternate instruction.
     Instruction *MainOp = nullptr;
     Instruction *AltOp = nullptr;
 
LLVM_DUMP_METHOD void dump() const {
       dbgs() << "Scalars: \n";
       for (Value *V : Scalars)
         dbgs().indent(2) << *V << "\n";
       dbgs() << "State: ";
       switch (State) {
       case Vectorize:
         dbgs() << "Vectorize\n";
         break;
+      case ScatterVectorize:
+        dbgs() << "ScatterVectorize\n";
+        break;
       case NeedToGather:
         dbgs() << "NeedToGather\n";
         break;
       }
       dbgs() << "MainOp: ";
       if (MainOp)
         dbgs() << *MainOp << "\n";
       else

 #endif
   };
 
   /// Create a new VectorizableTree entry.
   TreeEntry *newTreeEntry(ArrayRef<Value *> VL, Optional<ScheduleData *> Bundle,
                           const InstructionsState &S,
                           const EdgeInfo &UserTreeIdx,
                           ArrayRef<unsigned> ReuseShuffleIndices = None,
-                          ArrayRef<unsigned> ReorderIndices = None) {
+                          ArrayRef<unsigned> ReorderIndices = None,
+                          TreeEntry::EntryState State = TreeEntry::Vectorize) {
     bool Vectorized = (bool)Bundle;
     VectorizableTree.push_back(std::make_unique<TreeEntry>(VectorizableTree));
     TreeEntry *Last = VectorizableTree.back().get();
     Last->Idx = VectorizableTree.size() - 1;
     Last->Scalars.insert(Last->Scalars.begin(), VL.begin(), VL.end());
-    Last->State = Vectorized ? TreeEntry::Vectorize : TreeEntry::NeedToGather;
+    Last->State = Vectorized ? State : TreeEntry::NeedToGather;
     Last->ReuseShuffleIndices.append(ReuseShuffleIndices.begin(),
                                      ReuseShuffleIndices.end());
     Last->ReorderIndices.append(ReorderIndices.begin(), ReorderIndices.end());
     Last->setOperations(S);
     if (Vectorized) {
       for (Value *V : VL) {
         assert(!getTreeEntry(V) && "Scalar already in tree!");
         ScalarToTreeEntry[V] = Last;
       }
       // Update the scheduler bundle to point to this TreeEntry.
       unsigned Lane = 0;
       for (ScheduleData *BundleMember = Bundle.getValue(); BundleMember;
            BundleMember = BundleMember->NextInBundle) {
         BundleMember->TE = Last;
         BundleMember->Lane = Lane;
         ++Lane;
case Instruction::Load: {
                              ReuseShuffleIndicies, CurrentOrder);
             TE->setOperandsInOrder();
             LLVM_DEBUG(dbgs() << "SLP: added a vector of jumbled loads.\n");
             findRootOrder(CurrentOrder);
             ++NumOpsWantToKeepOrder[CurrentOrder];
           }
           return;
         }
+        // Vectorizing non-consecutive loads with `llvm.masked.gather`.
+        TreeEntry *TE = newTreeEntry(
+            VL, Bundle /*vectorized*/, S, UserTreeIdx, ReuseShuffleIndicies,
+            /*ReorderIndices=*/None, TreeEntry::ScatterVectorize);
+        TE->setOperandsInOrder();
+        buildTree_rec(PointerOps, Depth + 1, {TE, 0});
+        LLVM_DEBUG(dbgs() << "SLP: added a vector of non-consecutive loads.\n");
+        return;
       }
 
       LLVM_DEBUG(dbgs() << "SLP: Gathering non-consecutive loads.\n");
       BS.cancelScheduling(VL, VL0);
       newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx,
                    ReuseShuffleIndicies);
       return;
     }
case Instruction::Load: {
       Align alignment = cast<LoadInst>(VL0)->getAlign();
       int ScalarEltCost =
           TTI->getMemoryOpCost(Instruction::Load, ScalarTy, alignment, 0,
                                CostKind, VL0);
       if (NeedToShuffleReuses) {
         ReuseShuffleCost -= (ReuseShuffleNumbers - VL.size()) * ScalarEltCost;
       }
       int ScalarLdCost = VecTy->getNumElements() * ScalarEltCost;
-      int VecLdCost =
-          TTI->getMemoryOpCost(Instruction::Load, VecTy, alignment, 0,
+      int VecLdCost;
+      if (E->State == TreeEntry::Vectorize) {
+        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.
         VecLdCost += TTI->getShuffleCost(
             TargetTransformInfo::SK_PermuteSingleSrc, VecTy);
       }
       return ReuseShuffleCost + VecLdCost - ScalarLdCost;
     }
     case Instruction::Store: {
       // We know that we can merge the stores. Calculate the cost.
if (NeedToShuffleReuses) {
         GatherSeq.insert(I);
         CSEBlocks.insert(I->getParent());
       }
     }
     E->VectorizedValue = Vec;
     return Vec;
   }
 
-  assert(E->State == TreeEntry::Vectorize && "Unhandled state");
+  assert((E->State == TreeEntry::Vectorize ||
+          E->State == TreeEntry::ScatterVectorize) &&
+         "Unhandled state");
   unsigned ShuffleOrOp =
       E->isAltShuffle() ? (unsigned)Instruction::ShuffleVector : E->getOpcode();
   Instruction *VL0 = E->getMainOp();
   Type *ScalarTy = VL0->getType();
   if (auto *Store = dyn_cast<StoreInst>(VL0))
     ScalarTy = Store->getValueOperand()->getType();
   auto *VecTy = FixedVectorType::get(ScalarTy, E->Scalars.size());
   switch (ShuffleOrOp) {
case Instruction::Load: {
       // Loads are inserted at the head of the tree because we don't want to
       // sink them all the way down past store instructions.
       bool IsReorder = E->updateStateIfReorder();
       if (IsReorder)
         VL0 = E->getMainOp();
       setInsertPointAfterBundle(E);
 
       LoadInst *LI = cast<LoadInst>(VL0);
+      Instruction *NewLI;
       unsigned AS = LI->getPointerAddressSpace();
+      Value *PO = LI->getPointerOperand();
+      if (E->State == TreeEntry::Vectorize) {
 
-      Value *VecPtr = Builder.CreateBitCast(LI->getPointerOperand(),
-                                            VecTy->getPointerTo(AS));
+        Value *VecPtr = Builder.CreateBitCast(PO, VecTy->getPointerTo(AS));
 
-      // The pointer operand uses an in-tree scalar so we add the new BitCast to
-      // ExternalUses list to make sure that an extract will be generated in the
-      // future.
-      Value *PO = LI->getPointerOperand();
+        // The pointer operand uses an in-tree scalar so we add the new BitCast
+        // to ExternalUses list to make sure that an extract will be generated
+        // in the future.
         if (getTreeEntry(PO))
-        ExternalUses.push_back(ExternalUser(PO, cast<User>(VecPtr), 0));
+          ExternalUses.emplace_back(PO, cast<User>(VecPtr), 0);
+
+        NewLI = Builder.CreateAlignedLoad(VecTy, VecPtr, LI->getAlign());
+      } else {
+        assert(E->State == TreeEntry::ScatterVectorize && "Unhandled state");
+        Value *VecPtr = vectorizeTree(E->getOperand(0));
+        NewLI = Builder.CreateMaskedGather(VecPtr, LI->getAlign());
+      }
+      Value *V = propagateMetadata(NewLI, E->Scalars);
 
-      LI = Builder.CreateAlignedLoad(VecTy, VecPtr, LI->getAlign());
-      Value *V = propagateMetadata(LI, 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");
       }
       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);
for (const auto &ExternalUse : ExternalUses) {
     llvm::User *User = ExternalUse.User;
 
     // Skip users that we already RAUW. This happens when one instruction
     // has multiple uses of the same value.
     if (User && !is_contained(Scalar->users(), User))
       continue;
     TreeEntry *E = getTreeEntry(Scalar);
     assert(E && "Invalid scalar");
-    assert(E->State == TreeEntry::Vectorize && "Extracting from a gather list");
+    assert(E->State != TreeEntry::NeedToGather &&
+           "Extracting from a gather list");
 
     Value *Vec = E->VectorizedValue;
     assert(Vec && "Can't find vectorizable value");
 
     Value *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.

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

 ;         S[0]                 S[1]
 ;
 ; SLP should reorder the operands of the RHS add taking into consideration the cost of external uses.
 ; It is more profitable to reorder the operands of the RHS add, because A[1] has an external use.
 
 define void @lookahead_external_uses(double* %A, double *%B, double *%C, double *%D, double *%S, double *%Ext1, double *%Ext2) {
 ; CHECK-LABEL: @lookahead_external_uses(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[IDXA0:%.*]] = getelementptr inbounds double, double* [[A:%.*]], i64 0
 ; CHECK-NEXT:    [[IDXB0:%.*]] = getelementptr inbounds double, double* [[B:%.*]], i64 0
 ; CHECK-NEXT:    [[IDXC0:%.*]] = getelementptr inbounds double, double* [[C:%.*]], i64 0
 ; CHECK-NEXT:    [[IDXD0:%.*]] = getelementptr inbounds double, double* [[D:%.*]], i64 0
-; CHECK-NEXT:    [[IDXA1:%.*]] = getelementptr inbounds double, double* [[A]], i64 1
+; CHECK-NEXT:    [[IDXA1:%.*]] = getelementptr inbounds double, double* [[A:%.*]], i64 1
 ; CHECK-NEXT:    [[IDXB2:%.*]] = getelementptr inbounds double, double* [[B]], i64 2
-; CHECK-NEXT:    [[IDXA2:%.*]] = getelementptr inbounds double, double* [[A]], i64 2
+; CHECK-NEXT:    [[TMP0:%.*]] = insertelement <2 x double*> undef, double* [[A]], i32 0
+; CHECK-NEXT:    [[TMP1:%.*]] = insertelement <2 x double*> [[TMP0]], double* [[A]], i32 1
+; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr double, <2 x double*> [[TMP1]], <2 x i64> <i64 0, i64 2>
 ; CHECK-NEXT:    [[IDXB1:%.*]] = getelementptr inbounds double, double* [[B]], i64 1
-; CHECK-NEXT:    [[A0:%.*]] = load double, double* [[IDXA0]], align 8
 ; CHECK-NEXT:    [[C0:%.*]] = load double, double* [[IDXC0]], align 8
 ; CHECK-NEXT:    [[D0:%.*]] = load double, double* [[IDXD0]], align 8
 ; CHECK-NEXT:    [[A1:%.*]] = load double, double* [[IDXA1]], align 8
 ; CHECK-NEXT:    [[B2:%.*]] = load double, double* [[IDXB2]], align 8
-; CHECK-NEXT:    [[A2:%.*]] = load double, double* [[IDXA2]], align 8
-; CHECK-NEXT:    [[TMP0:%.*]] = bitcast double* [[IDXB0]] to <2 x double>*
-; CHECK-NEXT:    [[TMP1:%.*]] = load <2 x double>, <2 x double>* [[TMP0]], align 8
-; CHECK-NEXT:    [[TMP2:%.*]] = insertelement <2 x double> undef, double [[C0]], i32 0
-; CHECK-NEXT:    [[TMP3:%.*]] = insertelement <2 x double> [[TMP2]], double [[A1]], i32 1
-; CHECK-NEXT:    [[TMP4:%.*]] = insertelement <2 x double> undef, double [[D0]], i32 0
-; CHECK-NEXT:    [[TMP5:%.*]] = insertelement <2 x double> [[TMP4]], double [[B2]], i32 1
-; CHECK-NEXT:    [[TMP6:%.*]] = fsub fast <2 x double> [[TMP3]], [[TMP5]]
-; CHECK-NEXT:    [[TMP7:%.*]] = insertelement <2 x double> undef, double [[A0]], i32 0
-; CHECK-NEXT:    [[TMP8:%.*]] = insertelement <2 x double> [[TMP7]], double [[A2]], i32 1
-; CHECK-NEXT:    [[TMP9:%.*]] = fsub fast <2 x double> [[TMP8]], [[TMP1]]
-; CHECK-NEXT:    [[TMP10:%.*]] = fadd fast <2 x double> [[TMP9]], [[TMP6]]
+; CHECK-NEXT:    [[TMP3:%.*]] = call <2 x double> @llvm.masked.gather.v2f64.v2p0f64(<2 x double*> [[TMP2]], i32 8, <2 x i1> <i1 true, i1 true>, <2 x double> undef)
+; CHECK-NEXT:    [[TMP4:%.*]] = extractelement <2 x double*> [[TMP2]], i32 0
+; CHECK-NEXT:    [[TMP5:%.*]] = bitcast double* [[IDXB0]] to <2 x double>*
+; CHECK-NEXT:    [[TMP6:%.*]] = load <2 x double>, <2 x double>* [[TMP5]], align 8
+; CHECK-NEXT:    [[TMP7:%.*]] = insertelement <2 x double> undef, double [[C0]], i32 0
+; CHECK-NEXT:    [[TMP8:%.*]] = insertelement <2 x double> [[TMP7]], double [[A1]], i32 1
+; CHECK-NEXT:    [[TMP9:%.*]] = insertelement <2 x double> undef, double [[D0]], i32 0
+; CHECK-NEXT:    [[TMP10:%.*]] = insertelement <2 x double> [[TMP9]], double [[B2]], i32 1
+; CHECK-NEXT:    [[TMP11:%.*]] = fsub fast <2 x double> [[TMP8]], [[TMP10]]
+; CHECK-NEXT:    [[TMP12:%.*]] = fsub fast <2 x double> [[TMP3]], [[TMP6]]
+; CHECK-NEXT:    [[TMP13:%.*]] = fadd fast <2 x double> [[TMP12]], [[TMP11]]
 ; CHECK-NEXT:    [[IDXS0:%.*]] = getelementptr inbounds double, double* [[S:%.*]], i64 0
 ; CHECK-NEXT:    [[IDXS1:%.*]] = getelementptr inbounds double, double* [[S]], i64 1
-; CHECK-NEXT:    [[TMP11:%.*]] = bitcast double* [[IDXS0]] to <2 x double>*
-; CHECK-NEXT:    store <2 x double> [[TMP10]], <2 x double>* [[TMP11]], align 8
+; CHECK-NEXT:    [[TMP14:%.*]] = bitcast double* [[IDXS0]] to <2 x double>*
+; CHECK-NEXT:    store <2 x double> [[TMP13]], <2 x double>* [[TMP14]], align 8
 ; CHECK-NEXT:    store double [[A1]], double* [[EXT1:%.*]], align 8
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %IdxA0 = getelementptr inbounds double, double* %A, i64 0
   %IdxB0 = getelementptr inbounds double, double* %B, i64 0
   %IdxC0 = getelementptr inbounds double, double* %C, i64 0
   %IdxD0 = getelementptr inbounds double, double* %D, i64 0

 ; CHECK-NEXT:    [[IDXA0:%.*]] = getelementptr inbounds double, double* [[A:%.*]], i64 0
 ; CHECK-NEXT:    [[IDXB0:%.*]] = getelementptr inbounds double, double* [[B:%.*]], i64 0
 ; CHECK-NEXT:    [[IDXC0:%.*]] = getelementptr inbounds double, double* [[C:%.*]], i64 0
 ; CHECK-NEXT:    [[IDXD0:%.*]] = getelementptr inbounds double, double* [[D:%.*]], i64 0
 ; CHECK-NEXT:    [[IDXA1:%.*]] = getelementptr inbounds double, double* [[A]], i64 1
 ; CHECK-NEXT:    [[IDXB2:%.*]] = getelementptr inbounds double, double* [[B]], i64 2
 ; CHECK-NEXT:    [[IDXA2:%.*]] = getelementptr inbounds double, double* [[A]], i64 2
 ; CHECK-NEXT:    [[IDXB1:%.*]] = getelementptr inbounds double, double* [[B]], i64 1
+; CHECK-NEXT:    [[A0:%.*]] = load double, double* [[IDXA0]], align 8
 ; CHECK-NEXT:    [[B0:%.*]] = load double, double* [[IDXB0]], align 8
 ; CHECK-NEXT:    [[C0:%.*]] = load double, double* [[IDXC0]], align 8
 ; CHECK-NEXT:    [[D0:%.*]] = load double, double* [[IDXD0]], align 8
-; CHECK-NEXT:    [[TMP0:%.*]] = bitcast double* [[IDXA0]] to <2 x double>*
-; CHECK-NEXT:    [[TMP1:%.*]] = load <2 x double>, <2 x double>* [[TMP0]], align 8
+; CHECK-NEXT:    [[A1:%.*]] = load double, double* [[IDXA1]], align 8
 ; CHECK-NEXT:    [[B2:%.*]] = load double, double* [[IDXB2]], align 8
 ; CHECK-NEXT:    [[A2:%.*]] = load double, double* [[IDXA2]], align 8
 ; CHECK-NEXT:    [[B1:%.*]] = load double, double* [[IDXB1]], align 8
-; CHECK-NEXT:    [[TMP2:%.*]] = insertelement <2 x double> undef, double [[B0]], i32 0
-; CHECK-NEXT:    [[TMP3:%.*]] = insertelement <2 x double> [[TMP2]], double [[B2]], i32 1
-; CHECK-NEXT:    [[TMP4:%.*]] = fsub fast <2 x double> [[TMP1]], [[TMP3]]
-; CHECK-NEXT:    [[TMP5:%.*]] = insertelement <2 x double> undef, double [[C0]], i32 0
-; CHECK-NEXT:    [[TMP6:%.*]] = insertelement <2 x double> [[TMP5]], double [[A2]], i32 1
-; CHECK-NEXT:    [[TMP7:%.*]] = insertelement <2 x double> undef, double [[D0]], i32 0
-; CHECK-NEXT:    [[TMP8:%.*]] = insertelement <2 x double> [[TMP7]], double [[B1]], i32 1
-; CHECK-NEXT:    [[TMP9:%.*]] = fsub fast <2 x double> [[TMP6]], [[TMP8]]
-; CHECK-NEXT:    [[TMP10:%.*]] = fadd fast <2 x double> [[TMP4]], [[TMP9]]
+; CHECK-NEXT:    [[SUBA0B0:%.*]] = fsub fast double [[A0]], [[B0]]
+; CHECK-NEXT:    [[SUBC0D0:%.*]] = fsub fast double [[C0]], [[D0]]
+; CHECK-NEXT:    [[SUBA1B2:%.*]] = fsub fast double [[A1]], [[B2]]
+; CHECK-NEXT:    [[SUBA2B1:%.*]] = fsub fast double [[A2]], [[B1]]
+; CHECK-NEXT:    [[ADD0:%.*]] = fadd fast double [[SUBA0B0]], [[SUBC0D0]]
+; CHECK-NEXT:    [[ADD1:%.*]] = fadd fast double [[SUBA1B2]], [[SUBA2B1]]
 ; CHECK-NEXT:    [[IDXS0:%.*]] = getelementptr inbounds double, double* [[S:%.*]], i64 0
 ; CHECK-NEXT:    [[IDXS1:%.*]] = getelementptr inbounds double, double* [[S]], i64 1
-; CHECK-NEXT:    [[TMP11:%.*]] = bitcast double* [[IDXS0]] to <2 x double>*
-; CHECK-NEXT:    store <2 x double> [[TMP10]], <2 x double>* [[TMP11]], align 8
-; CHECK-NEXT:    [[TMP12:%.*]] = extractelement <2 x double> [[TMP1]], i32 1
-; CHECK-NEXT:    store double [[TMP12]], double* [[EXT1:%.*]], align 8
-; CHECK-NEXT:    store double [[TMP12]], double* [[EXT2:%.*]], align 8
-; CHECK-NEXT:    store double [[TMP12]], double* [[EXT3:%.*]], align 8
+; CHECK-NEXT:    store double [[ADD0]], double* [[IDXS0]], align 8
+; CHECK-NEXT:    store double [[ADD1]], double* [[IDXS1]], align 8
+; CHECK-NEXT:    store double [[A1]], double* [[EXT1:%.*]], align 8
+; CHECK-NEXT:    store double [[A1]], double* [[EXT2:%.*]], align 8
+; CHECK-NEXT:    store double [[A1]], double* [[EXT3:%.*]], align 8
 ; CHECK-NEXT:    store double [[B1]], double* [[EXT4:%.*]], align 8
 ; CHECK-NEXT:    store double [[B1]], double* [[EXT5:%.*]], align 8
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %IdxA0 = getelementptr inbounds double, double* %A, i64 0
   %IdxB0 = getelementptr inbounds double, double* %B, i64 0
   %IdxC0 = getelementptr inbounds double, double* %C, i64 0

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN:  opt < %s -slp-vectorizer -instcombine -S -mtriple=x86_64-unknown-linux -mattr=+sse2     | FileCheck %s
 ; RUN:  opt < %s -slp-vectorizer -instcombine -S -mtriple=x86_64-unknown-linux -mattr=+avx      | FileCheck %s
 ; RUN:  opt < %s -slp-vectorizer -instcombine -S -mtriple=x86_64-unknown-linux -mattr=+avx2     | FileCheck %s
 ; RUN:  opt < %s -slp-vectorizer -instcombine -S -mtriple=x86_64-unknown-linux -mattr=+avx512f  | FileCheck %s
 ; RUN:  opt < %s -slp-vectorizer -instcombine -S -mtriple=x86_64-unknown-linux -mattr=+avx512vl | FileCheck %s
 
 
 @b = global [8 x i32] zeroinitializer, align 16
 @a = global [8 x i32] zeroinitializer, align 16
 
 define void @foo() {
-; CHECK-LABEL: @foo(
-; CHECK-NEXT:    [[TMP1:%.*]] = load i32, i32* getelementptr inbounds ([8 x i32], [8 x i32]* @b, i64 0, i64 0), align 16
-; CHECK-NEXT:    store i32 [[TMP1]], i32* getelementptr inbounds ([8 x i32], [8 x i32]* @a, i64 0, i64 0), align 16
-; CHECK-NEXT:    [[TMP2:%.*]] = load i32, i32* getelementptr inbounds ([8 x i32], [8 x i32]* @b, i64 0, i64 2), align 8
-; CHECK-NEXT:    store i32 [[TMP2]], i32* getelementptr inbounds ([8 x i32], [8 x i32]* @a, i64 0, i64 1), align 4
-; CHECK-NEXT:    store i32 [[TMP1]], i32* getelementptr inbounds ([8 x i32], [8 x i32]* @a, i64 0, i64 2), align 8
-; CHECK-NEXT:    store i32 [[TMP2]], i32* getelementptr inbounds ([8 x i32], [8 x i32]* @a, i64 0, i64 3), align 4
-; CHECK-NEXT:    store i32 [[TMP1]], i32* getelementptr inbounds ([8 x i32], [8 x i32]* @a, i64 0, i64 4), align 16
-; CHECK-NEXT:    store i32 [[TMP2]], i32* getelementptr inbounds ([8 x i32], [8 x i32]* @a, i64 0, i64 5), align 4
-; CHECK-NEXT:    store i32 [[TMP1]], i32* getelementptr inbounds ([8 x i32], [8 x i32]* @a, i64 0, i64 6), align 8
-; CHECK-NEXT:    store i32 [[TMP2]], i32* getelementptr inbounds ([8 x i32], [8 x i32]* @a, i64 0, i64 7), align 4
-; CHECK-NEXT:    ret void
+; SSE-LABEL: @foo(
+; SSE-NEXT:    [[TMP1:%.*]] = load i32, i32* getelementptr inbounds ([8 x i32], [8 x i32]* @b, i64 0, i64 0), align 16
+; SSE-NEXT:    store i32 [[TMP1]], i32* getelementptr inbounds ([8 x i32], [8 x i32]* @a, i64 0, i64 0), align 16
+; SSE-NEXT:    [[TMP2:%.*]] = load i32, i32* getelementptr inbounds ([8 x i32], [8 x i32]* @b, i64 0, i64 2), align 8
+; SSE-NEXT:    store i32 [[TMP2]], i32* getelementptr inbounds ([8 x i32], [8 x i32]* @a, i64 0, i64 1), align 4
+; SSE-NEXT:    store i32 [[TMP1]], i32* getelementptr inbounds ([8 x i32], [8 x i32]* @a, i64 0, i64 2), align 8
+; SSE-NEXT:    store i32 [[TMP2]], i32* getelementptr inbounds ([8 x i32], [8 x i32]* @a, i64 0, i64 3), align 4
+; SSE-NEXT:    store i32 [[TMP1]], i32* getelementptr inbounds ([8 x i32], [8 x i32]* @a, i64 0, i64 4), align 16
+; SSE-NEXT:    store i32 [[TMP2]], i32* getelementptr inbounds ([8 x i32], [8 x i32]* @a, i64 0, i64 5), align 4
+; SSE-NEXT:    store i32 [[TMP1]], i32* getelementptr inbounds ([8 x i32], [8 x i32]* @a, i64 0, i64 6), align 8
+; SSE-NEXT:    store i32 [[TMP2]], i32* getelementptr inbounds ([8 x i32], [8 x i32]* @a, i64 0, i64 7), align 4
+; SSE-NEXT:    ret void
+;
+; AVX-LABEL: @foo(
+; AVX-NEXT:    [[TMP1:%.*]] = call <2 x i32> @llvm.masked.gather.v2i32.v2p0i32(<2 x i32*> <i32* getelementptr inbounds ([8 x i32], [8 x i32]* @b, i64 0, i64 0), i32* getelementptr inbounds ([8 x i32], [8 x i32]* @b, i64 0, i64 2)>, i32 16, <2 x i1> <i1 true, i1 true>, <2 x i32> undef)
+; AVX-NEXT:    [[SHUFFLE:%.*]] = shufflevector <2 x i32> [[TMP1]], <2 x i32> undef, <8 x i32> <i32 0, i32 1, i32 0, i32 1, i32 0, i32 1, i32 0, i32 1>
+; AVX-NEXT:    store <8 x i32> [[SHUFFLE]], <8 x i32>* bitcast ([8 x i32]* @a to <8 x i32>*), align 16
+; AVX-NEXT:    ret void
 ;
   %1 = load i32, i32* getelementptr inbounds ([8 x i32], [8 x i32]* @b, i64 0, i64 0), align 16
   store i32 %1, i32* getelementptr inbounds ([8 x i32], [8 x i32]* @a, i64 0, i64 0), align 16
   %2 = load i32, i32* getelementptr inbounds ([8 x i32], [8 x i32]* @b, i64 0, i64 2), align 8
   store i32 %2, i32* getelementptr inbounds ([8 x i32], [8 x i32]* @a, i64 0, i64 1), align 4
   store i32 %1, i32* getelementptr inbounds ([8 x i32], [8 x i32]* @a, i64 0, i64 2), align 8
   store i32 %2, i32* getelementptr inbounds ([8 x i32], [8 x i32]* @a, i64 0, i64 3), align 4
   store i32 %1, i32* getelementptr inbounds ([8 x i32], [8 x i32]* @a, i64 0, i64 4), align 16
   store i32 %2, i32* getelementptr inbounds ([8 x i32], [8 x i32]* @a, i64 0, i64 5), align 4
   store i32 %1, i32* getelementptr inbounds ([8 x i32], [8 x i32]* @a, i64 0, i64 6), align 8
   store i32 %2, i32* getelementptr inbounds ([8 x i32], [8 x i32]* @a, i64 0, i64 7), align 4
   ret void
 }

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

 ; CHECK-NEXT:    [[TMP9:%.*]] = load i32, i32* [[TMP3]], align 4
 ; CHECK-NEXT:    [[TMP10:%.*]] = insertelement <4 x i32> undef, i32 [[TMP4]], i32 0
 ; CHECK-NEXT:    [[TMP11:%.*]] = insertelement <4 x i32> [[TMP10]], i32 [[TMP6]], i32 1
 ; CHECK-NEXT:    [[TMP12:%.*]] = insertelement <4 x i32> [[TMP11]], i32 [[TMP8]], i32 2
 ; CHECK-NEXT:    [[TMP13:%.*]] = insertelement <4 x i32> [[TMP12]], i32 [[TMP9]], i32 3
 ; CHECK-NEXT:    [[TMP14:%.*]] = add nsw <4 x i32> [[TMP13]], <i32 1, i32 2, i32 3, i32 4>
 ; CHECK-NEXT:    [[TMP15:%.*]] = bitcast i32* [[TMP0:%.*]] to <4 x i32>*
 ; CHECK-NEXT:    store <4 x i32> [[TMP14]], <4 x i32>* [[TMP15]], align 4
 ; CHECK-NEXT:    ret void
 ;
   %3 = getelementptr inbounds i32, i32* %1, i64 1
   %4 = load i32, i32* %1, align 4
   %5 = getelementptr inbounds i32, i32* %0, i64 1
   %6 = getelementptr inbounds i32, i32* %1, i64 11
   %7 = load i32, i32* %6, align 4
   %8 = getelementptr inbounds i32, i32* %0, i64 2
   %9 = getelementptr inbounds i32, i32* %1, i64 4

 ; SSE-NEXT:    store i32 [[T12]], i32* [[T9]], align 4
 ; SSE-NEXT:    store i32 [[T16]], i32* [[T13]], align 4
 ; SSE-NEXT:    store i32 [[T20]], i32* [[T17]], align 4
 ; SSE-NEXT:    store i32 [[T24]], i32* [[T21]], align 4
 ; SSE-NEXT:    store i32 [[T28]], i32* [[T25]], align 4
 ; SSE-NEXT:    store i32 [[T32]], i32* [[T29]], align 4
 ; SSE-NEXT:    ret void
 ;
-; AVX-LABEL: @gather_load_4(
-; AVX-NEXT:    [[T6:%.*]] = getelementptr inbounds i32, i32* [[T1:%.*]], i64 11
-; AVX-NEXT:    [[T10:%.*]] = getelementptr inbounds i32, i32* [[T1]], i64 4
-; AVX-NEXT:    [[T14:%.*]] = getelementptr inbounds i32, i32* [[T1]], i64 15
-; AVX-NEXT:    [[T18:%.*]] = getelementptr inbounds i32, i32* [[T1]], i64 18
-; AVX-NEXT:    [[T22:%.*]] = getelementptr inbounds i32, i32* [[T1]], i64 9
-; AVX-NEXT:    [[T26:%.*]] = getelementptr inbounds i32, i32* [[T1]], i64 6
-; AVX-NEXT:    [[T30:%.*]] = getelementptr inbounds i32, i32* [[T1]], i64 21
-; AVX-NEXT:    [[T3:%.*]] = load i32, i32* [[T1]], align 4
-; AVX-NEXT:    [[T7:%.*]] = load i32, i32* [[T6]], align 4
-; AVX-NEXT:    [[T11:%.*]] = load i32, i32* [[T10]], align 4
-; AVX-NEXT:    [[T15:%.*]] = load i32, i32* [[T14]], align 4
-; AVX-NEXT:    [[T19:%.*]] = load i32, i32* [[T18]], align 4
-; AVX-NEXT:    [[T23:%.*]] = load i32, i32* [[T22]], align 4
-; AVX-NEXT:    [[T27:%.*]] = load i32, i32* [[T26]], align 4
-; AVX-NEXT:    [[T31:%.*]] = load i32, i32* [[T30]], align 4
-; AVX-NEXT:    [[TMP1:%.*]] = insertelement <8 x i32> undef, i32 [[T3]], i32 0
-; AVX-NEXT:    [[TMP2:%.*]] = insertelement <8 x i32> [[TMP1]], i32 [[T7]], i32 1
-; AVX-NEXT:    [[TMP3:%.*]] = insertelement <8 x i32> [[TMP2]], i32 [[T11]], i32 2
-; AVX-NEXT:    [[TMP4:%.*]] = insertelement <8 x i32> [[TMP3]], i32 [[T15]], i32 3
-; AVX-NEXT:    [[TMP5:%.*]] = insertelement <8 x i32> [[TMP4]], i32 [[T19]], i32 4
-; AVX-NEXT:    [[TMP6:%.*]] = insertelement <8 x i32> [[TMP5]], i32 [[T23]], i32 5
-; AVX-NEXT:    [[TMP7:%.*]] = insertelement <8 x i32> [[TMP6]], i32 [[T27]], i32 6
-; AVX-NEXT:    [[TMP8:%.*]] = insertelement <8 x i32> [[TMP7]], i32 [[T31]], i32 7
-; AVX-NEXT:    [[TMP9:%.*]] = add <8 x i32> [[TMP8]], <i32 1, i32 2, i32 3, i32 4, i32 1, i32 2, i32 3, i32 4>
-; AVX-NEXT:    [[TMP10:%.*]] = bitcast i32* [[T0:%.*]] to <8 x i32>*
-; AVX-NEXT:    store <8 x i32> [[TMP9]], <8 x i32>* [[TMP10]], align 4
-; AVX-NEXT:    ret void
+; AVX1-LABEL: @gather_load_4(
+; AVX1-NEXT:    [[T5:%.*]] = getelementptr inbounds i32, i32* [[T0:%.*]], i64 1
+; AVX1-NEXT:    [[T6:%.*]] = getelementptr inbounds i32, i32* [[T1:%.*]], i64 11
+; AVX1-NEXT:    [[T9:%.*]] = getelementptr inbounds i32, i32* [[T0]], i64 2
+; AVX1-NEXT:    [[T10:%.*]] = getelementptr inbounds i32, i32* [[T1]], i64 4
+; AVX1-NEXT:    [[T13:%.*]] = getelementptr inbounds i32, i32* [[T0]], i64 3
+; AVX1-NEXT:    [[T14:%.*]] = getelementptr inbounds i32, i32* [[T1]], i64 15
+; AVX1-NEXT:    [[T17:%.*]] = getelementptr inbounds i32, i32* [[T0]], i64 4
+; AVX1-NEXT:    [[T18:%.*]] = getelementptr inbounds i32, i32* [[T1]], i64 18
+; AVX1-NEXT:    [[T21:%.*]] = getelementptr inbounds i32, i32* [[T0]], i64 5
+; AVX1-NEXT:    [[T22:%.*]] = getelementptr inbounds i32, i32* [[T1]], i64 9
+; AVX1-NEXT:    [[T25:%.*]] = getelementptr inbounds i32, i32* [[T0]], i64 6
+; AVX1-NEXT:    [[T26:%.*]] = getelementptr inbounds i32, i32* [[T1]], i64 6
+; AVX1-NEXT:    [[T29:%.*]] = getelementptr inbounds i32, i32* [[T0]], i64 7
+; AVX1-NEXT:    [[T30:%.*]] = getelementptr inbounds i32, i32* [[T1]], i64 21
+; AVX1-NEXT:    [[T3:%.*]] = load i32, i32* [[T1]], align 4
+; AVX1-NEXT:    [[T7:%.*]] = load i32, i32* [[T6]], align 4
+; AVX1-NEXT:    [[T11:%.*]] = load i32, i32* [[T10]], align 4
+; AVX1-NEXT:    [[T15:%.*]] = load i32, i32* [[T14]], align 4
+; AVX1-NEXT:    [[T19:%.*]] = load i32, i32* [[T18]], align 4
+; AVX1-NEXT:    [[T23:%.*]] = load i32, i32* [[T22]], align 4
+; AVX1-NEXT:    [[T27:%.*]] = load i32, i32* [[T26]], align 4
+; AVX1-NEXT:    [[T31:%.*]] = load i32, i32* [[T30]], align 4
+; AVX1-NEXT:    [[T4:%.*]] = add i32 [[T3]], 1
+; AVX1-NEXT:    [[T8:%.*]] = add i32 [[T7]], 2
+; AVX1-NEXT:    [[T12:%.*]] = add i32 [[T11]], 3
+; AVX1-NEXT:    [[T16:%.*]] = add i32 [[T15]], 4
+; AVX1-NEXT:    [[T20:%.*]] = add i32 [[T19]], 1
+; AVX1-NEXT:    [[T24:%.*]] = add i32 [[T23]], 2
+; AVX1-NEXT:    [[T28:%.*]] = add i32 [[T27]], 3
+; AVX1-NEXT:    [[T32:%.*]] = add i32 [[T31]], 4
+; AVX1-NEXT:    store i32 [[T4]], i32* [[T0]], align 4
+; AVX1-NEXT:    store i32 [[T8]], i32* [[T5]], align 4
+; AVX1-NEXT:    store i32 [[T12]], i32* [[T9]], align 4
+; AVX1-NEXT:    store i32 [[T16]], i32* [[T13]], align 4
+; AVX1-NEXT:    store i32 [[T20]], i32* [[T17]], align 4
+; AVX1-NEXT:    store i32 [[T24]], i32* [[T21]], align 4
+; AVX1-NEXT:    store i32 [[T28]], i32* [[T25]], align 4
+; AVX1-NEXT:    store i32 [[T32]], i32* [[T29]], align 4
+; AVX1-NEXT:    ret void
+;
+; AVX2-LABEL: @gather_load_4(
+; AVX2-NEXT:    [[T5:%.*]] = getelementptr inbounds i32, i32* [[T0:%.*]], i64 1
+; AVX2-NEXT:    [[TMP1:%.*]] = insertelement <4 x i32*> undef, i32* [[T1:%.*]], i32 0
+; AVX2-NEXT:    [[TMP2:%.*]] = shufflevector <4 x i32*> [[TMP1]], <4 x i32*> undef, <4 x i32> zeroinitializer
+; AVX2-NEXT:    [[TMP3:%.*]] = getelementptr i32, <4 x i32*> [[TMP2]], <4 x i64> <i64 11, i64 4, i64 15, i64 18>
+; AVX2-NEXT:    [[T21:%.*]] = getelementptr inbounds i32, i32* [[T0]], i64 5
+; AVX2-NEXT:    [[T22:%.*]] = getelementptr inbounds i32, i32* [[T1]], i64 9
+; AVX2-NEXT:    [[T25:%.*]] = getelementptr inbounds i32, i32* [[T0]], i64 6
+; AVX2-NEXT:    [[T26:%.*]] = getelementptr inbounds i32, i32* [[T1]], i64 6
+; AVX2-NEXT:    [[T29:%.*]] = getelementptr inbounds i32, i32* [[T0]], i64 7
+; AVX2-NEXT:    [[T30:%.*]] = getelementptr inbounds i32, i32* [[T1]], i64 21
+; AVX2-NEXT:    [[T3:%.*]] = load i32, i32* [[T1]], align 4
+; AVX2-NEXT:    [[TMP4:%.*]] = call <4 x i32> @llvm.masked.gather.v4i32.v4p0i32(<4 x i32*> [[TMP3]], i32 4, <4 x i1> <i1 true, i1 true, i1 true, i1 true>, <4 x i32> undef)
+; AVX2-NEXT:    [[T23:%.*]] = load i32, i32* [[T22]], align 4
+; AVX2-NEXT:    [[T27:%.*]] = load i32, i32* [[T26]], align 4
+; AVX2-NEXT:    [[T31:%.*]] = load i32, i32* [[T30]], align 4
+; AVX2-NEXT:    [[T4:%.*]] = add i32 [[T3]], 1
+; AVX2-NEXT:    [[TMP5:%.*]] = add <4 x i32> [[TMP4]], <i32 2, i32 3, i32 4, i32 1>
+; AVX2-NEXT:    [[T24:%.*]] = add i32 [[T23]], 2
+; AVX2-NEXT:    [[T28:%.*]] = add i32 [[T27]], 3
+; AVX2-NEXT:    [[T32:%.*]] = add i32 [[T31]], 4
+; AVX2-NEXT:    store i32 [[T4]], i32* [[T0]], align 4
+; AVX2-NEXT:    [[TMP6:%.*]] = bitcast i32* [[T5]] to <4 x i32>*
+; AVX2-NEXT:    store <4 x i32> [[TMP5]], <4 x i32>* [[TMP6]], align 4
+; AVX2-NEXT:    store i32 [[T24]], i32* [[T21]], align 4
+; AVX2-NEXT:    store i32 [[T28]], i32* [[T25]], align 4
+; AVX2-NEXT:    store i32 [[T32]], i32* [[T29]], align 4
+; AVX2-NEXT:    ret void
+;
+; AVX512-LABEL: @gather_load_4(
+; AVX512-NEXT:    [[T5:%.*]] = getelementptr inbounds i32, i32* [[T0:%.*]], i64 1
+; AVX512-NEXT:    [[TMP1:%.*]] = insertelement <4 x i32*> undef, i32* [[T1:%.*]], i32 0
+; AVX512-NEXT:    [[TMP2:%.*]] = shufflevector <4 x i32*> [[TMP1]], <4 x i32*> undef, <4 x i32> zeroinitializer
+; AVX512-NEXT:    [[TMP3:%.*]] = getelementptr i32, <4 x i32*> [[TMP2]], <4 x i64> <i64 11, i64 4, i64 15, i64 18>
+; AVX512-NEXT:    [[T21:%.*]] = getelementptr inbounds i32, i32* [[T0]], i64 5
+; AVX512-NEXT:    [[T22:%.*]] = getelementptr inbounds i32, i32* [[T1]], i64 9
+; AVX512-NEXT:    [[T25:%.*]] = getelementptr inbounds i32, i32* [[T0]], i64 6
+; AVX512-NEXT:    [[T26:%.*]] = getelementptr inbounds i32, i32* [[T1]], i64 6
+; AVX512-NEXT:    [[T29:%.*]] = getelementptr inbounds i32, i32* [[T0]], i64 7
+; AVX512-NEXT:    [[T30:%.*]] = getelementptr inbounds i32, i32* [[T1]], i64 21
+; AVX512-NEXT:    [[T3:%.*]] = load i32, i32* [[T1]], align 4
+; AVX512-NEXT:    [[TMP4:%.*]] = call <4 x i32> @llvm.masked.gather.v4i32.v4p0i32(<4 x i32*> [[TMP3]], i32 4, <4 x i1> <i1 true, i1 true, i1 true, i1 true>, <4 x i32> undef)
+; AVX512-NEXT:    [[T23:%.*]] = load i32, i32* [[T22]], align 4
+; AVX512-NEXT:    [[T27:%.*]] = load i32, i32* [[T26]], align 4
+; AVX512-NEXT:    [[T31:%.*]] = load i32, i32* [[T30]], align 4
+; AVX512-NEXT:    [[T4:%.*]] = add i32 [[T3]], 1
+; AVX512-NEXT:    [[TMP5:%.*]] = add <4 x i32> [[TMP4]], <i32 2, i32 3, i32 4, i32 1>
+; AVX512-NEXT:    [[T24:%.*]] = add i32 [[T23]], 2
+; AVX512-NEXT:    [[T28:%.*]] = add i32 [[T27]], 3
+; AVX512-NEXT:    [[T32:%.*]] = add i32 [[T31]], 4
+; AVX512-NEXT:    store i32 [[T4]], i32* [[T0]], align 4
+; AVX512-NEXT:    [[TMP6:%.*]] = bitcast i32* [[T5]] to <4 x i32>*
+; AVX512-NEXT:    store <4 x i32> [[TMP5]], <4 x i32>* [[TMP6]], align 4
+; AVX512-NEXT:    store i32 [[T24]], i32* [[T21]], align 4
+; AVX512-NEXT:    store i32 [[T28]], i32* [[T25]], align 4
+; AVX512-NEXT:    store i32 [[T32]], i32* [[T29]], align 4
+; AVX512-NEXT:    ret void
 ;
   %t5 = getelementptr inbounds i32, i32* %t0, i64 1
   %t6 = getelementptr inbounds i32, i32* %t1, i64 11
   %t9 = getelementptr inbounds i32, i32* %t0, i64 2
   %t10 = getelementptr inbounds i32, i32* %t1, i64 4
   %t13 = getelementptr inbounds i32, i32* %t0, i64 3
   %t14 = getelementptr inbounds i32, i32* %t1, i64 15
   %t17 = getelementptr inbounds i32, i32* %t0, i64 4