[LoopVectorize] Support reductions that store intermediary result

Adds ability to vectorize loops containing a store to a loop-invariant
address as part of a reduction that isn't converted to SSA fo

[LoopVectorize] Support reductions that store intermediary result

Adds ability to vectorize loops containing a store to a loop-invariant
address as part of a reduction that isn't converted to SSA form due to
lack of aliasing info. Runtime checks are generated to ensure the store
does not alias any other accesses in the loop.

Ordered fadd reductions are not yet supported.

Differential Revision: https://reviews.llvm.org/D110235

show more ...

[VPlan] Simplify & adjust code as suggested in D123005.

Improve code as suggested in D123005. Applied separately, because the
comments where made a diff that has not been rebased to current main.

[VPlan] Initial modeling of middle block in VPlan.

This patch extends the scope of VPlan to also include the exit (aka
middle) block.

For now, the exit block remains empty, but handling of exit val

[VPlan] Initial modeling of middle block in VPlan.

This patch extends the scope of VPlan to also include the exit (aka
middle) block.

For now, the exit block remains empty, but handling of exit values will
subsequently be moved to VPlan, by adding recipes to model exit values
in the exit block.

As a first step, this will allow fixing #51366.

Reviewed By: Ayal

Differential Revision: https://reviews.llvm.org/D123457

show more ...

[VPlan] Expand induction step in VPlan pre-header.

This patch moves SCEV expansion of steps used by
VPWidenIntOrFpInductionRecipes to the pre-header using
VPExpandSCEVRecipe. This ensures that those

[VPlan] Expand induction step in VPlan pre-header.

This patch moves SCEV expansion of steps used by
VPWidenIntOrFpInductionRecipes to the pre-header using
VPExpandSCEVRecipe. This ensures that those steps are expanded while the
CFG is in a valid state. Previously, SCEV expansion may happen during
vector body code-generation, during which the CFG may be invalid,
causing issues with SCEV expansion.

Depends on D122095.

Reviewed By: Ayal

Differential Revision: https://reviews.llvm.org/D122096

show more ...

[VPlan] Turn external defs in Value -> VPValue mapping.

This addresses an existing TODO by keeping a mapping of external IR
Value * definitions wrapped in VPValues for use in a VPlan.

Reviewed By:

[VPlan] Turn external defs in Value -> VPValue mapping.

This addresses an existing TODO by keeping a mapping of external IR
Value * definitions wrapped in VPValues for use in a VPlan.

Reviewed By: Ayal

Differential Revision: https://reviews.llvm.org/D123700

show more ...

[VPlan] Place VPExpandSCEVRecipe in pre-header.

After D121624 models the pre-header in VPlan, VPExpandSCEVRecipes can be
placed there. This ensures SCEV expansion happens before modifying the
CFG du

[VPlan] Place VPExpandSCEVRecipe in pre-header.

After D121624 models the pre-header in VPlan, VPExpandSCEVRecipes can be
placed there. This ensures SCEV expansion happens before modifying the
CFG during VPlan execution, when CFG is incomplete.

Depends on D121624.

Reviewed By: Ayal

Differential Revision: https://reviews.llvm.org/D122095

show more ...

[VPlan] Model pre-header explicitly.

This patch extends the scope of VPlan to also model the pre-header.
The pre-header can be used to place recipes that should be code-gen'd
outside the loop, like

[VPlan] Model pre-header explicitly.

This patch extends the scope of VPlan to also model the pre-header.
The pre-header can be used to place recipes that should be code-gen'd
outside the loop, like SCEV expansion.

Depends on D121623.

Reviewed By: Ayal

Differential Revision: https://reviews.llvm.org/D121624

show more ...

[VPlan] Preserve debug location when creating branch.

Update createEmptyBasicBlock to preserve the debug location of the
previous terminator.

[LV] Add vector.body block to parent loop during skeleton creation.

When creating induction resume values, SCEV queries may rely on
LoopInfo. Make sure vector.body gets added to the loop of the pre-

[LV] Add vector.body block to parent loop during skeleton creation.

