This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[tcb] Re-enable copy propagation of loads and stores


This is similar to the store-ccp changes I committed a few days ago.  It
fixes a bug in the propagation of stores and loads.  We were only
looking at the first virtual definition and use of statements.  That
fails in many aliasing situations, of course.  Astonishingly, the
compiler was still bootstrapping.  I added a test case and slapped
myself silly.

The rest is just adding the additional glue needed to support copy
propagation of loads and stores.  It goes along the same lines as
STORE-CCP, so it's just mechanical changes.

Similarly to STORE-CCP, I only enabled STORE-COPY-PROP at -O2 and
higher.  When STORE-COPY-PROP is not enabled, we fall back to regular
copy propagation.

Bootstrapped and tested x86, x86-64 and ppc.


Diego.


	* common.opt (-ftree-store-copy-prop): New flag.
	* opts.c (decode_options): Enable STORE-COPY-PROP at O2.
	* timevar.def (TV_TREE_STORE_COPY_PROP): Define.
	* tree-flow.h (execute_copy_prop): Add boolean argument.
	* tree-optimize.c (init_tree_optimization_passes): Schedule
	STORE-COPY-PROP after SRA.
	* tree-pass.h (pass_store_copy_prop): Declare.
	* tree-ssa-ccp.c (set_lattice_value): Fix typo in comment.
	(replace_uses_in): Call may_propagate_copy before doing the
	final propagation.
	(replace_vuses_in): Call get_value_loaded_by.
	(ccp_lattice_meet): Do not test for memory reference equality
	if DO_STORE_CCP is false.
	(ccp_fold): Call get_value_loaded_by.
	(visit_assignment): Likewise.
	Set all the virtual definitions in the statement to the newly
	computed value.
	(ccp_visit_stmt): Reformat dump output.
	(do_ssa_store_ccp): If STORE-CCP is not enabled, run standard
	CCP.
	(gate_store_ccp): Return true if either CCP or STORE-CCP are
	enabled.
	(pass_store_ccp): Rename dump suffix.
	* tree-ssa-copy.c (cached_last_copy_of): Declare.
	(stmt_may_generate_copy): Return false if the name occurs in
	an abnormal PHI.
	(copy_chains): Remove.  Update all functions to use COPY_OF
	instead.
	(get_copy_of_val): Rename from get_first_copy.  Return a
	pointer to the COPY_OF slot for VAR.
	(set_copy_of_val): Rename from set_first_copy_of.
	Used CACHED_LAST_COPY_OF to determine whether the copy-of
	chain has changed.
	(copy_prop_visit_assignment): Do not call may_propagate_copy.
	In the case of STORE-COPY-PROP set the copy-of value for all
	the virtual definitions.
	(copy_prop_visit_stmt): Reformat dump output.
	(copy_prop_visit_phi_node): Support STORE-COPY-PROP by
	checking memory references for each argument.
	Do not allow copies to flow through abnormal edges.
	(init_copy_prop): Allocate cached_last_copy_of.
	(fini_copy_prop): Free cached_last_copy_of
	(execute_copy_prop): Add new boolean argument to determine
	whether to enable STORE-COPY-PROP.
	(do_copy_prop): New function.
	(pass_copy_prop): Call do_copy_prop.
	(gate_store_copy_prop): New function.
	(store_copy_prop): New function.
	(pass_store_copy_prop): Define.
	* tree-ssa-propagate.c (first_vuse): Remove.
	(get_value_loaded_by): New function.
	* tree-ssa-propagate.h (first_vuse): Remove.
	(get_value_loaded_by): Declare.
	* doc/invoke.texi (-ftree-store-copy-prop): Document.
	(-fdump-tree-store_copyprop): Document.


testsuite/ChangeLog.tcb

	* gcc.c-torture/execute/20041019-1.c: New test.

Index: common.opt
===================================================================
RCS file: /cvs/gcc/gcc/gcc/common.opt,v
retrieving revision 1.55.2.4
diff -d -c -p -u -r1.55.2.4 common.opt
--- common.opt	15 Oct 2004 03:19:40 -0000	1.55.2.4
+++ common.opt	19 Oct 2004 20:53:46 -0000
@@ -838,7 +838,11 @@ Replace SSA temporaries with better name
 
 ftree-copy-prop
 Common Report Var(flag_tree_copy_prop)
-Enable expression propagation and simplification on trees
+Enable copy propagation on trees
+
+ftree-store-copy-prop
+Common Report Var(flag_tree_store_copy_prop)
+Enable copy propagation for stores and loads
 
 ftree-dce
 Common Report Var(flag_tree_dce)
Index: opts.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/opts.c,v
retrieving revision 1.82.2.2
diff -d -c -p -u -r1.82.2.2 opts.c
--- opts.c	15 Oct 2004 03:19:40 -0000	1.82.2.2
+++ opts.c	19 Oct 2004 20:53:46 -0000
@@ -540,6 +540,7 @@ decode_options (unsigned int argc, const
       flag_reorder_functions = 1;
       flag_unit_at_a_time = 1;
       flag_tree_store_ccp = 1;
+      flag_tree_store_copy_prop = 1;
     }
 
   if (optimize >= 3)
