6 ms·

EDIT: I see- a different reading of the post than my original take would suggest that the author is saying, you as a C/C++ programmer are "not allowed" to compi

EDIT: I see- a different reading of the post than my original take would suggest that the author is saying, you as a C/C++ programmer are "not allowed" to compile code that would cause under/overflow. The compiler assumes that you are following this rule, enabling these optimizations. The author's wording is unclear as to who or what is not being allowed to under/overflow, hence my confusion. --- Right off the bat- > Signed integers are not allowed to wrap in C and C++ What? This is...not true. $ cat > test.c #include <stdio.h> #include <limits.h> int main() { int i = INT_MAX; printf("%i\n%i\n", i, i+1); } $ cc test.c $ ./a.out 2147483647 -2147483648 Im not an expert on these matters, but I suspect signed integers are not defined as wrapping and in fact not defined as doing anything particular in under/overflow situations, though in one common convention, two's complement integer arithmetic, they often do. The optimizations rely on the fact that the programmer can't depend on any specific overflow or underflow behavior.

hyperpape 11y ago
You are incorrect, or perhaps correct in a nit picky way[0]. It is undefined behavior, as any Google search can tell you. Your compiler is just being nice--it is allowed to print "screw you" as the result of that program. For more about undefined behavior, try here: http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html?m=1 http://blog.llvm.org/2011/05/what-every-c-programmer-should-... [0] Since its undefined behavior, the compiler can choose to wrap it. If that's what you're saying, I think it's pretty confusing expressed the way you did. In spite of that, a well defined C program is not allowed to overflow, and a compiler can compile a program that overflows it absolutely any way it chooses to. It is in fact able to optimize the program based on the assumption that the overflow cannot happen, even if it is actually possible.
- geofft 11y ago
  I think 'ssalazar is interpreting the phrase "not allowed to wrap" to mean "if the C compiler causes them to wrap, it is violating the spec". Undefined behavior means anything is allowed; this includes reasonable behavior. (Remember that undefined behavior exists for the purpose of allowing optimizations. Adding code to print "screw you" is rarely an optimization. Doing just what the programmer expected is usually an optimization, which is why UB is so tricky; it's just not always an optimization, and doing something unexpected might be faster.)
  - hyperpape 11y ago
    You're right. I added a note when I thought of this, and if that's what the parent meant, I think it's an exceedingly unhelpful addition.
- cnvogel 11y ago
  What you say is correct, but I think people are not helping the discussion by adding correct but misleading statements such as "the compiler is allowed to print 'screw you'". To me it sounds as if the compiler would be trying hard to find an opportunity to sneak in malicious code -- and then shout "told you so!" into my face with an ugly grin. The core of undefined behavior, for me, is the following: The compiler will, during optimization, convert your program (as written) into a second program (in its intermediate language, data-structures, assembler code, ...). This second program is identical to the program as written by you only regarding the defined behavior, and the transformation might not be obvious. For some optimizations (automatic vectorization, multithreading, ...) it will be pretty convoluted. For some simpler one, it might just replace mults by shifts or remove an unnecessary check here and there. If you rely on undefined behavior for calculation, branches, loops (such as INT_MAX+1 < INT_MAX), the compiler may create such a second program which behaves as if a branch may (or may not) be taken, a loop may, or may not terminate, or have a few iterations more or less. Unfortunately some of the statements that got replaced or mangled could be needed to guard certain invariants, avoid smashing the stack or accessing an array within bounds. And when you loose these guarantees, of course all bets are off as you might start executing random code from the data your program is trying to process (unintentionally, or maliciously crafted). A simple if(i+1<i){...} never was replaced by puts("screw you"), I'm almost... well... hardly... ...it might only happen rarely. :-)
  - hyperpape 11y ago
    It's a variant of the "nasal demons" comment, but you might be right. I don't know if that kind of phrase is helpful or not.
xentronium 11y ago
Oh, you're in for a surprise. http://blog.robertelder.org/signed-or-unsigned/ http://blog.robertelder.org/signed-or-unsigned/
geofft 11y ago
It's a little subtler than that. Wrapping two's complement arithmetic is a function of your CPU, not your compiler. Right now, those numbers are being handed directly to the CPU, because the compiler doesn't care what happens in the case of signed overflow. The CPU chooses to implement wrapping arithmetic. However, the compiler might do something to your program's control flow long before it hits the CPU's arithmetic instructions. For instance, try compiling this function under optimization: titan:/tmp geofft$ cat test.c int test(int x) { if (x > 0) return 1; x -= 10; if (x > 0) { return 2; } return 1; } titan:/tmp geofft$ cc -O3 -c test.c titan:/tmp geofft$ objdump -S test.o test.o: file format elf64-x86-64 Disassembly of section .text: 0000000000000000 <test>: 0: b8 01 00 00 00 mov $0x1,%eax 5: c3 retq The compiler makes no promises about what happens in the case of signed integer overflow or underflow. In this case, for numbers in [INT_MIN, INT_MIN + 10), it doesn't promise that wrapping happens -- even though, if it were to actually do the math on my CPU, it would end up with two's complement. So it assumes the second if can never be true if the first if is untrue, and optimizes the function to return a constant 1. I think you're right that the phrasing is sloppy, and should be "Signed integers are not allowed to overflow or underflow in C and C++," making it an obligation on the programmer not to overflow. If you're interpreting it as an obligation on the compiler not to implement wrapping, then yeah, that's incorrect.
- asgfoi 11y ago
  Nice example. More people should know that the second if statement is unreachable code.
