My registers spilleth over... (fwd)

My registers spilleth over... (fwd)

[H.J. Lu]

Forwarded message:
From owner-gcc@vger.rutgers.edu Fri Aug  4 02:50:53 1995
From: Jim Paradis <paradis@amt.tay1.dec.com>
Message-Id: <9508040120.AA07184@ives.amt.tay1.dec.com>
Subject: My registers spilleth over...
To: linux-gcc@vger.rutgers.edu, linux-alpha@vger.rutgers.edu
Date: Thu, 3 Aug 1995 21:20:07 -0500 (EDT)
X-Mailer: ELM [version 2.4 PL13]
Mime-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Content-Length: 3854      
Sender: owner-gcc@vger.rutgers.edu
Precedence: bulk

This message is of greater interest to the linux-gcc list, but it's also
of interest to the linux-alpha list as well...

For the linux-alpha folks: Someone, some weeks back, tried and failed to
cross-compile Linux/Alpha 1.2 on a Linux/i486 box.  I told him at the
time that that was because he was using the 32-bit cross-development
tools, and that I could build him a set of 64-bit cross-tools that would 
do the job.

I then went and tried to build a set of cross tools on my Linux/i486 box,
only to have the build fall over dead.  To make a VERY long story short,
I'd stumbled over not one but TWO bugs in both gcc2.6.3 and gcc2.7.0 for
i486.  I've since made workarounds that should allow me to build a working
64-bit cross-tool set.  It's building even as we speak, and I'll put it
up on gatekeeper once I've verified it.

(linux-gcc people can tune in now):  The first bug I found was when my
freshly-built gas tried to build a "dummy" Alpha object file (basically, a
six-line bit of assembly code that's nothing more than a single routine
consiisting of a single "ret" instruction).  gas fell over dead when it
tried to build it: got "Assertion failed in write.c".  Much tracking down
finally got me to the following line of code:

	fragp->fr_offset += newsize - size;

All of the variables above are 64-bit "long long"'s.  newsize=16, size=12;
therefore fragp->fr_offset should have been incremented by 12.  Instead it
was incremented by 24.  I figure this is a bug in the handling of
"long long"s by the i486 code generator; if I break the above apart into
two statements:

	fragp->fr_offset = fragp->fr_offset + newsize;
	fragp->fr_offset = fragp->fr_offset - size;

then everything works fine.

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.  The above message 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.

Anyhow: my workaround was to recompile the offending file with the 
-fvolatile flag.  It slows the code down, but it gets you there!

Anyhow: anyone with *real* fixes to these problems is more than welcome
to come forward 8-)

-- 
Jim Paradis (paradis@amt.tay1.dec.com)        "It's not procrastination, 
Digital Equipment Corporation		       it's my new Just-In-Time 
(508)952-4047				       Workload Management System!"


-- 
H.J. Lu
NYNEX Science and Technology, Inc.			hjl@nynexst.com

Re: My registers spilleth over... (fwd)

[Ian Lance Taylor]

   From: hjl@nynexst.com (H.J. Lu)
   Date: Tue, 15 Aug 95 16:30:38 EDT

   Forwarded message:
   From: Jim Paradis <paradis@amt.tay1.dec.com>
   Date: Thu, 3 Aug 1995 21:20:07 -0500 (EDT)

   (linux-gcc people can tune in now):  The first bug I found was when my
   freshly-built gas tried to build a "dummy" Alpha object file (basically, a
   six-line bit of assembly code that's nothing more than a single routine
   consiisting of a single "ret" instruction).  gas fell over dead when it
   tried to build it: got "Assertion failed in write.c".  Much tracking down
   finally got me to the following line of code:

	   fragp->fr_offset += newsize - size;

   All of the variables above are 64-bit "long long"'s.  newsize=16, size=12;
   therefore fragp->fr_offset should have been incremented by 12.  Instead it
   was incremented by 24.  I figure this is a bug in the handling of
   "long long"s by the i486 code generator; if I break the above apart into
   two statements:

	   fragp->fr_offset = fragp->fr_offset + newsize;
	   fragp->fr_offset = fragp->fr_offset - size;

   then everything works fine.

Note that this is a compiler bug.  Nothing needs to be changed in gas.

Ian

My registers spilleth over... (fwd)

[Michael Meissner]

(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)