Re: 1-pass Assembler Design

Marv Luse wrote:
>
> I have been pondering the design of a 1-pass assembler and have been
> considering schemes for dealing with forward references (i.e., jump to
> label not yet found in source code). Does anyone have any suggestions
> for a practical scheme for doing this? I have devised several
> approaches, but have limited time for investigation, so if someone
> could suggest an approach that would be great.
>
> Thanks!
> Marv Luse
> [Either you have to buffer enough of your output to wait for the
> definitions, potentially buffering an entire assembly, or else you
> need an output language that permits backpatching. Or if you want to
> be really gross, you can write your output file with holes, then
> rewind it and backpatch it in place, adjusting checksums and the like
> on the way. -John]


Steve Russell, of SLR Systems, came up with the ultimate solution for
this problem in his system for the old Z80, CP/M machines. As usual,
whenever I mention SLR, I add that this development system was, IMO,
the best assembly language system ever written, for any computer, at
any price, at any time. Just so's we're clear on _THAT_ <g>.


Steve's solution was not to backpatch at all, but to write files that
had relocation info (and other commands) into the binary files. I
don't know all the details (many of which are proprietary), but I
pieced together enough clues to figure out the general idea. His
linker (which also shared pieces with the assembler) was a classic
abstract machine, complete with stack arithmetic, reverse Polish
notation, etc. This made it capable of doing any kind of address
arithmetic at link time. It also could, of course, do all the usual
resolution of external references, etc., which meant that it
maintained a symbol table.


Steve's slick trick was to keep the kernel of this linker running
alongside the assembler, as well. If a reference was backward, it got
resolved immediately, and the addresses set as literals. Otherwise,
the command got stored in in a queue of pending commands to the
"linker."


During assembly, the assembler was constantly checking to see if a
valid address for one of the linker commands had been found. If so,
and if the backpatch was in range of the object code currently in
memory, the linker command got executed, effectively backpatching
it. Otherwise the command remained.


After all assembly was done, any backpatches that could be resolved,
had been. The remaining ones were written out to the binary file, in
a format suitable for the linker.


In short, SLR's secret was to blur the function of the linker into the
assembler as well, letting it resolve "externals" in the same way the
linker would. Any unresolved references, even though they were
encountered in the same file, were deferred and left to the linker to
resolve. The end result: Linker tables in the binary files that were
a little larger than usual, but that size was easily offset by a
linker that ran at the speed of light, not to mention an assembler
that generated true .com files (not .hex, like the old CP/M
assembler).


Needless to say, Steve had tons of tricks in all the components of the
system to make them run as fast as possible. As a side effect to his
tricky linker, he could resolve even the most bizarre references to
external addresses, such as performing complex arithmetic on addresses
in a different file.


The third part of the SLR system was an easy-to-use librarian. During
linking, you could include libraries much easier than with Microsoft's
linker, and only those functions needed by the system would be loaded.
The librarian also shared the same linker technology, so the same
kinds of resolution of externals was possible. The whole thing ran
incredibly fast. During tests I performed, using a 10Mb hard drive,
the linker/librarian could link a series of files, including library
files, with a speed that was 80% of the raw disk I/O speed. Try _THAT_
with Microsoft's linker!


Jack
--

Return to the comp.compilers page.
Search the comp.compilers archives again.