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] Clarify setting Lane in fixPhi (NFCI).

Split off from https://github.com/llvm/llvm-project/pull/94760, clarify
as suggested.

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

[IR] Add getDataLayout() helpers to BasicBlock and Instruction (#96902)

This is a helper to avoid writing `getModule()->getDataLayout()`. I
regularly try to use this method only to remember it does

[IR] Add getDataLayout() helpers to BasicBlock and Instruction (#96902)

This is a helper to avoid writing `getModule()->getDataLayout()`. I
regularly try to use this method only to remember it doesn't exist...

`getModule()->getDataLayout()` is also a common (the most common?)
reason why code has to include the Module.h header.

show more ...

[VPlan] Restructure code for BranchOnCond codegen. (NFCI)

Reoder code to exit early if the BranchOnCond isn't in an exiting block.
This delays retrieving the parent region, which may not be present.

[VPlan] Restructure code for BranchOnCond codegen. (NFCI)

Reoder code to exit early if the BranchOnCond isn't in an exiting block.
This delays retrieving the parent region, which may not be present.

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

show more ...

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

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] 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] Handle more cases in VPInstruction::onlyFirstPartUsed.

Handle binary ops and a few other instructions in onlyFirstPartUsed;
they only use the first part if they themselves only have their fi

[VPlan] Handle more cases in VPInstruction::onlyFirstPartUsed.

Handle binary ops and a few other instructions in onlyFirstPartUsed;
they only use the first part if they themselves only have their first
part used.

show more ...

[VPlan] Mark FirstOrderRecurrenceSplice as not having side-effects.

Now that FOR exit and resume value creation is explicitly modeled in
VPlan (05e1b5340b0caf1, 07b330132c0b) it doesn't depend on th

[VPlan] Mark FirstOrderRecurrenceSplice as not having side-effects.

Now that FOR exit and resume value creation is explicitly modeled in
VPlan (05e1b5340b0caf1, 07b330132c0b) it doesn't depend on the first
order recurrence splice being preserved and it can now be marked as not
having side-effects. This allows removal of first-order-recurrence-splce
if the FOR is only used in the exit or as scalar ph resume value.

show more ...

[VPlan] Check if only first part is used for all per-part VPInsts.

Apply the onlyFirstPartUsed logic generally to all per-part
VPInstructions. Note that the test changes remove the second part
of an

[VPlan] Check if only first part is used for all per-part VPInsts.

Apply the onlyFirstPartUsed logic generally to all per-part
VPInstructions. Note that the test changes remove the second part
of an unsued first-order recurrence splice.

show more ...

