The following patch resulted from PR81827 analysis where I was on
the wrong track initially. It still results in a small speedup
because we avoid useless duplicate work in case nodes are unified
and reduce the number of graph edges.
Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.
Richard.
2017-08-17 Richard Biener <rguent...@suse.de>
* tree-ssa-structalias.c (solve_graph): When propagating
to successors update the graphs succ edges and avoid duplicate work.
Index: gcc/tree-ssa-structalias.c
===================================================================
--- gcc/tree-ssa-structalias.c (revision 251119)
+++ gcc/tree-ssa-structalias.c (working copy)
@@ -2759,20 +2759,35 @@ solve_graph (constraint_graph_t graph)
unsigned eff_escaped_id = find (escaped_id);
/* Propagate solution to all successors. */
+ unsigned to_remove = ~0U;
EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i],
0, j, bi)
{
- bitmap tmp;
- bool flag;
-
+ if (to_remove != ~0U)
+ {
+ bitmap_clear_bit (graph->succs[i], to_remove);
+ to_remove = ~0U;
+ }
unsigned int to = find (j);
- tmp = get_varinfo (to)->solution;
- flag = false;
-
+ if (to != j)
+ {
+ /* Update the succ graph, avoiding duplicate
+ work. */
+ to_remove = j;
+ if (! bitmap_set_bit (graph->succs[i], to))
+ continue;
+ /* We eventually end up processing 'to' twice
+ as it is undefined whether bitmap iteration
+ iterates over bits set during iteration.
+ Play safe instead of doing tricks. */
+ }
/* Don't try to propagate to ourselves. */
if (to == i)
continue;
+ bitmap tmp = get_varinfo (to)->solution;
+ bool flag = false;
+
/* If we propagate from ESCAPED use ESCAPED as
placeholder. */
if (i == eff_escaped_id)
@@ -2783,6 +2798,8 @@ solve_graph (constraint_graph_t graph)
if (flag)
bitmap_set_bit (changed, to);
}
+ if (to_remove != ~0U)
+ bitmap_clear_bit (graph->succs[i], to_remove);
}
}
}
