[PATCH] Make SRA produce less useless statements

[Martin Jambor <mjambor at suse dot cz>]

Hi,

SRA currently creates a useless s1$i replacement for:

struct S
{
  int i;
  int j;
  char c[32]; /* this disables total scalarization in foo2 */
};

extern struct S bar(void);

int foo1 (int b)
{
   struct S s1;

   s1 = bar ();
   return s1.i;
}

The reason why we do our heristics this way is to make sure we
scalarize away s2 in:

extern struct S *g;

int foo2 (void)
{
   struct S s2;

   s2 = *g;
   return s2.i;
}

But we can do both if we differentiate between assignment and
non-assignment parent access writes exactly like we already do for
reads.  This patch avoids SRA in the first example while making sure
it still happens in the second one.

Bootstrapped and tested on x86_64-linux.  OK for trunk?

Thanks,

Martin


2010-10-06  Martin Jambor  <mjambor@suse.cz>

	* tree-sra.c (struct access): New field grp_assignment_write.
	(dump_access): Dump grp_assignment_write.
	(build_accesses_from_assign): Set grp_assignment_write.
	(sort_and_splice_var_accesses): Aggregate grp_assignment_write.
	(mark_read_status): Renamed to mark_rw_status, individual values
	renamed too.
	(analyze_access_subtree): Changed type of mark_write to
	mark_read_status.  Fixed propagating of mark_read and
	mark_write.  Changed benefit estimate.  Updated comment.

	* testsuite/gcc.dg/tree-ssa/sra-11.c: New test.

Index: mine/gcc/testsuite/gcc.dg/tree-ssa/sra-11.c
===================================================================
*** /dev/null
--- mine/gcc/testsuite/gcc.dg/tree-ssa/sra-11.c
***************
*** 0 ****
--- 1,33 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O1 -fdump-tree-esra-details" } */
+ 
+ struct S
+ {
+   int i;
+   int j;
+   char c[32]; /* this disables total scalarization */
+ };
+ 
+ extern struct S bar(void);
+ 
+ int foo1 (int b)
+ {
+    struct S s1;
+ 
+    s1 = bar ();
+    return s1.i;
+ }
+ 
+ extern struct S *g;
+ 
+ int foo2 (void)
+ {
+    struct S s2;
+ 
+    s2 = *g;
+    return s2.i;
+ }
+ 
+ /* { dg-final { scan-tree-dump-times "Created a replacement for s1" 0 "esra"} } */
+ /* { dg-final { scan-tree-dump-times "Created a replacement for s2" 1 "esra"} } */
+ /* { dg-final { cleanup-tree-dump "esra" } } */
Index: mine/gcc/tree-sra.c
===================================================================
*** mine.orig/gcc/tree-sra.c
--- mine/gcc/tree-sra.c
*************** struct access
*** 189,194 ****
--- 189,198 ----
       statement?  This flag is propagated down the access tree.  */
    unsigned grp_assignment_read : 1;
  
+   /* Does this group contain a write access that comes from an assignment
+      statement?  This flag is propagated down the access tree.  */
+   unsigned grp_assignment_write : 1;
+ 
    /* Other passes of the analysis use this bit to make function
       analyze_access_subtree create scalar replacements for this group if
       possible.  */
