Memory overhead of tree-SSA optimization passes

Memory overhead of tree-SSA optimization passes

[Jan Hubicka]

Hi,
I've made another little experiment about memory usage.  On combine.c we
produce 20MB of garbage for -O0 compilation (compared to 12MB of 3.4),
29MB of garbage with -O2 but all optimizers on tree-ssa disabled (so we
only go in and out SSA) and 44MB with default settings.

If you look into individual optimizers, we currently have no optimizer
saving memory (except for possibly DCE that cause abort when disabled)
major offender are dominators and pre together producing 9.8MB of
garbage (roughly 3/4 of the overall overhead)

For PRE we consume most of memory in bitmaps, I am just testing patch
obstackeizing them that should actually help here reducing GGC garbage
to 40MB but still I don't follow why we need such an extreme amount of
bitmaps.

For DOM large portion of consumption comes from the fact that it
reverses every expression several times...

Honza

 -ftree-dce:
ICE with -fno-tree-dce
../../gcc/combine.c:3679: error: Pointers with a memory tag, should have points-to sets or point to malloc
plen_2486, name memory tag: NMT.7797, points-to vars: { }
plen, UID 655
../../gcc/combine.c:3679: internal compiler error: verify_flow_sensitive_alias_info failed.

 -ftree-dominator-opts:

Peak amount of GGC memory allocated before garbage collecting increased from 7806k to 8032k, overall 2.90%
Peak amount of GGC memory still allocated after garbage collectin increased from 5990k to 6018k, overall 0.47%
Amount of produced GGC garbage increased from 37459k to 43156k, overall 15.21%
Amount of memory still referenced at the end of compilation increased from 4429k to 4631k, overall 4.57%
Peak memory use before GGC: 7806k -> 8032k
Peak memory use after GGC: 5990k -> 6018k
Maximum of released memory in single GGC run: 2997k -> 2997k
Garbage: 37459k -> 43156k
Leak: 4631k -> 4429k
Overhead: 4602k -> 5496k
GGC runs: 21 -> 23

 -fno-tree-pre:

Peak amount of GGC memory allocated before garbage collecting increased from 8020k to 8032k, overall 0.15%
Peak amount of GGC memory still allocated after garbage collectin increased from 6011k to 6018k, overall 0.12%
Amount of produced GGC garbage increased from 39034k to 43156k, overall 10.56%
Peak memory use before GGC: 8020k -> 8032k
Peak memory use after GGC: 6011k -> 6018k
Maximum of released memory in single GGC run: 3093k -> 2997k
Garbage: 39034k -> 43156k
Leak: 4631k -> 4628k
Overhead: 5196k -> 5496k
GGC runs: 22 -> 23

 -ftree-lrs:

Peak amount of GGC memory allocated before garbage collecting increased from 7821k to 8032k, overall 2.70%
Peak amount of GGC memory still allocated after garbage collectin increased from 5990k to 6018k, overall 0.47%
Amount of produced GGC garbage increased from 42572k to 43156k, overall 1.37%
Amount of memory still referenced at the end of compilation increased from 4477k to 4631k, overall 3.45%
Peak memory use before GGC: 7821k -> 8032k
Peak memory use after GGC: 5990k -> 6018k
Maximum of released memory in single GGC run: 3025k -> 2997k
Garbage: 42572k -> 43156k
Leak: 4631k -> 4477k
Overhead: 5449k -> 5496k
GGC runs: 24 -> 23

 -ftree-copyrename:

Peak amount of GGC memory allocated before garbage collecting increased from 7903k to 8032k, overall 1.63%
Peak memory use before GGC: 7903k -> 8032k
Peak memory use after GGC: 6050k -> 6018k
Maximum of released memory in single GGC run: 3165k -> 2997k
Garbage: 43579k -> 43156k
Leak: 4631k -> 4721k
Overhead: 5565k -> 5496k
GGC runs: 24 -> 23

 -ftree-ter:

Peak amount of GGC memory allocated before garbage collecting increased from 7920k to 8032k, overall 1.41%
Peak memory use before GGC: 7920k -> 8032k
Peak memory use after GGC: 6064k -> 6018k
Maximum of released memory in single GGC run: 3193k -> 2997k
Garbage: 43666k -> 43156k
Leak: 4631k -> 4734k
Overhead: 5585k -> 5496k
GGC runs: 24 -> 23

 -ftree-loop-optimize:

Peak amount of GGC memory allocated before garbage collecting increased from 7942k to 8032k, overall 1.13%
Peak amount of GGC memory still allocated after garbage collectin increased from 5990k to 6018k, overall 0.47%
Peak memory use before GGC: 7942k -> 8032k
Peak memory use after GGC: 5990k -> 6018k
Maximum of released memory in single GGC run: 3152k -> 2997k
Garbage: 43360k -> 43156k
Leak: 4631k -> 4642k
Overhead: 4788k -> 5496k
GGC runs: 24 -> 23

 -ftree-ch:

Amount of produced GGC garbage increased from 42114k to 43156k, overall 2.47%
Peak memory use before GGC: 8027k -> 8032k
Peak memory use after GGC: 6017k -> 6018k
Maximum of released memory in single GGC run: 2997k -> 2997k
Garbage: 42114k -> 43156k
Leak: 4631k -> 4633k
Overhead: 5094k -> 5496k
GGC runs: 23 -> 23

 -ftree-dse:

Peak amount of GGC memory still allocated after garbage collectin increased from 6010k to 6018k, overall 0.13%
Peak memory use before GGC: 8031k -> 8032k
Peak memory use after GGC: 6010k -> 6018k
Maximum of released memory in single GGC run: 2997k -> 2997k
Garbage: 43139k -> 43156k
Leak: 4631k -> 4631k
Overhead: 5264k -> 5496k
GGC runs: 23 -> 23

 -ftree-ccp:

Peak amount of GGC memory still allocated after garbage collecting increased from 6010k to 6018k, overall 0.13%
Peak memory use before GGC: 8031k -> 8032k
Peak memory use after GGC: 6010k -> 6018k
Maximum of released memory in single GGC run: 2997k -> 2997k
Garbage: 43144k -> 43156k
Leak: 4631k -> 4631k
Overhead: 5476k -> 5496k
GGC runs: 23 -> 23

 -ftree-loop-im:

Amount of memory still referenced at the end of compilation increased from 4626k to 4631k, overall 0.12%
Peak memory use before GGC: 8026k -> 8032k
Peak memory use after GGC: 6012k -> 6018k
Maximum of released memory in single GGC run: 2997k -> 2997k
Garbage: 43161k -> 43156k
Leak: 4631k -> 4626k
Overhead: 5391k -> 5496k
GGC runs: 23 -> 23

 -ftree-combine-temps:

Peak memory use before GGC: 8032k -> 8032k
Peak memory use after GGC: 6018k -> 6018k
Maximum of released memory in single GGC run: 2997k -> 2997k
Garbage: 43156k -> 43156k
Leak: 4631k -> 4631k
Overhead: 5496k -> 5496k
GGC runs: 23 -> 23

Re: Memory overhead of tree-SSA optimization passes

[Diego Novillo]

On Sat, 2004-09-04 at 09:22, Jan Hubicka wrote:

>  -ftree-dce:
> ICE with -fno-tree-dce
> ../../gcc/combine.c:3679: error: Pointers with a memory tag, should have points-to sets or point to malloc
> plen_2486, name memory tag: NMT.7797, points-to vars: { }
> plen, UID 655
> ../../gcc/combine.c:3679: internal compiler error: verify_flow_sensitive_alias_info failed.
> 
Jan,

Could you file a PR against this?  I've seen it before and it's slipped
through the cracks.


Diego.

Re: Memory overhead of tree-SSA optimization passes

[Jan Hubicka]

> On Sat, 2004-09-04 at 09:22, Jan Hubicka wrote:
> 
> >  -ftree-dce:
> > ICE with -fno-tree-dce
> > ../../gcc/combine.c:3679: error: Pointers with a memory tag, should have points-to sets or point to malloc
> > plen_2486, name memory tag: NMT.7797, points-to vars: { }
> > plen, UID 655
> > ../../gcc/combine.c:3679: internal compiler error: verify_flow_sensitive_alias_info failed.
> > 
> Jan,
> 
> Could you file a PR against this?  I've seen it before and it's slipped
> through the cracks.

Done.
Honza
> 
> 
> Diego.
> 

Re: Memory overhead of tree-SSA optimization passes

[Daniel Berlin]

On Sat, 2004-09-04 at 15:22 +0200, Jan Hubicka wrote:
> Hi,
> I've made another little experiment about memory usage.  On combine.c we
> produce 20MB of garbage for -O0 compilation (compared to 12MB of 3.4),
> 29MB of garbage with -O2 but all optimizers on tree-ssa disabled (so we
> only go in and out SSA) and 44MB with default settings.
> 
> If you look into individual optimizers, we currently have no optimizer
> saving memory (except for possibly DCE that cause abort when disabled)
> major offender are dominators and pre together producing 9.8MB of
> garbage (roughly 3/4 of the overall overhead)
> 
> For PRE we consume most of memory in bitmaps, I am just testing patch
> obstackeizing them that should actually help here reducing GGC garbage
> to 40MB but still I don't follow why we need such an extreme amount of
> bitmaps.
> 
Basically, PRE doesn't ever free the sets, it just creates new ones and
lets GGC take care of freeing the old ones.

