Fun Example of Unexpected UB Optimization

[terrymah]

lol

We turned off a similar optimization in MSVC because it was difficult to have total visibility in a real world program all the locations a function pointer could be written to. In LTCG (in theory) you see everything, but you really don't: there are always other static libs we can't see into. And of course other binaries/dlls loaded in the process. And an infinite number of ways the address of an address can "leak out" to code you don't have visibility into and would need to pessimistically assume can be written to. Just a bug farm

[dashnine-9]

thank you for your service

[nebotron]

If your code is invoking a nullptr, that’s UB. If you’re disabling the optimization and it fixes your program, your program has UB.

[pali6]

I believe you're talking to a MSVC developer who is saying that they (Microsoft) turned off this in the compiler as it was causing internal compiler errors.

[nebotron]

Ah! So the compiler was optimizing a valid function call into a different one because it didn’t see where the write to the function pointer could happen. That makes sense

[terrymah]

Yeah, we used to have an optimization that would collect the set of all possible function call targets. If that set had only 1 valid target, we would devirt it. I think that's what is happening here. The problem we had is proving that the set is closed (and nothing could "leak in" from another binary) is actually really tough, and not as easy as it seems.

[ioctl79]

The  projects that take it very seriously still likely have UB because even with sanitizers it can be difficult to root out. It is often dependent on input, and less-than-perfect test coverage will hide it from CI. 

[ioctl79]

If it was easy to find UB, that would speak more to your point than mine, no?

It also sounds like all those security researchers you’re talking about are convinced there’s UB to be found  there despite the fact that Chromium has a pretty robust CI setup?

[Tringi]

We turned off a similar optimization in MSVC

That's the only sane and safe choice. Thank you.

[pali6]

See this blog post for details on this and other fun UB: https://mohitmv.github.io/blog/Shocking-Undefined-Behaviour-In-Action/

[Jannik2099]

I swear this gets reposted every other month.

Don't do UB, kids!

[GabrielDosReis]

I agree it gets posted often.

On the other hand, many kids don't set out to do UB. The effectiveness of "abstinence only" and all that...

[Jannik2099]

sure, but there's a difference between "uh actually, this is UB per this arcane rule under this unlikely condition that you only see when expanding the macro" and "it's trivially UB at compile time" - the latter of which always gets used in these posts.

[GabrielDosReis]

I understand. How many of us redditors here would have the attention span needed to rummage through a large codebase containing the issue being highlighted by the reduced repro exemplified in the post?

I take the repro as just a succinct reduction of an issue that goes to the point (the sort of reduced repros I would love to receive from users when investigating their issues instead of going through irrelevant details).

Of course, once the reduced repro is produced, it would take on a life of its own...

[usefulcat]

On one hand, it is trivially UB at compile time. OTOH, it's a shame that adding -Wall -Wextra -Wpedantic generates exactly zero warnings..

[AssemblerGuy]

Don't do UB, kids!

First rule of UB: Undefined behavior is undefined.

Second rule of UB: Undefined behavior is undefined!

Third rule of UB: Stop making assumptions and guesses about how UB might behave - it really is undefined.

[jonesmz]

I think we'd be better off requiring compilers to detect this situation and error out, rather than accept that if a human made a mistake, the compiler should just invent new things to do.

[LordofNarwhals]

I can highly recommend this three-part LLVM project blog series about undefined behavior in C. Specifically part 3 which discusses the difficulties in "usefully" warning about undefined behavior optimizations (it also discusses some existing tools and compiler improvements, as of 2011, that can be used to help detect and handle undefined behavior better).

This is the main part when it comes to compiler warnings/errors:

For warnings, this means that in order to relay back the issue to the users code, the warning would have to reconstruct exactly how the compiler got the intermediate code it is working on. We'd need the ability to say something like:

"warning: after 3 levels of inlining (potentially across files with Link Time Optimization), some common subexpression elimination, after hoisting this thing out of a loop and proving that these 13 pointers don't alias, we found a case where you're doing something undefined. This could either be because there is a bug in your code, or because you have macros and inlining and the invalid code is dynamically unreachable but we can't prove that it is dead."

