#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "tree.h"
#include "rtl.h"
#include "tm_p.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "timevar.h"
#include "expr.h"
#include "ggc.h"
#include "langhooks.h"
#include "flags.h"
#include "function.h"
#include "diagnostic.h"
#include "tree-dump.h"
#include "tree-gimple.h"
#include "tree-flow.h"
#include "tree-inline.h"
#include "tree-pass.h"
#include "tree-ssa-structalias.h"
#include "convert.h"
#include "params.h"
#include "ipa-type-escape.h"
#include "vec.h"
#include "bitmap.h"
#include "vecprim.h"
#include "pointer-set.h"
static bitmap_obstack alias_obstack;
bool aliases_computed_p;
struct alias_map_d
{
tree var;
HOST_WIDE_INT set;
long total_alias_vops;
unsigned int grouped_p : 1;
bitmap may_aliases;
};
struct alias_stats_d
{
unsigned int alias_queries;
unsigned int alias_mayalias;
unsigned int alias_noalias;
unsigned int simple_queries;
unsigned int simple_resolved;
unsigned int tbaa_queries;
unsigned int tbaa_resolved;
unsigned int structnoaddress_queries;
unsigned int structnoaddress_resolved;
};
static struct alias_stats_d alias_stats;
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);
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_flow_sensitive_aliasing (struct alias_info *);
static void setup_pointers_and_addressables (struct alias_info *);
static void create_global_var (void);
static void maybe_create_global_var (struct alias_info *ai);
static void group_aliases (struct alias_info *);
static void set_pt_anything (tree ptr);
bitmap call_clobbered_vars;
bitmap addressable_vars;
tree global_var;
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);
}
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);
}
}
}
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);
}
}
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);
}
}
}
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);
}
qsort (VEC_address (tree, taglist),
VEC_length (tree, taglist),
sizeof (tree),
sort_tags_by_id);
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++)
{
if (!tagcc && is_call_clobbered (entry))
{
mark_call_clobbered (tag, var_ann (entry)->escape_mask);
tagcc = true;
changed = true;
}
if (!tagglobal && is_global_var (entry))
{
MTAG_GLOBAL (tag) = true;
changed = true;
tagglobal = true;
}
if (tagcc && tagglobal)
break;
}
}
}
VEC_free (tree, heap, taglist);
}
static void
set_initial_properties (struct alias_info *ai)
{
unsigned int i;
referenced_var_iterator rvi;
tree var;
tree ptr;
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; VEC_iterate (tree, ai->processed_ptrs, i, ptr); 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 (pi->name_mem_tag)
mark_call_clobbered (pi->name_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)
{
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 (pi->name_mem_tag
&& v_ann->symbol_mem_tag
&& is_call_clobbered (pi->name_mem_tag))
mark_call_clobbered (v_ann->symbol_mem_tag, pi->escape_mask);
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->symbol_mem_tag)
{
mark_call_clobbered (v_ann->symbol_mem_tag, ESCAPE_IS_GLOBAL);
MTAG_GLOBAL (v_ann->symbol_mem_tag) = true;
}
}
}
bool updating_used_alone;
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 ();
}
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;
return true;
}
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;
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;
}
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)
{
if (iscall && !lhs_may_store_to (stmt, svar))
continue;
if (!SMT_USED_ALONE (svar))
{
SMT_USED_ALONE (svar) = true;
if (!SMT_OLD_USED_ALONE (svar))
mark_sym_for_renaming (svar);
}
}
}
}
}
if (calls)
{
for (i = 0; VEC_iterate (tree, calls, i, stmt); i++)
update_stmt (stmt);
}
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;
}
static unsigned int
compute_may_aliases (void)
{
struct alias_info *ai;
memset (&alias_stats, 0, sizeof (alias_stats));
ai = init_alias_info ();
compute_points_to_sets (ai);
setup_pointers_and_addressables (ai);
compute_flow_sensitive_aliasing (ai);
compute_flow_insensitive_aliasing (ai);
compute_call_clobbered (ai);
if (ai->total_alias_vops >= MAX_ALIASED_VOPS)
group_aliases (ai);
maybe_create_global_var (ai);
if (ai->ref_all_symbol_mem_tag)
finalize_ref_all_pointers (ai);
if (dump_file)
{
dump_referenced_vars (dump_file);
if (dump_flags & TDF_STATS)
dump_alias_stats (dump_file);
dump_points_to_info (dump_file);
dump_alias_info (dump_file);
}
delete_alias_info (ai);
updating_used_alone = 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));
}
}
}
recalculate_used_alone ();
updating_used_alone = false;
return 0;
}
struct tree_opt_pass pass_may_alias =
{
"alias",
NULL,
compute_may_aliases,
NULL,
NULL,
0,
TV_TREE_MAY_ALIAS,
PROP_cfg | PROP_ssa,
PROP_alias,
0,
0,
TODO_dump_func | TODO_update_ssa
| TODO_ggc_collect | TODO_verify_ssa
| TODO_verify_stmts,
0
};
struct count_ptr_d
{
tree ptr;
unsigned count;
};
static tree
count_ptr_derefs (tree *tp, int *walk_subtrees, void *data)
{
struct count_ptr_d *count_p = (struct count_ptr_d *) data;
if (TREE_CODE (*tp) == ADDR_EXPR)
{
*walk_subtrees = 0;
return NULL_TREE;
}
if (INDIRECT_REF_P (*tp) && TREE_OPERAND (*tp, 0) == count_p->ptr)
count_p->count++;
return NULL_TREE;
}
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;
FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
if (use == ptr)
(*num_uses_p)++;
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);
}
static struct alias_info *
init_alias_info (void)
{
struct alias_info *ai;
referenced_var_iterator rvi;
tree var;
bitmap_obstack_initialize (&alias_obstack);
ai = XCNEW (struct alias_info);
ai->ssa_names_visited = sbitmap_alloc (num_ssa_names);
sbitmap_zero (ai->ssa_names_visited);
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);
if (aliases_computed_p)
{
unsigned i;
bitmap_clear (addressable_vars);
FOR_EACH_REFERENCED_VAR (var, rvi)
{
var_ann_t ann = var_ann (var);
ann->is_aliased = 0;
ann->may_aliases = NULL;
NUM_REFERENCES_CLEAR (ann);
if (TREE_CODE (var) == NAME_MEMORY_TAG
|| TREE_CODE (var) == SYMBOL_MEMORY_TAG
|| !is_global_var (var))
clear_call_clobbered (var);
}
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);
pi->pt_anything = 0;
pi->pt_null = 0;
pi->value_escapes_p = 0;
pi->is_dereferenced = 0;
if (pi->pt_vars)
bitmap_clear (pi->pt_vars);
}
}
}
aliases_computed_p = true;
return ai;
}
static void
delete_alias_info (struct alias_info *ai)
{
size_t i;
referenced_var_iterator rvi;
tree var;
sbitmap_free (ai->ssa_names_visited);
VEC_free (tree, heap, ai->processed_ptrs);
for (i = 0; i < ai->num_addressable_vars; i++)
free (ai->addressable_vars[i]);
FOR_EACH_REFERENCED_VAR(var, rvi)
{
var_ann_t ann = var_ann (var);
NUM_REFERENCES_CLEAR (ann);
}
free (ai->addressable_vars);
for (i = 0; i < ai->num_pointers; i++)
free (ai->pointers[i]);
free (ai->pointers);
BITMAP_FREE (ai->written_vars);
BITMAP_FREE (ai->dereferenced_ptrs_store);
BITMAP_FREE (ai->dereferenced_ptrs_load);
bitmap_obstack_release (&alias_obstack);
free (ai);
delete_points_to_sets ();
}
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);
}
static void
create_name_tags (void)
{
size_t i;
VEC (tree, heap) *with_ptvars = NULL;
tree ptr;
htab_t ptr_hash;
for (i = 1; i < num_ssa_names; i++)
{
tree ptr = ssa_name (i);
struct ptr_info_def *pi;
if (!ptr
|| !POINTER_TYPE_P (TREE_TYPE (ptr))
|| !SSA_NAME_PTR_INFO (ptr))
continue;
pi = SSA_NAME_PTR_INFO (ptr);
if (pi->pt_anything || !pi->is_dereferenced)
{
pi->name_mem_tag = NULL_TREE;
continue;
}
if (pi->pt_vars && !bitmap_empty_p (pi->pt_vars))
VEC_safe_push (tree, heap, with_ptvars, ptr);
else
set_pt_anything (ptr);
}
if (!with_ptvars)
return;
ptr_hash = htab_create (10, ptr_info_hash, eq_ptr_info, NULL);
for (i = 0; VEC_iterate (tree, with_ptvars, i, ptr); i++)
{
struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
tree old_name_tag = pi->name_mem_tag;
struct ptr_info_def **slot;
slot = (struct ptr_info_def **) htab_find_slot (ptr_hash, pi, INSERT);
if (*slot)
pi->name_mem_tag = (*slot)->name_mem_tag;
else
{
*slot = pi;
if (pi->name_mem_tag == NULL_TREE)
pi->name_mem_tag = get_nmt_for (ptr);
}
if (old_name_tag && old_name_tag != pi->name_mem_tag)
mark_sym_for_renaming (old_name_tag);
TREE_THIS_VOLATILE (pi->name_mem_tag)
|= TREE_THIS_VOLATILE (TREE_TYPE (TREE_TYPE (ptr)));
mark_sym_for_renaming (pi->name_mem_tag);
}
htab_delete (ptr_hash);
VEC_free (tree, heap, with_ptvars);
}
static void
compute_flow_sensitive_aliasing (struct alias_info *ai)
{
size_t i;
tree ptr;
for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++)
{
if (!find_what_p_points_to (ptr))
set_pt_anything (ptr);
}
create_name_tags ();
for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++)
{
unsigned j;
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 (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->symbol_mem_tag, referenced_var (j));
}
}
}
static void
compute_flow_insensitive_aliasing (struct alias_info *ai)
{
size_t i;
ai->total_alias_vops = 0;
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)->symbol_mem_tag;
var_ann_t tag_ann = var_ann (tag);
tree var;
if (PTR_IS_REF_ALL (p_map->var))
continue;
p_map->total_alias_vops = 0;
p_map->may_aliases = BITMAP_ALLOC (&alias_obstack);
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;
bool tag_stored_p, var_stored_p;
v_map = ai->addressable_vars[j];
var = v_map->var;
v_ann = var_ann (var);
tag_stored_p = is_call_clobbered (tag)
|| bitmap_bit_p (ai->written_vars, DECL_UID (tag));
var_stored_p = is_call_clobbered (var)
|| bitmap_bit_p (ai->written_vars, DECL_UID (var));
if (!tag_stored_p && !var_stored_p)
continue;
if (may_alias_p (p_map->var, p_map->set, var, v_map->set, false))
{
size_t num_tag_refs, num_var_refs;
num_tag_refs = NUM_REFERENCES (tag_ann);
num_var_refs = NUM_REFERENCES (v_ann);
gcc_assert (!var_can_have_subvars (var)
|| get_subvars_for_var (var) == NULL);
add_may_alias (tag, var);
bitmap_set_bit (p_map->may_aliases, DECL_UID (var));
ai->total_alias_vops += (num_var_refs + num_tag_refs);
p_map->total_alias_vops += (num_var_refs + num_tag_refs);
}
}
}
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)->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)->symbol_mem_tag;
bitmap may_aliases2 = p_map2->may_aliases;
if (PTR_IS_REF_ALL (p_map2->var))
continue;
if (!may_alias_p (p_map1->var, p_map1->set, tag2, p_map2->set, true))
continue;
if (bitmap_intersect_p (may_aliases1, may_aliases2))
continue;
if (!bitmap_empty_p (may_aliases2))
{
unsigned int k;
bitmap_iterator bi;
EXECUTE_IF_SET_IN_BITMAP (may_aliases2, 0, k, bi)
add_may_alias (tag1, referenced_var (k));
bitmap_ior_into (may_aliases1, may_aliases2);
}
else
{
add_may_alias (tag1, tag2);
bitmap_set_bit (may_aliases1, DECL_UID (tag2));
}
}
}
if (dump_file)
fprintf (dump_file, "\n%s: Total number of aliased vops: %ld\n",
get_name (current_function_decl),
ai->total_alias_vops);
}
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
{
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);
}
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);
}
}
}
static int
total_alias_vops_cmp (const void *p, const void *q)
{
const struct alias_map_d **p1 = (const struct alias_map_d **)p;
const struct alias_map_d **p2 = (const struct alias_map_d **)q;
long n1 = (*p1)->total_alias_vops;
long n2 = (*p2)->total_alias_vops;
return (n1 > n2 ? -1 : (n1 == n2) ? 0 : 1);
}
static void
group_aliases_into (tree tag, bitmap tag_aliases, struct alias_info *ai)
{
unsigned int i;
var_ann_t tag_ann = var_ann (tag);
size_t num_tag_refs = NUM_REFERENCES (tag_ann);
bitmap_iterator bi;
EXECUTE_IF_SET_IN_BITMAP (tag_aliases, 0, i, bi)
{
tree var = referenced_var (i);
var_ann_t ann = var_ann (var);
ann->is_aliased = 0;
ann->may_aliases = NULL;
if (var != tag)
add_may_alias (var, tag);
ai->total_alias_vops -= num_tag_refs;
}
ai->total_alias_vops += num_tag_refs;
tag_ann->may_aliases = NULL;
}
static void
group_aliases (struct alias_info *ai)
{
size_t i;
tree ptr;
qsort (ai->pointers, ai->num_pointers, sizeof (struct alias_map_d *),
total_alias_vops_cmp);
for (i = 0; i < ai->num_pointers; i++)
{
size_t j;
tree tag1 = var_ann (ai->pointers[i]->var)->symbol_mem_tag;
bitmap tag1_aliases = ai->pointers[i]->may_aliases;
if (ai->pointers[i]->grouped_p)
continue;
for (j = i + 1; j < ai->num_pointers; j++)
{
bitmap tag2_aliases = ai->pointers[j]->may_aliases;
if (bitmap_intersect_p (tag1_aliases, tag2_aliases))
{
tree tag2 = var_ann (ai->pointers[j]->var)->symbol_mem_tag;
bitmap_ior_into (tag1_aliases, tag2_aliases);
bitmap_clear (tag2_aliases);
var_ann (tag2)->may_aliases = NULL;
add_may_alias (tag2, tag1);
ai->pointers[j]->grouped_p = true;
}
}
group_aliases_into (tag1, tag1_aliases, ai);
if (ai->total_alias_vops < MAX_ALIASED_VOPS)
break;
}
for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++)
{
size_t j;
tree name_tag = SSA_NAME_PTR_INFO (ptr)->name_mem_tag;
VEC(tree,gc) *aliases;
tree alias;
if (name_tag == NULL_TREE)
continue;
aliases = var_ann (name_tag)->may_aliases;
for (j = 0; VEC_iterate (tree, aliases, j, alias); j++)
{
var_ann_t ann = var_ann (alias);
if ((!MTAG_P (alias)
|| TREE_CODE (alias) == STRUCT_FIELD_TAG)
&& ann->may_aliases)
{
tree new_alias;
gcc_assert (VEC_length (tree, ann->may_aliases) == 1);
new_alias = VEC_index (tree, ann->may_aliases, 0);
replace_may_alias (name_tag, j, new_alias);
}
}
}
if (dump_file)
fprintf (dump_file,
"%s: Total number of aliased vops after grouping: %ld%s\n",
get_name (current_function_decl),
ai->total_alias_vops,
(ai->total_alias_vops < 0) ? " (negative values are OK)" : "");
}
static void
create_alias_map_for (tree var, struct alias_info *ai)
{
struct alias_map_d *alias_map;
alias_map = XCNEW (struct alias_map_d);
alias_map->var = var;
alias_map->set = get_alias_set (var);
ai->addressable_vars[ai->num_addressable_vars++] = alias_map;
}
static void
setup_pointers_and_addressables (struct alias_info *ai)
{
size_t n_vars, num_addressable_vars, num_pointers;
referenced_var_iterator rvi;
tree var;
VEC (tree, heap) *varvec = NULL;
safe_referenced_var_iterator srvi;
num_addressable_vars = num_pointers = 0;
FOR_EACH_REFERENCED_VAR (var, rvi)
{
if (may_be_aliased (var))
num_addressable_vars++;
if (POINTER_TYPE_P (TREE_TYPE (var)))
{
if (TREE_THIS_VOLATILE (var))
bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var));
num_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;
n_vars = num_referenced_vars;
FOR_EACH_REFERENCED_VAR_SAFE (var, varvec, srvi)
{
var_ann_t v_ann = var_ann (var);
subvar_t svars;
if (MTAG_P (var) && TREE_CODE (var) != STRUCT_FIELD_TAG)
continue;
if (TREE_ADDRESSABLE (var))
{
if (!bitmap_bit_p (addressable_vars, DECL_UID (var))
&& TREE_CODE (var) != RESULT_DECL
&& !is_global_var (var))
{
bool okay_to_mark = true;
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)
{
if (bitmap_bit_p (addressable_vars, DECL_UID (sv->var)))
okay_to_mark = false;
mark_sym_for_renaming (sv->var);
}
}
if (okay_to_mark)
mark_non_addressable (var);
}
}
if (may_be_aliased (var)
&& (!var_can_have_subvars (var)
|| get_subvars_for_var (var) == NULL))
{
create_alias_map_for (var, ai);
mark_sym_for_renaming (var);
}
if (POINTER_TYPE_P (TREE_TYPE (var)))
{
if ((bitmap_bit_p (ai->dereferenced_ptrs_store, DECL_UID (var))
|| bitmap_bit_p (ai->dereferenced_ptrs_load, DECL_UID (var))))
{
tree tag;
var_ann_t t_ann;
tag = get_tmt_for (var, ai);
t_ann = var_ann (tag);
mark_sym_for_renaming (tag);
if (v_ann->symbol_mem_tag)
mark_sym_for_renaming (v_ann->symbol_mem_tag);
v_ann->symbol_mem_tag = tag;
if (bitmap_bit_p (ai->dereferenced_ptrs_store, DECL_UID (var)))
bitmap_set_bit (ai->written_vars, DECL_UID (tag));
NUM_REFERENCES_SET (t_ann,
NUM_REFERENCES (t_ann)
+ NUM_REFERENCES (v_ann));
}
else
{
var_ann_t ann = var_ann (var);
tree tag = ann->symbol_mem_tag;
if (tag)
{
mark_sym_for_renaming (tag);
ann->symbol_mem_tag = NULL_TREE;
}
}
}
}
VEC_free (tree, heap, varvec);
}
static void
maybe_create_global_var (struct alias_info *ai)
{
unsigned i, n_clobbered;
bitmap_iterator bi;
if (global_var == NULL_TREE)
{
n_clobbered = 0;
EXECUTE_IF_SET_IN_BITMAP (call_clobbered_vars, 0, i, bi)
{
n_clobbered++;
}
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 ();
}
EXECUTE_IF_SET_IN_BITMAP (call_clobbered_vars, 0, i, bi)
{
tree var = referenced_var (i);
if (global_var && var != global_var)
{
add_may_alias (var, global_var);
gcc_assert (!get_subvars_for_var (var));
}
mark_sym_for_renaming (var);
}
}
static bool
may_alias_p (tree ptr, HOST_WIDE_INT mem_alias_set,
tree var, HOST_WIDE_INT var_alias_set,
bool alias_set_only)
{
tree mem;
alias_stats.alias_queries++;
alias_stats.simple_queries++;
mem = var_ann (ptr)->symbol_mem_tag;
if (mem == var)
{
alias_stats.alias_noalias++;
alias_stats.simple_resolved++;
return false;
}
if (flag_argument_noalias > 2 && TREE_CODE (ptr) == PARM_DECL)
{
alias_stats.alias_noalias++;
alias_stats.simple_resolved++;
return false;
}
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 ((unmodifiable_var_p (mem) && !unmodifiable_var_p (var))
|| (unmodifiable_var_p (var) && !unmodifiable_var_p (mem)))
{
alias_stats.alias_noalias++;
alias_stats.simple_resolved++;
return false;
}
gcc_assert (TREE_CODE (mem) == SYMBOL_MEMORY_TAG);
alias_stats.tbaa_queries++;
if (!alias_sets_conflict_p (mem_alias_set, var_alias_set))
{
alias_stats.alias_noalias++;
alias_stats.tbaa_resolved++;
return false;
}
if ((mem_alias_set != 0) && (var_alias_set != 0))
{
tree ptr_type = TREE_TYPE (ptr);
tree var_type = TREE_TYPE (var);
if ((!alias_set_only) &&
ipa_type_escape_star_count_of_interesting_type (var_type) >= 0)
{
int ptr_star_count = 0;
while (POINTER_TYPE_P (ptr_type))
{
ptr_type = TREE_TYPE (ptr_type);
ptr_star_count++;
}
if (ptr_star_count > 0)
{
alias_stats.structnoaddress_queries++;
if (ipa_type_escape_field_does_not_clobber_p (var_type,
TREE_TYPE (ptr)))
{
alias_stats.structnoaddress_resolved++;
alias_stats.alias_noalias++;
return false;
}
}
else if (ptr_star_count == 0)
{
alias_stats.structnoaddress_queries++;
alias_stats.structnoaddress_resolved++;
alias_stats.alias_noalias++;
return false;
}
}
}
alias_stats.alias_mayalias++;
return true;
}
static void
add_may_alias (tree var, tree alias)
{
size_t i;
var_ann_t v_ann = get_var_ann (var);
var_ann_t a_ann = get_var_ann (alias);
tree al;
gcc_assert (var != alias);
#if 1
TREE_ADDRESSABLE (alias) = 1;
#else
gcc_assert (may_be_aliased (alias));
#endif
if (v_ann->may_aliases == NULL)
v_ann->may_aliases = VEC_alloc (tree, gc, 2);
for (i = 0; VEC_iterate (tree, v_ann->may_aliases, i, al); i++)
if (alias == al)
return;
VEC_safe_push (tree, gc, v_ann->may_aliases, alias);
a_ann->is_aliased = 1;
}
static void
replace_may_alias (tree var, size_t i, tree new_alias)
{
var_ann_t v_ann = var_ann (var);
VEC_replace (tree, v_ann->may_aliases, i, new_alias);
}
static void
set_pt_anything (tree ptr)
{
struct ptr_info_def *pi = get_ptr_info (ptr);
pi->pt_anything = 1;
pi->pt_vars = NULL;
if (pi->name_mem_tag)
{
mark_sym_for_renaming (pi->name_mem_tag);
pi->name_mem_tag = NULL_TREE;
}
}
enum escape_type
is_escape_site (tree stmt)
{
tree call = get_call_expr_in (stmt);
if (call != NULL_TREE)
{
if (!TREE_SIDE_EFFECTS (call))
return ESCAPE_TO_PURE_CONST;
return ESCAPE_TO_CALL;
}
else if (TREE_CODE (stmt) == ASM_EXPR)
return ESCAPE_TO_ASM;
else if (TREE_CODE (stmt) == MODIFY_EXPR)
{
tree lhs = TREE_OPERAND (stmt, 0);
if (TREE_CODE (lhs) != SSA_NAME)
lhs = get_base_address (lhs);
if (lhs == NULL_TREE)
return ESCAPE_UNKNOWN;
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 (POINTER_TYPE_P (from) && !POINTER_TYPE_P (to))
return ESCAPE_BAD_CAST;
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 (TREE_CODE (lhs) == SSA_NAME)
return NO_ESCAPE;
return ESCAPE_STORED_IN_GLOBAL;
}
else if (TREE_CODE (stmt) == RETURN_EXPR)
return ESCAPE_TO_RETURN;
return NO_ESCAPE;
}
static tree
create_tag_raw (enum tree_code code, tree type, const char *prefix)
{
tree tmp_var;
tree new_type;
new_type = build_type_variant (type, 0, 0);
TYPE_ATTRIBUTES (new_type) = TYPE_ATTRIBUTES (type);
tmp_var = build_decl (code, create_tmp_var_name (prefix),
type);
TREE_READONLY (tmp_var) = 0;
MTAG_GLOBAL (tmp_var) = 0;
TREE_STATIC (tmp_var) = 0;
TREE_USED (tmp_var) = 1;
return tmp_var;
}
static tree
create_memory_tag (tree type, bool is_type_tag)
{
var_ann_t ann;
tree tag = create_tag_raw (is_type_tag ? SYMBOL_MEMORY_TAG : NAME_MEMORY_TAG,
type, (is_type_tag) ? "SMT" : "NMT");
DECL_CONTEXT (tag) = current_function_decl;
TREE_ADDRESSABLE (tag) = 1;
ann = get_var_ann (tag);
ann->symbol_mem_tag = NULL_TREE;
add_referenced_var (tag);
return tag;
}
static tree
get_nmt_for (tree ptr)
{
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);
return tag;
}
static tree
get_tmt_for (tree ptr, struct alias_info *ai)
{
size_t i;
tree tag;
tree tag_type = TREE_TYPE (TREE_TYPE (ptr));
HOST_WIDE_INT tag_set = get_alias_set (tag_type);
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;
}
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)->symbol_mem_tag;
if (tag_set == curr->set)
{
tag = curr_tag;
break;
}
}
if (tag == NULL_TREE)
{
struct alias_map_d *alias_map;
if (var_ann (ptr)->symbol_mem_tag == NULL_TREE)
tag = create_memory_tag (tag_type, true);
else
tag = var_ann (ptr)->symbol_mem_tag;
alias_map = XCNEW (struct alias_map_d);
alias_map->var = ptr;
alias_map->set = tag_set;
ai->pointers[ai->num_pointers++] = alias_map;
}
TREE_THIS_VOLATILE (tag) |= TREE_THIS_VOLATILE (tag_type);
gcc_assert (tag_set == get_alias_set (tag));
return tag;
}
static void
create_global_var (void)
{
global_var = build_decl (VAR_DECL, get_identifier (".GLOBAL_VAR"),
void_type_node);
DECL_ARTIFICIAL (global_var) = 1;
TREE_READONLY (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_THIS_VOLATILE (global_var) = 0;
TREE_ADDRESSABLE (global_var) = 0;
create_var_ann (global_var);
mark_call_clobbered (global_var, ESCAPE_UNKNOWN);
add_referenced_var (global_var);
mark_sym_for_renaming (global_var);
}
static void
dump_alias_stats (FILE *file)
{
const char *funcname
= lang_hooks.decl_printable_name (current_function_decl, 2);
fprintf (file, "\nAlias statistics for %s\n\n", funcname);
fprintf (file, "Total alias queries:\t%u\n", alias_stats.alias_queries);
fprintf (file, "Total alias mayalias results:\t%u\n",
alias_stats.alias_mayalias);
fprintf (file, "Total alias noalias results:\t%u\n",
alias_stats.alias_noalias);
fprintf (file, "Total simple queries:\t%u\n",
alias_stats.simple_queries);
fprintf (file, "Total simple resolved:\t%u\n",
alias_stats.simple_resolved);
fprintf (file, "Total TBAA queries:\t%u\n",
alias_stats.tbaa_queries);
fprintf (file, "Total TBAA resolved:\t%u\n",
alias_stats.tbaa_resolved);
fprintf (file, "Total non-addressable structure type queries:\t%u\n",
alias_stats.structnoaddress_queries);
fprintf (file, "Total non-addressable structure type resolved:\t%u\n",
alias_stats.structnoaddress_resolved);
}
void
dump_alias_info (FILE *file)
{
size_t i;
const char *funcname
= lang_hooks.decl_printable_name (current_function_decl, 2);
referenced_var_iterator rvi;
tree var;
fprintf (file, "\nFlow-insensitive alias information for %s\n\n", funcname);
fprintf (file, "Aliased symbols\n\n");
FOR_EACH_REFERENCED_VAR (var, rvi)
{
if (may_be_aliased (var))
dump_variable (file, var);
}
fprintf (file, "\nDereferenced pointers\n\n");
FOR_EACH_REFERENCED_VAR (var, rvi)
{
var_ann_t ann = var_ann (var);
if (ann->symbol_mem_tag)
dump_variable (file, var);
}
fprintf (file, "\nSymbol memory tags\n\n");
FOR_EACH_REFERENCED_VAR (var, rvi)
{
if (TREE_CODE (var) == SYMBOL_MEMORY_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_EACH_REFERENCED_VAR (var, rvi)
{
if (TREE_CODE (var) == NAME_MEMORY_TAG)
dump_variable (file, var);
}
fprintf (file, "\n");
}
void
debug_alias_info (void)
{
dump_alias_info (stderr);
}
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_NEW (struct ptr_info_def);
memset ((void *)pi, 0, sizeof (*pi));
SSA_NAME_PTR_INFO (t) = pi;
}
return pi;
}
void
dump_points_to_info_for (FILE *file, tree ptr)
{
struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
print_generic_expr (file, ptr, dump_flags);
if (pi)
{
if (pi->name_mem_tag)
{
fprintf (file, ", name memory tag: ");
print_generic_expr (file, pi->name_mem_tag, dump_flags);
}
if (pi->is_dereferenced)
fprintf (file, ", is dereferenced");
if (pi->value_escapes_p)
fprintf (file, ", its value escapes");
if (pi->pt_anything)
fprintf (file, ", points-to anything");
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");
}
void
debug_points_to_info_for (tree var)
{
dump_points_to_info_for (stderr, var);
}
void
dump_points_to_info (FILE *file)
{
basic_block bb;
block_stmt_iterator si;
ssa_op_iter iter;
const char *fname =
lang_hooks.decl_printable_name (current_function_decl, 2);
referenced_var_iterator rvi;
tree var;
fprintf (file, "\n\nPointed-to sets for pointers in %s\n\n", fname);
FOR_EACH_REFERENCED_VAR (var, rvi)
{
if (POINTER_TYPE_P (TREE_TYPE (var)))
{
tree def = default_def (var);
if (def)
dump_points_to_info_for (file, def);
}
}
FOR_EACH_BB (bb)
{
tree phi;
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
tree ptr = PHI_RESULT (phi);
if (POINTER_TYPE_P (TREE_TYPE (ptr)))
dump_points_to_info_for (file, ptr);
}
for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
{
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);
}
}
fprintf (file, "\n");
}
void
debug_points_to_info (void)
{
dump_points_to_info (stderr);
}
void
dump_may_aliases_for (FILE *file, tree var)
{
VEC(tree, gc) *aliases;
if (TREE_CODE (var) == SSA_NAME)
var = SSA_NAME_VAR (var);
aliases = var_ann (var)->may_aliases;
if (aliases)
{
size_t i;
tree al;
fprintf (file, "{ ");
for (i = 0; VEC_iterate (tree, aliases, i, al); i++)
{
print_generic_expr (file, al, dump_flags);
fprintf (file, " ");
}
fprintf (file, "}");
}
}
void
debug_may_aliases_for (tree var)
{
dump_may_aliases_for (stderr, var);
}
bool
may_be_aliased (tree var)
{
if (TREE_ADDRESSABLE (var))
return true;
if (MTAG_P (var)
&& (MTAG_GLOBAL (var) || TREE_PUBLIC (var)))
return true;
else if (!MTAG_P (var)
&& (DECL_EXTERNAL (var) || TREE_PUBLIC (var)))
return true;
if (!TREE_STATIC (var))
return false;
if (flag_unit_at_a_time)
return false;
if (decl_function_context (var) == current_function_decl)
return false;
return true;
}
bool
is_aliased_with (tree tag, tree sym)
{
size_t i;
VEC(tree,gc) *aliases;
tree al;
if (var_ann (sym)->is_aliased)
{
aliases = var_ann (tag)->may_aliases;
if (aliases == NULL)
return false;
for (i = 0; VEC_iterate (tree, aliases, i, al); i++)
if (al == sym)
return true;
}
else
{
aliases = var_ann (sym)->may_aliases;
if (aliases == NULL)
return false;
for (i = 0; VEC_iterate (tree, aliases, i, al); i++)
if (al == tag)
return true;
}
return false;
}
bool
may_aliases_intersect (tree tag1, tree tag2)
{
struct pointer_set_t *set1 = pointer_set_create ();
unsigned i;
VEC(tree,gc) *may_aliases1 = may_aliases (tag1);
VEC(tree,gc) *may_aliases2 = may_aliases (tag2);
tree sym;
for (i = 0; VEC_iterate (tree, may_aliases1, i, sym); i++)
pointer_set_insert (set1, sym);
for (i = 0; VEC_iterate (tree, may_aliases2, i, sym); i++)
if (pointer_set_contains (set1, sym))
{
pointer_set_destroy (set1);
return true;
}
pointer_set_destroy (set1);
return false;
}
static tree
add_may_alias_for_new_tag (tree tag, tree var)
{
var_ann_t v_ann = var_ann (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) == SYMBOL_MEMORY_TAG)
return ali;
}
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);
}
return tag;
}
void
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));
tree tag;
subvar_t svars;
tree ali = NULL_TREE;
HOST_WIDE_INT offset, size, maxsize;
tree ref;
gcc_assert (p_ann->symbol_mem_tag == NULL_TREE);
gcc_assert (!MTAG_P (var));
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;
if (var_can_have_subvars (var)
&& (svars = get_subvars_for_var (var)))
{
subvar_t sv;
VEC (tree, heap) *overlaps = NULL;
unsigned int len;
for (sv = svars; sv; sv = sv->next)
{
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++)
{
ali = add_may_alias_for_new_tag (tag, sv_var);
if (ali != tag)
{
add_may_alias (tag, ali);
ali = tag;
}
}
}
}
else
ali = add_may_alias_for_new_tag (tag, var);
p_ann->symbol_mem_tag = ali;
TREE_READONLY (tag) = TREE_READONLY (var);
MTAG_GLOBAL (tag) = is_global_var (var);
}
typedef struct used_part
{
HOST_WIDE_INT minused;
HOST_WIDE_INT maxused;
bool explicit_uses;
bool implicit_uses;
bool write_only;
} *used_part_t;
static htab_t used_portions;
struct used_part_map
{
unsigned int uid;
used_part_t to;
};
static int
used_part_map_eq (const void *va, const void *vb)
{
const struct used_part_map *a = (const struct used_part_map *) va;
const struct used_part_map *b = (const struct used_part_map *) vb;
return (a->uid == b->uid);
}
static unsigned int
used_part_map_hash (const void *item)
{
return ((const struct used_part_map *)item)->uid;
}
static void
free_used_part_map (void *item)
{
free (((struct used_part_map *)item)->to);
free (item);
}
static used_part_t
up_lookup (unsigned int uid)
{
struct used_part_map *h, in;
in.uid = uid;
h = (struct used_part_map *) htab_find_with_hash (used_portions, &in, uid);
if (!h)
return NULL;
return h->to;
}
static void
up_insert (unsigned int uid, used_part_t to)
{
struct used_part_map *h;
void **loc;
h = XNEW (struct used_part_map);
h->uid = uid;
h->to = to;
loc = htab_find_slot_with_hash (used_portions, h,
uid, INSERT);
if (*loc != NULL)
free (*loc);
*(struct used_part_map **) loc = h;
}
static used_part_t
get_or_create_used_part_for (size_t uid)
{
used_part_t up;
if ((up = up_lookup (uid)) == NULL)
{
up = XCNEW (struct used_part);
up->minused = INT_MAX;
up->maxused = 0;
up->explicit_uses = false;
up->implicit_uses = false;
up->write_only = true;
}
return up;
}
static tree
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");
DECL_CONTEXT (subvar) = DECL_CONTEXT (var);
MTAG_GLOBAL (subvar) = DECL_EXTERNAL (var);
TREE_PUBLIC (subvar) = TREE_PUBLIC (var);
TREE_STATIC (subvar) = TREE_STATIC (var);
TREE_READONLY (subvar) = TREE_READONLY (var);
TREE_ADDRESSABLE (subvar) = TREE_ADDRESSABLE (var);
ann = get_var_ann (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;
}
static void
create_overlap_variables_for (tree var)
{
VEC(fieldoff_s,heap) *fieldstack = NULL;
used_part_t up;
size_t uid = DECL_UID (var);
up = up_lookup (uid);
if (!up
|| up->write_only)
return;
push_fields_onto_fieldstack (TREE_TYPE (var), &fieldstack, 0, NULL);
if (VEC_length (fieldoff_s, fieldstack) != 0)
{
subvar_t *subvars;
fieldoff_s *fo;
bool notokay = false;
int fieldcount = 0;
int i;
HOST_WIDE_INT lastfooffset = -1;
HOST_WIDE_INT lastfosize = -1;
tree lastfotype = NULL_TREE;
for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
{
if (!fo->size
|| TREE_CODE (fo->size) != INTEGER_CST
|| fo->offset < 0)
{
notokay = true;
break;
}
fieldcount++;
}
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;
}
if (notokay)
{
VEC_free (fieldoff_s, heap, fieldstack);
return;
}
subvars = lookup_subvars_for_var (var);
sort_fieldstack (fieldstack);
for (i = VEC_length (fieldoff_s, fieldstack);
VEC_iterate (fieldoff_s, fieldstack, --i, fo);)
{
subvar_t sv;
HOST_WIDE_INT fosize;
tree currfotype;
fosize = TREE_INT_CST_LOW (fo->size);
currfotype = fo->type;
if (((fo->offset <= up->minused
&& fo->offset + fosize <= up->minused)
|| fo->offset >= up->maxused)
|| (fo->offset == lastfooffset
&& fosize == lastfosize
&& currfotype == lastfotype))
continue;
sv = GGC_NEW (struct subvar);
sv->next = *subvars;
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,
SFT_OFFSET (sv->var));
fprintf (dump_file, " size " HOST_WIDE_INT_PRINT_DEC,
SFT_SIZE (sv->var));
fprintf (dump_file, "\n");
}
lastfotype = currfotype;
lastfooffset = fo->offset;
lastfosize = fosize;
*subvars = sv;
}
clear_call_clobbered (var);
}
VEC_free (fieldoff_s, heap, fieldstack);
}
static tree
find_used_portions (tree *tp, int *walk_subtrees, void *lhs_p)
{
switch (TREE_CODE (*tp))
{
case MODIFY_EXPR:
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;
HOST_WIDE_INT bitpos;
tree ref;
ref = get_ref_base_and_extent (*tp, &bitpos, &bitsize, &bitmaxsize);
if (DECL_P (ref)
&& var_can_have_subvars (ref)
&& bitmaxsize != -1)
{
size_t uid = DECL_UID (ref);
used_part_t up;
up = get_or_create_used_part_for (uid);
if (bitpos <= up->minused)
up->minused = bitpos;
if ((bitpos + bitmaxsize >= up->maxused))
up->maxused = bitpos + bitmaxsize;
if (bitsize == bitmaxsize)
up->explicit_uses = true;
else
up->implicit_uses = true;
if (!lhs_p)
up->write_only = false;
up_insert (uid, up);
*walk_subtrees = 0;
return NULL_TREE;
}
}
break;
case ADDR_EXPR:
{
tree var = get_base_address (TREE_OPERAND (*tp, 0));
if (var
&& DECL_P (var)
&& DECL_SIZE (var)
&& var_can_have_subvars (var)
&& TREE_CODE (DECL_SIZE (var)) == INTEGER_CST)
{
used_part_t up;
size_t uid = DECL_UID (var);
up = get_or_create_used_part_for (uid);
up->minused = 0;
up->maxused = TREE_INT_CST_LOW (DECL_SIZE (var));
up->implicit_uses = true;
if (!lhs_p)
up->write_only = false;
up_insert (uid, up);
*walk_subtrees = 0;
return NULL_TREE;
}
}
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:
{
tree var = *tp;
if (DECL_SIZE (var)
&& var_can_have_subvars (var)
&& TREE_CODE (DECL_SIZE (var)) == INTEGER_CST)
{
used_part_t up;
size_t uid = DECL_UID (var);
up = get_or_create_used_part_for (uid);
up->minused = 0;
up->maxused = TREE_INT_CST_LOW (DECL_SIZE (var));
up->implicit_uses = true;
up_insert (uid, up);
*walk_subtrees = 0;
return NULL_TREE;
}
}
break;
default:
break;
}
return NULL_TREE;
}
static unsigned int
create_structure_vars (void)
{
basic_block bb;
safe_referenced_var_iterator rvi;
VEC (tree, heap) *varvec = NULL;
tree var;
used_portions = htab_create (10, used_part_map_hash, used_part_map_eq,
free_used_part_map);
FOR_EACH_BB (bb)
{
block_stmt_iterator bsi;
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
walk_tree_without_duplicates (bsi_stmt_ptr (bsi),
find_used_portions,
NULL);
}
}
FOR_EACH_REFERENCED_VAR_SAFE (var, varvec, rvi)
{
if (var
&& DECL_SIZE (var)
&& var_can_have_subvars (var)
&& !MTAG_P (var)
&& TREE_CODE (DECL_SIZE (var)) == INTEGER_CST)
create_overlap_variables_for (var);
}
htab_delete (used_portions);
VEC_free (tree, heap, varvec);
return 0;
}
static bool
gate_structure_vars (void)
{
return flag_tree_salias != 0;
}
struct tree_opt_pass pass_create_structure_vars =
{
"salias",
gate_structure_vars,
create_structure_vars,
NULL,
NULL,
0,
0,
PROP_cfg,
0,
0,
0,
TODO_dump_func,
0
};
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,
NULL,
reset_cc_flags,
NULL,
NULL,
0,
0,
PROP_referenced_vars |PROP_cfg,
0,
0,
0,
0,
0
};