[PATCH] Copyprop through aggregates.

[Richard Guenther <rguenther at suse dot de>]

This patch enhances copyprop to see through store/load pairs to
aggregates by walking virtual use-def chains.  See
http://gcc.gnu.org/ml/gcc-patches/2006-01/msg01972.html
for SPEC results and numbers for extra copyprop opportunities
during a gcc bootstrap (though not including INDIRECT_REF bases
at that time due to the missing fix for get_ref_base_and_extent -
I can re-do the measurement, though).

Bootstrapped and tested on x86_64-unknown-linux-gnu for all languages
including Ada.

Ok for mainline?

Thanks,
Richard.


2006-02-04  Richard Guenther  <rguenther@suse.de>

	* tree-flow.h (get_stmt_rhs_def_stmt): Declare.
	(offset_overlaps_with_access): Likewise.
	* tree-flow-inline.h (offset_overlaps_with_access): New
	inline function definition.
	* tree-ssa-structalias.c (offset_overlaps_with_access):
	Remove.
	* tree-dfa.c (get_ref_base_and_extent): Remove assertion.
	Deal with structures ending in arrays and such unknown
	extent.
	(get_stmt_rhs_def_stmt): New helper walking virtual
	use-def chains.
	* tree-ssa-copy.c (stmt_may_generate_copy): Adjust for
	copyprop through aggregates.
	(copy_prop_visit_stmt): Likewise.
	(copy_prop_visit_assignment): For SSA_NAMEs defined by
	a memory load walk the virtual use-def chain searching for
	a definition of the memory load that is an SSA_NAME and
	use that for propagation.

	* gcc.dg.torture/copyprop-1.c: New testcase.
	* gcc.dg.torture/copyprop-2.c: Likewise.
	* gcc.dg/tree-ssa/copyprop-1.c: Likewise.
	* gcc.dg/tree-ssa/copyprop-2.c: Likewise.


Index: gcc/testsuite/gcc.dg/torture/copyprop-1.c
===================================================================
*** gcc/testsuite/gcc.dg/torture/copyprop-1.c	(revision 0)
--- gcc/testsuite/gcc.dg/torture/copyprop-1.c	(revision 0)
***************
*** 0 ****
--- 1,14 ----
+ /* { dg-do compile } */
+ 
+ struct set {
+     int src_hash;
+     int src_volatile;
+ };
+ void cse_insn (struct set *sets, int* j, int* k)
+ {
+     sets->src_hash = (*j && *k)
+ 	? *(int*)0
+ 	: *(int*)1;
+     sets->src_volatile = 0;
+     lookup (sets->src_hash);
+ }
Index: gcc/testsuite/gcc.dg/torture/copyprop-2.c
===================================================================
*** gcc/testsuite/gcc.dg/torture/copyprop-2.c	(revision 0)
--- gcc/testsuite/gcc.dg/torture/copyprop-2.c	(revision 0)
***************
*** 0 ****
--- 1,13 ----
+ /* { dg-do compile } */
+ /* { dg-options "-fno-tree-salias" } */
+ 
+ struct set {
+     int src_hash;
+ } sets;
+ void cse_insn (int* j, int* k)
+ {
+     sets.src_hash = (*j && *k)
+ 	? *(int*)0
+ 	: *(int*)1;
+     lookup (sets.src_hash);
+ }
Index: gcc/testsuite/gcc.dg/tree-ssa/copyprop-1.c
===================================================================
*** gcc/testsuite/gcc.dg/tree-ssa/copyprop-1.c	(revision 0)
--- gcc/testsuite/gcc.dg/tree-ssa/copyprop-1.c	(revision 0)
***************
*** 0 ****
--- 1,16 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O -fno-tree-sra -fno-tree-salias -fdump-tree-copyprop-details" } */
+ 
+ typedef struct {
+   int i;
+   int j;
+ } A;
+ int foo(A *a, int i, int j)
+ {
+   a->i = i;
+   a->j = j;
+   return a->i + a->j;
+ }
+ 
+ /* { dg-final { scan-tree-dump "into:.*i_. \\+ j_." "copyprop1" } } */
+ /* { dg-final { cleanup-tree-dump "copyprop" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/copyprop-2.c
===================================================================
*** gcc/testsuite/gcc.dg/tree-ssa/copyprop-2.c	(revision 0)
--- gcc/testsuite/gcc.dg/tree-ssa/copyprop-2.c	(revision 0)
***************
*** 0 ****
--- 1,16 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O -fno-tree-sra -fno-tree-salias -fdump-tree-copyprop-details" } */
+ 
+ int foo(int i, int j)
+ {
+   struct {
+     int i;
+     int j;
+   } a;
+   a.i = i;
+   a.j = j;
+   return a.i + a.j;
+ }
+ 
+ /* { dg-final { scan-tree-dump "into:.*i_. \\+ j_." "copyprop1" } } */
+ /* { dg-final { cleanup-tree-dump "copyprop" } } */
Index: gcc/tree-flow-inline.h
===================================================================
*** gcc/tree-flow-inline.h	(revision 110433)
--- gcc/tree-flow-inline.h	(working copy)
*************** overlap_subvar (unsigned HOST_WIDE_INT o
*** 1547,1550 ****
--- 1547,1570 ----
  
  }
  
