PATCH: Remove n^2 behavior in allocate_reg_info

[Mark Mitchell <mark at codesourcery dot com>]

I was a bit surprised when profiling showed that the function getting
the most time was allocate_reg_info.  This patch drops the impact of
allocate_reg_info from 12 seconds (16% of compilation-time) to 0 zero
seconds by eliminating N^2 behavior therein.

Bootstrapped and tested on i686-pc-linux-gnu.

--
Mark Mitchell                   mark@codesourcery.com
CodeSourcery, LLC               http://www.codesourcery.com

2000-04-24  Mark Mitchell  <mark@codesourcery.com>

	* regs.h (reg_n_max): Don't declare.
	* flow.c (reg_n_max): Don't define.
	* regclass.c (renumber): Don't initialize to zero.
	(regno_allocated): Likewise.
	(reg_n_max): Define.
	(allocate_reg_info): Don't initialize unnecessarily.
	
Index: regs.h
===================================================================
RCS file: /cvs/gcc/egcs/gcc/regs.h,v
retrieving revision 1.15
diff -c -p -r1.15 regs.h
*** regs.h	2000/02/26 14:23:43	1.15
--- regs.h	2000/04/24 07:44:21
*************** typedef struct reg_info_def
*** 60,67 ****
  
  extern varray_type reg_n_info;
  
- extern unsigned int reg_n_max;
- 
  /* Indexed by n, gives number of times (REG n) is used or set.
     References within loops may be counted more times.  */
  
--- 60,65 ----
Index: flow.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/flow.c,v
retrieving revision 1.254
diff -c -p -r1.254 flow.c
*** flow.c	2000/04/15 15:20:58	1.254
--- flow.c	2000/04/24 07:44:16
*************** int max_regno;
*** 221,230 ****
  
  varray_type reg_n_info;
  
- /* Size of the reg_n_info table.  */
- 
- unsigned int reg_n_max;
- 
  /* Size of a regset for the current function,
     in (1) bytes and (2) elements.  */
  
--- 221,226 ----
Index: regclass.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/regclass.c,v
retrieving revision 1.94
diff -c -p -r1.94 regclass.c
*** regclass.c	2000/03/25 18:34:03	1.94
--- regclass.c	2000/04/24 07:44:21
*************** auto_inc_dec_reg_p (reg, mode)
*** 1983,1990 ****
  }
  #endif
  
! static short *renumber = (short *)0;
! static size_t regno_allocated = 0;
  
  /* Allocate enough space to hold NUM_REGS registers for the tables used for
     reg_scan and flow_analysis that are indexed by the register number.  If
--- 1983,1991 ----
  }
  #endif
  
! static short *renumber;
! static size_t regno_allocated;
! static unsigned int reg_n_max;
  
  /* Allocate enough space to hold NUM_REGS registers for the tables used for
     reg_scan and flow_analysis that are indexed by the register number.  If
*************** allocate_reg_info (num_regs, new_p, renu
*** 2003,2009 ****
    size_t size_renumber;
    size_t min = (new_p) ? 0 : reg_n_max;
    struct reg_info_data *reg_data;
-   struct reg_info_data *reg_next;
  
    if (num_regs > regno_allocated)
      {
--- 2004,2009 ----
*************** allocate_reg_info (num_regs, new_p, renu
*** 2056,2089 ****
      {
        /* Loop through each of the segments allocated for the actual
  	 reg_info pages, and set up the pointers, zero the pages, etc.  */
!       for (reg_data = reg_info_head; reg_data; reg_data = reg_next)
  	{
  	  size_t min_index = reg_data->min_index;
  	  size_t max_index = reg_data->max_index;
  
! 	  reg_next = reg_data->next;
! 	  if (min <= max_index)
  	    {
! 	      size_t max = max_index;
! 	      size_t local_min = min - min_index;
! 	      size_t i;
! 
! 	      if (min < min_index)
! 		local_min = 0;
! 	      if (!reg_data->used_p)	/* page just allocated with calloc */
! 		reg_data->used_p = 1;	/* no need to zero */
! 	      else
! 		bzero ((char *) &reg_data->data[local_min],
! 		       sizeof (reg_info) * (max - min_index - local_min + 1));
! 
! 	      for (i = min_index+local_min; i <= max; i++)
! 		{
! 		  VARRAY_REG (reg_n_info, i) = &reg_data->data[i-min_index];
! 		  REG_BASIC_BLOCK (i) = REG_BLOCK_UNKNOWN;
! 		  renumber[i] = -1;
! 		  reg_pref_buffer[i].prefclass = (char) NO_REGS;
! 		  reg_pref_buffer[i].altclass = (char) NO_REGS;
! 		}
  	    }
  	}
      }
--- 2056,2089 ----
      {
        /* Loop through each of the segments allocated for the actual
  	 reg_info pages, and set up the pointers, zero the pages, etc.  */
!       for (reg_data = reg_info_head; 
! 	   reg_data && reg_data->max_index >= min;
! 	   reg_data = reg_data->next)
  	{
  	  size_t min_index = reg_data->min_index;
  	  size_t max_index = reg_data->max_index;
+ 	  size_t max = MIN (max_index, num_regs);
+ 	  size_t local_min = min - min_index;
+ 	  size_t i;
+ 
+ 	  if (reg_data->min_index > num_regs)
+ 	    continue;
+ 
+ 	  if (min < min_index)
+ 	    local_min = 0;
+ 	  if (!reg_data->used_p)	/* page just allocated with calloc */
+ 	    reg_data->used_p = 1;	/* no need to zero */
+ 	  else
+ 	    bzero ((char *) &reg_data->data[local_min],
+ 		   sizeof (reg_info) * (max - min_index - local_min + 1));
  
! 	  for (i = min_index+local_min; i <= max; i++)
  	    {
! 	      VARRAY_REG (reg_n_info, i) = &reg_data->data[i-min_index];
! 	      REG_BASIC_BLOCK (i) = REG_BLOCK_UNKNOWN;
! 	      renumber[i] = -1;
! 	      reg_pref_buffer[i].prefclass = (char) NO_REGS;
! 	      reg_pref_buffer[i].altclass = (char) NO_REGS;
  	    }
  	}
      }