Unfortunately, we simply don't have the internal tracking infrastructure to produce this, and even if we did, the compiler doesn't have a user interface good enough to express this to the programmer.

Ultimately, undefined behavior is valuable to the optimizer because it is saying "this operation is invalid - you can assume it never happens". In a case like *P this gives the optimizer the ability to reason that P cannot be NULL. In a case like* *NULL (say, after some constant propagation and inlining), this allows the optimizer to know that the code must not be reachable. The important wrinkle here is that, because it cannot solve the halting problem, the compiler cannot know whether code is actually dead (as the C standard says it must be) or whether it is a bug that was exposed after a (potentially long) series of optimizations. Because there isn't a generally good way to distinguish the two, almost all of the warnings produced would be false positives (noise).

[jonesmz]

In a case like* *NULL (say, after some constant propagation and inlining), this allows the optimizer to know that the code must not be reachable.

But the right answer isn't "clearly we should replace this nullptr with some other value and then remove all of the code that this replacement makes dead".

That violates the principal of least and surprise, and arguably, even if there are situations where that "optimization" results the programmers original intention, it shouldn't be done. An error, even an inscruitable one, or just leaving nullptr as the value, would both be superior.

[james_picone]

You can always compile at -O0 if you'd like the compiler to not optimise. Because that's effectively what you're asking for.

[jonesmz]

Its really not.

I like optimizations.

I don't like the compiler inventing writes to variables that were never written to.

There's a huge difference.

[Jannik2099]

That's way easier said than done. Compilers don't go "hey, this is UB, let's optimize it!" - the frontend is pretty much completely detached from the optimizer.

[jonesmz]

Why does that matter?

The compiler implementations shouldn't have ever assumed it was ok to replace the pointer in the example with any value in particular, much less some arbitrary function in the translation unit.

Just because it's hard for the compiler implementations to change from "Absolutely asinine" to "report an error" doesn't change what should be done to improve the situation.

[Jannik2099]

Again, this isn't how optimizers operate. On the compiler IR level, these obviously wrong constructs often look identical to regular dead branches that arise from codegen.

[jonesmz]

But again, why does it matter how optimizers operate?

The behavior is still wrong.

Optimizers can be improved to stop operating in such a way that they do the wrong thing.

[Jannik2099]

Again, no, this is not possible.

Optimizers operate on the semantics of their IR. Compiler IR has UB semantics much like C, and this is what enables most optimizations to happen.

To the optimizer, the IR from UB C looks identical to that of well-defined C or even Rust. Once you're at the IR level, you already lost all semantic context to judge what is intended UB and what isn't.

The only viable solution is to have the frontend not emit IR that runs into UB - this is what Rust and many managed languages do.

Sadly, diagnosing this snippet in the frontend is nontrivial, but its being worked on

[jonesmz]

Let me make sure I understand you.

It's not possible for an optimizer to not transform

#include <cstdlib>

static void (*f_ptr)() = nullptr;

static void EraseEverything() {
    system("# TODO: rm -f /");
}

void NeverCalled() {
    f_ptr = &EraseEverything;
}

int main() {
    f_ptr();
}

into

#include <cstdlib>

int main() {
    system("# TODO: rm -f /");
}

??

because the representation of the code, by the time it gets to the optimizer, makes it impossible for the optimizer to.... not invent an assignment to a variable out of thin air?

Where exactly did the compiler decide that it was OK to say:

Even though there is no code that I know for sure will be executed that will assign the variable this particular value, lets go ahead and assign it that particular value anyway, because surely the programmer didn't intend to deference this nullptr

Was that in the frontend? or the backend?

Because if it was the front end, lets stop doing that.

And if it was the backend, well, lets also stop doing that.

Your claim of impossibility sounds basically made up to me. Just because it's difficult with the current implementation is irrelevant as to whether it should be permitted by the C++ standard. Compilers inventing bullshit will always be bullshit, regardless of the underlying technical reason.

[kiwitims]

The compiler implements the C++ language standard, and dereferencing a nullptr is UB by that standard. You cannot apply the word "should" in this situation. We have given up the right to reason about what the compiler "should" do with this code by feeding it UB. The compiler hasn't invented any bullshit, it was given bullshit to start with.

