tree-ssa-propagate.h (struct prop_value_d, [...]): Move ...

2010-08-04  Richard Guenther  <rguenther@suse.de>

	* tree-ssa-propagate.h (struct prop_value_d, prop_value_t): Move ...
	* tree-ssa-ccp.c: ... here.
	* tree-ssa-copy.c: ... and here.
	* tree-ssa-propagate.h (enum value_range_type, struct value_range_d, 
	value_range_t): Move ...
	* tree-vrp.c: ... here.
	* tree-ssa-propagate.h (ssa_prop_get_value_fn): New typedef.
	(substitute_and_fold): Adjust prototype.
	* tree-ssa-propagate.c (replace_uses_in): Adjust.
	(replace_phi_args_in): Likewise.
	(substitute_and_fold): Take callback to query lattice instead
	of pointer to lattice.  Replace SSA name defs with lattice
	values first.
	* tree-ssa-ccp.c (ccp_finalize): Adjust.
	* tree-ssa-copy.c (copy_prop_visit_phi_node): Adjust.
	(get_value): New function.
	(fini_copy_prop): Adjust.
	* tree-vrp.c (vrp_finalize): Adjust.

	* gcc.dg/tree-ssa/vrp35.c: Adjust.
	* gcc.dg/tree-ssa/vrp36.c: Likewise.
	* gcc.dg/tree-ssa/vrp50.c: Likewise.
	* gcc.dg/tree-ssa/vrp52.c: Likewise.

From-SVN: r162864

11 files changed, 169 insertions, 103 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index c9b88a9..77424eb 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,26 @@
 2010-08-04  Richard Guenther  <rguenther@suse.de>
 
+	* tree-ssa-propagate.h (struct prop_value_d, prop_value_t): Move ...
+	* tree-ssa-ccp.c: ... here.
+	* tree-ssa-copy.c: ... and here.
+	* tree-ssa-propagate.h (enum value_range_type, struct value_range_d, 
+	value_range_t): Move ...
+	* tree-vrp.c: ... here.
+	* tree-ssa-propagate.h (ssa_prop_get_value_fn): New typedef.
+	(substitute_and_fold): Adjust prototype.
+	* tree-ssa-propagate.c (replace_uses_in): Adjust.
+	(replace_phi_args_in): Likewise.
+	(substitute_and_fold): Take callback to query lattice instead
+	of pointer to lattice.  Replace SSA name defs with lattice
+	values first.
+	* tree-ssa-ccp.c (ccp_finalize): Adjust.
+	* tree-ssa-copy.c (copy_prop_visit_phi_node): Adjust.
+	(get_value): New function.
+	(fini_copy_prop): Adjust.
+	* tree-vrp.c (vrp_finalize): Adjust.
+
+2010-08-04  Richard Guenther  <rguenther@suse.de>
+
 	PR middle-end/45176
 	* expr.c (expand_expr_real_1): Also preserve TARGET_MEM_REF
 	points-to set for original MEM_REF.
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index b7ef5ed..90dee6b 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,10 @@
+2010-08-04  Richard Guenther  <rguenther@suse.de>
+
+	* gcc.dg/tree-ssa/vrp35.c: Adjust.
+	* gcc.dg/tree-ssa/vrp36.c: Likewise.
+	* gcc.dg/tree-ssa/vrp50.c: Likewise.
+	* gcc.dg/tree-ssa/vrp52.c: Likewise.
+
 2010-08-04  Tobias Burnus  <burnus@net-b.de>
 
 	PR fortran/44857
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp35.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp35.c
index 06b567d..6402f4d 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/vrp35.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp35.c
@@ -11,5 +11,5 @@ int test1(int i, int k)
   return 1;
 }
 
