llvm / llvm/llvm-project

Missing certain bitshift optimization for types below u16/i16

Open
#223,264 0 comments 0 reactions 0 assignees View on GitHub
llvm:instcombine missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

Following example with x86-64-v4

```rs
#[unsafe(no_mangle)]
pub fn swapbits(ch: u8, p1: u8, p2: u8) -> u8 {
let set1 = (ch >> p1) & 1;
let set2 = (ch >> p2) & 1;
let mut xor_val = set1 ^ set2;
xor_val = (xor_val << p1) | (xor_val << p2);
return ch ^ xor_val;
}
```

doesn't generate shrx (https://www.felixcloutier.com/x86/sarx:shlx:shrx) instruction and falls back to normal (shr and shl) instructions.
Generated LLVM IR is identical

(good one)

```llvm
define noundef i8 @swapbits(i32 noundef %ch, i32 noundef %p1, i32 noundef %p2) unnamed_addr #0 {
start:
%0 = and i32 %p1, 31
%_5 = lshr i32 %ch, %0
%1 = and i32 %p2, 31
%_7 = lshr i32 %ch, %1
%set13 = xor i32 %_7, %_5
%2 = and i32 %set13, 1
%_9 = shl nuw i32 %2, %0
%_11 = shl nuw i32 %2, %1
%3 = or i32 %_9, %_11
%_12 = xor i32 %3, %ch
%_0 = trunc i32 %_12 to i8
ret i8 %_0
}
attributes #0 = { mustprogress nofree norecurse nosync nounwind nonlazybind willreturn memory(none) uwtable "probe-stack"="inline-asm" "target-cpu"="x86-64-v4" }
```

(bad one)

```llvm
define noundef i8 @swapbits2(i8 noundef %ch, i8 noundef %p1, i8 noundef %p2) unnamed_addr #0 {
start:
%0 = and i8 %p1, 7
%_5 = lshr i8 %ch, %0
%1 = and i8 %p2, 7
%_7 = lshr i8 %ch, %1
%set13 = xor i8 %_7, %_5
%2 = and i8 %set13, 1
%_9 = shl nuw i8 %2, %0
%_11 = shl nuw i8 %2, %1
%3 = or i8 %_9, %_11
%_0 = xor i8 %3, %ch
ret i8 %_0
}
attributes #0 = { mustprogress nofree norecurse nosync nounwind nonlazybind willreturn memory(none) uwtable "probe-stack"="inline-asm" "target-cpu"="x86-64-v4" }
```

Godbolt link: https://godbolt.org/z/Gjajvc87r
GCC codegen also seems to generate almost same output.

Since C allows implicit type promotion, a C version with u8 generates the optimal version of it.
https://godbolt.org/z/Yvq7W6o1o
GCC however zero extends it to 32 bit registers.

Original post: https://old.reddit.com/r/rust/comments/1wbgzz7/unoptimised_bitshifts_below_u32/

Contributor guide

Open the contributing guide

Research direction

Reproduce the Rust example with the linked Godbolt case and compare the generated x86-64-v4 assembly with the provided LLVM IR for i8 and i32 values. Trace the LLVM compiler path responsible for lowering these variable shifts, then verify that the smaller integer types receive the expected optimized shift instructions without changing the result.

Written by the indexing model from the issue text.

Assessment

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.