[VPlan] Remove dead recipes across whole plan.

This extends removeDeadRecipe to remove recipes across the whole plan.

Reviewed By: Ayal

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

[LV] Use exiting block instead of latch in addUsersInExitBlock.

The latch may not be the exiting block. Use the exiting block instead
when looking up the incoming value of the LCSSA phi node. This f

[LV] Use exiting block instead of latch in addUsersInExitBlock.

The latch may not be the exiting block. Use the exiting block instead
when looking up the incoming value of the LCSSA phi node. This fixes a
crash with early-exit loops.

show more ...

[LV] Re-generate check lines for loop-form.ll test.

Revert "[NFCI] Regenerate SROA/LoopVectorize test checks"

This reverts commit 14e3450fb57305aa9ff3e9e60687b458e43835c9.

[NFCI] Regenerate LoopVectorize test checks

[LV] Create & use VPScalarIVSteps for all scalar users.

This patch is a follow-up to D115953. It updates optimizeInductions
to also introduce new VPScalarIVStepsRecipes if an IV has both vector
and

[LV] Create & use VPScalarIVSteps for all scalar users.

This patch is a follow-up to D115953. It updates optimizeInductions
to also introduce new VPScalarIVStepsRecipes if an IV has both vector
and scalar uses.

It updates all uses that only need scalar values to use the newly
created recipe for the scalar steps.

This completes untangling of VPWidenIntOrFpInductionRecipe
code-generation. Now the recipe *only* creates the widened vector
values, as it says on the tin.

The code to genereate IR has been moved directly to
VPWidenIntOrFpInductionRecipe::execute.

Note that the recipe has been updated to hold a reference to
ScalarEvolution, which is needed to expand the step, until we can place
the corresponding SCEV expansion in the pre-header.

Depends on D120827.

Reviewed By: Ayal

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

show more ...

[VPlan] Use VPlan to check if only the first lane is used.

This removes the remaining dependence on LoopVectorizationCostModel from
buildScalarSteps and is required so it can be moved out of ILV.

I

[VPlan] Use VPlan to check if only the first lane is used.

This removes the remaining dependence on LoopVectorizationCostModel from
buildScalarSteps and is required so it can be moved out of ILV.

It also improves allows us to remove a few unneeded instructions.

Reviewed By: Ayal

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

show more ...

[test] refresh a couple of autogen tests

[VPlan] Support sinking recipes with uniform users outside sink target.

This is a first step towards addressing the last remaining limitation of
the VPlan version of sinkScalarOperands: the legacy v

[VPlan] Support sinking recipes with uniform users outside sink target.

This is a first step towards addressing the last remaining limitation of
the VPlan version of sinkScalarOperands: the legacy version can
partially sink operands. For example, if a GEP has uniform users outside
the sink target block, then the legacy version will sink all scalar
GEPs, other than the one for lane 0.

This patch works towards addressing this case in the VPlan version by
detecting such cases and duplicating the sink candidate. All users
outside of the sink target will be updated to use the uniform clone.

Note that this highlights an issue with VPValue naming. If we duplicate
a replicate recipe, they will share the same underlying IR value and
both VPValues will have the same name ir<%gep>.

Reviewed By: Ayal

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

show more ...

[LV] Enable vectorization of multiple exit loops w/computable exit counts

This change enables vectorization of multiple exit loops when the exit count is statically computable. That requirement - sh

[LV] Enable vectorization of multiple exit loops w/computable exit counts

This change enables vectorization of multiple exit loops when the exit count is statically computable. That requirement - shared with the rest of LV - in turn requires each exit to be analyzeable and to dominate the latch.

The majority of work to support this was done in a set of previous patches. In particular,, 72314466 avoids having multiple edges from the middle block to the exits, and 4b33b2387 which added support for non-latch single exit and multiple exits with a single exiting block. As a result, this change is basically just removing a bailout and adjusting some tests now that the prerequisite work is done and has stuck in tree for a bit.

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

