/* Generic routines for manipulating SSA_NAME expressions
- Copyright (C) 2003-2015 Free Software Foundation, Inc.
+ Copyright (C) 2003-2020 Free Software Foundation, Inc.
This file is part of GCC.
#include "stor-layout.h"
#include "tree-into-ssa.h"
#include "tree-ssa.h"
+#include "cfgloop.h"
+#include "tree-scalar-evolution.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
void
ssanames_print_statistics (void)
{
- fprintf (stderr, "SSA_NAME nodes allocated: %u\n", ssa_name_nodes_created);
- fprintf (stderr, "SSA_NAME nodes reused: %u\n", ssa_name_nodes_reused);
+ fprintf (stderr, "%-32s" PRsa (11) "\n", "SSA_NAME nodes allocated:",
+ SIZE_AMOUNT (ssa_name_nodes_created));
+ fprintf (stderr, "%-32s" PRsa (11) "\n", "SSA_NAME nodes reused:",
+ SIZE_AMOUNT (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;
+
+ auto_bitmap names_in_il;
+
+ /* 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. */
+ auto_bitmap names_in_freelists;
+ 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;
+ auto_bitmap all_names;
+ 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));
}
/* Move all SSA_NAMEs from FREE_SSA_NAMES_QUEUE to FREE_SSA_NAMES.
void
flush_ssaname_freelist (void)
{
+ /* If there were any SSA names released reset the SCEV cache. */
+ if (! vec_safe_is_empty (FREE_SSANAMES_QUEUE (cfun)))
+ scev_reset_htab ();
vec_safe_splice (FREE_SSANAMES (cfun), FREE_SSANAMES_QUEUE (cfun));
vec_safe_truncate (FREE_SSANAMES_QUEUE (cfun), 0);
}
+/* Initialize SSA_NAME_IMM_USE_NODE of a SSA NAME. */
+
+void
+init_ssa_name_imm_use (tree name)
+{
+ use_operand_p imm;
+ imm = &(SSA_NAME_IMM_USE_NODE (name));
+ imm->use = NULL;
+ imm->prev = imm;
+ imm->next = imm;
+ imm->loc.ssa_name = name;
+}
+
/* 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). */
+ used without a preceding definition). If VERISON is not zero then
+ allocate the SSA name with that version. */
tree
-make_ssa_name_fn (struct function *fn, tree var, gimple *stmt)
+make_ssa_name_fn (struct function *fn, tree var, gimple *stmt,
+ unsigned int version)
{
tree t;
- use_operand_p imm;
-
- gcc_assert (TREE_CODE (var) == VAR_DECL
+ gcc_assert (VAR_P (var)
|| TREE_CODE (var) == PARM_DECL
|| TREE_CODE (var) == RESULT_DECL
|| (TYPE_P (var) && is_gimple_reg_type (var)));
+ /* Get the specified SSA name version. */
+ if (version != 0)
+ {
+ t = make_node (SSA_NAME);
+ SSA_NAME_VERSION (t) = version;
+ if (version >= SSANAMES (fn)->length ())
+ vec_safe_grow_cleared (SSANAMES (fn), version + 1);
+ gcc_assert ((*SSANAMES (fn))[version] == NULL);
+ (*SSANAMES (fn))[version] = t;
+ ssa_name_nodes_created++;
+ }
/* If our free list has an element, then use it. */
- if (!vec_safe_is_empty (FREE_SSANAMES (fn)))
+ else if (!vec_safe_is_empty (FREE_SSANAMES (fn)))
{
t = FREE_SSANAMES (fn)->pop ();
ssa_name_nodes_reused++;
if (TYPE_P (var))
{
- TREE_TYPE (t) = var;
+ TREE_TYPE (t) = TYPE_MAIN_VARIANT (var);
SET_SSA_NAME_VAR_OR_IDENTIFIER (t, NULL_TREE);
}
else
SSA_NAME_IN_FREE_LIST (t) = 0;
SSA_NAME_IS_DEFAULT_DEF (t) = 0;
- imm = &(SSA_NAME_IMM_USE_NODE (t));
- imm->use = NULL;
- imm->prev = imm;
- imm->next = imm;
- imm->loc.ssa_name = t;
+ init_ssa_name_imm_use (t);
return t;
}
-/* Store range information RANGE_TYPE, MIN, and MAX to tree ssa_name NAME. */
+/* Helper function for set_range_info.
+
+ Store range information RANGE_TYPE, MIN, and MAX to tree ssa_name
+ NAME. */
void
-set_range_info (tree name, enum value_range_type range_type,
- const wide_int_ref &min, const wide_int_ref &max)
+set_range_info_raw (tree name, enum value_range_kind 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);
}
}
+/* Store range information RANGE_TYPE, MIN, and MAX to tree ssa_name
+ NAME while making sure we don't store useless range info. */
+
+void
+set_range_info (tree name, enum value_range_kind range_type,
+ const wide_int_ref &min, const wide_int_ref &max)
+{
+ gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
+
+ /* A range of the entire domain is really no range at all. */
+ tree type = TREE_TYPE (name);
+ if (min == wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type))
+ && max == wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type)))
+ {
+ range_info_def *ri = SSA_NAME_RANGE_INFO (name);
+ if (ri == NULL)
+ return;
+ if (ri->get_nonzero_bits () == -1)
+ {
+ ggc_free (ri);
+ SSA_NAME_RANGE_INFO (name) = NULL;
+ return;
+ }
+ }
+
+ set_range_info_raw (name, range_type, min, max);
+}
+
+/* Store range information for NAME from a value_range. */
-/* Gets range information MIN, MAX and returns enum value_range_type
- corresponding to tree ssa_name NAME. enum value_range_type returned
+void
+set_range_info (tree name, const value_range &vr)
+{
+ wide_int min = wi::to_wide (vr.min ());
+ wide_int max = wi::to_wide (vr.max ());
+ set_range_info (name, vr.kind (), min, max);
+}
+
+/* Gets range information MIN, MAX and returns enum value_range_kind
+ corresponding to tree ssa_name NAME. enum value_range_kind returned
is used to determine if MIN and MAX are valid values. */
-enum value_range_type
+enum value_range_kind
get_range_info (const_tree name, wide_int *min, wide_int *max)
{
gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
/* Return VR_VARYING for SSA_NAMEs with NULL RANGE_INFO or SSA_NAMEs
with integral types width > 2 * HOST_BITS_PER_WIDE_INT precision. */
- if (!ri || (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (name)))
+ if (!ri || (GET_MODE_PRECISION (SCALAR_INT_TYPE_MODE (TREE_TYPE (name)))
> 2 * HOST_BITS_PER_WIDE_INT))
return VR_VARYING;
return SSA_NAME_RANGE_TYPE (name);
}
+/* Gets range information corresponding to ssa_name NAME and stores it
+ in a value_range VR. Returns the value_range_kind. */
+
+enum value_range_kind
+get_range_info (const_tree name, value_range &vr)
+{
+ tree min, max;
+ wide_int wmin, wmax;
+ enum value_range_kind kind = get_range_info (name, &wmin, &wmax);
+
+ if (kind == VR_VARYING)
+ vr.set_varying (TREE_TYPE (name));
+ else if (kind == VR_UNDEFINED)
+ vr.set_undefined ();
+ else
+ {
+ min = wide_int_to_tree (TREE_TYPE (name), wmin);
+ max = wide_int_to_tree (TREE_TYPE (name), wmax);
+ vr.set (min, max, kind);
+ }
+ return kind;
+}
+
+/* Set nonnull attribute to pointer NAME. */
+
+void
+set_ptr_nonnull (tree name)
+{
+ gcc_assert (POINTER_TYPE_P (TREE_TYPE (name)));
+ struct ptr_info_def *pi = get_ptr_info (name);
+ pi->pt.null = 0;
+}
+
+/* Return nonnull attribute of pointer NAME. */
+bool
+get_ptr_nonnull (const_tree name)
+{
+ gcc_assert (POINTER_TYPE_P (TREE_TYPE (name)));
+ struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name);
+ if (pi == NULL)
+ return false;
+ /* TODO Now pt->null is conservatively set to true in PTA
+ analysis. vrp is the only pass (including ipa-vrp)
+ that clears pt.null via set_ptr_nonull when it knows
+ for sure. PTA will preserves the pt.null value set by VRP.
+
+ When PTA analysis is improved, pt.anything, pt.nonlocal
+ and pt.escaped may also has to be considered before
+ deciding that pointer cannot point to NULL. */
+ return !pi->pt.null;
+}
+
/* Change non-zero bits bitmask of NAME. */
void
{
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)));
+ {
+ if (mask == -1)
+ return;
+ set_range_info_raw (name, VR_RANGE,
+ wi::to_wide (TYPE_MIN_VALUE (TREE_TYPE (name))),
+ wi::to_wide (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. */
+ NAME, the constant for INTEGER_CST, or -1 if unknown. */
wide_int
get_nonzero_bits (const_tree name)
{
- unsigned int precision = TYPE_PRECISION (TREE_TYPE (name));
+ if (TREE_CODE (name) == INTEGER_CST)
+ return wi::to_wide (name);
+
+ /* Use element_precision instead of TYPE_PRECISION so complex and
+ vector types get a non-zero precision. */
+ unsigned int precision = element_precision (TREE_TYPE (name));
if (POINTER_TYPE_P (TREE_TYPE (name)))
{
struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name);
return ri->get_nonzero_bits ();
}
+/* Return TRUE is OP, an SSA_NAME has a range of values [0..1], false
+ otherwise.
+
+ This can be because it is a boolean type, any unsigned integral
+ type with a single bit of precision, or has known range of [0..1]
+ via VRP analysis. */
+
+bool
+ssa_name_has_boolean_range (tree op)
+{
+ gcc_assert (TREE_CODE (op) == SSA_NAME);
+
+ /* Boolean types always have a range [0..1]. */
+ if (TREE_CODE (TREE_TYPE (op)) == BOOLEAN_TYPE)
+ return true;
+
+ /* An integral type with a single bit of precision. */
+ if (INTEGRAL_TYPE_P (TREE_TYPE (op))
+ && TYPE_UNSIGNED (TREE_TYPE (op))
+ && TYPE_PRECISION (TREE_TYPE (op)) == 1)
+ return true;
+
+ /* An integral type with more precision, but the object
+ only takes on values [0..1] as determined by VRP
+ analysis. */
+ if (INTEGRAL_TYPE_P (TREE_TYPE (op))
+ && (TYPE_PRECISION (TREE_TYPE (op)) > 1)
+ && wi::eq_p (get_nonzero_bits (op), 1))
+ return true;
+
+ return false;
+}
+
/* We no longer need the SSA_NAME expression VAR, release it so that
it may be reused.
keep a status bit in the SSA_NAME node itself to indicate it has
been put on the free list.
- Note that once on the freelist you can not reference the SSA_NAME's
+ Note that once on the freelist you cannot reference the SSA_NAME's
defining statement. */
if (! SSA_NAME_IN_FREE_LIST (var))
{
- tree saved_ssa_name_var = SSA_NAME_VAR (var);
int saved_ssa_name_version = SSA_NAME_VERSION (var);
use_operand_p imm = &(SSA_NAME_IMM_USE_NODE (var));
- if (MAY_HAVE_DEBUG_STMTS)
+ if (MAY_HAVE_DEBUG_BIND_STMTS)
insert_debug_temp_for_var_def (NULL, var);
if (flag_checking)
/* Restore the version number. */
SSA_NAME_VERSION (var) = saved_ssa_name_version;
- /* Hopefully this can go away once we have the new incremental
- SSA updating code installed. */
- SET_SSA_NAME_VAR_OR_IDENTIFIER (var, saved_ssa_name_var);
-
/* Note this SSA_NAME is now in the first list. */
SSA_NAME_IN_FREE_LIST (var) = 1;
+ /* Put in a non-NULL TREE_TYPE so dumping code will not ICE
+ if it happens to come along a released SSA name and tries
+ to inspect its type. */
+ TREE_TYPE (var) = error_mark_node;
+
/* And finally queue it so that it will be put on the free list. */
vec_safe_push (FREE_SSANAMES_QUEUE (fn), var);
}
misalignment by INCREMENT modulo its current alignment. */
void
-adjust_ptr_info_misalignment (struct ptr_info_def *pi,
- unsigned int increment)
+adjust_ptr_info_misalignment (struct ptr_info_def *pi, poly_uint64 increment)
{
if (pi->align != 0)
{
- pi->misalign += increment;
- pi->misalign &= (pi->align - 1);
+ increment += pi->misalign;
+ if (!known_misalignment (increment, pi->align, &pi->misalign))
+ {
+ pi->align = known_alignment (increment);
+ pi->misalign = 0;
+ }
}
}
/* 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, enum value_range_type range_type,
+duplicate_ssa_name_range_info (tree name, enum value_range_kind range_type,
struct range_info_def *range_info)
{
struct range_info_def *new_range_info;
{
/* points-to info is not flow-sensitive. */
if (SSA_NAME_PTR_INFO (name))
- mark_ptr_info_alignment_unknown (SSA_NAME_PTR_INFO (name));
+ {
+ /* [E]VRP can derive context sensitive alignment info and
+ non-nullness properties. We must reset both. */
+ mark_ptr_info_alignment_unknown (SSA_NAME_PTR_INFO (name));
+ SSA_NAME_PTR_INFO (name)->pt.null = 1;
+ }
}
else
SSA_NAME_RANGE_INFO (name) = NULL;
tree def;
ssa_op_iter iter;
- /* Make sure that we are in SSA. Otherwise, operand cache may point
- to garbage. */
- gcc_assert (gimple_in_ssa_p (cfun));
-
FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
if (TREE_CODE (def) == SSA_NAME)
release_ssa_name (def);
TREE_TYPE (ssa_name) = TREE_TYPE (sym);
}
+/* Release the vector of free SSA_NAMEs and compact 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 (fun));
+
+ /* Now release the freelist. */
+ 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 < fun->gimple_df->ssa_names->length (); ++i)
+ {
+ tree name = ssa_name (i);
+ if (name)
+ {
+ if (i != j)
+ {
+ SSA_NAME_VERSION (name) = j;
+ (*fun->gimple_df->ssa_names)[j] = name;
+ }
+ j++;
+ }
+ }
+ fun->gimple_df->ssa_names->truncate (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 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. */
unsigned int
pass_release_ssa_names::execute (function *fun)
{
- unsigned i, j;
- int n = vec_safe_length (FREE_SSANAMES (fun));
-
- /* Now release the freelist. */
- 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 < fun->gimple_df->ssa_names->length (); ++i)
- {
- tree name = ssa_name (i);
- if (name)
- {
- if (i != j)
- {
- SSA_NAME_VERSION (name) = j;
- (*fun->gimple_df->ssa_names)[j] = name;
- }
- j++;
- }
- }
- fun->gimple_df->ssa_names->truncate (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);
+ release_free_names_and_compact_live_names (fun);
return 0;
}
projects / thirdparty / gcc.git / blobdiff