Patchwork Compact SSA version namespace when releasing the freelist

login
register
mail settings
Submitter Richard Guenther
Date April 5, 2012, 10:13 a.m.
Message ID <Pine.LNX.4.64.1204051152180.17575@jbgna.fhfr.qr>
Download mbox | patch
Permalink /patch/150902/
State New
Headers show

Comments

Richard Guenther - April 5, 2012, 10:13 a.m.
Currently we release the memory for released SSA names (which we keep
around on a freelist, mainly to try to keep the SSA version namespace
dense) after early optimizations.  This has the negative impact
(as documented) of permanently establishing holes in the SSA version
namespace.  The following patch fixes this in a simple way.

Bootstrapped and tested on x86_64-unknown-linux-gnu.

If you build fold-const.c with -O2 the distribution of released
ssa names / removed holes is as follows:

43 release_ssa "SSA names released" 34900
43 release_ssa "SSA name holes removed" 34900

which means we never have "trailing" released SSA names, all SSA
names on the freelist are for holes.  The following is the
distribution over releases happening per function:

43 release_ssa "SSA name holes removed == 0" 16
43 release_ssa "SSA name holes removed == 1" 13
43 release_ssa "SSA name holes removed == 2" 13
43 release_ssa "SSA name holes removed == 3" 6
43 release_ssa "SSA name holes removed == 4" 12
43 release_ssa "SSA name holes removed == 5" 3
43 release_ssa "SSA name holes removed == 6" 4
43 release_ssa "SSA name holes removed == 7" 5
43 release_ssa "SSA name holes removed == 8" 4
43 release_ssa "SSA name holes removed == 9" 4
43 release_ssa "SSA name holes removed == 10" 4
43 release_ssa "SSA name holes removed == 11" 4
43 release_ssa "SSA name holes removed == 13" 1
43 release_ssa "SSA name holes removed == 14" 5
43 release_ssa "SSA name holes removed == 16" 4
43 release_ssa "SSA name holes removed == 17" 1
43 release_ssa "SSA name holes removed == 18" 4
43 release_ssa "SSA name holes removed == 19" 1
43 release_ssa "SSA name holes removed == 20" 3
43 release_ssa "SSA name holes removed == 22" 1
43 release_ssa "SSA name holes removed == 23" 4
43 release_ssa "SSA name holes removed == 24" 1
43 release_ssa "SSA name holes removed == 26" 2
43 release_ssa "SSA name holes removed == 27" 1
43 release_ssa "SSA name holes removed == 28" 1
43 release_ssa "SSA name holes removed == 30" 2
43 release_ssa "SSA name holes removed == 32" 2
43 release_ssa "SSA name holes removed == 33" 3
43 release_ssa "SSA name holes removed == 34" 2
43 release_ssa "SSA name holes removed == 35" 1
43 release_ssa "SSA name holes removed == 36" 1
43 release_ssa "SSA name holes removed == 37" 1
43 release_ssa "SSA name holes removed == 39" 1
43 release_ssa "SSA name holes removed == 40" 1
43 release_ssa "SSA name holes removed == 41" 1
43 release_ssa "SSA name holes removed == 42" 1
43 release_ssa "SSA name holes removed == 46" 1
43 release_ssa "SSA name holes removed == 47" 2
43 release_ssa "SSA name holes removed == 48" 1
43 release_ssa "SSA name holes removed == 50" 1
43 release_ssa "SSA name holes removed == 51" 1
43 release_ssa "SSA name holes removed == 57" 1
43 release_ssa "SSA name holes removed == 59" 1
43 release_ssa "SSA name holes removed == 61" 2
43 release_ssa "SSA name holes removed == 63" 2
43 release_ssa "SSA name holes removed == 67" 1
43 release_ssa "SSA name holes removed == 68" 1
43 release_ssa "SSA name holes removed == 70" 1
43 release_ssa "SSA name holes removed == 75" 1
43 release_ssa "SSA name holes removed == 76" 1
43 release_ssa "SSA name holes removed == 78" 1
43 release_ssa "SSA name holes removed == 86" 1
43 release_ssa "SSA name holes removed == 87" 1
43 release_ssa "SSA name holes removed == 89" 2
43 release_ssa "SSA name holes removed == 90" 1
43 release_ssa "SSA name holes removed == 94" 1
43 release_ssa "SSA name holes removed == 95" 1
43 release_ssa "SSA name holes removed == 100" 1
43 release_ssa "SSA name holes removed == 103" 1
43 release_ssa "SSA name holes removed == 106" 1
43 release_ssa "SSA name holes removed == 109" 1
43 release_ssa "SSA name holes removed == 114" 1
43 release_ssa "SSA name holes removed == 116" 1
43 release_ssa "SSA name holes removed == 121" 1
43 release_ssa "SSA name holes removed == 122" 2
43 release_ssa "SSA name holes removed == 125" 1
43 release_ssa "SSA name holes removed == 131" 1
43 release_ssa "SSA name holes removed == 132" 1
43 release_ssa "SSA name holes removed == 133" 2
43 release_ssa "SSA name holes removed == 145" 3
43 release_ssa "SSA name holes removed == 150" 1
43 release_ssa "SSA name holes removed == 154" 1
43 release_ssa "SSA name holes removed == 168" 1
43 release_ssa "SSA name holes removed == 171" 1
43 release_ssa "SSA name holes removed == 178" 1
43 release_ssa "SSA name holes removed == 181" 1
43 release_ssa "SSA name holes removed == 195" 1
43 release_ssa "SSA name holes removed == 199" 1
43 release_ssa "SSA name holes removed == 206" 1
43 release_ssa "SSA name holes removed == 257" 1
43 release_ssa "SSA name holes removed == 258" 1
43 release_ssa "SSA name holes removed == 288" 1
43 release_ssa "SSA name holes removed == 375" 1
43 release_ssa "SSA name holes removed == 517" 1
43 release_ssa "SSA name holes removed == 542" 1
43 release_ssa "SSA name holes removed == 547" 1
43 release_ssa "SSA name holes removed == 727" 1
43 release_ssa "SSA name holes removed == 789" 1
43 release_ssa "SSA name holes removed == 1196" 1
43 release_ssa "SSA name holes removed == 1562" 1
43 release_ssa "SSA name holes removed == 1653" 1
43 release_ssa "SSA name holes removed == 1791" 1
43 release_ssa "SSA name holes removed == 2674" 1
43 release_ssa "SSA name holes removed == 14851" 1