show more ...

[LV] Unconditionally branch from middle to scalar preheader if the scalar loop must execute (try 4)

Resubmit after the following changes:

* Fix a latent bug related to unrolling with required epilo

[LV] Unconditionally branch from middle to scalar preheader if the scalar loop must execute (try 4)

Resubmit after the following changes:

* Fix a latent bug related to unrolling with required epilogue (see e49d65f). I believe this is the cause of the prior PPC buildbot failure.
* Disable non-latch exits for epilogue vectorization to be safe (9ffa90d)
* Split out assert movement (600624a) to reduce churn if this gets reverted again.

Previous commit message (try 3)

Resubmit after fixing test/Transforms/LoopVectorize/ARM/mve-gather-scatter-tailpred.ll

Previous commit message...

This is a resubmit of 3e5ce4 (which was reverted by 7fe41ac). The original commit caused a PPC build bot failure we never really got to the bottom of. I can't reproduce the issue, and the bot owner was non-responsive. In the meantime, we stumbled across an issue which seems possibly related, and worked around a latent bug in 80e8025. My best guess is that the original patch exposed that latent issue at higher frequency, but it really is just a guess.

Original commit message follows...

If we know that the scalar epilogue is required to run, modify the CFG to end the middle block with an unconditional branch to scalar preheader. This is instead of a conditional branch to either the preheader or the exit block.

The motivation to do this is to support multiple exit blocks. Specifically, the current structure forces us to identify immediate dominators and *which* exit block to branch from in the middle terminator. For the multiple exit case - where we know require scalar will hold - these questions are ill formed.

This is the last change needed to support multiple exit loops, but since the diffs are already large enough, I'm going to land this, and then enable separately. You can think of this as being NFCIish prep work, but the changes are a bit too involved for me to feel comfortable tagging the review that way.

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

show more ...

[LV] Mark increment of main vector loop induction variable as NUW.

This patch marks the induction increment of the main induction variable
of the vector loop as NUW when not folding the tail.

If th

[LV] Mark increment of main vector loop induction variable as NUW.

This patch marks the induction increment of the main induction variable
of the vector loop as NUW when not folding the tail.

If the tail is not folded, we know that End - Start >= Step (either
statically or through the minimum iteration checks). We also know that both
Start % Step == 0 and End % Step == 0. We exit the vector loop if %IV +
%Step == %End. Hence we must exit the loop before %IV + %Step unsigned
overflows and we can mark the induction increment as NUW.

This should make SCEV return more precise bounds for the created vector
loops, used by later optimizations, like late unrolling.

At the moment quite a few tests still need to be updated, but before
doing so I'd like to get initial feedback to make sure I am not missing
anything.

Note that this could probably be further improved by using information
from the original IV.

Attempt of modeling of the assumption in Alive2:
https://alive2.llvm.org/ce/z/H_DL_g

Part of a set of fixes required for PR50412.

Reviewed By: mkazantsev

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

show more ...

Revert "[LV] Unconditionally branch from middle to scalar preheader if the scalar loop must execute (try 3)"

This reverts commit 6d3e3ae8a9ca10e063d541a959f4fe4cdb003dba.

Still seeing PPC build bot

Revert "[LV] Unconditionally branch from middle to scalar preheader if the scalar loop must execute (try 3)"

This reverts commit 6d3e3ae8a9ca10e063d541a959f4fe4cdb003dba.

Still seeing PPC build bot failures, and one arm self host bot failing. I'm officially stumped, and need help from a bot owner to reduce.

show more ...

[LV] Unconditionally branch from middle to scalar preheader if the scalar loop must execute (try 3)

Resubmit after fixing test/Transforms/LoopVectorize/ARM/mve-gather-scatter-tailpred.ll

Previous c

[LV] Unconditionally branch from middle to scalar preheader if the scalar loop must execute (try 3)

