Using restrict to express possible partial overlap

Question

Given type definitions

struct a { int a; };
struct b { int b; struct a ba;};

and a function taking struct a* a and struct b* b, the type information expresses possible overlap between a->a and b->ba.a but no overlap on b->b.

Therefore in a function such as:

int possibleOverlapOn2ndInt(struct a *a, struct b *b){
    b->b  = 0xbb; //unaliased
    b->ba.a  = 0xba; //may alias a->a
    a->a  = 0xaa; //may alias b->ba.a;
    return b->b /*0xbb*/ + b->ba.a;
}

compilers need not reload b->b in the return line and instead they may substitute the stored constant. Gcc and clang indeed do this.

I am curious if this case of possible partial overlap could be expressed without via restrict without using structs.

I've tried:

int possibleOverlapOn2ndInt_(int a[1], int b[2]){ //<=> (int *a, int *b)
    int *restrict bp = &b[0];
    bp[0] = 0xbb; //unaliased
    b[1] = 0xba; //may alias a[0]
    a[0] = 0xaa; //may alias b[1]
    return bp[0] /*0xbb?*/ + b[1];
}

but got no effect from having the restricted pointer there. https://godbolt.org/z/9Y7zz37rs

Am I using restrict wrong here is it the compilers not optimizing as well as they could?

Answer 1

Am I using restrict wrong here is it the compilers not optimizing as well as they could?

restrict-qualification puts constraints on program behavior intended to allow optimizations that otherwise might be assumed unsafe on the basis of possible aliasing. In any particular case, however, that does not imply that the compiler has missed an optimization opportunity if it generates the same code both with and without restrict. Therefore, I'll focus mainly on the first part of the question.

These are the constraints associated with use of restrict, from C17 6.7.3.1, somewhat contextualized to your example:

Let D be a declaration of an ordinary identifier that provides a means of designating an object P as a restrict-qualified pointer to type T.

D is int *restrict bp = &b[0];.
P is bp.
T is int.

[...] let B denote the block.

B is the whole body of function possibleOverlapOn2ndInt_().

In what follows, a pointer expression E is said to be based on object P if (at some sequence point in the execution of B prior to the evaluation of E) modifying P to point to a copy of the array object into which it formerly pointed would change the value of E.

No such expressions E appear in possibleOverlapOn2ndInt_(), other than bp itself. In particular, neither a nor b is such an expression.

During each execution of B, let L be any lvalue that has &L based on P.

Neither a[0] nor b[0] nor b[1] satisfies that description. The only such lvalue appearing in possibleOverlapOn2ndInt_() is bp[0].

If L is used to access the value of the object X that it designates,

bp[0] is used to access the object it designates.

and X is also modified (by any means),

The object designated by bp[0] is modified (via bp[0] itself).

then the following requirements apply: [...] Every other lvalue used to access the value of X shall also have its address based on P.

This would be violated if a[0] aliased bp[0] (and therefore also b[0]) in any execution of possibleOverlapOn2ndInt_().

[...] If these requirements are not met, then the behavior is undefined.

If the compiler assumed that the behavior of every execution of possibleOverlapOn2ndInt_() has defined behavior, including with respect to restrict qualification, then it could generate code as if the function were written like so:

int possibleOverlapOn2ndInt_2(int a[1], int b[2]) {
    b[0] = 0xbb;
    b[1] = 0xba;  // cannot alias b[0]
    a[0] = 0xaa;  // must not alias b[0], may alias b[1]
    return 0xbb + b[1];
}

The compiler is by no means required to make use of that freedom, however.

Answer 2

Use it in the parameter list. bp is not restricted as it holds reference from the not-restricted pointer.

int possibleOverlapOn2ndInt_(int * restrict a, int *b){ //<=> (int *a, int *b)
    b[0] = 0xbb; //unaliased
    b[1] = 0xba; //may alias a[0]
    a[0] = 0xaa; //may alias b[1]
    return b[0] /*0xbb?*/ + b[1];

https://godbolt.org/z/89jb5hd4c

Maybe I misunderstood the question.

Answer 3

From what I can tell, while clang and gcc are sometimes extremely aggressive in their treatment of restrict qualifiers on function arguments, treating as UB some situations at least some authors of the Standard probably intended to define, neither seems to do apply even the most straightforward possible optimizations when the qualifier is used elsewhere. For example, given:

int x[10];
int test1(int *restrict p, int i)
{
    if (p+i != x)
        return 0;
    p[0] = 1;
    p[i] = 2;
    return 23 * p[0];
}
int test2(int *p, int *q)
{
    int *restrict pp = p;
    *pp = 1;
    *q = 2;
    return 23 * *pp;
}

both clang and gcc will generate code for test1 that returns 23 in the case where i is zero and p happens to equal x, but both will generate code for test2 that reads *pp and multiplies the result by 23, rather than recognizing that pp and q cannot alias.