2005-04-22 Diego Novillo <dnovillo@redhat.com>

	* Makefile.in (tree-into-ssa.o): Add dependency on PARAMS_H.
	* lambda-code.c (perfect_nestify): Mark virtual operands in
	the moved statement for renaming.
	* params.def (PARAM_MIN_VIRTUAL_MAPPINGS): Define.
	(PARAM_VIRTUAL_MAPPINGS_TO_SYMS_RATIO): Define.
	* params.h (MIN_VIRTUAL_MAPPINGS): Define.
	(VIRTUAL_MAPPINGS_TO_SYMS_RATIO): Define.
	* tree-flow.h (struct var_ann_d): Update comments.
	(rewrite_to_new_ssa_names_bb, rewrite_to_new_ssa_names,
	allocate_ssa_names, find_phi_node_for, dump_tree_ssa,
	debug_tree_ssa, debug_def_blocks, dump_tree_ssa_stats,
	debug_tree_ssa_stats, rewrite_ssa_into_ssa,
	dump_repl_tbl, debug_repl_tbl, dump_names_replaced_by,
	debug_names_replaced_by): Remove declarations.
	(delete_update_ssa, get_current_def, set_current_def): Declare.
	(rewrite_into_loop_closed_ssa): Add new argument.  Update
	all callers.
	* tree-into-ssa.c: Include params.h.
	(old_virtual_ssa_names): Remove.  Update all users.
	(need_to_replace_names_p): Remove.  Update all users.
	(struct update_ssa_stats_d): Declare.
	(update_ssa_stats): New local.
	(dump_tree_ssa, debug_tree_ssa, debug_def_blocks,
	dump_tree_ssa_stats, debug_tree_ssa_stats,
	dump_update_ssa, debug_update_ssa,
	dump_names_replaced_by, debug_names_replaced_by): Declare.
	(get_current_def, set current_def): Make extern.
	(is_old_name, is_new_name): Protect against references
	past the end of the sets.
	(add_new_name_mapping): Assert that OLD and NEW are
	different SSA names for the same symbol.
	When adding a virtual mapping, update stats for virtual
	mapping heuristic.
	(insert_phi_nodes_for): If UPDATE_P is true, create the
	LHS of the new PHI by duplicating SSA name VAR.
	(insert_phi_nodes_1): Remove.  Update all users.
	(insert_phi_nodes): Remove second argument.  Update all
	users.
	(maybe_replace_use, maybe_replace_def): New.
	(rewrite_update_stmt): Call them.
	(mark_def_interesting): Remove calls to is_gimple_reg.
	(prepare_phi_args_for_update): Remove.  Update all users.
	(prepare_block_for_update): Only process virtual operands
	and GIMPLE registers in normal form.
	(prepare_use_sites_for): New.
	(prepare_names_to_update): Rename from prepare_def_sites.
	Call prepare_use_sites_for.
	(dump_update_ssa): Rename from dump_repl_tbl.
	Update all users.
	Show statistics for virtual mapping heuristic.
	(debug_update_ssa): Rename from debug_debug_repl_tbl.
	(init_update_ssa): Initialize UPDATE_SSA_STATS.
	(delete_update_ssa): Make extern.
	(mark_set_for_renaming): If the set is empty, do nothing.
	(release_ssa_name_after_update_ssa): Update comment.
	(insert_updated_phi_nodes_for): Do not remove existing
	PHI nodes for symbols.
	(switch_virtuals_to_full_rewrite_p): New.
	(switch_virtuals_to_full_rewrite): New.
	(update_ssa): Call them.
	Clear REWRITE_THIS_STMT and REGISTER_DEFS_IN_THIS_STMT
	for every statement before updating.
	If all the names in NEW_SSA_NAMES have been marked for
	removal, do nothing.
	Only start at the top of the CFG if there are symbols in
	SYMS_TO_RENAME.
	(ssa_rewrite_finalize_block): Remove.
	(ssa_register_new_def): Remove.
	(ssa_rewrite_stmt): Remove.
	(ssa_rewrite_phi_arguments): Remove.
	(ssa_rewrite_initialize_block): Remove.
	(ssa_mark_def_sites): Remove.
	(ssa_mark_def_sites_initialize_block): Remove.
	(ssa_mark_phi_uses): Remove.
	(rewrite_ssa_into_ssa): Remove.
	* tree-phinodes.c (find_phi_node_for): Remove.
	* tree-ssa-loop-ivcanon.c (try_unroll_loop_completely):
	Call update_ssa.
	* tree-ssa-loop-unswitch.c (tree_ssa_unswitch_loops):
	Remove calls to verify_dominators and
	verify_loop_structure.
	(tree_unswitch_single_loop): Call update_ssa.
	* tree-ssa.c (verify_ssa): Assert that need_ssa_update_p
	returns false.
	Call verify_stmts.
	(delete_tree_ssa): Assert that need_ssa_update_p returns
	false.
	* tree-vect-transform.c (vect_transform_loop): Call update_ssa.
	* tree-vectorizer.c (allocate_new_names, rename_def_op,
	free_new_names): Remove.  Update all users.
	(rename_use_op): Call get_current_def.
	(rename_variables_in_bb): Do not handle any real or
	virtual definition.
	(slpeel_update_phis_for_duplicate_loop): Call
	get_current_def and set_current_def instead of using
	SSA_NAME_AUX.
	(slpeel_update_phi_nodes_for_guard2): Reformat comments.
	(slpeel_can_duplicate_loop_p): Call need_ssa_update_p,
	ssa_names_to_replace and delete_update_ssa.
	* doc/invoke.texi: Document --param min-virtual-mappings
	and --param virtual-mappings-ratio.

