Reduce startup cost of compiler (patch 2)

Reduce startup cost of compiler (patch 2)

[Jan Hubicka]

Hi,
this patch reduces cost of move_cost tables.  THose are the largest
tables used by regclass and are allocated as num_modes*num_classes*num_classes
array, while just modes that might appear in pseudos really matters.

The patch turns the tables into arrays of pointers to arrays so
only those modes needed are allocated (about 2K each) and the tables
are filled in lazily, so for normal units all those weird vector modes don't
need to be considered.  Additionally the code is now watching if
the table match last table and avoids computation then saving some extra
memory for vector modes that are largely identical.

I've also changed move cost type to short to save some extra memory, the values
are used in very internal loop of regclass that I unswitched. The patch is neutral
for combine.c (it however brings record_reg_classes down in schedule) and makes
noticeable difference to startup time (see profiles from previous patch)

Bootstrapped/regtested i686-linux?

Honza

	* regclass.c (move_table): New type.
	(move_cost, may_move_in_cost, may_move_out_cost): Use it.
	(init_move_cost): Break out from ...
	(init_reg_sets_1): ... here; simplify computation of
	have_regs-of_mode and contains_reg_of_mode.
	(record_reg_classes): Unswitch internal loops.
	(copy_cost): Trigger lazy initialization of move cost
	(record_address_regs): Likewise.
Index: regclass.c
===================================================================
*** regclass.c	(revision 126800)
--- regclass.c	(working copy)
*************** bool have_regs_of_mode [MAX_MACHINE_MODE
*** 212,233 ****
  
  /* 1 if class does contain register of given mode.  */
  
! static char contains_reg_of_mode [N_REG_CLASSES] [MAX_MACHINE_MODE];
  
  /* Maximum cost of moving from a register in one class to a register in
     another class.  Based on REGISTER_MOVE_COST.  */
  
! static int move_cost[MAX_MACHINE_MODE][N_REG_CLASSES][N_REG_CLASSES];
  
  /* Similar, but here we don't have to move if the first index is a subset
     of the second so in that case the cost is zero.  */
  
! static int may_move_in_cost[MAX_MACHINE_MODE][N_REG_CLASSES][N_REG_CLASSES];
  
  /* Similar, but here we don't have to move if the first index is a superset
     of the second so in that case the cost is zero.  */
  
! static int may_move_out_cost[MAX_MACHINE_MODE][N_REG_CLASSES][N_REG_CLASSES];
  
  #ifdef FORBIDDEN_INC_DEC_CLASSES
  
--- 212,235 ----
  
  /* 1 if class does contain register of given mode.  */
  
! static char contains_reg_of_mode [N_REG_CLASSES] [MAX_MACHINE_MODE];
! 
! typedef unsigned short move_table[N_REG_CLASSES];
  
  /* Maximum cost of moving from a register in one class to a register in
     another class.  Based on REGISTER_MOVE_COST.  */
  
! static move_table *move_cost[MAX_MACHINE_MODE];
  
  /* Similar, but here we don't have to move if the first index is a subset
     of the second so in that case the cost is zero.  */
  
! static move_table *may_move_in_cost[MAX_MACHINE_MODE];
  
  /* Similar, but here we don't have to move if the first index is a superset
     of the second so in that case the cost is zero.  */
  
! static move_table *may_move_out_cost[MAX_MACHINE_MODE];
  
  #ifdef FORBIDDEN_INC_DEC_CLASSES
  
*************** init_reg_sets (void)
*** 312,317 ****
--- 314,400 ----
  #endif
  }
  
