Can 2 `restrict`-ed pointers compare equal?

Question

int foo(void *restrict ptr1, void *restrict ptr2)
{
  if (ptr1 == ptr2) {
    return 1234;
  } else {
    return 4321;
  }
}

restrict implies the the memory pointed to by a pointer is not aliased by any other pointer. Given that, then ptr1 and ptr2 cannot point to the same region, so the comparison is tautological and foo() should return 4321 in all cases.

Yet clang and gcc do not see it this way (https://godbolt.org/z/fvPd4a1vd). Is this a missed optimization or is there another reason?

Sublett

But giving the compiler a hint or as you say implying doesn't enforce anything, does it? – Unman

I think I agree it is a missed optimization. But I think you have to *ptr1 = *ptr2 = access them for restrict to "take effect". – Tobit

This kind of optimization would lead to very hard to track and debug errors. It wouldn't be reasonable to have one – Rubel

Actually the restrict ensures the compiler that no other pointer will be used to access the same location of the restricted pointer; it doesn't ensure you that no other pointer will exist pointing to the same memory location. You need to access the location to have optimizations see godbolt.org/z/eb1j7rr9P and godbolt.org/z/f9G5nW6dT – Philosophical

@ryyker, restrict debuted in C99. I don't think I would call that "relatively new" 24 years and three editions of the language spec later. – Meld

"restrict implies the the memory pointed to by a pointer is not aliased by any other pointer" -- no, it doesn't. It sets up conditions in which program behavior is undefined, but where it would be defined without restrict. Those conditions require one pointer to alias a restrict-qualified pointer, so when all the other conditions are also present, the compiler is free to assume no aliasing of the restrict qualified pointer. But that's not the same as "they can't alias", and those conditions are not (all) present in the example code for any input. – Meld

As has been pointed out, the rules about restrict are predicated on accessing objects, not merely testing their addresses. And, for a hypothetical example where this is useful, consider code that accepts restrict-qualified pointers to a source buffer and a destination buffer. It could compare pointers, and, if they are different, use an algorithm that directly writes results to the destination buffer, whereas, if they are the same (or overlap), uses a different algorithm that, perhaps, reads and writes only through the destination pointer. – Petersburg

@EricPostpischil A slight off-topic. Re: "compare pointers, and, if they are different": to remind: GCC bug (?): godbolt.org/z/fY9exvcdf. – Polymath

Answer 1

According to the section 6.7.3 of the C99 Draft N1256:

An object that is accessed through a restrict-qualified pointer has a special association with that pointer. This association, defined in 6.7.3.1 below, requires that all accesses to that object use, directly or indirectly, the value of that particular pointer.117) The intended use of the restrict qualifier (like the register storage class) is to promote optimization, and deleting all instances of the qualifier from all preprocessing translation units composing a conforming program does not change its meaning (i.e., observable behavior).

Declaring a pointer as restrict ensures the compiler that no other pointer will modify the memory location pointed by the restricted pointer.

However, You can still have two restricted pointers pointing to the same memory region.

Again, the EXAMPLE 3 in 6.7.3.1 of the C99 Draft N1256 comes in handy:

void h(int n, int * restrict p, int * restrict q, int * restrict r)
{
    int i;
    for (i = 0; i < n; i++)
        p[i] = q[i] + r[i];
}

This is the comment from the standard:

[The function parameter declarations of h] illustrate how an unmodified object can be aliased through two restricted pointers. In particular, if a and b are disjoint arrays, a call of the form h(100, a, b, b) has defined behavior, because array b is not modified within function h.

So, the answer to your question is: No, this is not a missed optimization by GCC or Clang.

---

As pointed out by Peter in the comments there could be a missing optimization based on the following undefined behavior related to restricted pointers:

An object which has been modified is accessed through a restrict-qualified pointer to a const-qualified type, or through a restrict-qualified pointer and another pointer that are not both based on the same object (6.7.3.1).

Essentially, if two restricted pointers are not used to modify the data they are pointing to (which is the case of your function foo and the function h in my answer), no undefined behavior would occur even if they are pointing to the same memory region. Therefore, the compiler cannot say anything about their values at compilation time: they could be equal as well as different.

However, a different situation is the following:

int compare_pointers(int *restrict ptr1, int *restrict ptr2)
{
    *ptr1 = 0;
    *ptr2 = 1;
    if (ptr1 != ptr2) {
        return 1234;
    } else {
        return 4321;
    }
}

Since both pointers are used to modify data they must be associated to different memory region otherwise an undefined behavior would occur (this is a consequence of the restrict keyword) and so an optimization could remove the subsequent comparison and return 1234 instead. However, both GCC and Clang don't perform such optimization as shown by Peter's comment.

Philosophical

If you add *ptr1 = *ptr2 = 0;, then it is a missed optimization. (godbolt.org/z/ahE87TvWf). It would be UB for them to point to the same place, so they must not compare equal. But GCC and Clang do still compare. (As you commented under the question, if you compare values instead of pointers, when assigning to both restrict does let them optimize away the reload of the not-most-recently-stored object.) – Mala

It would be UB if they were used to modify the same memory location; it is slightly different. The restrict keyword allows the compiler to optimize access to the data pointed by the restricted pointers and to make assumptions on the data themselves as shown by our examples; however, and this is what I wanted to show with my answer, the restrict keyword seems useless when comparing pointers since the standard itself does not forbid having two restricted pointers to the same memory location. – Philosophical

A compiler is allowed to assume that there's no UB in the path of execution. For example, *ptr1 = 0; would let it assume ptr1 == NULL is false; compilers do make this optimization on null-pointer checks. And in this case, if the function does *ptr1 = *ptr2 = 0; or whatever else to modify both pointed-to objects, then it would be UB if the same object was modified through two different restrict pointers. So the compiler can assume that's no the case, which implies ptr1 != ptr2. But GCC and Clang miss that optimization for the related case where restrict actually implies anything – Mala

you definitely convinced me. I will update my answer with your precious insights, thank you. – Philosophical

You quoted the section that clearly refers to "access", which includes reads, yet you claimed that only modifications are relevant? – Eclampsia

@Philosophical FYI: In order to probit "assume ptr1 == NULL is false" there is -fno-delete-null-pointer-checks GCC option. Note that this option was added into Clang, because support for this option is needed for building Linux kernel. – Polymath

Answer 2

No, this is not a missed optimization opportunity in this case, because a pointed-to object is not modified and is not accessed through either pointer.

6.7.3.1 Formal definition of restrict:

If L is used to access the value of the object X that it designates, and X is also modified (by any means), then the following requirements apply: T shall not be const-qualified. Every other lvalue used to access the value of X shall also have its address based on P.

Indeed, restrict is useless here, since both pointers are to const.

Changing the code to:

int foo(int *restrict ptr1, int *restrict ptr2)
{
  int i = *ptr1;
  ++*ptr2;
  *ptr1 = i + 1;
  if (ptr1 == ptr2) {
    return 1234;
  } else {
    return 4321;
  }
}

we can see that gcc is aware of restrict, but fails to apply the optimization opportunity in this latter case, whereas clang is not aware of restrict at all.

Betsybetta

Clang is aware of restrict: note the difference in godbolt.org/z/j9T9bqqYj between compare_values_restrict and compare_values_norestrict (doing *ptr1 = 0; *ptr2 = 1; and then if (*ptr1 == *ptr2), with restrict clang knows they can't be equal.) Apparently clang isn't as good at taking advantage of restrict as GCC, though, like the missed optimization in your example where it actually loads + increments + stores instead of using two memory-destination inc instructions. – Mala