Re: [PATCH] Fix PR26135, store copyprop being not effective

[Richard Guenther <rguenther at suse dot de>]

On Tue, 7 Feb 2006, Richard Guenther wrote:

> This adds the missing parts to the copyprop implementation to do store
> copyprop.
> 
> Bootstrapped and tested on x86_64-unknown-linux-gnu, plain and with
> -fno-tree-dominator-opts (as most store copyprop opportunities are
> already handled by DOM).

And here is an alternative patch, killing current store copyprop and
replacing it with a more powerful one walking virtual use-def chains
(but at the same time making the stores propagation barriers due to
limitation to single-outputs of the propagator).

As this is (with this patch) only done for store-copyprop and 
store-copyprop runs very late (we could move it before PRE I suppose),
I'm currently re-doing SPEC testing.

Bootstrapped and tested on x86_64-unknown-linux-gnu.

I have a similar patch for tree-ssa-ccp.c, which would allow us to
kill mem_ref in prop_value_t.  Also it looks like get_stmt_rhs_def_stmt
could be used by tree-ssa-pre.c:try_look_through_load or 
get_stmt_rhs_def_stmt could be extended to allow multiple VUSEs.

Comments?

Thanks,
Richard.


2006-02-08  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): Handle
	memory load stmts.
	(copy_prop_visit_stmt): Deal with memory load stmts, do not
	simulate stores.
	(copy_prop_visit_assignment): Remove store copyprop code.
	(copy_prop_visit_phi_node): Remove store copyprop code.


Index: tree-flow-inline.h
===================================================================
*** tree-flow-inline.h	(revision 110745)
--- tree-flow-inline.h	(working copy)
*************** overlap_subvar (unsigned HOST_WIDE_INT o
*** 1525,1528 ****
--- 1525,1548 ----
  
  }
  
+ 
+ /* 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: tree-dfa.c
===================================================================
*** tree-dfa.c	(revision 110745)
--- tree-dfa.c	(working copy)
*************** get_ref_base_and_extent (tree exp, HOST_
*** 913,920 ****
    HOST_WIDE_INT maxsize = -1;
    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)
--- 913,919 ----
    HOST_WIDE_INT maxsize = -1;
    tree size_tree = NULL_TREE;
    tree bit_offset = bitsize_zero_node;
!   bool seen_variable_array_ref = false;
  
    /* First get the final access size from just the outermost expression.  */
    if (TREE_CODE (exp) == COMPONENT_REF)
*************** get_ref_base_and_extent (tree exp, HOST_
*** 1004,1009 ****
--- 1003,1011 ----
  				    fold_convert (bitsizetype, index),
  				    bitsize_unit_node);
  		bit_offset = size_binop (PLUS_EXPR, bit_offset, index);
+ 		/* A more outer constant index array ref subsumes any
+ 		   variable array ref seen sofar.  */
+ 		seen_variable_array_ref = false;
  	      }
  	    else
  	      {
*************** get_ref_base_and_extent (tree exp, HOST_
*** 1019,1024 ****
--- 1021,1028 ----
  		  }
  		else
  		  maxsize = -1;
+ 		/* Remember we seen an array ref with a variable index.  */
+ 		seen_variable_array_ref = true;
  	      }
  	  }
  	  break;
*************** get_ref_base_and_extent (tree exp, HOST_
*** 1043,1048 ****
--- 1047,1067 ----
      }
   done:
  
+   /* We need to deal with variable arrays ending structures such as
+        struct { int length; int a[1]; } x;           x.a[d]
+        struct { struct { int a; int b; } a[1]; } x;  x.a[d].a
+        struct { struct { int a[1]; } a[1]; } x;      x.a[0][d], x.a[d][0]
+      where we do not know maxsize for variable index accesses to
+      the array.  The simplest way to conservatively deal with this
+      is to punt in the case that offset + maxsize reaches the
+      base type boundary.  */
+   if (seen_variable_array_ref
+       && maxsize != -1
+       && host_integerp (TYPE_SIZE (TREE_TYPE (exp)), 1)
+       && TREE_INT_CST_LOW (bit_offset) + maxsize
+ 	 == TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (exp))))
+     maxsize = -1;
+ 
    /* ???  Due to negative offsets in ARRAY_REF we can end up with
       negative bit_offset here.  We might want to store a zero offset
       in this case.  */
*************** get_ref_base_and_extent (tree exp, HOST_
*** 1052,1054 ****
--- 1071,1140 ----
  
    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);
