Patch to delete scratch allocation in local-alloc

[Bernd Schmidt <crux at Pool dot Informatik dot RWTH-Aachen dot DE>]

Currently, scratches can be allocated in two ways: local-alloc has code to
do it, and reload has code to do it.  Apart from the fact that it is wasteful
to duplicate code like this, there are reasons why one would want to ditch
the code in local-alloc.

The code in reload always works, and allocates exactly the scratch registers
which are necessary.  The code in local-alloc only guesses; it can't know
which alternative is going to be selected by reload.  Worse, global can't
override the choices of local-alloc when they turn out to be wrong, which
may lead to suboptimal register allocation.
This patch deletes all the code that is necessary to allocate scratches in
local-alloc.  Currently, it might produce worse code for some cases, since
if reload has to spill a register to allocate a scratch, this can be rather
costly.  On the other hand, retry_global_alloc usually should be able to
handle the resulting spills, and once the local spill code is integrated,
spill costs are going to be much less anyway.
I have made some tests, and in the only case which I could find where the
produced code was different, the code generated by the compiler with this
patch was more efficient.  That indicates that the fact that global can't
override local-alloc's choices for scratch registers is in fact a real
problem, and the patch below may even be an optimization.

Bernd

	* global.c (global_alloc): Delete code to manage the scratch_list.
	* local-alloc.c (qty_scratch_rtx): Delete.
	(scratch_block): Delete.
	(scratch_list): Delete.
	(scratch_list_length): Delete.
	(scratch_index): Delete.
	(alloc_qty_for_scratch): Delete.
	(local-alloc): Update initialization of max_qty.
	Delete code to manage the scratch list.
	Delete code to allocate/initialize qty_scratch_rtx.
	(block_alloc): Don't allocate quantities for scratches.
	Delete code to manage the scratch list.
	* regs.h (scratch_list): Delete declaration.
	(scratch_block): Delete declaration.
	(scratch_list_length): Delete declaration.
	* reload1.c (reload): Delete code to manage the scratch list.
	(spill_hard_reg): Likewise.
	(mark_scratch_live): Delete.

Index: global.c
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/global.c,v
retrieving revision 1.15
diff -u -p -r1.15 global.c
--- global.c	1998/09/30 18:09:46	1.15
+++ global.c	1998/10/01 12:49:42
@@ -450,18 +450,6 @@ global_alloc (file)
   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
     if (regs_ever_live[i])
       local_reg_n_refs[i] = 0;
-
-  /* Likewise for regs used in a SCRATCH.  */
-  for (i = 0; i < scratch_list_length; i++)
-    if (scratch_list[i])
-      {
-	int regno = REGNO (scratch_list[i]);
-	int lim = regno + HARD_REGNO_NREGS (regno, GET_MODE (scratch_list[i]));
-	int j;
-
-	for (j = regno; j < lim; j++)
-	  local_reg_n_refs[j] = 0;
-      }
 	
   /* Allocate the space for the conflict and preference tables and
      initialize them.  */
Index: local-alloc.c
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/local-alloc.c,v
retrieving revision 1.20
diff -u -p -r1.20 local-alloc.c
--- local-alloc.c	1998/09/30 18:09:45	1.20
+++ local-alloc.c	1998/10/01 12:49:43
@@ -156,19 +156,14 @@ static int *qty_n_calls_crossed;
 
 static enum reg_class *qty_alternate_class;
 
-/* Element Q is the SCRATCH expression for which this quantity is being
-   allocated or 0 if this quantity is allocating registers.  */
-
-static rtx *qty_scratch_rtx;
-
 /* Element Q is nonzero if this quantity has been used in a SUBREG
    that changes its size.  */
 
 static char *qty_changes_size;
 
 /* Element Q is the register number of one pseudo register whose
-   reg_qty value is Q, or -1 is this quantity is for a SCRATCH.  This
-   register should be the head of the chain maintained in reg_next_in_qty.  */
+   reg_qty value is Q.  This register should be the head of the chain
+   maintained in reg_next_in_qty.  */
 
 static int *qty_first_reg;
 
@@ -227,11 +222,6 @@ static HARD_REG_SET regs_live;
 
 static HARD_REG_SET *regs_live_at;
 
-int *scratch_block;
-rtx *scratch_list;
-int scratch_list_length;
-static int scratch_index;
-
 /* Communicate local vars `insn_number' and `insn'
    from `block_alloc' to `reg_is_set', `wipe_dead_reg', and `alloc_qty'.  */
 static int this_insn_number;
