Unique reference pointer equality tests are not optimized

[Voultapher]

I tried this code:

pub fn x(a: &mut i32, b: &mut i32) -> bool {
    let a_ptr = a as *const i32;
    let b_ptr = b as *const i32;

    a_ptr == b_ptr
}

I expected to see this happen:
The optimised function should always return false. However it generates a comparison. As seen here https://godbolt.org/z/5YMK1Wc38.

example::x:
        cmp     rdi, rsi
        sete    al
        ret

rustc --version --verbose:

rustc 1.69.0-nightly (5e37043d6 2023-01-22)
binary: rustc
commit-hash: 5e37043d63bfe2f3be8fa5a05b07d6c0dad5775d
commit-date: 2023-01-22
host: x86_64-unknown-linux-gnu
release: 1.69.0-nightly
LLVM version: 15.0.7
Compiler returned: 0

[kadiwa4]

Maybe related: rust-lang/rust#56604 (nevermind, the optimization doesn't happen with *mut i32 either)

[Noratrieb]

It is currently not clear whether we are allowed to optimize this, as we do not have a finalized aliasing model yet. Under Stacked Borrows this would be a legal optimization, but under LLVM noalias it is not.

[Voultapher]

@Nilstrieb even without Stacked Borrows, the current documentation seems very clear that unique references can never alias, even when UnsafeCell is involved. noalias is not strong enough, true. But rustc is free to generate LLVM IR as it pleases. I would be surprised if the Rust model would be based on LLVM noalias. As far as I understand Stacked Borrows tries to formalise some other parts, but this property is not up for debate. Maybe I understood that part wrong.

Tagging @RalfJung as the resident Stacked Borrows expert.

[Noratrieb]

unique references can never alias

Depending on what you mean with alias, this is trivially untrue in safe code.

This code works with NLL: playground

fn main() {
    let mut a = ();
    let a1 = &mut a;
    let a2 = &mut *a1;

    let p2 = a2 as *const ();
    let p1 = a1 as *const ();
    
    assert_eq!(p1, p2);
}

I think this code here is similar enough to not warrant these opts until we have decided on an exact aliasing model that may or may not allow this opt (although I guess that it will).

[Voultapher]

let a2 = &mut *a1; conceptually I would have thought that creates a new reference from the copied value of a1.

[Voultapher]

From the UnsafeCell documentation:

There is no legal way to obtain aliasing &mut, not even with UnsafeCell.

To me that seems to leave very little room for interpretation.

[Noratrieb]

let a2 = &mut *a1; conceptually I would have thought that creates a new reference from the copied value of a1.

It does not copy a1, it's a reborrow. It points to the same place. I guess it's a little unlucky I used () in my example, but String would work too.

[Noratrieb]

From the UnsafeCell documentation:

There is no legal way to obtain aliasing &mut, not even with UnsafeCell.

To me that seems to leave very little room for interpretation.

It doesn't define what "alias" means, so there's plenty of room for Interpretation :). But yes, according to the spirit of the docs this optimization is legal, but I don't think it's precise enough to act on it.

Although I do agree that it's quite likely that this optimization will be legal under the aliasing model we will get.

[RalfJung]

This is an interesting question. Surprising as it may sound, aliasing is actually only loosely related to pointer equality. (For that reason, LLVM cannot use noalias to optimize ptr equality tests.) So until we have a very concrete model I think it is advisable to avoid optimizing prematurely. However it would be valuable to identify real-world cases where an optimization like this could be measurably useful.

[Voultapher]

Surprising as it may sound, aliasing is actually only loosely related to pointer equality.

Fascinating, I'd love to hear more about it. Can you point me to a source.

[Voultapher]

Also what do you suggest we do with this bug, close it?

[RalfJung]

Fascinating, I'd love to hear more about it. Can you point me to a source.

The definition of noalias in the LLVM LangRef, and of restrict in the C spec, both allow code like this:

void demo1(int *restrict x, int *restrict y) {
  // even if x and y are the same, since they are only used to read, we can treat them as noalias
  int i = *x;
  int i = *y;
}
void demo2(int *restrict x, int *restrict y) {
  // even if x and y are the same, since they are not accessed at the same index, we can treat them as noalias
  x[0] = 0;
  y[1] = 0;
}

void main() {
  int arr[2] = {0, 0};
  demo1(arr, arr);
  demo2(arr, arr);
}

Basically, when compilers talk about 'noalias', the property they really care about is "can I reorder these two memory accesses". A noalias parameter attribute means "memory accesses through this pointer can be reordered wrt accesses done through any other (non-derived-from-this) pointer". This is a lot more valuable than optimizing pointer equality tests, so pointer equality is not part of the definition.

Now, Rust's definition does not exactly match LLVM or C. So as others stated above, it may well be that some pointer equality optimizations will be legal on Rust. But that would be "collateral benefits" and not treated with high priority -- unless we have known examples where such pointer equality optimizations could be very valuable. Also we'd have to write our own optimization passes for this; LLVM is not allowed to do that since noalias does not make any such promises.

[RalfJung]

Also what do you suggest we do with this bug, close it?

I have moved it to the UCG repo. I assume this is a reoccurring question and thus worth tracking as an FAQ item, and as a place for people to put examples where such an optimization could be very useful.