5 ms·

How does a compiler know that signed overflow will happen in the above snippet? Couldn't all integer math result in overflow? If so, how does the compiler ever

by reza_n 9y ago

How does a compiler know that signed overflow will happen in the above snippet? Couldn't all integer math result in overflow? If so, how does the compiler ever know what to do? I do not think its plausible that the compiler is emitting code which checks for an overflow and then in a deterministic fashion skips all dependent logic there after. Im sorry, but I think this line of argument has been taken to such an extreme it has detached from reality.

amluto 9y ago
The compiler will see that you calculated capacity * 2. Since overflow is UB, the compiler may under that any code path that does this calculation does not cause signed overflow and can deduce that capacity * 2 does not overflow. Therefore, for example, the condition that capacity * 2 > capacity is equivalent to capacity > 0, and there goes your assertion. A modern compiler will likely also deduce that capacity > 0 and remove the assertion entirely. You can read up on "value range propagation" if you're interested. But all this is beside the point. In C, you may not invoke undefined behavior and then expect anything at all about the result. With malicious input, UB can and will result in RCE.
- reza_n 9y ago
  I can see the point you are trying to make, but in this context, it doesn't work. Lets start at line 20: vec.capacity = 0; Next, line 26: int new_capacity = vec->capacity * 2; So we get new_capacity = 0 * 2, so new_capacity is 0. The assert: assert(new_capacity > vec->capacity); Which translates to 0 > 0, it triggers a fail and we are done. If the compiler were to 'optimize' that out, then the compiler just introduced a very serious and fatal bug in our program, and we didn't even overflow or UB. So that assert works as intended, it forces new_capacity to grow until it hits INT_MAX or UB, at which point it will assert.
  - amluto 9y ago
    > I can see the point you are trying to make, but in this context, it doesn't work. No, you don't see the point. Writing code in C that invokes undefined behavior is wrong, full stop. You seem to think that it's only wrong if you, the programmer, can imagine how it would go wrong. > If the compiler were to 'optimize' that out, then the compiler just introduced a very serious and fatal bug in our program, and we didn't even overflow or UB. Sure, in this case, the compiler can't optimize the assertion out. But it certainly can change the condition in the assertion so that it won't fire on overflow.
    - reza_n 9y ago
      > But it certainly can change the condition in the assertion so that it won't fire on overflow. Once again, why would a compiler do that? To satisfy the Rust community's desire to spread FUD throughout the C community? (sorry to be so blunt, but im really scratching my head here) A more logical thought process here is that signed operations aren't uniform across architectures and are sometimes emulated, leading to UB for certain edge cases, like overflow. Its more practical to believe that a future C standard will fix this loophole rather than think compilers will exploit this and punish their own community. Very not impressed with this thread.
      - nkurz 9y ago
        why would a compiler do that? The theory is that constraint propagation enables optimizations that aren't possible otherwise. In particular, it lets the compiler avoid emitting code for conditions it judges are impossible to occur. This usually doesn't help much with C, but can be useful with C++, and many of the optimization decisions are driven by C++ performance. To satisfy the Rust community's desire to spread FUD throughout the C community? I'm a big fan of C, and consider it my primary language. I have barely used Rust and am not part of the Rust community. A more logical thought process here is that signed operations aren't uniform across architectures and are sometimes emulated, leading to UB for certain edge cases, like overflow. Personally, I would love if this was the vision for C that compiler writers held. But it is not, and has not been for at least a decade. Its more practical to believe that a future C standard will fix this loophole rather than think compilers will exploit this and punish their own community. Unfortunately there is no chance that this will happen. That ship has sailed. Compilers are taking ever greater advantage of undefined behavior for purposes of optimization. Overflowing a signed integer is undefined behavior, therefor real-world compilers can and do strip out checks that they determine would require undefined behavior to be occur. I realize this is hard to believe, but try this article as an intro: https://blogs.msdn.microsoft.com/oldnewthing/20140627-00/?p=633 https://blogs.msdn.microsoft.com/oldnewthing/20140627-00/?p=... Or even better, just look at the assembly that is generated here: #include <assert.h> int add_one(int num) { int increased = num + 1; assert(increased > num); return increased; } Both GCC and Clang completely remove the assert from the generated code: https://godbolt.org/g/5k43pV https://godbolt.org/g/5k43pV. To confirm, try adding "unsigned" to the "int" declarations and notice that it then keeps the check. I don't think either removes the check yet in the exact multiply by two case that you offer, but it is not safe to depend on this behavior. Very not impressed with this thread. I can see why you feel that way, but I think if you research this further you'll come to appreciate the stern warnings that people are giving you in this thread. C does not work the you want it to. Your choices are to adapt and avoid undefined behavior, or switch to a better language. I'm sticking with C because I think it's the best choice for what I do, but you need to be aware of the dangers if you are going to use it.
  - dpc_pw 9y ago
    Oh. In case you wanted to assert the capacity = 0 isn't happening, it's OK. I was talking about overflow protection. I'm sorry if I've missed something you said that was implying that. If you wanted to check overflow condition, this assert doesn't help. If the capacity was almost MAX_INT, and you multiply it be 2, then compiler has freedom to do whatever, and not catch it because it must never be happening in the first place.

