* common.opt (ftree-fre): New flag.

	* flags.h (flag_tree_fre): Declare.
	* opts.c (decode_options): Set.
	* timevar.def (TV_TREE_FRE): Define.
	* tree-flow-inline.h (may_propagate_copy): Re-arrange for
	readability.  Handle destinations that are not SSA_NAMEs.
	* tree-flow.h (struct ptr_info_def): Move from tree.h
	(cprop_into_stmt, cprop_into_successor_phis): Remove.
	(vn_compute, vn_lookup_or_add, vn_add, vn_lookup): Add
	vuse_optype parameter.
	* tree-pass.h (pass_fre): Declare.
	* tree-ssa-copy.c (cprop_operand): Move to tree-ssa-dom.c
	(cprop_into_stmt): Likewise.
	(cprop_into_successor_phis): Likewise.
	* tree-ssa-dom.c (eliminate_redundant_computations): Fix
	argument ordering in call to may_propagate_copy.
	* tree-ssa-pre.c (is_undefined_value): Assume hard registers
	to be always defined.
	(add_to_sets): New local function.
	(create_value_expr_from): New local function.
	(compute_avail): Call them.
	(eliminate): Don't ignore statements with virtual operands.
	(init_pre): New local function.
	(fini_pre): New local function.
	(execute_pre): Call them.
	Add argument DO_FRE.  Don't do insertion if DO_FRE is true.
	(do_pre): New function.
	(do_fre): New function.
	(gate_fre): New function.
	(pass_fre): Declare.
	* tree-ssa.c (init_tree_ssa): Don't call vn_init.
	(delete_tree_ssa): Don't call vn_delete.
	* tree-vn.c (val_expr_pair_d): Add documentation.
	(vn_compute): Add VUSES argument to incorporate in computing
	hash values.  Update all callers.
	(expressions_equal_p): Call operand_equal_p with
	OEP_PURE_SAME.
	(vn_add): Add VUSES argument.  Update all callers.
	(vn_lookup): Likewise.
	(vn_lookup_or_add): Likewise.
	* doc/invoke.texi: Document -ftree-fre and -fdump-tree-fre.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@83837 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 240 insertions, 7 deletions

diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c
index eadef0d41b8..28780747736 100644
--- a/gcc/tree-ssa-dom.c
+++ b/gcc/tree-ssa-dom.c
@@ -529,14 +529,9 @@ redirect_edges_and_update_ssa_graph (varray_type redirection_edges)
 
 /* Jump threading, redundancy elimination and const/copy propagation. 
 
-   Optimize function FNDECL based on a walk through the dominator tree.
-
    This pass may expose new symbols that need to be renamed into SSA.  For
    every new symbol exposed, its corresponding bit will be set in
-   VARS_TO_RENAME.
-
-   PHASE indicates which dump file from the DUMP_FILES array to use when
-   dumping debugging information.  */
+   VARS_TO_RENAME.  */
 
 static void
 tree_ssa_dominator_optimize (void)
@@ -2453,6 +2448,107 @@ simplify_switch_and_lookup_avail_expr (tree stmt,
   return 0;
 }
 
