Sorry, I meant to do a more thorough review before approving. I had a closer look today and found some nits and a couple of questions. Please see inline comments.

OK great. It sounds like there's agreement on the further direction overall and we can work on that in-tree. I'll work on getting the pieces ready to handle live-ins/live-outs in VPlan as required. As for the sekeleton creator, I might be able to take a look over the next week.

LGTM, thanks (meant to respond a bit earlier today :)

Forgot to remove target triple and attributes from target independent tests. They're fixed now.

Thank you for your reviews @SjoerdMeijer @fhahn .

Rebased, addressed comments, and added more tests (including one for the limited case of live-out supported).

Yeah, that could be the case. There are some (micro)benchmarks with a very small execution time, so more susceptible to fluctuations. Have you tried the CTMark subset and TEST_SUITE_BENCHMARKING_ONLY variable? Anyway, if it is too noisy, it was at least a good testing exercise.

I've tried both CTMark and TEST_SUITE_BENCHMARKING_ONLY .

Add link to the doc in comments.

Update llvm docs.

Addressed more comments.

In D89566#2385184, @SjoerdMeijer wrote:

This is a big change, and here are some notes from my first pass reading through this. Some high level questions here, and find some questions inlined:

• Think we need a doc update with the new vectorization skeleton? The picture in the description of this change? Don't know how feasible that is, some ascii art too as comments?

Sure, I had a similar comment in D88819. I find the textual graph horrendous. I'll create a section under https://llvm.org/docs/Vectorizers.html and put the diagram there.

In D89566#2383507, @SjoerdMeijer wrote:

My observations here are:

• Performance of both patches for SPEC are the same. The advantage of D88819 on ThunderX2 might be a coincidence (knock on effect, e.g. (loop) alignment) or some micro-architecture reason.
• This patch D89566 can handle more loops, but it is not reflected in the SPEC numbers (cold/not executed code?).
• The beauty of D88819 is that the changes are very minimal, but looks like it's worth spending extra lines of code here in D89566 to helps in vectorising more.

To me, that shows there's more potential with this patch.
I don't think I can be the arbiter in this, so it's best if other reviewers comment too.

In D89566#2383591, @xbolva00 wrote:

No regressions so enable by default?

Update test cases for default enablement.

Here are the numbers for SPEC2017 intrate suite on POWER9:

In D89566#2379500, @Prashanth wrote:

In D89566#2379432, @bmahjour wrote:

Just checking/summarising: is there consensus that this is the patch that is going to do epilogue vectorisation, and not D88819? Or does that depend on perf numbers as Florian suggested?

I think we should go with this, unless @fhahn finds that D88819 can outperform it (unlikely). There are more loops that can be transformed with this patch and I've listed other advantages in the description. @mivnay do you agree?

Are you blocking D88819 without running benchmarks? i.e. Without a comparison on any one of the architectures. For x264, D88819 might give better numbers....

Just checking/summarising: is there consensus that this is the patch that is going to do epilogue vectorisation, and not D88819? Or does that depend on perf numbers as Florian suggested?

Addressed code review comments + check for optsize and minsize.

In D89566#2371597, @dmgreen wrote:

I have not looked at any of the details here, but a very high level comment is that this isn't very VPlany. If we do want to push things in that direction, then it is at least worth thinking about how this and vplan will co-exist, even if vplan isn't ready for it yet. It would be great to get to a point where all this information is in the vplan and we can compare epilog remainders vs scalar remainders vs whatever else, and come up with a good total cost based on the estimated trip count. Just something to think about.

ping!

Removed executePlanForEpilogueVectorization, improved code reuse for creatInductionResumeValues, and added more test coverage including a case with double IV.

ping!

Please see D89566 for the alternative approach.

But setting things up as in the suggested CFG is going to be a bit more tricky and might not turn out to be much simpler in the end. I might give it a try to see if it's feasible.

I also agree with @mivnay's summary above and the general approach of just running ILV again on the remainder loop with the available vplan. If we mark the epilogue loop and put it back in the worklist, it'll be harder/uglier to then modify the CFG to make it more optimal. I do, however, think that the implementation can be improved (see my note below). Please also note that the SCEV and runtime checks cannot be avoided by marking them "noalias" (or similar tricks) because if the iteration count of the loop is small enough to by-pass the main vector loop and large enough to execute the vector epilogue, then the runtime checks need to be executed for the epilogue loop. The only way to avoid the redundant runtime checks is to generate the smaller trip count check first, as illustrated in the CFG I've posted above.

