One Word Broke C | Hacker News Reader

One Word Broke C

web.archive.org

30 pointsseansh6 comments

"""

Consider this code:

  if(p == NULL)
    write_error_message_and_exit();
  *p = 0;

If the compiler thinks that writing to NULL, is undefined, it can therefore assume that since you are writing to p, p can’t be NULL. If p can’t be NULL, the entire if statement can be removed and after optimization the code looks like this:

  *p = 0;

"""

The author has this backwards. The code in the first listing (test -> exit -> write) is correct, and will not be transformed in the way he claims.

The code which was wrong looked like this:

  int pv = *p;
  if (p == NULL)
    write_error_message_and_exit();

GCC decided that since reading/writing NULL is undefined behavior, it should be allowed to treat `*p` as an assertion that `p` is non-null. Then it pruned any branches after the read that tested for `p == NULL`, including some that guarded more important parts of the logic.

Original coverage in LWN: https://lwn.net/Articles/342330/

People complaining about UB frame it as if it was some intentional malice from compiler authors, a punishment for writing non-standard code.

The reality is much more boring: writing fast, well-optimizing, spec-compliant compiler is hard, and the way current compilers deal with this makes it nearly impossible to know when UB is exploited for good things that users demand, and when it creates nonsensical behaviors.

To tame this complexity, optimizations are typically decoupled into multiple analysis and transformation passes, with each pass doing only its own thing without a context. But this architecture also makes it nearly impossible to see the full picture. The pass that marks "this can't happen" cases doesn't know if it's propagating spec-compliant rules and useful checks done earlier in the function that may be useful for later optimization passes, or creating a weird action at a distance from UB code. The later "delete code that can't happen" pass doesn't know if it's cleverly removing redundant functions hoisted out of loops, remains of `if (0)` and inlined functions, or if it's deleting your slightly-wrong overflow check.

> with each pass doing only its own thing without a context

That's exactly how people working in organizations deny any wrongdoing. "I'm just following orders in my cubbyhole and that's it; I have no idea where this stuff comes from or what happens with it after I'm done."

C89's "permissible" word does appear to prohibit situations in which some optimization is performed on the assumption of "no UB", where that assumption is obviously unreasonable.

It is permissible to allow unpredictable behavior to take place if the situation is "ignored completely".

If it's obvious that UB must be happening, but we ignore that, then we are perhaps "ignoring completely". Turning a blind eye is ignorance, but it's not complete ignorance.

For instance, consider an optimization which turns for (int i = 0; i >= 0; i++); into an infinite loop. This is based on 1) knowing that i is initialized to a nonnegative value and 2) examining every update of i in the loop and seeing that i is incremented. But if i is only incremented in the loop, it is inescapable to know that i overflows. Ignoring that situation looks a lot more like "blind eye" ignorance and not passive, complete ignorance.

It's not an evil scheme to do whatever. It's a bunch of general-purpose optimizations that add up to this. There's a pass that looks at the condition, and checks if "for all cases that C cares about, is this always true?" replaces it with true. This pass ruins your loop, but also the very same pass cleverly removes redundant instructions in many other cases.

Not doing this to the loop would require special-casing this particular code, and it's a burden to special-case such code (and many other pathological cases) on top of all the other complexity there is already in optimizers. C gets "lowered" into blocks of assembly-like instructions, so there's no `for` loop any more even before the optimizer touches it. This format is used, because it's easier to correctly optimize than anything which looks like C (partly because C requires supporting wicked things like `case` in places you wouldn't believe are legal).

For the most part, C optimizers simulate running code on a Low-Level Virtual Machine described in the C spec, not a specific target CPU. This isn't to screw you for looking at this from perspective of what x86 would do. It's to support lots of different CPUs in one codebase, with the best possible optimizations, in a spec-compliant way. But it means your code will first "run" on an imaginary CPU that really can't overflow an int.

Just as a bunch of optimizations that are sensible in isolation can add up to surprising UB bomb, a bunch of "just do the simple thing that the code says" rules can add up to surprisingly inefficient code. If `i++` was simply implemented as `add 1 with overflow`, you couldn't get some strength reduction optimizations in the loop, or index arrays with CPU's native addressing modes (they overflow differently than an int).

> In C89, undefined behavior is interpreted as, “The C standard doesn’t have requirements for the behavior, so you must define what the behavior is in your implementation, and there are a few permissible options”

That is flat out wrong; it describes implementation-defined behavior, not undefined-behavior.

In spite of the word "permissible", the range of what is permissible is very broad. It is permissible to "ignor[e] the situation completely, with unpredictable results". Ignore the situation means not to implement any requirements at all in regard to that situation, and not provide a shred of documentation about that. (Contrary to the article's claim.)

Nowhere is it imposing a requirement for the implementation to define any choices. Only one of the options refers to documentation: in some area where behavior isn't defined, the implementors can choose to provide a documented extension. It's that documentation which makes it an extension. If the documentatio isn't provided, then the behavior isn't a documented extension. There is no requirement one way or the other.

Now about this "permissible" versus "possible" difference: there could be one, but perhaps not in the way the article's author thinks.

When C89 says that it's permissible to ignore the situation, that seems to rules out malice. If the program perpetrates the undefined situation, and some harm occurs (like a flash partition being wiped out), that must have happened because the situation had been ignored with unpredictable consequences, and not because the implementor put in code to detect the instance of undefined behavior, and arranged for the erasure to be done on purpose.

"Permissible" seems to be encouraging the implementor to terminate the program (possibly with a diagnostic) if the implementor develops the ability to detect the situation. Detecting the situation and acting maliciously is not in the range of what is "permissible".

With the word "possible", it is less clear that malice is being discouraged. Clearly, malice is not logically impossible; it seems as if the word is introducing an inexhaustive list of example consequences.

> everything after ANSI/C89 is broken and shouldn't be used because implementation-defined behaviour allows "anything" to happen, such as erasing your entire hard drive.

Language pedantry: 100

Reply on news.ycombinator.com