[PATCH][2/2] Speedup PTA (PR38474)
Richard Biener
rguenther@suse.de
Tue Dec 10 12:28:00 GMT 2013
This is the 2nd piece. We can cache solution_set_expand when processing
complex constraints. This also fixes spurious bits leaking into
constraints that don't need the expansion as the delta was expanded
in-place previously (seen by the ipa-pta-14.c XFAIL).
Bootstrapped and tested on x86_64-unknown-linux-gnu, applied.
Richard.
2013-12-10 Richard Biener <rguenther@suse.de>
PR middle-end/38474
* tree-ssa-structalias.c (solution_set_expand): Expand into
a different possibly cached bitmap and return the result.
(set_union_with_increment): Pass in a shared expanded bitmap
and adjust.
(do_sd_constraint): Likewise.
(do_ds_constraint): Likewise.
(do_complex_constraint): Likewise.
(solve_graph): Manage the shared expanded bitmap.
* gcc.dg/ipa/ipa-pta-14.c: Un-XFAIL.
Index: gcc/tree-ssa-structalias.c
===================================================================
*** gcc/tree-ssa-structalias.c (revision 205808)
--- gcc/tree-ssa-structalias.c (working copy)
*************** constraint_set_union (vec<constraint_t>
*** 917,928 ****
/* Expands the solution in SET to all sub-fields of variables included. */
! static void
! solution_set_expand (bitmap set)
{
bitmap_iterator bi;
unsigned j;
/* In a first pass expand to the head of the variables we need to
add all sub-fields off. This avoids quadratic behavior. */
EXECUTE_IF_SET_IN_BITMAP (set, 0, j, bi)
--- 917,933 ----
/* Expands the solution in SET to all sub-fields of variables included. */
! static bitmap
! solution_set_expand (bitmap set, bitmap *expanded)
{
bitmap_iterator bi;
unsigned j;
+ if (*expanded)
+ return *expanded;
+
+ *expanded = BITMAP_ALLOC (&iteration_obstack);
+
/* In a first pass expand to the head of the variables we need to
add all sub-fields off. This avoids quadratic behavior. */
EXECUTE_IF_SET_IN_BITMAP (set, 0, j, bi)
*************** solution_set_expand (bitmap set)
*** 931,981 ****
if (v->is_artificial_var
|| v->is_full_var)
continue;
! bitmap_set_bit (set, v->head);
}
/* In the second pass now expand all head variables with subfields. */
! EXECUTE_IF_SET_IN_BITMAP (set, 0, j, bi)
{
varinfo_t v = get_varinfo (j);
! if (v->is_artificial_var
! || v->is_full_var
! || v->head != j)
continue;
for (v = vi_next (v); v != NULL; v = vi_next (v))
! bitmap_set_bit (set, v->id);
}
}
! /* Union solution sets TO and FROM, and add INC to each member of FROM in the
process. */
static bool
! set_union_with_increment (bitmap to, bitmap from, HOST_WIDE_INT inc)
{
bool changed = false;
bitmap_iterator bi;
unsigned int i;
! /* If the solution of FROM contains anything it is good enough to transfer
this to TO. */
! if (bitmap_bit_p (from, anything_id))
return bitmap_set_bit (to, anything_id);
/* If the offset is unknown we have to expand the solution to
all subfields. */
if (inc == UNKNOWN_OFFSET)
{
! bitmap tmp = BITMAP_ALLOC (&iteration_obstack);
! bitmap_copy (tmp, from);
! solution_set_expand (tmp);
! changed |= bitmap_ior_into (to, tmp);
! BITMAP_FREE (tmp);
return changed;
}
/* For non-zero offset union the offsetted solution into the destination. */
! EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
{
varinfo_t vi = get_varinfo (i);
--- 936,987 ----
if (v->is_artificial_var
|| v->is_full_var)
continue;
! bitmap_set_bit (*expanded, v->head);
}
/* In the second pass now expand all head variables with subfields. */
! EXECUTE_IF_SET_IN_BITMAP (*expanded, 0, j, bi)
{
varinfo_t v = get_varinfo (j);
! if (v->head != j)
continue;
for (v = vi_next (v); v != NULL; v = vi_next (v))
! bitmap_set_bit (*expanded, v->id);
}
+
+ /* And finally set the rest of the bits from SET. */
+ bitmap_ior_into (*expanded, set);
+
+ return *expanded;
}
! /* Union solution sets TO and DELTA, and add INC to each member of DELTA in the
process. */
static bool
! set_union_with_increment (bitmap to, bitmap delta, HOST_WIDE_INT inc,
! bitmap *expanded_delta)
{
bool changed = false;
bitmap_iterator bi;
unsigned int i;
! /* If the solution of DELTA contains anything it is good enough to transfer
this to TO. */
! if (bitmap_bit_p (delta, anything_id))
return bitmap_set_bit (to, anything_id);
/* If the offset is unknown we have to expand the solution to
all subfields. */
if (inc == UNKNOWN_OFFSET)
{
! delta = solution_set_expand (delta, expanded_delta);
! changed |= bitmap_ior_into (to, delta);
return changed;
}
/* For non-zero offset union the offsetted solution into the destination. */
! EXECUTE_IF_SET_IN_BITMAP (delta, 0, i, bi)
{
varinfo_t vi = get_varinfo (i);
*************** topo_visit (constraint_graph_t graph, st
*** 1576,1582 ****
static void
do_sd_constraint (constraint_graph_t graph, constraint_t c,
! bitmap delta)
{
unsigned int lhs = c->lhs.var;
bool flag = false;
--- 1582,1588 ----
static void
do_sd_constraint (constraint_graph_t graph, constraint_t c,
! bitmap delta, bitmap *expanded_delta)
{
unsigned int lhs = c->lhs.var;
bool flag = false;
*************** do_sd_constraint (constraint_graph_t gra
*** 1601,1607 ****
dereferenced at all valid offsets. */
if (roffset == UNKNOWN_OFFSET)
{
! solution_set_expand (delta);
/* No further offset processing is necessary. */
roffset = 0;
}
--- 1607,1613 ----
dereferenced at all valid offsets. */
if (roffset == UNKNOWN_OFFSET)
{
! delta = solution_set_expand (delta, expanded_delta);
/* No further offset processing is necessary. */
roffset = 0;
}
*************** done:
*** 1663,1669 ****
as the starting solution for x. */
static void
! do_ds_constraint (constraint_t c, bitmap delta)
{
unsigned int rhs = c->rhs.var;
bitmap sol = get_varinfo (rhs)->solution;
--- 1669,1675 ----
as the starting solution for x. */
static void
! do_ds_constraint (constraint_t c, bitmap delta, bitmap *expanded_delta)
{
unsigned int rhs = c->rhs.var;
bitmap sol = get_varinfo (rhs)->solution;
*************** do_ds_constraint (constraint_t c, bitmap
*** 1699,1705 ****
dereferenced at all valid offsets. */
if (loff == UNKNOWN_OFFSET)
{
! solution_set_expand (delta);
loff = 0;
}
--- 1705,1711 ----
dereferenced at all valid offsets. */
if (loff == UNKNOWN_OFFSET)
{
! delta = solution_set_expand (delta, expanded_delta);
loff = 0;
}
*************** do_ds_constraint (constraint_t c, bitmap
*** 1761,1767 ****
constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */
static void
! do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
{
if (c->lhs.type == DEREF)
{
--- 1767,1774 ----
constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */
static void
! do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta,
! bitmap *expanded_delta)
{
if (c->lhs.type == DEREF)
{
*************** do_complex_constraint (constraint_graph_
*** 1772,1785 ****
else
{
/* *x = y */
! do_ds_constraint (c, delta);
}
}
else if (c->rhs.type == DEREF)
{
/* x = *y */
if (!(get_varinfo (c->lhs.var)->is_special_var))
! do_sd_constraint (graph, c, delta);
}
else
{
--- 1779,1792 ----
else
{
/* *x = y */
! do_ds_constraint (c, delta, expanded_delta);
}
}
else if (c->rhs.type == DEREF)
{
/* x = *y */
if (!(get_varinfo (c->lhs.var)->is_special_var))
! do_sd_constraint (graph, c, delta, expanded_delta);
}
else
{
*************** do_complex_constraint (constraint_graph_
*** 1790,1796 ****
&& c->rhs.offset != 0 && c->lhs.offset == 0);
tmp = get_varinfo (c->lhs.var)->solution;
! flag = set_union_with_increment (tmp, delta, c->rhs.offset);
if (flag)
bitmap_set_bit (changed, c->lhs.var);
--- 1797,1804 ----
&& c->rhs.offset != 0 && c->lhs.offset == 0);
tmp = get_varinfo (c->lhs.var)->solution;
! flag = set_union_with_increment (tmp, delta, c->rhs.offset,
! expanded_delta);
if (flag)
bitmap_set_bit (changed, c->lhs.var);
*************** solve_graph (constraint_graph_t graph)
*** 2709,2714 ****
--- 2717,2723 ----
solution_empty = bitmap_empty_p (solution);
/* Process the complex constraints */
+ bitmap expanded_pts = NULL;
FOR_EACH_VEC_ELT (complex, j, c)
{
/* XXX: This is going to unsort the constraints in
*************** solve_graph (constraint_graph_t graph)
*** 2723,2730 ****
is a constraint where the lhs side is receiving
some set from elsewhere. */
if (!solution_empty || c->lhs.type != DEREF)
! do_complex_constraint (graph, c, pts);
}
solution_empty = bitmap_empty_p (solution);
--- 2732,2740 ----
is a constraint where the lhs side is receiving
some set from elsewhere. */
if (!solution_empty || c->lhs.type != DEREF)
! do_complex_constraint (graph, c, pts, &expanded_pts);
}
+ BITMAP_FREE (expanded_pts);
solution_empty = bitmap_empty_p (solution);
Index: gcc/testsuite/gcc.dg/ipa/ipa-pta-14.c
===================================================================
*** gcc/testsuite/gcc.dg/ipa/ipa-pta-14.c (revision 205851)
--- gcc/testsuite/gcc.dg/ipa/ipa-pta-14.c (working copy)
*************** int main()
*** 21,29 ****
void *p;
a.p = (void *)&c;
p = foo(&a, &a);
! /* { dg-final { scan-ipa-dump "foo.result = { NULL a\[^ \]* c\[^ \]* }" "pta" { xfail *-*-* } } } */
! /* { dg-final { scan-ipa-dump "foo.result = { NULL a\[^ \]* a\[^ \]* c\[^ \]* }" "pta" { target { ! keeps_null_pointer_checks } } } } */
! /* { dg-final { scan-ipa-dump "foo.result = { NONLOCAL a\[^ \]* a\[^ \]* c\[^ \]* }" "pta" { target { keeps_null_pointer_checks } } } } */
((struct X *)p)->p = (void *)0;
if (a.p != (void *)0)
abort ();
--- 21,28 ----
void *p;
a.p = (void *)&c;
p = foo(&a, &a);
! /* { dg-final { scan-ipa-dump "foo.result = { NULL a\[^ \]* c\[^ \]* }" "pta" { target { ! keeps_null_pointer_checks } } } } */
! /* { dg-final { scan-ipa-dump "foo.result = { NONLOCAL a\[^ \]* c\[^ \]* }" "pta" { target { keeps_null_pointer_checks } } } } */
((struct X *)p)->p = (void *)0;
if (a.p != (void *)0)
abort ();
More information about the Gcc-patches
mailing list