@@ -245,7 +235,6 @@ static rtx this_insn;
 static rtx *reg_equiv_replacement;
 
 static void alloc_qty		PROTO((int, enum machine_mode, int, int));
-static void alloc_qty_for_scratch PROTO((rtx, int, rtx, int, int));
 static void validate_equiv_mem_from_store PROTO((rtx, rtx));
 static int validate_equiv_mem	PROTO((rtx, rtx, rtx));
 static int contains_replace_regs PROTO((rtx, char *));
@@ -297,96 +286,6 @@ alloc_qty (regno, mode, size, birth)
   qty_changes_size[qty] = REG_CHANGES_SIZE (regno);
 }
 
-/* Similar to `alloc_qty', but allocates a quantity for a SCRATCH rtx
-   used as operand N in INSN.  We assume here that the SCRATCH is used in
-   a CLOBBER.  */
-
-static void
-alloc_qty_for_scratch (scratch, n, insn, insn_code_num, insn_number)
-     rtx scratch;
-     int n;
-     rtx insn;
-     int insn_code_num, insn_number;
-{
-  register int qty;
-  enum reg_class class;
-  char *p, c;
-  int i;
-
-#ifdef REGISTER_CONSTRAINTS
-  /* If we haven't yet computed which alternative will be used, do so now.
-     Then set P to the constraints for that alternative.  */
-  if (which_alternative == -1)
-    if (! constrain_operands (insn_code_num, 0))
-      return;
-
-  for (p = insn_operand_constraint[insn_code_num][n], i = 0;
-       *p && i < which_alternative; p++)
-    if (*p == ',')
-      i++;
-
-  /* Compute the class required for this SCRATCH.  If we don't need a
-     register, the class will remain NO_REGS.  If we guessed the alternative
-     number incorrectly, reload will fix things up for us.  */
-
-  class = NO_REGS;
-  while ((c = *p++) != '\0' && c != ',')
-    switch (c)
-      {
-      case '=':  case '+':  case '?':
-      case '#':  case '&':  case '!':
-      case '*':  case '%':  
-      case '0':  case '1':  case '2':  case '3':  case '4':
-      case 'm':  case '<':  case '>':  case 'V':  case 'o':
-      case 'E':  case 'F':  case 'G':  case 'H':
-      case 's':  case 'i':  case 'n':
-      case 'I':  case 'J':  case 'K':  case 'L':
-      case 'M':  case 'N':  case 'O':  case 'P':
-#ifdef EXTRA_CONSTRAINT
-      case 'Q':  case 'R':  case 'S':  case 'T':  case 'U':
-#endif
-      case 'p':
-	/* These don't say anything we care about.  */
-	break;
-
-      case 'X':
-	/* We don't need to allocate this SCRATCH.  */
-	return;
-
-      case 'g': case 'r':
-	class = reg_class_subunion[(int) class][(int) GENERAL_REGS];
-	break;
-
-      default:
-	class
-	  = reg_class_subunion[(int) class][(int) REG_CLASS_FROM_LETTER (c)];
-	break;
-      }
-
-  if (class == NO_REGS)
-    return;
-
-#else /* REGISTER_CONSTRAINTS */
-
-  class = GENERAL_REGS;
-#endif
-  
-
-  qty = next_qty++;
-
-  qty_first_reg[qty] = -1;
-  qty_scratch_rtx[qty] = scratch;
-  qty_size[qty] = GET_MODE_SIZE (GET_MODE (scratch));
-  qty_mode[qty] = GET_MODE (scratch);
-  qty_birth[qty] = 2 * insn_number - 1;
-  qty_death[qty] = 2 * insn_number + 1;
-  qty_n_calls_crossed[qty] = 0;
-  qty_min_class[qty] = class;
-  qty_alternate_class[qty] = NO_REGS;
-  qty_n_refs[qty] = 1;
-  qty_changes_size[qty] = 0;
-}
-
 /* Main entry point of this file.  */
 
 void
@@ -407,26 +306,13 @@ local_alloc ()
   update_equiv_regs ();
 
   /* This sets the maximum number of quantities we can have.  Quantity
-     numbers start at zero and we can have one for each pseudo plus the
-     number of SCRATCHes in the largest block, in the worst case.  */
-  max_qty = (max_regno - FIRST_PSEUDO_REGISTER) + max_scratch;
+     numbers start at zero and we can have one for each pseudo.  */
+  max_qty = (max_regno - FIRST_PSEUDO_REGISTER);
 
   /* Allocate vectors of temporary data.
      See the declarations of these variables, above,
      for what they mean.  */
 
