X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Ftree-ssa-live.c;h=c3e00713b3aeb0d662afad3e5ab2c877200c35e2;hb=3ab97505ae0ccdbf56f501da272327f768217aaf;hp=47315184f9a1631c0ecfd5221f970275876988f6;hpb=32dedf8f97073ff511964dcb9e0554c19d219d1d;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/tree-ssa-live.c b/gcc/tree-ssa-live.c index 47315184f9a..c3e00713b3a 100644 --- a/gcc/tree-ssa-live.c +++ b/gcc/tree-ssa-live.c @@ -1,6 +1,6 @@ /* Liveness for SSA trees. - Copyright (C) 2003, 2004, 2005, 2007, 2008 Free Software Foundation, - Inc. + Copyright (C) 2003, 2004, 2005, 2007, 2008, 2009, 2010 + Free Software Foundation, Inc. Contributed by Andrew MacLeod This file is part of GCC. @@ -25,6 +25,8 @@ along with GCC; see the file COPYING3. If not see #include "tm.h" #include "tree.h" #include "diagnostic.h" +#include "tree-pretty-print.h" +#include "gimple-pretty-print.h" #include "bitmap.h" #include "tree-flow.h" #include "tree-dump.h" @@ -60,7 +62,7 @@ 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); @@ -136,9 +138,6 @@ init_var_map (int size) map = (var_map) xmalloc (sizeof (struct _var_map)); map->var_partition = partition_new (size); - map->partition_to_var - = (tree *)xmalloc (size * sizeof (tree)); - memset (map->partition_to_var, 0, size * sizeof (tree)); map->partition_to_view = NULL; map->view_to_partition = NULL; @@ -157,7 +156,6 @@ 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_view) free (map->partition_to_view); @@ -167,49 +165,24 @@ 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 +/* 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. */ int var_union (var_map map, tree var1, tree var2) { int p1, p2, p3; - tree root_var = NULL_TREE; - tree other_var = NULL_TREE; - /* This is independent of partition_to_view. If partition_to_view is + gcc_assert (TREE_CODE (var1) == SSA_NAME); + gcc_assert (TREE_CODE (var2) == SSA_NAME); + + /* 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_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->view_to_partition) - p1 = map->view_to_partition[p1]; - root_var = var1; - } - - if (TREE_CODE (var2) == SSA_NAME) - p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2)); - else - { - p2 = var_to_partition (map, var2); - if (map->view_to_partition) - p2 = map->view_to_partition[p2]; - - /* If there is no root_var set, or it's not a user variable, set the - root_var to this one. */ - if (!root_var || (DECL_P (root_var) && DECL_IGNORED_P (root_var))) - { - other_var = root_var; - root_var = var2; - } - else - other_var = var2; - } + p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1)); + p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2)); gcc_assert (p1 != NO_PARTITION); gcc_assert (p2 != NO_PARTITION); @@ -222,20 +195,15 @@ var_union (var_map map, tree var1, tree var2) if (map->partition_to_view) p3 = map->partition_to_view[p3]; - if (root_var) - change_partition_var (map, root_var, p3); - if (other_var) - change_partition_var (map, other_var, p3); - return p3; } - -/* Compress the partition numbers in MAP such that they fall in the range + +/* 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. + denser. This is implemented such that compaction doesn't affect partitioning. Ie., once partitions are created and possibly merged, running one @@ -249,8 +217,8 @@ var_union (var_map map, tree var1, tree var2) definitions for assignment to program variables. */ -/* 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 +/* 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 @@ -278,7 +246,9 @@ partition_view_init (var_map map) for (x = 0; x < map->partition_size; x++) { tmp = partition_find (map->var_partition, x); - if (map->partition_to_var[tmp] != NULL_TREE && !bitmap_bit_p (used, tmp)) + if (ssa_name (tmp) != NULL_TREE && is_gimple_reg (ssa_name (tmp)) + && (!has_zero_uses (ssa_name (tmp)) + || !SSA_NAME_IS_DEFAULT_DEF (ssa_name (tmp)))) bitmap_set_bit (used, tmp); } @@ -288,16 +258,15 @@ partition_view_init (var_map map) /* This routine will finalize the view data for MAP based on the partitions - set in SELECTED. This is either the same bitmap returned from + 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 +static void partition_view_fini (var_map map, bitmap selected) { bitmap_iterator bi; unsigned count, i, x, limit; - tree var; gcc_assert (selected); @@ -317,11 +286,6 @@ partition_view_fini (var_map map, bitmap selected) { 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, i); i++; } gcc_assert (i == count); @@ -332,7 +296,7 @@ partition_view_fini (var_map map, bitmap selected) } -/* Create a partition view which includes all the used partitions in MAP. If +/* 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 @@ -350,8 +314,8 @@ partition_view_normal (var_map map, bool want_bases) } -/* 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 +/* 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 @@ -379,25 +343,6 @@ partition_view_bitmap (var_map map, bitmap only, bool want_bases) } -/* This function is used to change the representative variable in MAP for VAR's - 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; - - gcc_assert (TREE_CODE (var) != SSA_NAME); - - ann = var_ann (var); - ann->out_of_ssa_tag = 1; - VAR_ANN_PARTITION (ann) = part; - if (map->view_to_partition) - map->partition_to_var[map->view_to_partition[part]] = var; -} - - static inline void mark_all_vars_used (tree *, void *data); /* Helper function for mark_all_vars_used, called via walk_tree. */ @@ -460,7 +405,7 @@ mark_scope_block_unused (tree scope) } /* Look if the block is dead (by possibly eliminating its dead subblocks) - and return true if so. + and return true if so. Block is declared dead if: 1) No statements are associated with it. 2) Declares no live variables @@ -485,10 +430,24 @@ remove_unused_scope_block_p (tree scope) next = &TREE_CHAIN (*t); /* Debug info of nested function refers to the block of the - function. */ + function. We might stil call it even if all statements + of function it was nested into was elliminated. + + TODO: We can actually look into cgraph to see if function + will be output to file. */ if (TREE_CODE (*t) == FUNCTION_DECL) unused = false; + /* If a decl has a value expr, we need to instantiate it + regardless of debug info generation, to avoid codegen + differences in memory overlap tests. update_equiv_regs() may + indirectly call validate_equiv_mem() to test whether a + SET_DEST overlaps with others, and if the value expr changes + by virtual register instantiation, we may get end up with + different results. */ + else if (TREE_CODE (*t) == VAR_DECL && DECL_HAS_VALUE_EXPR_P (*t)) + unused = false; + /* Remove everything we don't generate debug info for. */ else if (DECL_IGNORED_P (*t)) { @@ -506,15 +465,20 @@ remove_unused_scope_block_p (tree scope) /* 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; + a lot of memory. + For sake of -g3, we keep around those vars but we don't count this as + use of block, so innermost block with no used vars and no instructions + can be considered dead. We only want to keep around blocks user can + breakpoint into and ask about value of optimized out variables. + + Similarly we need to keep around types at least until all variables of + all nested blocks are gone. We track no information on whether given + type is used or not. */ + + else if (debug_info_level == DINFO_LEVEL_NORMAL + || debug_info_level == DINFO_LEVEL_VERBOSE) + ; else { *t = TREE_CHAIN (*t); @@ -529,45 +493,78 @@ remove_unused_scope_block_p (tree scope) { tree next = BLOCK_CHAIN (*t); tree supercontext = BLOCK_SUPERCONTEXT (*t); + *t = BLOCK_SUBBLOCKS (*t); - gcc_assert (!BLOCK_CHAIN (*t)); + while (BLOCK_CHAIN (*t)) + { + BLOCK_SUPERCONTEXT (*t) = supercontext; + t = &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); - } + *t = BLOCK_CHAIN (*t); } else { t = &BLOCK_CHAIN (*t); nsubblocks ++; } + + + if (!unused) + ; /* Outer scope is always used. */ - if (!BLOCK_SUPERCONTEXT (scope) - || TREE_CODE (BLOCK_SUPERCONTEXT (scope)) == FUNCTION_DECL) + else 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) + /* Innermost blocks with no live variables nor statements can be always + eliminated. */ + else if (!nsubblocks) + ; + /* For terse debug info we can eliminate info on unused variables. */ + else if (debug_info_level == DINFO_LEVEL_NONE + || debug_info_level == DINFO_LEVEL_TERSE) + { + /* Even for -g0/-g1 don't prune outer scopes from artificial + functions, otherwise diagnostics using tree_nonartificial_location + will not be emitted properly. */ + if (inlined_function_outer_scope_p (scope)) + { + tree ao = scope; + + while (ao + && TREE_CODE (ao) == BLOCK + && BLOCK_ABSTRACT_ORIGIN (ao) != ao) + ao = BLOCK_ABSTRACT_ORIGIN (ao); + if (ao + && TREE_CODE (ao) == FUNCTION_DECL + && DECL_DECLARED_INLINE_P (ao) + && lookup_attribute ("artificial", DECL_ATTRIBUTES (ao))) + unused = false; + } + } + else if (BLOCK_VARS (scope) || BLOCK_NUM_NONLOCALIZED_VARS (scope)) 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))))))) + /* See if this block is important for representation of inlined function. + Inlined functions are always represented by block with + block_ultimate_origin being set to FUNCTION_DECL and DECL_SOURCE_LOCATION + set... */ + else if (inlined_function_outer_scope_p (scope)) unused = false; + else + /* Verfify that only blocks with source location set + are entry points to the inlined functions. */ + gcc_assert (BLOCK_SOURCE_LOCATION (scope) == UNKNOWN_LOCATION); + + TREE_USED (scope) = !unused; return unused; } -/* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be +/* 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 @@ -577,6 +574,90 @@ mark_all_vars_used (tree *expr_p, void *data) } +/* Dump scope blocks starting at SCOPE to FILE. INDENT is the + indentation level and FLAGS is as in print_generic_expr. */ + +static void +dump_scope_block (FILE *file, int indent, tree scope, int flags) +{ + tree var, t; + unsigned int i; + + fprintf (file, "\n%*s{ Scope block #%i%s%s",indent, "" , BLOCK_NUMBER (scope), + TREE_USED (scope) ? "" : " (unused)", + BLOCK_ABSTRACT (scope) ? " (abstract)": ""); + if (BLOCK_SOURCE_LOCATION (scope) != UNKNOWN_LOCATION) + { + expanded_location s = expand_location (BLOCK_SOURCE_LOCATION (scope)); + fprintf (file, " %s:%i", s.file, s.line); + } + if (BLOCK_ABSTRACT_ORIGIN (scope)) + { + tree origin = block_ultimate_origin (scope); + if (origin) + { + fprintf (file, " Originating from :"); + if (DECL_P (origin)) + print_generic_decl (file, origin, flags); + else + fprintf (file, "#%i", BLOCK_NUMBER (origin)); + } + } + fprintf (file, " \n"); + for (var = BLOCK_VARS (scope); var; var = TREE_CHAIN (var)) + { + bool used = false; + var_ann_t ann; + + if ((ann = var_ann (var)) + && ann->used) + used = true; + + fprintf (file, "%*s",indent, ""); + print_generic_decl (file, var, flags); + fprintf (file, "%s\n", used ? "" : " (unused)"); + } + for (i = 0; i < BLOCK_NUM_NONLOCALIZED_VARS (scope); i++) + { + fprintf (file, "%*s",indent, ""); + print_generic_decl (file, BLOCK_NONLOCALIZED_VAR (scope, i), + flags); + fprintf (file, " (nonlocalized)\n"); + } + for (t = BLOCK_SUBBLOCKS (scope); t ; t = BLOCK_CHAIN (t)) + dump_scope_block (file, indent + 2, t, flags); + fprintf (file, "\n%*s}\n",indent, ""); +} + +/* Dump the tree of lexical scopes starting at SCOPE to stderr. FLAGS + is as in print_generic_expr. */ + +void +debug_scope_block (tree scope, int flags) +{ + dump_scope_block (stderr, 0, scope, flags); +} + + +/* Dump the tree of lexical scopes of current_function_decl to FILE. + FLAGS is as in print_generic_expr. */ + +void +dump_scope_blocks (FILE *file, int flags) +{ + dump_scope_block (file, 0, DECL_INITIAL (current_function_decl), flags); +} + + +/* Dump the tree of lexical scopes of current_function_decl to stderr. + FLAGS is as in print_generic_expr. */ + +void +debug_scope_blocks (int flags) +{ + dump_scope_blocks (stderr, flags); +} + /* Remove local variables that are not referenced in the IL. */ void @@ -588,8 +669,13 @@ remove_unused_locals (void) var_ann_t ann; bitmap global_unused_vars = NULL; - if (optimize) - mark_scope_block_unused (DECL_INITIAL (current_function_decl)); + /* Removing declarations from lexical blocks when not optimizing is + not only a waste of time, it actually causes differences in stack + layout. */ + if (!optimize) + return; + + mark_scope_block_unused (DECL_INITIAL (current_function_decl)); /* Assume all locals are unused. */ FOR_EACH_REFERENCED_VAR (t, rvi) @@ -609,6 +695,9 @@ remove_unused_locals (void) gimple stmt = gsi_stmt (gsi); tree b = gimple_block (stmt); + if (is_gimple_debug (stmt)) + continue; + if (b) TREE_USED (b) = true; @@ -642,6 +731,8 @@ remove_unused_locals (void) TREE_USED (e->goto_block) = true; } + cfun->has_local_explicit_reg_vars = false; + /* Remove unmarked local vars from local_decls. */ for (cell = &cfun->local_decls; *cell; ) { @@ -663,6 +754,10 @@ remove_unused_locals (void) continue; } } + else if (TREE_CODE (var) == VAR_DECL + && DECL_HARD_REGISTER (var) + && !is_global_var (var)) + cfun->has_local_explicit_reg_vars = true; cell = &TREE_CHAIN (*cell); } @@ -686,8 +781,7 @@ remove_unused_locals (void) if (TREE_CODE (var) == VAR_DECL && is_global_var (var) - && bitmap_bit_p (global_unused_vars, DECL_UID (var)) - && (optimize || DECL_ARTIFICIAL (var))) + && bitmap_bit_p (global_unused_vars, DECL_UID (var))) *cell = TREE_CHAIN (*cell); else cell = &TREE_CHAIN (*cell); @@ -702,16 +796,18 @@ remove_unused_locals (void) 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) - && (optimize || DECL_ARTIFICIAL (t))) + && !ann->is_heapvar + && !TREE_ADDRESSABLE (t)) remove_referenced_var (t); - if (optimize) - remove_unused_scope_block_p (DECL_INITIAL (current_function_decl)); + remove_unused_scope_block_p (DECL_INITIAL (current_function_decl)); + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Scope blocks after cleanups:\n"); + dump_scope_blocks (dump_file, dump_flags); + } } @@ -745,7 +841,7 @@ new_tree_live_info (var_map map) /* Free storage for live range info object LIVE. */ -void +void delete_tree_live_info (tree_live_info_p live) { int x; @@ -765,12 +861,12 @@ delete_tree_live_info (tree_live_info_p live) } -/* Visit basic block BB and propagate any required live on entry bits from - LIVE into the predecessors. VISITED is the bitmap of visited blocks. +/* 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 +static void loe_visit_block (tree_live_info_p live, basic_block bb, sbitmap visited, bitmap tmp) { @@ -790,12 +886,12 @@ loe_visit_block (tree_live_info_p live, basic_block bb, sbitmap visited, 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. + 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 + /* 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); @@ -808,7 +904,7 @@ loe_visit_block (tree_live_info_p live, basic_block bb, sbitmap visited, } -/* Using LIVE, fill in all the live-on-entry blocks between the defs and uses +/* Using LIVE, fill in all the live-on-entry blocks between the defs and uses of all the variables. */ static void @@ -887,13 +983,15 @@ set_var_live_on_entry (tree ssa_name, tree_live_info_p live) add_block = e->src; } } + else if (is_gimple_debug (use_stmt)) + continue; else { /* If its not defined in this block, its live on entry. */ basic_block use_bb = gimple_bb (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) @@ -934,7 +1032,7 @@ calculate_live_on_exit (tree_live_info_p liveinfo) { gimple phi = gsi_stmt (gsi); for (i = 0; i < gimple_phi_num_args (phi); i++) - { + { tree t = PHI_ARG_DEF (phi, i); int p; @@ -959,10 +1057,10 @@ calculate_live_on_exit (tree_live_info_p liveinfo) } -/* Given partition map MAP, calculate all the live on entry bitmaps for +/* Given partition map MAP, calculate all the live on entry bitmaps for each partition. Return a new live info object. */ -tree_live_info_p +tree_live_info_p calculate_live_ranges (var_map map) { tree var; @@ -1006,7 +1104,7 @@ dump_var_map (FILE *f, var_map map) else p = x; - if (map->partition_to_var[p] == NULL_TREE) + if (ssa_name (p) == NULL_TREE) continue; t = 0; @@ -1136,7 +1234,7 @@ verify_live_on_entry (tree_live_info_p live) fprintf (stderr, " in BB%d, ", tmp->index); fprintf (stderr, "by:\n"); print_gimple_stmt (stderr, stmt, 0, TDF_SLIM); - fprintf (stderr, "\nIt is also live-on-entry to entry BB %d", + fprintf (stderr, "\nIt is also live-on-entry to entry BB %d", entry_block); fprintf (stderr, " So it appears to have multiple defs.\n"); } @@ -1162,7 +1260,7 @@ verify_live_on_entry (tree_live_info_p live) else if (d == var) { - /* The only way this var shouldn't be marked live on entry is + /* The only way this var shouldn't be marked live on entry is if it occurs in a PHI argument of the block. */ size_t z; bool ok = false; @@ -1183,7 +1281,7 @@ verify_live_on_entry (tree_live_info_p live) continue; num++; print_generic_expr (stderr, var, TDF_SLIM); - fprintf (stderr, " is not marked live-on-entry to entry BB%d ", + 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"); }