From mboxrd@z Thu Jan  1 00:00:00 1970
From: Michael Meissner <meissner@cygnus.com>
To: hjl@nynexst.com
Cc: gas2@cygnus.com, gcc2@cygnus.com
Subject: My registers spilleth over... (fwd)
Date: Wed, 16 Aug 1995 06:10:00 -0000
Message-id: <199508161310.JAA01232@tiktok.cygnus.com>
References: <9508152031.AA08641@nynexst.com> <9508152031.AA08641@nynexst.com>
X-SW-Source: 1995/msg00152.html

(Gcc2 folks, the complaint is yet another register spill case
involving long longs, in this case building a cross debugger from x86
to alpha).

| The second problem was when I was compiling gdb; at one point, I got
| the following:
| 
| 	fixed or forbidden register was spilled.
| 	This may be due to a compiler bug or to impossible asm
| 	statements or clauses.
| 
| Turns out it was a compiler bug, though I don't know enough to be able to
| fix it.  Basically, the register-spilling algorithm breaks down terribly
| when you run out of spillable registers.

This has been a neverending struggle on the x86 and long longs.  With
some programs, changing the allocation order helps with -mreg-alloc=.
When I was actively working on the x86 port, I had programs that would
work with one order or another.  

IMHO, the real problem is the register allocator, and the reload phase
in particular.  However, rewriting it would take a while (and even
longer to shake out the bugs).  At one point, I had management at OSF
signed up to give me the time to do this, and then priorities (and the
layoff) occurred.

| because the compiler ran out of otherwise spillable registers and tried
| to spill SP (not a good thing to do if you want to find where you *put*
| the spilled data!).  When I fixed it so as not to do this, it then 
| tried to spill a previously-spilled-now-live register, and again gave
| the above message.  When I fixed *THAT*, it just threw up its hands and
| panic'ed with "can't find any more registers to spill".
| 
| Basically, I think this is a design deficiency in the register-allocation
| algorithm.  Every other architecture that gcc runs on has a large enough
| register set so that you'll never hit this case.  Intel, with its
| braindead register architecture left over from the 8088 days, is more
| likely to run out of places to put the data first....

| There are several ways to address this problem... one might abort and re-run 
| the register allocation on the routine, hauling fewer and fewer in-memory
| variables into registers until one is able to obtain a successful allocation.
| Or, one might implement multiple-spillage, using register coloring to
| determine just *how* live a register is (i.e. if it's not used in an
| inner scope but it is used in an outer scope, you can consider it "not
| dead but resting" and spill it temporarily).  Those who do compilers for
| a living no doubt could think up more.

Actually GCC does all that now (maybe not to the extent it could), and
it doesn't help sometimes.  But the more fundamendal problem is that
this takes a lot of work, and the GCC teams already has lots of
desirable work that also needs time and (smart) bodies.

-- 
Michael Meissner, Cygnus Support (East Coast)
Suite 105, 48 Grove Street, Somerville, MA 02144, USA
meissner@cygnus.com,	617-629-3016 (office),	617-629-3010 (fax)