2005-04-22  Zdenek Dvorak  <dvorakz@suse.cz>
	    Diego Novillo  <dnovillo@redhat.com>

	* tree-cfg.c (tree_duplicate_bb): Call create_new_def_for
	for newly created PHI nodes.
	Call create_new_def_for for every new V_MAY_DEF and
	V_MUST_DEF on the copied statement.
	(struct ssa_name_map_entry): Remove.
	(ssa_name_map_entry_hash): Remove.
	(ssa_name_map_entry_eq): Remove.
	(allocate_ssa_names): Remove.
	(rewrite_to_new_ssa_names_def): Remove.
	(rewrite_to_new_ssa_names_use): Remove.
	(rewrite_to_new_ssa_names_bb): Remove.
	(rewrite_to_new_ssa_names): Remove.
	(tree_duplicate_sese_region): Remove variables ver,
	definitions, phi, ssa_name_map and bi.
	Call need_ssa_update_p instead of any_marked_for_rewrite_p.
	Call update_ssa.
	* tree-ssa-dom.c (tree_ssa_dominator_optimize): Call
	update_ssa instead of rewrite_ssa_into_ssa.
	* tree-ssa-loop-manip.c (add_exit_phis_edge): Call
	create_new_def_for.
	(find_uses_to_rename_use): Add argument 'need_phis'.
	(find_uses_to_rename_stmt): Do not scan virtual operands.
	(find_uses_to_rename): Only scan PHI nodes for
	non-virtual names.
	(rewrite_into_loop_closed_ssa): Call update_ssa.
	(check_loop_closed_ssa_use): Ignore virtual operands.
	(check_loop_closed_ssa_stmt): Likewise.
	(verify_loop_closed_ssa): Do nothing if CURRENT_LOOPS is
	NULL.
	(rename_variables, set_phi_def_stmts): Remove.
	(tree_duplicate_loop_to_header_edge): Reformat comment.
	Remove variables BB, I and DEFINITIONS.
	Call need_ssa_update_p.
	Call update_ssa.
	(lv_adjust_loop_header_phi): Reformat comment.
	* tree-ssanames.c (ssa_names_to_rewrite): Remove.
	(marked_for_rewrite_p, any_marked_for_rewrite_p,
	mark_for_rewrite, unmark_all_for_rewrite,
	marked_ssa_names): Remove.  Update all users.
	(release_ssa_name): If VAR has been registered for SSA
	updating, do nothing.
	* tree-vrp.c (new_ssa_names, old_ssa_names): Remove.
	(build_assert_expr_for): Call register_new_name_mapping.
	(insert_range_assertions): Update call to update_ssa.
	* tree.h (mark_for_rewrite, unmark_all_for_rewrite,
	marked_for_rewrite_p, any_marked_for_rewrite_p,
	marked_ssa_names): Remove.


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

1 files changed, 52 insertions, 113 deletions

