[LoopVectorize] Permit vectorisation of more select(cmp(), X, Y) reduction patterns

This patch adds further support for vectorisation of loops that involve
selecting an integer value based on a prev

[LoopVectorize] Permit vectorisation of more select(cmp(), X, Y) reduction patterns

This patch adds further support for vectorisation of loops that involve
selecting an integer value based on a previous comparison. Consider the
following C++ loop:

int r = a;
for (int i = 0; i < n; i++) {
if (src[i] > 3) {
r = b;
}
src[i] += 2;
}

We should be able to vectorise this loop because all we are doing is
selecting between two states - 'a' and 'b' - both of which are loop
invariant. This just involves building a vector of values that contain
either 'a' or 'b', where the final reduced value will be 'b' if any lane
contains 'b'.

The IR generated by clang typically looks like this:

%phi = phi i32 [ %a, %entry ], [ %phi.update, %for.body ]
...
%pred = icmp ugt i32 %val, i32 3
%phi.update = select i1 %pred, i32 %b, i32 %phi

We already detect min/max patterns, which also involve a select + cmp.
However, with the min/max patterns we are selecting loaded values (and
hence loop variant) in the loop. In addition we only support certain
cmp predicates. This patch adds a new pattern matching function
(isSelectCmpPattern) and new RecurKind enums - SelectICmp & SelectFCmp.
We only support selecting values that are integer and loop invariant,
however we can support any kind of compare - integer or float.

Tests have been added here:

Transforms/LoopVectorize/AArch64/sve-select-cmp.ll
Transforms/LoopVectorize/select-cmp-predicated.ll
Transforms/LoopVectorize/select-cmp.ll

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

show more ...

[LV] Move reduction PHI node fixup to VPlan::execute (NFC).

All information to fix-up the reduction phi nodes in the vectorized loop
is available in VPlan now. This patch moves the code to do so, to

[LV] Move reduction PHI node fixup to VPlan::execute (NFC).

All information to fix-up the reduction phi nodes in the vectorized loop
is available in VPlan now. This patch moves the code to do so, to make
this clearer. Fixing up the loop exit value still relies on other
information and remains outside of VPlan for now.

Reviewed By: Ayal

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

show more ...

[Transforms] Drop unnecessary const from return types (NFC)

Identified with readability-const-return-type.

[LV] Move recurrence backedge fixup code to VPlan::execute (NFC).

As suggested in D105008, move the code that fixes up the backedge value
for first order recurrences to VPlan::execute.

Now all that

[LV] Move recurrence backedge fixup code to VPlan::execute (NFC).

As suggested in D105008, move the code that fixes up the backedge value
for first order recurrences to VPlan::execute.

Now all that remains in fixFirstOrderRecurrences is the code responsible
for creating the exit values in the middle block.

Reviewed By: Ayal

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

show more ...

Recommit "[VPlan] Add recipe for first-order rec phis, make splicing explicit."

This reverts the revert commit b1777b04dc4b1a9fee0e7effa7e177892ab32ef0.

The patch originally got reverted due to a c

Recommit "[VPlan] Add recipe for first-order rec phis, make splicing explicit."

This reverts the revert commit b1777b04dc4b1a9fee0e7effa7e177892ab32ef0.

The patch originally got reverted due to a crash:
https://bugs.chromium.org/p/chromium/issues/detail?id=1232798#c2

The underlying issue was that we were not using the stored values from
the modified memory recipes, but the out-of-date values directly from
the IR (accessed via the VPlan). This should be fixed in d995d6376. A
reduced version of the reproducer has been added in 93664503be6b.

show more ...

Revert "[VPlan] Add recipe for first-order rec phis, make splicing explicit."

Makes clang crash: https://reviews.llvm.org/D105008#2903350
This reverts commit d2a73fb44ea0b8c981e4b923f811f18793fc4770

Revert "[VPlan] Add recipe for first-order rec phis, make splicing explicit."

Makes clang crash: https://reviews.llvm.org/D105008#2903350
This reverts commit d2a73fb44ea0b8c981e4b923f811f18793fc4770.

Also revert a minor formatting follow-up:
This reverts commit 82834a673246f27a541ffcc57e0eb65b008102ef.

show more ...

[VPlan] Add recipe for first-order rec phis, make splicing explicit.

This patch adds a VPFirstOrderRecurrencePHIRecipe, to further untangle
VPWidenPHIRecipe into distinct recipes for distinct use ca

[VPlan] Add recipe for first-order rec phis, make splicing explicit.

This patch adds a VPFirstOrderRecurrencePHIRecipe, to further untangle
VPWidenPHIRecipe into distinct recipes for distinct use cases/lowering.
See D104989 for a new recipe for reduction phis.

This patch also introduces a new `FirstOrderRecurrenceSplice`
VPInstruction opcode, which is used to make the forming of the vector
recurrence value explicit in VPlan. This more accurately models def-uses
in VPlan and also simplifies code-generation. Now, the vector recurrence
values are created at the right place during VPlan-codegeneration,
rather than during post-VPlan fixups.