Index: timevar.def
===================================================================
RCS file: /cvs/gcc/gcc/gcc/timevar.def,v
retrieving revision 1.36.2.3
diff -d -c -p -u -r1.36.2.3 timevar.def
--- timevar.def	15 Oct 2004 03:19:40 -0000	1.36.2.3
+++ timevar.def	19 Oct 2004 20:53:46 -0000
@@ -65,6 +65,7 @@ DEFTIMEVAR (TV_TREE_EH		     , "tree eh"
 DEFTIMEVAR (TV_TREE_CFG		     , "tree CFG construction")
 DEFTIMEVAR (TV_TREE_CLEANUP_CFG	     , "tree CFG cleanup")
 DEFTIMEVAR (TV_TREE_COPY_PROP        , "tree copy propagation")
+DEFTIMEVAR (TV_TREE_STORE_COPY_PROP  , "tree store copy propagation")
 DEFTIMEVAR (TV_TREE_PTA		     , "tree PTA")
 DEFTIMEVAR (TV_TREE_MAY_ALIAS        , "tree alias analysis")
 DEFTIMEVAR (TV_TREE_INSERT_PHI_NODES , "tree PHI insertion")
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.46.2.5
diff -d -c -p -u -r2.46.2.5 tree-flow.h
--- tree-flow.h	15 Oct 2004 03:19:40 -0000	2.46.2.5
+++ tree-flow.h	19 Oct 2004 20:53:46 -0000
@@ -635,7 +635,7 @@ extern void propagate_tree_value (tree *
 extern void replace_exp (use_operand_p, tree);
 extern bool may_propagate_copy (tree, tree);
 extern bool may_propagate_copy_into_asm (tree);
-extern void execute_copy_prop (void);
+extern void execute_copy_prop (bool);
 
 /* Description of number of iterations of a loop.  All the expressions inside
    the structure can be evaluated at the end of the loop's preheader
Index: tree-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-optimize.c,v
retrieving revision 2.47.2.6
diff -d -c -p -u -r2.47.2.6 tree-optimize.c
--- tree-optimize.c	15 Oct 2004 03:19:40 -0000	2.47.2.6
+++ tree-optimize.c	19 Oct 2004 20:53:47 -0000
@@ -363,7 +363,7 @@ init_tree_optimization_passes (void)
   NEXT_PASS (pass_profile);
   NEXT_PASS (pass_sra);
   NEXT_PASS (pass_store_ccp);
-  NEXT_PASS (pass_copy_prop);
+  NEXT_PASS (pass_store_copy_prop);
   NEXT_PASS (pass_fre);
   NEXT_PASS (pass_dce);
   NEXT_PASS (pass_dominator);
Index: tree-pass.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-pass.h,v
retrieving revision 2.15.2.4
diff -d -c -p -u -r2.15.2.4 tree-pass.h
--- tree-pass.h	15 Oct 2004 03:19:41 -0000	2.15.2.4
+++ tree-pass.h	19 Oct 2004 20:53:47 -0000
@@ -163,5 +163,6 @@ extern struct tree_opt_pass pass_fre;
 extern struct tree_opt_pass pass_linear_transform;
 extern struct tree_opt_pass pass_copy_prop;
 extern struct tree_opt_pass pass_store_ccp;
+extern struct tree_opt_pass pass_store_copy_prop;
 
 #endif /* GCC_TREE_PASS_H */
Index: tree-ssa-ccp.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-ccp.c,v
retrieving revision 2.41.2.5
diff -d -c -p -u -r2.41.2.5 tree-ssa-ccp.c
--- tree-ssa-ccp.c	15 Oct 2004 14:51:43 -0000	2.41.2.5
+++ tree-ssa-ccp.c	19 Oct 2004 20:53:47 -0000
@@ -308,7 +308,7 @@ get_default_value (tree var)
       val.lattice_val = VARYING;
     }
   else if (SSA_NAME_VALUE (var)
-      && is_gimple_min_invariant (SSA_NAME_VALUE (var)))
+	   && is_gimple_min_invariant (SSA_NAME_VALUE (var)))
     {
       val.lattice_val = CONSTANT;
       val.value = SSA_NAME_VALUE (var);
@@ -391,7 +391,7 @@ set_lattice_value (tree var, prop_value_
      1- If *OLD_VAL and NEW_VAL are the same, return false to
 	inform the caller that this was a non-transition.
 
-     2- If we are doing store-ccp (ie, DOIN_STORE_CCP is true),
+     2- If we are doing store-ccp (i.e., DOING_STORE_CCP is true),
 	allow CONSTANT->UNKNOWN_VAL.  The UNKNOWN_VAL state is a
 	special type of UNDEFINED state which prevents the short
 	circuit evaluation of PHI arguments (see ccp_visit_phi_node
@@ -636,6 +636,9 @@ replace_uses_in (tree stmt, bool *replac
 	  && !may_propagate_copy_into_asm (tuse))
 	continue;
 
+      if (!may_propagate_copy (tuse, val))
+	continue;
+
       if (TREE_CODE (val) != SSA_NAME)
 	prop_stats.num_const_prop++;
       else
@@ -728,41 +731,43 @@ replace_vuses_in (tree stmt, bool *repla
       /* If STMT is an assignment whose RHS is a single memory load,
 	 see if we are trying to propagate a constant or a GIMPLE
 	 register (case #1 above).  */
-      tree var = first_vuse (stmt);
-      prop_value_t val = prop_value[SSA_NAME_VERSION (var)];
+      prop_value_t *val = get_value_loaded_by (stmt, prop_value);
       tree rhs = TREE_OPERAND (stmt, 1);
 
-      if (val.value
-	  && val.value != var
-	  && (is_gimple_reg (val.value) || is_gimple_min_invariant (val.value))
-	  && simple_cst_equal (rhs, val.mem_ref) == 1)
+      if (val
+	  && val->value
+	  && (is_gimple_reg (val->value)
+	      || is_gimple_min_invariant (val->value))
+	  && simple_cst_equal (rhs, val->mem_ref) == 1)
 
 	{
+	  /* If we are replacing a constant address, inform our
+	     caller.  */
+	  if (TREE_CODE (val->value) != SSA_NAME
+	      && POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt, 1)))
+	      && replaced_addresses_p)
+	    *replaced_addresses_p = true;
+
 	  /* We can only perform the substitution if the load is done
 	     from the same memory location as the original store.
 	     Since we already know that there are no intervening
 	     stores between DEF_STMT and STMT, we only need to check
 	     that the RHS of STMT is the same as the memory reference
 	     propagated together with the value.  */
-	  TREE_OPERAND (stmt, 1) = val.value;
+	  TREE_OPERAND (stmt, 1) = val->value;
 
-	  if (TREE_CODE (val.value) != SSA_NAME)
+	  if (TREE_CODE (val->value) != SSA_NAME)
 	    prop_stats.num_const_prop++;
 	  else
 	    prop_stats.num_copy_prop++;
 
-	  /* If we are replacing a constant address, inform our
-	     caller.  */
-	  if (TREE_CODE (val.value) != SSA_NAME
-	      && POINTER_TYPE_P (TREE_TYPE (var))
-	      && replaced_addresses_p)
-	    *replaced_addresses_p = true;
-
 	  /* Since we have replaced the whole RHS of STMT, there
 	     is no point in checking the other VUSEs, as they will
 	     all have the same value.  */
 	  return true;
 	}
+      else
+	return false;
     }
 
   /* Otherwise, the values for every VUSE operand must be other
@@ -1005,7 +1010,7 @@ ccp_lattice_meet (prop_value_t *val1, pr
   else if (val1->lattice_val == CONSTANT
 	   && val2->lattice_val == CONSTANT
 	   && simple_cst_equal (val1->value, val2->value) == 1
-	   && ((val1->mem_ref == NULL_TREE && val2->mem_ref == NULL_TREE)
+	   && (!do_store_ccp
 	       || simple_cst_equal (val1->mem_ref, val2->mem_ref) == 1))
     {
       /* Ci M Cj = Ci		if (i == j)
@@ -1172,12 +1177,9 @@ ccp_fold (tree stmt)
   else if (do_store_ccp && stmt_makes_single_load (stmt))
     {
       /* If the RHS is a memory load, see if the VUSEs associated with
-	 it are a valid constant for that memory load.  Since this is
-	 a single load operation, all the VUSE operands will be
-	 associated with the same constant, so we only examine the
-	 first VUSE operand.  */
-      prop_value_t *val = get_value (first_vuse (stmt), true);
-      if (simple_cst_equal (val->mem_ref, rhs) == 1)
+	 it are a valid constant for that memory load.  */
+      prop_value_t *val = get_value_loaded_by (stmt, const_val);
+      if (val && simple_cst_equal (val->mem_ref, rhs) == 1)
 	return val->value;
       else
 	return NULL_TREE;