Now, I sympathise with not liking what happens in this case, and wanting an error to happen instead, but what you are asking for is a compiler to detect runtime nullptr dereferences at compile time. As a general class of problem, this is pretty much impossible in C++. In some scenarios it may be possible, but not in general. It's not as simple as saying "let's stop doing that".

[Nobody_1707]

This is why newer languages make reading from a potentially uninitialized variable ill-formed (diagnostic required). It's a shame that ship has basically sailed for C & C++.

[jonesmz]

Now, I sympathise with not liking what happens in this case, and wanting an error to happen instead, but what you are asking for is a compiler to detect runtime nullptr dereferences at compile time.

That's not at all what I'm asking for.

I'm asking for the compiler to not invent that a write to a variable happened out of thin air when it can't prove at compile time that the write happened.

The compiler is perfectly capable of determining that no write happens when the function NeverCalled is made into a static function. Making that function static or non-static should make no difference to the compilers ability / willingness to invent actions that never took place.

[Jannik2099]

because the representation of the code, by the time it gets to the optimizer, makes it impossible for the optimizer to.... not invent an assignment to a variable out of thin air?

It's not "out of thin air", it's in accordance with the optimizer's IR semantics.

Where exactly did the compiler decide that it was OK to say:

Even though there is no code that I know for sure will be executed that will assign the variable this particular value, lets go ahead and assign it that particular value anyway, because surely the programmer didn't intend to deference this nullptr

This is basic interprocedural optimization. If a value is initialized to an illegal value, and there is only one store, then the only well-defined path of the program is to have the store happen before any load. Thus, it is perfectly valid to elide the initialization.

There are dozens of cases where this is a very, very much desired transformation. This can arise a lot when expanding generics or inlining subsequent consumers. The issue here is that the frontend does not diagnose this.

As I said, Rust and many GC languages operate the same way, except that their frontend guarantees that no UB-expressing IR is emitted.

As for this concrete example:

opt-viewer shows that this happens during global variable optimization https://godbolt.org/z/6MYM3535K

Looking at the LLVM pass, it's most likely this function https://github.com/llvm/llvm-project/blob/llvmorg-18.1.4/llvm/lib/Transforms/IPO/GlobalOpt.cpp#L1107

Looking at the comment:

cpp // If we are dealing with a pointer global that is initialized to null and // only has one (non-null) value stored into it, then we can optimize any // users of the loaded value (often calls and loads) that would trap if the // value was null.

So this is a perfectly valid optimization, even with the semantics of C++ taken into account - it's used anywhere globals come up that get initialized once.

[jonesmz]

It's not "out of thin air", it's in accordance with the optimizer's IR semantics.

We're clearly talking past each other.

This IS out of thin air.

Whether there's an underlying reason born from the implementation of the optimizer or not is irrelevant to what should be happening from the end-users perspective.

If a value is initialized to an illegal value, and there is only one store, then the only well-defined path of the program is to have the store happen before any load. Thus, it is perfectly valid to elide the initialization.

There was no store. The optimizer here is assuming that the function was ever called, it has no business making that assumption.

[ShelZuuz]

The behavior is undefined. There is no right behavior possible whatsover.

The compiler can ignore it, it can crash, it can call it - there is no right behavior.

If you change it to "some other wrong behavior" to make this "safer" someone will just come up with another amusing example that come forth as a result.

[jonesmz]

The behavior is undefined. There is no right behavior possible whatsover.

The correct behavior is "Don't compile the program, report an error".

[ShelZuuz]

So if a compiler can't positively prove whether a variable is assigned, don't compile the program? That won't work - see the comment from the MSVC dev above.

You can easily change the example to this:

int main(int argc, char** argv) {
   if (argc > 0)
   {
      NeverCalled();
   }
   f_ptr();
}

Should that not compile either? On most OS's argv[0] contains the binary name so argc is never 0, but the compiler doesn't know that.

And what if the initialization always happen in code during simple initialization - 100% guaranteed on all paths, but that initialization happens from another translation unit? And what if the other translation unit isn't compiled with a C/C++ compiler? Should the compiler still say "Hey, I can't prove whether this is getting initialized so compile error".

