Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Failure to recognize andn-like pattern #45100

Closed
GabrielRavier opened this issue Apr 30, 2020 · 9 comments
Closed

Failure to recognize andn-like pattern #45100

GabrielRavier opened this issue Apr 30, 2020 · 9 comments
Assignees
Labels
bugzilla Issues migrated from bugzilla llvm:codegen

Comments

@GabrielRavier
Copy link
Contributor

Bugzilla Link 45755
Resolution FIXED
Resolved on Apr 02, 2021 11:59
Version trunk
OS Linux
CC @LebedevRI,@RKSimon,@rotateright
Fixed by commit(s) 412fc74

Extended Description

int f(int x)
{
return ~(x | -x);
}

With -O3, GCC outputs this :

f(int):
lea eax, [rdi-1]
andn eax, edi, eax
ret

LLVM outputs this :

f(int): # @​f(int)
mov eax, edi
neg eax
or eax, edi
not eax
ret

@GabrielRavier
Copy link
Contributor Author

assigned to @rotateright

@RKSimon
Copy link
Collaborator

RKSimon commented Apr 30, 2020

Current Codegen: https://gcc.godbolt.org/z/JUaYXZ

gcc doesn't manage this for vectors

@rotateright
Copy link
Contributor

If we view this as a missed IR canonicalization:
http://volta.cs.utah.edu:8080/z/W3DavX

define i8 @​src(i8 %x) {
%s = sub i8 0, %x
%o = or i8 %s, %x
%not = xor i8 %o, -1
ret i8 %not
}

define i8 @​tgt(i8 %x) {
%dec = add i8 %x, -1
%not = xor i8 %x, -1
%a = and i8 %not, %dec
ret i8 %a
}

@RKSimon
Copy link
Collaborator

RKSimon commented Jun 11, 2020

Alive2 seems to be down at the moment, but this doesn't appear to need to be a unary transform:

int g(int x, int y)
{
return ~(x | -y);
}

works as well:

(gcc):

g:
leal -1(%rsi), %eax
andn %eax, %edi, %eax
ret

vs (clang):

g:
movl %esi, %eax
negl %eax
orl %edi, %eax
notl %eax
retq

https://gcc.godbolt.org/z/_F2dbz

@RKSimon
Copy link
Collaborator

RKSimon commented Apr 2, 2021

int g(int x, int y)
{
return ~(x | -y);
}

-->

int g2(int x, int y)
{
return ~x & (y - 1);
}

So the general case seem to be legit: https://alive2.llvm.org/ce/z/cxZDSp

It comes down to whether we want to do this in InstCombine or wait to SelectionDAG where we know if there's a ANDN instruction or not.

@rotateright
Copy link
Contributor

It comes down to whether we want to do this in InstCombine or wait to
SelectionDAG where we know if there's a ANDN instruction or not.

InstCombine should do. We prefer 'add' over 'sub' for analysis.

Codegen looks equal or better for the 'add' variant on the targets that I checked.

x86:
movl %esi, %eax
negl %eax
orl %edi, %eax
notl %eax
->
notl %edi
leal -1(%rsi), %eax
andl %edi, %eax

(with andn):
decl %esi
andnl %esi, %edi, %eax

AArch64:
neg w8, w1
orr w8, w8, w0
mvn w0, w8
->
sub w8, w1, #​1
bic w0, w8, w0

ARM-v7a:
rsb r1, r1, #​0
orr r0, r1, r0
mvn r0, r0
->
sub r1, r1, #​1
bic r0, r1, r0

PowerPC:
neg 4, 4
nor 3, 4, 3
extsw 3, 3
->
addi 4, 4, -1
andc 3, 4, 3
extsw 3, 3

@rotateright
Copy link
Contributor

I'll look at the instcombine patch. Most of the work will be in writing tests to cover variations.

@rotateright
Copy link
Contributor

@RKSimon
Copy link
Collaborator

RKSimon commented Apr 2, 2021

https://reviews.llvm.org/rG412fc74140c0

Thanks Sanjay

@llvmbot llvmbot transferred this issue from llvm/llvm-bugzilla-archive Dec 10, 2021
This issue was closed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bugzilla Issues migrated from bugzilla llvm:codegen
Projects
None yet
Development

No branches or pull requests

3 participants