@@ -1387,17 +1389,11 @@ visit_assignment (tree stmt, tree *outpu
     {
       /* Same as above, but the RHS is not a gimple register and yet
          has a known VUSE.  If STMT is loading from the same memory
-	 location that created the SSA_NAME for the first VUSE
-	 operand, we can propagate the value on the RHS.
-
-	 Notice that it is enough to check the very first VUSE operand
-	 because (1) we know that STMT is an assignment with a single
-	 memory load on the RHS, and, (2) every VUSE operand for the
-	 RHS will have been created at the same statement, so all the
-	 values will be identical.  */
-      prop_value_t *nval = get_value (first_vuse (stmt), true);
+	 location that created the SSA_NAMEs for the virtual operands,
+	 we can propagate the value on the RHS.  */
+      prop_value_t *nval = get_value_loaded_by (stmt, const_val);
 
-      if (simple_cst_equal (nval->mem_ref, rhs) == 1)
+      if (nval && simple_cst_equal (nval->mem_ref, rhs) == 1)
 	val = *nval;
       else
 	val = evaluate_stmt (stmt);
@@ -1448,9 +1444,12 @@ visit_assignment (tree stmt, tree *outpu
     }
   else if (do_store_ccp && stmt_makes_single_store (stmt))
     {
-      /* Otherwise, set the first name in the V_MAY_DEF/V_MUST_DEF to
-	 the new constant value and mark the LHS as the memory
+      /* Otherwise, set the names in V_MAY_DEF/V_MUST_DEF operands
+	 to the new constant value and mark the LHS as the memory
 	 reference associated with VAL.  */
+      ssa_op_iter i;
+      tree vdef;
+      bool changed;
 
       /* Stores cannot take on an UNDEFINED value.  */
       if (val.lattice_val == UNDEFINED)
@@ -1459,8 +1458,18 @@ visit_assignment (tree stmt, tree *outpu
       /* Mark VAL as stored in the LHS of this assignment.  */
       val.mem_ref = lhs;
 
+      /* Set the value of every VDEF to VAL.  */
+      changed = false;
+      FOR_EACH_SSA_TREE_OPERAND (vdef, stmt, i, SSA_OP_VIRTUAL_DEFS)
+	changed |= set_lattice_value (vdef, val);
+      
+      /* 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.  */
       *output_p = first_vdef (stmt);
-      if (set_lattice_value (*output_p, val))
+      if (changed)
 	{
 	  if (val.lattice_val == VARYING)
 	    retval = SSA_PROP_VARYING;
@@ -1518,8 +1527,8 @@ ccp_visit_stmt (tree stmt, edge *taken_e
 
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
-      fprintf (dump_file, "\nVisiting statement: ");
-      print_generic_stmt (dump_file, stmt, TDF_SLIM);
+      fprintf (dump_file, "\nVisiting statement:\n");
+      print_generic_stmt (dump_file, stmt, dump_flags);
       fprintf (dump_file, "\n");
     }
 
@@ -1608,19 +1617,23 @@ struct tree_opt_pass pass_ccp = 
 static void
 do_ssa_store_ccp (void)
 {
-  execute_ssa_ccp (true);
+  /* If STORE-CCP is not enabled, we just run regular CCP.  */
+  execute_ssa_ccp (flag_tree_store_ccp != 0);
 }
 
 static bool
 gate_store_ccp (void)
 {
-  return flag_tree_store_ccp != 0;
+  /* STORE-CCP is enabled only with -ftree-store-ccp, but when
+     -fno-tree-store-ccp is specified, we should run regular CCP.
+     That's why the pass is enabled with either flag.  */
+  return flag_tree_store_ccp != 0 || flag_tree_ccp != 0;
 }
 
 
 struct tree_opt_pass pass_store_ccp = 
 {
-  "storeccp",				/* name */
+  "store_ccp",				/* name */
   gate_store_ccp,			/* gate */
   do_ssa_store_ccp,			/* execute */
   NULL,					/* sub */
Index: tree-ssa-copy.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-copy.c,v
retrieving revision 2.15.2.5
diff -d -c -p -u -r2.15.2.5 tree-ssa-copy.c
--- tree-ssa-copy.c	15 Oct 2004 03:19:41 -0000	2.15.2.5
+++ tree-ssa-copy.c	19 Oct 2004 20:53:47 -0000
@@ -299,17 +299,21 @@ replace_exp (use_operand_p op_p, tree va
 ---------------------------------------------------------------------------*/
 /* During propagation, we keep chains of variables that are copies of
    one another.  If variable X_i is a copy of X_j and X_j is a copy of
-   X_k, COPY_CHAINS will contain:
+   X_k, COPY_OF will contain:
 
-   	COPY_CHAINS[i] = X_j
-	COPY_CHAINS[j] = X_k
-	COPY_CHAINS[k] = X_k  */
-static tree *copy_chains;
+   	COPY_OF[i].VALUE = X_j
+	COPY_OF[j].VALUE = X_k
+	COPY_OF[k].VALUE = X_k
 
-/* Final copy values for each SSA name.  After propagation,
-   SSA_NAME(I) will be known to be a copy of COPY_OF[I].VALUE.  */
+   After propagation, the copy-of value for each variable X_i is
+   converted into the final value by walking the copy-of chains and
+   updating COPY_OF[i].VALUE to be the last element of the chain.  */
 static prop_value_t *copy_of;
 
+/* Used in set_copy_of_val to determine if the last link of a copy-of
+   chain has changed.  */
+static tree *cached_last_copy_of;
+
 /* True if we are doing copy propagation on loads and stores.  */
 static bool do_store_copy_prop;
 
@@ -322,6 +326,9 @@ stmt_may_generate_copy (tree stmt)
   tree lhs, rhs;
   stmt_ann_t ann;
 
+  if (TREE_CODE (stmt) == PHI_NODE)
+    return !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (stmt));
+
   if (TREE_CODE (stmt) != MODIFY_EXPR)
     return false;
 
@@ -345,8 +352,9 @@ stmt_may_generate_copy (tree stmt)
     return false;
 
   /* Otherwise, the only statements that generate useful copies are
-     assignments whose RHS is just an SSA name.  */
-  return TREE_CODE (rhs) == SSA_NAME;
+     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);
 }
 
 
@@ -356,62 +364,88 @@ static inline bool
 need_imm_uses_for (tree var)
 {
   /* The only statements that are interesting as seeds for copy
-     propagation are those assignments whose RHS is an SSA_NAME.  */
+     propagation are those assignments that may generate a copy.  */
   tree def_stmt = SSA_NAME_DEF_STMT (var);
   return stmt_may_generate_copy (def_stmt);
 }
 
 
-/* Return the first variable in the copy-of chain for VAR.  */
+/* Return the copy-of value for VAR.  */
 
-static inline tree
-get_first_copy_of (tree var)
+static inline prop_value_t *
+get_copy_of_val (tree var)
 {
-  unsigned ver = SSA_NAME_VERSION (var);
+  prop_value_t *val = &copy_of[SSA_NAME_VERSION (var)];
 
-  if (copy_chains[ver] == NULL_TREE && !need_imm_uses_for (var))
+  if (val->value == NULL_TREE && !need_imm_uses_for (var))
     {
       /* If the variable will never generate a useful copy relation,
-	 make it its own copy in COPY_CHAINS and set its value to
-	 NULL.  */
-      copy_chains[ver] = var;
-      copy_of[ver].value = NULL_TREE;
+	 make it its own copy.  */
+      val->value = var;
+      val->mem_ref = NULL_TREE;
     }
 
-  return copy_chains[ver];
+  return val;
 }
 
 
-/* Return last variable in the copy-of chain for variable VAR.  */
+/* Return last link in the copy-of chain for VAR.  */
 
 static tree
 get_last_copy_of (tree var)
 {
-  tree copy_of = var;
+  tree last;
 
-  while (copy_chains[SSA_NAME_VERSION (copy_of)]
-         && copy_chains[SSA_NAME_VERSION (copy_of)] != copy_of)
-    copy_of = copy_chains[SSA_NAME_VERSION (copy_of)];
+  /* Traverse COPY_OF starting at VAR until we get to the last
+     link in the chain.  */
+  last = var;
+  while (copy_of[SSA_NAME_VERSION (last)].value
+         && copy_of[SSA_NAME_VERSION (last)].value != last)
+    last = copy_of[SSA_NAME_VERSION (last)].value;
 
-  return (copy_of) ? copy_of : var;
+  return last;
 }
 
 
 /* Set FIRST to be the first variable in the copy-of chain for DEST.
-   Also set DEST's copy-of value to the last variable in the copy-of
-   chain for DEST.  If either value has changed, return true.  */
+   If DEST's copy-of value or its copy-of chain have changed, return
+   true.
+
+   MEM_REF is the memory reference where FIRST is stored.  This is
+   used when DEST is a non-register and we are copy propagating loads
+   and stores.  */
 
 static inline bool
-set_first_copy_of (tree dest, tree first)
+set_copy_of_val (tree dest, tree first, tree mem_ref)
 {
   unsigned int dest_ver = SSA_NAME_VERSION (dest);
-  tree old_first = copy_chains[dest_ver];
-  tree old_copy_of = copy_of[dest_ver].value;
+  tree old_first, old_last, new_last;
+  
+  /* Set FIRST to be the first link in COPY_OF[DEST].  If that
+     changed, return true.  */
+  old_first = copy_of[dest_ver].value;
+  copy_of[dest_ver].value = first;
+  copy_of[dest_ver].mem_ref = mem_ref;
 
-  copy_chains[dest_ver] = first;
-  copy_of[dest_ver].value = get_last_copy_of (first);
+  if (old_first != first)
+    return true;
 
-  return (old_first != first || old_copy_of != copy_of[dest_ver].value);
+  /* If FIRST and OLD_FIRST are the same, we need to check whether the
+     copy-of chain starting at FIRST ends in a different variable.  If
+     the copy-of chain starting at FIRST ends up in a different
+     variable than the last cached value we had for DEST, then return
+     true because DEST is now a copy of a different variable.
+
+     This test is necessary because even though the first link in the
+     copy-of chain may not have changed, if any of the variables in
+     the copy-of chain changed its final value, DEST will now be the
+     copy of a different variable, so we have to do another round of
+     propagation for everything that depends on DEST.  */
+  old_last = cached_last_copy_of[dest_ver];
+  new_last = get_last_copy_of (dest);
+  cached_last_copy_of[dest_ver] = new_last;
+
+  return (old_last != new_last);
 }
 
 
@@ -432,8 +466,8 @@ dump_copy_of (FILE *dump_file, tree var)
   val = var;
   print_generic_expr (dump_file, val, 0);
   fprintf (dump_file, " ");
-  while (copy_chains[SSA_NAME_VERSION (val)]
-         && copy_chains[SSA_NAME_VERSION (val)] != val)
+  while (copy_of[SSA_NAME_VERSION (val)].value
+         && copy_of[SSA_NAME_VERSION (val)].value != val)
     {
       fprintf (dump_file, "-> ");
       val = copy_of[SSA_NAME_VERSION (val)].value;
@@ -441,7 +475,7 @@ dump_copy_of (FILE *dump_file, tree var)
       fprintf (dump_file, " ");
     }
 
-  val = get_first_copy_of (var);
+  val = get_copy_of_val (var)->value;
   if (val == NULL_TREE)
     fprintf (dump_file, "[UNDEFINED]");
   else if (val != var)
@@ -472,27 +506,34 @@ copy_prop_visit_assignment (tree stmt, t
       /* Straight copy between to SSA names.  */
       *result_p = lhs;
 
-      if  (may_propagate_copy (*result_p, rhs))
-	{
-	  /* FIXME, some copy operations fail 'may_propagate_copy'
-	     because of the typecasts being stripped by
-	     tree_ssa_useless_type_conversion_1.  These type casts are
-	     removed even though the types are not compatible
-	     according to lang_hook.types_compatible_p.  */
-	  if (set_first_copy_of (*result_p, rhs))
-	    return SSA_PROP_INTERESTING;
-	  else
-	    return SSA_PROP_NOT_INTERESTING;
-	}
+      if (set_copy_of_val (*result_p, rhs, NULL_TREE))
+	return SSA_PROP_INTERESTING;
+      else
+	return SSA_PROP_NOT_INTERESTING;
     }
   else if (stmt_makes_single_store (stmt))
     {
-      /* Under certain conditions it may be possible to propagate
-	 copies into memory.  If this operation is a store, save the
-	 RHS into the V_MAY_DEF/V_MUST_DEF symbols on the LHS.  */
+      /* 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;
+
+      gcc_assert (do_store_copy_prop);
+
+      /* Set the value of every VDEF to VAL.  */
+      changed = false;
+      FOR_EACH_SSA_TREE_OPERAND (vdef, stmt, i, SSA_OP_VIRTUAL_DEFS)
+	changed |= set_copy_of_val (vdef, rhs, 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 (set_first_copy_of (*result_p, rhs))
+      if (changed)
 	return SSA_PROP_INTERESTING;
       else
 	return SSA_PROP_NOT_INTERESTING;
@@ -578,8 +619,8 @@ copy_prop_visit_stmt (tree stmt, edge *t
 
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
-      fprintf (dump_file, "\nVisiting statement: ");
-      print_generic_stmt (dump_file, stmt, TDF_SLIM);
+      fprintf (dump_file, "\nVisiting statement:\n");
+      print_generic_stmt (dump_file, stmt, dump_flags);
       fprintf (dump_file, "\n");
     }
 
@@ -617,7 +658,7 @@ copy_prop_visit_stmt (tree stmt, edge *t
 	 statement again and mark all the definitions in the statement
 	 to be copies of nothing.  */
       FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_ALL_DEFS)
-	set_first_copy_of (def, def);
+	set_copy_of_val (def, def, NULL_TREE);
     }
 
   return retval;
@@ -625,17 +666,18 @@ copy_prop_visit_stmt (tree stmt, edge *t
 
 
 /* Visit PHI node PHI.  If all the arguments produce the same value,
-   set the value of LHS.  */
+   set it to be the value of the LHS of PHI.  */
 
 static enum ssa_prop_result
 copy_prop_visit_phi_node (tree phi)
 {
   enum ssa_prop_result retval;
   int i;
-  tree lhs, phi_val;
+  tree lhs;
+  prop_value_t phi_val;
 
   lhs = PHI_RESULT (phi);
-  phi_val = get_first_copy_of (lhs);
+  phi_val = *(get_copy_of_val (lhs));
 
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
@@ -648,6 +690,7 @@ copy_prop_visit_phi_node (tree phi)
 
   for (i = 0; i < PHI_NUM_ARGS (phi); i++)
     {
+      prop_value_t *arg_val;
       tree arg = PHI_ARG_DEF (phi, i);
       edge e = PHI_ARG_EDGE (phi, i);
 
@@ -656,10 +699,14 @@ copy_prop_visit_phi_node (tree phi)
       if (!(e->flags & EDGE_EXECUTABLE))
 	continue;
 
-      /* Constants in the argument list never generate a useful copy.  */
-      if (TREE_CODE (arg) != SSA_NAME)
+      /* Constants in the argument list never generate a useful copy.
+	 Similarly, names that flow through abnormal edges cannot be
+	 used to derive copies.  */
+      if (TREE_CODE (arg) != SSA_NAME
+	  || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (arg))
 	{
-	  phi_val = lhs;
+	  phi_val.value = lhs;
+	  phi_val.mem_ref = NULL_TREE;
 	  break;
 	}
 
@@ -675,27 +722,35 @@ copy_prop_visit_phi_node (tree phi)
 	  fprintf (dump_file, "\n");
 	}
 
-      /* If the LHS didn't have a value yet, make it be a copy of the
+      arg_val = get_copy_of_val (arg);
+
+      /* If the LHS didn't have a value yet, make it a copy of the
 	 first argument we find.  */
-      if (phi_val == NULL_TREE)
-	phi_val = arg;
+      if (phi_val.value == NULL_TREE)
+	{
+	  phi_val.value = arg_val->value;
+	  phi_val.mem_ref = arg_val->mem_ref;
+	  continue;
+	}
 
       /* If PHI_VAL and ARG don't have a common copy-of chain, then
-	 this PHI node cannot be a copy operation.  */
-      if (get_last_copy_of (phi_val) != get_last_copy_of (arg))
+	 this PHI node cannot be a copy operation.  Also, if we are
+	 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_val->value)
+	  || (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 = lhs;
+	  phi_val.value = lhs;
 	  break;
 	}
     }
 
-  /* FIXME, see note regarding tree_ssa_useless_type_conversion_1 in
-     copy_prop_visit_assignment.  */
-  if (phi_val && !may_propagate_copy (lhs, phi_val))
-    phi_val = lhs;
-
-  if (phi_val && set_first_copy_of (lhs, phi_val))
-    retval = (phi_val != lhs) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING;
+  if (phi_val.value && set_copy_of_val (lhs, phi_val.value, phi_val.mem_ref))
+    retval = (phi_val.value != lhs) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING;
   else
     retval = SSA_PROP_NOT_INTERESTING;
 
@@ -724,12 +779,12 @@ init_copy_prop (void)
 {
   basic_block bb;
 
-  copy_chains = xmalloc (num_ssa_names * sizeof (*copy_chains));
-  memset (copy_chains, 0, num_ssa_names * sizeof (*copy_chains));
-
   copy_of = xmalloc (num_ssa_names * sizeof (*copy_of));
   memset (copy_of, 0, num_ssa_names * sizeof (*copy_of));
 
+  cached_last_copy_of = xmalloc (num_ssa_names * sizeof (*cached_last_copy_of));
+  memset (cached_last_copy_of, 0, num_ssa_names * sizeof (*cached_last_copy_of));
+
   FOR_EACH_BB (bb)
     {
       block_stmt_iterator si;
@@ -758,7 +813,7 @@ init_copy_prop (void)
 	      /* Mark all the outputs of this statement as not being
 		 the copy of anything.  */
 	      FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
-		set_first_copy_of (def, def);
+		set_copy_of_val (def, def, NULL_TREE);
 	    }
 	}
 
@@ -779,17 +834,18 @@ fini_copy_prop (void)
 {
   size_t i;
   
+  /* Set the final copy-of value for each variable by traversing the
+     copy-of chains.  */
   for (i = 1; i < num_ssa_names; i++)
     {
       tree var = ssa_name (i);
-      if (var && copy_chains[i] && copy_chains[i] != var)
+      if (var && copy_of[i].value && copy_of[i].value != var)
 	copy_of[i].value = get_last_copy_of (var);
     }
 
   substitute_and_fold (copy_of);
   cleanup_tree_cfg ();
 
-  free (copy_chains);
   free (copy_of);
 }
 
@@ -897,10 +953,9 @@ fini_copy_prop (void)
    x_53 and x_54 are both copies of x_898.  */
 
 void
-execute_copy_prop (void)
+execute_copy_prop (bool store_copy_prop)
 {
-  /* FIXME.  Add pass_store_copy_prop.  */
-  do_store_copy_prop = false;
+  do_store_copy_prop = store_copy_prop;
   init_copy_prop ();
   ssa_propagate (copy_prop_visit_stmt, copy_prop_visit_phi_node);
   fini_copy_prop ();
@@ -913,12 +968,17 @@ gate_copy_prop (void)
   return flag_tree_copy_prop != 0;
 }
 
+static void
+do_copy_prop (void)
+{
+  execute_copy_prop (false);
+}
 
 struct tree_opt_pass pass_copy_prop =
 {
   "copyprop",				/* name */
   gate_copy_prop,			/* gate */
-  execute_copy_prop,			/* execute */
+  do_copy_prop,				/* execute */
   NULL,					/* sub */
   NULL,					/* next */
   0,					/* static_pass_number */
@@ -933,3 +993,41 @@ struct tree_opt_pass pass_copy_prop =
     | TODO_rename_vars,			/* todo_flags_finish */
   0					/* letter */
 };
+
+
+static bool
+gate_store_copy_prop (void)
+{
+  /* STORE-COPY-PROP is enabled only with -ftree-store-copy-prop, but
+     when -fno-tree-store-copy-prop is specified, we should run
+     regular COPY-PROP. That's why the pass is enabled with either
+     flag.  */
+  return flag_tree_store_copy_prop != 0 || flag_tree_copy_prop != 0;
+}
+
+static void
+store_copy_prop (void)
+{
+  /* If STORE-COPY-PROP is not enabled, we just run regular COPY-PROP.  */
+  execute_copy_prop (flag_tree_store_copy_prop != 0);
+}
+
+struct tree_opt_pass pass_store_copy_prop =
+{
+  "store_copyprop",			/* name */
+  gate_store_copy_prop,			/* gate */
+  store_copy_prop,			/* execute */
+  NULL,					/* sub */
+  NULL,					/* next */
+  0,					/* static_pass_number */
+  TV_TREE_STORE_COPY_PROP,		/* tv_id */
+  PROP_ssa | PROP_alias | PROP_cfg,	/* properties_required */
+  0,					/* properties_provided */
+  0,					/* properties_destroyed */
+  0,					/* todo_flags_start */
+  TODO_dump_func
+    | TODO_ggc_collect
+    | TODO_verify_ssa
+    | TODO_rename_vars,			/* todo_flags_finish */
+  0					/* letter */
+};
Index: tree-ssa-propagate.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-propagate.c,v
retrieving revision 2.5.2.3
diff -d -c -p -u -r2.5.2.3 tree-ssa-propagate.c
--- tree-ssa-propagate.c	15 Oct 2004 03:19:42 -0000	2.5.2.3
+++ tree-ssa-propagate.c	19 Oct 2004 20:53:47 -0000
@@ -683,20 +683,6 @@ ssa_propagate (ssa_prop_visit_stmt_fn vi
 }
 
 
-/* Return the first VUSE or V_MAY_DEF operand for STMT.  */
-
-tree
-first_vuse (tree stmt)
-{
-  if (NUM_VUSES (STMT_VUSE_OPS (stmt)) > 0)
-    return VUSE_OP (STMT_VUSE_OPS (stmt), 0);
-  else if (NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) > 0)
-    return V_MAY_DEF_OP (STMT_V_MAY_DEF_OPS (stmt), 0);
-  else
-    gcc_unreachable ();
-}
-
-
 /* Return the first V_MAY_DEF or V_MUST_DEF operand for STMT.  */
 
 tree
@@ -762,4 +748,28 @@ stmt_makes_single_store (tree stmt)
 	      || TREE_CODE_CLASS (TREE_CODE (lhs)) == tcc_reference));
 }
 
+
+/* If STMT makes a single memory load and all the virtual use operands
+   have the same value in array VALUES, return it.  Otherwise, return
+   NULL.  */
+
+prop_value_t *
+get_value_loaded_by (tree stmt, prop_value_t *values)
+{
+  ssa_op_iter i;
+  tree vuse;
+  prop_value_t *prev_val = NULL;
+  prop_value_t *val = NULL;
+
+  FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, i, SSA_OP_VIRTUAL_USES)
+    {
+      val = &values[SSA_NAME_VERSION (vuse)];
+      if (prev_val && prev_val->value != val->value)
+	return NULL;
+      prev_val = val;
+    }
+
+  return val;
+}
+
 #include "gt-tree-ssa-propagate.h"
