Figure out the interaction of GVN and function/vtable pointers

[RalfJung]

GVN has special treatment for function/vtable pointers. I haven't fully understood why.

Function pointers have unstable comparison. We set the unnamed_addr flag in LLVM. I am not entirely sure how far that attribute goes, but I think it means that == involving such functions is basically non-deterministic? @nikic @bjorn3 maybe you can help here -- can the result of comparing function pointers depend on whether or not optimizations are applied? Or how exactly unnamed_addr affect the generated code?

@cjgillot could you give an example for the code you are concerned about, where GVN would go wrong if it did not special-case function pointers? I think you gave an example a while ago but I can't find it right now.

[bjorn3]

unnamed_addr allows LLVM to merge multiple functions if they have the same body after optimizations. This will result in their address comparing equal.

[RalfJung]

So there's no impact on icmp semantics?

Apart from unnamed_addr we also have our own multiple-codegen-unit issue, where the same function can have more than one address. That could be considered as making a choice at fn-item-to-fn-ptr coercion time. The possible concern here is having the AllocId we generate there move into different codegen units or crates so they don't end up being the same address. But that's already the case I think? const C: fn() = myfunc; is evaluated once but we just use the AllocId everywhere and each crate will do with that whatever it wants. Even without GVN I think this means that that const can have different integer values in different crates?

[RalfJung]

Cc @oli-obk for the last question

[nikic]

So there's no impact on icmp semantics?

The icmp may evaluate to either true or false, but it will do so consistently. That is, for unnamed_addr symbols, LLVM will not fold "icmp eq s1, s2" to false in cases it normally could, in case s1 and s2 end up being merged later.

[oli-obk]

const C: fn() = myfunc; is evaluated once

it is evaluated per-crate. For constants we only cache within the current crate.

but we just use the AllocId everywhere and each crate will do with that whatever it wants.

yea, that's why it doesn't matter, each crate generates its own AllocId per function pointer anyway. And we do generate multiple different AllocIds for the same function pointer... sometimes. See

rust/compiler/rustc_middle/src/mir/interpret/mod.rs

Line 555 in 81d7d7a

