A huge number of seemingly-trivial optimizations depend on assuming that undefined behavior will never happen. The number of optimizations that don't depend on UB in any way is quite small. For example, if you want to get pedantic about it, even automatic promotion of local variables to registers is exploiting undefined behavior—who's to say you didn't have a pointer that just happened to point to one of them?
Hmm, nope. Sure, it will save you from much UB. But GCC and Clang have idiotic front ends. On purpose. They subscribe to the idea that the optimizer phase should clean up the front end mess. They're not entirely wrong, since it does simplify the front end, and does not really make the rest any more complex. It does make it slower, though.
Long story short, those compilers don't generate reasonable code by default. You need at least -O1.
Edit: the irony is that if you do compile with optimizations, it does a different optimization.
What won't necessarily work as expected is a shadily obtained pointer to a local variable, like by displacing &i to try to point to the same location as &j.
If &j doesn't occur anywhere (or does occur, but in a way that is optimized away), j may not even have a location.
Can you expand on why you feel this must be the case?
I'm thinking for example deference of pointer could be defined to be equivalent of platform-specific memory load instruction. It wouldn't be memory safe and would segfault like C, but it still wouldn't bring up nasal demons like C UB.
Optimization can work backwards in this regard.
For instance, let's consider CSE (common subexpression elimination). That allows some repetitive code to produce the same results as code that adheres to DRY.
E.g. stupid way to insert into a circular list:
node->prev = prev;
node->next = prev->next;
prev->next->prev = node;
prev->next = node;
smart way: get a local variable for prev->next!
node *next = prev->next;
node->prev = prev;
node->next = next;
next->prev = node;
prev->next = node;
Also note that we can reorder these four assignments in any of the 4! permutations and they produce the same result (unless there is aliasing, which would be unintentional and wrong regardless of the order).
Not the case in the original. For instance, it's important that prev->next is stored in node->next before the assignment to prev->next.
You can shoot yourself in the foot with local variables though. Caching is susceptible to staleness. You have to know when it is legitimate to keep using the cached value and when it must be reloaded or disused.
After our assignment prev->next = node, the next variable no longer represents the value of prev->next. In this case, since we are done, we don't care. If more code followed which still assumed that next is the original successor of prev (now the successor of node), that would be wrong.
By the way, the magic multiplication number can be worked out, because it's just fixed point math. We take the 32:32 fixed point representation of 1 and divide by 17 to get an approximation of 1/17 in 32:32 fixed: 0x100000000 / 17 = 0xF0F0F0F. That's our magic number for dividing 32 bits by 17 by doing a 64 bit multiplication. For instance 90/17 is 90 * 0xF0F0F0F = 0x54B4B4B46. The integer part of this 32:32 fixed point value is in the upper 32 bits which is 5.
There are some subtleties there, plus considerations of whether we want signed or unsigned division. Better let the compiler deal with it. Arithmetic reductions are safe optimizations. It's hard to imagine what you could do wrong so that an arithmetic reduction breaks your code, given that it produces the same result and doesn't interact with some some memory aliasing where the compiler isn't informed about what you're doing.
And by the way, given this code:
#include <stdio.h>
struct node {
struct node *next, *prev;
};
void ins_after_a(struct node *prev, struct node *node)
{
node->prev = prev;
node->next = prev->next;
prev->next->prev = node;
prev->next = node;
}
void ins_after_b(struct node *prev, struct node *node)
{
struct node *next = prev->next;
node->prev = prev;
node->next = next;
prev->next = node;
next->prev = node;
}
Better source that is easier to reason about; better machine code: all round win.
ins_after_a:
.LFB23:
.cfi_startproc
movq (%rdi), %rax
movq %rdi, 8(%rsi)
movq %rax, (%rsi)
movq (%rdi), %rax <-- wasteful re-load of (%rdi) due to aliasing suspicion
movq %rsi, 8(%rax)
movq %rsi, (%rdi)
ret
.cfi_endproc
.LFE23:
.size ins_after_a, .-ins_after_a
.p2align 4,,15
.globl ins_after_b
.type ins_after_b, @function
ins_after_b:
.LFB24:
.cfi_startproc
movq (%rdi), %rax
movq %rdi, 8(%rsi)
movq %rax, (%rsi)
movq %rsi, (%rdi)
movq %rsi, 8(%rax)
ret
.cfi_endproc
In this case, you could avoid the wasteful re-load by marking the function arguments as `restrict`. One of the reasons Rust's memory model is interesting is that the language statically prevents mutable aliasing in most cases, so "restrict" comes for free… well, kind of. (It's actually rather difficult to nail down the precise guarantees, especially when your compiler's backend was originally designed for C.)
That's what restrict does: it makes some behaviors undefined and otherwise doesn't change the semantics of the program. It's completely against the grain of moving to a safer language.
Why would I do that, if I can instead beautify the source and machine code while sticking to what was available in C90.
I think restrict is mainly intended as a way of competing against Fortran. If you're processing arrays referenced by pointers, and can get the compiler to believe that they do not overlap, then the compiler can unroll the loops and rearrange the accesses and calculations in the unrolled body. Like it can load four elements from a source arrays, do four calculations, and then store four elements into a target, rather than interleaving. That can be done by vectorized instructions.
Here is where our technique falls short: if we write the loop body with our load-calculate-store style, it cannot be unrolled and vectorized. We have pinned down an exact behavior for all possible cases of aliasing, like self-overlap with a displacement. Vectorizing unrolls do not preserve that behavior.
Manual unrolling isn't attractive because it's a guessing game. A good amount of unrolling on one machine may give the instruction cache indigestion on another machine.
Like UB in the preprocessor. WTF? Processing a bunch of tokens at compile time should be totally safe. But no: if the ## token pasting operator glues together two tokens which do not look like one token, the behavior is undefined.
It worked differently on different compilers 35 years ago and was coded as undefined. It being undefined gave the compiler writers no incentive to fix their implementations to some common behavior (like diagnosis of an invalid token paste).
For instance, we could have a dialect of C in which this is required to print "0123":
int i = 0;
printf("%d%d%d%d\n", i++, i++, i++, i++);
An example of undefined behavior which is not gratuitous is overflow on integer addition. Th expression i + j, where i and j are int, is not ipso facto undefined because of its form. Only for certain combinations of values of its operands is it undefined. We cannot simply banish that without banishing addition, and various ways of making overflow defined have drawbacks, like being expensive (e.g. target machine has no native support for the particular behavior, so extra instructions have to be generated) or super-expensive, with complicated representation and memory management (switching to bignums).
Where does C actually gain anything nowadays? Signed integer UB is mostly useful for optimizing misuses of `int` for unsigned values (https://news.ycombinator.com/item?id=17191295), and is evaluation order even relevant anymore? (I don't think clang can pass that information down to LLVM, at all)
The only example I gave which has known drawbacks is the shift one, where modern platforms differ in the behavior, and LLVM will only optimize out the masking of the shift amount on the platforms that have that same behavior in their shift instructions (I think x86, but not ARM).
However, even if you make all of these changes to C, there's still a lot of UB left, in the form of memory accesses, which is much harder to get rid of (see the other comments, some of which mention Rust as well).
I.e. you mean that the compiler front end has to choose an order without knowing which order will be good for LLVM, and there is no information to say "I don't actually need this specific order; pick another one that is better".
Compilers for languages with strict evaluation order can still perturb evaluation order when it is safe to do so: like when expressions do not have side effects, or have effects that don't mutually interfere and are not external. They can thus avoid or eliminate the temporaries.
C is still being specified like it's 1982 and compilers have to run in a few kilobytes of RAM, in a single pass, and go straight from source to target machine code.
Such languages typically do provide some form of "no promises, here there be dragons" in the form of unsafe blocks or functions. Restricting this region of unsafety is a huge benefit for programmers and compilers. Programmers because relatively few pieces of code need to be carefully reviewed. Compilers because most of the program contains little or no UB.
As a typical example, in C you can alias and type pun. Therefore to avoid all UB the compiler would need to be extremely careful in any function containing a pointer. You could return a reference to a local through a separate opaque function call, or receive multiple pointers all aliasing the same memory. To completely avoid all UB means inserting checks after every potentially mutable machine instruction, or emitting duplicate function bodies that take different paths when the pointers alias; that's assuming the compiler even has enough type information to answer the question!
With typical C#, Rust, Swift, etc you just can't cause those kinds of problems without deliberate subterfuge and use of Unsafe types or blocks.
Or to go even further in the past, NEWP, still alive on Unisys ClearPath mainframes.
Lest we forget, any language with a C FFI capability must have some notion of UB, because the FFI effectively includes the C code in its own semantics (unless fully sandboxed, which may be too expensive to be done).
In systems like Unisys ClearPath, you can even configure the system such that only admins can execute applications with unsafe blocks.
In C any line of code, if care is not taken to use the correct compiler flags, can be a possible source of UB.
What do you mean?
ANSI C11 has 200 documented cases of UB, and each compiler might have additional cases, are you sure you can know all of them by heart while looking at a random line of C code?
Any C function that manipulates pointers (or arrays) can alias those pointers, type pun, and otherwise touch the same block of memory through different paths and/or treating the bits as different types.
Vast areas of optimization are completely closed to you if you want code to be resilient in the face of aliasing.
You should sit down with pen and paper to figure out how to optimize a simple function while preserving invariants but without UB. It would be very illuminating.
So maybe come up with a real example and stop hand waving.
Recently I've been trying to imagine what Rust's safe abstractions that use `unsafe` code internally would look like on top of some advanced mix of dependent type theory and proofs about state-manipulating imperative programs.
At that point, the optimizer would have proofs of the invariants it can rely on and it could even potentially emit proofs that every single transformation it performed preserves the (safe) semantics of the code being optimized.
But we're not there yet. Today, we need at least a small subset of the libraries of a systems language to prevent UB "by hand". And in C (or C++, although not necessarily for the same reasons), that's even harder, as there is no notion of a "safe abstraction" (one which you cannot misuse to produce UB).
I would think that what we want is invariants that have been validated, not assumed - especially not assumed incorrectly.
What you want is effectively automated proof-search (a hard problem) for an entirely-safe systems language (which doesn't even exist yet, AFAIK. at least not what I described).
Both C++ and Rust use pointer ranges for iteration, and Rust even forces indexing/counting to use pointer-sized unsigned integers. So Rust turned off the LLVM bit which says "signed overflow is UB" and did not really lose much from it (AFAIK, anyway).
Everyone always rails against the bogeyman of asshole compile writers maliciously rewriting your program to eke out 1ms on benchmarks, but nobody every names which clang or llvm optimization pass, specifically, they think should be turned off even in -O2 or -O3.
There are means to apply the modern approach of optimizations beyond O0 on C without importing all kind of UB from the language level. You just have to actually proove the properties you want to rely on, instead of relying on wishful "UB => authorized by the standard => programmer fault if anything goes bad" thinking.
And promoting local variable to registers CERTAINLY NOT depends on language level UB. It would be permitted by the as-if general rule even if anything prevented it to happen in the first place, which is not the case. You don't have to have an address if nobody wants it and random pointers haver never been required to allow access to all objects, especially those who might never have an address at all. Plus nobody ever expected that anyway. People expect 2s complement. Or at least something that can not result in nasal daemons, and given C history, something that matches what the processor does. So 2s complements is at least not utterly stupid. So conflating the two is dishonest to the highest point -- except maybe if the only intended audience of the C language is now experts who e.g. write compilers. What a bright future this would be.
Hell, we dropped the hypothetical flat memory model even without strict aliasing for maybe 20 years (and probably 30, to be honest), and this had NEVER caused the kind of issues we are talking about. So don't pretend it did, just to dismiss the real issues. So ok even then it was actually probably informal as hell and in some ways worse for experts, but the amount of exploited UB was also WAY smaller. Quantity matters in this area. And context too. Do you want secure OR fast embedded systems? I would prefer reasonably secure and reasonably fast. Certainly NOT fast to execute and exploit, or more probably fast to crash pathetically.
You know very well that compiling in O0 is not going to happen in prod on tons on projects.
Don't dismiss real concerns with false "solutions", especially when mixed with proofs of your misunderstanding of the situation.
The spec says otherwise:
> An object exists, has a constant address, and retains its last-stored value throughout its lifetime.
[C11 6.2.4.2]
But that's more of a pedantic detail. More pragmatically, you do have a point. It is indeed possible to build a C compiler that has no "undefined behavior", but only unspecified behavior, as long as the program doesn't actually violate memory safety by, say, writing to some random address it can't prove it has permission to write. For example, guessing the stack slot used for a variable and overwriting it pretty much has to be undefined behavior – it's hard to optimize anything if variables can randomly change their values without being referenced. But that's okay, because overwriting random memory is inherently unsafe without obtaining a guarantee of what that memory will be used for. On the other hand, reading from random stack memory could be unspecified. A particular stack slot might be used for a variable, a temporary expression, or nothing at all, so it's unspecified what you might find there. But the compiler will always generate a single, real load instruction, without making any assumptions about aliasing that it can't prove; thus, you'll never get logical impossibilities like "x + 1 > x".
And such a compiler could definitely produce code that's better optimized than -O0 – because -O0 is a very, very low bar (it doesn't even do register allocation, in the compilers I've seen). But I expect it would do substantially worse than a modern compiler's -O2 even on average code, with a lot of little missed optimizations that add up. (Though if you're using -fno-strict-aliasing, you're probably already eating a decent percentage of that penalty.) And in the worst cases, like tight loops that can be autovectorized only by taking advantage of undefined behavior, it might be only a fraction of the speed of the better-optimized version.
Still, it might be an interesting project, especially if you could formalize the "no undefined behavior" guarantee.