- nkurz 11y ago
  titan:/tmp geofft$ cc -O3 -c test.c Is your use of 'cc' instead of 'gcc' intentional here? It implies that all compilers make this "optimization", but I think it's currently only GCC. ICC, Clang, and MSVC continue to work that way that the programmer intended: Godbolt for ICC and Clang http://goo.gl/jFfvyz http://goo.gl/jFfvyz, MSVC http://webcompiler.cloudapp.net/ http://webcompiler.cloudapp.net/. While it would be unwise to rely on this "polite" behavior from a compiler, I find it difficult to argue that GCC does a better job of compiling this particular code. But perhaps the speedup on similar code is enough to justify the occasional insidious bug? It would be nice if there was a GCC option that produced a warning here. Is there one?
mikeash 11y ago
It is absolutely true. Your test program is not well formed. The result of overflowing or underflowing a signed integer is undefined. What's tripping you up is that C can be very lax with stuff it doesn't allow. Some stuff is required to generate a compiler error, like if you try to start a variable name with a number. Some stuff is just "undefined behavior" which means the compiler can basically do whatever it wants. Undefined behavior is often referred to as "nasal demons" because it would be perfectly legal for a conforming C compiler which encounters undefined behavior to make demons fly out of your nose. This is impractical, but real-world compilers can and do crash or silently emit unexpected values in this case. The most confusing part of this is that a subset of undefined behavior is doing what you want it to do. That's what you're encountering here. The moment you do i+1 you've hit undefined behavior. In this particular case, the compiler is emitting code that causes the value to wrap, which is what you expected. This is still undefined behavior, which means your program is ill formed, and the compiler can change its mind and betray you at any moment!
cnvogel 11y ago
Here's an example indicating how we can use overflow from INT_MAX to INT_MIN to terminate a loop... ...if signed overflow would be properly defined. /* Write \"hi\" n times, counter will wrap to negative * to indicate we've written enough greetings. * * i=3 -> we want to write hi three times * * 1st INT_MAX-i+1 = INT_MAX-2 -> write hi * 2nd INT_MAX-1 -> write hi * 3rd INT_MAX -> write hi * 4th INT_MIN (signed overflow, terminates loop) */ int write_n_times_hi(int i) { int j; for (j=INT_MAX-i+1; j>0; j++) printf("hi\n"); return i; } This will be compiled into an endless loop by gcc 5.3.0/x86_64 for -O3, but will terminate properly with -O0. If you change the (undefined for j=INT_MAX) j++ into the (defined) *((unsigned*)&j)++, the compiler may no longer assume that j stays >0 all of the time, and the loop has to terminate.

hyperpape 11y ago

You are incorrect, or perhaps correct in a nit picky way[0]. It is undefined behavior, as any Google search can tell you. Your compiler is just being nice--it is allowed to print "screw you" as the result of that program. For more about undefined behavior, try here: http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html?m=1 http://blog.llvm.org/2011/05/what-every-c-programmer-should-... [0] Since its undefined behavior, the compiler can choose to wrap it. If that's what you're saying, I think it's pretty confusing expressed the way you did. In spite of that, a well defined C program is not allowed to overflow, and a compiler can compile a program that overflows it absolutely any way it chooses to. It is in fact able to optimize the program based on the assumption that the overflow cannot happen, even if it is actually possible.

geofft 11y ago
I think 'ssalazar is interpreting the phrase "not allowed to wrap" to mean "if the C compiler causes them to wrap, it is violating the spec". Undefined behavior means anything is allowed; this includes reasonable behavior. (Remember that undefined behavior exists for the purpose of allowing optimizations. Adding code to print "screw you" is rarely an optimization. Doing just what the programmer expected is usually an optimization, which is why UB is so tricky; it's just not always an optimization, and doing something unexpected might be faster.)
- hyperpape 11y ago
  You're right. I added a note when I thought of this, and if that's what the parent meant, I think it's an exceedingly unhelpful addition.
