thr3ads.net - llvm dev - [llvm-dev] Given one restrict pointer based on another, should they never alias? [Feb 2020]

If this information is useful, please help other people find it:
Share via:

Alexey Zhikhartsev via llvm-dev

2020-Feb-20 00:55 UTC

[llvm-dev] Given one restrict pointer based on another, should they never alias?

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>

Jeroen Dobbelaere via llvm-dev

2020-Feb-20 14:42 UTC

head link

[llvm-dev] Given one restrict pointer based on another, should they never alias?

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 ;)
(See: https://reviews.llvm.org/D68512#inline-681480 )

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

Jeroen


From: Alexey Zhikhartsev <alexey.zhikhar at gmail.com>
Sent: Thursday, February 20, 2020 01:56
To: Jeroen Dobbelaere <dobbel at synopsys.com>
Cc: via Llvm-dev <llvm-dev at lists.llvm.org>; hfinkel at anl.gov
Subject: Re: Given one restrict pointer based on another, should they never
alias?

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<mailto: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<mailto:alexey.zhikhar at gmail.com>>
Sent: Friday, February 14, 2020 22:52
To: via Llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at
lists.llvm.org>>
Cc: Jeroen Dobbelaere <dobbel at synopsys.com<mailto:dobbel at
synopsys.com>>; hfinkel at anl.gov<mailto: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/20200220/d67180cc/attachment.html>

Alexey Zhikhartsev via llvm-dev

2020-Feb-21 01:16 UTC

head link

[llvm-dev] Given one restrict pointer based on another, should they never alias?

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.

On Thu, Feb 20, 2020 at 9:42 AM Jeroen Dobbelaere <
Jeroen.Dobbelaere at synopsys.com> wrote:
> 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 ;)
>
> (See: https://reviews.llvm.org/D68512#inline-681480 )
>
>
>
> I hope to find some time in March to resurrect the activity on those
> patches...
>
>
>
> Jeroen
>
>
>
>
>
> *From:* Alexey Zhikhartsev <alexey.zhikhar at gmail.com>
> *Sent:* Thursday, February 20, 2020 01:56
> *To:* Jeroen Dobbelaere <dobbel at synopsys.com>
> *Cc:* via Llvm-dev <llvm-dev at lists.llvm.org>; hfinkel at anl.gov
> *Subject:* Re: Given one restrict pointer based on another, should they
> never alias?
>
>
>
> 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/20200220/b7e19317/attachment.html>

llvm dev - Feb 2020 - Given one restrict pointer based on another, should they never alias?

[llvm-dev] Given one restrict pointer based on another, should they never alias?

[llvm-dev] Given one restrict pointer based on another, should they never alias?

[llvm-dev] Given one restrict pointer based on another, should they never alias?