[PATCH] Fix PR56113

[Richard Biener]

This reduces the amount of memory needed by PTA pointer unification
which has quadratic memory requirements.  It's very easy to improve
the situation where a lot of pointer equivalences are present
by not keeping duplicate bitmaps we unify using a hashtable already.
This reduces the overhead of the testcase in the PR from requiring
peak 2.5GB to 1.4MB instead.  This doesn't change the fact that
the algorithm is quadratic in its memory requirements (worst memory
requirements when it doesn't produce anything useful in the end).

Bootstrap and regtest running on x86_64-unknown-linux-gnu.  I plan
to install this on trunk and the 4.7 branch for the general
memory-hog regressions.

Richard.

2013-01-29  Richard Biener  <rguent...@suse.de>

        PR tree-optimization/56113
        * tree-ssa-structalias.c (equiv_class_lookup): Also return
        the bitmap leader.
        (label_visit): Free duplicate bitmaps and record the leader instead.
        (perform_var_substitution): Adjust.

Index: gcc/tree-ssa-structalias.c
===================================================================
--- gcc/tree-ssa-structalias.c  (revision 195532)
+++ gcc/tree-ssa-structalias.c  (working copy)
@@ -1907,10 +1908,10 @@ equiv_class_label_eq (const void *p1, co
 }
 
 /* Lookup a equivalence class in TABLE by the bitmap of LABELS it
-   contains.  */
+   contains.  Sets *REF_LABELS to the bitmap LABELS is equivalent to.  */
 
 static unsigned int
-equiv_class_lookup (htab_t table, bitmap labels)
+equiv_class_lookup (htab_t table, bitmap labels, bitmap *ref_labels)
 {
   void **slot;
   struct equiv_class_label ecl;
@@ -1921,9 +1922,18 @@ equiv_class_lookup (htab_t table, bitmap
   slot = htab_find_slot_with_hash (table, &ecl,
                                   ecl.hashcode, NO_INSERT);
   if (!slot)
-    return 0;
+    {
+      if (ref_labels)
+       *ref_labels = NULL;
+      return 0;
+    }
   else
-    return ((equiv_class_label_t) *slot)->equivalence_class;
+    {
+      equiv_class_label_t ec = (equiv_class_label_t) *slot;
+      if (ref_labels)
+       *ref_labels = ec->labels;
+      return ec->equivalence_class;
+    }
 }
 
 
@@ -2123,14 +2133,21 @@ label_visit (constraint_graph_t graph, s
 
   if (!bitmap_empty_p (graph->points_to[n]))
     {
+      bitmap ref_points_to;
       unsigned int label = equiv_class_lookup (pointer_equiv_class_table,
-                                              graph->points_to[n]);
+                                              graph->points_to[n],
+                                              &ref_points_to);
       if (!label)
        {
          label = pointer_equiv_class++;
          equiv_class_add (pointer_equiv_class_table,
                           label, graph->points_to[n]);
        }
+      else
+       {
+         BITMAP_FREE (graph->points_to[n]);
+         graph->points_to[n] = ref_points_to;
+       }
       graph->pointer_label[n] = label;
     }
 }
@@ -2190,7 +2223,7 @@ perform_var_substitution (constraint_gra
       /* Look up the location equivalence label if one exists, or make
         one otherwise.  */
       label = equiv_class_lookup (location_equiv_class_table,
-                                 pointed_by);
+                                 pointed_by, NULL);
       if (label == 0)
        {
          label = location_equiv_class++;