/* 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.
#include "tree-gimple.h"
#include "tree-flow.h"
#include "tree-inline.h"
-#include "tree-alias-common.h"
#include "tree-pass.h"
#include "convert.h"
#include "params.h"
+#include "vec.h"
+/* '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. */
/* 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. */
- bitmap ssa_names_visited;
+ sbitmap ssa_names_visited;
/* Array of SSA_NAME pointers processed by the points-to collector. */
varray_type processed_ptrs;
/* Number of function calls found in the program. */
size_t num_calls_found;
+ /* Number of const/pure function calls found in the program. */
+ size_t num_pure_const_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. */
unsigned int simple_resolved;
unsigned int tbaa_queries;
unsigned int tbaa_resolved;
- unsigned int pta_queries;
- unsigned int pta_resolved;
};
static tree get_tmt_for (tree, struct alias_info *);
static tree get_nmt_for (tree);
static void add_may_alias (tree, 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 bool is_escape_site (tree, struct alias_info *);
static void add_pointed_to_var (struct alias_info *, tree, tree);
-static void add_pointed_to_expr (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. */
REFERENCED_VARS (I) is call-clobbered. */
bitmap call_clobbered_vars;
-/* 'true' after aliases have been computed (see compute_may_aliases). This
- is used by get_stmt_operands and its helpers to determine what to do
- when scanning an operand for a variable that may be aliased. If
- may-alias information is still not available, the statement is marked as
- having volatile operands. */
-bool aliases_computed_p;
+/* Addressable variables in the function. If bit I is set, then
+ REFERENCED_VARS (I) has had its address taken. Note that
+ CALL_CLOBBERED_VARS and ADDRESSABLE_VARS are not related. An
+ addressable variable is not necessarily call-clobbered (e.g., a
+ local addressable whose address does not escape) and not all
+ call-clobbered variables are addressable (e.g., a local static
+ variable). */
+bitmap addressable_vars;
/* When the program has too many call-clobbered variables and call-sites,
this variable is used to represent the clobbering effects of function
calls. In these cases, all the call clobbered variables in the program
are forced to alias this variable. This reduces compile times by not
- having to keep track of too many VDEF expressions at call sites. */
+ having to keep track of too many V_MAY_DEF expressions at call sites. */
tree global_var;
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;
}
p_6 = &b;
# p_1 = PHI <p_4(1), p_6(2)>;
- # a_7 = VDEF <a_3>;
- # b_8 = VDEF <b_5>;
+ # a_7 = V
_MAY_DEF <a_3>;
+ # b_8 = V_MAY_DEF <b_5>;
*p_1 = 3;
- # a_9 = VDEF <a_7>
+ # a_9 = V
_MAY_DEF <a_7>
# VUSE <b_8>
a_9 = b_8 + 2;
/* Deallocate memory used by aliasing data structures. */
delete_alias_info (ai);
- /* Indicate that may-alias information is now available. */
- aliases_computed_p = true;
+ {
+ 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 =
NULL, /* next */
0, /* static_pass_number */
TV_TREE_MAY_ALIAS, /* tv_id */
- PROP_cfg | PROP_ssa | PROP_pta, /* properties_required */
- 0, /* properties_provided */
+ PROP_cfg | PROP_ssa, /* properties_required */
+ 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 ATTRIBUTE_UNUSED, void *data)
+{
+ struct count_ptr_d *count_p = (struct count_ptr_d *) data;
+
+ 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 *
struct alias_info *ai;
ai = xcalloc (1, sizeof (struct alias_info));
- ai->ssa_names_visited = BITMAP_XMALLOC ();
+ 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 ();
+ ai->addresses_needed = BITMAP_ALLOC (NULL);
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 (NULL);
+ ai->dereferenced_ptrs_store = BITMAP_ALLOC (NULL);
+ ai->dereferenced_ptrs_load = BITMAP_ALLOC (NULL);
+
+ /* If aliases have been computed before, clear existing information. */
+ if (aliases_computed_p)
+ {
+ unsigned i;
+ basic_block bb;
+
+ /* Make sure that every statement has a valid set of operands.
+ If a statement needs to be scanned for operands while we
+ compute aliases, it may get erroneous operands because all
+ the alias relations are not built at that point.
+ FIXME: This code will become obsolete when operands are not
+ lazily updated. */
+ FOR_EACH_BB (bb)
+ {
+ block_stmt_iterator si;
+ for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
+ get_stmt_operands (bsi_stmt (si));
+ }
+
+ /* 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++)
+ {
+ tree var = referenced_var (i);
+ var_ann_t ann = var_ann (var);
+
+ ann->is_alias_tag = 0;
+ ann->may_aliases = NULL;
+
+ /* 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 (ann->mem_tag_kind == NAME_TAG
+ || ann->mem_tag_kind == TYPE_TAG
+ || !is_global_var (var))
+ clear_call_clobbered (var);
+ }
+
+ /* Clear flow-sensitive points-to information from each SSA name. */
+ for (i = 1; i < num_ssa_names; i++)
+ {
+ tree name = ssa_name (i);
+
+ if (!name || !POINTER_TYPE_P (TREE_TYPE (name)))
+ continue;
+
+ if (SSA_NAME_PTR_INFO (name))
+ {
+ struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name);
+
+ /* Clear all the flags but keep the name tag to
+ avoid creating new temporaries unnecessarily. If
+ this pointer is found to point to a subset or
+ 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)
+ bitmap_clear (pi->pt_vars);
+ }
+ }
+ }
+
+ /* Next time, we will need to reset alias information. */
+ aliases_computed_p = true;
return ai;
}
{
size_t i;
- BITMAP_XFREE (ai->ssa_names_visited);
+ sbitmap_free (ai->ssa_names_visited);
ai->processed_ptrs = NULL;
- BITMAP_XFREE (ai->addresses_needed);
+ BITMAP_FREE (ai->addresses_needed);
for (i = 0; i < ai->num_addressable_vars; 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);
free (ai);
}
static void
collect_points_to_info_for (struct alias_info *ai, tree ptr)
{
-#if defined ENABLE_CHECKING
- if (!POINTER_TYPE_P (TREE_TYPE (ptr)))
- abort ();
-#endif
+ gcc_assert (POINTER_TYPE_P (TREE_TYPE (ptr)));
- if (!bitmap_bit_p (ai->ssa_names_visited, SSA_NAME_VERSION (ptr)))
+ if (!TEST_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (ptr)))
{
- ssa_name_ann_t ann;
-
- bitmap_set_bit (ai->ssa_names_visited, SSA_NAME_VERSION (ptr));
- walk_use_def_chains (ptr, collect_points_to_info_r, ai);
-
+ 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);
-
- /* If we could not determine where PTR was pointing to, clear all the
- other points-to information. */
- ann = ssa_name_ann (ptr);
- if (ann->pt_anything)
- {
- ann->pt_malloc = 0;
- ann->pt_vars = NULL;
- }
- }
-}
-
-
-/* Helper for ptr_is_dereferenced_by. Called by walk_tree to look for
- 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 (TREE_CODE (*tp) == INDIRECT_REF
- && TREE_OPERAND (*tp, 0) == ptr)
- return *tp;
-
- return NULL_TREE;
-}
-
-
-/* Return true if STMT contains 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;
}
compute_points_to_and_addr_escape (struct alias_info *ai)
{
basic_block bb;
- size_t i;
+ unsigned i;
+ tree op;
+ ssa_op_iter iter;
timevar_push (TV_TREE_PTA);
for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
{
- use_optype uses;
- def_optype defs;
- vdef_optype vdefs;
- stmt_ann_t ann;
bitmap addr_taken;
tree stmt = bsi_stmt (si);
- bool stmt_escapes_p = is_escape_site (stmt, &ai->num_calls_found);
+ bool stmt_escapes_p = is_escape_site (stmt, ai);
+ bitmap_iterator bi;
/* Mark all the variables whose address are taken by the
statement. Note that this will miss all the addresses taken
get_stmt_operands (stmt);
addr_taken = addresses_taken (stmt);
if (addr_taken)
- EXECUTE_IF_SET_IN_BITMAP (addr_taken, 0, i,
- {
- tree var = referenced_var (i);
- bitmap_set_bit (ai->addresses_needed, var_ann (var)->uid);
- if (stmt_escapes_p)
- mark_call_clobbered (var);
- });
+ 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. 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,
- {
- tree var = referenced_var (i);
- mark_call_clobbered (var);
- });
-
- ann = stmt_ann (stmt);
- uses = USE_OPS (ann);
- for (i = 0; i < NUM_USES (uses); i++)
+ FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
{
- tree op = USE_OP (uses, i);
var_ann_t v_ann = var_ann (SSA_NAME_VAR (op));
- ssa_name_ann_t ptr_ann;
+ struct ptr_info_def *pi;
bool is_store;
+ unsigned num_uses, num_derefs;
/* If the operand's variable may be aliased, keep track
of how many times we've referenced it. This is used
collect_points_to_info_for (ai, op);
- ptr_ann = ssa_name_ann (op);
- if (ptr_is_dereferenced_by (op, stmt, &is_store))
- {
- /* If we found OP to point to a set of variables or
- malloc, then create a name memory tag for it. This
- gives more precise aliasing information, which helps
- the optimizers.
+ pi = SSA_NAME_PTR_INFO (op);
+ count_uses_and_derefs (op, stmt, &num_uses, &num_derefs,
+ &is_store);
- FIXME: Cycles in the SSA web and the lack of SSA
- information for structures will prevent the creation
- of name tags. Find ways around this limitation. */
- if (ptr_ann->pt_malloc || ptr_ann->pt_vars)
- ptr_ann->name_mem_tag = get_nmt_for (op);
+ if (num_derefs > 0)
+ {
+ /* 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
else
bitmap_set_bit (ai->dereferenced_ptrs_load, v_ann->uid);
}
- else if (stmt_escapes_p)
+
+ if (stmt_escapes_p && num_derefs < num_uses)
{
- /* 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. */
- ptr_ann->value_escapes_p = 1;
+ /* If STMT is an escape point and STMT contains at
+ least one direct use of OP, then the value of OP
+ escapes and so the pointed-to variables need to
+ be marked call-clobbered. */
+ 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);
+ {
+ 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. */
- defs = DEF_OPS (ann);
- for (i = 0; i < NUM_DEFS (defs); i++)
+ FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
{
- tree op = DEF_OP (defs, i);
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 VDEF operands as being written to. */
- vdefs = VDEF_OPS (ann);
- for (i = 0; i < NUM_VDEFS (vdefs); i++)
+ /* Mark variables in V_MAY_DEF operands as being written to. */
+ FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_DEFS)
{
- tree op = VDEF_OP (vdefs, i);
- tree var = SSA_NAME_VAR (op);
+ tree var = DECL_P (op) ? op : 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);
+ mark_stmt_modified (stmt);
}
}
}
+/* 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
+ the result of a call to malloc (which means that P cannot point to
+ anything else nor alias any other variable).
+
+ If two pointers P and Q point to the same set of variables, they
+ are assigned the same name tag. */
+
+static void
+create_name_tags (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);
+ struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
+
+ if (pi->pt_anything || !pi->is_dereferenced)
+ {
+ /* No name tags for pointers that have not been
+ dereferenced or point to an arbitrary location. */
+ pi->name_mem_tag = NULL_TREE;
+ continue;
+ }
+
+ if (pi->pt_vars && !bitmap_empty_p (pi->pt_vars))
+ {
+ 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++)
+ {
+ 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;
+ }
+ }
+
+ /* 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);
+ }
+ 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;
+ }
+
+ TREE_THIS_VOLATILE (pi->name_mem_tag)
+ |= TREE_THIS_VOLATILE (TREE_TYPE (TREE_TYPE (ptr)));
+
+ /* Mark the new name tag for renaming. */
+ mark_sym_for_renaming (pi->name_mem_tag);
+ }
+}
+
+
+
/* For every pointer P_i in AI->PROCESSED_PTRS, create may-alias sets for
the name memory tag (NMT) associated with P_i. If P_i escapes, then its
name tag and the variables it points-to are call-clobbered. Finally, if
{
size_t i;
+ create_name_tags (ai);
+
for (i = 0; i < VARRAY_ACTIVE_SIZE (ai->processed_ptrs); i++)
{
- size_t j;
+ unsigned j;
tree ptr = VARRAY_TREE (ai->processed_ptrs, i);
- ssa_name_ann_t ann = ssa_name_ann (ptr);
+ struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
var_ann_t v_ann = var_ann (SSA_NAME_VAR (ptr));
+ bitmap_iterator bi;
- if (ann->value_escapes_p || ann->pt_anything)
+ if (pi->value_escapes_p || pi->pt_anything)
{
/* If PTR escapes or may point to anything, then its associated
- memory tags are call-clobbered. */
- if (ann->name_mem_tag)
- mark_call_clobbered (ann->name_mem_tag);
+ memory tags and pointed-to variables are call-clobbered. */
+ if (pi->name_mem_tag)
+ mark_call_clobbered (pi->name_mem_tag);
if (v_ann->type_mem_tag)
mark_call_clobbered (v_ann->type_mem_tag);
- /* If PTR may point to anything, mark call-clobbered all the
- addressables with the same alias set as the type pointed-to by
- PTR. */
- if (ann->pt_anything)
- {
- HOST_WIDE_INT ptr_set;
- ptr_set = get_alias_set (TREE_TYPE (TREE_TYPE (ptr)));
- for (j = 0; j < ai->num_addressable_vars; j++)
- {
- struct alias_map_d *alias_map = ai->addressable_vars[j];
- if (alias_map->set == ptr_set)
- mark_call_clobbered (alias_map->var);
- }
- }
-
- /* If PTR's value may escape and PTR is never dereferenced, we
- need to mark all the variables PTR points-to as
- call-clobbered. Note that we only need do this it PTR is
- never dereferenced. If PTR is dereferenced, it will have a
- name memory tag, which will have been marked call-clobbered.
- This will in turn mark the pointed-to variables as
- call-clobbered when we call add_may_alias below. */
- if (ann->value_escapes_p && !ann->name_mem_tag && ann->pt_vars)
- EXECUTE_IF_SET_IN_BITMAP (ann->pt_vars, 0, j,
- mark_call_clobbered (referenced_var (j)));
+ if (pi->pt_vars)
+ EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, j, bi)
+ {
+ mark_call_clobbered (referenced_var (j));
+ }
}
/* Set up aliasing information for PTR's name memory tag (if it has
one). Note that only pointers that have been dereferenced will
have a name memory tag. */
- if (ann->name_mem_tag && ann->pt_vars)
- EXECUTE_IF_SET_IN_BITMAP (ann->pt_vars, 0, j,
- add_may_alias (ann->name_mem_tag, referenced_var (j)));
+ if (pi->name_mem_tag && pi->pt_vars)
+ 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
associated with the base VAR_DECL. */
- if (ann->name_mem_tag
+ if (pi->name_mem_tag
&& v_ann->type_mem_tag
- && is_call_clobbered (ann->name_mem_tag))
+ && is_call_clobbered (pi->name_mem_tag))
mark_call_clobbered (v_ann->type_mem_tag);
}
}
/* 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, tag_ann->uid);
+ var_stored_p = is_call_clobbered (var)
+ || bitmap_bit_p (ai->written_vars, v_ann->uid);
if (!tag_stored_p && !var_stored_p)
continue;
-
+
if (may_alias_p (p_map->var, p_map->set, var, v_map->set))
{
+ subvar_t svars;
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);
/* Add VAR to TAG's may-aliases set. */
- add_may_alias (tag, var);
+
+ /* If this is an aggregate, we may have subvariables for it
+ that need to be pointed to. */
+ 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);
+ /* 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 (sv->var)->uid);
+ }
+ }
+ else
+ {
+ add_may_alias (tag, var);
+ /* 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);
+ }
/* 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);
+
+ }
+ }
+ }
+
+ /* Since this analysis is based exclusively on symbols, it fails to
+ handle cases where two pointers P and Q have different memory
+ tags with conflicting alias set numbers but no aliased symbols in
+ common.
+
+ For example, suppose that we have two memory tags TMT.1 and TMT.2
+ such that
+
+ may-aliases (TMT.1) = { a }
+ may-aliases (TMT.2) = { b }
+
+ and the alias set number of TMT.1 conflicts with that of TMT.2.
+ Since they don't have symbols in common, loads and stores from
+ TMT.1 and TMT.2 will seem independent of each other, which will
+ lead to the optimizers making invalid transformations (see
+ testsuite/gcc.c-torture/execute/pr15262-[12].c).
+
+ 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. */
+ 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;
+
+ 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;
+
+ /* If the pointers may not point to each other, do nothing. */
+ if (!may_alias_p (p_map1->var, p_map1->set, tag2, p_map2->set))
+ continue;
+
+ /* The two pointers may alias each other. If they already have
+ symbols in common, do nothing. */
+ if (sbitmap_any_common_bits (may_aliases1, may_aliases2))
+ continue;
+
+ if (sbitmap_first_set_bit (may_aliases2) >= 0)
+ {
+ size_t k;
+
+ /* 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);
+ }
+ 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);
+ SET_BIT (may_aliases1, var_ann (tag2)->uid);
}
}
}
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++)
{
sbitmap tag2_aliases = ai->pointers[j]->may_aliases;
- sbitmap_a_and_b (res, tag1_aliases, tag2_aliases);
- if (sbitmap_first_set_bit (res) >= 0)
+ if (sbitmap_any_common_bits (tag1_aliases, tag2_aliases))
{
tree tag2 = var_ann (ai->pointers[j]->var)->type_mem_tag;
p_5 = &a;
...
- # a_9 = VDEF <a_8>
+ # a_9 = V
_MAY_DEF <a_8>
p_5->field = 0
... Several modifications to TMT.20 ...
# VUSE <a_9>
{
size_t j;
tree ptr = VARRAY_TREE (ai->processed_ptrs, i);
- tree name_tag = ssa_name_ann (ptr)->name_mem_tag;
+ tree name_tag = SSA_NAME_PTR_INFO (ptr)->name_mem_tag;
varray_type aliases;
if (name_tag == NULL_TREE)
{
tree alias = VARRAY_TREE (aliases, j);
var_ann_t ann = var_ann (alias);
- if (ann->may_aliases)
+
+ if ((ann->mem_tag_kind == NOT_A_TAG
+ || ann->mem_tag_kind == STRUCT_FIELD)
+ && ann->may_aliases)
{
-#if defined ENABLE_CHECKING
- if (VARRAY_ACTIVE_SIZE (ann->may_aliases) != 1)
- abort ();
-#endif
- VARRAY_TREE (aliases, j) = VARRAY_TREE (ann->may_aliases, 0);
+ tree new_alias;
+
+ gcc_assert (VARRAY_ACTIVE_SIZE (ann->may_aliases) == 1);
+
+ new_alias = VARRAY_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",
struct alias_map_d *alias_map;
alias_map = xcalloc (1, sizeof (*alias_map));
alias_map->var = var;
-
- if (TREE_CODE (TREE_TYPE (var)) == ARRAY_TYPE)
- alias_map->set = get_alias_set (TREE_TYPE (TREE_TYPE (var)));
- else
- alias_map->set = get_alias_set (var);
+ alias_map->set = get_alias_set (var);
ai->addressable_vars[ai->num_addressable_vars++] = alias_map;
}
if (POINTER_TYPE_P (TREE_TYPE (var)))
{
- /* Since we don't keep track of volatile variables nor
- variables with hidden uses, assume that these pointers
- are used in indirect store operations. */
- var_ann_t ann = var_ann (var);
- if (TREE_THIS_VOLATILE (var) || ann->has_hidden_use)
- bitmap_set_bit (ai->dereferenced_ptrs_store, ann->uid);
+ /* 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);
num_pointers++;
}
{
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_may_aliases. Similarly,
- type memory tags are already accounted for when we process their
- associated pointer. */
- if (v_ann->mem_tag_kind != NOT_A_TAG)
+ /* 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.
+
+ 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 (v_ann->mem_tag_kind != NOT_A_TAG
+ && v_ann->mem_tag_kind != STRUCT_FIELD)
continue;
/* Remove the ADDRESSABLE flag from every addressable variable whose
of ADDR_EXPR constants into INDIRECT_REF expressions and the
removal of dead pointer assignments done by the early scalar
cleanup passes. */
- if (TREE_ADDRESSABLE (var))
+ if (TREE_ADDRESSABLE (var) && v_ann->mem_tag_kind != STRUCT_FIELD)
{
if (!bitmap_bit_p (ai->addresses_needed, v_ann->uid)
- && !v_ann->has_hidden_use
- && v_ann->mem_tag_kind == NOT_A_TAG
- && !needs_to_live_in_memory (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);
+ mark_sym_for_renaming (var);
+
+ if (var_can_have_subvars (var)
+ && (svars = get_subvars_for_var (var)))
+ {
+ subvar_t sv;
+
+ for (sv = svars; sv; sv = sv->next)
+ {
+ var_ann_t svann = var_ann (sv->var);
+ if (bitmap_bit_p (ai->addresses_needed, svann->uid))
+ 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);
+ }
+ 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);
+ if (var_can_have_subvars (var)
+ && (svars = get_subvars_for_var (var)))
+ {
+ subvar_t sv;
+ for (sv = svars; sv; sv = sv->next)
+ bitmap_set_bit (addressable_vars, var_ann (sv->var)->uid);
+ }
+
}
}
if (may_be_aliased (var))
{
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))
- && (bitmap_bit_p (ai->dereferenced_ptrs_store, v_ann->uid)
- || bitmap_bit_p (ai->dereferenced_ptrs_load, v_ann->uid)))
+ if (POINTER_TYPE_P (TREE_TYPE (var)))
{
- tree tag = v_ann->type_mem_tag;
- var_ann_t t_ann;
-
- /* If pointer VAR still doesn't have a memory tag associated with it,
- create it now or re-use an existing one. */
- if (tag == NULL_TREE)
- tag = get_tmt_for (var, ai);
- t_ann = var_ann (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 pointer VAR is a global variable or a PARM_DECL, then its
- memory tag should be considered a global variable. */
- if (TREE_CODE (var) == PARM_DECL || needs_to_live_in_memory (var))
- mark_call_clobbered (tag);
-
- /* 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);
- }
- }
-
- /* If we found no addressable variables, but we have more than one
- pointer, we will need to check for conflicts between the
- pointers. Otherwise, we would miss alias relations as in
- testsuite/gcc.dg/tree-ssa/20040319-1.c:
-
- struct bar { int count; int *arr;};
-
- void foo (struct bar *b)
+ if ((bitmap_bit_p (ai->dereferenced_ptrs_store, v_ann->uid)
+ || bitmap_bit_p (ai->dereferenced_ptrs_load, v_ann->uid)))
+ {
+ tree tag;
+ var_ann_t t_ann;
+
+ /* If pointer VAR still doesn't have a memory tag
+ associated with it, create it now or re-use an
+ existing one. */
+ tag = get_tmt_for (var, ai);
+ t_ann = var_ann (tag);
+
+ /* The type tag will need to be renamed into SSA
+ 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. */
+ 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 pointer VAR is a global variable or a PARM_DECL,
+ then its memory tag should be considered a global
+ variable. */
+ if (TREE_CODE (var) == PARM_DECL || is_global_var (var))
+ mark_call_clobbered (tag);
+
+ /* 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);
+ }
+ else
+ {
+ /* The pointer has not been dereferenced. If it had a
+ type memory tag, remove it and mark the old tag for
+ renaming to remove it out of the IL. */
+ var_ann_t ann = var_ann (var);
+ tree tag = ann->type_mem_tag;
+ if (tag)
{
- b->count = 0;
- *(b->arr) = 2;
- if (b->count == 0)
- abort ();
+ mark_sym_for_renaming (tag);
+ ann->type_mem_tag = NULL_TREE;
}
-
- b->count and *(b->arr) could be aliased if b->arr == &b->count.
- To do this, we add all the memory tags for the pointers in
- AI->POINTERS to AI->ADDRESSABLE_VARS, so that
- compute_flow_insensitive_aliasing will naturally compare every
- pointer to every type tag. */
- if (ai->num_addressable_vars == 0
- && ai->num_pointers > 1)
- {
- free (ai->addressable_vars);
- ai->addressable_vars = xcalloc (ai->num_pointers,
- sizeof (struct alias_map_d *));
- ai->num_addressable_vars = 0;
- for (i = 0; i < ai->num_pointers; i++)
- {
- struct alias_map_d *p = ai->pointers[i];
- tree tag = var_ann (p->var)->type_mem_tag;
- create_alias_map_for (tag, ai);
+ }
}
}
}
-/* Determine whether to use .GLOBAL_VAR to model call clobbering semantics. At
- every call site, we need to emit VDEF expressions to represent the
+/* Determine whether to use .GLOBAL_VAR to model call clobbering semantics. At
+ every call site, we need to emit V_MAY_DEF expressions to represent the
clobbering effects of the call for variables whose address escapes the
current function.
(.GLOBAL_VAR). This works well, but it ties the optimizer hands because
references to any call clobbered variable is a reference to .GLOBAL_VAR.
- The second approach is to emit a clobbering VDEF for every call-clobbered
- variable at call sites. This is the preferred way in terms of optimization
- opportunities but it may create too many VDEF operands if there are many
- call clobbered variables and function calls in the function.
+ The second approach is to emit a clobbering V_MAY_DEF for every
+ call-clobbered variable at call sites. This is the preferred way in terms
+ of optimization opportunities but it may create too many V_MAY_DEF operands
+ if there are many call clobbered variables and function calls in the
+ function.
To decide whether or not to use .GLOBAL_VAR we multiply the number of
function calls found by the number of call-clobbered variables. If that
static void
maybe_create_global_var (struct alias_info *ai)
{
- size_t i, n_clobbered;
+ unsigned i, n_clobbered;
+ bitmap_iterator bi;
- /* Count all the call-clobbered variables. */
- n_clobbered = 0;
- EXECUTE_IF_SET_IN_BITMAP (call_clobbered_vars, 0, i, n_clobbered++);
+ /* No need to create it, if we have one already. */
+ if (global_var == NULL_TREE)
+ {
+ /* Count all the call-clobbered variables. */
+ n_clobbered = 0;
+ EXECUTE_IF_SET_IN_BITMAP (call_clobbered_vars, 0, i, bi)
+ {
+ 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.
+
+ 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:
+
+ 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 ();
+ }
- foo ()
- {
- int a = f ();
- g ();
- h (a);
- }
+ /* 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);
- 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)
- 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,
- {
- 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);
- }
- });
+ /* 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);
+ }
}
tree var, HOST_WIDE_INT var_alias_set)
{
tree mem;
- var_ann_t v_ann, m_ann;
+ var_ann_t 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;
+ }
+
+ /* 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;
+ }
+
+ m_ann = var_ann (mem);
+
+ gcc_assert (m_ann->mem_tag_kind == TYPE_TAG);
+
+ alias_stats.tbaa_queries++;
- v_ann = var_ann (var);
- m_ann = var_ann (mem);
-
-#if defined ENABLE_CHECKING
- if (m_ann->mem_tag_kind != TYPE_TAG)
- abort ();
-#endif
-
- 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)
+ && 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)
/* If the alias sets don't conflict then MEM cannot alias VAR. */
if (!alias_sets_conflict_p (mem_alias_set, var_alias_set))
{
- /* Handle aliases to structure fields. If either VAR or MEM are
- aggregate types, they may not have conflicting types, but one of
- the structures could contain a pointer to the other one.
-
- For instance, given
-
- MEM -> struct P *p;
- VAR -> struct Q *q;
-
- It may happen that '*p' and '*q' can't alias because 'struct P'
- and 'struct Q' have non-conflicting alias sets. However, it could
- happen that one of the fields in 'struct P' is a 'struct Q *' or
- vice-versa.
-
- Therefore, we also need to check if 'struct P' aliases 'struct Q *'
- or 'struct Q' aliases 'struct P *'. Notice, that since GIMPLE
- does not have more than one-level pointers, we don't need to
- recurse into the structures. */
- if (AGGREGATE_TYPE_P (TREE_TYPE (mem))
- || AGGREGATE_TYPE_P (TREE_TYPE (var)))
- {
- tree ptr_to_var;
-
- if (TREE_CODE (TREE_TYPE (var)) == ARRAY_TYPE)
- ptr_to_var = TYPE_POINTER_TO (TREE_TYPE (TREE_TYPE (var)));
- else
- ptr_to_var = TYPE_POINTER_TO (TREE_TYPE (var));
-
- /* If no pointer-to VAR exists, then MEM can't alias VAR. */
- if (ptr_to_var == NULL_TREE)
- {
- alias_stats.alias_noalias++;
- alias_stats.tbaa_resolved++;
- return false;
- }
-
- /* If MEM doesn't alias a pointer to VAR and VAR doesn't alias
- PTR, then PTR can't alias VAR. */
- if (!alias_sets_conflict_p (mem_alias_set, get_alias_set (ptr_to_var))
- && !alias_sets_conflict_p (var_alias_set, get_alias_set (ptr)))
- {
- alias_stats.alias_noalias++;
- alias_stats.tbaa_resolved++;
- return false;
- }
- }
- else
- {
- alias_stats.alias_noalias++;
- alias_stats.tbaa_resolved++;
- return false;
- }
- }
-
- if (flag_tree_points_to != PTA_NONE)
- alias_stats.pta_queries++;
-
- /* If -ftree-points-to is given, check if PTR may point to VAR. */
- if (flag_tree_points_to == PTA_ANDERSEN
- && !ptr_may_alias_var (ptr, var))
- {
alias_stats.alias_noalias++;
- alias_stats.pta_resolved++;
+ alias_stats.tbaa_resolved++;
return false;
}
-
alias_stats.alias_mayalias++;
return true;
}
var_ann_t v_ann = get_var_ann (var);
var_ann_t a_ann = get_var_ann (alias);
-#if defined ENABLE_CHECKING
- if (var == alias)
- abort ();
-#endif
+ gcc_assert (var != alias);
if (v_ann->may_aliases == NULL)
VARRAY_TREE_INIT (v_ann->may_aliases, 2, "aliases");
if (alias == VARRAY_TREE (v_ann->may_aliases, i))
return;
- /* If VAR is a call-clobbered variable, so is its new ALIAS. */
+ /* If VAR is a call-clobbered variable, so is its new ALIAS.
+ FIXME, call-clobbering should only depend on whether an address
+ escapes. It should be independent of aliasing. */
if (is_call_clobbered (var))
mark_call_clobbered (alias);
}
-/* Given two pointers DEST and ORIG. Merge the points-to information in
- ORIG into DEST. AI is as in collect_points_to_info. */
+/* Replace alias I in the alias sets of VAR with NEW_ALIAS. */
+
+static void
+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;
+
+ /* If VAR is a call-clobbered variable, so is NEW_ALIAS.
+ FIXME, call-clobbering should only depend on whether an address
+ escapes. It should be independent of aliasing. */
+ if (is_call_clobbered (var))
+ mark_call_clobbered (new_alias);
+
+ /* Likewise. If NEW_ALIAS is call-clobbered, so is VAR. */
+ else if (is_call_clobbered (new_alias))
+ mark_call_clobbered (var);
+}
+
+
+/* Mark pointer PTR as pointing to an arbitrary memory location. */
+
+static void
+set_pt_anything (tree ptr)
+{
+ struct ptr_info_def *pi = get_ptr_info (ptr);
+
+ pi->pt_anything = 1;
+ pi->pt_malloc = 0;
+
+ /* 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)
+ {
+ 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 contains all the alias
+ information collected up to this point. */
static void
merge_pointed_to_info (struct alias_info *ai, tree dest, tree orig)
{
- ssa_name_ann_t dest_ann, orig_ann;
+ struct ptr_info_def *dest_pi, *orig_pi;
+
+ gcc_assert (dest != orig);
/* Make sure we have points-to information for ORIG. */
collect_points_to_info_for (ai, orig);
- dest_ann = get_ssa_name_ann (dest);
- orig_ann = ssa_name_ann (orig);
+ dest_pi = get_ptr_info (dest);
+ orig_pi = SSA_NAME_PTR_INFO (orig);
- if (orig_ann)
+ if (orig_pi)
{
- dest_ann->pt_anything |= orig_ann->pt_anything;
- dest_ann->pt_malloc |= orig_ann->pt_malloc;
-
- if (orig_ann->pt_vars)
+ gcc_assert (orig_pi != dest_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, however we currently do not
+ handle cases of more than one pointer pointing to the same
+ malloc'd area.
+
+ FIXME: If the merging comes from an expression that preserves
+ the PT_MALLOC attribute (copy assignment, address
+ arithmetic), 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. */
+ dest_pi->pt_malloc = 0;
+ if (orig_pi->pt_malloc || orig_pi->pt_anything)
+ set_pt_anything (dest);
+
+ dest_pi->pt_null |= orig_pi->pt_null;
+
+ if (!dest_pi->pt_anything
+ && orig_pi->pt_vars
+ && !bitmap_empty_p (orig_pi->pt_vars))
{
- if (dest_ann->pt_vars == NULL)
+ if (dest_pi->pt_vars == NULL)
{
- dest_ann->pt_vars = BITMAP_GGC_ALLOC ();
- bitmap_copy (dest_ann->pt_vars, orig_ann->pt_vars);
+ dest_pi->pt_vars = BITMAP_GGC_ALLOC ();
+ bitmap_copy (dest_pi->pt_vars, orig_pi->pt_vars);
}
else
- bitmap_a_or_b (dest_ann->pt_vars,
- dest_ann->pt_vars,
- orig_ann->pt_vars);
+ bitmap_ior_into (dest_pi->pt_vars, orig_pi->pt_vars);
}
}
+ else
+ set_pt_anything (dest);
}
-/* Add VALUE to the list of expressions pointed-to by PTR. */
+/* Add EXPR to the list of expressions pointed-to by PTR. */
static void
-add_pointed_to_expr (tree ptr, tree value)
+add_pointed_to_expr (struct alias_info *ai, tree ptr, tree expr)
{
- ssa_name_ann_t ann;
-
-#if defined ENABLE_CHECKING
- /* Pointer variables should have been handled by merge_pointed_to_info. */
- if (TREE_CODE (value) == SSA_NAME
- && POINTER_TYPE_P (TREE_TYPE (value)))
- abort ();
-#endif
-
- ann = get_ssa_name_ann (ptr);
-
- /* If VALUE is the result of a malloc-like call, then the area pointed to
- PTR is guaranteed to not alias with anything else. */
- if (TREE_CODE (value) == CALL_EXPR
- && (call_expr_flags (value) & (ECF_MALLOC | ECF_MAY_BE_ALLOCA)))
- ann->pt_malloc = 1;
- else
- ann->pt_anything = 1;
+ if (TREE_CODE (expr) == WITH_SIZE_EXPR)
+ expr = TREE_OPERAND (expr, 0);
- if (dump_file)
+ get_ptr_info (ptr);
+
+ if (TREE_CODE (expr) == CALL_EXPR
+ && (call_expr_flags (expr) & (ECF_MALLOC | ECF_MAY_BE_ALLOCA)))
{
- fprintf (dump_file, "Pointer ");
- print_generic_expr (dump_file, ptr, dump_flags);
- fprintf (dump_file, " points to ");
- if (ann->pt_malloc)
- fprintf (dump_file, "malloc space: ");
- else
- fprintf (dump_file, "an arbitrary address: ");
- print_generic_expr (dump_file, value, dump_flags);
- fprintf (dump_file, "\n");
+ /* 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 (integer_zerop (expr))
+ {
+ /* EXPR is the NULL pointer. Mark PTR as pointing to NULL. */
+ SSA_NAME_PTR_INFO (ptr)->pt_null = 1;
+ }
+ 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. */
+ PTR. AI points to the collected alias information. */
static void
add_pointed_to_var (struct alias_info *ai, tree ptr, tree value)
{
- if (TREE_CODE (value) == ADDR_EXPR)
+ struct ptr_info_def *pi = get_ptr_info (ptr);
+ tree pt_var = NULL_TREE;
+ HOST_WIDE_INT offset, size;
+ tree addrop;
+ size_t uid;
+ tree ref;
+ subvar_t svars;
+
+ gcc_assert (TREE_CODE (value) == ADDR_EXPR);
+
+ addrop = TREE_OPERAND (value, 0);
+ if (REFERENCE_CLASS_P (addrop))
+ pt_var = get_base_address (addrop);
+ else
+ pt_var = addrop;
+
+ /* If this is a component_ref, see if we can get a smaller number of
+ variables to take the address of. */
+ if (TREE_CODE (addrop) == COMPONENT_REF
+ && (ref = okay_component_ref_for_subvars (addrop, &offset ,&size)))
+ {
+ subvar_t sv;
+ svars = get_subvars_for_var (ref);
+
+ uid = var_ann (pt_var)->uid;
+
+ if (pi->pt_vars == NULL)
+ pi->pt_vars = BITMAP_GGC_ALLOC ();
+ /* 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;
+
+ for (sv = svars; sv; sv = sv->next)
+ {
+ if (overlap_subvar (offset, size, sv, NULL))
+ {
+ bitmap_set_bit (pi->pt_vars, var_ann (sv->var)->uid);
+ bitmap_set_bit (ai->addresses_needed, var_ann (sv->var)->uid);
+ }
+ }
+ }
+ else if (pt_var && SSA_VAR_P (pt_var))
{
- tree pt_var;
- ssa_name_ann_t ann;
- size_t uid;
-
- pt_var = TREE_OPERAND (value, 0);
- if (TREE_CODE_CLASS (TREE_CODE (pt_var)) == 'r')
- pt_var = get_base_address (pt_var);
+
+ uid = var_ann (pt_var)->uid;
+
+ if (pi->pt_vars == NULL)
+ pi->pt_vars = BITMAP_GGC_ALLOC ();
- if (pt_var && SSA_VAR_P (pt_var))
+ /* If this is an aggregate, we may have subvariables for it that need
+ to be pointed to. */
+ if (var_can_have_subvars (pt_var)
+ && (svars = get_subvars_for_var (pt_var)))
+ {
+ subvar_t sv;
+ for (sv = svars; sv; sv = sv->next)
+ {
+ uid = var_ann (sv->var)->uid;
+ bitmap_set_bit (ai->addresses_needed, uid);
+ bitmap_set_bit (pi->pt_vars, uid);
+ }
+ }
+ else
{
- ann = get_ssa_name_ann (ptr);
- uid = var_ann (pt_var)->uid;
- if (ann->pt_vars == NULL)
- ann->pt_vars = BITMAP_GGC_ALLOC ();
- bitmap_set_bit (ann->pt_vars, uid);
bitmap_set_bit (ai->addresses_needed, uid);
+ bitmap_set_bit (pi->pt_vars, uid);
}
- else
- add_pointed_to_expr (ptr, value);
+
+ /* 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;
}
- else
- add_pointed_to_expr (ptr, value);
}
fprintf (dump_file, "\n");
}
- if (TREE_CODE (stmt) == MODIFY_EXPR)
+ switch (TREE_CODE (stmt))
{
- tree rhs = TREE_OPERAND (stmt, 1);
- STRIP_NOPS (rhs);
+ case RETURN_EXPR:
+ gcc_assert (TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR);
+ stmt = TREE_OPERAND (stmt, 0);
+ /* FALLTHRU */
- /* Found P_i = CONST. */
- if (is_gimple_min_invariant (rhs))
- add_pointed_to_var (ai, var, rhs);
+ case MODIFY_EXPR:
+ {
+ tree rhs = TREE_OPERAND (stmt, 1);
+ STRIP_NOPS (rhs);
+ add_pointed_to_expr (ai, var, rhs);
+ break;
+ }
- /* Found P_i = Q_j. */
- else if (TREE_CODE (rhs) == SSA_NAME
- && POINTER_TYPE_P (TREE_TYPE (rhs)))
- merge_pointed_to_info (ai, var, rhs);
+ case ASM_EXPR:
+ /* Pointers defined by __asm__ statements can point anywhere. */
+ set_pt_anything (var);
+ break;
- /* Found P_i = PLUS_EXPR or P_i = MINUS_EXPR */
- else if (TREE_CODE (rhs) == PLUS_EXPR
- || TREE_CODE (rhs) == MINUS_EXPR)
+ case NOP_EXPR:
+ if (IS_EMPTY_STMT (stmt))
{
- tree op0 = TREE_OPERAND (rhs, 0);
- tree op1 = TREE_OPERAND (rhs, 1);
-
- if (TREE_CODE (op0) == SSA_NAME
- && POINTER_TYPE_P (TREE_TYPE (op0)))
- merge_pointed_to_info (ai, var, op0);
- else if (TREE_CODE (op1) == SSA_NAME
- && POINTER_TYPE_P (TREE_TYPE (op1)))
- merge_pointed_to_info (ai, var, op1);
- else if (is_gimple_min_invariant (op0))
- add_pointed_to_var (ai, var, op0);
- else if (is_gimple_min_invariant (op1))
- add_pointed_to_var (ai, var, op1);
+ 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 (var, rhs);
+ add_pointed_to_expr (ai, var, decl);
}
+ break;
- /* Something else. */
- else
- add_pointed_to_expr (var, rhs);
- }
- else if (TREE_CODE (stmt) == ASM_EXPR)
- {
- /* Pointers defined by __asm__ statements can point anywhere. */
- ssa_name_ann_t ann = get_ssa_name_ann (var);
- ann->pt_anything = 1;
- }
- else if (IS_EMPTY_STMT (stmt))
- {
- tree decl = SSA_NAME_VAR (var);
+ 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);
- if (TREE_CODE (decl) == PARM_DECL)
- add_pointed_to_expr (var, decl);
- else if (DECL_INITIAL (decl))
- add_pointed_to_var (ai, var, DECL_INITIAL (decl));
- else
- add_pointed_to_expr (var, decl);
- }
- else if (TREE_CODE (stmt) == 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:
+ /* Avoid unnecessary merges. */
+ if (lhs != var)
+ 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;
+ }
- if (is_gimple_min_invariant (var))
- add_pointed_to_var (ai, lhs, var);
- else if (TREE_CODE (var) == SSA_NAME)
- merge_pointed_to_info (ai, lhs, var);
- else
- abort ();
+ default:
+ gcc_unreachable ();
}
- else
- abort ();
-
+
return false;
}
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)
+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)
determine whether they should be considered globals. */
DECL_CONTEXT (tag) = current_function_decl;
- /* If the pointed-to type is volatile, so is the tag. */
- TREE_THIS_VOLATILE (tag) = TREE_THIS_VOLATILE (type);
-
/* Memory tags are by definition addressable. This also prevents
is_gimple_ref frome confusing memory tags with optimizable
variables. */
ann->mem_tag_kind = (is_type_tag) ? TYPE_TAG : NAME_TAG;
ann->type_mem_tag = NULL_TREE;
- /* Add the tag to the symbol table and mark it for renaming. */
+ /* Add the tag to the symbol table. */
add_referenced_tmp_var (tag);
- bitmap_set_bit (vars_to_rename, ann->uid);
return tag;
}
static tree
get_nmt_for (tree ptr)
{
- ssa_name_ann_t ptr_ann = ssa_name_ann (ptr);
- tree tag = ptr_ann->name_mem_tag;
+ struct ptr_info_def *pi = get_ptr_info (ptr);
+ tree tag = pi->name_mem_tag;
if (tag == NULL_TREE)
- {
- tag = create_memory_tag (TREE_TYPE (TREE_TYPE (ptr)), false);
-
- /* If PTR is a PARM_DECL, its memory tag should be considered a
- global variable. */
- if (TREE_CODE (SSA_NAME_VAR (ptr)) == PARM_DECL)
- mark_call_clobbered (tag);
+ tag = create_memory_tag (TREE_TYPE (TREE_TYPE (ptr)), false);
- /* Similarly, if PTR points to malloc, then TAG is a global. */
- if (ptr_ann->pt_malloc)
- mark_call_clobbered (tag);
- }
+ /* 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);
return 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
- && (flag_tree_points_to == PTA_NONE
- || same_points_to_set (curr->var, ptr)))
+ 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;
}
}
{
struct alias_map_d *alias_map;
- /* Create a new MT.* artificial variable representing the memory
- location pointed-to by PTR. */
- tag = create_memory_tag (tag_type, true);
+ /* If PTR did not have a type tag already, create a new TMT.*
+ artificial variable representing the memory location
+ pointed-to by PTR. */
+ if (var_ann (ptr)->type_mem_tag == NULL_TREE)
+ tag = create_memory_tag (tag_type, true);
+ else
+ tag = var_ann (ptr)->type_mem_tag;
/* 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
ai->pointers[ai->num_pointers++] = alias_map;
}
+ /* If the pointed-to type is volatile, so is the tag. */
+ TREE_THIS_VOLATILE (tag) |= TREE_THIS_VOLATILE (tag_type);
+
+ /* Make sure that the type tag has the same alias set as the
+ 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) = 0;
+ DECL_EXTERNAL (global_var) = 1;
TREE_STATIC (global_var) = 1;
TREE_USED (global_var) = 1;
DECL_CONTEXT (global_var) = NULL_TREE;
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 PTA queries:\t%u\n",
- alias_stats.pta_queries);
- fprintf (file, "Total PTA resolved:\t%u\n",
- alias_stats.pta_resolved);
}
const char *funcname
= lang_hooks.decl_printable_name (current_function_decl, 2);
- fprintf (file, "\nAlias information for %s\n\n", funcname);
+ 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++)
+ {
+ 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++)
{
tree var = referenced_var (i);
var_ann_t ann = var_ann (var);
- if (ann->may_aliases
- || ann->type_mem_tag
- || ann->is_alias_tag
- || ann->mem_tag_kind != NOT_A_TAG)
+ if (ann->type_mem_tag)
+ dump_variable (file, var);
+ }
+
+ fprintf (file, "\nType memory tags\n\n");
+ for (i = 0; i < num_referenced_vars; i++)
+ {
+ tree var = referenced_var (i);
+ var_ann_t ann = var_ann (var);
+ if (ann->mem_tag_kind == TYPE_TAG)
+ dump_variable (file, var);
+ }
+
+ fprintf (file, "\n\nFlow-sensitive alias information for %s\n\n", funcname);
+
+ fprintf (file, "SSA_NAME pointers\n\n");
+ for (i = 1; i < num_ssa_names; i++)
+ {
+ tree ptr = ssa_name (i);
+ struct ptr_info_def *pi;
+
+ if (ptr == NULL_TREE)
+ continue;
+
+ pi = SSA_NAME_PTR_INFO (ptr);
+ if (!SSA_NAME_IN_FREE_LIST (ptr)
+ && pi
+ && pi->name_mem_tag)
+ dump_points_to_info_for (file, ptr);
+ }
+
+ fprintf (file, "\nName memory tags\n\n");
+ for (i = 0; i < num_referenced_vars; i++)
+ {
+ tree var = referenced_var (i);
+ var_ann_t ann = var_ann (var);
+ if (ann->mem_tag_kind == NAME_TAG)
dump_variable (file, var);
}
}
+/* Return the alias information associated with pointer T. It creates a
+ new instance if none existed. */
+
+struct ptr_info_def *
+get_ptr_info (tree t)
+{
+ struct ptr_info_def *pi;
+
+ gcc_assert (POINTER_TYPE_P (TREE_TYPE (t)));
+
+ pi = SSA_NAME_PTR_INFO (t);
+ if (pi == NULL)
+ {
+ pi = ggc_alloc (sizeof (*pi));
+ memset ((void *)pi, 0, sizeof (*pi));
+ SSA_NAME_PTR_INFO (t) = pi;
+ }
+
+ return pi;
+}
+
+
/* Dump points-to information for SSA_NAME PTR into FILE. */
-static void
+void
dump_points_to_info_for (FILE *file, tree ptr)
{
- ssa_name_ann_t ann = ssa_name_ann (ptr);
+ struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
- fprintf (file, "Pointer ");
print_generic_expr (file, ptr, dump_flags);
- if (ann == NULL)
- return;
-
- if (ann->name_mem_tag)
+ if (pi)
{
- fprintf (file, ", name memory tag: ");
- print_generic_expr (file, ann->name_mem_tag, dump_flags);
- }
+ if (pi->name_mem_tag)
+ {
+ fprintf (file, ", name memory tag: ");
+ print_generic_expr (file, pi->name_mem_tag, dump_flags);
+ }
- if (ann->value_escapes_p)
- fprintf (file, ", its value escapes");
+ if (pi->is_dereferenced)
+ fprintf (file, ", is dereferenced");
- if (ann->pt_anything)
- fprintf (file, ", points-to anything");
+ if (pi->value_escapes_p)
+ fprintf (file, ", its value escapes");
- if (ann->pt_malloc)
- fprintf (file, ", points-to malloc");
+ if (pi->pt_anything)
+ fprintf (file, ", points-to anything");
- if (ann->pt_vars)
- {
- unsigned ix;
+ if (pi->pt_malloc)
+ fprintf (file, ", points-to malloc");
- fprintf (file, ", points-to vars: { ");
- EXECUTE_IF_SET_IN_BITMAP (ann->pt_vars, 0, ix,
- {
- print_generic_expr (file, referenced_var (ix), dump_flags);
- fprintf (file, " ");
- });
- fprintf (file, "}");
+ if (pi->pt_null)
+ fprintf (file, ", points-to NULL");
+
+ if (pi->pt_vars)
+ {
+ unsigned ix;
+ bitmap_iterator bi;
+
+ fprintf (file, ", points-to vars: { ");
+ EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, ix, bi)
+ {
+ print_generic_expr (file, referenced_var (ix), dump_flags);
+ fprintf (file, " ");
+ }
+ fprintf (file, "}");
+ }
}
fprintf (file, "\n");
}
+/* Dump points-to information for VAR into stderr. */
+
+void
+debug_points_to_info_for (tree var)
+{
+ dump_points_to_info_for (stderr, var);
+}
+
+
/* Dump points-to information into FILE. NOTE: This function is slow, as
it needs to traverse the whole CFG looking for pointer SSA_NAMEs. */
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);
{
tree phi;
- for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
+ for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
tree ptr = PHI_RESULT (phi);
if (POINTER_TYPE_P (TREE_TYPE (ptr)))
for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
{
- stmt_ann_t ann = stmt_ann (bsi_stmt (si));
- def_optype defs = DEF_OPS (ann);
- if (defs)
- for (i = 0; i < NUM_DEFS (defs); i++)
- if (POINTER_TYPE_P (TREE_TYPE (DEF_OP (defs, i))))
- dump_points_to_info_for (file, DEF_OP (defs, i));
+ tree stmt = bsi_stmt (si);
+ tree def;
+ FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
+ if (POINTER_TYPE_P (TREE_TYPE (def)))
+ dump_points_to_info_for (file, def);
}
}
{
dump_may_aliases_for (stderr, var);
}
+
+/* Return true if VAR may be aliased. */
+
+bool
+may_be_aliased (tree var)
+{
+ /* Obviously. */
+ if (TREE_ADDRESSABLE (var))
+ return true;
+
+ /* Globally visible variables can have their addresses taken by other
+ translation units. */
+ if (DECL_EXTERNAL (var) || TREE_PUBLIC (var))
+ return true;
+
+ /* Automatic variables can't have their addresses escape any other way.
+ This must be after the check for global variables, as extern declarations
+ do not have TREE_STATIC set. */
+ if (!TREE_STATIC (var))
+ return false;
+
+ /* If we're in unit-at-a-time mode, then we must have seen all occurrences
+ of address-of operators, and so we can trust TREE_ADDRESSABLE. Otherwise
+ we can only be sure the variable isn't addressable if it's local to the
+ current function. */
+ if (flag_unit_at_a_time)
+ return false;
+ if (decl_function_context (var) == current_function_decl)
+ return false;
+
+ return true;
+}
+
+
+/* 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)
+{
+ varray_type aliases;
+ tree tag;
+ var_ann_t ann = var_ann (ptr);
+ subvar_t svars;
+
+ if (ann->type_mem_tag == NULL_TREE)
+ {
+ size_t i;
+ tree q = NULL_TREE;
+ tree tag_type = TREE_TYPE (TREE_TYPE (ptr));
+ HOST_WIDE_INT tag_set = get_alias_set (tag_type);
+
+ /* 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 (i = 0; i < num_referenced_vars; i++)
+ {
+ q = referenced_var (i);
+
+ 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 (var_ann (var)->type_mem_tag == NOT_A_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)
+ {
+ size_t i;
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (aliases); i++)
+ mark_sym_for_renaming (VARRAY_TREE (aliases, i));
+ }
+
+ /* 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)
+ {
+ size_t i;
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (aliases); i++)
+ mark_sym_for_renaming (VARRAY_TREE (aliases, i));
+ }
+}
+
+
+/* This structure is simply used during pushing fields onto the fieldstack
+ to track the offset of the field, since bitpos_of_field gives it relative
+ to its immediate containing type, and we want it relative to the ultimate
+ containing object. */
+
+typedef struct fieldoff
+{
+ tree field;
+ HOST_WIDE_INT offset;
+} *fieldoff_t;
+
+DEF_VEC_MALLOC_P(fieldoff_t);
+
+/* Return the position, in bits, of FIELD_DECL from the beginning of its
+ structure.
+ Return -1 if the position is conditional or otherwise non-constant
+ integer. */
+
+static HOST_WIDE_INT
+bitpos_of_field (const tree fdecl)
+{
+
+ if (TREE_CODE (DECL_FIELD_OFFSET (fdecl)) != INTEGER_CST
+ || TREE_CODE (DECL_FIELD_BIT_OFFSET (fdecl)) != INTEGER_CST)
+ return -1;
+
+ return (tree_low_cst (DECL_FIELD_OFFSET (fdecl), 1) * 8)
+ + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl), 1);
+}
+
+/* Given a TYPE, and a vector of field offsets FIELDSTACK, push all the fields
+ of TYPE onto fieldstack, recording their offsets along the way.
+ OFFSET is used to keep track of the offset in this entire structure, rather
+ than just the immediately containing structure. */
+
+static void
+push_fields_onto_fieldstack (tree type, VEC(fieldoff_t) **fieldstack,
+ HOST_WIDE_INT offset)
+{
+ fieldoff_t pair;
+ tree field = TYPE_FIELDS (type);
+ if (!field)
+ return;
+ if (var_can_have_subvars (field)
+ && TREE_CODE (field) == FIELD_DECL)
+ {
+ size_t before = VEC_length (fieldoff_t, *fieldstack);
+ /* Empty structures may have actual size, like in C++. So see if we
+ actually end up pushing a field, and if not, if the size is nonzero,
+ push the field onto the stack */
+ push_fields_onto_fieldstack (TREE_TYPE (field), fieldstack, offset);
+ if (before == VEC_length (fieldoff_t, *fieldstack)
+ && DECL_SIZE (field)
+ && !integer_zerop (DECL_SIZE (field)))
+ {
+ pair = xmalloc (sizeof (struct fieldoff));
+ pair->field = field;
+ pair->offset = offset;
+ VEC_safe_push (fieldoff_t, *fieldstack, pair);
+ }
+ }
+ else if (TREE_CODE (field) == FIELD_DECL)
+ {
+ pair = xmalloc (sizeof (struct fieldoff));
+ pair->field = field;
+ pair->offset = offset + bitpos_of_field (field);
+ VEC_safe_push (fieldoff_t, *fieldstack, pair);
+ }
+ for (field = TREE_CHAIN (field); field; field = TREE_CHAIN (field))
+ {
+ if (TREE_CODE (field) != FIELD_DECL)
+ continue;
+ if (var_can_have_subvars (field))
+ {
+ size_t before = VEC_length (fieldoff_t, *fieldstack);
+ push_fields_onto_fieldstack (TREE_TYPE (field), fieldstack,
+ offset + bitpos_of_field (field));
+ /* Empty structures may have actual size, like in C++. So see if we
+ actually end up pushing a field, and if not, if the size is nonzero,
+ push the field onto the stack */
+ if (before == VEC_length (fieldoff_t, *fieldstack)
+ && DECL_SIZE (field)
+ && !integer_zerop (DECL_SIZE (field)))
+ {
+ pair = xmalloc (sizeof (struct fieldoff));
+ pair->field = field;
+ pair->offset = offset + bitpos_of_field (field);
+ VEC_safe_push (fieldoff_t, *fieldstack, pair);
+ }
+ }
+ else
+ {
+ pair = xmalloc (sizeof (struct fieldoff));
+ pair->field = field;
+ pair->offset = offset + bitpos_of_field (field);
+ VEC_safe_push (fieldoff_t, *fieldstack, pair);
+ }
+ }
+}
+
+
+/* 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 used_part_t *used_portions;
+
+/* 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 (used_portions[uid] == NULL)
+ {
+ up = xcalloc (1, sizeof (struct used_part));
+ up->minused = INT_MAX;
+ up->maxused = 0;
+ up->explicit_uses = false;
+ up->implicit_uses = false;
+ }
+ else
+ up = used_portions[uid];
+ return up;
+}
+
+/* qsort comparison function for two fieldoff_t's PA and PB */
+
+static int
+fieldoff_compare (const void *pa, const void *pb)
+{
+ const fieldoff_t foa = *(fieldoff_t *)pa;
+ const fieldoff_t fob = *(fieldoff_t *)pb;
+ HOST_WIDE_INT foasize, fobsize;
+ if (foa->offset != fob->offset)
+ return foa->offset - fob->offset;
+
+ foasize = TREE_INT_CST_LOW (DECL_SIZE (foa->field));
+ fobsize = TREE_INT_CST_LOW (DECL_SIZE (fob->field));
+ if (foasize != fobsize)
+ return foasize - fobsize;
+ return 0;
+}
+
+/* Given an aggregate VAR, create the subvariables that represent its
+ fields. */
+
+static void
+create_overlap_variables_for (tree var)
+{
+ VEC(fieldoff_t) *fieldstack = NULL;
+ used_part_t up;
+ size_t uid = var_ann (var)->uid;
+
+ if (used_portions[uid] == NULL)
+ return;
+
+ up = used_portions[uid];
+ push_fields_onto_fieldstack (TREE_TYPE (var), &fieldstack, 0);
+ if (VEC_length (fieldoff_t, fieldstack) != 0)
+ {
+ subvar_t *subvars;
+ fieldoff_t 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_t, 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;
+ }
+
+
+ /* Cleanup after ourselves if we can't create overlap variables. */
+ if (notokay)
+ {
+ while (VEC_length (fieldoff_t, fieldstack) != 0)
+ {
+ fo = VEC_pop (fieldoff_t, fieldstack);
+ free (fo);
+ }
+ VEC_free (fieldoff_t, fieldstack);
+ return;
+ }
+ /* Otherwise, create the variables. */
+ subvars = lookup_subvars_for_var (var);
+
+ qsort (VEC_address (fieldoff_t, fieldstack),
+ VEC_length (fieldoff_t, fieldstack),
+ sizeof (fieldoff_t),
+ fieldoff_compare);
+
+ while (VEC_length (fieldoff_t, fieldstack) != 0)
+ {
+ subvar_t sv;
+ HOST_WIDE_INT fosize;
+ var_ann_t ann;
+ tree currfotype;
+
+ fo = VEC_pop (fieldoff_t, fieldstack);
+ 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))
+ {
+ free (fo);
+ continue;
+ }
+ sv = ggc_alloc (sizeof (struct subvar));
+ sv->offset = fo->offset;
+ sv->size = fosize;
+ sv->next = *subvars;
+ sv->var = create_tmp_var_raw (TREE_TYPE (fo->field), "SFT");
+ 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");
+
+ }
+
+ /* We need to copy the various flags from var to sv->var, so that
+ they are is_global_var iff the original variable was. */
+
+ DECL_EXTERNAL (sv->var) = DECL_EXTERNAL (var);
+ TREE_PUBLIC (sv->var) = TREE_PUBLIC (var);
+ TREE_STATIC (sv->var) = TREE_STATIC (var);
+ TREE_READONLY (sv->var) = TREE_READONLY (var);
+
+ /* Like other memory tags, these need to be marked addressable to
+ keep is_gimple_reg from thinking they are real. */
+ TREE_ADDRESSABLE (sv->var) = 1;
+
+ DECL_CONTEXT (sv->var) = DECL_CONTEXT (var);
+
+ ann = get_var_ann (sv->var);
+ ann->mem_tag_kind = STRUCT_FIELD;
+ ann->type_mem_tag = NULL;
+ add_referenced_tmp_var (sv->var);
+
+ lastfotype = currfotype;
+ lastfooffset = fo->offset;
+ lastfosize = fosize;
+ *subvars = sv;
+ free (fo);
+ }
+
+ /* 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_t, 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 bitpos;
+ tree offset;
+ enum machine_mode mode;
+ int unsignedp;
+ int volatilep;
+ tree ref;
+ ref = get_inner_reference (*tp, &bitsize, &bitpos, &offset, &mode,
+ &unsignedp, &volatilep, false);
+ if (DECL_P (ref) && offset == NULL && bitsize != -1)
+ {
+ size_t uid = var_ann (ref)->uid;
+ used_part_t up;
+
+ up = get_or_create_used_part_for (uid);
+
+ if (bitpos <= up->minused)
+ up->minused = bitpos;
+ if ((bitpos + bitsize >= up->maxused))
+ up->maxused = bitpos + bitsize;
+
+ up->explicit_uses = true;
+ used_portions[uid] = up;
+
+ *walk_subtrees = 0;
+ return NULL_TREE;
+ }
+ else if (DECL_P (ref))
+ {
+ if (DECL_SIZE (ref)
+ && var_can_have_subvars (ref)
+ && TREE_CODE (DECL_SIZE (ref)) == INTEGER_CST)
+ {
+ used_part_t up;
+ size_t uid = var_ann (ref)->uid;
+
+ up = get_or_create_used_part_for (uid);
+
+ up->minused = 0;
+ up->maxused = TREE_INT_CST_LOW (DECL_SIZE (ref));
+
+ up->implicit_uses = true;
+
+ used_portions[uid] = up;
+
+ *walk_subtrees = 0;
+ return NULL_TREE;
+ }
+ }
+ }
+ break;
+ case VAR_DECL:
+ case PARM_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 = var_ann (var)->uid;
+
+ up = get_or_create_used_part_for (uid);
+
+ up->minused = 0;
+ up->maxused = TREE_INT_CST_LOW (DECL_SIZE (var));
+ up->implicit_uses = true;
+
+ used_portions[uid] = up;
+ *walk_subtrees = 0;
+ return NULL_TREE;
+ }
+ }
+ break;
+
+ default:
+ break;
+
+ }
+ return NULL_TREE;
+}
+
+/* We are about to create some new referenced variables, and we need the
+ before size. */
+
+static size_t old_referenced_vars;
+
+
+/* Create structure field variables for structures used in this function. */
+
+static void
+create_structure_vars (void)
+{
+ basic_block bb;
+ size_t i;
+
+ old_referenced_vars = num_referenced_vars;
+ used_portions = xcalloc (num_referenced_vars, sizeof (used_part_t));
+
+ 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 (i = 0; i < old_referenced_vars; i++)
+ {
+ tree var = referenced_var (i);
+ /* The C++ FE creates vars without DECL_SIZE set, for some reason. */
+ if (var
+ && DECL_SIZE (var)
+ && var_can_have_subvars (var)
+ && var_ann (var)->mem_tag_kind == NOT_A_TAG
+ && TREE_CODE (DECL_SIZE (var)) == INTEGER_CST)
+ create_overlap_variables_for (var);
+ }
+ for (i = 0; i < old_referenced_vars; i++)
+ free (used_portions[i]);
+
+ free (used_portions);
+}
+
+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 */
+};
OSDN Git Service
