llvm / llvm/llvm-project

Missed Fold: `bitTest(a | ~b, N)` => `!bitTest(~a & b, N)` on targets with `andn`

Open
#186,016 0 comments 0 reactions 0 assignees View on GitHub
llvm:optimizations missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

The expression `a | ~b` is equivalent to `~(~a & b)`. When performing a bit test, the latter form is preferable on targets with `andn` (and that lack `orn`) as the finale NOT can be eliminated by implicitly inverting the result of the test:

```asm
selectIfBit:
mvn r1, r1
orr r0, r0, r1
tst r0, #8
moveq r2, r3
mov r0, r2
bx lr
```

```asm
selectIfBit_tgt:
bic r0, r1, r0
tst r0, #8
movne r2, r3
mov r0, r2
bx lr
```

https://godbolt.org/z/aYo1e6Krv

On x86 targets with BMI1, it is lowered to the latter form but the NOT isn't eliminated despite generally doing so when testing an inversion:

```asm
selectIfBit_src:
mov eax, edx
andn edx, edi, esi
not edx
test dl, 8
cmove eax, ecx
ret
```

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.