Resubmit after fixing test/Transforms/LoopVectorize/ARM/mve-gather-scatter-tailpred.ll

Previous commit message...

This is a resubmit of 3e5ce4 (which was reverted by 7fe41ac). The original commit caused a PPC build bot failure we never really got to the bottom of. I can't reproduce the issue, and the bot owner was non-responsive. In the meantime, we stumbled across an issue which seems possibly related, and worked around a latent bug in 80e8025. My best guess is that the original patch exposed that latent issue at higher frequency, but it really is just a guess.

Original commit message follows...

If we know that the scalar epilogue is required to run, modify the CFG to end the middle block with an unconditional branch to scalar preheader. This is instead of a conditional branch to either the preheader or the exit block.

The motivation to do this is to support multiple exit blocks. Specifically, the current structure forces us to identify immediate dominators and *which* exit block to branch from in the middle terminator. For the multiple exit case - where we know require scalar will hold - these questions are ill formed.

This is the last change needed to support multiple exit loops, but since the diffs are already large enough, I'm going to land this, and then enable separately. You can think of this as being NFCIish prep work, but the changes are a bit too involved for me to feel comfortable tagging the review that way.

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

show more ...

Revert "[LV] Unconditionally branch from middle to scalar preheader if the scalar loop must execute"

This reverts commit c23ce54b36b1a52eb280ea1d59802b56d6dd9800. I apparently missed some newly add

Revert "[LV] Unconditionally branch from middle to scalar preheader if the scalar loop must execute"

This reverts commit c23ce54b36b1a52eb280ea1d59802b56d6dd9800. I apparently missed some newly added non-x86 tests.

show more ...

[LV] Unconditionally branch from middle to scalar preheader if the scalar loop must execute

This is a resubmit of 3e5ce4 (which was reverted by 7fe41ac). The original commit caused a PPC build bot

[LV] Unconditionally branch from middle to scalar preheader if the scalar loop must execute

This is a resubmit of 3e5ce4 (which was reverted by 7fe41ac). The original commit caused a PPC build bot failure we never really got to the bottom of. I can't reproduce the issue, and the bot owner was non-responsive. In the meantime, we stumbled across an issue which seems possibly related, and worked around a latent bug in 80e8025. My best guess is that the original patch exposed that latent issue at higher frequency, but it really is just a guess.

Original commit message follows...

If we know that the scalar epilogue is required to run, modify the CFG to end the middle block with an unconditional branch to scalar preheader. This is instead of a conditional branch to either the preheader or the exit block.

The motivation to do this is to support multiple exit blocks. Specifically, the current structure forces us to identify immediate dominators and *which* exit block to branch from in the middle terminator. For the multiple exit case - where we know require scalar will hold - these questions are ill formed.

This is the last change needed to support multiple exit loops, but since the diffs are already large enough, I'm going to land this, and then enable separately. You can think of this as being NFCIish prep work, but the changes are a bit too involved for me to feel comfortable tagging the review that way.

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

show more ...

[NFCI] SCEVExpander: emit intrinsics for integral {u,s}{min,max} SCEV expressions

These intrinsics, not the icmp+select are the canonical form nowadays,
so we might as well directly emit them.

This

[NFCI] SCEVExpander: emit intrinsics for integral {u,s}{min,max} SCEV expressions

These intrinsics, not the icmp+select are the canonical form nowadays,
so we might as well directly emit them.

This should not cause any regressions, but if it does,
then then they would needed to be fixed regardless.

Note that this doesn't deal with `SCEVExpander::isHighCostExpansion()`,
but that is a pessimization, not a correctness issue.

Additionally, the non-intrinsic form has issues with undef,
see https://reviews.llvm.org/D88287#2587863

show more ...

[Vectorizers][TTI] remove option to bypass creation of vector reduction intrinsics

The vector reduction intrinsics started life as experimental ops, so backend support
was lacking. As part of promot

[Vectorizers][TTI] remove option to bypass creation of vector reduction intrinsics

