4 ms·

It seems to me like the final optimization is the only one that is not correct and obviously so. > The final optimization notices that q is never written to, s

It seems to me like the final optimization is the only one that is not correct and obviously so. > The final optimization notices that q is never written to, so we can replace q[0] by its initial value 0. However the line right above is *(p+1) = 10; The type of p is char[] which decays into a pointer and the type of (p+1) is char *. Because it is char * and not char * restrict, any assignment through such a pointer can be assumed to modify any and all data in a program. Therefore, the assumption that p[0] does not change and can be swapped out is not somehow surprisingly wrong, but simply entirely unfounded. It is up to the compiler to prove for itself that assignment through pointers does not change data it's interested in from before to after the assignment. (except, of course, in the case of restrict pointers, where the programmer makes this guarantee). This is not very difficult, at least conceptually. If the assignment was *p = 10; Well, we know that *p means p[0], which is within the bounds of the array, and we know that p and q do not overlap. Therefore, this assignment can not modify q. In the case of the first assignment, we know that *(p+1) means p[1], which is out of bounds for the array. So we do not know whether or not an assignment through *(p+1) modifies q, and we can not assume it does not.

Groxx 2y ago
It's not always correct, but that's kinda the tradeoff with undefined behavior. It's your responsibility to know the defined spec and stay within it, not the compiler's to prove you did it correctly in all cases. >Since q and p point to different local variables, a pointer derived from p cannot alias q[0], and hence we know that this write cannot affect the value stored at q[0]. Pointer math outside the array bounds isn't defined, so it can be treated as anything, including "cannot possibly do X, so we can optimize it out". A compiler that preferred to spend memory to improve correctness (e.g. Valgrind) might add padding between variables to prevent this kind of small-OOB action, which would make the output change again, which is why this is undefined and you can't rely on it. A compiler that was feeling moody could put that array at the end of your page of addressable memory, and cause a segfault when you try to write to it.
- serbuvlad 2y ago
  In the actual code *(p+1) is only ever accessed if it has been verified to be the same address as q[0], which is an object which we know exists and we have full access to. The problem is that pointers of the same type to the same address but originating from pointer arithmetic on the pointers obtained by dereferencing different objects have different semantics. In other words, the following is not semantically a NOP. char *p = /*some valid pointer*/; { char x; char *q = &x; while ((uintptr_t) q != (uintptr_t) p) q++; p = q; } I believe this goes against the principle of least astonishment (I find it quite astonishing, personally). I believe, even if the standard not does not guarantee the expected behavior, that implementations should still guarantee it. And they can do the optimizations they want in other ways, as I have outlined.
  - Groxx 2y ago
    While I generally agree and I much prefer my langs with minimal undefined behavior, this gets solidly into Hyrum's Law territory, and it means practically every significant optimization could break something therefore it cannot be done. C just doesn't have rich enough semantics to allow much else. You can find some languages that try to adhere to that, but C is extremely clearly not part of that group. It never has been, and it never will be.
    - imtringued 2y ago
      The problem with C is not necessarily the idea of undefined behavior. It's the culture around undefined behavior. There is no culture of avoiding UB in a programming language community that glorifies UB as necessary. That's the paradox. It's like you're supposed to cross an enemies' minefield, with the enemy laying ever more mines in your path and yet you're supposed to walk through the minefield and hope for the best. You'd have thought that C programmers have the best tools and techniques to avoid UB by now, so that UB would be a non-issue, a relic of the past that people remember suffering from in the 90s.
uecker 2y ago
This statement "any assignment through such a pointer can be assumed to modify any and all data in a program." is incorrect. You are not allowed to use a pointer to one object to modify another. At least this is what the C standard (somewhat imprecisely) implies and compilers generally exploit for optimization. Most people agree that the right solution is that the integer-round trips can not simply be assumed to be a no-op and has the effect that the recreated pointer can be used to point to the other object (as proposed by us in TS 6010). (So in this sense you are right). The LLVM maintainer stated recently that they are going to fix this.
- serbuvlad 2y ago
  > You are not allowed to use a pointer to one object to modify another. In this context, you means the author of a program written in Standard C. Implementations can choose to allow this (and in practice all do, because of the nature of pointers). And obviously, a code transformer for a particular implementation of C would only need to generate code valid for that implementation of C, not valid Standard C code.
  - uecker 2y ago
    True, an implementation could choose to allow this. But in is a bit questionable to say they do in practice, because most will miscompile your code in this case in various circumstances.
imtringued 2y ago
> The type of p is char[] which decays into a pointer and the type of (p+1) is char . Because it is char and not char * restrict, any assignment through such a pointer can be assumed to modify any and all data in a program. Out of bounds access is classic UB. The compiler is allowed to assume that you never access an array out of bounds. Since you never access p out of bounds, the effects of any write to p will not affect any "object" that is not p. >Therefore, the assumption that p[0] does not change and can be swapped out is not somehow surprisingly wrong, but simply entirely unfounded. I hope you notice your small mistake. It's print(q[0]), not print(p[0]), there is no "p" in the print. It's q[0] and q[0] is not p. The write to p did not affect q, because that would be UB. >It is up to the compiler to prove for itself that assignment through pointers does not change data it's interested in from before to after the assignment. (except, of course, in the case of restrict pointers, where the programmer makes this guarantee). This is not very difficult, at least conceptually. The code accesses q[0], not iq. You might say that if you did print(*iq), that the compiler should definitively know that iq and ip are the same and therefore a write to ip would also be a write to iq, but the code uses q[0], which is a memory address that is not proven to be identical to ip. Then again, what you're hoping for here is that the compiler fixes the UB for you, which is not the point of UB. You're supposed to rely on your godly C programmer instincts to never write code with UB in the first place.