Index: tree-ssa-propagate.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-propagate.h,v
retrieving revision 2.2.8.3
diff -d -c -p -u -r2.2.8.3 tree-ssa-propagate.h
--- tree-ssa-propagate.h	15 Oct 2004 03:19:42 -0000	2.2.8.3
+++ tree-ssa-propagate.h	19 Oct 2004 20:53:47 -0000
@@ -60,9 +60,9 @@ typedef enum ssa_prop_result (*ssa_prop_
 void ssa_propagate (ssa_prop_visit_stmt_fn, ssa_prop_visit_phi_fn);
 tree get_rhs (tree);
 bool set_rhs (tree *, tree);
-tree first_vuse (tree);
 tree first_vdef (tree);
 bool stmt_makes_single_load (tree);
 bool stmt_makes_single_store (tree);
+prop_value_t *get_value_loaded_by (tree, prop_value_t *);
 
 #endif /* _TREE_SSA_PROPAGATE_H  */
Index: doc/invoke.texi
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doc/invoke.texi,v
retrieving revision 1.539.2.4
diff -d -c -p -u -r1.539.2.4 invoke.texi
--- doc/invoke.texi	15 Oct 2004 03:19:42 -0000	1.539.2.4
+++ doc/invoke.texi	19 Oct 2004 20:53:51 -0000
@@ -321,7 +321,7 @@ Objective-C and Objective-C++ Dialects}.
 -ftree-loop-linear -ftree-loop-im -ftree-loop-ivcanon -fivopts @gol
 -ftree-dominator-opts -ftree-dse -ftree-copyrename @gol
 -ftree-ch -ftree-sra -ftree-ter -ftree-lrs -ftree-fre -ftree-vectorize @gol
