A question about using restrict

A question about using restrict

[Revital1 Eres]

Hello,

I have the loop below and I want to pass to gcc that src1 and src2 never
alias with dst; so I used the restrict keyword as below; however I still
see that there are dependence edges between dst and src1 and src2 in
the DDG created by SMS and I wonder how can I resolve this.
(I used GCC -v167637 and compiled for powerpc)

Thanks,
Revital

Original version:

void foo(unsigned char  ***dst,
    unsigned char *src1,
    unsigned char  *src2, int row)
{
    int x;

    for( x = 0; x < 100; x+=1)
      {
        dst[0][row][x] = ( src1[x] * src2[x]);
      }
}

version 1 with restrict:

void foo(unsigned char  ***__restrict__ dst,
    unsigned char *__restrict__ src1,
    unsigned char  *__restrict__ src2, int row)
{
    int x;

    for( x = 0; x < 100; x+=1)
      {
        dst[0][row][x] = ( src1[x] * src2[x]);
      }
}

version 2 with restrict:

void
foo(unsigned char  *** __restrict__ dst,
    unsigned char * __restrict__ src1,
    unsigned char  * __restrict__ src2, int row)
{
    int x;
    unsigned char  **__restrict__ dst1 = dst[0];
    unsigned char  * __restrict__ dst2 = dst1[row];

    for( x = 0; x < 100; x+=1)
      {
        dst2[x] = (src1[x] * src2[x]);
      }
}

RE: A question about using restrict

[Bingfeng Mei]

Hi, Revital,
Sorry for late reply. I think you can write following code
according to C99 standard to make sure src1/src2 don't alias
with dst. However, current GCC support for restrict is still
quite weak. The restrict info tends to be lost in all optimizations,
especially ivopts. You won't get the intended result. I have some
internal patch for 4.5 to track the source of a pointer.
It is not a very efficient implementation but works for us so far.
I can send to you if you are interested.

void
foo(unsigned char  *** dst,
    unsigned char * __restrict__ src1,
    unsigned char  * __restrict__ src2, int row)
{
    int x;
    unsigned char  * __restrict__ dst2 = dst[0][row];

    for( x = 0; x < 100; x+=1)
      {
        dst2[x] = (src1[x] * src2[x]);
      }
}

Cheers,
Bingfeng

> -----Original Message-----
> From: Revital1 Eres [mailto:ERES@il.ibm.com]
> Sent: 13 December 2010 07:59
> To: gcc@gcc.gnu.org
> Cc: Bingfeng Mei
> Subject: A question about using restrict
> 
> 
> Hello,
> 
> I have the loop below and I want to pass to gcc that src1 and src2
> never
> alias with dst; so I used the restrict keyword as below; however I
> still
> see that there are dependence edges between dst and src1 and src2 in
> the DDG created by SMS and I wonder how can I resolve this.
> (I used GCC -v167637 and compiled for powerpc)
> 
> Thanks,
> Revital
> 
> Original version:
> 
> void foo(unsigned char  ***dst,
>     unsigned char *src1,
>     unsigned char  *src2, int row)
> {
>     int x;
> 
>     for( x = 0; x < 100; x+=1)
>       {
>         dst[0][row][x] = ( src1[x] * src2[x]);
>       }
> }
> 
> version 1 with restrict:
> 
> void foo(unsigned char  ***__restrict__ dst,
>     unsigned char *__restrict__ src1,
>     unsigned char  *__restrict__ src2, int row)
> {
>     int x;
> 
>     for( x = 0; x < 100; x+=1)
>       {
>         dst[0][row][x] = ( src1[x] * src2[x]);
>       }
> }
> 
> version 2 with restrict:
> 
> void
> foo(unsigned char  *** __restrict__ dst,
>     unsigned char * __restrict__ src1,
>     unsigned char  * __restrict__ src2, int row)
> {
>     int x;
>     unsigned char  **__restrict__ dst1 = dst[0];
>     unsigned char  * __restrict__ dst2 = dst1[row];
> 
>     for( x = 0; x < 100; x+=1)
>       {
>         dst2[x] = (src1[x] * src2[x]);
>       }
> }
> 
> 

