8 ms·

Your proposed statement “conforming implementations cannot transform code on the basis that some behavior left undefined by the standard is impossible” would ha

Your proposed statement “conforming implementations cannot transform code on the basis that some behavior left undefined by the standard is impossible” would have no meaning in the standard, even if it were written somewhere other than a non-normative note. The standard doesn’t describe transformations; it describes behaviors. You can’t just say that undefined behaviors can’t be “transformed”, because there was nothing to transform them _from_. If you want some behaviors to be possible and some behaviors to be impossible, then you need to define those behaviors. For C, that’s not something we can realistically do in every case. There’s no way to reasonably constrain the set of allowed behaviors after a program does some crazy pointer operation like * (int *) rand() = rand(), because any implementation of those constraints would more or less require an expensive run-time check at every pointer access. What you could meaningfully ask is for particular situations (like negative shifts) to be considered unspecified or implementation-defined rather than undefined. That way you don’t give up the ability to constrain the behavior of programs after those situations arise. There are already many unspecified behaviors in the standard, such as reading the value of padding bytes in structs. Such proposals could be considered on their merits, but they’d have to be discussed individually. There’s no way to remove all undefined behavior from C and still have something that would be recognizable as C.

TooBrokeToBeg 8y ago
> The standard doesn’t describe transformations; it describes behaviors. That doesn't seem to be an argument against, or even related to, what the proposal entails. All of these proposals are reductive attempts to curb the instability that UB introduces, for little value (see the linux kernel). > because there was nothing to transform them _from_ Yes there was. Anything that can result in UB. > For C, that’s not something we can realistically do in every case. That's why the proposal is not exhaustive, as described.
- geofft 8y ago
  There aren't things that "can result in" UB, though. The C code itself, before any compilation, is already undefined by the C spec. For instance, the following code is not valid C code: int a[2], b; a[2] = 5; The compiler is free to do anything it wants, because the standard has not defined what it does. It could stop. Most likely it will just overwrite whatever memory is after a[1] with 5, because that's easiest. If you want the compiler to do something specific, you need to define it. In some cases the standard has language for otherwise-defined behavior that is carved out as undefined (e.g., strict aliasing), and it's easy to go "Never mind"; in some cases it does not (e.g., writing to a string literal). For these ones, the behavior needs to be defined. Simply saying "Don't optimize this" is just saying "I'm not going to define the behavior, but don't implement it this way," which isn't a particularly useful way to define a standard (e.g., for the null checks example, is the compiler permitted to leave the null check in, but insert a segfault right before it?).
  - vyodaiken 8y ago
    It's completely valid. It's just not conforming. No the compiler is not entitled to insert a segfault. Segaults come from architectures and operating systems, not from compilers. The compiler is free to leave in the dereference of the null pointer and then, who knows what happens. But the compiler can't break the code by deleting a perfectly conforming null check on the theory that a previous dereference means that the pointer is not null. The original Bourne shell used signal to catch memory faults so it could operate dynamic paging! If your OS/implementation permits, C is supposed to allow you do do things like that. The compiler is NOT supposed to insulate the programmer from bumps. (Disclaimer: I am not endorsing the horrible design of the Bourne shell which was also written in a macro style that made C into pseudo Algol).
    - palotasb 8y ago
      What is your definition of valid? It's not valid by any C standard or common compiler implementation. For the sake of any argument, we should at least agree on a common definition for valid. As for deleting null checks, time-travelling UB etc. the compiler always assumes the code is valid, bug-free for the compiler-specific definition of valid. This is at least the standard definition but it can be expanded by flags and extensions. Then they optimize that code without regard to what happens if the code actually had programming bugs.
      - vyodaiken 8y ago
        is k = i+j valid C? Can it be translated sensibly to add i,j; jump on overflow to random; store k; ? How about sometimes omitting the jump to random and sometimes not?
        geofft 8y ago
        Signed integer overflow is undefined, so the only obligation is that the code operates correctly when signed integer overflow doesn't happen. So, yes all those options are permissible, because as far as the C standard specifies, it's "add i,j; if false jump to random; store k". If you want to add a definition for signed integer overflow (as C++ is considering, see http://wg21.link/P0907r0 http://wg21.link/P0907r0 ) then it would be defined and the compiler would no longer get to consider "if signed overflow" and "if false" the same.
vyodaiken 8y ago
>The standard doesn’t describe transformations; it describes behaviors That is not remotely true - as you can see by looking up the example I reference. >For C, that’s not something we can realistically do in every case. There’s no way to reasonably constrain the set of allowed behaviors after a program does some crazy pointer operation like * (int *) rand() = rand(), because any implementation of those constraints would more or less require an expensive run-time check at every pointer access. That's such a weird response. There is nothing in the proposal that requires run-time checks. The proposal simply limits the ability of the compiler/translator to make counter-factual assumptions or otherwise violate the C semantics. >What you could meaningfully ask is for particular situations (like negative shifts) to be considered unspecified or implementation-defined rather than undefined. I don't want to do that: I want to clarify the meaning of "undefined behavior" to curtail its use as a license to do arbitrary code transformations. One implementation may trap on a negative shift, one may generate negative shift instructions that the architecture treats as no-ops or whatever they do, one might do sufficient static analysis to detect negative shifts and generate an error message - but the compiler is not free to assume that the shift operator has a negative value. I'm not trying to remove undefined behavior from C. I am trying to correct a mistaken analysis of what undefined behavior should mean. C is intended to allow for non-portable operations, for example. These are "undefined" in the standard because they depend on the implementation, not because the C language should be specified so as to allow compilers to introduce hidden booby traps or counter-factual assumptions into the implementation
- friendlydude12 8y ago
  Undefined behavior doesn’t exist to ease portability per se, it exists to handle meaningless yet syntactically valid constructs. Shifting by a negative number is meaningless and is indicative of programming error. Instead of specifying that an implementation should check and handle these programming errors, which implies runtime costs, we use undefined behavior and leave the responsibility to the programmer. The reason many compilers assume a positive shift after a shift operation executes is because otherwise the entire program would be undefined. You’re effectively asking for undefined programs to have defined behavior. The equivalent would be asking the compiler to correct your typos and it can’t do that. As they say: garbage in, garbage out. The compiler isn’t the one booby trapping you, you’re booby trapping yourself. I think GP is right that what you want is more definition but it has to be in specific cases because otherwise the runtime costs would be too high. In your negative shift example, the definition would be “shifting by a negative number results in garbage output,” but note that that would burden implementations where negative shifts trap.
Asooka 8y ago
You can fulfill (1) not too hard. First, the compiler is allowed to compile your program as-if all values of all variables are such that undefined behaviour doesn't happen, but isn't allowed to extract value bounds based on that for the purposes of optimising across more than one expression. So the compiler is allowed to assume pointers aren't NULL where they are dereferenced, because that is undefined behaviour and the compiler either has to assume the pointer isn't NULL, or require proof from the programmer, or refuse to compile any C program with pointer dereferencing because it is potentially invalid C. However, it is not allowed to assume that because a pointer was dereferenced, that it is not NULL. This restriction should be tight enough that int a, b; ... set a and b ... if (a > 0 && b > 0 && (a+b)&(int)(-1) > a) { ... } else { ... } is compiled to something like mov eax a add eax b cmp eax a jle .else Second, you can define "trivially compiled C" for every platform as a set of substitution rules that transform every C operation into machine instructions without any optimization. Such a trivial compilation would have every variable write correspond to a memory write, keep no variables in registers, always compile the same expression to the exact same machine code (except for memory addresses of variables involved), never inline functions etc. But it would still be allowed to e.g. put 32-bit integers in 64-bit registers on the basis that int operations are assumed not to overflow. The committee should define that for every supported platform as a reference C compiler, then require that C compilation produce machine code with observable side-effects for single-threaded execution equivalent to the reference trivially compiled C.
- palotasb 8y ago
  Isn't the reference compiler with trivial compilation equivalent to trying to make all UB implementation-defined where the implementation is the "trivial compilation"? For example this would preclude optimization based on aliasing rules which a lot of tight loops rely on. float max (float f[], int length, int* max_index) { float max_value = -FLT_MAX; *max_index = -1; for (int i = 0; i < length; i++) { if (max_value < f[i]) { *max_index= i; max_value = f[i]; } } return max_value; } Take the code above. It obviously has a well-defined trivial compilation implementation even for cases where max_index aliases an element of the f[] array. There is a good reason that implementations are allowed to assume that doesn't happen: it produces better code in the case where the program has no bugs. Otherwise even at -O3, the implementation would have to read f[i] twice from memory as the value might have changed when *max_index was written if it wants the same behavior as the "trivial compilation" implementation.

TooBrokeToBeg 8y ago

> The standard doesn’t describe transformations; it describes behaviors. That doesn't seem to be an argument against, or even related to, what the proposal entails. All of these proposals are reductive attempts to curb the instability that UB introduces, for little value (see the linux kernel). > because there was nothing to transform them _from_ Yes there was. Anything that can result in UB. > For C, that’s not something we can realistically do in every case. That's why the proposal is not exhaustive, as described.

geofft 8y ago
There aren't things that "can result in" UB, though. The C code itself, before any compilation, is already undefined by the C spec. For instance, the following code is not valid C code: int a[2], b; a[2] = 5; The compiler is free to do anything it wants, because the standard has not defined what it does. It could stop. Most likely it will just overwrite whatever memory is after a[1] with 5, because that's easiest. If you want the compiler to do something specific, you need to define it. In some cases the standard has language for otherwise-defined behavior that is carved out as undefined (e.g., strict aliasing), and it's easy to go "Never mind"; in some cases it does not (e.g., writing to a string literal). For these ones, the behavior needs to be defined. Simply saying "Don't optimize this" is just saying "I'm not going to define the behavior, but don't implement it this way," which isn't a particularly useful way to define a standard (e.g., for the null checks example, is the compiler permitted to leave the null check in, but insert a segfault right before it?).
- vyodaiken 8y ago
  It's completely valid. It's just not conforming. No the compiler is not entitled to insert a segfault. Segaults come from architectures and operating systems, not from compilers. The compiler is free to leave in the dereference of the null pointer and then, who knows what happens. But the compiler can't break the code by deleting a perfectly conforming null check on the theory that a previous dereference means that the pointer is not null. The original Bourne shell used signal to catch memory faults so it could operate dynamic paging! If your OS/implementation permits, C is supposed to allow you do do things like that. The compiler is NOT supposed to insulate the programmer from bumps. (Disclaimer: I am not endorsing the horrible design of the Bourne shell which was also written in a macro style that made C into pseudo Algol).
  - palotasb 8y ago
    What is your definition of valid? It's not valid by any C standard or common compiler implementation. For the sake of any argument, we should at least agree on a common definition for valid. As for deleting null checks, time-travelling UB etc. the compiler always assumes the code is valid, bug-free for the compiler-specific definition of valid. This is at least the standard definition but it can be expanded by flags and extensions. Then they optimize that code without regard to what happens if the code actually had programming bugs.
    - vyodaiken 8y ago
      is k = i+j valid C? Can it be translated sensibly to add i,j; jump on overflow to random; store k; ? How about sometimes omitting the jump to random and sometimes not?
      - geofft 8y ago
        Signed integer overflow is undefined, so the only obligation is that the code operates correctly when signed integer overflow doesn't happen. So, yes all those options are permissible, because as far as the C standard specifies, it's "add i,j; if false jump to random; store k". If you want to add a definition for signed integer overflow (as C++ is considering, see http://wg21.link/P0907r0 http://wg21.link/P0907r0 ) then it would be defined and the compiler would no longer get to consider "if signed overflow" and "if false" the same.

vyodaiken 8y ago

>The standard doesn’t describe transformations; it describes behaviors That is not remotely true - as you can see by looking up the example I reference. >For C, that’s not something we can realistically do in every case. There’s no way to reasonably constrain the set of allowed behaviors after a program does some crazy pointer operation like * (int *) rand() = rand(), because any implementation of those constraints would more or less require an expensive run-time check at every pointer access. That's such a weird response. There is nothing in the proposal that requires run-time checks. The proposal simply limits the ability of the compiler/translator to make counter-factual assumptions or otherwise violate the C semantics. >What you could meaningfully ask is for particular situations (like negative shifts) to be considered unspecified or implementation-defined rather than undefined. I don't want to do that: I want to clarify the meaning of "undefined behavior" to curtail its use as a license to do arbitrary code transformations. One implementation may trap on a negative shift, one may generate negative shift instructions that the architecture treats as no-ops or whatever they do, one might do sufficient static analysis to detect negative shifts and generate an error message - but the compiler is not free to assume that the shift operator has a negative value. I'm not trying to remove undefined behavior from C. I am trying to correct a mistaken analysis of what undefined behavior should mean. C is intended to allow for non-portable operations, for example. These are "undefined" in the standard because they depend on the implementation, not because the C language should be specified so as to allow compilers to introduce hidden booby traps or counter-factual assumptions into the implementation

friendlydude12 8y ago
Undefined behavior doesn’t exist to ease portability per se, it exists to handle meaningless yet syntactically valid constructs. Shifting by a negative number is meaningless and is indicative of programming error. Instead of specifying that an implementation should check and handle these programming errors, which implies runtime costs, we use undefined behavior and leave the responsibility to the programmer. The reason many compilers assume a positive shift after a shift operation executes is because otherwise the entire program would be undefined. You’re effectively asking for undefined programs to have defined behavior. The equivalent would be asking the compiler to correct your typos and it can’t do that. As they say: garbage in, garbage out. The compiler isn’t the one booby trapping you, you’re booby trapping yourself. I think GP is right that what you want is more definition but it has to be in specific cases because otherwise the runtime costs would be too high. In your negative shift example, the definition would be “shifting by a negative number results in garbage output,” but note that that would burden implementations where negative shifts trap.

Asooka 8y ago

You can fulfill (1) not too hard. First, the compiler is allowed to compile your program as-if all values of all variables are such that undefined behaviour doesn't happen, but isn't allowed to extract value bounds based on that for the purposes of optimising across more than one expression. So the compiler is allowed to assume pointers aren't NULL where they are dereferenced, because that is undefined behaviour and the compiler either has to assume the pointer isn't NULL, or require proof from the programmer, or refuse to compile any C program with pointer dereferencing because it is potentially invalid C. However, it is not allowed to assume that because a pointer was dereferenced, that it is not NULL. This restriction should be tight enough that int a, b; ... set a and b ... if (a > 0 && b > 0 && (a+b)&(int)(-1) > a) { ... } else { ... } is compiled to something like mov eax a add eax b cmp eax a jle .else Second, you can define "trivially compiled C" for every platform as a set of substitution rules that transform every C operation into machine instructions without any optimization. Such a trivial compilation would have every variable write correspond to a memory write, keep no variables in registers, always compile the same expression to the exact same machine code (except for memory addresses of variables involved), never inline functions etc. But it would still be allowed to e.g. put 32-bit integers in 64-bit registers on the basis that int operations are assumed not to overflow. The committee should define that for every supported platform as a reference C compiler, then require that C compilation produce machine code with observable side-effects for single-threaded execution equivalent to the reference trivially compiled C.

palotasb 8y ago
Isn't the reference compiler with trivial compilation equivalent to trying to make all UB implementation-defined where the implementation is the "trivial compilation"? For example this would preclude optimization based on aliasing rules which a lot of tight loops rely on. float max (float f[], int length, int* max_index) { float max_value = -FLT_MAX; *max_index = -1; for (int i = 0; i < length; i++) { if (max_value < f[i]) { *max_index= i; max_value = f[i]; } } return max_value; } Take the code above. It obviously has a well-defined trivial compilation implementation even for cases where max_index aliases an element of the f[] array. There is a good reason that implementations are allowed to assume that doesn't happen: it produces better code in the case where the program has no bugs. Otherwise even at -O3, the implementation would have to read f[i] twice from memory as the value might have changed when *max_index was written if it wants the same behavior as the "trivial compilation" implementation.