We seem to have quite some "dead" functions in fold-const.c ;)

I didn't measure any off-noise memory/compile-time effect of this
patch though.

Richard.

2012-04-05  Richard Guenther  <rguenther@suse.de>

	* tree-ssanames.c (release_dead_ssa_names): Compact the SSA
	version namespace as we release the freelist.
Diego Novillo - April 5, 2012, 3:27 p.m.
On 4/5/12 6:13 AM, Richard Guenther wrote:
>
> Currently we release the memory for released SSA names (which we keep
> around on a freelist, mainly to try to keep the SSA version namespace
> dense) after early optimizations.  This has the negative impact
> (as documented) of permanently establishing holes in the SSA version
> namespace.  The following patch fixes this in a simple way.
>
> Bootstrapped and tested on x86_64-unknown-linux-gnu.
>
> If you build fold-const.c with -O2 the distribution of released
> ssa names / removed holes is as follows:
>
> 43 release_ssa "SSA names released" 34900
> 43 release_ssa "SSA name holes removed" 34900

Could you elaborate on what this output means?  What is 43?  What is 34900?

> which means we never have "trailing" released SSA names, all SSA
> names on the freelist are for holes.  The following is the
> distribution over releases happening per function:
>
> 43 release_ssa "SSA name holes removed == 0" 16
> 43 release_ssa "SSA name holes removed == 1" 13

Likewise here.  What does this output mean?


> We seem to have quite some "dead" functions in fold-const.c ;)
>
> I didn't measure any off-noise memory/compile-time effect of this
> patch though.

I ask because I don't understand these two conclusions.  You're saying 
that we don't do a lot of this, so compile-time effects should be nil?


Thanks.  Diego.
Richard Guenther - April 6, 2012, 5:48 p.m.
On Thu, Apr 5, 2012 at 5:27 PM, Diego Novillo <dnovillo@google.com> wrote:
> On 4/5/12 6:13 AM, Richard Guenther wrote:
>>
>>
>> Currently we release the memory for released SSA names (which we keep
>> around on a freelist, mainly to try to keep the SSA version namespace
>> dense) after early optimizations.  This has the negative impact
>> (as documented) of permanently establishing holes in the SSA version
>> namespace.  The following patch fixes this in a simple way.
>>
>> Bootstrapped and tested on x86_64-unknown-linux-gnu.
>>
>> If you build fold-const.c with -O2 the distribution of released
>> ssa names / removed holes is as follows:
>>
>> 43 release_ssa "SSA names released" 34900
>> 43 release_ssa "SSA name holes removed" 34900
>
>
> Could you elaborate on what this output means?  What is 43?  What is 34900?

