2005-06-01 Diego Novillo <dnovillo@redhat.com>

	PR 14341, PR 21332, PR 20701, PR 21029, PR 21086, PR 21090
	PR 21289, PR 21348, PR 21367, PR 21368, PR 21458.
	* fold-const.c (invert_tree_comparison): Make extern.
	* tree-flow.h (enum value_range_type): Move to tree-ssa-propagate.
	(struct value_range_def): Limewise.
	(get_value_range): Remove.
	(dump_value_range): Remove.
	(dump_all_value_ranges): Remove.
	(debug_all_value_ranges): Remove.
	(vrp_evaluate_conditional): Declare.
	* tree-ssa-propagate.c (struct prop_stats_d): Add field
	num_pred_folded.
	(substitute_and_fold): Add argument use_ranges_p.
	Update all callers.
	If use_ranges_p is true, call fold_predicate_in to fold
	predicates using range information.
	Ignore ASSERT_EXPRs.
	Change debugging output to only show statements that have been
	folded.
	(replace_phi_args_in): Move debugging output code from
	substitute and fold.
	(fold_predicate_in): New local function.
	* tree-ssa-propagate.h (enum value_range_type): Move from
	tree-flow.h.
	(struct value_range_d): Likewise.
	Add field 'equiv'.
	(value_range_t): Rename from value_range.
	* tree-vrp.c (found_in_subgraph): Rename from found.
	(get_opposite_operand): Remove.
	(struct assert_locus_d): Declare.
	(assert_locus_t): Declare.
	(need_assert_for): Declare.
	(asserts_for): Declare.
	(blocks_visited): Declare.
	(vr_value): Declare.
	(set_value_range): Add argument 'equiv'.
	Don't drop to VARYING ranges that cover all values in the
	type.
	Make deep copy of equivalence set 'equiv'.
	(copy_value_range): New local function.
	(set_value_range_to_undefined): New local function.
	(compare_values): Return -2 if either value has overflowed.
	(range_includes_zero_p): New local function.
	(extract_range_from_assert): Flip the predicate code if the
	name being asserted is on the RHS of the predicate.
	Avoid creating unnecessary symbolic ranges if the comparison
	includes another name with a known numeric range.
	Update the equivalnce set of the new range when asserting
	EQ_EXPR predicates.
	(extract_range_from_ssa_name): Update the equivalence set of
	the new range with VAR.
	(extract_range_from_binary_expr): Also handle TRUTH_*_EXPR.
	If -fwrapv is used, set the resulting range to VARYING if the
	operation overflows.  Otherwise, use TYPE_MIN_VALUE and
	TYPE_MAX_VALUE to represent -INF and +INF.
	Fix handling of *_DIV_EXPR.
	(extract_range_from_unary_expr): Handle MINUS_EXPR and
	ABS_EXPR properly by switching the range around if necessary.
	(extract_range_from_comparison): New local function.
	(extract_range_from_expr): Call it.
	(adjust_range_with_scev): Do not adjust the range if using
	wrapping arithmetic (-fwrapv).
	(dump_value_range): Also show equivalence set.
	Show -INF and +INF for TYPE_MIN_VALUE and TYPE_MAX_VALUE.
	(build_assert_expr_for): Also build ASSERT_EXPR for EQ_EXPR.
	(infer_value_range): Change return value to bool.
	Add arguments 'comp_code_p' and 'val_p'.
	Do not attempt to infer ranges from statements that may throw.
	Store the comparison code in comp_code_p.
	Store the other operand to be used in the predicate in val_p.
	(dump_asserts_for): New.
	(debug_asserts_for): New.
	(dump_all_asserts): New.
	(debug_all_asserts): New.
	(register_new_assert_for): New.
	(register_edge_assert_for): New.
	(find_conditional_asserts): New.
	(find_assert_locations): New.
	(process_assert_insertions_for): New.
	(process_assert_insertions): New.
	(insert_range_assertions): Initialize found_in_subgraph,
	blocks_visited, need_assert_for and asserts_for.
	Call find_assert_locations and process_assert_insertions.
	(remove_range_assertions): Add more documentation.
	(vrp_initialize): Change return type to void.
	Do not try to guess if running VRP is worth it.
	(compare_name_with_value): New.
	(compare_names): New.
	(vrp_evaluate_conditional): Add argument 'use_equiv_p'.  If
	use_equiv_p is true, call compare_names and
	compare_name_with_value to compare all the ranges for every
	name in the equivalence set of the predicate operands.
	Update all callers.
	(vrp_meet): Try harder not to derive a VARYING range.
	If two values meet, the resulting equivalence set is the
	intersection of the two equivalence sets.
	(vrp_visit_phi_node): Call copy_value_range to get the current
	range information of the LHS.
	(vrp_finalize): Create a value vector representing all the
	names that ended up with exactly one value in their range.
	Call substitute_and_fold.
	(execute_vrp): Document equivalence sets in ranges.
	* tree.h (SSA_NAME_VALUE_RANGE): Remove.
	(struct tree_ssa_name): Remove field value_range.
	(invert_tree_comparison): Declare.