This approach doesn't work when most of the trip counts are always good for original vector loop. In fact, it even performs one additional trip count check when both vector loop and epilog vector loops are executed. For example, if original VF=16 and UF=2, and epilog VF=8 and UF=1, trip count as small as 40 requires 3 trip count checks. Where as, it is 2 in the current implementation.

Thanks for working on epilogue vectorization. Incidentally I've also looked into this recently. There has been a long and detailed discussion on the mailing list from back in 2017 about this transformation here http://llvm.1065342.n5.nabble.com/llvm-dev-Proposal-RFC-Epilog-loop-vectorization-td106322.html. Your patch is able to vectorize epilogue loops with fairly small changes to the LV, however the generated CFG is not optimal. For example, while the SCEV and memory checks are not redundantly executed, they are statically duplicated in the code and increase code size unnecessarily. The trip count checks can also be generated in a way that shortens the critical path from the checks to the scalar loop, which is critical for loops that have a small trip count. Based on the followup discussions from the mentioned RFC, the optimal CFG should look more like what I've attached below.

In D84951#2310611, @xbolva00 wrote:

Any futher comments, @bmahjour?

I think such an option is fine as a temporary stop-gap solution, but the goal should be to fix the underlying issue IMO.

The long term solution would be to make loop-idiom consider compile-time or PGO loop trip count data when deciding to transform loops. For non-constant non-PGO cases the cost modeling would be a heuristic at best, in which case the option would still be useful.

@lebedev.ri

I'd like to see a PhaseOrdering test showing the IR that is not optimized due to the DA being unaware about these intrinsics.

Given that interleaving alone (without vectorization) can still cause major performance improvements shows that this is really an interleaving profitability issue, so the heuristic and the option seem ok to me. To enable the option by default we would need more testing on other platforms. That can be done in a separate patch.

Another way that loop idiom can hurt performance is by creating imperfect loop nests. Certain transformations (such as loop interchange and unroll-and-jam) are more difficult (sometimes impossible) to do when loop nests are not perfect.

I agree with that, it seems to be better to improve DA. Is it feasible?

The theory of data dependence analysis relies on presence of subscripts in array references to be able to produce accurate results. I don't see how we can "improve DA" to address memset/memcpies short of turning them back into loop nests before applying the dependence tests. To do that the loop has to either be materialized before the DA analysis pass is run, or somehow SCEV expressions representing the implied subscripts be synthesized out of thin air. The former must be achieved by a transformation pass, so we would have to turn memset/memcpys into loop nests as soon as possible. For memset/memcpy calls generated by the loop idiom pass, the ideal place for that transformation would be immediately after loop idiom itself, which would have the same effect as preventing loop idiom from creating such loops in the first place when it knows they are not profitable. I don't know of any possible way to do the latter.

This patch only improves things for LCSSA phis, not for other trivial phis (multiple equal incoming values).

It would be good to clarify this in the title then.

rebase

@nemanjai has kindly provided a fix https://reviews.llvm.org/rG62a933b72c5b060bcb2c7332d05082f002d6c65a.

Some of the tests added in llvm/test/Analysis/ScalarEvolution/trivial-phis.ll come from https://reviews.llvm.org/D71492 but don't have the same expected results. @fhahn do you plan to improve those in this patch or a subsequent patch, or were you planning to leave those to me in D71492?

This can be closed in favor of https://reviews.llvm.org/D84589. Please migrate the tests and close the review. Thanks.

fix clang-format issue.

Address @pjeeva01 's comments, and sync with ToT.

Ping!

Added some minor comments. Overall looks good to me. I'll approve if there are no objections by EOD today.

Please put NFC in the title if no functional changes are intended. The same comment applies to D80580. Thanks.

May I suggest we only test what this patch actually changes? This patch adds an option which when enabled allows interleaving of loops with small trip counts and scalar reductions, so it suffices to test exactly that. That should be covered by llvm/test/Transforms/LoopVectorize/PowerPC/interleave_IC.ll. I think the other test cases can be removed. IMHO adding more tests to make sure SLP vectorization happens (and the like) are redundant, add unnecessary maintenance in the future and are beyond the scope of what this patch is trying to do.