llvm / llvm/llvm-project

Popcount loop doesn't get folded on some targets

Open
#171,969 4 comments 0 reactions 0 assignees View on GitHub
backend:MIPS backend:Sparc missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

Using the example adapted from [here](https://xania.org/202512/11-pop-goes-the-weasel-er-count), it seems that the loop fails to optimize on some targets, even when I tell clang that the target has a hardware instruction for it:

```c
// SPARC64: clang -O2 -mpopc
// MIPS64: clang -O2 -march=octeon
// X86-64: clang -O2 -mpopcnt
unsigned population_count_loop(long long value) {
unsigned result = 0;
while (value) {
value &= value - 1;
++result;
}
return result;
}
```

At least sparc64 and mips64 is affected (but I haven't checked the other targets, more could be affected):
```
! SPARC64
population_count_loop:
brz %o0, .LBB1_2
mov %g0, %o1
.LBB1_1:
add %o0, -1, %o2
and %o2, %o0, %o0
brnz %o0, .LBB1_1
add %o1, 1, %o1
.LBB1_2:
retl
srl %o1, 0, %o0
```
```
! MIPS64
population_count_loop:
.Lfunc_begin1 = .Ltmp3
daddiu $sp, $sp, -16
sd $ra, 8($sp)
sd $fp, 0($sp)
move $fp, $sp
beqz $4, .LBB1_2
addiu $2, $zero, 0
.LBB1_1:
daddiu $1, $4, -1
and $4, $1, $4
bnez $4, .LBB1_1
addiu $2, $2, 1
.LBB1_2:
sll $2, $2, 0
move $sp, $fp
ld $fp, 0($sp)
ld $ra, 8($sp)
jr $ra
daddiu $sp, $sp, 16
```

On the other hand, the builtin is compiled down to the hardware instruction as expected:
```c
unsigned population_count_builtin(long long value) {
return __builtin_popcountll(value);
}
```
```
! SPARC64
population_count_builtin:
retl
popc %o0, %o0
```
```
! MIPS64
population_count_builtin:
.Lfunc_begin0 = .Ltmp0
daddiu $sp, $sp, -16
sd $ra, 8($sp)
sd $fp, 0($sp)
move $fp, $sp
dpop $2, $4
move $sp, $fp
ld $fp, 0($sp)
ld $ra, 8($sp)
jr $ra
daddiu $sp, $sp, 16
```

For reference when targeting x86-64 both functions compile down to the popcount instruction:
```
! X86-64
population_count_builtin:
popcnt rax, rdi
ret

population_count_loop:
popcnt rax, rdi
ret
```

Generally I'd expect that such optimizations are performed in a target-independent manner.
[Godbolt link](https://godbolt.org/z/d66zdzoMz).

Contributor guide

Open the contributing guide

Research direction

Start with the C reproducer and the Godbolt link, comparing clang -O2 output for the loop and __builtin_popcountll on SPARC64 and MIPS64. Read the target-independent optimization path and target handling for popcount recognition, then verify that the loop folds to the hardware instruction on the affected targets without regressing the shown x86-64 behavior.

Written by the indexing model from the issue text.

Assessment

Tech stack
c
Domain
compilers, performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.