Btw, I've observed significant compile-time regression with this patch: http://llvm-compile-time-tracker.com/compare.php?from=99d82412f822190a6caa3e3a5b9f87b71f56de47&to=81b636bae72c967f526bcd18de45a6f4a76daa41&stat=instructions (thanks to @nikic for awesome service). This could be justified in case of comparable performance improvements but have you done any benchmarking?

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.

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

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.

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.

Align fix. Style fix.

Analogue of https://reviews.llvm.org/D90445 for stores.

In D90445#2402312, @bkramer wrote:

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

Fixed

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

Added another assert

Fixes and assert

Add overloaded newTreeEntry() for common case

Fix test, CHECK prefix is unused

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

Added optional EntryState param to newTreeEntry()

Add comment

In D90445#2391375, @dtemirbulatov wrote:

Also, please add ScatterVectorize to TreeEntry.dump()

Small fix of debug printer

Fixed asserts again

Assert fix

Added asserts

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)

Use of EntryState

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?

Renamed IsScatteredOps to IsScatteredOpds

Added second tree entry for addresses

Addressed notes

Rebased

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

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

Rebased against changed test file

Updated comments and LaneIndex

Addressed comments

Addressed comments

Fixed

Addressed

Fixed

Addressed comments

Ping. Rebase.

Updated

Addressed @ABataev's comments.

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

In D83779#2153039, @ABataev wrote:

In D83779#2150568, @xbolva00 wrote:

Add test?

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

Update tests

In D83779#2150568, @xbolva00 wrote:

Add test?

In D74516#1913475, @fedor.sergeev wrote:

I'm sorry for the late comment, but this should have really been done through the PassInstrumentation framework.
It looks like a classic use-case.

Here is the another patch for new pm support: D74516

I've faced with objections from @philip.pfaffe trying to implement the same: D62067. Since that time, trace profiler has supported multiple threads (D71059), so I do believe this can now correctly work. I would wait for review from new pm guys.

In D72689#1819130, @xbolva00 wrote:

I saw similar thing in recent research

https://www.nextgenvec.org/slides/revec-cc.pdf

They proposed a new compiler pass to perform revectorization.

Did you look at it? What do you think?

Update AAMDNodes constructors