Fixed comment containing this D94974 revision number

You are planning to revert this patch after ConstantData use-list removing, am I right?

Yes, thanks.

Looks good, but could you please precommit test (and rebase) to see actual output difference?

LGTM

In-short: I'm still do sure that current patch is bugfixing. But this bug had induced some of boundary vectorization cases before fixing. Below is a typical case.

In D93192#2451838, @xbolva00 wrote:

Kinda big impact on code size

https://llvm-compile-time-tracker.com/compare.php?from=6c8ded0d8c3c256defaf72c0596614eea465ca27&to=fac7c7ec3ccd64d19b6d33af0a8bc2f3f7f7b047&stat=size-text

Is it ok? No performance regressions?

In D57059#2442286, @RKSimon wrote:

AFAICT the only outstanding question is whether the compile time increase is acceptable?

In D92824#2439575, @RKSimon wrote:

@anton-afanasyev Please can you rebase? I added extra test coverage in rG41d0666391131ddee451085c72ba6513872e7f6c

Rebase

In D91919#2439339, @RKSimon wrote:

Actually NFC now, since stores could be only seed entry, but we collect only consecutive stores there for now. It will be changed in future commits.

Are you looking at supporting non-consecutive stores? This patch probably shouldn't be reviewed until we actually have something that uses and tests it.

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

I'm agree with @fhahn -- tuning cost model is more right way. Also it could be the case of arch where gathers are missing but it's beneficial to use them for vectorization tree building. They are lowered to scalarized instrs further.

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

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