5 ms·

As usual; if a compiler knows about undefined behavior I would much rather it throw an error rather than optimize something the programmer didn't intend based o

As usual; if a compiler knows about undefined behavior I would much rather it throw an error rather than optimize something the programmer didn't intend based on the compiler out-smarting a human's ability to be specific.

klodolph 6y ago
I've heard this proposal thrown around a lot on HN, but how would that even work? Can you describe how the compiler would do this, what patterns it would look for, and what error messages it would produce? For example, consider this: int factorial(int n) { int r = 1; for (int i = 1; i <= n; i++) { r *= i; } return r; } Since there are two instances of possible UB in the above function, what error messages would you like the compiler to produce? First of all, the compiler can assume that the loop terminates. This is a reasonable assumption from a human perspective—the loop is almost certainly intended to run N times. However, if n = INT_MAX, then there’s UB… and there’s no real way to know that n ≠ INT_MAX. You could argue that you want -fsanitize=undefined, where the compiler inserts checks at runtime. I don’t think this proposal is well formulated enough to be viable. Or consider something like this: void puts_safe(const char *s) { puts(s == NULL ? "(null)" : s) } void puts_with_len(const char *s) { printf("len = %zu\n", strlen(s)); puts_safe(s); } Do you want something like, Warning: puts_safe replaced with puts, because s != NULL, because strlen(NULL) is undefined I suspect there would be a mountain of false positives, and I would rather just use a static analyzer.
- mjevans 6y ago
  What I want is for the compiler to have a mode (which ideally would be enabled by default, at least with modern compile targets) that never optimizes based on undefined behavior. It would do this by handing any UB as an error and making the programmer write a correct program that lacks UB through informing the programmer where undefined behavior has been proven by the compiler. This would improve both the code and the programmer's skills, rather than trying to make each out-think the other.
  - ChrisSD 6y ago
    Detecting UB is far harder than the compiler simply assuming there is no UB. That said, there are already tools to do it for some cases (but far from all). They're not often used in C/C++, perhaps because they're slow.
  - GolDDranks 6y ago
    So, do you mean that in the above loop example, it would require you to prove somehow that the loop always finishes, or if the programmer fails to do that, fail with "possibly infinite loop" error? In what language/system you would require that proof?
  - klodolph 6y ago
    What you are describing is formal methods. You can take a subset of C, use a formally-verified toolchain, and write your own formally-verified C code using proof systems. Or perhaps what you want is a different language. It’s just that what you’re describing—having the compiler detect UB and warn you about it, but still letting you write C code—without the burden of also writing correctness proofs using some formalism—it’s just not a viable option. From a usability perspective, if you turn on aggressive static analysis / warning settings like this, what you usually end up with is programmers that just start ignoring warnings or turning them off, except for greenfield projects. C’s semantics don’t make this kind of thing easy. If you have a greenfield project and you are fighting the language this hard, that’s precisely the time when using a different language is the most viable option.
  - saagarjha 6y ago
    This is untenable in the general case. For example, consider this function: int dereference(int *p) { return *p; } What should the compiler do in this case? If I pass (int *)0x1283412 into this function, that's undefined behavior…should it just always warn?
    - mjevans 6y ago
      The compiler isn't __changing any programmer dictated behavior__. There are no UB sourced 'optimizations' being implicitly disabled and none have been expressly enabled. As long as valid code compiles it's on the humans that wrote the code (or that triggered it's writing in some higher level synthesis tool). Expanding on this; I don't want compilers _making_ optimizations based on UB. I want them educating the programmers so that the UB can be eliminated at a human level and correct outcomes are the result, optimized if it makes sense.
- tsimionescu 6y ago
  For your first example, I think most people want integer overflow to be unspecified behavior instead of undefined behavior - this is how most other languages treat it, it is how all C compilers behaved for a long time, and it is unreasonably difficult to actually write C code that makes sure not to cause integer overflow. Your example is in fact perfect for why that should be the case: consider the following code: int n = 0; scanf("%d", &n) factorial(n); //using your definition of factorial(int) A standard-compliant C compiler is apparently free to optimize this program to format your hard-drive. For your second example, I would say that, rather than omitting the NULL check, a helpful compiler could do one of two things: 1. Don't reason from strlen(s) to s != NULL, so the NULL check must be left in (unless it has even more context and can see a non-NULL assignment to s) 2. Wherever trying to optimize away a comparison to NULL based on UB reasoning, put in a new comparison to NULL at the place you applied that reasoning. For this example, optimize the program as if it looked like this: //first, the inline version void puts_with_len(const char *s) { s_len = strlen(s); printf("len = %zu\n", s_len); const char* puts_arg = s == NULL ? "(null)" : s puts(puts_arg) } //after optimization void puts_with_len(const char *s) { s_len = strlen(s); const char* puts_arg; if (s != NULL) { puts_arg = s; } else { puts_arg = "(null)"; //could also explicitly signal a segfault or assert here instead } printf("len = %zu\n", s_len); puts(puts_arg); } In this case we didn't gain anything, but if puts_with_len were itself inlined the check would be moved further back, potentially replacing many NULL checks with a single one. I would note that there is a third option here that goes in a different direction: now that compilers are extremely aggressive with NULL check removal optimizations, a lot of unsafe C functions could be made safe by manually adding the missing NULL checks to the stdlib and other major libraries. This wouldn't affect the semantics, and it wouldn't hurt performance assuming the optimizer really is doing its business. For example, strlen() could itself raise an assertion/exit on strlen(NULL). If called from a context where it is known that s != NULL, the null check can be optimized away by the aggressive optimizer; if not, better safe than sorry.
  - UncleMeat 6y ago
    If signed integer overflow is implementation defined rather than undefined then it isn’t an error and we cannot make compiler features that warn or reject when we can prove it will occur. In your case we’ve managed to get the worst of both worlds (a buggy program and no capacity for the compiler to stop you).
simias 6y ago
It would sometimes work but I think this (very common comment) misses the general point, there's absolutely fine and non buggy on warning-worthy code that can be optimized away if the compiler relies on UB. A very simple example: void do_stuff(int *some_ptr) { do_substuff(some_ptr); *some_ptr += 2; } static void do_substuff(int *some_ptr) { if (some_ptr != NULL) { *some_ptr = 10; } } do_stuff calls a subroutine that does a NULL pointer check, then unconditionally dereferences the same pointer. From this the compiler, if it decides to inline that code, can decide to optimize the NULL check away since if the pointer is NULL it's guaranteed to trigger UB. The logic being "clearly the programmer assumes that the pointer can't be NULL here, so thanks to UB rules I can too". There's nothing wrong with this code, there's no reason to emit a warning. Distinguishing between "of course that's a reasonable optimization, that's probably what the developer intended" and "wow this compiler is so dumb, obviously I never meant for that to happen" is a very tough nut to crack. At this point you can push the blame to the C language not being expressive enough, in this case not giving us a way to express nullable vs. non-nullable pointers within the language, which forces the compiler to lean onto these UB heuristics to optimize.
- dooglius 6y ago
  Even in your heavily contrived example, I can think of cases where the optimization isn't what the programmer wants. For instance, I might have a special handler via userfaultfd(2) that detects if I'm doing an increment of the null pointer and handles it in some special way, but can't handle just setting it to 10. For a more real example, I might have acquired a lock around do_substuff, and I might be okay with the thread segfaulting only if the lock wasn't held.
  - anderskaseorg 6y ago
    If the programmer really needs reads and writes through particular pointers to happen in a particular sequence, because the target memory follows different rules than the language ordinarily allows the compiler to assume, then it’s the programmer’s responsibility to use the annotation provided by the language for exactly that purpose: volatile. If the compiler had to assume that every pointer needs to be treated as volatile, just about all generated code would be be slowed down dramatically. As for locks, the language already has rules about which memory access are allowed to be reordered across lock acquire and release calls. Otherwise locks wouldn’t work correctly at all.
Diggsey 6y ago
The compiler very rarely knows that UB exists in the program. To give a concrete example: the compiler sees this: ``` while (<expr>) { if (p == 0) { do_thing(); } *p = 42; } ``` In this case, the compiler wants to move `do_thing()` outside the loop because it's expensive. It also knows that it would be UB for this branch to execute if `*p = 42` executes, because that would result in UB. Therefore the compiler can assume that if the loop runs at least once, then `p != 0`. At no point does the compiler have any information about whether the program is in fact UB.

klodolph 6y ago

I've heard this proposal thrown around a lot on HN, but how would that even work? Can you describe how the compiler would do this, what patterns it would look for, and what error messages it would produce? For example, consider this: int factorial(int n) { int r = 1; for (int i = 1; i <= n; i++) { r *= i; } return r; } Since there are two instances of possible UB in the above function, what error messages would you like the compiler to produce? First of all, the compiler can assume that the loop terminates. This is a reasonable assumption from a human perspective—the loop is almost certainly intended to run N times. However, if n = INT_MAX, then there’s UB… and there’s no real way to know that n ≠ INT_MAX. You could argue that you want -fsanitize=undefined, where the compiler inserts checks at runtime. I don’t think this proposal is well formulated enough to be viable. Or consider something like this: void puts_safe(const char *s) { puts(s == NULL ? "(null)" : s) } void puts_with_len(const char *s) { printf("len = %zu\n", strlen(s)); puts_safe(s); } Do you want something like, Warning: puts_safe replaced with puts, because s != NULL, because strlen(NULL) is undefined I suspect there would be a mountain of false positives, and I would rather just use a static analyzer.

mjevans 6y ago
What I want is for the compiler to have a mode (which ideally would be enabled by default, at least with modern compile targets) that never optimizes based on undefined behavior. It would do this by handing any UB as an error and making the programmer write a correct program that lacks UB through informing the programmer where undefined behavior has been proven by the compiler. This would improve both the code and the programmer's skills, rather than trying to make each out-think the other.
- ChrisSD 6y ago
  Detecting UB is far harder than the compiler simply assuming there is no UB. That said, there are already tools to do it for some cases (but far from all). They're not often used in C/C++, perhaps because they're slow.
- GolDDranks 6y ago
  So, do you mean that in the above loop example, it would require you to prove somehow that the loop always finishes, or if the programmer fails to do that, fail with "possibly infinite loop" error? In what language/system you would require that proof?
- klodolph 6y ago
  What you are describing is formal methods. You can take a subset of C, use a formally-verified toolchain, and write your own formally-verified C code using proof systems. Or perhaps what you want is a different language. It’s just that what you’re describing—having the compiler detect UB and warn you about it, but still letting you write C code—without the burden of also writing correctness proofs using some formalism—it’s just not a viable option. From a usability perspective, if you turn on aggressive static analysis / warning settings like this, what you usually end up with is programmers that just start ignoring warnings or turning them off, except for greenfield projects. C’s semantics don’t make this kind of thing easy. If you have a greenfield project and you are fighting the language this hard, that’s precisely the time when using a different language is the most viable option.
- saagarjha 6y ago
  This is untenable in the general case. For example, consider this function: int dereference(int *p) { return *p; } What should the compiler do in this case? If I pass (int *)0x1283412 into this function, that's undefined behavior…should it just always warn?
  - mjevans 6y ago
    The compiler isn't __changing any programmer dictated behavior__. There are no UB sourced 'optimizations' being implicitly disabled and none have been expressly enabled. As long as valid code compiles it's on the humans that wrote the code (or that triggered it's writing in some higher level synthesis tool). Expanding on this; I don't want compilers _making_ optimizations based on UB. I want them educating the programmers so that the UB can be eliminated at a human level and correct outcomes are the result, optimized if it makes sense.
tsimionescu 6y ago
For your first example, I think most people want integer overflow to be unspecified behavior instead of undefined behavior - this is how most other languages treat it, it is how all C compilers behaved for a long time, and it is unreasonably difficult to actually write C code that makes sure not to cause integer overflow. Your example is in fact perfect for why that should be the case: consider the following code: int n = 0; scanf("%d", &n) factorial(n); //using your definition of factorial(int) A standard-compliant C compiler is apparently free to optimize this program to format your hard-drive. For your second example, I would say that, rather than omitting the NULL check, a helpful compiler could do one of two things: 1. Don't reason from strlen(s) to s != NULL, so the NULL check must be left in (unless it has even more context and can see a non-NULL assignment to s) 2. Wherever trying to optimize away a comparison to NULL based on UB reasoning, put in a new comparison to NULL at the place you applied that reasoning. For this example, optimize the program as if it looked like this: //first, the inline version void puts_with_len(const char *s) { s_len = strlen(s); printf("len = %zu\n", s_len); const char* puts_arg = s == NULL ? "(null)" : s puts(puts_arg) } //after optimization void puts_with_len(const char *s) { s_len = strlen(s); const char* puts_arg; if (s != NULL) { puts_arg = s; } else { puts_arg = "(null)"; //could also explicitly signal a segfault or assert here instead } printf("len = %zu\n", s_len); puts(puts_arg); } In this case we didn't gain anything, but if puts_with_len were itself inlined the check would be moved further back, potentially replacing many NULL checks with a single one. I would note that there is a third option here that goes in a different direction: now that compilers are extremely aggressive with NULL check removal optimizations, a lot of unsafe C functions could be made safe by manually adding the missing NULL checks to the stdlib and other major libraries. This wouldn't affect the semantics, and it wouldn't hurt performance assuming the optimizer really is doing its business. For example, strlen() could itself raise an assertion/exit on strlen(NULL). If called from a context where it is known that s != NULL, the null check can be optimized away by the aggressive optimizer; if not, better safe than sorry.
- UncleMeat 6y ago
  If signed integer overflow is implementation defined rather than undefined then it isn’t an error and we cannot make compiler features that warn or reject when we can prove it will occur. In your case we’ve managed to get the worst of both worlds (a buggy program and no capacity for the compiler to stop you).

simias 6y ago

It would sometimes work but I think this (very common comment) misses the general point, there's absolutely fine and non buggy on warning-worthy code that can be optimized away if the compiler relies on UB. A very simple example: void do_stuff(int *some_ptr) { do_substuff(some_ptr); *some_ptr += 2; } static void do_substuff(int *some_ptr) { if (some_ptr != NULL) { *some_ptr = 10; } } do_stuff calls a subroutine that does a NULL pointer check, then unconditionally dereferences the same pointer. From this the compiler, if it decides to inline that code, can decide to optimize the NULL check away since if the pointer is NULL it's guaranteed to trigger UB. The logic being "clearly the programmer assumes that the pointer can't be NULL here, so thanks to UB rules I can too". There's nothing wrong with this code, there's no reason to emit a warning. Distinguishing between "of course that's a reasonable optimization, that's probably what the developer intended" and "wow this compiler is so dumb, obviously I never meant for that to happen" is a very tough nut to crack. At this point you can push the blame to the C language not being expressive enough, in this case not giving us a way to express nullable vs. non-nullable pointers within the language, which forces the compiler to lean onto these UB heuristics to optimize.

dooglius 6y ago
Even in your heavily contrived example, I can think of cases where the optimization isn't what the programmer wants. For instance, I might have a special handler via userfaultfd(2) that detects if I'm doing an increment of the null pointer and handles it in some special way, but can't handle just setting it to 10. For a more real example, I might have acquired a lock around do_substuff, and I might be okay with the thread segfaulting only if the lock wasn't held.
- anderskaseorg 6y ago
  If the programmer really needs reads and writes through particular pointers to happen in a particular sequence, because the target memory follows different rules than the language ordinarily allows the compiler to assume, then it’s the programmer’s responsibility to use the annotation provided by the language for exactly that purpose: volatile. If the compiler had to assume that every pointer needs to be treated as volatile, just about all generated code would be be slowed down dramatically. As for locks, the language already has rules about which memory access are allowed to be reordered across lock acquire and release calls. Otherwise locks wouldn’t work correctly at all.

Diggsey 6y ago

The compiler very rarely knows that UB exists in the program. To give a concrete example: the compiler sees this: ``` while (<expr>) { if (p == 0) { do_thing(); } *p = 42; } ``` In this case, the compiler wants to move `do_thing()` outside the loop because it's expensive. It also knows that it would be UB for this branch to execute if `*p = 42` executes, because that would result in UB. Therefore the compiler can assume that if the loop runs at least once, then `p != 0`. At no point does the compiler have any information about whether the program is in fact UB.