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

[LICM] Use DomTreeUpdater version of SplitBlockPredecessors, nfc (#107190)

The DominatorTree version is marked for deprecation, so we use the
DomTreeUpdater version. We also update sinkRegion() to

[LICM] Use DomTreeUpdater version of SplitBlockPredecessors, nfc (#107190)

The DominatorTree version is marked for deprecation, so we use the
DomTreeUpdater version. We also update sinkRegion() to iterate over
basic blocks instead of DomTreeNodes. The loop body calls
SplitBlockPredecessors. The DTU version calls
DomTreeUpdater::apply_updates(), which may call DominatorTree::reset().
This invalidates the worklist of DomTreeNodes to iterate over.

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

Remove "Target" from createXReduction naming [nfc]

Despite the stale comments, none of these actually use TTI, and they're
solely generating standard LLVM IR.

Prefer use of 0.0 over -0.0 for fadd reductions w/nsz (in IR) (#106770)

This is a follow up to 924907bc6, and is mostly motivated by consistency
but does include one additional optimization. In gen

Prefer use of 0.0 over -0.0 for fadd reductions w/nsz (in IR) (#106770)

This is a follow up to 924907bc6, and is mostly motivated by consistency
but does include one additional optimization. In general, we prefer 0.0
over -0.0 as the identity value for an fadd. We use that value in
several places, but don't in others. So, let's be consistent and use the
same identity (when nsz allows) everywhere.

This creates a bunch of test churn, but due to 924907bc6, most of that
churn doesn't actually indicate a change in codegen. The exception is
that this change enables the use of 0.0 for nsz, but *not* reasoc, fadd
reductions. Or said differently, it allows the neutral value of an
ordered fadd reduction to be 0.0.

show more ...

Reuse getBinOpIdentity in createAnyOfTargetReduction [nfc]

Consolidating code so that we have one copy instead of multiple reasoning
about identity element. Note that we're (deliberately) not passi

Reuse getBinOpIdentity in createAnyOfTargetReduction [nfc]

Consolidating code so that we have one copy instead of multiple reasoning
about identity element. Note that we're (deliberately) not passing
the FMF flags to common utility to preserve behavior in this change.

show more ...

Restructure createSimpleTargetReduction to match VP path [NFC]

Reduces code significantly, but more importantly makes it obvious that
this variant matches the VP variant just below.

[llvm] Make InstSimplifyFolder constructor explicit (NFC) (#101654)

[VP] Refactor VectorBuilder to avoid layering violation. NFC (#99276)

This patch refactors the handling of reduction to eliminate layering
violations.

* Introduced `getReductionIntrinsicID` in L

[VP] Refactor VectorBuilder to avoid layering violation. NFC (#99276)

This patch refactors the handling of reduction to eliminate layering
violations.

* Introduced `getReductionIntrinsicID` in LoopUtils.h for mapping
recurrence kinds to llvm.vector.reduce.* intrinsic IDs.
* Updated `VectorBuilder::createSimpleTargetReduction` to accept
llvm.vector.reduce.* intrinsic directly.
* New function `VPIntrinsic::getForIntrinsic` for mapping intrinsic ID
to the same functional VP intrinsic ID.

show more ...

[TTI][WebAssembly] Pairwise reduction expansion (#93948)

WebAssembly doesn't support horizontal operations nor does it have a way
of expressing fast-math or reassoc flags, so runtimes are currently

[TTI][WebAssembly] Pairwise reduction expansion (#93948)

WebAssembly doesn't support horizontal operations nor does it have a way
of expressing fast-math or reassoc flags, so runtimes are currently
unable to use pairwise operations when generating code from the existing
shuffle patterns.

This patch allows the backend to select which, arbitary, shuffle pattern
to be used per reduction intrinsic. The default behaviour is the same as
the existing, which is by splitting the vector into a top and bottom
half. The other pattern introduced is for a pairwise shuffle.

WebAssembly enables pairwise reductions for int/fp add/sub.

show more ...

[LV][EVL] Support in-loop reduction using tail folding with EVL. (#90184)

Following from #87816, add VPReductionEVLRecipe to describe vector
predication reduction.

Address one of TODOs from #761

[LV][EVL] Support in-loop reduction using tail folding with EVL. (#90184)

Following from #87816, add VPReductionEVLRecipe to describe vector
predication reduction.

Address one of TODOs from #76172.

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

[LV] Apply loop guards when checking recur during hoisting RT checks.

Apply loop guards when checking if the recurrence is non-negative in
cases where runtime checks are hoisted out of an inner loop.

[LoopUtils] Simplify code for runtime check generation a bit (NFCI).

Store getSE result in variable to re-use and use structured bindings
when looping over bounds.

Revert "[indvars] Missing variables at Og (#88270)" (#93016)

This reverts commit 89e1f7784be40bea96d5e65919ce8d34151c1d69.

https://github.com/llvm/llvm-project/pull/88270#discussion_r1609559724

Revert "[indvars] Missing variables at Og (#88270)" (#93016)

This reverts commit 89e1f7784be40bea96d5e65919ce8d34151c1d69.

https://github.com/llvm/llvm-project/pull/88270#discussion_r1609559724
https://github.com/llvm/llvm-project/pull/88270#discussion_r1609552972

Main concerns from @nikic are the interaction between the
'IndVars' and 'LoopDeletion' passes, increasing build times
and adding extra complexity.

show more ...

[indvars] Missing variables at Og (#88270)

https://bugs.llvm.org/show_bug.cgi?id=51735
https://github.com/llvm/llvm-project/issues/51077

In the given test case:
```
4 ...
5 void bar() {
6

[indvars] Missing variables at Og (#88270)

https://bugs.llvm.org/show_bug.cgi?id=51735
https://github.com/llvm/llvm-project/issues/51077

In the given test case:
```
4 ...
5 void bar() {
6 int End = 777;
7 int Index = 27;
8 char Var = 1;
9 for (; Index < End; ++Index)
10 ;
11 nop(Index);
12 }
13 ...
```
Missing local variable `Index` after loop `Induction Variable Elimination`.
When adding a breakpoint at line `11`, LLDB does not have information
on the variable. But it has info on `Var` and `End`.

show more ...

[Transforms] Use StringRef::operator== instead of StringRef::equals (NFC) (#91072)

I'm planning to remove StringRef::equals in favor of
StringRef::operator==.

- StringRef::operator==/!= outnumbe

[Transforms] Use StringRef::operator== instead of StringRef::equals (NFC) (#91072)

I'm planning to remove StringRef::equals in favor of
StringRef::operator==.

- StringRef::operator==/!= outnumber StringRef::equals by a factor of
31 under llvm/ in terms of their usage.

- The elimination of StringRef::equals brings StringRef closer to
std::string_view, which has operator== but not equals.

- S == "foo" is more readable than S.equals("foo"), especially for
!Long.Expression.equals("str") vs Long.Expression != "str".

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

[LoopUnswitch] Allow i1 truncs in loop unswitch (#89738)

With the addition of #84628, truncs to i1 are being emitted as
conditions to branch instructions. This caused significant regressions
in ca

[LoopUnswitch] Allow i1 truncs in loop unswitch (#89738)

With the addition of #84628, truncs to i1 are being emitted as
conditions to branch instructions. This caused significant regressions
in cases which were previously improved by loop unswitch. Adding truncs
to i1 restore the previous performance seen.

show more ...

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

This reverts commit c6e38b928c56f562aea68a8e90f02dbdf0eada85.

Causes miscompiles, see comments on #78304.

Revert "[indvars] Missing variables at Og: (#69920)"

This reverts commit 739fa1c84b92b8af7dceedf2e5ad808a64e85a57.

This introduces a layering violation by using IR in Support headers.

[indvars] Missing variables at Og: (#69920)

https://bugs.llvm.org/show_bug.cgi?id=51735
https://github.com/llvm/llvm-project/issues/51077

In the given test case:
```
4 ...
5 void bar() {

[indvars] Missing variables at Og: (#69920)

https://bugs.llvm.org/show_bug.cgi?id=51735
https://github.com/llvm/llvm-project/issues/51077

In the given test case:
```
4 ...
5 void bar() {
6 int End = 777;
7 int Index = 27;
8 char Var = 1;
9 for (; Index < End; ++Index)
10 ;
11 nop(Index);
12 }
13 ...
```
Missing local variable `Index` after loop `Induction Variable Elimination`. When adding a breakpoint at line `11`, LLDB does not have information on the variable. But it has info on `Var` and `End`.

show more ...

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

This reverts the revert commit 589c7abb03448.

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

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

This reverts the revert commit 589c7abb03448.

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

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

[RemoveDIs][NFC] Rename DPValue -> DbgVariableRecord (#85216)

This is the major rename patch that prior patches have built towards.
The DPValue class is being renamed to DbgVariableRecord, which re

[RemoveDIs][NFC] Rename DPValue -> DbgVariableRecord (#85216)

This is the major rename patch that prior patches have built towards.
The DPValue class is being renamed to DbgVariableRecord, which reflects
the updated terminology for the "final" implementation of the RemoveDI
feature. This is a pure string substitution + clang-format patch. The
only manual component of this patch was determining where to perform
these string substitutions: `DPValue` and `DPV` are almost exclusively
used for DbgRecords, *except* for:

- llvm/lib/target, where 'DP' is used to mean double-precision, and so
appears as part of .td files and in variable names. NB: There is a
single existing use of `DPValue` here that refers to debug info, which
I've manually updated.
- llvm/tools/gold, where 'LDPV' is used as a prefix for symbol
visibility enums.

Outside of these places, I've applied several basic string
substitutions, with the intent that they only affect DbgRecord-related
identifiers; I've checked them as I went through to verify this, with
reasonable confidence that there are no unintended changes that slipped
through the cracks. The substitutions applied are all case-sensitive,
and are applied in the order shown:

```
DPValue -> DbgVariableRecord
DPVal -> DbgVarRec
DPV -> DVR
```

Following the previous rename patches, it should be the case that there
are no instances of any of these strings that are meant to refer to the
general case of DbgRecords, or anything other than the DPValue class.
The idea behind this patch is therefore that pure string substitution is
correct in all cases as long as these assumptions hold.

show more ...

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

Broke sanitizer bots: https://lab.llvm.org/buildbot/#/builders/74/builds/26697

This reverts commit 95fef1dfefd5467206e74c089d29806fcd82889b.