Re: local alloc / global alloc / reload problem

Re: local alloc / global alloc / reload problem

[John Wehle]

> So what happened before the regmove change in terms of global alloc
> and reload?  ie, what hard reg was pseudo 28 assigned to?  Presumably
> that hard reg did not end up being used as a spill.

With the old regmove:

(insn 29 27 31 (set (reg:SI 28)
        (xor:SI (reg/v:SI 21)
            (const_int 1))) -1 (nil)
    (nil))

(insn 31 29 33 (set (mem:SI (pre_dec:SI (reg:SI 7 %esp)))
        (reg:SI 28)) -1 (insn_list 29 (nil))
    (expr_list:REG_DEAD (reg:SI 28)
        (nil)))

is turned into (in other words ... no change):

(insn 29 27 31 (set (reg:SI 28)
        (xor:SI (reg/v:SI 21)
            (const_int 1))) 189 {xorsi3} (nil)
    (nil))

(insn 31 29 33 (set (mem:SI (pre_dec:SI (reg:SI 7 %esp)))
        (reg:SI 28)) 50 {movsi-2} (insn_list 29 (nil))
    (expr_list:REG_DEAD (reg:SI 28)
        (nil)))

Local register allocation allocates hard register 0 for reg 28.
Global register allocation is performed and reload is called.  Hard
register 0 is spilled placing reg 28 on the stack.  Reload notices
that the xor needs fixing since the RTL template is:

  [(set (match_operand:SI 0 "nonimmediate_operand" "=rm,r")
	(xor:SI (match_operand:SI 1 "nonimmediate_operand" "%0,0")
		(match_operand:SI 2 "general_operand" "ri,rm")))]

The result after global register allocation and reload is:

(insn 281 27 29 (set (reg:SI 1 %edx)
        (mem:SI (plus:SI (reg:SI 6 %ebp)
                (const_int 8)))) 54 {movsi+2} (nil)
    (nil))

(insn:HI 29 281 31 (set (reg:SI 1 %edx)
        (xor:SI (reg:SI 1 %edx)
            (const_int 1))) 189 {xorsi3} (nil)
    (nil))

(insn:QI 31 29 33 (set (mem:SI (pre_dec:SI (reg:SI 7 %esp)))
        (reg:SI 1 %edx)) 50 {movsi-2} (insn_list 29 (nil))
    (expr_list:REG_DEAD (reg:SI 1 %edx)
        (nil)))

The difference is that with the new regmove reload didn't need to
fix up the xor so it left reg 28 on the stack.  With the old regmove
reload needs to fix up the xor which results in a register being
used.

-- John Wehle
-------------------------------------------------------------------------
|   Feith Systems  |   Voice: 1-215-646-8000  |  Email: john@feith.com  |
|    John Wehle    |     Fax: 1-215-540-5495  |                         |
-------------------------------------------------------------------------

Re: local alloc / global alloc / reload problem

[Jeffrey A Law]

  In message < 199807130430.AAA17950@jwlab.FEITH.COM >you write:
  > It appears that i386 performance regression resulting from the June 11
  > regmove change is due to regmove turning:
  > 
  > (insn 29 27 31 (set (reg:SI 28)
  >         (xor:SI (reg/v:SI 21)
  >             (const_int 1))) -1 (nil)
  >     (nil))
  > 
  > (insn 31 29 33 (set (mem:SI (pre_dec:SI (reg:SI 7 %esp)))
  >         (reg:SI 28)) -1 (insn_list 29 (nil))
  >     (expr_list:REG_DEAD (reg:SI 28)
  >         (nil)))
  > 
  > into:
  > 
  > (insn 280 27 29 (set (reg:SI 28)
  >         (reg/v:SI 21)) 54 {movsi+2} (nil)
  >     (nil))
  > 
  > (insn 29 280 31 (set (reg:SI 28)
  >         (xor:SI (reg:SI 28)
  >             (const_int 1))) 189 {xorsi3} (nil)
  >     (nil))
  > 
  > (insn 31 29 33 (set (mem:SI (pre_dec:SI (reg:SI 7 %esp)))
  >         (reg:SI 28)) 50 {movsi-2} (insn_list 29 (nil))
  >     (expr_list:REG_DEAD (reg:SI 28)
  >         (nil)))
  > 
  > Local register allocation allocates hard register 0 for reg 28.
  > This is noticed by:
  > 
  >   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
  >     if (REG_N_REFS (i) != 0 && reg_renumber[i] < 0 && REG_LIVE_LENGTH (i) !
  > = -1
  > 	&& (! current_function_has_nonlocal_label
	    || REG_N_CALLS_CROSSED (i) == 0))
  >       {
  > 	[ ... ]
  >       }
  >     else
  >       reg_allocno[i] = -1;
  > 
  > in global_alloc so reg_allocno[28] is set to -1.  Global register
  > allocation is performed and reload is called.  Hard register 0 is
  > spilled and retry_global_alloc is called for reg 28.  As a result
  > of reg_allocno equaling -1 retry_global_alloc doesn't do anything
  > and reg 28 ends up on the stack even though a hard register may of
  > been available.
  > 
  > The enclosed patch is intended ONLY as food for thought ... it does
  > NOT survive a bootstrap.  Hopefully someone more knowledgeable about
  > these issues will chime in.
Current the compiler does not support re-allocation of regs which are
allocated by local-alloc, but are kicked out due to the actions of either
global register allocation or reload.

It doesn't seem like a particularly difficult problem to solve, but then 
again I've never tried or even looked deeply into why we've got this
restriction.