+ /* Initialize may_move_cost and friends for mode M.  */
+ 
+ static void
+ init_move_cost (enum machine_mode m)
+ {
+   static unsigned short last_move_cost[N_REG_CLASSES][N_REG_CLASSES];
+   bool all_match = true;
+   unsigned int i, j;
+ 
+   gcc_assert (have_regs_of_mode[m]);
+   for (i = 0; i < N_REG_CLASSES; i++)
+     if (contains_reg_of_mode[i][m])
+       for (j = 0; j < N_REG_CLASSES; j++)
+ 	{
+ 	  int cost;
+ 	  if (!contains_reg_of_mode[j][m])
+ 	    cost = 65535;
+ 	  else
+ 	    {
+ 	      cost = REGISTER_MOVE_COST (m, i, j);
+ 	      gcc_assert (cost < 65535);
+ 	    }
+ 	  all_match &= (last_move_cost[i][j] == cost);
+ 	  last_move_cost[i][j] = cost;
+ 	}
+   move_cost[m] = (move_table *)xmalloc (sizeof (move_table)
+ 					* N_REG_CLASSES);
+   may_move_in_cost[m] = (move_table *)xmalloc (sizeof (move_table)
+ 					       * N_REG_CLASSES);
+   may_move_out_cost[m] = (move_table *)xmalloc (sizeof (move_table)
+ 					        * N_REG_CLASSES);
+   for (i = 0; i < N_REG_CLASSES; i++)
+     if (contains_reg_of_mode[i][m])
+       for (j = 0; j < N_REG_CLASSES; j++)
+ 	{
+ 	  int cost;
+ 	  enum reg_class *p1, *p2;
+ 
+ 	  if (last_move_cost[i][j] == 65535)
+ 	    {
+ 	      move_cost[m][i][j] = 65535;
+ 	      may_move_in_cost[m][i][j] = 65535;
+ 	      may_move_out_cost[m][i][j] = 65535;
+ 	    }
+ 	  else
+ 	    {
+ 	      cost = last_move_cost[i][j];
+ 
+ 	      for (p2 = &reg_class_subclasses[j][0];
+ 		   *p2 != LIM_REG_CLASSES; p2++)
+ 		if (*p2 != i && contains_reg_of_mode[*p2][m])
+ 		  cost = MAX (cost, move_cost[m][i][*p2]);
+ 
+ 	      for (p1 = &reg_class_subclasses[i][0];
+ 		   *p1 != LIM_REG_CLASSES; p1++)
+ 		if (*p1 != j && contains_reg_of_mode[*p1][m])
+ 		  cost = MAX (cost, move_cost[m][*p1][j]);
+ 
+ 	      gcc_assert (cost <= 65535);
+ 	      move_cost[m][i][j] = cost;
+ 
+ 	      if (reg_class_subset_p (i, j))
+ 		may_move_in_cost[m][i][j] = 0;
+ 	      else
+ 		may_move_in_cost[m][i][j] = cost;
+ 
+ 	      if (reg_class_subset_p (j, i))
+ 		may_move_out_cost[m][i][j] = 0;
+ 	      else
+ 		may_move_out_cost[m][i][j] = cost;
+ 	    }
+ 	}
+     else
+       for (j = 0; j < N_REG_CLASSES; j++)
+ 	{
+ 	  move_cost[m][i][j] = 65535;
+ 	  may_move_in_cost[m][i][j] = 65535;
+ 	  may_move_out_cost[m][i][j] = 65535;
+ 	}
+ }
+ 
  /* After switches have been processed, which perhaps alter
     `fixed_regs' and `call_used_regs', convert them to HARD_REG_SETs.  */
  
*************** init_reg_sets_1 (void)
*** 476,548 ****
    memset (have_regs_of_mode, 0, sizeof (have_regs_of_mode));
    memset (contains_reg_of_mode, 0, sizeof (contains_reg_of_mode));
    for (m = 0; m < (unsigned int) MAX_MACHINE_MODE; m++)
!     for (i = 0; i < N_REG_CLASSES; i++)
!       if ((unsigned) CLASS_MAX_NREGS (i, m) <= reg_class_size[i])
! 	for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
! 	  if (!fixed_regs [j] && TEST_HARD_REG_BIT (reg_class_contents[i], j)
! 	      && HARD_REGNO_MODE_OK (j, m))
! 	     {
! 	       contains_reg_of_mode [i][m] = 1;
! 	       have_regs_of_mode [m] = 1;
! 	       break;
! 	     }
! 
!   /* Initialize the move cost table.  Find every subset of each class
!      and take the maximum cost of moving any subset to any other.  */
! 
!   for (m = 0; m < (unsigned int) MAX_MACHINE_MODE; m++)
!     if (have_regs_of_mode [m])
!       {
! 	for (i = 0; i < N_REG_CLASSES; i++)
! 	  if (contains_reg_of_mode [i][m])
! 	    for (j = 0; j < N_REG_CLASSES; j++)
! 	      {
! 		int cost;
! 		enum reg_class *p1, *p2;
! 
! 		if (!contains_reg_of_mode [j][m])
! 		  {
! 		    move_cost[m][i][j] = 65536;
! 		    may_move_in_cost[m][i][j] = 65536;
! 		    may_move_out_cost[m][i][j] = 65536;
! 		  }
! 		else
! 		  {
! 		    cost = REGISTER_MOVE_COST (m, i, j);
! 
! 		    for (p2 = &reg_class_subclasses[j][0];
! 			 *p2 != LIM_REG_CLASSES;
! 			 p2++)
! 		      if (*p2 != i && contains_reg_of_mode [*p2][m])
! 			cost = MAX (cost, move_cost [m][i][*p2]);
! 
! 		    for (p1 = &reg_class_subclasses[i][0];
! 			 *p1 != LIM_REG_CLASSES;
! 			 p1++)
! 		      if (*p1 != j && contains_reg_of_mode [*p1][m])
! 			cost = MAX (cost, move_cost [m][*p1][j]);
! 
! 		    move_cost[m][i][j] = cost;
! 
! 		    if (reg_class_subset_p (i, j))
! 		      may_move_in_cost[m][i][j] = 0;
! 		    else
! 		      may_move_in_cost[m][i][j] = cost;
! 
! 		    if (reg_class_subset_p (j, i))
! 		      may_move_out_cost[m][i][j] = 0;
! 		    else
! 		      may_move_out_cost[m][i][j] = cost;
! 		  }
! 	      }
! 	  else
! 	    for (j = 0; j < N_REG_CLASSES; j++)
! 	      {
! 		move_cost[m][i][j] = 65536;
! 		may_move_in_cost[m][i][j] = 65536;
! 		may_move_out_cost[m][i][j] = 65536;
! 	      }
!       }
  }
  
  /* Compute the table of register modes.
--- 557,577 ----
    memset (have_regs_of_mode, 0, sizeof (have_regs_of_mode));
    memset (contains_reg_of_mode, 0, sizeof (contains_reg_of_mode));
    for (m = 0; m < (unsigned int) MAX_MACHINE_MODE; m++)
!     {
!       HARD_REG_SET ok_regs;
!       CLEAR_HARD_REG_SET (ok_regs);
!       for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
! 	if (!fixed_regs [j] && HARD_REGNO_MODE_OK (j, m))
! 	  SET_HARD_REG_BIT (ok_regs, j);
!       
!       for (i = 0; i < N_REG_CLASSES; i++)
! 	if ((unsigned) CLASS_MAX_NREGS (i, m) <= reg_class_size[i]
! 	    && hard_reg_set_intersect_p (ok_regs, reg_class_contents[i]))
! 	  {
! 	     contains_reg_of_mode [i][m] = 1;
! 	     have_regs_of_mode [m] = 1;
! 	  }
!      }
  }
  
  /* Compute the table of register modes.
*************** record_reg_classes (int n_alts, int n_op
*** 1465,1479 ****
  		     copy, which is one instruction.  */
  
  		  struct costs *pp = &this_op_costs[i];
