* [PATCH] Compact SSA version namespace when releasing the freelist
@ 2012-04-05 10:14 Richard Guenther
2012-04-05 15:27 ` Diego Novillo
0 siblings, 1 reply; 4+ messages in thread
From: Richard Guenther @ 2012-04-05 10:14 UTC (permalink / raw)
To: gcc-patches
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.
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;
}
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH] Compact SSA version namespace when releasing the freelist
2012-04-05 10:14 [PATCH] Compact SSA version namespace when releasing the freelist Richard Guenther
@ 2012-04-05 15:27 ` Diego Novillo
2012-04-06 17:48 ` Richard Guenther
0 siblings, 1 reply; 4+ messages in thread
From: Diego Novillo @ 2012-04-05 15:27 UTC (permalink / raw)
To: Richard Guenther; +Cc: gcc-patches
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.
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH] Compact SSA version namespace when releasing the freelist
2012-04-05 15:27 ` Diego Novillo
@ 2012-04-06 17:48 ` Richard Guenther
2012-04-07 19:37 ` Diego Novillo
0 siblings, 1 reply; 4+ messages in thread
From: Richard Guenther @ 2012-04-06 17:48 UTC (permalink / raw)
To: Diego Novillo; +Cc: Richard Guenther, gcc-patches
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.
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH] Compact SSA version namespace when releasing the freelist
2012-04-06 17:48 ` Richard Guenther
@ 2012-04-07 19:37 ` Diego Novillo
0 siblings, 0 replies; 4+ messages in thread
From: Diego Novillo @ 2012-04-07 19:37 UTC (permalink / raw)
To: Richard Guenther; +Cc: Richard Guenther, gcc-patches
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.
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2012-04-07 19:37 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2012-04-05 10:14 [PATCH] Compact SSA version namespace when releasing the freelist Richard Guenther
2012-04-05 15:27 ` Diego Novillo
2012-04-06 17:48 ` Richard Guenther
2012-04-07 19:37 ` Diego Novillo
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).