llvm / llvm/llvm-project

[AArch64] Hoist generated `rbit` when `ctz` appears in a loop

Open
#192,577 1 comment 0 reactions 0 assignees View on GitHub
backend:AArch64 missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

https://godbolt.org/z/qazc657v7
https://alive2.llvm.org/ce/z/JJcySG

Follow up to #192575.
When iterating over the positions of each 1 bit in a bitstring with `ctz`, LLVM generates an `rbit,clz` sequence in the body of the loop. The `rbit` can be hoisted outside of the loop, after taking care to adjust the code that updates the bitstring:

```c++
#include
#include

extern "C" {

auto src1(uint64_t bitstring) {
uint64_t ret = 0;

while (bitstring != 0) {
uint8_t pos = __builtin_ctzg(bitstring);
ret += pos;
bitstring >>= pos;
bitstring >>= 1;
}

return ret;
}

auto tgt1(uint64_t bitstring) {
uint64_t ret = 0;

bitstring = __rbitll(bitstring);
while (bitstring != 0) {
uint8_t pos = __builtin_clzg(bitstring);
ret += pos;
bitstring <<= pos;
bitstring <<= 1;
}

return ret;
}

auto src2(uint64_t bitstring) {
uint64_t ret = 0;

while (bitstring != 0) {
uint8_t pos = __builtin_ctzg(bitstring);
ret += pos;
bitstring &= (bitstring - 1);
}

return ret;
}

auto tgt2(uint64_t bitstring) {
uint64_t ret = 0;

bitstring = __rbitll(bitstring);
while (bitstring != 0) {
uint8_t pos = __builtin_clzg(bitstring);
ret += pos;
bitstring &= ~(1ULL << pos);
}

return ret;
}
}
```

```asm
src1:
mov x8, xzr
cbz x0, .LBB0_2
.LBB0_1:
rbit x9, x0
clz x9, x9
lsr x10, x0, x9
add x8, x9, x8
lsr x0, x10, #1
cbnz x0, .LBB0_1
.LBB0_2:
mov x0, x8
ret

tgt1:
cbz x0, .LBB1_3
rbit x8, x0
mov x0, xzr
.LBB1_2:
clz x9, x8
lsl x8, x8, x9
add x0, x9, x0
lsl x8, x8, #1
cbnz x8, .LBB1_2
.LBB1_3:
ret

src2:
mov x8, xzr
cbz x0, .LBB2_2
.LBB2_1:
rbit x9, x0
sub x10, x0, #1
ands x0, x10, x0
clz x9, x9
add x8, x9, x8
b.ne .LBB2_1
.LBB2_2:
mov x0, x8
ret

tgt2:
cbz x0, .LBB3_3
mov x8, x0
mov x0, xzr
mov w9, #1
rbit x8, x8
.LBB3_2:
clz x10, x8
lsl x11, x9, x10
add x0, x10, x0
bics x8, x8, x11
b.ne .LBB3_2
.LBB3_3:
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.