8

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

Improve this question
1
  • 1
    Note that a very effective way to let your callers be optimized is to declare the function pure: int f(const int *p) __attribute__((pure)); (would be [[reproducible]] in the upcoming C23 standard). However, here f is not pure (as it prints to stdout). Hopefully restrict is a way to say that the function is pure with respect to that particular pointer. Commented Jan 10, 2024 at 9:14

2 Answers 2

Reset to default
5

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

That is a very good example, especially the fact that your f is meaningfully accessing something through p, but not accessing *p itself through p. Exactly what I was asking for.
It demonstrates that restrict just cannot be used to optimize callers of a function period, no matter what other qualifications/tricks (such as const) you attempt to add.
3

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

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

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

Improve this answer

6 Comments

Re “You're right that the caller can assume *p wasn't accessed via any other path, though”: No, the caller cannot assume that. The formal definition of restrict imposes constraints only if an lvalue based on p is used to access an object. If the function never accesses *p via p (e.g., only uses p for comparison or accesses p[1] but not p[0]), then *p may be changed by other means (modified through another pointer or through an external identifier).
@EricPostpischil: That's not what CPPreference says; perhaps they got that wrong? They say if the pointed-to object is modified at all (which could include via *global_ptr), then all access to it within the block must be via p. en.cppreference.com/w/c/language/restrict - if some object that is accessible through P (directly or indirectly) is modified, by any means, ... Oh, hmm, the case you're talking about doesn't have any accesses to *p via p in the block itself, only via the other path. (From a different block, but during the lifetime of p.)
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:…” That is the only paragraph in the definition of restrict that imposes constraints. cppreference.com is wrong. Consider a copy routine that copied from one pointer and offset to another pointer and offset. Should it violate restrict when the caller passes the same pointer with different offsets for non-overlapping segments?
More simply, extern int m[2]; int f(int * restrict p) { m[0] = 3; p[1] = 4; } void bar(void) { f(m); } has defined behavior because, while the object designated by *p changes in f, it is never accessed by an lvalue L whose address &L is based on p. It is only accessed by m[0], which is not based on p.
@PeterCorders, I agree with both of your points, both are very relevant. Neglecting const semantics of C was my mistake. The second point about access is at the heart of restrict semantics, which was what the question was primarily about. So I am going to accept Eric's answer, which seems to be the first to make the point about access. Truly sorry that I cannot accept both answers, I do hope readers will read both.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.