testsuite/ChangeLog

2005-06-01  Diego Novillo  <dnovillo@redhat.com>

	PR 14341, PR 21332, PR 20701, PR 21086, PR 21090
	PR 21289, PR 21348, PR 21367, PR 21368, PR 21458.
	* gcc.dg/tree-ssa/pr14341.c: New test.
	* gcc.dg/tree-ssa/pr14841.c: New test.
	* gcc.dg/tree-ssa/pr20701.c: New test.
	* gcc.dg/tree-ssa/pr21086.c: New test.
	* gcc.dg/tree-ssa/pr21090.c: New test.
	* gcc.dg/tree-ssa/pr21332.c: New test.
	* gcc.dg/tree-ssa/pr21458.c: New test.
	* gcc.dg/tree-ssa/pr21658.c: New test.
	* gcc.dg/tree-ssa/vrp01.c: New test.
	* gcc.dg/tree-ssa/vrp02.c: New test.
	* gcc.dg/tree-ssa/vrp03.c: New test.
	* gcc.dg/tree-ssa/vrp04.c: New test.
	* gcc.dg/tree-ssa/vrp05.c: New test.
	* gcc.dg/tree-ssa/vrp06.c: New test.
	* gcc.dg/tree-ssa/vrp07.c: New test.
	* gcc.dg/tree-ssa/vrp08.c: New test.
	* gcc.dg/tree-ssa/vrp09.c: New test.
	* gcc.dg/tree-ssa/vrp10.c: New test.
	* gcc.dg/tree-ssa/vrp11.c: New test.
	* gcc.dg/tree-ssa/vrp12.c: New test.
	* gcc.dg/tree-ssa/vrp13.c: New test.

2005-06-01  Alexandre Oliva  <aoliva@redhat.com>

	PR 21029
	* gcc.dg/tree-ssa/pr21029.c: New test.


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

1 files changed, 114 insertions, 32 deletions

diff --git a/gcc/tree-ssa-propagate.c b/gcc/tree-ssa-propagate.c
index f272aa54b4b..37c644b50c4 100644
--- a/gcc/tree-ssa-propagate.c
+++ b/gcc/tree-ssa-propagate.c
@@ -773,6 +773,7 @@ struct prop_stats_d
 {
   long num_const_prop;
   long num_copy_prop;
+  long num_pred_folded;
 };
 
 static struct prop_stats_d prop_stats;
