6 ms·

The problem here is that the thing that "can't happen" isn't actually something that can't happen, it's something that isn't allowed to happen according to a ma

The problem here is that the thing that "can't happen" isn't actually something that can't happen, it's something that isn't allowed to happen according to a many-hundred-page document that approximately nobody reads. It's not something that can be optimised because the compiler can prove it cannot happen, it is allowed to be optimised because the standard says "dear programmer, if you ever make this happen, god help you".

iforgotpassword 4y ago
It's still braindead and idiotic. Every relevant platform nowadays has well defined overflow for signed ints. A sane C compiler should go with that and base its optimizations on it. GCC has been a pile of garbage in this regard for many years now. Its devs get further removed from reality with every year. Treating signed int overflow as undefined should be hidden behind a flag.
- masklinn 4y ago
  Signed int overflow being UB is one of the most basic UBs of the language, and what allows generating tight code in loops. This is not new, -fwrapv was introduced in 2003, but it can quite severely impact code quality, if you don’t care, just set that. Then complain that C is slow, because C is a shit language.
  - iforgotpassword 4y ago
    > and what allows generating tight code in loops. How so? How does breaking an if statement the programmer added make the code faster? If they intended the check not to happen/be required, they wouldn't have written it. Let signed int overflow and leave any code that depends on its value alone. So yes maybe make fwrapv the default. > because C is a shit language. Well, it's as low level as it can get before reaching assembly, but why not try reducing the number of foot guns? Sometimes you still need C, and that's not going to go away for the foreseeable future.
    - masklinn 4y ago
      > How does breaking an if statement the programmer added make the code faster? If they intended the check not to happen/be required, they wouldn't have written it. See your problem is that you’re 1. not thinking like a compiler 2. and reasoning on an isolated example The compiler does not “break an if statement”, the compiler uses the UB to limit the range of the input and output, it can then propagate this range analysis to see that the check is dead code, and so removes the dead code. It’s common for users to write unnecessary or redundant checks, even more so because of inlining, and especially macros. If you’re carefully checking for null in every function prologue, and the compiler in-line everything and knows the pointer is non-null, all checks are dead and can be removed. Which is what the compiler does. This reduces the amount of branches (and thus the space needed by the branch predictor), and reduces the amount of code meaning the new inlined function could fall below threshold and itself become a candidate for inlining.
      - iforgotpassword 4y ago
        Ok sure, I'm using this particular example here, but I've yet to see a good counter example to convince me it's the lesser evil to let that happen. Also I agree you should not write code like that example and rather move the check up. But reality is we (at least I) still depend on code written in C, like openssh, and want it to be as safe as possible. Now I can blindly trust the devs know every UB in the C spec in and out, run all the static and dynamic analysis tools in existence, but it would just make me feel even more safe if the compiler would also work with them, not against. Somewhere here in the comments it was claimed that the linux kernel for example already uses -fwrapv and its performance seems absolutely fine to me. And I'd suspect that an OS kernel is already on the more performance critical end of the spectrum regarding stuff written in C that's still in use. I just find it worrysome that such evidently unsafe optimizations are the default, and not hidden behind some sufficiently scary-sounding flag.
    - aw1621107 4y ago
      > How so? A somewhat common example I've seen is sign extension in loops, where the width of the loop variable is not the same as that of the CPU register [0]. If the compiler can assume that signed integer overflow is UB, then it has a lot more freedom to unroll/vectorize the loop [1] (remove -fwrapv and watch Clang go to town). Of course, that specific optimization is rendered somewhat moot if the programmer chooses to use a 64-bit loop variable, but that is a slightly different rabbit hole. > If they intended the check not to happen/be required, they wouldn't have written it. I feel that's somewhat iffy reasoning - if we trust the programmer so much, why allow the implementation to optimize in the first place? And if not to that extreme, where should the line be drawn? [0]: https://gist.github.com/rygorous/e0f055bfb74e3d5f0af20690759de5a7 https://gist.github.com/rygorous/e0f055bfb74e3d5f0af20690759... [1]: https://godbolt.org/z/EMaq1j3Kc https://godbolt.org/z/EMaq1j3Kc
