Ahh, the culprit here is a chain of FOR phi-users all sinking after a Previous - the latter should never be dead, but any member of the chain may by dead.
In the test case: %rec.2 is the FOR phi, %rec.2.prev is Previous, and {%cmp, %C, %B2} is the chain of users, where %B2 is dead as it feeds the loop's conditional branch only.

Good catch! Please remember to add a testcase along with D100260.

This looks good to me, adding final minor nits.

Minor comments and suggestions. This should compete the handling of sinking a recipe after another, thanks!

This looks good to me, thanks!
Title might emphasize "[LV] Try to sink multiple users ..."
Noting another couple of TODO thoughts.

In D84951#2777544, @fhahn wrote:

In D84951#2776110, @Ayal wrote:

The instructions to sink reside inside the header block in the desired order. It should be possible to traverse them, once, from the FOR phi to the terminator or Previous, w/o sorting nor changing order, by maintaining the set of phi's (direct and indirect) users. When encountering such a user during the traversal, check if it is sunkable, append it to be moved after the last sunken user (or after Previous if this is the first user being sunk), and add its users to the set - those that belong to the header block, others need to be dominated by (and distinct from) Previous.
Perhaps this would also help support sinking memory instructions in the future.
Sounds reasonable?

IIUC your suggestion would require to iterate over the instructions in the header block compared to just traversing the def-use chains from the PHI we are analyzing as we do at the moment? That would work, as we would visit the candidates in the correct order. But requiring to potentially iterate over all instructions in the header block might be worse in practice than sorting the (probably few) instructions that require sinking?

It will be indeed required once we want to sink memory operations, but until then it seems to me that just traversing the def-use chains + sorting would probably be less work in general for the cases we currently support (also given the interface that requires us to analyze each FOR separately). Please let me know if I understood correctly. Happy to update the patch as suggested if you think it's beneficial on its own.

Looks good to me, thanks!

Thanks for the changes!
Few remaining nits.

In D84951#2760659, @fhahn wrote:

Rebased, update to also avoid sinking instructions that may read from memory, as we cannot move them over ones with side-effects, move sort to isFirstOrderRecurrence.

In D84951#2753861, @Ayal wrote:

How about making SinkAfter a MapVector instead of DenseMap (to have its iteration order match insertion order) and insert interdependent sink candidates in the desired order?
How about traversing all insns from phi to previous, in order, checking if any is using the phi or a prior insn that was sunk? E.g., by maintaining the set of their users.
This might be clearer, and avoid the sorting.

I'm not sure if it is possible to maintain the order by dominance in the map as we go along, because we an instruction could be used by multiple others and we may visit them in reverse dominance order (relative to each other), so we would miss the fact we need to 'fix' the order of the first instruction. I think it is also difficult & expensive to change the order of multiple entries in the map vector.

I added a few more interesting scenarios as tests in 68d52f0dbe2e and c62f984814c4.

I *think* however it should be enough to sort only sort the instructions to sink per FOR phi, as we currently allow sinking for each instruction only once. That should certainly be better, as we have less to sort overall and everything is contained in IVDescriptor.cpp. The new code already maintains a vector of instructions to sink, so the sort fits in quite nicely. WDYT?

Nice optimization exercising VPlan capabilities!
Should always be a win, so ok to avoid cost-model considerations, although cost improvement is left unaccounted for.
An alternative may be to try and build larger replicating regions to begin with, but sinkScalarOperands may contribute as well.

How about making SinkAfter a MapVector instead of DenseMap (to have its iteration order match insertion order) and insert interdependent sink candidates in the desired order?
How about traversing all insns from phi to previous, in order, checking if any is using the phi or a prior insn that was sunk? E.g., by maintaining the set of their users.
This might be clearer, and avoid the sorting.

In D100257#2733025, @gilr wrote:

The anticipated long-term need for non-recipe VPUsers is indeed to represent live-outs, along with their underlying IR Value, or rather Instruction; analogous to VPValue::getLiveInIRValue(). This would call for a derived VPLiveOut non-recipe subclass of VPUser.

VPUser class itself should probably be pure virtual, similar to User, to avoid having a potential kitchen sink of dangling opaque instances. Instead of representing arbitrary "other"/"non-recipe" instances, the current VPUsers of VPBasicBlock predicates and conditions could be represented as specific, concrete subclasses of VPUser, potentially until they are cleaned up. WDYT?

This looks good, thanks for fixing, adding a couple of nits.

This is fine, thanks!

In D100257#2725020, @fhahn wrote:

In D100257#2718728, @Ayal wrote:

Non-recipe "other" VPUsers are quite exceptional ... would it suffice to have (native) VPlan hold all 'dangling' non-recipe VPUsers of its VPBasicBlocks, as an alternative, until these are cleaned up?

The blocks need to use the VPUsers to access the current value they hold I think, so I am not sure how the VPlan holding the VPUsers would look like unfortunately. It would be great if you could elaborate in a bit more detail, in case I am missing something.

Looks good to me, adding a minor nit; worth adding "NFC" to title.

Adding a couple of related thoughts. Thanks!

Reducing the coupling with the cost model by using information directly in VPlan is great. Have a few comments.

