Re: [ira] patch for making preferred and alternative classes closer to regclass ones

Re: [ira] patch for making preferred and alternative classes closer to regclass ones

[Steven Bosscher]

xf. http://gcc.gnu.org/ml/gcc-patches/2008-05/msg01348.html

> IRA set up pseudo classes differently from regclass pass.  The
> preferred and alternative classes are used in the reload.  IRA set up
> the pseudo cover class as the preferred and NO_REGS as the alternative
> class.  After some private discussion of this difference with Jeff
> Law, it seems that setting the classes as regclass does might be
> important for some targets.

What does "might be important" mean?  Did you actually find any target
where this matters?
(It's a shame you're having this kind of design discussions in private
instead of on the list.  Openness helps build support... ;-)

To me, this patch seems like a step away from the right direction that
IRA would take with its approach to not have an alternative regclass.
If IRA starts presenting more alternatives to reload, the task of
simplifying reload (such as by e.g. selecting instructions
alternatives earlier) becomes more complex again.

I understand that simplifying reload is not a goal for IRA itself. But
this preferred/alternative regclass stuff is considered to be a design
mistake in the existing allocator by some, and it would be a shame if
IRA needs this too. So is there any real proof that this patch helps?
If not, could you please reconsider this patch?

Thanks,

Gr.
Steven

Re: [ira] patch for making preferred and alternative classes closer to regclass ones

[Vladimir Makarov]

Steven Bosscher wrote:
> xf. http://gcc.gnu.org/ml/gcc-patches/2008-05/msg01348.html
>
>   
>> IRA set up pseudo classes differently from regclass pass.  The
>> preferred and alternative classes are used in the reload.  IRA set up
>> the pseudo cover class as the preferred and NO_REGS as the alternative
>> class.  After some private discussion of this difference with Jeff
>> Law, it seems that setting the classes as regclass does might be
>> important for some targets.
>>     
>
> What does "might be important" mean?  Did you actually find any target
> where this matters?
> (It's a shame you're having this kind of design discussions in private
> instead of on the list.  Openness helps build support... ;-)
>
>   
Discussion of this issue started from simple quick Jeff's question
sent only to me.  So I don't think we should be shamed for the private
discussion.  It happened naturally without intention to keep other
people away.

What probably I did wrong was sending the patch without real
explanation of the issue.  Here my try to explain it as I understand
the problem.

Target mn10300 has data, address, and extended registers.  Moving data
between address and data registers is cheap (in comparison with
memory).  Moving to/from the extended registers is expensive.  So
natural choice for the cover classes would be

data_and_address_registers and extended_registers.

Mn10300 has insns with alternatives containing extended and address
registers.  If we use data_and_address_registers as the preferred
class (that was before the patch) and we need a reload for the
alternative, find_reloads will use the preferred class
(data_and_address_registers) because address_and_extended_registers is
not subset of the preferred class (see find_reloads).  That is wrong,
the reload should use address_registers for the reload.

There are two solution for the problem (not considering a fix in the
find_reload any change in which is potentially dangerous):

 o Use of two cover classes data_registers and address_registers
   instead one data_and_address_registers.

 o Set up the preferred class as address_registers and the alternative
   class as the alternative.

The first solution would give worse allocation because we constrain
number of registers can be used for the pseudo.  The second one is
much better.

> To me, this patch seems like a step away from the right direction that
> IRA would take with its approach to not have an alternative regclass.
> If IRA starts presenting more alternatives to reload, the task of
> simplifying reload (such as by e.g. selecting instructions
> alternatives earlier) becomes more complex again.
>
> I understand that simplifying reload is not a goal for IRA itself. But
> this preferred/alternative regclass stuff is considered to be a design
> mistake in the existing allocator by some, and it would be a shame if
> IRA needs this too. So is there any real proof that this patch helps?
> If not, could you please reconsider this patch?
>   
Different setting preferred and alternative classes affect only the
reload.  In IRA itself nothing changes: we use the same cove classes
and costs for each hard register of given cover class.

May be we reconsider this patch if we find a better solution.  May be
it happens when the work on the reload will start.  I can not say that
definitely right now.

[ira] patch for making preferred and alternative classes closer to regclass ones

[Vladimir Makarov]

