llvm / llvm/llvm-project

Missed-optimizations for u128 known to fit in a u32

Open
#187,838 3 comments 0 reactions 1 assignee Claimed by @Takashiidobe View on GitHub
backend:X86 llvm:instcombine missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

I've got the following Rust code:

```rust
pub fn base128_length(n: u128) -> usize {
// Equivalent to: let bits = if n != 0 { 128 - n.leading_zeros() } else { 1 };
let bits = u128::BITS - (n | 1).leading_zeros();
let bytes = bits.div_ceil(7);
bytes as usize
}

#[unsafe(no_mangle)]
pub fn base128_length_u32(n: u32) -> usize {
base128_length(n.into())
}
```

`base128_length_u32` compiles to the following LLVM IR:

```llvm
define noundef range(i64 0, 6) i64 @src(i32 noundef %n) unnamed_addr #0 {
start:
%0 = or i32 %n, 1
%self.i = zext i32 %0 to i128
%1 = tail call range(i128 0, 128) i128 @llvm.ctlz.i128(i128 %self.i, i1 true)
%2 = trunc nuw nsw i128 %1 to i8
%bits.i = sub nuw i8 -128, %2
%d1.i = udiv i8 %bits.i, 7
%d.zext.i = zext nneg i8 %d1.i to i64
%r2.i = urem i8 %bits.i, 7
%_8.not.i = icmp ne i8 %r2.i, 0
%3 = zext i1 %_8.not.i to i64
%bytes.sroa.0.0.i = add nuw nsw i64 %3, %d.zext.i
ret i64 %bytes.sroa.0.0.i
}
```

Which is compiled to the following x86-64:

```asm
src: # @src
orl $1, %edi
bsrq %rdi, %rax
xorl $63, %eax
orb $64, %al
movb $-128, %cl
subb %al, %cl
movzbl %cl, %eax
leal (%rax,%rax,8), %ecx
leal (%rax,%rcx,4), %ecx
imull $-73, %eax, %edx
shrl $8, %ecx
subb %cl, %al
shrb %al
addb %cl, %al
shrb $2, %al
movzbl %al, %eax
cmpb $37, %dl
sbbq $-1, %rax
retq
```

however, LLVM should be able to optimize this to the far simpler:

```llvm
define i64 @tgt(i32 %n) {
%or = or i32 %n, 1
%ctlz = call i32 @llvm.ctlz.i32(i32 %or, i1 true)
%bits_minus_1 = sub nuw i32 31, %ctlz
%plus7 = add nuw i32 %bits_minus_1, 7
%mul = mul nuw i32 %plus7, 37
%div = lshr i32 %mul, 8
%ext = zext i32 %div to i64
ret i64 %ext
}
```

```asm
tgt: # @tgt
orl $1, %edi
bsrl %edi, %eax
leal (%rax,%rax,8), %ecx
leal 259(%rax,%rcx,4), %eax
shrl $8, %eax
retq
```

Alive proof: https://alive2.llvm.org/ce/z/BLfABR

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.