Looks good to me!

Non-recipe "other" VPUsers are quite exceptional ... would it suffice to have (native) VPlan hold all 'dangling' non-recipe VPUsers of its VPBasicBlocks, as an alternative, until these are cleaned up?

Looks good to me!
Adding a couple of nits and thoughts.
Perhaps "[VPlan] Representing backedge def-use feeding reduction phi's" may be a more accurate title - "incoming" also (more-so?) applies to the operand from the preheader.

Thanks @fhahn for moving this forward!
Have mostly minor nits.

This looks good to me, thanks!

ok, please land independent changes separately, thanks!

(how) are the VPPredInstPHIRecipe changes related to the introduction of getLiveInIRValue()?

In D93317#2472174, @fhahn wrote:

LGTM, thanks! I pushed a small fix for the crash discussed earlier in 0ea3749b3cde. It should be a very safe/straight-forward fix, but I would appreciate taking a look post-review.

Good step towards representing more Values, and in particular recording InductionDescriptor information, in VPlan!

This currently requires giving access to VPValue to those classes, so we
can call the protected constructor. But most of them can be removed in
the future, once the remaining single value def recipes inherit from
VPValue.

Good catch and fix! Minor post-commit comments.

In D93317#2470271, @fhahn wrote:

I think there are some scenarios when we break some LCSSA PHIs that use PHIs created during SCEV expansion when we generate the runtime checks. After a first glance, it appears like an issue after we add the conditional branch from the middle block. The example below should cause a verifier failure with opt -loop-vectorize -force-vector-width=4. I tried to reduce it a bit, but unfortunately it is still quite ugly.

This looks fine to me, thanks; would be good to get @fhahn approval too.

Nice leverage of requiresScalarEpilogue!
Looks good to me, adding some minor comments.

This looks good to me, adding some minor comments. Thanks!

In D66720#2413499, @Kryukova_l_p wrote:

@Ayal Hi.
Found a problem caused by these changes.
Take a look, please. I posted about it here https://bugs.llvm.org/show_bug.cgi?id=47390

I attach the file here too, after the bug point:

reduced-simplified.ll18 KBDownload

Run like this:
opt -passes=loop-vectorize 'reduced-simplified.ll' -S

Could you take a look?
Thanks in advance.

This looks good to me, thanks!

In D88380#2393587, @dmgreen wrote:

OK sounds great. I did not know that MLIR could represent multiple values, that's good to see.

I still like honestly like a more "llvm" Value/User model more, but perhaps as I read the patches I will learn to like Defs too.

Looks good to me, adding minor comments, thanks for pushing this forward!

Extending the recipe abstraction to support def/use relations is an important next step forward for VPlan, thanks for pushing this momentum forward!

This looks good to me, thanks!

This looks good to me, as part of the effort to support VPlan def-use modeling and traversals.
Note that top-down traversal from VPValue to its VPUsers, will now need to check if each VPUser isa single-def recipe/VPInstruction in order to continue downwards to its VPUsers, etc., facilitating multi-def recipes.

In D83470#2142057, @fhahn wrote:

LGTM, thanks!

In such cases, the loop vectorizer should either re-run the analysis or bail-out from vectorizing the loop, as done prior to D81345. The latter is chosen for now as the former requires refactoring.

As already discussed in D81345, ideally LV would have more flexibility to drive LAA, but this requires non-trivial refactoring. Which we should do, but until then the patch looks like a reasonable fix to the crash.

Good catch!

This looks good to me, thanks! with last couple of nits.

In D81416#2136421, @AaronLiu wrote:

In the application we try, LV refuse to vectorize due to not profitable, but if we force LV to vectorize and it will crash. Apparently there are some obstacles. There are cases that even if LV fails, SLP could succeed.

In D81416#2096034, @AaronLiu wrote:

In D81416#2095961, @spatel wrote:

IIUC, we should add a test under test/Transforms/PhaseOrdering with -O2 to show the cooperative effect of the 2 vectorizers rather than a stand-alone SLP test.
If you can push that test with full baseline CHECK lines and then apply this patch and show test diffs, that would make it much easier to tell what is intended with this patch.

Thanks for the comment. This patch does not intend to change or test phase ordering. In this patch, we interleave for small loops with scalar reductions which cannot be vectorized by LV, and later on SLP captures the opportunities. Interleaving is done by LV, and vectorization is done by SLP.

Looks good to me, thanks for following-up on this suggestion from D79976.

The proposed RecurrenceDescriptor::getReductionOpChain() method identifies horizontal reductions, a subset of the vertical reductions identified by RecurrenceDescriptor::isReductionPHI(). Being two totally independent methods, it's unclear what the latter supports that the former does not. Would it be better to have isReductionPHI() also take care of recognizing horizontal reductions, and record them as in CastsToIgnore? See also TODO commented inline.

Thanks!

In D80870#2066895, @manojgupta wrote:

D80491 has been breaking our ToT builds for a week now. Can this be submitted soon. If not please consider reverting D80491.

Alternatively we could force the computed max VF to the next-lowest power-of-2

Looks good to me. Added a minor nit.