This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[ssaupdate] SSA form updating rewrite


Hello,

this patch cleans up and updates the current machinery for ssa form
updating.  The concrete improvements are

1) Registration of SSA names for that SSA form needs to be updated:

   We no longer allow multiple definitions for a single ssa name.
   Instead new SSA names are created for new definitions, and we
   just record that they are 'equivalent' to the original ssa name.

   This makes it possible to find all such definitions for ssa form
   updating without scanning the whole function, and to find the
   statements for such definitions easily.  It also makes the management
   of ssa names a bit cleaner.

   From future perspective, this enables the optimizations to refine
   the information stored in the ssa names even before the further steps
   to update ssa form are taken.

2) Utilities for direct updating of ssa form in simple cases (mostly to
   make it simpler to rewrite the uses in the code by new names):

   Use the registration of SSA names to make it easier to choose by
   which SSA name you want to have the use rewritten (so you do not
   have to allocate new ssa names by hand as it is done now, you just
   specify which of the equivalents of the original SSA name should be
   used).

3) Generic incremental SSA form updating (to be used in cases when
   full power of generic solution is needed, like for LCSSA form
   updating and some of the code duplication optimizations):

   Rewritten from scratch.  The code is no longer shared with
   tree-into-ssa, which makes is possible to optimize things more,
   and cleans up the code quite a lot.

   The algorithm is modified to work just with the area in that the
   interesting variables are live, which usually is much smaller
   than whole function body.  Using the immediate uses and local
   dominance information, we avoid scanning the statements in basic
   blocks completely (so we save time by not having to skip irrelevant
   statements).  With these improvements, it should be possible to use
   the function on "once per loop" scale without causing compile time
   problems, instead of the current "once per pass" restriction.

More information about usage of the functions and algorithm can be found
in comments in tree-update-ssa.c.

The changes are compile-time neutral (although the functions should be
more efficient than their predecessors, updating of ssa form does not
eat any significant time currently, so there is not much to improve
upon).

Zdenek

	* Makefile.in (tree-update-ssa.o): Add.
	* lambda-code.c (perfect_nestify): Do not call mark_for_rewrite
	and unmark_all_for_rewrite.
	* toplev.c (general_init): Call ssa_name_eqto_init.
	* tree-cfg.c (tree_duplicate_bb): Use rewrite_new_def instead of
	mark_for_rewrite.
	(add_phi_args_after_copy_bb): Check that the corresponding phi nodes
	have the same original ssa name.
	(struct ssa_name_map_entry, ssa_name_map_entry_hash,
	ssa_name_map_entry_eq, allocate_ssa_names,
	rewrite_to_new_ssa_names_def, rewrite_to_new_ssa_names_use,
	rewrite_to_new_ssa_names_bb, rewrite_to_new_ssa_names): Removed.
	(tree_duplicate_sese_region): Use new ssa updating functions.
	* tree-flow.h (rewrite_to_new_ssa_names_bb, rewrite_to_new_ssa_names,
	allocate_ssa_names, rewrite_ssa_into_ssa): Declaration removed.
	(struct usf_def_list, struct usf_use_list, struct ssa_update_value):
	New structures.
	(USF_PHIS_ALREADY_EXIST): New constant.
	(update_ssa_form, update_ssa_form_for_registered_defs, rewrite_new_def,
	original_equivalent_name, release_ssa_name_from_eqto,
	get_values_for_ssa_form_update, any_values_for_ssa_update_p,
	ssa_names_for_ssa_update, get_defs_to_update, determine_def_stmt,
	determine_def_bb, rewrite_uses_region, rewrite_uses_bb,
	free_def_list, ssa_form_updated, ssa_form_updated_all): Declare.
	* tree-into-ssa.c (struct def_blocks_d): Remove phi_blocks field.
	(struct mark_def_sites_global_data): Remove names_to_rename field.
	(struct ssa_name_info): Removed.
	(get_ssa_name_ann, ssa_mark_def_sites_initialize_block,
	ssa_mark_phi_uses, ssa_mark_def_sites, ssa_register_new_def,
	ssa_rewrite_phi_arguments, ssa_rewrite_finalize_block,
	ssa_rewrite_stmt, rewrite_ssa_into_ssa): Removed.
	(get_phi_state, set_phi_state, get_current_def, set_current_def,
	mark_def_sites, set_def_block, insert_phi_nodes, insert_phi_nodes_for,
	def_blocks_free, get_def_blocks_for, rewrite_into_ssa): Remove parts
	dealing with updating over ssa form.
	* tree-pretty-print.c (dump_generic_node): Dump the original ssa name
	for ssa names.
	* tree-ssa-dom.c (tree_ssa_dominator_optimize): Use
	update_ssa_form_for_registered_defs.
	* tree-ssa-loop-manip.c (add_exit_phis_edge, find_uses_to_rename_use,
	find_uses_to_rename_stmt, find_uses_to_rename,
	rewrite_into_loop_closed_ssa, rename_variables,
	tree_duplicate_loop_to_header_edge): Use new ssa form updating functions.
	(set_phi_def_stmts): Removed.
	* tree-ssa-threadupdate.c (copy_phis_to_block): Use the fact that phi
	nodes in copied block come in the same order as those in the original.
	* tree-ssanames.c (ssa_names_to_rewrite, marked_for_rewrite_p,
	any_marked_for_rewrite_p, mark_for_rewrite, unmark_all_for_rewrite,
	marked_ssa_names): Removed.
	(release_ssa_name): Do not check marked_for_rewrite_p, call
	release_ssa_name_from_eqto.
	* tree-update-ssa.c: New file.
	* tree.h (mark_for_rewrite, unmark_all_for_rewrite,
	marked_for_rewrite_p, any_marked_for_rewrite_p, marked_ssa_names):
	Declaration removed.
	(ssa_name_eqto_init): Declare.

Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.1409
diff -c -3 -p -r1.1409 Makefile.in
*** Makefile.in	7 Oct 2004 05:28:46 -0000	1.1409
--- Makefile.in	3 Nov 2004 00:00:19 -0000
*************** C_OBJS = c-parse.o c-lang.o stub-objc.o 
*** 888,894 ****
  OBJS-common = \
   tree-chrec.o tree-scalar-evolution.o tree-data-ref.o			   \
   tree-cfg.o tree-dfa.o tree-eh.o tree-ssa.o tree-optimize.o tree-gimple.o  \
!  gimplify.o tree-pretty-print.o tree-into-ssa.o          \
   tree-outof-ssa.o tree-ssa-ccp.o tree-vn.o             \
   tree-ssa-dce.o  tree-ssa-copy.o tree-nrv.o tree-ssa-copyrename.o  \
   tree-ssa-pre.o tree-ssa-live.o tree-ssa-operands.o tree-ssa-alias.o       \
--- 888,894 ----
  OBJS-common = \
   tree-chrec.o tree-scalar-evolution.o tree-data-ref.o			   \
   tree-cfg.o tree-dfa.o tree-eh.o tree-ssa.o tree-optimize.o tree-gimple.o  \
!  gimplify.o tree-pretty-print.o tree-into-ssa.o tree-update-ssa.o	   \
   tree-outof-ssa.o tree-ssa-ccp.o tree-vn.o             \
   tree-ssa-dce.o  tree-ssa-copy.o tree-nrv.o tree-ssa-copyrename.o  \
   tree-ssa-pre.o tree-ssa-live.o tree-ssa-operands.o tree-ssa-alias.o       \
*************** tree-into-ssa.o : tree-into-ssa.c $(TREE
*** 1609,1614 ****
--- 1609,1618 ----
     errors.h toplev.h function.h $(TIMEVAR_H) \
     $(TM_H) coretypes.h $(TREE_DUMP_H) langhooks.h domwalk.h tree-pass.h \
     $(GGC_H)
+ tree-update-ssa.o : tree-update-ssa.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
+    $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) output.h diagnostic.h \
+    errors.h toplev.h function.h $(TIMEVAR_H) \
+    $(TM_H) coretypes.h $(TREE_DUMP_H) langhooks.h
  tree-outof-ssa.o : tree-outof-ssa.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
     $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) output.h diagnostic.h \
     errors.h toplev.h function.h $(TIMEVAR_H) \
Index: lambda-code.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/lambda-code.c,v
retrieving revision 2.13.6.1
diff -c -3 -p -r2.13.6.1 lambda-code.c
*** lambda-code.c	17 Oct 2004 08:12:14 -0000	2.13.6.1
--- lambda-code.c	3 Nov 2004 00:00:19 -0000
*************** perfect_nestify (struct loops *loops,
*** 2305,2314 ****
  	return false;
        VEC_safe_push (tree, phis, PHI_RESULT (phi));
        VEC_safe_push (tree, phis, PHI_ARG_DEF (phi, 0));
-       mark_for_rewrite (PHI_RESULT (phi));
      }
    e = redirect_edge_and_branch (EDGE_SUCC (preheaderbb, 0), headerbb);
-   unmark_all_for_rewrite ();
    bb_ann (olddest)->phi_nodes = NULL;
    /* Add back the old exit phis.  */
    while (VEC_length (tree, phis) != 0)
--- 2305,2312 ----
Index: toplev.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/toplev.c,v
retrieving revision 1.927
diff -c -3 -p -r1.927 toplev.c
*** toplev.c	28 Sep 2004 20:34:17 -0000	1.927
--- toplev.c	3 Nov 2004 00:00:19 -0000
*************** general_init (const char *argv0)
*** 1620,1625 ****
--- 1620,1627 ----
    /* This must be done after add_params but before argument processing.  */
    init_ggc_heuristics();
    init_tree_optimization_passes ();