--ftree-copy-prop -ftree-store-ccp@gol
+-ftree-copy-prop -ftree-store-ccp -ftree-store-copy-prop @gol
 --param @var{name}=@var{value}
 -O  -O0  -O1  -O2  -O3  -Os}
 
@@ -3798,11 +3798,16 @@ by appending @file{.pre} to the source f
 Dump trees after full redundancy elimination.  The file name is made
 by appending @file{.fre} to the source file name.
 
-@item copy-prop
-@opindex fdump-tree-copy-prop
-Dump trees after expression propagation.  The file name is made
+@item copyprop
+@opindex fdump-tree-copyprop
+Dump trees after copy propagation.  The file name is made
 by appending @file{.copyprop} to the source file name.
 
+@item store_copyprop
+@opindex fdump-tree-store_copyprop
+Dump trees after store copy-propagation.  The file name is made
+by appending @file{.store_copyprop} to the source file name.
+
 @item dce
 @opindex fdump-tree-dce
 Dump each function after dead code elimination.  The file name is made by
@@ -4638,7 +4643,14 @@ This flag is enabled by default at @opti
 
 @item -ftree-copy-prop
 Perform copy propagation on trees.  This pass eliminates unnecessary
-copy operations.  This flag is enabled by default at -O and higher.
+copy operations.  This flag is enabled by default at @option{-O} and
+higher.
+
+@item -ftree-store-copy-prop
+Perform copy propagation of memory loads and stores.  This pass
+eliminates unnecessary copy operations in memory references
+(structures, global variables, arrays, etc).  This flag is enabled by
+default at @option{-O2} and higher.
 
 @item -ftree-ccp
 Perform sparse conditional constant propagation (CCP) on trees.  This