-/* { dg-final { scan-tree-dump "Folding predicate j_.* == 10 to 0" "vrp1" } } */
+/* { dg-final { scan-tree-dump-not "j_.* == 10" "vrp1" } } */
 /* { dg-final { cleanup-tree-dump "vrp1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp36.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp36.c
index 9d61960..de300d7 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/vrp36.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp36.c
@@ -8,5 +8,5 @@ int foo(int i)
   return 1;
 }
 
-/* { dg-final { scan-tree-dump "Folding predicate i_.* == 1 to 0" "vrp1" } } */
+/* { dg-final { scan-tree-dump-not "i_.* == 1" "vrp1" } } */
 /* { dg-final { cleanup-tree-dump "vrp1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp50.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp50.c
index bf21672..a5b3ee2 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/vrp50.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp50.c
@@ -30,7 +30,5 @@ int baz (int x, int y)
   return x < 20;
 }
 
-/* { dg-final { scan-tree-dump "Folding predicate i_\[^\n\r\]* to 1" "vrp1" } } */
-/* { dg-final { scan-tree-dump "Folding predicate c_\[^\n\r\]* to 1" "vrp1" } } */
-/* { dg-final { scan-tree-dump "Folding predicate x_\[^\n\r\]* to 1" "vrp1" } } */
+/* { dg-final { scan-tree-dump-times "return 1;" 3 "vrp1" } } */
 /* { dg-final { cleanup-tree-dump "vrp1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp52.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp52.c
index 7d530e2..231d081 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/vrp52.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp52.c
@@ -12,5 +12,5 @@ foo (unsigned int i, unsigned int j)
   return i >= 1024 + 2048;
 }
 
-/* { dg-final { scan-tree-dump "Folding predicate i_\[^\n\r\]* to 1" "vrp1" } } */
+/* { dg-final { scan-tree-dump-times "return 1;" 1 "vrp1" } } */
 /* { dg-final { cleanup-tree-dump "vrp1" } } */
diff --git a/gcc/tree-ssa-ccp.c b/gcc/tree-ssa-ccp.c
index 830a0e4..7d5f1a9 100644
--- a/gcc/tree-ssa-ccp.c
+++ b/gcc/tree-ssa-ccp.c
@@ -144,6 +144,16 @@ typedef enum
   VARYING
 } ccp_lattice_t;
 
+struct prop_value_d {
+    /* Lattice value.  */
+    ccp_lattice_t lattice_val;
+
+    /* Propagated value.  */
+    tree value;
+};
+
+typedef struct prop_value_d prop_value_t;
+
 /* Array of propagated constant values.  After propagation,
    CONST_VAL[I].VALUE holds the constant value for SSA_NAME(I).  If
    the constant is held in an SSA name representing a memory store
@@ -645,7 +655,8 @@ ccp_finalize (void)
 
   do_dbg_cnt ();
   /* Perform substitutions based on the known constant values.  */
-  something_changed = substitute_and_fold (const_val, ccp_fold_stmt, true);
+  something_changed = substitute_and_fold (get_constant_value,
+					   ccp_fold_stmt, true);
 
   free (const_val);
   const_val = NULL;
diff --git a/gcc/tree-ssa-copy.c b/gcc/tree-ssa-copy.c
index 87d8968..767e183 100644
--- a/gcc/tree-ssa-copy.c
+++ b/gcc/tree-ssa-copy.c
@@ -285,6 +285,14 @@ propagate_tree_value_into_stmt (gimple_stmt_iterator *gsi, tree val)
    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.  */
+
+struct prop_value_d {
+    /* Copy-of value.  */
+    tree value;
+};
+
+typedef struct prop_value_d prop_value_t;
+
 static prop_value_t *copy_of;
 
 /* Used in set_copy_of_val to determine if the last link of a copy-of
@@ -626,7 +634,7 @@ copy_prop_visit_phi_node (gimple phi)
 {
   enum ssa_prop_result retval;
   unsigned i;
-  prop_value_t phi_val = { 0, NULL_TREE };
+  prop_value_t phi_val = { NULL_TREE };
 
   tree lhs = gimple_phi_result (phi);
 
@@ -818,6 +826,16 @@ init_copy_prop (void)
     }
 }
 
+/* Callback for substitute_and_fold to get at the final copy-of values.  */
+
+static tree
+get_value (tree name)
+{
+  tree val = copy_of[SSA_NAME_VERSION (name)].value;
+  if (val && val != name)
+    return val;
+  return NULL_TREE;
+}
 
 /* Deallocate memory used in copy propagation and do final
    substitution.  */
