Is it enough to only restrict the "out"-(pointer-)parameters of a function?

Question

Suppose I have a function which takes some pointer parameters - some non-const, through which it may write, and some const through which it only reads. Example:

void f(int * a, int const *b);

Suppose also that the function does not otherwise write to memory (i.e. doesn't use global variables, fixed addresses, recasting the const pointers as non-const and such tricks).

Now, is it sufficient (as per the C language standard), for achieving the benefits of restrict for all reads within f(), to only restrict the output parameters? i.e. in the example, restrict a but not b?

A simple test (GodBolt) suggests such restriction should be sufficient. This source:

int f(int * restrict a, int const * b) {
    a[0] += b[0];
    return a[0] + b[0];
}

int all_restricted(int * restrict a, int const * restrict b) {
    a[0] += b[0];
    return a[0] + b[0];
}

int unrestricted(int * a, int const * b) {
    a[0] += b[0];
    return a[0] + b[0];
}

Produces the same object code for x86_64:

f:
        mov     eax, DWORD PTR [rsi]
        mov     edx, DWORD PTR [rdi]
        add     edx, eax
        mov     DWORD PTR [rdi], edx
        add     eax, edx
        ret
all_restricted:
        mov     eax, DWORD PTR [rsi]
        mov     edx, DWORD PTR [rdi]
        add     edx, eax
        mov     DWORD PTR [rdi], edx
        add     eax, edx
        ret
unrestricted:
        mov     eax, DWORD PTR [rsi]
        add     eax, DWORD PTR [rdi]
        mov     DWORD PTR [rdi], eax
        add     eax, DWORD PTR [rsi]
        ret

but that's not a general guarantee.

Quan

in this trivial example, no additional optimizations are possible when you declare the pointer as restrict. What did you expect? – Knockabout

@0___________: But if you remove all the restrictions, a pessimization is necessary. Added that to the question. – Quan

The restrict only matters when data are modified. Thus modification of data pointer by a restricted pointer a mean that all other access to this data must be done via a. So any access via pointer b can never alias data pointed by a. So even const is no longer necessary for optimization and in practice it never is. See godbolt.org/z/a6bGYvhsG – Courser

@tstanisl: Yes, I realize const is not necessary for the optimization. I was asking whether the restrict on the outputs is sufficient. You seem to be saying that it is... can you back this up with a quote from the standard? – Quan

@Quan As I see it: 1) int * restrict a implies that the pointer a given to the function does not overlap other referenced data. All changes to *a are directly visible in the function. int const * b, without restrict does not have this guarantee for *b. The const implies the function will not directly change its *b, yet changing *a, as in a[0] += b[0]; still could change *b via f(p, p); 2) Posted assembly is an indicator, but not sufficient. Mis-called functions, that prevents an unsafe argument, result in UB. Emitted code does not have to be different. – Yucca

@chux-ReinstateMonica: That is my view as well, but - I'm looking for something more official. PS - Does Monica Cellio even want to be reinstated at this point? – Quan

@Quan Sorry I am unable to provide - deep dives into restrict have been time expensive for me. I simply go on the idea that restrict on a does not help b to have some restrict properties in any way – Yucca

Answer 1

No, it is not enough.

