This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH] Compact SSA version namespace when releasing the freelist


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;
 }
 


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]