+ 
+   ssa_name_eqto_init ();
  }
  
  /* Process the options that have been parsed.  */
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-cfg.c,v
retrieving revision 2.73.4.5
diff -c -3 -p -r2.73.4.5 tree-cfg.c
*** tree-cfg.c	25 Oct 2004 06:37:29 -0000	2.73.4.5
--- tree-cfg.c	3 Nov 2004 00:00:19 -0000
*************** tree_duplicate_bb (basic_block bb)
*** 4505,4512 ****
  {
    basic_block new_bb;
    block_stmt_iterator bsi, bsi_tgt;
!   tree phi, val;
    ssa_op_iter op_iter;
  
    new_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
  
--- 4505,4513 ----
  {
    basic_block new_bb;
    block_stmt_iterator bsi, bsi_tgt;
!   tree phi, new_phi;
    ssa_op_iter op_iter;
+   def_operand_p def;
  
    new_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
  
*************** tree_duplicate_bb (basic_block bb)
*** 4515,4522 ****
       the same order, so that we can add them later.  */
    for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
      {
!       mark_for_rewrite (PHI_RESULT (phi));
!       create_phi_node (PHI_RESULT (phi), new_bb);
      }
    set_phi_nodes (new_bb, nreverse (phi_nodes (new_bb)));
  
--- 4516,4523 ----
       the same order, so that we can add them later.  */
    for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
      {
!       new_phi = create_phi_node (PHI_RESULT (phi), new_bb);
!       rewrite_new_def (new_phi, PHI_RESULT_PTR (new_phi));
      }
    set_phi_nodes (new_bb, nreverse (phi_nodes (new_bb)));
  
*************** tree_duplicate_bb (basic_block bb)
*** 4529,4540 ****
        if (TREE_CODE (stmt) == LABEL_EXPR)
  	continue;
  
-       /* Record the definitions.  */
        get_stmt_operands (stmt);
- 
-       FOR_EACH_SSA_TREE_OPERAND (val, stmt, op_iter, SSA_OP_ALL_DEFS)
- 	mark_for_rewrite (val);
- 
        copy = unshare_expr (stmt);
  
        /* Copy also the virtual operands.  */
--- 4530,4536 ----
*************** tree_duplicate_bb (basic_block bb)
*** 4542,4547 ****
--- 4538,4548 ----
        copy_virtual_operands (copy, stmt);
        
        bsi_insert_after (&bsi_tgt, copy, BSI_NEW_STMT);
+       get_stmt_operands (copy);
+ 
+       /* Record the definitions.  */
+       FOR_EACH_SSA_DEF_OPERAND (def, copy, op_iter, SSA_OP_ALL_DEFS)
+ 	rewrite_new_def (copy, def);
      }
  
    return new_bb;
*************** add_phi_args_after_copy_bb (basic_block 
*** 4591,4597 ****
  	{
  	  phi_next = TREE_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);
  	}
--- 4592,4599 ----
  	{
  	  phi_next = TREE_CHAIN (phi);
  
! 	  gcc_assert (original_equivalent_name (PHI_RESULT (phi))
! 		      == original_equivalent_name (PHI_RESULT (phi_copy)));
  	  def = PHI_ARG_DEF_FROM_EDGE (phi, e);
  	  add_phi_arg (&phi_copy, def, e_copy);
  	}
*************** add_phi_args_after_copy (basic_block *re
*** 4617,4806 ****
      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 = TREE_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);
-       get_stmt_operands (stmt);
-       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_OP_PTR (v_must_defs, i), stmt, map);
-     }
- 
-   FOR_EACH_EDGE (e, ei, bb->succs)
-     for (phi = phi_nodes (e->dest); phi; phi = TREE_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
--- 4619,4624 ----
*************** tree_duplicate_sese_region (edge entry, 
*** 4823,4829 ****
    bitmap definitions;
    tree phi, var;
    basic_block *doms;
-   htab_t ssa_name_map = NULL;
    edge redirected;
    bitmap_iterator bi;
  
--- 4641,4646 ----
*************** tree_duplicate_sese_region (edge entry, 
*** 4871,4877 ****
        free_region_copy = true;
      }
  
!   gcc_assert (!any_marked_for_rewrite_p ());
  
    /* Record blocks outside the region that are duplicated by something
       inside.  */
--- 4688,4694 ----
        free_region_copy = true;
      }
  
!   gcc_assert (!any_values_for_ssa_update_p ());
  
    /* Record blocks outside the region that are duplicated by something
       inside.  */
*************** tree_duplicate_sese_region (edge entry, 
*** 4879,4885 ****
    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)
      {
--- 4696,4702 ----
    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 = ssa_names_for_ssa_update ();
  
    if (copying_header)
      {
*************** tree_duplicate_sese_region (edge entry, 
*** 4912,4942 ****
       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);
  
    if (free_region_copy)
      free (region_copy);
  
-   unmark_all_for_rewrite ();
-   BITMAP_XFREE (definitions);
- 
    return true;
  }
  
--- 4729,4767 ----
       are used outside region.  */
    EXECUTE_IF_SET_IN_BITMAP (definitions, 0, ver, bi)
      {
!       tree name, new_orig_name;
!       struct usf_def_list *copy_def, *orig_def;
  
!       name = ssa_name (ver);
! 
!       /* First entry in the list should be the original definition,
! 	 the second one should be the one in the copy.  */
!       orig_def = get_defs_to_update (name);
!       copy_def = orig_def->next;
!       gcc_assert (DEF_FROM_PTR (orig_def->op) == name);
! 
!       /* Create new definition inside copied region.  */
!       new_orig_name = rewrite_new_def (determine_def_stmt (orig_def),
! 				       orig_def->op);
  
+       phi = create_phi_node (name, exit->dest);
+       add_phi_arg (&phi, new_orig_name, exit);
+       add_phi_arg (&phi, DEF_FROM_PTR (copy_def->op), exit_copy);
        SSA_NAME_DEF_STMT (name) = phi;
+ 
+       free_def_list (copy_def);
      }
+   BITMAP_XFREE (definitions);
  
!   /* Replace the uses in original region and its copy.  */
!   rewrite_uses_region (region, n_region, 2);
!   rewrite_uses_region (region_copy, n_region, 1);
! 
!   ssa_form_updated_all ();
  
    if (free_region_copy)
      free (region_copy);
  
    return true;
  }
  
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.52.4.4
diff -c -3 -p -r2.52.4.4 tree-flow.h
*** tree-flow.h	25 Oct 2004 06:37:30 -0000	2.52.4.4
--- tree-flow.h	3 Nov 2004 00:00:19 -0000
*************** extern bool tree_duplicate_sese_region (
*** 481,489 ****
  					basic_block *);
  extern void add_phi_args_after_copy_bb (basic_block);
  extern void add_phi_args_after_copy (basic_block *, unsigned);
- extern void rewrite_to_new_ssa_names_bb (basic_block, struct htab *);
- extern void rewrite_to_new_ssa_names (basic_block *, unsigned, htab_t);
- extern void allocate_ssa_names (bitmap, struct htab **);
  extern bool tree_purge_dead_eh_edges (basic_block);
  extern bool tree_purge_all_dead_eh_edges (bitmap);
  extern tree gimplify_val (block_stmt_iterator *, tree, tree);
--- 481,486 ----
*************** extern void kill_redundant_phi_nodes (vo
*** 568,574 ****
  
  /* In tree-into-ssa.c  */
  extern void rewrite_into_ssa (bool);
- extern void rewrite_ssa_into_ssa (void);
  
  void compute_global_livein (bitmap, bitmap);
  tree duplicate_ssa_name (tree, tree);
--- 565,570 ----
*************** extern bool expr_invariant_in_loop_p (st
*** 728,733 ****
--- 724,789 ----
  
  tree force_gimple_operand (tree, tree *, bool, tree);
  
+ /* SSA form updating:  */
+ 
+ /* List of defs of a value.  */
+ 
+ struct usf_def_list
+ {
+   def_operand_p op;		/* The position of the definition.  */
+   struct usf_def_list *next;	/* Next definition in the list.  */
+ };
+ 
+ /* List of uses of a value.  */
+ 
+ struct usf_use_list
+ {
+   use_operand_p op;		/* The position of the use.  */
+   struct usf_use_list *next;	/* Next use in the list.  */
+ };
+ 
+ /* Description of a value for that the ssa form should be updated.  */
+ 
+ struct ssa_update_value
+ {
+   tree decl;			/* Base for the new phi nodes.  */
+   tree orig_name;		/* Original ssa name from that the information
+ 				   attached to newly created names is
+ 				   copied.  */
+   struct usf_def_list *defs;	/* A list of definitions of the value.  */
+   struct usf_use_list *uses;	/* A list of uses of the value.  */
+   struct ssa_update_value *next;	/* Next value in the list.  */
+ 
+   /* For internal use of update_ssa_form.  */
+   unsigned id;			/* Id for the value.  */
+   bitmap life_area;		/* Area in that the value is live.  */
+   struct valdef *stack;		/* Stack of definitions of the value.  */
+ };
+ 
+ /* Possible flags for update_ssa_form.  */
+ 
+ enum update_ssa_form_flags
+ {
+   USF_PHIS_ALREADY_EXIST = 1
+ };
+ 
+ void update_ssa_form (struct ssa_update_value *, unsigned);
+ void update_ssa_form_for_registered_defs (unsigned);
+ tree rewrite_new_def (tree, def_operand_p);
+ tree original_equivalent_name (tree);
+ void release_ssa_name_from_eqto (tree);
+ struct ssa_update_value *get_values_for_ssa_form_update (void);
+ bool any_values_for_ssa_update_p (void);
+ bitmap ssa_names_for_ssa_update (void);
+ struct usf_def_list *get_defs_to_update (tree);
+ tree determine_def_stmt (const struct usf_def_list *);
+ basic_block determine_def_bb (const struct usf_def_list *);
+ void rewrite_uses_region (basic_block *, unsigned, unsigned);
+ void rewrite_uses_bb (basic_block, unsigned);
+ void free_def_list (struct usf_def_list *);
+ void ssa_form_updated (tree);
+ void ssa_form_updated_all (void);
+ 
  #include "tree-flow-inline.h"
  
  #endif /* _TREE_FLOW_H  */
Index: tree-into-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-into-ssa.c,v
retrieving revision 2.24.10.2
diff -c -3 -p -r2.24.10.2 tree-into-ssa.c
*** tree-into-ssa.c	25 Oct 2004 06:37:30 -0000	2.24.10.2
--- tree-into-ssa.c	3 Nov 2004 00:00:20 -0000
*************** struct def_blocks_d
*** 66,74 ****
       Ith block contains a definition of VAR.  */
    bitmap def_blocks;
  
-   /* Blocks that contain a phi node for VAR.  */
-   bitmap phi_blocks;
- 
    /* Blocks where VAR is live-on-entry.  Similar semantics as
       DEF_BLOCKS.  */
    bitmap livein_blocks;
--- 66,71 ----
*************** struct mark_def_sites_global_data
*** 119,140 ****
       solely to avoid the overhead of allocating and deallocating
       the bitmap.  */
    sbitmap kills;
- 
-   /* Bitmap of names to rename.  */
-   sbitmap names_to_rename;
- };
- 
- /* Information stored for ssa names.  */
- 
- struct ssa_name_info
- {
-   /* This field indicates whether or not the variable may need PHI nodes.
-      See the enum's definition for more detailed information about the
-      states.  */
-   ENUM_BITFIELD (need_phi_state) need_phi_state : 2;
- 
-   /* The actual definition of the ssa name.  */
-   tree current_def;
  };
  
  /* Local functions.  */
--- 116,121 ----
*************** static void mark_def_sites (struct dom_w
*** 145,155 ****
  			    basic_block bb, block_stmt_iterator);
  static void mark_def_sites_initialize_block (struct dom_walk_data *walk_data,
  					     basic_block bb);
! static void set_def_block (tree, basic_block, bool, bool);
  static void set_livein_block (tree, basic_block);
  static bool prepare_use_operand_for_rename (use_operand_p, size_t *uid_p);
  static bool prepare_def_operand_for_rename (tree def, size_t *uid_p);
! static void insert_phi_nodes (bitmap *, bitmap);
  static void rewrite_stmt (struct dom_walk_data *, basic_block,
  			  block_stmt_iterator);
  static inline void rewrite_operand (use_operand_p);
--- 126,136 ----
  			    basic_block bb, block_stmt_iterator);
  static void mark_def_sites_initialize_block (struct dom_walk_data *walk_data,
  					     basic_block bb);
! static void set_def_block (tree, basic_block);
  static void set_livein_block (tree, basic_block);
  static bool prepare_use_operand_for_rename (use_operand_p, size_t *uid_p);
  static bool prepare_def_operand_for_rename (tree def, size_t *uid_p);
! static void insert_phi_nodes (bitmap *);
  static void rewrite_stmt (struct dom_walk_data *, basic_block,
  			  block_stmt_iterator);
  static inline void rewrite_operand (use_operand_p);
*************** static inline struct def_blocks_d *get_d
*** 163,188 ****
  static inline struct def_blocks_d *find_def_blocks_for (tree);
  static void htab_statistics (FILE *, htab_t);
  
- /* Get the information associated with NAME.  */
- 
- static inline struct ssa_name_info *
- get_ssa_name_ann (tree name)
- {
-   if (!SSA_NAME_AUX (name))
-     SSA_NAME_AUX (name) = xcalloc (1, sizeof (struct ssa_name_info));
- 
-   return SSA_NAME_AUX (name);
- }
- 
  /* Gets phi_state field for VAR.  */
  
  static inline enum need_phi_state
  get_phi_state (tree var)
  {
!   if (TREE_CODE (var) == SSA_NAME)
!     return get_ssa_name_ann (var)->need_phi_state;
!   else
!     return var_ann (var)->need_phi_state;
  }
  
  /* Sets phi_state field for VAR to STATE.  */
--- 144,155 ----
  static inline struct def_blocks_d *find_def_blocks_for (tree);
  static void htab_statistics (FILE *, htab_t);
  
  /* Gets phi_state field for VAR.  */
  
  static inline enum need_phi_state
  get_phi_state (tree var)
  {
!   return var_ann (var)->need_phi_state;
  }
  
  /* Sets phi_state field for VAR to STATE.  */
*************** get_phi_state (tree var)
*** 190,199 ****
  static inline void
  set_phi_state (tree var, enum need_phi_state state)
  {
!   if (TREE_CODE (var) == SSA_NAME)
!     get_ssa_name_ann (var)->need_phi_state = state;
!   else
!     var_ann (var)->need_phi_state = state;
  }
  
  /* Return the current definition for VAR.  */
--- 157,163 ----
  static inline void
  set_phi_state (tree var, enum need_phi_state state)
  {
!   var_ann (var)->need_phi_state = state;
  }
  
  /* Return the current definition for VAR.  */
*************** set_phi_state (tree var, enum need_phi_s
*** 201,210 ****
  static inline tree
  get_current_def (tree var)
  {
!   if (TREE_CODE (var) == SSA_NAME)
!     return get_ssa_name_ann (var)->current_def;
!   else
!     return var_ann (var)->current_def;
  }
  
  /* Sets current definition of VAR to DEF.  */
--- 165,171 ----
  static inline tree
  get_current_def (tree var)
  {
!   return var_ann (var)->current_def;
  }
  
  /* Sets current definition of VAR to DEF.  */
*************** get_current_def (tree var)
*** 212,221 ****
  static inline void
  set_current_def (tree var, tree def)
  {
!   if (TREE_CODE (var) == SSA_NAME)
!     get_ssa_name_ann (var)->current_def = def;
!   else
!     var_ann (var)->current_def = def;
  }
  
  /* Compute global livein information given the set of blockx where
--- 173,179 ----
  static inline void
  set_current_def (tree var, tree def)
  {
!   var_ann (var)->current_def = def;
  }
  
  /* Compute global livein information given the set of blockx where
*************** mark_def_sites_initialize_block (struct 
*** 284,348 ****
    sbitmap_zero (kills);
  }
  
- /* Block initialization routine for mark_def_sites.  Clear the 
-    KILLS bitmap at the start of each block.  */
- 
- static void
- ssa_mark_def_sites_initialize_block (struct dom_walk_data *walk_data,
- 				     basic_block bb)
- {
-   struct mark_def_sites_global_data *gd = walk_data->global_data;
-   sbitmap kills = gd->kills;
-   tree phi, def;
-   unsigned def_uid;
- 
-   sbitmap_zero (kills);
- 
-   for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
-     {
-       def = PHI_RESULT (phi);
-       def_uid = SSA_NAME_VERSION (def);
- 
-       if (!TEST_BIT (gd->names_to_rename, def_uid))
- 	continue;
- 
-       set_def_block (def, bb, true, true);
-       SET_BIT (kills, def_uid);
-     }
- }
- 
- /* Marks ssa names used as arguments of phis at the end of BB.  */
- 
- static void
- ssa_mark_phi_uses (struct dom_walk_data *walk_data, basic_block bb)
- {
-   struct mark_def_sites_global_data *gd = walk_data->global_data;
-   sbitmap kills = gd->kills;
-   edge e;
-   tree phi, use;
-   unsigned uid;
-   edge_iterator ei;
- 
-   FOR_EACH_EDGE (e, ei, bb->succs)
-     {
-       if (e->dest == EXIT_BLOCK_PTR)
- 	continue;
- 
-       for (phi = phi_nodes (e->dest); phi; phi = TREE_CHAIN (phi))
- 	{
- 	  use = PHI_ARG_DEF_FROM_EDGE (phi, e);
- 	  if (TREE_CODE (use) != SSA_NAME)
- 	    continue;
- 
- 	  uid = SSA_NAME_VERSION (use);
- 
- 	  if (TEST_BIT (gd->names_to_rename, uid)
- 	      && !TEST_BIT (kills, uid))
- 	    set_livein_block (use, bb);
- 	}
-     }
- }
- 
  /* Call back for walk_dominator_tree used to collect definition sites
     for every variable in the function.  For every statement S in block
     BB:
--- 242,247 ----
*************** mark_def_sites (struct dom_walk_data *wa
*** 402,408 ****
  	    SET_DEF (def_p, USE_FROM_PTR (use_p));
  	    
            set_livein_block (USE_FROM_PTR (use_p), bb);
! 	  set_def_block (DEF_FROM_PTR (def_p), bb, false, false);
  	}
      }
  
--- 301,307 ----
  	    SET_DEF (def_p, USE_FROM_PTR (use_p));
  	    
            set_livein_block (USE_FROM_PTR (use_p), bb);
! 	  set_def_block (DEF_FROM_PTR (def_p), bb);
  	}
      }
  
*************** mark_def_sites (struct dom_walk_data *wa
*** 411,478 ****
      {
        if (prepare_def_operand_for_rename (def, &uid))
  	{
! 	  set_def_block (def, bb, false, false);
  	  SET_BIT (kills, uid);
  	}
      }
  
  }
  
! /* Ditto, but works over ssa names.  */
! 
! static void
! ssa_mark_def_sites (struct dom_walk_data *walk_data,
! 		    basic_block bb,
! 		    block_stmt_iterator bsi)
! {
!   struct mark_def_sites_global_data *gd = walk_data->global_data;
!   sbitmap kills = gd->kills;
!   size_t uid, def_uid;
!   tree stmt, use, def;
!   ssa_op_iter iter;
! 
!   /* Mark all the blocks that have definitions for each variable in the
!      names_to_rename bitmap.  */
!   stmt = bsi_stmt (bsi);
!   update_stmt_if_modified (stmt);
! 
!   /* If a variable is used before being set, then the variable is live
!      across a block boundary, so mark it live-on-entry to BB.  */
!   FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_ALL_USES)
!     {
!       uid = SSA_NAME_VERSION (use);
! 
!       if (TEST_BIT (gd->names_to_rename, uid)
! 	  && !TEST_BIT (kills, uid))
! 	set_livein_block (use, bb);
!     }
! 	  
!   /* Now process the definition made by this statement.  Mark the
!      variables in KILLS.  */
!   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
!     {
!       def_uid = SSA_NAME_VERSION (def);
! 
!       if (TEST_BIT (gd->names_to_rename, def_uid))
! 	{
! 	  set_def_block (def, bb, false, true);
! 	  SET_BIT (kills, def_uid);
! 	}
!     }
! }
! 
! /* Mark block BB as the definition site for variable VAR.  PHI_P is true if
!    VAR is defined by a phi node.  SSA_P is true if we are called from
!    rewrite_ssa_into_ssa.  */
  
  static void
! set_def_block (tree var, basic_block bb, bool phi_p, bool ssa_p)
  {
    struct def_blocks_d *db_p;
    enum need_phi_state state;
  
!   if (!ssa_p
!       && TREE_CODE (var) == SSA_NAME)
      var = SSA_NAME_VAR (var);
  
    state = get_phi_state (var);
--- 310,331 ----
      {
        if (prepare_def_operand_for_rename (def, &uid))
  	{
! 	  set_def_block (def, bb);
  	  SET_BIT (kills, uid);
  	}
      }
  
  }
  
! /* Mark block BB as the definition site for variable VAR.  */
  
  static void
! set_def_block (tree var, basic_block bb)
  {
    struct def_blocks_d *db_p;
    enum need_phi_state state;
  
!   if (TREE_CODE (var) == SSA_NAME)
      var = SSA_NAME_VAR (var);
  
    state = get_phi_state (var);
*************** set_def_block (tree var, basic_block bb,
*** 480,487 ****
  
    /* Set the bit corresponding to the block where VAR is defined.  */
    bitmap_set_bit (db_p->def_blocks, bb->index);
-   if (phi_p)
-     bitmap_set_bit (db_p->phi_blocks, bb->index);
  
    /* Keep track of whether or not we may need to insert phi nodes.
  
--- 333,338 ----
*************** void insert_phi_nodes_1 (tree var, bitma
*** 597,607 ****
     the flowgraph.  PHI nodes will only be inserted at the dominance
     frontier of definition blocks for variables whose NEED_PHI_STATE
     annotation is marked as ``maybe'' or ``unknown'' (computed by
!    mark_def_sites).  If NAMES_TO_RENAME is not NULL, do the same but
!    for ssa name rewriting.  */
  
  static void
! insert_phi_nodes (bitmap *dfs, bitmap names_to_rename)
  {
    size_t i;
    varray_type work_stack;
--- 448,457 ----
     the flowgraph.  PHI nodes will only be inserted at the dominance
     frontier of definition blocks for variables whose NEED_PHI_STATE
     annotation is marked as ``maybe'' or ``unknown'' (computed by
!    mark_def_sites).  */
  
  static void
! insert_phi_nodes (bitmap *dfs)
  {
    size_t i;
    varray_type work_stack;
*************** insert_phi_nodes (bitmap *dfs, bitmap na
*** 617,631 ****
       to the work list all the blocks that have a definition for the
       variable.  PHI nodes will be added to the dominance frontier blocks of
       each definition block.  */
!   if (names_to_rename)
!     {
!       EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, bi)
! 	{
! 	  if (ssa_name (i))
! 	    insert_phi_nodes_1 (ssa_name (i), dfs, &work_stack);
! 	}
!     }
!   else if (vars_to_rename)
      EXECUTE_IF_SET_IN_BITMAP (vars_to_rename, 0, i, bi)
        {
  	insert_phi_nodes_1 (referenced_var (i), dfs, &work_stack);
--- 467,473 ----
       to the work list all the blocks that have a definition for the
       variable.  PHI nodes will be added to the dominance frontier blocks of
       each definition block.  */
!   if (vars_to_rename)
      EXECUTE_IF_SET_IN_BITMAP (vars_to_rename, 0, i, bi)
        {
  	insert_phi_nodes_1 (referenced_var (i), dfs, &work_stack);
*************** rewrite_initialize_block (struct dom_wal
*** 691,772 ****
      }
  }
  
- /* Register DEF (an SSA_NAME) to be a new definition for the original
-    ssa name VAR and push VAR's current reaching definition
-    into the stack pointed by BLOCK_DEFS_P.  */
- 
- static void
- ssa_register_new_def (tree var, tree def)
- {
-   tree currdef;
-    
-   /* If this variable is set in a single basic block and all uses are
-      dominated by the set(s) in that single basic block, then there is
-      nothing to do.  TODO we should not be called at all, and just
-      keep the original name.  */
-   if (get_phi_state (var) == NEED_PHI_STATE_NO)
-     {
-       set_current_def (var, def);
-       return;
-     }
- 
-   currdef = get_current_def (var);
- 
-   /* Push the current reaching definition into *BLOCK_DEFS_P.  This stack is
-      later used by the dominator tree callbacks to restore the reaching
-      definitions for all the variables defined in the block after a recursive
-      visit to all its immediately dominated blocks.  */
-   VARRAY_PUSH_TREE (block_defs_stack, currdef);
-   VARRAY_PUSH_TREE (block_defs_stack, var);
- 
-   /* Set the current reaching definition for VAR to be DEF.  */
-   set_current_def (var, def);
- }
- 
- /* Ditto, for rewriting ssa names.  */
- 
- static void
- ssa_rewrite_initialize_block (struct dom_walk_data *walk_data, basic_block bb)
- {
-   tree phi, new_name;
-   sbitmap names_to_rename = walk_data->global_data;
-   edge e;
-   bool abnormal_phi;
-   edge_iterator ei;
- 
-   if (dump_file && (dump_flags & TDF_DETAILS))
-     fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index);
- 
-   /* Mark the unwind point for this block.  */
-   VARRAY_PUSH_TREE (block_defs_stack, NULL_TREE);
- 
-   FOR_EACH_EDGE (e, ei, bb->preds)
-     if (e->flags & EDGE_ABNORMAL)
-       break;
-   abnormal_phi = (e != NULL);
- 
-   /* Step 1.  Register new definitions for every PHI node in the block.
-      Conceptually, all the PHI nodes are executed in parallel and each PHI
-      node introduces a new version for the associated variable.  */
-   for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
-     {
-       tree result = PHI_RESULT (phi);
- 
-       if (TEST_BIT (names_to_rename, SSA_NAME_VERSION (result)))
- 	{
- 	  new_name = duplicate_ssa_name (result, phi);
- 	  SET_PHI_RESULT (phi, new_name);
- 
- 	  if (abnormal_phi)
- 	    SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name) = 1;
- 	}
-       else
- 	new_name = result;
- 
-       ssa_register_new_def (result, new_name);
-     }
- }
- 
  /* SSA Rewriting Step 3.  Visit all the successor blocks of BB looking for
     PHI nodes.  For every PHI node found, add a new argument containing the
     current reaching definition for the variable and the edge through which
--- 533,538 ----
*************** rewrite_add_phi_arguments (struct dom_wa
*** 799,838 ****
      }
  }
  
- /* Ditto, for ssa name rewriting.  */
- 
- static void
- ssa_rewrite_phi_arguments (struct dom_walk_data *walk_data, basic_block bb)
- {
-   edge e;
-   sbitmap names_to_rename = walk_data->global_data;
-   use_operand_p op;
-   edge_iterator ei;
- 
-   FOR_EACH_EDGE (e, ei, bb->succs)
-     {
-       tree phi;
- 
-       if (e->dest == EXIT_BLOCK_PTR)
- 	continue;
- 
-       for (phi = phi_nodes (e->dest); phi; phi = TREE_CHAIN (phi))
- 	{
- 	  op = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
- 	  if (TREE_CODE (USE_FROM_PTR (op)) != SSA_NAME)
- 	    continue;
- 
- 	  if (!TEST_BIT (names_to_rename, SSA_NAME_VERSION (USE_FROM_PTR (op))))
- 	    continue;
- 
- 	  SET_USE (op, get_reaching_def (USE_FROM_PTR (op)));
- 	  if (e->flags & EDGE_ABNORMAL)
- 	    SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (op)) = 1;
- 	}
-     }
- }
- 
- 
  /* Similar to restore_vars_to_original_value, except that it restores 
     CURRDEFS to its original value.  */
  static void
--- 565,570 ----
*************** rewrite_finalize_block (struct dom_walk_
*** 869,900 ****
      }
  }
  
- /* Ditto, for rewriting ssa names.  */
- 
- static void
- ssa_rewrite_finalize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
- 			    basic_block bb ATTRIBUTE_UNUSED)
- {
- 
-   /* Step 5.  Restore the current reaching definition for each variable
-      referenced in the block (in reverse order).  */
-   while (VARRAY_ACTIVE_SIZE (block_defs_stack) > 0)
-     {
-       tree var = VARRAY_TOP_TREE (block_defs_stack);
-       tree saved_def;
- 
-       VARRAY_POP (block_defs_stack);
-       
-       if (var == NULL)
- 	break;
- 
-       saved_def = VARRAY_TOP_TREE (block_defs_stack);
-       VARRAY_POP (block_defs_stack);
- 
-       set_current_def (var, saved_def);
-     }
- }
- 
  /* Dump SSA information to FILE.  */
  
  void
--- 601,606 ----
*************** insert_phi_nodes_for (tree var, bitmap *
*** 1019,1028 ****
  	}
      }
  
