For example you could say that division by zero will either give a result or trap, but that it can't do anything else, and the code path cannot be ignored. Or that an uninitialized variable is equivalent to initializing it with a semi-random number.
Even if an out of bounds array access will cause untold chaos, you can at least specify that it will cause that chaos at X bytes past the base of the array.
Merely creating an invalid pointer would be, on architectures where it doesn't trap, 100% harmless.
And for crying out loud, is forgetting to terminate a string literal with a " still undefined? There are so many bits of undefined behavior that are easy to remove.
This proposal destroys lots of dead code elimination optimizations that are very important in code post inlining (for example, in the STL).
http://llvm.org/docs/LangRef.html#undefined-values
There's also the issue that having a stable value forces the register allocator to keep a live range for the undefined variable, which can cause unnecessary spills or remat in other places. Especially on 32-bit x86, this can be a problem.
Even specifying that they have a new arbitrary value on each access would be a big improvement over the status quo. It wouldn't allow nasal demons. Since LLVM seems to already have these semantics, it makes a good argument that it wouldn't hurt C's performance to tighten the spec at least that much.
But I'm not seeing how C or C++ code gets you in a situation where you're purposefully doing arithmetic or bitwise operations on uninitialized variables. If it almost never happens, it doesn't need to optimize particularly well. What parts of the STL can be faster by treating uninitialized variables as impossible?
> There's also the issue that having a stable value forces the register allocator to keep a live range for the undefined variable, which can cause unnecessary spills or remat in other places.
This would only happen when the variable is accessed multiple times. In which case having to keep the value safe is no worse than if it actually had been initialized. I don't see how this is a problem.
What I'm mostly thinking of is allowing unused branches to be pruned. The STL tends to get inlined really heavily, which results in a whole pile of IR being emitted for what look like very simple operations. Based on the actual parameters and state, the optimizer then wants to prune out as much dead code as possible to reduce i-cache footprint, and sometimes time as well.
Take small string optimization. That optimization requires a branch on length in almost every string operation. But if you have a std::string of constant size, you don't need the heap spilled code to be emitted at all. Usually the only way to work this out is inlining + constprop + DCE. That's where undefined value semantics are really helpful: a branch on an undefined value can be completely removed as undefined behavior, which can make its branch targets unreachable, and allow them to be removed, and so on recursively. Undefined values allow entire CFG subtrees to be eliminated in one fell swoop, which is an extremely powerful technique for reducing code size.
I don't have a precise example off the top of my head as to where this kicks in in the STL, but I strongly suspect it does.
Even if you can remove one of the branches because you know if the string is small, the logic of "this branch can't happen" -> undefined -> delete sounds more complex than "this branch can't happen" -> delete.
I was skeptical about all this about six months ago myself, but the continuous stream of articles on this topic, plus the spectacular and highly educational failure of Friendly C (and not just that it failed, but why it failed, which is why I posted that exact link) has satisfied me. It is also part of why I've stepped up my own anti-C rhetoric since I've been so convinced... as bad as I thought C was, it really is, no sarcasm, not merely "hating", even worse than I thought. I am honestly scared to use it professionally and pretty much refuse to touch it without good static analysis support.
Edit: Is it figuring out that the pointer in the string object is uninitialized? That doesn't seem any easier than reasoning about the length value, and I don't see how it would lead to "br undef".
Teach jump threading some more simple tricks:
1) have it fold "br undef", which does occur with
surprising frequency as jump threading iterates.
...
Related, with some actual numbers to prove it helps, LLVM commit #138618:
SimplifyCFG: If we have a PHI node that can evaluate to NULL and do a load or
store to the address returned by the PHI node then we can consider this
incoming value as dead and remove the edge pointing there, unless there are
instructions that can affect control flow executed in between.
In theory this could be extended to other instructions, eg. division by zero,
but it's likely that it will "miscompile" some code because people depend on
div by zero not trapping. NULL pointer dereference usually leads to a crash so
we should be on the safe side.
This shrinks the size of a Release clang by 16k on x86_64.Lots of LLVM users won't. The competition between LLVM and GCC is (or was) pretty brutal.
> Plus in most or all of those cases, the optimization would still be possible even with stable uninitialized values. It just needs to be done in a different way.
I doubt that's possible without justification. How? Are you familiar with all of the passes of LLVM, how they interact, and with the code patterns generated by the STL?
I trust Chris in that he didn't add the jump threading optimization for no reason, which is the main one that matters here. If he says that this occurs with "surprising frequency", sorry, but I'm going to trust him. Compiler developers are usually right about the impact of their optimizations. Submit a patch to LLVM if you like to remove it, but I highly doubt it'll go through. If it did go through, Rust (and perhaps Swift) would probably revert it, as we ensure that we don't emit UB in the front end, so losing the optimization hurts us for no reason.
It's not that I think the Chris is wrong, it's that I think other optimizations related to dead code have gotten better in the last many years, and focused effort could improve them more.
My position, by the way, is hardly uncommon among longtime C compiler developers.
What do we do about the fact that undefined behavior actually makes it harder or impossible to write efficient code in some cases, like checking for integer overflow?
Even if your goal is performance over anything, there are a whole lot of undefined behaviors that have absolutely zero performance benefit.
This is a good example of why we should be moving away from C. :) Signed overflow being undefined is basically necessary due to a self-inflicted wound from 1978: the fact that "int" is the easiest thing to type for the loop index when iterating over arrays. Nobody is going to go through and fix all the C code in existence to use unsigned, so we're stuck with that UB forever. The realistic solution is to start migrating away from C (and I have no illusions about how long that will take, but we'll never get there if we don't start now).
> Even if your goal is performance over anything, there are a whole lot of undefined behaviors that have absolutely zero performance benefit.
Sure. But compilers don't exploit those in practice (because compiler authors are not language lawyers for fun), so they're basically harmless in practice. They're essentially just spec bugs for the committee to fix in the next revision.
C should be writable by humans.
This entire discussion is predicated on the idea that undef values having a live range is something that actually prevents bugs, which I find extremely dubious. This is not like the "null dereference is UB" thing in the Linux kernel (which I also found to be overstated in importance, but it has caused at least one problem). I can't think of a single bug that this has caused, other than a compiler bug in Rust that was only exposed by people intentionally trying to write code that would break--that is, the bug had no practical effect. It strikes me as "friendly C lawyering" for little benefit.
Then smack the spec writers for never removing undefined behavior. You don't have to smack both, but the two groups are working together to make C more dangerous every day.
>They are doing this because their customers demand it.
If you show a chart of how often the customer's code will stop working because of these optimizations, perhaps they will stop demanding it. But even if it's implemented, there should be a --reduce-undefined-optimization flag.
> I can't think of a single bug that this has caused
If it was defined, then the Debian RNG bug likely would not have happened.
If an undefined behavior is rare, that's a good reason to flatly remove it from the spec. If we could have 10 undefined behaviors instead of 200, the world would be better off. There are undefined behaviors you can hit during preprocessing, for crying out loud.
(Also even in the most extreme version, you wouldn't need to count it as live until the first access, and if that's the last access then there's no live range at all.)
No. The Debian bug was not the result of a compiler optimization based on undefined behavior. It was due to OpenSSL doing something dodgy [1]. The compilers, being conservative, all declined to do any optimizations based on the undefined behavior. It was Valgrind that called OpenSSL out for the uninitialized use of memory. This is not a bug in Valgrind either! If the C standard defined live ranges for uninitialized values, then Valgrind would still be right to flag uses of uninitialized values, because they usually indicate bugs, and Valgrind is a bug finding tool. The Debian bug occurred because OpenSSL was doing something silly, Valgrind was doing its job properly pointing out that silly thing that OpenSSL was doing, and the fix was dangerously incorrect.
If it had been valid by the C standard, it is not unlikely that they would have kept it. Then there would have been no disaster. They would not have gotten confused about what was valid and what wasn't.
Extra entropy to mix in isn't that silly.
Edit: In other words, making "Is this code valid?" more complex to answer can have bad effects even in the absence of aggressive compilers.
Once again, if the C standard were to change to allow uninitialized variables to have live ranges, Valgrind would not just "git rm -rf memcheck; git commit". That is because Valgrind is a tool that is designed to check for uninitialized memory. It did its job properly. It is not designed to check for undefined behavior according to the C standard.
You seem to be determined to lay the blame for every problem at some combination of C compiler authors and C spec writers, regardless of whether the problem actually is theirs.
I don't blame all problems on C, but I think it should be easier to write valid C. Dealing with uninitialized variables was just an example of something that could be changed. It wasn't supposed to be the biggest most horrible problem with C.
Compilers may not turn functions that hit most kinds of UB into { return; }, but they can. As a general category, that's a bad thing.
It's highly unlikely that the maintainer of OpenSSL at Debian is a spec lawyer. The maintainer ran Valgrind because, as a general principle, reading undefined memory is bad. That is independent of whether the C standard says that it's OK. If I were the maintainer of the package in question, I would not ignore reads of undefined memory just because the C committee has declared that it has some kind of behavior. That would be silly.
Valgrind contains many tools that check for things that are not violations of the C standard: for example, memcheck checks for "fishy" arguments to malloc that are not C standard violations but are nevertheless usually bugs.
> Compilers may not turn functions that hit most kinds of UB into { return; }, but they can. As a general category, that's a bad thing.
Depends on the undefined behavior. For undefined behavior coming from the C preprocessor, sure, that shouldn't be undefined, and the committee should change the spec. For other kinds of UB, if compiler authors hadn't figured out those tricks, we'd have slower programs today. Undefined behavior is much of what has allowed performance of our programs to keep improving despite the language not changing over decades.
This is approximately what LLVM describes undef as, and it indeed leads to nasal demons. This description enables a single value to both pass a bounds check, and then subsequently go out of bounds!
(Of course, you could define it to work, but I would suspect that would make this sort of value much less useful.)
There's languages that have a few undefined corners, and then there's C. A sufficiently large difference in quantity becomes a difference in quality. C is qualitatively worse than most modern languages with its undefined behavior. (Granted, some modern languages escape by having the one implementation, which is then the definition. But still, that's less undefined than C.)
[1]: http://blog.regehr.org/archives/1287