When creating induction resume values, SCEV queries may rely on
LoopInfo. Make sure vector.body gets added to the loop of the pre-header
during skeleton construction.

%vector.body will be moved to the vector preheader during VPlan
execution.

Fixes #54745.

show more ...

[VPlan] Update VPInterleavedAccessInfo to use getVectorLoopRegion.

Update VPInterleavedAccessInfo to use the generic getVectorLoopRegion
helper instead of relying on the entry block being the top-m

[VPlan] Update VPInterleavedAccessInfo to use getVectorLoopRegion.

Update VPInterleavedAccessInfo to use the generic getVectorLoopRegion
helper instead of relying on the entry block being the top-most vector
loop region.

show more ...

[VPlan] Remember previous loop and reset vector loop.

At the moment this is NFC, but will be needed once nested loops are also
modeled as regions. Preparation for D123005.

Recommit "[LV] Remove unneeded createHeaderBranch.(NFCI)"

This reverts commit 14e3650f01d158f7e4117c353927a07ceebdd504.

The issue causing the revert were fixed independently in
a08c90a4023f and 14e

Recommit "[LV] Remove unneeded createHeaderBranch.(NFCI)"

This reverts commit 14e3650f01d158f7e4117c353927a07ceebdd504.

The issue causing the revert were fixed independently in
a08c90a4023f and 14e5f9785c9c.

show more ...

Revert "Recommit "[LV] Remove unneeded createHeaderBranch.(NFCI)""

This reverts commit 8378a71b6cce611e01f42690713fd7b561ff3f30.

It looks like this patch uncovered another issue, e.g. see
https://l

Revert "Recommit "[LV] Remove unneeded createHeaderBranch.(NFCI)""

This reverts commit 8378a71b6cce611e01f42690713fd7b561ff3f30.

It looks like this patch uncovered another issue, e.g. see
https://lab.llvm.org/buildbot/#/builders/168/builds/5518

show more ...

Recommit "[LV] Remove unneeded createHeaderBranch.(NFCI)"

This reverts the revert commit 2760cdc9c6.

This version pulls in the code to create the vector loop object in VPlan
from D121624.

This is

Recommit "[LV] Remove unneeded createHeaderBranch.(NFCI)"

This reverts the revert commit 2760cdc9c6.

This version pulls in the code to create the vector loop object in VPlan
from D121624.

This is needed because otherwise existing LoopInfo verification will
fail, as a loop block doesn't have in-loop successors now that we
do not replace the branch.

Now that we do not add new loops during skeleton construction, there's
also no need to verify LI there.

show more ...

Revert "[LV] Remove unneeded createHeaderBranch.(NFCI)"

This reverts commit 32bc83d11e19b8a8c15df81b32fde1f9f8c6156b.

This is causing bots with expensive-checks to fail. Revert while I
investigate.

[LV] Remove unneeded createHeaderBranch.(NFCI)

The only remaining use was to get the exit block of the loop. Instead of
relying on the loop, use the successor of VectorHeaderBB
(LoopMiddleBlock) dir

[LV] Remove unneeded createHeaderBranch.(NFCI)

The only remaining use was to get the exit block of the loop. Instead of
relying on the loop, use the successor of VectorHeaderBB
(LoopMiddleBlock) directly to set VPTransformState::CFG::ExitB

Depends on D121621.

Reviewed By: Ayal

Differential Revision: https://reviews.llvm.org/D121623

show more ...

[VPlan] Remove unneeded Loop variable (NFC).

Suggested in D121623. The remaining uses of L can be replaced, reducing
the need for the variable.

[VPlan] Track current vector loop in VPTransformState (NFC).

Instead of looking up the vector loop using the header, keep track of
the current vector loop in VPTransformState. This removes the
requi

[VPlan] Track current vector loop in VPTransformState (NFC).

Instead of looking up the vector loop using the header, keep track of
the current vector loop in VPTransformState. This removes the
requirement for the vector header block being part of the loop up front.

