News for hackers. Stuff that matters.
Re:Pointers Are Complicated II, or: We need better language ... by tsimionescu on Tuesday December 15, 2020 @03:11AM (#25428132)
Thinking about this quite a bit, I see the second optimization as pretty obviously incorrect - not because of provenance, but because it acts as if pointer-to-integer-to-pointer casting is value-preserving, which is not at all guaranteed by the C abstract machine. In particular, `p != q && ((uintptr_t)p == (uintptr_t)q)` can be true according to the C standard. Instead of trying to track provenance, simply considering that the transformation between pointers and integers is not value preserving seems to be a simpler rule.

If we want to reason about optimizations using the C abstract machine, we can't consider these transformations to be value-preserving, even if they happen to be in the real machines that LLVM targets (and if they start reasoning for the real machine instead of the C abstract machine, a lot of other optimizations are invalid).

Re:Pointers Are Complicated II, or: We need better language ... by magicalhippo on Tuesday December 15, 2020 @05:49AM (#25429026)
For me it is the third optimization which is incorrect. I mean, if you replace the pointers with array indexes, then you'd end up with something like this after the second optimization:

    char data[N];
    uintptr_t p = rand_int(N);
    uintptr_t q = rand_int(N);
    data[q] = 0;
    data[p] = 0;
    uintptr_t ip = (p+1);
    uintptr_t iq = q;
    if (iq == ip) {
      data[p+1] = 10;
      print(data[q]);
    }
Surely no sane compiler would replace the "data[q]" in the print statement with 0?

Or did the caffeine not kick in yet?

Re:Pointers Are Complicated II, or: We need better language ... by tsimionescu on Tuesday December 15, 2020 @05:12PM (#25435917)
You're right, and the optimization wouldn't have kicked in in the original example if p and q had been pointers to elements of the same array.

However, if they are pointers to different local variables, the compiler knows something else: it knows that p and q do not alias each other, so writes to p can't change the value pointed by q and vice versa.

Now, in the original code, there seems to be a write to a pointer casted from an integer, which would be allowed to alias any other pointer - so after the (int)ip = 10 write, both p's and q's value would normally have to be assumed to be potentially changed.

However, step 2 in the optimizations has removed this information - by replacing the integer pointer with a write to the p pointer, it has again enabled the compiler to reason that no (valid) writes to q have been performed, so q's vue can't have changed.

Note that the intermediate program after optimization 2 would have UB if written directly in C, since dereferencing one-past-the-end pointers is UB (creating them, comparing them, or casting them to uintptr_t is valid behavior, however).

Instead, if p and q pointed into the same object, such as an array, p+1 could very well be an alias for q, so there would be no way to prove that q's value hasn't changed.

What the article is getting at is that the compiler is relying on the origin of the pointers to allow it to make optimization 3 (it knows p+1 is a pointer to a local variable, q is a pointer to a different local variable, so they can't be aliased) ; but it previously optimized away a code change that is supposed to destroy this provenance information - a pointer-from-integer is allowed to alias any pointer in the whole program (if we ignore restrict/noalias).

Re:Pointers Are Complicated II, or: We need better language ... by magicalhippo on Wednesday December 16, 2020 @04:13AM (#25440489)
Thanks, that's making it more clear.
Re:Pointers Are Complicated II, or: We need better language ... by abra529 on Tuesday December 15, 2020 @05:38AM (#25428952)
Is it not guaranteed? Looking at this question [1] on StackOverflow and the quotes from the standard included in the question, it seems that the value should be preserved.

(It raises the issue of whether (char※)iq should technically be (char※)(void※)iq if this were C code, but the (void※) cast can be inserted without changing anything about the problems discussed in the article.)

[1] https://stackoverflow.com/q/34291377

Re:Pointers Are Complicated II, or: We need better language ... by tsimionescu on Tuesday December 15, 2020 @04:39PM (#25435570)
Yes, you are absolutely right, so my argument flies out the window. Thanks for finding the relevant C spec!