Hacker News Reader

> It's easy to pick on undefined behavior in C when you focus on the more gratuitous undefined behaviors such as signed overflow or oversized shifts.

I wouldn't even mind the signed integer overflow thing that much if there were a reasonable way in standard C to check whether a signed operation would overflow.

It's not impossible to do correctly in a compiler independent way, but ridiculously hard. And slow.

Another thing is that the wording around some of the UB issues is just plain bad. The most extreme probably is the rules around strict aliasing. That there, for quite a while, was uncertainty whether the rules allow type punning by reading a union member when the last write was to another member of a good example of not taking reality into account. Yes memcpy exists - but it is even less type safe!

The union punning trick is UB in C89 and well-defined in C99 and later, although it was erroneously listed in the (non-normative) Annex listing UBs in C99 (removed by C11).

Strict aliasing is another category of UB that I'd consider gratuitous.

> The union punning trick is UB in C89 and well-defined in C99 and later, although it was erroneously listed in the (non-normative) Annex listing UBs in C99 (removed by C11).

Right, that's my point. If the standard folks can't understand their standard, how are mere mortals supposed to?

> Strict aliasing is another category of UB that I'd consider gratuitous.

I'm of a bit split minds on it. It can yield substantial speedups. But is also impractical in a lot of cases. And it's often but strong enough anyway, requiring explicit restrict annotations for the compiler to understand two pointers don't alias. Turns out two pointers of the same (or compatible) type aren't rare in performance critical sections...

Realistically it should have been opt-in.

> Strict aliasing is another category of UB that I'd consider gratuitous.

Without it you cannot vectorize (or even internally re-order) many loops which are currently vectorizable because the compiler can't statically prove arguments won't alias otherwise.

That is completely false. Look up "restrict" and there are many other contexts. BTW, "prove" and "assume" are different things. This is an old argument, which in a just world would have been settled by Dennis Ritchie's comments.