- emn13 4y ago
  The C/C++ language doesn't provide for a way for the compiler to see that you really meant this one check to take precedence over the implicit promise in another. The reason why C++ is always relevant here (though C macros and inlining cause similar issues) is that generic programming being close to optimal is a language feature - and one of the ways that's possible is by letting you right reusable code that might be "called" from a context in which some of the checks or conditions just aren't necessary. It's by design that the optimizer gets to... well, optimize that kind of code. There's a solid case to be made that the details of C's UB weren't well chosen and we should try to update them; but which decades old choices are perfect? Which are easy to change once there's this much legacy software in operation? Don't forget that some of those UB's were chosen to deal with hardware realities of the day; i.e. that the "same" operation on different hardware would do different things. For example, eliminating signed integer overflow might allow a C compiler to use a signed register that's wider than necessary, which may help on hardware that doesn't have every possible register width, or where there are complex register usage limitations. I'm no hardware geek; I'm sure somebody here knows or real examples where UB allows portability, because that's the point: UB allows people to write portable, performant code - just don't do certain things, and you're fine... which leads us to today's situation, in which UB can feel like a minefield.
  - eru 4y ago
    > Don't forget that some of those UB's were chosen to deal with hardware realities of the day; i.e. that the "same" operation on different hardware would do different things. That's an argument for implementation defined behaviour. Not for undefined behaviour, at least not UB in the modern sense.
    - emn13 4y ago
      Having implementation defined behavior would imply non-portability. C compilers have all kinds of ways of exposing platform-specific features, but sneaking those into what looks like standard behavior has its own issues. And even if you accept that, that doesn't deal with the issue of inlining, generics, and macros - you can get different implementation defined behavior even in a single hardware implementation like that. If that is what you want, compilers have various flags that let you in essence do that. But the next problem with that is (1) that it's possible existing code may be suddenly and unpredictably lose performance, and (2) now you need to provide some other well-defined behavior for those UB cases, and (3) the selling point of generics/macros/inlining may be reduced. How many relevant UB's are there? I don't know. How much perf would code common lose? I don't know. To be sure, I fully acknowledge that removing UB from the spec may be the right thing to do, but it's also easy enough to find possible problems with that strategy; I'm just pointing out the complexities, which is a lot easier than solving them or knowing which are irrelevant.
- eru 4y ago
  It's not about what your CPU does. These days undefined overflow for signed integers is mostly used by compilers to be able to assume that eg 'a + 1 > a' is always true, and thus eliminate redundant checks. (And you wouldn't typically write code like 'a + 1 > a', but you can get either from code generation via macros etc or as a intermediate result from previous optimization passes.)
josephcsible 4y ago
I think this view is slightly unfair. I think of UB as the compiler saying "when you promised this thing wouldn't happen, I took you at your word. If bad things happen because you lied, they're your fault, not mine."
- proto_lambda 4y ago
  Lying requires intent. This was a mistake, something that humans are well-known for making, and if the compiler is designed to assume otherwise, it borders on useless in the real world.
  - eru 4y ago
    That's C for you. If you want something saner, use Rust or Haskell or Python or even Java or Go or.. almost any other language that's not C or C++. These days the whole point of C is this Faustian pact with the devil of speed for sanity.
    - consp 4y ago
      Writing Rust and Haskell for sanity is not something I would agree with. Maybe for language characteristics but reading those make me jump out of the window.
      - eru 4y ago
        I have the same issue with Java and Go. (Which I brought up as well.) Yet, they still compare favourably with C in this regard. Almost anything does.
    - pca006132 4y ago
      I think Rust doesn't allow integer overflow either, unless you specifically use the wrapping_* operations. Probably the same kind of thing will also happen to Rust.
      - 4y ago