diff --git a/gcc/tree-ssa-loop-manip.c b/gcc/tree-ssa-loop-manip.c
index 02b21a32f94..f16ec3f7522 100644
--- a/gcc/tree-ssa-loop-manip.c
+++ b/gcc/tree-ssa-loop-manip.c
@@ -139,11 +139,9 @@ add_exit_phis_edge (basic_block exit, tree use)
     return;
 
   phi = create_phi_node (use, exit);
-
+  create_new_def_for (PHI_RESULT (phi), phi, PHI_RESULT_PTR (phi));
   FOR_EACH_EDGE (e, ei, exit->preds)
     add_phi_arg (phi, use, e);
-
-  SSA_NAME_DEF_STMT (use) = def_stmt;
 }
 
 /* Add exit phis for VAR that is used in LIVEIN.
@@ -215,10 +213,11 @@ get_loops_exits (void)
 
 /* For USE in BB, if it is used outside of the loop it is defined in,
    mark it for rewrite.  Record basic block BB where it is used
-   to USE_BLOCKS.  */
+   to USE_BLOCKS.  Record the ssa name index to NEED_PHIS bitmap.  */
 
 static void
-find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks)
+find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks,
+			 bitmap need_phis)
 {
   unsigned ver;
   basic_block def_bb;
@@ -227,6 +226,10 @@ find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks)
   if (TREE_CODE (use) != SSA_NAME)
     return;
 
+  /* We don't need to keep virtual operands in loop-closed form.  */
+  if (!is_gimple_reg (use))
+    return;
+
   ver = SSA_NAME_VERSION (use);
   def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (use));
   if (!def_bb)
@@ -241,31 +244,32 @@ find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks)
     use_blocks[ver] = BITMAP_ALLOC (NULL);
   bitmap_set_bit (use_blocks[ver], bb->index);
 
-  if (!flow_bb_inside_loop_p (def_loop, bb))
-    mark_for_rewrite (use);
+  bitmap_set_bit (need_phis, ver);
 }
 
 /* For uses in STMT, mark names that are used outside of the loop they are
    defined to rewrite.  Record the set of blocks in that the ssa
-   names are defined to USE_BLOCKS.  */
+   names are defined to USE_BLOCKS and the ssa names themselves to
+   NEED_PHIS.  */
 
 static void
-find_uses_to_rename_stmt (tree stmt, bitmap *use_blocks)
+find_uses_to_rename_stmt (tree stmt, bitmap *use_blocks, bitmap need_phis)
 {
   ssa_op_iter iter;
   tree var;
   basic_block bb = bb_for_stmt (stmt);
 
   FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
-    find_uses_to_rename_use (bb, var, use_blocks);
+    find_uses_to_rename_use (bb, var, use_blocks, need_phis);
 }
 
 /* Marks names that are used in BB and outside of the loop they are
    defined in for rewrite.  Records the set of blocks in that the ssa
-   names are defined to USE_BLOCKS.  */
+   names are defined to USE_BLOCKS.  Record the SSA names that will
+   need exit PHIs in NEED_PHIS.  */
 
 static void
-find_uses_to_rename_bb (basic_block bb, bitmap *use_blocks)
+find_uses_to_rename_bb (basic_block bb, bitmap *use_blocks, bitmap need_phis)
 {
   block_stmt_iterator bsi;
   edge e;
@@ -275,10 +279,10 @@ find_uses_to_rename_bb (basic_block bb, bitmap *use_blocks)
   FOR_EACH_EDGE (e, ei, bb->succs)
     for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
       find_uses_to_rename_use (bb, PHI_ARG_DEF_FROM_EDGE (phi, e),
-			       use_blocks);
+			       use_blocks, need_phis);
  
   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
-    find_uses_to_rename_stmt (bsi_stmt (bsi), use_blocks);
+    find_uses_to_rename_stmt (bsi_stmt (bsi), use_blocks, need_phis);
 }
      
 /* Marks names that are used outside of the loop they are defined in
@@ -287,24 +291,24 @@ find_uses_to_rename_bb (basic_block bb, bitmap *use_blocks)
    scan only blocks in this set.  */
 
 static void
