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

[Jeroen Dobbelaere via llvm-dev]

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>