[Bug tree-optimization/67705] New: incorrect restrict interpretation

[Bug tree-optimization/67705] New: incorrect restrict interpretation

[vries at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67705

            Bug ID: 67705
           Summary: incorrect restrict interpretation
           Product: gcc
           Version: 6.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: vries at gcc dot gnu.org
  Target Milestone: ---

I think I found an example for which the compiler misinterprets restrict.

Consider test-case test.c:
...
void
f (int *__restrict__ &__restrict__ fp,
   int *__restrict__ &__restrict__ fp2)
{
  *fp = 1;
  *fp2 = 2;
}

void
g (int *__restrict__ gp)
{
  f (gp, gp);
}

void
h (void)
{
  int ha;
  g (&ha);
}
...

At the ealias dump we see that the two stores are disambiguated, due to the
fact that they're in the same clique (1) but have different bases (base 2 and
base 4):
...
void f(int* __restrict__&, int* __restrict__&) (intD.9 * restrict & restrict
fpD.2252, intD.9 * restrict & restrict fp2D.2253)
{
  intD.9 * _3;
  intD.9 * _6;

  # VUSE <.MEM_1(D)>
  # PT = { D.2269 } (nonlocal)
  _3 = MEM[(intD.9 * restrict &)fp_2(D) clique 1 base 1];

  # .MEM_4 = VDEF <.MEM_1(D)>
  MEM[(intD.9 *)_3 clique 1 base 2] = 1;

  # VUSE <.MEM_4>
  # PT = { D.2271 } (nonlocal)
  _6 = MEM[(intD.9 * restrict &)fp2_5(D) clique 1 base 3];

  # .MEM_7 = VDEF <.MEM_4>
  MEM[(intD.9 *)_6 clique 1 base 4] = 2;
...

>From the example, it's obvious that the stores in fact alias, because we call f
with the two arguments being identical.

The question is if this is a valid example, in other words, doesn't passing
identical arguments violate the second restrict in both "int *__restrict__
&__restrict__ fp" and "int *__restrict__ &__restrict__ fp2"?

I think the example is valid, due to the "modified" wording in the restrict
definition.

In the case of the second restrict, the object being referenced is gp. And gp
is not modified during execution of f, so the restrict has no impact.

This link has an explanation of the "modified" wording:
http://www.lysator.liu.se/%28nobg%29/c/restrict.html at "Aliasing of unmodified
objects".

It's to allow a call "f10(x, y, y)" to this function:
...
void
f10 (int n, float *restrict a, float *restrict b, float *restrict c)
{
  int i;
  for ( i=0; i<n; i++ )
    a[i] = b[i] + c[i];
}
...
The object pointed to by y is not modified in f10, so we're allowed to mark
both b and c restrict. And marking b and c restrict helps compilers which only
disambiguate is both pointers are restrict (PR48885), in other words, it allows
those compilers to disambiguate between first a[i] and b[i], and second a[i]
and c[i].

The downside of the "modified" wording is: "... allow aliasing through two
restrict-qualified pointers provided the referenced objects are not modified.
Unfortunately, if those objects are themselves pointers (i.e., there are two
levels of indirection), this aliasing can inhibit optimization, even if the
secondary pointers are also restrict-qualified and used to modify the objects
to which they, in turn, refer.  See X3J11.1/93-040 for examples."

I think test.c above is such an example (I have no access to X3J11.1/93-040
though).

[Bug tree-optimization/67705] incorrect restrict interpretation

[glisse at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67705

--- Comment #1 from Marc Glisse <glisse at gcc dot gnu.org> ---
Isn't that an old document? At least, I don't reach the same conclusions as you
do using the C11 wording:

1 Let D be a declaration of an ordinary identifier that provides a means of
designating an object P as a restrict-qualified pointer to type T.
2 If D appears inside a block and does not have storage class extern, let B
denote the block. If D appears in the list of parameter declarations of a
function definition, let B denote the associated block. Otherwise, let B denote
the block of main (or the block of whatever function is called at program
startup in a freestanding environment).
3 In what follows, a pointer expression E is said to be based on object P if
(at some sequence point in the execution of B prior to the evaluation of E)
modifying P to point to a copy of the array object into which it formerly
pointed would change the value of E. 137) Note that ‘‘based’’ is defined only
for expressions with pointer types.

(also, int*q=p; inside B means that q is based on p, despite what Richard said
in PR48885)
>From gcc-bugs-return-497963-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Thu Sep 24 09:19:17 2015
Return-Path: <gcc-bugs-return-497963-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 121092 invoked by alias); 24 Sep 2015 09:19:17 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 121062 invoked by uid 48); 24 Sep 2015 09:19:13 -0000
From: "pinskia at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug c/67680] Seg Fault in gcc 4.9.3 compiling libiberty/floatformat.c when building gcc 5.2.1 on Cygwin 64 on Windows
Date: Thu, 24 Sep 2015 09:19:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: c
X-Bugzilla-Version: 4.9.3
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: pinskia at gcc dot gnu.org
X-Bugzilla-Status: WAITING
X-Bugzilla-Resolution:
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields:
Message-ID: <bug-67680-4-sTnGMUG3PE@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-67680-4@http.gcc.gnu.org/bugzilla/>
References: <bug-67680-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2015-09/txt/msg01941.txt.bz2
Content-length: 296

https://gcc.gnu.org/bugzilla/show_bug.cgi?idg680

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Where did you get gmp/mpfr from?  The crash looks like either one of those two
are crashing?  If you compiled them yourself, did you run make check and was
there any failures?

[Bug tree-optimization/67705] incorrect restrict interpretation

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67705

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jsm28 at gcc dot gnu.org,
                   |                            |rguenth at gcc dot gnu.org

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
Indeed the wording contains "and X is also modified (by any means)." thus
fp == fp2 are valid even though they are marked restrict.  Btw, lets forgo
the use of references here and talk plain C:

void
f (int *__restrict__ *__restrict__ fp,
   int *__restrict__ *__restrict__ fp2)
{
  int *p = *fp;   // 1
  int *p2 = *fp2; // 2
  *p = 1;         // 3
  *p2 = 2;        // 4
}

void
g (int *__restrict__ gp)
{
  f (gp, gp);
}

void
h (void)
{
  int ha;
  g (&ha);
}

which better explains the issue you are rising.  The standard doesn't talk
about stmts 1 and 2 (they do not modify anything).  We are interested on
whether the writes 3 and 4 may alias or not.  *p and *p2 would have to
be based on the same pointer: "Every other lvalue used to access the value
of X shall also have its address based on P."

The "pointer expression" here are *fp or *fp2 and either p needs to be
dependent on p2 or p2 needs to be dependent on p.  Both are not the
case IMHO - that both p and p2 are dependent on "*gp" does not count.

I don't think writing

  **fp = 1;
  **fp2 = 2;

changes any of this.  If it does then this is worth a DR I think.
I think the standard refers to 'P' as rvalue, thus "modifying P
to point to a copy of the array object..." would not modify the lvalue *fp
but the rvalue *fp.

But yes, my original reasoning that *fp and *fp2 cannot refer to the same
storage is moot.

Adding Joseph.

[Bug tree-optimization/67705] incorrect restrict interpretation

[vries at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67705

--- Comment #3 from vries at gcc dot gnu.org ---
(In reply to Richard Biener from comment #2)
> Indeed the wording contains "and X is also modified (by any means)." thus
> fp == fp2 are valid even though they are marked restrict.  Btw, lets forgo
> the use of references here and talk plain C:
> 

Agreed, that makes it easier to name the individual bits.

> void
> f (int *__restrict__ *__restrict__ fp,
>    int *__restrict__ *__restrict__ fp2)
> {
>   int *p = *fp;   // 1
>   int *p2 = *fp2; // 2
>   *p = 1;         // 3
>   *p2 = 2;        // 4
> }
> 
> void
> g (int *__restrict__ gp)
> {
>   f (gp, gp);

After forgoing the references, that should be
    f (&gp, &gp);

> }
> 
> void
> h (void)
> {
>   int ha;
>   g (&ha);
> }
> 
> which better explains the issue you are rising.  The standard doesn't talk
> about stmts 1 and 2 (they do not modify anything). We are interested on
> whether the writes 3 and 4 may alias or not.

Agreed.

> *p and *p2 would have to
> be based on the same pointer: "Every other lvalue used to access the value
> of X shall also have its address based on P."
> 

I interpret this as follows.

Restrict declaration D: "int *__restrict__ gp"
Type T: int
Object P: gp
Block B: g function block
Lvalues: *p and *p2
Objects designated by lvalues: ha in both cases.
Object ha modified during execution of B: yes
&Lvalues: pointer expressions p and p2 (or equivalently, 
          pointer expressions *fp and *fp2)

Now, the question is: are pointer expressions p and p2 based on gp? I think so.
If we modify gp to point to a copy of ha before calling f in g, then both
pointer expressions p and p2 (and *fp and *fp2) will change value.

> The "pointer expression" here are *fp or *fp2

Agreed.

> and either p needs to be
> dependent on p2 or p2 needs to be dependent on p.
>  Both are not the
> case IMHO

They are indeed not dependent on each other, but I think that's not relevant.

> - that both p and p2 are dependent on "*gp" does not count.

I think what's relevant is that both pointer expressions p and p2 are based on
object P gp.

> I don't think writing
> 
>   **fp = 1;
>   **fp2 = 2;
> 
> changes any of this.

Agreed.

> If it does then this is worth a DR I think.

> I think the standard refers to 'P' as rvalue, 

The standard refers to P as a pointer object.

> thus "modifying P
> to point to a copy of the array object..." would not modify the lvalue *fp
> but the rvalue *fp.
> 

Modifying gp will modify pointer expressions p, p2, *fp and *fp2. The standard
does not mention any distinction between lvalue or rvalue pointer expressions.

[Bug tree-optimization/67705] incorrect restrict interpretation

[joseph at codesourcery dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67705

--- Comment #4 from joseph at codesourcery dot com <joseph at codesourcery dot com> ---
Regarding multiple levels of restricted pointers, please see my 
annotations of the C99 wording at 
<https://gcc.gnu.org/ml/gcc-bugs/2005-01/msg03394.html>, in particular as 
regards the wording "Every access that modifies X shall be considered also 
to modify P, for the purposes of this subclause.".

[Bug tree-optimization/67705] incorrect restrict interpretation

[vries at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67705

vries at gcc dot gnu.org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|---                         |INVALID

--- Comment #6 from vries at gcc dot gnu.org ---
(In reply to rguenther@suse.de from comment #5)
> On September 24, 2015 6:28:16 PM GMT+02:00, joseph at codesourcery dot com
> <gcc-bugzilla@gcc.gnu.org> wrote:
> >https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67705
> >
> >--- Comment #4 from joseph at codesourcery dot com <joseph at
> >codesourcery dot com> ---
> >Regarding multiple levels of restricted pointers, please see my 
> >annotations of the C99 wording at 
> ><https://gcc.gnu.org/ml/gcc-bugs/2005-01/msg03394.html>, in particular
> >as 
> >regards the wording "Every access that modifies X shall be considered
> >also 
> >to modify P, for the purposes of this subclause.".
> 
> Ah, indeed this makes the testcase invalid iff both pointers are the same
> As the reads from FP and fp2 are considered modifications.

Agreed, that makes the testcase invalid. Marking resolved-invalid.