+
+/* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
+   known value for that SSA_NAME (or NULL if no value is known).  
+
+   NONZERO_VARS is the set SSA_NAMES known to have a nonzero value,
+   even if we don't know their precise value.
+
+   Propagate values from CONST_AND_COPIES and NONZERO_VARS into the PHI
+   nodes of the successors of BB.  */
+
+static void
+cprop_into_successor_phis (basic_block bb,
+			   varray_type const_and_copies,
+			   bitmap nonzero_vars)
+{
+  edge e;
+
+  /* This can get rather expensive if the implementation is naive in
+     how it finds the phi alternative associated with a particular edge.  */
+  for (e = bb->succ; e; e = e->succ_next)
+    {
+      tree phi;
+      int phi_num_args;
+      int hint;
+
+      /* If this is an abnormal edge, then we do not want to copy propagate
+	 into the PHI alternative associated with this edge.  */
+      if (e->flags & EDGE_ABNORMAL)
+	continue;
+
+      phi = phi_nodes (e->dest);
+      if (! phi)
+	continue;
+
+      /* There is no guarantee that for any two PHI nodes in a block that
+	 the phi alternative associated with a particular edge will be
+	 at the same index in the phi alternative array.
+
+	 However, it is very likely they will be the same.  So we keep
+	 track of the index of the alternative where we found the edge in
+	 the previous phi node and check that index first in the next
+	 phi node.  If that hint fails, then we actually search all
+	 the entries.  */
+      phi_num_args = PHI_NUM_ARGS (phi);
+      hint = phi_num_args;
+      for ( ; phi; phi = PHI_CHAIN (phi))
+	{
+	  int i;
+	  tree new;
+	  use_operand_p orig_p;
+	  tree orig;
+
+	  /* If the hint is valid (!= phi_num_args), see if it points
+	     us to the desired phi alternative.  */
+	  if (hint != phi_num_args && PHI_ARG_EDGE (phi, hint) == e)
+	    ;
+	  else
+	    {
+	      /* The hint was either invalid or did not point to the
+		 correct phi alternative.  Search all the alternatives
+		 for the correct one.  Update the hint.  */
+	      for (i = 0; i < phi_num_args; i++)
+		if (PHI_ARG_EDGE (phi, i) == e)
+		  break;
+	      hint = i;
+	    }
+
+#ifdef ENABLE_CHECKING
+	  /* If we did not find the proper alternative, then something is
+	     horribly wrong.  */
+	  if (hint == phi_num_args)
+	    abort ();
+#endif
+
+	  /* The alternative may be associated with a constant, so verify
+	     it is an SSA_NAME before doing anything with it.  */
+	  orig_p = PHI_ARG_DEF_PTR (phi, hint);
+	  orig = USE_FROM_PTR (orig_p);
+	  if (TREE_CODE (orig) != SSA_NAME)
+	    continue;
+
+	  /* If the alternative is known to have a nonzero value, record
+	     that fact in the PHI node itself for future use.  */
+	  if (bitmap_bit_p (nonzero_vars, SSA_NAME_VERSION (orig)))
+	    PHI_ARG_NONZERO (phi, hint) = true;
+
+	  /* If we have *ORIG_P in our constant/copy table, then replace
+	     ORIG_P with its value in our constant/copy table.  */
+	  new = VARRAY_TREE (const_and_copies, SSA_NAME_VERSION (orig));
+	  if (new
+	      && (TREE_CODE (new) == SSA_NAME
+		  || is_gimple_min_invariant (new))
+	      && may_propagate_copy (orig, new))
+	    {
+	      propagate_value (orig_p, new);
+	    }
+	}
+    }
+}
+
+
 /* Propagate known constants/copies into PHI nodes of BB's successor
    blocks.  */
 
