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 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
Simplify exactly as InstCombine does. A follow-up would include
simplifying add x, (sub 0, y) -> sub x, y.
Alive2 proof: https://alive2.llvm.org/ce/z/Af7QiD
This patch replace the remaining LogicalAnd to vp.merge in the second
pass to not break the `m_RemoveMask` pattern in the optimizeMaskToEVL.
Also skip cost model comparison when the plan contains `vp_merge` which
won't be calculated by the legacy model.
This can help to remove header mask for FindLast reduction (CSA) loops.
Original PR: https://github.com/llvm/llvm-project/pull/184068
Original built-bot failure:
https://lab.llvm.org/buildbot/#/builders/213/builds/2497
Fixes#186005
On RV32 with zve32x, i.e. no legal 64 bit types either scalar or vector,
@llvm.cttz.elts.i64 cannot be lowered and so returns an illegal cost for
scalable VFs. However VPInstruction::FirstActiveLane and
VPInstruction::LastActiveLane always use a hardcoded i64 type.
This causes a legacy/VPlan cost model mismatch in the live-out.ll test,
and in early-exit-live-out.ll prevents the scalable VF from being
chosen.
This PR teaches the two VPInstructions to use the target's index type,
i.e. the width of a pointer in the default address space, so it will
generate a 32 bit cttz.elts on RV32. This should be large enough to hold
the maximum number of elements in a vector, as if the vector was any
bigger it would imply it isn't accessible by memory.
I considered using the canonical IV type but I don't think that will
work since the canonical IV can be i64 on RV32, and it causes
regressions due to extra zexting on 64-bit targets with a 32-bit IV.
This patch replace the remaining LogicalAnd to vp.merge in the second
pass to not break the `m_RemoveMask` pattern in the optimizeMaskToEVL.
This can help to remove header mask for FindLast reduction (CSA) loops.
PR: https://github.com/llvm/llvm-project/pull/184068
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
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
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
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.
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.
Right now memory dependencies checks and speculation for unit-strideness
are performed somewhat simultaneously. This is wrong because:
* Ideally, if accesses aren't unit-strided in runtime we might want to
take a version with gather/strided load (longer term). Those two loops
should share legality checks and the dispatch based on stride should
only happen after the legality condition has been satisfied.
* Even if we don't generate multiple vector loops (current situation),
not vectorizing at all is worse than generating gather-only vector loop.
This PR adds a test for the latter as that could be a first step in
adding full support for the former.
This isn't target-specific, but gathers aren't supported in generic
target and result in very ugly scalarized code/CHECKs, hence put the
test under RISCV/.
Co-authored-by: Florian Hahn <flo@fhahn.com>
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>
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 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
We have an optimization in VPPredicator when creating blends where if
all the incoming values are the same, we just return that value.
This extends it to handle cases like "phi [%x, %x, poison, %x]" by
ignoring poison values.
This is split off from #176143 to prevent regressions when maintaining
SSA by adding PHIs with a poison incoming value.
When a recipe can be safely sunk and all of its users are outside the
vector loop region in the same dedicated exit block, the recipe does not
need to be executed on every iteration.
This patch extends the VPlan-based LICM (Loop Invariant Code Motion) to
also sink such recipes from the vector loop region into the exit block.
This reduces redundant computation and improves cost model accuracy.
TODO: Support nested loop sinking
TODO: Support sinking `VPReplicateRecipe` (requires `replicateByVF`
fixes)
TODO: Support recipes with multiple defined values (e.g., interleaved
loads)
TODO: Clone recipes without users to all exit blocks
TODO: Support PHI node users by checking incoming value blocks
TODO: Support sinking when users are in multiple blocks
TODO: Clone recipes when users are on multiple exit paths
Co-authored-by: Luke Lau <luke@igalia.com>
---------
Co-authored-by: Luke Lau <luke@igalia.com>
Co-authored-by: Luke Lau <luke_lau@icloud.com>
Fixes#176208. Scaled back version of #176515 that only affects the RISCV backend.
Only modifies the cost for cases when DIV is a legal operation.
Updates the cost for both Scalar and Vector types.
Used `TTI::TCC_Expensive` as suggested by
https://github.com/llvm/llvm-project/issues/176208#issuecomment-3760902537.
---------
Co-authored-by: Luke Lau <luke_lau@icloud.com>
Whilst reviewing PR #176754 I realised there seemed to be some odd cost
model issues for the tests in file
LoopVectorize/AArch64/fold-tail-low-trip-count.ll
where we seemed to be vectorising loops that aren't worth it. It turns
out the tests were not targeting AArch64 despite being in the AArch64
directory. I fixed the RUN line for the file and also added a new file
for RISCV so we get more test coverage.
When `extract-lane` only contains single vector operand. We can simplify
it to `extractelement`.
This patch makes `extract-lane` generate simple `extractelement` when it
only contains single vector operand to prevent unused IR generated.
This patch is mostly NFC, the unused IR should be removed in following
IR passes.
Remove the artificial PhiR operand of ComputeReductionResult, which was
only used to look up recurrence kind, in-loop and ordered properties.
Instead, encode them as VPIRFlags as suggested by @ayalz in
https://github.com/llvm/llvm-project/pull/170223.
This addresses a TODO to make codegen for ComputeReductionResult
independent of looking up information from other recipes.
This is NFC w.r.t. codegen, the printing has been improved to include
the reduction type, and whether it is in-loop/ordered.
PR: https://github.com/llvm/llvm-project/pull/174026
Fixes#175058
Similar to #175028, on RV64 we insert a zext in between most uses of EVL
so most of the VPlanVerifier EVL checks don't fire unless we're
compiling for RV32.
In this case, we're experiencing a crash because we can have a PtrAdd
that uses EVL. This fixes it by adding PtrAdd to the list of allowed
instructions
Fixes#175028
We have a VPlanVerifier assertion that a VPInstruction that uses EVL
only has one use. This used to hold until we implemented CSE, but now we
can run into the case where e.g. a multiply from an expanded
VPWidenPointerInductionRecipe gets cse'd, causing it to have multiple
uses:
EMIT ir<%0> = WIDEN-POINTER-INDUCTION ir<%.pre3>, ir<6>, vp<%5>
EMIT ir<%1> = WIDEN-POINTER-INDUCTION ir<%.pre>, ir<6>, vp<%5>
EMIT-SCALAR vp<%5> = EXPLICIT-VECTOR-LENGTH vp<%avl>
-->
EMIT-SCALAR vp<%10> = EXPLICIT-VECTOR-LENGTH vp<%avl>
EMIT vp<%11> = mul ir<6>, vp<%10>
EMIT vp<%ptr.ind> = ptradd vp<%pointer.phi>, vp<%11>
EMIT vp<%12> = mul ir<6>, vp<%10>
EMIT vp<%ptr.ind>.1 = ptradd vp<%pointer.phi>.1, vp<%12>
-->
EMIT-SCALAR vp<%5> = EXPLICIT-VECTOR-LENGTH vp<%avl>
EMIT vp<%6> = mul ir<6>, vp<%5>
EMIT vp<%ptr.ind> = ptradd vp<%pointer.phi>, vp<%6>
EMIT vp<%ptr.ind>.1 = ptradd vp<%pointer.phi>.1, vp<%6>
This removes the check, as I'm not sure it's that useful anymore now
that we have CSE. Coincidentally, this crash only happened on RV32
because RV64 requires zexting the EVL, which sidesteps a lot of the
checks to begin with.
This patch simplifies extract-lane(%lane_num, %X) to %X when %X is a
scalar value. Extracting from a scalar is redundant since there is only
one value to extract.
In VPlanPatternMatch.h I have changed the int_pred_ty code to look
through broadcasts in order to catch more cases, i.e. multiplying by a
splat of one, etc.