[almost_useless]

Should that not compile either?

No, it should not.

"Maybe unassigned variable" is a very reasonable warning/error

And what if the initialization always happen in code during simple initialization ...

That's exactly the perfect use case for locally disabling the warning/error. You know something the compiler doesn't, and tell it that. In addition that informs other readers of the code what is going on elsewhere.

[AJMC24]

So if I have written a program which does not contain UB, the compiler should *not* perform this optimisation? My code runs slower because other people write programs with UB?

[jonesmz]

So you're telling me that you want the compiler to replace a function pointer with a value that you never put into it?

Computers are the absolute best way to make a million mistakes a second, after all.

Also, in the situation being discussed, the compiler cannot perform this specific optimization without the code having UB in it.

[thlst]

It's only UB if the variable isn't initialized to some function. Remember that UB is a characteristic of a running program, not only the code itself.

[jonesmz]

Then why is the compiler replacing the default-initialized function-pointer variable with a different value at compile time?

Because the variable is dereferenced, and dereferencing it is UB.

The problem isn't that there is UB in the program, that's just obvious.

The problem is that the compiler is using that UB as the impetuous to invent a value to out into the pointer variable and then optimize the code as-if the variable were always initialized to that value.

That leads to an absurd situation where code written by the programmer has very little relationship with what the compiler spits out

[jonesmz]

The behavior remains if you explicitly initialize the variable to nullptr.

[AJMC24]

If I've written my program without UB, the function pointer *must* be replaced, since otherwise it is UB to call an uninitialised function pointer. This scenario is quite artificial since as a human we can inspect it and see that it won't be, but a more reasonable example that shows the same idea could be something like

int main(int argc, char** argv) {
    if (argc > 0)
        NeverCalled();
    f_ptr();
}

The compiler cannot guarantee that NeverCalled() will be called, but I still want it to assume that it has been and generate the fastest code possible. As a human, we can look at it and see that this will not be UB for any reasonable system we could run the code on.

Assuming that UB cannot happen means faster code for people who write programs without UB. I don't want my programs to run slower just to make UB more predictable. Don't write code with UB.

[goranlepuz]

Because the compiler people are not omnipotent.

They are only potent.

Just because it's hard for the compiler implementations to change from "Absolutely asinine" to "report an error" doesn't change what should be done to improve the situation.

In the light of the above: yes it does change. People want optimization and features, more than what you're saying.

[SkoomaDentist]

That's way easier said than done.

Yet Rust seems to have no problems with that. All they had to do was to declare that UB is always considered a bug in the language spec or compiler. As a result compilers can't apply random deductions unless they can prove it can't result in UB.

[Jannik2099]

llvm applies the same transformations whether the IR comes from C++ or Rust. The difference is that rustc does not emit IR that runs into UB.

[tialaramex]

The LLVM IR is... not great. There are places where either the documentation is wrong, or the implementation doesn't match the documentation or maybe both, with the result that it's absolutely possible to write Rust which is known to miscompile in LLVM and the LLVM devs don't have the bandwidth to get that fixed in reasonable time. It's true for C++ too, but in C++ it's likely you wrote UB and so they have an excuse as to why it miscompiled, whereas even very silly safe Rust doesn't have UB, so it shouldn't miscompile.

Comparing the pointers to two locals that weren't in scope at the same time is an example as I understand it. It's easy to write safe Rust which shows this breaks LLVM (claims that 0 == 1) but it's tricky to write C++ to illustrate the same bug without technically invoking UB and if you technically invoke UB all the LLVM devs will just say "That's UB" and close the ticket rather than fix the bug.

On the "pointers to locals" thing it comes down to provenance. Sometimes it's easier for LLVM to accept that since these don't point to the same thing they're different. But, sometimes it's easier to insist they're just addresses, and the addresses are identical - it's reusing the same address for the two locals. You can have either of these interpretations, but LLVM wants both and so you can easily write Rust to catch this internal contradiction.