-  /* There can be up to MAX_SCRATCH * N_BASIC_BLOCKS SCRATCHes to allocate.
-     Instead of allocating this much memory from now until the end of
-     reload, only allocate space for MAX_QTY SCRATCHes.  If there are more
-     reload will allocate them.  */
-
-  scratch_list_length = max_qty;
-  scratch_list = (rtx *) xmalloc (scratch_list_length * sizeof (rtx));
-  bzero ((char *) scratch_list, scratch_list_length * sizeof (rtx));
-  scratch_block = (int *) xmalloc (scratch_list_length * sizeof (int));
-  bzero ((char *) scratch_block, scratch_list_length * sizeof (int));
-  scratch_index = 0;
-
   qty_phys_reg = (short *) alloca (max_qty * sizeof (short));
   qty_phys_copy_sugg
     = (HARD_REG_SET *) alloca (max_qty * sizeof (HARD_REG_SET));
@@ -435,7 +321,6 @@ local_alloc ()
   qty_phys_num_sugg = (short *) alloca (max_qty * sizeof (short));
   qty_birth = (int *) alloca (max_qty * sizeof (int));
   qty_death = (int *) alloca (max_qty * sizeof (int));
-  qty_scratch_rtx = (rtx *) alloca (max_qty * sizeof (rtx));
   qty_first_reg = (int *) alloca (max_qty * sizeof (int));
   qty_size = (int *) alloca (max_qty * sizeof (int));
   qty_mode
@@ -493,7 +378,6 @@ local_alloc ()
 	{
 	  for (i = 0; i < next_qty; i++)
 	    {
-	      qty_scratch_rtx[i] = 0;
 	      CLEAR_HARD_REG_SET (qty_phys_copy_sugg[i]);
 	      qty_phys_num_copy_sugg[i] = 0;
 	      CLEAR_HARD_REG_SET (qty_phys_sugg[i]);
@@ -505,7 +389,6 @@ local_alloc ()
 #define CLEAR(vector)  \
 	  bzero ((char *) (vector), (sizeof (*(vector))) * next_qty);
 
-	  CLEAR (qty_scratch_rtx);
 	  CLEAR (qty_phys_copy_sugg);
 	  CLEAR (qty_phys_num_copy_sugg);
 	  CLEAR (qty_phys_sugg);
@@ -1029,9 +912,6 @@ block_alloc (b)
   int max_uid = get_max_uid ();
   int *qty_order;
   int no_conflict_combined_regno = -1;
-  /* Counter to prevent allocating more SCRATCHes than can be stored
-     in SCRATCH_LIST.  */
-  int scratches_allocated = scratch_index;
 
   /* Count the instructions in the basic block.  */
 
@@ -1285,15 +1165,6 @@ block_alloc (b)
 		&& GET_CODE (XEXP (link, 0)) == REG)
 	      wipe_dead_reg (XEXP (link, 0), 1);
 
-	  /* Allocate quantities for any SCRATCH operands of this insn.  */
-
-	  if (insn_code_number >= 0)
-	    for (i = 0; i < insn_n_operands[insn_code_number]; i++)
-	      if (GET_CODE (recog_operand[i]) == SCRATCH
-		  && scratches_allocated++ < scratch_list_length)
-		alloc_qty_for_scratch (recog_operand[i], i, insn,
-				       insn_code_number, insn_number);
-
 	  /* If this is an insn that has a REG_RETVAL note pointing at a 
 	     CLOBBER insn, we have reached the end of a REG_NO_CONFLICT
 	     block, so clear any register number that combined within it.  */
@@ -1492,16 +1363,6 @@ block_alloc (b)
       {
 	for (i = qty_first_reg[q]; i >= 0; i = reg_next_in_qty[i])
 	  reg_renumber[i] = qty_phys_reg[q] + reg_offset[i];
-	if (qty_scratch_rtx[q])
-	  {
-	    if (GET_CODE (qty_scratch_rtx[q]) == REG)
-	      abort ();
-	    qty_scratch_rtx[q] = gen_rtx_REG (GET_MODE (qty_scratch_rtx[q]),
-					      qty_phys_reg[q]);
-	    scratch_block[scratch_index] = b;
-	    scratch_list[scratch_index++] = qty_scratch_rtx[q];
-
-	  }
       }
 }
 