-   /* Remove the blocks where we already have the phis.  */
-   bitmap_operation (phi_insertion_points, phi_insertion_points,
- 		    def_map->phi_blocks, BITMAP_AND_COMPL);
- 
    /* Now compute global livein for this variable.  Note this modifies
       def_map->livein_blocks.  */
    compute_global_livein (def_map->livein_blocks, def_map->def_blocks);
--- 725,730 ----
*************** rewrite_stmt (struct dom_walk_data *walk
*** 1092,1145 ****
      }
  }
  
- /* Ditto, for rewriting ssa names.  */
- 
- static void
- ssa_rewrite_stmt (struct dom_walk_data *walk_data,
- 		  basic_block bb ATTRIBUTE_UNUSED,
- 		  block_stmt_iterator si)
- {
-   stmt_ann_t ann;
-   tree stmt, var;
-   ssa_op_iter iter;
-   use_operand_p use_p;
-   def_operand_p def_p;
-   sbitmap names_to_rename = walk_data->global_data;
- 
-   stmt = bsi_stmt (si);
-   ann = stmt_ann (stmt);
- 
-   if (dump_file && (dump_flags & TDF_DETAILS))
-     {
-       fprintf (dump_file, "Renaming statement ");
-       print_generic_stmt (dump_file, stmt, TDF_SLIM);
-       fprintf (dump_file, "\n");
-     }
- 
-   /* We have just scanned the code for operands.  No statement should
-      be modified.  */
-   gcc_assert (!ann->modified);
- 
-   /* Step 1.  Rewrite USES and VUSES in the statement.  */
-   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
-     {
-       if (TEST_BIT (names_to_rename, SSA_NAME_VERSION (USE_FROM_PTR (use_p))))
- 	SET_USE (use_p, get_reaching_def (USE_FROM_PTR (use_p)));
-     }
- 
-   /* Step 2.  Register the statement's DEF and VDEF operands.  */
-   FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
-     {
-       var = DEF_FROM_PTR (def_p);
- 
-       if (!TEST_BIT (names_to_rename, SSA_NAME_VERSION (var)))
- 	continue;
- 
-       SET_DEF (def_p, duplicate_ssa_name (var, stmt));
-       ssa_register_new_def (var, DEF_FROM_PTR (def_p));
-     }
- }
- 
  /* Replace the operand pointed by OP_P with its immediate reaching
     definition.  */
  
--- 794,799 ----
*************** def_blocks_free (void *p)
*** 1249,1255 ****
  {
    struct def_blocks_d *entry = p;
    BITMAP_XFREE (entry->def_blocks);
-   BITMAP_XFREE (entry->phi_blocks);
    BITMAP_XFREE (entry->livein_blocks);
    free (entry);
  }
--- 903,908 ----
*************** get_def_blocks_for (tree var)
*** 1321,1327 ****
        db_p = xmalloc (sizeof (*db_p));
        db_p->var = var;
        db_p->def_blocks = BITMAP_XMALLOC ();
-       db_p->phi_blocks = BITMAP_XMALLOC ();
        db_p->livein_blocks = BITMAP_XMALLOC ();
        *slot = (void *) db_p;
      }
--- 974,979 ----
*************** rewrite_into_ssa (bool all)
*** 1495,1501 ****
    sbitmap_free (mark_def_sites_global_data.kills);
  
    /* Insert PHI nodes at dominance frontiers of definition blocks.  */
!   insert_phi_nodes (dfs, NULL);
  
    /* Rewrite all the basic blocks in the program.  */
    timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
--- 1147,1153 ----
    sbitmap_free (mark_def_sites_global_data.kills);
  
    /* Insert PHI nodes at dominance frontiers of definition blocks.  */
!   insert_phi_nodes (dfs);
  
    /* Rewrite all the basic blocks in the program.  */
    timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
*************** rewrite_into_ssa (bool all)
*** 1545,1702 ****
    timevar_pop (TV_TREE_SSA_OTHER);
  }
  
