[tree-ssa] Avoid nondeterminism in tree-ssanames

[Jan Hubicka <jh at suse dot cz>]

Hi,
I've run into problem that tree-ssanames in combination with garbage
collector may produce non-deterministic results.  The problem is that
garbage collector invoked form the middle of SSA compilation path (not
done in official tree) zaps the free list of nodes.
This avoids re-use of ssa versions that results in different results of
compilation in some side cases and also in more memory consumption
(143->151MB on Gerald's testcase).
The attached patch solves this by avoiding free list to be GGCeed while
compiling the function.  It also adds code for re-using SSA_NAME nodes
from compilations of previous functions in case GGC didn't happen in the
middle.  I get about 4% memory savings on compiling C frontend, but 0%
on gerald's testcase... interesting :)

Bootstrapped/regtested i686-pc-gnu-linux and x86_64-pc-gnu-linux.  OK?

Honza

	* tree-ssanames.c (local_free_ssanames, local_last_ssaname,
	ssa_name_nodes_reused_globally): New static variables.
	(init_ssanames): Init local list.
	(fini_ssanames): Put local list into global list.
	(ssanames_print_statistics): Print ssa_name_nodes_reused_globally.
	(make_ssa_name): Globally reuse nodes whenever possible.
Index: tree-ssanames.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssanames.c,v
retrieving revision 1.1.2.5
diff -c -3 -p -r1.1.2.5 tree-ssanames.c
*** tree-ssanames.c	29 Nov 2003 12:43:10 -0000	1.1.2.5
--- tree-ssanames.c	29 Nov 2003 19:02:17 -0000
*************** Boston, MA 02111-1307, USA.  */
*** 60,68 ****
  /* Next SSA version number to be allocated.  */
  unsigned int highest_ssa_version;
                                                                                  
! /* Free list of SSA_NAMEs.  This list is wiped at the end of each function
!    after we leave SSA form.  */
  static GTY ((deletable (""))) tree free_ssanames;
  
  /* Version numbers with special meanings.  We start allocating new version
     numbers after the special ones.  */
--- 60,73 ----
  /* Next SSA version number to be allocated.  */
  unsigned int highest_ssa_version;
                                                                                  
! /* Free list of SSA_NAMEs available from compilation of previous functions.  */
  static GTY ((deletable (""))) tree free_ssanames;
+ /* Free list of SSA_NAMEs.  This list is is used only withing single function
+    and it's reason is to allow easy SSA_NAME_VERSION reuse.  We don't garbage
+    collect this list in order to make re-use happen same way independently
+    on GGC invokations.  */
+ static GTY (()) tree local_free_ssanames;
+ static GTY (()) tree local_last_ssaname;
  
  /* Version numbers with special meanings.  We start allocating new version
     numbers after the special ones.  */
*************** static GTY ((deletable (""))) tree free_
*** 70,75 ****
--- 75,81 ----
  
  #ifdef GATHER_STATISTICS
  unsigned int ssa_name_nodes_reused;
+ unsigned int ssa_name_nodes_reused_globally;
  unsigned int ssa_name_nodes_created;
  #endif
  
*************** void
*** 79,85 ****
  init_ssanames (void)
  {
    highest_ssa_version = UNUSED_NAME_VERSION + 1;
!   free_ssanames = NULL;
  }
  
  /* Finalize management of SSA_NAMEs.  */
--- 85,91 ----
  init_ssanames (void)
  {
    highest_ssa_version = UNUSED_NAME_VERSION + 1;
!   local_free_ssanames = local_last_ssaname = NULL;
  }
  
  /* Finalize management of SSA_NAMEs.  */
*************** init_ssanames (void)
*** 87,93 ****
  void
  fini_ssanames (void)
  {
!   free_ssanames = NULL;
  }
  
  /* Dump some simple statistics regarding the re-use of SSA_NAME nodes.  */
--- 93,106 ----
  void
  fini_ssanames (void)
  {
!   if (local_last_ssaname)
!     {
!       if (TREE_CHAIN (local_last_ssaname))
! 	abort ();
!       TREE_CHAIN (local_last_ssaname) = free_ssanames;
!       free_ssanames = local_free_ssanames;
!     }
!   local_free_ssanames = local_last_ssaname = NULL;
  }
  
  /* Dump some simple statistics regarding the re-use of SSA_NAME nodes.  */
*************** ssanames_print_statistics (void)
*** 98,103 ****
--- 111,117 ----
  {
    fprintf (stderr, "SSA_NAME nodes allocated: %u\n", ssa_name_nodes_created);
    fprintf (stderr, "SSA_NAME nodes reused: %u\n", ssa_name_nodes_reused);
+   fprintf (stderr, "SSA_NAME nodes reused globally: %u\n", ssa_name_nodes_reused_globally);
  }
  #endif
  
*************** make_ssa_name (tree var, tree stmt)
*** 122,133 ****
    /* If our free list has an element, then use it.  Also reuse the
       SSA version number of the element on the free list which helps
       keep sbitmaps and arrays sized HIGHEST_SSA_VERSION smaller.  */
!   if (free_ssanames)
      {
        unsigned int save_version;
  
!       t = free_ssanames;
!       free_ssanames = TREE_CHAIN (free_ssanames);
  #ifdef GATHER_STATISTICS
        ssa_name_nodes_reused++;
  #endif
--- 136,149 ----
    /* If our free list has an element, then use it.  Also reuse the
       SSA version number of the element on the free list which helps
       keep sbitmaps and arrays sized HIGHEST_SSA_VERSION smaller.  */
!   if (local_free_ssanames)
      {
        unsigned int save_version;
  
!       t = local_free_ssanames;
!       local_free_ssanames = TREE_CHAIN (local_free_ssanames);
!       if (!local_free_ssanames)
! 	local_last_ssaname = NULL;
  #ifdef GATHER_STATISTICS
        ssa_name_nodes_reused++;
  #endif
*************** make_ssa_name (tree var, tree stmt)
*** 139,144 ****
--- 155,174 ----
        TREE_SET_CODE (t, SSA_NAME);
        SSA_NAME_VERSION (t) = save_version;
      }
+   else if (free_ssanames)
+     {
+       t = free_ssanames;
+       free_ssanames = TREE_CHAIN (free_ssanames);
+ #ifdef GATHER_STATISTICS
+       ssa_name_nodes_reused_globally++;
+ #endif
+ 
+       /* Clear the node so that it looks just like one we would have
+ 	 received from make_node.  */
+       memset (t, 0, tree_size (t));
+       TREE_SET_CODE (t, SSA_NAME);
+       SSA_NAME_VERSION (t) = highest_ssa_version++;
+     }
    else
      {
        t = make_node (SSA_NAME);
*************** release_ssa_name (tree var)
*** 176,183 ****
    if (! SSA_NAME_IN_FREE_LIST (var))
      {
        SSA_NAME_IN_FREE_LIST (var) = 1;
!       TREE_CHAIN (var) = free_ssanames;
!       free_ssanames = var;
      }
  }
  
--- 206,215 ----
    if (! SSA_NAME_IN_FREE_LIST (var))
      {
        SSA_NAME_IN_FREE_LIST (var) = 1;
!       TREE_CHAIN (var) = local_free_ssanames;
!       local_free_ssanames = var;
!       if (!local_last_ssaname)
! 	local_last_ssaname = var;
      }
  }