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
+sort_tags_by_id (const void *pa, const void *pb)
+{
+ tree a = *(tree *)pa;
+ tree b = *(tree *)pb;
+
+ return DECL_UID (a) - DECL_UID (b);
+}
+
+/* Initialize WORKLIST to contain those memory tags that are marked call
+ clobbered. Initialized WORKLIST2 to contain the reasons these
+ memory tags escaped. */
+
+static void
+init_transitive_clobber_worklist (VEC (tree, heap) **worklist,
+ VEC (int, heap) **worklist2)
+{
+ referenced_var_iterator rvi;
+ tree curr;
+
+ FOR_EACH_REFERENCED_VAR (curr, rvi)
+ {
+ if (MTAG_P (curr) && is_call_clobbered (curr))
+ {
+ VEC_safe_push (tree, heap, *worklist, curr);
+ VEC_safe_push (int, heap, *worklist2, var_ann (curr)->escape_mask);
+ }
+ }
+}
+
+/* Add ALIAS to WORKLIST (and the reason for escaping REASON to WORKLIST2) if
+ ALIAS is not already marked call clobbered, and is a memory
+ tag. */
+
+static void
+add_to_worklist (tree alias, VEC (tree, heap) **worklist,
+ VEC (int, heap) **worklist2,
+ int reason)
+{
+ if (MTAG_P (alias) && !is_call_clobbered (alias))
+ {
+ VEC_safe_push (tree, heap, *worklist, alias);
+ VEC_safe_push (int, heap, *worklist2, reason);
+ }
+}
+
+/* Mark aliases of TAG as call clobbered, and place any tags on the
+ alias list that were not already call clobbered on WORKLIST. */
+
+static void
+mark_aliases_call_clobbered (tree tag, VEC (tree, heap) **worklist,
+ VEC (int, heap) **worklist2)
+{
+ unsigned int i;
+ VEC (tree, gc) *ma;
+ tree entry;
+ var_ann_t ta = var_ann (tag);
+
+ if (!MTAG_P (tag))
+ return;
+ ma = may_aliases (tag);
+ if (!ma)
+ return;
+
+ for (i = 0; VEC_iterate (tree, ma, i, entry); i++)
+ {
+ if (!unmodifiable_var_p (entry))
+ {
+ add_to_worklist (entry, worklist, worklist2, ta->escape_mask);
+ mark_call_clobbered (entry, ta->escape_mask);
+ }
+ }
+}
+
+/* Tags containing global vars need to be marked as global.
+ Tags containing call clobbered vars need to be marked as call
+ clobbered. */
+
+static void
+compute_tag_properties (void)
+{
+ referenced_var_iterator rvi;
+ tree tag;
+ bool changed = true;
+ VEC (tree, heap) *taglist = NULL;
+
+ FOR_EACH_REFERENCED_VAR (tag, rvi)
+ {
+ if (!MTAG_P (tag) || TREE_CODE (tag) == STRUCT_FIELD_TAG)
+ continue;
+ VEC_safe_push (tree, heap, taglist, tag);
+ }
+
+ /* We sort the taglist by DECL_UID, for two reasons.
+ 1. To get a sequential ordering to make the bitmap accesses
+ faster.
+ 2. Because of the way we compute aliases, it's more likely that
+ an earlier tag is included in a later tag, and this will reduce
+ the number of iterations.
+
+ If we had a real tag graph, we would just topo-order it and be
+ done with it. */
+ qsort (VEC_address (tree, taglist),
+ VEC_length (tree, taglist),
+ sizeof (tree),
+ sort_tags_by_id);
+
+ /* Go through each tag not marked as global, and if it aliases
+ global vars, mark it global.
+
+ If the tag contains call clobbered vars, mark it call
+ clobbered.
+
+ This loop iterates because tags may appear in the may-aliases
+ list of other tags when we group. */
+
+ while (changed)
+ {
+ unsigned int k;
+
+ changed = false;
+ for (k = 0; VEC_iterate (tree, taglist, k, tag); k++)
+ {
+ VEC (tree, gc) *ma;
+ unsigned int i;
+ tree entry;
+ bool tagcc = is_call_clobbered (tag);
+ bool tagglobal = MTAG_GLOBAL (tag);
+
+ if (tagcc && tagglobal)
+ continue;
+
+ ma = may_aliases (tag);
+ if (!ma)
+ continue;
+
+ for (i = 0; VEC_iterate (tree, ma, i, entry); i++)
+ {
+ /* Call clobbered entries cause the tag to be marked
+ call clobbered. */
+ if (!tagcc && is_call_clobbered (entry))
+ {
+ mark_call_clobbered (tag, var_ann (entry)->escape_mask);
+ tagcc = true;
+ changed = true;
+ }
+
+ /* Global vars cause the tag to be marked global. */
+ if (!tagglobal && is_global_var (entry))
+ {
+ MTAG_GLOBAL (tag) = true;
+ changed = true;
+ tagglobal = true;
+ }
+
+ /* Early exit once both global and cc are set, since the
+ loop can't do any more than that. */
+ if (tagcc && tagglobal)
+ break;
+ }
+ }
+ }
+ VEC_free (tree, heap, taglist);
+}
+
+/* Set up the initial variable clobbers and globalness.
+ When this function completes, only tags whose aliases need to be
+ clobbered will be set clobbered. Tags clobbered because they
+ contain call clobbered vars are handled in compute_tag_properties. */
+
+static void
+set_initial_properties (struct alias_info *ai)
+{
+ unsigned int i;
+ referenced_var_iterator rvi;
+ tree var;
+
+ FOR_EACH_REFERENCED_VAR (var, rvi)
+ {
+ if (is_global_var (var)
+ && (!var_can_have_subvars (var)
+ || get_subvars_for_var (var) == NULL))
+ {
+ if (!unmodifiable_var_p (var))
+ mark_call_clobbered (var, ESCAPE_IS_GLOBAL);
+ }
+ else if (TREE_CODE (var) == PARM_DECL
+ && default_def (var)
+ && POINTER_TYPE_P (TREE_TYPE (var)))
+ {
+ tree def = default_def (var);
+ get_ptr_info (def)->value_escapes_p = 1;
+ get_ptr_info (def)->escape_mask |= ESCAPE_IS_PARM;
+ }
+ }
+
+ 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);
+ var_ann_t v_ann = var_ann (SSA_NAME_VAR (ptr));
+
+ if (pi->value_escapes_p)
+ {
+ /* If PTR escapes then its associated memory tags and
+ pointed-to variables are call-clobbered. */
+ 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 (pi->pt_vars)
+ {
+ bitmap_iterator bi;
+ unsigned int j;
+ EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, j, bi)
+ if (!unmodifiable_var_p (referenced_var (j)))
+ mark_call_clobbered (referenced_var (j), pi->escape_mask);
+ }
+ }
+ /* If the name tag is call clobbered, so is the type tag
+ associated with the base VAR_DECL. */
+ if (pi->name_mem_tag
+ && v_ann->type_mem_tag
+ && is_call_clobbered (pi->name_mem_tag))
+ mark_call_clobbered (v_ann->type_mem_tag, pi->escape_mask);
+
+ /* Name tags and type 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
+ clobbered if value_escapes_p is true, regardless of whether
+ they point to global memory or not.
+ So removing this code and fixing all the bugs would be nice.
+ It is the cause of a bunch of clobbering. */
+ if ((pi->pt_global_mem || pi->pt_anything)
+ && pi->is_dereferenced && pi->name_mem_tag)
+ {
+ mark_call_clobbered (pi->name_mem_tag, ESCAPE_IS_GLOBAL);
+ MTAG_GLOBAL (pi->name_mem_tag) = true;
+ }
+
+ if ((pi->pt_global_mem || pi->pt_anything)
+ && pi->is_dereferenced && v_ann->type_mem_tag)
+ {
+ mark_call_clobbered (v_ann->type_mem_tag, ESCAPE_IS_GLOBAL);
+ MTAG_GLOBAL (v_ann->type_mem_tag) = true;
+ }
+ }
+}
+
+/* This variable is set to true if we are updating the used alone
+ information for TMT's, 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. */
+
+static void
+compute_call_clobbered (struct alias_info *ai)
+{
+ VEC (tree, heap) *worklist = NULL;
+ VEC(int,heap) *worklist2 = NULL;
+
+ set_initial_properties (ai);
+ init_transitive_clobber_worklist (&worklist, &worklist2);
+ while (VEC_length (tree, worklist) != 0)
+ {
+ tree curr = VEC_pop (tree, worklist);
+ int reason = VEC_pop (int, worklist2);
+
+ mark_call_clobbered (curr, reason);
+ mark_aliases_call_clobbered (curr, &worklist, &worklist2);
+ }
+ VEC_free (tree, heap, worklist);
+ VEC_free (int, heap, worklist2);
+ compute_tag_properties ();
+}
+
+
+/* Recalculate the used_alone information for TMT's . */
+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 TMT used alone bits to zero. */
+ updating_used_alone = true;
+ FOR_EACH_REFERENCED_VAR (var, rvi)
+ if (TREE_CODE (var) == TYPE_MEMORY_TAG)
+ TMT_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 TMT anywhere in a real virtual use or virtual
+ def, mark the TMT as used alone, and for renaming. */
+
+
+ FOR_EACH_BB (bb)
+ {
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ stmt = bsi_stmt (bsi);
+ if (TREE_CODE (stmt) == CALL_EXPR
+ || (TREE_CODE (stmt) == MODIFY_EXPR
+ && TREE_CODE (TREE_OPERAND (stmt, 1)) == CALL_EXPR))
+ VEC_safe_push (tree, heap, calls, stmt);
+ else
+ {
+ ssa_op_iter iter;
+
+ 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) == TYPE_MEMORY_TAG)
+ {
+ if (!TMT_USED_ALONE (svar))
+ {
+ TMT_USED_ALONE (svar) = true;
+ 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);
+ }
+ VEC_free (tree, heap, calls);
+ updating_used_alone = false;
+}
/* Compute may-alias information for every variable referenced in function
FNDECL.
memory tags. */
compute_flow_insensitive_aliasing (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
/* 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;
}
+
struct tree_opt_pass pass_may_alias =
{
"alias", /* name */
{
var_ann_t ann = var_ann (var);
- ann->is_alias_tag = 0;
+ ann->is_aliased = 0;
ann->may_aliases = NULL;
NUM_REFERENCES_CLEAR (ann);
var_ann_t v_ann = var_ann (SSA_NAME_VAR (ptr));
bitmap_iterator bi;
- if (pi->value_escapes_p || pi->pt_anything)
- {
- /* If PTR escapes or may point to anything, then its associated
- 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 (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
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 (pi->name_mem_tag
- && v_ann->type_mem_tag
- && is_call_clobbered (pi->name_mem_tag))
- mark_call_clobbered (v_ann->type_mem_tag);
}
}
fprintf (dump_file, "\n%s: Total number of aliased vops: %ld\n",
get_name (current_function_decl),
ai->total_alias_vops);
-
- /* Determine if we need to enable alias grouping. */
- if (ai->total_alias_vops >= MAX_ALIASED_VOPS)
- group_aliases (ai);
}
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
if (bitmap_bit_p (ai->dereferenced_ptrs_store, DECL_UID (var)))
bitmap_set_bit (ai->written_vars, DECL_UID (tag));
- /* If pointer VAR is a global variable or a PARM_DECL,
- then its memory tag should be considered a global
- 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
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);
- }
+ gcc_assert (!get_subvars_for_var (var));
}
mark_sym_for_renaming (var);
if (alias == al)
return;
- /* 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);
-
- /* Likewise. If ALIAS is call-clobbered, so is VAR. */
- else if (is_call_clobbered (alias))
- mark_call_clobbered (var);
-
VEC_safe_push (tree, gc, v_ann->may_aliases, alias);
- a_ann->is_alias_tag = 1;
+ a_ann->is_aliased = 1;
}
{
var_ann_t v_ann = var_ann (var);
VEC_replace (tree, v_ann->may_aliases, i, new_alias);
-
- /* If VAR is a call-clobbered variable, so is NEW_ALIAS.
- FIXME, call-clobbering should only depend on whether an address
- 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);
}
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. */
+ AI points to the alias information collected so far.
-bool
+ 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)
{
tree call = get_call_expr_in (stmt);
ai->num_calls_found++;
if (!TREE_SIDE_EFFECTS (call))
- ai->num_pure_const_calls_found++;
+ {
+ ai->num_pure_const_calls_found++;
+ return ESCAPE_TO_PURE_CONST;
+ }
- return true;
+ return ESCAPE_TO_CALL;
}
else if (TREE_CODE (stmt) == ASM_EXPR)
- return true;
+ return ESCAPE_TO_ASM;
else if (TREE_CODE (stmt) == MODIFY_EXPR)
{
tree lhs = TREE_OPERAND (stmt, 0);
/* If we couldn't recognize the LHS of the assignment, assume that it
is a non-local store. */
if (lhs == NULL_TREE)
- return true;
+ 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. */
&& POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND
(TREE_OPERAND (stmt, 1), 0)))
&& !POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt, 1))))
- return true;
+ return ESCAPE_BAD_CAST;
/* If the LHS is an SSA name, it can't possibly represent a non-local
memory store. */
if (TREE_CODE (lhs) == SSA_NAME)
- return false;
+ return NO_ESCAPE;
/* FIXME: LHS is not an SSA_NAME. Even if it's an assignment to a
local variables we cannot be sure if it will escape, because we
Midkiff, ``Escape analysis for java,'' in Proceedings of the
Conference on Object-Oriented Programming Systems, Languages, and
Applications (OOPSLA), pp. 1-19, 1999. */
- return true;
+ return ESCAPE_STORED_IN_GLOBAL;
}
else if (TREE_CODE (stmt) == RETURN_EXPR)
- return true;
+ return ESCAPE_TO_RETURN;
- return false;
+ return NO_ESCAPE;
}
/* Create a new memory tag of type TYPE.
if (tag == NULL_TREE)
tag = create_memory_tag (TREE_TYPE (TREE_TYPE (ptr)), false);
-
- /* 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_global_mem)
- mark_call_clobbered (tag);
-
return tag;
}
{
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)))
+ if (tag_set == curr->set)
{
tag = curr_tag;
break;
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;
}
TREE_THIS_VOLATILE (global_var) = 0;
TREE_ADDRESSABLE (global_var) = 0;
+ create_var_ann (global_var);
+ mark_call_clobbered (global_var, ESCAPE_UNKNOWN);
add_referenced_tmp_var (global_var);
mark_sym_for_renaming (global_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;
found_tag:
/* If VAR is not already PTR's type tag, add it to the may-alias set
for PTR's type tag. */
- gcc_assert (!MTAG_P (var_ann (var)->type_mem_tag));
+ gcc_assert (!MTAG_P (var));
tag = ann->type_mem_tag;
/* If VAR has subvars, add the subvars to the tag instead of the
variable. Implicit uses occur when we can't tell what part we
are referencing, and have to make conservative assumptions. */
bool implicit_uses;
+ /* True if the structure is only written to or taken its address. */
+ bool write_only;
} *used_part_t;
/* An array of used_part structures, indexed by variable uid. */
up->maxused = 0;
up->explicit_uses = false;
up->implicit_uses = false;
+ up->write_only = true;
}
return up;
}
-/* 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");
ann = get_var_ann (subvar);
ann->type_mem_tag = NULL;
add_referenced_tmp_var (subvar);
-
+ SFT_PARENT_VAR (subvar) = var;
+ SFT_OFFSET (subvar) = offset;
+ SFT_SIZE (subvar) = size;
return subvar;
}
used_part_t up;
size_t uid = DECL_UID (var);
- if (!up_lookup (uid))
+ up = up_lookup (uid);
+ if (!up
+ || up->write_only)
return;
- up = up_lookup (uid);
push_fields_onto_fieldstack (TREE_TYPE (var), &fieldstack, 0, NULL);
if (VEC_length (fieldoff_s, fieldstack) != 0)
{
&& 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");
}
entire structure. */
static tree
-find_used_portions (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
+find_used_portions (tree *tp, int *walk_subtrees, void *lhs_p)
{
switch (TREE_CODE (*tp))
{
+ case MODIFY_EXPR:
+ /* Recurse manually here to track whether the use is in the
+ LHS of an assignment. */
+ find_used_portions (&TREE_OPERAND (*tp, 0), walk_subtrees, tp);
+ return find_used_portions (&TREE_OPERAND (*tp, 1), walk_subtrees, NULL);
+ case REALPART_EXPR:
+ case IMAGPART_EXPR:
case COMPONENT_REF:
+ case ARRAY_REF:
{
HOST_WIDE_INT bitsize;
HOST_WIDE_INT bitmaxsize;
up->explicit_uses = true;
else
up->implicit_uses = true;
+ if (!lhs_p)
+ up->write_only = false;
up_insert (uid, up);
*walk_subtrees = 0;