! 
! 		  for (class = 0; class < N_REG_CLASSES; class++)
! 		    pp->cost[class]
! 		      = ((recog_data.operand_type[i] != OP_OUT
! 			  ? may_move_in_cost[mode][class][(int) classes[i]]
! 			  : 0)
! 			 + (recog_data.operand_type[i] != OP_IN
! 			    ? may_move_out_cost[mode][(int) classes[i]][class]
! 			    : 0));
  
  		  /* If the alternative actually allows memory, make things
  		     a bit cheaper since we won't need an extra insn to
--- 1494,1526 ----
  		     copy, which is one instruction.  */
  
  		  struct costs *pp = &this_op_costs[i];
! 		  move_table *intable = NULL;
! 		  move_table *outtable = NULL;
! 		  int op_class = (int) classes[i];
! 
! 		  if (!move_cost[mode])
! 		    init_move_cost (mode);
! 		  intable = may_move_in_cost[mode];
! 		  outtable = may_move_out_cost[mode];
! 
! 		  /* The loop is performance critical, so unswitch it manually.
! 		   */
! 		  switch (recog_data.operand_type[i])
! 		    {
! 		    case OP_INOUT:
! 		      for (class = 0; class < N_REG_CLASSES; class++)
! 			pp->cost[class] = (intable[class][op_class]
! 					   + outtable[op_class][class]);
! 		      break;
! 		    case OP_IN:
! 		      for (class = 0; class < N_REG_CLASSES; class++)
! 			pp->cost[class] = intable[class][op_class];
! 		      break;
! 		    case OP_OUT:
! 		      for (class = 0; class < N_REG_CLASSES; class++)
! 			pp->cost[class] = outtable[op_class][class];
! 		      break;
! 		    }
  
  		  /* If the alternative actually allows memory, make things
  		     a bit cheaper since we won't need an extra insn to
*************** record_reg_classes (int n_alts, int n_op
*** 1691,1705 ****
  	      else
  		{
  		  struct costs *pp = &this_op_costs[i];
! 
! 		  for (class = 0; class < N_REG_CLASSES; class++)
! 		    pp->cost[class]
! 		      = ((recog_data.operand_type[i] != OP_OUT
! 			  ? may_move_in_cost[mode][class][(int) classes[i]]
! 			  : 0)
! 			 + (recog_data.operand_type[i] != OP_IN
! 			    ? may_move_out_cost[mode][(int) classes[i]][class]
! 			    : 0));
  
  		  /* If the alternative actually allows memory, make things
  		     a bit cheaper since we won't need an extra insn to
--- 1738,1770 ----
  	      else
  		{
  		  struct costs *pp = &this_op_costs[i];
! 		  move_table *intable = NULL;
! 		  move_table *outtable = NULL;
! 		  int op_class = (int) classes[i];
! 
! 		  if (!move_cost[mode])
! 		    init_move_cost (mode);
! 		  intable = may_move_in_cost[mode];
! 		  outtable = may_move_out_cost[mode];
! 
! 		  /* The loop is performance critical, so unswitch it manually.
! 		   */
! 		  switch (recog_data.operand_type[i])
! 		    {
! 		    case OP_INOUT:
! 		      for (class = 0; class < N_REG_CLASSES; class++)
! 			pp->cost[class] = (intable[class][op_class]
! 					   + outtable[op_class][class]);
! 		      break;
! 		    case OP_IN:
! 		      for (class = 0; class < N_REG_CLASSES; class++)
! 			pp->cost[class] = intable[class][op_class];
! 		      break;
! 		    case OP_OUT:
! 		      for (class = 0; class < N_REG_CLASSES; class++)
! 			pp->cost[class] = outtable[op_class][class];
! 		      break;
! 		    }
  
  		  /* If the alternative actually allows memory, make things
  		     a bit cheaper since we won't need an extra insn to
*************** copy_cost (rtx x, enum machine_mode mode
*** 1856,1861 ****
--- 1921,1929 ----
    sri.extra_cost = 0;
    secondary_class = targetm.secondary_reload (to_p, x, class, mode, &sri);
  
+   if (!move_cost[mode])
+     init_move_cost (mode);
+ 
    if (secondary_class != NO_REGS)
      return (move_cost[mode][(int) secondary_class][(int) class]
  	    + sri.extra_cost
*************** record_address_regs (enum machine_mode m
*** 2056,2061 ****
--- 2124,2131 ----
  
  	pp->mem_cost += (MEMORY_MOVE_COST (Pmode, class, 1) * scale) / 2;
  
+ 	if (!move_cost[Pmode])
+ 	  init_move_cost (Pmode);
  	for (i = 0; i < N_REG_CLASSES; i++)
  	  pp->cost[i] += (may_move_in_cost[Pmode][i][(int) class] * scale) / 2;
        }

Re: Reduce startup cost of compiler (patch 2)

[Richard Guenther]

On 7/24/07, Jan Hubicka <jh@suse.cz> wrote:
> Hi,
> this patch reduces cost of move_cost tables.  THose are the largest
> tables used by regclass and are allocated as num_modes*num_classes*num_classes
> array, while just modes that might appear in pseudos really matters.
>
> The patch turns the tables into arrays of pointers to arrays so
> only those modes needed are allocated (about 2K each) and the tables
> are filled in lazily, so for normal units all those weird vector modes don't
> need to be considered.  Additionally the code is now watching if
> the table match last table and avoids computation then saving some extra
> memory for vector modes that are largely identical.
>
> I've also changed move cost type to short to save some extra memory, the values
> are used in very internal loop of regclass that I unswitched. The patch is neutral
> for combine.c (it however brings record_reg_classes down in schedule) and makes
> noticeable difference to startup time (see profiles from previous patch)
>
> Bootstrapped/regtested i686-linux?

Nice!  Yes, this is ok.

Thanks,
Richard.

Re: Reduce startup cost of compiler (patch 2)

[Paolo Bonzini]

>> Bootstrapped/regtested i686-linux?
> 
> Nice!  Yes, this is ok.

all_match is write only, though:

+   bool all_match = true;
+   unsigned int i, j;
+
+   gcc_assert (have_regs_of_mode[m]);
+   for (i = 0; i < N_REG_CLASSES; i++)
+     if (contains_reg_of_mode[i][m])
+       for (j = 0; j < N_REG_CLASSES; j++)
+ 	{
+ 	  int cost;
+ 	  if (!contains_reg_of_mode[j][m])
+ 	    cost = 65535;
+ 	  else
+ 	    {
+ 	      cost = REGISTER_MOVE_COST (m, i, j);
+ 	      gcc_assert (cost < 65535);
+ 	    }
+ 	  all_match &= (last_move_cost[i][j] == cost);

Re: Reduce startup cost of compiler (patch 2)

[Jan Hubicka]

> 
> >>Bootstrapped/regtested i686-linux?
> >
> >Nice!  Yes, this is ok.
> 
> all_match is write only, though:

Uh, good catch.  I was testing if removing that trick slows down startup
(and it does) and forgot to put it back.  I am re-testing the attached
patch which I will commit if it passes.

Honza

Index: regclass.c
===================================================================
*** regclass.c	(revision 126859)
--- regclass.c	(working copy)
*************** bool have_regs_of_mode [MAX_MACHINE_MODE
*** 214,233 ****
  
  static char contains_reg_of_mode [N_REG_CLASSES] [MAX_MACHINE_MODE];
  
  /* Maximum cost of moving from a register in one class to a register in
     another class.  Based on REGISTER_MOVE_COST.  */
  
