Re: (i386-linux x sh-elf) More weak stack addressing

Re: (i386-linux x sh-elf) More weak stack addressing

[Joern Rennecke]

In article <200006290530.WAA01339@netcom.com> you wrote:
: version: CVS
:    host: i386-linux
:  target: sh-elf
: options: -O2 -m4-single-only -ml -S -g

: More weak stack addressing samples from stress-1.14.tar.gz at:

: ftp://shell14.ba.best.com/pub.t/tm2/stress-1.14.tar.gz

: GCC creates multiple pointers to the same stack slot and unnecessarily
: eats up hard registers:

: 6363:./vtkTriangleStrip.ii ****       {

I suppose I have a slightly different code base, since I get slightly
different code.  Yet, the basic pattern seems to be the same:  Inheritance
is prevented because the register is immediately resued for something else.
The first pattern looks like this:

        mov     #124,r3
        mov     #124,r7
        mov.w   .L88,r2
        add     r14,r3
        mov.l   .L89,r1
        add     r14,r7
        mov.l   @(52,r3),r3

This insn is being reloaded:
(gdb) call debug_rtx(chain->insn)
(insn 4156 1297 1300 (set (mem:SI (plus:SI (plus:SI (reg:SI 14 r14)
                    (const_int 188 [0xbc]))
                (const_int 28 [0x1c])) 25)
        (mem:SI (plus:SI (plus:SI (reg:SI 14 r14)
                    (const_int 124 [0x7c]))
                (const_int 52 [0x34])) 15)) 83 {movsi_ie} (nil)
    (nil))

And we get these reloads:
(gdb) call debug_reload()
Reload 0: reload_in (SI) = (plus:SI (reg:SI 14 r14)
                                                    (const_int 188 [0xbc]))
        GENERAL_REGS, RELOAD_FOR_OPERAND_ADDRESS (opnum = 0)
        reload_in_reg: (plus:SI (reg:SI 14 r14)
                                                    (const_int 188 [0xbc]))
        reload_reg_rtx: (reg:SI 2 r2)
Reload 1: reload_in (SI) = (plus:SI (reg:SI 14 r14)
                                                    (const_int 124 [0x7c]))
        GENERAL_REGS, RELOAD_FOR_INPUT_ADDRESS (opnum = 1)
        reload_in_reg: (plus:SI (reg:SI 14 r14)
                                                    (const_int 124 [0x7c]))
        reload_reg_rtx: (reg:SI 3 r3)
Reload 2: reload_out (SI) = (mem:SI (plus:SI (plus:SI (reg:SI 14 r14)
                                                            (const_int 188 [0xbc]))
                                                        (const_int 28 [0x1c])) 25)
        NO_REGS, RELOAD_FOR_OUTPUT (opnum = 0), optional
        reload_out_reg: (reg:SI 315)
Reload 3: reload_in (SI) = (mem:SI (plus:SI (plus:SI (reg:SI 14 r14)
                                                            (const_int 124 [0x7c]))
                                                        (const_int 52 [0x34])) 15)
        GENERAL_REGS, RELOAD_FOR_INPUT (opnum = 1), can't combine
        reload_in_reg: (reg/v:SI 70)
        reload_reg_rtx: (reg:SI 3 r3)

This re-using of reload registers is actually intentional.
allocate_reload_reg prefers registers that have been used previously.
If I disable this logic, I get a .s file that is about 1% shorter.

Index: reload1.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/reload1.c,v
retrieving revision 1.216
diff -p -r1.216 reload1.c
*** reload1.c	2000/06/06 02:40:14	1.216
--- reload1.c	2000/07/18 14:53:09
*************** allocate_reload_reg (chain, r, last_relo
*** 5018,5025 ****
  		 don't share regs used for inherited reloads; they are
  		 the ones we want to preserve.  */
  	      && (pass
! 		  || (TEST_HARD_REG_BIT (reload_reg_used_at_all,
! 					 regnum)
  		      && ! TEST_HARD_REG_BIT (reload_reg_used_for_inherit,
  					      regnum))))
  	    {
--- 5018,5025 ----
  		 don't share regs used for inherited reloads; they are
  		 the ones we want to preserve.  */
  	      && (pass
! 		  || ((1 || TEST_HARD_REG_BIT (reload_reg_used_at_all,
! 					 regnum))
  		      && ! TEST_HARD_REG_BIT (reload_reg_used_for_inherit,
  					      regnum))))
  	    {

Should we have a target macro to disable this logic?  Or maybe we should
identify reloads that are particularily suitable for inheritance,
(i.e. constants, addresses on the stack, and pseudos), and add them to
reload_reg_used_for_inherit?

Re: (i386-linux x sh-elf) More weak stack addressing

[Toshiyasu Morita]

On Sat, 22 Jul 2000, Joern Rennecke wrote:

> > I noticed this patch has already been applied to CVS...I'm still seeing 
> 
> Huh?  What patch has been applied to CVS?
> 

Sorry, I thought it'd be applied to CVS already.

I haven't tested the patch because the sh-elf target is broken
again in CVS. Will take another look when it's fixed.

Toshi

Re: (i386-linux x sh-elf) More weak stack addressing

[Joern Rennecke]

> I noticed this patch has already been applied to CVS...I'm still seeing 

Huh?  What patch has been applied to CVS?

Re: (i386-linux x sh-elf) More weak stack addressing

[Toshiyasu Morita]

On Thu, 20 Jul 2000, Joern Rennecke wrote:

> > On Thu, Jul 20, 2000 at 03:06:35PM -0700, Toshiyasu Morita wrote:
> >  
> > > Maybe I'm missing something, but it seems peeking beyond labels is 
> > > extremely important for the Hitachi SH. Forgive me for overexplaining
> > > a bit - I'm basically explaining my assumptions to see if people
> > > can spot any glaring oversights.
> > > 
> > > Consider:
> > > 
> > > The SH uses pc-relative addressing to load large constants, 
> > > therefore it generates literal pools in the .text segment. These 
> > > literal pools must be "jumped around" to continue execution.
> 
> But they don't exist yet at reload time.  They are generated in a later
> pass.

Doh! Okay.

I noticed this patch has already been applied to CVS...I'm still seeing 
a few more problems in advmilitary.i from stress-1.15 compiled with -O2 
-m4-single-only -ml:

1580 073c 7CE1                 mov     #124,r1         <- here
 1581 073e 7CE0                 mov     #124,r0         <- here
 1582 0740 EC31                 add     r14,r1          <- here
 1583 0742 1453                 mov.l   @(16,r1),r3
 1584 0744 EC30                 add     r14,r0          <- here
 1585 0746 9191                 mov.w   .L255,r1
 1586 0748 3152                 mov.l   @(4,r3),r2
 1589 074a 3355                 mov.l   @(12,r3),r5
 1592 074c 1702                 mul.l   r1,r2
 1595 074e 3254                 mov.l   @(8,r3),r4
 1598 0750 1A01                 sts     macl,r1
 1599 0752 AC31                 add     r10,r1
 1600 0754 1C10                 mov.l   r1,@(48,r0)
 1603 0756 4BD1                 mov.l   .L256,r1
 1604 0758 0B41                 jsr     @r1
 1605 075a 0900                 nop
...
3599:./advmilitary.i ****       { struct genlist_iterator myiter; struct 
city *  acity ; genlist_iterator_init(&myiter, & apl
 1843 08c8 7CE2                 mov     #124,r2         <- here
 1844 08ca 60D1                 mov.l   .L273,r1
 1845 08cc EC32                 add     r14,r2          <- here
 1846 08ce E36B                 mov     r14,r11         <- here
 1847 08d0 2B55                 mov.l   @(44,r2),r5
 1848 08d2 7C7B                 add     #124,r11        <- here
 1849 08d4 00E6                 mov     #0,r6
 1850 08d6 FC7F                 add     #-4,r15
 1851 08d8 B364                 mov     r11,r4
 1852 08da 0B41                 jsr     @r1
 1853 08dc 6075                 add     #96,r5
 1854 08de B151                 mov.l   @(4,r11),r1
 1855 08e0 1251                 mov.l   @(8,r1),r1
 1856 08e2 1821                 tst     r1,r1
 1857 08e4 028F                 bf.s    .L365
 1858 08e6 047F                 add     #4,r15
 1859 08e8 A0A1                 bra     .L368
 1860 08ea 7CE1                 mov     #124,r1
...
 3456 128c 7CE2                 mov     #124,r2         <- here
 3457 128e 7CE1                 mov     #124,r1         <- here
 3458 1290 1293                 mov.w   .L350,r3
 3459 1292 EC31                 add     r14,r1          <- here
 3460 1294 EC32                 add     r14,r2          <- here
 3461 1296 1450                 mov.l   @(16,r1),r0
3756:./advmilitary.i ****   return(urgency);
3757:./advmilitary.i **** }
 3464 1298 747E                 add     #116,r14
 3467 129a 2E52                 mov.l   @(56,r2),r2
 3470 129c 787E                 add     #120,r14
 3473 129e 2603                 mov.l   r2,@(r0,r3)
 3476 12a0 2360                 mov     r2,r0
 3479 12a2 E36F                 mov     r14,r15
 3480 12a4 264F                 lds.l   @r15+,pr
 3481 12a6 F66E                 mov.l   @r15+,r14
 3482 12a8 F66D                 mov.l   @r15+,r13
 3483 12aa F66C                 mov.l   @r15+,r12
 3484 12ac F66B                 mov.l   @r15+,r11
 3485 12ae F66A                 mov.l   @r15+,r10
 3486 12b0 F669                 mov.l   @r15+,r9
 3487 12b2 0B00                 rts
 3488 12b4 F668                 mov.l   @r15+,r8
...
4212:./advmilitary.i ****   struct unit virtualunit;
4213:./advmilitary.i ****   struct city *acity = 0;
 7850 2c30 E362                 mov     r14,r2
 7853 2c32 EC31                 add     r14,r1
 7856 2c34 7072                 add     #112,r2
 7859 2c36 0211                 mov.l   r0,@(8,r1)
 7862 2c38 2511                 mov.l   r2,@(20,r1)
 7863 2c3a 7CE1                 mov     #124,r1         <- here
 7864 2c3c EC31                 add     r14,r1          <- here
 7865 2c3e 1152                 mov.l   @(4,r1),r2
 7866 2c40 A991                 mov.w   .L872,r1
 7867 2c42 EC31                 add     r14,r1
 7868 2c44 1261                 mov.l   @r1,r1
 7869 2c46 2221                 mov.l   r2,@r1
4214:./advmilitary.i ****   struct unit *aunit = 0;
 7872 2c48 E362                 mov     r14,r2
 7873 2c4a 7CE1                 mov     #124,r1         <- here
 7874 2c4c 6C72                 add     #108,r2
 7875 2c4e EC31                 add     r14,r1          <- here
 7876 2c50 2411                 mov.l   r2,@(16,r1)
 7877 2c52 7CE1                 mov     #124,r1         <- here
 7878 2c54 EC31                 add     r14,r1          <- here
 7879 2c56 1152                 mov.l   @(4,r1),r2
 7880 2c58 9E91                 mov.w   .L873,r1

Toshi

Re: (i386-linux x sh-elf) More weak stack addressing

[Joern Rennecke]

> Yup.  There's a number of optimizers that could benefit from working on
> EBBs.  Including register allocation.

Well, reload inheritance already does.
Just by not invalidating information about old reloads when a jump is
passed.

Re: (i386-linux x sh-elf) More weak stack addressing

[Jeffrey A Law]

  In message < 20000720173747.A12948@cpopetz.com >you write:
  > Essentially you want the various optimization passes to operate on EBB
  > (extended basic blocks) where possible.  This is a worthwhile goal,
  > but it will take a lot of work to get there.
Yup.  There's a number of optimizers that could benefit from working on
EBBs.  Including register allocation.

If someone wants to take a step in that direction, writing code to build
EBBs would be greatly appreciated.  Algorithms to compute EBBs from the
existing CFG can be found in Muchnick and probably other books.

Once we can build EBBs, then we can look at improving the optimizers to
use EBBs.

jeff

Re: (i386-linux x sh-elf) More weak stack addressing

[Joern Rennecke]

> On Thu, Jul 20, 2000 at 03:06:35PM -0700, Toshiyasu Morita wrote:
>  
> > Maybe I'm missing something, but it seems peeking beyond labels is 
> > extremely important for the Hitachi SH. Forgive me for overexplaining
> > a bit - I'm basically explaining my assumptions to see if people
> > can spot any glaring oversights.
> > 
> > Consider:
> > 
> > The SH uses pc-relative addressing to load large constants, 
> > therefore it generates literal pools in the .text segment. These 
> > literal pools must be "jumped around" to continue execution.

But they don't exist yet at reload time.  They are generated in a later
pass.

> > >From a code analysis perspective, these jumps aren't really jumps
> > since they jump to a label accessed by only a single jump. Therefore
> > the jump destination can be considered in the same block as the jump
> > source.
> > 
> > If an optimization pass assumes a jump ends a basic block, it will miss 
> > many potential optimiations.

My test doesn't consider jumps - only labels.

Re: (i386-linux x sh-elf) More weak stack addressing

[Clinton Popetz]

On Thu, Jul 20, 2000 at 03:06:35PM -0700, Toshiyasu Morita wrote:
 
> Maybe I'm missing something, but it seems peeking beyond labels is 
> extremely important for the Hitachi SH. Forgive me for overexplaining
> a bit - I'm basically explaining my assumptions to see if people
> can spot any glaring oversights.
> 
> Consider:
> 
> The SH uses pc-relative addressing to load large constants, 
> therefore it generates literal pools in the .text segment. These 
> literal pools must be "jumped around" to continue execution.
> 
> >From a code analysis perspective, these jumps aren't really jumps
> since they jump to a label accessed by only a single jump. Therefore
> the jump destination can be considered in the same block as the jump
> source.
> 
> If an optimization pass assumes a jump ends a basic block, it will miss 
> many potential optimiations.

Essentially you want the various optimization passes to operate on EBB
(extended basic blocks) where possible.  This is a worthwhile goal,
but it will take a lot of work to get there.

				-Clint

Re: (i386-linux x sh-elf) More weak stack addressing

[Toshiyasu Morita]

On Wed, 19 Jul 2000, Joern Rennecke wrote:

> > I suspect a more comprehensive solution is required.
> > 
> > Even with this patch, I see the following generated elsewhere:
> > 
> > 6237:vtkTriangleStrip.ii ****   cell->DeepCopy(*this);
> >  49924 0280 FC7F                add     #-4,r15
> >  49925 0282 7CE7                mov     #124,r7		<- here
> >  49926 0284 6F93                mov.w   .L103,r3
> >  49927 0286 EC37                add     r14,r7		<- here
> >  49928 0288 7A52                mov.l   @(40,r7),r2
> >  49929 028a EC33                add     r14,r3
> >  49930 028c 7A57                mov.l   @(40,r7),r7
> >  49931 028e 2351                mov.l   @(12,r2),r1
> >  49932 0290 6077                add     #96,r7
> >  49933 0292 7713                mov.l   r7,@(28,r3)
> 
> What else would you do, with only r3 and r7 available as reload registers?
> sometimes there just aren't enough reload registers to go around.
> 
> I tried a more elaborate patch that peeks ahead what reloads are
> actually useful for future inheritance, but it actually results in
> one more assembler line for your testcase.
> Well, unless you peek ahead beyond labels, then it saves 5 lines,
> but such a strategy doesn't really make any sense.

Maybe I'm missing something, but it seems peeking beyond labels is 
extremely important for the Hitachi SH. Forgive me for overexplaining
a bit - I'm basically explaining my assumptions to see if people
can spot any glaring oversights.

Consider:

The SH uses pc-relative addressing to load large constants, 
therefore it generates literal pools in the .text segment. These 
literal pools must be "jumped around" to continue execution.

From a code analysis perspective, these jumps aren't really jumps
since they jump to a label accessed by only a single jump. Therefore
the jump destination can be considered in the same block as the jump
source.

If an optimization pass assumes a jump ends a basic block, it will miss 
many potential optimiations.

I think one example of this is regmove. If I remember correctly from an 
old PR, it misses many potential optimization opportunities in C++ 
exception handling code for the Hitachi SH because many literal pools are 
generated, and regmove assumes the basic block ends at the jump around 
the literal pool.

Toshi

Re: (i386-linux x sh-elf) More weak stack addressing

[Joern Rennecke]

> I suspect a more comprehensive solution is required.
> 
> Even with this patch, I see the following generated elsewhere:
> 
> 6237:vtkTriangleStrip.ii ****   cell->DeepCopy(*this);
>  49924 0280 FC7F                add     #-4,r15
>  49925 0282 7CE7                mov     #124,r7		<- here
>  49926 0284 6F93                mov.w   .L103,r3
>  49927 0286 EC37                add     r14,r7		<- here
>  49928 0288 7A52                mov.l   @(40,r7),r2
>  49929 028a EC33                add     r14,r3
>  49930 028c 7A57                mov.l   @(40,r7),r7
>  49931 028e 2351                mov.l   @(12,r2),r1
>  49932 0290 6077                add     #96,r7
>  49933 0292 7713                mov.l   r7,@(28,r3)

What else would you do, with only r3 and r7 available as reload registers?
sometimes there just aren't enough reload registers to go around.

I tried a more elaborate patch that peeks ahead what reloads are
actually useful for future inheritance, but it actually results in
one more assembler line for your testcase.
Well, unless you peek ahead beyond labels, then it saves 5 lines,
but such a strategy doesn't really make any sense.

Index: reload1.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/reload1.c,v
retrieving revision 1.216
diff -p -r1.216 reload1.c
*** reload1.c	2000/06/06 02:40:14	1.216
--- reload1.c	2000/07/19 16:43:52
*************** allocate_reload_reg (chain, r, last_relo
*** 4953,4960 ****
       int r;
       int last_reload;
  {
!   int i, pass, count;
! 
    /* If we put this reload ahead, thinking it is a group,
       then insist on finding a group.  Otherwise we can grab a
       reg that some other reload needs.
--- 4953,5001 ----
       int r;
       int last_reload;
  {
!   int i, pass, count, want_inherit, q, force_group;
!   rtx in, last;
!   struct insn_chain *next;
! 
!   /* Check if this reload's value is useful for future inheritance.  */
!   want_inherit = 0;
!   in = rld[r].in_reg;
!   if (in
!       && ! rld[r].out
!       && (CONSTANT_P (in)
! 	  || GET_CODE (in) == REG
! 	  || (GET_CODE (in) == PLUS
! 	      && (XEXP (in, 0) == stack_pointer_rtx
! 		  || XEXP (in, 0) == frame_pointer_rtx)
! 	      && CONSTANT_P (XEXP (in, 1)))))
!     {
!       for (q = r + 1; q < chain->n_reloads; q++)
! 	if (rtx_equal_p (rld[r].in_reg, chain->rld[q].in_reg))
! 	  want_inherit = 1;
! #if 0
!       want_inherit = 1;
! #endif
!       last = chain->insn;
!       for (next = chain, count = n_spills * 3;
! 	   (next = next->next_need_reload) && --count >= 0;)
! 	{
! #if 1
! 	  if (! no_labels_between_p (last, next->insn))
! 	    {
! 	      count = -1;
! 	      break;
! 	    }
! #endif
! 	  last = next->insn;
! 	  for (q = next->n_reloads; --q >= 0;)
! 	    if (rtx_equal_p (rld[r].in_reg, next->rld[q].in_reg))
! 	      break;
! 	  if (q >= 0)
! 	    break;
! 	}
!       if (count >= 0)
! 	want_inherit = 1;
!     }
    /* If we put this reload ahead, thinking it is a group,
       then insist on finding a group.  Otherwise we can grab a
       reg that some other reload needs.
*************** allocate_reload_reg (chain, r, last_relo
*** 4968,4974 ****
       Perhaps those classes should be avoided for reloading
       by use of more alternatives.  */
  
!   int force_group = rld[r].nregs > 1 && ! last_reload;
  
    /* If we want a single register and haven't yet found one,
       take any reg in the right class and not in use.
--- 5009,5015 ----
       Perhaps those classes should be avoided for reloading
       by use of more alternatives.  */
  
!   force_group = rld[r].nregs > 1 && ! last_reload;
  
    /* If we want a single register and haven't yet found one,
       take any reg in the right class and not in use.
*************** allocate_reload_reg (chain, r, last_relo
*** 4982,4988 ****
       reloads A and B can share regs.  These need two regs.
       Suppose A and B are given different regs.
       That leaves none for C.  */
!   for (pass = 0; pass < 2; pass++)
      {
        /* I is the index in spill_regs.
  	 We advance it round-robin between insns to use all spill regs
--- 5023,5029 ----
       reloads A and B can share regs.  These need two regs.
       Suppose A and B are given different regs.
       That leaves none for C.  */
!   for (pass = 0; pass < 2 + want_inherit; pass++)
      {
        /* I is the index in spill_regs.
  	 We advance it round-robin between insns to use all spill regs
*************** allocate_reload_reg (chain, r, last_relo
*** 5017,5025 ****
  	      /* Look first for regs to share, then for unshared.  But
  		 don't share regs used for inherited reloads; they are
  		 the ones we want to preserve.  */
! 	      && (pass
! 		  || (TEST_HARD_REG_BIT (reload_reg_used_at_all,
! 					 regnum)
  		      && ! TEST_HARD_REG_BIT (reload_reg_used_for_inherit,
  					      regnum))))
  	    {
--- 5058,5066 ----
  	      /* Look first for regs to share, then for unshared.  But
  		 don't share regs used for inherited reloads; they are
  		 the ones we want to preserve.  */
! 	      && (pass > want_inherit
! 		  || ((!! TEST_HARD_REG_BIT (reload_reg_used_at_all, regnum)
! 		       ^ (want_inherit > pass))
  		      && ! TEST_HARD_REG_BIT (reload_reg_used_for_inherit,
  					      regnum))))
  	    {
*************** allocate_reload_reg (chain, r, last_relo
*** 5062,5067 ****
--- 5103,5118 ----
    /* We should have found a spill register by now.  */
    if (count >= n_spills)
      return 0;
+ 
+   if (TEST_HARD_REG_BIT (reload_reg_used_for_inherit, spill_regs[i]))
+ {
+ #if 1
+     want_inherit = 0;
+     CLEAR_HARD_REG_BIT (reload_reg_used_for_inherit, spill_regs[i]);
+ #endif
+ }
+   if (want_inherit)
+     SET_HARD_REG_BIT (reload_reg_used_for_inherit, spill_regs[i]);
  
    /* I is the index in SPILL_REG_RTX of the reload register we are to
       allocate.  Get an rtx for it and find its register number.  */