[Q] Assembling with variable length instructions

Hiya


I've written a program that assembles a list of instructions into
binary form to be executed by a state machine. Instruction labels are
stored in a string table, to be computed at assemble time.


One of the characteristics of the instruction set is that it can use
either absolute or relative jumps, allowing space to be saved for
short jump distances.


Since the instruction size is unknown until I know all the label
addresses, and the label addresses can't be fully determined until all
the instruction sizes are known, I can't see that simple two-pass
assembling will work in this case.


I've come up with several approaches which should get most
relative/absolute jumps, but I can't help thinking there must be an
elegent O(n) solution that has yet to occur to me.


Any hints/suggestions? Apologies if this is a trivial question to
more experienced assembler writers <g>




C-YA
Jon


<http://www.dookie.demon.co.uk>
[Span-dependent-instructions (SDI) turn out to be pretty interesting.
In a slightly generalized form, the problem of coming up with the
optimal set of them is NP-complete, so if you find an O(n) solution, a
lot of people will be pleased to hear about it.


What I've done is to run the first pass assuming that each SDI is
long, noting the location and target of each SDI in a table. Then
between the first and second passes, iterate over the table looking
for an instruction that is long but could be short, shorten it, and
adjust symbol table values appropriately. Repeat until you don't find
any more. This isn't perfectly optimal, but it's close and runs
reasonably fast. There was a paper by Szymanski on SDIs in the CACM
in the early 1970s that lays out all of the theory. -John]

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