[AArch64] Fold `rbit` into "movemask" table
- 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
Assessment
This issue has not been assessed yet.