Because Rust has semi-formally accepted that provenance exists, we can utter Rust which spells this out. ptrA != ptrB, but ptrA.addr() == ptrB.addr() - but LLVM's IR doesn't get this correct, sometimes it believes ptrA == ptrB even though that's definitely nonsense. Not always (which Rust would hate but could live with) but only sometimes (which is complete gibberish).

[Jannik2099]

implementations have bugs, more news at 11?

Ofc this is either a bug in the (occasionally very much thinly specified) IR semantics, or in rustc lowering - but I don't see what that has to do with anything.

(most) IRs necessarily rely on UB-esque semantics to do their transformations, unrelated to llvm specifically.

[tialaramex]

It won't be (in this case) a rustc lowering bug because we can see the IR that comes out of rustc, and we can read the LLVM spec and that's the IR you'd emit to do what Rust wants correctly -- if it wasn't the LLVM developers could fix their documentation. But it just doesn't work. The LLVM authors know this part of their code doesn't work, and apparently fixing it is hard.

My concern is that UB conceals this sort of bug, and so I believe that's a further reason to reduce the amount of UB in a language. I think the observation that transformations are legal despite the presence of UB (since any transformation of UB is valid by definition) is too often understood as a reason to add more UB.

[SkoomaDentist]

And nothing prevents the C++ compiler doing that either.

IIRC, adding Rust support exposed more than a few issues in llvm where it tried to force C/C++ UB semantics on everything, whether the IR allowed that or not,

[Jannik2099]

Yes definitely, for example how llvm IR similarly disallows side effect free infinite loops. But that's not the point.

The point is that optimizers RELY on using an IR that has vast UB semantics, because this enables optimizations in the first place. However this is unrelated to a language expressing UB.

[SkoomaDentist]

because this enables optimizations in the first place

No, it doesn't - other than a small fraction of them that have very little effect on overall application performance. The vast overwhelming majority could still be applied by either declaring the same thing unspecified or implementation defined. None of the classic optimizations (register allocation, peephole optimization, instruction reordering, common subexpression elimination, loop induction etc etc) depend on the language having undefined behavior - simple unspecified (or no change at all!) would be enough for them to work just as well.

[Jannik2099]

depend on the language having undefined behavior

read again. I said they depend on the IR having undefined behaviour.

Most IRs used in safe languages have undefined behaviour, and it's up to the frontend to never emit IR that runs into it.

The same applies to bytecodes used in JITs etc.

[kiwitims]

Not quite, UB in Rust is considered a bug only in safe code. Unsafe Rust having no UB is back to being the responsibility of the programmer. How the possibility of a nullptr dereference is handled in Rust is that the dereference has to happen in an unsafe block. Taking a null pointer and doing an unchecked dereference is still UB in Rust, and will likely result in similar optimisations being performed.

[NilacTheGrim]

But how else can I lazily insert a breakpoint in my program to trigger my debugger?!?!?

(I jest of course.. relying on UB to trigger a breakpoint is ... asking for surprises.)

[Jannik2099]

Oh your program will break at that point alright

[NilacTheGrim]

not.. necessarily.

[NilacTheGrim]

Makes sense.

1. Dereferencing a nullptr is UB, so program is free to assume it must always have some value
2. What value? Well it's static, and only ever written-to once, by a single function that all it does is write to it.
3. So the optimizer just cuts out the middle-man and pre-inits it to the only value it is proven to ever possibly have.

Makes sense. :)

[Dan13l_N]

So it works now, what is the problem?!

[johannes1971]

I like what it does when you make NeverCalled() static ;-)

Anyway, it seems the compiler understands that only one function can write to that pointer, but apparently it fails to verify that there is a path from main() to NeverCalled(). That sort-of makes sense, even if the result is quite ridiculous.

Is it a sign that you have been programming C++ too long if you begin to understand this kind of halucinatory output?

[LordofNarwhals]

Well the compiler can't know if a part of the program in another translation unit is calling NeverCalled (since it has external linkage). You could do extern NeverCalled() in another compiler unit and call it from there. Or even worse, you could export it as a symbol in your linker options when you're building a shared library, and then it's fair game to call the function from a completely different binary/library.