- /* The marked ssa names may have more than one definition;
-    add phi nodes and rewrite them to fix this.  */
- 
- void
- rewrite_ssa_into_ssa (void)
- {
-   bitmap *dfs;
-   basic_block bb;
-   struct dom_walk_data walk_data;
-   struct mark_def_sites_global_data mark_def_sites_global_data;
-   unsigned i;
-   sbitmap snames_to_rename;
-   tree name;
-   bitmap to_rename;
-   bitmap_iterator bi;
-   
-   if (!any_marked_for_rewrite_p ())
-     return;
-   to_rename = marked_ssa_names ();
- 
-   timevar_push (TV_TREE_SSA_OTHER);
- 
-   /* Allocate memory for the DEF_BLOCKS hash table.  */
-   def_blocks = htab_create (num_ssa_names,
- 			    def_blocks_hash, def_blocks_eq, def_blocks_free);
- 
-   /* Initialize dominance frontier and immediate dominator bitmaps. 
-      Also count the number of predecessors for each block.  Doing so
-      can save significant time during PHI insertion for large graphs.  */
-   dfs = (bitmap *) xmalloc (last_basic_block * sizeof (bitmap *));
-   FOR_EACH_BB (bb)
-     dfs[bb->index] = BITMAP_XMALLOC ();
- 
-   /* Ensure that the dominance information is OK.  */
-   calculate_dominance_info (CDI_DOMINATORS);
- 
-   /* Compute dominance frontiers.  */
-   compute_dominance_frontiers (dfs);
- 
-   /* Setup callbacks for the generic dominator tree walker to find and
-      mark definition sites.  */
-   walk_data.walk_stmts_backward = false;
-   walk_data.dom_direction = CDI_DOMINATORS;
-   walk_data.initialize_block_local_data = NULL;
-   walk_data.before_dom_children_before_stmts
- 	  = ssa_mark_def_sites_initialize_block;
-   walk_data.before_dom_children_walk_stmts = ssa_mark_def_sites;
-   walk_data.before_dom_children_after_stmts = ssa_mark_phi_uses; 
-   walk_data.after_dom_children_before_stmts =  NULL;
-   walk_data.after_dom_children_walk_stmts =  NULL;
-   walk_data.after_dom_children_after_stmts =  NULL;
- 
-   snames_to_rename = sbitmap_alloc (num_ssa_names);
-   sbitmap_zero (snames_to_rename);
-   EXECUTE_IF_SET_IN_BITMAP (to_rename, 0, i, bi)
-     {
-       SET_BIT (snames_to_rename, i);
-     }
- 
-   mark_def_sites_global_data.kills = sbitmap_alloc (num_ssa_names);
-   mark_def_sites_global_data.names_to_rename = snames_to_rename;
-   walk_data.global_data = &mark_def_sites_global_data;
- 
-   VARRAY_TREE_INIT (block_defs_stack, 10, "Block DEFS Stack");
- 
-   /* We do not have any local data.  */
-   walk_data.block_local_data_size = 0;
- 
-   /* Initialize the dominator walker.  */
-   init_walk_dominator_tree (&walk_data);
- 
-   /* Recursively walk the dominator tree.  */
-   walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
- 
-   /* Finalize the dominator walker.  */
-   fini_walk_dominator_tree (&walk_data);
- 
-   /* We no longer need this bitmap, clear and free it.  */
-   sbitmap_free (mark_def_sites_global_data.kills);
- 
-   for (i = 1; i < num_ssa_names; i++)
-     if (ssa_name (i))
-       set_current_def (ssa_name (i), NULL_TREE);
- 
-   /* Insert PHI nodes at dominance frontiers of definition blocks.  */
-   insert_phi_nodes (dfs, to_rename);
- 
-   /* Rewrite all the basic blocks in the program.  */
-   timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
- 
-   /* Setup callbacks for the generic dominator tree walker.  */
-   walk_data.walk_stmts_backward = false;
-   walk_data.dom_direction = CDI_DOMINATORS;
-   walk_data.initialize_block_local_data = NULL;
-   walk_data.before_dom_children_before_stmts = ssa_rewrite_initialize_block;
-   walk_data.before_dom_children_walk_stmts = ssa_rewrite_stmt;
-   walk_data.before_dom_children_after_stmts = ssa_rewrite_phi_arguments;
-   walk_data.after_dom_children_before_stmts = NULL;
-   walk_data.after_dom_children_walk_stmts =  NULL;
-   walk_data.after_dom_children_after_stmts =  ssa_rewrite_finalize_block;
-   walk_data.global_data = snames_to_rename;
-   walk_data.block_local_data_size = 0;
- 
-   /* Initialize the dominator walker.  */
-   init_walk_dominator_tree (&walk_data);
- 
-   /* Recursively walk the dominator tree rewriting each statement in
-      each basic block.  */
-   walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
- 
-   /* Finalize the dominator walker.  */
-   fini_walk_dominator_tree (&walk_data);
- 
-   unmark_all_for_rewrite ();
- 
-   EXECUTE_IF_SET_IN_BITMAP (to_rename, 0, i, bi)
-     {
-       release_ssa_name (ssa_name (i));
-     }
- 
-   sbitmap_free (snames_to_rename);
- 
-   timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS);
- 
-   /* Debugging dumps.  */
-   if (dump_file && (dump_flags & TDF_STATS))
-     {
-       dump_dfa_stats (dump_file);
-       dump_tree_ssa_stats (dump_file);
-     }
- 
-   /* Free allocated memory.  */
-   FOR_EACH_BB (bb)
-     BITMAP_XFREE (dfs[bb->index]);
-   free (dfs);
- 
-   htab_delete (def_blocks);
- 
-   for (i = 1; i < num_ssa_names; i++)
-     {
-       name = ssa_name (i);
-       if (!name || !SSA_NAME_AUX (name))
- 	continue;
- 
-       free (SSA_NAME_AUX (name));
-       SSA_NAME_AUX (name) = NULL;
-     }
- 
-   BITMAP_XFREE (to_rename);
-   timevar_pop (TV_TREE_SSA_OTHER);
- }
- 
  /* Rewrites all variables into ssa.  */
  
  static void
--- 1197,1202 ----
Index: tree-pretty-print.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-pretty-print.c,v
retrieving revision 2.46.2.3
diff -c -3 -p -r2.46.2.3 tree-pretty-print.c
*** tree-pretty-print.c	25 Oct 2004 06:37:31 -0000	2.46.2.3
--- tree-pretty-print.c	3 Nov 2004 00:00:20 -0000
*************** dump_generic_node (pretty_printer *buffe
*** 1454,1462 ****
        break;
  
      case SSA_NAME:
!       dump_generic_node (buffer, SSA_NAME_VAR (node), spc, flags, false);
!       pp_string (buffer, "_");
!       pp_decimal_int (buffer, SSA_NAME_VERSION (node));
        break;
  
      case WITH_SIZE_EXPR:
--- 1454,1474 ----
        break;
  
      case SSA_NAME:
!       {
! 	tree orig;
! 
! 	dump_generic_node (buffer, SSA_NAME_VAR (node), spc, flags, false);
! 	pp_string (buffer, "_");
! 	pp_decimal_int (buffer, SSA_NAME_VERSION (node));
! 	orig = original_equivalent_name (node);
! 
! 	if (orig != node)
! 	  {
! 	    pp_string (buffer, "{eqto ");
! 	    dump_generic_node (buffer, orig, spc, flags, false);
! 	    pp_string (buffer, "}");
! 	  }
!       }
        break;
  
      case WITH_SIZE_EXPR:
Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-dom.c,v
retrieving revision 2.58.6.3
diff -c -3 -p -r2.58.6.3 tree-ssa-dom.c
*** tree-ssa-dom.c	25 Oct 2004 06:37:31 -0000	2.58.6.3
--- tree-ssa-dom.c	3 Nov 2004 00:00:20 -0000
*************** tree_ssa_dominator_optimize (void)
*** 387,393 ****
        cfg_altered = cleanup_tree_cfg ();
        calculate_dominance_info (CDI_DOMINATORS);
  
!       rewrite_ssa_into_ssa ();
  
        /* Reinitialize the various tables.  */
        bitmap_clear (nonzero_vars);
--- 387,393 ----
        cfg_altered = cleanup_tree_cfg ();
        calculate_dominance_info (CDI_DOMINATORS);
  
!       update_ssa_form_for_registered_defs (0);
  
        /* Reinitialize the various tables.  */
        bitmap_clear (nonzero_vars);
Index: tree-ssa-loop-manip.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-manip.c,v
retrieving revision 2.9.12.1
diff -c -3 -p -r2.9.12.1 tree-ssa-loop-manip.c
*** tree-ssa-loop-manip.c	17 Oct 2004 08:12:15 -0000	2.9.12.1
--- tree-ssa-loop-manip.c	3 Nov 2004 00:00:20 -0000
*************** add_exit_phis_edge (basic_block exit, tr
*** 138,148 ****
      return;
  
    phi = create_phi_node (use, exit);
! 
    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.
--- 138,146 ----
      return;
  
    phi = create_phi_node (use, exit);
!   rewrite_new_def (phi, PHI_RESULT_PTR (phi));
    FOR_EACH_EDGE (e, ei, exit->preds)
      add_phi_arg (&phi, use, e);
  }
  
  /* Add exit phis for VAR that is used in LIVEIN.
*************** get_loops_exits (void)
*** 211,220 ****
  
  /* 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.  */
  
  static void
! find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks)
  {
    unsigned ver;
    basic_block def_bb;
--- 209,219 ----
  
  /* 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.  Record the ssa name index to NEED_PHIS bitmap.  */
  
  static void
! find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks,
! 			 bitmap need_phis)
  {
    unsigned ver;
    basic_block def_bb;
*************** find_uses_to_rename_use (basic_block bb,
*** 237,252 ****
      use_blocks[ver] = BITMAP_XMALLOC ();
    bitmap_set_bit (use_blocks[ver], bb->index);
  
!   if (!flow_bb_inside_loop_p (def_loop, bb))
!     mark_for_rewrite (use);
  }
  
  /* 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.  */
  
  static void
! find_uses_to_rename_stmt (tree stmt, bitmap *use_blocks)
  {
    ssa_op_iter iter;
    tree var;
--- 236,251 ----
      use_blocks[ver] = BITMAP_XMALLOC ();
    bitmap_set_bit (use_blocks[ver], bb->index);
  
!   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 and the ssa names themselves to
!    NEED_PHIS.  */
  
  static void
! find_uses_to_rename_stmt (tree stmt, bitmap *use_blocks, bitmap need_phis)
  {
    ssa_op_iter iter;
    tree var;
*************** find_uses_to_rename_stmt (tree stmt, bit
*** 255,269 ****
    get_stmt_operands (stmt);
  
    FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES)
!     find_uses_to_rename_use (bb, var, use_blocks);
  }
  
  /* Marks names that are used 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.  */
  
  static void
! find_uses_to_rename (bitmap *use_blocks)
  {
    basic_block bb;
    block_stmt_iterator bsi;
--- 254,269 ----
    get_stmt_operands (stmt);
  
    FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES)
!     find_uses_to_rename_use (bb, var, use_blocks, need_phis);
  }
  
  /* Marks names that are used 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 and the ssa names themselves to
!    NEED_PHIS.  */
  
  static void
! find_uses_to_rename (bitmap *use_blocks, bitmap need_phis)
  {
    basic_block bb;
    block_stmt_iterator bsi;
*************** find_uses_to_rename (bitmap *use_blocks)
*** 275,284 ****
        for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
  	for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
  	  find_uses_to_rename_use (PHI_ARG_EDGE (phi, i)->src,
! 				   PHI_ARG_DEF (phi, i), use_blocks);
  
        for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
! 	find_uses_to_rename_stmt (bsi_stmt (bsi), use_blocks);
      }
  }
  
--- 275,286 ----
        for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
  	for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
  	  find_uses_to_rename_use (PHI_ARG_EDGE (phi, i)->src,
! 				   PHI_ARG_DEF (phi, i), 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,
! 				  need_phis);
      }
  }
  
*************** rewrite_into_loop_closed_ssa (void)
*** 313,341 ****
  {
    bitmap loop_exits = get_loops_exits ();
    bitmap *use_blocks;
!   unsigned i;
!   bitmap names_to_rename;
  
!   gcc_assert (!any_marked_for_rewrite_p ());
  
!   use_blocks = xcalloc (num_ssa_names, sizeof (bitmap));
  
    /* Find the uses outside loops.  */
!   find_uses_to_rename (use_blocks);
  
    /* 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++)
      BITMAP_XFREE (use_blocks[i]);
    free (use_blocks);
    BITMAP_XFREE (loop_exits);
    BITMAP_XFREE (names_to_rename);
  
!   /* Do the rewriting.  */
!   rewrite_ssa_into_ssa ();
  }
  
  /* Check invariants of the loop closed ssa form for the USE in BB.  */
--- 315,342 ----
  {
    bitmap loop_exits = get_loops_exits ();
    bitmap *use_blocks;
!   unsigned i, old_num_ssa_names = num_ssa_names;
!   bitmap names_to_rename = BITMAP_XMALLOC ();
  
!   gcc_assert (!any_values_for_ssa_update_p ());
  
!   use_blocks = xcalloc (old_num_ssa_names, sizeof (bitmap));
  
    /* Find the uses outside loops.  */
!   find_uses_to_rename (use_blocks, names_to_rename);
  
    /* Add the phi nodes on exits of the loops for the names we need to
       rewrite.  */
    add_exit_phis (names_to_rename, use_blocks, loop_exits);
  
!   for (i = 0; i < old_num_ssa_names; i++)
      BITMAP_XFREE (use_blocks[i]);
    free (use_blocks);
    BITMAP_XFREE (loop_exits);
    BITMAP_XFREE (names_to_rename);
  
!   /* Fix the ssa form.  */
!   update_ssa_form_for_registered_defs (0);
  }
  
  /* Check invariants of the loop closed ssa form for the USE in BB.  */
*************** copy_phi_node_args (unsigned first_new_b
*** 532,574 ****
  }
  
  /* 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;
! 	}
! 
!       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 = TREE_CHAIN (phi))
-     SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = phi;
  }
  
  /* The same ad cfgloopmanip.c:duplicate_loop_to_header_edge, but also updates
--- 533,551 ----
  }
  
  /* Renames variables in the area copied by tree_duplicate_loop_to_header_edge.
!    FIRST_NEW_BLOCK is the first block in the copied area.  */
  
  static void
! rename_variables (unsigned first_new_block)
  {
!   unsigned i;
    basic_block bb;
  
    for (i = first_new_block; i < (unsigned) last_basic_block; i++)
      {
        bb = BASIC_BLOCK (i);
!       rewrite_uses_bb (bb, bb->rbi->copy_number);
      }
  }
  
  /* The same ad cfgloopmanip.c:duplicate_loop_to_header_edge, but also updates
*************** tree_duplicate_loop_to_header_edge (stru
*** 587,596 ****
  				    unsigned int *n_to_remove, int flags)
  {
    unsigned first_new_block;
-   basic_block bb;
-   unsigned i;
    tree phi, arg, map, def;
-   bitmap definitions;
  
    if (!(loops->state & LOOPS_HAVE_SIMPLE_LATCHES))
      return false;
--- 564,570 ----
*************** tree_duplicate_loop_to_header_edge (stru
*** 601,607 ****
    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,
--- 575,581 ----
    verify_loop_closed_ssa ();
  #endif
  
!   gcc_assert (!any_values_for_ssa_update_p ());
  
    first_new_block = last_basic_block;
    if (!duplicate_loop_to_header_edge (loop, e, loops, ndupl, wont_exit,
*************** tree_duplicate_loop_to_header_edge (stru
*** 625,648 ****
    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_XFREE (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
--- 599,607 ----
    copy_phi_node_args (first_new_block);
  
    /* Rename the variables.  */
!   rename_variables (first_new_block);
  
!   ssa_form_updated_all ();
  
    scev_reset ();
  #ifdef ENABLE_CHECKING