*************** dump_access (FILE *f, struct access *acc
*** 364,378 ****
    if (grp)
      fprintf (f, ", grp_write = %d, total_scalarization = %d, "
  	     "grp_read = %d, grp_hint = %d, grp_assignment_read = %d,"
! 	     "grp_covered = %d, grp_unscalarizable_region = %d, "
! 	     "grp_unscalarized_data = %d, grp_partial_lhs = %d, "
! 	     "grp_to_be_replaced = %d, grp_maybe_modified = %d, "
  	     "grp_not_necessarilly_dereferenced = %d\n",
  	     access->grp_write, access->total_scalarization,
  	     access->grp_read, access->grp_hint, access->grp_assignment_read,
! 	     access->grp_covered, access->grp_unscalarizable_region,
! 	     access->grp_unscalarized_data, access->grp_partial_lhs,
! 	     access->grp_to_be_replaced, access->grp_maybe_modified,
  	     access->grp_not_necessarilly_dereferenced);
    else
      fprintf (f, ", write = %d, total_scalarization = %d, "
--- 368,384 ----
    if (grp)
      fprintf (f, ", grp_write = %d, total_scalarization = %d, "
  	     "grp_read = %d, grp_hint = %d, grp_assignment_read = %d,"
! 	     "grp_assignment_write = %d, grp_covered = %d, "
! 	     "grp_unscalarizable_region = %d, grp_unscalarized_data = %d, "
! 	     "grp_partial_lhs = %d, grp_to_be_replaced = %d, "
! 	     "grp_maybe_modified = %d, "
  	     "grp_not_necessarilly_dereferenced = %d\n",
  	     access->grp_write, access->total_scalarization,
  	     access->grp_read, access->grp_hint, access->grp_assignment_read,
! 	     access->grp_assignment_write, access->grp_covered,
! 	     access->grp_unscalarizable_region, access->grp_unscalarized_data,
! 	     access->grp_partial_lhs, access->grp_to_be_replaced,
! 	     access->grp_maybe_modified,
  	     access->grp_not_necessarilly_dereferenced);
    else
      fprintf (f, ", write = %d, total_scalarization = %d, "
*************** build_accesses_from_assign (gimple stmt)
*** 1019,1024 ****
--- 1025,1033 ----
    racc = build_access_from_expr_1 (rhs, stmt, false);
    lacc = build_access_from_expr_1 (lhs, stmt, true);
  
+   if (lacc)
+     lacc->grp_assignment_write = 1;
+ 
    if (racc)
      {
        racc->grp_assignment_read = 1;
*************** sort_and_splice_var_accesses (tree var)
*** 1581,1586 ****
--- 1590,1596 ----
        bool grp_write = access->write;
        bool grp_read = !access->write;
        bool grp_assignment_read = access->grp_assignment_read;
+       bool grp_assignment_write = access->grp_assignment_write;
        bool multiple_reads = false;
        bool total_scalarization = access->total_scalarization;
        bool grp_partial_lhs = access->grp_partial_lhs;
*************** sort_and_splice_var_accesses (tree var)
*** 1615,1620 ****
--- 1625,1631 ----
  		grp_read = true;
  	    }
  	  grp_assignment_read |= ac2->grp_assignment_read;
+ 	  grp_assignment_write |= ac2->grp_assignment_write;
  	  grp_partial_lhs |= ac2->grp_partial_lhs;
  	  unscalarizable_region |= ac2->grp_unscalarizable_region;
  	  total_scalarization |= ac2->total_scalarization;
*************** sort_and_splice_var_accesses (tree var)
*** 1634,1639 ****
--- 1645,1651 ----
        access->grp_write = grp_write;
        access->grp_read = grp_read;
        access->grp_assignment_read = grp_assignment_read;
+       access->grp_assignment_write = grp_assignment_write;
        access->grp_hint = multiple_reads || total_scalarization;
        access->grp_partial_lhs = grp_partial_lhs;
        access->grp_unscalarizable_region = unscalarizable_region;
*************** expr_with_var_bounded_array_refs_p (tree
*** 1822,1838 ****
    return false;
  }
  
! enum mark_read_status { SRA_MR_NOT_READ, SRA_MR_READ, SRA_MR_ASSIGN_READ};
  
  /* Analyze the subtree of accesses rooted in ROOT, scheduling replacements when
     both seeming beneficial and when ALLOW_REPLACEMENTS allows it.  Also set all
     sorts of access flags appropriately along the way, notably always set
     grp_read and grp_assign_read according to MARK_READ and grp_write when
!    MARK_WRITE is true.  */
  
  static bool
  analyze_access_subtree (struct access *root, bool allow_replacements,
! 			enum mark_read_status mark_read, bool mark_write)
  {
    struct access *child;
    HOST_WIDE_INT limit = root->offset + root->size;
--- 1834,1883 ----
    return false;
  }
  
! enum mark_rw_status { SRA_MRRW_NOTHING, SRA_MRRW_DIRECT, SRA_MRRW_ASSIGN};
  
  /* Analyze the subtree of accesses rooted in ROOT, scheduling replacements when
     both seeming beneficial and when ALLOW_REPLACEMENTS allows it.  Also set all
     sorts of access flags appropriately along the way, notably always set
     grp_read and grp_assign_read according to MARK_READ and grp_write when
!    MARK_WRITE is true.
! 
!    Creating a replacement for a scalar access is considered beneficial if its
!    grp_hint is set (this means we are either attempting total scalarization or
!    there is more than one direct read access) or according to the following
!    table:
! 
!    Access written to individually (once or more times)
!    |
!    |	Parent written to in an assignment statement
!    |	|
!    |	|	Access read individually _once_
!    |	|	|
!    |   	|	|	Parent read in an assignment statement
!    |	|	|	|
!    |   	|	|	|	Scalarize	Comment
! -----------------------------------------------------------------------------
!    0	0	0	0			No access for the scalar
!    0	0	0	1			No access for the scalar
!    0	0	1	0	No		Single read - won't help
!    0	0	1	1	No		The same case
!    0	1	0	0			No access for the scalar
!    0	1	0	1			No access for the scalar
!    0	1	1	0	Yes		s = *g; return s.i;
!    0	1	1	1       Yes		The same case as above
!    1	0	0	0	No		Won't help
!    1	0	0	1	Yes		s.i = 1; *g = s;
!    1	0	1	0	Yes		s.i = 5; g = s.i;
!    1	0	1	1	Yes		The same case as above
!    1	1	0	0	No		Won't help.
!    1	1	0	1	Yes		s.i = 1; *g = s;
!    1	1	1	0	Yes		s = *g; return s.i;
!    1	1	1	1	Yes		Any of the above yeses  */
  
  static bool
  analyze_access_subtree (struct access *root, bool allow_replacements,
! 			enum mark_rw_status mark_read,
! 			enum mark_rw_status mark_write)
  {
    struct access *child;
    HOST_WIDE_INT limit = root->offset + root->size;
*************** analyze_access_subtree (struct access *r
*** 1840,1862 ****
    bool scalar = is_gimple_reg_type (root->type);
    bool hole = false, sth_created = false;
    bool direct_read = root->grp_read;
  
!   if (mark_read == SRA_MR_ASSIGN_READ)
      {
        root->grp_read = 1;
        root->grp_assignment_read = 1;
      }
!   if (mark_read == SRA_MR_READ)
      root->grp_read = 1;
-   else if (root->grp_assignment_read)
-     mark_read = SRA_MR_ASSIGN_READ;
    else if (root->grp_read)
!     mark_read = SRA_MR_READ;
  
!   if (mark_write)
!     root->grp_write = true;
    else if (root->grp_write)
!     mark_write = true;
  
    if (root->grp_unscalarizable_region)
      allow_replacements = false;
--- 1885,1915 ----
    bool scalar = is_gimple_reg_type (root->type);
    bool hole = false, sth_created = false;
    bool direct_read = root->grp_read;
+   bool direct_write = root->grp_write;
  
!   if (root->grp_assignment_read)
!     mark_read = SRA_MRRW_ASSIGN;
!   else if (mark_read == SRA_MRRW_ASSIGN)
      {
        root->grp_read = 1;
        root->grp_assignment_read = 1;
      }
!   else if (mark_read == SRA_MRRW_DIRECT)
      root->grp_read = 1;
    else if (root->grp_read)
!     mark_read = SRA_MRRW_DIRECT;
  
!   if (root->grp_assignment_write)
!     mark_write = SRA_MRRW_ASSIGN;
!   else if (mark_write == SRA_MRRW_ASSIGN)
!     {
!       root->grp_write = 1;
!       root->grp_assignment_write = 1;
!     }
!   else if (mark_write == SRA_MRRW_DIRECT)
!     root->grp_write = 1;
    else if (root->grp_write)
!     mark_write = SRA_MRRW_DIRECT;
  
    if (root->grp_unscalarizable_region)
      allow_replacements = false;
*************** analyze_access_subtree (struct access *r
*** 1881,1887 ****
  
    if (allow_replacements && scalar && !root->first_child
        && (root->grp_hint
! 	  || (root->grp_write && (direct_read || root->grp_assignment_read))))
      {
        if (dump_file && (dump_flags & TDF_DETAILS))
  	{
--- 1934,1941 ----
  
    if (allow_replacements && scalar && !root->first_child
        && (root->grp_hint
! 	  || ((direct_write || root->grp_assignment_write)
! 	      && (direct_read || root->grp_assignment_read))))
      {
        if (dump_file && (dump_flags & TDF_DETAILS))
  	{
*************** analyze_access_trees (struct access *acc
*** 1920,1926 ****
  
    while (access)
      {
!       if (analyze_access_subtree (access, true, SRA_MR_NOT_READ, false))
  	ret = true;
        access = access->next_grp;
      }
--- 1974,1981 ----
  
    while (access)
      {
!       if (analyze_access_subtree (access, true,
! 				  SRA_MRRW_NOTHING, SRA_MRRW_NOTHING))
  	ret = true;
        access = access->next_grp;
      }