Miscompilation: comparing a pointer against all possible addresses returns `false`

[RalfJung]

Consider this code:

#![feature(strict_provenance)]

use std::ptr;

#[no_mangle]
pub fn test(x: *mut u8) -> bool {
    let local = 0u8;
    for i in 0..=usize::MAX {
        if x.addr() == ptr::from_ref(&local).wrapping_add(i).addr() {
            return true;
        }
    }
    false
}

This compares x.addr() with every possible address there is. And yet, the optimized LLVM IR for this is:

; Function Attrs: mustprogress nofree norecurse nosync nounwind nonlazybind willreturn memory(none) uwtable
define noundef zeroext i1 @test(ptr nocapture noundef readnone %x) unnamed_addr #0 {
start:
  ret i1 false
}

That's clearly nonsense.

This is the Rust version of llvm/llvm-project#34450.

Cc @nikic @rust-lang/opsem

[orlp]

This also gets optimized to simply returning false:

#![feature(strict_provenance)]

use std::ptr;

#[no_mangle]
pub fn test(p: *mut u8) -> bool {
    let a = 0u8;
    p.addr() == ptr::from_ref(&a).addr()
}

I'm not sure if strict_provenance is to blame, because this does as well:

#[no_mangle]
pub fn test(x: *const u8) -> bool {
    let a = 0u8;
    (&a as *const u8 as usize) == x as usize
}

[RalfJung]

@orlp yes but that can be justified. You are basically comparing an arbitrary non-deterministic value with p here, and we can rationalize this by saying that we can always put a at an address that's different from p, so we can optimize this to false. (Of course it is important that a then really does not actually live at address p.addr() -- if we can get contradictions that way, that would still be a bug. But I am not aware of a way to get contradictions here.)

And this has nothing to do with strict provenance indeed, I just used addr() as it is shorter than as usze and has more well-defined semantics. ;)

[orlp]

But I am not aware of a way to get contradictions here.

Simply put the non-inlined test function into a loop that once again tests every possible address x. Unless the compiler really inserts some funky intentional-stack-misaligning logic into the preamble of test, it must be wrong at least once.

[RalfJung]

@orlp that doesn't work since a, logically, has a different address each invocation. In your code as given, there is nothing that actually observes the address, so the compiler can pick a basically arbitrary integer as the claimed "address" for a each time. It doesn't matter where the data for a is actually stored as long as everything behaves as-if it was stored at that arbitrary other address.

You'd have to construct an example where one can actually tell, inside the Rust program (i.e., not via a debugger or by inspecting the assembly), that a lives at address p.addr() and yet the comparison returns false.

[orlp]

Alright, I tried a bit to make a contradiction under those conditions and couldn't make one.

[apiraino]

WG-prioritization assigning priority (Zulip discussion).

@rustbot label -I-prioritize +P-low

[nbdd0121]

I think this is another manifest of #107975 (adapted from as to .addr(): https://play.rust-lang.org/?version=nightly&mode=release&edition=2021&gist=4365daa75e5b4d040e8cb88a317a8622) and llvm/llvm-project#45725?

Essentially LLVM performs pointer comparision with provenance.