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] cse.c: Speed up cse_reg_info maintenance.


Hi,

Attached is a patch to speed up cse_reg_info maintenance.

Instances of cse_reg_info are maintained using a free list and a used
list.  The free list is a list of cse_reg_info instances that have
been allocated but are currently unused.  The used list is a list of
currently used cse_reg_info instances.

CSE has an interesting property that it keeps allocating an instance
of cse_reg_info and then "free"s all the instances at once.  That is,
it never "frees" a single instance while keeping others.  By "freeing"
an instance, I of course mean adding that instance to the free list.

We can actually take advantage of this property and get away with
maintaining only one linked list that looks like so

cse_reg_info_list
  |
  v
 cri -> cri -> cri -> cri -> cri -> cri -> cri -> csi -> NULL
                       ^
                       |
   cse_reg_info_list_free

where cri is an instance of cse_reg_info.  That is, the linked list,
cse_reg_info_list, would contain all cse_reg_info that have been
allocated so far.  Furthermore, the linked list would be partitioned
into two pieces.  The first piece would contain used nodes while the
second piece, pointed to by cse_reg_info_list_free, would contain free
nodes.

The patch implements the above idea.

Here is the timing in seconds for five runs of ./cc1 -quiet -O2 -o
/dev/null.

             original patched    diff
c-common.i     18.593  18.548 -0.242%
combine.i      17.546  17.518 -0.159%
fold-const.i   38.919  38.565 -0.654%
reload.i       13.607  13.587 -0.146%

Let me note that the free list is very effective in maintaining
instances of cse_reg_info.  While compiling cc1-i files, new
insntances of cse_reg_info are allocated 20,000 times while they are
reused 20,000,000 times.

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

Kazu Hirata

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

	* cse.c (cse_reg_info_free_list, cse_reg_info_used_list,
	cse_reg_info_used_list_end): Remove.
	(cse_reg_info_list, cse_reg_info_list_free): New.
	(get_cse_reg_info): When allocating an instance of
	cse_reg_info, add it to the beginning of the cse_reg_info_list
	list.  Remove code to maintain cse_reg_info_used_list.
	(new_basic_block): Reset the free list to the beginning of
	cse_reg_info_list.

Index: cse.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cse.c,v
retrieving revision 1.333
diff -c -d -p -r1.333 cse.c
*** cse.c	27 Jan 2005 23:00:19 -0000	1.333
--- cse.c	28 Jan 2005 03:55:30 -0000
*************** struct cse_reg_info
*** 329,340 ****
    unsigned int subreg_ticked;
  };
  
! /* A free list of cse_reg_info entries.  */
! static struct cse_reg_info *cse_reg_info_free_list;
  
! /* A used list of cse_reg_info entries.  */
! static struct cse_reg_info *cse_reg_info_used_list;
! static struct cse_reg_info *cse_reg_info_used_list_end;
  
  /* A mapping from registers to cse_reg_info data structures.  */
  #define REGHASH_SHIFT	7
--- 329,340 ----
    unsigned int subreg_ticked;
  };
  
! /* A linked list of cse_reg_info entries that have been allocated so
!    far.  */
! static struct cse_reg_info *cse_reg_info_list;
  
! /* A pointer to the first unused entry in the above linked list.  */
! static struct cse_reg_info *cse_reg_info_list_free;
  
  /* A mapping from registers to cse_reg_info data structures.  */
  #define REGHASH_SHIFT	7
*************** get_cse_reg_info (unsigned int regno)
*** 871,883 ****
    if (p == NULL)
      {
        /* Get a new cse_reg_info structure.  */
!       if (cse_reg_info_free_list)
  	{
! 	  p = cse_reg_info_free_list;
! 	  cse_reg_info_free_list = p->next;
  	}
        else
! 	p = xmalloc (sizeof (struct cse_reg_info));
  
        /* Insert into hash table.  */
        p->hash_next = *hash_head;
--- 871,887 ----
    if (p == NULL)
      {
        /* Get a new cse_reg_info structure.  */
!       if (cse_reg_info_list_free)
  	{
! 	  p = cse_reg_info_list_free;
! 	  cse_reg_info_list_free = p->next;
  	}
        else
! 	{
! 	  p = xmalloc (sizeof (struct cse_reg_info));
! 	  p->next = cse_reg_info_list;
! 	  cse_reg_info_list = p;
! 	}
  
        /* Insert into hash table.  */
        p->hash_next = *hash_head;
*************** get_cse_reg_info (unsigned int regno)
*** 889,898 ****
        p->subreg_ticked = -1;
        p->reg_qty = -regno - 1;
        p->regno = regno;
-       p->next = cse_reg_info_used_list;
-       cse_reg_info_used_list = p;
-       if (!cse_reg_info_used_list_end)
- 	cse_reg_info_used_list_end = p;
      }
  
    /* Cache this lookup; we tend to be looking up information about the
--- 893,898 ----
*************** new_basic_block (void)
*** 917,928 ****
  
    memset (reg_hash, 0, sizeof reg_hash);
  
!   if (cse_reg_info_used_list)
!     {
!       cse_reg_info_used_list_end->next = cse_reg_info_free_list;
!       cse_reg_info_free_list = cse_reg_info_used_list;
!       cse_reg_info_used_list = cse_reg_info_used_list_end = 0;
!     }
    cached_cse_reg_info = 0;
  
    CLEAR_HARD_REG_SET (hard_regs_in_table);
--- 917,924 ----
  
    memset (reg_hash, 0, sizeof reg_hash);
  
!   cse_reg_info_list_free = cse_reg_info_list;
! 
    cached_cse_reg_info = 0;
  
    CLEAR_HARD_REG_SET (hard_regs_in_table);


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