Groxx 2y ago

It's not always correct, but that's kinda the tradeoff with undefined behavior. It's your responsibility to know the defined spec and stay within it, not the compiler's to prove you did it correctly in all cases. >Since q and p point to different local variables, a pointer derived from p cannot alias q[0], and hence we know that this write cannot affect the value stored at q[0]. Pointer math outside the array bounds isn't defined, so it can be treated as anything, including "cannot possibly do X, so we can optimize it out". A compiler that preferred to spend memory to improve correctness (e.g. Valgrind) might add padding between variables to prevent this kind of small-OOB action, which would make the output change again, which is why this is undefined and you can't rely on it. A compiler that was feeling moody could put that array at the end of your page of addressable memory, and cause a segfault when you try to write to it.

serbuvlad 2y ago
In the actual code *(p+1) is only ever accessed if it has been verified to be the same address as q[0], which is an object which we know exists and we have full access to. The problem is that pointers of the same type to the same address but originating from pointer arithmetic on the pointers obtained by dereferencing different objects have different semantics. In other words, the following is not semantically a NOP. char *p = /*some valid pointer*/; { char x; char *q = &x; while ((uintptr_t) q != (uintptr_t) p) q++; p = q; } I believe this goes against the principle of least astonishment (I find it quite astonishing, personally). I believe, even if the standard not does not guarantee the expected behavior, that implementations should still guarantee it. And they can do the optimizations they want in other ways, as I have outlined.
- Groxx 2y ago
  While I generally agree and I much prefer my langs with minimal undefined behavior, this gets solidly into Hyrum's Law territory, and it means practically every significant optimization could break something therefore it cannot be done. C just doesn't have rich enough semantics to allow much else. You can find some languages that try to adhere to that, but C is extremely clearly not part of that group. It never has been, and it never will be.
  - imtringued 2y ago
    The problem with C is not necessarily the idea of undefined behavior. It's the culture around undefined behavior. There is no culture of avoiding UB in a programming language community that glorifies UB as necessary. That's the paradox. It's like you're supposed to cross an enemies' minefield, with the enemy laying ever more mines in your path and yet you're supposed to walk through the minefield and hope for the best. You'd have thought that C programmers have the best tools and techniques to avoid UB by now, so that UB would be a non-issue, a relic of the past that people remember suffering from in the 90s.

uecker 2y ago

This statement "any assignment through such a pointer can be assumed to modify any and all data in a program." is incorrect. You are not allowed to use a pointer to one object to modify another. At least this is what the C standard (somewhat imprecisely) implies and compilers generally exploit for optimization. Most people agree that the right solution is that the integer-round trips can not simply be assumed to be a no-op and has the effect that the recreated pointer can be used to point to the other object (as proposed by us in TS 6010). (So in this sense you are right). The LLVM maintainer stated recently that they are going to fix this.

serbuvlad 2y ago
> You are not allowed to use a pointer to one object to modify another. In this context, you means the author of a program written in Standard C. Implementations can choose to allow this (and in practice all do, because of the nature of pointers). And obviously, a code transformer for a particular implementation of C would only need to generate code valid for that implementation of C, not valid Standard C code.
- uecker 2y ago
  True, an implementation could choose to allow this. But in is a bit questionable to say they do in practice, because most will miscompile your code in this case in various circumstances.

imtringued 2y ago

> The type of p is char[] which decays into a pointer and the type of (p+1) is char . Because it is char and not char * restrict, any assignment through such a pointer can be assumed to modify any and all data in a program. Out of bounds access is classic UB. The compiler is allowed to assume that you never access an array out of bounds. Since you never access p out of bounds, the effects of any write to p will not affect any "object" that is not p. >Therefore, the assumption that p[0] does not change and can be swapped out is not somehow surprisingly wrong, but simply entirely unfounded. I hope you notice your small mistake. It's print(q[0]), not print(p[0]), there is no "p" in the print. It's q[0] and q[0] is not p. The write to p did not affect q, because that would be UB. >It is up to the compiler to prove for itself that assignment through pointers does not change data it's interested in from before to after the assignment. (except, of course, in the case of restrict pointers, where the programmer makes this guarantee). This is not very difficult, at least conceptually. The code accesses q[0], not iq. You might say that if you did print(*iq), that the compiler should definitively know that iq and ip are the same and therefore a write to ip would also be a write to iq, but the code uses q[0], which is a memory address that is not proven to be identical to ip. Then again, what you're hoping for here is that the compiler fixes the UB for you, which is not the point of UB. You're supposed to rely on your godly C programmer instincts to never write code with UB in the first place.