[PATCH] Limit VDEF walking in IPA-SRA when looking for potential modifications

[Martin Jambor-3]

Hi,

the patch below limits walking of VDEFs when searching for potential
modifications of what a parameter points to by providing a common
bitmap to various invocations of walk_aliased_vdefs which look for
alias vdefs of the same thing.

This is not a regression fix but may avoid some unnecessary costly
walks and the scope of the patch is small.  Therefore I'm still
proposing to commit this to trunk.  I have bootstrapped and tested the
patch on x86_64-linux with "yes" and "release" checking (both with
Ada).

What do you think?

Martin


2009-11-02  Martin Jambor  <mjambor@...>

        * tree-sra.c (analyze_modified_params): Pass a common bitmap to
        walk_aliased_vdefs.


Index: mine/gcc/tree-sra.c
===================================================================
--- mine.orig/gcc/tree-sra.c
+++ mine/gcc/tree-sra.c
@@ -2825,6 +2825,7 @@ analyze_modified_params (VEC (access_p,
    repr = repr->next_grp)
  {
   VEC (access_p, heap) *access_vec;
+  bitmap visited;
   int j, access_count;
   tree parm;
 
@@ -2835,6 +2836,7 @@ analyze_modified_params (VEC (access_p,
       || repr->grp_maybe_modified)
     continue;
 
+  visited = BITMAP_ALLOC (NULL);
   access_vec = get_base_access_vector (parm);
   access_count = VEC_length (access_p, access_vec);
   for (j = 0; j < access_count; j++)
@@ -2847,10 +2849,11 @@ analyze_modified_params (VEC (access_p,
       access = VEC_index (access_p, access_vec, j);
       ao_ref_init (&ar, access->expr);
       walk_aliased_vdefs (&ar, gimple_vuse (access->stmt),
-  mark_maybe_modified, repr, NULL);
+  mark_maybe_modified, repr, &visited);
       if (repr->grp_maybe_modified)
  break;
     }
+  BITMAP_FREE (visited);
  }
     }
 }

[Richard Guenther-3]

On Mon, 2 Nov 2009, Martin Jambor wrote:

> Hi,
>
> the patch below limits walking of VDEFs when searching for potential
> modifications of what a parameter points to by providing a common
> bitmap to various invocations of walk_aliased_vdefs which look for
> alias vdefs of the same thing.
>
> This is not a regression fix but may avoid some unnecessary costly
> walks and the scope of the patch is small.  Therefore I'm still
> proposing to commit this to trunk.  I have bootstrapped and tested the
> patch on x86_64-linux with "yes" and "release" checking (both with
> Ada).
>
> What do you think?

I wonder if it is correct.  How do the parm representatives
relate to the access expressions?  Thus, I would have expected
that ao_ref_init be moved outside of the inner loop and initialized
from repr->base.

If written as your patch then for example in

struct X { int i; float f; } *q;
double *x;
float foo (struct X *p)
{
  q->f = 1;
  *x = 0;
  return p->i + p->f;
}

if you start walking from the access p->i you visit both stores
and do not find an alias but mark both stmts as visited.  Then
you start walking from p->f and stop at *x because you have already
visited it.  And you do not see that q->f may possibly an alias
and grp_maybe_modified stays not set.

Thus, using the bitmap is only valid if you re-use it with the
same ao_ref or if you really really know what you are doing.

Richard.

> Martin
>
>
> 2009-11-02  Martin Jambor  <mjambor@...>
>
> * tree-sra.c (analyze_modified_params): Pass a common bitmap to
> walk_aliased_vdefs.
>
>
> Index: mine/gcc/tree-sra.c
> ===================================================================
> --- mine.orig/gcc/tree-sra.c
> +++ mine/gcc/tree-sra.c
> @@ -2825,6 +2825,7 @@ analyze_modified_params (VEC (access_p,
>     repr = repr->next_grp)
>   {
>    VEC (access_p, heap) *access_vec;
> +  bitmap visited;
>    int j, access_count;
>    tree parm;
>  
> @@ -2835,6 +2836,7 @@ analyze_modified_params (VEC (access_p,
>        || repr->grp_maybe_modified)
>      continue;
>  
> +  visited = BITMAP_ALLOC (NULL);
>    access_vec = get_base_access_vector (parm);
>    access_count = VEC_length (access_p, access_vec);
>    for (j = 0; j < access_count; j++)
> @@ -2847,10 +2849,11 @@ analyze_modified_params (VEC (access_p,
>        access = VEC_index (access_p, access_vec, j);
>        ao_ref_init (&ar, access->expr);
>        walk_aliased_vdefs (&ar, gimple_vuse (access->stmt),
> -  mark_maybe_modified, repr, NULL);
> +  mark_maybe_modified, repr, &visited);
>        if (repr->grp_maybe_modified)
>   break;
>      }
> +  BITMAP_FREE (visited);
>   }
>      }
>  }
>
>