It's citing from -fdump-statistics-stats output, 43 is the pass number
of the 'release_ssa'
pass, 34900 is the sum of released ssa names per function.  Thus
overall we released
34900 SSA names during the compile of fold-const.c

>
>> which means we never have "trailing" released SSA names, all SSA
>> names on the freelist are for holes.  The following is the
>> distribution over releases happening per function:
>>
>> 43 release_ssa "SSA name holes removed == 0" 16
>> 43 release_ssa "SSA name holes removed == 1" 13
>
>
> Likewise here.  What does this output mean?

That's with changed statistics accounting, it's a histogram for the per-function
number SSA names that got released, thus for 16 functions we released zero
SSA names, for 13 functions one.

>
>
>> We seem to have quite some "dead" functions in fold-const.c ;)
>>
>> I didn't measure any off-noise memory/compile-time effect of this
>> patch though.
>
>
> I ask because I don't understand these two conclusions.  You're saying that
> we don't do a lot of this, so compile-time effects should be nil?

No, I'm saying despite some significant savings in SSA names namespace
we don't have too many sbitmaps (the SSA renamer has one) or walks over
the SSA name array.  And we definitely don't have ones that would exhibit
quadratic behavior in the size of the SSA name array.

Richard.

>
> Thanks.  Diego.
Diego Novillo - April 7, 2012, 7:37 p.m.
On 4/6/12 1:48 PM, Richard Guenther wrote:

> That's with changed statistics accounting, it's a histogram for the per-function
> number SSA names that got released, thus for 16 functions we released zero
> SSA names, for 13 functions one.

Great, thanks.  Is this documented in the internals documentation?


Diego.

Patch

Index: gcc/tree-ssanames.c
===================================================================
--- gcc/tree-ssanames.c	(revision 186135)
+++ gcc/tree-ssanames.c	(working copy)
@@ -325,14 +325,14 @@  replace_ssa_name_symbol (tree ssa_name,
   TREE_TYPE (ssa_name) = TREE_TYPE (sym);
 }
 
-/* Return SSA names that are unused to GGC memory.  This is used to keep
-   footprint of compiler during interprocedural optimization.
-   As a side effect the SSA_NAME_VERSION number reuse is reduced
-   so this function should not be used too often.  */
+/* Return SSA names that are unused to GGC memory and compact the SSA
+   version namespace.  This is used to keep footprint of compiler during
+   interprocedural optimization.  */
 static unsigned int
 release_dead_ssa_names (void)
 {
   tree t;
+  unsigned i, j;
   int n = VEC_length (tree, FREE_SSANAMES (cfun));
   referenced_var_iterator rvi;
 
@@ -340,14 +340,33 @@  release_dead_ssa_names (void)
      eventually dead variables so a bunch of memory is held live.  */
   FOR_EACH_REFERENCED_VAR (cfun, t, rvi)
     set_current_def (t, NULL);
+
   /* Now release the freelist.  */
   VEC_free (tree, gc, FREE_SSANAMES (cfun));
   FREE_SSANAMES (cfun) = NULL;
 
+  /* And compact the SSA number space.  We make sure to not change the
+     relative order of SSA versions.  */
+  for (i = 1, j = 1; i < VEC_length (tree, cfun->gimple_df->ssa_names); ++i)
+    {
+      tree name = ssa_name (i);
+      if (name)
+	{
+	  if (i != j)
+	    {
+	      SSA_NAME_VERSION (name) = j;
+	      VEC_replace (tree, cfun->gimple_df->ssa_names, j, name);
+	    }
+	  j++;
+	}
+    }
+  VEC_truncate (tree, cfun->gimple_df->ssa_names, j);
+
   statistics_counter_event (cfun, "SSA names released", n);
+  statistics_counter_event (cfun, "SSA name holes removed", i - j);
   if (dump_file)
-    fprintf (dump_file, "Released %i names, %.2f%%\n",
-	     n, n * 100.0 / num_ssa_names);
+    fprintf (dump_file, "Released %i names, %.2f%%, removed %i holes\n",
+	     n, n * 100.0 / num_ssa_names, i - j);
   return 0;
 }