What Every C Programmer Should Know About Undefined Behavior (2011)
blog.llvm.org
blog.llvm.org
IIRC, the Linux kernel has a rule that as a kernel developer, you are not allowed to break userspace, even if you think userspace is wrong. This is an apologia for why compiler writers think they should not have to be held to similar standards.
The argument is always something along the lines that UB in the C standard means they get to do whatever they want, including such nonsense as eliminating entire loops because the last access is out of bounds or going down an if-else-branch other than what the if says.
That this argumentation is specious in the extreme is shown by the fact that C compilers worked fine (and with less code breakages) before there even was a C standard, so all behavior was "UB".
The unstated assumption is that the optimizations enabled by this are absolutely necessary. That overstates the importance of compiler optimizations in general, and certainly the importance of these particular optimizations. (see Proebsting's Law)[2].
There may be code-bases where these extra optimizations are beneficial or even essential, fine, let's add a -Ogoforit or -Oletsgocrazy flag.
Rebuttal here: What every compiler writer should know about undefined behavior or "Optimization" based on undefined behavior hurts performance[1]
Short summary is that this trend towards exploiting UB breaks a lot of code that has been working for decades, and the fixes required to bring them in-line with the new regime imposed in order to enable these new optimizations makes it slower than the old code without those optimization. Yay.
[1] http://www.complang.tuwien.ac.at/kps2015/proceedings/KPS_201...
[2] http://proebsting.cs.arizona.edu 'I may be best known for "Proebsting's Law", which asserts that compiler optimizations have yielded annual performance gains an order of magnitude worse than hardware performance gains. The law probably would have gone unnoticed had it not been for the protests by those receiving funds to do compiler optimization research.'
Not exploiting the UB for optimizations in ways that break lots of code is actually trivially easy. We have been doing it for 30+ years and we just have to stop adding new optimizations that break, and possibly revert some of the ones that are already in there.
Here lies madness. What optimizations are not allowed exactly? Strict aliasing? Assuming dereferenced pointers are not null? Assuming all array accesses are always in bound? Assuming that integers don't wrap? Assuming that allocated memory is not accessed after a free? Reusing function frame slots of variables with non overlapping lifetimes? Not laying down local variables in the most obvious way? Caching and reordering non-volatile memory accesses? Accessing local variables of functions that have returned?
I'm sure you will say obviously not allowed to the first few and obviously allowed to the last few, but at some point all of these optimizations (and more) did break some code as some point.
Nah. You're looking at it the wrong way. You are saying madness lies in going there. We don't have to "go there". We can simply not leave there. Not doing something is easy. In fact, it's my secret super-power. If you want, I'd be happy to teach you.
If what you want is a straightforward translation of C into machine code, there is always -O0.
git co <previous-hash>
You're welcome!
It's really common for bugs to only appear when compiling with optimization.
Reasonably, when those bugs appear, people go fix them.
My guess is in LLVM these optimization are turned off for debug builds. But who wants to be running debug builds all the time?
There are certainly safer alternatives, but not faster ones.
I'd probably agree though, in most cases users don't need the fastest builds (most OS tools). It would be interesting actually to be able to enabled optimized versions of functions as a runtime flag. But I've never seen that done.
1. Vary between compiler versions.
2. Vary between compiler implementations.
3. Often contain somewhat useless warnings (Wparentheses) that can change with changes in 1. or 2.
It's not the only language of this sort, but C also has a lot of code written in it, which is a major advantage.
Not really true in the context of the optimizations done by modern C compilers (e.g. autovectorization).
Not really; it's structurally nothing like assembly, which is as close as you can get to the hardware without just handcoding machine code.
Now, C -- for a structured language with static typing -- provides very little in terms of safety features that get in the way of direct hardware manipulation, whereas lots of languages with superficially similar structure aim to be safe in some ways by default which makes some hardware manipulation more difficult, or at least more verbose, than it would be in C. So, in some ways it gets less in the way of freedom to manipulate the hardware than some other structured programming languages.
But it's not particularly close to the hardware at all.
Here, assembly is touching the hardware. If you write your code in assembly, it's not portable to other architectures, even hypothetically.
>provides very little in terms of safety features that get in the way of direct hardware manipulation
Exactly. So it's a heck of a lot closer to the hardware than most 3GLs.
https://en.wikipedia.org/wiki/P-code_machine
Linoleum was another:
http://anynowhere.com/bb/layout/html/frameset.html
The closest in C land was C-- by Jones et al which still looks heavy compared to p-code:
1. What's the proper way to do a NULL check? In the first example, they show how a NULL check could be optimized away, but I didn't see where they explained how to do it the right way. I might have just missed it though.
2. It would be nice if compilers offered a special optimization flag that performs most optimizations, but also “fills in the gaps” for non standard behavior by behaving how people expect. I realize that this would essentially be like each compiler implementing its own version of the standard in a way, but the reality is that if 99% of the people are making an assumption about how the compiler is going to do something, maybe that’s how the compiler should do it? Perhaps like a “speed+security” optimization flag. GCC already has some flags to handle certain questionable things such as strict aliasing, etc… Maybe something already exists, IDK. I guess the real solution would be to change the actual standard.
EDIT: A comment elsewhere provides a good response to my second point. It was along the lines of "which optimizations are okay then? Most optimizations broke code at some point".
I guess my response would be to only disable the ones that are the most common trouble makers. Another factor could be the performance gain vs amount of bugs it causes. I am reconsidering my second point though...
You need to not do * p at all if p is NULL (i.e. move the "int dead = * p" after the early return).
However, an implementation could define various UBs however it wants. The difference between "undefined" and "implement-defined" is really that an implementation doesn't have to anything even remotely sensible for "undefined" behavior, but it has do define some ("sensible") behavior for "implementation-defined" behavior. Usually, "implementation-defined" behavior also tends to remain consistent across versions whereas "undefined" behavior usually has no such constraints. For example, for "undefined" behavior, version 5.1.2.3 of the compiler may differ drastically from 5.1.2.4 in terms of optimizations which rely on UB.
Undefined - the compiler may assume this can never happen, and if it does happen, it can "poison" the whole execution including whatever logically happens before the undefined part.
Unspecified - the behavior must be deterministic and cannot affect the semantics of other well-defined parts of the program, but the implementation need not guarantee any single behavior.
Implementation-specified - like above, but the implementation must specify the exact behavior.
Even though the standard imposes no specific requirements, it explicitly calls that out at something you could do: http://port70.net/~nsz/c/c11/n1570.html#3.4.3
But for some reason nobody seems to ever think this is an option.
The compiler doesn't specifically search for undefined behavior and use it as an excuse to do something "quirky." Instead, it assumes the code is well-defined and interprets (and transforms) it in ways that preserve its semantics. For example, "One cannot dereference null pointers. The author dereferenced the pointer p. Therefore, p is not null. Since p is not null, the compiler can avoid checking it after the first dereference." The compiler is essentially assuming that the author knows something that it may not and just runs with it.
However, there are a lot of transformations--and corner cases--many of which can interact. This can produce complex unwanted behavior that looks like "nasal demons", but largely as a side effect. The compiler does not say "OVERFLOW DETECTED. REPLACING ENTIRE FUNCTION WITH NOOP"
If stability/security is important in your codebase. It's of course worth avoiding undefined behavior, and compiling with warnings as errors (-Werror in gcc).
However it's also really worth running your test suite through Valgrind [1] too sometimes. This instruments your code to check for use for use of initialized variables/other non-deterministic behavior at runtime.
I used to run this under continuous integration, and flag builds with issues.
That can become really annoying for an end user looking to just compile and run your software, not debug why it fails to build because their setup outputs a warning somewhere that may not even be an error. And turning off -Werror tends to then require delving into Makefiles (or whatever other build system they chose to use), and at that point most people are probably just not going to bother and call it broken.
Again, I'm not saying you shouldn't attempt to snuff out and find every warning that you can, but you shouldn't have your default build rely on compiling with no warnings. There's just too many variables uncounted for to expect your software to compile without warnings in every possible configuration.
I also agree 100% with running test suites through valgrind - I do that as well and it's a very good way to guard against memory leaks being introduced (Of course, good structure and design techniques are always the best defense, but there's nothing wrong with a good check that things are doing good).
I'll generally build my own code with all warnings, but use as close as I can to the package maintainer's build settings for their code. Even then, you can get warnings because the third party developer doesn't use your exact compiler.
Like 'confusing indentation' or 'unused static const variables'.
Seriously, these two are completely idiotic; why would the compiler decide that the fact I don't have a blank line 'might' be confusing? on whose criteria? Same with static const variables in C files. Lots of code is often #ifdef in/out, and lots of people would rather have a static const int than a #define!
if ((err = SSLHashSHA1.update(&hashCtx, &signedParams)) != 0)
goto fail;
goto fail;
If a compiler does that, it is broken. Dereferencing P clearly has side effects (i.e. segfault if P does not point into valid memory). A compiler must prove that its optimisation does not affect the program execution. This is clearly a change that does. It cannot optimize away operations with side effects. And if this is a valid optimisation according to the standard, then the standard is broken.
EDIT: If segfaulting is not a part of C, but a part of the hardware architecture, then the compiler shouldn't assume that a dereferenced pointer is not NULL. Either way, the compiler should behave in a way to avoid the least expected outcomes.
If you want to force the compiler to not remove a memory operation in C, you need to define the pointer as "volatile"
I didn't think that dereferencing a variable could ever be the sole cause of a side effect. I thought that side effects were only relevant in the context of a store (except for maybe volatile variables in which there are some ordering/barrier constraints applied as well). I realize that in practice, deferencing NULL can definitely cause a crash, but I don't know if it counts as a "side effect" in the typical "C" sense of the phrase.
I know that modifying the value of a variable which is accessed by means of a reference passed as an argument could definitely have side effects (since another unrelated function might read that data) and thus a store can’t be completely optimized away (but still can be reordered), but I don’t see why “dead” can’t be optimized away in this case.
In this case “dead” is a local variable, thus it can never be accessed by anyone outside of the function. Therefore, if there are no reads of the variable after that single store, I don’t see why the store can’t be completely eliminated.
In fact, this is a common issue when dealing with microcontrollers where configuration registers are sometimes written by assigning a value to a dereferenced address constant. That's why they get casted as volatile.
If the C standard did not allow pointer dereferences to be optimized out, many optimizations would become impossible, and people would switch to a language that did allow this.
If the compiler knows that this is undefined, then you have already broken your end of the deal and therefore the compiler is free to break their end of the deal.
Therefore, eliminating the line is completely okay and the only think broken there is the code.
IIRC, simply making P point to anything other than an object or 1 past the end of an array is already UB. I suspect that this is because some architectures have dedicated address registers and can take an exception when an invalid address is loaded/calculated instead of doing it when the memory access happens.
I don't think this is true in the strict sense you're describing it. Certainly forming a null pointer isn't UB as I understand it, only dereferencing one.