If anything's messed up, then that would be my doing.
I thought at first that some of the words in the piece were distorted as a joke about undefined behavior, but as I look at the source, I think something is just broken with the custom fonts.
If signed overflow were defined, then 12 * i + 8 would have to have correct overflow behaviour for 32-bit values and so this trick couldn't be done.
I feel like this misses the difference between "undefined" and "implementation defined". Despite the example given, those of us (like me) who complain about compilers removing safety checks rarely claim that signed 32-bit ints must have guaranteed behavior on overflow. Overflowing might be easiest, if that's what the hardware does naturally, but it doesn't have to be defined to do this.
In our minds, it would be just fine for the compiler to generate an "add" instruction and let the registers fall where they may. What we object to is the compiler's reasoning that since "undefined behavior can be presumed not to occur, I'll just delete this spurious NULL check that the programmer accidentally put here".
Granted, there are cases where a compiler can take proper advantage of such optimizations, but it's emphatically not the case that the only alternative to the current "nasal daemon" approach is disabling all loop optimizations. Simply changing "undefined" to "implementation defined" would satisfy a majority of the objections.
What always surprises me is that, when a new optimization comes out justified by a sentence in a dark corner of the C standard, you can usually trace the sentence back all the way to C90.
>the members of the committee were rubbing their hands at the thought of all the optimizations the poorly specified ambiguous successive versions of the document would allow:
You are right. Either I was thinking of another comment by Derek Jones (one of the two persons I know on the C standardization committee, which is otherwise quite opaque) or I projected my own image of a patiently malevolent committee on the phrase “doing stuff that we could only dream about back in the day” that he did not mean this way.
> Granted, there are cases where a compiler can take proper advantage of such optimizations, but it's emphatically not the case that the only alternative to the current "nasal daemon" approach is disabling all loop optimizations. Simply changing "undefined" to "implementation defined" would satisfy a majority of the objections.
No. Since a huge number of loop optimizations are dependent on trip count detection, this is not in fact the case. Loop trip count detection is ruined by making signed overflow implementation defined.
Additionally, there's less of a difference between "undefined" and "implementation defined" than you might think. Consider the example in the original post:
if (x + y < x) {
return 0; /* Overflow */
}
length = x + y;
With implementation defined overflow, the compiler is still free to remove this check, because the value of "x + y" would become an undefined value on overflow, and comparisons on undefined values are themselves undefined. If you want the compiler to do anything else, then you're proposing a drastic overhaul of (for example) LLVM's notion of "undef" [1], one that would have massive consequences for optimization.
Since a huge number of loop optimizations are dependent on trip count detection, this is not in fact the case. Loop trip count detection is ruined by making signed overflow implementation defined.
Could you offer a good example of a loop where performance of a human written lop would suffer if the loop counter was changed from int64_t to uint64_t? I'm sure they exist, but I wonder if I'm underestimating the severity.
With implementation defined overflow, the compiler is still free to remove this check, because the value of "x + y" would become an undefined value on overflow
Well, no, at least the way I'm viewing "implementation defined". If the signed addition is implementation defined, I'd think that by definition "x + y" never becomes an undefined value.
As I'm sure you realize (but others might not), x64 doesn't have separate add-signed-32-bit and add-unsigned-32-bit instructions. So on x64, I'd hope that a sane implementation would simply define signed addition as "ask the processor to add x to y and interpret the result as signed".
I don't think this would require any overhaul of the notion of "undef"?
> Well, no, at least the way I'm viewing "implementation defined". If the signed addition is implementation defined, I'd think that by definition "x + y" never becomes an undefined value.
See my other reply. A compiler can legally rewrite the expression into "(uint64_t)x + (uint64_t)y > UINT_MAX ? undef : true" per your rule.
For bonus points you could write this as part of the compiler support library to derive the types and limits automatically, or even define it as part of the compiler. Why do GCC/clang not have:
The problem with solutions like this is that they break the abstraction of using algebraic notation for calculations. We're conditioned to expect calculations to be written in algebraic notation, and indeed one of the original selling points of C is that it lets you express calculations in that form. To undo that is a massive shame.
The calculation itself absolutely MUST look like this:
a + b
While maybe it's not too bad for simple addition, think of compound expressions with multiple terms.
A compiler can legally rewrite the expression into "(uint64_t)x + (uint64_t)y > UINT_MAX ? undef : true" per the rule suggested by nkurz. This makes the undef value show up.
> Given that the size of a Point is 12 bytes, the reference to the z members of points is turned into points + (12 * i + 8).
No, it's not. In the C abstract machine, arithmetic on pointers is not the same as arithmetic on integers.
This really is "points + i", but on pointers to an object with sizeof 12, and then a dereference with an offset of 8. These pointers don't have the overflow undefined behavior (but do have other undefined behavior if you have a pointer outside a C object). As implemented in assembly, yes, it comes to a multiplying by 12, but that's not a C int at that point. (And can be done with addressing trickery, as the article says.)
Perhaps someone who has a better grasp of the standard can correct me, but as far as I can tell, your interpretation is correct and the given example is not undefined behavior.
From 6.5.2.1 (Array Subscripting) of the C11 draft:
"A postfix expression followed by an expression in square brackets [] is a subscripted designation of an element of an array object. The definition of the subscript operator []
is that E1[E2] is identical to (*((E1)+(E2))). Because of the conversion rules that apply to the binary + operator, if E1 is an array object (equivalently, a pointer to the
initial element of an array object) and E2 is an integer, E1[E2] designates the E2-th element of E1 (counting from zero)."
From 6.5.6 (Additive Operators):
"When an expression that has integer type is added to or subtracted from a pointer, the result has the type of the pointer operand. If the pointer operand points to an element of an array object, and the array is large enough, the result points to an element offset from the original element such that the difference of the subscripts of the resulting and original array elements equals the integer expression. [...] If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the behavior is undefined."
To me, those sections together read that there should be no overflow as long as i is smaller than the length of `points` + 1, and thus no undefined behavior. Does anyone have another interpretation?
Nope, you're correct. On the other hand, earlier today I read a post about a pretty similar-seeming phenomenon (signed overflow UB reducing the number of lea instructions that have to be generated):
Perhaps the author had heard that -fwrapv causes extra 'lea's but got mixed up as to why. (TL;DR: it makes it harder for the compiler to prove that you're not a sadist using negative array indices.)
I was talking about the addressing at the assembly level, because that's what LEA and addressing modes deal with. However, your references to a spec make a very good point. Maybe I misunderstood Chandler in the first place.
I've pulled the post (since it may be incorrect) until I can sort it out with a compiler person.
I work on a piece of high-performance C++ code. Anything that can make us 1% faster than the competition would be welcome, given that our product often runs number crunching tasks for months. We compile all our code with -fwrapv, because fuck trying to guess how the compiler would "optimise" the code.
On the other hand, using nonstandard extensions makes it harder to move away from a compiler the direction of which you are not happy with, and can make your situation worse in the long term.
Looks like Safari is no longer rendering the fonts correctly. (It used to work but I hesitate to blame Safari because font files are complex and maybe there's a problem with the ones that I'm using.) I've dropped the custom font now.
(UINT_MAX - x < y) is wrong, if x and y are both of type int, it should be: (INT_MAX - x < y), which is defined and will yield true, if an overflow on x+y would happen.
Signed overflow optimization is just a cheap trick for avoiding the need to do real bounds analysis. Every single loop optimization possible by abusing signed overflow is also possible with unsigned values (and thus implementation-defined signed overflow) if you can prove your bounds.
I'm sick and tired of compiler authors whining about how we "need" undefined signed overflow for optimization, particularly because I usually use unsigned loop counters and so don't benefit from this optimization, but would benefit from real, robust bounds analysis that worked for both signed and unsigned types.
An interesting pet project for someone to attempt would be a language with fully-specified arithmetic.
So rather than declaring vaguely that you want an "integer", you'd specify bounds, signed-ness (two or one's complement), and what happens on overflowing the bounds (wrap / saturate / exception / trap / set flag / set NAN etc.)
Saturated arithmetic intrinsics are widely available but generally not used by generated code. Similarly I've never seen an attempt at doing "integer NaN", which could be quite useful in some situations.
You'd probably also want some flags to say "give me a compiler error or warning if this code doesn't compile to intrinsics and is being emulated instead".
Hmm, I can see why that would be useful but that makes it much harder to reason about in order to automatically eliminate checks wherever possible; you can guarantee that adding a number in [0,100) to [0,100) will produce a number in [0,200) without needing to apply checks, but one of your Values may generate an error if you just increment it.
Compilers already reason about values like that. They can prove certain bits in an integer to have certain values, etc, not just about ranges. Actual checks could be optimized away pretty often.
Simple example: Say, you multiply a number by two. From that, the compiler data flow analysis knows the lowest bit can only be zero. So it can safely optimize away anything that checks that bit.
Interestingly, arithmetic on the Mill CPU does this (at the machine level instead of at the language level). You can get modulo addition, saturating addition, widening addition, and excepting addition.
53 comments
[ 2.0 ms ] story [ 101 ms ] threadI thought at first that some of the words in the piece were distorted as a joke about undefined behavior, but as I look at the source, I think something is just broken with the custom fonts.
If signed overflow were defined, then 12 * i + 8 would have to have correct overflow behaviour for 32-bit values and so this trick couldn't be done.
I feel like this misses the difference between "undefined" and "implementation defined". Despite the example given, those of us (like me) who complain about compilers removing safety checks rarely claim that signed 32-bit ints must have guaranteed behavior on overflow. Overflowing might be easiest, if that's what the hardware does naturally, but it doesn't have to be defined to do this.
In our minds, it would be just fine for the compiler to generate an "add" instruction and let the registers fall where they may. What we object to is the compiler's reasoning that since "undefined behavior can be presumed not to occur, I'll just delete this spurious NULL check that the programmer accidentally put here".
Granted, there are cases where a compiler can take proper advantage of such optimizations, but it's emphatically not the case that the only alternative to the current "nasal daemon" approach is disabling all loop optimizations. Simply changing "undefined" to "implementation defined" would satisfy a majority of the objections.
http://shape-of-code.coding-guidelines.com/2014/08/31/undefi...
What always surprises me is that, when a new optimization comes out justified by a sentence in a dark corner of the C standard, you can usually trace the sentence back all the way to C90.
I couldn't find that in the blog post you linked?
I have edited my comment.
No. Since a huge number of loop optimizations are dependent on trip count detection, this is not in fact the case. Loop trip count detection is ruined by making signed overflow implementation defined.
See this thread from just last week explaining this: https://news.ycombinator.com/item?id=11653940
Additionally, there's less of a difference between "undefined" and "implementation defined" than you might think. Consider the example in the original post:
With implementation defined overflow, the compiler is still free to remove this check, because the value of "x + y" would become an undefined value on overflow, and comparisons on undefined values are themselves undefined. If you want the compiler to do anything else, then you're proposing a drastic overhaul of (for example) LLVM's notion of "undef" [1], one that would have massive consequences for optimization.[1]: http://llvm.org/docs/LangRef.html#undefined-values
Could you offer a good example of a loop where performance of a human written lop would suffer if the loop counter was changed from int64_t to uint64_t? I'm sure they exist, but I wonder if I'm underestimating the severity.
With implementation defined overflow, the compiler is still free to remove this check, because the value of "x + y" would become an undefined value on overflow
Well, no, at least the way I'm viewing "implementation defined". If the signed addition is implementation defined, I'd think that by definition "x + y" never becomes an undefined value.
As I'm sure you realize (but others might not), x64 doesn't have separate add-signed-32-bit and add-unsigned-32-bit instructions. So on x64, I'd hope that a sane implementation would simply define signed addition as "ask the processor to add x to y and interpret the result as signed".
I don't think this would require any overhaul of the notion of "undef"?
See my other reply. A compiler can legally rewrite the expression into "(uint64_t)x + (uint64_t)y > UINT_MAX ? undef : true" per your rule.
But they do: https://news.ycombinator.com/item?id=11711608 :-)
Both GCC and Clang have __builtin_add_overflow, which as far as I can tell do exactly what you're proposing.
I think they can be fixed with sensible macros, though:
Hopefully the compiler would optimise: to only do the addition once.The calculation itself absolutely MUST look like this:
While maybe it's not too bad for simple addition, think of compound expressions with multiple terms.No. If `x + y < x` is "implementation defined", then an "undef" value would never even come into existence!
No, it's not. In the C abstract machine, arithmetic on pointers is not the same as arithmetic on integers.
This really is "points + i", but on pointers to an object with sizeof 12, and then a dereference with an offset of 8. These pointers don't have the overflow undefined behavior (but do have other undefined behavior if you have a pointer outside a C object). As implemented in assembly, yes, it comes to a multiplying by 12, but that's not a C int at that point. (And can be done with addressing trickery, as the article says.)
From 6.5.2.1 (Array Subscripting) of the C11 draft:
"A postfix expression followed by an expression in square brackets [] is a subscripted designation of an element of an array object. The definition of the subscript operator [] is that E1[E2] is identical to (*((E1)+(E2))). Because of the conversion rules that apply to the binary + operator, if E1 is an array object (equivalently, a pointer to the initial element of an array object) and E2 is an integer, E1[E2] designates the E2-th element of E1 (counting from zero)."
From 6.5.6 (Additive Operators):
"When an expression that has integer type is added to or subtracted from a pointer, the result has the type of the pointer operand. If the pointer operand points to an element of an array object, and the array is large enough, the result points to an element offset from the original element such that the difference of the subscripts of the resulting and original array elements equals the integer expression. [...] If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the behavior is undefined."
To me, those sections together read that there should be no overflow as long as i is smaller than the length of `points` + 1, and thus no undefined behavior. Does anyone have another interpretation?
https://gist.github.com/rygorous/e0f055bfb74e3d5f0af20690759...
Perhaps the author had heard that -fwrapv causes extra 'lea's but got mixed up as to why. (TL;DR: it makes it harder for the compiler to prove that you're not a sadist using negative array indices.)
I've pulled the post (since it may be incorrect) until I can sort it out with a compiler person.
https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins...
http://clang.llvm.org/docs/LanguageExtensions.html#checked-a...
http://i.imgur.com/tryjhMi.png
(UINT_MAX - x < y) is wrong, if x and y are both of type int, it should be: (INT_MAX - x < y), which is defined and will yield true, if an overflow on x+y would happen.
As for securely implementing overflow checks for signed addition, this seems to be useful: http://blog.regehr.org/archives/1139
https://huonw.github.io/blog/2016/04/myths-and-legends-about...
tl;dr:debug mode checks for overflow and panics when it happens; release mode is defined to wrap as two's complement
I'm sick and tired of compiler authors whining about how we "need" undefined signed overflow for optimization, particularly because I usually use unsigned loop counters and so don't benefit from this optimization, but would benefit from real, robust bounds analysis that worked for both signed and unsigned types.
So rather than declaring vaguely that you want an "integer", you'd specify bounds, signed-ness (two or one's complement), and what happens on overflowing the bounds (wrap / saturate / exception / trap / set flag / set NAN etc.)
Saturated arithmetic intrinsics are widely available but generally not used by generated code. Similarly I've never seen an attempt at doing "integer NaN", which could be quite useful in some situations.
You'd probably also want some flags to say "give me a compiler error or warning if this code doesn't compile to intrinsics and is being emulated instead".
Like this:
(Value >= 0 && Value <= 1000 && (Value & 1) == 0) || Value in(value_enum)
Would limit Value to even numbers between [0 .. 1000] except if it's an enum (for error values).
Simple example: Say, you multiply a number by two. From that, the compiler data flow analysis knows the lowest bit can only be zero. So it can safely optimize away anything that checks that bit.
http://millcomputing.com/wiki/Instruction_Set_by_Category#Si...