[Bug middle-end/56113] out of memory when compiling a function with many goto labels (50k > )

["rguenther at suse dot de" <gcc-bugzilla at gcc dot gnu dot org>]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56113

--- Comment #10 from rguenther at suse dot de <rguenther at suse dot de> 2013-01-29 09:52:12 UTC ---
On Mon, 28 Jan 2013, steven at gcc dot gnu.org wrote:

> 
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56113
> 
> --- Comment #9 from Steven Bosscher <steven at gcc dot gnu.org> 2013-01-28 23:34:36 UTC ---
> (In reply to comment #7)
> 
> With the patch from comment #7:
> 
> n=1000 6.18user 254976k maxresident
> n=2000 16.76user 509184k maxresident
> n=4000 54.23user 1432576l maxresident
> n=8000 201.31user 1343296k maxresident
> 
> Without:
> n=1000 6.45user 255616k maxresident
> n=2000 17.65user 572096k maxresident
> n=4000 55.10user 1485184k maxresident
> n=8000 199.49user 1456000k maxresident
> 
> So there appears to be some small effect on memory footprint but
> nothing to get excited about, and no effect on compile time.

Yeah, I sort-of expected that ... the following should help more
(apart from the fact that we do not optimize the visiting order
to minimize the number of life bitmaps).

I was thinking of sth like the following - but this of course
leaves the equiv hashtable pointing to freed bitmaps ...
As finding all equivalences of  U recursive-preds (n)  for all
nodes n is the goal there doesn't seem to be a good way of
avoiding the excessive memory use (we can free those that get
their pointer_label shared - but that should be the minority).

I'm out of ideas - apart from killing this whole unification
on the base that it cannot be very effective.

Index: gcc/tree-ssa-structalias.c
===================================================================
--- gcc/tree-ssa-structalias.c  (revision 195530)
+++ gcc/tree-ssa-structalias.c  (working copy)
@@ -507,6 +507,10 @@ struct constraint_graph
   /* Explicit predecessors of each node (Used for variable substitution).  
*/
   bitmap *preds;

+  /* Number of nodes this is in their preds (used to track lifetime of
+     points_to).  */
+  unsigned *n_pred_of;
+
   /* Indirect cycle representatives, or -1 if the node has no indirect
      cycles.  */
   int *indirect_cycles;
@@ -2112,10 +2116,14 @@ label_visit (constraint_graph_t graph, s

       /* Skip unused edges  */
       if (w == n || graph->pointer_label[w] == 0)
-       continue;
-
-      if (graph->points_to[w])
+       ;
+      else
        bitmap_ior_into(graph->points_to[n], graph->points_to[w]);
+
+      /* If we were the last unvisited successor of w free
+        its points-to set.  */
+      if (--graph->n_pred_of[w] == 0 && w != n)
+       BITMAP_FREE (graph->points_to[w]);
     }
   /* Indirect nodes get fresh variables.  */
   if (!bitmap_bit_p (graph->direct_nodes, n))
@@ -2133,6 +2141,10 @@ label_visit (constraint_graph_t graph, s
        }
       graph->pointer_label[n] = label;
     }
+
+  /* If n has itself as predecessor we delayed freeing points_to.  */
+  if (graph->n_pred_of[n] == 0)
+    BITMAP_FREE (graph->points_to[n]);
 }

 /* Perform offline variable substitution, discovering equivalence
@@ -2159,12 +2171,26 @@ perform_var_substitution (constraint_gra
     if (!bitmap_bit_p (si->visited, si->node_mapping[i]))
       condense_visit (graph, si, si->node_mapping[i]);

+  /* Count the number of nodes a node is predecessor of.  */
+  graph->n_pred_of = XCNEWVEC (unsigned, graph->size);
+  for (i = 0; i < graph->size; i++)
+    {
+      bitmap_iterator bi;
+      unsigned int j;
+      if (si->node_mapping[i] != i)
+       continue;
+      EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[i], 0, j, bi)
+       graph->n_pred_of[si->node_mapping[j]]++;
+    }
+
   bitmap_clear (si->visited);
   /* Actually the label the nodes for pointer equivalences  */
   for (i = 0; i < FIRST_REF_NODE; i++)
     if (!bitmap_bit_p (si->visited, si->node_mapping[i]))
       label_visit (graph, si, si->node_mapping[i]);

+  free (graph->n_pred_of);
+
   /* Calculate location equivalence labels.  */
   for (i = 0; i < FIRST_REF_NODE; i++)
     {