raverbashing 4y ago
Except this can't happen happens many and many times in practice so maybe it's time the language bureaucrats got off their high horse (but they won't)
pjmlp 4y ago
Even if someone would read all those pages, constraining ourselves to ISO C only, no way that after an year they would still remeber the about 200 UB cases that are documented there. Which is why everyone should adopt static analysis tooling and enable all the warnings that are related to UB, pointer and casts misuses. Many think they know better, it is like those that think builders don't need protection gear at a construction site, it is stuff only for the weak.
- gpderetta 4y ago
  I think implicitly compiler-added runtime check are a more robust and reliable solution than static analysis. For example for pointer dereferences the compiler should could 0-offset dummy load if the load is not guaranteed to be within a page of the pointer. Or adding abort-on-overflow for math. Or bound checking where possible. It will have a non-trivial cost, but hopefully aggressive optimizations can remove many of these checks (which ironically it is exactly the kind of optimizations people are complaining about) and compilers provide pragmas to disable them when critical. In a way sanitizers are getting there, but they are explicitly marked as for non-production use which is a problem.
  - pjmlp 4y ago
    I agree, but unfortunely that will never happen in most C and C++ circles, just see the heat JF Bastien has been facing for a feature that has been shipping in Windows and Android for the last two years, proven in the battlefield to hardly hinder performance in real use cases. https://isocpp.org/files/papers/P2723R0.html https://isocpp.org/files/papers/P2723R0.html Lots of people telling him it will never fly in production, while their Windows and Android phones are using the code that they say isn't good enough.
    - gpderetta 4y ago
      Zero initialization is also one of those features that seems such a low hanging fruit to implement... I'm still moderately optimistic. I suspect that many of these checks will end up being enabled by default on compilers shipped by distros, like stack guards and other forms of hardening.
Asooka 4y ago
Basically, the compiler implements integer addition using an operation that doesn't match the semantics of integer addition in the standard, then hallucinates that it did. That is: 1) The compiler sees an expression like "a += b;" where a and b are signed integers. 2) It emits "add rA rB" in x86 assembly (rA/B being the register a/b is currently in). 3) Technically the machine code emitted does not match the semantics of the source code, since it uses wraparound addition, whereas the C standard says that for the operation to be valid, the values of a and b must be such that no overflow would occur. This is fine however, because the implementation has the freedom to do anything on integer overflow, including just punting the problem to hardware as it did in this case. 4) The compiler proceeds with the rest of the code as if the line above would never overflow. My brother in the machine spirit, you chose to translate my program to a form where integer overflow is defined. The compiler should either a) trap on integer overflow; or b) accept integer overflow. It will be fine if it chooses either a) or b) situationally, i.e. if we have a loop where assuming no overflow is faster, then by all means - add a precondition check and crash the program if it's false, but don't just assume overflow doesn't happen when you explicitly emit code with well-defined overflow semantics. The bigger problem is there is pretty much no way to guard against this. The moment your program is longer than one page you're screwed. You may think all your functions are fine, but then you call something from some library, the compiler does some inlining and suddenly there's an integer overflow where you didn't expect, leading to your bounds check being deleted.

iforgotpassword 4y ago

It's still braindead and idiotic. Every relevant platform nowadays has well defined overflow for signed ints. A sane C compiler should go with that and base its optimizations on it. GCC has been a pile of garbage in this regard for many years now. Its devs get further removed from reality with every year. Treating signed int overflow as undefined should be hidden behind a flag.

masklinn 4y ago
Signed int overflow being UB is one of the most basic UBs of the language, and what allows generating tight code in loops. This is not new, -fwrapv was introduced in 2003, but it can quite severely impact code quality, if you don’t care, just set that. Then complain that C is slow, because C is a shit language.
- iforgotpassword 4y ago
  > and what allows generating tight code in loops. How so? How does breaking an if statement the programmer added make the code faster? If they intended the check not to happen/be required, they wouldn't have written it. Let signed int overflow and leave any code that depends on its value alone. So yes maybe make fwrapv the default. > because C is a shit language. Well, it's as low level as it can get before reaching assembly, but why not try reducing the number of foot guns? Sometimes you still need C, and that's not going to go away for the foreseeable future.
  - masklinn 4y ago
    > How does breaking an if statement the programmer added make the code faster? If they intended the check not to happen/be required, they wouldn't have written it. See your problem is that you’re 1. not thinking like a compiler 2. and reasoning on an isolated example The compiler does not “break an if statement”, the compiler uses the UB to limit the range of the input and output, it can then propagate this range analysis to see that the check is dead code, and so removes the dead code. It’s common for users to write unnecessary or redundant checks, even more so because of inlining, and especially macros. If you’re carefully checking for null in every function prologue, and the compiler in-line everything and knows the pointer is non-null, all checks are dead and can be removed. Which is what the compiler does. This reduces the amount of branches (and thus the space needed by the branch predictor), and reduces the amount of code meaning the new inlined function could fall below threshold and itself become a candidate for inlining.
    - iforgotpassword 4y ago
      Ok sure, I'm using this particular example here, but I've yet to see a good counter example to convince me it's the lesser evil to let that happen. Also I agree you should not write code like that example and rather move the check up. But reality is we (at least I) still depend on code written in C, like openssh, and want it to be as safe as possible. Now I can blindly trust the devs know every UB in the C spec in and out, run all the static and dynamic analysis tools in existence, but it would just make me feel even more safe if the compiler would also work with them, not against. Somewhere here in the comments it was claimed that the linux kernel for example already uses -fwrapv and its performance seems absolutely fine to me. And I'd suspect that an OS kernel is already on the more performance critical end of the spectrum regarding stuff written in C that's still in use. I just find it worrysome that such evidently unsafe optimizations are the default, and not hidden behind some sufficiently scary-sounding flag.
  - aw1621107 4y ago
    > How so? A somewhat common example I've seen is sign extension in loops, where the width of the loop variable is not the same as that of the CPU register [0]. If the compiler can assume that signed integer overflow is UB, then it has a lot more freedom to unroll/vectorize the loop [1] (remove -fwrapv and watch Clang go to town). Of course, that specific optimization is rendered somewhat moot if the programmer chooses to use a 64-bit loop variable, but that is a slightly different rabbit hole. > If they intended the check not to happen/be required, they wouldn't have written it. I feel that's somewhat iffy reasoning - if we trust the programmer so much, why allow the implementation to optimize in the first place? And if not to that extreme, where should the line be drawn? [0]: https://gist.github.com/rygorous/e0f055bfb74e3d5f0af20690759de5a7 https://gist.github.com/rygorous/e0f055bfb74e3d5f0af20690759... [1]: https://godbolt.org/z/EMaq1j3Kc https://godbolt.org/z/EMaq1j3Kc
emn13 4y ago
The C/C++ language doesn't provide for a way for the compiler to see that you really meant this one check to take precedence over the implicit promise in another. The reason why C++ is always relevant here (though C macros and inlining cause similar issues) is that generic programming being close to optimal is a language feature - and one of the ways that's possible is by letting you right reusable code that might be "called" from a context in which some of the checks or conditions just aren't necessary. It's by design that the optimizer gets to... well, optimize that kind of code. There's a solid case to be made that the details of C's UB weren't well chosen and we should try to update them; but which decades old choices are perfect? Which are easy to change once there's this much legacy software in operation? Don't forget that some of those UB's were chosen to deal with hardware realities of the day; i.e. that the "same" operation on different hardware would do different things. For example, eliminating signed integer overflow might allow a C compiler to use a signed register that's wider than necessary, which may help on hardware that doesn't have every possible register width, or where there are complex register usage limitations. I'm no hardware geek; I'm sure somebody here knows or real examples where UB allows portability, because that's the point: UB allows people to write portable, performant code - just don't do certain things, and you're fine... which leads us to today's situation, in which UB can feel like a minefield.
- eru 4y ago
  > Don't forget that some of those UB's were chosen to deal with hardware realities of the day; i.e. that the "same" operation on different hardware would do different things. That's an argument for implementation defined behaviour. Not for undefined behaviour, at least not UB in the modern sense.
  - emn13 4y ago
    Having implementation defined behavior would imply non-portability. C compilers have all kinds of ways of exposing platform-specific features, but sneaking those into what looks like standard behavior has its own issues. And even if you accept that, that doesn't deal with the issue of inlining, generics, and macros - you can get different implementation defined behavior even in a single hardware implementation like that. If that is what you want, compilers have various flags that let you in essence do that. But the next problem with that is (1) that it's possible existing code may be suddenly and unpredictably lose performance, and (2) now you need to provide some other well-defined behavior for those UB cases, and (3) the selling point of generics/macros/inlining may be reduced. How many relevant UB's are there? I don't know. How much perf would code common lose? I don't know. To be sure, I fully acknowledge that removing UB from the spec may be the right thing to do, but it's also easy enough to find possible problems with that strategy; I'm just pointing out the complexities, which is a lot easier than solving them or knowing which are irrelevant.
eru 4y ago
It's not about what your CPU does. These days undefined overflow for signed integers is mostly used by compilers to be able to assume that eg 'a + 1 > a' is always true, and thus eliminate redundant checks. (And you wouldn't typically write code like 'a + 1 > a', but you can get either from code generation via macros etc or as a intermediate result from previous optimization passes.)