@@ -2538,7 +2634,7 @@ eliminate_redundant_computations (struct dom_walk_data *walk_data,
      CACHED_LHS into *EXPR_P.  */
   if (cached_lhs
       && (TREE_CODE (cached_lhs) != SSA_NAME
-	  || may_propagate_copy (cached_lhs, *expr_p)))
+	  || may_propagate_copy (*expr_p, cached_lhs)))
     {
       if (dump_file && (dump_flags & TDF_DETAILS))
 	{
@@ -2736,6 +2832,143 @@ record_equivalences_from_stmt (tree stmt,
     }
 }
 
+/* Replace *OP_P in STMT with any known equivalent value for *OP_P from
+   CONST_AND_COPIES.  */
+
+static bool
+cprop_operand (stmt_ann_t ann, use_operand_p op_p, varray_type const_and_copies)
+{
+  bool may_have_exposed_new_symbols = false;
+  tree val;
+  tree op = USE_FROM_PTR (op_p);
+
+  /* If the operand has a known constant value or it is known to be a
+     copy of some other variable, use the value or copy stored in
+     CONST_AND_COPIES.  */
+  val = VARRAY_TREE (const_and_copies, SSA_NAME_VERSION (op));
+  if (val)
+    {
+      tree op_type, val_type;
+
+      /* Do not change the base variable in the virtual operand
+	 tables.  That would make it impossible to reconstruct
+	 the renamed virtual operand if we later modify this
+	 statement.  Also only allow the new value to be an SSA_NAME
+	 for propagation into virtual operands.  */
+      if (!is_gimple_reg (op)
+	  && (get_virtual_var (val) != get_virtual_var (op)
+	      || TREE_CODE (val) != SSA_NAME))
+	return false;
+
+      /* Get the toplevel type of each operand.  */
+      op_type = TREE_TYPE (op);
+      val_type = TREE_TYPE (val);
+
+      /* While both types are pointers, get the type of the object
+	 pointed to.  */
+      while (POINTER_TYPE_P (op_type) && POINTER_TYPE_P (val_type))
+	{
+	  op_type = TREE_TYPE (op_type);
+	  val_type = TREE_TYPE (val_type);
+	}
+
+      /* Make sure underlying types match before propagating a
+	 constant by converting the constant to the proper type.  Note
+	 that convert may return a non-gimple expression, in which case
+	 we ignore this propagation opportunity.  */
+     if (!lang_hooks.types_compatible_p (op_type, val_type)
+           && TREE_CODE (val) != SSA_NAME)
+	{
+	  val = fold_convert (TREE_TYPE (op), val);
+	  if (!is_gimple_min_invariant (val)
+	      && TREE_CODE (val) != SSA_NAME)
+	    return false;
+	}
+
+      /* Certain operands are not allowed to be copy propagated due
+	 to their interaction with exception handling and some GCC
+	 extensions.  */
+      if (TREE_CODE (val) == SSA_NAME
+	  && !may_propagate_copy (op, val))
+	return false;
+
+      /* Dump details.  */
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file, "  Replaced '");
+	  print_generic_expr (dump_file, op, dump_flags);
+	  fprintf (dump_file, "' with %s '",
+		   (TREE_CODE (val) != SSA_NAME ? "constant" : "variable"));
+	  print_generic_expr (dump_file, val, dump_flags);
+	  fprintf (dump_file, "'\n");
+	}
+
+      /* If VAL is an ADDR_EXPR or a constant of pointer type, note
+	 that we may have exposed a new symbol for SSA renaming.  */
+      if (TREE_CODE (val) == ADDR_EXPR
+	  || (POINTER_TYPE_P (TREE_TYPE (op))
+	      && is_gimple_min_invariant (val)))
+	may_have_exposed_new_symbols = true;
+
+      propagate_value (op_p, val);
+
+      /* And note that we modified this statement.  This is now
+	 safe, even if we changed virtual operands since we will
+	 rescan the statement and rewrite its operands again.  */
+      ann->modified = 1;
+    }
+  return may_have_exposed_new_symbols;
+}
+
+/* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
+   known value for that SSA_NAME (or NULL if no value is known).  
+
+   Propagate values from CONST_AND_COPIES into the uses, vuses and
+   v_may_def_ops of STMT.  */
+
+static bool
+cprop_into_stmt (tree stmt, varray_type const_and_copies)
+{
+  bool may_have_exposed_new_symbols = false;
+  stmt_ann_t ann = stmt_ann (stmt);
+  size_t i, num_uses, num_vuses, num_v_may_defs;
+  vuse_optype vuses;
+  v_may_def_optype v_may_defs;
+  use_optype uses;
+
+  uses = USE_OPS (ann);
+  num_uses = NUM_USES (uses);
+  for (i = 0; i < num_uses; i++)
+    {
+      use_operand_p op_p = USE_OP_PTR (uses, i);
+      if (TREE_CODE (USE_FROM_PTR (op_p)) == SSA_NAME)
+	may_have_exposed_new_symbols
+	  |= cprop_operand (ann, op_p, const_and_copies);
+    }
+
+  vuses = VUSE_OPS (ann);
+  num_vuses = NUM_VUSES (vuses);
+  for (i = 0; i < num_vuses; i++)
+    {
+      use_operand_p op_p = VUSE_OP_PTR (vuses, i);
+      if (TREE_CODE (USE_FROM_PTR (op_p)) == SSA_NAME)
+	may_have_exposed_new_symbols
+	  |= cprop_operand (ann, op_p, const_and_copies);
+    }
+
+  v_may_defs = V_MAY_DEF_OPS (ann);
+  num_v_may_defs = NUM_V_MAY_DEFS (v_may_defs);
+  for (i = 0; i < num_v_may_defs; i++)
+    {
+      use_operand_p op_p = V_MAY_DEF_OP_PTR (v_may_defs, i);
+      if (TREE_CODE (USE_FROM_PTR (op_p)) == SSA_NAME)
+	may_have_exposed_new_symbols
+	  |= cprop_operand (ann, op_p, const_and_copies);
+    }
+  return may_have_exposed_new_symbols;
+}
+
+
 /* Optimize the statement pointed by iterator SI.
    
    We try to perform some simplistic global redundancy elimination and