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?

But giving the compiler a hint or as you say `implying` doesn't enforce anything, does it? — Eldinur the Kolibri, Jul 20 '23 at 14:07
I think I agree it is a missed optimization. But I think you have to `*ptr1 = *ptr2 =` access them for restrict to "take effect". — KamilCuk, Jul 20 '23 at 14:12
This kind of optimization would lead to very hard to track and debug errors. It wouldn't be reasonable to have one — 0___________, Jul 20 '23 at 14:14
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 https://godbolt.org/z/eb1j7rr9P and https://godbolt.org/z/f9G5nW6dT — Kalendistrien, Jul 20 '23 at 14:19
@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. — John Bollinger, Jul 20 '23 at 16:42
"*`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. — John Bollinger, Jul 20 '23 at 17:07
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. — Eric Postpischil, Jul 20 '23 at 22:13
@EricPostpischil A slight off-topic. Re: "compare pointers, and, if they are different": to remind: GCC bug (?): https://godbolt.org/z/fY9exvcdf. — pmor, Aug 07 '23 at 12:38

Kalendistrien · Accepted Answer · 2023-07-21T17:07:10.320

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.

If you add `*ptr1 = *ptr2 = 0;`, then it *is* a missed optimization. (https://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.) — Peter Cordes, Jul 20 '23 at 15:32
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. — Kalendistrien, Jul 20 '23 at 18:15
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 — Peter Cordes, Jul 20 '23 at 18:50
you definitely convinced me. I will update my answer with your precious insights, thank you. — Kalendistrien, Jul 21 '23 at 16:57
You quoted the section that clearly refers to "access", which includes reads, yet you claimed that only modifications are relevant? — Ben Voigt, Jul 21 '23 at 18:54
@Kalendistrien FYI: In order to probit "assume `ptr1 == NULL` is false" there is [`-fno-delete-null-pointer-checks`](https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html) GCC option. Note that this option was [added into Clang](https://reviews.llvm.org/D47894), because support for this option is needed for building Linux kernel. — pmor, Aug 07 '23 at 12:26

score 9 · Answer 2 · answered Jul 20 '23 at 15:27

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.

Clang is aware of `restrict`: note the difference in https://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. — Peter Cordes, Jul 20 '23 at 16:10

Can 2 `restrict`-ed pointers compare equal?

2 Answers2