-find_uses_to_rename (bitmap changed_bbs, bitmap *use_blocks)
+find_uses_to_rename (bitmap changed_bbs, bitmap *use_blocks, bitmap need_phis)
 {
   basic_block bb;
   unsigned index;
   bitmap_iterator bi;
 
-  if (changed_bbs)
+  if (changed_bbs && !bitmap_empty_p (changed_bbs))
     {
       EXECUTE_IF_SET_IN_BITMAP (changed_bbs, 0, index, bi)
 	{
-	  find_uses_to_rename_bb (BASIC_BLOCK (index), use_blocks);
+	  find_uses_to_rename_bb (BASIC_BLOCK (index), use_blocks, need_phis);
 	}
     }
   else
     {
       FOR_EACH_BB (bb)
 	{
-	  find_uses_to_rename_bb (bb, use_blocks);
+	  find_uses_to_rename_bb (bb, use_blocks, need_phis);
 	}
     }
 }
@@ -336,43 +340,42 @@ find_uses_to_rename (bitmap changed_bbs, bitmap *use_blocks)
       base 99 and step 1.
       
       If CHANGED_BBS is not NULL, we look for uses outside loops only in
-      the basic blocks in this set.  */
+      the basic blocks in this set.
+
+      UPDATE_FLAG is used in the call to update_ssa.  See
+      TODO_update_ssa* for documentation.  */
 
 void
-rewrite_into_loop_closed_ssa (bitmap changed_bbs)
+rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag)
 {
   bitmap loop_exits = get_loops_exits ();
   bitmap *use_blocks;
-  unsigned i;
-  bitmap names_to_rename;
+  unsigned i, old_num_ssa_names;
+  bitmap names_to_rename = BITMAP_ALLOC (NULL);
 
-  gcc_assert (!any_marked_for_rewrite_p ());
+  /* If the pass has caused the SSA form to be out-of-date, update it
+     now.  */
+  update_ssa (update_flag);
 
-  use_blocks = xcalloc (num_ssa_names, sizeof (bitmap));
+  old_num_ssa_names = num_ssa_names;
+  use_blocks = xcalloc (old_num_ssa_names, sizeof (bitmap));
 
   /* Find the uses outside loops.  */
-  find_uses_to_rename (changed_bbs, use_blocks);
+  find_uses_to_rename (changed_bbs, use_blocks, names_to_rename);
 
-  if (!any_marked_for_rewrite_p ())
-    {
-      free (use_blocks);
-      BITMAP_FREE (loop_exits);
-      return;
-    }
-
-  /* Add the phi nodes on exits of the loops for the names we need to
+  /* Add the PHI nodes on exits of the loops for the names we need to
      rewrite.  */
-  names_to_rename = marked_ssa_names ();
   add_exit_phis (names_to_rename, use_blocks, loop_exits);
 
-  for (i = 0; i < num_ssa_names; i++)
+  for (i = 0; i < old_num_ssa_names; i++)
     BITMAP_FREE (use_blocks[i]);
   free (use_blocks);
   BITMAP_FREE (loop_exits);
   BITMAP_FREE (names_to_rename);
 
-  /* Do the rewriting.  */
-  rewrite_ssa_into_ssa ();
+  /* Fix up all the names found to be used outside their original
+     loops.  */
+  update_ssa (TODO_update_ssa);
 }
 
 /* Check invariants of the loop closed ssa form for the USE in BB.  */
@@ -383,7 +386,7 @@ check_loop_closed_ssa_use (basic_block bb, tree use)
   tree def;
   basic_block def_bb;
   
-  if (TREE_CODE (use) != SSA_NAME)
+  if (TREE_CODE (use) != SSA_NAME || !is_gimple_reg (use))
     return;
 
   def = SSA_NAME_DEF_STMT (use);
@@ -400,7 +403,7 @@ check_loop_closed_ssa_stmt (basic_block bb, tree stmt)
   ssa_op_iter iter;
   tree var;
 
-  FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES)
+  FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
     check_loop_closed_ssa_use (bb, var);
 }
 
@@ -414,6 +417,9 @@ verify_loop_closed_ssa (void)
   tree phi;
   unsigned i;
 
+  if (current_loops == NULL)
+    return;
+
   verify_ssa (false);
 
   FOR_EACH_BB (bb)
@@ -566,53 +572,15 @@ copy_phi_node_args (unsigned first_new_block)
     BASIC_BLOCK (i)->rbi->duplicated = 0;
 }
 