! static int move_cost[MAX_MACHINE_MODE][N_REG_CLASSES][N_REG_CLASSES];
  
  /* Similar, but here we don't have to move if the first index is a subset
     of the second so in that case the cost is zero.  */
  
! static int may_move_in_cost[MAX_MACHINE_MODE][N_REG_CLASSES][N_REG_CLASSES];
  
  /* Similar, but here we don't have to move if the first index is a superset
     of the second so in that case the cost is zero.  */
  
! static int may_move_out_cost[MAX_MACHINE_MODE][N_REG_CLASSES][N_REG_CLASSES];
  
  #ifdef FORBIDDEN_INC_DEC_CLASSES
  
--- 214,235 ----
  
  static char contains_reg_of_mode [N_REG_CLASSES] [MAX_MACHINE_MODE];
  
+ typedef unsigned short move_table[N_REG_CLASSES];
+ 
  /* Maximum cost of moving from a register in one class to a register in
     another class.  Based on REGISTER_MOVE_COST.  */
  
! static move_table *move_cost[MAX_MACHINE_MODE];
  
  /* Similar, but here we don't have to move if the first index is a subset
     of the second so in that case the cost is zero.  */
  
! static move_table *may_move_in_cost[MAX_MACHINE_MODE];
  
  /* Similar, but here we don't have to move if the first index is a superset
     of the second so in that case the cost is zero.  */
  
! static move_table *may_move_out_cost[MAX_MACHINE_MODE];
  
  #ifdef FORBIDDEN_INC_DEC_CLASSES
  
*************** init_reg_sets (void)
*** 312,317 ****
--- 314,409 ----
  #endif
  }
  
