X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Ftree-ssa-live.c;h=ae4b909a5e3089abf01649b47954c7397c3d7c0e;hb=3bcc6ec599c91d88c4a01efe30a475ebd2e5ab1d;hp=3a166a7c21caf2ed437a4f625e5fc66fa121eb48;hpb=7e0c7e2e8e2c055a2751d8dbd5cdd4bd70fe316e;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/tree-ssa-live.c b/gcc/tree-ssa-live.c index 3a166a7c21c..ae4b909a5e3 100644 --- a/gcc/tree-ssa-live.c +++ b/gcc/tree-ssa-live.c @@ -1,12 +1,12 @@ /* Liveness for SSA trees. - Copyright (C) 2003 Free Software Foundation, Inc. + Copyright (C) 2003, 2004, 2005, 2007 Free Software Foundation, Inc. Contributed by Andrew MacLeod 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) +the Free Software Foundation; either version 3, or (at your option) any later version. GCC is distributed in the hope that it will be useful, @@ -15,52 +15,117 @@ 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. */ +along with GCC; see the file COPYING3. If not see +. */ #include "config.h" #include "system.h" #include "coretypes.h" #include "tm.h" #include "tree.h" -#include "flags.h" -#include "basic-block.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-alias-common.h" -#include "hashtab.h" #include "tree-dump.h" #include "tree-ssa-live.h" +#include "toplev.h" +#include "debug.h" +#include "flags.h" + +#ifdef ENABLE_CHECKING +static void verify_live_on_entry (tree_live_info_p); +#endif + + +/* VARMAP maintains a mapping from SSA version number to real variables. + + All SSA_NAMES are divided into partitions. Initially each ssa_name is the + only member of it's own partition. Coalescing will attempt to group any + ssa_names which occur in a copy or in a PHI node into the same partition. + + At the end of out-of-ssa, each partition becomes a "real" variable and is + rewritten as a compiler variable. + + The var_map datat structure is used to manage these partitions. It allows + partitions to be combined, and determines which partition belongs to what + ssa_name or variable, and vice versa. */ + + +/* This routine will initialize the basevar fields of MAP. */ + +static void +var_map_base_init (var_map map) +{ + int x, num_part, num; + tree var; + var_ann_t ann; + + num = 0; + num_part = num_var_partitions (map); + + /* If a base table already exists, clear it, otherwise create it. */ + if (map->partition_to_base_index != NULL) + { + free (map->partition_to_base_index); + VEC_truncate (tree, map->basevars, 0); + } + else + map->basevars = VEC_alloc (tree, heap, MAX (40, (num_part / 10))); + + map->partition_to_base_index = (int *) xmalloc (sizeof (int) * num_part); -static void live_worklist (tree_live_info_p, varray_type, 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, - tree, basic_block); -static inline void register_ssa_partition (var_map, tree, bool); -static inline void add_conflicts_if_valid (tpa_p, conflict_graph, - var_map, bitmap, tree); -static partition_pair_p find_partition_pair (coalesce_list_p, int, int, bool); + /* Build the base variable list, and point partitions at their bases. */ + for (x = 0; x < num_part; x++) + { + var = partition_to_var (map, x); + if (TREE_CODE (var) == SSA_NAME) + var = SSA_NAME_VAR (var); + ann = var_ann (var); + /* If base variable hasn't been seen, set it up. */ + if (!ann->base_var_processed) + { + ann->base_var_processed = 1; + VAR_ANN_BASE_INDEX (ann) = num++; + VEC_safe_push (tree, heap, map->basevars, var); + } + map->partition_to_base_index[x] = VAR_ANN_BASE_INDEX (ann); + } + + map->num_basevars = num; + + /* Now clear the processed bit. */ + for (x = 0; x < num; x++) + { + var = VEC_index (tree, map->basevars, x); + var_ann (var)->base_var_processed = 0; + } -/* This is where the mapping from SSA version number to real storage variable - is tracked. +#ifdef ENABLE_CHECKING + for (x = 0; x < num_part; x++) + { + tree var2; + var = SSA_NAME_VAR (partition_to_var (map, x)); + var2 = VEC_index (tree, map->basevars, basevar_index (map, x)); + gcc_assert (var == var2); + } +#endif +} - All SSA versions of the same variable may not ultimately be mapped back to - the same real variable. In that instance, we need to detect the live - range overlap, and give one of the variable new storage. The vector - 'partition_to_var' tracks which partition maps to which variable. - Given a VAR, it is sometimes desirable to know which partition that VAR - represents. There is an additional field in the variable annotation to - track that information. */ +/* Remove the base table in MAP. */ +static void +var_map_base_fini (var_map map) +{ + /* Free the basevar info if it is present. */ + if (map->partition_to_base_index != NULL) + { + VEC_free (tree, heap, map->basevars); + free (map->partition_to_base_index); + map->partition_to_base_index = NULL; + map->num_basevars = 0; + } +} /* Create a variable partition map of SIZE, initialize and return it. */ var_map @@ -74,11 +139,13 @@ init_var_map (int size) = (tree *)xmalloc (size * sizeof (tree)); memset (map->partition_to_var, 0, size * sizeof (tree)); - map->partition_to_compact = NULL; - map->compact_to_partition = NULL; + map->partition_to_view = NULL; + map->view_to_partition = NULL; map->num_partitions = size; map->partition_size = size; - map->ref_count = NULL; + map->num_basevars = 0; + map->partition_to_base_index = NULL; + map->basevars = NULL; return map; } @@ -88,21 +155,20 @@ init_var_map (int size) void delete_var_map (var_map map) { + var_map_base_fini (map); free (map->partition_to_var); partition_delete (map->var_partition); - if (map->partition_to_compact) - free (map->partition_to_compact); - if (map->compact_to_partition) - free (map->compact_to_partition); - if (map->ref_count) - free (map->ref_count); + if (map->partition_to_view) + free (map->partition_to_view); + if (map->view_to_partition) + free (map->view_to_partition); free (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) @@ -111,17 +177,17 @@ var_union (var_map map, tree var1, tree var2) tree root_var = NULL_TREE; tree other_var = NULL_TREE; - /* This is independent of partition_to_compact. If partition_to_compact is + /* This is independent of partition_to_view. If partition_to_view is on, then whichever one of these partitions is absorbed will never have a - dereference into the partition_to_compact array any more. */ + dereference into the partition_to_view array any more. */ if (TREE_CODE (var1) == SSA_NAME) p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1)); else { p1 = var_to_partition (map, var1); - if (map->compact_to_partition) - p1 = map->compact_to_partition[p1]; + if (map->view_to_partition) + p1 = map->view_to_partition[p1]; root_var = var1; } @@ -130,12 +196,12 @@ var_union (var_map map, tree var1, tree var2) else { p2 = var_to_partition (map, var2); - if (map->compact_to_partition) - p2 = map->compact_to_partition[p2]; + if (map->view_to_partition) + p2 = map->view_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,16 +210,16 @@ 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; else p3 = partition_union (map->var_partition, p1, p2); - if (map->partition_to_compact) - p3 = map->partition_to_compact[p3]; + if (map->partition_to_view) + p3 = map->partition_to_view[p3]; if (root_var) change_partition_var (map, root_var, p3); @@ -163,12 +229,12 @@ var_union (var_map map, tree var1, tree var2) return p3; } - + /* Compress the partition numbers in MAP such that they fall in the range 0..(num_partitions-1) instead of wherever they turned out during the partitioning exercise. This removes any references to unused partitions, thereby allowing bitmaps and other vectors to be much - denser. Compression type is controlled by FLAGS. + denser. This is implemented such that compaction doesn't affect partitioning. Ie., once partitions are created and possibly merged, running one @@ -181,241 +247,442 @@ var_union (var_map map, tree var1, tree var2) definitions, and then 'recompact' later to include all the single definitions for assignment to program variables. */ -void -compact_var_map (var_map map, int flags) + +/* Set MAP back to the initial state of having no partition view. Return a + bitmap which has a bit set for each partition number which is in use in the + varmap. */ + +static bitmap +partition_view_init (var_map map) { - sbitmap used; - int x, limit, count, tmp, root, root_i; - tree var; - root_var_p rv = NULL; + bitmap used; + int tmp; + unsigned int x; - limit = map->partition_size; - used = sbitmap_alloc (limit); - sbitmap_zero (used); + used = BITMAP_ALLOC (NULL); - /* Already compressed? Abandon the old one. */ - if (map->partition_to_compact) + /* Already in a view? Abandon the old one. */ + if (map->partition_to_view) { - free (map->partition_to_compact); - map->partition_to_compact = NULL; + free (map->partition_to_view); + map->partition_to_view = NULL; } - if (map->compact_to_partition) + if (map->view_to_partition) { - free (map->compact_to_partition); - map->compact_to_partition = NULL; + free (map->view_to_partition); + map->view_to_partition = NULL; } - map->num_partitions = map->partition_size; - - if (flags & VARMAP_NO_SINGLE_DEFS) - rv = root_var_init (map); - - map->partition_to_compact = (int *)xmalloc (limit * sizeof (int)); - memset (map->partition_to_compact, 0xff, (limit * sizeof (int))); - /* Find out which partitions are actually referenced. */ - count = 0; - for (x = 0; x < limit; x++) + for (x = 0; x < map->partition_size; x++) { tmp = partition_find (map->var_partition, x); - if (!TEST_BIT (used, tmp) && map->partition_to_var[tmp] != NULL_TREE) - { - /* It is referenced, check to see if there is more than one version - in the root_var table, if one is available. */ - if (rv) - { - root = root_var_find (rv, tmp); - root_i = root_var_first_partition (rv, root); - /* If there is only one, don't include this in the compaction. */ - if (root_var_next_partition (rv, root_i) == ROOT_VAR_NONE) - continue; - } - SET_BIT (used, tmp); - count++; - } + if (map->partition_to_var[tmp] != NULL_TREE && !bitmap_bit_p (used, tmp)) + bitmap_set_bit (used, tmp); } - /* Build a compacted partitioning. */ - if (count != limit) + map->num_partitions = map->partition_size; + return used; +} + + +/* This routine will finalize the view data for MAP based on the partitions + set in SELECTED. This is either the same bitmap returned from + partition_view_init, or a trimmed down version if some of those partitions + were not desired in this view. SELECTED is freed before returning. */ + +static void +partition_view_fini (var_map map, bitmap selected) +{ + bitmap_iterator bi; + unsigned count, i, x, limit; + tree var; + + gcc_assert (selected); + + count = bitmap_count_bits (selected); + limit = map->partition_size; + + /* If its a one-to-one ratio, we don't need any view compaction. */ + if (count < limit) { - 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, + map->partition_to_view = (int *)xmalloc (limit * sizeof (int)); + memset (map->partition_to_view, 0xff, (limit * sizeof (int))); + map->view_to_partition = (int *)xmalloc (count * sizeof (int)); + + i = 0; + /* Give each selected partition an index. */ + EXECUTE_IF_SET_IN_BITMAP (selected, 0, x, bi) { - map->partition_to_compact[x] = count; - map->compact_to_partition[count] = x; + map->partition_to_view[x] = i; + map->view_to_partition[i] = x; var = map->partition_to_var[x]; + /* If any one of the members of a partition is not an SSA_NAME, make + sure it is the representative. */ if (TREE_CODE (var) != SSA_NAME) - change_partition_var (map, var, count); - count++; - }); + change_partition_var (map, var, i); + i++; + } + gcc_assert (i == count); + map->num_partitions = i; } + + BITMAP_FREE (selected); +} + + +/* Create a partition view which includes all the used partitions in MAP. If + WANT_BASES is true, create the base variable map as well. */ + +extern void +partition_view_normal (var_map map, bool want_bases) +{ + bitmap used; + + used = partition_view_init (map); + partition_view_fini (map, used); + + if (want_bases) + var_map_base_init (map); else + var_map_base_fini (map); +} + + +/* Create a partition view in MAP which includes just partitions which occur in + the bitmap ONLY. If WANT_BASES is true, create the base variable map + as well. */ + +extern void +partition_view_bitmap (var_map map, bitmap only, bool want_bases) +{ + bitmap used; + bitmap new_partitions = BITMAP_ALLOC (NULL); + unsigned x, p; + bitmap_iterator bi; + + used = partition_view_init (map); + EXECUTE_IF_SET_IN_BITMAP (only, 0, x, bi) { - free (map->partition_to_compact); - map->partition_to_compact = NULL; + p = partition_find (map->var_partition, x); + gcc_assert (bitmap_bit_p (used, p)); + bitmap_set_bit (new_partitions, p); } + partition_view_fini (map, new_partitions); - map->num_partitions = count; - - if (rv) - root_var_delete (rv); - sbitmap_free (used); + BITMAP_FREE (used); + if (want_bases) + var_map_base_init (map); + else + var_map_base_fini (map); } /* This function is used to change the representative variable in MAP for VAR's - partition from an SSA_NAME variable to a regular variable. This allows - partitions to be mapped back to real variables. */ + partition to a regular non-ssa variable. This allows partitions to be + mapped back to real variables. */ void 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; VAR_ANN_PARTITION (ann) = part; - if (map->compact_to_partition) - map->partition_to_var[map->compact_to_partition[part]] = var; + if (map->view_to_partition) + map->partition_to_var[map->view_to_partition[part]] = var; } -/* This function looks through the program and uses FLAGS to determine what - SSA versioned variables are given entries in a new partition table. This - new partition map is returned. */ +static inline void mark_all_vars_used (tree *, void *data); -var_map -create_ssa_var_map (int flags) +/* 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) { - block_stmt_iterator bsi; - basic_block bb; - 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; -#endif + tree t = *tp; + enum tree_code_class c = TREE_CODE_CLASS (TREE_CODE (t)); + tree b; + + if (TREE_CODE (t) == SSA_NAME) + t = SSA_NAME_VAR (t); + if ((IS_EXPR_CODE_CLASS (c) + || IS_GIMPLE_STMT_CODE_CLASS (c)) + && (b = TREE_BLOCK (t)) != NULL) + TREE_USED (b) = true; + + /* 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), data); + mark_all_vars_used (&TMR_BASE (t), data); + mark_all_vars_used (&TMR_INDEX (t), data); + *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) + { + if (data != NULL && bitmap_bit_p ((bitmap) data, DECL_UID (t))) + { + bitmap_clear_bit ((bitmap) data, DECL_UID (t)); + mark_all_vars_used (&DECL_INITIAL (t), data); + } + set_is_used (t); + } + + if (IS_TYPE_OR_DECL_P (t)) + *walk_subtrees = 0; - map = init_var_map (highest_ssa_version + 1); + return NULL; +} -#if defined ENABLE_CHECKING - used_in_real_ops = sbitmap_alloc (num_referenced_vars); - sbitmap_zero (used_in_real_ops); +/* Mark the scope block SCOPE and its subblocks unused when they can be + possibly eliminated if dead. */ - used_in_virtual_ops = sbitmap_alloc (num_referenced_vars); - sbitmap_zero (used_in_virtual_ops); -#endif +static void +mark_scope_block_unused (tree scope) +{ + tree t; + TREE_USED (scope) = false; + if (!(*debug_hooks->ignore_block) (scope)) + TREE_USED (scope) = true; + for (t = BLOCK_SUBBLOCKS (scope); t ; t = BLOCK_CHAIN (t)) + mark_scope_block_unused (t); +} + +/* Look if the block is dead (by possibly eliminating its dead subblocks) + and return true if so. + Block is declared dead if: + 1) No statements are associated with it. + 2) Declares no live variables + 3) All subblocks are dead + or there is precisely one subblocks and the block + has same abstract origin as outer block and declares + no variables, so it is pure wrapper. + When we are not outputting full debug info, we also eliminate dead variables + out of scope blocks to let them to be recycled by GGC and to save copying work + done by the inliner. */ + +static bool +remove_unused_scope_block_p (tree scope) +{ + tree *t, *next; + bool unused = !TREE_USED (scope); + var_ann_t ann; + int nsubblocks = 0; - if (flags & SSA_VAR_MAP_REF_COUNT) + for (t = &BLOCK_VARS (scope); *t; t = next) { - map->ref_count - = (int *)xmalloc (((highest_ssa_version + 1) * sizeof (int))); - memset (map->ref_count, 0, (highest_ssa_version + 1) * sizeof (int)); + next = &TREE_CHAIN (*t); + + /* Debug info of nested function refers to the block of the + function. */ + if (TREE_CODE (*t) == FUNCTION_DECL) + unused = false; + + /* When we are outputting debug info, we usually want to output + info about optimized-out variables in the scope blocks. + Exception are the scope blocks not containing any instructions + at all so user can't get into the scopes at first place. */ + else if ((ann = var_ann (*t)) != NULL + && ann->used) + unused = false; + + /* When we are not doing full debug info, we however can keep around + only the used variables for cfgexpand's memory packing saving quite + a lot of memory. */ + else if (debug_info_level == DINFO_LEVEL_NORMAL + || debug_info_level == DINFO_LEVEL_VERBOSE + /* Removing declarations before inlining is going to affect + DECL_UID that in turn is going to affect hashtables and + code generation. */ + || !cfun->after_inlining) + unused = false; + + else + { + *t = TREE_CHAIN (*t); + next = t; + } } + for (t = &BLOCK_SUBBLOCKS (scope); *t ;) + if (remove_unused_scope_block_p (*t)) + { + if (BLOCK_SUBBLOCKS (*t)) + { + tree next = BLOCK_CHAIN (*t); + tree supercontext = BLOCK_SUPERCONTEXT (*t); + *t = BLOCK_SUBBLOCKS (*t); + gcc_assert (!BLOCK_CHAIN (*t)); + BLOCK_CHAIN (*t) = next; + BLOCK_SUPERCONTEXT (*t) = supercontext; + t = &BLOCK_CHAIN (*t); + nsubblocks ++; + } + else + { + gcc_assert (!BLOCK_VARS (*t)); + *t = BLOCK_CHAIN (*t); + } + } + else + { + t = &BLOCK_CHAIN (*t); + nsubblocks ++; + } + /* Outer scope is always used. */ + if (!BLOCK_SUPERCONTEXT (scope) + || TREE_CODE (BLOCK_SUPERCONTEXT (scope)) == FUNCTION_DECL) + unused = false; + /* If there are more than one live subblocks, it is used. */ + else if (nsubblocks > 1) + unused = false; + /* When there is only one subblock, see if it is just wrapper we can + ignore. Wrappers are not declaring any variables and not changing + abstract origin. */ + else if (nsubblocks == 1 + && (BLOCK_VARS (scope) + || ((debug_info_level == DINFO_LEVEL_NORMAL + || debug_info_level == DINFO_LEVEL_VERBOSE) + && ((BLOCK_ABSTRACT_ORIGIN (scope) + != BLOCK_ABSTRACT_ORIGIN (BLOCK_SUPERCONTEXT (scope))))))) + unused = false; + return unused; +} + +/* 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, void *data) +{ + walk_tree (expr_p, mark_all_vars_used_1, data, NULL); +} + + +/* Remove local variables that are not referenced in the IL. */ + +void +remove_unused_locals (void) +{ + basic_block bb; + tree t, *cell; + referenced_var_iterator rvi; + var_ann_t ann; + bitmap global_unused_vars = NULL; + + mark_scope_block_unused (DECL_INITIAL (current_function_decl)); + /* Assume all locals are unused. */ + FOR_EACH_REFERENCED_VAR (t, rvi) + var_ann (t)->used = false; + + /* Walk the CFG marking all referenced symbols. */ FOR_EACH_BB (bb) { - tree phi, arg; - for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi)) - { - int i; - register_ssa_partition (map, PHI_RESULT (phi), false); - for (i = 0; i < PHI_NUM_ARGS (phi); i++) - { - arg = PHI_ARG_DEF (phi, i); - if (TREE_CODE (arg) == SSA_NAME) - register_ssa_partition (map, arg, true); - } - } + block_stmt_iterator bsi; + tree phi, def; + /* Walk the statements. */ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) + mark_all_vars_used (bsi_stmt_ptr (bsi), NULL); + + for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) { - stmt = bsi_stmt (bsi); - get_stmt_operands (stmt); - ann = stmt_ann (stmt); + use_operand_p arg_p; + ssa_op_iter i; - /* Register USE and DEF operands in each statement. */ - uses = USE_OPS (ann); - for (x = 0; x < NUM_USES (uses); x++) - { - use = USE_OP_PTR (uses, x); - register_ssa_partition (map, *use, true); + /* No point processing globals. */ + if (is_global_var (SSA_NAME_VAR (PHI_RESULT (phi)))) + continue; -#if defined ENABLE_CHECKING - SET_BIT (used_in_real_ops, var_ann (SSA_NAME_VAR (*use))->uid); -#endif - } + def = PHI_RESULT (phi); + mark_all_vars_used (&def, NULL); - defs = DEF_OPS (ann); - for (x = 0; x < NUM_DEFS (defs); x++) - { - dest = DEF_OP_PTR (defs, x); - register_ssa_partition (map, *dest, false); + FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_ALL_USES) + { + tree arg = USE_FROM_PTR (arg_p); + mark_all_vars_used (&arg, NULL); + } + } + } -#if defined ENABLE_CHECKING - SET_BIT (used_in_real_ops, var_ann (SSA_NAME_VAR (*dest))->uid); -#endif - } + /* Remove unmarked local vars from local_decls. */ + for (cell = &cfun->local_decls; *cell; ) + { + tree var = TREE_VALUE (*cell); - /* 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++) + if (TREE_CODE (var) != FUNCTION_DECL + && (!(ann = var_ann (var)) + || !ann->used)) + { + if (is_global_var (var)) { - 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 + if (global_unused_vars == NULL) + global_unused_vars = BITMAP_ALLOC (NULL); + bitmap_set_bit (global_unused_vars, DECL_UID (var)); } - - vdefs = VDEF_OPS (ann); - for (x = 0; x < NUM_VDEFS (vdefs); x++) + else { - tree var = VDEF_OP (vdefs, x); - set_is_used (var); - -#if defined ENABLE_CHECKING - SET_BIT (used_in_virtual_ops, var_ann (SSA_NAME_VAR (var))->uid); -#endif + *cell = TREE_CHAIN (*cell); + continue; } } + cell = &TREE_CHAIN (*cell); } -#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) - { - EXECUTE_IF_SET_IN_SBITMAP (both, 0, i, - fprintf (stderr, "Variable %s used in real and virtual operands\n", - get_name (referenced_var (i)))); - abort (); - } + /* Remove unmarked global vars from local_decls. */ + if (global_unused_vars != NULL) + { + for (t = cfun->local_decls; t; t = TREE_CHAIN (t)) + { + tree var = TREE_VALUE (t); - sbitmap_free (used_in_real_ops); - sbitmap_free (used_in_virtual_ops); - sbitmap_free (both); - } -#endif + if (TREE_CODE (var) == VAR_DECL + && is_global_var (var) + && (ann = var_ann (var)) != NULL + && ann->used) + mark_all_vars_used (&DECL_INITIAL (var), global_unused_vars); + } - return map; + for (cell = &cfun->local_decls; *cell; ) + { + tree var = TREE_VALUE (*cell); + + if (TREE_CODE (var) == VAR_DECL + && is_global_var (var) + && bitmap_bit_p (global_unused_vars, DECL_UID (var))) + *cell = TREE_CHAIN (*cell); + else + cell = &TREE_CHAIN (*cell); + } + BITMAP_FREE (global_unused_vars); + } + + /* Remove unused variables from REFERENCED_VARs. As a special + exception keep the variables that are believed to be aliased. + Those can't be easily removed from the alias sets and operand + caches. They will be removed shortly after the next may_alias + pass is performed. */ + FOR_EACH_REFERENCED_VAR (t, rvi) + if (!is_global_var (t) + && !MTAG_P (t) + && TREE_CODE (t) != PARM_DECL + && TREE_CODE (t) != RESULT_DECL + && !(ann = var_ann (t))->used + && !ann->symbol_mem_tag + && !TREE_ADDRESSABLE (t)) + remove_referenced_var (t); + remove_unused_scope_block_p (DECL_INITIAL (current_function_decl)); } @@ -425,20 +692,24 @@ 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->livein = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap)); + for (x = 0; x < (unsigned)last_basic_block; x++) + live->livein[x] = 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->liveout = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap)); + for (x = 0; x < (unsigned)last_basic_block; x++) + live->liveout[x] = BITMAP_ALLOC (NULL); - /* liveout is deferred until it is actually requested. */ - live->liveout = NULL; + live->work_stack = XNEWVEC (int, last_basic_block); + live->stack_top = live->work_stack; + + live->global = BITMAP_ALLOC (NULL); return live; } @@ -449,1264 +720,236 @@ void delete_tree_live_info (tree_live_info_p live) { int x; - if (live->liveout) - { - for (x = live->num_blocks - 1; x >= 0; x--) - BITMAP_XFREE (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]); - free (live->livein); - } - if (live->global) - BITMAP_XFREE (live->global); - + + BITMAP_FREE (live->global); + free (live->work_stack); + + for (x = live->num_blocks - 1; x >= 0; x--) + BITMAP_FREE (live->liveout[x]); + free (live->liveout); + + for (x = live->num_blocks - 1; x >= 0; x--) + BITMAP_FREE (live->livein[x]); + free (live->livein); + free (live); } -/* Using LIVE, fill in all the live-on-entry blocks between the defs and uses - for partition I. STACK is a varray used for temporary memory which is - passed in rather than being allocated on every call. */ +/* Visit basic block BB and propagate any required live on entry bits from + LIVE into the predecessors. VISITED is the bitmap of visited blocks. + TMP is a temporary work bitmap which is passed in to avoid reallocating + it each time. */ -static void -live_worklist (tree_live_info_p live, varray_type stack, int i) +static void +loe_visit_block (tree_live_info_p live, basic_block bb, sbitmap visited, + bitmap tmp) { - int b; - tree var; - basic_block def_bb = NULL; edge e; - var_map map = live->map; - - var = partition_to_var (map, i); - if (SSA_NAME_DEF_STMT (var)) - def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var)); + bool change; + edge_iterator ei; + basic_block pred_bb; + bitmap loe; + gcc_assert (!TEST_BIT (visited, bb->index)); - EXECUTE_IF_SET_IN_BITMAP (live->livein[i], 0, b, - { - VARRAY_PUSH_INT (stack, b); - }); + SET_BIT (visited, bb->index); + loe = live_on_entry (live, bb); - while (VARRAY_ACTIVE_SIZE (stack) > 0) + FOR_EACH_EDGE (e, ei, bb->preds) { - b = VARRAY_TOP_INT (stack); - VARRAY_POP (stack); - - for (e = BASIC_BLOCK (b)->pred; e; e = e->pred_next) - 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); - } - } + pred_bb = e->src; + if (pred_bb == ENTRY_BLOCK_PTR) + continue; + /* TMP is variables live-on-entry from BB that aren't defined in the + predecessor block. This should be the live on entry vars to pred. + Note that liveout is the DEFs in a block while live on entry is + being calculated. */ + bitmap_and_compl (tmp, loe, live->liveout[pred_bb->index]); + + /* Add these bits to live-on-entry for the pred. if there are any + changes, and pred_bb has been visited already, add it to the + revisit stack. */ + change = bitmap_ior_into (live_on_entry (live, pred_bb), tmp); + if (TEST_BIT (visited, pred_bb->index) && change) + { + RESET_BIT (visited, pred_bb->index); + *(live->stack_top)++ = pred_bb->index; + } } } -/* If VAR is in a partition of MAP, set the bit for that partition in VEC. */ +/* Using LIVE, fill in all the live-on-entry blocks between the defs and uses + of all the variables. */ -static inline void -set_if_valid (var_map map, bitmap vec, tree var) +static void +live_worklist (tree_live_info_p live) { - int p = var_to_partition (map, var); - if (p != NO_PARTITION) - bitmap_set_bit (vec, p); -} + unsigned b; + basic_block bb; + sbitmap visited = sbitmap_alloc (last_basic_block + 1); + bitmap tmp = BITMAP_ALLOC (NULL); + sbitmap_zero (visited); -/* If VAR is in a partition and it isn't defined in DEF_VEC, set the livein and - global bit for it in the LIVE object. BB is the block being processed. */ + /* Visit all the blocks in reverse order and propagate live on entry values + into the predecessors blocks. */ + FOR_EACH_BB_REVERSE (bb) + loe_visit_block (live, bb, visited, tmp); -static inline void -add_livein_if_notdef (tree_live_info_p live, bitmap def_vec, - tree var, basic_block bb) -{ - int p = var_to_partition (live->map, var); - if (p == NO_PARTITION || bb == ENTRY_BLOCK_PTR) - return; - if (!bitmap_bit_p (def_vec, p)) + /* Process any blocks which require further iteration. */ + while (live->stack_top != live->work_stack) { - bitmap_set_bit (live->livein[p], bb->index); - bitmap_set_bit (live->global, p); + b = *--(live->stack_top); + loe_visit_block (live, BASIC_BLOCK (b), visited, tmp); } + + BITMAP_FREE (tmp); + sbitmap_free (visited); } -/* Given partition map MAP, calculate all the live on entry bitmaps for - each basic block. Return a live info object. */ +/* Calculate the initial live on entry vector for SSA_NAME using immediate_use + links. Set the live on entry fields in LIVE. Def's are marked temporarily + in the liveout vector. */ -tree_live_info_p -calculate_live_on_entry (var_map map) +static void +set_var_live_on_entry (tree ssa_name, tree_live_info_p live) { - tree_live_info_p live; - int num, i; - basic_block bb; - bitmap saw_def; - tree phi, var, stmt; - tree op; - edge e; - varray_type stack; - block_stmt_iterator bsi; - use_optype uses; - def_optype defs; - stmt_ann_t ann; + int p; + tree stmt; + use_operand_p use; + basic_block def_bb = NULL; + imm_use_iterator imm_iter; + bool global = false; - saw_def = BITMAP_XMALLOC (); + p = var_to_partition (live->map, ssa_name); + if (p == NO_PARTITION) + return; - live = new_tree_live_info (map); + stmt = SSA_NAME_DEF_STMT (ssa_name); + if (stmt) + { + def_bb = bb_for_stmt (stmt); + /* Mark defs in liveout bitmap temporarily. */ + if (def_bb) + bitmap_set_bit (live->liveout[def_bb->index], p); + } + else + def_bb = ENTRY_BLOCK_PTR; - FOR_EACH_BB (bb) + /* Visit each use of SSA_NAME and if it isn't in the same block as the def, + add it to the list of live on entry blocks. */ + FOR_EACH_IMM_USE_FAST (use, imm_iter, ssa_name) { - bitmap_clear (saw_def); + tree use_stmt = USE_STMT (use); + basic_block add_block = NULL; - for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi)) - { - for (i = 0; i < PHI_NUM_ARGS (phi); i++) + if (TREE_CODE (use_stmt) == PHI_NODE) + { + /* Uses in PHI's are considered to be live at exit of the SRC block + as this is where a copy would be inserted. Check to see if it is + defined in that block, or whether its live on entry. */ + int index = PHI_ARG_INDEX_FROM_USE (use); + edge e = PHI_ARG_EDGE (use_stmt, index); + if (e->src != ENTRY_BLOCK_PTR) { - 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); - - /* 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 - on entry to that block. */ - if (!stmt || e->src != bb_for_stmt (stmt)) - add_livein_if_notdef (live, saw_def, var, e->src); + if (e->src != def_bb) + add_block = e->src; } - } - - /* Don't mark PHI results as defined until all the PHI nodes have - been processed. If the PHI sequence is: - a_3 = PHI - b_3 = PHI - 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)) + } + else + { + /* If its not defined in this block, its live on entry. */ + basic_block use_bb = bb_for_stmt (use_stmt); + if (use_bb != def_bb) + add_block = use_bb; + } + + /* If there was a live on entry use, set the bit. */ + if (add_block) { - var = PHI_RESULT (phi); - set_if_valid (map, saw_def, var); + global = true; + bitmap_set_bit (live->livein[add_block->index], p); } + } - for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) - { - stmt = bsi_stmt (bsi); - get_stmt_operands (stmt); - ann = stmt_ann (stmt); + /* If SSA_NAME is live on entry to at least one block, fill in all the live + on entry blocks between the def and all the uses. */ + if (global) + bitmap_set_bit (live->global, p); +} - uses = USE_OPS (ann); - num = NUM_USES (uses); - for (i = 0; i < num; i++) - { - 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++) - { - op = DEF_OP (defs, i); - set_if_valid (map, saw_def, op); - } - } - } +/* Calculate the live on exit vectors based on the entry info in LIVEINFO. */ - VARRAY_INT_INIT (stack, last_basic_block, "stack"); - EXECUTE_IF_SET_IN_BITMAP (live->global, 0, i, - { - live_worklist (live, stack, i); - }); +void +calculate_live_on_exit (tree_live_info_p liveinfo) +{ + unsigned i; + int p; + tree t, phi; + basic_block bb; + edge e; + edge_iterator ei; -#ifdef ENABLE_CHECKING - /* Check for live on entry partitions and report those with a DEF in - the program. This will typically mean an optimization has done - something wrong. */ - - bb = ENTRY_BLOCK_PTR; - num = 0; - for (e = bb->succ; e; e = e->succ_next) - { - int entry_block = e->dest->index; - if (e->dest == EXIT_BLOCK_PTR) - continue; - for (i = 0; i < num_var_partitions (map); i++) - { - basic_block tmp; - tree d; - var = partition_to_var (map, i); - stmt = SSA_NAME_DEF_STMT (var); - tmp = bb_for_stmt (stmt); - d = default_def (SSA_NAME_VAR (var)); - - if (bitmap_bit_p (live_entry_blocks (live, i), entry_block)) - { - if (!IS_EMPTY_STMT (stmt)) - { - num++; - print_generic_expr (stderr, var, TDF_SLIM); - fprintf (stderr, " is defined "); - if (tmp) - fprintf (stderr, " in BB%d, ", tmp->index); - fprintf (stderr, "by:\n"); - print_generic_expr (stderr, stmt, TDF_SLIM); - fprintf (stderr, "\nIt is also live-on-entry to entry BB %d", - entry_block); - fprintf (stderr, " So it appears to have multiple defs.\n"); - } - else - { - if (d != var) - { - num++; - print_generic_expr (stderr, var, TDF_SLIM); - fprintf (stderr, " is live-on-entry to BB%d ",entry_block); - if (d) - { - fprintf (stderr, " but is not the default def of "); - print_generic_expr (stderr, d, TDF_SLIM); - fprintf (stderr, "\n"); - } - else - fprintf (stderr, " and there is no default def.\n"); - } - } - } - else - if (d == var) - { - /* The only way this var shouldn't be marked live on entry is - if it occurs in a PHI argument of the block. */ - int z, ok = 0; - for (phi = phi_nodes (e->dest); - phi && !ok; - phi = TREE_CHAIN (phi)) - { - for (z = 0; z < PHI_NUM_ARGS (phi); z++) - if (var == PHI_ARG_DEF (phi, z)) - { - ok = 1; - break; - } - } - if (ok) - continue; - num++; - print_generic_expr (stderr, var, TDF_SLIM); - fprintf (stderr, " is not marked live-on-entry to entry BB%d ", - entry_block); - fprintf (stderr, "but it is a default def so it should be.\n"); - } - } - } - if (num > 0) - abort (); -#endif - - BITMAP_XFREE (saw_def); - - return live; -} - - -/* Calculate the live on exit vectors based on the entry info in LIVEINFO. */ - -void -calculate_live_on_exit (tree_live_info_p liveinfo) -{ - unsigned b; - int i, x; - bitmap *on_exit; - basic_block bb; - edge e; - tree t, phi; - bitmap on_entry; - 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 (); - - /* 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++) - { - t = PHI_ARG_DEF (phi, i); - e = PHI_ARG_EDGE (phi, i); - if (!phi_ssa_name_p (t) || e->src == ENTRY_BLOCK_PTR) - continue; - set_if_valid (map, on_exit[e->src->index], t); - } - } - - /* Set live on exit for all predecessors of live on entry's. */ - for (i = 0; i < num_var_partitions (map); i++) - { - on_entry = live_entry_blocks (liveinfo, i); - EXECUTE_IF_SET_IN_BITMAP (on_entry, 0, b, - { - for (e = BASIC_BLOCK(b)->pred; e; e = e->pred_next) - if (e->src != ENTRY_BLOCK_PTR) - bitmap_set_bit (on_exit[e->src->index], i); - }); - } - - liveinfo->liveout = on_exit; -} - - -/* Initialize a tree_partition_associator object using MAP. */ - -tpa_p -tpa_init (var_map map) -{ - tpa_p tpa; - int num_partitions = num_var_partitions (map); - int x; - - if (num_partitions == 0) - return NULL; - - tpa = (tpa_p) xmalloc (sizeof (struct tree_partition_associator_d)); - tpa->num_trees = 0; - tpa->uncompressed_num = -1; - tpa->map = map; - tpa->next_partition = (int *)xmalloc (num_partitions * sizeof (int)); - memset (tpa->next_partition, TPA_NONE, num_partitions * sizeof (int)); - - tpa->partition_to_tree_map = (int *)xmalloc (num_partitions * sizeof (int)); - 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"); - VARRAY_INT_INIT (tpa->first_partition, x, "first_partition"); - - return tpa; - -} - - -/* Remove PARTITION_INDEX from TREE_INDEX's list in the tpa structure TPA. */ - -void -tpa_remove_partition (tpa_p tpa, int tree_index, int partition_index) -{ - int i; - - i = tpa_first_partition (tpa, tree_index); - if (i == partition_index) - { - VARRAY_INT (tpa->first_partition, tree_index) = tpa->next_partition[i]; - } - else - { - for ( ; i != TPA_NONE; i = tpa_next_partition (tpa, i)) - { - if (tpa->next_partition[i] == partition_index) - { - tpa->next_partition[i] = tpa->next_partition[partition_index]; - break; - } - } - } -} - - -/* Free the memory used by tree_partition_associator object TPA. */ - -void -tpa_delete (tpa_p tpa) -{ - if (!tpa) - return; - - free (tpa->partition_to_tree_map); - free (tpa->next_partition); - free (tpa); -} - - -/* This function will remove any tree entires from TPA which have only a single - element. This will help keep the size of the conflict graph down. The - function returns the number of remaining tree lists. */ - -int -tpa_compact (tpa_p tpa) -{ - int last, x, y, first, swap_i; - tree swap_t; - - /* Find the last list which has more than 1 partition. */ - for (last = tpa->num_trees - 1; last > 0; last--) - { - first = tpa_first_partition (tpa, last); - if (tpa_next_partition (tpa, first) != NO_PARTITION) - break; - } - - x = 0; - while (x < last) - { - first = tpa_first_partition (tpa, x); - - /* If there is not more than one partition, swap with the current end - of the tree list. */ - if (tpa_next_partition (tpa, first) == NO_PARTITION) - { - swap_t = VARRAY_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); - 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; - VARRAY_INT (tpa->first_partition, x) = swap_i; - for (y = tpa_first_partition (tpa, x); - y != NO_PARTITION; - y = tpa_next_partition (tpa, y)) - tpa->partition_to_tree_map[y] = x; - - /* Ensure last is a list with more than one partition. */ - last--; - for (; last > x; last--) - { - first = tpa_first_partition (tpa, last); - if (tpa_next_partition (tpa, first) != NO_PARTITION) - break; - } - } - x++; - } - - first = tpa_first_partition (tpa, x); - if (tpa_next_partition (tpa, first) != NO_PARTITION) - x++; - tpa->uncompressed_num = tpa->num_trees; - tpa->num_trees = x; - return last; -} - - -/* Initialize a root_var object with SSA partitions from MAP which are based - on each root variable. */ - -root_var_p -root_var_init (var_map map) -{ - root_var_p rv; - int num_partitions = num_var_partitions (map); - int x, p; - tree t; - var_ann_t ann; - sbitmap seen; - - rv = tpa_init (map); - if (!rv) - return NULL; - - seen = sbitmap_alloc (num_partitions); - sbitmap_zero (seen); - - /* Start at the end and work towards the front. This will provide a list - that is ordered from smallest to largest. */ - for (x = num_partitions - 1; x >= 0; x--) - { - t = partition_to_var (map, x); - - /* The var map may not be compacted yet, so check for NULL. */ - if (!t) - continue; - - p = var_to_partition (map, t); - -#ifdef ENABLE_CHECKING - if (p == NO_PARTITION) - abort (); -#endif - - /* Make sure we only put coalesced partitions into the list once. */ - if (TEST_BIT (seen, p)) - continue; - SET_BIT (seen, p); - if (TREE_CODE (t) == SSA_NAME) - t = SSA_NAME_VAR (t); - ann = var_ann (t); - if (ann->root_var_processed) - { - rv->next_partition[p] = VARRAY_INT (rv->first_partition, - VAR_ANN_ROOT_INDEX (ann)); - VARRAY_INT (rv->first_partition, VAR_ANN_ROOT_INDEX (ann)) = p; - } - else - { - ann->root_var_processed = 1; - VAR_ANN_ROOT_INDEX (ann) = rv->num_trees++; - VARRAY_PUSH_TREE (rv->trees, t); - VARRAY_PUSH_INT (rv->first_partition, p); - } - rv->partition_to_tree_map[p] = VAR_ANN_ROOT_INDEX (ann); - } - - /* 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); - var_ann (t)->root_var_processed = 0; - } - - sbitmap_free (seen); - return rv; -} - - -/* Initialize a type_var structure which associates all the partitions in MAP - of the same type to the type node's index. Volatiles are ignored. */ - -type_var_p -type_var_init (var_map map) -{ - type_var_p tv; - int x, y, p; - int num_partitions = num_var_partitions (map); - tree t; - sbitmap seen; - - seen = sbitmap_alloc (num_partitions); - sbitmap_zero (seen); - - tv = tpa_init (map); - if (!tv) - return NULL; - - for (x = num_partitions - 1; x >= 0; x--) - { - t = partition_to_var (map, x); - - /* Disallow coalescing of these types of variables. */ - if (!t - || TREE_THIS_VOLATILE (t) - || TREE_CODE (t) == RESULT_DECL - || TREE_CODE (t) == PARM_DECL - || (DECL_P (t) - && (DECL_REGISTER (t) - || !DECL_ARTIFICIAL (t) - || DECL_RTL_SET_P (t)))) - continue; - - p = var_to_partition (map, t); - -#ifdef ENABLE_CHECKING - if (p == NO_PARTITION) - abort (); -#endif - - /* If partitions have been coalesced, only add the representative - for the partition to the list once. */ - if (TEST_BIT (seen, p)) - continue; - SET_BIT (seen, p); - t = TREE_TYPE (t); - - /* Find the list for this type. */ - for (y = 0; y < tv->num_trees; y++) - if (t == VARRAY_TREE (tv->trees, y)) - break; - if (y == tv->num_trees) - { - tv->num_trees++; - VARRAY_PUSH_TREE (tv->trees, t); - VARRAY_PUSH_INT (tv->first_partition, p); - } - else - { - tv->next_partition[p] = VARRAY_INT (tv->first_partition, y); - VARRAY_INT (tv->first_partition, y) = p; - } - tv->partition_to_tree_map[p] = y; - } - sbitmap_free (seen); - return tv; -} - - -/* Create a new coalesce list object from MAP and return it. */ - -coalesce_list_p -create_coalesce_list (var_map map) -{ - coalesce_list_p list; - - list = (coalesce_list_p) xmalloc (sizeof (struct coalesce_list_d)); - - list->map = map; - list->add_mode = true; - list->list = (partition_pair_p *) xcalloc (num_var_partitions (map), - sizeof (struct partition_pair_d)); - return list; -} - - -/* Delete coalesce list CL. */ - -void -delete_coalesce_list (coalesce_list_p cl) -{ - free (cl->list); - free (cl); -} - - -/* Find a matching coalesce pair object in CL for partitions P1 and P2. If - one isn't found, return NULL if CREATE is false, otherwise create a new - coalesce pair object and return it. */ - -static partition_pair_p -find_partition_pair (coalesce_list_p cl, int p1, int p2, bool create) -{ - partition_pair_p node, tmp; - int s; - - /* Normalize so that p1 is the smaller value. */ - if (p2 < p1) - { - s = p1; - p1 = p2; - p2 = s; - } - - tmp = NULL; - - /* The list is sorted such that if we find a value greater than p2, - p2 is not in the list. */ - for (node = cl->list[p1]; node; node = node->next) - { - if (node->second_partition == p2) - return node; - else - if (node->second_partition > p2) - break; - tmp = node; - } - - if (!create) - return NULL; - - node = (partition_pair_p) xmalloc (sizeof (struct partition_pair_d)); - node->first_partition = p1; - node->second_partition = p2; - node->cost = 0; - - if (tmp != NULL) - { - node->next = tmp->next; - tmp->next = node; - } - else - { - /* This is now the first node in the list. */ - node->next = cl->list[p1]; - cl->list[p1] = node; - } - - return node; -} - - -/* 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) -{ - partition_pair_p node; - -#ifdef ENABLE_CHECKING - if (!cl->add_mode) - abort(); -#endif - - if (p1 == p2) - return; - - node = find_partition_pair (cl, p1, p2, true); - - node->cost += value; -} - - -/* Comparison function to allow qsort to sort P1 and P2 in descending order. */ - -static -int compare_pairs (const void *p1, const void *p2) -{ - return (*(partition_pair_p *)p2)->cost - (*(partition_pair_p *)p1)->cost; -} - - -/* Prepare CL for removal of preferred pairs. When finished, list element - 0 has all the coalesce pairs, sorted in order from most important coalesce - to least important. */ - -void -sort_coalesce_list (coalesce_list_p cl) -{ - int x, num, count; - partition_pair_p chain, p; - partition_pair_p *list; - - if (!cl->add_mode) - abort(); - - cl->add_mode = false; - - /* Compact the array of lists to a single list, and count the elements. */ - num = 0; - chain = NULL; - for (x = 0; x < num_var_partitions (cl->map); x++) - if (cl->list[x] != NULL) - { - for (p = cl->list[x]; p->next != NULL; p = p->next) - num++; - num++; - p->next = chain; - chain = cl->list[x]; - cl->list[x] = NULL; - } - - /* Only call qsort if there are more than 2 items. */ - if (num > 2) - { - list = xmalloc (sizeof (partition_pair_p) * num); - count = 0; - for (p = chain; p != NULL; p = p->next) - list[count++] = p; - -#ifdef ENABLE_CHECKING - if (count != num) - abort (); -#endif - - qsort (list, count, sizeof (partition_pair_p), compare_pairs); - - p = list[0]; - for (x = 1; x < num; x++) - { - p->next = list[x]; - p = list[x]; - } - p->next = NULL; - cl->list[0] = list[0]; - free (list); - } - else - { - cl->list[0] = chain; - if (num == 2) - { - /* Simply swap the two elements if they are in the wrong order. */ - if (chain->cost < chain->next->cost) - { - cl->list[0] = chain->next; - cl->list[0]->next = chain; - chain->next = NULL; - } - } - } -} - - -/* Retrieve the best remaining pair to coalesce from CL. Returns the 2 - 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 -pop_best_coalesce (coalesce_list_p cl, int *p1, int *p2) -{ - partition_pair_p node; - int ret; - - if (cl->add_mode) - abort(); - - node = cl->list[0]; - if (!node) - return NO_BEST_COALESCE; - - cl->list[0] = node->next; - - *p1 = node->first_partition; - *p2 = node->second_partition; - ret = node->cost; - free (node); - - return ret; -} - - -/* If variable VAR is in a partition in MAP, add a conflict in GRAPH between - VAR and any other live partitions in VEC which are associated via TPA. - Reset the live bit in VEC. */ - -static inline void -add_conflicts_if_valid (tpa_p tpa, conflict_graph graph, - var_map map, bitmap vec, tree var) -{ - int p, y, first; - p = var_to_partition (map, var); - if (p != NO_PARTITION) - { - bitmap_clear_bit (vec, p); - first = tpa_find_tree (tpa, p); - /* If find returns nothing, this object isn't interesting. */ - if (first == TPA_NONE) - return; - /* Only add interferences between objects in the same list. */ - for (y = tpa_first_partition (tpa, first); - y != TPA_NONE; - y = tpa_next_partition (tpa, y)) - { - if (bitmap_bit_p (vec, y)) - conflict_graph_add (graph, p, y); - } - } -} - - -/* Return a conflict graph for the information contained in LIVE_INFO. Only - conflicts between items in the same TPA list are added. If optional - coalesce list CL is passed in, any copies encountered are added. */ - -conflict_graph -build_tree_conflict_graph (tree_live_info_p liveinfo, tpa_p tpa, - coalesce_list_p cl) -{ - conflict_graph graph; - var_map map; - bitmap live; - int num, x, y, i; - basic_block bb; - varray_type partition_link, tpa_to_clear, tpa_nodes; - def_optype defs; - use_optype uses; - unsigned l; - - map = live_var_map (liveinfo); - graph = conflict_graph_new (num_var_partitions (map)); - - if (tpa_num_trees (tpa) == 0) - return graph; - - live = BITMAP_XMALLOC (); - - 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"); + /* live on entry calculations used liveout vectors for defs, clear them. */ + FOR_EACH_BB (bb) + bitmap_clear (liveinfo->liveout[bb->index]); + /* Set all the live-on-exit bits for uses in PHIs. */ FOR_EACH_BB (bb) { - block_stmt_iterator bsi; - tree phi; - - /* Start with live on exit temporaries. */ - bitmap_copy (live, live_on_exit (liveinfo, bb)); - - for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi)) - { - 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 - two things which are copied. If the two variables really do - conflict, they will conflict elsewhere in the program. - - 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. */ - - if (TREE_CODE (stmt) == MODIFY_EXPR) - { - tree lhs = TREE_OPERAND (stmt, 0); - tree rhs = TREE_OPERAND (stmt, 1); - int p1, p2; - int bit; - - if (DECL_P (lhs) || TREE_CODE (lhs) == SSA_NAME) - p1 = var_to_partition (map, lhs); - else - p1 = NO_PARTITION; - - if (DECL_P (rhs) || TREE_CODE (rhs) == SSA_NAME) - p2 = var_to_partition (map, rhs); - else - p2 = NO_PARTITION; - - if (p1 != NO_PARTITION && p2 != NO_PARTITION) - { - is_a_copy = true; - bit = bitmap_bit_p (live, p2); - /* If the RHS is live, make it not live while we add - the conflicts, then make it live again. */ - if (bit) - bitmap_clear_bit (live, p2); - add_conflicts_if_valid (tpa, graph, map, live, lhs); - if (bit) - bitmap_set_bit (live, p2); - if (cl) - add_coalesce (cl, p1, p2, 1); - 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++) - { - var_p = DEF_OP_PTR (defs, x); - add_conflicts_if_valid (tpa, graph, map, live, *var_p); - } - - uses = USE_OPS (ann); - num = NUM_USES (uses); - for (x = 0; x < num; x++) - { - var_p = USE_OP_PTR (uses, x); - set_if_valid (map, live, *var_p); - } - } - } - - /* If result of a PHI is unused, then the loops over the statements - will not record any conflicts. However, since the PHI node is - 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)) - { - tree result = PHI_RESULT (phi); - int p = var_to_partition (map, result); - - if (p != NO_PARTITION && ! bitmap_bit_p (live, p)) - add_conflicts_if_valid (tpa, graph, map, live, result); - } - - /* Anything which is still live at this point interferes. - In order to implement this efficiently, only conflicts between - partitions which have the same TPA root need be added. - TPA roots which have been seen are tracked in 'tpa_nodes'. A non-zero - entry points to an index into 'partition_link', which then indexes - into itself forming a linked list of partitions sharing a tpa root - which have been seen as live up to this point. Since partitions start - at index zero, all entries in partition_link are (partition + 1). - - Conflicts are added between the current partition and any already seen. - 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, - { - i = tpa_find_tree (tpa, x); - if (i != TPA_NONE) - { - int start = VARRAY_INT (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); - - /* Add interferences to other tpa members seen. */ - for (y = start; y != 0; y = VARRAY_INT (partition_link, y)) - conflict_graph_add (graph, x, y - 1); - VARRAY_INT (tpa_nodes, i) = x + 1; - VARRAY_INT (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); - } - - BITMAP_XFREE (live); - return graph; -} - - -/* This routine will attempt to coalesce the elements in TPA subject to the - conflicts found in GRAPH. If optional coalesce_list CL is provided, - only coalesces specified within the coalesce list are attempted. Otherwise - an attempt is made to coalesce as many partitions within each TPA grouping - as possible. If DEBUG is provided, debug output will be sent there. */ - -void -coalesce_tpa_members (tpa_p tpa, conflict_graph graph, var_map map, - coalesce_list_p cl, FILE *debug) -{ - int x, y, z, w; - tree var, tmp; - - /* Attempt to coalesce any items in a coalesce list. */ - if (cl) - { - while (pop_best_coalesce (cl, &x, &y) != NO_BEST_COALESCE) - { - if (debug) - { - fprintf (debug, "Coalesce list: (%d)", x); - print_generic_expr (debug, partition_to_var (map, x), TDF_SLIM); - fprintf (debug, " & (%d)", y); - print_generic_expr (debug, partition_to_var (map, y), TDF_SLIM); - } - - w = tpa_find_tree (tpa, x); - z = tpa_find_tree (tpa, y); - if (w != z || w == TPA_NONE || z == TPA_NONE) - { - if (debug) - { - if (w != z) - fprintf (debug, ": Fail, Non-matching TPA's\n"); - if (w == TPA_NONE) - fprintf (debug, ": Fail %d non TPA.\n", x); - else - fprintf (debug, ": Fail %d non TPA.\n", y); - } + /* Mark the PHI arguments which are live on exit to the pred block. */ + 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); + if (TREE_CODE (t) != SSA_NAME) continue; - } - var = partition_to_var (map, x); - tmp = partition_to_var (map, y); - x = var_to_partition (map, var); - y = var_to_partition (map, tmp); - if (debug) - fprintf (debug, " [map: %d, %d] ", x, y); - if (x == y) - { - if (debug) - fprintf (debug, ": Already Coalesced.\n"); + p = var_to_partition (liveinfo->map, t); + if (p == NO_PARTITION) continue; - } - if (!conflict_graph_conflict_p (graph, x, y)) - { - z = var_union (map, var, tmp); - if (z == NO_PARTITION) - { - if (debug) - fprintf (debug, ": Unable to perform partition union.\n"); - continue; - } - - /* z is the new combined partition. We need to remove the other - partition from the list. Set x to be that other partition. */ - if (z == x) - { - conflict_graph_merge_regs (graph, x, y); - w = tpa_find_tree (tpa, y); - tpa_remove_partition (tpa, w, y); - } - else - { - conflict_graph_merge_regs (graph, y, x); - w = tpa_find_tree (tpa, x); - tpa_remove_partition (tpa, w, x); - } - - if (debug) - fprintf (debug, ": Success -> %d\n", z); - } - else - if (debug) - fprintf (debug, ": Fail due to conflict\n"); - } - /* If using a coalesce list, don't try to coalesce anything else. */ - return; - } - - for (x = 0; x < tpa_num_trees (tpa); x++) - { - while (tpa_first_partition (tpa, x) != TPA_NONE) - { - int p1, p2; - /* Coalesce first partition with anything that doesn't conflict. */ - y = tpa_first_partition (tpa, x); - tpa_remove_partition (tpa, x, y); - - var = partition_to_var (map, y); - /* p1 is the partition representative to which y belongs. */ - p1 = var_to_partition (map, var); - - for (z = tpa_next_partition (tpa, y); - z != TPA_NONE; - z = tpa_next_partition (tpa, z)) - { - tmp = partition_to_var (map, z); - /* p2 is the partition representative to which z belongs. */ - p2 = var_to_partition (map, tmp); - if (debug) - { - fprintf (debug, "Coalesce : "); - print_generic_expr (debug, var, TDF_SLIM); - fprintf (debug, " &"); - print_generic_expr (debug, tmp, TDF_SLIM); - fprintf (debug, " (%d ,%d)", p1, p2); - } + e = PHI_ARG_EDGE (phi, i); + if (e->src != ENTRY_BLOCK_PTR) + bitmap_set_bit (liveinfo->liveout[e->src->index], p); + } - /* If partitions are already merged, don't check for conflict. */ - if (tmp == var) - { - tpa_remove_partition (tpa, x, z); - if (debug) - fprintf (debug, ": Already coalesced\n"); - } - else - if (!conflict_graph_conflict_p (graph, p1, p2)) - { - int v; - if (tpa_find_tree (tpa, y) == TPA_NONE - || tpa_find_tree (tpa, z) == TPA_NONE) - { - if (debug) - fprintf (debug, ": Fail non-TPA member\n"); - continue; - } - if ((v = var_union (map, var, tmp)) == NO_PARTITION) - { - if (debug) - fprintf (debug, ": Fail cannot combine partitions\n"); - continue; - } - - tpa_remove_partition (tpa, x, z); - if (v == p1) - conflict_graph_merge_regs (graph, v, z); - else - { - /* Update the first partition's representative. */ - conflict_graph_merge_regs (graph, v, y); - p1 = v; - } - - /* The root variable of the partition may be changed - now. */ - var = partition_to_var (map, p1); - - if (debug) - fprintf (debug, ": Success -> %d\n", v); - } - else - if (debug) - fprintf (debug, ": Fail, Conflict\n"); - } - } + /* Add each successors live on entry to this bock live on exit. */ + FOR_EACH_EDGE (e, ei, bb->succs) + if (e->dest != EXIT_BLOCK_PTR) + bitmap_ior_into (liveinfo->liveout[bb->index], + live_on_entry (liveinfo, e->dest)); } } -/* Send debug info for coalesce list CL to file F. */ +/* Given partition map MAP, calculate all the live on entry bitmaps for + each partition. Return a new live info object. */ -void -dump_coalesce_list (FILE *f, coalesce_list_p cl) +tree_live_info_p +calculate_live_ranges (var_map map) { - partition_pair_p node; - int x, num; tree var; + unsigned i; + tree_live_info_p live; - if (cl->add_mode) - { - fprintf (f, "Coalesce List:\n"); - num = num_var_partitions (cl->map); - for (x = 0; x < num; x++) - { - node = cl->list[x]; - if (node) - { - fprintf (f, "["); - print_generic_expr (f, partition_to_var (cl->map, x), TDF_SLIM); - fprintf (f, "] - "); - for ( ; node; node = node->next) - { - var = partition_to_var (cl->map, node->second_partition); - print_generic_expr (f, var, TDF_SLIM); - fprintf (f, "(%1d), ", node->cost); - } - fprintf (f, "\n"); - } - } - } - else + live = new_tree_live_info (map); + for (i = 0; i < num_var_partitions (map); i++) { - fprintf (f, "Sorted Coalesce list:\n"); - for (node = cl->list[0]; node; node = node->next) - { - fprintf (f, "(%d) ", node->cost); - var = partition_to_var (cl->map, node->first_partition); - print_generic_expr (f, var, TDF_SLIM); - fprintf (f, " : "); - var = partition_to_var (cl->map, node->second_partition); - print_generic_expr (f, var, TDF_SLIM); - fprintf (f, "\n"); - } + var = partition_to_var (map, i); + if (var != NULL_TREE) + set_var_live_on_entry (var, live); } -} - - -/* Output tree_partition_associator object TPA to file F.. */ -void -tpa_dump (FILE *f, tpa_p tpa) -{ - int x, i; - - if (!tpa) - return; - - for (x = 0; x < tpa_num_trees (tpa); x++) - { - print_generic_expr (f, tpa_tree (tpa, x), TDF_SLIM); - fprintf (f, " : ("); - for (i = tpa_first_partition (tpa, x); - i != TPA_NONE; - i = tpa_next_partition (tpa, i)) - { - fprintf (f, "(%d)",i); - print_generic_expr (f, partition_to_var (tpa->map, i), TDF_SLIM); - fprintf (f, " "); + live_worklist (live); #ifdef ENABLE_CHECKING - if (tpa_find_tree (tpa, i) != x) - fprintf (f, "**find tree incorrectly set** "); + verify_live_on_entry (live); #endif - } - fprintf (f, ")\n"); - } - fflush (f); + calculate_live_on_exit (live); + return live; } @@ -1723,8 +966,8 @@ dump_var_map (FILE *f, var_map map) for (x = 0; x < map->num_partitions; x++) { - if (map->compact_to_partition != NULL) - p = map->compact_to_partition[x]; + if (map->view_to_partition != NULL) + p = map->view_to_partition[x]; else p = x; @@ -1732,11 +975,11 @@ 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) - p = map->partition_to_compact[p]; + if (map->partition_to_view) + p = map->partition_to_view[p]; if (p == (int)x) { if (t++ == 0) @@ -1761,21 +1004,19 @@ 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) { FOR_EACH_BB (bb) { fprintf (f, "\nLive on entry to BB%d : ", bb->index); - for (i = 0; i < num_var_partitions (map); i++) + EXECUTE_IF_SET_IN_BITMAP (live->livein[bb->index], 0, i, bi) { - if (bitmap_bit_p (live_entry_blocks (live, i), bb->index)) - { - print_generic_expr (f, partition_to_var (map, i), TDF_SLIM); - fprintf (f, " "); - } + print_generic_expr (f, partition_to_var (map, i), TDF_SLIM); + fprintf (f, " "); } fprintf (f, "\n"); } @@ -1786,104 +1027,129 @@ 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 +/* Verify that SSA_VAR is a non-virtual SSA_NAME. */ 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))) { + 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"); + } +} - /* 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); +/* Verify that the info in LIVE matches the current cfg. */ - if (TREE_CODE (arg) != SSA_NAME) - continue; - if (!bitmap_bit_p (vars, - var_ann (SSA_NAME_VAR (arg))->uid)) - continue; +static void +verify_live_on_entry (tree_live_info_p live) +{ + unsigned i; + tree var; + tree phi, stmt; + basic_block bb; + edge e; + int num; + edge_iterator ei; + var_map map = live->map; - register_ssa_partition (map, arg, 1); - } - } - } - } + /* Check for live on entry partitions and report those with a DEF in + the program. This will typically mean an optimization has done + something wrong. */ + bb = ENTRY_BLOCK_PTR; + num = 0; + FOR_EACH_EDGE (e, ei, bb->succs) + { + int entry_block = e->dest->index; + if (e->dest == EXIT_BLOCK_PTR) + continue; + for (i = 0; i < (unsigned)num_var_partitions (map); i++) + { + basic_block tmp; + tree d; + bitmap loe; + var = partition_to_var (map, i); + stmt = SSA_NAME_DEF_STMT (var); + tmp = bb_for_stmt (stmt); + d = gimple_default_def (cfun, SSA_NAME_VAR (var)); - /* 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)) + loe = live_on_entry (live, e->dest); + if (loe && bitmap_bit_p (loe, i)) { - 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++) + if (!IS_EMPTY_STMT (stmt)) { - 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); + num++; + print_generic_expr (stderr, var, TDF_SLIM); + fprintf (stderr, " is defined "); + if (tmp) + fprintf (stderr, " in BB%d, ", tmp->index); + fprintf (stderr, "by:\n"); + print_generic_expr (stderr, stmt, TDF_SLIM); + fprintf (stderr, "\nIt is also live-on-entry to entry BB %d", + entry_block); + fprintf (stderr, " So it appears to have multiple defs.\n"); } - - 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); + else + { + if (d != var) + { + num++; + print_generic_expr (stderr, var, TDF_SLIM); + fprintf (stderr, " is live-on-entry to BB%d ",entry_block); + if (d) + { + fprintf (stderr, " but is not the default def of "); + print_generic_expr (stderr, d, TDF_SLIM); + fprintf (stderr, "\n"); + } + else + fprintf (stderr, " and there is no default def.\n"); + } } } + else + if (d == var) + { + /* The only way this var shouldn't be marked live on entry is + if it occurs in a PHI argument of the block. */ + int z, ok = 0; + for (phi = phi_nodes (e->dest); + phi && !ok; + phi = PHI_CHAIN (phi)) + { + for (z = 0; z < PHI_NUM_ARGS (phi); z++) + if (var == PHI_ARG_DEF (phi, z)) + { + ok = 1; + break; + } + } + if (ok) + continue; + num++; + print_generic_expr (stderr, var, TDF_SLIM); + fprintf (stderr, " is not marked live-on-entry to entry BB%d ", + entry_block); + fprintf (stderr, "but it is a default def so it should be.\n"); + } } } + gcc_assert (num <= 0); } - +#endif