/* Liveness for SSA trees.
- Copyright (C) 2003, 2004, 2005, 2007, 2008, 2009, 2010, 2011
- Free Software Foundation, Inc.
+ Copyright (C) 2003-2020 Free Software Foundation, Inc.
Contributed by Andrew MacLeod <amacleod@redhat.com>
This file is part of GCC.
#include "config.h"
#include "system.h"
#include "coretypes.h"
-#include "tm.h"
+#include "backend.h"
+#include "rtl.h"
#include "tree.h"
-#include "gimple-pretty-print.h"
-#include "bitmap.h"
-#include "tree-flow.h"
+#include "gimple.h"
#include "timevar.h"
+#include "ssa.h"
+#include "cgraph.h"
+#include "gimple-pretty-print.h"
+#include "diagnostic-core.h"
+#include "gimple-iterator.h"
+#include "tree-dfa.h"
#include "dumpfile.h"
#include "tree-ssa-live.h"
-#include "diagnostic-core.h"
#include "debug.h"
-#include "flags.h"
-#include "gimple.h"
+#include "tree-ssa.h"
+#include "ipa-utils.h"
+#include "cfgloop.h"
+#include "stringpool.h"
+#include "attribs.h"
+#include "optinfo.h"
+#include "gimple-walk.h"
+#include "cfganal.h"
-#ifdef ENABLE_CHECKING
-static void verify_live_on_entry (tree_live_info_p);
-#endif
+static void verify_live_on_entry (tree_live_info_p);
/* VARMAP maintains a mapping from SSA version number to real variables.
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;
- tree var;
- htab_t tree_to_index;
- struct tree_int_map *m, *mapstorage;
-
- num_part = num_var_partitions (map);
- tree_to_index = htab_create (num_part, tree_map_base_hash,
- tree_int_map_eq, NULL);
- /* We can have at most num_part entries in the hash tables, so it's
- enough to allocate so many map elements once, saving some malloc
- calls. */
- mapstorage = m = XNEWVEC (struct tree_int_map, num_part);
-
- /* If a base table already exists, clear it, otherwise create it. */
- free (map->partition_to_base_index);
- map->partition_to_base_index = (int *) xmalloc (sizeof (int) * num_part);
-
- /* Build the base variable list, and point partitions at their bases. */
- for (x = 0; x < num_part; x++)
- {
- struct tree_int_map **slot;
- unsigned baseindex;
- var = partition_to_var (map, x);
- if (SSA_NAME_VAR (var))
- m->base.from = SSA_NAME_VAR (var);
- else
- /* This restricts what anonymous SSA names we can coalesce
- as it restricts the sets we compute conflicts for.
- Using TREE_TYPE to generate sets is the easies as
- type equivalency also holds for SSA names with the same
- underlying decl. */
- m->base.from = TREE_TYPE (var);
- /* If base variable hasn't been seen, set it up. */
- slot = (struct tree_int_map **) htab_find_slot (tree_to_index,
- m, INSERT);
- if (!*slot)
- {
- baseindex = m - mapstorage;
- m->to = baseindex;
- *slot = m;
- m++;
- }
- else
- baseindex = (*slot)->to;
- map->partition_to_base_index[x] = baseindex;
- }
-
- map->num_basevars = m - mapstorage;
-
- free (mapstorage);
- htab_delete (tree_to_index);
-}
-
-
/* Remove the base table in MAP. */
static void
map->num_basevars = 0;
}
}
-/* Create a variable partition map of SIZE, initialize and return it. */
+/* Create a variable partition map of SIZE for region, initialize and return
+ it. Region is a loop if LOOP is non-NULL, otherwise is the current
+ function. */
var_map
-init_var_map (int size)
+init_var_map (int size, class loop *loop)
{
var_map map;
map->partition_size = size;
map->num_basevars = 0;
map->partition_to_base_index = NULL;
+ map->vec_bbs = vNULL;
+ if (loop)
+ {
+ map->bmp_bbs = BITMAP_ALLOC (NULL);
+ map->outofssa_p = false;
+ basic_block *bbs = get_loop_body_in_dom_order (loop);
+ for (unsigned i = 0; i < loop->num_nodes; ++i)
+ {
+ bitmap_set_bit (map->bmp_bbs, bbs[i]->index);
+ map->vec_bbs.safe_push (bbs[i]);
+ }
+ free (bbs);
+ }
+ else
+ {
+ map->bmp_bbs = NULL;
+ map->outofssa_p = true;
+ basic_block bb;
+ FOR_EACH_BB_FN (bb, cfun)
+ map->vec_bbs.safe_push (bb);
+ }
return map;
}
partition_delete (map->var_partition);
free (map->partition_to_view);
free (map->view_to_partition);
+ if (map->bmp_bbs)
+ BITMAP_FREE (map->bmp_bbs);
+ map->vec_bbs.release ();
free (map);
}
for (x = 0; x < map->partition_size; x++)
{
tmp = partition_find (map->var_partition, x);
- if (ssa_name (tmp) != NULL_TREE && is_gimple_reg (ssa_name (tmp))
+ if (ssa_name (tmp) != NULL_TREE && !virtual_operand_p (ssa_name (tmp))
&& (!has_zero_uses (ssa_name (tmp))
- || !SSA_NAME_IS_DEFAULT_DEF (ssa_name (tmp))))
+ || !SSA_NAME_IS_DEFAULT_DEF (ssa_name (tmp))
+ || (SSA_NAME_VAR (ssa_name (tmp))
+ && !VAR_P (SSA_NAME_VAR (ssa_name (tmp))))))
bitmap_set_bit (used, tmp);
}
}
-/* Create a partition view which includes all the used partitions in MAP. If
- WANT_BASES is true, create the base variable map as well. */
+/* Create a partition view which includes all the used partitions in MAP. */
-extern void
-partition_view_normal (var_map map, bool want_bases)
+void
+partition_view_normal (var_map map)
{
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);
+ var_map_base_fini (map);
}
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)
+void
+partition_view_bitmap (var_map map, bitmap only)
{
bitmap used;
bitmap new_partitions = BITMAP_ALLOC (NULL);
}
partition_view_fini (map, new_partitions);
- BITMAP_FREE (used);
- if (want_bases)
- var_map_base_init (map);
- else
- var_map_base_fini (map);
+ var_map_base_fini (map);
}
/* Only need to mark VAR_DECLS; parameters and return results are not
eliminated as unused. */
- if (TREE_CODE (t) == VAR_DECL)
+ if (VAR_P (t))
{
/* When a global var becomes used for the first time also walk its
initializer (non global ones don't have any). */
- if (set_is_used (t) && is_global_var (t))
+ if (set_is_used (t) && is_global_var (t)
+ && DECL_CONTEXT (t) == current_function_decl)
mark_all_vars_used (&DECL_INITIAL (t));
}
/* remove_unused_scope_block_p requires information about labels
done by the inliner. */
static bool
-remove_unused_scope_block_p (tree scope)
+remove_unused_scope_block_p (tree scope, bool in_ctor_dtor_block)
{
tree *t, *next;
bool unused = !TREE_USED (scope);
int nsubblocks = 0;
+ /* For ipa-polymorphic-call.c purposes, preserve blocks:
+ 1) with BLOCK_ABSTRACT_ORIGIN of a ctor/dtor or their clones */
+ if (inlined_polymorphic_ctor_dtor_block_p (scope, true))
+ {
+ in_ctor_dtor_block = true;
+ unused = false;
+ }
+ /* 2) inside such blocks, the outermost block with block_ultimate_origin
+ being a FUNCTION_DECL. */
+ else if (in_ctor_dtor_block)
+ {
+ tree fn = block_ultimate_origin (scope);
+ if (fn && TREE_CODE (fn) == FUNCTION_DECL)
+ {
+ in_ctor_dtor_block = false;
+ unused = false;
+ }
+ }
+
for (t = &BLOCK_VARS (scope); *t; t = next)
{
next = &DECL_CHAIN (*t);
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))
+ else if (VAR_P (*t) && DECL_HAS_VALUE_EXPR_P (*t))
unused = false;
/* Remove everything we don't generate debug info for. */
}
for (t = &BLOCK_SUBBLOCKS (scope); *t ;)
- if (remove_unused_scope_block_p (*t))
+ if (remove_unused_scope_block_p (*t, in_ctor_dtor_block))
{
if (BLOCK_SUBBLOCKS (*t))
{
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)
+ /* When not generating debug info we can eliminate info on unused
+ variables. */
+ else if (!flag_auto_profile && debug_info_level == DINFO_LEVEL_NONE
+ && !optinfo_wants_inlining_info_p ())
{
- /* Even for -g0/-g1 don't prune outer scopes from artificial
+ /* Even for -g0 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);
+ tree ao = BLOCK_ORIGIN (scope);
if (ao
&& TREE_CODE (ao) == FUNCTION_DECL
&& DECL_DECLARED_INLINE_P (ao)
}
else if (BLOCK_VARS (scope) || BLOCK_NUM_NONLOCALIZED_VARS (scope))
unused = false;
- /* 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... */
+ /* 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, unless they expand to nothing... */
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);
+ gcc_assert (LOCATION_LOCUS (BLOCK_SOURCE_LOCATION (scope))
+ == UNKNOWN_LOCATION);
TREE_USED (scope) = !unused;
return unused;
walk_tree (expr_p, mark_all_vars_used_1, NULL, NULL);
}
+/* Helper function for clear_unused_block_pointer, called via walk_tree. */
+
+static tree
+clear_unused_block_pointer_1 (tree *tp, int *, void *)
+{
+ if (EXPR_P (*tp) && TREE_BLOCK (*tp)
+ && !TREE_USED (TREE_BLOCK (*tp)))
+ TREE_SET_BLOCK (*tp, NULL);
+ return NULL_TREE;
+}
+
+/* Set all block pointer in debug or clobber stmt to NULL if the block
+ is unused, so that they will not be streamed out. */
+
+static void
+clear_unused_block_pointer (void)
+{
+ basic_block bb;
+ gimple_stmt_iterator gsi;
+
+ FOR_EACH_BB_FN (bb, cfun)
+ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ unsigned i;
+ tree b;
+ gimple *stmt;
+
+ next:
+ stmt = gsi_stmt (gsi);
+ if (!is_gimple_debug (stmt) && !gimple_clobber_p (stmt))
+ continue;
+ b = gimple_block (stmt);
+ if (b && !TREE_USED (b))
+ {
+ /* Elide debug marker stmts that have an associated BLOCK from an
+ inline instance removed with also the outermost scope BLOCK of
+ said inline instance removed. If the outermost scope BLOCK of
+ said inline instance is preserved use that in place of the
+ removed BLOCK. That keeps the marker associated to the correct
+ inline instance (or no inline instance in case it was not from
+ an inline instance). */
+ if (gimple_debug_nonbind_marker_p (stmt)
+ && BLOCK_ABSTRACT_ORIGIN (b))
+ {
+ while (TREE_CODE (b) == BLOCK
+ && !inlined_function_outer_scope_p (b))
+ b = BLOCK_SUPERCONTEXT (b);
+ if (TREE_CODE (b) == BLOCK)
+ {
+ if (TREE_USED (b))
+ {
+ gimple_set_block (stmt, b);
+ continue;
+ }
+ gsi_remove (&gsi, true);
+ if (gsi_end_p (gsi))
+ break;
+ goto next;
+ }
+ }
+ gimple_set_block (stmt, NULL);
+ }
+ for (i = 0; i < gimple_num_ops (stmt); i++)
+ walk_tree (gimple_op_ptr (stmt, i), clear_unused_block_pointer_1,
+ NULL, NULL);
+ }
+}
/* 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)
+dump_scope_block (FILE *file, int indent, tree scope, dump_flags_t 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)
+ fprintf (file, "\n%*s{ Scope block #%i%s",indent, "" , BLOCK_NUMBER (scope),
+ TREE_USED (scope) ? "" : " (unused)");
+ if (LOCATION_LOCUS (BLOCK_SOURCE_LOCATION (scope)) != UNKNOWN_LOCATION)
{
expanded_location s = expand_location (BLOCK_SOURCE_LOCATION (scope));
fprintf (file, " %s:%i", s.file, s.line);
fprintf (file, "#%i", BLOCK_NUMBER (origin));
}
}
+ if (BLOCK_FRAGMENT_ORIGIN (scope))
+ fprintf (file, " Fragment of : #%i",
+ BLOCK_NUMBER (BLOCK_FRAGMENT_ORIGIN (scope)));
+ else if (BLOCK_FRAGMENT_CHAIN (scope))
+ {
+ fprintf (file, " Fragment chain :");
+ for (t = BLOCK_FRAGMENT_CHAIN (scope); t ;
+ t = BLOCK_FRAGMENT_CHAIN (t))
+ fprintf (file, " #%i", BLOCK_NUMBER (t));
+ }
fprintf (file, " \n");
for (var = BLOCK_VARS (scope); var; var = DECL_CHAIN (var))
{
is as in print_generic_expr. */
DEBUG_FUNCTION void
-debug_scope_block (tree scope, int flags)
+debug_scope_block (tree scope, dump_flags_t flags)
{
dump_scope_block (stderr, 0, scope, flags);
}
FLAGS is as in print_generic_expr. */
void
-dump_scope_blocks (FILE *file, int flags)
+dump_scope_blocks (FILE *file, dump_flags_t flags)
{
dump_scope_block (file, 0, DECL_INITIAL (current_function_decl), flags);
}
FLAGS is as in print_generic_expr. */
DEBUG_FUNCTION void
-debug_scope_blocks (int flags)
+debug_scope_blocks (dump_flags_t flags)
{
dump_scope_blocks (stderr, flags);
}
mark_scope_block_unused (DECL_INITIAL (current_function_decl));
usedvars = BITMAP_ALLOC (NULL);
+ auto_bitmap useddebug;
/* Walk the CFG marking all referenced symbols. */
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, cfun)
{
gimple_stmt_iterator gsi;
size_t i;
/* Walk the statements. */
for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
{
- gimple stmt = gsi_stmt (gsi);
+ gimple *stmt = gsi_stmt (gsi);
tree b = gimple_block (stmt);
+ /* If we wanted to mark the block referenced by the inline
+ entry point marker as used, this would be a good spot to
+ do it. If the block is not otherwise used, the stmt will
+ be cleaned up in clean_unused_block_pointer. */
if (is_gimple_debug (stmt))
- continue;
+ {
+ if (gimple_debug_bind_p (stmt))
+ {
+ tree var = gimple_debug_bind_get_var (stmt);
+ if (VAR_P (var))
+ {
+ if (!gimple_debug_bind_get_value (stmt))
+ /* Run the 2nd phase. */
+ have_local_clobbers = true;
+ else
+ bitmap_set_bit (useddebug, DECL_UID (var));
+ }
+ }
+ continue;
+ }
if (gimple_clobber_p (stmt))
{
mark_all_vars_used (gimple_op_ptr (gsi_stmt (gsi), i));
}
- for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ for (gphi_iterator gpi = gsi_start_phis (bb);
+ !gsi_end_p (gpi);
+ gsi_next (&gpi))
{
use_operand_p arg_p;
ssa_op_iter i;
tree def;
- gimple phi = gsi_stmt (gsi);
+ gphi *phi = gpi.phi ();
- if (!is_gimple_reg (gimple_phi_result (phi)))
+ if (virtual_operand_p (gimple_phi_result (phi)))
continue;
def = gimple_phi_result (phi);
FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_ALL_USES)
{
tree arg = USE_FROM_PTR (arg_p);
+ int index = PHI_ARG_INDEX_FROM_USE (arg_p);
+ tree block =
+ LOCATION_BLOCK (gimple_phi_arg_location (phi, index));
+ if (block != NULL)
+ TREE_USED (block) = true;
mark_all_vars_used (&arg);
}
}
FOR_EACH_EDGE (e, ei, bb->succs)
- if (e->goto_locus)
- TREE_USED (e->goto_block) = true;
+ if (LOCATION_BLOCK (e->goto_locus) != NULL)
+ TREE_USED (LOCATION_BLOCK (e->goto_locus)) = true;
}
/* We do a two-pass approach about the out-of-scope clobbers. We want
ignores them, and the second pass (if there were any) tries to remove
them. */
if (have_local_clobbers)
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, cfun)
{
gimple_stmt_iterator gsi;
for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
{
- gimple stmt = gsi_stmt (gsi);
+ gimple *stmt = gsi_stmt (gsi);
tree b = gimple_block (stmt);
if (gimple_clobber_p (stmt))
{
tree lhs = gimple_assign_lhs (stmt);
- if (TREE_CODE (lhs) == VAR_DECL && !is_used_p (lhs))
+ tree base = get_base_address (lhs);
+ /* Remove clobbers referencing unused vars, or clobbers
+ with MEM_REF lhs referencing uninitialized pointers. */
+ if ((VAR_P (base) && !is_used_p (base))
+ || (TREE_CODE (lhs) == MEM_REF
+ && TREE_CODE (TREE_OPERAND (lhs, 0)) == SSA_NAME
+ && SSA_NAME_IS_DEFAULT_DEF (TREE_OPERAND (lhs, 0))
+ && (TREE_CODE (SSA_NAME_VAR (TREE_OPERAND (lhs, 0)))
+ != PARM_DECL)))
{
unlink_stmt_vdef (stmt);
gsi_remove (&gsi, true);
if (b)
TREE_USED (b) = true;
}
+ else if (gimple_debug_bind_p (stmt))
+ {
+ tree var = gimple_debug_bind_get_var (stmt);
+ if (VAR_P (var)
+ && !bitmap_bit_p (useddebug, DECL_UID (var))
+ && !is_used_p (var))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Dead debug bind reset to %u\n",
+ DECL_UID (var));
+ gsi_remove (&gsi, true);
+ continue;
+ }
+ }
gsi_next (&gsi);
}
}
+ if (cfun->has_simduid_loops)
+ {
+ class loop *loop;
+ FOR_EACH_LOOP (loop, 0)
+ if (loop->simduid && !is_used_p (loop->simduid))
+ loop->simduid = NULL_TREE;
+ }
+
cfun->has_local_explicit_reg_vars = false;
/* Remove unmarked local and global vars from local_decls. */
- num = VEC_length (tree, cfun->local_decls);
+ num = vec_safe_length (cfun->local_decls);
for (srcidx = 0, dstidx = 0; srcidx < num; srcidx++)
{
- var = VEC_index (tree, cfun->local_decls, srcidx);
- if (TREE_CODE (var) == VAR_DECL)
+ var = (*cfun->local_decls)[srcidx];
+ if (VAR_P (var))
{
if (!is_used_p (var))
{
continue;
}
}
- if (TREE_CODE (var) == VAR_DECL
- && DECL_HARD_REGISTER (var)
- && !is_global_var (var))
+ if (VAR_P (var) && DECL_HARD_REGISTER (var) && !is_global_var (var))
cfun->has_local_explicit_reg_vars = true;
if (srcidx != dstidx)
- VEC_replace (tree, cfun->local_decls, dstidx, var);
+ (*cfun->local_decls)[dstidx] = var;
dstidx++;
}
if (dstidx != num)
- VEC_truncate (tree, cfun->local_decls, dstidx);
+ {
+ statistics_counter_event (cfun, "unused VAR_DECLs removed", num - dstidx);
+ cfun->local_decls->truncate (dstidx);
+ }
- remove_unused_scope_block_p (DECL_INITIAL (current_function_decl));
+ remove_unused_scope_block_p (DECL_INITIAL (current_function_decl),
+ polymorphic_ctor_dtor_p (current_function_decl,
+ true) != NULL_TREE);
+ clear_unused_block_pointer ();
BITMAP_FREE (usedvars);
timevar_pop (TV_REMOVE_UNUSED);
}
-
/* Allocate and return a new live range information object base on MAP. */
static tree_live_info_p
new_tree_live_info (var_map map)
{
tree_live_info_p live;
- unsigned x;
+ basic_block bb;
- live = (tree_live_info_p) xmalloc (sizeof (struct tree_live_info_d));
+ live = XNEW (struct tree_live_info_d);
live->map = map;
- live->num_blocks = last_basic_block;
+ live->num_blocks = last_basic_block_for_fn (cfun);
- live->livein = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap));
- for (x = 0; x < (unsigned)last_basic_block; x++)
- live->livein[x] = BITMAP_ALLOC (NULL);
+ bitmap_obstack_initialize (&live->livein_obstack);
+ bitmap_obstack_initialize (&live->liveout_obstack);
- live->liveout = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap));
- for (x = 0; x < (unsigned)last_basic_block; x++)
- live->liveout[x] = BITMAP_ALLOC (NULL);
+ live->livein = XCNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
+ live->liveout = XCNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
+ for (unsigned i = 0; map->vec_bbs.iterate (i, &bb); ++i)
+ {
+ bitmap_initialize (&live->livein[bb->index], &live->livein_obstack);
+ bitmap_initialize (&live->liveout[bb->index], &live->liveout_obstack);
+ }
- live->work_stack = XNEWVEC (int, last_basic_block);
+ live->work_stack = XNEWVEC (int, last_basic_block_for_fn (cfun));
live->stack_top = live->work_stack;
live->global = BITMAP_ALLOC (NULL);
void
delete_tree_live_info (tree_live_info_p live)
{
- int x;
-
+ if (live->livein)
+ {
+ bitmap_obstack_release (&live->livein_obstack);
+ free (live->livein);
+ }
+ if (live->liveout)
+ {
+ bitmap_obstack_release (&live->liveout_obstack);
+ free (live->liveout);
+ }
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);
}
it each time. */
static void
-loe_visit_block (tree_live_info_p live, basic_block bb, sbitmap visited,
- bitmap tmp)
+loe_visit_block (tree_live_info_p live, basic_block bb, sbitmap visited)
{
edge e;
bool change;
edge_iterator ei;
basic_block pred_bb;
bitmap loe;
- gcc_assert (!TEST_BIT (visited, bb->index));
- SET_BIT (visited, bb->index);
+ gcc_checking_assert (!bitmap_bit_p (visited, bb->index));
+ bitmap_set_bit (visited, bb->index);
+
loe = live_on_entry (live, bb);
FOR_EACH_EDGE (e, ei, bb->preds)
{
pred_bb = e->src;
- if (pred_bb == ENTRY_BLOCK_PTR)
+ if (!region_contains_p (live->map, pred_bb))
continue;
- /* TMP is variables live-on-entry from BB that aren't defined in the
+ /* 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
+ being calculated.
+ 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)
+ change = bitmap_ior_and_compl_into (live_on_entry (live, pred_bb),
+ loe, &live->liveout[pred_bb->index]);
+ if (change
+ && bitmap_bit_p (visited, pred_bb->index))
{
- RESET_BIT (visited, pred_bb->index);
+ bitmap_clear_bit (visited, pred_bb->index);
*(live->stack_top)++ = pred_bb->index;
}
}
{
unsigned b;
basic_block bb;
- sbitmap visited = sbitmap_alloc (last_basic_block + 1);
- bitmap tmp = BITMAP_ALLOC (NULL);
+ auto_sbitmap visited (last_basic_block_for_fn (cfun) + 1);
- sbitmap_zero (visited);
+ bitmap_clear (visited);
- /* Visit all the blocks in reverse order and propagate live on entry values
+ /* Visit region's 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);
+ for (unsigned i = live->map->vec_bbs.length () - 1;
+ live->map->vec_bbs.iterate (i, &bb); --i)
+ loe_visit_block (live, bb, visited);
/* Process any blocks which require further iteration. */
while (live->stack_top != live->work_stack)
{
b = *--(live->stack_top);
- loe_visit_block (live, BASIC_BLOCK (b), visited, tmp);
+ loe_visit_block (live, BASIC_BLOCK_FOR_FN (cfun, b), visited);
}
-
- BITMAP_FREE (tmp);
- sbitmap_free (visited);
}
set_var_live_on_entry (tree ssa_name, tree_live_info_p live)
{
int p;
- gimple stmt;
+ gimple *stmt;
use_operand_p use;
basic_block def_bb = NULL;
imm_use_iterator imm_iter;
{
def_bb = gimple_bb (stmt);
/* Mark defs in liveout bitmap temporarily. */
- if (def_bb)
- bitmap_set_bit (live->liveout[def_bb->index], p);
+ if (def_bb && region_contains_p (live->map, def_bb))
+ bitmap_set_bit (&live->liveout[def_bb->index], p);
}
else
- def_bb = ENTRY_BLOCK_PTR;
+ def_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
+
+ /* An undefined local variable does not need to be very alive. */
+ if (ssa_undefined_value_p (ssa_name, false))
+ return;
/* 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)
{
- gimple use_stmt = USE_STMT (use);
+ gimple *use_stmt = USE_STMT (use);
basic_block add_block = NULL;
if (gimple_code (use_stmt) == GIMPLE_PHI)
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 = gimple_phi_arg_edge (use_stmt, index);
- if (e->src != ENTRY_BLOCK_PTR)
- {
- if (e->src != def_bb)
- add_block = e->src;
- }
+ edge e = gimple_phi_arg_edge (as_a <gphi *> (use_stmt), index);
+ if (e->src != def_bb && region_contains_p (live->map, e->src))
+ add_block = e->src;
}
else if (is_gimple_debug (use_stmt))
continue;
{
/* If its not defined in this block, its live on entry. */
basic_block use_bb = gimple_bb (use_stmt);
- if (use_bb != def_bb)
+ if (use_bb != def_bb && region_contains_p (live->map, use_bb))
add_block = use_bb;
}
if (add_block)
{
global = true;
- bitmap_set_bit (live->livein[add_block->index], p);
+ bitmap_set_bit (&live->livein[add_block->index], p);
}
}
/* Calculate the live on exit vectors based on the entry info in LIVEINFO. */
-void
+static void
calculate_live_on_exit (tree_live_info_p liveinfo)
{
basic_block bb;
edge_iterator ei;
/* live on entry calculations used liveout vectors for defs, clear them. */
- FOR_EACH_BB (bb)
- bitmap_clear (liveinfo->liveout[bb->index]);
+ for (unsigned i = 0; liveinfo->map->vec_bbs.iterate (i, &bb); ++i)
+ bitmap_clear (&liveinfo->liveout[bb->index]);
/* Set all the live-on-exit bits for uses in PHIs. */
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, cfun)
{
- gimple_stmt_iterator gsi;
+ gphi_iterator gsi;
size_t i;
/* Mark the PHI arguments which are live on exit to the pred block. */
for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
{
- gimple phi = gsi_stmt (gsi);
+ gphi *phi = gsi.phi ();
+ if (virtual_operand_p (gimple_phi_result (phi)))
+ continue;
for (i = 0; i < gimple_phi_num_args (phi); i++)
{
tree t = PHI_ARG_DEF (phi, i);
if (p == NO_PARTITION)
continue;
e = gimple_phi_arg_edge (phi, i);
- if (e->src != ENTRY_BLOCK_PTR)
- bitmap_set_bit (liveinfo->liveout[e->src->index], p);
+ if (region_contains_p (liveinfo->map, e->src))
+ bitmap_set_bit (&liveinfo->liveout[e->src->index], p);
}
}
+ if (!region_contains_p (liveinfo->map, bb))
+ continue;
+
/* 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],
+ if (region_contains_p (liveinfo->map, e->dest))
+ bitmap_ior_into (&liveinfo->liveout[bb->index],
live_on_entry (liveinfo, e->dest));
}
}
each partition. Return a new live info object. */
tree_live_info_p
-calculate_live_ranges (var_map map)
+calculate_live_ranges (var_map map, bool want_livein)
{
tree var;
unsigned i;
live_worklist (live);
-#ifdef ENABLE_CHECKING
- verify_live_on_entry (live);
-#endif
+ if (flag_checking)
+ verify_live_on_entry (live);
calculate_live_on_exit (live);
+
+ if (!want_livein)
+ {
+ bitmap_obstack_release (&live->livein_obstack);
+ free (live->livein);
+ live->livein = NULL;
+ }
+
return live;
}
+\f
+/* Data structure for compute_live_vars* functions. */
+
+struct compute_live_vars_data {
+ /* Vector of bitmaps for live vars indices at the end of basic blocks,
+ indexed by bb->index. ACTIVE[ENTRY_BLOCK] must be empty bitmap,
+ ACTIVE[EXIT_BLOCK] is used for STOP_AFTER. */
+ vec<bitmap_head> active;
+ /* Work bitmap of currently live variables. */
+ bitmap work;
+ /* Set of interesting variables. Variables with uids not in this
+ hash_map are not tracked. */
+ live_vars_map *vars;
+};
+
+/* Callback for walk_stmt_load_store_addr_ops. If OP is a VAR_DECL with
+ uid set in DATA->vars, enter its corresponding index into bitmap
+ DATA->work. */
+
+static bool
+compute_live_vars_visit (gimple *, tree op, tree, void *pdata)
+{
+ compute_live_vars_data *data = (compute_live_vars_data *) pdata;
+ op = get_base_address (op);
+ if (op && VAR_P (op))
+ if (unsigned int *v = data->vars->get (DECL_UID (op)))
+ bitmap_set_bit (data->work, *v);
+ return false;
+}
+
+/* Helper routine for compute_live_vars, calculating the sets of live
+ variables at the end of BB, leaving the result in DATA->work.
+ If STOP_AFTER is non-NULL, stop processing after that stmt. */
+
+static void
+compute_live_vars_1 (basic_block bb, compute_live_vars_data *data,
+ gimple *stop_after)
+{
+ edge e;
+ edge_iterator ei;
+ gimple_stmt_iterator gsi;
+ walk_stmt_load_store_addr_fn visit = compute_live_vars_visit;
+
+ bitmap_clear (data->work);
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ bitmap_ior_into (data->work, &data->active[e->src->index]);
+
+ for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ walk_stmt_load_store_addr_ops (gsi_stmt (gsi), data, NULL, NULL, visit);
+ for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ gimple *stmt = gsi_stmt (gsi);
+
+ if (gimple_clobber_p (stmt))
+ {
+ tree lhs = gimple_assign_lhs (stmt);
+ if (VAR_P (lhs))
+ if (unsigned int *v = data->vars->get (DECL_UID (lhs)))
+ bitmap_clear_bit (data->work, *v);
+ }
+ else if (!is_gimple_debug (stmt))
+ walk_stmt_load_store_addr_ops (stmt, data, visit, visit, visit);
+ if (stmt == stop_after)
+ break;
+ }
+}
+
+/* For function FN and live_vars_map (hash map from DECL_UIDs to a dense set of
+ indexes of automatic variables VARS, compute which of those variables are
+ (might be) live at the end of each basic block. */
+
+vec<bitmap_head>
+compute_live_vars (struct function *fn, live_vars_map *vars)
+{
+ vec<bitmap_head> active;
+
+ /* We approximate the live range of a stack variable by taking the first
+ mention of its name as starting point(s), and by the end-of-scope
+ death clobber added by gimplify as ending point(s) of the range.
+ This overapproximates in the case we for instance moved an address-taken
+ operation upward, without also moving a dereference to it upwards.
+ But it's conservatively correct as a variable never can hold values
+ before its name is mentioned at least once.
+
+ We then do a mostly classical bitmap liveness algorithm. */
+
+ active.create (last_basic_block_for_fn (fn));
+ active.quick_grow (last_basic_block_for_fn (fn));
+ for (int i = 0; i < last_basic_block_for_fn (fn); i++)
+ bitmap_initialize (&active[i], &bitmap_default_obstack);
+
+ bitmap work = BITMAP_ALLOC (NULL);
+
+ int *rpo = XNEWVEC (int, last_basic_block_for_fn (fn));
+ int n_bbs = pre_and_rev_post_order_compute_fn (fn, NULL, rpo, false);
+
+ bool changed = true;
+ compute_live_vars_data data = { active, work, vars };
+ while (changed)
+ {
+ int i;
+ changed = false;
+ for (i = 0; i < n_bbs; i++)
+ {
+ basic_block bb = BASIC_BLOCK_FOR_FN (fn, rpo[i]);
+ compute_live_vars_1 (bb, &data, NULL);
+ if (bitmap_ior_into (&active[bb->index], work))
+ changed = true;
+ }
+ }
+
+ free (rpo);
+ BITMAP_FREE (work);
+
+ return active;
+}
+
+/* For ACTIVE computed by compute_live_vars, compute a bitmap of variables
+ live after the STOP_AFTER statement and return that bitmap. */
+
+bitmap
+live_vars_at_stmt (vec<bitmap_head> &active, live_vars_map *vars,
+ gimple *stop_after)
+{
+ bitmap work = BITMAP_ALLOC (NULL);
+ compute_live_vars_data data = { active, work, vars };
+ basic_block bb = gimple_bb (stop_after);
+ compute_live_vars_1 (bb, &data, stop_after);
+ return work;
+}
+/* Destroy what compute_live_vars has returned when it is no longer needed. */
+void
+destroy_live_vars (vec<bitmap_head> &active)
+{
+ unsigned len = active.length ();
+ for (unsigned i = 0; i < len; i++)
+ bitmap_clear (&active[i]);
+
+ active.release ();
+}
+\f
/* Output partition map MAP to file F. */
void
else
p = x;
- if (ssa_name (p) == NULL_TREE)
+ if (ssa_name (p) == NULL_TREE
+ || virtual_operand_p (ssa_name (p)))
continue;
t = 0;
{
if (t++ == 0)
{
- fprintf(f, "Partition %d (", x);
+ fprintf (f, "Partition %d (", x);
print_generic_expr (f, partition_to_var (map, p), TDF_SLIM);
fprintf (f, " - ");
}
}
+/* Generic dump for the above. */
+
+DEBUG_FUNCTION void
+debug (_var_map &ref)
+{
+ dump_var_map (stderr, &ref);
+}
+
+DEBUG_FUNCTION void
+debug (_var_map *ptr)
+{
+ if (ptr)
+ debug (*ptr);
+ else
+ fprintf (stderr, "<nil>\n");
+}
+
+
/* Output live range info LIVE to file F, controlled by FLAG. */
void
if ((flag & LIVEDUMP_ENTRY) && live->livein)
{
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, cfun)
{
fprintf (f, "\nLive on entry to BB%d : ", bb->index);
- EXECUTE_IF_SET_IN_BITMAP (live->livein[bb->index], 0, i, bi)
+ EXECUTE_IF_SET_IN_BITMAP (&live->livein[bb->index], 0, i, bi)
{
print_generic_expr (f, partition_to_var (map, i), TDF_SLIM);
fprintf (f, " ");
if ((flag & LIVEDUMP_EXIT) && live->liveout)
{
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, cfun)
{
fprintf (f, "\nLive on exit from BB%d : ", bb->index);
- EXECUTE_IF_SET_IN_BITMAP (live->liveout[bb->index], 0, i, bi)
+ 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, " ");
}
}
-#ifdef ENABLE_CHECKING
-/* Verify that SSA_VAR is a non-virtual SSA_NAME. */
-void
-register_ssa_partition_check (tree ssa_var)
+/* Generic dump for the above. */
+
+DEBUG_FUNCTION void
+debug (tree_live_info_d &ref)
{
- gcc_assert (TREE_CODE (ssa_var) == SSA_NAME);
- if (!is_gimple_reg (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");
- }
+ dump_live_info (stderr, &ref, 0);
+}
+
+DEBUG_FUNCTION void
+debug (tree_live_info_d *ptr)
+{
+ if (ptr)
+ debug (*ptr);
+ else
+ fprintf (stderr, "<nil>\n");
}
{
unsigned i;
tree var;
- gimple stmt;
+ gimple *stmt;
basic_block bb;
edge e;
int num;
/* 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;
+ bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
num = 0;
FOR_EACH_EDGE (e, ei, bb->succs)
{
int entry_block = e->dest->index;
- if (e->dest == EXIT_BLOCK_PTR)
+ if (!region_contains_p (live->map, e->dest))
continue;
for (i = 0; i < (unsigned)num_var_partitions (map); i++)
{
else
if (d == var)
{
+ /* An undefined local variable does not need to be very
+ alive. */
+ if (ssa_undefined_value_p (var, false))
+ continue;
+
/* 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;
- gimple_stmt_iterator gsi;
+ gphi_iterator gsi;
for (gsi = gsi_start_phis (e->dest);
!gsi_end_p (gsi) && !ok;
gsi_next (&gsi))
{
- gimple phi = gsi_stmt (gsi);
+ gphi *phi = gsi.phi ();
+ if (virtual_operand_p (gimple_phi_result (phi)))
+ continue;
for (z = 0; z < gimple_phi_num_args (phi); z++)
if (var == gimple_phi_arg_def (phi, z))
{
}
if (ok)
continue;
+ /* Expand adds unused default defs for PARM_DECLs and
+ RESULT_DECLs. They're ok. */
+ if (has_zero_uses (var)
+ && SSA_NAME_VAR (var)
+ && !VAR_P (SSA_NAME_VAR (var)))
+ continue;
num++;
print_generic_expr (stderr, var, TDF_SLIM);
fprintf (stderr, " is not marked live-on-entry to entry BB%d ",
}
gcc_assert (num <= 0);
}
-#endif
projects / gcc.git / blobdiff