My registers spilleth over... (fwd)

[hjl@nynexst.com (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