Inconsistent behavior when comparing function pointers in release

[repnop]

Playground link: https://play.rust-lang.org/?gist=62d362e2bf72001bd3f3c4a3ed0c842c&version=stable&mode=release&edition=2015

Switching to debug causes it to print both addresses twice (expected behavior), but in release both functions are optimized into one, so x and y are given the same address. @CryZe took a look at the assembly, and LLVM removed the first comparison (and evaluated it to a constant false), but not the second, which then evaluates to true. This is very reminiscent of undefined behavior in C and C++.

Thanks to @memoryruins for sending the original link which allowed me to discover this.

fn foo(i: i32) -> i32 {
    1
}
fn bar(i: i32) -> i32 {
    1
}

fn main() {
    let x: fn(i32) -> i32 = foo;
    let y: fn(i32) -> i32 = bar;
    
    if x == y {
        println!("true")
    } else {
        println!("{:?}, {:?}", x, y);
    }

    if x == y {
        println!("true")
    } else {
        println!("{:?}, {:?}", x, y);
    }
}

Debug output:

0x562a7b399600, 0x562a7b399620
0x562a7b399600, 0x562a7b399620

Release output:

0x560d1e3a1310, 0x560d1e3a1310
true

stable rustc 1.29.1 (b801ae6 2018-09-20)

[repnop]

Also worth noting (pointed out by @memoryruins) that MIRI throws an error in the comparison saying it dereferenced a function pointer.

[ishitatsuyuki]

We run mergefunc pass on release builds. Anyway, can you explain why this is a problem? Rust does not make any guarantee on pointer values.

[CryZe]

It seems like LLVM starts comparing the pointer of bar to bar instead of comparing bar to foo. This very much looks like LLVM is messing up in some way.

Unless LLVM is allowed to break function pointers entirely.

Actually that may be what mergefunc is doing.

[Havvy]

@ishitatsuyuki The problem is that they shouldn't produce an x == y expression that is false in one statement and then true in the next. They should either always be equal or never be equal, but this code snippet shows that this is not always true.

@rep-nop Can you include the source code from the playground and the compilation results (under release and debug) into your opening comment?

[eddyb]