It's something i've been meaning to clean up for a while (we know when
we can free the old sets, it's just a matter of doing it).
I can fix it if it's really creating that much garbage.
However, it never actually showed up as something that mattered in any
timings i did.

--Dan

[PATCH] Remove all ggc'd bitmaps from PRE (Was Re: Memory overhead of tree-SSA optimization passes)

[Daniel Berlin]

[-- Attachment #1: Type: text/plain, Size: 509 bytes --]

> For PRE we consume most of memory in bitmaps, I am just testing patch
> obstackeizing them that should actually help here reducing GGC garbage
> to 40MB but still I don't follow why we need such an extreme amount of
> bitmaps.

Here's a patch that removes all ggc'd bitmaps from PRE.

It's bootstrapping now (on a day old tree).
If all goes well, i'll rebootstrap and testwhen the tree isn't broken,
add a changelog, and commit it.

However, in any case, it should be usable for your measurement purposes.


[-- Attachment #2: prenoggc.diff --]
[-- Type: text/x-patch, Size: 4029 bytes --]

Index: tree-ssa-pre.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-pre.c,v
retrieving revision 2.30
diff -u -p -r2.30 tree-ssa-pre.c
--- tree-ssa-pre.c	20 Aug 2004 16:48:00 -0000	2.30
+++ tree-ssa-pre.c	4 Sep 2004 16:14:37 -0000
@@ -468,7 +468,7 @@ value_insert_into_set_bitmap (value_set_
 
   if (set->values == NULL)
     {
-      set->values = BITMAP_GGC_ALLOC ();
+      set->values = BITMAP_XMALLOC ();
       bitmap_clear (set->values);
     }
 
@@ -482,13 +482,23 @@ static bitmap_set_t 
 bitmap_set_new (void)
 {
   bitmap_set_t ret = pool_alloc (bitmap_set_pool);
-  ret->expressions = BITMAP_GGC_ALLOC ();
-  ret->values = BITMAP_GGC_ALLOC ();
+  ret->expressions = BITMAP_XMALLOC ();
+  ret->values = BITMAP_XMALLOC ();
   bitmap_clear (ret->expressions);
   bitmap_clear (ret->values);
   return ret;
 }
 
+/* Free a bitmap set SET.  */
+
+static void
+bitmap_set_free (bitmap_set_t set)
+{
+  BITMAP_XFREE (set->expressions);
+  BITMAP_XFREE (set->values);
+  pool_free (bitmap_set_pool, set);
+}
+
 /* Create a new set.  */
 
 static value_set_t
@@ -503,6 +513,18 @@ set_new  (bool indexed)
   return ret;
 }
 
+/* Free a value set SET.  */
+static void
+value_set_free (value_set_t set)
+{
+  /* Note that we don't free the elements, they don't make up enough garbage
+  that it is worth the O(n) linked list walk.  The pool destruction at the end
+  of the PRE pass will free them for us.  */
+  if (set->indexed)
+    BITMAP_XFREE (set->values);
+  pool_free (value_set_pool, set);
+}
+
 /* Insert an expression EXPR into a bitmapped set.  */
 
 static void
@@ -1133,7 +1155,7 @@ compute_antic_aux (basic_block block)
   value_set_t S, old, ANTIC_OUT;
   value_set_node_t node;
   
-  ANTIC_OUT = S = NULL;
+  ANTIC_OUT = S = old = NULL;
   /* If any edges from predecessors are abnormal, antic_in is empty, so
      punt.  Remember that the block has an incoming abnormal edge by
      setting the BB_VISITED flag.  */
@@ -1152,7 +1174,6 @@ compute_antic_aux (basic_block block)
       goto visit_sons;
     }
   
-
   old = set_new (false);
   set_copy (old, ANTIC_IN (block));
   ANTIC_OUT = set_new (true);
@@ -1207,6 +1228,8 @@ compute_antic_aux (basic_block block)
   /* Generate ANTIC_OUT - TMP_GEN */
   S = bitmap_set_subtract_from_value_set (ANTIC_OUT, TMP_GEN (block), false);
 
+  value_set_free (ANTIC_IN (block));
+
   /* Start ANTIC_IN with EXP_GEN - TMP_GEN */
   ANTIC_IN (block) = bitmap_set_subtract_from_value_set (EXP_GEN (block), 
 							 TMP_GEN (block),
@@ -1237,6 +1260,9 @@ compute_antic_aux (basic_block block)
 
     }
 
+  value_set_free (S);
+  value_set_free (old);
+
   for (son = first_dom_son (CDI_POST_DOMINATORS, block);
        son;
        son = next_dom_son (CDI_POST_DOMINATORS, son))
@@ -1624,6 +1650,10 @@ insert (void)
     }
   if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS))
     fprintf (dump_file, "insert required %d iterations\n", num_iterations);
