Hacker News Reader

Comment by titzer | Hacker News Reader

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.

View on HN

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.

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.)

> 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.

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.

"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.

> 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.

Which of the points of my post is this in reference to?

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.

Reply on news.ycombinator.com