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

[LV][NFC] Auto-generate the test cases related to FindLastIV idioms. (#117560)

Pre-commit for #67812

[LV][NFC] Move and add truncated-related FindLastIV reduction test cases. (#67674)

[LV][NFC] Remove unnecessary parameter attributes from the test cases. (#67630)

The vectorization of the FindLastIV reduction does not depend on the
nocapture and readonly attributes.

LoopVectorize/iv-select-cmp: comment out-of-bound tests (NFC)

To help future contributors understand a couple of mysterious
out-of-bound tests, add a brief comment to each.

LoopVectorize/iv-select-cmp: add test for decreasing IV out-of-bound

The most straightforward extension to D150851 would involve handling the
decreasing IV case, for which tests have been added in 1

LoopVectorize/iv-select-cmp: add test for decreasing IV out-of-bound

The most straightforward extension to D150851 would involve handling the
decreasing IV case, for which tests have been added in 110ec1863a
(LoopVectorize/iv-select-cmp: add test for decreasing IV, const start).
However, the commit missed a testcase for the out-of-bound sentinel
value LONG_MAX, which should not be vectorized. Fix this by adding a
test corresponding to the following program:

long test(long *a) {
long rdx = 331;
for (long i = LONG_MAX; i >= 0; i--) {
if (a[i] > 3)
rdx = i;
}
return rdx;
}

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

show more ...

LoopVectorize/iv-select-cmp: add tests for truncated IV

The current tests in iv-select-cmp.ll are not representative of clang
output of common real-world C programs, which are often written with i32

LoopVectorize/iv-select-cmp: add tests for truncated IV

The current tests in iv-select-cmp.ll are not representative of clang
output of common real-world C programs, which are often written with i32
induction vars, as opposed to i64 induction vars. Hence, add five tests
corresponding to the following programs:

int test(int *a, int n) {
int rdx = 331;
for (int i = 0; i < n; i++) {
if (a[i] > 3)
rdx = i;
}
return rdx;
}

int test(int *a) {
int rdx = 331;
for (int i = 0; i < 20000; i++) {
if (a[i] > 3)
rdx = i;
}
return rdx;
}

int test(int *a, long n) {
int rdx = 331;
for (int i = 0; i < n; i++) {
if (a[i] > 3)
rdx = i;
}
return rdx;
}

int test(int *a, unsigned n) {
int rdx = 331;
for (int i = 0; i < n; i++) {
if (a[i] > 3)
rdx = i;
}
return rdx;
}

int test(int *a) {
int rdx = 331;
for (long i = INT_MIN - 1; i < UINT_MAX; i++) {
if (a[i] > 3)
rdx = i;
}
return rdx;
}

The first two can theoretically be vectorized without a runtime-check,
while the third and fourth cannot. The fifth cannot be vectorized, even
with a runtime-check.

This issue was found while reviewing D150851.

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

show more ...

LoopVectorize/iv-select-cmp: add test for decreasing IV, const start

The most straightforward extension to D150851 would involve a loop with
decreasing induction variable, with a constant start valu

LoopVectorize/iv-select-cmp: add test for decreasing IV, const start

The most straightforward extension to D150851 would involve a loop with
decreasing induction variable, with a constant start value.
iv-select-cmp.ll only contains a negative test for the decreasing
induction variable case when the start value is variable, namely
not_vectorized_select_decreasing_induction_icmp. Hence, add a test for
the most straightforward extension to D150851, in preparation to
vectorize:

long rdx = 331;
for (long i = 19999; i >= 0; i--) {
if (a[i] > 3)
rdx = i;
}
return rdx;

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

show more ...

[LV] Add tests for select-cmp reduction pattern. (NFC)

The test cases for selecting increasing integer induction variable.

Reviewed By: fhahn, shiva0217

Differential Revision: https://reviews.llvm

[LV] Add tests for select-cmp reduction pattern. (NFC)

The test cases for selecting increasing integer induction variable.

Reviewed By: fhahn, shiva0217

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

show more ...