+ 
+ /* Return true if an access to [ACCESSPOS, ACCESSSIZE]
+    overlaps with a field at [FIELDPOS, FIELDSIZE] */
+ 
+ static inline bool
+ offset_overlaps_with_access (const unsigned HOST_WIDE_INT fieldpos,
+ 			     const unsigned HOST_WIDE_INT fieldsize,
+ 			     const unsigned HOST_WIDE_INT accesspos,
+ 			     const unsigned HOST_WIDE_INT accesssize)
+ {
+   if (fieldpos == accesspos && fieldsize == accesssize)
+     return true;
+   if (accesspos >= fieldpos && accesspos < (fieldpos + fieldsize))
+     return true;
+   if (accesspos < fieldpos && (accesspos + accesssize > fieldpos))
+     return true;
+   
+   return false;
+ }
+ 
  #endif /* _TREE_FLOW_INLINE_H  */
Index: gcc/tree-ssa-copy.c
===================================================================
*** gcc/tree-ssa-copy.c	(revision 110433)
--- gcc/tree-ssa-copy.c	(working copy)
*************** stmt_may_generate_copy (tree stmt)
*** 370,382 ****
    /* If we are not doing store copy-prop, statements with loads and/or
       stores will never generate a useful copy.  */
    if (!do_store_copy_prop
!       && !ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
      return false;
  
    /* Otherwise, the only statements that generate useful copies are
       assignments whose RHS is just an SSA name that doesn't flow
       through abnormal edges.  */
!   return TREE_CODE (rhs) == SSA_NAME && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs);
  }
  
  
--- 370,391 ----
    /* If we are not doing store copy-prop, statements with loads and/or
       stores will never generate a useful copy.  */
    if (!do_store_copy_prop
!       && !ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS | SSA_OP_VIRTUAL_KILLS
! 				   | SSA_OP_VMAYUSE))
      return false;
  
    /* Otherwise, the only statements that generate useful copies are
       assignments whose RHS is just an SSA name that doesn't flow
       through abnormal edges.  */
!   if (TREE_CODE (rhs) == SSA_NAME)
!     return !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs);
! 
!   /* For non SSA_NAME RHS only visit statements that have interesting base.  */
!   if (TREE_CODE (lhs) == SSA_NAME
!       && handled_component_p (rhs))
!     return true;
! 
!   return false;
  }
  
  
*************** dump_copy_of (FILE *dump_file, tree var)
*** 523,529 ****
    sbitmap_free (visited);
  }
  
- 
  /* Evaluate the RHS of STMT.  If it produces a valid copy, set the LHS
     value and store the LHS into *RESULT_P.  If STMT generates more
     than one name (i.e., STMT is an aliased store), it is enough to
--- 532,537 ----
*************** copy_prop_visit_assignment (tree stmt, t
*** 539,545 ****
    lhs = TREE_OPERAND (stmt, 0);
    rhs = TREE_OPERAND (stmt, 1);
  
!   gcc_assert (TREE_CODE (rhs) == SSA_NAME);
  
    rhs_val = get_copy_of_val (rhs);
  
--- 547,586 ----
    lhs = TREE_OPERAND (stmt, 0);
    rhs = TREE_OPERAND (stmt, 1);
  
!   /* Try seeing through reference trees maybe finally ending up
!      with a SSA_NAME (or constant - but that's for cprop).
!      We might want to cache a (negative) outcome of get_ref_base_and_extent.  */
!   if (TREE_CODE (rhs) != SSA_NAME
!       /* Ignore store copyprop for now.  */
!       && TREE_CODE (lhs) == SSA_NAME)
!     {
!       tree def;
! 
!       def = get_stmt_rhs_def_stmt (stmt);
!       if (! def)
! 	return SSA_PROP_VARYING;
! 
!       /* Record lhs as copy of TREE_OPERAND (def, 1) in case it's an
! 	 SSA_NAME.  We could record constants here, too, but that breaks
! 	 in visiting the copy chains in get_last_copy_of.
! 	 XXX  Just setting rhs to TREE_OPERAND (def, 1) and continuing
! 	      with the path for SSA_NAME rhs below does not work as we
! 	      might never re-simulate this statement again to correct
! 	      wrong answers we got.
! 	      See copyprop-1 and copyprop-3 testcases.  */
!       if (TREE_CODE (TREE_OPERAND (def, 1)) != SSA_NAME
! 	  || ! may_propagate_copy (lhs, TREE_OPERAND (def, 1)))
! 	return SSA_PROP_VARYING;
!       *result_p = lhs;
!       if (set_copy_of_val (*result_p, TREE_OPERAND (def, 1), NULL))
! 	return SSA_PROP_INTERESTING;
!       else
! 	return SSA_PROP_NOT_INTERESTING;
!     }
! 
!   if (TREE_CODE (rhs) != SSA_NAME)
!     return SSA_PROP_VARYING;
!   /*gcc_assert (TREE_CODE (rhs) == SSA_NAME);*/
  
    rhs_val = get_copy_of_val (rhs);
  