+ /* Initialize may_move_cost and friends for mode M.  */
+ 
+ static void
+ init_move_cost (enum machine_mode m)
+ {
+   static unsigned short last_move_cost[N_REG_CLASSES][N_REG_CLASSES];
+   static int last_mode = -1;
+   bool all_match = true;
+   unsigned int i, j;
+ 
+   gcc_assert (have_regs_of_mode[m]);
+   for (i = 0; i < N_REG_CLASSES; i++)
+     if (contains_reg_of_mode[i][m])
+       for (j = 0; j < N_REG_CLASSES; j++)
+ 	{
+ 	  int cost;
+ 	  if (!contains_reg_of_mode[j][m])
+ 	    cost = 65535;
+ 	  else
+ 	    {
+ 	      cost = REGISTER_MOVE_COST (m, i, j);
+ 	      gcc_assert (cost < 65535);
+ 	    }
+ 	  all_match &= (last_move_cost[i][j] == cost);
+ 	  last_move_cost[i][j] = cost;
+ 	}
+   if (all_match && last_mode != -1)
+     {
+       move_cost[m] = move_cost[last_mode];
+       may_move_in_cost[m] = may_move_in_cost[last_mode];
+       may_move_out_cost[m] = may_move_out_cost[last_mode];
+       return;
+     }
+   last_mode = m;
+   move_cost[m] = (move_table *)xmalloc (sizeof (move_table)
+ 					* N_REG_CLASSES);
+   may_move_in_cost[m] = (move_table *)xmalloc (sizeof (move_table)
+ 					       * N_REG_CLASSES);
+   may_move_out_cost[m] = (move_table *)xmalloc (sizeof (move_table)
+ 					        * N_REG_CLASSES);
+   for (i = 0; i < N_REG_CLASSES; i++)
+     if (contains_reg_of_mode[i][m])
+       for (j = 0; j < N_REG_CLASSES; j++)
+ 	{
+ 	  int cost;
+ 	  enum reg_class *p1, *p2;
+ 
+ 	  if (last_move_cost[i][j] == 65535)
+ 	    {
+ 	      move_cost[m][i][j] = 65535;
+ 	      may_move_in_cost[m][i][j] = 65535;
+ 	      may_move_out_cost[m][i][j] = 65535;
+ 	    }
+ 	  else
+ 	    {
+ 	      cost = last_move_cost[i][j];
+ 
+ 	      for (p2 = &reg_class_subclasses[j][0];
+ 		   *p2 != LIM_REG_CLASSES; p2++)
+ 		if (*p2 != i && contains_reg_of_mode[*p2][m])
+ 		  cost = MAX (cost, move_cost[m][i][*p2]);
+ 
+ 	      for (p1 = &reg_class_subclasses[i][0];
+ 		   *p1 != LIM_REG_CLASSES; p1++)
+ 		if (*p1 != j && contains_reg_of_mode[*p1][m])
+ 		  cost = MAX (cost, move_cost[m][*p1][j]);
+ 
+ 	      gcc_assert (cost <= 65535);
+ 	      move_cost[m][i][j] = cost;
+ 
+ 	      if (reg_class_subset_p (i, j))
+ 		may_move_in_cost[m][i][j] = 0;
+ 	      else
+ 		may_move_in_cost[m][i][j] = cost;
+ 
+ 	      if (reg_class_subset_p (j, i))
+ 		may_move_out_cost[m][i][j] = 0;
+ 	      else
+ 		may_move_out_cost[m][i][j] = cost;
+ 	    }
+ 	}
+     else
+       for (j = 0; j < N_REG_CLASSES; j++)
+ 	{
+ 	  move_cost[m][i][j] = 65535;
+ 	  may_move_in_cost[m][i][j] = 65535;
+ 	  may_move_out_cost[m][i][j] = 65535;
+ 	}
+ }
+ 
  /* After switches have been processed, which perhaps alter
     `fixed_regs' and `call_used_regs', convert them to HARD_REG_SETs.  */
  
*************** init_reg_sets_1 (void)
*** 476,548 ****
    memset (have_regs_of_mode, 0, sizeof (have_regs_of_mode));
    memset (contains_reg_of_mode, 0, sizeof (contains_reg_of_mode));
    for (m = 0; m < (unsigned int) MAX_MACHINE_MODE; m++)