[VPlan] Model FOR extract of exit value in VPlan. (#93395)

This patch introduces a new ExtractFromEnd VPInstruction opcode to
extract the value of a FOR for users outside the loop (i.e. in the
sca

[VPlan] Model FOR extract of exit value in VPlan. (#93395)

This patch introduces a new ExtractFromEnd VPInstruction opcode to
extract the value of a FOR for users outside the loop (i.e. in the
scalar loop's exits). This moves the first part of fixing first order
recurrences to VPlan, and removes some additional code to patch up
live-outs, which is now handled automatically.

The majority of test changes is due to changes in the order of which the
extracts are generated now. As we are now using VPTransformState to
generate the extracts, we may be able to re-use existing extracts in the
loop body in some cases. For scalable vectors, in some cases we now have
to compute the runtime VF twice, as each extract is now independent, but
those should be trivial to clean up for later passes (and in line with
other places in the code that also liberally re-compute runtime VFs).

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

show more ...

[VPlan] Update VPBlendRecipe codegen for for first-lane only.

Update VPBlendRecipe::execute to support generating code for first-lane
only. This fixes a crash in the newly added test
@test_not_first

[VPlan] Update VPBlendRecipe codegen for for first-lane only.

Update VPBlendRecipe::execute to support generating code for first-lane
only. This fixes a crash in the newly added test
@test_not_first_lane_only_wide_compare_incoming_order_swapped.

show more ...

[VPlan] Add non-poison propagating LogicalAnd VPInstruction opcode. (#91897)

Add a new opcode to mode non-poison propagating logical AND operations
used when generating edge masks. This follows the

[VPlan] Add non-poison propagating LogicalAnd VPInstruction opcode. (#91897)

Add a new opcode to mode non-poison propagating logical AND operations
used when generating edge masks. This follows the similar decision to
model Not as dedicated opcode as well, to improve clarity.

This also helps to simplify the matchers for
https://github.com/llvm/llvm-project/pull/89386.


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

show more ...

Reapply "[LV] Improve AnyOf reduction codegen. (#78304)"

This reverts the revert commit c6e01627acf859.

This patch includes a fix for any-of reductions and epilogue
vectorization. Extra test covera

Reapply "[LV] Improve AnyOf reduction codegen. (#78304)"

This reverts the revert commit c6e01627acf859.

This patch includes a fix for any-of reductions and epilogue
vectorization. Extra test coverage for the issue that caused the revert
has been added in bce3bfced5fe0b019 and an assertion has been added in
c7209cbb8be7a3c65813.

--------------------------------
Original commit message:

Update AnyOf reduction code generation to only keep track of the AnyOf
property in a boolean vector in the loop, only selecting either the new
or start value in the middle block.

The patch incorporates feedback from https://reviews.llvm.org/D153697.

This fixes the #62565, as now there aren't multiple uses of the
start/new values.

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

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

show more ...

[VPlan] Check type directly in ::isCanonical (NFC).

Directly check the type of the wide induction matches the canonical
induction.

Refactor suggested in and in preparation for
https://github.com/ll

[VPlan] Check type directly in ::isCanonical (NFC).

Directly check the type of the wide induction matches the canonical
induction.

Refactor suggested in and in preparation for
https://github.com/llvm/llvm-project/pull/89603

show more ...

[VPlan] Make CallInst optional for VPWidenCallRecipe (NFCI).

Replace relying on the underling CallInst for looking up the called
function and its types by instead adding the called function as opera

[VPlan] Make CallInst optional for VPWidenCallRecipe (NFCI).

Replace relying on the underling CallInst for looking up the called
function and its types by instead adding the called function as operand,
in line with how called functions are handled in CallInst.

Operand bundles, metadata and fast-math flags are optionally used if
there's an underlying CallInst.

This enables creating VPWidenCallRecipes without requiring an underlying
IR instruction.

show more ...

[VPlan] Introduce recipes for VP loads and stores. (#87816)

Introduce new subclasses of VPWidenMemoryRecipe for VP
(vector-predicated) loads and stores to address multiple TODOs from
https://githu

[VPlan] Introduce recipes for VP loads and stores. (#87816)

Introduce new subclasses of VPWidenMemoryRecipe for VP
(vector-predicated) loads and stores to address multiple TODOs from
https://github.com/llvm/llvm-project/pull/76172

Note that the introduction of the new recipes also improves code-gen for
VP gather/scatters by removing the redundant header mask. With the new
approach, it is not sufficient to look at users of the widened canonical
IV to find all uses of the header mask.

In some cases, a widened IV is used instead of separately widening the
canonical IV. To handle that, first collect all VPValues representing header
masks (by looking at users of both the canonical IV and widened inductions
that are canonical) and then checking all users (recursively) of those header
masks.

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

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

show more ...

[VPlan] Split VPWidenMemoryInstructionRecipe (NFCI). (#87411)

This patch introduces a new VPWidenMemoryRecipe base class and distinct
sub-classes to model loads and stores.

This is a first step

[VPlan] Split VPWidenMemoryInstructionRecipe (NFCI). (#87411)

This patch introduces a new VPWidenMemoryRecipe base class and distinct
sub-classes to model loads and stores.

This is a first step in an effort to simplify and modularize code
generation for widened loads and stores and enable adding further more
specialized memory recipes.

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

show more ...

Revert "Reapply "[LV] Improve AnyOf reduction codegen. (#78304)""

This reverts commit c6e38b928c56f562aea68a8e90f02dbdf0eada85.

Causes miscompiles, see comments on #78304.

[VPlan] Remove unused first mask op from VPBlendRecipe. (#87770)

VPBlendRecipe does not use the first mask operand. Removing it allows
VPlan-based DCE to remove unused mask computations.

This al

[VPlan] Remove unused first mask op from VPBlendRecipe. (#87770)

VPBlendRecipe does not use the first mask operand. Removing it allows
VPlan-based DCE to remove unused mask computations.

This also fixes #87410, where unused Not VPInstructions are considered
having only their first lane demanded, but some of their operands
providing a vector value due to other users.

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

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

show more ...