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

[Jeroen Dobbelaere via llvm-dev]

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>