[Bug middle-end/14192] New: Restrict pointers don't help

[Bug middle-end/14192] New: Restrict pointers don't help

[hoogerbrugge at hotmail dot com]

I have two problems. It could be that they are related.

First. In the following code there is no dependence between the two stores 
which is what I would expect:

void restricttest2(int *restrict p, int *restrict q)
{
        *p = 0;
        *q = 0;
}

However, if only one of the two pointers is restrict then gcc generates a 
dependence. 

void restricttest1(int *restrict p, int *q)
{
        *p = 0;
        *q = 0;
}

According to my interpretation of the restrict spec this is not necessary. 
Also, two other (non-gcc) compilers that I have as a reference don't generate 
this dependence.

The second case is the following loop:

void copy(int *restrict pb, int *restrict qb)
{
        int i;

        for(i = 0; i < 100; i++)
        {
                qb[i] = pb[i]; i++;
                qb[i] = pb[i]; i++;
                qb[i] = pb[i]; i++;
                qb[i] = pb[i];
        }
}

When compiled with -fno-unroll-loops I see lots of dependences between the 
loads and stores. 

_copy:
        .function
        /***************************/
        ident r6 -> r35
        ident r5 -> r34
        ident r0 -> r33
        iaddi(99) r0 -> r36
L5:     asli(2) r33 -> r51
        iaddi(1) r33 -> r52
        asli(2) r52 -> r46
        iaddi(2) r33 -> r47
        iadd r51 r34 -> r50
        asli(2) r47 -> r41
        iaddi(3) r33 -> r42
        iadd r51 r35 -> r48
        ld32 r50 -> r49         [ID=1125][REGION=2]
        iadd r46 r34 -> r45
        st32 r48 r49            [ID=1031][REGION=2]
        asli(2) r42 -> r37
        iadd r46 r35 -> r43
        ld32 r45 -> r44         [ID=1126][REGION=2]
        iadd r41 r34 -> r40
        st32 r43 r44            [ID=1040][REGION=2]
        iadd r41 r35 -> r38
        ld32 r40 -> r39         [ID=1127][REGION=2]
        iadd r37 r34 -> r9
        st32 r38 r39            [ID=1049][REGION=2]
        iaddi(4) r33 -> r33
        iadd r37 r35 -> r8
        ld32 r9 -> r7           [ID=1128][REGION=2]
        st32 r8 r7              [ID=1058][REGION=2]
        igtr r33 r36 -> r6
        if !r6 ijmpi(L5)                [PROB=96]
        /***************************/
        ijmpf r0 r2     /* return */
        .depend 1128 -> 1058
        .depend 1049 -> 1058
        .depend 1127 -> 1049
        .depend 1040 -> 1049 1058
        .depend 1126 -> 1040
        .depend 1031 -> 1040 1049 1058
        .depend 1125 -> 1031
        .endfunction

(The .depend line indicate dependences between instructions (IDs))

However, in this loop there are no dependences at all:

void zero(int *restrict qb)
{
        int i;

        for(i = 0; i < 100; i++)
        {
                qb[i] = 0; i++;
                qb[i] = 0; i++;
                qb[i] = 0; i++;
                qb[i] = 0;
        }
}

I use "gcc version 3.5.0 20040119 (experimental)"

I observe the dependences in the INSN_DEPEND(insn) list in sched_finish().

-- 
           Summary: Restrict pointers don't help
           Product: gcc
           Version: 3.5.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: middle-end
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: hoogerbrugge at hotmail dot com
                CC: gcc-bugs at gcc dot gnu dot org
 GCC build triplet: linux
  GCC host triplet: linux
GCC target triplet: trimedia


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14192

[Bug middle-end/14192] Restrict pointers don't help

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-02-18 14:10 -------
*** Bug 14193 has been marked as a duplicate of this bug. ***

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14192

[Bug middle-end/14192] Restrict pointers don't help

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-02-18 14:15 -------
I cannot reproduce the problem you are having on powerpc-apple-darwin or i686-pc-linux-gnu with 
3.5-tree-ssa 20040208 (merged 20040126) or 3.5.0 20040204.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |pessimizes-code


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14192

[Bug middle-end/14192] Restrict pointers don't help

[hoogerbrugge at hotmail dot com]

------- Additional Comments From hoogerbrugge at hotmail dot com  2004-02-18 15:33 -------
I just did a update to version 3.5.0 20040218 and the problem is still there.

Are you not able to reproduce it because you don't have the sources of the my 
target port? If so, should I sent sources of the port?


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14192