Index: tree-ssa-threadupdate.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-threadupdate.c,v
retrieving revision 2.10.12.1
diff -c -3 -p -r2.10.12.1 tree-ssa-threadupdate.c
*** tree-ssa-threadupdate.c	25 Oct 2004 06:37:32 -0000	2.10.12.1
--- tree-ssa-threadupdate.c	3 Nov 2004 00:00:20 -0000
*************** static void
*** 103,124 ****
  copy_phis_to_block (basic_block new_bb, basic_block bb, edge e)
  {
    tree phi, arg;
  
    /* Walk over every PHI in BB.  */
!   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
      {
!       tree new_phi;
! 
!       /* First try to find a PHI node in NEW_BB which has the same
!          PHI_RESULT as the PHI from BB we are currently processing.  */
!       for (new_phi = phi_nodes (new_bb); new_phi;
! 	   new_phi = PHI_CHAIN (new_phi))
! 	if (PHI_RESULT (new_phi) == PHI_RESULT (phi))
! 	  break;
! 
!       /* If we did not find a suitable PHI in NEW_BB, create one.  */
!       if (!new_phi)
! 	new_phi = create_phi_node (PHI_RESULT (phi), new_bb);
  
        /* Extract the argument corresponding to E from the current PHI
           node in BB.  */
--- 103,117 ----
  copy_phis_to_block (basic_block new_bb, basic_block bb, edge e)
  {
    tree phi, arg;
+   tree new_phi;
  
    /* Walk over every PHI in BB.  */
!   for (phi = phi_nodes (bb), new_phi = phi_nodes (new_bb);
!        phi;
!        phi = PHI_CHAIN (phi), new_phi = PHI_CHAIN (new_phi))
      {
!       gcc_assert (original_equivalent_name (PHI_RESULT (phi))
! 		  == original_equivalent_name (PHI_RESULT (new_phi)));
  
        /* Extract the argument corresponding to E from the current PHI
           node in BB.  */
Index: tree-ssanames.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssanames.c,v
retrieving revision 2.15.10.2
diff -c -3 -p -r2.15.10.2 tree-ssanames.c
*** tree-ssanames.c	25 Oct 2004 06:37:33 -0000	2.15.10.2
--- tree-ssanames.c	3 Nov 2004 00:00:20 -0000
*************** Boston, MA 02111-1307, USA.  */
*** 61,69 ****
  /* Array of all SSA_NAMEs used in the function.  */
  varray_type ssa_names;
  
- /* Bitmap of ssa names marked for rewriting.  */
- bitmap ssa_names_to_rewrite;
- 
  /* Free list of SSA_NAMEs.  This list is wiped at the end of each function
     after we leave SSA form.  */
  static GTY (()) tree free_ssanames;
--- 61,66 ----
*************** unsigned int ssa_name_nodes_reused;
*** 77,140 ****
  unsigned int ssa_name_nodes_created;
  #endif
  
- /* Returns true if ssa name VAR is marked for rewrite.  */
- 
- bool
- marked_for_rewrite_p (tree var)
- {
-   if (ssa_names_to_rewrite
-       && bitmap_bit_p (ssa_names_to_rewrite, SSA_NAME_VERSION (var)))
-     return true;
- 
-   return false;
- }
- 
- /* Returns true if any ssa name is marked for rewrite.  */
- 
- bool
- any_marked_for_rewrite_p (void)
- {
-   if (!ssa_names_to_rewrite)
-     return false;
- 
-   return bitmap_first_set_bit (ssa_names_to_rewrite) != -1;
- }
- 
- /* Mark ssa name VAR for rewriting.  */
- 
- void
- mark_for_rewrite (tree var)
- {
-   if (!ssa_names_to_rewrite)
-     ssa_names_to_rewrite = BITMAP_XMALLOC ();
- 
-   bitmap_set_bit (ssa_names_to_rewrite, SSA_NAME_VERSION (var));
- }
- 
- /* Unmark all ssa names marked for rewrite.  */
- 
- void
- unmark_all_for_rewrite (void)
- {
-   if (!ssa_names_to_rewrite)
-     return;
- 
-   bitmap_clear (ssa_names_to_rewrite);
- }
- 
- /* Return the bitmap of ssa names to rewrite.  Copy the bitmap,
-    so that the optimizers cannot access internals directly  */
- 
- bitmap
- marked_ssa_names (void)
- {
-   bitmap ret = BITMAP_XMALLOC ();
-   if (ssa_names_to_rewrite)
-     bitmap_copy (ret, ssa_names_to_rewrite);
- 
-   return ret;
- }
- 
  /* Initialize management of SSA_NAMEs.  */
  
  void
--- 74,79 ----
*************** release_ssa_name (tree var)
*** 245,256 ****
    if (var == var_ann (SSA_NAME_VAR (var))->default_def)
      return;
  
-   /* If the ssa name is marked for rewriting, it may have multiple definitions,
-      but we may happen to remove just one of them.  So do not remove the
-      ssa name now.  */
-   if (marked_for_rewrite_p (var))
-     return;
- 
    /* release_ssa_name can be called multiple times on a single SSA_NAME.
       However, it should only end up on our free list one time.   We
       keep a status bit in the SSA_NAME node itself to indicate it has
--- 184,189 ----
*************** release_ssa_name (tree var)
*** 264,269 ****
--- 197,204 ----
        int saved_ssa_name_version = SSA_NAME_VERSION (var);
        ssa_imm_use_t *imm = &(SSA_NAME_IMM_USE_NODE (var));
  
+       release_ssa_name_from_eqto (var);
+ 
  #ifdef ENABLE_CHECKING
        verify_imm_links (stderr, var);
  #endif
Index: tree-update-ssa.c
===================================================================
RCS file: tree-update-ssa.c
diff -N tree-update-ssa.c
*** /dev/null	1 Jan 1970 00:00:00 -0000
--- tree-update-ssa.c	3 Nov 2004 00:00:20 -0000
***************
*** 0 ****
--- 1,1746 ----
+ /* SSA form updating utilities.
+    Copyright (C) 2004 Free Software Foundation, Inc.
+ 
+ This file is part of GCC.
+ 
+ GCC is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2, or (at your option)
+ any later version.
+ 
+ GCC is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ GNU General Public License for more details.
+ 
+ You should have received a copy of the GNU General Public License
+ along with GCC; see the file COPYING.  If not, write to
+ the Free Software Foundation, 59 Temple Place - Suite 330,
+ Boston, MA 02111-1307, USA.  */
+ 
+ #include "config.h"
+ #include "system.h"
+ #include "coretypes.h"
+ #include "tm.h"
+ #include "tree.h"
+ #include "flags.h"
+ #include "rtl.h"
+ #include "tm_p.h"
+ #include "langhooks.h"
+ #include "hard-reg-set.h"
+ #include "basic-block.h"
+ #include "output.h"
+ #include "errors.h"
+ #include "expr.h"
+ #include "function.h"
+ #include "diagnostic.h"
+ #include "bitmap.h"
+ #include "tree-flow.h"
+ #include "tree-gimple.h"
+ #include "tree-inline.h"
+ #include "varray.h"
+ #include "timevar.h"
+ #include "tree-dump.h"
+ 
+ /* This file implements utilities for updating SSA form.  The core is the
+    function
+ 
+    update_ssa_form (values, flags);
+ 
+    This function creates a ssa form for values in list VALUES.  The description
+    for each value contains the decl for the base of the ssa names that need to
+    be created, list containing the positions where the value is defined and
+    list containing the positions where the value is used.  In case you
+    performed simple code duplication, or called "rewrite_new_def" to create
+    new ssa name for the code you emitted yourself, you may obtain the lists to
+    feed to this function from "get_values_for_ssa_form_update" function.
+ 
+    WARNING -- be sure you do not modify/remove statements in such a way that
+    would cause def operands to get invalidated if you use this mechanism.
+    If you create the list of defs and uses yourself, ensure that the def
+    and use operand pointers are valid (for example resizing a phi node that
+    may occur during edge redirection invalidates def operand pointers).
+ 
+    The most common case for using this function is when a portion of the
+    code is duplicated.  Although new ssa names are created for duplicated
+    definitions, you should think about them as "aliases" for the original
+    definitions when arguing correctness of such transformation -- the code
+    for that you call update_ssa_form should be valid in case you replace
+    these aliases by the original ssa name (and forget that the program should
+    be in ssa form).  For example suppose you have the following piece of code:
+ 
+    L1:
+      goto L2;
+ 
+    L2:
+      a_1 = ...
+    L3:
+      use (a_1)
+ 
+    By duplicating of the definition of a_1 you obtain
+ 
+    L1:
+      a_2{eqto a_1} = ...	;; this notation is used for the variables
+ 				;; created in code duplication (or via
+ 				;; "rewrite_new_def") until update_ssa_form
+ 				;; is called on them (or alternatively until
+ 				;; you call "ssa_form_updated" on the variable
+ 				;; to inform that you performed ssa form
+ 				;; updating yourself.
+      goto L3;
+ 
+    L2:
+      a_1 = ...
+ 
+    L3:
+      use (a_1);
+ 
+    Observe that the code still has the original semantics if you replace
+    a_2 by a_1.  Usually this should mean that all values in the uses list
+    are the original ssa name (although this is not required, and we do not
+    look at the original contents of uses at all, so even NULL pointers are
+    fine).
+ 
+    Call to update_ssa_form transforms this code to valid ssa form:
+ 
+    L1:
+      a_2 = ...
+      goto L3;
+ 
+    L2:
+      a_1 = ...
+ 
+    L3:
+      a_3 = phi (a_1, a_2);
+      use (a_3);
+ 
+    The function creates new ssa names only for newly created phi nodes.  In
+    particular it expects each def in the list to be a separate ssa name based
+    on VAR.  The information associated with newly created ssa names in phi
+    nodes is obtained by merging the information at the arguments of the phi
+    node.  In some cases you may use some information from the optimization that
+    caused violation of the ssa form to improve this information; if this is the
+    case, you must create the phi nodes with the improved information yourself
+    (the update_ssa_form function may still be useful for you to perform the
+    rewriting of uses by the reaching defs, or even creating the phi nodes for
+    that you have no special information to improve).
+ 
+    The function runs in general in time proportional to the size of area in
+    that the updated variables are live.  If USF_PHIS_ALREADY_EXIST flag is
+    used, the function assumes that all necessary phi nodes are already
+    present and uses it to make the time proportional to the size of defs and
+    uses list (however it does not verify that it is really not necessary
+    to create new phis, so be sure that the phi nodes really exist).
+    This should be efficient enough for most purposes.  In case the function
+    causes performance problems for the specific task for that you need to use,
+    you may consider looking at the specific properties of the transformation
+    you perform and using them to create new phi nodes yourself, or even avoiding
+    use of this function altogether (but note that unless you have some such
+    reason, you should prefer this generic machinery to avoid unnecessary code
+    duplication).
+    
+    The algorithm employed is basically the standard ssa form creation algorithm
+    described in
+    
+    R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently
+    Computing Static Single Assignment Form and the Control Dependence
+    Graph. ACM Transactions on Programming Languages and Systems,
+    13(4):451-490, October 1991,
+    
+    only restricted to the area of liveness.  */
+ 
+ /* List of definitions.  */
+ 
+ struct valdef
+ {
+   struct ssa_update_value *val;	/* The value.  */
+   def_operand_p op;		/* Position of the definition.  */
+   struct valdef *next;		/* Next definition in the list.  */
+   struct valdef *next_in_stack;	/* Next definition in the stack.  */
+ };
+ 
+ /* List of uses.  */
+ 
+ struct valuse
+ {
+   struct ssa_update_value *val; /* The value.  */
+   use_operand_p op;		/* Position of the use.  */
+   struct valuse *next;		/* Next use in the list.  */
+ };
+ 
+ /* Representation of subtree of dominator tree.  */
+ 
+ struct dom_tree_node
+ {
+   basic_block bb;		/* The basic block represented by the node.  */
+   struct dom_tree_node *son;	/* The first son of the node.  */
+   struct dom_tree_node *next;	/* A brother of the node.  */
+ 
+   bitmap df;			/* Dominance frontiers of the node.  */
+   bitmap values_live;		/* Bitmap of values that are live here.  */
+   struct valdef *defs;		/* Values defined here.  */
+   struct valuse *uses;		/* Values used here.  */
+ };
+ 
+ /* Structure that may contain use or def.  */
+ 
+ struct use_or_def
+ {
+   union
+     {
+       struct usf_use_list *use;
+       struct usf_def_list *def;
+     } ud;
+ 
+   unsigned is_use : 1;		/* True if this is an use.  */
+ };
+ 
+ /* If function has less than this number of basic blocks, we always
+    scan whole dominance tree when creating the subtree of interesting
+    blocks.  */
+ 
+ #define LARGE_AREA_BASE 25
+ 
+ /* If more than LARGE_AREA_FRACTION% of blocks are interesting, whole
+    dominance tree is scanner when creating the subtree of interesting
+    blocks.  */
+ 
+ #define LARGE_AREA_FRACTION 25
+ 
+ /* For storing the contents of aux fields.  */
+ 
+ struct aux_contents
+ {
+   /* The stored data.  */
+   void **old;
+ 
+   /* Actual element when passing the tree in order to save/restore the
+      aux fields.  */
+   unsigned act;
+ };
+ 
+ /* Releases memory occupied by USE.  */
+ 
+ static void
+ free_use (struct usf_use_list *use)
+ {
+   free (use);
+ }
+ 
+ /* Releases memory occupied by DEF.  */
+ 
+ static void
+ free_def (struct usf_def_list *def)
+ {
+   free (def);
+ }
+ 
+ /* Determines the basic block in that USE occurs.  */
+ 
+ static basic_block
+ determine_use_bb (const struct usf_use_list *use)
+ {
+   tree stmt = USE_STMT (use->op);
+   unsigned idx;
+ 
+   if (TREE_CODE (stmt) != PHI_NODE)
+     return bb_for_stmt (stmt);
+ 
+   idx = PHI_ARG_INDEX_FROM_USE (use->op);
+ 
+   return PHI_ARG_EDGE (stmt, idx)->src;
+ }
+ 
+ /* Determines the statement in that DEF occurs.  */
+ 
+ tree
+ determine_def_stmt (const struct usf_def_list *def)
+ {
+   tree name = DEF_FROM_PTR (def->op);
+   
+   return SSA_NAME_DEF_STMT (name);
+ }
+ 
+ /* Determines the basic block in that DEF occurs.  */
+ 
+ basic_block
+ determine_def_bb (const struct usf_def_list *def)
+ {
+   return bb_for_stmt (determine_def_stmt (def));
+ }
+ 
+ /* Extracts information from X.  Basic block is stored to *BB, statement to
+    *STMT.  True is returned if it is use.  */
+ 
+ static bool
+ get_use_or_def_info (const struct use_or_def *x, basic_block *bb, tree *stmt)
+ {
+   if (x->is_use)
+     {
+       *stmt = USE_STMT (x->ud.use->op);
+       *bb = determine_use_bb (x->ud.use);
+     }
+   else
+     {
+       *stmt = determine_def_stmt (x->ud.def);
+       *bb = bb_for_stmt (*stmt);
+     }
+ 
+   if (*bb == NULL)
+     *bb = ENTRY_BLOCK_PTR;
+ 
+   return x->is_use;
+ }
+ 
+ /* Compare two struct usf_{use,def}_list elements by basic block and local
+    dominance number.  */
+ 
+ static int
+ compare_by_ldom (const void *a, const void *b)
+ {
+   basic_block bba, bbb;
+   tree stmta, stmtb;
+   bool usea, useb;
+ 
+   usea = get_use_or_def_info (a, &bba, &stmta);
+   useb = get_use_or_def_info (b, &bbb, &stmtb);
+ 
+   /* The direction in that different blocks are sorted is chosen in such a way
+      that the indices of the blocks in the lists that are later reassembled
+      grow monotonically.  This is good for performance of bitmaps.  */
+   if (bba != bbb)
+     return bbb->index - bba->index;
+ 
+   if (TREE_CODE (stmta) == PHI_NODE)
+     return usea ? 1 : -1;
+   if (TREE_CODE (stmtb) == PHI_NODE)
+     return useb ? -1 : 1;
+ 
+   if (stmta == stmtb)
+     {
+       if (usea)
+ 	return -1;
+       if (useb)
+ 	return 1;
+       return 0;
+     }
+ 
+   return stmt_dominated_by_p (stmtb, stmta) ? -1 : 1;
+ }
+ 
+ /* Rewrite use operand OP by DEF.  */
+ 
+ static void
+ rewrite_use (use_operand_p op, tree def)
+ {
+   tree stmt;
+   unsigned idx;
+ 
+   gcc_assert (TREE_CODE (def) == SSA_NAME);
+   SET_USE (op, def);
+ 
+   stmt = USE_STMT (op);
+   if (TREE_CODE (stmt) != PHI_NODE)
+     return;
+ 
+   /* Mark argument on abnormal edge.  */
+   idx = PHI_ARG_INDEX_FROM_USE (op);
+   if (PHI_ARG_EDGE (stmt, idx)->flags & EDGE_ABNORMAL)
+     SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def) = 1;
+ }
+ 
+ /* Rewrite USE by DEF.  */
+ 
+ static void
+ rewrite_by (struct usf_use_list *use, struct usf_def_list *def)
+ {
+   rewrite_use (use->op, DEF_FROM_PTR (def->op));
+ }
+ 
+ /* Rewrite USE by DEF.  */
+ 
+ static void
+ rewrite_by_vd (struct valuse *use, struct valdef *def)
+ {
+   tree adef;
+ 
+   if (def)
+     {
+       gcc_assert (use->val == def->val);
+       adef = DEF_FROM_PTR (def->op);
+     }
+   else
+     {
+       tree decl = use->val->decl;
+ 
+       adef = default_def (decl);
+       if (!adef)
+ 	{
+ 	  adef = make_ssa_name (decl, build_empty_stmt ());
+ 	  set_default_def (decl, adef);
+ 	}
+     }
+ 
+   rewrite_use (use->op, adef);
+ }
+ 
+ /* Updates ssa form for value VAL locally inside basic blocks.  The
+    lists of uses and defs are pruned.  True is returned if there is no
+    need for further ssa form updating, i.e. if all uses were rewritten
+    by values inside their basic block.  */
+ 
+ static bool
+ update_ssa_form_locally_1 (struct ssa_update_value *val)
+ {
+   unsigned i, n;
+   struct usf_use_list *use;
+   struct usf_def_list *def, *adef;
+   struct use_or_def *uses_and_defs;
+   basic_block last_def_block = NULL, bb;
+   
+   n = 0;
+   for (def = val->defs; def; def = def->next)
+     {
+       tree d = DEF_FROM_PTR (def->op);
+       gcc_assert (TREE_CODE (d) == SSA_NAME);
+       /* Currently this should be always true.  This is not really
+ 	 a hard constraint (we do not really care what the value of
+ 	 the def is, as long as it is a SSA name), so this may get
+ 	 changed in the future.  */
+       gcc_assert (SSA_NAME_VAR (d) == val->decl);
+ 
+       n++;
+     }
+   for (use = val->uses; use; use = use->next)
+     n++;
+ 
+   uses_and_defs = xmalloc (sizeof (struct use_or_def) * n);
+   i = 0;
+   for (def = val->defs; def; def = def->next, i++)
+     {
+       uses_and_defs[i].is_use = false;
+       uses_and_defs[i].ud.def = def;
+     }
+   for (use = val->uses; use; use = use->next, i++)
+     {
+       uses_and_defs[i].is_use = true;
+       uses_and_defs[i].ud.use = use;
+     }
+ 
+   val->defs = NULL;
+   val->uses = NULL;
+ 
+   qsort (uses_and_defs, n, sizeof (struct use_or_def), compare_by_ldom);
+   for (i = 0; i < n; i++)
+     {
+       if (uses_and_defs[i].is_use)
+ 	{
+ 	  use = uses_and_defs[i].ud.use;
+ 
+ 	  if (last_def_block == determine_use_bb (use))
+ 	    {
+ 	      rewrite_by (use, val->defs);
+ 	      free_use (use);
+ 	    }
+ 	  else
+ 	    {
+ 	      use->next = val->uses;
+ 	      val->uses = use;
+ 	    }
+ 	}
+       else
+ 	{
+ 	  def = uses_and_defs[i].ud.def;
+ 	  bb = determine_def_bb (def);
+ 
+ 	  if (last_def_block == bb)
+ 	    {
+ 	      adef = val->defs;
+ 	      val->defs = adef->next;
+ 	      free_def (adef);
+ 	    }
+ 
+ 	  def->next = val->defs;
+ 	  val->defs = def;
+ 	  last_def_block = bb;
+ 	}
+     }
+ 
+   free (uses_and_defs);
+ 
+   return val->uses == NULL;
+ }
+ 
+ /* Frees value VAL.  */
+ 
+ static void
+ free_value (struct ssa_update_value *val)
+ {
+   struct usf_def_list *def, *ndef;
+   struct usf_use_list *use, *nuse;
+ 
+   for (def = val->defs; def; def = ndef)
+     {
+       ndef = def->next;
+       free_def (def);
+     }
+   for (use = val->uses; use; use = nuse)
+     {
+       nuse = use->next;
+       free_use (use);
+     }
+ 
+   if (val->life_area)
+     BITMAP_XFREE (val->life_area);
+ 
+   free (val);
+ }
+ 
+ /* Updates ssa form for VALUES inside basic blocks.  The list of values for
+    that global updating is necessary is returned.  The following properties
+    are satisfied by uses and defs in the returned list:
+ 
+    There is at most one def per basic block.
+    If there are both uses and a def in a basic block, then the uses precede
+    defs.
+    Each value has at least one use.  */
+ 
+ static struct ssa_update_value *
+ update_ssa_form_locally (struct ssa_update_value *values)
+ {
+   struct ssa_update_value **val, *aval;
+ 
+   for (val = &values; *val; )
+     {
+       aval = *val;
+ 
+       if (update_ssa_form_locally_1 (aval))
+ 	{
+ 	  *val = aval->next;
+ 
+ 	  free_value (aval);
+ 	}
+       else
+ 	val = &aval->next;
+     }
+ 
+   return values;
+ }
+ 
+ /* Mark the blocks in that VALUE is defined or used in bitmap BLOCKS.  */
+ 
+ static void
+ mark_use_and_def_blocks (struct ssa_update_value *value, bitmap blocks)
+ {
+   struct usf_def_list *def;
+   struct usf_use_list *use;
+   basic_block bb;
+ 
+   for (def = value->defs; def; def = def->next)
+     {
+       bb = determine_def_bb (def);
+       if (!bb)
+ 	continue;
+       bitmap_set_bit (blocks, bb->index);
+     }
+ 
+   for (use = value->uses; use; use = use->next)
+     bitmap_set_bit (blocks, determine_use_bb (use)->index);
+ }
+ 
+ /* Mark the blocks in that VALUE is live in bitmap BLOCKS.  */
+ 
+ static void
+ mark_liveness_area (struct ssa_update_value *value, bitmap blocks)
+ {
+   struct usf_def_list *def;
+   struct usf_use_list *use;
+   basic_block bb;
+   bitmap defs = BITMAP_XMALLOC (), livein = BITMAP_XMALLOC ();
+ 
+   for (def = value->defs; def; def = def->next)
+     {
+       bb = determine_def_bb (def);
+       if (!bb)
+ 	continue;
+       bitmap_set_bit (defs, bb->index);
+     }
+   for (use = value->uses; use; use = use->next)
+     bitmap_set_bit (livein, determine_use_bb (use)->index);
+   compute_global_livein (livein, defs);
+ 
+   value->life_area = livein;
+   bitmap_a_or_b (blocks, blocks, defs);
+   bitmap_a_or_b (blocks, blocks, livein);
+   free (defs);
+ }
+ 
+ /* Returns a new dominance tree node corresponding to basic block BB.  */
+ 
+ static struct dom_tree_node *
+ new_dom_tree_node (basic_block bb)
+ {
+   struct dom_tree_node *ret = xcalloc (1, sizeof (struct dom_tree_node));
+   ret->bb = bb;
+   return ret;
+ }
+ 
+ /* Return a subtree of dominance tree induced by BLOCKS in a tree rooted
+    at ROOT.  FATHER is the father node for the subtree.  */
+ 
+ static void
+ create_dom_subtree_walk_whole_1 (struct dom_tree_node *father,
+ 				 basic_block root, bitmap blocks)
+ {
+   basic_block bb;
+ 
+   if (bitmap_bit_p (blocks, root->index))
+     {
+       struct dom_tree_node *node = new_dom_tree_node (root);
+ 
+       node->next = father->son;
+       father->son = node;
+       father = node;
+     }
+ 
+   for (bb = first_dom_son (CDI_DOMINATORS, root);
+        bb;
+        bb = next_dom_son (CDI_DOMINATORS, bb))
+     create_dom_subtree_walk_whole_1 (father, bb, blocks);
+ }
+ 
+ /* Return a subtree of dominance tree induced by BLOCKS.  The subtree is
+    obtained by walking whole dominance tree.  */
+ 
+ static struct dom_tree_node *
+ create_dom_subtree_walk_whole (bitmap blocks)
+ {
+   struct dom_tree_node *root = new_dom_tree_node (ENTRY_BLOCK_PTR);
+   basic_block bb;
+ 
+   for (bb = first_dom_son (CDI_DOMINATORS, ENTRY_BLOCK_PTR);
+        bb;
+        bb = next_dom_son (CDI_DOMINATORS, bb))
+     create_dom_subtree_walk_whole_1 (root, bb, blocks);
+ 
+   return root;
+ }
+ 
+ /* Return a subtree of dominance tree induced by BLOCKS.  The subtree is
+    obtained by inserting the nodes in BLOCKS one by one.  */
+ 
+ static struct dom_tree_node *
+ create_dom_subtree_incremental (bitmap blocks)
+ {
+   struct dom_tree_node *root = new_dom_tree_node (ENTRY_BLOCK_PTR);
+   struct dom_tree_node *nw, *act_father, **act_p, *act;
+   bitmap_iterator bi;
+   unsigned index;
+   basic_block bb;
+ 
+   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, index, bi)
+     {
+       bb = BASIC_BLOCK (index);
+       nw = new_dom_tree_node (bb);
+       act_father = root;
+ 
+       while (1)
+ 	{
+ 	  for (act_p = &act_father->son; *act_p;)
+ 	    {
+ 	      act = *act_p;
+ 
+ 	      if (dominated_by_p (CDI_DOMINATORS, bb, act->bb))
+ 		break;
+ 
+ 	      if (dominated_by_p (CDI_DOMINATORS, act->bb, bb))
+ 		{
+ 		  *act_p = act->next;
+ 		  act->next = nw->son;
+ 		  nw->son = act;
+ 		}
+ 	      else
+ 		act_p = &act->next;
+ 	    }
+ 
+ 	  if (!*act_p)
+ 	    break;
+ 
+ 	  act_father = *act_p;
+ 	  gcc_assert (!nw->son);
+ 	}
+ 
+       nw->next = act_father->son;
+       act_father->son = nw;
+     }
+ 
+   return root;
+ }
+ 
+ /* Passes dominance tree DOM_TREE in dfs. CALLBACK_BEFORE is called for each
+    node before its sons are traversed, and CALLBACK_AFTER is called after
+    they are traversed (any of the callbacks may be NULL, in which case it is
+    ignored).  DATA is passed to the callbacks.  */
+ 
+ static void
+ walk_dom_tree (struct dom_tree_node *dom_tree,
+ 	       void (*callback_before) (struct dom_tree_node *, void *),
+ 	       void (*callback_after) (struct dom_tree_node *, void *),
+ 	       void *data)
+ {
+   struct dom_tree_node *node, *next;
+ 
+   if (callback_before)
+     callback_before (dom_tree, data);
+   for (node = dom_tree->son; node; node = next)
+     {
+       next = node->next;
+       walk_dom_tree (node, callback_before, callback_after, data);
+     }
+   if (callback_after)
+     callback_after (dom_tree, data);
+ }
+ 
+ /* Moves list of valdefs from aux field of the basic block to NODE.
+    Callback for walk_dom_tree.  */
+ 
+ static void
+ wdt_set_defs (struct dom_tree_node *node, void *data ATTRIBUTE_UNUSED)
+ {
+   node->defs = node->bb->aux;
+   node->bb->aux = NULL;
+ }
+ 
+ /* Returns a new valdef for VALUE at position OP.  NEXT is the next valdef in
+    the list.  */
+ 
+ static struct valdef *
+ new_valdef (struct ssa_update_value *value,
+ 	    def_operand_p op,
+ 	    struct valdef *next)
+ {
+   struct valdef *ret = xmalloc (sizeof (struct valdef));
+ 
+   ret->val = value;
+   ret->op = op;
+   ret->next = next;
+   ret->next_in_stack = NULL;
+ 
+   return ret;
+ }
+ 
+ /* Move the information about defs from VALUES to DOM_TREE.  */
+ 
+ static void
+ attach_def_lists_to_dom_tree (struct dom_tree_node *dom_tree,
+ 			      struct ssa_update_value *values)
+ {
+   struct ssa_update_value *value;
+   struct usf_def_list *def;
+ 
+   for (value = values; value; value = value->next)
+     for (def = value->defs; def; def = def->next)
+       {
+ 	basic_block bb = determine_def_bb (def);
+ 	bb->aux = new_valdef (value, def->op, bb->aux);
+       }
+ 
+   walk_dom_tree (dom_tree, wdt_set_defs, NULL, NULL);
+ }
+ 
+ /* Moves list of valuses from aux field of the basic block to NODE.
+    Callback for walk_dom_tree.  */
+ 
+ static void
+ wdt_set_uses (struct dom_tree_node *node, void *data ATTRIBUTE_UNUSED)
+ {
+   node->uses = node->bb->aux;
+   node->bb->aux = NULL;
+ }
+ 
+ /* Returns a new valuse for VALUE at position OP.  NEXT is the next valuse in
+    the list.  */
+ 
+ static struct valuse *
+ new_valuse (struct ssa_update_value *value,
+ 	    use_operand_p op,
+ 	    struct valuse *next)
+ {
+   struct valuse *ret = xmalloc (sizeof (struct valuse));
+ 
+   ret->val = value;
+   ret->op = op;
+   ret->next = next;
+ 
+   return ret;
+ }
+ 
+ /* Move the information about uses from VALUES to DOM_TREE.  */
+ 
+ static void
+ attach_use_lists_to_dom_tree (struct dom_tree_node *dom_tree,
+ 			      struct ssa_update_value *values)
+ {
+   struct ssa_update_value *value;
+   struct usf_use_list *use;
+ 
+   for (value = values; value; value = value->next)
+     for (use = value->uses; use; use = use->next)
+       {
+ 	basic_block bb = determine_use_bb (use);
+ 	bb->aux = new_valuse (value, use->op, bb->aux);
+       }
+ 
+   walk_dom_tree (dom_tree, wdt_set_uses, NULL, NULL);
+ }
+ 
+ /* Moves liveness bitmaps from aux field of the basic block to NODE.
+    Callback for walk_dom_tree.  */
+ 
+ static void
+ wdt_set_live (struct dom_tree_node *node, void *data ATTRIBUTE_UNUSED)
+ {
+   node->values_live = node->bb->aux;
+   node->bb->aux = NULL;
+ }
+ 
+ /* Move the information about liveness of VALUES to DOM_TREE.  */
+ 
+ static void
+ attach_liveness_to_dom_tree (struct dom_tree_node *dom_tree,
+ 			     struct ssa_update_value *values)
+ {
+   struct ssa_update_value *value;
+   bitmap_iterator bi;
+   basic_block bb;
+   unsigned index;
+ 
+   for (value = values; value; value = value->next)
+     {
+       if (!value->life_area)
+ 	continue;
+ 
+       EXECUTE_IF_SET_IN_BITMAP (value->life_area, 0, index, bi)
+ 	{
+ 	  bb = BASIC_BLOCK (index);
+ 
+ 	  if (!bb->aux)
+ 	    bb->aux = BITMAP_XMALLOC ();
+ 
+ 	  bitmap_set_bit (bb->aux, value->id);
+ 	}
+     }
+ 
+   walk_dom_tree (dom_tree, wdt_set_live, NULL, NULL);
+ }
+ 
+ /* Set aux field of NODE->bb to NODE.  Callback for walk_dom_tree.  */
+ 
+ static void
+ wdt_set_aux_to_node (struct dom_tree_node *node,
+ 		     void *data ATTRIBUTE_UNUSED)
+ {
+   node->bb->aux = node;
+ }
+ 
+ /* Clear the aux field of NODE->bb and store the original value to the array
+    passed in DATA.  */
+ 
+ static void
+ wdt_save_aux_field (struct dom_tree_node *node, void *data)
+ {
+   struct aux_contents *old = data;
+ 
+   old->old[old->act++] = node->bb->aux;
+   node->bb->aux = NULL;
+ }
+ 
+ /* Save and clear aux fields for nodes of DOM_TREE.  SIZE is the number
+    of nodes of the DOM_TREE.  The structure containing the previous contents
+    of aux fields is returned.  */
+ 
+ static struct aux_contents
+ save_aux_fields (struct dom_tree_node *dom_tree, unsigned size)
+ {
+   struct aux_contents ret;
+ 
+   ret.old = xmalloc (size * sizeof (void *));
+   ret.act = 0;
+   walk_dom_tree (dom_tree, wdt_save_aux_field, NULL, &ret);
+ 
+   gcc_assert (ret.act == size);
+   return ret;
+ }
+ 
+ /* Set aux field of NODE->bb to the original value (passed to it in array in
+    DATA).  Callback for walk_dom_tree.  */
+ 
+ static void
+ wdt_restore_aux_field (struct dom_tree_node *node, void *data)
+ {
+   struct aux_contents *old = data;
+ 
+   node->bb->aux = old->old[old->act++];
+ }
+ 
+ /* Restores the aux fields for nodes of DOM_TREE using the data from OLD.  */
+ 
+ static void
+ restore_aux_fields (struct dom_tree_node *dom_tree, struct aux_contents old)
+ {
+   old.act = 0;
+   walk_dom_tree (dom_tree, wdt_restore_aux_field, NULL, &old);
+   free (old.old);
+ }
+ 
+ /* Move the information about uses and defs from VALUES to DOM_TREE.  */
+ 
+ static void
+ attach_use_and_def_info_to_dom_tree (struct dom_tree_node *dom_tree,
+ 				     struct ssa_update_value *values)
+ {
+   attach_def_lists_to_dom_tree (dom_tree, values);
+   attach_use_lists_to_dom_tree (dom_tree, values);
+   attach_liveness_to_dom_tree (dom_tree, values);
+   walk_dom_tree (dom_tree, wdt_set_aux_to_node, NULL, NULL);
+ }
+ 
+ /* Calculate a dominance frontiers for NODE, using the df information
+    that is already computed for all sons of NODE in the dominance tree.
+    Callback for walk_dom_tree.  */
+ 
+ static void
+ wdt_calc_df (struct dom_tree_node *node, void *data ATTRIBUTE_UNUSED)
+ {
+   edge e;
+   edge_iterator ei;
+   struct dom_tree_node *son;
+   unsigned index;
+   basic_block bb;
+   bitmap_iterator bi;
+ 
+   node->df = BITMAP_XMALLOC ();
+ 
+   FOR_EACH_EDGE (e, ei, node->bb->succs)
+     {
+       /* If the block does not belong to the area of liveness, ignore it.  */
+       if (!e->dest->aux)
+ 	continue;
+ 
+       if (dominated_by_p (CDI_DOMINATORS, e->dest, node->bb))
+ 	continue;
+ 
+       bitmap_set_bit (node->df, e->dest->index);
+     }
+ 
+   for (son = node->son; son; son = son->next)
+     {
+       EXECUTE_IF_SET_IN_BITMAP (son->df, 0, index, bi)
+ 	{
+ 	  bb = BASIC_BLOCK (index);
+ 
+ 	  if (!dominated_by_p (CDI_DOMINATORS, bb, node->bb))
+ 	    bitmap_set_bit (node->df, index);
+ 	}
+     }
+ }
+ 
+ /* Calculate dominance frontiers in DOM_TREE.  */
+ 
+ static void
+ calculate_df (struct dom_tree_node *dom_tree)
+ {
+   walk_dom_tree (dom_tree, NULL, wdt_calc_df, NULL);
+ }
+ 
+ /* Create a phi node for VALUE in NODE and record new definitions and uses.
+    Returns true if there is not another definition for value in node.  */
+ 
+ static void
+ create_a_phi (struct ssa_update_value *value,
+ 	      struct dom_tree_node *node)
+ {
+   tree name;
+   tree phi = create_phi_node (value->decl, node->bb), aphi = phi;
+   edge e;
+   edge_iterator ei;
+   unsigned i;
+   struct dom_tree_node *unode;
+ 
+   /* FIXME -- for now we simply copy the values attached to the newly created
+      ssa name from the original ssa name of the value.  This would be
+      wrong in the case the pass calling update_ssa_form would make such
+      information more precise in the original definition (and possibly some
+      of the copies).
+ 
+      So we need to replace this by a trivial dataflow over the newly created
+      phi nodes that merges the information once the optimizations will start
+      to need this (alternatively even without this they may create the phi
+      nodes together with the appropriate information themselves and call
+      update_ssa_form with USF_PHIS_ALREADY_EXIST, but in some cases this might
+      be quite inconvenient).  */
+   name = duplicate_ssa_name (value->orig_name, phi);
+   SET_PHI_RESULT (phi, name);
+   node->defs = new_valdef (value, PHI_RESULT_PTR (phi), node->defs);
+ 
+   FOR_EACH_EDGE (e, ei, node->bb->preds)
+     {
+       add_phi_arg (&phi, name, e);
+     }
+ 
+   /* Phi should not get reallocated (if it happened, def_operand_p to
+      the result would get invalidated).  */
+   gcc_assert (phi == aphi);
+ 
+   for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
+     {
+       e = PHI_ARG_EDGE (phi, i);
+       unode = e->src->aux;
+       unode->uses = new_valuse (value, PHI_ARG_DEF_PTR (phi, i), unode->uses);
+     }
+ }
+ 
+ /* Walk dominance frontiers from NODE and create new phi nodes for VALUE if
+    necessary.  */
+ 
+ static void
+ create_new_phi_nodes_for (struct ssa_update_value *value,
+ 			  struct dom_tree_node *node)
+ {
+   bitmap_iterator bi;
+   unsigned index;
+   basic_block bb;
+   struct dom_tree_node *bb_node;
+ 
+   EXECUTE_IF_SET_IN_BITMAP (node->df, 0, index, bi)
+     {
+       bb = BASIC_BLOCK (index);
+       bb_node = bb->aux;
+ 
+       if (!bb_node->values_live)
+ 	continue;
+       if (!bitmap_bit_p (bb_node->values_live, value->id))
+ 	continue;
+       bitmap_clear_bit (bb_node->values_live, value->id);
+ 
+       create_a_phi (value, bb_node);
+       create_new_phi_nodes_for (value, bb_node);
+     }
+ }
+ 
+ /* Create new phi nodes for values in NODE.  Callback for walk_dom_tree.  */
+ 
+ static void
+ wdt_create_new_phi_nodes (struct dom_tree_node *node,
+ 			  void *data ATTRIBUTE_UNUSED)
+ {
+   struct valdef *def;
+ 
+   for (def = node->defs; def; def = def->next)
+     create_new_phi_nodes_for (def->val, node);
+ }
+ 
+ /* Create new phi nodes for values in DOM_TREE.  */
+ 
+ static void
+ create_new_phi_nodes (struct dom_tree_node *dom_tree)
+ {
+   walk_dom_tree (dom_tree, wdt_create_new_phi_nodes, NULL, NULL);
+ }
+ 
+ /* Rewrites uses in basic block corresponding to NODE and registers new
+    definitions.  Callback for walk_dom_tree.  */
+ 
+ static void
+ wdt_rewrite_uses_in (struct dom_tree_node *node, void *data ATTRIBUTE_UNUSED)
+ {
+   struct valuse *use;
+   struct valdef *def;
+   tree stmt;
+ 
+   /* Definitions in the newly created phi nodes need to be processed before
+      uses (there may be also definitions in phi nodes that were not created
+      by this optimization, but in that case there are no uses of the value
+      in this block due to update_ssa_form_locally, so processing them here is
+      harmless).  */
+   for (def = node->defs; def; def = def->next)
+     {
+       stmt = SSA_NAME_DEF_STMT (DEF_FROM_PTR (def->op));
+ 
+       if (TREE_CODE (stmt) != PHI_NODE)
+ 	continue;
+ 
+       def->next_in_stack = def->val->stack;
+       def->val->stack = def;
+     }
+ 
+   /* Next come the uses that are not in phi nodes.  */
+   for (use = node->uses; use; use = use->next)
+     {
+       stmt = USE_STMT (use->op);
+       if (TREE_CODE (stmt) != PHI_NODE)
+ 	rewrite_by_vd (use, use->val->stack);
+     }
+ 
+   /* Now record non-phi defs.  Due to update_ssa_form_locally they must indeed
+      be after uses.  */
+   for (def = node->defs; def; def = def->next)
+     {
+       stmt = SSA_NAME_DEF_STMT (DEF_FROM_PTR (def->op));
+ 
+       if (TREE_CODE (stmt) == PHI_NODE)
+ 	continue;
+ 
+       def->next_in_stack = def->val->stack;
+       def->val->stack = def;
+     }
+ 
+   /* Next come the uses in newly created (possibly -- see the comment for defs)
+      that are in phi nodes.  */
+   for (use = node->uses; use; use = use->next)
+     {
+       stmt = USE_STMT (use->op);
+       if (TREE_CODE (stmt) == PHI_NODE)
+ 	rewrite_by_vd (use, use->val->stack);
+     }
+ }
+ 
+ /* Restores definitions in NODE.  Callback for walk_dom_tree.  */
+ 
+ static void
+ wdt_rewrite_uses_out (struct dom_tree_node *node, void *data ATTRIBUTE_UNUSED)
+ {
+   struct valdef *def;
+ 
+   for (def = node->defs; def; def = def->next)
+     {
+       def->val->stack = def->next_in_stack;
+       def->next_in_stack = NULL;
+     }
+ }
+ 
+ /* Rewrite uses in DOM_TREE by their reaching definitions.  */
+ 
+ static void
+ rewrite_uses (struct dom_tree_node *dom_tree)
+ {
+   walk_dom_tree (dom_tree, wdt_rewrite_uses_in, wdt_rewrite_uses_out, NULL);
+ }
+ 
+ /* Release memory for VALUES.  */
+ 
+ static void
+ free_values_list (struct ssa_update_value *values)
+ {
+   struct ssa_update_value *value, *next;
+ 
+   for (value = values; value; value = next)
+     {
+       next = value->next;
+ 
+       free_value (value);
+     }
+ }
+ 
+ /* Releases memory occupied by NODE.  Callback for walk_dom_tree.  */
+ 
+ static void
+ wdt_free_dom_node (struct dom_tree_node *node, void *data ATTRIBUTE_UNUSED)
+ {
+   struct valdef *def, *ndef;
+   struct valuse *use, *nuse;
+ 
+   for (def = node->defs; def; def = ndef)
+     {
+       ndef = def->next;
+       free (def);
+     }
+   for (use = node->uses; use; use = nuse)
+     {
+       nuse = use->next;
+       free (use);
+     }
+ 
+   if (node->df)
+     BITMAP_XFREE (node->df);
+ 
+   if (node->values_live)
+     BITMAP_XFREE (node->values_live);
+ 
+   free (node);
+ }
+ 
+ /* Release memory for DOM_TREE.  */
+ 
+ static void
+ free_dom_subtree (struct dom_tree_node *dom_tree)
+ {
+   walk_dom_tree (dom_tree, NULL, wdt_free_dom_node, NULL);
+ }
+ 
+ /* Update ssa form for VALUES.  If USF_PHIS_ALREADY_EXIST is set in FLAGS,
+    assumes that it is not necessary to create any new phi nodes (i.e. only
+    rewrites the uses by dominating definitions.  The VALUES list is freed
+    by the function.  */
+ 
+ void
+ update_ssa_form (struct ssa_update_value *values, unsigned flags)
+ {
+   bitmap interesting_blocks;
+   struct ssa_update_value *value;
+   struct dom_tree_node *dom_tree;
+   unsigned id, n, i;
+   bitmap_iterator bi;
+   bool large_area;
+   struct aux_contents aux_contents;
+ 
+   if (!values)
+     return;
+ 
+   values = update_ssa_form_locally (values);
+   if (!values)
+     return;
+ 
+   interesting_blocks = BITMAP_XMALLOC ();
+ 
+   for (value = values, id = 0; value; value = value->next, id++)
+     {
+       value->id = id; 
+       if (flags & USF_PHIS_ALREADY_EXIST)
+ 	mark_use_and_def_blocks (value, interesting_blocks);
+       else
+ 	mark_liveness_area (value, interesting_blocks);
+     }
+ 
+   n = 0;
+   EXECUTE_IF_SET_IN_BITMAP (interesting_blocks, 0, i, bi)
+     {
+       n++;
+     }
+ 
+   if (n_basic_blocks < LARGE_AREA_BASE)
+     large_area = true;
+   else
+     large_area = (100 * n > LARGE_AREA_FRACTION * (unsigned) n_basic_blocks);
+ 
+   if (large_area)
+     dom_tree = create_dom_subtree_walk_whole (interesting_blocks);
+   else
+     dom_tree = create_dom_subtree_incremental (interesting_blocks);
+   BITMAP_XFREE (interesting_blocks);
+ 
+   /* We need to use aux fields at blocks, but we cannot assume that the caller
+      does not already use them.  So save the original contents here and restore
+      it at the end.  */
+   aux_contents = save_aux_fields (dom_tree, n + 1);
+ 
+   attach_use_and_def_info_to_dom_tree (dom_tree, values);
+ 
+   if (!(flags & USF_PHIS_ALREADY_EXIST))
+     {
+       calculate_df (dom_tree);
+       create_new_phi_nodes (dom_tree);
+     }
+ 
+   rewrite_uses (dom_tree);
+ 
+   restore_aux_fields (dom_tree, aux_contents);
+   free_values_list (values);
+   free_dom_subtree (dom_tree);
+ }
+ 
+ /* Updates ssa form for all defs registered through rewrite_new_def.
+    FLAGS are passed to update_ssa_form.  */
+ 
+ void
+ update_ssa_form_for_registered_defs (unsigned flags)
+ {
+   update_ssa_form (get_values_for_ssa_form_update (), flags);
+   ssa_form_updated_all ();
+ }
+ 
+ /* Management of ssa names for that ssa form is violated.  */
+ 
+ struct ssa_name_eqto_elt
+ {
+   /* The ssa name version.  */
+   unsigned ver;
+ 
+   /* Operand for the definition.  */
+   def_operand_p op;
+ 
+   /* Original definition.  */
+   tree orig;
+ 
+   /* Next definition in chain of the new definitions.  */
+   struct ssa_name_eqto_elt *next;
+ 
+   /* Previous definition in the chain.  */
+   struct ssa_name_eqto_elt *prev;
+ };
+ 
+ static varray_type ssa_name_eqto;
+ 
+ static bitmap ssa_name_eqto_set;
+ 
+ /* Initializes the records for ssa names.  */
+ 
+ void
+ ssa_name_eqto_init (void)
+ {
+   VARRAY_GENERIC_PTR_NOGC_INIT (ssa_name_eqto, 100, "ssa_name_eqto");
+   ssa_name_eqto_set = BITMAP_XMALLOC ();
+ }
+ 
+ /* Returns entry for NAME in ssa_name_eqto array.  */
+ 
+ static struct ssa_name_eqto_elt *
+ get_ssa_name_eqto_entry (tree name)
+ {
+   unsigned ver = SSA_NAME_VERSION (name);
+   struct ssa_name_eqto_elt *elt;
+ 
+   if (ver >= VARRAY_SIZE (ssa_name_eqto))
+     VARRAY_GROW (ssa_name_eqto, 5 * ver / 4);
+ 
+   elt = VARRAY_GENERIC_PTR_NOGC (ssa_name_eqto, ver);
+   if (!elt)
+     {
+       elt = xmalloc (sizeof (struct ssa_name_eqto_elt));
+       elt->ver = SSA_NAME_VERSION (name);
+       elt->orig = NULL;
+       elt->prev = NULL;
+       elt->next = NULL;
+ 
+       VARRAY_GENERIC_PTR_NOGC (ssa_name_eqto, ver) = elt;
+     }
+ 
+   return elt;
+ }
+ 
+ /* Returns a def operand pointer for NAME.  */
+ 
+ static def_operand_p
+ def_op_for_name (tree name)
+ {
+   tree stmt = SSA_NAME_DEF_STMT (name);
+   def_operand_p ret;
+   ssa_op_iter oi;
+   unsigned flags;
+ 
+   if (TREE_CODE (stmt) == PHI_NODE)
+     return PHI_RESULT_PTR (stmt);
+ 
+   get_stmt_operands (stmt);
+ 
+   if (is_gimple_reg (name))
+     flags = SSA_OP_DEF;
+   else
+     flags = SSA_OP_VIRTUAL_DEFS;
+ 
+   FOR_EACH_SSA_DEF_OPERAND (ret, stmt, oi, flags)
+     {
+       if (DEF_FROM_PTR (ret) == name)
+ 	return ret;
+     }
+ 
+   gcc_unreachable ();
+ }
+ 
+ /* Returns entry for NAME in ssa_name_eqto array.  If there is no entry
+    for NAME yet, create it and mark it as original.  */
+ 
+ static struct ssa_name_eqto_elt *
+ get_ssa_name_eqto_entry_orig (tree name)
+ {
+   struct ssa_name_eqto_elt *elt = get_ssa_name_eqto_entry (name);
+ 
+   if (elt->orig)
+     return elt;
+ 
+   elt->orig = name;
+   elt->next = elt;
+   elt->prev = elt;
+   elt->op = def_op_for_name (name);
+   bitmap_set_bit (ssa_name_eqto_set, SSA_NAME_VERSION (name));
+ 
+   return elt;
+ }
+ 
+ /* Returns true if there is any ssa name with equivalent definitions
+    set.  */
+ 
+ bool
+ any_values_for_ssa_update_p (void)
+ {
+   return bitmap_first_set_bit (ssa_name_eqto_set) >= 0;
+ }
+ 
+ /* Returns a bitmap of ssa names with equivalent definitions set.  */
+ 
+ bitmap
+ ssa_names_for_ssa_update (void)
+ {
+   bitmap ret = BITMAP_XMALLOC ();
+   bitmap_copy (ret, ssa_name_eqto_set);
+   return ret;
+ }
+ 
+ /* Returns a def operand for DEF.  */
+ 
+ static def_operand_p
+ eqto_entry_def_op (struct ssa_name_eqto_elt *def)
+ {
+   tree stmt = SSA_NAME_DEF_STMT (ssa_name (def->ver));
+ 
+   if (TREE_CODE (stmt) == PHI_NODE)
+     {
+       /* The def operand may get invalidated if the phi node is
+ 	 reallocated, so determine it again.  */
+       return PHI_RESULT_PTR (stmt);
+     }
+   else
+     return def->op;
+ }
+ 
+ /* Get list of equivalent definitions for NAME.  */
+ 
+ struct usf_def_list *
+ get_defs_to_update (tree name)
+ {
+   struct usf_def_list *ret, **last = &ret, *act_usf;
+   struct ssa_name_eqto_elt *act = get_ssa_name_eqto_entry (name), *end;
+ 
+   if (!act->orig)
+     return NULL;
+ 
+   act = get_ssa_name_eqto_entry (act->orig);
+   end = act;
+   do
+     {
+       act_usf = xmalloc (sizeof (struct usf_def_list));
+       act_usf->op = eqto_entry_def_op (act);
+       *last = act_usf;
+       last = &act_usf->next;
+ 
+       act = act->next;
+     } while (act != end);
+ 
+   *last = NULL;
+   return ret;
+ }
+ 
+ /* Finds uses for update for DEFS.  */
+ 
+ static struct usf_use_list *
+ get_uses_to_update (struct usf_def_list *defs)
+ {
+   struct usf_use_list *uses, *nw;
+   struct usf_def_list *def;
+   tree name;
+   use_operand_p use;
+   imm_use_iterator iui;
+ 
+   uses = NULL;
+   for (def = defs; def; def = def->next)
+     {
+       name = DEF_FROM_PTR (def->op);
+ 
+       FOR_EACH_IMM_USE_FAST (use, iui, name)
+ 	{
+ 	  nw = xmalloc (sizeof (struct usf_use_list));
+ 	  nw->op = use;
+ 	  nw->next = uses;
+ 	  uses = nw;
+ 	}
+     }
+ 
+   return uses;
+ }
+ 
+ /* Releases a list of definitions DEFS.  */
+ 
+ void
+ free_def_list (struct usf_def_list *defs)
+ {
+   struct usf_def_list *act, *next;
+ 
+   for (act = defs; act; act = next)
+     {
+       next = act->next;
+ 
+       free (act);
+     }
+ }
+ 
+ /* Get all recorded definitions to update.  */
+ 
+ struct ssa_update_value *
+ get_values_for_ssa_form_update (void)
+ {
+   struct ssa_update_value *ret, **last, *act;
+   bitmap_iterator bi;
+   unsigned ver;
+   tree name;
+ 
+   last = &ret;
+ 
+   EXECUTE_IF_SET_IN_BITMAP (ssa_name_eqto_set, 0, ver, bi)
+     {
+       name = ssa_name (ver);
+       act = xcalloc (1, sizeof (struct ssa_update_value));
+ 
+       act->decl = SSA_NAME_VAR (name);
+       act->orig_name = name;
+       act->defs = get_defs_to_update (name);
+       act->uses = get_uses_to_update (act->defs);
+       *last = act;
+       last = &act->next;
+     }
+   *last = NULL;
+ 
+   return ret;
+ }
+ 
+ /* Returns the original ssa name to that NAME is equivalent.  */
+ 
+ tree
+ original_equivalent_name (tree name)
+ {
+   struct ssa_name_eqto_elt *elt = get_ssa_name_eqto_entry (name);
+ 
+   if (!elt->orig)
+     {
+       /* No name was set as original to NAME yet.  So consider NAME to be
+ 	 original.  */
+ 
+       return name;
+     }
+ 
+   return elt->orig;
+ }
+ 
+ /* Rewrites the definition DEF in statement STMT by new ssa name.  The ssa
+    name is returned.  The new ssa name is recorded as one of the aliases of
+    the old one.  */
+ 
+ tree
+ rewrite_new_def (tree stmt, def_operand_p def)
+ {
+   tree name = DEF_FROM_PTR (def);
+   tree orig = original_equivalent_name (name);
+   tree new_name = duplicate_ssa_name (orig, stmt);
+   struct ssa_name_eqto_elt *orig_elt, *new_elt;
+ 
+   SET_DEF (def, new_name);
+ 
+   if (TREE_CODE (stmt) == PHI_NODE)
+     {
+       edge e;
+       edge_iterator ei;
+       basic_block bb = bb_for_stmt (stmt);
+ 
+       /* Mark the result of abnormal phi node if needed.  */
+       FOR_EACH_EDGE (e, ei, bb->preds)
+ 	{
+ 	  if (e->flags & EDGE_ABNORMAL)
+ 	    break;
+ 	}
+ 
+       if (e)
+ 	SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name) = 1;
+     }
+ 
+   orig_elt = get_ssa_name_eqto_entry_orig (orig);
+   new_elt = get_ssa_name_eqto_entry (new_name);
+ 
+   new_elt->orig = orig;
+   new_elt->prev = orig_elt->prev;
+   new_elt->prev->next = new_elt;
+   orig_elt->prev = new_elt;
+   new_elt->next = orig_elt;
+   new_elt->op = def;
+ 
+   return new_name;
+ }
+ 
+ /* Records that form updating for NAME was performed.  */
+ 
+ void
+ ssa_form_updated (tree name)
+ {
+   struct ssa_name_eqto_elt *elt = get_ssa_name_eqto_entry (name);
+   struct ssa_name_eqto_elt *next, *end;
+ 
+   if (!elt->orig)
+     return;
+ 
+   bitmap_clear_bit (ssa_name_eqto_set, SSA_NAME_VERSION (elt->orig));
+ 
+   end = elt;
+   do
+     {
+       next = elt->next;
+ 
+       elt->orig = NULL;
+       elt->next = NULL;
+       elt->prev = NULL;
+ 
+       elt = next;
+     } while (elt != end);
+ }
+ 
+ /* Records that ssa form updating for all recorded ssa names was performed.  */
+ 
+ void
+ ssa_form_updated_all (void)
+ {
+   bitmap_iterator bi;
+   unsigned ver;
+   bitmap defs = ssa_names_for_ssa_update ();
+ 
+   EXECUTE_IF_SET_IN_BITMAP (defs, 0, ver, bi)
+     {
+       ssa_form_updated (ssa_name (ver));
+     }
+ 
+   BITMAP_XFREE (defs);
+ }
+ 
+ /* Releases ssa name NAME from eqto tables.  */
+ 
+ void
+ release_ssa_name_from_eqto (tree name)
+ {
+   struct ssa_name_eqto_elt *elt = get_ssa_name_eqto_entry (name);
+   struct ssa_name_eqto_elt *prev, *next;
+   tree orig, eq;
+   use_operand_p use;
+   imm_use_iterator iui;
+ 
+   if (!elt->orig)
+     return;
+ 
+   next = elt->next;
+   prev = elt->prev;
+   orig = elt->orig;
+   elt->next = elt->prev = NULL;
+   elt->orig = NULL_TREE;
+ 
+   if (orig == name)
+     bitmap_clear_bit (ssa_name_eqto_set, SSA_NAME_VERSION (name));
+ 
+   if (next == elt)
+     {
+       gcc_assert (orig == name);
+       return;
+     }
+ 
+   /* Since there are equivalent ssa names, it is possible that there still may
+      be uses of this ssa name that will not be removed when the definition
+      ceases to exist.  So rewrite the uses to some of the equivalents.  */
+ 
+   if (orig != name)
+     eq = orig;
+   else
+     eq = ssa_name (next->ver);
+ 
+   FOR_EACH_IMM_USE_SAFE (use, iui, name)
+     {
+       SET_USE (use, eq);
+     }
+ 
+   next->prev = prev;
+   prev->next = next;
+ 
+   if (orig != name)
+     return;
+ 
+   /* Make the next element in the list the original.  */
+   bitmap_set_bit (ssa_name_eqto_set, next->ver);
+   orig = ssa_name (next->ver);
+ 
+   elt = next;
+   do
+     {
+       elt->orig = orig;
+       elt = elt->next;
+     } while (elt != next);
+ }
+ 
+ /* Rewrites USE by VER-th version of the definition.  */
+ 
+ static void
+ rewrite_use_by_ver (use_operand_p use, unsigned ver)
+ {
+   tree name = USE_FROM_PTR (use);
+   struct ssa_name_eqto_elt *act, *def_elt;
+ 
+   if (TREE_CODE (name) != SSA_NAME)
+     {
+       gcc_assert (is_gimple_min_invariant (name));
+       return;
+     }
+ 
+   act = get_ssa_name_eqto_entry (name);
+ 
+   /* Unless we have some alternative definitions for name recorded,
+      there is nothing to do.  */
+   if (!act->orig)
+     return;
+ 
+   act = def_elt = get_ssa_name_eqto_entry (act->orig);
+   for (; ver != 0; ver--)
+     {
+       def_elt = def_elt->next;
+ 
+       /* Check that we do not wrap around in the list.  */
+       gcc_assert (def_elt != act);
+     }
+ 
+   SET_USE (use, ssa_name (def_elt->ver));
+ }
+ 
+ /* Rewrites uses in BB by VER-th version of definitions.  */
+ 
+ void
+ rewrite_uses_bb (basic_block bb, unsigned ver)
+ {
+   block_stmt_iterator bsi;
+   edge_iterator ei;
+   tree phi, stmt;
+   ssa_op_iter oi;
+   use_operand_p use;
+   edge e;
+ 
+   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+     {
+       stmt = bsi_stmt (bsi);
+ 
+       FOR_EACH_SSA_USE_OPERAND (use, stmt, oi, SSA_OP_ALL_USES)
+ 	{
+ 	  rewrite_use_by_ver (use, ver);
+ 	}
+     }
+ 
+   FOR_EACH_EDGE (e, ei, bb->succs)
+     {
+       for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
+ 	{
+ 	  use = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
+ 	  rewrite_use_by_ver (use, ver);
+ 	}
+     }
+ }
+ 
+ /* Rewrites uses in REGION of size N_REGION by VER-th version of
+    definitions.  */
+ 
+ void
+ rewrite_uses_region (basic_block *region, unsigned n_region, unsigned ver)
+ {
+   unsigned i;
+ 
+   for (i = 0; i < n_region; i++)
+     rewrite_uses_bb (region[i], ver);
+ }
Index: tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.h,v
retrieving revision 1.636.2.2
diff -c -3 -p -r1.636.2.2 tree.h
*** tree.h	25 Oct 2004 06:37:33 -0000	1.636.2.2
--- tree.h	3 Nov 2004 00:00:20 -0000
*************** extern void replace_ssa_name_symbol (tre
*** 2812,2824 ****
  extern void ssanames_print_statistics (void);
  #endif
  
- extern void mark_for_rewrite (tree);
- extern void unmark_all_for_rewrite (void);
- extern bool marked_for_rewrite_p (tree);
- extern bool any_marked_for_rewrite_p (void);
- extern struct bitmap_head_def *marked_ssa_names (void);
- 
- 
  /* Return the (unique) IDENTIFIER_NODE node for a given name.
     The name is supplied as a char *.  */
  
--- 2812,2817 ----
*************** extern bool thread_through_all_blocks (v
*** 3958,3961 ****
--- 3951,3957 ----
  /* In tree-gimple.c.  */
  extern tree get_base_address (tree t);
  
+ /* In tree-update-ssa.c  */
+ void ssa_name_eqto_init (void);
+ 
  #endif  /* GCC_TREE_H  */


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]