So what happened before the regmove change in terms of global alloc
and reload?  ie, what hard reg was pseudo 28 assigned to?  Presumably
that hard reg did not end up being used as a spill.


jeff

local alloc / global alloc / reload problem

[John Wehle]

It appears that i386 performance regression resulting from the June 11
regmove change is due to regmove turning:

(insn 29 27 31 (set (reg:SI 28)
        (xor:SI (reg/v:SI 21)
            (const_int 1))) -1 (nil)
    (nil))

(insn 31 29 33 (set (mem:SI (pre_dec:SI (reg:SI 7 %esp)))
        (reg:SI 28)) -1 (insn_list 29 (nil))
    (expr_list:REG_DEAD (reg:SI 28)
        (nil)))

into:

(insn 280 27 29 (set (reg:SI 28)
        (reg/v:SI 21)) 54 {movsi+2} (nil)
    (nil))

(insn 29 280 31 (set (reg:SI 28)
        (xor:SI (reg:SI 28)
            (const_int 1))) 189 {xorsi3} (nil)
    (nil))

(insn 31 29 33 (set (mem:SI (pre_dec:SI (reg:SI 7 %esp)))
        (reg:SI 28)) 50 {movsi-2} (insn_list 29 (nil))
    (expr_list:REG_DEAD (reg:SI 28)
        (nil)))

Local register allocation allocates hard register 0 for reg 28.
This is noticed by:

  for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
    if (REG_N_REFS (i) != 0 && reg_renumber[i] < 0 && REG_LIVE_LENGTH (i) != -1
	&& (! current_function_has_nonlocal_label
	    || REG_N_CALLS_CROSSED (i) == 0))
      {
	[ ... ]
      }
    else
      reg_allocno[i] = -1;

in global_alloc so reg_allocno[28] is set to -1.  Global register
allocation is performed and reload is called.  Hard register 0 is
spilled and retry_global_alloc is called for reg 28.  As a result
of reg_allocno equaling -1 retry_global_alloc doesn't do anything
and reg 28 ends up on the stack even though a hard register may of
been available.

The enclosed patch is intended ONLY as food for thought ... it does
NOT survive a bootstrap.  Hopefully someone more knowledgeable about
these issues will chime in.

ChangeLog:

Sun Jul 12 23:25:04 EDT 1998  John Wehle  (john@feith.com)

	* global.c (global_alloc): Assign allocation-numbers
	even for registers allocated by local_alloc in case
	they are later spilled and retry_global_alloc is called.

Enjoy!

-- John Wehle
------------------8<------------------------8<------------------------
*** gcc/global.c.ORIGINAL	Sun Jun 21 15:54:56 1998
--- gcc/global.c	Sun Jul 12 23:22:36 1998
***************
*** 389,395 ****
      /* Note that reg_live_length[i] < 0 indicates a "constant" reg
         that we are supposed to refrain from putting in a hard reg.
         -2 means do make an allocno but don't allocate it.  */
!     if (REG_N_REFS (i) != 0 && reg_renumber[i] < 0 && REG_LIVE_LENGTH (i) != -1
  	/* Don't allocate pseudos that cross calls,
  	   if this function receives a nonlocal goto.  */
  	&& (! current_function_has_nonlocal_label
--- 389,395 ----
      /* Note that reg_live_length[i] < 0 indicates a "constant" reg
         that we are supposed to refrain from putting in a hard reg.
         -2 means do make an allocno but don't allocate it.  */
!     if (REG_N_REFS (i) != 0 && REG_LIVE_LENGTH (i) != -1
  	/* Don't allocate pseudos that cross calls,
  	   if this function receives a nonlocal goto.  */
  	&& (! current_function_has_nonlocal_label
***************
*** 433,439 ****
    bzero ((char *) local_reg_live_length, sizeof local_reg_live_length);
    bzero ((char *) local_reg_n_refs, sizeof local_reg_n_refs);
    for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
!     if (reg_allocno[i] < 0 && reg_renumber[i] >= 0)
        {
  	int regno = reg_renumber[i];
  	int endregno = regno + HARD_REGNO_NREGS (regno, PSEUDO_REGNO_MODE (i));
--- 433,439 ----
    bzero ((char *) local_reg_live_length, sizeof local_reg_live_length);
    bzero ((char *) local_reg_n_refs, sizeof local_reg_n_refs);
    for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
!     if (reg_renumber[i] >= 0)
        {
  	int regno = reg_renumber[i];
  	int endregno = regno + HARD_REGNO_NREGS (regno, PSEUDO_REGNO_MODE (i));
***************
*** 561,567 ****
  	 except for parameters marked with reg_live_length[regno] == -2.  */
  
        for (i = 0; i < max_allocno; i++)
! 	if (REG_LIVE_LENGTH (allocno_reg[allocno_order[i]]) >= 0)
  	  {
  	    /* If we have more than one register class,
  	       first try allocating in the class that is cheapest
--- 561,568 ----
  	 except for parameters marked with reg_live_length[regno] == -2.  */
  
        for (i = 0; i < max_allocno; i++)
! 	if (reg_renumber[allocno_reg[allocno_order[i]]] < 0
! 	    && REG_LIVE_LENGTH (allocno_reg[allocno_order[i]]) >= 0)
  	  {
  	    /* If we have more than one register class,
  	       first try allocating in the class that is cheapest
-------------------------------------------------------------------------
|   Feith Systems  |   Voice: 1-215-646-8000  |  Email: john@feith.com  |
|    John Wehle    |     Fax: 1-215-540-5495  |                         |
-------------------------------------------------------------------------