This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[tree-ssa]: Greatly speed up PTA queries
- From: Daniel Berlin <dberlin at dberlin dot org>
- To: gcc-patches at gcc dot gnu dot org
- Date: Wed, 19 Feb 2003 15:29:55 -0500 (EST)
- Subject: [tree-ssa]: Greatly speed up PTA queries
Most of the PTA time in queries was spent doing hash table lookups to find
the typevar for a decl, or the cached ptset for a typevar.
On one testcase, this reduces the time from 600 seconds to 30, when we
have 265 million pta queries.
I tried putting the typevar in an annotation rather than in the decl node,
but it's too slow (it adds another 70 seconds back).
Besides, As long as the TBAA set belongs in the decl node, the typevar
belongs there too (IE when we can remove one, we should be able to remove
the other). We should be able to move both out when we don't make 265
million pta queries.
:)
I'll wait a day or two in case anyone has comments.
2002-02-19 Daniel Berlin <dberlin at dberlin dot org>
* tree-alias-ander.c: Store cached ptsets in the typevar, not
a seperate hash table.
(ptset_map): Removed;
(ptset_map_eq): Ditto.
(ptset_map_hash): Ditto.
(andersen_init): Remove ptset_map.
(andersen_cleanup): Ditto.
(andersen_add_var): Ditto.
(andersen_add_var_asm): Ditto.
(andersen_may_alias): Ditto.
* tree-alias-common.c: Store typevars for DECL nodes in the tree_decl
structure.
(get_alias_var_decl): Use DECL_PTA_TYPEVAR for DECL's.
(create_alias_var): Ditto.
(find_func_aliases): CONST functions don't affect aliasing either.
(ptr_may_alias_var): Don't call get_base_symbol.
Remove decl_function_context, use DECL_CONTEXT instead.
For DECL's, use DECL_PTA_TYPEVAR.
* tree-alias-type.c (struct alias_typevar_aterm): Add ptset member.
(ALIAS_TVAR_PTSET): New macro.
* tree.h (DECL_PTA_TYPEVAR): New macro.
(struct tree_decl): Add typevar member.
Index: tree-alias-ander.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-alias-ander.c,v
retrieving revision 1.1.2.9
diff -u -3 -p -r1.1.2.9 tree-alias-ander.c
--- tree-alias-ander.c 4 Feb 2003 05:10:22 -0000 1.1.2.9
+++ tree-alias-ander.c 19 Feb 2003 20:18:58 -0000
@@ -89,31 +89,9 @@ static alias_typevar andersen_add_var PA
static alias_typevar andersen_add_var_same PARAMS ((struct tree_alias_ops *,
tree, alias_typevar));
static bool pointer_destroying_op PARAMS ((tree));
-static hashval_t ptset_map_hash PARAMS ((const PTR));
-static int ptset_map_eq PARAMS ((const PTR, const PTR));
static splay_tree ptamap;
-static htab_t ptset_map;
-#define POINTER_HASH(x) (hashval_t)((long)x >> 3)
-struct ptset_map_data
-{
- tree decl;
- aterm_list ptset;
-};
-static hashval_t
-ptset_map_hash (p)
- const PTR p;
-{
- return POINTER_HASH (((struct ptset_map_data *)p)->decl);
-}
-static int
-ptset_map_eq (p1, p2)
- const PTR p1;
- const PTR p2;
-{
- return ((struct ptset_map_data *)p1)->decl == p2;
-}
static struct tree_alias_ops andersen_ops = {
andersen_init,
@@ -431,7 +409,6 @@ andersen_init (ops)
dump_file = dump_begin (TDI_pta, &dump_flags);
ptamap = splay_tree_new (splay_tree_compare_pointers, NULL, NULL);
- ptset_map = htab_create (7, ptset_map_hash, ptset_map_eq, free);
/* Don't claim we can do ip partial unless the user requests it. */
if (!flag_ip)
andersen_ops.ip_partial = 0;
@@ -472,7 +449,6 @@ andersen_cleanup (ops)
{
pta_reset ();
splay_tree_delete (ptamap);
- htab_delete (ptset_map);
deleteregion (andersen_rgn);
}
@@ -489,7 +465,6 @@ andersen_add_var (ops, decl)
tree decl;
{
alias_typevar ret;
- PTR *slot;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Adding variable %s\n",
alias_get_name (decl));
@@ -507,12 +482,7 @@ andersen_add_var (ops, decl)
}
splay_tree_insert (ptamap, (splay_tree_key) ALIAS_TVAR_ATERM (ret),
(splay_tree_value) ret);
- slot = htab_find_slot_with_hash (ptset_map,
- decl,
- POINTER_HASH (decl),
- NO_INSERT);
- if (slot)
- htab_clear_slot (ptset_map, slot);
+ ALIAS_TVAR_PTSET (ret) = NULL;
return ret;
}
@@ -527,7 +497,6 @@ andersen_add_var_same (ops, decl, tv)
alias_typevar tv;
{
alias_typevar ret;
- PTR *slot;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Adding variable %s same as %s\n",
@@ -546,19 +515,8 @@ andersen_add_var_same (ops, decl, tv)
pta_join (ALIAS_TVAR_ATERM (tv), ALIAS_TVAR_ATERM (ret));
splay_tree_insert (ptamap, (splay_tree_key) ALIAS_TVAR_ATERM (ret),
(splay_tree_value) ret);
- slot = htab_find_slot_with_hash (ptset_map,
- decl,
- POINTER_HASH (decl),
- NO_INSERT);
- if (slot)
- htab_clear_slot (ptset_map, slot);
-
- slot = htab_find_slot_with_hash (ptset_map,
- ALIAS_TVAR_DECL (tv),
- POINTER_HASH (ALIAS_TVAR_DECL (tv)),
- NO_INSERT);
- if (slot)
- htab_clear_slot (ptset_map, slot);
+ ALIAS_TVAR_PTSET (tv) = NULL;
+ ALIAS_TVAR_PTSET (ret) = NULL;
return ret;
}
@@ -800,25 +758,12 @@ andersen_may_alias (ops, ptrtv, vartv)
alias_typevar vartv;
{
aterm_list ptset;
- struct ptset_map_data *data;
-
- data = htab_find_with_hash (ptset_map, ALIAS_TVAR_DECL (ptrtv),
- POINTER_HASH (ALIAS_TVAR_DECL (ptrtv)));
+ ptset = ALIAS_TVAR_PTSET (ptrtv);
- if (!data)
+ if (!ptset)
{
ptset = aterm_tlb (pta_get_contents (ALIAS_TVAR_ATERM (ptrtv)));
- data = xmalloc (sizeof (struct ptset_map_data));
- data->decl = ALIAS_TVAR_DECL (ptrtv);
- data->ptset = ptset;
- *(htab_find_slot_with_hash (ptset_map,
- ALIAS_TVAR_DECL (ptrtv),
- POINTER_HASH (ALIAS_TVAR_DECL (ptrtv)),
- INSERT)) = data;
- }
- else
- {
- ptset = data->ptset;
+ ALIAS_TVAR_PTSET (ptrtv) = ptset;
}
if (aterm_list_empty (ptset))
Index: tree-alias-common.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-alias-common.c,v
retrieving revision 1.1.2.18
diff -u -3 -p -r1.1.2.18 tree-alias-common.c
--- tree-alias-common.c 4 Feb 2003 19:54:22 -0000 1.1.2.18
+++ tree-alias-common.c 19 Feb 2003 20:18:58 -0000
@@ -154,11 +154,18 @@ get_alias_var_decl (decl)
alias_typevar newvar;
- lookup.key = decl;
- entry = htab_find (alias_annot, &lookup);
- if (entry != NULL && entry->value != 0)
- return entry->value;
-
+ if (SSA_DECL_P (decl))
+ {
+ if (DECL_PTA_TYPEVAR (decl))
+ return DECL_PTA_TYPEVAR (decl);
+ }
+ else
+ {
+ lookup.key = decl;
+ entry = htab_find (alias_annot, &lookup);
+ if (entry != NULL && entry->value != 0)
+ return entry->value;
+ }
/* For debugging, remove this whole if block, and re-enable the
find_func_decls call. */
if (TREE_CODE (decl) == FUNCTION_DECL)
@@ -313,7 +320,6 @@ intra_function_call (args)
current_alias_ops->addr_assign (current_alias_ops, argav, av);
current_alias_ops->addr_assign (current_alias_ops, tempvar, av);
current_alias_ops->assign_ptr (current_alias_ops, argav, tempvar);
-
}
}
/* We assume assignments among the actual parameters. */
@@ -508,8 +514,8 @@ find_func_aliases (tp, walk_subtrees, da
if (TREE_CODE (callop0) == ADDR_EXPR)
create_fun_alias_var (TREE_OPERAND (callop0, 0), 0);
- /* NORETURN functions have no effect on aliasing. */
- if (!(call_expr_flags (op1) & ECF_NORETURN))
+ /* NORETURN and CONST functions have no effect on aliasing. */
+ if (!(call_expr_flags (op1) & (ECF_NORETURN | ECF_CONST)))
if (current_alias_ops->function_call (current_alias_ops, lhsAV,
get_alias_var (callop0),
args))
@@ -659,8 +665,8 @@ find_func_aliases (tp, walk_subtrees, da
}
if (TREE_CODE (TREE_OPERAND (stp, 0)) == ADDR_EXPR)
create_fun_alias_var (TREE_OPERAND (TREE_OPERAND (stp, 0), 0), 0);
- /* NORETURN functions have no effect on aliasing. */
- if (!(call_expr_flags (stp) & ECF_NORETURN))
+ /* NORETURN and CONST functions have no effect on aliasing. */
+ if (!(call_expr_flags (stp) & (ECF_NORETURN | ECF_CONST)))
if (current_alias_ops->function_call (current_alias_ops, NULL,
get_alias_var (TREE_OPERAND (stp, 0)),
args))
@@ -899,7 +905,11 @@ create_alias_var (decl)
struct alias_annot_entry entry, *result, *newentry, **slot;
alias_typevar avar;
-
+ if (SSA_DECL_P (decl))
+ {
+ if (DECL_PTA_TYPEVAR (decl))
+ return DECL_PTA_TYPEVAR (decl);
+ }
entry.key = decl;
result = htab_find (alias_annot, &entry);
if (result != NULL && result->value != NULL)
@@ -913,14 +923,20 @@ create_alias_var (decl)
}
else
avar = current_alias_ops->add_var (current_alias_ops, decl);
-
- newentry = ggc_alloc (sizeof (struct alias_annot_entry));
- newentry->key = decl;
- newentry->value = avar;
- slot = (struct alias_annot_entry **)htab_find_slot (alias_annot, newentry,
- INSERT);
- *slot = newentry;
-
+ if (SSA_DECL_P (decl))
+ {
+ DECL_PTA_TYPEVAR (decl) = avar;
+ }
+ else
+ {
+ newentry = ggc_alloc (sizeof (struct alias_annot_entry));
+ newentry->key = decl;
+ newentry->value = avar;
+ slot =
+ (struct alias_annot_entry **)htab_find_slot (alias_annot, newentry,
+ INSERT);
+ *slot = newentry;
+ }
VARRAY_PUSH_GENERIC_PTR (alias_vars, avar);
return avar;
@@ -990,7 +1006,14 @@ delete_alias_vars ()
for (i = 0; i < VARRAY_ACTIVE_SIZE (local_alias_vars); i++)
{
entry.key = VARRAY_GENERIC_PTR (local_alias_vars, i);
- htab_remove_elt (alias_annot, &entry);
+ if (!SSA_DECL_P (entry.key))
+ {
+ htab_remove_elt (alias_annot, &entry);
+ }
+ else
+ {
+ DECL_PTA_TYPEVAR (entry.key) = NULL;
+ }
}
for (i = 0; i < VARRAY_ACTIVE_SIZE (local_alias_varnums); i ++)
@@ -1037,54 +1060,63 @@ ptr_may_alias_var (ptr, var)
alias_typevar ptrtv, vartv;
#if !FIELD_BASED
- ptr = get_base_symbol (ptr);
- var = get_base_symbol (var);
#else
if (TREE_CODE (ptr) == COMPONENT_REF)
ptr = TREE_OPERAND (ptr, 1);
if (TREE_CODE (var) == COMPONENT_REF)
var = TREE_OPERAND (var, 1);
#endif
- if (ptr == var)
+ if (ptr == var || (DECL_CONTEXT (ptr) == NULL
+ && DECL_CONTEXT (var) == NULL))
return true;
-
- entry.key = ptr;
- result = htab_find (alias_annot, &entry);
-
- if (!result
- && decl_function_context (ptr) == NULL)
+ if (SSA_DECL_P (ptr))
{
- entry.key = global_var;
+ ptrtv = DECL_PTA_TYPEVAR (ptr);
+ if (DECL_CONTEXT (ptr) == NULL)
+ ptrtv = DECL_PTA_TYPEVAR (global_var);
+ if (!ptrtv && !current_alias_ops->ip && ptr != global_var)
+ abort ();
+ else if (!ptrtv)
+ return false;
+ }
+ else
+ {
+ if (DECL_CONTEXT (ptr) == NULL)
+ entry.key = global_var;
+ else
+ entry.key = ptr;
result = htab_find (alias_annot, &entry);
+ if (!result && !current_alias_ops->ip && ptr != global_var)
+ abort ();
+ else if (!result)
+ return false;
+ ptrtv = result->value;
+ }
+ if (SSA_DECL_P (var))
+ {
+ vartv = DECL_PTA_TYPEVAR (var);
+ if (DECL_CONTEXT (var) == NULL)
+ vartv = DECL_PTA_TYPEVAR (global_var);
+ if (!vartv && !current_alias_ops->ip && var != global_var)
+ abort ();
+ else if (!vartv)
+ return false;
}
-
- if (!result && !current_alias_ops->ip && ptr != global_var)
- abort ();
-
- else if (!result)
- return false;
-
- ptrtv = result->value;
- entry.key = var;
- result = htab_find (alias_annot, &entry);
-
- if (!result
- && decl_function_context (var) == NULL)
+ else
{
- entry.key = global_var;
+ if (DECL_CONTEXT (var) == NULL)
+ entry.key = global_var;
+ else
+ entry.key = var;
result = htab_find (alias_annot, &entry);
+ if (!result && !current_alias_ops->ip && var != global_var)
+ abort ();
+ else if (!result)
+ return false;
+
+ vartv = result->value;
}
-
- if (!result && !current_alias_ops->ip && var != global_var)
- abort ();
- else if (!result)
- return false;
-
- vartv = result->value;
- if (ptrtv == vartv)
- return true;
-
return current_alias_ops->may_alias (current_alias_ops, ptrtv, vartv);
}
Index: tree-alias-type.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-alias-type.h,v
retrieving revision 1.1.2.7
diff -u -3 -p -r1.1.2.7 tree-alias-type.h
--- tree-alias-type.h 30 Jan 2003 18:28:45 -0000 1.1.2.7
+++ tree-alias-type.h 19 Feb 2003 20:18:58 -0000
@@ -5,6 +5,7 @@
union alias_typevar_def;
struct aterm_;
+struct aterm_list_a;
enum alias_typevar_kind
{
ATERM_ATVAR
@@ -18,6 +19,7 @@ struct alias_typevar_aterm GTY (())
{
struct alias_typevar_common common;
struct aterm_ * GTY((skip (""))) term;
+ struct aterm_list_a *GTY ((skip (""))) ptset;
};
union alias_typevar_def GTY ((desc ("%0.common.kind")))
{
@@ -29,6 +31,7 @@ typedef union alias_typevar_def *alias_t
#define ALIAS_TVAR_KIND(x) ((x)->common.kind)
#define ALIAS_TVAR_DECL(x) ((x)->common.decl)
#define ALIAS_TVAR_ATERM(x) ((x)->aterm.term)
+#define ALIAS_TVAR_PTSET(x) ((x)->aterm.ptset)
union alias_type_def;
typedef union alias_type_def *alias_type;
Index: tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.h,v
retrieving revision 1.342.2.46
diff -u -3 -p -r1.342.2.46 tree.h
--- tree.h 13 Feb 2003 17:30:26 -0000 1.342.2.46
+++ tree.h 19 Feb 2003 20:19:00 -0000
@@ -2055,6 +2055,10 @@ struct tree_type GTY(())
#define DECL_POINTER_ALIAS_SET(NODE) \
(DECL_CHECK (NODE)->decl.pointer_alias_set)
+/* Used to store the alias_typevar for a DECL node. */
+#define DECL_PTA_TYPEVAR(NODE) \
+ (DECL_CHECK (NODE)->decl.typevar)
+
/* Used to map between a label and the block it begins during CFG
construction. Not valid any other time. */
#define LABEL_DECL_INDEX(NODE) \
@@ -2075,7 +2079,7 @@ struct tree_type GTY(())
#define DECL_POINTER_DEPTH(DECL) (DECL_CHECK (DECL)->decl.pointer_depth)
struct function;
-
+union alias_typevar_def;
struct tree_decl GTY(())
{
struct tree_common common;
@@ -2174,6 +2178,7 @@ struct tree_decl GTY(())
tree vindex;
HOST_WIDE_INT pointer_alias_set;
+ union alias_typevar_def * GTY ((skip (""))) typevar;
/* Points to a structure whose details depend on the language in use. */
struct lang_decl *lang_specific;
};