Re: [PATCH, PR 44258] Detect partially overlapping SRA accesses reliably

[Richard Guenther <rguenther at suse dot de>]

On Thu, 10 Jun 2010, Martin Jambor wrote:

> Hi,
> 
> this is an embarrassing bug.  I don't know what I was thinking when I
> wrote the code detecting partially overlapping accesses but just
> looking the neighboring accesses in the sorted vector clearly isn't
> enough and we must check for this property also when building the
> access tree.
> 
> Bootstrapped and tested on x86_64-linux, OK for trunk and for 4.5 as
> well, after a while?

Ok.

Thanks,
Richard.

> Thanks,
> 
> Martin
> 
> 
> 2010-06-10  Martin Jambor  <mjambor@suse.cz>
> 
> 	PR tree-optimization/44258
> 	* tree-sra.c (build_access_subtree): Return false iff there is a
> 	partial overlap.
> 	(build_access_trees): Likewise.
> 	(analyze_all_variable_accesses): Disqualify candidates if
> 	build_access_trees returns true for them.
> 
> 	* testsuite/gcc.dg/tree-ssa/pr44258.c: New test.
> 
> Index: mine/gcc/testsuite/gcc.dg/tree-ssa/pr44258.c
> ===================================================================
> --- /dev/null
> +++ mine/gcc/testsuite/gcc.dg/tree-ssa/pr44258.c
> @@ -0,0 +1,43 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-esra-details" } */
> +
> +struct blah
> +{
> +  char a[4];
> +};
> +
> +struct str
> +{
> +  struct blah b1;
> +  char x;
> +};
> +
> +struct val
> +{
> +  char y;
> +  struct blah b2;
> +};
> +
> +union U
> +{
> +  struct str str;
> +  struct val val;
> +};
> +
> +
> +extern struct blah e_b1, e_b2;
> +extern union U *e_u;
> +
> +int foo (int b)
> +{
> +  union U u;
> +
> +  u.str.b1 = e_b1;
> +  u.val.b2 = e_b2;
> +  u.str.b1.a[3] = 0;
> +
> +  *e_u = u;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "Created a replacement" 0 "esra"} } */
> +/* { dg-final { cleanup-tree-dump "esra" } } */
> Index: mine/gcc/tree-sra.c
> ===================================================================
> --- mine.orig/gcc/tree-sra.c
> +++ mine/gcc/tree-sra.c
> @@ -1689,9 +1689,10 @@ get_unrenamed_access_replacement (struct
>  
>  /* Build a subtree of accesses rooted in *ACCESS, and move the pointer in the
>     linked list along the way.  Stop when *ACCESS is NULL or the access pointed
> -   to it is not "within" the root.  */
> +   to it is not "within" the root.  Return false iff some accesses partially
> +   overlap.  */
>  
> -static void
> +static bool
>  build_access_subtree (struct access **access)
>  {
>    struct access *root = *access, *last_child = NULL;
> @@ -1706,24 +1707,32 @@ build_access_subtree (struct access **ac
>  	last_child->next_sibling = *access;
>        last_child = *access;
>  
> -      build_access_subtree (access);
> +      if (!build_access_subtree (access))
> +	return false;
>      }
> +
> +  if (*access && (*access)->offset < limit)
> +    return false;
> +
> +  return true;
>  }
>  
>  /* Build a tree of access representatives, ACCESS is the pointer to the first
> -   one, others are linked in a list by the next_grp field.  Decide about scalar
> -   replacements on the way, return true iff any are to be created.  */
> +   one, others are linked in a list by the next_grp field.  Return false iff
> +   some accesses partially overlap.  */
>  
> -static void
> +static bool
>  build_access_trees (struct access *access)
>  {
>    while (access)
>      {
>        struct access *root = access;
>  
> -      build_access_subtree (&access);
> +      if (!build_access_subtree (&access))
> +	return false;
>        root->next_grp = access;
>      }
> +  return true;
>  }
>  
>  /* Return true if expr contains some ARRAY_REFs into a variable bounded
> @@ -2062,9 +2071,7 @@ analyze_all_variable_accesses (void)
>        struct access *access;
>  
>        access = sort_and_splice_var_accesses (var);
> -      if (access)
> -	build_access_trees (access);
> -      else
> +      if (!access || !build_access_trees (access))
>  	disqualify_candidate (var,
>  			      "No or inhibitingly overlapping accesses.");
>      }
> 
> 

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