This is reminiscent of LV's interleave group optimization, in the sense that a couple of correlated inefficient vector "gathers" are replaced by a couple of efficiently formed vectors followed by transposing shuffles. The correlated gathers may come from the two operands of a binary operation, as in this patch, or more generally from arbitrary leaves of the SLP tree.

Looks good to me, thanks for addressing the issues, have only a few last minor suggestions.

Have test(s) for extractvalue's, for completeness.
Make sure tests cover best-order selection: cases where original order is just as frequent as other orders (tie-break), less frequent, more frequent.

See MaximizeBandwidth, as in
llvm-dev's Enable vectorizer-maximize-bandwidth by default?
patch: Enable vectorizer-maximize-bandwidth by default.
which is still reverted afaik: r306936 - Revert "r306473 - re-commit r306336: Enable vectorizer-maximize-bandwidth by default."

This patch addresses the following TODO, plus handles extracts:

In D36130#1004306, @ashahid wrote:

Hi Ayal, Sanjoy,

The last update's review was pending for long. Off late, SLP has lots of changes so I will have to rebase but before rebasing please see if any more changes required in its current form.

Thanks in advance.

In D36130#973399, @ashahid wrote:

In D36130#971181, @Ayal wrote:

This should fix the case observed by @sanjoy in http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20171218/511721.html; please also include a testcase.

Test case, test/Transforms/SLPVectorizer/X86/external_user_jumbled_load.ll, already included.

This should fix the case observed by @sanjoy in http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20171218/511721.html; please also include a testcase.

Presumably this fixes the reported regressions?

Just to formally close this review, as it wasn't closed by the commit.

This looks good to me, with a couple of last minor fixes.

This looks good to me, but please wait for Silviu to approve as well before committing.

LGTM, thanks for taking this out of D38948 and into a separate commit.

In D36130#946236, @ashahid wrote:

In D36130#945728, @Ayal wrote:

Good catch. Add a LIT test?

It was asserting in few of LNT Multisource bench mark. How to extract it for LIT test?

In D28975#946240, @rengolin wrote:

Hi Ayal,

This functionality has been submitted already, right? If so, please close this review.

Thanks,
--renato

Good catch. Add a LIT test?

Nice catch! Continuing to use SCEV and expect consistent answers in the midst of restructuring the IR is indeed wrong; its cache is not meant to cover for cases that can no longer be analyzed as before.

A few additional minor comments..

In D38785#913785, @dorit wrote:

In short, I think we are all in agreement that:

1. This patch is a (small) improvement, * regardless of the users and their specific cost considerations *.
2. The cost-model aspect of deciding when to specialize for a certain stride needs to be improved. The users (LV especially) are currently not making informed decisions.
   
   …Right?

Indeed, a loop with an iteration count smaller than VF is definitely not worth vectorizing. An interesting profitability issue is to decide how many iterations past VF suffice to amortize vectorization overheads. In any case, this single/no iteration case looks like a no-brainer and realistic case - traversing a column of an NxN matrix.

In D36130#885328, @ashahid wrote:

The regression test result is as follows. There are 2 failures coming from Clang however these failures are also observed without this patch.

Can you provide a reproducer? Best is to open a PR and continue this discussion there. See e.g. https://bugs.llvm.org/show_bug.cgi?id=34711, which also contains a suggested fix to be upstreamed, which might apply to your case as well.

Agreed, revisiting the ReverseConsecutive/NumLoadsWantToChangeOrder/shouldReorder() logic in view of general shuffled loads deserves a separate patch.

This was closed due to committing r312331, right? Code LGTM, for the record. Tests for interleaved loads of float/pointer should still be added, as this patch presumably handles them too.

@Ayal, any other comments or does this look good to go? Thanks.

In D36130#866073, @ashahid wrote:

In D36130#863237, @Ayal wrote:

In D36130#861823, @ashahid wrote:

0143_001.pdf19 KB

Download

Yes, thanks, the example is clear. I agree that having OpdNums allows to represent such cases where two shuffles from the same load are to feed two distinct operands of the same user. But the SLP vectorizer with this patch alone will not optimize such patterns, right? Take for example jumbled-load.ll above; to match the case depicted in the pdf, replace the zeroes used as the 2nd operands of the cmp's and/or of the select's by a shuffle (same as that of the 1st operand or different).

