This reduces the work done for single predecessor nodes for
assigning pointer equivalence classes in label_visit. For
the PR56113 testcase with n = 40000 this reduces PTA time from
tree PTA : 119.59 (34%) usr
to
tree PTA : 51.62 (18%) usr
(the percentages are with the domwalk fix applied).
Easy optimization with a surprisingly big effect. On the way
I also reduce the work done for non-direct nodes.
Bootstrap and regtest pending on x86_64-unknown-linux-gnu.
Richard.
2013-02-01 Richard Biener <rguent...@suse.de>
* tree-ssa-structalias.c (label_visit): Reduce work for
single-predecessor nodes.
Index: gcc/tree-ssa-structalias.c
===================================================================
*** gcc/tree-ssa-structalias.c (revision 195641)
--- gcc/tree-ssa-structalias.c (working copy)
*************** condense_visit (constraint_graph_t graph
*** 2107,2120 ****
static void
label_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
{
! unsigned int i;
bitmap_iterator bi;
- bitmap_set_bit (si->visited, n);
! if (!graph->points_to[n])
! graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
/* Label and union our incoming edges's points to sets. */
EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
{
unsigned int w = si->node_mapping[i];
--- 2108,2120 ----
static void
label_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
{
! unsigned int i, first_pred;
bitmap_iterator bi;
! bitmap_set_bit (si->visited, n);
/* Label and union our incoming edges's points to sets. */
+ first_pred = -1U;
EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
{
unsigned int w = si->node_mapping[i];
*************** label_visit (constraint_graph_t graph, s
*** 2126,2136 ****
continue;
if (graph->points_to[w])
! bitmap_ior_into(graph->points_to[n], graph->points_to[w]);
}
! /* Indirect nodes get fresh variables. */
if (!bitmap_bit_p (graph->direct_nodes, n))
! bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n);
if (!bitmap_empty_p (graph->points_to[n]))
{
--- 2126,2170 ----
continue;
if (graph->points_to[w])
! {
! if (first_pred == -1U)
! first_pred = w;
! else if (!graph->points_to[n])
! {
! graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
! bitmap_ior (graph->points_to[n],
! graph->points_to[first_pred], graph->points_to[w]);
! }
! else
! bitmap_ior_into(graph->points_to[n], graph->points_to[w]);
! }
}
!
! /* Indirect nodes get fresh variables and a new pointer equiv class. */
if (!bitmap_bit_p (graph->direct_nodes, n))
! {
! if (!graph->points_to[n])
! {
! graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
! if (first_pred != -1U)
! bitmap_copy (graph->points_to[n], graph->points_to[first_pred]);
! }
! bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n);
! graph->pointer_label[n] = pointer_equiv_class++;
! return;
! }
!
! /* If there was only a single non-empty predecessor the pointer equiv
! class is the same. */
! if (!graph->points_to[n])
! {
! if (first_pred != -1U)
! {
! graph->pointer_label[n] = graph->pointer_label[first_pred];
! graph->points_to[n] = graph->points_to[first_pred];
! }
! return;
! }
if (!bitmap_empty_p (graph->points_to[n]))
{