Suppose also that the function does not otherwise write to memory (i.e. doesn't use global variables, fixed addresses, recasting the const pointers as non-const and such tricks).

This supposition is insufficient. It would also be necessary that the compiler see the function does not otherwise write to memory that the pointer points to (including any memory that could be accessed via the pointer, such as b[18]). For example, if the function f calls bar(b);, and the compiler cannot see bar, then it cannot know whether memory that b points to is modified during execution of f, even if it is not.

Give this additional premise, that the compiler can see there are no modifications to any memory pointed to via b, then it does not matter for optimization whether b is declared with const and/or restrict: The compiler knows everything about the memory, and telling it anything more does not add information.

However, it is often not the case that code satisfies this premise. (And even when it does, it may be a nuisance for a programmer to be sure of it.) So let’s consider a case when we do not have the additional premise:

void f(int * restrict a, int const *b)
{
    printf("%d\n", *b);
    bar();
    printf("%d\n", *b);
}

When bar is called, the compiler does not know whether *b is modified. Even though this function does not pass b to bar, bar might access some external object that is *b or has a pointer to where *b is, and so bar can change the object that is *b. Therefore, the compiler must reload *b from memory for the second printf.

If instead we declare the function void f(int * restrict a, int const * restrict b), then restrict asserts that, if *b is modified during execution of f (including indirectly, inside bar), then every access to it will be via b (directly, as in *b, or indirectly, as through a pointer visibly copied or calculated from b). Since the compiler can see bar does not receive b, it knows bar does not contain any accesses to *b that are based on b, and therefore it may assume bar does not change *b.

Therefore, adding restrict to a parameter that is a pointer to a const-qualified type may enable some optimizations, even if all other parameters are also declared restrict.

Dissect

Good observation about "supposition is insufficient." – Yucca

Answer 2

The const keyword as shown will cause a warning or error if you attempt to modify the value pointed by the pointer, but it will not necessarily prevent you from modifying that value, and it certainly will not prevent someone else from modifying that value. Thus, the compiler may have to assume that such modifications may take place.

For example, if you invoke some function defined in a different source file, the compiler will have no knowledge of what that function does, so it will have to assume that the function may somehow have access to the value pointed by that pointer and it may modify it.

Furthermore, even as you modify the value pointed by the non-const pointer, that non-const pointer may be pointing to the same value as the const pointer. (As in, f( &x, &x );) Without restrict on the const pointer, the compiler has to assume that this is also a possibility.

Therefore, even the const parameter could benefit from the restrict keyword, because it promises that the memory pointed by that pointer will not be modified by anyone. Essentially, you would be promising that you are never going to do something like f( &x, &x );.

Subvert

This claim is invalid. If the object is not volatile then you promise that the referenced object will not be changed by anything when function is executed. – Knockabout

@Knockabout I used to think the same about volatile, but as it turns out, this is not the case. If you invoke another function, the compiler has to consider the possibility that the other function may change the memory pointed by the const pointer. If you modify the value pointed by another pointer, the compiler has to consider the possibility that the other pointer might point to the same location as the const pointer. – Subvert

"I would assume" - well, that's, just, like, your opinion, man... – Quan

“The const keyword on a pointer is a binding promise that you will not (can not) modify the memory pointed by the pointer” is false. When qualifying a pointed-to type, const serves only an advisory function: The C implementation must issue a diagnostic if a const-qualified lvalue is the subject of an assignment or other operation that would modify it (such as ++). Defining an object as a const-qualified type means the implementation may assume it is never modified. But the type used to point to an object and the type used to define an object are completely independent:… – Dissect

… You may have all combinations, const pointer to a const object, a const pointer to a non-const object, a non-const pointer to a const object, and a non-const pointer to a non-const object. When ` const` pointer points to a non-const object, it is entirely defined to take the pointer to const, cast it to non-const, and use it to modify the object. This may even happen out of sight of the compiler, by passing the const pointer to another function that does it. – Dissect

@EricPostpischil okay, so what would you have me rather write instead of "The const keyword on a pointer"? Should I write "A pointer to const"? – Subvert

@MikeNakis: You appear to have misunderstood. The issue is not about the phrasing. int const *b is not a promise that the function will not modify memory that b points to, nor it is a promise that the function will not modify memory that b points to via use of b. What the const is int const *b does is ensure the user will be advised, by diagnostic message, if they use *b (or related forms, such as b[i]) has an lvalue in a context where a modifiable lvalue is required. Its function is advice to the user, not a promise to the implementation. – Dissect

Okay then, (and thank you for discussing it with me,) how about this: "The const keyword will likely prevent you from modifying the memory pointed by the pointer; however, ..." – Subvert

Perhaps “The const in int const *b will cause the compiler to give you a warning or error if you attempt to modify *b, but it does not assure the compiler *b will not be modified…” – Dissect

Answer 3

Suppose I have a function which takes some pointer parameters - some non-const, through which it may write, and some const through which it only reads. Example:

void f(int * a, int const *b);

Suppose also that the function does not otherwise write to memory (i.e. doesn't use global variables, fixed addresses, recasting the const pointers as non-const and such tricks).

Now, is it sufficient (as per the C language standard), for achieving the benefits of restrict for all reads within f(), to only restrict the output parameters? i.e. in the example, restrict a but not b?

restrict is one-sided. It licenses the compiler to make assumptions about object accesses via lvalues "based on" the restrict-qualified pointer that do not depend on whether any other pointer is also restrict-qualified.

In particular, if you restrict parameter a then regardless of whether you also restrict parameter b, you license the compiler to assume that during any given execution of f(),

• if L is any lvalue whose address is "based on" a, and
• L is used to access the object it designates (read or write), and
• that object is modified by any means during the function's execution, then
• every access to that object (read or write) during the execution of that function will be performed via an lvalue whose address is "based on" a, though not necessarily via L in particular.
• (For example, that object will not be accessed via an lvalue "based on" b but not on a.)

That is laid out in more detail in C17 section 6.7.3.1, though that text is both complex and a bit fraught.

Thus, in the case you describe, restricting only a entitles the compiler to assume that reads via pointers derived from b will never observe writes via pointers derived from a. Whether it actually will generate different code is an entirely different question, of course.

Cordle

"... entitles the compiler to assume... from a" <- But that does not answer the question with "Yes" or "No" :-( – Quan

@einpoklum, the leading "restrict is one-sided. It licenses the compiler to make assumptions [...] that do not depend on whether any other pointer is also restrict-qualified" is intended to be a more direct answer to the question posed. But my problem here is that I'm uncertain whether your expectations of "the benefits of restrict" match up with the spec, so rather than a flat "yes", I'm telling you exactly what benefits you can expect. – Cordle