+ }
Index: tree-ssa-copy.c
===================================================================
*** tree-ssa-copy.c	(revision 110745)
--- tree-ssa-copy.c	(working copy)
*************** stmt_may_generate_copy (tree stmt)
*** 376,382 ****
    /* 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);
  }
  
  
--- 376,385 ----
    /* 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 (do_store_copy_prop
! 	  && TREE_CODE (lhs) == SSA_NAME)
! 	 || (TREE_CODE (rhs) == SSA_NAME
! 	     && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs));
  }
  
  
*************** copy_prop_visit_assignment (tree stmt, t
*** 570,604 ****
        else
  	return SSA_PROP_NOT_INTERESTING;
      }
-   else if (stmt_makes_single_store (stmt))
-     {
-       /* Otherwise, set the names in V_MAY_DEF/V_MUST_DEF operands
- 	 to be a copy of RHS.  */
-       ssa_op_iter i;
-       tree vdef;
-       bool changed;
- 
-       /* This should only be executed when doing store copy-prop.  */
-       gcc_assert (do_store_copy_prop);
- 
-       /* Set the value of every VDEF to RHS_VAL.  */
-       changed = false;
-       FOR_EACH_SSA_TREE_OPERAND (vdef, stmt, i, SSA_OP_VIRTUAL_DEFS)
- 	changed |= set_copy_of_val (vdef, rhs_val->value, lhs);
-       
-       /* Note that for propagation purposes, we are only interested in
- 	 visiting statements that load the exact same memory reference
- 	 stored here.  Those statements will have the exact same list
- 	 of virtual uses, so it is enough to set the output of this
- 	 statement to be its first virtual definition.  */
-       *result_p = first_vdef (stmt);
- 
-       if (changed)
- 	return SSA_PROP_INTERESTING;
-       else
- 	return SSA_PROP_NOT_INTERESTING;
-     }
- 
  
    return SSA_PROP_VARYING;
  }
--- 573,578 ----
*************** copy_prop_visit_stmt (tree stmt, edge *t
*** 684,697 ****
    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))
      {
        /* If the statement is a copy assignment, evaluate its RHS to
  	 see if the lattice value of its output has changed.  */
        retval = copy_prop_visit_assignment (stmt, result_p);
      }
    else if (TREE_CODE (stmt) == COND_EXPR)
      {
        /* See if we can determine which edge goes out of a conditional
--- 658,699 ----
    ann = stmt_ann (stmt);
  
    if (TREE_CODE (stmt) == MODIFY_EXPR
!       && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME
!       && TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME)
      {
        /* If the statement is a copy assignment, evaluate its RHS to
  	 see if the lattice value of its output has changed.  */
        retval = copy_prop_visit_assignment (stmt, result_p);
      }
+   else if (TREE_CODE (stmt) == MODIFY_EXPR
+ 	   && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME
+ 	   && do_store_copy_prop
+ 	   && stmt_makes_single_load (stmt))
+     {
+       /* If the statement is a copy assignment with a memory load
+ 	 on the RHS, see if we know the value of this load and
+ 	 update the lattice accordingly.  Due to the inability of
+ 	 the propagation engine to deal with multiple outputs use
+ 	 the value from the RHS of the def stmt, not its lattice
+ 	 value.  This way a propagated store acts as a propagation
+ 	 barrier.  */
+       tree val = get_stmt_rhs_def_stmt (stmt);
+       if (val
+ 	  && is_gimple_reg (TREE_OPERAND (val, 1)))
+ 	{
+ 	  bool changed = set_copy_of_val (TREE_OPERAND (stmt, 0),
+ 					  TREE_OPERAND (val, 1), NULL_TREE);
+ 	  if (changed)
+ 	    {
+ 	      *result_p = TREE_OPERAND (stmt, 0);
+ 	      retval = SSA_PROP_INTERESTING;
+ 	    }
+ 	  else
+ 	    retval = SSA_PROP_NOT_INTERESTING;
+ 	}
+       else
+ 	retval = SSA_PROP_VARYING;
+     }
    else if (TREE_CODE (stmt) == COND_EXPR)
      {
        /* See if we can determine which edge goes out of a conditional
*************** copy_prop_visit_phi_node (tree phi)
*** 804,814 ****
  	 copy propagating stores and these two arguments came from
  	 different memory references, they cannot be considered
  	 copies.  */
!       if (get_last_copy_of (phi_val.value) != get_last_copy_of (arg)
! 	  || (do_store_copy_prop
! 	      && phi_val.mem_ref
! 	      && arg_val->mem_ref
! 	      && simple_cst_equal (phi_val.mem_ref, arg_val->mem_ref) != 1))
  	{
  	  phi_val.value = lhs;
  	  break;
--- 806,812 ----
  	 copy propagating stores and these two arguments came from
  	 different memory references, they cannot be considered
  	 copies.  */
!       if (get_last_copy_of (phi_val.value) != get_last_copy_of (arg))
  	{
  	  phi_val.value = lhs;
  	  break;
Index: tree-flow.h
===================================================================
*** tree-flow.h	(revision 110745)
--- 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: tree-ssa-structalias.c
===================================================================
*** tree-ssa-structalias.c	(revision 110745)
--- tree-ssa-structalias.c	(working copy)
*************** bitpos_of_field (const tree fdecl)
*** 2317,2342 ****
           + 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
--- 2317,2322 ----