/* Generic routines for manipulating SSA_NAME expressions
- Copyright (C) 2003-2013 Free Software Foundation, Inc.
+ Copyright (C) 2003-2016 Free Software Foundation, Inc.
This file is part of GCC.
#include "config.h"
#include "system.h"
#include "coretypes.h"
-#include "tm.h"
+#include "backend.h"
#include "tree.h"
-#include "tree-ssa.h"
+#include "gimple.h"
#include "tree-pass.h"
+#include "ssa.h"
+#include "gimple-iterator.h"
+#include "stor-layout.h"
+#include "tree-into-ssa.h"
+#include "tree-ssa.h"
/* Rewriting a function into SSA form can create a huge number of SSA_NAMEs,
many of which may be thrown away shortly after their creation if jumps
unsigned int ssa_name_nodes_created;
#define FREE_SSANAMES(fun) (fun)->gimple_df->free_ssanames
+#define FREE_SSANAMES_QUEUE(fun) (fun)->gimple_df->free_ssanames_queue
/* Initialize management of SSA_NAMEs to default SIZE. If SIZE is
least 50 elements reserved in it. */
SSANAMES (fn)->quick_push (NULL_TREE);
FREE_SSANAMES (fn) = NULL;
+ FREE_SSANAMES_QUEUE (fn) = NULL;
fn->gimple_df->ssa_renaming_needed = 0;
fn->gimple_df->rename_vops = 0;
/* Finalize management of SSA_NAMEs. */
void
-fini_ssanames (void)
+fini_ssanames (struct function *fn)
{
- vec_free (SSANAMES (cfun));
- vec_free (FREE_SSANAMES (cfun));
+ vec_free (SSANAMES (fn));
+ vec_free (FREE_SSANAMES (fn));
+ vec_free (FREE_SSANAMES_QUEUE (fn));
}
/* Dump some simple statistics regarding the re-use of SSA_NAME nodes. */
fprintf (stderr, "SSA_NAME nodes reused: %u\n", ssa_name_nodes_reused);
}
+/* Verify the state of the SSA_NAME lists.
+
+ There must be no duplicates on the free list.
+ Every name on the free list must be marked as on the free list.
+ Any name on the free list must not appear in the IL.
+ No names can be leaked. */
+
+DEBUG_FUNCTION void
+verify_ssaname_freelists (struct function *fun)
+{
+ if (!gimple_in_ssa_p (fun))
+ return;
+
+ bitmap names_in_il = BITMAP_ALLOC (NULL);
+
+ /* Walk the entire IL noting every SSA_NAME we see. */
+ basic_block bb;
+ FOR_EACH_BB_FN (bb, fun)
+ {
+ tree t;
+ /* First note the result and arguments of PHI nodes. */
+ for (gphi_iterator gsi = gsi_start_phis (bb);
+ !gsi_end_p (gsi);
+ gsi_next (&gsi))
+ {
+ gphi *phi = gsi.phi ();
+ t = gimple_phi_result (phi);
+ bitmap_set_bit (names_in_il, SSA_NAME_VERSION (t));
+
+ for (unsigned int i = 0; i < gimple_phi_num_args (phi); i++)
+ {
+ t = gimple_phi_arg_def (phi, i);
+ if (TREE_CODE (t) == SSA_NAME)
+ bitmap_set_bit (names_in_il, SSA_NAME_VERSION (t));
+ }
+ }
+
+ /* Then note the operands of each statement. */
+ for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
+ !gsi_end_p (gsi);
+ gsi_next (&gsi))
+ {
+ ssa_op_iter iter;
+ gimple *stmt = gsi_stmt (gsi);
+ FOR_EACH_SSA_TREE_OPERAND (t, stmt, iter, SSA_OP_ALL_OPERANDS)
+ bitmap_set_bit (names_in_il, SSA_NAME_VERSION (t));
+ }
+ }
+
+ /* Now walk the free list noting what we find there and verifying
+ there are no duplicates. */
+ bitmap names_in_freelists = BITMAP_ALLOC (NULL);
+ if (FREE_SSANAMES (fun))
+ {
+ for (unsigned int i = 0; i < FREE_SSANAMES (fun)->length (); i++)
+ {
+ tree t = (*FREE_SSANAMES (fun))[i];
+
+ /* Verify that the name is marked as being in the free list. */
+ gcc_assert (SSA_NAME_IN_FREE_LIST (t));
+
+ /* Verify the name has not already appeared in the free list and
+ note it in the list of names found in the free list. */
+ gcc_assert (!bitmap_bit_p (names_in_freelists, SSA_NAME_VERSION (t)));
+ bitmap_set_bit (names_in_freelists, SSA_NAME_VERSION (t));
+ }
+ }
+
+ /* Similarly for the names in the pending free list. */
+ if (FREE_SSANAMES_QUEUE (fun))
+ {
+ for (unsigned int i = 0; i < FREE_SSANAMES_QUEUE (fun)->length (); i++)
+ {
+ tree t = (*FREE_SSANAMES_QUEUE (fun))[i];
+
+ /* Verify that the name is marked as being in the free list. */
+ gcc_assert (SSA_NAME_IN_FREE_LIST (t));
+
+ /* Verify the name has not already appeared in the free list and
+ note it in the list of names found in the free list. */
+ gcc_assert (!bitmap_bit_p (names_in_freelists, SSA_NAME_VERSION (t)));
+ bitmap_set_bit (names_in_freelists, SSA_NAME_VERSION (t));
+ }
+ }
+
+ /* If any name appears in both the IL and the freelists, then
+ something horrible has happened. */
+ bool intersect_p = bitmap_intersect_p (names_in_il, names_in_freelists);
+ gcc_assert (!intersect_p);
+
+ /* Names can be queued up for release if there is an ssa update
+ pending. Pretend we saw them in the IL. */
+ if (names_to_release)
+ bitmap_ior_into (names_in_il, names_to_release);
+
+ /* Function splitting can "lose" SSA_NAMEs in an effort to ensure that
+ debug/non-debug compilations have the same SSA_NAMEs. So for each
+ lost SSA_NAME, see if it's likely one from that wart. These will always
+ be marked as default definitions. So we loosely assume that anything
+ marked as a default definition isn't leaked by pretending they are
+ in the IL. */
+ for (unsigned int i = UNUSED_NAME_VERSION + 1; i < num_ssa_names; i++)
+ if (ssa_name (i) && SSA_NAME_IS_DEFAULT_DEF (ssa_name (i)))
+ bitmap_set_bit (names_in_il, i);
+
+ unsigned int i;
+ bitmap_iterator bi;
+ bitmap all_names = BITMAP_ALLOC (NULL);
+ bitmap_set_range (all_names, UNUSED_NAME_VERSION + 1, num_ssa_names - 1);
+ bitmap_ior_into (names_in_il, names_in_freelists);
+
+ /* Any name not mentioned in the IL and not in the feelists
+ has been leaked. */
+ EXECUTE_IF_AND_COMPL_IN_BITMAP(all_names, names_in_il,
+ UNUSED_NAME_VERSION + 1, i, bi)
+ gcc_assert (!ssa_name (i));
+
+ BITMAP_FREE (all_names);
+ BITMAP_FREE (names_in_freelists);
+ BITMAP_FREE (names_in_il);
+}
+
+/* Move all SSA_NAMEs from FREE_SSA_NAMES_QUEUE to FREE_SSA_NAMES.
+
+ We do not, but should have a mode to verify the state of the SSA_NAMEs
+ lists. In particular at this point every name must be in the IL,
+ on the free list or in the queue. Anything else is an error. */
+
+void
+flush_ssaname_freelist (void)
+{
+ vec_safe_splice (FREE_SSANAMES (cfun), FREE_SSANAMES_QUEUE (cfun));
+ vec_safe_truncate (FREE_SSANAMES_QUEUE (cfun), 0);
+}
+
/* Return an SSA_NAME node for variable VAR defined in statement STMT
in function FN. STMT may be an empty statement for artificial
references (e.g., default definitions created when a variable is
used without a preceding definition). */
tree
-make_ssa_name_fn (struct function *fn, tree var, gimple stmt)
+make_ssa_name_fn (struct function *fn, tree var, gimple *stmt)
{
tree t;
use_operand_p imm;
if (!vec_safe_is_empty (FREE_SSANAMES (fn)))
{
t = FREE_SSANAMES (fn)->pop ();
- if (GATHER_STATISTICS)
- ssa_name_nodes_reused++;
+ ssa_name_nodes_reused++;
/* The node was cleared out when we put it on the free list, so
there is no need to do so again here. */
- gcc_assert (ssa_name (SSA_NAME_VERSION (t)) == NULL);
+ gcc_assert ((*SSANAMES (fn))[SSA_NAME_VERSION (t)] == NULL);
(*SSANAMES (fn))[SSA_NAME_VERSION (t)] = t;
}
else
t = make_node (SSA_NAME);
SSA_NAME_VERSION (t) = SSANAMES (fn)->length ();
vec_safe_push (SSANAMES (fn), t);
- if (GATHER_STATISTICS)
- ssa_name_nodes_created++;
+ ssa_name_nodes_created++;
}
if (TYPE_P (var))
return t;
}
-/* Store range information MIN, and MAX to tree ssa_name NAME. */
+/* Store range information RANGE_TYPE, MIN, and MAX to tree ssa_name NAME. */
void
-set_range_info (tree name, double_int min, double_int max)
+set_range_info (tree name, enum value_range_type range_type,
+ const wide_int_ref &min, const wide_int_ref &max)
{
gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
+ gcc_assert (range_type == VR_RANGE || range_type == VR_ANTI_RANGE);
range_info_def *ri = SSA_NAME_RANGE_INFO (name);
+ unsigned int precision = TYPE_PRECISION (TREE_TYPE (name));
/* Allocate if not available. */
if (ri == NULL)
{
- ri = ggc_alloc_cleared_range_info_def ();
+ size_t size = (sizeof (range_info_def)
+ + trailing_wide_ints <3>::extra_size (precision));
+ ri = static_cast<range_info_def *> (ggc_internal_alloc (size));
+ ri->ints.set_precision (precision);
SSA_NAME_RANGE_INFO (name) = ri;
+ ri->set_nonzero_bits (wi::shwi (-1, precision));
}
+ /* Record the range type. */
+ if (SSA_NAME_RANGE_TYPE (name) != range_type)
+ SSA_NAME_ANTI_RANGE_P (name) = (range_type == VR_ANTI_RANGE);
+
/* Set the values. */
- ri->min = min;
- ri->max = max;
+ ri->set_min (min);
+ ri->set_max (max);
+
+ /* If it is a range, try to improve nonzero_bits from the min/max. */
+ if (range_type == VR_RANGE)
+ {
+ wide_int xorv = ri->get_min () ^ ri->get_max ();
+ if (xorv != 0)
+ xorv = wi::mask (precision - wi::clz (xorv), false, precision);
+ ri->set_nonzero_bits (ri->get_nonzero_bits () & (ri->get_min () | xorv));
+ }
}
is used to determine if MIN and MAX are valid values. */
enum value_range_type
-get_range_info (tree name, double_int *min, double_int *max)
+get_range_info (const_tree name, wide_int *min, wide_int *max)
{
- enum value_range_type range_type;
gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
gcc_assert (min && max);
range_info_def *ri = SSA_NAME_RANGE_INFO (name);
> 2 * HOST_BITS_PER_WIDE_INT))
return VR_VARYING;
- /* If min > max, it is VR_ANTI_RANGE. */
- if (ri->min.cmp (ri->max, TYPE_UNSIGNED (TREE_TYPE (name))) == 1)
+ *min = ri->get_min ();
+ *max = ri->get_max ();
+ return SSA_NAME_RANGE_TYPE (name);
+}
+
+/* Change non-zero bits bitmask of NAME. */
+
+void
+set_nonzero_bits (tree name, const wide_int_ref &mask)
+{
+ gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
+ if (SSA_NAME_RANGE_INFO (name) == NULL)
+ set_range_info (name, VR_RANGE,
+ TYPE_MIN_VALUE (TREE_TYPE (name)),
+ TYPE_MAX_VALUE (TREE_TYPE (name)));
+ range_info_def *ri = SSA_NAME_RANGE_INFO (name);
+ ri->set_nonzero_bits (mask);
+}
+
+/* Return a widest_int with potentially non-zero bits in SSA_NAME
+ NAME, or -1 if unknown. */
+
+wide_int
+get_nonzero_bits (const_tree name)
+{
+ unsigned int precision = TYPE_PRECISION (TREE_TYPE (name));
+ if (POINTER_TYPE_P (TREE_TYPE (name)))
{
- /* VR_ANTI_RANGE ~[min, max] is encoded as [max + 1, min - 1]. */
- range_type = VR_ANTI_RANGE;
- *min = ri->max + double_int_one;
- *max = ri->min - double_int_one;
+ struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name);
+ if (pi && pi->align)
+ return wi::shwi (-(HOST_WIDE_INT) pi->align
+ | (HOST_WIDE_INT) pi->misalign, precision);
+ return wi::shwi (-1, precision);
}
- else
- {
- /* Otherwise (when min <= max), it is VR_RANGE. */
- range_type = VR_RANGE;
- *min = ri->min;
- *max = ri->max;
- }
- return range_type;
+
+ range_info_def *ri = SSA_NAME_RANGE_INFO (name);
+ if (!ri)
+ return wi::shwi (-1, precision);
+
+ return ri->get_nonzero_bits ();
}
/* We no longer need the SSA_NAME expression VAR, release it so that
other fields must be assumed clobbered. */
void
-release_ssa_name (tree var)
+release_ssa_name_fn (struct function *fn, tree var)
{
if (!var)
return;
if (MAY_HAVE_DEBUG_STMTS)
insert_debug_temp_for_var_def (NULL, var);
-#ifdef ENABLE_CHECKING
- verify_imm_links (stderr, var);
-#endif
+ if (flag_checking)
+ verify_imm_links (stderr, var);
while (imm->next != imm)
delink_imm_use (imm->next);
- (*SSANAMES (cfun))[SSA_NAME_VERSION (var)] = NULL_TREE;
+ (*SSANAMES (fn))[SSA_NAME_VERSION (var)] = NULL_TREE;
memset (var, 0, tree_size (var));
imm->prev = imm;
/* Note this SSA_NAME is now in the first list. */
SSA_NAME_IN_FREE_LIST (var) = 1;
- /* And finally put it on the free list. */
- vec_safe_push (FREE_SSANAMES (cfun), var);
+ /* And finally queue it so that it will be put on the free list. */
+ vec_safe_push (FREE_SSANAMES_QUEUE (fn), var);
}
}
pi->misalign = 0;
}
-/* Store the the power-of-two byte alignment and the deviation from that
+/* Store the power-of-two byte alignment and the deviation from that
alignment of pointer described by PI to ALIOGN and MISALIGN
respectively. */
pi = SSA_NAME_PTR_INFO (t);
if (pi == NULL)
{
- pi = ggc_alloc_cleared_ptr_info_def ();
+ pi = ggc_cleared_alloc<ptr_info_def> ();
pt_solution_reset (&pi->pt);
mark_ptr_info_alignment_unknown (pi);
SSA_NAME_PTR_INFO (t) = pi;
statement STMT in function FN. */
tree
-copy_ssa_name_fn (struct function *fn, tree name, gimple stmt)
+copy_ssa_name_fn (struct function *fn, tree name, gimple *stmt)
{
tree new_name;
if (!ptr_info)
return;
- new_ptr_info = ggc_alloc_ptr_info_def ();
+ new_ptr_info = ggc_alloc<ptr_info_def> ();
*new_ptr_info = *ptr_info;
SSA_NAME_PTR_INFO (name) = new_ptr_info;
}
-/* Creates a duplicate of the range_info_def at RANGE_INFO for use by
- the SSA name NAME. */
+/* Creates a duplicate of the range_info_def at RANGE_INFO of type
+ RANGE_TYPE for use by the SSA name NAME. */
void
-duplicate_ssa_name_range_info (tree name, struct range_info_def *range_info)
+duplicate_ssa_name_range_info (tree name, enum value_range_type range_type,
+ struct range_info_def *range_info)
{
struct range_info_def *new_range_info;
if (!range_info)
return;
- new_range_info = ggc_alloc_range_info_def ();
- *new_range_info = *range_info;
+ unsigned int precision = TYPE_PRECISION (TREE_TYPE (name));
+ size_t size = (sizeof (range_info_def)
+ + trailing_wide_ints <3>::extra_size (precision));
+ new_range_info = static_cast<range_info_def *> (ggc_internal_alloc (size));
+ memcpy (new_range_info, range_info, size);
+ gcc_assert (range_type == VR_RANGE || range_type == VR_ANTI_RANGE);
+ SSA_NAME_ANTI_RANGE_P (name) = (range_type == VR_ANTI_RANGE);
SSA_NAME_RANGE_INFO (name) = new_range_info;
}
in function FN. */
tree
-duplicate_ssa_name_fn (struct function *fn, tree name, gimple stmt)
+duplicate_ssa_name_fn (struct function *fn, tree name, gimple *stmt)
{
tree new_name = copy_ssa_name_fn (fn, name, stmt);
if (POINTER_TYPE_P (TREE_TYPE (name)))
struct range_info_def *old_range_info = SSA_NAME_RANGE_INFO (name);
if (old_range_info)
- duplicate_ssa_name_range_info (new_name, old_range_info);
+ duplicate_ssa_name_range_info (new_name, SSA_NAME_RANGE_TYPE (name),
+ old_range_info);
}
return new_name;
}
+/* Reset all flow sensitive data on NAME such as range-info, nonzero
+ bits and alignment. */
+
+void
+reset_flow_sensitive_info (tree name)
+{
+ if (POINTER_TYPE_P (TREE_TYPE (name)))
+ {
+ /* points-to info is not flow-sensitive. */
+ if (SSA_NAME_PTR_INFO (name))
+ mark_ptr_info_alignment_unknown (SSA_NAME_PTR_INFO (name));
+ }
+ else
+ SSA_NAME_RANGE_INFO (name) = NULL;
+}
+
+/* Clear all flow sensitive data from all statements and PHI definitions
+ in BB. */
+
+void
+reset_flow_sensitive_info_in_bb (basic_block bb)
+{
+ for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
+ gsi_next (&gsi))
+ {
+ gimple *stmt = gsi_stmt (gsi);
+ ssa_op_iter i;
+ tree op;
+ FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_DEF)
+ reset_flow_sensitive_info (op);
+ }
+
+ for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
+ gsi_next (&gsi))
+ {
+ tree phi_def = gimple_phi_result (gsi.phi ());
+ reset_flow_sensitive_info (phi_def);
+ }
+}
+
/* Release all the SSA_NAMEs created by STMT. */
void
-release_defs (gimple stmt)
+release_defs (gimple *stmt)
{
tree def;
ssa_op_iter iter;
TREE_TYPE (ssa_name) = TREE_TYPE (sym);
}
-/* Return SSA names that are unused to GGC memory and compact the SSA
- version namespace. This is used to keep footprint of compiler during
- interprocedural optimization. */
-static unsigned int
-release_dead_ssa_names (void)
+/* Release the vector of free SSA_NAMEs and compact the the
+ vector of SSA_NAMEs that are live. */
+
+static void
+release_free_names_and_compact_live_names (function *fun)
{
unsigned i, j;
- int n = vec_safe_length (FREE_SSANAMES (cfun));
+ int n = vec_safe_length (FREE_SSANAMES (fun));
/* Now release the freelist. */
- vec_free (FREE_SSANAMES (cfun));
+ vec_free (FREE_SSANAMES (fun));
/* And compact the SSA number space. We make sure to not change the
relative order of SSA versions. */
- for (i = 1, j = 1; i < cfun->gimple_df->ssa_names->length (); ++i)
+ for (i = 1, j = 1; i < fun->gimple_df->ssa_names->length (); ++i)
{
tree name = ssa_name (i);
if (name)
if (i != j)
{
SSA_NAME_VERSION (name) = j;
- (*cfun->gimple_df->ssa_names)[j] = name;
+ (*fun->gimple_df->ssa_names)[j] = name;
}
j++;
}
}
- cfun->gimple_df->ssa_names->truncate (j);
+ fun->gimple_df->ssa_names->truncate (j);
- statistics_counter_event (cfun, "SSA names released", n);
- statistics_counter_event (cfun, "SSA name holes removed", i - j);
+ statistics_counter_event (fun, "SSA names released", n);
+ statistics_counter_event (fun, "SSA name holes removed", i - j);
if (dump_file)
fprintf (dump_file, "Released %i names, %.2f%%, removed %i holes\n",
n, n * 100.0 / num_ssa_names, i - j);
- return 0;
}
+/* Return SSA names that are unused to GGC memory and compact the SSA
+ version namespace. This is used to keep footprint of compiler during
+ interprocedural optimization. */
+
namespace {
const pass_data pass_data_release_ssa_names =
GIMPLE_PASS, /* type */
"release_ssa", /* name */
OPTGROUP_NONE, /* optinfo_flags */
- false, /* has_gate */
- true, /* has_execute */
TV_TREE_SSA_OTHER, /* tv_id */
PROP_ssa, /* properties_required */
0, /* properties_provided */
{}
/* opt_pass methods: */
- unsigned int execute () { return release_dead_ssa_names (); }
+ virtual unsigned int execute (function *);
}; // class pass_release_ssa_names
+unsigned int
+pass_release_ssa_names::execute (function *fun)
+{
+ release_free_names_and_compact_live_names (fun);
+ return 0;
+}
+
} // anon namespace
gimple_opt_pass *