timevar.def (TV_SCEV_CONST): New timevar.

	* timevar.def (TV_SCEV_CONST): New timevar.
	* tree-optimize.c (init_tree_optimization_passes): Add
	pass_scev_cprop.
	* tree-pass.h (pass_scev_cprop): Declare.
	* tree-scalar-evolution.c (scev_const_prop): New function.
	* tree-scalar-evolution.h (scev_const_prop): Declare.
	* tree-ssa-loop.c (gate_scev_const_prop, pass_scev_cprop):
	New.
	* tree-cfg.c (replace_uses_by): Export.
	* tree-flow.h (replace_uses_by): Declare.

From-SVN: r99860

9 files changed, 113 insertions, 1 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 1dffbedeb27..4d9766b4dba 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,16 @@
+2005-05-17  Zdenek Dvorak  <dvorakz@suse.cz>
+
+	* timevar.def (TV_SCEV_CONST): New timevar.
+	* tree-optimize.c (init_tree_optimization_passes): Add
+	pass_scev_cprop.
+	* tree-pass.h (pass_scev_cprop): Declare.
+	* tree-scalar-evolution.c (scev_const_prop): New function.
+	* tree-scalar-evolution.h (scev_const_prop): Declare.
+	* tree-ssa-loop.c (gate_scev_const_prop, pass_scev_cprop):
+	New.
+	* tree-cfg.c (replace_uses_by): Export.
+	* tree-flow.h (replace_uses_by): Declare.
+
 2005-05-17  Mike Stump  <mrs@apple.com>
 
 	Yet more Objective-C++...
diff --git a/gcc/timevar.def b/gcc/timevar.def
index d7bed9297ee..f6f099f0b88 100644
--- a/gcc/timevar.def
+++ b/gcc/timevar.def
@@ -95,6 +95,7 @@ DEFTIMEVAR (TV_TREE_LOOP	     , "tree loop optimization")
 DEFTIMEVAR (TV_TREE_LOOP_BOUNDS	     , "tree loop bounds")
 DEFTIMEVAR (TV_LIM                   , "loop invariant motion")
 DEFTIMEVAR (TV_TREE_LOOP_IVCANON     , "tree canonical iv")
+DEFTIMEVAR (TV_SCEV_CONST            , "scev constant prop")
 DEFTIMEVAR (TV_TREE_LOOP_UNSWITCH    , "tree loop unswitching")
 DEFTIMEVAR (TV_COMPLETE_UNROLL       , "complete unrolling")
 DEFTIMEVAR (TV_TREE_VECTORIZATION    , "tree vectorization")
diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c
index 4beb0e74290..c1419827e1f 100644
--- a/gcc/tree-cfg.c
+++ b/gcc/tree-cfg.c
@@ -1323,7 +1323,7 @@ tree_can_merge_blocks_p (basic_block a, basic_block b)
 
 /* Replaces all uses of NAME by VAL.  */
 
-static void
+void
 replace_uses_by (tree name, tree val)
 {
   imm_use_iterator imm_iter;
diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h
index 273a26ce49c..3fc5d98ab49 100644
--- a/gcc/tree-flow.h
+++ b/gcc/tree-flow.h
@@ -543,6 +543,7 @@ extern tree gimplify_build3 (block_stmt_iterator *, enum tree_code,
 			     tree, tree, tree, tree);
 extern void init_empty_tree_cfg (void);
 extern void fold_cond_expr_cond (void);
+extern void replace_uses_by (tree, tree);
 
 /* In tree-pretty-print.c.  */
 extern void dump_generic_bb (FILE *, basic_block, int, int);
diff --git a/gcc/tree-optimize.c b/gcc/tree-optimize.c
index 329c06e3182..6dba7bd0f83 100644
--- a/gcc/tree-optimize.c
+++ b/gcc/tree-optimize.c
@@ -472,6 +472,7 @@ init_tree_optimization_passes (void)
   NEXT_PASS (pass_copy_prop);
   NEXT_PASS (pass_lim);
   NEXT_PASS (pass_unswitch);
+  NEXT_PASS (pass_scev_cprop);
   NEXT_PASS (pass_record_bounds);
   NEXT_PASS (pass_linear_transform);
   NEXT_PASS (pass_iv_canon);
diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
index a65df46ccac..e2446344142 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -173,6 +173,7 @@ extern struct tree_opt_pass pass_loop_init;
 extern struct tree_opt_pass pass_lim;
 extern struct tree_opt_pass pass_unswitch;
 extern struct tree_opt_pass pass_iv_canon;
+extern struct tree_opt_pass pass_scev_cprop;
 extern struct tree_opt_pass pass_record_bounds;
 extern struct tree_opt_pass pass_if_conversion;
 extern struct tree_opt_pass pass_vectorize;
diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c
index 4019f78c0ae..4ff50e61890 100644
--- a/gcc/tree-scalar-evolution.c
+++ b/gcc/tree-scalar-evolution.c
@@ -2627,3 +2627,72 @@ scev_finalize (void)
   BITMAP_FREE (already_instantiated);
 }
 
