diff options
| author | Zdenek Dvorak <dvorakz@suse.cz> | 2004-11-03 12:26:25 +0000 |
|---|---|---|
| committer | Zdenek Dvorak <dvorakz@suse.cz> | 2004-11-03 12:26:25 +0000 |
| commit | e5e1091f6fc6ab55d27bfde80951e406a1df24f6 (patch) | |
| tree | 1e89ba7d5b314c51474b368dc17d1408765a3f57 | |
| parent | 0552860a64353a75fdfe7017fc8f9be69e1dc69a (diff) | |
* Makefile.in (tree-update-ssa.o): Add.ssaupdate-branch
* 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.
git-svn-id: https://gcc.gnu.org/svn/gcc/branches/ssaupdate-branch@90026 138bc75d-0d04-0410-961f-82ee72b054a4
| -rw-r--r-- | gcc/ChangeLog.ssaupdate | 59 | ||||
| -rw-r--r-- | gcc/Makefile.in | 6 | ||||
| -rw-r--r-- | gcc/lambda-code.c | 2 | ||||
| -rw-r--r-- | gcc/toplev.c | 2 | ||||
| -rw-r--r-- | gcc/tree-cfg.c | 249 | ||||
| -rw-r--r-- | gcc/tree-flow.h | 64 | ||||
| -rw-r--r-- | gcc/tree-into-ssa.c | 530 | ||||
| -rw-r--r-- | gcc/tree-pretty-print.c | 18 | ||||
| -rw-r--r-- | gcc/tree-ssa-dom.c | 2 | ||||
| -rw-r--r-- | gcc/tree-ssa-loop-manip.c | 103 | ||||
| -rw-r--r-- | gcc/tree-ssa-threadupdate.c | 19 | ||||
| -rw-r--r-- | gcc/tree-ssanames.c | 69 | ||||
| -rw-r--r-- | gcc/tree-update-ssa.c | 1746 | ||||
| -rw-r--r-- | gcc/tree.h | 10 |
14 files changed, 1982 insertions, 897 deletions
diff --git a/gcc/ChangeLog.ssaupdate b/gcc/ChangeLog.ssaupdate index 8f1070b8834..f42d9a06d05 100644 --- a/gcc/ChangeLog.ssaupdate +++ b/gcc/ChangeLog.ssaupdate @@ -1,3 +1,62 @@ +2004-11-03 Zdenek Dvorak <dvorakz@suse.cz> + + * 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. + 2004-10-22 Zdenek Dvorak <dvorakz@suse.cz> Andrew MacLeod <amacleod@redhat.com> diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 50cf9dd5487..16f7ab304e2 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -888,7 +888,7 @@ C_OBJS = c-parse.o c-lang.o stub-objc.o $(C_AND_OBJC_OBJS) 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 \ + 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 \ @@ -1609,6 +1609,10 @@ tree-into-ssa.o : tree-into-ssa.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \ 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) \ diff --git a/gcc/lambda-code.c b/gcc/lambda-code.c index 3ba5c22c17f..0a0f26fca27 100644 --- a/gcc/lambda-code.c +++ b/gcc/lambda-code.c @@ -2305,10 +2305,8 @@ perfect_nestify (struct loops *loops, 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) diff --git a/gcc/toplev.c b/gcc/toplev.c index eaeeecaca4d..11b139f7b15 100644 --- a/gcc/toplev.c +++ b/gcc/toplev.c @@ -1620,6 +1620,8 @@ general_init (const char *argv0) /* 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. */ diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c index 6cfbfc6224f..3ce7d8913c6 100644 --- a/gcc/tree-cfg.c +++ b/gcc/tree-cfg.c @@ -4505,8 +4505,9 @@ tree_duplicate_bb (basic_block bb) { basic_block new_bb; block_stmt_iterator bsi, bsi_tgt; - tree phi, val; + tree phi, new_phi; ssa_op_iter op_iter; + def_operand_p def; new_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb); @@ -4515,8 +4516,8 @@ tree_duplicate_bb (basic_block bb) 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); + 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))); @@ -4529,12 +4530,7 @@ tree_duplicate_bb (basic_block bb) 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. */ @@ -4542,6 +4538,11 @@ tree_duplicate_bb (basic_block bb) 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; @@ -4591,7 +4592,8 @@ add_phi_args_after_copy_bb (basic_block bb_copy) { phi_next = TREE_CHAIN (phi); - gcc_assert (PHI_RESULT (phi) == PHI_RESULT (phi_copy)); + 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); } @@ -4617,190 +4619,6 @@ add_phi_args_after_copy (basic_block *region_copy, unsigned n_region) region_copy[i]->rbi->duplicated = 0; } -/* Maps the old ssa name FROM_NAME to TO_NAME. */ - -struct ssa_name_map_entry -{ - tree from_name; - tree to_name; -}; - -/* Hash function for ssa_name_map_entry. */ - -static hashval_t -ssa_name_map_entry_hash (const void *entry) -{ - const struct ssa_name_map_entry *en = entry; - return SSA_NAME_VERSION (en->from_name); -} - -/* Equality function for ssa_name_map_entry. */ - -static int -ssa_name_map_entry_eq (const void *in_table, const void *ssa_name) -{ - const struct ssa_name_map_entry *en = in_table; - - return en->from_name == ssa_name; -} - -/* Allocate duplicates of ssa names in list DEFINITIONS and store the mapping - to MAP. */ - -void -allocate_ssa_names (bitmap definitions, htab_t *map) -{ - tree name; - struct ssa_name_map_entry *entry; - PTR *slot; - unsigned ver; - bitmap_iterator bi; - - if (!*map) - *map = htab_create (10, ssa_name_map_entry_hash, - ssa_name_map_entry_eq, free); - EXECUTE_IF_SET_IN_BITMAP (definitions, 0, ver, bi) - { - name = ssa_name (ver); - slot = htab_find_slot_with_hash (*map, name, SSA_NAME_VERSION (name), - INSERT); - if (*slot) - entry = *slot; - else - { - entry = xmalloc (sizeof (struct ssa_name_map_entry)); - entry->from_name = name; - *slot = entry; - } - entry->to_name = duplicate_ssa_name (name, SSA_NAME_DEF_STMT (name)); - } -} - -/* Rewrite the definition DEF in statement STMT to new ssa name as specified - by the mapping MAP. */ - -static void -rewrite_to_new_ssa_names_def (def_operand_p def, tree stmt, htab_t map) -{ - tree name = DEF_FROM_PTR (def); - struct ssa_name_map_entry *entry; - - gcc_assert (TREE_CODE (name) == SSA_NAME); - - entry = htab_find_with_hash (map, name, SSA_NAME_VERSION (name)); - if (!entry) - return; - - SET_DEF (def, entry->to_name); - SSA_NAME_DEF_STMT (entry->to_name) = stmt; -} - -/* Rewrite the USE to new ssa name as specified by the mapping MAP. */ - -static void -rewrite_to_new_ssa_names_use (use_operand_p use, htab_t map) -{ - tree name = USE_FROM_PTR (use); - struct ssa_name_map_entry *entry; - - if (TREE_CODE (name) != SSA_NAME) - return; - - entry = htab_find_with_hash (map, name, SSA_NAME_VERSION (name)); - if (!entry) - return; - - SET_USE (use, entry->to_name); -} - -/* Rewrite the ssa names in basic block BB to new ones as specified by the - mapping MAP. */ - -void -rewrite_to_new_ssa_names_bb (basic_block bb, htab_t map) -{ - unsigned i; - edge e; - edge_iterator ei; - tree phi, stmt; - block_stmt_iterator bsi; - use_optype uses; - vuse_optype vuses; - def_optype defs; - v_may_def_optype v_may_defs; - v_must_def_optype v_must_defs; - stmt_ann_t ann; - - FOR_EACH_EDGE (e, ei, bb->preds) - if (e->flags & EDGE_ABNORMAL) - break; - - for (phi = phi_nodes (bb); phi; phi = 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 @@ -4823,7 +4641,6 @@ tree_duplicate_sese_region (edge entry, edge exit, bitmap definitions; tree phi, var; basic_block *doms; - htab_t ssa_name_map = NULL; edge redirected; bitmap_iterator bi; @@ -4871,7 +4688,7 @@ tree_duplicate_sese_region (edge entry, edge exit, free_region_copy = true; } - gcc_assert (!any_marked_for_rewrite_p ()); + gcc_assert (!any_values_for_ssa_update_p ()); /* Record blocks outside the region that are duplicated by something inside. */ @@ -4879,7 +4696,7 @@ tree_duplicate_sese_region (edge entry, edge exit, n_doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region, doms); copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop); - definitions = marked_ssa_names (); + definitions = ssa_names_for_ssa_update (); if (copying_header) { @@ -4912,31 +4729,39 @@ tree_duplicate_sese_region (edge entry, edge exit, are used outside region. */ EXECUTE_IF_SET_IN_BITMAP (definitions, 0, ver, bi) { - tree name = ssa_name (ver); + tree name, new_orig_name; + struct usf_def_list *copy_def, *orig_def; - phi = create_phi_node (name, exit->dest); - add_phi_arg (&phi, name, exit); - add_phi_arg (&phi, name, exit_copy); + 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); - /* 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); + /* 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); - unmark_all_for_rewrite (); - BITMAP_XFREE (definitions); - return true; } diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h index 727737cf92b..fd076799f5d 100644 --- a/gcc/tree-flow.h +++ b/gcc/tree-flow.h @@ -481,9 +481,6 @@ extern bool tree_duplicate_sese_region (edge, edge, basic_block *, unsigned, 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); @@ -568,7 +565,6 @@ extern void kill_redundant_phi_nodes (void); /* 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); @@ -728,6 +724,66 @@ extern bool expr_invariant_in_loop_p (struct loop *loop, tree expr); 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 */ diff --git a/gcc/tree-into-ssa.c b/gcc/tree-into-ssa.c index 84a6904cce2..e0b61598cb7 100644 --- a/gcc/tree-into-ssa.c +++ b/gcc/tree-into-ssa.c @@ -66,9 +66,6 @@ struct def_blocks_d 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; @@ -119,22 +116,6 @@ struct mark_def_sites_global_data 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. */ @@ -145,11 +126,11 @@ static void mark_def_sites (struct dom_walk_data *walk_data, 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_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 *, bitmap); +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); @@ -163,26 +144,12 @@ static inline struct def_blocks_d *get_def_blocks_for (tree); 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; + return var_ann (var)->need_phi_state; } /* Sets phi_state field for VAR to STATE. */ @@ -190,10 +157,7 @@ get_phi_state (tree var) 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; + var_ann (var)->need_phi_state = state; } /* Return the current definition for VAR. */ @@ -201,10 +165,7 @@ set_phi_state (tree var, enum need_phi_state state) 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; + return var_ann (var)->current_def; } /* Sets current definition of VAR to DEF. */ @@ -212,10 +173,7 @@ get_current_def (tree var) 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; + var_ann (var)->current_def = def; } /* Compute global livein information given the set of blockx where @@ -284,65 +242,6 @@ mark_def_sites_initialize_block (struct dom_walk_data *walk_data, 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: @@ -402,7 +301,7 @@ mark_def_sites (struct dom_walk_data *walk_data, 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); + set_def_block (DEF_FROM_PTR (def_p), bb); } } @@ -411,68 +310,22 @@ mark_def_sites (struct dom_walk_data *walk_data, { if (prepare_def_operand_for_rename (def, &uid)) { - set_def_block (def, bb, false, false); + set_def_block (def, bb); 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. */ +/* Mark block BB as the definition site for variable VAR. */ static void -set_def_block (tree var, basic_block bb, bool phi_p, bool ssa_p) +set_def_block (tree var, basic_block bb) { struct def_blocks_d *db_p; enum need_phi_state state; - if (!ssa_p - && TREE_CODE (var) == SSA_NAME) + if (TREE_CODE (var) == SSA_NAME) var = SSA_NAME_VAR (var); state = get_phi_state (var); @@ -480,8 +333,6 @@ set_def_block (tree var, basic_block bb, bool phi_p, bool ssa_p) /* 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. @@ -597,11 +448,10 @@ void insert_phi_nodes_1 (tree var, bitmap *dfs, varray_type *work_stack) 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. */ + mark_def_sites). */ static void -insert_phi_nodes (bitmap *dfs, bitmap names_to_rename) +insert_phi_nodes (bitmap *dfs) { size_t i; varray_type work_stack; @@ -617,15 +467,7 @@ insert_phi_nodes (bitmap *dfs, bitmap names_to_rename) 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) + 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); @@ -691,82 +533,6 @@ rewrite_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, } } -/* 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 @@ -799,40 +565,6 @@ rewrite_add_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, } } -/* 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 @@ -869,32 +601,6 @@ rewrite_finalize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, } } -/* 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 @@ -1019,10 +725,6 @@ insert_phi_nodes_for (tree var, bitmap *dfs, varray_type *work_stack) } } - /* 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); @@ -1092,54 +794,6 @@ rewrite_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, } } -/* 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. */ @@ -1249,7 +903,6 @@ def_blocks_free (void *p) { struct def_blocks_d *entry = p; BITMAP_XFREE (entry->def_blocks); - BITMAP_XFREE (entry->phi_blocks); BITMAP_XFREE (entry->livein_blocks); free (entry); } @@ -1321,7 +974,6 @@ get_def_blocks_for (tree var) 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; } @@ -1495,7 +1147,7 @@ rewrite_into_ssa (bool all) sbitmap_free (mark_def_sites_global_data.kills); /* Insert PHI nodes at dominance frontiers of definition blocks. */ - insert_phi_nodes (dfs, NULL); + insert_phi_nodes (dfs); /* Rewrite all the basic blocks in the program. */ timevar_push (TV_TREE_SSA_REWRITE_BLOCKS); @@ -1545,158 +1197,6 @@ rewrite_into_ssa (bool all) 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 diff --git a/gcc/tree-pretty-print.c b/gcc/tree-pretty-print.c index ffeada0b8de..82c81d8fa22 100644 --- a/gcc/tree-pretty-print.c +++ b/gcc/tree-pretty-print.c @@ -1454,9 +1454,21 @@ dump_generic_node (pretty_printer *buffer, tree node, int spc, int flags, 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)); + { + 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: diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c index 4f95f9f4558..6f82bde3482 100644 --- a/gcc/tree-ssa-dom.c +++ b/gcc/tree-ssa-dom.c @@ -387,7 +387,7 @@ tree_ssa_dominator_optimize (void) cfg_altered = cleanup_tree_cfg (); calculate_dominance_info (CDI_DOMINATORS); - rewrite_ssa_into_ssa (); + update_ssa_form_for_registered_defs (0); /* Reinitialize the various tables. */ bitmap_clear (nonzero_vars); diff --git a/gcc/tree-ssa-loop-manip.c b/gcc/tree-ssa-loop-manip.c index 5be6d377962..8efb4950d9b 100644 --- a/gcc/tree-ssa-loop-manip.c +++ b/gcc/tree-ssa-loop-manip.c @@ -138,11 +138,9 @@ add_exit_phis_edge (basic_block exit, tree use) 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); - - SSA_NAME_DEF_STMT (use) = def_stmt; } /* Add exit phis for VAR that is used in LIVEIN. @@ -211,10 +209,11 @@ get_loops_exits (void) /* For USE in BB, if it is used outside of the loop it is defined in, mark it for rewrite. Record basic block BB where it is used - to USE_BLOCKS. */ + to USE_BLOCKS. Record the ssa name index to NEED_PHIS bitmap. */ static void -find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks) +find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks, + bitmap need_phis) { unsigned ver; basic_block def_bb; @@ -237,16 +236,16 @@ find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks) 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); + bitmap_set_bit (need_phis, ver); } /* For uses in STMT, mark names that are used outside of the loop they are defined to rewrite. Record the set of blocks in that the ssa - names are defined to USE_BLOCKS. */ + names are defined to USE_BLOCKS and the ssa names themselves to + NEED_PHIS. */ static void -find_uses_to_rename_stmt (tree stmt, bitmap *use_blocks) +find_uses_to_rename_stmt (tree stmt, bitmap *use_blocks, bitmap need_phis) { ssa_op_iter iter; tree var; @@ -255,15 +254,16 @@ find_uses_to_rename_stmt (tree stmt, bitmap *use_blocks) 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); + 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. */ + names are defined to USE_BLOCKS and the ssa names themselves to + NEED_PHIS. */ static void -find_uses_to_rename (bitmap *use_blocks) +find_uses_to_rename (bitmap *use_blocks, bitmap need_phis) { basic_block bb; block_stmt_iterator bsi; @@ -275,10 +275,12 @@ find_uses_to_rename (bitmap *use_blocks) 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); + 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); + find_uses_to_rename_stmt (bsi_stmt (bsi), use_blocks, + need_phis); } } @@ -313,29 +315,28 @@ rewrite_into_loop_closed_ssa (void) { bitmap loop_exits = get_loops_exits (); bitmap *use_blocks; - unsigned i; - bitmap names_to_rename; + unsigned i, old_num_ssa_names = num_ssa_names; + bitmap names_to_rename = BITMAP_XMALLOC (); - gcc_assert (!any_marked_for_rewrite_p ()); + gcc_assert (!any_values_for_ssa_update_p ()); - use_blocks = xcalloc (num_ssa_names, sizeof (bitmap)); + use_blocks = xcalloc (old_num_ssa_names, sizeof (bitmap)); /* Find the uses outside loops. */ - find_uses_to_rename (use_blocks); + 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. */ - names_to_rename = marked_ssa_names (); add_exit_phis (names_to_rename, use_blocks, loop_exits); - for (i = 0; i < num_ssa_names; i++) + for (i = 0; i < old_num_ssa_names; i++) BITMAP_XFREE (use_blocks[i]); free (use_blocks); BITMAP_XFREE (loop_exits); BITMAP_XFREE (names_to_rename); - /* Do the rewriting. */ - rewrite_ssa_into_ssa (); + /* Fix the ssa form. */ + update_ssa_form_for_registered_defs (0); } /* Check invariants of the loop closed ssa form for the USE in BB. */ @@ -532,43 +533,19 @@ copy_phi_node_args (unsigned first_new_block) } /* 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. */ + FIRST_NEW_BLOCK is the first block in the copied area. */ static void -rename_variables (unsigned first_new_block, bitmap definitions) +rename_variables (unsigned first_new_block) { - unsigned i, copy_number = 0; + unsigned i; 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); + rewrite_uses_bb (bb, bb->rbi->copy_number); } - - 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 @@ -587,10 +564,7 @@ tree_duplicate_loop_to_header_edge (struct loop *loop, edge e, unsigned int *n_to_remove, int flags) { unsigned first_new_block; - basic_block bb; - unsigned i; tree phi, arg, map, def; - bitmap definitions; if (!(loops->state & LOOPS_HAVE_SIMPLE_LATCHES)) return false; @@ -601,7 +575,7 @@ tree_duplicate_loop_to_header_edge (struct loop *loop, edge e, verify_loop_closed_ssa (); #endif - gcc_assert (!any_marked_for_rewrite_p ()); + 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, @@ -625,24 +599,9 @@ tree_duplicate_loop_to_header_edge (struct loop *loop, edge e, 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); + rename_variables (first_new_block); - /* 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); - } + ssa_form_updated_all (); scev_reset (); #ifdef ENABLE_CHECKING diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c index 6269b858291..5d05bea9791 100644 --- a/gcc/tree-ssa-threadupdate.c +++ b/gcc/tree-ssa-threadupdate.c @@ -103,22 +103,15 @@ static void 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); phi; phi = PHI_CHAIN (phi)) + for (phi = phi_nodes (bb), new_phi = phi_nodes (new_bb); + phi; + phi = PHI_CHAIN (phi), new_phi = PHI_CHAIN (new_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); + 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. */ diff --git a/gcc/tree-ssanames.c b/gcc/tree-ssanames.c index 848fa4f3cd1..a319a849ca7 100644 --- a/gcc/tree-ssanames.c +++ b/gcc/tree-ssanames.c @@ -61,9 +61,6 @@ Boston, MA 02111-1307, USA. */ /* 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; @@ -77,64 +74,6 @@ unsigned int ssa_name_nodes_reused; 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 @@ -245,12 +184,6 @@ release_ssa_name (tree var) 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 @@ -264,6 +197,8 @@ release_ssa_name (tree var) 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 diff --git a/gcc/tree-update-ssa.c b/gcc/tree-update-ssa.c new file mode 100644 index 00000000000..105818f3db4 --- /dev/null +++ b/gcc/tree-update-ssa.c @@ -0,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); +} diff --git a/gcc/tree.h b/gcc/tree.h index 43d41910d60..60ebfb29ef6 100644 --- a/gcc/tree.h +++ b/gcc/tree.h @@ -2812,13 +2812,6 @@ extern void replace_ssa_name_symbol (tree, tree); 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 *. */ @@ -3958,4 +3951,7 @@ extern bool thread_through_all_blocks (void); /* 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 */ |