Given one restrict pointer based on another, should they never alias?

We recently found an issue when using the full restrict implementation developed by Jeroen; it surfaces when compiling an obscure combination of std::valarray and std::indirect_array but I don’t want to bore you with all the details. What it boils down to is this basic question about restrict:

Given one restrict pointer based on another, should they never alias?

As far as I understand the formal definition of “restrict” in section 6.7.3.1 of the C standard [1], in the function below, pointer y is based on “restrict” pointer x; hence, the compiler will assume that accesses *x and *y might alias:

void assign1(int *pA, long N) {
int *restrict x = pA;
{
int *y = x + N;
*x = *y;
}
}

However, what if y itself is declared “restrict”: can the compiler assume that *x and *y will never alias?

void assign2(int *pA, long N) {
int *restrict x = pA;
{
int *restrict y = x + N;
*x = *y;
}
}

Both Jeroen’s and Hal’s implementation (the intrinsic-based one) will say “NoAlias” for the accesses in assign2() but shouldn’t x and y be in the same restrictness “bucket” since y is based on x?

[1] http://port70.net/~nsz/c/c11/n1570.html#6.7.3.1

Hi Alexey,

This is defined in 6.7.3.1 paragraph 4:

‘… Every other lvalue used to access the value of X shall also have its address based on P …’

For ‘assign1’:

  • x is a restrict pointer and is assumed to point to its own set of objects

  • y is a normal pointer, based on x

  • all access to the set of objects pointed by x are done through a pointer based on x

for ‘assign2’:

  • x is a restrict pointer and is assumed to point to its own set of objects

  • y is also a restrict pointer, based on x, but it is assumed to point to its own set of objects for the scope of y

  • because of that, *x and *y must never overlap, as all accesses to the objects of y must be done based on a pointer derived from y

As such, a N=0 will trigger undefined behavior in assign2

Doing the assignment to *x outside the inner block, makes the code valid again:

void assign3(int *pA, long N) {
int *restrict x = pA;

int tmp;
{
int *restrict y = x + N;
tmp = *y;
}

*x = tmp; // may alias with *y
}

Greetings,

Jeroen Dobbelaere

Thanks, Jeroen, that really helps.

A follow-up question, if you don’t mind. What if we have code somewhat similar to your example in assign3() but it’s in C++ and the pointer derived from x is stored in a class member field:

class S {
public:
S(int *d): data(d) {}
int *getData() { return data; }
private:
int *restrict data;
};

void assign4(int *pA, long N) {
int *restrict x = pA;
int tmp;
{
S s(x + N);
tmp = *s.getData();
}
*x = tmp;
}

I see that the full restrict implementation says that the load and the store do not alias. Is this by design?

Hi Alexey,

Thanks for the bug report !

this should indeed behave the same as ‘assign3’. With this code, you triggered a ‘FIXME’ in the full restrict patches :wink:

(See: https://reviews.llvm.org/D68512#inline-681480 )

I hope to find some time in March to resurrect the activity on those patches…

Jeroen

My pleasure, thanks for looking into it.

To clarify, is it correct to say that assign3 and assign4 are conceptually the same? That is, it makes no difference that a restrict pointer is a member variable, and it is private.