[patch] cse.c: Speed up cse_reg_info maintanance - Part 3

[Kazu Hirata]

Hi,

Attached is a patch to speed up cse_reg_info maintainance by
dramatically simplifying the memory allocation.

The patch replaces this complicated use of xrealloc with xmalloc.

Here is a timing in seconds for ./cc1 -quiet -O2 -o /dev/null.

             original patched   diff%
c-common.i     18.334  18.231 -0.561%
combine.i      17.475  17.425 -0.286%
fold-const.i   38.048  37.938 -0.289%
reload.i       13.497  13.444 -0.392%
reload1.i      14.258  14.229 -0.203%
cc1-i files   212.457 212.256 -0.094%

cc1-i files were compiled only once.

To my surprise, it's better to free memory when we are not using it,
that is, between passes of cse_main.  I thought it would be a good
idea to keep it if similar amount of memory is used over and over.
Maybe other passes can use the same memory locations for other
purposes and thereby improve locality!?  xrealloc may have been
somewhat expensive.

Of course, I saw no difference in generated code with this patch
applied.

Tested on i686-pc-linux-gnu.  OK to apply?

Kazu Hirata

2005-02-01  Kazu Hirata  <kazu@cs.umass.edu>

	* cse.c (cse_reg_info_table_size,
	cse_reg_info_table_first_uninitialized): Remove.
	(init_cse_reg_info): Always allocate with xmalloc.
	(fini_cse_reg_info): New.
	(cse_main): Call fini_cse_reg_info.

Index: cse.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cse.c,v
retrieving revision 1.339
diff -c -d -p -r1.339 cse.c
*** cse.c	1 Feb 2005 00:41:56 -0000	1.339
--- cse.c	1 Feb 2005 02:32:02 -0000
*************** struct cse_reg_info
*** 326,337 ****
  /* A table of cse_reg_info indexed by register numbers.  */
  struct cse_reg_info *cse_reg_info_table;
  
- /* The size of the above table.  */
- static unsigned int cse_reg_info_table_size;
- 
- /* The index of the first entry that has not been initialized.  */
- static unsigned int cse_reg_info_table_first_uninitialized;
- 
  /* The timestamp at the beginning of the current run of
     cse_basic_block.  We increment this variable at at the beginning of
     the current run of cse_basic_block.  The timestamp field of a
--- 326,331 ----
*************** notreg_cost (rtx x, enum rtx_code outer)
*** 839,888 ****
  static void
  init_cse_reg_info (unsigned int nregs)
  {
!   /* Do we need to grow the table?  */
!   if (nregs > cse_reg_info_table_size)
!     {
!       unsigned int new_size;
! 
!       if (cse_reg_info_table_size < 2048)
! 	{
! 	  /* Compute a new size that is a power of 2 and no smaller
! 	     than the large of NREGS and 64.  */
! 	  new_size = (cse_reg_info_table_size
! 		      ? cse_reg_info_table_size : 64);
! 
! 	  while (new_size < nregs)
! 	    new_size *= 2;
! 	}
!       else
! 	{
! 	  /* If we need a big table, allocate just enough to hold
! 	     NREGS registers.  */
! 	  new_size = nregs;
! 	}
  
!       /* Reallocate the table with NEW_SIZE entries.  */
!       cse_reg_info_table = xrealloc (cse_reg_info_table,
! 				     (sizeof (struct cse_reg_info)
! 				      * new_size));
!       cse_reg_info_table_size = new_size;
!     }
  
!   /* Do we have all of the first NREGS entries initialized?  */
!   if (cse_reg_info_table_first_uninitialized < nregs)
!     {
!       unsigned int old_timestamp = cse_reg_info_timestamp - 1;
!       unsigned int i;
  
!       /* Put the old timestamp on newly allocated entries so that they
! 	 will all be considered out of date.  We do not touch those
! 	 entries beyond the first NREGS entries to be nice to the
! 	 virtual memory.  */
!       for (i = cse_reg_info_table_first_uninitialized; i < nregs; i++)
! 	cse_reg_info_table[i].timestamp = old_timestamp;
  
!       cse_reg_info_table_first_uninitialized = nregs;
!     }
  }
  
  /* Given REGNO, ensure that a cse_reg_info entry exists for REGNO by
--- 833,853 ----
  static void
  init_cse_reg_info (unsigned int nregs)
  {
!   unsigned int i;
  
!   cse_reg_info_table = xmalloc (sizeof (struct cse_reg_info) * nregs);
!   cse_reg_info_timestamp = 0;
  
!   for (i = 0; i < nregs; i++)
!     cse_reg_info_table[i].timestamp = 0;
! }
  
! /* Free CSE_REG_INFO_TABLE.  */
  
! static void
! fini_cse_reg_info (void)
! {
!   free (cse_reg_info_table);
  }
  
  /* Given REGNO, ensure that a cse_reg_info entry exists for REGNO by
*************** cse_main (rtx f, int nregs, FILE *file)
*** 6811,6816 ****
--- 6776,6783 ----
    free (uid_cuid);
    free (reg_eqv_table);
    free (val.path);
+   fini_cse_reg_info ();
+ 
    rtl_hooks = general_rtl_hooks;
  
    return cse_jumps_altered || recorded_label_ref;