Update LV to also use the VPlan-based addMinimumIterationCheck for the
iteration count check for the epilogue.
As the VPlan-based addMinimumIterationCheck uses VPExpandSCEV, those
need to be placed in the entry block for now, moving vscale * VF * IC to
the entry for scalable vectors.
The new logic also fails to simplify some checks involving PtrToInt,
because they were only simplified when going through generated IR, then
folding some PtrToInt in IR, then constructing SCEVs again. But those
should be cleaned up by later combines, and there is not really much we
can do other than trying to go through IR.
PR: https://github.com/llvm/llvm-project/pull/189372
Following on from PR #188091 I've also removed the following function
attributes from tests:
nounwind uwtable ssp
as they didn't make any difference to the tests.
Following #146525, separate the reverse mask from reverse access
recipes.
At the same time, remove the unused member variable `Reverse` from
`VPWidenMemoryRecipe`.
This will help to reduce redundant reverse mask computations by
VPlan-based common subexpression elimination.
Due to a somewhat recent change, IntOrFpInduction recipes have
associated VPIRFlags. The VPlanUnroll logic for WidenInduction recipes
predates this change, and computes incomplete wrap-flags: update it to
simply use the flags on IntOrFpInduction recipes; PointerInduction
recipes have no associated flags, and indeed, no flags should be used.
This reverts commit 4562a953db9d9813a873b78144cee1df39c7e0c0.
The recommit adjusts processLaneForReplicateRegion to first remap all
operands, then update the new operands. This fixes a VPlan verification
failure when running LV tests with expensive checks.
Original message:
This patch adds a new replicateReplicateRegionsByVF transform to unroll
replicate=regions by VF, dissolving them. The transform creates VF
copies of the replicate-region's content, connects them and converts
recipes to single-scalar variants for the corresponding lanes.
The initial version skips regions with live-outs (VPPredInstPHIRecipe),
which will be added in follow-up patches.
Depends on https://github.com/llvm/llvm-project/pull/170053
PR: https://github.com/llvm/llvm-project/pull/170212
This patch adds a new replicateReplicateRegionsByVF transform to
unroll replicate=regions by VF, dissolving them. The transform creates
VF copies of the replicate-region's content, connects them and converts
recipes to single-scalar variants for the corresponding lanes.
The initial version skips regions with live-outs (VPPredInstPHIRecipe),
which will be added in follow-up patches.
Depends on https://github.com/llvm/llvm-project/pull/170053
PR: https://github.com/llvm/llvm-project/pull/170212
When not folding the tail the minimum iteration count check ensures that
the vector loop is not executed if computing the trip count wraps around
to zero, as the trip count must be at least VF when vectorizing without
tail-folding.
Add and use a new tryToRefineConstantMaxTripCount helper. This ensures
we do not create dead main loops when vectorizing the epilogue, as we
choose smaller main VFs.
PR: https://github.com/llvm/llvm-project/pull/188135
This reverts commit e30f9c19464bcf1bf1e9f69b63884fb78ad2d05d.
Re-land, now that the reported crash causing the revert has been fixed
as part of 77fb84889 (#187504).
Original message:
Replace manual region dissolution code in
simplifyBranchConditionForVFAndUF with using general
removeBranchOnConst. simplifyBranchConditionForVFAndUF now just creates
a (BranchOnCond true) or updates BranchOnTwoConds.
The loop then gets automatically removed by running removeBranchOnConst.
This removes a bunch of special logic to handle header phi replacements
and CFG updates. With the new code, there's no restriction on what kind
of header phi recipes the loop contains.
Note that VPEVLBasedIVRecipe needs to be marked as readnone. This is
technically unrelated, but I could not find an independent test that
would be impacted.
The code to deal with epilogue resume values now needs updating, because
we may simplify a reduction directly to the start value.
PR: https://github.com/llvm/llvm-project/pull/181252
This reverts commit cdaf29f84dd0abbd1f961982799059c92d76625b.
This version skips removeBranchOnConst when vectorizing the epilogue, as
it may trigger folds that remove the resume phi used as resume value
from the epilogue.
This fixes https://github.com/llvm/llvm-project/issues/187323.
Original message:
This patch tries to drastically simplify resume value handling for the
scalar loop when vectorizing the epilogue.
It uses a simpler, uniform approach for updating all resume values in
the scalar loop:
1. Create ResumeForEpilogue recipes for all scalar resume phis in the
main loop (the epilogue plan will have exactly the same scalar resume
phis, in exactly the same order)
2. Update ::execute for ResumeForEpilogue to set the underlying value
when executing. This is not super clean, but allows easy lookup of the
generated IR value when we update the resume phis in the epilogue. Once
we connect the 2 plans together explicitly, this can be removed.
3. Use the list of ResumeForEpilogue VPInstructions from the main loop
to update the resume/bypass values from the epilogue.
This simplifies the code quite a bit, makes it more robust (should fix
https://github.com/llvm/llvm-project/issues/179407) and also fixes a
mis-compile in the existing tests (see change in
llvm/test/Transforms/LoopVectorize/AArch64/partial-reduce-sub-epilogue-vec.ll,
where previously we would incorrectly resume using the start value when
the epilogue iteration check failed)
In some cases, we get simpler code, due to additional CSE, in some cases
the induction end value computations get moved from the epilogue
iteration check to the vector preheader. We could try to sink the
instructions as cleanup, but it is probably not worth the trouble.
Fixes https://github.com/llvm/llvm-project/issues/179407.
PR for recommit https://github.com/llvm/llvm-project/pull/188134
`LoopVectorizationCostModel::getPredBlockCostDivisor(...)` may return
large `uint64_t` values that get coerced to an `unsigned` by
`VPCostContext::getPredBlockCostDivisor(...)`, which can cause division
by zero.
Fixes#187584
This patch tries to drastically simplify resume value handling for the
scalar loop when vectorizing the epilogue.
It uses a simpler, uniform approach for updating all resume values in
the scalar loop:
1. Create ResumeForEpilogue recipes for all scalar resume phis in the
main loop (the epilogue plan will have exactly the same scalar resume
phis, in exactly the same order)
2. Update ::execute for ResumeForEpilogue to set the underlying value
when executing. This is not super clean, but allows easy lookup of the
generated IR value when we update the resume phis in the epilogue. Once
we connect the 2 plans together explicitly, this can be removed.
3. Use the list of ResumeForEpilogue VPInstructions from the main loop
to update the resume/bypass values from the epilogue.
This simplifies the code quite a bit, makes it more robust (should fix
https://github.com/llvm/llvm-project/issues/179407) and also fixes a
mis-compile in the existing tests (see change in
llvm/test/Transforms/LoopVectorize/AArch64/partial-reduce-sub-epilogue-vec.ll,
where previously we would incorrectly resume using the start value when
the epilogue iteration check failed)
In some cases, we get simpler code, due to additional CSE, in some cases
the induction end value computations get moved from the epilogue
iteration check to the vector preheader. We could try to sink the
instructions as cleanup, but it is probably not worth the trouble.
Fixes https://github.com/llvm/llvm-project/issues/179407.
Some VPlan transforms, like vectorizing fmin without fast-math,
introduce AnyOfs, which have costs assigned in the VPlan-based cost
model, but not the legacy cost model. Account for their cost like done
for other similar VPInstrctions, like EVL.
Fixes https://github.com/llvm/llvm-project/issues/185867.
When narrowInterleaveGroups transforms a plan, VF and VFxUF are
materialized (replaced with concrete values). This patch also
materializes the VectorTripCount in the same transform.
This ensures that VectorTripCount is properly computed when the narrow
interleave transform is applied, instead of using the original VF
+ UF to compute the vector trip count. The previous behavior generated
correct code, but executed fewer iterations in the vector loop.
The change also enables stricter verification prevent accesses of UF,
VF, VFxUF etc after materialization as follow-up.
Note that in some cases we no miss branch folding, but that should be
addressed separately, https://github.com/llvm/llvm-project/pull/181252
Fixes one of the violations accessing a VectorTripCount after UF and VF
being materialized
PR: https://github.com/llvm/llvm-project/pull/182146
This duplicates #182313 with some very small modifications on top, as
@dheaton-arm is unable
to finish the PR and I'm unable to push to his branch.
Expands support for the `FindLast` Reccurence Kind to floating-point and
pointer types, thereby
enabling conditional scalar assignment (CSA) for these types.
Originally authored by @dheaton-arm
---------
Co-authored-by: Damian Heaton <Damian.Heaton@arm.com>
This reverts commit d7e037c8383e66e5c07897f144f6d8ef47258682.
Recommit with a small fix to properly handle ordered reductions when
connecting the epilogue.
Original message:
Replace manual region dissolution code in
simplifyBranchConditionForVFAndUF with using general
removeBranchOnConst. simplifyBranchConditionForVFAndUF now just creates
a (BranchOnCond true) or updates BranchOnTwoConds.
The loop then gets automatically removed by running removeBranchOnConst.
This removes a bunch of special logic to handle header phi replacements
and CFG updates. With the new code, there's no restriction on what kind
of header phi recipes the loop contains.
Note that VPEVLBasedIVRecipe needs to be marked as readnone. This is
technically unrelated, but I could not find an independent test that
would be impacted.
The code to deal with epilogue resume values now needs updating, because
we may simplify a reduction directly to the start value.
PR: https://github.com/llvm/llvm-project/pull/181252
This extends the existing support to work with arbitrary interleave
factors. The main change here is reworking the ExtractLastActive
VPInstruction to take a variable amount of arguments and handling it in
unrollRecipeByUF and VPInstruction::generate.
The select condition for all mask/data values in a find-last recurrence
is the true if the mask for any part is true. Because of this the masks
for inactive parts will be updated to all-false when the parts with
active lanes are updated. This ensures the mask/data for last active
element always corresponds to the greatest part with an active lane.
This means finding the last element in the middle block simply requires
chaining the `extract.last.active` to forward the result from the last
active part through any inactive parts ahead of it.
Canonicalize GEP source element types from `%T` to `[sizeof(%T) x i8]`.
This is intended to flush out any remaining places that rely on GEP
element types, as part of the `ptradd` migration. The impact of this
change is expected to be fairly minimal (we might enable a few more
hoist/sink style folds that depend on equal GEP types).
Remove the use of function attributes no-nans-fp-math and
no-signed-zeros-fp-math in FP min/max reduction detection. The required
fast-math flags nnan and nsz should be present on the intrinsic calls,
fcmp and select instructions themselves.
Licm can now sink reverse VPInstructions outside the loop region; they
won't be considered when computing costs. Account for that in
planContainsAdditionalSimplifications.
Fixes https://github.com/llvm/llvm-project/issues/183592.
Replace manual region dissolution code in
simplifyBranchConditionForVFAndUF with using general
removeBranchOnConst. simplifyBranchConditionForVFAndUF now just creates
a (BranchOnCond true) or updates BranchOnTwoConds.
The loop then gets automatically removed by running removeBranchOnConst.
This removes a bunch of special logic to handle header phi replacements
and CFG updates. With the new code, there's no restriction on what kind
of header phi recipes the loop contains.
Note that VPEVLBasedIVRecipe needs to be marked as readnone. This is
technically unrelated, but I could not find an independent test that
would be impacted.
The code to deal with epilogue resume values now needs updating, because
we may simplify a reduction directly to the start value.
PR: https://github.com/llvm/llvm-project/pull/181252
After #183080, the canonical IV (not the increment!) can't overflow. So
now canonical IVs that are unrolled will have steps that don't overflow,
so we can add the nuw flag.
This allows us to tighten the VPlanVerifier isKnownMonotonic check by
restricting it to adds with nuw.
This reverts commit b0b3e3e1c7f6387eabc2ef9ff1fea311e63a4299.
After thinking about this for a bit, I don't think this is correct.
vscale being a power-of-2 only guarantees the canonical IV increment
overflows to zero, but not overflows in general.
After #183080 vscale can no longer be a non-power of 2, which means the
canonical IV can't overflow with tail folding w/ scalable vectors
anymore. Therefore we don't need to drop the NUW flag.
IVUpdateMayOverflow is left to be removed in a separate PR since it
removes further runtime checks.
Now that we have ExitingIVValue, we can also use it for tail-folded
loops; the only difference is that we have to compute the end value with
the original trip count instead the vector trip count.
This allows removing the induction increment operand only used when
tail-folding.
PR: https://github.com/llvm/llvm-project/pull/182507
When canonicalizing GEPs to have a single index, only ignore the first
leading zero index. This fixes a hole in the canonicalization in case
there was a struct zero offset, which can't be removed by the the
leading zero stripping.
The legacy cost model skips gather/scatters when determining the
predicated stores in useEmulatedMaskMemRefHack. Match the behavior in
the VPlan-based implementation. This fixes a cost divergence in the
attached test.
Directly unroll VectorEndPointerRecipe following 0636225b ([VPlan]
Directly unroll VectorPointerRecipe, #168886). It allows us to leverage
existing VPlan simplifications to optimize.
Co-authored-by: Luke Lau <luke@igalia.com>
Co-authored-by: Florian Hahn <flo@fhahn.com>
This reverts commit 8d29d09309654541fb2861524276ada6a3ebf84c.
The underlying issue causing the revert has been fixed independently
as 301fa24671256734df6b7ee65f23ad885400108e.
Original message:
Move narrowInterleaveGroups to to general VPlan optimization stage.
To do so, narrowInterleaveGroups now has to find a suitable VF where all
interleave groups are consecutive and saturate the full vector width.
If such a VF is found, the original VPlan is split into 2:
a) a new clone which contains all VFs of Plan, except VFToOptimize, and
b) the original Plan with VFToOptimize as single VF.
The original Plan is then optimized. If a new copy for the other VFs has
been created, it is returned and the caller has to add it to the list of
candidate plans.
Together with https://github.com/llvm/llvm-project/pull/149702, this
allows to take the narrowed interleave groups into account when
computing costs to choose the best VF and interleave count.
One example where we currently miss interleaving/unrolling when
narrowing interleave groups is https://godbolt.org/z/Yz77zbacz
PR: https://github.com/llvm/llvm-project/pull/149706
In some cases, LV gets simplifyable IR as input. Directly apply
simplifications on the initial VPlan0 to avoid vectorization in cases
where the loop body can be folded away.
Using the end-to-end pipeline, this is relatively rare, but when
reducing test cases, the reduction often ends up with cases with trivial
folds. Rejecting those will result in more robust & realistic test
cases.
As follow-up, I also plan to add initial dead recipe removal.
Depends on https://github.com/llvm/llvm-project/pull/176795.
PR: https://github.com/llvm/llvm-project/pull/176828
We reassociate ((x && y) && z) -> (x && (y && z)) if x has more than
use, in order to allow simplifying the header mask further. However this
is somewhat unreliable as there are times when it doesn't have more than
one use, e.g. see the case we run into in
https://github.com/llvm/llvm-project/pull/173265/changes#r2769759907.
This moves it into a separate transformation that always reassociates
the header mask regardless of the number of uses, which prevents some
fragile test changes in #173265.
We need to run it before both calls to simplifyRecipes in optimize. I
considered putting it in simplifyRecipes itself but simplifyRecipes is
also called after unrolling and when the loop region is dissolved which
causes vputils::findHeaderMask to assert.
There isn't really any benefit to reassociating masks that aren't the
header mask so the existing simplification was removed.
Add a new VPlan subdirectory as common place for tests checking VPlan
printing. It contains a lit.local.cfg that only runs the tests when
assertions are enabled.
This removes the need to add explicit REQUIRES: asserts to VPlan tests.
PR: https://github.com/llvm/llvm-project/pull/180611
The legacy cost model tries to scalarize loads that are used as
pointers. Skip if the load would need predicating when scalarized,
because that would incur very high costs, see useEmulatedMaskMemRefHack.
Fixes https://github.com/llvm/llvm-project/issues/180780.
The checks created by LAA only compute a pointer difference and do not
need to capture provenance. Use SCEVPtrToAddr instead of SCEVPtrToInt
for computations.
To avoid regressions while parts of SCEV are migrated to use PtrToAddr
this adds logic to rewrite all PtrToInt to PtrToAddr if possible in the
created expressions. This is needed to avoid regressions.
Similarly, if in the original IR we have a PtrToInt, SCEVExpander tries
to re-use it if possible when expanding PtrToAddr.
Depends on https://github.com/llvm/llvm-project/pull/178727.
Fixes https://github.com/llvm/llvm-project/issues/156978.
PR: https://github.com/llvm/llvm-project/pull/178861
This patch extends the support added in #158088 to loops where the
assignment is non-speculatable (e.g. a conditional load or divide).
For example, the following loop can now be vectorized:
```
int simple_csa_int_load(
int* a, int* b, int default_val, int N, int threshold)
{
int result = default_val;
for (int i = 0; i < N; ++i)
if (a[i] > threshold)
result = b[i];
return result;
}
```
It does this by extending the recurrence matching from only looking for
selects, to include phis where all operands are the header phi, except
for one which can be an arbitrary value outside the recurrence.
---
Reverts llvm/llvm-project#180275 (original PR: #178862)
Additional type legalization for `ISD::VECTOR_FIND_LAST_ACTIVE` was
added in #180290, which should resolve the backend crashes on x86.
There are some cases when PtrSCEV can be nullptr. Fall back to legacy
cost model, to not call isLoopInvariant with nullptr.
Fixes a crash after 0c4f8094939d2.
