Re: simpler test for spilling problem

[Richard Henderson <rth at cygnus dot com>]

On Sat, Dec 26, 1998 at 09:24:12AM -0800, Ulrich Drepper wrote:
> At ~drepper/stringperf.i.bz2 you can find a simpler test for the
> spilling problem.  But maybe it's also a different problem.  It now
> happens even without PIC enabled.
[...]
> It puts the asms in parallel and so minds up with lots of confliects
> and cannot possibly find the correct spill registers.

Actually, the parallel is just the way an asm with multiple
outputs is written.  Occasionally annoying, since it takes
up a lot of room, but there we are.

This is very tricky.  There is no bug, strictly speaking.  The
form that your asm takes is difficult to handle well.

  __asm__ __volatile__
    (
     "..."
     : "=a" (__res), "=&c" (__s1), "=&d" (__s2)
     : "0" (0), "1" (__s1), "2" (__s2)
     : "cc");

Here's the reloads this asm produces:

Reload 0: reload_in (SI) = (reg:SI 33)
        INDEX_REGS, RELOAD_FOR_OTHER_ADDRESS (opnum = 1)
        reload_in_reg: (reg:SI 33)
Reload 1: reload_in (SI) = (reg:SI 85)
        INDEX_REGS, RELOAD_FOR_OTHER_ADDRESS (opnum = 2)
        reload_in_reg: (reg:SI 85)
Reload 2: reload_in (SI) = (const_int 0)
        reload_out (SI) = (reg/v:SI 0 eax)
        AREG, RELOAD_OTHER (opnum = 0)
        reload_in_reg: (const_int 0)
        reload_out_reg: (reg/v:SI 0 eax)
        reload_reg_rtx: (reg/v:SI 0 eax)
Reload 3: reload_in (SI) = (mem/s:SI (plus:SI (reg:SI 5 edi)
                                              (reg:SI 33)) 0)
        reload_out (SI) = (reg/v:SI 2 ecx)
        CREG, RELOAD_OTHER (opnum = 1)
        reload_in_reg: (mem/s:SI (plus:SI (reg:SI 5 edi)
                                          (reg:SI 33)) 0)
        reload_out_reg: (reg/v:SI 2 ecx)
        reload_reg_rtx: (reg/v:SI 2 ecx)
Reload 4: reload_in (SI) = (mem/s:SI (plus:SI (reg:SI 85)
                                              (reg:SI 5 edi)) 0)
        reload_out (SI) = (reg/v:SI 1 edx)
        DREG, RELOAD_OTHER (opnum = 2)
        reload_in_reg: (mem/s:SI (plus:SI (reg:SI 85)
                                          (reg:SI 5 edi)) 0)
        reload_out_reg: (reg/v:SI 1 edx)
        reload_reg_rtx: (reg/v:SI 1 edx)

The matching input constraints ("0" etc) create the input-output
reloads marked RELOAD_OTHER.  These reloads are very long lived.

Note that the inputs for __s1 and __s2 were combined from memories,
and that one component each of the addresses did not receive a hard
reg.  This necessitates the RELOAD_FOR_OTHER_ADDRESS reloads, which
by necessity have a similarly long lifespan as those that
created them.

Since these are input-output reloads, and are thus all live
simultaneously, none of the reload registers involved may be
reused.  If we count up the registers involved, remembering
that %edi is used as well, we total 6 needed registers.  Given
that we're using -fpic and no -fomit-frame-pointer, we only
have 5 available. 

And so we loose.

Now, if we rewrite the asm like so

-     : "=a" (__res), "=&c" (__s1), "=&d" (__s2)
-     : "0" (0), "1" (__s1), "2" (__s2)
+     : "=a" (__res), "=c" (__s1), "=d" (__s2)
+     : "a" (0), "c" (__s1), "d" (__s2)

That is, replace the matching input constraints with the 
one-of register class that it belonged to, and remove the
early clobber because we have a non-matched input that we
do want at the same place.

Since we have no constraints that match memory, and so do not
have to worry about addresses, and since we performed the 
substitution only on one-of register classes, I claim this is
equivalent.

This produces the reloads

Reload 0: reload_in (SI) = (reg:SI 33)
	INDEX_REGS, RELOAD_FOR_INPUT_ADDRESS (opnum = 4)
	reload_in_reg: (reg:SI 33)
Reload 1: reload_in (SI) = (reg:SI 85)
	INDEX_REGS, RELOAD_FOR_INPUT_ADDRESS (opnum = 5)
	reload_in_reg: (reg:SI 85)
Reload 2: reload_in (SI) = (const_int 0)
	AREG, RELOAD_FOR_INPUT (opnum = 3)
	reload_in_reg: (const_int 0)
Reload 3: reload_in (SI) = (mem/s:SI (plus:SI (reg:SI 5 edi)
                                              (reg:SI 33)) 0)
        CREG, RELOAD_FOR_INPUT (opnum = 4)
        reload_in_reg: (mem/s:SI (plus:SI (reg:SI 5 edi)
                                          (reg:SI 33)) 0)
Reload 4: reload_in (SI) = (mem/s:SI (plus:SI (reg:SI 85)
                                              (reg:SI 5 edi)) 0)
        DREG, RELOAD_FOR_INPUT (opnum = 5)
        reload_in_reg: (mem/s:SI (plus:SI (reg:SI 85)
                                          (reg:SI 5 edi)) 0)

There are no output reloads, I think, because __res, __s1 and
__s2 got allocated to the proper hard register.  I'm not sure
if that happened before; it may well have.

The good bit is that RELOAD_FOR_INPUT reloads only live until
the start of the instruction, and RELOAD_FOR_INPUT_ADDRESS
reloads die as the input reload that created it comes to life.
So INPUT and INPUT_ADDRESS reloads can share a register.

And so we win:

        xorl    %eax, %eax
        movl    (%esi,%edi), %ecx
        movl    -48(%ebp), %edx
        movl    (%edi,%edx), %edx
#APP
	[...]
#NO_APP

Now, there is an outside chance that it might be possible to 
do this transformation automatically, but the complexity of
the test that would be necessary leaves doubt. 

The question to the gcc team is: should we try, or should we
ask the programmer to evaluate whether the modification is
legal and if so, do it themselves?

Alternately, or perhaps in addition, we might could teach
combine not to substitute memories when they won't be accepted.
In flow, we had

	0[ (const_int 0) (reg:SI 38) (reg:SI 41) ]

as input; combine substituted

	0[ (const_int 0)
           (mem/s:SI (plus:SI (reg:SI 29)
                              (reg:SI 33)) 0)
           (mem/s:SI (plus:SI (reg:SI 85)
                              (reg:SI 29)) 0)
	]

If this had not been done, we would have not had the
OTHER_ADDRESS reloads, and might well have needed only
three registers.

Thoughts?


r~