[VPlan] Introduce isHeaderMask helper (NFCI).

Split off from https://github.com/llvm/llvm-project/pull/92555
and slightly generalized to more precisely check for a header mask.

Use it to replace ma

[VPlan] Introduce isHeaderMask helper (NFCI).

Split off from https://github.com/llvm/llvm-project/pull/92555
and slightly generalized to more precisely check for a header mask.

Use it to replace manual checks in collectHeaderMasks.

show more ...

[VPlan] Support extracting any lane of uniform value.

If the value we are extracting a lane from is uniform, only the first
lane will be set. Return lane 0 for any requested lane.

This fixes a cras

[VPlan] Support extracting any lane of uniform value.

If the value we are extracting a lane from is uniform, only the first
lane will be set. Return lane 0 for any requested lane.

This fixes a crash when trying to extract the last lane for a
first-order recurrence resume value.

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

show more ...

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

This reverts commit 90fd99c0795711e1cf762a02b29b0a702f86a264.
This reverts commit 43e6f46936e177e47de6627a74b047ba27561b4

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

This reverts commit 90fd99c0795711e1cf762a02b29b0a702f86a264.
This reverts commit 43e6f46936e177e47de6627a74b047ba27561b44.

Causes crashes, see comments on https://github.com/llvm/llvm-project/pull/92555.

show more ...

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

This reverts commit 46080abe9b136821eda2a1a27d8a13ceac349f8c.

Extra tests have been added in 52d29eb287.

Original message:
This

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

This reverts commit 46080abe9b136821eda2a1a27d8a13ceac349f8c.

Extra tests have been added in 52d29eb287.

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 ...

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

This reverts commit 00798354c553d48d27006a2b06a904bd6013e31b.

Causes crashes, see comments on https://github.com/llvm/llvm-project/

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

This reverts commit 00798354c553d48d27006a2b06a904bd6013e31b.

Causes crashes, see comments on https://github.com/llvm/llvm-project/pull/92555.

show more ...

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