Index: regs.h
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/regs.h,v
retrieving revision 1.6
diff -u -p -r1.6 regs.h
--- regs.h	1998/09/30 18:09:44	1.6
+++ regs.h	1998/10/01 12:49:46
@@ -223,14 +223,5 @@ extern int caller_save_needed;
 #define HARD_REGNO_CALL_PART_CLOBBERED(REGNO, MODE) 0
 #endif
 
-/* Allocated in local_alloc.  */
-
-/* A list of SCRATCH rtl allocated by local-alloc.  */
-extern rtx *scratch_list;
-/* The basic block in which each SCRATCH is used.  */
-extern int *scratch_block;
-/* The length of the arrays pointed to by scratch_block and scratch_list.  */
-extern int scratch_list_length;
-
 /* Allocate reg_n_info tables */
 extern void allocate_reg_info PROTO((size_t, int, int));
Index: reload1.c
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/reload1.c,v
retrieving revision 1.68
diff -u -p -r1.68 reload1.c
--- reload1.c	1998/09/28 10:33:41	1.68
+++ reload1.c	1998/10/01 12:49:53
@@ -364,7 +364,6 @@ static int new_spill_reg		PROTO((int, in
 					       FILE *));
 static void delete_dead_insn		PROTO((rtx));
 static void alter_reg  			PROTO((int, int));
-static void mark_scratch_live		PROTO((rtx));
 static void set_label_offsets		PROTO((rtx, rtx, int));
 static int eliminate_regs_in_insn	PROTO((rtx, int));
 static void mark_not_eliminable		PROTO((rtx, rtx));
@@ -645,10 +644,6 @@ reload (first, global, dumpfile)
 	  regs_ever_live[i] = 1;
       }
 
-  for (i = 0; i < scratch_list_length; i++)
-    if (scratch_list[i])
-      mark_scratch_live (scratch_list[i]);
-
   /* Make sure that the last insn in the chain
      is not something that needs reloading.  */
   emit_note (NULL_PTR, NOTE_INSN_DELETED);
@@ -1388,13 +1383,6 @@ reload (first, global, dumpfile)
   if (real_at_ptr)
     free (real_at_ptr);
 
-  if (scratch_list)
-    free (scratch_list);
-  scratch_list = 0;
-  if (scratch_block)
-    free (scratch_block);
-  scratch_block = 0;
-
   free (reg_equiv_constant);
   free (reg_equiv_memory_loc);
   free (reg_equiv_mem);
@@ -2687,20 +2675,6 @@ mark_home_live (regno)
   while (i < lim)
     regs_ever_live[i++] = 1;
 }
-
-/* Mark the registers used in SCRATCH as being live.  */
-
-static void
-mark_scratch_live (scratch)
-     rtx scratch;
-{
-  register int i;
-  int regno = REGNO (scratch);
-  int lim = regno + HARD_REGNO_NREGS (regno, GET_MODE (scratch));
-
-  for (i = regno; i < lim; i++)
-    regs_ever_live[i] = 1;
-}
 
 /* This function handles the tracking of elimination offsets around branches.
 
@@ -3824,33 +3798,6 @@ spill_hard_reg (regno, global, dumpfile,
 		       i, reg_renumber[i]);
 	  }
       }
-  for (i = 0; i < scratch_list_length; i++)
-    {
-     if (scratch_list[i] 
-          && regno >= REGNO (scratch_list[i]) 
-          && regno <  REGNO (scratch_list[i]) 
-                      + HARD_REGNO_NREGS (REGNO (scratch_list[i]),
-                                          GET_MODE (scratch_list[i])))
-	{
-	  if (! cant_eliminate && basic_block_needs[0]
-	      && ! basic_block_needs[(int) class][scratch_block[i]])
-	    {
-	      enum reg_class *p;
-
-	      for (p = reg_class_superclasses[(int) class];
-		   *p != LIM_REG_CLASSES; p++)
-		if (basic_block_needs[(int) *p][scratch_block[i]] > 0)
-		  break;
-
-	      if (*p == LIM_REG_CLASSES)
-		continue;
-	    }
-	  PUT_CODE (scratch_list[i], SCRATCH);
-	  scratch_list[i] = 0;
-	  something_changed = 1;
-	  continue;
-	}
-    }
 
   return something_changed;
 }