| |||||||||||||
It's different viewpoints...It's different viewpoints...Posted May 24, 2011 8:05 UTC (Tue) by farnz (guest, #17727)In reply to: It's different viewpoints... by khim Parent article: What Every C Programmer Should Know About Undefined Behavior #3/3
But why do developers not realise that this is a problem? They're aware that triggering real machine undefined behaviour is a bad idea (e.g. poking random memory through a pointer set by casting the result of rand()). I think the model of C as a "high level assembler" is part of what triggers this misunderstanding in developers; if you think that the C compiler does some trivial optimisations (constant folding and the like), then spits out a program that works on the real hardware in roughly the same way that it would work if you'd hand-assembled the C code yourself, you don't stop and think "hang on a minute, this might be undefined behaviour - the compiler could do anything". Add to that the generally high quality of implementation of real compilers, such that undefined behaviour rarely bites you in the backside, and it can take a developer a long time to discover that their mental model of a C compiler as a thing that takes their input C code, and spits out machine code that does exactly what they would have done if they'd written the code in assembler for a machine they understand.
(Log in to post comments)
It's different viewpoints... Posted May 24, 2011 8:45 UTC (Tue) by etienne (subscriber, #25256) [Link]
Well, if I wanted to do a test tool for a library I may get the idea of calling functions with rand() or null pointers to see what happen...
It does bother me that the compiler would produce the message "your library is working perfectly" when in fact a wrong pointer may crash it... Same for debugging, I may want to display some binary values as unsigned in hexadecimal even if I know that is a float (so a dirty cast), to see if I had a memory overflow and in fact this float contains a string...
Sure, but then you deserve what you get... Posted May 24, 2011 10:05 UTC (Tue) by khim (subscriber, #9252) [Link] Same for debugging, I may want to display some binary values as unsigned in hexadecimal even if I know that is a float (so a dirty cast), to see if I had a memory overflow and in fact this float contains a string... Right, but how often you actually do that? Do you really want to punish the compiler and force it to keep "for loop iterative variable" in memory to make sure it's changed via float if the pointers are mixed just right? My favorite example is bug 33498. It's this piece of code: What does this piece of code do? Most people answer: it fills the table. Smart people answer: it efficiently fills the table of chars using trick with type conversions. At that point I show what it really does: it destroys your program. Oops? Nasty bug in the compiler? Nope: Status: RESOLVED INVALID. The problem with undefined behavior today is not that compilers peruse it for optimizations. It's the fact that they do it so carefully. That means that a lot of cases which should trigger undefined behavior don't blow up but silently work - this means people become complacent. Hopefully LTO will help: it'll allow the compiler to weed the undefined behavior branches more aggressively and this will mean people will be punished earlier and learn to look for undefined behavior cases.
Sure, but then you deserve what you get... Posted May 24, 2011 11:20 UTC (Tue) by farnz (guest, #17727) [Link] But look at comment 10 to that bug; Eric's not a fool, and yet his mental model of the C89 virtual machine tells him that the following code has implementation-defined semantics, not undefined semantics. In particular, he assumes that i will overflow in a defined fashion, although the final value is not predictable:
So, the question is why does Eric think that way? I would suggest that one reason is that an assembly language equivalent does have well-defined semantics (using an abstract machine that's a bit like ARM):
In this version of the code, which is roughly what an intuition of "C is a high level assembly language" would compile the source to,
If i was unsigned, and we changed INT_MAX to UINT_MAX, Eric would probably still have been surprised that his loop compiled to something like:
Assuming I'm right in thinking that it's the mental model caused by "C is a high level assembly language" that's breaking things, we have an open question: how do we change the way developers think about C such that perfectly correct compilers don't surprise them?
Sure, but then you deserve what you get... Posted May 24, 2011 15:16 UTC (Tue) by foom (subscriber, #14868) [Link]
I think it's pretty ridiculous that signed overflow is undefined but unsigned overflow is defined. That's an low-level accident of history (some architectures used 2's complement for signed values, some used 1's complement). That this mistake now gets used as a loophole to make programs be optimized better (or optimized into running incorrectly) is a nice trick, but doesn't really seem justifiable if you were going to do it again.
Signed overflow *ought to have been* implementation defined in C from the beginning, not undefined.
Sure, but then you deserve what you get... Posted May 24, 2011 16:08 UTC (Tue) by marcH (subscriber, #57642) [Link]
> That this mistake now gets used as a loophole to make programs be optimized better (or optimized into running incorrectly) is a nice trick,
I do not think this is a fair description of what gcc does here.
Please correct if I'm wrong: I think what happens here is just that gcc has a small and *unexpected* "overflow accident" while optimizing the end condition of the loop. And that is OK because signed overflows are simply not supported in C.
Of course it would be nice to have a warning; I guess the main article already explained why this is difficult.
Sure, but then you deserve what you get... Posted May 24, 2011 16:48 UTC (Tue) by farnz (guest, #17727) [Link] Reading the bug report, GCC specifically takes advantage of the undefinedness of signed overflow. We start with the following code (all code in a C-like pseudocode):
Step 1 of the failure determines that the only time val equals 0x04030200 is when the loop exit condition is true. It thus rewrites the program to look as if the programmer had written:
Next, GCC detects that in the absence of overflow, This code then translates using the naïve interpretation to the assembler output in the bug report. Note that a finite loop has become infinite; this is a useful optimization because it's not uncommon for real world code to have conditionals that depend solely on constants, such that for this build, the conditional is always true or always false.
Sure, but then you deserve what you get... Posted May 24, 2011 22:18 UTC (Tue) by marcH (subscriber, #57642) [Link]
I understand that there is a bad looking inconsistency between:
- optimization step 1 computes the result of a signed overflow - optimization step 2 assumes there is never any signed overflow
I did not like the "loophole" sentence because I (mis?)understood it as: "gcc is punishing everyone who has not read the standard, on purpose".
Sure, but then you deserve what you get... Posted May 24, 2011 23:14 UTC (Tue) by iabervon (subscriber, #722) [Link] Actually, I suspect that gcc actually transforms the condition to "val < 0x104030200". How would gcc, a C program, compute the result of a signed overflow without risking crashing? It's more comprehensible as "step 1 assumes that, because there is no signed overflow, the arbitrary-precision value of the expression 0x03020100 + (i*0x04040404) is the value of val; step 2 notices that the condition is always true due to the limited range of the variable." This also avoids the issue that it would be really hard to determine that "val != 0x04030200" is always true without determining that the code actually hits a signed overflow. Actually, the first transformed code is probably: int *value;
int val;
for (val = 0x03020100; val < 0x104030200; val += 0x04040404, value++)
*value = val;
Eliminating "i" is reasonably likely to be huge on x86 come register allocation, so it's a good optimization if it works. And gcc can assume it works because the programmer can't let signed arithmetic overflow. Of course, at this point, it already doesn't work as expected; the second optimization just makes the assembly confusing. The second optimization is really for "if (size >= 0x100000000) return -EINVAL;" where the programmer cares about a 32-bit limit in code that could be built with either 32-bit or 64-bit ints; in some builds it's important, and in all builds it's correct, but the compiler can eliminate it in cases where it doesn't matter.
Have you seen this page? Posted May 25, 2011 5:12 UTC (Wed) by khim (subscriber, #9252) [Link] 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.
Have you seen this page? Posted May 25, 2011 5:44 UTC (Wed) by iabervon (subscriber, #722) [Link] Those libraries compute the well-defined results of calculations with large numbers; they don't give the result of signed overflow. They aren't going to help for figuring out the results of running (unoptimized, on the target machine):
if (MAXINT + 1 == -MAXINT) printf("Wow, 1's complement!\n");
because that's a matter of processor architecture, not mathematics. And certainly gcc isn't going to try eliciting the undefined behavior itself and replicating it, because the undefined behavior might be "your compiler crashes processing unreachable code", which the C specification doesn't allow.
Have you seen this page? Posted May 26, 2011 8:27 UTC (Thu) by marcH (subscriber, #57642) [Link]
> Those libraries compute the well-defined results of calculations with large numbers; they don't give the result of signed overflow.
Of course they can do this; the latter is just one modulus operation away from the former.
> because that's a matter of processor architecture, not mathematics.
Surprise: processors architectures are rooted in arithmetics. All of them, even though they differ with each other.
Have you seen this page? Posted May 27, 2011 9:45 UTC (Fri) by dgm (subscriber, #49227) [Link]
> Surprise: processors architectures are rooted in arithmetics. All of them, even though they differ with each other.
Still not a matter of mathematics: both 1's and 2's compliment are equally correct. The matter is about the choice made by the processor designers, and thus, a matter of processor architecture.
Have you seen this page? Posted May 27, 2011 14:03 UTC (Fri) by marcH (subscriber, #57642) [Link]
It's a matter of both: 1. Choose the architecture, 2. Apply the maths specific to this architecture.
GMP or else can help for the latter (of course not for the former).
Sure, but then you deserve what you get... Posted May 25, 2011 1:27 UTC (Wed) by foom (subscriber, #14868) [Link]
Yes, it has optimization benefits. That doesn't mean it's actually a good feature.
Overloading "signedness" with "cannot overflow" makes no sense, it's simply an accident of history.
Of course, assuming that an unsigned int cannot overflow would also have optimization benefits! 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"?
Sure, but then you deserve what you get... Posted May 25, 2011 2:48 UTC (Wed) by iabervon (subscriber, #722) [Link]
Actually, if the compiler were forced to consider overflow, it would just have to think a little harder before making the same optimizations. The compiler could determine that 1<<32 / GCD(1<<32, 0x04040404) > 256/64 and thus that the first time i >= 256/64, 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.)
Sure, but then you deserve what you get... Posted May 25, 2011 3:31 UTC (Wed) by iabervon (subscriber, #722) [Link] 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...).
Sure, but then you deserve what you get... Posted May 26, 2011 17:21 UTC (Thu) by anton (guest, #25547) [Link] 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"?It gets slower? Doesn't the code with int loop infinitely when compiled with gcc? Great optimization!
Sure, but then you deserve what you get... Posted May 28, 2011 20:48 UTC (Sat) by BenHutchings (subscriber, #37955) [Link] 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, but then you deserve what you get... Posted May 28, 2011 20:46 UTC (Sat) by BenHutchings (subscriber, #37955) [Link] Signed overflow *ought to have been* implementation defined in C from the beginning, not undefined. Signed overflow results in an exception on some processors. So the range of permissible implementation-defined behaviour would have to include: the program aborts. Slightly better than the current situation, but not much.
Unsigned versus signed Posted May 24, 2011 12:58 UTC (Tue) by cesarb (subscriber, #6266) [Link]
Wow...
That was an impressive one. I did not expect gcc to use *val* for the loop condition.
I think this is yet one more point in favor of a personal rule of "always use unsigned unless you have a good reason to use signed" (that is, use "unsigned" by default when programming). If you followed that rule, all three "int" on this function would become "unsigned int", since there is no good reason to use signed here.
Sure, but then you deserve what you get... Posted May 25, 2011 10:14 UTC (Wed) by welinder (guest, #4699) [Link]
That piece of code does not invoke undefined behaviour unless
"int" is too small to hold whatever value things sum up to.
This program may also invoke undefined behaviour:
int main (int argc, char **argv) { return 65535+1; }
Sure, but then you deserve what you get... Posted May 26, 2011 17:05 UTC (Thu) by anton (guest, #25547) [Link] Do you really want to punish the compiler and force it to keep "for loop iterative variable" in memory to make sure it's changed via float if the pointers are mixed just right?Sure, if I keep an induction variable in a global variable, static variable or an auto variable that I take the address of, I expect that variable to be in memory and to be fetched from there and/or stored there whenever I access it. What's this nonsense about punishing the compiler? It's a thing without feelings, it cannot be punished. If it's a good compiler, it will do what I expect. Unfortunately, the most popular compilers become worse and worse with every release. I would welcome the world that you dream of where these compilers miscompile every significant program. Then the pain would be so large that we all (well, you and a few others excepted) would finally scratch our itch and write a compiler that does not do any of that nonsense, and gcc etc. would go the way of XFree86, like they should.
Oh, forgot to say... Posted May 24, 2011 10:19 UTC (Tue) by khim (subscriber, #9252) [Link] Same for debugging, I may want to display some binary values as unsigned in hexadecimal even if I know that is a float (so a dirty cast), to see if I had a memory overflow and in fact this float contains a string... Note that ANSI C standard does not consider this use case important enough to you can not ever convert print float as hex (it's even explained in wikipedia article) without triggering undefined behavior - but GNU C gives you such ability if you'll use union. This is enough for debugging, but please don't leave it in your program afterwards: GCC is not the only compiler in the world, you don't want to see your program broken later.
Oh, forgot to say... Posted May 24, 2011 18:35 UTC (Tue) by jrn (subscriber, #64214) [Link]
Wouldn't a loop to access the internal representation of a float through a pointer to char produce implementation-defined behavior, rather than nasal demons? On the other hand, reading through a pointer to unsigned int is problematic, of course.
Yes, that's true... Posted May 25, 2011 5:01 UTC (Wed) by khim (subscriber, #9252) [Link] Ah, my bad. Sure, but the temptation is very high to use conversion to int because they are of the same size - and this is impossible to do even if you use two transitions like (int *)(char *)pf. The only way to portably and correctly do that is via memcpy - and with current crop of the compilers it's quite efficient too (both memcpy and pointers will be elided), but this is counter-intuitive if you don't know about undefined behaviors and still think that C is high-level assembler.
Yes, that's true... Posted May 25, 2011 5:19 UTC (Wed) by jrn (subscriber, #64214) [Link]
Even memcpy is not portable to platforms where sizeof(float) != sizeof(int). :)
A rough and incomplete rule of thumb about aliasing rules is that constructs that would be portable given how alignment and size varies from platform to platform are likely to be permitted.
|
|||||||||||||