Index: testsuite/gcc.c-torture/execute/20041019-1.c
===================================================================
RCS file: testsuite/gcc.c-torture/execute/20041019-1.c
diff -N testsuite/gcc.c-torture/execute/20041019-1.c
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ testsuite/gcc.c-torture/execute/20041019-1.c	19 Oct 2004 20:53:54 -0000
@@ -0,0 +1,52 @@
+test_store_ccp (int i)
+{
+  int *p, a, b, c;
+
+  if (i < 5)
+    p = &a;
+  else if (i > 8)
+    p = &b;
+  else
+    p = &c;
+
+  *p = 10;
+  b = 3;
+
+  /* STORE-CCP was wrongfully propagating 10 into *p.  */
+  return *p + 2;
+}
+
+
+test_store_copy_prop (int i)
+{
+  int *p, a, b, c;
+
+  if (i < 5)
+    p = &a;
+  else if (i > 8)
+    p = &b;
+  else
+    p = &c;
+
+  *p = i;
+  b = i + 1;
+
+  /* STORE-COPY-PROP was wrongfully propagating i into *p.  */
+  return *p;
+}
+
+
+main()
+{
+  int x;
+  
+  x = test_store_ccp (10);
+  if (x == 12)
+    abort ();
+  
+  x = test_store_copy_prop (9);
+  if (x == 9)
+    abort ();
+
+  return 0;
+}


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]