[Bug middle-end/14192] Restrict pointers don't help

[hoogerbrugge at hotmail dot com]

------- Additional Comments From hoogerbrugge at hotmail dot com  2004-02-19 14:02 -------
I can demonstrate the problem on ia64. Here are three cases:

int zero_restrict_pointers(int *p, int *q)
{
        *p = 0;
        return *q;
}

int one_restrict_pointer(int *restrict p, int *q)
{
        *p = 0;
        return *q;
}

int two_restrict_pointers(int *restrict p, int *restrict q)
{
        *p = 0;
        return *q;
}

This gives the following ia64 code (version 20040217):

        .pred.safe_across_calls p1-p5,p16-p63
        .text
        .align 16
        .global zero_restrict_pointers#
        .proc zero_restrict_pointers#
zero_restrict_pointers:
        .prologue
        .body
        .mmb
        nop 0
        st4 [r32] = r0
        nop 0
        .mbb
        ld4 r8 = [r33]
        nop 0
        br.ret.sptk.many b0
        .endp zero_restrict_pointers#
        .align 16
        .global one_restrict_pointer#
        .proc one_restrict_pointer#
one_restrict_pointer:
        .prologue
        .body
        .mmb
        nop 0
        st4 [r32] = r0
        nop 0
        .mbb
        ld4 r8 = [r33]
        nop 0
        br.ret.sptk.many b0
        .endp one_restrict_pointer#
        .align 16
        .global two_restrict_pointers#
        .proc two_restrict_pointers#
two_restrict_pointers:
        .prologue
        .body
        .mmb
        nop 0
        ld4 r8 = [r33]
        nop 0
        .mbb
        st4 [r32] = r0
        nop 0
        br.ret.sptk.many b0
        .endp two_restrict_pointers#
        .ident  "GCC: (GNU) 3.5.0 20040217 (experimental)"


As you can imagine, the scheduler wants to schedule the long latency
load above the store. As you can see, this only happens in the case 
of two restrict pointers. I would also like to see it happen in the
case of one restrict pointer.



-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14192

[Bug middle-end/14192] Restrict pointers don't help

[giovannibajo at libero dot it]

------- Additional Comments From giovannibajo at libero dot it  2004-10-11 10:56 -------
Zack, do you confirm that the semantics of restrict (in C99 and/or GNU C) allow 
us to schedule the load before the store even if there is only one restrict 
pointer? Otherwise, this bug report is invalid.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |zack at gcc dot gnu dot org,
                   |                            |giovannibajo at libero dot
                   |                            |it


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14192

[Bug middle-end/14192] Restrict pointers don't help

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2005-01-23 18:48 -------
Zack, Joseph, could one of you comment on Jan's interpretation of 
the semantics of restrict? 
 
This restrict keyword keeps coming back to haunt us, bah. 
 
 

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jsm28 at gcc dot gnu dot org
             Status|UNCONFIRMED                 |WAITING


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14192

[Bug middle-end/14192] Restrict pointers don't help

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2005-01-23 18:51 -------
We should probably have a metabug for restrict.  We don't take advantage 
of the restrict keyword very well either in some (unfortunately proprierty) 
benchmark suites. 
 

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
  BugsThisDependsOn|                            |14187


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14192

[Bug middle-end/14192] Restrict pointers don't help

[joseph at codesourcery dot com]

------- Additional Comments From joseph at codesourcery dot com  2005-01-23 20:59 -------
Subject: Re:  Restrict pointers don't help

On Sun, 23 Jan 2005, steven at gcc dot gnu dot org wrote:

> Zack, Joseph, could one of you comment on Jan's interpretation of 
> the semantics of restrict? 

       6.7.3.1  Formal definition of restrict

       [#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).

I believe this much is straightforward.

       [#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.117)   Note  that
       ``based'' is  defined  only  for  expressions  with  pointer
       types.

Although things may not be clear in some cases where the representation of 
pointers is inspected bitwise, in plausibly optimizable cases I think the 
meaning of "based on" is OK.

       [#4]  During  each  execution of B, let L be any lvalue that
       has &L based on P.  If L is used to access the value of  the
       object  X that it designates, and X is also modified (by any
       means), then the following requirements apply: T  shall  not
       be  const-qualified.   Every other lvalue used to access the
       value of X shall also have its address based  on  P.   Every

So if something is accessed through a restricted pointer, and it is 
modified, all accesses are based on that pointer: all pointer dereferences 
not based on that pointer are independent of accesses to that which is 
modified.  (It is still valid to have two restricted pointers to the same 
array of char, one used to modify the odd numbered bytes and one to modify 
the even numbered bytes: but a byte accessed through one pointer and 
modified can't be accessed through any pointer not based on the restricted 
pointer, whether or not that other pointer is restricted.)

       access that modifies X shall be considered also to modify P,
       for the purposes of this subclause.  If P  is  assigned  the

For example, given

int *restrict *restrict p;
int *restrict *restrict q;

with **p modified, *p is deemed modified, so even if q == p you can't then 
modify **q as an alias to **p that goes through the same restricted 
pointer object *p.  But given

int *restrict *p;
int *restrict *q;

(without the second level of "restrict") it is possible that p == q and so 
you can modify both **p and **q, as both those expressions involve the 
same restricted pointer object *p (where &*p == &*q == p == q).

       value  of  a  pointer  expression E that is based on another
       restricted pointer object P2, associated with block B2, then
       either  the execution of B2 shall begin before the execution
       of B, or  the  execution  of  B2  shall  end  prior  to  the
       assignment.   If  these  requirements  are not met, then the
       behavior is undefined.

The aliasing information provided by "restrict" only applies during the 
execution of the block which contains the declaration providing the 
"restrict" information.  It is possible to copy the restricted pointer to 
an outside non-restricted pointer, and once the block has finished 
executing that pointer might freely alias; so that outside pointer, of 
similar type but lacking "restrict", can't be treated as completely 
interchangable with the inner pointer although it may have the same value.  

The restrictions on assignment between restricted pointers reduce the 
possible ways in which one restricted pointer might dynamically become 
based on another, but I'm not sure exactly what optimizations this is 
intended to facilitate.  As optimizations don't respect block boundaries, 
both the fact that "restrict" only provides aliasing information during 
its block's execution and the possibility of restricted pointers becoming 
based on other restricted pointers are things to bear in mind.

       [#5] Here an execution  of  B  means  that  portion  of  the
       execution  of  the  program  that  would  correspond  to the
       lifetime of an object with scalar type and automatic storage
       duration associated with B.

       [#6]  A  translator  is  free  to ignore any or all aliasing
       implications of uses of restrict.



-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14192

[Bug middle-end/14192] Restrict pointers don't help

[ian at airs dot com]

------- Additional Comments From ian at airs dot com  2005-09-28 05:21 -------
We are not waiting for anything in this bug, as far as I can tell.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ian at airs dot com
             Status|WAITING                     |NEW
   Last reconfirmed|0000-00-00 00:00:00         |2005-09-28 05:21:37
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14192

[Bug middle-end/14192] Restrict pointers don't help

[colanderman at gmail dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14192

Chris King <colanderman at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |colanderman at gmail dot com

--- Comment #14 from Chris King <colanderman at gmail dot com> ---
> Only two_restrict_pointers is valid.

> Sorry, but I still don't get it

I agree.  None of the above responses clearly explain why one_restrict_pointer
does not represent a valid bug.  The missed optimization still exists in 4.8.0.

[Bug middle-end/14192] Restrict pointers don't help

[alexey dot salmin at gmail dot com]

------- Comment #13 from alexey dot salmin at gmail dot com  2010-04-28 15:53 -------
Sorry, but I still don't get it :( Why exactly we can't remove the second load
of "*b"?

void f(int *a, const int *restrict b) {
        *a++ = *b + 1;
        *a++ = *b + 1;
}


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14192

[Bug middle-end/14192] Restrict pointers don't help

[pinskia at gcc dot gnu dot org]

------- Comment #12 from pinskia at gcc dot gnu dot org  2010-04-27 18:08 -------
*** Bug 43907 has been marked as a duplicate of this bug. ***


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |alexey dot salmin at gmail
                   |                            |dot com


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14192

[Bug middle-end/14192] Restrict pointers don't help

[rguenth at gcc dot gnu dot org]

------- Comment #11 from rguenth at gcc dot gnu dot org  2008-10-01 14:28 -------
Only two_restrict_pointers is valid.  This is a dup of PR14187.

*** This bug has been marked as a duplicate of 14187 ***


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |DUPLICATE


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14192

[Bug middle-end/14192] Restrict pointers don't help

[pinskia at gcc dot gnu dot org]

------- Comment #10 from pinskia at gcc dot gnu dot org  2007-06-11 00:34 -------
> The second case is the following loop:

This is just caused by how we represent pointer addition.  I have a fix for
that one, we now get the correct aliasing sets for it.


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |alias


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14192