*************** copy_prop_visit_stmt (tree stmt, edge *t
*** 684,690 ****
    ann = stmt_ann (stmt);
  
    if (TREE_CODE (stmt) == MODIFY_EXPR
-       && TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME
        && (do_store_copy_prop
  	  || TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME))
      {
--- 725,730 ----
Index: gcc/tree-flow.h
===================================================================
*** gcc/tree-flow.h	(revision 110433)
--- gcc/tree-flow.h	(working copy)
*************** static inline bool ref_contains_array_re
*** 607,616 ****
--- 607,622 ----
  static inline bool array_ref_contains_indirect_ref (tree);
  extern tree get_ref_base_and_extent (tree, HOST_WIDE_INT *,
  				     HOST_WIDE_INT *, HOST_WIDE_INT *);
+ extern tree get_stmt_rhs_def_stmt (tree stmt);
  static inline bool var_can_have_subvars (tree);
  static inline bool overlap_subvar (unsigned HOST_WIDE_INT,
  				   unsigned HOST_WIDE_INT,
  				   subvar_t, bool *);
+ static inline bool
+ offset_overlaps_with_access (const unsigned HOST_WIDE_INT fieldpos,
+ 			     const unsigned HOST_WIDE_INT fieldsize,
+ 			     const unsigned HOST_WIDE_INT accesspos,
+ 			     const unsigned HOST_WIDE_INT accesssize);
  
  /* Call-back function for walk_use_def_chains().  At each reaching
     definition, a function with this prototype is called.  */
Index: gcc/tree-ssa-structalias.c
===================================================================
*** gcc/tree-ssa-structalias.c	(revision 110433)
--- gcc/tree-ssa-structalias.c	(working copy)
*************** bitpos_of_field (const tree fdecl)
*** 2321,2346 ****
           + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl), 1);
  }
  
- 
- /* Return true if an access to [ACCESSPOS, ACCESSSIZE]
-    overlaps with a field at [FIELDPOS, FIELDSIZE] */
- 
- static bool
- offset_overlaps_with_access (const unsigned HOST_WIDE_INT fieldpos,
- 			     const unsigned HOST_WIDE_INT fieldsize,
- 			     const unsigned HOST_WIDE_INT accesspos,
- 			     const unsigned HOST_WIDE_INT accesssize)
- {
-   if (fieldpos == accesspos && fieldsize == accesssize)
-     return true;
-   if (accesspos >= fieldpos && accesspos < (fieldpos + fieldsize))
-     return true;
-   if (accesspos < fieldpos && (accesspos + accesssize > fieldpos))
-     return true;
-   
-   return false;
- }
- 
  /* Given a COMPONENT_REF T, return the constraint_expr for it.  */
  
  static void