+/* Replace ssa names for that scev can prove they are constant by the
+   appropriate constants.  Most importantly, this takes care of final
+   value replacement.
+   
+   We only consider SSA names defined by phi nodes; rest is left to the
+   ordinary constant propagation pass.  */
+
+void
+scev_const_prop (void)
+{
+  basic_block bb;
+  tree name, phi, type, ev;
+  struct loop *loop;
+  bitmap ssa_names_to_remove = NULL;
+
+  if (!current_loops)
+    return;
+
+  FOR_EACH_BB (bb)
+    {
+      loop = bb->loop_father;
+
+      for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+	{
+	  name = PHI_RESULT (phi);
+
+	  if (!is_gimple_reg (name))
+	    continue;
+
+	  type = TREE_TYPE (name);
+
+	  if (!POINTER_TYPE_P (type)
+	      && !INTEGRAL_TYPE_P (type))
+	    continue;
+
+	  ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name));
+	  if (!is_gimple_min_invariant (ev)
+	      || !may_propagate_copy (name, ev))
+	    continue;
+
+	  /* Replace the uses of the name.  */
+	  replace_uses_by (name, ev);
+
+	  if (!ssa_names_to_remove)
+	    ssa_names_to_remove = BITMAP_ALLOC (NULL);
+	  bitmap_set_bit (ssa_names_to_remove, SSA_NAME_VERSION (name));
+	}
+    }
+
+  /* Remove the ssa names that were replaced by constants.  We do not remove them
+     directly in the previous cycle, since this invalidates scev cache.  */
+  if (ssa_names_to_remove)
+    {
+      bitmap_iterator bi;
+      unsigned i;
+
+      EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi)
+	{
+	  name = ssa_name (i);
+	  phi = SSA_NAME_DEF_STMT (name);
+
+	  gcc_assert (TREE_CODE (phi) == PHI_NODE);
+	  remove_phi_node (phi, NULL);
+	}
+
+      BITMAP_FREE (ssa_names_to_remove);
+      scev_reset ();
+    }
+}
diff --git a/gcc/tree-scalar-evolution.h b/gcc/tree-scalar-evolution.h
index 7aa5f54e243..cfb3a39ae58 100644
--- a/gcc/tree-scalar-evolution.h
+++ b/gcc/tree-scalar-evolution.h
@@ -33,5 +33,6 @@ extern tree instantiate_parameters (struct loop *, tree);
 extern void gather_stats_on_scev_database (void);
 extern void scev_analysis (void);
 extern bool simple_iv (struct loop *, tree, tree, tree *, tree *, bool);
+void scev_const_prop (void);
 
 #endif  /* GCC_TREE_SCALAR_EVOLUTION_H  */
diff --git a/gcc/tree-ssa-loop.c b/gcc/tree-ssa-loop.c
index f7a96fb2aa7..9e38e9199d0 100644
--- a/gcc/tree-ssa-loop.c
+++ b/gcc/tree-ssa-loop.c
@@ -286,6 +286,31 @@ struct tree_opt_pass pass_iv_canon =
   0					/* letter */
 };
 
+/* Propagation of constants using scev.  */
+
+static bool
+gate_scev_const_prop (void)
+{
+  return true;
+}
+
+struct tree_opt_pass pass_scev_cprop =
+{
+  "sccp",				/* name */
+  gate_scev_const_prop,			/* gate */
+  scev_const_prop,	       		/* execute */
+  NULL,					/* sub */
+  NULL,					/* next */
+  0,					/* static_pass_number */
+  TV_SCEV_CONST,	  		/* tv_id */
+  PROP_cfg | PROP_ssa,			/* properties_required */
+  0,					/* properties_provided */
+  0,					/* properties_destroyed */
+  0,					/* todo_flags_start */
+  TODO_dump_func,			/* todo_flags_finish */
+  0					/* letter */
+};
+
 /* Record bounds on numbers of iterations of loops.  */
 
 static void