cnvogel 11y ago
What you say is correct, but I think people are not helping the discussion by adding correct but misleading statements such as "the compiler is allowed to print 'screw you'". To me it sounds as if the compiler would be trying hard to find an opportunity to sneak in malicious code -- and then shout "told you so!" into my face with an ugly grin. The core of undefined behavior, for me, is the following: The compiler will, during optimization, convert your program (as written) into a second program (in its intermediate language, data-structures, assembler code, ...). This second program is identical to the program as written by you only regarding the defined behavior, and the transformation might not be obvious. For some optimizations (automatic vectorization, multithreading, ...) it will be pretty convoluted. For some simpler one, it might just replace mults by shifts or remove an unnecessary check here and there. If you rely on undefined behavior for calculation, branches, loops (such as INT_MAX+1 < INT_MAX), the compiler may create such a second program which behaves as if a branch may (or may not) be taken, a loop may, or may not terminate, or have a few iterations more or less. Unfortunately some of the statements that got replaced or mangled could be needed to guard certain invariants, avoid smashing the stack or accessing an array within bounds. And when you loose these guarantees, of course all bets are off as you might start executing random code from the data your program is trying to process (unintentionally, or maliciously crafted). A simple if(i+1<i){...} never was replaced by puts("screw you"), I'm almost... well... hardly... ...it might only happen rarely. :-)
- hyperpape 11y ago
  It's a variant of the "nasal demons" comment, but you might be right. I don't know if that kind of phrase is helpful or not.

xentronium 11y ago

Oh, you're in for a surprise. http://blog.robertelder.org/signed-or-unsigned/ http://blog.robertelder.org/signed-or-unsigned/

geofft 11y ago

It's a little subtler than that. Wrapping two's complement arithmetic is a function of your CPU, not your compiler. Right now, those numbers are being handed directly to the CPU, because the compiler doesn't care what happens in the case of signed overflow. The CPU chooses to implement wrapping arithmetic. However, the compiler might do something to your program's control flow long before it hits the CPU's arithmetic instructions. For instance, try compiling this function under optimization: titan:/tmp geofft$ cat test.c int test(int x) { if (x > 0) return 1; x -= 10; if (x > 0) { return 2; } return 1; } titan:/tmp geofft$ cc -O3 -c test.c titan:/tmp geofft$ objdump -S test.o test.o: file format elf64-x86-64 Disassembly of section .text: 0000000000000000 <test>: 0: b8 01 00 00 00 mov $0x1,%eax 5: c3 retq The compiler makes no promises about what happens in the case of signed integer overflow or underflow. In this case, for numbers in [INT_MIN, INT_MIN + 10), it doesn't promise that wrapping happens -- even though, if it were to actually do the math on my CPU, it would end up with two's complement. So it assumes the second if can never be true if the first if is untrue, and optimizes the function to return a constant 1. I think you're right that the phrasing is sloppy, and should be "Signed integers are not allowed to overflow or underflow in C and C++," making it an obligation on the programmer not to overflow. If you're interpreting it as an obligation on the compiler not to implement wrapping, then yeah, that's incorrect.

asgfoi 11y ago
Nice example. More people should know that the second if statement is unreachable code.
nkurz 11y ago
titan:/tmp geofft$ cc -O3 -c test.c Is your use of 'cc' instead of 'gcc' intentional here? It implies that all compilers make this "optimization", but I think it's currently only GCC. ICC, Clang, and MSVC continue to work that way that the programmer intended: Godbolt for ICC and Clang http://goo.gl/jFfvyz http://goo.gl/jFfvyz, MSVC http://webcompiler.cloudapp.net/ http://webcompiler.cloudapp.net/. While it would be unwise to rely on this "polite" behavior from a compiler, I find it difficult to argue that GCC does a better job of compiling this particular code. But perhaps the speedup on similar code is enough to justify the occasional insidious bug? It would be nice if there was a GCC option that produced a warning here. Is there one?

mikeash 11y ago

It is absolutely true. Your test program is not well formed. The result of overflowing or underflowing a signed integer is undefined. What's tripping you up is that C can be very lax with stuff it doesn't allow. Some stuff is required to generate a compiler error, like if you try to start a variable name with a number. Some stuff is just "undefined behavior" which means the compiler can basically do whatever it wants. Undefined behavior is often referred to as "nasal demons" because it would be perfectly legal for a conforming C compiler which encounters undefined behavior to make demons fly out of your nose. This is impractical, but real-world compilers can and do crash or silently emit unexpected values in this case. The most confusing part of this is that a subset of undefined behavior is doing what you want it to do. That's what you're encountering here. The moment you do i+1 you've hit undefined behavior. In this particular case, the compiler is emitting code that causes the value to wrap, which is what you expected. This is still undefined behavior, which means your program is ill formed, and the compiler can change its mind and betray you at any moment!

cnvogel 11y ago

Here's an example indicating how we can use overflow from INT_MAX to INT_MIN to terminate a loop... ...if signed overflow would be properly defined. /* Write \"hi\" n times, counter will wrap to negative * to indicate we've written enough greetings. * * i=3 -> we want to write hi three times * * 1st INT_MAX-i+1 = INT_MAX-2 -> write hi * 2nd INT_MAX-1 -> write hi * 3rd INT_MAX -> write hi * 4th INT_MIN (signed overflow, terminates loop) */ int write_n_times_hi(int i) { int j; for (j=INT_MAX-i+1; j>0; j++) printf("hi\n"); return i; } This will be compiled into an endless loop by gcc 5.3.0/x86_64 for -O3, but will terminate properly with -O0. If you change the (undefined for j=INT_MAX) j++ into the (defined) *((unsigned*)&j)++, the compiler may no longer assume that j stays >0 all of the time, and the loop has to terminate.