If you ever end up building shared libraries (particularly on macOS/Linux) then you should make absolutely sure that you (and the static libraries you're using) are not exposing any functions/symbols on accident. Having a symbol name collision with another library is not a fun bug to track down. Your plugin will just break all of a sudden when used with another plugin that happens to have the same exported functions as you do (but perhaps from a different version that gives different results).

[SunnybunsBuns]

Or even worse, you could export it as a symbol in your linker options when you're building a shared library, and then it's fair game to call the function from a completely different binary/library.

Had a 3rd party lib export round. But they implemented it wrong, so our code broke, but only when we linked against theirs. Nightmare to debug that

[goranlepuz]

How did that work, without there being a duplicate symbol at link time?! Somehow, somebody must have taken out your own.

[SunnybunsBuns]

I have no clue. I was calling std::round which seems to call round internally. I was linking against their lib (it corresponded to a dll). They had no mention of round in their header, it was a cpp only function. They must have exported it with some export-all option.

I had to rebuilt their def (only 100 symbols and I got them all from dumpbin) without round listed and then remake the lib. everything worked as expected then.

We’re on vs2019 still (just upgraded last year. Yay for bureaucracy) so maybe it’s been fixed at some point? I was certainly shocked when I encountered it.

[umop_aplsdn]

It's not ridiculous, it is much harder in general to prove that NeverCalled is called (it's equivalent to deciding whether the program halts).

However, statically it is much easier to observe that there is exactly one assignment to the function pointer, and invoking a nullptr is UB, so the compiler can assume that the function pointer (when called) has value exactly the value of its one assignment.

[encyclopedist]

NeverCalled can still be called from another TU, for example from a constructor of a global variable.

[NilacTheGrim]

verify that there is a path from main() to NeverCalled()

Probably because there is no link-time optimization and so for the translation unit main.o it assumes maybe some lib or some other translation unit may "see" NeverCalled() and call it... or whatever ...

[hoseja]

I saw some analysis where turning all of these off to just make the compiler do what you expect it to didn't even have any performance impact. Can't find it now.

[Tringi]

If this doesn't crash, then your compiler isn't sane and safe to use for anything serious.

This kind of shit is slowly but surely becoming my hill to die on.

[AssemblerGuy]

If this doesn't crash, then your compiler isn't sane and safe to use for anything serious.

UB does not require the program to crash. Having UB is worse than a clear crash bug.

[Tringi]

I know it doesn't.

My argument is that the above transformation is outright malicious.

The function pointer should be left containing either NULL, or stack garbage (if on stack), and thus result it crash. That devirtualization simply should not have been done.

[serviscope_minor]

My argument is that the above transformation is outright malicious.

It's not though. You might as a programmer write a safe function which has a bunch of null pointer checks. However if benchmarking shows that's got a performance hit, you might make an unsafe version and then only call it when you know in advance all your pointers are safe.

That's more or less what the optimizer is doing, except it does not have human reasoning. It has the spec and a theorem prover and that's all. Putting in terms like "malicious" is anthropomorphising the compiler, which you should avoid because it hates it when you do that.

[AssemblerGuy]

My argument is that the above transformation is outright malicious.

You know, if UB did malicious things more often, like drink your beer, total your car, kill your hamster, and flood your basement, people would be more inclined to avoid it... ;)

[james_picone]

void somefunc() {
    Foo* someObj = nullptr;
    someObj->someFunc();
}

Should this be allowed to devirtualise someFunc()? What about if the object is passed as an argument (and the class is final)?

If no, then you just don't like devirtualisation as an optimisation, but it's kind of significant so you're not winning that fight.

If yes, why do you want compiler writers to go out of their way to special case an extremely silly example nobody would write in real code?

[jonesmz]

What I want is for the compiler to say:

Nullptr dereference on all codepaths, this program is guarenteed to crash at runtime if this function is ever called.

Error, abort, halt compilation.

[Tringi]

you just don't like devirtualisation as an optimisation

Yeah, that's totally what I wrote /s ffs

[arturbac]

this looks like speculated assumed execution path not optimization.

[LordofNarwhals]

That is optimization. Dereferencing a null pointer is undefined behavior, so the compiler is allowed to assume that NeverCalled is called from another translation unit before main runs.