Re: Backpatch?

Jesus Cea Avion (jcea@ait.uvigo.es) wrote:
: > boggs@osage.csc.ti.com "Lowell Boggs" writes:
: [...]
: > When the variable is unknown, its 'value' points to the linked list of
: > places where it is referenced; as soon as its value is known, the linked
: > list is resolved, and then the variable has its proper value ...
: [...]


: Well, I made a similar implementation in my Pascal and Basic compiler, and
: in my 6502 assembler in the Commodore Vic20 (!!Long time ago!!)


As have _many_ assembler writers since the late fifties, at least,
but it does have a fatal flaw:


: [...] But I had a problem. If you have the following fragment
: of code (680xx family):


: move.l #tableend-table,d0


: where 'tableend' and 'table' are labels with obvious meaning, the 'd0'
: register will be the lenght of that table. You can't resolve that
: references if 'tableend' and 'table' are defined after that line.


Well, there are at least three approaches.


My favorite is to emit a stream of expressions as the object
format. This sort of thing is represented very well by Fraser and Hanson's
"A Machine Independant Linker" (Software-Practice and Experience,
  Vol. 12,351-366 (1982)). Although it pushes a certain amount of work off
to the linker and/or loader, in practice it works marvelously well.
IEE695 is an example of this approach, I believe.


A fair step down is the idea of keeping a "fixup list" that
resides in memory during assembly, and is tagged onto the end of
the generated object file. The fixups could still be arbitrary expressions,
and could include both a pointer and a size, although the news of this
seems not to have percolated far into the *nix world of a.out and
various a.out-with-tailfins formats. By not using the address field
of the instruction, you "waste" a little memory, but you also get the
ability to use less-than-full-address-size expressions (such as 16-bit
displacements on the 68K).


The last approach is the one you are using, dating back at least
to some assemblers I looked at in the mid-sixties. It saves some memory,
but only if the only thing you ever want to re-locate is a full-sized
address. The "expression problem" can be tackled by creating a new
anonymous symbol with some sort of encoding in the "name" field that
indicates the expression to be resolved. I've seen RPN with funny
tokens to indicate other symbols, literal numbers, and "ascii" (well,
readable text :-) operators. Then you chain your new symbol through
the object code in the familiar way. I have seen this done, but don't
feel it has much to recommend it over the option above, as it does not
solve the "small address field" problem.


: In order to backpatching correctly the code, you must convert that line to,
: for example:


: move.l #tableend,d0
: sub.l #table,d0


: Does anybody know how resolve forward references without that problem?.


You could try any of the above. As soon as you forego the minor
savings in memory usage from trying to cram crucial bits of your fixup
information into the left-over bits of the instructions, the problem
simply vanishes. It is still beyond my comprehension how "modern" machines
make me suffer the lack of arbitrary expressions, despite having more
memory than I used to have disk...


Mike


| Mike Albaugh (albaugh@agames.com) Time Warner Interactive
| (The entertainment company formerly known as Atari Games (_NOT_ Tramiel's))
| 675 Sycamore Dr. Milpitas, CA 95035 voice: (408)434-1709
--

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