What are the exact semantics of pointer comparison?

[RalfJung]

Pointer comparison is complicated. However, for better or worse, Rust lets you safely compare any raw pointers, so we need to assign this some reasonable semantics. I wanted a place to centrally track all questions related to this, so here we go. (I never know whether to open such issues here in the UCG repo, or over in the rustc repo.)

There are two ways in which pointer comparison is "interesting": provenance, and objects without a guaranteed stable address.

Provenance

Does provenance affect whether pointers are equal? One major concern here is figuring out the semantics of pointer comparison in LLVM, and then likely we have no choice but to inherit that. Some data points:

• Eli Friedman writes

  icmp is defined to just take the raw pointer bits as an integer. This is described in LangRef. If the text of LangRef describing icmp isn't sufficiently clear, suggestions welcome. If some transform isn't consistent with this, please file a bug.

• In our LLVM semantics paper, we made pointer comparison non-deterministic under some conditions (when the addresses are equal but provenance differs), so that pointers derived from different calls to malloc can always compare inequal even if they are physically equal. This directly contradicts Eli's statement above.

I am trying to figure out if LLVM optimizations clearly indicate one or the other choice; so far that has been inconclusive.

Unstable objects

Functions, vtables, and consts do not have a unique stable address, also leading to interesting problems.

function address equality

• Inconsistent behavior when comparing function pointers in release rust#54685: Inconsistent behavior when comparing function pointers in release
• function pointers as match patterns have optimization-dependent behavior rust#70861: function pointers as match patterns have optimization-dependent behavior
• Invalid equality check result for usizes obtained from function pointers rust#73722: Invalid equality check result for usizes obtained from function pointers

vtable equality

• vtable addresses differ based on the number of codegen units rust#46139: vtable addresses differ based on the number of codegen units
• Consider warning when comparing wide pointers with vtables (as their address identity is unstable) rust#69757: Consider warning when comparing wide pointers with vtables (as their address identity is unstable)

const address equality

• Some interesting observations

[RalfJung]

This is a somewhat interesting example:

extern crate libc;
use std::mem;
pub fn test(ext: bool) -> bool { unsafe {
    let x = libc::malloc(mem::size_of::<i32>()) as *mut i32;
    *x = 0;
    if ext { libc::free(x as *mut _); }
    let y = libc::malloc(mem::size_of::<i32>()) as *mut i32;
    *y = 0;
    return x == y;
} }

It gets optimized to return false, so this looks a bit like ptr comparison does not look at the actual address, since ptr reuse could have happened. But then, ptr reuse also could have not happened, and LLVM assumes that the allocator itself is not observable. (I don't know if it assumes that just for malloc or also for e.g. custom Rust allocators. In case of the latter, that would be an interesting and so far undocumented piece of possible UB.) So arguably, even under the strict "compare int addresses", this optimization is correct.

[RalfJung]

Also see this LLVM bug.

[tmiasko]

The optimization from #239 (comment) is based on the assumption that LLVM is allowed to substitute its own allocation function and guarantee particular outcome of the comparison.

Those kind of optimizations are also applicable to Rust allocation functions, since rustc explicitly opt ins for this behaviour for rust_alloc, rust_dealloc and rust_realloc.

[RalfJung]

Right. But it is unclear to me howto actually make that formally precise. Like, how could we implement support for custom allocators in Miri in a way that it detects UB when the allocator works in a way that breaks the above optimization?

[RalfJung]

I updated the OP to also link to various issues about function pointer and vtable equality.

[RalfJung]

I entirely forgot that const are another example of objects without stable addresses; that can lead to some interesting effects as well.