#include "ipa-type-escape.h"
#include "vec.h"
#include "bitmap.h"
+#include "vecprim.h"
/* Obstack used to hold grouping bitmaps and other temporary bitmaps used by
aliasing */
/* Local functions. */
static void compute_flow_insensitive_aliasing (struct alias_info *);
+static void finalize_ref_all_pointers (struct alias_info *);
static void dump_alias_stats (FILE *);
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);
having to keep track of too many V_MAY_DEF expressions at call sites. */
tree global_var;
-DEF_VEC_I(int);
-DEF_VEC_ALLOC_I(int,heap);
-
/* qsort comparison function to sort type/name tags by DECL_UID. */
static int
unsigned int i;
referenced_var_iterator rvi;
tree var;
+ tree ptr;
FOR_EACH_REFERENCED_VAR (var, rvi)
{
}
}
- for (i = 0; i < VARRAY_ACTIVE_SIZE (ai->processed_ptrs); i++)
+ for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++)
{
- tree ptr = VARRAY_TREE (ai->processed_ptrs, i);
struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
var_ann_t v_ann = var_ann (SSA_NAME_VAR (ptr));
if (pi->name_mem_tag)
mark_call_clobbered (pi->name_mem_tag, pi->escape_mask);
- if (v_ann->type_mem_tag)
- mark_call_clobbered (v_ann->type_mem_tag, pi->escape_mask);
+ if (v_ann->symbol_mem_tag)
+ mark_call_clobbered (v_ann->symbol_mem_tag, pi->escape_mask);
if (pi->pt_vars)
{
mark_call_clobbered (referenced_var (j), pi->escape_mask);
}
}
- /* If the name tag is call clobbered, so is the type tag
+
+ /* If the name tag is call clobbered, so is the symbol tag
associated with the base VAR_DECL. */
if (pi->name_mem_tag
- && v_ann->type_mem_tag
+ && v_ann->symbol_mem_tag
&& is_call_clobbered (pi->name_mem_tag))
- mark_call_clobbered (v_ann->type_mem_tag, pi->escape_mask);
+ mark_call_clobbered (v_ann->symbol_mem_tag, pi->escape_mask);
- /* Name tags and type tags that we don't know where they point
+ /* Name tags and symbol tags that we don't know where they point
to, might point to global memory, and thus, are clobbered.
FIXME: This is not quite right. They should only be
}
if ((pi->pt_global_mem || pi->pt_anything)
- && pi->is_dereferenced && v_ann->type_mem_tag)
+ && pi->is_dereferenced
+ && v_ann->symbol_mem_tag)
{
- mark_call_clobbered (v_ann->type_mem_tag, ESCAPE_IS_GLOBAL);
- MTAG_GLOBAL (v_ann->type_mem_tag) = true;
+ mark_call_clobbered (v_ann->symbol_mem_tag, ESCAPE_IS_GLOBAL);
+ MTAG_GLOBAL (v_ann->symbol_mem_tag) = true;
}
}
}
+
+/* This variable is set to true if we are updating the used alone
+ information for SMTs, or are in a pass that is going to break it
+ temporarily. */
+bool updating_used_alone;
+
/* Compute which variables need to be marked call clobbered because
their tag is call clobbered, and which tags need to be marked
global because they contain global variables. */
compute_tag_properties ();
}
+
+/* Helper for recalculate_used_alone. Return a conservatively correct
+ answer as to whether STMT may make a store on the LHS to SYM. */
+
+static bool
+lhs_may_store_to (tree stmt, tree sym ATTRIBUTE_UNUSED)
+{
+ tree lhs = TREE_OPERAND (stmt, 0);
+
+ lhs = get_base_address (lhs);
+
+ if (!lhs)
+ return false;
+
+ if (TREE_CODE (lhs) == SSA_NAME)
+ return false;
+ /* We could do better here by looking at the type tag of LHS, but it
+ is unclear whether this is worth it. */
+ return true;
+}
+
+/* Recalculate the used_alone information for SMTs . */
+
+void
+recalculate_used_alone (void)
+{
+ VEC (tree, heap) *calls = NULL;
+ block_stmt_iterator bsi;
+ basic_block bb;
+ tree stmt;
+ size_t i;
+ referenced_var_iterator rvi;
+ tree var;
+
+ /* First, reset all the SMT used alone bits to zero. */
+ updating_used_alone = true;
+ FOR_EACH_REFERENCED_VAR (var, rvi)
+ if (TREE_CODE (var) == SYMBOL_MEMORY_TAG)
+ {
+ SMT_OLD_USED_ALONE (var) = SMT_USED_ALONE (var);
+ SMT_USED_ALONE (var) = 0;
+ }
+
+ /* Walk all the statements.
+ Calls get put into a list of statements to update, since we will
+ need to update operands on them if we make any changes.
+ If we see a bare use of a SMT anywhere in a real virtual use or virtual
+ def, mark the SMT as used alone, and for renaming. */
+ FOR_EACH_BB (bb)
+ {
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ bool iscall = false;
+ ssa_op_iter iter;
+
+ stmt = bsi_stmt (bsi);
+
+ if (TREE_CODE (stmt) == CALL_EXPR
+ || (TREE_CODE (stmt) == MODIFY_EXPR
+ && TREE_CODE (TREE_OPERAND (stmt, 1)) == CALL_EXPR))
+ {
+ iscall = true;
+ VEC_safe_push (tree, heap, calls, stmt);
+ }
+
+ FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter,
+ SSA_OP_VUSE | SSA_OP_VIRTUAL_DEFS)
+ {
+ tree svar = var;
+
+ if (TREE_CODE (var) == SSA_NAME)
+ svar = SSA_NAME_VAR (var);
+
+ if (TREE_CODE (svar) == SYMBOL_MEMORY_TAG)
+ {
+ /* We only care about the LHS on calls. */
+ if (iscall && !lhs_may_store_to (stmt, svar))
+ continue;
+
+ if (!SMT_USED_ALONE (svar))
+ {
+ SMT_USED_ALONE (svar) = true;
+
+ /* Only need to mark for renaming if it wasn't
+ used alone before. */
+ if (!SMT_OLD_USED_ALONE (svar))
+ mark_sym_for_renaming (svar);
+ }
+ }
+ }
+ }
+ }
+
+ /* Update the operands on all the calls we saw. */
+ if (calls)
+ {
+ for (i = 0; VEC_iterate (tree, calls, i, stmt); i++)
+ update_stmt (stmt);
+ }
+
+ /* We need to mark SMT's that are no longer used for renaming so the
+ symbols go away, or else verification will be angry with us, even
+ though they are dead. */
+ FOR_EACH_REFERENCED_VAR (var, rvi)
+ if (TREE_CODE (var) == SYMBOL_MEMORY_TAG)
+ {
+ if (SMT_OLD_USED_ALONE (var) && !SMT_USED_ALONE (var))
+ mark_sym_for_renaming (var);
+ }
+
+ VEC_free (tree, heap, calls);
+ updating_used_alone = false;
+}
+
/* Compute may-alias information for every variable referenced in function
FNDECL.
We have two classes of memory tags. Memory tags associated with the
pointed-to data type of the pointers in the program. These tags are
- called "type memory tag" (TMT). The other class are those associated
+ called "symbol memory tag" (SMT). The other class are those associated
with SSA_NAMEs, called "name memory tag" (NMT). The basic idea is that
when adding operands for an INDIRECT_REF *P_i, we will first check
whether P_i has a name tag, if it does we use it, because that will have
- more precise aliasing information. Otherwise, we use the standard type
+ more precise aliasing information. Otherwise, we use the standard symbol
tag.
In this phase, we go through all the pointers we found in points-to
3- Compute flow-insensitive aliases
- This pass will compare the alias set of every type memory tag and every
- addressable variable found in the program. Given a type memory tag TMT
- and an addressable variable V. If the alias sets of TMT and V conflict
- (as computed by may_alias_p), then V is marked as an alias tag and added
- to the alias set of TMT.
+ This pass will compare the alias set of every symbol memory tag and
+ every addressable variable found in the program. Given a symbol
+ memory tag SMT and an addressable variable V. If the alias sets of
+ SMT and V conflict (as computed by may_alias_p), then V is marked
+ as an alias tag and added to the alias set of SMT.
For instance, consider the following function:
return *p;
}
- After aliasing analysis has finished, the type memory tag for pointer
+ After aliasing analysis has finished, the symbol memory tag for pointer
'p' will have two aliases, namely variables 'a' and 'b'. Every time
pointer 'p' is dereferenced, we want to mark the operation as a
potential reference to 'a' and 'b'.
max-aliased-vops}), alias sets are grouped to avoid severe
compile-time slow downs and memory consumption. See group_aliases. */
-static void
+static unsigned int
compute_may_aliases (void)
{
struct alias_info *ai;
/* Compute flow-sensitive, points-to based aliasing for all the name
memory tags. Note that this pass needs to be done before flow
insensitive analysis because it uses the points-to information
- gathered before to mark call-clobbered type tags. */
+ gathered before to mark call-clobbered symbol tags. */
compute_flow_sensitive_aliasing (ai);
/* Compute type-based flow-insensitive aliasing for all the type
memory tags. */
compute_flow_insensitive_aliasing (ai);
+
+ /* Compute call clobbering information. */
+ compute_call_clobbered (ai);
/* Determine if we need to enable alias grouping. */
if (ai->total_alias_vops >= MAX_ALIASED_VOPS)
group_aliases (ai);
- /* Compute call clobbering information. */
- compute_call_clobbered (ai);
-
/* If the program has too many call-clobbered variables and/or function
calls, create .GLOBAL_VAR and use it to model call-clobbering
semantics at call sites. This reduces the number of virtual operands
aliasing precision. */
maybe_create_global_var (ai);
+ /* If the program contains ref-all pointers, finalize may-alias information
+ for them. This pass needs to be run after call-clobbering information
+ has been computed. */
+ if (ai->ref_all_symbol_mem_tag)
+ finalize_ref_all_pointers (ai);
+
/* Debugging dumps. */
if (dump_file)
{
/* Deallocate memory used by aliasing data structures. */
delete_alias_info (ai);
+ updating_used_alone = true;
{
block_stmt_iterator bsi;
basic_block bb;
}
}
}
-
+ recalculate_used_alone ();
+ updating_used_alone = false;
+ return 0;
}
+
struct tree_opt_pass pass_may_alias =
{
"alias", /* name */
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->processed_ptrs = VEC_alloc (tree, heap, 50);
ai->written_vars = BITMAP_ALLOC (&alias_obstack);
ai->dereferenced_ptrs_store = BITMAP_ALLOC (&alias_obstack);
ai->dereferenced_ptrs_load = BITMAP_ALLOC (&alias_obstack);
{
var_ann_t ann = var_ann (var);
- ann->is_alias_tag = 0;
+ ann->is_aliased = 0;
ann->may_aliases = NULL;
NUM_REFERENCES_CLEAR (ann);
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
+ || TREE_CODE (var) == SYMBOL_MEMORY_TAG
|| !is_global_var (var))
clear_call_clobbered (var);
}
tree var;
sbitmap_free (ai->ssa_names_visited);
- ai->processed_ptrs = NULL;
+ VEC_free (tree, heap, ai->processed_ptrs);
for (i = 0; i < ai->num_addressable_vars; i++)
free (ai->addressable_vars[i]);
delete_points_to_sets ();
}
+/* Used for hashing to identify pointer infos with identical
+ pt_vars bitmaps. */
+static int
+eq_ptr_info (const void *p1, const void *p2)
+{
+ const struct ptr_info_def *n1 = (const struct ptr_info_def *) p1;
+ const struct ptr_info_def *n2 = (const struct ptr_info_def *) p2;
+ return bitmap_equal_p (n1->pt_vars, n2->pt_vars);
+}
+
+static hashval_t
+ptr_info_hash (const void *p)
+{
+ const struct ptr_info_def *n = (const struct ptr_info_def *) p;
+ return bitmap_hash (n->pt_vars);
+}
+
/* 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
size_t i;
VEC (tree, heap) *with_ptvars = NULL;
tree ptr;
+ htab_t ptr_hash;
/* Collect the list of pointers with a non-empty points to set. */
for (i = 1; i < num_ssa_names; i++)
}
/* Set pt_anything on the pointers without pt_vars filled in so
- that they are assigned a type tag. */
-
+ that they are assigned a symbol tag. */
if (pi->pt_vars && !bitmap_empty_p (pi->pt_vars))
VEC_safe_push (tree, heap, with_ptvars, ptr);
else
if (!with_ptvars)
return;
+ ptr_hash = htab_create (10, ptr_info_hash, eq_ptr_info, NULL);
/* 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;
+ struct ptr_info_def **slot;
/* If PTR points to a set of variables, check if we don't
have another pointer Q with the same points-to set before
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++)
+
+ slot = (struct ptr_info_def **) htab_find_slot (ptr_hash, pi, INSERT);
+ if (*slot)
+ pi->name_mem_tag = (*slot)->name_mem_tag;
+ else
{
- struct ptr_info_def *qi = SSA_NAME_PTR_INFO (ptr2);
-
- if (bitmap_equal_p (pi->pt_vars, qi->pt_vars))
- {
- pi->name_mem_tag = qi->name_mem_tag;
- break;
- }
+ *slot = pi;
+ /* 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 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
/* Mark the new name tag for renaming. */
mark_sym_for_renaming (pi->name_mem_tag);
}
+ htab_delete (ptr_hash);
VEC_free (tree, heap, with_ptvars);
}
compute_flow_sensitive_aliasing (struct alias_info *ai)
{
size_t i;
+ tree ptr;
- for (i = 0; i < VARRAY_ACTIVE_SIZE (ai->processed_ptrs); i++)
+ for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++)
{
- tree ptr = VARRAY_TREE (ai->processed_ptrs, i);
if (!find_what_p_points_to (ptr))
set_pt_anything (ptr);
}
create_name_tags ();
- for (i = 0; i < VARRAY_ACTIVE_SIZE (ai->processed_ptrs); i++)
+ for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++)
{
unsigned j;
- tree ptr = VARRAY_TREE (ai->processed_ptrs, i);
struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
var_ann_t v_ann = var_ann (SSA_NAME_VAR (ptr));
bitmap_iterator bi;
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));
+ add_may_alias (v_ann->symbol_mem_tag, referenced_var (j));
}
}
}
addressable variables found in setup_pointers_and_addressables.
For every pointer P in AI->POINTERS and addressable variable V in
- AI->ADDRESSABLE_VARS, add V to the may-alias sets of P's type
- memory tag (TMT) if their alias sets conflict. V is then marked as
+ AI->ADDRESSABLE_VARS, add V to the may-alias sets of P's symbol
+ memory tag (SMT) if their alias sets conflict. V is then marked as
an alias tag so that the operand scanner knows that statements
containing V have aliased operands. */
ai->total_alias_vops = 0;
/* For every pointer P, determine which addressable variables may alias
- with P's type memory tag. */
+ with P's symbol memory tag. */
for (i = 0; i < ai->num_pointers; i++)
{
size_t j;
struct alias_map_d *p_map = ai->pointers[i];
- tree tag = var_ann (p_map->var)->type_mem_tag;
+ tree tag = var_ann (p_map->var)->symbol_mem_tag;
var_ann_t tag_ann = var_ann (tag);
+ tree var;
+
+ /* Call-clobbering information is not finalized yet at this point. */
+ if (PTR_IS_REF_ALL (p_map->var))
+ continue;
p_map->total_alias_vops = 0;
p_map->may_aliases = BITMAP_ALLOC (&alias_obstack);
+ /* Add any pre-existing may_aliases to the bitmap used to represent
+ TAG's alias set in case we need to group aliases. */
+ for (j = 0; VEC_iterate (tree, tag_ann->may_aliases, j, var); ++j)
+ bitmap_set_bit (p_map->may_aliases, DECL_UID (var));
+
for (j = 0; j < ai->num_addressable_vars; j++)
{
struct alias_map_d *v_map;
var_ann_t v_ann;
- tree var;
bool tag_stored_p, var_stored_p;
v_map = ai->addressable_vars[j];
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
+ For example, suppose that we have two memory tags SMT.1 and SMT.2
such that
- may-aliases (TMT.1) = { a }
- may-aliases (TMT.2) = { b }
+ may-aliases (SMT.1) = { a }
+ may-aliases (SMT.2) = { b }
- and the alias set number of TMT.1 conflicts with that of TMT.2.
+ and the alias set number of SMT.1 conflicts with that of SMT.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
+ SMT.1 and SMT.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).
{
size_t j;
struct alias_map_d *p_map1 = ai->pointers[i];
- tree tag1 = var_ann (p_map1->var)->type_mem_tag;
+ tree tag1 = var_ann (p_map1->var)->symbol_mem_tag;
bitmap may_aliases1 = p_map1->may_aliases;
+ if (PTR_IS_REF_ALL (p_map1->var))
+ continue;
+
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;
+ tree tag2 = var_ann (p_map2->var)->symbol_mem_tag;
bitmap may_aliases2 = p_map2->may_aliases;
+ if (PTR_IS_REF_ALL (p_map2->var))
+ continue;
+
/* 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, true))
continue;
}
+/* Finalize may-alias information for ref-all pointers. Traverse all
+ the addressable variables found in setup_pointers_and_addressables.
+
+ If flow-sensitive alias analysis has attached a name memory tag to
+ a ref-all pointer, we will use it for the dereferences because that
+ will have more precise aliasing information. But if there is no
+ name tag, we will use a special symbol tag that aliases all the
+ call-clobbered addressable variables. */
+
+static void
+finalize_ref_all_pointers (struct alias_info *ai)
+{
+ size_t i;
+
+ if (global_var)
+ add_may_alias (ai->ref_all_symbol_mem_tag, global_var);
+ else
+ {
+ /* First add the real call-clobbered variables. */
+ for (i = 0; i < ai->num_addressable_vars; i++)
+ {
+ tree var = ai->addressable_vars[i]->var;
+ if (is_call_clobbered (var))
+ add_may_alias (ai->ref_all_symbol_mem_tag, var);
+ }
+
+ /* Then add the call-clobbered pointer memory tags. See
+ compute_flow_insensitive_aliasing for the rationale. */
+ for (i = 0; i < ai->num_pointers; i++)
+ {
+ tree ptr = ai->pointers[i]->var, tag;
+ if (PTR_IS_REF_ALL (ptr))
+ continue;
+ tag = var_ann (ptr)->symbol_mem_tag;
+ if (is_call_clobbered (tag))
+ add_may_alias (ai->ref_all_symbol_mem_tag, tag);
+ }
+ }
+}
+
+
/* Comparison function for qsort used in group_aliases. */
static int
var_ann_t ann = var_ann (var);
/* Make TAG the unique alias of VAR. */
- ann->is_alias_tag = 0;
+ ann->is_aliased = 0;
ann->may_aliases = NULL;
/* Note that VAR and TAG may be the same if the function has no
group_aliases (struct alias_info *ai)
{
size_t i;
+ tree ptr;
/* Sort the POINTERS array in descending order of contributed
virtual operands. */
for (i = 0; i < ai->num_pointers; i++)
{
size_t j;
- tree tag1 = var_ann (ai->pointers[i]->var)->type_mem_tag;
+ tree tag1 = var_ann (ai->pointers[i]->var)->symbol_mem_tag;
bitmap tag1_aliases = ai->pointers[i]->may_aliases;
/* Skip tags that have been grouped already. */
if (ai->pointers[i]->grouped_p)
continue;
- /* See if TAG1 had any aliases in common with other type tags.
+ /* See if TAG1 had any aliases in common with other symbol tags.
If we find a TAG2 with common aliases with TAG1, add TAG2's
aliases into TAG1. */
for (j = i + 1; j < ai->num_pointers; j++)
if (bitmap_intersect_p (tag1_aliases, tag2_aliases))
{
- tree tag2 = var_ann (ai->pointers[j]->var)->type_mem_tag;
+ tree tag2 = var_ann (ai->pointers[j]->var)->symbol_mem_tag;
bitmap_ior_into (tag1_aliases, tag2_aliases);
/* Finally, all the variables that have been grouped cannot be in
the may-alias set of name memory tags. Suppose that we have
- grouped the aliases in this code so that may-aliases(a) = TMT.20
+ grouped the aliases in this code so that may-aliases(a) = SMT.20
p_5 = &a;
...
# a_9 = V_MAY_DEF <a_8>
p_5->field = 0
- ... Several modifications to TMT.20 ...
+ ... Several modifications to SMT.20 ...
# VUSE <a_9>
x_30 = p_5->field
Since p_5 points to 'a', the optimizers will try to propagate 0
into p_5->field, but that is wrong because there have been
- modifications to 'TMT.20' in between. To prevent this we have to
- replace 'a' with 'TMT.20' in the name tag of p_5. */
- for (i = 0; i < VARRAY_ACTIVE_SIZE (ai->processed_ptrs); i++)
+ modifications to 'SMT.20' in between. To prevent this we have to
+ replace 'a' with 'SMT.20' in the name tag of p_5. */
+ for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++)
{
size_t j;
- tree ptr = VARRAY_TREE (ai->processed_ptrs, i);
tree name_tag = SSA_NAME_PTR_INFO (ptr)->name_mem_tag;
VEC(tree,gc) *aliases;
tree alias;
/* Create ADDRESSABLE_VARS and POINTERS. Note that these arrays are
always going to be slightly bigger than we actually need them
because some TREE_ADDRESSABLE variables will be marked
- non-addressable below and only pointers with unique type tags are
+ non-addressable below and only pointers with unique symbol tags are
going to be added to POINTERS. */
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;
- /* Since we will be creating type memory tags within this loop, cache the
- value of NUM_REFERENCED_VARS to avoid processing the additional tags
- unnecessarily. */
+ /* Since we will be creating symbol memory tags within this loop,
+ cache the value of NUM_REFERENCED_VARS to avoid processing the
+ additional tags unnecessarily. */
n_vars = num_referenced_vars;
FOR_EACH_REFERENCED_VAR_SAFE (var, varvec, srvi)
/* Name memory tags already have flow-sensitive aliasing
information, so they need not be processed by
- compute_flow_insensitive_aliasing. Similarly, type memory
+ compute_flow_insensitive_aliasing. Similarly, symbol memory
tags are already accounted for when we process their
associated pointer.
}
/* Add pointer variables that have been dereferenced to the POINTERS
- array and create a type memory tag for them. */
+ array and create a symbol memory tag for them. */
if (POINTER_TYPE_P (TREE_TYPE (var)))
{
if ((bitmap_bit_p (ai->dereferenced_ptrs_store, DECL_UID (var))
tag = get_tmt_for (var, ai);
t_ann = var_ann (tag);
- /* The type tag will need to be renamed into SSA
+ /* The symbol 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. */
+ and we only create symbol 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);
+ if (v_ann->symbol_mem_tag)
+ mark_sym_for_renaming (v_ann->symbol_mem_tag);
/* Associate the tag with pointer VAR. */
- v_ann->type_mem_tag = tag;
+ v_ann->symbol_mem_tag = tag;
/* If pointer VAR has been used in a store operation,
then its memory tag must be marked as written-to. */
else
{
/* The pointer has not been dereferenced. If it had a
- type memory tag, remove it and mark the old tag for
+ symbol 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;
+ tree tag = ann->symbol_mem_tag;
if (tag)
{
mark_sym_for_renaming (tag);
- ann->type_mem_tag = NULL_TREE;
+ ann->symbol_mem_tag = NULL_TREE;
}
}
}
alias_stats.simple_queries++;
/* By convention, a variable cannot alias itself. */
- mem = var_ann (ptr)->type_mem_tag;
+ mem = var_ann (ptr)->symbol_mem_tag;
if (mem == var)
{
alias_stats.alias_noalias++;
alias_stats.simple_resolved++;
return false;
}
-
- /* If -fargument-noalias-global is >1, pointer arguments may
+
+ /* If -fargument-noalias-global is > 2, pointer arguments may
+ not point to anything else. */
+ if (flag_argument_noalias > 2 && TREE_CODE (ptr) == PARM_DECL)
+ {
+ alias_stats.alias_noalias++;
+ 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)
return false;
}
- gcc_assert (TREE_CODE (mem) == TYPE_MEMORY_TAG);
+ gcc_assert (TREE_CODE (mem) == SYMBOL_MEMORY_TAG);
alias_stats.tbaa_queries++;
return;
VEC_safe_push (tree, gc, v_ann->may_aliases, alias);
- a_ann->is_alias_tag = 1;
+ a_ann->is_aliased = 1;
}
3- STMT is an assignment to a non-local variable, or
4- STMT is a return statement.
- AI points to the alias information collected so far.
-
Return the type of escape site found, if we found one, or NO_ESCAPE
if none. */
enum escape_type
-is_escape_site (tree stmt, struct alias_info *ai)
+is_escape_site (tree stmt)
{
tree call = get_call_expr_in (stmt);
if (call != NULL_TREE)
{
- ai->num_calls_found++;
-
if (!TREE_SIDE_EFFECTS (call))
- {
- ai->num_pure_const_calls_found++;
- return ESCAPE_TO_PURE_CONST;
- }
+ return ESCAPE_TO_PURE_CONST;
return ESCAPE_TO_CALL;
}
if (lhs == NULL_TREE)
return ESCAPE_UNKNOWN;
- /* 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 ESCAPE_BAD_CAST;
+ 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)
+ {
+ tree from = TREE_TYPE (TREE_OPERAND (TREE_OPERAND (stmt, 1), 0));
+ tree to = TREE_TYPE (TREE_OPERAND (stmt, 1));
+
+ /* If the RHS is a conversion between a pointer and an integer, the
+ pointer escapes since we can't track the integer. */
+ if (POINTER_TYPE_P (from) && !POINTER_TYPE_P (to))
+ return ESCAPE_BAD_CAST;
+
+ /* Same if the RHS is a conversion between a regular pointer and a
+ ref-all pointer since we can't track the SMT of the former. */
+ if (POINTER_TYPE_P (from) && !TYPE_REF_CAN_ALIAS_ALL (from)
+ && POINTER_TYPE_P (to) && TYPE_REF_CAN_ALIAS_ALL (to))
+ return ESCAPE_BAD_CAST;
+ }
/* If the LHS is an SSA name, it can't possibly represent a non-local
memory store. */
create_memory_tag (tree type, bool is_type_tag)
{
var_ann_t ann;
- tree tag = create_tag_raw (is_type_tag ? TYPE_MEMORY_TAG : NAME_MEMORY_TAG,
- type, (is_type_tag) ? "TMT" : "NMT");
+ tree tag = create_tag_raw (is_type_tag ? SYMBOL_MEMORY_TAG : NAME_MEMORY_TAG,
+ type, (is_type_tag) ? "SMT" : "NMT");
/* By default, memory tags are local variables. Alias analysis will
determine whether they should be considered globals. */
TREE_ADDRESSABLE (tag) = 1;
ann = get_var_ann (tag);
- ann->type_mem_tag = NULL_TREE;
+ ann->symbol_mem_tag = NULL_TREE;
/* Add the tag to the symbol table. */
- add_referenced_tmp_var (tag);
+ add_referenced_var (tag);
return tag;
}
}
-/* Return the type memory tag associated to pointer PTR. A memory tag is an
- artificial variable that represents the memory location pointed-to by
- PTR. It is used to model the effects of pointer de-references on
- addressable variables.
+/* Return the symbol memory tag associated to pointer PTR. A memory
+ tag is an artificial variable that represents the memory location
+ pointed-to by PTR. It is used to model the effects of pointer
+ de-references on addressable variables.
- AI points to the data gathered during alias analysis. This function
- populates the array AI->POINTERS. */
+ AI points to the data gathered during alias analysis. This
+ function populates the array AI->POINTERS. */
static tree
get_tmt_for (tree ptr, struct alias_info *ai)
tree tag_type = TREE_TYPE (TREE_TYPE (ptr));
HOST_WIDE_INT tag_set = get_alias_set (tag_type);
+ /* We use a unique memory tag for all the ref-all pointers. */
+ if (PTR_IS_REF_ALL (ptr))
+ {
+ if (!ai->ref_all_symbol_mem_tag)
+ ai->ref_all_symbol_mem_tag = create_memory_tag (void_type_node, true);
+ return ai->ref_all_symbol_mem_tag;
+ }
+
/* To avoid creating unnecessary memory tags, only create one memory tag
per alias set class. Note that it may be tempting to group
memory tags based on conflicting alias sets instead of
for (i = 0, tag = NULL_TREE; i < ai->num_pointers; i++)
{
struct alias_map_d *curr = ai->pointers[i];
- 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)))
+ tree curr_tag = var_ann (curr->var)->symbol_mem_tag;
+ if (tag_set == curr->set)
{
tag = curr_tag;
break;
{
struct alias_map_d *alias_map;
- /* If PTR did not have a type tag already, create a new TMT.*
+ /* If PTR did not have a symbol tag already, create a new SMT.*
artificial variable representing the memory location
pointed-to by PTR. */
- if (var_ann (ptr)->type_mem_tag == NULL_TREE)
+ if (var_ann (ptr)->symbol_mem_tag == NULL_TREE)
tag = create_memory_tag (tag_type, true);
else
- tag = var_ann (ptr)->type_mem_tag;
+ tag = var_ann (ptr)->symbol_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
/* 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
+ /* Make sure that the symbol 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_var_ann (global_var);
mark_call_clobbered (global_var, ESCAPE_UNKNOWN);
- add_referenced_tmp_var (global_var);
+ add_referenced_var (global_var);
mark_sym_for_renaming (global_var);
}
FOR_EACH_REFERENCED_VAR (var, rvi)
{
var_ann_t ann = var_ann (var);
- if (ann->type_mem_tag)
+ if (ann->symbol_mem_tag)
dump_variable (file, var);
}
- fprintf (file, "\nType memory tags\n\n");
+ fprintf (file, "\nSymbol memory tags\n\n");
FOR_EACH_REFERENCED_VAR (var, rvi)
{
- if (TREE_CODE (var) == TYPE_MEMORY_TAG)
+ if (TREE_CODE (var) == SYMBOL_MEMORY_TAG)
dump_variable (file, var);
}
VEC(tree,gc) *aliases;
tree al;
- if (var_ann (sym)->is_alias_tag)
+ if (var_ann (sym)->is_aliased)
{
aliases = var_ann (tag)->may_aliases;
return false;
}
+/* 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. Return a memtag for the ptr, after adding the
+ proper may_aliases to it (which are the aliases of var, if it has any,
+ or var itself). */
-/* 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)
+static tree
+add_may_alias_for_new_tag (tree tag, 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;
+ var_ann_t v_ann = var_ann (var);
+ VEC(tree, gc) *aliases = v_ann->may_aliases;
- if (ann->type_mem_tag == NULL_TREE)
+ /* Case 1: |aliases| == 1 */
+ if ((aliases != NULL)
+ && (VEC_length (tree, aliases) == 1))
{
- 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;
- }
- }
+ tree ali = VEC_index (tree, aliases, 0);
- /* 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);
+ if (TREE_CODE (ali) == SYMBOL_MEMORY_TAG)
+ return ali;
}
-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));
- 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
+ /* Case 2: |aliases| == 0 */
+ if (aliases == NULL)
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)
+ else
{
- for (i = 0; VEC_iterate (tree, aliases, i, al); i++)
- mark_sym_for_renaming (al);
- }
+ /* Case 3: |aliases| > 1 */
+ unsigned i;
+ tree 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);
+ add_may_alias (tag, al);
}
- VEC_free (tree, heap, varvec);
-}
+ return tag;
+}
-/* Create a new type tag for PTR. Construct the may-alias list of this type
- tag so that it has the aliasing of VAR.
+/* Create a new symbol tag for PTR. Construct the may-alias list of this type
+ tag so that it has the aliasing of VAR, or of the relevant subvars of VAR
+ according to the location accessed by EXPR.
- Note, the set of aliases represented by the new type tag are not marked
+ Note, the set of aliases represented by the new symbol tag are not marked
for renaming. */
void
-new_type_alias (tree ptr, tree var)
+new_type_alias (tree ptr, tree var, tree expr)
{
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;
+ tree ali = NULL_TREE;
+ HOST_WIDE_INT offset, size, maxsize;
+ tree ref;
- gcc_assert (p_ann->type_mem_tag == NULL_TREE);
+ gcc_assert (p_ann->symbol_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
+ ref = get_ref_base_and_extent (expr, &offset, &size, &maxsize);
+ gcc_assert (ref);
+
+ tag = create_memory_tag (tag_type, true);
+ p_ann->symbol_mem_tag = tag;
+
+ /* Add VAR to the may-alias set of PTR's new symbol 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;
+ VEC (tree, heap) *overlaps = NULL;
+ unsigned int len;
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)
+ bool exact;
+
+ if (overlap_subvar (offset, maxsize, sv->var, &exact))
+ VEC_safe_push (tree, heap, overlaps, sv->var);
+ }
+ len = VEC_length (tree, overlaps);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "\nnumber of overlapping subvars = %u\n", len);
+ gcc_assert (len);
+
+ if (len == 1)
+ ali = add_may_alias_for_new_tag (tag, VEC_index (tree, overlaps, 0));
+ else if (len > 1)
+ {
+ unsigned int k;
+ tree sv_var;
+
+ for (k = 0; VEC_iterate (tree, overlaps, k, sv_var); k++)
{
- p_ann->type_mem_tag = ali;
- return;
+ ali = add_may_alias_for_new_tag (tag, sv_var);
+
+ if (ali != tag)
+ {
+ /* Can happen only if 'Case 1' of add_may_alias_for_new_tag
+ took place. Since more than one svar was found, we add
+ 'ali' as one of the may_aliases of the new tag. */
+ add_may_alias (tag, ali);
+ ali = tag;
+ }
}
}
+ }
+ else
+ ali = add_may_alias_for_new_tag (tag, var);
- 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);
- }
- }
+ p_ann->symbol_mem_tag = ali;
+ TREE_READONLY (tag) = TREE_READONLY (var);
+ MTAG_GLOBAL (tag) = is_global_var (var);
}
-
-
/* This represents the used range of a variable. */
typedef struct used_part
}
-/* Create and return a structure sub-variable for field type FIELD of
- variable VAR. */
+/* Create and return a structure sub-variable for field type FIELD at
+ offset OFFSET, with size SIZE, of variable VAR. */
static tree
-create_sft (tree var, tree field)
+create_sft (tree var, tree field, unsigned HOST_WIDE_INT offset,
+ unsigned HOST_WIDE_INT size)
{
var_ann_t ann;
tree subvar = create_tag_raw (STRUCT_FIELD_TAG, field, "SFT");
TREE_PUBLIC (subvar) = TREE_PUBLIC (var);
TREE_STATIC (subvar) = TREE_STATIC (var);
TREE_READONLY (subvar) = TREE_READONLY (var);
+ TREE_ADDRESSABLE (subvar) = TREE_ADDRESSABLE (var);
/* Add the new variable to REFERENCED_VARS. */
ann = get_var_ann (subvar);
- ann->type_mem_tag = NULL;
- add_referenced_tmp_var (subvar);
+ ann->symbol_mem_tag = NULL;
+ add_referenced_var (subvar);
SFT_PARENT_VAR (subvar) = var;
-
+ SFT_OFFSET (subvar) = offset;
+ SFT_SIZE (subvar) = size;
return subvar;
}
&& currfotype == lastfotype))
continue;
sv = GGC_NEW (struct subvar);
- sv->offset = fo->offset;
- sv->size = fosize;
sv->next = *subvars;
- sv->var = create_sft (var, fo->type);
+ sv->var = create_sft (var, fo->type, fo->offset, fosize);
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);
+ SFT_OFFSET (sv->var));
fprintf (dump_file, " size " HOST_WIDE_INT_PRINT_DEC,
- sv->size);
+ SFT_SIZE (sv->var));
fprintf (dump_file, "\n");
}
up->minused = 0;
up->maxused = TREE_INT_CST_LOW (DECL_SIZE (var));
up->implicit_uses = true;
+ if (!lhs_p)
+ up->write_only = false;
up_insert (uid, up);
*walk_subtrees = 0;
}
}
break;
+ case CALL_EXPR:
+ {
+ tree *arg;
+ for (arg = &TREE_OPERAND (*tp, 1); *arg; arg = &TREE_CHAIN (*arg))
+ {
+ if (TREE_CODE (TREE_VALUE (*arg)) != ADDR_EXPR)
+ find_used_portions (&TREE_VALUE (*arg), walk_subtrees, NULL);
+ }
+ *walk_subtrees = 0;
+ return NULL_TREE;
+ }
case VAR_DECL:
case PARM_DECL:
case RESULT_DECL:
/* Create structure field variables for structures used in this function. */
-static void
+static unsigned int
create_structure_vars (void)
{
basic_block bb;
}
htab_delete (used_portions);
VEC_free (tree, heap, varvec);
-
+ return 0;
}
static bool
TODO_dump_func, /* todo_flags_finish */
0 /* letter */
};
+
+/* Reset the DECL_CALL_CLOBBERED flags on our referenced vars. In
+ theory, this only needs to be done for globals. */
+
+static unsigned int
+reset_cc_flags (void)
+{
+ tree var;
+ referenced_var_iterator rvi;
+
+ FOR_EACH_REFERENCED_VAR (var, rvi)
+ DECL_CALL_CLOBBERED (var) = false;
+ return 0;
+}
+
+struct tree_opt_pass pass_reset_cc_flags =
+{
+ NULL, /* name */
+ NULL, /* gate */
+ reset_cc_flags, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ 0, /* tv_id */
+ PROP_referenced_vars |PROP_cfg, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ 0, /* todo_flags_finish */
+ 0 /* letter */
+};
OSDN Git Service