!     for (i = 0; i < N_REG_CLASSES; i++)
!       if ((unsigned) CLASS_MAX_NREGS (i, m) <= reg_class_size[i])
! 	for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
! 	  if (!fixed_regs [j] && TEST_HARD_REG_BIT (reg_class_contents[i], j)
! 	      && HARD_REGNO_MODE_OK (j, m))
! 	     {
! 	       contains_reg_of_mode [i][m] = 1;
! 	       have_regs_of_mode [m] = 1;
! 	       break;
! 	     }
! 
!   /* Initialize the move cost table.  Find every subset of each class
!      and take the maximum cost of moving any subset to any other.  */
! 
!   for (m = 0; m < (unsigned int) MAX_MACHINE_MODE; m++)
!     if (have_regs_of_mode [m])
!       {
! 	for (i = 0; i < N_REG_CLASSES; i++)
! 	  if (contains_reg_of_mode [i][m])
! 	    for (j = 0; j < N_REG_CLASSES; j++)
! 	      {
! 		int cost;
! 		enum reg_class *p1, *p2;
! 
! 		if (!contains_reg_of_mode [j][m])
! 		  {
! 		    move_cost[m][i][j] = 65536;
! 		    may_move_in_cost[m][i][j] = 65536;
! 		    may_move_out_cost[m][i][j] = 65536;
! 		  }
! 		else
! 		  {
! 		    cost = REGISTER_MOVE_COST (m, i, j);
! 
! 		    for (p2 = &reg_class_subclasses[j][0];
! 			 *p2 != LIM_REG_CLASSES;
! 			 p2++)
! 		      if (*p2 != i && contains_reg_of_mode [*p2][m])
! 			cost = MAX (cost, move_cost [m][i][*p2]);
! 
! 		    for (p1 = &reg_class_subclasses[i][0];
! 			 *p1 != LIM_REG_CLASSES;
! 			 p1++)
! 		      if (*p1 != j && contains_reg_of_mode [*p1][m])
! 			cost = MAX (cost, move_cost [m][*p1][j]);
! 
! 		    move_cost[m][i][j] = cost;
! 
! 		    if (reg_class_subset_p (i, j))
! 		      may_move_in_cost[m][i][j] = 0;
! 		    else
! 		      may_move_in_cost[m][i][j] = cost;
! 
! 		    if (reg_class_subset_p (j, i))
! 		      may_move_out_cost[m][i][j] = 0;
! 		    else
! 		      may_move_out_cost[m][i][j] = cost;
! 		  }
! 	      }
! 	  else
! 	    for (j = 0; j < N_REG_CLASSES; j++)
! 	      {
! 		move_cost[m][i][j] = 65536;
! 		may_move_in_cost[m][i][j] = 65536;
! 		may_move_out_cost[m][i][j] = 65536;
! 	      }
!       }
  }
  
  /* Compute the table of register modes.
--- 568,588 ----
    memset (have_regs_of_mode, 0, sizeof (have_regs_of_mode));
    memset (contains_reg_of_mode, 0, sizeof (contains_reg_of_mode));
    for (m = 0; m < (unsigned int) MAX_MACHINE_MODE; m++)
!     {
!       HARD_REG_SET ok_regs;
!       CLEAR_HARD_REG_SET (ok_regs);
!       for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
! 	if (!fixed_regs [j] && HARD_REGNO_MODE_OK (j, m))
! 	  SET_HARD_REG_BIT (ok_regs, j);
!       
!       for (i = 0; i < N_REG_CLASSES; i++)
! 	if ((unsigned) CLASS_MAX_NREGS (i, m) <= reg_class_size[i]
! 	    && hard_reg_set_intersect_p (ok_regs, reg_class_contents[i]))
! 	  {
! 	     contains_reg_of_mode [i][m] = 1;
! 	     have_regs_of_mode [m] = 1;
! 	  }
!      }
  }
  
  /* Compute the table of register modes.
*************** record_reg_classes (int n_alts, int n_op
*** 1465,1479 ****
  		     copy, which is one instruction.  */
  
  		  struct costs *pp = &this_op_costs[i];
! 
! 		  for (class = 0; class < N_REG_CLASSES; class++)
! 		    pp->cost[class]
! 		      = ((recog_data.operand_type[i] != OP_OUT
! 			  ? may_move_in_cost[mode][class][(int) classes[i]]
! 			  : 0)
! 			 + (recog_data.operand_type[i] != OP_IN
! 			    ? may_move_out_cost[mode][(int) classes[i]][class]
! 			    : 0));
  
  		  /* If the alternative actually allows memory, make things
  		     a bit cheaper since we won't need an extra insn to
--- 1505,1537 ----
  		     copy, which is one instruction.  */
  
  		  struct costs *pp = &this_op_costs[i];