[-- Attachment #1: Type: text/plain, Size: 1413 bytes --]

IRA set up pseudo classes differently from regclass pass.  The
preferred and alternative classes are used in the reload.  IRA set up
the pseudo cover class as the preferred and NO_REGS as the alternative
class.  After some private discussion of this difference with Jeff
Law, it seems that setting the classes as regclass does might be
important for some targets.

The following patch mostly sets up the preferred and alternative
pseudo classes for the reload close to what the regclass does.  Such
change practically does not change code for mainstream targets
(e.g. on x86_64 there are only small changes in the code of half
SPECINT2000 and one SPECFP2000 benchmarks which performance does
not change).

The patch was sucessfully boostrapped and tested on x86_64.

2008-05-21  Vladimir Makarov  <vmakarov@redhat.com>

	* ira.c (setup_preferred_alternate_classes): Remove.
	(setup_preferred_alternate_classes_for_new_pseudos): New.
	(setup_preferred_alternate_classes): Set memory cost for NO_REGS
	to minimal one.
	(ira): Remove setup_preferred_alternate_classes.  Call
	setup_preferred_alternate_classes_for_new_pseudos.

	* ira-costs.c (record_reg_classes): Don't decrease frequency for
	allows_mem.
	(record_operand_costs): Use memcpy instead of memmove.
	(print_costs): Use regno instead of allocno number in
	invalid_mode_change_p.
	(find_allocno_class_costs): Set up preferred and alternative
	classes.



[-- Attachment #2: classes.patch --]
[-- Type: text/x-patch, Size: 7776 bytes --]

Index: ira.c
===================================================================
--- ira.c	(revision 135713)
+++ ira.c	(working copy)
@@ -354,7 +354,7 @@ static void fix_reg_equiv_init (void);
 #ifdef ENABLE_IRA_CHECKING
 static void print_redundant_copies (void);
 #endif
-static void setup_preferred_alternate_classes (void);
+static void setup_preferred_alternate_classes_for_new_pseudos (int);
 static void expand_reg_info (int);
 static int chain_freq_compare (const void *, const void *);
 static int chain_bb_compare (const void *, const void *);
@@ -540,6 +540,9 @@ setup_class_subset_and_memory_move_costs
   enum machine_mode mode;
   HARD_REG_SET temp_hard_regset2;
 
+  for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
+    memory_move_cost[mode][NO_REGS][0]
+      = memory_move_cost[mode][NO_REGS][1] = SHRT_MAX;
   for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
     {
       if (cl != (int) NO_REGS)
@@ -547,8 +550,18 @@ setup_class_subset_and_memory_move_costs
 	  {
 	    memory_move_cost[mode][cl][0] = MEMORY_MOVE_COST (mode, cl, 0);
 	    memory_move_cost[mode][cl][1] = MEMORY_MOVE_COST (mode, cl, 1);
+	    /* Costs for NO_REGS are used in cost calculation on the
+	       1st pass when the preferred register classes are not
+	       known yet.  In this case we take the best scenario.  */
+	    if (memory_move_cost[mode][NO_REGS][0]
+		> memory_move_cost[mode][cl][0])
+	      memory_move_cost[mode][NO_REGS][0]
+		= memory_move_cost[mode][cl][0];
+	    if (memory_move_cost[mode][NO_REGS][1]
+		> memory_move_cost[mode][cl][1])
+	      memory_move_cost[mode][NO_REGS][1]
+		= memory_move_cost[mode][cl][1];
 	  }
-
       for (cl2 = (int) N_REG_CLASSES - 1; cl2 >= 0; cl2--)
 	{
 	  COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
@@ -1633,21 +1646,25 @@ print_redundant_copies (void)
 }
 #endif
 
-/* Setup preferred and alternative classes for pseudo-registers for
-   other passes.  */
+/* Setup preferred and alternative classes for new pseudo-registers
+   created by IRA starting with START.  */
 static void
-setup_preferred_alternate_classes (void)
+setup_preferred_alternate_classes_for_new_pseudos (int start)
 {
-  enum reg_class cover_class;
-  allocno_t a;
-  allocno_iterator ai;
+  int i, old_regno;
+  int max_regno = max_reg_num ();
 
-  FOR_EACH_ALLOCNO (a, ai)
+  for (i = start; i < max_regno; i++)
     {
-      cover_class = ALLOCNO_COVER_CLASS (a);
-      if (cover_class == NO_REGS)
-	cover_class = GENERAL_REGS;
-      setup_reg_classes (ALLOCNO_REGNO (a), cover_class, NO_REGS);
+      old_regno = ORIGINAL_REGNO (regno_reg_rtx[i]);
+      ira_assert (i != old_regno); 
+      setup_reg_classes (i, reg_preferred_class (old_regno),
+			 reg_alternate_class (old_regno));
+      if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
+	fprintf (ira_dump_file,
+		 "    New r%d: setting preferred %s, alternative %s\n",
+		 i, reg_class_names[reg_preferred_class (old_regno)],
+		 reg_class_names[reg_alternate_class (old_regno)]);
     }
 }
 
@@ -1861,6 +1878,8 @@ ira (FILE *f)
       else
 	{
 	  expand_reg_info (allocated_reg_info_size);
+	  setup_preferred_alternate_classes_for_new_pseudos
+	    (allocated_reg_info_size);
 	  allocated_reg_info_size = max_regno;
 	  
 	  if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
@@ -1893,8 +1912,6 @@ ira (FILE *f)
     check_allocation ();
 #endif
       
-  setup_preferred_alternate_classes ();
-      
   delete_trivially_dead_insns (get_insns (), max_reg_num ());
   max_regno = max_reg_num ();
   
Index: ira-costs.c
===================================================================
--- ira-costs.c	(revision 135713)
+++ ira-costs.c	(working copy)
@@ -42,8 +42,8 @@ along with GCC; see the file COPYING3.  
    works on the allocno basis.  */
 
 #ifdef FORBIDDEN_INC_DEC_CLASSES
-/* Indexed by n, is nonzero if (REG n) is used in an auto-inc or
-   auto-dec context.  */
+/* Indexed by n, is nonzero if allocno with number N is used in an
+   auto-inc or auto-dec context.  */
 static char *in_inc_dec;
 #endif
 
@@ -319,11 +319,9 @@ record_reg_classes (int n_alts, int n_op
 		  pp->mem_cost
 		    = ((recog_data.operand_type[i] != OP_IN
 			? memory_move_cost[mode][classes[i]][0] : 0)
-		       * frequency
 		       + (recog_data.operand_type[i] != OP_OUT
 			  ? memory_move_cost[mode][classes[i]][1] : 0)
-		       * frequency - allows_mem[i] * frequency / 2);
-
+		       - allows_mem[i]) * frequency;
 		  /* If we have assigned a class to this allocno in our
 		     first pass, add a cost to this alternative
 		     corresponding to what we would add if this allocno
@@ -563,12 +561,10 @@ record_reg_classes (int n_alts, int n_op
 		     insn to load it.  */
 		  pp->mem_cost
 		    = ((recog_data.operand_type[i] != OP_IN
-		        ? memory_move_cost[mode][classes[i]][0]
-			: 0) * frequency
+			? memory_move_cost[mode][classes[i]][0] : 0)
 		       + (recog_data.operand_type[i] != OP_OUT
-			  ? memory_move_cost[mode][classes[i]][1]
-			  : 0) * frequency - allows_mem[i] * frequency / 2);
-
+			  ? memory_move_cost[mode][classes[i]][1] : 0)
+		       - allows_mem[i]) * frequency;
 		  /* If we have assigned a class to this allocno in our
 		     first pass, add a cost to this alternative
 		     corresponding to what we would add if this allocno
@@ -938,7 +934,7 @@ record_operand_costs (rtx insn, struct c
      commutative.  */
   for (i = 0; i < recog_data.n_operands; i++)
     {
-      memmove (op_costs[i], init_cost, struct_costs_size);
+      memcpy (op_costs[i], init_cost, struct_costs_size);
 
       if (GET_CODE (recog_data.operand[i]) == SUBREG)
 	recog_data.operand[i] = SUBREG_REG (recog_data.operand[i]);
@@ -1072,7 +1068,7 @@ print_costs (FILE *f)
 	      && (! in_inc_dec[i] || ! forbidden_inc_dec_class[class])
 #endif
 #ifdef CANNOT_CHANGE_MODE_CLASS
-	      && ! invalid_mode_change_p (i, (enum reg_class) class,
+	      && ! invalid_mode_change_p (regno, (enum reg_class) class,
 					  PSEUDO_REGNO_MODE (regno))
 #endif
 	      )
@@ -1179,7 +1175,7 @@ find_allocno_class_costs (void)
 	  int class, a_num, father_a_num;
 	  loop_tree_node_t father;
 	  int best_cost;
-	  enum reg_class best, common_class;
+	  enum reg_class best, alt_class, common_class;
 #ifdef FORBIDDEN_INC_DEC_CLASSES
 	  int inc_dec_p = FALSE;
 #endif
@@ -1219,6 +1215,7 @@ find_allocno_class_costs (void)
 	    }
 	  best_cost = (1 << (HOST_BITS_PER_INT - 2)) - 1;
 	  best = ALL_REGS;
+	  alt_class = NO_REGS;
 	  /* Find best common class for all allocnos with the same
 	     regno.  */
 	  for (k = 0; k < cost_classes_num; k++)
@@ -1235,14 +1232,31 @@ find_allocno_class_costs (void)
 					    PSEUDO_REGNO_MODE (i))
 #endif
 		  )
-		;
-	      else if (temp_costs->cost[k] < best_cost)
+		continue;
+	      if (temp_costs->cost[k] < best_cost)
 		{
 		  best_cost = temp_costs->cost[k];
 		  best = (enum reg_class) class;
 		}
 	      else if (temp_costs->cost[k] == best_cost)
 		best = reg_class_union[best][class];
+	      if (pass == flag_expensive_optimizations
+		  && temp_costs->cost[k] < temp_costs->mem_cost
+		  && (reg_class_size[reg_class_subunion[alt_class][class]]
+		      > reg_class_size[alt_class]))
+		alt_class = reg_class_subunion[alt_class][class];
+	    }
+	  if (pass == flag_expensive_optimizations)
+	    {
+	      if (best_cost > temp_costs->mem_cost)
+		best = alt_class = NO_REGS;
+	      else if (best == alt_class)
+		alt_class = NO_REGS;
+	      setup_reg_classes (i, best, alt_class);
+	      if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
+		fprintf (ira_dump_file,
+			 "    r%d: preferred %s, alternative %s\n",
+			 i, reg_class_names[best], reg_class_names[alt_class]);
 	    }
 	  if (best_cost > temp_costs->mem_cost)
 	    common_class = NO_REGS;