pub fn reserve_and_set_fn_alloc(self, instance: Instance<'tcx>) -> AllocId {

Even without GVN I think this means that that const can have different integer values in different crates?

what integer values?

[RalfJung]

@nikic thanks!

@oli-obk

yea, that's why it doesn't matter, each crate generates its own AllocId per function pointer anyway.

If we have const C: fn() = myfunc; in one crate then that's a single AllocId, right?

But OTOH AllocId is a per-rustc-invocation identifier and they get re-assigned when rlibs get loaded... right? So the question is somewhat moot anyway.

what integer values?

The underlying address, after compilation.

So probably the GVN issue is about something like

const C: fn() = myfunc;

let x = C;
let y = x; // definitely the same address as x

becoming

const C: fn() = myfunc;

let x = C;
let y = C; // maybe a different address than x?

I think we want to be sure that C is the same address when it is used multiple times in the same function. But what has to happen to make that true?

[oli-obk]

But what has to happen to make that true?

It's already true if LLVM makes it true. We swap the alloc id for its Instance in codegen. So whatever happens there is relevant.

To also deduplicate AllocIds, we need to remove

rust/compiler/rustc_middle/src/mir/interpret/mod.rs

Line 567 in 81d7d7a

if is_generic {

and always run the else arm.

[cjgillot]

@RalfJung this is more than a concern, I saw it surface as an actual bug from core::fmt::rt::USIZE_MARKER. Consider the following rustc:

// crate A, optimized
fn foo() {}

static MARKER: fn() = foo;

#[inline]
fn bar(x: fn()) -> bool {
    x == MARKER
}

// crate B, no optimization
fn baz() -> bool {
    bar(A::MARKER)
}

The original MIR is something like:

// CGU-local copy, for LLVM to inline
fn bar(_1: fn()) -> bool {
    _2 = const { alloc0 as &fn() }; // the address for the static MARKER
    _3 = *_2; // the fn pointer inside MARKER
    _0 = Eq(_1, _3)
}

fn baz() -> bool {
    _2 = const { alloc0 as &fn() }; // stable cross-crate, so it's ok
    _3 = *_2;
    _0 = bar(_3)
}

All is well.

Now, coming to the issue. If we propagate values that contain provenance, we may get to codegen this MIR:

// CGU-local copy, for LLVM to inline
fn bar() -> bool {
    _3 = const { foo as fn() }; //-> point to a CGU-local copy
    _0 = Eq(_1, _3)
}

fn baz() -> bool {
    _2 = const { alloc0 as &fn() }; // the address for the static MARKER
    _3 = *_2; //-> points to the imported instance from crate A
    _0 = bar(_1, _3)
}

We have the bug: we now compare the addresses of 2 different copies of foo.

[RalfJung]

So the problem is that the same const value results in different final bit patterns when used in different CGUs. These values aren't actually values, there is further non-determinism when they get evaluated to their final form. That's pretty bad. I am surprised this only becomes a problem with optimizations.

FWIW one reasonable alternative here may be to say that GVN should never read from a static. With const we already say they have semantics that correspond to inlining so you are not guaranteed to get the same function pointer when you reference the same const multiple times.

[RalfJung]

FWIW one reasonable alternative here may be to say that GVN should never read from a static.

When would doing that not be sufficient?
I am imagining a scenario like

const C: fn() = ...;

let x = C;
return (x, x);

Now if this is turned into (C, C) we better be sure that wherever these two const values "flow", their bit patterns are actually the same, despite the fact that const values do not fully determine the final LLVM-level value. They will obviously be in the same CGU so the main risk here is MIR-level transformations that would put them in different CGU.

However it seems like we already don't guarantee that this function will return a constant usize:

const C: fn() = ...;

fn make() -> usize { C as *const () as usize }

So... I don't see how whatever happens in MIR optimizations can make it any worse.

Therefore it seems to me the best way forward is to establish a specific guarantee for static, that they are evaluated only once, and restrict how GVN reads values from static. Then GVN does not have to do any further restrictions down the line.

Or we find a way to fix the insanity that is const values actually not being values... that should be possible; after all const values can only refer to fully monomorphic items so we "just" have to make sure that all uses of the const value refer to the same instantiation of that monomorphic item. For const this doesn't really help as we just store their MIR, not their final value, and re-evaluate them -- but for static thanks to @oli-obk we store the final value, and so maybe we can make sure that the value we store is fully monomorphic and will result in the exact same bits no matter where it is codegen'd.

[RalfJung]

Another way to put this is that #116564 is incomplete. @oli-obk made it so that we store the "value" of the static rather than its MIR, so that we compute a single canonical value. The problem is that it turns out "values" aren't actually values, this is not canonical enough -- codegen will re-monomorphize what the "value" needs each time the value shows up in a CGU.

Instead static should store a "value" that is truly the final value, something that always becomes the same final bits, something where all the functions (and vtables) mentioned in the static are codegen'd in the crate that declared the static and then everything refers to those particular monomorphizations, not copies of the same function that appear elsewhere.

Is that possible?

[RalfJung]

@cjgillot

I saw it surface as an actual bug from core::fmt::rt::USIZE_MARKER

IMO that code is buggy, it should use a static pointing to an inline(never) monorphic function. That should ensure it is codegen'd only once. Would that avoid the issue?

Functions that can be inlined simply don't have a stable address, even if you store them in a static.

[RalfJung]

The problem is that it turns out "values" aren't actually values, this is not canonical enough -- codegen will re-monomorphize what the "value" needs each time the value shows up in a CGU.

Turns out we have an issue for that, at least for the case of function pointers: #84581.

[RalfJung]

So the problem is that the same const value results in different final bit patterns when used in different CGUs. These values aren't actually values, there is further non-determinism when they get evaluated to their final form. That's pretty bad.

I think we should fix that, which might just resolve all the GVN issues. I opened #128775 to discuss the possible options here.