Link-time relaxing for m68k ELF

[msokolov at ivan dot Harhan dot ORG (Michael Sokolov)]

Hi there,

OK, I'm finally getting to what I really want: link-time relaxing for m68k. I
wanted to do this back in January, but had nowhere near the needed binutils
hacking skills. I spent these three months sharpening my skills, though, and
now I'm back at it and this time I'll do it.

I'm now ready to dive in, but before I do, I just wanted to discuss with Ian
and others how I'm going to do it, to make sure it's right. Basically, I'm
planning to implement link-time relaxation the same way other targets do it:
have the assembler keep all relocs in the object file, even seemingly
unnecessary ones, to make it possible to stretch or compress sections (and
while we are at it, turn off the assembler's own relaxer, as it will only
interfere), and put in the relaxing routine in the BFD backend that goes over
the relocs, finds relaxable ones, and relaxes them, changing the instructions
and stretching/compressing the section as necessary. As it's much cheaper for
the linker and the BFD backend to compress a section than to stretch it, have
the assembler generate the longest (worst-case) instruction or sequence and
then have the linker relax it by shrinking it as much as possible.

However, there are two issues I need to discuss with Ian and others here, one
technical and one administrative, which are actually two sides of the same
issue: how to represent relaxable relocs in the object file and how to detect
them. The technical difficulty occurs in the detection part. All BFD backends I
have seen so far doing this kind of relaxing are for RISC architectures where
instructions have a fairly uniform format. Those backends simply assume that
all relocs in a code section are in instructions, and given the simplicity of
the architecture, they can easily locate the opcode and figure out the rest
from it. This won't be as simple for m68k. This is a CISC architecture and the
instruction format is very lax. Given a relocatable location, one can't really
figure out where is the opcode for the instruction whose operand it is.
Consider, for example, a relocatable reference operand directly following the
opcode vs. following a prior immediate operand in the instruction stream.
Therefore, we will really need some magic markers in the object file to denote
the relaxable relocs and convey this information.

The administrative issue is ABI conformance and compatibility. The linker must
of course accept existing ABI-compliant objects on input. Since the ABI doesn't
have link-time relaxing in mind, the sections in these objects won't be
stretchable or compressible, and we must not try to relax them. This means that
we will need relaxability markers in objects, treated as GNU extensions to the
ABI. Since objects with these markers probably won't be ABI-compliant or
intelligible by other linkers (and since the assembler's own relaxer will
probably need to be turned off), generating objects for link-time relaxing
should probably only be enabled by a special option in gas. In the linker the
relaxer is optional, called only with -relax, but we should still accept
objects assembled for link-time relaxing, i.e., recognize our special relaxable
relocs, just process them normally, without relaxing. This also means that
aside from special relocs or other markers, the relaxable objects must still
have absolutely valid processor code in them, ready for execution, even if not
the most efficient.

The above considerations bring me to the following strategy: invent new GNU
extension reloc types that are just like normal absolute and PC-relative relocs
(specifically, we'll need 32-bit absolute, 32-bit PC-relative, and 16-bit PC-
relative), but indicate relaxability. Have the assembler generate them only
when preparing objects for link-time relaxing, so that without this special
option gas output will be ABI-compliant. Have the normal reloc processing in
BFD handle them just like the corresponding normal relocs, so that nothing
weird happens when one links without relaxing. Have the relaxing routine in the
BFD backend do anything only when it encounters one of these relocs, ensuring
that it won't muck up an ABI-compliant object.

This still leaves one more issue. If you look at the current relaxer in gas,
you'll see that it handles several different kinds of relaxing, as there are
plenty of relaxing opportunities on m68k. Ideally I would like the link-time
relaxer to support all of them too, and also add some new ones to better handle
the differences between 68000 and 68020 and adequately address the needs of
both communities, and I'm ready to do the work to implement it. However, the
relaxer will need to know what kind of relaxation to perform. As on the m68k we
generally can't recover the opcode from a relocatable reference operand, this
information has to be communicated in the relaxability marker. Creating a whole
bunch of different reloc types for this seems distasteful to me, and it
actually won't solve the problem. For at least one relaxing mode the relaxable
reference is an instruction operand that can appear in almost any instruction
and is not necessarily the first, making it practically impossible to recover
the opcode word for the instruction it belongs to, and when this operand is
relaxed, the opcode needs to be changed. This can only be done practically by
including the offset between the opcode word and the relaxable operand in the
relaxability marker.

Here's what I'm thinking about. m68k ELF uses .rela, which means that the
contents of the relocation slots in the section image is not used. What about
storing the relaxation control information there? I think we will still need
special relocs to denote relaxability, as I think in the ABI-compliant objects
the contents of the relocation slots is undefined, not necessarily zero.
However, these special relocs would only indicate relaxability and the use of
our GNU extension, and then the relocation slots would be consulted for the
rest.

Ian and other gurus, what do you think about all this? Am I on the right track
or am I nuts? TIA.

--
Michael Sokolov		Harhan Engineering Laboratory
Public Service Agent	International Free Computing Task Force
			International Engineering and Science Task Force
			615 N GOOD LATIMER EXPY STE #4
			DALLAS TX 75204-5852 USA

Phone: +1-214-824-7693 (Harhan Eng Lab office)
E-mail: msokolov@ivan.Harhan.ORG (ARPA TCP/SMTP) (UUCP coming soon)