(came here from #54695)

According to @rkruppe, this could be caused by constant-folding &a == &b to false in LLVM (when a and b are different globals).
IMO this optimization shouldn't apply to functions and/or any unnamed_addr globals.

cc @rust-lang/compiler

[VictorKoenders]

Insanity Is Doing the Same Thing Over and Over Again and Expecting Different Results

[strega-nil]

This is definitely a bug in LLVM, afaict - this expression should never be true in C++. It may be that they never set unnamed_addr on functions?

[VictorKoenders]

• Still happens with no_mangle
• Still happens with pub
• Still happens with extern "C"

[hanna-kruppe]

@ubsan Yeah Clang doesn't add unnamed_addr anywhere as aggressively as rustc, and unnamed_addr is the one that allows completely merging the functions (which is required for the comparison to return true).

[strega-nil]

@rkruppe seems like someone added an optimization that assumes that functions are always distinct, even when unnamed_addr. We might want to open a bug on LLVM?

[hanna-kruppe]

I don't see why this would be an LLVM bug. The observed behavior seems perfectly in line with the meaning of unnamed_addr: the address is not significant, so address comparisons can evaluate either way. If a frontend does not want that, it shouldn't add unnamed_addr to functions whose address is observed. (Not saying that's what rustc should do, if it came down to it I would argue for the current behavior, just describing what would probably be a reasonable position of LLVM developers.)

[RalfJung]

Oh this is beautiful. ;) Finally we have a real-life example of pointer comparison being non-deterministic. It's not at all how I expected that example to look, though...

Non-determinism does not mean that we have UB, so I do not think there is a huge problem here. But non-deterministic comparison is certainly surprising. It means, for example, that the PartialEq implementation for function pointers does not satisfy the PartialEq contract, which is something we should keep in mind.

I suppose we could also have an analysis to see which functions have their address taken, and not set unnamed_addr for them?

[arielb1]

@RalfJung

What would be a problem would be if LLVM also assumes that equality is deterministic and duplicates 2 occurrences of the comparison.

[hanna-kruppe]

@arielb1

What would be a problem would be if LLVM also assumes that equality is deterministic and duplicates 2 occurrences of the comparison.

That is a very good point. I don't think there is anything preventing that, and in principle that could lead to unsoundness. However, this problem applies to all comparisons that might be non-deterministic, right? So "just don't use unnamed_addr" wouldn't solve it.

@RalfJung

I suppose we could also have an analysis to see which functions have their address taken, and not set unnamed_addr for them?

LLVM already does that, or more precisely, it adds unnamed_addr to functions that are guaranteed to not have their address taken. This is only knowable for internal functions, so it's a significant downgrade from the status quo in non-LTO builds. It also can't distinguish e.g. between only putting a function in a vtable (which is not accessible to users and only ever used for calling) and reifying a function pointer in user code. The latter could be solved by an analysis in rustc, but the former is a fundamental limitation of separate compilation.

[RalfJung]

@arielb1 Ah right, forgot about that... so, is it UB under LLVM IR to take the address of a function tagged unnamed_addr?

However, this problem applies to all comparisons that might be non-deterministic, right?

True, but it is not clear if there are any. I cannot give a satisfactory definition of LLVM semantics that makes ptr comparison deterministic, but I also was unable to find an example that would demonstrate that it is not deterministic.

[hanna-kruppe]

is it UB under LLVM IR to take the address of a function tagged unnamed_addr?

I see no reason for that and it seems unnecessarily restrictive (again consider function pointers in vtables, their address is taken and must be considered to escape, but the actual address is never observed). It ought to be enough if comparisons, pointer->integer casts, and and anything else that leaks information about the address is undef or poison.

[RalfJung]

Ack -- just taking a reference and calling it is fine indeed.

However, in Rust, with fn ptr comparison being a safe operation, that doesn't really help us all that much.

[hanna-kruppe]

Yes, for Rust we may have to stop applying unnamed_addr to most functions ☹️

[eddyb]

I don't think we should stop using unnamed_addr, and aside from this (overly, IMO) aggressive constant-folding optimization, I expect function pointers to behave as boringly as those obtained from Box::leak, just that sometimes you might happen to have two pointers to the same machine code function, despite them originating from distinct Rust functions.

That is, I expect the place where non-determinism happens, to be on reification to fn pointer.
It's possible for two distinct Rust functions to map to the same machine code function, or the same Rust function to map to two machine code functions.
That's what we don't guarantee - that mapping. foo as fn() != foo as fn() is fine.

Meanwhile, once you have a pointer, you should be able to expect it to behave in certain ways.
If you have let x = foo as fn(); then I certainly expect x == x and other properties to hold.
And if you black box its creation you totally can. It's just this optimization.

[eddyb]

@arielb1 said:

@RalfJung What would be a problem would be if LLVM also assumes that equality is deterministic and duplicates 2 occurrences of the comparison.

In terms of "pure operations on SSA values", I think it's reasonable to expect that the same operation applied to the same inputs, would be always deterministic.
Doesn't GVN rely on that? In fact, I'm shocked GVN doesn't hide the constant-folding here.

Oh, I figured out why we can even observe the difference! Printing takes a reference, and LLVM doesn't know it's a read-only reference, and assumes the pointer can change.

[VictorKoenders]

If you have let x = foo as fn(); then I certainly expect x == x and other properties to hold.

Especially if you have the statement if x == y being executed twice giving different results. Unless x or y changes when you compare it (which shouldn't happen, but technically is possible), you'd expect a std/core comparison to be deterministic.

[RalfJung]

In terms of "pure operations on SSA values", I think it's reasonable to expect that the same operation applied to the same inputs, would be always deterministic.

That's only true if the operation is, well, deterministic. The game is still open about whether that is the case for pointer comparison (think: comparing one-past-the-end pointers). But those subtleties are likely not an issue here.

Also one could make the same argument about casting a function to a fn ptr, I do not see a good reason why that would be any less deterministic than other operations.

But, concretely, you seem to propose to pass fn ptrs through black_box after their creation? That would likely fix this case, but it'd also kill LLVM's ability to replace dynamic calls by static ones.

[eddyb]

But, concretely, you seem to propose to pass fn ptrs through black_box after their creation?

No, I'm not. I'm just saying that the resulting behavior is what I expect, for integer operations on fn().

Also one could make the same argument about casting a function to a fn ptr, I do not see a good reason why that would be any less deterministic than other operations.

The compilation model means that we can't always easily deduplicate instances of the same function with the same type parameters, if that's what you mean.
Think about two sibling crates that both happen to instantiate Vec::<[u8; 3_141_592]>::new - if you're generating machine code, how would you guarantee that you get the same function pointer?

[RalfJung]

Think about two sibling crates that both happen to instantiate Vec::<[u8; 3_141_592]>::new - if you're generating machine code, how would you guarantee that you get the same function pointer?

That's a different case though. Here, both casts are in the same function even. Seems reasonable to expect something deterministic there.

No, I'm not. I'm just saying that the resulting behavior is what I expect, for integer operations on fn().

I do not understand what you are proposing then. Also, ptr equality is not the same as equality of the resulting integers. We are talking about comparison at fn() type here, not at usize. The latter definitely should be deterministic. (However, LLVM has some bugs where it removes ptr-int-casts, leading to miscompilations.)

[eddyb]

@RalfJung I guess the confusing bit that led me to say "integer operations" is that LLVM uses icmp for comparing pointers (albeit without casting to integers first).

Also, I found the code responsible for making the decision that the const-fold is valid:

static ICmpInst::Predicate areGlobalsPotentiallyEqual(const GlobalValue *GV1,
                                                      const GlobalValue *GV2) {
  auto isGlobalUnsafeForEquality = [](const GlobalValue *GV) {
    if (GV->hasExternalWeakLinkage() || GV->hasWeakAnyLinkage())
      return true;
// ...
    if (!isGlobalUnsafeForEquality(GV1) && !isGlobalUnsafeForEquality(GV2))
      return ICmpInst::ICMP_NE;

So it seems like patching LLVM to get the more boring behavior only involves adding an extra check for unnamed_addr, right next to the hasExternalWeakLinkage and hasWeakAnyLinkage check.
(Note that this problem also affects constant globals, not just functions)

[RalfJung]

Ah yes, icmp is used for both integer and pointer comparisons. I never even thought about the fact that the i might be for "integer". ;)

[strega-nil]

@eddyb there already exists the guarantee that

template <typename T>
void foo();

foo<int> == foo<int>, no matter where these pointers were gotten. That's what inline linkage is for.

[tmiasko]

This issue was fixed in https://reviews.llvm.org/D87123

[nikomatsakis]

Tagging as "needs test" -- do we have a minimal example?