@@ -825,12 +843,10 @@ init_copy_prop (void)
 static void
 fini_copy_prop (void)
 {
-  size_t i;
-  prop_value_t *tmp;
+  unsigned i;
 
   /* Set the final copy-of value for each variable by traversing the
      copy-of chains.  */
-  tmp = XCNEWVEC (prop_value_t, num_ssa_names);
   for (i = 1; i < num_ssa_names; i++)
     {
       tree var = ssa_name (i);
@@ -839,7 +855,7 @@ fini_copy_prop (void)
 	  || copy_of[i].value == var)
 	continue;
 
-      tmp[i].value = get_last_copy_of (var);
+      copy_of[i].value = get_last_copy_of (var);
 
       /* In theory the points-to solution of all members of the
          copy chain is their intersection.  For now we do not bother
@@ -847,18 +863,17 @@ fini_copy_prop (void)
 	 information completely by setting the points-to solution
 	 of the representative to the first solution we find if
 	 it doesn't have one already.  */
-      if (tmp[i].value != var
+      if (copy_of[i].value != var
 	  && POINTER_TYPE_P (TREE_TYPE (var))
 	  && SSA_NAME_PTR_INFO (var)
-	  && !SSA_NAME_PTR_INFO (tmp[i].value))
-	duplicate_ssa_name_ptr_info (tmp[i].value, SSA_NAME_PTR_INFO (var));
+	  && !SSA_NAME_PTR_INFO (copy_of[i].value))
+	duplicate_ssa_name_ptr_info (copy_of[i].value, SSA_NAME_PTR_INFO (var));
     }
 
-  substitute_and_fold (tmp, NULL, true);
+  substitute_and_fold (get_value, NULL, true);
 
   free (cached_last_copy_of);
   free (copy_of);
-  free (tmp);
 }
 
 
diff --git a/gcc/tree-ssa-propagate.c b/gcc/tree-ssa-propagate.c
index 6f50fc5..e08d2e7 100644
--- a/gcc/tree-ssa-propagate.c
+++ b/gcc/tree-ssa-propagate.c
@@ -872,7 +872,7 @@ static struct prop_stats_d prop_stats;
    PROP_VALUE. Return true if at least one reference was replaced.  */
 
 static bool