josephcsible 4y ago

I think this view is slightly unfair. I think of UB as the compiler saying "when you promised this thing wouldn't happen, I took you at your word. If bad things happen because you lied, they're your fault, not mine."

proto_lambda 4y ago
Lying requires intent. This was a mistake, something that humans are well-known for making, and if the compiler is designed to assume otherwise, it borders on useless in the real world.
- eru 4y ago
  That's C for you. If you want something saner, use Rust or Haskell or Python or even Java or Go or.. almost any other language that's not C or C++. These days the whole point of C is this Faustian pact with the devil of speed for sanity.
  - consp 4y ago
    Writing Rust and Haskell for sanity is not something I would agree with. Maybe for language characteristics but reading those make me jump out of the window.
    - eru 4y ago
      I have the same issue with Java and Go. (Which I brought up as well.) Yet, they still compare favourably with C in this regard. Almost anything does.
  - pca006132 4y ago
    I think Rust doesn't allow integer overflow either, unless you specifically use the wrapping_* operations. Probably the same kind of thing will also happen to Rust.
    - 4y ago

raverbashing 4y ago

Except this can't happen happens many and many times in practice so maybe it's time the language bureaucrats got off their high horse (but they won't)

pjmlp 4y ago

Even if someone would read all those pages, constraining ourselves to ISO C only, no way that after an year they would still remeber the about 200 UB cases that are documented there. Which is why everyone should adopt static analysis tooling and enable all the warnings that are related to UB, pointer and casts misuses. Many think they know better, it is like those that think builders don't need protection gear at a construction site, it is stuff only for the weak.

gpderetta 4y ago
I think implicitly compiler-added runtime check are a more robust and reliable solution than static analysis. For example for pointer dereferences the compiler should could 0-offset dummy load if the load is not guaranteed to be within a page of the pointer. Or adding abort-on-overflow for math. Or bound checking where possible. It will have a non-trivial cost, but hopefully aggressive optimizations can remove many of these checks (which ironically it is exactly the kind of optimizations people are complaining about) and compilers provide pragmas to disable them when critical. In a way sanitizers are getting there, but they are explicitly marked as for non-production use which is a problem.
- pjmlp 4y ago
  I agree, but unfortunely that will never happen in most C and C++ circles, just see the heat JF Bastien has been facing for a feature that has been shipping in Windows and Android for the last two years, proven in the battlefield to hardly hinder performance in real use cases. https://isocpp.org/files/papers/P2723R0.html https://isocpp.org/files/papers/P2723R0.html Lots of people telling him it will never fly in production, while their Windows and Android phones are using the code that they say isn't good enough.
  - gpderetta 4y ago
    Zero initialization is also one of those features that seems such a low hanging fruit to implement... I'm still moderately optimistic. I suspect that many of these checks will end up being enabled by default on compilers shipped by distros, like stack guards and other forms of hardening.

Asooka 4y ago

Basically, the compiler implements integer addition using an operation that doesn't match the semantics of integer addition in the standard, then hallucinates that it did. That is: 1) The compiler sees an expression like "a += b;" where a and b are signed integers. 2) It emits "add rA rB" in x86 assembly (rA/B being the register a/b is currently in). 3) Technically the machine code emitted does not match the semantics of the source code, since it uses wraparound addition, whereas the C standard says that for the operation to be valid, the values of a and b must be such that no overflow would occur. This is fine however, because the implementation has the freedom to do anything on integer overflow, including just punting the problem to hardware as it did in this case. 4) The compiler proceeds with the rest of the code as if the line above would never overflow. My brother in the machine spirit, you chose to translate my program to a form where integer overflow is defined. The compiler should either a) trap on integer overflow; or b) accept integer overflow. It will be fine if it chooses either a) or b) situationally, i.e. if we have a loop where assuming no overflow is faster, then by all means - add a precondition check and crash the program if it's false, but don't just assume overflow doesn't happen when you explicitly emit code with well-defined overflow semantics. The bigger problem is there is pretty much no way to guard against this. The moment your program is longer than one page you're screwed. You may think all your functions are fine, but then you call something from some library, the compiler does some inlining and suddenly there's an integer overflow where you didn't expect, leading to your bounds check being deleted.