Safe Rust code miscompilation due to a bug in LLVM's Global Value Numbering

[RalfJung]

lib/src.rs in the foo crate:

#[inline(never)]
pub fn test(gp1: &mut *const i32, gp2: &mut *const i32, b1: bool, b2: bool) -> (i32, i32) {
    let mut g = 0;
    let mut b = 0;
    let y = 6666;
    let mut x = 7777;
    let mut p = &mut g as *const _;

    {
        let mut q = &mut g;
        let mut r = &mut 8888;

        if b1 {
            p = (&y as *const _).wrapping_offset(1);
        }

        if b2 {
            q = &mut x;
        }

        *gp1 = p.wrapping_offset(1234);
        if q as *const _ == p {
            b = 1;
            *gp2 = (q as *const _).wrapping_offset(1234);
            r = q;
        }

        *r = 42;
    }

    return (b, x);
}

src/main.rs in the main crate:

use std::ptr;

extern crate foo;

pub fn main() {
    let mut x1 = ptr::null();
    let mut x2 = ptr::null();
    let mut gp1 = &mut x1;
    let mut gp2 = &mut x2;

    let (b, x) = foo::test(&mut gp1, &mut gp2, true, true);
    println!("b = {}, x = {}", b, x);
}

This prints b = 1, x = 7777. That is wrong; if b is 1, it must be the case that the then-branch in the q as *const _ == p conditional was taken, so r is &mut x (since b2 is true), so x cannot still be 7777.

This is a bug in LLVM's GVN, see https://bugs.llvm.org/show_bug.cgi?id=35229 for the upstream report and some further analysis.

Original C test case by Gil Hur.

[bstrie]

Conservatively tagging this as I-unsound, feel free to downgrade to I-wrong if necessary.

[nikomatsakis]

We discussed this in the @rust-lang/compiler team meeting and we are thinking of closing this bug. It doesn't make sense to have a bug for every LLVM bug, and this one hasn't been observed "in the wild" for Rust code, only for artificial examples, so it's probably not adding much value. @RalfJung thanks for bringing it to our attention.

If LLVM decides not to fix, we may want to re-open, though it's unclear if there is much we can practically do to prevent this sort of optimization.

[RalfJung]

Fine for me.

If LLVM decides not to fix, we may want to re-open, though it's unclear if there is much we can practically do to prevent this sort of optimization.

I'd say this depends on their reasoning. If they somehow introduce a rule that this ought to be UB, we have a problem -- I don't see any good way to rule out such safe code. I would also be surprised if it was not possible to expand this miscompilation to trigger actual UB in safe Rust (notwithstanding the fact that miscompilations giving the wrong results in safe code aren't really less bad than UB in safe code).
OTOH, adapting my proposal in #45719 to not use GEP in wrapping_offset would fix all known ways to exploit this bug.

[cristicbz]

FWIW, we could fix this by replacing the wrapping_offset implementation with ((self as isize).wrapping_add(offset * (size_of::<T>() as isize)) as *const T), but I see perf regressions on simple things like:

#[bench]
fn current(b: &mut Bencher) {
    let mut v = Vec::with_capacity(512);
    let mut r = 0u32;
    v.clear();
    for _ in 0..512 {
        r = r.wrapping_mul(1664525).wrapping_add(1013904223);
        v.push(r);
    }

    b.iter(|| {
        let v = black_box(&v);
        let mut p = v.as_ptr();
        let end = v.as_ptr().wrapping_offset(v.len() as isize);
        let mut sum = 0;
        while p != end {
            sum += unsafe { *p };
            p = p.wrapping_offset(1);
        }
        black_box(sum)
    });
}

goes from 23ns/iter up to 187ns/iter . Investigating the asm (playground), it looks like it inhibits auto-vectorisation on:

pub trait WrappingOffsetExt {
    fn wrapping_offset_ext(self, offset: isize) -> Self;
}

impl<T> WrappingOffsetExt for *const T {
    fn wrapping_offset_ext(self, offset: isize) -> Self {
       ((self as isize).wrapping_add(offset * (::std::mem::size_of::<T>() as isize)) as *const T)
    }
}

#[no_mangle]
pub fn via_wrapping_offset(v: &[u32]) -> u32 {
    let mut p = v.as_ptr();
    let end = v.as_ptr().wrapping_offset(v.len() as isize);
    let mut sum = 0;
    while p != end {
        sum += unsafe { *p };
        p = p.wrapping_offset(1);
    }
    sum
}

#[no_mangle]
pub fn via_integer(v: &[u32]) -> u32 {
    let mut p = v.as_ptr();
    let end = v.as_ptr().wrapping_offset_ext(v.len() as isize);
    let mut sum = 0;
    while p != end {
        sum += unsafe { *p };
        p = p.wrapping_offset_ext(1);
    }
    sum
}

fn main() {}

Edit: Fixed lack of size_of::<T>.

[RalfJung]

FWIW, we could fix this by replacing the wrapping_offset implementation with ((self as isize).wrapping_add(offset) as *const T),

That's what I mentioned in my previous commit; however, your patch is slightly wrong: You need to multiply offset by mem::size_of::<T>.

[eddyb]

The only reason wrapping_offset was added was to avoid roundtripping through an integer.
cc @dotdash who added the intrinsic (arith_offset) back in #25434.

[cristicbz]

@RalfJung

what I mentioned in my previous commit

Not sure which commit that, I must have missed it, sorry.

You need to multiply

D'oh, sorry. Numbers and conclusions stay exactly the same.

@eddyb
Right, makes sense. Figured it would be good to know if in this particular case roundtripping would fix the issue or not. @RalfJung mentioned on reddit that due to LLVM 34548 casting to integers before comparing doesn't help. Wanted to check if casting before the arithmetic does work.

[RalfJung]

@eddyb thanks for the pointer to #25434. It seems that wrapping_offset deliberately does not round-trip through integers, enabling more optimizations. In this case, however, I think there should be a big fat warning in that method's documentation that also the operational effect of this is very different from doing the same thing on integers! The fact that LLVM optimizes more is not because LLVM does not see the potential for optimization when using integers; it is that the optimization would be illegal.

[regehr]

Can I ask if you (Rust compiler) folks have looked over the emitted IR for this one super carefully to make sure it doesn't contain anything that gives LLVM an easy excuse to invoke UB?