Update summary

Refactored code, removed new TreeEntry::State. Make InsertElementInst passing through ordinary scheduling, allowing inner deps for bundle of insertelements.

Closed by commit: https://reviews.llvm.org/rG9abe50047330
(modified summary a bit to comply with changes)

LGTM except for the comment. I think MaxVecRegSize % EltSize != 0 check could be removed (together with comment).

Closed by commit https://reviews.llvm.org/rGdd90c36d601e

Sorry, prematurely closed this revision by mistake.

In D98596#2629238, @bule wrote:

In D98596#2629211, @anton-afanasyev wrote:

In D98596#2629181, @bule wrote:

Fix the duplicate element error that cause the failure in CI

Ok, is it working now? I could commit it on your behalf.

Thanks a lot, I am waiting for the build status. Does it still need anton @anton-afanasyev to review it first? since I have changed the code a lot.

In D98596#2629181, @bule wrote:

Fix the duplicate element error that cause the failure in CI

The same work is resumed here: D98714, so abandoning this.

Here is another fix approach: https://reviews.llvm.org/D98714

LGTM

I'm trying another approach here, so abandoned this for a while.

Also could you please precommit test or just make diff against it (to see test changes before/after patch)?

LGTM

LG after addressing all comments.

Actually, it is not reducing. This is how test-suite python script works. So, here lhs - number of instructions after this patch, rhs - before. And the less relative number, the more vector instructions we actually generate.

In D57059#2555233, @ABataev wrote:

This is an integral patch, going to split it into several smaller patches.

Btw, how could it be explained NumVectorInstructions stat reducing after this patch?

Added fp2int scalar and vector test cases

I can add fp2int sample, but it is not touched by this patch. Actually, its tree built is not vectorized by marking as "tiny" (R.isTreeTinyAndNotFullyVectorizable() function), its size is 2 (since fp2int is unary operation, whereas add is binary one). Though it could be fixed by checking that stores are using its result and therefore tree size could be increased. But this looks too hacky, isn't it?

Cleaned pr40522.ll

In D96791#2565982, @ABataev wrote:

I think the better approach would be to pass the list of InsertUses as a buildTree function UserIgnoreLst argument. You just need to correctly generate ExtractElement instructions for these InsertElements because currently the compiler just crashes trying to remove instructions used as operands for the original InsertElements. Thoughts?

LGTM

Due to what said above, I'm to abandon this change. It looks like over-optimization, breaking llvm IR middle-end abstraction.

At Dinar's request, I've measured compile time regression: http://llvm-compile-time-tracker.com/compare.php?from=f3449ed6073cac58efd9b62d0eb285affa650238&to=39362e11add238c45a7a7d55c1e002005f396fb7&stat=instructions. The regression is visible, but it is acceptable for such change imho. The largest regression comes from CMakeFiles/clamscan.dir/libclamav_uuencode.c.o (+11.28%), so one can investigate this particular file.

Clean up tests

Small test fix

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