[multiple changes]

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.

From-SVN: r98599

1 files changed, 32 insertions, 244 deletions

diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c
index d47c6b4..bf4d934 100644
--- a/gcc/tree-cfg.c
+++ b/gcc/tree-cfg.c
@@ -963,7 +963,7 @@ cleanup_tree_cfg_loop (void)
   /* This usually does nothing.  But sometimes parts of cfg that originally
      were inside a loop get out of it due to edge removal (since they
      become unreachable by back edges from latch).  */
-  rewrite_into_loop_closed_ssa (changed_bbs);
+  rewrite_into_loop_closed_ssa (changed_bbs, TODO_update_ssa);
 
   BITMAP_FREE (changed_bbs);
 
@@ -4698,6 +4698,7 @@ tree_can_duplicate_bb_p (basic_block bb ATTRIBUTE_UNUSED)
   return true;
 }
 
+
 /* Create a duplicate of the basic block BB.  NOTE: This does not
    preserve SSA form.  */
 
@@ -4706,45 +4707,49 @@ tree_duplicate_bb (basic_block bb)
 {
   basic_block new_bb;
   block_stmt_iterator bsi, bsi_tgt;
-  tree phi, val;
-  ssa_op_iter op_iter;
+  tree phi;
 
   new_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
 
-  /* First copy the phi nodes.  We do not copy phi node arguments here,
-     since the edges are not ready yet.  Keep the chain of phi nodes in
-     the same order, so that we can add them later.  */
+  /* Copy the PHI nodes.  We ignore PHI node arguments here because
+     the incoming edges have not been setup yet.  */
   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
     {
-      mark_for_rewrite (PHI_RESULT (phi));
-      create_phi_node (PHI_RESULT (phi), new_bb);
+      tree copy = create_phi_node (PHI_RESULT (phi), new_bb);
+      create_new_def_for (PHI_RESULT (copy), copy, PHI_RESULT_PTR (copy));
     }
+
+  /* Keep the chain of PHI nodes in the same order so that they can be
+     updated by ssa_redirect_edge.  */
   set_phi_nodes (new_bb, phi_reverse (phi_nodes (new_bb)));
 
   bsi_tgt = bsi_start (new_bb);
   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
     {
-      tree stmt = bsi_stmt (bsi);
-      tree copy;
+      def_operand_p def_p;
+      ssa_op_iter op_iter;
+      tree stmt, copy;
 
+      stmt = bsi_stmt (bsi);
       if (TREE_CODE (stmt) == LABEL_EXPR)
 	continue;
 
-      FOR_EACH_SSA_TREE_OPERAND (val, stmt, op_iter, SSA_OP_ALL_DEFS)
-	mark_for_rewrite (val);
-
+      /* Create a new copy of STMT and duplicate STMT's virtual
+	 operands.  */
       copy = unshare_expr (stmt);
-
-      /* Copy also the virtual operands.  */
-      get_stmt_ann (copy);
-      copy_virtual_operands (copy, stmt);
-      
       bsi_insert_after (&bsi_tgt, copy, BSI_NEW_STMT);
+      copy_virtual_operands (copy, stmt);
+
+      /* Create new names for all the definitions created by COPY and
+	 add replacement mappings for each new name.  */
+      FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
+	create_new_def_for (DEF_FROM_PTR (def_p), copy, def_p);
     }
 
   return new_bb;
 }
 
+
 /* Basic block BB_COPY was created by code duplication.  Add phi node
    arguments for edges going out of BB_COPY.  The blocks that were
    duplicated have rbi->duplicated set to one.  */
@@ -4788,8 +4793,6 @@ add_phi_args_after_copy_bb (basic_block bb_copy)
 	   phi = phi_next, phi_copy = PHI_CHAIN (phi_copy))
 	{
 	  phi_next = PHI_CHAIN (phi);
-
-	  gcc_assert (PHI_RESULT (phi) == PHI_RESULT (phi_copy));
 	  def = PHI_ARG_DEF_FROM_EDGE (phi, e);
 	  add_phi_arg (phi_copy, def, e_copy);
 	}
@@ -4815,193 +4818,6 @@ add_phi_args_after_copy (basic_block *region_copy, unsigned n_region)
     region_copy[i]->rbi->duplicated = 0;
 }
 
