/* Tree based points-to analysis
- Copyright (C) 2005, 2006 Free Software Foundation, Inc.
+ Copyright (C) 2005, 2006, 2007 Free Software Foundation, Inc.
Contributed by Daniel Berlin <dberlin@dberlin.org>
This file is part of GCC.
/* Old points-to set for this variable. */
bitmap oldsolution;
- /* Finished points-to set for this variable (IE what is returned
- from find_what_p_points_to. */
- bitmap finished_solution;
-
/* Variable ids represented by this node. */
bitmap variables;
static inline varinfo_t
get_varinfo (unsigned int n)
{
- return VEC_index(varinfo_t, varmap, n);
+ return VEC_index (varinfo_t, varmap, n);
}
/* Return the varmap element N, following the collapsed_to link. */
static inline varinfo_t
get_varinfo_fc (unsigned int n)
{
- varinfo_t v = VEC_index(varinfo_t, varmap, n);
+ varinfo_t v = VEC_index (varinfo_t, varmap, n);
if (v->collapsed_to)
return v->collapsed_to;
heapvar_lookup (tree from)
{
struct tree_map *h, in;
- in.from = from;
+ in.base.from = from;
h = htab_find_with_hash (heapvar_for_stmt, &in, htab_hash_pointer (from));
if (h)
h = ggc_alloc (sizeof (struct tree_map));
h->hash = htab_hash_pointer (from);
- h->from = from;
+ h->base.from = from;
h->to = to;
loc = htab_find_slot_with_hash (heapvar_for_stmt, h, h->hash, INSERT);
*(struct tree_map **) loc = h;
ret->has_union = false;
ret->solution = BITMAP_ALLOC (&pta_obstack);
ret->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
- ret->finished_solution = NULL;
ret->next = NULL;
ret->collapsed_to = NULL;
return ret;
{
unsigned int t = find (w);
unsigned int nnode = find (n);
- gcc_assert(nnode == n);
+ gcc_assert (nnode == n);
if (si->dfs[t] < si->dfs[nnode])
si->dfs[n] = si->dfs[t];
EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi)
{
unsigned HOST_WIDE_INT loff = c->lhs.offset;
- if (type_safe (j, &loff) && !(get_varinfo(j)->is_special_var))
+ if (type_safe (j, &loff) && !(get_varinfo (j)->is_special_var))
{
varinfo_t v;
unsigned int t;
bool flag = false;
unsigned int t;
- gcc_assert(c->rhs.type == SCALAR && c->lhs.type == SCALAR);
+ gcc_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR);
t = find (c->rhs.var);
solution = get_varinfo (t)->solution;
t = find (c->lhs.var);
if (flag)
{
get_varinfo (t)->solution = tmp;
- if (!TEST_BIT (changed, c->lhs.var))
+ if (!TEST_BIT (changed, t))
{
- SET_BIT (changed, c->lhs.var);
+ SET_BIT (changed, t);
changed_count++;
}
}
{
unsigned int t = si->node_mapping[w];
unsigned int nnode = si->node_mapping[n];
- gcc_assert(nnode == n);
+ gcc_assert (nnode == n);
if (si->dfs[t] < si->dfs[nnode])
si->dfs[n] = si->dfs[t];
fprintf (dump_file,
"Equivalence class for %s node id %d:%s is %d\n",
direct_node ? "Direct node" : "Indirect node", i,
- get_varinfo(i)->name,
+ get_varinfo (i)->name,
graph->label[si->node_mapping[i]]);
}
/* In certain indirect cycle cases, we may merge this
variable to another. */
- if (eliminate_indirect_cycles (i) && find(i) != i)
+ if (eliminate_indirect_cycles (i) && find (i) != i)
continue;
/* If the node has changed, we need to process the
bitmap solution;
VEC(constraint_t,heap) *complex = graph->complex[i];
bool solution_empty;
+
RESET_BIT (changed, i);
changed_count--;
}
/* Map from trees to variable infos. */
-static htab_t vi_for_tree;
-
-typedef struct tree_vi
-{
- tree t;
- varinfo_t vi;
-} *tree_vi_t;
-
-/* Hash a tree id structure. */
+static struct pointer_map_t *vi_for_tree;
-static hashval_t
-tree_vi_hash (const void *p)
-{
- const tree_vi_t ta = (tree_vi_t) p;
- return htab_hash_pointer (ta->t);
-}
-/* Return true if the tree in P1 and the tree in P2 are the same. */
-
-static int
-tree_vi_eq (const void *p1, const void *p2)
-{
- const tree_vi_t ta1 = (tree_vi_t) p1;
- const tree_vi_t ta2 = (tree_vi_t) p2;
- return ta1->t == ta2->t;
-}
-
-/* Insert ID as the variable id for tree T in the hashtable. */
+/* Insert ID as the variable id for tree T in the vi_for_tree map. */
static void
insert_vi_for_tree (tree t, varinfo_t vi)
{
- void **slot;
- struct tree_vi finder;
- tree_vi_t new_pair;
-
- finder.t = t;
- slot = htab_find_slot (vi_for_tree, &finder, INSERT);
+ void **slot = pointer_map_insert (vi_for_tree, t);
+ gcc_assert (vi);
gcc_assert (*slot == NULL);
- new_pair = XNEW (struct tree_vi);
- new_pair->t = t;
- new_pair->vi = vi;
- *slot = (void *)new_pair;
+ *slot = vi;
}
/* Find the variable info for tree T in VI_FOR_TREE. If T does not
- exist in the hash table, return false, otherwise, return true and
- set *VI to the varinfo we found. */
+ exist in the map, return NULL, otherwise, return the varinfo we found. */
-static bool
-lookup_vi_for_tree (tree t, varinfo_t *vi)
+static varinfo_t
+lookup_vi_for_tree (tree t)
{
- tree_vi_t pair;
- struct tree_vi finder;
+ void **slot = pointer_map_contains (vi_for_tree, t);
+ if (slot == NULL)
+ return NULL;
- finder.t = t;
- pair = htab_find (vi_for_tree, &finder);
- if (pair == NULL)
- return false;
- *vi = pair->vi;
- return true;
+ return (varinfo_t) *slot;
}
/* Return a printable name for DECL */
return res;
}
-/* Find the variable id for tree T in the hashtable.
- If T doesn't exist in the hash table, create an entry for it. */
+/* Find the variable id for tree T in the map.
+ If T doesn't exist in the map, create an entry for it and return it. */
static varinfo_t
get_vi_for_tree (tree t)
{
- tree_vi_t pair;
- struct tree_vi finder;
-
- finder.t = t;
- pair = htab_find (vi_for_tree, &finder);
- if (pair == NULL)
+ void **slot = pointer_map_contains (vi_for_tree, t);
+ if (slot == NULL)
return get_varinfo (create_variable_info_for (t, alias_get_name (t)));
- return pair->vi;
+ return (varinfo_t) *slot;
}
/* Get a constraint expression from an SSA_VAR_P node. */
{
tree type = TREE_TYPE (t);
- if (POINTER_TYPE_P (type) || AGGREGATE_TYPE_P (type)
+ if (POINTER_TYPE_P (type)
+ || AGGREGATE_TYPE_P (type)
|| TREE_CODE (type) == COMPLEX_TYPE)
return true;
+
return false;
}
switch (TREE_CODE_CLASS (TREE_CODE (t)))
{
case tcc_expression:
+ case tcc_vl_exp:
{
switch (TREE_CODE (t))
{
tree pttype = TREE_TYPE (TREE_TYPE (t));
get_constraint_for (exp, results);
+
/* Make sure we capture constraints to all elements
of an array. */
if ((handled_component_p (exp)
}
}
+
/* Update related alias information kept in AI. This is used when
building name tags, alias sets and deciding grouping heuristics.
STMT is the statement to process. This function also updates
}
}
/* In IPA mode, we need to generate constraints to pass call
- arguments through their calls. There are two case, either a
- modify_expr when we are returning a value, or just a plain
- call_expr when we are not. */
+ arguments through their calls. There are two cases, either a
+ GIMPLE_MODIFY_STMT when we are returning a value, or just a plain
+ CALL_EXPR when we are not. */
else if (in_ipa_mode
&& ((TREE_CODE (t) == GIMPLE_MODIFY_STMT
&& TREE_CODE (GIMPLE_STMT_OPERAND (t, 1)) == CALL_EXPR
{
tree lhsop;
tree rhsop;
- tree arglist;
+ tree arg;
+ call_expr_arg_iterator iter;
varinfo_t fi;
int i = 1;
tree decl;
}
else
{
- decl = TREE_OPERAND (rhsop, 0);
+ decl = CALL_EXPR_FN (rhsop);
fi = get_vi_for_tree (decl);
}
/* Assign all the passed arguments to the appropriate incoming
parameters of the function. */
- arglist = TREE_OPERAND (rhsop, 1);
- for (;arglist; arglist = TREE_CHAIN (arglist))
- {
- tree arg = TREE_VALUE (arglist);
+ FOR_EACH_CALL_EXPR_ARG (arg, iter, rhsop)
+ {
struct constraint_expr lhs ;
struct constraint_expr *rhsp;
}
i++;
}
+
/* If we are returning a value, assign it to the result. */
if (lhsop)
{
case tcc_constant:
case tcc_exceptional:
case tcc_expression:
+ case tcc_vl_exp:
case tcc_unary:
{
unsigned int j;
to process expressions other than simple operands
(e.g. INDIRECT_REF, ADDR_EXPR, CALL_EXPR). */
default:
- for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (rhsop)); i++)
+ for (i = 0; i < TREE_OPERAND_LENGTH (rhsop); i++)
{
tree op = TREE_OPERAND (rhsop, i);
unsigned int j;
tree t;
struct constraint_expr lhs, rhs;
- /* For each incoming pointer argument arg, ARG = ANYTHING or a
- dummy variable if flag_argument_noalias > 2. */
+ /* For each incoming pointer argument arg, create the constraint ARG
+ = ANYTHING or a dummy variable if flag_argument_noalias is set. */
for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t))
{
varinfo_t p;
}
}
+/* Structure used to put solution bitmaps in a hashtable so they can
+ be shared among variables with the same points-to set. */
+
+typedef struct shared_bitmap_info
+{
+ bitmap pt_vars;
+ hashval_t hashcode;
+} *shared_bitmap_info_t;
+
+static htab_t shared_bitmap_table;
+
+/* Hash function for a shared_bitmap_info_t */
+
+static hashval_t
+shared_bitmap_hash (const void *p)
+{
+ const shared_bitmap_info_t bi = (shared_bitmap_info_t) p;
+ return bi->hashcode;
+}
+
+/* Equality function for two shared_bitmap_info_t's. */
+
+static int
+shared_bitmap_eq (const void *p1, const void *p2)
+{
+ const shared_bitmap_info_t sbi1 = (shared_bitmap_info_t) p1;
+ const shared_bitmap_info_t sbi2 = (shared_bitmap_info_t) p2;
+ return bitmap_equal_p (sbi1->pt_vars, sbi2->pt_vars);
+}
+
+/* Lookup a bitmap in the shared bitmap hashtable, and return an already
+ existing instance if there is one, NULL otherwise. */
+
+static bitmap
+shared_bitmap_lookup (bitmap pt_vars)
+{
+ void **slot;
+ struct shared_bitmap_info sbi;
+
+ sbi.pt_vars = pt_vars;
+ sbi.hashcode = bitmap_hash (pt_vars);
+
+ slot = htab_find_slot_with_hash (shared_bitmap_table, &sbi,
+ sbi.hashcode, NO_INSERT);
+ if (!slot)
+ return NULL;
+ else
+ return ((shared_bitmap_info_t) *slot)->pt_vars;
+}
+
+
+/* Add a bitmap to the shared bitmap hashtable. */
+
+static void
+shared_bitmap_add (bitmap pt_vars)
+{
+ void **slot;
+ shared_bitmap_info_t sbi = XNEW (struct shared_bitmap_info);
+
+ sbi->pt_vars = pt_vars;
+ sbi->hashcode = bitmap_hash (pt_vars);
+
+ slot = htab_find_slot_with_hash (shared_bitmap_table, sbi,
+ sbi->hashcode, INSERT);
+ gcc_assert (!*slot);
+ *slot = (void *) sbi;
+}
+
+
/* Set bits in INTO corresponding to the variable uids in solution set
FROM, which came from variable PTR.
For variables that are actually dereferenced, we also use type
}
}
-/* Merge the necessary SMT's into the solution set for VI, which is
+/* Merge the necessary SMT's into the bitmap INTO, which is
P's varinfo. This involves merging all SMT's that are a subset of
the SMT necessary for P. */
static void
-merge_smts_into (tree p, varinfo_t vi)
+merge_smts_into (tree p, bitmap solution)
{
unsigned int i;
bitmap_iterator bi;
tree smt;
- VEC(tree, gc) *aliases;
+ bitmap aliases;
tree var = p;
if (TREE_CODE (p) == SSA_NAME)
/* Need to set the SMT subsets first before this
will work properly. */
- bitmap_set_bit (vi->finished_solution, DECL_UID (smt));
+ bitmap_set_bit (solution, DECL_UID (smt));
EXECUTE_IF_SET_IN_BITMAP (used_smts, 0, i, bi)
{
tree newsmt = referenced_var (i);
if (alias_set_subset_of (get_alias_set (newsmttype),
smtset))
- bitmap_set_bit (vi->finished_solution, i);
+ bitmap_set_bit (solution, i);
}
- aliases = var_ann (smt)->may_aliases;
+ aliases = MTAG_ALIASES (smt);
if (aliases)
- {
- size_t k;
- tree al;
- for (k = 0; VEC_iterate (tree, aliases, k, al); k++)
- bitmap_set_bit (vi->finished_solution,
- DECL_UID (al));
- }
+ bitmap_ior_into (solution, aliases);
}
}
&& SSA_NAME_IS_DEFAULT_DEF (p))
lookup_p = SSA_NAME_VAR (p);
- if (lookup_vi_for_tree (lookup_p, &vi))
+ vi = lookup_vi_for_tree (lookup_p);
+ if (vi)
{
-
if (vi->is_artificial_var)
return false;
unsigned int i;
bitmap_iterator bi;
bool was_pt_anything = false;
-
+ bitmap finished_solution;
+ bitmap result;
+
if (!pi->is_dereferenced)
return false;
}
}
- /* Share the final set of variables between the SSA_NAME
- pointer infos for collapsed nodes that are collapsed to
- non-special variables. This is because special vars have
- no real types associated with them, so while we know the
- pointers are equivalent to them, we need to generate the
- solution separately since it will include SMT's from the
- original non-collapsed variable. */
- if (!vi->is_special_var && vi->finished_solution)
+ /* Share the final set of variables when possible. */
+
+ finished_solution = BITMAP_GGC_ALLOC ();
+ stats.points_to_sets_created++;
+
+ /* Instead of using pt_anything, we instead merge in the SMT
+ aliases for the underlying SMT. */
+ if (was_pt_anything)
{
- pi->pt_vars = vi->finished_solution;
+ merge_smts_into (p, finished_solution);
+ pi->pt_global_mem = 1;
+ }
+
+ set_uids_in_ptset (vi->decl, finished_solution, vi->solution);
+ result = shared_bitmap_lookup (finished_solution);
+
+ if (!result)
+ {
+ shared_bitmap_add (finished_solution);
+ pi->pt_vars = finished_solution;
}
else
{
- vi->finished_solution = BITMAP_GGC_ALLOC ();
- stats.points_to_sets_created++;
-
- /* Instead of using pt_anything, we instead merge in the SMT
- aliases for the underlying SMT. */
- if (was_pt_anything)
- {
- merge_smts_into (p, vi);
- pi->pt_global_mem = 1;
- }
-
- set_uids_in_ptset (vi->decl, vi->finished_solution, vi->solution);
- pi->pt_vars = vi->finished_solution;
+ pi->pt_vars = result;
+ bitmap_clear (finished_solution);
}
if (bitmap_empty_p (pi->pt_vars))
sizeof (struct variable_info), 30);
constraints = VEC_alloc (constraint_t, heap, 8);
varmap = VEC_alloc (varinfo_t, heap, 8);
- vi_for_tree = htab_create (10, tree_vi_hash, tree_vi_eq, free);
+ vi_for_tree = pointer_map_create ();
memset (&stats, 0, sizeof (stats));
-
+ shared_bitmap_table = htab_create (511, shared_bitmap_hash,
+ shared_bitmap_eq, free);
init_base_vars ();
}
if (is_gimple_reg (PHI_RESULT (phi)))
{
find_func_aliases (phi);
+
/* Update various related attributes like escaped
addresses, pointer dereferences for loads and stores.
This is used when creating name tags and alias
varinfo_t v;
int i;
+ htab_delete (shared_bitmap_table);
if (dump_file && (dump_flags & TDF_STATS))
fprintf (dump_file, "Points to sets created:%d\n",
stats.points_to_sets_created);
- htab_delete (vi_for_tree);
+ pointer_map_destroy (vi_for_tree);
bitmap_obstack_release (&pta_obstack);
VEC_free (constraint_t, heap, constraints);
OSDN Git Service