The vector reduction intrinsics started life as experimental ops, so backend support
was lacking. As part of promoting them to 1st-class intrinsics, however, codegen
support was added/improved:
D58015
D90247

So I think it is safe to now remove this complication from IR.

Note that we still have an IR-level codegen expansion pass for these as discussed
in D95690. Removing that is another step in simplifying the logic. Also note that
x86 was already unconditionally forming reductions in IR, so there should be no
difference for x86.

I spot checked a couple of the tests here by running them through opt+llc and did
not see any asm diffs.

If we do find functional differences for other targets, it should be possible
to (at least temporarily) restore the shuffle IR with the ExpandReductions IR
pass.

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

show more ...

Revert "[LV] Unconditionally branch from middle to scalar preheader if the scalar loop must execute"

This reverts commit 3e5ce49e5371ce4feadbf97dd5c2b652d9db3d1d.

Tests started failing on PPC, for

Revert "[LV] Unconditionally branch from middle to scalar preheader if the scalar loop must execute"

This reverts commit 3e5ce49e5371ce4feadbf97dd5c2b652d9db3d1d.

Tests started failing on PPC, for example:
http://lab.llvm.org:8011/#/builders/105/builds/5569

show more ...

[LV] Unconditionally branch from middle to scalar preheader if the scalar loop must execute

If we know that the scalar epilogue is required to run, modify the CFG to end the middle block with an unc

[LV] Unconditionally branch from middle to scalar preheader if the scalar loop must execute

If we know that the scalar epilogue is required to run, modify the CFG to end the middle block with an unconditional branch to scalar preheader. This is instead of a conditional branch to either the preheader or the exit block.

The motivation to do this is to support multiple exit blocks. Specifically, the current structure forces us to identify immediate dominators and *which* exit block to branch from in the middle terminator. For the multiple exit case - where we know require scalar will hold - these questions are ill formed.

This is the last change needed to support multiple exit loops, but since the diffs are already large enough, I'm going to land this, and then enable separately. You can think of this as being NFCI-ish prep work, but the changes are a bit too involved for me to feel comfortable tagging the change that way.

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

show more ...

[test] pre commit a couple more tests for vectorizing multiple exit loops

[LV] Relax assumption that LCSSA implies single entry

This relates to the ongoing effort to support vectorization of multiple exit loops (see D93317).

The previous code assumed that LCSSA phis were

[LV] Relax assumption that LCSSA implies single entry

This relates to the ongoing effort to support vectorization of multiple exit loops (see D93317).

The previous code assumed that LCSSA phis were always single entry before the vectorizer ran. This was correct, but only because the vectorizer allowed only a single exiting edge. There's nothing in the definition of LCSSA which requires single entry phis.

A common case where this comes up is with a loop with multiple exiting blocks which all reach a common exit block. (e.g. see the test updates)

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

show more ...

Precommit tests requested for D93725

[IR] Let IRBuilder's CreateVectorSplat/CreateShuffleVector use poison as placeholder

This patch updates IRBuilder to create insertelement/shufflevector using poison as a placeholder.

Reviewed By: n

[IR] Let IRBuilder's CreateVectorSplat/CreateShuffleVector use poison as placeholder

This patch updates IRBuilder to create insertelement/shufflevector using poison as a placeholder.

Reviewed By: nikic

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

show more ...

Reapply "[LV] Vectorize (some) early and multiple exit loops"" w/fix for builder

This reverts commit 4ffcd4fe9ac2ee948948f732baa16663eb63f1c7 thus restoring e4df6a40dad.

The only change from the or

Reapply "[LV] Vectorize (some) early and multiple exit loops"" w/fix for builder

This reverts commit 4ffcd4fe9ac2ee948948f732baa16663eb63f1c7 thus restoring e4df6a40dad.

The only change from the original patch is to add "llvm::" before the call to empty(iterator_range). This is a speculative fix for the ambiguity reported on some builders.

show more ...