by reza_n 9y ago

amluto 9y ago

The compiler will see that you calculated capacity * 2. Since overflow is UB, the compiler may under that any code path that does this calculation does not cause signed overflow and can deduce that capacity * 2 does not overflow. Therefore, for example, the condition that capacity * 2 > capacity is equivalent to capacity > 0, and there goes your assertion. A modern compiler will likely also deduce that capacity > 0 and remove the assertion entirely. You can read up on "value range propagation" if you're interested. But all this is beside the point. In C, you may not invoke undefined behavior and then expect anything at all about the result. With malicious input, UB can and will result in RCE.

reza_n 9y ago
I can see the point you are trying to make, but in this context, it doesn't work. Lets start at line 20: vec.capacity = 0; Next, line 26: int new_capacity = vec->capacity * 2; So we get new_capacity = 0 * 2, so new_capacity is 0. The assert: assert(new_capacity > vec->capacity); Which translates to 0 > 0, it triggers a fail and we are done. If the compiler were to 'optimize' that out, then the compiler just introduced a very serious and fatal bug in our program, and we didn't even overflow or UB. So that assert works as intended, it forces new_capacity to grow until it hits INT_MAX or UB, at which point it will assert.
- amluto 9y ago
  > I can see the point you are trying to make, but in this context, it doesn't work. No, you don't see the point. Writing code in C that invokes undefined behavior is wrong, full stop. You seem to think that it's only wrong if you, the programmer, can imagine how it would go wrong. > If the compiler were to 'optimize' that out, then the compiler just introduced a very serious and fatal bug in our program, and we didn't even overflow or UB. Sure, in this case, the compiler can't optimize the assertion out. But it certainly can change the condition in the assertion so that it won't fire on overflow.
  - reza_n 9y ago
    > But it certainly can change the condition in the assertion so that it won't fire on overflow. Once again, why would a compiler do that? To satisfy the Rust community's desire to spread FUD throughout the C community? (sorry to be so blunt, but im really scratching my head here) A more logical thought process here is that signed operations aren't uniform across architectures and are sometimes emulated, leading to UB for certain edge cases, like overflow. Its more practical to believe that a future C standard will fix this loophole rather than think compilers will exploit this and punish their own community. Very not impressed with this thread.
    - nkurz 9y ago
      why would a compiler do that? The theory is that constraint propagation enables optimizations that aren't possible otherwise. In particular, it lets the compiler avoid emitting code for conditions it judges are impossible to occur. This usually doesn't help much with C, but can be useful with C++, and many of the optimization decisions are driven by C++ performance. To satisfy the Rust community's desire to spread FUD throughout the C community? I'm a big fan of C, and consider it my primary language. I have barely used Rust and am not part of the Rust community. A more logical thought process here is that signed operations aren't uniform across architectures and are sometimes emulated, leading to UB for certain edge cases, like overflow. Personally, I would love if this was the vision for C that compiler writers held. But it is not, and has not been for at least a decade. Its more practical to believe that a future C standard will fix this loophole rather than think compilers will exploit this and punish their own community. Unfortunately there is no chance that this will happen. That ship has sailed. Compilers are taking ever greater advantage of undefined behavior for purposes of optimization. Overflowing a signed integer is undefined behavior, therefor real-world compilers can and do strip out checks that they determine would require undefined behavior to be occur. I realize this is hard to believe, but try this article as an intro: https://blogs.msdn.microsoft.com/oldnewthing/20140627-00/?p=633 https://blogs.msdn.microsoft.com/oldnewthing/20140627-00/?p=... Or even better, just look at the assembly that is generated here: #include <assert.h> int add_one(int num) { int increased = num + 1; assert(increased > num); return increased; } Both GCC and Clang completely remove the assert from the generated code: https://godbolt.org/g/5k43pV https://godbolt.org/g/5k43pV. To confirm, try adding "unsigned" to the "int" declarations and notice that it then keeps the check. I don't think either removes the check yet in the exact multiply by two case that you offer, but it is not safe to depend on this behavior. Very not impressed with this thread. I can see why you feel that way, but I think if you research this further you'll come to appreciate the stern warnings that people are giving you in this thread. C does not work the you want it to. Your choices are to adapt and avoid undefined behavior, or switch to a better language. I'm sticking with C because I think it's the best choice for what I do, but you need to be aware of the dangers if you are going to use it.
- dpc_pw 9y ago
  Oh. In case you wanted to assert the capacity = 0 isn't happening, it's OK. I was talking about overflow protection. I'm sorry if I've missed something you said that was implying that. If you wanted to check overflow condition, this assert doesn't help. If the capacity was almost MAX_INT, and you multiply it be 2, then compiler has freedom to do whatever, and not catch it because it must never be happening in the first place.