[VPlan] Add getSCEVExprForVPValue util, use to get trip count SCEV (NFC) (#94464)

Add a new getSCEVExprForVPValue utility which can be used to get a SCEV
expression for a VPValue. The initial imple

[VPlan] Add getSCEVExprForVPValue util, use to get trip count SCEV (NFC) (#94464)

Add a new getSCEVExprForVPValue utility which can be used to get a SCEV
expression for a VPValue. The initial implementation only returns SCEVs
for live-in IR values (by constructing a SCEV based on the live-in IR
value) and VPExpandSCEVRecipe. This is enough to serve its first use,
getting a SCEV for a VPlan's trip count, but will be extended in the
future.

It also removes createTripCountSCEV, as the new helper can be used to
retrieve the SCEV from the VPlan.

PR: https://github.com/llvm/llvm-project/pull/94464

show more ...

[NFC][LoopVectorize] Rename variable in replaceVPBBWithIRVPBB (#108543)

I've renamed the variable in replaceVPBBWithIRVPBB from IRMiddleVPBB ->
IRVPBB, since the function is used for more than just

[NFC][LoopVectorize] Rename variable in replaceVPBBWithIRVPBB (#108543)

I've renamed the variable in replaceVPBBWithIRVPBB from IRMiddleVPBB ->
IRVPBB, since the function is used for more than just replacing the
middle VP block.

show more ...

[NFC][LoopVectorize] Dont pass LLVMContext to VPTypeAnalysis constructor (#108540)

We already pass a Type object into the VPTypeAnalysis constructor, which
can be used to obtain the context. While

[NFC][LoopVectorize] Dont pass LLVMContext to VPTypeAnalysis constructor (#108540)

We already pass a Type object into the VPTypeAnalysis constructor, which
can be used to obtain the context. While in the same area it also made
sense to avoid passing the context into the VPTransformState and
VPCostContext constructors.

show more ...

[VPlan] Handle ForceTargetInstructionCost in during precomputeCosts.

Make sure ForceTargetInstruction is respected in precomputeCosts.

[VPlan] Clarify comment for replaceVPBBWithIRVPBB and add assert (NFCI).

Follow-up to suggestion during
https://github.com/llvm/llvm-project/pull/100735.

More specifically
https://github.com/llvm/l

[VPlan] Clarify comment for replaceVPBBWithIRVPBB and add assert (NFCI).

Follow-up to suggestion during
https://github.com/llvm/llvm-project/pull/100735.

More specifically
https://github.com/llvm/llvm-project/pull/100735/files/9a40ed0919bad7fb79123317267d3eb36ff2c582#diff-6d0b73adfa9f8465923d2225ab6674ddcdeab71666f7a73dfaec7fa1246b3a1f

show more ...

[VPlan] Add VPIRInstruction, use for exit block live-outs. (#100735)

Add a new VPIRInstruction recipe to wrap existing IR instructions not to
be modified during execution, execept for PHIs. For PHI

[VPlan] Add VPIRInstruction, use for exit block live-outs. (#100735)

Add a new VPIRInstruction recipe to wrap existing IR instructions not to
be modified during execution, execept for PHIs. For PHIs, a single
VPValue
operand is allowed, and it is used to add a new incoming value for the
single predecessor VPBB. Expect PHIs, VPIRInstructions cannot have any
operands.

Depends on https://github.com/llvm/llvm-project/pull/100658.

PR: https://github.com/llvm/llvm-project/pull/100735

show more ...

[NFC][LoopVectorize] Avoid passing ScalarEvolution to VPlanTransforms::optimize (#108380)

Whilst trying to write some VPlan unit tests I realised
that we don't need to pass a ScalarEvolution object

[NFC][LoopVectorize] Avoid passing ScalarEvolution to VPlanTransforms::optimize (#108380)

Whilst trying to write some VPlan unit tests I realised
that we don't need to pass a ScalarEvolution object into
VPlanTransforms::optimize because the only thing we
actually need is a LLVMContext.

show more ...

[VPlan] Add VPValue for VF, use it for VPWidenIntOrFpInductionRecipe. (#95305)

Similar to VFxUF, also add a VF VPValue to VPlan and use it to get the
runtime VF in VPWidenIntOrFpInductionRecipe. Co

[VPlan] Add VPValue for VF, use it for VPWidenIntOrFpInductionRecipe. (#95305)

Similar to VFxUF, also add a VF VPValue to VPlan and use it to get the
runtime VF in VPWidenIntOrFpInductionRecipe. Code for VF is only
generated if there are users of VF, to avoid unnecessary test changes.

PR: https://github.com/llvm/llvm-project/pull/95305

show more ...

[VPlan] Assert that VFxUF is always used.

Add assertion to ensure invariant discussed in
https://github.com/llvm/llvm-project/pull/95305.

[VPlan] Move properlyDominates to VPDominatorTree (NFCI).

This allows for easier re-use in additional places in the future. Also
move code to VPlanAnalysis.cpp

VPlan: factor out VPlanUtils into its own file (NFC) (#105857)

[VPlan] Only use selectVectorizationFactor for cross-check (NFCI). (#103033)

Use getBestVF to select VF up-front and only use
selectVectorizationFactor to get the VF legacy VF to check the
vectori

[VPlan] Only use selectVectorizationFactor for cross-check (NFCI). (#103033)

Use getBestVF to select VF up-front and only use
selectVectorizationFactor to get the VF legacy VF to check the
vectorization decision matches the VPlan-based cost model.

PR: https://github.com/llvm/llvm-project/pull/103033

show more ...

[VPlan] Rename getBestPlanFor -> getPlanFor (NFC).

As suggested in https://github.com/llvm/llvm-project/pull/103033, more
accurately rename to getPlanFor , as it simplify returns the VPlan for
VF, r

[VPlan] Rename getBestPlanFor -> getPlanFor (NFC).

As suggested in https://github.com/llvm/llvm-project/pull/103033, more
accurately rename to getPlanFor , as it simplify returns the VPlan for
VF, relying on the fact that there is a single VPlan for each VF at the
moment.

show more ...

[VPlan] Move some LoopVectorizationPlanner helpers to VPlan.cpp (NFC).

Members not requiring access to LoopVectorizationLegality or
LoopVectorizationCostModel can safely be moved out of the very lar

[VPlan] Move some LoopVectorizationPlanner helpers to VPlan.cpp (NFC).

Members not requiring access to LoopVectorizationLegality or
LoopVectorizationCostModel can safely be moved out of the very large
LoopVectorization.cpp and are more accurately placed in VPlan.cpp

show more ...

[VPlan][NFC] Make VPValue pointer const. (#101334)

[VPlan] Relax assertion retrieving a scalar from VPTransformState::get.

The current assertion VPTransformState::get when retrieving a single
scalar only does not account for cases where a def has mu

[VPlan] Relax assertion retrieving a scalar from VPTransformState::get.

The current assertion VPTransformState::get when retrieving a single
scalar only does not account for cases where a def has multiple users,
some demanding all scalar lanes, some demanding only a single scalar.

For an example, see the modified test case. Relax the assertion by also
allowing requesting scalar lanes only when the Def doesn't have only its
first lane used.

Fixes https://github.com/llvm/llvm-project/issues/88849.

show more ...

Recommit "[VPlan] First step towards VPlan cost modeling. (#92555)"

This reverts commit 6f538f6a2d3224efda985e9eb09012fa4275ea92.

A number of crashes have been fixed by separate fixes, including
tt

Recommit "[VPlan] First step towards VPlan cost modeling. (#92555)"

This reverts commit 6f538f6a2d3224efda985e9eb09012fa4275ea92.

A number of crashes have been fixed by separate fixes, including
ttps://github.com/llvm/llvm-project/pull/96622. This version of the
PR also pre-computes the costs for branches (except the latch) instead
of computing their costs as part of costing of replicate regions, as
there may not be a direct correspondence between original branches and
number of replicate regions.

Original message:
This adds a new interface to compute the cost of recipes, VPBasicBlocks,
VPRegionBlocks and VPlan, initially falling back to the legacy cost model
for all recipes. Follow-up patches will gradually migrate recipes to
compute their own costs step-by-step.

It also adds getBestPlan function to LVP which computes the cost of all
VPlans and picks the most profitable one together with the most
profitable VF.

The VPlan selected by the VPlan cost model is executed and there is an
assert to catch cases where the VPlan cost model and the legacy cost
model disagree. Even though I checked a number of different build
configurations on AArch64 and X86, there may be some differences
that have been missed.

Additional discussions and context can be found in @arcbbb's
https://github.com/llvm/llvm-project/pull/67647 and
https://github.com/llvm/llvm-project/pull/67934 which is an earlier
version of the current PR.

PR: https://github.com/llvm/llvm-project/pull/92555

show more ...

[VPlan] Create vector header and latch VPBBs in createInitialVPlan (NFC)

The empty header and latch blocks can be created together with the
vector loop region.

This is in preparation for splitting

[VPlan] Create vector header and latch VPBBs in createInitialVPlan (NFC)

The empty header and latch blocks can be created together with the
vector loop region.

This is in preparation for splitting up the very large
tryToBuildVPlanWithVPRecipes into several distinct functions, as
suggested multiple times, including in
https://github.com/llvm/llvm-project/pull/94760

show more ...

[VPlan] Model branch cond to enter scalar epilogue in VPlan. (#92651)

This patch moves branch condition creation to enter the scalar epilogue
loop to VPlan. Modeling the branch in the middle block

[VPlan] Model branch cond to enter scalar epilogue in VPlan. (#92651)

This patch moves branch condition creation to enter the scalar epilogue
loop to VPlan. Modeling the branch in the middle block also requires
modeling the successor blocks. This is done using the recently
introduced VPIRBasicBlock.

Note that the middle.block is still created as part of the skeleton and
then patched in during VPlan execution. Unfortunately the skeleton needs
to create the middle.block early on, as it is also used for induction
resume value creation and is also needed to properly update the
dominator tree during skeleton creation.

After this patch lands, I plan to move induction resume value and phi
node creation in the scalar preheader to VPlan. Once that is done, we
should be able to create the middle.block in VPlan directly.

This is a re-worked version based on the earlier
https://reviews.llvm.org/D150398 and the main change is the use of
VPIRBasicBlock.

Depends on https://github.com/llvm/llvm-project/pull/92525

PR: https://github.com/llvm/llvm-project/pull/92651

show more ...

[VPlan] Rewrite cloneSESE to use 2 depth-first passes (NFCI).

Rewrite cloneSESE to perform 2 depth-first passes with the first one
cloning blocks and the second one updating the predecessors and
suc

[VPlan] Rewrite cloneSESE to use 2 depth-first passes (NFCI).

Rewrite cloneSESE to perform 2 depth-first passes with the first one
cloning blocks and the second one updating the predecessors and
successors.

This is needed to preserve the correct predecessor/successor ordering
with https://github.com/llvm/llvm-project/pull/92651 and has been split
off as suggested.

show more ...

[VPlan] Rename Preheader -> Entry in createInitialVPlan (NFCI).

Split off from https://github.com/llvm/llvm-project/pull/92651 as
suggested.

Revert "Recommit "[VPlan] First step towards VPlan cost modeling. (#92555)""

This reverts commit 242cc200ccb24e22eaf54aed7b0b0c84cfc54c0b and
eea150c84053035163f307b46549a2997a343ce9, as it is causi

Revert "Recommit "[VPlan] First step towards VPlan cost modeling. (#92555)""

This reverts commit 242cc200ccb24e22eaf54aed7b0b0c84cfc54c0b and
eea150c84053035163f307b46549a2997a343ce9, as it is causing a build bot
failure and there have been a number of crashes reported at
https://github.com/llvm/llvm-project/pull/92555

show more ...

[VPlan] Include IV phi and backedge cost in VPlan cost computation.

In WebAssembly, costs != 0 are assigned to be backedge and induction
phis, so make sure we include those costs in the VPlan-based

[VPlan] Include IV phi and backedge cost in VPlan cost computation.

In WebAssembly, costs != 0 are assigned to be backedge and induction
phis, so make sure we include those costs in the VPlan-based cost model.

This fixes a downstream crash with WebAssembly after 242cc200ccb
(https://github.com/llvm/llvm-project/pull/92555)

show more ...

Recommit "[VPlan] First step towards VPlan cost modeling. (#92555)"

This reverts commit 6f538f6a2d3224efda985e9eb09012fa4275ea92.

Extra tests for crashes discovered when building Chromium have been

Recommit "[VPlan] First step towards VPlan cost modeling. (#92555)"

This reverts commit 6f538f6a2d3224efda985e9eb09012fa4275ea92.

Extra tests for crashes discovered when building Chromium have been
added in fb86cb7ec157689e, 3be7312f81ad2.

Original message:
This adds a new interface to compute the cost of recipes, VPBasicBlocks,
VPRegionBlocks and VPlan, initially falling back to the legacy cost model
for all recipes. Follow-up patches will gradually migrate recipes to
compute their own costs step-by-step.

It also adds getBestPlan function to LVP which computes the cost of all
VPlans and picks the most profitable one together with the most
profitable VF.

The VPlan selected by the VPlan cost model is executed and there is an
assert to catch cases where the VPlan cost model and the legacy cost
model disagree. Even though I checked a number of different build
configurations on AArch64 and X86, there may be some differences
that have been missed.

Additional discussions and context can be found in @arcbbb's
https://github.com/llvm/llvm-project/pull/67647 and
https://github.com/llvm/llvm-project/pull/67934 which is an earlier
version of the current PR.

PR: https://github.com/llvm/llvm-project/pull/92555

show more ...

[VPlan] Model middle block via VPIRBasicBlock. (#95816)

Use VPIRBasicBlock to wrap the middle block and implement patching up
branches in predecessors in VPIRBasicBlock::execute. The IR middle bloc

[VPlan] Model middle block via VPIRBasicBlock. (#95816)

Use VPIRBasicBlock to wrap the middle block and implement patching up
branches in predecessors in VPIRBasicBlock::execute. The IR middle block
is only created after skeleton creation. Initially a regular
VPBasicBlock is created, which will later be replaced by a
VPIRBasicBlock once the middle IR basic block has been created.

Note that this slightly changes the order of instructions created in the
middle block; code generated by recipe execution in the middle block
will now be inserted before the terminator (and in between the compare
to used by the terminator). The original order will be restored in
https://github.com/llvm/llvm-project/pull/92651.


PR: https://github.com/llvm/llvm-project/pull/95816

show more ...