X-Git-Url: http://git.sourceforge.jp/view?p=pf3gnuchains%2Fgcc-fork.git;a=blobdiff_plain;f=gcc%2Ftree-ssa-live.c;h=132af929852e8ba4b33a55e85279f0f8214adc78;hp=38f4443de4d8852a855582876a5ca79ca875092c;hb=49299ed69a0bc20fe1e58148918ec55df9735702;hpb=365db11eea46f39f4e46a11a6509d212e41c2307 diff --git a/gcc/tree-ssa-live.c b/gcc/tree-ssa-live.c index 38f4443de4d..132af929852 100644 --- a/gcc/tree-ssa-live.c +++ b/gcc/tree-ssa-live.c @@ -1,5 +1,5 @@ /* Liveness for SSA trees. - Copyright (C) 2003 Free Software Foundation, Inc. + Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc. Contributed by Andrew MacLeod This file is part of GCC. @@ -16,8 +16,8 @@ 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. */ +the Free Software Foundation, 51 Franklin Street, Fifth Floor, +Boston, MA 02110-1301, USA. */ #include "config.h" #include "system.h" @@ -34,12 +34,12 @@ Boston, MA 02111-1307, USA. */ #include "tree-inline.h" #include "varray.h" #include "timevar.h" -#include "tree-alias-common.h" #include "hashtab.h" #include "tree-dump.h" #include "tree-ssa-live.h" +#include "toplev.h" -static void live_worklist (tree_live_info_p, varray_type, int); +static void live_worklist (tree_live_info_p, int *, int); static tree_live_info_p new_tree_live_info (var_map); static inline void set_if_valid (var_map, bitmap, tree); static inline void add_livein_if_notdef (tree_live_info_p, bitmap, @@ -102,7 +102,7 @@ delete_var_map (var_map map) /* This function will combine the partitions in MAP for VAR1 and VAR2. It Returns the partition which represents the new partition. If the two - partitions cannot be combined, NO_PARTITION is returned. */ + partitions cannot be combined, NO_PARTITION is returned. */ int var_union (var_map map, tree var1, tree var2) @@ -133,9 +133,9 @@ var_union (var_map map, tree var1, tree var2) if (map->compact_to_partition) p2 = map->compact_to_partition[p2]; - /* If there is no root_var set, or its not a user variable, set the + /* If there is no root_var set, or it's not a user variable, set the root_var to this one. */ - if (!root_var || is_gimple_tmp_var (root_var)) + if (!root_var || (DECL_P (root_var) && DECL_IGNORED_P (root_var))) { other_var = root_var; root_var = var2; @@ -144,8 +144,8 @@ var_union (var_map map, tree var1, tree var2) other_var = var2; } - if (p1 == NO_PARTITION || p2 == NO_PARTITION) - abort (); + gcc_assert (p1 != NO_PARTITION); + gcc_assert (p2 != NO_PARTITION); if (p1 == p2) p3 = p1; @@ -185,7 +185,8 @@ void compact_var_map (var_map map, int flags) { sbitmap used; - int x, limit, count, tmp, root, root_i; + int tmp, root, root_i; + unsigned int x, limit, count; tree var; root_var_p rv = NULL; @@ -238,10 +239,12 @@ compact_var_map (var_map map, int flags) /* Build a compacted partitioning. */ if (count != limit) { + sbitmap_iterator sbi; + map->compact_to_partition = (int *)xmalloc (count * sizeof (int)); count = 0; /* SSA renaming begins at 1, so skip 0 when compacting. */ - EXECUTE_IF_SET_IN_SBITMAP (used, 1, x, + EXECUTE_IF_SET_IN_SBITMAP (used, 1, x, sbi) { map->partition_to_compact[x] = count; map->compact_to_partition[count] = x; @@ -249,7 +252,7 @@ compact_var_map (var_map map, int flags) if (TREE_CODE (var) != SSA_NAME) change_partition_var (map, var, count); count++; - }); + } } else { @@ -274,8 +277,7 @@ change_partition_var (var_map map, tree var, int part) { var_ann_t ann; - if (TREE_CODE (var) == SSA_NAME) - abort(); + gcc_assert (TREE_CODE (var) != SSA_NAME); ann = var_ann (var); ann->out_of_ssa_tag = 1; @@ -284,6 +286,46 @@ change_partition_var (var_map map, tree var, int part) map->partition_to_var[map->compact_to_partition[part]] = var; } +static inline void mark_all_vars_used (tree *); + +/* Helper function for mark_all_vars_used, called via walk_tree. */ + +static tree +mark_all_vars_used_1 (tree *tp, int *walk_subtrees, + void *data ATTRIBUTE_UNUSED) +{ + tree t = *tp; + + /* Ignore TREE_ORIGINAL for TARGET_MEM_REFS, as well as other + fields that do not contain vars. */ + if (TREE_CODE (t) == TARGET_MEM_REF) + { + mark_all_vars_used (&TMR_SYMBOL (t)); + mark_all_vars_used (&TMR_BASE (t)); + mark_all_vars_used (&TMR_INDEX (t)); + *walk_subtrees = 0; + return NULL; + } + + /* Only need to mark VAR_DECLS; parameters and return results are not + eliminated as unused. */ + if (TREE_CODE (t) == VAR_DECL) + set_is_used (t); + + if (IS_TYPE_OR_DECL_P (t)) + *walk_subtrees = 0; + + return NULL; +} + +/* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be + eliminated during the tree->rtl conversion process. */ + +static inline void +mark_all_vars_used (tree *expr_p) +{ + walk_tree (expr_p, mark_all_vars_used_1, NULL, NULL); +} /* This function looks through the program and uses FLAGS to determine what SSA versioned variables are given entries in a new partition table. This @@ -294,41 +336,33 @@ create_ssa_var_map (int flags) { block_stmt_iterator bsi; basic_block bb; - tree *dest, *use; + tree dest, use; tree stmt; - stmt_ann_t ann; - vuse_optype vuses; - vdef_optype vdefs; - use_optype uses; - def_optype defs; - unsigned x; var_map map; -#if defined ENABLE_CHECKING - sbitmap used_in_real_ops; - sbitmap used_in_virtual_ops; + ssa_op_iter iter; +#ifdef ENABLE_CHECKING + bitmap used_in_real_ops; + bitmap used_in_virtual_ops; #endif - map = init_var_map (highest_ssa_version + 1); - -#if defined ENABLE_CHECKING - used_in_real_ops = sbitmap_alloc (num_referenced_vars); - sbitmap_zero (used_in_real_ops); + map = init_var_map (num_ssa_names + 1); - used_in_virtual_ops = sbitmap_alloc (num_referenced_vars); - sbitmap_zero (used_in_virtual_ops); +#ifdef ENABLE_CHECKING + used_in_real_ops = BITMAP_ALLOC (NULL); + used_in_virtual_ops = BITMAP_ALLOC (NULL); #endif if (flags & SSA_VAR_MAP_REF_COUNT) { map->ref_count - = (int *)xmalloc (((highest_ssa_version + 1) * sizeof (int))); - memset (map->ref_count, 0, (highest_ssa_version + 1) * sizeof (int)); + = (int *)xmalloc (((num_ssa_names + 1) * sizeof (int))); + memset (map->ref_count, 0, (num_ssa_names + 1) * sizeof (int)); } FOR_EACH_BB (bb) { tree phi, arg; - for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi)) + for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) { int i; register_ssa_partition (map, PHI_RESULT (phi), false); @@ -337,81 +371,67 @@ create_ssa_var_map (int flags) arg = PHI_ARG_DEF (phi, i); if (TREE_CODE (arg) == SSA_NAME) register_ssa_partition (map, arg, true); + + mark_all_vars_used (&PHI_ARG_DEF_TREE (phi, i)); } } for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) { stmt = bsi_stmt (bsi); - get_stmt_operands (stmt); - ann = stmt_ann (stmt); /* Register USE and DEF operands in each statement. */ - uses = USE_OPS (ann); - for (x = 0; x < NUM_USES (uses); x++) + FOR_EACH_SSA_TREE_OPERAND (use , stmt, iter, SSA_OP_USE) { - use = USE_OP_PTR (uses, x); - register_ssa_partition (map, *use, true); + register_ssa_partition (map, use, true); -#if defined ENABLE_CHECKING - SET_BIT (used_in_real_ops, var_ann (SSA_NAME_VAR (*use))->uid); +#ifdef ENABLE_CHECKING + bitmap_set_bit (used_in_real_ops, DECL_UID (SSA_NAME_VAR (use))); #endif } - defs = DEF_OPS (ann); - for (x = 0; x < NUM_DEFS (defs); x++) + FOR_EACH_SSA_TREE_OPERAND (dest, stmt, iter, SSA_OP_DEF) { - dest = DEF_OP_PTR (defs, x); - register_ssa_partition (map, *dest, false); + register_ssa_partition (map, dest, false); -#if defined ENABLE_CHECKING - SET_BIT (used_in_real_ops, var_ann (SSA_NAME_VAR (*dest))->uid); +#ifdef ENABLE_CHECKING + bitmap_set_bit (used_in_real_ops, DECL_UID (SSA_NAME_VAR (dest))); #endif } - /* While we do not care about virtual operands for - out of SSA, we do need to look at them to make sure - we mark all the variables which are used. */ - vuses = VUSE_OPS (ann); - for (x = 0; x < NUM_VUSES (vuses); x++) +#ifdef ENABLE_CHECKING + /* Validate that virtual ops don't get used in funny ways. */ + FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, + SSA_OP_VIRTUAL_USES | SSA_OP_VMUSTDEF) { - tree var = VUSE_OP (vuses, x); - set_is_used (var); - -#if defined ENABLE_CHECKING - SET_BIT (used_in_virtual_ops, var_ann (SSA_NAME_VAR (var))->uid); -#endif + bitmap_set_bit (used_in_virtual_ops, + DECL_UID (SSA_NAME_VAR (use))); } - vdefs = VDEF_OPS (ann); - for (x = 0; x < NUM_VDEFS (vdefs); x++) - { - tree var = VDEF_OP (vdefs, x); - set_is_used (var); +#endif /* ENABLE_CHECKING */ -#if defined ENABLE_CHECKING - SET_BIT (used_in_virtual_ops, var_ann (SSA_NAME_VAR (var))->uid); -#endif - } + mark_all_vars_used (bsi_stmt_ptr (bsi)); } } #if defined ENABLE_CHECKING { unsigned i; - sbitmap both = sbitmap_alloc (num_referenced_vars); - sbitmap_a_and_b (both, used_in_real_ops, used_in_virtual_ops); - if (sbitmap_first_set_bit (both) >= 0) + bitmap both = BITMAP_ALLOC (NULL); + bitmap_and (both, used_in_real_ops, used_in_virtual_ops); + if (!bitmap_empty_p (both)) { - EXECUTE_IF_SET_IN_SBITMAP (both, 0, i, + bitmap_iterator bi; + + EXECUTE_IF_SET_IN_BITMAP (both, 0, i, bi) fprintf (stderr, "Variable %s used in real and virtual operands\n", - get_name (referenced_var (i)))); - abort (); + get_name (referenced_var (i))); + internal_error ("SSA corruption"); } - sbitmap_free (used_in_real_ops); - sbitmap_free (used_in_virtual_ops); - sbitmap_free (both); + BITMAP_FREE (used_in_real_ops); + BITMAP_FREE (used_in_virtual_ops); + BITMAP_FREE (both); } #endif @@ -425,17 +445,17 @@ static tree_live_info_p new_tree_live_info (var_map map) { tree_live_info_p live; - int x; + unsigned x; live = (tree_live_info_p) xmalloc (sizeof (struct tree_live_info_d)); live->map = map; live->num_blocks = last_basic_block; - live->global = BITMAP_XMALLOC (); + live->global = BITMAP_ALLOC (NULL); live->livein = (bitmap *)xmalloc (num_var_partitions (map) * sizeof (bitmap)); for (x = 0; x < num_var_partitions (map); x++) - live->livein[x] = BITMAP_XMALLOC (); + live->livein[x] = BITMAP_ALLOC (NULL); /* liveout is deferred until it is actually requested. */ live->liveout = NULL; @@ -452,17 +472,17 @@ delete_tree_live_info (tree_live_info_p live) if (live->liveout) { for (x = live->num_blocks - 1; x >= 0; x--) - BITMAP_XFREE (live->liveout[x]); + BITMAP_FREE (live->liveout[x]); free (live->liveout); } if (live->livein) { for (x = num_var_partitions (live->map) - 1; x >= 0; x--) - BITMAP_XFREE (live->livein[x]); + BITMAP_FREE (live->livein[x]); free (live->livein); } if (live->global) - BITMAP_XFREE (live->global); + BITMAP_FREE (live->global); free (live); } @@ -473,38 +493,40 @@ delete_tree_live_info (tree_live_info_p live) passed in rather than being allocated on every call. */ static void -live_worklist (tree_live_info_p live, varray_type stack, int i) +live_worklist (tree_live_info_p live, int *stack, int i) { - int b; + unsigned b; tree var; basic_block def_bb = NULL; edge e; var_map map = live->map; + edge_iterator ei; + bitmap_iterator bi; + int *tos = stack; var = partition_to_var (map, i); if (SSA_NAME_DEF_STMT (var)) def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var)); - EXECUTE_IF_SET_IN_BITMAP (live->livein[i], 0, b, + EXECUTE_IF_SET_IN_BITMAP (live->livein[i], 0, b, bi) { - VARRAY_PUSH_INT (stack, b); - }); + *tos++ = b; + } - while (VARRAY_ACTIVE_SIZE (stack) > 0) + while (tos != stack) { - b = VARRAY_TOP_INT (stack); - VARRAY_POP (stack); + b = *--tos; - for (e = BASIC_BLOCK (b)->pred; e; e = e->pred_next) - if (e->src != ENTRY_BLOCK_PTR) + FOR_EACH_EDGE (e, ei, BASIC_BLOCK (b)->preds) + if (e->src != ENTRY_BLOCK_PTR) { /* Its not live on entry to the block its defined in. */ if (e->src == def_bb) continue; if (!bitmap_bit_p (live->livein[i], e->src->index)) { - bitmap_set_bit (live->livein[i], e->src->index); - VARRAY_PUSH_INT (stack, e->src->index); + bitmap_set_bit (live->livein[i], e->src->index); + *tos++ = e->src->index; } } } @@ -547,19 +569,22 @@ tree_live_info_p calculate_live_on_entry (var_map map) { tree_live_info_p live; - int num, i; + unsigned i; basic_block bb; bitmap saw_def; tree phi, var, stmt; tree op; edge e; - varray_type stack; + int *stack; block_stmt_iterator bsi; - use_optype uses; - def_optype defs; - stmt_ann_t ann; + ssa_op_iter iter; + bitmap_iterator bi; +#ifdef ENABLE_CHECKING + int num; + edge_iterator ei; +#endif - saw_def = BITMAP_XMALLOC (); + saw_def = BITMAP_ALLOC (NULL); live = new_tree_live_info (map); @@ -567,15 +592,15 @@ calculate_live_on_entry (var_map map) { bitmap_clear (saw_def); - for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi)) + for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) { - for (i = 0; i < PHI_NUM_ARGS (phi); i++) + for (i = 0; i < (unsigned)PHI_NUM_ARGS (phi); i++) { var = PHI_ARG_DEF (phi, i); if (!phi_ssa_name_p (var)) continue; stmt = SSA_NAME_DEF_STMT (var); - e = PHI_ARG_EDGE (phi, i); + e = EDGE_PRED (bb, i); /* Any uses in PHIs which either don't have def's or are not defined in the block from which the def comes, will be live @@ -592,7 +617,7 @@ calculate_live_on_entry (var_map map) The a_3 referred to in b_3's PHI node is the one incoming on the edge, *not* the PHI node just seen. */ - for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi)) + for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) { var = PHI_RESULT (phi); set_if_valid (map, saw_def, var); @@ -601,32 +626,25 @@ calculate_live_on_entry (var_map map) 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); - num = NUM_USES (uses); - for (i = 0; i < num; i++) + FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE) { - op = USE_OP (uses, i); add_livein_if_notdef (live, saw_def, op, bb); } - defs = DEF_OPS (ann); - num = NUM_DEFS (defs); - for (i = 0; i < num; i++) + FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF) { - op = DEF_OP (defs, i); set_if_valid (map, saw_def, op); } } } - VARRAY_INT_INIT (stack, last_basic_block, "stack"); - EXECUTE_IF_SET_IN_BITMAP (live->global, 0, i, + stack = xmalloc (sizeof (int) * last_basic_block); + EXECUTE_IF_SET_IN_BITMAP (live->global, 0, i, bi) { live_worklist (live, stack, i); - }); + } + free (stack); #ifdef ENABLE_CHECKING /* Check for live on entry partitions and report those with a DEF in @@ -635,12 +653,12 @@ calculate_live_on_entry (var_map map) bb = ENTRY_BLOCK_PTR; num = 0; - for (e = bb->succ; e; e = e->succ_next) + FOR_EACH_EDGE (e, ei, bb->succs) { int entry_block = e->dest->index; if (e->dest == EXIT_BLOCK_PTR) continue; - for (i = 0; i < num_var_partitions (map); i++) + for (i = 0; i < (unsigned)num_var_partitions (map); i++) { basic_block tmp; tree d; @@ -690,7 +708,7 @@ calculate_live_on_entry (var_map map) int z, ok = 0; for (phi = phi_nodes (e->dest); phi && !ok; - phi = TREE_CHAIN (phi)) + phi = PHI_CHAIN (phi)) { for (z = 0; z < PHI_NUM_ARGS (phi); z++) if (var == PHI_ARG_DEF (phi, z)) @@ -709,11 +727,10 @@ calculate_live_on_entry (var_map map) } } } - if (num > 0) - abort (); + gcc_assert (num <= 0); #endif - BITMAP_XFREE (saw_def); + BITMAP_FREE (saw_def); return live; } @@ -725,7 +742,7 @@ void calculate_live_on_exit (tree_live_info_p liveinfo) { unsigned b; - int i, x; + unsigned i, x; bitmap *on_exit; basic_block bb; edge e; @@ -734,14 +751,14 @@ calculate_live_on_exit (tree_live_info_p liveinfo) var_map map = liveinfo->map; on_exit = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap)); - for (x = 0; x < last_basic_block; x++) - on_exit[x] = BITMAP_XMALLOC (); + for (x = 0; x < (unsigned)last_basic_block; x++) + on_exit[x] = BITMAP_ALLOC (NULL); /* Set all the live-on-exit bits for uses in PHIs. */ FOR_EACH_BB (bb) { - for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi)) - for (i = 0; i < PHI_NUM_ARGS (phi); i++) + for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) + for (i = 0; i < (unsigned)PHI_NUM_ARGS (phi); i++) { t = PHI_ARG_DEF (phi, i); e = PHI_ARG_EDGE (phi, i); @@ -754,13 +771,16 @@ calculate_live_on_exit (tree_live_info_p liveinfo) /* Set live on exit for all predecessors of live on entry's. */ for (i = 0; i < num_var_partitions (map); i++) { + bitmap_iterator bi; + on_entry = live_entry_blocks (liveinfo, i); - EXECUTE_IF_SET_IN_BITMAP (on_entry, 0, b, + EXECUTE_IF_SET_IN_BITMAP (on_entry, 0, b, bi) { - for (e = BASIC_BLOCK(b)->pred; e; e = e->pred_next) + edge_iterator ei; + FOR_EACH_EDGE (e, ei, BASIC_BLOCK (b)->preds) if (e->src != ENTRY_BLOCK_PTR) bitmap_set_bit (on_exit[e->src->index], i); - }); + } } liveinfo->liveout = on_exit; @@ -769,7 +789,7 @@ calculate_live_on_exit (tree_live_info_p liveinfo) /* Initialize a tree_partition_associator object using MAP. */ -tpa_p +static tpa_p tpa_init (var_map map) { tpa_p tpa; @@ -790,7 +810,7 @@ tpa_init (var_map map) memset (tpa->partition_to_tree_map, TPA_NONE, num_partitions * sizeof (int)); x = MAX (40, (num_partitions / 20)); - VARRAY_TREE_INIT (tpa->trees, x, "trees"); + tpa->trees = VEC_alloc (tree, heap, x); VARRAY_INT_INIT (tpa->first_partition, x, "first_partition"); return tpa; @@ -832,6 +852,7 @@ tpa_delete (tpa_p tpa) if (!tpa) return; + VEC_free (tree, heap, tpa->trees); free (tpa->partition_to_tree_map); free (tpa->next_partition); free (tpa); @@ -865,19 +886,20 @@ tpa_compact (tpa_p tpa) of the tree list. */ if (tpa_next_partition (tpa, first) == NO_PARTITION) { - swap_t = VARRAY_TREE (tpa->trees, last); + swap_t = VEC_index (tree, tpa->trees, last); swap_i = VARRAY_INT (tpa->first_partition, last); /* Update the last entry. Since it is known to only have one partition, there is nothing else to update. */ - VARRAY_TREE (tpa->trees, last) = VARRAY_TREE (tpa->trees, x); + VEC_replace (tree, tpa->trees, last, + VEC_index (tree, tpa->trees, x)); VARRAY_INT (tpa->first_partition, last) = VARRAY_INT (tpa->first_partition, x); tpa->partition_to_tree_map[tpa_first_partition (tpa, last)] = last; /* Since this list is known to have more than one partition, update the list owner entries. */ - VARRAY_TREE (tpa->trees, x) = swap_t; + VEC_replace (tree, tpa->trees, x, swap_t); VARRAY_INT (tpa->first_partition, x) = swap_i; for (y = tpa_first_partition (tpa, x); y != NO_PARTITION; @@ -937,10 +959,7 @@ root_var_init (var_map map) p = var_to_partition (map, t); -#ifdef ENABLE_CHECKING - if (p == NO_PARTITION) - abort (); -#endif + gcc_assert (p != NO_PARTITION); /* Make sure we only put coalesced partitions into the list once. */ if (TEST_BIT (seen, p)) @@ -959,7 +978,7 @@ root_var_init (var_map map) { ann->root_var_processed = 1; VAR_ANN_ROOT_INDEX (ann) = rv->num_trees++; - VARRAY_PUSH_TREE (rv->trees, t); + VEC_safe_push (tree, heap, rv->trees, t); VARRAY_PUSH_INT (rv->first_partition, p); } rv->partition_to_tree_map[p] = VAR_ANN_ROOT_INDEX (ann); @@ -968,7 +987,7 @@ root_var_init (var_map map) /* Reset the out_of_ssa_tag flag on each variable for later use. */ for (x = 0; x < rv->num_trees; x++) { - t = VARRAY_TREE (rv->trees, x); + t = VEC_index (tree, rv->trees, x); var_ann (t)->root_var_processed = 0; } @@ -1007,16 +1026,13 @@ type_var_init (var_map map) || TREE_CODE (t) == PARM_DECL || (DECL_P (t) && (DECL_REGISTER (t) - || !DECL_ARTIFICIAL (t) + || !DECL_IGNORED_P (t) || DECL_RTL_SET_P (t)))) continue; p = var_to_partition (map, t); -#ifdef ENABLE_CHECKING - if (p == NO_PARTITION) - abort (); -#endif + gcc_assert (p != NO_PARTITION); /* If partitions have been coalesced, only add the representative for the partition to the list once. */ @@ -1027,12 +1043,12 @@ type_var_init (var_map map) /* Find the list for this type. */ for (y = 0; y < tv->num_trees; y++) - if (t == VARRAY_TREE (tv->trees, y)) + if (t == VEC_index (tree, tv->trees, y)) break; if (y == tv->num_trees) { tv->num_trees++; - VARRAY_PUSH_TREE (tv->trees, t); + VEC_safe_push (tree, heap, tv->trees, t); VARRAY_PUSH_INT (tv->first_partition, p); } else @@ -1129,18 +1145,34 @@ find_partition_pair (coalesce_list_p cl, int p1, int p2, bool create) return node; } +/* Return cost of execution of copy instruction with FREQUENCY + possibly on CRITICAL edge and in HOT basic block. */ +int +coalesce_cost (int frequency, bool hot, bool critical) +{ + /* Base costs on BB frequencies bounded by 1. */ + int cost = frequency; + + if (!cost) + cost = 1; + if (optimize_size || hot) + cost = 1; + /* Inserting copy on critical edge costs more + than inserting it elsewhere. */ + if (critical) + cost *= 2; + return cost; +} /* Add a potential coalesce between P1 and P2 in CL with a cost of VALUE. */ void -add_coalesce (coalesce_list_p cl, int p1, int p2, int value) +add_coalesce (coalesce_list_p cl, int p1, int p2, + int value) { partition_pair_p node; -#ifdef ENABLE_CHECKING - if (!cl->add_mode) - abort(); -#endif + gcc_assert (cl->add_mode); if (p1 == p2) return; @@ -1167,12 +1199,11 @@ int compare_pairs (const void *p1, const void *p2) void sort_coalesce_list (coalesce_list_p cl) { - int x, num, count; + unsigned x, num, count; partition_pair_p chain, p; partition_pair_p *list; - if (!cl->add_mode) - abort(); + gcc_assert (cl->add_mode); cl->add_mode = false; @@ -1198,10 +1229,7 @@ sort_coalesce_list (coalesce_list_p cl) for (p = chain; p != NULL; p = p->next) list[count++] = p; -#ifdef ENABLE_CHECKING - if (count != num) - abort (); -#endif + gcc_assert (count == num); qsort (list, count, sizeof (partition_pair_p), compare_pairs); @@ -1236,14 +1264,13 @@ sort_coalesce_list (coalesce_list_p cl) partitions via P1 and P2. Their calculated cost is returned by the function. NO_BEST_COALESCE is returned if the coalesce list is empty. */ -int +static int pop_best_coalesce (coalesce_list_p cl, int *p1, int *p2) { partition_pair_p node; int ret; - if (cl->add_mode) - abort(); + gcc_assert (!cl->add_mode); node = cl->list[0]; if (!node) @@ -1288,6 +1315,8 @@ add_conflicts_if_valid (tpa_p tpa, conflict_graph graph, } } +DEF_VEC_I(int); +DEF_VEC_ALLOC_I(int,heap); /* Return a conflict graph for the information contained in LIVE_INFO. Only conflicts between items in the same TPA list are added. If optional @@ -1300,12 +1329,13 @@ build_tree_conflict_graph (tree_live_info_p liveinfo, tpa_p tpa, conflict_graph graph; var_map map; bitmap live; - int num, x, y, i; + unsigned x, y, i; basic_block bb; - varray_type partition_link, tpa_to_clear, tpa_nodes; - def_optype defs; - use_optype uses; + int *partition_link, *tpa_nodes; + VEC(int,heap) *tpa_to_clear; unsigned l; + ssa_op_iter iter; + bitmap_iterator bi; map = live_var_map (liveinfo); graph = conflict_graph_new (num_var_partitions (map)); @@ -1313,16 +1343,17 @@ build_tree_conflict_graph (tree_live_info_p liveinfo, tpa_p tpa, if (tpa_num_trees (tpa) == 0) return graph; - live = BITMAP_XMALLOC (); + live = BITMAP_ALLOC (NULL); - VARRAY_INT_INIT (partition_link, num_var_partitions (map) + 1, "part_link"); - VARRAY_INT_INIT (tpa_nodes, tpa_num_trees (tpa), "tpa nodes"); - VARRAY_INT_INIT (tpa_to_clear, 50, "tpa to clear"); + partition_link = xcalloc (num_var_partitions (map) + 1, sizeof (int)); + tpa_nodes = xcalloc (tpa_num_trees (tpa), sizeof (int)); + tpa_to_clear = VEC_alloc (int, heap, 50); FOR_EACH_BB (bb) { block_stmt_iterator bsi; tree phi; + int idx; /* Start with live on exit temporaries. */ bitmap_copy (live, live_on_exit (liveinfo, bb)); @@ -1331,10 +1362,6 @@ build_tree_conflict_graph (tree_live_info_p liveinfo, tpa_p tpa, { bool is_a_copy = false; tree stmt = bsi_stmt (bsi); - stmt_ann_t ann; - - get_stmt_operands (stmt); - ann = stmt_ann (stmt); /* A copy between 2 partitions does not introduce an interference by itself. If they did, you would never be able to coalesce @@ -1344,7 +1371,7 @@ build_tree_conflict_graph (tree_live_info_p liveinfo, tpa_p tpa, This is handled specially here since we may also be interested in copies between real variables and SSA_NAME variables. We may be interested in trying to coalesce SSA_NAME variables with - root variables in some cases. */ + root variables in some cases. */ if (TREE_CODE (stmt) == MODIFY_EXPR) { @@ -1375,29 +1402,24 @@ build_tree_conflict_graph (tree_live_info_p liveinfo, tpa_p tpa, if (bit) bitmap_set_bit (live, p2); if (cl) - add_coalesce (cl, p1, p2, 1); + add_coalesce (cl, p1, p2, + coalesce_cost (bb->frequency, + maybe_hot_bb_p (bb), false)); set_if_valid (map, live, rhs); } } if (!is_a_copy) { - tree *var_p; - - defs = DEF_OPS (ann); - num = NUM_DEFS (defs); - for (x = 0; x < num; x++) + tree var; + FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF) { - var_p = DEF_OP_PTR (defs, x); - add_conflicts_if_valid (tpa, graph, map, live, *var_p); + add_conflicts_if_valid (tpa, graph, map, live, var); } - uses = USE_OPS (ann); - num = NUM_USES (uses); - for (x = 0; x < num; x++) + FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE) { - var_p = USE_OP_PTR (uses, x); - set_if_valid (map, live, *var_p); + set_if_valid (map, live, var); } } } @@ -1407,7 +1429,7 @@ build_tree_conflict_graph (tree_live_info_p liveinfo, tpa_p tpa, going to be translated out of SSA form we must record a conflict between the result of the PHI and any variables with are live. Otherwise the out-of-ssa translation may create incorrect code. */ - for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi)) + for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) { tree result = PHI_RESULT (phi); int p = var_to_partition (map, result); @@ -1429,32 +1451,35 @@ build_tree_conflict_graph (tree_live_info_p liveinfo, tpa_p tpa, tpa_clear contains all the tpa_roots processed, and these are the only entries which need to be zero'd out for a clean restart. */ - EXECUTE_IF_SET_IN_BITMAP (live, 0, x, + EXECUTE_IF_SET_IN_BITMAP (live, 0, x, bi) { i = tpa_find_tree (tpa, x); - if (i != TPA_NONE) + if (i != (unsigned)TPA_NONE) { - int start = VARRAY_INT (tpa_nodes, i); + int start = tpa_nodes[i]; /* If start is 0, a new root reference list is being started. Register it to be cleared. */ if (!start) - VARRAY_PUSH_INT (tpa_to_clear, i); + VEC_safe_push (int, heap, tpa_to_clear, i); /* Add interferences to other tpa members seen. */ - for (y = start; y != 0; y = VARRAY_INT (partition_link, y)) + for (y = start; y != 0; y = partition_link[y]) conflict_graph_add (graph, x, y - 1); - VARRAY_INT (tpa_nodes, i) = x + 1; - VARRAY_INT (partition_link, x + 1) = start; + tpa_nodes[i] = x + 1; + partition_link[x + 1] = start; } - }); + } /* Now clear the used tpa root references. */ - for (l = 0; l < VARRAY_ACTIVE_SIZE (tpa_to_clear); l++) - VARRAY_INT (tpa_nodes, VARRAY_INT (tpa_to_clear, l)) = 0; - VARRAY_POP_ALL (tpa_to_clear); + for (l = 0; VEC_iterate (int, tpa_to_clear, l, idx); l++) + tpa_nodes[idx] = 0; + VEC_truncate (int, tpa_to_clear, 0); } - BITMAP_XFREE (live); + free (tpa_nodes); + free (partition_link); + VEC_free (int, heap, tpa_to_clear); + BITMAP_FREE (live); return graph; } @@ -1732,7 +1757,7 @@ dump_var_map (FILE *f, var_map map) continue; t = 0; - for (y = 1; y < highest_ssa_version; y++) + for (y = 1; y < num_ssa_names; y++) { p = partition_find (map->var_partition, y); if (map->partition_to_compact) @@ -1761,8 +1786,9 @@ void dump_live_info (FILE *f, tree_live_info_p live, int flag) { basic_block bb; - int i; + unsigned i; var_map map = live->map; + bitmap_iterator bi; if ((flag & LIVEDUMP_ENTRY) && live->livein) { @@ -1786,104 +1812,27 @@ dump_live_info (FILE *f, tree_live_info_p live, int flag) FOR_EACH_BB (bb) { fprintf (f, "\nLive on exit from BB%d : ", bb->index); - EXECUTE_IF_SET_IN_BITMAP (live->liveout[bb->index], 0, i, + EXECUTE_IF_SET_IN_BITMAP (live->liveout[bb->index], 0, i, bi) { print_generic_expr (f, partition_to_var (map, i), TDF_SLIM); fprintf (f, " "); - }); + } fprintf (f, "\n"); } } } -/* Register partitions in MAP so that we can take VARS out of SSA form. - This requires a walk over all the PHI nodes and all the statements. */ - +#ifdef ENABLE_CHECKING void -register_ssa_partitions_for_vars (bitmap vars, var_map map) +register_ssa_partition_check (tree ssa_var) { - basic_block bb; - - if (bitmap_first_set_bit (vars) >= 0) + gcc_assert (TREE_CODE (ssa_var) == SSA_NAME); + if (!is_gimple_reg (SSA_NAME_VAR (ssa_var))) { - - /* Find every instance (SSA_NAME) of variables in VARs and - register a new partition for them. This requires examining - every statement and every PHI node once. */ - FOR_EACH_BB (bb) - { - block_stmt_iterator bsi; - tree next; - tree phi; - - /* Register partitions for SSA_NAMEs appearing in the PHI - nodes in this basic block. - - Note we delete PHI nodes in this loop if they are - associated with virtual vars which are going to be - renamed. */ - for (phi = phi_nodes (bb); phi; phi = next) - { - tree result = SSA_NAME_VAR (PHI_RESULT (phi)); - - next = TREE_CHAIN (phi); - if (bitmap_bit_p (vars, var_ann (result)->uid)) - { - if (! is_gimple_reg (result)) - remove_phi_node (phi, NULL_TREE, bb); - else - { - int i; - - /* Register a partition for the result. */ - register_ssa_partition (map, PHI_RESULT (phi), 0); - - /* Register a partition for each argument as needed. */ - for (i = 0; i < PHI_NUM_ARGS (phi); i++) - { - tree arg = PHI_ARG_DEF (phi, i); - - if (TREE_CODE (arg) != SSA_NAME) - continue; - if (!bitmap_bit_p (vars, - var_ann (SSA_NAME_VAR (arg))->uid)) - continue; - - register_ssa_partition (map, arg, 1); - } - } - } - } - - /* Now register partitions for SSA_NAMEs appearing in each - statement in this block. */ - for (bsi = bsi_start (bb); ! bsi_end_p (bsi); bsi_next (&bsi)) - { - stmt_ann_t ann = stmt_ann (bsi_stmt (bsi)); - use_optype uses = USE_OPS (ann); - def_optype defs = DEF_OPS (ann); - unsigned int i; - - for (i = 0; i < NUM_USES (uses); i++) - { - tree op = USE_OP (uses, i); - - if (TREE_CODE (op) == SSA_NAME - && bitmap_bit_p (vars, var_ann (SSA_NAME_VAR (op))->uid)) - register_ssa_partition (map, op, 1); - } - - for (i = 0; i < NUM_DEFS (defs); i++) - { - tree op = DEF_OP (defs, i); - - if (TREE_CODE (op) == SSA_NAME - && bitmap_bit_p (vars, - var_ann (SSA_NAME_VAR (op))->uid)) - register_ssa_partition (map, op, 0); - } - } - } + fprintf (stderr, "Illegally registering a virtual SSA name :"); + print_generic_expr (stderr, ssa_var, TDF_SLIM); + fprintf (stderr, " in the SSA->Normal phase.\n"); + internal_error ("SSA corruption"); } } - +#endif