Pointers Are Complicated II, or: We need better language specs

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?

[ Parent | on HN ]

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).

[ Parent | on HN ]

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.

[ Parent | on HN ]