The weak provenance solution is to ban optimizing the pointer to integer casts since they have a (conceptual) side-effect. The strict provenance proposal points out that the side effect is only observable if the integer is cast back to a pointer, so we can keep optimizing pointer to integer casts and instead ban integer to pointer casts. For example, an operation like `(int *)xaddr` is banned under strict provenance. Instead, we provide a casting operation that includes the pointer to assume the provenance of; something like `(int * with x)xaddr`. With this new provenance-preserving cast, we can see that the final optimization of replacing `*x` with its previously assigned value of `0` is no longer possible because the code in between involves `x`.
Yeah this article is great and the framing is pretty perfect. It really shows that optimization passes can't remove information, else they run the risk of tricking later passes. I definitely agree with OP that "the incorrect optimization is the one that removed xaddr"; that optimization seems wild to me. You only know y is x + 1 because of the way it's constructed in the calling function (main). So the compiler... inlines an optimized version of the function that removes most use of x? Isn't that optimizer fundamentally broken? Especially in a language with `volatile` and `restrict`?
I guess what bugs me about optimizations is that it feels like something _I_ should be doing. Like if GCC told me this code optimizes down to printf 1 and why, I'd question what I was doing (and rightly so). Doing it automatically feels like too much spooky action at a distance.
I just checked cppreference and it says: "if some object that is accessible through P [marked restrict] (directly or indirectly) is modified, by any means, then all accesses to that object (both reads and writes) in that block must occur through P (directly or indirectly), otherwise the behavior is undefined"
The only accesses I can see are "*x = 0;", "*ptr = 1;" and "return *x;". "*ptr" is an indirect access through "x" by way of an integer round trip. If the orignal program is indeed UB that would mean that pointers built from an integer round trip are not considered (indirect) accesses through the original pointer.
The author assumes that it is an indirect access: "However, the only possibly suspicious part of the original program is a pointer-integer-pointer round-trip – and if casting integers to pointers is allowed, surely that must work. I will, for the rest of this post, assume that replacing x by (int*)(uintptr_t)x is always allowed."
In the first example the integer-cast derivative of the second pointer does alias the first but isn't used to access either object, therefore there is (or should be) no UB.
> I guess if I am wrong its because `restrict` ...
The `restrict` keyword was -IIUC- specifically intended to make it possible to write functions like `memcpy()` w/ optimizations that are made possible by knowing that the pointed-to objects do not overlap. The semantics of that are crystal clear in a hand-wavy way, but... very difficult to nail down exactly.
With a hand-wavy definition of `restrict` it's pretty clear that the first `uwu()` is perfectly fine and has no UB.
> the original program already had Undefined Behavior, or (at least) one of the optimizations is wrong.
As far as I know, since the uwu function was declared with x and y as restrict, the way uwu is called in main is undefined behavior. Because they are both pointing into the same array, and are both 'derived' from the same array.
I guess if I am wrong its because `restrict` does not care if both are derived from the same pointer. Instead it might only care if x was derived directly from y or y was derived directly from x. Is there a good reason to only care about this 'directly derived from' rather than 'shared derivation'? It would sorta suck if you can't use a function with to restrict arguments pointing into the same array, but this example seems to suggest that might be a reasonable requirement.