-replace_uses_in (gimple stmt, prop_value_t *prop_value)
+replace_uses_in (gimple stmt, ssa_prop_get_value_fn get_value)
 {
   bool replaced = false;
   use_operand_p use;
@@ -881,7 +881,7 @@ replace_uses_in (gimple stmt, prop_value_t *prop_value)
   FOR_EACH_SSA_USE_OPERAND (use, stmt, iter, SSA_OP_USE)
     {
       tree tuse = USE_FROM_PTR (use);
-      tree val = prop_value[SSA_NAME_VERSION (tuse)].value;
+      tree val = (*get_value) (tuse);
 
       if (val == tuse || val == NULL_TREE)
 	continue;
@@ -911,7 +911,7 @@ replace_uses_in (gimple stmt, prop_value_t *prop_value)
    values from PROP_VALUE.  */
 
 static void
-replace_phi_args_in (gimple phi, prop_value_t *prop_value)
+replace_phi_args_in (gimple phi, ssa_prop_get_value_fn get_value)
 {
   size_t i;
   bool replaced = false;
@@ -928,7 +928,7 @@ replace_phi_args_in (gimple phi, prop_value_t *prop_value)
 
       if (TREE_CODE (arg) == SSA_NAME)
 	{
-	  tree val = prop_value[SSA_NAME_VERSION (arg)].value;
+	  tree val = (*get_value) (arg);
 
 	  if (val && val != arg && may_propagate_copy (arg, val))
 	    {
@@ -978,13 +978,15 @@ replace_phi_args_in (gimple phi, prop_value_t *prop_value)
    Return TRUE when something changed.  */
 
 bool
-substitute_and_fold (prop_value_t *prop_value, ssa_prop_fold_stmt_fn fold_fn,
+substitute_and_fold (ssa_prop_get_value_fn get_value_fn,
+		     ssa_prop_fold_stmt_fn fold_fn,
 		     bool do_dce)
 {
   basic_block bb;
   bool something_changed = false;
+  unsigned i;
 
-  if (prop_value == NULL && !fold_fn)
+  if (!get_value_fn && !fold_fn)
     return false;
 
   if (dump_file && (dump_flags & TDF_DETAILS))
@@ -992,15 +994,66 @@ substitute_and_fold (prop_value_t *prop_value, ssa_prop_fold_stmt_fn fold_fn,
 
   memset (&prop_stats, 0, sizeof (prop_stats));
 
-  /* Substitute values in every statement of every basic block.  */
+  /* Substitute lattice values at definition sites.  */
+  if (get_value_fn)
+    for (i = 1; i < num_ssa_names; ++i)
+      {
+	tree name = ssa_name (i);
+	tree val;
+	gimple def_stmt;
+	gimple_stmt_iterator gsi;
+
+	if (!name
+	    || !is_gimple_reg (name))
+	  continue;
+
+	def_stmt = SSA_NAME_DEF_STMT (name);
+	if (gimple_nop_p (def_stmt)
+	    /* Do not substitute ASSERT_EXPR rhs, this will confuse VRP.  */
+	    || (gimple_assign_single_p (def_stmt)
+		&& gimple_assign_rhs_code (def_stmt) == ASSERT_EXPR)
+	    || !(val = (*get_value_fn) (name))
+	    || !may_propagate_copy (name, val))
+	  continue;
+
+	gsi = gsi_for_stmt (def_stmt);
+	if (is_gimple_assign (def_stmt))
+	  {
+	    gimple_assign_set_rhs_with_ops (&gsi, TREE_CODE (val),
+					    val, NULL_TREE);
+	    gcc_assert (gsi_stmt (gsi) == def_stmt);
+	    if (maybe_clean_eh_stmt (def_stmt))
+	      gimple_purge_dead_eh_edges (gimple_bb (def_stmt));
+	    update_stmt (def_stmt);
+	  }
+	else if (is_gimple_call (def_stmt))
+	  {
+	    if (update_call_from_tree (&gsi, val)
+		&& maybe_clean_or_replace_eh_stmt (def_stmt, gsi_stmt (gsi)))
+	      gimple_purge_dead_eh_edges (gimple_bb (gsi_stmt (gsi)));
+	  }
+	else if (gimple_code (def_stmt) == GIMPLE_PHI)
+	  {
+	    gimple new_stmt = gimple_build_assign (name, val);
+	    gimple_stmt_iterator gsi2;
+	    SSA_NAME_DEF_STMT (name) = new_stmt;
+	    gsi2 = gsi_after_labels (gimple_bb (def_stmt));
+	    gsi_insert_before (&gsi2, new_stmt, GSI_SAME_STMT);
+	    remove_phi_node (&gsi, false);
+	  }
+
+	something_changed = true;
+      }
+
+  /* Propagate into all uses and fold.  */
   FOR_EACH_BB (bb)
     {
       gimple_stmt_iterator i;
 
       /* Propagate known values into PHI nodes.  */
-      if (prop_value)
+      if (get_value_fn)
 	for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (&i))
-	  replace_phi_args_in (gsi_stmt (i), prop_value);
+	  replace_phi_args_in (gsi_stmt (i), get_value_fn);
 
       /* Propagate known values into stmts.  Do a backward walk to expose
 	 more trivially deletable stmts.  */
@@ -1073,9 +1126,9 @@ substitute_and_fold (prop_value_t *prop_value, ssa_prop_fold_stmt_fn fold_fn,
 
 	  /* Only replace real uses if we couldn't fold the
 	     statement using value range information.  */
-	  if (prop_value
+	  if (get_value_fn
 	      && !did_replace)
-	    did_replace |= replace_uses_in (stmt, prop_value);
+	    did_replace |= replace_uses_in (stmt, get_value_fn);
 
 	  /* If we made a replacement, fold the statement.  */
 	  if (did_replace)
diff --git a/gcc/tree-ssa-propagate.h b/gcc/tree-ssa-propagate.h
index c5bb973..778f650 100644
--- a/gcc/tree-ssa-propagate.h
+++ b/gcc/tree-ssa-propagate.h
@@ -61,56 +61,11 @@ enum ssa_prop_result {
 };
 
 
-struct prop_value_d {
-    /* Lattice value.  Each propagator is free to define its own
-       lattice and this field is only meaningful while propagating.
-       It will not be used by substitute_and_fold.  */
-    unsigned lattice_val;
-
-    /* Propagated value.  */
-    tree value;
-};
-
-typedef struct prop_value_d prop_value_t;
-
-
-/* Type of value ranges.  See value_range_d for a description of these
-   types.  */
-enum value_range_type { VR_UNDEFINED, VR_RANGE, VR_ANTI_RANGE, VR_VARYING };
-
-/* Range of values that can be associated with an SSA_NAME after VRP
-   has executed.  */
-struct value_range_d
-{
-  /* Lattice value represented by this range.  */
-  enum value_range_type type;
-
-  /* Minimum and maximum values represented by this range.  These
-     values should be interpreted as follows:
-
-	- If TYPE is VR_UNDEFINED or VR_VARYING then MIN and MAX must
-	  be NULL.
-
-	- If TYPE == VR_RANGE then MIN holds the minimum value and
-	  MAX holds the maximum value of the range [MIN, MAX].
-
-	- If TYPE == ANTI_RANGE the variable is known to NOT
-	  take any values in the range [MIN, MAX].  */
-  tree min;
-  tree max;
-
-  /* Set of SSA names whose value ranges are equivalent to this one.
-     This set is only valid when TYPE is VR_RANGE or VR_ANTI_RANGE.  */
-  bitmap equiv;
-};
-
-typedef struct value_range_d value_range_t;
-
-
 /* Call-back functions used by the value propagation engine.  */
 typedef enum ssa_prop_result (*ssa_prop_visit_stmt_fn) (gimple, edge *, tree *);
 typedef enum ssa_prop_result (*ssa_prop_visit_phi_fn) (gimple);
 typedef bool (*ssa_prop_fold_stmt_fn) (gimple_stmt_iterator *gsi);
+typedef tree (*ssa_prop_get_value_fn) (tree);
 
 
 /* In tree-ssa-propagate.c  */
@@ -119,6 +74,6 @@ bool valid_gimple_rhs_p (tree);
 void move_ssa_defining_stmt_for_defs (gimple, gimple);
 bool update_call_from_tree (gimple_stmt_iterator *, tree);
 bool stmt_makes_single_store (gimple);
-bool substitute_and_fold (prop_value_t *, ssa_prop_fold_stmt_fn, bool);
+bool substitute_and_fold (ssa_prop_get_value_fn, ssa_prop_fold_stmt_fn, bool);
 
 #endif /* _TREE_SSA_PROPAGATE_H  */
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 05fa186..35d12b3 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -42,6 +42,38 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-chrec.h"
 
 
+/* Type of value ranges.  See value_range_d for a description of these
+   types.  */
+enum value_range_type { VR_UNDEFINED, VR_RANGE, VR_ANTI_RANGE, VR_VARYING };
+
+/* Range of values that can be associated with an SSA_NAME after VRP
+   has executed.  */
+struct value_range_d
+{
+  /* Lattice value represented by this range.  */
+  enum value_range_type type;
+
+  /* Minimum and maximum values represented by this range.  These
+     values should be interpreted as follows:
+
+	- If TYPE is VR_UNDEFINED or VR_VARYING then MIN and MAX must
+	  be NULL.
+
+	- If TYPE == VR_RANGE then MIN holds the minimum value and
+	  MAX holds the maximum value of the range [MIN, MAX].
+
+	- If TYPE == ANTI_RANGE the variable is known to NOT
+	  take any values in the range [MIN, MAX].  */
+  tree min;
+  tree max;
+
+  /* Set of SSA names whose value ranges are equivalent to this one.
+     This set is only valid when TYPE is VR_RANGE or VR_ANTI_RANGE.  */
+  bitmap equiv;
+};
+
+typedef struct value_range_d value_range_t;
+
 /* Set of SSA names found live during the RPO traversal of the function
    for still active basic-blocks.  */
 static sbitmap *live;
@@ -7526,8 +7558,6 @@ static void
 vrp_finalize (void)
 {
   size_t i;
-  prop_value_t *single_val_range;
-  bool do_value_subst_p;
   unsigned num = num_ssa_names;
 
   if (dump_file)
@@ -7537,31 +7567,8 @@ vrp_finalize (void)
       fprintf (dump_file, "\n");
     }
 
-  /* We may have ended with ranges that have exactly one value.  Those
-     values can be substituted as any other const propagated
-     value using substitute_and_fold.  */
-  single_val_range = XCNEWVEC (prop_value_t, num);
-
-  do_value_subst_p = false;
-  for (i = 0; i < num; i++)
-    if (vr_value[i]
-	&& vr_value[i]->type == VR_RANGE
-	&& vr_value[i]->min == vr_value[i]->max
-	&& is_gimple_min_invariant (vr_value[i]->min))
-      {
-	single_val_range[i].value = vr_value[i]->min;
-	do_value_subst_p = true;
-      }
-
-  if (!do_value_subst_p)
-    {
-      /* We found no single-valued ranges, don't waste time trying to
-	 do single value substitution in substitute_and_fold.  */
-      free (single_val_range);
-      single_val_range = NULL;
-    }
-
-  substitute_and_fold (single_val_range, vrp_fold_stmt, false);
+  substitute_and_fold (op_with_constant_singleton_value_range,
+		       vrp_fold_stmt, false);
 
   if (warn_array_bounds)
     check_all_array_refs ();
@@ -7578,7 +7585,6 @@ vrp_finalize (void)
 	free (vr_value[i]);
       }
 
-  free (single_val_range);
   free (vr_value);
   free (vr_phi_edge_counts);