A follow-up patch will move the code to generate the Loop object for the
vector loop to VPRegionBlock.

Depends on D121619.

Reviewed By: Ayal

Differential Revision: https://reviews.llvm.org/D121621

show more ...

[LV] Do not create separate latch block in VPlan::execute.

Now that all dependencies on creating the latch block up-front have been
removed, there is no need to create it early.

Depends on D121618.

[LV] Do not create separate latch block in VPlan::execute.

Now that all dependencies on creating the latch block up-front have been
removed, there is no need to create it early.

Depends on D121618.

Reviewed By: Ayal

Differential Revision: https://reviews.llvm.org/D121619

show more ...

[LV] Pass LoopHeaderBB directly to updateDominatorTree. (NFC)

At the call site, we already know what the vector header block is. Pass
it directly.

[LV] Move code to place pointer induction increment to VPlan post-processing.

This patch moves the code to set the correct incoming block for the
backedge value to VPlan::execute.

When generating t

[LV] Move code to place pointer induction increment to VPlan post-processing.

This patch moves the code to set the correct incoming block for the
backedge value to VPlan::execute.

When generating the phi node, the backedge value is temporarily added
using the pre-header as incoming block. The invalid phi node will be
fixed up during VPlan::execute after main VPlan code generation.
At the same time, the backedge value is also moved to the latch.

This change removes the requirement to create the latch block up-front
for VPWidenInductionPHIRecipe::execute, which in turn will enable
modeling the pre-header in VPlan.

Depends on D121617.

Reviewed By: Ayal

Differential Revision: https://reviews.llvm.org/D121618

show more ...

[LV] Move code to place induction increment to VPlan post-processing.

This patch moves the code to set the correct incoming block for the
backedge value to VPlan::execute.

When generating the phi n

[LV] Move code to place induction increment to VPlan post-processing.

This patch moves the code to set the correct incoming block for the
backedge value to VPlan::execute.

When generating the phi node, the backedge value is temporarily added
using the pre-header as incoming block. The invalid phi node will be
fixed up during VPlan::execute after main VPlan code generation.
At the same time, the backedge value is also moved to the latch.

This change removes the requirement to create the latch block up-front
for VPWidenIntOrFpInductionRecipe::execute, which in turn will enable
modeling the pre-header in VPlan.

As an alternative, the increment could be modeled as separate recipe,
but that would require more work and a bit of redundant code, as we need
to create the step-vector during VPWidenIntOrFpInductionRecipe::execute
anyways, to create the values for different parts.

Reviewed By: Ayal

Differential Revision: https://reviews.llvm.org/D121617

show more ...

[LV] Use getVectorLoopRegion to retrieve header. (NFC)

Update all places that currently assume the entry block to the plan is
also the vector loop header to use getVectorLoopRegion instead.

getVect

[LV] Use getVectorLoopRegion to retrieve header. (NFC)

Update all places that currently assume the entry block to the plan is
also the vector loop header to use getVectorLoopRegion instead.

getVectorLoopRegion will keep doing the right thing when the pre-header
is modeled explicitly (and becomes the new entry block in the plan).

show more ...

[VPlan] Add VPWidenPointerInductionRecipe.

This patch moves pointer induction handling from VPWidenPHIRecipe to its
own recipe. In the process, it adds all information required to generate
code for

[VPlan] Add VPWidenPointerInductionRecipe.

This patch moves pointer induction handling from VPWidenPHIRecipe to its
own recipe. In the process, it adds all information required to generate
code for pointer inductions without relying on Legal to access the list
of induction phis.

Alternatively VPWidenPHIRecipe could also take an optional pointer to InductionDescriptor.

Reviewed By: Ayal

Differential Revision: https://reviews.llvm.org/D121615

show more ...

Cleanup includes: Transforms/Instrumentation & Transforms/Vectorize

Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-cleanup
Differential Revision: https://reviews.llvm.or

Cleanup includes: Transforms/Instrumentation & Transforms/Vectorize

Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-cleanup
Differential Revision: https://reviews.llvm.org/D122181

show more ...