From b0382c67cb60bf717f7ed330da1c36ca379381d8 Mon Sep 17 00:00:00 2001 From: Zdenek Dvorak Date: Wed, 4 Aug 2004 22:37:38 +0200 Subject: [PATCH] tree-cfg.c (tree_duplicate_bb): Mark duplicated definitions. * tree-cfg.c (tree_duplicate_bb): Mark duplicated definitions. * tree-flow.h (rewrite_ssa_into_ssa): Declaration changed. * tree-into-ssa.c (rewrite_ssa_into_ssa): Use new interface to manipulate the duplicated ssa names. * tree-ssanames.c (ssa_names_to_rewrite): New variable. (marked_for_rewrite_p, any_marked_for_rewrite_p, mark_for_rewrite, unmark_all_for_rewrite, marked_ssa_names, release_ssa_name_force): New functions. (release_ssa_name): Do not release ssa names that may have multiple definitions. * tree.h (release_ssa_name_force, mark_for_rewrite, unmark_all_for_rewrite, marked_for_rewrite_p, any_marked_for_rewrite_p, marked_ssa_names): Declare. * tree-ssa-loop-ch.c (mark_defs_for_rewrite): Remove. (duplicate_blocks): Remove call to mark_defs_for_rewrite. Update call to rewrite_ssa_into_ssa. Co-Authored-By: Jeff Law From-SVN: r85572 --- gcc/ChangeLog | 20 ++++++++++++ gcc/tree-cfg.c | 26 ++++++++++++++++ gcc/tree-flow.h | 2 +- gcc/tree-into-ssa.c | 18 ++++++----- gcc/tree-ssa-loop-ch.c | 63 +------------------------------------- gcc/tree-ssanames.c | 69 +++++++++++++++++++++++++++++++++++++++++- gcc/tree.h | 7 +++++ 7 files changed, 134 insertions(+), 71 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 0461d107dff..e62fdf50fc6 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,23 @@ +2004-08-04 Zdenek Dvorak + Jeff Law + + * tree-cfg.c (tree_duplicate_bb): Mark duplicated definitions. + * tree-flow.h (rewrite_ssa_into_ssa): Declaration changed. + * tree-into-ssa.c (rewrite_ssa_into_ssa): Use new interface to + manipulate the duplicated ssa names. + * tree-ssanames.c (ssa_names_to_rewrite): New variable. + (marked_for_rewrite_p, any_marked_for_rewrite_p, mark_for_rewrite, + unmark_all_for_rewrite, marked_ssa_names, release_ssa_name_force): + New functions. + (release_ssa_name): Do not release ssa names that may have multiple + definitions. + * tree.h (release_ssa_name_force, mark_for_rewrite, + unmark_all_for_rewrite, marked_for_rewrite_p, any_marked_for_rewrite_p, + marked_ssa_names): Declare. + * tree-ssa-loop-ch.c (mark_defs_for_rewrite): Remove. + (duplicate_blocks): Remove call to mark_defs_for_rewrite. + Update call to rewrite_ssa_into_ssa. + 2004-08-04 Mark Mitchell * defaults.h (TARGET_DECLSPEC): New macro. diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c index c9d2424cf4c..576531610eb 100644 --- a/gcc/tree-cfg.c +++ b/gcc/tree-cfg.c @@ -4297,8 +4297,19 @@ tree_duplicate_bb (basic_block bb) { basic_block new_bb; block_stmt_iterator bsi, bsi_tgt; + tree phi; + def_optype defs; + v_may_def_optype v_may_defs; + v_must_def_optype v_must_defs; + unsigned j; new_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb); + + for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi)) + { + mark_for_rewrite (PHI_RESULT (phi)); + } + bsi_tgt = bsi_start (new_bb); for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) { @@ -4308,6 +4319,21 @@ tree_duplicate_bb (basic_block bb) if (TREE_CODE (stmt) == LABEL_EXPR) continue; + /* Record the definitions. */ + get_stmt_operands (stmt); + + defs = STMT_DEF_OPS (stmt); + for (j = 0; j < NUM_DEFS (defs); j++) + mark_for_rewrite (DEF_OP (defs, j)); + + v_may_defs = STMT_V_MAY_DEF_OPS (stmt); + for (j = 0; j < NUM_V_MAY_DEFS (v_may_defs); j++) + mark_for_rewrite (V_MAY_DEF_RESULT (v_may_defs, j)); + + v_must_defs = STMT_V_MUST_DEF_OPS (stmt); + for (j = 0; j < NUM_V_MUST_DEFS (v_must_defs); j++) + mark_for_rewrite (V_MUST_DEF_OP (v_must_defs, j)); + copy = unshare_expr (stmt); /* Copy also the virtual operands. */ diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h index 600d46256c2..0a979ef02ce 100644 --- a/gcc/tree-flow.h +++ b/gcc/tree-flow.h @@ -581,7 +581,7 @@ extern void kill_redundant_phi_nodes (void); /* In tree-into-ssa.c */ extern void rewrite_into_ssa (bool); -extern void rewrite_ssa_into_ssa (bitmap); +extern void rewrite_ssa_into_ssa (void); void compute_global_livein (bitmap, bitmap); tree duplicate_ssa_name (tree, tree); diff --git a/gcc/tree-into-ssa.c b/gcc/tree-into-ssa.c index 4d5992e2d56..edeeab5f1bf 100644 --- a/gcc/tree-into-ssa.c +++ b/gcc/tree-into-ssa.c @@ -1740,11 +1740,11 @@ rewrite_into_ssa (bool all) timevar_pop (TV_TREE_SSA_OTHER); } -/* The ssa names in NAMES_TO_RENAME may have more than one definition; +/* The marked ssa names may have more than one definition; add phi nodes and rewrite them to fix this. */ void -rewrite_ssa_into_ssa (bitmap names_to_rename) +rewrite_ssa_into_ssa (void) { bitmap *dfs; basic_block bb; @@ -1753,9 +1753,11 @@ rewrite_ssa_into_ssa (bitmap names_to_rename) unsigned i; sbitmap snames_to_rename; tree name; + bitmap to_rename; - if (bitmap_first_set_bit (names_to_rename) < 0) + if (!any_marked_for_rewrite_p ()) return; + to_rename = marked_ssa_names (); timevar_push (TV_TREE_SSA_OTHER); @@ -1800,7 +1802,7 @@ rewrite_ssa_into_ssa (bitmap names_to_rename) snames_to_rename = sbitmap_alloc (num_ssa_names); sbitmap_zero (snames_to_rename); - EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, + EXECUTE_IF_SET_IN_BITMAP (to_rename, 0, i, SET_BIT (snames_to_rename, i)); mark_def_sites_global_data.kills = sbitmap_alloc (num_ssa_names); @@ -1826,7 +1828,7 @@ rewrite_ssa_into_ssa (bitmap names_to_rename) set_current_def (ssa_name (i), NULL_TREE); /* Insert PHI nodes at dominance frontiers of definition blocks. */ - insert_phi_nodes (dfs, names_to_rename); + insert_phi_nodes (dfs, to_rename); /* Rewrite all the basic blocks in the program. */ timevar_push (TV_TREE_SSA_REWRITE_BLOCKS); @@ -1855,8 +1857,9 @@ rewrite_ssa_into_ssa (bitmap names_to_rename) /* Finalize the dominator walker. */ fini_walk_dominator_tree (&walk_data); - EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, - release_ssa_name (ssa_name (i))); + unmark_all_for_rewrite (); + + EXECUTE_IF_SET_IN_BITMAP (to_rename, 0, i, release_ssa_name (ssa_name (i))); sbitmap_free (snames_to_rename); @@ -1886,6 +1889,7 @@ rewrite_ssa_into_ssa (bitmap names_to_rename) SSA_NAME_AUX (name) = NULL; } + BITMAP_XFREE (to_rename); timevar_pop (TV_TREE_SSA_OTHER); } diff --git a/gcc/tree-ssa-loop-ch.c b/gcc/tree-ssa-loop-ch.c index ddb2438bae7..f10ec75e1cc 100644 --- a/gcc/tree-ssa-loop-ch.c +++ b/gcc/tree-ssa-loop-ch.c @@ -99,54 +99,6 @@ should_duplicate_loop_header_p (basic_block header, struct loop *loop, return true; } -/* Marks variables defined in basic block BB for rewriting. */ - -static void -mark_defs_for_rewrite (basic_block bb) -{ - tree stmt, var; - block_stmt_iterator bsi; - stmt_ann_t ann; - def_optype defs; - v_may_def_optype v_may_defs; - v_must_def_optype v_must_defs; - unsigned i; - - for (stmt = phi_nodes (bb); stmt; stmt = TREE_CHAIN (stmt)) - { - var = PHI_RESULT (stmt); - bitmap_set_bit (vars_to_rename, SSA_NAME_VERSION (var)); - } - - for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) - { - stmt = bsi_stmt (bsi); - get_stmt_operands (stmt); - ann = stmt_ann (stmt); - - defs = DEF_OPS (ann); - for (i = 0; i < NUM_DEFS (defs); i++) - { - var = DEF_OP (defs, i); - bitmap_set_bit (vars_to_rename, SSA_NAME_VERSION (var)); - } - - v_may_defs = V_MAY_DEF_OPS (ann); - for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++) - { - var = V_MAY_DEF_RESULT (v_may_defs, i); - bitmap_set_bit (vars_to_rename, SSA_NAME_VERSION (var)); - } - - v_must_defs = V_MUST_DEF_OPS (ann); - for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++) - { - var = V_MUST_DEF_OP (v_must_defs, i); - bitmap_set_bit (vars_to_rename, SSA_NAME_VERSION (var)); - } - } -} - /* Duplicates destinations of edges in BBS_TO_DUPLICATE. */ static void @@ -161,18 +113,6 @@ duplicate_blocks (varray_type bbs_to_duplicate) up-to-date. */ free_dominance_info (CDI_DOMINATORS); - for (i = 0; i < VARRAY_ACTIVE_SIZE (bbs_to_duplicate); i++) - { - preheader_edge = VARRAY_GENERIC_PTR_NOGC (bbs_to_duplicate, i); - header = preheader_edge->dest; - - /* It is sufficient to rewrite the definitions, since the uses of - the operands defined outside of the duplicated basic block are - still valid (every basic block that dominates the original block - also dominates the duplicate). */ - mark_defs_for_rewrite (header); - } - for (i = 0; i < VARRAY_ACTIVE_SIZE (bbs_to_duplicate); i++) { preheader_edge = VARRAY_GENERIC_PTR_NOGC (bbs_to_duplicate, i); @@ -210,8 +150,7 @@ duplicate_blocks (varray_type bbs_to_duplicate) calculate_dominance_info (CDI_DOMINATORS); - rewrite_ssa_into_ssa (vars_to_rename); - bitmap_clear (vars_to_rename); + rewrite_ssa_into_ssa (); } /* Checks whether LOOP is a do-while style loop. */ diff --git a/gcc/tree-ssanames.c b/gcc/tree-ssanames.c index 4e8985a4b21..94c14538b16 100644 --- a/gcc/tree-ssanames.c +++ b/gcc/tree-ssanames.c @@ -60,7 +60,10 @@ 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; @@ -74,6 +77,64 @@ 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 @@ -182,6 +243,12 @@ 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 diff --git a/gcc/tree.h b/gcc/tree.h index 92e9a55d802..64fde745415 100644 --- a/gcc/tree.h +++ b/gcc/tree.h @@ -2658,6 +2658,13 @@ 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 *. */ -- 2.30.2