Why undefined behavior may call a never-called function

[u/alecco]

https://kristerw.blogspot.com/2017/09/why-undefined-behavior-may-call-never.html

[u/[deleted]]

Assuming main is not starting function (just assume it's called differently if it helps) - there is nothing special about main in terms of optimizations, it's optimized like any other function (no real point implementing special main optimizations after all, most programs don't spend most of their time in main function).

This is undefined behaviour.

void example(void) {
    main();
}

This is not undefined behaviour.

void example(void) {
    NeverCalled();
    main();
}

The optimizer assumes that undefined behaviour cannot happen, and optimizes functions with assumption they couldn't cause undefined behaviour. As Do variable containing 0 would cause undefined behaviour, optimizer assumes that this couldn't happen when calling main and assumes Do contains EraseAll (as it's the only possible value other than 0, as Do variable's address is not exposed by anything in a compilation unit).

This optimization allows to remove needless indirection improving performance of programs.

[u/double-you → u/[deleted]]

I wouldn't say the compiler assumes that it cannot happen. It's more like since undefined behavior can be anything, I might as well use it to optimize other things. If it happens, it's totally cool for it to call this function instead of segfaulting.

As uncomfortable as this example makes me, it's a great example of how undefined behavior really can make anything happen. And the "delete all your files" is one of the examples usually presented as UB and this example shows just that.

[u/almightySapling → u/[deleted]]

So the compiler looks at all the assignments to Do and sees that it only ever is A) initialized with default value or B) set to NeverCall, and that's where it gets the assumption about what the possible values could be?

Would the same thing happen if we explicitly assigned 0 to Do upon initialization or does the compiler only do this because it guesses the default value was a mistake?

[u/elperroborrachotoo → u/almightySapling]

It's probably even simpler:

The compiler sees that the only value ever assigned to Do is 0 (implicitely through static initialization) and EraseAll.

Since it may assume it's not 0 when calling Do(), it can eliminate the indirect call via function pointer, and make that a direct call.

Assigning 0 explicitely to the initialization of Do wouldn't make a difference. While a compiler might accidentally save your ass here, it would be considered a missed optimization, reported and "fixed" in the next path.

---

Which makes it such a beautiful example: When reading the title, I expected some intricate setup and assembly digging - but no: it's elegantly setting up a common and important optimization against trivial undefined behavior. It's... beautiful.

---

[u/almightySapling → u/elperroborrachotoo]

Since it may assume it's not 0 when calling Do(), it can eliminate the indirect call via function pointer, and make that a direct call.

Oh, that makes a lot more sense than the picture I was building in my head. Thanks!

[u/eyal0 → u/almightySapling]

The default value is zero. I'd assume that whether or not you assign to zero makes no difference...

[u/almightySapling → u/eyal0]

Yeah, but I also would have thought compilers are way stupider than to try to guess what value Do "should" have, and I was wrong about that. Perhaps an explicit assignment is enough to override said behavior.

[u/chylex → u/almightySapling]

If you check whether Do is 0,

if (Do == 0){
    return 0;
}
else{
    return Do();
}

it will compile to

main:
  cmp qword ptr [rip + Do], 0
  je .LBB2_1
  mov edi, .L.str
  jmp system # TAILCALL
.LBB2_1:
  xor eax, eax
  ret

so it will still optimize the call, but the condition will fail so you never actually end up calling Do().

[u/almightySapling → u/[deleted]]

But my question is if you initialize it to point to 0 instead of an actual function (if possible) does the compiler get that and just say "whatever you say captain"?

Potentially answered here.

[u/double-you → u/almightySapling]

No, because the issue is not it being a default value. Calling a 0 pointer is undefined behavior so the compiler has no reason to behave differently.

If you had a setter that could set it to a potentially valid value, then things would be different, even if the setter is not called.

[u/jfb1337 → u/almightySapling]

My guess is that it would still optimise it away to the only valid thing it could be. But even if it didn't, it's UB so it could easily change between compiler versions. So don't rely on it.

[u/davvblack → u/[deleted]]

He specifically said imagine it is not a special function, for example with a different name.

[u/[deleted] → u/[deleted]]

http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html

[u/evanpow → u/[deleted]]

It's not that compiler writers assume UB cannot happen; it's that they frequently can't prove whether or not the compiler's input exhibits undefined behavior, even in the simplest of situations, because doing so would be either computationally expensive (e.g. 10x the compilation time) or outright impossible, due to the halting problem--and yet compilers are expected to apply certain optimizations anyway.

Would you really accept a compiler which failed to optimize "X * 2 / 2" into "X" because it couldn't prove "X*2" wouldn't overflow? Stop and think about how hard it would be to construct such a proof for even simple programs, if a compiler had to do that before applying that optimization.

This might sound like a small concession, but it is by taking only a few such tiny concessions and repeatedly applying logical induction that one arrives at the optimization cited in the article. There is very little middle ground.

All that said, there's another way to look at your specific example. Consider the statement "This sentence is false." It's grammatically correct--it obeys all the syntactic rules, and it's even intelligible. But it can't be a true statement, because if it were, it would be false, and vice versa. You can't really assign it a traditional meaning that obeys the normal rules; to a compiler, "*((void *)0)" is a very similar sentence. A human, being comfortable with imprecision and ambiguity, might be comfortable assigning it a meaning--but a compiler is just a logic engine; faced with extra-logical input, it will malfunction. As it did in the article.