Pointer equality across allocations hits poorly specified parts of LLVM

[mcy]

While Rust defines raw pointer equality as a safe operation, it appears that this is not so in practice. Consider the
following reduced example:

#[inline]
pub fn eq_inline<T>(a: *const T, b: *const T) -> bool {
    a == b
}

#[inline(never)]
pub fn eq_outline<T>(a: *const T, b: *const T) -> bool {
    a == b
}

#[inline(never)]
pub fn always_false() -> bool {
    let (a, b) = (0, 0);
    eq_inline((&a as *const i32).wrapping_add(1), &b)
}

#[inline(never)]
pub fn always_true() -> bool {
    let (a, b) = (0, 0);
    eq_outline((&a as *const i32).wrapping_add(1), &b)
}

pub fn main() {
    println!("{}, {}", always_false(), always_true())
}

(Godbolt)

On Rust 1.52.0 with rustc -O, this prints false, true; this is entirely dependent on the inlining attrs on the
two eq functions. always_false is optimized to a constant return, while always_true passes identical
pointers (rsp + 4, in this case) into eq_outline, which does a blind comparison.

The LLVM LangRef is unfortunately silent on this, but it appears that the root of the problem is that Rust emits the following code for pointer equality:

define ptr_eq(i32* readnone %a, i32* readnone %b) i1 {
  %eq = icmp eq i32 %a, %b
  ret i1 %eq
}

While this looks fine, Clang emits the exact same IR for comparisons of int*, and Clang is entitled to (and, in fact, makes) this optimization, because poitner comparisons across provenance domains is UB in C/C++. This makes me believe this is true UB, and not implementation-defined behavior.

In short, it is incorrect to lower pointer comparison, with Rust semantics, to icmp eq T*. I don't know of a workaround, since LLVM explicitly transmits provenance through bitcast and ptrtoint; in fact, icmp of pointers is defined as icmp of the pointers passed through ptrtoint. The solution may simply be to add some kind of optimization barrier to LLVM; who knows?

#54685 is a related but distinct issue, since it's about comparison of function pointers, which are inherently global variables; the fix in LLVM is only relevant to globals, AFAICT.

[workingjubilee]

To clarify the bug, since I misunderstood it at first, if the #[inline(never)] or eq_{outline,inline} are changed, the resulting truth value of the comparison may change. I believe our current behavior may indeed be unsound.

[nikic]

While LangRef does not explicitly say so, it is our working assumption that pointer equality is integer equality and comparison of pointers of different provenance is not poison. Alive2 was recently updated with these semantics.

[mcy]

This seems to motivate that LLVM does not have these semantics today:

bool always_false(void) {
    int* p = malloc(4);
    int q;
    return p < &q;
}

(Godbolt)

Clang is fully entitled to believe that this is UB, but LLVM emits the naive address comparison. All seems well? There is probably an overlap here between alias analysis feeding back into pointer equality (i.e. pointers do not alias, so the user cannot observe them being equal) that does not extend to order comparisions. Maybe it's sufficient to believe that icmp for T* of distinct provenances is implementation-defined but not poison (freeze i1 poison if you like). Good to know this is what the Alive2 people are thinking.

It seems a bit difficult to disentangle general alias analysis from pointer equality, but such as it is, I think.

[steffahn]

Is there a better demonstration of actual unsoundness? In my view, always_false and always_false are totally allowed to lay out the local variables different in always_false vs always_true. Something like

#[inline(never)]
pub fn both() -> (bool, bool) {
    let (a, b) = (0, 0);
    (eq_outline((&a as *const i32).wrapping_add(1), &b), eq_inline((&a as *const i32).wrapping_add(1), &b))
}

doesn’t seem to produce inconsistent results. Where’s the actual problem?

Edit: By the way, I wasn’t able to fully understand the explanation below the example. Nonetheless, if there is any form of UB involved, it would help a lot if there was a better example that demonstrates any actually weird or problematic behavior in a way that doesn’t require understanding LLVM internals.

[mcy]

I don't think there's a good way to illustrate this without knowledge of LLVM internals. =( I can try to think of a more complex example, but I've only got so much free time- I'm hoping people who more actively work with LLVM directly than I do can definitively confirm whether Rust is emitting sane IR.

(Compare: Rust having to emit getelementptr rather than getelementptr inbounds for wrapping_add.)

[inquisitivecrystal]

@rustbot label +T-compiler

[mcy]

Honestly, those LLVM bugs don't make me feel any better. It's pretty clear that we're not sure if icmp folding should take advantage of provenance or not-- I couldn't tell if there was consensus anyways (in C++ land I would want this to be a thing, but not in Rust where we seem to believe provenance does not flow into comparisons).

It may be worth either closing this or punting it to UCG, since the Rust semantics are not nailed down yet anyways and this is much more a "what does LLVM do" question at this point. (It definitely seems like something to pay attention to given we have had nasty miscompilations around icmp in the past, e.g. fnptrs.)

[RalfJung]

While this looks fine, Clang emits the exact same IR for comparisons of int*, and Clang is entitled to (and, in fact, makes) this optimization, because poitner comparisons across provenance domains is UB in C/C++.

Which part of the C standard do you derive this from (specifically for eq)? lt across allocations is UB, but eq is always defined I think. (I am not sure about C++.)

In short, it is incorrect to lower pointer comparison, with Rust semantics, to icmp eq T*

I don't think this is correct. To my knowledge, comparing pointers in LLVM is always safe (eq, lt, all of them). There are a few bugs here, but those should be reported with LLVM.

Honestly, those LLVM bugs don't make me feel any better. It's pretty clear that we're not sure if icmp folding should take advantage of provenance or not-- I couldn't tell if there was consensus anyways (in C++ land I would want this to be a thing, but not in Rust where we seem to believe provenance does not flow into comparisons).

I think it is pretty clear that consensus is forming towards "no, provenance may not affect pointer comparison". There are LLVM transformations that assume this, and the provenance TS also mandates it. In the relevant bugreports, LLVM devs have to my knowledge never used the argument that provenance should be taken into account for pointer comparison.

In other words: yes, there are bugs, because a few of the LLVM transformations have been written before people started thinking properly about the semantics of LLVM IR. But I see no indication that LLVM actually desired to make pointer comparison anything other than what Rust needs it to be.

[RalfJung]

since LLVM explicitly transmits provenance through bitcast and ptrtoint

These are bugs, there are other LLVM optimizations that explicitly assume that provenance is not transmitted through bitcast and ptrtoint. Se this blog post for a more lengthy explanation.

So, overall -- I agree it is important to keep an eye on what LLVM is doing here, and maybe work with them to ensure what they do works for us, but I don't think this issue should carry the "unsound" tag.