llvm dev - Feb 2020 - 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200214/f91a6da6/attachment.html>

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



From: Alexey Zhikhartsev <alexey.zhikhar at gmail.com>
Sent: Friday, February 14, 2020 22:52
To: via Llvm-dev <llvm-dev at lists.llvm.org>
Cc: Jeroen Dobbelaere <dobbel at synopsys.com>; hfinkel at anl.gov
Subject: 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<https://urldefense.proofpoint.com/v2/url?u=http-3A__port70.net_-7Ensz_c_c11_n1570.html-236.7.3.1&d=DwMFaQ&c=DPL6_X_6JkXFx7AXWqB0tg&r=ELyOnT0WepII6UnFk-OSzxlGOXXSfAvOLT6E8iPwwJk&m=xMDqkSAlj-YCOS4JMDXAENpBS-eaCcLYSkIm1qK68fs&s=B3LRzqpd9bD1724nvhG0FtpFh3QPsQ4FTBGQ4qJn1cA&e=>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200215/123add23/attachment.html>

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?


On Sat, Feb 15, 2020 at 9:00 AM Jeroen Dobbelaere <
Jeroen.Dobbelaere at synopsys.com> wrote:
> 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
>
>
>
>
>
>
>
> *From:* Alexey Zhikhartsev <alexey.zhikhar at gmail.com>
> *Sent:* Friday, February 14, 2020 22:52
> *To:* via Llvm-dev <llvm-dev at lists.llvm.org>
> *Cc:* Jeroen Dobbelaere <dobbel at synopsys.com>; hfinkel at anl.gov
> *Subject:* 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
>
<https://urldefense.proofpoint.com/v2/url?u=http-3A__port70.net_-7Ensz_c_c11_n1570.html-236.7.3.1&d=DwMFaQ&c=DPL6_X_6JkXFx7AXWqB0tg&r=ELyOnT0WepII6UnFk-OSzxlGOXXSfAvOLT6E8iPwwJk&m=xMDqkSAlj-YCOS4JMDXAENpBS-eaCcLYSkIm1qK68fs&s=B3LRzqpd9bD1724nvhG0FtpFh3QPsQ4FTBGQ4qJn1cA&e=>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200219/14510c24/attachment.html>