llvm / llvm/llvm-project

[AArch64] Fold `rbit` into "movemask" table

Open
#192,575 7 comments 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/vqThKbf5s
https://alive2.llvm.org/ce/z/CfV96U

When doing string searching with NEON, it is often useful to convert a vector of bools to a bitstring with a 1 where each vector element was 0xff and 0 otherwise. The positions of each match can then be found with `cttz`, eg

```llvm
define i8 @src8(<8 x i8> %bools) {
%bits = trunc nsw <8 x i8> %bools to <8 x i1>
%mask = bitcast <8 x i1> %bits to i8
%pos = call i8 @llvm.cttz(i8 %mask, i1 0)
ret i8 %pos
}
```

However, AArch64 (without `FEAT_CSSC`) doesn't have a ctz instruction, so currently LLVM emits an `rbit, clz` sequence:
```asm
.LCPI0_0:
.byte 1 // 0x1
.byte 2 // 0x2
.byte 4 // 0x4
.byte 8 // 0x8
.byte 16 // 0x10
.byte 32 // 0x20
.byte 64 // 0x40
.byte 128 // 0x80
src8: // @src8
shl v0.8b, v0.8b, #7
adrp x8, .LCPI0_0
ldr d1, [x8, :lo12:.LCPI0_0]
cmlt v0.8b, v0.8b, #0
and v0.8b, v0.8b, v1.8b
addv b0, v0.8b
fmov w8, s0
orr w8, w8, #0x100
rbit w8, w8
clz w0, w8
ret
```

If the order of the table `LCPI0_0` is reversed, the bitmask produced will already be reversed, and so there will be no need to reverse it in the scalar register:
```llvm
define i8 @tgt8(<8 x i8> %bools) {
%isolated_bits = and <8 x i8> %bools,
%mask = call i8 @llvm.vector.reduce.add(<8 x i8> %isolated_bits)
%pos = call i8 @llvm.ctlz(i8 %mask, i1 0)
ret i8 %pos
}
```

```asm
.LCPI1_0:
.byte 128 // 0x80
.byte 64 // 0x40
.byte 32 // 0x20
.byte 16 // 0x10
.byte 8 // 0x8
.byte 4 // 0x4
.byte 2 // 0x2
.byte 1 // 0x1
tgt8: // @tgt8
adrp x8, .LCPI1_0
ldr d1, [x8, :lo12:.LCPI1_0]
and v0.8b, v0.8b, v1.8b
addv b0, v0.8b
fmov w8, s0
clz w8, w8
sub w0, w8, #24
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.