-/* Maps the old ssa name FROM_NAME to TO_NAME.  */
-
-struct ssa_name_map_entry
-{
-  tree from_name;
-  tree to_name;
-};
-
-/* Hash function for ssa_name_map_entry.  */
-
-static hashval_t
-ssa_name_map_entry_hash (const void *entry)
-{
-  const struct ssa_name_map_entry *en = entry;
-  return SSA_NAME_VERSION (en->from_name);
-}
-
-/* Equality function for ssa_name_map_entry.  */
-
-static int
-ssa_name_map_entry_eq (const void *in_table, const void *ssa_name)
-{
-  const struct ssa_name_map_entry *en = in_table;
-
-  return en->from_name == ssa_name;
-}
-
-/* Allocate duplicates of ssa names in list DEFINITIONS and store the mapping
-   to MAP.  */
-
-void
-allocate_ssa_names (bitmap definitions, htab_t *map)
-{
-  tree name;
-  struct ssa_name_map_entry *entry;
-  PTR *slot;
-  unsigned ver;
-  bitmap_iterator bi;
-
-  if (!*map)
-    *map = htab_create (10, ssa_name_map_entry_hash,
-			ssa_name_map_entry_eq, free);
-  EXECUTE_IF_SET_IN_BITMAP (definitions, 0, ver, bi)
-    {
-      name = ssa_name (ver);
-      slot = htab_find_slot_with_hash (*map, name, SSA_NAME_VERSION (name),
-				       INSERT);
-      if (*slot)
-	entry = *slot;
-      else
-	{
-	  entry = xmalloc (sizeof (struct ssa_name_map_entry));
-	  entry->from_name = name;
-	  *slot = entry;
-	}
-      entry->to_name = duplicate_ssa_name (name, SSA_NAME_DEF_STMT (name));
-    }
-}
-
-/* Rewrite the definition DEF in statement STMT to new ssa name as specified
-   by the mapping MAP.  */
-
-static void
-rewrite_to_new_ssa_names_def (def_operand_p def, tree stmt, htab_t map)
-{
-  tree name = DEF_FROM_PTR (def);
-  struct ssa_name_map_entry *entry;
-
-  gcc_assert (TREE_CODE (name) == SSA_NAME);
-
-  entry = htab_find_with_hash (map, name, SSA_NAME_VERSION (name));
-  if (!entry)
-    return;
-
-  SET_DEF (def, entry->to_name);
-  SSA_NAME_DEF_STMT (entry->to_name) = stmt;
-}
-
-/* Rewrite the USE to new ssa name as specified by the mapping MAP.  */
-
-static void
-rewrite_to_new_ssa_names_use (use_operand_p use, htab_t map)
-{
-  tree name = USE_FROM_PTR (use);
-  struct ssa_name_map_entry *entry;
-
-  if (TREE_CODE (name) != SSA_NAME)
-    return;
-
-  entry = htab_find_with_hash (map, name, SSA_NAME_VERSION (name));
-  if (!entry)
-    return;
-
-  SET_USE (use, entry->to_name);
-}
-
-/* Rewrite the ssa names in basic block BB to new ones as specified by the
-   mapping MAP.  */
-
-void
-rewrite_to_new_ssa_names_bb (basic_block bb, htab_t map)
-{
-  unsigned i;
-  edge e;
-  edge_iterator ei;
-  tree phi, stmt;
-  block_stmt_iterator bsi;
-  use_optype uses;
-  vuse_optype vuses;
-  def_optype defs;
-  v_may_def_optype v_may_defs;
-  v_must_def_optype v_must_defs;
-  stmt_ann_t ann;
-
-  FOR_EACH_EDGE (e, ei, bb->preds)
-    if (e->flags & EDGE_ABNORMAL)
-      break;
-
-  for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
-    {
-      rewrite_to_new_ssa_names_def (PHI_RESULT_PTR (phi), phi, map);
-      if (e)
-	SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)) = 1;
-    }
-
-  for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
-    {
-      stmt = bsi_stmt (bsi);
-      ann = stmt_ann (stmt);
-
-      uses = USE_OPS (ann);
-      for (i = 0; i < NUM_USES (uses); i++)
-	rewrite_to_new_ssa_names_use (USE_OP_PTR (uses, i), map);
-
-      defs = DEF_OPS (ann);
-      for (i = 0; i < NUM_DEFS (defs); i++)
-	rewrite_to_new_ssa_names_def (DEF_OP_PTR (defs, i), stmt, map);
-
-      vuses = VUSE_OPS (ann);
-      for (i = 0; i < NUM_VUSES (vuses); i++)
-	rewrite_to_new_ssa_names_use (VUSE_OP_PTR (vuses, i), map);
-
-      v_may_defs = V_MAY_DEF_OPS (ann);
-      for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
-	{
-	  rewrite_to_new_ssa_names_use
-		  (V_MAY_DEF_OP_PTR (v_may_defs, i), map);
-	  rewrite_to_new_ssa_names_def
-		  (V_MAY_DEF_RESULT_PTR (v_may_defs, i), stmt, map);
-	}
-
-      v_must_defs = V_MUST_DEF_OPS (ann);
-      for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++)
-	{
-	  rewrite_to_new_ssa_names_def
-	    (V_MUST_DEF_RESULT_PTR (v_must_defs, i), stmt, map);
-	  rewrite_to_new_ssa_names_use
-	    (V_MUST_DEF_KILL_PTR (v_must_defs, i),  map);
-	}
-    }
-
-  FOR_EACH_EDGE (e, ei, bb->succs)
-    for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
-      {
-	rewrite_to_new_ssa_names_use
-		(PHI_ARG_DEF_PTR_FROM_EDGE (phi, e), map);
-
-	if (e->flags & EDGE_ABNORMAL)
-	  {
-	    tree op = PHI_ARG_DEF_FROM_EDGE (phi, e);
-	    SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op) = 1;
-	  }
-      }
-}
-
-/* Rewrite the ssa names in N_REGION blocks REGION to the new ones as specified
-   by the mapping MAP.  */
-
-void
-rewrite_to_new_ssa_names (basic_block *region, unsigned n_region, htab_t map)
-{
-  unsigned r;
-
-  for (r = 0; r < n_region; r++)
-    rewrite_to_new_ssa_names_bb (region[r], map);
-}
-
 /* Duplicates a REGION (set of N_REGION basic blocks) with just a single
    important exit edge EXIT.  By important we mean that no SSA name defined
    inside region is live over the other exit edges of the region.  All entry
@@ -5017,16 +4833,12 @@ tree_duplicate_sese_region (edge entry, edge exit,
 			    basic_block *region, unsigned n_region,
 			    basic_block *region_copy)
 {
-  unsigned i, n_doms, ver;
+  unsigned i, n_doms;
   bool free_region_copy = false, copying_header = false;
   struct loop *loop = entry->dest->loop_father;
   edge exit_copy;
-  bitmap definitions;
-  tree phi;
   basic_block *doms;
-  htab_t ssa_name_map = NULL;
   edge redirected;
-  bitmap_iterator bi;
 
   if (!can_copy_bbs_p (region, n_region))
     return false;
@@ -5035,7 +4847,6 @@ tree_duplicate_sese_region (edge entry, edge exit,
      missuses of the functions.  I.e. if you ask to copy something weird,
      it will work, but the state of structures probably will not be
      correct.  */
