/* Alias analysis for trees.
- Copyright (C) 2004 Free Software Foundation, Inc.
+ Copyright (C) 2004, 2005 Free Software Foundation, Inc.
Contributed by Diego Novillo <dnovillo@redhat.com>
This file is part of GCC.
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. */
+the Free Software Foundation, 51 Franklin Street, Fifth Floor,
+Boston, MA 02110-1301, USA. */
#include "config.h"
#include "system.h"
#include "tree-flow.h"
#include "tree-inline.h"
#include "tree-pass.h"
+#include "tree-ssa-structalias.h"
#include "convert.h"
#include "params.h"
+#include "ipa-type-escape.h"
+#include "vec.h"
+#include "bitmap.h"
+/* Obstack used to hold grouping bitmaps and other temporary bitmaps used by
+ aliasing */
+static bitmap_obstack alias_obstack;
+
+/* 'true' after aliases have been computed (see compute_may_aliases). */
+bool aliases_computed_p;
/* Structure to map a variable to its alias set and keep track of the
virtual operands that will be needed to represent it. */
/* Set of variables aliased with VAR. This is the exact same
information contained in VAR_ANN (VAR)->MAY_ALIASES, but in
bitmap form to speed up alias grouping. */
- sbitmap may_aliases;
-};
-
-
-/* Alias information used by compute_may_aliases and its helpers. */
-struct alias_info
-{
- /* SSA names visited while collecting points-to information. If bit I
- is set, it means that SSA variable with version I has already been
- visited. */
- sbitmap ssa_names_visited;
-
- /* Array of SSA_NAME pointers processed by the points-to collector. */
- varray_type processed_ptrs;
-
- /* Variables whose address is still needed. */
- bitmap addresses_needed;
-
- /* ADDRESSABLE_VARS contains all the global variables and locals that
- have had their address taken. */
- struct alias_map_d **addressable_vars;
- size_t num_addressable_vars;
-
- /* POINTERS contains all the _DECL pointers with unique memory tags
- that have been referenced in the program. */
- struct alias_map_d **pointers;
- size_t num_pointers;
-
- /* Number of function calls found in the program. */
- size_t num_calls_found;
-
- /* Array of counters to keep track of how many times each pointer has
- been dereferenced in the program. This is used by the alias grouping
- heuristic in compute_flow_insensitive_aliasing. */
- varray_type num_references;
-
- /* Total number of virtual operands that will be needed to represent
- all the aliases of all the pointers found in the program. */
- long total_alias_vops;
-
- /* Variables that have been written to. */
- bitmap written_vars;
-
- /* Pointers that have been used in an indirect store operation. */
- bitmap dereferenced_ptrs_store;
-
- /* Pointers that have been used in an indirect load operation. */
- bitmap dereferenced_ptrs_load;
+ bitmap may_aliases;
};
unsigned int simple_resolved;
unsigned int tbaa_queries;
unsigned int tbaa_resolved;
+ unsigned int structnoaddress_queries;
+ unsigned int structnoaddress_resolved;
};
/* Local functions. */
static void compute_flow_insensitive_aliasing (struct alias_info *);
static void dump_alias_stats (FILE *);
-static bool may_alias_p (tree, HOST_WIDE_INT, tree, HOST_WIDE_INT);
+static bool may_alias_p (tree, HOST_WIDE_INT, tree, HOST_WIDE_INT, bool);
static tree create_memory_tag (tree type, bool is_type_tag);
static tree get_tmt_for (tree, struct alias_info *);
static tree get_nmt_for (tree);
static void replace_may_alias (tree, size_t, tree);
static struct alias_info *init_alias_info (void);
static void delete_alias_info (struct alias_info *);
-static void compute_points_to_and_addr_escape (struct alias_info *);
static void compute_flow_sensitive_aliasing (struct alias_info *);
static void setup_pointers_and_addressables (struct alias_info *);
-static bool collect_points_to_info_r (tree, tree, void *);
-static bool is_escape_site (tree, size_t *);
-static void add_pointed_to_var (struct alias_info *, tree, tree);
static void create_global_var (void);
-static void collect_points_to_info_for (struct alias_info *, tree);
-static bool ptr_is_dereferenced_by (tree, tree, bool *);
static void maybe_create_global_var (struct alias_info *ai);
static void group_aliases (struct alias_info *);
static void set_pt_anything (tree ptr);
-static void set_pt_malloc (tree ptr);
/* Global declarations. */
The concept of 'escaping' is the same one used in the Java world. When
a pointer or an ADDR_EXPR escapes, it means that it has been exposed
outside of the current function. So, assignment to global variables,
- function arguments and returning a pointer are all escape sites.
+ function arguments and returning a pointer are all escape sites, as are
+ conversions between pointers and integers.
This is where we are currently limited. Since not everything is renamed
into SSA, we lose track of escape properties when a pointer is stashed
foo (int i)
{
- int *p, *q, a, b;
+ int *p, a, b;
if (i > 10)
p = &a;
else
- q = &b;
+ p = &b;
*p = 3;
- *q = 5;
a = b + 2;
return *p;
}
address of V escapes the current function, making V call-clobbered
(i.e., whether &V is stored in a global variable or if its passed as a
function call argument). */
- compute_points_to_and_addr_escape (ai);
+ compute_points_to_sets (ai);
/* Collect all pointers and addressable variables, compute alias sets,
create memory tags for pointers and promote variables whose address is
/* Deallocate memory used by aliasing data structures. */
delete_alias_info (ai);
+
+ {
+ block_stmt_iterator bsi;
+ basic_block bb;
+ FOR_EACH_BB (bb)
+ {
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ update_stmt_if_modified (bsi_stmt (bsi));
+ }
+ }
+ }
+
}
struct tree_opt_pass pass_may_alias =
PROP_alias, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_dump_func | TODO_rename_vars
- | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */
+ TODO_dump_func | TODO_update_ssa
+ | TODO_ggc_collect | TODO_verify_ssa
+ | TODO_verify_stmts, /* todo_flags_finish */
0 /* letter */
};
+/* Data structure used to count the number of dereferences to PTR
+ inside an expression. */
+struct count_ptr_d
+{
+ tree ptr;
+ unsigned count;
+};
+
+
+/* Helper for count_uses_and_derefs. Called by walk_tree to look for
+ (ALIGN/MISALIGNED_)INDIRECT_REF nodes for the pointer passed in DATA. */
+
+static tree
+count_ptr_derefs (tree *tp, int *walk_subtrees, void *data)
+{
+ struct count_ptr_d *count_p = (struct count_ptr_d *) data;
+
+ /* Do not walk inside ADDR_EXPR nodes. In the expression &ptr->fld,
+ pointer 'ptr' is *not* dereferenced, it is simply used to compute
+ the address of 'fld' as 'ptr + offsetof(fld)'. */
+ if (TREE_CODE (*tp) == ADDR_EXPR)
+ {
+ *walk_subtrees = 0;
+ return NULL_TREE;
+ }
+
+ if (INDIRECT_REF_P (*tp) && TREE_OPERAND (*tp, 0) == count_p->ptr)
+ count_p->count++;
+
+ return NULL_TREE;
+}
+
+
+/* Count the number of direct and indirect uses for pointer PTR in
+ statement STMT. The two counts are stored in *NUM_USES_P and
+ *NUM_DEREFS_P respectively. *IS_STORE_P is set to 'true' if at
+ least one of those dereferences is a store operation. */
+
+void
+count_uses_and_derefs (tree ptr, tree stmt, unsigned *num_uses_p,
+ unsigned *num_derefs_p, bool *is_store)
+{
+ ssa_op_iter i;
+ tree use;
+
+ *num_uses_p = 0;
+ *num_derefs_p = 0;
+ *is_store = false;
+
+ /* Find out the total number of uses of PTR in STMT. */
+ FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
+ if (use == ptr)
+ (*num_uses_p)++;
+
+ /* Now count the number of indirect references to PTR. This is
+ truly awful, but we don't have much choice. There are no parent
+ pointers inside INDIRECT_REFs, so an expression like
+ '*x_1 = foo (x_1, *x_1)' needs to be traversed piece by piece to
+ find all the indirect and direct uses of x_1 inside. The only
+ shortcut we can take is the fact that GIMPLE only allows
+ INDIRECT_REFs inside the expressions below. */
+ if (TREE_CODE (stmt) == MODIFY_EXPR
+ || (TREE_CODE (stmt) == RETURN_EXPR
+ && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR)
+ || TREE_CODE (stmt) == ASM_EXPR
+ || TREE_CODE (stmt) == CALL_EXPR)
+ {
+ tree lhs, rhs;
+
+ if (TREE_CODE (stmt) == MODIFY_EXPR)
+ {
+ lhs = TREE_OPERAND (stmt, 0);
+ rhs = TREE_OPERAND (stmt, 1);
+ }
+ else if (TREE_CODE (stmt) == RETURN_EXPR)
+ {
+ tree e = TREE_OPERAND (stmt, 0);
+ lhs = TREE_OPERAND (e, 0);
+ rhs = TREE_OPERAND (e, 1);
+ }
+ else if (TREE_CODE (stmt) == ASM_EXPR)
+ {
+ lhs = ASM_OUTPUTS (stmt);
+ rhs = ASM_INPUTS (stmt);
+ }
+ else
+ {
+ lhs = NULL_TREE;
+ rhs = stmt;
+ }
+
+ if (lhs && (TREE_CODE (lhs) == TREE_LIST || EXPR_P (lhs)))
+ {
+ struct count_ptr_d count;
+ count.ptr = ptr;
+ count.count = 0;
+ walk_tree (&lhs, count_ptr_derefs, &count, NULL);
+ *is_store = true;
+ *num_derefs_p = count.count;
+ }
+
+ if (rhs && (TREE_CODE (rhs) == TREE_LIST || EXPR_P (rhs)))
+ {
+ struct count_ptr_d count;
+ count.ptr = ptr;
+ count.count = 0;
+ walk_tree (&rhs, count_ptr_derefs, &count, NULL);
+ *num_derefs_p += count.count;
+ }
+ }
+
+ gcc_assert (*num_uses_p >= *num_derefs_p);
+}
+
/* Initialize the data structures used for alias analysis. */
static struct alias_info *
init_alias_info (void)
{
struct alias_info *ai;
- static bool aliases_computed_p = false;
+ referenced_var_iterator rvi;
+ tree var;
- ai = xcalloc (1, sizeof (struct alias_info));
+ bitmap_obstack_initialize (&alias_obstack);
+ ai = XCNEW (struct alias_info);
ai->ssa_names_visited = sbitmap_alloc (num_ssa_names);
sbitmap_zero (ai->ssa_names_visited);
VARRAY_TREE_INIT (ai->processed_ptrs, 50, "processed_ptrs");
- ai->addresses_needed = BITMAP_XMALLOC ();
- VARRAY_UINT_INIT (ai->num_references, num_referenced_vars, "num_references");
- ai->written_vars = BITMAP_XMALLOC ();
- ai->dereferenced_ptrs_store = BITMAP_XMALLOC ();
- ai->dereferenced_ptrs_load = BITMAP_XMALLOC ();
+ ai->written_vars = BITMAP_ALLOC (&alias_obstack);
+ ai->dereferenced_ptrs_store = BITMAP_ALLOC (&alias_obstack);
+ ai->dereferenced_ptrs_load = BITMAP_ALLOC (&alias_obstack);
/* If aliases have been computed before, clear existing information. */
if (aliases_computed_p)
{
unsigned i;
- bitmap_iterator bi;
-
- /* Clear the call-clobbered set. We are going to re-discover
- call-clobbered variables. */
- EXECUTE_IF_SET_IN_BITMAP (call_clobbered_vars, 0, i, bi)
- {
- tree var = referenced_var (i);
-
- /* Variables that are intrinsically call-clobbered (globals,
- local statics, etc) will not be marked by the aliasing
- code, so we can't remove them from CALL_CLOBBERED_VARS. */
- if (!is_call_clobbered (var))
- bitmap_clear_bit (call_clobbered_vars, var_ann (var)->uid);
- }
-
+
/* Similarly, clear the set of addressable variables. In this
case, we can just clear the set because addressability is
only computed here. */
bitmap_clear (addressable_vars);
/* Clear flow-insensitive alias information from each symbol. */
- for (i = 0; i < num_referenced_vars; i++)
+ FOR_EACH_REFERENCED_VAR (var, rvi)
{
- var_ann_t ann = var_ann (referenced_var (i));
+ var_ann_t ann = var_ann (var);
+
ann->is_alias_tag = 0;
ann->may_aliases = NULL;
+ NUM_REFERENCES_CLEAR (ann);
+
+ /* Since we are about to re-discover call-clobbered
+ variables, clear the call-clobbered flag. Variables that
+ are intrinsically call-clobbered (globals, local statics,
+ etc) will not be marked by the aliasing code, so we can't
+ remove them from CALL_CLOBBERED_VARS.
+
+ NB: STRUCT_FIELDS are still call clobbered if they are for
+ a global variable, so we *don't* clear their call clobberedness
+ just because they are tags, though we will clear it if they
+ aren't for global variables. */
+ if (TREE_CODE (var) == NAME_MEMORY_TAG
+ || TREE_CODE (var) == TYPE_MEMORY_TAG
+ || !is_global_var (var))
+ clear_call_clobbered (var);
}
/* Clear flow-sensitive points-to information from each SSA name. */
superset of its former points-to set, then a new
tag will need to be created in create_name_tags. */
pi->pt_anything = 0;
- pi->pt_malloc = 0;
+ pi->pt_null = 0;
pi->value_escapes_p = 0;
pi->is_dereferenced = 0;
if (pi->pt_vars)
delete_alias_info (struct alias_info *ai)
{
size_t i;
+ referenced_var_iterator rvi;
+ tree var;
sbitmap_free (ai->ssa_names_visited);
ai->processed_ptrs = NULL;
- BITMAP_XFREE (ai->addresses_needed);
for (i = 0; i < ai->num_addressable_vars; i++)
+ free (ai->addressable_vars[i]);
+
+ FOR_EACH_REFERENCED_VAR(var, rvi)
{
- sbitmap_free (ai->addressable_vars[i]->may_aliases);
- free (ai->addressable_vars[i]);
+ var_ann_t ann = var_ann (var);
+ NUM_REFERENCES_CLEAR (ann);
}
+
free (ai->addressable_vars);
for (i = 0; i < ai->num_pointers; i++)
- {
- sbitmap_free (ai->pointers[i]->may_aliases);
- free (ai->pointers[i]);
- }
+ free (ai->pointers[i]);
free (ai->pointers);
- ai->num_references = NULL;
- BITMAP_XFREE (ai->written_vars);
- BITMAP_XFREE (ai->dereferenced_ptrs_store);
- BITMAP_XFREE (ai->dereferenced_ptrs_load);
-
+ BITMAP_FREE (ai->written_vars);
+ BITMAP_FREE (ai->dereferenced_ptrs_store);
+ BITMAP_FREE (ai->dereferenced_ptrs_load);
+ bitmap_obstack_release (&alias_obstack);
free (ai);
-}
-
-
-/* Walk use-def chains for pointer PTR to determine what variables is PTR
- pointing to. */
-
-static void
-collect_points_to_info_for (struct alias_info *ai, tree ptr)
-{
- gcc_assert (POINTER_TYPE_P (TREE_TYPE (ptr)));
-
- if (!TEST_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (ptr)))
- {
- SET_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (ptr));
- walk_use_def_chains (ptr, collect_points_to_info_r, ai, true);
- VARRAY_PUSH_TREE (ai->processed_ptrs, ptr);
- }
-}
-
-
-/* Helper for ptr_is_dereferenced_by. Called by walk_tree to look for
- (ALIGN/MISALIGNED_)INDIRECT_REF nodes for the pointer passed in DATA. */
-
-static tree
-find_ptr_dereference (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED, void *data)
-{
- tree ptr = (tree) data;
-
- if (INDIRECT_REF_P (*tp)
- && TREE_OPERAND (*tp, 0) == ptr)
- return *tp;
-
- return NULL_TREE;
-}
-
-
-/* Return true if STMT contains (ALIGN/MISALIGNED_)INDIRECT_REF <PTR>.
- *IS_STORE is set to 'true' if the dereference is on the LHS of an
- assignment. */
-
-static bool
-ptr_is_dereferenced_by (tree ptr, tree stmt, bool *is_store)
-{
- *is_store = false;
-
- if (TREE_CODE (stmt) == MODIFY_EXPR
- || (TREE_CODE (stmt) == RETURN_EXPR
- && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR))
- {
- tree e, lhs, rhs;
-
- e = (TREE_CODE (stmt) == RETURN_EXPR) ? TREE_OPERAND (stmt, 0) : stmt;
- lhs = TREE_OPERAND (e, 0);
- rhs = TREE_OPERAND (e, 1);
-
- if (EXPR_P (lhs)
- && walk_tree (&lhs, find_ptr_dereference, ptr, NULL))
- {
- *is_store = true;
- return true;
- }
- else if (EXPR_P (rhs)
- && walk_tree (&rhs, find_ptr_dereference, ptr, NULL))
- {
- return true;
- }
- }
- else if (TREE_CODE (stmt) == ASM_EXPR)
- {
- if (walk_tree (&ASM_OUTPUTS (stmt), find_ptr_dereference, ptr, NULL)
- || walk_tree (&ASM_CLOBBERS (stmt), find_ptr_dereference, ptr, NULL))
- {
- *is_store = true;
- return true;
- }
- else if (walk_tree (&ASM_INPUTS (stmt), find_ptr_dereference, ptr, NULL))
- {
- return true;
- }
- }
-
- return false;
-}
-
-
-/* Traverse use-def links for all the pointers in the program to collect
- address escape and points-to information.
-
- This is loosely based on the same idea described in R. Hasti and S.
- Horwitz, ``Using static single assignment form to improve
- flow-insensitive pointer analysis,'' in SIGPLAN Conference on
- Programming Language Design and Implementation, pp. 97-105, 1998. */
-
-static void
-compute_points_to_and_addr_escape (struct alias_info *ai)
-{
- basic_block bb;
- unsigned i;
- tree op;
- ssa_op_iter iter;
-
- timevar_push (TV_TREE_PTA);
-
- FOR_EACH_BB (bb)
- {
- bb_ann_t block_ann = bb_ann (bb);
- block_stmt_iterator si;
-
- for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
- {
- bitmap addr_taken;
- tree stmt = bsi_stmt (si);
- bool stmt_escapes_p = is_escape_site (stmt, &ai->num_calls_found);
- bitmap_iterator bi;
-
- /* Mark all the variables whose address are taken by the
- statement. Note that this will miss all the addresses taken
- in PHI nodes (those are discovered while following the use-def
- chains). */
- get_stmt_operands (stmt);
- addr_taken = addresses_taken (stmt);
- if (addr_taken)
- EXECUTE_IF_SET_IN_BITMAP (addr_taken, 0, i, bi)
- {
- tree var = referenced_var (i);
- bitmap_set_bit (ai->addresses_needed, var_ann (var)->uid);
- if (stmt_escapes_p)
- mark_call_clobbered (var);
- }
-
- if (stmt_escapes_p)
- block_ann->has_escape_site = 1;
-
- /* Special case for silly ADDR_EXPR tricks
- (gcc.c-torture/unsorted/pass.c). If this statement is an
- assignment to a non-pointer variable and the RHS takes the
- address of a variable, assume that the variable on the RHS is
- call-clobbered. We could add the LHS to the list of
- "pointers" and follow it to see if it really escapes, but it's
- not worth the pain. */
- if (addr_taken
- && TREE_CODE (stmt) == MODIFY_EXPR
- && !POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt, 0))))
- EXECUTE_IF_SET_IN_BITMAP (addr_taken, 0, i, bi)
- {
- tree var = referenced_var (i);
- mark_call_clobbered (var);
- }
-
- FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
- {
- var_ann_t v_ann = var_ann (SSA_NAME_VAR (op));
- struct ptr_info_def *pi;
- bool is_store;
-
- /* If the operand's variable may be aliased, keep track
- of how many times we've referenced it. This is used
- for alias grouping in compute_flow_sensitive_aliasing.
- Note that we don't need to grow AI->NUM_REFERENCES
- because we are processing regular variables, not
- memory tags (the array's initial size is set to
- NUM_REFERENCED_VARS). */
- if (may_be_aliased (SSA_NAME_VAR (op)))
- (VARRAY_UINT (ai->num_references, v_ann->uid))++;
-
- if (!POINTER_TYPE_P (TREE_TYPE (op)))
- continue;
-
- collect_points_to_info_for (ai, op);
-
- pi = SSA_NAME_PTR_INFO (op);
- if (ptr_is_dereferenced_by (op, stmt, &is_store))
- {
- /* Mark OP as dereferenced. In a subsequent pass,
- dereferenced pointers that point to a set of
- variables will be assigned a name tag to alias
- all the variables OP points to. */
- pi->is_dereferenced = 1;
-
- /* Keep track of how many time we've dereferenced each
- pointer. Again, we don't need to grow
- AI->NUM_REFERENCES because we're processing
- existing program variables. */
- (VARRAY_UINT (ai->num_references, v_ann->uid))++;
-
- /* If this is a store operation, mark OP as being
- dereferenced to store, otherwise mark it as being
- dereferenced to load. */
- if (is_store)
- bitmap_set_bit (ai->dereferenced_ptrs_store, v_ann->uid);
- else
- bitmap_set_bit (ai->dereferenced_ptrs_load, v_ann->uid);
- }
- else if (stmt_escapes_p)
- {
- /* Note that even if STMT is an escape point, pointer OP
- will not escape if it is being dereferenced. That's
- why we only check for escape points if OP is not
- dereferenced by STMT. */
- pi->value_escapes_p = 1;
-
- /* If the statement makes a function call, assume
- that pointer OP will be dereferenced in a store
- operation inside the called function. */
- if (get_call_expr_in (stmt))
- {
- bitmap_set_bit (ai->dereferenced_ptrs_store, v_ann->uid);
- pi->is_dereferenced = 1;
- }
- }
- }
-
- /* Update reference counter for definitions to any
- potentially aliased variable. This is used in the alias
- grouping heuristics. */
- FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
- {
- tree var = SSA_NAME_VAR (op);
- var_ann_t ann = var_ann (var);
- bitmap_set_bit (ai->written_vars, ann->uid);
- if (may_be_aliased (var))
- (VARRAY_UINT (ai->num_references, ann->uid))++;
-
- if (POINTER_TYPE_P (TREE_TYPE (op)))
- collect_points_to_info_for (ai, op);
- }
-
- /* Mark variables in V_MAY_DEF operands as being written to. */
- FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_DEFS)
- {
- tree var = SSA_NAME_VAR (op);
- var_ann_t ann = var_ann (var);
- bitmap_set_bit (ai->written_vars, ann->uid);
- }
-
- /* After promoting variables and computing aliasing we will
- need to re-scan most statements. FIXME: Try to minimize the
- number of statements re-scanned. It's not really necessary to
- re-scan *all* statements. */
- modify_stmt (stmt);
- }
- }
- timevar_pop (TV_TREE_PTA);
+ delete_points_to_sets ();
}
-
/* Create name tags for all the pointers that have been dereferenced.
We only create a name tag for a pointer P if P is found to point to
a set of variables (so that we can alias them to *P) or if it is
are assigned the same name tag. */
static void
-create_name_tags (struct alias_info *ai)
+create_name_tags (void)
{
size_t i;
+ VEC (tree, heap) *with_ptvars = NULL;
+ tree ptr;
- for (i = 0; i < VARRAY_ACTIVE_SIZE (ai->processed_ptrs); i++)
+ /* Collect the list of pointers with a non-empty points to set. */
+ for (i = 1; i < num_ssa_names; i++)
{
- tree ptr = VARRAY_TREE (ai->processed_ptrs, i);
- struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
+ tree ptr = ssa_name (i);
+ struct ptr_info_def *pi;
+
+ if (!ptr
+ || !POINTER_TYPE_P (TREE_TYPE (ptr))
+ || !SSA_NAME_PTR_INFO (ptr))
+ continue;
+
+ pi = SSA_NAME_PTR_INFO (ptr);
if (pi->pt_anything || !pi->is_dereferenced)
{
continue;
}
- if (pi->pt_vars && !bitmap_empty_p (pi->pt_vars))
+ /* Set pt_anything on the pointers without pt_vars filled in so
+ that they are assigned a type tag. */
+
+ if (pi->pt_vars && !bitmap_empty_p (pi->pt_vars))
+ VEC_safe_push (tree, heap, with_ptvars, ptr);
+ else
+ set_pt_anything (ptr);
+ }
+
+ /* If we didn't find any pointers with pt_vars set, we're done. */
+ if (!with_ptvars)
+ return;
+
+ /* Now go through the pointers with pt_vars, and find a name tag
+ with the same pt_vars as this pointer, or create one if one
+ doesn't exist. */
+ for (i = 0; VEC_iterate (tree, with_ptvars, i, ptr); i++)
+ {
+ struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
+ size_t j;
+ tree ptr2;
+ tree old_name_tag = pi->name_mem_tag;
+
+ /* If PTR points to a set of variables, check if we don't
+ have another pointer Q with the same points-to set before
+ creating a tag. If so, use Q's tag instead of creating a
+ new one.
+
+ This is important for not creating unnecessary symbols
+ and also for copy propagation. If we ever need to
+ propagate PTR into Q or vice-versa, we would run into
+ problems if they both had different name tags because
+ they would have different SSA version numbers (which
+ would force us to take the name tags in and out of SSA). */
+ for (j = 0; j < i && VEC_iterate (tree, with_ptvars, j, ptr2); j++)
{
- size_t j;
- tree old_name_tag = pi->name_mem_tag;
-
- /* If PTR points to a set of variables, check if we don't
- have another pointer Q with the same points-to set before
- creating a tag. If so, use Q's tag instead of creating a
- new one.
-
- This is important for not creating unnecessary symbols
- and also for copy propagation. If we ever need to
- propagate PTR into Q or vice-versa, we would run into
- problems if they both had different name tags because
- they would have different SSA version numbers (which
- would force us to take the name tags in and out of SSA). */
- for (j = 0; j < i; j++)
+ struct ptr_info_def *qi = SSA_NAME_PTR_INFO (ptr2);
+
+ if (bitmap_equal_p (pi->pt_vars, qi->pt_vars))
{
- tree q = VARRAY_TREE (ai->processed_ptrs, j);
- struct ptr_info_def *qi = SSA_NAME_PTR_INFO (q);
-
- if (qi
- && qi->pt_vars
- && qi->name_mem_tag
- && bitmap_equal_p (pi->pt_vars, qi->pt_vars))
- {
- pi->name_mem_tag = qi->name_mem_tag;
- break;
- }
+ pi->name_mem_tag = qi->name_mem_tag;
+ break;
}
-
- /* If we didn't find a pointer with the same points-to set
- as PTR, create a new name tag if needed. */
- if (pi->name_mem_tag == NULL_TREE)
- pi->name_mem_tag = get_nmt_for (ptr);
-
- /* If the new name tag computed for PTR is different than
- the old name tag that it used to have, then the old tag
- needs to be removed from the IL, so we mark it for
- renaming. */
- if (old_name_tag && old_name_tag != pi->name_mem_tag)
- bitmap_set_bit (vars_to_rename, var_ann (old_name_tag)->uid);
- }
- else if (pi->pt_malloc)
- {
- /* Otherwise, create a unique name tag for this pointer. */
- pi->name_mem_tag = get_nmt_for (ptr);
- }
- else
- {
- /* Only pointers that may point to malloc or other variables
- may receive a name tag. If the pointer does not point to
- a known spot, we should use type tags. */
- set_pt_anything (ptr);
- continue;
}
-
+
+ /* If we didn't find a pointer with the same points-to set
+ as PTR, create a new name tag if needed. */
+ if (pi->name_mem_tag == NULL_TREE)
+ pi->name_mem_tag = get_nmt_for (ptr);
+
+ /* If the new name tag computed for PTR is different than
+ the old name tag that it used to have, then the old tag
+ needs to be removed from the IL, so we mark it for
+ renaming. */
+ if (old_name_tag && old_name_tag != pi->name_mem_tag)
+ mark_sym_for_renaming (old_name_tag);
+
TREE_THIS_VOLATILE (pi->name_mem_tag)
- |= TREE_THIS_VOLATILE (TREE_TYPE (TREE_TYPE (ptr)));
-
+ |= TREE_THIS_VOLATILE (TREE_TYPE (TREE_TYPE (ptr)));
+
/* Mark the new name tag for renaming. */
- bitmap_set_bit (vars_to_rename, var_ann (pi->name_mem_tag)->uid);
+ mark_sym_for_renaming (pi->name_mem_tag);
}
-}
+ VEC_free (tree, heap, with_ptvars);
+}
/* For every pointer P_i in AI->PROCESSED_PTRS, create may-alias sets for
compute_flow_sensitive_aliasing (struct alias_info *ai)
{
size_t i;
+
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (ai->processed_ptrs); i++)
+ {
+ tree ptr = VARRAY_TREE (ai->processed_ptrs, i);
+ if (!find_what_p_points_to (ptr))
+ set_pt_anything (ptr);
+ }
- create_name_tags (ai);
+ create_name_tags ();
for (i = 0; i < VARRAY_ACTIVE_SIZE (ai->processed_ptrs); i++)
{
if (pi->pt_vars)
EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, j, bi)
- {
- mark_call_clobbered (referenced_var (j));
- }
+ mark_call_clobbered (referenced_var (j));
}
/* Set up aliasing information for PTR's name memory tag (if it has
EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, j, bi)
{
add_may_alias (pi->name_mem_tag, referenced_var (j));
+ add_may_alias (v_ann->type_mem_tag, referenced_var (j));
}
/* If the name tag is call clobbered, so is the type tag
compute_flow_insensitive_aliasing (struct alias_info *ai)
{
size_t i;
- sbitmap res;
/* Initialize counter for the total number of virtual operands that
aliasing will introduce. When AI->TOTAL_ALIAS_VOPS goes beyond the
var_ann_t tag_ann = var_ann (tag);
p_map->total_alias_vops = 0;
- p_map->may_aliases = sbitmap_alloc (num_referenced_vars);
- sbitmap_zero (p_map->may_aliases);
+ p_map->may_aliases = BITMAP_ALLOC (&alias_obstack);
for (j = 0; j < ai->num_addressable_vars; j++)
{
/* Skip memory tags and variables that have never been
written to. We also need to check if the variables are
call-clobbered because they may be overwritten by
- function calls. */
- tag_stored_p = bitmap_bit_p (ai->written_vars, tag_ann->uid)
- || is_call_clobbered (tag);
- var_stored_p = bitmap_bit_p (ai->written_vars, v_ann->uid)
- || is_call_clobbered (var);
+ function calls.
+
+ Note this is effectively random accessing elements in
+ the sparse bitset, which can be highly inefficient.
+ So we first check the call_clobbered status of the
+ tag and variable before querying the bitmap. */
+ tag_stored_p = is_call_clobbered (tag)
+ || bitmap_bit_p (ai->written_vars, DECL_UID (tag));
+ var_stored_p = is_call_clobbered (var)
+ || bitmap_bit_p (ai->written_vars, DECL_UID (var));
if (!tag_stored_p && !var_stored_p)
continue;
- if (may_alias_p (p_map->var, p_map->set, var, v_map->set))
+ if (may_alias_p (p_map->var, p_map->set, var, v_map->set, false))
{
size_t num_tag_refs, num_var_refs;
- num_tag_refs = VARRAY_UINT (ai->num_references, tag_ann->uid);
- num_var_refs = VARRAY_UINT (ai->num_references, v_ann->uid);
+ num_tag_refs = NUM_REFERENCES (tag_ann);
+ num_var_refs = NUM_REFERENCES (v_ann);
/* Add VAR to TAG's may-aliases set. */
+
+ /* We should never have a var with subvars here, because
+ they shouldn't get into the set of addressable vars */
+ gcc_assert (!var_can_have_subvars (var)
+ || get_subvars_for_var (var) == NULL);
+
add_may_alias (tag, var);
+ /* Update the bitmap used to represent TAG's alias set
+ in case we need to group aliases. */
+ bitmap_set_bit (p_map->may_aliases, DECL_UID (var));
/* Update the total number of virtual operands due to
aliasing. Since we are adding one more alias to TAG's
ai->total_alias_vops += (num_var_refs + num_tag_refs);
p_map->total_alias_vops += (num_var_refs + num_tag_refs);
- /* Update the bitmap used to represent TAG's alias set
- in case we need to group aliases. */
- SET_BIT (p_map->may_aliases, var_ann (var)->uid);
+
}
}
}
To avoid this problem, we do a final traversal of AI->POINTERS
looking for pairs of pointers that have no aliased symbols in
common and yet have conflicting alias set numbers. */
- res = sbitmap_alloc (num_referenced_vars);
-
for (i = 0; i < ai->num_pointers; i++)
{
size_t j;
struct alias_map_d *p_map1 = ai->pointers[i];
tree tag1 = var_ann (p_map1->var)->type_mem_tag;
- sbitmap may_aliases1 = p_map1->may_aliases;
+ bitmap may_aliases1 = p_map1->may_aliases;
for (j = i + 1; j < ai->num_pointers; j++)
{
struct alias_map_d *p_map2 = ai->pointers[j];
tree tag2 = var_ann (p_map2->var)->type_mem_tag;
- sbitmap may_aliases2 = p_map2->may_aliases;
+ bitmap may_aliases2 = p_map2->may_aliases;
/* If the pointers may not point to each other, do nothing. */
- if (!may_alias_p (p_map1->var, p_map1->set, p_map2->var, p_map2->set))
+ if (!may_alias_p (p_map1->var, p_map1->set, tag2, p_map2->set, true))
continue;
/* The two pointers may alias each other. If they already have
symbols in common, do nothing. */
- sbitmap_a_and_b (res, may_aliases1, may_aliases2);
- if (sbitmap_first_set_bit (res) >= 0)
+ if (bitmap_intersect_p (may_aliases1, may_aliases2))
continue;
- if (sbitmap_first_set_bit (may_aliases2) >= 0)
+ if (!bitmap_empty_p (may_aliases2))
{
- size_t k;
+ unsigned int k;
+ bitmap_iterator bi;
/* Add all the aliases for TAG2 into TAG1's alias set.
FIXME, update grouping heuristic counters. */
- EXECUTE_IF_SET_IN_SBITMAP (may_aliases2, 0, k,
- add_may_alias (tag1, referenced_var (k)));
- sbitmap_a_or_b (may_aliases1, may_aliases1, may_aliases2);
+ EXECUTE_IF_SET_IN_BITMAP (may_aliases2, 0, k, bi)
+ add_may_alias (tag1, referenced_var (k));
+ bitmap_ior_into (may_aliases1, may_aliases2);
}
else
{
/* Since TAG2 does not have any aliases of its own, add
TAG2 itself to the alias set of TAG1. */
add_may_alias (tag1, tag2);
+ bitmap_set_bit (may_aliases1, DECL_UID (tag2));
}
}
}
-
- sbitmap_free (res);
-
+
if (dump_file)
- fprintf (dump_file, "%s: Total number of aliased vops: %ld\n",
+ fprintf (dump_file, "\n%s: Total number of aliased vops: %ld\n",
get_name (current_function_decl),
ai->total_alias_vops);
may-aliases(V2) = { TAG } */
static void
-group_aliases_into (tree tag, sbitmap tag_aliases, struct alias_info *ai)
+group_aliases_into (tree tag, bitmap tag_aliases, struct alias_info *ai)
{
- size_t i;
+ unsigned int i;
var_ann_t tag_ann = var_ann (tag);
- size_t num_tag_refs = VARRAY_UINT (ai->num_references, tag_ann->uid);
+ size_t num_tag_refs = NUM_REFERENCES (tag_ann);
+ bitmap_iterator bi;
- EXECUTE_IF_SET_IN_SBITMAP (tag_aliases, 0, i,
+ EXECUTE_IF_SET_IN_BITMAP (tag_aliases, 0, i, bi)
{
tree var = referenced_var (i);
var_ann_t ann = var_ann (var);
itself won't be removed. We will merely replace them with
references to TAG. */
ai->total_alias_vops -= num_tag_refs;
- });
+ }
/* We have reduced the number of virtual operands that TAG makes on
behalf of all the variables formerly aliased with it. However,
group_aliases (struct alias_info *ai)
{
size_t i;
- sbitmap res;
/* Sort the POINTERS array in descending order of contributed
virtual operands. */
qsort (ai->pointers, ai->num_pointers, sizeof (struct alias_map_d *),
total_alias_vops_cmp);
- res = sbitmap_alloc (num_referenced_vars);
-
/* For every pointer in AI->POINTERS, reverse the roles of its tag
and the tag's may-aliases set. */
for (i = 0; i < ai->num_pointers; i++)
{
size_t j;
tree tag1 = var_ann (ai->pointers[i]->var)->type_mem_tag;
- sbitmap tag1_aliases = ai->pointers[i]->may_aliases;
+ bitmap tag1_aliases = ai->pointers[i]->may_aliases;
/* Skip tags that have been grouped already. */
if (ai->pointers[i]->grouped_p)
aliases into TAG1. */
for (j = i + 1; j < ai->num_pointers; j++)
{
- sbitmap tag2_aliases = ai->pointers[j]->may_aliases;
+ bitmap tag2_aliases = ai->pointers[j]->may_aliases;
- sbitmap_a_and_b (res, tag1_aliases, tag2_aliases);
- if (sbitmap_first_set_bit (res) >= 0)
+ if (bitmap_intersect_p (tag1_aliases, tag2_aliases))
{
tree tag2 = var_ann (ai->pointers[j]->var)->type_mem_tag;
- sbitmap_a_or_b (tag1_aliases, tag1_aliases, tag2_aliases);
+ bitmap_ior_into (tag1_aliases, tag2_aliases);
/* TAG2 does not need its aliases anymore. */
- sbitmap_zero (tag2_aliases);
+ bitmap_clear (tag2_aliases);
var_ann (tag2)->may_aliases = NULL;
/* TAG1 is the unique alias of TAG2. */
size_t j;
tree ptr = VARRAY_TREE (ai->processed_ptrs, i);
tree name_tag = SSA_NAME_PTR_INFO (ptr)->name_mem_tag;
- varray_type aliases;
+ VEC(tree,gc) *aliases;
+ tree alias;
if (name_tag == NULL_TREE)
continue;
aliases = var_ann (name_tag)->may_aliases;
- for (j = 0; aliases && j < VARRAY_ACTIVE_SIZE (aliases); j++)
+ for (j = 0; VEC_iterate (tree, aliases, j, alias); j++)
{
- tree alias = VARRAY_TREE (aliases, j);
var_ann_t ann = var_ann (alias);
- if (ann->mem_tag_kind == NOT_A_TAG && ann->may_aliases)
+ if ((!MTAG_P (alias)
+ || TREE_CODE (alias) == STRUCT_FIELD_TAG)
+ && ann->may_aliases)
{
tree new_alias;
- gcc_assert (VARRAY_ACTIVE_SIZE (ann->may_aliases) == 1);
+ gcc_assert (VEC_length (tree, ann->may_aliases) == 1);
- new_alias = VARRAY_TREE (ann->may_aliases, 0);
+ new_alias = VEC_index (tree, ann->may_aliases, 0);
replace_may_alias (name_tag, j, new_alias);
}
}
}
- sbitmap_free (res);
-
if (dump_file)
fprintf (dump_file,
"%s: Total number of aliased vops after grouping: %ld%s\n",
create_alias_map_for (tree var, struct alias_info *ai)
{
struct alias_map_d *alias_map;
- alias_map = xcalloc (1, sizeof (*alias_map));
+ alias_map = XCNEW (struct alias_map_d);
alias_map->var = var;
alias_map->set = get_alias_set (var);
ai->addressable_vars[ai->num_addressable_vars++] = alias_map;
static void
setup_pointers_and_addressables (struct alias_info *ai)
{
- size_t i, n_vars, num_addressable_vars, num_pointers;
+ size_t n_vars, num_addressable_vars, num_pointers;
+ referenced_var_iterator rvi;
+ tree var;
+ VEC (tree, heap) *varvec = NULL;
+ safe_referenced_var_iterator srvi;
/* Size up the arrays ADDRESSABLE_VARS and POINTERS. */
num_addressable_vars = num_pointers = 0;
- for (i = 0; i < num_referenced_vars; i++)
+
+ FOR_EACH_REFERENCED_VAR (var, rvi)
{
- tree var = referenced_var (i);
-
if (may_be_aliased (var))
num_addressable_vars++;
/* Since we don't keep track of volatile variables, assume that
these pointers are used in indirect store operations. */
if (TREE_THIS_VOLATILE (var))
- bitmap_set_bit (ai->dereferenced_ptrs_store, var_ann (var)->uid);
+ bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var));
num_pointers++;
}
because some TREE_ADDRESSABLE variables will be marked
non-addressable below and only pointers with unique type tags are
going to be added to POINTERS. */
- ai->addressable_vars = xcalloc (num_addressable_vars,
- sizeof (struct alias_map_d *));
- ai->pointers = xcalloc (num_pointers, sizeof (struct alias_map_d *));
+ ai->addressable_vars = XCNEWVEC (struct alias_map_d *, num_addressable_vars);
+ ai->pointers = XCNEWVEC (struct alias_map_d *, num_pointers);
ai->num_addressable_vars = 0;
ai->num_pointers = 0;
unnecessarily. */
n_vars = num_referenced_vars;
- for (i = 0; i < n_vars; i++)
+ FOR_EACH_REFERENCED_VAR_SAFE (var, varvec, srvi)
{
- tree var = referenced_var (i);
var_ann_t v_ann = var_ann (var);
+ subvar_t svars;
/* Name memory tags already have flow-sensitive aliasing
information, so they need not be processed by
compute_flow_insensitive_aliasing. Similarly, type memory
tags are already accounted for when we process their
- associated pointer. */
- if (v_ann->mem_tag_kind != NOT_A_TAG)
+ associated pointer.
+
+ Structure fields, on the other hand, have to have some of this
+ information processed for them, but it's pointless to mark them
+ non-addressable (since they are fake variables anyway). */
+ if (MTAG_P (var) && TREE_CODE (var) != STRUCT_FIELD_TAG)
continue;
/* Remove the ADDRESSABLE flag from every addressable variable whose
cleanup passes. */
if (TREE_ADDRESSABLE (var))
{
- if (!bitmap_bit_p (ai->addresses_needed, v_ann->uid)
- && v_ann->mem_tag_kind == NOT_A_TAG
+ if (!bitmap_bit_p (addressable_vars, DECL_UID (var))
&& TREE_CODE (var) != RESULT_DECL
&& !is_global_var (var))
{
- /* The address of VAR is not needed, remove the
- addressable bit, so that it can be optimized as a
- regular variable. */
- mark_non_addressable (var);
+ bool okay_to_mark = true;
/* Since VAR is now a regular GIMPLE register, we will need
to rename VAR into SSA afterwards. */
- bitmap_set_bit (vars_to_rename, v_ann->uid);
- }
- else
- {
- /* Add the variable to the set of addressables. Mostly
- used when scanning operands for ASM_EXPRs that
- clobber memory. In those cases, we need to clobber
- all call-clobbered variables and all addressables. */
- bitmap_set_bit (addressable_vars, v_ann->uid);
+ mark_sym_for_renaming (var);
+
+ /* If VAR can have sub-variables, and any of its
+ sub-variables has its address taken, then we cannot
+ remove the addressable flag from VAR. */
+ if (var_can_have_subvars (var)
+ && (svars = get_subvars_for_var (var)))
+ {
+ subvar_t sv;
+
+ for (sv = svars; sv; sv = sv->next)
+ {
+ if (bitmap_bit_p (addressable_vars, DECL_UID (sv->var)))
+ okay_to_mark = false;
+ mark_sym_for_renaming (sv->var);
+ }
+ }
+
+ /* The address of VAR is not needed, remove the
+ addressable bit, so that it can be optimized as a
+ regular variable. */
+ if (okay_to_mark)
+ mark_non_addressable (var);
}
}
/* Global variables and addressable locals may be aliased. Create an
entry in ADDRESSABLE_VARS for VAR. */
- if (may_be_aliased (var))
+ if (may_be_aliased (var)
+ && (!var_can_have_subvars (var)
+ || get_subvars_for_var (var) == NULL))
{
create_alias_map_for (var, ai);
- bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
+ mark_sym_for_renaming (var);
}
/* Add pointer variables that have been dereferenced to the POINTERS
array and create a type memory tag for them. */
if (POINTER_TYPE_P (TREE_TYPE (var)))
{
- if ((bitmap_bit_p (ai->dereferenced_ptrs_store, v_ann->uid)
- || bitmap_bit_p (ai->dereferenced_ptrs_load, v_ann->uid)))
+ if ((bitmap_bit_p (ai->dereferenced_ptrs_store, DECL_UID (var))
+ || bitmap_bit_p (ai->dereferenced_ptrs_load, DECL_UID (var))))
{
tree tag;
var_ann_t t_ann;
afterwards. Note that we cannot do this inside
get_tmt_for because aliasing may run multiple times
and we only create type tags the first time. */
- bitmap_set_bit (vars_to_rename, t_ann->uid);
+ mark_sym_for_renaming (tag);
+
+ /* Similarly, if pointer VAR used to have another type
+ tag, we will need to process it in the renamer to
+ remove the stale virtual operands. */
+ if (v_ann->type_mem_tag)
+ mark_sym_for_renaming (v_ann->type_mem_tag);
/* Associate the tag with pointer VAR. */
v_ann->type_mem_tag = tag;
/* If pointer VAR has been used in a store operation,
then its memory tag must be marked as written-to. */
- if (bitmap_bit_p (ai->dereferenced_ptrs_store, v_ann->uid))
- bitmap_set_bit (ai->written_vars, t_ann->uid);
+ if (bitmap_bit_p (ai->dereferenced_ptrs_store, DECL_UID (var)))
+ bitmap_set_bit (ai->written_vars, DECL_UID (tag));
/* If pointer VAR is a global variable or a PARM_DECL,
then its memory tag should be considered a global
/* All the dereferences of pointer VAR count as
references of TAG. Since TAG can be associated with
several pointers, add the dereferences of VAR to the
- TAG. We may need to grow AI->NUM_REFERENCES because
- we have been adding name and type tags. */
- if (t_ann->uid >= VARRAY_SIZE (ai->num_references))
- VARRAY_GROW (ai->num_references, t_ann->uid + 10);
-
- VARRAY_UINT (ai->num_references, t_ann->uid)
- += VARRAY_UINT (ai->num_references, v_ann->uid);
+ TAG. */
+ NUM_REFERENCES_SET (t_ann,
+ NUM_REFERENCES (t_ann)
+ + NUM_REFERENCES (v_ann));
}
else
{
tree tag = ann->type_mem_tag;
if (tag)
{
- bitmap_set_bit (vars_to_rename, var_ann (tag)->uid);
+ mark_sym_for_renaming (tag);
ann->type_mem_tag = NULL_TREE;
}
}
}
}
+ VEC_free (tree, heap, varvec);
}
n_clobbered++;
}
- /* Create .GLOBAL_VAR if we have too many call-clobbered
- variables. We also create .GLOBAL_VAR when there no
- call-clobbered variables to prevent code motion
- transformations from re-arranging function calls that may
- have side effects. For instance,
+ /* If the number of virtual operands that would be needed to
+ model all the call-clobbered variables is larger than
+ GLOBAL_VAR_THRESHOLD, create .GLOBAL_VAR.
- foo ()
- {
- int a = f ();
- g ();
- h (a);
- }
+ Also create .GLOBAL_VAR if there are no call-clobbered
+ variables and the program contains a mixture of pure/const
+ and regular function calls. This is to avoid the problem
+ described in PR 20115:
- There are no call-clobbered variables in foo(), so it would
- be entirely possible for a pass to want to move the call to
- f() after the call to g(). If f() has side effects, that
- would be wrong. Creating .GLOBAL_VAR in this case will
- insert VDEFs for it and prevent such transformations. */
- if (n_clobbered == 0
- || ai->num_calls_found * n_clobbered >= (size_t) GLOBAL_VAR_THRESHOLD)
+ int X;
+ int func_pure (void) { return X; }
+ int func_non_pure (int a) { X += a; }
+ int foo ()
+ {
+ int a = func_pure ();
+ func_non_pure (a);
+ a = func_pure ();
+ return a;
+ }
+
+ Since foo() has no call-clobbered variables, there is
+ no relationship between the calls to func_pure and
+ func_non_pure. Since func_pure has no side-effects, value
+ numbering optimizations elide the second call to func_pure.
+ So, if we have some pure/const and some regular calls in the
+ program we create .GLOBAL_VAR to avoid missing these
+ relations. */
+ if (ai->num_calls_found * n_clobbered >= (size_t) GLOBAL_VAR_THRESHOLD
+ || (n_clobbered == 0
+ && ai->num_calls_found > 0
+ && ai->num_pure_const_calls_found > 0
+ && ai->num_calls_found > ai->num_pure_const_calls_found))
create_global_var ();
}
- /* If the function has calls to clobbering functions and .GLOBAL_VAR has
- been created, make it an alias for all call-clobbered variables. */
- if (global_var)
- EXECUTE_IF_SET_IN_BITMAP (call_clobbered_vars, 0, i, bi)
- {
- tree var = referenced_var (i);
- if (var != global_var)
- {
- add_may_alias (var, global_var);
- bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
- }
- }
+ /* Mark all call-clobbered symbols for renaming. Since the initial
+ rewrite into SSA ignored all call sites, we may need to rename
+ .GLOBAL_VAR and the call-clobbered variables. */
+ EXECUTE_IF_SET_IN_BITMAP (call_clobbered_vars, 0, i, bi)
+ {
+ tree var = referenced_var (i);
+
+ /* If the function has calls to clobbering functions and
+ .GLOBAL_VAR has been created, make it an alias for all
+ call-clobbered variables. */
+ if (global_var && var != global_var)
+ {
+ subvar_t svars;
+ add_may_alias (var, global_var);
+ if (var_can_have_subvars (var)
+ && (svars = get_subvars_for_var (var)))
+ {
+ subvar_t sv;
+ for (sv = svars; sv; sv = sv->next)
+ mark_sym_for_renaming (sv->var);
+ }
+ }
+
+ mark_sym_for_renaming (var);
+ }
}
static bool
may_alias_p (tree ptr, HOST_WIDE_INT mem_alias_set,
- tree var, HOST_WIDE_INT var_alias_set)
+ tree var, HOST_WIDE_INT var_alias_set,
+ bool alias_set_only)
{
tree mem;
- var_ann_t v_ann, m_ann;
alias_stats.alias_queries++;
alias_stats.simple_queries++;
alias_stats.simple_resolved++;
return false;
}
+
+ /* If -fargument-noalias-global is >1, pointer arguments may
+ not point to global variables. */
+ if (flag_argument_noalias > 1 && is_global_var (var)
+ && TREE_CODE (ptr) == PARM_DECL)
+ {
+ alias_stats.alias_noalias++;
+ alias_stats.simple_resolved++;
+ return false;
+ }
- v_ann = var_ann (var);
- m_ann = var_ann (mem);
+ /* If either MEM or VAR is a read-only global and the other one
+ isn't, then PTR cannot point to VAR. */
+ if ((unmodifiable_var_p (mem) && !unmodifiable_var_p (var))
+ || (unmodifiable_var_p (var) && !unmodifiable_var_p (mem)))
+ {
+ alias_stats.alias_noalias++;
+ alias_stats.simple_resolved++;
+ return false;
+ }
- gcc_assert (m_ann->mem_tag_kind == TYPE_TAG);
+ gcc_assert (TREE_CODE (mem) == TYPE_MEMORY_TAG);
alias_stats.tbaa_queries++;
- /* If VAR is a pointer with the same alias set as PTR, then dereferencing
- PTR can't possibly affect VAR. Note, that we are specifically testing
- for PTR's alias set here, not its pointed-to type. We also can't
- do this check with relaxed aliasing enabled. */
- if (POINTER_TYPE_P (TREE_TYPE (var))
- && var_alias_set != 0
- && mem_alias_set != 0)
- {
- HOST_WIDE_INT ptr_alias_set = get_alias_set (ptr);
- if (ptr_alias_set == var_alias_set)
- {
- alias_stats.alias_noalias++;
- alias_stats.tbaa_resolved++;
- return false;
- }
- }
-
/* If the alias sets don't conflict then MEM cannot alias VAR. */
if (!alias_sets_conflict_p (mem_alias_set, var_alias_set))
{
return false;
}
+ /* If var is a record or union type, ptr cannot point into var
+ unless there is some operation explicit address operation in the
+ program that can reference a field of the ptr's dereferenced
+ type. This also assumes that the types of both var and ptr are
+ contained within the compilation unit, and that there is no fancy
+ addressing arithmetic associated with any of the types
+ involved. */
+
+ if ((mem_alias_set != 0) && (var_alias_set != 0))
+ {
+ tree ptr_type = TREE_TYPE (ptr);
+ tree var_type = TREE_TYPE (var);
+
+ /* The star count is -1 if the type at the end of the pointer_to
+ chain is not a record or union type. */
+ if ((!alias_set_only) &&
+ ipa_type_escape_star_count_of_interesting_type (var_type) >= 0)
+ {
+ int ptr_star_count = 0;
+
+ /* Ipa_type_escape_star_count_of_interesting_type is a little to
+ restrictive for the pointer type, need to allow pointers to
+ primitive types as long as those types cannot be pointers
+ to everything. */
+ while (POINTER_TYPE_P (ptr_type))
+ /* Strip the *'s off. */
+ {
+ ptr_type = TREE_TYPE (ptr_type);
+ ptr_star_count++;
+ }
+
+ /* There does not appear to be a better test to see if the
+ pointer type was one of the pointer to everything
+ types. */
+
+ if (ptr_star_count > 0)
+ {
+ alias_stats.structnoaddress_queries++;
+ if (ipa_type_escape_field_does_not_clobber_p (var_type,
+ TREE_TYPE (ptr)))
+ {
+ alias_stats.structnoaddress_resolved++;
+ alias_stats.alias_noalias++;
+ return false;
+ }
+ }
+ else if (ptr_star_count == 0)
+ {
+ /* If ptr_type was not really a pointer to type, it cannot
+ alias. */
+ alias_stats.structnoaddress_queries++;
+ alias_stats.structnoaddress_resolved++;
+ alias_stats.alias_noalias++;
+ return false;
+ }
+ }
+ }
+
alias_stats.alias_mayalias++;
return true;
}
size_t i;
var_ann_t v_ann = get_var_ann (var);
var_ann_t a_ann = get_var_ann (alias);
+ tree al;
+ /* Don't allow self-referential aliases. */
gcc_assert (var != alias);
+ /* ALIAS must be addressable if it's being added to an alias set. */
+#if 1
+ TREE_ADDRESSABLE (alias) = 1;
+#else
+ gcc_assert (may_be_aliased (alias));
+#endif
+
if (v_ann->may_aliases == NULL)
- VARRAY_TREE_INIT (v_ann->may_aliases, 2, "aliases");
+ v_ann->may_aliases = VEC_alloc (tree, gc, 2);
/* Avoid adding duplicates. */
- for (i = 0; i < VARRAY_ACTIVE_SIZE (v_ann->may_aliases); i++)
- if (alias == VARRAY_TREE (v_ann->may_aliases, i))
+ for (i = 0; VEC_iterate (tree, v_ann->may_aliases, i, al); i++)
+ if (alias == al)
return;
/* If VAR is a call-clobbered variable, so is its new ALIAS.
else if (is_call_clobbered (alias))
mark_call_clobbered (var);
- VARRAY_PUSH_TREE (v_ann->may_aliases, alias);
+ VEC_safe_push (tree, gc, v_ann->may_aliases, alias);
a_ann->is_alias_tag = 1;
}
replace_may_alias (tree var, size_t i, tree new_alias)
{
var_ann_t v_ann = var_ann (var);
- VARRAY_TREE (v_ann->may_aliases, i) = new_alias;
+ VEC_replace (tree, v_ann->may_aliases, i, new_alias);
/* If VAR is a call-clobbered variable, so is NEW_ALIAS.
FIXME, call-clobbering should only depend on whether an address
struct ptr_info_def *pi = get_ptr_info (ptr);
pi->pt_anything = 1;
- pi->pt_malloc = 0;
+ pi->pt_vars = NULL;
/* The pointer used to have a name tag, but we now found it pointing
to an arbitrary location. The name tag needs to be renamed and
disassociated from PTR. */
if (pi->name_mem_tag)
{
- bitmap_set_bit (vars_to_rename, var_ann (pi->name_mem_tag)->uid);
+ mark_sym_for_renaming (pi->name_mem_tag);
pi->name_mem_tag = NULL_TREE;
}
}
-/* Mark pointer PTR as pointing to a malloc'd memory area. */
-
-static void
-set_pt_malloc (tree ptr)
-{
- struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
-
- /* If the pointer has already been found to point to arbitrary
- memory locations, it is unsafe to mark it as pointing to malloc. */
- if (pi->pt_anything)
- return;
-
- pi->pt_malloc = 1;
-}
-
-
-/* Given two different pointers DEST and ORIG. Merge the points-to
- information in ORIG into DEST. AI is as in
- collect_points_to_info. */
-
-static void
-merge_pointed_to_info (struct alias_info *ai, tree dest, tree orig)
-{
- struct ptr_info_def *dest_pi, *orig_pi;
-
- /* FIXME: It is erroneous to call this function with identical
- nodes, however that currently occurs during bootstrap. This check
- stops further breakage. PR 18307 documents the issue. */
- if (dest == orig)
- return;
-
- /* Make sure we have points-to information for ORIG. */
- collect_points_to_info_for (ai, orig);
-
- dest_pi = get_ptr_info (dest);
- orig_pi = SSA_NAME_PTR_INFO (orig);
-
- if (orig_pi)
- {
- /* Notice that we never merge PT_MALLOC. This attribute is only
- true if the pointer is the result of a malloc() call.
- Otherwise, we can end up in this situation:
-
- P_i = malloc ();
- ...
- P_j = P_i + X;
-
- P_j would be marked as PT_MALLOC, which is wrong because
- PT_MALLOC implies that the pointer may not point to another
- variable.
-
- FIXME 1: Subsequent analysis may determine that P_j
- cannot alias anything else, but we are being conservative
- here.
-
- FIXME 2: If the merging comes from a copy assignment, we
- ought to merge PT_MALLOC, but then both pointers would end up
- getting different name tags because create_name_tags is not
- smart enough to determine that the two come from the same
- malloc call. Copy propagation before aliasing should cure
- this. */
- gcc_assert (orig_pi != dest_pi);
-
- dest_pi->pt_malloc = 0;
-
- if (orig_pi->pt_malloc || orig_pi->pt_anything)
- set_pt_anything (dest);
-
- if (!dest_pi->pt_anything
- && orig_pi->pt_vars
- && !bitmap_empty_p (orig_pi->pt_vars))
- {
- if (dest_pi->pt_vars == NULL)
- {
- dest_pi->pt_vars = BITMAP_GGC_ALLOC ();
- bitmap_copy (dest_pi->pt_vars, orig_pi->pt_vars);
- }
- else
- bitmap_ior_into (dest_pi->pt_vars, orig_pi->pt_vars);
- }
- }
- else
- set_pt_anything (dest);
-}
-
-
-/* Add EXPR to the list of expressions pointed-to by PTR. */
-
-static void
-add_pointed_to_expr (struct alias_info *ai, tree ptr, tree expr)
-{
- if (TREE_CODE (expr) == WITH_SIZE_EXPR)
- expr = TREE_OPERAND (expr, 0);
-
- get_ptr_info (ptr);
-
- if (TREE_CODE (expr) == CALL_EXPR
- && (call_expr_flags (expr) & (ECF_MALLOC | ECF_MAY_BE_ALLOCA)))
- {
- /* If EXPR is a malloc-like call, then the area pointed to PTR
- is guaranteed to not alias with anything else. */
- set_pt_malloc (ptr);
- }
- else if (TREE_CODE (expr) == ADDR_EXPR)
- {
- /* Found P_i = ADDR_EXPR */
- add_pointed_to_var (ai, ptr, expr);
- }
- else if (TREE_CODE (expr) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (expr)))
- {
- /* Found P_i = Q_j. */
- merge_pointed_to_info (ai, ptr, expr);
- }
- else if (TREE_CODE (expr) == PLUS_EXPR || TREE_CODE (expr) == MINUS_EXPR)
- {
- /* Found P_i = PLUS_EXPR or P_i = MINUS_EXPR */
- tree op0 = TREE_OPERAND (expr, 0);
- tree op1 = TREE_OPERAND (expr, 1);
-
- /* Both operands may be of pointer type. FIXME: Shouldn't
- we just expect PTR + OFFSET always? */
- if (POINTER_TYPE_P (TREE_TYPE (op0))
- && TREE_CODE (op0) != INTEGER_CST)
- {
- if (TREE_CODE (op0) == SSA_NAME)
- merge_pointed_to_info (ai, ptr, op0);
- else if (TREE_CODE (op0) == ADDR_EXPR)
- add_pointed_to_var (ai, ptr, op0);
- else
- set_pt_anything (ptr);
- }
-
- if (POINTER_TYPE_P (TREE_TYPE (op1))
- && TREE_CODE (op1) != INTEGER_CST)
- {
- if (TREE_CODE (op1) == SSA_NAME)
- merge_pointed_to_info (ai, ptr, op1);
- else if (TREE_CODE (op1) == ADDR_EXPR)
- add_pointed_to_var (ai, ptr, op1);
- else
- set_pt_anything (ptr);
- }
-
- /* Neither operand is a pointer? VAR can be pointing anywhere.
- FIXME: Shouldn't we abort here? If we get here, we found
- PTR = INT_CST + INT_CST, which should not be a valid pointer
- expression. */
- if (!(POINTER_TYPE_P (TREE_TYPE (op0))
- && TREE_CODE (op0) != INTEGER_CST)
- && !(POINTER_TYPE_P (TREE_TYPE (op1))
- && TREE_CODE (op1) != INTEGER_CST))
- set_pt_anything (ptr);
- }
- else
- {
- /* If we can't recognize the expression, assume that PTR may
- point anywhere. */
- set_pt_anything (ptr);
- }
-}
-
-
-/* If VALUE is of the form &DECL, add DECL to the set of variables
- pointed-to by PTR. Otherwise, add VALUE as a pointed-to expression by
- PTR. AI is as in collect_points_to_info. */
-
-static void
-add_pointed_to_var (struct alias_info *ai, tree ptr, tree value)
-{
- struct ptr_info_def *pi = get_ptr_info (ptr);
- tree pt_var;
- size_t uid;
-
- gcc_assert (TREE_CODE (value) == ADDR_EXPR);
-
- pt_var = TREE_OPERAND (value, 0);
- if (REFERENCE_CLASS_P (pt_var))
- pt_var = get_base_address (pt_var);
-
- if (pt_var && SSA_VAR_P (pt_var))
- {
- uid = var_ann (pt_var)->uid;
- bitmap_set_bit (ai->addresses_needed, uid);
-
- if (pi->pt_vars == NULL)
- pi->pt_vars = BITMAP_GGC_ALLOC ();
- bitmap_set_bit (pi->pt_vars, uid);
-
- /* If the variable is a global, mark the pointer as pointing to
- global memory (which will make its tag a global variable). */
- if (is_global_var (pt_var))
- pi->pt_global_mem = 1;
- }
-}
-
-
-/* Callback for walk_use_def_chains to gather points-to information from the
- SSA web.
-
- VAR is an SSA variable or a GIMPLE expression.
-
- STMT is the statement that generates the SSA variable or, if STMT is a
- PHI_NODE, VAR is one of the PHI arguments.
-
- DATA is a pointer to a structure of type ALIAS_INFO. */
-
-static bool
-collect_points_to_info_r (tree var, tree stmt, void *data)
-{
- struct alias_info *ai = (struct alias_info *) data;
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "Visiting use-def links for ");
- print_generic_expr (dump_file, var, dump_flags);
- fprintf (dump_file, "\n");
- }
-
- switch (TREE_CODE (stmt))
- {
- case RETURN_EXPR:
- if (TREE_CODE (TREE_OPERAND (stmt, 0)) != MODIFY_EXPR)
- abort ();
- stmt = TREE_OPERAND (stmt, 0);
- /* FALLTHRU */
-
- case MODIFY_EXPR:
- {
- tree rhs = TREE_OPERAND (stmt, 1);
- STRIP_NOPS (rhs);
- add_pointed_to_expr (ai, var, rhs);
- break;
- }
-
- case ASM_EXPR:
- /* Pointers defined by __asm__ statements can point anywhere. */
- set_pt_anything (var);
- break;
-
- case NOP_EXPR:
- if (IS_EMPTY_STMT (stmt))
- {
- tree decl = SSA_NAME_VAR (var);
-
- if (TREE_CODE (decl) == PARM_DECL)
- add_pointed_to_expr (ai, var, decl);
- else if (DECL_INITIAL (decl))
- add_pointed_to_expr (ai, var, DECL_INITIAL (decl));
- else
- add_pointed_to_expr (ai, var, decl);
- }
- break;
-
- case PHI_NODE:
- {
- /* It STMT is a PHI node, then VAR is one of its arguments. The
- variable that we are analyzing is the LHS of the PHI node. */
- tree lhs = PHI_RESULT (stmt);
-
- switch (TREE_CODE (var))
- {
- case ADDR_EXPR:
- add_pointed_to_var (ai, lhs, var);
- break;
-
- case SSA_NAME:
- merge_pointed_to_info (ai, lhs, var);
- break;
-
- default:
- gcc_assert (is_gimple_min_invariant (var));
- add_pointed_to_expr (ai, lhs, var);
- break;
- }
- break;
- }
-
- default:
- gcc_unreachable ();
- }
-
- return false;
-}
-
-
/* Return true if STMT is an "escape" site from the current function. Escape
sites those statements which might expose the address of a variable
outside the current function. STMT is an escape site iff:
3- STMT is an assignment to a non-local variable, or
4- STMT is a return statement.
- If NUM_CALLS_P is not NULL, the counter is incremented if STMT contains
- a function call. */
+ AI points to the alias information collected so far. */
-static bool
-is_escape_site (tree stmt, size_t *num_calls_p)
+bool
+is_escape_site (tree stmt, struct alias_info *ai)
{
- if (get_call_expr_in (stmt) != NULL_TREE)
+ tree call = get_call_expr_in (stmt);
+ if (call != NULL_TREE)
{
- if (num_calls_p)
- (*num_calls_p)++;
+ ai->num_calls_found++;
+
+ if (!TREE_SIDE_EFFECTS (call))
+ ai->num_pure_const_calls_found++;
return true;
}
if (lhs == NULL_TREE)
return true;
+ /* If the RHS is a conversion between a pointer and an integer, the
+ pointer escapes since we can't track the integer. */
+ if ((TREE_CODE (TREE_OPERAND (stmt, 1)) == NOP_EXPR
+ || TREE_CODE (TREE_OPERAND (stmt, 1)) == CONVERT_EXPR
+ || TREE_CODE (TREE_OPERAND (stmt, 1)) == VIEW_CONVERT_EXPR)
+ && POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND
+ (TREE_OPERAND (stmt, 1), 0)))
+ && !POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt, 1))))
+ return true;
+
/* If the LHS is an SSA name, it can't possibly represent a non-local
memory store. */
if (TREE_CODE (lhs) == SSA_NAME)
return false;
}
+/* Create a new memory tag of type TYPE.
+ Does NOT push it into the current binding. */
+
+static tree
+create_tag_raw (enum tree_code code, tree type, const char *prefix)
+{
+ tree tmp_var;
+ tree new_type;
+
+ /* Make the type of the variable writable. */
+ new_type = build_type_variant (type, 0, 0);
+ TYPE_ATTRIBUTES (new_type) = TYPE_ATTRIBUTES (type);
+
+ tmp_var = build_decl (code, create_tmp_var_name (prefix),
+ type);
+ /* Make the variable writable. */
+ TREE_READONLY (tmp_var) = 0;
+
+ /* It doesn't start out global. */
+ MTAG_GLOBAL (tmp_var) = 0;
+ TREE_STATIC (tmp_var) = 0;
+ TREE_USED (tmp_var) = 1;
+
+ return tmp_var;
+}
/* Create a new memory tag of type TYPE. If IS_TYPE_TAG is true, the tag
is considered to represent all the pointers whose pointed-to types are
create_memory_tag (tree type, bool is_type_tag)
{
var_ann_t ann;
- tree tag = create_tmp_var_raw (type, (is_type_tag) ? "TMT" : "NMT");
+ tree tag = create_tag_raw (is_type_tag ? TYPE_MEMORY_TAG : NAME_MEMORY_TAG,
+ type, (is_type_tag) ? "TMT" : "NMT");
/* By default, memory tags are local variables. Alias analysis will
determine whether they should be considered globals. */
DECL_CONTEXT (tag) = current_function_decl;
- /* Memory tags are by definition addressable. This also prevents
- is_gimple_ref frome confusing memory tags with optimizable
- variables. */
+ /* Memory tags are by definition addressable. */
TREE_ADDRESSABLE (tag) = 1;
ann = get_var_ann (tag);
- ann->mem_tag_kind = (is_type_tag) ? TYPE_TAG : NAME_TAG;
ann->type_mem_tag = NULL_TREE;
/* Add the tag to the symbol table. */
/* If PTR is a PARM_DECL, it points to a global variable or malloc,
then its name tag should be considered a global variable. */
if (TREE_CODE (SSA_NAME_VAR (ptr)) == PARM_DECL
- || pi->pt_malloc
|| pi->pt_global_mem)
mark_call_clobbered (tag);
for (i = 0, tag = NULL_TREE; i < ai->num_pointers; i++)
{
struct alias_map_d *curr = ai->pointers[i];
- if (tag_set == curr->set)
+ tree curr_tag = var_ann (curr->var)->type_mem_tag;
+ if (tag_set == curr->set
+ && TYPE_READONLY (tag_type) == TYPE_READONLY (TREE_TYPE (curr_tag)))
{
- tag = var_ann (curr->var)->type_mem_tag;
+ tag = curr_tag;
break;
}
}
/* Add PTR to the POINTERS array. Note that we are not interested in
PTR's alias set. Instead, we cache the alias set for the memory that
PTR points to. */
- alias_map = xcalloc (1, sizeof (*alias_map));
+ alias_map = XCNEW (struct alias_map_d);
alias_map->var = ptr;
alias_map->set = tag_set;
ai->pointers[ai->num_pointers++] = alias_map;
pointed-to type. */
gcc_assert (tag_set == get_alias_set (tag));
+ /* If PTR's pointed-to type is read-only, then TAG's type must also
+ be read-only. */
+ gcc_assert (TYPE_READONLY (tag_type) == TYPE_READONLY (TREE_TYPE (tag)));
+
return tag;
}
create_global_var (void)
{
global_var = build_decl (VAR_DECL, get_identifier (".GLOBAL_VAR"),
- size_type_node);
+ void_type_node);
DECL_ARTIFICIAL (global_var) = 1;
TREE_READONLY (global_var) = 0;
DECL_EXTERNAL (global_var) = 1;
TREE_ADDRESSABLE (global_var) = 0;
add_referenced_tmp_var (global_var);
- bitmap_set_bit (vars_to_rename, var_ann (global_var)->uid);
+ mark_sym_for_renaming (global_var);
}
alias_stats.tbaa_queries);
fprintf (file, "Total TBAA resolved:\t%u\n",
alias_stats.tbaa_resolved);
+ fprintf (file, "Total non-addressable structure type queries:\t%u\n",
+ alias_stats.structnoaddress_queries);
+ fprintf (file, "Total non-addressable structure type resolved:\t%u\n",
+ alias_stats.structnoaddress_resolved);
}
size_t i;
const char *funcname
= lang_hooks.decl_printable_name (current_function_decl, 2);
+ referenced_var_iterator rvi;
+ tree var;
fprintf (file, "\nFlow-insensitive alias information for %s\n\n", funcname);
fprintf (file, "Aliased symbols\n\n");
- for (i = 0; i < num_referenced_vars; i++)
+
+ FOR_EACH_REFERENCED_VAR (var, rvi)
{
- tree var = referenced_var (i);
if (may_be_aliased (var))
dump_variable (file, var);
}
fprintf (file, "\nDereferenced pointers\n\n");
- for (i = 0; i < num_referenced_vars; i++)
+
+ FOR_EACH_REFERENCED_VAR (var, rvi)
{
- tree var = referenced_var (i);
var_ann_t ann = var_ann (var);
if (ann->type_mem_tag)
dump_variable (file, var);
}
fprintf (file, "\nType memory tags\n\n");
- for (i = 0; i < num_referenced_vars; i++)
+
+ FOR_EACH_REFERENCED_VAR (var, rvi)
{
- tree var = referenced_var (i);
- var_ann_t ann = var_ann (var);
- if (ann->mem_tag_kind == TYPE_TAG)
+ if (TREE_CODE (var) == TYPE_MEMORY_TAG)
dump_variable (file, var);
}
}
fprintf (file, "\nName memory tags\n\n");
- for (i = 0; i < num_referenced_vars; i++)
+
+ FOR_EACH_REFERENCED_VAR (var, rvi)
{
- tree var = referenced_var (i);
- var_ann_t ann = var_ann (var);
- if (ann->mem_tag_kind == NAME_TAG)
+ if (TREE_CODE (var) == NAME_MEMORY_TAG)
dump_variable (file, var);
}
pi = SSA_NAME_PTR_INFO (t);
if (pi == NULL)
{
- pi = ggc_alloc (sizeof (*pi));
+ pi = GGC_NEW (struct ptr_info_def);
memset ((void *)pi, 0, sizeof (*pi));
SSA_NAME_PTR_INFO (t) = pi;
}
if (pi->pt_anything)
fprintf (file, ", points-to anything");
- if (pi->pt_malloc)
- fprintf (file, ", points-to malloc");
+ if (pi->pt_null)
+ fprintf (file, ", points-to NULL");
if (pi->pt_vars)
{
{
basic_block bb;
block_stmt_iterator si;
- size_t i;
ssa_op_iter iter;
const char *fname =
lang_hooks.decl_printable_name (current_function_decl, 2);
+ referenced_var_iterator rvi;
+ tree var;
fprintf (file, "\n\nPointed-to sets for pointers in %s\n\n", fname);
/* First dump points-to information for the default definitions of
pointer variables. This is necessary because default definitions are
not part of the code. */
- for (i = 0; i < num_referenced_vars; i++)
+ FOR_EACH_REFERENCED_VAR (var, rvi)
{
- tree var = referenced_var (i);
if (POINTER_TYPE_P (TREE_TYPE (var)))
{
- var_ann_t ann = var_ann (var);
- if (ann->default_def)
- dump_points_to_info_for (file, ann->default_def);
+ tree def = default_def (var);
+ if (def)
+ dump_points_to_info_for (file, def);
}
}
}
-/* Dump points-to info pointed by PTO into STDERR. */
+/* Dump points-to info pointed to by PTO into STDERR. */
void
debug_points_to_info (void)
void
dump_may_aliases_for (FILE *file, tree var)
{
- varray_type aliases;
+ VEC(tree, gc) *aliases;
if (TREE_CODE (var) == SSA_NAME)
var = SSA_NAME_VAR (var);
if (aliases)
{
size_t i;
+ tree al;
fprintf (file, "{ ");
- for (i = 0; i < VARRAY_ACTIVE_SIZE (aliases); i++)
+ for (i = 0; VEC_iterate (tree, aliases, i, al); i++)
{
- print_generic_expr (file, VARRAY_TREE (aliases, i), dump_flags);
+ print_generic_expr (file, al, dump_flags);
fprintf (file, " ");
}
fprintf (file, "}");
/* Globally visible variables can have their addresses taken by other
translation units. */
- if (DECL_EXTERNAL (var) || TREE_PUBLIC (var))
+
+ if (MTAG_P (var)
+ && (MTAG_GLOBAL (var) || TREE_PUBLIC (var)))
+ return true;
+ else if (!MTAG_P (var)
+ && (DECL_EXTERNAL (var) || TREE_PUBLIC (var)))
return true;
/* Automatic variables can't have their addresses escape any other way.
return true;
}
+
+/* Given two symbols return TRUE if one is in the alias set of the other. */
+bool
+is_aliased_with (tree tag, tree sym)
+{
+ size_t i;
+ VEC(tree,gc) *aliases;
+ tree al;
+
+ if (var_ann (sym)->is_alias_tag)
+ {
+ aliases = var_ann (tag)->may_aliases;
+
+ if (aliases == NULL)
+ return false;
+
+ for (i = 0; VEC_iterate (tree, aliases, i, al); i++)
+ if (al == sym)
+ return true;
+ }
+ else
+ {
+ aliases = var_ann (sym)->may_aliases;
+
+ if (aliases == NULL)
+ return false;
+
+ for (i = 0; VEC_iterate (tree, aliases, i, al); i++)
+ if (al == tag)
+ return true;
+ }
+
+ return false;
+}
+
+
+/* Add VAR to the list of may-aliases of PTR's type tag. If PTR
+ doesn't already have a type tag, create one. */
+
+void
+add_type_alias (tree ptr, tree var)
+{
+ VEC(tree, gc) *aliases;
+ tree tag, al;
+ var_ann_t ann = var_ann (ptr);
+ subvar_t svars;
+ VEC (tree, heap) *varvec = NULL;
+ unsigned i;
+
+ if (ann->type_mem_tag == NULL_TREE)
+ {
+ tree q = NULL_TREE;
+ tree tag_type = TREE_TYPE (TREE_TYPE (ptr));
+ HOST_WIDE_INT tag_set = get_alias_set (tag_type);
+ safe_referenced_var_iterator rvi;
+
+ /* PTR doesn't have a type tag, create a new one and add VAR to
+ the new tag's alias set.
+
+ FIXME, This is slower than necessary. We need to determine
+ whether there is another pointer Q with the same alias set as
+ PTR. This could be sped up by having type tags associated
+ with types. */
+ FOR_EACH_REFERENCED_VAR_SAFE (q, varvec, rvi)
+ {
+ if (POINTER_TYPE_P (TREE_TYPE (q))
+ && tag_set == get_alias_set (TREE_TYPE (TREE_TYPE (q))))
+ {
+ /* Found another pointer Q with the same alias set as
+ the PTR's pointed-to type. If Q has a type tag, use
+ it. Otherwise, create a new memory tag for PTR. */
+ var_ann_t ann1 = var_ann (q);
+ if (ann1->type_mem_tag)
+ ann->type_mem_tag = ann1->type_mem_tag;
+ else
+ ann->type_mem_tag = create_memory_tag (tag_type, true);
+ goto found_tag;
+ }
+ }
+
+ /* Couldn't find any other pointer with a type tag we could use.
+ Create a new memory tag for PTR. */
+ ann->type_mem_tag = create_memory_tag (tag_type, true);
+ }
+
+found_tag:
+ /* If VAR is not already PTR's type tag, add it to the may-alias set
+ for PTR's type tag. */
+ gcc_assert (!MTAG_P (var_ann (var)->type_mem_tag));
+ tag = ann->type_mem_tag;
+
+ /* If VAR has subvars, add the subvars to the tag instead of the
+ actual var. */
+ if (var_can_have_subvars (var)
+ && (svars = get_subvars_for_var (var)))
+ {
+ subvar_t sv;
+ for (sv = svars; sv; sv = sv->next)
+ add_may_alias (tag, sv->var);
+ }
+ else
+ add_may_alias (tag, var);
+
+ /* TAG and its set of aliases need to be marked for renaming. */
+ mark_sym_for_renaming (tag);
+ if ((aliases = var_ann (tag)->may_aliases) != NULL)
+ {
+ for (i = 0; VEC_iterate (tree, aliases, i, al); i++)
+ mark_sym_for_renaming (al);
+ }
+
+ /* If we had grouped aliases, VAR may have aliases of its own. Mark
+ them for renaming as well. Other statements referencing the
+ aliases of VAR will need to be updated. */
+ if ((aliases = var_ann (var)->may_aliases) != NULL)
+ {
+ for (i = 0; VEC_iterate (tree, aliases, i, al); i++)
+ mark_sym_for_renaming (al);
+ }
+ VEC_free (tree, heap, varvec);
+}
+
+
+/* Create a new type tag for PTR. Construct the may-alias list of this type
+ tag so that it has the aliasing of VAR.
+
+ Note, the set of aliases represented by the new type tag are not marked
+ for renaming. */
+
+void
+new_type_alias (tree ptr, tree var)
+{
+ var_ann_t p_ann = var_ann (ptr);
+ tree tag_type = TREE_TYPE (TREE_TYPE (ptr));
+ var_ann_t v_ann = var_ann (var);
+ tree tag;
+ subvar_t svars;
+
+ gcc_assert (p_ann->type_mem_tag == NULL_TREE);
+ gcc_assert (!MTAG_P (var));
+
+ /* Add VAR to the may-alias set of PTR's new type tag. If VAR has
+ subvars, add the subvars to the tag instead of the actual var. */
+ if (var_can_have_subvars (var)
+ && (svars = get_subvars_for_var (var)))
+ {
+ subvar_t sv;
+
+ tag = create_memory_tag (tag_type, true);
+ p_ann->type_mem_tag = tag;
+
+ for (sv = svars; sv; sv = sv->next)
+ add_may_alias (tag, sv->var);
+ }
+ else
+ {
+ /* The following is based on code in add_stmt_operand to ensure that the
+ same defs/uses/vdefs/vuses will be found after replacing a reference
+ to var (or ARRAY_REF to var) with an INDIRECT_REF to ptr whose value
+ is the address of var. */
+ VEC(tree, gc) *aliases = v_ann->may_aliases;
+
+ if ((aliases != NULL)
+ && (VEC_length (tree, aliases) == 1))
+ {
+ tree ali = VEC_index (tree, aliases, 0);
+
+ if (TREE_CODE (ali) == TYPE_MEMORY_TAG)
+ {
+ p_ann->type_mem_tag = ali;
+ return;
+ }
+ }
+
+ tag = create_memory_tag (tag_type, true);
+ p_ann->type_mem_tag = tag;
+
+ if (aliases == NULL)
+ add_may_alias (tag, var);
+ else
+ {
+ unsigned i;
+ tree al;
+
+ for (i = 0; VEC_iterate (tree, aliases, i, al); i++)
+ add_may_alias (tag, al);
+ }
+ }
+}
+
+
+
+/* This represents the used range of a variable. */
+
+typedef struct used_part
+{
+ HOST_WIDE_INT minused;
+ HOST_WIDE_INT maxused;
+ /* True if we have an explicit use/def of some portion of this variable,
+ even if it is all of it. i.e. a.b = 5 or temp = a.b. */
+ bool explicit_uses;
+ /* True if we have an implicit use/def of some portion of this
+ variable. Implicit uses occur when we can't tell what part we
+ are referencing, and have to make conservative assumptions. */
+ bool implicit_uses;
+} *used_part_t;
+
+/* An array of used_part structures, indexed by variable uid. */
+
+static htab_t used_portions;
+
+struct used_part_map
+{
+ unsigned int uid;
+ used_part_t to;
+};
+
+/* Return true if the uid in the two used part maps are equal. */
+
+static int
+used_part_map_eq (const void *va, const void *vb)
+{
+ const struct used_part_map *a = (const struct used_part_map *) va;
+ const struct used_part_map *b = (const struct used_part_map *) vb;
+ return (a->uid == b->uid);
+}
+
+/* Hash a from uid in a used_part_map. */
+
+static unsigned int
+used_part_map_hash (const void *item)
+{
+ return ((const struct used_part_map *)item)->uid;
+}
+
+/* Free a used part map element. */
+
+static void
+free_used_part_map (void *item)
+{
+ free (((struct used_part_map *)item)->to);
+ free (item);
+}
+
+/* Lookup a used_part structure for a UID. */
+
+static used_part_t
+up_lookup (unsigned int uid)
+{
+ struct used_part_map *h, in;
+ in.uid = uid;
+ h = (struct used_part_map *) htab_find_with_hash (used_portions, &in, uid);
+ if (!h)
+ return NULL;
+ return h->to;
+}
+
+/* Insert the pair UID, TO into the used part hashtable. */
+
+static void
+up_insert (unsigned int uid, used_part_t to)
+{
+ struct used_part_map *h;
+ void **loc;
+
+ h = XNEW (struct used_part_map);
+ h->uid = uid;
+ h->to = to;
+ loc = htab_find_slot_with_hash (used_portions, h,
+ uid, INSERT);
+ if (*loc != NULL)
+ free (*loc);
+ *(struct used_part_map **) loc = h;
+}
+
+
+/* Given a variable uid, UID, get or create the entry in the used portions
+ table for the variable. */
+
+static used_part_t
+get_or_create_used_part_for (size_t uid)
+{
+ used_part_t up;
+ if ((up = up_lookup (uid)) == NULL)
+ {
+ up = XCNEW (struct used_part);
+ up->minused = INT_MAX;
+ up->maxused = 0;
+ up->explicit_uses = false;
+ up->implicit_uses = false;
+ }
+
+ return up;
+}
+
+
+/* Create and return a structure sub-variable for field FIELD of
+ variable VAR. */
+
+static tree
+create_sft (tree var, tree field)
+{
+ var_ann_t ann;
+ tree subvar = create_tag_raw (STRUCT_FIELD_TAG, TREE_TYPE (field), "SFT");
+
+ /* We need to copy the various flags from VAR to SUBVAR, so that
+ they are is_global_var iff the original variable was. */
+ DECL_CONTEXT (subvar) = DECL_CONTEXT (var);
+ MTAG_GLOBAL (subvar) = DECL_EXTERNAL (var);
+ TREE_PUBLIC (subvar) = TREE_PUBLIC (var);
+ TREE_STATIC (subvar) = TREE_STATIC (var);
+ TREE_READONLY (subvar) = TREE_READONLY (var);
+
+ /* Add the new variable to REFERENCED_VARS. */
+ ann = get_var_ann (subvar);
+ ann->type_mem_tag = NULL;
+ add_referenced_tmp_var (subvar);
+
+ return subvar;
+}
+
+
+/* Given an aggregate VAR, create the subvariables that represent its
+ fields. */
+
+static void
+create_overlap_variables_for (tree var)
+{
+ VEC(fieldoff_s,heap) *fieldstack = NULL;
+ used_part_t up;
+ size_t uid = DECL_UID (var);
+
+ if (!up_lookup (uid))
+ return;
+
+ up = up_lookup (uid);
+ push_fields_onto_fieldstack (TREE_TYPE (var), &fieldstack, 0, NULL);
+ if (VEC_length (fieldoff_s, fieldstack) != 0)
+ {
+ subvar_t *subvars;
+ fieldoff_s *fo;
+ bool notokay = false;
+ int fieldcount = 0;
+ int i;
+ HOST_WIDE_INT lastfooffset = -1;
+ HOST_WIDE_INT lastfosize = -1;
+ tree lastfotype = NULL_TREE;
+
+ /* Not all fields have DECL_SIZE set, and those that don't, we don't
+ know their size, and thus, can't handle.
+ The same is true of fields with DECL_SIZE that is not an integer
+ constant (such as variable sized fields).
+ Fields with offsets which are not constant will have an offset < 0
+ We *could* handle fields that are constant sized arrays, but
+ currently don't. Doing so would require some extra changes to
+ tree-ssa-operands.c. */
+
+ for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
+ {
+ if (!DECL_SIZE (fo->field)
+ || TREE_CODE (DECL_SIZE (fo->field)) != INTEGER_CST
+ || TREE_CODE (TREE_TYPE (fo->field)) == ARRAY_TYPE
+ || fo->offset < 0)
+ {
+ notokay = true;
+ break;
+ }
+ fieldcount++;
+ }
+
+ /* The current heuristic we use is as follows:
+ If the variable has no used portions in this function, no
+ structure vars are created for it.
+ Otherwise,
+ If the variable has less than SALIAS_MAX_IMPLICIT_FIELDS,
+ we always create structure vars for them.
+ If the variable has more than SALIAS_MAX_IMPLICIT_FIELDS, and
+ some explicit uses, we create structure vars for them.
+ If the variable has more than SALIAS_MAX_IMPLICIT_FIELDS, and
+ no explicit uses, we do not create structure vars for them.
+ */
+
+ if (fieldcount >= SALIAS_MAX_IMPLICIT_FIELDS
+ && !up->explicit_uses)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Variable ");
+ print_generic_expr (dump_file, var, 0);
+ fprintf (dump_file, " has no explicit uses in this function, and is > SALIAS_MAX_IMPLICIT_FIELDS, so skipping\n");
+ }
+ notokay = true;
+ }
+
+ /* Bail out, if we can't create overlap variables. */
+ if (notokay)
+ {
+ VEC_free (fieldoff_s, heap, fieldstack);
+ return;
+ }
+
+ /* Otherwise, create the variables. */
+ subvars = lookup_subvars_for_var (var);
+
+ sort_fieldstack (fieldstack);
+
+ for (i = VEC_length (fieldoff_s, fieldstack);
+ VEC_iterate (fieldoff_s, fieldstack, --i, fo);)
+ {
+ subvar_t sv;
+ HOST_WIDE_INT fosize;
+ tree currfotype;
+
+ fosize = TREE_INT_CST_LOW (DECL_SIZE (fo->field));
+ currfotype = TREE_TYPE (fo->field);
+
+ /* If this field isn't in the used portion,
+ or it has the exact same offset and size as the last
+ field, skip it. */
+
+ if (((fo->offset <= up->minused
+ && fo->offset + fosize <= up->minused)
+ || fo->offset >= up->maxused)
+ || (fo->offset == lastfooffset
+ && fosize == lastfosize
+ && currfotype == lastfotype))
+ continue;
+ sv = GGC_NEW (struct subvar);
+ sv->offset = fo->offset;
+ sv->size = fosize;
+ sv->next = *subvars;
+ sv->var = create_sft (var, fo->field);
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "structure field tag %s created for var %s",
+ get_name (sv->var), get_name (var));
+ fprintf (dump_file, " offset " HOST_WIDE_INT_PRINT_DEC,
+ sv->offset);
+ fprintf (dump_file, " size " HOST_WIDE_INT_PRINT_DEC,
+ sv->size);
+ fprintf (dump_file, "\n");
+ }
+
+ lastfotype = currfotype;
+ lastfooffset = fo->offset;
+ lastfosize = fosize;
+ *subvars = sv;
+ }
+
+ /* Once we have created subvars, the original is no longer call
+ clobbered on its own. Its call clobbered status depends
+ completely on the call clobbered status of the subvars.
+
+ add_referenced_var in the above loop will take care of
+ marking subvars of global variables as call clobbered for us
+ to start, since they are global as well. */
+ clear_call_clobbered (var);
+ }
+
+ VEC_free (fieldoff_s, heap, fieldstack);
+}
+
+
+/* Find the conservative answer to the question of what portions of what
+ structures are used by this statement. We assume that if we have a
+ component ref with a known size + offset, that we only need that part
+ of the structure. For unknown cases, or cases where we do something
+ to the whole structure, we assume we need to create fields for the
+ entire structure. */
+
+static tree
+find_used_portions (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
+{
+ switch (TREE_CODE (*tp))
+ {
+ case COMPONENT_REF:
+ {
+ HOST_WIDE_INT bitsize;
+ HOST_WIDE_INT bitmaxsize;
+ HOST_WIDE_INT bitpos;
+ tree ref;
+ ref = get_ref_base_and_extent (*tp, &bitpos, &bitsize, &bitmaxsize);
+ if (DECL_P (ref)
+ && var_can_have_subvars (ref)
+ && bitmaxsize != -1)
+ {
+ size_t uid = DECL_UID (ref);
+ used_part_t up;
+
+ up = get_or_create_used_part_for (uid);
+
+ if (bitpos <= up->minused)
+ up->minused = bitpos;
+ if ((bitpos + bitmaxsize >= up->maxused))
+ up->maxused = bitpos + bitmaxsize;
+
+ if (bitsize == bitmaxsize)
+ up->explicit_uses = true;
+ else
+ up->implicit_uses = true;
+ up_insert (uid, up);
+
+ *walk_subtrees = 0;
+ return NULL_TREE;
+ }
+ }
+ break;
+ /* This is here to make sure we mark the entire base variable as used
+ when you take its address. Because our used portion analysis is
+ simple, we aren't looking at casts or pointer arithmetic to see what
+ happens when you take the address. */
+ case ADDR_EXPR:
+ {
+ tree var = get_base_address (TREE_OPERAND (*tp, 0));
+
+ if (var
+ && DECL_P (var)
+ && DECL_SIZE (var)
+ && var_can_have_subvars (var)
+ && TREE_CODE (DECL_SIZE (var)) == INTEGER_CST)
+ {
+ used_part_t up;
+ size_t uid = DECL_UID (var);
+
+ up = get_or_create_used_part_for (uid);
+
+ up->minused = 0;
+ up->maxused = TREE_INT_CST_LOW (DECL_SIZE (var));
+ up->implicit_uses = true;
+
+ up_insert (uid, up);
+ *walk_subtrees = 0;
+ return NULL_TREE;
+ }
+ }
+ break;
+ case VAR_DECL:
+ case PARM_DECL:
+ case RESULT_DECL:
+ {
+ tree var = *tp;
+ if (DECL_SIZE (var)
+ && var_can_have_subvars (var)
+ && TREE_CODE (DECL_SIZE (var)) == INTEGER_CST)
+ {
+ used_part_t up;
+ size_t uid = DECL_UID (var);
+
+ up = get_or_create_used_part_for (uid);
+
+ up->minused = 0;
+ up->maxused = TREE_INT_CST_LOW (DECL_SIZE (var));
+ up->implicit_uses = true;
+
+ up_insert (uid, up);
+ *walk_subtrees = 0;
+ return NULL_TREE;
+ }
+ }
+ break;
+
+ default:
+ break;
+
+ }
+ return NULL_TREE;
+}
+
+/* Create structure field variables for structures used in this function. */
+
+static void
+create_structure_vars (void)
+{
+ basic_block bb;
+ safe_referenced_var_iterator rvi;
+ VEC (tree, heap) *varvec = NULL;
+ tree var;
+
+ used_portions = htab_create (10, used_part_map_hash, used_part_map_eq,
+ free_used_part_map);
+
+ FOR_EACH_BB (bb)
+ {
+ block_stmt_iterator bsi;
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ walk_tree_without_duplicates (bsi_stmt_ptr (bsi),
+ find_used_portions,
+ NULL);
+ }
+ }
+ FOR_EACH_REFERENCED_VAR_SAFE (var, varvec, rvi)
+ {
+ /* The C++ FE creates vars without DECL_SIZE set, for some reason. */
+ if (var
+ && DECL_SIZE (var)
+ && var_can_have_subvars (var)
+ && !MTAG_P (var)
+ && TREE_CODE (DECL_SIZE (var)) == INTEGER_CST)
+ create_overlap_variables_for (var);
+ }
+ htab_delete (used_portions);
+ VEC_free (tree, heap, varvec);
+
+}
+
+static bool
+gate_structure_vars (void)
+{
+ return flag_tree_salias != 0;
+}
+
+struct tree_opt_pass pass_create_structure_vars =
+{
+ "salias", /* name */
+ gate_structure_vars, /* gate */
+ create_structure_vars, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ 0, /* tv_id */
+ PROP_cfg, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_dump_func, /* todo_flags_finish */
+ 0 /* letter */
+};