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.
Extend intial unrolling of replicate regions
(https://github.com/llvm/llvm-project/pull/170212) to support live-outs,
if the VF is scalar.
This allows adding the logic needed to explicitly unroll, and replacing
VPPredPhiInsts with regular scalar VPPhi, without yet having to worry
about packing values into vector phis. This will be done in a follow-up
change, which means all replicate regions will be fully dissolved.
PR: https://github.com/llvm/llvm-project/pull/186252
The wrap flags from the IV bin-op are not guaranteed to apply to
truncated inductions, which are evaluated in narrower types.
Instead of dropping them late (in expandVPWidenIntOrFpInduction), do not
add them at the outset, the prevent invalid transforms based on
incorrect flags in the future.
PR: https://github.com/llvm/llvm-project/pull/188966
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
This patch removes the extra logical-and in `x && (x && y)` and `x && (y && x)` to `x && y`.
This helps to simplify mask calculation in the FindLast reduction and
exposes more opportunities to replace to EVL.
PR link: https://github.com/llvm/llvm-project/pull/185806
Previously, VPlanPredicator only reused the mask of the loop header when
a block post-dominates the header. This patch generalizes the
optimization to reuse the mask of immediate dominator when a block
post-dominates its immediate dominator.
This reduces more redundant mask computations, simplifies the generated
code, and improves EVL tail folding.
Based on #173265Fix#173260
When encountering a control-flow join, VPPredicator emit a disjunction
over the incoming edge masks as the entry mask of the joining block.
However, such a complex mask is not always necessary. If the block is
control-flow equivalent to the header block, we can directly use the
header block’s entry mask as the entry mask of that block.
This patch introduces a VPlan post-dominator tree to determine whether a
block is control-flow equivalent to the header block, and simplifies the
computation of block masks accordingly.
Based on #178724
Remove updateScalarResumePhis and create extracts for live-outs early in
addInitialSkeleton. Instead of extracting the from the header phi
recipes for the resume values (which is incorrect), extract the last
lane of the backedege value.
Then update optimizeInductionExitUsers to optimize both the scalar
resume values for IVs and IV exit values together.
This removes the need to pass state between transforms and addresses a
TODO.
PR: https://github.com/llvm/llvm-project/pull/174239
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.
Currently the logic for introducing a header mask and predicating the
vector loop region is done inside introduceMasksAndLinearize.
This splits the tail folding part out into an individual VPlan transform
so that VPlanPredicator.cpp doesn't need to worry about tail folding,
which seemed to be a temporary measure according to a comment in
VPlanTransforms.h.
To perform tail folding independently, this splits the "body" of the
vector loop region between the phis in the header and the branch + iv
increment in the latch:
Before:
```
+-------------------------------------------+
|%iv = ... |
|... |
|%iv.next = add %iv, vfxuf |
|branch-on-count %iv.next, vector-trip-count|
+-------------------------------------------+
```
After:
```
+-------------------------------------------+
|%iv = ... |
|%wide.iv = widen-canonical-iv ... |
|%header-mask = icmp ule %wide.iv, BTC |---+
|branch-on-cond %header-mask | |
+-------------------------------------------+ |
| |
v |
+-------------------------------------------+ |
|... | |
+-------------------------------------------+ |
| |
v |
+-------------------------------------------+ |
|%iv.next = add %iv, vfxuf |<--+
|branch-on-count %iv.next, vector-trip-count|
+-------------------------------------------+
```
Phis are then inserted in the latch for any value in the loop body that
have outside uses, with poison as their incoming value from the header
edge.
The motivation for this is to allow us to share the same "predicate all
successor blocks" type of predication we do for tail folding, but for
early-exit loops in #172454. This may also allow us to directly emit an
EVL based header mask, instead of having to match + transform the
existing header mask in addExplicitVectorLength.
This also allows us to eventually handle recurrences in the same
transform, avoiding the need to special case tail folding in
addReductionResultComputation.
Previously, the canonical IV increment may have overflowed to a non-zero
value due to vscale being a non power-of-two. So we used to emit a
runtime check for this.
If you didn't want the runtime check,
DataAndControlFlowWithoutRuntimeCheck skipped it and instead tweaked the
trip count so it wouldn't overflow.
However #144963 stopped the check from ever being emitted because vscale
is always a power-of-two on AArch64 and RISC-V, so it never overflowed
to a non-zero value. And in #183292 the code to emit the check was
removed. But we never restored the trip count back to normal when the
target's vscale was a power-of-two.
Now that vscale is always a power-of-two, this PR avoids adjusting it. A
follow up NFC can then remove DataAndControlFlowWithoutRuntimeCheck.
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.
Previously, we could miscompile when vectorizing conditional scalar
assignments with forced tail folding, as the backedge select could be
based on the header mask, not the assignment conditional.
This resulted in a number of failures in the LLVM test suite when
building with `-O3 -march=armv8-a+sve -mllvm
-prefer-predicate-over-epilogue=predicate-dont-vectorize`.
The patch reworks `handleFindLastReductions()` to correctly handle tail
folding.
Add an alternative to test VPlan in more isolation via a new
`vplan-test-transform` option, which builds VPlan0 for each loop in the
input IR and then can invoke a set of transforms on it.
In order to allow different recipe types to be created, a new
widen-from-metadata transform is added, which transforms VPInstructions
to different recipes, based on custom !vplan.widen metadata. Currently
this supports creating widen & replicate recipes, but can easily be
extended in the future.
Currently the handling is intentionally bare-bones, to be extended
gradually as needed.
PR: https://github.com/llvm/llvm-project/pull/178522
In order to be able to create selects for reduction phis through tail
folding in foldTailByMasking (#176143), make VPReductionPHIRecipe an
instance of VPIRFlags and plumb the FMFs from the original RdxDesc.
This allows us to remove more uses of the RecurrenceDescriptor in
addReductionResultComputation, which should help untie it from
LoopVectorizationLegality.
This is groundwork for #151300, which aims to support first-faulting
loads in non-tail-folded early-exit loops.
Per #175900, we need a variable-length stepping transform that can
shared between EVL and non-EVL loops.
The idea is to have an EVL-independent counter and transform for
tracking the cumulative number of processed elements.
This patch renames the existing counter (VPEVLBasedIVPHIRecipe) and
transform (canonicalizeEVLLoops) to be EVL-independent:
- Rename VPEVLBasedIVPHIRecipe to VPCurrentIterationRecipe to
reflect its general purpose of tracking processed element count.
- Rename canonicalizeEVLLoops to convertToVariableLengthStep.
This is NFC.
Building on top of the recent changes to introduce BranchOnTwoConds,
this patch adds support for vectorizing loops with multiple early exits,
all dominating a countable latch. The early exits must form a
dominance chain, so we can simply check which early exit has been taken
in dominance order.
Currently LoopVectorizationLegality ensures that all exits other than
the latch must be uncountable. handleUncountableEarlyExits now collects
those uncountable exits and processes each exit.
In the vector region, we compute if any exit has been taken, by taking
the OR of all early exit conditions (EarlyExitConds) and checking if
there's
any active lane.
If the early exit is taken, we exit the loop and compute which early
exit
has been taken. The first taken early exit is the one where its exit
condition is true in the first active lane of EarlyExitConds.
We create a chain of dispatch blocks outside the loop to check this for
the early exit blocks ordered by dominance.
Depends on https://github.com/llvm/llvm-project/pull/174016.
PR: https://github.com/llvm/llvm-project/pull/174864
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
Switch tests from using `-debug[-only=LoopVectorize]` to
`-vplan-print-after` as that provides better control at what step in the
pipeline we want to check the VPlan (I'm using `optimize$` for now to
preserve previous state).
Then, update `-vplan-print-after*` to print what function the loop
belongs to. That enables us to simplify VPlan UTC support as the output
of the updated tests contains the VPlan dump only - no special
filtering/extraction is necessary anymore.
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
