rust-lang / rust-lang/rust

Basic wrapping arithmetic on pointers is pessimized compared to integers

Open
#135,798 5 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

A-LLVM C-optimization I-slow T-compiler
Dominant language
Rust
Stars
119k
Forks
16.1k
PR merge metrics
PR metrics pending

Description

Consider these two very simple functions:

pub fn foo_int(x: usize, y: usize, z: isize) -> (usize, usize) {
    let mask = (z.wrapping_sub(15) >> (isize::BITS - 1)) as usize;
    (x.wrapping_sub(mask), y ^ mask)
}

pub fn foo_ptr(x: *const u8, y: usize, z: isize) -> (*const u8, usize) {
    let mask = (z.wrapping_sub(15) >> (isize::BITS - 1)) as usize;
    (x.wrapping_sub(mask), y ^ mask)
}

I would expect these to generate identical codegen. Here we are treating a pointer as an ordinary number, with wrapping_sub. But we actually see a pessimization in the codegen for the pointer version:

foo_int:
        mov     rax, rdi
        add     rdx, -15
        sar     rdx, 63
        sub     rax, rdx
        xor     rdx, rsi
        ret

foo_ptr:
        add     rdx, -15
        mov     rax, rdx
        shr     rax, 63
        sar     rdx, 63
        add     rax, rdi
        xor     rdx, rsi
        ret

I think this has something to do with provenance. Consider the following two modified examples:

pub fn foo_expose_ptr(x: *const u8, y: usize, z: isize) -> (*const u8, usize) {
    let mask = (z.wrapping_sub(15) >> (isize::BITS - 1)) as usize;
    let u = x.expose_provenance().wrapping_sub(mask);
    (std::ptr::with_exposed_provenance(u), y ^ mask)
}

pub fn foo_map_addr_ptr(x: *const u8, y: usize, z: isize) -> (*const u8, usize) {
    let mask = (z.wrapping_sub(15) >> (isize::BITS - 1)) as usize;
    (x.map_addr(|a| a.wrapping_sub(mask)), y ^ mask)
}

foo_expose_ptr is efficient like foo_int, but foo_map_addr_ptr is pessimized like foo_ptr. I think this is a bug, provenance should not pessimize basic wrapping integer arithmetic, even if it occurs on pointers.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with the foo_ptr, foo_expose_ptr, and foo_map_addr_ptr examples and compare their generated assembly with foo_int. Trace how wrapping subtraction and pointer provenance are represented in Rust compiler codegen; done means pointer and integer wrapping arithmetic produce equivalent efficient code without changing provenance semantics.

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
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.