[patch] cse.c: Speed up cse_reg_info maintenance.

[Kazu Hirata]

Hi Bernd.

> Expand the comment with one or two more sentences describing how it's 
> partitioned.

OK.  Here is the final patch that I committed.

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 15:42:56 -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,353 ----
    unsigned int subreg_ticked;
  };
  
! /* We maintain a linked list of cse_reg_info instances, which is
!    partitioned into two pieces.  The first part, pointed to by
!    cse_reg_info_list, is a list of those entries that are in use.  The
!    second part, pointed to by cse_reg_info_list_free, is a list of
!    those entries that are not in use.
  
!    We combine these two parts into one linked list for efficiency.
!    Specifically, when we take an element from the second part and want
!    to move it to the first part, all we have to do is move the pointer
!    cse_reg_info_list_free to the next element.  Also, if we wish to
!    move all elements into the second part, we just have to move the
!    pointer to the first element of the list.  */
! 
! /* 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;
--- 884,900 ----
    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
--- 906,911 ----
*************** 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);
--- 930,937 ----
  
    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);