+
+  FOR_ALL_BB (bb)
+    bitmap_set_free (NEW_SETS (bb));
+  
 }
 
 
@@ -1979,22 +2009,28 @@ static void
 fini_pre (void)
 {
   basic_block bb;
-
-  free_alloc_pool (value_set_pool);
-  free_alloc_pool (bitmap_set_pool);
-  free_alloc_pool (value_set_node_pool);
-  free_alloc_pool (binary_node_pool);
-  free_alloc_pool (reference_node_pool);
-  free_alloc_pool (unary_node_pool);
+  
   htab_delete (phi_translate_table);
   remove_fake_exit_edges ();
 
   FOR_ALL_BB (bb)
     {
+      value_set_free (EXP_GEN (bb));
+      bitmap_set_free (PHI_GEN (bb));
+      bitmap_set_free (TMP_GEN (bb));
+      bitmap_set_free (AVAIL_OUT (bb));
+      value_set_free (ANTIC_IN (bb));
       free (bb->aux);
       bb->aux = NULL;
     }
 
+  free_alloc_pool (value_set_pool);
+  free_alloc_pool (bitmap_set_pool);
+  free_alloc_pool (value_set_node_pool);
+  free_alloc_pool (binary_node_pool);
+  free_alloc_pool (reference_node_pool);
+  free_alloc_pool (unary_node_pool);
+
   free_dominance_info (CDI_POST_DOMINATORS);
   vn_delete ();
 

Re: Memory overhead of tree-SSA optimization passes

[Jan Hubicka]

> On Sat, 2004-09-04 at 15:22 +0200, Jan Hubicka wrote:
> > Hi,
> > I've made another little experiment about memory usage.  On combine.c we
> > produce 20MB of garbage for -O0 compilation (compared to 12MB of 3.4),
> > 29MB of garbage with -O2 but all optimizers on tree-ssa disabled (so we
> > only go in and out SSA) and 44MB with default settings.
> > 
> > If you look into individual optimizers, we currently have no optimizer
> > saving memory (except for possibly DCE that cause abort when disabled)
> > major offender are dominators and pre together producing 9.8MB of
> > garbage (roughly 3/4 of the overall overhead)
> > 
> > For PRE we consume most of memory in bitmaps, I am just testing patch
> > obstackeizing them that should actually help here reducing GGC garbage
> > to 40MB but still I don't follow why we need such an extreme amount of
> > bitmaps.
> > 
> Basically, PRE doesn't ever free the sets, it just creates new ones and
> lets GGC take care of freeing the old ones.
> 
> It's something i've been meaning to clean up for a while (we know when
> we can free the old sets, it's just a matter of doing it).
> I can fix it if it's really creating that much garbage.
> However, it never actually showed up as something that mattered in any
> timings i did.

Well, 15% of garbage is quite a lot, but the obstack trick seems to be
good enought (ie we temporarily allocate some 4MB of bitmaps but get rid
of them quickly and cheaply), so I am not sure if any further work on
cleaning them while doing the PRE itself would pay back.

Honza
> 
> --Dan
> 

Re: [PATCH] Remove all ggc'd bitmaps from PRE (Was Re: Memory overhead of tree-SSA optimization passes)

[Jan Hubicka]

> > For PRE we consume most of memory in bitmaps, I am just testing patch
> > obstackeizing them that should actually help here reducing GGC garbage
> > to 40MB but still I don't follow why we need such an extreme amount of
> > bitmaps.
> 
> Here's a patch that removes all ggc'd bitmaps from PRE.
> 
> It's bootstrapping now (on a day old tree).
> If all goes well, i'll rebootstrap and testwhen the tree isn't broken,
> add a changelog, and commit it.
> 
> However, in any case, it should be usable for your measurement purposes.
> 
Actually I am using the attached patch.  It reduces the memory footprint
by 10% as one would expect that is good by itself I think.  I am waiting
for numbers form automated tester but unless bootstrap unbreaks we won't
get them before monday as I am just about leave for one day.

Is your patch actually able to re-use the bitmaps during the PRE
process?  If not, I think obstack are actually better here than xmalloc
based approach simply because the xmalloced bitmaps gets moved into free
pool where they will stay unused as no one else apparently needs that
many of them (but I plan to actually add some statistics too), while
obstack memory just gets used for other purposes cheaply.

But this all needs to wait for day after tomorrow...

Honza

Index: tree-ssa-pre.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-pre.c,v
retrieving revision 2.30
diff -c -3 -p -r2.30 tree-ssa-pre.c
*** tree-ssa-pre.c	20 Aug 2004 16:48:00 -0000	2.30
--- tree-ssa-pre.c	4 Sep 2004 13:13:54 -0000
*************** static alloc_pool value_set_node_pool;
*** 306,311 ****
--- 306,312 ----
  static alloc_pool binary_node_pool;
  static alloc_pool unary_node_pool;
  static alloc_pool reference_node_pool;
+ static struct obstack grand_bitmap_obstack;
  
  /* Set of blocks with statements that have had its EH information
     cleaned up.  */
*************** value_insert_into_set_bitmap (value_set_
*** 468,474 ****
  
    if (set->values == NULL)
      {
!       set->values = BITMAP_GGC_ALLOC ();
        bitmap_clear (set->values);
      }
  
--- 469,475 ----
  
    if (set->values == NULL)
      {
!       set->values = BITMAP_OBSTACK_ALLOC (&grand_bitmap_obstack);
        bitmap_clear (set->values);
      }
  
*************** static bitmap_set_t 
*** 482,489 ****
  bitmap_set_new (void)
  {
    bitmap_set_t ret = pool_alloc (bitmap_set_pool);
!   ret->expressions = BITMAP_GGC_ALLOC ();
!   ret->values = BITMAP_GGC_ALLOC ();
    bitmap_clear (ret->expressions);
    bitmap_clear (ret->values);
    return ret;
--- 483,490 ----
  bitmap_set_new (void)
  {
    bitmap_set_t ret = pool_alloc (bitmap_set_pool);
!   ret->expressions = BITMAP_OBSTACK_ALLOC (&grand_bitmap_obstack);
!   ret->values = BITMAP_OBSTACK_ALLOC (&grand_bitmap_obstack);
    bitmap_clear (ret->expressions);
    bitmap_clear (ret->values);
    return ret;
*************** init_pre (void)
*** 1944,1949 ****
--- 1945,1951 ----
    FOR_ALL_BB (bb)
      bb->aux = xcalloc (1, sizeof (struct bb_value_sets));
  
+   obstack_init (&grand_bitmap_obstack);
    phi_translate_table = htab_create (511, expr_pred_trans_hash,
  				     expr_pred_trans_eq, free);
    value_set_pool = create_alloc_pool ("Value sets",
*************** fini_pre (void)
*** 1980,1985 ****
--- 1982,1988 ----
  {
    basic_block bb;
  
+   obstack_free (&grand_bitmap_obstack, NULL);
    free_alloc_pool (value_set_pool);
    free_alloc_pool (bitmap_set_pool);
    free_alloc_pool (value_set_node_pool);

Re: [PATCH] Remove all ggc'd bitmaps from PRE (Was Re: Memory overhead of tree-SSA optimization passes)

[Daniel Berlin]

On Sat, 2004-09-04 at 23:51 +0200, Jan Hubicka wrote:
> > > For PRE we consume most of memory in bitmaps, I am just testing patch
> > > obstackeizing them that should actually help here reducing GGC garbage
> > > to 40MB but still I don't follow why we need such an extreme amount of
> > > bitmaps.
> > 
> > Here's a patch that removes all ggc'd bitmaps from PRE.
> > 
> > It's bootstrapping now (on a day old tree).
> > If all goes well, i'll rebootstrap and testwhen the tree isn't broken,
> > add a changelog, and commit it.
> > 
> > However, in any case, it should be usable for your measurement purposes.
> > 
> Actually I am using the attached patch.  It reduces the memory footprint
> by 10% as one would expect that is good by itself I think.  I am waiting
> for numbers form automated tester but unless bootstrap unbreaks we won't
> get them before monday as I am just about leave for one day.
> 
> Is your patch actually able to re-use the bitmaps during the PRE
> process?  
Yes, but probably not even that obstack'ing them isn't a win.