Reviewed By: Ayal

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

show more ...

[VPlan] Remove default arg from getVPValue (NFC).

The const version of VPValue::getVPValue still had a default value for
the value index. Remove the default value and use getVPSingleValue
instead, w

[VPlan] Remove default arg from getVPValue (NFC).

The const version of VPValue::getVPValue still had a default value for
the value index. Remove the default value and use getVPSingleValue
instead, which is the proper function.

show more ...

Recommit "[VPlan] Add VPReductionPHIRecipe (NFC)." and follow-ups.

This reverts commit 706bbfb35bd31051e46ac77aab3e9b2dbc3abe78.

The committed version moves the definition of VPReductionPHIRecipe o

Recommit "[VPlan] Add VPReductionPHIRecipe (NFC)." and follow-ups.

This reverts commit 706bbfb35bd31051e46ac77aab3e9b2dbc3abe78.

The committed version moves the definition of VPReductionPHIRecipe out
of an ifdef only intended for ::print helpers. This should resolve the
build failures that caused the revert

show more ...

Revert "[VPlan] Add VPReductionPHIRecipe (NFC)." and follow-ups

This reverts commit 3fed6d443f802c43aade1b5b1b09f5e2f8b3edb1,
bbcbf21ae60c928e07dde6a1c468763b3209d1e6 and
6c3451cd76cbd0cd973d9c2b08b

Revert "[VPlan] Add VPReductionPHIRecipe (NFC)." and follow-ups

This reverts commit 3fed6d443f802c43aade1b5b1b09f5e2f8b3edb1,
bbcbf21ae60c928e07dde6a1c468763b3209d1e6 and
6c3451cd76cbd0cd973d9c2b08b168dcd0bce3c2.

The changes causing build failures with certain configurations, e.g.
https://lab.llvm.org/buildbot/#/builders/67/builds/3365/steps/6/logs/stdio

lib/libLLVMVectorize.a(LoopVectorize.cpp.o): In function `llvm::VPRecipeBuilder::tryToCreateWidenRecipe(llvm::Instruction*, llvm::ArrayRef<llvm::VPValue*>, llvm::VFRange&, std::unique_ptr<llvm::VPlan, std::default_delete<llvm::VPlan> >&) [clone .localalias.8]':
LoopVectorize.cpp:(.text._ZN4llvm15VPRecipeBuilder22tryToCreateWidenRecipeEPNS_11InstructionENS_8ArrayRefIPNS_7VPValueEEERNS_7VFRangeERSt10unique_ptrINS_5VPlanESt14default_deleteISA_EE+0x63b): undefined reference to `vtable for llvm::VPReductionPHIRecipe'
collect2: error: ld returned 1 exit status

show more ...

[VPlan] Add VPReductionPHIRecipe (NFC).

This patch is a first step towards splitting up VPWidenPHIRecipe into
separate recipes for the 3 distinct cases they model:

1. reduction phis,
2. fir

[VPlan] Add VPReductionPHIRecipe (NFC).

This patch is a first step towards splitting up VPWidenPHIRecipe into
separate recipes for the 3 distinct cases they model:

1. reduction phis,
2. first-order recurrence phis,
3. pointer induction phis.

This allows untangling the code generation and allows us to reduce the
reliance on LoopVectorizationCostModel during VPlan code generation.

Discussed/suggested in D100102, D100113, D104197.

Reviewed By: Ayal

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

show more ...

[VPlan] Print successors of VPRegionBlocks.

The non-DOT printing does not include the successors of VPregionBlocks.
This patch use the same style for printing successors as for
VPBasicBlock.

I thin

[VPlan] Print successors of VPRegionBlocks.

The non-DOT printing does not include the successors of VPregionBlocks.
This patch use the same style for printing successors as for
VPBasicBlock.

I think the printing of successors could be a bit improved further, as
at the moment it is hard to ensure a check line matches all successors.
But that can be done as follow-up.

Reviewed By: a.elovikov

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

show more ...

[VPlan] Add mayReadOrWriteMemory & friends.

This patch adds initial implementation of mayReadOrWriteMemory,
mayReadFromMemory and mayWriteToMemory to VPRecipeBase.

Used by D100258.

[VPlan] Add VPUserID to distinguish between recipes and others.

This allows cast/dyn_cast'ing from VPUser to recipes. This is needed
because there are VPUsers that are not recipes.

Reviewed By: gil

[VPlan] Add VPUserID to distinguish between recipes and others.

This allows cast/dyn_cast'ing from VPUser to recipes. This is needed
because there are VPUsers that are not recipes.

Reviewed By: gilr, a.elovikov

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

show more ...

[VPlan] Adjust assert in splitBlock to allow splitting at end.

SplitAt should only be dereferenced in the assert if it does not point
to the end of the block. This fixes a crash in the added test ca

[VPlan] Adjust assert in splitBlock to allow splitting at end.

SplitAt should only be dereferenced in the assert if it does not point
to the end of the block. This fixes a crash in the added test case.

show more ...

[VPlan] Properly handle sinking of replicate regions.