-
   for (i = 0; i < n_region; i++)
     {
       /* We do not handle subloops, i.e. all the blocks must belong to the
@@ -5072,7 +4883,7 @@ tree_duplicate_sese_region (edge entry, edge exit,
       free_region_copy = true;
     }
 
-  gcc_assert (!any_marked_for_rewrite_p ());
+  gcc_assert (!need_ssa_update_p ());
 
   /* Record blocks outside the region that are duplicated by something
      inside.  */
@@ -5080,7 +4891,6 @@ tree_duplicate_sese_region (edge entry, edge exit,
   n_doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region, doms);
 
   copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop);
-  definitions = marked_ssa_names ();
 
   if (copying_header)
     {
@@ -5094,49 +4904,27 @@ tree_duplicate_sese_region (edge entry, edge exit,
   flush_pending_stmts (entry);
 
   /* Concerning updating of dominators:  We must recount dominators
-     for entry block and its copy.  Anything that is outside of the region, but
-     was dominated by something inside needs recounting as well.  */
+     for entry block and its copy.  Anything that is outside of the
+     region, but was dominated by something inside needs recounting as
+     well.  */
   set_immediate_dominator (CDI_DOMINATORS, entry->dest, entry->src);
   doms[n_doms++] = entry->dest->rbi->original;
   iterate_fix_dominators (CDI_DOMINATORS, doms, n_doms);
   free (doms);
 
-  /* Add the other phi node arguments.  */
+  /* Add the other PHI node arguments.  */
   add_phi_args_after_copy (region_copy, n_region);
 
-  /* Add phi nodes for definitions at exit.  TODO -- once we have immediate
-     uses, it should be possible to emit phi nodes just for definitions that
-     are used outside region.  */
-  EXECUTE_IF_SET_IN_BITMAP (definitions, 0, ver, bi)
-    {
-      tree name = ssa_name (ver);
-
-      phi = create_phi_node (name, exit->dest);
-      add_phi_arg (phi, name, exit);
-      add_phi_arg (phi, name, exit_copy);
-
-      SSA_NAME_DEF_STMT (name) = phi;
-    }
-
-  /* And create new definitions inside region and its copy.  TODO -- once we
-     have immediate uses, it might be better to leave definitions in region
-     unchanged, create new ssa names for phi nodes on exit, and rewrite
-     the uses, to avoid changing the copied region.  */
-  allocate_ssa_names (definitions, &ssa_name_map);
-  rewrite_to_new_ssa_names (region, n_region, ssa_name_map);
-  allocate_ssa_names (definitions, &ssa_name_map);
-  rewrite_to_new_ssa_names (region_copy, n_region, ssa_name_map);
-  htab_delete (ssa_name_map);
+  /* Update the SSA web.  */
+  update_ssa (TODO_update_ssa);
 
   if (free_region_copy)
     free (region_copy);
 
-  unmark_all_for_rewrite ();
-  BITMAP_FREE (definitions);
-
   return true;
 }
 
+
 /* Dump FUNCTION_DECL FN to file FILE using FLAGS (see TDF_* in tree.h)  */
 
 void