--- 2321,2326 ----
Index: gcc/tree-dfa.c
===================================================================
*** gcc/tree-dfa.c	(revision 110539)
--- gcc/tree-dfa.c	(working copy)
*************** get_ref_base_and_extent (tree exp, HOST_
*** 914,921 ****
    tree size_tree = NULL_TREE;
    tree bit_offset = bitsize_zero_node;
  
-   gcc_assert (!SSA_VAR_P (exp));
- 
    /* First get the final access size from just the outermost expression.  */
    if (TREE_CODE (exp) == COMPONENT_REF)
      size_tree = DECL_SIZE (TREE_OPERAND (exp, 1));
--- 914,919 ----
*************** get_ref_base_and_extent (tree exp, HOST_
*** 1010,1018 ****
  		tree asize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
  		/* We need to adjust maxsize to the whole array bitsize.
  		   But we can subtract any constant offset seen sofar,
! 		   because that would get us outside of the array otherwise.  */
  		if (maxsize != -1
! 		    && asize && host_integerp (asize, 1))
  		  {
  		    maxsize = (TREE_INT_CST_LOW (asize)
  			       - TREE_INT_CST_LOW (bit_offset));
--- 1008,1031 ----
  		tree asize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
  		/* We need to adjust maxsize to the whole array bitsize.
  		   But we can subtract any constant offset seen sofar,
! 		   because that would get us outside of the array otherwise.
! 		   For the case of the last element of a structure being an
!                    array like
!                         struct {
!                           X a[1];
!                         };
!                    we can not assume a maxsize of the array size though!
!                    XXX  I believe it is safe to set maxsize to -1 in the
!                         case of asize == bitsize (i.e. a single element array,
!                         regardless of structure embedding and position)
!                         because otherwise maxsize != bitsize and that should
!                         inhibit misoptimizations.  In the end proper
!                         detection if the array referenced here is the last
!                         element of the outermost type is correct.  */
! 
  		if (maxsize != -1
! 		    && asize && host_integerp (asize, 1)
! 		    && (unsigned HOST_WIDE_INT)bitsize != TREE_INT_CST_LOW (asize))
  		  {
  		    maxsize = (TREE_INT_CST_LOW (asize)
  			       - TREE_INT_CST_LOW (bit_offset));
*************** get_ref_base_and_extent (tree exp, HOST_
*** 1052,1054 ****
--- 1065,1134 ----
  
    return exp;
  }
+ 
+ /* Return the defining stmt for the rhs of STMT following the virtual
+    use-def chains.  Returns the MODIFY_EXPR stmt which rhs is equal
+    to the lhs of STMT or NULL_TREE if no such stmt can be found.  */
+ 
+ tree
+ get_stmt_rhs_def_stmt (tree stmt)
+ {
+   /* See if we know exactly where this comes from.  */
+   tree def, rhs;
+   tree base;
+   HOST_WIDE_INT offset, size, maxsize;
+   tree base2;
+   HOST_WIDE_INT offset2, size2, maxsize2;
+   use_operand_p use;
+ 
+   gcc_assert (TREE_CODE (stmt) == MODIFY_EXPR);
+ 
+   rhs = TREE_OPERAND (stmt, 1);
+ 
+   /* If we don't know where this comes from, bail out.  */
+   base = get_ref_base_and_extent (rhs, &offset, &size, &maxsize);
+   if (size == -1 || size != maxsize)
+     return NULL_TREE;
+ 
+   /* The stmt must have a single VUSE.  */
+   use = SINGLE_SSA_USE_OPERAND (stmt, SSA_OP_VUSE);
+   if (use == NULL_USE_OPERAND_P)
+     return NULL_TREE;
+ 
+   do
+     {
+       /* Look at the DEF for the VUSE and see if it matches this USE
+ 	 and if it's RHS is an SSA_NAME.  Don't try to deal with
+ 	 PHI_NODEs.  */
+       def = SSA_NAME_DEF_STMT (*use->use);
+       if (TREE_CODE (def) != MODIFY_EXPR)
+ 	return NULL_TREE;
+ 
+       base2 = get_ref_base_and_extent (TREE_OPERAND (def, 0), &offset2,
+ 				       &size2, &maxsize2);
+       /* If the base of the DEF does not match that of the USE it may
+ 	 be a clobber.  Bail out in this case.  */
+       if (!operand_equal_p (base, base2, 0))
+ 	return NULL_TREE;
+ 
+       /* If the access touches our read, this has to be the one we're
+ 	 interested in.  Bail out if it is not.  */
+       if (offset_overlaps_with_access (offset, size, offset2, maxsize2))
+         {
+ 	  /* If the DEF is not exact and matches, bail out.  */
+ 	  if (maxsize2 != size2
+ 	      || size2 != size || offset2 != offset)
+ 	    return NULL_TREE;
+ 
+ 	  /* For now just handle a distance of one.  If the RHS of the DEF
+ 	     is another ref, we could recurse here.
+ 	     ???  Recurse here?  */
+ 	  return def;
+ 	}
+ 
+       /* Else just skip it and search for the next one.  */
+       use = SINGLE_SSA_USE_OPERAND (def, SSA_OP_VMAYUSE);
+       if (use == NULL_USE_OPERAND_P)
+ 	return NULL_TREE;
+     } while (1);
+ }