[CostModel][X86] Add missing costkinds for scalar CTLZ/CTTZ instructions

Baed off worst case llvm-mca numbers for CTLZ/CTTZ(+ZERO_UNDEF) codegen

Prep work for #102885

[ValueTracking] Remove SPF support from `computeKnownBitsFromOperator` (#76630)

This patch removes redundant SPF support
(https://github.com/llvm/llvm-project/commit/5350e1b5096aa4707aa525baf7398d9

[ValueTracking] Remove SPF support from `computeKnownBitsFromOperator` (#76630)

This patch removes redundant SPF support
(https://github.com/llvm/llvm-project/commit/5350e1b5096aa4707aa525baf7398d93b4a4f1a5)
from `computeKnownBitsFromOperator` as we always canonicalize a SPF into
an intrinsic call.

Compile-time improvement:
http://llvm-compile-time-tracker.com/compare.php?from=3dc0638cfc19e140daff7bf1281648daca8212fa&to=8771ef0749fb2ba4304dc68d418c88ec5769346f&stat=instructions:u

|stage1-O3|stage1-ReleaseThinLTO|stage1-ReleaseLTO-g|stage1-O0-g|stage2-O3|stage2-O0-g|stage2-clang|
|--|--|--|--|--|--|--|
-0.01%|-0.01%|+0.01%|+0.00%|+0.01%|+0.04%|-0.01%|

show more ...

[LoopIdiom] Convert tests to opaque pointers (NFC)

The differences here are due to SCEVExpander producing GEPs with
explicit offset calculation, a known difference with opaque pointers.

[NFC] Port all LoopIdiom tests to `-passes=` syntax

[CostModel][X86] Add CostKinds handling for CTLZ_ZERO_UNDEF/CTTZ_ZERO_UNDEF instructions

This was achieved with the 'cost-tables vs llvm-mca' script D103695

[LoopIdiomRecognize] Teach detectShiftUntilZeroIdiom to recognize loops where the counter is decrementing.

This adds support for loops like

unsigned clz(unsigned x) {
unsigned w = sizeof (x) *

[LoopIdiomRecognize] Teach detectShiftUntilZeroIdiom to recognize loops where the counter is decrementing.

This adds support for loops like

unsigned clz(unsigned x) {
unsigned w = sizeof (x) * CHAR_BIT;
while (x) {
w--;
x >>= 1;
}

return w;
}

and

unsigned clz(unsigned x) {
unsigned w = sizeof (x) * CHAR_BIT - 1;
while (x >>= 1) {
w--;
}

return w;
}

To support these we look for add x, -1 as well as add x, 1 that
we already matched. If the value was -1 we need to subtract from
the initial counter value instead of adding to it.

Fixes PR48404.

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

show more ...

[LoopIdiom] Pre-commit tests for D92745. NFC

[LoopIdiomRecognize] Autogenerate complete checks for the X86 ctlz/cttz tests. NFC

Preparation for D92745 which will add more tests to these files.

Revert "Temporarily Revert "Add basic loop fusion pass.""

The reversion apparently deleted the test/Transforms directory.

Will be re-reverting again.

llvm-svn: 358552

[LoopIdiomRecognize] Don't convert a do while loop to ctlz.

This commit suppresses turning loops like this into "(bitwidth - ctlz(input))".

unsigned foo(unsigned input) {
unsigned num = 0;
do {

[LoopIdiomRecognize] Don't convert a do while loop to ctlz.

This commit suppresses turning loops like this into "(bitwidth - ctlz(input))".

unsigned foo(unsigned input) {
unsigned num = 0;
do {
++num;
input >>= 1;
} while (input != 0);
return num;
}

The loop version returns a value of 1 for both an input of 0 and an input of 1. Converting to a naive ctlz does not preserve that.

Theoretically we could do better if we checked isKnownNonZero or we could insert a select to handle the divergence. But until we have motivating cases for that, this is the easiest solution.

llvm-svn: 336864

show more ...

[LoopIdiomRecognize] Add a test case showing a loop we turn into ctlz that we shouldn't.

This loop executes one iteration without checking the input value. This produces a count of 1 for an input of

[LoopIdiomRecognize] Add a test case showing a loop we turn into ctlz that we shouldn't.

This loop executes one iteration without checking the input value. This produces a count of 1 for an input of 0 and 1. We are turning this into 32 - ctlz(n), but that returns 0 if n is 0.

llvm-svn: 336862

show more ...

[LoopIdiomRecognize] Support for converting loops that use LSHR to CTLZ.

In the 'detectCTLZIdiom' function support for loops that use LSHR instruction instead of ASHR has been added.

This supports

[LoopIdiomRecognize] Support for converting loops that use LSHR to CTLZ.

In the 'detectCTLZIdiom' function support for loops that use LSHR instruction instead of ASHR has been added.

This supports creating ctlz from the following code.

int lzcnt(int x) {
int count = 0;
while (x > 0) {
count++;
x = x >> 1;
}
return count;
}

Patch by Olga Moldovanova

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

llvm-svn: 336509

show more ...

[ValueTracking] Match select abs pattern when there's an sext involved

When checking a select to see if it matches an abs, allow the true/false values
to be a sign-extension of the comparison value

[ValueTracking] Match select abs pattern when there's an sext involved

When checking a select to see if it matches an abs, allow the true/false values
to be a sign-extension of the comparison value instead of requiring that they're
directly the comparison value, as all the comparison cares about is the sign of
the value.

This fixes a regression due to r333702, where we were no longer generating ctlz
due to isKnownNonNegative failing to match such a pattern.

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

llvm-svn: 333927

show more ...

[LoopIdiomRecognize] Only convert loops to ctlz if we can prove that the input is non-negative.

Summary:
Loop idiom recognize tries to convert loops like

```
int foo(int x) {
int cnt = 0;
while

[LoopIdiomRecognize] Only convert loops to ctlz if we can prove that the input is non-negative.

Summary:
Loop idiom recognize tries to convert loops like

```
int foo(int x) {
int cnt = 0;
while (x) {
x >>= 1;
++cnt;
}
return cnt;
}
```

into calls to ctlz, but if x is initially negative this loop should be infinite.

It happens that the cases that motivated this change have an absolute value of x before the loop. So this patch restricts the transform to cases where we know x is positive. Note: We are relying on the absolute value of INT_MIN to be undefined so we can assume that the result is always positive.

Fixes PR37479

Reviewers: spatel, hfinkel, efriedma, javed.absar

Reviewed By: efriedma

Subscribers: dmgreen, llvm-commits

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

llvm-svn: 333702

show more ...

[LoopIdiomRecognize] Add a test case to show incorrect transformation of an infinite loop with side effets into a countable loop using ctlz.

We currently recognize this idiom where x is signed and t

[LoopIdiomRecognize] Add a test case to show incorrect transformation of an infinite loop with side effets into a countable loop using ctlz.

We currently recognize this idiom where x is signed and thus the shift in an ashr.

int cnt = 0;
while (x) {
x >>= 1; // arithmetic shift right
++cnt;
}

and turn it into (bitwidth - ctlz(x)). And if there is anything else in the loop we will create a new loop that runs that many times.

If x is initially negative, the shift result will never be 0 and thus the loop is infinite. If you put something with side effects in the loop, that side effect will now only happen bitwidth times instead of an infinite number of times.

So this transform is only safe for logical shift right (which we don't currently recognize) or if we can prove that x cannot be negative before the loop.

llvm-svn: 331493

show more ...

The patch adds CTLZ idiom recognition.

Summary:

The following loops should be recognized:
i = 0;
while (n) {
n = n >> 1;
i++;
body();
}
use(i);

And replaced with builtin_ctlz(n) if body() is

The patch adds CTLZ idiom recognition.

Summary:

The following loops should be recognized:
i = 0;
while (n) {
n = n >> 1;
i++;
body();
}
use(i);

And replaced with builtin_ctlz(n) if body() is empty or
for CPUs that have CTLZ instruction converted to countable:

for (j = 0; j < builtin_ctlz(n); j++) {
n = n >> 1;
i++;
body();
}
use(builtin_ctlz(n));

Reviewers: rengolin, joerg

Differential Revision: http://reviews.llvm.org/D32605

From: Evgeny Stupachenko <evstupac@gmail.com>
llvm-svn: 303102

show more ...