This patch updates the code that sinks recipes required for first-order
recurrences to properly handle replicate-regions. At the moment, the
cod

[VPlan] Properly handle sinking of replicate regions.

This patch updates the code that sinks recipes required for first-order
recurrences to properly handle replicate-regions. At the moment, the
code would just move the replicate recipe out of its replicate-region,
producing an invalid VPlan.

When sinking a recipe in a replicate-region, we have to sink the whole
region. To do that, we first need to split the block at the target
recipe and move the region in between.

This patch also adds a splitAt helper to VPBasicBlock to split a
VPBasicBlock at a given iterator.

Fixes PR50009.

Reviewed By: Ayal

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

show more ...

[VPlan] Add VPBasicBlock::phis() helper (NFC).

This patch introduces a helper to obtain an iterator range for the
PHI-like recipes in a block.

Reviewed By: Ayal

Differential Revision: https://revi

[VPlan] Add VPBasicBlock::phis() helper (NFC).

This patch introduces a helper to obtain an iterator range for the
PHI-like recipes in a block.

Reviewed By: Ayal

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

show more ...

[VPlan] Add getVPSingleValue helper.

As suggested in D99294, this adds a getVPSingleValue helper to use for
recipes that are guaranteed to define a single value. This replaces uses
of getVPValue() w

[VPlan] Add getVPSingleValue helper.

As suggested in D99294, this adds a getVPSingleValue helper to use for
recipes that are guaranteed to define a single value. This replaces uses
of getVPValue() which used to default to I = 0.

show more ...

[VPlan] Use recursive traversal iterator in VPSlotTracker.

This patch simplifies VPSlotTracker by using the recursive traversal
iterator to traverse all blocks in a VPlan in reverse post-order when

[VPlan] Use recursive traversal iterator in VPSlotTracker.

This patch simplifies VPSlotTracker by using the recursive traversal
iterator to traverse all blocks in a VPlan in reverse post-order when
numbering VPValues in a plan.

This depends on a fix to RPOT (D100169). It also extends the traversal
unit tests to check RPOT.

Reviewed By: a.elovikov

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

show more ...

[VPlan] Add VPRecipeBase::mayHaveSideEffects.

Add an initial version of a helper to determine whether a recipe may
have side-effects.

Reviewed By: a.elovikov

Differential Revision: https://reviews

[VPlan] Add VPRecipeBase::mayHaveSideEffects.

Add an initial version of a helper to determine whether a recipe may
have side-effects.

Reviewed By: a.elovikov

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

show more ...

[VPlan] Print VPValue operands for VPWidenPHI if possible.

For VPWidenPHIRecipes that model all incoming values as VPValue
operands, print those operands instead of printing the original PHI.

D9929

[VPlan] Print VPValue operands for VPWidenPHI if possible.

For VPWidenPHIRecipes that model all incoming values as VPValue
operands, print those operands instead of printing the original PHI.

D99294 updates recipes of reduction PHIs to use the VPValue for the
incoming value from the loop backedge, making use of this new printing.

show more ...

[VPlan] Include name when printing after 93a9d2de8f4f.

The name is included when printing in DOT mode. Also print it in non-DOT
mode after 93a9d2de8f4f.

This will become more important to distingui

[VPlan] Include name when printing after 93a9d2de8f4f.

The name is included when printing in DOT mode. Also print it in non-DOT
mode after 93a9d2de8f4f.

This will become more important to distinguish different plans once
VPlans are gradually refined.

show more ...

[NFC][VPlan] Guard print routines with "#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)"

Reviewed By: mehdi_amini

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

[VPlan] Add plain text (not DOT's digraph) dumps

I foresee two uses for this:
1) It's easier to use those in debugger.
2) Once we start implementing more VPlan-to-VPlan transformations (especially

[VPlan] Add plain text (not DOT's digraph) dumps

I foresee two uses for this:
1) It's easier to use those in debugger.
2) Once we start implementing more VPlan-to-VPlan transformations (especially
inner loop massaging stuff), using the vectorized LLVM IR as CHECK targets in
LIT test would become too obscure. I can imagine that we'd want to CHECK
against VPlan dumps after multiple transformations instead. That would be
easier with plain text dumps than with DOT format.

Reviewed By: fhahn

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

show more ...

Revert "[VPlan] Add plain text (not DOT's digraph) dumps"

This reverts commit 6b053c9867a3ede32e51cef3ed972d5ce5b38bc0.
The build is broken:

ld.lld: error: undefined symbol: llvm::VPlan::printDOT(l

Revert "[VPlan] Add plain text (not DOT's digraph) dumps"

This reverts commit 6b053c9867a3ede32e51cef3ed972d5ce5b38bc0.
The build is broken:

ld.lld: error: undefined symbol: llvm::VPlan::printDOT(llvm::raw_ostream&) const
>>> referenced by LoopVectorize.cpp
>>> LoopVectorize.cpp.o:(llvm::LoopVectorizationPlanner::printPlans(llvm::raw_ostream&)) in archive lib/libLLVMVectorize.a

show more ...