http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56113
--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> 2013-01-28
09:45:06 UTC ---
label_visit () seems to collect recursively points_to bits over the predecessor
graph, thus using a quadratic amount of memory. It does so to optimize
variables that point to the same stuff by assigning them the same
pointer_label.
"indirect" nodes seem to be special as far as I can see as they will never
share the same label with a previously visited node. We should be able
to represent their points_to set by themselves and not miss any equivalences
nor create false ones by that. Thus:
Index: gcc/tree-ssa-structalias.c
===================================================================
--- gcc/tree-ssa-structalias.c (revision 195502)
+++ gcc/tree-ssa-structalias.c (working copy)
@@ -2103,6 +2103,17 @@ label_visit (constraint_graph_t graph, s
if (!graph->points_to[n])
graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
+ /* Indirect nodes get fresh variables. Represent those by that
+ single fresh variable. */
+ if (!bitmap_bit_p (graph->direct_nodes, n))
+ {
+ bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n);
+ graph->pointer_label[n] = pointer_equiv_class++;
+ equiv_class_add (pointer_equiv_class_table,
+ graph->pointer_label[n], graph->points_to[n]);
+ return;
+ }
+
/* Label and union our incoming edges's points to sets. */
EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
{
@@ -2117,9 +2128,6 @@ label_visit (constraint_graph_t graph, s
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]))
{
not sure if it helps in this case though. Assigning pointer_labels is
an optimization, and could be completely short-cut if necessary (not
sure what the result would be for this testcase, or how we could up-front
detect if performing this equivalencing is worthwhile or not).
One may also think of using the pointer_labels of the incoming edges
to perform the unioning instead, thus cache by { set of pointer labels },
{ points-to set } instead of by expanded points-to set only.
The algorithm is definitely poor in its memory usage ...
