#undefined behavior

Happy Valentine's Day, nerds!

Lovebyte is a sizecoding party / community / competition which takes place (or time really) every year around V-day.

The community gathered around the sizecoding event is wholesome and welcoming, especially towards newcomers to the demo scene.

The intro itself is a DOS (.com) executable of size 127 bytes, nicely fit for the 128 byte intro highend competition.

I said that this example code

puts(a + b > 0 ? "true" : "false");

might be wrongly optimized by some compilers down to

puts("true");

as a result of compiler logic that amounts to "overflow would be undefined in this case so we're free to assume it won't happen, or won't result in wraparound if it does".

That's correct so far, but my mistake was understating the conditions. I said this can happen if `a` and `b` are signed integer types (or just the one of them with the higher conversion rank is). That is not sufficient for the compiler to take such liberties. The compiler must also be able to prove that either both `a` and `b` are positive, or that the one with larger absolute value is positive.

For example, if you did

int a = INT_MAX;

int b = INT_MAX;

You would reasonably expect on 2's compliment hardware that the result of `a + b` is a negative number (`-2`, if I did it right in my head). But some compilers might still produce code as if your `a + b > 0` check is always false in that case!

Because for it to be true, you must have gone through the undefined behavior of signed integer overflow. But surely you wouldn't? And if you did, the compiler is legally allowed to do anything, including removing your conditional check.

And again, real compilers out in the world do this by default at high enough optimization settings. There are technically "good" reasons why they do, because these code removals based on this "did you need to pass through undefined behavior for this to be true?" are what allows optimizing out code which is revealed to be dead after constant propagation and inlining and reordering so on.

Now let's imagine that the example code was instead checking for overflow like this:

puts(a + b > a ? "true" : "false");

Then, assuming the conditions about the types of `a` and `b` are still met, the compiler only needs to prove that the value `b` is non-negative. If b is non-negative, then it can deduce that the only way for that check to be false is through the undefined behavior of overflow, and legally eliminate that check entirely because there are no guarantees about behavior in that case. Similarly, if the compiler can prove that `b` has a negative value, it can deduce that the only way for that check to be true is through the undefined behavior of underflow, and eliminate that check.

For example, any time a loop gets "optimized" in a way that changes whether or not it is infinite or terminates. Or a check gets removed. My first reaction is "what the hell? you just don't do that! if the author put a check here, maybe - wild concept, but hear me out - maybe it was for a good reason, so don't remove it!"

But then there are other times when I look at the actual logic that got optimized out, and my sympathy dies on the spot. For example:

for(int i = 0; i >= 0; i++) //try it a bunch of times

Now, I still have sympathy in the sense that I empathize and relate - I can imagine what it is like to get so used to thinking in terms of low level machine operations that this is how you naturally think to express it. I've been there. And if you get used to relying on that, it sucks to have the compiler screw you over by violating your knowledge like that, especially when that knowledge is correct for your target hardware. And it's horrifying when you realize that this could be code for an embedded controller in a medical device or power reactor, which relies on that loop terminating after all the tries to not kill people. I sympathize when it comes to the consequences, and the desire to attribute some fault to the compiler "optimizing" that out.

But I'm no longer sympathetic in the sense that I start to think "this was never the code you ought to have written in this case, even independent of undefined behavior, so you 'started it', you committed the first wrong without which this would never have happened". You know what would be more readable and intuitive to a human reader? More clear and direct? What would take less mental steps and knowledge for the human reader to think through? This:

for(int i = 0; i < INT_MAX; i++)

Where `INT_MAX` is from the standard `limits.h` header, or you can define your own if you're on a weird minimal embedded platform. (I would also rename `i` to `tries`, at which point the line comment is redundant since the code itself tells the reader all of the same information.)

Why is this better besides being well-defined, which is just a happy coincidence? Because the code logic is closer to directly expressing the actual behavior and intent. The intent is "iterate a lot of times" and the behavior is "iterate from zero until we reach the highest positive value the counter can express". The second variant explicitly directly just says that.

The first variant doesn't say that: it says "count up from zero for as long as the result is zero or higher". Now I'm all for being conscious of what kind of arithmetic you're doing, but in the first and most common one that humans are taught and usually think in, the above sentence implies an infinite loop. And I'm all for saying "if you're coding in C you should be better at thinking in wraparound arithmetic", but what I'm saying is that wraparound arithmetic is inherently more complex as a concept: when interpreting the code you can't just have the invariant that n+1 always produces a number one larger than n, you have to maintain the possibility that sometimes n+1 does something else. And even if we treat just having that in the mind as free, the reader still has to do extra mental steps to actually apply it:

the termination condition is when the counter becomes less than zero

can this become less than zero?

yes, if it wraps around (assuming that's what happens on this hardware, which I guess I'll have to just trust that it does because the code seems to intend to use that behavior)

which will be when?

right after the counter reaches the maximum integer value that an `int` can hold.

So your readers have to bring in more knowledge and do more mental steps just to reach "oh we're basically doing `INT_MAX` tries". Or you could just say that with your code. Because if you just say `i < INT_MAX`, then your mental steps are just:

the termination condition is when the counter reaches the maximum integer value that an `int` can hold.

I am imagining a variadic function or macro called `unaliased`. At runtime it is allowed to do nothing or expand to nothing, so that a compiler is free to eliminate it or ignore it. But it is defined that calling it is equivalent to saying "within this scope, as of this call to `unaliased`, I promise that none of the arguments to this `unaliased` call are aliasing each other". More pedantically: if you call `unaliased` and any of the arguments to it are actually aliased, you get undefined behavior.

With such built-in functionality, I think you can:

Get even more optimizations than can be done by just going off the strict aliasing rule and `restrict`.

Get the same optimizations as from the strict aliasing rule, provided the code author used `unaliased` to indicate it was safe.

It is entirely possible that `restrict` from C99 is strictly speaking sufficient? If you trust that the compiler will do a good job inlining, then you can always refactor the chunk of code for which the "these pointers cannot alias each other" holds into its own function with `restrict` parameters. And when you don't need to communicate that requirement to callers, you can just use `restrict` block-scoped variables.

Writing the word `restrict` in a bunch of places is annoying, but if you're following best practices you'd only do it in the places where

you wanted to say "this function literally cannot work if the stuff at this pointer is aliased", or

you profiled and looked at the machine code and determined this spot was the bottleneck because the code assumed possible aliasing.

Because even popular compilers for mainstream platforms might change the behavior of code that relies on undefined behavior when you turn up optimization settings or upgrade or just change anything whatsoever. This isn't a hypothetical. This has happened several times in recent history. Modern compilers sometimes reach surprisingly far in their interpretations of undefined behavior and the liberties they are allowed to take with it.

So your release build might behave differently in some edge case than your development/test builds, for example. And the only way you'd know for sure is by being intimately familiar with what your specific compiler does.

Users blinked first in the staring contest, and in that brief moment GCC took all the liberty it wanted to begin optimizing on Undefined behavior. Clang followed suit, and now life is getting dicey for a lot of developers who believe they are writing robust, safe code but actually aren’t anymore because they were using constructs that the C Standard defined as Undefined behavior. The language lawyers and compiler politicians had, seemingly, won out and people like Victor Yodaiken, felix-gcc, and bug/ubitux (the author of the blog post that sparked the most recent outbreak of protest against optimization) were left with nothing.

… Which is, of course, not the whole truth.

The truth is that, even as much as Yodaiken argues in his blog that Undefined behavior being used for optimization is simply a “reading error”, the problem did not start with a reading error. The problem started much earlier, when the precursor to ISO C set you up, some of you before you were even born or knew what a computer was.