Autovectorisation of predicated counting loop produces suboptimal assembly
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
https://godbolt.org/z/TbjcdjWd3
Clang is able to autovectorise this loop, but its produces way too much assembly, with lots of unnecessary shifts
```c++
auto count_newlines_src(const uint8_t* bytes, uint64_t len) {
uint64_t count = 0;
for (uint64_t i = 0; i < len; i++) count += (bytes[i] == '\n');
return count;
}
```
```asm
count_newlines_src(unsigned char const*, unsigned long):
cbz x1, .LBB0_3
str d10, [sp, #-32]!
stp d9, d8, [sp, #16]
cmp x1, #8
b.hs .LBB0_4
mov x9, xzr
mov x8, xzr
b .LBB0_13
.LBB0_3:
mov x0, xzr
ret
.LBB0_4:
cmp x1, #32
b.hs .LBB0_6
mov x9, xzr
mov x8, xzr
b .LBB0_10
.LBB0_6:
movi v0.2d, #0000000000000000
movi v3.16b, #10
mov w8, #1
movi v2.2d, #0000000000000000
movi v7.2d, #0000000000000000
and x10, x1, #0x18
movi v1.2d, #0000000000000000
movi v18.2d, #0000000000000000
and x9, x1, #0xffffffffffffffe0
movi v5.2d, #0000000000000000
movi v6.2d, #0000000000000000
and x11, x1, #0xffffffffffffffe0
movi v4.2d, #0000000000000000
movi v22.2d, #0000000000000000
movi v17.2d, #0000000000000000
movi v16.2d, #0000000000000000
movi v23.2d, #0000000000000000
movi v20.2d, #0000000000000000
movi v21.2d, #0000000000000000
movi v19.2d, #0000000000000000
movi v24.2d, #0000000000000000
dup v25.2d, x8
add x8, x0, #16
.LBB0_7:
ldp q26, q27, [x8, #-16]
subs x11, x11, #32
add x8, x8, #32
cmeq v26.16b, v26.16b, v3.16b
cmeq v27.16b, v27.16b, v3.16b
ushll2 v28.8h, v26.16b, #0
ushll v26.8h, v26.8b, #0
ushll2 v9.8h, v27.16b, #0
ushll v27.8h, v27.8b, #0
ushll2 v29.4s, v28.8h, #0
ushll v28.4s, v28.4h, #0
ushll2 v31.4s, v26.8h, #0
ushll v26.4s, v26.4h, #0
ushll2 v30.2d, v29.4s, #0
ushll v29.2d, v29.2s, #0
ushll2 v8.2d, v28.4s, #0
ushll v28.2d, v28.2s, #0
ushll2 v10.2d, v31.4s, #0
ushll v31.2d, v31.2s, #0
and v29.16b, v29.16b, v25.16b
and v30.16b, v30.16b, v25.16b
and v8.16b, v8.16b, v25.16b
and v28.16b, v28.16b, v25.16b
and v10.16b, v10.16b, v25.16b
and v31.16b, v31.16b, v25.16b
add v4.2d, v4.2d, v29.2d
ushll2 v29.2d, v26.4s, #0
add v22.2d, v22.2d, v30.2d
ushll v30.4s, v9.4h, #0
add v6.2d, v6.2d, v8.2d
ushll v8.4s, v27.4h, #0
ushll2 v9.4s, v9.8h, #0
ushll2 v27.4s, v27.8h, #0
ushll v26.2d, v26.2s, #0
and v29.16b, v29.16b, v25.16b
add v18.2d, v18.2d, v10.2d
add v5.2d, v5.2d, v28.2d
ushll v10.2d, v30.2s, #0
add v1.2d, v1.2d, v31.2d
ushll2 v30.2d, v30.4s, #0
ushll v28.2d, v9.2s, #0
ushll2 v9.2d, v9.4s, #0
ushll2 v31.2d, v27.4s, #0
add v7.2d, v7.2d, v29.2d
ushll v29.2d, v8.2s, #0
ushll2 v8.2d, v8.4s, #0
ushll v27.2d, v27.2s, #0
and v26.16b, v26.16b, v25.16b
and v10.16b, v10.16b, v25.16b
and v28.16b, v28.16b, v25.16b
and v9.16b, v9.16b, v25.16b
and v31.16b, v31.16b, v25.16b
and v30.16b, v30.16b, v25.16b
and v29.16b, v29.16b, v25.16b
and v8.16b, v8.16b, v25.16b
and v27.16b, v27.16b, v25.16b
add v2.2d, v2.2d, v26.2d
add v20.2d, v20.2d, v10.2d
add v24.2d, v24.2d, v9.2d
add v19.2d, v19.2d, v28.2d
add v23.2d, v23.2d, v31.2d
add v21.2d, v21.2d, v30.2d
add v0.2d, v0.2d, v8.2d
add v17.2d, v17.2d, v29.2d
add v16.2d, v16.2d, v27.2d
b.ne .LBB0_7
add v3.2d, v23.2d, v18.2d
add v18.2d, v24.2d, v22.2d
cmp x1, x9
add v0.2d, v0.2d, v7.2d
add v2.2d, v17.2d, v2.2d
add v5.2d, v20.2d, v5.2d
add v6.2d, v21.2d, v6.2d
add v1.2d, v16.2d, v1.2d
add v4.2d, v19.2d, v4.2d
add v3.2d, v3.2d, v18.2d
add v2.2d, v2.2d, v5.2d
add v1.2d, v1.2d, v4.2d
add v0.2d, v0.2d, v6.2d
add v1.2d, v2.2d, v1.2d
add v0.2d, v0.2d, v3.2d
add v0.2d, v1.2d, v0.2d
addp d0, v0.2d
fmov x8, d0
b.eq .LBB0_15
cbz x10, .LBB0_13
.LBB0_10:
movi v0.2d, #0000000000000000
movi v1.8b, #10
mov w10, #1
movi v2.2d, #0000000000000000
movi v3.2d, #0000000000000000
fmov d4, x8
dup v5.2d, x10
mov x10, x9
and x9, x1, #0xfffffffffffffff8
sub x8, x10, x9
add x10, x0, x10
.LBB0_11:
ldr d6, [x10], #8
adds x8, x8, #8
cmeq v6.8b, v6.8b, v1.8b
ushll v6.8h, v6.8b, #0
ushll2 v7.4s, v6.8h, #0
ushll v6.4s, v6.4h, #0
ushll2 v16.2d, v7.4s, #0
ushll v17.2d, v6.2s, #0
ushll2 v6.2d, v6.4s, #0
ushll v7.2d, v7.2s, #0
and v16.16b, v16.16b, v5.16b
and v17.16b, v17.16b, v5.16b
and v6.16b, v6.16b, v5.16b
and v7.16b, v7.16b, v5.16b
add v3.2d, v3.2d, v16.2d
add v2.2d, v2.2d, v6.2d
add v4.2d, v4.2d, v17.2d
add v0.2d, v0.2d, v7.2d
b.ne .LBB0_11
add v0.2d, v4.2d, v0.2d
add v1.2d, v2.2d, v3.2d
cmp x1, x9
add v0.2d, v0.2d, v1.2d
addp d0, v0.2d
fmov x8, d0
b.eq .LBB0_15
.LBB0_13:
sub x10, x1, x9
add x9, x0, x9
.LBB0_14:
ldrb w11, [x9], #1
cmp w11, #10
cinc x8, x8, eq
subs x10, x10, #1
b.ne .LBB0_14
.LBB0_15:
ldp d9, d8, [sp, #16]
ldr d10, [sp], #32
mov x0, x8
ret
```
The ideal loop would look something like:
```asm
count_newlines_tgt(unsigned char const*, unsigned long):
;; x0: ptr
;; x1: len
;; x2: len rounded down
;; x3: end ptr
;; x4: end ptr rounded down
;; x5: sum
;; x6: loop ptr
cbz x1, .Lend
mov x5, 0
add x3, x0, x1
ands x2, x1, -16
b.eq .Lscalar_loop
add x4, x0, x2
movi v31.16b, 0
movi v30.16b, 10
mov x6, x0
.Lvector_loop:
ldr q0, [x6], 16
cmeq v0.16b, v30.16b, v0.16b
addv b0, v0.16b
sub d31, d31, d0
cmp x6, x4
b.lt .Lvector_loop
fmov x5, d31
.Lscalar_loop:
ldrb w10, [x6], 1
cmp w10, 10
cinc x5, x5, eq
cmp x6, x3
b.lt .Lscalar_loop
mov x0, x5
.Lend
ret
```
I tried to vectorise the loop myself with NEON intrinsics, but LLVM rewrote it to be the same as `src`:
```c++
auto count_newlines_tgt(const uint8_t* bytes, uint64_t len) -> uint64_t {
uint64x1_t count_vec = {0};
uint64_t i = 0;
uint64_t len_rounded_down = len / 16 * 16;
for (i = 0; i < len_rounded_down; i += 16) {
uint8x16_t vec = vld1q_u8(bytes + i);
uint8x16_t mask = (vec == '\n');
uint8_t sum = vaddvq_u8(mask);
count_vec -= (uint64x1_t){sum};
}
uint64_t count = count_vec[0];
for (; i < len; i++) count += (bytes[i] == '\n');
return count;
}
```
Contributor guide
Assessment
This issue has not been assessed yet.