RE: A question about using restrict

[Revital1 Eres]

Hello Bingfeng,

Thanks for your reply! I would be very interested to try your patch.

Revital




From:	"Bingfeng Mei" <bmei@broadcom.com>
To:	Revital1 Eres/Haifa/IBM@IBMIL, "gcc@gcc.gnu.org"
            <gcc@gcc.gnu.org>
Date:	13/12/2010 12:20 PM
Subject:	RE: A question about using restrict



Hi, Revital,
Sorry for late reply. I think you can write following code
according to C99 standard to make sure src1/src2 don't alias
with dst. However, current GCC support for restrict is still
quite weak. The restrict info tends to be lost in all optimizations,
especially ivopts. You won't get the intended result. I have some
internal patch for 4.5 to track the source of a pointer.
It is not a very efficient implementation but works for us so far.
I can send to you if you are interested.

void
foo(unsigned char  *** dst,
    unsigned char * __restrict__ src1,
    unsigned char  * __restrict__ src2, int row)
{
    int x;
    unsigned char  * __restrict__ dst2 = dst[0][row];

    for( x = 0; x < 100; x+=1)
      {
        dst2[x] = (src1[x] * src2[x]);
      }
}

Cheers,
Bingfeng

> -----Original Message-----
> From: Revital1 Eres [mailto:ERES@il.ibm.com]
> Sent: 13 December 2010 07:59
> To: gcc@gcc.gnu.org
> Cc: Bingfeng Mei
> Subject: A question about using restrict
>
>
> Hello,
>
> I have the loop below and I want to pass to gcc that src1 and src2
> never
> alias with dst; so I used the restrict keyword as below; however I
> still
> see that there are dependence edges between dst and src1 and src2 in
> the DDG created by SMS and I wonder how can I resolve this.
> (I used GCC -v167637 and compiled for powerpc)
>
> Thanks,
> Revital
>
> Original version:
>
> void foo(unsigned char  ***dst,
>     unsigned char *src1,
>     unsigned char  *src2, int row)
> {
>     int x;
>
>     for( x = 0; x < 100; x+=1)
>       {
>         dst[0][row][x] = ( src1[x] * src2[x]);
>       }
> }
>
> version 1 with restrict:
>
> void foo(unsigned char  ***__restrict__ dst,
>     unsigned char *__restrict__ src1,
>     unsigned char  *__restrict__ src2, int row)
> {
>     int x;
>
>     for( x = 0; x < 100; x+=1)
>       {
>         dst[0][row][x] = ( src1[x] * src2[x]);
>       }
> }
>
> version 2 with restrict:
>
> void
> foo(unsigned char  *** __restrict__ dst,
>     unsigned char * __restrict__ src1,
>     unsigned char  * __restrict__ src2, int row)
> {
>     int x;
>     unsigned char  **__restrict__ dst1 = dst[0];
>     unsigned char  * __restrict__ dst2 = dst1[row];
>
>     for( x = 0; x < 100; x+=1)
>       {
>         dst2[x] = (src1[x] * src2[x]);
>       }
> }
>
>

RE: A question about using restrict

[Bingfeng Mei]