@@ -964,6 +965,11 @@ static void
 replace_phi_args_in (tree phi, prop_value_t *prop_value)
 {
   int i;
+  bool replaced = false;
+  tree prev_phi = NULL;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    prev_phi = unshare_expr (phi);
 
   for (i = 0; i < PHI_NUM_ARGS (phi); i++)
     {
@@ -981,6 +987,7 @@ replace_phi_args_in (tree phi, prop_value_t *prop_value)
 		prop_stats.num_copy_prop++;
 
 	      propagate_value (PHI_ARG_DEF_PTR (phi, i), val);
+	      replaced = true;
 
 	      /* If we propagated a copy and this argument flows
 		 through an abnormal edge, update the replacement
@@ -991,19 +998,79 @@ replace_phi_args_in (tree phi, prop_value_t *prop_value)
 	    }
 	}
     }
+  
+  if (replaced && dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Folded PHI node: ");
+      print_generic_stmt (dump_file, prev_phi, TDF_SLIM);
+      fprintf (dump_file, "           into: ");
+      print_generic_stmt (dump_file, phi, TDF_SLIM);
+      fprintf (dump_file, "\n");
+    }
+}
+
+
+/* If STMT has a predicate whose value can be computed using the value
+   range information computed by VRP, compute its value and return true.
+   Otherwise, return false.  */
+
+static bool
+fold_predicate_in (tree stmt)
+{
+  tree *pred_p = NULL;
+  tree val;
+
+  if (TREE_CODE (stmt) == MODIFY_EXPR
+      && COMPARISON_CLASS_P (TREE_OPERAND (stmt, 1)))
+    pred_p = &TREE_OPERAND (stmt, 1);
+  else if (TREE_CODE (stmt) == COND_EXPR)
+    pred_p = &COND_EXPR_COND (stmt);
+  else
+    return false;
+
+  val = vrp_evaluate_conditional (*pred_p, true);
+  if (val)
+    {
+      if (dump_file)
+	{
+	  fprintf (dump_file, "Folding predicate ");
+	  print_generic_expr (dump_file, *pred_p, 0);
+	  fprintf (dump_file, " to ");
+	  print_generic_expr (dump_file, val, 0);
+	  fprintf (dump_file, "\n");
+	}
+
+      prop_stats.num_pred_folded++;
+      *pred_p = val;
+      return true;
+    }
+
+  return false;
 }
 
 
-/* Perform final substitution and folding of propagated values.  */
+/* Perform final substitution and folding of propagated values.
+
+   PROP_VALUE[I] contains the single value that should be substituted
+   at every use of SSA name N_I.  If PROP_VALUE is NULL, no values are
+   substituted.
+
+   If USE_RANGES_P is true, statements that contain predicate
+   expressions are evaluated with a call to vrp_evaluate_conditional.
+   This will only give meaningful results when called from tree-vrp.c
+   (the information used by vrp_evaluate_conditional is built by the
+   VRP pass).  */
 
 void
-substitute_and_fold (prop_value_t *prop_value)
+substitute_and_fold (prop_value_t *prop_value, bool use_ranges_p)
 {
   basic_block bb;
 
+  if (prop_value == NULL && !use_ranges_p)
+    return;
+
   if (dump_file && (dump_flags & TDF_DETAILS))
-    fprintf (dump_file,
-	     "\nSubstituing values and folding statements\n\n");
+    fprintf (dump_file, "\nSubstituing values and folding statements\n\n");
 
   memset (&prop_stats, 0, sizeof (prop_stats));
 
@@ -1013,41 +1080,51 @@ substitute_and_fold (prop_value_t *prop_value)
       block_stmt_iterator i;
       tree phi;
 
-      /* Propagate our known values into PHI nodes.  */
-      for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
-	{
-	  if (dump_file && (dump_flags & TDF_DETAILS))
-	    {
-	      fprintf (dump_file, "Replaced ");
-	      print_generic_stmt (dump_file, phi, TDF_SLIM);
-	    }
-
+      /* Propagate known values into PHI nodes.  */
+      if (prop_value)
+	for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 	  replace_phi_args_in (phi, prop_value);
 
-	  if (dump_file && (dump_flags & TDF_DETAILS))
-	    {
-	      fprintf (dump_file, " with ");
-	      print_generic_stmt (dump_file, phi, TDF_SLIM);
-	      fprintf (dump_file, "\n");
-	    }
-	}
-
       for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
 	{
           bool replaced_address, did_replace;
+	  tree prev_stmt = NULL;
 	  tree stmt = bsi_stmt (i);
 
+	  /* Ignore ASSERT_EXPRs.  They are used by VRP to generate
+	     range information for names and they are discarded
+	     afterwards.  */
+	  if (TREE_CODE (stmt) == MODIFY_EXPR
+	      && TREE_CODE (TREE_OPERAND (stmt, 1)) == ASSERT_EXPR)
+	    continue;
+
 	  /* Replace the statement with its folded version and mark it
 	     folded.  */
+	  did_replace = false;
+	  replaced_address = false;
 	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    prev_stmt = unshare_expr (stmt);
+
+	  /* If we have range information, see if we can fold
+	     predicate expressions.  */
+	  if (use_ranges_p)
+	    did_replace = fold_predicate_in (stmt);
+
+	  if (prop_value)
 	    {
-	      fprintf (dump_file, "Replaced ");
-	      print_generic_stmt (dump_file, stmt, TDF_SLIM);
+	      /* Only replace real uses if we couldn't fold the
+		 statement using value range information (value range
+		 information is not collected on virtuals, so we only
+		 need to check this for real uses).  */
+	      if (!did_replace)
+		did_replace |= replace_uses_in (stmt, &replaced_address,
+		                                prop_value);
+
+	      did_replace |= replace_vuses_in (stmt, &replaced_address,
+		                               prop_value);
 	    }
 
-	  replaced_address = false;
-	  did_replace = replace_uses_in (stmt, &replaced_address, prop_value);
-	  did_replace |= replace_vuses_in (stmt, &replaced_address, prop_value);
+	  /* If we made a replacement, fold and cleanup the statement.  */
 	  if (did_replace)
 	    {
 	      tree old_stmt = stmt;
@@ -1068,13 +1145,15 @@ substitute_and_fold (prop_value_t *prop_value)
 	      rhs = get_rhs (stmt);
 	      if (TREE_CODE (rhs) == ADDR_EXPR)
 		recompute_tree_invarant_for_addr_expr (rhs);
-	    }
 
-	  if (dump_file && (dump_flags & TDF_DETAILS))
-	    {
-	      fprintf (dump_file, " with ");
-	      print_generic_stmt (dump_file, stmt, TDF_SLIM);
-	      fprintf (dump_file, "\n");
+	      if (dump_file && (dump_flags & TDF_DETAILS))
+		{
+		  fprintf (dump_file, "Folded statement: ");
+		  print_generic_stmt (dump_file, prev_stmt, TDF_SLIM);
+		  fprintf (dump_file, "            into: ");
+		  print_generic_stmt (dump_file, stmt, TDF_SLIM);
+		  fprintf (dump_file, "\n");
+		}
 	    }
 	}
     }
@@ -1085,6 +1164,9 @@ substitute_and_fold (prop_value_t *prop_value)
 	       prop_stats.num_const_prop);
       fprintf (dump_file, "Copies propagated:    %6ld\n",
 	       prop_stats.num_copy_prop);
+      fprintf (dump_file, "Predicates folded:    %6ld\n",
+	       prop_stats.num_pred_folded);
     }
 }
+
 #include "gt-tree-ssa-propagate.h"