This brings down compile-time in PTA from
tree PTA : 25.37 (24%) usr
to
tree PTA : 5.06 ( 6%) usr
by doing something that was on my TODO list for ... ages. We
are currently re-translating internal points-to sets to final
points-to sets all the time even if we know the result will
be the same as one we computed already. When a lot of points-to
sets are equivalent (as in the above testcase) we spend a lot
of time doing that useless work.
The following patch simply caches the result using a pointer-map
(instead of enlarging the varinfo struct).
For the testcase incremental SSA update is now the worst offender:
tree SSA incremental : 34.14 (39%) usr
out of a remaining total
TOTAL : 86.53
(that's at -O1).
Bootstrap & regtest ongoing on x86_64-unknown-linux-gnu, scheduled
for a commit to trunk (generic compile-time regression, etc.).
Richard.
2013-01-29 Richard Biener <rguent...@suse.de>
* tree-ssa-structalias.c (final_solutions, final_solutions_obstack):
New pointer-map and obstack.
(init_alias_vars): Allocate pointer-map and obstack.
(delete_points_to_sets): Free them.
(find_what_var_points_to): Cache result.
(find_what_p_points_to): Adjust for changed interface of
find_what_var_points_to.
(compute_points_to_sets): Likewise.
(ipa_pta_execute): Likewise.
Index: gcc/tree-ssa-structalias.c
===================================================================
*** gcc/tree-ssa-structalias.c (revision 195549)
--- gcc/tree-ssa-structalias.c (working copy)
*************** static inline bool type_can_have_subvars
*** 303,309 ****
/* Pool of variable info structures. */
static alloc_pool variable_info_pool;
!
/* Table of variable info structures for constraint variables.
Indexed directly by variable info id. */
--- 303,311 ----
/* Pool of variable info structures. */
static alloc_pool variable_info_pool;
! /* Map varinfo to final pt_solution. */
! static pointer_map_t *final_solutions;
! struct obstack final_solutions_obstack;
/* Table of variable info structures for constraint variables.
Indexed directly by variable info id. */
*************** set_uids_in_ptset (bitmap into, bitmap f
*** 5872,5892 ****
/* Compute the points-to solution *PT for the variable VI. */
! static void
! find_what_var_points_to (varinfo_t orig_vi, struct pt_solution *pt)
{
unsigned int i;
bitmap_iterator bi;
bitmap finished_solution;
bitmap result;
varinfo_t vi;
!
! memset (pt, 0, sizeof (struct pt_solution));
/* This variable may have been collapsed, let's get the real
variable. */
vi = get_varinfo (find (orig_vi->id));
/* Translate artificial variables into SSA_NAME_PTR_INFO
attributes. */
EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
--- 5960,5988 ----
/* Compute the points-to solution *PT for the variable VI. */
! static struct pt_solution
! find_what_var_points_to (varinfo_t orig_vi)
{
unsigned int i;
bitmap_iterator bi;
bitmap finished_solution;
bitmap result;
varinfo_t vi;
! void **slot;
! struct pt_solution *pt;
/* This variable may have been collapsed, let's get the real
variable. */
vi = get_varinfo (find (orig_vi->id));
+ /* See if we have already computed the solution and return it. */
+ slot = pointer_map_insert (final_solutions, vi);
+ if (*slot != NULL)
+ return *(struct pt_solution *)*slot;
+
+ *slot = pt = XOBNEW (&final_solutions_obstack, struct pt_solution);
+ memset (pt, 0, sizeof (struct pt_solution));
+
/* Translate artificial variables into SSA_NAME_PTR_INFO
attributes. */
EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
*************** find_what_var_points_to (varinfo_t orig_
*** 5921,5927 ****
/* Instead of doing extra work, simply do not create
elaborate points-to information for pt_anything pointers. */
if (pt->anything)
! return;
/* Share the final set of variables when possible. */
finished_solution = BITMAP_GGC_ALLOC ();
--- 6017,6023 ----
/* Instead of doing extra work, simply do not create
elaborate points-to information for pt_anything pointers. */
if (pt->anything)
! return *pt;
/* Share the final set of variables when possible. */
finished_solution = BITMAP_GGC_ALLOC ();
*************** find_what_var_points_to (varinfo_t orig_
*** 5939,5944 ****
--- 6035,6042 ----
pt->vars = result;
bitmap_clear (finished_solution);
}
+
+ return *pt;
}
/* Given a pointer variable P, fill in its points-to set. */
*************** find_what_p_points_to (tree p)
*** 5963,5969 ****
return;
pi = get_ptr_info (p);
! find_what_var_points_to (vi, &pi->pt);
}
--- 6061,6067 ----
return;
pi = get_ptr_info (p);
! pi->pt = find_what_var_points_to (vi);
}
*************** init_alias_vars (void)
*** 6480,6485 ****
--- 6578,6586 ----
init_base_vars ();
gcc_obstack_init (&fake_var_decl_obstack);
+
+ final_solutions = pointer_map_create ();
+ gcc_obstack_init (&final_solutions_obstack);
}
/* Remove the REF and ADDRESS edges from GRAPH, as well as all the
*************** compute_points_to_sets (void)
*** 6638,6645 ****
solve_constraints ();
/* Compute the points-to set for ESCAPED used for call-clobber analysis. */
! find_what_var_points_to (get_varinfo (escaped_id),
! &cfun->gimple_df->escaped);
/* Make sure the ESCAPED solution (which is used as placeholder in
other solutions) does not reference itself. This simplifies
--- 6739,6745 ----
solve_constraints ();
/* Compute the points-to set for ESCAPED used for call-clobber analysis. */
! cfun->gimple_df->escaped = find_what_var_points_to (get_varinfo
(escaped_id));
/* Make sure the ESCAPED solution (which is used as placeholder in
other solutions) does not reference itself. This simplifies
*************** compute_points_to_sets (void)
*** 6679,6685 ****
memset (pt, 0, sizeof (struct pt_solution));
else if ((vi = lookup_call_use_vi (stmt)) != NULL)
{
! find_what_var_points_to (vi, pt);
/* Escaped (and thus nonlocal) variables are always
implicitly used by calls. */
/* ??? ESCAPED can be empty even though NONLOCAL
--- 6779,6785 ----
memset (pt, 0, sizeof (struct pt_solution));
else if ((vi = lookup_call_use_vi (stmt)) != NULL)
{
! *pt = find_what_var_points_to (vi);
/* Escaped (and thus nonlocal) variables are always
implicitly used by calls. */
/* ??? ESCAPED can be empty even though NONLOCAL
*************** compute_points_to_sets (void)
*** 6700,6706 ****
memset (pt, 0, sizeof (struct pt_solution));
else if ((vi = lookup_call_clobber_vi (stmt)) != NULL)
{
! find_what_var_points_to (vi, pt);
/* Escaped (and thus nonlocal) variables are always
implicitly clobbered by calls. */
/* ??? ESCAPED can be empty even though NONLOCAL
--- 6800,6806 ----
memset (pt, 0, sizeof (struct pt_solution));
else if ((vi = lookup_call_clobber_vi (stmt)) != NULL)
{
! *pt = find_what_var_points_to (vi);
/* Escaped (and thus nonlocal) variables are always
implicitly clobbered by calls. */
/* ??? ESCAPED can be empty even though NONLOCAL
*************** delete_points_to_sets (void)
*** 6755,6760 ****
--- 6855,6863 ----
free_alloc_pool (constraint_pool);
obstack_free (&fake_var_decl_obstack, NULL);
+
+ pointer_map_destroy (final_solutions);
+ obstack_free (&final_solutions_obstack, NULL);
}
*************** ipa_pta_execute (void)
*** 7023,7029 ****
??? Note that the computed escape set is not correct
for the whole unit as we fail to consider graph edges to
externally visible functions. */
! find_what_var_points_to (get_varinfo (escaped_id), &ipa_escaped_pt);
/* Make sure the ESCAPED solution (which is used as placeholder in
other solutions) does not reference itself. This simplifies
--- 7126,7132 ----
??? Note that the computed escape set is not correct
for the whole unit as we fail to consider graph edges to
externally visible functions. */
! ipa_escaped_pt = find_what_var_points_to (get_varinfo (escaped_id));
/* Make sure the ESCAPED solution (which is used as placeholder in
other solutions) does not reference itself. This simplifies
*************** ipa_pta_execute (void)
*** 7058,7066 ****
/* Compute the call-use and call-clobber sets for all direct calls. */
fi = lookup_vi_for_tree (node->symbol.decl);
gcc_assert (fi->is_fn_info);
! find_what_var_points_to (first_vi_for_offset (fi, fi_clobbers),
! &clobbers);
! find_what_var_points_to (first_vi_for_offset (fi, fi_uses), &uses);
for (e = node->callers; e; e = e->next_caller)
{
if (!e->call_stmt)
--- 7161,7169 ----
/* Compute the call-use and call-clobber sets for all direct calls. */
fi = lookup_vi_for_tree (node->symbol.decl);
gcc_assert (fi->is_fn_info);
! clobbers
! = find_what_var_points_to (first_vi_for_offset (fi, fi_clobbers));
! uses = find_what_var_points_to (first_vi_for_offset (fi, fi_uses));
for (e = node->callers; e; e = e->next_caller)
{
if (!e->call_stmt)
*************** ipa_pta_execute (void)
*** 7097,7103 ****
memset (pt, 0, sizeof (struct pt_solution));
else if ((vi = lookup_call_use_vi (stmt)) != NULL)
{
! find_what_var_points_to (vi, pt);
/* Escaped (and thus nonlocal) variables are always
implicitly used by calls. */
/* ??? ESCAPED can be empty even though NONLOCAL
--- 7200,7206 ----
memset (pt, 0, sizeof (struct pt_solution));
else if ((vi = lookup_call_use_vi (stmt)) != NULL)
{
! *pt = find_what_var_points_to (vi);
/* Escaped (and thus nonlocal) variables are always
implicitly used by calls. */
/* ??? ESCAPED can be empty even though NONLOCAL
*************** ipa_pta_execute (void)
*** 7118,7124 ****
memset (pt, 0, sizeof (struct pt_solution));
else if ((vi = lookup_call_clobber_vi (stmt)) != NULL)
{
! find_what_var_points_to (vi, pt);
/* Escaped (and thus nonlocal) variables are always
implicitly clobbered by calls. */
/* ??? ESCAPED can be empty even though NONLOCAL
--- 7221,7227 ----
memset (pt, 0, sizeof (struct pt_solution));
else if ((vi = lookup_call_clobber_vi (stmt)) != NULL)
{
! *pt = find_what_var_points_to (vi);
/* Escaped (and thus nonlocal) variables are always
implicitly clobbered by calls. */
/* ??? ESCAPED can be empty even though NONLOCAL
*************** ipa_pta_execute (void)
*** 7178,7191 ****
if (!uses->anything)
{
! find_what_var_points_to
! (first_vi_for_offset (vi, fi_uses), &sol);
pt_solution_ior_into (uses, &sol);
}
if (!clobbers->anything)
{
! find_what_var_points_to
! (first_vi_for_offset (vi, fi_clobbers), &sol);
pt_solution_ior_into (clobbers, &sol);
}
}
--- 7281,7294 ----
if (!uses->anything)
{
! sol = find_what_var_points_to
! (first_vi_for_offset (vi, fi_uses));
pt_solution_ior_into (uses, &sol);
}
if (!clobbers->anything)
{
! sol = find_what_var_points_to
! (first_vi_for_offset (vi, fi_clobbers));
pt_solution_ior_into (clobbers, &sol);
}
}
