[VPlan] Move mayHaveSideeffects for FORs check to VPlan.

[fhahn]

Summary

This patch moves the check if sink candidate may have sideeffects to
VPlan. Unfortunately this requires adding logic to try to convert
first-order recurrence phis to induction phis with an assumption. This
is because Legal tries to convert phis to inductions using PSE if they
cannot be converted to a FOR.

The current state of this patch is not ideal, the question is if there's
a better option to handle the fallback to predicated inductions.

[peterwaller-arm]

Are there other parent revisions? The base isn't a valid commit and the patch doesn't apply to main nor commits from the end of January, for example CompareByComesBefore isn't in the patch context but is on main and is old.

[fhahn]

Rebase and ping :)

In D142895#4155253, @peterwaller-arm wrote:

Are there other parent revisions? The base isn't a valid commit and the patch doesn't apply to main nor commits from the end of January, for example CompareByComesBefore isn't in the patch context but is on main and is old.

Sorry about that, there's been multiple strands of related improvements in flight, but most have landed now. This patch should now apply on current main and I'll also update the later patches in the series.

[fhahn]

Fix build failures after rebase.

[peterwaller-arm]

Doesn't build for me, tried against main (8bf7f86d7966) and your latest commit to vplan (668045eb7762).

../../llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp:791:27: error: no member named 'getOrAddVPValue' in 'llvm::VPlan'; did you mean 'getVPValue'?
    VPValue *Start = Plan.getOrAddVPValue(ID.getStartValue());
                          ^~~~~~~~~~~~~~~
                          getVPValue
../../llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp:794:21: error: no matching constructor for initialization of 'llvm::VPWidenIntOrFpInductionRecipe'
    auto *Ind = new VPWidenIntOrFpInductionRecipe(Phi, Start, Step, ID);
                    ^                             ~~~~~~~~~~~~~~~~~~~~

[fhahn]

Rebase again on current main, should apply and build now!

[fhahn]

rebase and ping :)

[Ayal]

This attempt to reclassify a header phi as an IV-Under-Predicates after failing to classify it initially as a FOR, raises some thoughts...

1. There are clearly header phi's P that are FORs but not IVUnderP's. E.g., when a load that appears above all of P’s users feeds P as its Previous.
2. There are clearly header phi's that are IVUnderP's but are not FORs, in the sense that placing a splice alone cannot handle their vectorization. E.g., a simple IV whose bump may wrap.
3. There are header phi's P that are both IVUnderP and FORs. E.g., a plain IV feeding a wrapping instruction (trunc/ext/and/shl/shr/rem) that feeds P as its Previous. This is a case we may currently fail to recognize as FOR, e.g., when P is used by a store located above Previous, because we only try to sink P's users below Previous giving up if any such user has side-effects, e.g., is a store, regardless of what Previous may be. But note that in this case Previous depends only on an AddRec Phi & bump cycle, so should be hoistable (along with dependents) as close as needed to their AddRec Phi, passing above P's users. It’s worth trying to sink stores as much as possible, i.e., past non-memory and non-aliased instructions (D143604, D143605), but control-flow may still hinder such motion.
4. If a header phi can be considered as either IVUnderP or FOR, should the latter be preferred, as currently and initially argued, chosing IVUnderP only "as last resort"? The former discards wrap-around instructions from within the loop and produces AddRecs that may serve vector loads, stores and interleave groups. The latter avoids specializing the vector loop under no-wrap predicates.
5. Perhaps the best is to try and identify each IVUnderP(*) as a “Wrapping IV”, i.e., not as a general splice-able FOR nor as a non-wrapping IV under predicates. If its wrapping is known to take place only at VF boundaries, it could serve vector loads and stores similar to AddRec. This "piecewise consecutive" behavior is reminiscent of the "piecewise uniform" raised in D148841.

(*) Regardless if the IVUnderP can or cannot be considered also as a FOR.