I'm quite familiar with restrict, having added it to many codebases. It's a moderately fragile construct which in no way replaces the normal c memory model. (It's also significantly under exploited by most compilers, presumably since very little code is restrict annotated.)

Prove and assume are indeed different things, but what the compiler is able to do is _prove_ the validity of the transform within the context of the C abstract machine.

Plenty of sibling comments in this thread show concrete examples of significant optimizations lost with alias analysis (and/or non-wrapping signed integers) disabled.

If the compiler is not allowed to assume that the source code is valid then very few optimizations are safe at all. Clearly that isn't what you want, so I suppose that you would argue that being able to vectorize something like 90% of all currently vectorizable loops in existing code isn't worth the cost, and instead compilers should be able to assume that anything my alias anything unless the programmer has manually restrict annotated every variable that is written to in a loop?

I expect in that world you'd see lots of code run needlessly lots slower, and lots of other code needlessly get slathered over with restrict annotations as restrict turns into a reflex because leaving it out results in poor performance so regularly... resulting in incorrect annotations and the miscompilation you were hoping to avoid-- arguably the worst of all worlds.

See e.g. https://github.com/postgres/postgres/blob/8bdd6f563aa2456de6...

> It's easy to pick on undefined behavior in C when you focus on the more gratuitous undefined behaviors ...

That is the whole point. There are scores of instances of gratuituous UB.

> I'm not certain why these are undefined behavior instead of implementation-defined, but my suspicion is that these caused traps on some processors, and traps are inherently undefined behavior.

Traps are not inherently undefined. The C standard discusses floating point traps in detail. Many details may of course be left to the implementation or platform to describe, but that's very different from saying "all bets are off".

The real reason for the gratuitous UB was misunderstanding and ignorance.

> Hopefully, you'll agree that that is a reasonable optimization.

Hopefully, you'll agree that the code is buggy, and should be fixed. We end up running expensive and cumbersome static analysis tools that try to detect situations just like this ... which the compiler itself has detected, but chosen not to warn us.

The first code isn't necessarily buggy.

I am not a compiler dev or a high skill coder so my opinion might not matter much but I'll still lay them out here.

> The first case is the compiler hint...

The compiler should refuse to compile if it comes upon such a case. Those hints are as much used by programmers as they are by the compiler. It should emit a warning and necessary checks + abort code if those hints can neither be proven nor disproven statically.

> The second case is uninitialized memory...

For the first example, unless the compiler knows that f() must always be true, it should give a compile time error. In case that it does know that f() is always true, it should still emit a warning (or give an error anyways).

> The third category is traps...

I am honestly not sure about this one. It would depend on the behaviour defined for multiple references / dereferences done simultaneously and type casting. I would still probably expect the compiler to give out warnings atleast.

Edit: language / grammar / typos

As a rule of thumb, yes, compilers should issue warnings where undefined behavior is obviously occurring. (And there is something to be said for compiling with -Werror). However, that's not going to always work, and there are two reasons for this.

The first reason is that undefined behavior is ultimately a statement about dynamic execution of the program. The set of expressions that could potentially cause undefined behavior is essentially all of them--every signed arithmetic expression, every pointer dereference, hell, almost all function calls in C++--and figuring out whether or not they actually do cause undefined behavior is effectively impossible at the compiler level. This is why sanitizers were developed, and also why sanitizers only work as a dynamic property.

For a concrete example, consider the following code:

  extern void do_something(int * restrict a, int * restrict b, size_t n);

  void my_function(int *y, int *z, size_t x, size_t n) {
    if (x > n)
      do_something(y, z, n);
  }

This code could produce undefined behavior. Or it could not. It depends on whether or not y and z overlaps. Maybe the check of the if statement is sufficient to guarantee it. Maybe it's not. It's hard to advocate that the compiler should warn, let alone error, about this kind of code.

The second issue to be aware of is that there is a general separation of concerns between the part of the compiler that gives warnings and errors (the frontend), and the part that is actually optimizing the code. It is difficult, if not impossible, to give any kind of useful warning or error message in the guts of the optimizer; by the time code reaches that stage, it is often incredibly transformed from the original source code, to the point that its correlation with the original can be difficult to divine.

So I once came across some really weird code that broke an optimization pass I was working on. It looked roughly like this (approximate C translation of the actual IR):

  if (nullptr != nullptr) {
    int *x = nullptr;
    do {
      /* do some stuff with x */
      x++;
    } while (x != nullptr);
  }

What hideous code creates a loop that iterates a pointer through all of memory? Why, this (after reducing the test case):

  void foo() {
    std::vector<std::set<int>> x;
    x.emplace_back();
  }

So the crazy code was generated from the compiler very heavily inlining the entire details of the STL, and the original code was a more natural iteration from a start to an end value. The compiler figured out enough to realize that the start and end values were both null pointers, but didn't quite manage to actually fully elide the original loop in that case. Warning the user about the resulting undefined behavior in this case is completely counterproductive; it's not arising from anything they did, and there isn't much they can to do to silence that warning.

"static int y; /* uninitialized / _Bool cond = f(); int x = cond ? 2 : y; / Is it legal to fold this to int x = 2; ? / Hopefully, you'll agree that that is a reasonable optimization. Now consider this code:"
Do not agree. That's not an optimization it's just false reasoning. Reasonable would be to either ignore it so the code depends on the uniitialized data, whatever it is, or to flag an error. Also according to the standard, static variable of arithmetic type are initialized to zero by default so there is no UB at all.
Second example has the same problem.

Third example has, for example, assumptions that C does not let the compiler make e.g. that z is a restricted pointer. Imagine that f(int c) { z = getsamepointer(); z +=1;return *z; }

And none of those optimizations existed in the 1980s.

I'll bite.

  > int x = cond ? 2 : y; /* Is it legal to fold this to int x = 2; ? */

This is permissible (on typical hardware) only if the implementation chooses to 'initialize' y to 2 (possibly skipping the actual write if it is later overwritten), since doing otherwise would result in:

  int x1 = cond1 ? 2 : y; /* So int x1 = 2; */
  int x2 = cond2 ? 3 : y; /* So int x2 = 3; */

No, no it may not do that.

Edit1: actually, as vyodaiken points out, that's only valid in the first place if y is auto, not static.

> Can this be lowered to int y = x;

Sure; the compiler is free to implement dereference in a non-trapping manner if possible.

> No one uses the result of the load, can I delete it?

Yes, it's not volatile.

> Can I hoist the load out of the loop?

I don't think so; foo might write to z.

> Note that all of the optimizations I'm alluding to here are ones that would have existed all the way back in the 1980s when C was being standardized, and these are pretty basic, pedestrian optimizations that you will cover in Compilers 101.

Yep, some of the proposed optimizations (x1x2 and hoist) aren't actually available, but they all seem like reasonable things to consider.

Edit, missed these:

> A function marked _Noreturn returns.

If written in C, the body of the function must include a return statement, and is thus a compile time error. If written in assembly, this is no different than overwriting your return address via buffer overflow and ending up in the middle of a function. The compiler should probably stick a trap instruction after the call instruction, though.

> Or you alias two pointers marked restrict.

`restrict` (formerly noalias) is not valid C[0] (or any language), no matter what the standard says; the compiler must emit a compile time error.

0: https://www.lysator.liu.se/c/dmr-on-noalias.html

> This is permissible (on typical hardware)

Hardware doesn't define C semantics. C defines C semantics. I don't understand what your conditional example is trying to say, but you seem to assume that an uninitialized y is an actual uninitialized register or memory location. It's not.

>> A function marked _Noreturn returns.

> If written in C, the body of the function must include a return statement, and is thus a compile time error.

It might contain a return statement that is never reached because the function goes into an infinite loop or exits/aborts the program or does a longjmp.

> Hardware doesn't define C semantics. C defines C semantics.

C does not define C sematics for undefined behaviour; that's what makes it undefined behaviour.

> an uninitialized y is an actual uninitialized register or memory location.

On typical hardware, yes.

>> an uninitialized y is an actual uninitialized register or memory location.

> On typical hardware, yes.

Maybe you can help me identify the register or memory location for y in your example: https://gcc.godbolt.org/z/3b4z56Y87

Link is broken; says:

> Without Javascript the regular website is not functional. To go to the noscript version Compiler Explorer click here

"click here" goes to https://gcc.godbolt.org/noscript/z/3b4z56Y87, which has:

  int choose(int cond1, int cond2)
    {
    int y;
    int x1 = cond1 ? 2 : y; /* So int x1 = 2; */
    int x2 = cond2 ? 3 : y; /* So int x2 = 3; */
    return x1 + x2;
    }

but no actual assembly.

Based on context, I'll speculate that you have found a compiler bug, that the compiler writers will refuse to fix it, and that the varible y has been optimised out because it's unused after constant propagation, regardless of whether said compiler bug causes the constants being propagated to be incorrect.

So on the one hand you're (rightly) saying that this function has no semantics under the rules of the C language, but on the other hand you're saying that the semantics that C compilers assign to it is a bug, and on the third hand you are saying that the hardware should assign semantics to it even though this code is not written in assembly language, so it's not clear what the hardware should assign semantics to? Got it.

What version of C doesn't require `static int y;` to be initialized to 0?

You're right, it should be automatic storage duration instead of static storage duration.