-/* Renames variables in the area copied by tree_duplicate_loop_to_header_edge.
-   FIRST_NEW_BLOCK is the first block in the copied area.   DEFINITIONS is
-   a bitmap of all ssa names defined inside the loop.  */
-
-static void
-rename_variables (unsigned first_new_block, bitmap definitions)
-{
-  unsigned i, copy_number = 0;
-  basic_block bb;
-  htab_t ssa_name_map = NULL;
-
-  for (i = first_new_block; i < (unsigned) last_basic_block; i++)
-    {
-      bb = BASIC_BLOCK (i);
 
-      /* We assume that first come all blocks from the first copy, then all
-	 blocks from the second copy, etc.  */
-      if (copy_number != (unsigned) bb->rbi->copy_number)
-	{
-	  allocate_ssa_names (definitions, &ssa_name_map);
-	  copy_number = bb->rbi->copy_number;
-	}
+/* The same as cfgloopmanip.c:duplicate_loop_to_header_edge, but also
+   updates the PHI nodes at start of the copied region.  In order to
+   achieve this, only loops whose exits all lead to the same location
+   are handled.
 
-      rewrite_to_new_ssa_names_bb (bb, ssa_name_map);
-    }
-
-  htab_delete (ssa_name_map);
-}
-
-/* Sets SSA_NAME_DEF_STMT for results of all phi nodes in BB.  */
-
-static void
-set_phi_def_stmts (basic_block bb)
-{
-  tree phi;
-
-  for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
-    SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = phi;
-}
-
-/* The same as cfgloopmanip.c:duplicate_loop_to_header_edge, but also updates
-   ssa.  In order to achieve this, only loops whose exits all lead to the same
-   location are handled.
-   
-   FIXME: we create some degenerate phi nodes that could be avoided by copy
-   propagating them instead.  Unfortunately this is not completely
-   straightforward due to problems with constant folding.  */
+   Notice that we do not completely update the SSA web after
+   duplication.  The caller is responsible for calling update_ssa
+   after the loop has been duplicated.  */
 
 bool
 tree_duplicate_loop_to_header_edge (struct loop *loop, edge e,
@@ -622,9 +590,6 @@ tree_duplicate_loop_to_header_edge (struct loop *loop, edge e,
 				    unsigned int *n_to_remove, int flags)
 {
   unsigned first_new_block;
-  basic_block bb;
-  unsigned i;
-  bitmap definitions;
 
   if (!(loops->state & LOOPS_HAVE_SIMPLE_LATCHES))
     return false;
@@ -635,8 +600,6 @@ tree_duplicate_loop_to_header_edge (struct loop *loop, edge e,
   verify_loop_closed_ssa ();
 #endif
 
-  gcc_assert (!any_marked_for_rewrite_p ());
-
   first_new_block = last_basic_block;
   if (!duplicate_loop_to_header_edge (loop, e, loops, ndupl, wont_exit,
 				      orig, to_remove, n_to_remove, flags))
@@ -648,31 +611,7 @@ tree_duplicate_loop_to_header_edge (struct loop *loop, edge e,
   /* Copy the phi node arguments.  */
   copy_phi_node_args (first_new_block);
 
-  /* Rename the variables.  */
-  definitions = marked_ssa_names ();
-  rename_variables (first_new_block, definitions);
-  unmark_all_for_rewrite ();
-  BITMAP_FREE (definitions);
-
-  /* For some time we have the identical ssa names as results in multiple phi
-     nodes.  When phi node is resized, it sets SSA_NAME_DEF_STMT of its result
-     to the new copy.  This means that we cannot easily ensure that the ssa
-     names defined in those phis are pointing to the right one -- so just
-     recompute SSA_NAME_DEF_STMT for them.  */ 
-
-  for (i = first_new_block; i < (unsigned) last_basic_block; i++)
-    {
-      bb = BASIC_BLOCK (i);
-      set_phi_def_stmts (bb);
-      if (bb->rbi->copy_number == 1)
-  	set_phi_def_stmts (bb->rbi->original);
-    }
-
   scev_reset ();
-#ifdef ENABLE_CHECKING
-  verify_loop_closed_ssa ();
-#endif
 
   return true;
 }
-