This adds a new interface to compute the cost of recipes, VPBasicBlocks,
VPRegionBlocks and VPlan, initially falling back to the legacy cost

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

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] Add VPIRBasicBlock, use to model pre-preheader. (#93398)

This patch adds a new special type of VPBasicBlock that wraps an
existing IR basic block. Recipes of the block get added before the

[VPlan] Add VPIRBasicBlock, use to model pre-preheader. (#93398)

This patch adds a new special type of VPBasicBlock that wraps an
existing IR basic block. Recipes of the block get added before the
terminator of the wrapped IR basic block. Making it a subclass of
VPBasicBlock avoids duplicating various APIs to manage recipes in a
block, as well as makes sure the traversals filtering VPBasicBlocks
automatically apply as well.

Initially VPIRBasicBlock are only used for the pre-preheader (wrapping
the original preheader of the scalar loop).

As follow-up, this will be used to move more parts of the skeleton
inside VPlan, starting with the branch and condition in the middle
block.

Separated out of https://github.com/llvm/llvm-project/pull/92651

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

show more ...

[VPlan] Preserve DT (and SCEV) in VPlan-native path (#93287)

As a follow-up to b2f65e80, use the DTU to also update and preserve
the DT in the native path. This should also allow preserving SCEV in

[VPlan] Preserve DT (and SCEV) in VPlan-native path (#93287)

As a follow-up to b2f65e80, use the DTU to also update and preserve
the DT in the native path. This should also allow preserving SCEV in the
native path

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

show more ...

[VPlan] Use DomTreeUpdater to automatically update DT for vector loop. (#92525)

Use DTU to queue DominatorTree updates directly when connecting basic
blocks during VPlan execution.

This simplifi

[VPlan] Use DomTreeUpdater to automatically update DT for vector loop. (#92525)

Use DTU to queue DominatorTree updates directly when connecting basic
blocks during VPlan execution.

This simplifies DT updates and will also automatically allow updating
the DT for the VPlan-native path as additional benefit in a follow-up.

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

show more ...

[VPlan] Relax over-aggressive assertion in VPTransformState::get().

There are cases where a vector value has some users that demand the
the single scalar value only (NeedsScalar), while other users

[VPlan] Relax over-aggressive assertion in VPTransformState::get().

There are cases where a vector value has some users that demand the
the single scalar value only (NeedsScalar), while other users demand the
vector value (see attached test cases). In those cases, the NeedsScalar
users should only demand the first lane.

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

show more ...

[VPlan] Version VPValue names in VPSlotTracker. (#81411)

This patch restructures the way names for printing VPValues are handled.
It moves the logic to generate names for printing to VPSlotTracker

[VPlan] Version VPValue names in VPSlotTracker. (#81411)

This patch restructures the way names for printing VPValues are handled.
It moves the logic to generate names for printing to VPSlotTracker.

VPSlotTracker will now version names of the same underlying value if it
is used by multiple VPValues, by adding a .V suffix to the name.

This fixes cases where at the moment the same name is printed for
different VPValues.

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

show more ...

[VPlan] Dont assign slots to VPValues with an underlying value.

This makes sure the numbering for VPValues without underlying
values is consecutive.

[LV, VP]VP intrinsics support for the Loop Vectorizer + adding new tail-folding mode using EVL. (#76172)

This patch introduces generating VP intrinsics in the Loop Vectorizer.

Currently the Loop

[LV, VP]VP intrinsics support for the Loop Vectorizer + adding new tail-folding mode using EVL. (#76172)

This patch introduces generating VP intrinsics in the Loop Vectorizer.

Currently the Loop Vectorizer supports vector predication in a very
limited capacity via tail-folding and masked load/store/gather/scatter
intrinsics. However, this does not let architectures with active vector
length predication support take advantage of their capabilities.
Architectures with general masked predication support also can only take
advantage of predication on memory operations. By having a way for the
Loop Vectorizer to generate Vector Predication intrinsics, which (will)
provide a target-independent way to model predicated vector
instructions. These architectures can make better use of their
predication capabilities.

Our first approach (implemented in this patch) builds on top of the
existing tail-folding mechanism in the LV (just adds a new tail-folding
mode using EVL), but instead of generating masked intrinsics for memory
operations it generates VP intrinsics for loads/stores instructions. The
patch adds a new VPlanTransforms to replace the wide header predicate
compare with EVL and updates codegen for load/stores to use VP
store/load with EVL.

Other important part of this approach is how the Explicit Vector Length
is computed. (VP intrinsics define this vector length parameter as
Explicit Vector Length (EVL)). We use an experimental intrinsic
`get_vector_length`, that can be lowered to architecture specific
instruction(s) to compute EVL.

Also, added a new recipe to emit instructions for computing EVL. Using
VPlan in this way will eventually help build and compare VPlans
corresponding to different strategies and alternatives.

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

show more ...

[VPlan] Remove VPTransformState::addMetadata with ArrayRef arg (NFCI).

addMeadata is only over called with a single element, clean up the
variant that takes multiple values.

[VPlan] Rename getVPValueOrAddLiveIn -> getOrAddLiveIn (NFCI).

The helper now only deals with live-ins, clarify the name.

[VPlan] Explicitly handle scalar pointer inductions. (#83068)

Add a new PtrAdd opcode to VPInstruction that corresponds to
IRBuilder::CreatePtrAdd, which creates a GEP with source element type
i8.

[VPlan] Explicitly handle scalar pointer inductions. (#83068)

Add a new PtrAdd opcode to VPInstruction that corresponds to
IRBuilder::CreatePtrAdd, which creates a GEP with source element type
i8.

This is then used to model scalarizing VPWidenPointerInductionRecipe by
introducing scalar-steps to model the index increment followed by a
PtrAdd.

Note that PtrAdd needs to be able to generate code for only the first
lane or for all lanes. This may warrant introducing a separate recipe
for scalarizing that can be created without relying on the underlying
IR.

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

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

show more ...

[VPlan] Add initial pattern match implementation for VPInstruction. (#80563)

Add an initial version of a pattern match for VPValues and recipes,
starting with VPInstruction.

PR: https://github.c

[VPlan] Add initial pattern match implementation for VPInstruction. (#80563)

Add an initial version of a pattern match for VPValues and recipes,
starting with VPInstruction.

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

show more ...

[VPlan] Consistently use (Part, 0) for first lane scalar values (#80271)

At the moment, some VPInstructions create only a single scalar value,
but use VPTransformatState's 'vector' storage for this

[VPlan] Consistently use (Part, 0) for first lane scalar values (#80271)

At the moment, some VPInstructions create only a single scalar value,
but use VPTransformatState's 'vector' storage for this value. Those
values are effectively uniform-per-VF (or in some cases
uniform-across-VF-and-UF). Using the vector/per-part storage doesn't
interact well with other recipes, that more accurately using (Part,
Lane) to look up scalar values and prevents VPInstructions creating
scalars from interacting with other recipes working with scalars.

This PR tries to unify handling of scalars by using (Part, 0) for scalar
values where only the first lane is demanded. This allows using
VPInstructions with other recipes like VPScalarCastRecipe and is also
needed when using VPInstructions in more cases otuside the vector loop
region to generate scalars.

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

show more ...

[VPlan] Remove unused VPTransformState::VPValue2Value (NFCI).

Clean up unused member variable.

[VPlan] Support live-ins without underlying IR in type analysis. (#80723)

A VPlan contains multiple live-ins without underlying IR, like VFxUF or
VectorTripCount. Trying to infer the scalar type of

[VPlan] Support live-ins without underlying IR in type analysis. (#80723)

A VPlan contains multiple live-ins without underlying IR, like VFxUF or
VectorTripCount. Trying to infer the scalar type of those causes a crash
at the moment.

Update VPTypeAnalysis to take a VPlan in its constructor and assign
types to those live-ins up front. All those live-ins share the type of
the canonical IV.

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

show more ...

[VPlan] Merge main VPlan verifer with HCFG verifier.

Unify VPlan verifiers in verifyVPlanIsValid. This adds verification for
various properties on blocks to the verifier used for VPlans generated
by

[VPlan] Merge main VPlan verifer with HCFG verifier.

Unify VPlan verifiers in verifyVPlanIsValid. This adds verification for
various properties on blocks to the verifier used for VPlans generated
by the inner loop vectorizer. It also adds def-use checks for the
verifier used in the VPlan native path.

This drops the separate flag to enable HCFG verification. Instead, all
VPlans are verified once they have been created, if assertions are
enabled.

This also removes VPWidenPHIRecipe from VPHeaderPHIRecipe; it is used to
model any phi node in the native path.

show more ...

[VPlan] Mark vputils::onlyFirstPartUsed arg as const (NFC)

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

[VPlan] Mark vputils::onlyFirstLaneUsed arg as const (NFC)

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

[VPlan] Update ::onlyScalarsGenerated to take IsScalable bool (NFCI).

Instead of passing in a full VF, just pass IsScalable as bool.

[VPlan] use getVPValueOrAddLiveIn in VPlan::duplicate.

Instead of creating live-ins manually, use getOrAddLiveIn which
automatically takes care of adding them to VPLiveInsToFree. Also use it
to crea

[VPlan] use getVPValueOrAddLiveIn in VPlan::duplicate.

Instead of creating live-ins manually, use getOrAddLiveIn which
automatically takes care of adding them to VPLiveInsToFree. Also use it
to create the VPValue for the trip-count. This fixes a leak:
https://lab.llvm.org/buildbot/#/builders/168/builds/18308/steps/10/logs/stdio

show more ...