Does a restrict-qualified pointer parameter of a function allow optimization of the caller functions?

Question

A restrict-qualified pointer parameter of a function is an effective way to allow compilers to optimize that function:

int f(const int *restrict p) {
  int n=*p;
  printf("Debug\n");
  return *p==n;
}

Here Clang 17 with -O3 will just return 1 without re-examining *p, and without performing the comparison. Without restrict, *p has to be re-examined and the comparison has to be performed. This is because printf is an external function, and the compiler doesn't know if it might modify *p. Indeed, if p happens to be pointing into the file position indicator of stdout, printf is actually going to modify it.

So, as a general principle, if you want maximum optimization for the function, and your function ever calls an external function, it is not meaningless to declare all your parameters restrict. Of course, this places a severe restriction on callers, because it requires them to promise that they will not call your function with pointers aliased into unexpected places.

My question goes further than this observation. I ask if restrict permits optimization of the callers of your function too?

int f(const int *restrict p);
int caller(int *p) {
  int n=*p;
  f(p);
  return *p==n;
}

It would seem to me that this guarantees to the compiler that f will not modify *p, thus it can omit re-examining *p and the comparison, and can safely return 1. Neither Clang nor GCC do this optimization.

I know it's OK that they don't optimize the caller. I am asking whether the are permitted to optimize. (This is primarily a question about the semantics of my program, not about performance.)

Answer 1

In this code:

int f(const int *restrict p);
int caller(int *p) {
  int n=*p;
  f(p);
  return *p==n;
}

the compiler cannot conclude that *p does not change during execution of f because the code below shows a definition of f and a call to caller in which the behavior is defined (does not violate the restrict requirements) yet the value of *p changes during execution of f:

extern int m[2];

int f(const int * restrict p)
{
    m[0] = 3;
    return p[1];
}

void bar(void)
{
    caller(m);
}

When f is called in this case, p points to m[0], so *p is m[0]. Since f changes m[0], the value of *p changes during execution of f, but this does not violate the restrict requirements because the restrict definition only imposes requirements if p is used, directly or indirectly, to access the object. C 2018 6.7.3.1 4 says:

During each execution of B, let L be any lvalue that has &L based on P. 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:…

In the above f, m[0] is accessed only through the lvalue m[0] and not through any lvalue whose address is based on p. So the prerequisite condition for restrict never occurs for m[0], so it imposes no constraints on whether or how m[0] is modified.

Answer 2

Two reasons this optimization isn't legal for an unknown f(const int *restrict p) when the caller() can only see a prototype:

• The restrict stuff only applies to objects that were actually accessed via the restrict pointer. f could ignore its arg (or access p[1] but not p[0]) and modify the caller's object via a global pointer. CPPreference omits this part of the ISO C standard's definition.
• f can legally cast away a const qualifier and modify the object unless the underlying object is const, so the optimization isn't valid even if there can't be any other pointer to the object floating around.

---

In general it's legal to cast away const, as long as the pointed-to object itself wasn't defined as const. The optimization you're suggesting would break with this f in this program which I think is free of UB:

void f(const unsigned *restrict p) {
    unsigned *unqualified_p = (unsigned*)p;
    ++*unqualified_p;  // *restrict p still exists but this pointer was derived from p
}

unsigned global;
int main(){          // aka caller(int *p)
    unsigned n = global;
    f(&global);
    return n == global;
}

This compiles cleanly with clang or gcc -O2 -Wall -Wextra. Godbolt. (And runs cleanly with -fsanitize=undefined, although I wouldn't be confident of UBsan catching const or restrict cast violations if I'm wrong and this isn't well-defined.)

---

Example of just the const part being enough to defeat optimization, with escape analysis giving the compiler everything you were hoping it could infer from restrict:

void g(const int *p);

int bar(){
    int a = 1;      // non-escaped local, no global pointer to it can exist
    g(&a);
    return a == 1;  // actually compares, not returning a constant
}

Optimization wouldn't be valid in this case. Unfortunately this demo isn't as good as I'd hoped because GCC and clang miss a valid optimization for passing a pointer to a const int local variable where the callee can't change it, because the actual object itself is const. A g that casted away const and modified the object would be UB. (If the initializer is a compile-time constant, compilers do constant propagation even across a call that passes the address.) (Godbolt).

int baz(int x){
    const int a = x, b = x;     // non-escaped locals, like the function arg
    // and the underlying objects are const so it would be UB for g to change them
    g(&a);
    return a == b;  // GCC and clang still compare!
    // return x == b;  // does optimize out the compare, neither local escapes
}

int barc(){
    const int a = 1;
    g(&a);
    return a == 1;  // constant folding to return 1
}

---

restrict only kicks in on access.

https://en.cppreference.com/w/c/language/restrict says if some object that is accessible through P (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 UB].

But the requirement isn't just that the object is accessible, it's that it actually was accessed. (Thanks @Eric Postpischil for catching this.) From the C 2018 standard (n2310), 6.7.3.1 Formal definition of restrict

[definitions of B as a block, P as a restrict pointer, etc.]

4. During each execution of B, let L be any lvalue that has &L based on P. 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. Every access that modifies X shall be considered also to modify P, for the purposes of this subclause. If P is assigned the value of a pointer expression E that is based on another restricted pointer object P2, associated with block B2, then either the execution of B2 shall begin before the execution of B, or the execution of B2 shall end prior to the assignment. If these requirements are not met, then the behavior is undefined.

5. Here an execution of B means that portion of the execution of the program that would correspond to the lifetime of an object with scalar type and automatic storage duration associated with B.

[later stuff is all just examples, no further clauses that impose any restrictions on behaviour.]

Everything is conditional on the value actually being accessed via a restrict pointer. This is confirmed earlier in 6.7.3 with "An object that is accessed through a restrict-qualified pointer has a special association with that pointer..."

int *global_ptr;
// No UB even if called with p == global_ptr
void f1(const int *restrict p) {
   *global_ptr = 1;  // which happens to point at the same object as p
}

// also legal with p == global_ptr
void f2(const int *restrict p) {
   p[1]++;
   *global_ptr = 1;  // points at p[0]
}

The CPPreference page about C restrict appears to also have a mistake in its discussion of const, in the function parameter section. They talk about the possibility of f taking float const * restrict b and what that implies, but it's written as if casting away const wasn't legal. (Unless I'm misreading what they're saying and they meant with the actual definition visible, not just a prototype.)