--
Richard Guenther <rguenther@...>
Novell / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746 - GF: Markus Rex

[Martin Jambor-3]

Hi,

On Tue, Nov 03, 2009 at 11:03:01AM +0100, Richard Guenther wrote:

> On Mon, 2 Nov 2009, Martin Jambor wrote:
>
> > Hi,
> >
> > the patch below limits walking of VDEFs when searching for potential
> > modifications of what a parameter points to by providing a common
> > bitmap to various invocations of walk_aliased_vdefs which look for
> > alias vdefs of the same thing...
>
> I wonder if it is correct.

It is not.  Unfortunately I suffer a weird form of blindness whenever
I look at this function and see what I want to see rather than what is
actually there.  The function, as it is now, is bogus, albeit in a
conservative way and so does not cause trouble.

I intended to loop over accesses of a group and analyze them for
potential modifications together, instead the loop is now over all
accesses of the same base.  In order to change this, I have built a
linked list of group members, overloading the next_sibling access
field which is not used in IPA-SRA.  I also moved ao_ref_init outside
the inner loop.

I have successfully bootstrapped and tested a very similiar patch, I
am bootstrapping and testing this exact version now.  OK if it passes?

Thanks,

Martin


2009-11-04  Martin Jambor  <mjambor@...>

        * tree-sra.c (struct access): Changed comment of next_sibling field.
        (analyze_modified_params): Loop over accesses of a group rather than
        over all with the ame base, pass a common bitmap to
        walk_aliased_vdefs.
        (unmodified_by_ref_scalar_representative): Build link lists of
        accesses of a group.
        (splice_param_accesses): Likewise.


Index: mine/gcc/tree-sra.c
===================================================================
*** mine.orig/gcc/tree-sra.c
--- mine/gcc/tree-sra.c
*************** struct access
*** 144,150 ****
       points to the first one.  */
    struct access *first_child;
 
!   /* Pointer to the next sibling in the access tree as described above.  */
    struct access *next_sibling;
 
    /* Pointers to the first and last element in the linked list of assign
--- 144,152 ----
       points to the first one.  */
    struct access *first_child;
 
!   /* In intraprocedural SRA, pointer to the next sibling in the access tree as
!      described above.  In IPA-SRA this is a pointer to the next access
!      belonging to the same group (having the same representative).  */
    struct access *next_sibling;
 
    /* Pointers to the first and last element in the linked list of assign
*************** analyze_modified_params (VEC (access_p,
*** 2824,2856 ****
    repr;
    repr = repr->next_grp)
  {
!  VEC (access_p, heap) *access_vec;
!  int j, access_count;
!  tree parm;
 
   if (no_accesses_p (repr))
     continue;
!  parm = repr->base;
!  if (!POINTER_TYPE_P (TREE_TYPE (parm))
       || repr->grp_maybe_modified)
     continue;
 
!  access_vec = get_base_access_vector (parm);
!  access_count = VEC_length (access_p, access_vec);
!  for (j = 0; j < access_count; j++)
     {
-      struct access *access;
-      ao_ref ar;
-
       /* All accesses are read ones, otherwise grp_maybe_modified would
  be trivially set.  */
-      access = VEC_index (access_p, access_vec, j);
-      ao_ref_init (&ar, access->expr);
       walk_aliased_vdefs (&ar, gimple_vuse (access->stmt),
!  mark_maybe_modified, repr, NULL);
       if (repr->grp_maybe_modified)
  break;
     }
  }
      }
  }
--- 2826,2853 ----
    repr;
    repr = repr->next_grp)
  {
!  struct access *access;
!  bitmap visited;
!  ao_ref ar;
 
   if (no_accesses_p (repr))
     continue;
!  if (!POINTER_TYPE_P (TREE_TYPE (repr->base))
       || repr->grp_maybe_modified)
     continue;
 
!  ao_ref_init (&ar, repr->expr);
!  visited = BITMAP_ALLOC (NULL);
!  for (access = repr; access; access = access->next_sibling)
     {
       /* All accesses are read ones, otherwise grp_maybe_modified would
  be trivially set.  */
       walk_aliased_vdefs (&ar, gimple_vuse (access->stmt),
!  mark_maybe_modified, repr, &visited);
       if (repr->grp_maybe_modified)
  break;
     }
+  BITMAP_FREE (visited);
  }
      }
  }