[-- Attachment #1: Type: text/plain, Size: 3336 bytes --]

Please find the attached patch. The second patch is from our target.c. 
You may put the functions at where you want to insert so that alias.c
can access them.

Cheers,
Bingfeng



> -----Original Message-----
> From: Revital1 Eres [mailto:ERES@il.ibm.com]
> Sent: 13 December 2010 10:37
> To: Bingfeng Mei
> Cc: gcc@gcc.gnu.org
> Subject: RE: A question about using restrict
> 
> Hello Bingfeng,
> 
> Thanks for your reply! I would be very interested to try your patch.
> 
> Revital
> 
> 
> 
> 
> From:	"Bingfeng Mei" <bmei@broadcom.com>
> To:	Revital1 Eres/Haifa/IBM@IBMIL, "gcc@gcc.gnu.org"
>             <gcc@gcc.gnu.org>
> Date:	13/12/2010 12:20 PM
> Subject:	RE: A question about using restrict
> 
> 
> 
> Hi, Revital,
> Sorry for late reply. I think you can write following code
> according to C99 standard to make sure src1/src2 don't alias
> with dst. However, current GCC support for restrict is still
> quite weak. The restrict info tends to be lost in all optimizations,
> especially ivopts. You won't get the intended result. I have some
> internal patch for 4.5 to track the source of a pointer.
> It is not a very efficient implementation but works for us so far.
> I can send to you if you are interested.
> 
> void
> foo(unsigned char  *** dst,
>     unsigned char * __restrict__ src1,
>     unsigned char  * __restrict__ src2, int row)
> {
>     int x;
>     unsigned char  * __restrict__ dst2 = dst[0][row];
> 
>     for( x = 0; x < 100; x+=1)
>       {
>         dst2[x] = (src1[x] * src2[x]);
>       }
> }
> 
> Cheers,
> Bingfeng
> 
> > -----Original Message-----
> > From: Revital1 Eres [mailto:ERES@il.ibm.com]
> > Sent: 13 December 2010 07:59
> > To: gcc@gcc.gnu.org
> > Cc: Bingfeng Mei
> > Subject: A question about using restrict
> >
> >
> > Hello,
> >
> > I have the loop below and I want to pass to gcc that src1 and src2
> > never
> > alias with dst; so I used the restrict keyword as below; however I
> > still
> > see that there are dependence edges between dst and src1 and src2 in
> > the DDG created by SMS and I wonder how can I resolve this.
> > (I used GCC -v167637 and compiled for powerpc)
> >
> > Thanks,
> > Revital
> >
> > Original version:
> >
> > void foo(unsigned char  ***dst,
> >     unsigned char *src1,
> >     unsigned char  *src2, int row)
> > {
> >     int x;
> >
> >     for( x = 0; x < 100; x+=1)
> >       {
> >         dst[0][row][x] = ( src1[x] * src2[x]);
> >       }
> > }
> >
> > version 1 with restrict:
> >
> > void foo(unsigned char  ***__restrict__ dst,
> >     unsigned char *__restrict__ src1,
> >     unsigned char  *__restrict__ src2, int row)
> > {
> >     int x;
> >
> >     for( x = 0; x < 100; x+=1)
> >       {
> >         dst[0][row][x] = ( src1[x] * src2[x]);
> >       }
> > }
> >
> > version 2 with restrict:
> >
> > void
> > foo(unsigned char  *** __restrict__ dst,
> >     unsigned char * __restrict__ src1,
> >     unsigned char  * __restrict__ src2, int row)
> > {
> >     int x;
> >     unsigned char  **__restrict__ dst1 = dst[0];
> >     unsigned char  * __restrict__ dst2 = dst1[row];
> >
> >     for( x = 0; x < 100; x+=1)
> >       {
> >         dst2[x] = (src1[x] * src2[x]);
> >       }
> > }
> >
> >
> 
> 
> 
> 


[-- Attachment #2: alias_c_patch --]
[-- Type: application/octet-stream, Size: 1256 bytes --]

Index: alias.c
===================================================================
RCS file: /cvs/dev/tools/src/fp_gcc/gcc/alias.c,v
retrieving revision 1.29.2.12
retrieving revision 1.29.2.14
diff -u -r1.29.2.12 -r1.29.2.14
--- alias.c	29 Nov 2010 15:24:04 -0000	1.29.2.12
+++ alias.c	30 Nov 2010 11:22:01 -0000	1.29.2.14
@@ -629,8 +629,9 @@
 /*BRCM: Goes back to find whether the memory access is restrict qualified 
         currently only handle INDIRECT_REF and TARGET_MEM_REF */
 #ifdef TARGET_FIREPATH
-      if (TREE_CODE (t) == INDIRECT_REF 
-         || TREE_CODE (t) == TARGET_MEM_REF)
+      if (currently_expanding_to_rtl
+          && (TREE_CODE (t) == INDIRECT_REF 
+            || TREE_CODE (t) == TARGET_MEM_REF))
         { 
           set = firepath_find_restrict_set (t);
           if (set != -1)
@@ -2630,6 +2631,14 @@
   x_addr = canon_rtx (x_addr);
   mem_addr = canon_rtx (mem_addr);
 
+/*BRCM: FIXME: Richard Guenther mentioned that DIFFERENT_ALIS_SETS_P
+ is not inter-iteration safe. But we need to that to make use of
+ alias set derived from restrict qualifier */
+#ifdef TARGET_FIREPATH
+  if (DIFFERENT_ALIAS_SETS_P (x, mem))
+    return 0;
+#endif    
+    
   if (nonoverlapping_memrefs_p (mem, x, true))
     return 0;
 

[-- Attachment #3: new_functions_patch --]
[-- Type: application/octet-stream, Size: 5765 bytes --]

Index: firepath.c
===================================================================
RCS file: /cvs/dev/tools/src/fp_gcc/gcc/config/firepath/firepath.c,v
retrieving revision 1.341.2.44
retrieving revision 1.341.2.46
diff -u -r1.341.2.44 -r1.341.2.46
--- firepath.c	23 Nov 2010 16:01:47 -0000	1.341.2.44
+++ firepath.c	29 Nov 2010 17:27:25 -0000	1.341.2.46
@@ -6852,3 +6852,171 @@
   
   return dummy.offset32;
 }
+
+/* Helper function that recursively search until succeed/fail to find
+  retrict qualified base pointer */
+static int firepath_find_restrict_set_1 (tree t)
+{
+  if (TREE_CODE (t) == SSA_NAME)
+  {
+    tree var = SSA_NAME_VAR (t);
+    gimple def_stmt;
+    /* If the var is not temporary variable and it is restrict qualified */
+    if (get_name (var) && !strchr (get_name (var), '.'))
+    {
+      int set = firepath_find_restrict_set_1 (var);
+      if (set != -1)
+        return set;
+    }
+    
+    /* Set this ssa_name as visited to prevent repeated visit */
+    if (TREE_VISITED (t))
+      return 0;
+    else
+      TREE_VISITED (t) = 1;
+    
+    /* Check def_stmt, only +/-/none is worth to search further 
+       Assume only the first operand is meaningful for restrict 
+       searching purpose */
+    def_stmt = SSA_NAME_DEF_STMT (t);
+    
+    /* If the gimple statement is PHI */
+    if (gimple_code (def_stmt) == GIMPLE_PHI)
+    {
+      unsigned i;
+      int prev_set = -1;
+      int set;
+      /* Search for all phi args */
+      for (i = 0; i < gimple_phi_num_args (def_stmt); i++)
+      {
+        struct phi_arg_d * phi_arg = gimple_phi_arg (def_stmt, i);
+        
+        set = firepath_find_restrict_set_1 (phi_arg->def);
+        
+        /* Just continue if we hit previously visited SSA_NAME */
+        if (set == 0)
+          continue;
+        /* If set of any phi_arg is unknown, return as unknown */  
+        else if (set == -1)
+          return set;
+        
+        /* If set of one phi_arg doesn't agree with another one 
+          return -1 */
+        if (prev_set == -1)
+          prev_set = set;
+        else if (prev_set != set)
+          return -1;    
+      }
+      
+      return prev_set;
+    }
+      
+    
+    /* e.g., GIMPLE_CALL */
+    if (!is_gimple_assign(def_stmt))
+      return -1;
+    
+    /* Only allow casting if only one operand */
+    if (gimple_num_ops (def_stmt) == 2)
+    {
+       if (gimple_assign_rhs_code (def_stmt) != NOP_EXPR
+          &&  gimple_assign_rhs_code (def_stmt) != CONVERT_EXPR)
+         return -1;
+       
+       /* Recurrsively search the only rhs operand */
+       return firepath_find_restrict_set_1 (gimple_assign_rhs1 (def_stmt));
+    }
+    /* Only allow plus/minus/pointer_plus in pointer calcuation
+       IVOPTS may convert pointer to normal variable, do some computation, then 
+       convert back to pointer */
+    else if (gimple_num_ops (def_stmt) == 3)
+    {
+       if (gimple_assign_rhs_code (def_stmt) != PLUS_EXPR
+          &&  gimple_assign_rhs_code (def_stmt) != MINUS_EXPR
+          &&  gimple_assign_rhs_code (def_stmt) != POINTER_PLUS_EXPR)
+         return -1;
+       
+       /* Only the first operand may come from pointer (Could be wrong )*/  
+       return firepath_find_restrict_set_1 (gimple_assign_rhs1 (def_stmt));
+    }
+    else
+      return -1;   
+    
+  }
+  else if (TREE_CODE (t) == VAR_DECL)
+  {
+    /* Temporary doesn't count  (no name or contain '.' ) */
+    if (!get_name (t) || strchr (get_name (t), '.'))
+      return -1;
+    /* Restrict-qualified non-temporary should get its own alias set */  
+    else if (TYPE_RESTRICT (TREE_TYPE (t)))
+    {
+      /* Either the decl_alias_set was created previously, or create a new one */
+      if (DECL_ALIAS_SET (t) == -1)
+        DECL_ALIAS_SET (t) = new_alias_set ();
+      
+      return DECL_ALIAS_SET (t);
+    }  
+    else
+      return -1;
+  }
+  /* Once we reach a parm_decl, this should be the end whether this
+    restirct qualified or not */
+  else if (TREE_CODE (t) == PARM_DECL)
+  {
+    if (TYPE_RESTRICT (TREE_TYPE (t)))
+    {
+      /* Either the decl_alias_set was created previously, or create a new one */
+      if (DECL_ALIAS_SET (t) == -1)
+        DECL_ALIAS_SET (t) = new_alias_set ();
+      
+      return DECL_ALIAS_SET (t);
+    }  
+    else
+      return -1;  
+  }
+  else
+    return -1;
+}
+
+/* Try to figure out alias set based on restrict pointer. The code in GCC 
+  is not good enough, often confused by temporary variables 
+  Main idea: 
+    1. Only handle INDIRECT_REF and TARGET_MEM_REF */
+int firepath_find_restrict_set (tree t)
+{
+  int i;
+  
+  gcc_assert (TREE_CODE (t) == INDIRECT_REF || TREE_CODE (t) == TARGET_MEM_REF);
+  
+  /* Clear all the visited flags, which are needed for PHI search */
+  for (i = 1; i < num_ssa_names; i++)
+  {
+    tree name = ssa_name (i);
+    if (name)
+      TREE_VISITED (name) = 0;
+  }
+          
+  if (TREE_CODE (t) == INDIRECT_REF)
+  {
+    /* Only the base address of TARGET_MEM_REF counts */
+    tree inner = TREE_OPERAND (t, 0);
+    return firepath_find_restrict_set_1 (inner);
+  }
+  else
+  {
+    /* Don't know how to handle symbol */
+    if (TREE_OPERAND (t, 0))
+      return -1;
+    /* Only base */  
+    if (TREE_OPERAND (t, 1) && !TREE_OPERAND (t, 2))
+      return firepath_find_restrict_set_1 (TREE_OPERAND (t, 1));
+    else if (TREE_OPERAND (t, 2) && !TREE_OPERAND (t, 3))
+      return firepath_find_restrict_set_1 (TREE_OPERAND (t, 2));
+    /* example: MEM[base: b_10(D), index: D.3497_24, step: 4]  */
+    else if (TREE_OPERAND (t, 1) && TREE_OPERAND (t, 2) && TREE_OPERAND (t, 3))
+      return firepath_find_restrict_set_1 (TREE_OPERAND (t, 1));
+    else
+      return -1;  
+  }
+}