Yes, that's right. However right now I am not clear what needs to be done to optimize those pattern. I also tried another simple case, where 2 different Shuffle from same LOAD is fed into
a MUL. Here, for VF=4, SLP reports "Scalar used twice in bundle" and removes redundant scalar operations instead of vectorization. Consequently, the STOREs of the results of the MULs does not get vectorized. May be we need to do a trade-off between scalar vs vector code here.

Only additional comment is whether the test needs to be X86/skx specific, or whether it can be placed in, say, memdep.ll

In D36130#861823, @ashahid wrote:

0143_001.pdf19 KB

Download

In D35498#857495, @rengolin wrote:

Sorry, slight overlap. Please follow Ayal's comments before committing.

3. Moved tests to Codegen/ARM. The crash disappears without arm tuple so can't remove it

Fix PR34248: pack a predicated scalar into a vector only when vectorizing; avoid doing so when only unrolling. Add a test derived from the reproducer of PR34248.

In D36130#847707, @ashahid wrote:

In D36130#847002, @Ayal wrote:

sortMemAccesses() is analogous to the formation of InterleaveGroups in the LoopVectorizer, which also scans a collection of Loads (or Stores) to determine if they are adjacent in some order and can be combined into one Vector Load of a given width; and if so, in what order. This requires a single scan to compute the distances relative to the first access, as done here. But knowing that we're looking for a permutation of a given width, we can more easily sort the accesses as they are entered into a map, holding the minimum and maximum indices. See insertMember() there.

Thanks Ayal for your comments.
As this is a long pending work and my current focus is to add this feature in SLP. I welcome your suggestions and would like to consider in a separate patch after this.

@sbaranga, can you clarify my comments and help me understand this better? Hopefully this could move forward.

sortMemAccesses() is analogous to the formation of InterleaveGroups in the LoopVectorizer, which also scans a collection of Loads (or Stores) to determine if they are adjacent in some order and can be combined into one Vector Load of a given width; and if so, in what order. This requires a single scan to compute the distances relative to the first access, as done here. But knowing that we're looking for a permutation of a given width, we can more easily sort the accesses as they are entered into a map, holding the minimum and maximum indices. See insertMember() there.

Previous upload missed newly added VPlan.h and VPlan.cpp, including them here. This is the version that was committed.

Uploading the version updated to top of trunk before committing, including merging with SinkAfter patch D33058 by reordering ingredients before constructing recipes for them.

Is it worth adding a test case for this? I'm not sure...

Looks good to me, please wait for @mssimpso to approve.

Instead of refraining to vectorize a loop which has an externally used phi (or rather the bump thereof) and any predicate, can a predicate be added (or an existing one be extended) to also cover the last iteration? Pity to bail out on such corner cases.

In D35725#817510, @mssimpso wrote:

This looks fine to me, but I don't quite follow why the patch is needed. Are we just trying to match what the VPlan recipe will eventually do?

Ping

In D35498#813120, @rengolin wrote:

... Or maybe we just load them as "data" (i32/i64?) and then bitcast safely?

Makes sense?

Added the following comment following review, and updated a testcase that was recently modified (if-conversion-nest.ll)

In D34150#802750, @mkuper wrote:

Re overflow - the point is that getOrCreateTripCount() returns, basically, PSE.getBackedgeTakenCount() + 1, and that may overflow, so the "trip count" may end up being 0 if the backedge taken count is 0. I don't think this is outdated, and this is behavior we want to preserve. But this patch should preserve this behavior IIUC.

Patch updated to llvm trunk, adapted to the new ValueMap interface of D34473. ValueMap is extracted to a standalone struct VectorizerValueMap.

ping

Updated version includes the comment requested by @hfinkel.

Updated version addresses review comments.

Yes, we saw a couple of ~7% improvements running eembc benchmarks on x86.

An alternative interface which may be simpler and clearer ... it may be better done in a separate patch.

This has been conceptually approved, but is pending:

In D33058#751569, @mssimpso wrote:
I'm wondering if it's worth extending this to handle other kinds of instructions/expressions.

Updated following review comments.

(Addressing review comments; To be completed)

Done. Will upload updated version shortly.