! 		  move_table *intable = NULL;
! 		  move_table *outtable = NULL;
! 		  int op_class = (int) classes[i];
! 
! 		  if (!move_cost[mode])
! 		    init_move_cost (mode);
! 		  intable = may_move_in_cost[mode];
! 		  outtable = may_move_out_cost[mode];
! 
! 		  /* The loop is performance critical, so unswitch it manually.
! 		   */
! 		  switch (recog_data.operand_type[i])
! 		    {
! 		    case OP_INOUT:
! 		      for (class = 0; class < N_REG_CLASSES; class++)
! 			pp->cost[class] = (intable[class][op_class]
! 					   + outtable[op_class][class]);
! 		      break;
! 		    case OP_IN:
! 		      for (class = 0; class < N_REG_CLASSES; class++)
! 			pp->cost[class] = intable[class][op_class];
! 		      break;
! 		    case OP_OUT:
! 		      for (class = 0; class < N_REG_CLASSES; class++)
! 			pp->cost[class] = outtable[op_class][class];
! 		      break;
! 		    }
  
  		  /* If the alternative actually allows memory, make things
  		     a bit cheaper since we won't need an extra insn to
*************** record_reg_classes (int n_alts, int n_op
*** 1691,1705 ****
  	      else
  		{
  		  struct costs *pp = &this_op_costs[i];
! 
! 		  for (class = 0; class < N_REG_CLASSES; class++)
! 		    pp->cost[class]
! 		      = ((recog_data.operand_type[i] != OP_OUT
! 			  ? may_move_in_cost[mode][class][(int) classes[i]]
! 			  : 0)
! 			 + (recog_data.operand_type[i] != OP_IN
! 			    ? may_move_out_cost[mode][(int) classes[i]][class]
! 			    : 0));
  
  		  /* If the alternative actually allows memory, make things
  		     a bit cheaper since we won't need an extra insn to
--- 1749,1781 ----
  	      else
  		{
  		  struct costs *pp = &this_op_costs[i];
! 		  move_table *intable = NULL;
! 		  move_table *outtable = NULL;
! 		  int op_class = (int) classes[i];
! 
! 		  if (!move_cost[mode])
! 		    init_move_cost (mode);
! 		  intable = may_move_in_cost[mode];
! 		  outtable = may_move_out_cost[mode];
! 
! 		  /* The loop is performance critical, so unswitch it manually.
! 		   */
! 		  switch (recog_data.operand_type[i])
! 		    {
! 		    case OP_INOUT:
! 		      for (class = 0; class < N_REG_CLASSES; class++)
! 			pp->cost[class] = (intable[class][op_class]
! 					   + outtable[op_class][class]);
! 		      break;
! 		    case OP_IN:
! 		      for (class = 0; class < N_REG_CLASSES; class++)
! 			pp->cost[class] = intable[class][op_class];
! 		      break;
! 		    case OP_OUT:
! 		      for (class = 0; class < N_REG_CLASSES; class++)
! 			pp->cost[class] = outtable[op_class][class];
! 		      break;
! 		    }
  
  		  /* If the alternative actually allows memory, make things
  		     a bit cheaper since we won't need an extra insn to
*************** copy_cost (rtx x, enum machine_mode mode
*** 1856,1861 ****
--- 1932,1940 ----
    sri.extra_cost = 0;
    secondary_class = targetm.secondary_reload (to_p, x, class, mode, &sri);
  
+   if (!move_cost[mode])
+     init_move_cost (mode);
+ 
    if (secondary_class != NO_REGS)
      return (move_cost[mode][(int) secondary_class][(int) class]
  	    + sri.extra_cost
*************** record_address_regs (enum machine_mode m
*** 2056,2061 ****
--- 2135,2142 ----
  
  	pp->mem_cost += (MEMORY_MOVE_COST (Pmode, class, 1) * scale) / 2;
  
+ 	if (!move_cost[Pmode])
+ 	  init_move_cost (Pmode);
  	for (i = 0; i < N_REG_CLASSES; i++)
  	  pp->cost[i] += (may_move_in_cost[Pmode][i][(int) class] * scale) / 2;
        }

Re: Reduce startup cost of compiler (patch 2)

[Rask Ingemann Lambertsen]

On Tue, Jul 24, 2007 at 07:02:10AM +0200, Jan Hubicka wrote:

> Index: regclass.c
[snip init_move_cost()]
> + 	      cost = REGISTER_MOVE_COST (m, i, j);
> + 	      gcc_assert (cost < 65535);

   Would you mind documenting this new upper limit? It happened to break my
16-bit x86 target where I try to discurage the register allocator from using
unusable classes such as ALL_REGS.

-- 
Rask Ingemann Lambertsen

Re: Reduce startup cost of compiler (patch 2)

[Jan Hubicka]

> On Tue, Jul 24, 2007 at 07:02:10AM +0200, Jan Hubicka wrote:
> 
> > Index: regclass.c
> [snip init_move_cost()]
> > + 	      cost = REGISTER_MOVE_COST (m, i, j);
> > + 	      gcc_assert (cost < 65535);
> 
>    Would you mind documenting this new upper limit? It happened to break my
> 16-bit x86 target where I try to discurage the register allocator from using
> unusable classes such as ALL_REGS.

Hi,
the limitation was alwas there - regclass used value of 65535 as an
infinity for impossible combinations.  This also means that you should
not need to discougrate ALL_REGS and similar classes since regstack is
supposed to work this out.  Documenting the maximum is however not bad
idea.

Honza

	* doc/tm.texi (REGISTER_MOVE_COST, MEMORY_MOVE_COST): Document maximal
	values.

Index: doc/tm.texi
===================================================================
*** doc/tm.texi	(revision 127065)
--- doc/tm.texi	(working copy)
*************** classes returns a value of 2, reload doe
*** 5737,5742 ****
--- 5737,5743 ----
  constraints of the insn are met.  Setting a cost of other than 2 will
  allow reload to verify that the constraints are met.  You should do this
  if the @samp{mov@var{m}} pattern's constraints do not allow such copying.
+ The maximal allowed value is 65535.
  @end defmac
  
  @defmac MEMORY_MOVE_COST (@var{mode}, @var{class}, @var{in})
*************** is to be written to memory, nonzero if i
*** 5746,5751 ****
--- 5747,5753 ----
  is relative to those in @code{REGISTER_MOVE_COST}.  If moving between
  registers and memory is more expensive than between two registers, you
  should define this macro to express the relative cost.
+ The maximal allowed value is 65535.
  
  If you do not define this macro, GCC uses a default cost of 4 plus
  the cost of copying via a secondary reload register, if one is

Re: Reduce startup cost of compiler (patch 2)

[Rask Ingemann Lambertsen]

On Tue, Jul 31, 2007 at 05:52:16AM +0200, Jan Hubicka wrote:
> 
> Hi,
> the limitation was alwas there

   COSTS_N_INSNS (60000) = 240000 used to work fine. :-)

> - regclass used value of 65535 as an
> infinity for impossible combinations.  This also means that you should
> not need to discougrate ALL_REGS and similar classes since regstack is
> supposed to work this out.

   It's a good thing you say "supposed to". Regclass tends to prefer
ALL_REGS over MEM and ALL_REGS tends to include such things as virtual
hard regs. Returning a high REGISTER_MOVE_COST for ALL_REGS keeps regclass
clear of ALL_REGS.

>   if the @samp{mov@var{m}} pattern's constraints do not allow such copying.
> + The maximal allowed value is 65535.
>   @end defmac

   Well, it's 65534, isn't it?

-- 
Rask Ingemann Lambertsen

Re: Reduce startup cost of compiler (patch 2)

[Jan Hubicka]

> On Tue, Jul 31, 2007 at 05:52:16AM +0200, Jan Hubicka wrote:
> > 
> > Hi,
> > the limitation was alwas there
> 
>    COSTS_N_INSNS (60000) = 240000 used to work fine. :-)

Well, it depends on definition of the word "work" :)
It a sense of not ICEing it works, in a sense of giving meaningful cost
model it does not.
> 
> > - regclass used value of 65535 as an
> > infinity for impossible combinations.  This also means that you should
> > not need to discougrate ALL_REGS and similar classes since regstack is
> > supposed to work this out.
> 
>    It's a good thing you say "supposed to". Regclass tends to prefer
> ALL_REGS over MEM and ALL_REGS tends to include such things as virtual
> hard regs. Returning a high REGISTER_MOVE_COST for ALL_REGS keeps regclass
> clear of ALL_REGS.

Well, regclass is not able to work out all details (it always assumes
worst case for union classes), but in your case it seems you got
something wrong.
ALL_REGS even if it contains hard regs such as stack pointers and
virtual frame pointers, they are fixed and should not cause much harm to
you. Can you send a bit more details how your classes/costs are set up?
> 
> >   if the @samp{mov@var{m}} pattern's constraints do not allow such copying.
> > + The maximal allowed value is 65535.
> >   @end defmac
> 
>    Well, it's 65534, isn't it?

Hmm, if we can find good reason for register move cost to trick the
infinity cost as you want to do, we can probably relax the assert and
document 65535 as infinity.

Honza
> 
> -- 
> Rask Ingemann Lambertsen

Re: Reduce startup cost of compiler (patch 2)

[Rask Ingemann Lambertsen]

On Tue, Jul 31, 2007 at 05:44:49PM +0200, Jan Hubicka wrote:

> Well, regclass is not able to work out all details (it always assumes
> worst case for union classes), but in your case it seems you got
> something wrong.
> ALL_REGS even if it contains hard regs such as stack pointers and
> virtual frame pointers, they are fixed and should not cause much harm to
> you. Can you send a bit more details how your classes/costs are set up?

   The comment I have for REGISTER_MOVE_COST says: "Discourage regclass.c
from using ALL_REGS as alternate class." So the issue is not about ALL_REGS
as the preferred class but that regclass would choose e.g. GENERAL_REGS as
preferred class and ALL_REGS as alternate class where it should choose MEM
as alternate class.

-- 
Rask Ingemann Lambertsen

Re: Reduce startup cost of compiler (patch 2)

[Michael Matz]

Hi,

On Fri, 3 Aug 2007, Rask Ingemann Lambertsen wrote:

> On Tue, Jul 31, 2007 at 05:44:49PM +0200, Jan Hubicka wrote:
> 
> > Well, regclass is not able to work out all details (it always assumes
> > worst case for union classes), but in your case it seems you got
> > something wrong.
> > ALL_REGS even if it contains hard regs such as stack pointers and
> > virtual frame pointers, they are fixed and should not cause much harm to
> > you. Can you send a bit more details how your classes/costs are set up?
> 
>    The comment I have for REGISTER_MOVE_COST says: "Discourage regclass.c
> from using ALL_REGS as alternate class." So the issue is not about ALL_REGS
> as the preferred class but that regclass would choose e.g. GENERAL_REGS as
> preferred class and ALL_REGS as alternate class where it should choose MEM
> as alternate class.

Well, the question was why do you think it was bad for regclass to choose 
ALL_REGS as alternate class?  It may have been not optimal perhaps, but 
from the thread it sounds as if it was a correctness issue for you.  If 
that is the case then this means you have a real bug somewhere else, as 
regclass theoretically could choose random classes as preferred and 
alternate class, and everything still works (with many reloads).  It's 
only an optimization hint, not a correctness measure.

OTOH if it was really only about optimization (i.e. choosing ALL_REGS is 
a bad decision) then adjusting the move cost was correct, but you didn't 
really have to use 65535 :-)  It would have been enough to make the cost 
higher than for memory moves.


Ciao,
Michael.

Re: Reduce startup cost of compiler (patch 2)

[Rask Ingemann Lambertsen]

On Fri, Aug 03, 2007 at 02:13:04PM +0200, Michael Matz wrote:

> OTOH if it was really only about optimization (i.e. choosing ALL_REGS is 
> a bad decision) then adjusting the move cost was correct, but you didn't 
> really have to use 65535 :-)  It would have been enough to make the cost 
> higher than for memory moves.

   Yes, it's purely an optimization issue. There are no useable registers in
ALL_REGS that aren't in any other class also. ALL_REGS is simply a junk
class. I picked COSTS_N_INSNS (60000) to mean "disabled". That's now
COSTS_N_INSNS (16000) which seems to do the trick also. :-)

-- 
Rask Ingemann Lambertsen