Signed overflow in C
imperialviolet.org
imperialviolet.org
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.
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:
if (x + y < x) {
return 0; /* Overflow */
}
length = x + y;
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.
if (x + y < x)
if (ADDITION_WOULD_OVERFLOW_INT(x, y))
{
...
}
#define ADDITION_WOULD_OVERFLOW_INT(a, b) \
(((a) > 0 && (b) > 0 && (b) > INT_MAX - (a)) || \
((a) < 0 && (b) < 0 && (b) < INT_MIN - (a)))
__builtin_addition_would_overflow(a, b)
?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:
#define ADDITION_WOULD_OVERFLOW(a, b) \
({ typeof((a) + (b)) __r; __builtin_add_overflow((a), (b), &__r); })
if (ADDITION_WOULD_OVERFLOW(a, b))
{
return 0;
}
return a + b;
0000000000400560 <maybe_overflow>:
400560: 01 f7 add %esi,%edi
400562: 70 03 jo 400567 <maybe_overflow+0x7>
400564: 89 f8 mov %edi,%eax
400566: c3 retq
400567: 31 c0 xor %eax,%eax
400569: c3 retq #define ADD_OR_DEFAULT(a, b, d) \
({ typeof((a) + (b)) r; __builtin_add_overflow((a), (b), &r) ? (d) : r; })
return ADD_OR_DEFAULT(a, b, 0);
The calculation itself absolutely MUST look like this:
a + b
No. If `x + y < x` is "implementation defined", then an "undef" value would never even come into existence!
https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins...
http://clang.llvm.org/docs/LanguageExtensions.html#checked-a...
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...
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.
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.
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
As for securely implementing overflow checks for signed addition, this seems to be useful: http://blog.regehr.org/archives/1139