So, the compiler finds out that the function pointer Do is either undefined or points to EraseAll, and since calling an undefined function is undefined behavior, the compiler assumes that 'Do' always points to EraseAll?
Is this what is happening?
While this is certainly unexpected, I can't fault the compiler here. The example emphasizes the need for tools to check for undefined behavior.
The undefined behavior is that the static variable "Do" (a function pointer) is used without initialization. The compiler optimization is that since, in the whole program, the only value to ever be assigned to "Do" is the function "EraseAll", the compiler statically initializes "Do" to "EraseAll". Doesn't seem too crazy.
Actually the optimization is not statically initializing Do, it is inlining the function calls via the Do pointer. I actually think this a quite useful optimization.
You can see that if you "fix" the program by checking Do before calling it, it still inlines the call in the True branch:
Of course, in some cases NULL checks will be optimized out (this is why GCC has acquired the -fno-delete-null-pointer-checks flag ...). At one point, this has been a huge source of conflict: basically, when you have something like
if (NULL != s)
{
s->a = 1;
}
s->b = 1;
then GCC may optimize away the NULL check because referring to s->b after the block protected by the NULL check indicates that the NULL check is superfluous. I this case, this is actually true, but in cases that involve aliasing that is not detected by dataflow analysis, there might be circumstances where the NULL check is required. Discussion of something related is here[0]; my example might not be very good.
An even more insidious case is [1](strong language), where manual overflow checks are optimized out because the overflow technically invokes UB.
If you rename "NeverCalled" to "Initialize" and "main" to "ExecuteAfterInitialization", the behavior is much less mysterious.
NeverCalled is a "public" function since it isn't marked static, so the author of this code intended for it to be called externally to initialize Do.
The compiler's optimization produces a correct program along the only valid execution path: Compile this as an object file, and link it with some other code that calls NeverCalled and then main.
If you mark NeverCalled as static, the compiler outputs an explicit "Undefined Instruction", because there are then no execution paths that don't invoke undefined behavior.
It's not creative or guessing. If you write a function without "static" it means you intended for it to be called externally.
It's not theoretical at all: Before I saw this thread, I was in the middle of writing some Haskell that loads some non-main symbols from an object file derived from an executable's source code, and invokes them. People carefully mark which functions are or are not static to ensure their executables don't get bloated. I'd be very annoyed if my C compiler didn't take symbol visibility into account when optimizing, because I depend on it all the time.
If I write a function without "static" it means I want to allow functions in other modules module to call it, it isn't implied that it will be actually called.
Real life analogy: declaring a static function is like locking your car because you don't want it stolen: only hackers can access it through forbidden means.
If instead you leave your nonstatic car parked in the street, open and with keys in the ignition, you are making it easy to steal (probably you want it to be stolen, there might be an UB corpse in the trunk you want to get rid of), but you cannot be sure that a thief will actually come along and take it away; you are just advertising that they should.
This is a technically correct compilation of the given C program. All executions of a program containing undefined behavior are invalid. That means, not just the part of execution "after" the undefined behavior, but the part of execution "before" as well.
Since the program unconditionally calls an uninitialized (actually zero-initialized) function pointer, that is undefined behavior. It therefore has no valid executions. The compiler is legally allowed to generate whatever code it wants, and that is considered valid according to the standard. It just so happens in this case that it probably generated no code at all for main, falling through to code that it did generate. (and my guess as to why it did generate code for NeverCalled() is because it's non-static and could be called by functions outside this compilation unit; NeverCalled keeps EraseAll() alive.)
edit: the above is only true if the compiler knows main is the entrypoint to the program.
No, if you try this with the various optimization levels you can see that it's not a bug; without optimization it doesn't happen. Instead what seems plausible to me is that some optimization pass analyses the possible values for "Do", which is tractable, since it's static and can't be aliased. Because the value must be initialized before Do() the optimizer seems to unconditionally use the only possible initialization, even if it is unreachable.
With -O1 you can see that this part already happens. With optimization cranked further up it just inlines EraseAll, and EraseAll ceases to exist as a separate symbol. This is possible since Do is static and not aliased. Meanwhile NeverCalled continues to exist as a retq, since it is not static.
I've seen plenty of people blame the optimizer for bugs in their code. This is especially common with people doing embedded stuff when they don't understand the "volatile" keyword. Just because it works without optimization doesn't mean your code is correct.
Some of them will insist on not using the optimizer because it can introduce bugs. I take the opposite attitude - let's go with -o3 from day one because we'll eventually run out of CPU time and have to turn it on anyway. If that uncovers bugs in the code or compiler it's better to find them early.
I don't think compilers know that main() is really the entrypoint, since there is some code in the C runtime that runs before main. If compilers treated main like the program entrypoint, then my original comment would stand.
That is a cop-out, and entirely useless definition of "correct".
Why don't we call that what the compiler emits when it encounters undefined behavior not "correct" but "invalid" or "wrong"? It's a matter of changing the terms to not overload "correct". The compiler is free to output "invalid" code on "invalid" input - garbage in, garbage out. But to use the term "correct" is silly.
Going a bit further, I believe a compiler has the right to do sensible things with undefined behavior. I greatly prefer it to do the obvious thing, when it can't do the correct thing.
In this case, try to execute the function at the address given by Do; since Do is uninitialized just use the number already in memory at Do's location as an address. I would also not be surprised if it initializes it with 0, and places EraseAll at 0x00, and thus calls EraseAll (although I know that address spaces on modern computers do not work like that).
In reality, I would expect the program to crash most of the time with an access violation, rarely with an invalid opcode, and extremely rarely call one of the functions (when Do contains that address by chance).
> since Do is uninitialized just use the number already in memory at Do's location as an address.
But the compiler has full control over that memory, and it's faster when the number is the same as what might eventually be written into it, but then you no longer need to write anything, since that value is already in memory, and now it's a constant and why keep a constant in memory when you can just inline it ...
All of the steps are completely intuitive and a compiler capable of executing them is much better than one that just indiscriminately zeros all memory and never dares to optimize anything to avoid exposing someone's mistakes.
The best a compiler can do in the face of guaranteed undefined behavior is to warn the programmer and tell them to fix their code. Unfortunately, C makes it quite difficult to distinguish between defensively-written code that avoids UB, and code that treats C like a portable assembler, that will do the "obvious" (but slow) thing.
Noting that your parent only used the word "correct" in the phrase "correct compilation"...
> The compiler is free to output "invalid" code on "invalid" input
... you are actually agreeing with your parent. Maybe they should have said "legal compilation" instead of "correct compilation".
You seem to be saying that your parent said "the resulting assembly program is a correct program", which is silly. We cannot talk about its correctness, as there is no specification to judge correctness against (or the source program already doesn't satisfy the specification, in which case the compiler cannot help and should never even be called before fixing the bug).
I'm agreeing with the parent that the result is according to the spec.
What I'm arguing is that we shouldn't call that a correct compilation. It is a wrong compilation - is wrong with prior notice, and there is in fact no way to do it right, because the source is wrong (UB).
I think I don't disagree about behavior, but about semantics. We shouldn't say, e.g. in a compiler's manual, that the compiler is free to (has the right to, is correct to) do anything when it encounters UB. Rather, I'd warn that the compilation might fail silenty on UB.
The difference is not factual, it is in tone. Stating matter-of-factly that nasal demons is the correct result of compiling UB code is aggravating. It is the equivalent of the compiler singing nana-nana-na-na (or ätsch bätsch for the Germans).
> Rather, I'd warn that the compilation might fail silenty on UB.
What do you mean by "fail"? Terminate compilation without producing output code? That's not possible, the compiler cannot detect all (or even most) UB at compilation time. Or do you mean it would produce "wrong" code (as it does now)? That's not what is commonly called "failure", and I think putting it that way is obscuring the issue, not making it clearer.
You're acting as if a compiler behaving reasonably is impossible. Yet Java compiles to code that runs basically as fast as C (modulo cases like where you use vectorised code in C and the JIT fails to auto-vectorise), but with rational and predictable behaviour in all cases.
I suspect UB is going to seriously damage or largely kill off statically compiled languages in the long run. Speculating JIT compilers can compile code in such a way that all executions are defined yet which does not experience the speed penalty C programs suffer, because the optimiser is free to make risky assumptions that are checked on the fly and de-optimise if they fail. It's heavy to have a full blown compiler running at the same time as your app, but desktop/laptop machines tend to have spare cores doing nothing anyway, and on servers the compiler is only running for a short period during warmup anyway and then is hardly used again.
You can get pretty good safety-performance trade-offs even without JITting, but yes, JITs are also great. But all that is only true for languages that are less insane than C, I agree. (Come to think of it, I don't know if people have explored the field of UBSan-style things in combination with JIT technologies.)
As for a "reasonable" C compiler, there is always -O0.
> It therefore has no valid executions. The compiler is legally allowed to generate whatever code it wants
If the compiler concludes that the program has no valid executions, then why not just generate an error message at compile time?
I wonder in what other engineering disciplines this kind of attitude (i.e. silently punishing users for mistakes by generating arbitrarily misbehaving code) is considered acceptable. It seems unethical to me. Perhaps compiler writers should think more about what constitutes sound engineering, rather than what happens to be permitted by The Standard.
> If the compiler concludes that the program has no valid executions, then why not just generate an error message at compile time?
I agree that that would be nice to see in this case, and it seems like this particular case would be low-hanging fruit, but it's not that simple. In particular, the compiler in this example most likely does not reason globally; it never actually decides that "the program has no valid executions". It does a series of local transformations, presumably based on facts of the form "if we can reach this point, then certain values are invalid".
Another thing about such error messages would be that they would push compilers more in the direction of verification tools, which they aren't, and cannot be.
Consider:
int f() {
return 1 / 0;
}
int g() {
int a = 0;
return 1 / a;
}
Clang warns about the first function, but not about the second one. If it warned about the second one, I could write a third function that always divided by zero, but that it could not warn about. If it learned to do that, I would find a fourth one, etc. This is an arms race that compilers cannot win, and they shouldn't try. You should use separate verification tools for that, which do the opposite of compiler warnings: They don't reject the program if it's trivially buggy, they reject it unless you prove that it is not buggy.
If compilers had more such warnings, programmers would be tempted to say "look, there is no warning, the code must be fine". That's the whole "if it compiles, it's correct" approach that gives some gullible people a false sense of security in other languages.
I certainly hope that there are not many programmers thinking "if it compiles, it's correct" after having made their first logic error, though I realize some Haskell programmers make statements that are close to that.
Clang and gcc will warn you about some of these issues if you give them the right flags (so much so that -Wall no longer means literally all warnings, IIRC), but then you run into static analysis' problem of burying you in false positives for conditional / data-dependent undefined behavior.
I have found it instructive to play with Dafny, one of the languages where the compiler does require you to prove that a variety of bugs will not occur, but 'play' is the operative word here. It is not a feasible option for C.
C has always been a language for (among other things) creating optimized code, but the implication of that has changed. Originally, it meant / required being 'close to the metal', but since then, effective automated optimization has come along, and the metal itself has become considerably more complicated (partly as a consequence of more capable optimization). As C programmers, we should understand that these changes have occurred, and what they mean for programming in C - or not use the optimizer.
> I certainly hope that there are not many programmers thinking "if it compiles, it's correct" after having made their first logic error, though I realize some Haskell programmers make statements that are close to that.
No, the Haskell slogan is "If it compiles it works". "It works" is something quite different to "it is correct".
You talk about compilers in the general case but UB causing pain like this is really a C and C++ phenomenon. Other compiled languages manage to have sane compilation strategies.
The really strange this is: there's probably tons of places that the compiler takes advantage of undefined behaviour, and nobody notices, and in fact is grateful of the magic speed improvement that comes for free simply from adding -O3 or whatever. And these are then used to justify the undefined behaviour that people find slightly mystifying, or that cause actual problems in practice (interestingly these always seem to be related, as in this case, to things that can be statically proven to have NULL-related undefined behaviour). But why not treat these two cases differently?
Why do you assume it's so easy for the compiler to tell the difference between the two cases?
From this optimization pass's perspective, it has proved that in a legal program `Do` can only have one possible value, and simplified the code appropriately. Most of the time this sort of optimization is correct and the programmer wants it; how is it supposed to figure out that this time the programmer had some different semantics in mind?
Oh, I totally agree. The history of C++ is basically a long argument between compiler writers and language designers, with the compiler writers inventing new optimizations which violate language semantics, a fight ensuing, undefined behavior somehow entering the equation, and then the language designers lose the argument, and the spec is changed.
E.g. one justification given for signed integer overflow being undefined behavior is so that compilers are legally permitted to optimize "(a + k) < (b + k)" to "a < b", which is not correct in the case of overflow.
I agree that the generated code is leagal wrt. the standard and that code for NeverCalled is generated because it is visible outside the translation unit.
However, to me it looks as if the assembly contains code for main (label main: is present) and EraseAll got inlined into main. This seems reasonable once you believe that the compiler can, due to undefined behavior, assume DO to be EraseAll.
You can't be sure, that's just what one compiler does today. Static analysis tools tend to refer to the standard.
$ tis-analyzer foo.c -val
/tmp/foo.c:16:[kernel] warning: Function pointer and pointed function have incompatible types.
Pointer type: int ()
Non-function: {0}
assert \valid_function(Do);
....
/tmp/foo.c:16:[value] Assertion 'Value,function_pointer' got final status invalid.
What worries me is that almost every other compiler supported by godbolt would wipe your drive. It's not an anomaly of Clang - it's something fundamentally wrong in the design of compilers that allows them to do this at right optimization levels.
Which means that if I have a method that wipes my entire production database but never ever call it, it might still get called because of mistake like this one where someone forgot to initialize a function pointer.
>> Which means that if I have a method that wipes my entire production database but never ever call it, it might still get called because of mistake like this one where someone forgot to initialize a function pointer.
Do you actually have a method like that? Somehow I doubt it. Also, the example is completely contrived. If you have an uninitialized function pointer it's going to be pretty uncommon that there's only one possible function for the compiler to conclude is the right one. Also, you should not be testing on a production system.
On a note related to your example, many automotive ECUs have the ability to re-flash over the vehicle network. In many cases the OEM requires that they do not contain any code to erase or program their own flash memory. This is for the reason you cite - if somehow (for whatever reason) that code were to execute it may brick that device. This then requires that the bootloader download a couple functions to RAM prior to updating its own code - those functions are the ones that erase and write flash. This is also convenient for some micro controllers that can't modify flash while code is being executed from it.
If you have a method that wipes your entire production database, and have a function pointer that is only ever set to point to that function, and you call it ... then what made you think it wouldn't wipe the production database? It's the only thing it could possibly do.
There are optimizations that can bite you when you thought you were doing everything right, but misunderstood undefined behavior. This is not such a case. If you write that kind of code, wiping your database is letting you off easy.
I would hope none, since no static analysis tool can make that assumption without knowing the exact compiler you're thinking about and a great deal else.
This is not the "expected" behavior; undefined behavior doesn't have an expected behavior. This is what the compiler at godbolt.com happens to generate for this particular code.
At best, an analysis tool can warn that the code has undefined behavior.
I just read the C++ Primer because I wanted to hack on some C++ code and the number of things you can do in C or C++ that result in "undefined behavior" is annoyingly large. There are some functions where they could have added a bounds check to the implementation, but the whole philosophy of the language seems to be that when choosing between lack of bult-in checks that would lead to easy to make errors that would cause undefined behavior and small speed increases on microbenchmarks the language designers choose the latter.
For what it's worth, in Design and Evolution of C++, Stroustrup says that when he was designing features, he would often think of a simple rule that he couldn't enforce (e.g., "couldn't enforce" being "if you violate this rule, the results are undefined") and a complex rule that he could enforce. He generally tried to pick the simpler, easier to teach rule. Unfortunately, that means there's more undefined behavior if those simpler rules are violated.
If we want zero-overhead abstraction (i.e. don't generate null checks in front of every division, etc.) and a (reasonably) safe language, more static analysis is in order.
The case in point is Rust: Its type system is basically an elaborate static analysis.
Rusts advantage over tools like UBsan is that the programmer expects to interact with the type system. Many static analysis tools get rejected by programmers, because the expectation is that they "just work", when really one needs to interact with such a tool. This means bidirectional communication: The programmer tells the tool what invariant he wants to get, and the tool tells the programmer which invariants it is missing.
It might be what you expect for that particular compiler, but there's no guarantee. A different compiler might decide that because `Do` has only two possible values, that it should replace the dynamic function call with an if condition deciding between two static function calls like I did here manually, to trigger the bug again: https://godbolt.org/g/kWcvvb
What kind of optimization? I'd rather this kind of code would crash on me, like the code that gcc compiles out of this, rather than compiler silently doing crazy inferences out of obviously buggy code.
For this particular edge case, yes it seems absurd. However, many optimization passes are based on simplifying code by figuring out what range of values something can take.
Most optimization passes don't know what the original code looks like, they only see it after it's been passed through a bunch of other optimization passes and preprocessing, so they can't reason about whether a particular optimization would seem "completely natural" or "abuse of UB" to the original programmer.
Do compilers emit warnings here (do they usually do that when there is a known UB?)
Here it's clear that "NeverCalled" is never called so it's clear that Do is never assigned, so the Call can't produce anything useful.
EDIT: Ugh missed the lack of "static" on the NeverCalled. Never mind.
Is this too hard to decide with certainty in C because of how you could do some pointer gymnastics and just fiddle with the field without the compiler realizing, so in order not to spit out false positives, compilers just have to assume the author knows what he's doing and allow the suspected UB without warning?
I'm just used to higher level "safe" languages (Rust, C#, etc), where lack of assignment is usually determined with certainty.
"Here it's clear that "NeverCalled" is never called so it's clear that Do is never assigned."
I don't think that is clear. If the given file is linked with another file that initializes a static variable with a function that calls NeverCalled, the initialization will be done before main is called, and so NeverCalled will be called. The compiler can't tell from just analysing the one file shown here whether or not NeverCalled is called.
Right. I missed that the uncalled function was public. So the issue is not clear until you link I suppose, so only detected "globally" whether the function is called. is it fair to say that that kind of global analysis is rare in the compiler+linker toolchain world for C, and usually left to static analyzers instead?
> The compiler can't tell from just analysing the one file shown here whether or not NeverCalled is called.
Right, and making it static you get the -Wunused-function. Great.
This warning is about the NeverCalled function being unused though, and not about Do being unassigned before it's called. Curious, is there any way to get a warning for this? This is UB, correct? And the assignment is now known not to happen?
typedef int (*Function)();
static Function Do;
void main() { Do(); }
> another file that initializes a static variable with a function that calls NeverCalled
How would that work in actual code? Static initialization must be done with constant expressions. C++ has constexpr functions, but they cannot call NeverCalled unless it is also marked constexpr, can they?
With clang you can enable run time UB checks using the -fsanitize=undefined flag[0]. But in this case, the sanitizer doesn't detect undefined behavior.
I tried to build the example (and changing the system to an echo) using "clang a.cpp -o a -Os -std=c++11 -lstdc++ -fsanitize=undefined", but the sanitizer didn't detect the UB.
Isn't this because the sanitizer works with the instrumented "optimized" code, which does no longer invoke UB? Or is the clang toolchain intelligent enough to not perform UB dependent optimizations when the sanitizer is specified?
What would it even mean for compiled, machine language code to invoke UB or not?
UB is mostly a C concept, not a lower-level one. The semantics of assembly language programs are well-defined much more often (the only counterexample I can think of is stuff involving using threading, memory barriers, etc. incorrect)
That's mostly a cosmetic warning. If you add a prototype for NeverCalled() at the top of the file, it silences the warning, but Clang still emits the same code.
This example is C++, not C. Clang is complaining because it's good practice to declare a prototype for a non-static function (in a header file) before using or declaring the function itself, so it can't accidentally be used with the wrong parameter list in a different compilation unit. It will produce this warning if you have () or (void) as the parameter list.
If an object that has automatic storage duration is not initialized explicitly, its value is indeterminate. If an object that has static or thread storage duration is not initialized explicitly, then:
— if it has pointer type, it is initialized to a null pointer;
>Variables with static storage duration (3.7.1) or thread storage duration (3.7.2) shall be zero-initialized (8.5) before any other initialization takes place
and from 8.5:
>To zero-initialize an object or reference of type T means
>--if T is a scalar type (3.9), the object is initialized to the value obtained by converting the integer literal 0 (zero) to T
and from 3.9:
>Arithmetic types (3.9.1), enumeration types, pointer types, pointer to member types (3.9.2), std::nullptr_- t, and cv-qualified versions of these types (3.9.3) are collectively called scalar types
It's a global static without an initializing expression; it is set to 0 before main() starts. 0 for a function pointer is of course the same as nullptr/NULL.
Compilers (and thus, compiler writers, i.e., people) have gone off the deep end with C. In search of endless over-optimization (don't worry, they will tell you that this optimization is "important" because some stupid benchmark runs 21% faster), programmer intent (as well as mistakes) are turned into bizarro behavior. Why we accept this is beyond me. For C, in particular, it has made writing code that uses plain old C ints way more challenging than it needs to be, among other things. We need to rethink what is important: a little more performance, or representing (to our best possible guess) what the programmer actually intended. </rant>
> We need to rethink what is important: a little more performance, or representing (to our best possible guess) what the programmer actually intended.
I remember reading an old book about implementing a compiler. The book actually recommended that compilers should make an effort to fix simple mistakes; e.g., compilers should add semicolons if needed, check whether an undefined variable or function was actually a misspelled variable or function, etc. I wasn't sure whether I should laugh at the naivety or shudder about what kind of code that would have led to. Especially given that each compiler would be lenient in different ways from competing compilers.
> representing (to our best possible guess) what the programmer actually intended.
If the programmer intended to write a correct program, and the programmer wrote an undefined program instead, you should blame the programmer, not the compiler.
Do you have an example of an optimization pass you would turn off in Clang?
I mean, do you actually know which one you'd turn off and what the pros and cons are. Not just answer like "of course, whichever one caused this behavior!"
I'm asking because I noticed nobody who rants about compiler behavior on UB code actually seems to have a detailed understanding of what they're talking about. They always seem to just be shooting from the hip.
So, the compiler finds out that the function pointer Do is either undefined or points to EraseAll, and since calling an undefined function is undefined behavior, the compiler assumes that 'Do' always points to EraseAll?
Is this what is happening?
While this is certainly unexpected, I can't fault the compiler here. The example emphasizes the need for tools to check for undefined behavior.
The undefined behavior is that the static variable "Do" (a function pointer) is used without initialization. The compiler optimization is that since, in the whole program, the only value to ever be assigned to "Do" is the function "EraseAll", the compiler statically initializes "Do" to "EraseAll". Doesn't seem too crazy.
Actually the optimization is not statically initializing Do, it is inlining the function calls via the Do pointer. I actually think this a quite useful optimization.
You can see that if you "fix" the program by checking Do before calling it, it still inlines the call in the True branch:
https://godbolt.org/g/9KS2r9
Of course, in some cases NULL checks will be optimized out (this is why GCC has acquired the -fno-delete-null-pointer-checks flag ...). At one point, this has been a huge source of conflict: basically, when you have something like
if (NULL != s) { s->a = 1; }
s->b = 1;
then GCC may optimize away the NULL check because referring to s->b after the block protected by the NULL check indicates that the NULL check is superfluous. I this case, this is actually true, but in cases that involve aliasing that is not detected by dataflow analysis, there might be circumstances where the NULL check is required. Discussion of something related is here[0]; my example might not be very good.
An even more insidious case is [1](strong language), where manual overflow checks are optimized out because the overflow technically invokes UB.
Compiler optimization gone wild.
[0] https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71892 [1] https://gcc.gnu.org/bugzilla/show_bug.cgi?id=30475
Your example also presents undefined behaviour, so the compiler is free to do whatever it wants.
That's like saying "You used the power drill incorrectly, so it's free to explode and burn your house down."
At some point safety matters, and the more likely human mistakes matter.
Static variables are implicitly initialized with zero if there is no explicit initialization.
If you rename "NeverCalled" to "Initialize" and "main" to "ExecuteAfterInitialization", the behavior is much less mysterious.
NeverCalled is a "public" function since it isn't marked static, so the author of this code intended for it to be called externally to initialize Do.
The compiler's optimization produces a correct program along the only valid execution path: Compile this as an object file, and link it with some other code that calls NeverCalled and then main.
If you mark NeverCalled as static, the compiler outputs an explicit "Undefined Instruction", because there are then no execution paths that don't invoke undefined behavior.
No, there is no valid execution path because of undefined behaviour. It doesn't cease to be undefined because of imaginary additional code.
Compilers are not in the business of creatively guessing what "the author of this code intended".
It's not creative or guessing. If you write a function without "static" it means you intended for it to be called externally.
It's not theoretical at all: Before I saw this thread, I was in the middle of writing some Haskell that loads some non-main symbols from an object file derived from an executable's source code, and invokes them. People carefully mark which functions are or are not static to ensure their executables don't get bloated. I'd be very annoyed if my C compiler didn't take symbol visibility into account when optimizing, because I depend on it all the time.
If I write a function without "static" it means I want to allow functions in other modules module to call it, it isn't implied that it will be actually called.
Real life analogy: declaring a static function is like locking your car because you don't want it stolen: only hackers can access it through forbidden means. If instead you leave your nonstatic car parked in the street, open and with keys in the ignition, you are making it easy to steal (probably you want it to be stolen, there might be an UB corpse in the trunk you want to get rid of), but you cannot be sure that a thief will actually come along and take it away; you are just advertising that they should.
This is a technically correct compilation of the given C program. All executions of a program containing undefined behavior are invalid. That means, not just the part of execution "after" the undefined behavior, but the part of execution "before" as well.
Since the program unconditionally calls an uninitialized (actually zero-initialized) function pointer, that is undefined behavior. It therefore has no valid executions. The compiler is legally allowed to generate whatever code it wants, and that is considered valid according to the standard. It just so happens in this case that it probably generated no code at all for main, falling through to code that it did generate. (and my guess as to why it did generate code for NeverCalled() is because it's non-static and could be called by functions outside this compilation unit; NeverCalled keeps EraseAll() alive.)
edit: the above is only true if the compiler knows main is the entrypoint to the program.
No, if you try this with the various optimization levels you can see that it's not a bug; without optimization it doesn't happen. Instead what seems plausible to me is that some optimization pass analyses the possible values for "Do", which is tractable, since it's static and can't be aliased. Because the value must be initialized before Do() the optimizer seems to unconditionally use the only possible initialization, even if it is unreachable.
With -O1 you can see that this part already happens. With optimization cranked further up it just inlines EraseAll, and EraseAll ceases to exist as a separate symbol. This is possible since Do is static and not aliased. Meanwhile NeverCalled continues to exist as a retq, since it is not static.
> it's not a bug
It's not a bug in what? The compiler or the input program? [The answer is, the compiler is fine, the input program has undefined behavior.]
> without optimization it doesn't happen
That's fine. As the input program has undefined behavior, the compiler is free to compile it differently at different optimization levels.
I've seen plenty of people blame the optimizer for bugs in their code. This is especially common with people doing embedded stuff when they don't understand the "volatile" keyword. Just because it works without optimization doesn't mean your code is correct.
Some of them will insist on not using the optimizer because it can introduce bugs. I take the opposite attitude - let's go with -o3 from day one because we'll eventually run out of CPU time and have to turn it on anyway. If that uncovers bugs in the code or compiler it's better to find them early.
Sorry, you are right.
I don't think compilers know that main() is really the entrypoint, since there is some code in the C runtime that runs before main. If compilers treated main like the program entrypoint, then my original comment would stand.
> I don't think compilers know that main() is really the entrypoint
Yes they do.
> since there is some code in the C runtime that runs before main
So? From the point of view of the C standard, main is the entrypoint to the C code in the program the compiler is asked to compile.
(Edited to add: This particular example program is in C++, but whatever.)
That is a cop-out, and entirely useless definition of "correct".
Why don't we call that what the compiler emits when it encounters undefined behavior not "correct" but "invalid" or "wrong"? It's a matter of changing the terms to not overload "correct". The compiler is free to output "invalid" code on "invalid" input - garbage in, garbage out. But to use the term "correct" is silly.
Going a bit further, I believe a compiler has the right to do sensible things with undefined behavior. I greatly prefer it to do the obvious thing, when it can't do the correct thing.
In this case, try to execute the function at the address given by Do; since Do is uninitialized just use the number already in memory at Do's location as an address. I would also not be surprised if it initializes it with 0, and places EraseAll at 0x00, and thus calls EraseAll (although I know that address spaces on modern computers do not work like that).
In reality, I would expect the program to crash most of the time with an access violation, rarely with an invalid opcode, and extremely rarely call one of the functions (when Do contains that address by chance).
> since Do is uninitialized just use the number already in memory at Do's location as an address.
But the compiler has full control over that memory, and it's faster when the number is the same as what might eventually be written into it, but then you no longer need to write anything, since that value is already in memory, and now it's a constant and why keep a constant in memory when you can just inline it ...
All of the steps are completely intuitive and a compiler capable of executing them is much better than one that just indiscriminately zeros all memory and never dares to optimize anything to avoid exposing someone's mistakes.
The best a compiler can do in the face of guaranteed undefined behavior is to warn the programmer and tell them to fix their code. Unfortunately, C makes it quite difficult to distinguish between defensively-written code that avoids UB, and code that treats C like a portable assembler, that will do the "obvious" (but slow) thing.
> useless definition of "correct".
Noting that your parent only used the word "correct" in the phrase "correct compilation"...
> The compiler is free to output "invalid" code on "invalid" input
... you are actually agreeing with your parent. Maybe they should have said "legal compilation" instead of "correct compilation".
You seem to be saying that your parent said "the resulting assembly program is a correct program", which is silly. We cannot talk about its correctness, as there is no specification to judge correctness against (or the source program already doesn't satisfy the specification, in which case the compiler cannot help and should never even be called before fixing the bug).
I'm agreeing with the parent that the result is according to the spec.
What I'm arguing is that we shouldn't call that a correct compilation. It is a wrong compilation - is wrong with prior notice, and there is in fact no way to do it right, because the source is wrong (UB).
I think I don't disagree about behavior, but about semantics. We shouldn't say, e.g. in a compiler's manual, that the compiler is free to (has the right to, is correct to) do anything when it encounters UB. Rather, I'd warn that the compilation might fail silenty on UB.
The difference is not factual, it is in tone. Stating matter-of-factly that nasal demons is the correct result of compiling UB code is aggravating. It is the equivalent of the compiler singing nana-nana-na-na (or ätsch bätsch for the Germans).
> Rather, I'd warn that the compilation might fail silenty on UB.
What do you mean by "fail"? Terminate compilation without producing output code? That's not possible, the compiler cannot detect all (or even most) UB at compilation time. Or do you mean it would produce "wrong" code (as it does now)? That's not what is commonly called "failure", and I think putting it that way is obscuring the issue, not making it clearer.
You're acting as if a compiler behaving reasonably is impossible. Yet Java compiles to code that runs basically as fast as C (modulo cases like where you use vectorised code in C and the JIT fails to auto-vectorise), but with rational and predictable behaviour in all cases.
I suspect UB is going to seriously damage or largely kill off statically compiled languages in the long run. Speculating JIT compilers can compile code in such a way that all executions are defined yet which does not experience the speed penalty C programs suffer, because the optimiser is free to make risky assumptions that are checked on the fly and de-optimise if they fail. It's heavy to have a full blown compiler running at the same time as your app, but desktop/laptop machines tend to have spare cores doing nothing anyway, and on servers the compiler is only running for a short period during warmup anyway and then is hardly used again.
You can get pretty good safety-performance trade-offs even without JITting, but yes, JITs are also great. But all that is only true for languages that are less insane than C, I agree. (Come to think of it, I don't know if people have explored the field of UBSan-style things in combination with JIT technologies.)
As for a "reasonable" C compiler, there is always -O0.
They are being explored now, check out this paper on lenient C, which works by JIT compiling LLVM on top of the JVM:
http://webcache.googleusercontent.com/search?q=cache%3Assw.j...
Ah, yes, thanks. In fact, their work on Safe Sulong was more along the lines of what I was thinking of, but this is also interesting.
> It therefore has no valid executions. The compiler is legally allowed to generate whatever code it wants
If the compiler concludes that the program has no valid executions, then why not just generate an error message at compile time?
I wonder in what other engineering disciplines this kind of attitude (i.e. silently punishing users for mistakes by generating arbitrarily misbehaving code) is considered acceptable. It seems unethical to me. Perhaps compiler writers should think more about what constitutes sound engineering, rather than what happens to be permitted by The Standard.
> If the compiler concludes that the program has no valid executions, then why not just generate an error message at compile time?
I agree that that would be nice to see in this case, and it seems like this particular case would be low-hanging fruit, but it's not that simple. In particular, the compiler in this example most likely does not reason globally; it never actually decides that "the program has no valid executions". It does a series of local transformations, presumably based on facts of the form "if we can reach this point, then certain values are invalid".
Another thing about such error messages would be that they would push compilers more in the direction of verification tools, which they aren't, and cannot be.
Consider:
Clang warns about the first function, but not about the second one. If it warned about the second one, I could write a third function that always divided by zero, but that it could not warn about. If it learned to do that, I would find a fourth one, etc. This is an arms race that compilers cannot win, and they shouldn't try. You should use separate verification tools for that, which do the opposite of compiler warnings: They don't reject the program if it's trivially buggy, they reject it unless you prove that it is not buggy.If compilers had more such warnings, programmers would be tempted to say "look, there is no warning, the code must be fine". That's the whole "if it compiles, it's correct" approach that gives some gullible people a false sense of security in other languages.
I certainly hope that there are not many programmers thinking "if it compiles, it's correct" after having made their first logic error, though I realize some Haskell programmers make statements that are close to that.
Clang and gcc will warn you about some of these issues if you give them the right flags (so much so that -Wall no longer means literally all warnings, IIRC), but then you run into static analysis' problem of burying you in false positives for conditional / data-dependent undefined behavior.
I have found it instructive to play with Dafny, one of the languages where the compiler does require you to prove that a variety of bugs will not occur, but 'play' is the operative word here. It is not a feasible option for C.
C has always been a language for (among other things) creating optimized code, but the implication of that has changed. Originally, it meant / required being 'close to the metal', but since then, effective automated optimization has come along, and the metal itself has become considerably more complicated (partly as a consequence of more capable optimization). As C programmers, we should understand that these changes have occurred, and what they mean for programming in C - or not use the optimizer.
> I certainly hope that there are not many programmers thinking "if it compiles, it's correct" after having made their first logic error, though I realize some Haskell programmers make statements that are close to that.
No, the Haskell slogan is "If it compiles it works". "It works" is something quite different to "it is correct".
You talk about compilers in the general case but UB causing pain like this is really a C and C++ phenomenon. Other compiled languages manage to have sane compilation strategies.
Which of the points of my post is this in reference to?
"These people simply don't understand what C programmers want": https://groups.google.com/forum/#!msg/boring-crypto/48qa1kWi...
"please don't do this, you're not producing value": http://blog.metaobject.com/2014/04/cc-osmartass.html
"No sane compiler writer would ever assume it allowed the compiler to 'do anything' with your code": http://article.gmane.org/gmane.os.plan9.general/76989
"Everyone is fired": http://web.archive.org/web/20160309163927/http://robertoconc...
The really strange this is: there's probably tons of places that the compiler takes advantage of undefined behaviour, and nobody notices, and in fact is grateful of the magic speed improvement that comes for free simply from adding -O3 or whatever. And these are then used to justify the undefined behaviour that people find slightly mystifying, or that cause actual problems in practice (interestingly these always seem to be related, as in this case, to things that can be statically proven to have NULL-related undefined behaviour). But why not treat these two cases differently?
The customer is always right!
Why do you assume it's so easy for the compiler to tell the difference between the two cases?
From this optimization pass's perspective, it has proved that in a legal program `Do` can only have one possible value, and simplified the code appropriately. Most of the time this sort of optimization is correct and the programmer wants it; how is it supposed to figure out that this time the programmer had some different semantics in mind?
I'm sorry, "legal" is not a term defined by the standard.
Oh, I totally agree. The history of C++ is basically a long argument between compiler writers and language designers, with the compiler writers inventing new optimizations which violate language semantics, a fight ensuing, undefined behavior somehow entering the equation, and then the language designers lose the argument, and the spec is changed.
E.g. one justification given for signed integer overflow being undefined behavior is so that compilers are legally permitted to optimize "(a + k) < (b + k)" to "a < b", which is not correct in the case of overflow.
I agree that the generated code is leagal wrt. the standard and that code for NeverCalled is generated because it is visible outside the translation unit.
However, to me it looks as if the assembly contains code for main (label main: is present) and EraseAll got inlined into main. This seems reasonable once you believe that the compiler can, due to undefined behavior, assume DO to be EraseAll.
So, is this on the underhanded C shortlist yet?
I wonder how many static analysis tools will pick up that the function will be run.
And then I start wondering if the static analysis tool "scene" realizes how important their work is for security...
> the function will be run.
You can't be sure, that's just what one compiler does today. Static analysis tools tend to refer to the standard.
In other words, the pointer is not initialized.What worries me is that almost every other compiler supported by godbolt would wipe your drive. It's not an anomaly of Clang - it's something fundamentally wrong in the design of compilers that allows them to do this at right optimization levels.
Which means that if I have a method that wipes my entire production database but never ever call it, it might still get called because of mistake like this one where someone forgot to initialize a function pointer.
>> Which means that if I have a method that wipes my entire production database but never ever call it, it might still get called because of mistake like this one where someone forgot to initialize a function pointer.
Do you actually have a method like that? Somehow I doubt it. Also, the example is completely contrived. If you have an uninitialized function pointer it's going to be pretty uncommon that there's only one possible function for the compiler to conclude is the right one. Also, you should not be testing on a production system.
On a note related to your example, many automotive ECUs have the ability to re-flash over the vehicle network. In many cases the OEM requires that they do not contain any code to erase or program their own flash memory. This is for the reason you cite - if somehow (for whatever reason) that code were to execute it may brick that device. This then requires that the bootloader download a couple functions to RAM prior to updating its own code - those functions are the ones that erase and write flash. This is also convenient for some micro controllers that can't modify flash while code is being executed from it.
This is a very specific case, if there is any other function that sets the pointer, the behavior is what you'd expect. https://godbolt.org/g/C3SYXt
If you have a method that wipes your entire production database, and have a function pointer that is only ever set to point to that function, and you call it ... then what made you think it wouldn't wipe the production database? It's the only thing it could possibly do.
There are optimizations that can bite you when you thought you were doing everything right, but misunderstood undefined behavior. This is not such a case. If you write that kind of code, wiping your database is letting you off easy.
I would hope none, since no static analysis tool can make that assumption without knowing the exact compiler you're thinking about and a great deal else.
This is not the "expected" behavior; undefined behavior doesn't have an expected behavior. This is what the compiler at godbolt.com happens to generate for this particular code.
At best, an analysis tool can warn that the code has undefined behavior.
> At best, an analysis tool can warn that the code has undefined behavior.
The least obvious things, like undefined behavior, are exactly the sort of thing a static analysis tool should be expected to warn about.
I just read the C++ Primer because I wanted to hack on some C++ code and the number of things you can do in C or C++ that result in "undefined behavior" is annoyingly large. There are some functions where they could have added a bounds check to the implementation, but the whole philosophy of the language seems to be that when choosing between lack of bult-in checks that would lead to easy to make errors that would cause undefined behavior and small speed increases on microbenchmarks the language designers choose the latter.
For what it's worth, in Design and Evolution of C++, Stroustrup says that when he was designing features, he would often think of a simple rule that he couldn't enforce (e.g., "couldn't enforce" being "if you violate this rule, the results are undefined") and a complex rule that he could enforce. He generally tried to pick the simpler, easier to teach rule. Unfortunately, that means there's more undefined behavior if those simpler rules are violated.
This might well be valid according to the standard, but I find it very depressing how many people consider it reasonable behavior.
If we want zero-overhead abstraction (i.e. don't generate null checks in front of every division, etc.) and a (reasonably) safe language, more static analysis is in order.
The case in point is Rust: Its type system is basically an elaborate static analysis.
Rusts advantage over tools like UBsan is that the programmer expects to interact with the type system. Many static analysis tools get rejected by programmers, because the expectation is that they "just work", when really one needs to interact with such a tool. This means bidirectional communication: The programmer tells the tool what invariant he wants to get, and the tool tells the programmer which invariants it is missing.
This is a very specific case, if there is any other function that sets the pointer, the behavior is what you'd expect. https://godbolt.org/g/C3SYXt
It might be what you expect for that particular compiler, but there's no guarantee. A different compiler might decide that because `Do` has only two possible values, that it should replace the dynamic function call with an if condition deciding between two static function calls like I did here manually, to trigger the bug again: https://godbolt.org/g/kWcvvb
Why? This sort of optimization is necessary in order to make programs run fast.
What kind of optimization? I'd rather this kind of code would crash on me, like the code that gcc compiles out of this, rather than compiler silently doing crazy inferences out of obviously buggy code.
For this particular edge case, yes it seems absurd. However, many optimization passes are based on simplifying code by figuring out what range of values something can take.
Most optimization passes don't know what the original code looks like, they only see it after it's been passed through a bunch of other optimization passes and preprocessing, so they can't reason about whether a particular optimization would seem "completely natural" or "abuse of UB" to the original programmer.
This is a really cool, graphic example of the importance of avoiding undefined behavior even if you can't see it segfault or whatever.
Do compilers emit warnings here (do they usually do that when there is a known UB?)
Here it's clear that "NeverCalled" is never called so it's clear that Do is never assigned, so the Call can't produce anything useful.
EDIT: Ugh missed the lack of "static" on the NeverCalled. Never mind.
Is this too hard to decide with certainty in C because of how you could do some pointer gymnastics and just fiddle with the field without the compiler realizing, so in order not to spit out false positives, compilers just have to assume the author knows what he's doing and allow the suspected UB without warning?
I'm just used to higher level "safe" languages (Rust, C#, etc), where lack of assignment is usually determined with certainty.
"Here it's clear that "NeverCalled" is never called so it's clear that Do is never assigned."
I don't think that is clear. If the given file is linked with another file that initializes a static variable with a function that calls NeverCalled, the initialization will be done before main is called, and so NeverCalled will be called. The compiler can't tell from just analysing the one file shown here whether or not NeverCalled is called.
> I don't think that is clear
Right. I missed that the uncalled function was public. So the issue is not clear until you link I suppose, so only detected "globally" whether the function is called. is it fair to say that that kind of global analysis is rare in the compiler+linker toolchain world for C, and usually left to static analyzers instead?
> The compiler can't tell from just analysing the one file shown here whether or not NeverCalled is called.
Right, and making it static you get the -Wunused-function. Great. This warning is about the NeverCalled function being unused though, and not about Do being unassigned before it's called. Curious, is there any way to get a warning for this? This is UB, correct? And the assignment is now known not to happen?
> another file that initializes a static variable with a function that calls NeverCalled
How would that work in actual code? Static initialization must be done with constant expressions. C++ has constexpr functions, but they cannot call NeverCalled unless it is also marked constexpr, can they?
With clang you can enable run time UB checks using the -fsanitize=undefined flag[0]. But in this case, the sanitizer doesn't detect undefined behavior.
I tried to build the example (and changing the system to an echo) using "clang a.cpp -o a -Os -std=c++11 -lstdc++ -fsanitize=undefined", but the sanitizer didn't detect the UB.
[0] https://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html
I can't build it with fsanitize=undefined at all with clang 3.4:
> but the sanitizer didn't detect the UB.
Isn't this because the sanitizer works with the instrumented "optimized" code, which does no longer invoke UB? Or is the clang toolchain intelligent enough to not perform UB dependent optimizations when the sanitizer is specified?
What would it even mean for compiled, machine language code to invoke UB or not?
UB is mostly a C concept, not a lower-level one. The semantics of assembly language programs are well-defined much more often (the only counterexample I can think of is stuff involving using threading, memory barriers, etc. incorrect)
Output of clang with -Weverything
11 : <source>:11:6: warning: no previous prototype for function 'NeverCalled' [-Wmissing-prototypes] void NeverCalled() { ^ 1 warning generated.
That's mostly a cosmetic warning. If you add a prototype for NeverCalled() at the top of the file, it silences the warning, but Clang still emits the same code.
> If you add a prototype for NeverCalled() at the top of the file, it silences the warning
Or you could write correct C and use (void) instead of () as argument list.
This example is C++, not C. Clang is complaining because it's good practice to declare a prototype for a non-static function (in a header file) before using or declaring the function itself, so it can't accidentally be used with the wrong parameter list in a different compilation unit. It will produce this warning if you have () or (void) as the parameter list.
Still better than having demons fly out of your nose.
There's only one value "Do" will ever have. He might as well set it from the beginning ;)
The only value it will ever have is NULL (but calling through a NULL function pointer is UB so it can instead call system() :)
It's uninitialized, not NULL.
edit: I was wrong, see below.
C11 6.7.9 (10):
If an object that has automatic storage duration is not initialized explicitly, its value is indeterminate. If an object that has static or thread storage duration is not initialized explicitly, then:
— if it has pointer type, it is initialized to a null pointer;
How is the C11 standard applicable to a C++ program?
I didn't notice it was C++. In C++14:
From 3.6.2:
>Variables with static storage duration (3.7.1) or thread storage duration (3.7.2) shall be zero-initialized (8.5) before any other initialization takes place
and from 8.5:
>To zero-initialize an object or reference of type T means
>--if T is a scalar type (3.9), the object is initialized to the value obtained by converting the integer literal 0 (zero) to T
and from 3.9:
>Arithmetic types (3.9.1), enumeration types, pointer types, pointer to member types (3.9.2), std::nullptr_- t, and cv-qualified versions of these types (3.9.3) are collectively called scalar types
It's a global static without an initializing expression; it is set to 0 before main() starts. 0 for a function pointer is of course the same as nullptr/NULL.
On that subject: CppCon 2016: Michael Spencer “My Little Optimizer: Undefined Behavior is Magic" (https://www.youtube.com/watch?v=g7entxbQOCc)
Compilers (and thus, compiler writers, i.e., people) have gone off the deep end with C. In search of endless over-optimization (don't worry, they will tell you that this optimization is "important" because some stupid benchmark runs 21% faster), programmer intent (as well as mistakes) are turned into bizarro behavior. Why we accept this is beyond me. For C, in particular, it has made writing code that uses plain old C ints way more challenging than it needs to be, among other things. We need to rethink what is important: a little more performance, or representing (to our best possible guess) what the programmer actually intended. </rant>
> We need to rethink what is important: a little more performance, or representing (to our best possible guess) what the programmer actually intended.
I remember reading an old book about implementing a compiler. The book actually recommended that compilers should make an effort to fix simple mistakes; e.g., compilers should add semicolons if needed, check whether an undefined variable or function was actually a misspelled variable or function, etc. I wasn't sure whether I should laugh at the naivety or shudder about what kind of code that would have led to. Especially given that each compiler would be lenient in different ways from competing compilers.
This is basically what happened in real life with HTML, with the results you predict.
> representing (to our best possible guess) what the programmer actually intended.
If the programmer intended to write a correct program, and the programmer wrote an undefined program instead, you should blame the programmer, not the compiler.
Do you have an example of an optimization pass you would turn off in Clang?
I mean, do you actually know which one you'd turn off and what the pros and cons are. Not just answer like "of course, whichever one caused this behavior!"
I'm asking because I noticed nobody who rants about compiler behavior on UB code actually seems to have a detailed understanding of what they're talking about. They always seem to just be shooting from the hip.
icc does this as well on the same example.
GCC is the most fun, jmp straight into the uninitialized function pointer.