PatternMatch: migrate to CmpPredicate (#118534)

With the introduction of CmpPredicate in 51a895a (IR: introduce struct
with CmpInst::Predicate and samesign), PatternMatch is one of the first
key p

PatternMatch: migrate to CmpPredicate (#118534)

With the introduction of CmpPredicate in 51a895a (IR: introduce struct
with CmpInst::Predicate and samesign), PatternMatch is one of the first
key pieces of infrastructure that must be updated to match a CmpInst
respecting samesign information. Implement this change to Cmp-matchers.

This is a preparatory step in migrating the codebase over to
CmpPredicate. Since we no functional changes are desired at this stage,
we have chosen not to migrate CmpPredicate::operator==(CmpPredicate)
calls to use CmpPredicate::getMatching(), as that would have visible
impact on tests that are not yet written: instead, we call
CmpPredicate::operator==(Predicate), preserving the old behavior, while
also inserting a few FIXME comments for follow-ups.

show more ...

[LoopVectorize] Vectorize select-cmp reduction pattern for increasing integer induction variable (#67812)

Consider the following loop:
```
int rdx = init;
for (int i = 0; i < n; ++i)
rdx

[LoopVectorize] Vectorize select-cmp reduction pattern for increasing integer induction variable (#67812)

Consider the following loop:
```
int rdx = init;
for (int i = 0; i < n; ++i)
rdx = (a[i] > b[i]) ? i : rdx;
```
We can vectorize this loop if `i` is an increasing induction variable.
The final reduced value will be the maximum of `i` that the condition
`a[i] > b[i]` is satisfied, or the start value `init`.

This patch added new RecurKind enums - IFindLastIV and FFindLastIV.

---------

Co-authored-by: Alexey Bataev <5361294+alexey-bataev@users.noreply.github.com>

show more ...

IVDesc: strip redundant arg in getOpcode call (NFC) (#118476)

[Analysis] Remove unused includes (NFC) (#114936)

Identified with misc-include-cleaner.

[InstCombine] Extend fcmp+select folding to minnum/maxnum intrinsics (#112088)

Today, InstCombine can fold fcmp+select patterns to minnum/maxnum
intrinsics when the nnan and nsz flags are set. The

[InstCombine] Extend fcmp+select folding to minnum/maxnum intrinsics (#112088)

Today, InstCombine can fold fcmp+select patterns to minnum/maxnum
intrinsics when the nnan and nsz flags are set. The ordering of the
operands in both the fcmp and select instructions is important for the
folding to occur.

maxnum patterns:
1. (a op b) ? a : b -> maxnum(a, b), where op is one of {ogt, oge}
2. (a op b) ? b : a -> maxnum(a, b), where op is one of {ule, ult}

The second pattern is supposed to make the order of the operands in the
select instruction irrelevant. However, the pattern matching code uses
the CmpInst::getInversePredicate method to invert the comparison
predicate. This method doesn't take into account the fast-math flags,
which can lead missing the folding opportunity.

The patch extends the pattern matching code to handle unordered fcmp
instructions. This allows the folding to occur even when the select
instruction has the operands in the inverse order.

New maxnum patterns:
1. (a op b) ? a : b -> maxnum(a, b), where op is one of {ugt, uge}
2. (a op b) ? b : a -> maxnum(a, b), where op is one of {ole, olt}

The same changes are applied to the minnum intrinsic.

show more ...

Consolidate all IR logic for getting the identity value of a reduction [nfc]

This change merges the three different places (at the IR layer) for
finding the identity value of a reduction into a sing

Consolidate all IR logic for getting the identity value of a reduction [nfc]

This change merges the three different places (at the IR layer) for
finding the identity value of a reduction into a single copy. This
depends on several prior commits which fix ommissions and bugs in
the distinct copies, but this patch itself should be fully
non-functional.

As the new comments and naming try to make clear, the identity value
is a property of the @llvm.vector.reduce.* intrinsic, not of e.g.
the recurrence descriptor. (We still provide an interface for
clients using recurrence descriptors, but the implementation simply
translates to the intrinsic which each corresponds to.)

As a note, the getIntrinsicIdentity API does not support fminnum/fmaxnum
or fminimum/fmaximum which is why we still need manual logic (but at
least only one copy of manual logic) for those cases.

show more ...

IVDescriptors: improve readability of a function (NFC) (#106219)

Avoid dereferencing operand to llvm::isa.

[LV] Prefer FLT_MIN/MAX for fmin/fmax reductions with ninf (#107141)

Analogous to 2c7786e94a1058bd4f96794a1d4f70dcb86e5cc5, cleanup a case
where the vectorizer is emitting a non-canonical identity

[LV] Prefer FLT_MIN/MAX for fmin/fmax reductions with ninf (#107141)

Analogous to 2c7786e94a1058bd4f96794a1d4f70dcb86e5cc5, cleanup a case
where the vectorizer is emitting a non-canonical identity value given
the available flags. We use largest/smallest value during ISEL, and VP
expansion, but not during vectorization.

Since the fmin/fmax/fminimum/fmaximum intrinsics don't require a start
value, this difference is only visible when masking of inactive lanes is
required.

Primary motivation of this change is simply to remove a difference
between version of code which reason about the identity value of a
reduction so I can kill all but one off.

In review, it was pointed out that this is actually a functional fix as well.
The old code used inf on a noinf reduction instruction - whose
result is poison! That wasn't the intent of the code.

show more ...

[LV] Separate AnyOf recurrence from getRecurrenceIdentity [NFC]

These recurrence types don't have a meaningful identity, and the
routine was abused to return the start value instead. Out of the
thr

[LV] Separate AnyOf recurrence from getRecurrenceIdentity [NFC]

These recurrence types don't have a meaningful identity, and the
routine was abused to return the start value instead. Out of the
three callers to this routine, only one actually wants this
behavior. This is a prep change for removing the routine entirely
and commoning it with other copies of the same logic.

show more ...

[IVDesc] Reuse getBinOpIdentity in getRecurrenceIdentity [nfc]

Avoid duplication so that we can easily tell these lists are in sync.

IVDescriptors: clarify getSCEV use in a function (NFC) (#106222)

getSCEV will assert unless the operand is SCEVable. Replace an instance
of the implementation of ScalarEvolution::isSCEVable (which

IVDescriptors: clarify getSCEV use in a function (NFC) (#106222)

getSCEV will assert unless the operand is SCEVable. Replace an instance
of the implementation of ScalarEvolution::isSCEVable (which checks that
the operand is either integer or pointer type) with a call to the
function, to make it clear that the subsequent use of getSCEV will not
fail.

show more ...

[LoopVectorize] LLVM fails to vectorise loops with multi-bool varables (#89226)

This change allows to consider compare instructions in the loop with
multiple use inside the loop and outside.

Thi

[LoopVectorize] LLVM fails to vectorise loops with multi-bool varables (#89226)

This change allows to consider compare instructions in the loop with
multiple use inside the loop and outside.

This change allows to vectorise this loop:
int foo(float* a, int n) {
_Bool any = 0;
_Bool all = 1;
for (int i = 0; i < n; i++) {
if (a[i] < 0.0f) {
any = 1;
} else {
all = 0;
}
}
return all ? 1 : any ? 2 : 3;
}

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

[InstSimplify][InstCombine] Remove unnecessary `m_c_*` matchers. (#81712)

This patch removes unnecessary `m_c_*` matchers since we always
canonicalize `commutive_op Cst, X` into `commutive_op X, Cs

[InstSimplify][InstCombine] Remove unnecessary `m_c_*` matchers. (#81712)

This patch removes unnecessary `m_c_*` matchers since we always
canonicalize `commutive_op Cst, X` into `commutive_op X, Cst`.

Compile-time impact:
https://llvm-compile-time-tracker.com/compare.php?from=bfc0b7c6891896ee8e9818f22800472510093864&to=d27b058bb9acaa43d3cadbf3cd889e8f79e5c634&stat=instructions:u

show more ...

[Analysis] Remove unnecessary includes (NFC)

[llvm] Fix duplicate word typos. NFC

Those fixes were taken from https://reviews.llvm.org/D137338

[LV] Rename the Select[I|F]Cmp reduction pattern to [I|F]AnyOf. (NFC)

Regarding this NFC change, please refer to the discussion in this thread. https://reviews.llvm.org/D150851#4467261

Reviewed By:

[LV] Rename the Select[I|F]Cmp reduction pattern to [I|F]AnyOf. (NFC)

Regarding this NFC change, please refer to the discussion in this thread. https://reviews.llvm.org/D150851#4467261

Reviewed By: Ayal

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

show more ...

[IVDescriptors] Remove typed pointer support (NFC)

This also removes the element type from the descriptor, as it is
always i8. The meaning of the step is now the same between
integers and pointers.

[LV] Add support for minimum/maximum intrinsics

{mini|maxi}mum intrinsics are different from {min|max}num intrinsics in
the propagation of NaN and signed zero. Also, the minnum/maxnum
intrinsics req

[LV] Add support for minimum/maximum intrinsics

{mini|maxi}mum intrinsics are different from {min|max}num intrinsics in
the propagation of NaN and signed zero. Also, the minnum/maxnum
intrinsics require the presence of nsz flags to be valid reductions in
vectorizer. In this regard, we introduce a new recurrence kind and also
add support for identifying reduction patterns using these intrinsics.

The reduction intrinsics and lowering was introduced here: 26bfbec5d2.

There are tests added which show how this interacts across chains of
min/max patterns.

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

show more ...

[IVDescriptors] Add assert to isInductionPhi to check for invalid Phis

Phis that are present inside loop headers can only be Induction Phis
legally. This patch adds an assertion to isInductionPhi wh

[IVDescriptors] Add assert to isInductionPhi to check for invalid Phis

Phis that are present inside loop headers can only be Induction Phis
legally. This patch adds an assertion to isInductionPhi which checks for
the said legality and it also updates the docs of the said function to
reflect the given legality.

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

show more ...

Recommit "[VPlan] Switch to checking sinking legality for recurrences in VPlan."

This reverts the revert commit 3d8ed8b5192a59104bfbd5bf7ac84d035ee0a4a5.

The new version of the patch adds a set to

Recommit "[VPlan] Switch to checking sinking legality for recurrences in VPlan."

This reverts the revert commit 3d8ed8b5192a59104bfbd5bf7ac84d035ee0a4a5.

The new version of the patch adds a set to avoid duplicating work in
isFixedOrderRecurrence, which was previously done through the removed
SinkAfter map.

Original commit message:
Building on D142885 and D142589, retire the SinkAfter map from the
recurrence handling code. It is replaced by checking whether it is
possible to sink all users of a recurrence directly in VPlan. This
results in simpler code overall and allows to handle additional cases
(see the improvements in @test_crash).

Depends on D142885.
Depends on D142589.

Reviewed By: Ayal

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

show more ...

Revert "[VPlan] Switch to checking sinking legality for recurrences in VPlan."

This reverts commit 7fc0b3049df532fce726d1ff6869a9f6e3183780.

Causes a clang hang when building xz utils, github issue

Revert "[VPlan] Switch to checking sinking legality for recurrences in VPlan."

This reverts commit 7fc0b3049df532fce726d1ff6869a9f6e3183780.

Causes a clang hang when building xz utils, github issue #62187.

show more ...

[VPlan] Switch to checking sinking legality for recurrences in VPlan.

Building on D142885 and D142589, retire the SinkAfter map from the
recurrence handling code. It is replaced by checking whether

[VPlan] Switch to checking sinking legality for recurrences in VPlan.

Building on D142885 and D142589, retire the SinkAfter map from the
recurrence handling code. It is replaced by checking whether it is
possible to sink all users of a recurrence directly in VPlan. This
results in simpler code overall and allows to handle additional cases
(see the improvements in @test_crash).

Depends on D142885.
Depends on D142589.

Reviewed By: Ayal

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

show more ...

[IVDescriptors] Add pointer InductionDescriptors with non-constant strides (try 2)

(JFYI - This has been heavily reframed since original attempt at landing.)

This change updates the InductionDescri

[IVDescriptors] Add pointer InductionDescriptors with non-constant strides (try 2)

(JFYI - This has been heavily reframed since original attempt at landing.)

This change updates the InductionDescriptor logic to allow matching a pointer IV with a non-constant stride, but also updates the LoopVectorizer to bailout on such descriptors by default. This preserves the default vectorizer behavior.

In review, it was pointed out that there's multiple unfortunate performance implications which need to be addressed before this can be enabled. Having a flag allows us to exercise the behavior, and write test cases for logic which is otherwise unreachable (or hard to reach).

This will also enable non-constant stride pointer recurrences for other consumers. I've audited said code, and don't see any obvious issues.

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

show more ...

Revert "[IVDescriptors] Add pointer InductionDescriptors with non-constant strides"

Multiple errors have being reported on
https://reviews.llvm.org/rG498aa534f472d28db893aa9a8627d0b46e17f312

Revert

Revert "[IVDescriptors] Add pointer InductionDescriptors with non-constant strides"

Multiple errors have being reported on
https://reviews.llvm.org/rG498aa534f472d28db893aa9a8627d0b46e17f312

Reverting until the correctness issues can be resolved.

We are also seeing a lot of performance differences from the patch. Some are
looking good, but some are looking pretty bad.

show more ...