*************** static struct access *
*** 3019,3042 ****
  unmodified_by_ref_scalar_representative (tree parm)
  {
    int i, access_count;
!   struct access *access;
    VEC (access_p, heap) *access_vec;
 
    access_vec = get_base_access_vector (parm);
    gcc_assert (access_vec);
!   access_count = VEC_length (access_p, access_vec);
 
!   for (i = 0; i < access_count; i++)
      {
!       access = VEC_index (access_p, access_vec, i);
        if (access->write)
  return NULL;
      }
 
!   access = VEC_index (access_p, access_vec, 0);
!   access->grp_read = 1;
!   access->grp_scalar_ptr = 1;
!   return access;
  }
 
  /* Sort collected accesses for parameter PARM, identify representatives for
--- 3016,3045 ----
  unmodified_by_ref_scalar_representative (tree parm)
  {
    int i, access_count;
!   struct access *repr;
    VEC (access_p, heap) *access_vec;
 
    access_vec = get_base_access_vector (parm);
    gcc_assert (access_vec);
!   repr = VEC_index (access_p, access_vec, 0);
!   if (repr->write)
!     return NULL;
!   repr->group_representative = repr;
 
!   access_count = VEC_length (access_p, access_vec);
!   for (i = 1; i < access_count; i++)
      {
!       struct access *access = VEC_index (access_p, access_vec, i);
        if (access->write)
  return NULL;
+       access->group_representative = repr;
+       access->next_sibling = repr->next_sibling;
+       repr->next_sibling = access;
      }
 
!   repr->grp_read = 1;
!   repr->grp_scalar_ptr = 1;
!   return repr;
  }
 
  /* Sort collected accesses for parameter PARM, identify representatives for
*************** splice_param_accesses (tree parm, bool *
*** 3091,3096 ****
--- 3094,3102 ----
     return NULL;
 
   modification |= ac2->write;
+  ac2->group_representative = access;
+  ac2->next_sibling = access->next_sibling;
+  access->next_sibling = ac2;
   j++;
  }
 

[Richard Guenther-3]

On Wed, 4 Nov 2009, Martin Jambor wrote:

> Hi,
>
> On Tue, Nov 03, 2009 at 11:03:01AM +0100, Richard Guenther wrote:
> > On Mon, 2 Nov 2009, Martin Jambor wrote:
> >
> > > Hi,
> > >
> > > the patch below limits walking of VDEFs when searching for potential
> > > modifications of what a parameter points to by providing a common
> > > bitmap to various invocations of walk_aliased_vdefs which look for
> > > alias vdefs of the same thing...
> >
> > I wonder if it is correct.
>
> It is not.  Unfortunately I suffer a weird form of blindness whenever
> I look at this function and see what I want to see rather than what is
> actually there.  The function, as it is now, is bogus, albeit in a
> conservative way and so does not cause trouble.
>
> I intended to loop over accesses of a group and analyze them for
> potential modifications together, instead the loop is now over all
> accesses of the same base.  In order to change this, I have built a
> linked list of group members, overloading the next_sibling access
> field which is not used in IPA-SRA.  I also moved ao_ref_init outside
> the inner loop.
>
> I have successfully bootstrapped and tested a very similiar patch, I
> am bootstrapping and testing this exact version now.  OK if it passes?

Ok.

Thanks,
Richard.

> Thanks,
>
> Martin
>
>
> 2009-11-04  Martin Jambor  <mjambor@...>
>
> * tree-sra.c (struct access): Changed comment of next_sibling field.
> (analyze_modified_params): Loop over accesses of a group rather than
> over all with the ame base, pass a common bitmap to
> walk_aliased_vdefs.
> (unmodified_by_ref_scalar_representative): Build link lists of
> accesses of a group.
> (splice_param_accesses): Likewise.
>
>
> Index: mine/gcc/tree-sra.c
> ===================================================================
> *** mine.orig/gcc/tree-sra.c
> --- mine/gcc/tree-sra.c
> *************** struct access
> *** 144,150 ****
>        points to the first one.  */
>     struct access *first_child;
>  
> !   /* Pointer to the next sibling in the access tree as described above.  */
>     struct access *next_sibling;
>  
>     /* Pointers to the first and last element in the linked list of assign
> --- 144,152 ----
>        points to the first one.  */
>     struct access *first_child;
>  
> !   /* In intraprocedural SRA, pointer to the next sibling in the access tree as
> !      described above.  In IPA-SRA this is a pointer to the next access
> !      belonging to the same group (having the same representative).  */
>     struct access *next_sibling;
>  
>     /* Pointers to the first and last element in the linked list of assign
> *************** analyze_modified_params (VEC (access_p,
> *** 2824,2856 ****
>     repr;
>     repr = repr->next_grp)
>   {
> !  VEC (access_p, heap) *access_vec;
> !  int j, access_count;
> !  tree parm;
>  
>    if (no_accesses_p (repr))
>      continue;
> !  parm = repr->base;
> !  if (!POINTER_TYPE_P (TREE_TYPE (parm))
>        || repr->grp_maybe_modified)
>      continue;
>  
> !  access_vec = get_base_access_vector (parm);
> !  access_count = VEC_length (access_p, access_vec);
> !  for (j = 0; j < access_count; j++)
>      {
> -      struct access *access;
> -      ao_ref ar;
> -
>        /* All accesses are read ones, otherwise grp_maybe_modified would
>   be trivially set.  */
> -      access = VEC_index (access_p, access_vec, j);
> -      ao_ref_init (&ar, access->expr);
>        walk_aliased_vdefs (&ar, gimple_vuse (access->stmt),
> !  mark_maybe_modified, repr, NULL);
>        if (repr->grp_maybe_modified)
>   break;
>      }
>   }
>       }
>   }
> --- 2826,2853 ----
>     repr;
>     repr = repr->next_grp)
>   {
> !  struct access *access;
> !  bitmap visited;
> !  ao_ref ar;
>  
>    if (no_accesses_p (repr))
>      continue;
> !  if (!POINTER_TYPE_P (TREE_TYPE (repr->base))
>        || repr->grp_maybe_modified)
>      continue;
>  
> !  ao_ref_init (&ar, repr->expr);
> !  visited = BITMAP_ALLOC (NULL);
> !  for (access = repr; access; access = access->next_sibling)
>      {
>        /* All accesses are read ones, otherwise grp_maybe_modified would
>   be trivially set.  */
>        walk_aliased_vdefs (&ar, gimple_vuse (access->stmt),
> !  mark_maybe_modified, repr, &visited);
>        if (repr->grp_maybe_modified)
>   break;
>      }
> +  BITMAP_FREE (visited);
>   }
>       }
>   }
> *************** static struct access *
> *** 3019,3042 ****
>   unmodified_by_ref_scalar_representative (tree parm)
>   {
>     int i, access_count;
> !   struct access *access;
>     VEC (access_p, heap) *access_vec;
>  
>     access_vec = get_base_access_vector (parm);
>     gcc_assert (access_vec);
> !   access_count = VEC_length (access_p, access_vec);
>  
> !   for (i = 0; i < access_count; i++)
>       {
> !       access = VEC_index (access_p, access_vec, i);
>         if (access->write)
>   return NULL;
>       }
>  
> !   access = VEC_index (access_p, access_vec, 0);
> !   access->grp_read = 1;
> !   access->grp_scalar_ptr = 1;
> !   return access;
>   }
>  
>   /* Sort collected accesses for parameter PARM, identify representatives for
> --- 3016,3045 ----
>   unmodified_by_ref_scalar_representative (tree parm)
>   {
>     int i, access_count;
> !   struct access *repr;
>     VEC (access_p, heap) *access_vec;
>  
>     access_vec = get_base_access_vector (parm);
>     gcc_assert (access_vec);
> !   repr = VEC_index (access_p, access_vec, 0);
> !   if (repr->write)
> !     return NULL;
> !   repr->group_representative = repr;
>  
> !   access_count = VEC_length (access_p, access_vec);
> !   for (i = 1; i < access_count; i++)
>       {
> !       struct access *access = VEC_index (access_p, access_vec, i);
>         if (access->write)
>   return NULL;
> +       access->group_representative = repr;
> +       access->next_sibling = repr->next_sibling;
> +       repr->next_sibling = access;
>       }
>  
> !   repr->grp_read = 1;
> !   repr->grp_scalar_ptr = 1;
> !   return repr;
>   }
>  
>   /* Sort collected accesses for parameter PARM, identify representatives for
> *************** splice_param_accesses (tree parm, bool *
> *** 3091,3096 ****
> --- 3094,3102 ----
>      return NULL;
>  
>    modification |= ac2->write;
> +  ac2->group_representative = access;
> +  ac2->next_sibling = access->next_sibling;
> +  access->next_sibling = ac2;
>    j++;
>   }
>  
>
>

--
Richard Guenther <rguenther@...>
Novell / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746 - GF: Markus Rex