What Every C Programmer Should Know About Undefined Behavior #3/3

How would gcc, a C program, compute the result of a signed overflow without risking crashing?

Have you seen this page? Specifically the libraries part? Do you know why GMP, MPFR and MPC are requirements, not options? Actually I think this particular optimization does not use multiprecision arithmetic, but if it's needed in some passes it is available to GCC despite the fact that it's C program.

P.S. Note that is you really want "overflow", not "undefined behavior" you can do that and the fact that GCC is a C program does not stop you.

if (MAXINT + 1 == -MAXINT) printf("Wow, 1's complement!\n");

Actually, if the compiler is forced to consider overflow, it just has to think a little harder before making the same optimizations. The compiler can determine that 1<<32 / GCD(1<<32, 0x04040404) > 256/4 and thus that the first time i >= 256/4, val == 0x04030200 with unsigned math, and val != 0x04030200 before that. Your loop would have to get slower (or, more likely, take an additional register) if it was going to use the same value in "val" multiple times, simply because it becomes necessary to track another piece of information.

(Also note that it doesn't matter if you declare the loop counter as an "unsigned int"; the nominal loop counter actually gets discarded entirely, in favor of a proxy loop counter, which is what could overflow.)

With gcc 4.4.5, replacing "int val" with "unsigned int val" makes it actually generate what you would expect of:

for (val = 0x03020100; val != 0x04030200; val += 0x04040404, value++)
    *value = val;

which avoids the "i = 0", "*value = val" is a simpler instruction than "value[i] = val", and uses one fewer register; but it still actually works. If the constant you're adding is 0x04000000, the optimization doesn't work, and gcc produces the slower code. The code it produces for "unsigned int" is the fastest working code possible, so it's not getting slower in any meaningful way by using "unsigned int" (I mean, it loops faster without testing the end condition, but...).

Does it really make sense that a loop gets slower just because you declare the loop counter as an "unsigned int" instead of an "int"?

C compilers weren't smart enough to take advantage of the leeway given: they in fact did exhibit implementation-defined behavior, not undefined behavior, in the face of a signed overflow. They acted like the hardware acts upon signed overflow.

Which was to crash, in many cases. Signed overflow caused a processor exception, just like division by zero, because the result could not be represented.

> Sure, some platforms were perfectly happy with such code. But then if you want low-level non-portable language... asm is always there.

And so is C. :) After all, what language is the Linux kernel written in?

Linux kernel is written in C, quite portable and people fight constantly to fix hardware and software compatibility problems. Note that while GCC improvements are source of a few errors they are dwarfed by number of hardware compatibility errors. Most of the compiler problems happen when people forget to use appropriate constructs defined to make hardware happy: by some reason macroconstructs designed to fight hardware make code sidestep a wide range of undefined C behaviors. Think about it.

I don't think the case of signed overflow is one of trial and error versus reading specifications.

It is, as was explained before. There are other similar cases. For example standard gives you ability to convert pointer to int in some cases, but even then you can not convert int to pointer because on some platforms pointer is not just a number - yet people who don't know better often do that. Will you object if gcc and/or clang will start to miscompile such programs tomorrow?

It seems more like one of folk knowledge versus new optimizations --- old gcc on x86 and many similar platforms would use instructions that wrap around for signed overflow, so when compiling old code that targeted such platforms, it seems wise to use -fwrapv, and when writing new code it seems wise to add assertions to document why you do not expect overflow to occur.

Note that all these new optimizations are perfectly valid for the portable code. Surprisingly enough -fwrapv exist not to make broken programs valid but to make sure Java overflow semantic is implementable in GCC. Sure, you can use it in C, but it does not mean your code is suddenly correct after that.

Of course, reading the spec can be a pleasant experience independently from that.

Actually it's kind of sad that the only guide we have here is the standard... Given how often undefined behavior bites us you'd think we'll have books which explain where and how they can be triggered in "normal" code. Why people accept that i = i++ + ++i; is unsafe and unpredictable code but lots of other cases which trigger undefined behavior are perceived as safe? It's matter of education...

Also, why should the separate FPU affect the types foo and bar?

If FPU module is weakly tied to CPU module then you must explicitly synchronize them. Functions like mamcpy did that so they were safe, regular operations didn't. That's why standard only supports one way to do what you want and it's memcpy. Which is eliminated completely by modern compilers like or clang where it's not needed.

My code ran fine on systems with physically separate FPU (e.g., MIPS R2000+R2010).

Well, sure. Not all combinations were flaky. It does not change the fact that the only way to convert float to int safely was, is and will be memcpy (till the next redaction of C standard, at least).

But a compiler that miscompiles on hardware that's perfectly capable of doing what I intend (as evidenced by the fact that gcc-2.x -O and gcc-4.x -O0 achieve what I intend) is a totally different issue.

Why? Compiler just makes your hardware less predictable - but only till the boundaries outlined in the standard. That's what the compiler is supposed to do! These boundaries were chosen to support wide range of architectures and optimizations, but if you want different boundaries - feel free to create new language.

For now we work around the breakage of gcc-4.x, but the resulting code is not as fast and small as it could be; and we did not have to endure such pain with gcc-2.x.

This is possible but it just shows you need some different capabilities from your language. You can propose some extensions and/or optimizations to gcc and clang developers to make your code faster. Complains that your code does not work when it clearly violates the spec will lead you nowhere.

GCC and CLANG developers are not stuck up snobs, they are ready to add new extensions when it's needed (this changes the language spec and makes some previously undefined constructs defined), but they clearly are reluctant to try to guess what your code is doing without your help - if they have no clear guidance they use the spec.

The language implemented by gcc-2.x does support these practices.

Ok, if you like it, then use it.

We just need a compiler for this language that targets modern hardware.

No problem, it's there. It may look like a stupid excuse, but it's not. The only way to support something which exist only as implementation on newer platform is emulation. That's why there are all these PDP-11 emulators, NES emulators, etc.

If you want something different then first you must document your assumptions which don't adhere to the C99 spec and then talk with compiler developers.

So, the ANSI C specification and the language it specifies is pretty useless, because of these holes.

Huh? Where THIS comes from? Compiler does not know what the program actually does, but surely the programmer which wrote it does! S/he can avoid undefined behaviors - even if it's not always simple and/or easy. If the programmer likes to play Russian Roulette with the language - it's his/her choice, but then he should expect to be blown to bits from time to time.

Not just would it mean giving up on low-level code, the compiler could still decide to format the hard disk if it likes to, because most likely the code still contains some undefined behaviour.

Compiler can only do that if you trigger undefined behavior. Most undefined behaviors are pretty easy to spot and avoid but some of them are not. Instead of whining here and asking for the pie in the sky which will never materialize you can offer changes to the specifications which will simplify life of the programmer. Then they may be adopted either as extensions or as new version of C. It's supposed to be revised every 10 years, you know.

The kernel developers do what we do, they try to work around the gcc breakage, but I doubt that that's the situation they wish for.

Sure, but they use new GCC capabilities when they become available too and they accepted that they come as package deal. Note that kernel no longer support GCC 2.95 at all.

There was one time when kernel developers said what you are saying and refused to support newer versions of GCC but this lead them nowehere. Today linux kernel can be compiler with GCC 4.6 just fine.